# SGD on Neural Networks Learns Functions of Increasing Complexity

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

## Key facts

- Cited by 204 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2019.

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

- [Mechanistic Interpretability for AI Safety -- A Review](https://mlsanity.com/paper/2404.14082/) (2024)
- [Fishr: Invariant Gradient Variances for Out-of-Distribution Generalization](https://mlsanity.com/paper/2109.02934/) (2021)
- [The Low-Rank Simplicity Bias in Deep Networks](https://mlsanity.com/paper/2103.10427/) (2021)
- [Deep Learning Through the Lens of Example Difficulty](https://mlsanity.com/paper/2106.09647/) (2021)
- [Sudden Drops in the Loss: Syntax Acquisition, Phase Transitions, and Simplicity Bias in MLMs](https://mlsanity.com/paper/2309.07311/) (2023)
- [The Evolution of Statistical Induction Heads: In-Context Learning Markov Chains](https://mlsanity.com/paper/2402.11004/) (2024)
- [Assessing Generalization of SGD via Disagreement](https://mlsanity.com/paper/2106.13799/) (2021)
- [Task-Specific Skill Localization in Fine-tuned Language Models](https://mlsanity.com/paper/2302.06600/) (2023)
- [Robust Training under Label Noise by Over-parameterization](https://mlsanity.com/paper/2202.14026/) (2022)
- [Evading the Simplicity Bias: Training a Diverse Set of Models Discovers Solutions with Superior OOD Generalization](https://mlsanity.com/paper/2105.05612/) (2021)
- [Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Bias](https://mlsanity.com/paper/2110.13905/) (2021)
- [Gradient flow dynamics of shallow ReLU networks for square loss and orthogonal inputs](https://mlsanity.com/paper/2206.00939/) (2022)
- [Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions](https://mlsanity.com/paper/2211.12316/) (2022)
- [Overview frequency principle/spectral bias in deep learning](https://mlsanity.com/paper/2201.07395/) (2022)
- [How Two-Layer Neural Networks Learn, One (Giant) Step at a Time](https://mlsanity.com/paper/2305.18270/) (2023)
- [MaskTune: Mitigating Spurious Correlations by Forcing to Explore](https://mlsanity.com/paper/2210.00055/) (2022)
- [Model Complexity of Deep Learning: A Survey](https://mlsanity.com/paper/2103.05127/) (2021)
- [The staircase property: How hierarchical structure can guide deep learning](https://mlsanity.com/paper/2108.10573/) (2021)
- [Learning time-scales in two-layers neural networks](https://mlsanity.com/paper/2303.00055/) (2023)
- [Saddle-to-Saddle Dynamics in Diagonal Linear Networks](https://mlsanity.com/paper/2304.00488/) (2023)
- [Linear Connectivity Reveals Generalization Strategies](https://mlsanity.com/paper/2205.12411/) (2022)
- [Do Input Gradients Highlight Discriminative Features?](https://mlsanity.com/paper/2102.12781/) (2021)
- [Mechanistic Mode Connectivity](https://mlsanity.com/paper/2211.08422/) (2022)
- [Neural networks trained with SGD learn distributions of increasing complexity](https://mlsanity.com/paper/2211.11567/) (2022)
- [Adaptive Data Optimization: Dynamic Sample Selection with Scaling Laws](https://mlsanity.com/paper/2410.11820/) (2024)
- [Investigating Why Contrastive Learning Benefits Robustness Against Label Noise](https://mlsanity.com/paper/2201.12498/) (2022)
- [Identifying Spurious Biases Early in Training through the Lens of Simplicity Bias](https://mlsanity.com/paper/2305.18761/) (2023)
- [Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensing](https://mlsanity.com/paper/2301.11500/) (2023)
- [Why Machine Reading Comprehension Models Learn Shortcuts?](https://mlsanity.com/paper/2106.01024/) (2021)
- [Strength of Minibatch Noise in SGD](https://mlsanity.com/paper/2102.05375/) (2021)

## Abstract (arXiv)

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.