Recursive PAC-Bayes: A Frequentist Approach to Sequential Prior Updates with No Information Loss

General comments:

• We agree that Section 4 is too dense. We will take advantage of the tenth page offered for the final version to sparsify it.
• Concerning works on sequential posterior updates: we are sorry for brevity, let us elaborate. In works on sequential posterior updates the prior remains fixed, and the posterior is updated as the data are processed point-by-point. Our contribution is the sequential update of the prior. It can be directly combined with sequential posterior updates, because the excess loss (the first term in Eq. (2)) can be bounded sequentially by processing the corresponding data chunk point-by-point, exactly as it is done in works on sequential posterior updates. We will add this clarification to the paper.

Major:

1. Sequential posterior updates of Chugg et al. (2023) can be combined with our approach, as described above. Concerning their sequential prior updates in Section 6.5, we note that the denominator of the bound reduces to the sample size since the last prior update, meaning that there is no preservation of confidence information, and it is not different from other data-dependent priors. (This may not be clear from the way they have presented the bound, but if you check the proof of the bound, this limitation becomes evident. Specifically, the proof of Thm 4, which is used to prove Thm 40, only allows them to use samples since the last prior update to be able to swap the expectations in the second line on Page 11 in the JMLR version of the paper.) On the other hand, as explained in Lines 64-66, Haddouche and Guedj (2023) provide a generalization bound that applies to an aggregation of posteriors, and their denominator of the generalization bound depends on the number of aggregated posteriors, which can be as large as the number of data points. This is a very different object from a standard posterior studied in our work. In particular, the generalization power of their approach comes primarily from aggregation, and their method requires construction of a large number of posteriors to work. We do not see any close connection between their work and ours. The need to construct and maintain as many posteriors as the number of data points is a limitation in terms of computation and storage. As far as we can see, the authors have not conducted empirical evaluation of their method, presumably because of that.
2. Sequential construction of posteriors for every data point is computationally expensive, and experimental evaluations of this approach are highly limited. It would not have been possible to conduct such experiments given the size of the datasets we have worked with and the computational resources available to us.
3. We fully agree that Section 4 is too dense. We will use the tenth page given for the final version to implement your suggestions. (We still think that there is value in keeping the proofs in the body, luckily we will not need to compromise on that.)
4. Thanks a lot for your valuable suggestions! We will definitely use them to improve the writing.
5. Oh, yes. In Line 232 $S$ is sampled according to $\mathcal D$ and $\hat \pi_{t-1}$ is a sequence of prediction rules, one prediction rule per every sample in $S$, sampled according to $\pi_{t-1}$. The expectation is with respect to the two distributions. We will find a better way to present this.
6. As already mentioned above, bounding of the excess loss (the first term in Eq. (2)) can be done sequentially using martingale techniques, as in the work of Chugg et al. We will add a comment about this, but we prefer to avoid spelling out the technical details. We believe that for those who are familiar with these techniques, filling out the technical details would be trivial, but for those who are not, it can make the reading unnecessarily complicated and obstruct the main message of our work.
7. Yes, this is correct. And, yes, Thm 5 applies to any sequence $\pi_t^*$, so it is not a problem that we only get an approximation of the optimum.
8. It depends on the model to which Recursive PAC-Bayes is applied. For our model we borrowed the sampling procedure from Pérez-Ortiz et al., (2021). The details are described in Appendix B.2 and B.3. Since in our case $\pi_t^*$ is a probabilistic neural network represented by a factorized Gaussian distribution, it is easy to sample from.
9. That’s a good question. Again, it depends on the models to which Recursive PAC-Bayes is applied.
10. To clarify the confusion, replace the sentence in L320 with: “Similar to them we used probabilistic neural networks with weights represented by Gaussian distributions.”
11. There are two reasons to limit $T$. The first is that the added value of additional splits saturates (the improvement in going from $T=4$ to $T=6$ is already relatively small), so at some point the cost of the union bound on the number of splits (the $\ln T$ factor in the bound) will dominate the benefit of making extra splits. The second reason is computational. Once the improvements saturate, it makes little sense to split further. We will add experiments with $T=8$, which show that there is little gain relative to $T=6$.
12. The computational cost or gain depends on the models to which the bound is applied in two ways. First, if the cost of finding the (approximate) argmin in Eq. (4) is linear in the sample size, as in our experiments, then the difference between using or not using the recursion is small. If the method would have been applied to models, where the cost of finding the argmin is superlinear (e.g., kernel SVMs), then it could lead to substantial computational savings. The second source for potential computational gain is a trade-off with the statistical gain. Specifically, we could imagine a scenario, where compromising on the statistical gain and doing several recursion steps with more relaxed approximation of the argmin could still yield better and faster outcomes than doing a more precise single-step posterior optimization.

We thank the reviewer for their feedback.

1. We agree that Section 3 and, even more crucially, Section 4 are too dense. We will take advantage of the tenth page offered for the final version to sparcify writing.
2. The application to streaming and online learning is essentially straightforward, because what we do with the data is effectively sequential processing. We will add a comment to the paper.
3. We fully agree that the splitting proportions matter. Splitting half-half is sort of default, and our approach can be seen as a default generalization of it, because we recursively continue splitting the first half further. Of course, experimenting with other proportions would be a natural continuation, although we think that it might be more appropriate for a journal extension, both due to space constraints, and because explosion in the number of experiments risks distructing from the primary theoretical contribution of the paper.

There are numerous and significant misunderstandings in the review, which we clarify below one-by-one.

The first sentence of the Summary states: “The paper presents a novel PAC-Bayesian procedure that allows for sequential prior updates without splitting the training dataset.” This statement is incorrect. We do split the dataset into $T$ folds. The novelty of our work is it allows meaningful sequential processing of the folds without losing confidence information along the way. Prior work could only meaningfully process splitting in two folds, but even then it was losing confidence information.

Limitations of derived bounds:

• The derived bounds assume zero-one loss: this statement is not fully correct. The main contribution of our paper is the recursive decomposition of the loss in Eq. (2), $\mathbb E_{\pi_t}[L(h)] = \mathbb E_{\pi_t}[L(h) - \gamma_t \mathbb E_{\pi_{t-1}}[L(h)]] + \gamma_t \mathbb E_{\pi_{t-1}}[L(h)]$. It applies to any loss function (as long as the expectations are well-defined). Any suitable PAC-Bayesian bounds can be used to bound the two terms in the decomposition, as mentioned in Lines 167-169. We have restricted the presentation to the zero-one loss and used the most basic PAC-Bayes-kl bound, because otherwise the reader would get lost in variations of PAC-Bayes and miss the main message. But it is straightforward to use, say, PAC-Bayes-Empirical-Bernstein, and obtain a bound for any bounded loss function.
• The bounds are valid only at a specific time point $t$: First, we believe that there is a confusion between $t$, which indexes folds and recursion steps, and $i$, which indexes samples. Our bounds hold for all $t$, because we take a union bound (factor $T$ under the logarithm in Thm 5). Concerning bounds that hold for all $i$, it is straightforward to replace our bounds for the two terms in the decomposition in Eq. (2) with existing PAC-Bayes bounds that hold for all $i$. what $t$ represents: $t$ indexes the folds, which also correspond to recursion steps, because each recursion step processes a new fold.

Comparison with existing approaches: priors based on differential privacy, as in the work of Dziugaite et al., pursue a very different goal from our work. Their goal is to construct a set of interesting priors based on a fixed dataset without revealing too much information. Our goal is to refine the priors while moving from one chunk of data to the next, without losing confidence information.

Data splitting and recursive approach:

• It is unclear how this fundamentally differs from traditional data-splitting prior learning approaches: Traditional approaches split the data in two folds. Our approach supports meaningful splitting into an arbitrary number of folds.
• Increasing the number of split data sets with $T$ might lead to suboptimal prior distributions due to fewer data in early stages, potentially affecting generalization performance: Allocating little data to early stages is actually an advantage, as can also be seen from Tables 1, 2, and 3 in the paper (compare small values of $T$ with large values of $T$). This way few data are used to steer the prior into the right region, and then there is still a lot of data to obtain a tight bound.
• The decreasing bound values with increasing $T$: As you can see from Tables 2 and 3, the first rounds of recursion are used to steer the prior into the right region. The KL term in the first rounds is large, but with every subsequent round the contribution of this term to the final bound is decreased by a factor of $\gamma_t$. Therefore, the larger is the number of rounds, the smaller is the contribution of the first terms to the final bound. In the later rounds the prior is already good, and the KL term is very small (Tables 2 and 3).

Computational Efficiency: See our reply to Reviewer gLvU, Point 12.

Convergence: The decomposition of the excess loss into a superposition of binary variables is exact (see the illustration in Fig. 2 in the appendix). Therefore, if the excess loss converges to zero and $n\to\infty$, then the bound will converge to zero. Put attention that as $n\to\infty$ the $kl^{-1,+}$ terms in the bound converge to the value of the first argument, and not to zero. So, if the excess loss is zero, they will counterbalance $-\gamma_t$.

Experimental validation: we emphasize that the primary contribution of the paper is theoretical, and that it is a conference submission. Further experimental evaluation would be natural for a journal extension.

Questions:

• Interpretation of the generalization bound in Eq. (3): look at the decomposition of the loss in Eq. (2). The first term in Eq. (3) is a PAC-Bayes bound on the first term in Eq. (2), and the second is a recursive PAC-Bayes bound on the second term in Eq. (2).
• Why the summation above Eq. (3) goes from $j=1$ to $j=3$: The excess loss takes 4 values ($K=4$, see Line 223) and the corresponding binary decomposition is given in Line 196. You can also check the illustration in Fig. 2 in the appendix.
• Algorithm: Our algorithm is a recursive computation of the argmin in Eq. (4). The computation of the argmin depends on the model to which the bound is applied, which is external to the paper.
• Comparison to Dziugaite et al.: addressed above.
• Clarification concerning the experiments: the experiments apply the zero-one loss in multiclass classification. (Correct prediction gives loss zero, incorrect one.) It is NOT one-vs-all.

Finally, we would like to say that the score given by the reviewer “3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and/or incompletely addressed ethical considerations.” is unjustified. The reviewer has not identified any technical flaws; our evaluation is reasonable for a theoretical contribution to a conference; we have provided the code to reproduce the experiments and no reproducibility issues were raised; and there are no ethical considerations concerning our work.

Thank you for the detailed review and the feedback.

“sampling error between $\hat \pi_{t-1}^*$ and $\pi_{t-1}^*$” - It is true that this is a delicate point, but in fact no correction is required. We have explained it in lines 219-233, but we accept that the explanation might have been too dense. Let us explain it again. $\mathcal{E}\_t(\pi_t,\gamma_t)$ in Theorem 5 is a summation of PAC-Bayes-kl bounds on $\mathbb{E}\_{\pi_t}[F\_{\gamma_t|j}(h,\pi\_{t-1}^*)]$. By definition, $\hat F\_{\gamma\_t|j}(h,U\_t^{val},\hat \pi\_{t-1}^*)$, which involves the sampling according to $\pi_{t-1}^*$, is an unbiased sample of size $n_t^{val}$ from $F_{\gamma_t|j}(h,\pi_{t-1}^*)$. In contrast to standard applications of PAC-Bayes, where the samples are pairs $(X,Y)$, here the samples are triplets $(X,Y,h’)$, where $h’$ is sampled according to $\pi_{t-1}^*$, but this does not matter for the bound. We will emphasize this in the final manuscript.

Lines 214 & 231: thanks for the comments, we will polish the writing.

The definition of Recursive VI and comparison to Recursive PAC-Bayes could be an interesting direction for future work. We note, though, that while the two share the similarity of using KL regularization, the settings and objectives are quite different. PAC-Bayes aims to minimise the generalization error, whereas VI aims to compute the Bayesian posterior. Therefore, it is not immediately clear what could be a meaningful comparison.