Information-Theoretic Generalization Bounds for Stochastic Gradient Descent
arXiv:2102.00931
Abstract
We study the generalization properties of the popular stochastic optimization method known as stochastic gradient descent (SGD) for optimizing general non-convex loss functions. Our main contribution is providing upper bounds on the generalization error that depend on local statistics of the stochastic gradients evaluated along the path of iterates calculated by SGD. The key factors our bounds depend on are the variance of the gradients (with respect to the data distribution) and the local smoothness of the objective function along the SGD path, and the sensitivity of the loss function to perturbations to the final output. Our key technical tool is combining the information-theoretic generalization bounds previously used for analyzing randomized variants of SGD with a perturbation analysis of the iterates.
arXiv commentCOLT 2021
References in corpus (15)
- Neural Tangent Kernel: Convergence and Generalization in Neural Networks
- A Convergence Theory for Deep Learning via Over-Parameterization
- A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
- Information-theoretic analysis of generalization capability of learning algorithms
- Sharp Minima Can Generalize For Deep Nets
- The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning
- Privacy Amplification by Iteration
- Generalization in Adaptive Data Analysis and Holdout Reuse
- Norm-Based Capacity Control in Neural Networks
- A PAC-Bayesian Tutorial with A Dropout Bound
- Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?
- Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates
- Generalization bounds for deep convolutional neural networks
- Asymmetric Valleys: Beyond Sharp and Flat Local Minima
- On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithm