Time-Independent Information-Theoretic Generalization Bounds for SGLD
Authors: Futoshi Futami
Masahiro Fujisawa
Venue: NeurIPS 2023 poster (2023)
Keywords: SGLD
Langevin dynamics
Generalization
Information theoretic analysis
TL;DR: We offer time-independent information-theoretic generalization bounds for stochastic gradient Langevin dynamics (SGLD) by focusing on the time evolution of the mutual information.

Abstract: We provide novel information-theoretic generalization bounds for stochastic gradient Langevin dynamics (SGLD) under the assumptions of smoothness and dissipativity, which are widely used in sampling and non-convex optimization studies.
Our bounds are time-independent and decay to zero as the sample size increases, regardless of the number of iterations and whether the step size is fixed.
Unlike previous studies, we derive the generalization error bounds by focusing on the time evolution of the Kullback--Leibler divergence, which is related to the stability of datasets and is the upper bound of the mutual information between output parameters and an input dataset.
Additionally, we establish the first information-theoretic generalization bound when the training and test loss are the same by showing that a loss function of SGLD is sub-exponential.
This bound is also time-independent and removes the problematic step size dependence in existing work, leading to an improved excess risk bound by combining our analysis with the existing non-convex optimization error bounds.

Time-Independent Information-Theoreti Generalization Bounds for SGLD
Futoshi Futami"
Masahiro Fujisawa"
Osaka University / RIKEN AIP futami futoshi. es@osaka-u ac. jp
RIKEN AIP
masabiro.
Abstract
We provide novel pntomattion-thereed generalization bounds for stochastic gradi- ent Langevin dynamies (SGLD) under the assumptions of smoothness and dissi- pativity, which are widely used sampling and non-convex optimization studies. Our bounds are time-independent and decay to zero the sample size increases, regardless the number of iterations and whether the step size fixed. Unlike previous studies, derive the generalization error bounds by focusing the time evolution the Kullback-Leibler divergence, which is related to the stability datasets and is the upper bound of the mutual information between output parame- ters and an input dataset. Additionally, we establish the first information -eematiio--thooetiic generalization bound when the training and test loss are the same by showing that loss function of SGLD is sub-exponential. This bound is also iimeinndeenddett and removes the problematic step size dependence in existing work, leading to im- proved excess risk bound by combining our analysis with the existing non-convex optimization error bounds.
Introduction
Stochastic optimization, including stochastic gradient descent (SGD), is central to realizing practical large-scale or deep-learning models. There are currently considerable active discussions on accurately determining the generalization performance of models trained by SGD or its variants. In particular, stochastic gradient Langevin dynamics (SGLD) [13, 39, 29], a noisy variant SGD, has garnered much attention in this type of study since it provides useful theoretical framework for generalization error analysis based on the Langevin diffusion context [29]. Our study aims to contribute a more accurate understanding and evaluation of the generalization performance for SGLD.
There are two main approaches generalization analysis SGLD. One the information -ieematiion--hooetiic analysis proposed by Russo and Zou [30] and Xu and Raginsky [40], by which a generalization error bound derived using the mutual information (MI) between the learned parameters and the training dataset. Recently, some extensions using gradient information have been made to investigate the generalization properties norm of gradients [28] and the sum of gradient variances [25, 35, 37, 36). coormation-theoretf generalization bounds are applicable to a wide range of noisy iterative algorithms such as differentially private SGD [11] and stochastic gradient Hamiltonian Monte Carlo [5] modified to include a noisy momentum.
SGLD, for example, upper-bounding the MI with the
The other approach is stability analysis, by which the effects of changes in the learning algorithm due the addition or removal of single training data point on the generalization performance are investigated. Raginsky et al. [29] derived the non-asymptotic generalization and excess risk bound of SGLD via the exponential ergodicity of Langevin diffusion. Starting with the study by Raginsky
"Equal contribution.
*Corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

et al. [29], there have been many attempts to improve the generalization analysis in SGLD from the stability perspective, such as those by Zhang et al. [43], Mou et al. [23] and Li et [20].
Unfortunately, these existing generalization bounds are time-dependent; namely, they diverge with increasing number of iterations unless the step size is adjusted so that the order of bound values is O(n"1) or (n 112),, where is the sample size (see Section 5 for details). Farghly and Rebeschini [10] attempted to avoid this problem by Wasserstein stability analysis through reflection coupling [9] under the smoothness and dissipativity [14] assumptions commonly used in sampling and non-convex optimization communities [29, 44]. Although their bounds bypass the divergence problem when taking a supremum
time, the geometry introduced for the reflection coupling yields an unnatural dependence on step size, resulting in a vacuous bound as the step size decreases (see Table 1).
In this paper, we provide novel generalization bounds for SGLD under smooth and dissipative loss functions obtained by the information-
approach. We focus on the upper bound of the MI, namely, the Kullback-Leibler (KL) divergence between the distributions of parameters learned from different training datasets. We then analyze its time evolution caused by the update of the SGLD algorithm through the Fokker-Plande (FP) equation (Lemma 1). On the basis of this analysis, obtain time- imm-independent generalization error bounds that decay to zero as n + DO regardless of the number of iterations whether the step size is fixed (Theorem 4 and Corollary 1). Conventional iiformationnthhoreeee generalization bounds [29, 28, 35, 36] are derived by bounding the MI between the parameters all iterations and the training dataset. Therefore, these bounds grow linearly with the number of iterations, resulting in a time-dependent generalization error bound. Our analysis based on time evolution eliminates both this linearity issue and the unnatural dependence on step size (the inverse of step size) in the time-independent bound of Farghly and Rebeschini [10].
Another contribution is providing the first information-theonn risk bound when the same loss is used for training and the generalization performance evaluation. In the conventional this setting was challenging owing to the unknown tail behavior of loss function of SGLD. We overcome this difficulty with our discovery that smooth and dissipative loss function of SGLD is sub-exponential.
generalization bound and the excess
-eemmatton-theoretti approach, deriving generalization error bounds under
Preliminaries
2.1
Problem settings and stochastic gradient Langevin dynamics
We represent random variables in capital letters, such as X, and deterministic values in lowercase letters. such as æ, and express the Euclidean inner product and distance as and | Let be an unknown generating distribution on the instance space 2 and w E W C TRd be the d-dimensional parameters such as weights of neural networks, where W is the space of the parameters. We consider a loss function : W x Z + I and the following optimization problem:
min (w) Ez[((w, Z)] /
l(w, Z)dp(2).
wEW
which cannot be computed since j is unknown. Instead, we typically minimize the empirical risk estimated using the dataset 5 = 7
1 n n
min Ls(w) = Σ I(w, Zt).
wEW
where [2 are independent and identically distributed (i.i.d.) samples from μr, i.e., Z lid.
J..
Stochastic gradient Langevin dynamics. In this paper, we use the SGLD algorithm [39] to solve the empirical risk minimization. SGLD utilizes the gradient information of the loss function; however, some loss functions, such as the 0-1 loss, are not differentiable. In this case, it is common to use the differentiable surrogate loss function W W Z R (e.g., the cross-entropy loss) and minimize the following empirical risk: Fs(w)= == E f (w, Z,). Given a mini-batch B C [r2] = {1.-...0 ,n]
with à
[B] S n, we define its mini-batch version
F(w, B) = k
Σ EEB
f(w, Z.).

---

The SGLD algorithm updates the parameters using the following recursion:
W4+1 W. - TI VVW,, B,) v 23, 'nE,
Wo Pwo.
where Pw. is a given initial distribution, (F B) is a stochastic gradient, is the number of iterations, 7 is the step size, 3e is the inverse temperature, and (Bt) is an wi.d. sequence of random variables distributed uniformly on {B C [n] B = k). In addition, (E)) is an i.i.d. sequence of standard Gaussian random variables, i.e., & (0, Ia). where I is the d-dimensional identity matrix. The output parameters W E W obtained using SGLD can be seen as the samples from a conditional distribution Pw]s 2 + W. We express the f-th output of the SGLD algorithm as W,-
2.2
Expected generalization error and its bounds
The focus of this paper is the expected generalization error, defined as
gen(u, PWis; L) := [E,, Ls(W)),
(I)
where the expectation is taken over the joint distribution of (S, W), i.e., nr' @ Pwis-
intormation-theoretii generalization bounds. Russo and Zou [30] and Xu and Raginsky [40] have shown that Eq. (1) can be bounded by the MI between the input dataset S and the output parameters W under the following sub-Gaussian assumption.
Assumption Saus-Gaussian losses). A loss function Iww Z) is sub- Gaussian under Z a for all w E W, that is, there is a positive constant o such that log Ez Ez (exp(A((((w Z) El (w, Z))) S X²og/ for all constant X R.
For example, bounded hipschiz-continuunn loss functions satisfy this assumption. Assumptions regarding the tail behavior of the loss function distributions as in the above are necessary for the infommation-theorettt generalization error analysis. Bu al. [3] have investigated information- theoretic generalization bounds with another tail-behavior assumption such sub-exponential losses.
We introduce the following standard cntommaiion-thooretti generalization bound.
Theorem 1 (Russo and Zou [30] and Xu and Raginsky [40]). Suppose that Assumption I holds. Then, we have
200 V V
1 SW:
Igen(e, Pwis; L)1
(2)
under a training dataset S = (Z and the algorithm's output W, where I(W;S) is the MI
between W and S.
In the SGLD context, 1(W,S) of Eq. (2) can be upper-bounded in a form that incorporates the gradient variance [28, 25, 35, 36). Given the output of the -- iterate of the SGLD algorithm, Wr, the following upper bound can be obtained.
Theorem 2 (Modified bound of Pensia et al. [28]). Let f(, an L-Lipschitz continuous function, namely, there is constant L >> 0 such that [[[ z) fw, =) I L|IW w|l holds for all w E W and all z E Z. Then, we obtain
d log 1 Boh d
d log (1+ 1+ Bemll²)
S)
Var Var,
(3)
where FWW, variance.
WWellV V f(W, B)]l[[]] is the conditional
Note that bound can be obtained by the data-processing inequality [6].
The merit of such informationn-heoreee generalization bounds that we can evaluate the bound value using the empirically estimated gradient variance per iteration. However, unfortunately, from Eq. (3), this bound is time- dependeennnnt; namely, the bound value can diverge unless the gradient variance or T + This is due the processing inequality when deriving upper bound (i) in Eq. (3). By the data-processing inequality, obtain I(Wr; 8) < (TW(T)) S), where
3yn approaches
3

---

W( = (Wo. Wi,... Wr) denotes the joint random variables appearing in all the iterations in the algorithm. Since W(T) is treated simultancously, the bound is inevitably linear in T'.
Another limitation of the information- -ehoorrttcc approach appears in the setting where training losses (f) are also used for performance evaluation, which is often employed in sampling and non-convex optimization studies of SGLD [29, 41J. In this setting, the generalization error is defined
gen(p, Pwis: F) W (W) Fss,)))
where F2 = (w Z)J. We cannot conduct the information-theooe analysis for Eq. (4) because the tail behavior of the distribution of the training loss is unclear.
Time-independent generalization bounds for Eq. (4). To solve the above problems, Farghly and Rebeschini [10] provided the generalization error bounds of Eq. (4) from the stability perspective under the following assumptions widely used in the non-convex optimization analysis SGLD [29, 41, 19].
Assumption 2 (Smoothness). For each E Z. f(-.z) is differentiable and M-smooth. That is, there a positive constant M for all w, w W and all E Z such that
[V, 2) - V =)1l S M| w//-
Assumption 3 (Dissipativity [14]). For each E Z, f(; is (m, b)-dissipatiie. positive constants m and for all w E W and E such that
That is, there
m||w||2 b - V fw, 2) w.
The discussion regarding loss functions that satisfy Assumption 3 is presented in Appendix B.
Hereafter, we eliminate the time dependence of the step size and temperature by setting 1 7 and 3e = B. With this notation, Farghly and Rebeschini [10] derived the following generalization bound.
Theorem 3 (Farghly and Rebeschini [10]). Suppose that Assumptions 2 and hold. Assume that the initial law of Wo has a finite fourth moment a.. Then, 17 S 1/2m, for any T N, we have
Igen(u, Pwris: F)I <i (1TT
T2(22 + 1) n -
12 + t1) 1///2)
(5)
where (x A v) min(x, y}. and C₁ and C2 are the positive constant terms w.r.t. {M, m, b, b, B,03 and (M, m, b, d, B), respectively.
Farghly and Rebeschini [10] utilized the Wasserstein stability the basis of the contraction property of Langevin diffusion under reflection coupling. The important technique to derive the above bound approach when
that we only focus on WT differently from W'() of the information-theon deriving the contraction property. In this way, the resulting bounds do not suffer from divergence as T -> oc; however, it still has a problem. That is, Eq. (5) depends on the factor 1//2, which implies that it becomes vacuous or even diverges with decreasing n)(= (r) as -> Do.
In this paper, we propose new generalization bounds to address the drawbacks of the information- theoretic and stability- approaches. Specifically, the proposed bounds are established on the basis of the two expected generalization errors outlined in Eqs. (1) and (4), which remain time- independent and do not diverge as the step size decreases.
3 Time-independent generalization error bound for SGLD
Here, we explain our time-independent bound of gen(μ, Pwis; I.) for SGLD. We first introduce the main result (Section 3.1) and then summarize its proof outline (Sections 3.2 and 3.3). Finally, in Section 3.4, we provide detailed discussion on our bound with concrete examples.
This assumption holds not only for (strongly) convex losses but also for many practically used non non-convex loss functions [24]. For example, it applies to non-convex loss functions with le constraints and likelihood functions that satisfy Poincaré inequality [2. 32).

---

3.1 Main result
Our key idea is to derive the generalized error bound using the FP equation. To use the FP equation. we impose the following regularity condition for Pw..
Assumption 4 (Regularity of the initial distribution). The initial distribution of Wo: Pwo Gaussian distribution with finite variance s² > 0, which is independent of n and T.
Our analysis is also grounded in the time evolution the FP equation using the logarithmic Sobolev inequality (LSD) [2] associated with ı described as follows. We state that satisfies the LSI with constant CLS, if for any p & n, the following relation holds:
(T.(pl=) CLS R V log p V log m1/²
Raginsky et al. [29] showed the existence of CLS under Assumptions 2, 3, and 3 2 2/m. Note that CLS is expressed by the problem-dependent constant (see Appendix F.1 for details).
We now introduce our generalization error bound.
Theorem 4. Suppose that Assumptions 1, 2, 3, and 4 are satisfied. Then, for any 2 2/m and E (0, A A 480rs) and any T E N, we have
m 5
20103 Igen(u, 1w L)I S
n/ (1^
(Vv + 02),
(6)
n
48CLS
where cı, c22 and VV are the positive constant terms w.r.t. {M, m, b, d, 3,5).
The above theorem shows ( Pwy L) dence since it does not diverge even if Do and thus converges as n co.
which implies time indepen-
In Eq. (6), the term V/ corresponds to stability, which is expressed as the upper bound of the difference of the expected conditional gradients with respect to changes in training datasets each iteration. This shows a certain similarity to existing information-theorede
generalization bounds, such as Theorem 2, expressed by the variance of gradients with respect to the training datasets. This similarity is discussed in detail in Section 3.4. Additionally, detailed information on the explicit expression of e1, C22 and Va can found Appendix F.
3.2 Proof outline of Theorem 4
In this section, we present how to derive our bound in Theorem 4. Our aim here is to share the ideas behind our analysis and an outline of the proof, providing the detailed proof in Appendix F.
We adopt the coormattonn-heorette approach and focus on the MI in Eq. (2). By using the Jensen inequality, have the following upper bound of the MI:
S) < Es,s (P
where S and S" are random variables drawn independently from μ²,, and KL Pw...s:) ) the KL divergence from Pwz)s to Pwr Note that this KL divergence indicates the stability of the learned parameter from two datasets, S and S'. We also note that Pw can be regarded as the data-dependent prior. Thus, this KL divergence tighter than that of the intepeddndeenn prior, which is often used in the probably approximately correct (PAC)-Baye bound 3.
The key idea is to analyze the time evolution of the KL. divergence, which summarized in the following lemma:
Lemma 1. Suppose that the same assumptions in Theorem 4 hold. Then, for any t E N, we have
KL(Pw,1s (w.1ss) Se -x30p KL(Pw, .1s Pw 115 + 1/Va + c37,
where VA and C3 is the constant term w.r.t. {M, m, b, d, s²).
The Gaussian assumption can be relaxed, e.g., Gaussian mixture, theorems corollaries shown in this paper. The detailed discussions are provided in Appendix F.3. We can confirm this from the fact that Eg, KL(PWy11 Pww1s*) = data-in data-independent prior distribution.
- KL IPw,). ). where Pwy is
5

---

We will discuss the details of Lemma in Section 3.3. By recursively applying Eq. (8) from t = 0 to
T, we obtain
KL(PW.Is//Wall 1
WT
(V + 0z) 4BOLS (I^
nT
2 (Vv + Cz),
apeus
which is based on the fact that (PaoPasssPWajs = O. Note that bound (i) can be obtained from
4P0LS
when
48eys 1, and AALLS
yf'
1639cts
4,80s"
3.3 Proof outline of Lemma 1 under the continuous Langevin diffusion
Here. we organize our ideas for the proof of Lemma 1 that are important in the derivation of Theorem 4. For simplicity, we now provide an intuitive explanation and an outline of the proof under the continuous Langevin diffusion setting. Note that the results of Theorem 4 and Lemma 1 are based on the SGLD setting, and their proofs are shown in Appendix F.
The Langevin diffusion is defined as
dW, VWW,, S)dt + /23-IdH,
where d/f is the standard Brownian motion in RR Note that, in this context, 1 expresses the continuous time and the full-batch gradient (F S) is used. The stationary distribution of Eq. (9) is given as the Gibbs distribution ग (dw) xx exp(-3F((e) (t),
With some abuse of notation, let denote Pw. is the conditional distribution obtained using Eq. (9) and express its density as pr. Then, the FP equation [2] for Eq. (9) can be obtained as
Opr 1) V (DVAL + FFW,,)
(10)
Öt
Similarly, we can define the Langevin diffusion when we use dataset S' and the conditional distribution using that diffusion as Pw.is with the density %/s obtaining the FP equation in the form of replaced by YY in Eq. (10).
Now we analyze the time evolution of KL(Pw,isi www.s//..iii. Pw,1s)) = kL(ptht) at time t, i.e. @KL(p)h)) By utilizing the FP equations of pt and %tt and the Cauchy-Schwartz Schwartz inequality, we obtain the following upper bound:
(KL(p)))) Øt S
1
(1I) The second term on the right-hand side of Eq. (11) represents the stability of the gradient with respect to the randomness of the training dataset S, ~ μ²,, which leads to V/ in Lemma I under the SGLD setting. Hereafter, we define E|| F.,,, S) VF(W,, S²2 as VE,-
B BlIV log v log roll VF(,, - VF(W,,
2B
By introducing V log (w) into E|| V log Pr
V lol in Eq. (11), obtain
OKL(p=) Ot
1
B EV log Vlog% Vv.
E V log V log 1
+
B
log 1|2 + EV
48
2
2
1
B
s 4,9CLS
(T((PeTT) + R(pr, ne, T) +
V
2,3
2
(KT.(p))x))
Elog ?t
+ s(pt, Tio
1
B
Vv.:
(12)
-,,CLS
2
2
where the first inequality is from the fact that -2² -1 y 2/2 + y2 for x, Hd and the
second one is from the LSI. We introduced A(pr, 7o, π) == Ep. V log π 2 2EE, V log P: V log 7 simplify the notation.
By integrating api aKL(pelTe) in Eq. (12) over t E [0, n] and rearranging it, we obtain Sr.
KT.(PTl))) S e LELL (T((p))2))
f
-(n-t)
B
E log ?t. + (pt.) de.
6 4BcLS
Ve.
(13)
2
4,CL
23

---

In Appendix F, we show that the terms related to :T in Eq. (13) can be bounded by using the techniques of Raginsky et [29] and Vempala and Wibisono [32].
We next derive an upper bound for the following terms in Eq. (13); E[log 24 and (pt, Tt πt by using the parametrix method for the FP equation [12, 27], which allows to expand the FP equation's ' solution via the heat kernel. On the basis of this expansion, we can upper bound Eq. (13) as
-(g-t)
E log
2t + Mpn ). 26m π 233
1
di S O()).
(14)
4,8CSS
By combining Eq. (14) with Eq. (13), obtain the continuous version of Lemma
The same procedure can be used for the SGLD setup. The difference from the continuous Langevin diffusion case is that the discretization errors and the effects of using stochastic gradient are taken into account, resulting in the appearance of an additional constant 4 in the above bounds (see Appendix F for details).
3.4 Additional discussion on our bound in terms of stability
We conclude this section by presenting further discussion on our bound in terms of stability with a concrete example.
As shown in Eq. (7), the information-theorete generalization bound is closely related the stability in KI. divergence under the different training datasets. However, our bound in Theorem 4 incorporates the constant term (2, which is irrelevant stability, alongside the stability term Vv. If avoid the occurrence of C2, the resulting upper bound of (s.,,iisP,,... would be dominantly expressed by Vr, and result, we may obtain bound where the relationship between generalization and stability is more directly represented.
The problematic constant term C2 arises from caf in Lemma analyzing the time evolution of stability in KL divergence. Specifically, the term Cy7 is the byproduct of treating the general dissipative function using LSL. Actually, it is possible to avoid the problematic constant term c37) and derive bounds that are evaluated solely on the basis of stability-related metrics in specific examples, such strongly convex bounded (non-convex) losses with Iz-regularization. For simplicity, show this fact using the following theorem under the Langevin diffusion (LD) setting, where the probability induced by Eq. (9) is expressed as Pwrrs.
Theorem 5. Suppose that Assumptions I and 2 are satisfied and that F(w, z) is R-strongly convex (0 < R < co). Then, for any T R,, we have
@KL(pelT) 0t
R + VIV((... E SVF
S -
(15)
and
2B
T
gen(u, Pwr|s; i L) S
(--1) VF(W,, V') (16)
n
similar bound Eq. (16) (with Rt replaced by 8/C) can be obtained for bounded non-convex
losses with Iz-regularization, where F(w, =) =0 Folw, =) + } [|||| (0 < < oo) and Fo =) is C-bounded (0 < C oc). The full proof is summarized in Appendix F.4.
When comparing with Lemma 1, we can see that, in Eq. (15), stbiiliy-uurelltte constants do not appear in the time evolution of KL. divergence at each time step. Therefore, the resulting generalization bound also independent of such constants. Furthermore, when compared with Theorem 2, which adds up the stability terms at all time steps, our bound is dominated by the stability terms near the final time step, those at carlier time steps decrease geometrically by e- 7. This indicates that the stability around the initial time steps is of lesser importance evaluating the final generalization performance.
Note that our bounds are closely related the bound indicated Proposition of Mou al. [23], which was also derived by focusing on stability. The bound of Mou et al. [23] primarily assesses
This constant is evaluable (see Vempala and Wibisono [32] Kinoshita and Suzuki [19]..
7

---

generalization errors focusing on the gradient norm near the conclusion of training. In contrast, our bounds evaluate it through the norm of differences in gradients, emphasizing the state in the proximity of training completion. In other words, our bound allows for the evaluation of generalization errors using a stability measure that more closely related to generalization performance than the gradient norm. This benefit originates from our approach, which tracks the time evolution of MI-related stability in Eq. (15) on the basis of nepemmtiinnthhooeee generalization bounds, in contrast to the PAC-Bayes bounds derived from the direct analysis of stability measures in Mou et al. [23].
4 Generalization analysis for SGLD directly using a training loss
In this section, we consider the setting that the generalization performance is measured by a training loss f directly as in Eq. (4). We show that this is possible by demonstrating that loss functions of SGLD are sub-exponential under smooth and dissipative assumptions (Section 4.1). On the basis of this fact, we obtain for the first time an informatoonttheee
generalization bound of SGLD that similar to Theorem 4. Finally, combining these results with existing optimization error bounds provides an excess risk bound with improved convergence (Section 4.2).
4.1 Smooth and dissipative loss function of SGLD is sub-exponential
To perform an information theoretic analysis for SGLD, it is necessary to know the tail behavior of f(W, Z). Our contribution here is showing that loss function of SGLD under smooth and dissipative assumptions is .ubbexxonential.
Theorem 6. Suppose that Assumptions 2, 3 and 4 are satisfied. Let Pw, = [Es[Pw, be the marginal distribution of the output obtained using the SGLD algorithm at the T -th iteration. Then, m and T N. f(Wr, Z) is sub-exponential under the distribution Pwr @ p That is, there exist positive constants o² and v w.rl {m, M, b, d, 52) such that
for any lj E (0, A 5MP)
x²²² for all | <
1
log Ewraz
2
Proof sketch. First, note that under Assumptions 2 and 3, for any 2 E Z, we obtain
b 2 log 3 S f(w, =) <
M |
v |||||
b + A,
m
+ +M,
My
(17)
m
where A is a positive constant (see Lemma 8 Appendix G.1 for its explicit form). By employing Lemma B.2 from Farghly and Rebeschini [10], we can show the following fact: for any E N,
BT 11""
Blll/ cc(p).
(18)
where
<(p) ( m
1 m
6 p-1 -
22p p l)d
[
M
P + +1+2
d
p-1
1
2b 2bb 8 m²
b
(2p 1)2
m3
B
This implies that Wr is a sub-Gausssian random variable according to Proposition 2.5.2 in Vershynin [33]. To show the sub-exponential property, we directly upper-bound by considering the Taylor expansion of the exponential mo- ment and using Eqs. (17) and (18) (see Appendix G.2 for the complete proof).
Ewrazle -B
analysis studies [28, 25, 35J, it is often assumed that a loss function I(w, Z) is Sab-Gaussian under the distribution is for all W. In contrast, Theorem 6 holds under the distribution Pw, @ p., not conditioned on w E W.
Remark In previous rnformation-theoreee
We can interpret the sub-exponential property of SGLD intuitively as follows. Under Assumptions 2 and 3, the loss function grows at most as a quadratic function shown in Eq. (17). The conditional distribution of the parameters follows the Gaussian distribution, and the square of the Gaussian random variable is known as the chi-square (x3) random variable [34]. According these facts, we expect that the behavior of the loss function resembles that of the x² 2rrandom variable; therefore, it sub-exponential since the x2 disttiiiitt is also sub-exponential [34]. Theorem validates this intuition.
3 The explicit form of a² and can be seen in Appendix G.2.
8

---

4.2 Generalization bounds for SGLD using the same loss for training and evaluation
On the basis of Theorem 6, we can derive the following information -heeorrtt generalization bound for SGLD even if surrogate loss is not used. In contrast to Theorem 4, an assumption regarding the tail behavior of loss function such as Assumption
not necessary.
Corollary 1. Suppose that Assumptions 2, 3, and 4 are satisfied. Then. for any B 2 2/m, n (0,1A 6M
the A 48CLS), and T E N, we obtain
Igen(u, Pwrls; F)] S v (a
Tff'
(V+ + +2))
1A
4BCLS
where
V202y
it
(1)
vy
otherwise
61 and 02 are the same as in Theorem 4, and o² and v are the same as in Theorem 6.
Proof sketch. This is the direct consequence of the sub-exponential property from Theorem 6 and the upper bound MI in Eq. (7) (see Appendix G.3 for the complete proof).
Remark 2. Despite the assumptions of Corollary being the same as those made by Farghly and Rebeschini [10] except for the initial distribution and step size, the resulting bound becomes 0 as n + 00 without being dependent on inverse stepsize.
We conclude this section by introducing our excess risk bound. Let define the excess risk as follows: Excess(p, Pwis) == EE..s [F (W) - -Fu(w") where w" = argmin (ww).. Under this definition, we derive the following upper bound for the excess risk by utilizing Corollary 1.
Corollary 2. Suppose that Assumptions 2, 3, and 4 are satisfied. Then, for any 3 2 2/m, n E (0, 1 SAT 48crs),, and T E N, we obtain
Excess(1, Pwr]s)= = =0(v
(1T A1)
-T////s + VT Cere
where Core is the positive constant w.r.f. {M, m, b. 3} corresponding to the optimizution error.
We show the complete proof Appendix G.4. In contrast with the existing excess risk studies, our bound does not diverge with increasing 1 owing to the time-independent generalization bound in Corollary I.
Related studies and discussion
In this section, compare generalization bounds with those in related studies. Table shows the order of each bound value along with its assumptions for a loss function.
SGLD analysis with/without changing losses. The existing generalization error bounds in Table I are dependennndntt; namely, we need to impose restrictive conditions for the step size 1 in terms of t to achieve generalization bound that decays zero with increasing sample size [29, 28, 25, 35] (see
the right column in Table 1). Some important applications of SGLD do not satisfy these conditions. For instance, the short-run Markov chain Monte Carlo [26] method used in energy-based models [17] adopts SGLD with a fixed step size. Another example is the cyclic SGLD [42] used in deep learning, where the step size is periodically increased decreased to facilitate escape from local optima.
Farghly and Rebeschini [10] first analyzed the generalization error of SGLD by using smoothness and dissipative assumptions, which are broadly used in sampling and non-convex optimization studies [29, 41, 4, 44]. Their bound is sime-independent; the bound does not diverge with time and achieves the order O1122). However, the bound depends on the inverse step size 1y -1/2 owing to the reflection coupling [9], which results in the unnatural behavior of decreasing 1) with increasing I. Farghly and Rebeschini [10] also derived a bound that does not suffer from this problem by assuming the Lipschitz loss function with weight decay; however, these assumptions excessively restrict the

---

Table 1: Comparison of our bounds with those in existing studies. Our bounds are iimeinneppnndent and bounded even if 17 + O. (I) denotes the informatioo-theorette approach and (S) denotes the stability analysis approach. The symbol means that the sub- Gaussian assumption is unnecessary for our bounds when using the same loss for training and generalization performance evaluation. Namely, our bounds can be derived under more relaxed assumptions for a loss function in this case.
Study
Assumptions a loss function
Expected generalization error bound
(S) Raginsky et al. (29) (Thm. 2.1.)
Dissipative. Smoothness
Onj + W/s + 1/u)
(S) Mou al. [23] (Thm. 1.)
Bounded, Lipschitz
(vit/n)
(S) Mou ot al. [23) (Thm. 2.)
Lipschitz. Sub-Gaussian, (Weight decay)
((v flggt 17/1)
(I) Pensia et al. (28) (Cor. 1.)
Lipschitz. Sub-Gaussian
(lv wt/n))
(1) Negrea et al. [25) (Thm. 3.1.)
Sub-Gaussan
(y/t//))
Farghly and Rebeschini [10] (Thm. 3.1.)
Lipschitz, Smoothness, Weight decay
0 ( ()(11n++++)))
(S) Furghly and Rebeschini [10] (Thm. 4.1.)
Dissiputive, Smoothness
(I) Wang et [35] (Thm.
Sub-Gaussian Dissipative, Smeothness, Sub-Gaussian
(1) Ours (Thm. and Cor.
My V/it 11/m)
class of loss functions and algorithms. In contrast to these bounds, our bound is time-independent and does not require scaling 7,, t, and n to achieve (n-1/)
Time evolution analysis of MI via FP equation. The analysis of SGLD using the FP equation has been successfully used in the convergence analysis of SGLLD [32, 19). These studies present analyses of the discretization errors and convergence properties of the unadjusted Langevin algorithm, SGLDD, and pariance-reduction SGLD (SVRG-I.D) [8], comparing them with the continuous Langevin dynamics through the FP equation.
In generalization error analysis, the FP equation is mainly used to analyze the time evolution of KL divergence appearing in generalization bound on the basis of the stability approach. Li et al. [20] analyzed the time evolution of the KL divergence between the probability densities of the parameters obtained from two training datasets that differ by only one data point under the bounded loss assumption. Mou et al. [23] also studied the KI. divergence and Hellinger divergence, and they derived generalization error bound on the basis of the PAC-Bayes notion [22]. Our idea is similar to these: we analyze the time evolution of the KI. divergence between the probability densities of the parameters obtained from two training datasets. The differences between our approach and other approaches are twofold. First, we do not assume weight decay or Lipschitz continuity but instead derive our analysis assuming smoothness and dissipativity. Second, the KL divergence we analyzed is tighter than that of the PAC-Bayes bound with data-independent prior dealt by Mou et al. [23].
Limitations and future work
In this paper, we provide generalization analysis of SGLD, where Gaussian noise is fundamental assumption for our theoretical results. Thus, it is difficult to extend our analysis to other noisy iterative algorithm variants with a different noise, such as differentially private SGD with Laplace or uniform noise [36]. Another limitation of this study is that we have estimated the sub-exponential parameter roughly with respect to the dimensions of the model parameters. Further investigation of the sub-exponentiality of smooth and dissipative losses, and improvement of the dependence on dimensionality, are crucial for enhancing the practicality of our generalization bounds. The lub-exponential property of loss function is expected to be helpful in fields other than generalized error analysis. For example, this property opens up room for new theoretical analysis policies that employ useful concentration and transport inequalities [34] in the sampling and optimization context. We hope that the analysis presented in this paper goes beyond generalization analysis and provides valuable insights into understanding the characteristics of machine learning.
6 The order of the bound in Mou et al. [23] varies with the choice of regularization parameters and decay factors. In this paper, we adopt the order of this bound in Table I of Farghly and Rebeschini [10]. For a more comprehensive discussion, we refer Section 5.2 of Mou al. [23].
10

---

Acknowledgments and Disclosure of Funding
We sincerely appreciate the anonymous reviewers for their insightful feedback. FF was supported by JSPS KAKENHI Grant Number JP23K 19948. FF was supported by JST, PRESTO Grant Number JPMJPR22C8, Japan. MF was supported by RIKEN Special Postdoctoral Researcher Program. MF was supported by JST, ACT-X Grant Number JPMJAX210K, Japan.
References
[1] R. Amit, B. Epstein, S. Moran, and R. Meir. Integral probability metrics PAC-bayes bounds. In Advances Neural Information Processing Systems, 2022.
[2] D. Bakry, I. Gentil, and M. Ledoux. Analysis and Geometry of Markov Diffusson Operators, volume 348. Springer Science & Business Media, 2013.
[3] Y. Bu, S. Zou, and V. V. Veeravalli. Tightening mutual information bounds on generaliza- tion error. IEEE Journal on Selected Areas in Information Theory, 1(1):121-130, 2020.
[4] N. H. Chau, É. Moulines, M. Rásonyi, S. Sabanis, and Zhang. On stochastic gradient Langevin dynamics with dependent data streams: The fully nonconvex case. SIAM Journal on Mathematics of Data Science, 3(3):959 986, 2021.
[5] Chen, E. Fox, and C. Guestrin. Stochastic gradient Hamiltonian Monte Carlo. In Proceedings of the 31st International Conference Machine Learning, volume 32, pages 1683-1691, 2014.
[6] T. M. Cover and J. A. Thomas. Elements of Information Theory. John Wiley & Sons, 2012.
[7] Deck and S. Kruse. Parabolic differential equations with unbounded coefficients generalization of the parametrix method. Acta Applicandae Mathematica, 74:71 14:71-91 1-911,99,-0 2002.
[8] K. A. Dubey, S. J. Reddi, S. A. Williamson, B. Poczos, A. Smola, and E. P. Xing. Variance reduction stochastic gradient Langevin dynamics. In Advances in Neural Information Processing Systems, volume 29, pages 1154-1162, 2016.
[9] A. Eberle. Reflection couplings and contraction rates for diffusions. Probability Theory and Related Fields, 166:851-886, 2021.
[10] T. Farghly and P. Rebeschini. Time-inde fime-independent generalization bounds for SGLD in non- convex settings. Advances Neural Information Processing Systems, volume 34, pages 19836-19846, 2021.
[11] V. Feldman, I. Mironov, K. Talwar, and A. Thakurta. Privacy amplification by iteration. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 521-532, 2018.
[12] A. Friedman. Partial Differential Equations of Purabolic Type. Courier Dover Publications, 2008.
[13] S. B. Gelfand and S. K. Mitter. Recursive stochastic algorithms for global optimization in Rd. SIAM Journal on Control and Optimization, 29(5):999-1018, 1991.
[14] J. K. Hale. Asymptotic Behavior of Dissipative Systems. Mathematical surveys and monographs. American Mathematical Society, 1988.
[15] H. Harutyunyan, M. Raginsky, G. Ver Steeg, and A. Galstyan. Cioommtiion-thooeete generaliza- tion bounds for black-box learning algorithms. In Advances in Neural Information Processing Systems, pages 26602-4468,, 2021.
[16] U. G. Haussmann and E. Pardoux. Time reversal of diffusions. The Annals of Probability, 14 (4):1188-128) 1986.
[17] G. E. Hinton. Training products of experts by minimizing contrastive divergence. Neural Computation, 14(8):1771-1800, 2002. 2002.

---

[18] Y. Jiang, B. Neyshabur, H. Mobahi, D. Krishnan, and S. Bengio. Fantastic generalization measures and where to find them. In The Tenth International Conference on Learning Repre- sentations, 2020.
[19] Y. Kinoshita and T. Suzuki. Improved convergence rate of stochastic gradient Langevin dynamics with variance reduction and its application to optimization. In Advances Neural Information Processing Systems, pages 19022-19033 2022.
[20] Li, X. Luo, and M. Qiao. On generalization error bounds of noisy gradient methods for non-convex learning. In The Eighth International Conference on Learning Representations, 2020.
[21] R. Livni. Information theoretic lower bounds for information theoretic upper bounds. arXiv preprint arXiv:2302.04925, 2022.
[22] D. A. McAllester. PAC-Bayesian stochastic model selection. Machine Learning, 51(1):5-21, 2003.
[23] W. Mou, L. Wang. X. Zhai, and K. Zheng. Generalization bounds of SGLD for non-convex learning: Two theoretical viewpoints. In Proceedings of the 31st Conference Learning Theory, volume 75, pages 605-638, 2018.
[24] W. Mou, N. Flammarion, M. J. Wainwright, and P. L. Bartlett. Improved bounds for discretiza- tion of Langevin diffusions: Near-optimal rates without convexity. Bernoulli, 28(3):1577 1601, 2022.
[25] J. Negrea, M. Haghifam, G. K. Dziugaite, A. Khisti, and D. M. Roy. Information-thhorriiic gen- eralization bounds for SGLD via data-dependent estimates. In Advances in Neural Information Processing Systems, volume 32, pages 1015-11025, 2019.
[26] E. Nijkamp, M. Hill, S.-C. Zhu, and Y. N. Wu. Learning non-convergent non-persistent short-run MCMC toward energy- based model. In Advances in Neural Information Processing Systems, volume 32, pages 5232-5242, 2019.
[27] G. A. Pavliotis. Stochastic processes and applications: Diffussoon processes, the Fokker-Planck and Langevin equations, volume 60. Springer, 2014.
[28] A. Pensia, V. Jog, and P.-L. Loh. Generalization error bounds for noisy, iterative algorithms. In 2018 IEEE International Symposium on Information Theory (ISIT), pages 546-550, 2018.
[29] M. Raginsky, A. Rakhlin, and M. Telgarsky. Non-convex learning via stochastic gradient Langevin dynamics: A nonasymptotic analysis. In Proceedings of the 30th Conference Learning Theory, volume 65, pages 1674-1703, 2017.
[30] D. Russo and J. Zou. Controlling bias in adaptive data analysis using information theory. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51, pages 1232-1240, 2016.
[31] S. Shalev-Shwart O. Shamir, N. Srebro, and K. Sridharan. Stochastic convex optimization. In Proceedings of the 22nd Conference on Learning Theory, 2009.
[32] S. Vempala and A. Wibisono. Rapid convergence of the unadjusted Langevin algorithm: Isoperimetry suffices. In Advances in Neural Information Processing Systems, volume 32, pages 8094-8106, 2019.
[33] R. Vershynin. High-dimensionss probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[34] M. J. Wainwright, High-Dimension Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
[35] H. Wang, Y. Huang, R. Gao, and F. Calmon. Analyzing the generalization capability of SGLD using properties of Gaussian channels. In Advances Neural Information Processing Systems, volume 34, pages
2021.
12

---

[36] H. Wang, R. Gao, and F. P. Calmon. Generalization bounds for noisy iterative algorithms using properties of additive noise channels. Journal of Machine Learning Research, 24(26):1-43, 2023.
[37] Z. Wang and Y. Mao. On the generalization of models trained with SGD: Information-theorreie bounds and implications. In The Tenth International Conference on Learning Representations, 2022.
[38] Z. Wang and Y. Mao. Tighter cioommtiiontteoreetie generalization bounds from supersamples. In Proceedings of the 40th International Conference on Machine Learning, volume 202, pages 361 16111-3637, 2023.
[39] M. Welling and Y. W. Teh. Bayesian learning via stochastic gradient Langevin dynamics. In Proceedings of the 28th International Conference on International Conference on Machine Learning, pages 681-688, 2011.
[40] A. Xu and M. Raginsky. Information-theoree -thooretic analysis of generalization capability of learning algorithms. In Advances in Neural Information Processing Systems, volume 30, pages 2524- 2533, 2017.
[41] Xu, J. Chen, D. Zou, and Q Gu. Global convergence of Langevin dynamics based algorithms for nonconvex optimization. In Advances in Neural Information Processing Systems, volume 31, pages 3126-3137 2018.
[42] R. Zhang, C. J. Zhang, C. Chen, and A. G. Wilson. Cyclical stochastic gradient MCMC for Bayesian deep learning. The Eighth International Conference on Learning Representations, 2020.
[43] Y. Zhang, P. Liang, and M. Charikar. A hitting time analysis of stochastic gradient Langevin dynamics. In Proceedings of the 30th Conference on Learning Theory, volume 65, pages 1980-2022, 2017.
[44] Y. Zhang, Ö. D. Akyildiz, T. Damoulas, and S. Sabanis. Nonasymptotic estimates for stochas- tic gradient Langevin dynamics under local conditions in nonconvex optimization. Applied Mathematics & Optimization, 87(25), 2021.
13


Reviews:
[{"review_id": "aKvmPgxQzE", "reviewer": "Reviewer_7RWp", "summary": "In the literature, there are two approaches to obtain generalization performance bounds. One approach is to study the algorithmic stability and there are well-known results that can bound the generalization error using the algorithmic stability bounds. Another approach is the information-theoretic analysis, which is the approach adopted in this paper. One major contribution of the paper is that it provides generalization bounds that do not grow linearly in time, and moreover, it also avoids an unnatural dependence on the stepsize. In addition, the paper provides additional results that provide information-theoretic generalization bound and the excess risk bound without relying on the surrogate losses. The author(s) are very familiar with the literature and the comparisons with the existing literature is ample and the contributions of the paper are clear.", "questions": "(1)\tIn the last sentence of Theorem 1, ``an training dataset’’, here ``an’’ should be ``a’’.\n(2)\tIn the paragraph before Theorem 1, can you provide a reference to the claim that ``This assumption is necessary to obtain the information-theoretic generalization bound.’’?\n(3)\tAssumption 4 seems to be a bit restrictive. Is it possible for example to relax this assumption to mixture of Gaussians or relax it in some other directions?\n(4)\tIn eqution (10), use \\left( and \\right).\n(5)\tPage 6. ``By integratng Eq. (12) over $t\\in[0,\\eta]$, we have’’ This does not seem to be rigorous. It seems to be that you should consider $\\partial/\\partial t(KL*e^{\\frac{1}{2\\beta c_{LS}}t})$ in (12) instead and then integrate over it.\n(6)\tIn the statements of Corollary 1 and Corollary 2, ``holds’’ should be ``hold’’.\n(7)\tIn remark 4, can you double check it is $s^2>1$? It seems to me it should be $s^2<1$ instead.\n(8)\tIn Remark 3 ``we often assume’’. It is better to write ``It is often assumed’’.\n(9)\tIn equation (19) on page 14, what is the integral $\\int\\left(\\frac{\\rho_{t}}{\\gamma_{t}}\\frac{\\partial\\gamma_{t}}{\\partial t}\\right)$ w.r.t.? Did you miss $dw$ or what? Please double check the other integrals on page 14 and page 15 as well.\n(10)\tAt the end of the first paragraph on page 17, what is $\\mathcal{W}[A]$? What does $[A]$ stand for?\n(11)\tIn the equation before equation (28), what does the notation $w^{d}$ stand for?\n", "limitations": "The authors have adequately discussed the limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "One major contribution of the paper is that it provides generalization bounds that do not grow linearly in time, and moreover, it also avoids an unnatural dependence on the stepsize. In addition, the paper provides additional results that provide information-theoretic generalization bound and the excess risk bound without relying on the surrogate losses. The author(s) are very familiar with the literature and the comparisons with the existing literature is ample and the contributions of the paper are clear.", "weaknesses": "One weakness is that even though the paper claims that the bound is independent of time $T$, I think some additional analysis is needed in Theorem 4 to make it more clear. For example, in Theorem 4, there is the term $V_{\\nabla}:=\\max_{t\\in[0,T]}\\beta\\text{Var}[\\nabla F(W_t,B_t)]$. I think the paper should include a lemma or something like that in the Appendix to explain how to provide an upper bound on $V_{\\nabla}$ that is uniform in $T$. My guess is that Lemma 6 in the Appendix or something like that can help. But it is better to provide an upper bound on $V_{\\nabla}$ to make it more clear your bound is uniform in $T$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our deepest appreciation for your insightful reviews.\nWe sincerely summarize our responses to you as follows.\n\n---\n## For Weaknesses\nWe appreciate your careful check. As you pointed out, the term $V_{\\Delta}:=\\max_{t\\in\\[0, T\\]}\\beta \\mathrm{Var}[\\nabla F(W_{t}, B_{t})]$ can be bounded with independent to $T$ and $\\eta$ by decomposing the variance at each time step into the sum of the gradient norm and applying Lemma 6. We have newly created Appendix C.3 and supplemented the explanation by adding the lemma. Then, we modified the following sentence before line 167:\n- ``In Appendix C, we provide further discussion, including the derivation of the upper bound of $\\beta \\mathrm{Var}[\\nabla F(W_{t}, B_{t})]$ with independence concerning $T$ and $\\eta$.’’\n---\n## For Questions\n### For questions (1), (4), (6), (8) (mainly focusing on typos):\nWe sincerely apologize for any inconvenience caused due to some typos.\nWe have fixed the above and carefully checked the other statements and equations overall paper.\n\n### For question (2) (about the citation before Theorem 1.):\nWe have modified the sentence, ``This assumption is…,’’ in lines 95–96 as follows ([24] == [Russo and Zou, 2016]; [31] == [Xu and Raginsky, 2017]):\n- ``Assumptions regarding the tail behavior of the loss function distributions, such as sub-Gaussianity, have been adopted in several studies, including Russo and Zou [24] and Xu and Raginsky [31], to obtain information-theoretic generalization bounds.’’\n\nThe issue with our original explanation is that it gives the impression that sub-Gaussian is a necessary assumption for deriving the information-theoretic generalization bound. Certainly, an assumption for loss functions w.r.t. randomness of datasets is necessary to derive the information-theoretic generalization bounds; however, that does not imply that sub-Gaussian is always necessary, as you know. For example, the sub-exponential, sub-gamma, or Lipschitzness assumptions are also widely used (please see [Russo and Zou, 2016]). We deeply regret any confusion that our misleading statements may have caused.\n\n### For question (3) (about Assumption 4):\nFollowing your advice, we have reconsidered relaxing Assumption 4.\nWe then found that Theorem 4 holds even when using a mixture distribution with each Gaussian distribution having a variance $s^{2}<1$.\nThis can be done by evaluating KL divergence in the same way as Theorem 4 for each component of the mixture Gaussian distribution thanks to the property of the convexity of the KL divergence.\nWe believe these discussions are too complex to be presented in the main part of this paper.\nTherefore, we have created Assumption C.4 and summarized the above explanation. We have further added the following sentence in the footnote on Assumption 4:\n- ``The Gaussian assumption can be relaxed, e.g., to Gaussian mixture, in the theorems and corollaries shown in this paper. The detailed discussions are provided in Appendix C.4.’’\n\n### For question (5) (about the integral in Eq.(12)):\nYou are right.\nWe have fixed ``By integrating Eq. (12)...’’ in line 214 as:\n- ``By integrating $e^{\\frac{t}{2\\beta c_{\\mathrm{LS}}}} \\frac{\\partial \\mathrm{KL}(\\rho_{t}|\\gamma_{t})}{\\partial t}$ in (12) over $t\\in[0,\\eta]$ and rearranging it, we obtain…’’\n\n### For question (7) (about $s^{2}>1$):\nThank you for carefully checking our manuscript.\nWe have modified it as $s^2<1$ in Remark 4.\nAs you are concerned, the condition $s^{2} < 1$ is necessary to ensure that the Gaussian integral does not diverge and to satisfy the initial condition of Corollary 1.\n\n### For question (9) (about the integral in Eq. (19)):\nWe deeply appreciate for reviewing the appendix part of our paper.\nAs you pointed out, we evaluate the integral in Eq.(19) w.r.t. dw. \nWe apologize and have made the corrections in lines 486–492.\n\n### For question (10) (about W[A] in p.17):\nThe term [A] is a typo. We have deleted this.\nWe are sorry for the inconvenience.\n\n### For question (11) (about $\\mathrm{d}w^{d}$):\nWe expressed the integral w.r.t. each $d$-dimensional parameters through $w^{d}$.\nHowever, it should have been written $\\mathrm{d}w$ for consistency with other descriptions.\nWe have modified the term $\\mathrm{d}w^{d}$ in line 548–555 as $\\mathrm{d}w$.\n\n## Reference\nPlease see our global responses."}, {"review_id": "a07guRxngA", "reviewer": "Reviewer_oJ4H", "summary": "The paper develops \"time-independent\" information-theoretic generalization bounds for SGLD. The key ingredients are: assuming the smoothness and dissipativity assumptions of the loss function , tracking evolution of the weight densities for two independent training sets, and their KL divergence. Such an approach avoids accumulation of the mutual information quantities over iterations.", "questions": "I am not familiar with dissapative losses. Assuming dissipativity is defined properly, are dissipative losses practically relevant? Can the authors give some loss functions that we use in practice satisfying this condition?", "limitations": "NONE", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The overall approach taken appears correct, and the results, if correct, are interesting and novel. It is unfortunate that the paper is not written clear enough for me assess the correctness of the results.", "weaknesses": "I think some important aspects of the paper are not presented clearly or contain errors.\n\n1. The definition of dissipativity appears wrong in Assumption 3: the right-hand side of the inequality is a not a scalar. Although this is easily fixable, it is upsetting to this reviewer that a central concept of the paper is not treated with care. \n2. In section 4 when the authors try to develop generalization bounds of SGLD without a surrogate loss. It is not clear to me how one would perform SGLD on say, the 0-1 loss, instead of on a differentiable surrogate loss: How would you get a gradient signal? -- In the opening paragraph of section 4, the paper states $l=f$. I speculate that the authors may be considering the case where SGLD is run on a differentiable surrogate loss but the generalization error is evaluated using the true loss (say 0-1 loss). If that is the case, I would imagine that somewhere a relationship between the true loss and the surrogate loss be given or assumed. But nowhere I can find it. That confused me and stopped me from further decoding what the authors intend to mean.  \n\n[After Rebuttal] I have read the authors' rebuttal and raised my rating to Weak Accept.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our deepest appreciation for your time and careful check.\n\n---\n## For Weaknesses\n### For weakness 1 (carelessness for dissipativity):\nFirst and foremost, we would like to extend our sincerest apologies for our carelessness.\nAs you pointed out, there was a typo in the dissipative assumption. Although the right-hand term in Definition 3 should be $\\nabla f(w,z) \\cdot w$, we accidentally dropped $\\nabla$ in front of $f(w,z)$. To be precise, the definition of dissipativity should be: $m||w||^2-b\\leq \\nabla f(w,z)\\cdot w$. We apologize and have corrected it here.\n\n### For weakness 2 (about the explanation in Section 4):\nWe sincerely regret our confusing explanations.\nWe would like to respectfully summarize and explain our intentions and contributions to you.\n\nSection 4 considers a scenario where we directly evaluate the generalization performance using a differentiable loss function $f$ (such as squared loss or logistic loss) employed during training. In other words, we examine the case where the loss function used for evaluating generalization performance ($l$) is the same as the loss function used during training ($f$). We thus do not consider the case when the non-differentiable loss such as the $0$-$1$ loss is used for training (e.g., we **do not assume setting 0-1 loss as $f$** as you mentioned). We regret that expressions such as *without surrogate losses* or *$l=f$* caused confusion. We have removed these expressions from our paper.\n\nThe case in which losses used for training are also used for performance evaluation is commonly employed in the theoretical studies of sampling and optimization for Langevin dynamics (please see [Raginsky et al., 2017] and [Xu et al., 2018]). In such studies, theoretical analyses are conducted based on the dissipative assumption that can be handled many non-convex losses, with a focus on deep learning. While the convergence of training errors or speed of convergence to a stationary distribution has been well-analyzed by the above studies, theoretical analysis of generalization ability is still insufficient. This background motivates us to conduct information-theoretic generalized error analysis, which also focuses on deep learning models, in a setting where the loss functions are identical for training and performance evaluation. In essence, our purpose is to enhance our understanding of both the optimization and generalization aspects of SGLD by analyzing generalization ability under the same settings and assumptions utilized in sampling and optimization research.\n\nWhy couldn't we perform a generalization error analysis based on the information-theoretic approach in the above setup? This is because the tail behavior of the loss function distribution used for training is unknown under the dissipative assumption (here, the loss function distribution is a distribution w.r.t. the dataset); thus, it is unclear whether the sub-Gaussian assumption is appropriate to assume for the dissipative losses.\nThis contrasts the settings in Section 3, where alternative losses with known tail behaviors were chosen (e.g., $f$ being a differentiable loss and $l$ being a 0-1 loss) to perform information-theoretic generalization error analysis for SGLD.\nOur contribution is to overcome this situation by showing the loss function with dissipativity and smoothness has the sub-exponential property in SGLD.\nThis allows us to apply the information-theoretic generalized error analysis to the dissipative and smooth losses commonly used in sampling and optimization studies of SGLD.\n\n## For Questions\nThe dissipative losses include all strongly convex and convex losses. The dissipative losses also include losses that are strongly convex or convex when sufficiently far from zero, that is, there exists $\\{m, R\\}>0$ such that $\\forall x, y \\ \\ \\mathrm{s.t.} \\ \\ ||x-y||^2 \\geq R, \\ \\  (x-y) \\cdot (\\nabla f(x,z) - \\nabla f(y,z)) \\geq m||x-y||^2$ or $\\forall x, y \\ \\ \\mathrm{s.t.} \\ \\ ||x-y||^2 \\geq R, \\ \\ (x-y)\\cdot (\\nabla f(x,z) - \\nabla f(y,z)) \\geq 0$ (please see [Mou et al., 2022]).\nThis means that the dissipative losses include the non-convex losses that have a local optimum somewhat close to zero and losses whose tail behavior is similar to the strongly convex losses. A typical example of losses that satisfy dissipativity is non-convex losses with $l_{2}$ regularization (please see [Mou et al., 2018]). Because of its capability to handle many non-convex losses, the dissipative condition is often employed in the theoretical analysis of non-convex optimization, such as [Raginsky et al., 2017] and [Xu et al., 2018].\n\nWhen considering the negative log-likelihood losses, which are often used in the Bayesian context, the likelihood distribution that satisfies the Poincar\\'{e} inequality exhibits the dissipative property (please see [Bakry et al., 2013] and [Vempara and Wibisono, 2019]).\nPoincar\\'{e} inequality is applicable to a wide range of practical likelihood distributions, such as log-concave distributions, distributions obtained via bounded perturbations of Poincar\\'{e}-inequality-satisfying (PIS) distributions, distributions with Gaussian convolution added to bounded losses, distributions formed by Lipschitz continuous transformations of PIS distributions, and direct sums of PIS distributions [Bakry et al., 2013]. Thus, this includes many useful models, including deep learning models [Mou et al. 2022; Vempara and Wibisono, 2019].\n\nIn essence, the dissipative assumption allows for the broad treatment of not only general non-convex optimization in machine learning but also non-convex losses used in Bayesian inference and Bayesian machine learning.\nOn the other hand, it is essential to note that thick-tailed losses, such as long-tailed t-distributions or Cauchy distributions, cannot be handled by the dissipativity assumption [Mou et al. 2022].\n\n## References & modifications\nPlease see our global responses."}, {"review_id": "ZF4Y6HWeJM", "reviewer": "Reviewer_h7LH", "summary": "This paper provides novel generalization bounds for SGLD under smooth and dissipative loss conditions via the information-theoretic approach. The proposed bounds are time-independent and decay to zero as the sample size increases, regardless of the number of iterations and whether the step size is fixed. In addition, the proposed bound also leads to an improved excess risk bound by combining the analysis with the existing non-convex optimization error bounds.", "questions": "It is shown in [1] that the generalization error of the Gibbs algorithm equals the symmetrized KL information between W and S. Under the sub-Gaussian condition, it can be further proved that the generalization error of the Gibbs algorithm has the order of $O(1/n)$ independent of dimension d and time t.  \n\nAs shown in Table 1, it seems that the bound provided by Farghly and Rebeschini is able to recover this 1/n rate for the generalization error Gibbs distribution but with an extra term $\\eta^{1/2}$ for SGLD.\n\nHowever, the bound provided in this paper only scales in the order of $O(1/\\sqrt{n})$. Could you please provide more insights into whether this gap is due to the mismatch between the Gibbs distribution and the SGLD or it is due to the looseness of mutual information-based bound? My guess would be the issue of mutual information-based bound, and maybe the techniques developed in the following recent paper [2,3] might be helpful.\n\n[1] Aminian, Gholamali, Yuheng Bu, Laura Toni, Miguel Rodrigues, and Gregory Wornell. \"An exact characterization of the generalization error for the Gibbs algorithm.\" Advances in Neural Information Processing Systems 34 (2021): 8106-8118.\n\n[2] Zhou, Ruida, Chao Tian, and Tie Liu. \"Exactly Tight Information-Theoretic Generalization Error Bound for the Quadratic Gaussian Problem.\" arXiv preprint arXiv:2305.00876 (2023).\n\n[3] Wu, Xuetong, Jonathan H. Manton, Uwe Aickelin, and Jingge Zhu. \"Fast rate generalization error bounds: Variations on a theme.\" In 2022 IEEE Information Theory Workshop (ITW), pp. 43-48. IEEE, 2022.\n\n", "limitations": "The limitations of the proposed method have been addressed well in the last section of the paper. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The combination of information-theoretic bounds and Fokker–Planck (FP) equation establishes the tighter bounds provided in the paper, which is impressive.", "weaknesses": "I did not note any significant weakness in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our deepest appreciation for your insightful reviews and for giving us very convincing papers. \nWe sincerely summarize our responses to you as follows.\n\n---\n\n## For Questions\nThank you for your insightful feedback.\nAs you pointed out, our derived bounds are based on the mutual information between $S$ and $W$, which often leads to slow convergence with the order O(1/sqrt{n}), and thus, our bound inherits same slow convergence order (please see [Bu et al., 2020] and [2,3] you raised.)\nIt might indeed be possible to derive improved bounds on the rates if the techniques presented in [2,3] you provided can be utilized in a generalization error analysis for SGLD.\n\nSince the objective of this paper is to derive the time-independent information-theoretic bound in the SGLD context, our analysis was conducted under the most fundamental bound in Theorem 1. We believe that improving the convergence rate is an essential task for the future.\n\n## Reference\nPlease see our global responses.\n"}, {"review_id": "pvYqYsNoTY", "reviewer": "Reviewer_sqKQ", "summary": "The paper provides novel information-theoretic generalization bounds for the SGLD. They derive the generalization error bounds by focusing on the time evolution of the Kullback–Leibler divergence.  The bound is   time-independent and removes the step size dependence in previous works.", "questions": "see weakness part.", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper provides novel generalization bounds for SGLD by using the Kullback–Leibler (KL) divergence between the distributions of parameters learned from different training datasets.\n\n2. The authors provide the first information-theoretic generalization error bound and the excess risk bound without surrogate losses.", "weaknesses": "\n1. Although the authors claim they provide the first information-theoretic generalization error bound and the excess risk bound without surrogate losses, they indeed use the dissipativity to fix the non-convexity in the proofs.\n \n2.  I feel a little overclaimed on the stepsize because you use the dissipativity, which can be a kind of weak \"strongly convexity\". In the strongly convex case of   SGLD,  the stepsize can also be improved.\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our deepest appreciation for your thoughtful reviews. We sincerely summarize our responses to you as follows.\n\n---\n## For Weaknesses (Questions)\n### For weakness 1 (about dissipativity):\nThe dissipative assumption plays an important role in guaranteeing the geometrical convergence of SGLD to the stationary distribution. We note that convergence to the stationary distribution is crucial for reducing training error since the stationary distribution in this context corresponds to the Gibbs posterior distribution of the given loss function. The dissipative assumption is widely used in the research on sampling or non-convex potential function optimization; thus, it is a fundamental property that enables optimization with SGLD rather than strong constraint conditions for generalization. As discussed by [Mou et al., 2022], the dissipative assumption is weaker than convexity and strong convexity. Many non-convex losses commonly used in practice satisfy this property. For specific examples, please see our response to the question from Reviewer oJ4H.\n\n### For weakness 2 (about our claim of contributions):\nWe believe that we are not overclaiming our contributions.\nAs you pointed out, it is indeed possible to improve the convergence rate w.r.t. learning rate if the loss function is strongly convex.\nOn the other hand, recent studies on sampling, optimization, and the generalization performance of SGLD, such as [Farghly and Rebeschini, 2021], [Xu et al., 2018], and [Raginsky et al., 2017], have focused on the non-convex losses to understand the deep learning models under the dissipative assumption. Moreover, the information-theoretic generalization analysis of SGLD often focuses on deep learning models whose losses are often non-convex and derives the data and algorithm-dependent generalization error bounds. Following this context, this paper analyzed the generalization error of SGLD dealing with non-convex losses under dissipative assumptions.\n\nFurthermore, the assumptions of our Theorem 4 in Section 3 are similar to those in [Farghly and Rebeschini, 2021], which provided the first time-independent bound for SGLD shown in Theorem 3 in Section 2, except for sub-Gaussianity. There is no need to assume sub-Gaussianity when using the same losses for training and generalization evaluation, enabling a direct comparison between our bound (Corollary 1)  and that of [Farghly and Rebeschini, 2021] (Theorem 3) under the completely same assumptions.\nIt is indeed a clear fact that in this fair comparison, our bound avoids the divergence observed in [Farghly and Rebeschini, 2021] due to the decrease in step size. We believe this is not an overclaim but a valid observation.\n\n## Reference\nPlease see our global responses.\n"}]

Author rebuttal:
Dear all PCs, SACs, ACs, and reviewers,

We sincerely appreciate your consideration of our paper.
We also would like to extend our deepest appreciation to the reviewers for providing insightful reviews.
Before summarizing our responses to each of the reviewers, due to word limitation, we organize the references and the modified sentences based on the received reviews as follows.
We would greatly appreciate it if you could confirm this.

Best regards,
Authors

---
## References
- [Russo and Zou, 2016]: D. Russo and J. Zou. Controlling bias in adaptive data analysis using information theory. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51, pages 1232–1240, 2016. http://proceedings.mlr.press/v51/russo16.pdf
- [Xu and Raginsky, 2017]: A. Xu and M. Raginsky. ``Information-theoretic analysis of generalization capability of learning algorithms.’’ In Advances in Neural Information Processing Systems, volume 30, pages 2524–2533, 2017. https://arxiv.org/pdf/1705.07809.pdf
- [Raginsky et al., 2017]: M. Raginsky, A. Rakhlin, and M. Telgarsky. ``Non-convex learning via stochastic gradient Langevin dynamics: A nonasymptotic analysis.’’ In Proceedings of the 2017 Conference on Learning Theory, volume 65, pages 1674–1703, 2017. https://arxiv.org/pdf/1702.03849.pdf (corresponds to [23])
- [Xu et al., 2018]: P. Xu, J. Chen, D. Zou, and Q. Gu. ``Global convergence of Langevin dynamics based algorithms for nonconvex optimization.’’ In Advances in Neural Information Processing Systems, volume 31, pages 3126–3137, 2018. https://arxiv.org/pdf/1707.06618.pdf (corresponds to [32])
- [Mou et al., 2022]: W. Mou, N. Flammarion, M. J. Wainwright, and P. L. Bartlett. ``Improved bounds for discretization of Langevin diffusions: Near-optimal rates without convexity.’’ Bernoulli 28(3): 1577–1601, August 2022. https://doi.org/10.3150/21-BEJ1343. https://projecteuclid.org/journals/bernoulli/volume-28/issue-3/Improved-bounds-for-discretization-of-Langevin-diffusions--Near-optimal/10.3150/21-BEJ1343.short (corresponds to [18])
- [Bakry et al., 2013]: D. Bakry, I. Gentil, and M. Ledoux. ``Analysis and Geometry of Markov Diffusion Operators,’’ volume 348. Springer Science & Business Media, 2013. https://link.springer.com/book/10.1007/978-3-319-00227-9 (corresponds to [1])
- [Vempara and Wibisono, 2019]: S. Vempala and A. Wibisono. ``Rapid convergence of the unadjusted Langevin algorithm: Isoperimetry suffices.’’ Advances in neural information processing systems, 32:8094–8106, 2019. https://arxiv.org/pdf/1903.08568.pdf (corresponds to [25])
- [Bu et al., 2020]: Y. Bu, S. Zou, and V. V. Veeravalli. ``Tightening mutual information-based bounds on generalization error.’’ IEEE Journal on Selected Areas in Information Theory, 1(1):121–130, 2020. https://arxiv.org/pdf/1901.04609.pdf
- [Farghly and Rebeschini, 2021]: T. Farghly and P. Rebeschini. ``Time-independent generalization bounds for SGLD in non-convex settings.’’ In Advances in Neural Information Processing Systems, volume 34, pages 19836–19846, 2021. https://openreview.net/pdf?id=tNT4APQ0Wgj
---
## Modifications
### From 7RWp's review
(We show them in our response for Reviewer 7RWp)
### From oJ4H's review
The following additions and corrections have been made to clearly explain the relationship between $f$ and $l$ and dissipativity.
- in lines 9–11: ``Additionally,...when the same loss is adopted for training and the generalization performance evaluation by showing…’’
- in lines 58–59: ``Another contribution is…when the same loss is used for training and the generalization performance evaluation.’’
- in lines 118–122: ``Another limitation of the information-theoretic approach appears in the setting where training losses ($f$) are also used for performance evaluation ($l$), which is often employed in sampling and non-convex optimization studies of SGLD [23, 32]. We could not conduct the information-theoretic analysis in this setting because the tail behavior of the distribution of the training loss, such as Assumption 1, is unclear.’’
- in line 123 (paragraph title): ``Time-independent generalization bounds under the same loss for training and the performance evaluation.’’
- in lines 123–126: ``To solve the above problems, Farghly and Rebeschini…when the same loss is adopted in training and performance metric from the stability…’’
- in lines 144–145: ``Specifically, the proposed bounds are…, and are available in both scenarios where the same loss is used for both training and generalization performance evaluation and when different losses are used.’’
- Title of Section 4. ``Generalization analysis for SGLD directly using a training loss’’
- in lines 227–229: ``Hereinafter, we consider the setting that the generalization performance is measured by a training loss $f$ directly.’’
- in lines 236–237: ``However, when using a training loss directly for the generalization performance measure, …’’
- Subsection title of Section 4.2: ``Generalization bounds for SGLD using the same loss for training and evaluation’’
- in line 293 (paragraph title): ``SGLD analysis with/without changing losses.’’
- in the statement of Table 1: ``The symbol * means…when using the same loss for training and evaluation of generalization performance.’’
- Section title of Appendix D.: ``Proofs of generalization analyses directly using a training loss’’
- in lines 573–574: ``In this section, we…in the case when the same loss is used for training and the generalization performance evaluation….’’
- Sub-section title of Appendix D.4: ``Proof of generalization error bound directly using a training loss’’
- the footnote of Assumption 4.: ``This assumption holds not only for (strongly) convex losses but also for many practically used non-convex loss functions [18]. For example, it applies to non-convex loss functions with $l_{2}$ constraints and likelihood functions that satisfy Poincar\'{e} inequality, such as Gaussian negative log-likelihood [1, 25].’’

Meta-review: - The paper provides a new time-independent information theoretic generalization bound.

- The bound was found to be interesting by the reviewers who favored the paper.

- During discussion, a limitation was raised, that no proof-of-concept was proposed for the utility of the bound.
- It was mentioned, that potentially the bound might be relevant only when there is some dependence on the dimension -- in that case time-independent bounds are trivial (uniform convergence)
- The authors raised the fact that this is indeed a limitation but may be a limitation to the whole approach of information-theoretic bounds -- they are correct in this.
- This limitation should be further discussed in the paper, and hopefully the authors could present a proof of concept for a case where the information bound is useful. 

- In the context of this paper, please note that L'22 provides a dimension-dependent lower bound on the mutual information that relies on a dissipative function (in fact a function of the form $\|w\|^2 + F_0(w)$. In other words, the structural assumptions suggested by the authors cannot circumvent dimension dependence without further assumptions.
Decision: Accept (poster)