Rechercher

sur ce site


Accueil du site > Résumés des séminaires > CO > Résumés > Recent progress in the global complexity analysis of the second-order methods

Recent progress in the global complexity analysis of the second-order methods

Yu. Nesterov (CORE) - 25 septembre 2007

In this talk we discuss an accelerated version of cubic regularization of Newton’s method. The original version, used for minimizing a convex function with Lipschitz-continuous Hessian, guarantees a global rate of convergence of order $O(1 \over k2)$, where $k$ is the iteration counter. Our modified version converges for the same problem class with order $O(1 \over k3)$, 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.

CMAP UMR 7641 École Polytechnique CNRS, Route de Saclay, 91128 Palaiseau Cedex France, Tél: +33 1 69 33 46 23 Fax: +33 1 69 33 46 46