Convergence of Newton-MR under inexact Hessian information
From MaRDI portal
Publication:5148404
Abstract: Recently, there has been a surge of interest in designing variants of the classical Newton-CG in which the Hessian of a (strongly) convex function is replaced by suitable approximations. This is mainly motivated by large-scale finite-sum minimization problems that arise in many machine learning applications. Going beyond convexity, inexact Hessian information has also been recently considered in the context of algorithms such as trust-region or (adaptive) cubic regularization for general non-convex problems. Here, we do that for Newton-MR, which extends the application range of the classical Newton-CG beyond convexity to invex problems. Unlike the convergence analysis of Newton-CG, which relies on spectrum preserving Hessian approximations in the sense of L"{o}wner partial order, our work here draws from matrix perturbation theory to estimate the distance between the subspaces underlying the exact and approximate Hessian matrices. Numerical experiments demonstrate a great degree of resilience to such Hessian approximations, amounting to a highly efficient algorithm in large-scale problems.
Recommendations
- Newton-type methods for non-convex optimization under inexact Hessian information
- Adaptive cubic regularization methods with dynamic inexact Hessian information and applications to finite-sum minimization
- Sub-sampled Newton methods
- Subsampled inexact Newton methods for minimizing large sums of convex functions
- Exact and inexact subsampled Newton methods for optimization
Cites work
- scientific article; zbMATH DE number 47363 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 783550 (Why is no real title available?)
- scientific article; zbMATH DE number 852532 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization
- A method for the solution of certain non-linear problems in least squares
- A note on performance profiles for benchmarking software
- ASTRO-DF: a class of adaptive sampling trust-region algorithms for derivative-free stochastic optimization
- Accelerated methods for nonconvex optimization
- Adaptive cubic regularisation methods for unconstrained optimization. I: Motivation, convergence and numerical results
- Adaptive cubic regularisation methods for unconstrained optimization. II: Worst-case function- and derivative-evaluation complexity
- Adaptive subgradient methods for online learning and stochastic optimization
- An Algorithm for Least-Squares Estimation of Nonlinear Parameters
- An investigation of Newton-sketch and subsampled Newton methods
- Analysis of a Symmetric Rank-One Trust Region Method
- Benchmarking optimization software with performance profiles.
- Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization
- Complexity and global rates of trust-region methods based on probabilistic models
- Complexity bounds for second-order optimality in unconstrained optimization
- Convergence of quasi-Newton matrices generated by the symmetric rank one update
- Convergence of trust-region methods based on probabilistic models
- Convex optimization algorithms
- Cubic regularization of Newton method and its global performance
- Exact and inexact subsampled Newton methods for optimization
- GMRES, L-curves, and discrete ill-posed problems
- Introductory lectures on convex optimization. A basic course.
- Invexity and optimization
- Linear and nonlinear functional analysis with applications. With 401 problems and 52 figures
- MINRES-QLP: a Krylov subspace method for indefinite or singular symmetric systems
- Matrix mathematics. Theory, facts, and formulas
- Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence
- Newton-type methods for non-convex optimization under inexact Hessian information
- Non-asymptotic theory of random matrices: extreme singular values
- On sufficiency of the Kuhn-Tucker conditions
- On the use of stochastic Hessian information in optimization methods for machine learning
- Perturbation analysis of the Moore-Penrose inverse for a class of bounded operators in Hilbert spaces
- Random perturbation of low rank matrices: improving classical bounds
- Rank Degeneracy
- Sample size selection in optimization methods for machine learning
- Solution of Sparse Indefinite Systems of Linear Equations
- Some bounds on the complexity of gradients, Jacobians, and Hessians
- Stochastic algorithms for inverse problems involving PDEs and many measurements
- Stochastic derivative-free optimization using a trust region framework
- Stochastic optimization using a trust-region method and random models
- Sub-sampled Newton methods
- The optimal perturbation bounds of the Moore-Penrose inverse under the Frobenius norm
- Trust Region Methods
- Understanding machine learning. From theory to algorithms
- Vector calculus, linear algebra, and differential forms. A unified approach
- What is invexity?
Cited in
(7)- A structured L-BFGS method and its application to inverse problems
- Hessian averaging in stochastic Newton methods achieves superlinear convergence
- MINRES: from negative curvature detection to monotonicity properties
- Linesearch Newton-CG methods for convex optimization with noise
- Inexact Newton-CG algorithms with complexity guarantees
- Newton-type methods for non-convex optimization under inexact Hessian information
- Newton-MR: inexact Newton method with minimum residual sub-problem solver
This page was built for publication: Convergence of Newton-MR under inexact Hessian information
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5148404)
