mlsanityData to 14 Oct 2026

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

arXiv 2106.03696 ↗First posted 7 Jun 2021math.OC cs.LG math.PRcited by 16

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 16 papers in the map (data through 14 Oct 2026). Builds on 28 of its 52 references that are in the map. First posted on arXiv 7 Jun 2021.

Builds on

28 of 52 references.

References · 28

  1. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
  2. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  3. 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 513
  4. 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 413
  5. 2018Measuring the Intrinsic Dimension of Objective Landscapescited by 370
  6. 2019An Investigation into Neural Net Optimization via Hessian Eigenvalue Densitycited by 292
  7. 2014Identifying and attacking the saddle point problem in high-dimensional non-convex optimizationcited by 289
  8. 2018Implicit Self-Regularization in Deep Neural Networks: Evidence from Random Matrix Theory and Implications for Learningcited by 215
  9. 2016Eigenvalues of the Hessian in Deep Learning: Singularity and Beyondcited by 159
  10. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  11. 2015Stochastic modified equations and adaptive stochastic gradient algorithmscited by 142
  12. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 135
16 more
  1. 2019Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Modelcited by 117
  2. 2018Stochastic Modified Equations and Dynamics of Stochastic Gradient Algorithms I: Mathematical Foundationscited by 114
  3. 2020A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descentcited by 70
  4. 2016A Variational Analysis of Stochastic Gradient Algorithmscited by 57
  5. 2018A Unified Analysis of Stochastic Momentum Methods for Deep Learningcited by 55
  6. 2020Learning Rates as a Function of Batch Size: A Random Matrix Theory Approach to Neural Network Trainingcited by 50
  7. 2017Momentum and Stochastic Momentum for Stochastic Gradient, Newton, Proximal Point and Subspace Descent Methodscited by 49
  8. 2018On the insufficiency of existing momentum schemes for Stochastic Optimizationcited by 49
  9. 2016Stochastic Heavy Ballcited by 42
  10. 2021SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticalitycited by 35
  11. 2020On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settingscited by 27
  12. 2015From Averaging to Acceleration, There is Only a Step-sizecited by 24
  13. 2019Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distancescited by 16
  14. 2018Robust Accelerated Gradient Methods for Smooth Strongly Convex Functionscited by 12
  15. 2019The Role of Memory in Stochastic Optimizationcited by 10
  16. 2019A Generic Acceleration Framework for Stochastic Composite Optimizationcited by 9

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 5; 2023: 2; 2024: 5; 2025: 1; 2026: 3.

16 papers.

Sort:

  1. 2022Implicit Regularization or Implicit Conditioning? Exact Risk Trajectories of SGD in High Dimensionscited by 23
  2. 2022Trajectory of Mini-Batch Momentum: Batch Size Saturation and Convergence in High Dimensionscited by 19
  3. 2026A Defense of the Quadratic Modelcited by 14
  4. 2022A view of mini-batch SGD via generating functions: conditions of convergence, phase transitions, benefit from negative momentacited by 11
  5. 2022Provable Acceleration of Heavy Ball beyond Quadratics for a Class of Polyak-Lojasiewicz Functions when the Non-Convexity is Averaged-Outcited by 11
  6. 2026Momentum Further Constrains Sharpness at the Edge of Stochastic Stabilitycited by 10
  7. 2022Accelerated SGD for Non-Strongly-Convex Least Squarescited by 9
  8. 2024Exact Risk Curves of signSGD in High-Dimensions: Quantifying Preconditioning and Noise-Compression Effectscited by 7
  9. 2023High-dimensional scaling limits and fluctuations of online least-squares SGD with smooth covariancecited by 6
  10. 2024The High Line: Exact Risk and Learning Rate Curves of Stochastic Adaptive Learning Rate Algorithmscited by 3
  11. 2024SGD with memory: fundamental properties and stochastic accelerationcited by 2
  12. 2023Statistical Inference for Linear Functionals of Online SGD in High-dimensional Linear Regressioncited by 1
4 more
  1. 2024(Accelerated) Noise-adaptive Stochastic Heavy-Ball Momentumcited by 1
  2. 2024Stochastic Gradient Flow Dynamics of Test Risk and its Exact Solution for Weak Featurescited by 1
  3. 2025Statistical Inference for Linear Functionals of Online Least-squares SGD when t gtrsim d1+δcited by 1
  4. 2026Dynamics of Stochastic Momentum with Sparse Updates in High Dimensionscited by 0