mlsanityData to 7 Oct 2026

Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks

arXiv 2209.09298 ↗First posted 19 Sep 2022cs.LG stat.MLcited by 21

Not on the map. Why?

Abstract (arXiv)

While significant theoretical progress has been achieved, unveiling the generalization mystery of overparameterized neural networks still remains largely elusive. In this paper, we study the generalization behavior of shallow neural networks (SNNs) by leveraging the concept of algorithmic stability. We consider gradient descent (GD) and stochastic gradient descent (SGD) to train SNNs, for both of which we develop consistent excess risk bounds by balancing the optimization and generalization via early-stopping. As compared to existing analysis on GD, our new analysis requires a relaxed overparameterization assumption and also applies to SGD. The key for the improvement is a better estimation of the smallest eigenvalues of the Hessian matrices of the empirical risks and the loss function along the trajectories of GD and SGD by providing a refined estimation of their iterates.

Key facts. Cited by 21 papers in the map (data through 7 Oct 2026). Builds on 51 of its 84 references that are in the map. First posted on arXiv 19 Sep 2022.

Builds on

51 of 84 references.

References · 51

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  3. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  4. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  5. 2019Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descentcited by 732
  6. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  7. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  8. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  9. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  10. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 527
  11. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  12. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
38 more
  1. 2018Stronger generalization bounds for deep nets via a compression approachcited by 306
  2. 2017Size-Independent Sample Complexity of Neural Networkscited by 289
  3. 2021Deep learning: a statistical viewpointcited by 239
  4. 2019Uniform convergence may be unable to explain generalization in deep learningcited by 223
  5. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 221
  6. 2018Universality of Deep Convolutional Neural Networkscited by 176
  7. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  8. 2019Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networkscited by 158
  9. 2018Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networkscited by 140
  10. 2018Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networkscited by 139
  11. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 118
  12. 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
  13. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 97
  14. 2019Sharper bounds for uniformly stable algorithmscited by 91
  15. 2017Data-Dependent Stability of Stochastic Gradient Descentcited by 90
  16. 2018Closing the Generalization Gap of Adaptive Gradient Methods in Training Deep Neural Networkscited by 89
  17. 2019Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networkscited by 79
  18. 2019On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learningcited by 57
  19. 2018Stability and Convergence Trade-off of Iterative Optimization Algorithmscited by 53
  20. 2020Train simultaneously, generalize better: Stability of gradient-based minimax learnerscited by 43
  21. 2021Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)cited by 42
  22. 2020Toward Better Generalization Bounds with Locally Elastic Stabilitycited by 41
  23. 2017Algorithmic stability and hypothesis complexitycited by 39
  24. 2020Regularization Matters: A Nonparametric Perspective on Overparametrized Neural Networkcited by 38
  25. 2021SGD Generalizes Better Than GD (And Regularization Doesn't Help)cited by 38
  26. 2021Stability and Generalization of Stochastic Gradient Methods for Minimax Problemscited by 35
  27. 2021Early-stopped neural networks are consistentcited by 34
  28. 2020Analyzing Finite Neural Networks: Can We Trust Neural Tangent Kernel Theory?cited by 33
  29. 2021Stability and Generalization of Bilevel Programming in Hyperparameter Optimizationcited by 31
  30. 2022Stability vs Implicit Bias of Gradient Methods on Separable Data and Beyondcited by 29
  31. 2020Generalization Bounds for Stochastic Saddle Point Problemscited by 27
  32. 2021Stability & Generalisation of Gradient Descent for Shallow Neural Networks without the Neural Tangent Kernelcited by 25
  33. 2022Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GDcited by 19
  34. 2022Benign Underfitting of Stochastic Gradient Descentcited by 18
  35. 2016Generalization Properties and Implicit Regularization for Multiple Passes SGMcited by 16
  36. 2021Learning with Gradient Descent and Weakly Convex Lossescited by 16
  37. 2021Universal Consistency of Deep Convolutional Neural Networkscited by 16
  38. 2020Benefit of deep learning with non-convex noisy gradient descent: Provable excess risk bound and superiority to kernel methodscited by 9

50 most cited of 51 All 51 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 8; 2024: 3; 2025: 5; 2026: 4.

21 papers.

Sort:

By area:

  1. 2023On the Optimization and Generalization of Multi-head Attentioncited by 37
  2. 2023Three-Way Trade-Off in Multi-Objective Learning: Optimization, Generalization and Conflict-Avoidancecited by 35
  3. 2023Generalization Ability of Wide Neural Networks on ℝcited by 28
  4. 2023Generalization and Stability of Interpolating Neural Networks with Minimal Widthcited by 21
  5. 2023Generalization Guarantees of Gradient Descent for Multi-Layer Neural Networkscited by 9
  6. 2023Select without Fear: Almost All Mini-Batch Schedules Generalize Optimallycited by 5
  7. 2023Stability and Generalization of Stochastic Compositional Gradient Descent Algorithmscited by 3
  8. 2025Stability and Generalization of Quantum Neural Networkscited by 3
  9. 2025Optimal Rates for Generalization of Gradient Descent for Deep ReLU Classificationcited by 3
  10. 2025Temperature is All You Need for Generalization in Langevin Dynamics and other Markov Processescited by 2
  11. 2025Observational Multiplicitycited by 2
  12. 2022Do highly over-parameterized neural networks generalize since bad solutions are rare?cited by 1
9 more
  1. 2024Which Algorithms Have Tight Generalization Bounds?cited by 1
  2. 2026Optimization, Generalization and Differential Privacy Bounds for Gradient Descent on Kolmogorov-Arnold Networkscited by 1
  3. 2023Towards Understanding the Generalizability of Delayed Stochastic Gradient Descentcited by 0
  4. 2024Bootstrap SGD: Algorithmic Stability and Robustnesscited by 0
  5. 2024Rethinking generalization of classifiers in separable classes scenarios and over-parameterized regimescited by 0
  6. 2025AYLA: Architecting a loss landscape in shallow neural networks to accelerate feature recoverycited by 0
  7. 2026Sequential Subspace Noise Injection Prevents Accuracy Collapse in Certified Unlearningcited by 0
  8. 2026Optimal Rates for Generalization of Gradient Descent Methods with Deep Neural Networkscited by 0
  9. 2026Minimax-Optimal Generalization Bounds for Smooth Deep Neural Networks Trained by (Stochastic) Gradient Descentcited by 0