mlsanityData to 7 Oct 2026

SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality

arXiv 2102.04396 ↗First posted 8 Feb 2021math.OC cs.LG math.PRcited by 33

Not on the map. Why?

Abstract (arXiv)

We propose a new framework, inspired by random matrix theory, for analyzing the dynamics of stochastic gradient descent (SGD) when both number of samples and dimensions are large. This framework applies to any fixed stepsize and the finite sum setting. Using this new framework, we show that the dynamics of SGD on a least squares problem with random data become deterministic in the large sample and dimensional limit. Furthermore, the limiting dynamics are governed by a Volterra integral equation. This model predicts that SGD undergoes a phase transition at an explicitly given critical stepsize that ultimately affects its convergence rate, which we also verify experimentally. Finally, when input data is isotropic, we provide explicit expressions for the dynamics and average-case convergence rates (i.e., the complexity of an algorithm averaged over all possible inputs). These rates show significant improvement over the worst-case complexities.

Key facts. Cited by 33 papers in the map (data through 7 Oct 2026). Builds on 32 of its 85 references that are in the map. First posted on arXiv 8 Feb 2021.

Builds on

32 of 85 references.

References · 32

  1. 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,337
  2. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  3. 2013Exact solutions to the nonlinear dynamics of learning in deep linear neural networkscited by 748
  4. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  5. 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 508
  6. 2018A Mean Field View of the Landscape of Two-Layers Neural Networkscited by 463
  7. 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 410
  8. 2019An Investigation into Neural Net Optimization via Hessian Eigenvalue Densitycited by 289
  9. 2014Identifying and attacking the saddle point problem in high-dimensional non-convex optimizationcited by 286
  10. 2017Three Factors Influencing Minima in SGDcited by 270
  11. 2019A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networkscited by 213
  12. 2018Implicit Self-Regularization in Deep Neural Networks: Evidence from Random Matrix Theory and Implications for Learningcited by 211
20 more
  1. 2019SGD: General Analysis and Improved Ratescited by 206
  2. 2015A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insightscited by 203
  3. 2019Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limitcited by 187
  4. 2016Eigenvalues of the Hessian in Deep Learning: Singularity and Beyondcited by 156
  5. 2015Stochastic modified equations and adaptive stochastic gradient algorithmscited by 141
  6. 2020The Heavy-Tail Phenomenon in SGDcited by 122
  7. 2019Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Ratescited by 119
  8. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 110
  9. 2017Stochastic gradient descent performs variational inference, converges to limit cycles for deep networkscited by 108
  10. 2020Neural Mechanics: Symmetry and Broken Conservation Laws in Deep Learning Dynamicscited by 93
  11. 2016A Variational Analysis of Stochastic Gradient Algorithmscited by 56
  12. 2018Fluctuation-dissipation relations for stochastic gradient descentcited by 47
  13. 2019First Exit Time Analysis of Stochastic Gradient Descent Under Heavy-Tailed Gradient Noisecited by 43
  14. 2015Probabilistic Line Searches for Stochastic Optimizationcited by 29
  15. 2017Adaptive Sampling Strategies for Stochastic Optimizationcited by 29
  16. 2020Halting Time is Predictable for Large Models: A Universality Property and Average-case Analysiscited by 14
  17. 2020Optimal Randomized First-Order Methods for Least-Squares Problemscited by 10
  18. 2020Randomized Kaczmarz converges along small singular vectorscited by 9
  19. 2020Average-case Acceleration Through Spectral Density Estimationcited by 3
  20. 2015Universal halting times in optimization and machine learningcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 4; 2023: 5; 2024: 12; 2025: 7; 2026: 4.

33 papers.

Sort:

By area:

  1. 2024A Dynamical Model of Neural Scaling Lawscited by 105
  2. 2022High-dimensional limit theorems for SGD: Effective dynamics and critical scalingcited by 69
  3. 2024How Feature Learning Can Improve Neural Scaling Lawscited by 55
  4. 2024Scaling and renormalization in high-dimensional regressioncited by 45
  5. 2022Homogenization of SGD in high-dimensions: Exact dynamics and generalization propertiescited by 26
  6. 2023SAM operates far from home: eigenvalue regularization as a dynamical phenomenoncited by 24
  7. 2022Implicit Regularization or Implicit Conditioning? Exact Risk Trajectories of SGD in High Dimensionscited by 23
  8. 2025Scaling Collapse Reveals Universal Dynamics in Compute-Optimally Trained Neural Networkscited by 21
  9. 2021Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Modelscited by 15
  10. 2022Trajectory of Mini-Batch Momentum: Batch Size Saturation and Convergence in High Dimensionscited by 15
  11. 2024High dimensional analysis reveals conservative sharpening and a stochastic edge of stabilitycited by 15
  12. 2024A Random Matrix Theory Perspective on the Spectrum of Learned Features and Asymptotic Generalization Capabilitiescited by 14
21 more
  1. 2024Near-Interpolators: Rapid Norm Growth and the Trade-Off between Interpolation and Generalizationcited by 7
  2. 2025Two-Point Deterministic Equivalence for Stochastic Gradient Dynamics in Linear Modelscited by 6
  3. 2023High-dimensional scaling limits and fluctuations of online least-squares SGD with smooth covariancecited by 5
  4. 2023A Nonstochastic Control Approach to Optimizationcited by 4
  5. 2025Unbiased and Sign Compression in Distributed Learning: Comparing Noise Resilience via SDEscited by 4
  6. 2024Three Mechanisms of Feature Learning in a Linear Networkcited by 3
  7. 2024The High Line: Exact Risk and Learning Rate Curves of Stochastic Adaptive Learning Rate Algorithmscited by 3
  8. 2024SGD with memory: fundamental properties and stochastic accelerationcited by 2
  9. 2025Statistical Guarantees for High-Dimensional Stochastic Gradient Descentcited by 2
  10. 2023Statistical Inference for Linear Functionals of Online SGD in High-dimensional Linear Regressioncited by 1
  11. 2024Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reductioncited by 1
  12. 2025Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newtoncited by 1
  13. 2025Statistical Inference for Linear Functionals of Online Least-squares SGD when t gtrsim d1+δcited by 1
  14. 2026Adaptive Methods Are Preferable in High Privacy Settings: An SDE Perspectivecited by 1
  15. 2023Batches Stabilize the Minimum Norm Risk in High Dimensional Overparameterized Linear Regressioncited by 0
  16. 2024Error dynamics of mini-batch gradient descent with random reshuffling for least squares regressioncited by 0
  17. 2024Estimating Generalization Performance Along the Trajectory of Proximal SGD in Robust Regressioncited by 0
  18. 2025Universality of high-dimensional scaling limits of stochastic gradient descentcited by 0
  19. 2026Distribution-Aware Algorithm Design with LLM Agentscited by 0
  20. 2026Factor Augmented High-Dimensional SGDcited by 0
  21. 2026Beyond Negative-Ridge Endpoints: Mixed-Sign Spectral Regularization via Negative-Shifted Gradient Descentcited by 0