Generalization Bounds for Gradient Methods via Discrete and Continuous Prior
Authors: Xuanyuan Luo
Bei Luo
Jian Li
Venue: NeurIPS 2022 Accept (2022)
Keywords: theory
generalization
gradient descent
PAC-Baysian
Langevin Dynamics

Abstract: Proving algorithm-dependent generalization error bounds for gradient-type optimization methods has attracted significant attention recently in learning theory. However, most existing trajectory-based analyses require either restrictive assumptions on the learning rate (e.g., fast decreasing learning rate), or continuous injected noise (such as the Gaussian noise in Langevin dynamics). In this paper, we introduce a new discrete data-dependent prior to the PAC-Bayesian framework, and prove a high probability generalization bound of order $O(\frac{1}{n}\cdot \sum_{t=1}^T(\gamma_t/\varepsilon_t)^2\left\|{\mathrm{g}_t}\right\|^2)$  for Floored GD (i.e. a version of gradient descent with precision level $\varepsilon_t$), where $n$ is the number of training samples, $\gamma_t$ is the learning rate at step $t$, $\mathrm{g}_t$ is roughly the difference of the gradient computed using all samples and that using only prior samples. $\left\|{\mathrm{g}_t}\right\|$ is upper bounded by and and typical much smaller than the gradient norm $\left\|{\nabla f(W_t)}\right\|$. We remark that our bound holds for nonconvex and nonsmooth scenarios. Moreover, our theoretical results provide numerically favorable upper bounds of testing errors (e.g., $0.037$ on MNIST). Using similar technique, we can also obtain new generalization bounds for a certain variant of SGD. Furthermore, we study the generalization bounds for gradient Langevin Dynamics (GLD). Using the same framework with a carefully constructed continuous prior, we show a new high probability generalization bound of order $O(\frac{1}{n} + \frac{L^2}{n^2}\sum_{t=1}^T(\gamma_t/\sigma_t)^2)$ for GLD. The new $1/n^2$ rate is due to the concentration of the difference between the gradient of training samples and that of the prior.

Generalization Bounds for Gradient Methods via Discrete and Continuous Prior
Xuanyuan Luo IIIS, Tsinghua University xuanyuanluo@googgee.cc
Luo Bei Renmin University of China
rabbit_lberuc edu. en
Jian Li
IIIS, Tsinghua University
1 inji8@mmaill tsinghua. edu
Abstract
Proving algorithm-dependen generalization error bounds for gradient-type opti- mization methods has attracted significant attention recently in learning theory. However, most existing rajectory-basee analyses require either restrictive assump- tions the learning rate (e.g., fast decreasing learning rate), or continuous injected noise (such as the Gaussian noise in Langevin dynamics). In this paper, we intro- duce discrete data-dependent prior to the PAC-Bayesian framework, and prove high probability generalization bounds of order O El= (1t//)))))) llg: lI') for floored GD and SGD (i.e. finite precision versions of GD and SGD with preci- sion level ex) where, where n the number of training samples, 7t the learning rate at step l, g. is roughly the difference between the average gradient over all samples and that over only prior samples. |lg|| |I is upper bounded by (typically much smaller) than the gradient norm Vf(W))]l We remark that bounds hold for nonconvex and nonsmooth loss functions. Moreover, our theoretical results provide numerically favorable upper bounds of testing errors (0.026 MNIST and 0.198 on CIFARIO). Furthermore, we study the generalization bounds for gradient Langevin Dynamics (GLD). Using the same framework with carefully constructed continuous prior, we show a new high probability generalization bound of order 0 + 1.2 the concentration of the difference between the gradient of training samples and that of the prior.
/ Et=1 (1t/o)²)) for GLD. The new 1/n² rate is obtained using
Introduction
Bounding generalization error of learning algorithms is one of the most important problems in machine learning theory. Formally, for supervised learning problem, the generalization error is defined as the testing eтrоr (or population error) minus the training error (or empirical error). In particular, we denote Rww, (ar, y)) == (x) # y] as the error of a single data point (I, u), where hey (z) the output of model with parameter w E Rd. Suppose S the of training data, each i..d. sampled from the population distribution 2, and we use R(w, S) = [sT Exes R(w, 2) and denote the training error and the testing error, respectively. The
R(w, D) == Ez-nl [R( [)] generalization error of w is formally defined as erTgen (w) = R(w, D) R(w, S).
Proving tighter generalization bounds for general nonconvex lcarning and particularly deep learning has attracted significant attention recently. While the classical learning theory (uniform conver- gence theory) which bounds the generalization error by various complexity measures (e.g., the
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

VC-dimension and Rademacher complexity) of the hypothesis class has been successful in several classical convex learning models, however, they become vacuous and hence fail explain the success of modern nonconvex over- rer-ppaametrized neural networks (i.e., the number of parameters significantly exceeds the number of training data) (see e.g., Zhang et al. [2017], Nagarajan and Kolter [2019]). Recently, learning theorists have tried to understand and explain generalization of deep learning from several other perspectives, such as margin theory [Bartlett et al., 2017, Wei et al., 2019], algorithmic stability [Hardt et al., 2016, Mou et al., 2018, Li et al., 2020, Bousquet et al., 2020], PAC-bayeisan [London, 2017, Bartlett et al., 2017, Neyshabur et al., 2018, Zhou et al., 2019, Yang et al., 2019], neural tangent kemee [Jacot et al., 2018, Du al., 2019, Arora et al., 2019, Cao and Gu, 2019], information theory [Pensia et al., 2018, Negrea et al., 2019], model compression [Arora et al., 2018, Zhou et al., 2019], differential privacy [Oneto et al., 2017, Wu et al., 2021] and
In this paper, we aim to obtain tighter generalization error bounds that depend on both the training data and the optimization algorithms (a.k.a. gradient-type methods) for general nonconvex learning problems. In particular, we prove algorithn-dependen generalization bounds for several gradient- based optimization algorithms such as certain variants of gradient descent (GD), stochastic gradient descent (SGD) and stochastic gradient Langevin dynamics (SGLD). Our proofs are based on the classic Catoni's PAC-Bayesian framework [Catoni, 2007] and also have a flavor of algorithmic stability [Bouqquet and Elisseeff, 2002]. Several prior works have obtained generalization bounds for SGD and SGLD by analyzing trajectory through either the -ay-Bayesian or the algorithmic stability framework (or closely related information theoretic arguments). However, most existing results based on analyzing the optimization trajectories require either restrictive assumptions on the learning rates, or continuous noise (such as the Gaussian noise in Langevin dynamics) in order to bound the stability the KL-divergence. In this paper, we resolve the above restrictions by combining the PAC- PAC-Bayesian framework with a few simple (yet effective) ideas, so that we can obtain new high probability and non-vacuous generalization bounds for several gradient-based optimization methods with either discrete or continuous noises (in particular certain variants of GD and SGD, either being deterministic with discrete noise, which cannot be handled by existing techniques).
1.1
Prior work
We first briefly mention some recent work on bounding the generalization error of gradient-based methods. Hardt et al. [2016] first studied the uniform stability (hence the generalization) of stochastic gradient descent (SGD) for both convex and non-convex functions. Their results for non-convex functions requires that the learning rate л) scales with 1/t. Their work motivates a long line of subsequent work on generalization error bounds of gradient-basee and Lampert [2018], London [2016], Chaudhari al. [2019], Raginsky et al. [2017]. Mou al. [2018], Chen et al. [2018], Li et al. [2020], Negrea et al. [2019], Wang et al. [2021].
optimization methods: Kuzborskij
Recently, Simsekli et al. [2020], Hodgkinson et al. [2022] obtained generalization bound of SGD through the perspective of heavy-tailed behaviors and using the notion of Hausdorff dimension du which depends on both the algorithm and data.
PAC-Bayesian bounds. The PAC-Bayesian framework [McAllester, 1999] is a powerful method
for proving high probability generalization bound [Bartlett et al., 2017, Zhou al., 2019, Mou et al., 2018). Roughly speaking, it bounds the generalization error by the KL divergence KL (Q ]l P). where Q is the distribution of the learned output and P is prior distribution which is typically independent of dataset S. In this framework, bounding KT. (Q P) is the most crucial part for obtaining tighter PAC-Bayesian bounds. In order bound the KL divergence, both the prior P and posterior Q are typically chosen to be continuous distributions (mostly Gaussians so that KL can be computed in closed form). Hence, most prior work either considered gradient methods with continuous noise (such as Gradient Langevin Dynamics) (e.g., [Mou et al., 2018. 8, Li et al., 2020, Negrea et al., 2019]), or injected Gaussian noise to the final parameter at the end (e.g.. [Neyshabur et al., 2018, 1,, Zhou et al., 2019]) (so Q is a Gaussian distribution). We also note that designing effective prior P can be also very important. For example, Lever et al. [2013] proposed to use the population distribution to compute the prior. In fact, the prior can even partially depend on the training data [Parrado-Hernández Hernández et al., 2012, Negrea et al., 2019], 1I, and our Theorem 4. is partially inspired by this idea.

---

1.2
Our contributions
First, we provide high probability generalization bounds for discrete gradient methods. In particular. we study the generalization of Floored Gradient Descent (FGD), which is variant of GD, and Floored Stochastic Gradient Descent (FSGD), variant of SGD. We obtain our bound by an interesting construction of discrete priors. Secondly, we consider well studied gradient methods with continuous noise, (stochastic) gradient Langvin dynamics (GLD and SGLD). We show sharper generalization bounds by carefully bounding the concentration of the sample gradients. Now, we summarize our results.
FGD and FSGD. We first study an interesting variant of GD, called Floored GD (FGD) (Algo- rithm 1). The update rule of FGD defined as follows:
W₂ < W - 7hh V/(WW-1, - e floor (7:gt/ex),
(FGD)
where S, is the subset of training dataset S with size indexed by subset J C [n] (J is chosen before training). V/(W,,1, 2) == 2 E V,(W,,1, 2) the average gradient over the dataset Z, Nt is the learning rate. is the precision level, and == Vf(W:-1. the gradient difference. The flooring operation defined by floor sign (z) ||x|] for any real number FGD can viewed as GD with given precision limit ez. We can see if we ignore the floor operation or & approaches 0, FGD reduces to GD (see also Appendix A).
Vf(Wi-1. is
We also study a finite precision variant of SGD, called Floored SGD (FSGD) (see Section 5 for its formal definition). Empirically, the optimization and generalization capabilities of FGD and FSGD are very close to those of GD and SGD (see Figure 5 and in Appendix H).
By constructing discrete data-dependent prior and incorporate it into Catoni's PAC-Bayesian framework, we prove that the following bound (Theorem 5.2) holds for FGD with high probability:
R(Wr, D) S ((R, +0
1
In(dT)
7
m n
where d the dimension of parameter space and co can chosen to be a small constant. The bound for FSGD is very similar (see Theorem 5.3). Now we make few remarks about our results.
Our result holds for nonconvex and nonsmooth learning problems (replacing the gradients with subgradients for nonsmooth cases). Moreover, there is no additional requirement the learning rate 7/-.
2. The gradient difference ge is typical much smaller than the worst case gradient norm. usually decreases when m = |J] grows (see Figure Ic in Section 7).
3. We obtain non-vacuous generalization bounds on commonly used datasets. Specifically, our theoretical test error upper bounds on MNIST and CIFARIO are 0.026 and 0.198 respectively (see Section 7). Both of them are tighter than the best-known MNIST bound (11%) and CIFARIO bound (23%) reported in Dziugaite al. [2021]. See Table 1 in Appendix for more comparisons.
4. In order bound the KL between P and the deterministic process of FGD, we construct the prior P from a discrete random processes.. We hope it may inspire future research on handling deterministic optimization algorithms or discrete noise.
Why study FGD/FSGD? We would like to remark that we study FGD/FSGD, not because FGD/FSGD have better performances than GD/SGD or other advantages. Indeed, their perfor- mances are almost the same as those of GD/SGD (see Appendix H). We use them as important stepping stones to study generalization bounds for GD and SGD. Note that most existing trajectory- based generalization bounds require either fast decreasing learning rate, or continuous injected noise, such the Gaussian noise in Langevin dynamics, for general non-convex loss functions. Handling deterministic algorithms (such as GD) or discrete noises (such as SGD) is challenging and beyond fact, understanding such discrete noises and their effects on
the reach of existing techniques. generalization has been an important research topic (see e.g., Li et al. [2020], Zhu et al. [2019]. Ziyin et al. [2021]). In particular, Zhu et al. [2019] show that it is insufficient to approximate SGD's discrete noise by isotropic Gaussian noise. Moreover, proving nontrivial generalization bounds for SGD-like algorithms with discrete noise has also been proposed as an open research direction Li et al. [2020].
3

---

GLD and SGLD. We provide new generalization bound for Gradient Langevin Dynamics (GLD). The update rule of GLD is defined as follows.
W Wi- N4 V o
(GLD)
In this paper, we show that the following generalization bound (Theorem 6.2) holds with high probability over the randomness of D and random subset J c [n]] m))
2 L(W oi
L(W
R(Wr,D) S cuR(Wr. S(m) +0
11 + (n m)
E
where T(W == max=es [W 1)=l is the longest gradient norm of any training sample in at step and m is the size of J. Since Wr is independent of the index set J, the first term ((Ij)) is upper bounded by R(Wr. S) 7h with high probability, using standard Hoeffding's inequality. By setting m = n/2,, our generalization bound has an O Vn + ) rate. The new 1/n2 rate is obtained using the concentration of the difference between the gradient of training samples and that of the prior (See Lemma 6.1).
We also prove a high probability generalization bound for Stochastic Gradient Langevin Dynamics (SGLD) (see Theorem 6.3):
1
R(WT, D) CoR( +0
L(W,
m
b
We compare our bounds with other GLD/SGLD bounds obtained in [Mou et al., 2018, Negrea et al., 2019, Li et al., 2020] and the details can found Appendix
CLD. Using the PAC-Bayesian framework, we obtain new generalization bound for Continuous Langevin Dynamies (CLD), defined by the stochastic differential equation dW, - FFW,, 5) + /2-3- dB, The main term the generalization bound scales as ((1nn²) (by choosing m = n/2) and does not grow to infinity the training time T increases. See Theorem G.6 for the details.
2 Other Related Work
Stochastic Langevin Dynamics Stochastic Langevin dynamics is popular sampling and opti- mization method in machine learning [Welling and Tch, 2011]. Zhang et al. [2017], Chen et al. [2020] show polynomial hitting time (hitting stationary point) of SGLD in general non-convex setting. Raginsky et al. [2017] study the generalization and excess risk of SGLD in nonconvex settings and their bound depends inversely polynomially may be exponential small in the dimension. Continuous Langevin dynamics (SDE) with various noise structure has also been used extensively as approximations of SGD in literature (see e.g., [Li et al., 2017, 2021]). However, in terms of generalization, isotropic Gaussian noise is not a good approximation of the discrete noise in SGI) (Zhu al. [2019]).
certain spectral gap parameter, which
Nonvacuous PAC-Bayesian Generalization Bounds. Dziugaite and Roy [2017] first present a non- vacuous PAC-Bayesian generalization bound on MNIST 16. for I-layer MLP, see column T-600 of Table their paper). They use a very different training algorithm that explicitly optimizes the PAC-Bayesian bound and the output distribution is multivariate normal distribution. To computing the closed form of KL, they choose a gero-mean Gaussian distribution as the prior distribution. Zhou et al. [2019] obtain the first non-vacuous generalization bound for ImageNet via different method. Their method does not require any continuous noise injected but assumes that the network can be significantly compressed (so that the prior distribution is supported over the set of discrete parameters with finite precision). To our best knowledge, it is the only work that utilizes a discrete prior for proving generalization bounds of deep neural networks. Our result for FGD/FSGD has similar flavor in a high level, that is the optimization method has a finite precision. However, our results do need any assumption on compressibility of the model and can be applied to nonconvex learning problems other than neural networks.
Generalization bounds via Information theory. Raginsky et al. [2017] first show that the expected generalization error Es-D= [R(W, D) R(W, S)] is bounded by /21(S; W)/n, where I(S; W)

---

P(S) & P(W)) is the mutual information between the data set S and the parameter W. This work motivates several subsequent studies [Pensia et al., 2018, 8, Negrea et al., 2019, Bu et al., 2020, Wang et al., 2021]. The main goal in this line of work is to obtain a tight bound on the mutual information T(S; W). This is again reduced bounding the KI. divergence and thus typically requires continuous injected noise (e.g.. Wang et al. [2021], Negrea et al. [2019]).
KL (P(S, W)
3 Preliminaries
Notations. We assume that the training dataset S = (21,-., zn) is sampled from DD, where D is the population distribution over the data domain Q2 The model parameter w is in IR The risk function R: Rd x Ω - [0. 1] measures the error of a model on datapoint. The loss function f R x - IR a proxy of the risk. The optimization algorithm minimizes the loss function and we assume we can compute the gradient of the loss function. We note that the loss function may be different from the risk function (e.g.. 0/1 risk vs the cross-entropy loss). The empirical risk R(w, S) - [S] Ezes R(w, =) and population risk is R(w, D) = EI-D (R(w, 2)]- Similarly, we can define the empirical loss f(w, S) and population loss f(w, D). For any J (.m)....m.. we use S, to denote the sequence (S), S.... The subsequence (A,, A.+1, .y) is denoted by A. We use (AF. BTT) to denote BI...... Bm). When the elements in sequence J are distinct, we also use J to represent the set consisting of all of its elements. We may also slightly abuse the notation of random variable to denote its distribution. For example, Ex=x [xx)) is shorthand for Px [fx)),, and KL (X || Y) means KL (Px Py). For a random variable W, we define R(W. S) = Rwo [Rw S)] and R(W, D) = Ew [R(w, D)). The set (1.2..., n} is denoted by [n].
the merged sequence A2,........
KL KL-divergence. Let P and Q be two probability distributions. The Kullback-Leibler diver- gence KL (Pl] Q) is defined only when P is absolute continuous with respect to Q (i.e., for 0 implies P(z)= 0). In particular, if P and Q are discrete distributions, then P(a) Otherwise, if P and Q are continuous distributions, it is defined KL (P Q) = P(r) In Q(=)
any x, (xx)
as f P(x)) In P(z) dr. The following Lemma 3.1 is frequently used in this paper and is a well known
Q(x] property of KL divergence (see Cover [1999, Theorem 2.5.3), Li et al. [2020], Negrea et al. (2019]). Lemma 3.1 (Chain Rule of KL). We are given two random sequences W = (Wo.... Wr) and W = (Wo--.. -.. W7). Then, the following equation holds (given all KLs are well defined):
T
KL (W) || [W) = KL (Wol W
Σ
E
KL (W.lW = w W W/ w)
w-
Here W. W. w denotes the distribution We,
W. conditioning on W (Wo.... ..., W(-1) w. PAC-Bayesian. In this paper, we use the PAC-Bayesian bound presented in Catoni [2007] which enjoys tighter O(KL (Q /n) rate comparing to the traditional O KL (Q P) /n) bound, but with slightly larger constant factor on the empirical error. We restate their bound as follows.
Lemma 3.2 (Catoni's Bound), e.g. Lever et al. [2013]) For any prior distribution P independent
of the training set S, any ō E (0, 1), and any 1) > O, the following bound holds w.p. 2 8 over S D":
KT. (Q P) + (111/)
E R(W, D)J < n0, E S)] W~Q
(VQ),
(1)
w-Q
where Cy = - an absolute constant.
Concentration inequality. We use the following variant of McDiramid inequality (Lemma 3.3) to prove the concentration of cumulative gradient difference in Section 6. The proof is deferred to Appendix C.
Lemma 3.3. Suppose $ [m]m -> R is order-independent and [+(J) - -JJ')) S e holds for any adjacent J' E <in]m satisfying [J n J'l
- 12. Let J be indices sampled uniformly from [r] without replacement. Then Pr, (J) F. [J)) > c] S exp( =25
"Ji,s...., = "(i holds for any input = (J1y..., jm) E 2 and any permutation a E 8m 2 JJnJ': := (i [n] J'
5

---

Data-Dependent PAC-Bayesian Bound
The dominating term in the PAC-Bayesian bound (1) is KT. (Q P) /n, where P is prior distribu- tion independent of the training dataset S. Typically, without knowing any information from S, the best possible bound for KL (Q (1 P) we can hope is least ( (it should not be function of hence should not decrease with n). However, if we are allowed to see m data points from S when constructing our prior, may produce better prediction on posterior Qs. The following theorem enables us to use data-dependent prior in PAC-Bayesian bound. The proof is almost the same as Cantoni's 's original proof and we provide proof for completeness in Appendix D.
Theorem 4.1 (Data-Dependent PAC-Bayesian). Suppose J is random sequence including m indices uniformly sampled from [n] without replacement. For any E (0, 1) and nj > have wap. 2 8 over ~ 'D" and J:
KL (Q
[2] P(S)) + In(1/)) (vQ),
R(Q,D) S RI (C, On:
m
where / = [n]]]] J is the set of indices not in J, P(S,) is the prior distribution only depending on the information of S5 (S, is the subset of S indexed by J), and C == I-c is constant.
Remarks. Note that the above bound holds regardless whether Q depends on S or not. Also note that the first term in the right hand side is Sy), not R(Q,S) S) in the usual generalization bounds. We remark that for most of our learning algorithms that are independent of (i.e., changing J does not change the output Q). by standard bounded by 5)) + 0(1/ the update rules of GLD, SGLD and CLD are independent of J, hence R(Q, Sy) can be replaced by R(Q, S) + O(1//n m) in Theorem 4.1. However, we point out a subtle point that FGD (Algorithm 1) studied in this paper depends more information from Sy but not much from Sj. unintentionally making R(Q, Sr) validation error, rather than the training error as it should be. However, from our experiment (see Figure 5 and in Appendix H. and Figure 2a), we can see that FGD is very close to GD and the S₁ error RWW,, S1) indeed close to the training error R(W,, S) and both are significantly smaller than the testing error RR,,, D). So R(Q, Si) can be considered as genuine training error in our study of FGD.
Sheemoff-Hooffciing inequality, R(Q,S,) can be m) with high probability over the randomness J. For example,
J. may be the case that by knowing J. FGD extracts
FGD and FSGD
In this section, study the generalization of finite precision variants of gradient descent and stochastic gradient descent: Floored Gradient Descent (FGD) and Floored Stochastic Gradient Descent (FSGD).
First we need to define the "floor" operation which is used in the definitions of FGD and FSGD. Definition 5.1 (Floor). For any vector X E Rd, ler Y = floor(X X) defined as:
Y floor(X,) = X X 2 0, = = Xf < 0, for all i E [d].
FGD: The Floored Gradient Descent algorithm formally defined in Algorithm 1, where (1i) and (5x)120 are the step size and precision sequences, respectively. For subset Z S S, we write (f(W.,,, 1 Σzez V, Note that FGD can be viewed as gradient descent with given precision limit Et. We see if we ignore the floor operation or let E, approach 0, FGD reduces to the ordinary GD (see Appendix A). We also study momentum FGD, in which the 5th line of Algorithm 1 is replaced by
W. <- W,-1 17-146 a (W,-1 W,-2) 92 St floor((g) - e2)/
Here a > 0 is a constant. We remark that both FGD and its momentum version are deterministic algorithms. The following theorem provides the generalization error bound for both algorithms.
Theorem 5.2. Suppose J is a random sequence consisting of m indices uniformly sampled from [n] without replacement. Then for any E (0, 1), both FGD (Algorithm 1) and its momentum version satisfy the following generalization bound w.p. at least - 8 over S ~ D and J:
R(W+. D) R,,, C. ln(1/8) +3
C₂ In(d))
T
Σ tm
Ig

---

Algorithm 1: Floored Gradient Descent (FGD)
Input: Training dataset S (21.") 2n). Index set J.
Result: Parameter Wr E IRd.
Initialize Wo f- Wo:
for i 1 + T do
- "n V,,
92 - " (.
W, < Wi-1 - 92 - Es floor((g1 92)/Er);
end
where d the dimension parameter space, I = [n]]]] is the set of indices not in J, Cy I- constant, and g: (f(W - (f(W(-1,
Proof. We use Theorem 4.1 to prove our theorem for the momentum version. The ordinary FGD is special case of the momentum version with 0. The key is to construct the prior distribution P(S,) such that KT, (Wr)) P(S,)) is tractable. Let be any real number in (0, 1/3). We first define a stochastic process
W4J. by the following update rule (Wi == wo):
W + Wi + a- (Wi-1 W;-2) - WW - E. E..
where & is a discrete random variable such that for all (al, ad) zd:
Pr(f: (a1, ad) '1
exp Σ k=1
In(1/p)of
is easy to verify that the sum the probabilities ( only depends on Sy. We define P(S,) the distribution of W
Pr(c: = a)) equals 1. Note that W/
Recall that W (Wo..., W;) is the parameter sequence of FGD (Algorithm 1). Applying the chain rule of KL-divergence (Lemma 3.1), we have:
KL (Wrl P(S.)) = KL (Wr WG) & KL W w
KL (WilW-- w W =w] =
(2)
wi
KT. (WalWo-1= = wh Wi = W6-1).
The last equation holds because FGD is deterministic.
Let w
W The distribution of Y1 (V S) - vf(w(-1,
W. We(w--1 w (where w = (wo, 1) is point mass on
Wi-1 - a -- - w[-2) - 70 v (w
floor
Let vector = (aI,...,ad) ) = floor 22 (Vf(w: (;
- V---Vfflee v((w(-1, By the definition of W/
we have
KL W = w Wi =w) =1 (1/ 1/Prr =a])
in Σ
Σ In(1pp) oz
Since |i| < 2 and (0, 1/3), we have in Do p² p²)dd) is at most dln (1 + Eie p¹). It can be further bounded by dln (1 + 3p). Moreover, can be bounded by 3dp as In(1 + x) < Thus, the above KL-divergence be bounded by 3dp + Ed_ In(1/p)of. Recall that the
7

---

kth entry of a is = - SV) - vaf(wr-1,, which is less than or equal to 25 (Vaf(ui-1, Vxf(w,-1, 8y)). Therefore, we have
In(1/p)7t [V((u=1, S :
KL (WalWh-1= = w1 w| = w) s 3dp E7
Plugging the above inequality into (2), we have
3dp + In In(1/p)²
KL (Wr P(S,))
-V
of
We conclude our proof by plugging it into Theorem 4.1 (setting p 1/(Td)).
We can use similar approach to prove a generalization bound for Floored Stochastic Gradient Desent (FSGD). Formally, FSGD is identical to Algorithm except for the definitions of gi and 92 replaced with:
FSGD:
VB.W.-I.BB.) 92 f Vf(W.-1.SBo.)
where B, S. [r]] a random batch independent S, J and W Formally, each B, is a set including b indices uniformly sampled from [n] without replacement. The following theorem provides a generalization bound for FSGD. The proof can be found in Appendix F.
Theorem 5.3. Suppose is a random sequence consisting of m indices uniformly sampled from [n] without replacement. Then for any 8 E (0,1), (0, 1), FSGD satisfies the following gemeralization bound: w.p. at least 8 over D and J:
R(WT, D) S C,,,, St) C. 1m(1/8) +
C In(dT)
T
E
gr
m
n
B
where d is the dimension of parameter space, = [n] On == I-c is constant, and g: SB.) SS(W.-)
6 Gradient Langevin Dynamics
In this section, we present new generalization bounds for Gradient Langevin Dynamics (GLD) and Stochastic Gradient Langevin Dynamics (SGLD) based Theorem 4.1.
Gradient Langevin Dynamics (GLD): The GLD algorithm can be viewed as gradient descent plus Gaussian noise. Formally, for given training set 5 ~ DD", the update rule of GLD is defined as follows:
W+11 < W,
7
VJ(,,, +
(GLD)
F
ZES
Here the gradient (),,, 2) can be replaced with any gradient-like vector such elipped gradient. The output of GLD is the last step parameter Wy or some function of the whole training trajectory W (e.g., the average of the suffix K Σi= W,).
We still use the data-dependent PAC-Bayesian framework (Theorem 4.1) prove the generalization bound for GLD. Unlike FGD (Algorithm 1), GLD is independent of the prior indices J, which enables us to prove the following concentration bound (Lemma 6.1) for the gradient difference. The proof is based on Lemma 3.3, which is postponed to Appendix F.
Lemma 6.1. Let S = (zI,...en) be any fixed training set. is a random sequence including m indices uniformly sampled from [m] without replacement, and W (Wo..., ..., Wr) is any random sequence independent of J. Then the following bound holds with probability at least 1 over the randomness of J:
E
T
S)
Cs <
E
L(We_1)
where C3 = 4+ 2lm(1 + 5.66 II(1/8) and L(w) max |/ (ww,

---

1.00
bound test error
Evmi 5,1l
0.75
0.03
test error
3000
0.50
0.02
2000
0.25
0.01
1000
0.00
0.00
600
1000
4000
6000
steps
Steps
m
(a) entire training path
(b) later stage
(c) gradient difference
Figure I: MNIST + CNN + FGD. In (a) and (b), we plot the true test error and our bound (Theorem 5.2 with 7/ = 1.5, 6 = 0.1). (c), we show how cumulative gradient difference decreases as m (the size of J) increases.
Now are ready to present main results. The proofs can be found in Appendix F. Theorem 6.2. Suppose is a random sequence consisting of m indices uniformly sampled [n]] without replacement. Let Wr be the output of GLD. Then for any å (0, 11) and
0. have w.p.
1 26 over S ~ D and J, the following holds (L(w) = max Ilf w. =){
1n1n(1/8)
Co
R(Wr, D) S C,,RR,
E 2(n m m)m W
I(W.-1)2
where C3 = 4 21 (1/0) + 5.60 (1188)) 5.006/1((11))) I= [n]] and C.
I-e-
Stochastic Gradient Langevin Dynamics (SGL.D): For given training data set S, the update rule of SGLDD is defined as:
W + Wi 7+ fWW, + 00,
(SGLD)
where B, uniform (zi]) o is the mini- batch of size b step Note that B, is sequence instead of a set, thus it may include duplicate elements. Similar to the analysis of GLD, we can prove the following bound for SGLD.
Theorem 6.3. Let WT be the output of SGLD when the training set is S, and be a random sequence with indices uniformly sampled from [n) without replacement. For any 8 E (0, 1) and m have w.p. 2 1 - 26 over S ~ D and J, the following holds:
C2 (n(1/1))
Cn
C5 2m
R(W D) S STG
Σ
L(W, 1)²
b
W
of
1=1
where L(w)= == m (If(w,) Cs = + (1 + 5.66 /5.66/1m(110)) C = I is the batch size, and I [m]],].
Remark 6.4. If the gradient norm is bounded and we use decaying learning rate schedule such as x O(1/t), then the summation in our bound converges. Hence, under such a learning rate schedule, Theorem 6.2 and 6.3 imply the following test error bound for GLD or SGLD: R(Wr, r, D) S M,,,, + Ō (_)) which is independent T, where Ô hides some logarithmic factors.
Experiment
In this section, we conduct experiments for FGD and FSGD on MNIST [LeCun et al., 1998] and CIFARIO [Krizhevsky al., 2009] to investigate the the optimization and generalization properties of FGD and FSGD, and the numerical closeness between our theoretical bounds and true test errors. Due to space limit, the detailed experimental setting and some additional experimental results can be found in Appendix H.
FGD/FGG GD/SGD. We first demonstrate that the training and testing curves of FGD and GD are nearly identical (we choose precision level = 0.005 or 0.004). We also show that the same is true for FSGD vs SGD. Due space limit, the figures are presented in Appendix H (Figure and 6).
il =) & L holds for all w,

---

1.
1.0
train error R(S)
our bound
70000
error R(S;
test
60000
test error R(D)
Cyboundy
50000
40000
2000
4000 -leps
6000
8000
0.0
2000
4000
6003
800D
20000
2000
4000
6000
8000
sleps
0I
(a) training and test (FSGD)
errors
(b) our bound
(c) gradient difference
Figure 2: CIFARIO + SimpleNet + FSGD. In (a), we plot R(WT, R(WT, S) and the test error. We can see that R(Wr.Sp S2) is very close to RWWr, In (b), we plot our theoretical bound (Theorem 5.3 with 7, = 2, = 0.1). The red part corresponds to the first term our bound (the empirical risk) and the green part corresponds to the rest. The last step test error and our bound 0.18 and 0. 0.198, respectively. In (c), we show how cumulative gradient difference decreases as m (the size of J) increases.
Non-vacuous bounds. For MNIST, we train a CNN (d = 1.4 10%) by FGD with "t = 0.005 0.91 and E, = 0.005 and momentum a = 0.9). The size = |J] is set to n/2 = 30000. As shown in Figure 1a and 1b, our bound (Theorem 5.2 with 77 1.5, 8 0.1) tracks the testing error closely, At step 7" = 990, our bound is 0.026 while the testing error is 0.011. This is non-vacuous and tighter than best known 11% MNIST bound reported in Dziugaite al. [2021]. For CIFAR1O 100 we train a SimpleNet [Hasanpour et al., 2016] without BatchNorm and Dropout. The number of parameters d nearly 18 10 We use FSGD to train our model. The learning rate % is set to 0.001 0.9(4/200] the precision E is set to 0.004, and the momentum is set 0.99. The batch size is 2000. m = [/] is set to n/5 = 10000. The result is shown in Figure 2b. We stop training at step t 8000 when the testing error is and 0.18. At that time, our testing error bound 0.198 which non-vacuous and tighter than best known 0.23 CIFARIO bound reported in Dziugaite et al. [2021].
Decrease of the gradient difference. Intuitively, the cumulative squared norm of gradient differ- ence == V fWW S) (WW,, .S)) should decrease as m |J] increases. Although we cannot prove a concentration like Lemma 6.1 (i.e., |lg: scales O(1/m)), can still observe that ||g/]] decreases when m increases. The results are depicted in Figure Ic and Figure 2c.
Random labels. We conduct the random label experiment designed in Zhang et al. [2017]. Our theoretical bounds can distinguish the datasets with different portion (p) of random labels. See Appendix H.
8 Conclusion
In this paper, we prove new generalization bounds for several gradient-based based methods with either discrete continuous noises based on carefully constructed data-dependent priors. Recall that FGD requires to compute the gradient difference for technical reasons. would be more natural and desirable if only need to compute the full gradient and rounded the nearest grid point. An intriguing future direction is to free FGD/FSGD from the dependence of the prior subset J so that we the gradient difference to obtain tighter bound. Of course, major
can apply the concentration further direction is to obtain similar generalization bounds for vanilla GD and SGD, which remains be an important open problem this line of work. Our technique can be useful for handling deterministic algorithms and discrete noises, but it seems that new technical ideas or assumptions are needed for tackling GD or SGD.
Acknowledgements
The authors would like to thank the anonymous reviewers for their constructive comments. The au- thors are supported in part by the National Natural Science Foundation of China Grant 62161146004 Turing AI Institute of Nanjing and Xi' an Institute for Interdisciplinary Information Core Technology.
10

---

References
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Zhang. Stronger generalization bounds for deep nets via a compression approach. In International Conference on Machine Learning, pages 254-263, PMLR, 2018.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pages 322-332. PMIR, 2019.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Opectrally-normalizee margin bounds for neural networks. Advances in neural information processing systems, 30, 2017.
Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-526 526, 2002.
Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In Conference on Learning Theory, pages 610-626. PMLR, 2020.
Yuheng Bu, Shaofeng Zou, and Venugopal Veeravalli. Tightening mutual information- bounds on generalization error. IEEE Journal on Selected Areas in Information Theory, 1(1): 121-130, 2020.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in neural information processing systems, 32, 2019.
Olivier Catoni. Pac-bayesian supervised classification: the thermodynamics of statistical learning. IMS Lecture Notes Monograph Series, 16:1-163, 2007. doi: 10. 1211447772277770000000
Pratik Chaudhari, Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Christian Borgs, Jennifer Chayes, Levent Sagun, and Riccardo Zecchina. Entropy-sgd: Biasing gradient descent into wide valleys. Journal of Statistical Mechanics: Theory and Experiment, 2014(12):124018, 2019.
Xi Chen, Simon S Du, and Xin T Tong. On stationary-pon -pontt hitting time and ergodicity of stochastic gradient langevin dynamics. Journal of Machine Learning Research, 2020.
Yuansi Chen, Chi Jin, and Bin Yu. Stability and convergence trade-off of iterative optimization algorithms. CoRR, 2018
Thomas M Cover. Elements of information theory. John Wiley Sons, 1999.
Monroe D Donsker and SR Srinivasa Varadhan. Asymptotic evaluation of certain markov process expectations for large time. iv. Communications on pure and applied mathematics, 36(2):183-212, 1983.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International conference on machine learning, pages 1675- 1685. PMLR, 2019.
Devdatt P. Dubhashi and Alessandro Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 2009. ISBN 978-0-521-88827-3.
John Duchi. Derivations for linear algebra and optimization. Berkeley, California, 3(1):2325-5870. 2007.
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. UAI, 2017.
Gintare Karolina Dziugaite, Kyle Hsu, Waseem Gharbieh, Gabriel Arpino, and Daniel Roy. On the role of data in pac-bayes bounds. International Conference on Artificial Intelligence and Statistics, pages 604 612. PMLR, 2021.
Vitaly Feldman and Jan Vondrak. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. Conference on Learning Theory, pages 1270-1279, PMLR, 2019.
11

---

Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. Conference On Learning Theory, pages 297-299, PMLR, 2018.
Mahdi Haghifam, Jeffrey Negrea, Ashish Khisti, Daniel M Roy, and Gintare Karolina Dziugaite. Sharpened generalization bounds based conditional mutual information and application to noisy, iterative algorithms. Advances in Neural Information Processing Systems, 13:9925-99335 2020.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference machine learning, pages 1225-1234. PMIR, 2016.
Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve-dimension bounds for piecewise linear neural networks. In Conference on learning theory, pages 1064-1068. PMLR, 2017.
Seyyed Hossein Hasanpour, Mohammad Rouhani, Mohsen Fayyaz, and Mohammad Sabokrou. Lets keep simple, using simple architectures outperform deeper and more complex architectures. CoRR, 2016.
Liam Hodgkinson, Umut Simsekli, Rajiv Khanna, and Michael Mahoney. Generalization bounds using lower tail exponents in stochastic optimizers. In International Conference on Machine Learning, pages 8774-8795. PMLR, 2022.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. Master's thesis, University of Tront, 2009.
Ilja Kuzborskij and Christoph Lampert. Data-dependent stability of stochastic gradient descent. In International Conference on Machine Learning, pages 2815-2824 PMLR, 2018.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11)2228-22224 1998.
Guy Lever, François Laviolette, and John Shawe-Taylor Tighter pac-bayes bounds through distributionndeeeeddemt priors. Theoretical Computer Science, 473:4-28, 28, 2013.
Jian Li, Xuanyuan Luo, and Mingda Qiao. On generalization error bounds of noisy gradient methods for non-convex learning. In International Conference on Learning Representations, 2020.
Qianxiao Li, Cheng Tai, and E Weinan. Stochastic modified equations and adaptive stochastic gradient algorithms. In International Conference Machine Learning, pages 2101-2110 100 PMLR, 2017.
Zhiyuan Li, Sadhika Malladi, and Sanjeev Arora. On the validity of modeling sgd with stochastic differential equations (sdes). Advances in Neural Information Processing Systems, 34, 2021.
Ben London. Generalization bounds for randomized learning with application to stochastic gradient descent. NIPS Workshop on Optimizing the Optimizers, 2016.
Ben London. A pac-bayesian analysis of randomized learning with application to stochastic gradient descent. Advances in Neural Information Processing Systems, 30, 2017.
David A McAllester. Some pac-bayesian theorems. Machine Learning, 37(3)3355-36, 1999.
Wenlong Mou, Liwei Wang, Xiyu Zhai, and Kai Zheng. Generalization bounds of sgld for non-convex learning: Two theoretical viewpoints. In Conference on Learning Theory, pages 605-638. PMLR, 2018.
Vaishnavh Nagarajan and Zico Kolter. Generalization deep networks: The role of distance from initialization. NewrIPS, 2017.
12

---

Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable to explain generalization in deep learning. Advances in Neural Information Processing Systems, 32, 2019.
Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M Roy. Information-theorer generalization bounds for sgld via data-dependent estimates. Advances in Neural Information Processing Systems, 32, 2019.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-hayesian approach to spectrally- normalized margin bounds for neural networks. In International Conference on Learning Repre- sentations, 2018.
Luca Oneto, Sandro Ridella, and Davide Anguita. Differential privacy and generalization: Sharper bounds with applications. Pattern Recognition Letters, 1-38, 2017.
Emilio Parrado-Heráánde Amiran Ambroladze, John Shawe-Taalor, and Shiliang Sun. Pac-bayes bounds with data dependent priors. The Journal of Machine Learning Research, 13(1):3507-3511, 2012.
Ankit Pensia. Varun Jog. and Po-Ling Loh. Generalization error bounds for noisy, iterative algorithms. In 2018 IEEE International Symposium on Information Theory (ISIT), pages 546-550. IEEE, 2018.
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: nonasymptotic analysis. In Conference Learning Theory, pages 1773-1703. PMLR, 2017.
Hannes Risken. Fokker-planck equation. In The Fokker-Plance Equation, pages 63-95. Springer, 1996.
Umut Simsekli, Ozan Sener, George Deligiannidis, and Murat A Erdogdu. Hausdorff dimension, heavy tails, and generalization neural networks. Advances in Neural Information Processing Systems, 33:5138 3-511, 2020.
Hao Wang, Yizhe Huang, Rui Gao, and Flavio Calmon. Analyzing the generalization capability of sgld using properties of gaussian channels. Advances in Neural Information Processing Systems, 34, 2021.
Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets vs their induced kernel. Advances in Neural Information Processing Systems, 32, 2019.
Max Welling and Yee W Teh. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference on machine learning (ICML-11), pages 681-688. Citeseer, 2011.
Bingzhe Wu, Zhicong Liang, Yatao Bian, ChaoChao Chen, Junzhou Huang, and Yuan Yao. General- ization bounds for stochastic gradient langevin dynamics: A unified view via information leakage analysis. CoRR, 2021.
Jun Yang, Shengyang Sun, and Daniel M Roy. Fast-rate pac-bayes generalization bounds via shifted rademacher processes. Advances in Neural Information Processing Systems, 32, 2019.
Valentina Zantedeschi, Paul Viallard, Emilie Morvant, Rémi Emonet, Amaury Habrard, Pascal Germain, and Benjamin Guedj. Learning stochastic majority votes by minimizing pac-bayes generalization bound. Advances in Neural Information Processing Systems, 34:455-467, 2021.
Chiyuan Zhang, Samy Bengio. Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In 5th International Conference on Learning Representations, ICI. 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
Yuchen Zhang, Percy Liang, and Moses Charikar. A hitting time analysis of stochastic gradient langevin dynamics. In Conference Learning Theory, pages 1980-2022. PMLR, 2017.
13

---

Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P. Adams, and Peter Orbanz. Non-vacuour generalization bounds the imagenet scale: pac-bayesian compression approach. In 7th International Conference Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
Zhanxing Zhu, Jingfeng Wu, Bing Yu, Lei Wu, and Jinwen Ma. The anisotropic noise stochastic gradient descent: Its behavior of escaping from sharp minima and regularization effects. In International Conference Machine Learning, pages 7654-7663. PMLR, 2019.
Liu Ziyin, Kanggiao Liu, Takashi Mori, and Masahito Ueda. Strength of minibatch noise in sgd. In International Conference on Learning Representations, 2021.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] [Yes], [No], or [N/A]- You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license to the code and datasets? [Yes]
Did you include the license the code and datasets? [No] proprictary.
The code and the data are
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See the conclusion section.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] It can be found in our supplemental material.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
14

---

(c) Did you discuss whether the data you are using/curating contains personally identifi- able information offensive content? [N/A] We only use the standard MNIST and CIFARIO 10 datasets.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "nilnt3qRR1X", "reviewer": "Reviewer_Zg1r", "summary": "This paper studies the generalization property of gradient-based optimization algorithms using PAC-Bayesian bound. To this end, the authors first provide a bound using data-dependent prior (Theorem 4.1) and use it to prove generalization bounds for FGD, FSGD, GLD, and SGLD. The authors also empirically observed that some proposed bounds are not vacuous for the MNIST classification task.", "questions": "All questions are listed in the Strength and Weakness section.", "limitations": "The authors mentioned that the conclusion section (in Appendix) contains the limitation; however, I couldn't find related discussions.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I like the idea of the paper and its results, while there are some unclear parts. I will raise my score once the authors resolve/answer the following issues/questions.\n- Is there any reference/application of FGD (or FSGD)? If not, is there any theoretical implication of these results for GD (or SGD)? \n- It seems that the proposed bounds can be vacuous due to the $\\eta C_\\eta$ multiplicative factor if the learning algorithms cannot achieve nearly zero training error. Is there optimal $\\eta$ for the non-zero training error case which enables the bound non-vacuous?\n- I am not sure if one can directly compare the GLD and SGLD bounds in the paper with those in [Negrea et al., 2019]. The authors applied Catoni's PAC-Bayesian bound to the result of [Negrea et al., 2019] and derived $O(\\frac1{n-m}+\\frac{(n-m)}{n^2}\\sum_{t=1}^T\\frac{\\gamma_t^2}{\\sigma_t^2}L^2)$. However, this bound and the bound in Theorem 6.2 may not be directly comparable since they bound different quantities; the first terms in RHS in Theorem 4.1 and Lemma 3.2 are different. I would like to see a more detailed discussion comparing the bounds in [Negrea et al., 2019] and this paper.\n- Using the proposed GLD bound under mild assumptions including decaying step size (e.g., $\\gamma_t\\propto1/t$), Lipschitz continuity of $f$, etc., it seems that the generalization gap reduces to $O(1/(n-m))$, regardless of $T$. Using this reduction, can the excess risk bound also be derived?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "YgxY_QHxDt", "reviewer": "Reviewer_4EBj", "summary": "This paper utilizes data-dependent PAC-Bayesian bounds to derive generalization errors for a variety of gradient-based learning algorithms. The key idea is to construct a special prior based on a run of the algorithm from a randomly selected subset of the data. In the algorithms studied, these priors lead to tractble upper bounds on the PAC-Bayesian bounds, and thus bounds on the overall generalization error. In tests on MNIST, the bounds are quite tight, and they also give non-vacuous bounds on generalization error for CIFAR. ", "questions": "From what I can tell, the FGD is deterministic once the data set is fixed. As a result, Theorem 5.2 can be applied to a single run on FGD to give a high-probability bound on the test error. \n\nIn contrast, it would seem that this is not necessarily possible for the stochastic algorithms, FSGD and the Langevin variants. In particular, the term $\\mathcal{R}(W_T,S_I)$ requires averaging out the effects of the randomness of the algorithms. Is this the correct way to interpret this?\n\nBased on that question above, is there a way to get true high-probability bounds for these stochastic algorithms? Would it just require running them several times (for a fixed dataset and selected $J$) and doing a concentration bound on the training error? Is there something more clever that can be done?", "limitations": "Yes. They indicate that the potential for negative societal impact is not applicable, and I agree.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\nThe methodology for deriving the bounds is quite interesting, and the bounds themselves give nice insights into the performance of various algorithms. The basic ideas seem quite extensible to a variety of different algorithms. The paper is well-written and well-organized.\n\nWeaknesses\nThe paper does have some typos and basic mistakes. All of them appear to be fixable. \n\nLemma 3.2 appears to be stated incorrectly. The bound on the right should probably include an empircal risk term, not a population risk term. However, this lemma is never actually used in the paper, from what I can tell. (The correctly stated Theorem 4.1 is used.) So, it could likely be removed. \n\nThere are a few fixable mistakes at the end of the proof of Theorem 4.1. Specifically, the equality between lines 517 and 518 does not hold. A related inequality, based on convexity does hold, but that goes the wrong way. So, a different approach is needed.\n\nEdit: Based on discussions, some better motivation for the algorithms is required.\n\nHere is a way to fix it. Let $c=\\frac{\\lambda}{n-m}$ and recall that $w$ is fixed. Note that for random $z_i$, $\\mathcal{R}(w,z_i)$ is a Bernoulli random variable which has expected value $\\mathcal{R}(w,\\mathcal{D})$. For simpler notation, set $b=\\mathcal{R}(w,z_i)$ and $q=\\mathcal{R}(w,\\mathcal{D})$. Direct calculation shows that \n$$\nE_b\\left[e^{c(\\Phi(q)-b)} \\right] = \n\\frac{e^{0}(1-q) + e^{-c}q}{1-(1-e^{-c})q}=\n1\n$$\n\nThe reference to Theorem 1 on line 538 probably should refer to Theorem 5.2\n\nIn line 554, the bound should probably be $\\|V_t\\|\\le \\frac{2}{m} L(W_{t-1})$. Based on this, the looser bound from line 551 seems unnecessary. \n\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IYtJzsAih1L", "reviewer": "Reviewer_nRQb", "summary": "In this paper, the authors introduced a new discrete data-dependent prior to the PAC-Bayesian framework, and prove a high probability generalization based on Floored GD. The bound depends on the gradient difference $\\|g_t\\|$ between the full batch gradient and that of the prior samples. The empirical results showed that the presented bound could be non-vacuous. \n\n", "questions": "The presented bound seems to decrease first and then increase again (figure 1(b) and Figure 2(c)), even after the test error stabilizes after certain training steps. This would lead to a very loose and eventually vacuous bound, which is not ideal and becomes useless in the later training steps.  I am wondering how does the cumulative gradient difference change over the training epoch? \n", "limitations": "The experiments are very limited and do not have any comparison with the current available non-vacuous generalization bound.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The FGD is used to derive the bound. While FGD has shown to have a similar learning curve as SGD (Figure 2 (a) vs. (b)), computing two gradients in a row with one of them to be a full batch gradient could be computationally expensive. While I understand the authors introduced FGD as an alternative to GD/SGD as a convenient way to analyze the bound, I do not think FGD/FSGD could become popular in practice and is not easy to understand intuitively.   \n\nThe empirical evaluation is fairly weak. The bound on Cifar-10 looks fairly loose even though part of it is non-vacuous. While there exist bounds that are non-vacuous on Cifar-10 and are empirically shown to be much tighter than the presented bound, it is essential to provide a fair comparison to such bound to show the usefulness of the presented new bound.\n\nThere are a couple of typos in the paper:\nLn 85-86 \"Floored Gradient Descent (FSGD), a variant of SGD.\" --> Floored Stochastic Gradient Descent (FSGD)\nFigure 2 Caption * MNIST+SimpleNet+FSGD/SGD --> Should be CIFAR-10 not MNIST\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "EGh42XmjBpQ", "reviewer": "Reviewer_XXfA", "summary": "This paper is concerned with proving new generalization bounds for gradient descent methods, by using suitable priors. To this end, the Catoni's PAC-Bayesian framework is used. But, unlike other work, this paper does not use restrictive assumptions on the learning rate or continuous injected noise. \nMore precisely, the authors show a high-probability generalization bound for Floored gradient descent. \nIn a similar way, the authors derive generalization bounds for (stochastic) gradient Langevin dynamics.", "questions": "1. Floor Gradient descent seems a bit constructed. Why would one be interested in that? Why would one use a mini-batch gradient if one computes the full gradient anyway?\n2. There are some references missing that also don't come with the restrictions of a step-size schedule or injected noise, e.g. https://proceedings.neurips.cc/paper/2020/hash/37693cfc748049e45d87b8c7d8b9aacd-Abstract.html\n3. I would suggest to carefully clean up the text, there are quite a few language mistakes.\n\nOverall, the clarity of the writing and presentation has to be improved. Like this, I cannot recommend the paper for NeurIPS.", "limitations": "The authors have adequately addressed the limitations. There are no potential negative societal impacts.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: Generalization bounds are an extremely central topic of ML. As far as I know, these bounds are novel. While floored gradient descent seems a bit artificial, the extension to stochastic gradient Langevin dynamics is very useful. The authors explain suitably how they choose the prior P. The literature review is nice and useful.\n\nWeaknesses: \n--- The writing is unfortunately poor, many typos and formulations which are difficult to understand. Due to this, I found the paper lacking in quality and could not follow the flow of the arguments in many cases. \n--- The main result is on floored gradient descent, which is not a very relevant method. According to Algorithm 1, it seems to consist of computing the full gradient and a batch gradient. Why would one compute the batch gradient if one already afforded to compute the full gradient? This has to be much better justified... \n--- The concept of data-dependent prior needs more explanation. Is this a usual concept in the literature?\n--- The experiment section is very short.\n--- No plots or illustrations are given to provide intuition. It would, however, be important to give intuition for the data-dependent priors, etc.\n--- The paper ends abruptly, without any conclusion or discussion of future work.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept