Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function- and derivative-evaluation complexity

By Coralia Cartis, N. Gould, Philippe L. Toint. Mathematical programming, 2011

373 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/ff23573d802b24a90527f6c455afb0e37e786de9

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Michael W. Mahoney
2. Kurt Keutzer
3. Martin Jaggi
4. A. Gholami
5. Aurélien Lucchi
6. Zi-Mei Yao
7. Simon Lacoste-Julien
8. Michael I. Jordan

In Computational Mechanics

1. Michael I. Jordan
2. Aurélien Lucchi
3. Ya-Xiang Yuan
4. Simon Lacoste-Julien
5. Martin Jaggi
6. Matilde Gargiani
7. Thomas Hofmann
8. Chi Jin

In Numerical Analysis

1. Ya-Xiang Yuan
2. Michael I. Jordan
3. Aurélien Lucchi
4. Coralia Cartis
5. N. Gould
6. Philippe L. Toint
7. Martin Jaggi
8. Thomas Hofmann

Citations in the corpus

• trlib: a vector-free implementation of the GLTR method for iterative solution of the trust region problem (2016, background): “Recently, trust region-like algorithms with guaranteed complexity estimates in relation to the KKT tolerance have been proposed [5, 6, 10].”
• Recent advances in trust region algorithms (2015, methodology): “Worst-case function-and derivative-evaluation complexity of the ARC method is studied in [15].”
• Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results (2011, methodology): “Our purpose here and in [2] is to unify and extend these contributions into a coherent and numerically efficient algorithmic framework, for which global and asymptotic convergence results can be proved under weaker assumptions and with simpler proofs, while preserving the good complexity bound shown…”
• A Subsampling Line-Search Method with Second-Order Results (2018, methodology): “The norm of this “next gradient” is a major tool for the derivation of complexity results in Newton-type methods [14, 44].”
• PyHessian: Neural Networks Through the Lens of the Hessian (2019, background): “[12] Coralia Cartis, Nicholas IM Gould, and Philippe L Toint.”
• Global rates of convergence for nonconvex optimization on manifolds (2016, neutral): “5 ) to generate x with grad f ( x ) ≤ ε have also been given for cubic regularization methods (Cartis et al., 2011a,b) and sophisticated trust region variants (Curtis et al., 2016).”
• Stochastic Cubic Regularization for Fast Nonconvex Optimization (2017, methodology): “Later, the ARC algorithm [Cartis et al., 2011] and trust-region methods [Curtis et al.”
• A Distributed Second-Order Algorithm You Can Trust (2018, methodology): “Here we suggest updating σ at each iteration of the algorithm using an update rule inspired by trust-region methods (Cartis et al., 2011), where σ acts as the reciprocal of the trust-region radius.”