Block-Sample MAC-Bayes Generalization Bounds
Authors: Matthias Frey
Jingge Zhu
Michael Gastpar
Venue: ICLR 2026 Poster (2026)
Keywords: PAC-Bayes bound
MAC-Bayes bound
KL divergence
block-sample MAC-Bayes bound
Primary area: learning theory
TL;DR: We propose a novel PAC-Bayes generalization bound for learning algorithms for that holds in expectation and show that it does not hold with high probability.

Abstract: We present a family of novel block-sample MAC-Bayes bounds (mean approximately correct). While PAC-Bayes bounds (probably approximately correct) typically give bounds for the generalization error that hold with high probability, MAC-Bayes bounds have a similar form but bound the expected generalization error instead. The family of bounds we propose can be understood as a generalization of an expectation version of known PAC-Bayes bounds. Compared to standard PAC-Bayes bounds, the new bounds contain divergence terms that only depend on subsets (or \emph{blocks}) of the training data. The proposed MAC-Bayes bounds hold the promise of significantly improving upon the tightness of traditional PAC-Bayes and MAC-Bayes bounds. This is illustrated with a simple numerical example in which the original PAC-Bayes bound is vacuous regardless of the choice of prior, while the proposed family of bounds are finite for appropriate choices of the block size. We also explore the question whether high-probability versions of our MAC-Bayes bounds (i.e., PAC-Bayes bounds of a similar form) are possible. We answer this question in the negative with an example that shows that in general, it is not possible to establish a PAC-Bayes bound which (a) vanishes with a rate faster than $\mathcal{O}(1/\log n)$ whenever the proposed MAC-Bayes bound vanishes with rate $\mathcal{O}(n^{-1/2})$ and (b) exhibits a logarithmic dependence on the permitted error probability.

Published as a conference paper at ICLR 2026
BLOCK-SAMPLE BOUNDS
MAC-BAYES
GENERALIZATION
Matthias Frey and Jingge Zhu Department of Electrical and Electronic Engineering The University of Melbourne
Michael C. Gastpar
Laboratory for Information in Networked Systems École polytechnique fédérale de Lausanne (EPFL)
ABSTRACT
We present family of novel block-sample MAC-Bayes bounds (mean approxi- mately correct). While PAC-Bayes bounds (probably approximately correct) typ- ically give bounds for the generalization error that hold with high probability, MAC-Bayes bounds have similar form but bound the expected generalization error instead. The family of bounds we propose can be understood alization of an expectation version of known PAC-Bayes bounds. Compared to standard PAC-Bayes bounds, the new bounds contain divergence terms that only depend on subsets (or blocks) of the training data. The proposed MAC-Bayes bounds hold the promise of significantly improving upon the tightness of tradi- tional PAC-Bayer and MAC-Bayes bounds. This is illustrated with simple nu- merical example in which the original PAC-Bayes bound is vacuous regardless of the choice of prior, while the proposed family of bounds are finite for appropriate choices of the block size. We also explore the question whether nigh-probabille versions of our MAC-Bayes bounds (i.e., PAC- bounds of a similar form) are possible. We answer this question the negative with an example that shows that in general, it is not possible to establish PAC-Bayes bound which (a) vanishes with a rate faster than O(1/ log/ n) whenever the proposed MAC-Bayes bound vanishes with rate O(n -1/2) and (b) exhibits a logarithmic dependence on the permitted error probability.
gener-
INTRODUCTION
Statistical learning theory studies the behavior of algorithms that infer a hypothesis W from train- ing set S. This framework can be understood as a mathematical abstraction of real-world machine learning algorithms. For instance, if we want to analyze a neural network for image classification, would be a sequence of images with class labels and W would be the set of all the weights and biases of the trained neural network. In this example, standard way of finding W given S would be to run a stochastic gradient descent algorithm. Once such an algorithm is implemented, defines (possibly stochastic) mapping which (possibly randomly) assigns hypothesis W to any given training set S. We write this algorithm as a conditional probability distribution Pwis. The analysis of the performance of such algorithms deals with the relationship of two fundamental quantities: The empirical loss describes how well the hypothesis given by the algorithm fits the training set S, while the population loss describes how well the hypothesis fits new data that may not be contained in S but follows the same probability distribution that generated S. While the empirical loss of any given hypothesis can easily be calculated, the population loss is harder deal with. can, e.g., be estimated if an additional testing set is available that follows the same distribution as the train- ing set, and while this is commonly done in practice, carries many limitations. For instance, the testing set is usually obtained by partitioning the set of available labeled data (making the training set smaller) and if the algorithm tweaked based on testing results, then technically, new and independent testing set would be required to test the new algorithm. One fundamental question of statistical learning theory therefore is to understand and characterize the generalization error, which is defined as the difference between the empirical and population loss. If the generalization error is well understood, we can draw conclusions about the population loss from calculating the empirical loss.

---

Published as a conference paper at ICLR 2026
More concretely, in the scenario study in this paper. we assume that S (Zi..... Zn) is sequence of length n that is distributed i..d. according to a data generating distribution Pz on a set Z, and the way in which we measure performance is described by a loss function & W x 2 - [0, oo). In the image classification example, each Z; would be an image and its associated classification label (the ground truth) and the loss function could be the classification loss, i.e., it maps a pair (w, to O if the classification label produced by the neural network with weights w and the image contained in matches the classification label contained in z and to 1 otherwise. On the basis of this loss function, the empirical loss of w under = (21..... 2n) is defined as [(w,)) = Ei=1 ((w,,2) 24), and the population loss of w is defined L L(w) := Ep f(w, Z).
PAC-Bayes bounds, initiated by McAllester (1999) and Shawe-Taylor & Williamson (1997), pro- vide a framework of bounding the generalization error and thus give learner the ability to draw conclusions about the population loss based on a computation of the empirical loss. They usually take the form
D (PWwisl(Qw) + I(n, d) log <
v8 E (0, 1] Ps (W. L(W))
n
(1)
where:
Ps P is the product distribution that generates the training set S.
d is comparator function. In this paper, make the assumption (which is standard in the context of PAC- PAC-Bayes and related bounds) that d is jointly convex in its arguments. For the left hand side of the bound to coincide with the generalization error, we would choose d(r, := r, but other notions of distance are possible here as well.
D ( (Pw)sllQW) is the Kullback-Leible (KL) divergence between Pwis and some prior Qw.
* Qw. although called the prior, does not need to be a representation of prior belief in the traditional Bayesian sense, but is rather a parameter that can be arbitrarily chosen for the evaluation of the bound. It is probability distribution on the hypothesis space W, and the bound is valid for every choice of Qw that does not depend on S. Ideally, Qw would be chosen in such way that it makes the right hand side as small possible (and therefore making the bound as tight as possible) but in practice it is often chosen to be a probability distribution that is feasible calculate with, such as uniform or Gaussian distribution.
[n, d) is quantity that depends on the number of training samples and d as well as the prior Q. Usually it contains moment generating function. For instance, (Germain et al.)
2009 Theorem 2.1), this quantity is [n,, d) log ErsQw exp (nd(L L(W))
Note that while Qw can be chosen for the sake of analysis as probability distribution that is tractable to calculate with, Ps may be unknown and potentially too complicated to calculate expectations over. Therefore, an upper bound for this expression (which is uniform for reasonable large class of Ps) is sometimes used as [(n, d) instead.
One interesting aspect of the PAC-Bayes bound is that the full information about the learning algo- rithm PwIs explicitly used the bound through the divergence term slwsslQQw), ). leading to a tight generalization error bound even for practical learning algorithms with large models such as deep neural networks, as illustrated in, c.g., Dziugaite & Roy (2017) and Pérez-Ortiz et al. (022I).
A variation of PAC-Bayes bounds that are not necessarily valid with high probability but instead bound the expected generalization error Eps w d(L(W, S). L(W)) have been called MAC-Bayes bounds (mean approximately correct) by Grunwald et al. (202T). Such bounds can be derived from PAC-Bayes bounds variations, but sometimes it is possible to give a MAC-Bayes bound that is tighter than the corresponding expectation version of the PAC-Bayes bound. An example for a MAC-Bayes version of (I) would be
E Ep dl (E i(,, Z), BP L(W)) Ep. D (Pwisll + I'(n
71
where I'(n, d) is possibly slightly distinct from (n, d) in (T) but also contains a moment- noment-generating function and exhibits a similar behavior.
2

---

Published as a conference paper at ICLR 2026
In this work, we study generalization of the MAC-Bayes bound 2 which we call block MAC-Bayer bound, taking the form
[p L(W, Epwis L(W)) S Ej=1 Eps, D ((ww)s,lQW)) + (", d,
(3)
where:
The training data S is partitioned into J blocks Si,..., SJ. Pwis, defined as
Pwis, == S,-1
Pwis
(4)
is the distribution of W conditional only Sj. It is important to note here that Pwis, does not denote an alternative algorithm that generates a hypothesis from block Sj only, but rather is averaged form of the algorithm Pwis-
(", d, J) is, similarly I(n, d) above, a moment-generating function. An important thing to note here is that in addition to being dependent on n, d, and Qw, it also depends on the number of blocks J.
The focus of this paper is to introduce and investigate the properties of this new type of bounds, the optimal choice of block size, and what possibilitics there exist to derive this type. Our finding shows that the obtained MAC-Bayes bounds can have right side terms that vanish at faster rates than that of the original PAC-Bayes bound or even vanish in some cases in which the original PAC-Baye bound would be vacuous.
bounds of
While ultimately the motivation for proposing a new type of bound is its potential to tighten existing PAC-Bayes based bounds for real-world learning algorithms such as the image classification exam- ple discussed above, substantial additional research will be necessary to solve many of the practical issues that arise when applying the bound complex algorithms. In this paper, limit ourselves illustrating the promise of the bounds in the context of a very simple example, namely the estimation of Gaussian mean under truncated square loss. Specifically, in this example, Pz N (p, 1) (the normal distribution with mean μ and variance 1) and the loss function is given by
xr, EEE (0,1) E [1, o.).
E(w, 2) = K ((w= K(x)
1
The training algorithm Pwis is a Dirac distribution with probability mass at Σ Z,, i.e., the algorithm deterministically computes W := algorithms like this one, the original PAC-Bayes bound (I) and its MAC-Bayes version (2) are vacuous (the right hand side is infinite) regardless of the choice of prior Qw while the block-sample bound 33) with choice J yields meaningful bounds.
Σー - 1 Zg It turns out that for deterministic learning
We now briefly summarize the contribution of this paper.
We prove a block-sample MAC-Bayes bound (Theorem D which generalizes the MAC- Bayes version of the original PAC-Bayer bound. In Corollary [ we show how this general result can be used to obtain a bound on the generalization error by substituting a specific choice of distance function. We also illustrate what happens if binary KI. divergence difference function are substituted instead. While these bounds are suboptimal compared Corollary [ is worth mentioning that substituting the difference function (Corollary 2 yields a bound with slightly wider applicability.
The usefulness of the block-sample bounds is illustrated via an example in Section 4 where we show that the new bounds are in general tighter than the original PAC-Bayes bounds. The bound is also validated numerically. In Section 5 we generalize the scenario and illus- trate how the growth behavior of the divergence term that appears in the bound influences the choice of m that optimizes the bound order-wise.
We explore the question of whether block-sample PAC-Bayes bounds are possible (i.e., a high probability version of the proposed block-sample MAC-Bayes bound). In Section we answer this question in the negative, proving that in general, reasonably fast decaying bounds with logarithmic dependence the permissible emor probability not possible.
3

---

Published as a conference paper at ICLR 2026
Like many other bounds we propose in this work depend on the distribution of the traming data. This means that our bound can potentially be tighter than distribution-indeee independent bounds in cases where least partial statistical knowledge about the training data is available, but it comes with the drawback that the bound may not be computable in cases in which such knowledge is not available. In Section 7 we discuss the limitations that arise from this in more detail.
bounds (c. g. Bu et al. 2020 and Negrea et al. (2019), the
2 RELATED WORKS
Numerous BACcss bounds have been developed since its conception. For iid. data, a frame- work was developed by Germain et al. (2009) and Bégin et al. (2016), where one class of PAC-Bayes bounds can be obtained systematically by choosing different comparator functions d. This frame- work allows us to recover well-known Maurer (2004)), Seeger (0002) and Catoni (007), etc. More recent work on PAC-Bayes bounds also deals with non-i.i.d. data. For example. Alquier & Guedj (2018) established bounds for de- pendent, heavy-tailed observations, and Haddouche & Guedjj (2022) considered a sequential model. PAC-Bayes bounds have recently received renewed interest partly due their ability to provide tight generalization bounds for practical algorithms with large models. The idea of applying PAC-Bayes bounds to neural networks goes back to [angfordd
bounds from McAllester (1999) (improved by
Caruana (200T). More recently, it has been shown by Dziugaite & Roy (2017) and (Pérez-Ortiz et al. (2021) that when combined with suitable optimization techniques, PAC-Bayes bounds can generate very tight bounds. The recent survey by Alquier 20224) provides a comprehensive review of this topic.
MAC-Bayes bounds have appeared in the literature under various names, such as integrated PAC- Bayes bounds, PAC-Bayes bounds in expectation, simply as PAC-Bayes bounds. Early appear- ances can, c.g., be found in Alquier (2006) and Catoni (2007). but they have also been of interest more recently in Grunwald et al. (2021). MAC-Bayes bounds have been studied in cases in which nontrivial PAC-Bayes bounds are not possible. A brief overview of MAC-Bayes bounds is included in the recent survey by [Alquier (024)).
A related line of works appeared later in the information theory literature, starting with the works Russo & Zou (2016); Xu & Raginsky (2017). Results similar in spirit to PAC-Bayes bounds presented under the name informatiion-thereell
bounds on the generalization error. Works on iioommtiion-thooreee bounds often focus on bounds in expectation, with many also proposing high- probability bounds. Examples of works that focus mostly on high-probability bounds are Esposito ( (Fellsttm & Durisi (2020). Further variations and refinements of information- -theoreec
bounds on generalization error include Asadi et al. (0018); [Steinke & Zakynthinou (2020); Bu et al.
(2020) Zhou et al.) (2022); Wu al. (2022 2025). recent survey by Hellström et al. (2025)
provides an overview.
Our block-sample bound is inspired by the collviduul--amplle information-thhores bound due to Bu et al. (2020) in which the KI. divergence terms are replaced by the mutual information of the individual samples contained in the training data and the hypothesis. The individual- -smple bound is tighter than the original information -theorett bound and has been applied to various learning sce- marios, e.g., by Saadrguez-Gäáleee et al. (202T): Harutyunyan et al. (021). The work Harutyunyan et al.] (2021) also considers bounds based the mutual information of the hypothesis with m train- ing samples drawn uniformly at random. In the present work, in contrast, the training set is divided into blocks of size m and the conditional distribution of the hypothesis given each of them shows up in the information quantities in our bounds. In the follow-up work Harutyunyan et al. (2022), the statements which resembles Theorem
authors also give an impossibility result for of the present paper, but is for the different system setup also used in Harutyunyan et al. (2021) iS based on a fundamentally different idea, and intersects with our result only in the special case where the block size is = 1. For m >> 1, the impossibility result in Harutyunyan et al. (2022) is not ap- plicable. Wu et al. (0024) also study PAC-Bayes bounds based on a separation of the training sample into blocks, however, their bound differs from the ones proposed in this paper in that it has recur- sive structure based on sequences of prior and posterior distributions, which makes not directly comparable to our bound. PAC-Bayes bounds involving individual samples have been considered in some recent work including Zhou et al. (2023); Hellsttöm & Durisi (2022). The recent works Foong al. (202T): Hellström & Guedj (024) studied the tightness of original PAC-Bayes bounds
4

---

Published as a conference paper at ICLR 2026
with different choices of the comparator function d, which are relevant to current study. To the best knowledge of the authors, this paper is the first work that presents block-based MAC-Bayes bounds under general framework, considers the optimization of the bound, and explores possible PAC-Bayes versions of the bound.
BLOCK-SAMPLE MAC-BAYER BOUNDS
In this section, we propose the general version of the block-sample MAC-Bayes bound along with specializations to some commonly used comparator functions d. In this bound, the training set S is partitioned into blocks Sj := 1ij-I)m+1:jm == (Z(j-1)m+1:--
Zjm).
Theorem (Block-sane sample MAC-Bayer bounds), Let m E [n] == (1....,R), n.). assume that n. an integer multiple of m, and let S' (Zi...., ?n where Zi..., Z.m are i..d. drawn from Pz. Assume that for X' E (0, b) and some distribution Qw over W, holds that
1 Ew exp (xa
X'd
=
e(W, Σ ==1
((W, ZD, (.W.Z).LW)))
S 2m (X)
(5)
for some function om (0, b) (0, 00). Then for any X E (0, bm/mm//mm...)m))) ) holds that
log 4 Am
Ej= D (Pwis;l1Qw)
Epdd d L(W,), L(W)) <
(6)
A
where J = n/m.
The proof uses the Donsker- Varadhan variational representation of KL divergence achieve a change of measure from the marginalized version of the algorithm Pw]s, to the prior Qw Specif- ically, we argue
Proof.
Epdd PPwss L(W, 5), Epwis L(W))
(0)
< Epg Brwis d ((W,)),L(V)
jm
= L.pp Epwis d
E(W, Zz), (.W.Z).
j
1=1
i=( 11
(0)
im
< Epg Erwis
Σ
Σ
e(W, Zz), Zi), (w..Z),.((0))
j
j=1
i= 1)m+1
jm
(b)
Eps
Eps 15
EPw
J m
Σ
e(W, Z,), L(W)
i= 11m++
im Σ
4
Erss
EPwIs;
(WW, 2,), L(W)
m
i= -- (ef--)jn 11m++1
jm
1
EPs
E EPIIS
j
Σ
((W, 2.), L(W)
m
1= (fff-1)m++ 11m+1
1
E(W, (W, (w.Z2).(()))
E Eps
log EQw exp
j
i= 1m
+ D (Pw1s,
5

---

Published as a conference paper at ICLR 2026
J log Ps, w exp (dd 1 Ei= -i=(j-1)mt l(W, 2.), L(W)) + +Ess D (PWis, lQw)
log pm (3) + +Ps, D (Pwis, lQw)
A
1=1
log Pm (3) Ej= Ers, D (Pwis,
X
where both steps labeled (a) are applications of Jensen's inequality which make use of the convex- ity of d, (b) is due to the Fubini-Tonelli theorem, (c) application of the Donsker- Varadhan inequality
E Pwis g(W) log Eow exp(g(W)) + D DDW (Pwis,
with
g() = ja
jm Σ
e(W, (W,)).L(W))
m
i=(j-1)m+1
and (d) uses Jensen's 's inequality with the concavity of the logarithm.
Remark Condition (5) can be understood assuming an upper bound on the moment generating function of the loss function. As can be seen in the proofs of Corollaries and it is always satisfied for bounded and subgaussian losses.
Remark 2 (Data dependent priors). It can be verified in the proof of Theorem 7 that the result also holds if Qw is replaced in (5) with data dependent prior Qwis.. The prior will then appear in (6) Qw In the remainder this paper, will focus on the case that Qw does not have any dependence on data.
Theorem I can be specialized by substituting various choices for d. In this paper, we look at bounds
in terms of the comparators d(r, 8) =- Cp(r, 8) == - -log (1 exp(-3)) 8 Brr (this is the Catoni function which was introduced as a comparator by Catoni (2007)), d(r, s) := kl (r|]s) := log & + (1 log + where define Olog 0 == by convention (this is the binary KL function which defined for r, [0, 1)). and d(r, s) is in terms of the difference function, it directly bounds the expected generalization error gen :=
(the difference function). If the result
E.s.w (L(W) L(W,
The following corollary shows how Theorem can be used to upper bound the generalization error of a learning algorithm in the case of bounded loss. It follows from Theorem [ by substituting d(r, 8) == (r s). Full details of the proof can be found in Appendix A
Corollary 1. Let f(w, =) E [0, for all w E W, E 2. Then for any B > O. we have
Ep. EEwis i(W, R I(W)
Eps, D (Pwis,11Qw).
Furthermore,
1
kl Ep L(W, ((W)))
E Eps, D (Pw1s,l1Qw)
(8)
1
gen <
Eps, D (Pwis))lQw).
(9)
4n
j=1
Remark 3. Under the assumption E(w, 2) E [0, for all w E W, E Z, we can of course also directly substitute d(r, s) == kl (r[[s)) in Theorem in an attempt to obtain a bound akin (8).
This would give us full details see Appendix A
lmg(2/m)
Epykl (EPw L(W,)) (W L(W)
Σ Eps, D (Pw]s,11Qw) (10)
m

---

Published as a conference paper at ICLR 2026
0.6
true gen
1
bound for gen
1
0.4
n1/2
14
m n/2
12
m n/2
0.2
m7 = /n
Vn
m nL
0
50
100
150
200
250
Figure 1: Comparison of true generalization error and theoretical bounds for the example in Sec- tion 4 with μ = 1/2. The solid blue curve shows the optimal bound (14) with optimal choice for m.
However, easy to see that after an application of Jensen's inequality this yields bound that is less tight than (8) due to the presence of the additional summand log(2</)), m. In terms of generalization error, this would yield the suboptimal bound
gen S
1
log(2/ml)
+
Σ Eps, D (Pw]s,llQw).
(11)
2
77
We conclude this section with corollary that shows how Theorem Caan be applied in case the loss not necessarily bounded. For this, we replace the boundedness assumption with the less general assumption that the loss is subgaussian and substitute d(r, s) following result. The further details of the proof can be found in Appendix [A]
in Theorem [ to obtain the
Corollary 2. Assume that the loss function E(w, Z) oL-subgaussian for any under the distribu- tion Pz, namely.
Epg exp(X(e((x) Z) L(w))) S exp(o2x21/2 for all E Then for any >> and a prior distribution Qw over W, it holds that
2x
gen
Ers, D (Pwis,
(12)
n
The same result holds if we assume the (weaker) condition EpzQW exp (XWW, Z))) exp(o2>22 x2/2), namely that E(W. L(W) is o² subgauussnn under the product distribution PzQw.
4 EXAMPLE: GAUSSIAN MEAN ESTIMATION WITH TRUNCATED LOSS FUNCTION
In this section, explore the simple example toy example for a learning scenario which was in- troduced in Section [ The example shows that proposed block-sample MAC-Bayes bounds can yield meaningful convergence guarantees in cases in which the original PAC-Bayes bound would be vacuous. In the following, we will use the Landau symbols O, O, and o according to their standard definitions.
Recall that Z, ~ N (n,) 1) for some (unknown) E E0,11, W = E Zi, and
x 0, 1) 1,
(w,, 2) = K ((w 2)²). K(x)=
x E [1, oc).

---

Published as a conference paper at ICLR 2026
Eps Sp,
gen with = θ (n*)
a²
gen with 2 (n
n -
mints 110)=
any
1 1<11
n
O (n
o () + O (n logn)
1 1
O (nmin(s-110)---1 -100) + (n (lolng logn)
Table 1: Convergence rate of gen depending on the growth behavior of m under assumption 15
This loss function has, c.g., been analyzed and applied to practical ML algorithms by Le & Zach 2021
To understand the choice of m for the KL-divergence term, we choose the set S, to be the j-th batch with m samples, namely S = Z 1:-m1mmm::mmmmmm and define Sj to be the sum of these elements S, ==
1m=+ Zi. It be seen that have Pwis, N (m(n m)/n S,/n, (n m)/ nn/
Choosing the prior Qw = N (m, (n mm)mn²) gives us
E (S) -mmmm 2)
n²
8
pm 72
(b)
Ep3 (Pw s, (Qww)
Eps
2(n - m)
n
2(n m))
2(n - m)
(13)
where (a) we have used the KL divergence formula from
Gil
201
Table 2.3) and (b) follows
because Sj follows the distribution N (um, m). Substituting
13
in
(
we obtain
m
1
1
gen S
(14)
m
2(n m) 2 2(n m)
The original PAC-Bayes bound, which would correspond to the choice m = n, can clearly be seen to be vacuous in this case. However, any other choice of block size yields a bound which decays as O(n=²), with choices of block size m and plot for illustration also the suboptimal bounds for gen that can be derived from (T) and (12 in a similar way. It can be seen in the plots that the bound (14) is not overly sensitive to suboptimal choices of m (as long as m F n.) and that if adjusting m appropriately, the suboptimal bounds derived from (11) and 12 will also decay reasonably n grows.
1 being the optimal choice. We show the bound (14) in Figure for various
Remark 4, While the choice of Qw we have used for the evaluation of this example is somewhat arbitrary, is worth noting that the bound for the case m = n (corresponding to the original PAC- Bayes bound) is vacuous for every possible choice of Qw. For detailed argument, see Appendix
5 OPTIMIZING BLOCK-SAMPLE MAC-BAYES BOUNDS
The example from the previous section illustrates that the right choice of m depends on the behavior of the divergence term Ep, E/=1 D (Pw]s, [[Qw). which needs to be evaluated on case-by-case basis. In this section, we illustrate this finding order-wise in more generality under the assumption that the summands of the divergence term satisfy
O(m²)
Ep D (Iwss,11Qw) = (n)
(15)
for some 2 and all S,,. Of course, the assumption in (15) needs to be verified for the problem at hand. For instance it can be seen in (1) that for the example in Section 4 (15) holds with 7 = 1 as long as m + n.
In Table we show bounds for the generalization gap gen = EP w (L(W) i(,, Z) that can be obtained from Corollary under assumption (1)). The notation 1, which appears in the table is the indicator function, defined to take the value when the condition & is satisfied and the value otherwise. If nothing is known about the behavior of the empirical loss E L,W, S), only the bound given in the first row applies. If, the other hand, it is known that the empirical loss vanishes as
8

---

Published as a conference paper at ICLR 2026
Ep, (WW O (n=s) where O, there is additional trick which enables to use the bound in the second row. This bound can, depending on the value E, be significantly tighter than the bound that does not use this assumption. For details on how these bounds are calculated, refer the reader to Appendix
The bounds given for choices of block size assumed behave m (n²)), where a E [0, a parameter that can be optimized. Correspondingly, we indicate the optimal value a of a along with the resulting order-wise behavior of the generalization bound. It can be seen in the table that the example from Section sits exactly at the transition point of a dichotomy: For < 1, any constant choice for m is optimal while for y > 1, the block size m should grow linearly with n. This would include the choice m = as well as choices such as m = n/2. 2. It is worth noting here that as can be seen in the example of Section 4 155 is in some cases only satisfied if m o n. In these cases, the original PAC-Bayes bound (m = n2. is not applicable (for instance, in our example it would be vacuous) but the sample approach still allows us to achieve the order-wise optimal tradeoff point with choice such as n2/2.
ON THE (IM)POSSIBILITY OF
PAC-BAYES BOUNDS
In this section, we explore the possibility of transforming the block-sample MAC-Bayes bound into a version that holds with high probability, and thus obtaining a PAC-Bayes bound. Specifically, possible to find a meaningful PAC-Bayes bound
we are interested in the following question: for every learning scenario for which Theorem 7 yields MAC-Bayes bound that converges to O (reasonably fast)? For the interpretation of meaningful PAC-Bayes bound, we will focus on the question whether bounds of the following form exist:
2 )1))211
Ps Erwisd (TWW,)) I(W)) S An An Bn
(16)
where A, converges to 0 reasonably fast as n + DC. Note that the right hand side of the original PAC-Bayes bound (1) is of the same form as the right hand side in (16) with f = log and B, 1/n. We show next that there exists a learning scenario with the following properties: (a) Theorem gives MAC-Bayes bound with square root convergence, but (b) any PAC-Bayes bound of the form (T6) which is valid for this learning scenario needs to either have a fast growing f or a slowly converging B, (see the theorem statement for the technical meaning of fast growing and slowly converging). For this, we focus on the comparator function d(r, s)
0o, is function that grows slowly, and Bn converges
r in which case
Epdd (EPwis L(W,)), E. I(W) gen E.S. (I(W)- - f(W..))
corresponds to the most commonly used definition of the generalization gap.
Theorem 2. Let be chosen in dependence of such that m/n -> -> Then there exist a loss function E with values bounded in [0, 1]. sample distribution Pz, and a learning algorithm Pwis with the following properties:
The assumptions of Theorem are satisfied with the choice d(r, 8) = 8
2. There exists Qw such that the right hand side of (6) vanishes in order O(n -1/2) DX.
3. For every nondecreasing function f :0, 00) + R. for every sequence An that vanishes
as n - 0o, for every sequence B,, in (ngg(())))g)) and for every sufficiently large n, there is 8 E [0, 1] such that
Ps E.wis (L(W)- -WW)-((W,)) > An B. / (1)) )
>
(17)
The full proof of Theorem is relegated Appendix D In it. explicitly construct a learning scenario with the following property: With a small probability over Ps. the learning algorithm dramatically overfits the training sample. With the remaining (larger) probability, outputs

---

Published as a conference paper at ICLR 2026
hypothesis that has zero loss (both empirical and in population). We then show that items and 3 hold for this learning scenario, giving an explicit choice of Qw for item
Items I and 2 in conjunction with Theorem tell us that there exists learning scenario in which the bound (6) holds with a right hand side of the order (n-11/). Item t that in the same learning scenario, a bound of the form (T6) cannot hold with a slowly growing and a fast converging В, at the same time (observe that (17) is the logical opposite of (6) with the difference function substituted for d).
We conclude this section with two remarks that approach the question of whether block-sample PAC-Bayes bounds are possible from slightly different angles.
Remark 5. If d lakes only nonnegative values then (6) and the Markov bound imply the sollowing high-probabiliiyy bound: For every E (0, 1). with probability at least 1 over Ps.
log t
j=1 Ers, D (Pwis, llQw)
d (EPwis L(W, PEPwisL
A6
This bound has the form (16) with An O and, depending the learning scenario at hand, quite possibly with a term Bn that converges to O reasonably fast. However, f is the identity function here, which is much worse than the original PAC-Bec PAC-Bayes bound (T) where have f = log.
Remark 6. While Theorem conclusively shows that an exponential high-probabilltyy version of the MAC-Baye bound O is not possible in general, it strictly speaking leaves open the possibility that a Block-sample version of the original PAC- PAC-Bayes bound (T) of the following form might exist:
E D (Pwiss 11Qw) + I[n, d) + log 1
P (d(i,))
(18)
The main difference compared to (6 is that the expectation operator in front of the divergence terms
D (Pwis, lIQw) is absent in (8)) However, one inspects the proof of Theorem 2 it is clear that in the error event evaluated in (for a detailed derivation see Appendix E}, we have
A inst
D (Pwis,)1QW) = Oloog)).
(19)
so the term Aisst n that appears in (18) vanishes at rate O(n log n). Therefore it is clear from item 3of Theorem that bound of the form 18 with I(n, d)/n 0 aas n can hold.
7 CONCLUSIONS AND LIMITATIONS
We have presented family of blopk-sample MAC-Bayes bounds which are generally tighter than MAC-Bayes versions of classical PAC-Bayes bounds, and we have shown that they cannot gen- eral be established as PAC (i.c., high-probabilg probability. One important further limitation of these bounds is their dependence on the data distri- bution Pz via the divergence term D (Pwis, [[Qw). In this sense, they cannot be applied immedi- ately if we do not have any information about the data distribution Pz. Two comments are order regarding this limitation: (a) Given certain basic information about the data distribution, block- sample MAC- Bayes bounds can give useful results without requiring full knowledge the data distribution Pz. In fact,
versions with logarithmic dependence on the error
show in Section as long as we have enough knowledge of the data distribution to be able to establish an upper bound of the form (15), the block-sample MAC-Bayes bound be applied. (b) More broadly. almost all informatiio--heerrtio bounds generalization error depend on the data distribution as the mutual information term (W:S) (or variations thereof) depends on the data distribution (see, c.g., Hellström al. (2025) ) for recent survey). In such cases, to make the bounds useful, the mutual information term is further upper bounded by using knowl- edge of the data and learning algorithm. This is done by, e.g.. Bu et al. (2020) and Negrea et al. (2019). A similar approach can be taken for the dloc--sample PAC-Bayes bounds by further bound- ing the divergence term D (Pw]s, [[Qw) with properties of the learning algorithm. We consider this an interesting future research direction.
'Of the three comparator functions studied in this paper, this applies only to the KL divergence. However, other comparator functions that satisfy this assumption readily available, for instance the absolute difference function d(r, a) = Ir the square distance function d(r, s) (r a)?
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
The work in this manuscript was partially supported by the Swiss National Science Foundation under Grant 200364 and by the Australian Research Council under Project DP23010149.
REFERENCES
Pierre Alquier. Transductive and inductive adaptative inference for regression and density estima- tion. PhD thesis, ENSAE ParisTech, 2006.
Pierre Alquier. User-friendly introduction PAC-Bayes bounds. Foundations and Trends in Ma- chine Learning. 17(2):174333. January 2024. Publisher: Now Publishers, Inc.
Pierre Alquier and Benjamin Guedj. Simpler PAC-Bayesian bounds for hostile data. Machine Learning, 107(5)887--902, May 2018.
Amir Asadi, Emmanuel Abbe, and Sergio Verdu. Chaining mutual information and tightening gen- eralization bounds. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Stéphane Boucheron, Gábor Lugosi, and Massart. Concentration Inequalities. A Nonasymptotic Theory of Independence. Oxford University Press, Oxford, 2013.
Yuheng Bu, Shaofeng Zou, and Venugopal V. Veeravalli. Tightening mutual information-based bounds on generalization error. IEEE Journal on Selected Areas in Information Theory, 1(1): 121-130, May 2020.
Luc Bégin, Pascal Germain, François Laviolette, and Jean-Francis Roy. PAC- AaC-sayei bounds based the Rényi divergence. In Proceedings the 19th International Conference Artificial Intelligence and Statistics, pp. 435-444444 444. Proceedings of Machine Learning Research, May 2016.
Olivier Catoni. PAC-Bayesian supervised classification: The thermodynamics of statistical learning.
Lecture Notes- Monos-Monoggaph Series, 56:i-163, 2007.
Gintare Karolina Dziugaite and Daniel M Roy. Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data. In Uncer- luinty in Artificial Intelligence, UAI, 2017.
Amedeo Roberto Esposito, Michael Gastpar, and Ibrahim Issa. Generalization error bounds via Rényi-, f-divergences and maximal leakage. IEEE Transactions on Information Theory, 67(8), August 2021. ISSN 1557-9654. doi: 10.1 10.1009/T.2202233355519999
Andrew Foong, Wessel Bruinsma, David Burt, and Richard Turner. How tight can PAC-Bayes be in the small data regime? Advances Neural Information Processing Systems, volume 34, pp- Curran Associates, Inc., 2021.
Pascal Germain, Alexandre Lacasse, François Laviolette, and Mario Marchand. PAC-Bayesian learning of linear classifiers. In Proceedings of the 26th Annual International Conference on Machine Learning, ICML '09, pp. 353-360, New York, NY, USA, June 2009. Association for Computing Machinery.
Pascal Germain, Alexandre Lacasse, Francois Laviolette, Mario March, and Jean-Franci Roy. Risk bounds for the majority vote: From PAC-Bayesian analysis to a learning algorithm. Journal of Machine Learning Research, 16(26):787-866 2015. URL http://// jmmr.. maar.oze ota.z..rr/papers//// v16/ 2r16/germainle germain15a.html
Manuel Gil. On Rényi divergence measures for continuous alphabet sources. PhD thesis, Depart- ment of Mathematics and Statistics, Queen's University, 2011.
Peter Grunwald, Thomas Steinke, and Lydia Zakynthinou. PAC-Bayes, MAC-Bayes and conditional mutual information: Fast rate bounds that handle general VC classes. In Conference on Learning Theory, pp. 2217-2247. Proceedings of Machine Learning Research, 2021.
11

---

Published as a conference paper at ICLR 2026
Maxime Haddouche and Benjamin Guedj. Online PAC-Bayes learning. Advances in Neural Infor- mation Processing Systems, 35:25725-257355 25738, December 2022.
Hrayr Harutyunyan, Maxim Raginsky, Greg Ver Steeg, and Aram Galstyan. coormation-theoretiee generalization bounds for black-box learning algorithms. In Advances Neural Information Processing Systems, volume 34, pp. 24670-24682. Curran Associates, Inc., 2021.
Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Formal limitations of sample-wise theormttion-theoretie generalization bounds. In 2022 IEEE Information Theory Workshop (ITW), pp. 440-445. IEEE, 2022.
Fredrik Hellström and Benjamin Guedj. Comparing comparators in generalization bounds. In Inter- national Conference Artificial Intelligence and Statistics, pp. 73-81. Proceedings of Machine Learning Research, 2024.
Fredrik Hellström, Giuseppe Durisi, Benjamin Guedj, Maxim Raginsky, et al. Generalization Perspectives from Information Theory and PAC-Bayes, volume 18 of Foundations and Trends in Machine Learning. Now Publishers, Inc., 2025.
Bounds:
Fredrik Hellström and Giuseppe Durisi. Generalization bounds via information density and condi- tional information density. IEEE Journal on Selected Areas in Information Theory, 1(3), Novem- ber 2020.
Fredrik Hellström and Giuseppe Durisi. A new family of generalization bounds using samplewise evaluated CMI. In Advances Neural Information Processing Systems, May 2022.
John Langford and Rich Caruana. (Not) bounding the true error. In Advances in Neural Information Processing Systems, volume 14. MIT Press, 2001.
Huu Le and Christopher Zach. Robust fitting with truncated least squares: bilevel optimization approach. In 2021 International Conference on 3D vision (3DV), pp. 1392-1400. IEEE, 2021.
Andreas Maurer. note on the PAC Bayesian theorem, November 2004. arXivics/0411099
David A. McAllester. Some PAC-Bayesian thcorems. Machine Learning, 37():3355333333333333333333 December 1999.
Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M Roy. information--heorrtiic generalization bounds for SGLD via data-dependent estimates. In Advances in Neural Information Processing Systems, volume 32, Curran Associates, Inc., 2019.
María Pérez-Ortiz, Omar Risvaplata, John Shawe-Taylor, and Csaba Szepesvári. Tighter risk cer- tificates for neural networks. Journal of Machine Learning Research, 22((27): 2021.
Borja Rodríguez-Gálve Gálvez, Germán Bassi, Ragnar Thobaben, and Mikael Skoglund. On random subset generalization еттоr bounds and the stochastic gradient langevin dynamics algorithm. In 2020 IEEE Information Theory Workshop (I7W), pp. 1-5, April 2021. doi: 10. 199//969.4..5.. 2021.9457578.
Daniel Russo and James Zou. Controlling bias in adaptive data analysis using information theory. In Proceedings the 19th International Conference Artificial Intelligence and Statistics, pp- 1232-1240 Proceedings of Machine Learning Research, May 2016. ISSN: 1938-7228.
Matthias Seeger. PAC-Bayesian generalisation error bounds for gaussian process classification. Journal of Machine Learning Research, 3(Oc)):333266, 2002.
John Shawe-Tay and Robert C. Williamson. A PAC analysis of a Bayesian estimator. In Proceed- ings of the tenth annual conference Computational learning theory, COLT '97, pp. 2-9, New York, NY, USA, July 1997. Association for Computing Machinery. doi: 10. 10.1145/274400.27746.
Thomas Steinke and Lydia Zakynthinou. Reasoning about generalization via conditional mutual information. In Proceedings of Thirty Third Conference on Learning Theory, pp. 3437-3452. Proceedings of Machine Learning Research, July 2020. ISSN: 2640-3498.
12

---

Published as a conference paper at ICLR 2026
Xuetong Wu, Jonathan H. Manton, Uwe Aickelin, and Jingge Zhu. Fast rate generalization bounds: Variations on a theme. In 2022 IEEE Information Theory Workshop (ITW), pp. 43-48, November 2022.
Xuetong Wu, Jonathan H. Manton, Uwe Aickelin, and Jingge Zhu. Fast informatiin-theorrtic bounds on generalization errors. JEEE Transactions on Information Theory, 71(8):6373-6392 2025.
Yi-Shan Wu, Yijie Zhang,
Chérief-Abdellate and Yevgeny Seldin. Recursive pac- bayes: A frequentist approach to sequential prior updates with no information loss. In Advances in Neural Information Processing Systems, volume 37, pp. 17947-17971, 2024.
Aolin Xu and Maxim Raginsky. Information-theoreti analysis of generalization capability of learn- ing algorithms. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 2524-2533. 2017.
Ruida Zhou, Chao Tian, and Tie Liu. Stochastic chaining and strengthened information-theorette generalization bounds. In 2022 IEEE International Symposium on Information Theory (ISIT), PP- 690-695, June 2022. ISSN: 2157-8117.
Ruida Zhou, Chao Tian, and Tie Liu. Exactly tight information-theortti generalization error bound for the quadratic Gaussian problem. In 2023 IEEE International Symposium Information Theory (ISIT), pp. 903-908, 2023.
13

---

Published as a conference paper at ICLR 2026
A PROOF DETAILS FOR COROLLARIES AND REMARKS IN SECTION 3
A.1 PROOF OF COROLLARY
The proof uses similar techniques in Foong al. (2021) and Maurer (2004), and is given here for completeness. We will make use of the following lemma.
Lemma (Maurer (2004), Lemma 3). Let XI.... Xx be i..d. random variables taking values in
[0, 1] and .i..... X Lid. Bernoulli random variables such that EX1 = E.x For any convex
function f [0, 1 R, holds that
ES((I,,.... Xa) S Ef(X) X
For any fixed denote X; := f(w, ZD for all 1, ... and use X to denote the tuple (X1,..., Xm). Define X' to tuple m i.i.d. Bernoulli random variables such that E.;; EX for all i. Let f X + exp(\'C((Ei=) X,, L(w)). Thus, obtain
Epg exp
XCO3
1
Σ 1=1
E(w, 2,), ((w)((w))
(2)
X ((w)) ))
Epx, exp
XCCp
1
BX Σ x 1=1
Exxr exp
1+ (ep(= - -1)
(1+ ((w)(( exp(e /m) -1) m
(1 (exp(-3)
where (a) is by Lemma and in (b) have used the well-known expression for the moment gener- ating function of the binomial distribution. This upper bound is clearly equal to = m, so (5) satisfied for X with & (m) Consequently, an application of Theorem with X
yields (7)
To obtain 8 from 7 observe that by (Foong al. 2021 Lemma E.1),
kl Ep S). = sup
C3 PB L(W,)) Eps L(W)).
BE(U,00)
Finally, we can obtain 9 from 8 using Pinsker's inequality
kl (Eps.w (W,,,))EEPP L(
gen I 2
A.2 CALCULATION DETAILS REMARK
We again fix E W and use Lemma with X; == f(w, Z,), corresponding Bernoulli variables X/.
and f X + exp (A'kl ( Xt/m| w)) ). It can be checked easily that f is convex. For any w. have
X'kl 1
Ep
exp
l(w, Z)) ())l((())))
m
(a)
Eps
exp
X'kl
X()
h: [T((cr)
Σ Px
X k
exp
A'kl
m
k=0
t 1r) ))
< sup
Bin k; m,
exp
X'kl
rE[0.1] k=0
14

---

Published as a conference paper at ICLR 2026
where (a) follows from Lemma 1 and Bin(k; r)) denotes the pmf of binomial random variable with m trials and success probability r, evaluated at k. Using the result by (Maurer 2004 Theorem 1), the last term is upper bounded by 2/m when choosing X' states the assumption m 2 8, however, as noted at the end the proof of (Germain et al. 2015 Lemma 19), this assumption not necessary the remaining cases can be verified computationally. This means that (5) holds with Pm (m) == 2/m. So an application of Theorem with À == n yields
(Maurer) 2004 Theorem 1)
22 log(2/m) + Σラ= Eps, D (Pwis, 11Qw)
Epg kl (Epw (WW I(W)) <
n
from which 10 follows.
A.3 PROOF OF COROLLARY 2
The assumption on the moment-generatinn function in the corollary straightforwardly implies
E(w, 23) L(w)) ))
02²
Epgr
gy exp
X
S exp
2m
1=1
for all X E IR and any w. Choosing d(s, := this then implies that for any A > 0
1
e(W, (1) (WWZZ).((W))
Ep Qw exp
Ad
1=1
1
e(W, 2,) -L(W)
Qu exp
->
(o2)2
I exp
2m
Sm (A)-
Furthermore, the above inequality also holds when the weaker condition in the corollary assumed by noticing that Ep (l(w, Z) (w)) 0 for every w
Erzow (?(W, Z) L(W)) Ep (e(W, Z) - L(W)) 0.
We invoke Theorem I and substitute our expression for 4m to get
gen EpS. (L(W)- ((W)-L(wm) ((W)) <
Eps,
D (Pwis, (1Qw)
2n
j=1
The corollary then follows with the choice
2n Σ/ j=1 E Eps, D (Pwis, l1Qw)
22
B DETAILED ARGUMENT FOR REMARK 4
In the m = n version of the bound, the KL divergence D (PwisllQue appears on the right hand side which is finite iff Pwis & Qw (where < denotes absolute continuity). Hence,
Ps (D (PwisllQw) < oo) = Ps(Pwis & Qw)) = Ps (P(wis((w:: Qw > >)) =1 (20)
Dirac distribution and therefore Pwis & Qw iff Qw (w) for the single mass point w of Pwis- Clearly, in this example Pw P is a continuous distribution (i.e., it measures all singletons with probability 0) and Qw cannot have more than countably many points of positive mass, so by aaddiiivity, we have
where the last equality holds since Pwis
Erg (Pwis((w: Qw 0))) Pw ((w Qw(w) 0}) =
(21)
15

---

Published as a conference paper at ICLR 2026
Since the integrand the left hand side of (21) is nonnegative, the integral being 0 implies that the integrand has to be 0 almost surely. Therefore. (20) and (11) together imply that Ps (D (Pwis (uis|(Q@)) < oo) 0, in case n,, the term Br, D (Pw P sllQww which appears the right hand side is infinite regardless of the choice of Pw, making the bound vacuous.
Indeed, it be from this argument that this property of the not specific to this example, but applies whenever the algorithm Pwis is a Dirac distribution (i.e., the algorithm maps every training S deterministically to hypothesis W) but the marginal distribution Pw is continuous.
version of the bound
C CALCULATIONS FOR TABLE 1 IN SECTION 5
In this appendix, we provide the full derivations for the rates shown in Table
We substitute
15 into to obtain
gen vO(n O(n O -
The entry in the second column of the first row then follows by substituting m = O(n"). For the second row, need the following lemma.
Lemma 2. If E [0, 1]. kl (r|ls) S and r O( )) then r 2x Onn *log n.)
Proof. We recall that due to the definition of binary KL divergence
x 2 (r(]ss) = r rlog r
l-r
+ log
8
1
or, equivalently,
log(1 1 8) 2 1 log log(1 - r) 1- 1-7 log s.
Since < 1 and assuming that n is large enough so that r S 1/2, we can further bound the right hand side and get
log(1 8)
log + log(1 r) 2x.
With equivalent term manipulations and using the facts that exp(-t) S for all and log(1 r) 2 -r 2 for all E [0, 1/2], we obtain
exp
logr r log(1 - 2x
1
2x
logr log(1 -
--r
2x
logr +
--r
2x
logr +
2
The lemma then follows by subtracting r on both sides and substituting the convergence behavior of the right hand side.
We substitute (55) into (8) and get
kl PP.. Z(W. P). s O(n-2Jmm)) On--mm²11)
The entry in the second column of the second now follows by substituting O(22) and applying Lemma 2
For the optimizing choice of (which is the same in both rows), we note that the exponent in the second column is decreasing in a when < 1, so in this case the maximum choice a" = is optimal. Similarly, when 2 1, the exponent is nondecreasing, optimal. Finally, the entry in the last column follows by substituting the optimal a into the entry in the second column.
the minimum choice a is
16

---

Published as a conference paper at ICLR 2026
D PROOF OF THEOREM 2
We prove the theorem by first explicitly constructing 6, Pz. and Pwrss and then proving that they satisfy the properties and claimed in the theorem statement.
Choice of E, Pz, and Pwis. We let K E N be a parameter to specified later, E == [K].
W = {0, }} (identified with the set of functions from [K] to (0, 1)), and
E(w, 2) == w((2).
This means in particular that é can only take the values 0 and 1 and hence is bounded as claimed in the theorem statement.
We define the sample distribution Pz the uniform distribution over 2. In preparation for speci- fying the learning algorithm PwIs, we define the hypothesis wh via wo = 0 for all i: E [K] and for any , 2t Z, we define hypothesis
= [0, Aje E [e] : 2j
(k)
11 otherwise.
Let Φ E [0, 1] be another parameter to be specified later, and let S6 S th be such that P (12) Φ. Choosing such a Sig is clearly possible as long as Φ is an integer multiple of K K-
We can now define the randomized algorithm for our example as follows:
Pwis( (w|z2,...., 2n) ) = w===
(21,.... 2m) $ 2z
(Z) 3m) E Sgg.
We conclude this part with brief discussion of our choices that is intended to provide some intuitive understanding and a brief outline of the remainder of this proof. Wo is hypothesis of low loss, or more precisely, the empirical loss on any sample as well as the population loss will always have the lowest possible value O. On the other hand, w0 w.......e is heavily overfitted hypothesis in the sense that it will have empirical loss 0 on any sample that a subset of (=i,..., ze} but it has a population loss of at least (K - /)/K which is close to 1 as long l < K. The learning algorithm is chosen in such a way that most of the time it outputs wy, and hence the generalization gap in this case will be O. However, with a carefully calibrated probability 6, it will output the hypothesis vū z.m-1.....n which is overfitted to most of our training set, and consequently will exhibit a large generalization gap. The probability e will be carefully chosen such that it is small enough to allow the divergence terms in 6 to vanish and at the same time is large enough so that I7 holds.
What remains be shown is that (5) is satisfied. This is straightforward as we have already argued the loss function E is bounded in [o, 1]. Hence, by Hoeffding's 's Lemma (see, e.g. [Boucheron al., 2013 Lemma 2.2)), f(w, Z) is 1 1/4-subgaussian
Item 1 Assumptions of Theorem 1
for all w E W and therefore (5) is satisfied with
X2
Pr (A) = exp
(22)
8m
Item D Choice of Qw such that the right hand side of 66 vanishes. We define
Qw(w): == al alw + (1 Km
I 1mm p2g.
(23)
Fim on 2m
where a E [0, 1] is another parameter to be specified later.
Next, we show that the right rand side in (6) vanishes with appropriate choices for the parameters of our construction. Recalling the definition S := Zi:m...., S, == Zn-m+ lan, this means that we have
Km- Ezm-inEgn-n 1w Wmm
21m E Zs otherwise,
Pwis, (wl 21:m)
(24)
1 -=
Pwis, (10l 21mm) (1-6) w= 1
kmm
Σ
(25)
Em -in-m EZ
17

---

Published as a conference paper at ICLR 2026
for j J2.
With this we are ready to calculate bounds for the divergence terms that appear on the right hand side of ( Conditioned the event S 21m for some 2im 2" with 21:m Sgg and denoting W fw E W Pwis, (w|21:) 0}, have
Pw 91 (w/=1mm) ) log Pwis, (wlz1m)
D (PWiss)llw)
= E
Qw(w)
WEW
Km-n E SmitinEZ 1 T momii
Σ
Pwis (w|zim) log (1 am Σ L -==
WEW
1
log
(26)
a
where step (a) follows by observing wi & W and substituting (4) and (23) and step (b) by observing that the sums in the numerator and denominator are identical since they differ only in the names of the summation variables.
Next, we condition on the event S = 21mm for some 21mm E 2" with Zim & Sgg In this case, we obtain
D ((w) = Σ
Pwis, (w/z1mm) log Pwis, (w]21mm) (a)
log Qw (wa)
(b)
log
(27)
Qw(w)
wEW
where step (a) follows because W wp almost surely under Pwis, (1 (l1z))) according to 24 and
step (b) follows by substituting 23
For j E J). we condition on the event S = 21:a for an arbitrary 21mh E 2" and write W = fw NEE.. W.W. Pwiss (wlzz, (1)m)))+s)))))) 0}. Thus, we get
(Pwis,l1Qw)
Pwis,, (1ris,(wlll (w12()- 1mm Qw(u) (w)
=
Σ Pwis,
log
wEW
Pwis, (wol 1m++1:mm)
= (wol log
Qw (wa)
Pwis, 11m+
Σ
Pwis, (wl 1111))mmm++mmm log
Qw (w)
wEW (wo)
(0)
1 Φ
(1 ②) log
Pwis, (wlz(-1))+tiim
a
Am111d 11:5
E26 2)m 2jm E2" E2
log
K-a)Km-"
Dan mmn-m Il Tummie fo
(6)
Φ 2 (1 ④) log
+
Σ
- 1 log (1 a1) Km-n
km2m-n
a
(c) (1 () log(1 - +) + (1 - +) log + Llogogg + omn log + & log
1
1-a
< log C
+ Φm log K + log a
(28)
where step (a) follows by substituting 25 and (23), step (b) follows because the sum in the denomi- nator contains all the summands that the sum in the numerator contains (hence cannot be smaller), and in step (c) we use the fact that
Pwis, (WV)
1 Pwis, (wol (oool=uj-z (1mm(=)m)))+11mmmm d.
18

---

1 Published as a conference paper at ICLR 2026
We can caleulate bound for the divergence terms in (6) Namely,
Eps, D (Pwis, lQw)
(4) Ps. (2t) (D (P(wsss:)QQW) [SI (ts) + (1- Psi (2t))
Ers, (D (Pwis 11 2o) + Σ
Ery, D (Pwis, 11@w)
/=2
(b)
1
( (m
--1)) 1)
log
1 + lm K + ølog
Φ Glog
(1 Φ) log
1-a
a
a
m
1
n2 log
I Φ log
+
+ no log K + ő log a-a'
(29)
where (a) is due to the law of total expectation and (b) follows by substituting
26
27 and
(8
This allows us bound the right hand side of (6) (from now on denoted as R). Substituting and 29 we obtain
22
Φ log I-a
log + no innlog log K + 22
2 log T-a
R
m
(30)
8n
With the choices
K == 3n log n
m71
= exp
(31)
6 = K
n log n2
= Vn
and the observation
m7
0
(32)
exp
+
72 + m
we can further bound
30
and get
R
V
n
+
log mim log n
+ 1 +
log(3n (3n log m))
log
log m.m. log
8n
Vn
(a)
1
log(n + 1)
log(3n log n)
log(n + 1)
+
nlog + 1
Vn
8
log n
log
1
17 log(n + 1) +
log(n + 1) + log log log m2) log
n logn
log n
where in (a) we use the fact that since m takes only values in [n]. we have (n + m)/m m I n + 1 as well as m 2 1 for all valid choices of m. Since all terms the bracket are nonincreasing, the bound () vanishes with rate O(1/Vn).
Item 3 The generalization error does not vanish reasonably fast with small error probability. With probability o 1/n log over Ps, have W therefore
2 Zm almost surely over Pwis and
K m
E Erwis L(W) Er ((W.)) 2
K
n
3n log
+
3n log n
n
1
n
3 log n
19

---

Published as a conference paper at ICLR 2026
Towards contradiction, assume that the logical opposite of (17) holds, i.e., that have An
which vanishes as n - oo and Bn which vanishes with order o(1 f( log n)) as n - co, and
Ps ERwss L(W) - Erwis L(W,S) < An + Bnf 8
for a sufficiently large n and all E [0,
Setting 8 Φ 1//logg n, this implies that with probability at least 8
An + Bn (n) An Bus (1)
> Epwls L(W)
EPwis L(W
2 m (1
3 log
We can observe that since the left and right hand side of this inequality chain are not random and the entire chain holds with positive probability, the left hand side is valid (deterministic) upper bound for the right hand side. Since m/n vanishes, the right hand side converges to 1, so in particular it is clearly bounded away from 0. This contradicts the assertion that An converges and B,, converges to O with rate (n n)).
E PROOF OF 19
To see this, we can sum the instantaneous divergences conditioned on the overfitting event calculated in (26) and (28):
1 log a
A Inst log a m
log K glog
1
(a) log (n + m) - log m + 1+
log
log log
log 22--112 m2
+
log Th
log n
y2 log n
where in step (a) we have substituted 311 and which can be bounded as
Clearly the dominating term log(n + m)
log(n + m) I log(2n) = log 2 + log n.
20


Reviews:
[{"review_id": "CHqUhLF1AH", "reviewer": "Reviewer_HaRN", "summary": "This paper studies the MAC-Bayes bounds. They proposed a family of novel block-sample MAC-Bayes bounds, which generalized the MAC-Bayes bounds in the sense that it aggregates the contributions of a collection of disjoint subsets of the sample (on the MAC-Bayes bound) instead of consider the sample a whole. They proved the convergence of the block-sample bound and showed its superior characteristic power compared with the original PAC-Bayes bounds in a simple application-Gaussian mean estimation. At last, the paper discussed how the block size could affect the convergence and the possibility of transforming the block-sample bound into a high probability form.", "questions": "* What does the assumption (3) in the main theorem implies intuitively?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "* Although I did not verify all the proofs in detail, they appear to be sound overall.\n* While not significant, the block-sample bound seems to be a non-trivial generalization of the prior results.", "weaknesses": "I think the authors should put more effort in the presentations of this paper because of the following reasons:\n* The authors throw out the definition of PAC-Bayes bounds at the very beginning, however, without giving enough explanation for the term in the expression. For instance, I do not see any description of $Q_W$ and have trouble in understanding what it means. Also, I advise the author to give a concrete example of $I(n,d)$ in addition to just saying it is proportional to $n$ and $d$. Similarly, instead of just saying what $P_{W|S}$ does in general, give a concrete example to demonstrate it.\n* The authors introduced the \"individual-sample bound\" in describing their first contribution but did not even explain what it is.\n* From my perspective, the authors did a poor job in motivating the audiences on their contributions. The author only briefly mentioned that their result is a generalization of the MAC-Bayes bound and individual-sample bound (which they did not define), they did not emphasize the significance of their generalization. In particular, the authors did not well explain what advantages this generalization can bring upon the original MAC-Bayes bound in the contribution part. \n* While the author gave an example on mean estimation of Gaussian in Section 4 to demonstrate the usefulness of the block-sample bound compared to the PAC-Bayes bound, I am not convinced by this example due to its overly simplicity. In particular, the PAC-Bayes bound exhibits a poor generalization for this application not because this task is hard. In fact, a simple Hoeffding bound can give a tight error bound on the mean estimation. Therefore, this example is not enough to demonstrate the significance of the generalization. With that being said, I still suggest to move this example into the introduction to give a more fluent and motivative presentation.\n* In Section 3, it would be more accessible for the audience if the author could briefly explain the assumption in the main theorem in plain language and sketch their proof idea of the theorem in advance.\n\nI will consider raise my rating if the authors address my concerns.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "M4Ob2xYz88", "reviewer": "Reviewer_7GiM", "summary": "This paper presents a mean posterior error bound that relates\n$$\\mathbb{E} \\\\{ d( \\rho\\\\{ \\hat L_n \\\\}, \\rho\\\\{ \\mathbb{E} L_n \\\\})  \\\\}$$\nto\n$$\\sum_{j=1}^J \\mathbb{E}\\\\{  D_{\\text{KL}}(\\rho_j\\\\|\\pi) \\\\} + J \\cdot \\text{``per block CGF''}$$\nwhere $\\mathbb E$ is over the randomness of the observations, $\\rho$ is the data-dependent posterior probability, and $\\pi$ a prior probability; importantly, the novelty of the paper lies in $\\rho_j$, the posterior probability *after observing the block #j*.\n\nThis implies novel generalization bounds that scale as\n$$\\sqrt{ \\frac 1 n  \\sum_{j=1}^J \\mathbb{E}\\\\{  D_{\\text{KL}}(\\rho_j\\\\|\\pi) \\\\}}$$\nwhere the usual ``complexity term'' is broken down linearly into block components.", "questions": "In general, how does the quantity\n\n$$K_{n} := m^{-1}\\mathbb{E} \\\\{ D_{\\text{KL}} (\\rho_m \\\\|\\pi) \\\\}$$\n\nevolve as a sequence of $m$? Here $m$ agrees with the definition in your paper (i.e. block size), $\\pi$ is a prior probability, and $\\rho_m$ is the posterior probability evolved from $\\pi$ after seeing $m$ i.i.d. observations. I believe this is important to better conceptualize the benefits of the block decomposition in bounds e.g. (10). Some graphical exploration would be helpful.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "I found the block decomposition concept novel, and the authors did convince me that the technique drives tighter bounds.\n\nSome might argue that this is an interpolation between the individual-sample ($m=1$) and the bulk-sample ($m=n$) regimes (borrowing the leave-one-out analysis technique, equality (b), from the former). However, the resulting bounds are tighter as a result of this interpolation, with the \"optimal block rate\" clearly explored in Section 5.", "weaknesses": "For those outside the PAC-Bayes community, Sections 1-2 do not provide a good introduction to the concepts involved. In particular, *what is $Q_W$*? PAC-Bayes people of course know this is the prior probability; however, even if explicitly mentioned, the role of this prior would usually still be quite confusing for generic readers. The authors did even less in this regard by expending 0 words on $Q_W$, and how the evolution to $P_{W|S_j}$ is to be construed.\n\nVery minor notation issue: $\\mathbb E_{P_S}$ vs. $\\mathbb E_{S}$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8lrdAg2cPY", "reviewer": "Reviewer_vrZ6", "summary": "MAC-Bayes bounds (mean approximately correct)  are a  variation of PAC-Bayes bounds that are not necessarily valid with high probability but bound the expected generalization error.\nThe study considers „block-sampled“ MAC-Bayes bounds, in which the data is split into block/batches and the divergence term between prior and posterior is defined on block level.\nThe submitted paper studies the optimization of these „block-sampled“ MAC-Bayes bounds and whether they can be turned into\nPAC-Bayes versions which improve on current PAC-Bayes results, which the authors show to be not possible in general.", "questions": "Please see \"Weaknesses\" above.", "limitations": "", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "I found the general topic of the study interesting.\nI would like to stress that also the negative result is interesting.", "weaknesses": "* The „impossibility result“ in Theorem 2 can be viewed as a general form of the properly cited results by \n\nHrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Formal limitations of sample-wise\ninformation-theoretic generalization bounds. In 2022 IEEE Information Theory Workshop (ITW),\npp. 440–445. IEEE, 2022.\n\n* I was wondering: how are the results related to the results by \n\nRecursive PAC-Bayes: A frequentist approach to sequential prior updates with no information loss\nYS Wu, Y Zhang, BE Chérief-Abdellatif, Y Seldin\nAdvances in Neural Information Processing Systems 37, 17947-17971\n\nwhich - in a different setting - consider a split of the training data and incrementally update the PAC-Bayes bound.\n\n* Section 4: I was somehow not convinced by this example that should show the usefulness of the new bounds. The prior leading to (11) depends on the „batch size“ m. I accept that in PAC-Baysian analysis the prior is not necessary some form of „prior belief“ as in stared Bayesian analysis, but rather a tool to get tight performance guarantees. Still, that the prior depends on m does not feel right to me - where should such a prior come from? Could the authors discuss this in more detail?  The fact that the results are better than without blocks-sampling is then also heavily dependent on the prior (end of  Section 4). Why should this prior be used for the  m=n case? Is the prior real „prior belief“  here? If yes, where does it come from for the m-n case? If not - if it is a tool to get tight bounds- why this choice for n=m?\n\n\nMinor comments:\n\n* Authors forgot to introduce the prior Q_W when introducing PAC-Bayes in equation (1).\n* Can the loss in the example 4 be viewed as some known robust loss function?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)