On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning
Authors: Jian Li
Xuanyuan Luo
Mingda Qiao
Venue:  (2020)
Keywords: learning theory
generalization
nonconvex learning
stochastic gradient descent
Langevin dynamics

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 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.

Published as a conference paper at ICLR 2020
ON GENERALIZATION ERROR BOUNDS OF NOISY GRADIENT METHODS FOR NON-CONVEX LEARNING
Jian Li
Xuanyuan Luo Tsinghua University
Mingda Qiao 1 Stanford University
Tsinghua University
ABSTRACT
Generalization error (also known 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 Iearn- ing theory. In this paper, we obtain generalization eπror bounds for learning general non-convex objectives, which has attracted significant attention re- cent years. We develop a new framework, termed Snyes-Stabilitty for proving algorithmnddependnt generalization error bounds. The new framework combines ideas from both the PAC-Bayesian theory and the notion of algorithmic stabil- ity. Applying the Bayes-Stability method, we obtain new data-dependent gener- alization bounds for stochastic gradient Langevin dynamics (SGLD) and several other noisy gradient methods (c.g., with momentum, mini-batch and acceleration, Entropy-SGD). Our result recovers (and is typically tighter than) recent result in Mou et al. (018)) and improves upon the results in PPnssa et al. (2018). Our ex- periments 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 al. (2017a). We also study the setting where the total loss is the sum of bounded loss and an additional l regularization term. We obtain new generalization bounds for the continuous Langevin dynamic in this set- ting by developing new Log-Sobolev inequality for the parameter distribution at any time. Our new bounds are more desirable when the noise level of the process is not very small, and do not become vacuous even when T tends to infinity.
INTRODUCTION
Non-convex stochastic optimization is the major workhorse of modern machine learning. For in- stance, the standard supervised learning on a model class parametrized by Ee can be formulated as the following optimization problem:
min E. [F(,, =)] wERd 2DD
where w denotes the model parameter, DD is an unknown data distribution over the instance space 2, and F R x Z + I is given objective function which may be non-convex. A learning algorithm takes as input sequence = (21, ........ 2n. of n data points sampled i..d. from D, and outputs a (possibly randomized) parameter configuration i E Rdd
fundamental problem in learning theory is to understand the generalization performance of learn- ing algorithms- is the algorithm guaranteed to output model that generalizes well to the data distribution D? Specifically, we aim to prove upper bounds on the generalization error erTgen = L(ū,, D) - L(ú,S), where L(ú, D) = (Es= (ú. =)] and L(w, S) = 1 Σ L(ū,, 2;) 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 surrogate for the loss L).
IIjjia83 @ mail. tawilltsinhua.ccm edu.....ducnnn lluo-xy19 19@ mails. tsinghua.edu.cn mgian@ stanford.edu

---

Published as a conference paper at ICLR 2020
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 explain the recent success of over- 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., B.,,Barteett et al. (2017); [Arora ct al. (2018); Wei Ma (2019) obtains more meaningful generalization bounds in the deep learning context.
An alternative approach generalization is to prove algorithn-depenee example along this line is the algorithmic stability framework initiated by Bousquet & Elisseeff (2002). Roughly speaking, the generalization error can bounded by the stability of the algorithm (see Section for the details). Using this framework, HHardt 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 tradient-based optimization methods: Kuzborskij & Lampert (2018); London| (2016); Chaudhari et al. (2017): Ra-
bounds. One celebrated
ginsky 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 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 variant of SGD, SGLD adds an isotropic Gaussian noise at every update step:
W W (W Te ((, V2"
(1)
where ge (W, denotes either the full gradient or the gradient over mini-batch sampled from training dataset. We also study a continuous version of ( which the dynamic defined by the following stochastic differential equation (SDE):
dW, -VF(() di + 2 dB,,
where B, is the standard Brownian motion.
1.1 RELATED WORK
Most related to our work the study of algorithm-dependent generalization bounds of stochastic gradient methods. Hardt et al. (2016) first study the generalization performance of SGD via algorith- mie stability. They prove a generalization bound that scales linearly with T, the number of iterations, when the loss function is convex, but their results for general non-convex optimization are more re- stricted. London (017)) and Rivasplata et al. (2018) also combine ideas from both PAC-Bayesiag and algorithm stability. However, these works are essentially different from ours. In London 2017). the prior and posterior are distributions on the hyperparameter space instead of distributions on the hypothesis space. RRvasplata et al. (2018) study the hypothesis stability measured by the distance on the hypothesis space in a setting where the returned hypothesis (model parameter) is perturbed by Gaussian noise. Our work is a follow-up of the recent work by Mou et al. (2018), in which they provide generalization bounds for SGLD from both stability and PAC-Bayesian perspectives. Another elosely related work by Pensia et al. (2018) derives similar bounds for noisy stochastic gra- dient methods, based on the information theoretic framework of Xu & Raginsky (0017). However, their bounds scale as O (VTTn)) (n is the size of the training dataset) and are sub-optimal even for SGLD.
We acknowledge that besides the algorithm- in learning theory aim to explain the generalization performance of neural networks from many other perspectives. Some of the most prominent ideas include bounding the network capacity by the norms of weight matrices Neyshabur et al. (2015); Liang et al. (2019), ) margin theory [Bartlttt et al. 2017); Wei et al. (2019) PAC-Bayesian theory Dziugaite & Roy (2017); Neyshabur et al. (2018). 8); Dziugaite & Roy (0018), network compressibility Arora et al. (2018). and over wer-paramettrizttonn Du et al. (2019) Zou et al. (2018): Chizat al. (201)). Most of these results stated in the context of neural networks (some are tailored to networks with specific architecture),
approach that we follow, recent advances
et al. Allen-
whereas our work addresses generalization in non-convex stochastic optimization in general. We
2

---

Published as a conference paper at ICLR 2020
also note that some recent work provides explanations for the phenomenon reported in Zhang et al.
(017a)) from a variety of different perspectives (c.g.. Bartlett et al. 2017 Arora et al. (2018) 2019)
Welling & Teh (2011) first consider stochastic gradient Langevin dynamics (SGLD) as a sampling algorithm in the Bayesian inference context. Raginsky et al. (2017) give a asymptotit analysis approximate global minimum.
and establish the finite-time convergence guarantee of SGLD
Zhang et al. (2017b) analyze the hitting time of SGLD and prove that SGLD converges to an approx- imate local minimum. These results are further improved and generalized to family of Langevin dynamics based algorithms by the subsequent work of et al. (2018).
1.2 OVERVIEW OF OUR RESULTS
In this paper, we provide generalization guarantees for the noisy variants of several popular stochas- tic gradient methods.
The Bayes- method and data-dependent generalization bounds. We develop a new method for proving generalization bounds, termed as Bayes-Stabilie by incorporating ideas from the PAC- PAC-Bayesian theory into the stability framework. In particular, assuming the loss takes value in [o, C). our method shows that the generalization error bounded by both 2C Ex (2, Q=)l and 2C IE, (0 P)], where P is a prior distribution independent of the training set S, and Qx is the expected posterior distribution conditioned on on = 2 (i.e., the last training data is 2). The formal definition and the results can be found in Definition and Theorem
Inspired by Lever et al. (013), instead of using fixed prior distribution, we bound the KL- divergence from the posterior distribution dependent prior. This enables us derive the fol- lowing generalization error bound that depends on the expected norm of the gradient along the optimization path:
C n
err efTgen O
E
(o((t)
(3)
Here S the dataset and (t) Ew squared gradient norm at step f; see Theorem f the details.
F F 2, =) is the expected empirical
Compared with the previous O ( V
bound in Mouu et al. 2018 Theorem 1), where L the global Lipschitz constant of the loss, our new bound (3) depends on the data distribution and is typically tighter (as the gradient norm is most L). In modern deep neural networks, the worst- case Lipschitz constant can be quite large, and typically much larger than the expected empirical gradient norm along the optimization trajectory. Specifically, in the later stage of the training, the expected empirical gradient is small (see Figure ((d) for the details). Hence, our generalization bound does not grow much even if we train longer at this stage.
E
of)
Our new bound also offers an explanation to the difference between training on correct and random labels observed by Zhang et al. (2017a). In particular, we show empirically that the sum of expected squared gradient norm (along the optimization path) is significantly higher when the training labels are replaced with random labels (Section 3.1 Figure T. Appendix
We would also like to mention the PAC-Bayesian bound (for SGLD with fgrregularization) proposed by Mou et al. (2018). (This bound is different from what we mentioned before; see Theorem 2 in their paper.) Their bound scales as ( (R)) and the numerator of their bound has similar sum of gradient norms (with a decaying weight if the regularization coefficient À > O). Their bound is based on the PAC-Bayesian approach and holds with high probability, while our bound only holds in expectation.
Extensions. We remark that our technique allows for arguably simpler proof of (Mou et al. 2018 Theorem I); the original proof based on SDE and Fokker-Plann Planck equation. More importantly, our technique can be casily extended handle mini- mini-batches and variety of general settings as follows.
1. Extension to other gradient- based methods. Our results naturally extends to other noisy stochastic gradient methods including momentum due to Polyak (1964) (Theorem 26). Nes-
3

---

Published as a conference paper at ICLR 2020
terov's accelerated gradient method in Nesterov (1883) (Theorem 26 and Entropy-SGi
proposed by Chaudhari et al. (2017) (Theorem 27).
2. Extension to general noises. The proof of the generalization bound in Mou al. (2018) relies heavily on that the noise is Gaussiar which makes it difficult to generalize to other noise distributions such as the Laplace distribution. In contrast, our analysis easily carries over to the class of Liggchitchitz noises (i.e., noises drawn from distributions with Lipschitz log densities).
3. Pathwise stability. In practice, it is also natural to output certain function of the entire optimization path, e.g., the one with the smallest empirical risk or a weighted average. We show that the same generalization bound holds for all such variants (Remark T2p. We note that the analysis in an independent work of Pensia et al. (2018) also satisfies this property,
yet their bound is O (VC2L3n Σt= nl/ /o
(see Corollary in their work), which
scales at a slower (11 vn) rate (instead of O(1/n) when dealing with C-bounded loss
Generalization bounds with & regularization via Log-Sobolev inequalities. We also study the setting where the total objective function F is the sum of a C-bounded differentiable objective Fo and an additional f2 regularization term 2 quadratic function, and the continuous Langevin dynamics (CLD) is well understood for quadratic functions. We obtain two generalization bounds for CLD, both via the technique of Log-Sobolev inequalities, a powerful tool for proving the convergence rate of CLD, One of bounds is as follows (Theorem 15
À ||w] In this case, F can be treated as perturbation of a
2E CL
B (1 exp (-
XT e8pc
-
err gen
The above bound has the following advantages:
1. Applying e- > 1
I. one can see that our bound is at most O(vT/n), which matches
the previous bound in (Mou et al. 2018 Proposition 8
2. As time T grows, the bound is upper bounded by and approaches to 2 190 CL- (unlike the previous OVVT/n) bound that goes to infinity as T +00).
3. If the noise level is not so small (i.e., ,3 is not very large), the generalization bound is quite desirable.
Our analysis is based on Log-Sobolev inequality (LSI) for the parameter distribution time whereas most known LSIs only hold for the stationary distribution of the Markov process. We prove the new LSI by exploiting the variational formulation of the entropy formula.
PRELIMINARIES
Notations. We use DD to denote the data distribution. The training dataset S (21,..., 2n) is sequence of n independent samples drawn from D. S, E 2" are called neighboring datasets and only if they differ at exactly one data point (we could assume without loss of generality that Zn * 2.)) ). Let F F(w, z) and L(w, z) be the objective and the loss functions, respectively, where E Id denotes a model parameter and E Z is a data point. Define F(w, S) 1 Σ'= F(w,21 24) and F(w, D) Ez-D [(w, >)]: L(w, S) and L(w, D) are defined similarly. A learning algorithm A takes as input a dataset S, and outputs parameter E gd randomly. Let be the set of all B) denotes the collection of mini-batches that contain the n-th data point, while G = G \ G,,- Let diam(() s || vl12 denote the diameter of set A.
possible mini-batches G, [ E G
In particular, their proof leverages the Fokker-Planck equation, which describes the time evolution of the density function associated with the Langevin dynamics and can only handle Gaussian noise.
2 "They assume the loss Sab-Gaussinn. By Hoeffding's lemma, C-bounded random variables are sub- Gaussian with parameter
'The proof of their OVTT/n) bound be easily extended our setting with & regularization.
4

---

Published as a conference paper at ICLR 2020
Definition 1 (L-lipschitz). A function F IR Z R is L-lipschitz and only if F(W1,2) F(w2, 2)1 $ |ml1 Well2 holds for any w1, W2 E R and 2 Z.
Definition (Expected generalization error). The expected generalization error of learning algo- rithm A is defined as
ert erTgen
(errgen (S)) SmDD
-
S~D"
Algorithmic Stability. Intuitively, learning algorithm that is stable (i.e., small perturbation of the training data does not affect its output too much) can generalize well. the seminal work of Bousquet & Elisseeff (2002) (see also Hardt et al. (2016)). the authors formally defined algorith- mic stability and established close connection between the stability of a learning algorithm and its generalization performance.
Definition (Uniform stability). (Bousquet& & Elisseeff (2002) Elisseeff et al. (2005)) A randomized algorithm A 6n unniforrll stable w.r.t. loss for all neighboring sets S, S E 2", holds that
sup [al[((s, 2)] -EA[C(Ws: 2)]l Cu: ZEZ
where ws and wy denote the outputs of A on S and S' respectively.
Lemma 4 (Generalization in expectation). (Hardt et al. (2016)) Suppose a randomized algorithm A is e, -niiforrmy stable. Then, |errgenl S En-
BAYES-STABILITY METHOD
In this section, incorporate ideas from the PAC-Bayesian theory (see e.g.. Lever al. (2013) into the algorithmic stability framework. Combined with the technical tools introduced in previous sections, the new framework enables us to prove tighter data-dependent generalization bounds.
First, we define the posterior dataset and the posterior a single data point.
Definition 5 (Single-point posterior). Let Qs be the posterior distribution the parameter for given training dataset S = (Z1...., In other words. it is the probability distribution of the output of the learning algorithm on dataset S (e.g..for T iterations of SGLD in TT, Qs the pdf of WT). The single-point posterior ((i,)) is defined as
Q(122)
E
Q
For convenience, we make the following natural assumption on the learning algorithm:
Assumption (Order-independent), For any fixed dataset (21....,2z) and any permutation Qs is the same as Qsv, where 5" (2p1..... 2pa
Assumption 6 implics Q(1.z) = ... Q (m.z), so we use Q2 as a shorthand for Q(a.)) in the fol- lowing. Note that this assumption can be easily satisfied by letting the learning algorithm randomly permute the training data at the beginning. It is also easy to verify that both SGD and SGLD satisfy the order- indee--edeeendentt assumption.
Now, we state our new Bayes-stability framework, which holds for any prior distribution P over the parameter space that is independent of the training dataset S.
Theorem (Bayes-Stabilitty, Suppose the loss function L(w, =) is C-bounded and the learning al- gorithm order-independent (Assumption O Then for any prior distribution P not depending on S,
the generalization error is bounded by both 2C Ez /2KL(PP. Q=) and 2C 2C /2KL(QQ,, P))
Remark 8. Our Bayes-Stability framework originates from the algorithmic stability framework, and hence similar to the notions of uniform stability and leave-one-out error (see Elisseeff et al.) (2003)) However, there are important differences. Uniform stability is distribution-indeeeeee property, while Sayee-Stabillity can incorporate the information of the data distribution (through the prior P). Leave-one-out error measures the loss of learned model Bayes-Stabiliry focuses on the extent to which a single data point affects the outcome of the learning algorithm (compared to the prior).
unseen data point, yet
5

---

Published as a conference paper at ICLR 2020
To establish an intuition, first apply this framework to obtain expectation generalization bound for (full) gradient Langevin dynamics (GLD), which is special case of SGLD in (T) (i.e., GLD uses the full gradient V FW, S) as g. (W,,)).
Theorem 9. Suppose that the loss function L is C'bounded. Then we have the following expected generalization bound for T iterations of GLD:
2C
err erigen
E
72
SwDD
where (o(() Em- 1 E is the parameter at step t of GLD.
VF
2)2l is the empirical squared gradient norm, and W
Proof The proof builds upon the following technical lemma, which we prove Appendix A.2
Let (Wo...., Wr) and (W...., W be two independent sequences of random vari- ables such that for each t E {o.....T) T), W, and Wi have the same support. Suppose Wo and W follow the same distribution. Then,
Lemma 10.
KL(W ST. W
Σ
E wer
[W wee: WiIW's =wei)l
t=1
where Wee denotes (Wo.... W.) and Wet denotes Sst-1
Define p= Es- (s.o)) where denotes the zero data point (i.e., F(w, 0) 0 for any w).
Theorem 7 shows that
efTgen 2C V (K. P).
(5)
By the convexity of KL-divergence, for a fixed & E Z, we have
KL(Q,, KI. (.).
s E KL (Q 0(3,0))
3
Let (W))20 and (W)(2)) be the training process of GLD for (S,z) and (S, 0). re- spectively. Note that for a fixed was, both W,|W> wet and W W Wer Gaussian
distributions. Since KL(N((1, (L, N1,,,N o²)) 20
|p1-0213
(see Lemma 18 in Appendix A.2
KL(W, Wet = Wet, WilW'' = wee) = 2e V
ofn²
Applying Lemma 10 and KL(WT, W7) < KL(W <T, W' gives
T
KL(Qs, < n
E
[VF(w,))1
Recall that W 1 is the parameter at step t - using S = (S, 2) as dataset. In this case, we can rewrite & as 2n since it is the n-th data point of S. Note that SGLD satisfies the order-independent assumption, we can rewrite 2 as z; for all i E [n). Together with (5) (6) and using E Iz, S
E'L T., we can prove this theorem.
More generally, we give the following bound for SGLD. The proof is similar to that of Theorem the difference is that we need to bound the KL-divergence between two Gaussian mixtures instead of two Gaussians. This proof is more technical and deferred to Appendix
Theorem 11. Suppose that the loss function L is C-bounded and the objective function f is L- lipschitz. Assume that the following conditions hold:
1. Batch size b n/2

---

Published as a conference paper at ICLR 2020
2. Learning rate " o2/()))).
Then, the following expected generalization error bound holds for T iterations of SGLD
8.12C
T
ert gon
E SrrD
Σ
Ba(()
(empirical norm)
n
where (e(t) = Be---.lll E is the parameter step of SGLD.
VF((,, 2) is the empirical squared gradient norm, and W
Furthermore, based on essentially the same proof, we can obtain the following bound that depends on the population gradient norm:
T
8.12C
erTgen
E 9'
E LanD
IIF (w, 2)1
n
A The full proofs of the above results are postponed to Appendix and we provide some remarks about the new bounds.
Remark 12. fact, our proof establishes that the above upper bound holds for the two se- 2
" quences Wer and W'sr KL(Wer, W'Sr) 5,12 ET of go()). Hence, our bound holds for any sufficiently regular function over the parameter sequences: (W S
22 12 Et= of (t). In particular, eral variants of SGLDD such as outputting the average of the trajectory, the averuge of the suffix of certain length, the exponential moving average.
generalization error bound automatically extends to sev-
Remark 13 brobb-probbbility bounds). By relaxing the expected squared gradient norm term to L and using the uniform stability framework, our proof can be adapted recover the OLLCvT /n) bound in Mou et al.) 2018 Theorem 1). Then, we can apply the recent results of Feldman & Vondrak (2019) to provide generalization error bound of D(CC///i + 1/ //) that holds with high probability. (Here Ô hides poly-togarithmic factors.) When T is at least linear in the additional l//n term is not dominating.
3.1 EXPERIMENT
Distinguish random from normal. Inspired by Zhang et al. (2017a), we run both GLD (Figure T and SGLD (Appendix C.2 to both normal data and randomly labeled data (see Appendix for more experiment details). As shown in FigureTant and Figure i Appendix C.2 a larger random label portion p leads to both much higher generalization error and much larger generalization error bound. Moreover, the shapes of the curves of our bounds look quite similar those of the generalization еггоr curves.
Note that in (b) and (c) of Figure [ the scales in the y-axis are different. We list some possible reasons that may explain why our bound larger than the actual generalization error. (1) as we explained in Remark 12 our bounds (Theorem 9 and 11) hold for any trajectory-basee output. and are much stronger than upper bounds for the last point on the trajectory. (2) The constant we can prove Lemma 21 may not be very tight. (3) The variance of Gaussian noise of is not large enough in our experiment. However, if we choose a larger variance, fitting the random labeled training data becomes quite slow. Hence, we use a small data size
10000) for the above reason. We also run an extra experiment for GLD on the full MNIST dataset (n 60000) without label corruption (see Figure 2 in the Appendix C We can see that our bound non-vacuous (since SLD-wwich computes the full gradients took long time converge, stopped when achieved 90% training accuracy).
We highlight another difficulty proving non- vacuouu generalization emrr bounds when the data are randomly labeled. Consider a 10-class classification setting where all the labels are random. For any sufficiently small data size, there is always a deep neural network that perfectly fits the dataset. Thus, the training error is zero while the population error is 90%. In this case, any valid generalization emror bound should he larger than 0.9. Then, the theoretical hound would still he vacuous if is only loose by factor of 2.

---

Published as a conference paper at ICLR 2020
training accurscy
0.8-
p
p-0
0.8
p=0.25
p=0.25
grddent
generallean
p-0.5
p+0
6.4-
p=:0.75
ampprit
10
p=0.75
0.4
0.2
p=0.75
100
10fstop
10"step
10'step
10'step
(a)
(b)
(c)
(d)
Figure 1: Training MLP with GLD (a, = m.) on smaller version of MNIST with different random label portion p. (a) shows the training aceuracy. (b) shows the generalization error, i.e., the gap between the 0/1 loss f the training data and on the test data. (c) plots our bound in Theorem 9 (d) shows that for p = 0, the gradient norms become much smaller at later stages of training.
Relax the step size constraint. in the practical use We provide several ways to relax this constraint:
The condition on step size in Theorem 11 may seem restrictive
1. The proof of Theorem max;e|n] [ 122 in the constraint.
still goes through if we replace L with
2. The maximum gradient norm can be controlled by gradient clipping, i.c. multiplying min(CL..lVVF((W_....).)) to each VF(W)-1,2))
|VF(W
3. Replacing the constant with in this constraint will only increase the constant of our bound from 8.12 to 84.4.
We also provide an experiment combining the above ideas to make our Theorem applicable in the practical use (see Figure in Appendix C
4 GENERALIZATION OF CLD AND GLD WITH & REGULARIZATION
In this section, we study the generalization error of Continuous Langevin Dynamics (CLD) with & regularization. Throughout this section, assume that the objective function training set S is defined as F(w, 8) Fo(w, || 2. and moreover, the following assumption holds.
Assumption 14. The loss function L and the original objective Fo are C-bounded. Moreover, Fo is differentiable and L-lipschitz.
The Continuous Langevin Dynamics is defined by the following SDE:
dw, FWW,, S) dt 2 dB,, Wo Mu:
(CLD)
where (Bt)2a is the standard Brownian motion on Id and the initial distribution Ao is the centered Gaussian distribution in d with covariance * Ig. We show that the generalization error of CLD is
upper bounded by O ( (A30n=1/B/// which is independent of the training time T (Theorem 15
Furthermore, T' goes infinity, we have tighter generalization error bound O (3 (The- orem 39 in Appendix B). We also study the generalization of Gradient Langevin Dynamics (GLD), which is the discretization of CLD:
W k++1 WR VWW S) 22 Ex.
(GLD)
where Et. is the standard Gaussian random vector in Rdd By leveraging a result developed Ragin- sky et al. (2017). we show that, as Kry² tends to zero, GLD has the same generalization as CLD (see Theorems 15 and 39). We first formally state our first main result in this section.
"The condition 7. O(7./ T.) is also required in Mou
2018 Theorem 1)
8

---

Published as a conference paper at ICLR 2020
-A
Theorem 15. Under Assumption 14 CLD (with initial probability measure dpo ze has the following expected generalization error bound:
dw)
2EAB0 CL Vx (1 cxp (-
XI ))
CIT
In addition, if L is M-smooth and non-negative, by setting XB > 2, >> 0 and [0.1A rrunning K iterations with the same po as CLD) has the expected generalization error bound:
8M
GLD
2C grr SC 22C/2
B VX
(111
AnnK e,30
exp
(8)
where 11 is a constant that only depends on M, X, 3. b, and d.
The following lemma is crucial for establishing the above generalization bound for CLD In partic- ular, we need to establish a Log-Sobolev inequality for ft, the parameter distribution at time i, for every time step > In contrast, most known LSIs only characterize the stationary distribution of the Markov process, The proof of the lemma can be found in Appendix B
Lemma 16. Under Assumption 24 let pt be the probability measure of W, in CLD (with dua
-Allwi? dw). Let v be a probability measure that is absolutely continuous with respect to pa. Suppose du4 = (e(w) dw and dv ((w) dw. Then, it holds that
KL(Y,T)) exp(83C)
7(w) Te. (w)
V log
(w) dw.
2A3
Rd
We sketch the proof Theorem and the complete proof relegated to Appendix
Proof Sketch of Theorem 15 Suppose S and S' are two neighboring datasets. Let (W,) and (W)) be the process of CLD running on S and S", respectively. Let Y and ne be the pdf of W and Wr Let (w) denote F(w, S). We have
KL KL T()
-1
V log
2
dw
log Vo
Tt VFs VFss dw
3 JRd
Tt
2
Rd
n
-1
Yt
V log
71t
dw
+
B
It V
V 12 dw.
2,3 Rd
T
RRd
2,322
KL KL
(Tts nT))
(Lemma [6]
n Solving this inequality gives KL(Y,, m.) S
83C
X00/ Hence the generaliza-
n
tion error of CLD can bounded by 20' (YT, Tr). which proves the first part. The second
part of the theorem follows from Lemma 36 in Appendix B
Our second generalization bound for CLD
Theorem
39 in Appendix B
is
83C2
-XT
erTgen
4C exp
eBC
BC.
n
The high level idea to prove this bound very similar to that in Raginsky et al. (2017). We first observe that the (stationary) Gibbs distribution μ has small generalization error. Then, bound the distance from je to In our setting, we can use the Holley-Stroock perturbation lemma which allows us to bound the Logarithmic Sobolev constant, and we can thus bound the above distance easily.
5 FUTURE DIRECTIONS
In this paper, we prove new generalization bounds for variety of noisy gradient- based methods. Our current techniques only handle continuous noises for which bound the KI.-divergence.

---

Published as a conference paper at ICLR 2020
One future direction is to study the discrete noise introduced in SGD (in this case the KL-divergence may not be well defined). For either SGLD or CLD, if the noise level is small (i.e., 8 is large), it may take long time for the diffusion process to reach the stable distribution. Hence, another interesting future direction is to consider the local behavior and generalization of the diffusion process in finite time through the techniques developed in the studies of metastability (see e.g., (B-vir et al. (2005); Bovier & den Hollander (2006); Tzen et al. (2018)) In particular, the technique may be helpful for further improving the bounds in Theorems 15 and 39 (when ' very large).
ACKNOWLEDGEMENT
We would like to thank Liwei Wang for several helpful discussions during various stages of the work. The research is supported in part by the National Natural Science Foundation of China Grant 61822203, 61772297, 61632016, 746013, and the Zhongguancun Haihua Institute for Frontier Information Technology and Turing Al Institute of Nanjing.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameter- ized neural networks, going beyond two layers. In Advances in Neural Information Processing Systems (NeurIPS), pp. 6155-6166, 2019.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via compression approach. International Conference on Machine Learning (ICML), pp. 263, 2018.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Advances Neural Information Processing Systems (NeurIPS), pp. 8139-8148, 8148, 2019.
Dominique Bakry, Ivan Gentil, and Michel Ledoux. Analysis and geometry of Markov diffusion operators, volume 348. Springer Science &amp; Business Media, 2013.
Peter L Bartlett, Dylan J Foster, and Matus Telgarsky. Spectrally- normalized margin bounds for neural networks. In Advances in Neural Information Processing Systems (NeurIPS), pp. 6240- 6249, 2017.
Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of Machine Learning Research (JMLR), 2:499-526, 2002.
Anton Bovier and Frank den Hollander. Metastability: a potential theoretic approach. In Interna- tional Congress of Mathematicians, volume 3, pp. 499-518. Eur. Math. Soc. Zürich, 2006.
Anton Bovier, Véronique Gayrard, and Markus Klein. Metastability in reversible diffusion processes ii: Precise asymptotics for small eigenvalues. Journal of the European Mathematical Society, (1):69-99, 2005.
Pratik Chaudhari, Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Christian Borgs, Jennifer Chayes, Levent Sagun, and Riccardo Zecchina. Entropy-SGD: Biasing gradi- ent descent into wide valleys. International Conference on Learning Representations (ICLR), 2017.
Yuansi Chen, Chi Jin, and Bin Yu. Stability and convergence trade-off of iterative optimization algorithms. arXiv preprint
2018.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. In Advances in Neural Information Processing Systems (NeurIPS), pp. 2933-29922 2943, 2019.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning (ICML), pp- 1675-1685, 2019.
John Duchi. Derivations for linear algebra and optimization. Berkeley, California, 3, 2007.
10

---

Published as a conference paper at ICLR 2020
Gintare Karolina Dziugaite and Daniel Roy. Entropy-SCe -aropyy-GDDa. optimizes the prior of PAC-Bayes bound: Generalization properties of entropy- SSD and data data-dependent priors. In International Conference on Machine Learning (ICML), pp. 1377-1386, 2018.
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Uncertainty in Artificial Intelligence (UAI), 2017.
André Elisseeff, Massimiliano Pontil, et al. Leave-one-out ertor and stability of learning algorithms with applications. NATO science series sub series ii computer and systems sciences, 190:111- 130, 2003.
Andre Elissefff, Theodoros Evgeniou, and Massimiliano Pontil. Stability of randomized learning algorithms. Journal of Machine Learning Research (JMLR), 6(Jan):55-79, 2005.
Vitaly Feldman and Jan Vondrak. High probability generalization bounds for uniformly stable al- gorithms with nearly optimal rate. In Conference on Learning Theory (COLT), pp. 1270-1279, 2019.
Moritz Hardt, Benjamin Recht, and Yoram Singer. Train faster, generalize better: stability of stochastic gradient descent. In International Conference Machine Learning (ICML), pp. 1225- 1234, 2016.
2016.
Richard Holley and Daniel Stroock. Logarithmic sobolev inequalities and stochastic ising models. Journal of statistical physics, 46(5):1 159-11944 1987.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Tech- nical report, Citeseer, 2009.
Alex Krizhevsky, Nya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in Neural Information Processing Systems (NeurIPS), pp. 1097-1105, 2012.
Iija Kuzborskij and Christoph Lampert. Data-dependent stability of stochastic gradient descent. In International Conference Machine Learning (ICML), pp. 2815-2824, 2018.
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, al. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 1):2278-223333 2324, 1998.
Guy Lever, François Laviolette, and John Shawe-Taylor. Tighter pac-bayes bounds through distributionnddeeendent priors. Theoretical Computer Science, 473:4-28, 2013.
Tengyuan Liang, Tomaso Poggio, Alexander Rakhlin, and James Stokes. Fisher-rao metric, geome-
try, and complexity of neural networks. In International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 888-896, 2019.
Ben London. Generalization bounds for randomized learning with application to stochastic gradient descent. In NIPS Workshop Optimizing the Optimizers, 2016.
Ben London. A pac-bayesian analysis of randomized learning with application stochastic gradient descent. In Advances in Neural Information Processing Systems (NeurIPS), pp. 2931-29400 2017.
Georg Menz, André Schlichting, et al. Poincaré and logarithmic sobolev inequalities by decompo- sition of the energy landscape. The Annals of Probability, 42(5): 2014.
Wenlong Mou, Liwei Wang, Xiyu Zhai, and Kai Zheng. Generalization bounds of SGLD for non- convex learning: Two theoretical viewpoints. In Conference on Learning Theory (COLT), pp. 605-638, 2018.
Yurii E Nesterov. A method for solving the convex programming problem with convergence rate O(1/k²). In Dokl. Akad. Nauk SSSR, volume 269, pp. 543-547, 1983.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory (COLTT), pp. 1376-1401, 2015.
11

---

Published as a conference paper at ICLR 2020
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nathan Srebro. A PAC-Bayesian approach to spectrally- normalized margin bounds for neural networks. In International Confer- ence on Learning Representations (ICLR), 2018.
Grigorios Pavliotis. Stochastic processes and applications: diffusion processes, the Fokker-Planck and Langevin equations, volume 60. Springer, 2014.
Ankit Pensia, Varun Jog, and Po-Ling Loh. Generalization enror bounds for noisy, iterative algo- rithms. In International Symposium on Information Theory (ISIT), pp. 546-550, 2018.
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. USSR Com- putatiooal Mathematics and Mathematical Physics, 4(5):1-17, 1964.
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gra- dient langevin dynamics: nonasymplotic analysis. In Conference Learning Theory (COLT), pp. 1674-1703, 2017.
Hannes Risken. Fokker-planck equation. In The Fokker-Planck Equation, pp. 63-95. Springer, 1996.
Omar Rivasplata, Csaba Szepesvári, John S Shawe-Taylor Emilio Parrado- Hernandez, and Shiliang Sun. Pac-bayes bounds for stable algorithms with instance-dependent priors. In Advances in Neural Information Processing Systems C (NeurIPS), pp. 9214-9224, 2018.
Parrado-Hernnndez
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initializa- tion and momentum deep learning. In International Conference on Machine Learning (ICML), pp. 1139-1144 1447, 2013.
Flemming Topsoe. Some inequalities for information divergence and related measures of discrimi- nation. IEEE Transactions on Information Theory, 46(4):1602-1609 2000.
Belinda Tzen, Tengyuan Liang, and Maxim Raginsky. Local optimality and generalization guaran- tees for the langevin algorithm via empirical metastability. In Conference On Learning Theory (COLT), pp. 857-875, 2018.
Colin Wei and Tengyu Ma. Data-dependent sample complexity of deep neural networks via lipschitz augmentation. In Advances Neural Information Processing Systems (NeurIPS), pp. 9722-9733, 2019.
Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets vs their induced kernel. In Advances in Neural Information Processing Systems (NeurIPS), pp. 9709-9721, 2019.
Max Welling and Yee W Teh. Bayesian learning via stochastic gradient langevin dynamics. In International Conference on Machine Learning (ICML), pp. 681-688, 2011.
Aolin Xu and Maxim Raginsky. ceemmation--heoretii analysis of generalization capability of learn- ing algorithms. In Advances in Neural Information Processing Systems (NeurIPS), pp. 2524- 2533, 2017.
Pan Xu, Jinghui Chen, Difan Zou, and Quanquan Gu. Global convergence of langevin dynamics based algorithms for nonconvex optimization. In Advances in Neural Information Processing Systems (NeurIPS), pp. 3126-3137, 2018.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. International Conference on Learning Rep- resentations (ICLR), 2017a
Yuchen Zhang. Perey Liang, and Moses Charikar. A hitting time analysis of stochastic gradient langevin dynamics. In Conference on Learning Theory (COLT), pp. 1980-2022, 2017b.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks. arXiv preprint arX.v:1811.08888, 2018
12

---

Published as a conference paper at ICLR 2020
A PROOFS IN SECTION 3
A.1 SAYES-STARILITY FRAMEWORK
Lemma 17. Under Assumption O for any prior distribution P not depending the dataset $ (Z : Zn), the generalization error upper bounded by
E.
L(w,
L(w,z) 2)
EE
E wepp
((w)
L(w))
w-
w
where ((w) denotes the population loss L(w, D).
Proof of Lemma 17
Let erTtrain Es Eu L(w, S) and erf
Es Bu L(w). We can
rewrite generalization enror as erTgen = efflest elitrains where
test
E
E
[(w) = E E ((w) u
(Assumption 6
Q1.0)
(Q+(w) P(w))((() dw + / P(w) dw. Rd
/
and
elTtrain
E L(w, 2i)
11
S wo
((w, = E L(w, Z um-Q=
(Assumption 6
n
w ((.a)
E / (Q+(w) P(w))L(w, 2) dw + P(w) E L(w, 2) dw JRd
(P is prior)
JRd
= E Rd
(Q.(w) P(w)) 2) dw + P(w) dw.
(definition of f(w))
Thus, we have
Jerrgenl
|erttest
elTtrain
(Q:(w) - ((w)))((w) dw -E / (Q=(w) P(w))L(w,, 2) dw
Rd
Rdd
E
E W.QQ
L(w,z)- - E wap
[(w, 2)
+ E E
((w)
E wPp
((w))
=w
Now we are ready to prove Theorem 7 which we restate in the following.
Theorem (Bayes-Stabilityy) Suppose the loss function L(w, =) is C-bounded and the learning al- gorithm order-inden inder-independent (Assumption 66. then for any prior distribution not depending on S,
the generalization error is bounded by both 2C Ez /2KL(P, Qz) and 2C E, (2KLL(Q2, P)
Proof By Lemmal
erTgen
E
E L(w, 2)
E
L(u, =)
+
E L(w) E ((w) maap
w>Q=
w
(2C TV Q+) 2C TV(P, Qz)]
(C-boundedness)
V (KL(P.Q.)
< 4CE
(Pinsker's inequality)
The other bound follows from similar argument.
13

---

Published as a conference paper at ICLR 2020
A.2 TECHNICAL LEMMAS
Now we turn to the proof of Theorem 11 The following lemma allows us to reduce the proof of algorithmic stability the analysis of single update step.
Lemma 10. Let (Wo.... WT) and (Wo.... W/ be two independent sequences of random vari- ables such that for each & ; T.). W, and Wi have the same support. Suppose Wo and W follow the same distribution. Then,
KL(W ST, WST)
Σ
E
KK[W,
= wen. Wi|W" =wa)).
1=1 Wer~Wer
where Wet denotes oW....., ..) and Wet denotes Ws--1
Proof By the chain rule of the KL-divergence,
KL(W St w)) = KL(W<a <t: W +
E Wer-Wa
WKL web WiIl' =ee)]
The lemma follows from a summation over =1,.... T.
The following lemma (see e.g., (Duchi 2007 Section 9)) gives a closed-fome formula for the KL- divergence between two Gaussian distributions.
Lemma 18. Suppose that P = (N Σn) and Q = NN2,, Σz) are two Gaussian distributions on Fd Then,
" T 141) - d det (Σ2)
(P,( = (r( E1) + (12 m1)
det (E1)
The following lemma (Topsoe 2000
Theorem 3) helps us upper bound the KL-divergence.
Definition 19. Let P and Q be two probability distributions on Rd. The directional triangular discrimination from P to Q is defined as
A (P.Q) Σ 2 P (1
where
APP(Q== (P(w) Q(w))
P(w) Q(w) dw.
Lemma 20. For any probability distributions P and Q Rd
KL(P,Q) < ln2 (P,Q).
Recall that G is the set of all possible mini-batches. G₁ = (B G B) denotes the collection of mini-batches that contain while G, G G,- diam(A) sup x yll denotes the diameter of set A. The following technical lemma upper bounds the KL-divergence between two Gaussian mixtures induced by sampling mini-batch from neighbouring datasets.
Lemma 21. Suppose that batch size b < n/2. {NB B E G} and {H'g B E G} are two collections of points in IRd labeled by mini matchhatches of size that satisfy the following conditions for some constant o):
1. ||B - -'gll S for E Gn and μB =1 f'r B E G.,
2. diam((pB B G) U B E G}) < 6/10.
o² Id). Let P 3 P and P Let Pu,o denote the Gaussian distribution N(p, 2
[al
о EBEG o be two mixture distributions over all mini-batches. Then,
1
8.2317 82
KL(P,P)) <
14

---

Published as a conference paper at ICLR 2020
Proof of Lemma 21 By Lemma 20
KL(P, P') is bounded by
+00
In2 (P,P) = In2
2
A 422 (1-22++1)))
k=
+00
(P(() P -
= In 2 Σ
2
dw.
2 (2 22 P(m))
Rd
k=0
The numerator of the above integrand is upper bounded by
4 4 p-)2 =
(Pugio Prig,o)
G
BEG
4 G 12
(Punio Pr(g.o)
|G|2
|Gnl BEG.
4 k-b
(Pue.o - Pwnn))?
n²
|G
BEG..
while the denominator be lower bounded follows:
2 2-k
2 2-2 2-h
2 2 p + 22-2
Z
Σ Pun.o
+
Σ Punn
G
|G|
BEG
BEG,
Pug.o
(JB = 1t'3 for B E Ga)
G
BEG
2(n b)
Σ Ppa.o
G
n
BEG,
Ppn.or
(b n/2)
G
BEGn
which implies, by the convexity of 1/x, that
(10)
2 k (2 2 pM
EBE Pugi
G
Pun.o
Gr
BEGa
Inequalities p and 10 together imply
4 R2
(Pun.o (w) Pw (w))²
A (2 k p +
(1-21-2
2
p 'p,
P') n Grl
Σ Σ AEG. BEG
dw.
JRd (w)
(11)
Now we bound the right-hand side of (TT) for fixed A and B. By applying translation and rotation, we can assume without loss of generality that μд = 0, and the last 2 coordinates of μB and Llg are all zero. Note that the integral is unchanged when project the space the two- dimensional subspace corresponding to the first two coordinates. Thus, it suffices to prove a bound
for d = 2. We rewrite (11
4-412
A(2*PP((1-2-))) P') <
Σ
dw.
n² G Gml
T B32
AEG,, BEG.,
(12)
15

---

Published as a conference paper at ICLR 2020
Let be the integral in the right-hand side of (12). Note that
Ai
Miee
S 0.1 and
g Let 5
0 and
|| -uu
Our goal is to bound max
(18-2)
Let (x) max((x,0) 0).
Since
ma to. -
I I
2
2x dr.
We have
1
(e-v² - (u+
max 6e/0,0.1|
I 0²
c"
2Tr
max ve((n-0.1) ,+ 6c
max
dr.
62
0
82
Let o(y, 6) - -e (u+a} )2, we make two claims which we will prove later:
1. For all y, 8 2 0, Φ 0) E.
2. For all y 2 /2' ply, 8) is non-increasing in 6.
The above claims imply that:
1. For any E 0, 52 + +.1.]. max mmx.g(--aj..-011000000l./ 2.
2. For any r E
v2 + 0.1, +01,, +00).
we have
[ o(y s
max
max
lim (o 8)] 8-00
(e1()-0.1) -.0t--00))++.1111
4yye 2v²
yEl(r- (.16--01)--00 0+0.1]
= 4(r 2
The last step holds since + e-2e-2j is decreasing on
1 +00) V2
Thus we have
2
/
3/2 +0.1
2nT 2"22Tr
2
dr +02
+00
c"
2Tr - 1(r - (0.1) 2(1- - dr
max 0
82
V2 +0.
18.648702
Plugging the above into 12 gives
k-2 n²02T
4-bb2 (1/82)
21 PT)
8²
max
< n²m 18.648762.
6E(0.0.
We conclude that
+00
KL(P,P') < 2n2
Σ 2*
A(2 k + (1- 21- pt)
k=U
37. 37.2974/ In
8,2362,3
n²
n²o²
Finally, we prove the two claims used above:
1. For all y. 5 2 0, let h(x) -== we have v² e11+-)) Syts l((t) dt. Since
[/(t)] = le +² (-2t) = ( Let (1((t)) = 0, we have t = 1/v2. Thus, [W((t)) s
e2/2 and e 3² e- ((rt)) I /2/eee
2. Suppose y 2 1/ 22, we have
e
e (y+5)
(u+o)²
(2yo + 28 + 1) - wv
05
8
82
[e 2yp 2yō 5² (2yō + 282 + 1) 1].
82
Let 8) -206-82 1206-8(228 282 + 1) 1. Note that
16

---

Published as a conference paper at ICLR 2020
(a) limg 36 [ -e (04-6 0.
(b) & (1/V2,,00) -4e 8(6+ -4e--666+ -2 v2) < and g(1/v2,0) =
It implies that 06
(--1//a)) - -
6
for > 0. Since 2 gy.
=
1822--86422) + y) < for y 2 0, we conclude that for any y 1/v2:
0 x²
e (v+62²
(L/v222) -e-1222++
S
08
06
A.3 MAIN THEOREM
Recall that SGLD on dataset S is defined as
We t Wt1 - -/ FW
0t V2"
NO, Ia).
Here "tt is the step size. B, fii..... } is subset (I. of size b, and SB. (Zirs..., 24, is the mini-batch indexed by Be. Recall that F(w, 8) denotes 1े E! F(w, 24). We restate and prove Theorem M in the following.
Theorem 11. Suppose that the loss function C is C-bounded and the objective function F is L- lipschitz. Assume that the following conditions hold:
1. Batch size S n2/2.
2. Learning rate " S (20L)
Then, the following expected generalization error bound holds for T iterations of SGLD
8.12C
T
erT
E
ge
(t)
(empirical norm)
n
Sm2n
o
where ge(t) EwwW,-i 11 E
[V 2)1l is the empirical squared gradient norm, and Wa
nn is the parameter at step L of SGLD.
Proof By Theorem we have
err gon 2C VCL(2KL
(13)
for any prior distribution P. In particular, we define the prior as P(w) EznD" (Pps(w)), where Py(w) Q(3.o) By the convexity of KL-divergence.
KL(Q,, P) = KI. KI. BQQ E(Q 3
x
KL (03.0))
(14)
Z. Let (W.):20 and (W)) be the training process of SGLD for S (S, 2) and S' (S, 0), respectively. Fix time step and wet (Wo.... .... wt-1). Let and P. denote the distribution of W, and W/ conditioned on Wze = Wet and W = wer, respectively. By the I EBEG Pr where μB wi-1
Fix data point
definition of SGLD, we have Pt te (w: p'B wt-1 7t V F. FwWW-WWW SB), and p, denotes the Gaussian distribution of (u, 2 Ta). We note that:
[c| Σ Pan and P/ = c
1
1. 1/4 -1 < 7el VF( 1.=) for B E Gn and μn 1'/ for B E G..-
17

---

Published as a conference paper at ICLR 2020
2. tiam((/4 B G) U (uB: B E G)) < 2nL 01/10.
By applying Lemma 21 with 3 The F and 0 = dt,
8.2372 VF
KL(P,,PD) S
o7n1²
By Lemma 10
KL(W ST, W
Σ
E
KL(Pt. Pi)
WernWer
8.237 2 V Fw,, =)
10 Wt-1
oR,n
which implies that
KL(Qs: KL(WTr W7) S KL
ST. W'ST)
T
8.23
E
VF (wc, 2)12
n²
W
1=1
Together with 13 and [4). we have
T
erigen S 2C' E
E
8.23
|IF
21)
5
112
Wi-1
S 2C
2E
8.23
E
[VF((w
(concavity of vx)
n2
Since SGLD order-independent, we can replace VF 2,,) with VF 2,) for any i E [n] in the right-hand side of the above bound. Our theorem then follows from the concavity of vz. Further- more, if we bound KI(P, Q2) instead of (L P) in the above proof, we obtain the following bound that depends on the population squared gradient norm:
8.12C
gen
E 1e W
(F..,2)))
DND
A.4 EXTENSION TO GENERAL NOISES
We can extend the generalization bounds in previous sections, which require the noise to be Gaus- sian, other general noises, namely the family of log-lipschitz noises.
Definition 22 Log-Lipschitz Noises). A probability distribution on R2 with density is L-log- lipschitz if and only if V In p(w)] < L holds for any E Rd. A random variable is called an lipsg-iipschitz noise if and only if it is drawn from an
distribution.
The analog of SGLD, noisy momentum method (Definition 24), and noisy NAG (Definition 25 be naturally defined by replacing the Gaussian noise Çe at each iteration with an independent L-log-lipschitzz noise the definition.
The following lemma is analog of Lemmal 21 under A-log-lipschice noises. Recall that G denotes a collection mini batches of size b. Lemma 23 readily implics the analogs of Theorems II and 27 under more general noise distributions.
18

---

Published as a conference paper at ICLR 2020
Lemma 23. Suppose that batch size b S n/2 and N is an Lnoise waaee-loo---ppp lipschitz distribution IR.
{MB : B E G} and {u'g E G} are two collections of points in I2 that satisfy the following conditions for some constant
0,
1. ||a rell s 3 for B Gn and aa 1BB for B E Gn-
2. diam( B G} U (Mb: B 1
For μs Rd, let Py denote the distribution C+ when Ç is drawn from N. Let Pet कि EBEG Png and P' 1
G EBE Prcg be mixture distributions over all hani-batches. Then,
Co
KL(P, PO)
for some constant Co that only depends on Lnuise-
Proof of Lemma 23 Following the same argument as in the proof of Lemma 21 we have
+00
KL(P, In2
Σ 2
A(2
* (1- " P')
(15)
where
4 k-²
(Pwz (w) PNig (w))
A(2 + (1-2 P')
E AEG., BEG,
dw. (16)
n² Gm Gml
Rd
Pμa (w)
Fixed A E Gn and B E Gn. Let Phoise denote the density of the noise distribution N. Since μ| MBll S and Pnoise is Looise-log lipschitz, -og--ishht,,, we have
Pun (w) Pnoise (w PB) S Puoise (w HA) e Jasi Maa-lell I c elassie elasieppa Pea (w).
Similarly, since ||MB - M'B ll I B, we have
- Piu (w) S Pul (w0) S e @bunee pup
Then, follows from 3 Inoise < that
(Puæ (w) Pr', (w)) < (e (e 1 1)2puz (w)2 < L Lussee (w)2
Therefore, the integral the righthand side of (16) can be upper bounded as follows:
f (Pan (w) Pule (2))2 Pua (w)
Pen (w) dw
dw <,8 T
Ra PμА (w)
<22 L Doise
Puo (w) chuve du
JR
32 D Jrass
Plugging the above inequality into 15 and I6 gives
222
4 32
A(2 * -1-22 P')
<
Σ
L2 Lauiue Juave = 2 Junie
e
n²
G Gn
n22
AEG. BEG.
and
+o0
4 kk222
6² noise
KL(P, < 2n
Σ
2 2 brain
2 ln 21
Inbba
n2
n2?
k=0
19

---

Published as a conference paper at ICLR 2020
A.5 EXTENSION TO OTHER GRADIENT-BASER METHODS
A.5.1 STABILITY BOUND FOR MOMENTUM AND NESTEROVS ACCELERATED GRADIENT
We adopt the formulation of Classical Momentum and Nesterov's Accelerated Gradient (NAG) methods in Sutskever et al. (2013) and consider the noisy versions of them.
Definition 24 (Noisy Momentum Method), Noisy Momentum Method on objective functionn F(w,z) and dataset S is defined as
{ V + 1 V W. c- W
Definition 25 (Noisy Nesterovs Accelerated Gradient). Noisy Nesterovs Accelerated Gradient (NAG) on objective functionn F(w, 2) and dataset is defined as
[Vi 7 V WW- (B.)). Se. W; W Ve.
In both definitions, "/e is the step size, mini-batch B, drawn uniformly from G. Çe is a Gaussian noise drawn from from.N(O, (((0, La), and 77 [0,1] is the momentum coefficient.
Theorem 26. Under the same assumptions on the loss function, objective function, batch size and learning rate as in Theorem [7] the generalization bounds in Theorem 77 still hold for noisy mo- mentum method and noisy NAG.
Proof of Theorem 26 For any time step and wet (Wy, W1, .... W,-1), let Pe and P/' denote the distribution of W, and W conditioned on W = wet and W = Wet, respectively. By definition,
we have Pe = [o] EBEG PHa and P/ = 1
[ EBEG Pun
/ = 1, for both noisy momentum method and noisy NAG, we have
PB = = 71 V 11 n = W 7/ V.. F(u SB)) For t > 1, if noisy momentum method is used, we have
PB w + 7 - 12-2) - 7/ V FW
fBB = w + n(w=-1 - wx-2) - 7t V Ww S.).
Similarly, the following holds under noisy NAG:
= w:-1 + 7/ wi 22-2) - V., F (w:- + n|w, - (0 w(-2), Sn),
Mgg = w ( w,-2) - 7 V (w; + 17( 7 - ((-2),553
In either case, can be verified that the conditions of Lemma 21 hold for B 20 and d
The rest of the proof is the same as the proof of Theorem
A.5.2 STABILITY BOUND FOR ENTROPY-SGD
In the Entropy-SGD algorithm due to Chaudhari et al. 2017)) instead of directly optimizing the original objective F(w), we minimize the negative local entropy defined as follows:
-E(w, 7) - log / exp (-F(w') 2 || w w'll)) dw
(17)
Intuitively, wider local minimum has lower loss (i.e., - Fw 7)) than sharper local minima. See Chaudhari et al.) (2017) for more details. The Entropy-SGI algorithm invokes standard SGD to minimize the negative local entropy. However, the gradient of negative local entropy
.v. (.,,(,,))) = (
P(w') x exp(-F(w') -
2 ||w w (13)
(18)
hard compute. Thus, the algorithm exponential averaging to estimate the gradient in the SGLD loop; see Algorithm[ for more details.
We have the following generalization bound for Entropy-SGD.
20

---

Published as a conference paper at ICLR 2020
Algorithm 1: Entropy-SGID
Input: Training set = (21,.., and loss function g 2).
plyper-parameters: Scope y, SGD learning rate 17, SGLD step size n/ and batch size 6.
for f to 7 do
//SGD iteration
Wr.0. Mr,0 f- K1+
for k = 0 K 1 do
//SGLD iteration
Br, mini-batch with size b;
WL,++ WG, - V (WW. ke SB..) tW W..) + VFeN(O, [T)):
PL,++ + (1-a))4a + aWi,ki
end
WiK+1 + WiK (WWK Ht,k);
11 end
12 return WT,K+1i
Theorem 27. Suppose that the loss function L is C-bounded and the objective function F is L- lipschitz. If batch size b & n/2 and v $ e/(2L),, the following expected generalization error bound holds for Entropy-SGD:
8.
K (t,
erT gen S
Σ
Σ
ge
(empirical norm)
ET1
where ge(t, k) = Ba. Σ
[V = We denotes the training process with respect to S.
is the empirical squared gradient norm, and
Since ge St, (.) is most L?, it further implies the generalization error of Entropy-SGI SGD is bounded
by O CV VTK)
Proof of Theorem 27 Define the history before time step () as follows:
W ((. (Wo.o..., Wo,++,, W W,- 1,K-1 W W.,
(19)
Since f is only determined by W, we only need to focus on W. This proof is similar to the proof of Theorem I1 By setting P = Egz Q (3. Suppose S = (3, 2) and S = (5,0) 0) are fixed, let W and W' denote their training process, respectively. Considering the following 3 cases:
We,0 f Wi-1K+11 In this case, for fixed WC()-1,K+1). we have
KL (Wroll (/-ooW/s--1,,+1) WS(--1K+1) W W S(t-1,441) -S(0-1K+1) 0.
2. WLA+1 + WeR n/'V w SB..) + (W, -114+ WeR) + ViTEN(O, [la): In this case, fix (g(L,))) applying Lemma
gives
8.231/ [V
KL (We. (We++I S(..))) = wg(, W
6.+ W ((,,)) = (g(()))
E?n?
3. WCK+1 + We,K (W, K - -t,k): this case, for a fixed Wg(t,K), we have
KL ( W.KK+IWeS Ws = (g(.)))) W Wh,K+1 W ((.K) = w = 0.
By applying Lemma 10
have
8.23n/
T K-1
KL(WrK41,WH
Σ
Σ
(t, k).
c2n²
km0
and Where (t, k) is the empirical squared gradient norm of the k-th SGLD iteration in the f-th SGD iteration, respectively. The rest of the proof is the same as the proof of Theorem
21

---

Published as a conference paper at ICLR 2020
B PROOFS IN SECTION 4
B.1 MARKOV SEMIGROUP AND LOG-SOBOLEV INEQUALITY
The continuous version of the noisy gradient descent method is the Langevin dynamics, described by the following stochastic differential equation:
dW; FW,, di 22--1 dB, Wo plo,
(20)
where B, is the standard Brownian motion. To analyze the above Langevin dynamies, we need some preliminary knowledge about Log-Sobolev inequalities.
Let (e y) denote the probability density function (i.e., probability kemel) describing the distri-
bution of W2 starting from w. For given SDE such as (20) we can define the associated diffusion semigroup
Definition 28 (Diffusion Semigroup). (see e.g., (Bakry et al. 2013 p. 39)) Given stochastic
(Pt)c20 is a family of operators that satisfy for every & 2 Pt is linear operator sending any real-valued bounded measurable function f on IR to P.f(w) ELf(W:) =w] = f()):(w,dy))
differential equation (SDE), the associated diffusion semigroup P
The semigroup property Pi+. P. holds for every t, 2 Another useful property of Pa is that it maps nonnegative function to a nonnegative function. The carré du champ operator I of this diffusion semigroup (w.r.t (20)) is (Bakry et al. 2013 p. 42)
r(f.g) 3- (V.. Vg).
We use the shorthand notation [(f,) 8- v f and define (with the convention that log 0 =
Ent, (f) | flog du du- clu-Joe du
log log (Fr
f du Idu
Definition 29 (Logarithmic Sobolev Inequality). (see e.g., (Bakry et al. 2013 p. 237)) A probability
measure I said satisfy a logarithmic Sobolev inequality LS(a) (with respect to I), if for all functions f Rd + 1R+ in the Dirichlet domain D(E),
T(J)
Ent, Ent S
O Jez
dp.
2
D(E) is the of functions f TT. for which the quantity 1 Sga J(S P.f) dp has a finite (decreasing) limit as decreases to
well-known Logarithmic Sobolev Inequality the following result for Gaussian measures.
Lemma 30 (Logarithmic Sobolev Inequality for Gaussian measure), (Bakry al. 2013 p. 258) Let be the centered Gaussian measure on Rd with covariance matrix a Then μ satisfies the following LSI:
0² 2
|V f
Ent, (f)
dp
Lemma states that the centered Gaussian measure with covariance matrix o² satisfies LS(3o2) (with respect to I'), where I' = 3 (V Vg) is the carré du champ operator of the diffusion semi- group defined above.
Before proving our results, we need some known results from Markov diffusion process. It is well known that the invariant measure (Bakry al. (0033] p. 10) of the Above/CLDjep the Gibbs measure
dy 2,,
dw (Menz et al. 2014 (I.3).. In other words, satisfies Jg.. Prfda.
Sas fdu for every bounded positive measurable function f. where P. is the Markov semigroup
in Definition 28 The following lemma by Holley and Stroock Holley & Stroock/ (1987) (see also
(Bakry et al. 2013 p. 240)) allows us to determine the Logarithmic Sobolev constant the invariant
measure μr.
22

---

Published as a conference paper at ICLR 2020
Lemma 31 (Bounded perturbation). Assume that the probability measure satisfies LS((:) (with respect to T). Let μ be a probability measure such that 1/b S du/dv I b for some constant > 1. Then μ satisfies LS(b'aa) a)) (with respect to I')
In fact, Lemma 31 is simple consequence of the following variational formula in the special case that (xx) = 2: log r, which we will also need in our proof:
Lemma 32 (Variational formula). (see (Bakry et al. 2013 240)) Let á + R on some open interval R be convex of class C², For every (bounded or suitably integrable) measurable function f Rd - R with values in I.
Jec +() al) du du-dd-o Φ
- inf (())))(()--((0 rEt
du.
(21)
worth noting the integrand the right-hand side nonnegative due to the convexity of Φb
B.2 LOGARITHMIC SOBOLEV INEQUALITY FOR CLD
Recall that Fs(w) = F), (w, S) + À |//1//2 is the sum of the empirical original ob- jective (w, S) and &g regularization. Let dy z, exp(- - 1ep(-8Fsth Fs())) du be the invariant (Gibbs) measure of CLD and is the centered Gaussian measure de > exp(-8X | /2) dw. In- voking Lemma 30 with = AØ shows that satisfies LS(1/A) (with respect to I). Consider the density ((w) dv 2/2 exp(- 5)). If the original objective function Fo is C-bounded, we have exp(-2.8) - h(w) S exP())C). By applying Lemma 31 with b cxp(28C), we have following lemma.
Lemma 33, Under Assumption 14 lel r(..g) (VI(VJ, Vg) be the carré du champ operator of the diffusion semigroup associated to CLD and μs be the invariant measure of the SDE. Then, satisfies LS(e4BC />) with respect to I.
Let br be the probability measure of W,. By definition of Pt, for any real-valued bounded measur- able function ff Rd and any t 0,
E wo-ttt
[f(w)] = E (P(s(w))
(22)
In particular, if the invariant measure = 1ox exists, we have
E [f(w]] wmy
E [Pif(w)] wm-ptc
E woupetoo
[f(w)] E. [Pif(w)). wwy
(23)
The following lemma crucial for establishing the first generalization bound for CLD In fact, we establish Log-Sobolev inequality for Pt. the parameter distribution at time f, for any time f. >> 0. Note that our choice of the initial distribution μo is important for the proof.
Lemma 34. Under Assumption 74 let μt be the probability measure of W, in (CLD) with initial
probability measure d140 = 7e ~ dw. Let be the carré du champ operator of diffussion
semigroup associated to (CLD). Then, for any ʃ Rd - IR+ in DEE):
83C /
D()
Ent,, (ʃ) S
dpc
Proof
Let μ be the invariant measure of CLD
By Lemma 33 and Definition 29
A3C
||V/12 dy.
Ent <
/ f
(24)
2X3
For arbitrary initial distribution, it is impossible to prove similar inequality for any 0 (unless the loss strongly convex).
23

---

Published as a conference paper at ICLR 2020
By applying Lemma 32 with d(x) log z, rewrite the left-hand side
[f) = |pc f flog du | dulog (fee du
inf { [o(0) 6(r) - ( -r]] du
rel
inf { (P((0(f)- x(r) - -1)] du.
where the last equation holds by the definition of invariant measure have
Pif dp = I f dp. Thus, we
[ (P:(0()) -())
48C
inf rET
- du = (f)
du,
(25)
2AB
f
JR
Let μr be the probability measure of W.. Lemma 32 and
together imply that
/
(f) = inf rel Rd
[o(f) 6(r) ('(r( - -r) duc
(26)
=inf red Rdd
[P: (b(1) 6()) - (r)
- r))] dys
Since Pi(o(f) - ((r) - (f - r)) 2 and
dug du S cxp(22BC) we have
/
[Po (d(f)) x(r) - o'(r) -r)) auo du
Ent.. (f)
inf
rET Rd
du
(27)
600
[ II dr.
S exp(22CC)nt,,0) 2X8
Since de Bjo
S exp(23C) and is the invariant measure, we conclude that
6BC
V/ VI
630
|VS
Ent,,, (1)
du
Jxc Pt
dj
2AB
Rd
2AB
f
6BC
dg
P
duo
2X83 Rd
duo
(28)
8BC
I
P.
2X3 Rd
8BC
3-1
fll
8BC
/X
I(F) Rd f
dj
2X
Lemma 16. Under Assumption 14 let pt be the probability measure of W, in CLD (with duo = Je 22llel2
= dw), Let v a probability measure that is absolutely continuous with respect to μas. Suppose du4 = T((w) dw and du = (ww) dw. Then it holds that:
KL(7, Te) < exp(833)
((w Te. (w)
V log
(w) dw.
(29)
2X3
Rd
Proof Let /(w) = (ww) (ww), by Lemma 34 and SE f dji
1, we have
[ f log f du <
830
|V 1
dp
(30)
2X3
Rd
This is because is convex and P; positive operator.
24

---

Published as a conference paper at ICLR 2020
We can that the left-hand side is equal to KL me) and the right-hand side is equal to
7(w) (w) du [
BBC
(T)) JRd 7(w), (w)
8BC
((w) ((w) dw.
V log
2AB
2A3 Rd
Te (T
This concludes the proof.
B.3 THE DISCRETIZATION LEMMA FROM RAGINSKY ET AL. (017)
Let h(w, 2) Fo 2) + Allell We can rewrite Fs(w) Ei h(w, z.) Define uss. a. and es.
as the probability measure of W. (in GLD) and W, (in CLD respectively, Raginsky et al. (2017)
provided bound of (L(us,e> VS.nk) under Assumption 35
This bound enables
derive
generalization error bound for the discrete GLD from the bound for the continuous CLD. We use the assumption from Raginsky et al. (2177) Their work considers the following SGLD:
Wk+1 = Wi - -ngs + V2n 'EK-
Where (s(wk) is conditionally unbiased estimate of the gradient FFs(w)) In GLD setting, Is (Wa) is equal to (wr))
Assumption 35. Let Fs(w)= Ei= h(w 24) Fw S) 1w
1. The function takes non-negative real values, and there exist constants A, B 2 0, such that
1(0, = S
and
|V 2112 S B
V Z.
2. For each z E 2, the function ic(,, 2) is M-smooth: for some M 0, [Vh(w, 2) Vh(u, 2)1 s M ||we e112 Yu,, v Rdd.
3. For each E Z, the function tu(, 2) is (m, b) disisiippa:;:: for some > 0 and b 2 0,
(w, Vh(w, 2)) m 1|lll b, Vw Rdd.
4. There exists a constant ó E [0, 1). such that, for each S E z".
[[lgs(w) VFs(w) s 28 M2 |1ll12 B²) B²),
Vi Rd.
5. The probability law pa of the initial hypothesis Wo has a bounded and strictly positive density po with respect to the Lebesgue measure on IRd, and
Kg
log JRa
e el 2012))(w) dw < oc.
Lemma 36. (Raginsky et 2017 Lemma 7) Suppose that Assumption 35 holds and set (15.0 VS.0 = pa- Then, for any k E & and any 7i E (0, 1 A 43f2) the following inequality holds
KL(us,e MS.nk) S (Co38 + Cin)kn,
where Co and C1 constants that only depend M, Ku, b. 3, B and d.
B.4 PROOFS FOR MAIN THEOREMS
Theorem 15. Under Assumption 14 CLD (with initial probability measure dio 1 has the following expected generalization error bound:
dw)
2c ABC CL
/ 3 (11 (1-1100 exp V
(-XT) XT
gen
(-
-CABC
(31)
n
Indeed, Sga f log f dju Sad 2 log( 2 J KI,l,, Te)
25

---

Published as a conference paper at ICLR 2020
In addition, if Fo is also M-smooth and non-negative, by setting XB 2, X 0 and n 10,1 A ) the GLD (running K iterations with the same pbo CLD) has the expected generalization error bound:
gon S 22C/2KCCTf 2C
B (1 exp
(
(>xnk X eBBC
(32)
where 11 is a constant that only depends on M, X, 3, b, and d.
We apply the uniform stability framework. Suppose and S' are two neigh- boring datasets that differ on exactly one data point. Let (Wi) and (W2) be the process of CLD running on and S", respectively. Let 7/ and ne be the pdf of W? and Wt. We have
Proof of Theorem 15
d KL( m²) dt / " log dw
d
dt
dry
log
Tte
+
Te
doe
dt
Yo
dnc
de
dw
(33)
dt
1 Y
x
f
drit
drt
log
dw
dw
Rd
dt
TT.
Rd
dt
According to Fokker-Planck equation (see
Risken
(1996) for CLD
we know that
An + V (F...)
Ame + V VFs).
Ot
Ot
follows that
dr
7k
I ==
log
dw
Rd
dt
A + V (7e v Fss))
log dw
Rd
1
Ft V dw /
7t
(
log
(V log
Jt. Fss) dw,
(integration by parts)
B
Rd
and
Tt. dmte)
dw
zd
T dt
V (me (FF)F))
ATs
dw
Rd
Ti.
/
( 2 nr.
ViT) dw
VFs)
dw.
(integration by parts)
Rd
n
Together with
33
we have
KL KL(
(7: mT)
J
-1
V7
Vn
V7
76 VT
Vn)
dw
B
7/
T
m
log
I't
7tt
V
Fst)
7t
AV
log
Yt
कe (FF)
dw
n.
n
1
7t
V log
dw
Yes V
log
VFs
Fss)) di
8
add
-1
B
7t
V
log
dw
+
7t. |VF3
V dw.
2/3
Rd
JRd
26

---

Published as a conference paper at ICLR 2020
The last step holds because (a/vB. bv3) I
|a]]
B|lble
Since
VV's
VFs 11
12 n
by
28
2
Lemma T6. we have
EBAC
KT( mT) -
log
dw:
22/
Ru
t 2
which implies
800
KL mT)
2
-1
2B Jud
?t
V
log
7t
dwc.
2
Hence,
d dt
2,122 n²
KL my) - KL TT) +
with KL To) = 0.
(34)
e
Solving this differential inequality gives
2
(1
e X1/0800
KL( -
(35)
n²d
By Pinsker's inequality, we can finally see that
CC
B
( 11-e
sup 2) C(Wr,2)]1 s / KLr, mr)
By Lemma the generalization error of CLD bounded by the right-hand side of the above in- equality.
Now, we prove the second part of the theorem. Let (W+)k20 and (W))z2 be the (discrete) GLD processes training on S and S", respectively. Then for any Z:
|B[[(WK: =)] E[[(Wk, =)]l
20 (
(C-boundedness))
20 (TV (S,nkk + TV(VS.KK MS'
MS'. nk) + TV K, VS mk))
Since AB and X > ..4. Assumption 35 holds with A C, B L, m 3/4 b
2x
12
6 0 and
Kig = 1 log
[ + xZ-z) ). By applying Pinskers inequality and Lemma we have
WV(ss.KPPsnkk S V KL VS,K)) S V KCmn
(36)
and
TV(Ps K, vS
$ KL(Usr,K, K. us S KCin?
(37)
From 35
we have
(1 1- e
Ank
3L2e83C
232e
TV(Us.gk US mk) V
US (SS S\
(38)
n²)
Combining (36..
37 and 38). we have
(
Ank 89C
- B[[(WK,2)) - C[C(WW 2)] 2 20 2KC/ 2CLe4BC
En-
n
A
By Definition GLD is c,, unniformyy stable. Applying Lemma gives the generalization bound of GLD.
Lemma 37 (Exponential decay in entropy). (Bakry al. 2013 Theorem 5.2.1) The logarithmic Sobolev inequality LS(a) for the probability measure is equivalent to saying that for every positive function p IL (n) (with finite entropy).
Eut, Se 2t/0 (pt
for every 2 0.
27

---

Published as a conference paper at ICLR 2020
The following Lemma shows that Po( dee) μ4 in our diffusion process.
Lemma 38. Let P denote the diffusion semigroup of CCL and let Pe denote the probability measure of W.. Then P.
Let μ denote the invariant measure of P
dya
Pt-
du
Proof Let du = =u(x) dæ and dys - (x)x)) dæ. As shown (Pavliotis 2014 page 118), our dif- fusion process (Smoluchowski dynamics) is reversible, which means pl,z (T, v) ((y)pe(y,,))
Thus for any g(z), we have
E
[x(x))] = s(e))(())
s(x))(x)d J
/ (()))(x)d (olu))((...
/ g(s))la)wult))/(lll
E [9(x)] 2m
Since g is arbitrary, P. dp and μ4 must be the same.
Theorem 39. Suppose that > 83C. Under Assumption 14
CLD
(with initial distribution duo
Adlwi1 dw) has the following expected generalization error bound:
83C²
-XT
eTT gen S
+ 4C' exp
VBC.
ABC
In addition, if Fo is also M-smooth and non-negative, by setting XB > 2, X > 1/ and E
10,1A SA the GLDprroess (running K iterations with the same pro as CLD) has the expected generalization error bound:
83C² + 4C'Ceem exp
(Ann
erg 20 /2K
exp
VBC,
eBSC
where C₁ a constant that only depends on M. 3. b, and d.
Proof of Theorem 39 Suppose S and S" are two datasets that differ on exactly one data point. Let (W2)zz and (W))eo be their processes, respectively. Let dut = Te( (w) dw and dug = ((()) dw be the probability measure of W, and W/, respectively. The invariant measure of CLD for S and S are denoted as and pl, respectively. Recall that
dp
Zp e (FF dw,
dp'= = e (FFFg( du.
Zμ
The total variation distance of μ and je is
dy'
TV M²) = 2
dp
Rd
dp
(39)
Zu
exp(-3(Fssrtun Fs(ww))
1
(Fs(w) dw.
2 Rd
Z
Since Zu z (xp(-B(Fs-ruun Fs(ww)) E
[e
1BC
10c
and
480
<
1/2, we have
TV(,, & max
1
4BC
e
43C
1)}
<
43C
(40)
Since y and n' satisfy LS(AA)(1A) (Lemma 33
applying Lemma
37 with p
d du
dph and p'
and Lemma 38 yields:
-2At cBC
22t cABC
KT()::) I exx
KL(Po.)),
KT n²) & exp
KT((p,.11))
(41)
28

---

Published as a conference paper at ICLR 2020
Since KL pi) and KL(16, p²) are upper bounded by 23C, Pinsker's inequality implies that (V u)) and (V4s,, p²) upper bounded by Vexp (h BC. Combining with (40) and note that (V & (V TV p²) + TV (44, H²),
we have
22 c43C
83C²
sup B(C(WT. L(W2, +)]1 2C TV(,,, 14) - 4 exp
BC
n
By Lemma 4 the generalization error of CLD is bounded by the right-hand side.
The proof for GLD proceeds the same way as the second part of the proof of Theorem
C EXPERIMENT DETAILS
We first present the general setup of our experiments:
Dataset: We MNIST (LeCun et al. 1998) and CIFARIO (Krizhevsky & Hinton 2009) in
experiments.
our experiments, we test two different neural networks: smaller version of AlexNet (Krizhevsky et al. 2012) and MLP. The structures of the networks are similar to what are used in Zhang et al. (2017a).
Neural network:
Small AlexNet: & the kernel size, is the depth convolution layer, fc(m) is the fully- connected layer that has neurons. The Rel.U activation are used in the first layers.
3
(onv(k:5,d:64))
pool(k:3)
conv(k:5,::192)
pool(k:3)
fc(384)
fc(192)
fc(10)
MLP:
The MLP used in our experiment has 3 hidden layers, each having width 512. We also use ReLU as the activation function in MLP.
Objective function: For a data point z = (ær y) in MNIST, the objective function is
F(W, 2) = In (ssootmaax(netty (x)))))
where softmax(a)[1) Σ
e and netw (x:) the output of the neural network (10 dimensional vector). Note that the objective function F is exactly the cross-entropy loss.
0/1 loss The 0-1 loss L is defined as:
{
(arg max, netw (x)(i)) *
L (W, (W, (x.
(42)
otherwise.
Random labels: Suppose the dataset contains datapoint, and the corruption portion is p. We randomly select n p data points, and replace their labels with random labels, as in /hhan et al. 2017a).
C.1 EXPERIMENTAL RESULTS FOR GLD
The result of this experiment (see Figure T is discussed in Section 3.1 Here we present our imple- mentation details.
We repeat experiment 5 times. At every individual run, first randomly sample 10000 data points from the complete MNIST training data. The initial learning rate n0 = 0.003. It decays 0.995 after every 60 steps, and it stops decaying when it is lower than 0.0005. During the training, we keep a, 0.2 Recall that the empirical squared gradient norm ga(t) in bound (Theorem 9
29

---

Published as a conference paper at ICLR 2020
is Ew, E'= [V((W,,1,2)) Since it is time-consumingg to compute the exact ge (t),, in experiment, we use an unbiased estimation instead. At every step. we randomly sample a mini batch B with batch size 200 from the training data, and use 200 ΣieB [V 2;)]1 as ge(() to com- pute our bound in Figure [ The estimation of ge at every step shown in Figure dd) Since ge (t) is not very stable, in figure, plot its moving average over window of size 100 make
the curve smoother (i.e., Beeg (t) T00 > ge (T)).
100
C.2 EXPERIMENTAL RESULTS FOR SGLD
In this subsection, we present some experiment results for running SGLD on both MNIST and CIFARIO datasets, to demonstrate that our bound (see Theorem [T]. in particular the sum of the em- pirical squared gradient norms along the training path, can distinguish normal dataset from dataset that contains random labels. As shown in Figure 3 the curves of our bounds look quite similar to the generalization curves. Due to the sub-optimal constants in our bound, the bound is currently greater than I, and hence we omit the numbers on the y-axis.
We note that in our experiments presented in Figure 3 the learning rate that choose is larger than that required by the second condition of Theorem 11 This is because the global Lipschitz constant is hard estimate and the model not able to fit training data under a very large noise. As discussed in Section 3.1 we can relax o; 2 (20L) to 2 maxie[m] [|VF(W; 2))l)% By applying gradient clipping trick, we can further relax this condition to
oi 2 min Ci, (2 max
& VE(N)
(43)
where Cz, is defined in Section 3.1 In order to show that our observation ("random > normal") still holds when the step size satisfies the requirement of our theory, we run an experiment that using gradient clipping trick with Cz 1. The model is trained the original data set with random labels under such a large Gaussian noise extremely slow. As shown in Figure the experimental results remain unchanged when all the conditions of our bound are met.
small subset of MNIST fitting
These experiments indicate that the sum of squared empirical gradient norms is highly related the generalization performance, and we believe by further optimizing the constants in our bound, it is possible to achieve generalization bound that much closer to the real generalization error.
1.0
0.8
train acc
Igen error|
emp bound
0.2
0.0
100
200
300 step
400
500
Figure 2: Training MLP with GLD = 0.2%) on the full MNIST dataset without label corruption. Learning rate % = 0.01 0.95L1/60) Note that in the carly stage, the testing accuracy even higher than the training accuracy, thus plot the absolute value of generalization error. As shown in this figure, even when the training accuracy approaches 90%, our bound still relatively small.
30

---

Published as a conference paper at ICLR 2020
training accurac ayy
generalizan cineralization error
0.8
p-0
emplrical bound
0.8
p-0.5
0.6
0.4
0.4
p
0.2
p=0
p=0.5
0-0.5
0.0
2
10
10*step
10 step
(a)
(c)
0.5
p-0
p-0
0.8
0.5
p-0.5
emplrical bound
p-0.5
training
generalii
0.3
0.4
p=0
p=0.5
0.0
3.0
0.0
0.5
2.0
10"step
10'stop
10'
(d)
(f)
allizatioon error
0.5
emplrical bound
p-0 p-0.5
0.8
0.4
0.3
p=0
p=
0.4
p-0
0.1
p-0.5
0.0
0.5
1.0
2.0 2.5 10fstep
0.0
1.0 1.5
2.0
2.5
3.0
10*step
10fstep
(g)
(h)
Figure 3: SGLD fitting random labels. The meaning of these plots are the same as those in Figure I (a-c): CIFAR10 MLP: (d-f): Neest+AlexNet; (g-i): MNIST+MLP; For each data set, only 5000 data points that randomly sampled from the complete dataset are used for training. Mini-batch size b 500. Learning rate " max(0.0005, 0.003 0.995L*/000 1/60)). Noise level o 0.002
sccursyy
1.0
0.25
squarad gradinn nome
1.0
pm0
0.8
0.20
0.8
0.202
empiniall
0.6
6.4
p-0
0.25
p=0
p
64
p=0.20
0.000
p=0.20
02
0.8
12
12
(a)
(b)
(c)
(d)
Training SGLD with AlexNet on subset of MNIST (250 data points) with different random label portion p. The meanings of the y-labels are same as that in Figure D We use the gradient clipping trick to force the gradient norms of every data points are within C₁. = 1. We set o, according to (43) with replacing ">" with "_". Mini-batch size b = 10. Learning rate
Figure 4:
Yt = max(10-5, 0.0005 0.9 0.910/1000
31


Reviews:
[{"review_id": "SkleD9Q3tH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the generalization error bounds of stochastic gradient Langevin dynamics. The convexity of the loss function is not assumed. The author proposed \"Bayes-stability\" to derive generalization bound while taking the randomness of the algorithm into account. The generalization bound proposed in this paper applies to some existing problem setups. Also, the authors proposed the generalization bound of the continuous Langevin dynamics.\n\nThis is an interesting paper. Overall, the readability is high. The Bayes-stability is a significant contribution of this paper, and the theoretical analysis of the SGLD with non-Gaussian noise distribution will have a practical impact. \n\nSome comments below:\n- What is the function f of f(w,0)=0 above the equation (5)? Besides, the role of zero data point, i.e., f(w,0)=0, was not very clear. \n- In the numerical results (b) and (c) of Figure 1, the scale in the y-axis was very different. What made the generalization bound so loose? \n- In this paper, the developed theory was a general-purpose methodology. For deep neural networks, however, is there a meaningful insight obtained from the method developed in this paper?\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}, {"review_id": "SkeOi8jAYB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper aims at developing a better understanding of generalization error for increasingly prevalent non-convex learning problems. For many such problems, the existing generalization bounds in the statistical learning theory literature are not very informative. To address these issues, the paper explores algorithm-specific generalization bounds,  especially focusing on various types of noisy gradient methods.\n\nThe paper employs a framework that combines uniform stability and PAC-Bayesian theory to obtain generalization bound for the noisy gradient methods. For gradient Langevin dynamic (GLD) and stochastic gradient Langevin dynamics (SGLD), using this Bayes-Stability framework, the paper obtains a generalization bound on the expected generalization error that scales with the expected empirical squared gradient norm. As argued in the paper, this provides an improvement over the existing bounds in the literature. Furthermore, this bound enables the treatment of the setting with noisy labels. For this setting the expected empirical squared gradient norm along the optimization path is higher, leading to worse generalization bound. \n\nThe paper then extends their results to the setting where an $\\ell_2$ regularization is added to the non-convex objective. By using a new Log-Sobolev inequality for the parameter distribution at time t, the paper obtains new generalization bounds for continuous Langevin dynamic (CLD). These bounds subsequently provide bounds for GLD as well.\n\nThe paper demonstrates the utility of their generalization bound via empirical evaluation on MNIST and CIFAR dataset. The obtained generalization bounds are informative as they appear to capture the trend in the generalization error. \n\nOverall, the paper is very well written with a clear comparison with the existing generalization bounds. The results in the paper are interesting and novel. That said, the discussion in the introduction and abstract appears a bit misleading as it gives the impression that this is the first paper that combines the ideas from stability and PAC-Bayesian theory to obtain generalization bounds. This is not the case, e.g. see [1].\n\nAs noted by the authors, some of the bounds obtained in this paper share similarities with one of the bounds in Mou et al.  as all these bounds contain the expected empirical squared gradient norm. The bound in Mou et al. holds with high probability and decays as $O(1/\\sqrt{n})$, whereas the bounds in this paper are on expected generalization error and decay as $O(1/n)$. Could authors comment on extending their results to hold with high probability and how it would affect their bounds?\n\n[1] Rivasplata et al., PAC-Bayes bounds for stable algorithms with instance-dependent priors.\n\n\n----------------------- Post author response -------------\n\nThank you for addressing my comments. I have decided to keep my original score unchanged.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "HyxQ4HuatB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors provide new generalization analysis of (stochastic) gradient langevin dynamics in a nonconvex learning setting. The results are largely based on and improves the analysis in Mou et al. (2018). In more details,  Theorem 11 improves the corresponding generalization bound in Mou et al. (2018) by replacing the uniform Lipschitz constant by the expected empirical gradient norm, which can be smaller than the Lipschitz constant. The authors also argue this can distinguish normal data from randomly labelled data with experiments. The authors further studied the setting with an l_2 regularizer and derived improved result applicable to the case with infinite number of iterations, in which case the results in Mou et al. (2018) can diverge. These results are derived by a new bayes-stability method.\n\nA drawback is that the results are only applicable to gradient methods in Section 4, i.e., using all examples in the gradient calculation. It would be interesting to see how the generalization bound would be for the stochastic counterparts.\n\nThe authors assume \\lambda>1/2 in deriving (8). In practice, the regularization parameter should be set to be small enough to achieve a small test error. Therefore, eq (8) may not be quite interesting.\n\n----------------------\nAfter rebuttal:\n\nI have read the authors' response. I would like to keep my original score.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors provide bounds on the expected generalization error for noisy gradient methods (such as SGLD). They do so using the information theoretic framework initiated by Russo and Zou, where the expected generalization error is controlled by the mutual information between the weights and the training data. The work builds on the approach pioneered by Pensia, Jog, and Loh, who proposed to bound the mutual information for noisy gradient methods in a step wise fashion.

The main innovation of this work is that they do not implicitly condition on the minibatch sequence when bounding the mutual information. Instead, this uncertainty manifests as a mixture of gaussians. Essentially they avoid the looseness implied by an application of Jensen's inequality that they have shown was unnecessary.

I think this is an interesting contribution and worth publishing. It contributes to a rapidly progressing literature on generalization bounds for SGLD that are becoming increasingly tight.

I have one strong request that I will make of the authors, and I'll be quite disappointed if it is not executed faithfully.

1. The stepsize constraint and its violation in the experimental work is currently buried in the appendix. This fact must be brought into the main paper and made transparent to readers, otherwise it will pervert empirical comparisons and mask progress.

2. In fact, I would like the authors to re-run their experiments in a way that guarantees that the bounds are applicable. One approach is outline by the authors: the Lipschitz constant can be replaced by a max_i bound on the running squared gradient norms, and then gradient clipping can be used to guarantee that the step-size constraint is met.  The authors might compare step sizes, allowing them to use less severe gradient clipping. The point of this exercise is to verify that the learning dynamics don't change when the bound conditions are met. If they change, it may upset the empirical phenomena they are trying to study. If this change does upset the empirical findings, then the authors should present both, and clearly explain that the bound is not strictly speaking known to be valid in one of the cases. It will be a good open problem.





Decision: Accept (Poster)