Generalization Bounds with Arbitrary Complexity Measures
Authors: Paul Viallard
Rémi Emonet
Amaury Habrard
Emilie Morvant
Valentina Zantedeschi
Venue: Submitted to ICLR 2023 (2023)
Keywords: Complexity Measure
Generalization Bounds
Disintegrated PAC-Bayes Bounds

Abstract: In statistical learning theory, generalization bounds usually involve a complexity measure that is constrained by the considered theoretical framework. This limits the scope of such analysis, as in practical algorithms, other forms of regularization are used. Indeed, the empirical work of Jiang et al. (2019) shows that (I) common complexity measures (such as the VC-dimension) do not correlate with the generalization gap and that (ii) there exist arbitrary complexity measures that are better correlated with the generalization gap, but come without generalization guarantees. In this paper, we bridge the gap between this line of empirical works and generalization bounds of statistical learning theory. To do so, we leverage the framework of disintegrated PAC-Bayes bounds to derive a generalization bound that involves an arbitrary complexity measure. Our bound stands in probability jointly over the hypotheses and the learning sample, which allows us to improve the correlation between generalization gap and complexity, as the latter can be set to fit both the hypothesis class and the task.

Under review as a conference paper at ICLR 2023
GENERALIZATION BOUNDS WITH ARBITRARY COMPLEXITY MEASURES
Anonymous authors Paper under double-blind review
ABSTRACT
In statistical learning theory, generalization bounds usually involve complexity measure that determined by the considered theoretical framework. This limits the scope of such analyses, other forms of capacity measures regularization are used in practical algorithms. In this paper, we leverage the framework disin- tegrated PAC-Bayesian bounds and combine it with Gibbs distributions to derive generalization bounds involving a complexity measure that can be defined by the user. Our bounds stand in probability jointly over the hypotheses and the learning sample, which allows us to tighten the complexity for given generalization gap since can be set to fit both the hypothesis class and the task.
INTRODUCTION
Statistical learning theory offers various theoretical frameworks to assess generalization by studying whether the empirical risk is representative the true risk thanks an upper bounding strategy of the generalization gap. The generalization gap is deviation between the true risk and the empir- ical risk. An upper bound on this gap is generally a function of two main quantities: (i) the size of the training sample and (ii) complexity measure that captures how prone model is to over- fitting. One potential limitation is that existing frameworks are restricted to particular complexity measures, among them the VC-dimension (Vapnik & Chervonenkis, 1971 or the Rademacher com- plexity (Bartlett & Mendelson 2002) for which some generalization bounds can derived. To the best of our knowledge, there no generalization bound able take into account, by construction, some arbitrary complexity measures that can serve as good proxies for the generalization gap.
In this paper, we tackle this drawback by leveraging the framework of disintegrated PAC-Bayesian bound (Theorem 2. to propose a novel generalization bound with arbitrary complexity measures. To do so, we make use of the Gibbs probability distributions (Equation ? that depend on user-defined parametric function characterizing the complexity. It allows us to derive guarantees terms of probabilistic bounds that depend on model sampled from Gibbs distribution men- tioned above. It is worth noticing that our result allows retrieving the uniform convergence and algorithm-dependent bounds.
We believe that our novel result provides theoretical foundations for the many regularizations used in practice to perform model selection. For instance, our result allows integrating complexity measures studied empirically in recent line of work on weeepprraetrrized models (Jiang et al. 2019 Dziu- gaite et al. 2020 Diang et al.) 202T). In our experimental evaluation, we show how these measures be easily integrated into framework in practice. We notably provide stochastic version of the Metropolis Adjusted Langevin algorithm to compute empirical estimates of our bounds.
Organization of the paper. In Section 2 provide some preliminary definitions and concepts.
Then, we present our main contribution in Section S
In Section we provide a practical instantia-
tion of our framework before concluding in Section

---

Under review as a conference paper at ICLR 2023
2 PRELIMINARIES
2.1 SETTING
We consider the supervised classification learning setting where X denotes the input space and Y is the label space. We consider that an example (x, E Xx is sampled from an unknown data distribution on x Y. A learning sample S=((x;, yi) Ji) contains m examples drawn i.i.d. from D; we denote the distribution of such an m-sample by Dm Let H. be potentially infinite set of functions h X-Y, called hypotheses (or models), that associate a label from Y given an input from X. Let ((H) be the set of probability densities over HI given reference measure (e.g., the Lebesgue measure); we denote by MI (IHI C ((H) the set of strictly positive probability densities. Given learning sample S, we aim to find h E IH that minimizes the so-called true risk (p(h)= 12 (x.g)>Dl [x) * yl. where [[]]=1 if a is true, and O otherwise. In practice, as the data distribution D is unknown, we estimate the true risk with its empirical counterpart: the empirical risk (h) = m Σ I [xx,
) # yıl. We hereafter denote the generalization gap by Φ : [o, 1]² + I, which is usually defined by (h), (h)) (h Rs((h) empirical risk is representative of the true risk.
that quantifies how much the
In this paper, we leverage the PAC-Bayesian framework Shawe-Tlaylor & Williamson (997 p
McAllester (1998); Guedi] (2019); Alquier (2021) to upper-bound the generalization gap with a arbitrary measure of complexity. In PAC-Bayes, consider an apriori
function that depends belief on the hypotheses in Hi that is modeled by a prior distribution E M* (HI) on H. We aim to learn, from S and n, a posterior distribution o (HH on H. assign higher probability hypotheses in H. (the support of p being included in the support of x). The classical PAC- PAC-Bayesian generalization bounds provide upper bounds expectation over p. meaning that they bound the generalization gap expressed as
the best
J. and where the complexity term depends on the KI. divergence between and π defined as (T[(p])) En p(h)
*(h) This standard com- plexity hence captures how much the prior and the posterior distribution deviate in expectation over all the hypotheses. To incorporate custom complexities in the bounds, we follow slightly different framework recalled below (the disintegrated BaC-Bayesian bounds) in which the expectations on p are "disintegrated": the gap (() Rs()))= (h)-ss((h) of a single h sampled from p is considered in the bounds.
2.2 DISINTEGRATH, PAC-BAYESIAN BOUNDS
B Bayesian bounds have been introduced by Catoni 2007 Th 1.2.7) and Blan- chard & Fleuret 2007 Prop 3.1 As far as we know, despite their significance, they have been little used in the literature and received only recently renewed interest for deriving tight bounds in practice (e.g.. Rivasplata al. 22000; Viallard et al. (202T)). Such bounds provide guarantees for a hypothesis h sampled from posterior distribution Ps. They take the form of a bound that stands with high probability (at least 1 5) over the random choice of training set S ~ D and hypothesis h. This paper mainly focuses on a particular bound, namely, the one of Rivasplata et al. 2020
The disintegrated PAC-
Theorem 1 (i)) recalled below.
Theorem 2.1 (General Disintegrated Bound of Rivasplata et al. (2020). ). For any distribution D on X x Y, for any hypothesis set H., for any distribution E M MHH), for any measurable function HI x (X x Wym + R. for any 5 E (0, 1}. we have
Ps (h) hh)
1
P Sn-Dm.hupp
S(h,S) < In
+ ln
E E exp (xp()
21 21-6,
S'ND
S
goo
(PS..T
where ps is a posterior distribution such that ps E M(H..
In this case, the function (phh, SR (h)) is deviation between the true risk Rp(h) and the empirical risk (h).) Moreover, the function ( n, 6) is constituted of terms: (i) the
disintegrated KI. divergence In (s(h) defining how much the prior and posterior distributions deviate
*(A)
Disintegrated PAC-Bayesian bounds have also heen introduced as "single-draw case" by Hellström & Durisi 2020
2

---

Under review as a conference paper at ICLR 2023
for single h, and (ii) the term In Es Bywr exp (p(g which is constant W.E. h H and S E (X and usually upper-bounded to instantiate the bound. In the following, we refer to the whole right-hand side of the bound, $(), as the complexity measure for the sake of simplicity. Note that this is in slight contrast with the standard definitions of complexity, where the term (ii) (related to and the sample size m) is not included. This additional term is, in fact, constant w.n.t the hypothesis hops and the learning sample S~D"..
In the bound of Theorem 2.1 the complexity term Φ() depends on the disintegrated KL divergence and suffers from drawbacks: the KL complexity term is imposed by the framework and can be subject to high variance in practice (Viallrdd et al., 202I). However, is important to notice that this disintegrated KI. divergence has clear advantage: it only depends on the hypothesis h and data sample S. instead of the whole hypothesis class (as it is often the case for instance with the KI. divergence in PAC-Bayesian bounds, or the VC-dimension). This might imply better correlation between the generalization gap and some complexity measures. In the next section, we leverage this disintegrated KL divergence to derive our main contribution: a general bound that involves arbitrary complexity measures.
3 INTEGRATING ARBITRARY COMPLEXITIES IN GENERALIZATION BOUNDS
We first begin with a short presentation of our result to give some preliminary intuitions and to in- troduce the notion of Gibbs distribution which is a key element in the exposition of our contribution. We then formalize our theoretical result in Section 3
3.1 AN INTRODUCTION TO OUR RESULTS
Let D (h, 5) be a real-valued function that takes a hypothesis h E H., a learning sample S e (XxY)m, and the parameter 8 as arguments and that is dependent on an additional function μ : H (I The idea is to use this function p() to parametrize the complexity measure with respect to the data sample S and the model h, in order to introduce custom complexity measures in the bound; we call "parametric function" the function u(). This function must, in fact, serves to obtain a complexity measure 4 pr,hh, S, that is representative of the generalization gap (which is unknown). For instance, when H is a set of hypotheses hw parameterized by some weights w e Rd, can fix j(hw, /)=||w||. for some norm Il. This means that μ(hw.S) S) can be set to the regularization term of the chosen objective function so that the complexity, hence the bound, will to
depend it. This is not entirely new since, for example, uniform stability bounds allow consider such norms (see, e.g., Kakade et al., 2008). This example is just for illustration purposes. Our framework is compatible with broader families of complexity measures, we will see later. Given such a parametric function μ²),, the bound we derive in Theorem 3.1 takes the following form.
Definition 3.1 (Generalization Bound with Complexity Measures). Let 6: [o, 112-R be the gener- alization gap, p=: (XxY)" be paramelric function. A generalization bound with arbitrary complexity measures is defined such that for any distribution 'D on % x W, for any hypothesis set HH, there exists real-valued function 4,, :.:HH (Ax () x (0, 1]-2R such that for any ō E (0, 11, we have
IP SWD. houps
(RDD()), S 4 (h, 2 1-6.
The main trick to obtain such a result is to consider partieular posterior distribution ps: incorporate the function n²) by choosing the distribution ps as the Gibbs distribution defined as
ps( x (1)s - -uh, S)), where a E R+
This Gibbs distribution ps interesting from an optimization viewpoint: a hypothesis more likely to be sampled from it when the objective function h + Rs(h)+ ((h, S) is low for a given S. In the ideal case, since we want to minimize the generalization gap @(R(h)) Rs)h),, one can define the function p(h, S) (o@(D(h), Rs(h)) (h) to obtain Gibbs distribution that samples hypotheses with small gaps. However, since the generalization gaps are unknown, they must be replaced with computable function u()) For instance, the function a!) can serve "regularizing term" (when pa) is a norm), so that a hypothesis is more likely to be sampled when the trf Rs(h) ((h, S) is low. Equation 2 might look restrictive, but it can actually represent
3

---

Under review as a conference paper at ICLR 2023
any probability density function. Indeed, let p's be distribution on H,, e.g., Gaussian Laplace distribution. by setting S) = -aRs (h) In p'g(h) we can retrieve the distribution P's- The Gibbs distribution is well-known and studied in learning theory. In the following, we discuss the principal theoretical works based on it and highlight the differences with our framework.
3.2 RELATED WORKS USING THE GIBBS DISTRIBUTION
This section highlights two lines of work that are related setting: (i) the link between the Gibbs distribution and optimization and (i) the usage of the Gibbs distribution in generalization bounds.
Relationship between optimization and the Gibbs distribution. Given objective function
f: H (XX + R, the information risk minimization principle Zhang 2006 is related to the
Gibbs distribution, Le., by taking
Ps argmin { E [h, (L(p|TT) where houp
ps(h) exp [-a (mm()))
(BM
Note that in our case, we have S),, Rs(h) + p(h, _ In n (h). This distribution is also linked to the Stochastic Gradient Langevin Dynamics (SGLD) algorithm (Welling & Teh, 201T that learns the hypothesis h E [HI by running several iterations of the form
23
h1 - h4 [h,
-e,,, with ((O,I))
where h2 is the hypothesis learned at iteration E B the learning rate, and a the concentration parameter of the Gibbs distribution. This algorithm has an interesting feature: when the learning rate tends to zero, the SGLD algorithm becomes a continuous-time process called Langevin diffusion, defined as the stochastic differential equation in Equation (4 Indeed, Equation can be seen as
the Euler-Mane Marrerma discretization (see, Raginsky et al. 2017 of Equation defined for t as
dhg- fh,, S)dt + Ve
where B, is the Brownian motion. Under some mild assumptions on the function SQ, Chiang al. (1987) show that the invariant distribution of the Langevin diffusion is the Gibbs distribution proportional to oxp(-af(he S)).
Gibbs distributions in generalization bounds. The Gibbs distribution is introduced in the PAC- Bayesian theory by Catoni 2004 2007). Alquier et al. (2016) Theorems 4.2 & 4.3) further de- velop PAC-Bayesian generalization bounds based on the Gibbs distribution of Equation 2 with u(h, S) 0 as posterior. The Gibbs distribution has also been considered in information-theoree
generalization bounds (see e.g., Raginsky 2017 Goyal al. 2017 Bu al. 2020) that upper- bound the expected generalization gap Es-DD Awps Rp(h) - (s)). For instance, Kuzborskij
ct al. (Theorem 1. 2019 provides generalization bounds for ff being the empirical risk (with sub- Gaussian losses). Aminian et al. (Theorem 1, 202T prove closed-form solution of the expected
generalization gap with the Gibbs distribution defined with a non-negative f. The expected true risk Bsw-Dm,Auppe R RD(h) has also been upper bounded by excess risk bounds (Xu & Raginsky 2017 Kuzborskij et al. 2019), i.e., bounds w.r.f. the minimal true risk over the hypothesis set. However, all these bounds consider expected risks while we are interested in the risk of single hypothesis
h sampled from ps- Hence, to the best of our knowledge, we are the first to derive probabilistic
bounds for single hypothesis sampled from Gibbs distribution (see Corollary 3.1 Theorem
3.3 OUR MAIN RESULT: GENERALIZATION BOUND WITH COMPLEXITY MEASURES
We now state our main result: bound on the generalization gap involving a custom μ. standing for hypotheses sampled from the posterior (s)h) x exp (x p(h, S)].
Theorem 3.1 (Generalization Bound with Complexity Measures). Let ø 1].1]2=R be the generalization gap. For any D X W, for any hypothesis set IHI, for any prior distribution
4

---

Under review as a conference paper at ICLR 2023
M (H) on H. for any μ.: (XXx(X +R. for any ò (0, 11, we have
(Ro((h), S (aRs(h() + u(h,)) - [aRs(1)) + (((h
P SmDDm, Wows, hmps
=(h) T(h) 82 S'nDm
+In
+ In
E (x))) Rs 2 1-6,
where ps is the Gibbs distribution defined by Equation
This theorem is general since it depends only on the functions <() (expressing the generalization gap) and ı(( (expressing the complexity) chosen by the user. Moreover, we show that this theorem allows obtaining mnfform-convergencee based and algorithm-dependee bounds with the integration of complexity measures. We defer the proof of this result to Appendix D
Given o() and p(), we note point that can be surprising at first reading: it appears indeed possible to sample hypotheses with high objective Rs (h)h+ u(h, S) value and to obtain a tight generalization bound. However, by definition of the Gibbs distribution ps. such sampled hypothesis h~ps is less likely to be drawn since the density is higher when the objective is low. In other words, when ((h, S) acts as a regularizer, the bound holds more likely for the hypotheses achieving low regularized empirical risk, which a rather expected result when considering regularized learning.
In general, the bound may appear loose as there is no explicit dependence on the size of the data sample m. However, to get a bound that converges when m increases, it is function of such (() Rs()))=mm (k)RR()) or
sufficient to fix 6() (h), Rs (b)))=2m((B))) (h)) where kl(gllp) _ qqn p + (1 q) In 1-9 for p E (0,1)
1-p
and q [0, 1]. Then, the tightness of the bound depends on m, apart from s0), p() and a.
The remaining challenge is to upper-bound ESS-D Bewn exp (R Rs (o)) and In =(h)
*()
to get a practical bound. As an illustration, provide in the next corollary instantia- tion of Theorem 3.I for two generalization gaps: ( s [R)() and (k)(hh) Rs (R)))))))(
and for æ is uniform distribution on bounded set H..
Corollary 3.1 (Practical Generalization Bound with Complexity Measures). For any DD on XxY, for any bounded hypothesis set H. given the uniform prior π on H. for any H: (X any 8 (0, 1}. with probability at least 1 1 over SmD h' h'm hrops we huve
Y) (XXY)""
.R for
kl (Rs(h) (R)()))))()))))))))))))))))))))) S 1 [aRs(N)) + [aRs(N)+ +(b,
8ym
- (a)((h) + w(hh, 53
+ 82
(5)
and ( SV 2m
[aRs(t))+ + +((,s))) (bRs(h) + p(h, S)
8/m²
(6)
82
where [a]+ = (0, a), and ps is the Gibbs distribution defined in Equation
Interestingly, Corollary 3.1 gives a bound on kl (h) and RR (s) where all
terms except (h) are computable. To compute Equations (5) and 6 to obtain a generalization bound on the true risk (h). We obtain respectively
rearrange the terms
(h) < kl
(h)
1 m
[aRs(h') + p(h, (1) [)h
8/m
82
8/mm
and (D) < (h)
(a)s(h') + ((), (h) + (hh, S)] +
2m
82
where (l(g)7)=max(2 E 1) kl(glpp) < <... These bounds are used in Section to illustrate
the generalization guarantees for different values of #() and a. In general, Equation provides a tighter bound on the true risk than Equation B This can be proven with Pinsker's ineuuality (Appendix G and is shown in experiments. Notice that the r.h.s. of Equations 5 and enjoys asymptotic convergence for m- However, for some trivial cases, the convergence rate can be arbitrarily degraded by increasing (h<R((h)+ ( S)] (aRs(h)+ ((h, For example,
5

---

Under review as a conference paper at ICLR 2023
for a large empirical risk Rs(h') (which is common when h/ is sampled from uniform prior
HD, and for a=m and S0 the r.h.s. for ( (h, -R) + In 2n2 and is large, matter m. In order for the bound to be meaningful, we have then to set a and 14( such that (i) the distribution Ps allows us to sample a hypothesis h associated with a low objective function h + (1)++++ S) and (ii) the complex- ity measure (h, 8, is tight. For example, for a=ym and juh,, S)=0, the distribution ps is less concentrated around the minimizers of the empirical risk, but the complexity measure is tighter compared to the previous example: mmm ( + In 2 with j(h, - m. (RD(()), (s)) (alt))))Rs(())) and a- mm, the upper-bound of (<RD (h), Rs(h)) (R)(()))))))()))))(())((()))) + In 2 I+ which is tight when the gaps of l and h'' are small; the tightness arise with high probability since the den- sity ps (h) x exp( - _x (Rp(h)) Rs(h)) is concentrated around the small gaps. This also highlights that the choice of the parametric function pa( is key to obtaining a tight generalization bound.
= kl[Rs (h) [R((]] simplifies to
8 J_. Lastly, in the ideal case
m (h))) ([)]][[[]]]]]]]] becomes +/mm
m
In our previous analysis, we considered a uniform distribution for the prior π for illustration pur- poses. It is nevertheless clear that if the prior is good, i.e., it associates higher probability to hypotheses having a low objective function, then the bounds become tighter. The most favorable case is when both the prior and the posterior Ps associate high probabilities to these hypotheses. While the posterior Ps is generally learned from data, the choice of the prior π matters to get tight bounds. When no prior knowledge of the problem available, to obtain better bounds, one solution is to consider data-dependent priors that have been heavily used in the e.g. (Parrad-Hernaaae
literature (see, et al. 2012, Dziugaite et al., 202T Pérez-Ortiz et al. 202Ip. In the context of our practical evaluation hereafter, we consider only uniform distributions for the prior π,, as we think it helps us assess generalization better. Indeed, a hypothesis h sampled from the uniform dis- tribution has a high chance of underfitting. Hence, if the hypothesis h ~ Ps has tight bound, it must be that this hypothesis generalizes well. On the other hand, when using data-dependent priors, cannot tell if the bound is tight because the hypothesis generalizes well or because the posterior is close to the prior.
4 USING ARBITRARY COMPLEXITIES IN PRACTICE
The bound of Corollary 3.1 is not directly applicable in practice: the remaining challenge to sample h from the Gibbs distribution As defined in Equation We address the sampling issue in Section 4. Then, we make use of the proposed solution to assess our bound in practice. Section 4.2 introduces our experimental setting and Section reports an overview of results the tightness of the bound. We report more results on the influence of a and the other parameters in Appendix
4.1 SAMPLING FROM THE GIBBS DISTRIBUTION
Sampling from the Gibbs distribution of Equation 2 is hard task: naively, it requires to evaluate the function + (h) S) for all h E H. which is intractable when H. is infinite or even large. In empirical study of our bound, we tackle this issue for peretaraaeter models, which we later consider in Section 4.2 Let us consider a set H of hypotheses hw parameterized by w e IR," and a tractable distribution denoted PW (e.g., Gaussian distribution) such that its density approximates the density of ps. In this setting, to learn such a tractable distribution, we propose in Algorithm μ a stochastic version of the Metropolis Adjusted Langevin Algorithm (MALA, [Bssag] (1994) i Its objective is to generate samples from ps by iteratively refining the tractable distribution that we define as
PW - W (V-S/REA(W++ a p(w.20]. 28 )
(w) (xxx))) E(tw: (x, y)) the empirical risk on the mini-batch C S, and E H x (XxY) [0. 1] is loss function. Concretely, we initialize the parameters w of the model as the output of an optimization algorithm (Vanilla SGD in our case) minimizing (w(w)++ S) (which is approximated by (w)++ ((w, for each mini-batch 2).
where (w)
"See Chib & Greenberg 1995) for introduction on Metropolls-Hastinns Algo on which MALA based.

---

Under review as a conference paper at ICLR 2023
Algorithm Stochastic MALA
Input: Learning set S, weights w, function y²)) loss function E()
2: Hyperparameters: Number of iterations T,, learning rate 3, parameter
3: for f- 1.... do
4: U < Sample (without replacement) mini-batch from S
5: w' +- Sample from the distribution P
1, Pu((w)) wt (w) Pi (W) (w")
6:
T f min
7:
Sample from the distribution Uni(O,
8:
if u S then
9:
w w
10:
return w
Then, we refine them as follows: each iteration, given the current weights w and mini-batch U C S (Line 4), we sample candidate vector w' (Line 5) according to the distribution Pt: then (Line 9) we decide to reject or accept the new candidate become our current weights w, depending on its ratio r= min(1, Per www (w)
(w) (w/) is larger than a control value u sampled from the uniform distribution Uni(O, 1) [0, 1j. Note that, compute т, it is not necessary to know the normalization constants of the two distributions appearing in since they cancel out. In other words, only the function (without the normalizations) associated to the distributions are required to compute 7. Under the mild assumption that Ps is absolute continuous w.r.f. P (see Chib & Greenberg 1995 for details), when the number of iterations tends infinity and when U=S, the returned w is sampled according to ps (Smith & Roberts 1993). Note that this assumption requires that the tractable distribution P has a strictly positive density when the density of ps strictly positive as well (see Chib & Greenberg 1995).
4.2 EXPERIMENTAL SETTING
In this section, investigate the tightness of our bounds of Equations 7 and the MNIST (Le- Cun et al. 1998) and FashionMNIST (Xiao et al., 2017) datasets. We keep the original learning set as S and the original test set T to estimate the true risk that refer test risk (4))..
Model. We use a "Convolutional Network in Network" (Lin et al. 2013) similarly to Jiang et al. (201)) and Dziugaite et al. (2020) that consists of several modules of 3 convolutional layers each followed by leaky ReLU activation function (its negative slope is set to 10-3). The depth of the network L the number of convolutional layers, and the width H is the number of channels of each convolution. In addition, for each layer i, we denote its weights by w,. For full details of the architecture, we refer the reader to Appendix We consider (9, 12, 15) and H [128,, 256). Furthermore, we initialize the network with the weights E obtained by the uniform Kaiming He initializer He al. (0055). The set corresponds to the hypotheses bw that can be obtained from this initialization (and we clamp the weights during the optimization in the initialization interval).
12,
Arbitrary complexity measures. We study 6 different complexity measures parametrized by differ- ent functions p(hw; S) from fromJiang Jiang al. 2019 Sec. c These 6 functions are actually independent of the learning sample S (S is dropped below for convenience) and defined as follows:
DIST DROT_FRO(Iw)) =
w
Plla,
and DIST.L2(hw) = (/w-w"ll 112
L Σ
card(2))
CARAM_NORM(h.. and
/wil2 and PATH NORM Σ
h (1)(1),
and SUM_FRO(hw))
II
1w.ll and ZERO(Hw) 0.
Note we consider subset of the functions studied by Jiang al. we select those that optimizable.
7

---

Under review as a conference paper at ICLR 2023
MNIST. A/A Disr,PRo
MNIST p(b 5)- PARAM, NORM
MNIST, piA SUM,FRO
0.10
0.10
0.125
0.08
0.08
0.100
0.06
0.075
0.04
0.04
0.02
0.02
0.025
0.0
0.2
0.4
0.0
0.1
0.2
0.3
0.4
0.0
0.1
0.2
0.3
MNIST, oEA D1st Aq
MNIST. MIN 5) PATE Nossi
MNIST, MEh 5) ZIERO
0.12
0.15
0.15
0.10
0.10
0.10
0.06
0.05
0.01
0.05
0.0
0.1
0.2
0.3
0.0
0.2
0.4
0.5
0.0 0.1
0.2
0.3
Figure 1: Scatter plot given a parametric function p(h, S). where each segment represents a neural network ho learned with a given a, width H and depth L. Each segment has a corresponding orange square and a blue circle. The orange squares corresponds to the empirical risk (s) (x-axis) and test risk RT(h) (y-axis). The blue circle resp. the black triangle represents Equation 7 resp. Equa- tion (8) in the x-axis and the test risk R (h) in the y-axis. The dashed line is the identity function.
We define the considered measures with a taken among 5 values uniformly spaced between [ym, m). Note that, as mentioned above, these 6 parametric functions are independent of the sam- ple S, we have also analyzed other parametric functions that depend on S. The results obtained are similar, we decided defer these results in Appendix
Bound optimization. To compute our bound in Equations and we aim to sample a hypothesis h ~ ps via Algorithm [ We set the loss function to the bounded cross entropy from Dz- jugaite & Roy (2018) 8): E(h. (x, y))= & 1n(e=1+(112))) "byy))) where h[y] is the probability assigned to label y by h. The advantage of DZiugaite & Roy] (2018) 's cross-entropy is that it lies in Eh,, (x. 3)) E [0, 1J. whereas the classical cross-entropy is unbounded. Indeed, taking into account the classical cross-entropy when optimizing the objective function would lead to focusing too much on the risk minimization, while we want to take into account 1 ((w,2). We initialize the
weights W to the solution found by optimizing the objective function R (w)+++ ((w,S) with Vanilla SGD (with 10 epochs, a learning rate of 10-1, and a batch size of 64). Given these initial parameters w, we execute Algorithm 1 for 1 epoch with a mini-batch of size 64, where 3=10-4.
4.3 TIGHTNESS OF THE BOUNDS
For each parametric function 1(), we report in Figures I and 2 the test risks Ry (h) and the values of the tightest bound (h) (w.F. a) associated to Equations 7 and Bb for different param- eters (depth L, width H). First of all, we observe that the bounds correctly upper-bound the test risks and that some measures lead to tighter bounds, such as SUM_FRO or DIST_L2. We also re- mark that certain empirical risks are high, in particular, for these latter measures. This is due to the sampling of the hypothesis from the distribution ps: the hypothesis does not necessarily min- imizes the objective function h + (s(h)+ p(h, S). We nevertheless observe that the bounds' values are higher when the empirical risk Rs (h) is low. This can be explained by the fact that (h'R(h")) + n(h,,, S)] - (h) + /ahh, S)] is large in this case due notably to the non-informative prior æ. Interestingly, when the empirical risks are a bit worse or close to the true risks, the bounds become tighter for certain parametric functions such as DIST_ and SUM_ FRO, which then appear to capture more information on the generalization capabilities. Indeed, the more the objective func- tion Rs (s(h++ j(hh,) S) is representative of the gap of h, the tighter the bound. On the other hand, we can also note that for some measures such as DIST FRO, PARAM NORM, and ZERO (mainly for FashionMNIST), the bounds remain similar whatever the hypothesis which illustrates that these
8

---

Under review as a conference paper at ICLR 2023
FashioMMIST, plb, 5) Tisn,Faa
MNITT M(A 5) PARAM,NORM
FastioMNNSST pih -SIM_FRO
0.4
0.20
0.18
0.18
0.16
0.10
0.14
0.14
0.2
0.12
0.12
0.10
0.1
0.2
0.4
0.1
0.2
0.3
0.4
0.5
0.1
0.2
0.3
0.4
FashicrMMIST, als,5) DISt ko
FactionMNIST. PIA 5) PATiE Nossi
FachirMMNSTT MMA. Z200O
0.35
0.35
0.32
0.30
0.30
0.30
0.25
0.25
0.28
0.20
0.26
0.15
0.15
0.24
0.10
0.1
0.2
0.3
0.4
0.2
0.1 0.6
0.8
0.25
0.30
0.35
Figure 2: Scatter plot given a parametric function p(h, S), where each segment represents a neural network ho learned with a given a, width H and depth L. Each segment has a corresponding orange square and a blue circle. The orange squares correspond to the empirical risk Rs (x-axis) and test risk R (h) (y-axis). The blue circle resp. the black triangle represents Equation 7 resp. Equa- tion (8) in the x-axis and the test risk R (h) in the y-axis. The dashed line is the identity function.
latter measures do not really help to capture some information about the generalization gap. This confirms that there is an interest in using a parametric function that captures information on the model during the training phase to assess its generalization capability. In Appendix E we provide additional results the influence of the parameter a and the depth/width of the network. As ex- pected, the bounds tend to increase when a becomes large for smaller a (e.g., close to /m), the bounds are improved but to the price of potentially higher risks. In contrast, about the depth/width impact, some measures are less sensitive to the increase of such parameters, such as PARAM NORM and, to lesser extend, SUM FRO and DIST This illustrates our framework's interest in studying the impact of some regularization when learning porameeparaetterizee models.
5 CONCLUSION
In this paper, we provide a novel generalization bound that is able to incorporate arbitrary complex- ity measures, unlike classical learning theory frameworks (for which the framework imposes the complexity). These measures incorporate a data and model-dependent function, which can favor tightening the complexity for the generalization gap. To the best of our knowledge, our framework is one of the few able to be general enough to bring theoretical guarantees for most of the arbitrary complexity measures used in practice, e.g., based on some norms or a validation set. Such a frame- work may be adapted to other settings, such as transfer learning, offering new research directions. However, one limitation of this work is clearly that the hypothesis is obtained from a distribution difficult to use, namely, the Gibbs distribution, which uses specific sampling algorithm, e.g., our algorithm stochastic MALA. It would be interesting to study the performance of such a sampling theoretically. Al Alternately, the generality of this framework allows bounds, for example, as in Corollary D.I] Improving the frame- work in this direction is an interesting future work. In particular, investigating the use of other distributions for sampling the hypothesis could be a possible direction. Another one could be to consider other specific ways to define informative data-dependent priors in order obtain better bounds. For instance, the parametric function can be leveraged in order to include informative prior. Another interesting perspective is to study SGD-based algorithms, either by analyzing models learned by SGD through our framework or by developing SGD alternatives to optimize our bounds. In conclusion, we believe that this work paves the way for new research directions that try to bridge statistical learning theory and practice.
to avoid the sampling if we
consider uniform-coovergence-eee

---

Under review as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
In order to ensure the reproducibility of our results, we complete the presentation of the experimental complete description of the setting, models, and parameter used in Appendix D where some additional results are also provided. We also include the code of our method as an additional zip file in the supplementary material in order to facilitate the reproduction of the experiments.
setup of the main text in Section 4.2 with
Regarding the theoretical contributions, we provide in Appendices to the proofs of the results presented in the main paper, namely Theorems 2.1 and 3.1 and corollary 3.1 We also provide in
Appendix some additional results and discussion about the comparison of our framework with the uniform convergence and algorithm-dependen generalization bounds.
ETHIC STATEMENT
The contributions of this paper are essentially fundamental and theoretical; we do not see an immedi- ate potential negative social impact from these contributions. We followed classic ethical guidelines in machine learning which in our case mainly consists in bringing information about reproducibility issues which addressed in the previous paragraph.
REFERENCES
Pierre Alquier. User-friendly introduction to pac-bayes bounds. CoRR, abs/2110.112111 2021.
Pierre Alquier, James Ridgway, and Nicolas Chopin. On the properties of variational approximations of Gibbs posteriors. Journal of Machine Learning Research, 2016.
Gholamali Aminian, Yuheng Bu, Laura Toni, Miguel R. D. Rodrigues, and Gregory W. Wornell. An exact characterization of the generalization error for the gibbs algorithm. In NeurIPS, 2021.
Peter Bartlett and Shahar Mendelson. Rademacher and Gaussian Complexities: Risk Bounds and Structural Results. Journal of Machine Learning Research, 2002.
Julian Besag. Comments "Representations of knowledge in complex systems" by U. Grenander and MI Miller. Journal of the Royal Statistical Society, Series B., 1994.
Gilles Blanchard and François Fleuret. Occam's hammer. In Anmual Conference on Learning Theory (COLT), volume 4539 of Lecture Notes in Computer Science, pp. 112-126. Springer, 2007.
Olivier Bousquet and André Elisseeff. Stability and Generalization. Journal of Machine Learning Research, 2002.
Yuheng Bu, Shaofeng Zou, and Venugopal V. Veeravalli, Tightening mutual information-based bounds on generalization error. IEEE Sel. Areas Inf. Theory, 2020.
Olivier Catoni. Statistical learning theory and stochastic optimization: Ecole d'Eté de Probabilités de Saint-Flout Flour, XXXI-2001. Springer Science & Business Media, 2004.
Olivier Catoni. Pac-Bayesian Supervised Classification: The Thermodynamics of Statistical Learn- ing. CORR, abs/0712.025 2007.
Tzuu-Shuh Chiang, Chii-Ruey Hwang, and Shuenn Jyi Sheu. Diffusion for global optimization in R", SIAM Journal on Control and Optimization, 1987.
Siddhartha Chib and Edward Greenberg. Understanding the metropolis-hastings algorithm. The american statistician, 1995.
Gintare Karolina Dziugaite and Daniel Roy. Data-dependent PAC-Bayes priors via differential pri- vacy. In NewrIPS, 2018.
Gintare Karolina Dziugaite, Alexandre Drouin, Brady Neal, Nitarshan Rajkumar, Ethan Caballero, Linbo Wang, Ioannis Mitliagkas, and Daniel M. Roy. search of robust measures of generaliza- tion. In NewrlPS, 2020.
10

---

Under review as a conference paper at ICLR 2023
Gintare Karolina Dziugaite, Kyle Hsu,, Waseem Gharbieh, Gabriel Arpino, and Daniel Roy. On the role of data in PAC-Bayes. AISTATS, 2021.
Anil Goyal, Emilie Morvant, Pascal Germain, and Massih-Reza Amini. PAC- MAC-Bayesian Analysis for Two-Step Hierarchical Multiview Learning Approach. In Machine Learning and Knowledge Discovery in Databases (ECML PKDD), volume 10535 of Lecture Notes in Computer Science, pp. 205-221. Springer, 2017.
Benjamin Guedj. primer on pac-bayesial learning. CoRR, abs/1901 .05353, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification. In IEEE ICCV, 2015.
Fredrik Hellström and Giuseppe Durisi. Generalization bounds via information density and condi- tional information density. IEEE J. Sel. Areas Inf. Theory, 2020.
Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic generalization measures and where to find them. In ICLR, 2019.
Yiding Jiang, Parth Natekar, Manik Sharma, Sumukh K. Aithal, Dhruva Kashyap, Natarajan Sub- ramanyam, Carlos Lassance, Daniel M. Roy, Gintare Karolina Dziugaite, Suriya Gunasekar, Is- abelle Guyon, Pierre Foret, Scott Yak, Hossein Mobahi, Behnam Neyshabur, and Samy Bengio. Methods and Analysis of The First Competition in Predicting Generalization of Deep Learning. In NeurlPS 2020 Competition and Demonstration Track, 2021.
Sham Kakade, Karthik Sridharan, and Ambuj Tewari. On the Complexity of Linear Prediction: Risk Bounds, Margin Bounds, and Regularization. In NIPS, 2008.
IÍaa Kuzborskij, Nicolò Cesa-Bianchi, and Csaba Szepesvári. Distribation-deeenddent analysis of gibbs-erm principle. In COLT, 2019.
Yann LeCun, Corinna Cortes, and Christopher J.C. Burges. THE MNIST DATASET of handwritten digits, 1998. URL http://yann. lecun. com wwtp///bo////i/eeeeeceeee/
Min Lin, Qiang Chen, and Shuicheng Yan. Network in network. CoRR, abs/1312.4400, 2013.
Andreas Maurer. Note on the PAC Bayesian Theorem. CoRR, cs.LG/0411099, 2004.
David McAllester. Some PAC-Bayesian Theorems. In COLT, 1998.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. Adaptive computation and machine learning. MIT Press, 2012.
Emilio Herrnndee,,, Amiran Ambroladze, John Shawe-Taylor, and Shiliang Sun. PAC-Bayes Bounds with Data Dependent Priors. Journal of Machine Learning Research, 2012.
María Pérez-Ortiz, Ortiz, Omar Rivasplata, John Shawe- Shawe-Taylor, and Csaba Szepesvári. Tighter risk certifi- cates for neural networks. J. Mach. Learn. Res., 2021.
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis. In COLT, 2017.
Omar Rivasplata, Ilja Kuzborskij, Csaba Szepesváti, and John Shawe-Taylor. PAC-Bayes Analysis Beyond the Usual Bounds. In Advances in Neural Information Processing System (NeurIPS), 2020.
John Shawe- Taylor and Robert Williamson. A PAC Analysis of Bayesian Estimator. In COLT, 1997.
Adrian FM Smith and Gareth O Roberts. Bayesian computation via the Gibbs sampler and related Markov chain Monte Carlo methods. Journal of the Royal Statistical Society, Series B (Method- ological), 1993.
Vladimir Vapnik and Alexey Chervonenkis. On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities. Theory of Probability and its Applications, 1971.
11

---

Under review as a conference paper at ICLR 2023
Paul Viallard, Pascal Germain, Amaury Habrard, and Emilie Morvant. A general framework for the disintegration pac-bayesian bounds. arXiv preprint arXiv:2102.08649, 2021.
Max Welling and Yee Whye Teh. Bayesian Learning via Stochastic Gradient Langevin Dynamics. In ICML, 2011.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: a Novel Image Dataset for Bench- marking Machine Learning Algorithms. CoRR, 2017.
Aolin Xu and Maxim Raginsky, Information-theorede analysis of generalization capability of learn- ing algorithms. NIPS, 2017.
Huan Xu and Shie Mannor. Robustness and generalization. Machine Learning, 2012.
Tong Zhang. Information-theerrtiic upper and lower bounds for statistical estimation. IEEE Trans. Inf. Theory, 2006.
12


Reviews:
[{"review_id": "zdVwH2TL1LC", "reviewer": "Reviewer_g1xt", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers the problem of providing generalization bounds using the disintegrated PAC-Bayesian framework. The main idea behind the paper is that we can start with an arbitrary complexity measure which provides a hierarchy over the hypotheses. Then the authors show that a particular learning algorithm based on the Gibbs posterior can be used for learning. Moreover, using the PAC-Bayesian framework we can show that the complexity measure arises in the upper bound on the generalization.  ", "summary_of_the_review": "This paper is interesting. However, there is a big gap between the motivation behind the paper and the actual results. It is my main concern. ", "strength_and_weaknesses": "The paper is very-well written, and the idea is presented very clearly.\n\nI think there is a mismatch between the motivation explained in the intro and the results: In particular, in the intro there is a discussion on the challenges behind proving generalization of \"SGD\". The results mentioned in the intro state that proving generalization is difficult because most of the theoretical results for \"SGD\" empirically do not correlate with the generalization gap.\n\nLater in the paper the authors provide an abstract learning algorithm based on \"Gibbs posterior\" which takes into account the complexity measure. Also, there are some technical details such as, the loss function is not cross entropy,....\n\nAnother point to consider is that in the learning theory community, the main question is why does SGD without any \"regularization\" generalize? It is quite different from the results in the paper since the proposed algorithm is not SGD, also the proposed algorithm is based on using an \"explicit\" form of regularization. Again you can contrast it with the implicit bias results for SGD.\n\nQuestions:\n\n1- For a given problem what is the best complexity measure? Is there any theoretical insight on that?\n\n2- Generalization can't show the learnability. I would suggest that the authors compare the performance of their algorithm with SGD in terms of the \"population error\"?\n\n3- Do the results suggest that we should use the proposed algorithm compared to SGD? I agree that the proposed algorithm comes with theoretical guarantees. \n\n4- You can't sample perfectly from the Gibbs distribution. It is interesting to study the impact of the stochastic mala on the generalization. There are a few results in the literature on the finite time generalization performance of such a samplers:\n\n[1] Negrea, Jeffrey, et al. \"Information-theoretic generalization bounds for SGLD via data-dependent estimates.\" Advances in Neural Information Processing Systems 32 (2019).\n\n[2] Mou, Wenlong, et al. \"Generalization bounds of sgld for non-convex learning: Two theoretical viewpoints.\" Conference on Learning Theory. PMLR, 2018.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "iSKeOZ010Dz", "reviewer": "Reviewer_m9hB", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper provides a PAC-bayes bound that is able to utilize and arbitrary complexity measure. They define a complexity measure, $\\mu$ as a function that maps a pair $(h, S)$ to a real number, where $h \\in \\mathbb{H}$ is a hypothesis, and $S$ is a labeled training sample. This notion generalizes common complexities such as the norm-weight, or the Rademacher complexity. They then show that the following posterior distribution, $\\rho_S(h) \\propto \\exp \\left[ -\\alpha R_S(h) - \\mu(h, S)\\right]$ has a generalization gap that can be bounded with high probability. Their bound is highly general, due to the abstraction of $\\mu$. \n\nTo empirically validate their results, they also give a way of approximately sampling from the posterior distribution above (which is quite non-trivial due to the nature of the distribution). They then apply this to several natural complexity  measures.", "summary_of_the_review": "I recommend this paper for acceptance. I think that it could benefit from increased intuition and more examples, but both of these are easily addressable. ", "strength_and_weaknesses": "This paper offers an interesting general theoretical result that leverages its generality to increase its practical relevance. In particular, it allows a practitioner to understand their algorithms convergence for arbitrary complexity measures. This is particularly relevant because it is well known that traditional complexity measures often do not provide relevant bounds for practical forms of generalization.\n\nI think this paper could have included a further discussion of complexity measures -- both including more examples as well as providing more context to their formalism. In particular, I believe that outlining common properties that one would expect the function $\\mu$ to have could be very helpful for building better intuition.  ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "0WxAYKjdnp", "reviewer": "Reviewer_H8Gk", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper leverages the framework of disintegrated PAC-Bayes bounds to derive a generalization bound for the Gibbs algorithm that involves an arbitrary complexity measure. The proposed bound stands in probability jointly over the hypotheses and the learning sample, which can be used to tighten the complexity for a given generalization gap since it can be set to fit both the hypothesis class and the task.", "summary_of_the_review": "Overall, it is an interesting paper with some novel results. However, I feel that the authors oversell their contribution in the title and abstract. The proposed results only work for Gibbs distribution. If I understand correctly, different complexity measures $\\mu(h,S)$ will induce different learning algorithms, which are hard to implement and compare in practice. Also, I would expect that the structure of the Gibbs distribution could provide a tighter bound or better converge rate, but the resulting bounds are not as tight as I mentioned above.", "strength_and_weaknesses": "Strength:\nThe theoretical part of the paper is very clear. Although Thm 3.1 highly depends on the structure of the Gibbs algorithm, the resulting form is correct and novel.\n\nWeaknesses:\nOne major drawback is the tightness of the bound. From Figures 1 and 2, it seems that the proposed bounds are loose in most cases and are only informative when the empirical risks are high, which is not the current operating regime for deep learning. \n\nA lot of important references are missing. This paper completely ignores a recent line of work on information-theoretic generalization bounds. Though the original forms of these bounds are in expectation [1,2], more recent results [3] can provide high-probability generalization bounds and should be mentioned in the discussion. \n\n[1] Xu, Aolin, and Maxim Raginsky. \"Information-theoretic analysis of generalization capability of learning algorithms.\" Advances in Neural Information Processing Systems 30 (2017). \n\n[2] Bu, Yuheng, Shaofeng Zou, and Venugopal V. Veeravalli. \"Tightening mutual information-based bounds on generalization error.\" IEEE Journal on Selected Areas in Information Theory 1, no. 1 (2020): 121-130.\n\n[3] Hellström, Fredrik, and Giuseppe Durisi. \"Generalization bounds via information density and conditional information density.\" IEEE Journal on Selected Areas in Information Theory 1, no. 3 (2020): 824-839.\n\nMore specifically, the following two papers on the generalization error for the Gibbs algorithm that provides 1/m in expectation bounds are not discussed. \n\n[4] Kuzborskij, Ilja, Nicolò Cesa-Bianchi, and Csaba Szepesvári. \"Distribution-dependent analysis of Gibbs-ERM principle.\" In Conference on Learning Theory, pp. 2028-2054. PMLR, 2019.\n\n[5] Aminian, Gholamali, Yuheng Bu, Laura Toni, Miguel Rodrigues, and Gregory Wornell. \"An exact characterization of the generalization error for the Gibbs algorithm.\" Advances in Neural Information Processing Systems 34 (2021): 8106-8118.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "-GY83Ocq-Td", "reviewer": "Reviewer_g9Hx", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "\nA general framework to compute PAC-Bayesian Generalization bounds is provided. The bounds are “disintegrated” in the sense that they bound the generalization gap by a function which involves both the trained hypothesis h and another hypothesis h’ drawn from the prior distribution. The bounds hold with high probability over the joint draw of the sample, h’ and h, where h is obtained via the Gibbs distribution from classic PAC Bayesian bounds. Sampling from this distribution is analogous to performing empirical risk minimization with added randomness/regularization which depends on the definition of a regularizing function mu.  \n\nThe main theorems are Theorem 3.1, which applies to any priori, and Corollary 3.1, which applies to the case of a uniform prior over a set \\mathcal{H}. Theorem 3.1 bounds the generalization gap with high probability by the sum of three terms: the last term is a function of delta and is similar to an expected generalization gap of a sample from the prior (modulo exponentials and logs): in more concrete situations such as Corollary 3.1, this term is O(constant/\\sqrt{m}\\delta^2) and therefore doesn’t actually depend on the prior pi. The control of this quantity in Cor 3.1 is obtained via a result of Maurer (cf. appendix F). The second term in Theorem 3.1 is the log of the ratio of the prior probabilities of h’ and h, which is a disintegrated analog of the KL divergence which would appear in classic PAC Bayesian bounds. Finally, the first term in Theorem 3.1 is the difference between the regularized risks of h (“trained”, i.e. drawn from Gibbs) and h’, drawn from the prior. This term can be interpreted as an empirically computable complexity measure, and is the main term left in corollary 3.1. The main ingredient in the proof of Theorem 3.1 is Theorem 2.1 which is taken from Rivasplata et al. \nExperiments show that the bounds provide a good control of the true risk at some data-rich regimes where the generalization gap is nearly non existent. Sampling from the Gibbs distribution is achieved via a “stochastic” (i.e. batch-version of the)  Metropolis Adjusted Langevin Algorithm. Further experiments investigate the effects of the regularization parameter alpha. \n\nThere is an attempt to show that the proposed setting supersumes the uniform convergence approach (as well as algorithm dependent approaches) to generalization bounds, but the arguments are not convincing at all. \n\n", "summary_of_the_review": "I enjoyed some parts of the paper, including the main theorem and corollary. The paper is generally well written, but some definitions are imprecise. The comparison to uniform convergences bounds unfairly places the current work above them without providing a concrete framework which could allow one to derive bounds as concrete as uniform convergence ones (without having to sample from the prior or estimate other quantities). Section D in the supplementary is sloppy and repetitive. Overall, only the short proof of Theorem 3.1  counts as an original theoretical contribution, which is not much for as prestigious a conference as ICLR. \n\nI apologize if I missed something as I am not an expert on PAC Bayesian bounds, I am looking forward to the thorough rebuttal and willing to change my score if the other reviews and the rebuttal warrant it. \n\n\n\n=================*More minor* comments=================\n\n1. I would really appreciate a more specific reference (exact page and theorem) for Theorem 2.1 from Rivasplata et al. A proof is provided in the present paper and it seems correct, but it would be nice to see where the result is from (I couldn’t find the exact statement easily when browsing through the reference).\n\n2. In the proof of Theorem 2.1, you might want to explain how you get to the last line in terms of the change of measure which absorbs the $ln(pi(h’)/\\rho_S(h’))$ term. This is especially important since there are other minor typos in the proof (\\mathcal{S} and \\mathbb{S} are used interchangeably to refer to the same quantity and $\\phi(h,S)$ should be $\\phi(h’,S)$ in the exponential at the end of the first equation.\n\n3. On page 13 “by simplifying the left-hand side …” I think you mean “right-hand”. Note that the last two equations immediately above that line are exactly identical. It seems there is a missing simplification (it is not hard to fill the gap though). \nIt would be nice to have a pointer to the proof of Prop. D.1 in section D.2, since the proof is in section D.4. \nIn the preliminaries (“setting”), in the definition of the risk, it seems that you are restricting yourself to classification, which needs to be made clearer earlier on. It seems the assumption is necessary to define kl the quantities in Corollary 3.1. \n\n4. The notation in the main Theorem 3.1 includes two uses of h’ as a different dummy variable.\n\n   5.Below corollary 3.1, “kl” (the KL divergence of the Bernouilli distributions induced by the numbers (\\in (0,1)) provided as arguments ) is not defined. A pointer to page 27 would be nice. \n\n6. For readability, it might be nice to repeat the fact that the quantity at line six of the algorithm can be computed despite the fact that \\rho_U cannot, due to the simplification of the normalization constants in the numerator and denominator. \n\n7. Do you know whether there are guarantees analogous to those of Chib and Greenberg for the stochastic variant of MALA you use? Is the stochastic version original to your work or does it appear elsewhere?\n\n\n=======================Very minor typos etc.======================\n\n\n1. Capital letter at “Theorem 3.1” on line two of the proof of Corollary 3.1 \nThere are a few somewhat inelegant sentences such as: \n\n 2. Section 2.2 just above definition 2.1: “obtained after obtaining”\n\n  3.  Page 5: “Concerning the tightness of the bounds, it may appear loose.”\n\n   4. Top of  Page 15: “ The generality of our framework can thus generalize”\n\n\n", "strength_and_weaknesses": "Strengths: \n\nDisintegrated PAC Bayesian bounds are quite interesting and the main result theorem 3.1 seems original and worthwhile \nI like the fact that the appendix always puts a copy of the theorems to prove, which means the reader doesn’t have to keep going back and forth between the paper and the appendix. \nThe writing is good in general and there are not many grammatical mistakes. \nThe proof of Theorem 3.1 appears correct to me, and so does the proof of Corollary 3.1.  \nThe stochastic MALA algorithm seems to be correctly implemented.\n\nWeaknesses (including main points to be addressed in a rebuttal, numbered for the authors’ convenience): \n\n1.\t(TL;DR: state the exact page of Nagaragan and Kolter where Proposition D.2 appears, substantially rewrite and clarify Section D)\nThe paper claims that their bounds supersume the uniform convergence approach, but It is very hard to make sense of the “proofs”. The claim is also misleading in general since no bound analogous to uniform convergence bounds is derived for any concrete architecture.  There are errors in the “definitions” as well. Definition 3.1 is not very well written, but it is still technically possible to make sense of it. On the other hand, Section D makes very little sense. \n     1.1 **The “proofs” of propositions D.2 and D.3 (which are almost exactly identical) merely seem to go back and forth through tautologies**. Although I admit I may have missed something due to my lack of familiarity with PAC Bayesian bounds, I am quite certain that the proofs are at best very unclearly executed: Proposition D.2 seems to be a reformulation of the concept of uniform generalization bounds taken from Nagarajan and Kolter 19. The authors say that NK19 failed to provide a proof, but it seems unlikely that the result in NK19 needs proof and the current treatment is messy. **Prop. D.2 states that \\Phi_u needs to fulfil definition D.1, which includes equation (14).  This seems to be an assumption of the proposition. The proposition statement than says that equation (14) (from the assumed definition D.1) is equivalent to another trivial reformulation of it.**  \n\n1.2\tThe nearly identical Corollaries D.1 and D.2 are not better. First of all, the corollaries claim to use Theorem 3.1 but do not explicitly state where they do so, though I believe it is exactly after the line “for any hypothesis h… the definition of the parametric function… bound”.  The conclusion there does not seem sound either: Theorem 3.1 is implicitly used there in a form that doesn’t involve the probability over h’ being drawn from the prior. It is also not clear to me why the definition of mu is different depending on whether h=h’ or not (please explain). \n2.\tIn Section 4.2 (experiments), you claim that the set H  “corresponds to the hypotheses h_w that can be obtained from this initialization” (the initialization being that of He et al. 2015). This initialization requires drawing from gaussian distributions, but corollary 3.1 only applies to a uniform distribution on H. Am I correct in assuming that you use the scaling/normalizing factor of the normal initializations from He et al. 2015 to define lower and upper thresholds that define a uniform distribution over the weights? If so, this needs to be explained thoroughly. It is also very unclear how this would maintain the benefits of He initialization since uniformly sampling from a hypercube is radically different from sampling from a multivariate gaussian in terms of dimensional dependence. \n3.\t It seems like most of the experiments are conducted at a regime where there is so much data that the generalization gap is near zero, which makes the bounds far less informative.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject