Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Models

2021/06/07 by Courtney Paquette, Paquette, Courtney, Elliot Paquette +1 · 1 citation
Computer Science · Engineering · Mathematics · #Algorithm #Applied mathematics #FOS: Computer and information sciences #FOS: Mathematics #Hessian matrix #Hyperparameter #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Mathematical optimization #Mathematics #Momentum (technical analysis) #Optimization and Control (math.OC) #Probability (math.PR) #Quadratic equation #Random Matrices and Applications #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Stochastic optimization #cs.LG #math.OC #math.PR #stat.ML

paper · pdf · doi:10.48550/arxiv.2106.03696

published in arXiv (Cornell University) 34 (Cornell University) · 39 pages, 7 figures

openalex publication_date 2021/06/07 · arxiv created 2021/10/26 · arxiv updated 2021/10/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06

Abstract

We analyze a class of stochastic gradient algorithms with momentum on a high-dimensional random least squares problem. Our framework, inspired by random matrix theory, provides an exact (deterministic) characterization for the sequence of loss values produced by these algorithms which is expressed only in terms of the eigenvalues of the Hessian. This leads to simple expressions for nearly-optimal hyperparameters, a description of the limiting neighborhood, and average-case complexity. As a consequence, we show that (small-batch) stochastic heavy-ball momentum with a fixed momentum parameter provides no actual performance improvement over SGD when step sizes are adjusted correctly. For contrast, in the non-strongly convex setting, it is possible to get a large improvement over SGD using momentum. By introducing hyperparameters that depend on the number of samples, we propose a new algorithm sDANA (stochastic dimension adjusted Nesterov acceleration) which obtains an asymptotically optimal average-case complexity while remaining linearly convergent in the strongly convex setting without adjusting parameters.

Citations

• Eigenvalues of the Hessian in Deep Learning: Singularity and Beyond
• An Investigation into Neural Net Optimization via Hessian Eigenvalue Density
• The Full Spectrum of Deepnet Hessians at Scale: Dynamics with SGD Training and Sample Size
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Accelerating SGD with momentum for over-parameterized learning

Cited by

• Statistical Inference for Linear Functionals of Online Least-squares SGD when t \gtrsim d^1+δ

Related

• Momentum and Stochastic Momentum for Stochastic Gradient, Newton, Proximal Point and Subspace Descent Methods
• Does Momentum Help? A Sample Complexity Analysis
• Dimension-adapted Momentum Outscales SGD
• On the Hyperparameters in Stochastic Gradient Descent with Momentum
• (Accelerated) Noise-adaptive Stochastic Heavy-Ball Momentum