Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints

Abstract

Algorithm-dependent generalization error bounds are central to statistical learning theory. A learning algorithm may use a large hypothesis space, but the limited number of iterations controls its model capacity and generalization error. The impacts of stochastic gradient methods on generalization error for non-convex learning problems not only have important theoretical consequences, but are also critical to generalization errors of deep learning. In this paper, we study the generalization errors of Stochastic Gradient Langevin Dynamics (SGLD) with non-convex objectives. Two theories are proposed with non-asymptotic discrete-time analysis, using Stability and PAC-Bayesian results respectively. The stability-based theory obtains a bound of $O\left(\frac{1}{n}L\sqrt{\beta T_k}\right)$, where $L$ is uniform Lipschitz parameter, $\beta$ is inverse temperature, and $T_k$ is aggregated step sizes. For PAC-Bayesian theory, though the bound has a slower $O(1/\sqrt{n})$ rate, the contribution of each step is shown with an exponentially decaying factor by imposing ${\ell }^2$ regularization, and the uniform Lipschitz constant is also replaced by actual norms of gradients along trajectory. Our bounds have no implicit dependence on dimensions, norms or other capacity measures of parameter, which elegantly characterizes the phenomenon of "Fast Training Guarantees Generalization" in non-convex settings. This is the first algorithm-dependent result with reasonable dependence on aggregated step sizes for non-convex learning, and has important implications to statistical learning aspects of stochastic gradient methods in complicated models such as deep learning.

References in corpus (9)

• Understanding deep learning requires rethinking generalization
• Train faster, generalize better: Stability of stochastic gradient descent
• How to Escape Saddle Points Efficiently
• Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis
• A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics
• The True Cost of Stochastic Gradient Langevin Dynamics
• Statistical Inference for Model Parameters in Stochastic Gradient Descent
• On the diffusion approximation of nonconvex stochastic gradient descent
• PAC-Bayesian Theory Meets Bayesian Inference

Cited by in corpus (25)

• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Stability and Convergence Trade-off of Iterative Optimization Algorithms
• Gram-Gauss-Newton Method: Learning Overparameterized Neural Networks for Regression Problems
• Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networks
• Shape Matters: Understanding the Implicit Bias of the Noise Covariance
• Generalization Error Bounds with Probabilistic Guarantee for SGD in Nonconvex Optimization
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent
• An Empirical Study of Large-Batch Stochastic Gradient Descent with Structured Covariance Noise
• PAC-Bayes Information Bottleneck
• On Stationary-Point Hitting Time and Ergodicity of Stochastic Gradient Langevin Dynamics
• Dynamic of Stochastic Gradient Descent with State-Dependent Noise
• The Impact of Local Geometry and Batch Size on Stochastic Gradient Descent for Nonconvex Problems
• On generalization bounds for deep networks based on loss surface implicit regularization
• Improved Learning Rates for Stochastic Optimization
• Stability of SGD: Tightness Analysis and Improved Bounds
• Learning with Gradient Descent and Weakly Convex Losses
• Characterizing Membership Privacy in Stochastic Gradient Langevin Dynamics
• Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks
• Laplacian Smoothing Stochastic Gradient Markov Chain Monte Carlo
• PAC-Bayesian Transportation Bound
• Time-Delay Momentum: A Regularization Perspective on the Convergence and Generalization of Stochastic Momentum for Deep Learning
• Generalisation under gradient descent via deterministic PAC-Bayes
• Distributed SGD Generalizes Well Under Asynchrony
• Towards Understanding Generalization via Decomposing Excess Risk Dynamics
• Distribution-Dependent Analysis of Gibbs-ERM Principle