# Stability & Generalisation of Gradient Descent for Shallow Neural Networks without the Neural Tangent Kernel

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 41 references that are in the map.
- First posted on arXiv 27 Jul 2021.

## Builds on (most cited first, 29 of 29)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [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)
- [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)
- [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)
- [Loss landscapes and optimization in over-parameterized non-linear systems and neural networks](https://mlsanity.com/paper/2003.00307/) (2020)
- [Towards moderate overparameterization: global convergence guarantees for training shallow neural networks](https://mlsanity.com/paper/1902.04674/) (2019)
- [Eigenvalues of the Hessian in Deep Learning: Singularity and Beyond](https://mlsanity.com/paper/1611.07476/) (2016)
- [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)
- [On the linearity of large non-linear models: when and why the tangent kernel is constant](https://mlsanity.com/paper/2010.01092/) (2020)
- [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)
- [Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks](https://mlsanity.com/paper/1910.01619/) (2019)
- [Stability and Convergence Trade-off of Iterative Optimization Algorithms](https://mlsanity.com/paper/1804.01619/) (2018)
- [Regularization Matters: A Nonparametric Perspective on Overparametrized Neural Network](https://mlsanity.com/paper/2007.02486/) (2020)
- [Early-stopped neural networks are consistent](https://mlsanity.com/paper/2106.05932/) (2021)
- [Analyzing Finite Neural Networks: Can We Trust Neural Tangent Kernel Theory?](https://mlsanity.com/paper/2012.04477/) (2020)
- [Learning with Gradient Descent and Weakly Convex Losses](https://mlsanity.com/paper/2101.04968/) (2021)
- [Benefit of deep learning with non-convex noisy gradient descent: Provable excess risk bound and superiority to kernel methods](https://mlsanity.com/paper/2012.03224/) (2020)
- [Fast Rates for Empirical Risk Minimization of Strict Saddle Problems](https://mlsanity.com/paper/1701.04271/) (2017)
- [An Exponential Efron-Stein Inequality for Lq Stable Learning Rules](https://mlsanity.com/paper/1903.05457/) (2019)
- [Nonparametric Regression with Shallow Overparameterized Neural Networks Trained by GD with Early Stopping](https://mlsanity.com/paper/2107.05341/) (2021)

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

- [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)
- [Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problems](https://mlsanity.com/paper/2206.07082/) (2022)
- [Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks](https://mlsanity.com/paper/2209.09298/) (2022)
- [Generalization and Stability of Interpolating Neural Networks with Minimal Width](https://mlsanity.com/paper/2302.09235/) (2023)
- [Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizes](https://mlsanity.com/paper/2406.06838/) (2024)
- [Generalization Guarantees of Gradient Descent for Multi-Layer Neural Networks](https://mlsanity.com/paper/2305.16891/) (2023)
- [Norm-based Generalization Bounds for Compositionally Sparse Neural Networks](https://mlsanity.com/paper/2301.12033/) (2023)
- [NTK-Guided Few-Shot Class Incremental Learning](https://mlsanity.com/paper/2403.12486/) (2024)
- [Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methods](https://mlsanity.com/paper/2410.10024/) (2024)
- [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)
- [On the Theory of Continual Learning with Gradient Descent for Neural Networks](https://mlsanity.com/paper/2510.05573/) (2025)
- [Black-Box Generalization: Stability of Zeroth-Order Learning](https://mlsanity.com/paper/2202.06880/) (2022)
- [Optimization, Generalization and Differential Privacy Bounds for Gradient Descent on Kolmogorov-Arnold Networks](https://mlsanity.com/paper/2601.22409/) (2026)
- [Sufficient Conditions for Stability of Minimum-Norm Interpolating Deep ReLU Networks](https://mlsanity.com/paper/2602.13910/) (2026)
- [Stochastic Gradient Descent with Momentum is Algorithmically Stable](https://mlsanity.com/paper/2605.28517/) (2026)
- [A Linearly Convergent GAN Inversion-based Algorithm for Reverse Engineering of Deceptions](https://mlsanity.com/paper/2306.04756/) (2023)
- [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)
- [Generalization and Optimization of SGD with Lookahead](https://mlsanity.com/paper/2509.15776/) (2025)
- [Sequential Subspace Noise Injection Prevents Accuracy Collapse in Certified Unlearning](https://mlsanity.com/paper/2601.05134/) (2026)
- [Towards Initialization-dependent and Non-vacuous Generalization Bounds for Overparameterized Shallow Neural Networks](https://mlsanity.com/paper/2604.00505/) (2026)
- [Learning Theory of the SVRG: Generalization and Convergence Analysis](https://mlsanity.com/paper/2605.28513/) (2026)
- [Minimax-Optimal Generalization Bounds for Smooth Deep Neural Networks Trained by (Stochastic) Gradient Descent](https://mlsanity.com/paper/2606.06772/) (2026)
- [Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problems](https://mlsanity.com/paper/2610.19322/) (2026)

## Abstract (arXiv)

We revisit on-average algorithmic stability of GD for training overparameterised shallow neural networks and prove new generalisation and excess risk bounds without the NTK or PL assumptions. In particular, we show oracle type bounds which reveal that the generalisation and excess risk of GD is controlled by an interpolating network with the shortest GD path from initialisation (in a sense, an interpolating network with the smallest relative norm). While this was known for kernelised interpolants, our proof applies directly to networks trained by GD without intermediate kernelisation. At the same time, by relaxing oracle inequalities developed here we recover existing NTK-based risk bounds in a straightforward way, which demonstrates that our analysis is tighter. Finally, unlike most of the NTK-based analyses we focus on regression with label noise and show that GD with early stopping is consistent.