mlsanityData to 7 Oct 2026

Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks

arXiv 1909.12292 ↗First posted 26 Sep 2019cs.LG math.OC stat.MLcited by 120

Not on the map. Why?

Abstract (arXiv)

Recent theoretical work has guaranteed that overparameterized networks trained by gradient descent achieve arbitrarily low training error, and sometimes even low test error. The required width, however, is always polynomial in at least one of the sample size n, the (inverse) target error 1/ε, and the (inverse) failure probability 1/δ. This work shows that widetildeTheta(1/ε) iterations of gradient descent with widetildeOmega(1/ε2) training examples on two-layer ReLU networks of any width exceeding polylog(n,1/ε,1/δ) suffice to achieve a test misclassification error of ε. We also prove that stochastic gradient descent can achieve ε test error with polylogarithmic width and widetildeTheta(1/ε) samples. The analysis relies upon the separation margin of the limiting kernel, which is guaranteed positive, can distinguish between true labels and random labels, and can give a tight sample-complexity analysis in the infinite-width setting

Key facts. Cited by 120 papers in the map (data through 7 Oct 2026). First posted on arXiv 26 Sep 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 28; 2022: 35; 2023: 28; 2024: 12; 2025: 10; 2026: 7.

120 papers.

Sort:

By area:

  1. 2022Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limitcited by 184
  2. 2022High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representationcited by 146
  3. 2022Modality Competition: What Makes Joint Training of Multi-modal Network Fail in Deep Learning? (Provably)cited by 115
  4. 2022Benign Overfitting in Two-layer Convolutional Neural Networkscited by 90
  5. 2021Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Biascited by 82
  6. 2023Dichotomy of Early and Late Phase Implicit Biases Can Provably Induce Grokkingcited by 76
  7. 2022Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Datacited by 74
  8. 2022Analyzing Sharpness along GD Trajectory: Progressive Sharpening and Edge of Stabilitycited by 61
  9. 2022AutoBalance: Optimized Loss Functions for Imbalanced Datacited by 49
  10. 2021Understanding the Generalization of Adam in Learning Neural Networks with Proper Regularizationcited by 48
  11. 2021On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widthscited by 44
  12. 2022Sub-Task Decomposition Enables Learning in Sequence to Sequence Taskscited by 41
38 more
  1. 2022The Neural Covariance SDE: Shaped Infinite Depth-and-Width Networks at Initializationcited by 41
  2. 2023On the Optimization and Generalization of Multi-head Attentioncited by 37
  3. 2022Memorization and Optimization in Deep Neural Networks with Minimum Over-parameterizationcited by 36
  4. 2023Patch-level Routing in Mixture-of-Experts is Provably Sample-efficient for Convolutional Neural Networkscited by 35
  5. 2021Early-stopped neural networks are consistentcited by 34
  6. 2021Does Preprocessing Help Training Over-parameterized Neural Networks?cited by 32
  7. 2023Continual Learning in Linear Classification on Separable Datacited by 31
  8. 2022Spectral Evolution and Invariance in Linear-width Neural Networkscited by 30
  9. 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
  10. 2022Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessingcited by 29
  11. 2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 29
  12. 2021Properties of the After Kernelcited by 27
  13. 2021Subquadratic Overparameterization for Shallow Neural Networkscited by 26
  14. 2023How to Protect Copyright Data in Optimization of Large Language Models?cited by 26
  15. 2021Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descentcited by 21
  16. 2023Generalization and Stability of Interpolating Neural Networks with Minimal Widthcited by 21
  17. 2021Towards Understanding Learning in Neural Networks with Linear Teacherscited by 19
  18. 2023Six Lectures on Linearized Neural Networkscited by 19
  19. 2021Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noisecited by 17
  20. 2021Learning with Density Matrices and Random Featurescited by 17
  21. 2022Quadratic models for understanding catapult dynamics of neural networkscited by 17
  22. 2022Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithmcited by 17
  23. 2021Learning with Gradient Descent and Weakly Convex Lossescited by 16
  24. 2022Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysiscited by 15
  25. 2023Understanding Multi-phase Optimization Dynamics and Rich Nonlinear Behaviors of ReLU Networkscited by 15
  26. 2023Provable Multi-Task Representation Learning by Two-Layer ReLU Neural Networkscited by 15
  27. 2021The Separation Capacity of Random Neural Networkscited by 14
  28. 2021Understanding Square Loss in Training Overparametrized Neural Network Classifierscited by 14
  29. 2024Differential Privacy Mechanisms in Neural Tangent Kernel Regressioncited by 14
  30. 2021On the Generalization Power of Overfitted Two-Layer Neural Tangent Kernel Modelscited by 13
  31. 2021Actor-critic is implicitly biased towards high entropy optimal policiescited by 13
  32. 2022Feature selection with gradient descent on two-layer networks in low-rotation regimescited by 13
  33. 2023A Unified Approach to Controlling Implicit Regularization via Mirror Descentcited by 13
  34. 2023A Unified Scheme of ResNet and Softmaxcited by 12
  35. 2021The Dynamics of Gradient Descent for Overparametrized Neural Networkscited by 11
  36. 2021On the Convergence of Shallow Neural Network Training with Randomly Masked Neuronscited by 11
  37. 2022Spectral Bias Outside the Training Set for Deep Networks in the Kernel Regimecited by 11
  38. 2023Unmasking Transformers: A Theoretical Approach to Data Recovery via Attention Weightscited by 11

50 most cited of 120 All 120 (JSON)