Exactly Tight Information-theoretic Generalization Bounds via Binary Jensen-Shannon Divergence

Dear Reviewer PSQE, thank you for your kind words and insightful comments! We address your questions below:

On the Optimal Convex Comparator

We 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.

In 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.

A 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.

On the Value of Tight CMI Bounds

This 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.

While 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.

Other Minor Points

Thank you for pointing these out. We will make these necessary corrections in the revised version.

[1] Information complexity of stochastic convex optimization: Applications to generalization, memorization, and tracing. ICML, 2024.

Dear Reviewer 537o, Thank you for your thoughtful comments and questions! We address them below:

Assumption in Corollary 3.12

We 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.

Experiments on Larger Datasets

While 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.

Relation to PAC-Bayesian Bounds

We 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.

On Tighter Bounds

Yes, 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.

On the Restrictiveness of Assumption 3.7

Assumption 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].

[1] Estimation of generalization error: random and fixed inputs. Statistica Sinica, 2006.

[2] An exact characterization of the generalization error for the Gibbs algorithm. NeurIPS, 2021.

Dear reviewer S7W7, Thanks for your valuable comments! We are addressing your questions as follows:

Redefinition of $L_n$ and $L_\mu$

You 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.

Training and Testing Separation in $(\widetilde{Z}_i^0, \widetilde{Z}_i^1)$

The 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.

The symmetry in the supersample setting implies that the distributions of $(L_i^0, L_i^1)$ are actually identical under these two procedures:

• 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)$.
• 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})$.

We will revise the paper to unify the example and main analysis settings to avoid confusion.

It 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.

Convexity of $d_{\text{JS}}$

Here 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.

Dear reviewer o7Wh, thanks for your thorough reading and constructive questions! We are addressing your questions as follows:

On the Nature and Significance of Information-Theoretic Results

This 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:

1. Understanding the Limits of the Information-Theoretic Approach

Recent efforts to tighten bounds have proceeded along two main directions:

• Improving dependencies between mutual information and generalization error: progressing from square-root bounds → binary KL → fast-rate → and now, our binary JS.
• Refining the mutual information term itself: evolving from MI → CMI → $f$-CMI → e-CMI → ld-MI → and finally, our bl-MI.

These 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.

2. Strengthening Theoretical Guarantees for Downstream Applications

It 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:

• 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.
• 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]).

These applications highlight the practical value of our results, though a detailed exploration lies beyond this paper’s scope.

Alternative Proof for Lemma 3.1

Thank 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.

On the $O(1/n)$ Convergence Rate

(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.

As suggested, we fit the generalization error curves in Figure 3 using $y = ax^b$, and report:

This indicates a convergence rate near $O(1/n)$ for synthetic data and closer to $O(\sqrt{1/n})$ on real datasets.

Other Points

We 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.

[1] Information complexity of stochastic convex optimization: Applications to generalization, memorization, and tracing. ICML, 2024.

[2] On $f$-Divergence Principled Domain Adaptation: An Improved Framework. NeurIPS, 2024.

[3] How Does Distribution Matching Help Domain Generalization: An Information-theoretic Analysis. TIT, 2025.

[4] On the generalization of models trained with SGD: Information-theoretic bounds and implications. ICLR, 2022.

[5] Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms. NeurIPS, 2020.

[6] Analyzing generalization of neural networks through loss path kernels. NeurIPS, 2023.

[7] Train faster, generalize better: Stability of stochastic gradient descent. ICML, 2016.