# On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths

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

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 25 references that are in the map.
- First posted on arXiv 24 Jan 2021.

## Builds on (most cited first, 21 of 21)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [A Mean Field View of the Landscape of Two-Layers Neural Networks](https://mlsanity.com/paper/1804.06561/) (2018)
- [On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport](https://mlsanity.com/paper/1805.09545/) (2018)
- [Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss](https://mlsanity.com/paper/2002.04486/) (2020)
- [Towards moderate overparameterization: global convergence guarantees for training shallow neural networks](https://mlsanity.com/paper/1902.04674/) (2019)
- [An Improved Analysis of Training Over-parameterized Deep Neural Networks](https://mlsanity.com/paper/1906.04688/) (2019)
- [Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks](https://mlsanity.com/paper/1909.12292/) (2019)
- [Dynamics of Deep Neural Networks and Neural Tangent Hierarchy](https://mlsanity.com/paper/1909.08156/) (2019)
- [Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networks](https://mlsanity.com/paper/2012.11654/) (2020)
- [How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?](https://mlsanity.com/paper/1911.12360/) (2019)
- [SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data](https://mlsanity.com/paper/1710.10174/) (2017)
- [Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topology](https://mlsanity.com/paper/2002.07867/) (2020)
- [Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound](https://mlsanity.com/paper/1906.03593/) (2019)
- [SGD Learns the Conjugate Kernel Class of the Network](https://mlsanity.com/paper/1702.08503/) (2017)
- [Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems](https://mlsanity.com/paper/1905.09870/) (2019)
- [Neural Networks Learning and Memorization with (almost) no Over-Parameterization](https://mlsanity.com/paper/1911.09873/) (2019)

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

- [On the Implicit Bias of Initialization Shape: Beyond Infinitesimal Mirror Descent](https://mlsanity.com/paper/2102.09769/) (2021)
- [On Provable Benefits of Depth in Training Graph Convolutional Networks](https://mlsanity.com/paper/2110.15174/) (2021)
- [Memorization and Optimization in Deep Neural Networks with Minimum Over-parameterization](https://mlsanity.com/paper/2205.10217/) (2022)
- [Spectral Evolution and Invariance in Linear-width Neural Networks](https://mlsanity.com/paper/2211.06506/) (2022)
- [Offline Neural Contextual Bandits: Pessimism, Optimization and Generalization](https://mlsanity.com/paper/2111.13807/) (2021)
- [Approximation bounds for norm constrained neural networks with applications to regression and GANs](https://mlsanity.com/paper/2201.09418/) (2022)
- [Characterizing the Spectrum of the NTK via a Power Series Expansion](https://mlsanity.com/paper/2211.07844/) (2022)
- [Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networks](https://mlsanity.com/paper/2109.09304/) (2021)
- [A global convergence theory for deep ReLU implicit networks via over-parameterization](https://mlsanity.com/paper/2110.05645/) (2021)
- [Generalization Properties of NAS under Activation and Skip Connection Search](https://mlsanity.com/paper/2209.07238/) (2022)
- [Wide Neural Networks as Gaussian Processes: Lessons from Deep Equilibrium Models](https://mlsanity.com/paper/2310.10767/) (2023)
- [On the Convergence of Encoder-only Shallow Transformers](https://mlsanity.com/paper/2311.01575/) (2023)
- [Bounds for the smallest eigenvalue of the NTK for arbitrary spherical data of arbitrary dimension](https://mlsanity.com/paper/2405.14630/) (2024)
- [On the Convergence of Shallow Neural Network Training with Randomly Masked Neurons](https://mlsanity.com/paper/2112.02668/) (2021)
- [Spectral Bias Outside the Training Set for Deep Networks in the Kernel Regime](https://mlsanity.com/paper/2206.02927/) (2022)
- [From Activation to Initialization: Scaling Insights for Optimizing Neural Fields](https://mlsanity.com/paper/2403.19205/) (2024)
- [Local SGD Optimizes Overparameterized Neural Networks in Polynomial Time](https://mlsanity.com/paper/2107.10868/) (2021)
- [Global Convergence of Over-parameterized Deep Equilibrium Models](https://mlsanity.com/paper/2205.13814/) (2022)
- [Sample Complexity of Offline Reinforcement Learning with Deep ReLU Networks](https://mlsanity.com/paper/2103.06671/) (2021)
- [When Expressivity Meets Trainability: Fewer than n Neurons Can Work](https://mlsanity.com/paper/2210.12001/) (2022)
- [Understanding the training of infinitely deep and wide ResNets with Conditional Optimal Transport](https://mlsanity.com/paper/2403.12887/) (2024)
- [Spurious Local Minima Are Common for Deep Neural Networks with Piecewise Linear Activations](https://mlsanity.com/paper/2102.13233/) (2021)
- [Restricted Strong Convexity of Deep Learning Models with Smooth Activations](https://mlsanity.com/paper/2209.15106/) (2022)
- [On skip connections and normalisation layers in deep optimisation](https://mlsanity.com/paper/2210.05371/) (2022)
- [Gradient Descent Optimizes Infinite-Depth ReLU Implicit Networks with Linear Widths](https://mlsanity.com/paper/2205.07463/) (2022)
- [Finite Sample Identification of Wide Shallow Neural Networks with Biases](https://mlsanity.com/paper/2211.04589/) (2022)
- [Learning Lipschitz Functions by GD-trained Shallow Overparameterized ReLU Neural Networks](https://mlsanity.com/paper/2212.13848/) (2022)
- [How much pre-training is enough to discover a good subnetwork?](https://mlsanity.com/paper/2108.00259/) (2021)
- [Global Convergence Rate of Deep Equilibrium Models with General Activations](https://mlsanity.com/paper/2302.05797/) (2023)
- [Convergence Rates for Gradient Descent on the Edge of Stability in Overparametrised Least Squares](https://mlsanity.com/paper/2510.17506/) (2025)

## Abstract (arXiv)

We give a simple proof for the global convergence of gradient descent in training deep ReLU networks with the standard square loss, and show some of its improvements over the state-of-the-art. In particular, while prior works require all the hidden layers to be wide with width at least Omega(N8) (N being the number of training samples), we require a single wide layer of linear, quadratic or cubic width depending on the type of initialization. Unlike many recent proofs based on the Neural Tangent Kernel (NTK), our proof need not track the evolution of the entire NTK matrix, or more generally, any quantities related to the changes of activation patterns during training. Instead, we only need to track the evolution of the output at the last hidden layer, which can be done much more easily thanks to the Lipschitz property of ReLU. Some highlights of our setting: (i) all the layers are trained with standard gradient descent, (ii) the network has standard parameterization as opposed to the NTK one, and (iii) the network has a single wide layer as opposed to having all wide hidden layers as in most of NTK-related results.