Convergence of Newton-MR under inexact Hessian information
From MaRDI portal
Publication:5148404
DOI10.1137/19M1302211zbMATH Open1458.90473arXiv1909.06224MaRDI QIDQ5148404FDOQ5148404
Authors: Yang Liu, Fred Roosta 
Publication date: 4 February 2021
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1909.06224
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
Numerical mathematical programming methods (65K05) Large-scale problems in mathematical programming (90C06) Nonlinear programming (90C30)
Cites Work
- MINRES-QLP: a Krylov subspace method for indefinite or singular symmetric systems
- ASTRO-DF: a class of adaptive sampling trust-region algorithms for derivative-free stochastic optimization
- Adaptive subgradient methods for online learning and stochastic optimization
- Title not available (Why is that?)
- A note on performance profiles for benchmarking software
- Title not available (Why is that?)
- Title not available (Why is that?)
- Benchmarking optimization software with performance profiles.
- Introductory lectures on convex optimization. A basic course.
- Title not available (Why is that?)
- On the use of stochastic Hessian information in optimization methods for machine learning
- An Algorithm for Least-Squares Estimation of Nonlinear Parameters
- Understanding machine learning. From theory to algorithms
- A method for the solution of certain non-linear problems in least squares
- Sample size selection in optimization methods for machine learning
- Trust Region Methods
- Matrix mathematics. Theory, facts, and formulas
- On sufficiency of the Kuhn-Tucker conditions
- What is invexity?
- Convergence of quasi-Newton matrices generated by the symmetric rank one update
- Stochastic algorithms for inverse problems involving PDEs and many measurements
- Solution of Sparse Indefinite Systems of Linear Equations
- Title not available (Why is that?)
- Title not available (Why is that?)
- Linear and nonlinear functional analysis with applications. With 401 problems and 52 figures
- Invexity and optimization
- GMRES, L-curves, and discrete ill-posed problems
- The optimal perturbation bounds of the Moore-Penrose inverse under the Frobenius norm
- Stochastic optimization using a trust-region method and random models
- Convergence of trust-region methods based on probabilistic models
- Stochastic derivative-free optimization using a trust region framework
- Non-asymptotic theory of random matrices: extreme singular values
- 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
- Analysis of a Symmetric Rank-One Trust Region Method
- Cubic regularization of Newton method and its global performance
- Some bounds on the complexity of gradients, Jacobians, and Hessians
- Complexity bounds for second-order optimality in unconstrained optimization
- Convex optimization algorithms
- Rank Degeneracy
- Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization
- Accelerated methods for nonconvex optimization
- 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
- Sub-sampled Newton methods
- Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence
- An investigation of Newton-sketch and subsampled Newton methods
- Exact and inexact subsampled Newton methods for optimization
- Newton-type methods for non-convex optimization under inexact Hessian information
- A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization
- Vector calculus, linear algebra, and differential forms. A unified approach
- Complexity and global rates of trust-region methods based on probabilistic models
Cited In (7)
- 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
- A structured L-BFGS method and its application to inverse problems
Uses Software
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)
