Information-Theoretic Generalization Bounds for Stochastic Gradient Descent

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.

COLT 2021

References in corpus (5)

• Norm-Based Capacity Control in Neural Networks
• Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?
• Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates
• Asymmetric Valleys: Beyond Sharp and Flat Local Minima
• On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithm

Cited by in corpus (4)

• User-friendly introduction to PAC-Bayes bounds
• Information-theoretic generalization bounds for black-box learning algorithms
• Heavy Tails in SGD and Compressibility of Overparametrized Neural Networks
• Optimizing Information-theoretical Generalization Bounds via Anisotropic Noise in SGLD