mlsanityData to 7 Oct 2026

A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks

arXiv 2101.04243 ↗First posted 12 Jan 2021cs.LG math.OC stat.MLcited by 4

Not on the map. Why?

Abstract (arXiv)

Deep neural networks' remarkable ability to correctly fit training data when optimized by gradient-based algorithms is yet to be fully understood. Recent theoretical results explain the convergence for ReLU networks that are wider than those used in practice by orders of magnitude. In this work, we take a step towards closing the gap between theory and practice by significantly improving the known theoretical bounds on both the network width and the convergence time. We show that convergence to a global minimum is guaranteed for networks with widths quadratic in the sample size and linear in their depth at a time logarithmic in both. Our analysis and convergence bounds are derived via the construction of a surrogate network with fixed activation patterns that can be transformed at any time to an equivalent ReLU network of a reasonable size. This construction can be viewed as a novel technique to accelerate training, while its tight finite-width equivalence to Neural Tangent Kernel (NTK) suggests it can be utilized to study generalization as well.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 72 of its 90 references that are in the map. First posted on arXiv 12 Jan 2021.

Builds on

72 of 90 references.

References · 72

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  3. 2020Language Models are Few-Shot Learnerscited by 32,199
  4. 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 6,979
  5. 2016Wide Residual Networkscited by 3,057
  6. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  7. 2019RandAugment: Practical automated data augmentation with a reduced search spacecited by 2,261
  8. 2016Identity Mappings in Deep Residual Networkscited by 1,960
  9. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  10. 2015Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs)cited by 1,061
  11. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  12. 2019Big Transfer (BiT): General Visual Representation Learningcited by 766
38 more
  1. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  2. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  3. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 572
  4. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  5. 2015Empirical Evaluation of Rectified Activations in Convolutional Networkcited by 515
  6. 2018Quantizing deep convolutional networks for efficient inference: A whitepapercited by 507
  7. 2018How Does Batch Normalization Help Optimization?cited by 355
  8. 2018On the Optimization of Deep Networks: Implicit Acceleration by Overparameterizationcited by 280
  9. 2014The Loss Surfaces of Multilayer Networkscited by 278
  10. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 260
  11. 2020ReZero is All You Need: Fast Convergence at Large Depthcited by 260
  12. 2016Deep Learning without Poor Local Minimacited by 233
  13. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 221
  14. 2018Just Interpolate: Kernel "Ridgeless" Regression Can Generalizecited by 190
  15. 2018To understand deep learning we need to understand kernel learningcited by 186
  16. 2015The Power of Depth for Feedforward Neural Networkscited by 181
  17. 2018A Convergence Analysis of Gradient Descent for Deep Linear Neural Networkscited by 180
  18. 2019Towards moderate overparameterization: global convergence guarantees for training shallow neural networkscited by 176
  19. 2015Training Very Deep Networkscited by 172
  20. 2019Complexity of Linear Regions in Deep Networkscited by 166
  21. 2019Deep ReLU Networks Have Surprisingly Few Activation Patternscited by 160
  22. 2020Finite Versus Infinite Neural Networks: an Empirical Studycited by 156
  23. 2018Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networkscited by 139
  24. 2017Convergence Analysis of Two-layer Neural Networks with ReLU Activationcited by 137
  25. 2017Theoretical insights into the optimization landscape of over-parameterized shallow neural networkscited by 128
  26. 2019An Improved Analysis of Training Over-parameterized Deep Neural Networkscited by 120
  27. 2020TResNet: High Performance GPU-Dedicated Architecturecited by 119
  28. 2016Identity Matters in Deep Learningcited by 107
  29. 2017Spurious Local Minima are Common in Two-Layer ReLU Neural Networkscited by 104
  30. 2018On the Power of Over-parametrization in Neural Networks with Quadratic Activationcited by 102
  31. 2018Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolatecited by 99
  32. 2015On the Expressive Power of Deep Learning: A Tensor Analysiscited by 97
  33. 2019Dynamics of Deep Neural Networks and Neural Tangent Hierarchycited by 96
  34. 2018Which Neural Net Architectures Give Rise To Exploding and Vanishing Gradients?cited by 94
  35. 2015Representation Benefits of Deep Feedforward Networkscited by 84
  36. 2019How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?cited by 84
  37. 2019Scaling description of generalization with number of parameters in deep learningcited by 83
  38. 2016Why Deep Neural Networks for Function Approximation?cited by 82

50 most cited of 72 All 72 (JSON)

Built on by

Cited by year

Citing papers per year: 2021: 2; 2022: 2.

4 papers.

  1. 2021Continuous vs. Discrete Optimization of Deep Neural Networkscited by 34
  2. 2022When Expressivity Meets Trainability: Fewer than n Neurons Can Workcited by 8
  3. 2021SGD Through the Lens of Kolmogorov Complexitycited by 1
  4. 2022Demystifying the Global Convergence Puzzle of Learning Over-parameterized ReLU Nets in Very High Dimensionscited by 0