Accelerating the cubic regularization of Newton’s method on convex problems

In this paper we propose an accelerated version of the cubic regularization of Newton’s method (Nesterov and Polyak, in Math Program 108(1): 177–205, 2006). The original version, used for minimizing a convex function with Lipschitz-continuous Hessian, guarantees a global rate of convergence of order \(O\big({1 \over k^2}\big)\), where k is the iteration counter. Our modified version converges for the same problem class with order \(O\big({1 \over k^3}\big)\), keeping the complexity of each iteration unchanged. We study the complexity of both schemes on different classes of convex problems. In particular, we argue that for the second-order schemes, the class of non-degenerate problems is different from the standard class.

Authors and Affiliations

1. Center for Operations Research and Econometrics (CORE), Catholic University of Louvain (UCL), 34 voie du Roman Pays, 1348, Louvain-la-Neuve, Belgium

   Yu. Nesterov

Corresponding author

Correspondence to Yu. Nesterov.

The research results presented in this paper have been supported by a grant “Action de recherche concertè ARC 04/09-315” from the “Direction de la recherche scientifique - Communautè française de Belgique”. The scientific responsibility rests with the author.

Reprints and permissions