Learning via Wasserstein-Based High Probability Generalisation Bounds
Authors: Paul Viallard
Maxime Haddouche
Umut Simsekli
Benjamin Guedj
Venue: NeurIPS 2023 poster (2023)
Keywords: Wasserstein
PAC-Bayes
Generalisation Bound
Algorithm

Abstract: Minimising upper bounds on the population risk or the generalisation gap has been widely used in structural risk minimisation (SRM) -- this is in particular at the core of PAC-Bayesian learning. Despite its successes and unfailing surge of interest in recent years, a limitation of the PAC-Bayesian framework is that most bounds involve a Kullback-Leibler (KL) divergence term (or its variations), which might exhibit erratic behavior and fail to capture the underlying geometric structure of the learning problem -- hence restricting its use in practical applications.
As a remedy, recent studies have attempted to replace the KL divergence in the PAC-Bayesian bounds with the Wasserstein distance. Even though these bounds alleviated the aforementioned issues to a certain extent, they either hold in expectation, are for bounded losses, or are nontrivial to minimize in an SRM framework.  In this work, we contribute to this line of research and prove novel Wasserstein distance-based PAC-Bayesian generalisation bounds for both batch learning with independent and identically distributed (i.i.d.) data, and online learning with potentially non-i.i.d. data. Contrary to previous art, our bounds are stronger in the sense that (i) they hold with high probability, (ii) they apply to unbounded (potentially heavy-tailed) losses, and (iii) they lead to optimizable training objectives that can be used in SRM. As a result we derive novel Wasserstein-based PAC-Bayesian learning algorithms and we illustrate their empirical advantage on a variety of experiments.

Learning via W High Probability
Generalisation Bounds
Paul Viallard"
Maxime Haddouche" Inria, University College London and Université de Lille, France
Inria, CNRS, Ecole Normale Supérieure,
PSL Research University, Paris, France paul. viallard@inria.
maxime. wwwdohchehinnd...c.c..c. fr
Umut Şimçekli
Benjamin Guedj
Inria, CNRS, Ecole Normale Supérieure PSL Research University, Paris, France umut.simsede wiaeeeekiiiiiii.......
Inria and University College London, France and UK benjaming gued @inria. fr
Abstract
Minimising upper bounds on the population risk or the generalisation gap has been widely used in structural risk minimisation (SRM) this is in particular at the core PAC-Bayesian learning. Despite its successes and unfailing surge of interest in recent years, limitation of the PAC-Bayest AAC-Bayesian framework is that most bounds involve a Kullback- Leibler (KL) divergence term (or its variations), which might exhibit erratic behavior and fail to capture the underlying geometric structure of the learning problem hence restricting its use in practical applications. As remedy, recent studies have attempted replace the KI. divergence in the PAC-Bayesian bounds with the Wasserstein distance. Even though these bounds alleviated the aforementioned issues bounded losses, or are nontrivial to minimize in an SRM framework. In this work, we contribute this line of research and prove novel Wasserstein distance-based PAC-Bayesian generalisation bounds for both batch learning with independent and identically distributed (i.i.d)) data, and online learning with potentially non-i.i.d data. Contrary to previous art, our bounds are stronger in the sense that (i) they hold losses, with high probability, (ii) they apply unbounded (potentially heavy- and (iā) they lead to optimizable training objectives that can be used in SRM. As a result we derive novel Wasserstein- based PAC- MaC-Bayesian learning algorithms and we illustrate their empirical advantage on variety of experiments.
certain extent, they either hold in expectation, are for
Introduction
Understanding generalisation is of the main challenges in statistical learning theory, and even more so in modern machine learning applications. Typically, learning problem is described by hypothesis (or predictor) space a data space Z, and loss function E: H x Z + R. The goal is to estimate the population risk of given hypothesis h, defined as (,(h) " z)), where μ denotes the unknown data distribution over Z.
tuple (H, Z, f) consisting
As μ is not known, in practice, a hypothesis h is usually built by (approximately) minimising the empirical risk, given by (h) = 1 Σm E(h, z.), where S = {z, 2) is dataset of m data points, independent and identically distributed (i.i.d) from μ. We define the generalisation gap of hypothesis h as (h) (h).
The authors contributed equally this work
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Developing upper bounds on the generalisation gap. i.e., generalisation bounds has been a long- standing topic in statistical learning. While a plethora of techniques have been introduced, the PAC-Bayesian framework has gained significant traction over the past two decades to provide non-vacuous generalisation guarantees for complex structures such as neural networks during the training phase (see DR17, PORPH+21, PRSS21, among others). In these works, the bounds are also used to derive learning algorithms by minimising the right-hand side of a given bound. Beyond neural networks, the flexibility of PAC-Bayes learning makes it useful toolbox to derive both theoretical results and practical algorithms in various learning fields such as reinforcement learning [FP10], online learning [HG22], multi-armed bandits [SLST* 11, SLCB * 12, SAC23], meta-learning [AM18, FM21, RFJK21, RJFK22, DCL to name but a few. The PAC- PAC-Bayesian bounds focus on randomised setting where the hypothesis is drawn from dependennn distribution p E M(H)), where M(H) denotes the set of probability distributions defined on H. A classical PAC-Bayesian result is [Mau04, Theorem 5] (the so-called McAllester bound), which states that, with probability at least 1 - 5, for any posterior distribution E MMH),
kL(p|TT) In 2ym
(h) Rs(hi] s Rmpp
E
2m
where π E M(H) is any data-free distribution and KL denotes the Kullback-Leibler divergence. In analogy with Bayesian statisties, is often called the prior, and p is called the posterior we refer to [Gue19] for a discussion on these terms.
While PAC-Bayesian bounds remain nowadays of the utmost interest to explain generalisation in various learning problems [LGGL19, MGG19, NGG20, MGW20, BG21, HGRS21, ZVM+21, BG22b, BG22a, BZG22, CSDG22, 22, FRKP22, BG23, SAC23, RACA23], they mostly rely on the KL divergence or variants which causes two main limitations: (i) as illustrated in the generative modeling literature, the KL divergence does not incorporate the underlying geometry or topology of the data space Z, hence can behave in an erratic way [ACB17], (ii) the KL divergence and its variants require the posterior P to be absolutely continuous with respect to the prior However, recent studies [CDE*2] have shown that, in stochastic optimisation, the distribution of the iterates, which is the natural choice for the posterior, can converge to singular distribution, which does not admit a density with respect to the Lebesgue measure. Moreover, the structure of the singularity (i.e., the fractal dimension of p) depends on the data sample S [CDE+21] Hence, in such case, it would not be possible to find a suitable prior æ that can dominate for almost every S ~ ,=",, which will trivially make [L too and the generalisation bound vacuous.
Some works have focused on replacing the Kullback-Leible divergence with more general diver- gences in PAC-Bayes [AG18, OH21, PWG22], although the problems arising from the presence of the KT. divergence in the generalisation bounds are actually not specific to PAC-Bayes: information- theoretic bounds [GMGA17, XR17, RZ20] also suffer from similar issues they are based mutual information term, which is the KL divergence between two distributions. In this context, as remedy to these issues introduced by the KL divergence. [ZLT18, WDFC19, GBTS21, LN22] proved analogous bounds that are based on the Wasserstein distance, which arises from the theory of optimal transport [Mon81]. As the Wasserstein distance inherits the underlying geometry of the data space and does not require absolute continuity, it circumvents the problems introduced by the KL divergence. Yet, these bounds hold only in expectation, i.e., none of these bounds is holding with high probability over the random choice of the learning sample S ~ pM
In the context of PAC-Bayesiag learning, the recent works [AEMM22, CL.21] incorporated Wasser- stein distances as a complexity measure and proved generalisation bounds based on the Wasserstein distance. More precisely, [AEMM22] proved high-probability generic PAC-Baycsian bound for bounded losses depending on an integral probability metric [Mü97], which contains the Wasserstein distance as special case. On the other hand, [CL21] exploited PAC-Bayesian tools to obtain learning strategies with their associated regret bounds based on the Wasserstein distance for the online learning setting while requiring a finite hypothesis space and do not deal with generalisation.
Contributions. The theoretical understanding of the high-probabillty generalisation bounds based on the Wasserstein distance is still limited. The aim of this paper is not only to prove generalisation bounds (for different learning settings) based on the optimal transport theory but also to propose new learning algorithms derived from our theoretical results.

---

(i) Using the supermartingale toolbox introduced in [HG23a, CWR23), we prove in Section 3.1, novel PAC- BaC-Baaesinn bounds based on the Wasserstein distance for i.i.d. data. While [AEMM22] proposed a McAllester-like bound for bounded losses, we propose a Catoni-like bound (see e.g., ARC16, Theorem 4.1) valid for heavy-tailed losses with bounded order moments. This assumption is less restrictive than assuming subgaussian or bounded losses, which are at the core many PAC-Bayes results. This assumption also covers distributions beyond subgaussian or subexponential ones (e.g., gamma distributions with scale smaller than I, which have an infinite exponential moment).
(ii) We provide in Section 3.2 the first generalisation bounds based on Wasserstein distances for the online PAC-Bayes framework [HG22]. Our results are, again, Catoni-like bounds and hold for heavy-tailed losses with bounded order 2 moments. Previous work [CI.21] already provided online strategics mixing PAC-Bayes and Wasserstein distances. However, their contributions focus on the best deterministic strategy, regularised by a Wasserstein distance, with respect to the deterministic notion of regret. Our results differ significantly provide the best-regularised strategy (still in the sense of Wasserstein term) with respect to the notion of generalisation, which is new.
(iii)
As our bounds are linear with respect to Wasserstein terms (contrary to those of AEMM22), they are well suited for optimisation procedures. Thus, we propose the first PAC-Bayese B---ssaysi learning algorithms based Wasserstein distances instead of KL divergences. For the first time, we design PAC- AaC-Bays algorithms able to output deterministic predictors (instead of distributions over all H() designed from deterministic priors. This is due to the ability of the Wasserstein distance to measure the discrepancy between Dirac distributions. We then instantiate those algorithms in Section 4 various datasets, paving the way to promising practical developments of PAC-Bayes learning.
To sum up, we highlight two benefits of PAC-Bayes learning with Wasserstein distance. First, it ships with sound theoretical results exploiting the geometry of the predictor space, holding for heavy-tailed losses. Such a weak assumption on the loss extends the usefulness of PAC-Bayes with Wasserstein distances wide range of learning problems, encompassing bounded losses. Second, it allows us to consider deterministic algorithms (i.e., sampling from Dirac measures) designed with respect to the notion of generalisation: showcase their performance in experiments.
Outline. Section 2 describes our framework and background, Section 3 contains our new theoretical results and Section 4 gathers our experiments. Appendix A gathers supplementary discussion, Appendix B contains all proofs of our claims, and Appendix C provides insights into our practical results as well as additional experiments.
2 Our framework
Framework. We consider a Polish predictor space H. equipped with a distance d and a o-algebra En, a data space Z, and loss function l H Z + R. In this work, we consider Lipschitz functions with respect to d. We also associate filtration (Fi))z1 adapted to our data (zi)i=1....mm and we assume that the dataset S follows the distribution D. In PAC-Bayes learning, we construct a data-driven posterior distribution E M(H) with respect to prior distribution π.
For all i, we denote by B.[:] the conditional expectation B[- Fi). In this work, consider data-dependent priors. A stochastic kernel is mapping π : U m= 2 x Σn -> [0, 1] where (i) for any B E Ex,, the function S (S, B) is measurable, (ii) for any dataset S, the function B +
Definitions.
K (S, B) is probability measure over H.
In what follows, we consider two different learning paradigms: batch learning, where the dataset is directly available, and online learning, where data streams arrive sequentially.
Batch setting. We assume the dataset S to be i.i.d., so there exists distribution μ over Z such that D nT"h We then define, for given E H. the risk to be R,, := [zza[[((h, z)] and its empirical counterpart Rs == 1 Σm E(h, 2,). Our results aim to bound the expected generalisation gup defined by En~p [R, SI....,Sk. We consider K stochastic kernels ,,,-.., R such that for any S, the distribution (S..) does not depend on S..
[s))).. We assume that the dataset S is split into K disjoint sets
3

---

Online setting. We adapt the online PAC-Bayes framework of [HG22]. We assume that we have access to stream of data S (Z.).=I.....mm arriving sequentially. with no assumption on D. In online PAC-Bayes, the goal is to define posterior sequence (pt)iz1 from a prior sequence (T:))21, which can be data-dependent. We define an online predictive sequence (Æ=) satisfying: (i) for all i and dataset S, the distribution n, (S...) .) is F1 measurable and (ūi) there exists To such that for all i 2 1, we have n; (S. > то- This last condition covers, in particular, the case where H is an Euclidean space and for any the distribution Si,s is Dirac mass. All of those measures uniformly continuous with respect to any Gaussian distribution.
Wasserstein distance. In this paper, we focus on the Wasserstein distance of order (a.k.a., Earth Mover's distance) introduced by [Kan60] in the optimal transport literature. Given distance d: AAx A + R and a Polish space (AA, d), for any probability measures and [3 on A, the Wasserstein distance is defined by
W(a, == inf {
E d(a, (1).b)] (ET(a. ((.b))
where I' (3 is the set of joint probability measures y E MM(A²) such that the marginals are a and B. The Wasserstein distance aims to find the probability measure y MM42) minimising the expected cost E ((,,b)~> d(a, b). We refer the reader to [Vil09, PC19] for an introduction to optimal transport.
3 Wasserstein-based PAC-Bayesian generalisation bounds
We present novel high-probability PAC-Bayesian bounds involving Wasserstein distances instead of the classical Kullback-Leibler divergence. Our bounds hold for heavy-tailed losses (instead of classical subgaussian and subexponential assumptions), extending the remits of [AEMM22, Theorem 11]. We exploit the supermartingale toolbox, recently introduced in PAC-Bayes framework by [HG23a, CWR23, JJKO23J, to derive bounds for both batch learning (Theorems and 2) and online learning (Theorems and 4).
3.1 PAC-Bayes for batch learning with i.i.d. data
In this section, we use the batch setting described Section 2. We state our first result, holding for heavy-tailed losses admitting order moments. Such an assumption is in line, for instance, with reinforcement learning with heavy-tailed reward (see, e.g., LZ11, LWHZ19, ZS21).
Theorem 1. We assume the loss to be L-LLipschitz Then, for any (0. 1). for any sequence of positive scalar (>:)vE with probability at least 1 over the sample S, the following holds for the distributions Ti,S == T((S,.) and for any M(H):
(h) - Rs(h)
tepp
L K
K
In
d
(Ms.(()) + (isi(()))
W (p,
TI,)) + m A;
+
m
2
i=1
where T1,8 does not depend on S., Also, for any i, i,1S% we
have Vis,(()) =
ExEs, (e(h, (((h,))-R,((e R₂(h))² and (is Es, (1))
The proof is deferred to Appendix B.I. While Theorem holds for losses taking values in R, many learning problems rely practice on more constrained losses. This loss can be bounded as in the case of, e.g., supervised learning or the multi-armed bandit problem [Sli19], or simply non-negative as in regression problems involving the quadratic loss (studied, for instance, in Cat16, CG17). Using again the supermartingale toolbox, we prove in Theorem 2 tighter bound holding for heavy-tailed non-negative losses.
Theorem assume our loss & to be non-tigetive and I--Lipschitz We also assume that, for any 1 < i < K, for any datasetS, we have Bn-na(..))arm [E(h, 2 < (bounded order 2 moments for

---

priors). Then, for any 8 E (0, 1]. with probability at least 1 - 8 over the sample S, the following holds for the distributions Ki == (i...) and for any p E M(H):
K T W(P, TT,S)
K
2 In K
E homp
R - Rs
-
+
m
i=1 m²
where Ti,s does not depend on S...
Note that when the loss function takes values in [0, 1]. an alternative strategy allows tightening the last term of the bound by a factor 1/2. This result is rigorously stated in Theorem 6 of Appendix B.3.
High-level ideas of the proofs. Theorems and 2 structured around two tools. First, exploit the Sertorovicc-Rubissteen duality [Vil09, Remark 6.5] to replace the change of measure inequality [Csi75, DV76]: this allows us to consider Wasserstein distance instead of a KL term. Then, we exploit the supermartingales used in [HG23a, CWR23J alongside Ville's inequality (instead of Markov's one) to obtain high probability bound holding for heavy-tailed losses. Combining those techniques provides our PAC-Bayese bounds.
Analysis of our bounds. Our results hold for Lipschitz losses and allow to consider heavy-tailed losses with bounded order moments. While such an assumption on the loss is more restrictive than in classical PAC-Bayes, allowing heavy-tailed losses is strictly less restrictive. While Theorem I is our most general statement, Theorem 2 allows recovering a tighter result (without empirical variance terms) for -on-nttatvve heavy-tailed losses. An important point is that the variance terms are considered with respect to the prior distributions Ti.s and not p as in [HG23a, CWR23]. This is crucial as these papers rely on the implicit assumption of order 2 moments, holding uniformly for all E (HH,, while we only require this assumption for the prior distributions assumption is in line with the PAC-Bayesian literature, which often relies bounding averaged quantity with respect to the prior. This strength is a consequence of the Kantorovich-Rubinste duality. To illustrate this, consider i.i.d. data with distribution μ admitting a finite variance bounded by V and the loss E(h, z) = //- 2| where both f and lie in the real axis. Notice that in this particular case, we can imagine that is data point and h is a hypothesis outputting the same scalar for all data. To satisfy the assumption of Theorem 2, it is enough, by Cauchy Schwarz, to satisfy E a.ses 2) S E[Ah] 2V E[hh]] + V2 S 1 for all Ti On the contrary. [HG23a, CWR23] would require this condition to hold for all p. which is more restrictive. Finally, an important point that our bound allows us to consider Dirac distributions with disjoint support as priors and posteriors. On the contrary, KI. divergence forces us to consider a non-Dirac prior for our bound to be non-vacuous. This allows us to retrieve a uniform-convergeen bound described in Corollary 7.
K. Such an
Role of data-dependent priors. Theorems 1 and 2 allow the use of prior distributions depending possibly on a fraction of data. Such dependency is crucial to control our sum of Wasserstein terms as we do not have an explicit convergence rate. For instance, for a fixed K, consider compact predictor space H. a bounded loss and the Gibbs posterior defined as dp(h) x exp (-)Rs(h) dh where A >>00 0. Also define for any and S, the distribution ddt,,((h) x exp (->Rs/s; (h)) dh. Then, by the law of large numbers, when m goes to infinity, for any h, both R (h) and (Rs/s, (h)) converge to (h). This ensures, alongside with the dominated convergence theorem, that for any i, the Wasserstein distance W(p,T,,) goes to zero as m goes to infinity.
Comparison with the literature. [AEMM22, Theorem 11] establishes a PAC-Bayes bound with Wasserstein distance valid for bounded losses being Lipschitz with high probability. While we circumvent the first assumption, the second one is less restrictive than actual Lipschitzness and can also be used in our setting. Also [AEMM22, Theorem 12) proposes an explicit convergence for finite predictor classes. We show in Appendix A that are also able to recover such convergence.
Towards new PAC-Bayesian algorithms. From Theorem 2, we derive a new PAC-Bayesian algorithm for Lipschitz non-negative losses:
[Rs(h)] + Σ L W(p, TT,s).
argmin E (EM(H) hmp
(2)
m
Equation (2) uses Wasserstein distances as regularisers and allows the use of multiple priors. We compare ourselves to the classical PAC-Bayes algorithm derived from [Cat07, Theorem 1.2.6] (which
5

---

leads to Gibbs posteriors):
argmin E [Rs(h]] + KL a)
PEM(H) hwop
Considering Wasserstein distance in Equation (2) makes our algorithm more flexible than in Equation (3), the KL divergence implies absolute continuity w.r.f. the prior т. Such an assumption not required to use Equation (2) and covers the case of prior Dirac distributions. Finally, Equation (2)
relies on a fixed value K whose value is discussed below.
Role of K. We study the cases K = 1, vm, and m in Theorem 2. We refer to Appendix A for detailed treatment. First of all, when K 1, we recover classical batch learning setting where all data are collected at once. In this case, we have a single Wasserstein with no convergence rate coupled with a statistical ersatz of /ln(1/6)/m. However, similarly to [AEMM22, Theorem 12], in the case of finite predictor class, we are able recover an explicit convergence rate. The case K = / provides a tradeoff between the number of points required to have good data-dependent priors (which may lead to a small > ((p, Ti)) and the number of sets required to have an explicit convergence rate. Finally, the case K m leads to vacuous bound as we have the incompressible term v In (mm5), which makes the bound vacuous for large values of m. This means that the batch setting is not fitted to deal with a data stream arriving sequentially. To mitigate that weakness, we propose in Section 3.2 the first online PAC-Bayes bounds with Wasserstein distances.
3.2 Wasserstein-basee generalisation bounds for online learning
Here, we use the online setting described in Section and derive the first online PAC-Bayes bounds involving Wasserstein distances in Theorems 3 and 4. Online PAC-Bayes bounds are meant to derive online counterparts of classical PAC-Bayesian algorithms [HG22], where the KI.-divergence acts as regulariser. We show in Theorems 3 and 4 that it is possible to consider online PAC-Bayesin algorithms where the regulariser is a Wasserstein distance, which allows us to optimise on measure spaces without a restriction of absolute continuity.
Theorem 3. We assume our loss to be L-Lipschitz. Then, for any ò E (0,1), 1]. with probability at least 8 over the sample S, the following holds for the distributions S4, == (S. and for any sequence (pi)i=1...m M(H))"
m E hempp
m
B[e(h,, ) Fi-1] E(h,, zi)
2L
A
21(h,,2)++ vi(ha)
In(1/5)
E hamTLE
X
where for all i, Va( 2;) = (E(h,, 2;) E4-1 [(,,, 2;) is the conditional empirical variance at time and V((h.) = E, (V 2;)] is the true conditional variance.
The proof is deferred Appendix B.4. We also provide the following bound, being an online analogous of Theorem 2, valid for non-negative heavy-tailed losses.
Theorem 4. We assume our loss to be non-negative and L-Lipschitz. We also assume that, for any i, S, ()) [E,-i[[(h,, ) < 1 (bounded conditional order 2 moments for priors). Then, for any 8 E (0, 11, with probability at least 1 - 8 over the sample S, any online predictive sequence (used as priors) (TT) we have with probability at least - over the sample S ~ p. the following, holding for the data- date-dependent measures is TT(SS.) and any posterior sequence (pt)
E h.mps
B(e(h;,2.) Fi-1l E(hi, 2i)
2T.
W(p,,
2ln (t) m
m
m
The proof is deferred to Appendix B.5.
Analysis of our bounds. Theorems 3 and 4 are, to our knowledge, the first results involving Wasserstein distances for online PAC-Bayes learning. They are the online counterpart Theorems and 2, and the discussion of Section 3.1 about the involved assumptions also apply here. The sum of

---

Wasserstein distances involved here is a consequence of the online setting and must grow sublinearly for the bound to be tight. For insaacce, when (p; = )221 is the output of an online algorithm outputting Dirac measures and a P:-1, the sum of Wasserstein is exactly Σi= d(h,, h4- 1)- This sum has to be sublinear for the bound to be non-vacuous, and the tightness depends on the considered learning problem. An analogous of this sum can be found in dynamic online learning [Zin03] where similar sums appear as path lengths to evaluate the complexity of the problem.
Comparison with literature. We compare our results to existing PAC-Bayes bounds for martingales of [SLCB+ 12]. [SLCB+12. 12. Theorem 4] is PAC-Bayes bound for martingales, which controls an average of martingales, similar to our Theorem 1. Under boundedness assumption, they recover McAllester-tyy typpe bound, while Theorem 1 is more of a Catoni-type typed result. Also, [SLCB* 12, Theorem 7] is Catoni-typed bound involving a conditional variance. similar to our Theorem 4. They require to bound uniformly the variance on all the predictor sets, while we only assume averaged variance with respect to priors, which is what we required to perform Theorem 4.
new online algorithm. [HG22] derived from their main theorem, an online counterpart of Equation (3), proving it comes with guarantees. Similarly, we exploit Theorem 4 to derive the online counterpart of Equation (2), from the data-free initialisation pt
Vi 2 1, Pi E argmin E [e(h; 2:)] 2LW n.,s).
PE.(H) hoop
We highlight the merits of the algorithm defined by Equation (4), alongside with the one from Equation (2), in Section 4.
4 Learning via Wasserstein regularisation
Theorems 2 and 4 are designed to be informative on the generalisation ability of a single hypothesis even when Dirac distributions are considered. In particular, our results involve Wasserstein distances acting as regularisers on H. In this section, we show that a Wasserstein regularisation of the learning objective, which comes from our theoretical bounds, helps to better generalise practice. Inspired by Equations (2) and (4), we derive new PAC-Bayesian algorithms for both batch and online learning involving a Wasserstein distance (see Section 4)1,, we describe our experimental framework in Section 4.2 and we present some of the results in Section 4.3. Additional details, experiments, and discussions are gathered Appendix C due to space constraints. All the experiments are reproducible with the source code provided on GitHub at https: pettps://githut com/ com/paulviallard NeurIPS23-PE -w-.aassrsstte..n
4.1 Learning algorithms
Classification. In the classification setting, we assume that the data space Z = X'xy is composed of a d-dimensional input space X' = {x E Rd [ S 1} and a finite label spuce ) = {l...., [) with | labels. We aim to learn models hw Rd >> R parameterised by a weight vector w that outputs, given input E X, score /w [x][ IR for each label y'. This score allows us assign a label to x E X; to check if fw classifies correctly the example (x, y). we use the classification loss defined by (hwws (x) == 1 [x)(v) maxx' hw (x)[y') < 0). where 1 denotes the indicator function.
Batch algorithm. In the batch setting, we aim to learn a parametrised hypothesis Aw E H. that minimises the population classification risk Ry (hw) E (x,))= L" (hw: (x, B)) that we can only estimate through the empirical classification risk Rs (hw))) = I m >m= (hww (x1, y:)). To learn the ... are Dirac masses, hypothesis, we start from Equation (2), when the distributions p and T1,..., TK
localised at hws /ww..... Aww E H respectively. Indeed, in this case, W(p. :T.S) = d(hw. hw..) for any i. However, the loss ( z) is not Lipschitz and the derivatives z E X' X D, which prevents its use in practice to obtain such a hypothesis hw Instead, for the population risk R,, (h) and the empirical risk (h) (in Theorem and Equation (2)), we consider 1
zero for all examples
the loss (h,, (x, 3)) = |>)] Ey Sy max(O, 1-yy(hly -h(y))))))))) which is Lipsschhiitz w.t. the outputs This loss has subgradients everywhere, which is convenient in practice. We go
7

---

step further by (a) setting L and (b) adding parameter > 0 to obtain the objective
|S m
argmin
Rs (kw(ww) te
Σ
d (low, (tww, Now:
(5)
Aww EW
EH
A=1
To (approximately) solve Equation (5), we propose a two-step algorithm. First, PRIORS LEARN- ING learns K hypotheses liw..... Aww E H by minimising the empirical risk via stochastic gradient descent. Second, POSTERIOR LEARNING learns the hypothesis how E H by minimising the objective associated with Equation (5). More precisely, PRIORS LEARNING outputs the hy- potheses : h.w. obtained by minimising the empirical risk through mini-batches. Those batches are designed such that for any i, the hypothesis lw. does not depend on S, Then, given hw,....,, ....,,,,g H. POSTERIOR LEARNING minimises the objective in Equation (5) with mini- batches. Those algorithms are presented in Algorithm 1 of Appendix C. While & is not suggested by Equation (2), it helps to control the impact of the regularisation in practice, Equation (5) then optimises a tradeoff between the empirical risk and the regularisation term E > Aml S. d(ttw, lw,)) ).
Online algorithm. Online algorithms output, each time step E {1, m }, new hypothesis hw. From Equation (4), particularised to a sequence of Dirac distributions (localised in hw. .wwx). we design novel online AAC-Bayesian algorithm with a Wasserstein regulariser:
Vi 2 1, h2 E argmin (liw, 2,) + d /ww.)) EW
s.t. d (Iw liw:-)) SI.
(6)
According to Theorem 4, such an algorithm aims to bound the population cumulative classification
loss C₁ = Σm= (kw,,,, 2.) Fi- Note that we added the constraint d (hw: lw...) S 1
compared Equation (4). This constraint ensures that the new hypothesis hw; is not too far from hw.-, (in the sense of the distance || I12).. Note that the constrained optimisation problem in Equation (6) can be rewritten in an unconstrained form (see [B4)) thanks to barrier B-)) defined by B(a) = 0 if a S 0 and B(a)- = +oo otherwise; we have
Vi 1, h4g E argmin E(hw, 2,) + (hw: lw: .) + B(d (lowr lww .) 1).
EW
When solving the problem in Equation (7) is not feasible, we approximate it with log barrier of [KDY+22] (suitable in a stochastic gradient setting); given a parameter >> 0, the log barrier extension is defined by B(a)= = - ln( if a S - - and B(a) = ta - 1 [I(})) + otherwise. We present in Appendix C Algorithm 2 that aims to (approximately) solve Equation (7). To do so, for each new example (x, y.). the algorithm runs several gradient descent steps to optimise Equation (7).
4.2 Experimental framework
In this part, we assimilate the predictor space H to the parameter space Rd. Thus, the distance d is the Fuclidean distance between two parameters: d (hw, htw) ||w- w/lla. This implies that the Lipschitzness of l has to be taken w.z. w instead of hw-
Models. We consider that the models are either linear neural networks (NN), Linear models are defined by (x) = Wx+ 6, where W E gDix is the weight matrix, & E RD' is the bias, and w = vec((W,6)) its vectorisation; the vector w with the zero vector. Thanks to the definition of X, we know from Lemma 8 (and the composition of Lipschitz functions) that the loss is -2ns-isschitz w.e.t w. For neural networks, we consider fully connected ReLU neural networks with L hidden layers and D nodes, where the leaky ReI.U activation function ReI.U R TRD" applies elementwise x + max(x; (x. 0. More precisely, the network is defined by (x) = Wh4( h- (x)) + where W E RD b E IR >l, Each layer h (x) = (W has a weight matrix W; E DxD and bias b E RDD except for i = where we have W, E Dxd The weights w are also the vectorisation w vec( (W, WL...., W1, b. b...... 61 }). We have precised in Lemma 9 that our loss is Lipschitz w.r.t. the weights w. We initialise the network similarly to [DR17] by sampling the weights from a Gaussian distribution with zero mean and a standard deviation of a 0.04; the weights are further clipped between -20 and +2a. Moreover, the values in the biases b,,.. , by are set to 0.1, while the values for b are set to 0. In the following, we consider D 600 and L 2; more experiments are considered in the appendix.
Optimisation. To perform the gradient steps, we use the COCOB--ackprop Backprop optimiser [OT17] (with parameter a= = 10000). 2 This optimiser is flexible as the learning rate is adaptative and, thus, does
'Th parameter a in COCOB-Backprop Backprop can be seen as initial learning rate; see [OT17].
8

---

not require hyperparameter tuning. For Algorithm 1, which solves Equation (5), we fix a batch size of 100, i.e. [4] 100, and the number of epochs T and T' are fixed to perform at least 20000 iterations. Regarding Algorithm 2, which solves Equation (7), we set /. = 100 for the log barrier, which is enough to constrain the weights and the number of iterations to T = 10.
Datasets. We study the performance of Algorithms 1 and 2 on UCI datasets [DG17] along with MNIST [LeC98] and FashionMNIIT [XRV17]. We also split all the data (from the original train- ing/test set) in two halves; the first part of the data serves in the algorithm (and is considered as a training set), while the second part used to approximate the population risks Ry (h) and e₂ (and considered as testing set).
4.3 Results
We present in Table the performance of Algorithms 1 and compared to the Empirical Risk Minimisation (ERM) and the Online Gradient Descent (OGD) with the COCOB- COCOB-Backprop optimiser. Tables la and le present the results of Algorithm 1 for the i...d. setting on linear and neural networks respectively, while Tables lb and Id present the results of Algorithm 2 for the online case.
Analysis of the results. In batch learning, we note that the regularisation term brings generalisation improvements compared to the empirical risk minimisation. Indeed, our batch algorithm (A (Algorithm 1) has lower population risk R,, (h) on 11 datasets for the linear models and datasets for the neural networks. In particular, notice that NNs obtained from Algorithm are more efficient than the ones obtained from ERM on MNIST and FASHIONMIIST, which are the more challenging datasets. This suggests that the regularisation term helps to generalise well. For the online case, the performance of the linear models obtained from our algorithm (Algorithm 2) and by OGD are comparable: we have a tighter population classification risk Ri, (h) on 5 datasets over 13. However, notice that the risk difference less than 0.05 on datasets. The advantage of Algorithm is more pronounced for neural networks: we improve the performance in all datasets except ADULT and SENSORL Hence, this confirms that optimising the regularised loss f(w 2,) + ||W -w: || brings a good advantage compared to the loss f(hw: 2;) only. A possible explanation would be that OGD suffers from underfitting (with high empirical risk (,,) while we are able to control overfitting through regularisation term. Indeed, only one gradient descent step is done for each new datum (x:, Vs),
which might not be sufficient to decrease the loss. Instead, our method solves the problem associated with Equation (7) and constrains the descent with the norm |w w,-1ll-
Conclusion and Perspectives
We derived novel generalisation bounds based the Wasserstein distance, both for batch and online learning, allowing for the use of deterministic hypotheses through PAC-Bayes. We derived new learning algorithms which are inspired by the bounds, with remarkable empirical performance on a number of datasets: we hope our work can pave the way to promising future developments (both theoretical and practical) of generalisation bounds based on the Wasserstein distance. Given the mostly theoretical nature of our work, we do not foresee an immediate negative societal impact, although we hope better theoretical understanding of generalisation will ultimately benefit practitioners of machine learning algorithms and encourage virtuous initiatives.
6
Acknowledgements
We warmly thank the reviewers who provided insightful comments and suggestions which greatly helped us improve our manuscript. P.V. and U.S. are partially supported by the French government under the management of Agence Nationale de la Recherche as part of the "Investissements d' l'avenni" program, reference ANR-19-P3IA 19-A3A1-0000 (PRAIRIE 3IA Institute). U.S. is also partially supported by the European Research Council Starting Grant DYNASTY 101039676. B.G. acknowledges partial support by the U.S. Army Research Laboratory and the U.S. Army Research Office, and by the U.K. Ministry of Defence and the U.K. Engineering and Physical Sciences Research Council (EPSRC) under grant number EP/RO1 361 6/1. B.G. acknowledges partial support from the French National Agency for Research, grants ANR- 18 18-CE40-0016- 1011 and 1NN--8-CE23--0

---

Table Performance of Algorithmss and 2 compared respectively to ERM and OGD on different datasets on linear and neural network models. For the i.i.d. setting, we consider & 1/mm and with K 0.2ym. For each method, we plot the empirical risk Rs(h) or Es with its associated test risk R (h) or Ep. The risk in bold corresponds to the lowest one among the ones considered. For the online case, the two population risks are underlined when the absolute difference lower than 0.05.
1/m and
(a) Linear model batch learning
(b) Lincar model online learning
Alg.
(
Alg.
ERM
Alg. 2
OGD
Vm
Dataset
(t((k) (A)
(t)(h)
(N)
(ts(h) (k)
C3 e,
C3 Cy-
ADULT
.165
.166
.165
.167
.166
.167
.230 .236
.248 .248
FASHIONMNIST
.128
.151
.126
.148
.139
.153
.223 .282
.540 .548
LETTER
.255
.297
.287
.296
.287
.297
.919 .955
916 .926
MNIST
.200
.266
.066
.092
.065
.091
.284 .310
.378 .397
MUSHROOMS
.001
.001
.001
.001
.001
.001
.288 .22
.082 .087
NURSERY
.766
.773
.760
.773
.794
.807
.794 .807
.789 .805
PENDIGITS
.049
.059
.050
.061
.052
.064
.342 .84
.899 .600
PHISHING
.063
.067
.065
.069
.064
.067
.226 .242
.226 .220
SATIMAGE
.144
.200
.138
.011
.148
.209
.669 .988
.655 .888
SEGMENTATION
.057
.216
.164
.386
.087
.232
.749 .003
.738 .893
SENSORLESS
.129
.129
.131
.131
.134
.136
.906 .910
.25 .830
TICTACTOE
.388
.299
.013
.021
.28
.238
.443 .468
.390 .303
YEAST
.527
.497
.524
.504
.700
.427
.699 .713
.667 .708
(c) NN model batch learning
(d) model
online learning
Alg. (
Alg.
Vm
ERM
Alg. 2
OGD e,
Dataset
Rs(hh) (h)
Rt(h))
(h)
(b)
pt,, (b)
Ess
c,
css
ADULT
.164
164
.166
.165
.165
.163
.241 .254
.248 .248
FASHIONMNIST
.159
.163
.156
.160
.163
.167
.096 .327
.397 .446
LETTER
259
.272
.250
.260
.258
.270
.829 .945
.958 .963
MNIST
.112
.120
.084
.094
.119
.127
.092 .265
.470 .521
MUSHROOMS
.000
.000
.000
.000
.000
.000
.022
.202 .217
NURSERY
.706
.719
.706
.719
.706
.719
.800 .805
.793 .806
PENDIGITS
.009
.023
.021
.032
.009
.022
.323 .537
.871 .879
PHISHING
.042
.050
.039
.054
.046
.055
.164 .222
.331 .318
SATIMAGE
.132
.184
.149
.172
.141
.189
.401 .763
.626 .857
SEGMENTATION
.145
.250
.189
.373
.174
.389
.619 .857
.739 .913
SENSORLESS
.076
.079
.077
.079
.075
.078
.899 .900
.622 .633
TICTACTOE
.392
.301
.000
.038
.000
.023
.388 .309
.397 .309
YEAST
.679
.666
.487
.478
.644
.682
.662 .720
.702 .720
References
[ACB17] Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein Generative Adver- sarial Networks. In International Conference Machine Learning (ICML), 2017.
[AEMM22] Ron Amit, Baruch Epstein, Shay Moran, and Ron Meir. Integral Probability Met- rics PAC-Bayes Bounds. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
[AG18] Pierre Alquier and Benjamin Guedj. Simpler PAC-Bayesian bounds for hostile data. Machine Learning, 107(5), 2018.
[AM18] Ron Amit and Ron Meir. Meta-Learning by Adjusting Priors Based on Extended PAC-Bayes Theory. In International Conference on Machine Learning (ICML), 2018.
10

---

[ARC16] Pierre Alquier, James Ridgway, and Nicolas Chopin. On the properties of variational approximations of Gibbs posteriors. Journal of Machine Learning Research, 2016.
[BG21] Felix Biggs and Benjamin Guedj. Differentiable PAC-Bayes Objectives with Partially Aggregated Neural Networks. Entropy, 23(10), 2021.
[BG22a] Felix Biggs and Benjamin Guedj. Non-Vacuour Generalisation Bounds for Shallow Neural Networks. In International Conference on Machine Learning (ICML), 2022.
[BG22b] Felix Biggs and Benjamin Guedj. On Margins and Derandomisation in PAC-Bayes. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2022.
[BG23] Felix Biggs and Benjamin Guedj. Tighter PAC-Bayes Generalisation Bounds by Leveraging Example Difficulty. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2023.
[BM01] Peter Bartlett and Shahar Mendelson. Rademacher and Gaussian Complexities: Risk Bounds and Structural Results. Conference on Computational Learning Theory (COI.T), 2001.
[BM02] Peter Bartlett and Shahar Mendelson. Rademacher and Gaussian Complexities: Risk Bounds and Structural Results. Journal of Machine Learning Research, 2002.
[BT08] Bernard Bercu and Abderrahmen Touati. Exponential inequalities for self normalzedd martingales with applications. The Annals of Applied Probability, 2008.
[B004] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge University Press, 2004.
[BZG22] Felix Biggs, Valentina Zantedeschi, and Benjamin Guedj. On Margins and Generali- sation for Voting Classifiers. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
[Cat07] Olivier Catoni. PAC-Bayesian supervised classification: the thermodynamics of statistical learning. Institute of Mathematical Statistics, 2007.
[Cat16] Olivier Catoni. PAC-Bayesian bounds for the Gram matrix and least squares regression with a random design. arXiv, abs/1603.0522
2016.
[CD Alexander Camuto, George Deligiannidis, Murat A. Erdogdu, Mert Gürbüzbalaban, Umut Şimsekli, and Lingjiong Zhu. Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms. In Advances in Neural Information Processing Systems (NeurIPS), 2021
[CG17] Olivier Catoni and Ilrii Giulini. Dimension-free PAC-Bayesian bounds for matrices, vectors, and linear least squares regression. arXiv, abs/1712.00744 2017.
[CL21] Andrew Chee and Sébastien Loustau. Learning with BOT Bregman and Optimal Transport divergences. 2021.
[CSDG22] Badr-Eddine Aidérief-Abdellatee Yuyang Shi, Arnaud Doucet, and Benjamin Guedj. On PPC-Baycsial reconstruction guarantees for VAEs. In International Conference Artificial Intelligence and Statistics (AISTATS), 2022.
[Csi75] Imre Csiszár. I-Divergence Geometry of Probability Distributions and Minimization Problems. The Annals of Probability, 3(1), 1975.
[CWR23] Ben Chugg, Hongjian Wang, and Aaditya Ramdas. A unified recipe for deriving (time-uniform) PAC-Bayes bounds. arXiv, abs/2302.033211, 2023.
[DCL+21] Nan Ding, Chen, Tomer Levinboim, Sebastian Goodman, and Radu Soricut. Bridg- ing the Gap Between Practice and PAC-Bayes Theory in Few-Shot Meta-Learning. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[DG17] Dheeru Dua and Casey Graff. UCI Machine Learning Repository, 2017.
[DR17] Gintare Karolina Dziugaite and Daniel Roy. Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data. In Conference on Uncertainty in Artificial Intelligence (UAT), 2017.
[DV76] Monroe David Donsker and Srinivasa Varadhan. Asymptotic evaluation of certain Markov process expectations for large time-Ill. Communications on Pure and Applied Mathematics, 29(4), 1976.

---

[FM21] Alec Farid and Anirudha Majumdar. Generalization Bounds for Meta- Mleta-Learning via PAC-Bayes and Uniform Stability. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[FPI0] Mahdi Milani Fard and Joelle Pineau. PAC-Bayesian Model Selection for Rein- forcement Learning. In Advances in Neural Information Processing Systems (NIPS), 2010.
[FRKP22] Hamish Flynn, David Reeb, Melih Kandemir, and Jan Peters. PAC- Bayyeia lifelong learning for multi-armed bandits. Data Mining and Knowledge Discovery, 2022.
[GBTS21] Borja Rodríguez Gálvez, Germán Bassi, Ragnar Thobaben, and Mikael Skoglund. Tighter Expected Generalization Error Bounds via Wasserstein Distance. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[GMGA17] Anil Goyal, Emilie Morvant, Pascal Germain, and Massih- Amini. PAC-Bayesian Analysis for a Two-Step Hierarchical Multiview Learning Approach. In Machine Learning and Knowledge Discovery Databases European Conference (ECML- PKDD), 2017.
[Gue19] Benjamin Guedj. A Primer on PAC-Bayesian Learning. arXiv,
2019.
[HG22] Maxime Haddouche and Benjamin Guedj. Online PAC-Bayes Learning. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
[HG23a] Maxime Haddouche and Benjamin Guedj. PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingales. Transactions on Machine Learning Research, 2023.
[HG23b] Maxime Haddouche and Benjamin Guedj. Wasserstein PAC-Bayes Learning: A Bridge Between Generalisation and Optimisation. arXiv, abss2300400704, 2023,
[HGRS21] Maxime Haddouche, Benjamin Guedj, Omar Rivasplata, and John Shawe-Taylor. PAC-Bayes Unleashed: Generalisation Bounds with Unbounded Losses. Entropy, 23(10), 2021.
[JJKO23] Kyoungseok Jang, Stwan--uug Jun, Ilja Kuzborskij. and Francesco Orabona. Tighter BAC-Bayes Bounds Through Coin-Betting. In Conference on Learning Theory (COLT), 2023.
[Kan60] Leonid Vitalievitch Kantorovitch. Mathematical Methods of Organizing and Planning Production. Management Science, 1960.
[2D Hoel Kervadec, Jose Dolz, Jing Yuan, Christian Desrosiers, Eric Granger, and Is- mail Ben Ayed. Constrained deep networks: Lagrangian optimization via log-barrier extensions. In European Signal Processing Conference (EUSIPCO), 2022.
[KP00] Vladimir Koltchinskii and Dmitriy Panchenko. Rademacher processes and bounding the risk of function learning. In High dimensional probability 2000.
[LeC98] Yann LeCun. The MNIST database of handwritten digits, 1998.
[LFK*t22] Sanae Lotfi, Mare Finzi, Sanyam Kapoor, Andres Potapczynski, Micah Goldblum, and Andrew Wilson. PAC-Bayes Compression Bounds So Tight That They Can Explain Generalization. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
[LGGL19] Gaël Letarte, Pascal Germain, Benjamin Guedj, and François Laviolette, Dichotomize and Generalize: PAC-Bayesian Binary Activated Deep Neural Networks. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[LN22] Gábor Lugosi and Gergely Neu. Generalization Bounds via Convex Analysis. In Conference on Learning Theory (COLT), 2022.
[LWHZ19] Shiyin Lu, Guanghui Wang, Yao Hu, and Lijun Zhang, Optimal Algorithms for Lipschitz Bandits with Heavy-tailed Rewards. International Conference on Machine Learning (ICML), 2019.
[LZI1] Keqin Liu and Qing Zhao. Multi-Armed Bandit Problems with Heavy Tail Reward Distributions. Allerton Conference on Communication, Control, and Computing, 2011.
12

---

[Mau04] Andreas Maurer. A note on the PAC-Bayesian theorem. arXiv, cs/0c 1090, 2004.
[MGG19] Zakaria Mhammedi, Peter Grünwald, and Benjamin Guedj. PAC-Bayes Un-Expected Bernstein Inequality. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[MGW20] Zakaria Mhammedi, Benjamin Guedj, and Robert Williamson. PAC-Bayesian Bound for the Conditional Value at Risk. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[Mon81] Gaspard Monge. Mémoire sur la théorie des déblais et des remblais. Histoire de l'Académie Royale des Sciences de Paris, 1781.
[Mû97] Alfred Müller. Integral Probability Metries and Their Generating Classes of Functions. Advances in Applied Probability, 29(2), 1997.
[NGG20] Kento Nozawa, Pascal Germain, and Benjamin Guedj. PAC-Baycsian Contrastive Unsupervised Representation Learning. In Conference Uncertainty in Artificial Intelligence (UAI), 2020.
[OH21] Yuki Ohnishi and Jean Honorio. Novel Change of Measure Incqualities with Ap- plications to PAC-Bayesial Bounds and Monte Carlo Estimation. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2021.
[OT17] Francesco Orabona and Tatiana Tommasi. Training Deep Networks without Learning Rates Through Coin Betting. In Advances in Neural Information Processing Systems (NIPS), 2017.
[PC19] Gabriel Peyré and Marco Cuturi. Computational Optimal Transport. Foundations and Trends in Machine Learning, 11(6-6), 2019.
[P0 Maria Perez-Ortiz, Omar Rivasplata, Emilio Parrado- Hernaddzz Benjamin Guedj, and John Shawe-Taylor. Progress in Self-Certified Neural Networks. NeurIPS 2021 Workshop on Bayesian Deep Learning, 2021.
[PRSS21] María Pérez-Ortiz, Omar Rivasplata, John Shawe-Taylor, and Csaba Szepesvári. Tighter risk certificates for neural networks. Journal of Machine Learning Research, 22, 2021.
[PWG22] Antoine Seard-Weibell and Benjamin Guedj. On change of measure inequalities for f-divergences. arXiv, htss/202.00566. 2022.
[RACA23] Charles Riou, Pierre Alquier, and Badr-Eddine Chérief-Abdellatif. Bayes meets Bernstein at the Meta Level: an Analysis of Fast Rates in Meta-Learning with PAC- Bayes. arXiv, abs/2302.117099 2023.
[RFJK21] Jonas Rothfuss, Vincent Fortuin, Martin Josifoski, and Andreas Krause. PACOH: Bayes-optimal meta-learning with PAC-guarantees. In International Conference on Machine Learning (ICML), 2021.
[RJFK22] Jonas Rothfuss, Martin Josifoski, Vincent Fortuin, and Andreas Krause. PAC-Bayesian Meta-Learning: From Theory to Practice. arXiv, abs/221 1.07206, 2022.
[RZ20] Daniel Russo and James Zou. How Much Does Your Data Exploration Overfit? Controlling Bias via Information Usage. IEEE Transactions on Information Theory, 66(1), 2020.
[SAC23] Otmane Sakhi, Pierre Alquier, and Nicolas Chopin. PAC-Bayesian Offline Contextual Bandits With Guarantees. In International Conference Machine Learning (ICML), 2023.
[SLCB+12 12] Yevgeny Seldin, François Laviolette, Nicolò Cesa-Bianchi, John Shawe-Taylor and Peter Auer. PAC-Bayesian Inequalities for Martingales. IEEE Transactions Information Theory, 58(12), 2012.
[Sli1]] Aleksandrs Slivkins. Introduction to Multi-Armed Bandits. Foundations and Trends in Machine Learning, 2019.
[SLST+11] Yevgeny Seldin, François Laviolette, John Shawe- Taylor, Jan Peters, and Peter Auer. PAC-Bayesian Analysis of Martingales and Multiarmed Bandits. arXiv, Abs/1105.241e 2011.
13

---

[VC68] Vladimir Vapnik and Alexey Chervonenkis, On the uniform convergence of relative frequencies of events their probabilities. In Doklady Akademii Nauk USSR, 1968.
[VC74] Vladimir Vapnik and Alexey Chervonenkis. Theory of pattern recognition, 1974.
[Vi109] Cédric Villani. Optimal transport: old and new. Number 338 in Grundlehren der mathematischen Wissenschaften, Springer, 2009.
[WDFC19] Hao Wang, Mario Diaz, José Cândido Silveira Santos Filho, and Flávio Calmon. An information-Theete Theoretic View of Generalization via Wasserstein Distance. In IEEE International Symposium on Information Theory (ISIT), 2019.
[XR17] Aolin Xu and Maxim Raginsky. Information-theoretie analysis of generalization capability of learning algorithms. In Advances in Neural Information Processing Systems (NeurIPS). 2017.
[RV17]] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: Novel Image
Dataset for Benchmarking Machine Learning Algorithms, 2017.
[Zin03] Martin Zinkevich. Online Convex Programming and Generalized Infinitesimal Gradi- ent Ascent. In International Conference on Machine Learning (ICML), 2003.
[ZLT18] Jingwei Zhang, Tongliang Liu, and Dacheng Tao. An Optimal Transport View on Generalization. arXiv, abs/1811.032711 2018.
[ZS21] Vincent Zhuang and Yanan Sui. No-Regret Reinforcement Learning with Heavy- Tailed Rewards. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2021.
[ZVM+21] Valentina Zantedeschi, Paul Viallard, Emilie Morvant, Rémi Emonet, Amaury Habrard, Pascal Germain, and Benjamin Guedj. Learning Stochastic Majority Votes by Minimizing PAC-Bayes Generalization Bound. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
14

---

The supplementary material is organized as follows:
(i) We provide more discussion about Theorems and in Appendix A;
(ii) The proofs of Theorems
are presented in Appendix B;
(iii) We present in Appendix C additional information about the experiments.
A Additional insights on Section 3.1
In Appendix A.I, we provide additional discussion about Theorem while Appendix A.2 discuss about the convergence rates for Theorem 2.
A.1
Supplementary discussion about Theorem
(HG23b, Corollary 10] proposed PAC-Bayes bounds with Wasserstein distances Euclidean predictor space with Gaussian prior and posteriors. The bounds have an explicit convergence rate of O( ((VaW1(o.))a where the predictor space is Euclidean with dimension d. While our bound does propose such explicit convergence rate, it allows us derive learning algorithms as described in Section 4. A broader discussion about the role of K detailed in Theorem 2. Furthermore, our bound holds for any Polish predictor space and does require Gaussian distributions. Furthermore. our result exploits data-dependent priors and deals with the dimension only through the Wasserstein distance, which can attenuate the impact of the dimension.
A.2 Convergence rates for Theorem 2
In this section, we discuss more deeply the values K Theorem This implies a tradeoff between the number of sets K and the cardinal of each S.. The tightness of the bound depends highly on the sets ,
Full batch setting K=1. When S = S with K = 1, the bound of Theorem 2 becomes, with probability 8, for any p M(H)
In
E Amp
R. (h) (h) Rs(hi] 2LW (p, T) +2
m
where πi is data-free. This bound can be seen as the high-probability (PAC-Bayesian) version of the expected bound of [WDFC19]. Furthermore, in this setting, we are able, through our proof technique, to recover explicit convergence rate similar to the one of [AEMM22, Theorem 12]. It stated below.
Corollary 5. For any distribution μ for any finite hypothesis space H equipped with distance for any L-Lipschitz loss function & x Z + [0, 1], for any 8 E (0, 1]. we have, with probability 1 - 8 over the sample S. for any P M(H)::
W(p, TT) + +2 In (1)11//a
In (2/8)
E
(b) - Rs(()) s S
hoep
m
where N is data-free prior.
Proof. We exploit [AEMM22, Equation 35] state that with probability at least 6/2, for any (h, E H2:
1/12
2
m (K/,2) - el (h, 2:)] (e(',2) -(hh
S L
d (h, M/)-
zrope
So, with high probability, we can exploit the Kantorovich-Rubinee duality with this new Lipschitz constant: with probability at least 1 8/2:
1 2
E happ
(h) - Rs(h)) S
x)
E
Σ R1) - e(h. zi)
hoot
15

---

To conclude, we control the quantity on the right-hand side the same way as in Theorem 1 and Theorem 2. We then have, with probability least 5/2, for loss function in [0, 1]:
m Σ Ry(h)
1
e(h, 2,) s 2
In K
m
Taking the union bound concludes the proof.
Mini-batch setting K /m. When tradeoff is desired between the quantity of data want to infuse in our priors and an explicit convergence rate, a meaningful candidate when K mm. Theorem 2's bound becomes, in this particular case:
E hrup
(h) - Rs((
&
m mm Σ
2L
W(p, m.) + 2
V In
d vm
(8)
Towards online learning: K = m. When K the sets S; contain only one example. More precisely, we have for all i E [1....m)) the set S {z). this case, the bound becomes:
E houp
(1) - (
2L W(e + 2 In 1n <
m
This bound vacuous since the last term incompressible, hence the need for new technique detailed in Section 3.2 to deal with it.
B Proofs
The proof of Theorem is presented in Appendix B.1. Appendices B.2 and B.3 introduce two proofs of Theorem 2. Theorem 3's proof is presented in Appendix B.4. Appendix B.5 provides the proof of Theorem 3.
B.1 Proof of Theorem 1
Theorem 1. We assume the loss E to be L-Lipschitz. Then, for any 5 E (0. for any sequence of positive scalar ().,,E(),....K) with probability at least 1 over the sample the following holds for the distributions S. == (T(S..) .) and for any p M(H):
E hm<p
(h) - Rs(h))
L W(p, 1 K
In
X
(Mss)(() + Visu((hi)
+
E hwFLs
where
ni,S does not depend on S.. Also, for any i, i,15,,, we have Vis,(h)
ExEs, (((h,z) R2) and Visi(h)= Es, [M)s
Proof. For the sake of readability, we identify, for any i, क. and Ti.S.
Step 1: Exploit the Kantorovich duality [Vi109, Remark 6.5]. First of all, note that for L-Lipschitz loss function & H. x Z + [0, 11, we have
( [S)]Rp((/)) Σ ((11.2) SES.
[|. [s))
Σ E(12,2) 2) ZES,
< L (9)
16

---

Indeed, we can deduce Equation (9) from Jensen inequality, the triangle inequality, and by definition that we have
(s)R)((11)
(((
(15.)R(((22)
E(hh2,?) 2)
ZE8:
ZES:
Σ Rm((1)-
Σ ((b1,2))
Σ
Rx((2)
Σ ((h2, z))
*ES;
zES:
E
[(((h12z) - E((h2,2)) + ((((22 ((h1122)
x d'mup
2
S
E
2Td(h1,
x N
ZES:
= S Ld(hi, h2)
We are now able to upper-bound Enup (R) Rs(h)]. Indeed, we have
E hmpp
(b) Rs(h)]
E
(h)
Σ
E((h,2 2)
m
hrup
ZES:
K L
K
W(p, m.)
+
E
(,)
(h) - Σ ((h,z)
(10)
howm,
xES;
where the inequality comes from the Sinioooovic-RRbiisttenn duality theorem.
Step 2: Define adapted supermartingale. For any 1 1 K, we fix A > 0 and we provide an arbitrary order to the elements of S, == [Zi.1. TM Zr.1s.1.. Then we define for any h:
|8.1
(h) == (b) Σ E(h,z) Σ Rn) E(h, Z1,)).
xES.
j=1
Remark that, because our data are i..dd, (Mis.) is martingale. We then exploit the technique [HG23a] to define supermartingale. More precisely, we exploit a result from [BT08] cited in Lemma 1.3 of [HG23a] coupled with Lemma 2.2 of [HG23a] to ensure that the process
Texp (A.Mss.(h))
X 2 (Mss,(0)) + visu((t))]
SMis.1 == E
huTe
is a supermartingale, where (is E|S (l(h, z,,r) - (h))) and Vis, (h) = Es, [Misa((t]]
Step 3. Combine steps 1 and 2. Rubinstein duality.
We restart from Equation (10) to exploit again the Kantorovich-
K
R (h) keup
E
Rs)
1
E
(h) -
Σ e(h, 2)
houp
1=1
ZES,
K
2/S: I
K
W(p.T)) me) + Σ
di E
Σ #ES:
E(h, 2)
m
md:
hovi
1=1
2/8.LL W(p.
1
+
E
[AAMss
m
mR
h~m;
1=1
2|5
K
W(p. me)
+ Σ mX
In (SMs.) )
m
K
(Mss (h) + Visa (1))
E
2
17

---

The last line holds thanks to Jensen's 's inequality. We now apply Ville's inequality (see e.g., Section 1.2 [HG23a]). We have for any
(SS. 1,542,,,MMA, SMS.
1 8 2 21
P Stmpp (:1
-
Applying an union bound and authorising X; to be function of |.S:] (thus the inequality does not hold for all [S.] simultaneously) finally gives with probability least 1 - 6, for all p E M(H)
L|S W(p, T.
In
K A
A
R (h) (s( hmp
E2
E 2m howm,
[vs((h) (1)
m
B.2 Proof of Theorem 2
Theorem 2. We assume our loss E to be non-negative and L-Lipschitz. We also assume that, for any 1 1 i K, for any datasetS, we have Bn--n((_S).2mp [E(h, 2)²] I 1 (bounded order moments for priors). Then, for any 8 E (0, 1}, with probability at least 1 over the sample S, the following holds for the distributions Ti.S TT(S..) and for any E M(H):
E hrop
(1) (R)(1)-Rs())))
Rs) -
2
+
K
2|S, In
m²
where TiSS does not depend on S..
Proof. For the sake of readability, we identify, for any i, and Ti.s-
Step 1: Exploit the Kantorovich duality [Vi109, Remark 6.5]. L-Lipschitz loss function 8: H x 2 + [0, 1], we have
First of all, note that for
( (IsiRACh))
Σ E(2, 2)
(11) Indeed, we can deduce Equation (11) from Jensen inequality, the triangle inequality, and by definition that we have
e(1 nES.
[S. (Rn((2)
= Ld h2).
#ES:
Σ E(h2,22) )
((1)
Σ ((h1.z)
ZES,
nES:
Σ Rn(h))) Σ E(11,
Σ Ru((2) Σ ((b2,2)
2ES.
RES.
ZES,
Σ E [E((11,)) - E(h2, 2')l + 1)(((())))-((itt)
- E(h1,,
=ES,
< E 2Ld(h1,
ZES:
2 Ld ha).
We are now able to upper-bound Expp (R) Rs(h)). Indeed, we have
E hwep
(1)
Rs(l)]
Σ E(h, 2)
m
kmp
ZES,
K
L
W(p, TT)
E howe
(h)
- Σ E(h,z)
(12)
m
zES;
where the inequality comes from the Cantorovich-Rubinstee duality theorem.
18

---

Step 2: Define an adapted supermartingale. For any 1 sis K, we fix A > 0 and we provide an arbitrary order to the elements of S == {Zi,).-. 211ss. /- Then we define for any h:
|..1
(h) = (,))
Σ
e(h,2) Σ (h) j=1
E(h, Zi.)).
xES;
Remark that, because our data are i..d.. (Mss.))ss.12 is martingale. We then exploit the technique [CWR23] to define supermartingale. More precisely, we exploit [CWR23, Lemma A.2 and Lemma B.1] to ensure that the process
(,)) - A7 2 Lis: (1)) (m)]
SMS. == E
exp
a supermartingale, where, because our data are iidd, L1s,(1)) Es
| 18
E(h, 2o.
|S| (0-m][((h, =)²].
Step 3. Combine steps and 2. Rubinstein duality again.
We restart from Equation (12) to exploit the Kantorovich-
K =
E hwup
(h) - [s)
E hmp
(h)
- Σ
e(h,
z)
1=1
xES;
K
2|S, L
K
W(p, me)
+
Aj E
Σ
Eeh,, 2)
m
md
hovs
i=1
ZES.
2|S:|L
K
W W(p, me)
Σ
E
[sMis
m
md
2|8:|L
K
W(p, mi)
+ Σ md;
In (SMss
m
K
Lis.((1))
+
The last line holds thanks to Jensen's 's inequality. We now apply Ville's inequality (see e.g., section 1.2 [HG23a]]. We have for any
(1SS/) 1, S 8
2 1 6.
S 15g1
Applying union bound and authorising X; be function of [.Sy] (thus the inequality does not hold for all (. simultaneously) finally gives with probability at least 1 - 8, for all E M(H)
215.1L W(p. TT)
In
K Am
A
E Rh, (..()))R((h))) hmp
E [L]S,[(M]] Awws
m
2m
Finally, using the assumption Ensx, Ezap 1[(h, 2) < gives, with probability at least 1 - 8, for all p E M(H):
K 2 L W(p. mT) +
K In
E hepp
(h) - Rs(h)) <
X,m
2m
Taking for each i, A;
2 [S,]
concludes the proof.
B.3 Alternative proof of Theorem
We state here slightly tighter version of Theorem 2 for bounded losses, which relies an application of McDiarmid's inequality instead of supermartingale techniques. This is useful for the numerical evaluations of our bound.
19

---

Theorem 6. We assume our loss E to be in [0, 1] and L L-Lipschitz Then, for any 8 E (0, 1]. with probability least 1 over the sample S, the following holds for the distributions T3,S = (S.).) and for any p E M(H))
2|S, L Σ m
S In K 2m2
E houp
-
((D,
8
where ny does not depend on Sy.
Proof. For the sake of readability, we identify, for any i, n. and TT,8.
First of all, note that for T--Lipschitz loss function e: H 2 [0, 1]. we have
( (k)) Σ ((bb,,z)
[1s (R,,))
Σ E(h2, z) =ES;
s Ld(, h2).
(13)
zES;
Indeed, we can deduce Equation (13) from Jensen's inequality, the triangle inequality, and by definition that we have
(s1R)((11)-
Σ
E(h1, z)
Ee(he,
Σ Elbg, 2)
2ESt
zESL
Σ Rn(hi)- Σ ((11,22)
Σ Rm(22) Σ ((h2,2)
xES.
KES.
ZES.
E z'mu
[((()),) - E(h2, 2¹)l + (e(h2, 2) - E(h1, 2)]
2E8,
< E
2Ld(h1.
#ES;
(Ld(h,, h2)
We are now able to upper-bound BAmp! - RR(())]. Indeed, we have
E heep
(h) - Rs(h))
[S,(Rr(h))
Σ E(h, z)
El(h,
m
hrap
xES.
L. W(p, m4)
E KOT,
(h) - Σ ((h,2) (14) ZES,
m
where the inequality comes from the Kantorovich-Rubinsten duality theorem. Let f(S;) = En 1 (h) - Eves, ((h, z:)]. the function has the bounded difference inequality, i.e., for two datasets S; and S that differs from one example (the k-th example, without loss of general- ity), have
(f(S)) f(S))
(s)
Σ E(h,z) z)
E h~w;
1
()),
Σ E(h,z')
Amwa,, m
m
zES:
x'E
1
1
|8 (h)
E(h,2)
(k)
E(h,z')
howT,
m
m
m
m
z'ES
E homm,
1
Σ
m ((h,2')
E(h, 2)
m
x'ES'
ZES,
E hooTs
E(h, 2%)
e(h, 2b:)
m
m
1
20

---

Hence, from Mediarmid's inequality, we have with probability at least 1
k over S ~ pm
E
(
Σ
((h,z)
howx; m
xES;
|S | In K 2m2
E
(A)
Σ
E(h, z))
+
Smpth howte
zES:
E
1
|S (h)
- E(h, z)
S:l In K 2m2
Spm mn 18 SempulBel Bell Aema,; m
xES:
Si| In % 2m2
E
E
[s:
E
E(h, z)
Spmupm 18,1 hower
Semp
ZES:
1 (.)
( +
S In K
E
Sp-pm- 11pp--181 18,1 AEMTT m72
2m
St In
2m2
From the union bound, we have with probability at least 1 - 8 over S ~ nm" for any P E M(H),
2|S W ((p TT.)
S In K 2m
E
8
hma
m
which is the claimed result.
We are now able to give a corollary of Theorem 6.
Corollary 7. We assume our loss é be in [0, 1] and L-Lipschitz. Then, for any d E (0, 1}. with probability at least 1 - 8 over the sample S, the following holds for the hypotheses hiss E H associated with the Dirac distributions S and for any h E H:
218 h(,
K
S In 2m²
(h) < (h) + Σ
m
Such a bound was impossible to obtain from the PAC-Bayesian bounds based on KL diver- gence. Indeed, the KL divergence is infinite for two distributions with disjoint supports. Hence, the PAC-Bayesian framework based on the Wasserstein distance allows us to provide uniform- convergence bounds from a proof technique different from the ones based on the Rademacher complexity [KP00, BM01, BM02] or the VC-dimension [VC68, VC74]. In Section 4, we provide an algorithm minimising such bound.
B.4 Proof of Theorem 3
Theorem 3. We assume our loss to be L-Lipschitz. Then, for any 8 (0, 1], with probability at least 1 - 8 over the sample S, the following holds for the distributions TiSS == nz(S..) and for any sequence (pi)i=1... "
Σ
E i= hempp
B(e(hi, Fi-1] ((hi,2i)
2L Σ
W W(pi, R5,s)
In(1/8)
Vi(hs, 2.) + v.(ha)
2
h hywo
X
where for all i, Vi(h,, z;) (e(hs, 2:) E (h, 21) is the conditional empirical variance at time i and (h(h)) EV-iVV(h,, 2;)] is the true conditional variance.
21

---

Proof. First of all, note that for a L- L-Lipschitz loss function E H. x 2 - R, we have
( R i-1
[e(hs; (mle(hn
2:)] ((hs, 2.))
[e(h) 2.)) - z1)
2Td(h, M.).
(15)
Indeed, we can deduce Equation (15) from Jensen inequality, the triangle inequality, and by definition that we have
( E [e 2ill,
mi))
x E 1-1
(((h),2)) - e(h4, z4)1 + (e(1; - e(h', 2i)]
E 2Ld(h h() 2Ld(hs KQ).
From the Kantorovich-Rubinsti duality theorem [Vi109, Remark 6.5], we have
E Pemps
E [[(h,, z;)] - E(h,, zi)
< 2L
Wi T.,s) Σ
E b-TLs
Ru(hs) - C(hss 2:)]
2m
Now, define X₂ (hs,; 2:) R₁- (e 2:)] l(hs, zz). We also recall that for any have
(h;, 2;) = (e(h; 2,) 1 [e z, )) and (h, = E (h,, 2:)]. To apply the supermartin-
gales techniques of [HG23a], we define the following function:
(S, (s. hm) = Axx,(h, 2:) - X
Σ
(V,(h,, 2.) + Vi(h+)).
2
I=1
==1
Now, Lemma 3.2 of [HG23a] state that the sequence (SMm)m2 defined for any m as:
SM ==
E
exp (Sm(S, h1 (mm),)hmm)))))))) hm))
(li Jtm) mi is 60 m
a supermartingale. We exploit this fact as follows:
m
m
E
[1,,, 2;)1 E(h,, 2.)
=
Σ Xi 2i)
(b1 A
IE (hi Ar (omir
[mm(S Amm)
X
E hunts
(i(h), + vi(ba))
2
==1
In (5Mm)
+
h
The last line holds thanks to Jensen's 's inequality. Now using Ville's inequality ensures us that:
1
PP Vm, S.M 5 2
Thus, with probability 1 1, 8, for any have In (SMm) S In (+). This concludes the proof.
B.5 Proof of Theorem 4
Theorem 4. We assume our loss E be non-negative and T.-Lipschitz. We also assume that, for any S, ( (..)) [E,, 2 < 1 (bounded conditional order 2 moments for priors). Then, for any 5 E (0, 1], with probability at least 1 - 8 over the sample S, any online predictive sequence (used as priors) (Ts)421, we have with probability at least
over the sample S ~ p. the following. holding for the data- detendepnnd measures T.S == (S, .) and any posterior sequence (pt)z21
m
2L
m
2ln (+)
E hemp:
Ble(hi, Fi-I] E(h,, zi)
<
W(p.,T,.)
+
77
m
m
22

---

Proof. The proof starts similarly to the one of Theorem 3. Indeed, note that for L-Lipschitz loss function é Z R. we have
( 2i)
(1),
2Ld(h, ht).
(16)
Indeed, we can deduce Equation (16) from Jensen inequality, the triangle inequality, and by definition that we have
( E [e [(h,,,))] 2:)1 zi)1-e(hi.z))) zi) 1-1
E [ 2:)1- (1
$ E 1-1
[((h),))) e(h1, z4)1 + |e(h; 2.) - E(h,, 2:)]
E 2Ld(h H()) = 2Ld(hs M4).
From the Setttorvvic-RRubisttiee duality theorem [Vi109, Remark 6.5], we have
m
E [1(s, z:)] - E(h;, 2i)
S 2L Σ Wi mis)) +
Σ
E howaL
[R,(hs) - C(hs, 2:)]
hampp
Now, define X2 2,) := Ex-,le(h,, 2.)1 of [CWR23], we define the following function:
e(h4, z,). To apply the supermartingales techniques
m
X2
m
fm (S, bi.... hm)
Σ (h,
E [[ 21
2
Now, because our loss is nonnegative, [CWR23, Lemma A.2 and Lemma B.1] state that the sequence defined for any
exp (fm(S, M1, hi, hm))]
SMm = (hu
E
is a supermartingale. We exploit this fact as follows:
E [l 2:)1 E(hr,
E (ba Am Jun am.mm....m.m
X, zi)
h-mpi-
E
Um hi,, 1mm)
À (hi Jen Jii
m.
m
2
In (SMM)
E lewwL
E (((h, 2:) 3]
A
The last line holds thanks Jensen's inequality. Now using Ville's inequality ensures us that:
P Vm, Vm, SM, -
2
Thus, with probability 1-6, for any m we have In (SM 55 In J. We conclude the proof by exploiting the boundedness assumption on conditional order 2 moments and optimising the bound in X.
C Supplementary insights on experiments
In this section, Appendix C.1 presents the learning algorithm for the i.i.d. setting. We also introduce the online algorithm Appendix C.2. We prove the Lipschitz constant of the loss for the linear models in Appendix C.3, Finally, we provide more experiments in Appendix C.5.
23

---

C.1 Batch algorithm for the i.i.d. setting
The pseudocode of our batch algorithm is presented in Algorithm 1.
Algorithm (Mini-)Batch Learning Algorithm with Wasserstein distances
1:
procedure PRIORS LEARNING
2: h1,..., hx < initialize the hypotheses
3:
for é - ,,..., .'' do
4:
for each mini-batch U for i + 1,... K do U, 4 U S;
S do
5:
6:
7:
h; + perform a gradient descent step with VRa, (ha)
8:
return hypotheses h1 ... hx
9:
10: procedure POSTERIOR LEARNING
< initialize the hypothesis
12:
for / < 1...., , do
13:
for each mini- Mami-bbtcc U S S do
- perform a gradient descent step with (/Ru(h) + E [St dddd(h, h:)]
14:
15:
return hypothesis/ h
PRIORS LEARNING minimises the empirical risk through maniibbtchhs! U C S for T epochs. More precisely, for each epoch, we (a) sample a mini-batch (line by excluding the set S from for each fú E Ht (line 5-6), then (b) the hypotheses h1.... hg E H are updated (line 7). In POSTERIOR LEARNING, we perform gradient descent step (line 14) on the objective function associated with Equation (5) for 7" epochs in mini-batch fashion.
C.2 Learning algorithm for the online setting
Algorithm 2 presents the pseudocode of our online algorithm.
Algorithm 2 Online Learning Algorithm with Wasserstein distances
Initialize the hypothesis ho H.
2: for +- 1,..., m do
3: for < 1,..., T do
4: h4 t perform gradient step with Vie(h, z,) + B(d(h,, h1-1)-1)] (Eq. (7) with B)
5: return hypotheses h ftm
For each time step i, we perform T gradient descent steps on the objective associated with Equation (6) (line 4). Note that we can retrieve OGD from Algorithm 2 by (a) setting T 1 and (b) removing the regularisation term Bdd(,,, h --)1)
C.3 Lipschitzness for the linear model
Recall that use, in experiments, the marti-margin loss function from the Pytorch module defined for any linear model with weights W RD xd and biases E RRD any data point E X x
1
max (0, f(W,b, Σ C(W, z) = 3 リ'ン
where f(W, b, y = + (W - w [yl. x) + blyl] bly). and Wiyl e Rd and bly] E IR are respectively the vector and the scalar for the y-th output.
To apply our theorems, we must ensure that our loss function Lipschitz with respect to the linear model. hence the following lemma.

---

Lemma 8. For any (x.y) E 2' x y with the norm of x bounded by 1, the finction W, b + E(W, b, z) is 2-pischiizz
Proof. Let (W, b). (W", both in Mixd x TRD
we have
(e(,,b,)) - E(W", b,' 2)1 5
Σ
max (,W,,,,,,, max (0, J(W", ;,, 2/,2
D
y'
Note that because a + max(0, a)) is L-Lipschitz, we have:
(,(, -(W,', (('6,,2)) =
1
Σ
((W. f(W', b','))
1 v'zy
Finally, notice that:
| Σ ((W,6,2,2)) - 2.,", 1>1 デ'ø4
Σ
K(W -W') - -W - -W))l,,
A'Ay
Σ
1(b - 8060 - - -b)bll
| - 1
8'
Σ
II(W - W' - (W - Telll ||x|
|3| 1
y'
Σ
10b - ()71 - (b (b-b)(o]1-
D
8'
Because we consider the Euclidean norm, we have for any y/ E y:
I(W - -W (W W'Llll VI(W - W' - (W - W/
<2((W - W" + II(W (D
S WHIW-W'1
The second line holding because for any scalars a, b. we have (a b) < 2(a² + b²) and the last line holding because ||
W2 Eper II(W [2]l2
similar argument gives
Σ (b - b')(n'l - (b b0)lol < v2 b'11. 8'
Then, using that ||^||| < 1 and summing all y gives:
Je(W,,,2 2) M(W' S /2 W'll + ||b 11b-811) b'[))
Finally, notice that (I|W- -// +|b-++|bbbb11p < 2([ - W 0113) 2 (WW,))-WWn.o.. ()),
Thus |[ - w + |bb b'|l - (W, (W", /)]. This concludes the proof.
C.4 Lipschitzness for neural networks
Recall that we use, in our experiments, the multi-margin loss function from the Pytorch module de- fined consider the loss f(h, (x, v)) د En max(0, (4m(ly))-ll/)) which is -ipischhitz the output of the neural network with input x. Note that this loss is s/-lipschitz with respect to the outputs. To apply our theorems, we must ensure that our loss function is Lipschitz with respect to the weights of the neural networks, hence
w.r.f. the outputs h h1]], ".....,,][[[])) For neural networks,
the following lemma with associated background.
25

---

We define FCN recursively as follows: for a vector Wi = (W. b)), (f.e., the vectorisation of a weight matrix Wi and bias and an input datum x, FCN, (W,, x] = = (W1 X + b1), where di is the activation function. Also, for any i 2 2 we define for vector W; = (W; bi, W; (defined recursively as well), FCN, s; x) oj (W,
(W,-1, (
+ b;). Then, setting z (x, y) a
datum and (x) == (WN,(W,;) x) we can rewrite our loss as a function of (W.. 2).
Lemma 9. Assume that all the weight matrices of W; are bounded and that the activation functions are Lipschitz continuous with constant bounded by Ka- Then for any datum = (x, y), any i,
W; + ((W.,)) is Lipschitz continuous.
Proof. We consider the Frobenius norm matrices as W2 is a vector we consider the L.2nnorm on the vector. We prove the result for = 2. assuming it is true for i = 1. We then explain how this proof generalises the case 1 and works recursively. Let z, W2, W for clarity we write FCN₂ (x) == FCN(W2, x) and FxN] = FCN(W22 x). As E is Lipschitz on the outputs (x), (x). We have
1e(2,. z) - ((W,,, z)1 S FFN2(x) - (x)]
S 1 00 (W2FCN (x) + (2) 02 (WEFCN) + K6)l
< k 1W2FNN (x) -W3 - -b2ll
<nK (11(W2 FCN (x) + +I[W)(FCN1()) (x) (CC((X)) + |6b - b2ll)
Then, we have I[(W2 W2) (x) S 11(W: -2 L second inequality holding as FCN, (x) is a continuous function of the weights. Indeed, as on a compact space, a continuous function reaches its maximum, then its norm is bounded by a certain Kx. Also, as the weights are bounded, any weight matrix has its norm bounded by a certain Kw thus FCN, I |W| - FCN (x)ll-
S K2 (WW W/) |r. The
[IW](FNN - FCN, Finally, taking Keemp = K, max(Ks, Kw, 1) gives:
||
1e(W2, z) ((W,, 2) I Kremp (II(W2 W + ll62 6 + |[FNN (x) FCN(
Exploiting the recursive assumption that FCN, is Lipschitz with respect to its weights W1 gives [ FCN (x)] < K, Will.
If we denote by (W2, b2) the vector of all concatenated weights, notice that (W2, W r + lb2 831 = V(I(W22 - W3) + 162 - -, < ( - 1
1|62 22 = 2 b2)
(W2, b/)ll Il (we used that for any real numbers a, b, (a + b)2 < 2(a² + B))). We then have:
1e(W2, 2) ((2 2) S K Temp max( (v2, K1) (ll b2) - (W₁, +6)1+))+++100 ||W, Wi
I 22Kemp max (v2, Ki)l[W, - --
The last line holds by reusing the same calculation trick. This concludes the proof for i = 2. Then for 1 the same proof holds by replacing W2, b2, FCN, by W1, 61, FCN, and replacing FCN, (x), FCN, (x) by x (we then do not need to assume recursive Lipschitz behaviour). Therefore the result holds for i 1.
We then properly apply a recursive argument by assuming the result at rank reusing the same proof any rank i by replacing W2, b2, FCN, by W b, FCN, and FCN, (xx) FCN, (x) by FCN, (x), (FCNL,(x), This concludes the proof.
C.5 Experiments with varying number of priors
The experiments of Section 4 rely on data-dependent priors constructed through the procedure PRIORS LEARNING. We fixed number of priors K equal to 0.2./m. This number is an empirical tradeoff between the informativeness of our priors and time-efficient computation. However, there is no theoretical intuition for the value of this parameter (the discussion of Section 3.1 considered K = vm as a potential tradeoff; see Appendix A). Thus, we gather below the performance of our learning procedures for K a.m, where {0, 0.4, 0.6, 0.8, (the case = 0 being a convention to
26

---

denote K = 1). The experiments are gathered below, and all remaining hyperparameters (except K) are identical those described in Section 4.
Analysis of our results. First, when considering neural networks, note that for any dataset except SEGMENTATION, LETTER, the performances of our methods similar better when considering data-dependent priors (i.e., when a > O). A similar remark holds for the linear models for all datasets except for SATIMAGE, SEGMENTATION, and TICTACTOE. This illustrates the relevance of data- dependent priors. We also remark that there is no value of a, which provides a better performance on all datasets. For instance, considering neural networks, note that a gives the better performance (i.e., the smallest RR, (h)) for Algorithm (1/vm) for the SATIMAGE dataset while, for the same algorithm, the better performance on the SEGMENTATION dataset attained for a 0.8. Sometimes, the number K does not have a clear influence: on MNIST with NNs, for Algorithm 1 (%/ml) our performances are similar, whatever the value of K, but still significantly better than ERM. any case, note that for every dataset, there exists value of K and such that our algorithm attains either similar or significantly better performances than ERM on every dataset, which shows the relevance of our learning algorithm to ensure good generalisation ability. Moreover, there is no obvious choice for the parameters e. For instance, in Tables 2 and 3, for the SEGMENTATION dataset, the parameters K = 1, 1 are optimal (in terms of test risks) for both models. As K = 1 means that our single prior is data-free, this shows that the intrinsic structure SEGMENTATION makes less sensitive to both the information contained in the prior (K 1 meaning data-free prior) and the place of the prior itself (s 1/m meaning that we give less weight to the regularisation within our optimisation procedure). On the contrary, in Table Table 1, the YEAST dataset performs significantly better when & = 1/ 1//mm/K K = 0.2ym), exhibiting positive impact of our data-dependent priors.
To
C.6 Experiments on classical regularisation methods
We perform additional experiments to see the performance of the weight decay, i.e., the L2 regu- larisation on the weights; the results are presented Table 4. Moreover, notice that the 'distance to initialisation' ||w- woll (where Wo is the weights initialized randomly) is a particular case of Algorithm 1 when K = (i.e., we treat the data as a single batch, and the prior is the data-free initialisation); the results are in Tables 2 and 3.
Analysis of our results. This experiment on the weight decay demonstrates that on a few datasets (namely SENSORLESS and YEAST), when our predictors are neural nets, the weight decay regularisa- tion fails to learn while ours succeeds, as shown Table In general, this table shows that, on most of the datasets, considering data-dependent priors leads to sharper results. This shows the efficiency of our method compared to the 'distance to initialisation' regularisation.
27

---

Table 2: Performance of Algorithm 1 compared to ERM on different datasets for neural network models. We consider 1/m and 1/mm, with K aammm and a {0, 0.4, 0.6, 0.8, 1}. We plot the empirical risk Rg (h) with its associated test risk (h).
(a) K
(b) K 0.4ym
Alg. (
Alg. 1 (CL)
Alg. (+)
Alg.
Vm (k)
Dataset
(k(
(k)
(k)
Dataset
Rg(A))
(A)
9gg(h)
ADULT
0.207
0.207
0.248
0.248
ADULT
0.167
0.166
0.164
0.164
FASHIONMNIST
0.160
0.164
0.158
0.164
FASHIONMNIST
0.160
0.164
0.156
0.160
LETTER
0.258
0.269
0.268
0.280
LETTER
0.263
0.275
0.252
0.263
MNIST
0.116
0.123
0.085
0.096
MNIST
0.112
0.120
0.085
0.096
MUSHROOMS
0.000
0.000
0.000
0.001
MUSHROOMS
0.000
0.000
0.000
0.000
NURSERY
0.705
0.720
0.720
0.736
NURSERY
0.705
0.720
0.706
0.719
PENDIGITS
0.704
0.724
0.021
0.037
PENDIGITS
0.011
0.025
0.010
0.022
PHISHING
0.048
0.052
0.038
0.055
PHISHING
0.043
0.053
0.041
0.052
SATIMAGE
0.148
0.208
0.147
0.207
SATIMAGE
0.147
0.178
0.145
0.174
SEGMENTATION
0.141
0.176
0.248
0.385
SEGMENTATION
0.345
0.408
0.225
0.416
SENSORLESS
0.907
0.911
0.907
0.911
SENSORLESS
0.075
0.078
0.074
0.077
TICTACTOE
0.000
0.042
0.000
0.033
TICTACTOE
0.000
0.031
0.000
0.019
YEAST
0.695
0.712
0.677
0.658
YEAST
0.450
0.480
0.695
0.712
(c) K = 0.6.m m
(d) K = 0.8.m
Alg. 1 (
Alg. 1 ((m))
Alg. (
Alg. 1 (mm))
Dataset
Ml((h)
(b)
(A)
(A)
Dataset
Mis(h)
(h)
(l)(h)
(R,)
ADULT
0.165
0.163
0.165
0.164
ADULT
0.165
0.164
0.164
0.164
FASHIONMNIST
0.158
0.164
0.156
0.160
FASHIONMNIST
0.158
0.163
0.156
0.161
LETTER
0.259
0.275
0.260
0.267
LETTER
0.260
0.274
0.260
0.267
MNIST
0.112
0.121
0.084
0.094
MNIST
0.113
0.121
0.083
0.093
MUSHROOMS
0.000
0.000
0.000
0.000
MUSHROOMS
0.000
0.000
0.000
0.000
NURSERY
0.706
0.719
0.706
0.719
NURSERY
0.706
0.719
0.704
0.721
PENDIGITS
0.008
0.023
0.009
0.022
PENDIGITS
0.011
0.026
0.008
0.020
PHISHING
0.043
0.055
0.040
0.050
PHISHING
0.042
0.054
0.048
0.063
SATIMAGE
0.138
0.184
0.141
0.174
SATIMAGE
0.136
0.174
0.128
0.183
SEGMENTATION
0.577
0.845
0.145
0.309
SEGMENTATION
0.140
0.463
0.121
0.249
SENSORLESS
0.073
0.076
0.073
0.076
SENSORLESS
0.075
0.079
0.074
0.077
TICTACTOR
0.000
0.023
0.000
0.013
TICTACTOR
0.392
0.301
0.000
0.008
YEAST
0.461
0.449
0.410
0.426
YEAST
0.394
0.422
0.686
0.671
(e) K = vm
(f) HRM
Alg. 1 (2))
Alg.
(L))
Dataset
Re(hh)
Dataset
Rs(h)
(K)
(K)
(N)
ADULT
0.165
0.163
ADULT
0.167
0.166
0.167
0.167
FASHIONMNIST
0.163
0.167
FASHIONMNIST
0.159
0.164
0.157
0.162
LETTER
0.258
0.270
LETTER
0.253
0.269
0.255
0.267
0.119
0.127
MNIST
0.110
0.119
0.084
0.094
MUSHROOMS
0.000
0.000
MUSHROOMS
0.000
0.000
0.000
0.000
NURSERY
0.706
0.719
PENDIGITS
PHISHING
NURSERY
0.012
0.706
0.042
0.719
0.026
0.050
0.703
0.012
0.039
0.024
0.722
0,053
PENDIGITS
PHISHING
0.046
0.009
0.055
0.022
SATIMAGE
0.137
0.176
0.125
0.169
SATIMAGE
0.141
0.189
SEGMENTATION
0.162
0.398
0.153
0.387
SEGMENTATION
0.174
0.389
SENSORLESS
0.075
0.077
0.073
0.076
SENSORLESS
0.075
0.078
TICTACTOE
0.000
0.035
0.000
0.008
TICTACTOE
0.000
0.023
YEAST
0.415
0.435
0.418
0.450
YEAST
0.644
0.682
28

---

Table 3: Performance of Algorithm compared to ERM on different datasets for linear models. We consider 1/m and & 3/vm, with K /v/m and E (0,0.4, 0.6, 0.8, 1). We plot the empirical risk (h) with its associated test risk (h).
(a) K
(b) K 0.4ym
Alg. (
Alg. (LL) (k)
Alg. (+)
Alg.
Vm (R)
Dataset
(k(
(k)
(k)
Dataset
Rg(h)
(A)
9g((h)
ADULT
0.207
0.207
0.248
0.248
ADULL
0.166
0.167
0.166
0.167
FASHIONMNIST
0.142
0.155
0.126
0.149
FASHIONMNIST
0.128
0.150
0.126
0.150
LETTER
0.286
0.296
0.286
0.295
LETTER
0.285
0.296
0.286
0.297
MNIST
0.067
0.092
0.069
0.094
MNIST
0,069
0.089
0.067
0.093
MUSHROOMS
0.001
0.001
0.000
0.000
MUSHROOMS
0.001
0.001
0.001
0.001
NURSERY
0.788
0.799
0.796
0.804
NURSERY
0.760
0.778
0.769
0.781
PENDIGITS
0.049
0.060
0.047
0.057
PENDIGITS
0.050
0.061
0.048
0.061
PHISHING
0.063
0.065
0.057
0.062
PHISHING
0.062
0.067
0.065
0.068
SATIMAGE
0.142
0.202
0.136
0.199
SATIMAGE
0,565
0.773
0.137
0.200
SEGMENTATION
0.053
0.151
0.079
0.176
SEGMENTATION
0.058
0.212
0.177
0.382
SENSORLESS
0.907
0.911
0.907
0.911
SENSORLESS
0.220
0.220
0.133
0.134
TICTACTOE
0.013
0.021
0.013
0.021
TICTACTOE
0.378
0.290
0.013
0.021
YEAST
0.702
0.720
0.693
0.687
YEAST
0.488
0.478
0.492
0.478
(c) K = 0.6/m
(d) K = 0.8.m
Alg. 1 (
Alg. 1 (()))
Alg. (
Alg. 1
(T)))
Dataset
9la(h)
(b)
(A)
(A)
Dataset
Mi{(h)
(h)
(l)(h)
(R))
ADULT
0.166
0.167
0.166
0.167
0.166
0.167
0.166
0.167
FASHIONMNIST
0.127
0.147
0.127
0.150
0.130
0.149
0.128
0.151
LETTER
0.288
0.296
0.286
0.296
LETTER
0.285
0.296
0.288
0.297
MNIST
0.067
0.092
0.067
0.093
MNIST
0.067
0.091
0.067
0.093
MUSHROOMS
0.001
0.001
0.001
0.001
MUSHROOMS
0.001
0.001
0.001
0.001
NURSERY
0.791
0.802
0.759
0.779
NURSERY
0.771
0.787
0.758
0.778
PENDIGITS
0.048
0.061
0.047
0.059
PENDIGITS
0.047
0.060
0.047
0.059
PHISHING
0.062
0.067
0.064
0.068
PHISHING
0.062
0.066
0.065
0.068
SATIMAGE
0.146
0.202
0.137
SATIMAGE
0.168
0.216
0.137
0.199
SEGMENTATION
0.058
0.215
0.058
0.204
SEGMENTATION
0.053
0.212
0.052
0.204
SENSORLESS
0.129
0.130
0.130
0.130
SENSORLESS
0.129
0.130
0.132
0.132
TICTACTOR
0.013
0.021
0.013
0.021
TICTACTOR
0.013
0.021
0.013
0.021
YEAST
0.477
0.461
0.478
0.464
YEAST
0.476
0.461
0.477
0.460
(e) K = vm
(f) HRM
Alg. 1 (2))
Alg.
(L))
Dataset
Re(hh)
Dataset
Rs(h)
(K)
(N)
(R)
ADULT
0.166
0.167
ADULT
0.166
0.167
0.166
0.167
FASHIONMNIST
0.139
0.153
FASHIONMNIST
0.354
0.361
0.127
0.151
LETTER
0.287
0.297
LETTER
0.287
0.296
0.288
0.298
0.065
0.091
MNIST
0.068
0.092
0.065
0.092
MUSHROOMS
0.001
0.001
MUSHROOMS
0.001
0.001
0.001
0.001
NURSERY
0.794
0.807
PENDIGITS
PHISHING
NURSERY
0.050
0.062
0.795
0.067
0.062
0.805
0.065
0.047
0.796
0.059
0.805
0.067
PENDIGITS
PHISHING
0.064
0.052
0.067
0.064
SATIMAGE
0.143
0.200
0.137
0.201
SATIMAGE
0.148
0.209
SEGMENTATION
0.055
0.210
0.055
0,212
SEGMENTATION
0.087
0.232
SENSORLESS
0.130
0.130
0.131
0.132
SENSORLESS
0.134
0.136
TICTACTOE
0.013
0.021
0.392
0.301
TICTACTOE
0.228
0.238
YEAST
0.476
0.456
0.476
0.457
YEAST
0.470
0.427
29

---

Table Performance of ERM with weight decay (with the L2 regularisation) for linear and neural network models.
(a) Linear
(b) NN
L2 Reg.
(L)
L2 Reg. (vm)
L2 Reg. (2)
L2 Reg. (
Dataset
(i)(h)
(h)
Sts (A)
(b)(b)
Dataset
(ts(A)
(h)
(h)
ADULT
0.207
0.207
0.248
0,248
ADULT
0.207
0.207
0.248
0.248
FASHIONMNIST
0.141
0.149
0.127
0.150
FASHIONMNIST
0.160
0.166
0.159
0.164
LETTER
0.285
0.295
0.285
0.296
LETTER
0.261
0.275
0.256
0.269
MNIST
0.067
0.092
0.066
0.092
MNIST
0.116
0.125
0.084
0.095
MUSHROOMS
0.001
0.001
0.000
0.000
MUSHROOMS
0,000
0.000
0.000
0.000
NURSERY
0.788
0.799
0.796
0.804
NURSERY
0.704
0.721
0.770
0.788
PENDIGITS
0,049
0.060
0.047
0.057
PENDIGITS
0.009
0.022
0.012
0.026
PHISHING
0.063
0.065
0.057
0.062
PHISHING
0.042
0.050
0.054
0.059
SATIMAGE
0.144
0.203
0.138
0,200
SATIMAGE
0.150
0.215
0.143
0.205
SEGMENTATION
0.058
0.157
0.075
0.177
SEGMENTATION
0.141
0.216
0.198
0.371
SENSORIEESS
0.907
0.911
0.907
0.911
SENSORIEES
0.907
0.911
0.907
0.911
TICTACTOE
0,013
0.021
0.013
0.021
TICTACTOE
0.000
0,046
0.000
0.021
0.702
0.720
0.693
0.687
0.662
0.674
0.693
0.683
30


Reviews:
[{"review_id": "40NvRfhv5G", "reviewer": "Reviewer_gr5G", "summary": "The paper builds on recent advances in PAC-Bayesian learning and derives new Wasserstein distance-based generalization bounds. Besides batch learning for iid data, a first set of results are derived for online learning (with non iid data). The authors also provide tight bounds for the case of heavy tailed loss with bounded second order moments. Through experimental results the authors argue that these bounds can inspire new learning algorithms that achieve comparable (and in some cases better) empirical performance than classical benchmarks (ERM for batch and OGD for online setting). \n", "questions": "Please see my comments/suggestion in the Weaknesses section. ", "limitations": "Would have liked to see a more robust discussion on the limitations of the proposed approach. A clear explanation about when and to what extent geometry of data space can improve the results obtained through Wasserstein distance based approach would be much appreciated. Also comment on future work to refine results on online setting. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "\nThe introduction and main results are well placed in the context of recent literature in this area. Although this reviewer has not worked on the topic of PAC-Bayes learning, it was possible to understand the authors’ contribution relative to work by Haddouche and Guedj, Catoni and co-authors, and recent paper of Amit et al from NeurIPS 2022. One would have expected more clarity on the use of “supermatingale toolbox” in the main text of the paper, but I suppose this can be addressed using minor revisions of the paper. \n\n", "weaknesses": "\nHowever, there are several points that impede the broader understanding of the work. Firstly, the role and possible limitations imposed by L-Lipschitz assumption should be clarified. \n\nIn the discussion of Theorem 1, the authors mention that the variance terms are considered with respect to the prior distributions $\\pi_{i,\\mathcal{S}}$ and not $\\rho$. Can you clearly explain why this is a strength of the result (if so)? \n\nIn comment after equation (2), I agree that Wasserstein distance as regularizer…allows the user of multiple priors. But the issue of selecting K (as opposed to choice of $\\lambda$ in classical algorithm). The authors do provide some discussion of role of $K$ but the nuance of its role in regularization is still not very clear (besides, the discussion on tradeoff needs a bit more clarity). \n\nAppreciate the interest in online setting, but the contribution/merits of algorithm based on equation (4) are not very clear. Firstly, what is the conceptual novelty here in comparison to online counterpart to equation (3)? Secondly, the particularization to Dirac masses seems like a restriction. The algorithmic aspects need a bit more clarity as well. \n\nThe computational results seem promising and an assertive discussion on comparison with ERM and OGD benchmarks is needed. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your thoughtful review. We are encouraged to read that 'the introduction and main results are well-placed in the context of recent literature' and that you appreciated the goal of our work, even though 'this reviewer has not worked on the topic of PAC-Bayes learning', as one of our goals is to reach a broader audience.  \n\n**Role of Lipschitz assumption** \n\nAs the Wasserstein distance is used in PAC-Bayes as a geometric notion of complexity, the theoretical role of the Lipschitz assumption is to allow the use of such a distance. On the contrary, the KL divergence comes from information theory and does not require such an assumption, but the price to pay is that the KL divergence has erratic behaviours in many cases, starting with Dirac measures. \nIndeed, a KL divergence between two Dirac measures with disjoint supports is infinite.\nThus, Lipschitzness helps to handle a broader range of prior/posterior pairs. However, we agree that the Lipschitzness requirement is a clear limitation (as it is to a wide variety of generalization bounds with similar assumptions) and we will make this more clear in the next version.\n    \n**Discussion on Theorem 1** \n\nPrevious PAC-Bayes bounds using supermartingales techniques implied that order 2 moments of the prior *and all considered posteriors* have to be uniformly bounded by a certain $C$. This suggests that those two distributions have to be robust enough to compensate for heavy-tailed data. For instance, if the data distribution of a point $z$ only admits a finite variance and that we consider the loss $\\ell(h,z)= |h-z|$ where both $h,z$ lie in the real axis. Then, assuming $\\mathbb{E}[z^2]\\le V$, then by Cauchy Schwarz, we have  $\\mathbb{E}[\\ell(h,z)^2] \\le \\mathbb{E}[h^2] + 2V\\mathbb{E}[|h|] +V^2 \\le C$, the last inequality being our assumption. This invites us to consider posterior distributions with first and second moments satisfying the previous inequality, which is restrictive. On the contrary, our work assumes only such an assumption on the prior distribution: we are allowed to move freely on the space of distribution to find the best posterior. We thank you for this discussion which will enhance our manuscript. We will provide more detail on the high-level ideas of the proof in the next version to explain the use of the 'supermartingale toolbox'.\n    \n**Role of $K$** \n\nWe thought the role of $K$ with respect to the notion of generalisation, i.e., having multiple data-dependent priors may tighten the generalisation bound and thus, ensure good theoretical generalisation ability. In this work, we consider regularisation as directly incorporating the generalisation error into the algorithm. Understanding more deeply the role of $K$ into the optimisation procedure is a promising lead for future works.\n\n **Online setting** \n\nThe online counterpart of the classical bound Eq. (3) would involve a KL divergence at each time step while our approach Eq. (4) implies a Wasserstein distance. The important point is that we perpetrate the spirit of Haddouche and Guedj (2022), which showed that the natural online counterpart of the classical PAC-Bayes bound Eq. (3) comes with sound theoretical guarantees. Our approach is similar here: in Theorems 1 and 2, we show that our batch PAC-Bayesian algorithm is derived from sound theoretical bounds, and we show in Theorems 3 and 4 that it is the same for its online counterpart. Concerning the Dirac case, it is indeed a restriction for classical bounds Eq. (3). However, we focused on this important case as it cannot be handled properly by classical PAC-Bayes algorithms as the KL divergence of two Dirac with disjoint supports is infinite. In other words, our framework **does not** require Dirac priors (many other options can be used), but it can actually accommodate Dirac priors as opposed to KL-based bounds. An important message of our work is that the PAC-Bayes learning is rich enough to explain the generalisation ability of deterministic predictors (and not only probabilistic ones).\n\n**About the experiments** \n\nAs suggested, we will include more discussion about the experiments in the next version. We are happy to provide supplementary insights into our experimental conclusions. We also provided new experiments with classical regularisers (see general answer).\n\nWe thank you again for your review and are happy to include the above comment in the revised version of our work, and hopefully, the camera-ready."}, {"review_id": "dfuecj1xCZ", "reviewer": "Reviewer_tL5n", "summary": "This work propose PAC-Bayesian learning with the KL divergence replaced by the Wasserstein distance on the metric space of hypotheses $(\\mathcal{H}, d)$. Denoting the data distribution by $\\mathcal{D}$, the authors study the following learning problems:\n\n1. Batch learning. Under the assumption that the loss function has bounded 2nd moment with respect to $\\mathcal{D}$ and priors over $\\mathcal{H}$, the authors derive a generalization bound in terms of $LW$, where $W$ is the Wasserstein distance between posterior and prior distributions over $\\mathcal{H}$ and $L$ is the Lipschitz constant of the loss function (with respect to $d$).\n2. Online learning. Under the assumption that the loss function has bounded 2nd _conditional_ moment with respect to $\\mathcal{D}$ and priors over $\\mathcal{H}$, the authors derive a similar generalization bound as above, where the population risk is defined by the sum of conditional expections of the loss, given a filtration adapted to the sequence of data.\n\nBoth bounds can be applied to heavy-tailed loss functions with bounded 2nd moment. And they can be used to derive new learning problems regularized by $LW$. Experimental results with a linear model and an NN model show that these algorithms have better test risks than ERM and OGD on several dataset, among which online learning with the NN model shows the most improvement.", "questions": "- Though not required, but I think high level ideas of the proofs of Theorem 1 and 3 would be a nice addition.\n-  In Section 4.1: Batch algorithm, has the definition of $d(h,h_i)$ been defined before? I guess the authors have make a convention that $d(h,h_i)=d(w,w_i)$.\n- Can the authors performs the experiment against ERM with standard regularization as well?", "limitations": "The authors might want to add some limitation of the bounds. For example, it might be difficult to compute the Wasserstein distance over nonparametric models, such as kNN.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- This is a strong result in the field of PAC-Bayes learning. Replacing the KL divergence by the Wasserstein distance is logical when the geometry of the underlying metric space is in consideration.\n- The bound is just as nice as the KL divergence version of the PAC-Bayes bound. And the ability to convert the bound into the algorithm is powerful.\n- The experimental results show that the bound can be used to improve models' generalization.\n", "weaknesses": "- It seems that the batch size substantially affects the test risks. For example,  learning with $\\epsilon = 1/m$ on MNIST and TICTACTOE with the linear model, and TICTACTOE on the NN model. Are there any specific reasons that make these models underperform on these datasets?\n- Alg 2. seemingly performs as well as OGD with the linear model; on the other hand, the former does noticeably better with the NN model. The authors might want to discuss on why the NN model performs well in this case.\n- A minor comment on the organization: In Section 4.1: Batch algorithm, the authors set $L=1/2$ and proceed to define a specific loss that has the said Lipschitz constant, which is quite confusing to read. I think it is more logical to introduce the loss function first. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your enthusiastic review. We are thrilled to read that you see this work as a 'strong result in the field of PAC-Bayes learning'. We answer your questions below. \n\n**About the batch size** \n\nThis is indeed a fair question, and unfortunately at this stage we found no particular reason why $\\varepsilon$ affects the test risks. For a given dataset, there is no obvious choice for the model and the parameters $\\varepsilon$ and $K$. For instance, in Table 3 of Appendix C, for the SEGMENTATION dataset, the parameters $K=1,\\varepsilon=\\frac{1}{m}$ are optimal (in terms of test risks) for both models. As $K=1$ means that our single prior is data-free, this shows that the intrinsic structure of SEGMENTATION makes it less sensitive to both the information contained in the prior ($K=1$ meaning data-free prior) and the place of the prior itself ($\\varepsilon=1/m$ meaning that we give less weight to the regularisation within our optimisation procedure). On the contrary, in Table 1, the YEAST dataset performs significantly better when $\\varepsilon=1/\\sqrt{m}$ (and $K=0.2\\sqrt{m}$), exhibiting a positive impact of our data-dependent priors. We will add a discussion on this matter in the next version. \n    \n**Performance of Alg.2** \n\nAs stated in lines 353 to 355, we believe that OGD can suffer from underfitting. Indeed, only one gradient descent step is done for each new datum $(\\mathbf{x}\\_i, y\\_i)$, which might not be sufficient to decrease the loss. Instead, our method solves the problem associated with Eq. (7) and constrains the descent with the norm $||\\mathbf{w}-\\mathbf{w}\\_{i-1}||$. In the linear case, we are able to solve the problem, but for the neural network case, we minimise the approximation for 10 steps. As the question was also raised by reviewer mMbV, this answer will be added in the next revision of the paper after line 355.\n\n**About the organisation of Sec. 4.1**\n\n Thank you for notifying this; we acknowledge in our general answer that the beginning of Sec. 4.1 would benefit of more clarity. More precisely, we will move the second paragraph of the 'Batch algorithm' part before Eq. (5). We will also define properly $d$ on $\\mathcal{H}$ to make explicit the convention $d(h\\_{\\mathbf{w}},h\\_{\\mathbf{w}'})=||\\mathbf{w}-\\mathbf{w}'||$ and will replace the Euclidean norm by the distance $d$ in Eqs. (5), (6), (7).\n\n**High-level ideas of the proof** \n\nDue to space constraints, we did not extend the theoretical discussion as much as we wanted. However, we are happy to put more discussion about both the high-level ideas of the proof and our set of assumptions in the next version.\n\n**Additional experiments** \n\nYes, we will provide additional experiments. As written in the general answer, we implemented in Table 3 of Appendix C.4 the particular case $K=1$ of Algorithm 1, which corresponds to the classical 'distance to initialisation' regularisation (i.e., $||\\mathbf{w}-\\mathbf{w}\\_0||$ with $\\mathbf{w}\\_0$ being the initialisation. It shows that in most cases, taking $K$ greater than 1 (i.e., fully exploiting the theoretical ground offered by our PAC-Bayes bounds) leads to better results in a vast majority of datasets. Furthermore, as it was asked by Rev. jPqk to run an ERM with the 'weight decay' regularisation (i.e, $||\\mathbf{w}||$), this has been added in the pdf document linked to the general answer. This experiment shows concretely that on a few datasets (namely sensorless and yeast) when our predictors are neural nets, the weight decay regularisation fails to learn while ours succeeds as shown in Tables 1 (of our work) and 4 (of the new pdf). More generally, when considering neural nets, the weight decay regularisation outperforms our method 3 times over 11 for batch learning.\n    \nAgain, we thank you for your review and hope our answers address all of your concerns."}, {"review_id": "bvLSCYZlms", "reviewer": "Reviewer_mMbV", "summary": "This paper introduces Wasserstein-based PAC-Bayes bounds both for offline (batch learning) and online learning. \n\nThese bounds are obtained with a clever use of the Kantorovich-Rubinstein duality together with a control of some additional terms appearing in the proof that only depend on the prior. To use the Kantorovich-Rubinstein duality they require the loss to be Lipschitz and to control the additional terms they require the loss to have a bounded second moment, following the techniques from [HG23a]. The extension from offline to online learning comes almost \"for free\" in the analysis due to the super-martingale strategies developed in [HG23a]. This way, the presented bounds have a set of weak assumptions (Lipschitzess + bounded second moment) which makes them amenable to losses with potentially heavy tails.\n\nAnother aspect of the bounds is that they allow data-dependent priors. For this, they separate the training dataset $\\mathcal{S}$ into $K$ subsets $\\mathcal{S}\\_i$and dedicate $K$ data-dependent priors $\\pi\\_i$ that depend on $\\mathcal{S} \\setminus \\mathcal{S}\\_i$. This way, they have an average of Wasserstein distances of the posterior and each of these priors weighted accordingly. This way, for a large number of samples the posterior and the priors start to align helping the bound to become tighter.\n\nFinally, they employ their bounds to derive regularization terms that are employed to design algorithms both in offline and online learning. They showcase how the usage of these algorithms does not decrease the performance of linear and deep models and that, in some cases, they help these models achieve better performance.\n\n\n\n\n\n", "questions": "* How do you justify the usage of the $\\ell_2$ norm on the weights in equations (5), (6), and (7) if the employed loss is only Lipschitz with respect to the outputs of the hypotheses $h_{\\textbf{w}}$ but not necessarily with respect to the weights themselves?\n* What is the intuition for the fact that Algorithm 2 has a smaller empirical risk than OGD? It seems weird given the fact that Algorithm 2 is essentially a regularized version of OGD, which is an algorithm for ERM.", "limitations": "Some of the limitations are mentioned throughout the text, yes.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The strengths of this paper are multiple, but the most important are:\n- The presented theorems are general (Lipschitz and second-moment assumptions only).\n- The proofs of the presented theorems are exposed in a simple way, even though the final results are useful.\n- The theorems allow for deterministic predictors, which is one of the biggest drawbacks of PAC-Bayes bounds.\n- The results are validated empirically.", "weaknesses": "There are not many major issues with the paper. My biggest concern is the following:\n- In the section \"Batch algorithm\" starting in line 275, you use the equation (5) to guide the training of the posterior, which includes the distance $\\lVert \\textbf{w} - \\textbf{w}_i \\rVert_2$ that comes from the Wasserstein distance. However, the employed loss is only Lipschitz with respect to the outputs. How do you justify then the usage of the $\\ell$_2 norm of the weights, as it could be that the loss is not Lipschitz with respect to the weights? The same happens later in equations (6) and (7).\n\nOther smaller issues are the following:\n- The experimental results don't seem too strong compared with previous methods such as the one presented in [PORPH+21]. Although they use probabilistic networks, it would have been interesting to observe how the two methods compare to each other with the same network architecture. For instance, with a FCN and Gaussian priors, they show population risk certificates of ~0.02, while the presented here are of ~0.09 and ~0.12.\n- Some of the writing can be clarified. In particular, I am referring to sentences of the type: \"for all $i$, $\\mathcal{S}$,$\\pi\\_i(S,\\cdot)$ is $\\mathcal{F}\\_{i-1}$ measurable\". This is not very clear, I would recommend changing all these sentences for something like \"the distribution $\\pi\\_i(S,\\cdot)$ is $\\mathcal{F}\\_{i-1}$ measurable for all $i$ and all $\\mathcal{S}$\". This small change can improve readability. \n- I missed some comments on Proposition 5 of [AEM22], which is a Seeger-type bound. How do the presented bounds compare to that?\n- I am not sure the implementation of OGD is correct, given that it ends up having a larger empirical risk than the regularized version. Maybe I am missing something here, or maybe this showcased some limitations of OGD I was not aware of. I also mentioned it explicitly as a question below.\n\nSome typos:\n- In line 29, it should be $R\\_{\\mu}(h) - \\hat{R}\\_{\\mathcal{S}}(h)$.\n- In lines 192 and 193, you forgot to include the hat in $\\hat{R}$.\n- In line 354, it should be $\\mathfrak{C}\\_{\\mathcal{S}}$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive review and for pointing out the 'multiple strengths'.\n\n**Your major concern**\n\nThank you for spotting this - see also our general response. A Wasserstein is defined on a Polish space w.r.t a distance $d$. Indeed our Algos in Eqs. (5-7) must be described w.r.t $d$ and not an Euclidean norm on the weights, we fixed this in the revision. When the predictor space $\\cal{H}$ is parametrised by a Euclidean space with Euclidean distance $||.||$, the distance between two predictors $h\\_{\\bf w},h\\_{{\\bf w}'}\\in \\cal{H}^2$ is $d(h\\_{\\bf w},h\\_{{\\bf w}'})=||{\\bf w}-{\\bf w}'||$. This raises the question of transferring the Lipschitzness on $h_{\\bf w}$ to one on ${\\bf w}$. Lemma 8 ensures this is true for the linear model, but we omitted to prove it was true for our neural nets when weights are bounded. We prove below a new lemma showing that with clipped weights in a Fully Connected Network (FCN) with Lipschitz activation functions, then our loss is Lipschitz w.r.t the weights and we can use the $\\ell_2$ norm in our objective. Note that the clipping constant plays no role so we set it to a large value to avoid interfering with optimisation. This has been added to Sec 4.1 and we hope this addresses your concern.\n\n**Minor**\n1. Discrepancy in performance: this is because we do not minimise the same objective (they use the cross-entropy loss).\n2. Thanks - added to the revised paper.\n3. We do not compare to Prop. 5 of [AEM22] but to their Thms 11-12, which are versions of Prop. 5 for Wasserstein. See paragraph starting on l196. Our proof does not allow the use of the 'small' kl divergence as we need $\\sum_{i=1}^m R_{\\mu}(h)-\\ell(h,{\\bf z}_i)$ to apply our supermartingale trick. Note that our result holds with weaker assumptions than Thms 11-12.\n\n**Questions**\n1. The L2 norm in experiments is motivated by Lemma 8 and the new lemma. In both cases we prove the loss is Lipschitz w.r.t the output $h_{{\\bf w}}$ and ${\\bf w}$.\n\n2. For each datum, OGD is performing only one gradient descent step while our method solves a (constrained) optimization problem. Hence, we believe that OGD might suffer from underfitting as one gradient step at each time may not be enough for a non-regularised method. Since Rev. tL5n has the same concern, we decided to add the answer to the paper after line 355.\n\n**Lemma's statement** \n\nWe define recursively a FCN as follows: for a vector ${\\bf W}\\_1= \\text{vect}(\\{W\\_1,b\\})$ and an input datum $x$, $FCN\\_1({\\bf W}\\_1,x)=\\sigma\\_1(W\\_1x+b\\_1)$, where $\\sigma\\_1$ is the activation function. Also, for any $i\\geq 2$ we define for a vector ${\\bf W}\\_i=(W\\_i,b\\_i,{\\bf W}\\_{i-1})$ (defined recursively as well), $FCN\\_i({\\bf W}\\_i,x)=\\sigma\\_i(W\\_iFCN\\_{i-1}({\\bf W}\\_{i-1},x)+b\\_i)$.\nThen, setting ${\\bf z}=(x,y)$ a datum and  $h\\_i(x):=FCN\\_i({\\bf W}\\_{i},x)$ we can rewrite our loss as a function of $({\\bf W}\\_i,{\\bf z})$. \n\n**Lemma.** *Assume that all weight matrices of ${\\bf W}\\_i$ are bounded and that the activation functions are Lipschitz with constant bounded by $K\\_\\sigma$. Then for any datum ${\\bf z}=(x,y)$, any $i,{\\bf W}\\_i\\rightarrow\\ell({\\bf W\\_i},{\\bf z})$ is Lipschitz.*\n\n*Proof.* We consider the Frobenius norm on matrices as ${\\bf W}_2$ is a vector as we consider the L2-norm on the vector. We prove the result for $i=2$, assuming it is true for $i=1$. We then explain how this proof generalises the case $i=1$ and works recursively. Let ${\\bf z},{\\bf W}_2,{\\bf W}_2'$, for clarity we write $FCN_2(x):=FCN({\\bf W}_2,x)$ and $FCN_2'(x):=FCN({\\bf W}_2',x)$.  As $\\ell$ is $\\eta$-Lipschitz on the outputs $FCN_2(x), FCN_2'(x)$:\n\n$$|\\ell({\\bf W\\_2},{\\bf z})-\\ell({\\bf W'\\_2},{\\bf z})|$$\n$$\\le\\eta||FCN\\_2(x)-FCN\\_2'(x)||$$\n$$\\le\\eta||\\sigma\\_2(W\\_2FCN\\_{1}(x)+b\\_2)-\\sigma\\_2(W\\_2'FCN\\_{1}'(x)+b\\_2')||$$\n$$\\le\\eta K\\_\\sigma||W\\_2FCN\\_{1}(x)+b\\_2-W\\_2'FCN\\_{1}'(x)-b\\_2'||$$\n$$ \\le\\eta K\\_\\sigma( ||(W\\_2- W\\_2')FCN\\_{1}(x)||+||W\\_2'(FCN\\_{1}(x)-\\text{FCN\\}_{1}'(x))||+||b\\_2-b\\_2'||)$$\n    \nThen we have $||(W\\_2-W\\_2')FCN\\_1(x)||\\le||(W\\_2-W\\_2')||\\_F||FCN\\_1(x)|| \\le  K\\_x ||(W\\_2- W\\_2')||\\_F$. The second inequality holding as $FCN\\_1(x)$ is a continuous function of the weights. Indeed, as on a compact space, a continuous function reaches its maximum, then its norm is bounded by a certain $K\\_x$. Also, as the weights are bounded, any weight matrix has its norm bounded by a certain $K\\_{W}$ thus $||W\\_2'(FCN\\_1(x)FCN\\_1'(x)|| \\le ||W\\_2'||\\_F||(FCN\\_1(x)-FCN\\_1'(x)||\\le K\\_{W}||FCN\\_1(x)-FCN\\_1'(x)||$. Finally, taking $K\\_{temp}=\\eta K\\_\\sigma\\max(K\\_{x},K\\_W,1)$ gives: $$|\\ell({\\bf W\\_2},{\\bf z})-\\ell({\\bf W'\\_2},{\\bf z})|\\le K\\_{temp}(||(W\\_2-W\\_2')||\\_F+||b\\_2-b\\_2'||+||FCN\\_1(x)-FCN\\_1'(x)||).$$\n\nExploiting the recursive assumption that $FCN\\_1$ is Lipschitz with respect to its weights ${\\bf W}\\_1$ gives  $||FCN\\_1(x)-FCN\\_1'(x)||\\le K\\_1||{\\bf W}\\_1-{\\bf W}\\_1'||$. If we denote by $(W_2,b_2)$ the vector of all concatenated weights, notice that $||(W\\_2- W\\_2')||\\_F+||b\\_2-b\\_2'||=\\sqrt{(||(W\\_2-W\\_2')||\\_F+||b\\_2-b\\_2'||)^2}$$\\le\\sqrt{2(||(W\\_2-W\\_2')||\\_F^2+||b\\_2-b\\_2'||^2)}=\\sqrt{2}||(W_2,b_2)-(W_2',b_2')||$ (we used that for any real numbers $a,b,(a+b)^2\\le 2(a^2+b^2)$). We then have: $$|\\ell({\\bf W\\_2}, {\\bf z})-\\ell({\\bf W'\\_2},{\\bf z})|$$\n$$\\le K\\_{temp}\\max(\\sqrt{2},K\\_1)( ||(W\\_2,b\\_2)-(W\\_2',b\\_2')||+||{\\bf W}\\_1-{\\bf W}\\_1'||)$$\n$$\\le\\sqrt{2}K_{temp}\\max(\\sqrt{2},K_1)||{\\bf W}_2-{\\bf W}_2'||.$$\nThe last line holds by reusing the same calculation trick. This concludes the proof for $i=2$. For $i=1$, the same proof holds by replacing $W_2,b_2,FCN_2$ by $W_1,b_1,FCN_1$ and replacing $FCN_1(x), FCN_1'(x)$ by $x$ (we then do not need to assume a recursive Lipschitz behaviour). Then the result holds for $i=1$.\n    \nWe then apply a recursive argument at rank $i$ by assuming the result at rank $i-1$ reusing the same proof by replacing $W\\_2,b\\_2,FCN\\_2$ by $W\\_i,b\\_i,FCN\\_i$ and $FCN\\_1(x),FCN\\_1'(x)$ by $FCN\\_{i-1}(x),FCN\\_{i-1}'(x)$. This concludes the proof."}, {"review_id": "uS6gIpWtXL", "reviewer": "Reviewer_jPqk", "summary": "This paper focuses on studying PAC-Bayes generalization bounds based on the Wasserstein distance. It introduces novel high-probability bounds applicable to both batch learning (i.i.d. setting) and online learning (non-i.i.d. setting). Unlike previous PAC-Bayes bounds, their bounds are not limited to bounded or sub-Gaussian losses. Furthermore, leveraging their theoretical findings, the authors propose a new SRM training strategy and provide empirical evidence to validate its effectiveness.", "questions": "Major concerns:\n\n1. There might be a small error in Theorem 2: in the proof of Theorem 2 (Section B.2), you let $\\lambda_i=\\sqrt{\\frac{\\ln{(K/\\delta)}}{|S_i|}}$ in the last step (i.e. Line 636). However, this choice does not yield the desired $\\sum_{i=1}^K\\sqrt{\\frac{|S_i|\\ln{(K/\\delta)}}{m^2}}$ in your bound. If I understand correctly, you could consider setting $\\lambda_i=\\sqrt{\\frac{2\\ln{(K/\\delta)}}{|S_i|}}$, which would result in the last term in the bound becoming $\\sum_{i=1}^K\\sqrt{\\frac{2|S_i|\\ln{(K/\\delta)}}{m^2}}$. This may be the smallest achievable second term in Section B.2.\n\n2. In Line 206-207, you argue that Eq. (3) contains a trade-off parameter $\\lambda$, while Eq. (2) does not. However, it is worth noting that a similar parameter, $\\epsilon$, is also involved in your practical training objective, namely Eq. (5). Therefore, the argument regarding the presence of $\\lambda$ may not be entirely fair. Perhaps removing Line 206-207 could be considered?\n\n3. Have you considered incorporating the empirical variance term into your algorithm? Since you emphasize its reliance on the prior rather than the posterior, I would appreciate it if you could demonstrate some practical implications.\n\n4. Under the same conditions, such as bounded loss or even zero-one loss, is it possible to compare your Wasserstein-based PAC-Bayes bounds with the standard KL-based PAC-Bayes bounds, especially those that also include variance terms as mentioned in [1,2,3]?\n\nMinor comments:\n\n1. Line 131: there is a missing period after $S_K$.\n\n2. RHS of the equation on Line 633: $L{|S_i|}\\Longrightarrow L_{|S_i|}$.\n\n3. RHS of the equation on Line 635: $\\lambda [S_i|]\\Longrightarrow \\lambda |S_i|$.\n\n[1] Seldin, Yevgeny, et al. \"PAC-Bayesian inequalities for martingales.\" IEEE Transactions on Information Theory 58.12 (2012): 7086-7093.\n\n[2] Tolstikhin, Ilya O., and Yevgeny Seldin. \"PAC-Bayes-empirical-Bernstein inequality.\" NeurIPS 2013.\n\n[3] Mhammedi, Zakaria, Peter Grünwald, and Benjamin Guedj. \"PAC-Bayes un-expected Bernstein inequality.\" NeurIPS 2019.", "limitations": "There is no potential negative societal impact.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "Compared to previous results, the Wasserstein-distance PAC-Bayes bounds presented in this paper require fewer or weaker assumptions. Additionally, unlike previous PAC-Bayes bounds that typically invoke Gaussian distributions, their bounds accommodate discrete Dirac distributions for both the prior and posterior distributions.", "weaknesses": "Regarding the Wasserstein regularization part, it might be necessary to empirically compare it with similar styles of regularization, such as weight decay $||w||$ and the 'distance to initialization' $||w-w_0||$. Although I believe that a data-dependent prior will provide a tighter bound, it is uncertain whether the data-dependent prior can significantly outperform a data-independent prior (e.g., $0, w_0$) considering the significantly increased computational time required.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your careful review, and we answer your concerns below.\n\n**Weaknesses**\n\nAs noted in the general answer, the 'distance to initialisation' is a particular case of our Eq. (5) when $K=1$. This particular case has been plotted in Table 3 of Appendix C.4. More precisely, this table shows that, on most of the datasets, considering data-dependent priors leads to sharper results. This shows the efficiency of our method compared to the 'distance to initialisation' regularisation. Furthermore, we ran a novel experiment with the weight decay generalisation which is gathered in the pdf document updated with the rebuttal. This experiment shows concretely that on a few datasets (namely SENSORLESS, YEAST), when our predictors are neural networks, the weight decay regularisation fails to learn while our method succeeds, as shown in Tables 1 (of our work) and 4 (of the new pdf). More generally, weight decay regularisation outperforms our method 3 times over 11 for batch learning with neural nets.\n\nWe hope the experiments and the analysis address your concerns.\n\n**Major concerns**\n1. Thank you for spotting this, you are actually right. Our choice of $\\lambda$ was not correct, while yours is. We will correct it in the next version of the document. \n\n2. Thank you again; this remark is indeed unfair. After looking at our practical optimisation procedure, we will remove those two lines. \n    \n3. According to our theoretical bounds, it is legitimate to incorporate the empirical variance term when considering a heavy-tailed loss that takes value in all $\\mathbb{R}$. This situation is in line, for instance, with reinforcement learning with heavy-tailed rewards, as noticed in line 155. However, we proved in Theorems 2 and 4 that if the loss is nonnegative, then the empirical variance does not intervene in the bound. Thus, as our optimisation goal is driven by the theory, it does not seem relevant to us to incorporate such an empirical variance in a classification problem. However, in order to provide a concrete situation where order 2 moments on the prior only have a positive influence (rather than on the pair prior/posterior) we propose the following example. \n\nAssume that order 2 moments of the prior *and all considered posteriors* have to be uniformly bounded by a certain $C$.\nLet the data distribution of a point $z$ to admit only a finite variance and consider the loss $\\ell(h,z)= |h-z|$ where both $h,z$ lie in the real axis. Then, assuming $\\mathbb{E}[z^2]\\le V$, then by Cauchy Schwarz, we have  $\\mathbb{E}[\\ell(h,z)^2] \\le \\mathbb{E}[h^2] + 2V\\mathbb{E}[|h|] +V^2 \\le C$, the last inequality being our assumption. Then, this invites us to consider posterior distributions with first and second moments satisfying the previous inequality, which is restrictive. On the contrary, assuming only such an assumption on the prior distribution, we are allowed to move freely on the space of distribution to find the best posterior. \nWe thank you for asking for more details, as this short example will improve the next version of our manuscript. \n\n4. We provide below further elements of comparison between [1,2,3] and our results, beyond the fact that we used the Wasserstein distance instead of KL divergence. \n\nThe bounds of [1] are PAC-Bayes bounds for martingales, we focus on their Theorem 4 which controls an average of martingales, similarly to our Thm 1. Under a boundedness assumption, they recover a McAllester-typed bound while Thm 1 is more of a Catoni-typed result. Also, their Theorem 7 is a Catoni-typed bound involving a conditional variance, similar to our Theorem 4. However, they require to bound uniformly the variance on all the predictor sets, which is more restrictive than the assumption of bounding the averaged variance with respect to priors, which is what we required to perform Theorem 4.\n\nThe bounds of [2] have been obtained for bounded loss functions and iid data; this allows us to exploit techniques involving the 'small' kl divergence between two Bernoulli r.v. Thus, their bounds have been obtained through a certain lower bound on this kl term. Their main result (Theorem 4) contains a term of variance times a KL divergence, exhibiting an interaction between those two quantities. On the contrary, our bounds decoupled the influence of the empirical variance from the one from the complexity term (i.e., the Wasserstein distance). The major advantage to this is that we do not have to assume a constraint on our choice of posterior, such as the assumption below Eq. (7) in [2]. This allows our learning algorithms to move freely in the space of distributions to find our posterior. \n\nThe bounds of [3] are a continuation of [2] as they provide tighter PAC-Bayes Bernstein inequalities. However, we notice that the involved technical toolbox is closer to ours as they widely used Exponential Stochastic Inequalities (ESI). Indeed, our supermartingale toolbox can be seen as a carefully designed ESI. However, their results remain valid for bounded losses and i.i.d data, which remains more restrictive than our assumptions.\n\nWe hope this clarifies your concerns and are happy to respond to any additional questions."}]

Author rebuttal:
We warmly thank all reviewers for their insightful reviews of our work. We are encouraged to see that our work generated enthusiasm and we answer thoroughly to all of the concerns raised by the reviewers. We address, in this general response, remarks raised by at least two reviewers.


**New experiments to study ERM with classical regularisation methods.** 

Additional experiments have been asked by reviewers jPqk and tL5n to see the performance of classical regularisation methods such as the 'distance to initialisation' $||\mathbf{w}-\mathbf{w}\_0||$ and the weight decay $||\mathbf{w}||$. We point out that the first is a particular case of Algorithm 1 when $K=1$ (i.e., we treat the data as a single batch, and the prior is the data-free initialisation); the results are in Table 3 of Appendix C.4. More precisely, this table shows that, on most of the datasets, considering data-dependent priors leads to sharper results. This shows the efficiency of our method compared to the 'distance to initialisation' regularisation. Furthermore, we ran experiments with the weight decay regularisation which is gathered in the pdf document updated with the rebuttal. 
This experiment demonstrates that on a few datasets (namely SENSORLESS and YEAST) when our predictors are neural nets, the weight decay regularisation fails to learn while ours succeeds as shown in Tables 1 (of our work) and 4 (of the new pdf).
More generally, the weight decay regularisation outperforms our method 3 times over 11 for batch learning with neural nets.

 **Clarity of Section 4.1** 

Several comments have pointed out the lack of clarity in the first paragraphs of Section 4.1. We worked on the following points that will appear in the revised version of the paper:
    
1. We move the second paragraph of the 'Batch algorithm' part before Eq. (5). This makes the loss function we introduced appear more clearly, as suggested by Rev. tL5n. 

2. Also, when our predictor space $\mathcal{H}$ is parametrised over $\mathbb{R}^D$ (for a certain $D>0$) equipped with the Euclidean distance $||.||$, we clearly define the distance $d$ between two predictors $h\_{\mathbf{w}},h\_{\mathbf{w}'}\in \mathcal{H}^2$ to be $d(h\_{\mathbf{w}},h\_{\mathbf{w}'})= ||\mathbf{w}-\mathbf{w}'||$. In Eq. (5), we also replace $||\mathbf{w}-\mathbf{w}\_i||$ by $d(h\_{\mathbf{w}},h\_{\mathbf{w}\_i})$ for the sake of consistency. This might clarify the concern of Rev. mMbV on how this Euclidean distance appeared in Eqs. (5),(6),(7) but raises the question of whether our losses are Lipschitz with regard to $\mathbf{w}$ and not $h_{\mathbf{w}}$. As Lemma 8 provided a positive answer for the linear model, we provided a supplementary lemma (with its proof) stating that our neural networks, as long as the weights are clipped (with an arbitrarily high constant), are Lipschitz with respect to their weight, explaining why our learning procedure is consistent with our theorems. As we considered a high value of the clipping, it did not interfere with our optimisation procedure. Those points will be clearly stated in the next version.

Again, we thank the reviewers for their work and hope this, as well as individual responses, clarifies all existing concerns.



Meta-review: The paper introduces PAC-Bayesian learning with Wasserstein distance replacing the KL divergence in the metric space of hypotheses, presenting results for both batch and online learning scenarios. The generalization bounds are derived based on the Wasserstein distance between posterior and prior distributions over hypotheses, and the Lipschitz constant of the loss function. These bounds are applicable to heavy-tailed loss functions with bounded 2nd moments, and experiments with linear and neural network models demonstrate improved generalization compared to ERM and OGD on various datasets. Some weaknesses include variability in model performance based on batch size, and the need for further discussion on performance disparities between algorithms. The referees suggested reorganizing the paper.
Decision: Accept (poster)