Cubic Regularization of Newton Method and Its Global Performance

Authors

Yurii Nesterov, Boris T. Polyak

Year

2006

Journal Paper

Algorithm

Cubic Regularized Newton

Source

Mathematical Programming

Identifiers

DOI 10.1007/s10107-006-0706-8

Abstract¶

In this paper, we provide theoretical analysis for a cubic regularization of Newton method as applied to unconstrained minimization problem. For this scheme, we prove general local convergence results. However, the main contribution of the paper is related to global worst-case complexity bounds for different problem classes including some nonconvex cases. It is shown that the search direction can be computed by standard linear algebra technique.

Summary¶

Analyzes Newton's method with a cubic model regularizer and proves global worst-case complexity bounds across several smooth optimization classes, including nonconvex cases. The paper is a landmark reference for modern second-order methods with explicit complexity guarantees.