Information-Theoretic Generalization Bounds for Stochastic Gradient Descent
This work addresses the theoretical understanding of generalization in SGD, which is crucial for machine learning practitioners, but it appears incremental as it builds on existing information-theoretic bounds.
The paper tackles the problem of understanding the generalization properties of stochastic gradient descent (SGD) for non-convex loss functions, providing upper bounds on generalization error that depend on local statistics like gradient variance and objective smoothness along the SGD path.
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.