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

arXiv: https://arxiv.org/abs/2102.04396 · HTML: https://mlsanity.com/paper/2102.04396/

## Key facts

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

## Builds on (most cited first, 30 of 32)

- [On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima](https://mlsanity.com/paper/1609.04836/) (2016)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Exact solutions to the nonlinear dynamics of learning in deep linear neural networks](https://mlsanity.com/paper/1312.6120/) (2013)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [A Mean Field View of the Landscape of Two-Layers Neural Networks](https://mlsanity.com/paper/1804.06561/) (2018)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [An Investigation into Neural Net Optimization via Hessian Eigenvalue Density](https://mlsanity.com/paper/1901.10159/) (2019)
- [Identifying and attacking the saddle point problem in high-dimensional non-convex optimization](https://mlsanity.com/paper/1406.2572/) (2014)
- [Three Factors Influencing Minima in SGD](https://mlsanity.com/paper/1711.04623/) (2017)
- [Implicit Self-Regularization in Deep Neural Networks: Evidence from Random Matrix Theory and Implications for Learning](https://mlsanity.com/paper/1810.01075/) (2018)
- [A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks](https://mlsanity.com/paper/1901.06053/) (2019)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights](https://mlsanity.com/paper/1503.01243/) (2015)
- [Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit](https://mlsanity.com/paper/1902.06015/) (2019)
- [Eigenvalues of the Hessian in Deep Learning: Singularity and Beyond](https://mlsanity.com/paper/1611.07476/) (2016)
- [Stochastic modified equations and adaptive stochastic gradient algorithms](https://mlsanity.com/paper/1511.06251/) (2015)
- [The Heavy-Tail Phenomenon in SGD](https://mlsanity.com/paper/2006.04740/) (2020)
- [Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates](https://mlsanity.com/paper/1905.09997/) (2019)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [Stochastic gradient descent performs variational inference, converges to limit cycles for deep networks](https://mlsanity.com/paper/1710.11029/) (2017)
- [Neural Mechanics: Symmetry and Broken Conservation Laws in Deep Learning Dynamics](https://mlsanity.com/paper/2012.04728/) (2020)
- [A Variational Analysis of Stochastic Gradient Algorithms](https://mlsanity.com/paper/1602.02666/) (2016)
- [Fluctuation-dissipation relations for stochastic gradient descent](https://mlsanity.com/paper/1810.00004/) (2018)
- [First Exit Time Analysis of Stochastic Gradient Descent Under Heavy-Tailed Gradient Noise](https://mlsanity.com/paper/1906.09069/) (2019)
- [Adaptive Sampling Strategies for Stochastic Optimization](https://mlsanity.com/paper/1710.11258/) (2017)
- [Probabilistic Line Searches for Stochastic Optimization](https://mlsanity.com/paper/1502.02846/) (2015)
- [Halting Time is Predictable for Large Models: A Universality Property and Average-case Analysis](https://mlsanity.com/paper/2006.04299/) (2020)
- [Optimal Randomized First-Order Methods for Least-Squares Problems](https://mlsanity.com/paper/2002.09488/) (2020)
- [Randomized Kaczmarz converges along small singular vectors](https://mlsanity.com/paper/2006.16978/) (2020)

## Built on by (most cited first, 30 of 35)

- [A Dynamical Model of Neural Scaling Laws](https://mlsanity.com/paper/2402.01092/) (2024)
- [High-dimensional limit theorems for SGD: Effective dynamics and critical scaling](https://mlsanity.com/paper/2206.04030/) (2022)
- [How Feature Learning Can Improve Neural Scaling Laws](https://mlsanity.com/paper/2409.17858/) (2024)
- [Scaling and renormalization in high-dimensional regression](https://mlsanity.com/paper/2405.00592/) (2024)
- [Homogenization of SGD in high-dimensions: Exact dynamics and generalization properties](https://mlsanity.com/paper/2205.07069/) (2022)
- [SAM operates far from home: eigenvalue regularization as a dynamical phenomenon](https://mlsanity.com/paper/2302.08692/) (2023)
- [Implicit Regularization or Implicit Conditioning? Exact Risk Trajectories of SGD in High Dimensions](https://mlsanity.com/paper/2206.07252/) (2022)
- [Scaling Collapse Reveals Universal Dynamics in Compute-Optimally Trained Neural Networks](https://mlsanity.com/paper/2507.02119/) (2025)
- [Trajectory of Mini-Batch Momentum: Batch Size Saturation and Convergence in High Dimensions](https://mlsanity.com/paper/2206.01029/) (2022)
- [High dimensional analysis reveals conservative sharpening and a stochastic edge of stability](https://mlsanity.com/paper/2404.19261/) (2024)
- [Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Models](https://mlsanity.com/paper/2106.03696/) (2021)
- [A Random Matrix Theory Perspective on the Spectrum of Learned Features and Asymptotic Generalization Capabilities](https://mlsanity.com/paper/2410.18938/) (2024)
- [Near-Interpolators: Rapid Norm Growth and the Trade-Off between Interpolation and Generalization](https://mlsanity.com/paper/2403.07264/) (2024)
- [Two-Point Deterministic Equivalence for Stochastic Gradient Dynamics in Linear Models](https://mlsanity.com/paper/2502.05074/) (2025)
- [High-dimensional scaling limits and fluctuations of online least-squares SGD with smooth covariance](https://mlsanity.com/paper/2304.00707/) (2023)
- [Unbiased and Sign Compression in Distributed Learning: Comparing Noise Resilience via SDEs](https://mlsanity.com/paper/2502.17009/) (2025)
- [A Nonstochastic Control Approach to Optimization](https://mlsanity.com/paper/2301.07902/) (2023)
- [Three Mechanisms of Feature Learning in a Linear Network](https://mlsanity.com/paper/2401.07085/) (2024)
- [The High Line: Exact Risk and Learning Rate Curves of Stochastic Adaptive Learning Rate Algorithms](https://mlsanity.com/paper/2405.19585/) (2024)
- [Universality of high-dimensional scaling limits of stochastic gradient descent](https://mlsanity.com/paper/2512.13634/) (2025)
- [Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reduction](https://mlsanity.com/paper/2403.06677/) (2024)
- [SGD with memory: fundamental properties and stochastic acceleration](https://mlsanity.com/paper/2410.04228/) (2024)
- [Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton](https://mlsanity.com/paper/2502.13583/) (2025)
- [Statistical Guarantees for High-Dimensional Stochastic Gradient Descent](https://mlsanity.com/paper/2510.12013/) (2025)
- [Adaptive Methods Are Preferable in High Privacy Settings: An SDE Perspective](https://mlsanity.com/paper/2603.03226/) (2026)
- [Statistical Inference for Linear Functionals of Online SGD in High-dimensional Linear Regression](https://mlsanity.com/paper/2302.09727/) (2023)
- [Statistical Inference for Linear Functionals of Online Least-squares SGD when t gtrsim d1+δ](https://mlsanity.com/paper/2510.19734/) (2025)
- [Batches Stabilize the Minimum Norm Risk in High Dimensional Overparameterized Linear Regression](https://mlsanity.com/paper/2306.08432/) (2023)
- [Error dynamics of mini-batch gradient descent with random reshuffling for least squares regression](https://mlsanity.com/paper/2406.03696/) (2024)
- [Estimating Generalization Performance Along the Trajectory of Proximal SGD in Robust Regression](https://mlsanity.com/paper/2410.02629/) (2024)

## 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.