Recursive PAC-Bayes: A Frequentist Approach to Sequential Prior Updates with No Information Loss
Authors: Yi-Shan Wu
Yijie Zhang
Badr-Eddine Chérief-Abdellatif
Yevgeny Seldin
Venue: NeurIPS 2024 spotlight (2024)
Keywords: PAC-Bayes
data-dependent prior
Primary area: learning_theory
TL;DR: We solve a long-standing open problem on how to do sequential prior updates in the frequentist framework (as it has always been done in the Bayesian framework) without losing information along the way.

Abstract: PAC-Bayesian analysis is a frequentist framework for incorporating prior knowledge into learning. It was inspired by Bayesian learning, which allows sequential data processing and naturally turns posteriors from one processing step into priors for the next. However, despite two and a half decades of research, the ability to update priors sequentially without losing confidence information along the way remained elusive for PAC-Bayes. While PAC-Bayes allows construction of data-informed priors, the final confidence intervals depend only on the number of points that were not used for the construction of the prior, whereas confidence information in the prior, which is related to the number of points used to construct the prior, is lost. This limits the possibility and benefit of sequential prior updates, because the final bounds depend only on the size of the final batch.

We present a novel and, in retrospect, surprisingly simple and powerful PAC-Bayesian procedure that allows  sequential prior updates with no information loss. The procedure is based on a novel decomposition of the expected loss of randomized classifiers. The decomposition rewrites the loss of the posterior as an excess loss relative to a downscaled loss of the prior plus the downscaled loss of the prior, which is bounded recursively. As a side result, we also present a generalization of the split-kl and PAC-Bayes-split-kl inequalities to discrete random variables, which we use for bounding the excess losses, and which can be of independent interest. In empirical evaluation the new procedure significantly outperforms state-of-the-art.

Recursive PAC-Bayes: A Frequentist Approach to Sequential Prior Updates with No Information Loss
Yi-Shan Wu University of South Denmark yswu@imada. sdu.di dk
Yijie Zhang
University of Copenhagen & Novo Nordisk A/S yizh@di.ku.. ku.dk
Badr-Eddine Chérief-Abdellatif CNRS, LPSM, Sorbonne Université, Université Paris Cité badr-eddine Seeriee--addllattifeee
Yevgeny Seldin
University of Copenhagen seldinØdi. ku. dk
Abstract
PAC-Bayesian analysis is frequentist framework for incorporating prior knowl- edge into learning. It was inspired by Bayesian learning, which allows sequential data processing and naturally turns posteriors from one processing step into priors for the next. However, despite two and a half decades of research, the ability to update priors sequentially without losing confidence information along the way remained elusive for PAC-Bayes. While PAC-Bayes allows construction of data- informed priors, the final confidence intervals depend only the number of points that were not used for the construction of the prior, whereas confidence information in the prior, which related to the number of points used construct the prior, lost. This limits the possibility and benefit of sequential prior updates, because the final bounds depend only on the size of the final batch.
We present a novel and, in retrospect, surprisingly simple and powerful PAC- Bayesian procedure that allows sequential prior updates with no information loss. The procedure is based on novel decomposition of the expected loss of random- ized classifiers. The decomposition rewrites the loss of the posterior as an excess loss relative to a downscaled loss of the prior plus the downscaled loss of the prior, which bounded recursively. As a side result, we also present generalization the split-kl and PAC-Bayes-splita inequalities to discrete random variables, which we use for bounding the excess losses, and which can of independent interest. empirical evaluation the new procedure significantly outperforms state-of-N -fth-----te-art.
Introduction
PAC-Bayesian analysis was born from an attempt derive frequentist generalization guarantees for Bayesian-style prediction rules (Shawe- Taylor and Williamson, 1997 McAllester, 1998). The motivation was provide way incorporate prior knowledge into the frequentist analysis of gener- alization. PAC-Bayesian bounds provide high-probability generalization guarantees for randomized classifiers. randomized classifier defined by a distribution p on a set of prediction rules H, which is used to sample prediction rule each time prediction is to be made. Bayesian posterior is an example of a randomized classifier, whereas PAC-Bayesian bounds hold generally for all randomized classifiers. Prior knowledge is encoded through a prior distribution π on H. and the complexity of a posterior distribution p is measured by the Kullback-Leible (KL) divergence from the prior, (L(p)()) r)) PAC- PAC-Bayesian generalization guarantees optimized by posterior distributions p that optimize a trade-off between empirical data fit and divergence from the prior in the KL sense.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Selection of a "good" prior plays an important role in the PAC- PAC-Bayesian bounds. If one manages to foresee which prediction rules are likely to produce low prediction error and allocate higher prior mass for them, then the bounds are tighter, because the posterior only needs to make a small deviation from the prior. But if the prior mass on well-performing prediction rules is small, the bounds are loose. A major technique to design good priors is to use part of the data to estimate a good prior and the rest of the data to compute a PAC-Bayes bound. It is known as data-dependent or data-informed priors (Ambroladze et al. 2007). However, all existing approaches to data-informed priors have three major disadvantages. The first is that the bounds are computed on "the rest of the data" that were not used in construction of the prior. Thus, the sample size in the bounds is only fraction of the total sample size. Therefore, empirically data-informed priors are not always helpful. In many cases starting with an uninformed prior and using all the data to compute the posterior and the bound turns to be superior to sacrificing part of the data for prior construction (Ambroladze et al. 2007 Mhammedi et al., 2019). The second disadvantage is that all the confidence information about the prior is lost in the process. In particular, a prior trained on a few data points is treated in the same way prior trained on lot of data. And third related disadvantage is that sequential data processing provides no benefit, because the bounds only depend on the size of the last chunk and all the confidence information from processing earlier chunks lost in the process.
Our main contribution is a new (and simple) way of decomposing the loss of a randomized classifier defined by the posterior. We write it as excess loss relative to downscaled loss of the randomized classifier defined by the prior plus the downscaled loss of the randomized classifier defined by the prior. The excess loss can be bounded using PAC-Bayes Eearyeca-miiiiaal---a
inequalities (Tolstikhin and Seldin 2013 Mhammedi et al., 2019, Wu et al. 2021 Wu and Seldin 2022), whereas the loss of the randomized classifier defined by the prior can be bounded recursively. The recursive bound can both use the data used for construction of the prior and "the rest of the data", and thereby preserves confidence information on the prior. Our contribution stands out relative to all prior work on PAC-Bayes, and in fact all prior work on frequentist generalization bounds, because it makes sequential data processing and sequential prior updates meaningful and beneficial.
We note that while several recent papers experimented with sequential posterior updates by using martingale-style analysis, in all these works the prior remained fixed and only the posterior was changing (Chugg et al. 2023 Biggs and Guedj] 2023] Rodríguez-Gale Gälvez et al. 2024). The work on sequential posterior updates is orthogonal to our contribution and can be combined with it. Namely, it is possible to apply sequential posterior updates in-between sequential prior updates. Another line of work used tools from online learning to derive PAC-Bayesian bounds (Jang al. (023) : and in this context Haddouche and Guedj] (2023) have used sequential prior updates, but their bounds hold for a uniform aggregation of sequentially constructed posteriors, which is different from standard posteriors studied in our work. The confidence bounds in their work come primarily from aggregation rather than confidence in individual posteriors in the sequence (the denominator of their bounds depends on the number of aggregated posteriors). The need to construct and maintain a large number of posteriors has a negative impact on the computational efficiency. Our work is the first one allowing sequential prior updates without loss of confidence information.
An additional side contribution of independent interest is generalization of the split-kl and PAC- Bayes-split-kl inequalities of Wu and Seldin (2022) from ternary to general discrete random variables. It based on a novel representation of discrete random variables as a superposition of Bernoulli random variables.
The paper is organized in the following way. In Section 2 we briefly survey the evolution of data- informed priors in PAC- PAC-Bayes and present our main idea behind Recursive PAC-Bayes; in Section we present our generalization of the split-kl and PAC-Bayes all incqualities, which are later used to bound the excess losses; in Section we present the Recursive PAC-Bayes bound; in Section 5 we present an empirical evaluation; and in Section 6 we conclude with discussion.
2 The evolution of data-informed priors and the idea of Recursive PAC-Bayes
In this section we briefly survey the evolution of data-informed priors, and then present our con- struction of Recursive PAC-Bayes. We consider the standard classification setting, with X being a sample space, ) a label space, H a set of prediction rules h X - V, and ((h(X), () = 1 (h(X) # Y) the zero-one loss function, where 1()) denotes the indicator function. We let D
2

---

denote a distribution on A' x y and S = ())... Yn)} an ii.d. sample from D. Let (hh) = -xxx,)>>/(((((x) Y] be the expected and (h,, S) = > f(h(x,), Yi) the empirical loss.
Let be distribution on H. A randomized classifier associated with P samples a prediction rule h according to p for each sample X X, and applies it to make a prediction h(X). The expected loss of such randomized classifier, which we call p. is (h)] and the empirical loss is En- (h, S)]. For brevity use [ to denote [+==p----
We use KL(pl(z) denote the Kullback-Leible divergence between two probability distributions, P and (Cover and Thomas 2006). For p. E [0, 1] we further use kl(pl = (PPp(p q)) to denote the Kullback- divergence between two Bernoulli distributions with biases and q.
The goal of PAC-Bayes is to bound 1 (h)). Below we present how the bounds on [x(4()) have
evolved. In Appendix A we also provide graphical illustration of the evolution.
Early work on PAC-Bayes used uninformed priors (McAllester 1998). An uniformed prior æ is distribution on H. that is independent of the data S. A classical, and still one of the tightest bounds, is the following.
Uninformed priors
Theorem 1 (PAC-Bayes-ki Inequality, Seeger 2002 on H that is independent of S and any ò E (0, I]:
Maurer 2004). For any probability distribution
P PP kl (RpLE((, 5)] B. (Z(0)) 2 (L(p|TT) + In(22//0)
n
where P is the set of all probability distributions on H. including those dependent on S.
A posterior p that minimizes (T)) has balance between allocating higher mass to prediction rules h with small [h,, S) and staying close to in the (L(p sense. Since x has be independent of S, typical uninformed priors aim "to leave maximal options open" for by staying close to uniform.
Data-informed priors Ambroladze al. (007) proposed split the data S into two disjoint sets, S = S1 US2, and use S1 to construct a data-informed prior ι and compute bound on E, [hh) using ı and S2. Since in this approach π is independent of S.g Theorem can be applied. The advantage that π can use S1 to give higher mass to promising classifiers, thus relaxing the regularization pressure (L(pI| π) and making it easier for p to allocate even higher mass to well sell-performing classifiers (those with small ih, S2)). The disadvantage is that the sample size in the bound (the n in the denominator) decreases from the size of S to the size of S2. Indeed, Ambroladze et al. observed that the sacrifice of S1 for prior construction does not always pay off.
Data-informed priors excess loss Mhammedi et al. (2019) observed that if we have already sacrificed S₁ for the construction of n. we could also use it to construct a reference prediction rule h", typically an Empirical Risk Minimizer (ERM) on S. They then employed the decomposition [h)] (h) - L(h")] L(h*)
and used S2 to give a PAC-Bayesian bound on E (h) - L(h)) and a singlc-hypothesis bound on L(h"). The quantity (h L(h")] ) is known as excess loss. The advantage of this approach is that when L(h*) is a good approximation of [,[L()),, the excess loss has lower variance than the plain loss [L)] and, therefore, is more efficient to bound, whereas the syngle-hypothesis bound on L(k") does not involve the (L(p](T) term. Therefore, it is generally beneficial to use excess losses in combination with data-informed priors. However, as with the previous approach, sacrificing S₁ to learn π and h² means that the denominator in the bounds (n in Theorem I reduces to the size of $z, and it does not always pay off. (We note that the excess loss is not binary and not in the [0, 1] interval, and in order to exploit small variance it is actually necessary to apply a inequality (Tolstikhin and Seldin 2013 Mhammedi al. 2019 Wu et al., 2021) or the PAC- MMC-Baye--splite
Baayes-Empirrcal--eensstiiii
inequality (Wu and Seldin 2022) rather than Theorem but the point about reduced sample size still applies.)
Recursive PAC-Bayes (new) We introduce the following decomposition of the loss
Ep[L(h) = (h!h(h) [Lhh)]] + 7 (Lh)).
(I)
3

---

As before, we decompose S into two disjoint sets S = S1 U S2. We make the following major observations:
The quantity E., [bk))] on the right is "of the same kind" as E [p]](h)] the left.
We can take uninformed prior xo and apply Theorem 1 (or any other suitable PAC-Bayes bound) to bound E [L(')]] (The KL term in the bound on [L(()] will be (T(T]((m))))
We can restrict to depend only on Sj, but still use all the data in calculation of the PAC- Bayes bound on E, [T.''' because ı is a posterior relative to no, and a posterior is allowed to depend on all the data, and in particular on any subset of the data. Therefore, the empirical loss E5 (h', S)] can be computed on all the data S, and the denominator of the bound in Theorem D can be the size of S, and not the size of S2. This is what we call preservation of confidence information on π,, because all the data S are used to construct a confidence bound on E., (hh)], and not just S2. This is in contrast to the bound on L(h*) ) in the approach of Mhammedi et al. (2019), which only allows to use S₂ for bounding (h*)). Note that while we use all the data S in calculation of the bound, we only use S and Ex, [LLL,, S:)] in the construction of R. Nevertheless, we can still use the knowledge that we will have n samples when we reach the estimation phase, i.e., when constructing æ we can leave the denominator of the bound at n, allowing more aggressive deviation from To.
If we restrict и depend only on St, then it is a valid prior for estimation of any posterior quantity [p][]] based on S2. Thus, if we also restrict y to depend only on S1, we can use any PAC- Bayes-Empiricall Drss--miprriaal-Beetttiii Bernstein-sttyle inequality or the PAC-Bayes-split-a inequality to estimate the
excess loss E, (h) yIE [L())) based on S2, i.e., based on E (E. S2) yI [E S2)]]]
If [L is good approximation of E. [h)] and [L)) is not close to zero, then the excess loss (h, - -E,, [M(')] (W] is more efficient bound than the plain loss [h)]]
In general, since [h]] is expected to improve on [L))( it is natural to set y < 1. However, 7 is not allowed to depend on S2, because otherwise ((h,,2) -F becomes a biased estimate of L(hh) [T()). We discuss the choice of y in more detail
(f,, S2)]
when we present the bound and the experiments
Biggs and Guedj (203)) have proposed a sequential martingale-style evaluation of a martingale version of [E - L(h")] and L(h*) in the approach of Mhammedi et al., but it has not been shown to yield significant improvements yet. The same "martingalization" can be directly applied to our decomposition, but to keep things simple we stay with the basic decomposition.
Finally, note that we can split S1 further and apply ① recursively to bound [L,))(
To set notation for recursive decomposition, we use No, T1 ................................ TT to denote sequence of distribu- tions on H. where To an uninformed prior and रт p is the final posterior. We use .., 7T to denote a sequence of coefficients. For 2 2 we then have the recursive decomposition
(2) To construct Mi. Tr we split the data into T non-overlapping subsets, S = S1 U..... We restrict Ty to depend on Utrain U'_1 S, only, and we use U. = - S. to estimate (recursively) Es, [h)] (see Figures and 2 in Appendix for a graphical illustration). Note that S, is used both for construction of and for estimation of E,,, [L(h]] (it is both in U.rain and U,Yal), resulting in efficient use of the data. is possible to use any standard PAC-Bayes bound, e.g., Theorem [1] to Bewseeeinsttetete
ET, [L(h)] = F.,, [L(h) - i + B. [I()
bound E,, [h)], and any PAC--ayes-EEppin Beste-rpprrialll-eeteineen style bound or the MAC-Bayes-splic bound to bound the excess losses E,, (T(h) - y [T.,___[[b]]]]] The excess losses take more than three values, in the next section we present generalization of the PAC-Bayes-split-kl inequality to general discrete random variables, which may be of independent interest. The Recursive PAC-Bayes bound is presented in Section 4
3 Split-kl and PAC-Bayes-split-kl inequalities for discrete random variables
The kl inequality is one of the tightest concentration of measure inequalities for binary random vari- ables. Letting kl-1,+(p,
(p, s) == max {v p E [0, 1] and kl(pllp) S }) denote the upper inverse of kl
and kl kl-1.-(0, ;= min {p p [0, 1] and kl(lllp) < } the lower inverse, it states the following.

---

Theorem 2 (kl Inequality (Lngfordd 2005 Foong et al. 2021
2022 ) Let Zz. Znn be indepen-
dent random variables bounded in the [0. 1J interval and with E [i]] for all Let p " =i==1 Z; be the empirical mean. Then, for any 5 E (0,
P P(p kl 1,+
0 1 In 1m=
5)
1
P P
1 - 1m (
1
S 8.
While the kl inequality is tight for binary random variables, it is loose for random variables taking more than two values due to its inability to exploit small variance. To address this shortcoming Wu and Seldin (2022) have presented the split-kl and PAC-Bayes-spli-kll inequalities for ternary random variables. Temary random variables naturally appear in a variety of applications, including analysis of excess losses, certain ways of analysing majority votes, and in learning with abstention. The bound of and Seldin is based on decomposition of ternary random variable into pair of binary random variables and application of the kl inequality each of them. Their decomposition yields tight bound in the binary and ternary case, but loose otherwise. The same decomposition was used by Biggs and Guedj 2023) to derive slight variation of the inequality, with the same limitations. We present novel decomposition of discrete random variables into superposition of binary random variables. Unlike the decomposition Wu and Seldin) which only applies in the ternary case, our decomposition applies to general discrete random variables. By combining it with kl bounds for the binary elements we obtain a tight bound. The decomposition is presented formally below and illustrated graphically in Figure in Appendix A
3.1 Split-kl inequality
Let Z E (bn,..., bx} } be (K + 1)-valued random variable with do bi < ... bg- For j e fl.....,K K} define 11 1 [( 2 by) and aj b, bj-1- Then bo E 02 Zij. For a sequence Zi.....,Z Zn of (K - 1)-valued random variables with the same support, let Zilj = (Z, 2 b,) denote the elements of binary decomposition of Z₁.
Theorem 3 (Split-kl inequality for discrete random variables). Let Zi.... Zn be i.i.d. random variables taking values in (bo....,bg with [Z.] any 8 (0,
p for all i. Let P1j 1 n Ei= Zily. Then for
P p bo
+
ag
kl 1,+
1,+
- In 55)
S6.
j=1
Proof. Let P1z = E |pp.1
then p = bo + ش
ajPly and
K
1,t ( 5)
K)
K ( In 5
)
p bo + Σ 1=1
aa k
< 3j pb 2 1,+
<
where the first inequality is by the decomposition of p and the second inequality is by the union bound and Theorem 2
3.2 PAC-Bayes-Split-H inequality
Let f H x Z + fbo...., be a (K + 1)-valued loss function. (To connect it to the earlier examples, in the binary prediction case we would have Z X' x y with elements = (X, Y) and [h, Z) ((h(X), Y), but we will need more general space Z later.) For j E (1..... K} let (()())) ( 2 by). Let Dz be an unknown distribution on 2. For E H let F(h) EDz (h, 2) and (h) EED Lf 2)]. Let S (Z,.... Zn} be an i..dd sample according to Dz and (h, S) = 1 Ei (1, Z.).
Theorem
Cee--Byys--pltttea Inequality). For any distribution a H that is independent of S and any ā E (0, 1):
K Ea (E,( KL(pl(T) + In 2K
))
P 3p SpEP:
bo
S 88,
n
j=1
where P is the set of all possible probability distributions on H. that can depend on S.
5

---

Proof. We have f(..)) bo + E/=ı agts(t))
and F(h) = bo + EØ= aj afFi,(h). Therefore,
K
B (h, KT(pp|=) + +ln y
P P [xp 2 bo +
Σ
ag
kl
kl 1,
j=1
1. Ep S)], (T.(p](T) + In 2Ky
< p and 3j (1)) 2 kl
S 8,
where the first inequality is by the decomposition of F and the second inequality is by the union bound and application of Theorem to Fi5 (note that fiz is a zero-one loss function).
4 Recursive PAC-Bayes bound
Now we derive Recursive PAC-Bayes bound based on the loss decomposition in equation 2 We aim to bound E., (h) Y.lE... [h]]]] which we denote by
- (h) L(h) (L(",,,((((h))) = EDxx [e(h(x), Y) (x(("(
where D TT-1 is product distribution on X x y H and h E H is sampled according to m- We further define
(h, (X,Y, = ((h(x), me (X), (-7,, 0, -/. 1}:
then F n superposition of binary functions. For this purpose we let {bujo: b b1j b13) {-71,, 0, 7o, 13
(h) EDxx. [f (h, Y,,, In order apply Theorem
4 represent fye as
and define (h, (X,Y,")) = (f (h, (X, Y,h() 2 dejg). We let F 11 (h) ExxT, ( (h, (X, Y, K()), then Fr.. (0) (h) - (b 1 (h).
Now we construct an empirical estimate of 11 (h). We first let #.-1 {11 .12 .12.-1 ,.... be a sequence of prediction rules sampled independently according to m--1- We define U. # (X,, Y, A:" ")==))==---- (X,, Yi) E Uyal). In words, for every sample (X;, Y.) UNaal we sample a prediction rule AT according to πz-1 and put the triplet (X;, Y,, 1: 1:1))))) in U o 4.-1-
The triplets (X,, Y,, 1-)) correspond to the random variables Z in Theorem 4 We note that | -VUNal #111 and we let val |1 We define the empirical estimate of F (1)) as Pr UN, o f nxal E(x.MMYEUTTOR S (X,Y, Note that
1D (1,, Upall o fr--)) = F (1)h),,))))),, therefore, we can use Theorem to bound E,, F2 1 (h)] using its empirical estimates. We are now ready to state the bound.
Theorem (Recursive PAC-Bayes Bound). Let S = U... ST be an i.i.d. sample split in an arbitrary way into T non-overlapping subsamples, and let Utrain = -U' S. and U - S.- Let n. = [.Sall Let mb; -i,-... . के. be a sequence of distributions on H. where म is allowed to depend on Uttmann but not the rest of the data. Let "2...., is allowed to depend on Utrain, but not the rest of the data. Fort E {l....,T) let Pe be a set of distributions on H. which are allowed to depend on Utssin Then for any 8 E (0, 1):
,....," .r be a sequence of coefficients, where
P(3t {1....,T) and T4 Pp E,,, [T(h)] 2 Bx( -
where (T( is PAC-Bayes bound on E., [L(h]] defined recursively as follows. For t
BI(m) = kl 1,+ Ex, (h,, S)], {T((m]|(0)) + In /
For t 2 we let Ee ET 7) denote PAC-Bayes bound Ez, [L,( 7 Brzr [I('']] given by
Ei(Te, 71) = - Σ (bels -113- 11+ E [Friss (h, Upal o #7 # )
KT KL (
+ In
61
ny
and then
B((m)) Ee(Tes ve) + Br (
(3)

---

Proof. By Theorem we have P( E P1 [L()]] 2 (I( - z. Further, by Theorem for 1 E (2,.... T we have P(3T,, E P. I,,,, 1 [[(}]]] 2 (T (t) T. The
theorem follows by a union bound and the recursive decomposition of the loss
Discussion
Note that Ti:..., m. can be constructed sequentially, but zं can only be constructed based the data in Utrain, meaning that in the construction of mi can only rely EITE (h, St 1t)- but not on E,, [Prris(h, Uyal o ft- Also note that S. is part of both Uprain and Uyal (see Figure Appendix for a graphical illustration). In other words, when we evaluate the bounds we can use additional data. And even though the additional data still use the knowledge that will get more
only be used in the evaluation stage, data for evaluation when we construct .p. For example, we can take
Ez [L,, (I
+ In 27 27yn
πj = arg min kl 1,+ 11+
(4)
and for 2 2
3
Em Prets (h, St a2 (I(x=|T
62' Vazul
mi = arg min
Σ ==1
(bals b1 k)
val
The empirical losses above are calculated on St corresponding to nÿ. but the sample sizes n; correspond to the size of the validation set U.al rather than the size of S,. This allows to be more aggressive in deviating with тद from - by sustaining larger (L( ( terms.
Similarly, 72....,
also be constructed sequentially, long "te only depends on Utrain (otherwise Ex,15(h S, o ) becomes a biased estimate of 16
We naturally want to have improvement over recursion steps, meaning (r(m)) ( 1) Plugging this into 3.. we obtain E(T) 7e) +
< 1i-1 ( which implies that we want Y' be sufficiently small satisfy 7t < 1 7. 1(72-))' At the same time, Yt should be non-negative. Therefore, improvement over recursion steps can only be maintained as long as (x( 7/e) < (T7-) We note that Yt By-1 1 term (3) linearly increasing in "ts whereas E(x), 7/) is decreasing in Nr. The value of that minimizes the trade-off depends the data. Even though it is not allowed to use U.val for tuning %t it is possible to take a grid of values of ? and a union bound over the grid, and then select the best value from the grid based the value of the bound evaluated on U.aal.
Experiments
In this section, we provide an empirical comparison of our Recursive PAC-Bayes (RPB) procedure
the following prior work: i) Uninformed priors (Uninformed), (Dziugaite and Roy 2017 ii) Data- informed priors (Informed) (Ambroladze al. 2007 Pérez-Ortiz al. [202]]: 1); ini Data-informed prior excess loss (Informed + Excess) (Mhammedi et al. 2219 Wu and Seldin 2022). All the experiments were run on laptop. The source code for replicating the experiments available at Githut
We start with describing the details of the optimization procedure, and then present the results.
5.1 Details of the optimization and evaluation procedure
We constructed कं. ..... गÿ sequentially using the optimization objective. (4 for क and (5) for тī to ,ÿ. and computed the bound using the recursive procedure in Theorem 5 There are few technical details concerning convexity of the optimization procedure and infinite size of the set of prediction rules H that we address next.

---

5.1.1
Convexification of the loss functions
The functions 1 (X, Y, ())) defined in Section are non-convex and non-differentiable: 2 ba1s) I (e(h(X), (X)), Y) 2 b(g)) In
fhe (X)) 1(f,, (h, approximate the external indicator function [= 20) by sig- =0)))=
order facilitate optimization, moid function (1; =0) = (1 + exp(ci (()(c( with fixed parameter c1 > 0 specified in Appendix B.3
Furthermore, since the zero-one loss (,, Y) is also non-differentiable. we adopt the cross-entropy loss, as in most modern training procedures (Pérez- Férez-Ortiz et al., 2021). Specifically, for k-class classification problem, let h X + R represent the function implemented by the neural network, assigning each class real value. Let ((X) be the assignment, with u, being the i-th value of the vector. To convert this real-valued vector into a probability distribution over classes, we apply the softmax function
R - A k-1, where (u)) exp(c2u,)/ E, exp(c2u;) for some C2 0
for each entry. The crosspy loss e00 R x [k] - R is defined by (", Y) = - lu)(o However, since this loss is unbounded, whereas the PAC-Bayes-kl bound requires losses within [0, 1). we enforce a [0, v-alledd cross-entropy loss by mixing the output distribution with a uniform distribution (u), i.e., (u); = (1 Pmin (omin))(()) (o();; + Pmin/ for all i [R] and for some Pmin > and then rescaling
[0, 1] by taking e (u, Y)
log(ō )/ log (k/ pmin).
We emphasize that in the evaluation of the bound (using Theorem 5). we directly compute the zero-one loss and the [ functions without employing the approximations.
5.1.2 Relaxation of the PAC-Bayes-kl bound
The PAC-Bayes-kl bound is often criticized for being unfriendly to optimization (Rodriguez-Gallez et al. 2024). Therefore, several relaxations have been proposed, including the PAC-Bayes-classic bound (McAllester) 1999). the PAC- AAC-Bayes-A bound (Thiemann et al.) 2017). and the PAC-Bayes-
quadratic bound (Rivasplata et al. 2019 Pérez-Ortiz et 2001)) among others. In our optimization
we have adopted the bound of McAllestrr 1999) instead of the kl-based bounds in Equation (5)
We again emphasize that in the evaluation of the bound we used the kl-based bounds in Theorem
5.1.3 Estimation of [.
Due to the infinite size of H. and lack of a closed-form expression for E [f S) and E,, (h, Upval o f appearing in Theorem we approximate them by sampling (Pérez. Ortiz et al. 202T). For optimization, we sample one classifier for each mini-batch during stochastic gradient descent. For evaluation, we sample one classifier for each data in the corresponding evalua- tion dataset. Due to approximation of the empirical quantities the final bound in Theorem reequiees an additional concentration bound. (We note that the extra bound is only required for computation of the final bound, but not for optimization of &t. .) Specifically, let मे = [h T1, ...,..., h } be m prediction rules sampled independently according to πT. Then for any function f(h taking values in [0, (which the case for L(h, 8) and 1T.15( (h, Uval )) and 8' E 10, have
log / 1))
P Ex; [f(h) 2 kl 11+
Σ
f(
1 m
5
is worth noting that E.; [h)] is evaluated for a fixed n;, meaning that there is no selection involved, and therefore no KL term appears in the bound above. We, of course, take union bound over all the quantities being estimated.
5.2 Experimental results
We evaluated our approach and compared it to prior work using multi-class classification tasks on MNIST (LeCun and Cortes 2010) and Fashion MNIST (Xiao et al. 2017) datasets, both with 60000 training data. The experimental setup was based on the work of Dziugaite and Roy (2017) and Pétez-Ortiz et al.] (202T). Similar to them we used Gaussian distributions for all the priors and posteriors, modeled by probabilistic neural networks. Technical details provided in
8

---

The empirical evaluation is presented in Table For the Uninformed approach, we trained and evaluated the bound using the entire training dataset directly. For the other two baseline methods, Informed and Informed Excess Loss, we used half of the training data to train the informed prior and an ERM h" for the excess loss, and the other half learn the posterior. For our Recursive PAC-Bayes, we chose 7/2 1/2 for all i, and conducted experiments with T = 2, 4, 6, 8 to study the impact of recursion depth. (Each value of I'' corresponded to a separate run of the algorithm and a separate evaluation of the bound, i.e., they should not be seen as successive refinements.) We applied a geometric data split. Specifically, for T = the split was (30000, 30000) points; for = 4, it was (7500, 7500, 15000, 30000); for T = 6 it was (1875, 1875, 3750, 7500, 15000, 30000); and for T = 8, it was (469, 469, 937, 1875, 3750, 7500, 15000, 30000). This approach allowed the early recursion steps, which had fewer data points, to efficiently learn the prior, while preserving enough data for fine-tuning in the later steps. Note that with this approach the value of nig ا = Σ ==t (ll1. which is in the denominator of the bounds in Theorem is at least E.
Table I: Comparison of the classification loss of the final posterior p on the entire training data, Ep (h, S)] (Train 0-1), and on the testing data, E, (h, S (Test 0-1), and the corresponding bounds for each method on MNIST and Fashion MNIST. We report the mean and one standard deviation over repetitions. "Unif." abbreviates the Uniform approach, "Inf." the Informed, "Inf. + Ex." the Informed Excess Loss, and "RPB" the Recursive PAC-Bayes.
MNIST
Fashion MNIST
Train 0-1
Test 0-1
Bound
Train 0-1
Test 0-1
Bound
Uninf.
.343 (2c-3)
.335 (3c-3)
.457 (2e-3)
.382 (2c-3)
.384 (2c-3)
.464 (2e-3)
Inf.
.377 (8c-4)
.371 (6e-3)
.408 (9c-4)
.412 (le-3)
.413 (6c-3)
.440 (1e-3)
Inf. + Ex
.157 (2e-3)
.151 (3e-3)
.192 (2e-3)
.280 (4e-3)
.285 (5e-3)
.342 (6e-3)
RPB T
.143 (2e-3)
.139 (3e-3)
.321 (3e-3)
.257 (3e-3)
.266 (5e-3)
.404 (3e-3)
RPB T = 4
.112 (Ie-3)
.109 (1e-3)
.203 (8e-4)
.203 (2e-3)
.213 (3e-3)
.293 (1e-3)
RPB T
.103 (Ie-3)
.101 (1e-3)
.166 (1e-3)
.186 (4e-4)
.198 (1e-3)
.255 (1e-3)
RPB T = 8
.101 (1e-3)
.097 (2e-3)
.158 (2e-3)
.181 (1e-3)
.192 (3e-3)
.242 (1e-3)
Table [ ssows that even with only = which corresponds to the data split used in the Informed and the Informed Excess Loss approaches, RPB achieves better test performance than prior work. As the recursion deepens, further improvements in both the test eтror and the bound are observed. We note that while the bound for T is looser compared the Informed Excess Loss method, deeper recursion yields bounds that are tighter. Overall, deep recursion provides substantial improvements in the bound and the test error relative to prior work.
Tables 2 and 3 provide a glimpse into the training progress of RPB with 7 = 8 by showing the evolution of the key quantities along the recursive process. Similar tables for other values of T are provided in Appendix B B.4, along with training details for other methods. The tables show an impressive reduction of the KL term and significant improvement of the bound as the recursion proceeds, demonstrating effectiveness of the approach.
Table 2: Insight into the training process of the Recursive PAC-Bayes for T 8 on MNIST. The table shows the evolution & + (TT),, and other quantities as the training progresses with t. Pr.
We define F.,, (h, Ural #) = Tt + Σ; (bel) bel
Uyal ft-1).
nx
E.. 3r (h, U.ral #))1
KL(a Im:_1)
(x(TT)
Test 0-1
mya
1
60000
.009 (3e-4)
.612 (9e-3)
.532 (.011)
2
59532
-0.06 (4e-3)
.031 (1e-3)
.114 (2e-3)
.421 (5e-3)
.215 (7e-3)
3
59063
.040 (3e-3)
.013 (9e-4)
.125 (3e-3)
.366 (2e-3)
.146 (3e-3)
58125
.049 (1e-3)
.005 (3e-4)
.099 (1e-3)
.267 (7e-4)
.120 (2e-3)
5
56250
.052 (4c-4)
.002 (lc-4)
.083 (1c-3)
.217 (1e-3)
.111 (2e-3)
6
52500
.051 (1c-3)
.001 (4c-5)
.076 (1c-3)
.185 (1e-3)
.104 (2e-3)
7
45000
.050 (Ic-3)
8c-4 (6e-5)
.073 (Ie-3)
.166 (1e-3)
.099 (Ie-3)
8
30000
.050 (1e-3)
6e-4 (4e-5)
.074 (1e-3)
.158 (2e-3)
.097 (2e-3)

---

Table 3:
Insight into the training process of the Recursive PAC-Bayes for T = 8 on Fashion MNIST.
t
EM, [F (h, U. o fc--1)
KL(m; |mi-1)
Be(Ti)
Test 0-1
1 60000
.003 (7c-5)
.733 (7c-3)
.686 (8c-3)
2 59532
-0.043 (8c-3)
.023 (6e-4)
.104 (9c-3)
.470 (8c-3)
.309 (7e-3)
3
59063
.083 (4e-3)
.008 (3c-4)
.161 (3e-3)
.396 (4c-3)
.242 (Ie-3)
4
58125
.090 (3e-3)
.004 (5e-4)
.142 (4e-3)
.341 (5e-4)
.216 (5e-3)
5
56250
.093 (3e-3)
.001 (2e-4)
.126 (3e-3)
.297 (4e-3)
.204 (4e-3)
6
52500
.090 (1e-3)
6e-4 (6e-5)
.117 (le-3)
.265 (1e-3)
.195 (3e-3)
45000
.990 (1e-3)
4e-4 (2e-5)
.115 (1e-3)
.248 (Ie-3)
.195 (Se-4)
8
30000
.090 (1e-3)
4e-4 (le-5)
.117 (le-3)
.242 (1e-3)
.192 (3e-3)
Discussion
We have presented the first PAC-Bayesian bound that supports sequential prior updates and preserves confidence information on the prior. The work closes long-standing gap between Bayesian and Frequentist learning by making sequential data processing and sequential updates of prior knowledge meaningful and beneficial in the frequentist framework, as it has always been in the Bayesian framework. We have shown that apart from theoretical beauty the approach is highly beneficial in practice.
The Recursive PAC-Bayes framework is extremely rich and powerful, and leads to numerous direc- tions for future research, some of which we briefly sketch next.
The decomposition in 2 applies to any loss function, including unbounded losses. It would be interesting to find additional applications to it.
While we have restricted ourselves to the zero-one loss function to illustrate the use of PAC- Bayes-split-kl. the results can be directly generalized to any bounded loss function by replacing PAC-Bayes-split-kt with JAC-Bayes-Fmpirrcaa Bernstein Empsiricll-Brrsttein or PAC-Bayes- CCC-BBaes-Unexppee Seaxseeced-Beenstteee and deriving the corresponding analogue of Theorem [ (which is straightforward).
We have shown that the bound works well with geometric split of the data, but there are many other ways to split the data which could be studied.
There is also a lot of space for experimentation with optimization of Yr-
It would be interesting to study how the bound will perform in sequential learning settings, where the data arrives sequentially, and thus the partition is dictated externally.
There are many interesting research directions from the computational perspective. We note that for base models with linear computational complexity (c.g.. neural networks) the overhead of recursion is relatively small and optimization time of Recursive PAC-Bayes is comparable to processing all data at once or in two chunks (as in data-dependent priors). For base models with superlinear computational complexity (e.g., kernel SVMs) sequential training of several small models in the recursion may actually be cheaper than training a big model based on all the data. Moreover, since the bound in Theorem 5 holds for any sequence of distributions Tő mi:..... nÿ. the optimization in equation (5) is allowed to be approximate. Considering that the improvement very significant, there is space to look at the trade-off between statistical power and computational complexity. Namely, it may potentially be possible to relax the approximation of arg min in equation (5) to gain computational speed-up at the cost of only small compromise on the bounds and test losses.
of the bounds and the test loss relative to prior work
We note that Theorem 2 to bound E.,, [h)] using all the data, and apply the recursive decomposition (2) starting from मं. Whether this would yield an advantage relative starting the recursion at TT as we did, remains to be studied.
possible to start the recursion at πT. Namely, is possible use, for example.
Acknowledgments and Disclosure of Funding
YW acknowledges support from the Novo Nordisk Foundation, grant number NNF21 OC0070061.
YZ acknowledge Ph.D. funding from Novo Nordisk A/S. BECA acknowledges funding from the ANR grant project BACKUP
10

---

References
Amiran Ambroladze, Emilio Heraade-ermández, and John Shawe-Taylor. Tighter PAC-Bayes bounds. In NeurIPS, 2007.
Felix Biggs and Benjamin Guedj. Tighter PAC-Bayes generalisation bounds by leveraging example difficulty. In Proceedings on the International Conference on Artificial Intelligence and Statistics (AISTATS), 2023.
Ben Chugg, Hongjian Wang, and Aaditya Ramdas. A unified recipe for deriving (time-uniform) PAC-Bayes bounds. Journal of Machine Learning Research, 24(372), 2023.
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley Series in Telecommu- nications and Signal Processing, 2nd edition, 2006.
Gintare Karolina Dziugaite and Daniel M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAT), 2017.
Andrew Foong, Wessel Bruinsma, David Burt, and Richard Turner. How tight can pac-bayer be in the small data regime? In NeurlPS, 2021.
Andrew Y. K. Foong, Wessel P. Bruinsma, and David R. Burt. A note on the chernoff bound for random variables in the unit interval. arXiv preprint arXiv. 22X5:22055077800 2022.
Maxime Haddouche and Benjamin Guedj. PAC-Bayes generalisation bounds for heavy-tailed losses through supermartingales. Transactions on Machine Learning Research Journal, 2023.
Kyoungseok Jang, Kwang-Sin Sung Jun, Ilja Kuzborskij, and Francesco Orabona. Tighter PAC-Bayes bounds through coin-betting. In Proceedings of the Conference on Learning Theory (COLT), 2023.
John Langford. Tutorial on practical prediction theory for classification. Journal of Machine Learning Research, 6, 2005.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URL http://yann lecun cooom/xxbbmmiss//
Andreas Maurer. A note on the PAC-Bayesian theorem. arXiv preprint cs/041 1099, 2004.
David McAllester. Some PAC-Bayesian theorems. In Proceedings of the Conference on Learning Theory (COLT), 1998.
David McAllester. Some PAC-Bayesian theorems. Machine Learning, 37, 1999.
Zakaria Mhammedi, Peter Grünwald, and Benjamin Guedj. PAC-Bayes un-expected Bernstein inequality. In NeurlPS, 2019.
María Pérez-Ortiz, Omar Rivasplata, John Shawe-Taylon and Csaba Szepesvári. Tighter risk certifi- cates for neural networks. Journal of Machine Learning Research, 2021.
Omar Rivasplata, Vikram M Tankasali, and Csaba Szepesvari. Pac-bayes with backprop. arXiv preprint arXiv:1908.073300 07338, 2019.
Borja Rodríguez-Gäätvzz Ragnar Thobaben, and Mikael Skoglund. More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity. Journal of Machine Learning Research, 25(110), 2024.
Matthias Seeger. PAC-Bayesian generalization error bounds for Gaussian process classification. Journal of Machine Learning Research, 3, 2002.
John Shawe-Taie TaalorTTTToraa and Robert C. Williamson. PAC analysis of Bayesian estimator. In Proceed- ings of the Conference on Learning Theory (COLT), 1997.
Niklas Thiemann, Christian Igel, Olivier Wintenberger, and Yevgeny Seldin. A strongly quasiconvex PAC-Bayesian bound. In Proceedings of the International Conference on Algorithmic Learning Theory (ALT), 2017.
11

---

Iyy Tolstikhin and Yevgeny Seldin. MMC-BBass-EmmrriiclBBmmsss Bermssienn inequality. In NeurIPS, 2013.
Yi-Shan Wu and Yevgeny Seldin. Split-kl and PAC-Bayes-split-kl inequalities for ternary random variables, NeurIPS, 2022.
Yi-Shan Wu, Andres Masegosa, Stephan Sloth Lorenzen, Christian Igel, and Yevgeny Seldin. Chebyshev-cantelli pac-bayes-bennet inequality for the weighted majority vote. In NeurIPS, 2021.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNISTT: a novel image dataset for bench- marking machine learning algorithms. arXiv preprint arXiv: 2017.
12

---

A Illustrations
In this appendix we provide graphical illustrations of the basic concepts presented in the paper.
Uninformed (McAllester, 1998)
S
E, [L(A))
Informed Prior (Ambroladze 2007)
p
$
E [L()))
πt;
Informed Prior Excess Loss (Mhammedi al., 2019)
P
F,p [T, I(hh);; 1.(1))
Jy :72
E,, [4((A]]
Recursive PAC-Bayes 7 2
Em, L(h) Y2 En, [((b]]
S
S2
S3
:72
Ex, [L(hh)
Recursive PAC Bayes 7= 3
J2 :7s
Fry, [L(h) Y2 [thh)]
S
((h) ys E, [.(0]]
S
S₂
Sg
S
Ex, [L(h)
R2 :3ss
Recursive PAC-Bayes T
k., [400 (o00)-mhe [600]]
S
IT' :74
B., |100 -we. [400]]
ST
P., (600 (00,00000
Figure I: Evolution of PAC-Bayes. The figure shows how data used by different PAC-Bayes approaches. Dark yellow shows data used directly for optimization of the indicated quantities. Light yellow shows data involved indirectly through dependence on the prior. Light green shows data used for estimation of the indicated quantities. In Recursive PAC-Bayes data are released and used sequentially bhunk-by-chume
as indicated by the dashed lines. For example, in the T 4 case Ez, [L) is first evaluated on S₁ to construct πı and 72, then in the first recursion step on S₁ U U2, in the second step on S₁ S2 S3, and in the last step on all
13

---

Eng [L(h]] E,
((hk) Vy Y3EN,IL(hN]] Yallm (1ch) - 12 [LCHO]] + y3721Em, [L(h)]
Visualization of the data split:
S 71
S
7
753
Figure 2: Recursive Decomposition into Three Terms. The figure illustrates recursive decom- position of Eng [L]]]] into three terms based on equation 2 and a geometric data split, as used in our experiments. The bottom line illustrates which data are used for construction of which dis- tribution: S1 for πı; S2 for т2: and S3 for и3- The brackets above the data show which data are used for computing PAC-Bayes bounds for which term: S₁ U S2 U.S. for E., [L(]]]: S2 S3 for En, (L()) - 12 [Lh'']]] )]; and S3 for Ex, [L(h) ?3E,, [h'']] Note that a direct computation of PAC-Bayes bound on Ex, [Lh]] would have only allowed to use the data in S3, shown by the black dashed line. The figure illustrates that recursive decomposition provides more efficient use of the data. We also note that initially we start with poor priors, and so the KL( || term for small is expected to be large, but this compensated by a small multiplicative factor II and
availability of lot of data U Sy for computing the PAC-Bayes bound. For example, Ex,, [L(h] is multiplied by Ya72 and we can use all the data for computing PAC-Bayes bound on this term. By the time we reach higher I, the priors m get better, and the <T.(Te||===>)) term in the bounds gets much smaller, and additionally the bounds benefit from the small variance of the excess loss. With geometric split of the data, we use little data to quickly move म; good region, and then we still have enough data for a good estimation of the later terms, like En, [h)) ralEm, [L(h']]]
Z b2
2 = 1
Z 1 = 1
Z = 0
bo
b
b2
b3
a1
a2
d3
Figure 3: Decomposition of a discrete random variable into a superposition of binary random variables. The figure illustrates decomposition of discrete random variable Z with domain of four values by < bj < by < by into superposition of three binary random variables, Z = bo + Σラ= 73 A way to think about the decomposition is to compare it to progress bar. In the illustration Z takes value by, and so the random variables Zμ and Zi corresponding to the first two segments "light up" (take value 1), whereas the random variable Z corresponding to the last segment remains "turned off"" (takes value 0). The value of Z equals the sum of the lengths ay of the "lighted up" segments.
14

---

B Experimental details
In this section, we provide the details of the datasets in Appendix [811 our neural network architectures in Appendix B.2 and other details in Appendix B.3 on both datasets in Appendix B.4
We provide further statistics for all the methods
B.1 Datasets
We perform our evaluation on two datasets, MNIST (LeCun and Cortes 2010) and Fashion MNIST (Xiao et al. 2017). We will introduce these two datasets in the following.
B.1. MNIST
The MNIST (Modified National Institute of Standards and Technology) dataset is of the most renowned and widely used datasets in the field of machine learning, particularly for training and testing in the domain of image processing and computer vision. It consists of a large collection of handwritten digit images, spanning the numbers O through 9.
The MNIST dataset comprises a total of 70,000 grayscale images of handwritten digits, where the training set has 60,000 images and the test set has 10,000 images. Each image in the dataset 28x28 pixels, resulting
total of 784 pixels per image. The images are in grayscale, with pixel values ranging from 0 (black) to 255 (white). Each image is associated with a label from 0 to 9, indicating the digit that the image represents. The images typically stored in single flattened array of 784 elements, although they can also be represented in a 28x28 matrix format.
B.1.2 Fashion MNIST
The Fashion MNIST dataset contemporary alternative to the traditional MNIST dataset, created to provide more challenging benchmark for machine learning algorithms. It consists of images of various clothing items and accessories, offering a more complex and varied dataset for image classification tasks.
The Fashion MNIST dataset contains total of 70,000 grayscale images, where the training has 60,000 images and the test set has 10,000 images. Each image in the dataset is 28x28 pixels, resulting in total of 784 pixels per image. The images are in grayscale, with pixel values ranging from (black) to 255 (white). Each image is associated with one of 10 categories, representing different types of fashion items. The categories are: 1. T-shirt/top 2. Trouser 3. Pullover Dress 5. Coat 6. Sandal 7. Shirt 8. Sneaker 9. Bag 10. Ankle boot. Similar to MNIST, the images are stored in single flattened array of 784 elements but can also be represented 28x28 matrix format.
B.2 Neural network architectures
For all methods, we adopt family of factorized Gaussian distributions to model both priors and posteriors, characterized by the form Nww, aI) where Rd denotes the mean vector, and represents the scalar variance. We use feedforward neural networks for the MNIST dataset (LeCun and Cortes 2010), while using convolutional neural networks for the Fashion MNIST dataset (Xiao et al. 2017
Both feedforward neural network and convolutional neural network probabilistic, and each layer has factorized (i.c. mean-field) Gaussian distribution.
Our feedforward neural network has the following architecture:
1. Input layer. Input size: 28 x 28 (flattened to 784 features).
2. Probabilistic linear layer 1. Input features: 784, output features: 600, activation: ReLU.
3. Probabilistic linear layer 2. Input features: 600, output features: 600, activation: ReLU,
Probabilistic linear layer 3. Input features: 600, output features: 600, activation: ReLU.
5. Probabilistic linear layer 4. Input features: 600, output features: 10, activation: Softmax.
Our convolutional neural network has the following architecture:
15

---

1. Input layer. Input size: 1 x 28 x 28.
Probabilistic convolutional layer 1. Input channels: 1, output channels: 32, kernel size: 3x3, activation: ReLU.
3. Probabilistic convolutional layer 2. Input channels: 32, output channels: 64, kernel size: 3x3, activation: ReLU.
4. Max pooling layer. Pooling size: 2x2.
5. Flattening layer. Flattens the output from the previous layers into single vector.
6. Probabilistic linear layer 1. Input features: 9216, output features: 128, activation: ReLU.
7. Probabilistic linear layer 2 (output layer). Input features: 128, output features: 10, activation: Softmax
B.3 Other details in the experiments
General for all methods The methods comparisons are trained and evaluated using the procedure described in Section and visually illustrated in Figure [] We will provide some further details for each method later in the following. For all methods comparison, we apply the optimization and evaluation method described in Section 5.1 For the approximation described in Section 5.1.1 we set the parameters 6j = 02 = The lower bound for the prediction Pmni le 5. The in our bound the PAC-Bayes-clase classic bound by |MAAlleter in replacement of PAC- AAC--Baes-kl when doing optimization. Note that for all methods, in Section 5.1.3 We also allocate the budget for the union bound for the estimation such that these estimations in the bound controlled with probability least 1 - 5', where
and all the other methods is selected to be 8 0.025. As mentioned in Section 5 5.2
also have to estimate the empirical loss of the posterior [x described
chose 8' 0.01. Therefore, the ultimate bounds for all methods hold with probability at least 1 - 8'. Note that we do not consider such bounds during optimization but only when estimating the bounds.
For methods, we adopt a family of factorized Gaussian distributions to model both priors and posteriors of all the learnable parameters of the classifiers, characterized by the form = Nww, o)) where w Rd denotes the mean vector, and a represents the scalar variance. For all methods, we initialize an uninformed prior xo = A (wo, IoI) that is independent of data, where the mean randomly initialized, and the variance is initialized to 0.03 (Pérez-Ortiz et al.) 2021).
In the training process of all methods in experiments, we the batch size to 250, the number of training epochs to 200, and use stochastic gradient descent with a learning rate of 0.005 and momentum of 0.95.
Uninformed priors We take Ty defined above as the uninformed prior. We then learn the posterior p from the prior using the entire training dataset S, applying PAC-Bayes bound. We evaluate the bound using, again, the entire training dataset S.
Data-informed priors We start with the same to as the uninformed prior. We train the informed prior #i using S₁ with |S1] = |S|/2 by minimizing a PAC-Bayes bound. The posterior p then learned using the informed prior n and the subset S2 with [S2] = |S|/2, again by minimizing PAC-Bayes bound. The bound evaluated using S2.
Data-informed priors + excess loss We train the informed prior and the reference classifier h" using Sj that contains half of the training dataset. Ti obtained by minimizing PAC-Bayes bound with the uninformed prior To while the reference classifier h is obtained by an empirical risk minimizer (ERM). The posterior p is obtained by minimizing a PAC-Bayes bound on the excess loss between p and h. The prior used in the bound for both training and evaluation is the data-informed prior ग.. Therefore, the data for both training and evaluation p must be the other half data Sa.
B.4 Further results for the experiments
In this section, report some more statistics for all methods.
16

---

For all methods, to calculate the classification loss of on the testing data, E, S (Test 0-1), l), we sample one classifier for each data. The train 0-1 loss for all methods computed on the entire training dataset S, while the test 0-1 loss for all methods is computed on the test dataset Siest
B.4.1 Recursive PAC-Bayes
We report the additional results of Recursive PAC-Bayes on MNIST with T 2 in Table T in Table 5 and T = in Table 6 We report Recursive PAC-Bayes on Fashion MNIST with T = 2 in Table in Table and in Table
Table 4: Insight into the training process of the Recursive PAC-Bayes for T = 2 on MNIST.
n
En, E,, [F (h, U. ft-1))
Be(T;)
Test 0-1
nya
60000 2
1
.024 (3e-5)
.370 (1e-3)
.254 (2e-3)
30000
.013 (3e-3)
.024 (1c-4)
.136
(3e-3)
.321 (3e-3)
.139 (3e-3)
Table 5: Insight into the training process of the Recursive PAC-Bayes for T = 4 on MNIST.
t
E (5 (h, U.al a #c-1))
KL(n; (mi-1) nyal
Be(T;)
Test 0-1
1
60000
.023 (8e-5)
.374 (1e-3)
258 (le-3)
2
52500
-4e4 (le-3)
.025 (3e-4)
.118 (1e-3)
.305 (1e-3)
.126 (2e-3)
3
45000
.053 (Ie-3)
.002 (9c-5)
.087 (2e-3)
240 (2e-3)
.114 (Ie-3)
4
30000
.054 (le-3)
.001 (2e-5)
.083 (le-3)
.203 (8e-4)
.109 (le-3)
Table 6: Insight into the training process of the Recursive PAC-Bayes for T MNIST.
nt
E., (x (h, Uyall ft-1))
KI[( (m;-1) ny
B₂(T?)
Test 0-1
1
60000
.019 (7e-5)
.25 (1e-3)
.311 (3e-3)
2
58125
-0.013 (1e-3)
.032 (6e-4)
.128 (2e-3)
.341 (3e-3)
.139 (1e-3)
3
56250
.050 (1e-3)
.003 (1e-4)
.093 (6e-4)
.264 (1e-3)
.117 (2e-3)
4
52500
.051 (1e-3)
.001 (6e-5)
.080 (9e-4)
.122 (5e-4)
.108 (2e-3)
5
45000
.051 (le-3)
9c-4 (3e-5)
.076 (2e-3)
.182 (1e-3)
.104 (6e-4)
6
30000
.049 (Ie-3)
7e-4 (3e-5)
.074 (Ie-3)
.166 (Ie-3)
.101 (Ie-3)
Table 7: Insight into the training process of the Recursive PAC-Bayes for 2 on Fashion MNIST.
t
n
E., (,,, (h, U.aal fc-1))
KI(5; (mi-1) ny
(7)
Be(T²)
Test 0-1
60000
.011 (3e-5)
.466 (1e-3)
.389 (5e-3)
2
30000
.064 (3c-3)
.013 (2c-4)
.171 (4c-3)
.404 (3c-3)
.266 (5e-3)
Table 9: Insight into the training process of the Recursive PAC-Bayes for = 6 on Fashion MNIST.
nyaa
Ex, PB, (h,, U.yal l #)-1))
KL(a (m?_1) nya
(x(TT)
Test 0-1
1
60000
9e-3 (8e-5)
534 (4e-3)
.462 (5e-3)
2
58125
.013 (6e-3)
.023 (1e-3)
.151 (4e-3)
.418 (5e-3)
.254 (6e-3)
3
56250
.091 (3e-3)
3e-3 (4e-4)
.141 (2e-3)
.350 (3e-3)
.223 (1e-3)
4
52500
.090 (2c-3)
9c-4 (9c-5)
.121 (1e-3)
.296 (1e-3)
.207 (1e-3)
5
45000
.090 (Ie-3)
6c-4 (3e-5)
.117 (2e-3)
.655 (2c-3)
.199 (2e-3)
6
30000
.093 (1e-3)
5c-4 (2c-5)
.122 (1e-3)
.255 (1e-3)
.198 (Ie-3)
B.4.2
Uninformed priors
We report the additional results of uninformed priors MMcAllester 1998) on MNIST and Fashion MNIST in Table TQ As described earlier in Section Section and Section B.3 we evaluate the bound using the entire training set.
17

---

Table 8: Insight into the training process of the Recursive PAC-Bayes for T = 4 on Fashion MNIST.
t
ER, [F (h, U. o fc-1))
KL(m; (mi-1)
7t)
Be(TT)
Test 0-1
1
60000
.011 (le-4)
.476 (4e-3)
.397 (6e-3)
2
52500
.032 (6c-4)
.017 (9c-4)
.147 (2e-3)
.386 (3c-3)
.240 (4e-3)
3
45000
.100 (3c-3)
3e-3 (Ie-4)
.138 (5e-3)
.331 (4c-3)
.222 (5e-3)
4
30000
.095 (2e-3)
7e-4 (5e-5)
.128 (2e-3)
.293 (1e-3)
.213 (3e-3)
Table 10: Further details to compute the bound for the uninformed prior approach on MNIST and Fashion MNIST.
Bound
Test 0-1
MNIST F-MNIST
.343 (2e-3)
.023 (4e-5)
.457 (2e-3)
.335 (3e-3)
.382 (2e-3)
.011 (8e-6)
.46 (2e-3)
.384 (5e-3)
B.4.3 Data-informed priors
We report the additional results of data-informed priors (Ambroladze et al. 2007) on MNIST and Fashion MNIST in Table [1] As described earlier in Section 2 Section [ and Section B.3 evaluate the bound using S2 that is independent of the data-informed prior TT
Table 11: Further details to compute the bound for the data-informed prior on MNIST and Fashion MNIST.
(,, (2))
Bound
Test 0-1
MNIST F-MNIST
.376 (8e-4)
8e-4 (9e-6)
4088 (9e-4)
.371 (6e-3)
.412 (1e-3)
4e-4 (7e-6)
.44 (le-3)
.413 (6e-3)
B.4.4
Data-informed priors + excess loss
We report the additional results of data-informed priors excess loss (Mhammedi et al. 2019 on MNIST and Fashion MNIST in Table and 13 As described earlier in Section 2 Section S and Section B.3 we evaluate the bound using Sa that is independent of the data-informed prior ж and the reference prediction rule h². The bound is composed of two parts: a bound on the excess loss of P with respect h* (Excess bound) and single hypothesis bound on h (h* bound). We report the two components of the bound in Table [2] We provide further details to compute these bounds from the losses of their corresponding quantities Table 13]
Table 12: Details to compute the bound for the data-informed prior and excess loss on MNIST and Fashion MNIST. The table shows the bound on the excess loss of p with respect to h" (Excess bound) and a single hypothesis bound on (h* bound).
Ex. Bound
h² Bound
Bound
Test 0-1
MNIST F-MNIST
.122 (1c-3)
.029 (4c-4)
.192 (2e-3)
.151 (3c-3)
.196 (5e-3)
.145 (Ie-3)
.342 (6e-3)
.285 (5e-3)
Table 13: Further details to compute the bound for the data-informed prior and excess loss on MNIST and Fashion MNIST. The table shows the empirical excess loss [,, (h, /t", S2)], where we define (hh, h² h²) = i(h, S2) _(h S2), and its bound (Excess Bound). It also shows the empirical loss of the reference prediction rule L(h", 82) and its bound. The computation of such bound does not involve the KL term.
E,lÂ(h, h², ,S))
KL(plma) S2
Ex. Bound
i(h", S2)
ht Bound
Bound
MNIST F-MNIST
-0.011 (3e-3)
.035 (5e-4)
.162 (1e-3)
.026 (4e-4)
.029 (4e-4)
.192 (2e-3)
.104 (6e-3)
.018 (5e-4)
.196 (5e-3)
.122 (Ie-3)
.145 (1e-3)
.342 (6e-3)
18

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We tried to write an abstract and an introduction that reflected the rest of the paper accurately possible.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We have tried to be as honest as possible in setting the framework of this theoretical work and have explicitly mentioned the limiting assumptions the paper, e.g. i.idd data.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
19

---

Answer: [Yes]
Justification: We have clearly stated the assumptions made in the paper, and our theoretical results are accompanied by detailed proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The datasets are available online and we have tried to provide as much detail possible to make experiments transparent and reproducible.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
20

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The code has been uploaded, the datasets open source.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips.co. ccippi.cc guwdes/ddeeeee CooeeSumeeieeeeeeeeeee ssi onyolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: We have introduced many different notations to accurately specify the different data splits and parameters used in our framework, and have tried detail the optimization procedure to make our results as understandable as possible.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We provided for each experiment the corresponding standard deviations over different runs of the experiments. Please refer to the tables in the paper for more details.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
21

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CL, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
As mentioned in the paper, all the experiments were run on a personal laptop.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer:
[Yes]
Justification:
We have violated any of the points in the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is theoretical paper with no specific societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
22

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The open source datasets used in the paper were properly cited, namely MNIST (LeCun and Cortes 2010) and Fashion MNIST (Xiao et al. (017))
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
23

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We have not released any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/codeemoodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper did not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Our paper did not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
25


Reviews:
[{"review_id": "SjuBTnhEUt", "reviewer": "Reviewer_oqWC", "summary": "PAC-Bayes bounds are extended to the recursive or streaming case by breaking the expected loss into ($a$) expected loss on the previous step times a discounting factor plus ($b$) current expected loss minus $a$. An extension of the kl inequality to many-valued (here 4-valued) random variables provides a bound on $b$.", "questions": "The objective in (4) is very similar to the VI objective, especially with 0-1 loss replaced by cross-entropy as in section 5.1.1. (I think replacing $kl^{-1,+}$ with Euclidean divergence and $n^{val}_t$ with $|S_t|$ would yield the VI update.) It would be useful to see an experimental comparison between recursive PAC-Bayes and recursive VI.", "limitations": "none noted", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This is impressive work. It's technically sound and makes a major theoretical advance.", "weaknesses": "The proof of thm 5 doesn't account for sampling error between $\\hat{\\pi}^*_{t-1}$ and $\\pi^*_{t-1}$. The inequality used in line 244 refers only to $\\pi^*_{t-1}$ but the definitions of \n$\\mathcal{E}\\_{t}$ \nand \n$\\\\hat{F}\\_{\\\\gamma_{t} | j}$\ninvolve \n$\\hat{\\pi}^{*}\\_{t-1}$. \nThe method in section 5.1.3 can resolve this but it should be included in the theorem (or the theorem should be rewritten without sampling).\n\n214: \"can depend on $S$\" is conceptually helpful but technically superfluous. What's really meant is that because the quantification is over all of $\\mathcal{P}$ one is free to choose $\\rho$ in a way that depends on $S$.\n\n231: the summation index is misleading because it implies the index set is the product of $U^{val}\\_t$ \nand $\\hat{\\pi}\\_{t-1}$, \nwhereas the actual index is $((X,Y),h')$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed review and the feedback.\n\n“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.\n\nLines 214 & 231: thanks for the comments, we will polish the writing.\n\nThe 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.", "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": "", "extra_scores": {}}, {"review_id": "Geh5CHuIG7", "reviewer": "Reviewer_Kzqj", "summary": "- The paper presents a novel PAC-Bayesian procedure that allows for sequential prior updates without splitting the training dataset.\n- The proposed procedure is based on a novel decomposition of the expected loss of randomized classifiers, which rewrites the posterior loss as an excess loss relative to a downscaled loss of the prior plus the downscaled loss of the prior, which is recursively bounded.\n- The paper generalizes the split-kl and PAC-Bayes-split-kl inequalities to discrete random variables.\n- The authors confirmed that their PAC-Bayes learning method outperforms state-of-the-art methods in empirical evaluations.", "questions": "In addition to the concerns raised in the Weakness section, I would appreciate it if you could also address the following questions:\n\n- Can you provide a qualitative interpretation of the generalization error bound given by Equation (3)?\n- Why does the summation part in \\(\\mathcal{E}\\) above Equation (3) only sum from \\(j=1\\) to \\(j=3\\)?\n- The specific algorithm of the proposed method is not very clear. Could you provide an algorithm table?\n- What are the advantages of the proposed method compared to traditional PAC-Bayes prior pre-training approaches that fully use the training data (e.g., Dziugaite et al., 2017; Dziugaite et al., 2018)? If there is a reason for not conducting a theoretical or experimental comparison with these methods, please explain.\n- You mentioned calculating the 0-1 loss. Is this correct that you conducted binary classification using a one-vs-all approach?", "limitations": "This study is foundational research aimed at improving the generalization by PAC-Bayes learning with prior optimization, and these aspects are discussed in the Broader Impact paragraph. The datasets used are open datasets such as MNIST and Fashion MNIST, which suggests that there are no significant concerns regarding potential negative social impacts.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper addresses a practically important topic of adaptively optimizing the prior in PAC-Bayes learning to reduce pre-training costs while enhancing generalization performance.\n- The attempt to derive recursively bounded generalization error bounds for the optimization steps includes originality.", "weaknesses": "First, I want to note that I find it difficult to fully grasp the motivation, utility, and specific algorithms of this paper from the current manuscript, which may lead to some of the points in the Weaknesses and Questions sections being based on misunderstandings. If there are any misunderstandings, I would appreciate it if the authors could correct them and provide clearer explanations beyond what is presented in the paper.\n\n- **Limitations of Derived Bounds**:\n  - As one of the limitations in this paper, the derived bounds assume 0-1 loss, limiting their applicability to binary classification problems. \n  - The bounds are valid only at a specific time point $t$. Considering that most existing PAC-Bayes bounds provide insights into generalization error independent of iteration, this bound appears to be valid under very restrictive conditions.\n  - The definitions of symbols throughout the paper seem ambiguous, affecting readability. For instance, it is unclear what $t$ represents—whether it is training iteration, epoch, or a separate recursion step. Clarification is needed.\n\n- **Comparison with Existing Approaches**:\n  - The main issue addressed by this paper is that traditional data-dependent priors in PAC-Bayes learning are constructed by splitting the training data, thus discarding some information. However, alternative approaches not discussed in this paper use optimization methods like SGLD or Entropy-SG(L)D, which guarantee differential privacy while optimizing the prior using all training data (e.g., Dziugaite et al., 2017; Dziugaite et al., 2018). Although these methods might result in looser bounds or smaller probabilities of bound validity, they have shown good performance in similar experimental settings. While these methods differ in being pre-training approaches rather than recursive, they share the goal of optimizing the prior without splitting the training data. The lack of comparison with these methods leaves the usefulness of the proposed approach insufficiently demonstrated.\n\n- **Data Splitting and Recursive Approach**:\n  - The paper still splits data according to the value of $T$. It is unclear how this fundamentally differs from traditional data-splitting prior learning approaches. In the split strategy proposed in Sec. 5, 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.\n  - There is no discussion on the tightness of the bounds derived in Theorem 5, especially for $t \\geq 2$. Intuitively, even though $\\gamma_{t}$ is multiplicative, the cumulative addition of the KL term may result in looser bounds as $t$ increases unless $\\gamma_{t}$ or/and the complexity value is very small. The decreasing bound values with increasing $T$ observed in the experiments may be due to the simplicity of datasets like MNIST, where KL values are initially very small. If there is another reason, it should be explained.\n\n- **Computational Efficiency**:\n  - There is no mention of computational efficiency. It seems that increasing the number of recursive steps would lead to higher computational costs.\n\n- **Convergence of generalization bounds**:\n  - It is unclear whether the bound guarantees convergence with respect to the sample size $n$, i.e., whether it converges to zero as $n \\rightarrow \\infty$. If we only consider Equation (3), even if $n_{t}^{\\mathrm{val}} \\rightarrow \\infty$ and $B_{t-1} = 0$, it seems that $-\\gamma_{t}$ would remain in $\\mathcal{E}_{t}$, preventing convergence. Is this a desirable property for a generalization error bound?\n\n- **Experimental Validation**:\n  - The experiments are limited to very simple datasets like MNIST and Fashion-MNIST, which is insufficient to convincingly demonstrate the utility of the proposed algorithm. More diverse and complex datasets should be tested to validate the approach comprehensively.\n\nCitation:\n- Dziugaite et al., 2017: Dziugaite et al. Data-dependent PAC-Bayes priors via differential privacy. NeurIPS2018. https://arxiv.org/pdf/1802.09583\n- Dziugaite et al., 2018: Dziugaite et al. Entropy-SGD optimizes the prior of a PAC-Bayes bound: Generalization properties of Entropy-SGD and data-dependent priors. ICML2018. https://arxiv.org/pdf/1712.09376", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "There are numerous and significant misunderstandings in the review, which we clarify below one-by-one.\n\nThe 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.\n\nLimitations of derived bounds:\n- 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.\n- 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$.\nwhat $t$ represents: $t$ indexes the folds, which also correspond to recursion steps, because each recursion step processes a new fold.\n\nComparison 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. \n\nData splitting and recursive approach: \n- 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.\n- 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. \n- 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). \n\nComputational Efficiency: See our reply to Reviewer gLvU, Point 12. \n\nConvergence: 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$.\n\nExperimental 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.\n\nQuestions:\n- 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).\n- 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.\n- 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. \n- Comparison to Dziugaite et al.: addressed above.\n- 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.\n\nFinally, 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.", "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": "", "extra_scores": {}}, {"review_id": "Arlk8JysK7", "reviewer": "Reviewer_ZaLx", "summary": "Data-dependent priors are crucial for the tightness of PAC-Bayesian bounds in several scenarios. However, using a fraction of the data to train the prior reduces the sample size of the bounds, which can sometimes be counter-productive. This fact also discourages sequential prior updates since the bounds can rapidly degenerate. This paper elegantly solves these problems using a \"prior-dependent\" excess loss bound inspired by Mhammedi et al. (2019). Their approach allows sequential prior updating without confidence loss and surpasses previous data-dependent prior building techniques in standard benchmark datasets. \n\nAdditionally, they generalize ternary split-kl PAC-Bayes bounds to general discrete random variables.", "questions": "See Weaknesses.", "limitations": "No significant limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1- The main result, Theorem 5, is a significant contribution to the study of data-dependent priors with many possible applications.\n\n2- The experimental results (Table 1) show a remarkable improvement over previous methods.", "weaknesses": "I find no major weaknesses, just a couple of comments:\n\n1- Sections 3 and 4 are very dense in notation and difficult to read (I recognize there is not much the authors can do about that).\n\n2- Since Recursive PAC-Bayes is developed for sequential prior updating, it would be nice (if possible) to have some discussion about its possible applications to streaming/online learning scenarios.\n\n3- In the experiments with data-dependent priors 1/2 of the data was used for building the prior. However [1] shows that the proportion of data used for prior building is crucial. It would be nice to have experiments with different data splitting proportions (also, I think [1] is a relevant paper that could be cited as related work).\n\n\n\n[1] Dziugaite, G. K., Hsu, K., Gharbieh, W., Arpino, G., & Roy, D. (2021). On the role of data in PAC-Bayes bounds. In International Conference on Artificial Intelligence and Statistics (pp. 604-612). PMLR.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback.\n\n1. 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.\n2. 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.\n3. 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.", "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": "", "extra_scores": {}}, {"review_id": "eUYjzVRFWn", "reviewer": "Reviewer_gLvU", "summary": "The paper investigates a type of PAC-Bayes bounds that makes use of sequential prior updates, without loosing the appearance of the cardinality of the whole training set.", "questions": "Any of my major comments above, with a priority to items 1 and 11, and commitment to follow the suggestions of clarification in Section 4.", "limitations": "This is fundamental work; no potential negative or environmental societal impact other than making the pdf available!", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Sequential updates feel natural in that context, not only statistically as demonstrated here, but also computationally. Indeed, having sequential Monte Carlo methods in mind, it might be easier to approximate a complex posterior by slowly modifying the prior. \n* The first three sections of the paper are very nicely written, and agreeable to read for a non-expert.\n* While the proofs are straightforward consequences of earlier results, the key theorem has practical importance and, to my limited knowledge and following the authors' claim, seems to have been missed by earlier investigations.\n* Overall, I enjoyed reading the paper, and feel like I learned something.", "weaknesses": "## General comments\n* The crux of the paper, Section 4, is too dense and hard to read, to the point of hiding some of the degrees of freedom of the paper, and making it tedious to follow the paper line by line and check the claims. This can easily be solved; see major comments. \n* After a very nice historical introduction, I was expecting a down-to-earth comparison to recent work on PAC-Bayes and sequential posterior updates, as listed in p2 L60-68. Maybe my lack of expertise made me miss a point, but I think these approaches are introduced and discarded in a single high-level paragraph, which feels unfair compared to the (nice) long pedagogic account of Section 2.\n\n## Major\n1. p2 L60 to L68: this paragraph cites several competing martingale-based approaches to PAC-Bayes inequalities with sequential posterior updates, which are discarded a bit quickly for me to understand why. Could you elaborate and give some details on the claims of e.g. Section 6.5 of [Chugg et al., 2023] and [Haddouche and Guedj, 2023]? For instance, you could give an informal version of their main claim, and point to the limitations you address. \n2. Relatedly, why are these approaches not featured in the experimental section? Maybe the answer to bullet 1. will make it clear.\n3. I would avoid bullet lists on p4 and p7, and put the proofs of Theorems 3 and 4 in the appendix; all of this would create space for Section 4 to breathe. I was enjoying reading the paper until Section 4, and then bumped into the daunting density of Section 4 on p6, due in part to too many inline formulas and overly compact definitions. The risk is to lose many readers here, while this is the crux of the paper. With the space gained, you could e.g. use centered displays for the most important definitions. \n4. With the space created, still in Section 4, I would take time to introduce objects one by one. I believe $(\\gamma_t)$, for instance, is used before Theorem 5 without definition. Implicitly, we understand in Theorem 5 that they can be predictable functions. We should thus, for instance, have a definition of $\\gamma_t$ as a sequence of real-valued functions adapted to a filtration. Then we could introduce, for $\\gamma\\in\\mathbb{R}$, the function $f_{\\gamma}: \\mathcal{H} \\times \\mathcal{X} \\times \\mathcal{Y} \\times \\mathcal{H} \\rightarrow \\mathbb{R}$ by $f_{\\gamma}(h, x, y, h')=...$, instead of the more compact definition of $f_{\\gamma_t}(h, (X,Y,h'))$, which saves space but intertwines the definitions of several objects, functions and random variables. Similarly, I would start by defining a filtration to be able to state which function is measurable w.r.t. to what $\\sigma$-algebra.\n5. Relatedly, L232 I am not sure I understand over what distribution the expectation is taken. Slower definitions would likely make it clearer.\n6. Section 4 feels like it could be rewritten in terms of (super)martingales, although it's a matter of taste, I guess, and I think I saw a comment in the paper that you wanted to avoid doing so. However, not explicitly using martingales makes it harder to connect to previous work. For instance, your theorem 5 bears resemblance with a maximal inequality for martingales such as Ville's, as in [Chugg et al., 2023], could you comment on this?\n7. Can you confirm that I understand well Section 5.1? Basically, you describe how you approximate the sequential optimization problems in (4), for $t=1, ..., T$. This does create a sequence $(\\pi^*_t)$, to which you can apply Theorem 5. Actually, Theorem 5 does not care whether $(\\pi^*_t)$ optimizes (4), so it is OK to actually approximate the optimal sequence (4).\n8. Section 5.1.3: how do you draw $h_{t,1}\\sim\\pi_t^*$? Is $\\pi_t^*$ easy to draw from by construction?\n9. Section 5: as a side remark, I am wondering whether sequential Monte Carlo techniques could help sequentially approximating $\\pi^*_t$; see e.g. [[Chopin and Papaspiliopoulos, An Introduction to Sequential Monte Carlo, Springer, 2020]](https://link.springer.com/book/10.1007/978-3-030-47845-2).\n10. p8 L320 what is meant by \"Gaussian distributions modeled by probabilistic neural networks\"?\n11. Why do you not split the data more than in 6 shards? What happens if we go \"online\" and make $n$ shards of $1$ data point? What differs then from the \"online PAC-Bayes\" approach of [Haddouche and Guedj, 2023]?\n12. Is there any computational gain in splitting the dataset and sequentially optimizing $\\pi_t$ instead of doing plain batch PAC-Bayes, on top of the statistical gain in the tighter bound? \n\n## Minor\n* p1 L27 The Bayesian posterior", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "General comments:\n- We agree that Section 4 is too dense. We will take advantage of the tenth page offered for the final version to sparsify it.\n- 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.\n\nMajor:\n1. 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.\n2. 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.\n3. 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.)\n4. Thanks a lot for your valuable suggestions! We will definitely use them to improve the writing.\n5. 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.\n6. 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.\n7. 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.\n8. 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. \n9. That’s a good question. Again, it depends on the models to which Recursive PAC-Bayes is applied.\n10. To clarify the confusion, replace the sentence in L320 with: “Similar to them we used probabilistic neural networks with weights represented by Gaussian distributions.”\n11. 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$.\n12. 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.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviewers agreed this is a technically solid paper and a significant advance for the PAC-Bayes learning theory. There is no doubt that it deserves acceptance.

It is also worth mentioning that there is a consensus that the submitted manuscript contains dense explanations, and some parts deserve to be clarified. For the benefit of the readers, I strongly recommend the authors address these concerns in their camera-ready.
Decision: Accept (spotlight)