Generalization Bounds via Meta-Learned Model Representations: PAC-Bayes and Sample Compression Hypernetworks
Authors: Benjamin Leblanc
Mathieu Bazinet
Nathaniel D'Amours
Alexandre Drouin
Pascal Germain
Venue: ICML 2025 poster (2025)
Keywords: Meta-learning
Pac-Bayes
Sample Compression
Hypernetworks
Primary area: general_machine_learning->transfer_multitask_and_metalearning
TL;DR: We investigate hypernetwork architectures for deriving generalization bounds in meta-learning by leveraging the PAC-Bayesian framework and the Sample Compression theory

Abstract: Both PAC-Bayesian and Sample Compress learning frameworks have been shown instrumental for deriving tight (non-vacuous) generalization bounds for neural networks. We leverage these results in a meta-learning scheme, relying on a hypernetwork that outputs the parameters of a downstream predictor from a dataset input. The originality of our approach lies in the investigated hypernetwork architectures that encode the dataset before decoding the parameters: (1) a PAC-Bayesian encoder that expresses a posterior distribution over a latent space, (2) a Sample Compress encoder that selects a small sample of the dataset input along with a message from a discrete set, and (3) a hybrid between both approaches motivated by a new Sample Compress theorem handling continuous messages. The latter theorem exploits the pivotal information transiting at the encoder-decoder junction in order to compute generalization guarantees for each downstream predictor obtained by our meta-learning scheme.

Generalization Bounds via Meta-Learned Model Representations: PAC-Bayes and Sample Compression Hypernetworks
Benjamin Leblanc'
Mathieu Bazinet Nathaniel D'Amours'
Alexandre Drouin
Pascal Germain
Abstract
Query
Both PAC-Bayesian and Sample Compress learn- ing frameworks have been shown instrumental for deriving tight (non-vacuous) generalization bounds for neural networks. We leverage these results in a meta-learning scheme, relying on a hypernetwork that outputs the parameters of a downstream predictor from a dataset input. The originality of our approach lies in the investigated hyperettwrkk architectures that encode the dataset before decoding the parameters: (1) a PAC-Bayesian encoder that expresses a posterior distribution over a latent space, (2) Sample Com- press encoder that selects a small sample the dataset imput along with message from discrete set, and (3) hybrid between both approaches motivated by new Sample Compress theorem handling continuous messages. The latter theorem exploits the pivotal information transiting at the encoder-decoder junction order to compute generalization guarantees for each downstream predictor obtained by our meta-learning scheme.
S
El Ennoder compressor
Decoderr ! reconetracoo
*Ouput
Laieni Ingreserration
Supporast ant
Figure 1: Overview of our meta meta- learning framework.
probabilistic bounds on model's error rate. Applying these techniques to deep neural networks is challenging because classical approaches struggle to account for the true effective complexity of such models (Zhang et al., 2017), which may not well captured by naive measures such as parameter count (Belkin et al., 2019). However, prior work suggests that if one obtain more compact yet expressive rep- resentation of a model's complexity, tighter generalization bounds are possible (Dziugaite et al., 2020; Wang et al., 2022; Kawaguchi et al., 2023), even when it comes to models as big as Large Langage Models (Lotfi et al., 2024a;b).
In this work, we investigate meta-learning framework for obtaining such representations and leverage them establish tight generalization bounds. Our approach is based hypernetwork architecture, trained by meta-learning, and composed of two components: an encoder that projects set of training examples into an explicit information bottleneck (Tishby & Zaslavsky, 2015) and a decoder that generates downstream predictor based this bottleneck. We demon- strate that the complexity of this information bottleneck provides effective measure of the downstream predictor complexity by computing generalization guarantees based on that complexity. Conceptually. our hypernetwork is akin to a learning algorithm that explicitly exposes the complexity of the models it produces. We then show how our approach can used to obtain generalization guarantees in three theoretical frameworks: PAC-Bayesian analysis, sample compression theory, and new hybrid approach that integrates both perspectives, each of which motivates specific architecture for the bottleneck.
1. Introduction
Machine learning is increasingly shaping our daily lives, trend accelerated by rapid advancements in deep learning and the widespread deployment of these models across various applications (c.g., language models and AI agents). Ensuring the reliability of machine learning models therefore more critical than ever. A fundamental aspect of reliability is understanding how well model generalizes beyond its training data, particularly for modern neural networks, whose complexity makes it challenging to obtain strong theoretical guarantees. One way to assess generalization is through
'Département d' d'informatique et de génie logiciel, Uni- versité Laval, Québec, Canada "ServiceNow Research, Montréal, Canada. Correspondence to: Benjamin Leblane <benjamin.leblann 2ww..eebbaaac...l.....c... @uulaval.ca..
We begin by introducing the theoretical frameworks used to obtain generalization bounds (Section 2), including a new PAC-Bayes Sample Compression framework, which we
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Generalization Bounds via Meta-I.carned Model Representations: PAC-Bayes and Sample Compression Hypernetworks
propose in Section 2.3. We then describe our meta-learning approach for training hypernetworks and how it is adapted to each theoretical framework (Section 3). Finally, we present an empirical study evaluating the quality of the obtained bounds and models on both simulated and real-world datasets (Section 4). Our results demonstrate that our approach effectively learns accurate neural network-based classifiers. We also show that the information bottleneck reliably serves proxy for model complexity, enabling the derivation of tight generalization guarantees.
Notable theoretical results. Germain at. (2015) expresses general PAC-Bayesian formulation that encompasses many specific results previously stated in the literature, by resorting on comparator function A } x y + [o. 1], used to assess the discrepancy between the expected empirical loss BR-- (h) and the expected generalization loss En-q CD The theorem states that this discrepancy should not exceed a complexity term that notably relies on the Bullback-Leibbe divergence (L(Q) = En-q In Q(A) P(b))
Theorem 2.1 (General PAC-Bayesian theorem (Germain et al., 2015)). For any distribution D on X' f.r any set H of predictors h : X + Y. for any loss f y x y - [0, 1]. for any prior distribution P over H. for any 6 E (0, 1] and for any convex function A : [0, x [0, 1] - I. with
Related works. The meta-learning framework was pio- neered by Baxter (2000), where a learning problem encom- passes multiple tasks under the assumption that all learning tasks are independently and identically distributed (i.i..) from task environment distribution. Various standpoints have been considered to derive generalization guarantees in this setting, for example the VC-theory (Maurer, 2009;
probability at least 1 - 5 over the draw of S ~ D",, we have
vQ over H : : h~Q
(1)))),
R. (D(li)
m~Q
Maurer et al., 2016) and algorithmic stability (Maurer, 2005; Chen et al., 2020). In recent years, the PAC-Bayesian frame- work has been the foundation of a rich line of work: Pentina & Lampert (2014); Amit & Meir (2018); Rothfuss et al. (2021); Liu al. (2021); Guan et al. (2022); Guan & Lu (2022); Reza- zadeh (2022); Zakerinia et al. (2024). Up to our knowledge, using the sample compression framework (Littlestone & War- muth, 1 1986) to derive generalization bounds for meta-learned predictors is an idea that has not been explored yet.
S KL(Q]IP) + In (Za(m))
with ( (m)= = Es-D" En e (Es(())),(C
A common choice of comparator fuuction is the Kullback- Leibler divergence between two Bernoulli distributions of probability of success q and p.
1-9 9 + +11 - 9) In 1 1-p p
kl = q In p
(1)
2. Learning Theory and Generalization Bounds
for whichIu((m)) S 2/m
The prediction problem. A dataset = {(x,, y5)) is collection of m examples, each of them being feature- target pair (x, 3) E X' x V/ and a predictor is function h : X' + V. We denote H. the predictor space. Let A be a learning algorithm A UREEe( (X' x 3) -> Ht that outputs a predictor A(5) E H. Given a predictor / and a loss function t: y x y + [0, 1]. the empirical loss of the predictor over a set of m i..dd examples is (h) = Σm {(h(x,), yz)- We denote D the data-genen generatnn distribution over X x y such that S D and the generalization loss of a predictor h
To avoid relying on stochastic predictor, disintegrated PAC- Bayes theorems have been proposed to bound the loss of a sin- gle deterministic predictor, as the one of Viallard et al. (2024) reported in the appendix (Theorem E. 1). They allow the study of a single hypothesis (drawn once) from the distribution Q.
2.2. Sample Compression Learning Framework
Initiated by Littlestone & Warmuth (1986) and refined by many authors over time (Attias et al., 2024; Bazinet et al., 2025; Campi & Garatti, 2023; David et al., 2016; ?:
(h) (xx,)>> [((h(x), v)].
Hanneke & Kontorovich, 2021; Hanneke et al., 2019; 2024;
Laviolette et al., 2005; Marchand & ShalorTaylor, 2002;
2.1. PAC-Bayesian Learning Framework
Marchand & Sokolova, 2005; Moran & Yehudayoff, 2016; Rubinstein & Rubinstein, 2012; Shah, 2007), the sample compression theory expresses generalization bounds on predictors that rely only on a small subset of the training set, referred to as the comprexsion set, valid even if the learning algorithm observes the entire training dataset. The sample compression theorems thus express the generalization ability of predictive models as an accuracy-complexity trade-off, measured respectively by the training loss and the size of the compressed representation.
The PAC-Bayes theory, initiated by McAllester (1998; 2003) and enriched by many (see Alquier (2024) for a recent survey), has become prominent framework for obtaining non-vacuous generalization guarantees on neural network since the seminal work of Dziugaite& & Roy (2017). As a defining characteristic of PAC-Bayes bounds, they rely on prior P and posterior Q distributions over the predictor space H. Hence, most PAC-Bayes results are expressed as upper bounds on the Q Q-expected loss of the predictor space, thus providing guarantees stochastic predictor.
The reconstruction function. Once a predictor is learned from dataset S, Le. h A(S), one can obtain
2

---

Generalization Bounds via Meta-L.arrned Model Representations: PAC-Bayes and Sample Compression Hypernetworks
an upper bound on (b( thanks to the sample compres-
Theorem 2.2 is limited in its scope, for many tasks involve non-binary losses (e.g. regression tasks, cost-sensitive classification). The following recent result, due to Bazinet et al. (2025), permits real-valued losses & y x 3 + R. Given a comparator function A analogous to the one classically used in PAC-Bayesian theorems, Theorem 2.3 bounds the discrepaney between the empirical loss of the reconstructed hypothesis R(S). w) on the complement set Sj and its generalization loss on the data distribution 'D.
sion theory whenever it is possible to reconstruct the predictor h from a compression set (that is, a subset of S) and an optional message (chosen from a predetermined discrete message set (t) with a reconstruction function R: : UsEN (X' x )* x f2 + H. Thus, a sample compress predictor can be written
h = w)
(2)
j C {()mm being the indexes of the training samples be- longing to the compression set Sj - {xx, Mj) and E Ω being the message. In the following, we denote the set of all training indices m- {{);;= === and (Pmm) its powerset; for com- pression set indices j E Pmm), the complement js = m j..
Theorem 2.3 (Sample compression real-valued losses (Bazinet et al., 2025)). For any distribution D over X' x V, for any set J S P(m), for any distribution P, over J. for any distribution Po over Q. for any reconstruction function R. for any loss e: y x 3 + BR, for any function A R x R - R and for any 5 E (0, 11, with probability at
An example: the Support Vector Machine (SVM). Con- sider A to be the SVM building algorithm, and S dataset with y = +-1,++1, An easy way of reconstructing A(S) is by choosing the compression set to be Sj. the m support vec- tors of A(S). and having the reconstruction function to be the linear SVM algorithm R = A. Thus, we know that ((;)) A(S)) = ASS) without having to use any message.
least 8 over the draw of S ~ D we have
vj E J.WER A Cs, (R(S).
LD ( (R(S). (3))
JA w) 1 In Pj( Pa(w) 8
I lil
with
Another example: the example-aligned decision stump. Given dataset with y/ = [1] the example-aligned decision stump (weak) learning algorithm A returns a predictor A(S) huc, such that hx (xx)) = 1 if v(xx= -x/))= < 0 or -1 otherwise, for some datapoint x' (af,.... a'ds) E S, direction v E {-1,+1) and index A E (l.....d) d3. We can fully reconstruct the stump with R(S}. u) = u,,, where Sj = {(x','/) is the compression set and = (v, k) is the message.
ح (Cr, ( (R( ((TT
Ja(i.w)
= E
E Tj-DDi TD-D"-
In order compute a numerical bound on the general- ization loss ()), one must commit to choice of A. See Appendix A for corollaries involving specific choices of comparator function. In particular, the choice of comparator function kl(g,p) of Equation (1) leads to Tia w) S 2/m m [j] (see Corollary A.2).
Notable theoretical results. Theorem 2.2 below, due to Laviolette et al. (2005), improves the bound developed for their Set Covering Machine (SCM) algorithm (Marchand & Shawe-Taylor, 2001; Marchand & Taylor, 2002; Marchand & Sokolova, 2005). It is premised on two iata-independent distributions: Po(m) on the compression set indices P(m). and Pn on a discrete set of messages Q Noteworthy, the bound is valid solely for binary-valued losses, as it considers each "successful" and "unsuccessful" prediction to be the result of Bernoulli distribution.
2.3. A New PAC-Bayes Sample Compression F Framework
Our first contribution lies in the extension of Theorem 2.3 to real-valued messages. This is achieved by using a strategy from the PAC-Bayesian theory: we consider a data- intteenndeennent prior distribution over the messages Ω denoted Pn. and a data-dependent posterior distribution over the messages, denoted Qa- We then obtain bound for the expected loss over Qn. Note that this new result shares sim- ilarities with the existing PAC-Bayes sample compression theory (Germain et al., 201 1; 2015; Laviolette & Marchand, 2005; ?), which gives PAC-Bayesian bounds for an expecta- tion of data-dependent predictors given distributions on both the compression set and the messages. Our result differs by restricting the expectation solely according the message.
Theorem 2.2 (Sample compression- binary loss (Laviolette et al., 2005)). For any distribution D over X x Y, for any set J C P(m)., for any distribution P3 over J. any Po. over for any reconstruction function foror any binary loss e: y x y + {0, 1) and for any E (0, 1), with probability at least 1 8 over the draw of S D we have
VjE E J, EΩ: LD (D(R(S),,))) w)) z
Theorem 2.4 IPAC-Baye Sample compression real-valued losses with continuous messages), For any distribution D over X xx V. for any set J C. P(()), for any distribution P3 over J, for any prior distribution Pn over Ω. for any reconstruction function R, for any loss y x y - [o, 1). for any convexfunction A [0,1] x [0, 1] - TK and for any
K
,k ,*((1 (1)r))(1+2 Pi( Pa(w)
argsup re(o,1]
with K = [o (R)
3

---

Generalization Bounds via Meta-I.carned Model Representations: PAC-Bayes and Sample Compression Hypernetworks
5 (0, 11, with probability at least 8 over the draw of
A meta-learning algorithm receives input meta-dataset S { that is collection of datasets obtained from distributions {Di)i= The aim is to learn meta- predictor H that, given only few sample S' (D'ym' for new task D' ~ D, produces a predictor h' = SC(S") that generalizes well, i.e., with low generalization loss (h").
S D",, we have
vj E J, Qn over
A
E @a
Esy (R))
E Lo (R))),w))
AA (m)) ] P)())
In conformity with classical meta-learning literature (Setlur et al., 2020; Vinyals et al., 2016), the following considers that each task dataset S; E S split into a support set S, C S, and a query set T3 S SS; the former used to learn the predictor h; HH(S)) and the latter to estimate hy's loss:
(T((Q]lPPo) + In
m maxjeJ lil
with
Aa(m)= = E R Ji (TT)) GTO-PITD"
C.p
Σ
((bs(x).))
T
See Appendix D for the complete proof of Theo- rem 2.4 and specific choices of A. In particular, lil (Cor. D.2). Note that, in the setting where the compression set size is fixed (i.e., Vj E J, j] c)), Theorem 2.3 is particular case of Theorem 2.4 where the message space f2 is discrete and the posterior Qe a Dirac over a singlew" (i.e., Qn(w")=1)
(x.8))
Meta-learning hypernetworks. We propose to use a hypernetwork as meta-predictor, that is a neural network He with parameters 0, whose output is an array 7 E Rhl that is in turn the parameters of a downstream network hy -R- Y The particularity of our approaches is the use of explicit bottleneck in the hypernetwork architecture. An overview is given in Figure 1. Hence, given a training set S, we train the hypernetwork by optimizing its parameters A in order to minimize the empirical loss of the downstream predictor hy on the query set. That is, given training meta-dataset S ( we propose to optimize the following objective.
Au(m)s Ej-P,
Leveraging the PAC-Bayes disintegrated theorem of Viallard et al. (2024), we also obtain a variant of Theorem 2.4 valid for a single deterministic predictor (S)r,, w²) (with w' drawn once according to Qa), instead of the expected loss ac- cording to Qn- This new result requires the use of singular compression function ((S, Pa) = (Sj.. O which takes as input a dataset and a prior distribution over the messages, and outputs a compression set and a posterior distribution.
min 8
E.p (hew))
N= ((.))
Theorem 2.5 (Disintegrated PAC-Bayes Sample compres- sion bound). For any distribution D over x y, for any set J S P(m), for any prior distribution P, over J. for any prior distribution Ps over Q2 for any reconstruction function R, for any compression function for any loss for any convex function A [0, 1] x [0, - R. for any ê E (0, 1], with probability at least 1- - 6 over the draw of ~ D (which leads to (Sp, 2 = <(S, ), and ~ Q we have
Toward generalization bounds. From now on, our aim is to study variants of hypernetwrk architectures for the meta-predictor Hg, each variant inspired by the learning frameworks of Section 2. By doing so, once Hig is learned, every downstream network h. (S' comes with its own risk certificate, i.e., an upper bound on its generalization loss Lo (h+)) statistically valid with high probability.
f:yx x y + [0, for any any
We stress that, while the usual meta-learning bounds are computed after the meta-learning training phase in order to guarantee the expected performance of future downstream predictors learned on yet unseen tasks, the bounds we provide concern the generalization of downstream predictors once they are outputted by the meta-predictor.
(m max ( [sg.. (R(S)r (n),=()))))))) C) LD (I(SS), ww))) JEJ
2a -
2 a 8
1 + In P)(j") + D. PP) + In Am))
The proof of Theorem 2.5 is given in Appendix E.
3.1. PAC-Bayes Encoder-Decoder Hypernetworks
We depart from previous works on PAC-Bayesian meta- learning and from classical PAC-Bayes, which consider a hierarchy of (meta-)prior and (meta- )oosteior distributions (e.g., Pentina & Lampert, 2014). Instead, we consider distributions over a latent representation learned by the hy- pernetwork H.g. To encourage this representation to focus on relevant information, we adopt an encoder-decoder architec- ture Ho(-) = D (E with 0 = (Ø, w. The encoder E
3. MMeta-Lernnnng with Hypernetworks
The meta-prediction problem. We now introduce the meta- learning setting that we leverage in order to benefit from the generalization guarantees presented in the previous section.
Let a task Dj be a realization of a meta distribution D, and SDDD be a dataset of m, i..dd. samples from given task.
4

---

Generalization Bounds via Meta-Learrned Model Representations: PAC-Bayes and Sample Compression Hypernetworks
Cumry
Query
pression
Encoder
Decoder
Output
S
Sample compresser
Perturboton
Message
Output
Hypentseent
Message
Figure 2: The PAC-Bayee hypernetwork.
Support set
Micsaage
Hyperamenrk
compresses the relevant dataset information into vector J R. (l (typically, 1 < The vector μ then treated the mean of the Gaussian posterior distribution Q2 = (N, I) over the latent representation space, such that the decoder D,: maps the realizations drawn from Qμ to the downstream parameters y. Figure illustrates this architecture.
Figure 3: The Sample Compression hypernetwork.
before in the sample compress literature (to our knowledge). The overall resulting architecture is illustrated by Figure 3.
Reconstructor hypernetwork. In line with the sample com- pression framework of Section 2.2, our reconstructor 'R takes two complementary inputs:
Training objective. Based on the above, learning the proposed encoder-decoder hypernetwork amount to solve
n E p. (Nyr) 7= (p:D((utt)) m. p.= E.
A compression set Sj containing a fixed number of examples;
min 6
with NNO, I).
2. (optionally) A message E {-1,1) = Ω2 that is binary-valued vector of size
Bound computation. Given nnew task sample S' (D')'m, we obtain from the PAC-Bayesian Theorem 2.1 (using prior Po (0, I) over the latent representation space and the comparator function Equation (1)), the following upper bound on the expected loss according to D':
The output of the reconstructor hypernetwork an array 7 e Rll that is in turn the parameters of downstream network h, BRd y Hence, given a (single task) training set S, a compression set Sj C and message reconstructor is trained by optimizing its parameters v in order to minimize the empirical loss of the downstream predictor h,, on the complement set Sj = \
Ω,
11 2 m/m
T" argsspp (EE2s rE.011]
m
(4)
where μ the mean of the Gaussian posterior distri- bution. That is, with probability least 1-6, we have E LD (hy: rT, where the expectation comes from the stochastic latent space.
Σ (x,, Ro (S). (5) (x.y)ES}
min
Note that the above corresponds to the minimization of the empirical loss term (.) of the sample compression bounds (e.g., Theorem 2.3). However, to be statistically valid, these bounds must not be computed on the same data used to learn the reconstructor. Fortunately, our meta-learning framework satisfies this requirement since the reconstructor is learned the meta-training set, rather than the task of interest. Note that the compression set and the message not given, but outputted by C,2, and M
3.2. Sample Compression Hypernetworks
Let design hypernetwork architecture derived from the sample compression theory presented in Section 2.2. Sim- ilar to the previously presented PAC-Bayes encoder- decoder, the architecture detailed below acts as an information bottleneck. However, instead of PAC-Bayesian encoder & mapping the dataset to a latent representation, we consider sample compressor Co, that selects a few samples from the training set. These become the input of reconstructor R. that produces the parameters of a downstream predictor, akin to the decoder in our PAC-Bayesian approach. In line with the sample compress framework, our reconstructor Ry optionally takes additional message input, given by a message compressor Møz- This amounts to learn the reconstruction fuconttraciionnuucttoo;; an idea that has not been envisaged
Training objective. Our goal is to learn parameters th, Φ1 and du such that, for any task D' ~ D producing S'~ (D')m" the resulting output gives rise to downstream predictor hy of low generalization loss E (hyr), with
'' Ry Co, (S') M (S'))
(6)
Given a training meta-dataset S ( we propose to
5

---

Generalization Bounds via Meta-Learrned Model Representations: PAC-Bayes and Sample Compression Hypernetworks
optimize the following objective:
Query eet
Hsperrstoons
Compression bet
(s)) (8.)) (7)
C.p (1ers) Rx- (S))
min 1.01
Surppl ComSrnnac
Reconszaatix
Note that the learning objective a surrogate for Equa- tion (5), as the complement of the compression set Sj is replaced by the query set F, in Equation (7). The pseudocode of the proposed approach can be found in Appendix G.
Message oroodot
Support aut
Ponurbatoo (r)
Meesage
Figure 4: The PAC-Bayes Sample Compression hypernetwork.
Bound computation. When the 0-1 loss is used, the gener- alization bound from Theorem 2.2 is computed, using a fixed cor the compression sets; given a dataset size m'' we use J= [j P(mm) jj c} and a uniform probability dis- tribution over all distinct compression sets (sets that not permutations of one another): = ()( = ('r') Vj E J. When using the optional message compressor module, we set a message size b and a uniform distribution over all messages of size b: Pa(w) = 2- You E {-1, 13,, leading to the following upper bound on the loss:
Training objective. Based on the above formulation, we obtain the following training objective:
n E E (kan) n- R= (C.r (S.), E,z (5:) (s)()))t)) (5)++))
min 14.01:92 11
with E (0,1))
Bound computation. From Theorem 2.4, using fixed compression set size a prior Pn.0 N N I) over the real- valued message space of size b, a uniform probability over the compression set choice p = (i(
r'= argsup rE(0.1]
Σ
K
m'-c)
m'
k )
(1-1)-
(w)) Vj E J.
and the comparator function of Equation (1), we obtain the following upper bound on the expected loss:
with K = [5)Cs((
When real-valued loss is used, applying Theorem 2.3 with the comparator function of Equation (1), we obtain the following upper bound on the loss:
T T argsup kl E Esy all +In 2ym rE|0,1]
m'
That is, with probability at least 5, have E CD (hy- r", where the expectation comes from the stochastic message treatment.
r" argsupp kl (Esg(hy). m' In re(o.1]
26+1
m
pd
To compute the disintegrated bound of Theorem 2.5, we choose Ç to output the compression set SJ = Co, (S') and normal distribution centered on the message Eag (S"), denoted Q (NEE, (S'), Thus, have
is, Co (
S T" with probability at least 8.
3.3. PAC-Bayes Sample Compression Hypernetworks
As a third hypemeework architecture, the new theoretical per- spective presented in Section 2.3 led a hybrid between pre- vious PAC-Bayesian and sample compression approaches.
((S', Pn) (S, Q After sampling a message w Q we define 7' = ( Applying Theorem 2.5 with a = 2, we have the following upper bound on the loss:
Recall that Theorem 2.4 is obtained by handling the message of the sample compress framework in a PAC- -CC-Baysi fashion, enabling the use of a posterior distribution over con- tinous messages. Hence, this motivates revisiting the sample compress hypernetwork of Section 3.2 by replacing the message compressor Mgz (outputting a binary vector) by the PAC-Bayes encoder of Section 3.1. We denote the latter & whose task is to output the mean 4 R² of posterior distribution Q2 = N(, I) over real-valued message space Ω = gb_ The sample compressor remaining un- changed from Section 3.2, the PAC-Bayes Sample Compress architecture is expressed by HG((.) = (Cs, (+), E0g (.)). Figure illustrates the resulting architecture.
- Ka (a((ss((h)).)) | In 16ymm rE(0.1]
p-63
m'
That is, CD (hyr) ST" with probability at least
4. Experiments
We now study the performance of models learned using our meta-learning framework as well as the quality of the obtained bounds. Then, we report results on a synthetic meta-learning task (Section 4.2) and two real-world meta-learning tasks (Sections 4.3 and 4.4).
6

---

Generalization Bounds via Meta-Learned Model Representations: PAC-Bayes and Sample Compression Hypernetworks
the
6th
-25 5o Mi 123
35 -3
25 50 183
11-007
Pg
Figure Examples of decision boundaries given by the down- stream predictors, with a compression set size 3 and without message, on test datasets. The stars show the retained points from the sample compressor Co... As shown by the axes, each plot is centered and scaled on the moons datapoints.
Figure 5: Illustration of decision boundaries generated by downstream predictors hy, when parameters are given by PAC-Bayes decoder (4) with input 14 (J4, w22) IR2 The encoder generated the message (0.97, -0. 0.27) on shown training datapoints. Left: The first latent dimension is fixed (I = 0.97), while the second varies (I22 E [-1,1], 1)). Right: The first dimension varies (/1 E [-1,,]] while the second is fixed fr -0.27.
having an important representation size (see Equation (4)).
As for the message compressor, it has the same architecture as the PAC-Bayes encoder, but its final activation is the sign function coupled with the straight- estimator (Hinton, 2012) 2) in order to generate binary values.
4.1. Implementation Details
In each task, we split our training datasets into train and validation datasets; for each meta-lcarning hypernetwork, the hyperparameters are selected according to the error made on the validation datasets. Detailed hyperparameters used for each experiment are given in Appendix H.!
Sample compressor. Given a fixed compression set size c, the sample compressor Cş, is composed of e independent attention mechanisms (Bahdanau et al., 2015). The queries are the result of DeepSet module (see Definition 4.1), the keys the result of a fully-connected neural network and the values are the features themselves. Each attention mech- anism outputs probability distribution over the examples indices from the support set, and the example having the highest probability is added to the compression set.
DeepSet dataset encoding. The hypernetwork (S) must be invariant to the permutation of its input S: the order of the examples in the input dataset should not affect the resulting encoding. Modules such as FSPool (Zhang et al., 2020) or a transformer (Vaswani et al., 2017) ensure such property. Our experiments use a simpler mechanism that is inspired by the DeepSet module (Zaheer et al., 2017).
Decoder reconstructor. The input of the decoder / recon- structor is passed through a DeepSet. Then, both the obtained compression set embedding and the message (if there is one) are fed to feedforward neural network, whose output constitutes the parameters of the downstream network.
Definition 4.1 (DeepSet Module). For binary tasks: given a data-matrix X E mRm and a binary label vector "M the output of DeepSet module is the embed- ding z E Rd obtained by first applying a fully-connected neural network d : Rdd - R2d to each row of X, sharing the weights across rows, to obtain a matrix M E m=xdd and then aggregating the result column-wise: z m M
y e (-",
Nomenclature. In the following, we refer to our different meta-predictors as such: PAC-Bayes Hypernetoor (PBH); Sample Compression Hypernetoork, without messages (SCH_) and with messages (SCH,); and PAC-Bayes Sample Compression Hypernetwork (PB SCH).
For K class tasks, where K 2:2: given a data-matrix X E Rxdd and a one-hot encoding of the label Y. the output of DeepSet module the embedding E Rd", obtained by first applying fullyyconneeted neural network I.: dR Rd' to each row of X, where the label representa- tion have been appended, to obtain matrix M E Rm=x (d' +x) and then aggregating the result column-wise: z
4.2. Numerical Results on a Synthetic Problem
We first conduct an experiment on the moons 2-D synthetic dataset from Scikit-learn (Pedregosa al., 2011), which consists of two interleaving half circles with small Gaussian noise, the goal being to better understand the inner workings of the proposed approach. We generate tasks by rotating (random degree in [0, 360)), translating (random moon center in [- 10)²), and re-scaling the moons (random scaling factor in [0.2, 5)). The moons meta-train set consists of 300 tasks of 200 examples, while the meta-test set consists of 100 tasks of 200 examples. We randomly split each dataset into support and query of equal size. See Appendix H for implementation details.
1 1 m
PAC-Bayes encoder / message compressor. The PAC- Bayes encoder takes as input a dataset and outputs a continuous representation.? module, followed by a feedforward network. Its last activation function is Tanh function, so that the message is close to 0, leading to bound that is not penalized much from
is composed of a DeepSet
OOr code is available at https::/ /ttp://ggtttb/// com/ GRAAL- Research DeepRM.
PI a slight language abuse, from now on, this continuous representation will be referred to as message, just like the output of the message compressor.
Figure displays the decision boundaries of a predictor trained with the PBH model, given a message of size |p| 2,
7

---

Generalization Bounds via Meta-I.carned Model Representations: PAC-Bayes and Sample Compression Hypernetworks
on a random test dataset. We plot the result for many values of the message, displaying its effect on the decision boundary of the resulting downstream predictor; we observe that each dimension of the message encapsulates a unique piece of information about the task at hand.
This matter is empirically confirmed by the next experiment.
4.4. Test Case: Binary MNIST and CIFAR100 Tasks
In light of the analysis made in the previous subsection, we now explore an experimental setup where a prior model can- not encompass most of the information of the various tasks. To do so, we create variety of binary tasks involving the var- ious classes of the MNIST CIFAR100) dataset, where a task corresponds to a random class versus another one. We create 90 (150) such tasks, where the meta-test set corresponds to all of the tasks involving either label 0 or label I, chosen at random, leading to a total of 34 (50) meta-test tasks. Each training task contains 2000 (1200) examples from the train split of the MNIST (CIFAR 100) original task, while each test task contains at most 2000 (200) examples from the test split of the original task. We consider the same benchmarks as previously. We report the test bounds and test errors on the novel tasks of various methods in Table with their corresponding latent representation information in Table 3.
Figure 6 displays the decision boundaries of a predictor (trained with the SCH_ meta- predierre with compression set of size c = 3) for three different test tasks. We see that the sample compressor selects three examples far from each other, efficiently compressing the task, while the reconstructor correctly leverages the information contained in these examples to correctly parameterize the downstream predictor, leading to an almost perfect classification. Recall that SCH does not incorporate any message.
4.3. Test Case: Noisy MNIST
Following Amit & Meir (2018), we experiment with three dif- ferent yet related task environments, based on augmentations of the MNIST dataset (LeCun et al., 1998). In each envi- ronment, each classification task is created by the random permutation of given number (100, 200, and 300) of pixels. The pixel permutations are created by a limited number of lo- cation swaps to ensure that the tasks stay reasonably related in each environment. In each of the three experiments, the meta- training set consists of 10 tasks of 60'000 training examples, while the meta-test set consists of 20 tasks of 2000 examples.
As expected, in such setting, when it comes to the benchmarks, the posterior for each task is required to be truly different from the prior in order to perform well (as attested by the strawman's 's test error, being similar to a random guess), We present in Table 4 the penalty (KL) value measuring the distance between the prior and posterior for two benchmarks on both the pixel swap experiments and the binary MNIST variant. There is significant gap between the KL value re- ported for the various pixel swap tasks and the binary MNIST task, which confirms our insight. Thus, the benchmarks methods generate uninformative generalization bounds, even though their test loss is competitive. On the other hand, most of our approaches achieve competitive empirical perfor- mances while also having informative generalization bounds, since the downstream predictors can be truly different from one another without impacting the quality of the bound.
We compare our approaches to algorithms yielding PAC- Bayesian bounds as benchmarks. The reported bounds concern the generalization property of the trained model on a given test task. We chose fully connected network with no more than 3 hidden layers and a linear output layer as a backbone, as per the selected benchmarks. We also report the performances of strawman: an opaque encoder outputting nothing, followed by a decoder which input is a predefined sole constant scalar; though the reconstructor can be trained, the hypernetwork always generates the same predictor, no matter the input. We report the test bounds and test errors on the novel tasks of various methods in Table 1. More details about the experiment setup can be found in Appendix H.
The architectures reported in Table 3, along with the empiri- cal performances in Table 2, confirm that 1) the encoder / the message compressor and the sample compressor correctly distill the particularities of the task at hand, and 2) that the reconstructor is able to utilize this representation to judiciously generate the downstream predictor.
When it comes to generalization bounds, our approaches outperform the benchmarks. However, our approaches cannot learn from the task environment, their performances being similar to those of the strawman. This is because the difference between the various tasks is very subtle; such a setting is not well-suited for our approaches, which rely on the encapsulation of the differences between tasks a message or a compression set. The benchmark methods per- form well because the posterior (over all of the downstream predictor), for each test task, is similar to the prior. Indeed, the various tasks do not vary much; this is reflected by a single predictor (the strawman, an opaque hypernetwork) yielding competitive performances across all of the test tasks.
Figure 7 depicts the test error and generalization bound for our PB SCH algorithm as a function of both the compression set size and the message size. We recall that Tables 1 and 2 report the performances of the models obtaining the best validation error, Figure 7 helps to grasp the inner workings of our proposed approach: using a larger message seems better-suited for minimizing the test error, but trf between the compression set size and the message size is required to obtain the best bounds. Interestingly, when the message size {4] is restricted to be small, we clearly see the benefit of using a compression set (c > 0).
8

---

Generalization Bounds via Meta-L.crrned Model Representations: PAC-Bayes and Sample Compression Hypernetworks
Table I: Comparison of different meta- leta-lea methods on the MNIST-pixels swap task. The 95% confidence interval is reported for generalization bound and test error, computed over 20 test tasks. The best (smallest) result in each column is bolded.
100 swap
200 Pixels swap
300 swap
Algorithm
Bound (4)
Test (L)
Bound (4)
error (L)
[ound
Test (3)
(Pentina & Lampert, 2014)
0.190 0.022
0.019 0.001
0.026 0.030
0.002
0.334 = 0.036
0.038 = 0.003
(Amit & Meir, 2018)
0.138 +: 0.024
0.016 0.001
0.161 + 0.002
0.020 +: 0.001
0.329 + 0.081
0.040 = 0.681
(Guun & Lu. 2022) kl
0.119 0.024
0.017
0.001
0.189 1: 0.027
0.027
0.026
0.001
0,359 1 0.042
0.030 = 0.002
(Guan & Lu, 2022)- Catonii
0.093 0.027
0.015
0.128
0,019
0,210 = 0.035
0.024 0.001
(Zakerinia et al., 2024)
0,053 0.020
0.019 0.1346
0.108 0.037
0.026
+ 0.263
0.149 = 0.039
0,035 = 0.547
PBH
0.068 0.007
0.027 = 0.005
0.112
0.076 0.018
0,219 0.031
0.186 = 0.060
SCH
0.067 0.007
0.029
0.007
0.129 0.023
0.084 0.017
0.193 1 0.038
0.162 0.043
SCHL,
0,035 0.012
0.024
0.005
0.091 +: 0.022
0,075
+ 0.019
0.177 + 0.032
0.153 0.028
PB SCTT
0.068 1 0.007
0.027
0.005
0.11211 0.021
0.076
1 0.018
0,219 0.031
0.186 0.060
Oparue encoler
0.043 1 0.003
0.037
0.006
0.092 4 0.019
0.087
1: 0.018
0.173 1 0.030
0.159 = 0.031
Round on average over the decoder output.
PB SCH on the binary MNIST task, test error (%)
PB SCH on the binary MNIST task, generalization bound (%)
0-
4B A37:36
43 -25.65
on .2525
22
-2145
45
44-4
+:2-4
2-
22,10
+3374
24.95 +0
25.32
+1.2
20.24
18.05
+0.1
-10
2-
+:3
-21.0
.3113
-18.5
-16
-55
Message size
22.75
11639
23.55
-20.0
22.46
-13.0
22.90
-1
13.45
-3.35
35
Message s20
AG
+25
+1/30
1351
8-
19.5 19.99
113.03
21.79
-24.4
20.19
.18.3
21,23
18:53
-25.7
8-
37.47
A0300
38,
+:340
38.26
+1h.1
42.20
+10-4
43
10
15.41
23.02
20.29
17,80
20.78
25
1.4
-26-7
22110
.1113
-13.5
-45
64-
24.72
25:4
18.90
-14.11
15:12
.1.39
17.13
.12.82
10.43
-36/3
20
64-
6:4
54.31
53.83
+10.0
53.41
-11.
128
13.83
18.60
15.89
15.39
13:29
15
120
59.67
-23.0
63,44
.1201
63.40
.1322
.13.9
-25
0
12
0
8
12
Compression set size
Compression
Figure 7: Teso
error and generalization bound for the PB SCH algorithm as a ffunction of both the compression set size and the message size on binary MNIST tasks. The 95% confidence interval is reported for both the generalization bound and the test error, computed over 34 test tasks.
Table 2:
Comparison of different meta-lcarning methods on the MNIST and CIFAR 100 binary tasks. The 95% confidence interval reported for generalization bound and test error, computed over test tasks. The best (smallest) result in each column is bolded.
Table 4: KL value of two benchmarks on the pixel swap tasks and the binary MNIST task. The 95% confidence interval is reported for generalization bound and test error, computed over 20 test tasks,
Algoditimn
Paeess swap
Pisels swap (300 Pisels seop
binary MNIST
Alguritham
Hound (L)
MNIST
Test error
(ound(L)
CIPAR1OO
Test erroe (1)
(Zakerinia al., 2024)
(Pontin & Lampert, 3014)
63.91 +
3.833 = 0.444
3,760 2: 0,750
1599 54.78
9.604 2: 1.035
223.9 58.60
661
14 = 0.018
(Pestina&& & Lampert 2014)
0.767
0.001
+
0.00 + 0.001
0.490 +: 0.070
(Amit & Meir, 2018)
1372 + 23.36
0 + 0.212
950.9 + 343.1
0.284
+ 0.120
5. Conclusion
(Guan Lu, 2022) kll
0.366
0.221
0.802 0.001
0.189
0:073
(Guin & Lu, -0n
1.132:0000
0.351
0.212
1,577 1: 0.567
0.282
0.122
(Rezazddhh,
0.005
0.366
0.221
10.91
+: 0.368
0:334
0.0199
We developed a new paradigm for deriving generalization bounds in meta-learning by leveraging the PAC-Bayesian framework or the Sample Compression theory. We also present a new generalization bound that permits the coupling of both paradigms. We develop meta-learning hypernet- works based on these results. We show that many PAC-Bayes approaches do not scale when the various tasks in an envi- ronment have important discrepancies while our approaches still yield low losses and tight generalization bounds.
(aaeeiini ot al. 2024)
0.644 4: 0.021
0:351
0212
0.53
4: 0.315
0.281
4: 0.125
PBH
0,9771 0.107
0.150
1: 0.114
0.7477 0.022
0.295
0.103
SCH
0.187
0.278
0.076
0,600
-
0.118
SCH
0,280 4: 0,148
0.155
4- 0.109
0,445
4 0.101
0.305
0.1422
SCH
0.59711..107
0.11
0.9441
0.295
0.103
Opaque encoder
0.533 4: 0,104
0.497
0-133
0.544 4: 0.112
0.506 0.0101
BBund on average over the docoder outpur.
Table 3: Selected architecture for the sample compression hypernetwor algorithm (we recall that e corresponds to the compression set size, while (p). b corresponds to the message size); hyperparameter choices can be found in Appendix H.
The approaches we presented could be enhanced by having the model dynamically select the compression set size and the latent representation (or message) size or using larger archi- tecture for the reconstruction function, inspired from Mother- Net (Mueller et al., 2024). Finally, since the bound values are not impacted by the complexity of the decoder or the down- stream predictor, our approach could be used to get tight gen- eralization bounds for very large models of the multi-billion parameter scale, assuming that the parameters varying across tasks admit a compact representation (e.g., a LoRA adapter).
SC Hypemetwork
MNIST
CIFAR100
e
PBH
NIA
128
N/A
128
SCIL.
NIA
N/A
SCH_.
64
1
128
PB SCH
0 128
0
128
See Table 5 in Appendix H for results involving the bound from Theorem 2.3 and Theorem 2.5. See also in Appendix H a decomposition of the various terms involved in the composition of our bounds and the benchmarks'.

---

Generalization Bounds via Meta-L.arrned Model Representations: PAC-Bayes and Sample Compression Hypernetworks
Impact Statement
Dziugaite, G. K., Drouin, A., Neal, B., Rajkumar, N., Caballero, E., Wang, L.,, Mitliagkas, I., and Roy, D. M. In search of robust measures of generalization. In NeurIPS, 2020.
This paper presents work whose goal is to advance the field of Machine Learning. Since we work for the better certification of machine learning algorithms, we do not see any potentially harmful societal consequences of our work.
Germain, P., Lacoste, A., Laviolette, F., Marchand, M., and
Shanian, S. PAC-Bayes sample-compresioon approach to kernel methods. In ICML, 2011.
Acknowledgements
This research is supported by the NSERC/Intact Finan- cial Corporation Industrial Research Chair in Machine Learning for Insurance. Pascal Germain is supported by the Canada CIFAR AI Chair Program, and the NSERC Mathieu Bazinet is supported by FRONT B2X scholarship (343192, doi: /1tp://///0009977333333399
Germain, P., Lacasse, A., Laviolette, F., Marchand, M., and Roy, J.-F. Risk bounds for the majority vote: From a PAC- Bayesian analysis to learning algorithm. JMLR, 2015.
Guan, J. and Lu, Z. Fast-rate PAC-Bayesian generalization bounds for meta-learning. In ICML, 2022.
Discovery grant
Guan, J., Lu, Z., and Liu, Y. Improved generalization risk bounds for meta-learning with PAC-Bayes-ki analysis. In ICLR, 2022.
References
Alquier, P. User-friendly introduction to PAC-Bayes bounds. Found. Trends Mach. Learn., 2024.
Hanneke, S. and Kontorovich, A. Stable sample compression schemes: New applications and an optimal SVM margin bound. In AL7, 2021.
Amit, R. and Meir, R. Meta-learning by adjusting priors based on extended PAC-Bayes theory. In ICML, 2018.
Hanneke, S., Kontorovich, A., and Sadigurschi, M. Sample compression for real-valued learners. In Algorithmic Learning Theory, 2019.
Attias, I., Hanneke, S., Kontorovich, A., and Sadigurschi, M. Agnostic sample compression schemes for regression. In /CML, 2024.
Hanneke, S., Moran, S., and Tom, W. List sample compression and uniform convergence. COLT, 2024.
Bahdanau, D., Cho, K., and Bengio, Y. Neural machine translation by jointly learning to align and translate. In ICLR, 2015.
He, K., Zhang, X., Ren, S., and Sun, J. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In ICCV, 2015.
Baxter, J. A model of inductive bias learning. J. Artif. Intell.
Res., 2000.
Hinton, G. Neural networks for machine learning. coursera, video lectures, 2012.
Bazinet, M., Zantedeschi, V., and Germain, Sample compression unleashed: New generalization bounds for real valued losses. In AISTATS, 2025.
Kawaguchi, K., Deng, Z., Ji. X., and Huang, J. How does in- formation bottleneck help deep learning? In ICMI, 2023.
Belkin, M., Hsu, D., Ma, S., and Mandal, S. Reconciling modern machine- learning practice and the classical bias-variance trade-off. PNAS, 2019.
Kingma, D. P. and Ba. J. Adam: A method for stochastic optimization. In ICLR, 2015.
Laviolette, F. and Marchand, M. PAC-Bayes risk bounds for sample-compressed Gibbs classifiers. In /CML, 2005.
Campi, M. C. and Garatti, S. Compression, generalization and learning. JMLR, 2023.
Laviolette, F,, Marchand, M., and Shah, M. Margin-sparsity trade-off for the set covering machine. In ECMI,, 2005.
Chen, J., Wu, X., Li, Y., Li, Q. Zhan, L., and Chung, F. A closer look at the training strategy for modern meta-learning. In NeurIPS, 2020.
LeCun, Y., Bottou, I.,, Bengio, Y., and Haffner, Gradient- based learning applied to document recognition. IEEE, 1998.
David, O., Moran, S., and Yehudayoff, A. Supervised learning through the lens of compression. In NIPS, 2016.
Littlestone, N. and Warmuth, M. K. Relating data compression and learnability. Technical report, 1986.
Dziugaite, G. K. and Roy, D. M. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In UAI, 2017.
Liu, T., Lu, J., Yan, Z., and Zhang, G. PAC- BAC-Bayes bounds for meta-learning with data-dependent prior. CoRR, 2021.
10

---

Generalization Bounds via Meta-L.crrned Model Representations: PAC-Bayes and Sample Compression Hypernetworks
Lotfi, S., Finzi, M. A., Kuang, Y., Rudner, T. G.J., Goldblum, M., and Wilson, A. G. Non-vacuous generalization bounds for large language models. In ICML, 2024a.
Setlur, A., Li, O., and Smith, V. Is support diversity
necessary for meta-learning? CoRR, 2020.
Shah, M. Sample compression bounds for decision trees. In ICML, 2007.
Lotfi, S., Kuang, Y., Finzi, M., Amos, B., Goldblum, M., and Wilson, A. G. Unlocking tokens as data points for generalization bounds on larger language models. In NeurlPS, 2024b.
Thiemann, N., Igel, C., Wintenherger, O., and Seldin, Y. A strongly quasiconvex PAC-Bayesian bound. In ALT, 2017.
Tishby, N. and Zaslavsky, N. Deep learning and the infor- mation bottleneck principle. In 2015 IEEE Information Theory Workshop, 2015.
Marchand, M. and Shawe-Taylor, J. Learning with the set covering machine. In ICML, 2001.
Marchand, M. and Shawe-Taie Taylor, J. The covering machine. JMLR, 2002.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, I.., Gomez, A. N., Kaiser, I.., and Polosukhin, Attention is all you need. NeurlPS, 2017.
Marchand, M. and Sokolova, M. Learning with decision lists of data-dependent features. JMLR, 2005.
Viallard, P., Germain, P., Habrard, A., and Morvant, E. general framework for the practical disintegration of PAC-Bayesian bounds. Machine Learning, 2024.
Maurer, A. Algorithmic stability and meta-learning JMIR, 2005.
Maurer, A. Transfer bounds for linear feature learning.
Vinyals, O., Blundell, C., Lillicrap, T., Kavukcuoglu, K., and Wierstra, D. Matching networks for one shot learning. In NeurIPS, 2016.
Machine Learning, 2009.
Maurer, A., Pontil, M., and Romera-Parceee B. The benefit of multitask representation learning. JMLR, 2016.
Wang, Z., Huang, S., Kuruoglu, E. E., Sun, J., Chen, X., and Zheng, PAC-Bayes information bottleneck. In ICLR, 2022.
McAllester, D. A. Some PAC-Bayesian theorems. In COLT, 1998.
Zaheer, M.. Kottur, S., Ravanbakhsh, S., Póczos, B., Salakhutdinov, R., and Smola, A. Deep sets. In NIPS, 2017.
McAllester, A. A. PAC-Bayesian stochastic model selection. Machine Learning, 2003.
Moran, and Yehudayoff, A. Sample compression schemes for VC classes. JACM, 2016.
Zakerinia, H., Behjati, A., and Lampert, C. H. More flexible PAC-Bayesian meta-learning by learning learning algorithms. In JCML, 2024.
Mueller, A. C., Curino, C. A., and Ramakrishnan, R. Mothernet: Fast training and inference via hyper-network transformers. In NeurlPS Third Table Representation Learning Workshop, 2024.
Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, Understanding deep learning requires rethinking generalization. In ICLR, 2017.
O.
Pedregosa, Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., and Duchesnay, E. Scikit-learn: Machine learning in Python. JMLR, 2011.
Zhang, Y., Hare, J. S., and PrüigelBBnnett, Espool: Learning set representations with featurewise sort pooling, In ICLR, 2020.
Pentina, A. and Lampert, H. A PAC-Bayesian bound for lifelong learning. In 2014,
Rezazadeh, A. unified view on PAC-Bayes bounds for meta-learning. In /CML, 2022.
Rothfuss, J., Fortuin, V., Josifoski, M., and Krause, A. PA- COH: bayes-optimal meta-learning with muc-guarantees. In /CML, 2021.
Rubinstein, B. I. P. and Rubinstein, J. H. A geometric approach to sample compression. JMLR, 2012.

---

Generalization Bounds via Meta-L.arrned Model Representations: PAC-Bayes and Sample Compression Hypernetworks
A. Corollaries of Theorem 2.3
For completeness, we present the corollaries of Theorem 2.3 derived by Bazinet et al. (2025). Corollary A.1 (Corollary 4 of Bazinet et al. (2025)). In the setting of Theorem 2.3, with
Ac(1,p) = - In( -1-e )p - -Cq (where C > 0),
with probability at least 1 - 8 over the draw of ~ Dm,, we have
VJE M(Ji))
1
exexp exp (CC(,, In In(P((i) PM(U)) (w) -8)
()) - 1- c-
1 -
Corollary A.2 (Corollary 6 of Bazinet et al. (2025)). In the setting Theorem 2.3, with
9 (1 A(g,p) kl(g. p) -n p
(). In 1- 9
p
with probability at least 1 - 8 over the draw S ~ DD,, we have
vj E J.w E M(II kl (a(Cs, (
2 m -
In
jl
Pr(j) (w) .
Corollary A.3 (Corollary 7 of Bazinet et al. (2025)). In the setting of Theorem 2.3. for any X > O, with Agg. p) A(p q). with 2² ----ub---eee sub-Gaussian loss function y x y > R, with probabiliy at least 1 over the draw of 5 ~ D"n we have
As 2
In(Pr(i) PM (w)
Vj E J,w E M(U)) (D(((()) < Ls, (R(S),W))
A(m j
B. General PAC-Bayes Sample Compression Theorems
We derive two new PAC- PAy-Bayes Sample compression theorems for real-valued losses, both for the loss on the complement set and the train set. Theorem B.I extends the setting of Laviolette & Marchand (2005); ?); Thiemann et al. (2017), whilst Theorem B.2 extends the setting of Germain et al. (201 1; 2015).
B.1. First General PAC-Bayes Sample Compression Theorem
We first present new general PAC-Bayes Sample Compression theorem, from which will derive a sample compression bound for continuous messages. Interestingly, this theorem is directly at the intersection between PAC- -CC-Bays theory and sample compression theory. Indeed, if we restrict the model to have no compression set, this bound reduces to Theorem 1. Moreover, if we restrict the model to a discrete family Q2 and to Dirac measures as posteriors on J and Ω this bound is almost exactly reduced to Theorem 2.3, albeit being possibly slightly less tight, as the complexity term denominator m - [j] the latter is replaced by the worst case: m maxje [j]
Theorem B.1 (PAC-Bayes Sample Compression). For any distribution 'D over X x foror any reconstruction function R, for any set J C P(m). for any set of messages Qt for any data-independent prior distribution P over Ω, for any loss E: y + [0, 1). for any convex function A [0,1] x [0,1] - R and for any 8 E (0, 1), with probability least 1 8 over the draw of S T have
YQ over Ω
KL[( (As(m))
A
E Esg (R) Co (R(S,.))) (
<
m maxjeJ j
with
(m (m- (
As(m)
E
E
E
(Py)~PTy>D To Dm-
12

---

Generalization Bounds via Meta-L.crrned Model Representations: PAC-Bayes and Sample Compression Hypernetworks
Proof. With ry 0, our goal is bound the following expression
7
Es, (R(S).W)), Cp (R) (Jw)n
We follow the proof of the General PAC-Bayes bound for real-valued losses of Germain et al. (2015). We first apply Jensen's inequality and then use the change of measure inequality to obtain the following result.
AQ over J Ω:
A
E Es, (R(S), w)), E
Co (R(S),
(jw)QQ
s E (j))Q
7
(Cs (R(S3. W)): LD (R(S). W))
(Jensen's Inequality)
e n S (R((S) (1(3)))))
KT( In
E (م:م
(Change of measure)
Using Markov's inequality, we know that with probability at least over the sampling ~ DD" we have
vQ over J :: A
Ls, (R(S), E Lo (R(S),W)) KL(QQIP) +In ( E Ee n (arr (1)3 (ww~Q
E (nwNQ
T-D" (1.)~P
By choosing to define Q and on instead of on the hypothesis class, the prior independent the dataset. can then swap the expectations finish the proof.
We the independence of the prior to the dataset and the i.idd assumption separate Tj and Tj T \ Tj obtain the following results.
I (Ee, (R(T) (
E T~D
E (jwe
م (Er, (R(T)W))).CC (R(T),))))
E
E
(Independence of the prior)
UN)NPINDM
e (2 (8(1)1)))
E U
E
E TT-D=-u
(i.i.d assumption)
For jolj J, we need to bound the moment generating function
n (Br (R(T).)))
E Ty-Dul T D--
E
To bound the moment generating function using the usual PAC-Bayes techniques, we need r S m for for e J. Thus, the largest value of 1 (which gives the tightest bound) that can be used r7 m maxje. li).
As the exponential is monotonically increasing and maxgej lil < v. we have
(R(T,,)) <
(m- (m-JD4 (Exg (R(0) (RC),w)) = As(m).
E
E Di-Dul Ty-D--
Ti~Dlil TJ-D"
13

---

Generalization Bounds via Meta-I.crrned Model Representations: PAC-Bayes and Sample Compression Hypernetworks
B.2. Second General PAC-Bayes Sample Compression Theorem
We now extend the setting of Germain al. (2015), by making the bound rely on Ls(-) instead of Lsy(-).
Theorem B.2 (PAC-Bayes Sample Compression). For any distribution D over X x for any reconstruction, function R, for any set J C P(m), for any set of messages S2 for any data-independent prior distribution P Pover J S for any loss t: y x > [0, 1]. for any convex fincttin A [0, 1] [0. 1] I, with B sup (gq, p). anr any ò & (0, 1]. with probability at least 1 - 8 over the draw S ~ DD", we have
VQ over J x Q
KL(Q + In (Aa(m))
(m)
A
E (1/))
Es W)), E LD (R(S), 5 maxjeJ
5
with
(m-mmy ma UD
(m- (1110)((((0100000)))))0007000000 E Tj Ty-Da Ty--Dm-ial
Aa(mm)
E (WNP
Proof. We start from the end of the proof of Theorem B.I, after using the i.i.d. assumption. As the loss of the hypothesis is computed on the data used define R(T], w). this term cannot be bounded straightforwardly as before. To tackle this problem, we assume that A is bounded. We want to remove the need compute the loss on examples Tj = T \ TJ in the following term.
E (Er (R(T),W)))CC (R((),W)) (with rj > 0).
E (P P DilD To
Following the work of Germain et al. (2015), we separate the loss:
()(((T].W) = (R(T)..)(
1
1
(()()) +
Σ
())(T).W)(ss))
EET;
(m..9))
1
li]
(I)(T),w))xx))
[(R(T), ().)
m
m [
EET
(E
1
j| Ery (R(T), w)) + (m (ū1) (r5((
m
With this new expression, we have
a n (R(T) (()))
E
E
E
(PIDPIDD
1M
e !nl Erg (R(T) الليت (7)( (X((),,0)
E
E
E
(w) Ti Ty D
m (Er, (RIT) w)), (x(T) m1m-1112 a (RT) (R(T)W))) (Jensen inequality)
<
Tjm
E sup p A(ap)t -لm-نبي ا (Br (B(T,,0)
E
E
( Tj
E
n
sup oe ((p.))
E
E
un S (Er, (R)T),)))cCo (R(T,W)))
Tj To
26m amm-1l W1 s (21,)011),))).c (3((),w0))
E
e
m
(B = suP A(g, p))
j
DyDDii Dm
Ball
n (Eg((,(R(T) Co (R(T)))))
E
E
E
Ty~Diii u1
14

---

Generalization Bounds via Meta-Lcarned Model Representations: PAC-Bayes and Sample Compression Hypernetworks
Similarly to Theorem B.I, choose r m
maxjeJ J and we have
n Exg (R(T) w)) (2(T),00)
E
E
TimDii
TY
(m U1 (2r (R(3,W))) (mmm).
E Www
Th-Dil Tj-D=-Ul
The most common comparator functions, namely the quadratic loss A2(4,2) = 2( p)². Catoni's distance Ac p) - In(1 (1 -e )p) - Cqq and the linear distance Ax(g.p) = A(q - p) are all bounded, with the exception of the kl. Thus, we have p. A2(g.p) p) = 2, sup n.reoo01 Ac p) = C and sup, pe 4x = A(b a).
C. Corollaries of Theorem B.1 and Theorem B.2
With Theorem B.1 and A kl, we recover real-valued version of Theorem 4 of Laviolette & Marchand (2005). Corollary C.1. In the setting of Theorem B.1. with (qq. p) = kl(g, p) and S = Sz. with probability at least 1 over the draw of S D we have
SQ over J XΩ:
KL(Q]IP) + In (Bjw) 20 [j
Cs, (R)S),W)), E fo (8(S).W))
kl E (j.)nQ
(ja)
maxjeJ li]
We can relax this corollary to obtain a bound that has Theorem of Thiemann et al. (2017) as a special case where we choose J == [j [i] r for 0.
Corollary C.2. the setting of Theorem B.I, with S = Sz. with probability at least 5 over the draw of ~ D',, we have
AQ over J x E (0,2):
Eg w)) < B Lo w)) KI(QQIPP) + In (1 Be 2/m [j] (w)r
E
A(1 ²m maxjeJ (i])
We can also recover tighter bound than Theorem 39 of Germain et al. (2015). Instead of bounding the complement loss, they bound the training loss the whole dataset, thus can use Theorem B.2. Although this could theoretically lead to tighter bounds, later in the section we present a toy experiment that shows that in practice, it rarely is tighter.
Corollary C.3. In the setting of Theorem B.2, with A A(g,)) 2(q p)2, with probability at least over the draw
S ~ DD we have
VQ over J x Ω2:
KL(Q|P) + In E(j 2(m 1312
2
Co (R) S E (j.)
Es (R)
2(m maxjej [j])
Corollary C.3 expresses tighter and more general bound than the results of Germain al. (2015), Moreover, explained below, the latter is not always valid.
Identifying a small error in previous work of Germain et al. (2015). Although the sample compression result of Germain et al. (2015) is stated for any compression sets of size at most X, only the case for compression set sizes were considered by the authors. Indeed, the proof of Lemma 38, with 0, when bounding A's (m), they consider the term
E ( Sy~DA S
E
E
(8)
15

---

Generalization Bounds via Meta-Learned Model Representations: PAC-Bayes and Sample Compression Hypernetworks
By the definition Sj = ( my Jej. have that |Syl [j]. Thus, Equation (8) only makes sense when À [j]. Moreover, later on, the decomposition of the loss
()) = m
A Ass (R(S), + (m - A) (R)(((S))
only makes sense when lil = X. Indeed, we have
1 m
(R(S))) =
(((()).)((:):.1)
m
Σ
(())))
Σ
((R w) (axe)
m
(mi:De)ES)
Σ
[(R(S), ((x)), m
Σ
((R(Sj, w) (ac;), yt)
m
X
(an (a)
X Ls, (R((S) W)) + (m 2) (R(S))(()))
m
If X * [j]. then Ls, (R(S) w) *
Σ (R)(S).w)a::)) v.) and (R) # m-X
Σ
((R(S) (x;)), vi).
The result was used correctly in Germain et al. (2015), as they only considered this setting. However, the statement of the theorem was slightly incorrect.
In this specific setting, we can easily show that the log term of Corollary C.3 is upper bounded by the log term in Theorem 39 of Germain et al. (2015):
e
mmm
13
2 m
S
1
2
2
m -
8
1
lill
2 pa--ii (j).
Empirical comparison of the bounds. We now compare the bound on Es instead of Σsy. To do so, compute the value of Corollary C.3 and relaxed version of Corollary C.I using Pinsker's inequality. We choose m 10000, KT[(QII)) 100, 8 = 0.01, Es, (h) = and such that maxjeJ [j] = 2000. this setting, we can investigate the relationship between the compression size and the validation loss Lsy (h). In Figure 8(a), we report the difference between Corollary C.3 and the relaxed version of Corollary C.I.
m It is obvious that in this setting, the exponential term exp( ()(m(m(m)))))) -i)) of Corollary C.3 is very penalizing. We can that the difference becomes smaller when the validation loss becomes larger. This can be explained by the fact that the loss (g) m- m- til (h)(h) decreases when [j] becomes larger. However, doesn't 't come close to being advantageous. Indeed, seems like Corollary C.3 only becomes advantageous when the KL is very large. In Figure 8(b), we chose [L[ = 10000. We then observe that for Esp (h) larger than 0.6, Corollary C.3 is actually smaller. However, the advantage doesn't 't seem good enough to use this bound in any setting, as the advantage is only available in degenerate cases when the loss on the dataset is very high and the KL is also very large.
m
16

---

Generalization Bounds via Meta-Learned Model Representations: PAC-Bayes and Sample Compression Hypernetworks
30
330
60
03
439
650
0009
859
890
050
250
0253
1350
200
1200
255
1450
0025
335
1350
100
2003
(a) is small compared to the MGF.
(b) is large compared to MGF.
Figure 8: Behavior of the gap between Corollary C.3 and the relaxed version of Corollary C.I, when the KT, is (a) small (b) large
compared the moment generating function (MGF) term. A positive value means Corollary C.3 looser.
D. Proof and Corollaries of Theorem 2.4
Using Theorem B. we can obtain new sample compression bound for real-valued messages. To do so, we restrict the result to use only Dirac measures posterior distributions for the compression sets.
Theorem 2.4 (PAC-Bayes Sample compression real-valued losses with continuous messages), For any distribution D over X x y. for any set J S Pmm), for any distribution Pj over J, for any prior distribution Pn over Q, for any reconstruction function R, for any loss : y x y > [0, 1), for any convex function 1] x [0, 1] - and for any 8 E (0, 1), with probability at least 1
over the draw of S ~ D we have
Vj E J, Qn over Q
AA (m)
E @a
Σs, ()) wnla
E Lo (R()).W))
log (j(
+ KL(Qol)Pp) +In
maxjeJ ji
8
with
(m (0---DAA((y(a(cc,,).c.ovoo0,,,,
Am(m)=
E Py Dy UI
E
Proof. We restrict the posterior distributions to be Dirac measures, e.g. for any vector j", the posterior distribution is Q("") and Q(j) ovj j³. We also separate the KL in two terms.
Q(h) P(h)
KL(QIIP)
log
h~Q
@(.w)
E log
(
w(j.)
log Qú.w)
E
E
j~Qu
wwQn
w(j.)
E log Q)())
E
j~Qu W>Qa
(a())
17

---

Generalization Bounds via Meta-Learnned Model Representations: PAC-Bayes and Sample Compression Hypernetworks
log Qi(
Py(j) + log @n(w)
E
J~Qq
@o
Pa((w)
log Q5(i)
E log Qa(w) @nQu
E
+ Jo
J~Q
W
(j)
Pa(w)
Q. (o') Q,(i")
Qソ(i)
log Da(w) Pa(w)
+
Σ
(1) log
wnQo
P)(J)
Py(j)
1-Q. un@
Qn(w)
1 1.log Pj(j)
+
Σ 0 0-log Ps(i)
+ E
E log
w>Qn
J~Q w~Qn
Pa(w)
(n(w)
log
E log wnQn
Pj(j')
Pa(w)
log P)(5")
+ KL(Q2ll PP))
we also restrict the posterior distribution on to be Dirac measures, we obtain slightly worse version of Theoree 2.3. Indeed, it restricts the comparator function be convex and it is penalized by the maximum the denominator and the expectation in AA (m)) which weren't present in Theorem 2.3.
The following corollaries are easily derived from Theorem 2.4 by choosing comparator function A and bounding As (m). Corollary D.1. In the setting of Theorem 2.4, with Ac(g,p) In(1 (1 e- C-)))) - (where C 0), with probability al least 1 - 8 over the draw S ~ Dmn, we huve
Vj E J, Qa over Q:
CD(R(S), S -1-11--- 1- [1-exp wrQq
1
(-c
2sg (2((),))))) (I.(Qnl|Pa) - In (P5 8) m maxjeJ ji
>
E
E
wn
Corollary D.2. In the setting of Theorem 2.4, with A(g.p) = kl(g. In + (1 9) In 1 with probability at least 1 - over the draw of S ~ DD we have
Vj E J,Qa Q::
Ej-P, 2 m j Pj(j) 8
kl
E Wn
()(S),,,,
E (D(((S))w)) whQa
KL(Qn||Pa) In
m maxjej [j]
Corollary D.3. In the setting of Theorem 2.4, for any O. with (q..p) = X(p 1 9). with a 52 -uu--uu--Cee Gaussian loss function
{: x + R. with probability at least 1 over the draw of S Dmh for all j and posterior probability distribution Qa we have
E CD(R(S).w)) wn
< IE (s((R()). wwQn
1
(n- 1il)A? }
KL(Qn||Pa) + In + E exp Py(j) joP,
Xm maxjeJ [i]
2
E. Proof of Theorem 2.5
Theorem 2.5 (Disintegrated PAC-Baye Sample compression bound). For any distribution over X x Y.for any set J C P(m). for any prior distribution p, over for any prior distribution Pa over Z, for any reconstruction pression function for any loss { y + [0, for any any a >> 1o any convex function A [0, 1] x [0, + for any ö (0, 1], with probability at least 1 - 8 over the draw of S ~ th (which leads to (Sp., Q C(S, Pa) ). and Q we have
R, for anranyyeaa any com-
any
any
A (Esz. (R(S). w)), Lo (R(S) w))s,ww)))
20x 1
In
2
+ In 8
1 Ps(1*)
+ D. (Pa) +Im1... Am
m maxjej lil a
18

---

Generalization Bounds via Meta-Learrned Model Representations: PAC-Bayes and Sample Compression Hypernetworks
To prove this result, we need the following results from Viallard et al. (2024).
Theorem E.1 (Viallard al. 2024). For any distribution on 2, for any hypothessi set H. for any prior distribution P M (H), for any measurable function Φ H. x + Ryo for any a > L, for any E (0, 11, for any algorithm B T (H) + MMH), we have
P SNDmi
In S)
a
1) 21
2a - 1 2
a In
(2s P)) + In
E E S' Nap (K
21-6; 16
where 2s ((S,P) output by the deterministic algorithm Ç.
of Theorem 2.5. Let = x y. We consider a set of sample-compressed predictors that can be defined using a reconstruction function R, a compression set j and a message w. Following from the PAC-Bayes Sample compression work of Laviolette Marchand (2005), we define the distribution on instead of the hypothesis class; it is equivalent to sample from distribution on the hypothesis class and sample (j* ww*) from distribution on and set h (Sp w
Let apply Theorem E.1 with
((h, S) exp
a -
(m
max ( (Csy (2))),..")), JEJ
a
Then, we have
a
In (n)),
a
Inexp
a
(m - max [sy, (2) (0,)))
JEJ
1
(m max lil) (C. (R(S)+ w*)) (D
a
a
jej
(m max (il) (Esy. (fsg (R(S)), w) )), ( jeJ
Moreover,
ln
E
6(h', S'
5'DDm Kap
In
E Woop Dm
o(', s')
In
E
E
exp
Q
(m
max jEJ
(i]) (35
jr wo Pa S/
a
In
E
E
E
E
exp
a
jej (m max (i) A (CC
j~P, wm Pw Dial 8) Sp
In
E
E
E
exp
(m - max ه (R(S) w)) (12,
jo w Po
Sy Sy
jEJ
In
E
E
E g-
exp (m [j]) A (B))
Jr w Pa D
With these two derivations, we have a disintegrated PAC- PAC-Bayes Sample Compression bound, with a posterior distribution Qs = <(S, P). We need to reframe this to accommodate the fact that we want a single compression set and a message sampled from an uncountable set of messages.
19

---

Generalization Bounds via Meta-L.arrned Model Representations: PAC-Bayes and Sample Compression Hypernetworks
To do so, start by choosing P Py Po and Qs = = Qh- Moreover, we choose ( such that Q3 is always Dirac
distribution such that the only compression with non-zero probability is The Rényi Divergence then becomes:
1
2 P(j. w)
Da(QIIP)=
a
1
1
m
IE
(a(w))
1
(i)
Qa(w)
m
IE
~PP
Py(
Pr(w)
Q2((i
(2(w))
In
E
E
0
WN Po
Jr
Pj(j)
Pa(w))
1
Qa(w)
(Q)
In
E
E
WnPPa
Pr((W)
Jr
P)())
Qn(ww)
[Q(i")
Qi())
In
P)(jn)
+
P)(
a
wm Ptz
Pa(w)
Pj()))
P,(i)
Qn(w)
1
0
E Wo
Ps(j*)
Pr(i)
OF
Pa(w)
PJ(j")
P₂(1)
Qn(w)
1
In
E
Pj(j*)
0
WrrPa
Pa(ww
P)(j")
(2((w)
1-11
In
Pn(w)
P)(j")
1
Qa(w)
1 In
In
E
a
Wrroo
Pa(w)
Pj()")
Qn(w)
1
In
E
a
W.PP
Pi((w]
P((j*)
1
(aal
Pa) + In
P((1))
F. Corollaries of Theorem 2.5
Corollary F.1. In the setting of Theorem 2.5, with probability at least we have
8 over the draw of D j Qr, Qa
kl (Ls, (R(S), ()) LDD (R(S).w))) < maxjes [i]
a- In
2a 2 + In Py(i) + Pa(QallPa) + In E JoP,
2 mm [i]
Corollary F.2. In the setting of Theorem 2.5, with probability at least 8 over the draw of S ~ D Q Qs we have
Co (R(S), < c 1 exp
( (- (-CEs((R(S),))) (
- m - maxjej [i]
2a 2
a -
In +
Pι())
Da (alll()
)
Corollary E33. In the setting of Theorem 2.5, for any X > 0, with probability at least 1 - 8 over the draw of S ~ Dm j~ QJ,w ~ Qsa we have
Co w)) < Esg (R(S
2a 2
(n - 22
In 3
+
+ Da(Qul + +In E exp JwP,
X(m maxjeJ [i])
a-1
2
20

---

Generalization Bounds via Meta-Learrned Model Representations: PAC-Bayes and Sample Compression Hypernetworks
G. Algorithm
The following pseudocode depicts our Sample Compression Hypernetworks approach.
Algorithm 1 Training of Sample Compression Hypernetworks (with messages) architecture.
Inputs: S {S² ) meta-dataset
E N, support set size (1 S < min,(m.).
b E N, the compression set and message size
BackProp, a function doing gradient descent step
v. 11 02 < Initialize parameters
while Stopping criteria is not met do:
for .....;1.. do:
S, + Sample datapoints from S;
j t Co, (S;) such that |j =
Mar such that | =
7 - (S....
loss mi-o
1 Σ (x.)ES |S. (x1,(2)))))
1 Φ1 d2 BackProp(loss)
end for end while
return Ros Co., Mos
H. Numerical Experiment and Implementation Details
The code for all experiments is available at ht :
com/GRAAL Research/DeepRe
Synthetic experiments (moons dataset). We fixed the MLP architecture in the sample compressor, the message compressor, the reconstructor and the DeepSet modules single-hidden layer MLP of size 100 while the predictor also is single-hidden layer MLP of size 5.
We added skip connections and batch norm in both the modules of the meta-learner and the predictor to accelerate the training time. The experiments were conducted using an NVIDIA GeForce RTX 2080 Ti graphic card.
We used the Adam optimizer (Kingma Ba, 2015) and trained for at most 200 epochs, stopping when the validation accuracy did not diminish for 20 epochs. inittaliize the weights of each module using the Kaiming uniform technique (He et al., 2015).
Pixels swap and binary MNIST and CIFAR100 experiments. Let MLP1 be the architecture of the feedforward network in the sample compressor, the message compressor, the encoder, and the reconstructor; MLP; be the architecture of the feedforward network in the DeepSet module; MLP3 the architecture of the downstream predictor. We used the following components and values in our hyperparameter grid:
Learning rate: 1e-3, 1c-4;
MLP;: (200, 200], [500, 500];
MLP2: [100], [200];
MLP3: [100], [200, 200]:
c: 0, 1, 2, 6.
[n], 6: 0, 1, 4, 8, 16, 32, 64, 128.
We added skip connections and batch norm in both the modules of the meta-learner and the predictor to accelerate the training time. The experiments were conducted using an NVIDIA GeForce RTX 2080 Ti graphic card.
We used the Adam optimizer (Kingma & Ba, 2015) and trained for at most 200 epochs, stopping when the validation accuracy did not diminish for 20 epochs. We initializzed the weights of each module using the Kaiming uniform technique (He et al., 2015).
21

---

Generalization Bounds via Meta-L.crrned Model Representations: PAC-Bayes and Sample Compression Hypernetworks
Table Comparison different meta leta-learning methods and generalization bounds on the MNIST and CIFAR100) binary task. The 95% confidence interval is reported for generalization bound and test error, computed over the test tasks.
MNIST
CIFARIO0
Algorithm
Bound (L)
Test crror ())
Bound (L)
eeror error ())
PBH
0.597 0.107 (Thm. 2.1)
0.150 0.114
0.974"1 (Thm. 2.1)
0.295 - 0.103
0.770 :: 0.076 (Thm. 2.5)
0.999 1: 0.001 (Thm. 2.5)
SCH_
0.352 0.187 (Thm. 2.2)
0.278 = 0.076
0.600 + 0. 143 (Thm. 2.3)
0.374 0.118
0.369 + 0.187 (Thm. 2.3)
0.629 + 0.142 (Thm. 2.5)
SCH_.
0.280 + 0.144 (Thm. 2.2)
0.155 + 0.109
0.745 + 0.101 (Thm. 2.2) 0.305 + 0.142
0.295 + 0. 148 (Thm. 2.3)
0.758 + 0.098 (Thm. 2.5)
PB SCH
0.597" 0.107 (Thm. 2.4) 0.150 + 0.114
0.974 0.022 (Thm. 2.4) 0.295 + 0.103
0.770 + 0.076 (Thm. 2.5)
0.999 + 0.001 (Thm. 2.5)
Bound average over the decoder output.
More results on binary MNIST and CIFARIO0 experiments. We present in Figure 9() and Table (Figure 9(b) and Table 7) the contribution of each of the terms impacting the bound value for few algorithms the MNIST 200 pixels swap (binary CIFAR 100) task. In the figures, the cumulative contributions are displayed, while in the tables, the marginal contributions are displayed. The bounds are decomposed as follows:
The observed meta train "error";
The "confidence penalty", which corresponds to the term - In 0 in Theorem 2.1 and the corresponding term in other bounds;
The "complexity term", which corresponds to the KL factor in the PAC-Bayes bounds. The latter further decomposed into the compression set probability and the message probability in sample compression-based bounds.
When considering the decomposition on the 200 pixels swap experiment, we see that our approaches, despite having a larger error term, relies on a small message probability and an empty compression set to yield competitive bounds. In contrast, for Pentina & Lampert (2014), the complexity term profoundly impacts the bound, making it compeetitee. As for the decomposition on the CIFAR 100 experiments, is interesting to see that the bound from Zakerinia al. (2024) and the one from PB SCH have similar decomposition, whereas SCH,, despite being penalized by the message probability, relies on a better treatment of its error and confidence term to obtain best bound of the four considered algorithms. This is empirical evidence of the tightness of our bounds compared to those of the runner-ups, all factors (error, confidence O....) being kept equal, thanks to the non-linear comparator function A (see Theorem 2.1).
Label shufile experiment. As suggested by one ICML reviewer, we performed an additional experiment, based on the one in Amit & Meir (2018) (as well as Zakerinia et al. (2024)). The label shuffle experiment goes as follows: we start with the MNIST multiclass dataset, and we create each new task by performing random permutations of the label space. There 30 training tasks of 1000 examples, and evaluated the methods on 10 tasks of 100 samples. Table 8 presents the obtained results. We witness that, despite an extensive grid search over hyperparameters, the PB SCH approach fails to learn to generalize to the test tasks. We empirically observed severe overfitting on meta- meta-train tasks. We hypothesize that this is due to the See architecture, which might not be powerful enough to encode the subtleties of the tasks at hand.
22

---

Generalization Bounds via Meta-Learnned Model Representations: PAC-Bayes and Sample Compression Hypernetworks
Generalization bounds decomposition 200 pixels swap
Generalization bounds decompesition binary CIFAR100
Message
Complesity
Message prob.
Eror
Complexity
Confiée ice peniliy
Comp, set prab.
Conhdence penalty
Comp. set prob.
0.25
10
0.20
Pere UN
06
0.00
00
Lampert
Lampart
SCII+
Aigeekhm
Algurithm
(a) MNIST 200 pixels swap task
(b) Binary CIFAR100 task
Figure 9; Bound values cumulative decomposition for few algorithms.
Table 6: Bound value decomposition for a few algorithms on the 200 pixels swap task.
Algorithm
Error
Confidence penalty
Complexity
Total
(Pentina & Lampert, 2014)
0.028 0.002
0.085 + 0.000
0.127 + 0.028
0.240 0.030
(Zakerinia al., 2024)
0.042 0.198
0.045 + 0.000
0.021 +: 0.160
0.108 0.037
Error
Confidence penalty
Message prob. Comp. set prob.
Total
SCH,, PB SCH
0.073 0.017
0.015 + 0.002
0.003 + 0.001
0.000 0.000
0.091 0.022
0.077 +: 0.016
0.030 + 0.001
0.005 + 0.005
0.000 0.000
0.1 0.021
Table 7: Bound value decomposition for a few algorithms on the binary CIFARI00 task.
Algorithm
Error
Confidence penalty
Complexity
Total
(Pentina & Lampert, 2014)
0.485 + 0.068
0.270 + 0.000
0.046 + 0.069
0.801 0.001
(Zakerinia al., 2024)
0.283 0.120
0.133 + 0.000
0.537 1 0.195
0.953 0.315
Errr
Confidence penalty
Message prob. Comp. set prob.
Total
SCH,
0.264 0.133
0.078 0.010
0.374 + 0.017 0.027 0.003
0.745 0.101
PB SCH
0.298 + 0.098
0.155 + 0.008
0.521 + 0.045
0,000 0.000
0.974 = 0.022
Table 8: Comparison of different meta-learning methods on the MNIST label shuffle binary task. The 95% confidence interval is reported for generalization bound and test error, computed over 10 test tasks. The best (smallest) result in each column is bolded.
MNIST label shuffle
Algorithm
Bound (J)
Test error ())
(Pentina & Lampert, 2014)
2.376 + 0.001
0.900 + 0.589
(Amit & Meir, 2018)
0.542 + 0.034
0.023 + 0.062
(Guan Lu, 2022)
3.199 0.372
0.023 + 0.006
(Guan & Lu, 2022) Catoni
0.536 + 0.063
0.030 = 0.001
(Rezazadeh, 2022)
12.95 0.001
0.902 + 0.660
(Zakerinia et al., 2024)
3.779 + 0.079
0.165 + 0.023
SCH
0.997* 0.005 0.792 + 0.070
"Bound on average over the decoder output.
23


Reviews:
[{"review_id": "4SWWxIcMUi", "reviewer": "Reviewer_sASN", "summary": "The paper provides novel PAC-Bayesian bounds for meta-learning within the sample compression framework. The approach is based on the hypernetwork architecture. The paper also provides an experiment to show that the proposed bounds can be tighter than prior works. The key technical innovation is extending the sample compression bound (Bazinet et al., 2024) into a setting with real-valued messages.\n\n### update after rebuttal\nI am maintaining the current score  following the rebuttal.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for his careful reading of the paper.\n\n**1. Other Strengths And Weaknesses**\n\n**1.1.** Concerning the complexity of the proposed framework, the encoder-decoder architectures are central to our contributions; each component has its unique role in the whole. We are open to performing new experiments if the reviewer has a suggestion on simplifications. That said, we suggest extending the current Appendix G, accompanying Figures 7 to 9 with a comprehensive description and motivation of every choice we made concerning the encoder-decoder architecture.\n\n**1.2.** Concerning the mixed empirical performances, we report empirical evaluation in unfavorable (Table 1) and favorable (Table 2) environments to investigate a new family of methods honestly. Nevertheless, we agree that adding more experiments could reinforce the encouraging performances on the meta-learning binary variants of MNIST and CIFAR100.\n\nThat is why we crafted new heatmaps (see https://imgur.com/a/r45Wq56) depicting the test error and generalization bound for PB SCH as a function of both the compression set size and the message size (Recall that Tables 1 and 2 report the performances of the models obtaining the best validation error). These detailed results help in grasping the inner workings of our proposed approach. They depict that using a large message is better-suited for minimizing the test error, but a trade-off between the compression set size and the message size is required to obtain the best bounds. Interestingly, when the message size is restricted to be small, we clearly see the benefit of using $c>0$.\n\n**2. Other Comments Or Suggestions** \n\nMany thanks for pointing out the typos and ambiguities. We will give an example of “message” in Section 2.2 and explain our bounds compared to the ones from the literature in the appendix.\n\n**3. Questions For Authors**\n\n**3.1.** Concerning the choice of a prior distribution over the compression set and the (discrete) message, one can think of using a prior that gives more importance to smaller compression sets and shorter messages. In our current approach, these values are hyperparameters that are fixed, but as discussed in 1.2, the elaboration of an algorithm that selects these quantities as parameters would benefit from such priors. These are interesting options that we will mention as future research directions.\n\n**3.2.** In our tables, the bolded values correspond to the smallest bound values, not those with the smallest gaps.", "claims_and_evidence": "The claims made in the submission are well supported.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "The theorems in the main text look correct to me.", "experimental_designs_or_analyses": "Yes, the experiment setup looks correct to me.", "relation_to_broader_scientific_literature": "The key contribution (Theorem 2.4) extends the prior bound for sample compression (Bazinet et al., 2024) to the setting where messages are real-valued.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "1. The hypernetwork framework is rather complicated. It would be helpful if the authors considered simpler alternative frameworks and included a discussion explaining why each component is important to their approach.\n\n2. The experimental results show mixed performance - good on CIFAR but not ideal on the MNIST pixel swap task. Including more experiments would be more convincing in demonstrating that the proposed method works effectively across different scenarios.", "other_comments_or_suggestions": "1. A typo on line 53 'a'\n2. It would be nice to provide real-world examples of \"message\" in the preliminary section.\n3. Line 223, what is $\\mu$, in the equation (5) ?\n4. For the computed bounds, it would be helpful to include a short description that explains how much better the bounds are compared to prior work, since the bounds are rather complicated and it is not easy to interpret the results.", "questions_for_authors": "1. The bound computation on page 5 is for a uniform distribution on J and the message. The choice is quite simple but seems arbitrary. What kind of distribution would lead to a better bound compared to a uniform one?\n\n2. Regarding Table 1, the best results are bolded. For the bound column, is the bolded value the one with the smallest gap with the true test error?", "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": "PQBGpQKBpo", "reviewer": "Reviewer_5RkH", "summary": "The paper introduces new generalization bounds combining both PAC-Bayes and sample compression framework, and apply it in a meta-learning scheme. They introduce three different designs inspired by different theorems by using hypernetworks.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for his careful reading of the paper.\n\n**1. Claims And Evidence**\n\nThe reviewer correctly says that “the generalization bounds proved in this paper are not meta-learning generalization bounds.” Instead, our framework shows a new way of using generalization bounds in a meta-learning framework. We will clarify this further to avoid misconceptions, especially in the Related Works part of the introduction.\n\n**2. Experimental Designs Or Analyses:**\n\n**2.1.** Concerning the comparison with the benchmarks: for our algorithms, we naturally used the support set for the computation of the bound, and the query set for the computation of the test error. Though the benchmarks do not require support/query splits, it is necessary to compute the bound and the test error on independent sets to ensure the reliability of the results. Since the query/support split is done in a random 50/50 fashion for our approaches, we split similarly the datasets for the benchmarks to compute the bound and the test error.\n\n**2.2** Concerning the labels shuffle experiment, we agree it would be an interesting use case for our algorithms and will add this experiment to the revised version of our manuscript.\n\n**2.3** Concerning PB SCH and  $c > 0$: we produce new results (see: https://imgur.com/a/r45Wq56) depicting the test error and generalization bound for PB SCH as a function of both the compression set size and the message size. We see that the message is better-suited for the minimization of the test error, but a trade-off between the compression set size and the message size is required to obtain the best bounds (In Table 1 and 2, we used the validation error to select the compression set size and message size). Interestingly, when we enforce a small message size, the benefit of using $c>0$ becomes apparent.\n\n**2.4** We also present the contribution of each of the terms in the bound to the bound value for a few algorithms on the 200 pixels swap (see here: https://imgur.com/a/9d4fOvB) and on the CIFAR100 binary task (see here: https://imgur.com/a/GSyoggu). In the figures, the cumulative contributions are displayed, while in the tables, the marginal contributions are displayed. The bounds are decomposed as follows: \n- The observed meta train “error” \n- The “confidence penalty”, which corresponds to the term $-\\ln(\\delta)$ in Theorem 2.1 and the similar terms in other bounds\n- The “complexity term”, which corresponds to the KL factor in the PAC-Bayes bounds. The latter is further decomposed into the compression set probability and the message probability in our sample compression-based bounds.\n\nWhen considering the decomposition on the 200 pixels swap experiment, we see that our approach, despite having a larger error term, relies on a small message probability and a null compression set probability to yield competitive bounds. In contrast, for Pentina & Lampert, the complexity term profoundly impacts the bound, making it non-competitive. As for the decomposition on the CIFAR100 experiments, it is interesting to see that the bound from Zakerinia et al. and the one from PB SCH have a similar decomposition, whereas SCH$_+$, despite being penalized by the message probability, relies on a better treatment of its error and confidence term to obtain best bound of the four considered algorithms. This is empirical evidence of the tightness of our bounds compared to those of the runner-ups, all factors (error, confidence $\\delta$, …) being kept equal, thanks to the non-linear comparator function $\\Delta$ (see Theorem 2.1).\n\n**3. Essential References Not Discussed** \n\nWe agree that discussing and conceptually comparing prior work on hypernetworks will enrich the paper. We thank the reviewers for the references from the federated learning literature. They are great examples of the benefits of meta-learned representations and hypernetworks. On a similar note, kindly point toward “Rebuttal KTTB, points 2. and 6.” where the differences between our approaches and model compression approaches.\n\n**4. Questions For Authors** \n\nConcerning the large bound values, many bounds mathematical expressions can give values greater than one. This is especially true when the bound is linear, i.e., of the form “true error $\\leq$ empirical error + complexity term” (which is the case for many benchmarks) since the complexity term is usually not upper-bounded. The calculated bound values for Amit & Meir (2018) in Table 2 are truly around 1000, for the complexity term here is too important. We point to the fact that all of our bounds enjoy being bounded in the interval [0,1], so that no vacuous (trivial, >1) bound can be outputted.", "claims_and_evidence": "Technically, the generalization bounds proved in this paper are not meta-learning generalization bounds. Meta-learning bounds, usually are applied in the Baxter's setting during the meta-learning *training* phase based on the training task, to guarantee the performance of the future test tasks. The bounds provided here however, assume that the training phase is over and the hypernetworks are learned from previous tasks, and provide a bound on the generalization gap for the test tasks. I think this should be made clear in the paper, in discussion to related works. Other than this, the paper is clear.", "methods_and_evaluation_criteria": "The provided theorem and the methods derived from them are interesting, and the addition of the sample compression for a meta-learning setting is novel. In general the experiments are done based on standard benchmarks as in prior works, and the results are good. However, I have the following questions/concerns. See Below.", "theoretical_claims": "I skimmed the proofs and they seem correct, however I didn't check them in full detail.", "experimental_designs_or_analyses": "- As mentioned above, the prior works provide a meta-learning bound in the training phase, and this work is a transfer bound. How did you do the comparison of the tables? Are they all test time bounds? And yes, can you clarify how did you compute the bounds for the baselines?\n\n- Amit & Meir, 2018 had another experiments based on MNIST in which they shuffle the labels instead of pixels. That experiment can be interesting, since I assume sample compression would need at least 10 samples. It is interesting to see if it is possible to get good result with less than 10 samples by using the message.\n\n- The new bound proved in the paper is about PB SCH, however, in the experiments, it has $c=0$ and it is reduced to PB setting. Is it because additional samples doesn't improve? Can you come up with a setting, which $c>0$ helps?", "relation_to_broader_scientific_literature": "Prior works focus on the generalization gap in the meta-learning setting, however the focus of this paper is improving the generalization gap for a given task, after the meta-learning training. Hypernetworks were also used in the prior works for meta-learning, but the addition of sample compression is novel and an  interesting idea for gain improvement.", "essential_references_not_discussed": "The paper uses hypernetworks, however does not have any citations related to it or any prior works who use hypernetworks. The following papers are some relevant references which probably should be discussed. The first paper is the paper that introduces the hypernetworks, and the other three use hypernetworks for personalized federated learning, in a meta-learning scheme, which I think are relevant. The use of hypernetwork is similar to the current paper, and a discussion and comparison is needed.\n\n- Ha, D., Dai, A. M., and Le, Q. V. HyperNetworks. ICLR, 2017. \n\n- Shamsian, A., Navon, A., Fetaya, E., and Chechik, G. Personalized Federated Learning using Hypernetworks. ICML, 2021.\n\n- Scott, J., Zakerinia, H., and Lampert, C. H. PeFLL: Personalized Federated Learning by Learning to Learn. ICLR, 2024.\n\n- Amosy, O., Eyal, G., and Chechik, G. Late to the party? On-demand unlabeled personalized federated learning. WACV, 2024.", "other_strengths_and_weaknesses": "_", "other_comments_or_suggestions": "- I think the pixel swap experiments when there are less samples per task for training tasks and/or test tasks is more interesting. I assume Opaque encoder does not work in this setting.", "questions_for_authors": "- Why are some bounds in table 2 bigger than 1? especially, there is a 1372 in the table. Is this correct?", "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": "fBlen5hx7v", "reviewer": "Reviewer_XmYZ", "summary": "This paper proposes  a novel meta-learning framework that uses PAC-Bayes and Sample compression theory to learn the hypernetwork parameters.  The hypernetwork consists of two components: an encoder (or compressor) that maps the training set into the latent representation space, and a decoder (or reconstructor) the maps the latent representation into the parameter of downstream predictor. A new PAC-Bayes sample compression bound as well as it disintegrated variant are provided to guarantee the low generalization error of the posterior over the latent representation space. Experiments are also conducted to validate the effectiveness of proposed method.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for his feedback, which will help us highlight the precise nature of our contribution. We undertake to add these clarifications to the manuscript.\n\n**1. First concern (the theoretical results are not novel enough)**\n\n**1.1.** We agree that our theoretical results are moderately novel, and we respectfully suggest that our work should not be judged on this basis. Our main contributions are not new PAC-Bayesian and sample compression generalization bounds or advanced proof techniques. Instead, we propose an original way to leverage existing results in a meta-learning framework. We are the first to apply PAC-Bayesian and sample compression to hypernetworks. With this in mind, we undertake to present various kinds of generalization bounds in a unified setting, advancing the idea that each bound can inspire a particular hypernetwork architecture. To our knowledge, this unconventional perspective is fresh, and we argue that it deserves to be shared with the machine learning community.\n\n**1.2.** Hence: “What is the main technical difficulty of [...] to obtain new bound in Theorem 2.4?” There is no technical difficulty here for those being familiar with the usual PAC-Bayes and sample compress proof schemes; our result is indeed based on existing ones. The interest in our results does not lie in their complexity. In the proof of Theorem B.1 and Theorem B.2, we unify and generalize the proof techniques of previous results. Doing so, we present Theorem B.1, which recovers a version of the theorem of Laviolette & Marchand (2005) for real-valued losses and a version of the theorem of Thiemann et al. (2017) for different sizes of compression sets. Theorem B.2 is a tighter version of previous works and a correct version of Theorem 39 of Germain et al. (2015). Indeed, as pointed out in lines 809-839, their proof was only correct for one size of compression set. \n\nFinally, Theorem 2.4 is a direct consequence of Theorem B.1. The idea of using a Dirac distribution to obtain “sample-compression” style bounds is not novel, as it was explored in Marchand & Laviolette (2005). Nevertheless, mixing probabilistic messages and deterministic compression sets is entirely new and follows our peculiar way of looking at generalization bounds to inspire original hypernetworks. This enables us to use real-valued messages instead of binary messages, which is pivotal to optimizing the parameters of the PB SCH architecture bounds with respect to the message in a continuous way.\n\n**2. Second concern (the experimental results are not convincing)**\n\n**2.1.** We rigorously reported the empirical evaluation in both unfavorable (Table 1) and favorable (Table 2) environments. On the binary MNIST task, our methods compare very favorably to others. On the CIFAR100 task, our method achieves the best bound by a reasonable margin.\n\n**2.2.** The reviewer asks “how to demonstrate the posterior and the prior is similar?” To better illustrate our claim, we computed the prior-posterior KL term of both Pentina & Lampert (2014) and Zakerinia et al. for a few tasks (see https://imgur.com/a/tcIJlNZ). This shows that the KL values are lower for a small amount of pixel swap and larger for the binary MNIST task.\n\n**2.3.** As to “why the test bounds in Table 1 are smaller than the test bound of benchmark methods”, it partly relies on the fact that our bounds are based on the $kl(q,p)$ comparator function (see Eq. 1) instead of being linear as in Pentina (2014). Also, a small compression set and message are selected; thus, only a small complexity term enters the computation of the bound.\n\n**2.4.** Concerning the performances of PB SCH, we study in a new figure (see https://imgur.com/a/r45Wq56) the test error and generalization bound for PB SCH as a function of both the compression set size and the message size. See “Rebuttal to Reviewer 5RkH, 2.3” for a discussion of these results.\n\n**3. “Theorems 2.1-2.3 are existing results [... and] can be deferred to the supplementary material.”**\n\nWe thank the reviewer for the suggestion. We will move these parts to the appendix and use the freed space to clarify the abovementioned points.\n\n**4. “In the experimental setting, each training task including 2000 images [...] of these 2000 images?”**\n\nThis is right: half the images (the support set) are used to generate the predictor, while the other half (the query set) is used to compute the meta train loss. However, a new random support/query split is performed at each epoch for every train dataset.\n\n**5. “Some crucial explanations should be added to make the whole proof clearer and more readable. For example, in line 1069, why [...].”**\n\nOn Line 1069, the expectation is on discrete distributions  $P_J$, and $Q_J$, the latter being a Dirac on $\\mathbf{j}$ such that $Q(\\mathbf{j})=1$, explaining the equality. We will add this clarification and comment on the many other steps of the proof.", "claims_and_evidence": "Weaknesses:\n\n**(1) My first major concern is that, the theorectical results are not novel enough.** Two reasons are as follow:\n\n(i) Theorems 2.1-2.3 are the existing results. Although authors may place Theorems 2.1-2.3 in the main body for the completeness of the whole work, some of them in my opinion can be deferred to the supplementary material (e.g. Theorem 2.2. can be somewhat regarded as a special result of Theorem 2.3 and did not be used very few times in the main body, hence can be deferred to the appendix).\n\n(ii) The proof technique is not new. The proof for the disintegrated bound in Theorem 2.5 is actually a direct extension of Theorem E.1 by Viallard et al. 2024. The proof technique (i.e. the use of change of measure lemma, the Markov's inequality, as well as the bounding of moment generating function of the comparator function $\\Delta$) of Theorems B.1 and  B.2 (i.e. of Theorem 2.4) is basic, and the contribution is to integrate PAC-Bayes bound into the sample compression framework, which is not new for me and seems not technical enough.\n\n----\n\n**(2) The second major concern is that, the experimental results in Tables 1-2 of the proposed method are not convincing .**  Several reasons are as follow:\n\n(i) First, in Table 1, the proposed method could not outperform ALL PAC-Bayes meta learning methods in terms of the test error (although the proposed method can achieve the tightest bounds). The explanation for this phenomenon lies in line 380 right column that, \"The benchmark methods perform well because the posterior for each test task, is similar to the prior.\" As far as I know, the posterior for test tasks in the benchmark methods (like (pentina 2014 icml)) is outputed by running the PAC-Bayes algorithm that takes prior (sampled from the informative hyper-posterior) and the training data as input. Then, how to demonstrate the posterior and the prior is similar? If they are similar, then the KL-divergence between them will be small and the PAC-Bayes bound (of benchmark method) is small, then why the test bounds of the proposed method in Table 1 is smaller than the test bound of benchmark method?\n\n(ii) In Table 1 and CIFAR100 of Table 2, the performance PBH and PB SCH is worse than the propoesd SCH _ and SCH +. And even worse is that, PBH and PB SCH could not outperform many benchmark methods in terms of the tightness of test bound the test error. Then it seems that the proposed PAC-Bayes encoder-decoder hypernetworks in Section 3.1 is not good enough. In particular, given that PB SCH is the hybrid version of PBH and SCH but performs much worse than SCH, I am not convinced that the proposed PAC-Bayes encoder-decoder hypernetworks (and it variant PB SCH) works well.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I check the proof as far as I can, and believe it is correct. However, some crucial explanations should be added to make the whole proof clearer and more readable. For example, in line 1069,  why \"${\\mathbb{E}}\\left[\\frac{Q_J(\\mathbf{i})}{P_J(\\mathbf{i})}\\right]^\\alpha=P_J(\\mathbf{j})\\left[\\frac{1}{P_J(\\mathbf{j})}\\right]^\\alpha$\" holds? Such kind of explanations should be added.", "experimental_designs_or_analyses": "The proposed meta-learning method uses support-query training strategy that needs to split the training dataset into two non-overlapping parts. But according to my experience, the benchmark methods in Table 1 \\&2 (like [PL2014], [AM2018],[GL2022]) uses traditional ERM training strategy, instead of such support-query strategy. Then, in the experimental setting, for example each training task including 2000 images, benckmark methods compute the training loss over 2000 images but the proposed method only compute the training loss over part of these 2000 images?", "relation_to_broader_scientific_literature": "This paper provides a new PAC-Bayes meta-learning framework to analyze the generalization performance of predictor on downstream tasks, which is different from the existing literature that considered the hierarchy of prior and posterior distribution.s", "essential_references_not_discussed": "Yes.", "other_strengths_and_weaknesses": "Strengths:\n\n(1) The new PAC-Bayes sample compression bound in Theorem 2.4 is well-motivated by existing works in Theorems 2.1-2.3.\n\n(2) Experimental results in Table 2 validate the effectivess of the proposed hypernetwork framework.", "other_comments_or_suggestions": "Typos:\n\n(1) line 91: by many (investigators)\n\n(2) line 105: asses->assess\n\n(3) line 122: abbreviation SCM lacks explanation\n\n(4) line 186, right column: $\\mathscr{H}(S') ->\\mathscr{H}_{\\theta}(S') $", "questions_for_authors": "(1) In the experimental setting, for example each training task including 2000 images, benckmark methods compute the training loss over 2000 images but the proposed method (with support-query strategy) only compute the training loss over part of these 2000 images?\n\n(2) What is the main technical difficulty of combining PAC-Bayes bound and sample compression scheme to obtain new bound in Theorem 2.4?", "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": "IVpxTZxA7g", "reviewer": "Reviewer_KTTB", "summary": "--- increased score from 2 to 3 after comment from authors ---\n\nThe authors developed a sample compression version of PAC Bayes generalization bounds, which reduce the number of training data points in standard PAC Bayes bounds into a compressed subset with generalization guarantee. They used a hypernetwork to meta-learn the parameter of another network, which they applied the PAC Bayes bound to. The authors explore three different hypernetwork architectures. Specifically, the authors design the sample compression hypernetwork to encode both samples and messages and decode the parameters of a downstream predictor. For hybrid networks, the message encoder is replaced by a PAC Bayes encoder. They evaluate their method over synthetic tasks and image tasks like MNIST variants and CIFAR100. The proposed bounds and training procedure lead to a tighter bound compared to a couple of baselines.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for his insightful feedback. \n\n**1.** “People are applying bounds on models like 100M~7B parameters.”\n\nIndeed, interesting works have successfully computed tight generalization bounds for large models. It does not undermine the need for tighter generalization bounds for smaller models, as they are still used for many applications. Moreover, the submitted manuscript focuses on investigating a new way of obtaining bounds in meta-learning, which we conceive as a stepping stone for undertaking larger experiments.\n\n**2.** “Missing literature review on PAC Bayes for LLMs”\n\nFollowing the reviewer's comments, we will include a literature review of PAC-Bayes for LLMs in Section 2.1 and mention these two works: “Unlocking Tokens as Data Points for Generalization Bounds on Larger Language Models” and “Non-Vacuous Generalization Bounds for Large Langage Models”.\n\n**3.** “The proposed subspace compression is similar to the hypernetwork idea [ in SubLoRA (https://arxiv.org/abs/2312.17173) ].”\n\nWe would like to emphasize the following differences between SubLoRA and our approach: the representation in SubLoRA (and in LoRA) is learned via SGD and is composed of tunable parameters. In our case, though the representation is a function of tunable parameters, it mostly depends on the input dataset. The task is not to encode the weights of a model working well on a single task but to ensure the versatility of the representation for any related task. The way the representation is treated is also quite different: in our case, it is fed to a hypernetwork whose output is the weights of the downstream predictor. (See also **6.** for a conceptual difference.) \n\n**4.** “Empirical results in Tables 1 and 2 are a bit weak. Some of the bound values are higher than the strawman baseline.”\n\nWe report empirical evaluation in both unfavorable (Table 1) and favorable (Table 2) environments. Table 1 illustrates that a fixed model can perform well across the tasks in terms of both error and bound. This highlights that the commonly used pixel swap environment does not account for all meta-learning scenarios. See “Rebuttal XmYz, 2.2” for a numerical investigation. \n\nThe strawman bounds are essentially test bounds: they are valid for a single predictor. Since no predictor is learned on the query set, the empirical error is an unbiased test error estimate (close to 0.5 in Table 2). Hence, the gap between the bounds and the test error is small in these cases. In contrast, the train bounds underlying the other methods are valid uniformly for all learnable predictors. The price to obtain train bounds is a larger complexity term that increases the gap. For the CIFAR100 experiment, all training bounds are greater than the one of the baseline, but we achieved the lowest one with our SCH- model.\n\n**5.** “I’m a bit skeptical about why meta-learning the parameters of a downstream predictor is a good idea. Too restrictive for very large models?”\n\nSince our bound relies on the latent representation instead of the complexity of the downstream predictor and decoder, we expect it to be suited for fine-tuning of the last few layers of large models. Also, one could consider a “prior” over the downstream predictor, which would correspond to the random initialization in the LoRA nomenclature, and predict the weights of LoRA-like matrices to modify this “prior”. Finally, note that our bounds hold for any bounded loss function, which is necessary in some settings for bounding models generating sequences of tokens. These are all promising future works that we will mention in our conclusion.\n\n**6.** “How does this meta-learning approach compare to other types of model compression like [...]?”\n\nAlthough both our approach and the aforementioned methods are compression-based, ours is not a model-compression approach. Our primary goal is to compress the dataset into a subset of datapoints and a message, which is a less explored strategy. By creating a bottleneck, we compress the information contained in the dataset and use it to learn a model instead of compressing the model itself. Therefore, to our knowledge, we compared ourselves to the works closest to ours in the field of meta-learning: PAC-Baysian approaches.\n\n**7.** “The paper can benefit from more analysis figures [...].\"\n\nDuring the rebuttal period, we crafted additional figures following the Reviewers' suggestions:\n- We present the contribution of each of the terms in the bound to the bound value for a few algorithms on the 200 pixels swap (see https://imgur.com/a/9d4fOvB) and on the CIFAR100 binary task (see https://imgur.com/a/GSyoggu). See “Rebuttal to Reviewer 5RkH, 2.4” for a discussion on these figures.\n- We depict the test error and generalization bound for PB SCH as a function of both the compression set size and the message size. (see https://imgur.com/a/r45Wq56 and “Rebuttal to Reviewer 5RkH, 2.3” discussion).", "claims_and_evidence": "Looks reasonable to me. There are no signs of extravagant claims.", "methods_and_evaluation_criteria": "The benchmark dataset (MNIST, CIFAR100) is quite standard, though they are a bit small scale. Nowadays people are applying bounds on models like 100M~7B parameters. See https://arxiv.org/abs/2407.18158, https://arxiv.org/abs/2312.17173.", "theoretical_claims": "I’m not an expert on sample compression bounds, but the combinations of PAC Bayes and sample compression bounds look reasonable to me. The KL term and the terms introduced by sample compression are within expectations, though I didn’t verify every details in the derivation.", "experimental_designs_or_analyses": "--- after authors' responses: These are promising avenues for future work indeed. Thank you for answering and I don't expect results on this since it would be beyond the scope of this paper. ---\n\nI’m a bit skeptical about why meta-learning the parameters of a downstream predictor is a good idea. Would this meta-learning be too restrictive for very large models? How does this meta-learning approach compared to other types of model compression like subspace methods https://arxiv.org/abs/1804.08838, quantization https://arxiv.org/abs/2407.18158 etc. Why is the hypernetwork approach potentially better than other approaches listed above. Would be great to motivate this or demonstrate the superiority of this approach empirically.", "relation_to_broader_scientific_literature": "This paper is an extension of a line of works in PAC Bayes bounds. More specifically, the authors combined the KL term in PAC Bayes and the term introduced by sample compression to bound generalization error.", "essential_references_not_discussed": "Missing https://arxiv.org/abs/2407.18158, https://arxiv.org/abs/2312.17173. PAC Bayes bounds on LLMs. The proposed subspace compression via a linear mapping is similar to the hypernetwork idea here.", "other_strengths_and_weaknesses": "Strength:\n- the combination of PAC Bayes and sample compression is novel. The hypernetwork design here is novel.\n- bounds derivation looks reasonable.\n\n--- after authors' responses: Thank you for explaining the differences between these two tables. It makes more sense now. ---\n\nWeakness:\n- insufficient motivation for hypernetworks\n- insufficient empirical demonstration for hypernetworks, though this is a minor point depending on how much compute the authors have. \n- empirical results in Table 1 and 2 are a bit weak. Some of the bound values are higher than the strawman baseline.", "other_comments_or_suggestions": "The paper can benefit from more analysis figures. For example, I would like to know the contribution of each of the terms in the bound to the bound value. Might be interesting to plot it out and visualize which part takes up most of the bound value when summed together.", "questions_for_authors": "as shown above.", "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: This paper proves new PAC Bayes sample compression bounds in a meta-learning setting. The main idea is to extend results in the compression literature which apply to the passing of a single message $\omega$ to the case where a prior and posterior distributions are defined on the messages as well. 

Although reviewer XmYZ complains about the novelty, the reviewer **agrees that the results are sound**. The other reviewers conceed that the proofs techniques are "heavily inspired" from the literature, but are applied in a novel way which deserves to be discussed and included in the conference. 


[1] Marchand, M. & Sokolova, M. Learning with decision lists of data-dependent features. JMLR, 2005.

[2] Bazinet, M., Zantedeschi, V. & Germain, P. Sample compression unleashed: New generalization bounds for real valued losses. AISTATS 2025


[3] Viallard, P., Germain, P., Habrard, A. & Morvant, E. A general framework for the practical disintegration of PAC-Bayesian bounds. Mach. Learn., 2024.
Decision: Accept (poster)