# Gradient Descent Finds Global Minima of Deep Neural Networks

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

## Key facts

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

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

- [Understanding self-supervised Learning Dynamics without Contrastive Pairs](https://mlsanity.com/paper/2102.06810/) (2021)
- [U-NO: U-shaped Neural Operators](https://mlsanity.com/paper/2204.11127/) (2022)
- [A Geometric Analysis of Neural Collapse with Unconstrained Features](https://mlsanity.com/paper/2105.02375/) (2021)
- [The Values Encoded in Machine Learning Research](https://mlsanity.com/paper/2106.15590/) (2021)
- [Exploring Deep Neural Networks via Layer-Peeled Model: Minority Collapse in Imbalanced Training](https://mlsanity.com/paper/2101.12699/) (2021)
- [Neural Networks can Learn Representations with Gradient Descent](https://mlsanity.com/paper/2206.15144/) (2022)
- [The Low-Rank Simplicity Bias in Deep Networks](https://mlsanity.com/paper/2103.10427/) (2021)
- [Dash: Semi-Supervised Learning with Dynamic Thresholding](https://mlsanity.com/paper/2109.00650/) (2021)
- [Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation](https://mlsanity.com/paper/2105.14368/) (2021)
- [On the Convergence and Robustness of Adversarial Training](https://mlsanity.com/paper/2112.08304/) (2021)
- [Geometry of the Loss Landscape in Overparameterized Neural Networks: Symmetries and Invariances](https://mlsanity.com/paper/2105.12221/) (2021)
- [Label Noise SGD Provably Prefers Flat Global Minimizers](https://mlsanity.com/paper/2106.06530/) (2021)
- [A Kernel-Based View of Language Model Fine-Tuning](https://mlsanity.com/paper/2210.05643/) (2022)
- [Toward Understanding the Feature Learning Process of Self-supervised Contrastive Learning](https://mlsanity.com/paper/2105.15134/) (2021)
- [Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration](https://mlsanity.com/paper/2101.10588/) (2021)
- [Do We Actually Need Dense Over-Parameterization? In-Time Over-Parameterization in Sparse Training](https://mlsanity.com/paper/2102.02887/) (2021)
- [What Happens after SGD Reaches Zero Loss? --A Mathematical Framework](https://mlsanity.com/paper/2110.06914/) (2021)
- [Self-Consistent Dynamical Field Theory of Kernel Evolution in Wide Neural Networks](https://mlsanity.com/paper/2205.09653/) (2022)
- [Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformer](https://mlsanity.com/paper/2305.16380/) (2023)
- [Theory of overparametrization in quantum neural networks](https://mlsanity.com/paper/2109.11676/) (2021)
- [Benign Overfitting in Two-layer Convolutional Neural Networks](https://mlsanity.com/paper/2202.06526/) (2022)
- [Learning with invariances in random features and kernel models](https://mlsanity.com/paper/2102.13219/) (2021)
- [Improved architectures and training algorithms for deep operator networks](https://mlsanity.com/paper/2110.01654/) (2021)
- [Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Bias](https://mlsanity.com/paper/2110.13905/) (2021)
- [Dichotomy of Early and Late Phase Implicit Biases Can Provably Induce Grokking](https://mlsanity.com/paper/2311.18817/) (2023)
- [Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction](https://mlsanity.com/paper/2106.15013/) (2021)
- [A Mathematical Guide to Operator Learning](https://mlsanity.com/paper/2312.14688/) (2023)
- [Universality of empirical risk minimization](https://mlsanity.com/paper/2202.08832/) (2022)
- [Policy Gradient Method For Robust Reinforcement Learning](https://mlsanity.com/paper/2205.07344/) (2022)
- [Improved OOD Generalization via Adversarial Training and Pre-training](https://mlsanity.com/paper/2105.11144/) (2021)

## Abstract (arXiv)

Gradient descent finds a global minimum in training deep neural networks despite the objective function being non-convex. The current paper proves gradient descent achieves zero training loss in polynomial time for a deep over-parameterized neural network with residual connections (ResNet). Our analysis relies on the particular structure of the Gram matrix induced by the neural network architecture. This structure allows us to show the Gram matrix is stable throughout the training process and this stability implies the global optimality of the gradient descent algorithm. We further extend our analysis to deep residual convolutional neural networks and obtain a similar convergence result.