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

Nesterov, Yurii
(2008) Mathematical Programming — Vol. 112, n° 1, p. 159-181 (2008)

Files

pdfdocument.pdf
  • Restricted Access
  • Adobe PDF
  • 291.08 KB
Request a copy

Details

Authors
  • Nesterov, YuriiUCLouvain
    Author
Abstract
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 O1k2 , where k is the iteration counter. Our modified version converges for the same problem class with order O1k3 , 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.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Nesterov, Y. (2008). Accelerating the cubic regularization of Newton’s method on convex problems. Mathematical Programming, 112(1), 159-181. https://doi.org/10.1007/s10107-006-0089-x (Original work published 2008)