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

Nesterov, Yurii
(2005)

Files

dp2005_68.pdf
  • Open Access
  • Adobe PDF
  • 202.48 KB
Download

Details

Authors
  • Nesterov, YuriiUCLouvain
    Author
Abstract
In this paper we propose an accelerated version of the cubic regularization of Newton's method [6]. The original version, used for minimizing a convex function with Lipschitz-continuous Hessian, guarantees a global rate of convergence of order O(1/k exp.2), where k is the iteration counter. Our modified version converges for the same problem class with order O(1/k exp.3), 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. (2005). Accelerating the cubic regularization of Newton’s method on convex problems (CORE Discussion Papers 2005/68). https://hdl.handle.net/2078.5/40673