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.

arXiv commentAccepted by ICLR 2022

References in corpus (31)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Understanding deep learning requires rethinking generalization
• Benign Overfitting in Linear Regression
• 2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization
• A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
• Exploring Generalization in Deep Learning
• Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Information-theoretic analysis of generalization capability of learning algorithms
• Matrix Completion has No Spurious Local Minimum
• Spectrally-normalized margin bounds for neural networks
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach
• Parallelizing Stochastic Gradient Descent for Least Squares Regression: mini-batching, averaging, and model misspecification
• Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints
• Optimistic Rates for Learning with a Smooth Loss
• Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms
• Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian
• Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margin
• 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
• Generalization Error Bounds with Probabilistic Guarantee for SGD in Nonconvex Optimization
• Information Complexity and Generalization Bounds
• The Implicit Bias of Depth: How Incremental Learning Drives Generalization
• 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
• Fast-rate PAC-Bayes Generalization Bounds via Shifted Rademacher Processes
• Stability of SGD: Tightness Analysis and Improved Bounds