Accelerating the cubic regularization of Newton’s method on convex problems
Accelerating the cubic regularization of Newton’s method on convex problems
复制标题
DOI：
10.2139/ssrn.885933
复制
发表时间：
2005-09
影响因子：
2.7
通讯作者：
Y. Nesterov
中科院分区：
文献类型：
--
作者：
Y. Nesterov
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.
