Generalization of noisy SGD in unbounded non-convex settings
Authors: Leello Tadesse Dadi
Volkan Cevher
Venue: ICML 2025 poster (2025)
Keywords: Information theoretic generalization
Langevin
SGD
differential privacy
Primary area: theory->optimization

Abstract: We study generalization of iterative noisy gradient schemes on smooth non-convex losses. Formally, we establish time-independent information theoretic generalization bounds for Stochastic Gradient Langevin Dynamics (SGLD) that do not diverge as the iteration count increases. Our bounds are obtained through a stability argument: we analyze the difference between two SGLD sequences ran in parallel on two datasets sampled from the same distribution. Our result only requires an isoperimetric inequality to hold, which is merely a restriction on the tails of the loss. Our work relaxes the assumptions of prior work to establish that the iterates stay within a bounded KL divergence from each other. Under an additional dissipativity assumption, we show that the stronger Renyi divergence also stays bounded by establishing a uniform log-Sobolev constant of the iterates. Without dissipativity, we sidestep the need for local log-Sobolev inequalities and instead exploit the regularizing properties of Gaussian convolution. These techniques allow us to show that strong convexity is not necessary for finite stability bounds. Our work shows that noisy SGD can have finite, iteration-independent, generalization and differential privacy bounds in unbounded non-convex settings.

Generalization of Noisy SGD in Unbounded Non-convex Settings
Leello Dadi
Volkan Cevher
Abstract
Formally, they show under reasonable assumptions that
ggnnralization gap(A, so (VILAD))))
(
We study the generalization of iterative noisy gra- dient schemes on smooth non-convex losses. For- mally, establish time-independent informa- tion theoretic generalization bounds for Stochas- tic Gradient Langevin Dynamics (SGLD) that do not diverge as the iteration count increases. Our bounds are obtained through a stability argument: we analyze the difference between two SGLD se- quences in parallel on two datasets sampled from the same distribution. Our result only re- quires an isoperimetric inequality to hold, which is merely restriction on the tails of the loss. We relax the assumptions of prior work to establish that the iterates stay within a bounded KL diver- gence from each other. Under an additional dis- sipativity assumption, show that the stronger Renyi divergence also stays bounded by establish- ing a uniform log-Sobolev constant of the iter- ates. Without dissipativity. we sidestep the need for local log- log-Sobolev inequalities and instead ex- ploit the regularizing properties of Gaussian con- volution. These techniques allow us to show that strong convexity is not necessary for finite stabil- ity bounds and thus for finite generalization and differential privacy bounds.
where the input-outpur mutual information I [(A(D), D) measures the dependence of the algorithm's 's output on the observed samples D. Unlike uniform-coo sefform-converrence-bbasss bounds, information-theoreiic bounds depend on the algo- rithm and the data distribution. This makes them well suited to assess the performance of models whose complexity ren- ders vacuous all classic uniform--convergence bounds. More importantly, they align with the practical observations that generalization is data distribution dependent, as observed in experiments contrasting random versus real labels (Zhang et al., 2021).
For them be useful however a major difficulty remains in controlling this input-output mutual information for specific algorithms. Of particular interest for machine learning are algorithms obtained as iterative noisy gradient schemes. A standard template that these possess is the following. For a given dataset D, a set of weights are randomly initialized Xp E Rdd then updated following the recursion
X Noise(Gradient step(Xx: D))
(1)
The information enformation-thhoretii analysis of these algorithms was initiated in (Pensia et al., 2018) where the gradient step is assumed to be bounded. Their results, as well as sev- eral follow-ups, are derived by viewing the algorithm as composition of individual steps analyzed separately. As consequence, after T iterations of the algorithm, the bounds obtained on I(Xr, D) scale O(T) O(vT) for fixed non-vanishing step-sizes. The introduction of well-chosen analytical tools like data-dependent priors (Haghifam et al., 2020), or the clever refinements of (Bu et al., 2020) im- prove the bounds but still fall short of improving the time dependence.
1. Introduction
Learning algorithms whose outputs not highly sensitive to the specifics of their training data are likely to generalize well. This is the intuitive idea that undergirds the frame- work of iiformation-thhoreee contributions of Russo & Zou (2016) and Xu & Raginsky (2017) establish that the expected generalization gap of an algorithm A can be controlled by the amount of information the algorithm extracts from its training dataset 'D of size n.
generalization. The seminal
The step-wise analysis leads to vacuous generalization bounds iterations increase even if the recursion in equa- tion converges to limit. Even more curious is the fact that this limit approximates the Gibbs distribution e e where F, is the optimized training loss, which has been shown to achieve a finite information-theereticc bound (Xu & Raginsky, 2017; Pensia et al., 2018). We are faced with
EEFL, Lausanne, Switzerland. Correspondence Lecllo
Dadi <leello dadi @epfl.ch............
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Generalization of Noisy SGD in Unbounded Non-convex Settings
the strange situation where the iterates have an exploding bound but converge close to distribution that has finite one. Our aim in this work amend this strange gap to answer
all the iterates verify a uniform log-Sobolev inequality, a result which, to date, was only shown under strong convexity.
the following question:
As dissipativity is crude assumption used control the log-Sobolev constant that often introduces constants ex- ponential in dimension, we establish secondary result that removes the dissipativity assumption but exploits ergodicity. Our bound in this case is polynomial in dimension and in the Gibbs' distribution's log-Sobolev constant. Unlike the analysis of (Futami & Fujisawa, 2024) who use dissipativity and rely an involved ex- tension of the parametrix method to unbounded drifts (Bally & Kohatsu-Higa 2015), our analysis relaxes dis- sipativity and only exploits the regularizing properties of Gaussian convolution.
Do noisy iterative schemes in non-convex settings admit generalization bounds that go to zero as n + 0o without becoming vacuous as the number of iterations increases?
Our main motivation for tackling this question is to under- stand whether early-stopping is necessary for generalization. If generalization gaps indeed diverge as iterations increase, then long training runs with non- non-vanishing step sizes are proscribed, by theory. If the divergence is merely the result of loose analysis, then we should be able to establish better bounds that are more faithful to practice, where long train- ing runs are common (Power et al., 2022; Nakkiran et al., 2019).
2. Setup
We thus want to establish properties of noisy iterative schemes in their most realistic setting, i.e., when they are run for thousands of iterations with non-vanishing step- sizes. The algorithm we study as a representative of such schemes is noisy SGD, or Stochastic Gradient Langevin Dynamies (WelD) & Teh, 2011). To study its generalization, we show that characterizing its stability is sufficient. Informally speaking, if SGLD outputs weights that are close (in a well-defined sense) when ran on two, different, independentty-saaplle datasets then it must not be overfitting. The difference between the outputs of SGLD measured using the KI. and a stronger Rényi divergence re- lates to the expected generalization of the algorithm. Rényi stability goes further and also relates differential privacy, notion closely related to generalization. Through these techniques, we will show that noisy iterative schemes can have finite generalization and privacy bounds in unbounded non-convex settings, even when run for a large number of iterations. We make the following precise contributions.
2.1. Notation
A central object in our analysis will be probability distri- butions over R All considered distributions are abso- lutely continuous with respect to the Lebesgue measure and admit a continuously differentiable density. For a distribution a over Rd, we will conflate the distribution and its density and denote Vlog as the gradient of its log-density and E, the expectation under a. For q 0, the q-Rényi divergence of a with respect to b is given by D, (alb) = --و log (E, [()) It is generalization of the Kullback-Leible divergence (or relative entropy) which is recovered by taking the limit DKL (alb) == D (alb)= == limg-1 D, (albb). For random variables X, Y with distri- bution a, 6, we will denote, with slight abuse of notation D, (XIY)= == D2 (allb).
2.2. Empirical loss minimization with SGLD
In supervised learning, the aim is minimize a popula- tion risk of the form F(x) = [fr, Z)] with respect to E Rd where Z ~ is some unknown probability mea- sure over some set Z. Given access to dataset D of n in- dependent, identically distributed samples D = Zi...., Zn from V. we optimize the empirical approximation F,, given by (x, D) = 1 E.= f(x, Z.). We perform this min- imization by assuming access to unbiased estimates of the gradient of VE, of through minibatches of the form g(x, B) [B] Eie fz Z;) where B = ii...., in C [l...., n) are i.idd uniform indices chosen from [n]. We have that Eg [g(x, B)] = V (2. D). With this in hand, the recursion we study minimize F,, is the following. An initial set of weights X, E Rdd is randomly sampled, then updated as follows
Contributions:
Under structural assumption on the optimized loss, namely dissipativity, we show that uniform-in-ti bounds can be established for both generalization and (e, o)ddiffferetta privacy of noisy SGD. Our bound only involves stability-related quantities and does not rely on ergodicity. We thus improve over the prior work in this setting namely (Farghly& & Rebeschini, 2021; Futami & Fujisawa, 2024; Zhu et al., 2024) who either rely on ergodicity (thus involving non-stability related constants) or obtain bounds that do not decay to zero as n + 20.
To achieve our result, we resolve in passing an open question of (Vempala & Wibisono, 2019) on the isoperimetric properties of the biased limit of discrete Langevin iterates. We show that under dissipativity,
2n No+1
X = X -ng(XA, Bb) + VV
(SGLD)
2

---

Generalization of Noisy SGD in Unbounded Non-convex Settings
where 7/ > 0 is the stepsize, (Bk) is (conditionally) independent sequences of batches, (N&) & are independent (O, I) random variables, and [ > 0 is temperature parameter that scales the amount of noise injected. We refer to this recursion as noisy SGD as it corresponds to the SGD iterates with additional Gaussian noise added on top.
2.4. Differential privacy
A closely related notion generalization is differential pri- vacy. For e, 6 > 0, (e. 6)Diffeerent privacy (Dwork, 2008) is standardized formalization of the notion of privacy. A useful interpretation of it is given by (Wasserman & Zhou, 2010) who show that an (e, dddfferrnnt privacy guaran- tee on an algorithm IP Px|e outputting weights X given a dataset D, equates to a guarantee that no statistical test (or mull-hypothesis test) on the output can reliably determine if specific data point was part of the training set D. The false-positive and false-negative rates of any such test will be controlled by and 6. Algorithms with small and 8 are those for which no powerful test exists. Remarkably, as shown below, stability in terms of the stronger Rényi divergence implies that an algorithm is (e, -ddifffrrett private.
2.3. Information theoretic generalization
A quantity of interest is how well optimizing the empirical proxy Fn transfers to F. The SGLD algorithm ran for k iterations is a randomized algorithm that outputs a random variable X3 with distribution Px, x, D and the gap
v) == [RD, [F(X*) - Fa(Xx, D)]1
where the expectations is taken with respect to D ~ van and X PX,IDD measures how well the algorithm gener- alizes through the discrepancy between the loss achieved on the empirical loss versus the population one. Using a change of measure argument, (Xu & Raginsky, 2017) show that the following assumption is sufficient to control the generalization gap.
Lemma 2.3 (From Rényi stability to (e, 6DDP (Thm.21 (Balle al., 2020))). Let Px,ND be a randomized algorithm oulputting weights given dataset D. Let q > 1, > O. If Da (Px,IDl px,,)))) I foo D'D' adjacent datasets, then Px,ID is (e+ log 1/5-lom(a) + log 2-1 ( -'differrettially private for any 0.
Assumption 2.1 (Sub-Gaussian loss). There exists Gag >
such that for any w E R&, the random variable f(w, Z) is with variance proxy e when Z v
The study of the privacy properties of noisy iterative schemes appears in (Minami et al., 2016). A comprehensive treatment from perspective of privacy amplification by iteration in convex setting is provided in (Feldman et al.. 2018) 8) using Rényi differential privacy (Mironov, 2017). Fundamentally, the technical problem of showing stability is identical for generalization and privacy, which is why we mention differential privacy here. The analysis of (Ganesh & Talwar, 2020; Chourasia et al., 2021; Ye & Shokri, 2022) establishes iime-independent privacy bound for strongly convex settings with deterministic and stochastic gradients. Going beyond convexity as noted in (Ganesh et al., 2023) remained an open question.
For losses verifying the assumption above, (Xu & Raginsky, 2017)'s work shows that KL stability of the algorithm con- trols the expected generalization gap (see Appendix F for short proof).
Lemma 2.2 (From KL-stability generalization). Let D, D' be two independent samples from u uan, It holds under Assumption 2.1 that
20og E DDa (Px, pol px
gen gen(Fx.te (X),ID,
n
2.5. Isoperimetry
To control the generalization gap, it therefore suffices to control distance between two sets of SGLD iterates ran on two datasets 'D and D' (see figure 1). Formally, by considering the KL divergence between iterates of
In our work, we relax the strong-convexity requirements to assumptions of dissipativity and isoperimetry. The in- equality below is referred to as an isoperimetric inequality since it implies Gaussian (or uniform on the unit sphere) like concentration properties on the distribution (Gozlan, 2009).
2m 3
Xx+1 Xx (X BR) + +V{
No+1 and
(2) Definition 2.4 (LSI), A distribution b is said to verify the lobole inequality (LSII with constant e if for any a < b.
2n
X = X - ng (X BB)
+
V
No+1
3
which are two sequences SGLD iterates on two different independent datasets 'D and D', we obtain upper bounds on the generalization gap.
Cb - E, [|V log a - V log [og]
DKL (allb) <
2
A random variable X is Gabbsiansninn with proxy if for E TR, log F. [expAX(XX - EE())] S X²2/2
Instead of assuming strong convexity of the optimized loss Fns we assume in the following that the Gibbs distribution
3

---

Generalization of Noisy SGD in Unbounded Non-convex Settings
with density proportional to e satisfies the LSI. A pre- cise discussion on which conditions of Fn. yield the LSI is provided in section 5. Moreover, our main technical tool will rely on showing that the outputs Xx of equation SGLD all satisfy the LSI with a constant that is uniform in k. It was unknown if such a uniform bound held without strong convexity. (Vempala & Wibisono, 2019) include a proof under strong-convexity in their last arxiv modification and (Altschuler & Talwar, 2022) specifically study this question under convexity. The lack of uniform LSI was the bottle- neck that prevented analyses from capturing non-convex settings and required (Vempala & Wibisono, 2019) to state the uniform LSI as assumption(Assumppil 2).
Gredicat Nu
Noise
X2+3
Exxpansion
Contraction
Noise
Figure 1. Analysis template
camnot be readily applied to SGLD to take into account the algorithm which is the primary goal of our work.
4. Analysis template
3. Related Work
In this section, we describe the analysis template depicted in Figure which will allow us to establish KL. and Rényi stability through a step-wise analysis of each iteration k. Our central contributions follow in later sections. Earlier versions of this template appear in (Chourasia et al., 2021) and (Ye & Shokri, 2022nnpp D.7), who refined the Rényi analysis of (Vempala & Wibisono, 2019). Our anal- ysis relies on showing that, at each iteration, there is an expansion followed by a contraction.
Several authors have considered the question of time depen- dence of generalization bounds of noisy iterative schemes. The work of (Mou et al., 2018) was the first to notice that each step includes a decay factor that can compen- sate for step-wise increases derived in previous analyses. Unfortunately, only a degrading decay factor established, making vanishing step-sizes mandatory. (Li al., 2019) build their result to show time-independent bound for non-convex losses obtained as bounded perturbations of strongly convex loss. Unfortunately, their bounds do not go to as n + co. In bounded settings, where a projection step follows each noisy gradient update, the work of (Wang et al., 2023) and (Chien et al., 2024) establish that a uniform decay factor can be established. They show that if each iteration of SGLD is followed by projection on convex set C, then constant decay factor that depends on exp (diam(C)/n) can be established.
Before diving into the analysis, we ease the computations by assuming that the sequences of batches are chosen before the start of the recursion. In other words, analysis conditioned on B (Bx))s by using the fact that conditioning increases Dg (see 7.11 in (Polyanskiy, 2019)).
conduct the
That is, for any distributions a, b.
Dg (alb) S EB [D, [a]BIb|BB]
when q 2 1. Consequently, we can conduct the analysis for a fixed non-random sequence of batches, and then take the expectation of the final result with respect the batch selection. This is the standard simplification for analyzing stochastic gradients (Wang et al., 2023; Ye & Shokri, 2022).
Fewer papers tackle the unbounded setting. Using coupling techniques, (Farghly& & Rebeschini, 2021) establish a time- uniform bound but incur inelegant step size dependences and do not obtain a bound going to as n + do for fixed stepsizes. The recent work (Zhu et al., 2024) considers the same dissipative setting and exploits Markov chain pertur- bation results but their Wassertein analysis requires that Lipschitz losses be used to measure the generalization gap. The work most closely related to ours is (Futami & Fuji- sawa, 2024). For dissipative losses, their result involves dimennion-deependent quantities unrelated stability. We show that the dissipative setting is friendly enough to not require such constants, and we improve their analysis to remove the dissipativity assumption under ergodicity. We include table for ease of comparison in Table 1.
The first step of our method consists of decomposing the noise term as follows
2n 3
X X -ng(Xx. BB) +
Nk+1
= =X n BB) +
(1) K+1
K+1
Expunsion term
Contraction term
7 (2)
=: Xx+11/2 +
V
(3) where we have split the random variable N841 into two k=1
Observe that the fast 1/n rate achievable with information theoretic bounds comes with drawbacks. (Wang et al., 2023) achieve the fast rate only for k < n. In other words the result only holds for the first epoch of training. Other bounds obtaining the fast rate (see GRodriguez-Gálvezz et al., 2024))
independent (N 1) variables v² and 22(2) K+11 A single update therefore corresponds to two consecutive half steps, the first going from X₃ to X (the gradient update half- step) and second going from X Xx+1/2 to X (the noise
4

---

Generalization of Noisy SGD in Unbounded Non-convex Settings
non-convex
un-bounded domain
Bound
(Chourasia al., 2021; Ye Shokri, 2022) (Raginsky et al., 2017)
X
O
(1/vn) (g exp -////x + 1/m)
(Mou et al., 2018)
X
o
Vog K/n
(Farghly & Rebeschini, 2021)
0
(1/(m/11)
+ vn)
(Futami& & Fujisawa, 2024)
o
I+C with C d, b, m-dependent
(1/aa) if
(Wang al., 2023; Chien al., 2024)
0
[/nn with (Chien et al., 2024)
Present work
0
Vinn
Table Our result matches the strongly-conve bound of (Chourasia al., 2021; Ye & Shokri, 2022) in the un-bounded, non-convex setting. Crucially, our techniques avoid the additional non-explicit constants appearing in (Futami & Fujisawa, 2024).
step). We analyze these half-steps in what follows for the iterates (Xx).. (X²);: defined in equation 2.
Additive Gaussian noise channels) has been well explored in the sampling literature (Wibisono & Jog, 2018; Vempala & Wibisono, 2019; Chewi et al., 2021). In particular, (Chen et al., 2022) generalize a result of (Vempala & Wibisono, 2019) to derive the following contraction theorem.
4.1. Expansion half-step
The control of the divergence along the first half-step will result from the analog of the chain rule for q-Rényi diver- gence. We can show that the following bounded expansion holds.
Theorem 4.3 (Adapted from (Chen et al., 2022) Theorem 3). Let Xk+1/2 and X k++122 12 the gradient half-steps as defined in equation 3. If (X all verify the LSI with constant a, then after simultaneous heat flow Xx+1/2 +
Theorem 4.1 (Bounded expansion). Let Xk-1/2 and 1/11/2 be the gradient update half-steps in equation 3, then
Vn/BN BN and X 1+//2 /2" + v1/3N', with N,N ~ ~N( I).
we have that
Dg (Xa+i|X SDDa (ePP(Xxt////) (X++1/2lxx+1/2)
Dg (X s Dg (x)
Bu B +
(llo B&) - g (X2, 101
where 7 =(33
1/9 (3tt
30
< 1.
2
where the tilted expectation Ex.g an expectation under a modified density defined Definition A.
If uniform LSI can be established, the addition of noise after each gradient step corrects the overfitting and brings the distributions back to being closer as shown in Figure I. The proofs for this template can be found in A.
The result above tells us that the expansion (or over-fitting) induced by the gradient step can be controlled by the term
4.3. Combining the steps
S = Ex,g (llsalll(x X B&) ( 1
(4)
With the bounded expansion and approximate contraction results, it suffices to unroll the recurrence to obtain time- independent bounds. By combining theorems 4.1 and 4.3, obtain the following single-step result.
which is a quantity that measures how sensitive gradients are with respect to changes in the dataset.
Remark 4.2. Observe that since Sp Bx] 2lEr, Bx)]] upper bounds involving S& can be transformed to upper bounds involving gradient norms (or gradient variance) along the trajectory.
Theorem 4.4 (Single step bound). Lef k N, (Xx) and (XL) the two sets of SGLD iterates defined equation 2. If (X) (X 22/22 all verify the LSI with contant a, we have that
By
Dy (Xx=11X++1 S SDD (X+(X) +77
St
2
4.2. Contraction half-step
where St. is the gradient sensifivity in equation 4 and 7 1/9
After the expansion half-step, the next iterates are obtained by simply adding the remaining half of the Gaussian noise. In other words, the next iterates are obtained after simulta- neous Gaussian convolution (or diffusion along heat flow). This parallel addition of independent Gaussian noise (or
<1
Bart
Under bounded gradient sensitivity (equation 4), this geo- metric recurrence given above remains bounded for i ++
5

---

Generalization of Noisy SGD in Unbounded Non-convex Settings
Poincare lequulity
5.1. Strongly convex setting
Log Scholev inqqulity
In the literature, uniform LSI constants have only been established in strongly convex settings (Ganesh & Talwar, 2020; Ye & Shokri, 2022; Chourasia et al., 2021; Vempala & Wibisono, 2019). The uniform constants are obtained by noticing that if f((;z) is m--troonly convex for all 2, then Xx+1 is obtained by applying a (1 - mpn)-Lipschitz gradient mapping to X₃ and adding independent Gaussian noise. Using the stability properties of the LSI constant, can be shown that
Disipative
Twer foais
Stronply ccpves
Canvee
Figure 2. A diagram of the commonly used assumptions. A proof that strongly convex functions are dissipative can be derived from the quadratic lower bound at O. Corollary 2.1.(2) of (Cattiaux al., 2010) shows that dissipativity and lower bounded Hessians imply LSI. The fact that Poincaré incqualities hold for log-concave measures is shown in Corollary 1.9 of (Bakry al., 2008). The proof that LSI implies Poincaré can be found in (Bakry et al., 201 20rooopoonnn 5.1.3).
(i S (iss + "
The geometric sequence stays bounded and yields the de- sired uniform bound on the LSI of Xx. Without strong convexity, the gradient cannot have a Lipschitz constant less than 1 for all 1) S 1. quence derived by considering successive gradient updates and noise gives (xsx(X I (1 + nL) + 33- which can only diverge exponentially as the iterate count increases. We will show that using different techniques, a finite bound can be established under a relaxation of strong convexity.
1.- Consequently, the geometric se-
00. Indeed a simple unrolling yields (Xx( & dg Σt ~ The results thus all hinge on finding 2
a constant a such that all iterates of equation SGLD verify
the LSI inequality with constant a.
5. Uniform LSI under dissipativity
In this section, we show that the iterates of equation SGLD all verify the LSI under a dissipativity assumption on f- For a target distribution иT x e a set of increasingly re- laxed structural assumptions can be made on f to guarantee that admits an LSI constant. A hierarchy of the com- monly used assumptions is given in Figure 2. The iterates of equation SGLD however are evolving distributions so establishing that the structural assumptions hold uniformly for the distribution of the iterates X5 can be burdensome. Luckily the Soboleeeev constant is stable through Lipschitz mappings and convolutions as shown below.
5.2. Dissipative functions
The standard way of relaxing strong convexity is by adding perturbations. A classic result establishes that bounded per- turbations of strongly convex functions still satisfy the LSI, albeit with an exponential degradation (Holley & Stroock, 1988). More recent results show that other types of perturba- tions can preserve the LSI. For instance, if V is strongly con- vex and H Lipschtiz function, then e VV+ff still verifies the LSI (Brigati & Pedrotti, 2024). This setting corresponds precisely to Lipschitz losses with weight decay analyzed by (Farghly & Rebeschini, 2021).
Theorem 5.1 (Operations preserving LSI (Chafai, 2004)).
If the distribution of random variable A is LSI(ca). then the distribution of T(A) is (SI(Lip(T)) c.) and if B is in- dependent from A and LSI(c)), then A + B is LSI(c, + cs).
Another seemingly different relaxation is the requirement that f be strongly convex outside of bounded region. In other words, the gradient of ʃ is strongly monotone outside of some ball. This can be expressed by adding slack b >> 0 to the gradient monotonicity condition to yield
By leveraging these stability results, structural assumptions on the gradient mapping T x ト x v fxx) in SGLD can lead to uniform LSI constants. The following minimal assumption is necessary to show that the gradient mapping Lipschitz.
(x y. Vz()) vf())) 2 ml|a 0 -b
(5)
for all pairs x; x,y- The above condition is known as strong- dissipativity (Erdogdu et al., 2022). We note here that strongly dissipative functions are equivalent to bounded or Lipschitz perturbations of strongly convex functions (see Lem.1 I of (Ma et 2019) or Lem.2.4 of (Brigati & Pedrotti, 2024)).
Assumption 5.2 (Smoothness). For any E Z, the fune- tion + f(z, z) is continuously twice differentiable and there exists L >> 0 such that for any E Z, =z) Vf 2| < [||== - vll.
A step further can be achieved by only requiring one point strong convexity and dropping the y in equation 5. This is akin to the relaxations of strong convexity analyzed in (Karimi et al., 2016) (see their appendix A for hierarchy).
With the above, we can track the log-Sobolev constant throughout the iterations and additional assumptions are then added to ensure boundedness of the constant.
6

---

Generalization of Noisy SGD in Unbounded Non-convex Settings
By relaxing equation 5, we obtain the set of dissipative functions defined as below.
This ensures that the mini-batches are gradients of dissipa- tive functions. The next assumption is mild requirement needed to ensure that the sensitivity terms Sy. equation 4 can be controlled.
Definition 5.3 (Dissipativity)). A function f is (m,b) dis- sipative if for any x E IRd we have that (x. Vz())) 2 m||=||²-bb
Assumption 5.7 (Pseudo-Lipschize) There exists 0, D > 0 such that for any 2, 2, E 2, [V](z,=) Vf(x,=)) S 0||z||| + D
The condition appeared in (Cattiaux et al., 2010) as a simple criterion to ensure the existence of a finite LSI constant. It has then become the standard relaxation of strong-convexity in the sampling and noisy optimization literature (Raginsky et al., 2017; Erdogdu et al., 2022). Indeed, when F is dissi- pative, then e -9F can be shown to admit an LSI constant of the order O (exp(3 + d)).
Corollary 5.8 (Bounded KI. stability). For q = under Assumptions 5.6 and 5.7, for any 2 1 and 311 32m < nj S 21 we have that the iterates X₃ and X of SGLD with stay within a bounded KL divergence from each other given by
m
Our result hinges on the fact that, despite being the broadest relaxation of strong convexity, dissipative functions still admit well-behaved gradient updates.
D (Xx S Bn M + +D2)
(1 (1-
(1-?)
Lemma 5.4 (Dissipative gradient updates are approximately contractive). Let f be an L-smooth, (m, -isssipaaee func-
with 7 = (3o+-1
2n +2b +
2d and with a mB
m
(1 + CLSS + 7 ( where CLSI is the uniform LSI given in Theorem 5.5.
tion, then for any n S 21.'
/m
| - V/ (x))) S 11| + 2()b) with w- = (1 - 1ym) and R = Vn.
+
Remark 5.9. Note that our result readily transfers to sub- exponential losses using the same argument as (Futami & Fujisawa, 2024) Theorem 7.
The secudo-Lipschite assumption which appears in (Zhu et al., 2024) is merely an alternative way of bounding the sensitivity terms S& in equation 4, without requiring a uni- form sensitivity bound when q 1. For other divergences, the pseudo-Lipschitz assumption is insufficient, we need a more stringent L -bounded sensitivity assumption (which can be ensured by clipping gradients (Ye & Shokri, 2022)).
This approximate contraction property gives control of the norms of the iterates of equation SGLD. This allows to show that the gradient mapping under dissipativity ensures that the iterates remain -au-Gaasiinn. A remarkable result of (Chen et al., 2021) then allows us to upgrade this sub-Gaussianity to log-Sobolev inequality.
Theorem 5.5 (Uniform LSI). Let Xo NOO.
IT).
Assumption 5.10 (J -bounde sensitivity). For any ,, E Z. I 2) - ff(z, =2) Sax
V Da
and let f be (m, disssipaive 32m m 2t2 the iterates of equation SGLD all verify a Poincare and log-Sobolev inequality with constants Cp S 4n exp (32 (b d m3+n)(LRR)) and CLSI S 6Cp (32 (b +b+d d (B(R)))))) where R = Db/m.
31 <
S
Corollary 5.11 ity). For q 2 1, under Assumptions 5.6 and 5.10, for any m
privacy under dissipativ-
k 2 1 and 32m < < S 212, we have that the iterates X and X of SGLD stay within a bounded Rényi divergence from each other given by
The proof of this result can be found in appendix B. The bound on the log-Sobolev inequality of the iterates is ex- ponential in dimension, but is of the same order as the LSI constant of the target distribution e -āf (Raginsky et al., 2017). It is thus unlikely that the bound can be improved without additional assumptions. The constant factors in bounds on 1 are loose and can be improved with clever uses of Young's inequality (see appendix C).
B1.S00
Dy (x+lx)) S 44211 - 7)
(1 (11)
1/9 with (Do-T)
Ba
< and a = (1 + nL)) + B.
where CLSI is given in Theorem 5.5.
Our corollaries above imply a time-independent bound for the expected generalization gap (Lemma 2.2) and the privacy loss (Lemma 2.3) under dissipativity. Our bounds solely involve stability-related related constants, just like the strongly- convex bound of (Chourasia et al., 2021)[Thm 3] and they decay to zero as n + 20. Fundamentally the real tool we used was the upgrading behavior of Gaussian convolution. In the next section, we show this is sufficient to remove dissipativity.
5.3. Corollaries under dissipativity
The results dissipative functions allow us to derive the following immediate corollaries of Theorem 4.4. We first state our assumptions.
Assumption 5.6 (Uniform dissipativity). For all 2 E Z, the function x + f(x, 2) is (m, dissiiiipe and T-smhhhh.
7

---

Generalization of Noisy SGD in Unbounded Non-convex Settings
6. Without dissipativity but with ergodicity
rem can then be established.
Theorem 6.3 (Approximate Contraction). Let π ~ 9
In this section, we show that dissipativity is not needed to establish time-uniform generalization bounds as long as the SGLD iterates converge towards a target distribution that verifies the LSI. It is possible to make milder requirements on at the cost of introducing quantities unrelated to stabil- ity: unlike Theorems 5.8 and 5.11, the result in this section will no longer match the strongly-convex lower-bound as it will include additional terms but its dimension dependence improved. We significantly relax the analysis of (Futami & Fujisawa, 2024) which needlessly requires dissipativity and the parametrix method. We instead rely simple tools to show that an approximate contraction result (Theorem 6.3) can replace Theorem 4.3. Instead of requiring per- eer-iterate LSI, Theorem 6.3 only requires the target to be LSI.
be a distribution verifying the LSI with constant G₁ 2 L, whose potential Fn is L-smooth and lower bounded by F For any distribution x' and 0s = ag *N (), be bo (0,tt with V Vlog bo = - we have that
DxL. (ayl (aylby) S e enneee DEL. (nollbo)
+ erg((a by T, x') + ProbConst
where the ergodicity ervor term gathers quantities related to convergence of on. by towards n, म. and ProbConst gathers constants (explicitly given in equation 8 and equation 9).
The approximate contraction established in Theorem 6.3, can be instantiated for our two parallel chains of SGLD to yield the following corollary under the following assump- tions.
6.1. Gaussian convolution and log-Hessian lower bounds
The core of our result in this section relies on relaxing Theorem 4.3 in the analysis template. To do so, we must exchange distributions: we need to swap the per-iterate distribution with the target distribution. The swap only possible if the distribution is sufficiently smooth. The fol- lowing Lemma shows that Gaussian convolution enforces lower bound on the Hessian of log-densities.
Assumption 6.4 (Reasonable loss). For any dataset D, the function F, is L-smooth and lower bounded by F R. The distribution e verifies the LSI with constant Cx and has bounded second moments Ex [[|]]]] < co.
Assumption 6.5 (Bounded variance). The stochastic gradients are unbiased and satisfy EB [lls( X, B) Fy (X) s²
Lemma 6.1 (Hessian lower bound). Let be distribution that results from a Gaussian convolution, i.e. (0 1/1) for some distribution D, then 2 log v - -
Corollary 6.6 (KL stability under isoperimetry). Under assumption 6.4, 6.5. and assuming On 2 1. We have for r S 3 C. the iterates of equation SGLD Xx and X². ran on datasets 'D and D' satisfy
This simple result follows from straightforward computa- tions. Moreover, Gaussian convolution can only improve the log-Hessian lower bound of a distribution (see Lemma E.3). Functions with a Hessian lower bound are convenient as they allow for simple changes of measure:
poly (1), L, d, or dinit; diniis
Lemma 6.2 (Change of measure). Let g : Rd + IR be a for some K E R. Then, for any random variables X, Y over Rdd we have B[ g( gY)] E[-g(X)] + 1 [X))
DKL (X+]X))
twice-differentiable function such that Våg m
CF + e..
1-7
+ K+1 El| X- Y 1
2
where Scuis E, [[] (X)(I) OF DRL (X6l.), di
Eg [|| 2F= dinit
The lemma above gives us the ability to change an expec- tation under Y an expectation under X, and leaves open the choice of coupling between X and Y.
DEL (XIIT',, and 7 = e eene//4 n/48ex,
We prove this Corollary in Appendix D. We are able to show KL stability while making the fewest assumptions on the structure of the optimized loss F,, Our result shows that merely knowing that e =FF, verifies an isoperimetric inequality is sufficient to establish generalization bound that does not degrade the iteration count increases.
6.2. Approximate contraction along simultaneous heat flow
We now have all the tools in hand show that that if the SGLD chains converge to well-behaved limit, then ap- proximate contraction can be established. We begin by observing that the contraction step is applied to half step Xx+1/2 that itself results from a Gaussian convolution since we split the noise in two. Consequently, we know that 2 log Px - & la by Lemma E.2. The following theo-
7. Conclusion
Our Rényi and KL stability bounds directly imply general- ization and differential privacy guarantees for disspativite
7
8

---

Generalization of Noisy SGD in Unbounded Non-convex Settings
objectives, extending results only available for strongly con- settings. Noisy iterative algorithms can be run ad infini- tum with non-vanishing step sizes without early-stopping in non-convex settings. This is an improvement over the previously infinite bounds and is in accordance with the practical observations that long training runs do not always harm generalization and in fact can sometimes improve it (Olmin & Lindsten, 2024).
Brigati, G. and Pedrotti, F. Heat flow, log-concavity, and lip- schitz transport maps. arXiv preprint 2520:5, 2024.
Bu, Y., Zou, S., and Veeravalli, V. V. Tightening mutual information-based bounds on generalization error. IEEE Journal on Selected Areas in Information Theory, 1(1): 121-130. 2020.
Cattiaux, P., Guillin, A., and Wu, L.-M. A note Tala- grand's transportation inequality and logarithmic Sobolev inequality. Probability Theory and Related Fields, 148 (1):285-304, September 2010. ISSN 1432-2064. doi: 10.1007/s00440-00 009-0231-9
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must specifically highlighted here..
Chafaï, Entropies, convexity, and functional inequalities, on phi-entropies and phi-sobolev inequalities. Journal of Mathematics of Kyoto University, 44(2):325-366 2004.
Acknowledgments
This project has received funding from the European Re- search Council (ERC) under the European Union's Hori- zon 2020 research and innovation programme (grant agree- ment n 725594 time-data). This work was supported by Hasler Foundation Program: Hasler Responsible Al (project number 21043). Research sponsored by the Army Re- search Office and was accomplished under Grant Number W911NF-2441-0048
Chen, H.-B., Chewi, S., and Niles-Weed, J. Dimension-free log-sobolev inequalities for mixture distributions. Journal of Functional Analysis, 281 (11):109233, 2021.
Chen, Y., Chewi, S., Salim, A., and Wibisono, A. Improved analysis for a proximal algorithm for sampling. In Confer- ence Learning Theory, pp. 2984-3014. PMLR, 2022.
Chewi, S., Erdogdu, M. A., Li, M. B., Shen, R., and Zhang, M. Analysis of langevin monte carlo from poincar) 'e to log-sobolev. arXiv preprint arXiv:21 12.222221266660 12662, 2021.
References
Altschuler, J. M. and Talwar, K. Concentration of the langevin algorithm's stationary distribution. arXiv preprint 22Xiv:22/2.1266 2022.
Chien, E., Wang, H., Chen, Z., and Li, P. Langevin un- learning: new perspective of noisy gradient descent for machine unlearning, arXiv preprint ar3:1:2401.10371, 2024.
Bakry, D.,, Barthe, F., Cattiaux, P., and Guillin, A. A simple proof of the Poincaré inequality for large class of prob- ability measures. Electronic Communications in Proba- bility, 13(none):60066 January 2008. ISSN 1083-589X, 1083-589X. doi: 10. (0.1214/ECP/ 13- 1352. Publisher: In- stitute of Mathematical Statisties and Bernoulli Society.
Chourasia, R., Ye, J., and Shokri, R. Differential privacy dy- namics of langevin diffusion and noisy gradient descent. Advances in Neural Information Processing Systems, 34: 14771-14781, 2021.
Dwork, C. Differential privacy: survey of results. In International conference on theory and applications of models of computation, pp. 1-19. Springer, 2008.
Bakry, D., Gentil, I., and Ledoux, M. Markov Semi- groups. In Bakry, D., Gentil, I., and Ledoux, M. (eds.), Analysis and Geometry of Markov Diffuusion Operators, Grundlehren der mathematischen Wissenschaften, pp. 3- 75. Springer International Publishing, Cham, 2014. ISBN 978-3-319-00227-9 doi: 10. 00.1077/978-3-31-00222
Erdogdu, M. A., Hosseinzadeh, R., and Zhang, S. Conver- gence of langevin monte carlo in chi-squared and rényi divergence. In Camps- Valls, G., Ruiz, F. R., and Valera, I. (eds.), Proceedings of The 25th International Confer- ence on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pp. 8151- 8 1175. PMLR, 28-30 Mar 2022.
Balle, B., Barthe, G., Gaboardi, M., Hsu, J., and Sato, T. Hypothesis testing interpretations and renyi differential privacy. In International Conference on Artificial Intelli- gence and Statistics, pp. 2496-2506. PMLR, 2020.
Farghly, T. and Rebeschini, P. Time-independent general- ization bounds for sgld in non-convex settings. Advances in Neural Information Processing Systems, 34:19833 19846, 2021.
Bally, V. and Kohatsu-Ba Higa, A. A probabilistic interpretation of the parametrix method. 2015.

---

Generalization of Noisy SGD in Unbounded Non-convex Settings
Feldman, V., Mironov, I., Talwar, K., and Thakurta, A. Pri- vacy amplification by iteration. In 2018 IEEE Annual Symposium on Foundations of Computer Science (FOCS),
Minami, K., Arai, H., Sato, I., and Nakagawa, H. Differ- ential privacy without sensitivity. Advances in Neural Information Processing Systems, 29, 2016.
pp. 521-532. IEEE, 2018.
Mironov, I. Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pp- 263263 275. IEEE, 2017
Futami, F. and Fujisawa, M. Time-independent information- theoretic generalization bounds for sgld. Advances in Neural Information Processing Systems, 36, 2024.
Mou, W., Wang, L., Zhai, X., and Zheng, K. Generalization bounds of sgld for non-convex learning: Two theoretical viewpoints. In Conference on Learning Theory, pp. 605- 638. PMLR, 2018.
Ganesh, A. and Talwar, K. Faster differentially private sam- plers via rényi divergence analysis of discretized langevin meme. Advances in Neural Information Processing Sys- tems, 23:7222-7233, 2020.
Nakkiran, P., Kaplun, G., Bansal, Y., al. Deep double descent: Where bigger models and more data hurt. arxiv: 191 191202292 [cs, stat]. 2019.
Ganesh, A., Thakurta, A., and Upadhyay, J. Universality of langevin diffusion for private optimization, with applica- tions sampling from rashomon sets. In The Thirty Sixth Annual Conference on Learning Theory, pp. 1730-1773. PMLR, 2023.
Olmin, A. and Lindsten, F. Towards understanding epoch- wise double descent in two-layer linear neural networks. arXiv preprint arXiv:2407.0940 07.44447.944,, 2024.
Gozlan, N. A characterization of dimension free concentra- tion in terms of transportation inequalities. 2009.
Pensia, A.,
Jog, V., and Loh, P.-.. Generalization error bounds for noisy, iterative algorithms. In 2018 IEEE International Symposium on Information Theory (ISIT), pp. 546-550. IEEE, 2018
Haghifam, M., Negrea, J., Khisti, A., Roy, D. M., and Dz- iugaite, G. K. Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms. Advances in Neural Informa- tion Processing Systems, 33:9925 99355, 2020.
Polyanskiy, Y. Statistics and Computer Science, 2019. patps://peophs lids. ..s.s.m www.mitt..... mmi..edu/yy homepage/data/LLL
Information Theoretic Methods in
URL
pdf.
Holley, R. and Stroock, D. Simulated annealing via sobolev inequalities. Communications in Mathematical Physics, 115(4):553-56, 1988.
Power, A., Burda, Y., Edwards, H., Babuschkin, I., and Misra, Grokking: Generalization beyond overfit- ting on small algorithmic datasets. arXiv preprint 2rXiv:2201.02/777 2022.
Karimi, H., Nutini, J., and Schmidt, M. Linear conver- gence of gradient and proximal-gradient methods under the oolyak-lojasiewice condition. In Machine Learn- ing and Knowledge Discovery in Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23, 2016, Proceedings, Part 16. pp. 795- 811. Springer, 2016.
Raginsky, M., Rakhlin, A., and Telgarsky, M. Non-convex
learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis. In Conference Learning The- ory, pp. 1674-1703. PMLR, June 2017. ISSN: 2640- 3498.
Rodríguez-Gálver B., Thobaben, R., and Skoglund, M. An information-theoreticc approach to generalization theory. arXiv preprint arXiv:2408. 13275, 2024.
Kinoshita, and Suzuki, T. Improved convergence rate of stochastic gradient langevin dynamics with variance reduction and its application to optimization. Advances in Neural Information Processing Systems, 35:19022- 19034, 2022.
Russo, D. and Zou, J. Controlling bias in adaptive data anal- ysis using information theory. In Artificial Intelligence and Statistics, pp. 1232-1240. PMLR, 2016.
Li, J., Luo, X., and Qiao, M. On generalization error bounds of noisy gradient methods for non-convex learning. In International Conference on Learning Representations, 2019.
Vempala, S. and Wibisono, A. Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices. Ad- vances in neural information processing systems, 32, 2019.
Ma, Y.-A., Chen, Y., Jin, C., Flammarion, N., and Jordan, M. Sampling can be faster than optimization. Pro- ceedings of the National Academy of Sciences, 116(42): 20881 1-0885, 2019.
Wang, H., Gao, R., and Calmon, F. P. Generalization bounds for noisy iterative algorithms using properties of additive noise channels. Journal of Machine Learning Research, 24(26): 2023.
10

---

Generalization of Noisy SGD in Unbounded Non-convex Settings
Wasserman, L. and Zhou, S. A statistical framework for differential privacy. Journal of the American Statistical Association, 105(489) 2010.
Welling, M. and Teh, Y. W. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings the 28th international conference on machine learning (ICMI-II),
pp. 681-688. Citeseer, 2011.
Wibisono, A. and Jog, Convexity of mutual information along the heat flow. In 2018 IEEE International Sympo- sium on Information Theory (ISIT), pp. 1615-1619. IEEE, 2018.
Xu, A. and Raginsky, M. Information-theorrticc analy- sis of generalization capability of learning algorithms. Advances in neural information processing systems, 30, 2017.
Ye, and Shokri, R. Differentially private learning needs hidden state (or much faster convergence). Advances in Neural Information Processing Systems, 35:703-715, 2022.
Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107- 115, 2021.
Zhu, L., Gurbuzbalaban, M., Raj. A., and Simsekli, U. Uniform-ing -nntmm--i--imee wasserstein stability bounds for (noisy) stochastic gradient descent. Advances in Neural Informa- fion Processing Systems, 36, 2024.
Zozor, and Brossier, J.-M. debruijn identities: From shannon, kullback-leibler and fisher generalized - entropies, --divergences and --ffihher informations. In AIP Conference Proceedings, volume 1641, pp. 522-529. American Institute of Physics, 2015.

---

Generalization of Noisy SGD in Unbounded Non-convex Settings
A. Analysis template proofs
In this section we provide proofs for the results in the expansion-conttaction template. The first result we prove the bounded expansion result. We first define the tilted expectation.
Definition A.1 (q-tilted Expectation). For any function h, the tilted expectation Ex, is an expectation under a modified density and is defined by
Ex.q [h(X)]] = Ex; (X)((()((
[
"7 )
with tilting function the ratio 0g == A.
PXg Px2
where the normalization is given by Ag = Ex,
PXL Pxt
If =
the tilted expectation simplifies
Bk.g (xxx)) Ex, [M(X:)]
We can show that the over- over-fitting induced at each step is controlled by this tilted expectation as shown in the following theorem.
Theorem 4.1 (Bounded expansion). Let X and X1/1/2 1/2 be the gradient update half-steps in equation 3, then
D, (X4t1/2lX24112) & Dr (XxlX))
Bn + 2
Ex.g (ll Bx) g'(x B()
where the tilted expectation Ex.g is an expectation under a modified density defined in Definition A.I.
Proof. We first apply the data processing inequality to obtain that
Dy (Xx+1/21XX s D2 (Xx+1/22xx))I(C X3)
The q-tilted chain rule for g-Rényi divergences ( (7.59) in (Polyanskiy, 2019)) then gives us
Dy (XX+t) where the tilted expectation is given by
< Dy (XulX() + Ex, Dr (Xet1/2/Xe= = X Xx)
Exg [((2))] Ext (x)(X()
"
where (z(x)
Pxa Px-
Pxg where the normalization constant is given by Ag Ex
PxL Pxt
This tilted
expectation is a little complicated but what inside the expectation is a simple term.
Observe that X/ is a (xx g(x, B&), v 3. We obtained the result by using closed form results for the q-Rényi divergence between Gaussians ((Mironov, 2017) Proposition 7).
The second element is the contraction component. The contraction theorem 4.3 is direct application of the forward step in Theorem of (Chen et al., 2022) with = n/3.
B. Uniform LSI under dissipativity
In this section we prove that the iterates of equation SGLD verify uniform log-Sobolev inequality under assumption 5.3.
B.1. Properties of dissipative functions
We first begin by showing approximative contraction property of dissipative functions.
12

---

Generalization of Noisy SGD in Unbounded Non-convex Settings
Lemma B.1 (Dissipative gradient updates are approximately contractive). Let be an L-smooth, (m, b)-dissipative function, then any S
ym
25
> -V/[[]]]] 2 w||=| (2 21bb)
with w = - (1- and R
b
Proof. Let 1) S
vm
2L x E IR
|x 7/ 7/ (x))] = ||=||2 - 21/ (z. + (z)
$ | - 1 2/|=1 2n/² + 2nj (using Ass. 5.3 and Lemma B.2)
$ (1 mym) | 1| + 2,2 b + 2njb (using that vy s
171
2T,
-||+||² + 27j L22²² + 2mb
with w = (1 - 1pm) and =
A/
Lemma B.2 (Gradients of dissipative and smooth functions). Let be an L-smooth, (m, diddsipaee functioonii,,nn then
[V S L|| L m
Proof. Let x be a stationary point of f. then
|V fx)]l = - v=(x))] s L|| - x*1l S L |x|||
-||>"|
The result follows from Lemma B.3.
Lemma B.3 (Stationary points of dissipative functions). Let f be an (m, b) dissipatiiv function, then for any x E Rd
b
vf(²) =0 = ||
m
Proof. The result follows from the definition of dissipativity in 5.3.
Dissipative functions therefore roughly keep the iterates in bounded region of size for their exponential integrability.
V
m This will have implications
B.2, Exponential integrability
Given that each gradient update is contracting, we can show that the iterates of SGLD are sub-Gaussian. In other words, we can show exponential integrability as given by the following lemma.
Lemma B.4 (Exponential integrability). Let Xo N v 3 and let f be (m, b) didsiipatee with contraction constant
w (1 - -mm) For any p 2 such that pa < <1/8, we have for any 1, the iterate Xs of equation SGLD verifies
1
9 X - -VX(x(()) < 16 1)((R))))
log E p
exp
2p 2m
Proof. We show the result by expressing the norm of the gradient update sum of Gaussian norms. Let 1, we have
that
| VV
z w|| X I" 2nb
27 8
s - V + 2w
| + 2n + 2nb
-
27
212 + 2mb
s <2ww)* +
Σ
B 1
2w
13

---

Generalization of Noisy SGD in Unbounded Non-convex Settings
Since Xn ~ NN(
di I), we have that
* X /V((III 1 (2w) + Σ (2w) N
n)()))) b 21ym
2n
where each N; an independent (0, I) variable. Norms of Gaussians are exponentially integrable. Consequently, for p such that 2p(2w) 1/4, we invoke Lemma B.5 find that
3 2p 2m
(4p(2w)* +4 > (2w) dp + n)( +
log E
exp
X - -V
21m
100
$ 16 (6 d + m3 (L)))) p
where we used the fact that w < 1/4 implies that 2mm- 1 2 1/2.
Lemma B.5 (Square Gaussian moment generating function). Ler Z ~ (0, Ia), we have that, for any X < 1/4.
log
M S
2dA
Proof. The random variable || is sum of d standard Gaussians squared. Using elementary computations we can derive its moment generating function
d/2
E[ 21
2X
We obtain the result using the inequality - In (1 2X) S 4A for X < 1/4.
With the Exponential integrability, we simply exploit the fact that Gaussian convolution upgrades uub-Gaussianity to an LSI to show the following result.
Theorem 5.5 (Uniform LSI). Let Xo ~ NNO,, 3d
D) and let f be (m, b)ddissipattve,
32m
31
<
S
21
m
the iterates of
equation SGLD all verify a Poincare and log- fog-Sobolev inequality with constants Cp S exp (32 (b d n3(L))2)) and CLSI < 6Cp (32 (b ()(())))) where R / bb/m
Proof. Thanks to our Lemma B.4, the proof will follow from the fact that Gaussian convolution upgrades aub-Gaussianity log-Sobolev inequality which was shown in (Chen et al., 2021). For any 1, we have that
X = X - - B&) +
N
Exponentially integral gradient
Independent noise
We cast our result in their notation. We can express the equation above the mixture of Gaussians. Indeed if denotes the distribution of the gradient step and P. is the Gaussian distribution centered at X, then the distribution of X₁ is the mixture y.P := f Padj(()) We can thus apply Theorem (Chen et al., 2021) which bounds the LSI mixtures. Using the exponential integrability bound established in Lemma B.4 and taking p = 2, we have, following their notation, that,
Xr - (VF((x)))))
K Kp (P,p) = Ex>axxx [1+ (Px
< E
exp
4
2n
By combining our bound in Lemma B.4 and Theorem (Chen et al., 2021) yields the result since Kp
B.3. Corollaries under dissipativity
Here we provide proofs for the corollaries derived under dissipativity.
14

---

Generalization of Noisy SGD in Unbounded Non-convex Settings
Corollary B.6 (Bounded KL stability). q 1, under Assumptions 5.6 and 5.7, for any k 2 1 and
< 1) S
n
32m
21
have that the iterates X& and X of SGLD with stay within bounded KI. divergence from each other given by
(Xxx)) & 3y(022 + D2) (1-ght1)
(1-7)
with y
30 Ba+t 2yy." 42
M
2d m3
and with (1 nL) + 3. where CLSI is the uniform LSI given in
Theorem 5.5.
Proof. To establish the corollary, it suffices to control the sensitivity terms S given in equation 4. Thanks to assumption 5.7, we have that
S S 20 É [||* 2D
Since we have chosen q = 1, the tilted expectation is actually an expectation under X according to Definition A.1. Consequently,
2dn B
E [|X|] = E [| S w || [I?] + L2 2nb) +
where the second inequality follows from the approximate contractions of dissipative gradient updates Lemma 5.4 and the last term the expected norm of Gaussian noise Ng. By unrolling the geometric sequence above, we have that
2dn
E
(2n² 2mb) +
1
8
Using the fact that 1 = 1ym, we find that
22
2b
2d
E [1x11
+
mB
Defining M 2ry 2nt n22
yields the result.
m
mB
C. Optimizing constants
With regards to optimizing the constant 31/32, we first observe that for any x E IRd, and >> 0, we have thanks to Lemma B.2,
[|x + L.V
6 I
13 + (2(L
m
1/|0|/ 2(VLL(x = 17²
(1 (1+2)) (1 nn m
where we have used Young's inequality in the last inequality. Now here, notice that we have (1 + t) instead of 2 in the proof
of Lemma 5,4. So we can choose 7 < (1+4)EZ to have that
m
(1 2 b
V
m
By having a larger constant term, we can allow ourselves larger choice of 1). can combine this result with dissipativity to obtain the following gradient contraction
b +nb
Jar [V (1 m/)] 2, 7 m
which tightened version of Lemma 5.4.
15

---

Generalization of Noisy SGD in Unbounded Non-convex Settings
D. Approximate contraction proofs
In this section, we prove the approximate contraction along heat flow theorem established in section.
Theorem 6.3 (Approximate Contraction). Let π ~ e e-BFF be a distribution verifying the LSI with constant c 2 1, whose potential F, I-smooth and lower bounded by F*. For any distribution n' and 0g = ag * *N(0, by * *N(0, 1) with Vlog bo = I, we have that
DEL (o,1bb) 4/4r, DEL lbo)
erg(an (a, Dys x²) ProbConst
where the ergodicity ervor term gathers quantities related to convergence of o,,, by towards n' and ProbConst gathers problem-dependent constants (explicitly given in equation 8 and equation 9).
Proof. From Lemma F.2, we know that
- - [|V ao V Vlogbe(A:)11 DxL (acl)))
dt
Expanding the square, we find that
- DKL (,, S BBB. [|V log [e3] E [ log (A.)]]] + Eu, I( log ae V log bt)
d
d
Now making the same observation as (Futami Fujisawa, 2024) that ||u w112 S 1111 + ||0|12 have that
d DKL (A,1B.) S
1 Eu, [|[ log o Ba,
4 Fa,
log log |
+B, (VVlgg at, Vlogb.))
dt
Invoking the I.SI for æ,, we write
DKL (A,l <
Es,
log ae
+
1 t2
[ log π |
2 Bo. [] V loggbll2 boll + Ea, ((V log az, V log by)]
dt
4c
Introducing b, back into the first term, find that
d
1 dc
Qt b.
DKL (A,li)) <
Eor
log
+ Err(TT + Err(b)
(6)
di
where we define
1 +
Err(T) =
Eu, [log
Bus | 1|
4cr
2
and
1
Err(b)
E., |- log b,]
Bo, ||| log bell 1| Ea, KV log a,, V logbr)]
4cz
We will establish time-independen upper bounds for both these error terms. Using Grónwall's lemma, can then deduce from equation 6, by integrating from O to
/ / that
DKL (ag (igbbg) S n/48cn DEL (bo) + (Err(T)) + Err(b)
We control each term individually. First, observe that Er((T) is sum of a negative Shannon entropy and a log oog-gradient norm measured through distribution a, instead of æ. We bound each summand Lemmas D.4 and D.5 respectively to obtain that
3L 2Tr
Err(m) < -2FF log(
1,2
(az.T) 1,2 Ld
The other error term where the regularizing properties of Gaussian convolution are fully exploited and it is here that we differ most sharply with the analysis of (Futami & Fujisawa, 2024). The first term in Err()) is an expectation of log by
16

---

Generalization of Noisy SGD in Unbounded Non-convex Settings
and We have established that thanks to Gaussian convolution, the log-Hessian of log by is lower bounded. This induced smoothness allows perform change of measure in Lemma D.2 control the first two terms of Err(b). The last term is again controlled using the properties of Gaussian convolution and simple integration by parts in Lemma D.I. We obtain that
Err(b) S max Bs, [- log by] + K + 2
(w2
ag. by 8 2d -
Kd
Using the density bound in equation D.3, we can control the Shannon entropy, which gives for any x²,
43 Brr(b) 5 - W3 (bg, x +
43 E [1|1]]]
K
W3 (az.by) + 8 8) kd
2d
Putting everything together in equation 7, with K B 9
find that
DKL. (aylby)
S e n/47 DRL. (oollba) + erg(ay, by. ,²,²) ProbConst
where the ergodicity error term gathers quantities related to the convergence of the processes
erg(ag. by by. म. x²) = 1 (az. T) (1 + 23"
W (g + 4M3 (by,
(8)
and the problem constants intervene in ProbConst with
ProbConst Exr [||]]]]] 2F
1ld
log(
3L
d
log(2 17 3 + +d dd1111 Ld Ld a d +
2x 2
Lemma D.1 (Inner product bound). Let ag be in Theorem 6.3 with log bu K,
En, [VVog 01, V log ba)] R.g, A log bx] < Kd
Proof. The result follows from integration by parts (Lemma F:3) which gives
E.g. (VV log ae: V Voo by) = E,, [A log by]
Since Gaussian convolution only improves log- nes-HHssian lower bounds, we find that
Ea, log by] s Kd
Lemma D.2 (Change of measure). Let ae by as in Theorem 6.3, for 2 1
Em, |- log by]
1 E.. [|/V log bell < Eg, |- log by] +
K + 2
(w3 (Ag. + 8833
+87
4cx
2
Proof. Since
2 log by J K, we can apply the change of measure Lemma 6.2 to the function
logg by to find that for
Cr 2 1, we have
1 Eo, |- log be]
1 Bo, [[[V log bill Es, |- log b.]
K + E [I]A 1.
4ca
The crucial feature of the change of measure lemma is that we can choose the coupling between (A,, B,) freely. Let ((Ap, N), ((Bo. N')) be coupled such that
W Ao + #++V27
IN Bo
7 (N) = [11A0 + VTN - (Bo VT
17

---

Generalization of Noisy SGD in Unbounded Non-convex Settings
With this coupling in hand, we define A, Ao VIZ and B, By + VIZ' with Z, Z' independent (O,, 7) variables. We then compute
+ 4ld 4 " 3 11 N - -Bo /
E [IIA, Bell < 2E
A
V3"
B
W2 Ag. By
+ 1(t + ?
B yd
Lemma D.3 (Density bound), Let t < S 1, let B be random variable with density b. Let define the half step density? as b1/2- = (b x n/)). Let b. b1/2 (0, LT) be the result of Gaussian convolution applied to the half step b1/2-
then for any w', we have that
43 W (g. + Ea, lolog by] -
48 E [|x]]3]] + d log(2x ") 2d 2
"
Proof. By definition of Gaussian convolution, the following equalities hold
(x()) EE [1//2 VEN)] and b1/2(x) EB Wo B,nl))
repeated application of Jensen's inequality yields
log (x) - EN
1ogb1/2(00 -VVin
- EN Fbb
B
||0- - ViN B112]]
d
log 2n 7
2n
2
3 3)
< EN
3
||00 ViN B1(3]
d
log 2m "
2m
2
Now taking expectation with respect to by, we find that
Es, |- log by (B.))
<
E [B. VIN- - B1|] + 2 log (2 " 21
3
(10)
We then add some noise terms to look forward in the heat flow. Let N', N" ~ ~O, 1) be independent Gaussians, then
E B VEN BB1
S
( +
tN') - -B 2n 113
+ *13 7
+)d td 2nd
V
< 2E
| 2
2E
[IB + 11 +3
Recall that both By and +
/2 N" have the same law. Indeed B3 has distribution by b1/2 * *N(O, # I) (i.e b
with f = }) which adds variance gaussian noise to the half step which already adds variance 3 gaussian noise to B, consequently it corresponds to adding 2 variance gaussian noise to B. By plugging the above into 10 that,
233 [ [1] Es, log by (B:) <
log(2r 2n " + 2"
+ 2
B
17
From this we deduce that,
Es, [- log be (B:) < 17
4,3 W (bg x¹)
4,3
Ex
[|
d
Log(2n "
" + 2d.
17
Piie akin to density X441/2)
18

---

Generalization of Noisy SGD in Unbounded Non-convex Settings
Lemma D.4 (Entropy bound lower bound). Let & e with F L-smooth, lower bounded function such that F(x) F for some real value F* E [R, then for any
3L 2m
Ev [log π| _ -2 + log(
Proof. We denote by the normalization constant of π defined as
= /
c-FF(w)
Rd
Observe that
log -3F log(A) S 3F logg(A)
We therefore need only to lower bound log( which, as performed in (Raginsky et al., 2017) Propostion 3.4, can be achieved using a Laplace integral approximation to yield
2m
log A 2 3F
+ log(
2
3L
As consequence, we obtain that
d
BL
Ba, [log T| S -23F
+
log(
2
2m
Lemma D.5 (log-Gradient bound). Lef π x BB with F an I-smooth potential, then for / S B.
E... 2
[ log || < 1. (az.T) + 2.312nd Ld
Proof. Recall from (Vempala & Wihisono, 2019) Lemma 11 that
Ex [|| < dL.
To control the gradients under different measure, suffices to do simple change of measure as is done in Lemma 12 of (Vempala & Wibisono, 2019). Since gradients F are L-Lipsethiz, we have that for any Rd and independent
N' (0,
Ea, V 12| < 3,, [FF(A) - V
2
< L
[||Ar
y/1 + [[F(
$ 1,2 I.2Ba,
|| + V tN y1²
+ 2.3 T,2
< 232 L2W3 (An
T) + 2 + Ld,
where the last inequality is obtained by having y with optimal coupling.
D.1. Proof of the Corollary
Here we show how to use our approximate contraction result to obtain bound on the generalization of SGLD.
8 Corollary D.6 (KL stability under isoperimetry). Under assumption 6.4, 6.5, and assuming Cx 1. We have for T. the iterates of equation SGLD X and X ran on datasets D and D' satisfy
poly (g. L, d, o, dinst, d'nit)
DeL (XxIX))= <
1-7
CF + Scaas
1 1-7
where Scibbs Ex (X), VF(X))])) Cp E, [|||||] 2F*, dinit DeL (X6l)), d'uit
Duu (X/lT').
and 7 = e -1/BBe,
19

---

Generalization of Noisy SGD in Unbounded Non-convex Settings
Proof. Our goal is apply Theorem 6.3 the iterates X5 and X Let us first look at the additive error term erg 8. The additive error term erg(ag g, by, m, x²) is of Wassertein distances between ag and and by and n², Indeed, we have that
bg. = L
(1+ !
W2 (ag. b2)
4W2 (bg,
23
x 2n 1, 1.2 (az. x) + 2(1 + W3 (ag.
23
+ 4(1 + " W (T, x) 8(1
" W by.
2
23
where we use the triangle inequality for Wassertein distances to obtain the above. We thus have the following three Wassertein distances we need to control: W2 T), (2 x') and W²(T, m').
When applied the iterates of SGLD, the Wassertein distances of interest become W3 (X*+1, x) and W ++1, x²) and W2 (IT, x²). To bound these terms, we therefore need to show that the iterates of SGLD converge in Wassertein distance to their respective target measures and IT.. This was shown in (Kinoshita & Suzuki, 2022) and we restate their result in Lemma D.7. The distances (2(X*+1)) (X++1, x) and (X (X,, X') are thus given by Lemma D.7. Now we also know from the log-Sobolev inequality that
Wi(T,, x') S 2c, DKL (Λ| S &CE - (X)
The first inequality follows from Talagrand's inequality which is implied by the LSI (see 2.2.1 in (Vempala & Wibisono, 2019). The second incquality is the LSI. We define the stability quantity denoted SGibbs == E (VF() (X)) to control the right hand side.
Combining the upper bounds given in equation 11 for X and X with the above find that
erg(ag, g. by. n, m') S poly (2 L, d, DKL (Xol=). DeL (X6llz)) + c Scitbs
Adding in the second constant ProbConst and un-rolling the geometric recursion for the iterates X X in Theorem 6.3 yields the result.
Lemma D.7 (W2 convergence of SGLD (Vempala & Wibisono, 2019; Kinoshita & Suzuki, 2022)). Under ussumptions 6.4 and for 17 6. the iterates of Xş of SGLD satisfy
W2( S
KL(X,, & + " (8d2= 202)
(11)
Proof. The analysis of (Vempala & Wibisono, 2019) is sufficient to show this result. As shown in Lemma 3 of (Vempala Wibisono, 2019), convergence is established by comparing a single step to the continuous Langevin diffusion with the discrete iterates. Here, our case, in addition words, the gap between the drift of the continuous time Langevin diffusion and the discretized SGLD iterates compounds two emrors: one for discretization, one for stochasticity. For continuous Langevin diffusion (X); with drift V F, started Xo. the expected gap between the continuous Langevin drift and the gradient step of SGLD is given by
discretization error, we further have stochastic gradient error. In other
(XI))),((X)) (X,, B) < 2E FA (X,) V (x) 2E(II 9 (Xo, B)
2E (X. VF, (X 202
Consequently, the same analysis as (Vempala & Wibisono, 2019) holds, with an additional 20 term appearing in addition the discretization error. According equation 13 in (Vempala & Wibisono, 2019) it follows that
KL(Xx, x) < KL T) (/ddL + 20
Sc₂
20

---

Generalization of Noisy SGD in Unbounded Non-convex Settings
Since verifies the LSI, and the LSI implies Talagrand's T2 inequality (Gozlan, 2009) the inequality above also gives
(2,,,, S &c,KL(Xo, τ) + [8dL2 20
E. Properties of Gaussian convolution
In this section, prove the two fundamental properties of Gaussian convolution which enable our analysis. We first provide expressions of the og-Hessian, from which both properties of interest follow.
Lemma E.1 (Lemma E.3 (Chen et al., 2022)). Let Pn = p (0, n/), we have that
1. 2 log Var poly (x)
la
2. 2 log (x) Epota
2 log [(Y) + Var pa: (V log p(Y)
Both the following lemmas follow immediately from the characterization given above. Indeed since Variance terms are p.s.d, we deduce both the lemmas below. The next Lemma follows from point 1. in E.1.
Lemma F.2 (log-Hessian lower bound). Let be distribution that results from Gaussian convolution, ie, v= ix*((0, for some distribution D, then
1
2 Pog -aa- 7)
The next lemma follows from point 2. E.1. Lemma E.3 (Only upwards). For any distribution be distribution, it holds that
2 log * NO m/)) = V² log
direct application of the lemmas allows also establish that Lemma E.4 (Bounded Laplacian). Let be distribution such that 2 log 2 K, with K 2 0, ler by = bb b(,tt)
Es, [ log bell] --E,, (tr ( log b,)] S Kd
Finally the change of measure lemma is simple consequence of analysis.
Lemma E,5 (Change of measure). Let Rd - be a twice-differemtiable function such that V2g ł IK some K R. Then, for any random variables X, over Rdd, we have TE[ [V[) [R[ o( X)] [IV((
+ K+1 E - Y|
2
Proof. From classic results in analysis, we know that
K
( 2 g(x) + (Vg(z). 2)
y/1
2
We apply Young's inequality and integrate to obtain the result.
F. Technical Lemmas
In this section, we include the small technical lemmas that can be found in the literature.
We first show the link between our Lemma 2.2 and the result of (Xu & Raginsky, 2017). We first recall their result. Lemma F1 (Expected generalization of subgaussian losses, Thm (Xu & Raginsky, 2017)). Let fww Z) be a loss function that verifies assumption 2. Then, for any k 2 1,
2cI(Xx;; D)
gen (x.
n
where T denotes the mutual information.
21

---

Generalization of Noisy SGD in Unbounded Non-convex Settings
Let X5 be the output of SGLD ran dataset D with distribution P2,,/D- Recall that the mutual information is given by
[ x, [D: D) DxL ((X,, DI((,,
where X2 is an independent output of SGLD ran on an independent dataset D'. Conditioning on the second coordinate we have that
(Ppx/:: D)
ED [KKI. (FxxeIPx;)
since Px.= f [ invoke Jensen and convexity of the KL divergence to find that
T(PxIDD: & FD,DD [DKL. (Px.io|Px,pr))
Which leads to the KL stability characterization of generalization.
Lemma F.2 (DeBruijn's s Identity (Zozor & Brossier, 2015)). Lel A, B be two random variables over TRd, for 1 > O, let A = + VIN and B B + VtN. Denoting by at and by the densities of A and B, respectively, we have that
d DEL (b) = E [[Vllg
V log b1l
dt
Lemma F.3 (Integration by parts). For any two functions h, g: Rd + R
(Vh(z), Vg(z)) de =- .f (gr))g
Lemma F.4 (DeBruijn's Identity (Zozor & Brossier, 2015)). Let A, B be two random variables over Ted, for 0, let A, A VNN and B B VtN. Denoting by at and by the densities of A and B, respectively, we have that
d Dxy. (a. (b) < 2
1 log V log by ||
di
Proof. Since ae, b, are undergoing simultaneous heat flow we know that
Da: Dat
bb.
Ab.
Ot
Ōt
follows from straightforward computations that
0DR.. (o.lb.).
/
da:
(x(x)) (x(
ab.
(x(x)
Jaa
(x)
log
(x)
Ot
Ōt bx(x))
Ea,
||| log
V log bell
2
22


Reviews:
[{"review_id": "o71pvF4V3C", "reviewer": "Reviewer_kUSb", "summary": "This paper studies noisy SGD, or Stochastic Gradient Langevin Dynamics (SGLD), in the setting when they are run for many iterations with non-vanishing step sizes, to understand the generalization bounds. They study this by comparing the weights when run on two different, independently-sampled datasets. They show that by assuming dissipative loss functions, uniform-in-time bounds can be established for the generalization and differential privacy of noisy SGD. This is done by resolving an open question on the isoperimetric properties of the biased limit of discrete Langevin iterates.", "questions": "", "limitations": "", "rating": 3, "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": "We thank you for your time and review. We would like to address some of your concerns.\n\nWe have provided a clear application of our bound in our response to mwzT. Our goal is to have theory catch up to practice where it is already common to train on non-convex losses for several thousand iterations.\n\nMoreover, the form of our result closely matches the one obtained in strongly convex settings. In other words, there are no unecessary terms in our results unlike prior work. However, since there are almost no lower bounds in non-convex settings for sampling algorithms (or noisy iterative schemes), it is difficult to prove optimality of our upper-bound.\n\nWe remain at your disposal for further discussion.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "No.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "This paper extends prior results to the non-convex, unbounded setting.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "Strengths:\n- This work extends prior results for strongly convex settings to the non-convex setting.\n\nWeaknesses:\n- The results are purely theoretical and lack concrete connections to applications.\n- It would be good to discuss how optimal the results are.", "other_comments_or_suggestions": "None.", "questions_for_authors": "- Could you discuss more about whether the assumptions used in this work hold in practical settings, and describe more concrete applications of this work?\n- How tight are the bounds derived in this work?", "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": "", "extra_scores": {}}, {"review_id": "Ef06STa9Od", "reviewer": "Reviewer_mwzT", "summary": "This paper investigates the stability and generalization properties of noisy stochastic gradient descent (SGD) in unbounded non-convex settings, extending prior analyses that primarily focused on convex or bounded loss functions. The authors establish stability-based generalization bounds that remain non-vacuous even as the number of SGD iterations increases.\n\nThe key contributions of the paper are as follows.\n- KL and Rényi divergence stability analysis for noisy SGD. The paper derives uniform stability guarantees using isoperimetric inequalities, which provide a framework for analyzing the long-term stability of noisy SGD.\n- Generalization bounds under non-asymptotic and convergent settings. The authors extend classical stability-based generalization results to unbounded, non-convex loss landscapes, leveraging log-Sobolev inequalities.\n- Implications for differential privacy (DP). The stability analysis is connected to DP guarantees, showing that the derived bounds naturally extend to Rényi DP in certain conditions.\n- Relaxation of traditional strong convexity assumptions. The paper shows that dissipative and smooth losses satisfy the required isoperimetric properties, significantly broadening the applicability of the results beyond strongly convex settings.\n\n## update after rebuttal\n\nThe authors have provided a detailed and thoughtful response. They clarified the connection to gradient variance and indicated that they plan to incorporate an upper bound on the generalization error based on a surrogate loss derived from Futami & Fujisawa (2024). This addition is expected to significantly enhance the contribution of the paper. Furthermore, the authors’ explanations regarding concrete cases in which the assumptions hold, as well as the interpretability of the proposed bounds, were convincing and informative.\n\nAssuming these points are appropriately reflected in the revised manuscript, I believe the paper will offer a comprehensive and rigorous discussion of the topic. Accordingly, I have decided to raise my score by one point.", "questions": "", "limitations": "", "rating": 4, "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": "We are sincerely grateful for your thorough review and detailed feedback. We would like to address some of the areas of improvement that have been identified.\n\n**Extension of the bound**:     \n\nYou correctly observe that some generalization bounds only hold for an evaluation loss (like the 0-1 loss for example) but the algorithm is run on a different differentiable surrogate. Our work applies to a differentiable surrogate. Often since surrogates are chosen to be upper bounds of the evaluation loss, our result still has implications on the evaluation loss in the following way\n```\nloss(test) < surrogate(test) = surrogate(train) + [surrogate(test) - surrogate(train)]\n```\nwhere the final term is the generalization gap we control.\nJust like Futami and Fujisawa's, our result allows us to control the gap in cases where the surrogate loss and the evaluation are exactly the same.  Technically our result bounds the mutual information( denoted $I(W_T, S)$ in Futami and Fujisawa) so we can directly use Theorem 7 from Futami and Fujisawa (also in [B]) and our improved bound will still hold in that setting. We had chosen to omit this component for simplicity but we will add this result as it relaxes the requirement on the surrogate loss: we can include sub-exponential losses and not just sub-gaussian ones. \n        \n**Connections to gradient variance**:\n\nTo establish this connection, notice that our stability term is the norm of a difference of gradients and this difference can be expanded into the sum of gradient norms since $\\|a - b\\|_2^2 \\leq 2\\|a\\|_2^2 + 2\\|b\\|_2^2$. With this relaxation, our bound can be expressed as a function the gradient norms encountered on the trajectory. We will add a discussion of on using sensitivity term $S_k$ versus gradient norms along the trajectory. The work of Jiang et al shows the difficulty of aligning theoretical generalization bounds with practice and it is important to mention. \n\n**Example of loss verifying our assumptions**:\n\nWe agree that to we should showcase the relaxed requirements by giving a concrete example. We will add the following. Consider a two-layer network with weights $x = [x_2, X_1]$ defined as $NN(x, z) = x_2^\\top \\sigma(X_1z)$ for a data point $z \\in \\mathcal{Z}$ and the differentiable logistic sigmoid function $\\sigma$. We assume the datapoints are bounded (for example pixels in $[0,1]$ for images). We define a learning task through a Lipschitz loss over the outputs $o = NN(x, z)$ of the network: \n$$\nLipschitz(NN(x, z))\n$$\nWith weight decay (i.e $\\ell_2$ regularization), this non-convex loss is dissipative (see section 4 of [C]). It satisfies assumption 5.7 because, for any two $z_1, z_2$,\n$$\n\\nabla F(x, z_1) - \\nabla F(x, z_2) = Lipschitz'(o_1) \\nabla_x NN(x, z_1) - Lipschitz'(o_2) \\nabla_x NN(x, z_2) \n$$\n\nThe gradient difference of the neural network is given by the vector\n$$\n\\begin{bmatrix} \\sigma(X_1z_1) -  \\sigma(X_1z_2),  \\\\\n (x_2\\odot \\sigma'(X_1z_1))z_1^\\top - (x_2\\odot \\sigma'(X_1z_1))z_2^\\top) \\end{bmatrix}\n$$\n\nBy virtue of the sigmoid being lispchitz and our bounded data assumption on $z_1, z_1$, this gradient difference can be bounded by the norm $\\theta\\|x\\|_2$ + constants where $\\|x\\| = \\sqrt{\\|x_1\\|_2^2 +\\|X_1\\|_2^2}$. We will add this example in the appendix, along with [A]'s result capturing sub-exponential losses like the example above. The Assumption 5.7 is stating that if only the data points differ, then the gradient difference only grows at most linearly with respect to the parameter. \n\n\n**Interpretability of Bounds**:\n\nWe see our work as an attempt at amending a theoretical gap so it can capture the practically relevant setting of very long training runs on non-convex losses. In essence we are trying to make theory catch up to practice. Our result shows that the presence of noise can compensate for a high iteration count. Concretely, for a fixed choice of $\\eta$, we can see that choosing a low $\\beta$ (i.e adding more noise) is advantageous for generalization, the trade-off however is that a lower $\\beta$ can harm convergence of the training loss. We also see that  will add a discussion on the trade-offs between generalization and utility.\n\nWe are again grateful for your time and we remain at your disposal to discuss these points further.\n\n---\n\n[A] Futami, Futoshi, and Masahiro Fujisawa. \"Time-independent information-theoretic generalization bounds for SGLD.\" Advances in Neural Information Processing Systems 36 (2023): 8173-8185.\n\n[B] Bu, S. Zou, and V. V. Veeravalli. Tightening mutual information-based bounds on general-\nization error. IEEE Journal on Selected Areas in Information Theory, 1(1):121–130, 2020\n\n[C] Raginsky, Maxim, Alexander Rakhlin, and Matus Telgarsky. \"Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis.\" Conference on Learning Theory. PMLR, 2017.", "claims_and_evidence": "The claims in this paper is well-supported.\nBy leveraging log-Sobolev inequalities and isoperimetric properties, the paper provides a unified theoretical framework for studying stability. To the best of my knowledge, this proof approach is a novel contribution.\nThis result extends previous stability-based generalization analyses and provides meaningful bounds that do not become vacuous over long training horizons.\n\n### Potential Areas for Clarification or Improvement:\n- Interpretability of Bounds:\n    - The derived bounds are rigorous, but it would be better to further discuss their practical implications.\n    - For example, can the results provide insights into hyperparameter selection for SGLD, such as noise control and learning rate tuning in terms of generalization?\n\n- Applicability of Assumptions:\n    - While the theoretical assumptions are mild, it would be useful to provide explicit examples of loss functions and models that satisfy these conditions in an Appendix.\n        - Especially, I have some concerns about Assumption 5.7. Is that satisfied for broader models or can we make it to be satisfied by using some reasonable techniques?\n\n- Extension of the Bounds:\n    - In practice, SGLD and similar stochastic gradient methods often deal with non-differentiable loss functions, using differentiable surrogate losses instead. Are the generalization bounds derived in this paper based on the generalization error with surrogate losses or that with the original non-differentiable losses?\n    - If only one case is covered, could the bounds be extended to handle both scenarios, similar to [Futami & Fujisawa, NeurIPS 2023](https://proceedings.neurips.cc/paper_files/paper/2023/hash/19dbb86f771ddbf9986cf0c9b1c61c17-Abstract-Conference.html)?\n    - If such an extension is possible, can the improved generalization bounds derived in this paper also be maintained in both cases?", "methods_and_evaluation_criteria": "The proposed theoretical approach is practically reasonable, as it does not introduce additional restrictive assumptions but rather removes certain limiting conditions from prior work. \nThe metric analyzed in this paper is generalization error, which is well-aligned with the study’s objectives. However, as mentioned in the Claims And Evidence section, I have some concerns regarding the clarity and applicability of the theoretical assumptions:\n- Explicit examples of models and loss functions satisfying the assumptions would enhance clarity and help practitioners better understand the scope of the results. Including such details in some part such as an appendix would be valuable.\n- Does the generalization bound measure the error with respect to the original loss function, or does it analyze generalization with respect to the surrogate loss function used in practical optimization? If only one case is analyzed, can this framework be extended to derive generalization bounds for both settings?", "theoretical_claims": "I have reviewed the proofs, including those in the appendix, at a broad level.\n\nGiven the assumptions made—particularly Assumption 5.7, which allows for the control of $S_{k}$—I found no issues in the proof techniques, their logical progression, or the claims derived from them. The mathematical framework appears sound under these assumptions.", "experimental_designs_or_analyses": "As discussed in the \"Methods And Evaluation Criteria\" section, the theoretical analysis focuses on generalization error, which is well-aligned with the objectives of this study. \nThe choice of this metric is appropriate given the problem setting and theoretical framework.\n\nOne potential concern is the definition of the generalization error being analyzed. \nThat is: Is the generalization error evaluated based on the surrogate loss function used in optimization, or is it defined with respect to the original, potentially non-differentiable loss function?", "relation_to_broader_scientific_literature": "This work is closely related to several lines of research, including (i) stability-based generalization analysis and (ii) analysis of SGLD performance.\n\n- Stability-based generalization analysis has been a fundamental tool for understanding learning algorithms, originating from the work of [Bousquet & Elisseeff (2002)](https://www.jmlr.org/papers/volume2/bousquet02a/bousquet02a.pdf) and later extended by [Hardt et al. (2016)](https://arxiv.org/pdf/1509.01240) for SGD. While these studies focus on convex or bounded settings, this paper extends stability-based generalization bounds to unbounded non-convex settings.\n- SGLD and noisy SGD have been extensively studied in terms of convergence and generalization, with prior works by Raginsky et al. (2017), Mou et al. (2018), and Pensia et al. (2018) analyzing the stability and learning dynamics under specific regularity conditions. (I omit the paper link because these papers have already been cited in this paper.) This paper removes the strong convexity assumption, making the more realistic results in terms of the modern machine learning context.", "essential_references_not_discussed": "I find that the paper appropriately cites and discusses the most relevant prior work. \nI do not see any critical missing references that would significantly impact the understanding or positioning of this work.", "other_strengths_and_weaknesses": "### Additional Strength\nThe paper is well-written and structured. The presentation is carefully designed to guide the reader through the background, assumptions, and supporting theorems in a clear and logical manner, making the technical content easier to follow.\n\n### Additional Concerns\nOne additional concern is that while the derived bounds improve upon existing results, it remains unclear whether they offer new practical insights into generalization performance.\nSpecifically:\n\n- It seems that the bounds do not explicitly provide a discussion on what conditions lead to improved generalization performance. It would be useful to explore whether the new bound provides insights into what factors influence generalization in practice.\n\n- While stability is undoubtedly an important quantity in generalization analysis, it remains unclear how the derived upper bound connects to other empirically well-correlated generalization metrics, such as gradient variance as studied in [Jiang et al., (2019)](https://arxiv.org/pdf/1912.02178).\n\nIn contrast, alternative approaches such as information-theoretic analyses of SGLD generalization often produce bounds that are expressed in terms of gradient norms (Pensia et al., 2018) or the sum of gradient variances ([Negrea et al., 2019](https://arxiv.org/abs/1911.02151)), which are known to correlate well with empirical generalization. \nIt is unclear whether the improved stability-based bounds in this paper provide similarly strong connections to empirical generalization behavior.\n\nClarifying how the proposed bounds relate to these widely used empirical generalization indicators would strengthen the impact of this work.", "other_comments_or_suggestions": "I do not have additional comments. Please refer to the Questions for Authors section. \nI will consider further raising my overall score if these concerns are adequately addressed.", "questions_for_authors": "- Interpretability of Generalization Bounds:\n    - The paper improves existing generalization bounds, but what new practical insights do these bounds provide regarding what conditions lead to improved generalization performance?\n    - Can the authors discuss how the new bounds relate to hyperparameter settings, such as noise level and learning rate tuning in practice?\n\n- Connection to Empirical Generalization Metrics:\n\n    - Stability is a well-established quantity for analyzing generalization, but can the authors clarify how their derived upper bound connects to empirical generalization metrics, such as gradient variance (as in [Jiang et al., (2019)](https://arxiv.org/pdf/1912.02178))?\n\n- Definition of Generalization Error:\n\n    - Does the analysis in this paper consider generalization error with respect to the original non-differentiable loss function, or is it defined based on the surrogate loss function used in practical optimization? If only one case is covered, could the framework be extended to analyze both settings?\n\n- Applicability of Assumptions\n\n    - The theoretical assumptions seem relatively mild, but could the authors provide explicit examples of loss functions and models that satisfy them? Would adding such examples in the appendix help make the results more accessible to practitioners?\n    - In particular, could the authors provide the discussion for the reason why Assumption 5.7, which allows for controlled $S_{k}$, is realistic? For instance, are there standard techniques in model training that naturally satisfy this assumption? Providing concrete practical examples would strengthen the justification of this assumption.", "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": "", "extra_scores": {}}, {"review_id": "ZC0KC3yLLB", "reviewer": "Reviewer_TC71", "summary": "The authors introduce novel generalization guarantees for Noisy SGD that extend to non-convex settings, possessing desirable properties such as an $O(1/\\sqrt{n})$ dependence on dataset size and an $O(1)$ dependence on the number of iterations. The first major contribution of this paper demonstrates that assuming the loss function satisfies dissipativity—a condition relaxing strong convexity by allowing non-convexity within a confined region around 0—is sufficient to ensure that Noisy SGD iterates remain distributionally similar across different datasets regardless of the iteration count. Remarkably, this guarantee holds even under strong divergence measures like KL and Rényi divergences. Previously, such properties were only known to hold under strong convexity assumptions within the coupled diffusion analysis framework. This guarantee translates into $O(1/\\sqrt{n})$ generalization bound, using the information-theoretic generalization arguments of (Xu and Raginsky, 2017).  However, their resulting bound initially reveals an undesirable $O(e^d)$ dependence on the model dimension $d$. To address this limitation, the authors present their second key contribution. By employing an ergodicity-based analysis framework, they establish another KL divergence bound that avoids this exponential dependence. Specifically, they show that under a condition even weaker than dissipativity—characterized as a Log-Sobolev-type isoperimetric assumption on the Gibbs distribution induced by the loss function—the generalization bound exhibits only a $O(poly(d))$ dependence on the model dimension $d$.", "questions": "", "limitations": "", "rating": 4, "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": "We sincerely thank you for your time and thorough review of our work. We would like to address some of the points you have raised.\n\n*Sampling directly from the Gibbs distribution*: You are correct in stating that an exact sample from the Gibbs distribution would attain the fast rate. However, there is no exact sampling algorithm available for non-convex unbounded losses. Approximate samplers either need a vanishing step size or need to have an additive step size dependent term in the generalization bound. This is precisely the technical hurdle we try to overcome, we want a bound that decays to zero when $n$ goes to infinity without needing to set the stepsize as $1/n$. We will add this discussion along with the relevant reference. Removing conditioning would be very interesting and will likely lead to better bounds but we believe it will add complexity in tracking the LSI constant.\n\n\n*reasonable parameter regimes*: There is indeed a possible trade-off between composition bounds and our bound in section 5 if the dimension is very large and the iteration count is low in comparison. The dimension dependence in section 5 comes from the fact that we only use dissipativity to establish a worst case LSI constant (which introduces the unfavorable dimension dependence). In section 6 we show that *if* the LSI is known to not have a good dimension dependence (for example if the mimima are connected), then the exponential dependence can be avoided to yield the polynomial bound in section 6. \n\n*Initialization in Corollary 6.6* You are correct that the initial points cannot be diracs in Corollary 6.6. We can warm start the algorithms and initialize them as Gaussians at stationary points of the losses, just like in the sampling literature, to ensure a finite $O(d)$ initial KL divergence.\n\nWe are grateful for your time and remain available for any further discussion.", "claims_and_evidence": "The claims appear to be correct.", "methods_and_evaluation_criteria": "The paper is theoretical. The theoretical framework is sound.", "theoretical_claims": "I did not verify the correctness of all the results, but they look okay from the quality of writing and the proof descriptions.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The contributions of the paper extends prior works. The authors establish two generalization guarantees that do not become vacuous with the number of iterations even under non-convexity and have a standard $O(1/\\sqrt{n})) dependence on dataset size.", "essential_references_not_discussed": "The essential related works are all mentioned.", "other_strengths_and_weaknesses": "**Strengths**\n- Paper is very well written with the core ideas being well explained. \n- Breaking down information-theoretic generalization guarantees into modular blocks of results that combine well together is great for understanding the bottlenecks and areas of improvements.\n\n**Weakness**\n- Sampling directly from the Gibbs distribution $e^{-\\beta F_n}$ where $F_n$ is the average loss on dataset has an $O(1/n)$ generalization guarantee (cf. Theorem 2 from (Aminian et al., 2021)). This generalization guarantee holds without making any assumptions on the loss function (besides the subgaussian tail assumption on loss, which is the same as that needed for (Xu and Raginsky, 2017)’s information-theoretic generalization bound used by the authors). So I believe it is reasonable to expect that if Noisy SGD reasonably approximates Gibbs distribution, it generalizes with $O(1/n)$ guarantee as well. More precisely, I expect the $I(A(D); D)$ to be $O(1/\\sqrt{n}))$. But, the authors apply conditioning to upper bound $I(A(D); D)$ with $E_{D,D’}[KL(A(D)||A(D’))]$ and focus only on bounding the $KL(A(D)||A(D’))$ for worst-case $D, D’$ that has no hope of yielding a bound better than $O(1)$. \n- Although the bounds in section 5 have really $O(1)$ dependencies on number of iterations, they only seem useful when model size $d$ is extremely small. That’s because $\\gamma$ very quickly tends to 1 as LSI constant $\\alpha$ grows $O(\\exp(d))$ in model size $d$. This results in the factor $(1-\\gamma^k)/ (1- \\gamma) \\approx k$ up to $k < c \\exp(d)$ for some constant $c$. In other words, in the reasonable parameter regimes of model size $d$ and number of iterations $k$, the generalization guarantee in Corollary 5.8 and Renyi DP guarantee in Corollary 5.9 grows linearly in number of iterations $k$. Effectively, applying Rényi composition might result in a better guarantee in this regime.\n- In Corollary 6.6, the initial divergence $D(X_0||\\pi)$ and $D(X_0'||\\pi')$ can be infinite if the weights are initialized to a fixed point rather than sampled from a distribution. The authors don’t talk about how the weights can be initialized so that $D(X_0||\\pi)$ and $D(X_0'||\\pi')$ are finite.\n\nRef:  \n[1] Aminian, Gholamali, et al. \"Characterizing the generalization error of Gibbs algorithm with symmetrized KL information.\" arXiv preprint arXiv:2107.13656 (2021).", "other_comments_or_suggestions": "Overall, this paper makes good contributions towards non-vacuous generalization guarantees for Noisy-SGD under practical settings. Although we aren’t totally there yet, the ideas in the paper could prove useful towards this goal.", "questions_for_authors": "Could the authors address my comments in the weaknesses?", "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": "", "extra_scores": {}}, {"review_id": "JgeWaHKNqv", "reviewer": "Reviewer_PcWQ", "summary": "This paper provides generalization error and differential privacy guarantees for the stochastic gradient Langevin dynamics algorithm (SGLD). This is done by proving bounds on either a KL divergence (generalization error) or a Renyi divergence differential privacy(). In accordance with several prior works, the main technical elements are a stability argument combined with a bound on the KL divergence featuring a decay term, ie, a bound of the form $KL(k+1) \\leq \\gamma KL(k) + C$m with $\\gamma < 1$. As it has been identified in the prior art, such an inequality is the consequence of the distribution of the iterates satisfying a logarithmic Sobolev inequality (LSI). Unfortunately, prior works either relied on strong assumptions (eg, strong convexity), or did not prove a time-uniform bound on this log-Sobolev constant, hence leading to vanishing decay. Moreover, when dealing with the discrete-time algorithm, a lot of prior works provide bounds that do not vanish as $n\\to\\infty$.\n\nIn this paper, the authors tackle the above issue by decomposing each iteration into a gradient and a contraction step. Along with other technical elements, they use it to prove that under previously considered dissipativity and pseudo-Lipschitz assumptions, the log-Sobolev constants can be time-uniformly bounded, hence leading to improved generalization bounds. Finally, the authors relax the dissipativity assumption by introducing ergodicity constants characterising the convergence of the iterates to the Gibbs distribution.", "questions": "", "limitations": "", "rating": 4, "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": "We are sincerely grateful for your time, your very detailed review and feedback. We will add a discussion of the limitation you mention.\n\nThank you for spotting the typos, here are a few details to answer some of the remarks:\n- Definition A.1: In integral form the expectation is the following:\n\n $$\n \\Tilde{\\mathbb{E}}_{k, q}[h({X'_k})] = \\mathbb{E}_{X'_k}[\\phi_q(X'_k)h(X'_k)] = \\int h(x_k')\\phi_q(x'_k) p_{X_k'}(x_k')dx_k'\n $$\n\n When $q=1$ it cancels out the density of p_X_k'. We hope this clarifies the definition. We will add this in the text. With this clarification, there is no tilde in theorem 4.1, it should just be $X'_k$ in both terms. We will remove it, it was a typo. It is an integral under $X'_k$ modified by $\\phi_q$.\n \n - Lemma 5.4: Thank you.\n - Theorem 5.5: There should be a $d$ we will fix it.\n - Theorem 5.5: We will add the result of Chen et al for completeness so the $\\chi^2$ computation is easy to follow. The constant $31/32$ comes from factors $2$ from naive applications of Jensen. It can be tightened as described in appendix C. We will add explicitly the tightening argument.\n\n\nQuestions:\n- We will add Li et al. The only reason it wasn't included initially was because their discrete result tightens the Lipschitz dependence but has the same iteration count dependence as result already present in the table. Their secondary analysis was carried out for the continuous version of SGLD and an approximation argument was used to obtain the discrete result. This introduced a need for a vanishing stepsizes which we are trying to relax and it applies to the smaller class of bounded + $\\ell_2$ functions. \n- Indeed you are correct, in case II of their result they establish a decay factor for the slightly smaller class of Lipschitz + $\\ell_2$ functions. This corresponds to a subset of *strongly* dissipative functions discussed in our section 5.2. Our work relaxes this to simply dissipative. As their result is close so we will highlight it further. We loosen the structural requirements on the function further in section 6 where we show that we only need the LSI to hold without explicit structural requirements like Lipschitz + $\\ell_2$.\n- The continuous case for bounded + $\\ell_2$ has been analyzed before in Li et al but remains open for generally dissipative functions as far as we know. The continuous analysis is interesting as it can help to establish optimality indepedently of discretization error but the we believe the non-vanishing discretization error is the central difficulty of the analysis and so we keep our focus on the discrete setting. Indeed, if we could obtain exact samples of the Gibbs distribution, the generalization bound would be straightforward.\n\nWe thank you again for your review and we remain at your disposal for any further discussion.", "claims_and_evidence": "The main claims (regarding time-uniform bounds under dissipativity assumptions by a uniform bound on the log-So bole constant) are well-introduced and supported by a rigorous mathematical theory. The proof that SGLD iterates have uniformly bounded log-Sobolev constants is a strong result.\n\nRegarding these claims, my only remarks would by to (i) mention the pseudo-Lipschitz assumption in the introduction, as this assumption is essential to the stability approach (and might not be mild) and (ii) discuss the dimension-dependence that is obtained, which might be problematic in overparameterized settings.\n\nThe claim that dissipativity can be relaxed through ergodicity conditions is also well-supported by mathematical proofs. \nHowever, it is claimed at line 388 that these bounds have an improved dimension dependence. Looking at the constants appearing in Corollary 6.6, this does not seem to be the case, which might require more discussion.", "methods_and_evaluation_criteria": "The proposed proof technique is based on several existing works on this topic and the authors provide very nice additions to the existing techniques.", "theoretical_claims": "I checked the correctness of most theoretical claims, apart from some details in the proof corollary 6.6, regarding the exact expression of the error terms.\n\nHere are the remarks I have (please correct me if I am wrong):\n\n - Theorem 4.1: I find definition A.1 confusing, in particular it is not clear whether $\\Lambda_q$ means that we integrate over the $X_k'$ in $p_{X_k'}$ or if we integrate the function $p_{X_k} / p_{X_k'}$ over the distribution of $X_k'$ (for this reason I mainly checked the result when $q=1$). I think a few additional details would improve clarity a lot. \n\n- Theorem 4.1: in the expectation in the statement, there should be.a Tilde on the first $X_k'$.\n\n- Proof of Lemma 5.4: it should be $\\eta \\leq m^2 / 2L^2$ instead of $\\sqrt{m}/2L$.\n\n- Proof of theorem 5.5: $X_0$ has variance $\\eta / (\\beta d)$ while it is $\\eta / \\beta$ in the statement, this should be clarified. Moreover, I think it would be more standard to use the variance and not the standard deviation in the symbol $\\mathcal{N}$. \n\n- Proof of theorem 5.5: I think additional details on the result of [Chen et al.] would be very beneficial, as well as details of the $\\chi^2$ computation. The current version of the theorem is hard to check because of these two points and it is not clear where the constant $31/32$ comes from.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "This paper is strongly connected to the existing literature on generalization bounds for SGLD, to name a few: Mou et al., Li et al., Futami and Fujisawa.\n\n The authors provide nice improvements of the proof techniques existing in the literature, in particular regarding the use of the dissipativity assumption and the uniform bound on log-Sobolev constants.", "essential_references_not_discussed": "To my knowledge, the essential references regarding this line of work are discussed by the authors. \n\nA potential additional direction to discuss would be the extension to non-Gaussian noise, as recent works proved generalization bounds fror heavier-tailed versions of noisy SGD.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "Lemma f.4 is a repetition of Lemma fF.2, it could be removed.", "questions_for_authors": "In addition to all the points mentioned above, I would have the following questions:\n\n - Is there a reason why the paper of [Li et al., 2019] not presented in Table 1?\n\n - You mention that the bound of [Mou et al.] has a degrading decay factor. For me this is only true for the results of [Mou et al.] in the absence of regularisation. With regularisation, they obtain a constant decay. Could you discuss more the comparison with their bounds?\n \n - You results focus on the discrete-time case, do you consider that previous work provided optimal bounds in the continuous-time case?", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper considers stochastic gradient langevin dynamics on non-convex landscapes. Authors derive information theoretic generalization bounds for SGLD, which is stable under the number of iterations. Several conditions that appeared in prior works have been relaxed in this paper. Paper shows that SGLD can achieve generalization bounds that are stable in number of iterations, in non-convex settings.

This paper was reviewed by four expert reviewers the following Scores: Accept, Accept, Accept, Weak Accept. I think the paper is studying an interesting topic and the results are relevant to ICML community. The following concerns were brought up by the reviewers:

- Motivations is weak. 

- No new insights to be gained from the improvements in the paper.

- several typos and ambiguous statements were pointed by the reviewers. These should be carefully addressed.


Authors should carefully go over reviewers' suggestions and address any remaining concerns in their final revision. Based on the reviewers' suggestion, as well as my own assessment of the paper, I recommend including this paper to the ICML 2025 program.
Decision: Accept (poster)