Towards Understanding Generalization via Decomposing Excess Risk Dynamics

Abstract

Generalization is one of the fundamental issues in machine learning. However, traditional techniques like uniform convergence may be unable to explain generalization under overparameterization. As alternative approaches, techniques based on stability analyze the training dynamics and derive algorithm-dependent generalization bounds. Unfortunately, the stability-based bounds are still far from explaining the surprising generalization in deep learning since neural networks usually suffer from unsatisfactory stability. This paper proposes a novel decomposition framework to improve the stability-based bounds via a more fine-grained analysis of the signal and noise, inspired by the observation that neural networks converge relatively slowly when fitting noise (which indicates better stability). Concretely, we decompose the excess risk dynamics and apply the stability-based bound only on the noise component. The decomposition framework performs well in both linear regimes (overparameterized linear regression) and non-linear regimes (diagonal matrix recovery). Experiments on neural networks verify the utility of the decomposition framework.

Accepted by ICLR 2022

References in corpus (13)

• Understanding deep learning requires rethinking generalization
• Exploring Generalization in Deep Learning
• Spectrally-normalized margin bounds for neural networks
• Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints
• Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian
• Understanding Double Descent Requires a Fine-Grained Bias-Variance Decomposition
• Shape Matters: Understanding the Implicit Bias of the Noise Covariance
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses
• Information Complexity and Generalization Bounds
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression
• Understanding Generalization in Adversarial Training via the Bias-Variance Decomposition
• On the computational and statistical complexity of over-parameterized matrix sensing
• Stability of SGD: Tightness Analysis and Improved Bounds