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 additiona l`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 noise level of the processis not very small, and do not become vacuous even when T tends to infinity. Non-convex stochastic optimization is the major workhorse of modern machine learning. For instance, the standard supervised learning on a model class parametrized by R d can be formulated as the following optimization problem: where w denotes the model parameter, D is an unknown data distribution over the instance space Z, and F : R d × Z → R is a given objective function which may be non-convex. A learning algorithm takes as input a sequence S = (z 1 , z 2 , . . . , z n ) of n data points sampled i.i.d. from D, and outputs a (possibly randomized) parameter configurationŵ ∈ R d . A fundamental problem in learning theory is to understand the generalization performance of learning algorithms-is the algorithm guaranteed to output a model that generalizes well to the data distribution D? Specifically, we aim to prove upper bounds on the generalization error err gen (S) = L(ŵ, D) − L(ŵ, S), where L(ŵ, D) = Ez∼D[L(ŵ, z)] and L(ŵ, S) = 1 n n i=1 L(ŵ, z i ) are the population and empirical losses, respectively. We note that the loss function L (e.g., the 0/1 loss) could be different from the objective function F (e.g., the cross-entropy loss) used in the training process (which serves as a surrogate for the loss L). Classical learning theory relates the generalization error to various complexity measures (e.g., the VC-dimension and Rademacher complexity) of the model class. Directly applying these classical complexity measures, however, often fails to explain the recent success of over-parametrized neural networks, where the model complexity significantly exceeds the amount of available training data (see e.g., Zhang et al. (2017a) ). By incorporating certain data-dependent quantities such as margin and compressibility into the classical framework, some recent work (e.g., Bartlett et al. (2017) ; Arora et al. (2018) ; Wei & Ma (2019) ) obtains more meaningful generalization bounds in the deep learning context. An alternative approach to generalization is to prove algorithm-dependent bounds. One celebrated example along this line is the algorithmic stability framework initiated by Bousquet & Elisseeff (2002) . Roughly speaking, the generalization error can be bounded by the stability of the algorithm (see Section 2 for the details). Using this framework, Hardt et al. (2016) study the stability (hence the generalization) of stochastic gradient descent (SGD) for both convex and non-convex functions. Their work motivates recent study of the generalization performance of several other gradient-based optimization methods: Kuzborskij & Lampert (2018) ; London (2016); Chaudhari et al. (2017) ; Raginsky et al. (2017) ; Mou et al. (2018) ; Pensia et al. (2018) ; Chen et al. (2018) . In this paper, we study the algorithmic stability and generalization performance of various iterative gradient-based method, with certain continuous noise injected in each iteration, in a non-convex setting. As a concrete example, we consider the stochastic gradient Langevin dynamics (SGLD) (see Raginsky et al. (2017) ; Mou et al. (2018) ; Pensia et al. (2018) ). Viewed as a variant of SGD, SGLD adds an isotropic Gaussian noise at every update step: where g t (W t−1 ) denotes either the full gradient or the gradient over a mini-batch sampled from training dataset. We also study a continuous version of (1), which is the dynamic defined by the following stochastic differential equation (SDE): where B t is the standard Brownian motion.
We give some generalization error bounds of noisy gradient methods such as SGLD, Langevin dynamics, noisy momentum and so forth.
{"src": "scitldr-AIC_train", "paper_id": "SkxxtgHKPS"}