Exactly Tight Information-theoretic Generalization Bounds via Binary Jensen-Shannon Divergence
Authors: Yuxin Dong
Haoran Guo
Tieliang Gong
Wen Wen
Chen Li
Venue: ICML 2025 poster (2025)
Keywords: Information Theory
Generalization Analysis
Mutual Information
Jensen-Shannon Divergence
Primary area: theory->learning_theory
TL;DR: We establish exactly tight information-theoretic generalization bounds for general randomized learning algorithms.

Abstract: Information-theoretic bounds, while achieving significant success in analyzing the generalization of randomized learning algorithms, have been criticized for their slow convergence rates and overestimation. This paper presents novel bounds that bridge the expected empirical and population risks through a binarized variant of the Jensen-Shannon divergence. Leveraging our foundational lemma that characterizes the interaction between an arbitrary and a binary variable, we derive hypothesis-based bounds that enhance existing conditional mutual information bounds by reducing the number of conditioned samples from $2$ to $1$. We additionally establish prediction-based bounds that surpass prior bounds based on evaluated loss mutual information measures. Thereafter, through a new binarization technique for the evaluated loss variables, we obtain exactly tight generalization bounds broadly applicable to general randomized learning algorithms for any bounded loss functions. Our results effectively address key limitations of previous results in analyzing certain stochastic convex optimization problems, without requiring additional stability or compressibility assumptions about the learning algorithm.

Exactly Tight Information-theorrticc Generalization Bounds via Binary
Jensen-Shannon Divergence
Yuxin Dong' Haoran Guo
Tieliang Gong'
Wen Wen
Chen Li
Abstract
1.0
Information- -theoretc bounds, while achieving significant success in analyzing the generalization of randomized learning algorithms, have been crit- icized for their slow convergence rates and over- estimation. This paper presents novel bounds that bridge the expected empirical and population risks through a binarized variant of the Jensen-Shannon divergence. Leveraging our foundational lemma that characterizes the interaction between an arbi- trary and a binary variable, we derive hypothesis- based bounds that enhance existing conditional mutual information bounds by reducing the num- ber of conditioned samples from 2 to 1. We ad- ditionally establish prediction-bare based bounds that surpass prior bounds based on evaluated loss mu- tual information measures. Thereafter, through a new binarization technique for the evaluated loss variables, we obtain exactly tight generalization bounds broadly applicable general randomized learning algorithms for any bounded loss func- tions. Our results effectively address key limi- tations of previous results in analyzing certain stochastic convex optimization problems, without requiring additional stability or compressibility assumptions about the learning algorithm.
Bound on La
0.6
Scuare
Fast-Ralo
Rinery KI
0.4
Binary (Ours)
6
0.2
0.0
0.1
0.3
[L4: U1
Figure Visualization of ieformmtiion-thooreee generaliza- tion bounds for the population risk Ly evaluated using 0-1 loss with empirical risk Ln 0.2.
conservative vacuous generalization bounds.
Employing information-theoreti measures for analyzing generalization properties has gained considerable traction following the pioneering work (Russo Zou, 2019; Xu & Raginsky, 2017). This paradigm quantifies the amount of information about the training data encoded model param- eters. Unlike conventional techniques, these information- theoretic approaches deliver generalization bounds that both data and algorithm-deeendde with significantly weaker assumptions compared to those of algorithm stability (Hardt et al., 2016; Bassily et al., 2020) or model compression (Arora et al., 2018; Zhou et al., 2019). Recent advancements in this domain have substantially enhanced our understand- ing of stochastic gradient- based learning algorithms (Negrea et al., 2019; Neu al., 2021; Wang & Mao, 2021).
1. Introduction
Despite their appeal, cntomattion-theoredde bounds have faced substantial criticism for their suboptimal convergence rates. Specifically, when the key information quantities are bounded by a constant, these bounds typically decay at a rate of O (())). ). which contrasts with the faster ((2) rate frequently observed practical learning scenarios, e.g.. convex or strongly-convex optimization problems. These bounds may be inherently suboptimal when faster rates are achievable. To mitigate this limitation, (Hellström & Durisi, 2021; Wang & Mao, 2023a) introduce fast-rate bounds by leveraging a linear combination of the empirical risk and information-theoree generalization terms. Mcanwhile, (Hellström & Durisi, 2022b) explores an unconventional relationship between the expected empirical and popula- tion risks using binary KI. divergence. Although these ap-
Characterizing the behavior of generalization error is a cornerstone of statistical learning theory. Traditional ap- proaches grounded in complexity measures such as VC- dimension or Rademacher complexity often fail capture the dynamics of modern iterative and noisy optimization algorithms, such as stochastic gradient descent (SGD) and Adam. Consequently, these methods typically yield overly
Sccoool of Computer Science and Technology, Xi'an Jiao- tong University. Correspondence to: Ticliang Gong <adidas- gtl@ gmail.com>>
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Exactly Tight Information-theoree Generalization Bounds via Binary Jensen-Shannon Divergence
proaches yield faster decay rates when the empirical risk (T.z) approaches or equals zero, they still become vacuous
non-vacuous guarantees for the population risk and is exactly tight for binary loss functions.
for higher population risks (L,), illustrated in Figure 1.
We propose a novel binarization technique for evaluated loss variables, leading to exactly tight generalization bounds (Corollary 3.10) for arbitrary bounded loss func- tions. Unlike prior works, which focus on exact character- izations for interpolating settings (Wang & Mao, 2023a) or specific categories of learning algorithms (Aminian et al., 2021; Zhou et al., 2024), our results are broadly applicable to general randomized learning algorithms without imposing additional strong assumptions.
Another prevalent critique of information -ooommttio--thooetti bounds pertains to their reliance on input-output mutual informa- tion, which often results in severe overestimation for mod- ern deep neural networks. To address this, one line of re- search employs the individual-sample technique (Bu al., 2020), enabling tighter nnermatiio-thhorettee generalization terms. This methodology has been extended to the super- sample generalization framework (Steinke & Zakynthinou, 2020), which facilitates tightened bounds through condition- ing techniques (Haghifam et al., 2020; Zhou et al., 2022a). complementary line of research refines bounds by reduc- ing the dimensionality of the associated random variables, including network predictions (Harutyunyan et al., 2021), loss pairs (Hellström& & Durisi, 2022b), or loss differences (Wang& & Mao, 2023a). These bounds not only yield tighter estimates but also enhance computational tractability. How- ever, all these bounds fail to vanish in at least one of the counterexamples demonstrated by (Haghifam al., 2023), highlighting their inherent limitations.
We extend our exactly tight results to accommodate un- bounded loss functions (Corollary 3.12) and generalize beyond KL divergence to include f-divergence (Theo- rem 4.2) and Wasserstein distance (Corollary 4.3).
We validate the effectiveness of our bounds in capturing generalization dynamics across diverse synthetic and real- world learning scenarios. The results demonstrate that our bounds consistently outperform existing methods and precisely track the true generalization error.
2. Preliminaries
approach to characterizing the relationship between expected empirical and population risks through a binarized variant of the (IS) divergence, which achieves faster convergence com- pared to existing fast-rate and binary KL-based methods. Additionally, we introduce tighter information -hooortt gen- eralization measures utilizing binarized loss variables, sur- passing the tightness of current loss pair or loss difference approaches. By combining these techniques, we success- fully derive exactly tight information -eeemaatio--hhorettic bounds for general randomized learning algorithms. The key contribu- tions of this paper are listed as follows:
In this paper, we propose
Throughout this paper, random variables are denoted by cap- italized letters (X), their specific realizations by lowercase letters (z), and the corresponding spaces by calligraphic letters (A). The distribution of a variable X is denoted by Px, the conditional distribution of X given Y is Pxly, and the conditional distribution given a specific realization is Px|Y=y- Expectations taken over X ~ Px are denoted by Ex. We use (XX represent Shannon's 's (differential) en- tropy, and DKr. (P [] Q) to denote the Kullback-Leibler (KL) divergence of P relative to Q. The mutual information be- tween variables X and Y is denoted by T(X; Y), and their conditional mutual information given Z is [(X; YIZ). Ad- ditionally, we define the disintegrated mutual information as [=X;; Y) = D( Pr The logarithmic function log is assumed to have base e.
We demonstrate that the interaction between an arbitrary variable and a binary variable can be effectively captured using the proposed binary JS divergence (Lemma 3.1), enabling us to derive new informmaiion-hhorette general- ization bounds for the expected population risk.
2.1. Generalization Error
Motivated by recent work on hypothesis- based general- ization bounds, which suggest that removing redundant variables from the conditional mutual information tight- ens the bounds, we establish a new bound (Theorem 3.2) by conditioning on a single sample instead of the pre- vious sample pair approach as in (Zhou et al., 2022a), achieving tighter upper-bound estimates as well as exact tightness for some specific learning tasks. Inspired by the single-loss mutual information frame- work explored in (Wang& & Mao, 2023a), we introduce a single-loss binary JS bound (Theorem 3.6), which is sig- nificantly tighter than existing square-root, fast-rate, and binary Kasbased bounds. Our bound provides strictly
Let Z X' x y denote the instance space. where X' and y' represent the input and label spaces, respectively. The training dataset Z = {Zi] E 2" is constructed by i.i.d. sampling from the data-generating distribution μ. A learning algorithm A takes Z as input and outputs a hypothesis W = A(Z) E W, characterized by the con- ditional distribution Pwiz- Let E W x Z + R+ be the loss function. For a given w E W. the population risk is defined L, (w) & Ezll(w, Z)), where Z ~ μ is independent test sample. The expected population risk is denoted by Ty = Ew [w, distribution μ is generally unknown in practice, the em- pirical risk is used instead and is defined as Lz(w) a
Since the true
2

---

Exactly Tight informattion-hhereee Generalization Bounds via Binary Jensen-Shannon Divergence
1 E (w1 Z.). Similarly, the expected empirical risk is n T., = B. z Z (W)). The generalization error is quantified as W Z) A (W) - (W), measuring the discrep- ancy between the population and empirical risks. Under the average case, it is abbreviated as gen Ew,z gen W Z)].
pected empirical and population risks, defined as:
dis(p _ d (p) 2 + jdka =
(2)
As the JS divergence serves as a proper metric of distance in the space of probability distributions, the binary JS diver- gence can be interpreted quantifiable measure of the "distance" between empirical and population risks.
2.2. Supersample Setting
The supersample framework, first introduced in (Steinke & Zakynthinou, 2020), provides a powerful approach for
We begin our exploration by presenting a foundational lemma upon which the main results in this section are built. This inequality introduces a new perspective for characteriz- ing the interaction between 1/2 --Bernoulli variable and an arbitrary random variable. Notably, this result may hold significance beyond the context of generalization analysis, offering potential applications in broader aspects.
generalization analysis. Let Z = { (2,)%=1 E g denote a supersample dataset drawn i.i.d. from μa, where each el-
ement Z; = ( 7 consists of a pair of samples. A set of binary variables U = {U:]== ~ (n0 1)") used to partition the supersample dataset into train- ing and test datasets. Specifically, the training dataset is
Lemma 3.1. Given random variable X, binary variable Y ~ Bern( ( and a measurable function f(x). Assume that f(X) E [0. 1] almost surely. then
Zo = -12 1Z J= while the test dataset is Zu - yi=1. where U. = =1 U, The empirical and population risks in this setup are formulated as Ln = Ew (Lz (W) and I,p- = E ww.zzul2. (W) respectively. Additionally, let
das (o (xIx=II((X)) S I(X;Y). Additionally, if [xx) is invertible and f(X) E (0. almost surely, the inequality above holds with equality.
L L(W, 23)) for {0, denote the evaluated loss. A pair of losses is represented as L,; (I., I.), and their difference is defined as A, = L7- L.
The proof, which is derived using Jensen's 's inequality and the Varadhan Donsker-Varadban in Appendix B along with proofs of all other results.
Donsker-
formula for KL divergence, is provided
2.3. Binary KL Divergence
The work of (Hellström & Durisi, 2022b) introduces an approach to bound the binary KL divergence between the expected empirical and population risks, defined as follows:
This lemma integrates seamlessly with the supersample framework to analyze the interaction between supersample variables U and the hypothesis or predictions. For illustra- tion, consider supersample dataset containing two samples, Zo and Zi. where Zo is used for training and Zi for test- ing. Define a loss variable evaluated as L = f(W, Zu), where U ~ Bern( randomly selects Zu E [Za, Z It is straightforward to verify that Ln = E and In = [2) By setting X = L, Y = U, and f(() =1 in Lemma 3.1, we establish the following bound:
dKL (p A poog () + (1 p) log (
(1)
This framework is further refined in (Dong et al., 2024a) by eliminating the conditional dependence on Z. The binary KL divergence dKL (Ln, || L,.) delineates an unconventional relationship between Ln, and L, often yielding bounds that are tighter than the square-root or fast-rate counterparts proposed in (Harutyunyan et al., 2021). The proof hinges on a relaxed form of binary KL divergence, defined as:
dis(Ln || Lp) S UL:
(3)
Using the inverse of the binary JS divergence, defined as: Ts (p. c) e sup(q E [o, 1] dis |1 4) S c), (4)
(p g) A yp log(1 q 9 qe?).
A key property of this relaxed binary KL divergence is:
we can now characterize the population risk L, in terms of the empirical risk L,, and I(L:U):
(p |l 4) = supd;(pllg).
Notably, both drs. (-) and d,, (- 1) are jointly convex in their arguments. Additionally, (- exhibits linearity w.r.t its first argument. These properties serve as founda- tional elements for the subsequent theoretical analysis.
Ip S dJs (Ln, UL;
(5)
Next, we leverage Lemma 3.1 to explore several classi- cal types of informition--hherrtiic generalization bounds, demonstrating the substantial potential of this lemma.
3. Generalization Bounds via Binary Jensen-Shannon Divergence
3.1. A Hypothesis- Generalization Bound
Consider the scenario where X= = W. = U,, and f(w) E(w, 2 all conditioned on Z Building on Lemma 3.1, the following bound is established:
In this section, we present a new family of generalization bounds based on the binary JS divergence between the ex-
3

---

Exactly Tight information-theoree Generalization Bounds via Binary Jensen-Shannon Divergence
Table I: Summary of hypothesis-based inforoitio generalization approaches in the literature.
Approach
Reference
Measure
Bound for ((.,)) E [0, 1]
Mutual Information (MI)
(Xu & Raginsky, 2017)
T(W; Z)
T(W; 2)
2m
Individual MI (IMI)
(Bu al., 2020)
(W)
D=1
31(W;)) Z.)
Conditional MI (CMI)
(Steinke & Zakynthinou, 2020)
I(W; UIZ)
I(W; U (Z)
Conditional Individual MI (CIMI)
(Haghifam al., 2020)
I( (2)
1 Σ
22 U.
Individually CIMI (ICIMI
(Zhou et al., 2022a)
1. -
2I(W: U.)
Single ICTMI (SICIM)
Ours
T(WUU122)
E V Nr(W:Ul??
SICIMI (Ours)
improved by eliminating redundant random variables from the key mutual information terms. Building on this insight, Corollary 3.3 reduces the number of conditional samples from 2 (7,) to (7%) compared to the prior work of (Zhou et al., 2022a), thereby sharpening the bound. We designate this method as Single Individually Conditional Individ- ual Mutual Information (SICIMI), whose superiority is formally established in the following proposition:
ICIMI
CIMI
CMI
IMI
MI
Figure 2: Comparison between approaches listed in Table An arrow from to B indicates that A is tighter than B.
Proposition 3.4. For any E [1, n). we have
Theorem 3.2. Assume e(.,)) E [0, 1). then
I(W; U. 2 S I(W; (W.)...).
dıs(Ln L,) S n I(; UW:
The above proposition demonstrates that our SICIMI bound in Theorem 3.2 is strictly tighter than all hypothesis- based information- theorrttc generalization bounds summarized in Table 1. The following example illustrates that our SICIMI bound can be exactly tight for specific learning algorithms:
Theorem 3.2 exemplifies one of the major directions in information-theorriie generalization bounds, leveraging mu- tual information measures that involve the hypothesis W. This line of inquiry originated with the foundational work of (Xu & Raginsky, 2017), which introduced the idea of bound- ing generalization error through the mutual information IW; Z) between the hypothesis and the training dataset. Subsequent efforts have extended this framework, as seen in (Bu et al., 2020; Hellström & Durisi, 2022b), by incorpo- rating individual or conditional information measures.
Example 3.5. Consider the case with 1, μ Bern (t)
Z"I and E(w, 2) = 1w=e. One can verify that:
Ln = 0, Lp = 2 d Lμ) I(W; Us 7 0.216.
gen = 1
I(W;U:)2)) = log2 ~ 0.347 > d1s [nn || Lp)-
Moreover, f eliminating the dependence on 7 in these bounds will be infeasible, as it can be readily verified that I(W; U.) 0 in the example above. These observations collectively suggest that our SICIMI approach is optimal in this line of research, which tries to capture the behav- ior of the generalization error through mutual information measures involving only W, U, and Z.
Table provides a summary of recent hypothesis-bart based approaches to information-theorete generalization analy- sis, focusing on the square-root bound for the specific case where )()-)) [o, 1). chosen for simplicity. For equitable comparison, we demonstrate that our bound can be straight- forwardly relaxed to yield square-rod bound:
Corollary 3.3. Assume ((---) [o, 1), then
3.2. A Prediction- Generalization Bound
/ bI(WWU,129)
gen
Now consider another case where X = LQ Y = U, and f()) = Building on Lemma 3.1, we established that: Theorem 3.6. Assume ((-,-) E [0, 1J. then
An intuitive comparison of the tightness of these bounds is provided in Figure 2. Examining the progression of works (CMI- >> CIMI- - ICIMI) suggests that bounds may be
dns(Ln || L,)) < 1 Σ U.)

---

Exactly Tight Information-theoreii Generalization Bounds via Binary Jensen-Shannon Divergence
Theorem 3.6 represents another principal category of
1. Observe that the function s(1) I with I E {0. 1} satisfies the additional conditions of Lemma 3.1. Con- sequently, Eq. (3) holds with equality.
information-theoretie generalization bounds, leveraging mu- tual information measures involving network predictions. This direction can be traced back to (Harutyunyan et al.,
2. The joint convexity of dxL(- II-) directly implies the joint convexity of d Il Since das || g) attains its minimum when p = q. Eq. (4) provides a unique solution for L, under Assumption 3.7, ensuring that Eq. (5) holds with equality.
2021), which introduced generalization bounds based on the mutual information [ff (Z,); Uz|Z) between super- sample variables and network outputs (f-CMI). Subsequent refinements include evaluated losses (c-CMI in (Steinke & Zakynthinou, 2020; Hellström & Durisi, 2022b) and loss dif- ferences (ld-CMI) or single-loss mutual information terms T(TP; U.) in (Wang& & Mao, 2023a).
3. Finally, Assumption 3.8 guarantees that I(L;; U2) is identical for all E [1,
These observations collectively imply the following result: Theorem 3.9. Assume E(:,)) E (0, then
In Figure 1, we compare our Binary IS bound (Theorem 3.6)
with several related results in the literature, including the Square-Root bound (Theorem 4, (Wang& & Mao, 2023a)), the Fast-Rate bound (Theorem 4.3, (Wang& & Mao, 2023a)), and the Binary KL' bound (Theorem 5, (Hellström & Durisi, 2022b)). The population risk T,, is evaluated within [o, 1] using 0-1 loss to simplify mutual information calculations. As shown in Figure 1, our Binary JS bound provides the tightest estimation for the population risk. Although the figure highlights the case where I., = 0.2, the superior- ity of Theorem 3.6 is consistent across any L, E [0, 1]. Furthermore, Theorem 3.6 consistently offers non-vacuous upper- bouer-bounddo estimations for any L, E [L,, 1]. whereas other bounds yield vacuous results for L, 2 0.8. Most notably, our Binary IS bound accurately recovers the true population risk when 0-1 loss is applicd. This observation will be explored in detail in the following sections.
I = djs Im, Σ (2):Ui) 1=1
This result indicates that the single-loss mutual informa- tion term T[T,;; U?) is sufficient to characterize the true generalization error precisely. Importantly, it suggests that introducing additional assumptions, such as hypothesis sta- bility (Wang & Mao, 2023b), is unnecessary for deriving vanishing information-theoree generalization bounds.
3.3.2. BOUNDED Loss FUNCTION
While the results above are promising, they do not generalize to the wide variety of loss functions commonly used in practice. To address this, we extend these results to general bounded continuous or discrete loss functions by employing a perturbation and rounding scheme for the evaluated loss variables. Let D = {(D), D)) ~ Unif 1]²") be independent random uniform variables. For any i E [1, n] and u E {0, 1}. we define the binarized loss variables as;
3.3. Exactly Tight Generalization Bounds
Next, we explore specific scenarios where the true general- ization error can be precisely recovered using our Binary IS bound. To this end, we outline the assumptions used
throughout this section:
L [1 + DJJ,
1 Bern(L.).
Assumption 3.7. Ln < L.
When ((.-) [0, 1]. it is straightforward to verify that LA E 1) almost surely and satisfies B[4M] B[4M]. Thus, the empirical risk can be equivalently expressed as
We assume that the expected empirical risk is less than or equal to the expected population risk. This assumption is naturally satisfied by any well-trained network.
Assumption 3.8. A is invariant to sample permutations, i.c.
I
1 n
Σ
B
Σ B.
n
Pw.u,,7- P,.u,,z, for any i E [1, n).
We further assume that the learning algorithm A is invariant to the indices of samples. This property is typically satisfied by most noisy and iterative learning algorithms, such as SGD or Adam, since mini- batces are selected uniformly. It also holds true for full-batch gradient descent.
Similar results also apply to I.p. Consequently, it follows directly from Theorem 3.9 that:
Corollary 3.10. Assume ((.,-) -) E 10, 11, then
L = djs' Lns Σ I(T)) U.) 1=1
3. BINARY LOSS FUNCTION
We first show that for binary loss functions, such as the 0-1 loss, the Binary IS bound in Theorem 3.6 is exactly tight:
Given the Markov chain U, - L L. it follows from the data-processing inequality that I(E) U.) S I(LP:U.) U.). Thus, our binarized-loss mutual information (bl-MI)
For this evaluation, we approximate T[T:;; U.) Re 2T(T22 U.).
5

---

Exactly Tight pnformation-theoree Generalization Bounds via Binary Jensen-Shannon Divergence
strictly tighter than the single-loss mutual information in Theorem 3.6 and precisely recovers the true generalization error for any bounded loss function.
3.3.3. UNBOUNDED Loss FUNCTION
Besides bounded loss functions, unbounded ones such as cross-entropy are also frequently encountered in practical scenarios. To address this, extend the aforementioned results to accommodate general loss functions by employing a truncation-and-summiin strategy. For any i E [1, n. and u E {0, 1}. we define the truncated loss as:
Additionally, this perturbation and rounding technique is not confined to our binary JS bound. It can also be applied information-theoretii gener-
to any other prediction-based alization measures, such as e-CMI (Hellström & Durisi, 2022b) or Id-MI (Wang& & Mao, 2023a; 2024), to achieve tighter generalization bounds. Importantly, the bl-MI frame- work offers direct computational tractability, as / (E2;;) U.) only involves binary variables that can be directly estimated through binning. In contrast, estimating I [ U,) for con- tinuous Lọ is significantly more challenging, often requiring kernel density estimation techniques.
6, 1323
The corresponding truncated empirical risk is defined as 5y In = 1 - [s F. T.U:J,,
which can be verified to satisfy Ln = = j=1 8 Similarly, the truncated population risk is denoted as 65L,. By recursively applying Corollary 3.10, the following result can be established:
Recently, (Haghifam et al., 2023) demonstrated that most existing information -iooomaatoon-hhorttiic generalization bounds, includ- ing our Binary JS bound presented in Theorem 3.6, fail to vanish for certain stochastic convex optimization problems. Specifically, consider the following scenario:
Corollary 3.12. Assume 85Ln T. all j 2 1, then
1 Σ 166,
Lp
Σ djs 65Ln,
Example 3.11. (Theorem 17, Haghifam et al. (2023)) Let n
Throughout this section, we assume a loss interval of [0, 1] for simplicity. However, these results can be straightfor- wardly extended to any interval by applying a linear transfor- mation to both the loss variables and the bounds. Addition- ally, non-uniform truncation thresholds in Corollary 3.12 can be chosen to enhance flexibility, enabling tailored ad- justments to specific requirements.
T n², 17 1_ and d = 2n Define the instance space Z =e(()) : E d), where e(i) represents the i-th one-hot vector, and let
Unit( (2). A hypothesis is chosen from W = {w E gd |||||| < } via full-batch gradient descent with the loss function fww, 2) = - (w, 2). using a learning rate 77 over T iterations.
When the samples in Ž are all distinct (which occurs with probability at least 2), the empirical risk is Ln = v while the population risk is I, = 2n/a yielding 1
4. Extending beyond KL Divergence
It is well-established that the widely used KI. divergence specific instance of the broader family of f-divergences, with (=x log x.. In this section, we extend our previous results to accommodate arbitrary f-divergence measures. Given a convex function f :0,, [0,+20) + (-00, +oo] which satisfies that [(x) is finite for any x > 0 and f(1) = O, the f-divergence between absolutely continuous probability distributions P and Q is defined as:
generalization error gen (( However, it can be verified that the supersample variables U, could be recon- structed by the information of LQ. leading to I [L); U4) 2 [(1 (i=== U,) = log 2- ((1). This indicates that the gen- eralization bound in Theorem 3.6 does not even vanish as n - Xc, revealing that bounds relying on evaluated loss- based information measures may be loose for certain learn- ing tasks, including e-CMI bounds (Hellström & Durisi, 2022b) and Id-CMI bounds (Wang& & Mao, 2023a).
D,(P11 & Eq f [1
In contrast, by observing that ((w,2) z) E [0, 1] for any [[]]] ||||| < 1, our exactly tight bound in Corollary 3.10 remains valid in these scenarios, underscoring the advan- tages of our bl-MI measures. This improvement is achieved through our binarization technique, which eliminates ex- traneous information needed reconstruct U, from the observations of L. thereby producing tighter information generalization measures. While recent works also provided vanishing bounds for Example 3. from the perspectives of hypothesis stability (Wang& & Mao, 2023b) and algorithm compressibility (Sefidgaran & Zaidi, 2024), our results ap- ply broadly to general learning algorithms without imposing any stability or compressibility requirements.
Following (Wang & Mao, 2024), the concept of mutual information can be generalized to of f-information as:
(X; e (y Px
Analogous to Eq. (1) and (2), we define the f-divergence counterparts for binary KL and IS divergences as follows:
dr(p1l 2 of ($) + +(1 g)f (12)
ds () A ( pto) + dd (1 ptg))
Using these definitions, we extend our main Lemma 3.1 to accommodate fdivergeence measures:
6

---

Exactly Tight inbormation-thhoreee Generalization Bounds via Binary Jensen-Shannon Divergence
Lemma 4.1. Given random variables X, Y such that Y Bern()) and X {0, 13 almost surely, then
from 2n to n + 1. Beyond traditional supervised learning, information-theorriic bounds have been extended to ana- lyze generalization across meta-learning (Rezazadeh et al., 2021; Jose et al., 2021; Hellström & Durisi, 2022a), semi- supervised learning (Aminian et al., 2022; He et al., 2022), and transfer learning (Wu et al., 2020; Masiha et al., 2021; Wang & Mao, 2022; Bu et al., 2022) paradigms. Further- more, recent works (Haghifam et al., 2023; Livni, 2024; At- tias et al., 2024) have highlighted the limitations of existing information-theoree
[X] Ex-r= = (X)))
4.1. A Exactly Tight /IInformation Bound
Building upon Lemma 4,1, we extend the previous exactly tight bound in Corollary 3.10 to incorporate f fiinformation quantities. Specifically, under Assumption 3.8, we establish the following result:
bounds in certain stochastic convex optimization settings. This paper adequately addresses these issues through the proposed ld-MI measure, which resolves the identified failures and provides an exactly tight bound for general learning algorithms.
Theorem 4.2. Assume ((.-)) E [0, 11. then
1 Σ U:)) 11
dr 4n)
While we use the binary JS divergence as the comparator be- tween empirical and population losses, (Hellström & Guedj, 2024) explores general convex comparator for this pur- pose and further investigates the optimal convex comparator. According to their analysis, the optimal comparator for the standard generalization analysis setting is the binary KL divergence when {(: E [0, 1]. However, their conclusion does not naturally extends the supersample framework, as we have clearly shown that our binary JS outperforms binary KL. This stems from the fact that the key information quan- tities for supersample settings are ILL, Ut). while those for the standard setting are 7 I(; This may explain, from another perspective, why our binary JS method is limited to the supersample setting.
It is noteworthy that the binary f-JS divergence in the above equation retains joint convexity, as f-divergence itself is jointly convex (Theorem 7.5, Polyanskiy & Wu (2024)). Consequently, under Assumption 3.7, the value of Ly can be uniquely determined by Ln and dL-Js(Ln))) || L,), in a manner analogous to Eq. (4).
4.2. A Exactly Tight Wasserstein Distance Bound
Inspired by (Rodríguez Gálvez et al., 2021), which demon- strates that generalization bounds based on Wasserstein dis- tance metries are generally tighter than those derived from informmation-theoretii measures, lowing exactly tight bound using the Wasserstein distance between conditional and marginal loss distributions:
further derive the fol-
The limitations of this work are as follows: While Corol- lary 3.12 provides exact characterization of the gener- alization error for general unbounded loss functions, the precondition 6y Ln S 6 for each j 2 is significantly more stringent than Assumption 3.7 and may not always be satisfied in practice. Additionally, the primary focus of this paper is on expected generalization bounds. remains a compelling avenue for future research to develop exactly tight bounds that hold with high probability, addressing broader spectrum of practical scenarios.
Corollary 4.3. Assume e((--) E [0, then
2
BU. (w Pro)]
gen
The result above is a direct application of Theorem 4.2 to the case of total variation, noting that the Wasserstein distance W and total variation distance Drv are equivalent for discrete distributions P and Q:
6. Experimental Results
(P QP.Q)).
In this section, we assess the tightness of our exactly tight Binary IS bound (Corollary 3. 10) in comparison to several existing information-theoree
generalization bounds from the literature. These include the Fast-Rate bound (Theorem 4.3, (Wang & Mao, 2023a)). the Binary KI. bound (Theorem 5, (Hellström & Durisi, 2022b)), and the f-information series of oracle bounds: CMI, CSHI, and CJSI (Theorems 3.1, 3.2, and 3.3, (Wang & Mao, 2024)). Our experimental settings align closely with those in (Wang & Mao, 2024), where we evaluate three distinct classification tasks?:
5. Related Works and Limitations
In addition to the works of information -hhooreticc general- ization bounds discussed earlier, significant progress has been made in enhaneing these bounds through conditioning (Hafez-Kolale Kolahi et al., 2020) and chaining techniques (Asadi et al., 2018; Zhou et al., 2022b; Clerico et al., 2022). A noteworthy development within the supersample framework is the leave-one-out setting (Haghifam et al., 2022; Rammal et al., 2022), which reduces the sample size requirement
inttps: :// /ttttttttt/btg//////////ttt.hhtt com/ Tuxin- Muxin-Dong//ee Dwwg//onnnnn///// Binarryss.
7

---

Exactly Tight Information-theorer Generalization Bounds via Binary Jensen- Divergence
Binary 0-1 Loss
Cross-Entropy ((0, 1 -/tunccct)
Froe
Froe
Gaussian (Linear)
0.33
Fasi-ita
Braryfi.
Bracy RL
Driry Pt.
0.4
O-nay 25 1Dund
Drery 25 DOun)
CMM
CSM (Dhilk
CSN (Dona))
102
CSM (tiris 2.00 phouda
0.8
CSs pooclet
(Dlude))
c.d (Oroua))
0.00 pliclas
0.2
00.1
0.0
0.0
0.0
0.0
200
(a) 2-Class
(b) 10-Class
(c) 2-Class
(d) 10-Class
0.025
MNIST (CNN)
1..3
0.2
Cdl (D)
(Orode)
0.015
10.
(Drada
0.02
0.1
0.010
0.01
0.005
75
250
1000
4003
10
20
30
75
250
1000
4000
10
20
30
40
Epoch
Epoch
(c) SGD
(l) SGLD
(g) SGD
(h) SGLD
CIFARIO (ReNNet-
0.4
Cnar
0.10
0.5
Dror
8.100
0.3
Kenx
0.08
0. 0.100
0.2
C.04 (onodr
0.05
0.00 Jaoaii
0.075
102
0.1
0.04
8.000
0.02
20003
20300
10
Epoch
Eppch
(i) SGD
(i) SGLD
(k) SGD
(I) SGLD
Figure 3: Comparison of generalization bounds under different learning scenarios. (a-d) Linear classifier trained on synthetic
Gaussian dataset. (e-h) CNN trained on binary MNIST (4 vs. 9). (i-I) Pretrained ResNet-50 fine-tuned on CIFARIO.
Simple linear classifier on synthetic Gaussian dataset.
samples of every (L., i E nI to estimate the uni- fied mutual information T(TQ; U.). This method deviates slightly from prior approaches (Dong al., 2024b;a; Wang & Mao, 2024). However, argue that this modification does not introduce additional bias to the estimated probabil- ity distribution, as discussed in Appendix C.
4-yyyer CNN on binarized MNIST (classes vs. 9). Pretrained ResNet-50 model on CIFARIO.
In all these scenarios, Assumption 3.8 is inherently satisfied, since the linear classifier is trained with full-batch gradi- ent descent while CNN and ResNet-50 models are trained with mini-batch-based iterative learning algorithms such as SGD and SGLD. Moreover, Assumption 3.7 is empirically validated in every experiment conducted.
The final results, presented in Figure 3, demonstrate that our Binary JS bound fully captures the dynamics of the generalization error. When using the 0-1 loss, the Fast-Rate bound also closely tracks the generalization gap, differing only slightly from Binary JS bound. This similarity arises because both bounds leverage the single-loss mutual information [[L;; U.). As shown in Figure 1, the difference between these two is negligible when T T(T U.) is small. However, for continuous loss functions, the gap becomes pronounced, underscoring the superiority of our bI-MI ap- proach. In the case of the SGLD algorithm, the CMI and CSHI bounds effectively utilize the scale information of the loss variables to produce tighter estimates. Lastly, across all the practical learning scenarios considered, our Binary JS bound consistently achieves exact tightness relative to the true generalization error.
To evaluate the effectiveness of generalization bounds for both discrete and continuous loss variables, consider two distinct loss functions: 1) The binary 0-1 loss. 2) A trun- cated version of the cross-entropy loss constrained within [o, 1]. This approach reflects practical scenarios, as cross- entropy loss is typically clamped to a constant range to ensure numerical stability. For the binary 0-1 loss, we em- ploy a simple binning method estimate the probability distribution of PLo.U. For the truncated cross-entropy loss, we use probability density estimation via truncated Gaussian kernels, with bandwidth determined by the rule-of-thumb criterion. To satisfy Assumption 3.8, we jointly utilize the
8

---

Exactly Tight informattiontheoreeie Generalization Bounds via Binary Jensen-Shannon Divergence
7. Conclusion
tion, and tracing. In Forty-first International Conference on Machine Learning, 2024.
In this paper, we introduce a new framework for charac- terizing the relationship between expected empirical and population risks via the binarized Jensen-Shannon diver- gence. Our proposed bounds achieve exact tightness rela- tive to the true generalization error for binary loss functions. Leveraging a binarization technique for supersample loss variables, we derive exactly tight generalization bounds ap- plicable to general learning algorithms under mild assump- tions. These results effectively resolve the limitations of prior informattion-hhorreli bounds, particularly their failure in certain stochastic convex optimization scenarios.
Bassily, R., Feldman, V., Guzmán, C., and Talwar, K. Stabil- ity of stochastic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Sys- tems, 33:4381-4533 2020.
Bu, Y., Zou, S., and Veeravalli, V. V. Tightening mutual information-basedd bounds on generalization emror. IEEE Journal Selected Areas in Information Theory, 1(1): 121-130, 2020.
Bu, Y., Aminian, G., Toni, L., Wornell, G. W., and Ro- drigues, M. Characterizing and understanding the gener- alization error of transfer learning with gibbs algorithm. In International Conference on Artificial Inielligence and Statistics, pp. 8673-8699, PMLR, 2022.
Acknowledgements
This work was supported by the National Natural Science Foundation of China (62172326) and the Fundamental Re- search Funds for the Central Universities (xxj032025002). We would like thank the anonymous reviewers for their valuable suggestions and for bringing the related work of (Hellström & Guedj, 2024) to our attention.
Clerico, E., Shidani, A., Deligiannidis. G., and Doucet, A. Chained generalisation bounds. In Conference on Learning Theory, pp. 4212-4257, PMLR, 2022.
Dong, Y., Gong, T., Chen, H., He, Z., Li, M., Song, S., and Li, C. Towards generalization beyond pointwise learning: A unified information-thern theoretic perspective. In International Conference on Machine Learning. PMLR, 2024a.
Impact Statement
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Dong, Y., Gong, T., Chen, H., Yu, S., and Li, C. Rethink ing information-theoretic generalization: Loss entropy induced pac bounds. In The Twelfth International Con- ference on Learning Representations, 2024b.
References
Aminian, G., Bu, Y., Toni, L., Rodrigues, M., and Wornell, G. An exact characterization of the generalization error for the gibbs algorithm. Advances in Neural Information Processing Systems, 34:8106-811 811668818,1001111111118881811110 2021.
Hafez-Kolahi, H., Golgooni, Z., Kasaei, S., and Soleymani, M. Conditioning and processing: Techniques to improve information-theorcticc generalization bounds. Advances in Neural Information Processing Systems, 33:16457- 16467, 2020.
Aminian, G., Abroshan, M., Khalili, M. M., Toni, I.., and Rodrigues, M. An information-theorrtiiall approach to semi-supervised learning under sovariate-shift. In Inter- national Conference on Artificial Intelligence and Statis- tics, pp. 7433-7449. PMLR, 2022.
Haghifam, M., Negrea, J., Khisti, A., Roy, D. M., and Dz- iugaite, G. K. Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms. Advances in Neural Informa- tion Processing Systems, 33:9925-9999 2020.
Arora, S., Ge, R., Neyshabur, B., and Zhang, Y. Stronger generalization bounds for deep nets via compression ap- proach. In International conference on machine learning, pp. 254-263. PMLR, 2018
Haghifam, M., Moran, S., Roy, D. M., and Dziugiate, G. K. Understanding generalization via leave-one-out condi- tional mutual information. In 2022 IEEE International Symposium on Information Theory (ISIT), pp. 2487-2492. IEEE, 2022.
Asadi, A., Abbe, E., and Verdú, S. Chaining mutual infor- mation and tightening generalization bounds. Advances in Neural Information Processing Systems, 31, 2018.
Haghifam, M., Rodríguez-Gálvez, B., Thobaben, R., Skoglund, M., Roy. D. M., and Dziugaite, G. K. Lim- itations of information- thriorttitheetiiccc generalization bounds for gradient descent methods in stochastic convex opti- mization. In International Conference on Algorithmic Learning Theory, pp. 663-706. PMLR, 2023.
Attias, I., Dziugaite, G. K., Haghifam, M., Livni, R., and Roy, D. M. Information complexity of stochastic convex optimization: Applications to generalization, memoriza-

---

Exactly Tight Informition-theoreiic Generalization Bounds via Binary Jensen-Shannon Divergence
Hardt, M., Recht, B., and Singer, Y. Train faster, generalize better: Stability of stochastic gradient descent. In Inter- national conference on machine learning, pp. 1225-1234. PMLR. 2016.
Polyanskiy, Y. and Wu, Y. Information theory: From coding to learning. Cambridge university press, 2024.
Rammal, M. R., Achille, A., Golatkar, A., Diggavi, S., and Soatto, S. On leave-one-out conditional mutual informa- tion for generalization. Advances in Neural Information Processing Systems, 35:10179-10190 2022.
Harutyunyan, H., Raginsky, M., Ver Steeg, G., and Galstyan, A. Information thhooretictt generalization bounds for black- box learning algorithms, Advances in Neural Information Processing Systems, 222477-224882 2021.
Rezazadeh, A., Jose, S. T., Durisi, G., and Simeone, O. Con- generalization bound
ditional mutual information-batt for meta learning. In 2 IEEE International Sympo- sium on Information Theory (ISIT), pp. 1176-1181. IEEE, 2021.
He, H., Yan, H., and Tan, V. Y. Information -eterrrtttt char- acterization of the generalization error for iterative semi- supervised learning. The Journal of Machine Learning Research, 23(1): 10011-10411999 2022.
Rodríguez Gálvez, B., Bassi, G., Thobaben, R., and Skoglund, M. Tighter expected generalization error bounds via wasserstein distance. Advances in Neural Information Processing Systems, 14119199-1 2021.
Hellström, F. and Durisi, G. Fast-rate loss bounds via con- ditional information measures with applications to neural networks. In 2021 IEEE International Symposium Information Theory (ISIT), pp. 952-957. IEEE, 2021.
Russo, D. and Zou, J. How much does your data explo- ration overfit? controlling bias via information usage. IEEE Trunsactions on Information Theory, 66(1):302 323, 2019.
Hellström, F. and Durisi, G. Evaluated cmi bounds for meta learning: Tightness and expressiveness. Advances in Neural Information Processing Systems, 35:20648- 20660, 2022a.
Sefidgaran, M. and Zaidi, A. Data-dependent generalization bounds via variable-size compressibility. IEEE Transac- tions on Information Theory, 2024.
Hellström, F. and Durisi, G. A new family of generaliza- tion bounds using samplewise evaluated cmi. Advances in Neural Information Processing Systems, 35:10108- 10121, 2022b.
Steinke, T. and Zakynthinou, L., Reasoning about general-
ization via conditional mutual information. In Conference on Learning Theory, pp. 3437-3452. PMLR, 2020.
Hellström, F. and Guedj. B. Comparing comparators in generalization bounds. In International Conference on Artificial Intelligence and Statistics, pp. 73-81. PMLR, 2024.
Wang. Z. and Mao, Y. On the generalization of models trained with sgd: Information -ooomation-theoreticc bounds and im- plications. In International Conference on Learning Rep- resentations, 2021.
Jose, S. T., Simeone, O., and Durisi, G. Transfer meta- learning: Information -iceortion-thoortticc bounds and information meta-risk minimization. IEFE Transactions on Informa- fion Theory, 68(1):474-501 2021.
Wang. Z. and Mao, Y. Information-theoreiic analysis of unsupervised domain adaptation. In The Eleventh Inter- national Conference on Learning Representations, 2022.
Livni, R. Information theoretic lower bounds for informa- tion theoretic upper bounds. Advances in Neural Infor- mation Processing Systems, 36, 2024.
Wang, Z. and Mao, Y. Tighter information-thhorede general- ization bounds from supersamples. In International Con- ference on Machine Learning, pp. pp. 2023a.
PMLR,
Masiha, M. S., Gohari, A., Yassaee, M. H., and Aref, M. R. Learning under distribution mismatch and model mis- specification. In 2021 IEEE International Symposium on Information Theory (ISIT). pp. 2912-2922299 2917. IEEE, 2021.
Wang, Z. and Mao, Y. Sample-condition hypothesis stabil- ity sharpens iiformation-thhoretti generalization bounds. Advances in Neural Information Processing Systems, 36, 2023b.
Negrea, J., Haghifam, M., Dziugaite, G. K., Khisti, A., and Roy, D. M. Information thhooretic generalization bounds for sgld via data-dependent estimates. Advances Neural Information Processing Systems, 32, 2019.
Wang. Z. and Mao, Y. Generalization bounds via condi- tional f-information. In Advances in Neural Information Processing Systems, 2024.
Neu, G., Dziugaite, G. K., Haghifam, M., and Roy, D. M. cermatiio-thhoretii generalization bounds for stochas- tic gradient descent. In Conference on Learning Theory, pp. PMLR, 2021.
Wu, X., Manton, J. H., Aickelin, U. and Zhu, J. Information- theoretic analysis for transfer learning. In 2020 IEEE International Symposium on Information Theory (ISIT), pp. 2819-2824. IEEF, 2020.
10

---

Exactly Tight Information-thcoreiie Generalization Bounds via Binary Divergence
Xu, A. and Raginsky, M. Information-theorrti analysis of generalization capability of learning algorithms. Ad- vances in Neural Information Processing Systems, 30, 2017.
Zhou, R., Tian, C., and Liu, T. Individually conditional individual mutual information bound on generalization error. IEEE Transactions on Information Theory, 68(5): 2022a.
Zhou, R., Tian, C., and Liu, T. Stochastic chaining and strengthened information-theoree generalization bounds. In 2022 IEEE International Symposium on Information Theory (ISIT), pp. 690-695 IEEE, 2022b.
Zhou, R., Tian, C., and Liu, Exactly tight information- theoretic generalization error bound for the quadratic gaussian problem. IEEE Journal Selected Areas in Information Theory, 2024.
Zhou, W., Veitch, V., Austern, M., Adams, P., and Orbanz, P. Non-vacoe Von-vuuuous generalization bounds at the imagenet scale: pac-baaesian compression approach. In Interna- lional Conference on Learning Representations, 2019.

---

Exactly Tight information-theoreee Generalization Bounds via Binary Jensen-Shannon Divergence
A. Prerequisite Definitions and Lemmas
Definition A.I. (Sub-Gaussian) A random variable X is o-subbGaussian if for any p E R, Blee(X- exp( e2ze)
Definition A.2. (Kullback-Leibler Divergence) Let P and Q be probability measures the space X, then the KI. divergence from P to Q is defined as (P || Q) _ fx p(z) log
p(z)
dz.
g(x)
Definition A.3. (Mutual Information) Let (X, Y) be a pair of random variables with values over the space X x V. Let their joint distribution be Px,y and the marginal distributions be Px and Py respectively, then the mutual information between X and Y is defined as T(X;Y) = ( (xx,y / PxPy).
Definition A.4. (Wasserstein Distance) Let -(::) be metric and let P and Q be probability measures on X. De- note T(P, Q) as the set of all couplings of P and Q (i.e. the set of all joint distributions on & X with two marginals being P and Q), then the Wasserstein distance of order p between P and Q is defined as W (Pp(P, P, Q) - 1/p
(inf fxxx dx, x')P dr((x,z))
Unless otherwise noted, we use (.:-) to denote the Wasserstein distance of order 1.
Lemma A.5. (Donsker-Vuralhcc formula) Let P and Q be probability measures defined on the same measurable space X, where absolutely contimuous with respect to Q. Then for any bounded measurable function f : X + R.
D(P -up (up((E-Pl((x)) - log Ee- (())
where X is any random variable such that ex is Q-integrable and Ep(X] exists. Lemma A.6. (Lemma 2, Hellström & Durisi (2022b)) Let X be random variable that satisfies X E [0, 1] almost surely and [ μ.. Then for any N E I.
Ex
( 1
Lemma A.7. (Pinsker's Inequality) Let P and Q probability measures defined on the same space, then S 1/2 (PI(()
B. Omitted Proofs
Lemma 3.1 (Restate). Given random variable X, binary variable Y (Ben and measurable function fx). Assume that fX) [0, 1] almost surely, then
dis (Ex]y=o (xx <((XYY.
Additionally, if f(x) is invertible and f(X) E 10 almost surely, then the inequality above holds with equality.
Proof. By Jensen's 's inequality and the joint convexity of d- II-,, we have
dKL dKL (xx] = sup d, (Xx]=
I Sup Ex (4
(6)
Similarly, we can prove that
drr. (Ex]y Ex[f(X)) I Ex 12p
Notice that [x[](X)] [ we then have
2
1
1
d1s [(x]
dKL (Bx) + (ExIx (x(()))
2
sup (x
(7)
2
ME (0(1)
12

---

Exactly Tight Inforoition-theorrtie Generalization Bounds via Binary Jensen-Shannon Divergence
By applying Lemma A.5 with P Po Q Px and f(x - d [Ixx we have
DKL (0 Px) 2 ox [Xx(XXXX log Ex (d,(((x) |xx [ExI(xX)]]
Then by applying Lemma A.6 we know that for any 7 E R.
Ex e d (x(() [X 1
Plugging this into the inequality above and taking the supremum over 7, we can get
DKL (Pxjy Px) 2 o4) [xxIxxx)
(8)
Similarly, have the same result for the case Y
DKL (Px Px) sxnBxxaa1@//////)))
Combining the two inequalities above, we now have
I(X = Ey [DL Px)]
1
DRI. DRI (Px
|| Px) + + DKi. (Px Px)
sup E Ex]x=a(d [xxxxx)))
(0.1)
Plugging the inequality above into Eq. (7), we finally get
das (Exiy= Exy= S 1
Σ (0,1) ?
sup [ (Xx;))
(()
The proof of the first part is complete.
To prove that the main inequality of the lemma holds with equality, we only need to check if the inequalities in Eq. (6) and (8) hold with equality. When X E {0, 1}, we have [x = P(X =| = 0) and
dkr. (ox Bx(x)) sup [Bx
Bx
sup P(X = 1| = 0)7 - log(1 E [X] + Ex(ee)
ssup P(X = 0|Y = llg(1 - Ex [X] + Ex(X]e))
P(X 1|Y = 0)(1 log11 Ex[x] + Ex([je
sup Ex d Y
x [XX] Ex [x])]
On the other hand, we can prove that
DKL (Px Px) = dKL (P 0|Y P( 0))
= dKL (P(X = 1|Y = =0) | = 1))
dKL [E || EE [X]]
The same results also hold for Y = 1. Combining the results above, we then have
das [ x X
E Ex
Σ
D (Px || Px) I(X;Y).
ME (0.1)
Therefore, when f(X) E {0, 1} almost surely, we have
dis (Ex ( E = I(f(X):Y)
Combining with the condition that f(X) is invertible, we have I(f(X):Y) = I(X;Y) which finishes the proof.
Y) I) by the data paoc-ssocgssing inequality,
13

---

Exactly Tight Information-theorett Generalization Bounds via Binary Jensen-Shannon Divergence
Theorem 3.2 (Restate). Assume ((,,) E [0, 11. then
1 n
dL || Lp)
Proof. By Jensen's inequality and the joint convexity of dkL((- [I.), we have
dKL[
Ln
In + Lsp
= dxL
Σ
B.
E
((WW.Z70) |]
Σ B (9) e(W, 2
n
2
n i=1
2n i=1
n
dkL
Ew:2,u:
[e(W, 27:,)
2 F.
(() + e(W.
((W,2?>)) 2
71
Σ dKL
1
[e(w] |?)]
+ 2 w. [:)]
1
2
((W, |
1
[C(W] 2
E E
2
1
dKL
B Ow.ZQiue=u/
[[W.
|| |Ew.29 e(w, 22,1)
2n
i=1
+
dkl.
[8 (B..24ui-1 (eww;
Ew:2? ((w,, 2;11)
2n
i=1
1
E Ezz
dKL
B (B
(e(,
w e(w; |
2n
dkl. [ (BW12)u1==(((0
[e(W. |
Ewiz [e(wZ)))] 1
Ez!
2n
8=1
Similarly, one can prove that
In
+
I,
dKL (EW11 1ww222.0000 U5, [((,, | |2 [e(w; 229)))
dkL
Lp
E3 0/
2
2n
i=1
n
Ezy [dkL (E 12:124.00000 [e(w; [erw: 2 1 [ccw: 2 2
2n
Notice that
1 (e(W
|9)
1
E
1 (0122,U,,11 [((,; | + +EIizg [((V] 2291)
2
E 2 [e(w.
1
E
[E u,= [(w. | + 1wi2),u, [ 2,)))
2
Combining the results above and applying Lemma 3.1 with X = W 2 (or X = wl2,), Y = U, and f(W) E(W (or f(W)- = ((W D. we can get
1
Ln + Lyz
+ 1
Ln + Lu
dLs(Ln) || Ln) = dkl
Ln
dkl Ln
2
2
2
5
1
Σ
E
dds
(E
(e(w: }
F [((W, [e(W:z9))) )
2n
1=1
+
1
Σ
Bz!
dds
(Bwiz) ((..) [W)
E
Ew 21 [(W, 2+1
(9)
2n
14

---

Exactly Tight Information-theorele Generalization Bounds via Binary Jensen-Shannon Divergence
1
E Zz
(W:U3) -
n +
Σ
1 12 (W:U.)
2n
2n
1 2n
I(W:U:12)) + I(W:U.
Following the formulation of the supersample setting, we know that the learning algorithm A is unaware of the supersample variables U.. Therefore, it should be invariant w.r.t the supersamples Zú, i.e the distributions Pw.u. Pw.u.20 and P W.U.Z!! should satisfy certain symmetry such that
PW. Pw.ZqIU;=0 = P ". Pw. Pw.29|0;=1 = Pw I
(10)
Therefore, we can conclude that (W; U,129)= U(W;) and the proof is complete. Corollary 3.3 (Restate). Assume (((,-) E [0, 11. then
/2(W;
Proof. Applying Lemma A.7, we have that for any p.g E [0. 11.
+ 4
p a+0 q
dıs(p
2 dkı
p
+ dKL
2
2
2
2
di
p
p+q 9
+ dry
(9)
9
p+
= 22(p (p 9)²
2
2
With the same technique to bound Eq. (9), we then have
E F Jeww, ((W,, 2 - E Bwizi u1 [(W, 2
2d3s (E11z),
[(W, [(W,2%)]
1 ((W:229)
(
S (W:
Similarly, we can prove
B B [(W,, [WW - E B -0,00 -0
[(W, S 22:2
By the definition of generalization error and Jensen's 's inequality, we obtain
22 e(W; -
gen
Lzz (W) Liz (W)]
E w.
e(W: 2(41
11
E. 12, (e(W. ]
[e(W) -.. ||]
Ez,y
- EEwiZ.u. Z.
E W1 20 [e(W,
- E 1w129,U.=1 (ew, 2.,) ) |]
2n
1
Σ
Ezz
Ew 11 =1=
<(W, ] - Ew 2,, ((W, 2
2n
1
22 (W;U3)
+ +EZ V /2r2: (W:
E %0
2n
2I(W: U219) +
21(W; (1))
2n
15

---

Exactly Tight Information-theoreii Generalization Bounds via Binary Jensen- Censen-Shannon Divergence
11
n
The proof is complete.
Proposition 3.4 (Restate). For any E [1. we have
I(W: U.12,) I (W:UU.Z.)
Proof. Since 29. : and U; are independent, we have (2) 0. Then by the chain rule of conditional mutual information, we can prove that
I(W:U:12) - I(W; ( + [() U, - I(W, U.;
I(W;U, -
= U(W
Theorem 3.6 (Restate). Assume ((.,) E [0, 1I. then
a
dis Im 11 Tup) I n
Proof. By Jensen's 's inequality and the joint convexity of d=L(- || .), we have
dkL
Ln
Ln
+ Ln
dKL
Σ
U.
L
1
EL
EL. [ + L7]
2
n im1
2n
im1
1 EL. [1 + n.:]
dKL
ELLUS
(11)
2
11 (
dkL
[
+ Br. [
2 Ez, و + L!l)
n
Similar to Eq. 10, the distributions Pr..uu and PıJ.u. should satisfy certain symmetry such that
PLşIU.=0 PLujU==1, PLyIC== Pagiu PLマ PL.-
Therefore, it satisfies that
Ln + Lu 2
drL.
Ln
<
dRI. EE..uC:- Brg [19]]
Similarly, we can prove that
dKL
Txp
Ln + Lu
<
deL E Bzg [1])
2
Notice that [RqqU,=1 [-]]] + R [T.0])
F [..]]
Then by combining the two inequalities above and applying
Lemma 3.1 with X T. Y U, and S(T.))
T.Q, we have
1
In Ly ) + dkL
1
Ln + Ly
dns(Ln) Lμ)
2 dKL Ln
L
2
2
d1s
Erypu, - [4.1
E
Ergju.=1 [19
The proof is complete.
16

---

Exactly Tight information-theoree Generalization Bounds via Binary Jensen-Shannon Divergence
Theorem 3.9 (Restate). Assume Assumption 3.7 and 3.8 hold and e(;, {0, 13, then
n Iun ni
b = dis
T((2UU))
Proof. Notice that Assumption 3.8 implies Er,,Us equality. Therefore,
L
Ers Us [1.]
for any i,j [1, have Eq. (11) holds with
In +
Lup
dKL
Ln
dKL 0
ELg [4
2
dxL
L
In +
Iup
n
deL E [i]
E2D [ )
2
n
Then by applying the additional condition of Lemma 3.1 with X = L Y = U₁ and S(L = L we have
dn Lp)
Σ
dkL EB [49]
Bgg [=]]) +
1
Σ
dkL E U1= [
Egg [T!]
2n
2n
1=1
imi
1
d3s (B
[
E [49]
Ti
1
U(L);U,)
n
When Assumption 3.7 holds, by the strong convexity of binary KL divergence, obtain
n
I(L)U.)
Ly djs
Las Σ
which completes the proof.
Corollary 3.10 (Restate). Assume Assumption 3.7 and 3.8 hold and E(: :) E [0, 11. then
1 Σ (()) Lns
Lp djss
t=1
Proof. From the definition of the binarized loss L we have L E 10 almost surely and
E E E
E2g [T0] = 1 [722]
for any é E [1, n] and E {0. 1}. Therefore,
Ln + Lu
dKL
Ln
deL E E [43]
B24 [z8]
2
7
dkl. Er.qc.= [Mg]
Byg [29]
Similarly, prove that
In +
Lu
dkL
Lp
deL
Eigi. -1 [77]
B [z-]
2
i=
17

---

Exactly Tight Inforoition-theoreii Generalization Bounds via Binary Jensen-Shannon Divergence
Then by following the proof of Theorem 3.9, we have
n
Ly djs
Las Σ IIP.
Corollary 3.12 (Restate), Assume Assumption 3.8 hold and 0z I' S 6z for any j 2 1, then
(0,L):
J8
1=1
Proof. From the definition of the truncated loss L, we have 8, E {0, 1] almost surely and
D
6,L
for any i E [L, r.] and E {0,1) 13. Then by following the proof of Theorem 3.9, we have
n
dıs(o, 11 6 [,)
n
for any j 2 Combining with the condition that ,nLn S b. we finally have
x
n
6,
Iu
ds
8yTm:
T(, U.) n
j=1
j=1
Lemma 4.1 (Restate), Given random variables X, Y such that Y ~ Bern (2) and X E {0, 1} almost surely, then
8xxI Ex|== (X)
Proof. From the definition of f-information, we have
P(X = x, Y= v)
1x(x)Y)= = Σ Σ
P(X = x)PP( = v)s
P(X = P = =1)
zE(U,1) sE(0.1)
P(X x ( =
Σ
Σ P(X= P(x=2)f(
P(X=I)
2E (0.1) (0.1)
Noticing that ExIr= x
[x] we obtain
2
1
E E
(X)
y
+ _d [X] Ex
2
1
Σ [xXxI==((]||XxXXX]
2
ve (0.1)
1
Σ
Ex|X]5
[xXx=y|X]] +(1-Ex|X]) ( (
1 F - 1x1)
Ex(X (1-
2
Ex[X]
(e(0,1)
1
Σ
P(X (X=00]1 0)S
P(X= = - +P(X 1])
P(X = 018 =w) =0)===))
P(X = (1Xx=11Y=1
2
P(X=1)
vE(0.1)
Σ
Σ
Σ P(x=x))
P(X= x/Y P =1)
2
P(X==)
(E(0.)
Combining the two equalities above yields the desired result.
18

---

Exactly Tight information-theoree Generalization Bounds via Binary Jensen-Shannon Divergence
Theorem 4.2 (Restate). Assume Assumption 3.8 hold and e(:,)) E [0, 1]. then
dn Lp) UL).UU))
Proof. By Assumption 3.8 and the definition of f-divergence, we have
ds
Ln
Ln + 42
ds
Li
Us
Li
U1
1
BLg
[L] + Lil
2
71
2n
i=1
y
- Er.
1
[1] + [.]]
2
1=1
Σ
dj
FL, Er, [..]]
+ E E [4]]]
2 Rr, [1 + [.,]]
2
Σ
d,
E EL1 =0 [z
E2y [b
n
d
(B [1]]
Ezg [2.))
n
Similarly, prove that
dr Lu
Ln + Lip
= Σ
ds
(ELoI [2.]
Erg [1)]
2
i=1
By applying Lemma 4.1 with X T.y and Y = Una we have
1 dd Ln
In Toy
1
I' + Typ
d |1 Lnn)
+ =d1 L4
2
dy-Js (Bigiu=00 [E.]]]
E REQU [T9]]
i=1
15(L U.).
The proof is complete.
Corollary 4.3 (Restate). Assume ((:,-) E [0, 1). then
gen Σ Eu, W Piqiee+ PL:)]
2
Proof. By taking f(x) = 1/x - -1/, we obtain the total variation metric:
drv(pll = =pp- g)-
We then have
1
Ln Lu
1
Ln La
dL Lμ)
drv
Ln
+ drv
Lp
Tn
Taju
T,p.
Ton
Igen
2
2
19

---

Exactly Tight Information-theorele Generalization Bounds via Binary Jensen-Shannon Divergence
By the equivalence between total variation and Wasserstein distance for discrete distributions, we can get
P(L = -,U P(L: -)P(U = =u]f = -
UT,(L;;
E 1E(0.1) wE(0.1)
E
(PLL) -1U; (
Σ
P(U =
Σ
P(L. 1)
P(L.=1)
wE(0,1)
lE(0,1)
Eus Drv Preyu Pro.)
Bus
W (LLIUU. PLo)
Combining the two equalities above and Theorem 4.2, we obtain
gen 2drv-Js Lp) = T
Σ (Tv()):
= 2
Σ Ev, W PERRU, PE:) (L. n
The proof is complete.
C. Experiment Details and Additional Results
In this section, we present experiment details and additional experimental results that were not included in the main text due to space limitations. The deep learning models are trained with an Intel Xeon CPU (2.10GHz, 48 cores), 256GB memory, and 4 Nvidia Tesla V100 GPUs (32GB). The generalization bounds included the comparison are listed as follows:
Theorem C.I. (Square-Root), (Theorem 3.2, Wang & Mao (2023a)) Assume {(.)) :) E [0, 1). then
gen
2I(A;; U.).
Theorem C.2. (Fast-Rate), (Theorem 4.3, Wang Mao (2023a)) Assume ((,,) E [0, 1], then for any C2 E (o, log and
2022)
C1 2-
1,
20₂
gen & C. +
Σ U(L
nC2
i=1
Theorem C.3. (Binary KL), (Theorem 4.8, Dong et (2024a)) Assume E(.-)) [0, 1]. then
Ln + Lu
dRL
Ln
ILL
2
1=1
Theorem C.4. (CMI-Oracle), (Theorem 3.1, Wang Mao (2024)) Assume f(.,-) E [0, 1J. then
gen < Σ
V 22 Aa + [R. (G.)))((A
Theorem C.S. (CSHI-Oracle), (Theorem 3.2, Wang & Mao (2024)) Assume ((.,)) E [0, 1}. then
1
1, [A] + 2 [C.ll) 12 U:). 4E
gen
Ez
n1
Theorem C.6. (CISI-Oracle), (Theorem 3.3, Wang & Mao (2024)) Assume E(.,)) [0, 1), then
2
gen
E
Ez,
4E 4E
22
A + |B [Gil] 13 (A U.)
t=
20

---

Exactly Tight Information Generalization Bounds via Binary Jensen- Divergence
Binary 0-1 Loss
Cross-Entropy (00, 1] -truncccted)
0.3
0.6
0.5
0.3
Pale
weyil
0.5
(Oun))
10un) CM (Dride)
Brary
0.2
CSH (Orada)
CMll (rrad))
Col (onecia
Cll (Cridls)
(Orscia
0.4
DM (Cnsci)
0.3
0.2
0.0
1.0
0.1
75
250
1000
4000
76
250
1000
4030
75
250
1000
4000
75
250
1000
4000
(a) 5 = 0
(b) = 0.05
(c) 8 = 0
(d) 5 = 0.05
1.0
0.6
1,0
0.6
0.8
1.0.6
0.6
0.6
0.4
0.4
0.4
0.2
75
250
1000
4000
76
250
1000
4020
75
250
1000
4030
1000
4000
(c) 6=) = 0.1
(f) 5 = 0.15
(g) 606=00 = 0.1
(h) 5 = 0.15
Figure 4: Comparison of generalization bounds under the binary MNIST classification task, where the labels are randomly flipped with probability 8.
In the theorems above, G3 is defined as G, A (-1)U: A. and satisfies Ec, = gen when Assumption 3.8 holds.
In this experiment, we employ all samples of (L., U.), é E [L, n]. simultancously to estimate the shared joint distribution PLO.U.. This approach differs slightly from prior methods (Harutyunyan et al., 2021; Hellström & Durisi, 2022b; Wang Mao, 2023a; 2024), which estimate PIç.u, using only the samples of the corresponding pair (LQ, U,). Nonetheless, we argue that our method still produces an unbiased estimator for the joint distribution PLD.U.- Taking the binary loss function as an example, let Pc(1, u) = 1 for Prq.u, is then given by Px- = - P.(1.v) w). Since E,g,,, [P]] = Pro.u,. it follows that Eng,o, [Px] = Prç.u,. confirming P. as an unbiased estimator. Therefore, although the samples (L), U;). i E [1, are interdependent, our method avoids introducing additional bias in probability density estimation. Furthermore, previous estimators are known to overestimate significantly during the initial stages of SGLD iterations, as noted in (Harutyunyan et al., 2021; Wang & Mao, 2023a). Our approach mitigates this limitation, enabling the estimated upper bounds to accurately track the trends of the generalization error throughout the entire training process.
1 =i denote the empirical distribution for sample (I.), U.). The empirical estimator
Our synthetic experimental settings closely follow those in (Wang & Mao, 2024), where synthetic Gaussian datasets are generated using the scikit-learn package. The task involves training 1-layer linear classification network on 5-dimensional input data points. Class centers are randomly selected from the vertices of a 5-dimensional hypercube, and data instances are then independently drawn from the standard Gaussian distribution at each class center. The model is trained using full-batch gradient descent with a fixed learning rate of 0.01 for 300 epochs. For each test case, we generate 50 distinct supersample datasets Z, and for each dataset, we draw 100 different supersample variables U, resulting in 5, 000 independent runs.
In addition, we replicate the experimental settings of (Harutyunyan al., 2021; Hellström & Durisi, 2022b) for two distinct real-world learning tasks: 1) MNIST (4 vs. 9) classification using 4-layer CNN network, 2) CIFARIO 10 classification using a pretrained Re network. For each learning task, k instances of Z are sampled, and for each Z, k2 samples of U are drawn, yielding K1 x k2 independent runs in total. The values of (k1, are (5, 30) for MNIST and (2, 40) for CIFAR10. respectively. To further investigate scenarios with substantial overfitting, we conduct an additional experiment introducing random label noise in the binary MNIST classification task. As shown in Figure 4, our Binary JS bound consistently yields exactly tight estimates of the true generalization error across all experiments, including those with significant label noise.
21


Reviews:
[{"review_id": "GP3k07e3PF", "reviewer": "Reviewer_o7Wh", "summary": "The paper discusses tight information theoretic bounds for the generalization error. The bound is general and can be applied to any machine learning model. This line of work is based on the seminal works of Xu and Raginsky (2017) and follow-up works that use the mutual information between training data and the output of the learning algorithm as a measure of generalization. The research program is motivated by the goal of obtaining a tight computable bound.  Here are the highlights:\n\n* The paper uses the supersample idea (Section 2.2), a data processing like inequality for Jensen-Shannon divergence (Lemma 3.1) to obtain a result. \n* Generalization bounds are obtained in Theorem 3.2(where $I(W;U_i|\\tilde{Z}^0_i)$ is used) and Theorem 3.6 (where $I(L^0_i;U_i)$ is used).  \n* Proposition 3.4 shows that the bound based on $I(W;U_i|\\tilde{Z}^0_i)$ is strictly tighter. \n* In section 3.3, the bound in Theorem 3.6 is shown to be tight for various cases. Finally some extensions are presented in Section 4 based on f-divergence, and the experiments are presented in Section 6.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer o7Wh, thanks for your thorough reading and constructive questions! We are addressing your questions as follows:\n\n---\n\n**On the Nature and Significance of Information-Theoretic Results**\n\nThis is an insightful and important question involving many works studying information-theoretic bounds. We will clarify the significance of our work from two key perspectives:\n\n**1. Understanding the Limits of the Information-Theoretic Approach**\n\nRecent efforts to tighten bounds have proceeded along two main directions:\n- **Improving dependencies between mutual information and generalization error:** progressing from square-root bounds → binary KL → fast-rate → and now, our binary JS.\n- **Refining the mutual information term itself:** evolving from MI → CMI → $f$-CMI → e-CMI → ld-MI → and finally, our bl-MI.\n\nThese efforts have brought increasingly tighter (though still suboptimal) bounds. This naturally raises the question [1]: *For which learning problems is the CMI framework expressive enough to accurately estimate the optimal worst-case generalization error?* Or, are there learning settings where the CMI framework must fail? Some prior works (e.g., Haghifam et al., 2023) explore this on SCO problems. Our work provides a definitive answer: the information-theoretic approach is capable of achieving exactly tight bounds across a broad range of learning scenarios. In doing so, we have adequately addressed this open question and mark a meaningful milestone in this direction.\n\n**2. Strengthening Theoretical Guarantees for Downstream Applications**\n\nIt should be noted that our results are developed in a very general setting. They can become especially valuable when applied to more specific contexts. Two particularly promising directions are:\n\n- **Out-of-distribution (OOD) generalization:** Prior works [2,3] use information-theoretic bounds to identify key components for OOD generalization and propose loss-level optimization objectives (e.g., Eq. (5) in [2], Sec. VII.D in [3]). Our results can be adopted to provide a more robust theoretical foundation for such methods.\n- **Understanding noisy, iterative learning algorithms:** For algorithms like SGD and SGLD, information-theoretic bounds (e.g., MI [4], CMI [5]) have been used to analyze the trajectory of the hypothesis and link algorithm behavior with some interesting factors like gradient variance or landscape flatness. We believe our loss-based bounds will further advance this line of works to analyze the loss trajectory (e.g., [6]).\n\nThese applications highlight the practical value of our results, though a detailed exploration lies beyond this paper’s scope.\n\n---\n\n**Alternative Proof for Lemma 3.1**\n\nThank you for this perspective. While intriguing, we currently do not see a direct derivation of Lemma 3.1 from the $f$-divergence-based data processing inequality. This route may be able to characterize relationships between $d_{\\text{JS}}$ and $I_{\\text{JS}}$, but not Shannon's mutual information. We consider this a promising direction for future work.\n\n---\n\n**On the $O(1/n)$ Convergence Rate**\n\n(Strongly) convex optimization is a well-known case exhibiting $O(1/n)$ convergence (e.g., [7]). We agree that information-theoretic bounds with $1/n$ or $\\sqrt{1/n}$ terms do not necessarily reflect their real rates. Nevertheless, our aim is not to claim a universal $1/n$ bound, but rather to point out that earlier bounds with explicit $\\sqrt{1/n}$ scaling may be inherently suboptimal when faster rates are achievable.\n\nAs suggested, we fit the generalization error curves in Figure 3 using $y = ax^b$, and report:\n\n| Dataset  | Gaussian | MNIST | CIFAR-10 |\n|----------|----------|-------|----------|\n| $b$      | -1.084   | -0.585| -0.326   |\n\nThis indicates a convergence rate near $O(1/n)$ for synthetic data and closer to $O(\\sqrt{1/n})$ on real datasets.\n\n---\n\n**Other Points**\n\nWe now cite Russo and Zou’s seminal work, and explicitly denote $W = \\mathcal{A}(\\mathbf{Z})$ to clarify the dependence on training data. Regarding the number of training samples, we note that the curves for different bounds already converge closely at large $n$, and thus increasing $n$ may not further enhance this comparison.\n\n---\n\n[1] Information complexity of stochastic convex optimization: Applications to generalization, memorization, and tracing. ICML, 2024.\n\n[2] On $f$-Divergence Principled Domain Adaptation: An Improved Framework. NeurIPS, 2024.\n\n[3] How Does Distribution Matching Help Domain Generalization: An Information-theoretic Analysis. TIT, 2025.\n\n[4] On the generalization of models trained with SGD: Information-theoretic bounds and implications. ICLR, 2022.\n\n[5] Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms. NeurIPS, 2020.\n\n[6] Analyzing generalization of neural networks through loss path kernels. NeurIPS, 2023.\n\n[7] Train faster, generalize better: Stability of stochastic gradient descent. ICML, 2016.", "claims_and_evidence": "The main claim is tighter information theoretic bounds backed by proofs, which seem to be sound. The tightness of the bound is shown in various experimental results as well as theoretically proven.", "methods_and_evaluation_criteria": "The paper is mainly a theoretical one. The main idea is the use of an inequality based on the Jensen-Shannon divergence and relate that to a mutual information term. The bound is shown to be provably tighter and, in some cases, exactly tight. The key is using the supersample framework and a data processing like inequality for Jensen-Shannon divergence (Lemma 3.1). The key improvement with respect to previous bounds is that the bound is the sum of single samples with the selector random variable in the MI term conditioned on a single sample. I will comment on the utility of these bounds later.", "theoretical_claims": "The theoretical claims are properly presented, and the proofs are well-readable and correct. I checked the proofs of Lemma 3.1, Theorem 3.2, and Proposition 3.4 in-depth and looked rapidly at other proofs, which mostly utilize a generally similar proof strategy.", "experimental_designs_or_analyses": "Experiments are conducted for MNIST and CIFAR10 which are considered simple datasets by today’s standard. Nonetheless, for the generalization error analysis, it is sufficient. Many GE works are already vacuous or do not apply for ResNet50 on Cifar10. \n\nThe main issue is the low number of training samples used in MNIST and Gaussian experiments.", "relation_to_broader_scientific_literature": "The paper is about the generalization error analysis of learning algorithms. The approach is quite specific and therefore not directly connected to other bounds like PAC Baysian or Rademacher Complexity based bounds, which is fine.", "essential_references_not_discussed": "Xu and Raginsky themselves cite the original work, where the information-theoretic generalization bound is presented: \n\nRusso and J. Zou, How much does your data exploration overfit? Controlling bias via information usage \n\nIt is fair to say that this is the seminal work on the information-theoretic generalization bound, and should be cited.", "other_strengths_and_weaknesses": "**Strengths:**  \n\nThe paper is well written, and the exact tightness is a merit. \n\n**Weakness:**\n\nI would like to clarify a dilemma I have with these information theoretic results. To put it simply, it is not clear what insights these bounds give us about learning. Naively, it seems that these results do not provide any additional insight beyond the fact that the learning algorithm should not memorize the training data, or in this case, it should not memorize the procedure of training data selection.  \n\nBesides, the prediction-based generalization bound already involves losses that directly contribute to the precise generalization error, and I wonder whether we are just verifying an algebraic equality, self-fulfilling-ly.  \n\nThe paper in particular lacks more extensive insights about the results. It presents theorem and plots the numerical results.  \n\nIt is crucial that the authors clarify what these bounds tell us about learning, how they can be employed in practice, and why machine learning community should care about it. Note that the seminal work of Russo and J. Zou had interesting insights.", "other_comments_or_suggestions": "I wonder if the dependence of $W$ on the training data can be made more explicit for better readability.", "questions_for_authors": "As I alluded to in my comment above, I wonder if Lemma 3.1 can be obtained using a data processing inequality for f-divergence, knowing that JS-divergence is one (maybe something can be found here f-Divergence Inequalities by Igal Sason, and Sergio Verdu?). \n\nThe author mentions the convergence rate of $O(1/n)$ “frequently observed in practical learning scenarios”. Could authors provide additional reference for this claim?  \n\nRegarding the bounds in Table 1, including what was presented in the paper: I am not sure if one can read much from the appearance of the term $O(1/n)$ or $O(1/\\sqrt{n})$, because the way the other terms scale with $n$ impacts the final dependence. There are many norm-based bounds for deep nets that scale poorly with $n$ despite the explicit $O(1/\\sqrt{n})$ dependence. It is difficult to guess the trend from the plots. It might be worth to study the dependence via some curve fitting.", "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": "0zLPHcl3Gd", "reviewer": "Reviewer_537o", "summary": "This paper introduces a novel framework for deriving *exactly tight* information-theoretic generalization bounds in machine learning using the binary Jensen-Shannon (JS) divergence. By leveraging a binarization technique for loss variables and supersample frameworks, the authors propose hypothesis-based and prediction-based bounds that address key limitations of prior work, including slow convergence rates and overestimation in deep neural networks. Experiments validate the bounds on synthetic and real-world datasets, demonstrating superiority over baselines like Binary KL divergence and fast-rate bounds.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer 537o, Thank you for your thoughtful comments and questions! We address them below:\n\n---\n\n**Assumption in Corollary 3.12**\n\nWe agree that the assumption in Corollary 3.12 is stronger than Assumption 3.7. This limitation is acknowledged in Section 5, and we leave the task of relaxing this assumption to future work. Importantly, the core contributions of our paper do not depend on this assumption and are already applicable to a wide range of practical learning scenarios.\n\n---\n\n**Experiments on Larger Datasets**\n\nWhile MNIST and CIFAR-10 are relatively simple by today’s standards, they remain common benchmarks in generalization studies (e.g., Harutyunyan et al., 2021; Hellström \\& Durisi, 2022b; Wang \\& Mao, 2024). Our bounds are designed to scale with arbitrary $n$ and sample distributions, so there is no indication they would deteriorate on larger datasets. ```Reviewer o7Wh``` also found the current experiments sufficient, and we believe they effectively demonstrate our contributions.\n\n---\n\n**Relation to PAC-Bayesian Bounds**\n\nWe agree that PAC-Bayesian bounds are closely connected to information theory, especially through KL divergence terms. However, our work focuses on bounding the *expected* generalization error, whereas PAC-Bayesian approaches typically emphasize *high-probability* bounds. Therefore, the two are not directly comparable. This distinction is also acknowledged by ```Reviewer o7Wh```.\n\n---\n\n**On Tighter Bounds**\n\nYes, recent improvements in information-theoretic generalization bounds typically fall into two categories: (1) refining the dependence between mutual information and generalization error—where we propose the binary JS divergence, and (2) improving the information measure itself—where we propose SICIMI for hypothesis-based bounds and bl-MI for prediction-based bounds. These two approaches complement each other to achieve the tightest bounds.\n\n---\n\n**On the Restrictiveness of Assumption 3.7**\n\nAssumption 3.7 effectively assumes non-negative generalization error, which is typically satisfied by well-trained models. In practice, test performance usually lags behind training performance, and this is exactly the reason why we need generalization analysis. Similar assumptions are also adopted in prior works [1], and it has been shown to always hold for certain algorithms such as Gibbs sampling [2].\n\n---\n\n[1] Estimation of generalization error: random and fixed inputs. Statistica Sinica, 2006.\n\n[2] An exact characterization of the generalization error for the Gibbs algorithm. NeurIPS, 2021.", "claims_and_evidence": "The claims are all supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods  make sense for the problem.", "theoretical_claims": "The paper appears to be technically sound, but I have not carefully checked the details.", "experimental_designs_or_analyses": "The experiment evaluated three different classification tasks, generating Gaussian datasets, 4-layer CNN on binarized MNIST and Pretrained ResNet-50 model on CIFAR10. The experiment is generally reasonable, but it lacks experiments with high-dimensional data, such as ImageNet datasets.", "relation_to_broader_scientific_literature": "This paper is focus on the theoretical side  and does not have a significant connection with the broader scientific literature.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "**Strengths**:  \n1.  This paper proposes a new approach to characterizing the relationship between expected empirical and population risks through a binarized variant of the Jensen-Shannon divergence, which achieves faster convergence compared to existing fast-rate and binary KL-based methods. \n2.  Results can be applied to stochastic convex optimization  and extend to f-divergence/Wasserstein metrics .  \n3. Lemma 3.1 may hold significance beyond the context of generalization analysis,\noffering potential applications in broader aspects.\n\n**Weaknesses**:  \n1. Corollary 3.12 requires $\\delta_j L_n \\leq \\delta_j L_{\\mu}$, which seems to be a stronger condition than Assumption 3.7.\n2. Lack of experiments on larger datasets.", "other_comments_or_suggestions": "The related work lacks a discussion and comparison with the literature on PAC-Bayesian generalization bounds, such as\nDupuis, Benjamin, et al. \"Uniform Generalization Bounds on Data-Dependent Hypothesis Sets via PAC-Bayesian Theory on Random Sets.\" Journal of Machine Learning Research 25.409 (2024): 1-55.\n\nhttps://www.jmlr.org/papers/volume25/24-0605/24-0605.pdf", "questions_for_authors": "1. This paper introduce  two reasons for producing tight generalization bounds. One is  eliminating redundant random variables from the key mutual information terms (Line 179). Another is using the binary KL divergence (Line 141). Is it necessary to ignore redundant information in conjunction with binary KL divergence to improve the upper bound?\n2. Your results rely on ​Assumption 3.7 ($L_n \\leq L_{\\mu}$). How restrictive are this assumption in practice?", "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": "bjvjaIP1Q4", "reviewer": "Reviewer_S7W7", "summary": "This paper investigates the question of tightness in mutual information generalisation bounds. Authors propose exactly tight generalisation bounds based on the binary Jensen-Shannon divergence. They show that their results are also tighter than various existing bounds and successfully involve the impact of a statistical property of optimisation algorithms. They then extend the notion of Jensen-Shannon divergence beyond the KL case and propose associated generalisation bounds. The paper concludes with a numerical assessment of the tightness of their bounds.The", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer S7W7, Thanks for your valuable comments! We are addressing your questions as follows:\n\n---\n\n**Redefinition of $L_n$ and $L_\\mu$**\n\nYou are correct that $L_n$ and $L_\\mu$ are defined in both Sections 2.1 and 2.2. These two definitions are actually equivalent but expressed using different notations: one for the standard empirical and population risks, and the other adapted to the supersample setting. We will clarify this equivalence in the revised version.\n\n---\n\n**Training and Testing Separation in $(\\widetilde{Z}_i^0, \\widetilde{Z}_i^1)$**\n\nThe interpretation where $Z_0$ is the training sample and $Z_1$ is the test sample only applies to the illustrative example preceding Section 3.1. In the main analysis, we adopt the supersample setting, where the binary variable $U_i$ determines the training sample $\\widetilde{Z}_i^{U_i}$ and the test sample $\\widetilde{Z}_i^{\\overline{U}_i}$. Hence, $\\widetilde{Z}_i^0$ is equally likely to serve as either a training or test sample.\n\nThe symmetry in the supersample setting implies that the distributions of $(L_i^0, L_i^1)$ are actually identical under these two procedures:\n- **Original supersample formulation:** Assign training and test samples as $\\widetilde{Z}_i^{U_i}$ and $\\widetilde{Z}_i^{\\overline{U}_i}$ respectively, and define $L_i^0 = \\ell(W, \\widetilde{Z}_i^0)$, $L_i^1 = \\ell(W, \\widetilde{Z}_i^1)$.\n- **Illustrative example formulation:** Always fix $\\widetilde{Z}_i^0$ for training and $\\widetilde{Z}_i^1$ for testing, and define $L_i^0 = \\ell(W, \\widetilde{Z}_i^{U_i})$, $L_i^1 = \\ell(W, \\widetilde{Z}_i^{\\overline{U}_i})$.\n\nWe will revise the paper to unify the example and main analysis settings to avoid confusion.\n\nIt is true that our SICIMI term $I(W;U_i|\\widetilde{Z}_i^0)$ conditions on $\\widetilde{Z}_i^0$, whose distribution reflects a mixture of training and test samples. However, our focus remains on inductive learning algorithms, not transductive ones. Unlike transductive methods, which may leverage unlabeled test data during training, inductive algorithms do not access any information about the test set in the learning phase. The test samples are only used in the analysis stage to evaluate generalization bounds. Therefore, the two setups are fundamentally different and not directly comparable.\n\n---\n\n**Convexity of $d_{\\text{JS}}$**\n\nHere is a proof sketch for this result: The joint convexity of $d_{\\text{JS}}$ follows directly from that of the Jensen-Shannon divergence. Specifically, when considering Bernoulli random variables, we have $d_{\\text{JS}}(p\\\\|q) = D_{\\text{JS}}(\\text{Bern}(p) \\\\| \\text{Bern}(q))$ and $\\frac{1}{2} \\text{Bern}(p) + \\frac{1}{2} \\text{Bern}(q) = \\text{Bern}\\left(\\frac{p+q}{2}\\right)$. Moreover, the joint convexity of $f$-divergences follows from the convexity of the mapping $(p, q) \\mapsto q f(p/q)$, which is inherited from the definition of convex $f$-functions.", "claims_and_evidence": "The paper is well-written and pedagogical. The tightness of their results is provably shown, and limitations of the proposed bounds are clearly highlighted.", "methods_and_evaluation_criteria": "The experimental part consists in simple computations of various generalisation bounds for different pairs (loss, learning algorithms). The  benchmark here consist in the binary KL bound which is a natural comparison point.", "theoretical_claims": "As I am not familiar with literature, I cannot assess the veracity of the proofs. However, the proposed contributions look coherent with existing results, and it is clear to understand the reason of why their results are tighter bounds than existing ones through Figure 2.", "experimental_designs_or_analyses": "The experimental part look sound and coherent with theoretical claims, although I did not check the details.", "relation_to_broader_scientific_literature": "I am not familiar enough with this literature to know whether all relevant references have been discussed.", "essential_references_not_discussed": "I am not familiar enough with this literature to know whether any crucial reference is missing.", "other_strengths_and_weaknesses": "See Questions.", "other_comments_or_suggestions": "See Questions.", "questions_for_authors": "- In Secs 2.1 and 2.2 you defined twice $L_n$ and $L_\\mu$, I assume that it is the definitions of Sec. 2.2 that holds in this work.\n- l.134-143 right column: Does this mean that in this work, you always consider $\\tilde{Z}_i^0$ to be your training data and $\\tilde{Z}_i^1$ the test one? \n- More generally, I am not sure to understand the notion of conditioning to $\\tilde{Z}_i^0$ in Table 1 when defining your SICIMI framework. If this means that you always assume $\\tilde{Z}_i^0$ to be your training data, then is it still relevant to invoke a supersample instead of directly mentioning training and test sets? In this case this would be relevant to discuss the difference with transductive learning, and more particularly the transductive PAC-Bayes learning (see e.g. Begin et al. 2014) which also consider directly a train and test set and propose generalisation bounds involving KL divergences (thus mutual information). \n- l.223 right column: would it be possible to briefly describe the proof of convexity of $d_{JS}$?\n\n\n\nReferences: \n\nBegin et al. 2014 PAC-Bayesian Theory for Transductive Learning", "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": "7ycOtruXMg", "reviewer": "Reviewer_PSQE", "summary": "This paper studies the information-theoretic generalization bounds within the conditional mutual information (CMI) framework by introducing a new information measure called binary Jensen-Shannon (JS) divergence. Specifically, the paper begins with a cleverly designed lemma that builds a relationship between binary JS divergence and mutual information. This key result allows the authors to derive novel, tighter CMI bounds in which the CMI term conditions only on a single random variable. The paper further extends these results by presenting evaluated CMI bounds.\nMore importantly, under an invariance assumption, the authors demonstrate that the generalization error can be exactly characterized by their binary JS divergence measure. This argument applies not only to the zero-one loss but also to general bounded loss through a novel loss binarization technique. Furthermore, the paper generalizes its findings by extending mutual information and KL-based results to the broader class of $f$-divergence-based results.\nFinally, the authors also provide empirical study of their theoretical results, showing that their novel binary JS divergence bounds can exactly characterize generalization, making them tighter than all previous CMI bounds.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer PSQE, thank you for your kind words and insightful comments! We address your questions below:\n\n---\n\n**On the Optimal Convex Comparator**\n\nWe appreciate you highlighting this work. As stated in Theorem 4 of that paper, the Cramér function is defined as the convex conjugate of the CGF of a distribution $P_p$ from a set $\\mathcal{P}$, where for any $r$ in the loss space $\\mathbb{L}$, there exists a $P_r \\in \\mathcal{P}$ such that $\\mathbb{E}[P_r] = r$. This means the Cramér function is not fixed but depends on the loss space.\n\nIn their analysis, when $\\mathbb{L} = [0,1]$ (as in our setting), $\\mathcal{P}$ is the set of all Bernoulli distributions (Eq. (19)), making the Cramér function the binary KL divergence (Eq. (29)). In contrast, our work demonstrates that binary JS divergence outperforms binary KL in the supersample setting, suggesting that their optimality result does not directly extend to our framework.\n\nA key reason may lie in the choice of mutual information measure. Their formulation is based on $D_{\\text{KL}}(Q_0 D^n \\\\| Q_n D^n)$, a generalization of $I(W;\\mathbf{Z})$, which reflects the standard hypothesis-based mutual information. In contrast, our analysis focuses on the supersample setting, where the key quantities are $I(W;U|\\widetilde{\\mathbf{Z}})$ or $I(L;U)$. This may explain from another perspective why our binary JS method (and also the previous fast-rate one) does not apply to this original generalization analysis setting but only the supersample one. Extending their analysis to the supersample setting would be a promising future direction, and we will include these discussions in the revised manuscript.\n\n---\n\n**On the Value of Tight CMI Bounds**\n\nThis is indeed a crucial question for the CMI-based generalization literature. We believe our contribution goes beyond providing tighter estimates to the generalization error. In particular, we address an open question raised by [1]: For which learning problems and learning algorithms is the CMI framework expressive enough to accurately estimate the optimal worst-case generalization error? Our results show that the framework can achieve exact tightness in a broad range of scenarios, offering a conclusive resolution to this line of inquiry.\n\nWhile our setting is quite general, the practical significance of these bounds becomes more apparent when applied to specific downstream tasks. Due to space limitations, please refer to our response to ```reviewer o7Wh``` for how our results connect to the analysis of out-of-distribution generalization and noisy iterative learning algorithms.\n\n---\n\n**Other Minor Points**\n\nThank you for pointing these out. We will make these necessary corrections in the revised version.\n\n---\n\n[1] Information complexity of stochastic convex optimization: Applications to generalization, memorization, and tracing. ICML, 2024.", "claims_and_evidence": "All claims are clearly supported.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria make sense to me.", "theoretical_claims": "I checked all the proofs and they seem correct to me.", "experimental_designs_or_analyses": "The experiment settings follow some previous studies and are reasonable to me.", "relation_to_broader_scientific_literature": "This paper is within the literature on learning theory and generalization theory, with a particular focus on the information-theoretic generalization analysis framework. Notably relevant works include Steinke \\& Zakynthinou (2020), Hellström \\& Durisi (2022b), and Wang \\& Mao (2023a).", "essential_references_not_discussed": "The following paper may need discussion in this work:\n\n[R1] Hellström, Fredrik, and Benjamin Guedj. \"Comparing comparators in generalization bounds.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2024.\n\nThe current paper uses binary JS divergence as the comparator between empirical and population loss, whereas [R1] explores a general convex comparator for this purpose and further investigates the optimal convex comparator. Given these conceptual connections, discussing [R1] may provide additional understanding for the choice of binary JS divergence in this work.", "other_strengths_and_weaknesses": "Strengths:\n\n1.This paper makes an important technical contribution to the field. While Hellström \\& Durisi (2022b) shows that the binary KL term $d(L_n||\\frac{L_\\mu+L_n}{2})$ is upper bounded by the CMI term, the authors cleverly identify that this binary KL term is embedded within their proposed binary JS measure. More importantly, they utilize the fact that the mutual information between an arbitrary R.V. $X$ and a Bernoulli R.V. $Y$ is equivalent to the JS divergence between $P\\_{X|Y=0}$ and $P\\_{X|Y=1}$. They further demonstrate that the binary JS divergence between $\\mathbb{E}\\_{X|Y=0}[X]$ and $\\mathbb{E}\\_{X|Y=1}[X]$ is exactly equal to this mutual information when $X$ is also binary. This enables an exact characterization of the generalization error using their binary JS measure, and the technique itself may be of independent interest beyond generalization analysis.\n\n2.  The binarization and truncation techniques introduced in this paper are also novel and contribute valuable methodological advancements to the field.\n\n3. Since the binary JS-based bounds provide an exact characterization of generalization error, they overcome key limitations of previous CMI-based bounds, as pointed out in recent works.\n\nWeaknesses:\n\n1. The exact characterization results (e.g., Theorem 3.9, Corollary 3.10) require the algorithm to be invariant to sample permutations. While this is a notable restriction, it is a much more relaxed assumption compared to the interpolating algorithm assumption used in previous works for obtaining exact characterization results.\n\n2. The assumption in Corollary 3.12 may not be easily satisfied in practice. The authors have already acknowledged this limitation in the paper.", "other_comments_or_suggestions": "1. In the right column, Lines 110–114, the authors state that \"JS divergence serves as a proper metric of distance\". This statement is incorrect because **JS divergence does not satisfy the triangle inequality** and therefore is not a proper metric. Please remove this incorrect statement.\n\n2. Please explicitly include Assumption 3.8 in the statements of Theorem 3.9, Corollary 3.10, and Corollary 3.12, as it is crucial for the exact characterization of generalization error in your framework.\n\n3. In the right column, Line 139,  $L=f(W,Z_u)$ should be $L=\\ell(W,Z_u)$.", "questions_for_authors": "1. In [R1] (see \"Essential References Not Discussed\"), it has been shown that when the convex comparator is the Cramér function, one can obtain the tightest possible bound. How do the findings in your paper relate to their results? Could you provide further discussion on the connection between the Cramér function and your binary JS divergence?\n\n2. I thoroughly enjoyed reading this paper, but I have a question regarding the motivation for obtaining the tightest possible CMI bound for generalization error. Specifically, why is it meaningful to derive a generalization bound that is exactly equal to the generalization error? In the CMI setting, where both a training sample and a ghost sample are available, estimating the generalization error directly is feasible. Given this, why should one use your binary JS bound as a predictor of generalization error? Additionally, what unique insights does your exactly tight bound provide, beyond simply computing the generalization error directly in the CMI framework?", "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: The paper discusses tight information theoretic bounds for the generalization error. The bound is general and can be applied to any machine learning model. This line of work is based on the seminal works of Xu and Raginsky (2017) and follow-up works that use the mutual information between training data and the output of the learning algorithm as a measure of generalization. The research program is motivated by the goal of obtaining a tight computable bound.
Decision: Accept (poster)