mlsanityData to 14 Oct 2026

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

arXiv 2101.09612 ↗First posted 24 Jan 2021cs.LG stat.MLcited by 44

Not on the map. Why?

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.

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

21 of 25 references.

References · 21

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  2. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  3. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
  4. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 655
  5. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 574
  6. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 566
  7. 2018A Mean Field View of the Landscape of Two-Layers Neural Networkscited by 466
  8. 2018On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transportcited by 426
  9. 2020Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Losscited by 268
  10. 2019Towards moderate overparameterization: global convergence guarantees for training shallow neural networkscited by 176
  11. 2019An Improved Analysis of Training Over-parameterized Deep Neural Networkscited by 121
  12. 2019Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networkscited by 121
9 more
  1. 2019Dynamics of Deep Neural Networks and Neural Tangent Hierarchycited by 96
  2. 2020Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networkscited by 87
  3. 2019How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?cited by 84
  4. 2017SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Datacited by 79
  5. 2020Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topologycited by 66
  6. 2019Quadratic Suffices for Over-parametrization via Matrix Chernoff Boundcited by 59
  7. 2017SGD Learns the Conjugate Kernel Class of the Networkcited by 54
  8. 2019Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problemscited by 24
  9. 2019Neural Networks Learning and Memorization with (almost) no Over-Parameterizationcited by 23

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 13; 2022: 18; 2023: 3; 2024: 4; 2025: 3; 2026: 3.

44 papers.

Sort:

By area:

  1. 2021On the Implicit Bias of Initialization Shape: Beyond Infinitesimal Mirror Descentcited by 70
  2. 2021On Provable Benefits of Depth in Training Graph Convolutional Networkscited by 58
  3. 2022Memorization and Optimization in Deep Neural Networks with Minimum Over-parameterizationcited by 36
  4. 2022Spectral Evolution and Invariance in Linear-width Neural Networkscited by 30
  5. 2021Offline Neural Contextual Bandits: Pessimism, Optimization and Generalizationcited by 25
  6. 2022Approximation bounds for norm constrained neural networks with applications to regression and GANscited by 22
  7. 2022Characterizing the Spectrum of the NTK via a Power Series Expansioncited by 22
  8. 2021Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networkscited by 21
  9. 2021A global convergence theory for deep ReLU implicit networks via over-parameterizationcited by 17
  10. 2022Generalization Properties of NAS under Activation and Skip Connection Searchcited by 14
  11. 2023Wide Neural Networks as Gaussian Processes: Lessons from Deep Equilibrium Modelscited by 14
  12. 2023On the Convergence of Encoder-only Shallow Transformerscited by 13
32 more
  1. 2024Bounds for the smallest eigenvalue of the NTK for arbitrary spherical data of arbitrary dimensioncited by 13
  2. 2021On the Convergence of Shallow Neural Network Training with Randomly Masked Neuronscited by 11
  3. 2022Spectral Bias Outside the Training Set for Deep Networks in the Kernel Regimecited by 11
  4. 2024From Activation to Initialization: Scaling Insights for Optimizing Neural Fieldscited by 11
  5. 2021Local SGD Optimizes Overparameterized Neural Networks in Polynomial Timecited by 10
  6. 2022Global Convergence of Over-parameterized Deep Equilibrium Modelscited by 10
  7. 2021Sample Complexity of Offline Reinforcement Learning with Deep ReLU Networkscited by 8
  8. 2022When Expressivity Meets Trainability: Fewer than n Neurons Can Workcited by 8
  9. 2024Understanding the training of infinitely deep and wide ResNets with Conditional Optimal Transportcited by 8
  10. 2021Spurious Local Minima Are Common for Deep Neural Networks with Piecewise Linear Activationscited by 7
  11. 2022Restricted Strong Convexity of Deep Learning Models with Smooth Activationscited by 7
  12. 2022On skip connections and normalisation layers in deep optimisationcited by 7
  13. 2022Gradient Descent Optimizes Infinite-Depth ReLU Implicit Networks with Linear Widthscited by 5
  14. 2022Finite Sample Identification of Wide Shallow Neural Networks with Biasescited by 5
  15. 2022Learning Lipschitz Functions by GD-trained Shallow Overparameterized ReLU Neural Networkscited by 5
  16. 2021How much pre-training is enough to discover a good subnetwork?cited by 4
  17. 2023Global Convergence Rate of Deep Equilibrium Models with General Activationscited by 4
  18. 2025Convergence Rates for Gradient Descent on the Edge of Stability in Overparametrised Least Squarescited by 4
  19. 2025A Law of Data Reconstruction for Random Features (and Beyond)cited by 3
  20. 2021Generalization of GANs and overparameterized models under Lipschitz continuitycited by 2
  21. 2022A Framework for Overparameterized Learningcited by 2
  22. 2021SGD Through the Lens of Kolmogorov Complexitycited by 1
  23. 2022Improved Overparametrization Bounds for Global Convergence of Stochastic Gradient Descent for Shallow Neural Networkscited by 1
  24. 2022Improved Convergence Guarantees for Shallow Neural Networkscited by 1
  25. 2024Error Analysis of Three-Layer Neural Network Trained with PGD for Deep Ritz Methodcited by 1
  26. 2026Finite-Time Analysis of Gradient Descent for Shallow Transformerscited by 1
  27. 2026On the global convergence of gradient flow for wide shallow models beyond homogeneous nonlinearitiescited by 1
  28. 2026Dynamics of Gradient Descent with Large Step Size Near a Manifold of Flat Minimacited by 1
  29. 2021To Supervise or Not: How to Effectively Learn Wireless Interference Management Models?cited by 0
  30. 2022On Practical Reinforcement Learning: Provable Robustness, Scalability, and Statistical Efficiencycited by 0
  31. 2022Provable Acceleration of Nesterov's Accelerated Gradient Method over Heavy Ball Method in Training Over-Parameterized Neural Networkscited by 0
  32. 2025Learning Provably Improves the Convergence of Gradient Descentcited by 0