On the Importance of Gradient Norm in PAC-Bayesian Bounds
Authors: Itai Gat
Yossi Adi
Alex Schwing
Tamir Hazan
Venue: NeurIPS 2022 Accept (2022)
Keywords: generalization bound
pac-bayes

Abstract: Generalization bounds which assess the difference between the true risk and the empirical risk have been studied extensively. However, to obtain bounds, current techniques use strict assumptions such as a uniformly bounded or a Lipschitz loss function. To avoid these assumptions, in this paper, we follow an alternative approach: we relax uniform bounds assumptions by using on-average bounded loss and on-average bounded gradient norm assumptions. Following this relaxation, we propose a new generalization bound that exploits the contractivity of the log-Sobolev inequalities. These inequalities add an additional loss-gradient norm term to the generalization bound, which is intuitively a surrogate of the model complexity. We apply the proposed bound on Bayesian deep nets and empirically analyze the effect of this new loss-gradient norm term on different neural architectures.

On the Importance of Gradient Norm in PAC-Bayesian Bounds
Itai Gat', Yossi Adi Alexander Schwing', Tamir Hazan
Technion
2 FAIR Team, Meta AI Research
The Hebrew University of Jerusalem *University of Illinois at Urbana-Chaman crhama-Champaign
Abstract
Generalization bounds which assess the difference between the true risk and the empirical risk have been studied extensively. However, to obtain bounds, current techniques use strict assumptions such as uniformly bounded or Lipschitz loss function. To avoid these assumptions, in this paper, we follow an alternative approach: we relax uniform bounds assumptions by using on-average bounded loss and on-average bounded gradient norm assumptions. Following this relaxation, we propose new generalization bound that exploits the contractivity of the log- Sobolev inequalities. These inequalities add additional loss-gradien norm term to the generalization bound, which is intuitively a surrogate of the model complexity. We apply the proposed bound on Bayesian deep nets and empirically analyze the effect this new loss bass-grradent norm term on different neural architectures.
Introduction
Deep neural networks are ubiquitous across disciplines and often achieve state-of-the-art results. Despite the fact that deep nets are able to encode highly complex input-output relations, in practice, they do not tend to overfit [Zhang et al., 2016]. This tendency to not overfit has been investigated in numerous works on generalization bounds. Indeed, many generalization bounds apply to composite functions specified by deep nets. However, most of these results assume that the loss function satisfies various assumptions, such as uniformly bounded [Alquier et al., 2016], Lipschitz [Alquier et al., 2019], aub-Gaussian [Bégin et al., 2016, Alquier and Guedj, 2018], sub-gamms [Germain et al., 2016], or self- soffdoondiig [Haddouche et al., 2021]. Unfortunately, these assumptions exclude many state-of-the-art deep nets, whose properties cannot be statistically determined per data distribution.
In this work, we take a different route and use the deep net gradient- Bayesian generalization. For this purpose, we treat the loss function as a random function that is generated by a high-dimensional probability space, which is governed by the generating process of the training data. This view allows to introduce new tools from high-dimensional probability theory that relate measure concentration to the expansion of the loss function, as determined by its gradient-nome nore [van Handel, 2016].
measure for PAC-
We begin by adjusting theorem (Herbst theorem) to estimate the measure concentration via the entropy of the loss function (Lemma 3.1). We then derive a term for the entropy tailored to the multiclass classification setting (discrete labels which condition Gaussian data), (Lemma 3.2). Finally we bound the entropy using log-Sobolev inequality (Lemma 3.3).
Importantly, these steps result in PAC-Bayesian bound which depends the norm of the gradient of the loss. Intuitively this norm measures the complexity of the loss function, i.c., the model. Different from prior work, the bound hence depends on the structure of the employed model and its gradient
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

norm. This result admits bound for multi-class classification with linear models and Lipschitz loss (Theorem 3.4), extending result of Alquier al. [2016]. and multi-class classification with deep nets when the loss function and its gradient are on-average bounded (Theorem 3.5 and Theorem 3.6). The assumptions for the derived bound (Theorem 3.5 and Theorem 3.6) are closer to present-day deep net practice emphasizing the importance of the gradients in learning: in addition to the critical importance of controlling the loss gradient to better optimize deep net, the gradient-none also controls the generalization of the loss function (as measured by the deep net).
Our contributions: (I) We present a new PAC-Bayesian generalization bound that depends on the gradient-noni norm of the loss function. Consequently, we replace the uniform bound assumptions with an on-average bounded loss and an on-average bounded gradient norm. This answers an open problem raised by Bartlett et al. [2017a] (cf. Sec. 4) in the PAC-Bayesian setting. This result is presented in Theorem 3.5. (2) We extend the PAC-Bayesian bounds of Alquier et al. [2016] for the hinge-loss to any linear model with a Lipschitz loss function. This result appears in Theorem 3.4. (3) We empirically demonstrate that our bounds produce tighter generalization performance than the baseline methods. This helps to bridge the gap between theory and practice towards tighter bounds that have more realistic assumptions that match modern deep nets.
2 Background
Generalization bounds provide statistical guarantees on learning algorithms. They assess how the learned parameters w of model perform on test data given the model's result on the training data S = {(21, vi),..., (Im, 3m)}, where 2; is the data instance and yi is the corresponding label. The performance of the parametric model measured by a loss function f(w, x; y)- The risk Ln(w)= = (x fwc, v)
y) of this model is its average loss when the data instance and its label
are sampled from the true but unknown distribution D. The empirical risk is the average training set loss (sw 1. Em f(w, 2w, k.)
2.1 PAC-Bayesian bounds
PAC- AAC-Bayesian theory bounds the expected risk Ewnng (D(w) of a model when its parameters are averaged over the learned posterior distribution 9. The posterior distribution is learned from the training data S. In our work, we start from the following PAC- -ay-eaasi bound:
Theorem 2.1 (Alquier al. [2016)). Let KT(glpp)
f q(w) log(g(w) (ilg((/w/p(())) )(w))) be the Kl-- divergence between two probability density functions p. 4- For any > O, for any E (0, 1) and for any prior distribution p. with probability at least 1 5 over the draw of the training set S, the following holds sinultaneously for any posterior distribution
BLo S [L 1 IC((2 + KI(glD) log(1 (10))
where C(A, p) & log (emepps---m/(elloooo
Unfortunately, the complexity term C(A, p) of this bound is challenging to compute exactly in general: it requires to integrate (and maximize if the log-sum-exp trick is used) over large parameter and data sub-gamma loss functions,
spaces. Using different assumptions, e.g., learning with sub-Gaussian learning with specific losses, etc., it is possible to analytically bound the complexity term C(A, p) as we briefly illustrate next.
We say that a loss function l sub-Gaussian with variance v/2 if it can be described by a sub-Gaussian random variable, i.c., if its momeettnt generating function is upper bounded by 1 //2
log ((rra) je M(b(()) ((
(
Alquier et al. [2016] use Hoeffding's lemma to show that uniformly bounded loss function, namely S E(ue, x. v) & B is a sub-Gaussian loss function with variance B² and hence derive from Theorem 2.1 and Equation (2) PAC-Bayesia bound for bounded loss functions.

---

2.2 Measure concentration in high-dimension
However, the Hoeffding lemma, which asserts the sub-Gaussian property bounded loss function, treats the value of the loss as a real-valued random variable L(w, æ, y) while entirely ignoring the high-dimensional probability space (z. y) that generates this random value. Said differently: any properties of function F transforming the data (I.y) are ignored, and all functions F are treated identically. This is sub-optimal. In the following, we describe an entropy method that utilizes the measure concentration phenomena that exist in the nigh-dimensional random space of (ar, v). cf. Chapter of van Handel [2016]. The entropy of a non-negative random variable F is
[n A R[F log F] - E[F) log [F]].
The Herbst theorem connects (nn to measure concentration by providing bound on the log- moment generating function, as summarized next.
Theorem 2.2 (Herbst), Suppose that for all X the following bound for the entropy holds:
X²0² Be
EntleAF]
(4)
Then the scaled log-moment generating function which we also refer to as (b)) is bounded as follows:
(A)
x log
(B(eAR) S
<E|F]+
oo
(5)
Proof.
First, we note that due to the fundamental theorem of calculus
((A)
(0)
(b(())
da.
(6)
a
Using l'Hopital rule, we verify that lima-u M(x) FF which yields the first term of the bound. The following identity
((a) α
Ent [eFF a² E eaar
which is obtained from the definition of (aa)/ar and where (.)' refers to the derivative w.r.t. a. derives the theorem after plugging Equation (7) into Equation (6) and using Equation (4) to bound the integral.
Importantly, note that this is step forward. Different from classical PAC-Bayesian bounds discussed in Section 2. which use the fact that uniformly bounded loss function sub-Gaussian, the Herbst theorem asserts that any random variable that satisfies Equation (4) is x² sub-Gaussian.
To take advantage of this step, in this work, benefit from the (modified) log- Sobolev inequality (LSI) for Gaussian random variables, which bounds the entropy.
Theorem 2.3 (Gaussian Jog-Sobolev inequality (LSI), Gross [1975]). Let Zi...., Za independent Gaussian random variables, i.e., Z, ~ N N o,). We then have
Ent (2
(.m...aa)))) Za)]
1 Evilo Vzf(Zi,... 2 e (Z).....a))
(8)
2
where a Vzf(Z,,.., Za) is an element-wise multiplication.
Proof. See supplementary material.
One can apply the LSI to the Herbst theorem attain measure concentration bounds for high- dimensional Lipschitz functions: a differentiable function f(z1, Zd) is said to be g-Lipschitz if (f(2,.... 2a) f( 21i1 I gl|2 2'I1, or equivalently if / 24)ll S g for any 2i.... Zd. The LSI for g- g-Lipschitz functions with s Ei= o? variance reduces to the bound Ent ( < X²g'e (eee.(e......))),, which in turn provides a bound on the log-moment generating function of f(z,,.., 2a) using Theorem 2.2.
3

---

3 PAC-Bayesian bounds with log-Sobolev inequalities
Different from prior work, we suggest measuring the generalization of neural nets by taking into account the expected gradient-norm of the loss function with respect to the data generation process.
For this, note that classical PAC-Bayesian generalization bounds depend measure concentration, as described in Theorem 2.1 and Equation (2.1). However, the sub-Gaussian assumption used in classical PAC-Bayesian generalization bounds seamlessly bypasses the measure concentration phenomena. This is too restrictive and enforces all loss functions, and consequently, all neural nets, have the same measure concentration phenomena.
Instead, we first use the Herbst theorem to estimate the measure concentration by taking into account the entropy. In second step allows us to consider the high-dimensional probability space (I, y) ~ that controls the measure concentration of the loss function l(w, æ; y). This differs from the use of a crude worst-case bound on the loss function (e.g., f(w, x, y) S B for any w, y) in classical PAC-Bayesian generalization bounds, which entirely ignores the neural that generates the loss function.
Log-Soboley inequalities (LSSI) bound the entropy, which
Herbst theorem to estimate measure concentration: As just discussed, we first adjust the Herbst theorem to setting:
Lemma 3.1 (Herbst). For any X >> O we huve
Ent (e a(m.a))))
log [SsD (eMLLole) X
a Ep -of(maa da.
(9)
Proof. First, we use the statistical independence of the training samples to decompose the moment generating function
M (A) & (
(10)
as follows:
ES-Dm [oNLL(
(LD(w)) ESnDm [e
(11)
(w)(w)
E (a:ii) (e (-
(12)
iml
)
cLL M
(13)
m
We apply the differential representation Theorem 2.2 with (/A) = log M (A) and obtain:
(AA)
1/¹ v((a) ( da
(0)
Lo
Ent le al(w)))))
a ED le al(w da B(,,))-D(((,,z,,))) (14)
X
Since M (A/m) = (d/m) and E( (ww, x v)) = (w(,,, we obtain from Equation (14) the identity
m A A
Rue paepleatkw....) Epple uct do (LD(w)
M
(15)
which completes the proof when being combined with Equation (13).
2) Entropy bound: In the second step we now aim bound the entropy Entple ad(ux)))))
Since we focus on the classification setting, the label y is discrete. We further assume that for any (discrete) label y its corresponding data x (I1, ...; m2) is generated from d-dimensional Gaussian distribution that consists of i.i.d. Gaussian random variables I; ~ N (MHy,, of,)). We denote this Gaussian distribution by ~ N( oz) and abbreviate it by Ng. The data generation distribution of æ is the Gaussian mixture model D = Σy Dy -y, where D, is the marginal distributions of 'D w.r.t y.
We begin by decomposing the entropy of the (exponent) of the loss function according to the labels:

---

Lemma 3.2. Let D = Dy.Ne Ny be mixture model, whose label marginal probabiliries are D, and set fan (2, (), =c al(ww,2))) One can show that
Ent = Σ Dy Ent,, [fo] + EULD, (Br-N,, [[u]]
(16)
Proof. From the definition of the entropy of function E(w,, x. y) with respect to its measure (x, v) DD we have
Ent [f] A ED fu (a,, v) log (w v) - (Ev(fu (2, vi]) log [Ep(fu(( v))))
(17)
The result is
attained by Ey-D (E [f (z, v)l) log EE.-N,Lfuaa y)]). The result then follows from the defini- tions of entropies of the mixed components, while setting glv) = EE [fw (x,,))) Specifically, have
adding and subtracting the quantity
Euty, [fw]
Ew, v) log fo (xx,))]= (IGN,LFu(a w)l) log (EW, [f, (18)
Entp, [g]
loglo()))
Σ 21
Dog(v)
log E
(19)
It is important to note that the number of components in the mixture model is not limited. Such Gaussian mixture model can approximate any smooth density [Titterington al., 1985, Scott, 1992. Goodfellow et al., 2016].
Next, we the LSI to bound the loss function entropy using its expected gradient- norm with respect to the data generation process.
Lemma 3.3. Assume that the loss per label is balanced, namely Em-N LerVVeleeeelee -a((w..))) c for every w and then under the conditions of Lemma 3.2.
log ESSDD (cMLo()))Ls(ww)))
1 AD [loo Vzl(w, v. y)12 Eple Eple-a((w.a..)) da (20)
$ 2
Proof. Lemma 3.2 asserts that Eutple (attlll-a(waaay is composed of the entropies Enty, (e and Entp, [Ew,N, []] The assumption Ez-N, I, -a((waa))]] e implies the identity Entp, BEW,, [c-al(m
Entp,/c 0. Thus Entple-al(wan
Σ, Dy Entar, (.)a We use Theorem 2.3 to bound
1 a² En [ll, F,l(w,,,))11 - al(wa).))]]
Enty, [e [e-a(((...)) S
(21)
2
Combination with Lemma 3.1 concludes the proof.
Note, the per-label loss balance originates from bounding the term Ent [E [fw]] in Lemma 3.2. If the loss is per-label balanced, the entropy equals zero. In fact, the per-label balance can be relaxed by assuming that the loss is per-label bounded within an amplitude (Sec. 3.16 in van Handel [2016]).
Notably, the above lemma is more theoretical than practical: to estimate it in practice, one needs to avoid integrating over a. Nevertheless, it serves as an essential generalization of the Herbst theorem and the LSI that is useful to derive PAC-Bayesian bounds for various settings. We look at these different settings next.
3.1 Linear models
In the following, we consider differentiable and Lipschitz loss functions' over linear models in a multi-class setting of the form E(w, x, y) A &(W xr, y). Included in these assumptions are the popular NLL loss log p(y|z, w) = (Wwx), + log Σ (W=z)s) that is used in logistic regression and the multi-class hinge loss max)((Wz))
(Wx), + [y # ø]} that is used in support vector machines.
It is enough to assume that the loss function is continuous and almost everywhere differentiable with respect
5

---

Theorem 3.4. Let f(w, v. v) ((Wx,y) be differentiable loss function over x = (Z1....,Td)) Id) and k classes y {l.... k}, with Lipschitz constant g, i.e., V y)ll 9. Consider Gaussian prior distribution (0, o2) Under the conditions of Lemma 3.3, for any 0 < X S v TTt/////00000 10/90p0 and 5 E (0, 1}, with probability at least 1 - over the draw of the training set S, we have
EwwglLD(u)) S (EwnlLs((W)) + kd 4/3) + pL(g))p) + log(1/6)
(22)
À
Proof. This bound is derived by applying Lemma 3.3. We begin by realizing the gradient of É(W xr y) with respect x. Using the chain rule, Vzl(Wx, y) W V Wwee(War wx, y). Hence, we obtain for the
gradient norm [V x; y)1 & I WV (Ww((W, y) 2 Σn Ej= w 4
S g2 Σy= j=1 w
v.
Plugging this result into Lemma 3.3, we obtain the following bound:
L0a e (-al(wra))) da S "g9
d
ED ae(ww)))))
ED |lo Vi(w,,
M(a)
W
Mi
M(a)
da.
Since M(a)= - ED [e-ae(waa.)] the ratio in the integral equals one and the integral Jo" da Finally, whenever Ago vm/4 we follow the Gaussian integral and derive the bound
2 ? log (Bwap e En, wi:s
kd log
m (Vm-
m mm44 kd -log( (oo((/43)).
(23)
Finally, we obtain Equation (22) by plugging the above into Theorem 2.1. detailed proof provided in Appendix.
Notice, the linear case, the gradients the model are a function of W. Thus they are not uniformly bounded for every W. Since assume the loss to be Lipschitz, we can bound C)),),, and by further assuming bounded X, and Gaussian W, we obtain kd log(4/3).
Theorem 3.4 provides PAC-Bayesian bound for classification using the NLL loss. This extends the result of Alquier et al. [2016] for binary hinge-loss to the multi-class hinge loss (cf. [Alquier et al., 2016], Sec. 6).
While the above result can be applied to deep nets, obtaining value for the bound requires computing the Lipschitz constant, which is an NP-hard problem even for two-layer neural nets [Virmmux and Scaman, 2018]. Moreover, common Lipschitz constant approximation algorithms tend overestimate the constant and are exponential in the network's 's depth [Virmaux and Scaman, 2018, Combettes and Pesquet, 2019].
3.2 Non-linear models
Sadly, the bound proposed in the previous sub-section cannot be applied to non-linear loss functions since their gradient-norm is not bounded, as evident by the exploding gradients property in deep nets. To mitigate this, we suggest utilizing on-average bounded losses and gradients. Formally, one can show the following:
Theorem 3.5. Consider smooth loss functions that are on-average bounded, i.e., for every the
following holds: Ep ((w,x,y) I and Ey [[] x, y) S 9. Under the conditions of Lemma 3.3 for any 0 < X S m and E (0, 1), with probability at least over the draw of the training set S, we obtain
+ 2m + KL(gllp) + log(1/0)]
BwngLLD(w)) S Buwg(Ls(w))
(24)
Proof. This bound is derived by applying Lemma 3.3 and bounding fo -ood(..r.))) da S c.. We M(a)
derive this bound in three steps: First, from É(w, x, y) 2 we obtain e -0((,,2.)) < 1. Then, we lower
bound M(a) 2 (1)) for any S a S A/m. Also, since f(w, 2r y) 2 0 the function e-dl(w.a.v)
monotone in within the unit interval and M (a) > (1) for any < 1. Lastly, the assumption

---

Lanour mnpeel
Lenor mode Jana
Expectio Nro
2layes
0.04
MLD
CKM
Layer CNM
XX3 0.33 a. Tean Exes
1252
025
2.00 9-11
23%
(a) MNIST
(b) CIFAR
(c) MNIST
(d) CIFAR
Figure (a-b) Ed ED[ (o[((w y)] as function of different priors for the model parameters. (c-d)
ED [IIV, x, y)ll function of the different variance levels of the prior distribution. Results are reported for MNIST (a, c) using MLPs, and CIFARIO (b, d) using CNNs.
Ep f- 2, y) 2 b and the monotonicity of the exponential function result in the lower bound 6 [ww,y, -
From convexity of the exponential function we have Ep (=((w,)))) 2 [Fo(-(tw...)), Combining these bounds and replacing Ep [lloy [ x, v) with go we obtain the upper bound
X²e-go
c(A,p) <
(25)
2m
Finally, we obtain Equation (24) by plugging Equation (25) into Theorem 2.1. A detailed proof is provided in Appendix.
In contrast to prior work that assumes the loss function to be uniformly bounded, i.e., f(w, y) B for every w, x. y [Alquier et al., 2016), in Theorem 3.5, we assume an on average bounded loss and an average bounded gradient norm, i.e., Ep (ww, x. y) I b and Ep [[VE(w, 8) S g for all w.
The above bound corresponds to open problem raised by Bartlett et al. [2017a], wondering about existence of generalization bounds that assume on-average bounds on the loss and/or the gradient norm. Nevertheless, this bound is more theoretical than practical, as it enforces global on-average bounds 2 Ep f(w, 2, y) and g 2 Ep [[ xz 8)
For a more practical perspective, in the following, we consider the on-average loss and gradient norm be functions of the model parameters.
Theorem 3.6. Consider smooth loss functions and the conditions of Lemma 3.3. For any 0 < X S m we obtain
Az ((w,,)))) Ep [[[ v. o
C(A.p) S log
Ewap
exp
(26)
2m
The proof of this Theorem follows the proof of Theorem 3.5. However, this case, we cannot remove the expectation over the prior distribution since we assume the bound over the loss and gradients to depend on w.
The above derivation upper bounds the complexity term C(A, p) by the expected gradient- of the loss function, i.e., the flow of its gradients through the model's architecture. We show empirically that the rate of the bound À can be as high as m, dependent on the gradient-norm. This is a favorable property since the convergence of the bound scales 1/X. Therefore, one would like to avoid exploding gradient-norms, which effectively harm the true risk bound. While one may achieve a fast rate bound by forcing the gradient-norm to vanish rapidly, practical experience shows that vanishing gradients prevent the deep net from fitting the model to the training data when minimizing the empirical risk. In our experimental evaluation, we demonstrate the influence of the expected gradient-norm on the bound of the true risk.
4 Experiments
In this section, we evaluate our PAC-Bayesian bounds experimentally, both for linear and non-linear models. We begin by verifying assumptions, comparing the proposed bound to prior work, and
7

---

Layers MLF
0.005
Layers
Layers
0.032
Layers CNN
CFFAR
5.05
Lagers
4 Layers CNN
6.42
Layers NLP
0.01
0.023
Layers CNN
0.003
0.001
0.012
0.002
0.000
13000
20030
20103
50200
50300
23000
23000
30020
40000
30002
Network Sopth
(a)
(b)
(c)
Figure 2: Complexity study: In (a-b), we present the complexity term as a function of A. Furthermore, in (c), present the complexity term C(A, p) as function of the network depth for both CIFAR and MNIST. Note, the bound on the complexity term decreases as a function of the depth of the network.
estimating its predictive generalization capabilities. Next, we study the behavior of the complexity term p)),p) for different architectures, both for linear models and deep nets. We conclude the section with an evaluation of the effectiveness of the proposed bound at predicting generalization performance and analyzing its different components during optimization. All reported results were averaged over three runs using different seeds. The complete experimental setup can be found in the Appendix.
Verifying assumptions: In Lemma 3.3 we assume that the loss per label is balanced. To verify that this assumption holds, we use ten different architectures (ResNet18, PreActResnet18 18, GoogLeNet, VGGII, VGG13, VGG16, VGG19, DenseNet121, MobileNet, EfficientNeiBO) on CIFARIO and CIFAR100 (Krizhevsky, 2009, Simonyan and Zisserman, 2014, Szegedy et al., 2015, He et al., 2016 6, Huang et al., 2017, Howard al., 2017, Tan and Le, 2019]. The maximum standard deviation across the labels is 0.022, while the mean value is 4.605. Hence. it is evident that this assumption holds in practice. In Theorem 3.6 we assume that the loss is unbounded but is on-average bounded by a function depending w. i.c., ED f(W, 2, y) S b(w). The results to verify this for MNIST [LeCun et al., 1998] and CIFARIO are provided in Fig. 1a and Fig. 1b. We observed that until of = 0.1, the loss is on-average bounded by ~ 2. Moreover, for de < 0.01, the on-average loss bound is about 1, and its effect on the complexity term C(A, p) is minor. This validates empirically our assumptions that the on-average bounds Ep E(w, 1r, y) are small although max w.y ((w, æ, y) much larger (see Tab. for its impact on the generalization).
Complexity of neural nets:
We now turn to estimate our bounds over C(A,p) p). both for linear and non-linear models. Recall that À determines the rate of the generalization bound, and one would like to set 0 X I m large possible while C(p, A) to be small possible. As the bound on C(X,p) p) is controlled by the expected gradient-norm ED [I] //V((w x, })] we present in Fig. Ic and Fig. Id the expected squared gradient- nrom as a function of different variance levels for the prior distribution p over the model parameters, again using both MNIST and CIFARIO data.
We note that the linear model has the largest expected gradient-norm. Further, note that the deeper the network, the smaller its mradient-norm. As result, deeper nets can use larger values of À for the generalization bound. Thus, we present our complexity bound as a function of X in Fig. 2a and Fig. 2b. Note, the complexity term C(A,p) reaches its minimum around X m. Fig. 2c studies the effect of network's depth on the complexity term. We observe that, as expected based on the earlier plots, deeper networks have lower complexity term. We attribute this phenomenon to vanishing gradients which create a contractivity property that stabilizes the loss function, i.c., reduces its variability. However, this comes at the expense of the expressivity of the deep net, since deep nets with vanishing gradients cannot the training data in the learning phase.
Comparison to prior PAC-Bayesian bounds: We compare the proposed bound to Alquier et al. [2016] (bounded version). Germain al. [2016], and Dziugaite and Roy [2017] on both MNIST and CIFAR. Unlike our bound which assumes the expected loss to be bounded, both Alquier et al. [2016] and Germain et al. [2016] assume the loss to be uniformly bounded by a constant B. Hence, for fair comparison, we estimated B to be the maximum and average loss over the training set and use it to bound the maximum and expected loss respectively. Results are summarized in Tab. Notice, our bound produces tighter generalization bounds compared to the baseline methods for both datasets.
8

---

Table 1: Comparison of the full PAC-Bayesian generalization bound versus Alquier et al. [2016]. Germain et al. [2016], and Dziugaite and Roy [2017]. For MNIST we use three layer fully connected model, while for CIFAR-I0 10 we use a CNN with three convolutional layers. In all settings we used À m and of 0.01.
DATASET
ALQUIER
GERMAIN
DZIUGAITE
OURS
MNIST
3.36 1 SE-4
1.86 1 4E-3
0.41 1 3E-4
0.04 1 5E-4
CIFAR-10
4.81 1 IE-2
8.37 9E-2
0.05 1 4E-3
5 Related work
Generalization bounds for deep nets were explored in various settings. VC-theory provides both upper bounds and lower bounds to the network's VC-dimension, which are linear in the number of network parameters [Bartlett al., 2017b, 2019]. While VC theory asserts that such model should overfit as it can learn any random labeling (e.g.. [Zhang et al., 2016)), surprisingly. deep nets generally do not overfit.
Rademacher complexity allows to apply data-dependent bounds to deep nets [Bartlett and Mendelson, 2002, Neyshabur et al., 2015, Bartlett et al., 2017a, Golowich et al., 2017, Neyshabur et al., 2018]. These bounds rely on the loss and the Lipschitz constant of the network and consequently depend on product of norms of weight matrices, which scales exponentially in the network depth. Wei and Ma [2019] developed a bound over the gradient-norm of training examples. In contrast, our bound depends average quantities of the gradient-norm. Thus we answer open question of Bartlett et al. [201 [a] about the existence of bounds that depend on average loss and average gradient-norm albeit in PAC-Bayesian setting. PAC-Bayesian bounds that use Rademacher complexity have also been studied [Kakade et al., 2009, Yang et al., 2019].
Stability bounds may be applied to unbounded loss functions and in particular to the negative log- likelihood (NLL) loss [Bousquet and Elissceff, 2002, Rakhlin et al., 2005, Shalev-Shwartz et al., 2009, Hardt et al., 2015, Zhang al., 2016]. However, stability bounds for convex loss functions, e.g., for logistic regression, do not apply to deep nets since they require the NLL loss to be a convex function of the parameters. Alternatively, Hardt al. [2015] and Kuzborskij and Lampert [2017] estimate the stability of stochastic gradient descent dynamics, which strongly relies on early stopping. This approach results in weaker bounds for the non-convex setting. Stability PAC- MAC-Bayesian bounds for bounded and Lipschitz loss functions were developed by London [2017]. Li et al. [2019] utilized the log-Sobolev inequality bound the KL divergence under the PAC-Bayesian setting while assuming a bounded loss function. In contrast, we assume an unbounded loss function and a Gaussian prior distribution over the model weights. The latter allows us to compute the KL divergence. Holland [2019] studies PAC-Bayesian learning guarantees for heavy-tailed losses. Haddouche et al. [2021] relax the boundness assumption by modifying the range of the loss to depend on each predictor. Differently, through the log- log-Sobolev inequality, our bound relies on the expected gradient-norm of the loss function, which may be unbounded as well.
PAC-Bayesie Bayesian bounds were recently applied to deep nets [McAllester, 2013, Dziugaite and Roy, 2017, Neyshabur al., 2017, Pérez-Ortiz et al., 2021]. In contrast to our work, those related works all consider bounded loss functions. An excellent survey on PAC-Bayesian bounds was provided by Germain al. [2016]. Alquier et al. [2016] introduced PAC-Bayesian bounds for linear classifiers trained with a hinge-loss by explicitly bounding its moment generating function. Dziugaite et al. [2021] investigate the role of data in learning a PAC-Bayesian prior. Closely, Foong et al. [2021] study the tightness of PAC-Bayesian bounds for small datasets. Alquier et al. [2012] provide an analysis for PAC-Bayesian bounds with Lipschitz functions. Our work differs as we derive PAC-Bayesian bounds for non-Lipschitz functions. Work by Germain et al. [2016] is closer to our setting and considers PAC-Bayesian bounds for linear models and quadratic loss functions. In contrast, our work considers the multi-class setting and non-linear models. PAC-Bayesian bounds for the NLL loss in the online setting were put forward too [Takiimoto and Warmuth, 2000, Banerjee, 2006, Bartlett et al., 2013, Grünwald and Mehta, 2017]. The online setting does not consider the whole sample space and therefore is simpler to analyze the Bayesian setting. Recently, PAC-Bayesian generalization bound for meta-nc was proposed [Rothfuss et al., 2020, Amit and Meir, 2018, Farid and

---

Majumdar, 2021, Ding et al., 2021]. In contrast to our work, Amit and Meir [2018] and Farid and Majumdar [2021] focus on bounded loss functions while Rothfuss al. [2020] assume the loss function to be sub-gamma.
PAC-Bayesian bounds for the NLL loss function are intimately related to learning Bayesian infer- ence Germain et al. [2016]. Recently, many works applied various posteriors in Bayesian deep nets. Gal and Ghahramani [2015], Gal [2016] introduce Bayesian inference approximation using Monte Carlo (MC) dropout, which approximates a Gaussian posterior using Bernoulli dropout. Srivastava et al. [2014], Kingma al. [2015] introduced Gaussian dropout, which effectively created Gaussian posterior that couples the mean and the variance of the learned parameters and explored the relevant log-unin log-uniform priors. Blundell et al. [2015], Louizos and Welling [2016] suggest taking a complete Bayesian perspective and learning the mean and the variance of each parameter separately.
Stochastic gradient Langevin dynamics (SGLD) bounds [Pensia et al., 2018, Mou et al., 2018, Negrea et al., 2019, Haghifam et al., 2020] suggest bounding the generalization gap by investigating the dynamics of the parameters through Langevin dynamies and Fokker-Pland equations. Broadly, the Fokker-Planck equation defines a Markov process, and these works measure the KL-divergence between prior and posterior distribution of this process in the parameter space using gradient norms of the parameters. Differently, our work utilizes the Herbst theorem to measure the KL-divergence (in the form of functional entropy) between prior and posterior in the imput space. This distinction leads to computation of the gradients with respect to different quantities, i.e., parameters vs. input data.
6 Discussion and future work
In this study, we present new PAC-Bayesian generalization bounds that depend on the gradient-norm of the loss function. We explore their properties in our experimental validation in various deep learning settings, reinforcing the importance of gradients in contemporary deep nets. Our framework allows for new PAC- AAC-Bayesian bounds that assume an on-average bounded loss and an on-average bounded gradient norm assumption. These findings answer open problem raised by Bartlett et al. [2017a] under the PAC-Bayesian setting. Moreover, we extend the current generalization bounds proposed for the hinge-loss to any linear model with Lipschitz loss function. Finally, empirically show that our bounds produce tighter generalization performance than the bascline methods. These results are another step towards bridging the gap between theory and practice while having more realistic assumptions for modern deep nets.
Our framework can be extended in different directions. Log-Sobolev inequalities (LSIs) are intimately related to hypereontractivity. Our generalization bounds also imply that deep nets hyper-contracts their input and therefore generalize. While the relation between generalization and hypercontractivity under explored, with the small-ball theorem as a notable exception [Lecué and Mendelson, 2017, Mendelson, 2014], we believe it is fundamental concept in contemporary deep nets that require further research. Additionally, our framework focuses on bounding the complexity term. It is interesting future work to also consider the KL term.
We assume that the labels are balanced with respect to the loss, or equivalently, the influence of all labels is equal. The theory of influence of discrete functions is well-developed and very relevant to LSIS, hypercontractivityy and measure concentration, and further investigation on its relation to generalization is desired [O' Donnell, 2014].
Acknowledgements: This work is supported in part by NSF under Grant 2008387, and, BSF under Grant # 2019783.
References
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv: 16/ 1611500300 2016.
Pierre Alquier, James Ridgway, and Nicolas Chopin. On the properties of variational approximations of gibbs posteriors. JMLR. 2016.
Pierre Alquier, Vincent Cottet, and Guillaume Lecué. Estimation bounds and sharp oracle inequalities of regularized procedures with lipschitz loss functions. The Annals of Statistics, 2019.
10

---

Luc Bégin, Pascal Germain, François Laviolette, and Ccan-Francis Roy. Pac- beso-bayeian bounds based on the rényi divergence. In Artificial Intelligence and Statisties. PMLR, 2016.
Pierre Alquier and Benjamin Guedj. Simpler pac-bayesian bounds for hostile data. Machine Learning, 2018.
Pascal Germain, Francis Bach, Alexandre Lacoste, and Simon Lacoste-Julien. Pac-bayesian theory meets bayesian inference. In NeurIPS, 2016.
Maxime Haddouche, Benjamin Guedj. Omar Rivasplata, and John Shawe-Taylor Pac-bayes un- leashed: generalisation bounds with unbounded losses. Entropy, 2021.
Ramon van Handel. Probability high dimension, December 2016.
Peter L Bartlett, Dylan Foster, and Matus J Telgarsky. Spectrally Spectrally- normalized margin bounds for neural networks. In NewrIPS, 2017a.
Leonard Gross. Logarithmic sobolev incqualities. American Journal of Mathematics, 1975.
D.M. Titterington, P.S.D.M. Titterington, S.A.F. M, A.F.M. Smith, U.E. Makov, and John Wiley Sons. Statistical Analysis of Finite Mixture Distributions. Wiley, 1985.
David W Scott. Multivariate density estimation: theory, practice, and visualization. John Wiley & Sons, 1992.
lan Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: analysis and efficient estimation. NeurIPS, 2018.
Patrick I. Combettes and Christhit Pesquet. Lipschitz certificates for neural network structures driven by averaged activation operators. arXiv preprint arXiv: 190::00030004 2019.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint 1eXXiv:1009.14 2014.
Christian Szegedy, Wei Liu, Yangging Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions, In CVPR, 2015.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. CVPR, 2016.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In CVPR, 2017.
Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. Mobilenets: Efficient convolutional neural networks for mobile vision applications. arXiv preprint ArXiv::704.00 704.04861, 2017.
Mingxing Tan and Quoc Le. Efficientnet: Rethinking model scaling for convolutional neural networks. In ICML, 2019.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. 1998.
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint 173/v:1703.11008, 2017.
Peter L. Bartlett, Nick Harvey, Chris Liaw, and Abbas Mehrabian. Nearly-tight ve-dimension and pseudodimension bounds for piecewise linear neural networks. arXiv preprint arXiv: 1703.02930 2017b.

---

Peter L. Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve-dimension and pseudodimension bounds for piecewise linear neural networks. JMLR, 2019.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities Risk bounds and structural results. JMLR, 2002.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, 2015.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. arXiv preprint arXiv:1712.06541 2017.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. Towards understanding the role of preeeerramtiinntooonn in generalization of neural networks. arXiv preprint arXiv:1805.1200 12076, 2018.
Colin Wei and Tengyu Ma. Data-dependent sample complexity of deep neural networks via lipschitz augmentation. In NewrIPS, 2019.
Sham M Kakade, Karthik Sridharan, and Ambuj Tewari. On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. In NeurlPS, 2009.
Jun Yang, Shengyang Sun, and Daniel M Roy. Fast-rate pac-bayes generalization bounds via shifted rademacher processes. In NeurlPS, 2019.
Olivier Bousquet and André Elisseeff. Stability and generalization. JMLR, 2002.
Alexander Rakhlin, Sayan Mukherjee, and Tomaso Poggio. Stability results in learning theory.
Analysis and Applications, 2005.
Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Stochastic convex optimization. In COLT, 2009.
Moritz Hardt, Benjamin Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. arXiv preprint arXiv:1 2015.
Ilja Kuzborskij and Christoph H Lampert. Data-dependent stability of stochastic gradient descent. arXiv preprint arXiv: /703 2017.
Ben London. pac-bayesian analysis of randomized learning with application stochastic gradient descent. In NeurlPS, 2017.
Jian Li, Xuanyuan Luo, and Mingda Qiao. On generalization error bounds of noisy gradient methods for non-convex learning. arXiv preprint arXiv:1902.00622 2019.
Matthew Holland. Pac-bayes under potentially heavy tails. NeurIPS, 2019.
David McAllester. A pac-bayesian tutorial with a dropout bound. arXiv preprint arXiv: 1307,213
2013.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nathan Srebro. pac- bayesian approach to ppectrally-normalizee margin bounds for neural networks. arXiv preprint /707 2017.
Maria Pérez-Ortiz, Omar Rivasplata, John Shawe-Taylor, and Csaba Szepesvári. Tighter risk certifi- cates for neural networks. JMLR, 2021.
Gintare Karolina Dziugaite, Kyle Hsu, Waseem Gharbieh, Gabriel Arpino, and Daniel M Roy. On the role of data in pac-bayes bounds. AISTATS, 2021.
Andrew YK Foong, Wessel P Bruinsma, David R Burt, and Richard E Turner. How tight can pac-bayes be in the small data regime? In NeurlPS, 2021.
Pierre Alquier, Olivier Wintenberger, et al. Model selection for weakly dependent time series forecasting, Bernoulli, 2012.
12

---

Eiji Takimoto and Manfred K Warmuth. The last minimax algorithm. In International Conference on Algorithmic Learning Theory. Springer, 2000.
Arindam Banerjee. On bayesian bounds. ICML, 2006.
Peter Bartlett, Peter Grunwald, Peter Harremoës, Fares Hedayati, and Wojciech Kotlowski. Hlorizon-independe optimal prediction with log-loss in exponential families. arXiv preprint arXiv:/305.4322 2013.
Peter Grünwald and Nishant A Mehta. A tight excess risk bound via a unified pac-hayesian- medemacchrr-hhtrkkv--me complexity. arXiv preprint crXiv:1710.07732, 2017.
Jonas Rothfuss, Vincent Fortuin, and Andreas Krause. Pacoh: Bayes-optimal meta-learning with pac-guarantees. arXiv preprint arXiv:2002.0555/, 2020.
Ron Amit and Ron Meir. Meta-learning by adjusting priors based extended pac-bayes theory. ICML, 2018.
Alec Farid and Anirudha Majumdar. Generalization bounds for meta-learning via pac-bayes and uniform stability. In NeurlPS, 2021.
Nan Ding, Xi Chen, Tomer Levinboim, Sehastian Goodman, and Radu Soricut. Bridging the gap between practice and pac-bayes theory in few-shot meta-learning. In NeurIPS, 2021.
Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty in deep learning. arXiv preprint (rXXv:1506.02.. 2015.
Yarin Gal. Uncertainty in deep learning. PhD thesis, PhD thesis, University of Cambridge, 2016.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way prevent neural networks from overfitting. JMLR, 2014.
Durk Kingma, Tim Salimans, and Max Welling. Variational dropout and the local reparameterizzaioo trick. In NeurlPS, 2015.
Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in neural networks. arXiv preprint 4rX15:1505.00444. 2015.
Christos Louizos and Max Welling. Structured and efficient variational deep learning with matrix gaussian posteriors. In ICLR, 2016.
Ankit Pensia, Varun Jog, and Po-Ling Loh. Generalization error bounds for noisy, iterative algorithms. In ISIT, 2018.
Wenlong Mou, Liwei Wang, Xiyu Zhai, and Kai Zheng. Generalization bounds of sgld for non-convex learning: Two theoretical viewpoints. In Conference Learning Theory, 2018.
Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel Roy. information-theoreti generalization bounds for sgid via data-dependent estimates. NeurIPS, 2019,
Mahdi Haghifam, Jeffrey Negrea, Ashish Khisti, Daniel M Roy, and Gintare Karolina Dziugaite. Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms. NeurIPS, 2020.
Guillaume Lecué and Shahar Mendelson. Regularization and the small-ball method ii: complexity dependent error rates. The Jourmal of Machine Learning Research, 2017.
Shahar Mendelson. Learning without concentration. In Conference on Learning Theory, 2014.
Ryan O' O'Donnell. Analysis of functions. Cambridge University Press, 2014.
13

---

Checklist
1. 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]
(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 experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as 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 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 (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
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 roe're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "iqZgWZoMNVe", "reviewer": "Reviewer_sAtx", "summary": "The paper studies the PAC generalization bound and relaxes the uniform bounds assumptions in literature by the on-average bounded loss and on-average bounded gradient norm assumption. Under this relaxed assumption, the paper derives new generalization bound related with the loss-gradient norm. The paper verified its effect empirically.\n", "questions": "The paper should be clearer about the assumption on the data, i.e., how to understand these assumptions and derived bound therein when the real data do not satisfy these assumptions.", "limitations": "See the later two parts of the weakness.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe paper relaxed an unrealistic assumption in previous PAC generalization bound. The relaxation is natural and interesting, providing a fine-grained view to improve existing results. The average gradient norm has been studied to reflect the generalization of the algorithm [1], and this PAC bound gives more theoretical evidence on the importance of the average gradient norm.\n\n[1] Understanding generalization error of SGD in nonconvex optimization\n\nIt uses clean mathematical language and explains the caveats clearly. Overall the presentation is very good.\n\nWeakness:\n\nThe assumptions on the data are strong (x Gaussian or mixture Gaussian, y label balance) in Section 3's entropy bound. It is not clear how critical these assumptions are in terms of deriving a meaningful bound.\n\n In the generalization bound, it considers the complexity term and ignores the KL term and empirical loss term. Only optimizing the complexity term may lead to some undesired behavior: \"one may achieve a fast rate bound by forcing the gradient-norm to vanish rapidly, practical experience shows that vanishing gradients prevent the deep net from fitting the model\". This hides the influence of the empirical loss and the KL divergence part.   It would be great if they can be jointly studied, i.e., trade-off the noise variance and lambda.\n\nThough non vacuous, the paper does not demonstrate the power of such generalization bound. It will be much more interesting if we can see how the generalization bound / numerically computed generalization gap changes according to the model architecture, data distribution, or label balance.\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": "AbFI8T6kqn", "reviewer": "Reviewer_RE5w", "summary": "The paper extends PAC-Bayes generalization literature by proving new generalization bounds. These bounds require (and depend on) the expected loss (and loss gradient norm) to be bounded, where the expectation is taken over the data distribution. In general, these assumptions on the bound on the loss and gradient have to be valid uniformly over the weight space, or when integrated over the prior on the weights (if computing such a quantity is possible). The bounds were derived for a data distribution that is a mixture of Gaussians. The authors also include an empirical section, measuring how the complexity terms appearing in the bounds change with a parameter lambda that appears in the bounds, as well as the depth of the network.", "questions": "Related work issues: the literature on information-theoretic approaches to generalization contains several papers that depend on gradient norms, an average deviations from the norms. The paper under submission is obviously related, and thus I believe a deeper comparison is needed. The authors should check a fairly large body of work, such as Negrea et al ‘19, Haghifam et al ‘20, Mou et al. ‘18, Pensia et al. ‘18.\n\nEmpirical evaluation / Section 4: \nSection 4 contains a paragraph on verifying assumptions, but there is no mention of the assumption that the data is sampled from a mixture of Gaussians. This is the key assumption used to derive the main result.\nThere is no plot directly comparing average gradient versus max gradient, which is the key distinction. \nFig 1 shows how the expected loss and loss gradient vary with sigma (prior variance). It looks like these quantities are reported at a fixed w (the one learned by SGD?). If so, the relevant quantity is the one where w is also random, and sampled from the posterior, and the expectation should be taken over w.\nGiven the issue with Figure 1, I would also like the authors to explicitly confirm that Table 1 reports average error of randomized classifiers.\n\nWhen discussing subgaussianity in Sec 2.1, and assumptions for Herbst theorem in Section 2.2,  the same letter sigma is being used, despite sigma referring to two different quantities (if i understand correctly). I found it a bit confusing at first, and wondered for some time whether 2.2 uses subgaussianity  in any way.\n\nTheorem 2.2 gives a bound on the log moment generating function that essentially looks like a bound for subgaussian random variables, but also has an extra term E[F]. For a subgaussian loss, what would sigma in Eq (5) look like?\n\nIt seems like Theorem 2.3 could have been stated for a single draw from a gaussian, given it’s use in the proof of Lemma 3.3.\n\n\nThe proofs for existing results (that are not derived by the authors) are included in the main text, but the proofs for new results are all in the appendix. I think the authors should at least include the outlines in the main text, and, if needed, shorten the other proofs.\n\nOther comments and minor issues:\nNotation in theorem 3.4 is unclear: does one need a bound on the loss gradient norm to hold uniformly over y? Or t (so w, and x, i suppose)?\nTheorem 3.5 what is the gradient w.r.t.? \nLine 15 “they do not tend to overfit” is not really accurate, depends on the exact definition of overfitting, what loss overfitting is being measured w.r.t., etc. The same holds for ~line 271.\nLines 100, 253 typos\nWhat do the authors mean by “avoid integrating” in line 166?\n- line 333 typo, lower case log.", "limitations": "The authors discuss how their work can be extended. However, there is no explicit discussion of limitations. I think the major one if the assumption on the data distribution (mixture of gaussians). This should be mentioned explicitly in the abstract, as well as discussed under limitations. I personally do not see any societal impact of this work beyond standard impact of theory and better understanding of deep learning, thus for me personally it is not an issue that the authors skipped it.\n\nI believe citations to datasets and architectures used are missing.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, it’s a pretty good and interesting paper, and I believe the advancements in PAC-Bayes theory are worth a publication and novel. I like that the authors did not only stick to theory, but also evaluated their bound empirically. However, there are a few issues \n - with the experiments (i hope the authors will answer my questions, and confirm the correctness of their evaluation of the bounds), \n - some presentation issues in the theory part that need to be addressed with care to improve clarity, \n - and also missing references and comparison to prior work, which is the one of the biggest issues for me. \n\nI am leaning towards accepting the paper with the hope that the issues listed above will be addressed by the authors. \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": "3nQtVkLNmwh", "reviewer": "Reviewer_2Hhp", "summary": "The authors present a new PAC-Bayesian generalization bound in connections with the gradient norm of loss function with respect to the input space. The authors start from the bound presented in Alquier 2016, and compared to the assumption where loss is uniformly bounded, the authors try to give the complexity term a new bound with a more general assumption, i.e. on-average bounded loss and gradient norm. With such assumptions, this new bounds regarding both linear and non-linear models are proved via the Herbst theorem and Log-Sobolev inequalities. Finally, the authors show some empirical study to show the effectiveness of their frame, which can provide tighter generalization bound compared to conventional techniques.\n", "questions": "I hope the authors can address my concerns in their rebuttal..", "limitations": "In my opinion, this paper do not involve related issues for its current version.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "&nbsp;\n### **Strengths**\n\n1. This paper is clear and well written. \n2. This paper provides a new generalization bound with a more relaxing assumption. In my opinion, theoretical insights of the generalization bound are valuable for enriching our understanding towards the neural networks. It is encouraged to contribute to this topic. The authors prove it under the assumptions to the on-average bounded loss and gradient norm, which, to my understanding, makes it closer to our practical situations, although the assumption here has not been significantly improved compared to that in Alquier 2016 (i.e. from uniformly bounded loss assumption to on-average bounded loss assumption). \n3. It is interesting to see the theoretical connections between the generalization and the gradient norm of loss w.r.t the input space. This may also provide theoretical insights about the model robustness.\n4. This paper provides rigorous mathematical proof.\n\n&nbsp;\n### **Weaknesses**\n\n1. I think it can be much more better if the authors show the experiments results regarding the connections between the generalization bound, gradient norm and testing performance.\n2. From formula 22 and Lemma 3.1 to Lemma 3.3, it seems that the authors exchange the expectation and integral operation. I am somehow worried about whether such exchange is eligible.\n2. Formula 8, $Ent[e^{\\alpha F]}$ -> $Ent[e^{\\alpha F}]$.\n3. Formula 23, it seems that the authors are missing the explanation of $d$, which may be $W \\in R^{k \\times d}$.", "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": "08DPyW_n0jx", "reviewer": "Reviewer_b5Rz", "summary": "This paper presented a novel PAC-Bayesian generalization error bound that depends on the gradient norm of the loss function. The idea is to use Herbst argument and control the entropy using the appropriate assumption about data and loss functions and their gradient norm. The obtained bound assumes the average of the loss function and its gradient norm. Numerical experiments suggest that the obtained bound can capture the structure of the deep neural networks.", "questions": "- Questions related to Weaknesses.\n- The assumption in line 139, input data $x$ follows the Gaussian distribution, is very strong. On the other hand, if we relax such an assumption not the input space but the feature or latent space, then it would be moderate and easier to verify. Is such relaxation possible?\n\n- In lines 233 to 237, the assumption in Lemma 3.3 is evaluated by the numerical experiments. Authors claimed that ``The maximum standard deviation across the labels is 0.022, while the mean value is 4.605. Hence, it is evident that this assumption holds in practice\", but I cannot how this conclusion is derived. I would like to know more detail about this point.", "limitations": "The limitations (assumptions) are written clearly. Since this paper proposed a theoretical analysis, it seems there exists no social negative impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n- The motivation of the research is practical and easy to understand.\n- As far as I know, using Herbst argument for deriving the generalization error bound seems novel and the assumption of the obtained bound (on average bounded and Lipschitz property of the loss function) is also novel and meaningful.\n- The obtained bound naturally includes the multi-class classification, which is practically important. \n- The numerical experiments especially Figure 2, can successfully capture the importance of the depth of neural networks in generalization ability.\n\n# Weaknesses\n- I think some assumptions are difficult to verify or strong in practice. I list them below.\n- To analyze the entropy, the authors assumed that input data $x$ follows the Gaussian distribution (line 139), which is a very strong assumption in practice.\n- The assumption in Lemma 3.3, ``the loss per label is balanced'', for any parameter $w$ is very strong and difficult to understand intuitively.\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": {}}]

Author rebuttal:

Decision: Accept