mlsanityData to 14 Oct 2026

Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks

arXiv 1905.13210 ↗First posted 30 May 2019cs.LG math.OC stat.MLcited by 222

Not on the map. Why?

Abstract (arXiv)

We study the training and generalization of deep neural networks (DNNs) in the over-parameterized regime, where the network width (i.e., number of hidden nodes per layer) is much larger than the number of training data points. We show that, the expected 0-1 loss of a wide enough ReLU network trained with stochastic gradient descent (SGD) and random initialization can be bounded by the training loss of a random feature model induced by the network gradient at initialization, which we call a neural tangent random feature (NTRF) model. For data distributions that can be classified by NTRF model with sufficiently small error, our result yields a generalization error bound in the order of tildeO(n-1/2) that is independent of the network width. Our result is more general and sharper than many existing generalization error bounds for over-parameterized neural networks. In addition, we establish a strong connection between our generalization error bound and the neural tangent kernel (NTK) proposed in recent work.

Key facts. Cited by 222 papers in the map (data through 14 Oct 2026). First posted on arXiv 30 May 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 50; 2022: 53; 2023: 49; 2024: 35; 2025: 19; 2026: 16.

222 papers.

Sort:

By area:

  1. 2021The Values Encoded in Machine Learning Researchcited by 172
  2. 2022A Kernel-Based View of Language Model Fine-Tuningcited by 121
  3. 2022Benign Overfitting in Two-layer Convolutional Neural Networkscited by 91
  4. 2022Understanding the Generalization Benefit of Normalization Layers: Sharpness Reductioncited by 86
  5. 2023Dichotomy of Early and Late Phase Implicit Biases Can Provably Induce Grokkingcited by 80
  6. 2023A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexitycited by 77
  7. 2021Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeedcited by 69
  8. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  9. 2021Exploring Memorization in Adversarial Trainingcited by 55
  10. 2022Towards Understanding Mixture of Experts in Deep Learningcited by 52
  11. 2021Understanding the Generalization of Adam in Learning Neural Networks with Proper Regularizationcited by 49
  12. 2021A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Networkcited by 47
38 more
  1. 2022Deep Nonparametric Estimation of Operators between Infinite Dimensional Spacescited by 45
  2. 2021EE-Net: Exploitation-Exploration Neural Networks in Contextual Banditscited by 44
  3. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 43
  4. 2022Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPscited by 42
  5. 2021Neural Contextual Bandits without Regretcited by 40
  6. 2023On the Optimization and Generalization of Multi-head Attentioncited by 37
  7. 2024How Do Nonlinear Transformers Learn and Generalize in In-Context Learning?cited by 35
  8. 2021Early-stopped neural networks are consistentcited by 34
  9. 2021Scaling Neural Tangent Kernels via Sketching and Random Featurescited by 32
  10. 2021Does Preprocessing Help Training Over-parameterized Neural Networks?cited by 32
  11. 2021Deep Active Learning by Leveraging Training Dynamicscited by 32
  12. 2022Understanding Gradual Domain Adaptation: Improved Analysis, Optimal Path and Beyondcited by 32
  13. 2024PINNACLE: PINN Adaptive ColLocation and Experimental points selectioncited by 32
  14. 2024Implicit Bias and Fast Convergence Rates for Self-attentioncited by 31
  15. 2022Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessingcited by 29
  16. 2022Improving Multi-Task Generalization via Regularizing Spurious Correlationcited by 28
  17. 2021Properties of the After Kernelcited by 27
  18. 2021Rethinking Influence Functions of Neural Networks in the Over-parameterized Regimecited by 26
  19. 2023Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimensioncited by 26
  20. 2023How to Protect Copyright Data in Optimization of Large Language Models?cited by 26
  21. 2021Measuring Generalization with Optimal Transportcited by 25
  22. 2021Offline Neural Contextual Bandits: Pessimism, Optimization and Generalizationcited by 25
  23. 2022Sample-Then-Optimize Batch Neural Thompson Samplingcited by 25
  24. 2023Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuroncited by 25
  25. 2022Convergence of gradient descent for deep neural networkscited by 24
  26. 2021Neural Active Learning with Performance Guaranteescited by 22
  27. 2022Global Convergence of MAML and Theory-Inspired Neural Architecture Search for Few-Shot Learningcited by 22
  28. 2021The Limitations of Large Width in Neural Networks: A Deep Gaussian Process Perspectivecited by 21
  29. 2022Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networkscited by 21
  30. 2023Generalization and Stability of Interpolating Neural Networks with Minimal Widthcited by 21
  31. 2024Operator Learning Using Random Features: A Tool for Scientific Computingcited by 21
  32. 2021Multi-facet Contextual Bandits: A Neural Network Perspectivecited by 20
  33. 2023Graph Neural Banditscited by 20
  34. 2023Six Lectures on Linearized Neural Networkscited by 20
  35. 2024A Survey on Statistical Theory of Deep Learning: Approximation, Training Dynamics, and Generative Modelscited by 20
  36. 2021Towards Understanding Learning in Neural Networks with Linear Teacherscited by 19
  37. 2023Provable Guarantees for Nonlinear Feature Learning in Three-Layer Neural Networkscited by 19
  38. 2022Fast Neural Kernel Embeddings for General Activationscited by 18

50 most cited of 222 All 222 (JSON)