Analyzing the Generalization Capability of SGLD Using Properties of Gaussian Channels
Authors: Hao Wang
Yizhe Huang
Rui Gao
Flavio Calmon
Venue: NeurIPS 2021 Poster (2021)
Keywords: Information theory
statistical learning theory

Abstract: Optimization is a key component for training machine learning models and has a strong impact on their generalization. In this paper, we consider a particular optimization method---the stochastic gradient Langevin dynamics (SGLD) algorithm---and investigate the generalization of models trained by SGLD. We derive a new generalization bound by connecting SGLD with Gaussian channels found in information and communication theory. Our bound can be computed from the training data and incorporates the variance of gradients for quantifying a particular kind of "sharpness" of the loss landscape. We also consider a closely related algorithm with SGLD, namely differentially private SGD (DP-SGD). We prove that the generalization capability of DP-SGD can be amplified by iteration. Specifically, our bound can be sharpened by including a time-decaying factor if the DP-SGD algorithm outputs the last iterate while keeping other iterates hidden. This decay factor enables the contribution of early iterations to our bound to reduce with time and is established by strong data processing inequalities---a fundamental tool in information theory. We demonstrate our bound through numerical experiments, showing that it can predict the behavior of the true generalization gap.

Analyzing the Generalization Capability of SGLD Using Properties of Gaussian Channels
Hao Wang Harvard University
Yizhe Huang
The University of Texas at Austin yizhehuang@utexas. edu
hao_wangog. harvard.
Rui Gao
Flavio P. Calmon
The University of Texas at Austin rui rui.gao maii.gom@mmommss utexas edu
Harvard University
flavio8seas. harvard.
Abstract
Optimization is key component for training machine learning models and has a strong impact on their generalization. In this paper, we consider a particu- lar optimization method- the stochastic gradient Langevin dynamics (SGLD) algorithm-an and investigate the generalization of models trained by SGLD. We derive new generalization bound by connecting SGLDD with Gaussian channels found in information and communication theory. Our bound can be computed from the training data and incorporates the variance of gradients for quantifying a particular kind of "sharpness" of the loss landscape. We also consider a closely related algorithm with SGLD, namely differentially private SGD (DP-SGD). We prove that the generalization capability of DP-SGD can be amplified by iteration. Specifically, our bound can sharpened by including a time-decaying factor if the DP-SGD algorithm outputs the last iterate while keeping other iterates hidden. This decay factor enables the contribution carly iterations to our bound to reduce with time and is established by strong data processing inequalities- fundamental tool in information theory. We demonstrate our bound through numerical experiments, showing that it can predict the behavior of the true generalization gap.
Introduction
Modern deep neural networks (DNNs) are highly expressive: they memorize entire training dataset and still generalize well to unseen data (Zhang et al., 2016). This empirical observation is not captured by traditional generalization bounds found in statistical learning theory, which attribute the generalization ability to the use of a hypothesis class with constrained complexity (Vapnik and Chervonenkis, 1971; Valiant, 1984). Recent studies demonstrate that different algorithmic choices and data distributions may yield DNNs with contrasting generalization behaviors (Hardt et al., 2016; Neyshabur al., 2017; Bartlett et al., 2017). In this paper, we study how optimization method used for training DNNs, namely the stochastic gradient Langevin dynamics (SGLD) algorithm (Gelfand and Mitter, 1991; Welling and Teh, 201 1),, may influence their generalization.
The SGLD algorithm is used in different practical settings. For example, it has been implemented in open-source libraries (Facebook AI, 2020; Radebaugh and Erlingsson, 2019) for training models with differential privacy guarantees (Dwork et al., 2006; Song et al., 2013; Abadi et al., 2016). The additive noise in the SGLD algorithm also mitigate overfitting for DNNs (Neelakantan al., 2015). Recently, there is an increasing number of efforts (see e.g.. Raginsky et al., 2017; Mou et al., 2018; Li et al., 2019; Pensia al., 2018: Negrea et al., 2019) that investigate the generalization properties the SGLD algorithm. It is within this body of work that the present paper is inscribed.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

10
1.0
70%
Training wosrree
0.0
50%
27%
0%
Oul bound
0.8
Geratalizaton
0.0
0.
17%
0.0K
25%
0.4K
02
90%
0.2K
200
400
600
800
1000
1200
1400
200
400
600
500
1000
1200
1400
200
400
600
000
1000
1200
1400
Epoch
Epoch
Epoch
Figure 1: Illustration of our generalization bound in Theorem We use the SGLD algorithm to train 3-layer neural networks MNIST when the training data have different label corruption level E (0%, 25%, 50%, 75%}. Left: training accuracy. Middle: (empirical) generalization gap. Right: (empirical) generalization bound. As shown, the generalization gap is increasing with respect and our bound can capture this phenomenon. We defer detailed discussions to Section 5.
We derive new generalization bound (Theorem 1) for the SGLD algorithm in Section Our bound (see Figure for an illustration) incorporates the variance of gradients, which can be estimated from the training data and captures a particular kind of "sharpness" of the loss landscape (Keskar et al., 2016). This variance term can also be predictive of the generalization gap shown in recent empirical study (Jiang et al., 2019). We consider a general setting in which the output from the SGLD algorithm be any function of the iterates. This is crucial since many theoretical analyses (see e.g.. Zhang et al., 2017; Jin et al., 2019) require the final output to be the iterate that achieves the smallest value of the loss function numerical experiments in Section suggest that our generalization bound is highly correlated with the true generalization gap.
average of the iterates, but not necessarily the last iterate. Finally, the
We also investigate the DP-SGD algorithm in Section In particular, we prove that if it known prior, that the algorithm outputs the last iterate rather than arbitrary function of all iterates, then our bound can be further tightened by incorporating a time-decaying factor. Our analysis is motivated by line of recent works (Feldman et al., 2018; Balle et al., 2019; Asoodeh et al., 2020) on privacy amplification by iteration. Specifically, the original work by Feldman et al. (2018) provided two intertwined observations of the DP-SGD algorithm: (i) not releasing the intermediate steps can amplify the privacy guarantees and (ii) data points used in the carly iterations get stronger privacy protection than those occurring late. In this paper, establish our generalization bound can be sharpened by incorporating a time-decaying factor if DP-SGD only outputs the last iterate (Theorem 2) and (ii) this decay factor enables the impact of early iterations our bound to reduce with time (Lemma 4).
analogous results: (i)
The proof techniques of this paper are based fundamental tools from information theory. We first use an information-theowe (2017) and further tightened by Bu et al. (2020), for deriving algorithmic generalization bound. This framework relates the generalization gap with the mutual information I [(W Z,) between the output parameter W from the SGLD algorithm and each individual data point Z,. However, estimating the mutual information from data is often intractable. Given this major challenge, our key contribution is connect the SGLD algorithm with well-understood notion in data transmission, namely additive white Gaussian noise (AWGN) channels. This connection allows us to use properties of Gaussian channels for analyzing the mutual information. First, upper bound I(W; Z4) using the variance of gradients by exploring the input-output mutual information of a Gaussian channel. This variance term can be estimated from the training data and is highly correlated with the true generalization gap. Second, we incorporate a time-decaying factor into our bound. This factor is established by strong data processing inequalities (Dobrushin, 1956: Cohen al., 1998) and has an intuitive interpretation: if a data point is used at an early iteration, its impact on the generalization gap reduces with time due to external Gaussian noise. The above two aspects correspond Lemma 4 and Lemma 5 which, in turn, are the basis of our main results in Theorem and Theorem 2.
framework, proposed by Russo and Zou (2016) and Xu and Raginsky
The supplementary material of this paper includes: (i) omitted proofs of all theoretical results and (ii) supporting experimental results.

---

Related Works
We contextualize our contributions in regard to existing literature (Mou et al., 2018; Li et al., 2019;
Pensia et al., 201 80 Bu et al., 2020; Negrea et al., 2019; Haghifam et al., 2020; Rodríguez- Gálvez et al., 2020; Neu et al., 2021). Among them, Mou et al. (2018) introduced two generalization bounds. The first one (Theorem 1 of Mou et al., 2018), stability- bound, achieves Q(1/n) rate in terms of the sample size n but relies the Lipschitz constant of the loss function which makes it A cerrriution-indepeddee
distribution- distribution-indeennddr capture empirical observations (c.g.. network trained using true labels generalizes better than network trained using corrupted labels as shown in Figure 1). The second one (Theorem 2 of Mou et al., 201 8), PAC-Bayes bound, replaces the Lipschitz constant by an expected-squaree gradient norm but suffers from a slower rate O(1/ D()/vn). In contrast, our bound has order (11/n) and tightens the aspeced-squared gradient norm by the variance of gradients. The PAC-Bayes bound in Mou et al. (2018) is the only SGLD bound, besides ours, which incorporates an explicit time-decaying factor. However, their decay factor is incomparable with ours since they are established through distinct proof techniques and rely on different assumptions: their factor relies on an T-g regularization' whereas ours is focused on the DP-SGD algorithm. A follow-up work by Li al. (2019) combined the algorithmic stability approach with PAC-Bayesian theory and presented bound which achieves order O(1nn). However, their bound requires the scale of the learning rate to be upper bounded by the inverse Lipschitz constant of the loss function. In contrast, we do not need any assumptions on the learning rate.
bound can be potentially loose and may not
There are significant recent works that adopt the information-theoreti framework (Xu and Raginsky, 2017) for bounding the SGLD generalization gap. Among them, Pensia al. (2018) initially proposed a bound in Corollary 1 for analyzing a class of noisy iterative algorithms, including SGLD, and their bound was extended in Proposition 3 of Bu et al. (2020). However, the bounds in Recently, Negrea et al. (2019)
Pensia et al. (2018); Bu et al. (2020) are iestributtio-indepeedddd improved these bounds by replacing the Lipschitz constant with a gradient prediction residual, which is distribution-dependerr
To compare with the generalization bound in Negrea et al. (2019), we incorporate a decaying factor into our bound under additional assumptions. Furthermore, the numerical experiments (Section 5) suggest that our bound is more favourably correlated with the true generalization gap. Negrea al. (2019) provided another bound in their Theorem 3.1 which involves variance term but it suffers from a slower rate O(1/ Vz).
More broadly, there are several recent works considering algorithms closely related to SGLD. For example, Haghifam et al. (2020) investigated the Langevin dynamics algorithm (i.e., full batch SGLD), which was later extended by Rodríguez-Gálvee et al. (2020) SGLD, and observed time-decaying phenomenon in their experiments. Specifically, Haghifam et al. (2020) incorporated a quantity, namely the squared error probability of the hypothesis test, into their bound in Theorem 4.2 and this quantity decays with the number of iterations. This seems to suggest that earlier iterations have a larger impact on their generalization bound. In contrast, our decay factor and the counterpart in Mou et al. (2018) indicate that the impact of earlier iterations is reducing with the total number of iterations. A recent work by Neu et al. (2021) investigated the generalization properties of SGD and provided bound that also involves the variance of gradients. Note that the generalization bound in their Proposition suffers from weaker order (11/ / vn) when the analysis is applied to SGLD.
To summarize, our main contribution is to provide a generalization bound for SGLD that incorporates the variance of gradients for quantifying the "sharpness" of the loss landscape and has O(1/n) sample size dependence. Moreover, our bound holds under mild conditions and is applicable to a general setting in which the output from SGLD can be any function of the iterations. Under additional assumptions that are satisfied by DP-SGD, our bound includes an explicit time-decaying factor. Although each of the above contributions has been discussed in existing works, to the best of our knowledge, our bound is the first one that simultaneously combines all these aspects. Moreover, our proof techniques based on information-theore properties of Gaussian channels) may be of broader interest to the community studying generalization theory.
tools (e.g., strong data processing inequalities and
We note that Mou et al. (2018) also provided bound in Theorem 23 without requiring regularization but the rate of the decay factor is slower than our factor in this case.
3

---

2 Preliminaries
Consider the following (possibly non-convex) optimization problem:
min (w)) - [( 2)) = / f(w, z)dj((2),
wEW
where w W S Rd is the parameter (e.g., weights of a neural network) to optimize: p is the underlying data distribution that generates Z; and : W x Z + R is the loss function (e.g., 0-1 loss). Since μ unknown, ((w) cannot be computed directly. Hence, one can instead minimize the empirical risk using a dataset _ (Zz,' Zn) which contains n i.dd. points Z₁ ~ JC
min Ls(w) WEW
Σ E(w,24 2+). 12
Stochastic gradient Langevin dynamics. We consider the stochastic gradient Langevin dynamics (SGLD) algorithm (Gelfand and Mitter, 1991; Welling and Teh, 2011) 1) for solving this empirical risk optimization. The dataset S is first divided into m disjoint mini-batches:
S s= U Sj, ==1
where SSy1 = and Sj n Ss = 0 for j + k.
We initialize the parameter with a random point Wo E W and update using the following rule:
12
W. V ( +
N.
(1)
B.
where Ne is the learning rate; 3e the inverse temperature: N (0, Ia) is a random variable drawn independently from standard Gaussian distribution; Br [m]] is the mini-batch index?; i is surrogate loss (e.g., hinge loss); and
V Vw SB.) a Σ vwe((W.11,2))
(2)
ZESB,
The recursion in (1) runs for T' iterations and the final output is W = f(W,,.... Wr) which is function of the parameters across all iterations. For example, the output can be the parameter the last iteration W Wr, the one which achieves the smallest value of the loss function W = argminw, Lμ (W)). or average of the parameters (i.e., Polyak averaging) W = 1 E, W,.
Information- generalization bounds. The goal of this paper is to derive an upper bound for the expected generalization gap:
(w) Ls)).
(3)
recent work by Xu and Raginsky (2017) provided a new method for bounding the expected generalization gap in terms of the mutual information between the input dataset and the output parameter W. The bound in Xu and Raginsky (2017) was later tightened by Bu et al. (2020).
Lemma (Bu et al. (2020) Proposition 1). Let the loss function f(w, 7.) be Suub-aussiin under μ for all e W. For any learning algorithm which takes dataset S (Zi, ... ZZn) input and outputs W,
EE (W) (s()] <
(4)
where I(W;Z) Z.) is the mutual information between the learning algorithmn' 's output W and an individ- ual data point Zi
For the sake of illustration, assume that the mini-batch indices specified before the SGLD

---

Strong data processing inequalities. In order to characterize the time-decaying phenomenon, we use an
tool: strong data processing inequalities (Dobrushin, 1956; Cohen et al., 1998). The data processing inequality (Cover and Thomas, 2012) states that if a Markov chain U - holds, then T(U; Y) S X). In other words, no post-processing of can increase the information about U. Under certain conditions, the data processing inequality can be sharpened, which leads to a strong data processing inequality, often cast terms of a contraction coefficient. Next, we recall the contraction coefficients of f-divergences and show their connection with strong data processing inequalities.
Let f: : (0, oc) + IR be convex function with f(1) = 0 and P. Q be two probability distributions over a set X' C IRd. The f-divergence (Csiszár, 1967) between P and Q is defined as
(y(1)) & f
dP aQ
dQ.
(5)
Examples of f-divergence include KL-divergence (f(t) = tt log t) and total variation distance (f(1) || - 11/2). For given transition probability kernel Prix X + Y, let Pyxx P be the distribution on )/ induced by the push-forward of the distribution P (i.e., the distribution of when the distribution of X is P). The contraction coefficient of Pyix for Dy is defined
DP o P Q) Dy(PIQ)
75 (Y(x)
sup P.Q:P&Q
E [0.
In particular, when the total variation distance is used, the corresponding contraction coefficient Thv Pr(x) is known as the Dobrushin's s coefficient (Dobrushin, 1956), which upper bounds all other contraction coefficients (Cohen et al., 1998): ny Pvix) S 7/v (Pyx). Furthermore, for any Markov chain U - X + Y, the contraction coefficient of KL-divergence satisfies (Ahlswede and Gáes, 1976)
I(U:Y) S TkL Thk (Prix) I(U;X).
(6)
When 7ka (Pyx)) < 1, the strict inequality T(U: Y) T(U:X) improves the data processing inequality and, hence, is referred to as a strong data processing inequality. We refer the reader to Polyanskiy and Wu (2016) and Raginsky (2016) for more comprehensive review on strong data processing inequalities and Calmon et al. (2017) for non-linear strong data processing inequalities in Gaussian channels.
Gaussian channels. We describe next a few fundamental properties of Gaussian channels. They will be used to derive a closed-form expression of the decay factor and to upper bound the mutual information by quantity that can be estimated from data.
Consider pair of random variables (X, Y) related by Y = X mNN where X lying on X:; m 0 is a constant; and N ~ (0, Ia) follows standard Gaussian distribution. This model can be regarded as single use of a Gaussian channel, which has long history in information theory and possesses many interesting properties. For example, if X' is a compact set, the contraction coefficients have non-trivial upper bound
diam(X))
(Py S 1/ (Pyj)) = 1 2Φ
(7)
2m
where di' A sup,, x x'112 is the diameter of X and (t) 2 S. <
1 exp( xxp /2)de
is the Gaussian complementary cumulative distribution function (CCDF). Another useful property is the following inequality (see Lemma 3.4.2 in Raginsky and Sason, 2012, for proof) which upper bounds the KL-divergence of the output distributions from the Gaussian channel by the Wasserstein distance of their input distributions. It also serves fundamental lemma for proving Villanilann's HWI inequality (Oto and Villani, 2000) in the Gaussian case.
Lemma 2. Let X and X' be a pair of random variables which are independent of (0),
Then for any m
1 W3(Px,
DRu (px(PxmmNl) (aettPtmllPPxtmaa -
(8)
2m
5

---

Here W2(Px,Px is the 2- Wasserstein distance equipped with the L2 cost function:
(2 Px) A inl [||X -
where the infimum is taken over all couplings joint distributions) of the random variables X and X' with marginals Px and Px. respectively.
We recall an analogous result (Guo al., 2005) which is also used in proof. It gives upper bound for the input-output mutual information a Gaussian channel.
Lemma 3. Let X be random variable which is independent of N ~ N(0, Ia). Then for any m > 0
I(X mN:X) - 2m2
Var (X).
3 Generalization Bounds for SGLD
Although Lemma provides a generalization bound for any learning algorithm, estimating the mutual information from data is often difficult. In this section, we further upper bound the mutual information for the SGLD algorithm by using properties Gaussian channels, discussed in the last section. This effort leads to generalization bound (Theorem 1) which can be estimated from the training set. We observe our experiments (Section 5) that Theorem captures some generalization phenomena of DNNs, such as label corruption, and is highly correlated with the true generalization gap. We end this section by comparing our bound with existing SGLD generalization bounds (Corollary 1) and extending our analysis to a high-probal probability bound (Proposition 1).
Before diving into the analysis, first discuss the main assumption made in this paper. Assumption 1. The loss function f(w, Z) is Saub-Gausiian under Z ~ for all w W.
We impose this assumption in order to apply Lemma 1. In particular, the loss function is bounded between two constants and b, this assumption is naturally satisfied with sub-Gaussian constant
σ = (b- 22/
Now we present the main result in this section- generalization bound for the SGLD algorithm. Its proof relies on the chain rule mutual information and properties Gaussian channels (Lemma 3). As a reminder, the output from SGLD is allowed to be any function of the iterates (i.e., W f(W1. Wr)).
Theorem 1. Under Assumption 1, the expected generalization gap of the SGLD algorithm has the following upper bound:
2bb
E [W, - [W)) <
Σ
3em - Var (Vrne(We-1,,.)
(10)
2n
j=1
LET,
where the set Ty contains the indices of iterations in which the mini-batch Sy is used and
Var (v=e(WW-1,s,)) A E [ (i S3) -ell3]
with the vector e A V (
Remark 1. Our proof techniques can be extended to analyze a broad class of noisy iterative al- gorithms besides SGLD. For example, if the probability distribution of the additive noise N is log-Lipschitz (i.e., the logarithmic probability density function (pdf) is Lipschitz) considered in Li al. (2019), one can derive an analogous generalization bound by adapting our proof. contrast, some generalization bounds (e.g., Mou al., 2018) seem to heavily rely on the Gaussian noise.
The variance of gradients in (10) measures particular kind of "sharpness" of the loss landscape. A recent work (Section 4.4 in Jiang et al., 2019) has observed empirically that this quantity is predictive of and highly correlated with the true generalization gap. Here we evidence this connection from theoretical viewpoint by incorporating the gradient variance into the generalization bound.
Many existing SGLD generalization bounds (e.g., Mou et al., 2018; Li et al., 2019; Pensia et al., 2018; Negrea al., 2019) are expressed as sum errors associated with each training iteration. In order to compare with these results, we present an analogous bound in the following corollary. This bound is obtained by combining a key lemma for proving Theorem with Minkowski inequality and Jensen's 's inequality so it is often much weaker than Theorem 1.

---

Corollary 1. Under Assumption 1, the expected generalization gap (3) of the SGLD algorithm can be upper bounded by
220
min
T Σ
Ben:
Var (vu)((W-1,,
Σ 1=1
B.n Var (Vue(WW.:: j
2
bn
where Z) is any data point used in the t-th iteration.
Our bound is distribution-dependent through the variance of gradients in contrast with Corollary of Pensia et al. (2018), Proposition 3 of Bu et al. (2020), and Theorem 1 of Mou et al. (2018), which rely on the Lipschitz constant: w. [ phenomena of DNNs, such as label corruption (Zhang et al., 2016), because the Lipschitz constant and data points In other words, this
z) 2)12 These bounds fail explain some generalization
takes supremum over all possible weight matrices Lipschitz constant only relies on the architecture of the network instead of the weight matrices or data distribution. Hence, it is the same for network trained from corrupted data and network trained from true data. We remark that the Lipschitz constant used by Pensia et al. (2018); Bu et al. (2020); Mou al. (2018) is different from the Lipschitz constant of the function corresponding to network w.r.t. the input variable. The latter one has been used in the literature (see e.g., Bartlett et al., 2017) for deriving generalization bounds and, some degree, can capture generalization phenomena, such as label corruption.
The order of our generalization bound in Corollary 1 is min ( ET V BB V
1 bn E
Th It.It is
tighter than Theorem of Mou et al. (2018) whose order is "E" 1)-- Our bound is applicable regardless of the choice of learning rate while the bound in Li et al. (2019) requires the scale of the learning rate be upper bounded by the reciprocal of the Lipschitz constant. Our Corollary I has the same order with Negrea et al. (2019) but we incorporate an additional decay factor under additional assumptions (see Theorem 2) and numerical experiments suggest that bound is more favourably correlated with the true generalization gap (see Table 1).
Theorem provides upper bound for the expected generalization gap of the SGLD algorithm. In practice, a bound holding with high probability is also worth investigating since the SGLD algorithm may be run only once using the training set. Next, we leverage the monitor technique (Bassily et al., 2016; Xu and Raginsky, 2017) and derive a concentration inequality for the generalization gap of SGLD.
Proposition 1. Under Assumption 1, with probability at least - 8 over the randomness of (S, W), the generalization gap of the SGLD algorithm has the following upper bound:
2ho
Sen
Var (Voo(W..-I,,)) + log 2 8
(w) Ls())
LET
Amplifying Generalization by Iteration for DP-SGD
In the last section, derived generalization bound for the SGLD algorithm and allowed the algorithmic output to be any function of all iterates. Here we consider a closely related algorithm- DP-SGD-and prove that the generalization bound can be sharpened by incorporating a time-decaying factor if the algorithmic output is the last iterate.
We start by recalling an implementation of the (projected) DP-SGD algorithm (see e.g., Algorithm 1 in Feldman et al., 2018). The parameter of the empirical risk is updated using the following rule:
W, = Projw (W,-1 - (g( WW Zz) + N)),
(11)
where N (O, I2) and function g indicates a direction for updating the parameter. The parameter is projected (w) 2 argmin ||w - w||2 onto the domain W at each iteration. We assume
sup WE
(l 2 2)1|2 < K.
(12)
7

---

This assumption is crucial for guaranteeing differential privacy as it controls the sensitivity of each update. It satisfied if g is the gradient of Lipschitz continuous function the clipped gradient of generic loss function.
The recursion in (11) replacement). The final output from the DP-SGD algorithm is the last iterate Wr. Again, our goal is derive an upper bound for the expected generalization gap:
for T iterations and assume that 7 (i.e., data drawn without
E 1 (Wr) (W())
(13)
Recall that Lemma provides generalization bound in terms of the mutual information I(Wr; Zd) Intuitively speaking, if a data point Ze used at an early iteration, I(Wr; should be small due to the cumulative effect of the noise added in the iterations afterward. We characterize this intuition rigorously in the following lemma, which is established by strong data processing inequalities. Lemma 4. For the DP-SGD algorithm, we have
I(Wr; Z.) & I(We: Z+) T-
(14)
Here we define
+ 2n
- 1- 1-20 24h
E (0,
(15)
2m
where (--) the Gaussian CCDF and the constant D is the diameter of the parameter domain W.
Lemma 4 explains why our generalization bound Theorem 2 incorporates a time-decaying factor. In particular, it implies that I(Wr; Z4) - 0 T because the output from DP-SGD W while all the intermediate steps are not released. To further illustrate this point, let imagine the opposite extreme scenario in which the DP-SGD algorithm outputs the parameters across all iterations: Wi, Wr. The data processing inequality yields that for the data point Z, used at the (-th iteration,
This time-decaying phenomenon occurs
T(W1, Wr; Zx) T(W,;
Hence, it is impossible to have I( Wr: Z.) +
oc unless [(W;; Z,) 0.
Since the underlying data distribution is unknown, so is the mutual information Z() in (14),
which poses problem for computing the generalization bound. In order to obtain computable bound like Theorem 1, we further upper bound the mutual information by employing properties of Gaussian channels (Lemma 2).
Lemma 5. For the DP-SGD algorithm, we have
T(W;77) < 2 Var (I(W,-1,7)) where the variance is over the randomness of (W.-1,Z) Z) ~ Pw... @ μ.
(16)
With Lemma 4, 5,5 in hand, we present the main result of this section generalization bound for the DP-SGD algorithm.
Theorem 2. Under Assumption 1, the expected generalization gap of the DP-SGD algorithun has the following upper bound:
T
20
E [L, (s S
Var (g (W.-1,Z) ---1,
(17)
where q is defined in (15).
Remark 2. To qualitatively analyze the role of the decay factor, we demonstrate that as - oc, the generalization bound in Theorem converges to O, whereas the counterpart without decay factor
may tend to a large constant. Under assumption (12), we can further upper bound the variance term by K²2 In this case, our bound in Theorem 2 becomes
T
C C1-9 T/2
n
n /
where the constant C A 2o
0. By choosing n and letting them go to infinity, the above bound converges to 0 but the counterpart without the decay factor can only tend to the constant C.

---

120
0.080
Generalization gap
0.086
110
bound
100
0.075
0.070
90
0.065
30
70
0.055
256
Width
Comparison between the generalization gap and our generalization bound in Theorem 1. We use the SGLD algorithm to train 3-layer neural networks with varying widths on MNIST. As shown, both the generalization gap and our bound are decreasing w.r.t. the network width.
Figure 2:
Numerical Experiments
In this section, we demonstrate our generalization bound in Theorem I through numerical experiments on the MNIST dataset. First, we validate the ability of our generalization bound in capturing generalization phenomena of DNNs observed by empirical studies (see e.g.. Zhang et al., 2016) 6). Second, we examine the correlation between our generalization bound and the true generalization gap using the three evaluation criteria suggested by Jiang et al. (2019), and compare it with the benchmarks. We reproduce our experiments on the CIFAR-10 dataset (Krizhevsky al., 2009) the supplementary material.
Corrupted label. As observed in Zhang et al. (2016), DNNs have the potential to memorize the entire training dataset when large portion of the labels corrupted. For networks with identical architecture, those trained using true labels have better generalization capability than those ones trained using corrupted labels, although both of them achieve perfect training accuracy.
In our experiment, we randomly select 5000 samples as our training dataset and change the label of 40%, 25%. 50%, 75%} training samples. Then network under different corruption levels. The training process continues until the training accuracy is 1.0 (see Figure I Left). We compare our generalization bound with the generalization gap in Figure 1 Middle and Right. As shown, despite being vacuous, our bound is highly correlated with the true gap. When the corruption level is increasing, both bound and the generalization gap are increasing and the curve of our bound has very similar shape to the generalization gap. Finally, we observe that the generalization gap tends be stable since the algorithm converges (Figure Middle). Our generalization bound captures this phenomenon (Figure 1 Right) as the variance of gradients becomes negligible when the algorithm starts converging. The intuition is that the variance of gradients reflects the sharpness of the loss landscape and as the algorithm converges, the loss landscape becomes flatter.
the SGLD algorithm to train 3-layer
Network width. As observed by several recent studies (see e.g., Neyshabur et al., 2014; Jiang et al., 2019), wider networks lead to smaller generalization gap. This may seem contradictory to the traditional wisdom as one may expect that class of wider networks has a higher VC-dimension and, hence, would exhibit a higher generalize gap. In experiments, neural networks with different widths. The training process runs for 400 epochs until the training accuracy is 1.0. We compare our generalization bound with the generalization gap in Figure 2. As shown, both the generalization gap and our bound are decreasing with respect to the network width.
use the SGLD algorithm to train
Comparison with benchmarks. To evaluate our bound, we adopt the three criteria proposed in Jiang et al. (2019): (i) Kendall's cank-correlation coefficient (7) (Kendall, 1938). (ii) Granulated Kendall's coefficient (V), and (iii) conditional independent test via mutual information (MI) (Verma and Pearl, 1991). In our experiments, we select 3 commonly used hyper-parameters (i.e., learning rate (Ir), width, depth), which are believed to influence the generalization gap, and let each hyper- parameter choose three different values. We train 27 neural networks under all combinations of

---

dataset
method
1r
width
depth
y
MI
(THEOREM I)
1.00
0.75
0.34
MNIST
NEGREA (2019)
0.26
0.26
0.48
0.25
0.33
0.12
Table 1: We adopt the three evaluation criteria proposed in Jiang et al. (2019) for comparing generalization bound with the benchmark method (Theorem 3.1 of Negrea et al., 2019); (i) Kendall's 's rank-correlation cocfficient (r), (ii) Granulated Kendall's cocfficient (V),, and (iii) conditional independent test (MI), All scores, except MI, are within [-1, 1J and the score of MI is normalized to [0, 1]. We also report the correlations when a single hyper-parameter (e.g., learning rate (Ir)) is varying.
and assess the correlations between the generalization bound and the generalization
gap.
We compare our generalization bound with the sandient-rredcctoon-tt Negrea et al. (2019) under the above three evaluation criteria. As shown in Table 1, our generalization bound is highly correlated with the true generalization gap and outperforms benchmark under all the criteria suggested in Jiang et al. (2019).
bound in Theorem 3.1 of
6
Summary
We provide new generalization bounds for the SGLD algorithm. Our hope is that these bounds can help explain some empirical observations (e.g., why wer-parameterized DNNs often generalize well in practice) and inspire new regularization methods. The proof techniques in this paper rely on information-theorete tools (e-g., strong data processing inequalities and properties of Gaussian channels). We believe that these tools can find a wider applicability within the community studying generalization theory. Our approach tighten our time-decaying factor in Theorem 2 by letting it be distributtion-deendeen Moreover, the proof blueprint outlined here can be applied analyze broader family of noisy iterative algorithms that rely on additive noise. There are several open questions that deserve further investigation. For example, we prove that our generalization bound can be tightened if the output of the algorithm the last iterate. Our analysis is inspired by line of works on privacy amplification by iteration (Feldman al.. 2018; Balle et al., 2019; Asoodeh al., 2020). On the other hand, there are other ways to amplify privacy, such as subsampling (Chaudhuri and Mishra, 2006) and shuffing (Erlingsson et al., 2019). It would be interesting understand the algorithmic generalization capability can be improved by these methods.
be extended in several directions. For example, one could
10

---

Acknowledgments and Disclosure of Funding
The work of H. Wang and F. P. Calmon supported in part by the National Science Foundation under grants CAREER 1845852, IIS 1926925, and FAI 2040880 and F. P. Calmon also acknowledges gift from Google Faculty Research Award and an Amazon Research Award.
References
Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L. (2016). Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference computer and communications security, pages -08-318.
Ahlswede, R. and Gács, P. (1976). Spreading of sets in product spaces and hypercontraction of the Markov operator. The annals of probubility, pages 925-939.
Asoodeh, S., Diaz, M., and Calmon, F. P. (2020). Privacy analysis of online learning algorithms via contraction coefficients. In International Symposium on Information Theory.
Balle, B., Barthe, G., Gaboardi, M., and Geumlek, J. (2019). Privacy amplification by mixing and diffusion mechanisms. Advances in neural information processing systems.
Bartlett, P. L., Foster, D. J., and Telgarsky. M. J. (2017). Specttaaly-nnoraaiized margin bounds for neural networks. Advances in Neural Information Processing Systems, pages 6240-6249.
Bassily, R., Nissim, K., Smith, A., Steinke, T., Stemmer, U., and Ullman, J. (2016). Algorithmic stability for adaptive data analysis. In Proceedings of the forty-eighth annual ACM symposium Theory of Computing, pages 1056-1059.
Bu, Y., Zou, S., and Veeravalli, V. V. (2020). Tightening mutual information based bounds generalization error. IEEE Journal on Selected Areas in Information Theory.
Calmon, F. P., Polyanskiy, Y., and Wu, Y. (2017). Strong data processing inequalities for input constrained additive noise channels. IEEE Transactions on Information Theory, 1873)1887--1892
Chaudhuri, K. and Mishra, N. (2006). When random sampling preserves privacy. In Annual International Cryptology Conference, pages 193-213. Springer.
Cohen, J. F.,, Kempermann, J., and Zbaganu, G. (1998). Comparisons of stochastic matrices with applications in information theory, statistics, economics and population. Springer Science & Business Media.
Cover, T. M. and Thomas, J. A. (2012). Elements of information theory. John Wiley & Sons.
Csiszár, I. (1967). Information-type measures of difference of probability distributions and indirect observation. studia scientiarum Mathematicarum Hungarica, 2:229-31 -18.
Dobrushin, L. (1956). Central limit theorem for nonstationary Markov chains. Theory of Probability & Its Applications, 1(1):65-80.
Dwork, C., McSherry, F., Nissim, K., and Smith, (2006). Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer.
Erlingsson, Ú. Feldman, V., Mironov, I., Raghunathan, A., Talwar, K., and Thakurta, A. (2019). Amplification by shuffling: From local to central differential privacy via anonymity. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2479.. SIAM.
Facebook AI (2020). Introducing Opacus: A high-speed library for training Py Torch models with differential privacy.
Feldman, V., Mironov, I., Talwar, K., and Thakurta, A. (2018), Privacy amplification by iteration. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 521-532. IEEE.

---

Gelfand, S. B. and Mitter, S. K. (1991). Recursive stochastic algorithms for global optimization in R SIAM Journal on Control and Optimization, 29(5):99--0018
Guo, D., Shamai, S., and Verdú, S. (2005). Mutual information and minimum mean -quare error in Gaussian channels. IEEE Transactions on Information Theory, 5144):221-128)
Haghifam, M., Negrea, J., Khisti, A., Roy, D. M., and Dziugaite, G. K. (2020). Sharpened gener- alization bounds based on conditional mutual information and an application to noisy, iterative algorithms. arXiv preprint ar0iv:2004. /2983.
Hardt, M., Recht, B., and Singer, Y. (2016). Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pages 1225-1234.
Jiang. Y., Neyshabur, B., Mobahi, H., Krishnan, D., and Bengio, S. (2019). Fantastic generalization measures and where to find them. arXiv preprint
Jin, C., Netrapalli, P., Ge, R., Kakade, S. M., and Jordan, M. I. (2019). On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points. arXiv preprint arXiv: 04811.
Kendall, M. G. (1938). A new measure of rank correlation. Biometrika, 30(1/2):81-93
Keskar, N. S., Mudigere, D., Nocedal, J., Smelyanskiy, M., and Tang, P. T. P. (2016). On large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv: 044866.
Krizhevsky, A., Hinton, G., et al. (2009). Learning multiple layers of features from tiny images.
Li, J. Luo, X., and Qiao, M. (2019). On generalization enror bounds of noisy gradient methods for non-convex learning. arXiv preprini
Mou, W., Wang, L.., Zhai, X., and Zheng, K. (2018). Generalization bounds of SGLD for non-convex learning: Two theoretical viewpoints. In Conference on Learning Theory, pages 605-638.
Neelakantan, A., Vilnis, L., Le, Q. V., Sutskever, I., Kaiser, L., Kurach, K., and Martens, (2015). Adding gradient noise improves learning for very deep networks. arXiv preprint
Negrea, J., Haghifam, M., Dziugaite, G. K., Khisti, A., and Roy, D. M. (2019). cormmation-theoretii generalization bounds for SGLD via data-dependent estimates. Advances in Neural Information Processing Systems, pages 11015-1 1-155
Neu, G., Dziugaite, G. K., Haghifam, M., and Roy, D. M. (2021). Information- generalization bounds for stochastic gradient descent. arXiv preprint arXiv:2102.00931
Neyshabur, B., Bhojanapalli, S., McAllester, D., and Srebro, N. (2017). Exploring generalization in deep learning. In Advances in neural information processing systems, pages 5947-5956.
Neyshabur, B.. Tomioka, R., and Srebro, N. (2014). In search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint arXiv:1411 1412.6614.
Otto, F. and Villani, C. (2000). Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality. Journal of Functional Analysis, 173(2):361-400,
Pensia, A., Jog, V., and Loh, P.-L. (2018). Generalization error bounds for noisy, iterative algorithms.
In 2018 IEEE International Symposium on Information Theory (ISIT), pages 546-550. IEEE.
Polyanskiy, Y. and Wu, Y. (2016). Dissipation of information in channels with input constraints. IEEE Transactions Information Theory, 62(1):35-55,
Radebaugh, C. and Erlingsson, U. (2019). Introducing TensorFlow privacy: Learning with differential privacy for training data.
Raginsky, M. (2016). Strong data processing inequalities and @-Sooolev inequalities for discrete channels. IEEE Transactions Information Theory, 63565333553338.
Raginsky, M., Rakhlin, A., and Telgarsky, M. (2017). Non-convex learning via stochastic gradient Langevin dynamics: a nonasymptotic analysis. In Conference on Learning Theory, pages 1674- 1703.
12

---

Raginsky, M. and Sason, I. (2012). Concentration of measure inequalities in information theory, communications and coding. arXiv preprint arXi::1212.4663.
Rodríguez-Gällez, B., Bassi, G., Thobaben, R., and Skoglund, M. (2020). On random subset generalization emror bounds and the stochastic gradient Langevin dynamics algorithm. arXiv preprint arXiv:2010.1090)
Russo, D. and Zou, J. (2016). Controlling bias in adaptive data analysis using information theory. In Artificial Intelligence and Statistics, pages 1232-1222 PMLR.
Song, S., Chaudhuri, K., and Sarwate, A. D. (2013). Stochastic gradient descent with differentially private updates. In 2013 IEEE Global Conference on Signal and Information Processing, pages 245-248. IEEE.
Valiant, G. (1984). theory of the learnable. Communications of the ACM, 134-111111412
Vapnik, and Chervonenkis,
(1971). On the uniform convergence relative frequencies of events to their probabilities. Measures of Complexity, 16(2):11.
Verma, T. and Pearl, J. (1991). Equivalence and synthesis of causal models. UCLA, Computer Science Department.
Welling, M. and Teh, Y. W. (2011). Bayesian learning via stochastic gradient Langevin dynamics. In Proceedings of the 28th international conference on machine learning (ICML), pages 681-688.
Xu, A. and Raginsky, M. (2017). ieformation-thhorettii analysis of generalization capability of learning algorithms. In Adv. Neural Inf. Process. Syst., pages 2524-2533.
Zhang, C., Bengio. S., Hardt, M., Recht, B., and Vinyals, O. (2016). Understanding deep learning requires rethinking generalization. arXiv preprint arXiv: 161 1,03530.
Zhang, Y., Liang, P., and Charikar, M. (2017). hitting time analysis of stochastic gradient Langevin dynamics. In Conference Learning Theory, pages 1980-2022
13


Reviews:
[{"review_id": "mpFIG0ms2oG", "reviewer": "Reviewer_QtYi", "summary": "This paper derives upper bounds on the generalization error of SGLD and DP-SGD using an information theoretic analysis. Compared to past work on this problem the authors derive upper bounds that depend on the sum of variance of the gradients along the path, converge at a rate of 1/n, and discount the effect of samples seen early in the training run. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "As mentioned by the authors, previous papers have used information theoretic tools to obtain generalization bounds that have one or more of the following properties: a) upper bounds that depend on the sum of variance of the gradients along the path or on the expected norm of the gradients, b) converge at a rate of 1/n, and c) discount the effect of samples seen early in the training run; but none of the previous bounds have satisfy all of the properties simultaneously. The authors derive such a bound, and the main technical driving force for their analysis seems to be the use of strong data processing inequalities. While I appreciate this advance, it does seem like a narrow, technical step forward to me in light of the past work on this area, including the paper of Xu and Raginsky, who also previously suggested using strong data processing inequalities to get tighter bounds. Other comments and questions about the paper are listed below:\n\n1. The abstract suggest that SGLD is a widely used optimizer, but the authors do not provide any citations to support this claim. The authors should back up this claim with citations in the text. \n2. Do the bounds of Li et al. (2019) discussed in ln 94 also depend on the sum of the variance of the gradients or on the expected norms of the gradients?\n3. Ln. 219 says that DP-SGD is a special instance of SGLD algorithm. I am not sure why this is the case, since the gradients are clipped in the DP-SGD algorithm (see Algorithm 1, Abadi et al. (2016)). How does the theory handle this clipping? Relatedly, do Theorems 1 and 2, and Corollary 1 apply to the DP-SGD algorithm? The authors should clarify this.\n4. In ln. 246, if I understand correctly, the sharpness studied Jiang et al. 2019 refers to the robustness of the network's output when the weights are perturbed slightly. Why does the variance of the gradient relate to the sharpness studied there?\n5. Do the authors expect a sharper version of Theorem 2 to hold if the average iterate is returned instead of an arbitrary function of the weights.\n6. Regarding the experiments, in Table 1, I am not quite sure why the authors only compare their generalization bounds to that of Negrea et al. The authors say that the previous papers Mou et al., Pensia et al. ,... did not perform a empirical study, but Table 1 only compares the correlation between the actual generalization performance of a network and the theoretical bound. I believe the authors should add these comparisons to their empirical study. \n\n\n\n============== Post author rebuttal =============\nThank you for carefully answering my questions. I have raised my score as a result.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not think there is any potential negative societal impact of this work. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "XUmIA7Oosyx", "reviewer": "Reviewer_42Mp", "summary": " The authors study the generalization properties of stochastic gradient Langevin dynamics (SGLD),  using\nresults about Gaussian channels from info theory. \n\nThe paper derives a generalization bound that involves the variance of the mini batch gradients in various steps. The variance terms are multiplied by a decaying factor (Thm 1) when one is interested in generalization bound for the last iterate, and the factor is (not surprisingly) absent when the function under consideration depends on all the iterates (Thm 2). The results are established by building on the recent results relating generalization bounds for sub-Gaussian loss functions in terms of the mutual information between the parameter iterates and samples used at various iterations (Bu et al. 2020 result), and upper bounding the mutual information in terms of the variance of gradient of the loss function, and the SGLD step size eta, and temperature beta (Lemma 5). The results scale as 1/n with sample size n---which is better than some of the previous results that try to remove the Lip constant dependence. \n\nThe authors present some numerical experiments that demonstrate that their generalization bounds correlate well with generalization gaps observed with small versions of MNIST and CIFAR 10 datasets (5k training examples): (a) with the amount of corrupted labels---increasing corruption increases the generalization error, (b) the width of the network---increasing width decreases the generalization. Their bounds (Table 1) correlate with generalization bounds better compared with Negrea et al. 2019 results, when one considers various settings across learning rate, width, and depth hyper-parameters.\n\nThe paper is very well written and fairly easy to follow---a feature missing in several submissions in recent times. It summarizes some useful results in a reader-friendly way.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nI have four major concerns with the current version of the work:\n\n1. The authors say that prior works often characterize the generalization bounds in terms of the Lipschitz constants, and argue that '''such bounds can be potentially loose since the Lipschitz constants may be large and fails to explain some empirical observations (e.g., a network trained using true labels generalizes better than a network trained using corrupted labels as shown in Figure 1)'''--- I find this argument incomplete, especially because prior work by Foster et al. https://arxiv.org/pdf/1706.08498.pdf  (that this work does not cite) try to study phenomenon identical to Figure 1 and they show that Lipschitz based bounds can explain this phenomenon to a certain degree; the constants are large when there are fake labels. In fact, one of the key pieces of numerical evidence for the usefulness of the results in this draft is the same as the evidence in this earlier work---the generalization bounds ``correlate\" with the generalization gaps observed in datasets with correct and fake labels. I would like to see a discussion to this end.\n\n\n2. The authors state '''In contrast, we do not need any assumptions on the learning rate.''' This aspect while on the face seems true, it is unclear to me how the variance bounds in Thm 1 and 2 evolve over time for arbitrary step sizes. Do we not need some condition on eta for the variances to remain stable over time? For large eta, I can see that the q will degenerate to 1, and that we have a factor of sqrt(eta) in Thm 1, but the variance terms will begin to blow up as we increase eta. This leads to a slightly more important question: Some discussion is warranted on what condition on eta and beta is sufficient to ensure that the bounds in Thm 1 and Thm 2 are not vacuous, or increasing with time.\n\n3. While it is heartening to see the bounds having some nice correlations, none of the experiments (I checked the appendix) involved a large sample dataset (the usual 50k for MNIST and CIFAR 10)---is there a reason for that? Also, the authors should add details about the variance of gradients were estimated?\n\n4. The authors discuss related work earlier in the work, but ignore it completely after stating their bounds more formally---a revisit to the key results from prior works and putting their bounds in Thm 1 and Thm 2 would allow me to better appreciate their results in context. Also, see the minor question below.\n\nMinor question (optional)\n\n1. Are there settings under which Lemma 5 is tight? For instance, does the bound in Thm 1 provide a strict improvement over Lemma 3 https://arxiv.org/pdf/1901.04609.pdf for large T?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have not included a discussion on this.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "TLicLTjG-5P", "reviewer": "Reviewer_kujL", "summary": "This paper presents some new results on bounding the generalization error of the SGLD algorithm using the properties of Gaussian channels. For SGLD without sample replacement, strong data processing inequality for Gaussian channel is used to show a time-wise contraction of the upper bound. For the general SGLD with sample replacement, a result that relates the mutual information of Gaussian channel to the input variance is used to obtain a more general upper bound.\nExperiments are also performed to show some interesting correlations between the obtained upper bounds and the true generalization error.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "While the results presented in the paper look to be new and the experimental results look interesting, there are some aspects that could be improved.\n1. The term \"DP SGD\" is mentioned several times in the paper without an explicit statement. It looks to be referring to SGD without sample replacement, but it would be better if this can be explicitly stated.\n2. For Theorem 1, obtaining a time-decaying (contraction) is good, but there is no further discussion on this factor, e.g. how does the final bound scale as T increases. Even some qualitative discussion on this factor would be useful to assess its significance. \n3. For Theorem 2, it is claimed that the final bound scales in n as O(1/n). However, the actual dependence of the bound on n may not be that simple, because here n = m*b, which means that as n increases, both m and b would increase. It is thus not clear whether the O(1/n) can be maintained as n increases. Also, at least some qualitative discussion on the dependence on n and T would be helpful.\n4. For the experimental results, many details are missing. For example, how are the variance terms in the bound (Theorem 2) evaluated?\nHow are the bounds scaled to match the empirical generalization error? \nHow is the correlation between the bound the empirical generalization defined?\nIt can also be seen that the empirical generalization error in all cases saturates as T increases. Is this predicted by the bound? This is another reason why more discussions on the bounds themselves should be provided. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The major limitations are the lack of discussions on the obtained bounds and missing details of the experimental results. But I think the paper can be easily improved by addressing these limitations.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "LfvOtUOpHMZ", "reviewer": "Reviewer_HZ1y", "summary": "This paper gives a generalization bound for the stochastic gradient Langevin dynamics (SGLD) algorithm using tools from information theory (notably, the SDPI for Gaussian channels and the HWI inequality). The bound is subsequently used to analyze generalization of differentially private SGD (DP-SGD). Supporting experiments on the CIFAR-10 dataset show that the bound is more favorably correlated with the generalization error than prior work by Negrea et al. (2019).\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "*** Post-rebuttal ***\n\nI am increasing my score to 6 based on the authors' response.\n\n***\n\nGeneralization bounds for SGLD have recently attracted a lot of attention in the NeurIPS community and the contribution is timely. \n\nOriginality:\n\n-- The analysis primarily builds on the works of Xu and Raginsky (2017), and Pensia et al. (2018) that bound the expected generalization error in terms of the mutual information (MI) between the input training data and the output hypothesis under a sub-Gaussian loss. Since the date generating distribution is unknown, estimating the mutual information is intractable. This issue is addressed by upper-bounding the MI. The bounds thus obtained (for DP-SGD) are expressed as a sum of errors associated with each training iteration and features the variance of the gradients (from upper bounding the MI + chain rule of MI) and a time-decaying factor (by way of Gaussian SDPI) that weighs the contributions from early iterations of SGLD. The intuition for the time-decaying factor is natural as it factors in the cumulative effect of noise. \n\n-- In terms of originality, application of the SDPI and HWI inequality for Gaussians appear novel.  \n\n\nIssues:\n\n-- It appears that there is a version of this work (arXiv:2102.02976v1, dated Feb 5th, 2021) with a different title ``\"Learning While Dissipating Information: Understanding the Generalization Capability of SGLD.\"  I will recommend that the authors cite this work. Also a question: Theorem 1 in the arXiv version apparently gives a bound for SGLD (sampling with replacement) that features the time-decay factor. I believe the corresponding bound in the present submission is Theorem 2, which does NOT feature the time-decay factor. If the latter is a correction of sorts for the one in the arXiv version, then this should be stated clearly with citation. \n\n-- I can understand that the DP-SGD is a special case of SGLD, but the motivation for selecting this specific algorithm is not very clear. Ideally, the general version of the algorithm (SGLD, Theorem 2) should be stated before stating a special case (DP-SGD, Theorem 1). However, the order is reversed here. I believe this was done to accentuate the role of the time-decay factor. In any case, the organization and overall presentation of the paper can be significantly improved.\n\n\nSuggestion (minor):\n\n-- The isotropic noise structure of SGLD is integral to the proof here and I am inclined to believe that the technique cannot be applied to SGD. Nonetheless, a discussion on if and how any of the proposed techniques can be used to analyze SGD might benefit the potential reader. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors claim that that is no direct negative societal impact of their work and I agree. \n", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "Three"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides new generalization guarantees for SGLD, which incorporate the gradient variance, giving a more adaptive flavor. The paper also considers differentially private stochastic optimization as an application of their results. 

We had quite a bit of discussion on this paper and we thank the authors for providing the reviewers with additional details, which helped to clear up some confusion. After deliberation, we agreed that the paper should be accepted. 

Please do carefully go over the reviews and discussion and incorporate any suggestions into the final manuscript.
Decision: Accept (Poster)