Complexity of Minimizing Regularized Convex Quadratic Functions
研究了用梯度方法最小化带有欧几里得范数次幂正则项的凸二次函数的迭代复杂度，证明了一类一阶方法的最优下界，并设计了新步长的简单梯度下降达到最优收敛率，数值实验证实了结论，适合优化领域研究者。
Abstract. In this work, we study the iteration complexity of gradient methods for minimizing convex quadratic functions regularized by powers of Euclidean norms. We show that, due to the uniform convexity of the objective, gradient methods have improved convergence rates. For the general class of all first-order methods, we prove a lower bound on the rate of order [Formula: see text] in terms of the functional residual, where [Formula: see text] is the iteration number and [Formula: see text] is the power of the regularization term. This rate is optimal and was previously achieved by the composite fast gradient method. Therefore, we establish that this rate is tight for the class of uniformly convex quadratic functions. A special case of our problem is [Formula: see text], i.e., cubically regularized convex quadratic functions. It naturally appears as a subproblem at each iteration of the cubic Newton method, and our theory shows that the rate of [Formula: see text] is optimal in this case. Despite its theoretical efficiency, the composite gradient methods requires solving a univariate nonlinear equation of order [Formula: see text] to compute the step. In contrast, we develop a simple version of the basic gradient descent using a novel step size that has a convergence rate of [Formula: see text]. We show that this rate is unimprovable for a class of first-order momentum-free methods with small step sizes. Numerical experiments also demonstrate the tightness of our bounds.