# Gradient Descent Finds Global Minima for Generalizable Deep Neural Networks of Practical Sizes

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Aug 2019.

## Built on by (most cited first, 29 of 29)

- [Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth](https://mlsanity.com/paper/2105.04550/) (2021)
- [Meta-learning PINN loss functions](https://mlsanity.com/paper/2107.05544/) (2021)
- [On the Theory of Implicit Deep Learning: Global Convergence with Implicit Layers](https://mlsanity.com/paper/2102.07346/) (2021)
- [Subquadratic Overparameterization for Shallow Neural Networks](https://mlsanity.com/paper/2111.01875/) (2021)
- [Robustness Implies Generalization via Data-Dependent Generalization Bounds](https://mlsanity.com/paper/2206.13497/) (2022)
- [Six Lectures on Linearized Neural Networks](https://mlsanity.com/paper/2308.13431/) (2023)
- [Overcoming the Spectral Bias of Neural Value Approximation](https://mlsanity.com/paper/2206.04672/) (2022)
- [Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysis](https://mlsanity.com/paper/2206.12802/) (2022)
- [Efficient Neural Networks for Tiny Machine Learning: A Comprehensive Review](https://mlsanity.com/paper/2311.11883/) (2023)
- [A Recipe for Global Convergence Guarantee in Deep Neural Networks](https://mlsanity.com/paper/2104.05785/) (2021)
- [Approximation results for Gradient Descent trained Shallow Neural Networks in 1d](https://mlsanity.com/paper/2209.08399/) (2022)
- [On the Double Descent of Random Features Models Trained with SGD](https://mlsanity.com/paper/2110.06910/) (2021)
- [Global Convergence of SGD On Two Layer Neural Nets](https://mlsanity.com/paper/2210.11452/) (2022)
- [A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks](https://mlsanity.com/paper/2101.04243/) (2021)
- [Learning distinct features helps, provably](https://mlsanity.com/paper/2106.06012/) (2021)
- [Learning Proximal Operators to Discover Multiple Optima](https://mlsanity.com/paper/2201.11945/) (2022)
- [Analysis of the expected L2 error of an over-parametrized deep neural network estimate learned by gradient descent without regularization](https://mlsanity.com/paper/2311.14609/) (2023)
- [Approximation Results for Gradient Descent trained Neural Networks](https://mlsanity.com/paper/2309.04860/) (2023)
- [Improved Overparametrization Bounds for Global Convergence of Stochastic Gradient Descent for Shallow Neural Networks](https://mlsanity.com/paper/2201.12052/) (2022)
- [Parameter Convex Neural Networks](https://mlsanity.com/paper/2206.05562/) (2022)
- [Approximation and Gradient Descent Training with Neural Networks](https://mlsanity.com/paper/2405.11696/) (2024)
- [From Sublinear to Linear: Local Convergence in Finite-Width Networks via Locally Polyak-Lojasiewicz Regions](https://mlsanity.com/paper/2507.21429/) (2025)
- [On damage of interpolation to adversarial robustness in regression](https://mlsanity.com/paper/2601.16070/) (2026)
- [Complexity from Adaptive-Symmetries Breaking: Global Minima in the Statistical Mechanics of Deep Neural Networks](https://mlsanity.com/paper/2201.07934/) (2022)
- [Demystifying the Global Convergence Puzzle of Learning Over-parameterized ReLU Nets in Very High Dimensions](https://mlsanity.com/paper/2206.03254/) (2022)
- [Analysis of the rate of convergence of an over-parametrized convolutional neural network image classifier learned by gradient descent](https://mlsanity.com/paper/2405.07619/) (2024)
- [Statistically guided deep learning](https://mlsanity.com/paper/2504.08489/) (2025)
- [Distributionally Robust Wireless Semantic Communication with Large AI Models](https://mlsanity.com/paper/2506.03167/) (2025)
- [Upper Bounds on the Generalization Error of Deep Learning Models via Local Robustness and Stability](https://mlsanity.com/paper/2606.16883/) (2026)

## Abstract (arXiv)

In this paper, we theoretically prove that gradient descent can find a global minimum of non-convex optimization of all layers for nonlinear deep neural networks of sizes commonly encountered in practice. The theory developed in this paper only requires the practical degrees of over-parameterization unlike previous theories. Our theory only requires the number of trainable parameters to increase linearly as the number of training samples increases. This allows the size of the deep neural networks to be consistent with practice and to be several orders of magnitude smaller than that required by the previous theories. Moreover, we prove that the linear increase of the size of the network is the optimal rate and that it cannot be improved, except by a logarithmic factor. Furthermore, deep neural networks with the trainability guarantee are shown to generalize well to unseen test samples with a natural dataset but not a random dataset.