Complexity of Minimizing Regularized Convex Quadratic Functions

In this work, we study the iteration complexity of gradient methods minimizing the class of uniformly convex regularized quadratic functions. We prove lower bounds on the functional residual of the form (N^-2p/ (p-2) ), where p > 2 is the power of the regularization term, and N is the number of calls to a first-order oracle. A special case of our problem class is p=3, which is the minimization of cubically regularized convex quadratic functions. It naturally appears as a subproblem at each iteration of the cubic Newton method. The corresponding lower bound for p = 3 becomes (N^-6). Our result matches the best-known upper bounds on this problem class, rendering a sharp analysis of the minimization of uniformly convex regularized quadratic functions. We also establish new lower bounds on minimizing the gradient norm within our framework.