On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning

Abstract

Generalization error (also known as the out-of-sample error) measures how well the hypothesis learned from training data generalizes to previously unseen data. Proving tight generalization error bounds is a central question in statistical learning theory. In this paper, we obtain generalization error bounds for learning general non-convex objectives, which has attracted significant attention in recent years. We develop a new framework, termed Bayes-Stability, for proving algorithm-dependent generalization error bounds. The new framework combines ideas from both the PAC-Bayesian theory and the notion of algorithmic stability. Applying the Bayes-Stability method, we obtain new data-dependent generalization bounds for stochastic gradient Langevin dynamics (SGLD) and several other noisy gradient methods (e.g., with momentum, mini-batch and acceleration, Entropy-SGD). Our result recovers (and is typically tighter than) a recent result in Mou et al. (2018) and improves upon the results in Pensia et al. (2018). Our experiments demonstrate that our data-dependent bounds can distinguish randomly labelled data from normal data, which provides an explanation to the intriguing phenomena observed in Zhang et al. (2017a). We also study the setting where the total loss is the sum of a bounded loss and an additional \ell_2 regularization term. We obtain new generalization bounds for the continuous Langevin dynamic in this setting by developing a new Log-Sobolev inequality for the parameter distribution at any time. Our new bounds are more desirable when the noisy level of the process is not small, and do not become vacuous even when T tends to infinity.

Published in ICLR 2020

References in corpus (11)

• On Exact Computation with an Infinitely Wide Neural Net
• A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Information-theoretic analysis of generalization capability of learning algorithms
• Fisher-Rao Metric, Geometry, and Complexity of Neural Networks
• Norm-Based Capacity Control in Neural Networks
• Poincaré and logarithmic Sobolev inequalities by decomposition of the energy landscape
• Data-Dependent Stability of Stochastic Gradient Descent
• Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz Augmentation
• A PAC-Bayesian Analysis of Randomized Learning with Application to Stochastic Gradient Descent
• Stability and Convergence Trade-off of Iterative Optimization Algorithms

Cited by in corpus (6)

• Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent
• Stability and Generalization of Stochastic Gradient Methods for Minimax Problems
• Stability of SGD: Tightness Analysis and Improved Bounds
• Improved Learning Rates for Stochastic Optimization
• Optimizing Information-theoretical Generalization Bounds via Anisotropic Noise in SGLD