# Exact Mean Square Linear Stability Analysis for SGD

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 26 references that are in the map.
- First posted on arXiv 13 Jun 2023.

## Builds on (most cited first, 15 of 15)

- [On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima](https://mlsanity.com/paper/1609.04836/) (2016)
- [Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability](https://mlsanity.com/paper/2103.00065/) (2021)
- [Three Factors Influencing Minima in SGD](https://mlsanity.com/paper/1711.04623/) (2017)
- [Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stability](https://mlsanity.com/paper/2209.15594/) (2022)
- [The Break-Even Point on Optimization Trajectories of Deep Neural Networks](https://mlsanity.com/paper/2002.09572/) (2020)
- [On the Relation Between the Sharpest Directions of DNN Loss and the SGD Step Length](https://mlsanity.com/paper/1807.05031/) (2018)
- [Towards Understanding Generalization of Deep Learning: Perspective of Loss Landscapes](https://mlsanity.com/paper/1706.10239/) (2017)
- [The alignment property of SGD noise and how it helps select flat minima: A stability analysis](https://mlsanity.com/paper/2207.02628/) (2022)
- [On Linear Stability of SGD and Input-Smoothness of Neural Networks](https://mlsanity.com/paper/2105.13462/) (2021)
- [Learning Rates as a Function of Batch Size: A Random Matrix Theory Approach to Neural Network Training](https://mlsanity.com/paper/2006.09092/) (2020)
- [Strength of Minibatch Noise in SGD](https://mlsanity.com/paper/2102.05375/) (2021)
- [Noise and Fluctuation of Finite Learning Rate Stochastic Gradient Descent](https://mlsanity.com/paper/2012.03636/) (2020)
- [Step Size Matters in Deep Learning](https://mlsanity.com/paper/1805.08890/) (2018)
- [A view of mini-batch SGD via generating functions: conditions of convergence, phase transitions, benefit from negative momenta](https://mlsanity.com/paper/2206.11124/) (2022)
- [Type-II Saddles and Probabilistic Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/2303.13093/) (2023)

## Built on by (most cited first, 11 of 11)

- [High dimensional analysis reveals conservative sharpening and a stochastic edge of stability](https://mlsanity.com/paper/2404.19261/) (2024)
- [A Defense of the Quadratic Model](https://mlsanity.com/paper/2607.21716/) (2026)
- [Momentum Further Constrains Sharpness at the Edge of Stochastic Stability](https://mlsanity.com/paper/2604.14108/) (2026)
- [On the Stability of Nonlinear Dynamics in GD and SGD: Beyond Quadratic Potentials](https://mlsanity.com/paper/2602.14789/) (2026)
- [Edge Flow: A Tractable and Predictive Continuous-Time Model for Gradient Descent at the Edge of Stability](https://mlsanity.com/paper/2606.18080/) (2026)
- [Variational Learning Finds Flatter Solutions at the Edge of Stability](https://mlsanity.com/paper/2506.12903/) (2025)
- [A Unified Stability Analysis of SAM vs SGD: Role of Data Coherence and Emergence of Simplicity Bias](https://mlsanity.com/paper/2511.17378/) (2025)
- [Understanding diffusion models requires rethinking (again) generalization](https://mlsanity.com/paper/2605.06077/) (2026)
- [Does SGD Seek Flatness or Sharpness? An Exactly Solvable Model](https://mlsanity.com/paper/2602.05065/) (2026)
- [Zeroth-Order Optimization at the Edge of Stability](https://mlsanity.com/paper/2604.14669/) (2026)
- [A Solvable Model of Adaptive Learning Rate Rescaling: Acceleration, Stability & Scaling](https://mlsanity.com/paper/2610.06701/) (2026)

## Abstract (arXiv)

The dynamical stability of optimization methods at the vicinity of minima of the loss has recently attracted significant attention. For gradient descent (GD), stable convergence is possible only to minima that are sufficiently flat w.r.t. the step size, and those have been linked with favorable properties of the trained model. However, while the stability threshold of GD is well-known, to date, no explicit expression has been derived for the exact threshold of stochastic GD (SGD). In this paper, we derive such a closed-form expression. Specifically, we provide an explicit condition on the step size that is both necessary and sufficient for the linear stability of SGD in the mean square sense. Our analysis sheds light on the precise role of the batch size B. In particular, we show that the stability threshold is monotonically non-decreasing in the batch size, which means that reducing the batch size can only decrease stability. Furthermore, we show that SGD's stability threshold is equivalent to that of a mixture process which takes in each iteration a full batch gradient step w.p. 1-p, and a single sample gradient step w.p. p, where p ≈ 1/B . This indicates that even with moderate batch sizes, SGD's stability threshold is very close to that of GD's. We also prove simple necessary conditions for linear stability, which depend on the batch size, and are easier to compute than the precise threshold. Finally, we derive the asymptotic covariance of the dynamics around the minimum, and discuss its dependence on the learning rate. We validate our theoretical findings through experiments on the MNIST dataset.