Minimum Description Length and Generalization Guarantees for Representation Learning
Authors: Milad Sefidgaran
Abdellatif Zaidi
Piotr Krasnowski
Venue: NeurIPS 2023 poster (2023)
Keywords: Information Bottleneck
Representation Learning
Generalization Error
Minimum Description Length
TL;DR: We derive the first generalization guarantee for the representation learning in terms of the minimum description length of the representations (latent variables).

Abstract: A major challenge in designing efficient statistical supervised learning algorithms is finding representations that perform well not only on available training samples but also on unseen data. While the study of representation learning has spurred much interest, most existing such approaches are heuristic; and very little is known about theoretical generalization guarantees. For example, the information bottleneck method seeks a good generalization by finding a minimal description of the input that is maximally informative about the label variable, where minimality and informativeness are both measured by Shannon’s mutual information. 

In this paper, we establish a compressibility framework that allows us to derive upper bounds on the generalization error of a representation learning algorithm in terms of the ``Minimum Description Length'' (MDL) of the labels or the latent variables (representations). Rather than the mutual information between the encoder’s input and the representation, which is often believed to reflect the algorithm’s generalization capability in the related literature but in fact, falls short of doing so, our new bounds involve the "multi-letter" relative entropy between the distribution of the representations (or labels) of the training and test sets and a fixed prior. In particular, these new bounds reflect the structure of the encoder and are not vacuous for deterministic algorithms. Our compressibility approach, which is information-theoretic in nature, builds upon that of Blum-Langford for PAC-MDL bounds and introduces two essential ingredients: block-coding and lossy-compression. The latter allows our approach to subsume the so-called geometrical compressibility as a special case. To the best knowledge of the authors, the established generalization bounds are the first of their kind for Information Bottleneck type encoders and representation learning. Finally, we partly exploit the theoretical results by introducing a new data-dependent prior. Numerical simulations illustrate the advantages of well-chosen such priors over classical priors used in IB.

Minimum Description Length and Generalization Guarantees for Representation Learning
Milad Sefidgaran', Abdellatif Zaidi 11, Piotr Krasnowski! 1
Paris Research Center, Huawei Technologies France
Université Gustave Eiffel, France
[milad. sef aegirana,,,, piotr. g. krasnowski Batpwssiiihuuu @huawei. com,
bodellatif. waw.llaii...iidduiiveeeeeee zaidi@umiv-iiffe! fr
Abstract
A major challenge in designing efficient statistical supervised learning algorithms is finding representations that perform well only available training samples but also unseen data. While the study of representation learning has spurred much interest, most existing such approaches are heuristic; and very little known about theoretical generalization guarantees. For example, the information bottleneck method seeks a good generalization by finding a minimal description of the input that maximally informative about the label variable, where minimality and informativeness are both measured by Shannon's 's mutual information.
In this paper, we establish compressibilitty framework that allows us to derive upper bounds the generalization error of representation learning algorithm in of the "Minimum Description Length" (MDL.) of the labels or the latent variables (representations). Rather than the mutual information between the encoder's input and the representation, which is often believed to reflect the algorithm's 's generalization capability in the related litcrature but in fact, falls short of doing so, our new bounds involve the "multi-letter" relative entropy between the distribution of the representations (or labels) of the training and test sets and fixed prior. particular. these new bounds reflect the structure of the encoder and are not vacuous for deterministic algorithms. Our compressibility approach, which is information- theooretc nature, builds upon that of Blum Langford for PAC-MDL bounds and introduces two essential ingredients: block-coding and lossy-cod posy-coomression. The latter allows our approach to subsume the so-called geometrical compressibility special case. To the best knowledge of the authors, the established generalization bounds are the first of their kind for Information Bottleneck type encoders and representation learning. Finally, we partly exploit the thcoretical results by introducing a new data-dependent prior. Numerical simulations illustrate the advantages of well-chosen such priors over classical priors used in IB.
Introduction
key performance indicator of stochastic learning algorithms is their capability to generalize, i.c., perform equally well training and unseen data. However, designing learning algorithms with good generalization guarantees remains a major challenge. A popular approach involves learning an encoder part and a decoder part. The encoder aims at generating a suitable representation of the input (referred as "latent variable") by extracting relevant features from the input data. The decoder aims at optimizing the performance of the learning task for the given training dataset, known as empirical risk minimization (ERM), based only the learned latent variables. This approach is grounded on the idea that performing ERM on the latent variable (instead of the input itself) prevents overfitting.
Information Bottleneck. Several approaches have attempted to formalize the concept of a "good rep- resentation" [SSTIO AFDMI7 VDOV* + 17 DKSV20) Perhaps, the most prominent the information bottleneck (IB) method which was first introduced in (PB00) and then extended in several dircctions SSTTO AFDMI7 AZ19 KTW19 Fis20, RGTS20, KASK22] The IB approach was deemed useful to analyze deep neural networks SZT17 ZEAS20
GP20 Gei21 and guide their training process. For
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

instance, in supervised learning tasks the IB seeks representations that capture "minimum" information about the input data (shoots for good generalization power) while providing "maximum" information about the label (shoots for small empirical risk), where the amounts of captured and provided information are measured using Shannon mutual information. More precisely, denoting by Y the label variable and by X the input data, the IB latent variable U is chosen so to maximize the mutual information ZUU; Y) while minimizing the mutual information I(U; Equivalently, this can be formulated as maximizing the Lagrange cost
T(U: - -BT(U;;)) X);
where 3 > 0 designates Lagrange multiplier. Let (X" ( denote vector, or block, of m independent and identically distributed (i.i.d.) realizations (X; U4). 6= = 1,..., m, of discrete variables (X, U) ~ Px,U- Fix a distribution Pg such _x20= Px,u- Essentially by means of the rate-distortion theoretic covering lemma [CTU6], it is easy to see that one can get suitable description 0 of X using only [(U; X) bits per symbol. Preciscly, generating a codcbook of roughly Im R 2 vectors an U = 1,..., m. all drawn i.i.d. according to Pt. the covering lemma states that for large m there exists least one index j for which the empirical distribution of (Xm.. ú (i] is arbitrary close to Px,u in some suitable sense. That is, the empirical distributions (x* UT) and (xm, 6tt [1]) are close. Hence, an "equivalent" version t7m of t can be described with roughly m mT X) bits. Intuitively, this makes a connection between the mutual information / [U; X) and the concept of Minimal Description Length (MDL) [Ri788 GMP05 when one considers MDL of the latent variables, not that of model parameters [VPV18 ZEAS20, Morcover, it is now relatively well known that there cxists a connection between the generalization crror of a learning model and the MDL of the parameters of that model, see, e.g.. (BEHW87 B018 GRI9). A notable work [B033] has considered MDL of the predicted labels of a super-sample of training and test data.
Critics to IB. The aforemeentioed connections perhups formed belief that [(U; X) is closely related to the generalization performance of representation learning algorithms. This belief, however, is controversial and confticting evidence has been reported (K19) For instance. using the term (U; X) as regularizer has been criticized for four main reasons K V RG19 AG19 DKSV20 i. The few existing upper bounds on the generalization error which involve (among other terms) the mutual information [U; X) reported in [PV18] and the very recent and concurrent work [KD]H23 are not convincing. For example, the bound of [VVI& holds only when the alphabets of the imput and latent spaces are finite; and, in that case, it states that for any 8 >> O, with probability 1 - ō it holds that: gen(S, W) & O log(n)
VI(U;X) + Cg. where gen W) is the generalization error of model W, C3= (144) [2/] is the size of the latent space and n is the size of the training dataset. For reasonable setups, however, the term Cs dominates and their bound becomes vacuous [G119 LLS The bound reported in [DDJH23] suffers similar shortcomings For further details on this, see Appendix [B.2] ii. Experimental evidence shows dependence of the generalization error on the so-called geometrical compression rather than on [U; X) [K19)] Geometrical compression occurs when the latent variables are concentrated around a limited number of clusters. See [K19 Fig. 2] for a visual representation. iil. [U; X) is invariant to bijection; and, as such, does not favor learning algorithmwshppreenuttiins with simple decision boundaries and does not reflect the "structure" or "simplicity"" of the encoder/decodeer. Please refer to [AGT9 Section& 4.3] for a detailed discussion and examples. iv. Finally, for deterministic algorithms [U; X) can take large even infinite values, especially for continuous variables or high-dimensionas data, hence limiting the usefulness of IB [TTVK18] AG19).
MDL/Compressibility. Several works have studied ACDppoiprssiiiility to establish generalization bounds. this context, key is the "Occam's 's razor" principle [LW6 BEHWS7 BL03] which, e.g., for binary classification tasks, states that if the labels of the training data S = 1Z Zn), ). Z; (X;, Yt) predicted by a model W can be described by < n number of bits, then the learned model W has a good generalization performance. There exist three closely related lines of work that use different means to describe the dataset labels: i. The first describes the predicted labels via the hypothesis (parameter models). It includes the works of (BEHW87 AGNZI8 SAM*200 HJT 1 BSE 21 SGRS22 Recently, it was shown in SSGRS22 S7223 that wnlformation-thoreee [McA98] and intrinsic dimension based approaches [SSDE20 also fall into this category. The proof uses so-called "fixed-size" [SGRS22 and "variable-size"
bounds [ XR 17 S720 PAC-Bayes bounds
(SZ23) compressibility frameworks introduced therein. ii The sccond formulates the minimal description of labels as follows: if learning algorithm can predict all labels of the training data S by using only samples from small subset of S, then the learning algorithm guaranteed to generalize well. This second approach was initiated by [LS66 and followed by others including [9 HKS19 BHMZ200 HK21 HKSW20 CK22]. iii. The third, initiated by [BL003. deals directly with the compression of the predicted labels. This approach is shown to be related to the previous two lines, and also to PAC-Bayer and VC--iiennionn-be results. Moreover, it the closest to the problem

---

S
training
W
S training
W
WWWW, Wa)
Y- Y
Y- P
PUIX,W
PyIu,Wa
(a) Single-step prediction model.
(b) Two-step prediction model.
Figure 1: Considered learning frameworks.
of establishing bounds on the generalization error of representation learning algorithms in terms of the compressibility of the latent variables. This approach detailed in Appendix [..1
this work we aim at undcrstanding the thcory of representation learning through a rigorous investigation of the connection between the MDL (or compressibility of the latent variable and the generalization performance of representation learning algorithms.. In doing so, we first study the single-step prediction model of Fig- Ia and, them, we leverage the developed tools study the two-step (encoder-decoder) prediction model of Fig. lb We also examine the claimed relationship hetween MDL and [UU X).
Contributions. Specifically, the main contributions of this work are follows.
For the prediction model of Fig. la inspired by [BL03] we establish an information -heeorette framework that allows us to measure compressibility (MDL) of the predicted labels terms new object which is the KL-divergence of vector of labels and any arbitrary symmetric prior. For proper choice of prior, this new measure reduces to the sample-wise mutual information and hence inherits the associated properties. However, unlike the sample-wise mutual information, can also reflect the structure/simplictty the learning algorithm. Furthermore, by extending the framework to "lossy compressibility" this new measure does not become vacuous when considers continuous variables instead of discrete labels. Moreover, it subsumes geometrical compressibility as a special case.
We also establish both in-expectation and tail generalization bounds terms of this compressibility measure of the predicted labels. In simple case, the in in-expectation bound can be cast into the form
(Deedricieeed Labels)
The tail bound involves similar expression. This generalization bound easily recovers the VC-dimension bound as a special case; and, hence, also shows how the introduced compressibility measure depends the complexity of the hypothesis class.
Our results make connection between the compressibility framework of [BL03] and the functional conditional mutual information (f-CMI) [HRVSG2] HD22),, which itself is an extension of the CMI- framework developed by (SZ20] In particular, this connection shows how the f-CMI framework can be leveraged to study the compressibility of the predicted labels.
For the cncoder-decoder prediction model of Fig. [b] the framework is extended non-trivially to the case in which instead of the compressibility of the predicted labels it is the compressibility of the latent variable which is considered. The results for this prediction model, which are our main results in this paper given in Section are generalization bounds for the representation learning algorithms in terms the complexity the latent variable. The established in-expectation and tail bounds hold for any decoder; and, for the K-class classification task for example, take the form
MDL(Latent Variables) +
2
These bounds appear be the first of their kind for the studied representation learning setup. In part, their utility lies in that: i) they reflect the structure of the encoder class, ii) they do not become vacuous for deterministic encoders with continuous latent space and iii) they can explain the geometrical compressibility phenomenon. Thus, our framework reveals that the "joint" MDL of the latent space is more related the encoder structure, rather than the mutual information XU;
Finally, our results suggest that data-dependent priors can be used place of the dlta--ndeependet prior of the popular variational IB (VIB) method, We conduct experiments that illustrate the advantage brought up by proper choices of dapa-depend priors over VIB.
Our results also open up several future directions discussed in Appendix C.4
3

---

Notation. Random variables, their realizations, and their alphabets are denoted respectively by upper-case letters, lower-case letters, and Calligraphy fonts, e.g,, X, z, and X. Their distributions and expectations are denoted by Px and [[ For ease of presentation, when X' is a discrete set, Px is a probability mass a probability X. We use the notation {x:4)== ym denote a sequence of real or natural numbers. The set .1,................. K J. K E N, is denoted by [ Finally, IR* denotes the set of non- non-negative real numbers. Our results are expressed in terms of information-theorrtiec functions. For two distributions P and Q, the Kullback-Leibler (KL) divergence is defined as DKr (PI()) := [Ep[lo((P/ (P/)) if P & Q, and co otherwise. The mutual information between two random variables X, Y Px,y with marginals Px and Py is defined as T(X;Y)= = D (xx | Px Py). The reader is referred to [CT06 CKT for further information.
fumction. Otherwise, Px
function. collection of n random variables (X1,..., Xn)
is denoted by X
Our results in this paper will be expressed in terms of symmetric conditional priors. The following definition formalizes three types of symmetry.
Definition 1 (Symmetric Priors). For U,V ~ Pu., let (U²m,, v²²) be vectors composed of 2n Li.d. instances (Us, V.) ~ PV.V. i E [2n]. For any permutation æ: [2n]] [2me]. denote U2" = (nt::) Un(2n)) and V22 == (V=(1)...., V=(2n))
(U (.)))....,
Type-I symmetry: Define type-I permutations the set of permutations a: [2m] [2m] having the property that for any e [m]. the sets {x(1), (i + n)} and {i, + n) are equal. The conditional prior Q(U2=(122)) has type-I symmetry if Q(U?"IV?" is invariant arbitrary type-I permutations. This definition first appeared in [Aud04] (called "almost exchangeable prior" therein) and was used for the CMI framework in (GSZ2TV.
Type-Il symmetry: The conditional prior Q(U?2I122)) has type-ll symmetry if QUU?" (V2") is invariant to any arbitrary permutations w: [2m] + [2m].
Type-Ill symmetry: For a random variable P'z (128,y2., the conditional prior ((U/2m122 .Z) has
type-IIl III symmetry if QUU Z) is invariant to any permutation :: [2m]] - [2m]] having the property that V, Vnis) for every [2n]]
Throughout. if the underlying (U2), is clear from the context, for ease of the notation the correspond- ing sets of Type-I and Type-ll priors will be denoted simply as Q; and Qú respectively.
Problem setup. Unless indicated otherwise, we consider the K-class classification sctup. Let Z = YX be some input data taking value over the input space Z x y according to an unknown distribution μr. We call X E X' the features of the data, and Y E 3 its label, where y = [K]. We assume a training dataset = ( ] ~ fr fr =: Ps. composed of n i.i.d. samples 7, = (X,, Vi) of the input data, is available. We denote the features and labels of S by X == X H
8r and Y := Y f respectively. We often
use also a ghost or lest dataset 5' (Z) ..... Z }
Psr. where Z Y)). Similarly, we
denote the features and labels of S by X' == X
and Y == ymm 8on respectively.
2 Generalization bounds in terms of predicted label complexity
In this section, we formulate a compressibility framework that allows us to derive upper bounds on the generalization error of a representation learning algorithm. Our proposed framework can be seen suitable generalization of the framework of Blum and Langford [BL03). in which the generalization encompasses lossy compression of the predicted labels and which exploits block-coding. However, unlike in the original framework based on (compression) game between two agents Alice and Bob (see Appendix B. for details), this work adopts a rate-distortion theoretic perspective.
For case of exposition, the results are presented for classification problems and the 0-1 loss function, but they can be extended trivially any continuous y and bounded loss function. Consider the setup in Fig. [a Let A: 2n - W he a possibly stochastic learning algorithm. That is, for a given S = (Z,..., 7,)) E 2 the algorithm picks a hypothesis or model W A(S) E W. Also, let the induced joint distribution over S x W be denoted as P:sw: and the induced conditional distribution over W given S be denoted as Pw]s- For every input data = (Ir, y) E Z, every choice of hypothesis w e W induces conditional distribution P (MIr, w) on ÿ y: For convenience, we use the following handy notations:
pan v ()) =: I [eem]] Pfix.w (Di (0), plnn FIx.w 1''x'0 w) Leefml Py Pyix. (0) (6 w),
po2n F.x.w (8: 8' xx,x w) -: Lie(n (PE (wr xs, w) Prixx w C6l lalle' ()).

---

The quality of the prediction is measured by the loss function E: Z x W [0. 1] given by
f[z, w) = By Pjxx, w (M),,))) (ump)l
(I)
where stands for the indicator function. The associated empirical and population risks for this loss are defined as L(s, w) # Exe[n] E(zi, w) and ((w) Bz- w)J. respectivcly. Finally, the generalization error is defined as gen(s, 1) == ((w)- [(s, w).
2.1 Compressibility framework
Now, we introduue briefly the joint compression of a block of the predicted labels. Further details can he found in Appendix C.T. Consider m i.i.d. pairs of train and test datasets Sj == (Z,,1..... Zg,nn) and S = (4), 1....... Lj where Zz₁í (X Yj,)) and 2j = (X', (j)) Let S = (Si..... ................................ "i....,,m), Sm), Sth
and W :- (WI...., Wm), where W Pw;1s,- Denote the predicted labels using model W for inputs X3 and X,,, as F,, and 1 for [mi] and E [ni] Moreover, let 37th 2 denote a rearrangement of the elements of (S) SS) in way that makes it indistinguishable whether given sample is from Sy or S/. In the following two subsections, we investigate two such rearrangements of a given (S,S") ) as 3 Then, for the collection """"), each pair (S,, S)) for j E [m]] is rearranged independently and the matrix of all rearrangements is denoted by 3 Finally, given some 32mn, let denote the rearranged versions of (Y (ym y ymmn) and (ymmn y.mmn respectively by 2) and 2)
Our approach is based on studying the compressibility of the rearranged model-predicted labels 2) 2mmm, from an intormmttinnthhoreeee point of view. The rationale is as follows: since the (rearranged) predicted- vector 2 agrees mostly with the true labels 2 on the dataset S then in accordance with "Occam's ' Razor" theorem [LW86] BEHW87 the model W is guaranteed to generalize well if 2) can be described using only a few bits (or nats). We leverage source coding arguments measure the compressibility of 2)2mm In our block-coding rate-distortion theoretic framework, a compression rate R E Rt is said to be achievable if there exists compression codebook of size mit (fixed priori) which covers the space spanned by the model-predicted labels 2) with high probability. That is, if I is achievable then 2mm can be described using R e R+ nats. Formally, R is achievable if there exists a sequence of label books {Dim meN, with Pm == [f[r]. e [mm]] S )22ma, In E N, ý[r] [r],..... .tm [r]) and [r]r] = (0 ................................ 2y [r]) y:2m such that: lm mR and ii there exist sequence {6m) Jmey for which limm- 6m = 0 such that with probability at least (1 - 5m) over the choices of 5m s one can find at least one index e [lm] whose associated $[r] equals 2) 2mm....
As explained further in Appendix C.I.3 this fixed-size compressibility framework, which is suitable to upper bound the expectation of the generalization error, can be extended to variable-size compressibility in way that is similar to [SZ23] in order upper bound the generalization
with high probability. We notice that, in essence, the core idea of the compressibility framework of Blum-Langford, which we recall one-shot counterpart of our approach. As discussed in (SGRS22 (S23), in the one-shot case one deals with the "worst case" scenario; and this results in bounds that involve framework allows us to bound the compression rate H. in terms of simpler new quantity: the relative entropy of the joint conditional P(Ý",, y y' and a (symmetric) conditional prior Q over 5:2n given 22n
in Appendix [B.I] can be seen
combinatorial terms [BL03] In contrast, our information-theete
Our approach to establishing bound on the compressibility of 2)2mn in terms of information-theoree measures starting from the combinatorial approach of [BL03 and by using block-coding essentially consists in suitable combination of the following key proof steps: (i) introduce and use the symmetries of Definition to rearrange ( (ii) generate the codewords using symmetric priors and (tii)
analyze the minimum codebook size needed to "cover" reliably 22amm, cssentially by use of the covering lemma. As shown in [SGRS22 S723 and also proofs, the last ingredients can be merged via the Donsker- Varadhan's 's variational representation lemma. The application of this lemma is reminiscent of Inforration-theoreticc works on the generalization error such RZ166 XR17 S720
2.2 Generalization bounds using type-I symmetric priors
One way to rearrange indistinguishably (S, S') as 32n is as follows: Let J (JI...., Jn) be a vector of i.i.d. Bernoulli(}) random variables J; E {i, + n), ie [m]. For every i [m]. let the random variable J (1,1 + n) be defined such that J = i n if = and J = J; = i n. Also, let the vector J (Jf......JE) J.). For e [n]. we let the random variables 3J, and 3.z de defined as 3J, Z, and
5

---

3. Z₁ Observe that the vector 3 (31...., 32a) is a J-dependent random re-arvangement of the samples of the training and ghost datasets S and 5". Without knowledge of J every element of the vector 3 has equal likelihood to be from S or S" A similar construction was used in the context of the analysis of Rademacher complexity and the CMI of [SZ20]. We use Type-I symmetric priors. block coding and informationnthhoreee covering arguments in order to analyse the space spanned by the random vector 3 This yields the generalization bound stated in the next theorem whose proof is deferred to Appendix E.2
Theorem 1. i. Let Qi be the set of rype-l symmetric conditional priors on (Y, Y') given (Y, Y'). Then, W.sw [gen(S, W)] & /2R/n, with
p82n R E inf Ey DKL X W Q
FIX, (Y, (X, X' = =1 82m (3: (2)
=
where Y, Y .u@an and X', ..W W- Px WIY. Also the mutual information calculated with respect to the joint distribution PJ 33,8 you = Bern(1 3n i P Pgzu $3011x3" V and the latter term
is defined as Ex X.W p0 VIx (83", 83 XX x x)) in which x' X, W ~ P P "WI3"".
ii For any 8 E RR' and any conditional type-I symmetric prior Q on ( Y') given (x, Y. Y Y"), with probability at least (1 5) over choices of S,S' ,W Ps. Ps.w. it holds that
i W) - W) & V 2n
4
DKL
p82n FIx, (8, (X + log(v22n/0)
A couple of remarks are in order. The part of the result of Theorem I can be understood as being some form of the f-CMI of [HRVSG2]] in which the function / represents the predicted labels in fact our result is slightly stronger comparatively, since instead of conditioning
2 as in the f-CMI of [HRVSG2T one here conditions only on y2n. Incidentally, the result also unveils an appealing connection between an extension of the compressibility approach of [BL03 (in this extension one needs to consider Type-I symmettric priors) and CMI and f-CMI (S220 HRVSG21 HID22). However, for type-Il and type-IlI symmetries, used in the coming sections, our framework goes beyond the CMI framework. The type-I priors have been also used in [GSZ21] to establish (fast-rate) tail bounds for the CMI framework. Due to the difference in the considered setups, their results
not directly comparable with ours. We also note that the above result (and some of the results in the rest of the paper) is kept for clarity and can be trivially improved, by i) moving Ey, Y outside the square root, ii) by rewriting E[gen(s, u²) = =1
n Eiefm) [E[gen(2;, w)]. and applying the bound for each [E[gen(2; 2i; w. similar to (BZV20 H RGBTS2[] iii) by extending the results in accordance with e-CMI framework [SZ20] HD22], and iv) establishing tail bound on gen(S, (S, W. by noting that with probability at least (1- L(S', W) > L(W)- v log(1/)) (1/))/(2n) (similar to Theorem
Next, observe that for any Q Ex,x/ Y Q (Ý, Y X', Y, Y') where QY, Y'X,X' is an arbitrary type-I symmetric prior, and by using the Jensen's 's inequality, we have
RHS of ② <ES.ss. Pgr DKr
(P82n x (8",, p' x W) Q.)
(3)
Relation to Mutual Information. A particular choice of the conditional prior Q1 in the RHS of (3) is Q882n for some prior Q defined over V For this special choice, the RHS (3) is given by
Exiixs DKL DKL(PyIxn ( (8IX, (1IX () w -W Pw [ (P (F W)I1)))
where ixis is the empirical distribution of X in the datasct S. Morcover, by choosing Q as the marginal distribution of ý under Py P' .s. it is easy to see that the first term of the sum of the RHS of 4 coincides with ní (x; Y) for that choice, where ((:-)) stands for the "empirical mutual information" as computed from the available samples. Thus, the contrihution of this term to the bound on generalization error does not necessarily vanish as n - oo (unless the empirical mutual information itself is small). In fact, as already observed in GK19, there exist models which generalize well but have non-small mutual- information i(X;; Y). This instantiates that mutual-informaate information type bounds may fall short of cxplaining true generalization capability, an observation which was already made [GK19. The bound on the generalization error of our Theorem ] which is provably tighter (see 33), then possibly remedies this issue.
'The reader may notice the absence of a "disintegrated bound" here, as opposed to the classical single-dra draw PAC Bayes bound [Cat07]. This is due to the choice of the loss function, which includes an expectation term.

---

In what follows we further investigate the relationship of the result of our Theorem I] which is based on -iideiveg,,,,,, to VC-dimension and mutual information type bounds on the generalization error.
Relation to VC-dimension Suppose that the VC-dimension of the hypothesis class is d. Then, using the Sauer-Shelah lemma [Sau72 72 we get that given any X and X' one can have at most (2en/d)² distinct labels. By letting the conditional prior Q1 be a uniform distribution over all such possible predictions, it is easily seen that the KL. divergence term of our Theorem iis upper bounded by d log (2en/d). This means that the result of our Theorem | and possibly improves over the VC-dimension bound.
Structure and "simplicity" of the learning algorithm. Let consider simple example. Suppose that X = [0, 1] = R and let & (0, 1) be parameter. Then, consider the set of deterministic classifiers w as follows: P w (ū]z, w)
if (ø- and æ >> 7) or (O- = 0 and < 7): and Pýjx,w' (ū)zz w) = otherwise. well known that the VC-dimension of this learning class the aforementioned relation to the VC dimension, we obtain that our Theorem yields bound on the generalization error which is O(v (log(nn)//) In particular, it is casy to see that this bound vanishes as n - 3c. This is in sharp contrast with the mutual information term T(X; Y) which does not necessarily vanish for large n. For example, if the pair (X, Y) is such that Y 1 iff X t r* for some 7* (0, 1), and n converges (for large n) to a value which is at least HY) (because then the ratio between RHS and, in this example, I(X;Y) (Y)).
1. Then, by recalling
I(X; 8)
1X;; Y)
The above example indicates that using mutual information as a regularizer for learning algorithms (as the case in IB) may fail to find models that generalize well and have a comparatively simple structure. In fact, using a different approach, it was already observed in [AG19] and [DKSV20] that using the mutual information term
complexity measure does not reflect the "structure" of the learning algorithm and considering it as regularizer might not favor "simple" learning algorithms. This suggests that mutual information regularizer in the IB approach may be replaced by the KL divergence term of the RHS of (3) (when the latent variables are considered instead of predictions) which does reflect the complexity of the encoder's structure. As investigated and shown in Section in addition to favoring encoders of simpler structure, our approach provides theoretical guarantees of the generalization error.
2 Lossy compressiblity
The above approach and results can be extended to any bounded loss function and continuous variables Y and Y (see the next section where continuous latent variables are studied). In the regime of continuous variables, standard result of rate-dista dieeotsttotoonn theory stipulates that any lossless encoding of y and fm may require an infinite number of bits, making the generalization bounds vacuous. This is precisely why Shannon's mutual information fails regularizer in deterministic learning algorithms with continuous alphabet variables. On the other hand, our approach can be easily extended to include the lossy compression of the labels (see Appendix C.1.2 the same spirit as done in [SGRS22) for the hypothesis compression. The following result states a lossy in-expectation bound and lossy tail bound is reported in Appendix A Theorem 2. Let Q₂ be the set of type-I symmetric conditional priors on (Y, Y') given (Y, Y'). Then, for any E R, Es,w' B..wlu [gen(S, W)] is upper bounded by
inf inf Ex x
DKL. Ex x
p02n YIX,W D XXX te,
V
Pwis Q
822 Eps. w Pwis gen (S, W) gen (S, W)] e.
where Y, Y
X' W-
Pxixy: w.Y and the first infinum is over all Pwis satisfying
A proof of this theorem follows by an easy combination of the distortion criterion with the bound on Eg [e,[[S W)] obtained by application of Theorem I to the compressed model W (not W). This simple trick, which is related conceptually to lossy source coding, prevents the KL-divergence term from taking very large (infinite) values for continuous alphabet variables. Moreover, the lossy compressibility also offers interpretation of the geometrical compressibility concept that was observed to be related to the generalization performance in [GK19.
2.3 Generalization bounds using type-Il symmetric priors
In this section, consider another way rearrange indistinguishably (S,S') as 3 which is inspired by BL.3 Let T = (Ti,..., T, he a random set obtained by picking uniformly n indices from (1,..., 2n), without replacement. Note that in contrast to J which had i..d. components, here the components of T
7

---

are dependent. let T {L..... (.......n]]?.... be the complement of T, having the elements T ......., } Now, for each E [m]. let 34, = (7, 7.). We use type-Il symmetric prior to cover such rearranged vectors. To state the result, first we need to define the function
[o. 1] x [o. 1] [0.2]
2] as follows:
hp(r, x') 2/b
+ hb(x)) - ho''',
where (x))) == - (z) (1 - x) 1ogg(1 =.). Note that hD x²) 2//2/ is equal to the -ensennShannon divergence between two binary Bernoulli distributions with parameters æ and x'. The reader is referred to Appendix [A for the relation of this function with the combinatorial term appeared in [BL03). The function hD(ss)) has the following interesting properties, proved in Appendix E.3
Lemma 1. Y (xx = [o. 1] x [0, 1], we have: (i) h x') > (x-x/)² is increasing with respect to x in the range [x', 11, and (iv) hp r/) is conver with respect to both inputs.
x²)²
(i) h 0) > x, (ii) hp(a, x')
Now, we state the main result of this section.
Theorem 3. Let Qis be the set of type-ll symmetrie priors on (L, Y`) given (Y, Y'). Then, n 10.
nhn [Ew[<(W)]] Es, [C(S, [s w)1) &
inf Ey.y, DRL XX W Q=
pooen
X (G, X x w)]l +lgg() = / (T; 22)) log(m),
where Y, Y' ugg and X', X, W P Px Y.
Also the mutual information is calculated with
respect to the joint distribution TT, 82 y
Pruy
82n p
yz 8:2 yT and the latter term is defined
as Ex X.W
V/x,W (222
2 T X, X .W)
in which X', X. W Px Px.W
The proof of Theorem B is deferred to Appendix E.4 Also, a similar tail bound is provided in Appendix A
Using the part (i) of Lemma it can be seen that if the value of the KI. divergence term is larger than log(n) then the bound Theorem Bis tighter than that Theorem [ Also, using part (ii) Lemma it seen that if the error on the training set is zero (a setting referred as "realizable case" in [B033] Thcorem yiclds a bound on the generalization error which is ((1/n).
3 Generalization bounds in terms of latent variable complexity
The generalization bounds of the previous section particularly useful in the following sense: if the learning algorithm is "simple" enough to produce a low "relative entropy" sequence of labels for training and test sets, then the algorithm generalizes well. However, they have downside that they cannot be used directly as they are in the optimization, since minimizing those bounds may result in solutions with large empirical risk. In this section, extend the results of the previous section to settings in which the processing is split into two parts: an encoder part that produces a family of representations that have the property to generalize well (developed according the guidelines of the previous section) and decoder part that seleets among that family one representation that minimizes the empirical risk. As such the goal of the encoder is to guarantee a small generalization error and that of the decoder is to guarantee small empirical risk. This procedure, which is similar to the Information Bottleneck method, aims at finding a good balance between generalizing well to unseen data and minimizing the risk of the training data.
Let W = (We, Wa), where We and Wa are the hypotheses (or models) used by the encoder and the decoder, respectively, as illustrated in Fig. [bb Also, let U denote the output of the encoder, which will be referred hereafter interchangcably as "representation" or "latent variable". The encoder produces the representation U according to the conditional Purjaww. The decoder produces an estimate Y of the true label Y according to the conditional - We consider stochastic learning algorithm A: nn - W which picks model
W (We, Wa) W := We x W. according Pwis- Let a loss function E: Z x W [0, 1] be given. For a model ws (we, wa) the quality the prediction of Y is evaluated as
((z, w) :- Ey-Py x. (f ww (wz :- BUJ-P (1) P
Pye (1 (wer))
Empirical risk, population risk, and generalization error are defined similarly to the previous section. According to the above motivation, we are interested in establishing bound on the generalization error of the algorithm A that depends only on the part We of the model W. In accordance with our compressibility
8

---

framework of Jection[]such bound would then depend on the complexity of the latent variable U. However, here, the encoder part We and the decoder part Wa are both trained using the dataset S. Thus, they may be statistically dependent in general and therefore the "rearrangemen"" ideas using type-I and type-II symmetries do not work here. To elaborate on this a bit more, recall that for example for type-I symmetry, to rearrange (Y, Y) and IY', Y in indistinguishable manner, randomly shuffle the positions of the pairs (Y,, Y and (X (.). If we now consider using the type-I symmetry for the new setup, then shuffling of the pairs (Y; U,. Y4) and (Y/ U,, Y,), changes the dataset S and thus the distributions Pwis and Py P Hence, covering the resulting rearranged sequence would unavoidably depend on both encoder and decoder parts. To overcome this issue, we use type-IlI symmetry, where we leave the train and ghost datasets untouched and randomly "swap" only those latent variables and their corresponding predictions, i.e., (U,, Y;) and (U', Yj), that are associated with the train and ghost samples with the same label, ie., if Y Y The following result is the main theorem of this section and the paper derived using the type-Ill symmetric priors. A formal proof of this result can found in Appendix
Theorem (Generalization Bound for Representation Learning Algorithmss). Consider a K K-classification learning task. Let Q be rype-Ill symmetric conditional prior over U given X2" y and We E We. namely, Q (1)())).... (2()n)) ) [ZI1...,,, 22n), (y . V2n) ) We remains the same for all permutations n: [2m] - [2n]] that preserves the label, i..., (i) = y4 for i E [2n]. Then.
2E 2F S.
DKL.
p82n U. (U,U)X,X,
wallo) K +
Es, Eg.wlgen(S, W)] & 2nf
c
n
where S, S,S'We ~ Ps... Ps and the infimum is over all Markov kernels Pw.is is such that for W (We, Wa). Ers. Pw.1s [een(, W) gen(S, w)] & c.
The bound of Theorem to the best of our knowledge the first of its kind and significance. fact, while few works have alreudy investigated the generalization error of IB [SSTIO, VPVI8 KDIH23) for the special case of discrete variables, their bounds, which in part are expressed in terms of the empirical mutual information X(U; appear be vacuous for most settings already observed in [RG19 GK19 AG19 DKSV20
I Fon the generalization error of representation learning, and the related IB- IB-encoder,
(see introduction and Appendix [B.2] for more details). Furthermore, as also extensively discussed in [AG19 GK19 DKSV20]. mutual information may not be good indicator of the generalization error. Such aspects, including how mutual information fails to reflect "simplicity" or "structure" of the encoder, are discussed in more detail in the previous section. An alternate bound on the generalization error of representation learning appeared in DKSV22). However, their bound only holds for encoders that find the optimal representation in a sense defined therein.
Now, few remarks on the result of Theorem 4 are in order. First, note that the generalization bound of this theorem depends only the encoder and more precisely on the complexity of the latent space U; and, so, this bound is valid for any choice decoder Next, similar to the bounds of the Theorems [ the KL--divergence term of Theorem F explicitly takes into account the "structure" and "simplicity" " of the
2
encoder, and, therefore, it resolves one of the major issues of the IB method AG19 G919 DKSV20
Moreover, the result of Theorem suggests that the considered prior could depend on the data and model. This enables a larger class of choices for the prior. Examples include (i) Symmetric jointly Gaussian priors, (ii) priors that depend on the category (label), i.e., the prior for category l E [K] each optimization iteration could possibly depend on some statistics of the latent variables of all training and test samples having label and (iii) priors that steer latent variables toward some pre-defined "constellations" in the latent space. depending on their label. On this aspect, note that allowing the prior to depend on labels cnables a connection with the "conditional information-bottlene
of [Fis20].
Another important property of our bound of Theorem is that, unlike the empirical mutual information VPVI8 term of VVVII [DIHHg it does not become infinite for deterministic encoders with continuous input-output. Morcover, our approach which is based on lossy compression provides an interpretation of the geometric compression of [GK19 GVDBG 19] where latent variables are concentrated around some
II some cases, the bound may be loose, however, e.g., with decoder wa that produces an estimate y independently of the obtained representation U. 'The lossy compression trick, however, can also be applied for results of SSTIO VPVI8 KDJH23

---

constellation points Fl We hasten to mention that "lossy compression" here should not be confused with approaches that add noise after the encoder. The main difference is that those approaches the noisy representations are passed to the decoder; while here, the "noisy" representations are used only to estimate lossy compressibility. These "noisy" representations can be achieved by either adding small "noise" to the model parameters the latent variable. Note that by increasing the noise level the term in Theorem increases while the KL-divergence term potentially decreases. In practice, a suitable trade-off between the two effects be found by treating the amount of added noise hyper-parameter to optimize.
Finally, a similar tail bound on the generalization error has been established in Appendix
4 Experiments
In this section, we illustrate our results via some experiments. For more detail and other experiments the reader is referred to Appendix D
Our main Theorems and suggest that for the representation learning setup of Fig. lb the generalization U, (U, X' Y, w.)) Wo)
where Q a type-Ill symmetric prior. a sense, this also means that, with a proper data-dependent choice of the prior, the usage of the aforementioned divergence term as regularizer possibly offers better generalization guarantees (relative, e.g., to the conventional dala-independent prior of VIB). In what follows, we propose a new family of data- deta-dependent priors which appear to better capture the "simplicity" or "structure" of the encoder. We also compare the associated accuracy with that offered by the fixed prior of VIB.
error is controlled essentially by the divergence term Dx (p822
More precisely, in VIB the prior Q factorizes as product of 2n scalar standard Gaussian priors, i.e. Q = Q0an, where Q (0m, Im), Om E R the zero vector and In the m m identity matrix. In our lossless approach, which we here coin Lossless Q still factorizes as product 2n scalar Gaussian priors, i.e., Q = [hef2n] Qi but with three major differences: i. Each Q can be chosen from set of M x K priors M priors for each label. ii Unlike VIB, each of M x K priors can depend on some statistics of (S, SS) and also on the label of each sample, iii. Unlike VIB, where the prior is fixed, here Q is 'learned" during the training phase. To this end, the mean and variance of the scalar priors are updated after each training iteration using a moving average with some small coefficient, allowing the latent space better adapt the structure of the encoder and the data. Taking the moving average also has another role, which is to "partially" reproduce the effect of the "ghost data" (which comes from the datasct that usually unavailable during training). In lossy CDVIB, similar priors are considered but over "noisy" versions of the latent variables, iee. (Ü, U'). Note that while the noisy versions are considered for the regularizer, the decoder receives as input (U, U').
VIB (CDVIB), the prior
We consider CIFARIO I0 [KH 09] image classification using a small CNN-based encoder and linear decoder. The results shown in Fig. 2 indicate that the model trained using priors achieves hetter (~ 2.5%) performance in terms of both generalization error and population risk. This suggests that our priors help find better representation than the standard VIB prior.
-0.8
standard
standard
0.65
CDVIB
-0.9
CDVBB
lssslsss CDVIB
losslesa CDVIB
0.64
-1.1
0.62
-1.3
0.61
-15
16-7
10-6
20.5
20-4
10.3
16:2
16-1
16.7
10-6
20-5
30-4
30.3
30.2
16-2
Bell
Ball
(a) Accuracy.
(b) Log-likelihood.
Figure 2: Accuracy during test phase of our two-step prediction model trained using the standard VIB prior and our "lossless" CDVIB and "lossy" CDVIB priors computed for M = 5. The values are averaged over runs. The graphs are displayed together with 95% bootstrap confidence intervals.
'The reader is referred Appendix C.3 for simple example of geometric compression.
10

---

5 Acknowledgement
The authors would like thank the anonymous reviewers for their many insightful comments and sugges- tions. In particular, by pointing out the connection between our results and the f-CMI literature.
References
[AFDM17] Alexander A. Alemi, Ian Fischer, Joshua V. Dillon, and Kevin Murphy. Deep variational information bottleneck. In International Conference Learning Representations, 2017.
[AG19] Rana Ali Amjad and Bernhard C Geiger. Learning representations for neural network-based -based classification using the information bottleneck principle. IEEE transactions on pattern analysis and machine intelligence, 42(9):2225-2233, 2019.
[AGNZI8] Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via compression approach. In International Conference on Machine Learning, pages 254-263, PMLR. 2018.
[Aud04] Jean- Yves Audibert. PAC- BaC-Bay statistical learning theory, PhD thesis, Université Paris VI., 2004.
[AZ19] Inaki Estella Aguerri and Abdellatif Zaidi. Distributed variational representation learning. IEEE transactions on pattern analysis and machine intelligence, 43(1):120-133, 2019.
[BBR 18] Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeswar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and R Devon Hjelm. Mine: mutual information neural estimation. arXiv preprint arXiv: 1801, 04062, 2018.
[BEHW87] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Occam's razor. Information processing letters, 24(6):377-380, 1987.
[BHM720] Olivier Bousquet, Steve Hanneke, Shay Moran, and Nikita Zhivolovskiy. Proper learning, helly number. and an optimal svm bound. Conference on Learning Theory, pages 582-609. PMLR, 2020.
[BL03] Avrim Blum and John Langford. Pac-mdl bounds. In Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003. Proceedings, pages 344 117- Springer, 2003.
[BM06] Nader H Bshouty and Hanna Mazzawi. Exact learning composed classes with small number of mistakes. In Learning Theory: 19th Annual Conference on Learning Theory, COLT 2006, Pittsburgh, PA, USA, June 22-25, 2006. Proceedings 19, pages 213. Springer, 2006.
[BO18] Léonard Blier and Yann Ollivier. The description length of deep learning models. Advances in Neural Information Processing Systems, 31, 2018.
[BSE*21 Melih Barsbey, Milad Sefidgaran, Murat A Erdogdu, Gael Richard, and Umut Şimşekli. Heavy tails in SGD and compressibility of overparametrized neural networks. In Thirry- Fifth Conference on Neural Information Processing Systems, 2021.
[BZV20] Yuheng Bu, Shaofeng Zou, and Venugopal V. Veeravalli. Tightening mutual information- based bounds on generalization error. IEEE Journal on Selected Areas Information Theory, 121):121-,30, May 2020.
[Cat07] Olivier Catoni. Pac-bayesian supervised classification. Lecture Notes-Monograph Series. IMS, 2007.
[CK11] Imre Csiszár and János Körner. Information Theory: Coding Theorems for Discrete Memoryless Systems. Cambridge University Press, 2 edition, 2011.
[CK22] Dan Tsir Cohen and Aryeh Kontorovich. Learning with metrie losses. Conference on Learning Theory, pages 662-700. PMLR, 2022.

---

[CT06] Thomas M. Cover and Joy A. Thomas, Elements of information theory (2. ed.). Wiley, 2006.
[Dev83] Lue Devroye. The equivalence of weak, strong and complete convergence in for kemel density estimates. The Annals of Statistics, pages 896-904, 1983.
[DKSV20] Yann Dubois, Douwe Kiela, David J Schwab, and Ramakrishna Vodantam. Learning optimal representations with the decodable information bottleneck. Advances in Neural Information Processing Systems, 18118664--869) 2020.
[Fis20] Ian Fischer. The conditional entropy bottleneck. Entropy: 22(9):999, 2020.
[Gal68] Robert G Gallager. Information theory and reliable communication, volume 588. Springer, 1968.
[GB10] Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 249-256. JMLR Workshop and Conference Proceedings, 2010.
[Gei21] Bernhard C Geiger. On information plane analyses of neural network classifiers-a review. IEEE Transactions on Neural Networks and Learning Systems, 2021.
[GK19] Bernhard C Geiger and Tobias Koch. On the information dimension of stochastic processes.
IEEE transactions on information theory, 65(10):6496 6611499966661,,,,8 2019.
[GMPO5] Peter D Grünwald, In Jae Myung, and Mark Pitt. Advances in minimum description length: Theory and applications. MIT press, 2005.
[GP20] 7iv Goldfeld and Yury Polyanskiy. The information bottleneck problem and its applications in machine learning. IEEE Journal on Selected Areas in Information Theory, 1(1::19-38. 2020.
[GR19] Peter Grünwald and Teemu Roos. Minimum description length revisited. International journal of mathematics for industry, 1930000 2019.
[GSZ21] Peter Grunwald, Thomas Steinke, and Lydia Zakynthinou. Pac-bayes, mac-bayes and conditional mutual information: Fast rate bounds that handle general classes. In Conference on Learning Theorr, pages 2217-2247. PMLR, 2021.
[GVDBG+19 19] Ziv Goldfeld, Ewout Van Den Berg, Kristjan Greenewald, Igor Melnyk. Nam Nguyen, Brian Kingsbury, and Yury Polyanskiy. Estimating information flow in deep neural net- works. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 2299-2308. PMLR, 09-15 Jun 2019.
[HD22] Fredrik Hellström and Giuseppe Durisi. A new family of generalization bounds using samplewise evaluated emi. Advances in Neural Information Processing Systems, 35:10108- 10121, 2022.
[HJTWI]] Daniel Hsu, Ziwei Ji, Matus Telgarsky, and Lan Wang. Generalization bounds via distilla- tion. In International Conference on Learning Representations, 2021.
[HK Steve Hanneke and Arych Kontorovich. A sharp lower bound for agnostic learning with sample compression schemes. Algorithmic Learning Theory, pages 489-505. PMLR, 2019.
[HK21] Steve Hanneke and Aryeh Kontorovich. Stable sample compression schemes: New applica- tions and an optimal sym margin bound. In Algorithmic Learning Theory, pages 697-721. PMLR, 2021.
[HKS19] Steve Hanneke, Aryeh Kontorovich, and Menachem Sadigurschi. Sample compression for real-valued learners. In Algorithmic Learning Theory, pages 466-488 PMLR, 2019.
12

---

[HKSW20] Steve Hanneke, Aryeh Kontorovich, Sivan Sabato, and Roi Weiss. Universal bayes con- sistency metric spaces. 2020 Information Theory and Applications Workshop (ITA), pages 1-33. IEFF, 2020.
[HRVSG2I] Hrayr Harutyunyan. Maxim Raginsky, Greg Ver Steeg, and Aram Galstyan. Information- theoretic generalization bounds for black-box learning algorithms. Advances in Neural Information Processing Systems, 34, 2021.
[KASK22] Michael Kleinman, Alessandro Achille, Stefano Soatto, and Jonathan Kao. Gacs-korma common information variational autoencoder. arXiv preprint arXiv:2205. 12239, 2022.
[KB15] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
[KDJH23] Kenji Kawaguchi, Zhun Deng, Xu Ji, and Jiaoyang Huang. How does information bottle- neck help deep lcarning? In Andreas Krausc, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th Interna- tional Conference on Machine Learning. volume 202 of Proceedings of Machine Learning Research, pages 16049-16096. PMLR, 23-29 Jul 2023.
(KH+09) 09] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Toronto, ON, Canada, 2009.
[KTVKI8] Artemy Kolchinsky, Brendan D Tracey, and Steven Van Kuyk. Caveats for information bottleneck in deterministic scenarios. arXiv preprint arXiv:1808.0733 2018.
[KTW19] Artemy Kolchinsky, Brendan D Tracey, and David H Wolpert. Nonlinear information bottleneck, Entropy, 21(12):1188 181, 2019.
[KW14] Diederik P Kingma and Max Welling. Auto-encoding variational bayes. ICLR, 2014.
[LEG18] Chcuk Ting Li and Abbas El Gamal. Strong functional representation Iemma and applica- tions to coding theorems. IEEE Transactions on Information Theory, 64(1 (66666669676777 2018.
[LLS Yilin Lyu, Xin Liu, Mingyang Song, Xinyue Wang, Yaxin Peng. Tieyong Zeng, and Liping Jing. Recognizable information bottleneck. arXiv preprint arXiv:2304. 14618, 2023.
[LW86] Nick Littlestone and Manfred Warmuth. Relating data compression and learnability. Citeseer, 1986.
[McA98] David A McAllester. Some pac-bayesian theorems. In Proceedings of the eleventh annual conference on Computational learning theory, pages 230-234, 1998.
[NBS18] Behnam Neyshabur, Srinadh Bhojamapalli, and Nathan Srebro. A pac-bayesian approach to spectrally-normaliieed margin bounds for neural networks, 2018
[PGM 19] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32. 2019.
[RG19] Borja Rodriguez Galvez. The information bottleneck: Connections to other problems, learning and exploration of the ib curve, 2019.
[RGBTS21] Borja Rodríguez-Gällve. Germán Bassi, Ragnar Thobaben, and Mikael Skoglund. On random subset generalization error bounds and the stochastic gradient langevin dynamics algorithm. In 2020 IEEE Information Theory Workshop (ITW), pages 1-5. IEEE, 2021.
[RGTS20] Borja Rodríguez Gálvez, Ragnar Thobaben, and Mikael Skoglund. The convex information bottleneck lagrangian. Entropy, 22(1):98, 2020.
[Ris78] Jorma Rissanen. Modeling by shortest data description. Automatica, 14(5):665-471, 1978.
13

---

[RZ16]
Daniel Russo and James Zou. Controlling bias in adaptive data analysis using information theory. In Arthur Gretton and Christian C. Robert, editors, Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Research, pages 122--1200, Cadiz, Spain, 09-11 May 2016. PMI.R.
[SAM* + 20] Taiji Suzuki, Hiroshi Abe, Tomoya Murata. Shingo Horiuchi, Kotaro Ito, Tokuma Wachi, So Hirai, Masatoshi Yukishima, and Tomoaki Nishimura. Spectral pruning: Compressing deep neural networks via spectral analysis and its generalization error. In International Joint Conference on Artificial Intelligence, pages 2839-2846, 2020.
[Sau72] Norbert Sauer. On the density of families of sets. Journal of Combinatorial Theory, Series A, 13(1):145-1477 147, 1972.
[SGRS22] Milad Sefidgaran, Amin Gohari, Gael Richard, and Umut Simsekli. Ratc-distortion theoretic generalization bounds for stochastic learning algorithms. In Conference on Learning Theory, pages 4416-4463, PMLR, 2022.
[She72] Saharon Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific Journal of Mathematics, 41(1):247 261,, 1972
[$SDE20] Umut Simşekli, Ozan Sener. George Deligiannidis. and Murat A Erdogdu. Hausdorff dimension, heavy tails, and generalization in neural networks. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 5138-5151. Curran Associates, Inc., 2020.
[SST10] Ohad Shamir, Sivan Sabato, and Naftali Tishby. Learning and generalization with the information bottleneck. Theoretical Computer Science, 41 129-300)226666 2010.
[S720] Thomas Steinke and Lydia Zakynthinou. Reasoning about generalization via conditional mutual information. In Jacob Abernethy and Shivani Agarwal, editors. Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 3437-3452. PMLR, 09-12 Jul 2020.
[S723] Milad Sefidgaran and Abdellatif 7aidi. Data-dependent generalization bounds via variable- size compressibility. arXiv preprint
05369, 2023.
[SZT17] Ravid Shwartz-ZN Ziv and Naftali Tishby. Opening the black box of deep neural networks via information. arXiv preprint arXiv: 1703.00800 2017.
[THP23) Dor Tsur, Bashar Hulcihel, and Haim Permuter. Rate distortion via constrained estimated mutual information minimization. In 2023 IEEE International Symposium on Information Theory (ISIT), pages 695-700, 2023.
[TPB00) Naftali Tishby, Fernando C Percira, and William Bialck. The information bottlencek method. arXiv preprint physics/0004057, 2000.
[VDOV+ 17] Aaron Van Den Oord, Oriol Vinyals, al. Neural discrete representation learning. Advances in neural information processing systems, 30, 2017.
[VPV18] Matí Vera, Pablo Piantanida, and Leonardo Rey Vega. The role of the information bottleneck in representation learning. In 2018 IEEE International Symposium on Information Theory (ISIT), pages 1580-1584, 2018
[Wai 19] Martin J. Wainwright. bridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
Statistics: A Non-Asymptotic Viewpoint. Cam-
[XR17] Aolin Xu and Maxim Raginsky. Information-thherete analysis of generalization capability of learning algorithms. Advances in Neural Information Processing Systems, 30, 2017.
[ZEAS20] Abdellatif Zaidi, Iñaki Estella-Aguerri. and Shlomo Shamai. On the information bottleneck problems: Models, connections, applications and information theoretic views. Entropy. 2512):151, 2020.
14

---

Appendices
The appendices organized follows.
Appendix containn further theoretical results. Specifically,
in Appendix [.I] [wo more tail bounds on the generalization error in terms of the predicted
label complexity are presented.
in Appendix |.2 a tail bound on the generalization error in terms of the latent variable complexity is presented.
We discuss some the related works in more detail in Appendix In particular,
in Appendix B.
we recall the compressibility framework of Blum and Langford [BL03
in Appendix B.2 discuss the results of (KDJH23).
we discuss various topics that could not be sufficiently addressed in the paper, due to lack of space. More preciscly,
Appendix C
define various notions of compressibility, including lossless, lossy, and variable-size compressibility in Appendix C.1
C.I
we present intuition on the function hp(--). used in Section in Appendix
we give a simple example of geometrical compression, and its relation to lossy compressibil- ity, in Appendix C.3
and finally we present the conclusion our work together with some interesting future directions in Appendix C.4
Appendix contains the details of the experiments presented Section
Appendix D.
recalls the standard VIB objective function,
Appendix D.2
defines family of lossless objective functions using data-dependent priors,
Appendix
defines a family lossy objective functions using data-dependent priors,
Appendix
D
details the training and testing datasets used in experiments,
Appendix
D.5
details the model architecture used in experiments,
Appendix
D.6
provides training details,
Appendix D.7
presents and discusses the numerical results.
Appendix contains the deferred proofs of our theoretical results. More precisely,
the intuition behind our proof tcchniques is presented in Appendix B.
Appendix
E.2 contains the proof of Theorem
Appendix
contains proof of Lemma
Appendix
contains the proof of Theorem
Appendix
contains the proof of Theorem
Appendix contains the proof of Theorem
Appendix
contains the proof of Theorem
Appendix
E
contains the proof of Theorem
Appendix
E.9
contains the proof of Lemma
A Additional theoretical results
In this section, present several tail bounds the generalization enror in terms of the complexity of the predicted labels or the latent variables.
A.1 Tail bounds on the generalization error in terms of predicted label complexity
First, we start by stating a lossy tail bound on generalization error terms the complexity of the bound.
15

---

Theorem 5. Consider the learning framework defined above. Let Q be any fixed type-I symmetric prior
on (Y, Y') that could depend on (X, X Y'). Then for any e E R and E IR with probability at least
(1 8) over choice of S and S', we have that W Pwis [gen( (S, W)] is upper bounded by
(og(2/6)
2n + inf
B BW--Pass
DKL V/X,W (Y, Y' XX + log((V8B/0)) (o((VB//))
2n -
where the infimum over all Pwis that sarisfy
E Ewis Pis ()sss,)>-ao -
B(s -
e/2.
(6)
The theorem is proved in Appendix E.6 In the above result, it is easy replace the expectation with respect to PwIs with any arbitrary expectations, as it is common PAC-Bayes bounds and used for example in NES188
Next, we state a tail bound terms of the function hp(s)) +), defined in (
Theorem 6. Consider the learning framework of Section Let Q be any fixed type-ll symmetric prior on (Y, Y!) that could depend (X, Y, X. x Y'). Then, for any Rt,, with probability at least (1 8) over
choices of (S, W) ~ Ps Ps,,, it holds that
nhn (..) &DRL.
82n Y (Y. (X. + log(n/6).
This theorem is proved in Appendix E.7 In particular, when É(S, W) 0, using Lemma conclude that, this result yields that with probability at least (1 1--3 5),
p8en DEL
Fix.W FI XX,,'X W) Q + +og(n//))
L(S", ()) &
A.2 Tail bounds on the generalization error in terms of latent variable complexity
this section, we present a tail generalization bound for the two-step learning setup of Section highlights the relevance of latent variable compressibility to generalization error.
3 that
Theorem 7. Consider K-classificatio learning task with the above defined framework. Let Q be a type-lll symmetric conditional prior over 222n given X2n y2, and We E We. namely. Q (uI(1))..... (212))) (V1...., ,V2n),, w) remains the same for all permutations :: [2m]
[2m] that preserves the label, i.e,, (i) Vi for i E [m]. Then, for any X E R
i. with probability least (1 - 6) over choices of (S,S W) Ps.
DKL.
p82n
UJX,W. (U, Wo) Q) -K log(1/8)
((s', (W) &
21
n
ii with probability at least (1 - 8) over choices of (8, W) ~ Ps.
gen W) DKL
p22n U.X.W, (U, X Q (K 2)/2 + log (2/0)
2\
log
Note that the sccond part of the theorem can be casily derived from the first part using Hoeffding's incquality. We provide the proof of the first part in Appendix E.8
B
Related works
In this section, discuss some of the related works in more detail.
16

---

B.1 PAC-MDL framework of Blum and Langford
Here, we recall the PAC-MDL framework of [BL03] which, therein, was introduced in the form of a (compression) game between two agents, Alice and Bob. Alice has access both labeled training set S = (x", y,", consisting of n labeled samples, and a test set S' = x" consisting of n unlabeled samples, all drawn independently from [ Bob has available just the test set and the unlabeled version of the training set, i.e. (X", ,x"), ordered in some predefined (c.g., lexicographic) order known to both agents. Hereafter we denote the ordered vector of labeled and unlabeled samples as T x²"). is assumed that by observing the vector ((X",X* Bob cannot know which samples of it are from the training set and which are from the test set. The goal of Alice is to communicate the labels o(Y", y") to Bob using as few bits as possible. To this end, let E: z" x X - {0. 1)* be mapping (encoder) used by Alice and a = ESS, x the string transmitted to Bob. The goal of Bob is to guess the labels of both sets X and x and does so by running decoder mapping D: x x {0, 1 - y/2m. That is, Bob forms an estimate of the true labels as D(x(Xx,, _x"),,)) In this context, the empirical risk is measured C(a, s, s,) := 1
2 >ine [x] (M.+ and proxy test risk is measured Li s, := [ 1 (v)+ Essentially, the PAC-MDL bound of [B103] can be seen as a generalized version of Occam's- S-aaor
theorem [LW86 BEHW87] which states that if one can explain (or encode) the labels of set of training samples by a hypothesis that can be described using only |a| & n bits then this guarantees that this
hypothesis generalizes well for unseen samples.
Theorem (BL03 Theorem 6)). For any prior distribution Q()) of a and any > 0. with probability at least 5 over the choices of S,S' PsPs' we have;
Vo:: nC(o, bmax (n, L(o (.,)
where
bmax (n. () max(b: Bucket(n, a, 3 8).
(8)
and
(a+h-o
Bucket(n,,,
Σ
(9)
2n
cE(b,a+b]]
(a+b)
The result is made more explicit for the so-called realizable case, i.e., when S,a, = 0. For this case, we have [L03] Corollary 3]
r(vo: ((o,S,5) > or Clo, 5,5") & (lol + (1/2(1/)))/m)) > 1 8,
where |o|| denotes the size in bits of the string using some priori fixed codewords. The result clearly shows that if the string a can be sent using few bits then the algorithm generalizes well. Also, the approach can be used in order to establish similar results for the VC-dimension and PAC-Bayes bounds.
We emphasize that our construction
sharp contrast with an adaptation of the above-described approach of Blum and Langford [BL03] in which one would reveal both labeled and unlabeled samples (STT x²"m)) to Alice and only unlabeled samples (X x to Bob (both predefined order). We, however, in proposed approach in Section 2. reveal the vector 3 32m containing (S S in predefined order
to both. Furthermore, we emphasize that the goal in our approach is not to recover the labels 2) 2 but the predictions 2mmm produced by the picked models hypotheses m
On another note, we remark that the interpretation of Rt which appeared in the size of the codebook in our approach, i.e., [)/ml & et corresponds to the average number of bits (per dataset S) that is needed to send a compressed version of the string a [BL03] As such, for the fixed-size codebook explained in Section 2.1 and when |o| is constant, R & |o]. Similar relations hold in general, by considering the variable-size codebook.
'For simplicity, we assume here that the training and test sets S and S' have identical sizes, i..., |S| but all the results that will follow extend easily to the case of [S] y (.5). Note that Alice does not know the true labels ' of the test samples X and can only estimate them as pm
||
17

---

B.2 On the generalization bounds of KDJH233
After the initial submission of work, another work [DJH233 appeared on arXiv, accepted at ICML 2023, that provides an upper bound on the generalization error of representation learning algorithms. As claimed, this result justifies the benefits of the information bottleneck principle. by relating generalization error. The results provided for the multi-layer neural networks and for different choices of latent variables corresponding to the output of different layers. Here, to adapt the results to the selup of this paper, we only consider the output of the encoder layer as the latent variable and adapt correspondingly the notations of the results in [DJJ223 to our notations.
the
With the adapted notations, KDJH23 claims to bound the generalization error of representation learning algorithm "roughly by
T(X;UI))+ +
However, firstly, since this bound is in terms of the mutual information function. the critics on the relation of mutual information and generalization error, discussed in [KTVKI8 RG19 AG19 DKSV20 and provided also in the "Crities to IB" section of the introduction (Section are valid for the results of KDJH23), as well. More importantly, we could not conclude the reported order-wise behavior from
KDJH23 Theorem 2]. Using the notations of our work, their result states that with probability at least 1 5 over training data S, the gencralization error is bounded by
(I(:UU)Y) + 1W) + G2
G1 Vn'
G3
where the constants G1, G2, and G3 are defined in KDJH233 Appendix F. I] and claimed that &2 (1) and G3 (1), as n co. However, we were unable resolve the following concerns regarding this bound.
Firstly, it is not clear how T(We: S) is considered behave Õ(1), when n cc. Indeed, the size of dataset S and the learning algorithm Pw.1s change as n - cc.
i. Secondly, by referring
definitions of the constants in [DJA23 Appendix E. it can be
easily verified that G2 C1 (H (H(UIX, Y) + H (We (S)) In (2). for some non non-negative constant
C1. Hence, the bound can be re-written as
(H(UlY) H(W.)) hn( Ci
Gi
G
Vn
Thus, the bound is in terms of H(UYY) + H(W)), and not T(X;U)Y) + I)We:
iii. Lastly, the term G3, defined in KDJH233 Appendix E.1], I1, is composed of Ty E elements. By [KDHH23] Lemma 21, Ty behaves roughly as ((2))) Using [DIH223 Lemma 2]. shown that G3 is bounded. However, it seems that this is only shown by assuming that the Ty terms of G3 satisfy certain conditions related to decreasing rate their ordered values. This assumption however, may not hold general, and hence G may behave ŌTT,) (VID)) which then becomes the dominant term in the bound.
C Further clarifications and discussions
In this section, explain compressibility framework in detail. Moreover, present intuitions on the function (p(r)) and give an example of how lossy compression is related to geometrical compression. Finally, we discuss some potential future works.
C.1 Compressibility framework
In this section, we propose various notions of the compressibility used in Section 2
C.1.1 Lossless fixed-size compressibility
start by recalling needed elements for joint compression of block the predicted labels. Consider m i..d. pairs of train and test datasets S, (Z 4j,n) and Sy == (2), 4)..)
18

---

where Z,,i - (X).s. K.s and Z (X),, Let Sth - (Si...., Smm) Stm (S ..) and W == (Wi,.... Wm) where W ~ PW,1s,, important to note that the model or hypothesis W is chosen based on the dataset S; only and the introduction of the (ghost) datasct Sÿ is here only for the sake of the analysis, similarly as it was done in the derivation of the PAC-MDL bound of [BL03] or in Rademacher sample complexity or the conditional mutual information of [SZ20]. Denote the predicted labels using model W; for inputs X1, and X),, as Yj.+ and y for j [m] and i [n].
Moreover, let 32mn E 222m denote rearrangement of the elements of "S"",""") such that while the entire sets 5th and 8 are known by having the vector 3 32mn but they are arranged in an order that one cannot distinguish whether a given sample x from STh or 5tm Accordingly, denote the rearranged versions of (Y"",, y and (Y"mh, y-min) respectively by 2)amn and 2)2mn. In Sections and and 2.3 we presented two methods for such rearrangement. As mentioned before. in both methods, the rearrangement of (STh _5t) as 32mm {33.)] jie(] is done in two steps: First, for each j E [m]]. we rearrange indistinguishably Sy)) as 3),²n, and then we concatenated the resulting {3,"" ]J][m]] to achieve 3 2mn Now, we explain how to rearrange indistinguishably a given (") as 32n using two methods:
Section 2.2 Let J = (JI....,,Jh) Jn) be vector of n i.i.d. Bernoulli (+) random variables Jj E (i, n) [n]. Denote by J (Jf...., JR) the vector of the complementary choices in J, i.e. J J. = {i, i nJj. Now, for cach e [n.. lct (3.,. to be equal to (Z;, 2₁).
Scction 2.3 Let T = (Ti...., , 3. be a random set obtained by picking uniformly n indices from {I,..., 2n), without replacement. Note that in contrast J which had i.idd. components, here the components of T are dependent. let T = (l,..., ......,2]]...... 2n]/T T be the complement of T, having the elements T (Tí...... T. Now, for each i [n]] let (3m.3...) (Z, Z/).
Based on the above, hereafter we study the compressibility of the sorted from an information-theoreti point of view. The rationale is that, in accordance with "Oecam's Razor" theorem [LW86] [BEHW87), since the (rearranged) predicted-labele vector 2) 2mmn agrees mostly with the true labels 2) 2mm on the dataset S if ②) 2mm can be described using only a few bits, this guarantees that the model W generalizes well. As it will be shown from the result that will follow, instead of the size of the message needed to be sent in the Blum-Lane Lann-Lngfoor approach (see Appendix[B.]] a new quantity emerges in our work measure of the compressibility of 2)amm, the relative entropy of the joint conditional p(L"", " y and a (symmetric) conditional prior Q over y given y22", Depending on the way we rearrange (55T 5tm),, ), the type-I or type-Il symmetric priors needed be applied.
labels 2)
Let R E R.. In our block-coding rate-distortion thcoretic framework, R is said to be achievable there exists a compression codebook of size emR, fixed priori, which covers the space spanned by the model-predicted labels 2j with high probability. Specifically, if there exists a sequence of label books (Dim Ime,, where Vm == [S[r],r [mm]] S y22m, Im N. 9[r] (.[[r......$.. and rr = (0s.1rr..... (j.2n E y such that:
(i) mm & RR
(ii) there exist a sequence Imm for which limm- &m = 0 and with probability at least (1 - 8m) over the choices of 5th s.m. and J or T. one can find at least one index r e [mm] whose associated }[r] exactly equals 22mm..
The above framework, explained in Scction 2.1 is called fixed-size compressibility, as the size of the codebook does not depend on a given dataset. This type of compressibility is useful for establishing "data-independent" B e.g. bounds on the expectation of the generalization error. This is also called lossless, since we look codeword that is exactly equal to 2)2m..
C.1.2 Lossy fixed-size compressibility
As already stated, the above approach and results can be extended to any bounded loss function and continuous variables Y and y (see for example Section 3 where continuous latent variables are studied). In this case, standard result of rate-distortion theory states that to cover losslessly and reliably 2) 22mm R should be infinity, which makes the framework and resulting bounds vacuous. However, the approach can
'Here, we emphasize that by data-dependent bounds we refer to bounds that depend on the particular sample of the input data at hand, rather than for example just on the distribution of the data which is unknown.
19

---

be easily extended to include the lossy compression of the labels; in the same spirit as done in |SGRS22 for hypothesis compression. More precisely, for a given distortion threshold IR, one can consider same way of codebook generation, but with the following conditions:
(i) emR
(ii) there exist sequence f8m bme for which limm- om 0 and with probability at least (1 8m) over the choices of 5th ,mm, and J or T, one can find at least one index r E [1m] whose associated
8[r] satisfies:
1
Σ (4100ee4401..))) (1050
(is - (0..,, (b...))))
mon [e[m]
where it is assumed that set indices {(j. femm) and (() jejm)) are the sets of indices in the rearranged sequence that belong to the training and ghost datasets, respectively, Here, Ukefm] (4, o ( = (I,...,2m].
In the case of lossy compressibility, the block-coding technique brings another advantage in addition to the advantages discussed for the lossless case: allows to consider the average distortion criterion, instead of worst-case distortion criterion. Please refer to [SGRS22 for further discussion on this.
C.1.3 Variable-size compressibility
In the frameworks, explained in previous sections, for given m, the size of the codebook e'n is fixed. Hence, the bounds derived using this framework, cannot depend on a particular training dataset at hand. In particular, while above mentioned frameworks useful establish bounds the expectation of the generalization error, they are not appropriate for establishing data-dependent tail bounds. To overcome this issuc, in [S723] "variable-size" compressibility is proposed, which, one allowed search for suitable [r] only in the first e Rissss elements of this codebook, where R[s,s', w) is the data- dependent term that will consequently appear in the resulting bound using this approach, For instance, the term (S.S" W) in Part.ii of Theorem iis exactly the KL--ivergence term appearing in the bound.
C.2 Intuition about the function hp
In Section 2.3 we have provided the bound on the generalization error in terms of the function hp(a;=') [0, [0. 2]. defined as:
x (1=
x ===="
(1) 2/1b
where (x) z (ogg(()) (z)- (1) logg(1 (1 zz). As mentioned, (2, (2,,2"=))) is equal to the Jensen-Shannon divergence between two binary Bernoulli distributions with parameters i and x'.
In this section, we provide an intuition about this function, by showing its relation with the combinatorial term that appeared in [BL.03] Recall that the main result of (BL.03, i.e., Theorem therein (re-stated in the Appendix B. J. is established in terms of (n, a/n, 6) defined as follows:
bmax n1, _ := max(b: Bucket(n, a, b) > 6),
where
latb
Bucket(n, b,
2n (a+b)
cE(b.a+b]
where [b, a b] N denotes the integer interval and c E N.
Now, the intuition about the function h (I,, x²)
follows: by Stirling's formula, have that
ma
mi)
mmnhp at
(10)
2mn
ma mb
as m + 30. Hence, for large (infinite) values of mn we have that the function Bucket(mn,, ma, mb) of BB00 is dominated by
mmn 2t0-1)
max b
(11)
20

---

where [b, bf c R denotes the real interval and & E R. Furthermore and as consequence
a mnn =, 5th) max b: min b.
nhp ( + 6---- & log(1/8)
bmax
(12)
m
771
can be observed that by considering cooiing and letting m cp. the intractable combinatorial terms appeared in [BL03] can be expressed in terms of the function (p())-).
C.3 On relation between lossy compressibility and geometric compression
The experimental studies suggest the existence of a relation between generalization performance and geometrical compression [KK19]. Geometrical compression occurs when the latent variables concen- trated around a limited number clusters. Please refer to [GKT9] Fig. 2] for a visual representation. As mentioned both in Section 3 lossy compression provides interpretation of the geometric compression of [9 GVDBG 19) where latent variables are concentrated around some constellation points. In this section, provide simple example of that.
geometrical compression, the latent variables ~ Puix are distinet but concentrated around few "centers". Hence, while in this case, the "lossless compression" captured by I(U; X) becomes very large or infimite, the "lossy compression" cuptured by rate-distortion may be very small, as these scattered latent variables around the centers can be seen lossy version of the mappings from X centers, with some small distortion. To give a simple example, suppose X [0, 1J. and X < 0.5, then X /5. In this while I(U; X) oo, simple lossy
of these
U - + /5, and if X >> 0.5, then U mapping Poix with average distortion less than 0.05 can be found such that I(U; X) = 1. This explains the geometrical compression observation.
C.4 Conclusion and future directions
In this paper, inspired by [BL33, we developed a compressibility framework that we used establish various bounds on the generalization error of the stochastic learning algorithms. The bounds are expressed terms of the newly defined notion of "minimum description the latent variables. The notion is expressed in terms of "symmetric" prior, where the "symmetry" defined and used in three different ways. The type-I and type-Il symmetries are useful to establish bounds in terms of MDL of the predicted labels. The former one, in particular, shows clear connection between the seemingly different approaches of [BL03 and CMI (SZ20] HRVSG21). The type- symmetry is used to derive the main result of this paper which is bound in terms of MDL of latent variables. The results of the last section suggest that the generalization error in representation learning is related to the newly defined MDL of latent variables. Unlike mutual information, which captures the "information leakage", , the new notion of MDL captures the simplicity and structure of the encoder. These insights are then partly exploited propose new regularizers in terms of "data-dependent" priors. The performed simulations show the advantage of these priors over the classical ones used in VIB.
of the predicted labels or
Our proposed framework and obtained results also open up several future research directions. In the following, we discuss some of those directions.
In Part i. of Theorem 1 we proposed a tail bound, which unlike the classical PAC-Bayes bound with a single draw from the posterior [Cat07), does not contain a "disintegrated" term. As explained, this is due to the choice of the loss function, which inherently contains an expectation term. It would be interesting to consider a loss function that captures the "one-shot" prediction of the performance to develop a disintegrated bound for such a loss function.
One of the contributions of this work has been establish "rate-distortion theoretic" bounds by using lossy compressibility framework. For example, the established bound in Theorem 4 contains an infimum over all "compressed algorithms" Pw: is that satisfy some distortion criterion. Note that this implies that this bound holds for "any" choice of cligible Pw.is- and thus, taking the infimum obtain "valid bound" is not necessarily required. Thus, any simple technique that adds noise or applies parameter quantization can be considered. However, besides these general approaches, an interesting direction is how to find an "optimal" P Pw.is: Perhaps, the approach taken [HP233] which uses combination of
the MINE estimator
BBR 18 and the "SFRL" [LEG18] could be adapted to our setup.
21

---

Another potentially valuable direction would be to compute the bounds analytically in simple setups, such as two-layer neural networks with Gaussian data, and compare the results with the existing results such as [VPVI8]. Also, it is instructive to study numerically the geometry and MDL of the latent variables for different network architectures, e.g., FCN versus CNN. This may lead to new understanding of how and why some architectures produce "better" representations.
Inspired by our results, we have proposed some simple "data-dependent" priors. While the proposed priors show improvements over the classical priors, they are limited to priors that can factorized as products of some Gaussian distributions. Thus, they only "partially" capture the joint compressibility of the latent variables (and hence the encoder structure). We imagine that more "appropriate" priors can be proposed that capture better the structure of the encoder.
In this paper, we partially discuss the intuition behind the importance of the "structure" of the encoder. However, the explicit effect of the "structure" on the geometry of latent variables and predictions needs to be investigated, as partially shown in [BM06].
Finally, we emphasize that in representation learning, one is interested in extracting good representations that are suitable in terms of generalization error for multiple learning tasks, simultaneously. It would be interesting to extend our results to such more realistic settings.
D Details of the experiments
this section, we present the details of the experiments presented Section
D.1 VIB objective function
The traditional information bottleneck (IB) approach TPB00 SSTIO for training representation learning models, and particularly its variational implementation (VIB) by (AFMM17), considers fixed data- independent prior Q @82n. Then, for some Lagrange multiplier 3 > 0, the VIB approach minimizes
E (DDKL Poix. (U, Wo)ll - Ey Pu: x,w. W.)) log Priu,, (wilUg, wa)]:
using the reparamctrizatioo trick of KW14). As can be noticed, the first term, which acts as a regularizer, only takes into account the training dataset part of DxL U, (U, U' X, x',Wa', We) Q). the test set is not available. The second term attempts to maximize the relevance of U for prediction. Intuitively, it seeks to find the best decoder among the possible choices, i.e., the one that minimizes the empirical risk.
pp82
A popular choice for Q is the multi-dimensional standard Gaussian distribution Q N'Om, Im), where Im is the identity matrix, m dimension the latent variable U, and 0m E R. is the zero vector. In the original implementation of [AFDM17), for each sample ær, the encoder generates the mean far = (H pz, R and variance of (. 22 ). e R" the latent variable U. Then, we let Pejx,w. (U) We) = Niu,, (1)),, where diag(o?) E g denotes a diagonal matrix whose diagonal clements are denoted by the vector of. This means that the latent variable for the input is generated according to U ~ - N(u, diag(a.)). Hence, the objective function to minimize becomes
b B DKL (N diag( Im)] Ev Popxo. Pul................... log Priu.w (Mi Wa)
(13)
where b is the size of a mini-batch of training samples .1...., Ab. 2 (#; vi). Morcover, 13 is repeated itcrativcly over multiple mini- batches until the convergence the representation lcarning model.
D.2 Lossless CDVIB objective function
We describe here another learning appreach which, unlike the VIB, uses data-dependent prior. This prior, coined Saategory-Dependee
VIB (CDVIB) is again factorized as product of 2n. scalar Gaussian priors, ie.. Q = The Q; Each of these scalar priors Q; is chosen among one of the K x M Gaussian priors (centers) M priors per each label. More precisely, for cach label l e [K], we consider M e N priors
r [M], e [K], -N(1( (1)) diag okrr (1)
)))
22

---

defined over R", where the superscript N represents the optimization iteration.
Unlike in the VIB approach, the mean and variance of the scalar priors are updated during the training process. Firstly, the vectors Mer and (1)
initialized respectively m-diimensional vectors of zeros and ones. Next, these initialized vectors are updated each iteration using procedure defined below.
kk.r
For any sample (z, y) with label y = k and for any iteration category-dependen prior (center) which is the closest to [(Hr, diag(a))) in terms of the KL-divergence
let r E [M]] denote the index of the
arg min DEL Wuu, diag diag(r)))]ll
(0)
(0)
Pk.
Suppose that the picked mini-batch at iteration B, (z1....: 2.). For each E [K] and r [M], let
k.r z i [b], Vs = k, = =r>
and let byrr [x,r|- Now, if bkrr o update Per and ohr as
(t)
(t) Pkr (1 - abb, (1-1)
Σ zeIEer
peil
( k.r
(t-1)2 (1 - abx,b k.rd
Σ
2 j i
=
k.r.
2,E,,
where é [o, 1] a coefficient that smoothens the evolution of the mean and variance, and also implicitly takes into account the effect of the ghost dataset S' appearing in the bounds of Theorems 4 and 7 The
optimal value of a, among others, depends on mini-batch size and the number centers M
Finally, the considered objective function at iteration in the Lossless CDVIB approach is
8 DKL N MM(a, ding(o
(z(0)
diag(a 2 ]
(C.l,,,))) log Prlu,s, (ni Wa)]
(14)
D.3 Lossy CDVIB objective function
Inspired by the lossy compression and bounds introduced in work, consider the MDL of the "perturhed" latent variable, while passing the un-perturbed latent variable to the decoder. More precisely, as before, consider the log loss for evaluation of the relevance of U in the decoder, i.e.
BU,- Pujx, w. W.)) log Pyjc, w, (3a1U,, Wa)
For the regularizer, we first consider the perturbed U as
= U + Ze = μ + Z2 x 21 = 01 + Oz
(15)
where Z1 and Ze are independently drawn from the same distribution
Note that we chose
Ú == px + 22.
Ú2 Ú2 71
(16)
Hence, given (X, We), Úi ~ N(ux, Im) is independent from 0Ú ~N0,, di)g(o))). )). Let us define two sets of priors Q = (ee [M[]]] over U1 and Q2 = {Q2,k.r like [e[[K]eee[M over Ú2. Next, for cach e [b]. we select two priors Q1 E Q1 and Q2 22, in a manner that will become clear in the following. Denote the induced prior for Ō Ú₃ Ü2. where Ú₃ ~ Q1 and U2 ~ Q2, by Q4. Then, the KL divergence of Püjx, (Ú|X, We) and Q. can upper bounded by
DKL poxx.w (.)).W))l 1Q
<DKL Po,I, (61Ix,
- DKL PisIx.w. (it.xxwww0//x... (ú2)X, We)
-DKL
N( N
Lm)xx DKL N(0m, diag( diag(ox)))10
(17)
'It can be shown that this choice of prior for M = satisfies the type-Ill symmetry property and for M > 1 approximation of a prior that satisfies such symmetry.
23

---

We use this upper bound for our regularizer. To make things more formal, for each label & [K], we consider 2M priors, M E N,
i,kr =N (1 rE ke [K],
22 =M Om, diag (11)
))
[M],EE[K]
defined over RT,, where the superscript represents the optimization itcration.
Similar to lossless CDVIB, firstly, the vectors ( and (t) kir initialized respectively m-dimmenionnal
vectors of zeros and ones. Next, these initialized vectors updated at each iteration using procedure defined below.
For any sample = (z. v) with label & and for any iteration t > 1, let [M] denote the index of the cutegory-dependent prior (center) which has the smallest distance (Qi,k.r minimizes the RHS of (17). In other words, 2 equal
(Q Q 12,,,r) in sense that
arg min DKL N(ue, (M Jm) DKL O0 diag(o?))1 Om, diag okr [e[M]]
Then, the mean and variances of the priors are updated exactly similarly to Lossless CDVIB. For complete- ness, we repeat this procedure here. Suppose that the picked mini-batch at iteration is Bt {=1,-.., 2b) For each E [K] and r E [M], let
I (0) k.r & i [6], krr =r].
and let by.r [Irrl- Now, if burr * O, update
(e) and ((t) as
Mk.r (1 -abbb))
(8)
(t-1)
Σ per: ziEle,r
(t) k.nd
ob-r
(t-1)² kind
Σ
B.g 1,...., m,
ZIEI
where a E [0, 1] is a coefficient that smoothens the evolution of the mean and variance, and also implicitly takes into account the effect of the ghost dataset S' appearing in the bounds of Theorems and 7 The optimal value of a, among others, depends on the mini-batch size b and the number of centers M.
Finally, the considered objective function at iteration in the Lossy CDVIB approach is
1
3DKi. Im))I Im)) (z)) wird Im
+BDKK N(00: [i Om. diag (a(1)
vort! 9)]
b
-U (.la,, log (ww.s.
(18)
D.4
Datasets
In the experiments, we used CIFARIO KH 09 The full dataset was split into a training set with 50,000 labeled images and validation set with 10,000 labeled images, all of them of size 32 x 32 3. The input images were scaled to have most values between 0 and before being fed to the network.
D.5 Architecture details
The model architecture considered in our experiments is detailed in Table The encoder part of our two- step prediction model a convolutional network consisting of four convolutional layers followed two linear layers. We use max-pooling and LeakyReLU activation function with a negative slope coefficient equal to 0.1. The encoder takes input re-scaled images and produces parameters μa and variance of of the latent variable of dimension
64. The latent samples generated using the reparameterizztion trick of [KW14). Next, the produced latent samples are processed by decoder consisting of one línear layer with softmax activation function. The decoder outputs soft class prediction.

---

Similarly, as in [DKS220]. our evaluated encoder is complex enough in order to make it close to "a universal function approximator". On other hamd, we use simple decoder as in [AFDMI7] in order to reduce spurious regularization introduced by the high decoder's complexity and hence to highlight the henefits of our regularizer terms of generalization performance.
Table 1: The model architecture used in experiments. The convolutional layers are parametrized respectively by the number of input channels, the number of output channels, and the filter size. The linear layers are defined by their input and output sizes.
Encoder
Encoder cont'd
Encoder cont'd
Number
Layer
Number 6
Layer
Number
Layer
Conv2D(3,8,5)
Conv2D(16,16.33
11
Leaky
C3,,2D(3,8.5)
LeakyReLU((O.))
12
(inear(256,122)
(e00)))
8
MaxPool(2.22)
Decoder
MaxPool(2.2)
9
Flatten
Linear(64, 10)
Conv2D((8,16,3)
10
Linear( Linear(1024,225)) 1024,256)
Softmax
D.6 Implementation and training details
Our prediction model trained using Py ToToc 19 and GPU Tesla P100 with CUDA 11.0. All weights were initialized using the default Py Xavier initialization scheme [BBI0] with all biases initialized zero. The Adam optimizer KB15) (31 0.5, 022 0.999) was used with an initial learning rate of 10 4 and exponential decay of 0.97. The batch size was equal to 128 throughout the whole experiment. The code used MDL Bol_aand_Genal SeanndGGnerallzzttinn (twiiiiiiionnnaraateeeeee for Representatioon Learning
experiments is available //tttt:////tthiee com/Piottkraanooskii
During the training phase, we jointly trained the encoder and the decoder parts for 200 epochs using cither the standard Gaussian prior of the traditional VIB objective function or our CDVIB objective functions. As (FDM17), we generated one latent sample per image during training and 12 samples during testing.
D.7 Numerical findings
Figure FigureBdisplay displays the training and test performance our model for wide range of parameters 8. It could be noticed that the best test accuracy with our Lossy CDVIB objective function is 65% (for 3 0.01), which is about 2.5% better than the best test accuracy for VIB (62.5% for 0.005). the case of Lossless CDVIB, the best achieved test accuracy is 64% for 1e 5.
0.8
-0.5
Boelhond
Azcuracy
0.6
-1.0
0.4
Suandard VID. train
-1.5
standard VID. train
VIB..
standard VIS. text
train
CDVIB.
lospy C2VI8 test
lasgy CDVIS, test lossioss CDVIB, train
lossless CDVIB, train
losoless CDVIS, test
CDVIB,
0.0
-2.
1e-7
1
1
1e-4 3e.3
2
10
1e-7
1e-8
1e.5
Je-4
10:3
10-2
Beta
(a) Accuracy.
(b) Lig-likelihood.
Figure 3: Test and train performances of our two-step prediction model trained using the standard VIB prior, the "lossless" CDVIB prior, and the "lossy" CDVIB prior, both with M 5. The plots show the average over runs and 95% bootstrap confidence intervals.
25

---

E
Proofs
E.1
General proof techniques
Most of our proofs contain two main steps.
Technically speaking, the first step uses Donsker- Varadhan's variational representation lemma, to change the measure. an example, in proof of Theorem first step gives
AE w [gen((., W)]
Drt.
882n My Es S.W
82n
FIx. (8',, gmnxa,, xtm, wi] u @en Q p ymn
log Em ym 8m Q y ym ) E" y Eiat (4 118
that changes the measure from
822 My S,W S,
p82n
Y (p x x",, w)]
62n Q("", 8 y'
This has particular meaning and intuition in our fixed-size compressibility approuch. Indeed, one can show that there exists proper sequence of compression books, with size [Sml & emR where
R = DEL 82n Pym.
82n Q y vm))
This means that by this step, wefix suitable sequence of compression books such that with high probability (that goes to as m - c0), one can find the sequence of predicted labels this codebook. Using Donsker- Varadhan's 's change of measure is shortcut this, previously explained in (SGRS22] Appendix B.1.] the context of hypothesis compression. Then, we consider the union bound over all elements of this codebook in the next step. For tail bounds, similar interpretations hold, but this time with variable-size compressibility notion, as shown in (S723) in the context of hypothesis compression.
The second step be seen bounding the generalization error for every element of such code- book. This step is achieved in quite diffcrent manners for the proofs of different results of the paper, follows in the coming sections. Note that in this step, the predicted labels have distributions ac- cording to the prior Q(Y", y: y", ,Y"),, rather than the one induced by the learning algorithm, ie.. p82n (Yrm Vm [ X W).
YIX.W
E.2
Proof of Theorem
E.2.1
Part
Proof. We first show that
inf Ex DKL (Ex x,w petn P (Ý, Y' x' q) 1 [1 22)
(19)
Q
Let Q' be the set of conditional priors Q' that can be written
Q' Y' Y') = IF Qi (v3". VJ
(20)
for some arbitrary distribution Q/- Here 22 and y 2n are the concatenations of the vectors (Y, Y') and (Y, Y'), respectively. It is casy to verify that Q C. Henee, by denoting P(Y, Y Y') =
Exxx.1 X.w
p622 v X'X,''', w)
we can write
inf Er DKY. (PY v Q)] LHS
Q
= inf YY DKL (P(Y, ( [')
Q
26

---

inf Q'eo;
2y By DKo (P(V3) "P y3 [0)]
inf Byzn Eg DKL P pm y1 yi yf² |S Qi 133",.31 v3 Y3
=1 (J: [J: )
This completes the proof of showing the equality in 2
Now, we proceed to prove the upper bound. Let Q be any fixed type-I symmetric conditional prior on (Y" m) given (Y , We show that
2 ym DEL Ex
pozn (8n, pm X X w) vIx,W
a)]
s [genwge []]
(21)
where Y y 82n and x" Xx, W Pxm wyye For ease of notation, denote
Pyn Pm Ex Xx, w
p02n v|x,w
(Y", y "x"""""".." .w)
where again X",, _",, W py Px" wiyn. We start the proof by applying the change of measure using Donsker- Varadhan's variational representation (step (a) below):
S ( W)]
Σ
(ox49) - 1 tessssii))
s.S. ".m.,."""mmmPP... P Pa.
pman v/x, (pm, X" W
A Σ (1 (,/4P)))))) - I ((see8)))
=By yin 8.m n.ld uullue. misiiui wik
122m Q(pm بل y yuu!
(a)
22 DKL 82n Ppn py silna ymu
e Enew - fmanzsi
log B Byy,, y
ymd
(22)
Now, we bound the second term. Consider the notation Di y2an and Di.; y for i e [n] and j e 21, Denote j == (ý=1) + 1. Furthermore, for every e [n], let K2 be a random variable that takes values uniformly over (1,2] The variables (K₂) assumed to be mutually independent. Let the complement variable K; be equal to 2 if K,j and 1 otherwise.
E 1ooaapy--aaa (mness) (epo)
logEy., Beeyy,ymmm ym pm pom-aaan " ym ymm
(0) log F p02n Q x mx) Uni
sT[m]
kn. gaxa axut
b/ E [T[]]
(200K, - to0k x (xg
po gaxza xynxx log E
Qig x2 Ex Unif((12)))
(b)
A/n e -A/n
A/n
& log
2
2
(23)
2n'
where (a) concluded by symmetry of and (b) by inequality g0 x 222 Combining this with yield
22
Eg,w(gen(S, W)] 5 2 DKz (1 (ppiipp Pmm
Q(P", p! x(m) + My
82n
A 2n
27

---

Letting
2nDKE
MY
PemnPnn,pe Pm
14 1 Q(pn smyr ymm)
completes the proof.
E.2.2
Part ii.
Proof: The proof of this proposition follows similarly proof of Theorem 5 (with 0), and avoided for brevity. Note that similar to Theorem 5 by noting that with probability at least (1 5). L(S', W) L(W) - (oooo(1/))((())) one can also establish a tail bound on gen(S, W).
>
E.3
Proof of Lemma
Proof.
Parts i. and ii, can easily verified numerically. To show Part iii., take derivative with respect
to x. This derivative, iee., log 2-x-w' log _ ), always non-negative for > x > x'. For Part iv.
242
the second partial derivative hp (2, 2²) with respect to is equal to ж[|=] (a+"")(2-3-3) which always positive for 0 & x Finally, show the convexity with respect both variables and x' simultancously. The Hessian of the function hn(r, x²) equals
H x[1=2] a+t X2-2"2)
(z+a
(24)
(xtta (2
We show the cigenvalues of this symmetric matrix is always non-negative, and hence H is positive semi- definite. This completes the proof. Solving
AI2 11
x1-=2
latx' 12 r x-x
= 0,
(25)
x7 [1= + 12-2"12-2-27
1o+F (2---12---'
reduces to solving
(A a)+
(A+a)
2² 0.
(26)
x01 - x)
2'(1 - x²)
x(1 2) (1 - 2²)
where a
The roots this equation are
2 x0 (1-x")
u(1-w) + x(1-x')
4a
a.
(27)
2
It straightforward to verify that both roots always non-negative, which completes the proof.
E.4
Proof of Theorem 3
Proof. We first show that
inf Ex,x' DKL X. Pi (8, (X,,,, w) = 1 (T; x2
(28)
QEQ
Let C' be the set of conditional priors Q' that can be written
Q' Q((x, xx,x Er 2m
2
x
(29)
for some arbitrary (and not necessarily symmetric distribution Q₁. Here 2 and 2m are concatenations of the vectors (Y, Y and (Y, Y'), respectively. It is easy verify that Qis C'g- Hence, by denoting
28

---

YY, Y') == B Fix,W (Y, X x m))
we can write
LHS
inf Ev,y' Qe
DKL. (((. Y x [0]
Ex, DKL P(Y. Y Y [0]
inf Q'Eli
inf Q'E
Eyzn ETT DKI. P
2m YT YT Y [Q)1
inf Byzn Ex DKL P 22 - Y y
BT
01
(77 |
x )
9
=1 T; g22 x
This completes the proof of showing the equality in 28
Now we proceed show the upper bound on ahp [W B., [(S) w)]) Let Q be any fixed type-ll symmetric conditional prior on (f pm given (Y", y").. We show that for v > 10.
whp (Bw[[B [B[[[(W]],Es.w [c(S.
& Eyn ym DKL Ss p82n (8", (P"; pi x wi] a)] log(n),
vxx.w
where y", ,",'" y ~ u and S S,S. ~ Ps.Wiy- For ease of notation, denote
pyn pmlyy = Rss,s,
vxx. (p", pmpx x x wi].
where S',S, W. ~ Ps Psr ym Ps.wjyn- We have
nh (wwlC(W),, Essw ((S,w)))
EnBpy. Ps.w IND (I, W))]
1 Σ (m==Pia) DJ
=nBs' S,W hD Epre F.x. (pmIxx,,.))
Σ 1m/
E Epa
Fix. (8
n
ie[m]
ie[m]
EnB
Psr Ps,
p0an
Fix. (8 pi aD | Σ 1x/=1/00
Σ 1
se(m]
& <DKL
82n Py Py 8m My
82n Q(r'n ym y(mn)
8. e nho Eneny Aogpar/a Eup 40cn8))
+ log Eyn y 8n,
(30)
Now, we compute the last term, which does not depend on W anymore. Suppose that Unif(2n) is distribution that picks uniformly n indices among indices 2n indices, i.e., the probability of each one
is (Tr))
We denote such indices by T (Ti....,TT)) Tx), and the corresponding distribution by Unif(2m).
For vector yn of length 2n, we denote the elements corresponding to indices picked by as y m ..... Y2n). We denote by T (Tf. Ta) the other remaining elements in 1....,2 2n
that are not picked by T. We denote 2) (9) ........ .T. Then,
nhn (# Eie(m) Po/ Mic(al (1x
logiE ynyy fn pm 82n Qi8 8
nho Eie(a #ypp Eie(a) 100, +0,,)
=log E Egga Sa T, 22 2 Unif(2n)
(31)
29

---

Let V be a random variable indicating V : Eie(2m] 1 (2)+9)) in the sequence 2)²". Then, we consider different cases for V and show that
nho + Eejne Org Eoetol (00, /or1))
Unif((2()
& n,
(32)
for n e 10. This completes the proof.
We use the following lemma repeatedly in the rest of the proof.
Lemma
Gal68 Exercise 5.8.al). For j 2 and - j > 1, where j, n 1.
& 8j(n -) j)
n
n e nhols/n) & V 2 - j)
n
(33)
Now,
L. I E [1,
(v=r))
uh (v=))
(V
2
(2))
(2m)
+
(27)
(a)
2
v VnV(2n - V)
+
(2m)
# VVi(n - j)( -j)(n - +
(8)
V-1
(2))
+ n/ (2n -V)
Σ
j(n
(V (V-
==1
V-1
2
1
VVV(22
V)
Σ
1
2m)
j(n -j)
j-1
2
1
/2n
V-1
Σ
()
+ -))
(2
(c)
2
2
n
Vn3
f=1
2
2 n1
(log(n - 1) + 0.58 + 1/(2n - 2))
2n
(d)
& n,
where (a) is deduced using Lemma upper bound on the Harmonic series, and (d) holds for > 2.
(b) is due to inequality Vey 2
1 1 + 2y
1 for any x, > 0, (c) by the
ii. If V E [n + 1, 2n 1]:
xholfin.V- (v²,)
(2))
j-V
=26 aV (v=m))
(3) (v=,) uhols/n
(nl
V n+1
vv
(0)
V2V
mh1(111/m)
max Ve(n+2,2n
1] v TV
(n+1)
VnV(2n-1)
TV7(m [](V j](n V
(6)
<2
(n 2)
+ v n2V V)
Σ
( + (v i)(n (V--))(-- 1 1
v )
π
j=V-n+1
30

---

[1
2)
1
m
(2n V)
n-
Σ
j(n -5
j-V -++
[1
2)
+
1
/nV (2n V)
n-1
Σ
(j n
7
1177
jーV-
n1 2)
2
n1
π
[1 2)
n
(log(n 1) 0.58 1/(2n- -2) 2))
7
(d) 12
where (a) is deduced using Lemma 2 (b) is due to inequality Jay I for any z, and by verifying the first term for V numerically, (c) by the upper bound the Harmonic series, and (d) holds for n > 10.
iii. If V 2n: In this case E ーn (V (+5) =1
E.5
Proof of Theorem 4
Let Q be a conditional prior over 2 given x2n, y22n and We E We. which is symmetric in the following Q (M>(1)--..> (*((2)) (=1,,. 22,), (Vi,-.., V2n), the remains the same for all permutations T: [2n] [2n] that preserves the label, i.e. vx(1)= Vs- Then, we show that for the K K-classification learning task,
sense:
2B + K + 2
i.. [Se W)] & 2
t
n
where
B= inf If Pew. Ps PKL P (U" "
xm We) (2)]
and the infimum is over all Pw.s such that for W (We, Wa).
E E Pi., s [gen(S W) gen(S, w)] & c.
Proof. We prove the theorem for W W and The general result follows by the distortion criterion and applying the theorem on gen(S, W). We start the proof similar to the proof of Theorem | but with a different expansion of the probability distribution.
ABs.w Agenw, W)]
(1 - -1 - Fochraa)
Σ (1 (11:4087)
=E S.s S,St M.S.W.UU.UUE u "..u"", fn Ps.Ww
st(m)
<DKL Ps. p82n U|x,W, (U"h " x", Wo) Ps. Q(U", 1"M,,,
2 (2 (ma00))))) + log loggs,e Sr, W."",, ur yn pn Pgr Ps.wv3
(34)
where
4 = p=p32p p32n
U|x,W, (U", ",",""""",," P80n Plu.. ""00" ,a),
1/2 = QUU", " W)p22n yio,wa 18" um airii""""" " Wa).
Now, bound the last term. Let
Pa (r" 1s, w) ((00))))(00__)))..))))) petnn (rm, "m Tnh Wa)] (35)
31

---

Then, the last term in (34) can be written as
log E S.S W,Y" y -P Pa. P8 S 1s,ss..) Eieto (Tor/ Po
Note that since have PrI Priu..
be easily verified that the distribution Po nr, y"s,, S" w) symmetric with respect to all permutations ı that preserve the labels of Y.
For each s, let f: [n] [n], E [T]] and k: [m]] [n]. i E [r]] be permutations of indices of 8 and s' respectively, where y, = Ygg for & T and y, * Ve. for > T, and where T equals n - 3 lpp - P 111-
Here, Pa. and fa are empirical distributions of Y in and 8', respectively. We denote (0" "00) ) by g² x where Vi [m]. 01, and 02,4 Di-
Consider the binary random variable K, taking value as (2, ft) or (1, k2) with probability 1/2 (independent of other # i). Denote the complementary choice as KÝ i.c., K; = (2, f.) iff K; (1,
Then, due the particular symmetry Q, and by using shorthand notation
w). P = Ps Ps,w Pa (nn Smm " (')
we have
A Lie(fn 10% #BL.ke
118 (2..))))1))
S.S.W
e
T
1xy #1 -1 F2
=,, ".S.r.
i-1
T=++1
( ) or, (
X(n-7)
<B
3.5 W.W.
( -20,, (8x9))
Mm-Ti
= E S,S' w.y.xn Km Unif(
N/n + A/nn T
A(n-2)
2
22 Mn-21
&.s, -.r.
(a) 22
④ 1is Agrl1
~ PPr
x
K
+
2
312
<exp
+
+
2n
2
2n
2x2
K
+
< exp
n
where (a) is deduced from Lemma conditioned that A/n < 1.36.
Now, combining this with 34. and letting À X /n(2B K + 2)/4, the expectation of generaliza- tion crror upper bounded by
Bg.w(gen(S w)] 2B +
2
n
(2B + K +2
2
7
if TT> 1.36. Note that if 1.36
X*
(28+ +2) then
2B + K 2)
4(A 1(**n))>* 1.
Since generalization error is always bounded by hence, this bound always holds.
32

---

Lemma 3. Suppose that y and Y are 2n i...d instances of [K].
Then, if A/ne < 0.68, then,
log Eyn [ Alrr B Bym
K+2 + 6X2
The lemma is proved in Appendix F.9 usiig results of Dev83
E.6 Proof of Theorem 5
Let Q be any fixed symmetric prior on (Y",, f that could depend on (X", y", x y")) We show that for any e R and ó e B with probability at least (1 6) over choices of S and S', we have that aww-olee(S... W)] upper bounded by
F|x,W (8n, 8mixa, X'm, (1//2) log(v88/6)) + +c, (36)
Bw Pwis
DxL.
log (2/6) + inf
2n
(2n - 1)/4
where the infimum is over all Pwis that satisfy
E Eriss Pais (c(s',w), E(S.W)) w. ((S.
- E/2.
(37)
Proof. Consider distribution Pwis that satisfies 37
Denote X
2n-1 4-
and
(Yn, ÿm X", X wi) (2) llog( (8r//8)
W Pinss
DKL
p82n YIx,
A(S, Q)
c.
Furthermore, we use the shorthand notations P == pM2n Fix. (8 xm xxm 18). Then,
PS 0
Ew Ew- [gen(S,
W)]
1og(2/8)
A(S.))))
2n
(a)
(5.8))
Ew Pwis
LIS', W) L(s, A(S. +
A *C(IS', W) ((S, )²1
P
(8,8)~w00
Ew-Pwis
> > Q)² +
(c)
(8,8)))EE
E Ewr-PWis
X X"(ES'' wy 2(s) -
>>*((S Q)3)
+//
11 1 (-1x-4811 -
>*B 8n 8m Paiis
3 >>*((S
+ 8/2
DKL (Piriso P
& ((
(38)
+ log Bg Bgn, expp (*
L(S, - x A(S, Q)?
+ 8/2
(c)
P Pssss
log Eg BegEpn pm
>
18 A 11z08/ - + log((/6)
log Eg,s, 8 Pm.pm-PpPoo
c
+ 8/2
(f)
6,
(39)
33

---

where (a) holds by Hoeffding inequality and using the fact that for arbitrary random variables U, V and constants a, b E R, IP(U + > a + b) & IP(U > a) + P(V > b), (b) by applying the Jensen inequality on the convex function f(z) x², (c) by using the distortion function (37) and since the loss is bounded by one, (d) by using the Saakkkr-aaaaaaa'ss variational representation lemma, (e) shown in the following.
and (f) by Markov inequality.
Hence, remains show step (e). this end, it sufficient upper bound
x* **(A -o0ssp0--eeeee
log R s,5", Ses PsPS
by log(von) /2n). Note that this terms equals
A# (# ( Eiefml (1 (17488)) -2 =
log l8 y ym y pm Prean
where Qi is equal Exxajyn Pxmprm
Q(Pm, pimli y x ymm]. Now.
Eyn ym ("n,
(0)
x (etm)
1 toxxe m xcg.ee)
E6 2g KK- Q (9) 3 Unif(1.2)@m
x 1 sm[os]
(100K, 1wo xes
=I8 B goxxx p gaxx) ~
(b)
22,
(40)
where (a) is concluded by symmetry of Q₁ and (b) is deduced since
1
Σ
1 (1 Deg.)))
72 iE[m]
h /-suugaausian process and hence
Mie(w)) (Z10K) -1 xxgg w))) (001210)))))))1)11) & vnn
Eg Unif_nif(122)0 e
duc to Waily Theorem 2.6.IV... This completes the proof.
E.7 Proof of Theorem 6
Let Q he any fixed symmetric prior on (Ý*", y-hn) that could depend on (X", Y x y²)). Then, for any 8 IR ,e show that with probability at least 5) choice of (S,S", W) Ps: Ps.w.
nho
(),ss,,,,45 (), <DKL
p PPIX (8" 8"1X" x wy (a) + log(n/0).
Proof. The proof a combination of proofs of Theorems and theorem A(S, S", W).
Denote the RHS of the bound
34

---

First, note that nhD
(3,
Σ t
=nhn
Fix pp
( w)
1 1r18813
Byn~ pen FIX, (Fxpx,,w)
sc[m]
se(n]
EnBB y ( ymm.a
ND
Σ
1 Σ (x
< <DKL. FIx,W (P') an x xmm w) Qe8 yim x y xm ym)
daa )لnل ب, # )n( (1.:)8))
+ log Bug pmm p y x ymm)
(41)
Hence,
Ps.s w (nhD ((S", W), ((S" ((), > A(5,S',w)
(a)
nho Eier Poparp
ECet Eetall (mg08))) > log(n/8))
ym
log BugBEnn y
(b)
nho (M Ener 1m/ Eeeoo (pg08s))
Py ym ym
log Byn 8m
e anp Exeuol Aypppp Evjoal (1329))) + log(11()
log Ex yie p pmap
(c)
66
where (a) follows by (41). (b) holds since
log Ey y y pm mm--pp u nho Enetan tm/pe/y Eeer towes)) log(n))
by the proof of Theorem and (c) derived using Markov inequality. This completes the proof.
E.8 Proof of Theorem 7
Let Q be a type-lll symmetric conditional prior over 2 given 22" 222n and We E We. namely, (V1, - V2n,,, w) remains the same for all permutations :: [2m] [2m] that preserves the label, i.e., Ma(s)
Q ((.
for i E [rz]. Then, for any À R+, we show that for K- K-classification learning task, with probability at least (1 8) over (S, , W) Ps.
L(s', w) W) W) & DKL p (U", " x", x"m, Wo) Wa) Q) + (K + 2)/2 + log(1/8) + n
2x
The poof of the second part follows trivially using Hoeffding's 's inequality.
Proof. Note that whenever A/n > 1.36, the bound trivially holds. Hence, assume that A/n < 1.36. Denote the RHS of the bound of Part i. A(S, S', W). We use the shorthand notation = poen (U"h """ x", We) and p2 = p82n (F ymu Thm U|x,w.
the Wa).
Ylu.w,
Note that (S, W) Ps.... Now.
Ps.s.w (R(S'WW) W) L(S, A(S,S", ((S, W))
Σ (10:4833 1ocaraa) AA(S,Ss
=Ps.st.W
AEMipz
[t[n]
(0) P...
DKL P1P2 Qp2
(42)
35

---

+ log Qp2 exp (>(2(5', v'M) L(S, L(S, xn) AA(S,S' m
e Eaclall- (x/48/)) - (
& Pssst.
log Ears
e (eew - log Ep Ps, Qm2
(13 + +lgg(115)
(d) 6
(43)
where (a) by using the Varadhan' variational representation lemma, (6) since due to proof of Theorem (in Appendix E.5
e (0020)))
21 +
+ 2
log E Er Ps,w Qp2
2
when A/n 1.36, and (d) by Markov inequality. This completes the proof.
E.9 Proof of Lemma
Proof. The proof takes its main elements from Dev83 V1, Y2. ... Yi, Yg.... be i.i.d. realizations of Y E [K]. Denote (y) Pk. for k [K] Let N and N' be two independent Poisson random variables with mean n. Let and U,, i e [K]. be number of occurrences of value k among y|m] and I''], respectively. Moreover, let V; and V. [K]. be number of occurrences of value among y-lM] and y|'N",, respectively. As shown [ev833 Vi...., VK and Vi...., V are independent Poisson random variables with means B[V]] = E [V] rPp,, for k E [K]. In addition, (U1....,Uk and (U,...., Ukk are two independent multinomial (n. P........ PP. random vectors. Then,
E Al A Aym
(2: 10, 10-v--0 (V-VV-00--2)) (2: IV VV-V
(M 10 U0-
E 22 (E (V-
24 (x
U0 vo v1
(Σ [v--
-
B 23 (V- (7-
(44)
where (a) is due to Cauchy-Schwarz inequality.
Recall that for random variable X having the Poisson distribution with mean v, we have IR 1x Now,
ale -1)
23
(IV- N
ml)
22 m-l
(IN
(
e
= e
E
(N-n)
22 N))
B
22 (N'
(n-N')
< 16
22 2n(e
2n
-1-22)
(45)
and
K
22 ( vi-v
23 (V/-VV))
+e - (V:-
E
ap. 23 -146 2-11
22 K n(e 116
(46)
36

---

Combining 44
and 45 yield
log A lss b
(a)
K +
28
2A
1 6 "
23
22
+
e
1
2
71
2
2
K + 2
1
2A
2A
+
+
2
1.2
12
K 2
6x²
where (a) holds due inequalities that be verified numerically: for < 1.36, e <1+ f2 and ii) for i < 1.3, to
1 + 12 x²
37


Reviews:
[{"review_id": "dHuzgjykMT", "reviewer": "Reviewer_2eZy", "summary": "This submission considers supervised learning problems and derives two types of generalization gap bounds. The first type states that generalization gap can be upper bounded by approximately $\\sqrt{\\mathrm{KL}(P || Q) / n}$, where $P$ is the average (wrt data and training stochasticity) of predicted label distribution on $n$ training examples and $n$ test examples conditioned on the labels of the $2n$ examples, while $Q$ is a fixed **symmetric** prior distribution for predicted labels on $2n$ examples given $2n$ labels. $Q$ is symmetric when $Q(\\hat{y_1},\\ldots,\\hat{y_{2n}} | y_1,\\ldots,y_{2n}) = Q(\\hat{y_{\\pi(1)}},\\ldots,\\hat{y_{\\pi(2n)}} | y_{\\pi(1)},\\ldots,y_{\\pi(2n)})$ for any permutation $\\pi$. In a sense, the symmetricity means that $Q$ puts a distribution on $\\hat{\\mathcal{Y}}^{2n}$ given $y_1,\\ldots,y_{2n}$ without \"knowing\" which $n$ of the $2n$ examples belong to the training set.\n\nThe second type of generalization bounds are designed for classifiers which have a representation part (an encoder) and a classification head. The main term in these type of bounds is also of the form $\\sqrt{\\mathrm{KL}(P || Q) / n}$, but where representations play the role of predicted labels. Again there are $n$ training, $n$ testing examples, and a symmetric prior $Q$ but now over representations. Notably, this type of bounds do not depend on the classification head, they only depend on the encoder.\n\nFor both type of generalization bounds, both in-expectation and in-probability bounds are derived. Furthermore, the authors derive tighter bounds where the mismatch between empirical and population risks is measured by a convex function $h:[0,1] \\times [0,1] \\rightarrow [0,2]$ instead of the $|x-y|$ function. Finally, to avoid KL divergence becoming infinite when working with continuous labels or continuous representations, the authors derive bounds where one seeks a \"quantized\" algorithm that has a similar generalization gap but non-infinite KL divergence.\n\n\n\n\n\n\n", "questions": "1. Lines 45-48: What exact result is being referred here? The mutual information between two variables cannot be seen directly as some sort of description length (just consider two variables with 0 mutual information). \n2. Section 2.1 Compressibility framework: The concepts introduced in this section are not used in the main text (specifically the block quantities). I recommend moving this subsection to Appendix C. This way it becomes easier to read the main text and the already complicated notation does not become more complicated. The only idea that I recommend keeping from this section is that if one can encode $\\hat{Y}^{2n}$ with short code on average, then one should expect good generalization. Similarly, the sentence of lines 209-211 should be moved too.\n3. Theorem 1: $\\text{gen}(S,W)$ should be defined.\n4. Equation (3): The training algorithm can act differently on training examples with different indices. It is not necessarily true that the RHS of eq. (3) can be written as $n$ times the quantity for a single example.\n5. Theorem 2: $\\mathcal{L}(W)$ and $\\hat{\\mathcal{L}}(S,W)$ should be defined.\n6. Line 295: $\\boldsymbol{Q}$ instead of $P$ for the prior.\n7. Theorem 4: Why is the idea of a posterior $Q$ introduced here, can't it be just $P_{W|S}$ and $P_{\\hat{W}|S}$? As it has been done before this point, the letter $Q$ would be good to use only for priors. In the equation after line 311, it should be $\\hat{W} \\sim P_{\\hat{W}|S}$ instead of $\\hat{W} \\sim Q$. Also, in eq. (6) it would be good to write it as a difference of two expectations. In that case it will be clear what distributions $W$ and $\\hat{W}$ follow.\n8. Line 802: It should be $\\boldsymbol{Q}$ (the symmetric prior) instead of $Q$ (the posterior over $W$). Similarly in all $\\Delta(S,Q)$ terms. Also $\\Delta(S,Q)$ should be $\\Delta(S,S',Q)$ as it depends on $S'$ too.\n9. Line 350: Why is the property of preserving labeling important for the permutation $\\pi$ in the definition of a symmetric prior? I recommend adding more details of the transition at line 839 where the symmetricity of $\\boldsymbol{Q}$ is used. \n10. Line 831-832, \"it can be easily verified that this distribution is symmetric\": Which distribution is referred here?\n11. Line 833: It should be $k : [n] \\rightarrow [n]$.\n12. Line 834: $||\\hat{p_s} - \\hat{p_{s'}}||_1 \\in [0, 2]$, so $T$ can become negative. It should be divided by 2.\n13. Lines 833-834: The construction of the permutation $k$ is not always possible. It might not be possible to map the *first* $T$ samples in $Y$ to another $T$ equal samples in $Y'$.\n14. The technique of taking an infimum over close enough \"quantized\" algorithms is a step that can be applied no matter whether the bound depends on joint compressibility or $\\hat{I}(X; U)$ or something else. Therefore, I feel that one should not claim advantage over other results in terms of being applicable also to continuous variables when the advantage is a result of applying this general technique (not due to something inherent to the approach).\n15. It would be good to have a small discussion on the fact that representation learning has many goals (e.g., learning representations that are \"useful\" for many tasks). Learning representations that guarantee small generalization gap for a *given* task is not of high importance in common representation learning settings. I don't think that one would be happy to find out that after a heavy pretraining round with a pretraining task $Y$ the network learned a representation $R=\\phi(X)$ such that $R=g(Y)$ for some function $g$. \n", "limitations": "The limitations are addressed adequately.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "**Strength #1: Relevance.** Understanding how some properties of learned representations affect generalization is an important and highly relevant direction for the NeurIPS community. The authors present a good summary of the criticism of information-bottleneck compression ideas in explaining generalization and propose to consider instead the joint compressibility of training and test representations.\n\n**Strength #2: Originality.** To my best knowledge, the bounds that depend on representation complexity (results of Section 3) are novel. In some sense, these results suggest a new type of information bottleneck for representation learning.\n\n**Weaker strength: Soundness.** The results of this submission are sound as far as I checked. However, in some places I couldn't follow the proofs very carefully as some steps were not detailed enough or the notation was confusing (please see my comments below).\n", "weaknesses": "**Weakness #1: Hard to judge the significance.** While the overall direction of obtaining generalization guarantees via joint compressibility is interesting and this submission makes a good step towards exploring that direction, it is hard to judge how significant are the main results of Section 3.\n- [Estimation] I don't see a good way of estimating the bound of Theorem 5. In the case of continuous representations, how can one take an infimum over learning algorithms that have similar generalization gap?\n- [Experiments] The experiments do not help to judge whether the KL term in the bound can be successfully used as a regularization.\n\t* [E1] Line 608, \"As in the VIB approach, inevitably, we only restrict the optimization to the training set.\": This seems to go against the spirit of the approach employed throughout the paper. Namely, as I understand the symmetricity of $\\boldsymbol{Q}$ can be interpreted as $\\boldsymbol{Q}$ not being aware of the train-test set split. Forcing the encoder to be close to such a distribution $\\boldsymbol{Q}$ forces the encoder to behave similarly for seen and unseen examples. From this one gets a generalization guarantee.\n\t- [E2] Even if one splits an original training set into a new training set and a ghost set to follow the logic of the main text, the KL regularization term will probably be fitted by \"cheating\", in the sense that representations of the new training set and ghost set examples will be different from those of unseen examples. The nature of ghost examples (to be not used during the training) makes it impossible to use the KL divergence term of Theorem 5 as a regularization.\n\t* [E3] Lines 612-617: $\\boldsymbol{Q}$ will not be symmetric in this construction, as it is constructed using statistics of *training data*. Consequently, the KL divergence can become optimistically small (when training examples are \"memorized\").\n\t- [E4] Lines 667-669, \"It can be observed that our scheme outperforms VIB in terms of both generalization error and population risk, for all values of the Lagrange multiplier $\\beta$\": Since the two objectives are different one should not compare then for a fixed $\\beta$. Instead, we can consider tuning $\\beta$ for each of them independently to minimize test error. We see that in that case there is no significant difference between the two approaches. Similarly, there is no significant difference if we compare generalization gaps for a fixed level of small test error.\n- [Applications] The submission would benefit significantly from an analytical evaluation/bounding of the bound of Theorem 5 in some tractable settings (maybe a two-layer neural network on Gaussian data). This would allow to see if the bound is powerful enough to produce meaningful results in some settings.\n\n**Weakness #2: Clarity & Presentation.** This submission would benefit from improvements in terms of clarity and presentation. It was hard for me to read and understand the details. There are many small mistakes, the notation is cumbersome, and some parts of derivations are not detailed enough. Please see more detailed comments and suggestions below.\n\n**Weakness #3: Missing important related work.** This submission does not cite well the literature of information-theoretic generalization bounds initiated by the works Russo and Zou [1] and Xu and Raginsky [2], and developed further by many others. This line of work is relevant for multiple reasons.\n1. The general technique of deriving bounds in this work and in the mentioned line of work is the same (using Donsker-Varadhan inequality and bounding a cumulant-generating function).\n2. The general idea of measuring how different a learned function acts on training and testing examples has been used in many follow-ups on [3].\n3. The idea of symmetric priors appears in [4] under the name \"almost exchangeable data-dependent priors\". In their bound there is also a term of the form $\\mathrm{KL}(P||Q)$, where $P$ is the output distribution (over hypotheses) after training on $n$ training examples, while $Q$ is a symmetric prior over hypotheses given $2n$ examples. **Important:** when considering in-expectation bounds, the optimal $Q$ is the average of output distributions over all possible $2^n$ training/test splits. The KL divergence for this optimal prior becomes the conditional mutual information (CMI) $I(W; J | \\tilde{Z}_0, \\tilde{Z}_1)$, where $J \\sim \\mathrm{Uniform}\\\\{0,1\\\\}^n$ is the training-test split, $W$ is the output of the learning algorithm when splitting with $J$, and $\\tilde{Z}_0$ and $\\tilde{Z}_1$ are the $n$ training and $n$ testing examples respectively.\n4. While in works [2], [3], and [4] the bounds depend on some kind of information captured by the output of a learning algorithm (i.e., the output hypothesis), in [5] there are bounds that measure information in *predicted labels* in the random subsample setting of Steinke and Zakynthinou [3]. Given the important part of the last point, the result of Theorem 1 can be seen as an f-CMI bound written differently. The only minor difference is that in f-CMI bounds there is conditioning on $\\tilde{Z}_0$ and $\\tilde{Z}_1$ instead of $\\tilde{Y}_0$ and $\\tilde{Y}_1$ (i.e., only the label parts), but it is easy to see that the proof does not use the input parts ($\\tilde{X}_0$ and $\\tilde{X}_1$).\n5. It is also worth to mention that CMI (or f-CMI or e-CMI) bounds are usually improved by measuring information with individual pairs separately (variations of the technique of Bu et al. [6]), and by conditioning on an individual pair of train/test examples (e.g., [7]). These two techniques together produce f-CMI bounds of form $\\sum_{i=1}^n \\sqrt{I(\\hat{Y_{0,i}}, \\hat{Y_{1,i}}; J_i | Y_{0,i}, Y_{1,i})}$ that can be much tighter than the bound of Theorem 1 (the equivalent of the f-CMI bound when measuring information in all predictions at once).\n\n\n**References**\n\n[1] D. Russo and J. Zou. How much does your data exploration overfit? controlling bias via information usage. IEEE Transactions on Information Theory, 2019.\n\n[2] A. Xu and M. Raginsky. Information-theoretic analysis of generalization capability of learning algorithms. NeurIPS 2017.\n\n[3] T. Steinke and L. Zakynthinou. Reasoning About Generalization via Conditional Mutual Information. COLT 2020.\n\n[4] P. Grunwald, T. Steinke, L. Zakynthinou. Pac-bayes, Mac-bayes and conditional mutual information: Fast rate bounds that handle general VC classes. COLT 2021.\n\n[5] H. Harutyunyan, M. Raginsky, GV. Steeg, and A. Galstyan. Information-theoretic generalization bounds for black-box learning algorithms. NeurIPS 2021.\n\n[6] Y. Bu, S. Zou, and V. V. Veeravalli. Tightening mutual information-based bounds on generalization error. IEEE Journal on Selected Areas in Information Theory, 2020.\n\n[7] B. Rodríguez-Gálvez, G. Bassi, R. Thobaben, and M. Skoglund. On random subset generalization error bounds and the stochastic gradient Langevin dynamics algorithm. IEEE ITW 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed investigation of the paper, their interest, and their constructive comments.\n\n**Weakness #1:** As mentioned by the reviewer, our work is the first theoretical work that characterizes $gen(S,W)$ in terms of the complexity of latent variables, achieved by considerably extending the framework of [BL03] to characterize the MDL of predictions/latent variables. In Sections 2 and 3, we address \"conceptually\" several existing challenges and criticisms about measuring the MDL using mutual information, in particular by implicitly taking into account the encoder's simplicity and the geometric compression. Furthermore, we demonstrated some practical benefits of our result and the role of \"data-dependent\" priors, which we believe can be exploited further in future works.\n\n- Estimation: Firstly, the bound in Theorem 5 holds for **any** choice of $P_{\\hat{W}_e|S}$ satisfying (7) and taking the infimum to achieve a \"valid bound\" is not needed. Thus, any simple technique that adds noise/quantization to parameters or models can be considered, as described in lines 381-388, which is especially useful for deterministic encoders. Besides these \"blind\" approaches, an interesting direction could be to leverage a combination of Mine (arXiv:1801.04062) and \"SFRL\" (arXiv:1801.04062), similar to \"Rate-Distortion via Constrained Estimated Mutual Information Minimization\" (ISIT2023), to intuitively \"learn\" a \"semi-optimal\" choice of \"noise-injection\" using another NN. Nonetheless, these approaches would need to be (non-trivially) adapted to our setup. We add these discussions as future directions.\n\n- Experiments: Regarding [E1-E3], we do agree that to \"correctly\" use the KL-divergence term of Theorem 5 as a regularizer and to satisfy the symmetry condition of the prior, one needs a \"fresh\" test mini-batch in each iteration, which is impractical. To partially address this concern, we made several changes in our experiments and by considering the best choice of $\\beta$ for each algorithm ([E4]), indeed now we observe a better improvement of about 3\\% upon VIB. Please refer to the response to all reviewers for the changes: moving-average and multiple (per label) priors and the CNN choice.\n\n- Application: We agree that analytically evaluating the bound for a two-layer NN will be a significant complement to our work, which in our opinion merits a separate publication. As for the current state, we believe, we made significant theoretical and experimental contributions that show the importance of our work.\n\n**Weakness #2:** Thanks for the provided feedback in the Questions section, addressed below. We will proofread the paper and the calculations carefully.\n\n**Weakness #3:** Our motivation was to understand the \"complexity\" of the predictions/latent variables and their connection to $gen(S,W)$, as \"assumed\" in IB. This is conceptually and practically different than results in terms of complexity of $W$. To study this, we built a framework based on the combinatorical approach of [BL03]. The proofs using Donsker-Varadhan's lemma appeared later as an abstraction of our initial proofs. \n\nWe missed the connection with CMI-based works as the original CMI-based work was mainly focused on the complexity of $W$. We sincerely thank the reviewer for bringing our attention to them, in particular the f-CMI-based follow-ups. We will make the connection between the CMI-based works (and IT-based bounds and their proof techniques) and ours, which also highlights the connection between [BL03] and the CMI bounds, which had not been elaborated in CMI-based works, AFAWK. For further discussions, please see the parts **Regarding CMI** and **Regarding almost exchangeable priors** in Reviewer Lcin's response.\n\n**Questions**\n\n1.Covering lemma in a sense explained in \"Regarding the presentation\" part in Reviewer FoJr's answer. This will be clarified.\n \n2.This section is provided to give an intuition about *compressibility* nature of MDL and our results and also how IT terms arise by combining [BL03] and block-coding. However, we agree it may be hard to follow. We will rephrase/reduce this section and keep only the needed intuitions in the main text.\n\n3, 5,6, 8, 11. Thanks, will be added/corrected.\n\n4.Per our understanding, the question is about the first term in (3) which is related to $S$. If so, we agree and the text already reflects this by considering $X\\sim \\hat{\\mu}_{X|S}$ in (3) and by denoting empirical MI in line 218 as $\\hat{I}(X;\\hat{Y})$. \n\n7.Thanks. Will be adapted and corrected. Using another distribution is to emphasize that the expectation is not needed to necessarily be taken w.r.t. $P_{W|S}$ induced by learning algorithm; as used e.g. in arXiv:1707.09564.\n \n9.Thanks, details of the proof will be added. For the intuition, please refer to \"Regarding the presentation\" part in Reviewer FoJr's answer. Just please note a typo at line 350 and its correct version at line 820.\n\n10.We meant $P_{\\mathbf{Q}}$ in (31). Will be rephrased. \n\n12.Thanks. Indeed $T=n-\\frac{n}{2}\\|\\hat{p_s}-\\hat{p_{s'}}\\|$, which slightly improves the bound.\n\n13.Thanks for such a precise verification! We implicitly assumed this holds w.l.o.g. since the proof does not rely on the position of these indices, but to be more precise, we will consider another permutation $f\\colon [n] \\to [n]$ s.t. $Y_{f_i}=Y_{k_i}^{'}$, $i\\in[T]$ (for simplicity, the dependence of $f$ on vectors $(Y^n,Y^{'n})$ are dropped in the notation.). The rest of the proof follows similarly as before by replacing $Y_i$ by $Y_{f_i}$ and $\\hat{Y_{2,i}}$ by $\\hat{Y_{2,f_i}}$.\n\n14.We agree and this will be precised to avoid confusion. As mentioned, the idea comes from the RD theory that is indeed applied to MI. Here, it is leveraged in particular to explain the experimentally-observed \"geometrical compression\" concept that was \"perceived\" to be different from IT compression.\n\n15.Thanks. We add the discussion that we believe can be partially addressed by our work."}, {"review_id": "SJapC8g4eE", "reviewer": "Reviewer_FoJr", "summary": "**Post-rebuttal**\n\nI thank the authors for their response and have raised my score to an accept.\n\n\nUnderstanding the generalization properties of modern machine learning algorithms is one of the key challenges in statistical learning theory. Focusing on the classification setup, this paper first studies the generalization error in terms of the compressibility of the predicted labels using tools from rate distortion theory. The proposed bounds feature a new KL divergence term that takes into account the structure and \"simplicity\" of the algorithm. The authors then extend the framework to give a generalization bound for information bottleneck-type representation learning in terms of the compressibility of the latent variable. The authors also empirically demonstrate a practical benefit of their theoretical results for the information bottleneck.", "questions": "* What is a high-level intuition for variable-size compressibility for the tail bounds? Likewise, for block covering does compressing multiple instances simultaneously allow for smaller distortion levels? It would definitely help the reader if some of the high-level proof ideas are laid out more clearly either in the main text or supplementary.", "limitations": "I do not foresee any potential negative societal impact of this work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "In terms of originality, the generalization guarantee in terms of the compressibility of the representation that takes into account the complexity and structure of the encoder class appear novel. Also unlike existing mutual information-based bounds, the new bounds are not vacuous for deterministic algorithms. The work builds on prior work on PAC-MDL bounds from Blum and Langford (2003). The latter used a bits-back coding argument, while the tools developed in this paper rely on rate distortion theory and block coding arguments building on prior work [SGRS22] and [SZ23].\n\nThe authors also demonstrate a practical benefit of their theoretical results by comparing the performance of the vanilla VIB and a `\"category-dependent\" version, with the latter performing better in terms of generalization error and population risk.\n\nOverall, the writing is clear though the presentation can be improved in certain parts.", "weaknesses": "The presentation in the main text can be improved in certain parts, e.g., giving more intuition for the proof techniques; see below. Also, in its current form, the paper seems to end abruptly. A separate Conclusions section summarizing the main contributions along with scope for future work / citing open problems can be very useful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their interest in our work and their constructive comments. We will apply them to improve the quality of our work.\n\n**Regarding the presentation:** Thanks for all suggestions related to the presentation of our work. We will definitely take them into account for the next version of our paper. We will also focus on giving more intuition about the concepts and proof techniques. In particular, we will improve Section 2.1 and explain more clearly how starting from a combinatorical approach of [BL03], we established an information-theoretic framework using the \"block-coding\" technique. This technique, combined with lossy compression, can better explain the concept of \"geometrical compression\". Furthermore, we will expand the discussion about the connection between the block-coding technique and the Donsker-Varadhan's variation representation lemma that is used in the proofs. To this end, we will explain better also the \"Covering Lemma\" in information theory. This also helps to better explain the intuition behind IB (lines 45-49): Consider $n$ i.i.d. realizations $(X_i,U_i),i\\in[n]$ of a discrete input $X \\sim P_X$ and its corresponding discrete latent variable $U \\sim P_{U|X}$. The covering lemma says for large enough $n$ there exists roughly $l_n\\approx e^{nI(U;X)}$ vectors $\\tilde{u}^n(j),j\\in[l_n]$ such that with high probability for every $(X^n,U^n)$, $\\exists j\\in[l_n]$ such that the empirical distributions of $(X^n,U^n)$ and $(X^n,\\tilde{u}^n(j))$ are close enough (and close to $P_X P_{U|X}$). Hence, loosely speaking, if block coding were allowed, an \"equivalent\" version of the latent variable could be described with roughly $I(U;X)$ nats.\n\nTo give more intuition about the proof techniques, we will discuss more the intuition behind the choices of our \"data-dependent\" priors, which is new in this context. As an example, we will explain in Section 2 that in the simplest form inspired by [BL03], intuitively, we consider independent \"shuffling\" of $n$ pairs of $((Y_{i,1},\\hat{Y_{i,1}}),(Y_{i,2},\\hat{Y_{i,2}}))$ in a way that it becomes fully ambiguous whether any pair belongs to a training or test (ghost training) dataset. For this result, in fact, only a \"partial\" symmetry suffices, since considering a vector of $(Y^{n\\times 2},\\hat{Y}^{n,2})$, the elements $(Y_{i,1},\\hat{Y_{i,1}})$ may be only swapped by $(Y_{i,2},\\hat{Y_{i,2}})$. However, in Theorem 2, we consider shuffling the whole super-sample to assign $n$ instances to the training set and the remaining $n$ instances to the ghost training set. This requires a \"complete symmetry\" as described in lines 201-206. The idea of Section 2, however, is not directly applicable to Section 3, as the decoder part also depends on data, and hence by shuffling only pairs $((Y_{i,1},U_{i,1}),(Y_{i,2},U_{i,2}))$, $P_{W|S}$ and hence $P_{\\hat{Y}|W_d,U}$ may change also. For this reason, we keep the training and test sets unchanged (hence, $P_{W|S}$ remains also unchanged) and only \"shuffle\" the assigned latent variables (distributed according to $\\mathbf{Q}$) to a pair of test and data samples having the same label. This is the intuition behind the symmetry notion used in Section 3.\n\nWe will add a conclusion to summarize the main questions addressed by our work and the future directions. We believe that our framework could be useful to study theoretically or experimentally different architectures of neural networks (e.g., two-layer FCN vs CNN) in order to understand how and why some of them can generate \"better\" representations. Another interesting direction would be to understand how to learn a \"semi-optimal\" lossy version of the latent variables and how to estimate the corresponding KL-divergence term using the recent advances in Rate-distortion estimation. Finally, while we performed some convincing experiments which partially showcase the practical implications of our results, we believe that our framework can be exploited further. For example, one may introduce more suitable priors which can better account for the \"simplicity of the encoder\" or the dependency of all latent variables $U^n$ (as induced by the encoder).\n\n**Regarding variable-size compressibility:**  Perhaps the main idea behind variable-size compressibility could be intuitively better explained by its contrast to the \"fixed-size\" compressibility: in the latter, one considers a fixed-size codebook (as defined in the paragraph starting from line 187) and then for \"quantization\" chooses any suitable vector $\\hat{\\mathbf{y}}[j]$. Technically, since in the proof we apply the union bound over the vectors of the codebook, the result of this approach would depend on the \"fixed-size\" length of the codebook (i.e., $\\lim_{m\\to \\infty} \\frac{1}{m}\\log(l_m)$). In the high probability or tail bound (or, more precisely, in \"data-dependent\" tail bounds), in general, we allow the bound to depend on particular instances $S$, $S'$, and probably also on $W$. Hence, one cannot readily use fixed-size codebooks. To make this compatible, we consider a codebook with sufficiently large size. Then, depending on $(S,S',W)$, we only search for a suitable $\\hat{\\mathbf{y}}[j]$ only in the **first** $e^{R_{(S,S',W)}}$ elements of this codebook. For instance, the term $R_{(S,S',W)}$ in Proposition 1 is exactly the KL-divergence term appearing in the bound. We add these explanations.\n\n**Regarding block covering:** Thanks for pointing this out. Indeed, this is one of the main reasons why block covering is considered in lossy compression (rate-distortion) in information theory. In general, to guarantee the distortion level of \"one-shot\" covering to remain below a certain threshold, one usually needs to consider the \"worst-case\" scenarios. In contrast, the block-covering allows to consider the \"average cost\" which can be considerably smaller. We will add this discussion."}, {"review_id": "l15F6IcFsc", "reviewer": "Reviewer_D6jh", "summary": "The paper advances state-of-the-art on information theoretic generalization guarantees for a class of representational learning problems. The contribution is positioned in the framework of information bottleneck approach and builds on the classical work of Blum and Langford for PAC-MDL bounds. The main result is on non-trivial upper bounds on generalization error of a representational learning algorithm in terms of so-called minimum description length of the label. The result is expressed in terms of KL-divergence of a vector of labels and any arbitrary symmetric prior, and resolves the issues related to use of mutual information measure. The aspects related to block coding and lossy compression are new to this type of results. ", "questions": "1. Better explain the implications of Theorem 5 relative to generalization based on mutual information. Why *should* the encoder structure matter more than information in latent variable. \n\n2. The connection/interpretation to/of geometric compressibility and how the lossy compressibility plays a role here is not very clear. \n\n3. Is possible to have a concrete example where proposed bounds are shown to be superior to classical bounds based on mutual information? ", "limitations": "not applicable.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The writing is adequately clear both in terms of technical precision and intuitive interpretations, where appropriate. The problem is important and the proposed results advance state-of-the-art. ", "weaknesses": "Perhaps a weakness of the paper is that it relies on a solid understanding of information theoretic background; for e.g., [GK19]. More importantly, Theorem 5 which is main result on generalization bound for representation learning needs a bit more explanation, both in terms of intuitive/conceptual ideas and technical contribution based on work in the previous section. The proposed result – as the authors claim – resolves issues with the information bottleneck method, but the reader gets limited understanding of how the complexity of latent space and validity of any choice of decoder plays out in practical settings. On the other hand, the discussion in Section 2 could be more pointed – with focus on key novelties (which might help save space and leave room for more extensive discussion in Section 3). It also appears that a tabular comparison of generalization bounds proposed in this paper, relative to the ones based on mutual information would clarify some of the issues regarding positioning of the results. \nUnless I am mistaken, it seems the authors do not formally introduce the key object $\\mathbb{E}[gen(S,W)]$. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their interest and their thoughtful comments that help to ameliorate the quality of the work.\n\nWe will improve the readability of the paper by gently introducing the used information-theoretic concepts. Among others, by explaining how by adding the \"block-coding\" technique to the combinatorical approach of [BL03], we ended-up in having bounds containing the KL-divergence term. To this end, we will explain better the \"Covering Lemma\" in information theory, which will highlight the implication of KL-divergence terms, which are key elements in our results. This will also help to better explain the intuition behind IB (lines 45-49). We will also explain better the lossy compression and its implications (please see the answer to Question 2).\n\nWe believe that the step-by-step structure of Section 2 helps the reader to understand the needed fundamental concepts and implications of our main result (Theorem 5). We will, however, try to make this section more pointed. We will also provide more high-level intuition about our proof techniques to highlight the key elements and implications of our results in Sections 2 \\& 3; as sketched in \"Regarding the presentation\" part of our response to Reviewer FoJr.\n\nWe apologize for missing the definition of $gen(S,W)$, that will be added. This definition existed in the earlier version and had been removed by mistake while reorganizing the paper.\n\n**Questions**\n\n1.The generalization bound of [VPV18] has several shortcomings: it loses its relevance in a realistic setup, it cannot explain the geometrical compression, it does not capture the encoder's \"simplicity\"/\"structure\", and it also depends on the decoder's structure. Moreover, mutual information (MI) appears to be a bad indicator of generalization error [AG19, GK19, DKSV20]. Our results address these issues. As suggested by the reviewer, we will summarize the benefits of our bound in comparison to [VPV18]. In our answers to Questions 1-3, we briefly discuss some aspects of such benefits.\n\nThe importance of the encoder's simplicity/structure can be well explained when the decoder is the identity mapping (no decoder) and hence the latent variables are the final predictions. Then, a common way to describe the simplicity is by studying the corresponding VC-dimension, which is known to be related to the generalization error. For VC-dimension, in contrast to MI, what matters is the structure of the whole vector $(X^n,\\hat{Y}^n)$, rather than coordinate-wise relations that matter in MI. An example is given in the paragraph 234-259. When a decoder exists, a similar intuition holds. Loosely speaking, simple encoders generate more \"structured\" latent variables that consequently make more \"structured\" predictions. A closely related question is studied before. e.g.. by Bshouty and Mazzaw in \"Exact Learning Composed Classes with a Small Number of Mistakes\". Making the connection more specific is another interesting future direction to be mentioned.\n\nIn principle, the encoder should guarantee good generalization behavior on its own and the role of the decoder is instead to minimize the risk. Our bound reflects this principle, by depending merely only on the encoder and being valid for any decoder. \n\n2.Borrowed from the rate-distortion theory, lossy compression is a \"natural solution\" to measure the compressibility of continuous data. Indeed, to describe even a bounded continuous variable $X$ in a \"lossless\" way, one needs an infinite number of bits. However, if we allow for some \"average distortions\" in compression, the needed number of bits becomes finite and the i.i.d. instances of compressed versions of $X$ will be \"concentrated\" around $X$.\n\nNow, consider the geometric compression [GK19]: in this experimentally observed behavior, the latent variables $U\\sim P_{U|X}$ of $X$ are distinct but concentrated around a few \"centers\". Thus, $I(U;X)$ becomes very large or infinite, causing the IB to lose its relevance. This happens for a similar reason as for the impossibility of the lossless compression of continuous sources. Hence, these scattered latent variables around the centers can be seen as a lossy version of the mappings from $X$ to one of these centers, with some small distortion. It should be noted that here there exists a subtle difference with the classical lossy compression, as we consider \"lossy mapping\" or \"lossy algorithm compressibility\" [SGRS22], instead of lossy compression. To give a simple example of \"lossy mapping\", suppose $X \\in [0,1]$, and if $X<0.5$, then $U=-1+X/5$, and if $X>0.5$, then $U=1+X/5$. In this case while $I(U;X)=\\infty$, a simple lossy mapping $P_{\\hat{U}|X}$ with average distortion less than $0.05$ can be found such that $I(\\hat{U};X)=1$. This explains the geometrical compression observation. \n\nWe note this connection was a partial intuition behind the new algorithm MMCDVIB, as described in the responses to all reviewers.\n\n3.Thank you for the suggestion. The MI-based bound of [VPV18] becomes infinite for continuous $(X,U)$. Even for discrete spaces, in a reasonable setup, the term containing MI in their bound is not dominant anymore, so the bound loses its relevance [RG19, LLS23]. In any of such a wide range of setups, our bound gives a better result. Moreover, the new experiments show a clear advantage of our KL-divergence regularization over MI. One reason is the data-dependent form of our priors in contrast to fixed priors in classical IB (as explained in our general response).\n\nThat said, we agree it would be interesting to compare analytically our bounds with [VPV18], in a simple neural network (NN). However, this evaluation turns out to be a difficult problem even for the classical bound, i.e. to study analytically MI in NN. We will mention this direction, and also studying the geometries of the latent variables in different architectures (e.g., FCN vs CNN), as interesting future directions."}, {"review_id": "GlJ1oM2K5g", "reviewer": "Reviewer_Lcin", "summary": "This paper obtains new generalization bounds of the conditional mutual information-flavor (Steinke and Zakynthinou, 2020), where the bounds depend only on the predictions that the algorithm induces on the supersample. These bounds are phrased more generally in terms of a KL divergence with symmetric priors, analogous to the almost exchangeable priors of Audibert (2004), and are placed in a rate-distortion theoretic perspective. This is further extended to lossy compression and tail bounds. Tighter bounds in terms of a function of the binary entropy are derived, which appear similar to classical PAC-Bayes bounds with the binary KL divergence in the style of Maurer (2004). Throughout, this is related to the representation in the style of the information bottleneck, leading to the main result of the paper: a generalization bound for representation learning algorithms which depends only on the encoder part, allowing for the decoder part to be chosen freely to minimize the training loss without affecting the bound. This allows for priors that are in some senses data-dependent, and the potential benefit of this is demonstrated numerically.\n\n**Post-Rebuttal edit**: I read the author rebuttal, which addressed my questions, in particular regarding related literature. I consequently updated the rating (as stated below).", "questions": "— There appears to be a clear connection to the frameworks of functional and evaluated CMI (f-CMI, e-CMI) of, e.g., Harutyunyan et al (2021) and Hellström and Durisi (2022). Is there a clear distinction between these bounds and your Theorem 1, other than the use of an auxiliary prior (the possibility of which is also noted in the mentioned works)?\n\n— The concept of symmetric priors seems identical to the almost exchangeable priors discussed by Audibert (2004). Is there any difference with these?\n\n— The bounds in terms of the function $h_D$ appear closely related to bounds with the binary KL divergence on the left-hand side, e.g. Maurer (2004) and Seeger (2002) — the properties of the function appear to be very similar. Is there a difference or are the two approaches equivalent?\n\n— Proposition 1: The left-hand side here is a single-draw result, which typically does not lead to bounds in terms of the KL divergence, but instead some form of information density or log-likelihood ratio. This is also possible to derive from your results, but the derivations have to be slightly altered. In the proof of Theorem 4, you instead consider a “PAC-Bayesian” bound which is averaged over the posterior, which naturally leads to bounds in terms of the KL divergence. I assume this is what you meant to write in Proposition 1 as well. As noted by Grunwald et al (2023), such PAC-Bayesian bounds follow immediately from the same derivation as average generalization bounds if they are based on “exponential inequalities” (as yours are). This can be extended to single-draw bounds as well, under more stringent absolute continuity assumptions.\n\nMinor: \n\nAbstract: IB undefined\n\nIntro: $\\text{gen}(W,S)$ and the corresponding notation for population and training losses (from e.g. Proposition 1) appear to be undefined\n\nQuotation mark lines 34, 234, 33\n\nLine 50: A sentence with only citations.\n\nLine 131: KL divergence notation is flipped in LHS of definition\n\nFig. 1 is not on the same page as it is discussed\n\nMargin overflow in Eq. (3), lines 579-581, more in appendix\n\nLine 242: $\\tau*$ instead of $\\tau^*$\n\nLines 266-272: inconsistent conventions for fractions. Can some expressions be moved to equation environments? Maybe this intuition can be expressed more informally and the math can be moved to the appendix where there is space\n\nI assume $[a,b]=\\{a,a+1,\\dots,b\\}$ for integers in some expressions, but I do not think this is defined and it conflicts with the standard use for closed intervals\n\nTheorem 3: The prior is called $P$ in the theorem statement but $Q$ in the equation.\n\nLine 329, 686: Incomplete sentence\n\nReferences:\n\nAudibert, “A better variance control for PAC-Bayesian classification”, 2004\n\nMaurer, “A Note on the PAC Bayesian Theorem”, 2004\n\nHarutyunyan et al, \"Information-theoretic generalization bounds for black-box learning algorithms”, 2021\n\nHellstrom and Durisi, “A New Family of Generalization Bounds Using Samplewise Evaluated CMI”, 2022\n\nSeeger, “PAC-Bayesian Generalisation Error Bounds for Gaussian Process Classification”, 2002\n\nGrunwald et al, “Exponential Stochastic Inequality”, 2023", "limitations": "Perhaps the discussion of limitations can be expanded, but it is not crucial.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "— The new results and their relevance for representation learning are well-established.\n\n— The theoretical analysis is thorough, covering several possible variants and tightenings of the results.\n\n— The presentation is overall very clear and pedagogical, including a very thorough discussion of some related prior work.\n\n— The numerical evaluation nicely illustrates the potential benefit of the proposed methods.", "weaknesses": "— There are some missing connections to previous work (see questions).\n\n— A few of the results appear to be stated incorrectly, and some notation seems undefined (see questions).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful reading of the paper, their interest in our work, and their constructive comments.\n\n**Regarding CMI:** We thank the reviewer for bringing our attention to CMI-based works and in particular the f-CMI-based follow-ups. We missed this connection, as the original CMI work is mainly focused on the complexity of the hypothesis space. However, thanks to the feedbacks, we understood that in particular the f-CMI framework has a close connection to Section 2 of our work, and therefore it deserved to be mentioned and discussed. \n\nMore precisely, Theorem 1 (with proper choice of the prior) gives a slightly stronger result than the f-CMI framework with $f$ being the predicted variables and $u=[n]$. The reason is that in Theorem 1, the expectation with respect to $Y^n,Y^{'n}$ of KL-divergence (of conditional distributions given $Y^n,Y^{'n}$) is considered, while f-CMI considers the expectation with respect to $X^n,Y^{n},X^{'n},Y^{'n}$ and KL-divergence is a convex function. There is also another small difference: in Theorem 1, we take the expectation w.r.t. $W$ (somehow equivalent to $R$ in the f-CMI setup) inside the KL-divergence term. We will highlight this connection after Theorem 1 by properly referencing the mentioned works and by mentioning that for the in-expectation result, the bounds can be potentially improved by considering $u=[m]$, where $1\\leq m <n$. In fact, interestingly, our approach, which is based on the framework of [BL03], shows the connection between this approach and CMI also. \n\nHowever, other results (including those based on the function $h_D$ and tail bounds) seemingly cannot be directly obtained using the existing f-CMI framework. Besides, in the f-CMI framework, we need the loss to be computable using $f$ and the label $Y$. Hence, this framework cannot be applied to the setup of Section 3 and thus, cannot obtain the main result of the paper (Theorem 5).\n\n**Regarding almost exchangeable priors:** We thank the reviewer for pointing out this valuable work, which we have not been aware of. Indeed, Definition 1.1 therein is applicable in our Theorem 1 and, in fact, we used a nearly identical definition in our preliminary version. However while this more relaxed condition is sufficient for Theorem 1, it is not the case for Theorem 2. In Theorem 1, similarly to the f-CMI approach of [Harutyunyan et al.] (and CMI-approaches in general), we only consider shuffling independently samples in $n$ pairs $(Z_{i,1},Z_{i,2})$ (and their corresponding predictions) of a \"super-sample\" $\\{Z_{1,1},Z_{1,2},\\ldots,Z_{n,1},Z_{n,2}\\}$ in order to assign randomly one sample to the training set and the other one to the test set. In Theorem 2, which is indeed inspired by [BL03], we consider shuffling the whole super-sample to assign $n$ instances to the training set and the others to the test set. This requires a different definition for the symmetry of the priors. This is why we opted for a unique definition of symmetry for both theorems. We will add these discussions. We note that the symmetry definition in Section 3 is also a bit different as it requires the invariance only under the permutations of latent variables that preserve the associated labeling.\n\n**Regarding $h_{D}$:** The function $h_{D}$ indeed resembles the pointed binary KL divergence function. As the reviewer is definitely aware, such bounds are established in terms of KL-divergence of priors and posteriors on the hypothesis space $D_{KL}(P_{W|S}\\\\|Q_W)$ that captures the complexity of the hypothesis space. To use this binary KL-divergence function for relating the generalization error to the complexity of the labels/latent variables, we need to consider KL-divergences over the space of labels/latent variables. This turns out to be difficult to achieve, among others, since the cumulant-generating function (equation (23)) appearing in this setup is different than classical PAC-Bayes bounds, and hence the proof does not follow straightforwardly. Thus, we cannot say these functions and approaches are the same, despite the similarity of their properties. We refer the reviewer to line 268 for the intuition behind $h_D$, inspired by [BL03].\n\n**Regarding Proposition 1:** We understand the point of the reviewer. This is the case for the classical PAC-Bayes bounds, where the posterior $P_{W|S}$ and prior $Q_W$ are defined over the hypothesis space. Hence, by considering an instance $(S,W) \\sim \\mu^{\\otimes n} P_{W|S}$, the bound contain the information density $\\log\\frac{\\mathrm{d} P_{W|S}}{\\mathrm{d} Q_{W}}$. In our work, however, the prior and posterior, for example in the case of Proposition 1, are defined over the predicted sample space, and hence for any given $(S,S',W) \\sim \\mu^{\\otimes 2n}P_{W|S}$, the KL-divergence term $D_{KL}( P_{\\hat{Y}|X,W}^{\\otimes 2n}(\\hat{Y}^n, \\hat{Y}^{\\prime n}|X^n,X^{\\prime n},W) \\\\| \\mathbf{Q} )$ appears. This is because in our definition of the loss function (after line 156) we already considered the expectation with respect to the prediction, and hence LHS of the bound of Proposition 1 already contains an expectation term.\n\nIn Theorem 4, there exists an extra expectation w.r.t $\\hat{W}$ for the exactly same reason that the reviewer suggested: because we considered the average over the posterior. We will discuss this difference in our PAC-Bayes bounds w.r.t. the classical PAC-Bayes bounds in terms of the complexity of the hypothesis space.\n\nMoreover, using the provided feedback, we discuss the potential of considering further a \"disintegrated PAC-Bayes\" bound that not only consider one draw of $(S,S',W) \\sim \\mu^{\\otimes 2n}P_{W|S}$, but also the \"one-shot\" prediction of the label. For this case, one should remove the expectation term in the loss function.\n\n**Minor Comments:** Due to space limitations, we will apply the minor comments directly. Thanks for such a careful reading. We just precise that by the interval $[a,b]$ in line 272, we meant the closed interval. "}]

Author rebuttal:
We sincerely thank all the reviewers for their valuable time and their pertinent comments that helped to improve our work. We are excited to see that all reviewers appreciated the value of our work. We carefully read the comments of all reviewers and addressed them separately. Please do let us know if any further clarification is needed. 

Here, we present our new experimental methods and findings that further reveal the potential practical implications of our work.

**New experimental results.**  To improve the experimental results, we introduce two enhanced variations of the previously described CDVIB approach: a Moving-average CDVIB (MCDVIB) and Multiple-centers Moving-average CDVIB (MMCDVIB).

**MCDVIB:** The first approach (MCDVIB) is similar to CDVIB with the only difference that the mean and covariance matrix of the priors $Q_K$ do not depend solely on the data in a single mini-batch. Instead, we consider a *moving-average* of such quantities over mini-batch sequences. Please note that although MCDVIB is just a special case of MMCDVIB (see below) with $M=1$, we presented them separately to better illustrate the effect of each enhancement.

By taking the moving average of mean and covariance, the data in the previous batches plays "partially" the role of the "ghost data" (that should be from the test set and is not available). This synthetic reproduction of the effect of ghost data is more pronounced during the first epochs where the neural network had not yet "memorized" the whole data. Note that the learning rates at the first epochs are larger and in general the early epochs of the training are important and sometimes "decisive" during which the regularization has significant importance, as shown in arXiv:2002.09572, arXiv:1609.04836, arXiv:2002.05366, arXiv:1711.08856. As can be observed in the attached PDF file, indeed this helps to increase the accuracy.

**MMCDVIB:** Now, we consider a prior choice that allows *multiple* priors for each label. For each label $k\in[K]$, we consider $M\in \mathbb{N}$ priors 

$$Q\_{k,r}^{(t)}=\mathcal{N}\left(\bar{\mu}\_{k,r}^{(t)},diag\left(\bar{\sigma}^{(t)^2}\_{k,r}\right)\right),\quad r\in[M], k\in [K],$$

defined over $\mathbb{R}^m$, where the superscript $t\in\mathbb{N}$ represents the optimization iteration. The vectors $\bar{\mu}^{(t)}\_{k,r}$ and $\bar{\sigma}^{(t)^2}\_{k,r}$ are initialized as $m$-dimensional zero vector and updated at each iteration as follows. First, we introduce two notations. For any sample $z$ with label $k$ and for any $t\geq 1$, denote
$$r\_z^{(t)} = argmin\_{r\in[M]} \| \mu\_{x}-\bar{\mu}\_{k,r}^{(t-1)} \|.$$

Suppose that the picked mini-batch at iteration $t$ is $\mathcal{B}\_t=\{z_1,\ldots,z_b\}$. For each $k\in[K]$ and $r\in[M]$, let
$$\mathcal{I}\_{k,r}^{(t)}=\\{ z_i: i\in[b],y\_i=k, r\_{z\_i}^{(t)}=r \\},$$ 
and let $b\_{k,r}=|\mathcal{I}\_{k,r}|$. Now, if $b\_{k,r}\neq 0$, update $\bar{\mu}^{(t)}\_{k,r}$ and ${\bar{\sigma}^{(t)}\_{k,r}}$ as
$$\bar{\mu}\_{k,r}^{(t)} \coloneqq  (1-\alpha b\_{k,r})\bar{\mu}\_{k,r}^{(t-1)} + \alpha \sum_{z_i\in \mathcal{I}\_{k,r}} \mu\_{x_i},$$
$$\bar{\sigma}^{(t)}\_{k,r,j} \coloneqq \sqrt{(1-\alpha b\_{k,r})  \bar{\sigma}^{(t-1)^2}\_{k,r,j}+ \alpha\sum\_{z\_i\in \mathcal{I}\_{k,r}} \sigma_{x_i,j}^2},\quad j=1,\ldots,m.$$
where $\alpha \in [0,1]$ is a coefficient smoothening the evolution of the mean and variance, and also implicitly takes into account the effect of the ghost dataset $S'$ appearing in the bounds of Theorems 5 and 7. The optimal value of $\alpha$, among others, depends on $b$ and $M$.
Finally, the considered objective function at iteration $t$ is 
$$\frac{1}{b} \sum\_{i=1}^b \\bigg\\{  \beta  D\_{KL}\bigg[\mathcal{N}\left(\mu\_{x_i},diag(\sigma\_{x\_i}^2)\right) \\| \mathcal{N}\left(\bar{\mu}^{(t)}\_{y_i,r_{z_i}^{(t)}},diag(\bar{\sigma}\_{y_i,r_{z_i}^{(t)}}^{(t)^2})\right)\bigg]-\mathbb{E}\_{U_i\sim P\_{U|X,W_e}(U_i|x_i,W_e)}\left[\log P_{\hat{Y}|U,W_d}(y_i|U_i,W_d)\right] \\bigg\\}.$$

**Simulation setup:** For the simulations, we consider the CIFAR10 dataset and a two-step prediction model, where the encoder consists of 4 conv. and 2 fully-connected layers (CONV4+FC2) and the decoder is a single FC layer. This choice is motivated by the fact that in general, CNN are better adapted to process image data. We set mini-batch size $b=128$, the moving average coefficients $\alpha = 5e-4$ in (M)MCDVIB, and the number of centers in MMCDVIB $M=5$. We trained the model for 200 epochs.

**Simulation findings:** As can be observed in the attached PDF, both MCDVIB and MMCDVIB help to improve the performance of the learning algorithm. The latter improves the accuracy by around 3\% upon VIB.

We have further plotted the 2-dimensional random projection of the latent space for both training and testing data for MMCDVIB, and for $\beta = 0.001, 0.01, 0.1$ (for these values of $\beta$, the advantage of MMCDVB over VIB is the most pronounced, as seen in Fig. 1a). It could be noticed that the distribution of testing samples is closely aligned with the distribution of training samples. This suggests in turn that the trained models did not simply "memorize" the training data, and instead, they learned to generalize. Furthermore, although it is hard to judge on this 2D projection whether the produced learned samples are far apart, we may notice that when $\beta=0.1$ the latent space (somewhat intuitively) seems to be more "structured" and compact than when $\beta=0.001$.

Meta-review: The paper shows new generalization bounds based on information-theoretic quantities and techniques. The contribution builds on the classical work of Blum and Langford for PAC-MDL bounds; the bounds are phrased in terms of a KL divergence with symmetric priors, and leverage a rate-distortion theoretic perspective. The work also has connections to ideas in information bottleneck, and to some degree formalize the benefit of "bottlenecked" representations, in a sense the authors suitably formalize. 

The reviewers universally agreed the paper is written well, places the bounds in good context given prior work, and provides interesting insights.
Decision: Accept (poster)