Time-independent Generalization Bounds for SGLD in Non-convex Settings
Authors: Tyler Farghly
Patrick Rebeschini
Venue: NeurIPS 2021 Poster (2021)
Keywords: SGLD
Langevin
stochastic gradient
generalization
stability
non-convex
wasserstein
optimization

Abstract: We establish generalization error bounds for stochastic gradient Langevin dynamics (SGLD) with constant learning rate under the assumptions of dissipativity and smoothness, a setting that has received increased attention in the sampling/optimization literature. Unlike existing bounds for SGLD in non-convex settings, ours are time-independent and decay to zero as the sample size increases. Using the framework of uniform stability, we establish time-independent bounds by exploiting the Wasserstein contraction property of the Langevin diffusion, which also allows us to circumvent the need to bound gradients using Lipschitz-like assumptions. Our analysis also supports variants of SGLD that use different discretization methods, incorporate Euclidean projections, or use non-isotropic noise.

Time-independent Generalization Bounds for SGLD in Non-convex Settings
Tyler Farghly Department of Statistics University of Oxford farghlydstats. ox ac ac.uk uk
Patrick Rebeschini Department of Statistics University of Oxford ac uk
1x1v:2111112876V [stat.ML] 25 Nov 2021
Abstract
We establish generalization error bounds for stochastic gradient Langevin dy- namics (SGLD) with constant learning rate under the assumptions of dissipativ- ity and smoothness, setting that has received increased attention in the sam- pling/optimization literature. Unlike existing bounds for SGLD in non-convex settings, ours are time-indeen -ieeinndeenndett and decay to zero as the sample size increases. Using the framework of uniform stability, we establish umeeindependent bounds by exploiting the Wasserstein contraction property of the Langevin diffusion, which also allows cireumvent the need bound gradients using Lipschitz-like assumptions. Our analysis also supports variants of SGLD that use different discretization methods, incorporate Euclidean projections, or use non-isotropic noise.
Introduction
Investigating the generalization error of learning algorithm is fundamental problem in machine learning that has motivated the development of rich theory connecting notions of model complexity and sensitivity to the ability of learning algorithm generalize well to unscen data. Recently, there has been increased interest in studying the generalization capabilities of stochastic gradient descent (SGD) and its variants, e.g. [13 [1 6
17 (2 19). Despite them being some of the most important methods of modern machine learning and statistics, their learning capabilities have not been fully explored, particularly in non-convex settings.
One variant that has attracted lot of attention is stochastic gradient Langevin dynamics (SGLD) With the addition of independent Gaussian noise to each iteration, SGLD combines the SGD framework with the Langevin diffusion, a stochastic process that converges to the Gibbs distribution of a given objective function. By tuning the scale of the noise applied, SGLD has been shown to work well as both a sampling scheme and a statistical learning algorithm a variety of settings, e.g. [29 25 [4]. Using its relationship with the Langevin equation, various tools from stochastic analysis have been adopted to develop a rich theory analyzing SGLD in settings where no comparable results seem to be available for SGD, e.g. (23 32 31). In particular, a recent work from Raginsky et al. (23) provides non-asymptotic excess risk bounds for SGLD for a broad class of non-convex learning problems and these bounds were derived using the exponential ergodicity of Langevin diffusions. Following this work, there has been ongoing progress in the development of bounds for both optimization error and mixing times, e.g. 32 by recent results showing that Langevin diffusions contract in particular Wasserstein distances (8, 9).
29
7 4. Many of these works are motivated
In parallel to this literature, there has been growing body of work that considers generalization error bounds for SGLD. Using uniform stability, Mou et al. [17] showed that under the assumption of bounded gradient updates and bounded loss functions, SGLD attains generalization bounds that grow slower with time than those that are known for SGD in identical settings [3] 6
By bounding
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

the generalization error using the mutual information between its input and output [30], Pensia et al. [22] established similar results while replacing the assumption of bounded loss functions with the weaker assumption that the loss function applied to the data is subgaussian. This technique has also been used to develop data-dependent generalization bounds that depend on the gradient along the trajectory of the iterates [18 12 19].
Although the assumptions made in the aforementioned bounds cover several settings of interest, we are not aware of any convergence analysis that considers Lipschitz, bounded, or subgaussian objective functions. In general, the Gibbs distribution, which is an object that is fundamental to the design and known convergence analyses for SGLD [29 25 23 5 [2], cannot be defined in the case that the objective is bounded over the Euclidean space, as the distribution would not integrate to one. Similarly, we are not aware of any generalization bounds for SGLD that use the assumptions of dissipativity and smoothness that are consistently applied the non-convex sampling/optimization literature, e.g. 233 32).
Another commonality in existing generalization bounds for SGLD that they grow indefinitely with time. Sampling from the Gibbs distribution, the limiting behavior of the Langevin diffusion, is known to be uniformly stable in multiple settings 30 23 and it has also been shown that the continuous- time Langevin dynamics are uniformly stable when applied to bounded Lipschitz functions with weight decay [T6]. However, convergence in generalization error for SGLD seems to have only been observed in preliminary empirical evidence that uses data-dependent bounds [18] 12). Time- independent bounds have been obtained for SGD, for example, under the assumption of strong convexity in [13] and in non-convex settings, Lei and Ying [15] obtain bounds that decrease with time but do not decay to zero as the sample size increases.
1.1 Our contributions
In this paper, we obtain expected generalization error bounds for SGLD for learning problems under dissipativity and smoothness assumptions. We analyze both the discrete-time algorithm as well as a continuous-time version and in both cases, we obtain bounds that converge with time. Taking the supremum with respect to time yields time-independent bounds that, with the appropriate scaling of the learning rate, decay to zero as the sample size increases.
At first, focus on the special case of Lipschitz loss functions with weight decay, which is the primary example of a dissipative objective given in Raginsky et al. 223) For the continuous-time algorithm, we obtain bound with rate (n=1)) and for the discrete-time algorithm, we obtain bound with the slower rate ( + 1 where 1) is the learning rate. Then we extend the result to the full dissipative case without Lipschitz requirements. In this setting, we obtain bounds with rate O(n 111) for the continuous cantinuous-time algorithm and with rate On 1/2 time case. We also discuss how method allows for the consideration of different discretization techniques and how it can be used to obtain generalization error bounds for modifications of SGLD that incorporate Fuclidean projections or non-isotropic noise. From our bounds, scheme for choosing v follows: in the Lipschitz setting, we obtain dimension-free (n--1) bounds by setting " dd where d is the model dimension, and in the dissipative setting find that scaling of 17 n leads to (1/2) bounds that, in general, scale exponentially in dimension.
11/ + 17 /22 in the discrete-
To derive iime-independent bounds, our proof technique depends fundamentally on the two sources of noise that occur in the algorithm: the random mini-batches and the injected Gaussian noise. Using the framework of uniform stability, in the sense defined in [1), we derive generalization bounds by estimating how much SGLD diverges in Wasserstein distance when an element of the data set is changed. We exploit recent results that use reflection couplings to show that under dissipativity- type assumptions, Langevin diffusions contract in Wasserstein distance. Though this property has been adopted extensively in the sampling/opiimizatinn literature, we are not aware of any results for generalization bounds based on this property. Using the convexity of the Wasserstein distance, we combine this with the stability induced by using stochastic gradients to obtain bounds that are time-indepen inmeinddeeendet.
peculiarity of our results that arises from the methodology we use is that some of our bounds diverge as v - 0. This contrasts with the usual approach of stability- generalization bounds based on non-expansivity that often require the learning rate to decay sufficiently fast or the time-horizon to be sufficiently small to guarantec bounds that are non- vacuous [13 17). Furthermore, for our bounds to

---

Paper
Assumptions
EGE Bound
Key
Raginsky et al.
D,
(nt t m0/0 + 1/n ((nt)))///)) /n)
B
Bounded
Mou al. 17
B, L
L
Lipschitz
Mou et al. 17
L, SG, l
Ollog(++))/n))
Smooth
Pensia
22
L, SG
(nl//n)//
&
Weight decay
Present work
L, S, f2 D. S
O A 1)(1/n+1 + 1) ((1) A 1)
D
Dissipative
SG
Subgaussian
1/2 /n/ (3)
Table 1: Comparison of expected generalization error bounds for SGLD in recent works.
converge with time, require the mini-batch size to be less than While our bounds support the case of full-batch gradient descent, we find that our bounds grow indefinitely with time.
2 Background and notation
2.1 Stability and generalization
In this paper, we consider a loss function f IRd x 2 + R where the Euclidean space Rd represents the set of possible model parameters and 2 represents the data instance space. A common objective in learning theory is to minimize the population risk which, given data distribution P, is defined by
Fp(x) := Ez-p/ (x, Z).
instead collect independent samples from P to form a data set and we compute the average loss, or empirical risk, over the data set. We will use the (01,....,,,, Zn) denote the data and define the empirical risk
In practice, often cannot compute F2(x))
notation S (Z1,
T
Fs(x) == n
f(x, 21).
When the parameter is chosen by random algorithm that depends on the data set, denoted A(S), we define the object central this paper, the generalization error, as follows:
gen( A) = F - Fs{()S))
To bound this quantity we employ the following notion of uniform stability. Definition 2.1 (113, Definition 2.1), An algorithm A is c-uniformly stable if
Estab(A) = sup sup E (((()))))) Se. 3 2EZ
where the first supremum over data sets S. 2" that differ by one element. denoted by S ~ S.
The connection between generalization and stability under changes in the data set has received increased attention since the paper of Bousquet and Elisseeff [2], and these results have been extended account for random algorithms by Elisseeff al. [10]. The precise notion of stability that we consider in this paper is given in Hardt et al. [3].
Proposition 2.2 [33, Theorem 2.2). Suppose A is an s-uniformly stable algorithm, then the expected generalization error is bounded by
EA, gen (A)l Se.
Though we will present the results of this paper as bounds on expected generalization error, uniform stability bounds can also give high probability bounds for the generalization error 3 Outside of generalization bounds, the concept of uniform stability has also been shown to be fundamentally related to differential privacy and learnability 28 24).

---

2.2 Stochastic gradient Langevin dynamics
We will now define the algorithm of interest this paper. Given a mini- B C [n] := fl.... let the mini-batch average be defined by
Fs(r, B)
5(r 21). B
EEB
In our analysis we will consider uniformly sampled random mini- mini-batches of fixed size k S n. We now define SGLD, which given initial distribution Pa, is characterized by the update
1+++ = 3z - v, V Ps B1+1) + 233 1/ To μ4::
(I)
where (B)) is am i..d. sequence of random variables distributed uniformly on the set {B C [B] k} and (Er) is i.idd sequence of (00, La) standard Gaussian random variables. The parameters 77, 3 > are tunable and are referred to as the learning rate and inverse temperature V refer to the gradient with respect to the
[m]
respectively. Here and throughout the paper model parameter.
If = n then (1) describes the Fuler-Maruyama discretization of the (overdamped) Langevin equation with potential (.).). This stochastic differential equation the form
dX, Fx) + /28-1dW: ldW, Xo Po.
where W, is d-dimensional Wiener process (1 In the more common case that k < n we can still define a stochastic differential equation that approximates SGLD, given by
dX, - V's Bit/n + 233 Xo Po.
We will refer to the solution X, as the continuous-timg SGLD algorithm. Note that, under the smooth- ness assumptions imposed throughout this paper, all stochastic differential equations considered have strong solutions (see Theorem 3.1 of (2
Since F2 is Markov process, reference this fact, we will use the notation μRg to denote the law of re+a under the condition Iy ~ J.. Because of its dependence BR, X, is not necessarily a Markov process in continuous discrete-time process (Xon) does in fact satisfy the Markov property and so we denote its kernel by Rx.
define its Markov kernel Rg. Though will not frequently
but the
Given a deterministic set B C [n]] we use the notation μPP B to denote the law of 0,, the solution to the SDE,
d0.- - Fo, B)dt + 1223-1WW Ou μ4
(3)
which is Markov (diffusion) process. Thus μRx can be computed by integrating μP over B with respect to the mini-batch distribution.
Since this work is concerned with stability under changes in the data set, we will also be interested in SGLD when S is replaced with some data set S that differs by single element. We will use the notation & and X, to denote the respective counterparts of of X, when trained using Š instead of and similarly we will use R2, Rx and P.B.
2.3 Wasserstein distance
For probability measures μ, u on Rdd with finite th moment, we define the Wasserstein distance
W = (
/ ||x yll" (dd., dy)
1/p
inf (TC((p.))
where || is the Euclidean norm. Here the infimum is over all couplings of μ and v. that is, the set of all probability measures with marginals p and v. In our analysis, we will also consider Wasserstein distances based on any semimetric p, which under certain integrability assumptions is defined by
W (p, = inf rECunM) I I |plx.10 v) π (dd, dy).

---

Note that throughout this paper all probability measures considered outside of the data distribution, are Borel probability measures on R"
property of the Wasserstein distance that will prove to be of central importance in our results is its convexity.
Lemma 2.3 (Convexity of the Wasserstein distance). Suppose that p is a semimetric and pi, P2, Vi, M2 are probability measures. Then, for any r E [0, 11,
Wp(n,, 2/ S r W ( v1) (1 W ( v2): where we define p(dr)= = rpu (dx) + (1 r)p2(dz) and v(dz)= rv1 (dx) + (1- (1-r))u(dd)))
The proof of this result, as well as more general statement, can be found 26 Theorem 4.8.
3 The Lipschitz setting with weight decay regularization
To begin our analysis, we focus on a special case of the dissipativity and smoothness assumptions. We will assume that the loss function f (xx 2) is Lipschitz in æ: for any fixed z, and when performing gradient updates we will use the empirical risk with an added weight decay term:
+ X ||=||
Fs(z, B) = Fs(x, B)
2
This setting has been considered in the data-dependent literature for SGLD, for example by Mou et al. [17] and under the additional assumption of boundedness, this setting has also been considered in the stability-based analysis of the continuous Langevin dynamics by Li et al. [16].
The following assumptions are imposed:
Assumption 3.1. For each z E Z, f(,22) is L-Liscchitz: for all x1, E Rd and 2 E Z,
2) [ 2)] S L| - -x2ll- Assumption 3.2. For each z E Z. 2) is differentiable and M-smooth: for all x x1, E Rd and z E Z,
[V 2) f ([(22,2)] 2)Il S M| x2ll-
Assumption 3.3. The initial condition pa has finite first moment 0 po 11) <0.
When using weight decay, Assumption 3.1 guarantees that Fs is dissipative which allows us obtain Wasserstein contractions. Assumption 3.2 guarantees the existence of solution the SDE in ( and allows us control the error that is brought about when using it to approximate the discrete-time algorithm. Assumption 3.3 is used to guarantee that SGLD has finite first moment so that we can perform our analysis using the I-Wasserstein distance. Note that the weight decay term only affects the gradient updates of SGLD and is not used in the computation of the generalization error, which is still defined in terms of Fs and Fp and not Fs-
Theorem 3.1. Suppose Assumptions] 3./ 3.33.3 hold and 1j < 1, then any t E N the continuous-time
algorithu attains the generalization bound
E gen((Xee) < C2 min { nt,
(C1 (C1 + 1)m
n k
Furthermore, if < - then the discrete-tine algorithm attains the generalization bound
nt, (C1 + 1)m n n The positive constants C C. (M,,
E gen((x))) < C33 min
} (
{
+ (nd))/2)
n
C2 (,,,,, L,X,3), C3(M, 3,0 are
given in equations (5). 7 and ( respectively.
Remark 3.2. This result suggests that by using the step-size scaling = O(1/r²d) we obtain dimension-free time- inee-nddeeedden generalization bounds for SGLD that scale with Okk/n).
The bound for the continuous-tim ttmme algorithm has no explicit dependence on dimension and in the discrete-ting case the bound grows with the rate d!/2 In general, the constants C1 C2 and C3s depend exponentially on M,, L, À and B. However, in the case of X > M, the constants become polynomial in these parameters and C2 becomes independent of B3. A similar dependence was found in the time-independent bounds for the Langevin equation [16] and it is also found in convergence analyses non-convex settings, leading to the time horizon required to attain a certain guaranteed
accuracy having to scale exponentially with parameters including d and B, e.g. [23 5 32)
5

---

3.1 Methodology
In this section, we present the method used obtain the bounds in Theorem 3.1 in particular we proceed with the stability framework presented in Section 2.1 Without loss of generality, we require that the two data sets S and S differ only in the 12th coordinate.
Under Assumption 3.1 obtain uniform stability, it is sufficient to control the quantities Wi ( no R'x) and W (uo R. Hi R2). follows directly from the definition of Estab that
(stab(A) S sup W1 (lavo (la))((S)), law (A(S))
(4)
8=2
property similar to this has been utilized in 23 where it was used to prove the stability of the Gibbs algorithm.
To prove Theorem 3.1 we begin with weak estimate for the divergence in W-Wasserstein distance using synchronous couplings between X, and X,, that is, we couple the processes by having them share the same Brownian motion.
Lemma 3.3. Suppose Assumption
3.1 holds, then for any two probability measures μa, v on Rd
W1 (uPB, vPP) - (i()s + 2Tt.
Additionally, via similar technique, we obtain discretization error bounds.
Lemma 3.4. Suppose Assumptions 3.7 3.3 hold and r) < A then with = Ro for any E N,
Wi(aRa,RRy I 7(> M) m(Ao + 2L) + 2 22222d3-1 exp(M + 1).
We refer Appendix B for the proofs of these two lemmas.
3.3 In a recent result from Eberle [8] reflection couplings were used to show that under conditions not dissimilar from dissipativity, diffusion processes contract in Wasserstein distance. The Wasserstein distance considered in this result does not use standard metric, it uses the metric Pg (2r y) == g(Ikæ vll) where g strictly-increasing concave function that is constructed depending on the objective function (or drift term) used. In the lemma that follows we give special case of such result in the setting that we consider. Throughout this section we use the notation W ( v) = Wo, (1, v). We refer to Appendix C for the proof and broader discussion on this result.
In the case p PB we can obtain sharper bounds than those given in Lemma
Lemma 3.5. Suppose Assumptions 3.7 [and 3.2 hold, then there exists a stricily-increasing concave function g I {0} + IR U {0} such that for any two probability measures p. v on R any B C [n] and t 2 0, we have
if < M, if> Z M,
Wo (upB vPB) < -1/0 Wo(an), O
(5)
C3
with constants exp|23L2 a)/23). 02 8(L2B\X 1)/A, c3 max max(1612 2/A). Furthermore, W is equivalent to the I-Wasserstein distance in the sense that
2 ma Wi(M, s Wo(un) < Wi,,
In the case that n is not in the random mini- batih i.. n g B, which occurs with probability 1 k/n, it follows that On = p and so the processes Xt., and X,,, contract with respect to the Wasserstein distance Wg- In the case that is in the random mini-batch, E B, Lemma 3.3 gives uniform bounds for how much Xt,, and Xe, can diverge. The remainder of the proof works to combine these facts and shows that if n is sufficiently large, X',, and X.,, can only diverge by some fixed amount. We combine the two cases using the convexity of the Wasserstein distance and we find that given sufficiently large n, the resulting bound does indeed converge over time.
Proof of Theorem 3.7
As was pointed out in 4 is sufficient to bound the 1-Wasserstein distance between the processes to obtain stability bounds, so this is how will proceed. Since the probability

---

of random mini-bated containing the element n is k/n, Lemma 2.3 is used to bound the Wasserstein distance with the decomposition
Wg (elRx,RRx]
k sup Wg (uP, vp,))
(1 (1-
k
sup Wg (uP . w BugB
n B.EB
n
Bounding the first term using Lemma 3.3 and the second term using Lemma 3.5 it follows that W ((uRx, vxxx I on W W)(,,v) + 2g where é == + (1 We
-)eh//h w/Ch and 82 2L & It follows
by induction that
1 7
Wy Roo Po Rxx)
ड 02 + ej W Wg(Ho:
= 1 - E1
222
(6)
since 0 < 1. Combining this with it follows that
1 - 29
k
Extab(Xny)) S (c V 1) W9 (KR's, vRx) S C21l
n
where,
L,,,,,,,, 40? A 11) This bound is simplified with the approximation ブ I (1 (1-6)) and, using the bound
et 2 1 + x, it follows that (1 - e ----== ---===-- < + + 1/x for x > 0 and so
1
n(c/n+1]
1 δ1 (1 -1-k k/n) e//)
n- k
This result is extended to the discrete-time by applying the triangle inequality,
Wg g (uRg, v Wg (uRz, The first and third terms are bounded using the discretization error bound in Lemma 3,4 and the same argument applied to obtain the bound,
W, (uRx, vfx)xxxxx)) + W, (vxx, vRz).
(Fr) S 2L(c A 1) Wa (polfy, S Can o k
(dd))
where
= =4l( (1l 41) (A + M) (1 - 2I. + 2V 28-1)
(8)
Remark 3.6. For the discrete-time algorithm, the bound is obtained by appending the one-step discretization error to the bound in (6) for the continuous-time algorithm. Thus, the result can easily be extended to a broader range of discretizations of (X1) Suppose K₂ is a Markov kernel on Rdd such that for any probability measure μ on R.d, (iKK,,,RR S 8(1), then we immediately obtain the bound
W1 (HOKz, R) 0 c 5(m)
ni
"
In the case of the standard discrete-ting -ieee algorithm obtain 8(π) = (rp3 A simple example of more accurate discretization follows by instead of approximating X,, with a single Euler-Maruyama step we use = -[1/n] steps with step-size 7 = n/TT, then we can show that 5(n) S (((7) S O
Remark 3.7. With our methodology. it is also possible to derive bounds for projected versions of SGLD. I C Ed is a compact set, we can define the algorithm,
-=1=111
FVFFs
1/3-11
(9)
where Na is the Euclidean projection onto the set Q. A well-known property that is often used in the optimization literature is that for any æ1, 22 IR. [[[n((z)) -1n(22) S || x2ll and, given two measures H.v on Rdd, this naturally extends
W Wi(p'Th N2, v Ta) I W2(H,
where y²" Tl denotes the pash-forward of p. with respect to the mapping Ng. we let Rll be the kernel of the process given in (9, it follows immediately that,
W1 (UR.. R vR! S W1 (1R2,, RR)).
and hence the Wasserstein distance bound given the proof also applies to the projected algorithm and therefore, the generalization bound in Theorem 4.1 also holds for the projected algorithm.
7

---

Remark 3.8. Our technique supports the case where, instead of assuming E. is a standard Gaussian random vector, we set & (0, ) for some symmetric positive semidefinite matrix Σ R If the operator norm of is 1, the conclusions of Lemma 3.3 and Lemmal 3.5 still hold true and, result, the conclusion of Theorem 3.1 would also hold.
4 The dissipative setting
Now we extend the results of the previous section to the full dissipative smooth case. We refer to Section of [23] for detailed discussion on dissipativity.
Assumption 4.1. For each z Z, [ 2) is (m, -isisiiipt:;::: for all IRd and 2,
(Vf(z, 2). m||=]12
Assumption 4.2. Same as Assumption 3.2
Assumption 4.3. The initial condition Po has finite fourthh moment 04 Mol I]) < co.
Without the Lipschitz assumption, the analysis is more challenging as is no longer sufficient to control the uniform argument stability or 1-Wasserstein distance. Furthermore, can longer guarantee that the difference between F's and P'g is upper bounded.
Theorem 4.1. Suppose Assumptions 4.1 hold. If 10, then for any E N, the continuous- time algorithm attains the generalization bound
(tt. {nt. (C4 (Ca+ 1)nz n - //mp1/2''
gen (Xn)) Oss min
Furthermore, if S 1/2m, then the discrete-time algorithm attains the generalization bound
[R gen(())) < Co min
np. (C1 + 1)m k
S 1mp2/22 + +)/
The constants C4 = CM m. b, d. 3). C5 = Cs(M, m, 04). Co = Co are given in equations (11. 12 and 13
Remark 4.2. Choosing y = O 1/2) leads to O(n generalization bounds.
In general, the constants C4, Cs,, and Co depend exponentially parameters M, m, b, d, B. Improv- ing the dependence on these parameters in specific settings would require improvements on estimates of the contraction rate and therefore, improvements on the coupling arguments given in [9].
peculiarity of this result that the bounds explode as r - 0. This is due the fact that when n) is smaller, there is less time for the processes to contract at each iteration. In the setting of Section this combated by the fact that the divergence bounds scale with rate (()). but in the present setting we only obtain divergence bounds with rate O(7 This a result of the metric that we use in our analysis that is designed to suit the coupling arguments given in [9]
4.1 Methodology
Since this result relies similar techniques to the proof of Theorem 4.1 proof to the appendix and in this section, we will focus on the challenges faced when extending to the dissipative setting. Without the Lipschitz assumption it is no longer sufficient control the 1- L-Wasserstein distance and so we must turn to different metrics. Raginsky et al. [23] used continuity
will postpone the
with respect to the 2- Wasserstein metric to derive stability bounds for the Gibbs sampler but, as has been noted in (8) and (27]. contractions in 2- Wasserstein distance are notably more difficult to obtain than in 1- Wasserstein distance.
We use a semimetric of the form,
p( o(1 vl) 2s -e +ely|11,,
where g R+ - [ U a mon-decreasing concave function and s E (0, 1). As will be exhibited in the appendix, Eberle et al. [9] show that there exists g such that for s sufficiently small,
Wp (uP, VP S -t-/Co t/C Wo (u,v).
8

---

for any two probability measures μ. on R Additionally, this function is constant for r > R and has the property fr S g(r) I for some yp, R*
We show that this result can be used to derive stability bounds in the following lemma.
Lemma 4.3. Suppose Assumptions 4.1 and 4.2 hold and let be a random algorithm, then
M M(b/ m
Estab (A)
sup Wp (law law (A()))
see ( RV
S=$
The proof of Theorem 4.1 proceeds by establishing similar results to Lemma 3.3 and Lemma 3.5 using synchronous and reflection couplings. However, the argument is made markedly more difficult due to the fact that W, is not metric, we do not have access to the triangle inequality and not possible to show W, is directly comparable to any standard Wasserstein distances.
5 Conclusion
In this paper, we derive time-independern generalization eπror bounds for SGLD under the as- sumptions of dissipativity and smoothness. We obtain bounds scaling as 0(n-1/2,,-1/2) for the continuous-time algorithm and scaling as Onn-1/2, + 1) /22/2) in the discrete-time case. In the special case of Lipschitz loss functions with weight decay regularization, we obtain faster rates of O(n for the continuous-ting time algorithm and O(n 1/3 ) for the discrete- case. In the latter case, we show that by having the step-size scaling = Old 2),, we obtain dimension-free )-nnegggenaallizaaton bounds.
Within the framework of uniform stability, we use combination of synchronous and reflection couplings to control the Wasserstein distance between versions of the algorithm with perturbations on the data set. Using the convexity of the Wasserstein distance, we show that the two versions the algorithm can only diverge by fixed amount that, with the appropriate scaling of 7), decays to zero as n increases.
The methodology used in our analysis allows for the extension to broader class of discretizations. We are also able explore modifications of the algorithm that incorporate Euclidean projections or non-isotropic Gaussian noise.
The fact that our proof relies heavily properties of the Langevin diffusion does introduce some shortcomings. For example, the discretization error introduced when considering the discrete-time algorithm leads to an explicit dependence on the dimension and, furthermore, the dependence on model parameters aside from d' is often exponential. In addition, Gaussian noise is fundamental in the construction and analysis the Langevin diffusion, so our analysis does not directly extend to algorithms where different types of noise are used.
Acknowledgements
Tyler Farghly was supported by the Engineering and Physical Sciences Research Council (EP/T517811/1) Patrick Rebeschini supported in part by the Alan Turing Institute under the EPSRC grant EP/N510129/1.
References
[1] Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Systems, volume 33, pages 4381-4391, 2020.
[2] Olivier Bousquet and André Elisseeff. Stability and Generalization. Journal of Machine Learning Research, 2:499-526 2002.
[3] Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy. Sharper bounds for uniformly stable algorithms. Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 610-626. PMLR, 2020.

---

[4] Nicolas Brosse, Alain Durmus, and Eric Moulines. The promises and pitfalls of stochastic gradient langevin dynamics. In Advances in Neural Information Processing Systems, volume 31, 2018.
[5] Ngoc Huy Chau, Éric Moulines, Miklos Rásonyi, Sotirios Sabanis, and Ying Zhang. On stochastic gradient langevin dynamics with dependent data streams: The fully nonconvex case. SIAM Journal on Mathematics of Data Science, 3(3):559-988) 2021.
[6] Yuansi Chen, Chi Jin, and Bin Yu. Stability and convergence trade-off of iterative optimization algorithms. arXiv preprint arXiv:1804.01619 2018.
[7] Arnak S Dalalyan and Avetik Karagulyan. User-friendle guarantees for the Langevin Monte Carlo with inaccurate gradient. Stochastic Processes and their Applications, 129(12):5278-5311 2019.
[8] Andreas Eberle. Reflection couplings and contraction rates for diffusions. Probability Theory and Related Fields, 166(3-4):851-886, 2013.
[9] Andreas Eberle, Arnaud Guillin, and Raphael Zimmer. Quantitative Harris-type theorems for diffusions and McKean-Vlaso processes. Trunsactions of the American Mathernatical Society, 371(10):7355715 2018.
[10] Andre Elisseeff, Theodoros Evgeniou, and Massimiliano Pontil. Stability of Randomized Learning Algorithms. Journal of Machine Learning Research, 6(3):55-79, 2005.
[11] Vitaly Feldman and Jan Vondrak. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. In Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 1270-1279. PMLR, 2019.
[12] Mahdi Haghifam, Jeffrey Negrea, Ashish Khisti, Daniel M Roy, and Gintare Karolina Dziugaite. Sharpened Generalization Bounds based Conditional Mutual Information and an Applica- tion to Noisy, Iterative Algorithms. Advances Neural Information Processing Systems, volume 33, pages
2020.
[13] Moritz Hardt, Benjamin Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. 33rd International Conference on Machine Learning. ICML 2016, 111868-18777 2015.
[14] Leonard Hasenclever, Stefan Webb, Thibaut Lienart, Sebastian Vollmer, Balaji Lakshmi- narayanan, Charles Blundell, and Yee Whye Teh. Distributed Bayesian Learning with Stochastic Natural Gradient Expectation Propagation and the Posterior Server. Mach. Learn. Res., 18(1): 3744-376 3780, 2017.
[15] Yunwen Lei and Yiming Ying. Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 5809-5819, PMLR, 2020.
[16] Jian Li, Xuanyuan Luo, and Mingda Qiao. On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning. In International Conference on Learning Representations, 2020.
[17] Wenlong Mou, Liwei Wang, Xiyu Zhai, and Kai Zheng Generalization bounds of sgld for non-convex learning: Two theoretical viewpoints. In Proceedings the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 605-638. PMLR, 2018
[18] Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M Roy. Information-Theores Generalization Bounds for SGLDD via Data-Dependent Estimates. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
10

---

[19] Gergely Neu, Gintare Karolina Dziugaite, Mahdi Haghifam, and Daniel M. Roy. Information- theoretic generalization bounds for stochastic gradient descent. Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 3526-3545. PMLR, 15-19 Aug 2021.
[20] Bernt Øksendal. Stochastic differential equations. Springer, 2003.
[21] Grigorios A. Pavliotis. Stochastic Processes and Applications, volume 60 of Texts in Applied Mathematics. Springer New York, 2014.
[22] Ankit Pensia, Varun Jog, and Po Ling Loh. Generalization Error Bounds for Noisy, Iterative Algorithms. In IEEE International Symposium on Information Theory Proceedings, volume 2018-June, pages 546-550. Institute of Electrical and Electronics Engineers Inc., 2018.
[23] Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-Convex Learning via Stochas- tic Gradient Langevin Dynamics: A Nonasymptotic Analysis. In Proceedings of Machine Learning Research, volume 65, pages 1-30. PMLR, 2017.
[24] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. The Journal of Machine Learning Research, 11:2635-2670, 2010.
[25] Yee Whye Teh, Alexandre H Thiery, and Sebastian J Vollmer. Consistency and Fluctuations For Stochastic Gradient Langevin Dynamies. Journal of Machine Learning Research, 17(7):1-33, 2016.
[26] Cédric Villani. Optimal Transport: Old and New, volume 338 of Grundlehren der mathematis- chen Wissenschaften. Springer Berlin Heidelberg, 2009.
[27] Feng Yu Wang. Exponential Contraction in Wasserstein Distances for Diffusion Semigroups with Negative Curvature. Potential Analysis,
2020.
[28] Yu-Xiang Wang, Jing Lei, and Stephen E Fienberg. Learning with differential privacy: Stability, learnability and the sufficiency and necessity erm principle. The Journal of Machine Learning Research, ((1):633336639) 2016.
[29] M Welling and YW Teh. Bayesian learning via stochastic gradient langevin dynamies. Proceed- ings of the 28th International Conference on Machine Learning, ICML 2011, 2011.
[30] Aolin Xu and Maxim Raginsky. Information-thewne analysis of generalization capability of learning algorithms. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[31] Pan Xu, Jinghui Chen, Difan Zou, and Quanquan Gu. Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization. In Advances Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
[32] Ying Zhang, Ömer Deniz Akyildiz, Theodoros Damoulas, and Sotirios Sabanis. Nonasymp- totic estimates for stochastic gradient langevin dynamics under local conditions in nonconvex optimization, arXiv preprint arXiv::19000000 2019.


Reviews:
[{"review_id": "ijcx7Ief2YH", "reviewer": "Reviewer_hd8z", "summary": "The paper derives time-independent generalization bounds for (discrete- and continuous- time) SGLD under dissipativity and smoothness assumptions. The main novelty of the new bounds appears to be the fact that they decay to zero as the sample size increases. The authors claim that the theoretical approach is different to prior related works on SGLD as it relies on the framework of uniform stability.", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "Before everything, let me say that I am not quite familiar with this line of work on analyzing SGLD in non-convex settings. Thus, even though I have not found a technical issue in the proof sketch in the main body, I cannot guarantee correctness of the all the proofs. \n\nIn general, the paper is well written with only a few typos. Main results and accompanying assumptions are clearly stated. Also, comparison to related literature is thorough and seems satisfactory, although at certain places it is mostly targeting the expert reader rather than the general Neurips audience.\n\nI understand from the presentation that the results are novel and the technique differs from previous most closely related works. In particular, it is claimed that the authors are the first to bring the contraction property of Langevin dynamics in Wasserstein distance from the optimization/sampling literature to generalization analysis. \n\nHowever, I am not convinced about the consequences of the new bounds. What do we learn from them about SGLD behavior (that is perhaps surprising or new)? Are there any implications ---even at a high-level--- about SGD schemes used in practice of non-convex optimization? Does it say something about how to choose the learning parameter? Or under what conditions on loss and data is generalization good?\n\nI would like to see more such discussion and insights on the bounds that would also benefit the broader Neurips crowd. \n\nOther questions:\n1. Why are *time-independent* bounds desirable? Wouldn't it be better that they depend on time so that they are informative about the algorithm's evolution over time. This seems to not be explained in the paper.\n\n2. Lines 84-85: How do your assumptions on the learning rate relate to practical choices?\n\n3. Equation end of page 4: Why is the weight-decay in the form of \\ell_2, rather than \\ell_2^2 norm? Also, is the weight decay needed here for the analysis?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I would like to see more discussion on the consequences of the new bounds in the practice of non-convex optimization. See above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "bXXbZEMO-u", "reviewer": "Reviewer_Ki1F", "summary": "In this paper, the authors investigate the stability of stochastic gradient Langevin dynamics (SGLD) with varying data sets. They prove a time-independent stability bound for SGLD in non-convex settings. And their analysis can also be used to analyze other variants of SGLD.\n\nMore specifically, the reviewer summarizes their contribution as follows: In this paper, they bound the generalization error to show the stability of SGLD. As claimed by the authors, unlike existing bounds for SGLD in non-convex setting, their bound is time-independent and decays to zero as data size increases.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "Quality, significance: Overall, the reviewer thinks this is a good paper.  They give a time-independent bound for generalization error in non-convex setting. There haven't been any results like this before. (This is claimed by the author, in fact, the reviewer is not familiar with the reference in this area.) The reviewer thinks this is an interesting and reasonable improvement. \n\nClarity: On the whole, the review thinks the organization of this paper is clear. But there are still some misleading parts, the review will mention them in \"Limitations\". \n\nOriginality:  The review thinks this paper is novel enough to be published. The reviewer has done some research in Langevin dynamics before. So the reviewer thinks that the idea in this paper is not very surprising and creative. But it's good that the author can combine different results together to bound the generalization error. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There are several limitations and concerns that the reviewer wants to mention:\n1. The authors mention they require the learning rate to be sufficiently large relative to n. This is counter-intuitive. The reviewer thinks if \\eta is small enough, then the whole system will converge to an SDE. And it's often easier to study the stability of SDE. Can the authors give more comments on this?\n2. In Theorem 3.1 and 4.1, the authors give an equal requirement for time step $\\eta$ in the discretization case. This seems too strict. Is it possible to give a looser requirement for $\\eta$? \n3. The authors need a weight term in their result, is this purely technical? \n4. The reviewer quickly went through the proof of Proposition 4.2 (Appendix E.1). The reviewer is curious about how the authors get the second inequality in (18).  It seems the authors use the contraction property of Langevin dynamics (Lemma 3.4). But the assumptions of Lemma 3.4 are no longer true in Section 4. The reviewer might miss something.\n5. Although the authors give an improved result, the paper lacks applications. Is it possible to give some applications?\n\nThere are some structural problems and typos that the reviewer wants to mention:\n1. The authors put the definition of $\\bar{F}_S$ at the beginning of Section 3. This is weird since this definition is also used in Section 4. \n2. In Section 4, $m$ is abused. It is used for both dissipative constant and iteration steps.\n3. There are a lot of parameters in this paper. The authors might recall the origin of some parameters when they use them. One example is $\\lambda$ in Theorem 3.1 and 4.1. \n4. When the authors mention continuous-time algorithm or discrete-time algorithm, the authors can also cite the equations. Then it will be more clear to readers.", "review_text": "", "extra_scores": {"ethical_concerns": "I think there aren't any ethical issues with this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "LvqNxgTYKRt", "reviewer": "Reviewer_WU19", "summary": "The paper proves generalization bounds for stochastic gradient Langevin dynamics (SGLD) for nonconvex functions. Previous bounds for SGLD in similar settings typically goes to infinity as time or the number of steps increases. This work gives bounds that are independent of time, and also decreases to 0 as the sample size $n$ grows.\n\nSimilar to previous bounds, the authors prove that SGLD is uniformly stable, which is known to imply good generalization. The proofs of stability proceed by starting with the continuous version of the algorithm, and then apply discretization techniques to get guarantees for the discrete-time SGLD. This discretization leads to a slower rate: the bounds are $O(1/n)$ vs $O(\\sqrt{d/n})$ for Lipschitz loss functions plus weight decay, and $O(1/n^{1/3})$ vs $O(1/n^{1/6})$ for the full dissipative case without the Lipschitz-ness assumption.\n\nFor Lipschitz loss functions, it is sufficient to control the 1-Wasserstein distance ($W_1$) between the distributions induced by two neighbouring datasets. The nontrivial step is Lemma 3.4, which shows that conditioning that the differing data point, $n$, is not in the minibatch, some proxy for $W_1$, $W_g$, actually gets contracted due to the regularization term. Then, as long as the minibatch size is relatively small, the overall distance also gets shrinked. This leads to the time-independent bound on stability.\n\nThe proof becomes more challenging without the Lipschitz-ness assumption, since controlling $W_1$ alone does not guarantee stability. The authors show that controlling $W_2$ instead would work, though the contraction proof becomes more involved.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "I found the paper very well-written, as it includes sufficient motivation and background for the problem, and the main paper contains an appropriate amount of technical details to allow the readers to understand the general proof strategy.\n\nI have two questions:\n- Theorem 3.1: The precondition requires the minibatch size, $k$, to be relatively small to the dataset size $n$. In particular, the theorem does not seem to hold for the full gradient setting $k = n$, whereas the result of Li et al. [16] (only) holds for this setting. Some discussion about this distinction could be helpful.\n- Line 298: Is $\\mathbb{E}\\|A(S)\\|^2 \\le s^2$ an additional assumption for Theorem 4.1 to hold (instead of something that can be proven)? If so, it should also appear in the theorem statement.\n\nThe analyses follow a similar roadmap to those of previous stability bounds, though a few new tools (like considering both $W_1$, $W_2$ and their proxies under different settings) are needed to establish the required contraction phenomena and time-independent bounds. My only reservation is that the applicability of the results to actual ML settings, since they either require $d \\ll n$ (which is not true for overparametrized models) or the dissipativity condition which is too strong to hold for real-world loss functions. That said, the current paper already contains interesting new results to a problem of much recent attention, so I recommend accept.\n\n===Added After Author Response===\n\nI have read the authors' response, and would like to thank the authors for answering the questions. My overall evaluation of the paper stays positive.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequately addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "8P4NJPhZAKu", "reviewer": "Reviewer_v2Zx", "summary": "This paper proves generalization bounds for SGLD under dissipativity and smoothness assumptions. A nice feature of these bounds is that they are \"time-independent\" and uniformly hold across all iterations. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "*Main Comments*\n- The paper requires a more detailed comparison with previous work and a better interpretation/justification for the bounds (see below). \n- Although the \"time-independent\" bounds are elegant, and the analysis is novel, I do not understand the utility of these bounds even in theoretically understanding the fundamental dependencies on the dimension, batch-size or the step-size in the discrete setting. In these terms, the paper needs to be better motivated for the machine learning audience. \n\n*Details*\n- In Theorem 3.1, the constants $C_1, C_2, C_3$ depend exponentially on the $M, L, \\beta, \\lambda$. Is there a lower bound that justifies this bad dependence? \n- In this theorem, please explain the effect of the regularization - how does it help the generalization (does the bound capture the difference between the regularized case, and when $\\lambda = 0$)? SImilarly, what is the effect of the batch-size $k$ (do we expect better generalization bounds for smaller batch-sizes)? What is the intuition behind the $\\eta \\geq C_1 \\frac{k}{n}$ condition needed in the theorem?\n- It would be helpful to compare Theorem 3.1 to the bounds obtained in the previous work, for example, [22]\n- Similarly, for Theorem 4.1, please compare the obtained bounds to the previous work. And are there corresponding lower bounds to explain the dependence on $n$, and the exponential dependence on the constants? It is unclear to me which dependencies are fundamental vs those that are limitations of the analysis technique. \n- Comparing the bounds in Theorems 3.1 and 4.1, with the Lipschitz assumption, the bounds for the discrete case are better in $n$, but suffer a dimension dependence. For Thm 4.1, the discrete case bounds have worse dependence on $n$ which makes sense, but they do not have a dimension dependence. What is the reasoning behind this?\n-  \n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper has been received with mixed impressions. I mostly agree with the bottom-line of the reviews: the paper does introduce novel results and techniques to the line of work on generalization of SGLD, and there should be sufficient interest at NeurIPS for such a contribution; yet on the other hand, it is unclear how significant are the actual bounds derived, and the paper does not provide ample discussion/comparison around this.

As some of the reviews alluded to, the significance of the dimension-dependant bounds is questionable (under the assumptions the paper makes, $\sqrt{d/n}$-type bounds can be obtained, independently of the algorithm, from generic uniform-convergence arguments; the authors response to this point is unconvincing).  While the dimension-independent bounds (Theorem 4.1) seem more compelling, for truly appreciating them I would have liked to see a more nuanced discussion of their relation to existing bounds, as well as a more careful analysis of their precise dependence on the problem parameters.

All considered, my decision is to accept the paper - but I urge the authors to carefully address the primary concerns raised in the discussion for the final version and carefully clarify their contribution and its relation to existing generalization bounds.

Decision: Accept (Poster)