Inexact Newton-CG algorithms with complexity guarantees

DOI10.1093/IMANUM/DRAC043MaRDI QIDQ6171574zbMATH OpenOpenAlexFDO

Authors

Publication date 14 August 2023

Published in IMA Journal of Numerical Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2109.14016

zbMATH Keywords

inexact gradientinexact HessianNewton-CG methodnonconvex optimization

Mathematics Subject Classification ID

Numerical methods based on necessary conditions (49M05) Newton-type methods (49M15) Numerical mathematical programming methods (65K05) Numerical optimization and variational techniques (65K10)

Abstract: We consider variants of a recently-developed Newton-CG algorithm for nonconvex problems citep{royer2018newton} in which inexact estimates of the gradient and the Hessian information are used for various steps. Under certain conditions on the inexactness measures, we derive iteration complexity bounds for achieving $epsilon$-approximate second-order optimality that match best-known lower bounds. Our inexactness condition on the gradient is adaptive, allowing for crude accuracy in regions with large gradients. We describe two variants of our approach, one in which the step-size along the computed search direction is chosen adaptively and another in which the step-size is pre-defined. To obtain second-order optimality, our algorithms will make use of a negative curvature direction on some steps. These directions can be obtained, with high-probability, using a certain randomized algorithm. In this sense, all of our results hold with high-probability over the run of the algorithm. We evaluate the performance of our proposed algorithms empirically on several machine learning models.

Recommendations

• A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization
• Newton-type methods for non-convex optimization under inexact Hessian information
• Linesearch Newton-CG methods for convex optimization with noise
• Convergence of Newton-MR under inexact Hessian information
• Exact and inexact subsampled Newton methods for optimization

Cited in

(7)

• Inexact generalized Newton methods for second order C-differentiable optimization
• Newton-MR: inexact Newton method with minimum residual sub-problem solver
• Hessian averaging in stochastic Newton methods achieves superlinear convergence
• Complexity guarantees for nonconvex Newton-MR under inexact Hessian information
• Yet another fast variant of Newton's method for nonconvex optimization
• A randomized algorithm for nonconvex minimization with inexact evaluations and complexity guarantees
• Riemannian adaptive regularized Newton methods with Hölder continuous Hessians

This page was built for publication: Inexact Newton-CG algorithms with complexity guarantees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6171574)