# Train faster, generalize better: Stability of stochastic gradient descent

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

## Key facts

- Cited by 552 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Sep 2015.

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

- [Detecting Pretraining Data from Large Language Models](https://mlsanity.com/paper/2310.16789/) (2023)
- [Membership Inference Attacks on Machine Learning: A Survey](https://mlsanity.com/paper/2103.07853/) (2021)
- [Model Merging in LLMs, MLLMs, and Beyond: Methods, Theories, Applications and Opportunities](https://mlsanity.com/paper/2408.07666/) (2024)
- [Training Neural Networks with Fixed Sparse Masks](https://mlsanity.com/paper/2111.09839/) (2021)
- [On the Effectiveness of Parameter-Efficient Fine-Tuning](https://mlsanity.com/paper/2211.15583/) (2022)
- [Reasonable Effectiveness of Random Weighting: A Litmus Test for Multi-Task Learning](https://mlsanity.com/paper/2111.10603/) (2021)
- [Benign Overfitting in Two-layer Convolutional Neural Networks](https://mlsanity.com/paper/2202.06526/) (2022)
- [Information-Theoretic Generalization Bounds for Stochastic Gradient Descent](https://mlsanity.com/paper/2102.00931/) (2021)
- [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021)
- [Topology-Aware Segmentation Using Discrete Morse Theory](https://mlsanity.com/paper/2103.09992/) (2021)
- [On the geometry of generalization and memorization in deep neural networks](https://mlsanity.com/paper/2105.14602/) (2021)
- [Neural Networks Efficiently Learn Low-Dimensional Representations with SGD](https://mlsanity.com/paper/2209.14863/) (2022)
- [Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss](https://mlsanity.com/paper/2205.13710/) (2022)
- [Sharp-MAML: Sharpness-Aware Model-Agnostic Meta Learning](https://mlsanity.com/paper/2206.03996/) (2022)
- [Gradient Norm Aware Minimization Seeks First-Order Flatness and Improves Generalization](https://mlsanity.com/paper/2303.03108/) (2023)
- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [Langevin Unlearning: A New Perspective of Noisy Gradient Descent for Machine Unlearning](https://mlsanity.com/paper/2401.10371/) (2024)
- [LoRA Training in the NTK Regime has No Spurious Local Minima](https://mlsanity.com/paper/2402.11867/) (2024)
- [Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings](https://mlsanity.com/paper/2107.05585/) (2021)
- [Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)](https://mlsanity.com/paper/2103.12024/) (2021)
- [Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensing](https://mlsanity.com/paper/2301.11500/) (2023)
- [Subspace Adversarial Training](https://mlsanity.com/paper/2111.12229/) (2021)
- [Towards Understanding the Generalization of Graph Neural Networks](https://mlsanity.com/paper/2305.08048/) (2023)
- [Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion](https://mlsanity.com/paper/2302.04451/) (2023)
- [Low-Pass Filtering SGD for Recovering Flat Optima in the Deep Learning Optimization Landscape](https://mlsanity.com/paper/2201.08025/) (2022)
- [SGD Generalizes Better Than GD (And Regularization Doesn't Help)](https://mlsanity.com/paper/2102.01117/) (2021)
- [On Convergence of FedProx: Local Dissimilarity Invariant Bounds, Non-smoothness and Beyond](https://mlsanity.com/paper/2206.05187/) (2022)
- [Topology-aware Generalization of Decentralized SGD](https://mlsanity.com/paper/2206.12680/) (2022)
- [Spectral Bias in Practice: The Role of Function Frequency in Generalization](https://mlsanity.com/paper/2110.02424/) (2021)
- [Why Is Public Pretraining Necessary for Private Model Training?](https://mlsanity.com/paper/2302.09483/) (2023)

## Abstract (arXiv)

We show that parametric models trained by a stochastic gradient method (SGM) with few iterations have vanishing generalization error. We prove our results by arguing that SGM is algorithmically stable in the sense of Bousquet and Elisseeff. Our analysis only employs elementary tools from convex and continuous optimization. We derive stability bounds for both convex and non-convex optimization under standard Lipschitz and smoothness assumptions. Applying our results to the convex case, we provide new insights for why multiple epochs of stochastic gradient methods generalize well in practice. In the non-convex case, we give a new interpretation of common practices in neural networks, and formally show that popular techniques for training large deep models are indeed stability-promoting. Our findings conceptually underscore the importance of reducing training time beyond its obvious benefit.