SGD on Neural Networks Learns Functions of Increasing Complexity

By Preetum Nakkiran, Gal Kaplun, Dimitris Kalimeris, Tristan Yang, Benjamin L. Edelman, Fred Zhang, Boaz Barak. 2019

301 citations recorded by the source corpus.

We perform an experimental study of the dynamics of Stochastic Gradient Descent (SGD) in learning deep neural networks for several real and synthetic classification tasks. We show that in the initial epochs, almost all of the performance improvement of the classifier obtained by SGD can be explained by a linear classifier. More generally, we give evidence for the hypothesis that, as iterations progress, SGD learns functions of increasing complexity. This hypothesis can be helpful in explaining why SGD-learned classifiers tend to generalize well even in the over-parameterized regime. We also show that the linear classifier learned in the initial stages is "retained" throughout the execution even if training is continued to the point of zero training error, and complement this with a theoretical result in a simplified model. Key to our work is a new measure of how well one classifier explains the performance of another, based on conditional mutual information.

Subfields: Artificial Intelligence, Control and Systems Engineering, Statistical 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

In Control and Systems Engineering

In Statistical Learning Theory

Citations in the corpus

Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks (2019, background): “Mangalam and Prabhu [30] and Nakkiran et al. [31] experimentally demonstrate that deep networks may ﬁrst ﬁt examples learnable by “simpler” classiﬁers.”
What Makes Training Multi-Modal Classification Networks Hard? (2019, background): “We believe that, in general, patterns learned by neural network are different at different stage of training (e.g. [36]), thus the overﬁtting / generalization behavior also changes during training; this leads to different weights at different stages of the training.”
Understanding and Improving Fast Adversarial Training (2020, background): “[26] Preetum Nakkiran, Gal Kaplun, Dimitris Kalimeris, Tristan Yang, Benjamin L.”
The Pitfalls of Simplicity Bias in Neural Networks (2020, background): “Empirical findings [49, 43] provide further evidence to suggest that SGD-trained NNs generalize well because SGD learns models of increasing complexity.”
Mechanistic Interpretability for AI Safety - A Review (2024, background): “Characterizing these algorithms helps test hypotheses around generalizable mechanisms like variable binding (Feng & Steinhardt, 2023; Davies et al., 2023) and arithmetic reasoning (Stolfo et al., 2023).”
Gradient Starvation: A Learning Proclivity in Neural Networks (2020, background): “The same phenomenon is referred to as implicit bias, implicit regularization, simplicity bias and spectral bias in several works [83, 75, 36, 74, 70, 53, 94, 10, 13, 35, 82, 66].”
Deep Learning Through the Lens of Example Difficulty (2021, background): “Deep models learn easy data (Jiang et al., 2021; Toneva et al., 2019) and simple functions first (Hu et al., 2020; Kalimeris et al., 2019).”
Implicit Regularization in Deep Learning May Not Be Explainable by Norms (2020, background): “[41] Dimitris Kalimeris, Gal Kaplun, Preetum Nakkiran, Benjamin Edelman, Tristan Yang, Boaz Barak, and Haofeng Zhang.”
Model complexity of deep learning: a survey (2021, background): “For example, a measure metric of the effective model complexity of neural networks helps to monitor the changes of a model during the optimization process and understand how the optimization process progresses [44,47,74,89].”