Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 
strengths_and_weaknesses: Strengths:

1.	This 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. 
2.	The main contribution in Theorem 2.2 seems to be very general, and even holds for non-convex bounded functions. 
3.	Experimental results demonstrate the effectiveness of the proposed methods. 

Weaknesses: 

1. 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)?


2. I have the following questions: 

Can 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)?

If the data is iid, does Theorem 2.2 reduces to the classical conclusions? 

Why 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? 

It 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. 

Could the authors be more clear in the introduction about the contributions of Section 4? 

questions: The questions are listed above. 
limitations: Yes.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
The 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.

 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. 

The paper then analyzes two special cases of the main theorem.
Corollary 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.
As 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. 

strengths_and_weaknesses: ### Strengths
I believe the work is original and well-motivated. 
The 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. 

The paper is well-written and clear.
The authors provide an adequate survey of related work.

All in all, I think the paper has the potential to make important contributions to the  PAC-Bayes literature.

### Weaknesses
1. Regarding the experimental results, I think it would be interesting to add a comparison with the prediction of the bounds.
2.  I have a few issues (see questions below) that I would like the authors to clarify in their rebuttal.


questions: 1. 
In 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.

2. 
Reading the proof of the theorem, it seems that $Q_i$ is defined as stochastic kernels (Def. C.1.)
as 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?

3.
Does the algorithm derived in the paper have ensured generalization guarantees? 
I.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.?
 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.
As 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. 

3. 
In 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? 

4. Can the authors expand on the significance of Cor. 3.3.? How is it different from applying Chernoff’s bound per step?

5. 
Lines 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?)


limitations: The limitations have been discusse above.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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. 

strengths_and_weaknesses: **Strenghts:**
* Proofs seem to be correct
* Code provided
* Extensions of the PAC-Bayesian methodology to the online learning setting is a relevant open problem
**Weaknesses:**
* Questionable experiment methodology:
     * No error bars.
     * How the experiments were conducted and how the hyper-parameters are chosen is hardly described.
* Bound is extremely loose and diverges with m instead of converging to the empirical risk, neither of this is discussed in the paper.
* The clarity of the paper could be significantly improved
* 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’
* 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.

Here, I elaborate a bit more what I think the central problem with the paper is:
To 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.

All together, this paper is clearly below the standard of what I would expect from a NeurIPS paper.


questions: * How would choose $\lambda$?
* 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?

limitations: The mentioned limitations and the fact that the bound constitutes a trivial upper bound is not discussed.
Ethical consideration or negative societal impact discussions are not necessary since the work is theoretical.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.

The 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.
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.

Since 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.

This 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.

Assuming 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.

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}$.

**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.
review_title: null

Meta-review: metareview: PAC-Bayes theory provides upper-bounds on the risk of aggregation of predictors in the batch setting. Many PAC-Bayes bounds are actually minimized by EWA (Exponentially Weighted Aggregation), but these bounds can also be applied on (slightly) sub-optimal aggregation procedure, and allow to control their level of sub-optimality: classical examples include Gaussian aggregation / variational Bayes.

There are also bounds on the regret of EWA in the online setting. However, while these bounds look quite similar to PAC-Bayes bound, they usually do not allow to work with alternate aggregation procedure such as Gaussian aggregation. Recently, some results allowed to study other aggregation rules, as in van der Hoeven et al. [2018] and Chérief-Abdellatif et al. [2019], but these results still impose strong constraint and cannot be applied to arbitrary aggregation strategies.

Here, the authors manage to extend totally PAC-Bayes bounds to the online setting. In other words, their Theorem 2.2 can be used to upper bound the regret of very general aggregation strategies, including of course EWA and Gaussian aggregation.

There was initially a disagreement between reviewers, based on the following:
1) on the one hand, the reviewers agree that Theorem 2.2 is a nice extension of PAC-Bayes bounds, and provides a generalization of existing results on EWA and Gaussian aggregation [see Reviewers Kjzo, orn2 and also UW2Y].
2) on the other hand, it is not clear whether there is a useful application of Theorem 2.2 can lead to new results beyond the "usual cases" EWA / Gaussian. Indeed, these are the two examples discussed by the authors [UW2Y].
After discussion, there was ultimately an agreement that even though some of the reviewers and myseld are still not totally convinced about 2), the nice construction of 1) justifies publication of the paper. I will therefore recommend to accept it.

Each of the reviewers raised many minor issues that the authors should take into account in the camera ready version (writing [zWwp, UW2Y] / experiments [Kjzo, orn2] / ...). I will add the following points:
- van der Hoeven et al. [2018] already contains a nice discussion on the extension of regret bounds beyond EWA, and share many similarities with this work (even though it does NOT contain a result such as Theorem 2.2). This paper is currently not cited by the authors. The authors should cite it, and discuss it.
- "The guarantees Chérief-Abdellatif et al. [2019] provided for SVB hold for Gaussian priors and posteriors and are valid for iid data, which is a particular case of our work." This is an incorrect and misleading statement: this paper is written in the same setting than the classical bounds on EWA. There is no stochastic assumption on the data in this paper (nor in van der Hoeven et al. [2018]).
confidence: Less certain
Decision: Accept