mlsanityData to 7 Oct 2026

SGD on Neural Networks Learns Functions of Increasing Complexity

arXiv 1905.11604 ↗First posted 28 May 2019cs.LG cs.NE stat.MLcited by 203

Not on the map. Why?

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.

Key facts. Cited by 203 papers in the map (data through 7 Oct 2026). First posted on arXiv 28 May 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 36; 2022: 34; 2023: 37; 2024: 37; 2025: 27; 2026: 32.

203 papers.

Sort:

By area:

  1. 2024Mechanistic Interpretability for AI Safety -- A Reviewcited by 415
  2. 2021Fishr: Invariant Gradient Variances for Out-of-Distribution Generalizationcited by 186
  3. 2021The Low-Rank Simplicity Bias in Deep Networkscited by 150
  4. 2021Deep Learning Through the Lens of Example Difficultycited by 139
  5. 2023Sudden Drops in the Loss: Syntax Acquisition, Phase Transitions, and Simplicity Bias in MLMscited by 121
  6. 2021Assessing Generalization of SGD via Disagreementcited by 116
  7. 2024The Evolution of Statistical Induction Heads: In-Context Learning Markov Chainscited by 115
  8. 2023Task-Specific Skill Localization in Fine-tuned Language Modelscited by 104
  9. 2022Robust Training under Label Noise by Over-parameterizationcited by 93
  10. 2021Evading the Simplicity Bias: Training a Diverse Set of Models Discovers Solutions with Superior OOD Generalizationcited by 83
  11. 2021Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Biascited by 82
  12. 2022Gradient flow dynamics of shallow ReLU networks for square loss and orthogonal inputscited by 74
38 more
  1. 2022Overview frequency principle/spectral bias in deep learningcited by 68
  2. 2022Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functionscited by 68
  3. 2023How Two-Layer Neural Networks Learn, One (Giant) Step at a Timecited by 67
  4. 2022MaskTune: Mitigating Spurious Correlations by Forcing to Explorecited by 66
  5. 2021Model Complexity of Deep Learning: A Surveycited by 64
  6. 2021The staircase property: How hierarchical structure can guide deep learningcited by 62
  7. 2023Learning time-scales in two-layers neural networkscited by 57
  8. 2022Linear Connectivity Reveals Generalization Strategiescited by 55
  9. 2023Saddle-to-Saddle Dynamics in Diagonal Linear Networkscited by 54
  10. 2021Do Input Gradients Highlight Discriminative Features?cited by 52
  11. 2022Mechanistic Mode Connectivitycited by 50
  12. 2022Neural networks trained with SGD learn distributions of increasing complexitycited by 50
  13. 2022Investigating Why Contrastive Learning Benefits Robustness Against Label Noisecited by 46
  14. 2024Adaptive Data Optimization: Dynamic Sample Selection with Scaling Lawscited by 46
  15. 2023Identifying Spurious Biases Early in Training through the Lens of Simplicity Biascited by 44
  16. 2021Why Machine Reading Comprehension Models Learn Shortcuts?cited by 40
  17. 2023Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensingcited by 40
  18. 2021Strength of Minibatch Noise in SGDcited by 39
  19. 2022Fortuitous Forgetting in Connectionist Networkscited by 39
  20. 2021Embedding Principle of Loss Landscape of Deep Neural Networkscited by 36
  21. 2021Spectral Bias in Practice: The Role of Function Frequency in Generalizationcited by 36
  22. 2021Trivial or impossible -- dichotomous data difficulty masks model differences (on ImageNet and beyond)cited by 35
  23. 2021A Little Robustness Goes a Long Way: Leveraging Robust Features for Targeted Transfer Attackscited by 33
  24. 2021Towards Understanding the Condensation of Neural Networks at Initial Trainingcited by 31
  25. 2023Which Features are Learnt by Contrastive Learning? On the Role of Simplicity Bias in Class Collapse and Feature Suppressioncited by 30
  26. 2022Data-driven emergence of convolutional structure in neural networkscited by 29
  27. 2023Deep neural networks have an inbuilt Occam's razorcited by 28
  28. 2022Mitigating and Evaluating Static Bias of Action Representations in the Background and the Foregroundcited by 26
  29. 2023Simplicity Bias in 1-Hidden Layer Neural Networkscited by 26
  30. 2022On the Generalization Mystery in Deep Learningcited by 25
  31. 2021Multi-scale Feature Learning Dynamics: Insights for Double Descentcited by 24
  32. 2022How Robust is Unsupervised Representation Learning to Distribution Shift?cited by 24
  33. 2022An Empirical Study of Implicit Regularization in Deep Offline RLcited by 24
  34. 2022Mechanism of feature learning in deep fully connected networks and kernel machines that recursively learn featurescited by 24
  35. 2024A distributional simplicity bias in the learning dynamics of transformerscited by 23
  36. 2024Learned feature representations are biased by complexity, learning order, position, and morecited by 22
  37. 2025Mitigating Plasticity Loss in Continual Reinforcement Learning by Reducing Churncited by 22
  38. 2021The Three Stages of Learning Dynamics in High-Dimensional Kernel Methodscited by 21

50 most cited of 203 All 203 (JSON)