mlsanityData to 14 Oct 2026

Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Bias

arXiv 2110.13905 ↗First posted 26 Oct 2021cs.LGcited by 83

Not on the map. Why?

Abstract (arXiv)

The generalization mystery of overparametrized deep nets has motivated efforts to understand how gradient descent (GD) converges to low-loss solutions that generalize well. Real-life neural networks are initialized from small random values and trained with cross-entropy loss for classification (unlike the "lazy" or "NTK" regime of training where analysis was more successful), and a recent sequence of results (Lyu and Li, 2020; Chizat and Bach, 2020; Ji and Telgarsky, 2020) provide theoretical evidence that GD may converge to the "max-margin" solution with zero loss, which presumably generalizes well. However, the global optimality of margin is proved only in some settings where neural nets are infinitely or exponentially wide. The current paper is able to establish this global optimality for two-layer Leaky ReLU nets trained with gradient flow on linearly separable and symmetric data, regardless of the width. The analysis also gives some theoretical justification for recent empirical findings (Kalimeris et al., 2019) on the so-called simplicity bias of GD towards linear or other "simple" classes of solutions, especially early in training. On the pessimistic side, the paper suggests that such results are fragile. A simple data manipulation can make gradient flow converge to a linear classifier with suboptimal margin.

Key facts. Cited by 83 papers in the map (data through 14 Oct 2026). Builds on 45 of its 56 references that are in the map. First posted on arXiv 26 Oct 2021.

Builds on

45 of 56 references.

References · 45

  1. 2015Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classificationcited by 3,611
  2. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  3. 2016Understanding deep learning requires rethinking generalizationcited by 1,674
  4. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  5. 2017Spectrally-normalized margin bounds for neural networkscited by 686
  6. 2018On Lazy Training in Differentiable Programmingcited by 675
  7. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
  8. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 655
  9. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 574
  10. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 566
  11. 2019Fantastic Generalization Measures and Where to Find Themcited by 513
  12. 2019Implicit Regularization in Deep Matrix Factorizationcited by 405
33 more
  1. 2020The Pitfalls of Simplicity Bias in Neural Networkscited by 351
  2. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  3. 2019Gradient Descent Maximizes the Margin of Homogeneous Neural Networkscited by 320
  4. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 314
  5. 2020Kernel and Rich Regimes in Overparametrized Modelscited by 306
  6. 2020Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Losscited by 268
  7. 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 266
  8. 2018Implicit Bias of Gradient Descent on Linear Convolutional Networkscited by 251
  9. 2019SGD on Neural Networks Learns Functions of Increasing Complexitycited by 204
  10. 2018Gradient descent aligns the layers of deep linear networkscited by 182
  11. 2020Directional convergence and alignment in deep learningcited by 178
  12. 2018Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balancedcited by 177
  13. 2020Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learningcited by 150
  14. 2018Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networkscited by 141
  15. 2018Stochastic subgradient method converges on tame functionscited by 124
  16. 2019Implicit Regularization of Discrete Gradient Dynamics in Linear Neural Networkscited by 124
  17. 2019Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networkscited by 121
  18. 2018Convergence of Gradient Descent on Separable Datacited by 110
  19. 2018Risk and parameter convergence of logistic regressioncited by 85
  20. 2019How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?cited by 84
  21. 2017SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Datacited by 79
  22. 2020Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracycited by 71
  23. 2020Phase diagram for two-layer ReLU neural networks at infinite-width limitcited by 67
  24. 2018Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Ratecited by 64
  25. 2019The Implicit Bias of Depth: How Incremental Learning Drives Generalizationcited by 64
  26. 2018Gradient Descent Quantizes ReLU Network Featurescited by 61
  27. 2020The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networkscited by 58
  28. 2019Gradient Dynamics of Shallow Univariate ReLU Networkscited by 46
  29. 2021Implicit Regularization in Tensor Factorizationcited by 44
  30. 2021Towards Understanding Learning in Neural Networks with Linear Teacherscited by 19
  31. 2020Extreme Memorization via Scale of Initializationcited by 18
  32. 2021Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noisecited by 17
  33. 2020An analytic theory of shallow networks dynamics for hinge loss classificationcited by 14

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 17; 2023: 20; 2024: 19; 2025: 17; 2026: 10.

83 papers.

Sort:

By area:

  1. 2022Understanding Gradient Descent on Edge of Stability in Deep Learningcited by 128
  2. 2022Understanding the Generalization Benefit of Normalization Layers: Sharpness Reductioncited by 86
  3. 2022On the Implicit Bias in Deep-Learning Algorithmscited by 86
  4. 2022Same Pre-training Loss, Better Downstream: Implicit Bias Matters for Language Modelscited by 84
  5. 2022Gradient flow dynamics of shallow ReLU networks for square loss and orthogonal inputscited by 76
  6. 2024Implicit Bias of AdamW: ℓ_∞ Norm Constrained Optimizationcited by 58
  7. 2022Implicit Regularization Towards Rank Minimization in ReLU Networkscited by 53
  8. 2022Implicit Bias in Leaky ReLU Networks Trained on High-Dimensional Datacited by 46
  9. 2024Neural Redshift: Random Networks are not Random Functionscited by 43
  10. 2023Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensingcited by 42
  11. 2024Get rich quick: exact solutions reveal how unbalanced initializations promote rapid feature learningcited by 42
  12. 2022Implicit Bias of Gradient Descent on Reparametrized Models: On Equivalence to Mirror Descentcited by 39
38 more
  1. 2023SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problemcited by 39
  2. 2022Random Feature Amplification: Feature Learning and Generalization in Neural Networkscited by 35
  3. 2023Feature emergence via margin maximization: case studies in algebraic taskscited by 33
  4. 2023Which Features are Learnt by Contrastive Learning? On the Role of Simplicity Bias in Class Collapse and Feature Suppressioncited by 30
  5. 2023Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximizationcited by 29
  6. 2023Early Neuron Alignment in Two-layer ReLU Networks with Small Initializationcited by 28
  7. 2022Implicit Regularization in Hierarchical Tensor Factorization and Deep Convolutional Neural Networkscited by 27
  8. 2023Simplicity Bias in 1-Hidden Layer Neural Networkscited by 26
  9. 2022The Asymmetric Maximum Margin Bias of Quasi-Homogeneous Neural Networkscited by 25
  10. 2023The Double-Edged Sword of Implicit Bias: Generalization vs. Robustness in ReLU Networkscited by 23
  11. 2022Empirical Phase Diagram for Three-layer Neural Networks with Infinite Widthcited by 17
  12. 2025An overview of condensation phenomenon in deep learningcited by 17
  13. 2023Phase Diagram of Initial Condensation for Two-layer Neural Networkscited by 16
  14. 2023Learning a Neuron by a Shallow ReLU Network: Dynamics and Implicit Bias for Correlated Inputscited by 16
  15. 2025Saddle-to-Saddle Dynamics Explains A Simplicity Bias Across Neural Network Architecturescited by 15
  16. 2022Feature selection with gradient descent on two-layer networks in low-rotation regimescited by 14
  17. 2023Provable Guarantees for Neural Networks via Gradient Feature Learningcited by 14
  18. 2024Transformers Learn Low Sensitivity Functions: Investigations and Implicationscited by 14
  19. 2024Improving Generalization and Convergence by Enhancing Implicit Regularizationcited by 14
  20. 2024Differential Privacy Mechanisms in Neural Tangent Kernel Regressioncited by 14
  21. 2025Alternating Gradient Flows: A Theory of Feature Learning in Two-layer Neural Networkscited by 14
  22. 2025Do We Always Need the Simplicity Bias? Looking for Optimal Inductive Biases in the Wildcited by 13
  23. 2024Directional Convergence Near Small Initializations and Saddles in Two-Homogeneous Neural Networkscited by 11
  24. 2024Simplicity Bias of Two-Layer Networks beyond Linearly Separable Datacited by 11
  25. 2024Simplicity bias and optimization threshold in two-layer ReLU networkscited by 11
  26. 2024The Implicit Bias of Gradient Descent on Separable Multiclass Datacited by 11
  27. 2024Meta-Exploiting Frequency Prior for Cross-Domain Few-Shot Learningcited by 11
  28. 2025Towards Understanding Text Hallucination of Diffusion Models via Local Generation Biascited by 11
  29. 2022Adversarial Reprogramming Revisitedcited by 10
  30. 2025When Do Neural Networks Learn World Models?cited by 8
  31. 2024Early Directional Convergence in Deep Homogeneous Neural Networks for Small Initializationscited by 7
  32. 2022Max-Margin Works while Large Margin Fails: Generalization without Uniform Convergencecited by 6
  33. 2023Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimizationcited by 6
  34. 2024Topological obstruction to the training of shallow ReLU neural networkscited by 6
  35. 2025On Learning Verifiers and Implications to Chain-of-Thought Reasoningcited by 6
  36. 2026Topology and Geometry of the Learning Space of ReLU Networks: Connectivity and Singularitiescited by 6
  37. 2022Early Stage Convergence and Global Convergence of Training Mildly Parameterized Neural Networkscited by 5
  38. 2023Deep ReLU Networks Have Surprisingly Simple Polytopescited by 5

50 most cited of 83 All 83 (JSON)