PAC-Bayes-Chernoff bounds for unbounded losses
Authors: Ioar Casado
Luis A. Ortega
Aritz Pérez
Andres R Masegosa
Venue: NeurIPS 2024 poster (2024)
Keywords: Statistical learning theory
PAC-Bayes
Chernoff bounds
regularization
Primary area: learning_theory
TL;DR: We introduce a new PAC-Bayes bound that allows working with richer assumptions and illustrate its potential by generalizing previous bounds, obtaining novel ones for several regularization techniques, and minimizing them to get new posteriors

Abstract: We introduce a new PAC-Bayes oracle bound for unbounded losses that extends Cramér-Chernoff bounds to the PAC-Bayesian setting. The proof technique relies on controlling the tails of certain random variables involving the Cramér transform of the loss. Our approach naturally leverages properties of Cramér-Chernoff bounds, such as exact optimization of the free parameter in many PAC-Bayes bounds. We highlight several applications of the main theorem. Firstly, we show that our bound recovers and generalizes previous results. Additionally, our approach allows working with richer assumptions that result in more informative and potentially tighter bounds. In this direction, we provide a general bound under a new *model-dependent* assumption from which we obtain bounds based on parameter norms and log-Sobolev inequalities. Notably, many of these bounds can be minimized to obtain distributions beyond the Gibbs posterior and provide novel theoretical coverage to existing regularization techniques.

PAC-Bayes-Chernon bounds for unbounded losses
Ioar Casado
Luis A. Ortega
Machine Learning Group
Machine Learning Group
Basque Center for Applied Mathematics (BCAM) icasado@bcamath.co org
Computer Science Dept. EPS.
Universidad Autónoma de Madrid
luis ortegaQuam.ee
Aritz Pérez
Andrés R. Masegosa Department Computer Science
Machine Learning Group Basque Center for Applied Mathematics (BCAM) aperezObcamath.co org
Aalborg University arma@cs aau
Abstract
We introduce a new PAC-Bayes oracle bound for unbounded losses that extends Cramér-Chernoff bounds to the PAC-Bayesian setting. The proof technique relies controlling the tails of certain random variables involving the Cramér transform the loss. Our approach naturally leverages properties of Cramér-Chernoff bounds, such as exact optimization of the free parameter in many PAC-Bayes bounds. We highlight several applications of the main theorem. Firstly, we show that our bound recovers and generalizes previous results. Additionally, our approach allows working with richer assumptions that result in more informative and potentially tighter bounds. In this direction, provide general bound under new model- dependent assumption from which we obtain bounds based on parameter norms and log-S log-Sobolev inequalities. Notably, many of these bounds be minimized to obtain distributions beyond the Gibbs posterior and provide novel theoretical coverage existing regularization techniques.
Introduction
PAC-Bayes theory provides powerful tools to analyze the generalization performance of randomized learning algorithms -for an introduction to the subject see the recent surveys of Guedj (2019); Alquier (2024) and Hellström et al. (2023)-. Let θ be model class parametrized by 0 E Rdd With small abuse notation, E will represent both a model and its parameters. Instead of learning a single model, we consider the set of probability measures over our class, M1 (Q), and aim to find the optimal distribution p" E M (+). This approach more robust than finding the single best model
in O and is tightly related to Bayesian and ensemble methods. The learning algorithm infers this distribution from a sequence of n training data points D J which are assumed to i.i.d.
sampled from an unknown distribution vax:) with support X' RR.
Given a loss function : x X' + R., bounding the gap between the population risk T.( ==
[,(e X)] and the empirical risk İ(e, D) := Σn L(O, æ,) of individual models is the standard approach in statistical learning theory.
contrast, PAC-Bayes theory provides high- probabiiyyy bounds over the population Gibbs risk [T.))] in terms of the empirical Gibbs risk E, (. D)) and an extra term measuring the dependence of to the dataset D. This second term involves an information measure -usually the Kullback-Leible divergence K L((ppT) between the data
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

dependent posterior' e M1 and prior т T E (1(@),, chosen before observing the data. These bounds hold simultaneously for every p É (O). hence minimizing them with respect to P provides an appealing approach to derive new learning algorithms with theoretically sound guarantees.
)and
The foundational papers PAC-Bayes theory (Shawe- Tayle- and Williamson, 1997; McAllester, 1998, 1999; Seeger, 2002) worked with classification problems under bounded losses, usually the zero-one loss. This framework was significantly extended in Catoni (2007), who introduced some of the first bounds for unbounded losses. McAllester's ' bound (McAllester, 2003) is one of the most representative results for bounded losses: for any E (M) independent of D and every 8 E (0. 1). we have
KL(pTT) + log 2/R
B [T((0) (D) +
2n
simultaneously for every / E (e))). where the above inequality holds with probability no less than 1 8 over the choice of D ~ v². Another significant example under the bounded loss assumption is the Langford- Maagerr bound after (Langford and Seeger, 2001; Seeger, 2002; Maurer, 2004) Under the same conditions as above,
kl (E), - [(pTT + log 2y 5
O).
n
where kl is the so-called binary-kl distance, defined as kl(a, == aln (1- in
These bounds illustrate typical trade-offs in PAC-Bayes theory. In (1), the relation between the empirical and the population risk is easy to interpret because the expected loss is bounded by the empirical loss plus complexity term. More crucially, the right-hand side of the bound can be directly minimized with respect to the posterior p. resulting in the Gibbs posterior (Guedj, 2019). Conversely, (2) is known to be tighter than (1), but it is not straightforward to minimize because it requires inverting kl (L, et al., 2018)
several techniques deal with this issue (Thiemann et al., 2017; Reeb
With the trade-offs among explainability, tightness, and generality in mind, the PAC-Bayes community has come up with novel bounds with applications in virtually every area of machine learning, ranging from the study of particular algorithms -ineear regression (Alquier and Lounici, 201 1; Germain et al., 2016), matrix factorization (Alquier and Guedj, 2017), kernel PCA (Haddouche et al., 2020), ensembles (Masegosa et al., 2020; Wu et al., 2021; Ortega et al., 2022) or Bayesian inference (Germain et al., 2016; Masegosa, 2020)- and generie versions of PAC- theorems (Bégin et al., 2016; Rivasplata et al., 2020) to the study of the generalization of deep neural networks (Dziugaite and Roy, 2017; Rivasplata et al., 2019).
Such applications often require relaxing the assumptions of the classical PAC- MAC-Bayesian framework, such as inteeeddddendttt priors, i.i.d. data or bounded losses. Here we are interested in the case of PAC-Bayes bounds for unbounded losses such as the squared error loss and the log-loss-
PAC-Bayes bounds for unbounded losses
The main challenge of working with unbounded losses is that one needs to deal with an exponential moment term which cannot be easily bounded without specific assumptions about the tails of the loss. The following theorems, fundamental starting points for many works on PAC-Bayes theory over unbounded losses, illustrate this point.
Theorem 1 ((Alquier et al., 2016; Germain et al., 2016)). Let ग E ()) be any prior independent
of D. Then, for any d E (0, 1) and any X O, with probability least 1 - 8 over draws of D v."
1 E, (L()) < E,(((D,)) + An
KT(pTTT) + log [A. 8
simultaneously for every p (I). Here (a. := E, (m (I.(0)-
'n PAC- theory the term posterior is used to emphasize that p E (M) depends on training data, and does not necessarily refer to the Bayesian posterior. We refer the reader to Germain et al. (2016) for discussion of the relation between PAC- Bayysian and Bayesian methods.

---

This is an oracle bound, because (A) depends on the data generating distribution v". To obtain empirical bounds from the theorem above, the exponential term f.., is usually bounded by making the appropriate assumptions on the tails of the loss, such as the Hoeffding assumption (Alquier et al., 2016), Sabb-aussiantty (Alquier and Guedj, 2018; Xu and Raginsky, 2017), sub-gamma (Germain et al., 2016) or sub-exponential (Catoni, 2004). See Section 5 of Alquier (2024) for an overview.
Many of these assumptions are generalized by the notion that the cumulant generating function (CGF) of the (centered) loss, Aa A), exists and is bounded (Banerjee and Montúfar, 2021; Rodríguez-Gálvee et al., 2024). Remember that we say (A exists if it bounded in some interval [o, b) with b >
Definition 2 (Bounded CGF). A loss function é has bounded CGF if for all 0 E O there a convex
and continuously differentiable function vi : [0, + R+ such that (0) = (0(0) = 0 and
(A log By [cA12(0))((0000 (A) for all À E [0,
We will say that loss function E is ei-bounded if it satisfies the above assumption under the function sb. In this setup, Banerjee and Montúfar (2021) obtain the following MAC-Bayes bound under the Bounded CGF assumption:
Theorem 3. Let E be loss with v--bounded CGF and E MM) any prior independent of D. Then, for any ō E (0, 1) and any X E (0, b), with probability al least - ô over draws of D ~ v",
[p([(()]= S (.( 0)] + KL(p)T) log
(A)
An
A
simultaneously for every P E (O).
Theorems I and 3 illustrate a pervasive problem of many PAC-Bayes bounds for unbounded losses: they often depend on a free parameter À > -see for example (Alquier et al., 2016; Hellström and Durisi, 2020; Guedj and Pujol, 2021; Banerjee and Montúfar, 2021; Haddouche et al., 2021) The choice of this free parameter is crucial for the tightness of the bounds, and it cannot be directly optimized because its choice is prior to the draw of data, while the optimal À would be data-dependent.. The standard approach is to optimize over a grid using union-bounde arguments. but the resulting is not guaranteed to be optimal. Seldin et al. (2012) carefully design the grid so that the optimal À is inside its range, but their work only deals with bounded losses. See the discussion in Section 2.1.4 of Alquier (2024) for an overview.
Recently, Hodríguez-Gálver et al. (2024) improved the union-bound approach for the bounded CGF scenario using a convenient partition of the event space. However, their optimization remains approximate. Hellström and Durisi (2021) could circumvent this problem for the particular case of sub-Gaussian losses, but the exact optimization of X for the general case remains an open question. A positive result in this direction would lift the restriction of having to optimize À over restricted grids or using more complex approaches.
The use of the bounded CGF assumption entails another potential drawback: both uniform control of the CGF (A < (A) for every 0 E e and integrability assumptions as in Alquier et al. (2016) E. [Ao] < C' for some constant C-, necessarily drop information about the different concentration properties of individual models. For example, Masegosa and Ortega (2023) show that within the class of models defined by the weights of common neural networks, the behavior of their CGFs and hence of their Cramér transforms, which control generalization error via Cramér- Chernoff bound- varies significantly. As Figure 1 shows, uniformly bounding the CGFs can result in loose worst-case bounds that ignore the properties of the models that interest us most.
The bounds of Seldin et al. (2012) and Haddouche et al. (2021) partially address this issue including average variances and model-dependent range functions to their bounds, which account for the fact that differrnt models have difffrrnt CGFs. However, the former only applies to bounded losses, while the latter cannot be exploited to obtain better posteriors because their model- dependdd function only impacts the prior. Outside the PAC-Bayes framework, Jiao et al. (2017) generalized the bounded CGF assumption, but their result only applies to finite model sets.
Exploiting these differences among models within the same class could be an important line of research in PAC-Bayes theory. This approach would provide more informative generalization bounds, paving also the way for the design of better posteriors. This is one of the main appeals of our work.
3

---

Ap(A)
Metric/ Model
Standard
Random
Zero
0.2
Staodard
Train Acc.
99.9%
100%
100%
10.0%
L2
Test log-loss
Test Acc.
84.3%
0.65
86.6%
0.49
10.1%
5.52
10.0%
2.30
0.1
Zero
Randora
Eg-norm
304
200
311
0
Ep |V 0)
839
519
4112
0
(E 0))
3.58
2.21
12.6
0
0.0
0.0
0.2 0.3
0.5
Figure 1: Models with very different CGF's coexist within the same model class. On the left, we display several metries for InceptionV3 models trained on CIFAR 10 without regularization (Standard) and with L2 regularization (L22. Random refers to model learned over randomly reshuffled labels and Zero refers to a model where all the weights are equal to zero. For each model, the metries include train and test accuracy, test log-loss, fn-norm of the parameters of the model, the variance of the log-loss function, denoted (f(((z, 0)), and the expected norm of the input-gradient denoted E, [ (zz, 0)]@]- On the right, we display the estimated CGFs of each model, following Masegosa and Ortega (2023). Note how models with smaller variance V(((z, 0)), f--norm or input- gradient norm E,, [(vr, 0)] have smaller CGFs. Bounds derived from Theorem 7 naturally exploit these differences. Experimental details in Appendix C.
Overview and Contributions
The main contribution of this paper is Theorem 7, novel (oracle) PAC-Bayes bound for unbounded losses which extends the classic Cramér-Chernos bound the PAC-Bayesian setting. The theorem is introduced in Section 3, while Section contains the necessary prerequisites. As far as we know, the proof technique based on Lemma 6 also novel and can be of independent interest.
We discuss the applications of our main theorem in sections 4 and 5. First, we show that our bound allows exact optimization of the free parameter À incurring in a log n penalty without resorting union-bound approaches. In the case of bounded CGFs, we recover bounds which are optimal up that logarithmic term. We also show that versions of many well-known bounds -such as the Sangford-Seggee bound- can be recovered from Theorem 7.
In Section 5, show how main theorem provides a general framework to deal with richer assumptions that result novel, more informative, and potentially tighter bounds. In Theorem 11, generalize the bounded CGF assumption that there is different bounding function, (0..)., for the CGF of each model. We illustrate this idea in three cases: generalized sub-Gaussian losses, norm-based regularization, and input-gradient regularization based on log-Sobolev inequalities. Remarkably, the bounds in Section can be minimized with respect to E MM (M),)) resulting in optimal posteriors beyond Gibbs' and opening the door to the design of novel algorithms.
Appendix A contains the proofs not included in the paper.
2 Preliminaries
In this section we introduce the necessary prerequisites order to prove our main theorem. Its proof relies in controlling the concentration properties of each model in O using their Cramér transform. Definition& 4. Let / C IR be an interval and f R convex function. The Legendre transform of f is defined as
(a) == sup {Aa - [(A),, Va R.
xet
Following this definition, the Legendre transform of the CGF model θ is known as its Cramér transform:
(a(a)= = sup {Aa Ao(A)), Va E R.
xE(o,6)
Throughout the paper, we will use the abbreviation gen(0, D) to denote the generalization gap L( i(D,00 0). in order to make the notation more compact. Cramér's 's transform provides non-

---

asymptotic bounds on the right tail of gen D) via of Boucheron et (2013) Section 2.2 of Dembo and Zeitouni (2009)
theorem see Section 2.2
Theorem (Cramér-Chermoff) For any + and I,
Pun (gen 0, D) 2 a) S E -Ag(o)
(6)
Furthermore, the inequality is asymptotically tight up to paannnntallaactonn
Importantly, Cramér-Chernoffi bound can be inverted to establish high-probability generalization bounds: for any E (0, 1),
Pyr gen(O. = (H, log 1og 2 1-66
where (Ag)=1 is the inverse of the Cramér transform. We cannot directly use Theorem 5 to obtain PAC-Bayes bounds, because we need a bound which uniform for every model. The following lemma will be our main technical tool for this purpose.
Lemma 6. For any E A and 2 O, we have
( Pur (nAb(gen(O) D)) 20) S PXxexp(1)) (x (x2)).
This way of controlling the survival function of Ag(gen(O, ( D)) for every 0 E will allow us to bound an exponential moment term in main theorem.
3 MAC-Bayes-Chernol bound
As we hinted above, instead of directly introducing boundedness conditions on the loss or its CGF, we stay the realm of oracle bounds, aiming to provide a flexible starting point for diverse applications. A key element of our theoretical approach is the averaging of the CGFs with respect to posterior distribution. For any posterior distribution
(M), we may consider the expectation of the CGF, A (A)), as in Jiao et al. (2017). In analogy to the standard definition, we define the Cramér transform of a posterior distribution p as the following function:
(a)
sup {Aa - EA(A) E X.
8
Since the CGFs (A) are convex and continuously differentiable with respect to X, their expectation E, [AA(((()) (A)] retains the same properties. Hence according to Lemma 2.4 in Boucheron al. (2013), the (generalized) inverse of A exists and can be written as
E Ao (A)) (A
(A (8)
inf
(E(O,M)
X
With these definitions in hand, are ready to introduce main result, novel (oracle) PAC-Bayes bound for unbounded losses:
Theorem (PAC-Bayes- OPAC-Bayes-Chernoff Chernoff bound). Let N (M) any prior independent of D. Then, for any å E (0, 1), with probability at least 1 over draws of D ~ 1²,
(L(p)T) + log B A(n 1)
[A(A
< [D)
inf XE(0,6)
X
simultaneously for every p (O).
The above result gives oracle PAC-Bayes analogue to the because the second term of the right hand side of the inequality corresponds with the inverse of A as described in equation (9). Theorem 7 shows that bounds like the one given in Theorem 3 can hold simultaneously for every penalty, virtually the same as if we were optimizing over a uniform grid of size using union-bound arguments. Although the dependence union bound arguments can be improved to log()g((1)) (Alquier, 2024), our optimization is exact.
' bound of equation (7).
and hence optimized with respect to X- by paying log(n)
5

---

Furthermore, Theorem 7 also shows that the postenior minimizing its hight-hand-sie is involved in three-way trade-off: firstly, must explain the training data due to P (T( 0)}; secondly, it must be close the prior due to the KL term [(ppz);; and lastly, it must place its density in models with lower CGF due to the [A]] term. We note that the first two elements are standard most PAC-Bayesian bounds, but the role the CGF defining an optimal posterior p is novel compared to previous bounds. We explore the implications of this fact in Section 5.
Relation with previous bounds
We first relate Theorem 7 to previous bounds. As first application, show how some well-known PAC-Bayes bounds can be recovered from ours. When the distribution of the loss is known, we can often compute its Cramér transform. This happens be the case with the zero-one loss, where we recover Langford-Seeger bound (Seeger, 2002, Theorem 1).
Corollary 8. Let l be the 0 1 loss and π E ()) be any prior independent of D. Then, for any ò E (0, 1), with probability at least 1 over draws of D v".
(L(pT) TT) + log 2
kl (L, (0, D)I, E(((())
<
n-
simultaneously for every p E (e)
The dependence in Corollary 8 was further improved by Maurer (2004). However, our version enough to illustrate the role played by Crámer transforms in obtaining tight PAC-Bayes bounds, which is a recent line of work by Foong al. (2021) and Hellström and Guedj (2024).
When the loss of bounded CGF -recall Definition 2-, Theorem 7 results in a generalization of
Theorem 3, where the bound holds simultaneously for every À (0,b) b) with log penalty.
Corollary 9. Let E be loss function with --bounded CGF. Let E (e) be any prior independent of D. Then, for any 8 E (0, 1), with probability at least 1 - over draws of D v",
x) + log n 8
(A) X
[g]((0) < E,L inf
AE(0,6)
X(n - 1)
simultaneously for every p (1)
Proof. Directly follows from the definition of gi-bounded CGF and Theorem 7.
Corollary is the first PAC-Bayes bound that allows exact optimization the free parameter 2 for the general case of losses with bounded CGF without resorting to mnion-bound approaches (Seldin et al., 2012; Rodríguez-Gdii Galvez et al., 2024), which cannot guarantee an exact minimization. Although in the particular case of sub-Gaussian losses the log n penalty is worse than that in Hellström and
Durisi (2021), when KL(p/T) Vōn/c Corollary tighter than the general Theorem 14 in Rodríguez- Gálvez et al. (2024). We instantiate Corollary 9 in the case of sub-Gaussian and sub-ga gamma losses in the Appendix B.
PAC-Bayes bounds under model-deppndent assumptions
As discussed in the introduction, most boundedness conditions used to bound the exponential moment term in Theorem 7 discard information about the statistical properties of individual models. In this section, we show that the structure of Theorem 7 allows for a more fine- fineggrained control of the CGFs, resulting in potentially tighter and more informative bounds. We start by generalizing Definition 2.
Definition 10 (Model-dependent bounded CGF). A loss function é has model-dependent bounded CGF for each E O, there is a convex and continuously differentiable function () X) such that (0, 0) (' 0) = 0 and for any X E b).
(A( = log E, [e (T.(0) [(mm)))((mmm))) oim < (0 X)-
(10)

---

As motivated in Figure and in opposition to Definition 2, this new condition acknowledges the possibility of having different bounding functions, (0 X). for each (A))
Using this definition, we can easily exploit Theorem to derive the following bound:
Theorem 11. Let be a loss function satisfying Definition 10. Let π E MM(@)) be any prior independent of D. Then, for any 8 (0, 1), with probability at least - over draws of D ~ v²,
over
[K(ppT) + log # +
[0,
[p]] - E,IL(D,
inf XE(0,b]
(11)
A(n -
A
simultaneously for every p E (1))).
Proof. The proof is analogue to that of Corollary 9.
This theorem can be understood as a PAC-Bayesian version of Theorem 2 in Jíao et al. (2017), where we allow infinite model classes. Note that if we tried to exploit this model-dependent CGF assumption on other oracle bounds, as the one shown in Theorem 1, we would end with an empirical bound where the e A) term would be exponentially averaged by the prior, In E, [e))), instead of having the more amenable term Ep (e, A) which directly impacts on the choice of the optimal posterior p².
As discussed in Section 3, the posterior distribution in Theorem 11 is involved in three- trade-off which has the potential to result in tighter bounds and the design of better posteriors. It is worth noting that the posterior minimizing the bound in Theorem 11 is not the standard Gibbs posterior.
Proposition 12. If we fix some À > O, the bound in Theorem 11 can be minimized with respect to E (O). The optimal posterior
00) x क (0) exp -n -n
(12)
Observe that under the posterior in Proposition 12, the maximum a posteriori (MAP) estimate is
1 L(D.0) 0) + (0, 1 In (0)
i MAP = arg min
As we will illustrate below, the extra term, (0, A), can often be understood as a regularizer. In what remains, we exemplify the general recipe of Theorem 11 in several cases. To start providing concrete
intuition, we instantiate Corollary 11 in the case of sub-Gaussian losses.
Generalized sub-Gaussian losses
is well known that if X is a Pr-suu-Gaussine random variable, we have V(X) I a² (Arbel et al., 2020). In many cases, it might not be reasonable to bound (.(0 X)) S 0² for every 0 O, because the variance of the loss function highly depends on the particular model, as illustrated in Figure 1. This is where Corollary 11 comes into play: may assume that (6, is -ub- Gaussian for each f E @ In this case the variance proxy (0) is specific for each model, leading to the following bound:
Corollary 13. Assume the loss E X) is (0)))ssub Gaussian. Let MM be any prior independent of D. Then, for any 8 (0, 1), with probability at least 8 over draws of ~ v
KL (/T))
log
Ep(((O)) < E,(L(D,O)) + 2E, (0)22
(13)
n
simultaneously for every p (M).
Proof. Use Theorem 11 and the fact that (0, A) 1²02(0) 2
Then optimize X.
This result generalizes sub-Gaussian PAC-Bayes bounds Corollary 2 in Hellström and Durisi (2021) or Corollary 19- and shows that posteriors favoring models with small variance-proxy, o² (()), generalize better. It is, therefore, potentially tighter than previous results, because the o²
7

---

factor in standard sub-Suuseee Gaussian bounds is a worst-case constant, while Corollary 13 exploits the fact that some models have much smaller variance-pron proxx than others.
Analogous bounds can be straighfforwardy derived for generalized sub-gamma or sub-exponential losses, but Theorem 11 is not limited to explicit tail assumptions the loss. 'hhe following subsections explore model-dependent assumptions on Ag (A) that result in novel PAC-Bayes bounds involving well-known regularization techniques.
L2 regularization
We now introduce bounds based on the norm of the model parameters. For that purpose we use the following standard assumption in machine learning (Li and Orabona, 2019). Assumption (Parameter Lipschitz). The loss function (ar, 0) is M-Lipschitz with respect to 0, that is, for any 0 E θ and any æ E X' we have (V 0) 12 < M.
the model class is parametrized in such a way that the model with null parameter vector has null variance -...., (E(x,, 0)) O, which is the case of neural net with null weights-, then, as shown in Masegosa and Ortega (2023), we can derive the following model-dependent bound for the CGF:
(14) This case further illustrates the idea motivated in the introduction: bounding the CGFs with model-dependent proxies for generalization. Figure illustrates how models with smaller norm has increasingly smaller CGFs.
(A 2MA
Using Equation (14) we obtain the following generalization bound penalizing model's L.2norm: Corollary 14. If Assumption holds, then for any prior distrihution (M) independent of D)
and any E (0, 1), with probability at least 1 over draws D ~ v²,
KL(pTT) log ah
= =E,LL(D,)) +
2ME 10
(15)
72 1
simultaneously for every p E (1)
Proof. The result follows from using (0, A) = 2M in Theorem 11 and optimizing X.
Corollary 14 shows that models with smaller parameter norms generalize better, and provides PAC- Bayesian certificates for norm-basee regularization. Many other PAC-Bayesian bounds contains different kind of parameter norms (Germain et al., 2009, 2016; Neyshabur et al., 2017), but their parameter norm term is always introduced through the prior e.g., using zero-centered Gaussian prior distribution The novelty here that this parameter norm term appears independently of the prior as result of Theorem 11.
According Proposition 12, the MAP estimate of the optimal posterior is, OMAP arg ming () + 2M 1013
- X[n (0)), which is the result of L2-regularization with
tradeoff parameter 2M
Gradient-based regularization
We finish this section providing novel bounds based on log-Sobolev inequalities that include gradient term penalizing the sensitivity of models to small changes in the input data. First, let us simplify the notation for this section. We use 2 -E V=((x,,)) 1 to denote the expected and empirical (squared) gradient norms of the loss.
V 0)ll and |
Including gradient-based penalization is the idea behind input-gradient regularization (Varga et al., 2017), which minimizes objective function of the form L(D.0) + 2 where k > is trade-off parameter. This approach often used to make models more robust against disturbances in input data and adversarial attacks (Ross and Doshi- Deshi-Velez, 2018; Finlay and Oberman, 2021).
We make the connection between PAC-Bayes bounds and gradient norms assuming that and satisfy certain log-Sobolev incquality (Chafai, 2004).

---

Assumption 2 (log-Sobolev). For any 0 E θ and any X > O, we have
C Ao(A) S 2 1 el 2+ for some C' C>> 0.
For example, Assumption 2 holds when v is strictly uniformly log-concave, as shown in Corollary 2.1 of Chafai (2004) -this case includes the Gaussian and Weibull densities (Saumard and Wellner, 2014).. We also try to empirically verify Assumption 2 for certain class of neural networks in Appendix C.2. Assumption 2 is going to be our model-dependent bound on the CGF. We first provide a bound for expected gradients.
Theorem 15. If A'sssmmption 2 is satisfied, then for any prior distribution E (M) independent of D and any 81 E (0, 1), with probability at least 61 over draws D ~ v²,
(L(p)(=) log 01
Ep[L(0)] (D) 0)] + 2C v
(16)
n
simultaneously for every (M)
Proof. Follows from the application Assumption to Theorem 11 and the optimization of X.
This bound shows that under certain regularity conditions posteriors favoring models with smaller expected gradients, = generalize better, which the heuristic behind input-gradien regularization (Varga et al., 2017). However, Theorem 15 is still an oracle bound. We can obtain new, fully empirical one we concatenate Corollary 15 with a PAC-Bayes concentration bound for E. [I]V= This can be done if we assume that the loss is Lipschitz. w.r.t. the input-data.
Assumption (Input-data Lipschitz). For any 0 E θ and for any æ E X, we have V 0)1 s L.
Assumption is satisfied in standard deep neural network architectures, and the Lipschitz constant can be efficiently estimated (Virmaux and Scaman, 2018; Fazlyab et al., 2019).
Theorem 16. If Assumptions and 3 are satisfied, then for any prior distribution π E (M)(@) independent of D and any 8 (0, 1); with probability at least 1 5 over draws of D v",
E.p [T[]) S E,IL((D,)) 0)) V 2C [
K(p, V2CL. K(p
simultaneously for every E (O),), where Kip,T,n, 0) = Kog n-1
With minimal modifications, the result above also holds under the assumption that on-average gradients are bounded, ,I < g. or when [V,e(0, X) are sub-Gaussian.
Similar bounds with imput- gradients were first introduced by Gat al. (2022) under the assumption that the underlying distribution of data was a mixture of Gaussians plus technical "per-label loss balance" assumption. However, Theorem 16 is, as far as we know, the first empirical PAC-Bayes bound for free parameter and explicitly relate the gradients with the generalization ability of the posterior (e). The recent work of Haddouche et al. (2024) also includes gradient terms in their bounds, but they are gradients with respect to the model parameter, not input-gradients.
Furthermore, in contrast with Gat et al. (2022), our bounds optimize the
As for the optimal posterior p", if we minimize the bound in Theorem 15 for a fixed A >> O, the MAP estimate in Proposition 12 is 0 = arg ming (LD 0) + X | V 2 2 X(x-1) In I0)), which is the result of
1
regularization with trade-off parameter AC
In conclusion, the approach suggested by Theorem 11 not only provides novel insights in the form of tight bounds or PAC-Bayesian interpretations of previously known algorithms- it also hints towards the design of new regularized learning algorithms with solid theoretical guarantees.
6 Conclusion
We derived a novel PAC-Bayes oracle bound using basic properties of the Cramér transform Theorem 7-, In general, our work aligns with very recent literature Gallee et al.,

---

2024; Hellström et al., 2023) that highlights the importance of Cramér transforms in the quest for tight PAC-Bayes bounds. This bound has the potential to stepping stone in the development of novel, tighter empirical PAC-Bayes bounds for unbounded losses. Firstly, because it allows exact optimization of the free parameter bound approaches. But, more relevantly, because it allows the introduction of flexible, fine-grained, model-dependent assumptions for bounding the CGF Theorem 11- which results in optimal distributions beyond Gibbs' posterior. The importance and wide applicability of this result have been illustrated with three model-dependent assumptions: generalized sub-Gausse Gaussian losses, bounds based on parameter norms, and graddinndss based on log- So--ooolev inequalities. In the last case introduce PAC-Bayes bounds including empirical input input-gradients gradients norms.
without the need for more convoluted union-
Limitations and future work
A limitation of our approach is that the we are implicitly assuming that E ()) is light-tailed (equivalently, sub-exponential), as every Chaméf-Chernoff bound. This is only partially true. Although there are specific studies for heavy-tailed losses (Alquier and Guedj, 2018; Holland, 2019; Haddouche and Guedj, 2023; Chugg et al., 2023), we avoid this limitation because we are only interested in the right tail of gen 0, D) that is, P)()(0)= L(D, 0) 2 a) for a 2 0- This is done by defining the CGF only for À 2 0. In this way, [0)) guarantees the existence of [A(AA(A) in Theorem This approach motivated by the fact that most state-of-the-art models lie in the interpolating regime, hence P. (ī,(D, 0) L( 2 a) for a 2 0 has less practical importance. However, the case where one looking for two-tailed bounds, our work is restricted to sub-exponential losses. See the discussion on Section 4.2.1 of Zhang et al. (2024).
show in Remark 17, the finiteness of
Given the generality of Theorem 7, the dependence of the logarithmic penalty term in the bound may be suboptimal in certain cases, as discussed in Section 4. Going beyond Lemma 6 and improving this dependence is one of the main open tasks.
Our results provide systematic approach for integrating general model-dependent CGF bounds into PAC-Bayes theory, and can open exciting new research lines: they can provide a PAC-Bayesian extension of the work of Masegosa and Ortega (2023), which studies the effects of different regular- ization techniques and the role of invariant architectures, data augmentation and over-parametriizttoo bounds be applied to unbounded losses such the log-loss, it could
in generalization. Since be interesting to apply them in Bayesian setting (Germain et al., 2016) in order to study the relation between marginal likelihood and generalization (Lotfi et al., 2022).
10

---

Acknowledgments and disclosure of funding
IC acknowledges financial support from the Basque Government through the IKUR pro- gram. LO acknowledges financial support from project BID2022-13986NNB-J funded by MCIN/ AEI/ 10. 10000 1033/EEEE, UE and from the Autonomous Community of Madrid (ELLIS Unit Madrid), AP acknowledges financial support by the Basque Government through the BERC 2022-2025 program and Elkartek program (KK-2023/00038), and by the Ministry of Science and Innovation: BCAM Severo Ochoa accreditation CEX2021 10X2021-00111 142- S/MICIN/AEV/O.II MMMCINN/EE/1O.100//5000000 1030000000000000000000000 AM acknowledges financial support from Grant PID2022- 139293NB-C3I funded by MCIN/AEV/1..13039//000 100011033 and by ERDF A way of making Europe.
References
Pierre Alquier. User-friendly introduction to PAC-Bayes bounds. Machine Learning, 17(2):174-303, 2024.
Foundations and Trendso in
Pierre Alquier and Benjamin Guedj. An oracle inequality for quasi-Bayesialt nonnegative matrix factorization. Mathematical Methods of Statistics, 26:55-67, 2017.
Pierre Alquier and Benjamin Guedj. Simpler PAC-Bayesian bounds for hostile data. Machine Learning, 107(5)887-902, 2018.
Pierre Alquier and Karim Lounici. PAC-Bayesian bounds for sparse regression estimation with exponential weights. Electronic Journal of Statistics, 5:127 145, 2011.
Pierre Alquier, James Ridgway, and Nicolas Chopin. On the properties of variational approximations of Gibbs posteriors. Journal of Machine Learning Research, 17(1):8374-88) 8414, 2016.
Julyan Arbel, Olivier Marchal, and Hien D Nguyen. On strict sub- sub-Gaussianity, optimal proxy variance and symmetry for bounded random variables. ESAIM: Probability and Statistics, 24:39-55, 2020.
Pradeep Kr Banerjee and Guido Montúfar. Information complexity and generalization bounds. In 2021 IEEE International Symposium on Information Theory (ISIT), pages 676-681, 681. IEEE, 2021.
Luc Bégin, Pascal Germain, François Laviolette, and Jean-Francis Roy. MAC-Bayesian bounds based on the Rényi divergence. In Artificial Intelligence and Statisties, pages 435 444. PMLR, 2016.
Christopher M. Bishop. Pattern Recognition and Machine Learning. Springer New York, NY, 2006.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford University Press, 2013.
Olivier Catoni. Statistical learning theory and stochastic optimization: Ecole d' Eté de Probabilités de Saint Flour, XXXI-2001 volume 1851 of Lecture Notes in Mathematics. Springer Science Business Media, 2004.
Olivier Catoni. PAC- (CC-Byysian Supervised Classification: The Thermodynamics of Statistical Learning, volume 1277 of IMS Lecture Notes-Monograph Series. 2007.
Djalil Chafai. Entropies, convexity, and functional inequalities, on d-entropies and d-soboley inequalities. Journal of Mathematics of Kyoto University, 44(2):325-363, 2004.
Ben Chugg, Hongjian Wang, and Aaditya Ramdas. A unified recipe for deriving (time-uniform) PAC-Bayes bounds. Journal of Machine Learning Research, 24(372):1-61, 2023.
Amir Dembo and Ofer Zeitouni. Large deviations techniques and applications, volume 38 of Stochastic Modelling and Applied Probability. Springer Science Business Media, 2009.
Monroe D Donsker and SR Srinivasa Varadhan. Asymptotic evaluation of certain Markov process expectations for large time, Communications on Pure and Applied Mathematics, 28(1):1-47 1975.
11

---

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 arXiv: 1008,, 2017.
Paul Embrechts and Marius Hofert. A note on generalized inverses. Mathematical Methods of Operations Research, 77:423-4322 2013.
Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas. Efficient and accurate estimation of Lipschitz constants for Deep Neural Networks. Advances in Neural Information Processing Systems, 32, 2019.
Chris Finlay and Adam M Oberman. Scaleable imput gradient regularization for adversarial robustness. Machine Learning with Applications, 3: 3:100017, 2021.
Andrew Foong, Wessel Bruinsma, David Burt, and Richard Turner. How tight can PAC-Bayes in the small data regime? Advances in Neural Information Processing Systems, 34:4093-4105, 2021.
Nina Gantert, Steven Soojin Kim, and Kavita Ramanan. Cramér's theorem is atypical. In Gail Letzter, Kristin Lauter, Erin Chambers, Nancy Flournoy, Julia Elisenda Grigsby, Carla Martin, Kathleen Ryan, and Konstantina Trivisa, editors, Advances in the Mathematical Sciences, pages 253-270, Cham, 2016. Springer International Publishing.
Itai Gat, Yossi Adi, Alex Schwing, and Tamir Hazan. On the importance of gradient norm in PAC-Bayesian bounds. Advances in Neural Information Processing Systems, 35:16068-16081 2022.
Pascal Germain, Alexandre Lacasse, Mario Marchand, Sara Shanian, and François Laviolette. From PAC-Bayes bounds to KL regularization. Advances in Neural Information Processing Systems, 22, 2009.
Pascal Germain, Francis Bach, Alexandre Lacoste, and Simon Lacoste-Julien. PAC- Bayessaa theory meets Bayesian inference. Advances in Neural Information Processing Systems, 29, 2016.
Benjamin Guedj. A primer on PAC-Bayesian learning, arXiv preprint arXiv: 1901:053900.. 2019.
Benjamin Guedj and Louis Pujol. Still no free lunches: the price to pay for tighter PAC-Bayes bounds. Entropy, 23(1 1529, 2021.
Maxime Haddouche and Benjamin Guedj. PAC-Bayes generalization bounds for heavy-tailed losses through supermartingales. Transactions on Machine Learning Research, 2023.
Maxime Haddouche, Benjamin Guedj, and John Shawe-Taylor. Upper and lower bounds the performance of kernel PCA. arXiv preprint arXiv:2012. 10366, 10369, 2020.
Maxime Haddouche, Benjamin Guedj. Omar Rivasplata, and John Shawe-Taylor. PAC-Bayes unleashed: Generalisation bounds with unbounded losses. Entropy, 23(1))13330, 2021.
Maxime Haddouche, Paul Viallard, Umut Simsekli, and Benjamin Guedj. A PAC-Bayesing link between generalisation and flat minima. arXiv preprint arXiv:2402.08500. 2024.
Fredrik Hellström and Giuseppe Durisi. Generalization bounds via information density and condi- tional information density. IEEE Journal on Selected Areas in Information Theory, 1(3):824-39, 2020.
Fredrik Hellström and Benjamin Guedj. Comparing comparators in generalization bounds. In International Conference on Artificial Intelligence and Statistics, pages 73-81. PMLR, 2024.
Fredrik Hellström and Giuseppe Durisi. Corrections to "Generalization bounds via information density and conditional information density". IEEE Journal on Selected Areas Information Theory, 203):1072-1773 2021.
Fredrik Hellström, Giuseppe Durisi, Benjamin Guedj, and Maxim Raginsky. Generalization Bounds: Perspectives from Information Theory and PAC-Bayes. arXiv preprint arXiv:2309.0433 2023.
12

---

Matthew Holland. PAC-Bayes under potentially heavy tails. Advances in Neural Information Processing Systems, 32, 2019.
Jiantao Jiao, Yanjun Han, and Tsachy Weissman. Dependence measures bounding the exploration bias for general measurements. In 2017 IEEE International Symposium on Information Theory (ISIT), pages 1475-1479. IEEE, 2017.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. Technical report, Toronto, ON, Canada, 2009.
John Langford and Matthias Seeger. Bounds for averaging classifiers. Technical report, School of Computer Science, Carnegie Mellon University, 2001.
Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In The 22nd International Conference on Artificial Intelligence and Statisties, pages 983-992. PMLR, 2019.
Sanae Lotfi, Pavel Izmailov, Gregory Benton, Micah Goldblum, and Andrew Gordon Wilson. Bayesian model selection, the marginal likelihood, and generalization. In International Con- ference on Machine Learning, pages 14223-14247) PMLR, 2022.
Andrés Masegosa, Stephan Lorenzen, Christian Igel, and Yevgeny Seldin. Second order PAC- Bayesian bounds for the weighted majority vote. Advances in Neural Information Processing Systems, 33:5263-5211 2020.
Andrés R Masegosa and Luis A Ortega. PAC-Chemoff Bounds: Understanding Generalization in the Interpolation Regime. arXiv preprint arXiv:2306.1044 2023.
Andrés Masegosa. Learning under model misspecification: Applications to variational and ensemble methods. Advances in Neural Information Processing Systems, 13:5479-5491 2020.
Andreas Maurer. A note on the PAC Bayesian theorem. arXiv preprint cs/04/ 1099, 2004.
David A McAllester. Some PAC-Bayesian theorems. In Proceedings of the 11th annual conference on Computational Learning Theory, pages 230-234. ACM, 1998.
David A McAllester. PAC-Bayesian model averaging. In Proceedings of the 12th annual conference on Computational Learning theory, pages 164-170. ACM, 1999.
David A McAllester. PAC-Bayesian stochastic model selection. Machine Learning, 51:5-21, 2003.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A PAC-Bayesian approach to spectrally-normalized margin bounds for neural networks. arXiv preprint arXiv: 1107.0/70.005500 2017.
Luis A Ortega, Rafael Cabañas, and Andres Masegosa. Diversity and generalization in neural network ensembles. In International Conference on Artificial Intelligence and Statistics, pages 11720-11743. PMIR, 2022.
David Reeb, Andreas Doerr, Sebastian Gerwinn, and Barbara Rakitsch. Learning Gaussian processes by minimizing PAC-Bayesian generalization bounds. Advances in Neural Information Processing Systems, 31, 2018
Omar Rivasplata, Vikram M Tankasali, and Csaba Szepesvari. PAC-Bayes with backprop. arXiv preprint arXiv: 1908000800 2019.
Omar Rivasplata, Ilja Kuzborskij, Csaba Szepesvári, and John Shawe- PAC-Bayes analysis beyond the usual bounds. Advances in Neural Information Processing Systems, - 2020.
Borja Rodríguez-Gáätvzz Ragnar Thobaben, and Mikael Skoglund. More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity. Journal of Machine Learning Research, 25(110):1-43, 2024.
2024.
13

---

Andrew Ross and Finale Doshi- Velez. Improving the adversarial robustness and interpretability of deep neural networks by regularizing their input gradients. In Proceedings of the AAAI conference on artificial intelligence, 2018.
Adrien Saumard and Jon A Wellner. Log-concavity and strong log-concavity: review. Statistics surveys, 8:45, 2014.
Matthias Seeger. PAC-Bayesian generalisation error bounds for Gaussian process classification. Journal of machine learning research, 3(Oct):233- 269, 2002.
Yevgeny Seldin, Nicolò Cesa-Bianchi, Peter Auer, François Laviolette, and John Shawe-Taylor PACC-Baes-Bernstein inequality for martingales and its application to multiarmed bandits. In Proceedings of the Workshop on On-line Trading of Exploration and Exploitation 2, pages 98-111. JMLR Workshop and Conference Proceedings, 2012.
John Shawe- Shawe-Taylor and Robert C. Williamson. A PAC analysis of a Bayesian estimator. In Pro- ceedings of the 10th annual conference on Computational Learning theory, pages 2-9, ACM, 1997.
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages
2016.
Niklas Thiemann, Christian Igel, Olivier Wintenberger, and Yevgeny Seldin. A strongly quasiconvex PAC-Bayesian bound. In International Conference on Algorithmic Learning Theory, pages 466- 492. PMLR, 2017.
Dániel Varga, Adrián Csiszárík, and Zsolt Zombori. Gradient regularization improves accuracy of discriminative models. arXiv preprint 1712:09712 2017.
Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: analysis and efficient estimation. Advances in Neural Information Processing Systems, 31, 2018.
Yi-Shan Wu, Andres Masegosa, Stephan Lorenzen, Christian Igel, and Yevgeny Seldin. Chebyshev- Cantelli PAC-Bayes-Bennets inequality for the weighted majority vote. Advances in Neural Information Processing Systems, 34: 12625-26666,,, 2021.
Aolin Xu and Maxim Raginsky. Information- theorreti analysis of generalization capability of learning algorithms. Advances in Neural Information Processing Systems, 30, 2017.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. International Conference on Learning Representations, 2017.
Xitong Zhang, Avrajit Ghosh, Guangliang Liu, and Rongrong Wang. Improving generalization of complex models under unbounded loss using PAC-Bayes bounds. Transactions Machine Learning Research, 2024.
14

---

A Proofs
We first gather some standard properties of CGFs and Cramér transforms.
Let DAo := {A E R Ao (A) < oo). Under the assumption that there is some À > such that Ag (A) < oC, have DA [0. b) for some b 0. Furthermore, Ag is strictly convex and C on (0, b) (Boucheron et al., 2013, Section 2.2).
In particular, since for any À 0 have Ao := log E, (0(11)))((200))))) I log Ey [e^L[o]] XL(O) < oo because l 2 0, we verify that A = [0, oo) and that Ag strictly convex and C on
(0, 0o).
Remark 17. Observe that the previous proof also shows that E, [[)) < oo is enough to guarantee that [A)] finite for every 2
The following technical result will be important for the proof of Lemma It combines the previous remarks with Lemma 2.2.5(c) of Dembo and Zeitouni (2009). Lemma 18. (a) < oo for any a E (()). Furthermore, Ng is differentiable in (0, ((0).
Proof. We start by proving the finiteness condition. Since Ao is strictly convex on (0, oc), N also strietly increasing on (0, s0). This means that Ng is bijection from (0, 00) to
inf (A), sup A2(()) In other words, for every a E inf (2(2), sup Ag(A) AE(0,00)
(0(0,00)
XE(0,20)
AE(0,00)
the equation (A) has unique solution da (o).
Now consider the function g()) Xa AA). The previous observation means that g'(Xa)
and since g is concave, Ag = sup {Aa - Aa(A)) = 9(xa) < cc.
xE(0,00)
It only remains prove that inf (A) 0 and sup (2) L(0). The first part follows xE(0,
x0)),00)
from the fact that (0) = 0. The second one is equivalent to proving
lim (A) esssup(L(()) ((X)
X+000
where, without loss of generality, we assume that ess inf 8(X, 0) 0. This is also a standard property of CGFs (see, for example, this proof).
Finally, differentiability of Aù follows from its finiteness in [0, (())) and Lemma 6(5) in Gantert et al. (2016).
With the tools we gathered above, we are ready to prove our main technical lemma: Lemma 6. For any 0 E O and 2 O, we have
Py- (nAbgge((O, D)) 20) S Px
( (x2)).
Proof. The proof relies in the properties of generalized inverses. Consider
P D (mAā(gen(O,, D)) 2 a)
for a 2 O. We will separately consider three cases:
Case a/n < SUP)e(o.L(O)) (g(r).
By Proposition 1(5) in Embrechts and Hofert (2013), we have
P (nAn(gen(() D)) 2 a) < Pa (gen D) 2 (A))
and using the Cramér-Chernof bound the right-hand side obtain
PP PDwy (nAg(gen(O, D)) 2 a) se ==-m)(((33)-1a)m)))
15

---

This results in
P Pawer (gn 2a S e
because Ao is continuous (in fact differentiable, see Lemma 18) on a/n and we can apply Proposition (44) in Embrechts and Hofert (2013).
Case 2: a/n (0) Az(x). P P (nAg(gen(O, 2 = Dawn gen((0, D) = L(0))
= Px~ ((X,0) =0)
= =
If Ag (L())) < co, then a/n = (L)) by the lower semi-continuity of Ag. and the result holds. Otherwise it is trivially true.
Case 3: a/n > ()))E(), (1)). In this case
Powea n. (ngggen(OO D)) 2a) PDwn (Ag(gen(0, D)) =x0)
But Až (gen((, (,, D)) can only happen if gen D) L(0) and (L(( = oo, and this means that P DaND gen((0, D) = =(()) = 0.
This concludes the proof.
Now we list every result whose proof is not included in the paper. Theorem PPAC-BayesCChemen bound). Let π (e) any prior independent of D. Then, for any 5 E (0,1), 1), with probability at least 1 over draws of D v",
(L(p)T) TT) + log Aa
[,] S E,LL(D,)) 0)]+ inf xE(0,b)
A(n
X
simullaneously for every p E (e)
Proof. For any posterior distribution E (, and any positive < n, consider
mAz[gen(pp D)), where gen(p, == E, [L LL 0)). The function A,(-) will play a role analogue to the convex comparator function in Rivasplata et al. (2020). Since sup, EX,- S Esup, Xx, it verifies that
(gggge)(p &
D))]
(17)
Applying Donsker-Vart Varadhan's 's change of measure (Donsker and Varadhan, 1975) to the right-hand side of the inequality we obtain
mA (gen(p, D)) I (L(p))) + log E,, (emA3(oen(0.D))
(18)
We can now apply Markov's inequality the random variable E,, (emAAlgen(e.D))) Thus, with probability at least 1 ó,
mA; (gen(p, D)) < (L(p) + log 3 + log E, (emAg(een(.DD)))
(19)
Since æ is data-independent, we can swap both expectations using Fubini's theorem, so that we need bound Eyn (emAg(gen(0.D)) for any fixed have that for any > O,
θ Here is where Lemma comes into play:
P (nAg(gen(0,) D)) 2 " < (x=exp(1) (x 2 m c
Since X exp(1), we get kX ~ exp(:). Thus, multiplying by m.
P Paya (mAg(gen D)) c) S P PXxxxxx (2) x x2c). (
(20)
16

---

which in turn results in for any t 2 1. Finally, since X exp( m have ex Pareto m 1). Thus, for any t 2 1
P (emAblscn(O.D)) 2t) - P exp (#)
c 21)
(21)
P (e (m 2 Puretof _ 1)
x 21)
(22)
Using that for any random variable Z with support Ω S R4, its expectation can be written as
E
P(Z 2 2)d2,
(23)
nn
we obtein the desired bound:
E Daven (e (emAblscn(O.D)))
D (emsgloen(O.D)) 2 2))ol
IP P # a2 (x (x2
E Pareto 1) (X)
m
Observe how the condition < n is crucial because Pareto(1, 1) has finite mean. In conclusion, with probability at least 8 we have
(gen(pp, D)) & KL(ppT) + log n + log 1 8"
(24)
Dividing by setting
and applying (A7) in both sides concludes the proof.
Corollary 8. Let & be the 0-1 loss and E (M) be any prior independent of D. Then, for any 5 E (0, 1), with probability at least 1 - over draws of D ~ v",
(L(pTT + log 2
kl D),
S
n
simultaneously for every (e).
Proof. We know that (0, Bin [())), hence following the approach in Section 2.2 of Boucheron et al. (2013), we obtain
(a) = (L(O) - alL(O))
From the proof of Theorem we have
K KL(pT)) + log
<
(25)
n n-1
and the result follows from the convexity of kl and Jensen's inequality.
Proposition 12. If we fix some X > 0, the bound in Theorem 11 can be minimized with respect to E (O)). The optimal posterior is
(0) α ग. (0) exp { 1---()AALDD) -n- -
(12)
Proof. We can solve the constrained minimization problem using standard results from variational calculus ssee Appendices D and E of Bishop (2006) for succinct introduction-.. We need to minimize the functional
B Ap] == EL(L(D,))) Eo A)]
KL(ppm) log 3 + (((10)10-1)
+
A
A(n 1)
17

---

where y 2 is the Lagrange multiplier. For this purpose, we compute the functional derivative of B wrt p.
BB L(,,0) 200, N(n 1)
(log f +1 + 7.
6p
and find p ()) satisfying 8B.. 0, which results in the desired p" after straightforward algebraic manipulations.
Theorem 16. If Assumptions and 3 are satisfied, then for any prior distribution MM)(O) independent of D and any 8 E (0, 1); with probability at least 1 - over draws of D ~ v",
[[)) & (P( V 2 |1 e
K(p, n1, V2CL. K(p,,,,,0)
simultaneously for every p E M1(@), where K(p, K(p,T,n, n, koip
Proof. By Assumption 3, V L0, 11 S L for any 0 @ and any X note that with this can already obtain a bound that includes a model-dependent Lipschitz constant L(0)- In particular, [ 2 is 4 ---suu--Guusian Thus use Corollary 5.3 in Hellström et al. (2023) and obtain the following BACeB bound:
KT(p) + log / 02
L
Ep V
S Ep
(26)
22
n -
with probability at least - 82.
Now taking ò1 = 62 = the bound in Theorem 15 and the one in (26) hold simultaneously with probability least 1 6. Finally, plugging (26) in Theorem 15 we obtain the desired result.
O
B PAC-Bayes bounds for losses with bounded CGF
Corollary 19. Assume the loss is Then, for any 8 E (0, 1), with probability at least over draws of D v",
Let a E (M)(O) be any prior independent of D).
20 KL(pTT) + log n
[,[z(0)] & {E(LL(D,)) +
simultaneously for every (M).
Proof. Follows from the fact that (18))-((8) V202s for q2-sub-Gaussin random variables (Boucheron et al., 2013, Section 2).
Corollary 20. Assume the loss is (a² cl-sub--gamee gamma. Let Mi(() be any prior independent of D. Then, for any & (0,1), 1), with probability at least over draws of Va
KL(ppT) - log n
KL(pTT) + log
[L() < E,(L(D,))] + 1222
n-1
simultaneously for every (M)
2 + as for (o², (o2,cc)-uub-gaae gamma random variables Proof. Follows from the fact that (15))
(Boucheron al., 2013, Section 2).
18

---

C Experimental details
C.1 Models and data
As for the experimental setting for Figure 1 and the verification of Assumption 2: we have used the small InceptionV3 architecture (Szegedy al., 2016) used in Zhang al. (2017), where the total number of parameters of the model is 1.814.106. We trained the model in the CIFARIO dataset (Krizhevsky et al., 2009) with the default train/test split using SGD with momentum 0.9 and learning rate 0.01 with exponential decay of 0.95. All models are trained for 30.000 iterations of batches of size 200 or until the train loss under 0.005. These settings are selected to ensure that the random label model converges an interpolator. For l regularization, the multiplicative factor is 0.01. We include a Jupyter Notebook in the Supplementary Material with the code for reproducing our experiments and figures.
From the definition the log-loss, we have
Ag (A) In Ey ((4(0)) En [p(y/ 0)^} E, [In p(y) 0)*1,
and we estimate the expectations using the test data:
Ao(A) = In
Σ
p(yl,,
0)^
1
Σ
Inply 0)*
M
M (Dro))
(tte)
We also estimated V()) and V Valll2 using Diest
C.2
Experimental backing for Assumption
We now experimentally evaluate Assumption in the same setup as above. We need show that there is certain C' > O such that for any X >> 0, we have
Aa(A)
for every 0 E @. Since in this case each 0 represents configuration of weights the Inception V3 architecture, cannot strictly verify the assumption for every 0, however, provide empirical backing for its feasibility.
(A We estimate (A) and V with test data and plot 0.5X² 1 x 0
for the three different models introduced in Figure (in the case of Zero the inequality trivially holds).
We plot the results in Figure 2, showing that the quantity of interest decreases with and that is reasonable to expect Assumption 2 holding with C < 1. Observe that by simple call to L' L'Hopital's
rule, that lim 0.5A = TV=1l
Aa(A)
V(2)
Ag
06A W
0.004
Standard
0.0015
Stondlard
122
1,2
Randon
0.0010
Raudoca
0.003
Zero
0.0005
0.00000
0.1
0.1
0.2
11.5
0.4
0
10
60
1000
(a in two different scales. In the case of these models, Assumption
Figure 2: The plots of 0.5x
holds with C 0.005.
19

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We mention and discuss bounds and techniques that are introduced later in the paper. Limitations of the assumptions are also mentioned.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Both during related work discussion and the conclusions.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
20

---

Yes, complete proofs are included in Appendix A, and the assumptions are discussed and justified.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We include our code in the supplementary material, and the details of the implementations are discussed in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
21

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The same as above.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
Shbllic/guidee//deeSbbbmsss ionosoooorsiiioooicooooooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: /nipp. wwtp:c/cppwlcgggiicccoeeoo
/CodeSubmia ssionoliccy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
Yes, in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Not necessary.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
22

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https /tttps:/neeurti http///eerrrp.eeeeee/eee/ cttppp..ccpppllee hwtpp///llc....eccccceeeeeeeeeee
Answer: [Yes]
Justification:
No relevant issues in our work.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: This is theoretical work aiming towards better understanding generalization, no negative societal impact. Potential positive impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
23

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
25


Reviews:
[{"review_id": "C3Cb4XzYuP", "reviewer": "Reviewer_XnKo", "summary": "The paper presents a PAC-Bayes bound for the unbounded loss setting, improving on some of the main drawbacks of previous work on such bounds. The first such drawback discussed is the dependence of the tightness of the such bounds on a priori chosen free parameters, something which can usually only be partially circumvented by union bounding over a grid of free parameters. The second is the uniform control of the cumulant generating function of the loss across a model class. The paper show how the the introduced bound eliminates the need for approximate optimization over the free parameters (and the concomitant union bounding procedure), and how show the framework leading to the main theorem can be extended, exploiting model-specific bounding of the GCF.", "questions": "Is there any particular reason to use the phrasing \"$\\pi$ independent of $D$\" (e.g. line 34)? I know this means that $\\pi$ is chosen independent of the training sample (which allows for a Fubini theorem application), but find the phrase odd given that $P$ is usually chosen with reference to some features of the data distribution.", "limitations": "Yes", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper introduces a novel PAC-Bayes bound in the challenging setting of unbounded loss, and motives the contribution with clear discussion of the issues with previous PAC-Bayes bounds for unbounded loss functions. The numerical example of Figure 1 is a nice touch, showcasing how uniformly bounding the cumulative generating function of different models really can be a significant source of looseness in realistic settings. The paper is generally very well-written.", "weaknesses": "My main concern would be the extent to which this work will be interesting to this particular community. The technical contribution seems both solid and potentially useful, but it may be a better fit in a more specific venue. I am not well-versed enough in the line of work to which this paper belongs to give meaningful technical critiques.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review, we are happy to see that you appreciated the clarity of our writing and the motivation for our contribution. As for the weaknesses and questions, we address them individually below.\n\n\n> My main concern would be the extent to which this work will be interesting to this particular community. The technical contribution seems both solid and potentially useful, but it may be a better fit in a more specific venue. I am not well-versed enough in the line of work to which this paper belongs to give meaningful technical critiques.\n\n\nThere is a long history of theoretically inclined impactful contributions to the field of learning theory and PAC-Bayes in NeurIPS (see for example, [2,3,4]). In fact, the first appearances of PAC-Bayesian learning theory made their appearance in the NeurIPS conference with [2] in 2002; along with more modern studies such as [4] from 2022. Furthermore, a quick look at how many works in the NeurIPS website include the words \"PAC-Bayes\" in the title or abstract show more than 1500 results in Google (site:https://neurips.cc PAC-Bayes). Hence we believe the NeurIPS community is an appropriate audience for our contribution.\n\n\n> Is there any particular reason to use the phrasing \"$\\pi$ independent of $D$\" (e.g. line 34)? I know this means that is chosen independent of the training sample (which allows for a Fubini theorem application), but find the phrase odd given that $\\pi$ is usually chosen with reference to some features of the data distribution.\n\nIn this paper, we consider the standard approach in PAC-Bayesian bounds of using data-independent priors (see, for example, [1]). These priors can be selected using a priori features of the data distribution, such as the standard assumptions on the tails of the distribution (see the example at the discussion in Section 6 of [3]). But as the reviewer points, it is possible to use data-dependent priors, for instance, by splitting the available training data into two independent sets and using the first to construct the data-dependent prior (see Sections 4.3 and 9.3 in [5]).\n\n\n[1] Rodríguez-Gálvez, B., Thobaben, R., Skoglund, M. (2024). More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity. Journal of Machine Learning Research, 25(110), 1-43.\n\n[2] Langford, J., Shawe-Taylor, J. (2002). PAC-Bayes and margins. Advances in Neural Information Processing Systems, 15.\n\n[3] Germain, P., Bach, F., Lacoste, A., Lacoste-Julien, S. (2016). PAC-Bayesian theory meets Bayesian inference. Advances in Neural Information Processing Systems, 29.\n\n[4] Haddouche, M., Guedj, B. (2022). Online PAC-Bayes learning. Advances in Neural Information Processing Systems, 35, 25725-25738.\n\n[5] Sanae Lotfi, Pavel Izmailov, Gregory Benton, Micah Goldblum, and Andrew Gordon Wilson. Bayesian model selection, the marginal likelihood, and generalization. In International Conference on Machine Learning, pages 14223–14247. PMLR, 2022.", "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": "", "extra_scores": {}}, {"review_id": "wQyt7O6r5i", "reviewer": "Reviewer_MaqK", "summary": "The authors present a novel PAC-Bayes bound tailored for unbounded losses, akin to a PAC-Bayes version of the Cramér-Chernoff inequality. The provided bound allows exact optimization of the free parameter across various PAC-Bayes bounds, and leads to more informative and tighter bounds by incorporating \"model-dependent\" terms, such as gradient norms.", "questions": "See above", "limitations": "See above", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This is a strong paper, that addresses important points in PAC-Bayes. It is clear, well-written, theoretically sound and pleasant to read.", "weaknesses": "I really enjoyed the paper, and only have a few points:\n- The only fully empirical bound is Theorem 16. However, the Lipschitz constant L is unknown in practice and has to be estimated. Does that affect significantly the tightness of the bound, as well as its minimization? Same question for Constant C.\n- I'm a bit disappointed the minimization of this bound has not been addressed here. Is that due to a computational difficulty or simply left for future work?\n- Could the authors develop on the behavior of the optimal posteriors?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review, we are happy to see that you appreciated our contributions and had a pleasant reading. We address your doubts below:\n\n\n> The only fully empirical bound is Theorem 16. However, the Lipschitz constant L is unknown in practice and has to be estimated. Does that affect significantly the tightness of the bound, as well as its minimization? Same question for Constant C.\n\nVery good question. Yes, computing both the Lipchitz constant and the constant C will probably have an impact in the tightness of the bounds. For the former, specific approaches has been devised [1] and it is an active area of research. Computing the constant C would be challenging too.\n\n\n\n> I'm a bit disappointed the minimization of this bound has not been addressed here. Is that due to a computational difficulty or simply left for future work?\n\nWe agree that training models by PAC-Bayes bound minimization is the next natural step for our work, and this is definitely under our radar for future work. However, these practical procedures contain several technical challenges, which we cannot address in the limited space we have. These challenges include simultaneously optimizing $\\lambda$ and $\\rho$, which would require adapting the work of [2], and the adaptation of either *PAC-Bayes with backprop* [3] or variational inference methods to our bounds. \nAs we said, this is promising but highly non-trivial work we are planning to carry out in future works.\n\n\n> Could the authors develop on the behavior of the optimal posteriors?\n\nIf we look at the optimal posterior in Proposition 12, we can see that in cases where the model-dependent bounding term $\\psi(\\theta,\\lambda)$ is independent from the data, the posterior can be interpreted as a standard Gibbs posterior where the $\\exp(-(n-1)\\psi(\\theta,\\lambda))$ term is absorbed by the prior. In the other case there is not much we can say at the moment, that is why we talk about MAP estimates in the paper: because the regularizing effect of $\\psi(\\theta,\\lambda)$ is easier to interpret there. In any case, further study of these posteriors is an exciting line of future work.\n\n\n[1] Fazlyab, M., Robey, A., Hassani, H., Morari, M., Pappas, G. (2019). Efficient and accurate estimation of Lipschitz constants for deep neural networks. Advances in Neural Information Processing Systems, 32.\n\n[2] Thiemann, N., Igel, C., Wintenberger, O., Seldin, Y. (2017, October). A strongly quasiconvex PAC-Bayesian bound. In International Conference on Algorithmic Learning Theory (pp. 466-492). PMLR.\n\n[3] Rivasplata, O., Tankasali, V. M., Szepesvari, C. (2019). PAC-Bayes with backprop. arXiv preprint arXiv:1908.07380.", "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": "", "extra_scores": {}}, {"review_id": "BvrLmSXg1R", "reviewer": "Reviewer_JzAv", "summary": "This paper gives novel PAC-Bayes oracle bounds using the Cramer transform's basic properties under a bounded exponential moment condition. \n\nThe benefit of using the Cramer transform is that the bound allows exact optimization of the free parameter $\\lambda$ incurring in a $\\log n$ penalty without resorting to union-bound approaches, typically used in the related literature. \n\nThen, by considering a model-dependent bounded exponential moment condition, the bound would be tightened. In this case, the posterior distribution can be optimized, which results in optimal distributions beyond Gibbs’ posterior. \n\nBy applications to generalized sub-Gaussian losses, norm-based regularization, and log-Sobolev inequalities, tighter and novel bounds are provided.", "questions": "Can Lemma 6 be bounded by a subgaussian random variable for subgaussian loss. Will there be better generalization results in this situation?", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The introduction is written very clearly.\n\nMany insights concerning the PAC-Bayes are given: exact optimization of the free parameter λ, designing of better posteriors, and tighter bounds, etc.", "weaknesses": "I don't understand the author's claim in the first paragraph of the Section Limitations and future work: An apparent limitation of our approach is that the we are implicitly assuming that ℓ(θ, X) is light tailed (equivalently, sub-exponential), as in every Cramér-Chernoff bound. This is only partially true.\n\nLemma 6 gives an upper bound of sub-exponential random variables. In my opinion, the results of this paper seem to only apply to sub exponential losses. Can the author provide more explanations？", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your review, we are happy that you appreciated the clarity and the insights of our work. We address your questions below.\n\n\n> I don't understand the author's claim in the first paragraph of the Section Limitations and future work: An apparent limitation of our approach is that the we are implicitly assuming that $\\ell(\\theta, X)$ is light tailed (equivalently, sub-exponential), as in every Cramér-Chernoff bound. This is only partially true.\nLemma 6 gives an upper bound of sub-exponential random variables. In my opinion, the results of this paper seem to only apply to sub exponential losses. Can the author provide more explanations?\n\n\nThis is a fair question that will be clarified in more detail using the extra page available for the camera-ready version.\n\n\nSince we assume the loss function $\\ell$ is positive, the random variable $L(\\theta) - \\ell(\\theta, X)$ is upper-bounded by $L(\\theta)$. Therefore, we don't need to make assumptions about the right tail of $L(\\theta) - \\ell(\\theta, X)$, other than ensuring that the expected value $L(\\theta)$ is finite. However, if we were interested in bounding $|L(\\theta) - \\ell(\\theta, X)|$, we would also need to control the left tail of $L(\\theta) - \\ell(\\theta, X)$. The left tail can be heavy-tailed, which would require the sub-exponential assumption to manage effectively.\n\nSince we assume the loss function $\\ell$ is positive, the random variables we are interested in upper-bounding, $L(\\theta) - \\ell(\\theta, X)$, are all bounded by $L(\\theta)$, hence we don't need to assume anything about the right tail of $L(\\theta) - \\ell(\\theta, X)$ (except for the expected value $L(\\theta)$ being finite, of course). However, if we were interested in bounding $|L(\\theta) - \\ell(\\theta, X)|$, we would need to control the left tail of $L(\\theta) - \\ell(\\theta, X)$ too, which can be heavy-tailed and would need the sub-exponential assumption to work.\n\nThe fact that we only care on the right tail of $L(\\theta) - \\ell(\\theta, X)$ is also implicit on the fact that the CGF (or the CGF bounding function) is only defined for $\\lambda>0$. This fact is explicited, for example, in Definition 10 of [1] and the discussion below. The discussion on Section 2.2 of Chapter 2 in [2] is also clarifying.\n\nMost PAC-Bayes bounds only care about upper bounds on $L(\\theta) - \\ell(\\theta, X)$ because in practice the empirical risk is usually much smaller than the actual one and because PAC-Bayesian learning works by minimizing upper bounds on $L(\\theta) - \\ell(\\theta, X)$. If the loss function was not bounded from below or we cared about bounds on $|L(\\theta) - \\ell(\\theta, X)|$, we would need sub-exponentiality. This is what we tried to express in Limitations and future work (Section 6), but maybe our explanations were too rushed. As mentioned before, we will provide a more detailed clarification in the camera-ready version to ensure better understanding.\n\n\n> Can Lemma 6 be bounded by a subgaussian random variable for subgaussian loss. Will there be better generalization results in this situation?\n\nIf it can be done it is not straightforward, because Lemma 6 relies in $\\Lambda^*$ cancelling out with $(\\Lambda^*)^{-1}$, hence resulting in the same $\\mathbf{P}_{exp(1)}(X\\geq c)$ bound. However, tightening this result is an important line of research for future work because the penalty term in our bounds depends on Lemma 6.\n\n\n[1] Rodríguez-Gálvez, B., Thobaben, R., Skoglund, M. (2024). More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity. Journal of Machine Learning Research, 25(110), 1-43.\n\n[2] Boucheron, S., Lugosi, G., Massart, P. (2013). Concentration inequalities: a non asymptotic theory of independence.", "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": "", "extra_scores": {}}, {"review_id": "n9ppVG71TH", "reviewer": "Reviewer_Kbx9", "summary": "The authors propose a new oracle PAC-Bayesian bound that has two main features: it is valid for unbounded losses (or at least under assumptions weaker than bounded loss) and it allows for an exact optimization of the free parameter $\\lambda$ appearing in most PAC-Bayesian bound, with only the cost of a penalty that is logarithmic in the number of data points. Based on this new bound, the authors first recover existing bounds and improve over the prior art by introducing model-dependent assumptions in the generalization bounds. They also make the link with regularization techniques. In particular, they obtain new bounds based on input-gradients by combining their theory with log-Sobolev-type inequalities.", "questions": "- Do you know any explicit example where your oracle bound yields a better optimization of $\\lambda$ than the best existing results under the same assumptions (obtained either by union bound arguments or other techniques)?\n\n - In Lemma 18, you prove that $\\Lambda_\\theta^* (a) < \\infty$ on $[0,L(\\theta))$, but then in the proofs of Lemma 6 and theorem 7, you apply $\\Lambda_\\theta^*$ on $gen(\\theta, D)$, which may take negative values. Why is that justified?\n\n - Corollary 13: the result would be even stronger if the expectation over the posterior was outside of the square root. Do you think it is possible to obtain such a result?\n\n - After Assumption 2, line 279, you claim that the log-Sobolev inequality state in Assumption 2 holds for several well-known distributions, such as the Gaussian distribution. However, in the reference [50] you give for this result, a much weaker inequality appears. Indeed, the log-Sobolev inequality would be $\\Lambda_\\theta (\\lambda) \\leq \\frac{C}{2} \\lambda^2 L(\\theta)^2$, where $L(\\theta)$ is the Lipschitz constant of $x \\longmapsto \\nabla_x \\ell(x, \\theta)$. Can you prove that Assumption 2 indeed holds for the Gaussian distribution, or give a reference?\n\n - Line 250: where exactly is this result proven in the cited paper? Can you be more precise about how this result is obtained?\n\n**Minor remarks / questions:**\n\n - Line 26: a $\\to$ an.\n\n - Line 17: The notation $\\mathcal{M}_1(\\Theta)$ should be introduced.\n\n - Line 131: space permits to use the long notations in most cases, but it is not done, while it would improve the readability of the paper. \n\n - Line 243: regularizaton $\\to$ regularization\n\n - Line 244: based in $\\to$ based on.\n\n - Assumption 1: if $\\ell$ is $M$-Lipschitz in $\\theta$, then $\\Vert \\nabla_\\theta \\ell (x,\\theta)\\Vert_2^2$ is bounded by $M^2$, not $M$.\n\n - We see in Appendix A that the fact that $\\ell\\geq 0$ plays an important role in the proofs. Does your theory hold if $\\ell$ is not lower bounded?\n\n - In the definition of $\\Lambda_\\theta^*$, could the parameter $b$ depend on $\\theta$? Could that cause any issue in your proofs?", "limitations": "Most of the limitations were discussed in the paper.\n\nThe paper has no societal or ethical impact.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The ability of exactly optimizing the free parameter $\\lambda$ in an oracle PAC-Bayesian bound is a nice contribution. It may be useful in several settings. \n\n - The proofs of the main results rely on quite general bounded CGF assumptions, which are weaker than the usual bounded loss assumption and allow for model-dependent assumptions.\n\n - Instead of usual exponential terms that are averaged over the prior distribution, the authors provide PAC-Bayesian bounds with a stronger dependence on the posterior distribution, hence leveraging the concentration properties of each individual model. Beyond tightening the generalization bounds, this could strengthen the practical relevance of PAC-Bayesian theory.", "weaknesses": "- It should be made more clear how the main results compare to existing results, especially the ones relying on grids and union bounds, as well as other PAC-Bayesian bounds that do not have neither a $\\log(n)$ penalty nor free parameters for subgaussian (hence unbounded) losses. These existing results should be written explicitly and compared with the new bounds. \n\n - Adding a few examples of situations where the new bounds clearly outperform the existing ones would enhance the paper.\n\n - Additional technical background on the generalized inverse and its main properties would help a lot the readability of the paper, as it is the main technical ingredient.\n\n - The log-Sobolev inequalities mentioned in the last section seem to be stronger than the usual log-Sobolev inequality. Some clarification should be added (see the questions). \n\n - There might be a mistake in the statement of Theorem 1. Shouldn't it be $1/\\lambda$ instead of $1/(\\lambda n)$? In Theorem 3 of [Germain et al., 2016], the result is stated with $1/\\lambda$ instead of $1/(\\lambda n)$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for your detailed feedback, it will definitely improve the quality of our paper. \n\n> It should be made more clear how the main results compare to existing results [...]\n\nThank you for the suggestion. You are correct that our discussion is somewhat incomplete and scattered throughout the paper. We will add a new subsection in the revised version to compare our results with existing findings. Please note that we compare our bound with Theorem 14 of [1] in lines 189-194, demonstrating that our bound is tighter for large KL divergences. Additionally, [1] offers state-of-the-art bounds for unbounded losses and enhances the grid+union bound method.  \n\nIn relation to your comment about  *PAC-Bayesian bounds that do not have neither a $\\log(n)$ penalty nor free parameters for sub-Gaussian (hence unbounded) losses*, we understand you refer to sub-Gaussian bounds with $\\log(1/\\delta)$ dependency and no free parameters. As far as we know, most of those bounds, such as Corollary 4 in [2], simply hold for a fixed certain $\\lambda$, which usually result in looser bounds than those with a $\\log(n)$ penalty and optimized $\\lambda$. \n\n\n\n> Adding a few examples of situations where the new bounds clearly outperform the existing ones would enhance the paper.\n\nGood suggestion. Probably, the most clear example is the one given in our discussion of Corollary 13 we observe how this bound outperforms standard sub-Gaussian bounds because of the model-dependent proxy variance improves upon the worst-case proxy variance. This case can be extended for sub-gamma random variables and the like. We will better highlight these cases in the new version of the paper. Furthermore, we will also highlight more how Theorems 15 and 16 improve those in [3] for qualitative reasons (actually relating posterior performance with gradient norms and optimization of $\\lambda$).\n\n\n> Additional technical background on the generalized inverse and its main properties would help a lot the readability of the paper, as it is the main technical ingredient.\n\nThis is also a reasonable suggestion, we'll add the definitions and lemmas used in the proofs in a separate Appendix Section. \n\n\n> There might be a mistake in the statement of Theorem 1. Shouldn't it be $1/\\lambda$ instead of $1/(\\lambda n$)? [...] \n\nThis is just a matter of the parametrization you choose, see for example Theorem 1 in [4] and the discussion in Footnote 3. We used $\\lambda n$ to emphasize the dependence on the dataset size $n$.\n\n> Do you know any explicit example where your oracle bound yields a better optimization of $\\lambda$ [...] ? \n\nAs discussed above, our Corollary 9 provides better optimization than the method of Theorem 14 in [1] when the KL term is large. But, again, when making these comparisons we are forced to discard one of the main contributions of our bounds, that is, the model-dependent bounding term.\n\n\n> In Lemma 18 [...], which may take negative values. Why is that justified?\n\nObserve that $\\Lambda^*_\\theta(a):=\\sup_{\\lambda>0} \\{\\lambda a - \\Lambda_\\theta(\\lambda)\\}$, hence $\\Lambda^*_\\theta(a)=0$ for negative values of $a$ because $\\Lambda_\\theta(\\lambda)$ is always positive. See our discussion with Reviewer MaqK for more context.\n\n> Corollary 13: the result would be even stronger if the expectation over the posterior was outside of the square root. Do you think it is possible to obtain such a result?\n\nNot with our approach because the square root is a consequence of optimizing $\\lambda$ and the optimization depends on $\\rho$ and $\\sigma(\\theta)^2$. \n\n\n> After Assumption 2, line 279, you claim that the log-Sobolev inequality state in Assumption 2 [...]\n\nOur Assumption 2 follows from Corollary 9 in [50] using $\\phi=-\\log f$ and $f=\\exp(-\\lambda \\ell)$. Note that Corollary 9 in [50] directly involves the expected norm of the gradients. We will include a formal result in the appendix for completeness. The Gaussian case is a particular case of Corollary 9.\n\n> Line 250: where exactly is this result proven in the cited paper? Can you be more precise about how this result is obtained?\n\nThis is shown in the proof of the Proposition 5.2 of [37], where we only use that the model $\\theta_0$ with all parameters set to zero has zero variance. For completeness, we will include the complete proof in the camera-ready version.\n\n> We see in Appendix A that the fact that $\\ell\\geq 0$\nplays an important role in the proofs. Does your theory hold if $\\ell$ is not lower bounded?\n\nSee the answer to Reviewer MaqK related to the sub-exponential assumption. In sort, if $\\ell$ is not lower bounded we would need to make a sub-exponential assumption. But, in ML, having not lower-bounded lossess hardly make sense. \n\n\n> In the definition of $\\Lambda^*_\\theta$, could the parameter $b$ depend on $\\theta$? Could that cause any issue in your proofs?\n\nObserve that in the Appendix A (Line 515) we show that $b=\\infty$ for all $\\theta$ when $L(\\theta)$ is finite, which is the standard case. In more general cases, yes, it can happen and this would affect the definition of $\\Lambda^*_\\rho$ in Line 150. The interesting thing is that, even when $\\Lambda_\\theta$ are finite in $[0,b_\\theta)$ for different $b_\\theta$'s, $E_\\rho[\\Lambda_\\theta(\\lambda)]$ is also finite in some interval $[0,c)$, where $c$ depends on the $b_\\theta$, and everything works normally. \n\n[1] Rodríguez-Gálvez, B. et al. (2024). More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity. Journal of Machine Learning Research.\n\n[2] Germain, P. et al. (2016). PAC-Bayesian theory meets Bayesian inference. Advances in Neural Information Processing Systems, 29.\n\n[3] Gat, I. et al. (2022). On the importance of gradient norm in PAC-Bayesian bounds. Advances in Neural Information Processing Systems, 35.\n\n[4] Masegosa, A. (2020). Learning under model misspecification: Applications to variational and ensemble methods. Advances in Neural Information Processing Systems, 33.", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank all four reviewers for their helpful questions and suggestions. We are happy to see that there is certain consensus on the clarity, the soundness and the contributions of our work. We hope we clarified your doubts, and we are willing to implement the suggested changes on the camera-ready version.

Meta-review: Classical PAC Bayes theorem holds for bounded losses and mainly rely on concentration inequality techniques for bounded random variables. In this paper PAC bayes theorem is extended to unbounded losses by considering the tail behavior of the losses. Specifically, the authors seem to combine PAC Bayesian approach with the log-sobolev style tools for proving concentration inequalities. This yielded to the authors a neat PAC Bayesian extension that could apply to unbounded losses as long as the Cramer transform of the losses are well behaved. This is a neat result worth publishing.
Decision: Accept (poster)