Generalization Bounds via Conditional $f$-Information
Authors: Ziqiao Wang
Yongyi Mao
Venue: NeurIPS 2024 poster (2024)
Keywords: information-theoretic generalization bound
generalization
f-divergence
Primary area: learning_theory
TL;DR: We use novel methods to derive information-theoretic generalization bounds via conditional $f$-divergences.

Abstract: In this work, we introduce novel information-theoretic generalization bounds using the conditional $f$-information framework, an extension of the traditional conditional mutual information (MI) framework. We provide a generic approach to derive generalization bounds via $f$-information in the supersample setting, applicable to both bounded and unbounded loss functions. Unlike previous MI-based bounds, our proof strategy does not rely on upper bounding the cumulant-generating function (CGF) in the variational formula of MI. Instead, we set the CGF or its upper bound to zero by carefully selecting  the measurable function invoked in the variational formula. Although some of our techniques are partially inspired by recent advances in the coin-betting framework (e.g., Jang et al. (2023)), our results are independent of any previous findings from regret guarantees of online gambling algorithms. Additionally, our newly derived MI-based bound recovers many previous results and improves our understanding of their potential limitations. Finally, we empirically compare various $f$-information measures for generalization, demonstrating the improvement of our new bounds over the previous bounds.

Generalization Bounds via Conditional f -IIformmation
Ziqiao Wang
School Computer Science and Technology
Tongji University
Shanghai, China
zi ziqiaowangttonggi.coom edu. cn
Yongyi Mao
School Electrical Engineering and Computer Science
University of Ottawa Ottawa, Canada
ymaobuottaw..ca
Abstract
In this work, introduce novel information-theoreti generalization bounds using the conditional /-information framework, an extension of the traditional conditional mutual information (MI) framework. We provide a generic approach to derive generalization bounds via /-information in the supersample setting, applicable both bounded and unbounded loss functions. Unlike previous MI- based bounds, our proof strategy does not rely on upper bounding the cumulant- generating function (CGF) in the variational formula of MI. Instead, we set the CGF or its upper bound to zero by carefully selecting the measurable function invoked in the variational formula. Although some of our techniques are partially inspired by recent advances in the coin coin-betting framework (e.g., Jang et al. (2023)), our results are independent of any previous findings from regret guarantees of online gambling algorithms. Additionally, our newly derived MI-based bound recovers many previous results and improves our understanding of their potential limitations. Finally, we empirically compare various f-information measures for generalization, demonstrating the improvement of our new bounds over the previous bounds.
Introduction
Understanding generalization is longstanding topic of machine learning research. Recently, information-theerret generalization measures, e.g., mutual information (MI) between the input (i.e. data) and output (i.e. hypothesis) of a learning algorithm, have been proposed by [2-4]. While coermatiionthhorree generalization bounds have made significant progress in analyzing the generalization of stochastic gradient-based algorithms in nonconvex learning problems (e.g., deep learning) [5-13], they are found to have several limitations. One of the most severe limitations is their unboundedness, where the MI measure can be infinite while the true generalization error is small [14]. To mitigate this issue, various bound-tige tight-igggtniing techniques have been proposed [15, 6, 7]. Among them, [16] introduces conditional mutual information (CMI) framework. which allows for the derivation of a CMI-based bound that is strictly upper- bounded by a constant. In the CMI framework, the unknown data distribution. A Bernoulli random variable sequence is then used to determine the membership of training data from these two samples. Ultimately, the CMI between these Bernoulli random variables and the output hypothesis of the learning algorithm, conditioned on these two samples, characterizes generalization. This setup, known the "supersample" setting, ensures the
original MI-based
additional "ghost sample" is introduced alongside the original sample drawn from
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

boundedness of the CMI bound due to the constant entropy of a Bernoulli random variable. Intuitively, this CMI quantity leaks less information between data and the hypothesis, resulting in tighter bounds compared to the original MI quantity, as theoretically justified in [17]. Furthermore, several studies have aimed to further tighten CMI-based bounds. For example, previous tightening techniques in [15, 6, 7] are also applicable to CMI bounds [17-21]. Notably, another way to tighten the CMI bound is by utilizing variants of the original CMI quantity, such as functional CMI (f-CMI) [22], evaluated CMI (e-CMI) [16, 23]. and loss-difference CMI (ld-CMI) [24]. As the output hypothesis is replaced by the predictions, loss pairs, and loss differences of the two samples, these CMI quantities tighter than the original hypothesis-basee information theoretic bounds in the supersample setting focus on (conditional) mutual information measures, it is natural to ask whether there is general way to extend this CMI framework to other statistical distance/divergencee measures, such as other f-divergences.
CMI due to the data-procee processinn inequality. While most
Using alternative dependence measures to replace MI in information-thewwn has been studied in several existing works [25-30], with some of them considering the supersample setting. In particular, [26] provides some Wasserstein distance-based and total puriation-based bounds in the supersample setting. Furthermore, [29] proposes a general convex analysis- based framework that replaces the input-output MI quantity in [2-4] with any strongly convex function. While [29] itself does not discuss the supersample setting, the further extension in [30] indeed considers invoking the supersample setting to strengthen the bounds.
generalization bounds
In this work, we present a generic approach to derive generalization bounds based on conditional f-information, a natural extension from mutual information to other f f-dvergence-basee dependence measures. Our proof strategy is significantly different from the original CMI framework [16] and the convex analysis (or regret analysis) based framework [29, 30]. Specifically, our development starts from the variational representation of f-divergence, which involves the convex conjugate of convex function used to define the f-divergence. While the previous CMI framework focuses on upper-bounding the cumulant generating function (CGF) of a selected measurable function (which relates to the generalization error), we make a particular choice of such a measurable function, namely the inverse of that convex conjugate function. This choice makes CGF equal to (or upper bounded by) zero, hence eliminated from the variational representation. The remaining task is to lower bound this inverse of the convex conjugate function under a joint distribution. In the case of MI (or KL), the expectation of this inverse function is close to the log wealth quantity used in the coin-betting framework for obtaining concentration inequalities [31, 32]. Indeed, the lower bounding techniques here are inspired by some inequalities used in the coin-betting framework [31, 1, 32], and extend them to the cases of other f-divergence in the supersample setting. Notably, unlike [30, 1J, our conditional f-information generalization bounds do not rely on any existing regret guarantees of online learning algorithms. We discuss the connection with the coin-betting framework in Appendix E.
Given that f-divergences all obey the data-process processicns inequality [33]. we focus on using loss difference (ld)-based f-information, an extension of ld- dM-MI in [24], in this work. Specifically, our main contributions are summarized as follows: 1) In the case where the loss difference between data pair is bounded, we first provide a novel variational formula (cf. Lemma 3) for f-information, enabling us to derive conditional --information-based generalization bounds; For the KL case, we first provide an "oracle" CMI bound (cf. Theorem 3.1). This bound recovers many previous CMI bounds, including the square-root bound and fast-rate bounds in low empirical risk settings. also helps us understand the potential looseness of previous square-root CMI bounds, where some quantities that can vanish as the sample size n increases are simply ignored. Additionally, some novel fast-rate bounds are implied (cf. Corollary 3.1 133.2). Particularly, Corollary 3.2 contains a term in the form of the product of total variation and KL divergence, a similar quantity also appearing in a recent PAC- ACC-Bayesian bound [34]; 3) We present several other f f-information-buu based bounds, including the looser measure, X² -iiiformatioon (cf. Theorem B.2) and tighter measures, squared Hellinger (SH)- information (cf. Theorem 3.2) and Censen-Shanoon JS)-information (cf. Theorem 3.3). Due to the similarity in expressions, most arguments for our CMI bounds are also applicable to these bounds based on f f-information measures; 4) We extend our framework to the unbounded loss difference case, where we provide a refined variational formula for f-information (cf. Lemma 4. I), enabling us to provide novel /-information-base bound (cf. Theorem 4.1 for the case of KL). The obtained bound no worse than a previous information-theorees
generalization bound in [25] (adapted to the same supersample setting); 5) Empirical results show that the new bounds in our framework, particularly the squared
bound, outperform previous results.
2

---

2 Preliminaries
Notation Throughout this paper, adopt convention where capitalized letters denote random variables, and their corresponding lowercase letters represent specific realizations. Let Px denote the distribution of a random variable X, and Px y represent the conditional distribution of X given Y. When conditioning on a specific realization, we use Pxjr=y or simply Pxly- Additionally, we use Ex and Ep interchangeably to denote the expectation over X P. whenever it is clear from context. Moreover, Y (or E Exly) denotes the expectation over X ~ Px|Y=y-
Generalization Error Let 2 be the domain of the instances, and let W be the domain of the hypotheses. We denote the unknown distribution of the instances by μu, and let S = [Zz}== s.i,d be the training sample. A learning algorithm A. characterized by conditional distribution Pwis- takes the training sample S as the input and outputs a hypothesis W E W. i.e. A 2 - W. To evaluate the quality of the output hypothesis W, we any hypothesis w, the population risk is defined as L A Ez [e(w, Z') where Z' f is an independent testing instance. In practice, since is unknown, we use the empirical risk, which is defined as (w) 1 E lw,, Zi), as proxy for the population risk of w. The expected generalization error is then defined (A) A Ew [L, (W)) Ew,s [W)]
loss function E W 2 TR.-- For
Supersample Setting We follow the traditional supersample setting introduced by [16]. Let an n 2 matrix Z E g be the supersample, where each entry is drawn i.i.d. from the data distribution We index the columns of Z by {0, 1}. and denote the ith row of Ž as Z, with entries (Z... 1, We use U {U Unif( (0, 1))).. independent of Z. determine the training sample membership from Z. Specifically, when U, = 0, Zi.o in Z is included in the training set S, and Z,, is used for testing; U, = dictates the opposite case. Let U, = 1 - U, the training sample S then equivalent to Zu = { Pi and the testing sample is Zy = [Z,,,, H Additionally, we let Li,0 A <WW 74,0) and define L1,1 similarly. Let AT; = T1,11 I4,0 be the loss difference in the ith row of Z. To avoid complicated subscripts, also superscripts + and replace the subscripts O and 1, respectively, namely, Z Zeo. z 1, L I and L I.,1 Furthermore, we define G, & (-1)%, AL, i.e. the testing loss minus the training loss at position Clearly, E Gj is unbiased estimator of (A). In other words, (A) = - Ear,,,, ., [G.].
F-Divergence and fInfoommaiinnn The family of f- f-divergence is defined as follows.
Definition 2.1 (J-divergence [33]). Let P and Q be two distributions on O, and let & .R+ + IR be a convex function with @(1) If P < Q then the f-divergence between P and Q is defined as
dP
(o(1)) & EQ
dQ
where dP is Radon-Nikodym derivative. aq
A variational representation for f-divergence, as provided below, has been independently investigated
in previous works [35, 25, 36, 37, 33]. Recently, this variational representation has also been applied to PAC- AaC-BByeiian generalization theory [38] and domain adaptation theory [39, 40].
Lemma 2.1 (137, Corollary 3.5)). Let o² be the convex conjugate' of Φ. and G = {g : 0 -
dom())) } The following, known as variational formula of f-divergence, holds:
D& sup Ea-r [g(()) gEG
inf (Ea-Q (d5 (g(0) + X)] A}- XER
Following [33, Section 7.8), let (x(X; Y) & (Px. Py: be the f-information, which extends the standard mutual information (MI) defined in terms KL. divergence.
We now set 0 (ALi, U.) and g g(A,, U.) = tG, in Lemma 2.1, where t E P. P PA is the joint distribution of (AL;, U.) and Q PAt, Pv, is the product of the marginal distributions. Consequently, Lemma 2.1 directly implies that
For function X RU (-00, +oc). its convex conjugate is f"( A suP (2, f(x).
3

---

To(AT,;U)) + inf { T (0 (1(-)) At; + 20] - -
Ep [G:] < inf &
(1)
AER
inf teR t
[o( U.) + EQ (t(((_1)":
(2)
where we let À = 0 in Eq. (2). Notice that if σ(x) = x log + c(x 1) for any constant then (X; Y) becomes MI. In this case, the optimal A = -log Bqq [e9(0)] in Lemma 2.1, and Lemma 2.1 recovers the Donsker and Varadhan's variational formula (ef. Lemma A. Here, the second term in Eq. (1) represents the cumulant generating function of (AT,, U.). By analyzing the tail behavior of (AI,, U.) and applying Eq. (1), one can derive the final MI-based generalization bound. For example, if the loss is bounded, Eq. (1) recovers [24, Theorem 3.2] by using Hoeffding's Lemma.
On one hand, while Eq. (1) is tighter than Eq. (2), the parameter À may not have an analytic form for divergences beyond KL and x². In this sense. Eq. (2) has its own merits. On the other hand, previous MI-based generalization bounds use concentration results to further upper bound the second term in Eq. (1). While this strategy has been successful for the MI case, for instance by using Hoeffding's Lemma, it may be challenging to obtain similar concentration results for other f-information. In this work, we introduce a novel approach to prove generalization bounds for f-information.
Conditional fIIformmation Bounds: Bounded Loss Difference Case
We begin by presenting general lemma that will serve as main recipe for obtaining generalization bounds in this section. This lemma introduces a new variational formula for f-divergence, which may be of independent interest beyond the context of generalization.
Lemma 3.1. Given random variables X, Y, and measurable function f for (). For every t E (b1, b2] C R. assume that o' is invertible within the range of t ff, which we denote by Т, Let 6" be the inverse of ø= on Ute(h dor and let Y' be an independent copy of Y. If
Ex,y' [](X, Y") = 0, then
sup Ex,y (t" S S (X(;Y). xe(b).0g) Aa]
Although Lemma 3.1 is a simple and straightforward result derived from Lemma 2.1 by setting g = Ø- (tf). it is quite powerful for deriving f-information-bast -ased generalization bounds. Specifically, in the supersample setting, due to the symmetric properties of two columns of Z, we set X = AL; Y = U, and f(AL;, U?) = (-1)²² AL; (where U/ is an independent copy of U:), the condition Lemma 3.1, namely Ex,y" [S(X, Y 0, clearly met. Then we have
sup BAL,U, - (1G.) S Is (.L;
After carefully choosing b1 by such that 0011 is well defined, the main focus is to find lower bound for the function o* over a certain interval. We will start with the standard MI case.
3.1 Mutual Information (KI.-based) Generalization Bound
Consider dxx) = x log + 1. Its convex conjugate function is o² (3) et with the inverse (2) log(1 2). Building upon Lemma 1. we obtain the following bound:
Theorem 3.1. Assume the loss difference É(w, 21) E(w, 22) is bounded in [-1, 1] for any W
and 21, 22 E 2, we have
(, Σ 2[ + | (AL;;
We remark that bounded loss difference is less restrictive assumption than a strictly bounded loss. For example, if is L-Lipschitz in the second argument, then l(w, 21) [(w, 22) I L||21 22

---

Thus, as long as ||21 22 pellis is bounded, the loss difference is bounded even when & itself is unbounded. Additionally, we refer Theorem 3.1 as the "oracle" CMI bound because the upper bound itself includes the expected generalization error at position i, E [Gi], which is precisely the quantity we aim to bound.
From Theorem 3.1, first, if we simply upper bound the loss difference AL; (and G,) by one, Theo- rem 3.1 recovers [24, Theorem 3.2] up a constant. More importantly. Theorem 3.1 indicates that in the case of bounded loss difference or bounded loss, solely using / (AL;; U.) as the generalization insufficient accurately characterize its generalization error. Specifically, when 2 [E AL?] + IE [l) vanishes as n increases, relying on the MI-based measure alone, i.c.,
measure for algorithm
VI(AL; U.). will always result in slow convergence rate for [ (A)). While similar observations have been made in recent studies [41-43], where it is found that the sub-Gaussian variance proxy in previous MI bounds may also vanish in some examples, our Theorem 3.1 provides a more straightfor- ward understanding of the potential looseness of O (( (AL; U,)). Additionally. further discussion comparing our oracle CMI bound with the MI-hased results in [29, 30] is provided in Appendix B. 4.
To highlight the differences in our proof techniques compared to previous informmtiion-thoreeee generalization bounds, we provide a proof sketch below.
Proof Sketch of Theorem 3.1. Lemma 3.1 gives us [(AL; 2 sup; E [log (1+t(-1)u4 [L)]] Let (xx) log(1 (1++) - ax. and set
|E[G.]
By demonstrating that [(x) holds when
2
G
2 and |x|| S 1 2n we have sup E3
llg (1 + +G.
2 - E [tG at G:)
The supremum is attained when t*
E[G,]
E
which is achievable. Therefore,
2n G
|B[G.||+E c
I(L4; U4) 2 supre(-1,tox) EAL.U. log -1+ 11+t(-1) t(-1) A.)
which simplifies to daE [aE|G:]
R G.
E E2 S
[E [G,]| - (G (()L;U)).
The remaining steps are straightforward. See Appendix B.1 for the complete proof.
also worth noting that by letting g = 0-~1 and IEq [g] = 0 in the case of KL divergence, we obtain X 0 in Lemma 2.1. As result, Eq. (2) becomes equivalent to Eq, (1). In this sense, starting
from Eq. (2) does not compromise the tightness of Eq. (I). Moreover, the proof provides deeper
insights into the tightness of Theorem 3.1, which we will now discuss.
Small Empirical Risk Case or Realizable Setting Previously, fast-rate information-thcoreee generalization bounds in the realizable setting setting-where where the square-root function is removed have been derived by demonstrating that the CGF can be negative [16, 44, 23, 24], or by invoking the channel capacity result of the binary channel [44, 24].
Based on Theorem 3.1, 1, the square-root funetion can be directly removed in the realizable setting. Specifically, if the learning algorithm A is an interpolating algorithm, i.e., the training loss is always
minimized to zero, then G3 E [0, 1] always holds. In this case, [E [G&]] = E [G,] and E G I E [G.], allowing us obtain [G,]] < (L;;; U.) from Eq. (3). Consequently. Theorem 3.1 simplifies to (A) < Σ 1= I(A;; U.). Note that for this bound to hold, the condition of zero training loss
can be relaxed to the training loss being always no larger than the testing loss.
Furthermore, to achieve a better constant in the bound, observe that the proof of our Theorem 3.1 utilizes the in-
equality log + x) 2
az² for [r| < 1
If E [0, 1] always holds, one can use the inequality log(1 + x) 2 x log in- stead, where equality holds when the loss is zero-one loss (See Figure (Righht) for visualized illustration).
1
8
8
2n
21767-1
3.1
Figure 1: Comparison of different 6-11 (Left) and examples of x- ax for bownribon log(1 11 æ) (Right).
5

---

As result, we obtain 5
> llgg which is tighter than the previous bound and will never be vacuous (i.e. the bound is always smaller than 1) since T T(AL;; U.) I HUU) log 2. In fact, this bound can exactly characterize the generalization error (i.e., equality holds) if the loss is the zero-one loss, demonstrated in [24, Theorem 3.3].
HALU))
New Fast-Rate Bounds Theorem 3.1 not only recovers the previous fast-rate Id-CMI bound in the realizable setting but also introduces new fast-rate bounds.
By solving Eq. (3) for [E [G.]l, we obtain the following bound.
Corollary 3.1. Under the conditions of Theorem 3.1, we have
(E((A)) S
21(AL;U)) + (2TALE)(AL;U3)
This fast-rate bound has not been proved [24], yet resembles [24, Eq. (2)) in structure. Specifically, the single-loss MI term, ;T( U.) in [24, Eq. (2)], is now substituted with 7(A7;;; Us), and the empirical risk term, E [W)) is replaced by E [AL]]. Here, AL, Li LT= and notice that both LTT and L follow the same marginal distribution due the symmetric construction of the supersample, so 4 (Vrr(Lt). Consequently, Corollary 3.1 further implies the following bound:
obtain that E [ E [ T,+ 4E [(T, E [
(x)) S - Σ (2I(A):))) + +2/2 (4T) I(AL.U)))
(4)
Notably, Eq. (4) hints that if the variance of the single loss in the supersample is sufficiently small, the bound will decay the same rate in the realizable setting, namely ((T(AT;; U.)), ) the second term vanishes.
Instead of solving Eq. (3), if we directly upper-bound |E [Ga]] in Theorem 3.1, we can also obtain the following bound from Theorem 3.1.
Corollary 3.2. Under the conditions of Theorem 3.1, we have
1 T1 Σ
(VEE U.) + /2 [DTv (PALIU,, PAL.))
(A))
Note that Corollary 3.2 is tighter than Corollary 3.1 by Jensen's inequality and Pinsker's inequality. While we focus on the MI-based or KL-baase generalization bound in this section, the inclusion of total variation (TV) in the second term of Corollary 3.2 expands the scope of the bound. Notably, in recent study by [34], component of the form DTyy-DKL is also present in their generalization bounds. Specifically, they derive PAC-Bayesian generalization bounds using the -htang-Cutkosky Paschalidis (ZCP) divergence, initially explored in [45]. Interestingly, the ZCP divergence can be further upper bounded by O D(V + Drv). Although it remains uncertain whether the first term in Corollary 3.2 is tighter than DrV or not, we demonstrate that the component /Dry can emerge directly in the derivation of KL-based bounds, without using the 7CP divergence. Additionally, note that the term E AL?] in Corollary 3.2 can likewise be replaced by 4 4Var(L) term.
3.2 Other --nooormttionnbaaseee based Generalization Bound
Based on Lemma 3.1, it is straightforward to apply similar techniques to many well-known f- divergences or /-information measures to obtain generalization bounds. this section, we dis- cuss several other /-iiformmtionn-aaeeee
bounds. Before we study the specific f-divergence, we remark that, in Section 3.1, our focus was on the unconditional mutual information T(AT;;; U,). As illustrated in [24], using the data-procsssing incquality (DPI) and the chain rule, we have I(AL; U. < I[LØ L, U,)
([WU,,)Z)) This makes it easy to derive other CMI variant- based bounds. While other /-divergences also satisfy DPI, they may not adhere to the chain rule. Accordingly, for these cases, we use the disintegrated conditional j-information, defined as Y) |
(noting that I(X; Y|Z) Ez [ (X:Y)) ), instead of the unconditional quantity. In this context, at least Ts (A U.| S (W; U. 7,) still holds, ensuring that the hypothesis based conditional f fiinformation bound can be directly derived.

---

X²2 based Generalization Bound Consider 6(x) = (x - 1)). Its convex conjugate is 6 (v) =
_²= + y. For y 2 -2, the inverse of conjugate function (²) 2(v2 + +1 1) exists. Since 2(v=+ 2 log(1+2) any lower bound that holds for log(1+2) will also hold for +
T
See Figure 1(Left) for visualization. In other words, all the bounds in Section 3.1 will also hold when using x² <2-divergence. This can also be immediately noticed by the inequality DKL. (PII)) S
Q)) [33]. We defer the formal disintegrated x d--information bound in Appendix B.7.
Squared Hellinger (SH) Distance Generalization Bound Consider <(x) = (VT - 1)3, and its
convex conjugate is 6 (v) , For y (-o0, 1). the inverse function (-) - exists for E (-1,+00), We then have the following oracle conditional squared Hellinger iSf)-information bound.
Theorem 3.2. Under the same conditions in Theorem 3.1, we have
[e,(A)) 3 EE
Ez,
4E A
+ B G.
1 (AL; U.),
[=1
where (HL; U:) = DH² (PAL, || PAL, 12, Pu.)) is the (disintegrated) SH-information.
Given that DHi (PIIQ) S Drv (P,Q), the TV-based bound can be derived corollary from above.
(JS) Divergence Generalization Bound Consider d(x) x log
2z + log 2
I+z
I4
with the convex conjugate x'(v) (v) = - log(2- - e²). For y < log 2, the inverse function (z) log(2- e=) exists for = > log 2. This leads the following oracle JS-information bound. Theorem 3.3. Under the same conditions in Theorem I. we have
Ex(A)) - 2
Ez
V
4E
AL31
E
24 AL; U.), G.I
where (AL U.) = DJSD (PAL, Po.) is the (disintegrated) JS- JS-information.
Jeffrey's divergence [46], which is defined as DJeffrey (PI A DKL (PIIQ) + DKL (Q1IP), is an
f-divergence with the convex function Φ(x) = (x 1) log Since DJSD (PIQ)) < DJeffrey (PI Q) [47], a Jeffrey's divergence-bart based bound can be derived as a corollary from Theorem 3.3 (and clearly,
also from Theorem 3.1 due to the non-negativity of KI. divergence).
Notably, Theorems 3.2-3.3 share similar expressions with Theorem 3.1, and deriving analogous corollaries to Corollaries 3.1-3.2 is feasible (see Appendix B.7).
In the proofs of Theorems 3.2 and Theorem 3.3, we continue to use x ax to lower bound the inverse of conjugate functions z and log(2 - E E for SH-information and JS-information, respectively. 1+- However, due to the complexity of handling log(2 - -)² in the context of IS-information, we opted for a much rougher selection of the parameter than in the proof of Theorem 3.1 for simplicity.
Consequently, the constants in Theorem 3.3 are not optimal and can be refined with more fine- grained analysis.
4 Extension to Unbounded Loss Difference
Previous bounds are typically applicable when dealing with bounded loss differences (albeit not necessarily within the range of [-1, , 1D. This limitation arises from the fact that the function ø--1 may fail to exist in Lemma 3.1 when f is unbounded, regardless of any non-trivial adjustments made to the range of t. To overcome this limitation, we now extend our analysis the case of unbounded loss differences by refining Lemma 3.1. One crucial modification to Lemma 3.1 involves defining the measurable function g = t 1 1 for some C 2 O, where is the indicator function.
We present the following lemma tailored for unbounded functions.
Lemma 4.1. Let X be arbitrary random variable, e be Rademacher variable, and t E (-b, b). Assume that there exists a constant C 2 0 such that 0² is invertible in (-bC, bC"). If (0) = 0, then
sup Ex.e [0- (teX) L[xise] < Ix(:=)).
tE(-b,))
7

---

Note that (0) = 0 is satisfied by all divergences discussed in Section 3. Armed with Lemma 4.1, our proof strategy hinges on separately bounding the truncated terms E [G, [[|cc]] and E [G, 1 [[x]sc]. To achieve this, we utilize Lemma 4.1 along with similar lower-bounding techniques as detailed in Section 3 to bound the first term. For the second term, we invoke Hölder's inequality, drawing inspiration from prior works such as [25, 27].
Before presenting the refined bound for unbounded loss difference, we introduce some additional nota-
tions. Define the Lp norm of a random variable X ~ Pas | (Ep XII) for p (o),
ess sup |X] for p = 0o,
where ess sup |X| e [nf : P([X) > M) 03 is the essential supremum. Furthermore, let the f- divergence generated by the convex function (x)x = |r 1 be Do.. (PIIQ) _ Eg [ d4
This divergence, which takes x²-divergence and total variation as special cases (with a 2 and = 1, respectively), and it has been utilized in previous information-theoree generalization bounds [25, 29, 30]. We denote the corresponding f-information of De.. (PIIQ) as Is..
Now, we are ready to present a MI-based bound, with straightforward extensions to other f- information measures.
Theorem 4.1. For constants C 2 0, 2 1, and a E [oo] such that 1 + 3 = denote
G = /2 (E |c + C [G. [aL]K]]] and C2 = (P((AT)) > C)) |
=1
we have
(x,(A)) < inf 1 Σ (VIIAAL + C2 V 1o. (AL:: Ui)
C.g.. T
Since Ug is a Bernoulli random variable, according to [25, Lemma I]. we know that Lo. (AL; Ut) <
1 - 20-1 for a E [1, 2] and remains bounded for other values of a as well. Thus, Theorem 4.1 generally preserves the boundedness property of the original CMI bound unless AL; has an infinite Too-n Additionally, due to truncation, E S V2C for any given C, while C2 heavily depends on the tail behavior of AL, ~ PAr., (or G. ~ Pet PaL: equivalently). We now discuss several common
cases.
Bounded Loss Notably, Theorem 4.1 also covers the bounded loss cases. For instance, if & is bounded in [0, 1] a.s., setting C 1 in Theorem 4.1 leads to S2 = 0, directly recovering Theorem 3.1 for bounded loss. In fact, the choice of C = 1 might not necessarily be the optimal for i E [0, 1]. Particularly, for certain C' E (0, 1), we let 1 and B = co, then (2 ||LLi||> boo and (Te., (AT,; U/ = TTv (AT U.). Since Drv I vDKL by Pinsker's inequality, this alternative choice holds potential for even tighter bounds than Theorem 3.1.
"Almost Bounddd Loss When the loss function exhibits sub-Gaussian or sub-Gamma tail behav- iors, the probability P(G.a) > C.) decays rapidly. By carefully selecting the threshold C, the domi- nance of the first term in the bound can be expected. Assume the loss difference AT, is sub-Gaussian
with certain variance proxy, say, a. Setting C = a and g = 2, we have P( > C) S 2e-1
and || ALاlla S Vạža [48]. Consequently, each term in the summation of Theorem 4.1 simpli- fies to O ((0 (TVT(AL:; U.) + (2e)
a- a VTo. (AI,; However, the relationship between I (AL U.) and Lo., (AL;; U.) is not clear beyond the cases of
and 2 (corresponding to total variation and -iiformmaiinn, respectively). Studying the overall behavior of the bound represents an intriguing direction for future research. Furthermore, consider the alternative case with C' 0 and 1, where the first term in Theorem 4.1 becomes zero. The second term, using ||LL Z /B for sub-gaussian random variables, becomes O0
Vlo. (AL;; U.)). Com- pared existing MI bounds, e.g.. Ola ((AVT(AL) U.)), we know from DTV (P, S DDKL. (PIQ) and DKL (PIIQ) < x²(ll()) that Lo, (AL; U.) S VI(AL. & V (AL U.), suggesting that some E (1,2) 2) may yield a tighter bound than MI.
Heavy-tailed Loss Heavy-tailed losses, although lacking universally agreed definitions, typically refer to the cases where the -enerttgene function (MGF) does not exists (away from 0) [49].
8

---

Remarkably, our Theorem 4.1 remains meaningful for such losses since it does not rely on the existence the MGF of the loss function. Specifically, without any additional knowledge about the tail behavior of ATa we have the following result from Theorem 4.1.
Corollary 4.1. Under the conditions in Theorem 4.1, let q3
9-1 we have
(A)) v Σ ( ) (V2I(AL:U.)
(IAWIRIAAL 180 V Tau (AL;; U;)
It's worth noting that as 7 0 (i.e. 9 - 1), we can see that (yste + 4071
_ 1. Consequently,
in Corollary 4.1, the bound simplifies to J > (IALills V To. (AL; This is an extension
of [25, Theorem 3], incorporating individual techniques [6] and loss-difference methods [24] in the supersample setting. Notably, our Corollary 4.1 improves upon [25, Theorem 3], as r - 0 may not necessarily be the optimal choice. Furthermore, it is also intriguing to investigate whether our Corollary 4.1 can recover [29, Corollary 5J.
5 Numerical Results
In this section, we conduct an empirical comparison between our novel conditional f-information generalization bounds and several existing information-theorreie generalization bounds. Our ex- perimental setup closely aligns with the settings in [24]. In particular, we undertake two distinct prediction tasks follows: 1) Linear Classifier Synthetic Gaussian Dataset, where train simple linear classifier using a synthetic Gaussian dataset; 2) CNN and ResNet-50 on World Datasets. The second task follows the same deep learning training protocol in [22], involves training& a 4-layer CNN on a binary MNIST dataset ("4 vs 9")) [50] and fine-tuning a ResNet-50 model [51], pretrained ImageNet [52], on CIFARIO [53]. In both tasks, we assess prediction error as performance metric. That is, we utilize the zero-one loss function to compute generalization error. Note that during training, use the cross-entropy loss as a surrogate enable optimization with gradient-based methods.
0.8
0.25
Encr
CHyCrecid
CSHEDraden
1.0
0.20
COHENNII
CSilkarr
0.15
0.4
16:C9
0.6
Sharpress
0.10
CSC
0.4
Bisar
0.05
0.0
100
150
200
250
300
150
200
0.00
75
250
1000
4000
Linear (Two)
(b) Linear (Ten)
(c) CNN (MNIST)
0.25
CP3Crecs
0.10
C4100ade
0.12
codi1rade
0.06
0.10
0.20
0.08
0.06
0.04
0.10
0.02
0.05
0.02
0.00
1000
5000
20000
10
Epochs
Epochs
(d) ResNet (CIFARIO)
(e) SGLD (MNIST)
(I) SGLD (CIFAR1O)
Figure 2: Comparison of bounds on synthetic dataset, MNIST ("4 vs 9"), and CIFAR10. (a-b) Linear classification for two-class and ten-class data. (c-d) Dynamics of generalization bounds as dataset size changes. (c-f) Dynamics of generalization bounds during SGLD training.
The comparison of generalization bounds mainly focuses on those presented in Section 3. Specif- ically, we consider the oracle bounds, given in Theorem 3.1, Theorem 3.2, and Theorem 3.3, which we denote as OMacOralle,, Orace,, and CJSI(Oracle), respectively. Given that the

---

squared Hellinger-information information is a tighter measure than MI, and the constants in Theorem 3.2 ex- hibit less pessimism compared to those in the JS-information bound, we introduce two additional squared Hellinger-information bounds for comparison. The first one, akin to Corollary 3.2, is
(A( - n - / (4E[ALØ] + 2E Drv (PAI,IU,, Par. 21 )1) (AL;))) (cf. Corol-
lary B.1 in Appendix B.7), denoted as CSHI( (Var). The second one adopts a more pessimistic choice by replacing E [ with the constant 1, labeled as CSHI( Worst). Additionally, we include three previous coommation-theoretti generalization bounds as baselines: the original Id-CMI bound in [24, Theorem3.1 I] (ld-CMI), the sharpness- based single-loss MI bound in [24, Theorem 4.5] (Sharpness), and the binary KL-based CMI bound [23, Theorem 5] (Binary kl). Further details on experimental settings are available in the Appendix D.
The final results are shown in Figure First, we observe that for the linear classifier on the two-class data (Figure 2a), most bounds are close to the exact generalization error, with Sharpness being the tightest. Note that the sharpness-based MI bound in [24, Theorem 4.5] is applicable solely for zero-one loss. As the prediction task becomes more complex (Figures 2b-2f), our squared Hellinger- information-basee bounds are the tightest. Specifically, the squared rellingrr-infomatioon bbsedd bound is always tighter than the CMI bound in the oracle type. Notably. CSHI( Var) also outperforms all other f f-informationn-iat -baee bounds in these cases, and even the pessimistic CSHI( Worst) bound outperforms them, except for Sharpness, in Figures 2c-2d. Additionally, by comparing CMI(Oracle) and (dIMMI, we see significant potential for improving the original Id-CMI bound. Finally, although the IS- iS-information bound contains relatively pessimistic constants, it still outperforms some MI-based bounds in many cases (e.g., Figures 2c-2e). These observations suggest that considering alternative f-information rather than MI is indeed necessary for studying generalization.
6 Other Related Works and Limitations
In addition to the studies mentioned previously, there have been recent developments in information- theoretic generalization bounds in the supersample setting. For example, [54, 44] propose a "leave- one-out" (LOO) construction of supersamples, reducing the size of the supersample from 2n to 1. Additionally, [55] constructs of a hyypohheiis-condiiione CMI bound. The key component in this bound is the product of the new CMI term and algorithmic stability parameter. Furthermore, significant progress has been made in understanding MI or CMI as generalization measures in stochastic convex optimization (SCO) problems. Specifically, [56-58] all point out that MI or CMI bounds can be non-vanishing in some SCO examples, while the exact generalization error is vanishing. Notably, [58] discovers a "CMI-accuracy tradeoff" phenomenon in certain scenarios: For the generalization error to be upper bounded by vanishing parameter, the original hypothesis-basee CMI must be lower bounded by the reciprocal of this parameter (or even the reciprocal of its square). indicating that the CMI bound cannot characterize the lcarnability of such problems. Although this limitation is currently only observed for hypothesis-based CMI, it is anticipated to hold in other variants of CMI, such as Id-CMI.
matrix, enabling the derivation
Our work also contributes to understanding the potential looseness of previous CMI generalization bounds. However, the current state of our bounds cannot explain resolve the limitation presented in [58] in a non-trivial way. Nonetheless, our framework provides some intuition that, as long as a gap exists between e--1 and x ax² (see Figure ((igght), there will always be room for constructing counterexamples that challenge information- rare. Another limitation of this work is the lack of high sigh-bbbbabiltty generalization guarantee. There are two potential directions to address this: either by applying similar techniques to the framework in [59], which is the PAC-Bayesian counterpart of the CMI bound, or by combining it with recent ciarmattion-ootlennee generalization bounds [60, 61].
measures, although such examples may be
Acknowledgments and Disclosure of Funding
This work supported partly by an NSERC Discovery grant. The authors would like to thank the anonymous AC and reviewers for their careful reading and valuable suggestions.
10

---

References
[1] Kyoungseok Jang, Kwang-Suna Jun, Lija Kuzborskij, and Francesco Orabona. Tighter pac-bayes bounds through coin-betting. In The Thirty Sixth Annual Conference on Learning Theory, pages 2240-2264. PMLR, 2023.
[2] Daniel Russo and James Zou. Controlling bias in adaptive data analysis using information theory. In Artificial Intelligence and Statistics. PMLR, 2016.
[3] Daniel Russo and James Zou. How much does your data exploration overfit? controlling bias via information usage. IEEE Transactions on Information Theory, 66(1):302-323 2019.
[4] Aolin Xu and Maxim Raginsky. enformation-theorehe analysis of generalization capability of learning algorithms. Advances in Neural Information Processing Systems, 2017.
[5] Ankit Pensia, Varun Jog, and Po-Ling Loh. Generalization error bounds for noisy, iterative algorithms. In 2018 IEEE International Symposium on Information Theory (ISIT). IEEE, 2018.
[6] Yuheng Bu, Shaofeng Zou, and Venugopal V Veeravalli. Tightening mutual information based bounds on generalization error. In 2019 IEEE International Symposium on Information Theory (ISIT), pages 587-591. IEFF, 2019.
[7] Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M Roy. Information-uee -hoomation--hhoretiic generalization bounds for sgld via data-dependent estimates. Advances in Neural Information Processing Systems, 2019.
[8] Hao Wang, Yizhe Huang, Rui Gao, and Flavio Calmon. Analyzing the generalization capability of sgld using properties of gaussian channels. Advances in Neural Information Processing Systems, 34:24222-24234, 2021.
(9] Bohan Wang. Huishuai Zhang, Jieyu Zhang, Qi Meng, Wei Chen, and Tie- Yan Liu. Optimizing information-theoreticie generalization bound via anisotropic noise of sgld. Advances Neural Information Processing Systems, 2021.
[10] Gergely Neu, Gintare Karolina Dziugaite, Mahdi Haghifam, and Daniel M Roy. Information- theoretic generalization bounds for stochastic gradient descent. In Conference on Learning Theory. PMLR, 2021.
[1I] Ziqiao Wang and Yongyi Mao. On the generalization of models trained with SGD: Information- theoretic bounds and implications. In International Conference on Learning Representations, 2022.
[12] Ziqiao Wang and Yongyi Mao. Two facets of sde under an information theoorti lens: General- ization of sgd via training trajectories and via terminal states. arXiv preprint arXiv:2211.10691, 2022.
[13] Futoshi Futami and Masahiro Fujisawa. Time-independent information-theoree generalization bounds for sgld. Advances in Neural Information Processing Systems, 36, 2024.
[14] Raef Bassily, Shay Moran, Ido Nachum, Jonathan Shafer, and Amir Yehudayoff. Learners that use little information. In Algorithmic Learning Theory. PMLR, 2018.
[15] Amir Asadi, Emmanuel Abbe, and Sergio Verdú. Chaining mutual information and tightening generalization bounds. Advances in Neural Information Processing Systems, 31, 2018.
[16] Thomas Steinke and Lydia Zakynthinou. Reasoning about generalization via conditional mutual information. In Conference on Learning Theory. PMLR, 2020.
[17) Mahdi Haghifam, Negrea, Ashish Khisti, Daniel M Roy, and Gintare Karolina Dziugaite. Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms. Advances in Neural Information Processing Systems, 2020.
[18] Hassan Hafez- Kolahi, Zeinab Golgooni, Shohreh Kasaei, and Mahdieh Soleymani. Conditioning and processing: Techniques to improve information--hherrtiic generalization bounds. Advances in Neural Information Processing Systems, 33:16457 2020.

---

[19] Borja Rodríguez- Gálvez. Germán Bassi, Ragnar Thobaben, and Mikael Skoglund. On random subset generalization eπror bounds and the stochastic gradient langevin dynamics algorithm. In 2020 IEFF Information Theory Workshop (TTW), pages 1-5. IEEE, 2021.
[20] Ruida Zhou, Chao Tian, and Tie Liu. Individually conditional individual mutual information bound on generalization error. IEEE Transactions on Information Theory, 68(5):3304-3311
2022.
[21] Ruida Zhou, Chao Tian, and Tie Liu. Stochastic chaining and strengthened iiloomation-thhorette generalization bounds. In 2022 IEEE International Symposium Information Theory (ISIT). IEEE, 2022.
[22] 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, 2021.
[23] Fredrik Hellström and Giuseppe Durisi. A new family of generalization bounds using sample- wise evaluated CMI. In Advances in Neural Information Processing Systems, 2022.
[24] Ziqiao Wang and Yongyi Mao. Tighter information-theoreee generalization bounds from supersamples. In International Conference on Machine Learning. PMLR, 2023.
[25] Jiantao Jiao, Yanjun Han, and Tsachy Weissman. Dependence measures bounding the explo- ration bias for general measurements. In 2017 IEEE International Symposium on Information Theory (ISIT), pages 1475-1479. IEEE, 2017.
[26] Borja Rodríguez Gálvez, Germán Bassi, Ragnar Thobaben, and Mikael Skoglund. Tighter expected generalization error bounds via wasserstein distance. Advances in Neural Information Processing Systems, 34, 2021.
[27] Amedeo Roberto Esposito, Michael Gastpar, and Ibrahim Issa. Robust generalization via a- mutual information. International Zurich Seminar on Information and Communication (IZS 2020), page 96, 2020.
[28] Amedeo Roberto Esposito and Michael Gastpar. From generalisation error to transportation-con inequalities and back. In 2022 IEEE International Symposium on Information Theory (ISIT), pages 294-299. IEEE, 2022.
[29] Gábor Lugosi and Gergely Neu. Generalization bounds via convex analysis. Conference on Learning Theory, pages 3524-3546. PMLR, 2022.
[30] Gábor Lugosi and Gergely Neu. Online-to torleetto-pccc--- pac conversions: Generalization bounds via regret analysis. arXiv preprint arXiv:2305.19674 2023.
[31] Kwang-Sung Jun and Francesco Orabona. Parameter-free online convex optimization with sub-exponential noise. In Conference on learning theory, pages 1802-1823, PMLR, 2019.
[32] Francesco Orabona and Kwang-Sung Jun. Tight concentrations and confidence sequences from the regret of universal portfolio. IEEE Transactions on Information Theory, 70(1):436-455 2024.
[33] Yury Polyanskiy and Yihong Wu. Information Theory: From Coding to Learning. Cambridge university press, 2023.
[34] Ilja Kuzborskij. Swang-Sung Jun, Yulian Wu, Kyoungseok Jang, and Francesco Orabona. Better-than-kl pac-bayes bounds. arXiv preprint arXiv:2402.09201 2024.
[35] Aharon Bel-Tal and Mare Teboulle. An old-new concept of convex risk measures: The optimized certainty equivalent. Mathematical Finance, 17(3):449 2007.
[36] Jeremiah Birrell, Markos A Katsoulakis, and Yannis Pantazis. Optimizing variational repre- sentations of divergences and accelerating their statistical estimation. IEEE Transactions on Information Theory, 68(7):4553-45 2022.
12

---

[37] Rohit Agrawal and Thibaut Horel. Optimal bounds between f-divergences and integral prob- ability metrics. In International Conference on Machine Learning, pages 115-124. PMLR. 2020.
[38] Paul Viallard, Maxime Haddouche, Umut Şimşekli, and Benjamin Guedj. Tighter generalisation bounds via interpolation. arXiv preprint arXiv:2402.05101, 2024.
[39] Ziqiao Wang and Yongyi Mao. On f-divergence principled domain adaptation: An improved framework. arXiv preprint arXiv:2402.01887 2024.
[40] Wenliang Liu, Guanding Yu, Lele Wang, and Renjie Liao. An information -hformationn-hhorrticc theoretic framework for out-of- of-isiirbiiittionnnn generalization. arXiv preprint (tti::2403.19999 2024.
[41] Xuetong Wu, Jonathan H Manton, Uwe Aickelin, and Jingge Zhu. Fast rate generalization error bounds: Variations on a theme. In 2022 IEEE Information Theory Workshop (ITW), pages 43-48 IEEE, 2022.
[42] Xuetong Wu, Jonathan H Manton, Uwe Aickelin, and Jingge Zhu. On the tightness of information- bounds on generalization error of learning algorithms. arXiv preprint arXiv:2303. I4658, 2023.
[43] Ruida Zhou, Chao Tian, and Tie Liu, Exactly tight information-theoree generalization error bound for the quadratic gaussian problem. 2023 IEEE International Symposium on Information Theory (ISIT), pages 903-908, 2023.
[44] Mahdi Haghifam, Shay Moran, Daniel M Roy, and Gintare Karolina Dziugiate. Understanding generalization via leave-one-out conditional mutual information. In 2022 IEEE International Symposium on Information Theory (ISIT), pages 2487-2492. IEEE, 2022.
[45] Zhiyu Zhang, Ashok Cutkosky, and Yannis Paschalidis. Optimal comparator adaptive online learning with switching cost. Advances in Neural Information Processing Systems, 35:23936- 23950, 2022.
[46] Harold Jeffreys, An invariant form for the prior probability in estimation problems. Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences, 186(1007): 453-461, 1946.
[47] Gavin E. Crooks. Inequalities between the jenson-shannon and jeffreys divergences. In Tech. Note 004, 2008
[48] Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
[49] Fredrik Hellström, Giuseppe Durisi, Benjamin Guedj, and Maxim Raginsky. Generalization bounds: Perspectives from information theory and pac-bayes. arXiv preprint arXiv:2309.04381 2023.
[50] Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://wwweccc.co////aaaee
2, 2010.
[51] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition. pages 770-778, 2016.
[52] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages 248 255, 2009.
[53] Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
[54] Mohamad Rida Rammal, Alessandro Achille, Aditya Golatkar, Suhas Diggavi, and Stefano Soatto. On leave-one-out conditional mutual information for generalization, In Advances in Neural Information Processing Systems, 2022.
13

---

[55] Ziqiao Wang and Yongyi Mao. Sample-conditonned hypothesis stability sharpens information- theoretic generalization bounds. In Thirry-seventh Conference on Neural Information Processing Systems, 2023.
[56] Mahdi Haghifam, Borja Rodríguez-Gälvez. Ragnar Thobaben, Mikael Skoglund, Daniel M Roy, and Gintare Karolina Dziugaite. Limitations of coormationntheoretii generalization bounds for gradient descent methods in stochastic convex optimization. In International Conference Algorithmic Learning Theory, pages 663-706. PMLR, 2023.
[57] Roi Livni. Information theoretic lower bounds for information theoretic upper bounds. arXiv preprint arXiv:2302. 04925, 2023.
[58] Idan Attias, Gintare Karolina Dziugaite, Mahdi Haghifam, Roi Livni, and Daniel M. Roy. Information complexity of stochastic convex optimization: Applications to generalization, memorization, and tracing. In Forty-first International Conference on Machine Learning, 2024.
[59] Peter Grunwald, Thomas Steinke, and I Lydia Zakynthinou. Pac-bayes, mac-bayes and conditional mutual information: Fast rate bounds that handle general classes. In Conference Learning Theory. PMLR, 2021.
[60] Kenji Kawaguchi, Zhun Deng, Xu Ji, and Jiaoyang Huang. How does information bottleneck help deep learning? In International Conference Machine Learning, pages (6049-16096
PMLR, 2023.
[61] Yuxin Dong, Tieliang Gong, Hong Chen, Shujian Yu, and Chen Li. Rethinking information- theoretic generalization: Loss entropy induced PAC bounds. In The Twelfth International Conference on Learning Representations, 2024.
[62] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
[63] Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-288 2830. 2011.
[64] Francesco Orabona and Kwang-Sung Jun. Tight concentrations and confidence sequences from the regret of universal portfolio. IEEE Transactions on Information Theory, 2023.
14

---

Appendices
A
Technical Lemmas
Lemma A.1 (Donsker and Varadhan's 's variational formula). Let Q, P be probability measures on O, for any bounded measurable function log Ee-p (exp f())].
E. have DKL DKL (QIIP) = sup, B [f
Lemma A.2. Let P and Q two probability measures on the same metric space X. f some measurable function associated with X. The total variation distance between P and Q can be written
as
1
Dry (P.Q)
sup
Ep [f(X]]] Eq [f(X)]l.
M
Lemma A.3. The following inequalities hold:
log(1 + x) 20 ax²
for a 2 and
1
(5)
2a
2a
[
2x ax 2
for a 2 1 and x E
1,
(6)
1 1+ x
a
log(2- ")
2x ax
for 2 4 and x E
2' 2
Proof. We prove these inequalities separately.
We first prove Eq. (5) first derivative f())):
We analyze the function f(x) = -log(1 (1 + +.)
+ ax. By computing the
x22a 1 + 2ax.)
f'(x) 1 -1+ 2ax
+ x
Let (z(x) = 0, we have x(2a- - 1 + 2ar) = 0, which gives two critical points:
1
2a
0 and
2a
Note that 1-20 is within the interval f*(x):
1,1 20
Then computing the second derivative
f"(x)= = (1 + x))
2a.
Since a 2 Z and -1 < x < 1, we have ('(x) 2 0, indicating that f(x) ) is either concave upwards or linear at these critical points. It is easy to check that the minimum value f(0) 0, f(x) 2 in this interval. Hence, log(1 + I)
az? holds for 2 and
1, 2a.
We then prove Eq. (6) We analyze the function f(x) = It + ax By simplifying this function, we have:
12 1 + aa)) f(x)
1 x
Notice that 1 2 0 and - S ar < a 1, then it is easy to see that the numerator (a ax) is always non-negative for r E [ - 1, and 2 1. In addition, the denominator + æ is always positive for E 1, 2]. Therefore, f(x) x (aa( 0.
14
Consequently, have shown that r+z 2 ax for 1 and E 1,1
15

---

We then prove Eq. (7) We analyze the function f(z) log(2 e-*) - 2 + +ax By taking its derivative, have
f(x)) = 2x -1 2ax.
We now demonstrate that the function (z) 0 for [0. j and (z( s 0 for x [- 2, 0]. The second derivative of (z) is
-2
(x) (2 1)3
+ 2a.
Let t 2e", since [-] 21, we know that t [2e- 22,2eh Hence, we reformulate f"(x)
-t (*) = (t - 1)2 + 2a t - + 20.
Notice that + 1 monotonically increasing when t. > 1, so (t) is monotonically increasing in t [2e 2e2). Consequently,
(1 2 (1 = -2- x 226.7 + 2a. Additionally, it is clear that (r = 0) = -t = =2 = -22 > 0 for 2 4. WWe now consider two cases:
Case 1. If a > 13.35, then (* 2 (" = 2c 0. Hence, f'(x) is monotonically increasing
in E :
l. Since f' = 0) = 0, we demonstrate that ('(x) for x E [o. 1 and
f'(x) $ 0 for x E [ 0].
Case 2. If a < 13.35, then there exists an To such that ("(xo) < 0. Recall that f" = 0) (" 2. = 22 + 2a > 0 and f"(x) is monotonically increasing in x E [- 2 we
know that such 2o E - 0) and (x) 2 0 for all x E [o. f]] Thus, f'(x) first decreases in æ E _
rol -ol then increases in r E [zo. 1
Since ['(x = - _
a Rs 3.69 a < 0 for a 2 4, we conclude that f'(x) > 0
20
for [o, ]] and ('(x) S 0 for E [ 0].
Consequently, we know that f fx) decreases in x E 1-2 0] and increases in [0, 2. By checking f(x) 2 (() = 0, the inequality log(2 - -e e-=) 2 axz holds for 2 4 and x E 2 2
1 1
This completes the proof.
B Omitted Proofs in Section 3 and Additional Results
B.1 Proof of Theorem 3.1
Proof. Lemma 3.1 indicates that
I(AL;U,)
sup 1E(-1,+cc)
EAL,U [log (1 +++t(-- ((-1)U:
Recall that G, = (-1)%: AL, and let [GG]] 2E c3
_ Since 2 and 2u 2 0, we can apply
Eq. (5) in Lemma A.3 to have f(x) = log(1
+ x))
x + a 2 0 for x E [2] 1, 20
Hence, by G; E [-1, we restrict [ 1,1 inequality,
1 and let x = tG, to have the following
za
E E
sup E flog (1 + ++,)
>
sup
E IGG at at&
4aE G?
(8)
1>
tE
-1,1 3a
16

---

where the last equality holds when t"
BGG
2n G
We now show that tr can indeed be reached within Substituting
[1 1,
2a
|
+ 2. we can see that t
G
In addition, notice that
23
BG G
1
[G [
G G + E [
and
2a
E
E
[G]]
2a
E
Clearly, either IE [Gi] one of the endpoints of Therefore.
E
I [G:]] holds. Consequently, /" can be achieved at G. or [.G.]
1,1 24
E G. 4a
MALU
sup (0(-)
Bar,, [log (1 A(=) 2
G
which is equivalent to
E² < 4alE
[ ((LG
(9)
Then, by Jensen's inequality.
1
(A) EALLU [G:]]
71 1=1
2 [E[G:]|+ (ECE))(((LA ((L:;
where the last inequality is by Eq. (9).
This completes the proof.
B.2 Proof of Corollary 3.1
Proof. Recall Eq. (3) (or Eq. (9) equivalently).
E [= ( [.:] [G:]l- ( T(A,; U.).
Notice that E [G,]] 2 0, we now solve the inequality above for E [G Let A = EE [?? and A2 =
[( (AL; U.), then by the quadratic-root formula, the solution to E [ 2A₂ [E [G.]] 2A, S 0
2A2 + /4Ag A8AA2
< E [.)]
A2 + A + 2A, A2-
2
Therefore, we have
E [G,] ST(AL;U)) + (TAAL)))) 2 (R
<2T(AL; ( [[
where the second inequality is by vx y V Vy. The remaining steps are routine, which will complete the proof.
B.3 Proof of Corollary 3.2
Proof. Based on Theorem 3.1, by /x + U V + Vv. we have
(V 2E
(A)) < Σ 1=1
(10)
17

---

Let G = (-1)): where AL; is an independent copy of AL, Notice that E [ = 0. Then,
EAL, G. = |Ea,,,, [G,] Ear,u, [G]]] - Eu, BaL.j [G.] - Bay; [G]]]]
where the last inequality is by Jensen's inequality.
Notice that G2 S 1, by the dual form of total variation (cf. Lemma A.2), we have
Eu, ALLU, [G:] Eal; [G] S Eu, [Drv (PaLaUs Par.)]
Plugging the above into Eq. (10) will complete the proof.
B.4 Comparison with "Online-to-PAC" Generalization Framework
We now discuss the comparison with [29, 30], consider the case of the KL mutual information. The only explicit expected generalization bound provided in [30] is their Corollary 21, which recovers the square-root bound of O( (WW s)/n). This bound is clearly weaker than our fast-rate bound in our Corollary 3.1-3.2, due the omission of vanishing terms in our oracle bound in Theorem 3.1. In fact, more refined MI bound is presented in the earlier version of [30], namely [29, Corollary 4]. This bound takes the form
4Ez le(, Z) 122((, 2) I(W:))
(A,( S
n
which can indeed be derived from [30] due to the generality of their framework. Recall that our Theorem 3.1 gives the bound
(a,( S n
(2E + 2I
Notably, because we apply individual and loss-difference techniques, our averaged MI term is
n always tighter than that of [29, 30], as 1. E. VI(A,; U.) S I(W:5) generally holds. To fairly
"
compare our framework with theirs, we ignore the difference between MI terms and only focus on the novel components of each bound, specifically ( Z) I [e(: Z)]l& in their work and E[AL?] + [[]]]] in ours, let's consider the following simple example:
Example 1. Let W 1), and let the imput space be 2 (1,-1). Assume μ Unif( 2), Lee. 7 is a Rademacher variable. Consider a convex and 1-Lipschitz loss function f(w, 2) = 1 22
Under the ERM algorithm, W = =A(S) 1 Ei= Z4. Notice that for any w E W, B3 [[(w, 7))
"
2 (- (1 1)) O, hence Ez](e(- 22 [2 2)1. Ezlle(, 1
In contrast,
since A L, E [-1, 1] in this case, TE[A [.]] S E |T, and [E[G]]] S B[
[], we have R[A
[E[]]]| S [T Moreover, E AL,]] = B[ ( ZT S E Σ 1=1 Zi] S v where
the last step is by the Chintchine-Kahatn inequality [62, Theorem D.9].
Thus, in this example, [ 2) - Rz[<(. 2)1 1, while our bound B[AT.] + |EG.]] < 21] < (+)))) shows tighter convergence rate. Consequently, even without using the individual trick and loss-difference technique, our bound (Theorem 3.1) can still be tighter than [29, 30] in terms convergence rate in this example. This suggests that, MI-based bounds in [29, 30] can still encounter limitations (c.g., slow convergence rate), as with previous MI-based bounds.
Finally, to clarify the comparison, we only demonstrate that our oracle CMI bound could be tighter. It is worth noting that the unpublished version of [30] represents an initial exploration of their "online-to-PAC" generalization framework. As such, the results in their current version may primarily aim to recover previous findings, and their framework likely has room for further advancements.
B.5 Proof of Theorem 3.2
Proof. Lemma 3.1 indicates that
((-1)U:AL
T (AL:
sup EAL.U, xE(-o0,1)
1+
18

---

Let
G [:]
+ 1. Consider the function f(z) = Ite + az?. Notice that 2 1 and
2E C
I By Eq. (6) in Lemma A.3, we know that when a 1 1, - l. f(x) 2 0. Hence, recall that G, E [-1,1], I]. we restrict & E l1 1,,1- y) to have the following inequality.
-1
<
1G IG,
E.G. 4al | E.
sup E c
sup
- al G? E -
(11)
1
rE(2 1111-11 1
where the last equality holds when t"
B 20
G
We now show that 1* can indeed be reached within / E Substituting a, we can see that
-
G 2
E
G
[4
2E
G
In addition, 1 -
B
and 1
Clearly, either E [G,
[E| +
- -IE [G]] or E [G[]E]]] = |E E.] holds. Consequently, t can be achieved in 11_ 1, d
Therefore,
((-1)) AL 1+1(-1)U.AT A..
G.
Hi (.) 2 sup EAL.U.E LE(-20,1)
N
4aE
G
which is equivalent
B[G; &||l & v LaB G (AL. = (2 (2
+ 4E (G)E) 4 U.). (12)
Then, by Jensen's inequality,
(A) < Σ B B. [Gi||
< Σ
AL, [G/]
Ez.
i=1
Plugging Eq. (12) into the above will complete the proof.
B.6 Proof of Theorem 3.3
Proof. Lemma 3.1 indicates that
(AL; sup EAL,U,E t- log 2
[oo((2 -((-)) u/ A1:))1)
Let E[G, [ G
+ 4. Consider the function f(z) log(2 - =) - x + ax Notice that a 2
and by Eq. (7) in Lemma A.3, we know that when x E [ 2: 111 f(x) 2 Hence, recall that
G E [], we restrict E [-2 1 to have the following inequality, 2:22
B&
[log(2 --G >1:]] 2 sup t> log
sup
[tG, af
(13)
4aÆ [G?
as the same with the previous proofs, the last equality holds when t"
BIG, 1 20 1
We then check the conditions that to E 2 f]:
E G
[
E G
2IE C [
E
G
which is clearly satisfied by E
+ 4. Consequently, 1x can be achieved in |- 7.
1
E
19

---

Therefore,
E2 G
(is(A)) 2
sup BAL.U.E - - -- 2og
4aB [ E
With additional arrangements, we have
E|G.| < V 4aB (G) (4 16B [G) lis (AL: U.). (14)
Then, by Jensen's inequality,
(A) S Σ B.L.U. G.il S
E U.1 [Gi]|
Ez.
1=1
Plugging Eq. (14) into the above will complete the proof.
B.7 Additional f-Information Disintegrated Bounds
The following bounds can be derived by first employing a similar approach as in the proof of Theorem 3.1 to upper bound EAr, U. [G.]. Then, we incorporate this individual bound into
(A) S 4, Ei= BAA,,U.. [G.] S E A.L.. [Gi]
Theorem B.1. Under the same conditions in Theorem 3.1, we have
(xx( 1 Σ
E
(B
+
G.IZ. 12. (AL;UU).
Theorem B.2. Under the same conditions in Theorem 3.1, we have
(xx( S
Σ
Ez
E
+ E G (AL.
1=1
where U.); = (PAL.U, &. PAL.13. Po:) the (disintegrated) x² -iinformmaiion.
The following bound is corollary from Theorem 3.2, which is used our experiments in Section Corollary B.1. Under the same conditions in Theorem 3.1, we have
(A)( < M Ez. V
[E
A171%
12 (A U.). + +Eu, [Div (PAL.UUIZ P Pam.
The proof is nearly the same to Corollary 3.2 except that we do not apply 18 S V to unpack the terms.
C Omitted Proof in Section 4
C.1 Proof of Lemma 4.1
Proof. By the variational representation of fdiivergence, we have
Ix(X;s) 2 sup Ex,e [g(X,s)) - Ex,e/ 10 (a(XX
sup Ex,e (0 (teX) [xica] - Ex 10" (texi 1|x|s))]
For the second term above, we have
LX LX
Ex,e' [60 (0 ((=--((t' - [|x]s])] LE' te' + (0)
dP
=0
2
where =\t = (I X,EE (-1,1)| |2| S C). Putting everything together will conclude the proof.
20

---

C.2 Proof of Theorem 4.1
Proof. Since (-1) is a Rademacher variable and (0) e² for KL divergence, we can apply Lemma 4.1 first then follow the similar developments in Theorem 3.1 by controlling tG, [ In particular, for any 2 0,
[(LA 2
sup LE| AE(-1/C:1/C]
BAL.U, [log(1 + + 4aglc
2
sup EAL.U, [[tG; - a.scc]
at -
4aE La,
cl |a.se
x. G c.1scc
e Ga c.
where a
+ Notice that
28 07 |0,100
10.100
203 |olso
cB cB +E G a sc
and it is easy verify 1" Consequently,
1-2a 2a-11 2aC
J, so the last equality be achieved.
E [GLL $ /2 | [G E [(LL
(15)
Furthermore, let P= PAL.U, and Q = PAL, Pu
/ G: aQ
dP
[G:
dQ
/
dP
-1 dQ
aQ
Bol -
where we use the fact that ESL.U; [G, [AL Then, by using Hölder's inequality twice,
E [[AAa & (fIG. [[
( dQ)
(/LL,, aQ) *
(A);
(P (IAL,) > C))
| (To, (AL;
(16)
Moreover, notice that
1 n
n
(A))
E
[i:]
E G |.SS + G.1 [alsel
n
E G [ + +| [G a,se)))
Plugging Eq. (15) and Eq. (16) into the above will complete the proof.
C.3 Proof of Corollary 4.1
Proof. First, by Markov's inequality, we have
E EI
AL, |17 AL, 1
6 -
||ALillgs
C
Cr
In addition, recall that Çi 5 /2C, we let
A 2T([ U.)
and A₂ =
=| VTo. (AT:; U.).
21

---

Then, define f(C) A1C + Az.
C Solving minc f(C),
we have
A27
C
A
Plugging C* into f(C), we have
f(C*)= = (1 T+1 + t
Apti
Azt1.
From the proof of Theorem 4.1, notice that
E G [[apac + | [a $ f(C))
Substituting A1 and A₂ into the expression of f(C*), we will finally obtain
[x)( - n2 Σ +オ ( (V21(AT:U))
केन (IATIIRIIATT) / VTo To (AT.;
This completes the proof.
D
Experimental Details
Our experimental setup largely follows [24], and the code of experiments be found at http://gittubcoo//iiiioaaaaaani WwwaaaaeohheCCnnniioooaallooeoee
Linear Classifier on Synthetic Gaussian Dataset In this experiment, similar to [24], we use the popular Python package scikit-lear [63] to generate synthetic Gaussian data. Each feature of data drawn independently from Gaussian distribution, ensuring that all features are informative for the class labels. Specifically, we set the dimension feature vector to 5 and create different classes of points, which are normally distributed. We train the linear classifier using full-bater gradient descent with a fixed learning rate of 0.01 for a total of 300 epochs, employing early stopping when the training error falls below threshold (e.g.. < 0.5%). To ensure robustness and statistical significance, we generate 50 different supersamples for each experiment. Within each supersample, we create 100 different mask random variables, resulting total of 5, 000 runs for each experimental setting. This thorough setup allows us to compare and the disintegrated f f-information-bae -aaed bounds.
WorldWorld Datasets In these experiments, the same setup is initially given in [22], and is also used in [23, 24, 61]. Specifically, draw kj samples of 2 and k2 samples of U for each given ž. For the CNN on the binary MNIST dataset, we set k = 5 and h 30. The 4-layer CNN model is trained using the Adam optimizer with a learning rate of 0.001 and momentum coefficient of 31 0.9. The training process spans 200 epochs with batch size of 128. For ResNet-50 on CIFAR10, we set h 2 and l2 40. The ResNet model trained using stochastic gradient descent (SGD) with learning rate of 0.01 and momentum coefficient of 0.9 for a total of 40 epochs. The batch size for this experiment is set to 64. the SGLD experiment, we train a 4-layer CNN on the binary MNIST dataset with a batch size of 100 for 40 epochs. The initial learning rate is 0.01 and decays by a factor of 0.9 after every 100 iterations. Let be the iteration index; the inverse temperature of SGLD given by min mi00,000,, max mmax(10) (100, 10et/1003). We set the training sample size to n 4000, and h = 5 and k2g 30. Checkpoints are saved every 4 epochs.
CNN and ResNet-50
All these experiments are conducted using NVIDIA 1100 GPUs with 40 GB of memory. For more comprehensive details, including model architectures, we recommend referring to [22-24].
E
CMI Framework from the Perspective of Coin-Betting Sequences
Deriving generalization bounds from coin-betting perspective is inspired by [64, 1, 34]. We now adapt this strategy to derive CMI bounds, invoking inequalities similar to those in Lemma A.3.
Assume & [0, 1]. Let A4, E [-1, 1] be sequence of "continuous coin" outcomes chosen arbitrarily, and at each round a player bets e 2 0 money on the sign of the outcome & E (11,1). Then, AL, is revealed, and the bettor wins loses C, money.
22

---

Let the initial wealth Wealtho = 1. The wealth at the end of round n is:
Wealth, = Wealth + C.E,, An, = 1+ 2=1
GE,AL,
Notice that G2 [0, Wel Now consider a strategy where the player always bets fixed fraction t E [0, 1] of the current money, i.e., G; = tWealth;-1- Then:
Wealth,
= Wealth + te,, A6, Wealth = II
+ te,
2m1
It follows that
log Wealth, (1) = Σ log(1 + ts; t6)
Unlike the traditional online gambling game, incorporate the individual technique from [6] by analyzing the expected log-wealth of the ith bet', given by
(t(t) = Be,,ar, (1 + AL,)
There are two kinds of players: those guessing the coin outcome randomly and those with side information. Let ε (-1)%; where Uj Bern(1/2). The average log- log-wealth of the random guesser EUg,Ar, lo,,AAloog1111 + t(-1)t'sAL)) and the average log-wealth of the informed player is (t(t) Eu, + t(-1)/
Clearly, the value of side information impacts the second player's 's income. To quantify this impact, by the DV-representation of KL divergence (cf. Lemma A. we have
log (0e(1+((11) 200(1H1(1))(AA.))
T(AL;U) U.) 2 sup Bu, log + ((-)) log EUy LE(U,1)
6
= sup BU,,L, (1 (1+((-1)- AL,) - log BUy, (1+t(-1)(AA,) tE(0.1)
= sup BU,,LL (1+ (1+ tE(0,1)
(17)
where the last equality holds because Er, 1(-1)" EAL, Eo: EAL. [ = 0. Notice that the log-wealth of the comparator, i.c. the random candom-guesser,
appears in Eq. (17) in the form of inf ESL.U; 00 (log(1 + ((11) + + - X.
Similar to [1], by the inequality log(1 + x) 2 x - z for x N -0.68 (see Figure ((iight) for visualization of this inequality), we have
I I(L U.) 2 sup EU,AL, log (1 + ((11))-AAi) tE(0,1)
2 sup EU,,LL, (1 + t(-1) AL.) .E(0.0.68)
sup RU,AL [1(-1)u: A - 221 (0(0.0.68)
sup EU,AL [t(-1)u, AL: [2 (0(0.0068)
E Ey
A.r.. A..]
We then have
EU,AL, [(-1) S 2 T(AL;U))
(18)
"This can also be interpreted as having players each place single bet with f, so log Wealth,, (t) represents their collective wealth..
23

---

Moreover, we now assume that the side information is "perfect" such that (-1) AL, 2 0 (i.e. an interpolating or overfitting algorithm) always holds for each namely the income always positive. Under this condition, the players can safely set / 1, that is, the players "all-in" their money. Then, by log (1 + x)) 2 [1+x)
for x > -1, we have
I(A; ZEu,,at, (1 (-1)
(-1)
AU, 1+ (-1)6;AL
(-1)
AU,
which gives us
Ru,, (-1 S 2T(A;U
(19)
Consequently, recovering several existing Id-CMI bounds (up to a constant) from Eq. (19) and Eq. (18) straightforward.
24

---

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

---

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

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We only use synthetic dataset and some well-known public image datasets, which can be easily found, and we provide our source code in Appendix D and in the supplementary materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
public/guided wttgg/gee/oodeuuabee CCaess//oSSSuusssseeee commiisssonooicyyyo for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ cttpsscccppbbccccceceece wwwpce/ggiiessseeee hatps//ooeeSSbeeeeeeeeeeeeee wwwssinnoooiyyyl for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
See Appendix D.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We provide the standard deviations in some figures in Figure 2.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
27

---

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

---

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

---

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


Reviews:
[{"review_id": "KI1mx4y6F2", "reviewer": "Reviewer_Ka5u", "summary": "This paper extends conditional mutual information bounds to other $f$-divergences. A list of bounds involving various $f$-information terms are established. The results are derived by evaluating a previously established variational formula for f-divergences at a specific function. Analysis tailored to various choices of $f$ is then conducted to extract expected generalization bounds.", "questions": "How exactly are the experimental plots made ? The theorems involve expectations and mutual information terms, are the authors estimating those? Can the authors add more information on what is plotted?", "limitations": "The limitations are discussed.", "rating": 4, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The paper is clear in the assumptions made to derive its results. The buildup to each theorem is well detailed making it easy for the reader to follow.", "weaknesses": "The main weakness of this work is in the motivation and the reason for being for the results. The derived extensions have the quantity to be bounded appearing within the bound itself. The leads to strange tautological statements like in line 165 where it is said that if each term in the expected generalization decays fast with $n$ then so does the expected generalization. The $\\chi^2$, Hellinger, Jensen-Shannon results have increasingly complicated terms that also involve the very quantity trying to be bound. It is unclear to me why such bounds would be of interest, especially since any instantiation requires falling back to a previously established result. \n\nFor example, the sub-gaussian assumption seems to be necessary to have any hope of controlling the quantities appearing in theorem 4.1, and when the assumption is made, the result yields a bound that is worse than existing bounds. The heavy-tail corollary 4.2 is even more impenetrable, the very same quantities we wish to bound appear on the right hand side within $L_p$ norms. The authors should provide justifications as to why these true inequalities are not circular and of limited interest.\n\nMinor note: There is some prior work establishing expected generalization bounds using different $f$-divergences [1].\n[1] Esposito, Amedeo Roberto, and Michael Gastpar. \"From generalisation error to transportation-cost inequalities and back.\" 2022 IEEE International Symposium on Information Theory (ISIT). IEEE, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you sincerely for your valuable feedback on our paper. Our responses follow.\n\n>- The main weakness of this work is in the motivation ...\n\n**Response.** As noted in Lines 159-160, when a bound contains $\\mathbb{E}[G_i]$, we refer to it as an \"oracle\" bound, such as Theorem 3.1. Obtaining the oracle bounds first provides new insights into information-theoretic generalization bounds and inspires novel bounds (e.g., Corollaries 3.1-3.2). When the oracle bound falls back to a previous result, our aim is to show either that the previous bound is potentially loose or that it can be recovered by a simpler approach based on our framework.\n\nWe now restate our motivation for introducing the $f$-information-based generalization framework. Our framework provides a new, generic method for deriving generalization bounds based on $f$-divergence in the supersample setting, differing from related works by not relying on existing concentration inequalities (e.g., Hoeffding's lemma) or existing regret guarantees for online learning algorithms. The advantages of our framework are twofold: 1) By first obtaining an oracle bound, we show that previous bounds are potentially loose as they ignore some vanishing terms; 2) By carefully handling these vanishing terms, we can either recover previous fast-rate bounds or derive new fast-rate bounds.\n\nTo elaborate, consider the KL divergence as an example. Our Theorem 3.1 presents the bound: $\\mathcal{E}\\_\\mu(\\mathcal{A})\\leq\\mathcal{O}(\\sqrt{(\\mathbb{E}[\\Delta L_i^2]+\\mathbb{E}[G_i])I(\\Delta L_i;U_i)})$. In contrast, existing square-root MI bounds under the same boundedness assumption are $\\mathcal{E}_\\mu(\\mathcal{A})\\leq\\mathcal{O}(\\sqrt{I(\\Delta L_i;U_i)})\\leq\\mathcal{O}(\\sqrt{I(W;U_i|\\widetilde{Z})})\\leq\\mathcal{O}(\\sqrt{I(W;Z_i)})$. These previous bounds can be very loose as they ignore the vanishing term $\\sqrt{\\mathbb{E}[\\Delta L_i^2]+\\mathbb{E}[G_i]}$. Additionally, our framework allows us to recover previous fast-rate bounds such as $\\mathcal{O}(I(\\Delta L_i;U_i))$ under realizable settings. Furthermore, using the oracle bound, we derive two new fast-rate bounds in Corollaries 3.1-3.2, which do not contain $\\mathbb{E}[G_i]$, to mitigate  the looseness in previous square-root bounds. \n\nFor other $f$-divergence bounds, we mainly state their \"oracle\" versions because obtaining similar bounds as in Corollaries 3.1 and 3.2 follows the same procedure. This is mentioned in lines 257-258 (and see Corollary B.1 in Appendix B.6 for the squared Hellinger case).\n\n>- For example, the sub-gaussian assumption ...\n \n**Response.** Regarding the sub-gaussian case, we note that our Theorem 4.1 is not worse than existing bounds. The bound provided in Line 306 uses a rough choice of $C=\\sigma$ and a pessimistic upper bound $\\zeta_1\\leq\\sqrt{2}C$. While this bound shows a simple combination of two divergences, it does not rely on the optimal choice of $C$ (which we believe should also vanish as $n$ increases), and $\\zeta_1$ is simply replaced by a non-vanishing constant in this case.\n\nIn fact, if we want to compare our bound with existing bounds, we can set $C=0$ and $q=1$ in the sub-gaussian case. This makes the first term in Theorem 4.1 zero, and the second term, using $||\\Delta L\\_i||\\_{\\beta}\\lesssim \\beta\\sigma$ for sub-gaussian R.V., becomes $\\mathcal{O}(\\beta\\sigma\\sqrt[\\uproot{5} \\alpha]{I\\_{\\phi_\\alpha}(\\Delta L_i;U_i)})$. Compared to existing MI bounds, e.g., $\\mathcal{O}(\\sigma\\sqrt{ I(\\Delta L_i;U_i)})$, we know from Pinsker's inequality and $\\mathrm{KL} \\leq \\chi^2$ that $\\mathcal{O}(I_{\\phi_1}(\\Delta L_i;U_i))\\leq \\mathcal{O}(\\sqrt{ I(\\Delta L_i;U_i)})\\leq\\mathcal{O}(\\sqrt{I_{\\phi_2}(\\Delta L_i;U_i)})$, suggesting that some $\\alpha \\in (1,2)$ could outperform the MI bound.\n\nMoreover, even if we set $C = \\sigma$ and $q = 1$ as in Line 306, the bound $\\mathcal{O}(\\sigma\\sqrt{ I(\\Delta L_i;U_i)}+\\frac{\\alpha}{\\alpha-1}\\sigma\\sqrt[\\uproot{5} \\alpha]{I_{\\phi_\\alpha}(\\Delta L_i;U_i)})$ is not necessarily worse than existing bounds in terms of convergence rate. The bound in Line 306 is worse only if $\\frac{\\alpha}{\\alpha-1}\\sqrt[\\uproot{5} \\alpha]{I_{\\phi_\\alpha}(\\Delta L_i;U_i)})$ dominates, namely, if $\\frac{\\alpha}{\\alpha-1}\\sqrt[\\uproot{5} \\alpha]{I_{\\phi_\\alpha}(\\Delta L_i;U_i)})\\geq \\sqrt{ I(\\Delta L_i;U_i)}$. We will add these additional discussions in the revision.\n\nRegarding the heavy-tailed result, there is a typo: $G_i$ in Line 317 should be $\\Delta L_i$. We sincerely apologize for the confusion and have fixed it. Furthermore, the validity of our Corollary 4.1 is consistent with existing heavy-tailed generalization bounds, which typically assume the higher $L_p$ norm of the loss is finite, implying the corresponding norm of the loss difference $\\Delta L_i$ is finite. Therefore, as long as those bounds are valid, our Corollary 4.1 is meaningful.\n\n>- Minor note: ...\n\n**Response.** Thank you for pointing out this missing reference. We have included in our revision.\n\n>- How exactly are the experimental plots made ...\n\n**Response.** The experimental plots are generated following protocols from previous works on CMI variants [21, 22, 23], and yes, we estimate expectations and MI terms by conducting multiple runs of experiments in the supersample settings. Specifically, as detailed in Appendix D, we draw $k_1$ samples of $\\widetilde{Z}$ and $k_2$ samples of $U$ for each given $\\tilde{z}$ (e.g., $k_1=5$ and $k_2=30$ for CNN on MNIST). Given that the loss function is 0-1 loss, estimating the mutual information between the discrete random variable $\\Delta L_i$ (which can be $0$, $1$, or $-1$) and the binary random variable $U_i$ (which can be $0$ or $1$) is easy. For each plot, we show the mean and standard deviation (represented by the shaded areas) of the estimated bound values and generalization error values. A more detailed description of the experimental protocol is provided in [21, Appendix B], and we will include additional information in the next revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UgTyHbIfoi", "reviewer": "Reviewer_gd7k", "summary": "Understanding generalization using information-theoritic measures of dependence between input and output of a learning algorithm is an important area of study. The main focus of this line of work is using the KL divergence as a measure of dependence and providing generalization bounds. In this work, the authors propose a more general approach that replaces the KL divergence with arbitrary f-divergences. The main contribution of this work is presenting an approach to obtain such a generalisation bounds.", "questions": "1- Write down the definition of convex conjugate?\n2- One main question here is that what is the gain of using f-divergence compared to the usual mutual information?\n3- Typo in Lemma 3.1. It should be b_1 and b_2.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The main strength of this work is showing KL divergence is not necessary for obtaining information-theoritic generalization bounds. Also, compared to other work showing this fact, the proof strategy in this paper is much simpler.", "weaknesses": "I think the weakness of the work are the following:\n\n1- The point that one can replace KL with an arbitrary f-divergence was shown in the following paper:\n\nLugosi G, Neu G. Online-to-PAC conversions: Generalization bounds via regret analysis. arXiv preprint arXiv:2305.19674. 2023 May 31.\n\nI could not find a clear comparison of the approach proposed in this work and the the paper by Lugosi et.\n\n2- More general question is that by replacing KL with f-divergence what sort of new insights can we obtain? I am trying to understand the real advantage of replacing KL with f-divergences.\n\n3- It is difficult to parse Theorem 4.1. for me. How one can find a good truncation value?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you sincerely for your constructive comments on our paper. Our responses follow.\n\n>- 1- The point that one can replace KL with an arbitrary f-divergence was shown in the following paper:\nLugosi G, Neu G. Online-to-PAC conversions: Generalization bounds via regret analysis. arXiv preprint arXiv:2305.19674. 2023 May 31.\nI could not find a clear comparison of the approach proposed in this work and the the paper by Lugosi et.\n\n**Response.** Our work was indeed inspired by Lugosi et al. (2023) and other recent studies exploring alternative measures of dependency for generalization analysis. While we share a common theme with these works, our proof strategy differs significantly. Notably, our framework is much simpler as it does not rely on existing regret guarantees for online learning algorithms, unlike Lugosi et al. (2023).\n\nAdditionally, these works are not directly comparable due to different assumptions (e.g., Lugosi et al. (2023) require the second moment of the loss to be bounded, which we do not). However, both frameworks are deeply connected with convex analysis, and we believe each has its own advantages in specific contexts. We plan to further compare and potentially unify these frameworks in future research.\n\n\n>- 2- More general question is that by replacing KL with f-divergence what sort of new insights can we obtain? I am trying to understand the real advantage of replacing KL with f-divergences.\n\n>- 2- One main question here is that what is the gain of using f-divergence compared to the usual mutual information?\n\n**Response.** Thanks to our generic recipe, we have shown that most generalization bounds based on KL divergence or other $f$-divergence can be derived by lower-bounding $\\phi^{\\*-1}(x)\\geq x-ax^2$. The gap between  $\\phi^{\\*-1}(x)$ and $x-ax^2$ reflects the tightness of the bound. To elaborate, define the gap function $g(x,a;\\phi)=\\phi^{\\*-1}(x)- (x-ax^2)$. Therefore, to derive a tighter bound (i.e., a smaller $g(x,a;\\phi)$), we consider the optimization problem $\\min\\_{x,a,\\phi}g(x,a;\\phi)$. Notably, there is no indication that choosing $\\phi(x)=x\\log(x)$, corresponding to KL divergence, is optimal.\n\nIn the paper, we use Figure 1 to visualize this. Clearly, using alternative $f$-divergences such as JS-divergence and squared Hellinger divergence can potentially lead to tighter bounds compared to KL divergence (i.e., the blue line in Figure 1(a)), as they have smaller $g(x,a;\\phi)$. This has also been corroborated by our experiments.\n\nWhile KL divergence and mutual information have advantageous properties like the chain rule, which enable various interesting studies and are not generally applicable to other $f$-divergences, there is no compelling reason to exclusively use KL divergence if tighter bounds can be achieved with other $f$-divergences.\n\n\n>- 3- It is difficult to parse Theorem 4.1. for me. How one can find a good truncation value?\n\n**Response.** We have discussed common cases for selecting truncation values in Lines 295-321. For the bounded case, the truncation value is often chosen as the boundedness value, though it might not always be optimal. If the random variable is likely to stay within a bounded range with high probability, selecting the corresponding boundedness value as the truncation value can be appropriate since $\\zeta_2$ will be small in Theorem 4.1. If there is no additional information about the tail behavior of the random variable (e.g., loss difference), we invoke $\\zeta_1\\leq\\sqrt{2}C$, apply the Markov inequality to $\\zeta_2$ and then optimize the upper bound with respect to the truncation value $C$. This approach leads to Corollary 4.1.\n\n\n>- 1- Write down the definition of convex conjugate? \n\n**Response.** Thank you for pointing this out. We have added the definition of the convex conjugate to our manuscript.\n\n>- 3- Typo in Lemma 3.1. It should be b_1 and b_2.\n\n**Response.** We appreciate you catching these typos. We have fixed them.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XWMRWOJ0ce", "reviewer": "Reviewer_abMK", "summary": "This paper presents a general framework for generalization bounds using a careful application of the Donsker-Vardaran representation of the conditional $f$-information, and show that a suitable quadratic Taylor expansion of the bounds, for various $f$-divergences, improves over the state of the art.", "questions": "Had any other works in the literature considered bounds based on $f$-divergences before? Did the original bounds, based on Shannon information, using the variational characterization in any meaningful way? It would be quite helpful for me to understand this better to fully gauge novelty.", "limitations": "The authors do an adequate job of explaining the limitations of their work: lack of high probability guarantees, failure to account for the tradeoff in source [52], and perhaps the general limitations of purely information-theoretic approaches to generalization.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper has a number of strengths:\n(1) The technique appears generic and \"fundamental:\" it works regardless of $f$ divergence, and unifies the perspectives on quite a few of them. Moreover, it seems to improve over prior art, consistently, and in many instantiations. Finally, Lemma 3.1 does seem useful in its own right. From what I understand, the use of the variational representation also seems novel. \n(2) The bound admits extension to unbounded losses, even those which do not admit MGFs\n(3) The bounds satisfy an oracle property, in that they adapt to problem-dependent quantities. \n(4) For a paper focused on theoretical contribution, the experiments are rather compelling: across toy domains and CIFAR 10, the Hellinger-based oracle confidence interval consistency improves upon prior art. \n(5) The authors go to great lengths to explain and differentiate their contributions from prior work.", "weaknesses": "I am not an expert in the state-of-art guarantees for generalization, so please take these concerns with a grain of salt. However, my only concern would be that these guarantees do not feel \"field changing\" in the sense that they appear to be an extension of and elaboration upon an accepted framework: construct a super-sample, evaluate its ($f$-)information, and evaluate the ensuing consequences. The idea of \"generalize Shannon information to $f$-information\" feels like a natural extension, and therefore its hard for me to find that some of these results are surprising. Moreover, the extension to unbounded losses appears to be based on standard truncation techniques. \n\nThat is to say, form an outsider's perspective, this appears a good, solid work with nice fundamental insights. But it doesn't feel groundbreaking enough for me to say, advocate for an award. \n\nThere are also a few typos here and there, and the preliminaries read a bit dense at times. This is probably standard in the community, and does not trouble me that much. \n\nPerhaps one suggestion: regarding the presentation, the authors could do well to offer a table in the appendix where they compare the bounds to prior art in a more structured and systematic way. The comparison in the paper often assumes familiarity with prior work, and it would be more effective to re-present the formal statements upon which the authors are improving an an Appendix. Then the authors can more clearly delineate the key advantages of their bounds over past art.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you sincerely for your valuable feedback and the positive comments on our paper. Our responses follow.\n\n>- I am not an expert in the state-of-art guarantees for generalization, so please take these concerns with a grain of salt. However, my only concern would be that these guarantees do not feel \"field changing\" in the sense that they appear to be an extension of and elaboration upon an accepted framework: construct a super-sample, evaluate its ($f$-)information, and evaluate the ensuing consequences. The idea of \"generalize Shannon information to $f$-information\" feels like a natural extension, and therefore its hard for me to find that some of these results are surprising. Moreover, the extension to unbounded losses appears to be based on standard truncation techniques.\n\n>- That is to say, form an outsider's perspective, this appears a good, solid work with nice fundamental insights. But it doesn't feel groundbreaking enough for me to say, advocate for an award.\n\n**Response.** Thank you for considering our paper to be a good and solid work with nice fundamental insights. While we acknowledge that our work builds on existing SOTA information-theoretic generalization bound techniques, such as the CMI framework, our novel change of measure inequalities in Lemma 3.1 and Lemma 4.1 enable the derivation of tighter generalization bounds in a simpler manner. We believe these inequalities can be applied in even broader contexts. Additionally, we sincerely appreciate the reviewer’s evaluation of our paper from an award-level perspective.\n\n\n>- There are also a few typos here and there, and the preliminaries read a bit dense at times. This is probably standard in the community, and does not trouble me that much.\n\n>- Perhaps one suggestion: regarding the presentation, the authors could do well to offer a table in the appendix where they compare the bounds to prior art in a more structured and systematic way. The comparison in the paper often assumes familiarity with prior work, and it would be more effective to re-present the formal statements upon which the authors are improving an an Appendix. Then the authors can more clearly delineate the key advantages of their bounds over past art.\n\n**Response.** Thank you for your valuable suggestions. We will include a table to compare with previous works and put the prior theorem statements in the appendix to improve the readability of our work. In addition, we have fixed some typos and will continue to improve the presentation of our paper in the next revision.\n\n>- Had any other works in the literature considered bounds based on $f$-divergences before? Did the original bounds, based on Shannon information, using the variational characterization in any meaningful way? It would be quite helpful for me to understand this better to fully gauge novelty.\n\n**Response.** Yes, as noted in Lines 43-48, there are previous works that explore using alternative dependence measures, including various $f$-divergences, in place of KL divergence. However, our contribution is distinct in its generic proof approach for $f$-divergence-based bounds under the supersample setting, as detailed in Lemmas 3.1 and 4.1. This method represents a significant departure from previous approaches and provides insight into the tightness of the obtained bound for different $f$-divergences, illustrated by the gap between $\\phi^{*-1}(x)$ and $x - ax^2$ in Figure 1. In addition, earlier works typically focus on hypothesis-based $f$-divergence quantities, which are challenging to evaluate empirically. \n\nRegarding the original Shannon information-based bounds, they are indeed based on the Donsker and Varadhan variational formula of KL divergence. These Shannon information-based generalization bounds are obtained by using concentration results (e.g., Hoeffding's Lemma) to upper bound the cumulant generating function in the variational formula, which can be challenging to generalize to other $f$-information. Such challenges are avoided in our Lemmas 3.1 and 4.1, as we discussed in Line 131-136.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7Z4mhymqmm", "reviewer": "Reviewer_D8Mx", "summary": "This paper introduces novel generalization bounds using the conditional f-information framework. It first derives conditional f-information-based generalization bounds for bounded loss, then examines mutual information generalization bounds as a specific example of their general theorem. This analysis helps to highlight the potential looseness of previous CMI bounds. Additionally, the paper presents several other f-information-based generalization bounds and extends the framework to handle unbounded loss cases. Finally, the tightness of the obtained bounds is demonstrated through empirical comparisons with other existing bounds.", "questions": "- For the definition of the expected generalization error (line 101 on page 3), should the correct definition be $\\\\mathbb{E}\\_S[\\\\mathbb{E}\\_W[L_{\\\\mu}(W)-L\\_S(W)]]$ instead of the current formula in the paper? If I understand correctly, $\\\\mathbb{E}\\_W$ refers to taking the expectation with respect to $P\\_{W|S}$, which depends on $S$.\n- In the “Other Fast-Rate Bound Cases” section, could the authors provide some examples where $\\\\mathbb{E}[\\\\Delta L^2\\_i] \\lesssim \\text{Var}(L\\_i^{+})$ holds?", "limitations": "See weaknesses and questions.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- **Clear presentation**: The structure of this paper is clear and easy to follow, with definitions and theorems clearly presented.\n- **Empirical validation**: Although it is a theoretical work, the paper includes empirical studies to demonstrate the utility of the proposed generalization bounds.", "weaknesses": "As the authors mention, the results pertain to the expected generalization error and therefore lack the high-probability generalization guarantee, which is more critical.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you sincerely for the valuable feedback. Our responses follow.\n\n>- For the definition of the expected generalization error (line 101 on page 3), should the correct definition be $\\mathbb{E}\\_S[\\mathbb{E}\\_W[L_\\mu(W)-L_S(W)]]$ instead of the current formula in the paper? If I understand correctly, $\\mathbb{E}\\_W$ refers to taking the expectation with respect to $P\\_{W|S}$, which depends on $S$.\n\n**Response.** In the definition provided in Line 101, $\\mathcal{E}\\_\\mu(\\mathcal{A})\\triangleq \\mathbb{E}\\_W{L\\_\\mu(W)}-\\mathbb{E}\\_{W,S}{L\\_S(W)}$, the first $\\mathbb{E}\\_W$ is taken with respect to the marginal distribution $P\\_W$. Although $W$ indeed depends on $S$, the population risk $L\\_\\mu(W)$, as a function of random vairable $W$, only depends on $W$. Therefore, knowing the marginal distribution of $W$ is sufficient to compute $\\mathbb{E}\\_W{L_\\mu(W)}$, namely $\\mathbb{E}\\_{S,W}{L\\_\\mu(W)}=\\mathbb{E}\\_W{L\\_\\mu(W)}$.\n\n\n\n\n\n>- In the “Other Fast-Rate Bound Cases” section, could the authors provide some examples where $\\mathbb{E}[\\Delta L^2_i]\\lesssim \\mathrm{Var}(L_i^+)$ holds?\n\n**Response:** We note that the inequality $\\mathbb{E}[\\Delta L^2_i]\\lesssim \\mathrm{Var}(L_i^+)$ holds in the CMI setting in general, rather than being specific to particular examples. This can be demonstrated as follows: In the CMI setting, due to the symmetric nature of the supersample construction, the random variables $L_i^+$ and $L_i^-$ have identical marginal distributions, thus having the same mean $e=\\mathbb{E}[L^-_i]=\\mathbb{E}[L_i^+]$. Consequently,\n\n$$\n\\mathbb{E}[(L^-_i-L_i^+)^2]=\\mathbb{E}[(L^-_i-e+e-L_i^+)^2]\\leq 2\\mathbb{E}[(L^-_i-e)^2]+2\\mathbb{E}[(L^+_i-e)^2]=4\\mathbb{E}[(L^+_i-\\mathbb{E}[L_i^+])^2]=4 \\mathrm{Var}(L_i^+). \n$$\n\nTherefore, $\\mathbb{E}[\\Delta L^2_i]\\lesssim \\mathrm{Var}(L_i^+)$ is indeed a general result. \n\nWe will include this justification in the revision to clarify this point.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces a general framework for deriving generalization bounds using a careful application of the Donsker-Varadhan representation. The reviewers found the approach solid and the contributions meaningful. I recommend acceptance.
Decision: Accept (poster)