Generalization and Stability of Interpolating Neural Networks with Minimal Width

2023/02/18 by Hossein Taheri, Christos Thrampoulidis, Taheri, Hossein +1 · 3 citations
Computer Science · #Advanced Neural Network Applications #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and ELM #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2302.09235

openalex publication_date 2023/02/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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)² /T) and generalization error O(g(1/T)² /n) at iteration T, provided there are at least m=Ω(g(1/T)⁴) 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 O(1/ T) given polylogarithmic number of neurons m=Ω(log⁴ (T)). Moreover, with m=Ω(log⁴ (n)) neurons and T≈ n iterations, we bound the test loss by O(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.

Cited by

• On the Theory of Continual Learning with Gradient Descent for Neural Networks
• Optimal Rates for Generalization of Gradient Descent for Deep ReLU Classification
• Generalization and Optimization of SGD with Lookahead

Related

• Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methods
• Stability & Generalisation of Gradient Descent for Shallow Neural Networks without the Neural Tangent Kernel
• How many Neurons do we need? A refined Analysis for Shallow Networks trained with Gradient Descent
• Approximation results for Gradient Descent trained Shallow Neural Networks in 1d
• Fast Convergence in Learning Two-Layer Neural Networks with Separable Data