Hessian averaging in stochastic Newton methods achieves superlinear convergence
From MaRDI portal
(Redirected from Publication:6165593)
Abstract: We consider minimizing a smooth and strongly convex objective function using a stochastic Newton method. At each iteration, the algorithm is given an oracle access to a stochastic estimate of the Hessian matrix. The oracle model includes popular algorithms such as Subsampled Newton and Newton Sketch. Despite using second-order information, these existing methods do not exhibit superlinear convergence, unless the stochastic noise is gradually reduced to zero during the iteration, which would lead to a computational blow-up in the per-iteration cost. We propose to address this limitation with Hessian averaging: instead of using the most recent Hessian estimate, our algorithm maintains an average of all the past estimates. This reduces the stochastic noise while avoiding the computational blow-up. We show that this scheme exhibits local -superlinear convergence with a non-asymptotic rate of , where is proportional to the level of stochastic noise in the Hessian oracle. A potential drawback of this (uniform averaging) approach is that the averaged estimates contain Hessian information from the global phase of the method, i.e., before the iterates converge to a local neighborhood. This leads to a distortion that may substantially delay the superlinear convergence until long after the local neighborhood is reached. To address this drawback, we study a number of weighted averaging schemes that assign larger weights to recent Hessians, so that the superlinear convergence arises sooner, albeit with a slightly slower rate. Remarkably, we show that there exists a universal weighted averaging scheme that transitions to local convergence at an optimal stage, and still exhibits a superlinear convergence rate nearly (up to a logarithmic factor) matching that of uniform Hessian averaging.
Recommendations
- On the asymptotic rate of convergence of stochastic Newton algorithms and their weighted averaged versions
- Superlinearly convergent approximate Newton methods for LC\(^ 1\) optimization problems
- Stochastic approximation method with gradient averaging for unconstrained problems
- A stochastic semismooth Newton method for nonsmooth nonconvex optimization
- scientific article; zbMATH DE number 1329062
- Subsampled Hessian Newton Methods for Supervised Learning
- New basic Hessian approximations for large-scale nonlinear least-squares optimization
- Stochastic regularized Newton methods for nonlinear equations
- Superlinear convergence of conjugate gradients
- Non-asymptotic superlinear convergence of standard quasi-Newton methods
Cites work
- A Characterization of Superlinear Convergence and Its Application to Quasi-Newton Methods
- An adaptive stochastic sequential quadratic programming with differentiable exact augmented Lagrangians
- An investigation of Newton-sketch and subsampled Newton methods
- Convergence of Newton-MR under inexact Hessian information
- Convex optimization: algorithms and complexity
- Exact and inexact subsampled Newton methods for optimization
- First-order and stochastic optimization methods for machine learning
- Freedman's inequality for matrix martingales
- Globally Convergent Levenberg-Marquardt Method for Phase Retrieval
- Greedy quasi-Newton methods with explicit superlinear convergence
- High-dimensional probability. An introduction with applications in data science
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- Hybrid deterministic-stochastic methods for data fitting
- Inexact Newton-CG algorithms with complexity guarantees
- New results on superlinear convergence of classical quasi-Newton methods
- Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence
- Non-asymptotic superlinear convergence of standard quasi-Newton methods
- On the use of stochastic Hessian information in optimization methods for machine learning
- Optimization methods for large-scale machine learning
- Randomized iterative methods for linear systems
- Rates of superlinear convergence for classical quasi-Newton methods
- Sample size selection in optimization methods for machine learning
- Second-order stochastic optimization for machine learning in linear time
- Stochastic optimization using a trust-region method and random models
- Sub-sampled Newton methods
- Subsampled inexact Newton methods for minimizing large sums of convex functions
- Understanding machine learning. From theory to algorithms
- User-friendly tail bounds for sums of random matrices
Cited in
(8)- Subsampled Hessian Newton Methods for Supervised Learning
- Fully stochastic trust-region sequential quadratic programming for equality-constrained optimization problems
- Complexity guarantees for nonconvex Newton-MR under inexact Hessian information
- Randomized Kaczmarz methods with beyond-Krylov convergence
- Panda: partially approximate Newton methods for distributed minimax optimization with unbalanced dimensions
- Statistical inference of constrained stochastic optimization via sketched sequential quadratic programming
- Second-order information promotes mini-batch robustness in variance-reduced gradients
- Online covariance matrix estimation in sketched Newton methods
This page was built for publication: Hessian averaging in stochastic Newton methods achieves superlinear convergence
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6165593)
