Online PAC-Bayes Learning
Authors: Maxime Haddouche
Benjamin Guedj
Venue: NeurIPS 2022 Accept (2022)
Keywords: PAC-Bayes
Online Learning
Non-Convex losses

Abstract: Most PAC-Bayesian bounds hold in the batch learning setting where data is collected at once, prior to inference or prediction. This somewhat departs from many contemporary learning problems where data streams are collected and the algorithms must dynamically adjust. We prove new PAC-Bayesian bounds in this online learning framework, leveraging an updated definition of regret, and we revisit classical PAC-Bayesian results with a batch-to-online conversion, extending their remit to the case of dependent data. Our results hold for bounded losses, potentially \emph{non-convex}, paving the way to promising developments in online learning.

Online PAC-Bayes Learning
Maxime Haddouche Inria and University College London France and UK
Benjamin Guedj
Inria and University College London France and UK
Abstract
Most PAC-Bayesian bounds hold in the batch learning setting where data is col- lected once, prior inference prediction. This somewhat departs from many contemporary learning problems where data streams are collected and the algo- rithms must dynamically adjust. We prove PAC-Bayesian bounds in this online learning framework, leveraging an updated definition of regret, and we revisit clas- sical PAC-Bayesian results with batch-to-online conversion, extending their remit to the case of dependent data. Our results hold for bounded losses, potentially non-convex, paving the way to promising developments online learning.
Introduction
Batch learning is somewhat the dominant learning paradigm in which we aim to design the best predictor by collecting a training dataset which then used for inference or prediction. Classical algorithms such SVMs [see Cristianini et al., 2000, among many others] or feedforward neural networks [Svozil et al., 1997] are popular examples of efficient batch learning. While the mathematics of batch learning constitute vivid and well understood research field, in practice this might not be aligned with the way practitionners collect data, which can be sequential when too much information available at given time (e.g. the number of iiero-trannaactons made in finance daily basis). Indeed batch learning is not designed to properly handle dynamic systems.
Online learning (OL) IZinkevich, 2003, Shalev-Shwartz, 2012, Hazan, 2016] fills this gap by treating data as a continuous stream with a potentially changing learning goal. OL has been studied with convex optimisation tools and the celebrated notion of regret which measures the discrepancy between the cumulative sum of losses for a specific algorithm at each datum and the optimal strategy. It led to many fruitful results comparing the efficiency of prediction for optimisation algorithms such that Online Gradient Descent (OGD), Online Newton Step through static regret [Zinkevich, 2003, Hazan al., 2007]. OL is flexible enough incorporate external expert advice onto classical algorithms with the optimistic point of view that such advices are useful for training [Rakhlin and Sridharan, 2013a.b] and then having optimistic regret bounds. Modern extensions also allow compare to moving strategies through dynamic regret [see e.g. Yang et al., 2016, Zhang et al., 2018, Zhao et al., 2020]. However, this notion of regret has been challenged recently: for instance, Wintenberger [2021] chose to control an expected cumulative loss through PAC inequalities in order to deal with the case of stochastic loss functions.
Statements holding with arbitrarily large probability are widely used in learning and especially within the PAC-Bayes theory. Since its emergence in the late 90s, the PAC-Bayes theory (see the seminal works of Shawe-Taylor and Williamson, 1997, McAllester, 1998, 1999 and the recent surveys by Guedj. 2019, Alquier, 2021) has been powerful tool to obtain generalisation bounds and derive efficient learning algorithms. Classical PAC- generalisation bounds help to understand how learning algorithm may perform on future similar batches of data. More precisely, PAC-Bayes learning exploits the Bayesian paradigm of explaining a learning problem through a meaningful distribution over space of candidate predictors [see e.g. Maurer, 2004, Catoni, 2007, Tolstikhin and Seldin, 2013, Mhammedi et al., 2019]. An active line of research in PAC-Bayes learning is to
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

overcome classical assumptions such that data-free prior, bounded loss, iid data [see Lever et al., 2010, 2013, Alquier and Guedj, 2018, Holland, 2019, Rivasplata et al., 2020, Haddouche et al., 2021, Guedj and Pujol, 2021] while remaining in a batch learning sprit. Finally, pioneering line of work led by [Seldin et al., 2012a,b] on PAC-Bayes learning for martingales and independently developed by [Gerchinovitz, 2011, Foster et al., 2015, Li et al., 2018] boosted PAC-Bayes learning by providing sparsity regret bound, adaptive regret bounds and online algorithms for clustering.
Our contributions. Our goal is to provide a general online framework for PAC-Bayesian learning. Our main contribution (Thm. 2.3 in Sec. 2) a general bound which is then used to derive several online PAC-Bay BaBesias results (as developed in Secs. 3 and 4). More specifically, we derive two types of bounds, online PAC-Bayesian training and test bounds. Training bounds exhibit online procedures while the test bound provide efficiency guarantees. We propose then several algorithms with their associated training and test bounds as well as a short series of experiments to evaluate the consistency of our online PAC-Bayesian approach. Our efficiency criterion is not the classical regret but an expected cumulative loss close to the one of Wintenherger [2021]. More precisely, Sec. propose a stable yet time-consuming Gibbs-based algorithm, while Sec. 4 proposes time efficient yet volatile algorithms. We emphasize that our PAC-Bayesian results only require a bounded loss to hold: no assumption is made on the data distribution, priors can be data-dependent and we do not require any convexity assumption on the loss, as commonly assumed in the OL framework.
Outline. Sec. 2 introduces the theoretical framework as well as our main result. Sec. 3 presents an online PAC-Bayesian algorithm and draws links between PAC-Bayes and OL results. Sec. 4 details online PAC-Bayesian disintegrated procedures with reduced computational time and Sec. 5 gathers supporting experiments. We include reminders on OL and PAC-Bayes in Appendixes A. and C. Appendix B provide disucssion about our main result. All proofs are deferred to Appendix D.
2 An online PAC-Bayesian bound
We establish a novel PAC-Bayesian theorem (which in turn will be particularised in See. 3) which overcomes the classical limitation of data-independent prior and iid data. We call our main result an online PAC-Bayesian bound as allows to consider a sequence of priors which may depend on the past and a sequence of posteriors that can dynamically evolve well. Indeed, we follow the online learning paradigm which considers a continous stream of data that the algorithm has to process on the fly, adjusting its outputs at each time step w.r.t. the arrival of new data and the past. In the PAC- AAC-Bayesian framework, this paradigm translates as follows: from an initial (still data independent) prior Q P and data sample S = (Z1, we design a sequence of posterior (Qi) where Qi = f(Q1...,, 14)
Framework. Consider data space 2 (which can be only inputs or pairs of inputs/outputs). We fix an integer m > 0 and our data sample S E 2n is drawn from an unknown distribution μs. We do not make any assumption on μ.. We set sequence of priors, starting with P. P data-free distribution and (P:) (2) such that for each i, P, is F;-1 measurable where (F, (2,) is an adapted filtration to S. For P. Q Mr (3C), the notation P < Q indicates that Q is absolutely continuous wrt P (i.e. Q(A) = if P(A) = 0 for measurable A C H). We also denote by Qi our sequence of candidate posteriors. There is no restriction on what Q; could be. In what follows we fix filtration (Fi)ezo and we denote by KT, the Kullback-L divergence between two distributions.
We consider predictor space H and a loss funtion e H x 2 + R+ bounded by a real constant K3 > O. This loss defines the (potentially moving) learning objective. We denote by (HH) the set of all probability distributions on H. We now introduce the notion of stochastic kernel [Rivasplata et al., 2020] which formalise properly data-dependent measures within the PAC-Bayes framework. First, for fixed predictor space H., we set Σn to be the considered alagebrr on K.
Definition 2.1 (Stochastic kernels). A stochastic kernel from S = n to H is defined as mapping Q: : mm
Exe + [0; 1] where
* For any B E Esc, the function S = (51, ... 7m) + Q(S, is measurable,
* For any S E 2m, the function B - Q(S, B) is probability measure over H.
We denote by Stoch(8, H) the set of all stochastic kernels from to K and for a fixed S, we set Qs = Q(S.) the data-dependent prior associated to the sample S through Q.
2

---

From now, to refer to distribution Qs depending on dataset S, we introduce a stochastic kernel Q(...) such that Qs = Q(...) Note that this notation perfectly suited to the case when Qs is obtained from an algorithmic procedure A. In this case the stochastic kernel Q of interest is the learning algorithm A. We use this notion to characterise our sequence of priors.
Definition 2.2. We say that a sequence of stochastic kernels (P:)i=t..m is an online predictive sequence if for all 2 1,5 "n, P.....) is F--1 measurable and for all i 2 2. P.(S..) P.-1(S..).
Note that (ii) implies that for all i, P((..) > Pi(S..) with (S,..) a data-free measure (yet a classical prior in the PAC-Bayesian theory).
We can now state our main result.
Theorem 2.3. For any distribution μ over 2 any X > 0 and any online predictive sequence (used as priors) (Pr), any sequence of stochastic kernels (Qi) we have with probability 1-8 over the sample
S ~ ,s the following, holding for the data- deta-dependent measures Qi,s ... == P:(...)
Qis [B(e(hs, 24) F1-11]1 S Σ Qi. [e(h, =,]]+ KL(Qus)|Prss) Amk
log 1/6)
À
2 À
Remark 2.4. For the sake of clarity, we assimilate in what follows the stochastic kernels Qi P, to the data-dependent distributions Qi(S,.), P((S.). P.S..). Then, an online predictive sequence is also assimilated to a sequence of data-dependent distributions. Concretely this leads to the switch of notation Qt,s + Qi in Thm. 2.3. The reason of this switch is that, even though stochastic kernel is the right theoretical structure to state our main result, we consider in Secs. 3 and 4 practical algorithmic extensions which focus only on data depe-dennndent distributions, hence the need alleviate our notations.
The proof is deferred to Appendix D. See Appendix B for context and discussions.
A batch to online conversion. First, we remark that our bound slightly exceeds the OL framework: indeed, it would require our posterior sequence to be an online predictive sequence as well, which not the case here (for any the distribution Q1.s can depend on the whole dataset This is a consequence of our proof method (see Appendix D.I), which is classically denoted as a "batch to online" conversion (in opposition to the "online batch" procedures as in Dekel and Singer, 2005). In other words, we exploited PAC-Bayeed -ay-Bayninnn tools designed for fixed batch of data to obtain a dynamic result. This is why we refer to our bound as online as allows to consider sequences of priors and posteriors that can dynamically evolve.
Analysis of the different terms in the bound. Our PAC-Bayesian bound formally differs in many points from the classical ones. On the left-hand side of the bound, the sum of the averaged expected loss conditioned the past appears. Having such a sum of expectations instead of a single one is necessary to assess the quality of all our predictions. Indeed, because data may be dependent, one can not consider a single expectation as in the iid case. We also stress that taking an online predictive sequence as priors leads to control losses conditioned to the past, which differs from classical PAC- MAC-Bayes results designed
bound the expected loss. This term, while original in the PAC- MAC-Bayesian framework (to the best of our knowledge) recently appeared (in a modified form) in Wintenberger [2021, Prop 3]. See Appendix B.2 for further disucssions.
On the right hand-side of the bound, online counterparts of classical PAC-Bayes terms appear. At time i, the measure Q; (i.e. Qt.s according Remark 2.4) has tradeoff to achieve between an overfitted prediction of z; (the case Qi = 5z; where is a Dirac measure) and a too weak impact of the new data with regards our prior knowledge (the case Q2 = P.). The quantity À > 0 can be seen as a regulariser to adjust the relative impact of both terms.
Influence of A. The quantity À also plays crucial role the bound as it is involved in explicit tradeoff between the KL terms, the confidence term log(1/5) and the residual term mK2 2/2 This idea of seeing À as trading parameter is not new [Thiemann al., 2017, Germain al., 201 (]. However, the results from Thiemann et al. [2017] stand w.p. 1 8 for any À while ours and the ones from Germain et al. [2016] hold for any À w.p. 1 8 which is weaker and implies to discretise R+ onto a grid to estimate the optimal X.
We now move on to the design of online PAC-Bayesie algorithms.
3

---

3 An online PAC-Bayesian procedure
OL algorithms (we refer to Hazan, 2016 an introduction to the field) are producing sequences of predictors by progressively updating the considered predictor (see Appendix A.1 for example). Recall that, in the OL framework, an algorithm outputs at time a predictor which is F;- -measurable. Here, our goal is design an online procedure derived from Thm. 2.3 which outputs online predictive sequence (which is assimilated, according to Remark 2.4, to a sequence of distributions).
Online PAC-Bayesian (OPB) training bound. We state corollary of our main result which paves the way to an online algorithm. This constructive procedure motivates the name Online PAC-Bayesian training bound (OPBTRAIN in short).
Corollary 3.1 (OPBTRAIN). For any distribution μu over 2 any X > 0 and any online predictive sequences Q, P. the following holds with probability 1 5 over the sample S p
B Q [e(hi, =:] + KL(Q++1lP.)
Amk²
log(1/0)
E h, Qum1 B[e(h;, I--]]] S
+
À
2
Here, À is seen as scale parameter as precised below. The proof consists in applying Thm. 2.3 with for all i, Qi = Qi+i and P, Note that in this case, our posterior sequence is an online predictive sequence in order to fit with the OL framework.
Corollary 3.1 suggests design Q follows, assuming we have drawn dataset S {z1, 2m fixed scale parameter À > O and an online predictive sequence P.:
P2) A
i = P1,
Vi 2 Q:+1 = argmin ExSn [e(h; 2;)]
(1)
QEM,(30)
which leads to the explicit formulation
dQ 10++1 (h) = dP.
exp (-Xe(h, 24)
(2)
En [exp (-Ae(h, =;))]
Thus, the formulation of Eq. (2), which has been highlighted by Catoni [2003, Sec. 5.1] shows that our online procedure produces Gibbs posteriors. So, PAC-Bayesian theory provides sound justification for the somewhat intuitive online procedure in Eq. (I): at time i, we adjust our new measure Qi+1 by optimising a tradeoff between the impact of the newly arrived data 2, and the one of prior knowledge Q.
Notice that is an online predictive sequence: Qi is F,-1 for all as it depends only on Qi-1 and 2;- Furthermore, one has Q > Q.-1 for all i as Q; is defined as an argmin and the KL. term is finite if and only it is absolutely continuous w.r.t. Q.
Remark 3.2. In Corollary 3.1. while the right hand-side is the reason we considered Eq. (1), the left hand side still needs to be analysed. It expresses how the posterior Q++1 (designed from Qú, 24) generalises well on average to any new draw of 24. More precisely, this term measures how much the training of Q.- overfitting on 2;, low value of it ensures our online predictive sequence, which is obtained from a single dataset, is robust to the randomness of S. hence the interest of optimising the right hand side of the bound. This is supplementary reason we refer to Corollary 3.1 as an OPBTRAIN bound as it provide robustness guarantees for our training.
Online PAC-Bayesian (OPB) test bound. However, Corollary 3.1 does not say if Q will produce good predictors to minimise {(., 1)) which is the objective of Q.+1 in the OL framework (we only have access to the past to predict the future). We then need to provide an Online PAC- Bayesian (OPB) test bound (OPBTEST bound) to quantify our prediction's 's accuracy. We now derive an OPBTEST bound from Thm. 2.3.

---

Corollary 3.3 (OPBTEST). For any distribution j. over 2mh any À > O, and any online predictive
sequence (Qi), the following holds with probability 1 - 8 over the sample S ~ p.:
E B. [e(h, 2,)1 + Amk²
log (1/6)
Σ R &. [B(e(hs;;)) [ S
2
X
1=1
Optimising in À gives x 2 loge 1olg(1/00/mmk and ensure that:
m
B - [Bie 2i) Fi-1lll S Σ B [e(hi zi]] + +0 (Vlog(1/8)K3mm
The proof consists in applying Thm. 2.3 with for all i, 0, = P..
Corollary 3.3 quantifies how efficient will our predictions be. Indeed, the left hand side of this bound relates for all i, how good Q; is to predict 2, (on average) which is what Q; is designed for. Note that here, the involved À can differ from the scale parameter of Eq. (1), it is now way to compensate for the tradeoff between the two last terms of the bound. The strength of this bound is that since Q is an online predictive sequence, the Kullback-Leibler terms vanished, leaving terms depending only on hyperparameters.
Links with previous approaches
We now present a specific case of Corollary 3.1 where we choose as priors the online predictive sequence Q ei.e. in Thm. 2.3, we choose Qi = Qi+1, P. = (.). The reason we focus on this specific case is that it enables to build strong links between PAC-Bayes and OL.
We then adapt our OPBTRAIN bound (Corollary 3.1). The online procedure becomes:
vi vi 2 1Q41 argming En [e(h,, 2:)] + KL(Q141)
P
(3)
which leads to the explicit formulation
dQ
exp (-X((h, 2;))
(h)
dQ:
Q (exp (-Ae(h, 2,)]
Links with classical PAC-Bayesian bounds. case is such that at any time i, dQ++1(h) exp(-Xe(h, (1)))(((,,2))d(((() (() hence dQ@+1(h) oc (- m E(h, 2,)) aQ, (h). One recognises, up to a multiplicative constant, the optimised predictor of Catoni [2007, Th 1.2.6] which solves argming Ey~Q [ Σm E(h, 24)] KL(QIς4)) thus one sees that in this case, the output of our online procedure after steps coincides with Catoni's output. This shows consistency of our general procedure which recovers classical result within an online framework: when too many data are available, treating data sequentially until time leads to the same Gibbs posterior than if we were treating the whole dataset as a batch.
We denote that the optimal predictor in this
Analogy with Online Gradient Descent (OGD). We propose an analogy between the procedure Eq. (3) and the celebrated OGD algorithm (see Appendix A.I for a recap). First we remark that our minimisation problem equivalent argming XER,. [E(h, 2;)] + KL(Q)IQ.). Then we assume that for any i, Q N(m,, La) with nú E Rd and set L;
_ [e(h,, x4) The minimisation problem becomes: argmin, (m, + 1 12. And so using the first order Taylor expansion, use the approximation (m) RJ (m..)) + (m m. V V.C(mM), which finally transform our argmin into the following optimisation process: m2+1 = m, (fL)( which is exactly OGD on the loss sequence L,. We draw an analogy between the scale parameter À and the step size 7) in OGD. the KL term translates the influence of the previous point and the expected loss gives the gradient. This analogy has been already exploited in they approximated En,~g, [E(h,, 24] := L,(H) Re 4 (L,()) where μ is their considered online predictive sequence.
[2012] where
Finally, we remark that the optimum rate in Corollary 3.3 a O(ym) which is comparable to the best rate of Shaley-Shwartz [2012, Eq (2.5)) (see proposition A.2).
5

---

Comparison with previous work. We acknowledge that the procedure of Eq. (3) already appeared in literature. Li et al. [2018, Alg. 1] propose a Gibbs procedure somewhat similar to ours, the main difference heing the addition of surrogate of the true loss at each time step. Within the OL literature, the idea of updating measures online has been recently studied for instance in Chérief-Abdellltii et al. [2019]. More precisely, our procedure is similar to their Streaming Variational Bayes (SVB) algorithm. A slight difference is that they approximated the expected loss similarly to Shalev-Shwartz [2012]. The guarantees Chérief-Abdellatt et al. [2019] provided for SVB hold for Gaussian priors and comes at the cost of additional constraints that do not allow to consider any aggregation strategies contrary to what Corollary 3.1 propose. Their bounds are deterministic and are using tools and assumptions from convex optimisation (such that convex expected losses) while ours are probabilistic and are using measure theory tools which allow to relax these assumptions.
Strength of our result. We emphasize two points. First, to the best of our knowledge, Corollary 3.1 is the first bound which theoretically suggests Eq. (3) as learning algorithm. Second, we stress that Eq. (3) is a particular case of Corollary 3.1 and our result can lead to other fruitful routes. For instance, consider the idea of adding noise to our measures at each time step to avoid overfitting (this idea has been used e.g. in Neelakantan et al., 2015 in the context of deep neural networks); our online predicitve sequence (Q+) can be defined through a sequence of parameter vectors fa, then we can define P. by adding small noise Pú and thus giving more freedom through stochasticity.
Thus, we see that our procedure led us to the use of the Gibbs posteriors of Catoni. However, in practice, Gaussian distributions are preferred [e.g. Dziugaite and Roy, 2017, Rivasplata et al., 2019, Perez-Ortiz et al., 2021b,a, Pérez-Ortiz et al., 2021J). That is why we focus next on new online PAC-Bayesian algorithms involving Gaussian distributions.
4 Disintegrated online algorithms for Gaussian distributions.
We dig deeper in the field of disintegrated PAC-Bayesian bounds, originally explored by Catoni [2007], Blanchard and Fleuret (2007), further studied by Alquier and Biau [2013), Guedj and Alquier [2013] and recently developed by Rivasplata et al. [2020], Viallard al. [2021] (see Appendix C for a short presentation of the bound we adapted and used). The strength of the disintegrated approach is that we have directly guarantees on the random draw of single predictor, which avoids consider expectations over the predictor space. This fact is particularly significant in our work as the procedure precised in Eq. (2), require the estimation of exponential moment to be efficient, which may be costful. We then show that disintegrated PAC-Bayesian bounds can be adapted to the OL framework, and that they have the potential to generate proper online algorithms with weak computational cost and sound efficiency guarantees.
Online PAC-Bayesian disintegrated (OPBD) training bounds. We present a general form for online PAC-Bayes disintegrated (OPBD) training bounds. The terminology comes from the way we craft those bounds: from PAC- Aay-BByesian disintegrated bounds use the same tools as in Thm. 2.3 to create the first online PAC-Bayesian disintegrated bounds. OPBD training bounds have the following form.
For any online predictive sequences Q,P, P, any X > 0 w.p. 1 1-6 8 over S ~ a and (hi hm) ~
Q2 @ ... & Qm+1:
B(e(h,,=)) (aocz)133111 13-11 S Σ e(by, + (h Q:11 P.) + +(m),
(4)
with V & being real-valued functions. controls the global behaviour of Qi+1 w.r.t. the FT-1- measurable prior P. If one has no dependency on h; this behaviour is global, otherwise it is local. Note that those functions may depend on A, 8. However, since they are fixed parameters, we do not make these dependencies explicit. Similarly to Corollary 3. this kind of bound allows to derive learning algorithm (cf Algorithm 1) which outputs online predicitve sequence Q. Finally draw hm.)...,.,,) Q2 @ ... & Qm+1 (and not Q1 @ ... @ Qm. since an OPBD bound is designed to justify theoretically an OPBD procedure in the same way Corollary 3.1 allowed to justify Eq. (1).
Why focus on Gaussian measures? The reason is that Gaussian variable h N(w, Ta) can be written as h w + E with & N(0, I2),, and this expression totally defines (I. being the identity matrix).

---

A general OPBD algorithm for Gaussian measure with fixed variance We use an idea presented in Viallard al. [2021] which restrict the measure set to Gaussian on I' with known and fixed covariance matrix I² Then we present in Algorithm a general algorithm (derived from an OPBD training bound) for Gaussian measures with fixed variance which outputs a sequence of gaussian Q: = N(; La) from a prior sequence P; = N(w (L, where for each i, w ---1- measurable. Because the variance is fixed, the distribution is uniquely defined by its mean, thus we identify Q, and uū, P. and w..
Algorithm 1: A general OPBD algorithm for Gaussian measures with fixed variance.
Parameters : Time m, scale parameter À
Initialisation: : Variance o², Initial mean 01 E Rd, epoch m
for each iteration in 1..m do Observe 2,, in and draw ~ N(0, La)
2
Update:
0/41 == argmin l(w + Ei, V(w Ei, w,
end
5 Return
At each time i, Algorithm 1 requires the draw of E ~ N(0,o²Ia) Ig)... Doing so, we generated the randomness for our hı (because our bound holds for a single draw of (hig.., hmm) ) ~ Q2 8 @ 1-),
we then write h4 w + E, and we optimise w.r.t. V to find 2;+1-
Bounds of interest. We present two possible choices of pairs (v, 1) derived from the disintegrated results presented in Appendix C. Doing so, we explicit two ready-to-use declinations of Algorithm 1. Corollary 4.1. For any distribution μ over nm, any online predictive sequences of Gaussian measures with fixed variance Q N(u;; o IT)) and P; = N(w,, I'Ia), any X >> O, w.p.
over S ~ l and (h; = wit1 + Ei)i=l..m ~ Q2 8 ... 2 Q Qm+1, the bound of Eq. (4) holds for the two following pairs M T
Vn (bis 18441, w!) = | 1 6i
11 12 ||e|12
AmK2
+ log(1/5)
2 (
(5)
20
(2(hi, 1 w!)) = [0041 w11l
3 3log(1/8)
(2 Am kmnk2 +
(6)
202
2X
Where the notation 1,2 denote whether the functions have been derived from adapted theorems of Rivasplata et al., 2020, Viallard al., 2021 recalled in Appendix We then can use algorithm with Eq. (5), Eq. (6).
Proof deferred to Appendix D.2. Note that in Corollary 4.1, we identified Q to Wy and for the last formula, V/ has no dependency on h4.
Comparison with Eq. (1). The main difference with Eq. (1) provided by the disintegrated framework that the optimisation route does not include an expected term within the optimisation objective. The main advantage is weaker computational cost when main weakness is a lack of stability as our algorithm now depends at time i on f(h + S;, 2;) so on e; directly. We denote that Eq. (5) is less stable than Eq. (6) as it involves another dependency through V. The reason is that Rivasplata et al. [2020) proposed a bound involving a disintegrated KI. divergence while Viallard al. [2021] proposed result involving Rényi divergence avoiding dependency on E,. We refer to Appendix C for a detailed statement of those properties.
restrict to Gaussian distributions. The
E;
Comparison with van der Hoeven et al. [2018]. Theorem of van der Hoeven et al. [2018] 2018] recovers OGD from the exponential weights algorithm by taking a sequence of moving distributions being Gaussians with fixed variance which is exactly what consider here. From these, they retrieve the classical OGD algorithm as well as its classical convergence rate. Let us compare our results with theirs.
First, if we fix a single step v their bound and assume two traditional assumptions for OGD (a finite diameter D of the convex set and an uniform bound G on the loss gradients), recover
7

---

for the OGD (greedy GD in der Hoeven et al., 2018) rate of D 20 + >0"TG" This is, up to constants and notation changes, exactly our V, (i (1,2)). Also, we notice a difference in the way to use Gaussian distributions: Theorem 3 of van der Hoeven et al. [2018] is based on their Lemma I which provides guarantees for the expected regret. This is clear incentive to consider as predictors the mean of the sucessive Gaussians of interest. On the contrary, Corollary 4.1 involves supplementary level of randomness by considering predictors h; drawn from our Gaussians. This additional randomness appears in our optimisation process (algorithm 1). Finally, notice that van der Hoeven et al. [2018] based their whole work on the use of a KL divergence while Corollary 4.1 not only exploit disintegrated KL (W/) 1) but also Rényi a-divergence (V22). Note that we propose result only for a = 2 for the sake of space constraints but any other value of a leads to another optimisation objective to explore.
OPBD test bounds. Similarly what we did in Sec. 3, we also provide OPBD test bounds to provide efficiency guarantees for online predicitve sequences (e.g. the output of algorithm 1). Our proposed bounds have the following general form.
For any online predictive sequence Q, any À > 0 w.p. 1 over S and (hi, hm) @13...8.mm.
Ele(h,, 24) [2-1) Σ E(h,, + +(m),
with & being real-valued function(possibly dependent on X, 6 though it is not explicited here).
Note that our predictors (hi..... hmm) are now drawn from Q @ & Qm. Thus, the left-hand side of the bound considers h; drawn from an -eeasuuuur distribution evaluated ((,, this is effectively measure of the prediction performance.
We now state a corollary which gives disintegrated guarantees for any online predicitve sequence.
Corollary 4.2. For any distribution μ over 2", any X O, and any online predictive sequence (Q:). the following holds with probability 1 1-6 - over the sample S ~ and the predictors (h1...., hm) ~ Q @ & Qm the bound of Eq. (7) holds with
AmR
log(1/0)
22(m) = 2XmK2 + log(1/8)
(m))
2
X
X
Where the notation 1,2 denote whether the functions have been derived from adapted theorems of Rivasplata al., 2020, Viallard et al., 2021 recalled in Appendix C. The optimised X gives in both cases a O(ym 1og(1/8).
Proof deferred to Appendix D.2.
5 Experiments
We adapt the experimental framework introduced in Chérief-Abdellatif et al. [2019, Sec.5) to our algorithms (anonymised code available here). We conduct experiments on several real-life datasets, in classification and linear regression. Our objective is twofold: check the convergence of our learning methods and compare their efficiencies with classical algorithms. We first introduce our experimental setup.
Algorithms. We consider four online methods of interest: the OPB algorithm of Eq. (3) which update through time Gibbs posterior. We instantiate it with different priors Q1: Gaussian distribution and a I Laplace one. We also implement A Algorithm with the functions V,, V, from Corollary 4.1. To assess efficiency, we implement the classical OGD (as described in Alg. I of Zinkevich, 2003) and the SVB method of Chérief-Abdellane
et al. [2019].
Binary Classification. At each round i the learner receives data point æ; Rd and predicts its label y/ E {-1,+1 +1} using (x,, hz), with h; = En-QQ. [h] for OPB methods or h; being drawn under Q for OPBD methods. The adversary reveals the true value yt, then the learner suffers the loss E(hs, =)) (1 yu æz)_, with z; (zi, v:) and a if and a 0 otherwise. This loss unbounded but can be thresholded.

---

Classification Breast Cancer
Classification PIMA Indians
10
10P
9x:10
0x13
Loss
7x
100
200
300
400
500
100
200
300
400
500
600
700
Regression Boston Housing
Regression California Housing
10a
Loss
Loss
10.1
040
Globa Couss
0PS0 Rioa
000
0P53 Aira
S48
G100 Lap loc2
0150 Via
SYB
0P83 Via
10
10000 17500
Figure 1: Averaged cumulative losses for all four considered datasets. 'Gibbs Gauss' denotes OPB with Gaussian Prior, 'Gibbs Laplace' denotes OPB with Laplace prior. 'OPBD Riva' denotes OPBD with 11. 'OPBD Via' denotes OPBD with 2/
Linear Regression, At each round i, the learner receives set of features x, Id and predicts Y: E IR using (a,, hy) with h, Rn- [h] for SVB and OPB methods h; being drawn under Q: for OPBD methods. Then the adversary reveals the true value 3/2 and the learner suffers the loss ((,,, 2)) (y: - hif =.) with 2; (Iz, This loss is unbounded but can be thresholded.
Datasets. We consider four real world dataset: two for classification (Breast Cancer and Pima Indians), and two for regression (Boston Housing and California Housing). All datasets except the Pima Indians have been directly extracted from sklearn [Pedregosa et al., 201 1]. Breast Cancer dataset [Street et al., 1993] is available here and comes from the UCI ML repository as well as the Boston Housing dataset [Belsley al., 2005] which can be obtained here. California Housing dataset [Pace and Barry, 1997] comes from the StatLib repository and available here. Finally, Pima Indians dataset [Smith et al., 1988] has been recovered from this Kaggle repository. Note that randomly permuted the observations to avoid to learn irrelevant human ordering of data (such that date or label).
Parameter settings. We ran experiments Gb RAM. For OGD, the initialisation point is Oga and the values of the learning rates are set to 7 1/ /m. For SVB, mean is initialised to Og and covariance matrix to Diag(1). Step at time i is Mi 0.1/Vi. For both of the OPB algorithms with Gibbs posterior, chose À = 1/m. As priors, we took respectively a centered Gaussian vector with the covariance matrix Diag (a = 1.5) and iid vector following the standard Laplace distribution. For the OPBD algorithm with 1, we chose À= = 10-1/mann m, the initial mean is Og and our fixed covariance matrix is Diag(o²) with - 3.10- For the OPBD algorithm with VI, we chose À 2.10- 3/m, the initial mean Og and our covariance matrix is Diag(a²) with a = 10-2 The reason of those higher scale parameters and variance is that V from Rivasplata et al. [2020] is more stochastic (yet unstable) than the one Viallard et al. [2021].
2021 MacBookPro with an MI chip and 16
Experimental results. For each dataset, we plot the evolution of the average cumulative loss Σ (h, 24) /t function of the step t 1,..., m, where m is the dataset size and h, is the decision made by the learner h, at step i. The results are gathered in Fig.
Empirical findings. OPB with Gaussian prior ('Gibbs Gauss') outperforms OGD on all datasets except California Housing (on which this method not implemented while OPB with Laplace prior ('Gibbs Laplace') always fail w.r.t. OGD. OPB methods fail to compete with SVB the Boston

---

Housing dataset. OPBD methods compete with SVB on regression problems and clearly outperforms OGD on classification tasks. OPBD with 2 (labeled as 'OPBD Via' in Fig. 1) performs better on the California Housing dataset while OPBD with 1 (labeled as 'OPBD Riva") is more efficient on the Boston Housing dataset. Both methods performs roughly equivalently on classification tasks. This brief experimental validation shows the consistency of all our online procedures as we observe visible decrease of the cumulative losses through time. It particularly shows that OPBD procedures improve OGD on these dataset. We refer to Appendix E for additional table gathering the error bars of our OPBD methods.
Why do we perform better than OGD? As stated in Sec. 4, OGD can be recovered as a Gaussian approximation of the exponential weights algorithm (EWA). Thus, legitimate question why do we perform better than OGD as our OPBD methods are also based on a Gaussian surrogate of EWA? van der Hoeven et al. [2018] only used Gaussians distributions with fixed variance as a technical tool when the considered predictors are the Gaussian means. In our work, we exploited richer characteristic of our distributions in the sense our predictors are points sampled from our Gaussians and not only the means. This also has consequences in our learning algorithm at time i of our algorithm I, our optimisation step involves a noise E; ~ N(0, I²I). Thus, we believe that OPBD methods should perform at least as well OGD. We write 'at least" we think that the higher flexibility due to this additional level of randomness might result in slightly better empirical performances, as seen on the few datasets in Fig.
6 Conclusion
We establish links between Online Learning and PAC-Bayes. We show that PAC-bayesian bounds are useful to derive OL algorithms. We also prove sound theoretical guarantees for such algorithms. We emphasise that all of our results stand for any general bounded loss, especially no convexity assumption is needed. Having convexity assumption the loss paves the way exciting future practical studies, starting with Spiking Neural Network which is investigated in an online fashion (see Lobo et al., 2020 for recent survey). A follow-up question the theoretical part is whether relax the bounded loss assumption: we leave this for future work.
Acknowledgements
We warmly thank reviewers and the Area Chair who provided insigthful comments and suggestions which greatly helped us improve our manuscript. 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 3616/1; G. also acknowledges partial support from the French National Agency for Research, grants ANR- 18 CE40-0016-01 and 10--188-E3-0000
References
P. Alquier. User-friendly introduction to PAC-Bayes bounds, 2021. URL https: org/ abs/2110. 11216.
P. Alquier and G. Biau. Sparse single-index model. Journal of Machine Learning Research, 14(1), 2013.
Alquier and B. Guedj. Simpler PAC- AAC-Baycsian bounds for hostile data. Machine Learning, 107(5): 887-902, 2018. ISSN 1573-0565. URL http: //xx. /twp/xxxxxiii//////ooo/////.ootd org/ 2ttg/10... 1wt.0000001940000 5690-0 O.
P. Alquier, J. Ridgway, and N. Chopin. On the properties of variational approximations of gibbs posteriors. Journal of Machine Learning Research, 17(236): 141, 2016. URL http://jmlr. org/papers/v17/15 html. 2t0.html.
D. A. Belsley, E. Kuh, and R. E. Welsch. Regression diagnosties: Identifying influential data and sources of collinearity. John Wiley & Sons, 2005.
G. Blanchard and F. Fleuret. Oceam's hammer. International Conference on Computational Learning Theory, pages 1 112-126. Springer, 2007.
10

---

O. Catoni. A PAC- PAC-Bayesian approach to adaptive classification. preprint, 840, 2003.
O. Catoni. PAC-Bayesian Supervised Classification: The Thermodynamics of Statistical Learning. Institute of Mathematical Statistics Lecture Notes Monnograhh Series 56. IMS, Beachwood, Off. MR2483528, 5544465, 2007.
B.-E. Chérief-Abdellatit, Alquier, and M. E. Khan. A generalization bound for online variational inference. In Asian Conference on Machine Learning, pages 662-677. PMLR, 2019.
N. Cristianini, J. Shawe-Taylor, et al. An introduction to support vector machines and other kernel- based learning methods. Cambridge university press, 2000.
O. Dekel and Y. Singer. Data-driven online to batch conversions. Advances in Neural Information Processing Systems, 18, 2005.
G. K. Dziugaite and D. M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv: 1703. 1008, 2017.
D. Foster, A. Rakhlin, and K. Sridharan. Adaptive Online Learning. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015. URL htsttts::pproeeeeeeeee 2015/file/1s (tteiieeee//eedee 14
neurips cc/paper/ Paper .df.
S. Gerchinovitz. Sparsity Regret Bounds for Individual Sequences in Online Linear Regression. In M. Kakade and U. von Luxburg, editors, Proceedings of the 24th Annual Conference on Learning Theory, volume 19 of Proceedings of Machine Learning Reseurch, pages 377-396, Budapest, Hungary, 09-11 Jun 2011. PMLR. URL btttps://proceeeee perchinovitzl1e htmm..mll..
P. Germain, F. Bach, A. Lacoste, and S. Lacoste- PAC-Bayesian theory meets Bayesian inference. Advances in Neural Information Processing Systems, 29, 2016.
M. Gil, F, Alajaji, and T. Linder. Rényi divergence measures for commonly used univariate continuous distributions. Information Sciences, 249:124-131, 2013.
B. Guedj. A Primer on PAC-Bayesian Learning. In Proceedings the second congress of the French Mathematical Society, 2019.
B. Guedj and P. Alquier. PAC-Bayesian estimation and prediction in sparse additive models. Electron. Statist., 7:264-291, 2013. doi: 10.1214/13-EIS771 URL https://doi.orge 1214/ 13-EJS771.
B. Guedj and L. Pujol. Still No Free Lunches: The Price Pay for Tighter PAC-Bayes Bounds. Entropy, 23(11), 2021. ISSN 1099-4300. doi: 10.3390/e21111529 100000////111////2
URL https://www http::///www.m......
M. Haddouche, B. Guedj, Rivasplata, and J. Shawe-Tayloe PAC-Bayes unleashed: generalisation bounds with unbounded losses. Entropy, 23(10):1330 2021.
E. Hazan. Introduction to online convex optimization. Foundations and Trendy@ in Optimization, (3-4):157-325, 2016.
E. Hazan, A. Agarwal, and S. Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, (642)):69-119) 2007.
M. Holland. PAC-Bayes under potentially heavy tails. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 2715-2724. Curran Associates, Inc., 2019. URL http:: nips cc/ paper/8558 8839//5399-10 www.85539-------e bayes- under under-potentialll--evvyee-eeeeee .dff.
G. Lever, F. Laviolette, and Shawe-Taylor. Distribattion-eeeenneee PAC-Bayes Priors. In M. Hutter, Stephan, V. Vovk, and Zeugmann, editors, Algorithmic Learning Theory, pages 119-133, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg, ISBN 978-3-642-1610887.

---

G. Lever, F. Laviolette, and J. Shawe-Taylor. Tighter PAC-Bayes Bounds through Distribution- Dependent Priors. Theor. Comput. Sci., 473:4-28, Feb. 2013. ISSN 0304-3975. URL https: //doi ott.loo.g//0../.......
tcs. 2012.10.01
L. Li, B. Guedj, and S. Loustau. A quasi-Bayesian perspective online clustering. Electronic Journal of Statistics, 12(2):3071 - 3113, 2018. doi: 10.1214/1-FE1S1499 URL https://doi. org/10. ////1....11/1111 1214/18-EJS144
L. Lobo, Del Ser, A. Bifet, and N. Kasabov. Spiking neural networks and online learning: An overview and perspectives. Neural Nenworks, 121:88-100, 2020.
A. Maurer, on the PAC Bayesian theorem. arXiv preprint cs/0411099, 2004.
D. A. McAllester. Some PAC-Bayesian theorems. In Proceedings of the eleventh annual conference Computational Learning Theory, pages 234. ACM, 1998.
D. A. McAllester. PAC-Bayesian model averaging. Proceedings of the twelfth annual conference on Computational Learning Theory, pages 164-170. ACM, 1999.
7. Mhammedi, P. Grünwald, and B. Guedj. PAC-Bayes Un-Expected Bernstein In- equality. In H. Wallach, H. Larochelle, A. Beygelzimer, F. Alché-Bue, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 12202-12213. Curran Associates, Inc., 2019. URL http://papers.nnt ceaapers.niss.ccpaperr cc/paper/ payT-pacbbyy----- wwwpsaaa-eeeeeeeeeeeeeeee -epscced---rrssttennnnne- iiteeiiiinnnuutttty...mm .dff.
A. Neelakantan, L. Vilnis, Q. V. Le, I. Sutskever, L. Kaiser, K. Kurach, and J. Martens. Adding gradient noise improves learning for very deep networks. arXiv preprint arXiv:1511.0688 2015.
R. K. Pace and R. Barry. Sparse spatial autoregressions. Statistics & Probability Letters, 33(3): 291-297, 1997.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
M. Perez-Ortiz, O. Rivasplata, B. Guedj, M. Gleeson, J. Zhang, J. Shawe-Taylor, M. Bober, and Kittler, Learning PAC-Bayes priors for probabilistic neural networks. Submitted., 202 la. URL https://arxiv org/ http://bs/11...../// 10304.
M. Perez-Ortiz, O. Rivasplata,
Herado-Hermandez B. Guedj, and Shawe-Taylor. Progress in self-certified neural networks. In NeurIPS 2021 workshop Bayesian Deep Learning [BDLJ, 2021b. pdf.
URL htt.::ttpp/baaeeiimeeeelaaaaaa httpeeppllaaainnoorrrrreo.e
M. Pérez-Ortiz, O. Rivasplata, J. Shawe-Taylorr, and C. Szepesvári. Tighter risk certificates for neural networks. Journal Machine Learning Research, 22, 2021.
A. Rakhlin and K. Sridharan. Online Learning with Predictable Sequences. S. Shalev-Shwartz and
I. Steinwart, editors, Proceedings of the 26th Annual Conference on Learning Theory, volume 30 of Proceedings of Machine Learning Research, pages 993-1019, Princeton, NJ, USA, 12-14 Jun 2013a. PMLR. URL https: httpa::///roceeeeee http://oooceee...eeee/// mlr press/v30 1300/akhlin13 html.
S. Rakhlin and K. Sridharan. Optimization, Learning. and Games with Predictable Se- quences. In C. Burges, L. Bottou. M. Welling, Z. Ghahramani, and K. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran As- sociates, Inc., 2013b. URL https: https:// ptropee/prooeedings neurips. cc/ patpp/p/1/////ieee F0004999aa0000090775555222-22002
.df.
O. Rivasplata, V. M. Tankasali, and C. Szepesvári. PAC-Bayes with backprop. arXiv preprint arXiv: /908.0088. 2019.
O. Rivasplata, Kuzborskij, C. Szepesvári, and Shawe-Taylor PAC-Bayes analysis beyond the usual bounds. Advances in Neural Information Processing Systems, 33: 118833-16855,, 2020.
12

---

Y. Seldin, N.
P. Auer, F. Laviolette. and J. Shawe-Taylor. B.C-BByes-Beenstere Inequality for Martingales and its Application to Multiarmed Bandits. In D. Glowacka, L. Dorard, and J. Shawe-Taylor editors, Proceedings of the Workshop and Exploitation 2, volume 26 of Proceedings of Machine Learning Research, pages 98-111, Bellevue, Washington, USA, 02 Jul 2012a. PMLR. URL https: ptttps://proceeddngg mlr. mlr.press/ v26/seldin12a. html.
On-line Trading of Exploration
Y. Seldin, F. Laviolette, N. Cesa-Bianchi, Shawe-Taylor, and Auer. PAC-Bayesian Inequalities for Martingales. IEEE Transactions on Information Theory, 58(12):788-7099, 2012b. doi:
10.11009/11222012221133
S. Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends@ in Machine Learning, 4(2):107-194, 2012.
Shawe-Taylos and R. C. Williamson. A PAC analysis of a Bayes estimator. In Proceedings of the 10th annual conference on Computational Learning Theory, pages 2-9, ACM, 1997.
J. W. Smith, E. Everhart, W. Dickson, W. C. Knowler, and R. S. Johannes. Using the adap learning algorithm to forecast the onset of diabetes mellitus. In Proceedings of the annual symposium computer application in medical care, page 261. American Medical Informatics Association, 1988.
W. Street, W. H. Wolberg, and O. I.. Mangasarian. Nuclear feature extraction for breast tumor diagnosis. In Biomedical image processing and biomedical visualization, volume 1905, pages 861-870. SPIE, 1993.
D. Svozil, V. Kvasnicka, and J. Pospichal. Introduction to multi-layer feed-forward neural networks. Chemometrics and intelligent laboratory systems, 39(1):43-62, 1997.
N. Thiemann, C. Igel, O. Wintenberger, and Y. Seldin. strongly quasiconvex PAC-Bayesian bound. In International Conference on Algorithmic Learning Theory, pages 466-492. PMLR, 2017.
I. O. Tolstikhin and Y. Seldin. PAC- MAC-Bayes-EEmpirical-eeneess
Inequality. In C. Burges, L.. Botton, M. Welling, Z. Ghahramani, and K. Weinberger, editors, Advances in Neural Information Process- ing Systems, volume 26, Curran Associates, Inc., 2013. URL https: /tt::///rroocco http://ooonnnnnnueeeeeee neurips. cc/ http//app/211//////// httee//////////////////////eeeee (
pdf.
D. van der Hoeven. T. van Erven, and W. Kotlowski. The many faces of exponential weights in online learning. In S. Bubeck, V. Perchet, and P. Rigollet, editors, Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 2067-2092. PMLR, 06-09 Jul 2018. URL https: http///oooeeeen..ccee////
waw.eediinnmmmm.......mmmm.. mlr httpss/w.......e.eeeeeeeeeeeeeee https////////eeeeeeeee htt/hhoveeen11. html.
Viallard, Germain, A. Habrard, and E. Morvant. general framework for the derandomization of PAC-Bayesian bounds. 2021. URL http:: /ttttps://arziie
08649.
O. Wintenberger. Stochastic Online Convex Optimization; Application to probabilistic time series forecasting. arXiv preprint arXiv: 100.00029, 2021.
T. Yang, L. Zhang, R. Jin, and J. Yi. Tracking slowly moving clairvoyant: Optimal dynamic regret of online learning with true and noisy gradient. In International Conference on Muchine Learning, pages 449- PMLR, 2016.
L. Zhang, T. Yang, rong jin, and Z.-H. Zhou. Dynamic Regret of Strongly Adaptive Methods. In Dy and A. Krause, editors, Proceedings the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 5882-5891. PMLR, 10-15 Jul 2018. URL https: http:///poeeeennssee/ee// mlr, press/v80/ //////00/2a//11// html.
P. Zhao, Y.-J. Zhang, L. Zhang, and Z.-. Zhou. Dynamic Regret of Convex and Smooth Functions. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 12510-12520. Cur- ran Associates, Inc., 2020. URL
neurips. httpp/cccpappee/2////ee11/ pdf.
M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pages 928-936. 2003.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] From the abstract to the conclu-
sion, we explicited our main assumption (bounded loss).
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Due to the theoretical nature of our contribution, we do not foresee immediate societal impact. anything, we certainly hope a better theoretical understanding of online learning algorithms can foster more responsible use by practitionners.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes] for all theorems and corollaries
(b) Did you include complete proofs of all theoretical results? [Yes] But deferred to Appendix D due to space constraints.
3. If you ran experiments...
(a) Did you include the code. data, and instructions needed reproduce the main perimental results (either in the supplemental material or as a URL.? [Yes] We have included the url in Sec. 5, note that this is anonymous repository.
(b) Did you specify all the training details (e.g.. g. data splits, hyperparameters, how they were chosen)? [Yes] All details are gathered in Sec. 5 so that all readers can replicate our experiments and validate our fundings.
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [No] We chose consider the classical online gradient descent as main comparison.
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes] We precised the machine we used in the Parammeters Settings' paragraph of Sec. 5.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] precised the origin of our datasets in the 'Datasets' paragraph of Sec. 5.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either the supplemental material as URL? [Yes] All the original code is available on the anonymised repository precised in Sec. 5.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "zFRX-jWPHWP", "reviewer": "Reviewer_zWwp", "summary": "This paper extends the classical PAC-bayes theory to the online learning setting, where the sequence of priors and posteriors can dynamically involve. The authors provide the first online version of training and testing bound, and drive OGD-like algorithm for this problem. ", "questions": "The questions are listed above. ", "limitations": "Yes.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1.\tThis paper considers PAC-Baysian learning in an online fashion, which is a natural extension of the classical PAC-Bayes results and to my knowledge is novel. \n2.\tThe main contribution in Theorem 2.2 seems to be very general, and even holds for non-convex bounded functions. \n3.\tExperimental results demonstrate the effectiveness of the proposed methods. \n\nWeaknesses: \n\n1. I find the paper is difficult to read especially for readers who are not very familiar with PAC-Bayes theory. I think a preliminary on the classical PAC-Bayes before introducing the online version in Section 2 would be super helpful, and a comparison between Theorem 2.2 and the classical PAC-Bayes theory is also needed. Moreover, could the authors provide the definition of absolute continuity (line 88)?\n\n\n2. I have the following questions: \n\nCan the authors provide more details about the LHS of the inequality in Theorem 2.2? More specifically, about the expectation inside (the expectation is taken wrt which random variables)?\n\nIf the data is iid, does Theorem 2.2 reduces to the classical conclusions? \n\nWhy corollary 3.1 suggests the algorithm in (1), if we perform the algorithm in (1), are their any follow up results (like regret)? And how do one compute the expectation in (1) in practice? (Line 181) Compared to OGD, is the algorithm more related to OMD or exponential gradient? \n\nIt seems to me that Corollary 3.1 and 3.2 are just Theorem 2.2 with different notations, and I’m not sure if it is necessary to repeat the same conclusion for several times. \n\nCould the authors be more clear in the introduction about the contributions of Section 4? \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "jj6rbmNtTMO", "reviewer": "Reviewer_orn2", "summary": "The paper employs the PAC-Bayesian proof methodology of Rivasplata et al. 2020 to provide bounds for online learning. To adapt the proof of Rivasplata et al. 2020 to the online learning setting, the loss is conditioned on the filtration of previous samples and the hypothesis space and space of posterior measures are replaced by cartesian producucts thereof. The moment generating function is bounded by recursively applying Hoeffding’s inequality for each i. In section 4, the paper discusses a disintegrated version of the bound for a hypotheses sampled from the posterior $Q$ instead of the expectation over $Q.$ Inspired by the presented PAC-Bayesian online learning bounds, the paper proposes an online learning algorithm which uses a Gibbs posterior that is iteratively updated. The learning method is evaluated on four simple binary classification and linear regression settings. \n", "questions": "* How would choose $\\lambda$?\n* All the related work I am familiar with that uses data dependent priors requires some additional assumption such as differential privacy. In corollary 3.3. You set P = Q such that the KL is 0. For instance, the differential privacy condition would not allow that. Can you explain why this is possible in your setting?\n", "limitations": "The mentioned limitations and the fact that the bound constitutes a trivial upper bound is not discussed.\nEthical consideration or negative societal impact discussions are not necessary since the work is theoretical.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strenghts:**\n* Proofs seem to be correct\n* Code provided\n* Extensions of the PAC-Bayesian methodology to the online learning setting is a relevant open problem\n**Weaknesses:**\n* Questionable experiment methodology:\n     * No error bars.\n     * How the experiments were conducted and how the hyper-parameters are chosen is hardly described.\n* Bound is extremely loose and diverges with m instead of converging to the empirical risk, neither of this is discussed in the paper.\n* The clarity of the paper could be significantly improved\n* A lot of the language in the paper is vague. First example in line 1 of the intro: ‘Batch learning is somewhat the dominant learning paradigm’\n* As described in the summary above, the proof methodology is a straightforward extension of Rivasplata et al. 2020 to the online settings. * The paper has very few take aways that would make it worthwhile to read.\n\nHere, I elaborate a bit more what I think the central problem with the paper is:\nTo my best understanding, the critical point in the paper is the trivial upper bound of the moment generating function (MGF) which results from applying Hoeffding’s inequality m times. The resulting term $\\frac{\\lambda m K^2}{2}$ grows linearly with $m$. The fact that $\\lambda$ appears in the enumerator here but in the denominator of $\\frac{\\log(1/\\delta)}{\\lambda}$ makes it impossible to make both terms converge. Either of the two terms diverge. To my best understanding, the trivial upper bound of the MGF also leads to the fact that the authors can set $Q=P$. Typically, to obtain a meaningful bound on the MGF, we either have to assume that $P$ is independent of the samples or some weaked criterion such as differential privacy.\n\nAll together, this paper is clearly below the standard of what I would expect from a NeurIPS paper.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "jbHz_C163vK", "reviewer": "Reviewer_Kjzo", "summary": "The paper extends the PAC-Bayes framework to an online setting, where in each time step, the algorithm is presented with one sample and outputs a posterior.\nThe framework is very general, in that the data distribution can be arbitrary (e.g., history-dependent), and the per-step posteriors are allowed to depend on previous posteriors and data.\n\n The generalization performance is measured on the new sample given the past. The main result (Thm 2.2.)  bounds this measure generalization by an “empirical error term”  and a complexity term - effectively showing a trade-off between fitting the current sample and generalizing to the next sample. \n\nThe paper then analyzes two special cases of the main theorem.\nCorollary 3.1. considers the case where the per-step posterior is based on previous data (not including the current sample) and provides guarantees for the posterior applied to the last sample.  Cor. 3.3. considers the case where the posterior at each step equals the current prior and provides guarantees for the posterior applied to the current sample.\nAs another special case, a disintegrated PAC-Bayes bound with isotropic Gaussian measures is proved (Cor. 4.1) and is used to derive Alg. 1. Numerical experiments show preferable performance compared to OGD. \n", "questions": "1. \nIn Thm 2.2., I found it hard to understand the conditions on the posterior sequence and its relation to the sample set $S$.   At first reading, the statement of Thm 2.2. seems to me as a “pointwise” bound per posterior sequence, instead of a simultaneous bound over all posteriors (as in standard PAC-Bayes bounds). This formulation means that the bound does not hold for sample ($S$) -dependent posteriors (to clarify,  by “pointwise”  I mean the statement is “for any posteriors sequences w.h.p. over the sampling of $S$, bound holds”, in contrast to “simultaneous”  where the statement should be “ w.h.p. over the sampling of $S$, for any posteriors sequences, bound holds”).  If this is the case, I believe the paper should discuss this and explain the challenges in obtaining a “simultaneous” bound in this setting.\n\n2. \nReading the proof of the theorem, it seems that $Q_i$ is defined as stochastic kernels (Def. C.1.)\nas in Rivasplata et al., 2020. This is not mentioned at all in the main body of the paper. To my understanding, the formulation in the main body differs from the one used in the proof. Shouldn't the main body of the paper use this definition?\n\n3.\nDoes the algorithm derived in the paper have ensured generalization guarantees? \nI.e., is the stochastic kernel that minimizes the RHS of the bound of Thm 2.2. given a dataset, has the generalization guarantees predicted by Thm 2.2.?\n In usual PAC-Bayes bounds, this is true, since the bound simultaneously holds for all posterior distributions. I wonder if the same conclusion can be drawn here.\nAs stated in “Rivasplata, Omar. PAC-Bayesian Computation. Diss. UCL (University College London), 2022”, Sect 3.2, the stochastic-kernel-based bound is not suitable for optimization. I have not found a discussion of this in the paper in the algorithm and experiments sections. \n\n3. \nIn line 143, and in Remark 3.2. the prior is said to be $\\hat{Q}_i,$ while in Eq. 1, the prior is $P_i$.  What is the reason for the discrepancy? \n\n4. Can the authors expand on the significance of Cor. 3.3.? How is it different from applying Chernoff’s bound per step?\n\n5. \nLines 181-191 (Analogy with Online Gradient Descent) - the claims here can be written more clearly and explicitly (e.g., can you show explicitly how the analogy holds? what is the relation between lambda and mu?)\n\n", "limitations": "The limitations have been discusse above.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\nI believe the work is original and well-motivated. \nThe extension of the PAC-Bayes framework to the online setting (and the analyzed performance measure) is logical and elegant. The framework requires very limited assumptions, allowing general data distributions and history-dependent posteriors. \n\nThe paper is well-written and clear.\nThe authors provide an adequate survey of related work.\n\nAll in all, I think the paper has the potential to make important contributions to the  PAC-Bayes literature.\n\n### Weaknesses\n1. Regarding the experimental results, I think it would be interesting to add a comparison with the prediction of the bounds.\n2.  I have a few issues (see questions below) that I would like the authors to clarify in their rebuttal.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Aljnl6LUvf7", "reviewer": "Reviewer_UW2Y", "summary": "Traditional PAC-Bayes analysis and algorithm design is centered around a single (prior, posterior) distribution pair and a batch of typically iid data. In this work, the authors develop the machinery for analyzing learning algorithms that are characterized by a *sequence* of priors and posteriors, where data need not be iid and can be processed one by one, i.e., an \"online\" PAC-Bayes scenario.\n\nThe substantive content of this paper includes a general-purpose error bound that can be used in the scenario described above, and applications of this bound to derive learning algorithms. Essentially, if we have a sequence of $m$ random data points, there will be $m$ ideal objective functions of interest (i.e., one expected loss for each random data point), and the main technical result of this work bounds the sum of these \"Gibbs risks\" (taking expectation of each expected loss WRT the random draw from the corresponding posterior) in a typical PAC-Bayes style, such that we have a high probability bound (over the draw of the data), which holds uniformly in the choice of the posteriors. The form of the upper bound is essentially the sum of $m$ traditional PAC-Bayes bounds, except that the empirical risk term for each bound is based on a single point, and thus it is possible to derive Gibbs posteriors that are optimal in the sense of minimizing the terms in the upper bound. The authors consider several specialized settings of priors, posteriors, and distribution families, drawing links between the procedures derived from their framework and existing techniques.", "questions": "Why does the bounded loss assumption arise, and what consequences are there to weakening this assumption? Considering my previous comments about naively stacking up traditional PB bounds, I would like to know if there is something inherent in allowing for data-dependent priors that means we need to naively bound a sum of (squared?) losses by $mK^{2}$.\n\n**Update:** the authors' response and revision has shed light on several key questions I had, and I have revised my score.", "limitations": "The authors are quite upfront about the limitations of their current approach (cumulative losses rather than regret, bounded losses, etc.) which is great, but as I mentioned earlier, there is virtually no information about why these limitations arise.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, the writing is quite clear, the paper is well-structured and it is easy to parse the main results of this work. The claims by the authors are sound, as they do not oversell their main result, and are quite thorough in their comparison with the existing literature.\n\nSince the idea of an online variant of PAC-Bayes itself is not particularly novel, the novelty and value of this paper should be in the execution, i.e., the means by which the authors obtain their general purpose online PAC-Bayes bound. However, the key ideas underlying their approach are completely swept under the carpet in the main paper. All the reader has to go on is a brief comment after Thm 2.2 telling us that the authors made use of a \"batch to online\" technique, leveraging much of the existing PB machinery in a sequential fashion. In my opinion the nature of the online PB bound obtained, the assumptions made (e.g., bounded losses), and how these points relate to the techniques used are the most important and interesting elements of a work of this nature, yet in its current form, the paper just \"gifts\" the reader with a new bound and discusses the most direct consequences of this bound.\n\nThis makes it somewhat difficult for me to evaluate the novelty and significance of this work. The authors lucidly relate the consequences of their main bound to the existing literature, but the more fundamental question of how one should/could make an online PB framework and the merits/demerits of the current approach (set against other possible approaches, if any) feels like a sidenote here. Let me expand just a bit more on this point.\n\nAssuming for now that we are satisfied with bounding the sum of expected losses, I feel like the bound in Thm 2.2 seriously lacks context. For example, if we assume that the priors are all data-independent, one could naively \"stack\" up $m$ traditional PB bounds ($m$ good events) applied to batches of size 1, sum these bounds, and then take a union bound. This would result in a $\\log(m/\\delta)$ term which is of course worse than the current $\\log(1/\\delta)$ term, but aside from the data-free priors, it is simple and yields a bound very similar to that of Thm 2.2, plus existing techniques can be easily used to deal with unbounded losses, etc. Of course, I know that data-dependent priors is a critical element of this work, but if this naive technique cannot be easily modified to allow for data-dependent priors, then I think that is a point the authors should communicate to the reader, and show how their approach alleviates this issue.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept