A unified framework for information-theoretic generalization bounds
Authors: Yifeng Chu
Maxim Raginsky
Venue: NeurIPS 2023 poster (2023)
Keywords: generalization bounds
information theory
chaining
PAC-Bayes
couplings
TL;DR: We present a unified framework for deriving information-theoretic generalization bounds.

Abstract: This paper presents a general methodology for deriving information-theoretic generalization bounds for learning algorithms. The main technical tool is a probabilistic decorrelation lemma based on a change of measure and a relaxation of Young's inequality in $L_{\psi_p}$ Orlicz spaces. Using the decorrelation lemma in combination with other techniques, such as symmetrization, couplings, and chaining in the space of probability measures, we obtain new upper bounds on the generalization error, both in expectation and in high probability, and recover as special cases many of the existing generalization bounds, including the ones based on mutual information, conditional mutual information, stochastic chaining, and PAC-Bayes inequalities. In addition, the Fernique--Talagrand upper bound on the expected supremum of a subgaussian process emerges as a special case.

A Unified Framework for Information-Theerrtii Generalization Bounds
Yifeng Chu Maxim Raginsky Cychu26 millimoi@ edu*
Abstract
This paper presents general methodology for deriving information-theoreii gener- alization bounds for learning algorithms. The main technical tool is probabilistic decorrelation lemma based on change of measure and relaxation of Young's s inequality in LØp Orlicz spaces. Using the decorrelation lemma in combination with other techniques, such symmetrization, couplings, and chaining in the space probability measures, we obtain new upper bounds on the generalization error, both in expectation and in high probability, and recover special cases many of the existing generalization bounds, including the ones based on mutual information, conditional mutual information, stochastic chaining, and PAC-Bayes inequalities. In addition, the remique-Talagrand upper bound on the expected supremum of a subgaussian process emerges special case.
Introduction
The generalization error of learning algorithm is useful proxy for evaluating the performance of the learned model on previously unseen data. Formally, is defined as the expected (absolute) difference between the population risk and the empirical risk of the hypothesis returned by the algorithm. One of the classical methods for estimating the generalization error is via uniform convergence of various empirical processes indexed by the hypothesis class [1.2]. For example, in the analysis of Empirical Risk Minimization, one can estimate the expected generalization error via Rademacher averages, which can be bounded from above using chaining techniques [3].
However, the bounds based on uniform convergence are often too pessimistic and may even become vacuous when the hypothesis space is extremely large, typical situation with deep neural net models. For this reason, is preferable to obtain algorithm-dependent generalization bounds that take into account the joint distribution of the training samples and of the output hypothesis. In this context, one capitalizes on the intuition that the generalization ability of a learning algorithm should be related to the amount of information the output hypothesis reveals about the training data. This idea, which has origins in the work on PAC-Bayes methods [4,5], is the basis of the growing literature on information-theoreti generalization bounds, first proposed in [6] and further devoloped [7-16] and many other works.
In fact, it is possible effectively combine the coemmattion-thhoretie approach with the classical framework based on various measures of complexity of the hypothesis class: One can use chaining techniques to successively approximate the hypothesis class by simpler model classes, which can then be analyzed using
ceammatiio-thheoeee tools. This methodology, again originating in the PAC-Bayes literature [17], has been developed recently in [18-21]. Our goal in this work is develop these ideas further by giving unified framework for informatiin-theerrtie generalization bounds, from which many of the existing results emerge as special cases.
Department of Electrical and Computer Engineering and Coordinated Science Laboratory, University of Illioois Urbana, 1L 61801, USA.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

1.1 The main idea, informally
The main idea behind our framework surprisingly simple. We first give an abstract description and then show how it can be particularized to various settings of interest. Let (Xt)ter be a centered (zero-mean) stochastic process defined on a probability space (Ω, A, P) and indexed by the elements of some set T. Let Q be Markov kernel from Ω to T, i.e., measurable mapping taking each w E Ω probability measure Q- () on Together, P and Q define probability measure s Q on the product space f x T. The mathematical object we would like to study is the expected value
2 Q, = [
JaXT ((())(((()))
For example, assuming that there exists a measurable map T² : + T, such that sup XxWw, teT
X, (w) (w)
IP
we can take Q(Aw)) 1 ())())))) for all measurable subsets A of T. Then
IP 2 x) E sup X; TET
the expected supremum of X,, the central object of study in the theory of generic chaining, where (I, is metric space and increments X, - X, are "stochastically small" relative to d(u, v). Altennatvely, consider statistical learning problem with instance space 2, hypothesis space W, and loss function & W 2 + Let Pz be the (unknown) probability law of the problem instances in Then we could take = 2", psn T W, and
X
Σ (L(w) - l(w, Z:)), T
where I(w) == Ez-Pz [K(w, Z)] the population risk of w. Let Q be a (randomized) learning algorithm that associates to each sample S (Zi...., Zn. P probability measure Q(-IS) on the hypothesis space W. Then
( =
(L(W) - e(w,
((w))-(w,,:))
is the expected generalization error of Q. In either case, proceed to analyze (P Q, X) via combination of the following two steps:
Decorrelation - We can remove the correlations encoded P&Q by choosing convenient product measure P % μ Ω x T. that (roughly)
Q X) S /D(P QIP 2 p) + Error
provided the process (X,)ter is regular enough for the term to be small. Here, use the relative entropy (or information divergence) D(-II-) to illustrate the key idea with minimum of detail; the precise description given in Section 3.
Chaining in the space of measures - Since the process (Xt)teT is centered and P & is a product measure, we automatically have (F @ μ,, X) = 0 even though (P & Q) o We can therefore interpolate between IP @ Q and P & along a (possibly infinite) sequence Qu Q....., QK of Markov kernels, such that P & QK = P & Q. P & Qu = P & μ., and the differences (P @ X) (P @ Qk suitably small. Telescoping, get
P (
Σ (P&Q (P Qx1,)))).
For each h; we then apply the decorrelation procedure to increment process (X,, Xx)a,veT, with IP as before and with suitably chosen family of couplings of Q+(+ww) and (.-w(- This step can combined effectively with other techniques, such as symmetrization.

---

2 Preliminaries
Basic definitions. All measurable spaces in this paper are assumed to be standard Borel spaces. The set of all Borel probability measures on a space X' will be denoted by P(X). A Markov kernel from (X', A) to (), B) a mapping Py x B X [0. 1]. such that Pr)x==())
Pyix (-1z) is an element of P()) for every x E X' and the map x Pylx==(B) B) is measurable for every B E B. The set of all such Markov kernels will be denoted by .M)))))).
The product of Px E P(X) and Pyix E (M()) the probability measure Px @ Prix P )) defined on product sets A B S xxy by (Px @ Pyxx) := ʃA ( then extended to all Borel subsets of X' x y by countable additivity. This defines a joint probability law for a random element (X of X x V, so that Px the marginal law of X, Pyxx is the conditional law of given X, and (-) = Sx ()) (dr) is the marginal law Y. The product measure Px & Py. under which X and Y are independent, is special case of this if we interpret Py as trivial Markov kernel with Pr|x== = Py for all x.
and
coupling of E P(X) and E P()) is probability measure P E P(X y), such that P(. x )) = p((-) and P(X' x =(-). We will denote the set of all couplings of and v by [1(, v/). Let the space X' JU be equipped with a metric d, and let Pp. for p 2 1. denote the space of all probability measures P on X' U V. for which there exists some 20 E X' U such that fxuy d(z, 20)
xo. Then the p- Wasserstein distance between μ E P(X) n Pp and
E P()) n Pp is given by
1/p
(fdeennaaale dy)
v)(u,))= = inf =elliaes
(see [22, for details).
L and LV spaces. The (P()) norms of f X - R, for p E P(X) and 2 1, are defined as
IIfle=(a) := ( 1fP dp) 1/r
whenever the expectation on the right-hand side exists. We will often use the linear functional notation for expectations, i.e., () = =[x dp,
For p 2 define the function uip R4 - by (/((x) exp(x*) - 1. Its inverse is given by d/ (z)
(og(x+1)) 1/p, where log will always denote natural logarithms. Some useful properties of these two functions are collected in Appendix A Supplementary Material. The function ttp arises in the context of controlling the tail behavior of random variables (see [1,24,25 25] for details). The Orlicz v morm of real-valued random variable is defined as
|| == inf {c 0: E
(x))
$1}
and the tails of X satisfy P| 2 u] S Ke Cu" for all u 2 and some K,C 0 if and only [|X < oc. The Orlicz space Lup is the space of all random variables X with ||X < co. In particular, is o-subgaussian, i.e., P| 2 u] < 2e- -e222/20² for all u 2 0, then || l1 S V6a; conversely, every X E Loz is ousugaaussian with 5 cl x| for some absolute constant c > 0.
Information-theereti quantities. The relative entropy (or information divergence) D(ullv) be- tween two probability measures μr, on the same space X' is defined as
D(ulp)) < log
du de
if & (i.e., is absolutely continuous w.r.t. v), and D(ullv) == +o0 otherwise. The following inequality will be useful (proofs of results are in Appendix B of the Supplementary Material); Proposition 1. If < v, then for any
(u.0, 2 (1(m))
(dp))
(D(Hllv) + 1PP
dv
3

---

The conditional divergence between Pries Quio E M(VIU) given Pu P(U) is defined by
D(Pv)o/QVielP)) D(Pu @ Py @ Qviu).
The mutual information T(X;Y) == D(Py P and conditional mutual information I(X;Y 2) D( 1 2 Pxz) are special cases of the above definition, and the identities
D 10 = I(X;)) +(yy)QQ D D(Pyixzll@yp Px2) = (( D(Priz 1Qrzz|p2)
(2)
(3)
hold whenever all the quantities are finite. See, e.g., [26] for details.
The decorrelation lemma
All of our subsequent developments make of the following decorrelation lemma: Lemma 1. Let ns, be two probability measures spuce X such that μ & and let f,g X - R2 be two nonnegative measurable functions. Then the following inequalities hold:
(g) S 22/2/ f1, dv ( + (wp())
(4)
and
(u, <21P111fll> + 41 fU (())
dH dv))
+ 4/ /1/pllll (log(u, exp(s"))) Mp.
(5)
The proof makes extensive use of various properties of 1/p and ,/p1 In particular, Eq. (4) is relaxation of the Young-type inequality S (x)) + (y),,, where (x) == sup, sup, uapyyo(oe)) (20 the (one-sided) Lengendre- Eeneendre-Fenchel conjugate of upp. (We refer the reader to [13] for another use of duality in Orlicz spaces in the context of generalization bounds.)
1 (v))
Every of Lemma in the sequel will be instance of the following scheme: Let Px P(X), Qy E P()), and Py|x E M X)) be given, such that Py|x== < Qy for all x E X. Let YX,Y,Y) be random element of X' x y x y with joint law Px @ Prix & Qy; in particular, Y independent of (X, Y). Furthermore, let f y + TR., and X' y + R. be given, such that E (o y))] S for all y V. Then, applying Lemma conditionally Py|X== V Qr, f. and g( :), and then taking expectations w.r.t. Px, we obtain
X with
(APrIx
)) + E((())) aQy
E[((Y)((X, S /PE 1005
In specific cases, the quantity the right-hand side can be further upper-bounded in terms of the information divergences D(Py [[Qy) using Proposition 1.
Some estimates for the absolute generalization error
We adopt the usual set-up for the analysis of (possibly randomized) learning algorithms and their generalization error. Let instance space Z, hypothesis space W, and nonnegative loss function L: ?:Wx x Z >> R4 be given. learning algorithm Markov kernel Pw is from the product space n into W, which takes as input an n-tuple S (Zi...., Zn,) i.i.d. random elements of with unknown marginal probability law Pz and generates a random element W of W. We define the empirical risk and the expected (or population) risk of each w E W by
n
Ln(w)= =
Σ i=1
E(w, Zt).
L(w) = (P2,((w) +)) Elf(w, Z)]
where P, is the empirical distribution of S, and the pointwise generalization error by
gen (w, S) == L(w)- L,(w).

---

It will also be convenient to introduce an auxiliary n-tuple 5' = (Zi...., Zn, ~ P2", which is independent of (S, W) P @ Pwis. We will use $ denote the pair (5', ,S) and write E2 (w) for the empirical risk of w on S".
As first illustration of general approach, we show that it can be used to recover some existing results on the generalization error, including the bounds of Xu and Raginsky [7] involving the mutual information and the bounds of Steinke and Zakynthinou [10] involving the conditional mutual information. We start with the following estimate on the expected value of [gen W, S)]:
Theorem 1. Assume the random variables f(w, Z), W E W, are o-subaaussian when Z ~ Pz. Let learning algorithm Pwis be given. Then, for any Qw P(W),
12o²
dPwis
+1)
Ellgen(W; (W, S
E
222
(6)
n
dQw
where the expectation on both sides is w.r.t. Ps @ Pwis= p @ PWIS-
The key step in the proof is to apply the decorrelation lemma, conditionally on S, to j = Pwis-
V' = Qw. f(w) = o 6/n, and g(w) =
[g)n(w.S)
//6/n The same subgaussianity assumption was
also made by Xu and Raginsky [7]. Minimizing the right-ham hand side of (6) over Qw, we recover their generalization bound up to a multiplicative constant and an extra ((1/vnz) term (which is unavoidable since we are bounding the expected absolute generalization error):
Corollary 1. Under the assumptions of Theorem 1,
24 E| Ellgen W, W)] S V (I(W:S) + 4).
n
A notable shortcoming of Theorem and Corollary is that they yield vacuous bounds whenever the mutual information (WW infinite, which will be the case, e.g., when the marginal probability laws Pz and Pw are nonatomic (i.c., assign zero mass to singletons) and the learning algorithm deterministic. To remove this drawback, will use an elegant auxiliary randomization device introduced by Steinke and Zakynthinou [10].
Let (E1..... ,,,) be n-tuple of i.i.d. Rademacher random variables, i..., P(E, =1| = 1/2, independent of S. For each let 7, : 74 and 7, Z and let P Sew be the joint probability law of (5,e, W). such that Psc = P3 @ Pe and Pwis. == Pwis- where S = (2i 2 In other words, under P. å and are independent and have their respective marginal distributions, while W generated by feeding the learning algorithm Pwis with the tuple 5 Consequently, W is independent of 5-c e2 -, Then, letting P be the joint law of (Š, W). we have
Ep |gen (W, W))) = Er Ep [T,, (W)- - I., (W)S,, W1]
< Er I', (W) I,,
Epp 1
21) -(( - 27-))
n
Ep 1
Σ ((W,Z) e(W, (.W,
i=1
Thus, all the analysis be carried out w.r.t. P. in the following:
Theorem 2. Assume there exists function A Z x Z + Rt, such that (e(w,2) E(w, 2')1 < A(z,²') for all E W and z, E Z. Then for any Markov kernel Q Qwis with access to $ but not to we have
V12 | 1/5 / (dPwise wiss
+1)l
Epllgen (, W)S)]| < n
Ep
(8)
dQ w/s |
where (a(5)l(a = (E A(zi, 2/)2)1/2
5

---

The same assumption on l was also made in [10]. Optimizing over Qwis we can recover their Theorem 5.1 (again, up multiplicative constant and a ((L/vT) fluctuation term):
Corollary 2. Under the assumptions of Theorem 2,
24
Epllgen(W, S) S V
44,
(9)
where Z and are independent samples from Pz and where the conditional mutual information is computed w.r.t. P.
The main advantage of using conditional mutual information is that it never exceeds log 2 (of course, the bound is only useful if ((W; = o(n)).
5 Estimates using couplings
We now turn to the analysis of EWg S)] using couplings. The starting point is the following observation: With (S', W) be constructed as before, consider the quantities
I. (w) == Ii,(u)) I, (w)
Σ (l(w, Z,) ((),
Then, using the fact that (P3 60 Qw: Iim) = 0 for any Qw E P(W), we have
Elgen (W,5)) (P3 @ Pwis: I.n) - (Pg @ Qw, Lmn)
[
( i.)) (Qw: T.n)).
(10)
Zxz
This suggests the idea of introducing, for each 8 E 2", ; a coupling of Pwis= and Qw i.e., a probability law Puvis=s for a random element (U, of W x W with marginals Po PwIs=s and Py Qw. We then have the following:
Theorem 3. For u, E W and 3 = (s) ('') 2" x 2", define
o² o² v. 3) = Σ (((,,)))(((,22))) - (E(u, 23) - f(u, ((0,,11)))
(11)
==1
Then, for any Qw E P(W), any family of couplings PUvIS=s II(PW)s==: Qw) depending measurably on E 2", and any puv E P(W x W).
244 E (U.
dPovis dupv )+ + E(o
Eigen (W,S))
(12)
where the expectation on the right-hand side is w.r.f. the joint law of (U, V,U V, 5), under which (S, UV are distributed according to Ps 2 Puvis, (U, V) are distributed according to pøv inde- pendently of (U, V, V), and S' is distributed according Ps independently of everything else.
The proof makes essential use of symmetrization using auxiliary n-tuple of i.i.d. Rademacher random variables, which allows to apply Lemma conditionally on $.
The coupling-based formulation looks rather complicated compared to the setting of Section 4. However, being able to choose not just the "prior" Qw, but also the couplings PUvIs of Pwis and Qw and the reference measure μUv, allows to overcome some of the shortcomings of the set-up of Section 4. Consider, for example, the case when the learning algorithm ignores the data, i.c., PwIS Pw. Then we can choose Qw Pw. Puvis du) Pw (du) @ (, where 8, is the Dirac measure concentrated on the point and Pøy = Poy (since the latter does not depend on S). With these choices, U V and V almost surely, so the right-ham side of (12) is identically zero. By contrast, the bounds of Theorems 1 and 2 always include an additional ((1/ /n) term even when W and Š are independent.

---

Moreover, Theorem 3 can be used to recover the bounds of Theorems and 2 to multiplicative constants. For example, to recover Theorem 1, we apply Theorem with PEvis Pwis Qw-
μUv = Qw @ Qw, and with an estimate on oU, V, 5) based on the subgaussianity of l(w, Z).
For more manageable bound that will be useful later, let us define the following for u, W:
1/2
dg,c(u,u) = n2
(e(u, Z.) E(v, 2,))²
= -[e(u,-) -(u -(v,,))le<((P))
1/2
u) E
[[(((u, f(v, 2))
= =[(((u,)) (0()))((w,))))) (((,))
Corollary 3. Under the assumptions of Theorem 3,
48
dl. (1sss
( dr(0,
Eigen(W.,S] S
duov
Refined estimates via chaining in the space of measures
We now combine the use of couplings in Section 5 with chaining argument. The basic idea as follows: Instead of coupling Pwis with Qw directly, we interpolate between them using (possibly infinite) sequence of Markov kernels pn
wis P wis..... PK p wis+ such that P0 wis = Qw and PK Pwis (or lim4-+00 W|s P'w in an appropriate sense, e.g., weakly for each S, if the sequence is infinite). Given any such sequence, we telescope the terms (10) as follows:
E(gen(W,,S]
/ Pg(dE) 2x2
Σ (1P Pa) (PWTs-=:
K
k=1
For each k. now choose a family of random couplings Pw. [[PP W Pivis) and a deterministic probability measure PW, W E P(W x W). The following an immediate consequence of applying Corollary 3 to each summand:
Theorem 4. Let Pwis: Qw, PweWe..ls. and pw.W.. be given as above. Then
Elgen(W; (W,)) S)]
48
K
(de( Wk-1) + dW,, Wk-1)) ( ddWw.w 118) dpw.wa.. uls) + de(Wen, W Wx-1)
Σ
E
where in the kth term on the right-hand side Wh, Wk-1) are jointly distributed according to Ps 8 Pw, Wis and (Wr, Wx-1) are jointly distributed according to PWaWa-1
Apart from Theorem symmetrization to construct various subgaussian random variables conditionally W and S. For the next series of results, we will assume something more, namely that (W, d) is a metric space and that the following holds for the centered loss E(w, f(w, E(l(w, Z)):
have been imposing only minimal assumptions & and then using
(((u, - 2.))
I Vnd(u, v), Vu W.
(13)
1/2
In other words, the centered empirical process Vn Ein E(w. Zi) indexed by the elements of (W, d) subgaussian process [1-3].
Theorem 5. Assume (13). Then
2 Σ
(1) d(Wa, W2-1)
E igen (WS)) S)] <
d(We, W2-1)
dpw.
(14)
As a byproduct, we recover the stochastic chaining bounds Zhou et al. [20] (which, in turn, subsume the bounds of Asadi et al. [18]):
7

---

Corollary 4.
Let Pz and Pwis be given, and let Pw be the marginal law ofW. W. Let (Pwyls) k20 be
sequence of Markov kernels satisfying the following conditions: (i) Pwols = Pwi (ii) Pwals k000
Pwis: (iii) for every k 1, S- - W WE Wk-1 is Markov chain. Then
E Eigen(W. [WS)] S
E d(W W Wi-1) D(Ps +1]
(15)
n
(16)
Finally, we give estimate based on 2- 2-Wasserstein distances (cf. Section 2 for definitions and notation). Let -2(:.-) ) be the Wasserstein distance on P2 induced by the metric d on W. (constant-speed) geodesic connecting two probability measures P. Q P2(W) is continuous path [0.1 H Pt E P2(W), such that ph = P. P = Q, and W2(ps. Pt) = (L (P, for all 0 0S8 $ Then we have the following corollary of Theorem 5:
Corollary 5. Let Pz and Pwis be given, and let Pw be the marginal law of W. With respect to 2- Wasserstein distance, let (Wils)oskks be some points on the constant-speed geodesic (pe)eejo.1] with endpoints Pa Pwols = Pwis and = Pwx|S = Pw (where K may be infinite). i.e., there exist some to < t1
tk 1, such that Pwa|s Pta for k 0,1,.... For each k let Ww,W,- be the optimal coupling between the neighboring points Pwa-1|s and Pwass. i.e., the one that achieves Wa(PWe-.1ss Pw.1s). Then
< tk
E (g,
2 Vi n
2 Pw))+ Σ E Wa(Pwiss Pwa, (is) D(Pw.w i1 (wsllPWowail)
$
(17)
Observe that the first term on the right-hand side of (17) is the expected 2- 2-Wasserstein distance between the posterior Pwis and the prior Pw, while the second term a sum of "divergence weighted" Wasserstein distances. Also note that the form of the second term is in the spirit of the Dudley entropy integral [1-3], where the Wasserstein distance corresponds to the radius of the covering ball and the square root of the divergence corresponds to square root of the metric entropy. We should also point out that the result in Corollary 5 does not require Lipschitz continuity of the loss function E(w, 2) w.r.t. the hypothesis E W, except in weaker stochastic sense in (13), in contrast to some existing works that obtain generalization bounds using Wasserstein distances [27.28].
Tail estimates
Next, we turn to bigh-probbbility tail estimates on gen (enWWS) We start with the followoing simple observation: Assume Eww, Z) is o-subgaussian for all w W when Z ~ Pz. Then, for any Qw E P(W) such that Pwis== < Qw for all Zn, we have
gen2(WWS) 602/n
log (1+ dPwis
(m))
gen gen"(W,S)
]
E
exp
exp
dQw
602
with W Qw independent of W). Thus, by Markov's inequality, for any 0 << 8 < 1,
6 e
(=
(w)) + log 1 dQw
P
Igen( W, S) > o
<
In other words, Igen (W made by Hellström and Durisi [9] with Qw = Pw. giving high-probabilityy bounds of the form ( S) S V
S)I S vn 2/
dPw with high Psw Sew-probability. Similar observations
dQw
o² D(Pis Pw)
Generalization bounds in terms of the divergence D(Pwisl) Pw) are also common in the PAC-Bayes literature [4.5]. Moreover, using the inequality (5) in Lemma 1, can give high Ps- Ps-probability bounds the conditional expectation
(Pwis, Aegn (W, (Pwis, ((W)) L,, (W))).

---

Theorem 6. Assume E(w, Z) is o-subgaussian for all w when Z ~ Pz. Then. for any Qw E P(W), the following holds with Ps-probability of at least 6:
24a²
((PWIs:V2' (dPw)s) dd@
2 log 8
(Pwis, (w, S)I> -
Another type of result that appears frequently in the literature on PAC-Bayes methods pertains to so-called transductive bounds, i.e., inequalities for the difference between
(P) @ Pwis: 8) (P, 2 Qw. = Σ
Ble(w, e(W, 2)15),
and
(Pr & PwIs, - (Pr @ Qw
Σ E(e(w, 2.) e(W, (.W
where Qw is some fixed "prior" and where W W~ Qw is independent of (5', W). Using our techniques, we can give the following general transductive bound:
Theorem 7. Let Pwis and Qw be given and tuke any (Pw. and (pwawe 2)mm in Theorem 4. Also, let
(p..P2....N be a strictly positive probability distribution on N. Then the following holds with Pg-probability at least 6:
(PP @ Pwrs: E) - (P' 00 Qw, ( Pwis: E) (Po 1 Qw,
96
K
V VPwwa B B.d + (Ws d3 (
dpw
n
+ (PW. log 2
pnd
where
(u,v)
1 2n
(((u, Zi) (f(u, ((),, e(v, ((v,,,)))) 22
l(v,
This result subsumes some existing transductive PAC-Bayes estimates, such as Theorem of Audibert
and Bousquet [17]. Let us briefly explain how we can recover this result from Theorem 7. Assume that W is countable and let (A&) be an increasing sequence For each lc and each w W. let (w) be the unique set in As containing w. Choose representative point in each A Ay and let Ws denote the set of all such representatives, with Wi = {wo). Take
finite partitions of W with Ao (W)-
PW = Pwis and Pw; Qw 8wng Now, for each A: 2 O, we take Pw.ss the projection of PwIs onto Ws, i.e., the finite mixture
Pwals: = Σ Pwis(As
wEW
Moreover, given some "prior" π E P(W), we can construct a sequence (Tt (Tr) of probability measures with ao and un 8 such that Ta is a projection of onto Wt. Now observe that, for each kt S - Wx - We W is a Markov chain. Indeed, if we know Pwiis- then we can construct Pw, for any e < i without knowledge of S. With these ingredients in place, let choose Ws = Pw._, |Wa & PwEis and pw,w,, W, = and Jensen, we conclude that the following holds with Ps-probability at least 1- 8:
m @ Pwe-, IW., Then, using Cauchy-Schwarz
(P% & Pw]ss (P, & Swo 4)) (PP, & Pwis; e) (P., @ dwo 2)
96
(IT PWi-I 1 d.
11
2(Pw. & Pw W. LB BG. (D(PWaiss|TT)) + log p4ō V
2e
This recovers [17, Thm. 2] up to extra term that scales like J Ex / VITe & Pwi 1/W, da dz

---

The Fernique-Talagrand bound
As bonus, we show that combination decorrelation and chaining in the space of measures can be used to recover the upper bounds of Fernique [29] and Talagrand [30] on the expected supremum of stochastic process in terms of majorizing measures (see Eq. (19) below and also [31,32]).
For simplicity, let (T, d) be a finite metric space with diain(") sup d(u, v) u E T < oo. Let r), denote the ball of radius 2 0 centered at E T, i.e., B(t,r) {u E T d(u, S r). Let (Xe)er be centered stochastic process defined on some probability space (Ω, A, IP) and satisfying
Xu
X d(u, v)
}
E
S 1,
Vu,ETT
(18)
for some p 2 Then we can obtain the following result using chaining in the space of measures and decorrelation estimates:
Theorem 8. Let T be random element T, i.e, a measurable map : S2 - T with marginal probability law v. Then for any μ. E P(T) we have
E diam (T) f f./. (iim(())
1/p
log
dev(dt).
u(B(t,e))
Applying Theorem 8 to r* defined in (1) and then minimizing over we recover Ferniuue Talagrand type bound on the expected supremum of X,;
diam(T)
(l0g u(B(t,e))
1/D
E sup X₁ tT
E[X,-] & (T) + inf sup μEP(T) TET
de. (19)
9 Conclusion and future work
In this paper, we have presented unified framework for information iibommation-thoortiic generalization bounds based combination of two key ideas (decorrelation and chaining in the space of measures). However, our method has certain limitations, which we plan to address in future work. For example, it would be desirable cover the case of processes satisfying Bernstein-type (mixed 1/1 and v/2) increment conditions. It would also be of interest to see whether there are any connections to the convex-analytic approach of Lugosi and Neu [33]. Finally, since our method seamlessly interpolates between Fernique-Talagrand type bounds and information-theoretic bounds, we plan to use further develop the ideas of Hodgkinson al. [21]. who were the first to combine these two complementary approaches to analyze the generalization capabilities of iterative learning algorithms.
Acknowledgments
This work was supported by the Illinois Institute for Data Science and Dynamical Systems (iDS²), an NSF HDR TRIPODS institute, under award CCF-1934986. The authors would like to thank Matus Telgarsky for some valuable suggestions and the anonymous reviewers for pointing out some relevant work that was not cited in the original submission.
10

---

References
[1] Aad W. van der Vaart and Jon A. Wellner. Weak Convergence and Empirical Processes. Springer,
1996.
[2] Evarist Giné and Richard Nickl. Mathematical Foundations of Infimite-iimensionnl Statistical Models. Cambridge University Press, 2016.
[3] Michel Talagrand. Upper and Lower Bounds for Stochastic Processes: Modern Methods and Classical Problems. Springer, 2014.
[4] David A. McAllester. PAC-Bayesian model averaging. In Conference on Learning Theory, 1999.
[5] Tong Zhang. cormmattion-hhhorette upper and lower bounds for statistical estimation. IEEE Transactions on Information Theory, 52(4):1307-132 April 2006.
[6] Daniel Russo and James Zou. Controlling Bias in Adaptive Data Analysis Using Information Theory. In Conference on Artificial Intelligence and Statistics, 2016.
[7] Aolin Xu and Maxim Raginsky. tnferoition-theoreiiic analysis of generalization capability of learning algorithms. In Advances in Neural Information Processing Systems, 2017.
[8] Yuheng Bu, Shaofeng Zou, and Venugopal V. Veeravalli. Tightening Mutual Information Based Bounds on Generalization Error. IEEE Journal on Selected Areas in Information Theory, 1(1):121-130, May 2020.
[9] Fredrik Hellström and Giuseppe Durisi. Generalization Bounds via Information Density and Conditional Information Density. IEEE Journal on Selected Areas in Information Theory, 1(3):824-839, November 2020.
[10] Thomas Steinke and Lydia Zakynthinou. Reasoning About Generalization via Conditional Mutual Information. Xxiv:2000.00112: June 2020.
[11] Hassan Hafez-Kolahi, Zeinab Golgooni. Shohreh Kasaei, and Mahdieh Soleymani. Condition- ing and processing: Techniques to improve information theoretic generalization bounds. In Advances in Neural Information Processing Systems, 2020.
[12] Mahdi Haghifam, Jeffrey Negrea, Ashish Khisti, Daniel M Roy, and Gintare Karolina Dziugaite. Sharpened generalization bounds based on conditional mutual information and an application noisy, iterative algorithms. In Advances in Neural Information Processing Systems, 2020.
[13] Amedeo Roberto Esposito, Michael Gastpar, and Ibrahim Issa. Generalization error bounds via Rényi-, f f-divergences and maximal leakage. IEEE Transactions on Information Theory, 67(8):986-55) -00400 August 2021.
[14] Mahdi Haghifam, Gintare Karolina Dziugaite, Shay Moran, and Dan Roy. Towards a uni- fied information-theoretii framework for generalization. In Advances in Neural Information Processing Systems, 2021.
[15) Hrayr Harutyunyan, Maxim Raginsky, Greg Ver Steeg, and Aram Galstyan. Information- theoretic generalization bounds for black-box learning algorithms. In Advances in Neural Information Processing Systems, 2021.
[16] Ruida Zhou, Chao Tian, and Tie Liu. Individually conditional individual mutual information bound on generalization error. IEEE Transactions on Information Theory, 68(5):3304-331 May 2022.
[17] Jean-Y Audibert and Olivier Bousquet. Combining PAC-Bayesian and Generic Chaining Bounds. Journal of Machine Learning Research, 8332):8638889 2007.
[18] Amir Asadi, Emmanuel Abbe, and Sergio Verdú. Chaining Mutual Information and Tightening Generalization Bounds. In Advances in Neural Information Processing Systems, 2018.
[19] Eugenio Clerico, Amitis Shidani, George Deligiannidis, and Arnaud Doucet. Chained generali- sation bounds. In Conference on Learning Theory, 2022.
[20] Ruida Zhou, Chao Tian, and Tie Liu. Stochastic Chaining and Strengthened Information- Theoretic Generalization Bounds. In IEEE International Symposium on Information Theory, January 2022.
11

---

[21]
Liam Hodgkinson, Umut Şimsekli, Rajiv Khanna, and Michael W. Mahoney. Generalization Bounds using Lower Tail Exponents in Stochastic Optimizers. In International Conference on Machine Learning, July 2022.
[22] Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré. Gradient Flows in Metric Spaces and in the Space of Probability Measures. Birkhäuser, 2008.
[23] Cédric Villani. Topics in Optimal Transportation. American Mathematics Society, Providence,
RI, 2003.
[24] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities:
Nonasymptolic Theory of Independence. Oxford University Press, 2013.
[25] Roman Vershynin.
Probability. Cambridge University Press, 2018.
[26] Yury Polyanskiy and Yihong Wu. ing Learning.
Information Theory: Cambridge University Press, forthcoming.
From
Cod-
URL:
https://people middspeelids..o lids. mit cedu/yp/homepagee data////oo/aaitbookkk httt://gg/ooooggggaaaatttttbbooo www-eeepppttttoo
[27] Hao Wang, Mario Diaz, José Cândido Santos Filho, and Flavio P. Calmon. An information- theoretic view of generalization via Wasserstein distance'. In IEEE International Symposium on Information Theory, 2019.
[28] Borja Rodrígues- Gälvez, Germán Bassi, Ragnar Thobaben, and Mikael Skoglund. Tighter ex- pected generalization error bounds via Wasserstein distance. In Advances in Neural Information Processing Systems, 2021.
[29] Xavier Fernique. Regularité des trajectoires des fonctions aléatoires Gaussiennes. In X. M. Fernique, J. P. Conze, J. Gani, and P. L.. Hennequin, editors, Ecole d' Faé de Probabilités de Saint-Flour 19-4974, Lecture Notes in Mathematics, pages 1-96. Springer, 1975.
[30] Michel Talagrand. Regularity of gaussian processes. Acta Mathemutica, 159:99-149, 1987.
[31] Witold Bednorz. A theorem majorizing measures. The Annals of Probability, 34(5). September 2006.
[32] Witold Bednorz. The majorizing measure approach to sample boundedness. Colloquium Mathematicae, 239-2):005-227, 2015.
[33] Gábor I Lugosi and Gergely Neu, Generalization bounds via convex analysis. Conference on Learning Theory, 2022.
12

---

A Some elementary facts
We first list some useful inequalities for thp and 1/p". Note that the estimates may not be the sharpest, but they suffice for our needs.
Proposition A.2. For p 2 1 and æ 2 O, let vp(x) = exp(x*) - and ler 4/,'(x1)) (xx = (log(1 + 1)) be its inverse. Then we have the following:
(i) ///22/1/0) S 12(z))
(ii) 20p(2/4 2//2/p///2//////11/2
(ii) for x 2 0 and q 2 1, // (x9) S (1pppp (s).
(iv) For 2 1, 1/ (z) < (log(r))2/1++ +1.
Proof.
(i) For any 2
2x)(x) exp(>") - -1 (exp(x" /2) 1)(ex((=" + + 2 (exp(x"/2) (2) - 1)² = =
(ii) We only need to consider the case > 1 since otherwise the incquality is obvious. Since S 2(exp (Texp(y/4) + 1) for all y 2 1, we have
s 2 (c /4) + // s 2 ('xp((222//44)) 1) 2
(cxp(x*/44 /4) 1).
Then
(2/11/4440) x(exp(x²/4))
2 2cxp(' /4) 1)(cxp(xx/4)) /4) 1)
2)x((ep /2) 11)
21/2p(z\/2//1
(iii) Since x 2 and 2 1,
v (s.9 (log(1 19) (log(1 + x)))//e 1/ (x)).
(iv) When x 2 1,
x+1 log x + +12 log( + = log (0g)/((x) 12 S5 (x))
The following simple result is for converting between sums and integrals:
Proposition A.3. For any 2 2, K E N, and a continuous nonincreasing f (0, +00) + (0, +o0),
we have
K
f(r Sr L'' f(E) S x3 Er-kf(
(A.1)
k=1
k=0
Proof. Using the monotonicity of f, we have
K
K
K
f(r <
fr - 195(7 ST
ds
1-1
k=1
k=1
Sr (' f(E)de <r Σ f. f(c) de S 2 Σ -
f(r-)))
k=0
13

---

B Omitted proofs
B.1 Proofs for Section 2
Proof of Proposition 1. It follows from the inequality x: clog(1 + 1) v x log x + 1, x 2 0, that
dj log
dj dv dv
+1) =
dy de dv + 1.
log du
Using this and Jensen's 's inequality, we get
(u,0% 2//p
dH dv
M4
[og
du
+ 1) 1/m
dy
cd
+1) 1/p
Mr,
log
dv
du
du
1/p
v dv
log
+
du
du log dv
du
1/P
+ 1)
dv
(D(lllu) + +1) 1/8.
B.2
Prool's for Section 3
Proof of Lemma 1. To prove (4), we start with the Young-type inequality
ry S (z) + (y))
x,y 0
where
1 (x) = sup ry vp(w))
v20
the (one-sided) Legendre-Fencee Fenchel conjugate of u.p While a closed-form expression for u/g is not available, claim that bound it from above (x) s 2 2//r/,,'' (x). resulting in
xy S 22/p (x) + (1))
(B.1)
To establish the claim, we write
sup (zy (x(( sup (zy (e - 1) 1)) y2u
v20
and consider two cases:
if y S 2 (z). then
+1) 22 (x).
xy -
if 2 (x), then Applying (B.1) with
(ev0 1) +1) S (050 1)(y (600 + +1) ()) s 0.
da and y I gives
dp
dv < 2 2/1 dp w w-1 (
du dv (l)
so that
(9) ( (v, fg
du Tt
< v, (2//1/
du 1/ ddp
+ stp())))
dv
(vv)
= -2 (4, f ( ( + (v. f f()())))
14

---

To prove (5), define the event
du dv z
explo /4) (v, (xp(xp))))
E
Then, since (v, exp(g")) 2 1,
J Igdu - 42/1 / / (10gg
du
(v, (xpe(()()))) + +1)) 1/8 du
de
S / / f {log
dH
+ 1) + log(u, exp(e")) 1/8 du
de
s ///1 / f (log
(due + +1)) 1/0 du + 1/11/ / fdp. (loglv, cxp(o))) 1/P
(log(u, ( ///11|/fllrl (0 exp()))))( 1r. 14, f1/
/2/1 Nr
On the other hand,
J ge
exploe /4) - de Igdu < / 1g (u, (uxexp((PP))
$2 / exp(xe /2) de
(x,xxx((1))))
$2\/1|1f(l
where the first inequality is by the definition of F, the second inequality follows from Proposi- tion A.2(ii), and the third inequality is by Cauchy-Schward Putting everything together, get (5).
B.3 Prool's for Section 4
Proof of Theorem 1. subgaussian, so
It follows from the independence of Z1, Zn that gen is (a/ /n)-
Igen(w, S)] )
E 4/2
1 Vw W.
(B.2)
/666n
Using Lemma with Pwis. v Qw, f(w)) = a 66nn / and g(w) = Igen (mn.()
we have
o /66/n
(Pwis: gen(:,)))) 12o
(Bwiss 155
ddPwis dQw
)) (+ ahe
[gen(-,
0666n
Taking expectations of both sides w.r.t. Ps and using Fubini's theorem and (B.2), we get (6).
Proof of Corollary 1. Applying Proposition conditionally S gives
(Pwis: (dPWWs) S ((PwisllQw) + +1,
dQw
where the divergence D(Pwis sll@), being a function of S, random variable. Substituting this into (6) and using Jensen's inequality, the definition of conditional divergence, and Va + b Va + vb < 22(a b), we get
24g2 (D(PW sllQw Ps) + 4).
E Elggen(W (W, W, S
n
Taking the infimum of both sides w.r.t. Qw and using (2), get (7).
15

---

Proof of Theorem 2. For each fixed (w, 3), the random variable ò(w,, = E e 2/)
(w,=))) is ow,, susuuasannin where aww, 8)
(e(w,, f(w, )/) Thus,
8(w,,,e) 8,
8(w,
Ee(((w, 8, 8, Ee 4/2
1
v(w,3) 8)-
(B.3)
Voo 8)
Applying Lemma conditionally on (S,c) with μ P WIS6: Qwis f(w) ow, S), g(w) = ((w, S,e,, we obtain
P w Se. o(, ()(,,
2 V2 ( P ol.
w/SEe dQwis
( (, ()
+
(APrissnti ( wIS.e
[dPwin dQwis
)) + (Qw (2((((, (erisssaa((((())
(2]lA(5)]le=
Taking expectations of both sides w.r.t. S and e, then using Fubini's theorem, (B.3), and the inequality Ep Epllgen(W, ( S) < + E. S, e)], we obtain (8).
Proof of Corollary For any Qwis using Proposition 1, Cauchy-Schwarz, and the independence of (Z Z.), we have
[PP wiiss dQwis
Ep
|
P +
(')3 //EAA Pss)) 1).
Substituting this estimate into (8), taking the infimum of both sides w.r.t. Qwis- and using (3), we
get (9).
B.4
Proofs for Section
Proof of Theorem 3. Let
8(u, U,, = (((u,))) -(v,, (e(u,2) E(v, 2)).
8(u,0,)) = Σ 8(u, v, 21,4
C(u, u. 5) = 18(u, v)
(u,
For each fixed (u, v) 2 8(u, Z, 2j), < i are i.i.d. symmetric random variables. Therefore, introducing a tuple & = (E.,..., ,..) of i.i.d. Rademacher random variables indepen- dent of everything else and using the fact that the joint distributions of (5(u, v, Zi, Z)) 2- and (e:ō(u, v, Z4, ZD) 1=1 the same,
that
D E;ō(u, U, Z,, ZD)
([Wu(C(u, 5)) = EgEr
the
1
V6o v, S)
where the inequality follows from the fact that, conditionally on S and S", the random variables Li=1 Evō(u, v, Z4, 7 are au, v, SS-uuugaausiann
Now, given Qw P(W) and a family of couplings PovIS=s E Il(Pw]s==) Qw), it follows from the above definitions and from (10) that
V6 E Eggen W. S)) < V
(B.4)
16

---

Picking any PUV E P(W W) such that Puvis-a < PUV for E 2" and applying Lemma 1, we get
(t,
V dpuv )) + pov, a., ((, S)
((C,5)
$2 Prvis, ((,
v2
Using the inequality (/2 (/2(2)) (see Proposition A.2(i)), have
and (B.4),
((u, 5
E
ou, u, 5)
$ (u, 5)1,
V(u, u) EW x W.
V2
Putting everything together and taking expectations w.r.t. S and S', we obtain (12).
Proof of Corollary 3. For defined in Theorem 3, we have
(u, vu, S) < Σ (Alu, Z,) - l(v, z)))² + (e(u, 7:) - E(v, (1)))
Taking conditional expectations given V. S and using Jensen's inequality gives
V, < < VE.,P(UVVSSJUVv..
S V2n(dd(U,V) + +ds.
An analogous argument gives
(U, (,,VV V $ 2/nde(U, V).
Substituting these estimates into (12) gives the desired result.
B.5
Proof's for Section 6
Proof of Theorem 5. Using the definition of l, we have
K
Efgen (W,S) S)]
(e(Wk, 7,) -E(W6-1, Zi))
n
Applyng Lemma conditionally S with f(u,v) d(u, v), g(u, EEi
/nd(u.v)
μ = Pw.we_.1s and v 1 taking expectations w.r.t. Ps. and using (13) gives the desired result.
Proof of Corollary 4. For each k 2 let PWeWe-1 -We.a-r Then
dPwawa.ll d.w.w...s
dPs/WeWe- dPsswa
dPw.We- d(Pwaw._, Ps)
dPs
dPs
where we have made use of Bayes' rule and the fact that TT Wa-1lWi. Using this in (14) together with Proposition gives (15). An application of Cauchy- Cauchy-Schwarz and Jensen gives (16).
Proof of Corollary 5. For each 1, let pw-w Pwaw.. Notice that, by disintegration and the choice of couplings,
Eid Wx-1)] = E d(u, u)Pww .is(du, du) s E[W2(Pwalss Pw, .1s)],
where we have used the fact that W2(:.) dominates W1(:.) [23]. Since Pwis are points on the geodesic connecting Pwis and Pw, we have
K
K
W2(Pw.is Pw._,ls) = E(e Σ
(tx to W.ttt//W,(PPiss.. Pw) = Wa(PWss,PP).
A=1
Using this together with Cauchy-Schward and Proposition 1, we obtain (17).
17

---

B.6 Proofs for Section 7
Applying (5) conditionally on with f(w) 6/n, g(w) [gen( S.
Proof of Theorem 6.
/66/n
3 == Pwis, and v = Qw. we have
(Pwis, Iggn (W,
24 1 1/1
(dPWIs) )
gen (., (,,))
1/2
log Qw: exp
60² /n
n
Since f(w, 5) is hte/V//)suugaussiii for all Markov's inequality gives, for any
< 5 < 1,
P (Qw.exp exp
(.en((;))) 60² /n
2
(gen)(;:)) $ Ps Qw, exp
S 8.
8
602 /
which concludes the proof.
Proof of Theorem 7. The argument is almost identical to the proof of Theorem 3, with the difference that (5) used for decorrelation.
To lighten the notation, let केे := Pwaww-n and Pk: == W Use the same definitions of
5, o, Ç in the proof of Theorem 3. Then, applying (5) with f(-) a.. (). g(-) S(+, S), e T..
V = Pk: we have
d
(1, S /21|o(;,))l + T 0. ())
dpp
+2 ()) V log(pk: cxp (5)()
By Markov's inequality and the union bound, for any < 11
pkd
P l s.t. (px, exp (c² >
PRo Σ
Ps Ph. exp (52 1)) S
2
k
Using this together with the estimate (.,5) < 22 (.) yields the result in the statement.
B.7 Proofs for Section 8
Proof of Theorem 8. Without loss of generality, we assume diam(T) 1. Let Q be the Markov kernel from Ω to T defined by Q(-ww) = (-) in particular, v(.) = So. ((dl))((-lw))
Fix some 2 2. For each k 2 0 and each t E T, let Bx(t): = B(t,r-*), Since T is finite, there exists some E N, such that (I) = {1} for all T. Let μ E P(T) given. Define the following sequence of Markov kernels from Q to T:
Qx(+lw)== m(- B& (T())))) ([Bx(T(W)))
k=0...,,K K.
Observe that Qu = and QK = Q. Then, since
(TP 80 14, X) = Jaxr p(d)))(())) = ((d())(x.) - = =0,
can write
E E[X] ( Q X) (P
= (P QK - -P Q)
P Q+ - P Qx
Σ D (1, x( - /,, x((w)Qn- P(dw)
Σ
[Xa(w)
TXT
18

---

Applying (4) conditionally on with
f(u, u) = Ba(r(w)) (ro))
g(u, u) [a(w) - -x,(w]
d(u, v)
p(du, de) = Qu(dulw) @ Qk-1 v(du, du) = su(du) @ y(dv),
and using the fact that (+(-)) is supported on (x()(W) and Bx (T(T(w)) C Ba- (r))( we have
J (uulw) (d
[Xu(w) Xo(ww) u(du))(dv)
< 2/ - (TW))
+r h+1
vp
d(u,v)
TXT
- <22/pp 222/p ((BL)T(W)))
+r- k+1
STAT
Up
[K((w)= - Xo(w)]
u(du))((d))
d(u, v)
where the first term in the last step is due to Proposition A.2(iii). Then, using the increment condition and Proposition A.3, we have
K
K
[ 1/
E E|X, 2 22/9
(I(B(( v(d)) (H(B(t,))) de v(de).
k=1
k=1
< 1 + p
1/
Since 1/m(B((,s)) 2 1, we can apply Proposition A.2(iv) to obtain the inequality
S. (Log ((B((,,)))
1/P de v(dt)
E [X+] < 2
2 +
We can now take 2 to get the desired result when diam(T) = 1; the general finite-diameter case follows by straightforward rescaling.
19


Reviews:
[{"review_id": "ZGTTUjgNP4", "reviewer": "Reviewer_5Qrr", "summary": "This paper proposes a unified framework for deriving information-theoretic generalization bounds for learning algorithms. The main technical result relies on a probabilistic decorrelation lemma based on a change of measure and Young’s inequality in $L_{\\psi_p}$ Orlicz spaces. Combining it with other techniques, such as summarization, couplings, and changing the space of probability measures, new upper bounds on the generalization error can be obtained both in expectation and in high probability. The proposed framework also recovers many of the existing generalization bounds as special cases, including the ones based on mutual information, conditional mutual information, stochastic chaining, and PAC-Bayes inequalities. Strength: Lemma 1 provides a very general way to derive generalization error bounds in multiple setting, and it recovers many existing results as special case.", "questions": "Could the proposed framework recover the ICIMI bounds obtained in the following paper? In general, is it compatible with the individual sample technique used in [8] and [12]?\n\nZhou, Ruida, Chao Tian, and Tie Liu. \"Individually conditional individual mutual information bound on generalization error.\" IEEE Transactions on Information Theory 68, no. 5 (2022): 3304-3316.\n", "limitations": "The limitation has been addressed well in the confusion section. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The decorrelation Lemma 1 provides a very general way to derive generalization error bounds in multiple settings, and it recovers many existing results as a special case.", "weaknesses": "As the proposed bounds are not based on standard information measures, is there a way to evaluate these quantities even in some illustrative examples, like the mean estimation problem considered in [8] and [17]? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Since our decorrelation lemma can be used as an alternative to Donsker-Varadhan, it should be possible to obtain the ICIMI bounds using our approach since a key lemma used to prove these bounds also makes use of Donsker-Varadhan. Moreover, it should be possible to obtain the results of [8] and [12] proved using the approach of [14], which also relies on Donsker-Varadhan and random subsampling of the training data. The same technique as we used in our proof of the original CMI bound of Zakynthinou and Steinke could then be used to recover the main results of [14] (possibly with different constants)."}, {"review_id": "iVq3uUjhlT", "reviewer": "Reviewer_U1pj", "summary": "The paper presents a unified perspective of information-theoretic generalization bounds through decorrelation and coupling/chaining. Various existing generalization bounds in the literature are recovered or generalized via this perspective. The Fernique-Talagrand upper bound on the expected supremum of subgaussian processes also emerge as a special case from this framework.\n", "questions": "In the discussion after Theorem 3, the authors demonstrated the advantage of the theorem in the trivial case where W and S are independent. Are there more interesting (i.e. less trivial) cases where such an advantage can be demonstrated?", "limitations": "See weakness.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "\nI did not check carefully the proofs in the supplementary materials, but the presented results look sound to this reviewer. The paper offers a good service to the learning theory community for understanding information-theoretic generalization bounds and key techniques therein for their development. The development in this paper is original, to this reviewer. \n\nThe paper is also clearly written. I appreciate the authors' informal summary in section 1.1, making the paper easy to read.\n\n", "weaknesses": "On the minor side, the work appears to be limited only to unification, without aiming at developing novel and/or tighter bounds using the developed tool, despite that some bounds are stated in more general forms (e.g., Theorem 7) and some are shown to have certain improvement (e.g. Theorem 3). It would be much better appreciated if the authors can further demonstrate the power of their framework by presenting novel bounds of greater significance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "For Theorem 3: if the output of the algorithm does depend on the data, we have to choose suitable couplings and prior, such that the sum of the two terms on the right-hand side of (12) is minimized. We doubt that there exists a single procedure for finding such optimal choices in general cases (or even in ``less trivial cases''), but this is definitely an important direction for future work. Also, we use Theorem 3 to obtain results beyond the independent case. For example, via Corollary 3, Theorem 3 leads to the results of Section 6 (Theorem 4 and 5), which make nontrivial use of couplings beyond the case of independent $S$ and $W$."}, {"review_id": "U5ELqg1HKa", "reviewer": "Reviewer_7JF4", "summary": "This paper describes some steps of the standard formula to obtain generalization error bounds: (i) decoupling of the joint distribution + (ii) chaining. Then, they use this formula contributing mainly on the first front by deriving new decoupling results based on Orlicz $\\psi\\_p$-norms that can be cast into the standard decoupling results based on the relative entropy.\n\nAdditionally, they also include a section describing results based on couplings between the hypothesis' distribution obtained with the algorithm's kernel evaluated on a training set and the hypothesis' marginal distribution. These are used to develop their bounds on chaining, but they can stand alone independently.\n\nFinally, the authors note that their results can be extended to high-probability PAC-Bayes bounds and that these can be used to also recover bounds of the type of Fernique's and Talagrand's bounds on the expected supremum of a stochastic process.", "questions": "- I believe in the equations after line 379 there is an $f$ missing in the last equality.\n\n- I don't really follow the set of inequalities after line 381. Could you please clarify it?\n\n- Can (how does) this framework incorporate other advances in generalization error bounds based on mutual information like the single sample bounds from [8], [F], [G] or the data-dependent bounds from [H], [12], [F]?\n\n- How can we interpret the provided bounds? Can new results be obtained from them other than recovering the standard relative entropy-based bounds? Could you give some examples where the abstraction to Orlicz norms is beneficial to the analysis?\n\n**Additional References**\n\n[F] Borja Rodríguez-Gálvez, Germán Bassi, Ragnar Thobaben, and Mikael Skoglund. \"On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithm\". ITW. 2020.\n\n[G] Ruida Zhou, Chao Tian, and Tie Liu. \"Individually Conditional Individual Mutual Information Bound on Generalization Error\". IEEE Transactions on Information Theory. 2022.\n\n[H] Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M Roy. \"Information-theoretic generalization bounds for SGLD via data-dependent estimates\". NeurIPS. 2019.", "limitations": "The limitations of the paper are not generally pointed out in the paper (e.g. some of the questions and weaknesses above are not discussed such as how the extension to Orlicz spaces gives any advantage to the standard relative entropy and the decoupling lemma using Donsker-Vardhan).\n\nRegarding potential negative societal impact, there is no mention but there is no need to be as this is theoretical, fundamental research. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is generally well-written and easy to follow. It does a good work summarizing how to derive generalization error bounds using Orlicz norms and, therefore, using the relative entropy of the posterior hypothesis distribution $P\\_{W|S}$ with respect to a prior $Q\\_W$.\n\nTheir decoupling result (or \"decorrelation lemma\") is interesting and they gain clarity and interoperability by relaxing the tighter standard result they could have obtained with Young's inequality. I believe that Lemma 1 is the main result of the paper, which is later interpreted and contextualized into the generalization error set-up.\n\nIt is good that the presented bounds can be brought down (up to constants) to known bounds in the community. This is usually a necessary \"goodness test\" to know if the results obtained are valuable. Particularly, it was good to see that Fernique's and Talagrand's bounds were recoverable this way.\n\n[*Even though the strengths section will be shorter than the weaknesses, I believe this is a good paper. The authors should note that this will be the case only to help them improve the manuscript and to expand on each of the weaknesses so it can be easily addressed.*]", "weaknesses": "While their \"decorrelation lemma\" is novel and interesting, the applications of this lemma afterwards for the estimates using couplings, the usage of chaining in the space of measures, and the tail estimates are standard and shown otherwise with different decoupling lemmas (see e.g. [7,9,11,15,16,17,18] of the references of their own paper). While probably not on purpose, the paper seems to position itself as if it is introducing this set of steps to obtain this kind of bounds. This is not accurate, as these procedures have been used and done previously, just with a different (although maybe less general in some situations) decoupling lemma. I believe it would benefit the paper to make this clear both in the introduction and at the start of each of these sections.\n\nThe paper obtains results based on the inverse of an Orlicz norm of the Radon-Nikodym derivative of the posterior with respect to the prior. While this seems to be more general, the paper only gives examples of this instantiating into relative entropy-based bounds. In the end, it does not provide any example of anything new to gain by using their framework with respect to what was already known. This is not super problematic, but when the constants of the bounds are deteriorating under this framework, it is good to show that it can produce new results that lead to interesting conclusions.\n\nSimilarly to the comment above, the paper does not give examples or motivation to many of their bounds. For instance:\n- Why are the bounds using couplings useful? The paper mentions the fact that when the algorithm ignores the data, i.e. $P\\_{W|S} = P\\_W$ a.s. and the prior $Q\\_W$ is chosen to be the real marginal of the hypothesis $P\\_W$, then the resulting bound is exactly zero, which is not the case for the bounds presented in Section 4. However, the bounds in Section for are for the expected *absolute* generalization error, where the extra term $O(1/\\sqrt{n})$ is hard to avoid (or unavoidable in many cases). In Section 5, the bounds are for the expected generalization error instead, where the standard bounds (e.g. from [7]) already achieve a zero generalization error with this set-up.\n- Why are the bound using chaining useful? The paper basically uses the same techniques as [17] with their \"decorrelation lemma\". In [16,17] they come up with a slightly artificial example to showcase why their results are useful when compared to previous bounds. It is unclear if this technique provides any practical advantage to previous results, either in terms of obtaining bounds with a better rate in certain settings, in terms of interpreting the resulting bounds, or even in terms of simplicity to obtain actually computable bounds.\n\nThe paper does not discuss some relevant literature in certain parts of the text:\n-  In line 102 they state that they \"define the conditional divergence [...]\". This is a standard notation for the conditional divergence, sometimes credited to Verdú, although I am unsure which is the origin. Probably this is just a writing thing, but it contrasts with the previous introduction of the relative entropy where they introduce it with \"[...] is defined as\".\n- Even though the techniques employed are different, some mention to [A] would be interesting in the introduction and/or in the preliminaries. In this paper, they obtain PAC-Bayes bounds considering Orlicz norms with general Orlicz function, not necessarily $\\exp(x^p) - 1$.\n- In Section 5, it would be interesting to compare and/or mention other works that deal with the couplings of the posterior and the prior to bound the generalization error, e.g. [B,C,D]. In [C], for instance, they also mention the relationship of these bounds with chaining in Appendix A and with the relative entropy and subgaussian conditions in Appendix B.\n- In Section 7, it would be good to compare and discuss the work in [E] regarding chained generalization error bounds.\n\n**Additional References**\n\n[A] Amedeo Roberto Esposito, Michael Gastpar, and Ibrahim Issa. \"Generalization Error Bounds Via Rényi, f-Divergences and Maximal Leakage\". IEEE Transactions on Information Theory. 2021.\n\n[B] Hao Wang, Mario Diaz, José Cândido S. Santos Filho, and Flavio P. Calmon. \"An Information-Theoretic View of Generalization via Wasserstein Distance\". IEEE ISIT. 2019.\n\n[C] Borja Rodríguez-Gálvez, Germán Bassi, Ragnar Thobaben, and Mikael Skoglund. \"Tighter Expected Generalization Error Bounds via\nWasserstein Distance\". NeurIPS. 2021.\n\n[D] Ron Amit, Baruch Epstein, Shay Moran, and Ron Meir. \"Integral Probability Metrics PAC-Bayes Bounds\". NeurIPS. 2022.\n\n[E] Eugenio Clerico, Amitis Shidani, George Deligiannidis, and Arnaud Doucet. \"Chained Generalisation Bounds\". COLT. 2022.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "It is not the intent of our work to cover all existing generalization error bounds or even to replace existing approaches (many of which, as this review correctly points out, make use of various decoupling lemmas). Most of the additional references listed in the review are indeed very relevant, and we will cite and contextualize them in the final version.\n\nOur decorrelation lemma can be considered as an alternative to the Donsker-Vardhan lemma that allows us to work directly with the tails of Radon-Nikodym derivatives (or density ratios), rather than with various expected values, such as the relative entropy. Both the $\\psi_2$ function and the relative entropy arise naturally whenever one can engineer a subgaussian condition for a properly chosen centered process, say, by symmetrization techniques. This is often possible with minimal assumptions. However, under other tail conditions, it should possible to use a similar approach based on estimating Legendre-Fenchel conjugates to come up with different decorrelation lemmas to cover more general scenarios.\n\nThe benefit of using couplings is that we can actually relate the quantities on the upper bounds to an optimal transportation problem. Specifically, a common quantity in our bounds that rely on couplings is of the form ${\\bf E}[C(U,V)R(\\mu,\\nu)] + {\\bf E}[C’(\\bar{U},\\bar{V})]$, where $(U,V),(\\bar{U},\\bar{V})$ are random pairs in the hypothesis space; $C, C’$ are some cost functions, and $R$ is some functional of the density $d\\mu/d\\nu$; and $\\mu$ is data dependent, while $\\nu$ is not. Observe that the second term is the standard transportation cost under the law of $(\\bar{U},\\bar{V})$, while the first term can be thought of as information-weighted transportation cost due to the presence of $R(\\mu,\\nu)$, especially if we take $\\nu$ to a marginal of $\\mu$ (after averaging out the data). Thus, we can interpret $R$ as a functional of the ``information gain\" due to observing the data. We did not mention this perspective in the paper because the cost function would be somewhat exotic if we were view it literally in the context of a transportation problem. However, we do mention that the choices of couplings and priors are flexible, such that we may find an optimal coupling and prior for some particular cases. \n\nNow we briefly illustrate the benefit of using chaining in the space of measures. We consider the term ${\\bf E}[C(U,V)R(\\mu,\\nu)]$. When the posterior $\\mu$ is not absolutely continuous w.r.t. the prior $\\nu$, the functional of the density $d\\mu/d\\nu$ becomes vacuous. However, if we use chaining, then the term containing the density ratio is weighted by a distance-like quantity as long as we make sure that the entire summation (such as the summation on the RHS of Theorem 4) is finite. This is a much weaker assumption than $\\mu \\ll \\nu$. A relevant example is the Dudley entropy integral where we also have this multiplicative form $\\epsilon \\sqrt{\\log N(\\epsilon)}$. Here $\\log N(\\epsilon)$, the epsilon-entropy, will generally become infinite as $\\epsilon$ goes to zero, but this will not be an issue as long as the integral is finite. \n\nSome comments and answers to the questions:\n\n- We were certainly not claiming the definition of conditional divergence to be original; it is standard in the information theory literature, going back at least to the text of Csiszár and Körner. We should have been more consistent in using the passive voice (''is defined as\" rather than \n''we define it as\").\n- There is indeed a missing $f$ after line 379.\n- Clarification of the chain of inequalities after line 381: the first inequality uses the definition of $E$ to replace $g$; the second inequality uses the fact $1 \\le \\langle \\nu, \\exp(g^p) \\rangle$; the third inequality is due to $(a+b)^{1/p} \\le a^{1/p} + b^{1/p}$ for $a, b \\ge 0$.\n- Partial answers to the last two questions are addressed in the previous paragraphs."}, {"review_id": "MxteA9KOsf", "reviewer": "Reviewer_HuV6", "summary": "The paper studies the generalization error of the statistical learning algorithms from the information-theoretic point of view. In particular, by leveraging a “decorrelation lemma”, the authors show how various previously established upper bounds on the generalization error, including the common information-theoretic bounds, PAC-Bayes bounds, and chaining versions of them, can be recovered using this decorrelation lemma; and therefore, present a unifying methodology for establishing these bounds.", "questions": "The main ones are mentioned above. Some other minor typos/comments:\n\n-\tAlthough trivial but K and C are not introduced in line 93.\n-\tIn lines 120-121, it is claimed that “the right-hand side can be further upper-bounded in terms of the information divergence $D(P_{Y|X}\\| Q_Y)$ using Proposition 1.” Can it be done for any function $f(y)$?\n-\tTypo in line 141: $\\frac{|gen(w,S)|}{\\sigma \\sqrt{6/n}}$\n-\tThe proof of Theorem 5, or a comment on how it is derived seems to be missing.\n-\tThere are typos in the proof of Proposition 1;  after line 367, the LHS should be $\\frac{d\\mu}{d\\nu}\\log(\\frac{d\\mu}{d\\nu}+1)$. A similar typo exists on the first line after 368.\n-\tThe term “f” seems to be missing in the last line of equations after line 379.\n", "limitations": "Mentioned above.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The authors using the introduced decorrelation lemma managed to compactly recover various existing upper bounds on the generalization error. In particular, the method naturally can be combined with the chaining methods to recover a number of results such as the generalization bounds of Zhou et al., Asadi et al., and the bound of Fernique and Talagrand on the expected supremum of a stochastic process. Moreover, the work presents high probability bounds; which is rarely common in the information-theoretic bounds on the generalization.\n\nI believe the decorrelation lemma is a powerful technical lemma using which hopefully, new understandings and bounds can be achieved in future works. For this reason, I think the paper could be of interest to the part of the Neurips audiences that are interested in the theoretical understating of statistical learning algorithms. \n", "weaknesses": "1. The main weakness of the work is that it remains only at the technical level. \n\n-  1.a. The form of the general bounds, e.g. Theorem 3, does not seem to be easy to compute. It is not clear whether the general results can be leveraged to derive new bounds or to give a new understanding of the generalization error of the learning algorithms (in general or for a particular algorithm). Can authors provide cases where the results of this work give “new” and “simple” or \"practical\" results? I think the authors would agree that the justification of how coupling in Theorem 3 can be used to show that the expected generalization error is zero when $P_{W|S}=P_W$ is not convincing enough to show the utility of that.\n\n- 1.b. The only cases where these general results give concrete results are when they recover previous results (e.g. Information-theoretic bounds or PAC-Bayes ones) but only with the worst coefficients.\n\n- 1.c. Moreover, even at the intuition level, it is not clear if this work, and more specifically, this decorrelation lemma, gives any new “understanding\" of the generalizability of the learning algorithms. Does this work, and this decorrelation lemma, can provide any new intuition/understanding?\nFor these reasons, unfortunately, the paper remains only on the “technical level” and we can only hope that this interesting tool can be used for establishing new concrete results/understandings.\n\n2. The paper lacks a proper literature review and comparison with other works. Indeed, only 25 works have been cited; most of which are purely listed in the very short introduction. The authors are needed to widen the comparison of the current work with previous literature on generalization error (including different information-theoretic approaches, PAC-Bayes ones, compression-based ones, etc.) to make a clear picture of where this work/tools stand.\n\n3. As an example of the previous point, perhaps, as claimed by the authors, one of the main advantages of this work is the unifying methodology for deriving various existing bounds. This is indeed interesting, as has been done in some other works before. Non-exhaustive examples of some of these works, sorted by year, are: “PAC-MDL Bounds” (Blum and Langford 2003), arXiv:1912.01439, arXiv:2006.13057, arXiv:2105.01747, arXiv:2110.11216, arXiv:2111.05275, arXiv:2203.02474, arXiv:2303.05369. Although some of these works are less directly related as they consider different approaches (and some maybe are more directly related), I believe it is helpful to put this work in this context as well: how does the unifying approach of this work differ from previous attempts? What are the similarities? What are the “limitations” of those works and this one?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Regarding the decorrelation lemma: both our decorrelation lemma and the Donsker-Varadhan lemma use convex conjugate pairs to bound a product or an expectation of a product. The main difference is that, when using the decorrelation lemma, we can work with some functional of the density ratio $d\\mu/d\\nu$, which is a more primitive object and can be further relaxed into divergence-like quantities.\n\n- In lines 120-121, it can be done for any $f$ satisfying appropriate moment constraints, although Hölder’s inequality will be needed in general before invoking Proposition 1. We remark, though, that this statement should not be taken as a theorem, but as part of an informal discussion illustrating the use of the decorrelation lemma.\n- The proof of Theorem 5 relies essentially on the same argument as the one used to prove Theorem 4. We will clarify this in the final version.\n- Thank you for catching the typos in the proof of Proposition 1.\n"}]

Author rebuttal:
We would like to thank all the reviewers for their detailed and careful reviews. In fact, we wish all of NeurIPS reviews adhered to such a high standard! While we address the points raised by each reviewer in individual rebuttals, we would like to clarify a few points that were common to all the reviews.

The literature on information-theoretic generalization bounds is rather extensive and continues to grow. We thank the reviewers for mentioning a number of works we should have cited; we will do so in the final version and discuss their relation to other work whenever possible. We neither believe nor claim that all existing results can be unified under a single framework. The unification we speak of in our work is to ``effectively combine the information-theoretic approach with the classical framework based on various measures of complexity of the hypothesis class" (lines 29-30 in our paper). This can be (and has been) done in different ways; we believe our approach is valuable because it rests on a couple of simple but very flexible ingredients and because it seamlessly interpolates between classical bounds of Fernique and Talagrand and more recent information-theoretic results.

Also, here we would like to provide an example we did not include in the paper due to space limitations. This example may help to provide more intuition about our results, specifically with respect to the use of couplings as in Theorem 3.

Assume the loss function satisfies (13) as in Theorem 5. We take $Q_W = P_W$, take $P_{W_k|S}$ to be some points on the geodesic with respect to Wasserstein-2 distance with endpoints $P_{W|S}$ and $P_W$, and take $\rho_{W_kW_{k-1}}=P_{W_kW_{k-1}}$. Then there exist data-dependent couplings $P_{W_k W_{k-1}|S}$, such that

$$
{\bf E}[{\rm gen}(W,S)] \lesssim \frac{1}{\sqrt{n}}\left( {\bf E}[W_2(P_{W|S}, P_W)] + \sum_{k=1}^K {\bf E}[W_2(P_{W_k|S}, P_{W_{k-1}|S})\sqrt{D(P_{W_k W_{k-1}| S}|| P_{W_k W_{k-1}} )}]\right).
$$

Observe that the first term is the expected Wasserstein-2 distance between the posterior and the prior and the second term is a sum of  ‘’divergence weighted’’ Wasserstein distances. Also note that the form of the second term is in the spirit of the Dudley entropy integral, where the Wasserstein distance corresponds to the the radius of the covering ball and the square root of the divergence corresponds to square root of the metric entropy. We believe such a bound, where the Wasserstein distance appears without Lipschitz assumption on the loss function, is new. As far as we can tell, it is not covered by references [B], [C], and [E] brought up by Reviewer 7JF4.

Meta-review: The paper offers a unified perspective on information-theoretic generalization bounds by incorporating concepts of decorrelation and coupling/chaining. This perspective allows the recovery and generalization of existing generalization bounds in the literature, as well as showcasing how the Fernique-Talagrand upper bound on subgaussian processes emerges as a special case. The presentation is clear, and while the reviewers haven't extensively verified the proofs in the supplementary materials, the results seem sound. The paper's primary strength lies in its contribution to understanding information-theoretic generalization bounds and the techniques behind them.
Decision: Accept (poster)