Trust-Region Newton-CG with Strong Second-Order Complexity Guarantees for Nonconvex Optimization
Curtis, F. E.; Robinson, D. P.; Royer, Clément; Wright, S. J. (2019), Trust-Region Newton-CG with Strong Second-Order Complexity Guarantees for Nonconvex Optimization, SIAM Journal on Optimization, 31, 1, p. 518-544. 10.1137/19M130563X
TypeArticle accepté pour publication ou publié
Journal nameSIAM Journal on Optimization
MetadataShow full item record
Author(s)Curtis, F. E.
Robinson, D. P.
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Wright, S. J.
Abstract (EN)Worst-case complexity guarantees for nonconvex optimization algorithms have been a topic of growing interest. Multiple frameworks that achieve the best known complexity bounds among a broad class of first- and second-order strategies have been proposed. These methods have often been designed primarily with complexity guarantees in mind and, as a result, represent a departure from the algorithms that have proved to be the most effective in practice. In this paper, we consider trust-region Newton methods, one of the most popular classes of algorithms for solving nonconvex optimization problems. By introducing slight modifications to the original scheme, we obtain two methods---one based on exact subproblem solves and one exploiting inexact subproblem solves as in the popular “trust-region Newton-conjugate gradient” (trust-region Newton-CG) method---with iteration and operation complexity bounds that match the best known bounds for the aforementioned class of first- and second-order methods. The resulting trust-region Newton-CG method also retains the attractive practical behavior of classical trust-region Newton-CG, which we demonstrate with numerical comparisons on a standard benchmark test set.
Subjects / Keywordssmooth nonconvex optimization; trust-region methods; Newton's method; conjugate gradient method; Lanczos method; worst-case complexity; negative curvature
Showing items related by title and author.
A nonlinear conjugate gradient method with complexity guarantees and its application to nonconvex regression Chan-Renous-Legoubin, Rémi; Royer, Clément W. (2022) Article accepté pour publication ou publié
Bergou, El Houcine; Diouane, Youssef; Kunc, Vladimir; Kungurtsev, Vyacheslav; Royer, Clément (2022) Article accepté pour publication ou publié
Corrigendum for "Second-order reflected backward stochastic differential equations" and "Second-order BSDEs with general reflection and game options under uncertainty" Matoussi, Anis; Possamaï, Dylan; Zhou, Chao (2021) Article accepté pour publication ou publié
Viscosity solutions of fully nonlinear second-order equations and optimal stochastic control in infinite dimensions. III. Uniqueness of viscosity solutions for general second-order equations Lions, Pierre-Louis (1989) Article accepté pour publication ou publié