mlsanityData to 7 Oct 2026

An Improved Analysis of Training Over-parameterized Deep Neural Networks

arXiv 1906.04688 ↗First posted 11 Jun 2019cs.LG math.OC stat.MLcited by 120

Not on the map. Why?

Abstract (arXiv)

A recent line of research has shown that gradient-based algorithms with random initialization can converge to the global minima of the training loss for over-parameterized (i.e., sufficiently wide) deep neural networks. However, the condition on the width of the neural network to ensure the global convergence is very stringent, which is often a high-degree polynomial in the training sample size n (e.g., O(n24)). In this paper, we provide an improved analysis of the global convergence of (stochastic) gradient descent for training deep neural networks, which only requires a milder over-parameterization condition than previous work in terms of the training sample size and other problem-dependent parameters. The main technical contributions of our analysis include (a) a tighter gradient lower bound that leads to a faster convergence of the algorithm, and (b) a sharper characterization of the trajectory length of the algorithm. By specializing our result to two-layer (i.e., one-hidden-layer) neural networks, it also provides a milder over-parameterization condition than the best-known result in prior work.

Key facts. Cited by 120 papers in the map (data through 7 Oct 2026). First posted on arXiv 11 Jun 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 30; 2022: 32; 2023: 21; 2024: 23; 2025: 9; 2026: 5.

120 papers.

Sort:

By area:

  1. 2021Do We Actually Need Dense Over-Parameterization? In-Time Over-Parameterization in Sparse Trainingcited by 107
  2. 2023A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexitycited by 77
  3. 2022DisPFL: Towards Communication-Efficient Personalized Federated Learning via Decentralized Sparse Trainingcited by 74
  4. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  5. 2023Revisiting Weighted Aggregation in Federated Learning with Neural Networkscited by 57
  6. 2021What can linearized neural networks actually say about generalization?cited by 49
  7. 2021Understanding the Generalization of Adam in Learning Neural Networks with Proper Regularizationcited by 48
  8. 2021Asymmetric Loss Functions for Learning with Noisy Labelscited by 46
  9. 2021On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widthscited by 44
  10. 2022Memorization and Optimization in Deep Neural Networks with Minimum Over-parameterizationcited by 36
  11. 2024How Do Nonlinear Transformers Learn and Generalize in In-Context Learning?cited by 35
  12. 2021Continuous vs. Discrete Optimization of Deep Neural Networkscited by 34
38 more
  1. 2021Does Preprocessing Help Training Over-parameterized Neural Networks?cited by 32
  2. 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
  3. 2022Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessingcited by 29
  4. 2023Catapults in SGD: spikes in the training loss and their impact on generalization through feature learningcited by 29
  5. 2021Properties of the After Kernelcited by 27
  6. 2021Subquadratic Overparameterization for Shallow Neural Networkscited by 26
  7. 2023How to Protect Copyright Data in Optimization of Large Language Models?cited by 26
  8. 2024Evaluating the design space of diffusion-based generative modelscited by 25
  9. 2022Characterizing the Spectrum of the NTK via a Power Series Expansioncited by 22
  10. 2023Generalization and Stability of Interpolating Neural Networks with Minimal Widthcited by 21
  11. 2024A Survey on Statistical Theory of Deep Learning: Approximation, Training Dynamics, and Generative Modelscited by 20
  12. 2023Six Lectures on Linearized Neural Networkscited by 19
  13. 2022Demystifying the Neural Tangent Kernel from a Practical Perspective: Can it be trusted for Neural Architecture Search without training?cited by 18
  14. 2021Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noisecited by 17
  15. 2021A global convergence theory for deep ReLU implicit networks via over-parameterizationcited by 17
  16. 2022Quadratic models for understanding catapult dynamics of neural networkscited by 17
  17. 2021Learning with Gradient Descent and Weakly Convex Lossescited by 16
  18. 2022Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysiscited by 15
  19. 2022An Analysis of Attention via the Lens of Exchangeability and Latent Variable Modelscited by 15
  20. 2024FedFisher: Leveraging Fisher Information for One-Shot Federated Learningcited by 15
  21. 2021Understanding Overparameterization in Generative Adversarial Networkscited by 14
  22. 2021The Separation Capacity of Random Neural Networkscited by 14
  23. 2021Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networkscited by 14
  24. 2024What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encodingcited by 14
  25. 2024Differential Privacy Mechanisms in Neural Tangent Kernel Regressioncited by 14
  26. 2024Wide Neural Networks Trained with Weight Decay Provably Exhibit Neural Collapsecited by 14
  27. 2023On the Convergence of Encoder-only Shallow Transformerscited by 13
  28. 2024Bounds for the smallest eigenvalue of the NTK for arbitrary spherical data of arbitrary dimensioncited by 13
  29. 2024The Persistence of Neural Collapse Despite Low-Rank Biascited by 12
  30. 2022Spectral Bias Outside the Training Set for Deep Networks in the Kernel Regimecited by 11
  31. 2023Efficient SGD Neural Network Training via Sublinear Activated Neuron Identificationcited by 11
  32. 2024From Activation to Initialization: Scaling Insights for Optimizing Neural Fieldscited by 11
  33. 2021Local SGD Optimizes Overparameterized Neural Networks in Polynomial Timecited by 10
  34. 2022Global Convergence of Over-parameterized Deep Equilibrium Modelscited by 10
  35. 2022Nonlinear Sufficient Dimension Reduction with a Stochastic Neural Networkcited by 10
  36. 2022Implicit Bias of MSE Gradient Optimization in Underparameterized Neural Networkscited by 9
  37. 2022A Kernel-Expanded Stochastic Neural Networkcited by 9
  38. 2023An Automatic Learning Rate Schedule Algorithm for Achieving Faster Convergence and Steeper Descentcited by 9

50 most cited of 120 All 120 (JSON)