# An Improved Analysis of Training Over-parameterized Deep Neural Networks

arXiv: https://arxiv.org/abs/1906.04688 · HTML: https://mlsanity.com/paper/1906.04688/

## Key facts

- Cited by 121 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2019.

## Built on by (most cited first, 30 of 121)

- [Do We Actually Need Dense Over-Parameterization? In-Time Over-Parameterization in Sparse Training](https://mlsanity.com/paper/2102.02887/) (2021)
- [A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexity](https://mlsanity.com/paper/2302.06015/) (2023)
- [DisPFL: Towards Communication-Efficient Personalized Federated Learning via Decentralized Sparse Training](https://mlsanity.com/paper/2206.00187/) (2022)
- [Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time](https://mlsanity.com/paper/2112.07628/) (2021)
- [Revisiting Weighted Aggregation in Federated Learning with Neural Networks](https://mlsanity.com/paper/2302.10911/) (2023)
- [What can linearized neural networks actually say about generalization?](https://mlsanity.com/paper/2106.06770/) (2021)
- [Understanding the Generalization of Adam in Learning Neural Networks with Proper Regularization](https://mlsanity.com/paper/2108.11371/) (2021)
- [Asymmetric Loss Functions for Learning with Noisy Labels](https://mlsanity.com/paper/2106.03110/) (2021)
- [On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths](https://mlsanity.com/paper/2101.09612/) (2021)
- [Memorization and Optimization in Deep Neural Networks with Minimum Over-parameterization](https://mlsanity.com/paper/2205.10217/) (2022)
- [How Do Nonlinear Transformers Learn and Generalize in In-Context Learning?](https://mlsanity.com/paper/2402.15607/) (2024)
- [Continuous vs. Discrete Optimization of Deep Neural Networks](https://mlsanity.com/paper/2107.06608/) (2021)
- [Does Preprocessing Help Training Over-parameterized Neural Networks?](https://mlsanity.com/paper/2110.04622/) (2021)
- [Catapults in SGD: spikes in the training loss and their impact on generalization through feature learning](https://mlsanity.com/paper/2306.04815/) (2023)
- [A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time](https://mlsanity.com/paper/2309.07418/) (2023)
- [Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing](https://mlsanity.com/paper/2211.14227/) (2022)
- [Properties of the After Kernel](https://mlsanity.com/paper/2105.10585/) (2021)
- [Subquadratic Overparameterization for Shallow Neural Networks](https://mlsanity.com/paper/2111.01875/) (2021)
- [How to Protect Copyright Data in Optimization of Large Language Models?](https://mlsanity.com/paper/2308.12247/) (2023)
- [Evaluating the design space of diffusion-based generative models](https://mlsanity.com/paper/2406.12839/) (2024)
- [Characterizing the Spectrum of the NTK via a Power Series Expansion](https://mlsanity.com/paper/2211.07844/) (2022)
- [Generalization and Stability of Interpolating Neural Networks with Minimal Width](https://mlsanity.com/paper/2302.09235/) (2023)
- [Six Lectures on Linearized Neural Networks](https://mlsanity.com/paper/2308.13431/) (2023)
- [A Survey on Statistical Theory of Deep Learning: Approximation, Training Dynamics, and Generative Models](https://mlsanity.com/paper/2401.07187/) (2024)
- [Demystifying the Neural Tangent Kernel from a Practical Perspective: Can it be trusted for Neural Architecture Search without training?](https://mlsanity.com/paper/2203.14577/) (2022)
- [Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noise](https://mlsanity.com/paper/2101.01152/) (2021)
- [A global convergence theory for deep ReLU implicit networks via over-parameterization](https://mlsanity.com/paper/2110.05645/) (2021)
- [Quadratic models for understanding catapult dynamics of neural networks](https://mlsanity.com/paper/2205.11787/) (2022)
- [Learning with Gradient Descent and Weakly Convex Losses](https://mlsanity.com/paper/2101.04968/) (2021)
- [An Analysis of Attention via the Lens of Exchangeability and Latent Variable Models](https://mlsanity.com/paper/2212.14852/) (2022)

## 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.