mlsanityData to 14 Oct 2026

Gradient Descent Provably Optimizes Over-parameterized Neural Networks

arXiv 1810.02054 ↗First posted 4 Oct 2018cs.LG math.OC stat.MLcited by 659

Not on the map. Why?

Abstract (arXiv)

One of the mysteries in the success of neural networks is randomly initialized first order methods like gradient descent can achieve zero training loss even though the objective function is non-convex and non-smooth. This paper demystifies this surprising phenomenon for two-layer fully connected ReLU activated neural networks. For an m hidden node shallow neural network with ReLU activation and n training data, we show as long as m is large enough and no two inputs are parallel, randomly initialized gradient descent converges to a globally optimal solution at a linear convergence rate for the quadratic loss function. Our analysis relies on the following observation: over-parameterization and random initialization jointly restrict every weight vector to be close to its initialization for all iterations, which allows us to exploit a strong convexity-like property to show that gradient descent converges at a global linear rate to the global optimum. We believe these insights are also useful in analyzing deep models and other first order methods.

Key facts. Cited by 659 papers in the map (data through 14 Oct 2026). First posted on arXiv 4 Oct 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2020: 1; 2021: 163; 2022: 146; 2023: 142; 2024: 80; 2025: 82; 2026: 45.

659 papers.

Sort:

By area:

  1. 2021FedBN: Federated Learning on Non-IID Features via Local Batch Normalizationcited by 571
  2. 2021AutoFormer: Searching Transformers for Visual Recognitioncited by 188
  3. 2022Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limitcited by 187
  4. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  5. 2021The Low-Rank Simplicity Bias in Deep Networkscited by 154
  6. 2022High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representationcited by 150
  7. 2021Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolationcited by 132
  8. 2021Geometry of the Loss Landscape in Overparameterized Neural Networks: Symmetries and Invariancescited by 127
  9. 2022Modality Competition: What Makes Joint Training of Multi-modal Network Fail in Deep Learning? (Provably)cited by 122
  10. 2022A Kernel-Based View of Language Model Fine-Tuningcited by 121
  11. 2023SAM-CLIP: Merging Vision Foundation Models towards Semantic and Spatial Understandingcited by 111
  12. 2021Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentrationcited by 110
38 more
  1. 2021What Happens after SGD Reaches Zero Loss? --A Mathematical Frameworkcited by 107
  2. 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 102
  3. 2023Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformercited by 102
  4. 2021Theory of overparametrization in quantum neural networkscited by 100
  5. 2022Neural Collapse: A Review on Modelling Principles and Generalizationcited by 95
  6. 2022Benign Overfitting in Two-layer Convolutional Neural Networkscited by 91
  7. 2021Learning with invariances in random features and kernel modelscited by 89
  8. 2021Saddle-to-Saddle Dynamics in Deep Linear Networks: Small Initialization Training, Symmetry, and Sparsitycited by 85
  9. 2021Information-Theoretic Generalization Bounds for Stochastic Gradient Descentcited by 84
  10. 2023DiffFit: Unlocking Transferability of Large Diffusion Models via Simple Parameter-Efficient Fine-Tuningcited by 84
  11. 2021Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Biascited by 83
  12. 2023Dichotomy of Early and Late Phase Implicit Biases Can Provably Induce Grokkingcited by 80
  13. 2023A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexitycited by 77
  14. 2021Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Modelscited by 76
  15. 2022Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Datacited by 74
  16. 2023Transformers as Support Vector Machinescited by 74
  17. 2021On the Validity of Modeling SGD with Stochastic Differential Equations (SDEs)cited by 73
  18. 2021On the Implicit Bias of Initialization Shape: Beyond Infinitesimal Mirror Descentcited by 70
  19. 2021Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeedcited by 69
  20. 2022Domain-Adjusted Regression or: ERM May Already Learn Features Sufficient for Out-of-Distribution Generalizationcited by 69
  21. 2022Analyzing Sharpness along GD Trajectory: Progressive Sharpening and Edge of Stabilitycited by 63
  22. 2022Neural Networks Efficiently Learn Low-Dimensional Representations with SGDcited by 63
  23. 2021Lost in Pruning: The Effects of Pruning Neural Networks beyond Test Accuracycited by 62
  24. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  25. 2022Theory of Graph Neural Networks: Representation and Learningcited by 61
  26. 2023ZiCo: Zero-shot NAS via Inverse Coefficient of Variation on Gradientscited by 58
  27. 2021Tensor Programs IIb: Architectural Universality of Neural Tangent Kernel Training Dynamicscited by 57
  28. 2021Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depthcited by 55
  29. 2022Towards Understanding Mixture of Experts in Deep Learningcited by 52
  30. 2022Theoretical Guarantees for Permutation-Equivariant Quantum Neural Networkscited by 52
  31. 2023JoMA: Demystifying Multilayer Transformers via JOint Dynamics of MLP and Attentioncited by 52
  32. 2022Learning threshold neurons via the "edge of stability"cited by 51
  33. 2022Mechanistic Mode Connectivitycited by 50
  34. 2021Deep Kronecker neural networks: A general framework for neural networks with adaptive activation functionscited by 49
  35. 2021Understanding the Generalization of Adam in Learning Neural Networks with Proper Regularizationcited by 49
  36. 2023A Theory of Non-Linear Feature Learning with One Gradient Step in Two-Layer Neural Networkscited by 49
  37. 2024From Lazy to Rich: Exact Learning Dynamics in Deep Linear Networkscited by 49
  38. 2021A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Networkcited by 47

50 most cited of 659 All 659 (JSON)