# Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks

arXiv: https://arxiv.org/abs/2209.09298 · HTML: https://mlsanity.com/paper/2209.09298/

## Key facts

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

## Builds on (most cited first, 30 of 51)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (2018)
- [Stronger generalization bounds for deep nets via a compression approach](https://mlsanity.com/paper/1802.05296/) (2018)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Deep learning: a statistical viewpoint](https://mlsanity.com/paper/2103.09177/) (2021)
- [Uniform convergence may be unable to explain generalization in deep learning](https://mlsanity.com/paper/1902.04742/) (2019)
- [Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks](https://mlsanity.com/paper/1905.13210/) (2019)
- [Universality of Deep Convolutional Neural Networks](https://mlsanity.com/paper/1805.10769/) (2018)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks](https://mlsanity.com/paper/1903.11680/) (2019)
- [Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks](https://mlsanity.com/paper/1805.12076/) (2018)
- [Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks](https://mlsanity.com/paper/1811.08888/) (2018)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [Stability and Generalization of Learning Algorithms that Converge to Global Optima](https://mlsanity.com/paper/1710.08402/) (2017)
- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [Sharper bounds for uniformly stable algorithms](https://mlsanity.com/paper/1910.07833/) (2019)
- [Data-Dependent Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/1703.01678/) (2017)
- [Closing the Generalization Gap of Adaptive Gradient Methods in Training Deep Neural Networks](https://mlsanity.com/paper/1806.06763/) (2018)
- [Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks](https://mlsanity.com/paper/1910.01619/) (2019)
- [On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning](https://mlsanity.com/paper/1902.00621/) (2019)

## Built on by (most cited first, 21 of 21)

- [On the Optimization and Generalization of Multi-head Attention](https://mlsanity.com/paper/2310.12680/) (2023)
- [Three-Way Trade-Off in Multi-Objective Learning: Optimization, Generalization and Conflict-Avoidance](https://mlsanity.com/paper/2305.20057/) (2023)
- [Generalization Ability of Wide Neural Networks on ℝ](https://mlsanity.com/paper/2302.05933/) (2023)
- [Generalization and Stability of Interpolating Neural Networks with Minimal Width](https://mlsanity.com/paper/2302.09235/) (2023)
- [Generalization Guarantees of Gradient Descent for Multi-Layer Neural Networks](https://mlsanity.com/paper/2305.16891/) (2023)
- [Select without Fear: Almost All Mini-Batch Schedules Generalize Optimally](https://mlsanity.com/paper/2305.02247/) (2023)
- [Stability and Generalization of Stochastic Compositional Gradient Descent Algorithms](https://mlsanity.com/paper/2307.03357/) (2023)
- [Stability and Generalization of Quantum Neural Networks](https://mlsanity.com/paper/2501.12737/) (2025)
- [Optimal Rates for Generalization of Gradient Descent for Deep ReLU Classification](https://mlsanity.com/paper/2510.02779/) (2025)
- [Temperature is All You Need for Generalization in Langevin Dynamics and other Markov Processes](https://mlsanity.com/paper/2505.19087/) (2025)
- [Observational Multiplicity](https://mlsanity.com/paper/2507.23136/) (2025)
- [Do highly over-parameterized neural networks generalize since bad solutions are rare?](https://mlsanity.com/paper/2211.03570/) (2022)
- [Which Algorithms Have Tight Generalization Bounds?](https://mlsanity.com/paper/2410.01969/) (2024)
- [Optimization, Generalization and Differential Privacy Bounds for Gradient Descent on Kolmogorov-Arnold Networks](https://mlsanity.com/paper/2601.22409/) (2026)
- [Towards Understanding the Generalizability of Delayed Stochastic Gradient Descent](https://mlsanity.com/paper/2308.09430/) (2023)
- [Bootstrap SGD: Algorithmic Stability and Robustness](https://mlsanity.com/paper/2409.01074/) (2024)
- [Rethinking generalization of classifiers in separable classes scenarios and over-parameterized regimes](https://mlsanity.com/paper/2410.16868/) (2024)
- [AYLA: Architecting a loss landscape in shallow neural networks to accelerate feature recovery](https://mlsanity.com/paper/2504.01875/) (2025)
- [Sequential Subspace Noise Injection Prevents Accuracy Collapse in Certified Unlearning](https://mlsanity.com/paper/2601.05134/) (2026)
- [Optimal Rates for Generalization of Gradient Descent Methods with Deep Neural Networks](https://mlsanity.com/paper/2606.06764/) (2026)
- [Minimax-Optimal Generalization Bounds for Smooth Deep Neural Networks Trained by (Stochastic) Gradient Descent](https://mlsanity.com/paper/2606.06772/) (2026)

## 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.