Train faster, generalize better: Stability of stochastic gradient descent
By Moritz Hardt, B. Recht, Yoram Singer. 2015
1,448 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training, Scaling & Learning Theory
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Yoshua Bengio
- Percy Liang
- Sergey Levine
- Mohit Bansal
- Quoc V. Le
- Ruslan Salakhutdinov
- Dacheng Tao
- Jianfeng Gao
In Computational Mechanics
- Peter Richtárik
- Nicolas Loizou
- Jason D. Lee
- Tengyu Ma
- Simon Lacoste-Julien
- Yuanzhi Li
- Michael I. Jordan
- Nati Srebro
In Optimization & Training
- Peter Richtárik
- Tengyu Ma
- Yoshua Bengio
- Jason D. Lee
- Nicolas Loizou
- Yuanzhi Li
- Simon Lacoste-Julien
- Martin Jaggi
In Scaling & Learning Theory
- Tengyu Ma
- Yuanzhi Li
- Jason D. Lee
- Behnam Neyshabur
- Colin Wei
- Samet Oymak
- Quanquan Gu
- Simon Shaolei Du
Citations in the corpus
- Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, background): “Stochastic gradient descent (SGD) (Robbins and Monro, 1951; Nemirovski and Yudin, 1978, 1983; Shalev-Shwartz et al., 2007; Nemirovski et al., 2009; Hardt et al., 2016), is the workhorse for training supervised machine learning problems that have the generic form (1).”
- A Closer Look at Memorization in Deep Networks (2017, background): “A number of arguments support the idea that SGD-based learning imparts a regularization effect, especially with a small batch size (Wilson & Martinez, 2003) or a small number of epochs (Hardt et al., 2015).”
- Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networks (2015, methodology): “However, after extensive model exploration we identified a family of archi-2 tectures that resulted in stable training across a range of datasets and allowed for training higher resolution and deeper generative models.”
- Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian (2019, background): “Generalization properties of stochastic gradient descent is extensively studied empirically [34, 28, 50, 16, 29, 24, 25].”
- Training Neural Networks with Fixed Sparse Masks (2021, methodology): “In practice, minimizing a large neural network’s training loss using SGD often results in models that generalize well to new data [3, 17, 27], making SGD an invaluable tool.”
- Understanding deep learning requires rethinking generalization (2016, background): “…that more investigation is needed to understand exactly what the properties are inherited by models that were trained using SGD. 1.2 R ELATED WORK Hardt et al. (2016) give an upper bound on the generalization error of a model trained with stochastic gradient descent in terms of the number of…”
- On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima (2016, background): “In [18], the authors show that for pure-SGD (i.”
- Train longer, generalize better: closing the generalization gap in large batch training of neural networks (2017, background): “• In contrast to common practices (Montavon et al., 2012) and theoretical recommendations (Hardt et al., 2016), generalization keeps improving for a long time at the initial high learning rate, even without any observable changes in training or validation errors.”
- Regularizing and Optimizing LSTM Language Models (2017, background): “SGD demonstrably performs well in practice and also possesses several attractive theoretical properties such as linear convergence (Bottou et al., 2016), saddle point avoidance (Panageas & Piliouras, 2016) and better generalization performance (Hardt et al., 2015).”
- Membership Inference Attacks Against Machine Learning Models (2016, methodology): “Similar metrics are used in the literature to measure how overfitted a model is [18].”
- Sharp Minima Can Generalize For Deep Nets (2017, background): “For example, Duchi et al. (2011); Nesterov & Vial (2008); Hardt et al. (2016); Bottou et al. (2016); Go-nen & Shalev-Shwartz (2017) rely on the concept of stochastic approximation or uniform stability (Bousquet & Elisseeff, 2002).”
- Stable and Fair Classification (2019, background): “[40], [49] and [47] showed that the stochastic gradient descent method is stable.”
- Entropy-SGD: biasing gradient descent into wide valleys (2016, background): “All these results suggest that the energy landscape of deep neural networks should be easy to optimize and they more or less hold in practice — it is easy to optimize a prototypical deep network to near-zero loss on the training set (Hardt et al., 2015; Goodfellow & Vinyals, 2015).”
- AdaNet: Adaptive Structural Learning of Artificial Neural Networks (2016, methodology): “The second involves studying the black-box optimization algorithms that are often used for training these networks (e.g. [Hardt et al., 2015, Lian et al., 2015]).”
- Mixed-Privacy Forgetting in Deep Networks (2020, background): “The downside is that gradient descent (GD) is impractical for large-scale deep learning applications compared to SGD, projection based algorithms are not popular in practice, and the commonly used loss functions are not generally Lipschitz.”
- Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks (2019, background): “In [13], a bound is derived on the divergence of training path of models trained with the same random seed (i.”
- Regularisation of neural networks by enforcing Lipschitz continuity (2018, background): “Hardt et al. (2016) provide some theoretical justifications for common practices, such as early stopping.”
- Where is the Information in a Deep Neural Network? (2019, background): “Notice that the norm (cid:107)∇ D w ∗ of the Jacobian ∇ D w ∗ can be interpreted as a measure of the stability of SGD, that is, how much the final solution changes if the dataset is perturbed [10].”