mlsanityData to 14 Oct 2026

A Convergence Theory for Deep Learning via Over-Parameterization

arXiv 1811.03962 ↗First posted 9 Nov 2018cs.LG cs.DS cs.NEcited by 787

Not on the map. Why?

Abstract (arXiv)

Deep neural networks (DNNs) have demonstrated dominating performance in many fields; since AlexNet, networks used in practice are going wider and deeper. On the theoretical side, a long line of works has been focusing on training neural networks with one hidden layer. The theory of multi-layer networks remains largely unsettled. In this work, we prove why stochastic gradient descent (SGD) can find textitglobal minima on the training objective of DNNs in textitpolynomial time. We only make two assumptions: the inputs are non-degenerate and the network is over-parameterized. The latter means the network width is sufficiently large: textitpolynomial in L, the number of layers and in n, the number of samples. Our key technique is to derive that, in a sufficiently large neighborhood of the random initialization, the optimization landscape is almost-convex and semi-smooth even with ReLU activations. This implies an equivalence between over-parameterized neural networks and neural tangent kernel (NTK) in the finite (and polynomial) width setting. As concrete examples, starting from randomly initialized weights, we prove that SGD can attain 100% training accuracy in classification tasks, or minimize regression loss in linear convergence speed, with running time polynomial in n,L. Our theory applies to the widely-used but non-smooth ReLU activation, and to any smooth and possibly non-convex loss functions. In terms of network architectures, our theory at least applies to fully-connected neural networks, convolutional neural networks (CNN), and residual neural networks (ResNet).

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 187; 2022: 180; 2023: 156; 2024: 111; 2025: 88; 2026: 65.

787 papers.

Sort:

By area:

  1. 2021LoRA: Low-Rank Adaptation of Large Language Modelscited by 14,380
  2. 2021GPT Understands, Toocited by 716
  3. 2021FedBN: Federated Learning on Non-IID Features via Local Batch Normalizationcited by 571
  4. 2022Mind the Gap: Understanding the Modality Gap in Multi-modal Contrastive Representation Learningcited by 561
  5. 2021Gradient Descent on Neural Networks Typically Occurs at the Edge of Stabilitycited by 427
  6. 2021A Geometric Analysis of Neural Collapse with Unconstrained Featurescited by 227
  7. 2023ReLoRA: High-Rank Training Through Low-Rank Updatescited by 204
  8. 2021AutoFormer: Searching Transformers for Visual Recognitioncited by 188
  9. 2022Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limitcited by 187
  10. 2021The Values Encoded in Machine Learning Researchcited by 172
  11. 2021Exploring Deep Neural Networks via Layer-Peeled Model: Minority Collapse in Imbalanced Trainingcited by 166
  12. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
38 more
  1. 2021Dash: Semi-Supervised Learning with Dynamic Thresholdingcited by 148
  2. 2022Signal Propagation in Transformers: Theoretical Perspectives and the Role of Rank Collapsecited by 141
  3. 2023Domain Specialization as the Key to Make Large Language Models Disruptive: A Comprehensive Surveycited by 135
  4. 2021On the Convergence and Robustness of Adversarial Trainingcited by 130
  5. 2022Understanding Gradient Descent on Edge of Stability in Deep Learningcited by 128
  6. 2022A Kernel-Based View of Language Model Fine-Tuningcited by 121
  7. 2021Toward Understanding the Feature Learning Process of Self-supervised Contrastive Learningcited by 119
  8. 2021Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentrationcited by 110
  9. 2021Do We Actually Need Dense Over-Parameterization? In-Time Over-Parameterization in Sparse Trainingcited by 110
  10. 2024Physics of Language Models: Part 2.1, Grade-School Math and the Hidden Reasoning Processcited by 108
  11. 2021What Happens after SGD Reaches Zero Loss? --A Mathematical Frameworkcited by 107
  12. 2022Self-Consistent Dynamical Field Theory of Kernel Evolution in Wide Neural Networkscited by 105
  13. 2023Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformercited by 102
  14. 2021Theory of overparametrization in quantum neural networkscited by 100
  15. 2022The Slingshot Mechanism: An Empirical Study of Adaptive Optimizers and the Grokking Phenomenoncited by 94
  16. 2022Benign Overfitting in Two-layer Convolutional Neural Networkscited by 91
  17. 2022q-Learning in Continuous Timecited by 91
  18. 2021Improved architectures and training algorithms for deep operator networkscited by 86
  19. 2022Understanding the Generalization Benefit of Normalization Layers: Sharpness Reductioncited by 86
  20. 2022The Unreasonable Effectiveness of Random Pruning: Return of the Most Naive Baseline for Sparse Trainingcited by 85
  21. 2021Information-Theoretic Generalization Bounds for Stochastic Gradient Descentcited by 84
  22. 2021Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Biascited by 83
  23. 2023Physics of Language Models: Part 1, Learning Hierarchical Language Structurescited by 83
  24. 2023Dichotomy of Early and Late Phase Implicit Biases Can Provably Induce Grokkingcited by 80
  25. 2022Personalized Prompt Learning for Explainable Recommendationcited by 79
  26. 2023A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexitycited by 77
  27. 2021Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Modelscited by 76
  28. 2023A Mathematical Guide to Operator Learningcited by 76
  29. 2022Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Datacited by 74
  30. 2022DisPFL: Towards Communication-Efficient Personalized Federated Learning via Decentralized Sparse Trainingcited by 74
  31. 2023Transformers as Support Vector Machinescited by 74
  32. 2021On the Validity of Modeling SGD with Stochastic Differential Equations (SDEs)cited by 73
  33. 2021Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeedcited by 69
  34. 2022In Defense of the Unitary Scalarization for Deep Multi-Task Learningcited by 67
  35. 2021Improved OOD Generalization via Adversarial Training and Pre-trainingcited by 66
  36. 2023Residual Prompt Tuning: Improving Prompt Tuning with Residual Reparameterizationcited by 64
  37. 2022Neural Networks Efficiently Learn Low-Dimensional Representations with SGDcited by 63
  38. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62

50 most cited of 787 All 787 (JSON)