mlsanityData to 14 Oct 2026

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

arXiv 2107.12723 ↗First posted 27 Jul 2021stat.ML cs.LG math.STcited by 26

Not on the map. Why?

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.

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

29 of 41 references.

References · 29

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  2. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  3. 2019Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descentcited by 738
  4. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
  5. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 566
  6. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  7. 2017Size-Independent Sample Complexity of Neural Networkscited by 290
  8. 2021Deep learning: a statistical viewpointcited by 240
  9. 2020Loss landscapes and optimization in over-parameterized non-linear systems and neural networkscited by 233
  10. 2019Towards moderate overparameterization: global convergence guarantees for training shallow neural networkscited by 176
  11. 2016Eigenvalues of the Hessian in Deep Learning: Singularity and Beyondcited by 159
  12. 2019Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networkscited by 159
17 more
  1. 2018Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networkscited by 142
  2. 2020On the linearity of large non-linear models: when and why the tangent kernel is constantcited by 129
  3. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 119
  4. 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
  5. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 98
  6. 2019Sharper bounds for uniformly stable algorithmscited by 93
  7. 2017Data-Dependent Stability of Stochastic Gradient Descentcited by 92
  8. 2019Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networkscited by 79
  9. 2018Stability and Convergence Trade-off of Iterative Optimization Algorithmscited by 53
  10. 2020Regularization Matters: A Nonparametric Perspective on Overparametrized Neural Networkcited by 38
  11. 2021Early-stopped neural networks are consistentcited by 34
  12. 2020Analyzing Finite Neural Networks: Can We Trust Neural Tangent Kernel Theory?cited by 33
  13. 2021Learning with Gradient Descent and Weakly Convex Lossescited by 16
  14. 2020Benefit of deep learning with non-convex noisy gradient descent: Provable excess risk bound and superiority to kernel methodscited by 9
  15. 2017Fast Rates for Empirical Risk Minimization of Strict Saddle Problemscited by 7
  16. 2019An Exponential Efron-Stein Inequality for Lq Stable Learning Rulescited by 6
  17. 2021Nonparametric Regression with Shallow Overparameterized Neural Networks Trained by GD with Early Stoppingcited by 5

Built on by

Cited by year (2026 to 14 Oct)

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

26 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 36
  3. 2022Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problemscited by 25
  4. 2022Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networkscited by 21
  5. 2023Generalization and Stability of Interpolating Neural Networks with Minimal Widthcited by 21
  6. 2024Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizescited by 12
  7. 2023Generalization Guarantees of Gradient Descent for Multi-Layer Neural Networkscited by 9
  8. 2023Norm-based Generalization Bounds for Compositionally Sparse Neural Networkscited by 7
  9. 2024NTK-Guided Few-Shot Class Incremental Learningcited by 7
  10. 2024Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methodscited by 7
  11. 2025Stability and Generalization of Quantum Neural Networkscited by 3
  12. 2025Optimal Rates for Generalization of Gradient Descent for Deep ReLU Classificationcited by 3
14 more
  1. 2025On the Theory of Continual Learning with Gradient Descent for Neural Networkscited by 3
  2. 2022Black-Box Generalization: Stability of Zeroth-Order Learningcited by 1
  3. 2026Optimization, Generalization and Differential Privacy Bounds for Gradient Descent on Kolmogorov-Arnold Networkscited by 1
  4. 2026Sufficient Conditions for Stability of Minimum-Norm Interpolating Deep ReLU Networkscited by 1
  5. 2026Stochastic Gradient Descent with Momentum is Algorithmically Stablecited by 1
  6. 2023A Linearly Convergent GAN Inversion-based Algorithm for Reverse Engineering of Deceptionscited by 0
  7. 2023Towards Understanding the Generalizability of Delayed Stochastic Gradient Descentcited by 0
  8. 2024Bootstrap SGD: Algorithmic Stability and Robustnesscited by 0
  9. 2025Generalization and Optimization of SGD with Lookaheadcited by 0
  10. 2026Sequential Subspace Noise Injection Prevents Accuracy Collapse in Certified Unlearningcited by 0
  11. 2026Towards Initialization-dependent and Non-vacuous Generalization Bounds for Overparameterized Shallow Neural Networkscited by 0
  12. 2026Learning Theory of the SVRG: Generalization and Convergence Analysiscited by 0
  13. 2026Minimax-Optimal Generalization Bounds for Smooth Deep Neural Networks Trained by (Stochastic) Gradient Descentcited by 0
  14. 2026Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problemscited by 0