Integral Probability Metrics PAC-Bayes Bounds
Authors: Ron Amit
Baruch Epstein
Shay Moran
Ron Meir
Venue: NeurIPS 2022 Accept (2022)
Keywords: PAC-Bayes
Learning Theory
Generalization bound

Abstract: We present a PAC-Bayes-style generalization bound which enables the replacement of the KL-divergence with a variety of Integral Probability Metrics (IPM). We provide instances of this bound with the IPM being the total variation metric and the Wasserstein distance. A notable feature of the obtained bounds is that they naturally interpolate between classical uniform convergence bounds in the worst case (when the prior and posterior are far away from each other), and improved bounds in favorable cases (when the posterior and prior are close). This illustrates the possibility of reinforcing classical generalization bounds with algorithm- and data-dependent components, thus making them more suitable to analyze algorithms that use a large hypothesis space.

Integral Probability Metrics PAC-Bayes Bounds
Ron Amit
Baruch Epstein
Technion Israel Institute of Technology The Viterbi Faculty of Electrical Engincering ronamit t campus www.ampsssecccioooo..o. twchniin..nn.ooo ac.il
Technion Israel Institute of Technology The Viterbi Faculty of Electrical Engincering baruch. epst i menigmmmmlll. com
Shay Moran
Ron Meir
Technion Israel Institute of Technology
Technion Israel Institute of Technology The Viterbi Faculty of Electrical Engineering rmeirgee tecchii.eecciooo ic
Faculty of Mathematics
The Taub Faculty of Computer Science Google Rescarch, Isracl
smoran@technion.cm ac.il
Abstract
We present PAC-Bayes-style generalization bound which enables the replacement of the KL-divergence with a variety of Integral Probability Metrics (IPM). We provide instances of this bound with the IPM being the total variation metric and the Wasserstein distance. A notable feature of the obtained bounds is that they naturally interpolate between classical uniform convergence bounds in the worst case (when the prior and posterior are far away from cach other). and improved bounds in favorable cases (when the posterior and prior are close). This illustrates the possibility reinforcing classical generalization bounds with algorithm- and data data-dependent components, thus making them more suitable to analyze algorithms that use large hypothesis space.
Introduction and Related Work
Classical statistical learning theory is based on a worst-case perspective which can be too pessimistic model practical machine learning. reality, data is rarely worst-case, and experiments demonstrate lcarning tasks that are solved with much less data than predicted by traditional thcory. A primary manifestation of the traditional worst-case perspective demonstrated by uniform convergence (UC); a genre of generalization bounds which form the backbone of the classical theory (Vapnik, 1999). These bounds guarantee that the generalization gap of all hypotheses in the output-space of the algorithm simultaneously vanish as the training-set size grows. The key algorithmic insight these bounds provide summarized by the Empirical Risk Minimization principle (ERM), which asserts that it suffices output any hypothesis in the class which minimizes the empirical risk.
Consequently, UC arguments provide non-trivial guarantees only if the hypothesis class used by the algorithm is restricted (c.g. has low Rademacher complexity or bounded VC dimension). In contrast, practical learning approaches such as deep learning algorithms use huge hypothesis classes whose VC dimensions rapidly increase with the size and depth of the underlying network. Hence, the rate guaranteed by UC arguments is often much slower than the rate observed in practice (Bach- mann, Moosavi-De Dezfooli, & Hofmann, 2021; Nagarajan & Kolter, 2019b; Neyshabur, Bhojanapalli, McAllester, Srebro, 2017: Zhang, Bengio, Hardt, Recht, & Vinyals, 2017).
A further shortcoming of UC bounds, and the associated ERM principle, is that they are algorithm- and data-indeppendent: that is, they do not utilize beneficial properties of the data and/or the algorithm. For
Mooe precisely, UC bounds only depend on the hypothesis space.
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

example, in practice, regularized algorithms often perform better than Empirical Risk Minimization, but this cannot be expressed by UC bounds and the ERM principle.
The PAC-Bayes (PB) framework is a prominent example of a theoretical framework that does not require the UC property, This framework was pioneered by -hyler and Williamson (1997) and McAAllsterr (1998) and developed in later papers, e.g. (Catoni, 2007; Lever, Laviolette, & Shawe- Taylor, 2013; Maurer, 2004; McAllester, 2003; Sceger, 2002); see Guedj (2019) and Alquier (2021) for extensive surveys. Begin, Germain, Laviolette, and Roy (2016) introduced a general strategy that produces PB bounds from change- of-measure inequalities leading to bounds based on the Rényi's a-divergence, and Alquier and Guedj (2018); Ohnishi and Honorio (2021); Picard-Weibel and Guedj (2022) further extended PB bounds to other Csiszár's f -diiergenness.
PB theorems consider the generalization performance of stochastic predictors. These bounds are non- uniform² by nature, and are algorithm and data-dependent. They are usually based complexity term that depends on the Kullback-LeiDe Leibler (KL) divergence between a data-dependent posterior distribution and data-indeppndent prior distribution."
There are additional notable works on data and
-ereebdddededeeet guarantees. The classical work of Bousquet and Elisseeff (2002) and Xu and Mannor (2012) studied generalization guarantees that depend on data and algorithn--depender stability measures. A further line of recent papers tries to incorporate noise robustness/resilienee. In Miyaguchi (2019), PAC-Bayes transportation bound is used to measure the contribution of randomization to PB. This is done via optimal transport and Lipschitzness, based on the usual KL-PB bound. The work of Wei and Ma (2019) uses data-dependent Lipschitz smoothness to improve margin bounds, and Nagarajan and Kolter (2019a) passes from standard PB to deterministic bound by assuming noise-resilience on the training data. This property translates to the test data, implying that good training smoothness leads to good test smoothness. Finally, Yang. Sun, and Roy (2019) measure data-dependent smoothness around each hypothesis (for each sample) and merge Catoni's 's bound (Catoni, 2007) with Rademacher thcory, to obtain fast rates.
Recent work by Aminian, Bu, Wornell, and Rodrigues (2022); Lopez and Jog (2018); Ro- dríguez Gálvez, Bassi, Thobaben, and Skoglund (2021); Wang. Diaz, Santos Filho, and Calmon (2019); J. Zhang, Liu, and Tao (2021) and Neu and Lugosi (2022) proved information-the -tteorettccc bounds on the expected generalization gap using the Wasserstein and the total-variation (TV) dis- tances. Our work is within the PB framework, and therefore enjoys the following advantages: (i) The bounds are "in high probability" over the sample rather than in expectation. (ii) PB bounds are sample dependent, i.c., bound the generalization gap for a specific sample-dependent posterior, while information- -theorcticc bounds are formulated as expectation over all sample sets, thereby pro- viding basis for empirical algorithms, c.g., Alquier (2021); Dziugaite and Roy (2017). (ii)) The reference measure in PB can be any cample-independent distribution, while information coomation--theortiic bounds consider a specific reference. Our work introduces uniform convergence assumptions, while the above- mentioned papers each used different assumptions. Recently, Chee and Loustau (2021) I) proposed PB bounds with the entropy regularized optimal transport distance for an online-learning setting with a finite class.
The optimal transport interpretation of the Wasserstein distance has been used recently in other contexts to derive generalization bounds. Chuang, Mrouch, Greenewald, Torralba, and Jegelka 12021) proposed a bound that uses data-dependent complexity measure, evaluated via the Wasserstein distance of independently sampled subsets of the training data in the feature space. Hou, Kassraie, Kratsios, Rothfuss, and Krause (2022) used the principles of optimal transport to derive an instance- based bound based on the local Lipschitz regularity of the learned prediction function in the data space.
In the modern deep learning regime, measures of the hypothesis class complexity used in UC bounds, such the VC dimension Rademacher complexity, are enormous, making the bounds extremely loose for any reasonable number of samples, as opposed to PB bounds (Dziugaite & Roy, 2017; Jiang, Neyshabur, Mobahi, Krishnan, & Bengio, 2019). However, these complexity measures often have closed-form formulas for models such as neural networks, which show explicitly the effect of the model architecture (number of layer, activation functions etc.). This in contrast PB bounds, in which the dependence on the hypothesis class is less explicit (but see Anthony and Bartlett
2 Te.., PB bounds apply even in learning problems without uniform convergence (Definition 1). But see Rivasplata, Kuzborskij, Szepesvári, and Shawe-Tayle (2020) for data-dependent priors.

---

(1999); Neyshabur, Tomioka, and Srebro (2015) for exceptions for neural networks). Therefore, we believe that extension of UC bounds to incorporate data- and algorith-deppendnne can facilitate the design of better performing architectures. A further advantage of PB bounds is their non-uniformity (the generalization gap bound depends on the learning output), hence we can use the bound as a minimization objective for structural minimization algorithm, where the complexity term acts as a regularizer. In cases where the hypothesis class is very large, but we have some prior knowledge on which hypotheses suggested by Occam's 's Razor), then in PB one can inject this knowledge as the prior distribution, effectively lowering the generalization bound.
more likely to have low population loss (c.g. prefer simpler hypothesis as
Can the rich theory of UC bounds be extended to help explain generalization with modern large scale models? Can this theory be used to prove data and algorithm dependent guarantees? In this paper, we take a step in the direction of answering these questions positively. To achieve this goal, we show new technique to incorporate UC bounds within the PAC-Bayes framework. We prove new PB bounds with Integral Probability Metric (IPM) (Müller, 1997) to measure distances between distributions, rather than the standard KL or f-divergences used so far. Specifically, we focus on utilizing two specific IPMs: the total variation and Wasscrstein metrics This IPM framework allows greater flexibility, it does not require the support of the posterior to be subset of the prior's ' support (absolute continuity) as in standard KL-PB bounds, and it applies to deterministic as well as stochastic prior and posterior distributions. In fact, the IPM-based PB bounds worst, the rate of the UC bound used. Recently, Livni and Moran (2020) showed that the classical KL-PB theorem cannot imply meaningful distribution-free generalization bounds for 1-dimensional linear classification. In contrast, our derived IPM-PB bounds do imply such bounds, because linear classifiers satisfy uniform convergence.
introduce match, at
We note that the work of Audibert and Bousquet (2003, 2007) showed a different approach to utilizing the UC assumption to derive PAC-Bayes bounds. Their work assumed UC property to utilize the generic chaining tochnique, resulting in more refined, variance-sensitive, bounds. In contrast to our work, their bound is not fully empirical, and the assumed UC bound is not used by the resulting bound.
The Total Variation PAC-Bayes (TVPB) bound (Thm. 6) applies in any setting where uniform convergence (UC) (Def. 1) holds, an assumption that is satisfied by many natural learning problems. For example, in binary problems, UC holds with a rate of O( /vC(Hl/m), where VC(H) is the VC dimension (Vapnik, 1999). As observed in practice, for large models of deep neural networks with very large VC dimensions the learning rate on natural datasets is often much faster than predicted UC bounds. To explain this gap, we must turn to data and algorithm-dependee bounds. The TVPB
improves the gap bound to be O (OCH))Div(Q.P)mm effectively multiplying the VC dimension by the total variation distance of the posterior from the prior. Intuitively, simpler posteriors (closer to the prior assumed before observing the data) lead to better generalization gap. Compared to the vanilla KL-PB, the TV distance can be small even in cases where the KL distance can be very large, and in any case, the bound only improves over the original UC bound. In addition, the TV-PB bounds incorporate properties of H via the VC dim. We also explore settings where the generalization gap function exhibits a certain smoothness property, and show PB bound with the Wasserstein metric maaserstein-based bound in the finite hypothesis class setting and in linear regression setting. In the latter setting, show that standard UC bound can be improved by factor of O (Q, P)), where W1(Q, P) is the s order Wasserstein distance between postcrior and prior over the unit-sphere. We conduct a numerical simulation to demonstrate the improvement of the Wasserstein PB bound over the UC bound, and, in cases of narrow prior distributions, over the KL-PB bound. The experiment also investigates the case of non-randomized predictors by setting the prior and posterior as Dirac delta measures, which f-divergence based PB bounds are unable to use.
(Thm. 11). We analyze this smoothness property and show an explicit
Figure iillustrates graphically the organization of the claims in the paper.
3

---

Template (Prop. 4)
Lipschitz
Template Wasserstein-PB Bound (Thm. 11)
Template for Total-Variation PB Bound (Thm. 6)
Loss-Gradient
UC
VC
Wasserstein- Bound for Finite Classes (Thm. 12)
Wasserstein-PP Bound for Loss-Gradien UC Classes (Thm. 14)
Total-Variation PB Bound Classes (Cor. 8)
Linear
Regression
Wasserstein- Bound for Linear Regression (Cor. 15)
Figure Claims tree diagram. B means that claim B is special case of claim A, under additional assumptions on the learning problem. For full description of the assumptions, see the corresponding claims.
2
Preliminaries
2.1 The Learning Problem
We begin with short description standard supervised learning task. Consider domain 2, distribution D over 2, a hypothesis set H. and finally, a loss function f H x 2 - [0, 1]. The tuple (D, H. defines learning problem: The learning algorithm receives input training S= { E n sampled i..d from D and selects an hypothesis / E H. The performance of measured by the expected risk, (h)h) def Ez-DE (h, 2). While the expected risk is unavailable to algorithm, the empirical risk, (s(h) def EiE (h, zi), can be evaluated using the training data. m
The gencralization gap is defined by (h) def LD(h) Ls(
Several of our results will assume that the learning problem (D, H. E) satisfies the uniform conver- gence property; i.e. the existence of uniform upper bound on the generalization gap which applies simultaneously to all hypotheses in H.
Definition (Uniform convergence, (Vapnik & Chervonenkis, 2015)). The learning problem (D, H. E) satisfies the uniform convergence property, if there exists a bound function u(m, 8') > 0 s.t. for any m E N+ 5 E (0, 1) we have
(H)ss(h)] S u(m, 8), vh e H3 2 - and u(m, 6) m0+00
0.
(1)
UC type bounds are major part of the foundations of theoretical machine learning. Unfortunately, they suffers from few drawbacks. First, currently known bounds tend to be extremely loose in many cases, most notably for deep networks. Sccond, the setup does not provide natural way to encode prior knowledge into the bounds, particularly when dealing with deep networks the hypothesis set is usually rich enough to express relevant functions, and the training algorithms that might utilize some prior knowledge are not themselves part of UC based bounds. Finally, UC bounds are usually data-dependent, a property which is critical to explain the generalization of DNNs on real- world data (Nagarajan & Kolter, 2019b; C. Zhang et al., 2017).
2.2 PAC-Bayes Bounds
Let M(H) denote the set of all probability measures over H. For any probability measure Q (H), we define the expected loss, empirical loss and generalization gap by
(D(
E R~Q
LD)h)
Ls(
E h-Q
Ls(h)
As(Q) Lo - is(
(2)
"This formulation allows for greater generality than the standard Z = X y and mis classification loss setting. In particular, it can describe number of unsupervised learning problems (Seldin and Tishby (2010)).

---

PAC-Baaee theory bounds the expected loss, simultaneously for all "posterior" (sample-dependen) probability measures Q M(H), with high probability over the samples S ~ DDm, given any "prior" (sample-independenl probability measure P E M(H). A key feature of most PAC-Bayes
bounds is their dependence on the KL divergence between the two distributions P, Q, KL(Q) |I P) def dQ )dQ, where dQ JP is the Radon-Noe -Nkkodmm derivative of Q w.r.t. P. While KL is natural measure of divergence between probability distributions, it restricts the applicability the resulting bounds to cases where the support of Q is contained in the support of P.. The following bound was introduced by McAllester (1998).
Jx In( aP
Proposition (Classical KL-PB Bound), For any prior P (MH) and 6 (0, 1). with probability at least 5 over the samples S ~ D for all Q E M(H), we have
KL(Q P) + In(m/)
As(Q) S
(3)
2(m - 1)
3 A Template for IPM PAC-Bayes Bounds
3.1 General IPM-PB Bound
Definition 3 (Integral Probability Metric). (Müller, 1997; Sriperumbudur; Fukumizu, Gretton,
Schölkopf. & Lanckriet, 2009, 2012) The Integral Probability Metric (IPM) between two proba- bility measures P and Q over H is defined
P),
del
sup [ fap FEF
( faq
sup E FEF h>P A~D
[f(h]]
E [r())]
(4)
HH
where F is a set of real-valued bounded functions
functionunctionss Ht R.
By definition, IPM distance measures are symmetric and non- non- negative. Note that the KL-divergence is not a special case of IPM, rather it belongs to the family of f-divergences, that intersect with IPM only at the Total- Variataai (Sriperumbudur al., 2009, 2012).
The following proposition assumes that for any fixed sample S' E - the function fs (h) def 2(m 1) (h) is a member of a family of functions that depend on the sample, denoted Fs Thus, the IPM-PB bound allows us to 'convert' some knowledge we have about the properties of the generalization gap function (s( a generalization bound.
Since we do not specify yet the collection of function families (Fs) (Fsh.sggm the bound does not convey explicit rate, and should rather be seen as template. In the next sections, will derive explicit bounds with specific IPMs divergences. Namely, we will derive a total-variation distance based bound by selecting collection of bounded function sets, and Wasserstein distance based bound. by selecting a collection of Lipschitz function sets.
Proposition (Template for IPM PB Bound). For any fixed dataset S E 2 .m E N+ let Fsr be family of bounded and measurable functions H - R. Assume that for any number of sumples, m, and sample S" E n the function 2m - 2 (-) is in Fs:. Then for any prior P E MMH) and ò E (0, 1), with probability least 1 over the samples S Dm for all Q E M(H), we have
(Q, P) In(m/s)
As( S
(5)
2(m 1)
The proof is in Appendix A. The main idea is to use the IPM definition and the assumption as Shange-of-measure inequality, instead of the variational formula by Donsker and Varadhan (1975), which is used in the classical KL-PB bound proof. The rest of the proof is similar to the classical derivation (McAllester, 2003; Shalev-Shwartz & Ben-David, 2014).
Note that, similarly to the classical KL-PB bound, Proposition 4 does not require the UC property to hold. However, in the next sections we will see that assuming an existence of a UC bound u(m, 8), and selecting particular collection of function families {Fs)sez" will result in explicit bounds that can improve upon the worst-case nature of the original u(m, 6) bound.
5

---

3.2 Template for Seeger Type IPM PAC-Bayes Bound
The work of Seeger (2002) and Maurer (2004) presented different form of the PAC-Bayes theorem with fast (l)m) rate as the dominant term, if the empirical risk is low.
We denote by kp Il q) the KL divergence between two Bernoulli distributions B(p) and B(q). q E 11. that is,
( pln + p) In 1-
if $ {0, else if = elsc.
k1 pp g)
O, undefined,
(6)
For any h E H. define the relative entropy of the empirical risk with respect to the expected onc as (h) def (h) || (D())). Similarly, and overloading notations, we define for any distribution Q E M(H), A (Q) def (Q)(((Q) || (Q))).
By replacing the KL-based change-of-measun inequality step in the proof (Maurer, 2004, Thm. 5) with the IPM property (Def. get similar bound for IPM measures (see detailed proof in Appendix A.2).
def m A (h) Fs- Then for any prior (MH) and 8 (0, 1), with probability at least over the samples
Proposition 5 (Template for Seeger Type IPM PAC-BBaee Bound), Assume fs(h)
S ~ Dm, for all Q C MMH)), we have
(Q) 7Fs (Q, + P)nn(2v) (n(2m//))
By applying the Refined Pinsker's 's relaxation (McAllester (2003), Eq. 6) we can immediately derive the following, looser, but easier to interpret bound
As(Q) < (L 15s (Q, P) + (n(vmm/) + 25% (Q, P) In(2v7/6))
m7
When [Q( is small (as is typical with modern deep networks), the final term determines the convergence rate. We defer the investigation of PB bounds derived from Prop. Appendix B. In the following sections we focus on investigating the implication of the Template IPM PB Bound of Prop. 4.
4 Total- Variation PAC-Bayes Bounds
In this section, investigate PB bound with the total-variation (TV) distance, Drv (Q, P) def supAgEx ((A) Q(4),, where Σn is the standard Borel sigma-algebra associated with H. The TV distance can be described an IPM with the family of functions
F {f H. - oo), ll s M),
(9)
for any M 2 0. To see this, note that
7F P) = sup fEF%
sap - [ fdQ
1
M sup PP(A) - Q(A) = MDrv(Q, (Q, AEEN
P), (10)
where equality (i) holds since in the supremum it suffices to take the class of indicator functions {M 1h),), E Σx}, since the functions in Fxx are bounded in [0, M).
Theorem (Template for Total- Variation PB Bound). Assume that there exists some uniform convergence bound u(m, 8') (Definition 1), then, for any prior P. E -M(H) and 8 (0, 1), with probability of at least over samples ~ DT' for all Q E ~MH)), we have
In(2m/8)
As(Q) S $110 n22(m, 8T2)
(11)
2(m 1)

---

The proof (Appendix A.3) follows directly from the general IPM PB bound (Prop. 4) and the uniform convergence assumption, using a union bound argument. This bound can be seen as a template to be used to derive explicit PB bounds, by plugging in existing UC bounds. Note that while we require the existence of UC bound, the resulting bound is nonuniform (since depends on the data-dependent posterior).
Compared to the original UC bound, u(m, 6), the bound in (11) is roughly multiplied by a factor of (Drv(Q, P) E [o, I], ensuring tighter guarantees, especially the posterior is close to the prior.
For example, consider a binary classification case, with the zero-one loss function and VC(H) class H. The well-known UC theorem states that the generalization gap converges uniformly at a rate o (TCCH)/m)
Proposition 7 (VC Bound, Boucheron, Bousquet, and Lugosi (2005)). There exists some universal constant <> 0 s.t. for any 8 (0, 1) we have
P P As(h) s soy
VC(H) In(16) wh H n1) 2 1-18.
(12)
m
Using Thm. 6, we derive the following algorithm and data-dependent bound.
Corollary (Total- Variation PB Bound for VC Classes). Consider a binary classification problem, with the zemo-ne loss, and hypothesis class H. with finite VC dimension, VC(H). There exists some universal constant c. > O s.t. for any prior P E MMH)) and 5 E (0, 1), with probability of at least 1 8 over samples S ~ DDm,, for all Q MH)), have
VC(H) + In(1/s) DIv(Q, In(m/s)
As( &
(13)
2(m -
Compared the UC bound of Prop. 7, Cor. 8 multiplies the dominant term of the bound by a factor of /Drv(Q4 (Q, P), which guaranteed tighten
nonuniform (data and the bound.
Note that the total-variation based bound of Aminian al. (2022) and Rodríguez Gálvez al. (2021) assume Lipschitz loss function, while our TV bound allows non continuous loss functions such as the zero-one loss. The TV based bound of Wang al. (2019) (Thm. 1) is not directly comparable, since the empirical risk term is multiplied by a factor that goes to infinity for TVV distance that goes to 1.
Wasserstein PAC-Bayes Bounds
5.1 Template for Wasserstein-PP -BB Bound
In this section, we provide a PAC-Bayes generalization bound with the Wasserstein metric between posterior and prior and certain smoothness parameter of the generalization gap function. We explore learning settings for which H can be paired with distance metric p H. x + R 220 s.t. (H. p) is a Polish metric space (complete, separable metric space). 6 Given the distance metric p, we can define the Wasserstein distance between any two probability measures H.
Definition 9 (Wasserstein Distance). For any two probability measures P,Q on with finite first moment, the st order Wasserstein distance is
P)
def
inf PPT(Q.P)
/ p(h, (ld,,h)
(14)
HHH
where I(Q,P) denotes the set of all couplings of Q and P, that is, the set of all joint measure on H x H. whose marginals are Q and P.
'The bound of Cor. originates from Talagrand (1994). As far as we know, there is no explicit value of the universal constant in the literature. Obtaining the constant involves careful computations of covering numbers and using the chaining method (e.g.. based Thm. 1.16 and 1.17 in Lugosi (2002)). Since on the numerical evaluation the bounds, we did not include this in our work. We note that there are other VC-type bounds with explicit constants, but with an extra log(m) factor (e.g.. Vapuik (1999), Sect 3.4). See Villani (2006) Ch. 1, for discussion of this assumption.
focus
7

---

The following proposition gives a dual representation for the first-order Wasserstein distance. Proposition 10 Senntorovich-Rubinssee Duality (Villani, 2006)). For any S K, and any two probability measures P, Q с M(H)..
K (i, P)=
sup E JEFR
[F(N]]
E [F(h)]
(15)
hwwP
h~Q
where Fli is the set of K- funipichiteuunctionss w.r.t. p(h, W¹), i.e. functions that satisfy
[f) f(h')
sup (hA)))H
< K.
(16)
p(h,h') h²)
We can write the Kantorovich-Rubinsteer duality (15) using IPM formulation (Def. 3),
K (Q, = 7 (P,Q).
(17)
Using this duality we will prove the following bound.
Theorem 11 (Template for Wasserstein-P PB Bound). Assume that for any 8' E (0, 11, w.p. at least
1 - 8' over the sampling S ~ DDmm, the squared generalization gap function, (-),), is K K-pisschitz w.r.t. the metric p with some K K (m,,8 8'), Then, for any prior P E M(H) and 6 E (0, 1), with probability of at least 1 ó over samples S ~ Dm for all Q E (MHH), we have
In(2m/6)
As(Q) V K(mm, ((m,, (Q.) + 2(m 1)
(18)
The proof (Appendix A.4) follows directly from Proposition 4 and the assumption, via the union bound. Theorem 11 can be seen template to be used for deriving Wasserstein-PB bounds in various learning settings where the A K K-Lipschitz with high probability (over samples), where the rate of K K (m, +/2) should be 02/m) to ensure a factor (l//mm) multiplying the divergence between posterior and prior, as in the KL-PB bound.
Such result can be challenging prove since it requires uniform convergenee of the slope between any two hypotheses in H. Next, we will show specific learning settings where this property holds and the resulting generalization bounds.
We note that recent work Neu and Lugosi (2022) also establishes Wasserstein- -ased information- theoretic generalization bound. This work assumed infinitely smooth loss functions and established bounds on the expected generalization gap, rather than high-probabiliiyy bounds. fact, Neu and Lugosi (2022) noted that obtaining such bounds is an open problem. Observe, though, that our bound depends on the Lipschitz constant K K K(m, 6) which needs to assessed; see sections 5.2 and 5.3 for specific examples. The general problem remains open.
At more pragmatic level, we note that learning algorithms derived from minimizing Wasserstein based PB bounds have an added benefit of more stable optimization compared to KL based approaches, due to lower gradient variance, as noted in Arjovsky, Chintala, and Bottou (2017), and this distance measure can be approximated efficiently from finite samples (Cuturi, 2013; Weed & Bach, 2017)
5.2 Wasserstein-PP PB Bound for Finite Classes
We first investigate the simple case of finite hypothesis class with loss function é which is G- Lipschitz w.r.t. the metric p. Note that for finite classes, UC always holds. We derive the following bound from Thm. 11.
Theorem 12 (Wasserstein-PP Bound for Finite Classes). Let H be finite hypothesis class. Assume that for any fixed E Z, E(h, z) is a G-Lipschitz function in h wrr the metric p. Then for any prior P E M(H) and ó E (0, 1), with probability of least 8 over samples S DTH for all
Q E MMH), we have
In 1n(2m/5) 8G log((()))) () m
As( S
(19)
2(m - 1)
The proof (Appendix A.5) makes use of standard union bound arguments, Hoeffding's s concentration incquality and the template Wasserstein-PB bound (Thm. 11). Notice that compared to the standard UC bound for finite classes, Thm. 12 multiplies the bound by a nonuniform factor of / /GW1(Q,P) P).
8

---

5.3 Wasserstein-PB Bound for Loss-Gradient UC Classes
In this section we show a Wasserstein- bound for learning problems (D, H. E), with C RR, for some dimension d N+, that satisfy the standard UC property, and, additionally, satisfy UC property for the loss gradient, as defined below.
Definition 13 (Loss-Gradies UC Property). A learning problem (D, H. E), with C Rd, is said to satisfy the loss-gradient UC property. if: (i) the loss function E(h, 2) is differentiable w.r.t. h on (n)(H) x and continuous w.rt. on x Z. (ii) The problem satisfies the uniform convergence property (Def. 1). (iii) The empirical average of the loss gradient converges uniformly in L2 norm sense its mean. Le., there exists a bound function u (m, 6) 0, s.t. for any E (0, 1) we have wordd (m, 5)
+ O and for any E N
1 m
EIND EEND
Vne(h,
m Σ
Vnl(h, 24)
S surrdd (m, vh E In((H)) 2 21-6,
(20)
where V W vi(hh,2) 2) denotes the gradient of V V,,((,, w.r.t. h, for a fixed E Z, and Int(H) is the interior of H. We call ugrud, the UC bound of the loss gradient.
Theorem 14 (Wasserstein-PE Bound for Loss- Gradient UC Classes). Let (H, be metric space such that H C Rd is closed and convex set, and is the L2 distance. Assume the learning problem satisfies the loss- gradient UC property (Def. 13), with UC bound u, and UC bound of the loss gradient, word Then for any prior P E MMH) and ó E (0, 1), with probubility of at least 1 - over samples S ~ for all Q E M(H), we have
In(2m//) 2(m 1)
As(Q) < /2 vum,6/// um, 5/1))) Wi(Q, P)
(21)
The proof (Appendix A.6) is derived from the assumptions and the template Wasserstein-PP bound (Thm. 11). In learning problems that satisfy the loss-gradient UC property, we often have u(m (m, 8/4), ugrrd (m, (m,./4) E ((//m), and then the resulting bound O(!/mm). We provide full analysis that shows such rate for the following linear regression example.
5.4 Linear Regression Example
Based on the Wasserstein-PP Bound for Doss-Gradient UC Classes (Thm. 14), we derive the following corollary.
Corollary 15 (Wasserstein-PD Bound for Linear Regression). Consider a data distribution of pairs (x, w). where æ is sampled from an unknown distribution supported on a d-dimensional ball of radius r > Bd def {a E Rdd ||=1||2 < r}. and the target, y fxx), set by an unknown, possibly random, target function f B 1-1,1] The hypothesis space is Byy,
u/. and the loss function is fx, v, h) (h x - -2 Then, for any prior P E M(H) and 5 E (0, 1), with probability at least 1 over samples S Dmm,, for all Q E M(H),
(2(2m/5) 2(m 1) where (QQ P) denotes the 1st order Wasserstein distance with the L2 metric,
As(Q)= S /2((m, 6/4) umnd 6/4) W),
(22)
u(m, 0) of d(1 d(1 ((11))(1/)) and grad (m, 8) O (
d(1 +n(((n)))
(23)
m
m
The full expression of the bound appears in the theorem's 's proof (Appendix A.7). Ignoring logarithmic
factors we obtained UC bound of Ō and a Wasscrstein-PG bound of Ō v /Wi
(Q,
P)
Note that from Thm. 6 we can also deduce a TV-PB bound of order ò (VDrV(QQ,P))
In

---

comparison, the standard KL-PB bound is of order Ö
KL(Q || P)
The TV-PB bound is, at
m
worst, roughly the same the UC bound, since Dry (Q, P) S Note that since Q and P are distributions over a sphere of radius 3/r, then (Q, P) I 2. Hence, the Wasserstein-PB is also, worst, roughly the same as the UC bound. However, the KL-PB bound can be either tighter or looser, depending on P and Q. In cases where the mass of the posterior Q is concentrated in region of the hypothesis set where the prior P is arbitrarily small, then the KL divergence can be arbitrarily large, making the KL-PB bound extremely loose compared to the UC, TV-PB, and Wasserstein-PP bounds. The numerical experiment described in Appendix C demonstrates this by investigating different prior distributions with different widths. In particular, for posteriors and priors that are Dirac delta distributions (i.e., deterministic predictors), we show that the Wasserstein-PP considerably improves over the UC bound, while the KL-PB bound is undefined. We therefore demonstrated non- vacuous guarantees for deterministic models within the PB framework without requiring additional derandomization steps.
We compare the bound of Thm. 14 the bound of Corollary in Neu and Lugosi (2022), which is also dependent on the Wasserstein distance between a data-dependent output (posterior) and a base measure (prior). The bound of Thm. 14 is different in the sense that (i) holds with high probability instead of in expectation. (fi) Instead of assumiig infinitcly-smooet loss function with 8- 8-bounded directional derivatives, Thm. 14 assumes a foss-gradicn UC class. (iti) The bound scales
as Ö (VWi- W1 ugraa) instead of Ô (VW2> d8
In our linear regression example, Cor. 15 scales as 0( W1 a ugrad = =
VVVVVV
d
The loss is infinitely-smooth with & E 0(1 + r r²), and therefore Cor. 8 of Neu
and Lugosi (2022) scales as Ō ( W/2 de
o rv (01
d (1 (1+ (1+r+r2) i.e., looser by factor of
Ó + r2) compared to Cor. 15.
6 Discussion
We have presented high-probabiliy PB bounds based on integral probability metrics, that extend standard PB bounds based on KL divergence and more recent f-divergence and a-divergence based bounds, to a new class of distances. Our bounds interpolate between classic UC bounds and PB bounds, by allowing data- and algerithm-dependent complexity terms. As in all PB results, our bounds suggest improved rates when the PB posterior is close to the prior. While we have extended sigh-probability PB bounds for IPMs to novel distance measures, still an open question to do so without the UC assumption.
Possible directions for future research include: (i) Deriving high probability IPM-PB bounds (c.g. Wasserstein or TV based), without global UC assumptions (possibly using localization based ap- proaches, e-g. Local Rademacher complexities (Bartlett, Bousquet, & Mendelson, 2005; Koltchinskii & Panchenko, 2004) are computed only on a subset of hypotheses with small empirical risk). This may allow non-vacuous bounds for large-scale models where global UC-based bounds are extremely vacuous. (ii) Derivation of algorithms that utilize the bounds as minimization objectives. Based on the optimization advantages Wasserstein based costs mentioned in Sec, 5. these could lead to enhanced practical utility. Such an ad advantage could play important role in meta-lcarmin schemes where PB methods have been widely used in recent years (Amit & Meir, 2018).
Acknowledgments
We thank Nadav Merlis and Daniel Soudry for helpful discussions of this work, and the anonymous reviewers for their helpful comments. Shay Moran a Robert Shillman Fellow; he acknowledges support by ISF grant 1225/20, by BSF grant 201 8018835, by an Azrieli Faculty Fellowship, by Israel VATA, by the Technion Center for Machine Learning and Intelligent Systems (MLIS), and by the the European Union (ERC, GENERALIZATION,, 101039692). Views and opinions expressed
10

---

are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. The work of Ron Meir is partially supported by ISF grant 1693/22, by the Ollendorff Center of the Viterbi ECE Faculty at the Technion, and by the Skillman chair in biomedical sciences.
References
Alquier, (2021).
User-friendly introduction PAC-Bayes bounds.
arXiv preprint
arXiv:2110.1111 12216...
Alquier, P., & Guedj, B. (2018). Simpler PAC-Bayesian bounds for hostile data. Machine Learning,
107(5), 887-902.
Aminian, G., Bu, Y.. Wornell, G., & Rodrigues, M. (2022). Tighter expected generalization error
bounds via convexity of information measures. arXiv preprint arXiv:2202. 12150.
Amit, R., & Meir, R. (2018). Meta-learning by adjusting priors based on extended PAC-Bayes theory.
In International conference machine learning (ICML) (pp. 205-214).
Anthony, M., & Bartlett, P. L. (1999). Neural network learning: Theoretical foundations (Vol. 9). cambridge university press Cambridge.
Arjovsky, M., Chintala, S., & Bottou, L. (2017). Wasserstein generative adversarial networks. In International conference machine learning (ICML) (pp. 214-223).
J. & Bousquet, O. (2003). PAC-Bayesial generic chaining. In S. Thrun, L. Saul, & B. Schölkopf (Eds.), Advances in neural information processing systems (NeurIPS) (Vol. 16).
MIT Press.
Audibert, J.-Y., & Bousquet, O. (2007). Combining PAC-Bayesian and generic chaining bounds.
Journal of Machine Learning Research, 8(4).
Bachmann, G., Moosavi-Dezzoolli, S.-M., Hofmann, T. (2021). Uniform convergence, adversarial
spheres and simple remedy. In International conference on machine learning (ICML) (pp.
490-499).
Bartlett, P. L., Bousquet, O., & Mendelson, S. (2005).. Local Rademacher complexities. The Annals of Statistics, 33), 1497-1537.
Bastani, H., Simchi-Levi, D., & Zhu, R. (2021). Meta dynamic pricing: Transfer learning across experiments. Management Science.
Begin, L., Germain, P., Laviolette, F., & Roy, J.-F. (2016). PAC-Bayesian bounds based on the rényi divergence. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS).
Bouchcron, S., Bousquet, O., & Lugosi, G. (2005). Theory of classification: A survey of some recent advances. ESAIM: probability and statistics, 9, 323-375. Bousquet, O., & Elisseeff, A. (2002). Stability and generalization. The Journal of Machine Learning
Research, 2, 499-526.
Catoni, O. (2007). PAC-Bayesian supervised classification: the thermodynamics of statistical learning.
arXiv preprint arXiv:0712.0228.
Chee, A., & Loustau, S. (2021). Learning with BOT Bregman and Optimal Transport divergences.
hal-03262687vv.
Chuang, C.-Y., Mroueh, Y., Greenewald, K., Torralba, A., & Jegelka, S. (2021). Measuring generalization with optimal transport. Advances in Neural Information Processing Systems, 34, 8294-8306.
Clement, P.. & Desch, W. (2008). An elementary proof of the triangle inequality for the Wasserstein metric. Proceedings of the American Mathematical Society, 136(1), 333-339.
Cuturi, M. (2013). Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems (NeurIPS, 26.
Dembo, A., & Zeitouni, O. (2009). Ldp for finite dimensional spaces. In Large deviations techniques and applications (pp. 1 1-70). Springer.
Donsker, M. D., & Varadhan, S. S. (1975). Asymptotic evaluation of certain markov process expectations for large time. Comm. Pure Appl. Math..
Dziugaite, G. K., & Roy, D. M. (2017). Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Conference on uncertainty in artificial intelligence, (UAI).
Givens, C. R., & Shortt, R. M. (1984), A class of Wasserstein metries for probability distributions.
11

---

Michigan Mathematical Journal, 31(2,, 231-240.
Guedj, B. (2019). A primer on PAC-Bayesian learning. arXiv preprint urXiv:
Hou, S., Kassraie, P., Kratsios, A., Rothfuss, J., & Krause, A. (2022). Instance-dependent generaliza-
tion bounds via optimal transport. arXiv preprint arx:0v2211.01255.
Hsu, D., Kakade, S., & Zhang. T. (2012). A tail inequality for quadratic forms of subgaussian random vectors. Electronic Communications in Probability, 17, 1-6.
Jiang, Y., N.yeshaaur,, B., Mobahi, H., Krishnan, D., & Bengio. S. (2019). Fantastic generalization
measures and where to find them. arXiv preprint arXiv:1912.02.
Kingma, D., & Ba, J. (2015). Adam: A method for stochastic optimization. In International conference on learning representations (ICLR).
Kingma, D. P.,& & Welling, M. (2013). Auto-encoding variational Bayes. In International conference on learning representations (ICLR).
Koltchinskii, V., & Panchenko, D. (2004). Rademacher processes and bounding the risk of function
learning. arXiv preprint math/04055338
Lever, G., Laviolette,, F., & Shawe-Taylor, J. (2013). Tighter PAC-Bayes bounds through distribution- dependent priors. Theor. Comput. Sci., 473(Feb), 4-28.
Livni, R., & Moran, S. (2020). A limitation of the PAC-Bayes framework. Advances in Neural Information Processing Systems (NeurIPS), 33, 20543-20553.
Lopez, A. T., & Jog, V. (2018). Generalization error bounds using wasserstein distances. In 2018
ieee information theory workshop (ITW) (pp. 1-5).
Lugosi, G. (2002). Pattern classification and learning theory. In Principles of nonpurametric learning
(pp. 1-56). Springer.
Mardia, J., Jiao, J., Tánczos, E.,, Nowak, R. D., & Weissman, T. (2019, 11). Concentration inequalities for the empirical distribution of discrete distributions: beyond the method of types. Information
and Inference: A Journal of the IMA, 9(), 813-850.
Maurer, A. (2004). A note the PAC Bayesian theorem. CoRR abs/cs/0411099,
McAllester, D. (1998). Some PAC-Bayestin theorems. Conference on Learning Theory (COLT). McAllester, D. (2003). Simplified PAC-Bayesian margin bounds. Conference on Learning Theory (COLT).
Miyaguchi, K. (2019). PAC-Bayesian transportation bound. arXiv preprint arXiv:1905.13443
Müller, A. (1997). Stochastic orders generated by integrals: a unified study. Advances in Applied
probability, 29(2), 414-428.
Nagarajan, V., & Kolter, J. Z. (2019a). Deterministic PAC-Bayesian generalization bounds for deep
networks via generalizing noise-resilience. arXiv preprint arXiv::905.. 13344.
Nagarajan, V., & Kolter, J. Z. (2019b). Uniform convergence may be unable to explain generalization
in deep learning. Advances in Neural Information Processing Systems (NeurIPS), 32.
Ncu, G., & Lugosi, G. (2022). Generalization bounds via convex analysis. arXiv preprint
arXiv:2202.00 245.:22022.44885 04985.
Neyshabur, B., Bhojanapalli, S., McAllester, D., & Srebro, N. (2017). Exploring generalization in deep learning. Advances in Neural Information Processing Systems (NeurIPS). 30. Neyshabur, B., Tomioka, R., & Srebro, N. (2015). Norm-based capacity control in neural networks.
In Conference on learning theory (pp. 1376-1401).
Ohnishi, Y., & Honorio, J. (2021). Novel change of measure inequalities with applications to PAC-Bayesian bounds and monte carlo estimation. In International conference on artificial intelligence and statistics (pp. 1711-1719).
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., others (2019). Pytorch:
An imperative style. high-performance deep learning library. Advances in Neural Information Processing Systems (NeurIPS), 32.
Seerr-, A., & Guedj. B. (2022). On change of measure inequalities for f-divergences. arXiv preprint XXXi:22022005666
Rivasplata, O., Kuzborskij, I., Szepesvári, C., & Shawe- Taylor, J. (2020). PAC-Bayes analysis beyond the usual bounds. Advances in Neural Information Processing Systems (NeurIPS), 33,
16833-16845.
Rodríguez Gálvez, B., Bassi, G., Thobaben, R., & Skoglund, M. (2021). Tighter expected gener- alization error bounds via Wasserstein distance. Advances in Neural Information Processing Systems (NeurIPS), 34.
Seeger, M. (2002). PAC-Bayesian generalisation bounds for gaussian processes. Journal of Machine Learning Research, 3:233-269.
Seldin, Y. & Tishby, N. (2010). PAC-Bayesian analysis of co-clustering and beyond. JMLR 2010.
12

---

Shalev-Shwarte S., & Ben-Davidd S. (2014). Understanding machine learning: From theory to algorithms. Cambridge University Press.
Shawe-Taylor, J., & Williamson, R. C. (1997). A PAC analysis of Bayesian estimator. Proceedings the the International Conference on Computational Learning Theory (COLT).
Sriperumbudur, B. K., Fukumizu, K., Gretton, A., Schölkopf, B., & Lanckriet, G. R. (2009).
On integral probability metrics, d-divergences and binary classification. arXiv preprint 00l:00991.296
Sriperumbudur, B. K., Fukumizu, K., Gretton, A., Schölkopf, B., Lanckrict, G. R. (2012). On the empirical estimation of integral probability metrics. Electronic Journal of Statisties, 6,
1550-1599.
Talagrand, M. (1994). Sharper bounds for gaussian and empirical processes. The Annals of Probability, 28-76.
Thorpe, M. (2018). Introduction to optimal transport. Notes of Course University of Cambridge..
Vapnik, V. (1999). The nature of statistical learning theory. Springer science & business media.
Vapnik, V., & Chervonenkis, A. Y. (2015). On the uniform convergence of relative frequencies of events to their probabilities. In Measures of complexity (pp. 11-30). Springer.
Villani, C. (2006). Optimal transport: old and new. Springer Science and Business Media. Wainwright, M. J. (2019). High-dimensional statistics: A con-asymptotic viewpoint (Vol. 48).
Cambridge University Press.
Wang. H., Diaz, M., Santos Filho, J. C. & Calmon, F. P. (2019). An cetemmattioo-hhereette view of generalization via Wasserstein distance. In 2019 IEEE international symposium on information theory (ISIT) (pp. 577-581).
Weed, J., & Bach, F. (2017). Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance. Bernoulli 25 (4A), 0620-26448
Wei, C., & Ma, T. (2019). Data-dependent sample complexity deep neural networks via lipschitz augmentation. arXiv preprint arXiv:7905 006640
Xu, H., & Mannor, S. (2012). Robustness and generalization. Machine learning. 86(3), 391-423. Yang. J., Sun, S., & Roy, D. M. (2019). Fast-rate PAC-BByes generalization bounds via shifted Rademacher processes. arXiv preprint arXiv: 075585
Zhang, C., Bengio, S., Hardt, M., Recht, B., & Vinyals, O. (2017). Understanding deep learning
requires rethinking generalization. International Conference on Learning Representations (ICLR).
Zhang, J., Liu, T., & Tao, D. (2021). An optimal transport analysis on generalization in deep learning.
IEEE Transactions on Neural Networks and Learning Systems.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including thcoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
13

---

4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any asscts either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "cqlieDjIK27", "reviewer": "Reviewer_TFE4", "summary": "Authors open the classical PAC-Bayesian framework to new type of divergences, going beyond the classical KL-divergence or the $f$-divergences. They introduce the general notion of Integral Probability Metric (IPM) and they derived from it general templates for a new type of IPM-PAC-Bayesian bounds. \n\nFrom those general bounds, authors provide new concrete results for two classical divergences: the TV distance and the Wasserstein distance. ", "questions": "Do authors have an argument to counter my claim on Prop. 4 's veracity? \n\n- Is there any cases where one can compute TV-distance nor the Wasserstein one? To the local nature (see the major issue of Strengths&Weaknesses section) of all the proposed result I believe insisting on the practical extensions is now essential on this work.\n\n- I am wondering about the choice of the universal constant in Cor. 8. Is it an accessible quantity? I am wondering if the proposed bound remains fully empirical.\n\n- In Th. 11, do authors have an instance of a non-Lipschitz function verifying the assumption of being Lipschitz with high probability? \n", "limitations": "Autors are clear on their framework and the remits of their contributions. \n\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "MAJOR ISSUE:\n\nTo my understanding (please correct me if there is an argument that I missed), the preliminary theorem (Prop 4.) is not correct. Authors stated this result holds \"with probability $1-\\delta$, for all $Q\\in\\mathcal{M}(\\mathcal{H})$...\" while the correct formulation is  \"for all $Q\\in\\mathcal{M}(\\mathcal{H})$,with probability $1-\\delta$...\"\n\nI provide below a corrected version of author's proof which starts from the line 458 of the appendix.\n\nNEW PROOF--\n\nInequalities (23) and (24) imply $\\\\forall (Q,P)\\\\in \\\\mathcal{M}(\\\\mathcal{H})^2,$\n\n $\\\\mathbb{E}\\_{S \\\\sim \\\\mathcal{D}^{m}} \\\\exp \\\\left(\\\\underset{h \\\\sim Q}{\\\\mathbb{E}}\\\\left[f\\_{S}(h)\\\\right]-\\\\gamma_{\\\\mathcal{F}_{S}}(Q, P)\\\\right) \\\\leq m .$\n\nTherefore, by Markov's inequality, for any $t>0$ we have  $\\forall (Q,P)\\in \\mathcal{M}(\\mathcal{H})^2,$\n\n\\begin{multline*}\n  \\mathbb{P}\\_{S \\sim \\mathcal{D}^{m}}\\left(\\exp \\left(\\underset{h \\sim Q}{\\mathbb{E}}\\left[f_{S}(h)\\right]-\\gamma_{\\mathcal{F}\\_{S}}(Q, P)\\right) \\geq t\\right) \\\\\n   \\leq \\frac{\\mathbb{E}\\_{S \\sim \\mathcal{D}^{m}} \\exp \\left(\\underset{h \\sim Q}{\\mathbb{E}}\\left[f_{S}(h)\\right]-\\gamma_{\\mathcal{F}\\_{S}}(Q, P)\\right)}{t} \\leq \\frac{m}{t} .\n\\end{multline*}\n\n\nOr, equivalently, $\\forall (Q,P)\\in \\mathcal{M}(\\mathcal{H})^2,$\n$$\n\\mathbb{P}\\_{S \\sim \\mathcal{D}^{m}}\\left(\\underset{h \\sim Q}{\\mathbb{E}}\\left[f\\_{S}(h)\\right]-\\gamma_{\\mathcal{F}\\_{S}}(Q, P) \\geq \\ln (t)\\right) \\leq \\frac{m}{t}\n$$\n\nLet $\\delta \\in(0,1)$, we set $t=\\frac{m}{\\delta}$, and plug in $f_{S}(h) \\stackrel{\\text { def }}{=} 2(m-1) \\Delta_{S}^{2}(h)$ to get\n$$\n\\forall (Q,P)\\in \\mathcal{M}(\\mathcal{H})^2,\\mathbb{P}\\_{S \\sim \\mathcal{D}^{m}}\\left(\\underset{h \\sim Q}{\\mathbb{E}}\\left(2(m-1) \\Delta\\_{S}^{2}(h)\\right)-\\gamma_{\\mathcal{F}\\_{S}}(Q, P) \\geq \\ln (m / \\delta)\\right) \\leq \\delta\n$$\nRearranging the above, we have that, for all $Q,P \\in \\mathcal{M}(\\mathcal{H})^2$, with probability at least $1-\\delta$ over the samples $S \\sim \\mathcal{D}^{m}$, the following inequality holds\n$$\n\\underset{h \\sim Q}{\\mathbb{E}}\\left(\\Delta\\_{S}^{2}(h)\\right)<\\frac{\\gamma_{\\mathcal{F}\\_{S}}(Q, P)+\\ln (m / \\delta)}{2(m-1)} .\n$$\nBy Jensen's inequality applied to $\\Delta\\_{S}(h)^{2}$\n$$\n\\left(\\underset{h \\sim Q}{\\mathbb{E}} \\Delta_{S}(h)\\right)^{2} \\leq \\underset{h \\sim Q}{\\mathbb{E}}\\left(\\Delta_{S}^{2}(h)\\right) \\leq \\frac{\\gamma_{\\mathcal{F}}(Q, P)+\\ln (m / \\delta)}{2(m-1)}\n$$\nThe theorem follows for any pair $(Q,P)$ with probability $1-\\delta$ by taking the square root of both sides.\n\n--\n\nThe problem with author's proof is that they did not realise that they were applying Markov's inequality on a random variable depending on the sample $S$ and the distributions $Q,P$. **Modifying the posterior distribution changes the variable onto which we apply Markov's inequality and then requires a novel application of this bound.** That is why Prop 4. cannot hold with high probability for all posteriors (except on the case of a finite posterior class $C$ where one can apply an union bound on the events and maintain the result at the cost of an extra $\\log(|C|)$).\n\nThat is why the change of measure inequality is so important in classical PAC-Bayesian proofs: it allows a deterministic control over the whole class of posterior by bounding a moment depending on $Q$ by a KL divergence plus a random variable depending only on the prior $P$ and the sample $S$. Then one can apply a single time Markov's inequality on this random variable to obtain an uniform PAC bound over all the posteriors.\n\n\nThus, this apparently small modification of the result has actually huge consequences:\n\n- All the theorems provided in the paper lose the strength of having a global control over the posterior class : they only have a local control over a single posterior, which is not catastrophic but I believe this fact changes the spirit of the paper. Indeed, I think authors should now also focus on constructive procedure to exhibit concrete posteriors (which still benefits from author's theoretical guarantees)\n\n- The place of the change of measure inequality is crucial to obtain strong global guarantees and is not only a mathematical technique to involve KL-divergence. Authors should also check and refer to the work of (Picard-Weibel and Guedj, 2022) which tries to generalise the change of measure inequality to others type of divergences.\n\n\nOther points:\n\n- This major point being said, I am not sure on how I should consider the rest of the new resuts of the paper as they are all derived from Prop. 4.  I see plenty of results which are now local on the choice of the couple $(Q,P)$. Then I am wondering if one can derive some concrete optimisation routes from those upper bounds if one restricts to specific classes. More generally, I did not see much discussion about the range of the proposed results which is a shame, especially when authors still have more than a half page available.\n\n- I would have appreciated more discussion about the proposed theorems, their novelty and the interest of considering such new distances (although I admit  the end of Sec. 5 goes in this direction) given the extra space authors still have\n\n- I find interesting the idea of exploit IPM onto a PAC-Bayes framework. It may be a fruitful tool to extract PAC-Bayes from KL and $f$-divergences.\n\n\nCONCLUSION: My main problem with this work is Prop. 4's proof. To me, this point weakens the paper a lot as it shows that for instance the TV distance nor the Wasserstein one are 'less adapted' to PAC-Bayesian than the KL divergence as it allows to only recovers local results for a similar framework. This point, to me, should be at least acknowledged and a discussion about the change of measure inequality should be proposed in this work. However, I think that with a more careful study, this line of research could be fruitful and I do not contest the novelty of the proposed approach. A convincing axis of work would be to focus on the practical extensions of their work and exploit the fact that, according to the authors, Wasserstein distance is potentially more stable in practice. Having concrete extensions would for me, compensate the local behavior of those results.\n\n\n\n ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "UKbN7AgGzsg", "reviewer": "Reviewer_cRSg", "summary": "The present work develops PAC-Bayes like generalization bounds using integral probability metrics in place of divergences between a prior and the posterior. The bounds combine aspects of data independent ‘uniform convergence’ bound (based on empirical process theory), and data-dependent bounds (as is typical of PB bound, as well as margin based bounds, etc.) in a way that generalizes both since the present work’s bounds are smaller than one would expect from either alone. The present work specializes this to two particular IPM’s, total variation distance and Wasserstein distance. The focus is on theoretical results;  specific examples and numerical evaluation of bounds are not discussed.", "questions": "NA", "limitations": "Lack of experimental/numerical results showing the new bounds are materially better in practice than existing ones.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper has a number of strengths, which lead me to support its acceptance. \nThe writing is very clear, easy to follow, concise and accurate. The paper was a pleasure to read.\nThe results are interesting, useful, and (to my knowledge) completely original. \nThe proofs are straight forward and easy to follow. Thus the results appear to be sound.\nAn aspect of the work which I find quite compelling, and an especially good fit for Neurips, is that the Wasserstein bounds do not require the posterior to be abs.continuous w.r.t. the prior, which means the bounds can be applied to SGD  training of general models, without modification to ensure abs.continuity. This is in contrast to prior work where similar bounds are expressed in terms of divergences.\n\nThe main weakness that I would like to point out, and the only item which addressed well would likely lead me to increase my score, is the lack of experimental or numerical evidence that shows that the theoretical improvements to standard bounds made herein are material in practical settings. An example of a model+training method where UC and PB bounds are both loose and the bounds of the present work are tight would materially improve the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6M07vjgXXdS", "reviewer": "Reviewer_3Pda", "summary": "The paper presents new generalizations bounds that aesthetically look like a mix between uniform convergence and PAC-Bayesian bounds.   In one instantiation, the new bound can improve on uniform convergence bounds by a factor proportional to the square root of the TV distance between a posterior and prior distribution. The authors achieve their results thanks to a new IPM-based generalization guarantee. ", "questions": "Have you done/can you include any experiments to compare the new bounds to previous PAC-Bayesians ones? ", "limitations": "Some suggestions for improvement (mainly typos):\n- It would be good to include an explicit comparison of the new bounds to those of, e.g., Neu and Lugosi (2022). (If space is an issue, at least include the bound of the latter in the appendix).\n- Eq (4), f_S is not defined within Def 3\n- Line 199: with the the zero-one -> with the zero-one\n- Line 234: $K(m,\\delta')$-Lipschitz? Do you mean just $K$-Lipschitzness with $K$ that may depend on $m$ and $\\delta'$? If so, this is a little confusing---just say $K$-Lipschitz. \n- Line 239-240: \"is K-Lipschitz with high probability, where the rate of $K$ is preferably $O(1/m)$\" Not clear what you mean by this. Clarify.\n- Line 273: \"Assume that for any fixed $z ∈ Z$, $f(h,z)$ is continuously differentiable for any $h \\in H$\". This is redundant as it is already a condition in Def 13.\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The new IPM-based generalization guarantees seem new and would be of interest to the ML community in my opinion. One desirable feature of these bounds is that they allow for degenerate posteriors (the posterior need not be absolutely continuous w.r.t. the prior), which is not allowed in standard PAC-Bayesian bounds. \n\nIn terms of weaknesses, the fact that uniform convergence is required in most bounds is not ideal. Especially, since the new bounds depend on the uniform convergence error which can be large for Neural Networks, for example. After all, having non-vacuous bounds for large classes was one of the main motivations behind the paper. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5cpNgvl5hD7", "reviewer": "Reviewer_2x57", "summary": "The paper derives PAC-Bayes generalization bounds taking as complexity term integral probability metrics, in particular Total Variation and Wasserstein distance.\nExisting bounds based on such complexities stand in expectation over samples from the data distribution, while the new results stand with high probability.\nThe principal requirements for deriving such bounds is that the loss is bounded and Uniform Convergence stands. The new certificates are potentially tighter than this type of classical results as they are algorithm and data dependent.", "questions": "My principal question is detailed in weaknesses 2. In other words, in which settings the new results improve on both classical Uniform Convergence bounds and PAC-Bayesian bounds? ", "limitations": "The limitations of the work are adequately addressed.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### strengths\n1. To the best of my knowledge the results are novel and non-trivial, as it is not straightforward to derive bounds with Integral Probability Metric within the PAC-Bayesian framework. In my opinion, the main advantage of the new certificates is that they drop the requirement of absolute continuity, hence the prior distribution can have null mass on bad predictors of the hypothesis class.\n\n2. The paper is generally well presented and the proofs are clear and easy to follow.\n\n### weaknesses\n1. I find the argument that this work should improve existing generalization bounds for over-parameterized model weak. lt is not clear whether the new factors really tighten the bounds enough to make them non-vacuous (at the very least). On the contrary introducing VC or Radamacher complexity measures in PAC-Bayes bounds might end up make them looser, as these complexity measures do not correlated well with generalization (see e.g. [1]). On the other hand, dropping the constraint of absolute continuity potentially allows to derive certificates for dirac posteriors, hence to remove the need to derandomize the bound for deterministic models. However, the IPM might become too big for the available sample size. An empirical analysis or reporting few example settings would have helped showing in which contexts the new results have practical interest.\n\n2. The literature on early works on algorithm dependent guarantees is not reported. Please consider citing at least the following seminal works: Uniform Stability [2], Algorithmic Robustness [3].\n\n### minors\n#### Writing\nParagraph 40-54: specify when expectations/probabiltities are over data or over predictors; which uniform convergence assumptions do you refer to?\nDiscussion: which works are referred to as \"localized based approaches\"?\n\n#### Typos\n1. line 48: probabily -> probability\n2. line 51: it can -> can\n3. line 243: Wasserstein-BP -> Wasserstein-PB \n4. Discussion: divergences -> distances\n\n[1] Jiang, Yiding, et al. \"Fantastic generalization measures and where to find them.\" ICLR (2020).\n\n[2] Bousquet, Olivier, and André Elisseeff. \"Stability and generalization.\" The Journal of Machine Learning Research 2 (2002): 499-526.\n\n[3] Xu, Huan, and Shie Mannor. \"Robustness and generalization.\" Machine learning 86.3 (2012): 391-423.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept