PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingales
Authors: Maxime Haddouche
Benjamin Guedj
Venue: Accepted by TMLR ()

Abstract: While PAC-Bayes is now an established learning framework for light-tailed losses (\emph{e.g.}, subgaussian or subexponential), its extension to the case of heavy-tailed losses remains largely uncharted and has attracted a growing interest in recent years. We contribute PAC-Bayes generalisation bounds for heavy-tailed losses under the sole assumption of bounded variance of the loss function. Under that assumption, we extend previous results from \citet{kuzborskij2019efron}. Our key technical contribution is exploiting an extention of Markov's inequality for supermartingales. Our proof technique unifies and extends different PAC-Bayesian frameworks by providing bounds for unbounded martingales as well as bounds for batch and online learning with heavy-tailed losses.

Published in Transactions on Machine Learning Research (04/2023)
PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingales
Maxime Haddouche
maziinechaadooncce@@@iiii..
Inria, University College London and Université de Lille
Benjamin Guedj
Inria and University College London
Reviewed on OpenReview: https: // openreview. net/ forun? id- garut6F3sf
Abstract
While PAC-Bayes now established learning framework for light-tailed losses (e.g., sub- gaussian subexponential), its extension to the case of heavy-tailed losses remains largely uncharted and has attracted growing interest in recent years. We contribute PAC-Bayes generalisation bounds for heavy-tailed losses under the sole assumption of bounded variance of the loss function. Under that assumption, we extend previous results from Kuzborskij and Szepesvári (2019). Our key technical contribution is exploiting an exlention of Markov's 's inequality for supermartingales. Our proof technique unifies and extends different PAC- Bayesian frameworks by providing bounds for unbounded martingales well as bounds for batch and online learning with heavy-tailed losses.
1 Introduction
PAC-Bayes learning is a branch of statistical learning theory aiming to produce (tight) generalisation guar- antecs for learning algorithms, and byproduct leads to designing efficient learning procedures by minimising such guaranlees. Generalisation bounds are helpful for understanding how learning algorithm may perform on future similar batches of data. Since its emergence in the late 1990s, PAC-Bayes theory (see the seminal works of Shawc-Taylor and Williamson, 1997; McAllestor, 1998; 1999; 2003; Catoni, 2003; 2007) has revealed powerful enough to explain the generalisation abilities of learning algorithums which output distributions over the predictors space (a particular case being when the output Dirac mass on a single predictor) from which our predictors of interest are designed. We refer to the recent surveys from Guedj (2019); Alquier (2021) for overview PAC-Bayes.
At first, PAC-Bayes theory was mainly focused on classification tasks (see Seeger, 2002; Langford and Schapire, 2005; Catoni, 2007) but has quickly been generalised to any bounded loss function in regression (see e.g., Maurer, 2004; Germain et al., 2009; 2016). PAC- learning covers a broad scope of domains and tools, from information theory (Kakade et al., 2008; Wu and Seldin, 2022) to statistical learning (Catoni, 2003; 2007), convex optimisation (Thiemann al., 2017), Bernstein-type concentration incqualities (Tolstikhin and Seldin, 2013; Mhammedi et al., 2019), margins (Biggs and Guedj, 2022a; Biggs et al., 2022) and martingales (Seldin et al., 2011; 2012a;b), to name but few.
From practical perspective, the above led to generalisations guarantees for PAC-Bayes-inppieee neural networks (NN): a promising line of work initiated by Dziugaite and Roy (2017) and pursued further by Letarte et al. (2019); Rivasplata et al. (2019); Pérez-Ortiz et al. (2021); Biggs and Guedj (2021); Perez- Ortiz al. (2021a;b); Biggs and Guedj (2022b), among others, established NN architectures enjoying tight generalisation guarantees, turning PAC-Bayes into a powerful tool handle complex neural structures (c.g.. Chérief-Abdellathe et al., 2022).

---

Published in Transactions on Machine Learning Research (04/2023)
These encouraging breakthroughs gave rise to several initiatives to extend PAC-Bayer beyond the bounded losses assumption which is limiting in practice. Indeed, the goal is to make PAC-Bayes able to provide efficiency guarantees to any learning algorithm attached to a loss function. For instance, consider a NN trained to solve regression problems without constraints on the training domain. Several works already proposed roules lo overcome the boundedness constraint: Catoni (2004, Chapter 5) already proposed PAC- Bayes bounds for the classification tasks and regressions ones with quadratic loss under a subexponential assumption. This technique has later been exploited in Alquier and Biau (2013) for the single-index model, and by Guedj and Alquier (2013) for nonparametric sparse additive regression, both under the assumption that the noise is subexponential. However all these works are dealing with light-tailed losses. Alquier and Guedj (2018); Holland (2019); Kuzborskij and Szepesvári (2019); Haddouche et al. (2021) proposed extensions beyond light-tailed losses. Our work stands in the continuation ion of this spirit while developing and exploiting a novel technical toolbox. To better highlight the novelty of our approach, we first present the two classical building blocks of PAC-Bayes.
1.1 Understanding PAC-Bayes: a celebrated route of proof
1.1.1 Two essential building blocks for preliminary bound
In PAC-Bayes, typically assumne access to non-negative loss function ((h,z) taking argument predictor & E H and data E 2 (think of as pair input-output (a, y) for supervised learning problems, or as a single datum x in unsupervised learning). We also assume access to a m-sized sample S = (21, =m) E 2.m of data on which we will learn a meaningful posterior distribution Q on H, from a prior P (or reference measure see e.g., Guedj, 2019 for a discussion on the terminology of probability distributions in PAC-Bayes).
To do so, PAC-Bayesian proofs are built upon two cornerstones. The first one is the change of measure incquality (Csiszár, 1975; Donsker and Varadhan, 1975; Dupuis and Ellis, 2011 also Banerjec, 2006; Guedj, 2019 for proof).
Lemma 1.1 (Change of measure inequality). For any measurable function vb H + R and any distributions Q, P on H:
= KL( + log (En=p(exp(((()))
with KT, denoting the Kullback- Leihler divergence.
The change of measure inequality is then applied to certain function fm 2 x H - R of the data and candidate predictor: for all posteriors Q,
En-olsm (S, A)] S KL(Q, P) + log (Bn=-(eex((/m,
(1)
To deal with the random variable X(S) == En (aex:e/eemmmmss 1))], our second building block is Markov's incquality (P(X > a) B(X]) which we apply for fixed Ej0, 1[ on X(S) with Es[X(S)]/6. Taking
the complementary event gives that for any m, with probability at least - 5 over the sample S, X(S) < [S))(8) thus:
En-Q(fm S KL(Q, log(1//) - log (BA-
(2)
1.1.2 From preliminary to complete bounds
From the preliminary result of Eq. (2), there exists several ways to obtain PAC-Bayesian generalisation bounds, all being tied to specific choices of ff and the assumptions on the datasct S. However they all rely on the control of an exponential moment implied by Markov's inequality: this is a strong constraint which has been at the heart of the classical assumption appearing in PAC-Bayes learning. For instance, the celebrated result of McAllester (1999), tightened by Maurer (2004), exploits in particular, data-frec prior, an jid assumption on and a light-tailed loss function. Most of the existing results stand with those assumptions (see e-g.; Catoni, 2007; Germain et al., 2009; Guedj and Alquier, 2013; Tolstikhin and Seldin,
2

---

Published in Transactions on Machine Learning Research (04/2023)
2013; Guedj and Robbiano, 2018; Mhammedi et al., 2019; Wu and Seldin, 2022). Indeed, in many of these works, boundedness assumption the loss is used but in many cases, it can be relaxed to subgaussiannity without loss of generality. Catoni (2004) extended PAC-Bayes learning to the subexponential case. Many works tried to mitigate at least one of the following three assumptions.
Data-free priors. With an alternative set of techniques, Catoni (2007) obtained bounds with localised (i.e., data-dependent) priors. More recently, Lever et al. (2010); Parrado- et al. (2012); Lever et al. (2013); Oneto et al. (2016); Dziugaite and Roy (2017); Mhammedi et al. (2019) also obtained PAC-Bayes bound with data-dependent priors.
The iid assumption on S. The work of Fard and Pincau (2010) established links between rein- forcement. learning and PAC-Bayes theory. This naturally led to the study of PAC-Bayesian bound for martingales instead of iid data (Seldin al., 2011; 2012a:b).
Light-tailed loss. PAC-Bayes bounds for heavy-tailed losses (f.., without subgaussian or subex- ponential assumptions) have been studied. Audibert and Catoni (2011) provide PAC-Bayes bounds for least square estimators with heavy-tailed random variables. Their results was suboptimal with respect to the intrinsic dimension and was followed by further works from Catoni and Giulini (2017) and Catoni (2018). More recently, this question has been adressed in the works of Alquier and Guedj (2018); Holland (2019); Kuzborskij and Szepesvári (2019); Haddouche et al. (2021), extending PAC- Bayes to heavy-tailed losses under additional technical assumptions.
Several questions then legitimately arise.
Can we avoid these three assumptions simultaneously? The answer is yes: for instance the work of Rivasplata et al. (2020) proposed a preliminary PAC-Bayes bound holding with none of the three assump- tions listed above. Building on their theorem, Haddouche and Guedj (2022) only exploited a bounded loss assumption to derive a PAC-Bayesian framework for online learning, requiring no assumption on data and allowing data, (history in their context)-dependdnt priors.
Can we obtain PAC-Bayes bounds without the change of measure inequality? Yes, for instance Alquier and Guedj (2018) proposed PAC-Bayes bounds involving f-divergences and exploiting Holder's inequality instead of Lemma 1.1. More recently, Picard-Weibel and Guedj (2022) developed a broader discussion about generalising the change of mcasure inequality for wide range of f-divergences. We note also that Germain et al. (2009) proposed version of the classical route of proof stated above avoiding the use of the change of mcasure incquality. This comes at the cost of additional tochnical assumptions (sce Haddouche et al., 2021, Theorem for a statement of the theorem in proper measure-theoretie framework).
Can we avoid Markov's inequality? We mentioned above that several works avoided the change of measure inequality to obtain PAC-Bayesian bounds, but can we do the same with Markov's inequality? This point interesting as avoiding Markov allow us to avoid assumptions such as aab-gaussiannity to provide PAC-Bayes bound. The answer is yes but this is rare breed. To the best of our knowledge, only two papers are explicitly not using Markov's inequality: Kakade et al. (2008) obtained PAC-Bayes bound using results on Rademacher complexity based on the McDiarmid concentration inequality, and Kuzborskij and Szepesvári (2019) exploited a concentration inequality from De la Peña et al. (2009), up to a technical assumptions to obtain results for unbounded losses. Both of this works did not required a bound on an exponential moment to hold.
1.2 Originality of our approach
Avoiding Markov's inequality appears challenging in PAC-Bayes but leads to fruitful results as those in Kuzborskij and Szepesvári (2019).
In this work, we exploit generalisation of Markov's inequality for supermartingales: Ville's inequality (as noticed by Doob 1939). This result has, to knowledge, never been used in PAC-Bayes before.
3

---

Published in Transactions on Machine Learning Research (04/2023)
Lemma 1.2 (Ville's maximal inequality for supermartingales). Let (Ft) be filtration and (Zt) non- negalive muper-marlingale salisfying Zo = a.s. If 74 is adapted to Ft and B. [e Ft S 7 a.8., 1 1, then, for any 0 < 8 < 1, it holds
(eT 2 1: Zr > 5-14-51 5-1) 5
Proof. We apply the optional stopping theorem (Durrctt, 2019, Thm 4.8.4) with Markov's incquality defining Z > }-1) so that
the slopping time = in >
P(3 2 5-1) = =
A major interest of Ville's result that holds for a countable sequence of random variables simultaneously, This point new PAC-Bayes as will allow us obtain bounds holding for a countable (not necessarily finite) dataset S = (z))21
To fully exploit Lemma 1.2, we now take countable dataset S = (2))21 nm. Recall that, because use the change of measure inequality, we have to deal with the following exponential random variable appearing in Eq. (1) for any m 2 1:
On which supermartingale do apply Ville's bound ?
2m = Enw-lexp([(mmmee (S, (S,4))]
Our goal choose sequence of functions Sm such that (7 is a supermartingale. A way to do so comes from Bereu and Tonati (2008).
Lemma 1.3. Let (Mm) be a locally equare-integrabe martingale with respect to the filtration (Fm). For all 7) R and 2 0, one has:
E exp Am " (A[M) + A(M)m)) |Fm- S1,
where AMm. Mm Mm-1 A|M AM and A(M) = -E |AM I Jm-1).
We define (n) exp (n 10mm- "" (I + mM) Then, for all n R. (V,(m)) is positive super- martingale with E (n) S where [M (h) = Em A[M (t)
= Em AMM)
In the sequel, this lemma will be helpful design supermartingale (f.e., to choose relevant fm for any m) without further assumption.
1.3 Contributions and outline
By avoiding Markov, key message of (Kuzborskij and Szepesvári, 2019) that, for learning problems with independent data, PAC-Bayes learning only requires the control of order 2 moment losses to be used with convergence guarantees. This is strictly less restrictive than the classical subgaussian/subaamnn. assumptions appearing in the major part of the literature.
We successfully prove this fact remains even for non-independent data: we only need to control order 2 (con- ditional) moments to perform PAC-Bayes learning. Furthermore, our proof technique general enough encompass two different PAC-Bayesian framework: PAC-Bayes for martingales (Seldin et al., 2011; 2012a;b) and Online PAC-Bayes learning (Haddouche and Guodj, 2022). Thus, main contributions are twofold.
We provide novel PAC-Bayesian bound holding for data-free priors and unbounded martingales. From this, we recover in PAC-Bayes bounds for unbounded losses and iid data significant particular case.
We extend the Online PAC-Bayes framework of Haddouche and Guedj (2022) the case of un- bounded losses.
4

---

Published in Transactions on Machine Learning Research (04/2023)
More precisely, Sec. 2.1 contains our novel PAC-Bayes bound for unbounded martingales and Sec. 2.3 con- tains immediate corollary for learning theory with iid data. Our second contribution lies in Sec. 3 and extend Online PAC-Bayes theory to the case of unbounded losses. We eventually apply our main result for martingalos in Sec. to the setting of multi-armed bandit. Doing so, we provably extend a result of Seldin et al. (2012a) to the case of unbounded rewards.
Appendix A gathers more details on PAC-Bayes, we draw in Appendix B detailed comparison between our new results and few classical ones. We show that adapting our bounds to the assumptions made in those papers allows to recover similar improved bounds. We defer to Appendix C the proofs of Secs. 2.3 and 4.
2
A
bound for unbounded martingales
2.1 Main result
A line of work led by Seldin et al. (2011; 2012a;b) provided PAC-Bayes bounds for almost surely bounded martingales. We provably extend the remits of their result to the case of unbounded martingales.
Framework Our framework is close to the one of Seldin et al. (2012a): we assume having access to a countable dataset S = (z))211 with no restriction on the distribution of S (in particular the 2 can depend on each others). We denote for any m, Sm == (zi)i=1..mm the restriction of S to its m first points. (3i) is a filtration adapted to S. We denote for any i E N E,-I[-= == B[. Fi-1]. We also precise the space H to be an index (or a hypothesis) space, possibly uncountably infinite. Let (X1 h), X2(S2, ... : h E H) be martingale difference sequences, meaning that for any m 2 1, E H, Em [mm (Sm. h)] =0
For any E H, let Mm(h) En X,(S,,) be martingales corresponding to the martingale difference sequences and define, as in Bercu and Touati (2008), the following
[M]m(h)= X,(S,,,)²
m2
(M) (h) Σ E,-1 hS)
For a distribution Q over H define weighted averages of the martingales with respect to Q as Mm En~q [h)] (similar definitions hold for [M)((Q), (M),(Q)).
Main result. We now present the main result of this section where we succesfully avoid the boundedness assumption on martingales. This relaxation comes at the cost of additional variance terms [M]ms (M)m-
Theorem 2.1. For any fata-free prior P E MT (H), any À > O, any collection of martingales (Mm (h)) m1)) indered by h E H. the following holds with probability 1 - 5 over the sample S = (zi)ee,, for all m E N/(0), Q E Mt (9C):
[M (Q)) KL(Q,P) + log(2/0)
(MM),)
X
Proof lies in Sec. 2.2.
Analysis of the bound. This thoorem involves several terms. The change of mcasure incquality introduces the KL divergence term, the approximation term log(2/5) comes from Ville's inequality (instead of Markov in classical PAC-Bayes). Finally, the terms [M] mn (Q), (M) (Q) come from our choice of supermartingale as suggested by Bercu and Touati (2008). The term [M]((Q (Q) can be interpreted as an empirical variance term while (M)..Q) (Q) is its theoretical counterpart. Note that (M)m (Q) also appears in Seldin et al. (2012a, Theorem 1).
We recall that this general result stands with no assumption on the martingale difference sequence (X))22 and holds uniformly on all m 2 1. Those two points are, to the best of our knowledge, new within the PAC-Bayes literature. We discuss in Sec. 2.3 and Appendix B more concrete instantiations.
5

---

Published in Transactions on Machine Learning Research (04/2023)
Comparison with literature. The closest result from Thm. 2.1 is the PAC-Bayes Bernstein inequality of Seldin et al. (2012a). Our bound is natural extension of theirs as their result only involves the variance term (not the empirical one), but requires two additional assumptions:
1. Bounded variations of the martingale difference sequence: Vm, Fm R such that a.s. for all h [Sm, hi] Cm-
Restriction on the range of the x: Vm, Am S 1/Cm-
Seldin et al. (2012a) need those assumptions to ensure the Bernstein assumplion which states that for any h, E)exp(AM,, (h) X² (M)m())) s 1. Our proof technique do not require the Bernstein assump- tion (and so none of the conditions described above, which allow us deal with unbounded martin- gales)
exploit the supermartingale structure to obtain results. More precisely, the price to pay to avoid the Bernstein assumption is to consider the empirical variance term [M) and to prove that
is supermartingale using Lemma 1.2 and Lemma 1.3 (see Sec. 2.2 for the complete proof). A broader discussion is detailed in Appendix B.
(exp (AMm- - X ([M] + (M)m)) m>1
2.2 Proof of Thm. 2.1
Proof. We fix n) E R and we consider the function fm to be for all (S, h):
fm(S,h) = :- (M))(()))))))))))))))))))) n)2 ([Mm(h) + (M)m())
= Σ AMM()) "2 of (A
m
-
where (M, X,(S,,), ([M)(()) = X, h)², (M E,- (s,S,, h)3]. For the sake of clarily, we dropped the dependency in S of Mm. Note that, given the definition of Mm, Mm(h) is Fm measurable for any fixed h.
Let P fixed data-free prior, we first apply the change of mcasure incquality to obtain Vm N, QQ Mc
En~Qlfm(S,h) KI(Q,P) log En~P (exp(fm(ss
:=2m
with the convention fo = We now have show that (Zm)m is a supermartingale with Zo 1. To do remark that for any m, because P is data free one has the following result.
Lemma 2.2. For any data-free prior P, any olaleerra F belonging to the filtration (Ft)s20, any nonnegative function laking as argument the sample S and a prediclor h one has almost surely:
E B [f(, [1 Ex-r [[f(S,h) [J].
Proof. Let A be F-measurable event. We want to show that
E [B E EAPP E[f(S,)) 91] LA],
where the first expectation in each term taken over Note that it possible to take this expectation thanks to the Kolomogorov's extension theorem (see e.g. Tao, 2011, Thm 2.4.4) which ensure the existence of probability space for the discrete-time stochastic process S (2))21
Thus, this is enough to conclude that
E B [[(,
|
En- [S[ FF),

---

Published in Transactions on Machine Learning Research (04/2023)
by definition of the conditional expectation. To do so, notice that because f(S, is nonnegative function, and that P is data-free, we can apply the classical Fubini-Tonelli theorem.
E (S (S) En-r [R (f(S,)) A)]
One now conditions by F and use the fact that A F-measurable:
EB-P (B [3]] [A]]
We finally re-apply Fubini-Tonelli to re-intervert the expectations:
E E (f((sh) 99 LA]]
This concludes the proof of Lemma 2.2.
We then use Lemma 2.2 with f exp(fm) and T = Jm-1 to obtain:
Em-1lZml = -ENP [ex=I(exp((m(S.
ERNP exp(fm ex n2 _ (A ((
with fm-1(5,h) = EEET - (AM (h))). Using Lemma 1.3 ensures that for any h.
(
Bm Bm-1eepp7AAMm.. - 71²
[ (h) 4 (h)) 1
thus we have
Em- [Zm] S Ep-P (exp(fm- Zm-11
Thus (Zm)m is nonnegative supermartingale with Zp = 1. We can use Ville's inequality (Lemma 1.2) which stales that
Ps (3m 2 1: Zm > >8-1 5
Thus, with probability 1 - 8 over S, for all m N, 7m S 1/8. We then have the following intermediary
result. For all P data-free prior, I, with probability 1 - over S, for all 0, Q E MT(())
?
(Q) < KL(Q.
P) log(1/))+++++1
2 (M + (Q)))
(3)
recalling that (Q) = En~ol Mn, (h)], and that similar definitons hold for (M](() (M) (Q). Thus, applying the bound with y) = () > 0) and laking an union bound gives, with probability å over S
for any m N, Q E Mt (3C)
X² A MM (Q) KL P) log(2/0) (IM (M) (Q)))
Dividing by À concludes the proof.
2.3 A corollary: Batch learning with iid data and unbounded losses
In this section, we instantiate Thm. 2.1 onto learning theory framework with iid data. We show that our bound encompasses several results of literature as particular cases.
Framework We consider a learning problem specified by a tuple (Jt, 2, E) consisting of a set H of predictors, the data space 2, and loss function f: I: 2 I We consider a countable dataset (2))21 E 2 and assume that sequence is iid following the distribution μ. We also denote by Mt (JC is the set of probabilities H.

---

Published in Transactions on Machine Learning Research (04/2023)
The generolisation error R. of predictor h E H is wh, R(h) Ez-ul[(h,,]], the empir- ical error of h is Yh, (h) mu E f(h, zi] and finally the quadralic generalisation ervor V of h is Wh, Q = [x-nh 2)²]. We also denote by generalisation gap for any h the quantity [R(h) - Rm (h)).
Definitions
Main result.. We now state the main result of this section. This bound is a corollary of Thm. 2.1 and fills the gap with learning theory.
Theorem 2.3. For any data-free prior P E MI (30), any X > 0 the following holds with probability over the sample S (zi)iets for all m E N/(0), Q E (FC
A 2m
A KL(Q, P) + log(2/6) -EhnolQuad(
[n-o[[(h)]] < 1n~Q (1)( +
E(h, 2i)²
+
-
Am
Proof is furnished in Appendix C.
About the choice of X. A novelty this theorem is that the bound holds simullaneously on all m > this is due the use of Ville's inequality. This sheds a new light on the choice of X. Indeed, taking a localised \ depending on given sample size (e.g. Am 1/ym) ensures convergence guarantces for the expected generalisation gap. Doing so, our bound matches the usual PAC-Bayes literature (i.e. a bound holding with high probability for a single m). However the novelty brought by Thm. 2.3 is that our bound holds for unbounded losses for all times simultaneously. This suggests that taking a sample size-dependent À may not be the best answer. We detail an instance of this fact below when one thinks of À as a parameter of an optimisation objective. Indeed, our bound suggests a new optimisation objective for unbounded losses which is for any m >> O:
((h,2)) + - E(h, ((,,2))))
KT(Q, Am
argmino
Enn
(4)
Eq. (4) differs from the classical objective of Catoni (2007, Thm 1.2.6) on the additional quadratic term (h, 23).. Note that this objective implies a bound on the theoretical order 2 moment to be meaningful as we do not include it in our objective. Note that this constraint is less restrictive than Catoni's objective which requires a bounded loss. This objective stresses the role of the parameter as being involved in new explicit tradcoff between the KL term and the efficiency on training data.
Also, this optimisation objective is valid for any sample size m, this means that our should not depend on certain dataset size but should be fixed in order to ensure learning algorithm with generalisation guarantees at all time. This draws a parallel with Stochastic Gradient Descont with fixed Icarning step.
A bout the underlying assumptions in this bound. Our result is empirical (all terms can be computer or approxinated) at the exception of the term En En (Quad(h)]. This invites to choose carefully the class of posteriors, in order to bound this sccond-order moment with minimal assumptions. For instance, if we consider the particular case of the quadratic loss E(h, 2) (h-z)?, then we only need to assume that our data have finite variance if we restrict our posteriors to have both bounded means and variance. This assumption is stricity less restrictive than the classical brngaussiannsuuaaaaaan assumption classically appearing in the literature.
Comparison with literature. Back to the bounded case, we note that instantiating the boundedness assumption in Thm. 2.3 make us recover the result of Alquier et al. (2016, Theorem 4.1) for the subgaussian case. We also remark that instantiating the HYPE condition conditioning Haddouche et al. (2021, Theorem 3) allow us to improve their result we transformed the control of an exponential moment into one a sccond-order moment. More details are gathered in Appendix B. We also compare Thm. 2.3 to Kuzborskij and Szepesvári (2019, Theorem 3) which is a PAC-Bayes bound for unbounded losses obtained through a concentration inequality from De la Peña et al. (2009). They arrived to what they denote as semi- empirical incqualities which also involve empirical and thcoretical variance terms (and not an exponential moment). Their Their bound holds for independent data and a single posterior. First of all, note that Thm. 2.3 holds for any posterior, which is strictly more general. Note also that our bound is forwadd corollary
8

---

Published in Transactions on Machine Learning Research (04/2023)
of Thm. 2.1 which holds for any martingale (thus for any data distribution in learning theory framework) and so, exploits different toolbox than Kuzborskij and Szepesvári (2019) (control of supermartingale vs. concentration bounds for independent data). We insist that a fundamental novelty in our work is to extend the conclusion of Kuzborskij and Szepesvári (2019) to the case of non-independent data: it possible to perform PAC-Bayes learning for unbounded losses at the expense of the control of second-order moments. Note also that their bound slightly tighter than ours as their result is Thm. 2.3 being optimised in À (which is something we cannot do as the resulting would be data-dependent).
3 Online PAC-Bayes learning with unbounded losses
Recently, an online learning framework has been designed Haddouche and Guedj (2022). This allowed the design of Online PAC-Bayes (OPB) algorithms which involved the use of history-dependent priors evolving at cach time step of the learning procodure. The main contribution of this section is OPB bound valid for unbounded losses.
Framework We consider the same framework as in Sec. 2.3 except we do not make any assumption the data distribution. Our goal is now to define posterior sequence (Qi)s21 from a prior sequence (Pi)z21 We also define a filtration (Fi) adapted to (z:)21- We reuse the following definitions extracted from Haddouche and Guedj (2022).
Definitions For all i, we denote by E,[-] the conditional expectation [/).
2 A stochastic kernel from U m 2 to H defined as a mapping Q - x Exc + [0, 1] where (i) For any
B Egc, the function S - QS, B) measurable, (ii) For any S, the function B - QS, , B) is a probability measure over H.
We also say that sequence of stochastic kernels (Pt)s21 is an online predictive sequence if (1) for all 2 1, E 2m P P:(,,.) is F;-1 measurable and (ii) for all 2 2, P.(S..) > Pi (S,.).
Main result. We now state the main theorem this section, which extends the remits of the Online PAC-Bayes framework to the case of unbounded losses.
Theorem 3.1. For any distribulion over the (countable) datasel S, anay >> O and any online predictive sequence (used as priors) (P:)i21, we have with probability at least 1-5 over the sample S ~ ,u the following, holding for the data- dela-dependent measures p., == P.(S..) any posterior sequence (Qi)i21 and any 2 1:
E BRnqQ [B(((h;, F(-1]] S _
En [R(hs; 2:)] + Σ 1=1
B Bh [P((hs, + vo(ha))
1=1
KT(QQ)IPP.s) + A
log(1/5)
With for all i, Vi 2)) (e(hy, ((1,,,))))--((((. 2))1)² (h,, =)] is the true conditional variance.
the empirical variance at time i and Vi(h.)
Proof lies See. 3.1.
Analysis of the bound. This bound is, to our knowledge, the first Online PAC-Bayes bound in literature holding for unbounded losses. It is semi-empirical as the variance and empirical variance terms have theo- retical components. However, these terms can be controlled with assumptions on conditional socond-order moments and not on exponential ones (as made in Haddouche and Guedj, 2022 where the bounded loss as- sumption was used to obtain conditional subgaussianity). To emphasise our point, we consider as in Sec. 2.3 the case of the quadratic loss f(h, 2) (h - 2)2. Here, we only need assume that our data. have a finite variance if we restrict our posteriors have both bounded means and variance. Also the meaning of the online predictive sequence P, is that must. be able to design properly sequence of priors before drawing
9

---

Published in Transactions on Machine Learning Research (04/2023)
our data, this can be for instance online algorithm whihe generate prior distribution from past data each time step.
Finally, we note that if we assume being able to bound simultaneaously all condtional means and variance (which is strictly less restrictive than bounding the lhsn).then Thm. 3.1 suggests a new online learning objective which is an online counterpart to Eq. (4).
> argmin Enco (((h))2)) [(hs 2:)²
(L(QQ) A
Vi 2 1 Q++1
(5)
QEMÉ (9)
Comparison with literature. Our most natural comparison point is Theorem 2.3 of Haddouche and Guedj (2022) (re-stated in Appondix A). We claim that Thm. 3.1 is strict improvement of their result on various sides described below.
If assume our loss to be bounded, then can upper bound our empirical/thheorticaal variance terms to recover exactly Haddouche and Guedj (2022, Theorem 2.3). Our bound can then be seen as a striet extension of theirs and shows that bounding order two moments sufficient condition to perform online PAC-Bayes: subgaussianity induced by boundedness is not necessary even when our data are non iid.
Another crucial point lies on the range of our result which holds with high probability for any countable posterior sequence (Qu) any time and the priors (Pr,5)e11 This is far much general than Haddouche and Guedj (2022, Thcorem 2.3) which holds only for single and single posterior sequence (Qi.s)i=t..m. This happens because in Haddouche and Guedj (2022), the change of measure inequality has not been exploited: they used preliminary theorem from Rivasplata et al. (2020) which holds for single (data-dependent) priorpposterior couple. This preliminary theorem already involved Markov's inequality which forced the authors to assume conditionnal subgaussianity to deal with an exponential moment. On the contrary, we exploited the fact that our online predictive sequence was history-dependent to use the change of measure inequality any time step and control an exponential supermartingale through Ville's inequality.
In Haddouche and Guedj (2022, Eq. 1), OPB algorithm is given by their upper bound. This works because their associated lcarning objective admits a close form (Gibbs posterior) which matches the fact their bound hold for a single posterior sequence. Because our bound holds uniformly on all posteriors, it is now legitimate to restrict their algorithms to any parametric class of distributions and perform any optimisation algorithm to obtain a surrogate of the best candidate.
Online PAC-Bayes as presented in Haddouche and Guedj (2022) relies on conditional subgaussiannity assumption to control an exponential moment. They did not exploit a martingale-tppe structure to do so. Our supermartingale approach has proven to be well suited to Online PAC-Bayes as we provided athcorom valid for unbounded losses holding simultaneously on all posteriors: two points which have not been reached in Haddouche and Guedj (2022).
3.1 Proof of Thm. 3.1
Proof. We fix m 2 1, S a countable dataset and (P:) an online predictive sequence. We aim to design a m-tuple of probabilities. Thus, our predictor set of interest is Km = He and then, our predictor h is a tuple hm, H.
Our goal is to apply the change of measure inequality on Hm to specific function fm inspired from Lemma 1.3. We define this function below, for any sample S and any predictor 1t = (hi, ... hm)
2
fm,
XX, 24)
Σ s=1
(illss 22) Vi(h.)),
10

---

Published in Transactions on Machine Learning Research (04/2023)
where X,(h, 24) E,-1(e(h,, 24)] ((,,,22) Notice that for fixed h, the sequence (fm(5 is super- martingale according to Lemma 1.3.
Now for given posterior tuple Q1,..Qm we define Q Qi @ @ Qm and also Ps = P1s @ @ Pm.s. We can now properly apply the change of measure inequality for any m.
X² (Vi(hi,2)) + V;(h+)) = R (m,(
Cha_q,AX, z;)
2
S KKL(Q, + log PE (S,
Noticing that KL(Q, = Em KL(Qi, P,s), the only remaining term to deal with is the exponential rv. To do so we prove the following lemma:
Lemma 3.2. The sequence (Mn Bg exp(fm ((, )22 non-negative supermartingale.
Proof. We fix m 2 and we recall that for any i, Pi,s is measurralll We show that Em-1 [M S Mn-1- We first recover Mm-1 from i [Mm]-
E 11 [Mm] = R1
Pm h
-1
B 30
(S,
X2 (Xx((h, (Vi 23) + Vi(ha))
Emm-
cxp
X2
1.M-1Emm Em--
Reth Rephmr exp
XXm 2m)
(Vin (lims (Vm(M + Vm (Pm)))
2m)
2
The last line holding because PS pmm Pl.s 8 PM-1. Jm-1 measurable.
Now we exploit the fact that Pm.s is Jm-1 measurable apply conditional Fubini lemma stated in Haddouche and Guedj (2022, Lemma D.3). We have:
X2 (V (hmm 2m) + Vm (Phml)
Em
P Pm.s
eepp Ax (lim: Zm)
2
X2 (V (lims 7m) Vm (m((m)) )
En Pm..
Bm-1 exp AXm (d 2m)
Now apply Lemma 1.3 for any hm H. with AMm Xmmlmm Zm), A[M V(hms 2m) and A(M) (hm). We then have for all hm H:
X2 (V (11m: zm) + Vnn Vnn (mn(hm))) 11.
Em-1 exp
AX (Nmm 2m)
2
Thus Em- [M,] S Mm-1. this concludes the lemma's proof.
Now we can apply Ville's incquality which implics that with probability least 8, for any m 2 1:
Em exp(Sm <
Thus we have with probability at least 1-5, 6, for any posterior sequence (Q,)z2 the data-dependent measures .,, Pm,s and any m 1:
11

---

Published in Transactions on Machine Learning Research (04/2023)
B (x,((h))))) - X² 2 (Vi(h,,2s) + Vi(h)) - KL(Q,, - log (
Re-organising the terms in this bound and dividing by À concludes the proof.
4 Application to the multi- bandit problem
We exploit our main result in the context of the multi-armed bandit problem we adopt the framework of Seldin et al. (2012a).
Framework. Let A be set of actions of size |A| K < +oo and E A be an action. At each round i, the environment furnishes reward function R, A + R which associate reward R₂(a) to the arm Assuming the R,s are iid, we denote for any the expected reward for action to be R(a) ER, [R)(a)] At each round i, the player exccutes an action A, according to policy We then set the filtration (F)).21 to be F, = a (1T Aj, R2 1
Assumptions. We suppose here that (R))21 is an sequence and that at each time i, A₃ and Rg are independent and that n, is F--1 measurable. This means that the player is not aware of the rewards each round and performs its current move with regards to the past.
We also add two technical assumptions. First, the order two moment of the expected reward is uniformly bounded: suPaE.4 En, (a) < C. This assumption is strictly less restrictive than the boundedness as- sumption made in Seldin et al. (2012a). Similarly to this work, we also assume that there exists a sequence (sz)121 such that inf (a) 2 Eg. We say that (T1)22 is bounded from below by (5,)221-
Definitions. For 2 1 and a {l...., K}, define a set of random variables (11))22 (the importance weighted samples, Sutton and Barto, 2018)
a. R.
if A =a
R =
0, otherwise.
We define for any time m: (a) = R(a). Let a" be the "best" action (the action with the highest expected reward, there are multiple "best" actions pick any of (hem). Define the expecled and empérical per-round regrels
Ei= -
R. Observe that for all i, E (R FT-1]= R(a) and (a)
A(a) Ra") R(a), Am(a)= = Pun (a*) (a).
Observe that m (Am(a) - A(a) forms a martingale. Tet
Σ E R - (R(a") - R(a)) 19-1
(a) =
the cumulative variance of this martingale and
R R - [R(a") R(a))²
Vin(a (a)
its empirical counterpart. We denote for any distribution Q over A, A(Q) = Banq/A(a)), Vn = Ea~qIVn similar definitions hold for (Q), (Q). We can now state the main result of this sec- tion its proof is deferred to Appendix C.
12

---

Published in Transactions on Machine Learning Research (04/2023)
Theorem 4.1. For any 2 1, any historg-dependent policy sequence (TT))21 bounded from below by (E:)121 we have with probabilily - 6, for all posterior Q
(1+ )x) (log(K) log(4/)))
- - (m)))) s $21
mcm
To the best of our knowledge, this result is the first. PAC-Bayesian guarantees for multi-armed bandits with unbounded rewards. The proposed bound is as tight as Theorem 2.3 of Seldin et al. (2012a), up to a factor (e (e-2) transformed into (1 + 2K) (which is huge dependency K) within the square root. Note that our result comes at. the price of the localisation: Theorem 2.3 of Seldin al. (2012a) proposes bound holding uniformly for all time while our approach only holds for single time
We believe there is room for improvement in Thm. 4.1. Indeed, the current approach is naive as it consists in bounding crudely with high probability the empirical variance. Such naive trick impeach us to consider all times simultancously. Indeed, in its current form, taking an union bound on Thm. 4.1 costful as we have a dependency in 1/6 in our result (instead of (1g(1/6) in Seldin et al., 2012a): this would destroy the convergence rate. The question of dealing more subtly with the empirical variance term left as an open question.
5 Conclusion
We showod that it possible generalise the PAC-Bayes toolbox unbounded martingales and heavy- tailed losses (resp. learning problem with unbounded losses for batch/online learning), the solely implicit assumption being the existence of second order moments the martingale difference sequence (resp. the loss function) which is reasonable many PAC-Bayes bound lies assumptions on exponential moments (e.g. the subgaussian assumption) to work. We also proved that our main theorem can be seen as a general basis allowing to recover several PAC-Bayesian bounds. This shows that the supermartingale framework is a fruitful approach to unify several branches of PAC-Bayes and could lead to new promising developement such the work of Jang et al. (2023).
References
P. Alquier. User friendryyndly introduction to PAC-Bayes bounds, 2021. URL 11216.
P. Alquier and G. Biau. Sparse single-index model. J. Mach. Learn. Res., 14(1):243-25) 280, 2013. doi: 10.5565//566709925522222 2502580.. URL https://dl, acm. org/doi/10 5555/2567709 0rr//06/10..555/6677000 0ttp:/2257770..2225558.. 2502589.
P. Alquier and B. Guedj. Simpler PAC-Bayesian bounds for hostile data. Machine Learning, 107(5))887-00,, 2018. ISSN 1573-0565. URL http://dx doi. org/10. 100.0000000000944000550000000000
P. Alquier, J. Ridgway, and N. Chopin. On the properties of variational approxiiaiosss of gibbs posteriors. Journal of Machine Learning Research, 17(236):1-44 41, 2016. URL http::://iaal..orgpppprrs/////tt html.
J.-Y. Audibert and O. Catoni. Robust linear least squares regression. The Annals of Statistics, 39(5):2766 2794, 2011. doi: 10.1214/11-AOS91. URL https://doi. /1t////...0///000111111111103030
Banerjee. On Bayesian Bounds. In Proceedings of the 23rd international conference on Machine learning,
pages 81-88, 2006.
B. Bercu and A. Touati. Exponential incqualitics for self-normalized martingales with applications. The Annals of Applied Probability, 18(5):1848 1869, 2008.
F. Biggs and B. Guedj. Differentiable PAC-Bayes objectives with partially aggregated neural networks. Entropy, 13(10):1280, 2021.
13

---

Published in Transactions on Machine Learning Research (04/2023)
F. Biggs and B. Guedj. On margins and derandomisation in PAC-Bayes. In G. Camps- Valls, F. J. R. Ruiz, and I. Valera, editors, Proceedings of The 25th International Conference Artificial Intelligence and Statistics [AISTATS], volume 151 of Proceedings of Machine Learning Research, pages 3709 3731. PMLR, 28-30 Mar 2022a. URL https://proceednngs www.mmlrr.eeeee... wttppp///////i/gg/22220. htmll.
F. Biggs and B. Guedj. Non-vacuous Gencralisation Bounds for shallow neural networks. In ICML, 2022b.
F. Biggs, V. Zantedeschi, and B. Guedj. On margins and generalisation for voting classi- fiers. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, odi- tors, Advances in Neural Information Processing Systems, volume 35, pages 9713-9726. Curran Associates, Inc., 2022. URL https://proceeding/ neurips. nwurips.cc/paperr. cc/paper fatteerffflsepppppaeeeeee files//paper/2222/1ee Poaeeeeeeee
O. Catoni. A PAC-Bayesiag approach to adaptive classification. preprinl, 840, 2003.
O. Catoni. Slatistical learning (heory and slochastic oplimizalion: Bcole d' d'Elé de Probabililés de Swint-Flour XXXI-2001, volume 1851. Springer Science & Business Media, 2004.
O. Catoni. PAC-Bayesian Supervised Classification: The Thermodynamies of Statistical Learning. Institute
of Mathematical Statistios Lecture Pates-Monograppe Series 56. IMS, Beachwood, OH. MR2483528, 5544465, 2007.
O. Catoni. PAC-Bayesian bounds for the Gram matrix and least squares regression with random design. arXiv preprint arXio: 100.00009 2018.
O. Catoni and 1. Giulini. fimension-fres PAC- Bayesian bounds for matrices, vectors, and linear least squares regression. arXiv preprint 1iii::712.027/ 2017.
B.-F. Chérief-Abdellann Y. Shi, A. Doucet, and B. Guedj. On PAC-Bayesian reconstruction guarantees for VAEs. In G. Camps-Vale Valls, F. J. R. Ruiz, and 1. Valera, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics [AISTATS], volume 151 of Proceedings of Machine Learning Research, pages 1966-3079 PMLR, 28-30 30 Mar 2022. URL httpps://rrocedingss mlr press/ ht55/hheriief-abdllattii.
html.
1. Csiszár. 1-divergence geometry of probability distributions and minimization problems. The annals of probability, pages 146-158, 1975.
V. H. De la Peña, T. L. Lai, and Q.-M. Shao. Self-normalized processes: Limit theory and Statistical Applications, volume 204. Springer, 2009.
M. D. Donsker and S. S. Varadhan. Asymptotic evaluation of certain Markov process expectations for large time, I. Communications on Pure and Applied Mathematics, 28(1):1-47, 1975.
J. Doob. Jean Ville, Étude Critique de la Notion de Collectif. Bulletin of the American mathematical society, 45(11))824-824, 1939.
P. Dupuis and R. S. Ellis. A Weak Convergence Approach to the Theory of Large Deviations. Wiley- Interscience, 2011.
R. Durrett. Probability: theory and eromples, volume 49. Cambridge university press, 2019.
G. K. Dziugaite and D. M. Roy. Computing Nonvacuous Generalivation Bounds for Deep (stochastic) Neural Networks with many more parameters than training data. arXiv preprint arXic:1703. 100.11008, 2017.
M. Fard and Pineau. PAC-Bayesian Model Selection for Reinforcement Learning. Advances in Neural Information Processing Systems (NeurIPS), 23, 2010.
P. Germain, A. Lacasse, F. Laviolette, and M. Marchand. PAC-Bayesian Learning of Linear Classifiers. In Proceedings of the 26th Annual International Conference on Machine Learning, ICMI. '09, page 353-360, New York, NY, USA, 2009. Association for Computing Machinery. ISBN 9781605585161. URL https: //doi.oor//1i 11 11110..11111155111 1553419.
14

---

Published in Transactions on Machine Learning Research (04/2023)
P. Germain, F. Bach, A. Lacoste, and S. Lacoste-Julien. PAC-Bayesian theory meets Bayesian inference. Aduances in Newral Information Processing Systems (NewrIPS), 29, 2016.
B. Guedj. A Primer on PAC-Bayesian Learning. In Proceedings of the second congress of the French Mathematical Society, 2019.
B. Guedj and Alquier. PAC-Bayesian estimation and prediction in sparse additive models. Electron. J. Statist., 7:264 291, 2013. doi: 10.1214/13-EJS77L. URL https://doi.orr//11 http://0o...oog/111.11443313377 1211111111-1117711
Guedj and Robbiano. PAC- Bay-saan high dimensional rapartite Journal of Statistical Planning and Inference, 196:70 86, 2018. ISSN 0378-3758. doi: http:://dbbbooo//000000./ppppp11
URL
http://www.ecieenctireettt wttee/tccccciiicc/reereeee http://///ccaaaaaaaata//////////
M. Haddouche and В. Guedj. Online PAC-Baye Learning. In Koyejo, S. Mohamed, A. Agarwal, D. Bel- grave, K. Cho, and A. Oh, editors, Advances in Newral Information Processing Systems, volume 35, pages 25725 25738. Curran Associates, Inc., 2022. URL https://prooeeedingg neurips. wwweerps..cppappeeppeeeeeeeeeeee wwwpaper_pppeeeeeeeeeeeeeeee hecppperrfiies////// _flees pdf.
M. Haddouche, Guedj, O. Rivasplata, and J. Shawe- Shawe-Taylor. PAC-Bayes unleashed: generalisation bounds with unbounded losses. Entropy, 23(1)):3330, 2021.
M. Holland. PAC-Bayes under potentially heavy tails. In H. Wallach, H. Larochelle, A. Beygelzimer, Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Newral Information Processing Systems (NeurIPS) 32, pages 2715-2724. Curran Associates, Inc., 2019. URL http://papers. mips cc/paper/ pdf.
8539
Jang, K.-S. Jun, Kuzborskij, and F. Orabona. Tighter PAC-Bayes Bounds Through Coin-Belting, 05829.
2023. URL
S. M. Kakade, K. Sridharan, and A. Tewari. On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. Advances in Newral Information Processing Systems (NeurIPS), 21, 2008.
I. Kuzborskij and C. Szepesvári. Efron-Stein PAC-Bayesian Inequalities. arXiv preprint 19XX:v:909.01900 2019.
J. Langford and R. Schapire. Tutorial practical prediction theory for classification. Journal of machine learning research, 6(3), 2005.
G. Letarte, P. Germain, B. Guedj, and F. Laviolette. Dichotomize and generalize: PAC-Bayesian binary activated deep neural networks. Advances in Newral Information Processing Systems (NeurIPS), 32, 2019.
G. Lever, F. Laviolette, and J. Shawe-Taylor. Distiibution-dependeent PAC-Bayes priors. In International Conference on Algorithmic Learning Theory, pages 119 133. Springer, 2010.
G. Lever, F. Laviolette, and Shawe-Taylor. Tighter PAC-Bayes bounds through distributtion-depeedent priors. Theoretical Computer Science, 473:4-28, 2013.
A. Maurer. A note on the PAC Bayesian thcorem. arXiv preprint cs/0411099, 2004.
D. A. McAllester. Some PAC-Bayesian theorems. In Proceedings of the eleventh. annual conference Computational Learning Theory, pages 230-234. ACM, 1998.
D. A. McAllester. PAC-Bayesian model averaging. In Proceedings of the twelfth annual conference Computational Learning Theory, pages 164 170. ACM, 1999.
D. A. McAllester. PAC-Bayesian stochastic model selection. Machine Learning, 51(1):5 21, 2003.
Z. Mhammedi, P. Grünwald, and B. Guedj. PAC-Bayes Un-Expected Bernstein Inequality. In H. Wallach, H. Larochelle, A. Beygelzimer, F. Alché-Bue, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems (NeurIPS) 32, pages 12202-12213. Curran Associates, Inc., 2019. URL http://papers:
15

---

Published in Transactions on Machine Learning Research (04/2023)
L. Oneto, D. Anguita, and S. Ridella. PAC-Bayesian analysis of distribution dependent priors: Tighter risk bounds and stability analysis. Pattern Recognition Letters, 00:200-207, 2016.
E. Parradd--Hrnnndez, A. Ambroladze, J. Shawe-Taylor, and S. Sun. PAC-Bayes bounds with data depen- dent priors. The Journal of Machine Learning Research, (3(1):3507-355 2012.
M. Perez-Ortiz, O. Rivasplata, B. Guedj, M. Gleeson, J. Zhang, J. Shawe-Taylor, M. Bober, and J. Kittler. Learning PAC-Bayes Priors for Probabilistic Neural Networks. 2021a. URL 2030.
abs//
M. Perez-Ortiz, O. Rivasplata, E. Herradd-Hernander, B. Guedj, and J. Shawe-Taylor. Progress in self- certified neural networks. In NewrIPS 2021 workshop Bayesian Deep Learning (BDL), 2021b. URL http: //bayesiandeplearinng wwweeniinnoogg/////e
/
pdf.
M. Pérez-Ortiz, O. Rivasplata, Shawe-Taylor, and C. Szepesvári. Tighter Risk Certificates for Neural Networks. Journal of Machine Learning Research, 22, 2021.
A. Picard-Weibel and B. Guedj. On change of measure inequalities for f-divergences. arXiv preprint arXiv:2202.0588 05568, 2022.
O. Rivasplata, V. M. Tankasali, and C. Szepesvári. PAC-Bayes with Backprop. CoRR, abs/ 1908.07388 2019. URL http:/ /ttp::////axvvv// org/ wwtgg/ab//990/// 07380.
Rivasplata, Kuzborskij, C. Szepesvári, and J. Shawe-Taylor. PAC-Bayes analysis beyond the usual bounds. Advances in Neurol Information Processing Systems (NeurIPS), 33:16833 16845, 2020.
M. Seeger. PAC-Rayesian Generalization Error Bounds for Gaussian Process Classification. Journal of Machine Learning Research, 3, 08 2002.
Y. Seldin, F. Laviolette, J. Shawe-Tayes Taylor, J. Peters, and Auer. PAC-Bayesian Analysis of Martingales and Multiarmed Bandits. aivi preprint arXiv: 1r5.e:1105.2416, 2011.
Y. Seldin, N. Cesa- Bianchi, P. Auer, F. Laviolette, and J. Shawe- Taylor. BAC-Bayes-Bernstein Bernstein Inequality for Martingales and its Application to Multiarmed Bandits. In D. Glowacka, L. Dorard, and J. Shawe-Taylor, editors, Proceedings of the Workshop Online Trading of Exploration and Exploitation 2, volume 26 of Proceedings of Machine Learning Research, pages 98 111, Bellevue, Washinglon, USA, 02 Jul 2012a. PMLR. URL https: //tp://////ccc/s.s..o/o.o mlr, wwt.smll....sseeee ppess//v2/seeddnnnge sete///dddiniia...aa... html.
Y. Seldin, F. Laviolette, N. Cesa- Bisnchianchi, J. Shawe-Taylor, and P. Auer. PAC-Bayesian Inequalities for Martingales. IEFE Transactions on Information Theory, (5(12):7086-7099)) 2012b.
J. Shawe-Tayiae and R. C. Williamson. A PAC analysis of Bayes estimator. In Proceedings of the 10th annual conference on Compulational Learning Theory, pages 2 9. ACM, 1997.
R. S. Sutton and A. G. Barto. Reinforcement Learning: An introduction. MIT press, 2018.
T. Tao. An introduction to measure theory, volume 126. American Mathematical Society Providence, 2011.
N. Thiemann, C. Tgel, O. Wintenberger, and Y. Seldin. A strongly quasiconvex PAC-Bayesian bound. Tn International Conference on Algorithmiic Learning Theory, pages 466-44 496. PMLR, 2017.
I. O. Tolstikhin and Y. Seldin.
Inequality. In C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Weinberger, editors, Advances in Neural Information Processing Systems (NewrIPS), volume 26. Curran Associates, Inc., 2013. URL https::/proceeet .df.
neurips. cc/
Y.S.. Wu and Y. Seldin. Split-kl and pac-bayos-split-kl inequalitics for ternary random vari- ables. S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, edi- tors, Advances in Neural Information Processing Systems, volume 35, pages 11369 11381. Cur- Associates, Inc., 2022. URL https://proceeddngg ceourip..c/ppppee. files//aper/2022//1ee 499ff177184000t000ee22eeeeee Papise----p----ee Conf confeeenne..o pdf.
16

---

Published in Transactions on Machine Learning Research (04/2023)
A Some PAC-Bayesian background
We present below an immediate corollary of Scldin et al. (2012a, Thm 2.1) where we upper bounded the cumulative by an empirical quantity (the sum of squared upper bound of the martingale difference sequence).
Theorem A.1 (Seldin et al., 2012a, Theorem 2.1). Let {Ci, C2,...) be increasing sequence set in odvance, such that (S,, h)] & C2 for all S; h with probability 1. Let {P1,P2.... be sequence of data-free prior distributions over H. Let (A:) be sequence of positive numbers such that
1
Am S Cm
Then with probability 1 - over S (24)621, for all 2 1, any posterior Q over H.
Mm (Q)1 < KL Pm) log(m + 1) log 2
+ - 22)2m Vm (Q):
Am
where (Q) is defined in Appendir B.1.
Furthermore, if bound the variance term, would have:
Mm (Q) < (Q]()
log(m + 1) log + (e - 2) Cτ.
Am
im1
Below, we use the definitions introduced Sec. 2.3. We study here a particular case Alquier et al. (2016) for bounded losses which are especially subgaussian thanks to Hoeffding's ' lemmaa
Theorem A.2 (Adapted from Alquier et al., 2016, Theorem 4.1). Let m > 0,8 = (Z1, 2m) be an iid sample from the same law μ. For any data-free prior P, for any loss function bounded by K, any X > 0, e]0; 1[, one has with probability 1 for any posterior Q E (H)
E [R(h)] S EA (h)] + KI(QIIP) log(115) AK2
+
A
2m
Theorem A.3 (Haddouche et al., 2021, Theorem 3). Let the loss E be HYPE(K) compliant. For any P E MT (H) with no dala dependency, for any a E lK and for any å E [0, 1], we have with probabilily al least over size-m samples S, for any Q
En~Q [R(h]] S En-Q [mm (h)) + [TI + (t)
K(h) )1)
+ ma
log EAWP exp
m
2m
Theorem A.4 (Theorem 2.3 of Haddouche and Guedj, 2022). For any distribution μ over 2 any À > O and any online predictive sequence (used as priors) (Pt), for any sequence of stochastic kernels (Q:) we have with probability 1 over the sample ~ ,., the following, holding for the data-dependent measures Q= = = Q.S..),, Pi.s == P.(...)
RA -n. [B[e(hs, 2:) Fi-1]]] < Σ BA [e(hs 2:)] KL(QU.s|IP.s)
XmK² + log(1/0)
Σ 1=1
X
B Extensions of previous results
Here we gather several corollaries of our main result in order to show how our Thm. 2.1 extends the validity of some classical results in the literature. More precisely we show that our result extends (up to numerical factors) the PAC-Bayes Bernstein incquality of Seldin et al. (2012a). Then, going back the bounded case, we generalise result from Catoni (2007) reformulated in Alquier et al. (2016) and we also show how our work strictly improves the bound of Haddouche et al. (2021).
17

---

Published in Transactions on Machine Learning Research (04/2023)
B.1 Extension of the PAC-Bayes Bernstein inequality
Here we rename two terms for consistency with Theorem 2.1 of Seldin et al. (2012a) (see Thm. A.1). For martingale Mm (h) Li=l (S,S,, h), define, at time m, empirical cumulative variance to be V (h) (h) = - (S,, h) and the cumulative variance as (h) (M) (h) L ( h)))
m
We provide below a corollary containing two bounds: the first one being a straightforward corollary of Thm. 2.1, the second being valid for bounded martingales and formally close to Theorem 2.1 of Seldin et al. (2012a).
be a sequence of data-free prior distributions over K. Let (Az)s21 be sequence of positive numbers. Then the following holds with probability 5 over S = (zi)i21: : for any tuple (m, ARs Pk) with m, z 1, any posterior Q over H,
Corollary B.1. Let
Mm (Q)1 - KL Pa) + 2 log(k k + 1) + 1og(2/6) d (vn
(6)
A
= - V (h)]. Furthermore, if we assume that for any i, there exists C > O such that [X,(S;, h)l I C2 for all S, then we have the following corollary: with probability over S, for any tuple (m, Ams Pm) m 2 1, any posterior Q,
with ( (h)], Vm (Q)
KL KL (Q,Pm) + 2 log(m + 1) + log(2/6) Am
Mm (Q) S
C²-
Am
The proof deferred to Appendix C. Note that Eq. (6) holds uniformly on all tuples {(A,, Pky m) k 1.m 1} while Eq. (7), as well as Theorem 2.1 of Seldin et al. (2012a) holds uniformly the tuples [(mm, Pm;m) 2 }} which is strictly smaller collection. Hence our approach gives guarantees for a larger event with the same confidence level.
Furthermore, Theorem 2.1 of Seldin et al. (2012a) involves the cumulative variance Vn (Q) (and not its empirical counterpart). Because this term is theoretical, we bound it in Thm. A.1 by E C? which is supposedly empirical. In this context, Eq. (7), recovers nearly exactly the bound of Seldin et al. (2012a) with the transformation of factor (e- 2) into 1. Notice also that Eq. (7) stands with no assumption on the range of the λo which is not the case in Thm. A.1.
Finally, we stress two fundamental differences between our work and the one of Seldin et al. (2012a). First, we replace Markov's inequality by Ville's inequality; second, we exploited the exponential inequality of Lemma 1.3 instead of the Bernstein inequality. These allow for results for unbounded martingales for all m simultancously.
B.2
Extensions of learning theory results
B.2.1 general result for bounded losses
We use definitions from Sec. 2.3 and provide corollary of our main result when the loss is bounded by positive constant K > 0. We assume our data are iid.
Corollary B.2. For any data-free prior P E (H), any the following holds with probability over the sample S (z))es, for all m E N/(0), Q E MT (I()
KL(Q,, P) + log(2/5) + XK?
1 [[h)] Ennq RR, (h)]l
Am
We also have the local bound: for any m 2 1, with probability 1 - over S, for all Q E (J()
KL(Q, log(2/8) + m
XR
Ex~o| < Ex- Rm [h)]+
18

---

Published in Transactions on Machine Learning Research (04/2023)
The proof is deferred to Appendix C. Remark that the second bound of Corollary B.2 is exactly the Catoni bound stated in Alquier et al. (2016) (see Thm. A.2 in Appendix A) up to numerical factor of 2.
The first bound is, to our knowledge, the first PAC-Bayesian bound for bounded losses holding uniformly (for a given parameter X) on the choice of Q. m and thus extends the scope of Catoni's bound which holds for a single m with high probability. Indeed, if we want for instance Thm. A.2 to hold for any E (1..m), we then have to take an union bound on m events which turns the term log(1/0) into log(m/6) (but with the benefit of holding for m parameters A.....Am)). This point is common to the most classical PAC- Bay-Bay bounds (as those of McAllester, 1998; 1999; Maurer, 2004; Catoni, 2007; Tolstikhin and Seldin, 2013) and impeach us to have a bound uniformly on all m E N/(0} as log(m) goes to infinity asymptotically.
B.2.2 An extension of Haddouche al. (2021)
We now focus on the work of Haddouche et al. (2021) which provides general PAC-Bayesian bounds for unbounded losses. Their theorems hold for iid data and under the so-called HYPE (for HYPothesis- dependent rangF) condition. It states that a loss function & is HYPE(() compliant if there exists a function : + I= (supposedly accessible) such that Vz E 2, ((h, S (h).. We provide Cor. B.3 to compare ourselves with their main result (stated in Thm. A.3 for convenience).
Corollary B.3. For any data-free prior P E M (IC), any loss function & being HYPE(K) compliant, any a E (0, 1), 2 1, the following holds with probability 1 8 over the sample S = (zi)ieN, for all Q E (H)
E [R(h)] En~Q
m Σ
2(h,2i) +
2m 2m (h, 2))²
+) m
E Ex~ [K (h))
2m
Proof. The proof is a straightforward application of Thm. 2.3 by fixing 2 choosing À = =m=-1 (thus we localise Thm. 2.3 to single m), and bounding Quad(h) by (h).
The main improvement of our bound over Thm. A.3 is that we do not have to assume the convergence of an exponential moment to obtain a non-trivial bound. Indcod, we transformed the (implicit) assumption ExpP
+00 onto Ex-q [k)))K(h)) < +00, which is significantly less restrictive. Furthermore, Thm. A.3 holds for a single choice of m while ours still holds uniformly over all integers m > 0.
exp
2m 2m--2a
K(h)²
Cor. B.3 also sheds new light on the HYPE condition. Indeed, in Haddouche et al. (2021), K only intervenes in an exponential moment involving the prior P, while ours considers a second-order moment on K implying the posterior Q. The difference major as Ex~Q ER>q|K(())) [K(h] can be controlled by wise choice of posterior. Thus it can be incorporated in our optimisation route, acting now as an optimisation constraint instead of environment constraint.
C Proofs
C.1 Proof of Thm. 2.3
Proof. Let P a fixed data-free prior, set (Fi) such that for all i, 24 is Fj measurable. We also set for any fixed h. E H. Mn (h) = Σm ((h, 4:)- - R(h). Note that because data are iid, for any fixed h, the sequence (Mm (h)) is indeed a martingale. We set for any m 2 1, E H
(h) Σ (e(h, - R(h)))
i=1
and
(M) (h) = - E, [(((h, 2;) R(h)) Σ E Eenp((((he)) (E(h,2) R((h))9.
E
i=1
19

---

Published in Transactions on Machine Learning Research (04/2023)
The last equality holds because data is assumed rid. Thus, we can apply Thm. 2.1 to obtain with probability
1-6 8
(Mm(2)) KI[Q, P) log(2/6) A (l04) + (M))(
Now, we notice that |M (Q)l = m mm (R(h) - Rm)ll]] and that for any m, h, because is nonnegative
m
(m) + (m) =
Σ (((h, - RR(h))² + -E=nul((hh R(h)))
1=1
m
Σ
((h,zi)² R(h)² EZzZp (e(,, -R(h))
Thus integrating over h gives:
(M) (M) S
Σ En olehh 2x) mBn--qQuad(hh
Then dividing by and applying the last inequality gives
((h, 24) + 2 ((h, ((hh 22²²)
KL P) + log(2/8) Bn-olQuad((h).
[R-o(R(M) En-Q
Am
2
This concludes the proof.
C.2 Proof of Thm. 4.1
Proof. Let (Am)iz1 be a countable sequence of positive scalars. As precised earlier Mm(a) := m (mm(a) - A(a)) is martingale. We then apply Thm. 2.1 with the uniform prior (Va, P(a) K and À Am (depending possibly m): with probability 1 8/2, for any tuple (m, Am) with m 2 any posterior Q.
Mm (Q) S KL(Q,P) +2+ log(4/0)
+ Am (2) + Vz)
Am
Notice that for any Q, KL(Q, P) S log( K)) by concavity of the log. We now fix an horizon M > 0, we then have in particular, with probability - 8/2: for any posterior Q,
log(K) + 2 log(k: + 1) + log(4/0) + 2 (Q) Vm
Am
Mm (Q) <
d
We now have to deal with V₂(Q),, (Q) for all & m. To do so, we propose the two following lemmas.
Lemma C.I. For all 2 1, A, Vn (a) <
2Cm cm
Then, we have for any m, Q, Vn (Q) S 2Cm
Em
Proof. We have
Vi(a)= =
E
Red
Rdj - A(a)
1
Rg."
R
|
mn
m
EE
[gg"
15,-1
IE
E
E
Es:
me(at)2 (a(aa) =a)+
Te(a)² T 1((a) a) 15
20

---

Published in Transactions on Machine Learning Research (04/2023)
The last line holding because R, is independent of F--1, A, is independent of R4 and is Fi-1 measurable. We now use that for all i, a,a, ER, [R:(a) S
1 CI(A = a) F
BArn
= a²) + CI(AA=aa)
CI(A,
Ti(a')²
2,(08
(a)
Tt (a*)
T=(aa²
3i (a+) )²
1=1
(a)
Ti (a*)
2Cm
Em
Lemma C.2. Let m 2 1, with probability 1 8/2, for any posterior Q, we have
4CKm
Vm S
5
Proof. Let Q a distribution over A. Recall that
(Q) Σ R R2 (R(()) R(a)))
1=1
Σ (a))
aEA
Notice that for any a, (SM mm nonnegative random variable. We then apply Markov's inequality for any a, with probability 1 8/2K
(a) < 2KE
Noticing that EV (a)) [V[,.. (4)), we can apply Lemma C.I conclude that
20m
V s
Em
Finally, taking union bound thoser events for all A gives us, with probability 1 - 5/2, for any posterior
(m) S Σ (a))
aEA
4CKm
Σ Q(a)
aEA
4CKm
Emd
This concludes the proof.
To conclude, apply Lemmas C.1 and C.2 to get that with probability 1 1 8, for any posterior Q
KL (Q, P) + log (4/8) Cmdm
2k
MM,, (Q) <
1
Am
Em
21

---

Published in Transactions on Machine Learning Research (04/2023)
Dividing by and taking
(log( K)) + log(4/6)) Em
Am
Cm (1 28
concludes the proof.
C.3 Proof of Cor. B.1
Proof. Fix 0. For any pair (Au, Po), 2 1, we apply Thm. 2.1 with
8
6g :- k(k +1)
1)2*
Notice that we have E0 6x =. We then have with probability - òn over S, for any m 2 1, any posterior
Q
M (Q)) S KL + log(k + 1) log(2/0) An
2 (2))
Taking an union bound on all those event, gives the final result, valid with probability 1 1-6 over the sample S, for any any tuple (m, Ae Ps) with m, k 2 any posterior Q over H. This gives Eq. (6).
To obtain Eq. (7), we restrict the range of Eq. (6) to the tuples (m, Am Pm), m 2 1 (the restricted set of tuples where = m) and we bound both V., (Q), Vm (Q) by Em C? to conclude.
C.4 Proof of Cor. B.2
Proof. For the first bound we start from the intermediary result Eq. (3) of Thm. 2.1. Using the same
marrtingale as in Thm. 2.3 gives, for any E I,, holding with probability - å for any m > 0, E (T())
En~o [(1,, 2:)] - m mBn mBB-o((((N)) < KL(Q, log(1/)) - 112 Σ Em 1=1
2 1=1
Taking = +1 with > gives
X² Am EANQ [R(h) (m)( < KL log(1/5)
E
En
[MM] A(M))
(8)
1=1
Finally, divide by Am and bound A (h) + (h) by 2K2 to conclude.
For the second bound, start from Eq. (8) again and for fixed m, now apply our result with X' A/m.
We then have for any m, with probability 6, for any Q
X m
A [ [Rhh) Rm (h)]l & KL(Q, + log(1/6)
En-o/A[M].(1 + (MM)
2m
Finally, dividing by A, bounding (M) + ((M)(() by 2K2 and rearranging the terms concludes the proof.
22


Reviews:
[{"review_id": "lkAqlOLsYK", "reviewer": "Reviewer_oC3Q", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I found the paper very well-written and the stated lemma in the main body helps the reader understand the main contribution of the paper. I think the technique used in the paper is novel and can have a lasting impact on the literature. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of PAC-Bayes bounds under the assumption that the losses can be unbounded. The well-known results for PAC-Bayes mainly stated for bounded loss functions. \n\nThe authors in this paper provide a nice technique for obtaining Pac-Bayes bound for unbounded losses. They also show the applications of their technique for statistical learning with iid data and PAC-bayes guarantee for online leanring.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I think the paper is good as is.", "broader_impact_concerns": "There is no concern in this front.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "kCZyfuZ5xN", "reviewer": "Reviewer_bQp1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe result is new to my knowledge, and the proof technique is very clean: up to the technical Lemma 2.2 which is essentially a careful verification that one can interchange certain integrals, the proof follows the method of building a submartingale $Z_n(\\eta)$ from a martingale $M_n$ by setting $Z_n(\\eta) = \\exp(\\eta M_n - \\eta^2 V_n)$ and then using Ville’s maximal inequality to bound $Z_n(\\eta)$ for all $n$.\n\nThe applications to previous results are interesting, although to my mind the basic main theorem is the most valuable part of the paper. Indeed, the application to multi-armed bandits seems to actually have the wrong dependence on the number of arms $K$ Although the authors acknowledge that the bandit result is probably not tight, one has to inspect the bound carefully to see this worse dependence - I think the paper would be better to actually mention this to guide future readers to future questions.\n\nWeakness:\n\nThis is not much of a weakness but more a comment:\nWhether having the dependence on the empirical variance in Theorem 2.1 is wholly a negative is up for debate: the empirical second moment is observable and so is arguable more useful than the true second moment.The authors attempt to exploit this in equation (4) which provides a kind of analog of a “structural risk minimization” objective using empirically observable quantities. However, it seems unsatisfying for  two reasons:\n1. The dependence on the actual variance is ignored, so as far as I can tell, we cannot conclude what  the relationship is between solutions to this objective and the generalization error.\n2. The value of $\\lambda$ is fixed. The authors seem to claim this is a feature rather than a bug, but I am not convinced. Surely it would be better to have a data-dependence $\\lambda$ (intuitively it should be something like $1/\\sqrt{\\text{some variance term}}$. I do not understand what is meant by a fixed $\\lambda$ being helpful  ”in order to ensure a stable  learning algorithm”. Stable in what sense? The only argument I can see for having a non-adaptive $\\lambda$ is computational as the objective might be harder to solve. In particular with a tuned $\\lambda$, the result should presumably become a kind of \"generalization bound analog\" of adaptive algorithms in the learning with expert advice literature in which the  ideal algorithm obtains regret $\\tilde O(\\sqrt{KL(P,Q)  V_n})$ where $P$ is  some prior, $Q$ is a comparator and $V_n$ is  variance-analog just as in this paper  (e.g. see https://arxiv.org/pdf/2102.01046.pdf and references therein).\n\nThese seem like they should be fixable if it were possible to obtain a purely empirical bound with only $[M]_(Q) $ without $\\langle M\\rangle_m(Q)$. After tuning $\\lambda$, the objective might become more difficult to minimize of course, but that seems a secondary issue.\n\nMinor comments:\nLemma 1.3: I think you have not defined $[M]_m$ and $\\langle M\\rangle_m$ yet - just $\\Delta[M]_m$ and $\\Delta\\langle M\\rangle_m$. Please add the definitions here.\n\nThe authors might take a look at recent papers https://arxiv.org/abs/2110.14099 and https://arxiv.org/abs/2302.05829, which use similar techniques to prove bounds on martingales. The latter in particular appears to be a similar result (although contemporaneous so I do not have novelty concerns on that front).\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper provides a new concentration inequality for parametrized martingales $M_1(h), M_2(h),\\dots$ where $h\\in H$ is some parameter (often $H$ is a hypothesis class but in principle it could be anything). Specifically, for any distributions $P$ and $Q$ over $H$, we define $M_n(Q)=\\mathbb{E}_{h\\sim Q}[M_n(h)]$ and then it is shown that for any $\\lambda, \\delta$, with probability $1-\\delta$, for all $n$:\n\n$|M_n(Q)| \\le \\frac{KL(Q,P) + \\log(2/\\delta)}{\\lambda} + \\frac{\\lambda}{2} V_n$\n\nWhere $V_n$ is some technical analog of variance that we might expect to be $O(n)$ in the case that $M_n$ is bounded or has light tails, but might be controllable in other cases as well. Notably, by taking a union bound over pairs $(\\lambda, \\delta) = (2^i, 6\\delta /\\pi i^2)$ for all positive integers $i$, one recovers an analog of the law of iterated logarithm (this fact seems not mentioned in the paper, but I think it might be worth a remark).\n\nImportantly, the result does  not require any light tailed conditions on the martingales and so can be used to generate concentration inequalities that require only a bound on the second moment. This appears to be “paid for” in the term $V_n$, which now depends not only on the second moment of $M$, but also on an “empirical” second moment.  \n\nThis main result is used to extend several previous results about generalization error, online learning, and bandits to the case of unbounded losses.\n\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address the issues raised in the review. Adding more discussion as suggested in various places would help the paper IMO, but is not required for securing my recommendation.", "broader_impact_concerns": "none", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "iauud0fBqS", "reviewer": "Reviewer_Foq3", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths:*\n- The basic problem of interest is stated clearly, with comprehensive references from the literature giving their results context.\n- The technical strategy taken in this paper is explained quite clearly, as is the impact this strategy has on the resulting PAC-Bayes style error bounds.\n\n*Weaknesses:*\nOverall, I found the presentation and writing to be somewhat sloppy. I think there is a fair bit of room for improvement here.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Broadly speaking, this is a technical paper which looks at extending the PAC-Bayes analytical machinery to new learning problems and algorithms. More precisely, they are interested in problems involving (random) losses or rewards that are allowed to be unbounded, and potentially dependent (up to martingale requirements).\n\nMy understanding of the main contributions is as follows.\n\nAs a foundational technical lemma, they exploit Ville's maximal inequality (extending beyond the Markov inequality step typical to PAC-Bayes proofs) to deal with martingale difference sequences that are potentially unbounded. The main general-purpose result here is Thm. 2.1. Martingales in the PAC-Bayes setting were addressed in previous work by Seldin et al. a decade ago, but with boundedness assumptions. The \"corollary\" of this result is Thm. 2.3, which gives a more typical PAC-Bayes learning setup (iid data, expected loss bounds), and does not require bounded losses. Their bound here involves quadratic loss terms (both sample and population) and holds jointly over all sample sizes. The dependence on $\\delta$ is better than that of Alquier and Guedj (2018), and they do not have terms that can increase with sample size as in Holland (2019). As for Kuzborskij and Szepesvari (2019; henceforth KS19), the result is very similar, albeit looser (since $\\lambda$ cannot be optimized in the same way here), but holds for any prior.\n\nIn addition, they build upon the recent Online PAC-Bayes framework of Haddouche and Guedj (2022), essentially leaving the framework as-is, but removing the need for sub-Gaussianity (instead using quadratic deviations), and obtaining bounds that hold over all time steps.\n\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Below, I will highlight a few specific points that I tripped up on while reading this paper; it is not a comprehensive list, but I think the authors can generalize beyond these points easily, and that doing so would strengthen the paper.\n\n*Section 2.1 is unclear*\n- The overall flow of this section is rather unnatural. The main result Thm. 2.1 is buried between \"Framework\" and \"Analysis of the bound\" paragraphs; the proof also starts abruptly after the literature comparison. Why not break the proof into a separate sub-section? (I think the same should be done for the main result of section 3 as well)\n- I found the \"Comparison with literature\" quite terse. This is an important paragraph, comparing the work with that of Seldin et al., but the price paid to be able to handle unbounded random variables is not clear. The authors mention \"Bounded variations of the martingale difference sequence\", \"restrictions on the range of $\\lambda$\" and \"Bernstein\", but I think many readers will not know what the authors are talking about - the only assumption in this section is that of a martingale difference sequence and a data-free prior. Presumably a reference to certain points in section 1.2 or the proof of Thm 2.1 could clear things up.\n\n*Claims in 2.2:*\nThe comparison with KS19 is mentioned briefly in the last paragraph with details relegated to the appendix, but I think this is worth the effort of explaining to the reader, since KS19 gives PAC-Bayes bounds for unbounded losses. Related to this, on p.7, the authors say that their bound \"matches the usual PAC-Bayes literature\" (which is true), \"while for unbounded losses, which is novel\" (this is questionable). I assume the authors have the \"holds jointly over all $m$\" qualifier in mind when they make this statement, but it is confusing and I think this paragraph should be re-written. The proof route here is very different from KS19, and it is rooted in a result that allows for dependent random variables. \n\n*Notation:*\nWhen introducing the *stochastic kernel* on p.8, they introduce $\\mathcal{S}$; does this appear anywhere else? Note also the mapping $Q$ (same paragraph) maps to \"$[0;1]$\", I think the unit interval is usually written $[0,1]$.\n\n*Bandit extension:*\nIn section 4, the authors essentially match the Seldin et al. bounds for multi-armed bandits without requiring bounded rewards, though with the cost being \"localization\". This is the opposite of what we see in the batch iid case, where the authors' bounds hold simultaneously over all sample sizes; unless I have missed it, I think a paragraph describing the reason for this difference would be beneficial to the reader.", "broader_impact_concerns": "No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Three reviewers read the manuscript. Even in the initial reviews, the reviewers were unanimous that the technique is new and the results are important. I agree with them.

On the other hand, the reviewers disagreed on the writing of the initial version. While oC3Q "found the paper very well-written", bQp1 found it "acceptable" and provided a list of minor problems to be fixed. Foq3 wrote "I found the presentation and writing to be somewhat sloppy. I think there is a fair bit of room for improvement here" and pointed out many parts of the paper that were unclear or inaccurate. I thank reviewers bQp1 and Foq3 for their detailed reading of the paper and their constructive comments. These were taken into accounts by the authors and it was very beneficial to the paper. About the new version, Foq3 wrote "I feel that the paper presents reasonable claims with evidence presented in a sufficiently clear form, and that the paper should have an audience if included in TMLR" and bQp1 wrote "the authors have improved the readability in the revision, and I am happy to recommend acceptance".

Thus, I am also happy to support the publication of the paper in TMLR, and I sincerely congratulate the authors for this nice work.

That being said, I maintain that both the abstract and the introduction still contain inaccuracies on the subexponential/bounded problem. This is both unfair to some existing works, and misleading for future readers: sub-exponentiality is not boundedness. Thus, I will require a minor revision in order to fix these issues.

More precisely:

1) PAC-Bayes bounds for unbounded losses are quite old. In Catoni's St-Flour notes (2021), Chapter 5 is dedicated to PAC-Bayes bounds for classification AND regression with quadratic loss, under the assumptions that the loss is sub-exponential (Equation 5.8.1 page 181). While this is still restrictive, it allows to deal with Gaussian noise, which is I believe an important example of unbounded noise. This approach was reused in a large number of papers on PAC-Bayes since. For example, Guedj's PhD thesis [Aggregation of estimators and classifiers : theory and methods, 2013] studies nonparametric additive regression under the assumption that the noise is subexponential (Assumption 2.1 page 40) and indeed follows Catoni's technique in the proofs. For these reasons, I think the following sentence is misleading: "Several works (Alquier and Guedj, 2018; Holland, 2019; Haddouche et al., 2021) already proposed routes to overcome the boundedness constraint". There are two problems in one sentence:
- PAC-Bayes bounds for unbounded losses are standard in the sub-exponential case, and Catoni's lecture notes should be cited,
- the main contribution of (Alquier and Guedj, 2018; Holland, 2019) was not to tackle the unbounded case, but heavy-tailed losses (or without exponential moments). Alquier and Guedj (page 889): "This paper shows that a proof scheme of PAC-Bayesian bounds proposed by Bégin et al. (2016) can be extended to a very general setting, without independence nor exponential moments assumptions". Holland (abstract): "We derive PAC-Bayesian learning guarantees for heavy-tailed losses".

I will ask the authors to fix these sentences. I would even suggest to fix the title: "PAC-Bayes bounds for Heavy-tailed Losses through Supermartingales" instead of "PAC-Bayes bounds for Unbounded Losses through Supermartingales", as the current title is not an accurate description the contribution of the paper, but I will leave the choice to the authors.

2) there were other works on PAC-Bayes bounds with heavy-tailed losses besides (Alquier and Guedj, 2018; Holland, 2019). The paper [Audibert and Catoni, Robust linear least squares regression, AOS, 2011] proves PAC bounds for least square estimators with unbounded (and potentially heavy-tailed) X's and noise. While the estimator studied is not Bayesian, the proof relies on PAC-Bayes bounds and the results could completely be extended to Bayesian estimators. A problem in the proof makes the result suboptimal with respect to the dimension, this was later fixed by [Catoni and Giulini, Dimension-free PAC-Bayesian bounds for matrices, vectors, and linear least squares regression, arXiv, 2017] and [Catoni, PAC-Bayesian bounds for the Gram matrix and least squares regression with a random design, arXiv, 2018]. The latter proves PAC-Bayes bounds for the quadratic loss under the only assumption that moments of order 4 are finite.

Thus, the comment in the abstract "(as simple as the squared loss on an unbounded space)" is particularly poorly chosen: results in this case have been known for years. It is very important to remove this comment from the paper before publication and I think it would be honest to cite Catoni and Giulini's papers. As Catoni and Giulini's technique is very specific to the quadratic loss, this does not remove any interest from the new supermartingale technique.
Decision: Accept (poster)