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

By Wenlong Mou, Liwei Wang, Xiyu Zhai. 2017

177 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

An Alternative View: When Does SGD Escape Local Minima? (2018, background): “For example, it is proved that noise helps to escape saddle points [7, 16], gives better generalization [9, 23], and also guarantees polynomial hitting time of good local minima under some assumptions [29].”
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, methodology): “Another line of algorithmdependent analysis of generalization (Hardt et al., 2015; Mou et al., 2017; Chen et al., 2018) used stability of specific optimization algorithms that satisfy certain generic properties like convexity, smoothness, etc.”
The Anisotropic Noise in Stochastic Gradient Descent: Its Behavior of Escaping from Minima and Regularization Effects (2018, background): “This indicates that it is not sufﬁcient to analyze SGD by treating it as an isotropic diffusion over landscape [22, 15].”
Generalization Error Bounds for Noisy, Iterative Algorithms (2018, methodology): “[12] provide generalization error bounds for SGLD by relating stability to the squared Hellinger distance and bounding the latter quantity.”
Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates (2019, methodology): “Using Monte Carlo simulation, we compared estimates of our expected generalization error bounds with (coupled) estimates of the bound from [21].”
Interplay Between Optimization and Generalization of Stochastic Gradient Descent with Covariance Noise (2019, methodology): “A closely-related approach to ours is the Stochastic Gradient Langevin Dynamics (SGLD) (Gelfand et al., 1992; Welling & Teh, 2011); a modiﬁcation of SGD where an annealed isotropic Gaussian noise is injected to the gradients.”
The Anisotropic Noise in Stochastic Gradient Descent: Its Behavior of Escaping from Sharp Minima and Regularization Effects (2018, background): “This indicates that it is not sufficient to analyze SGD by treating it as an isotropic diffusion over landscape (Zhang et al., 2017; Mou et al., 2017).”
Noise against noise: stochastic label noise helps combat inherent label noise (2021, methodology): “Following Wang et al. (2018), we yield CIFAR-10 with open-set noise by randomly replacing 40% of its training images with images from CIFAR-100. θ ( t ) .”
On the Power of Over-parametrization in Neural Networks with Quadratic Activation (2018, background): “A line of research tries to explain this phenomenon by studying the implicit regularization from stochastic gradient descent algorithm (Hardt et al., 2015; Pensia et al., 2018; Mou et al., 2017; Brutzkus et al., 2017; Li et al., 2017).”