# Generalization and Stability of Interpolating Neural Networks with Minimal Width

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 44 of its 58 references that are in the map.
- First posted on arXiv 18 Feb 2023.

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

- [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)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [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)
- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (2018)
- [Gradient Descent Maximizes the Margin of Homogeneous Neural Networks](https://mlsanity.com/paper/1906.05890/) (2019)
- [Norm-Based Capacity Control in Neural Networks](https://mlsanity.com/paper/1503.00036/) (2015)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss](https://mlsanity.com/paper/2002.04486/) (2020)
- [Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data](https://mlsanity.com/paper/1808.01204/) (2018)
- [Loss landscapes and optimization in over-parameterized non-linear systems and neural networks](https://mlsanity.com/paper/2003.00307/) (2020)
- [Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks](https://mlsanity.com/paper/1905.13210/) (2019)
- [Directional convergence and alignment in deep learning](https://mlsanity.com/paper/2006.06657/) (2020)
- [Towards moderate overparameterization: global convergence guarantees for training shallow neural networks](https://mlsanity.com/paper/1902.04674/) (2019)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [Linearized two-layers neural networks in high dimension](https://mlsanity.com/paper/1904.12191/) (2019)
- [Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel](https://mlsanity.com/paper/1810.05369/) (2018)
- [Theoretical insights into the optimization landscape of over-parameterized shallow neural networks](https://mlsanity.com/paper/1707.04926/) (2017)
- [An Improved Analysis of Training Over-parameterized Deep Neural Networks](https://mlsanity.com/paper/1906.04688/) (2019)
- [Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks](https://mlsanity.com/paper/1909.12292/) (2019)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [Convergence of Gradient Descent on Separable Data](https://mlsanity.com/paper/1803.01905/) (2018)
- [Stability and Generalization of Learning Algorithms that Converge to Global Optima](https://mlsanity.com/paper/1710.08402/) (2017)
- [Benign Overfitting in Two-layer Convolutional Neural Networks](https://mlsanity.com/paper/2202.06526/) (2022)
- [Risk and parameter convergence of logistic regression](https://mlsanity.com/paper/1803.07300/) (2018)
- [How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?](https://mlsanity.com/paper/1911.12360/) (2019)
- [Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks](https://mlsanity.com/paper/1910.01619/) (2019)
- [Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Data](https://mlsanity.com/paper/2202.05928/) (2022)

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

- [Implicit Bias of Spectral Descent and Muon on Multiclass Separable Data](https://mlsanity.com/paper/2502.04664/) (2025)
- [On the Optimization and Generalization of Multi-head Attention](https://mlsanity.com/paper/2310.12680/) (2023)
- [Implicit Bias and Fast Convergence Rates for Self-attention](https://mlsanity.com/paper/2402.05738/) (2024)
- [Generalization Guarantees of Gradient Descent for Multi-Layer Neural Networks](https://mlsanity.com/paper/2305.16891/) (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)
- [Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimization](https://mlsanity.com/paper/2303.10758/) (2023)
- [Select without Fear: Almost All Mini-Batch Schedules Generalize Optimally](https://mlsanity.com/paper/2305.02247/) (2023)
- [Fast Convergence in Learning Two-Layer Neural Networks with Separable Data](https://mlsanity.com/paper/2305.13471/) (2023)
- [Divergence of Empirical Neural Tangent Kernel in Classification Problems](https://mlsanity.com/paper/2504.11130/) (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)
- [Fine-grained Analysis of Non-parametric Estimation for Pairwise Learning](https://mlsanity.com/paper/2305.19640/) (2023)
- [Optimization, Generalization and Differential Privacy Bounds for Gradient Descent on Kolmogorov-Arnold Networks](https://mlsanity.com/paper/2601.22409/) (2026)
- [Stochastic Gradient Descent with Momentum is Algorithmically Stable](https://mlsanity.com/paper/2605.28517/) (2026)
- [Bootstrap SGD: Algorithmic Stability and Robustness](https://mlsanity.com/paper/2409.01074/) (2024)
- [Generalizability of Neural Networks Minimizing Empirical Risk Based on Expressive Ability](https://mlsanity.com/paper/2503.04111/) (2025)
- [Generalization and Optimization of SGD with Lookahead](https://mlsanity.com/paper/2509.15776/) (2025)
- [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)
- [Optimal Rates for Generalization of Gradient Descent Methods with Deep Neural Networks](https://mlsanity.com/paper/2606.06764/) (2026)

## Abstract (arXiv)

We investigate the generalization and optimization properties of shallow neural-network classifiers trained by gradient descent in the interpolating regime. Specifically, in a realizable scenario where model weights can achieve arbitrarily small training error ε and their distance from initialization is g(ε), we demonstrate that gradient descent with n training data achieves training error O(g(1/T)2 /T) and generalization error O(g(1/T)2 /n) at iteration T, provided there are at least m=Omega(g(1/T)4) hidden neurons. We then show that our realizable setting encompasses a special case where data are separable by the model's neural tangent kernel. For this and logistic-loss minimization, we prove the training loss decays at a rate of tilde O(1/ T) given polylogarithmic number of neurons m=Omega(log4 (T)). Moreover, with m=Omega(log4 (n)) neurons and T≈ n iterations, we bound the test loss by tildeO(1/n). Our results differ from existing generalization outcomes using the algorithmic-stability framework, which necessitate polynomial width and yield suboptimal generalization rates. Central to our analysis is the use of a new self-bounded weak-convexity property, which leads to a generalized local quasi-convexity property for sufficiently parameterized neural-network classifiers. Eventually, despite the objective's non-convexity, this leads to convergence and generalization-gap bounds that resemble those found in the convex setting of linear logistic regression.