Information-Theoretic Generalization Bounds for Stochastic Gradient Descent

We study the generalization properties of the popular stochastic optimization\nmethod known as stochastic gradient descent (SGD) for optimizing general\nnon-convex loss functions. Our main contribution is providing upper bounds on\nthe generalization error that depend on local statistics of the stochastic\ngradients evaluated along the path of iterates calculated by SGD. The key\nfactors our bounds depend on are the variance of the gradients (with respect to\nthe data distribution) and the local smoothness of the objective function along\nthe SGD path, and the sensitivity of the loss function to perturbations to the\nfinal output. Our key technical tool is combining the information-theoretic\ngeneralization bounds previously used for analyzing randomized variants of SGD\nwith a perturbation analysis of the iterates.\n