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.