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

2021/07/27 by Dominic Richards, Ilja Kuzborskij, Richards, Dominic +1 · 4 citations
Computer Science · #Advanced Neural Network Applications #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Data Classification #Machine Learning and ELM #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.2107.12723

openalex publication_date 2021/07/27 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• Minimax-Optimal Generalization Bounds for Smooth Deep Neural Networks Trained by (Stochastic) Gradient Descent
• 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

• Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks
• Generalization Guarantees of Gradient Descent for Multi-Layer Neural Networks
• Minimax-Optimal Generalization Bounds for Smooth Deep Neural Networks Trained by (Stochastic) Gradient Descent
• Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methods
• How many Neurons do we need? A refined Analysis for Shallow Networks trained with Gradient Descent