Class-wise Generalization Error: an Information-Theoretic analysis

Weaknesses: Thank you for raising this point. From a technical perspective, while the proof of Theorem 1 can be seen as an extension of prior works by applying the classic Donsker–Varadhan (DV) variational representation over a conditional distribution, however, we note that in the super-sample setting, the existence of the indicator functions, as mentioned in L243-L248 introduces a noticeable challenge.

To address this issue and derive tight bounds, we first extend prior bounding techniques (Wang & Mao, 2023; Harutyunyan et al., 2021) in Lemma 2. The novel proof requires a combination of DV representation along with Hoeffding’s Lemma to obtain tight bounds using the indicator functions. More importantly, we derive a tighter bound in Theorem 4, eliminating the need for a max operation between two indicator functions. We propose to use the CMI between the label-dependent projection of the loss pair $∆_y L$ (which we propose) and the random selection process to upper bound the class-generalization error.

Q the "truck" example: Yes, it is possible. Note that our bounds show two key dependencies: $1/n^Y$ and the CMI term (e.g., $I\_{Z[2n]} (∆_yL_i ; U_i))$. While increasing the number of samples decreases $1/n^Y$, it does not necessarily decrease the CMI term and can even increase it.
For the "truck" class, the generalization error increases with the number of samples $n^y$ because the growth rate of the CMI term exceeds the rate at which $\frac{1}{n^y}$ decreases. This suggests that the model increasingly memorizes patterns in the additional samples, leading to higher CMI and, consequently, an increase in both the bound and the generalization error. Our bounds effectively capture and explain this class-specific generalization behavior, demonstrating that the CMI term can increase under certain conditions. Now the question ‘why CMI is increasing’ needs a more refined analysis of the algorithm dynamic and our theory suggests that adding class-specific noise could mitigate this issue.

Q Remark 3: Thanks for pointing this out. To our understanding, the proposed bound is indeed discrepancy-independent, in the sense that it doesn’t depend on an intractable measure. Note that the difference between Eq. 12 and Eq 14 is simply the difference between the empirical losses on E_Q and E_P. Hence, the bound derived in Theorem 5 can be converted to bounds for Eq.12 by simply adding (E_Q-E_P) on both sides. Importantly, (EQ−EP) can be directly computed from the training data, eliminating the need for intractable discrepancy measures between the true target and domain distributions, as required in prior bounds. This highlights the key advantage of our bound compared to prior bounds. To make this clear and avoid confusion, as suggested by the reviewer, we have rephrased Remark 3 in the updated manuscript to highlight these points.

Q [1] Chained Generalisation Bounds: Thank you for raising this interesting point. Indeed, the chaining technique can tighten mutual information bounds by shifting the regularity assumption from the loss function to its gradient. However, bounds derived using standard MI/CMI, as used in this paper, offer greater interpretability compared to their chained counterparts.
Furthermore, in this study, we prioritized the empirical validation of our bounds to understand and capture the generalization behavior of neural networks. Standard MI/CMI settings are well-suited for this purpose as they result in computable bounds that align closely with empirical results.
We consider our work to be a foundational step toward a theoretical understanding of class-generalization. Extending these results using the chaining technique constitutes a promising avenue for future research, particularly in deriving tighter and potentially more nuanced class-generalization bounds. We have now added this discussion in the future work section at the end of the paper

Weakness discussion on the topic of imbalanced/balanced datasets: Thank you for your interesting point. In our study, we focused on balanced datasets such as CIFAR-10/CIFAR100, where each class is represented equally, to ensure that the observed class-generalization disparities are not confounded by class imbalance. This allows us to attribute disparities in class-generalization error to intrinsic properties of the learning algorithm and data distribution rather than to skewed class proportions. We have updated the caption of Figure 1 in the revision to emphasize this point.

Weakness discussion in Appendix C.2: In Appendix C.2, we discussed this alternative definition of class-generalization error by tweaking the supersample setting to ensure that each pair of supersample $Z_i^{\pm}$ has the same label y. However, the key issue with such a formulation lies in creating some dependency between the training set $\hat{\mathbf{Z}}_{[n]}^\mathbf{U}$ and the test set $\hat{\mathbf{Z}}\_{[n]}^{-\mathbf{U}}$ Hence, the last equality in the review is not valid in this case, as the test sample $Z_1^{-U1}$ is not independent of W, given that $Z_1^{-U1}$ and the training sample $Z_1^{U1}$ always share the same label. As shown in Eq. 55 in the paper, this setting accounts for class-generalization only in the first term, not the second.

Q $n_y \leq n$?: Thank you for pointing this out. $n_y=n$ corresponds to all training/test data coming from one class. So there is no notion of class-generalization disparity in this case, which is the main scope of this work. However, it is true that our theory holds even for $n_y=n$. Hence, we have changed it to $\leq$ to include the strict equality case.

Q supersample: It is true that in the original paper, they refer to $Z\_{[2n]}$ as a supersample. Here, we adopt a slightly different notation with the supersample being the pair $Z_i^{\pm}$ and hence $Z\_{[2n]}$ is the set of n supersamples. We have clarified this point in the revision.

Q brackets: Thank you for pointing this out. We have revisited the manuscript and fixed the sizes of all brackets to improve readability and make it aesthetically pleasing.

Q Line 1070: Thank you for catching this. We have fixed the typos in the revised manuscript.

Q class-specific gradient noise in Appendix D.7: Thank you for raising this interesting question. Our theory predicts that any approach capable of reducing the MI/CMI between the training samples of class y and the model weights or outputs should improve the class-generalization performance. From this perspective, adding noise specifically to the gradients of samples from class y or introducing noise to all samples (including those from class y) is expected to enhance the generalization for this class.

In this work, we focus on class-specific gradient noise to perturb the gradients for a single class at a time. This allows us to isolate the impact of MI/CMI related to class y, as analyzed in Theorems 2-4, rather than addressing the MI/CMI associated with the standard generalization error, such as in Corollary 2 of Harutyunyan et al. (2021).

Q PAC-Bayesian literature: Thank you for bringing up the PAC-Bayesian literature on generalization bounds for the confusion matrix for our attention. While the work by Morvant et al. focuses on bounding the entries of the confusion matrix to understand multi-class classification with PAC-based bounds, our work takes a different perspective. Specifically, we introduce the concept of class-generalization error, which quantifies the generalization of a specific class. More importantly, our theoretical results are not restricted to the Gibbs algorithm but apply to any learning algorithm. We have added this discussion to the related work section in the revised manuscript.

Lemma 2: Indeed, the random variable V depends only on the random variable $W$ and the constant z_[2n]. To make this clear, we have rephrased the statement of lemma2 in the revision.

Weakness: Thank you for catching this. In the revised manuscript, we have made the notation consistent. We also fixed the sizes of all brackets to improve readability and make it aesthetically pleasing.

Q1 Motivation: While standard generalization error measures the overall generalization performance of a model, it can hide significant disparities in generalization behavior across different classes, as shown in Figures 1 and 2. The main motivation of our work is to address this phenomenon by using information-theoretic tools to study class-generalization. Beyond providing the first theoretical step toward understanding this puzzling phenomenon, we highlight several key motivations:

• Practical Importance: In certain applications, standard generalization may be less relevant when an important class exists (e.g., rare diseases). In such cases, understanding generalization for this specific class is more critical than focusing on overall performance. Our results provide valuable insights into this scenario.
• Technical Contribution: Our bounding technique, which incorporates conditioning, produces tighter standard generalization bounds in the MI setting, as demonstrated in Corollary 1.
• Broader Applicability: We also show that our results can be easily converted to study: i) fairness generalization ii) subtask generalization iii) generalization in terms of recall or specificity which can be crucial in various applications.

Q2 Essentiality: The core conclusion of our results (Theorem 1-4) demonstrates that models generalize differently across classes due to varying degrees of memorization. Specifically, the CMI between class data and model parameters acts as a proxy for class-generalization error: high CMI indicates memorization and poor generalization, while low CMI suggests better generalization.
This finding provides an explanation for the observed generalization disparity, showing that models can memorize certain classes more than others. Our theory further suggests that CMI and KL divergence terms can serve as proxies for class-specific generalization, aiding in predicting which classes will generalize better. As illustrated in the scatter plots in Figure 2, the CMI terms show a strong correlation with actual class-generalization error.
Furthermore, in general generalization bounds are crucial because they provide a theoretical framework to understand generalization. They offer both theoretical guarantees and practical insights essential for developing new algorithms with stronger performance (e.g., our noise addition approach in Appendix D.7).

Q3 3.Proof Details:

• i) Thanks for pointing this out. There is no inversion of the positive and negative signs in Equation 30. This is because we have $\bar{U_i} = - U_i$ at the start of Equation 30, which accounts for the apparent sign inversion.

• ii) The main aim in Theorem 3 (and Theorem 2) is to derive bounds with CMI terms depending explicitly on the model’s outputs $f_W(X_i^{\pm})$ (and model weights W), in direct analogy to the bounds in Harutyunyan et al. (2021) (and Steinke & Zakynthinou (2020)). To derive tight bounds with explicit depends on $f_W(X_i^{\pm})$ or ($W$), it is not possible to avoid the max term $\max (\mathbb{1}\_{y_i^-=y}, \mathbb{1}\_{y_i^+=y})$. In Theorem 5, we wanted to derive a tight bound without this max term and this required introducing a novel random variable $\delta_y L$ which encapsulates $\mathbb{1}\_{y_i^-=y}$ and $\mathbb{1}\_{y_i^+=y}$.

Applying Equation 47 to Theorem 3 in the expression preceding Equation 31, as suggested by the reviewer, would lead to the following bound:

$

| \overline{\mathrm{gen}_y}| \leq \mathbb{E}_{\mathbf{Z}_{[2n]}} \Big[ \frac{1}{n^y_{\mathbf{Z}_{[2n]}}} \sum_{i=1}^n \sqrt{2 I_{\mathbf{Z}_{[2n]}} (f_{W}(X^\pm_i); U_i )} \Big]

$

Note that this bound cannot capture any class-specific dependency and therefore does not provide insights into class-specific generalization behavior. More significantly, the proposed bound is much looser compared to the bound derived in Theorem 3. Our bound, which incorporates the $\max (\mathbb{1}\_{y_i^-=y}, \mathbb{1}\_{y_i^+=y} )$, is always tighter as $\max (\mathbb{1}\_{y_i^-=y}, \mathbb{1}\_{y_i^+=y} ) \leq 1$. Therefore, the inclusion of the max ⁡operator in Theorems 2 and 3 is essential for achieving tight, output-dependent (and weights-dependent) bounds that uncover meaningful class-specific dependencies and insights.

Weakness : Thank you for pointing out the challenges in following the logical flow of our paper. We acknowledge that the current structure might appear tailored to specialists. The presentation order reflects the progression of how these techniques were developed. To address this issue, we have created a new figure (Figure 12 in the revised manuscript) that provides a visual summary of the logical progression and relationships between the main definitions and theorems in Section 2, as well as their connections to the corollaries in Section 4.1.

Q1:

• Similar to (Bu et al., 2020.), we aim to study a generalization quantity, in particular, class-wise generalization. In most theoretic frameworks, generalization errors are defined as the difference between a ‘population’ risk and an ‘empirical’ risk, explaining the similarities between the two settings. However, unlike Bu et al. (2020), Xu and Raginsky (2017), or Zhou et al. (2020), which focus on standard generalization error, our work introduces a distinct concept: class-generalization error. This concept addresses disparities in generalization performance across different classes, an aspect not explored in prior works.
• Furthermore, the main contribution of (Bu et al., 2020) is showing that sample-wise formulations of generalization errors lead to tighter bounds compared to the dataset-based formulation. Building on this insight, we provide a sample-wise Definition in Lemma 1 for class-wise generalization. Note that this change in definitions within the class-wise setting (of "population" and "empirical" risks) introduces a different quantity, necessitating the development of new proof techniques.
• From a technical perspective, while the proof of Theorem 1 (the MI setting) can be seen as an extension of prior works (Bu et al., 2020) by applying the Donsker–Varadhan (DV) variational representation over a conditional distribution, however, in the super-sample setting, the existence of the indicator functions introduces a noticeable technical challenge and requires a new bounding technique, as demonstrated in Lemma 2 and Theorem 4.

Q2: Xu & Raginsky (2017) study the standard generalization error, whereas our work focuses on class-wise generalization. While Theorem 1 in our paper may appear to resemble Theorem 1 in Xu & Raginsky (2017), the quantities being bounded are different and not directly comparable. Furthermore, Corollary 1 in our paper directly compares to Theorem 1 of Xu & Raginsky, 2017, as both bound the standard generalization error. Notably, Theorem 1 of Bu et al. (2020) provides a tighter bound with individual sample mutual information compared to Xu and Raginsky's. As stated under Corollary 1, our bound is even tighter than Bu et al. (2020), and thus also tighter than Xu and Raginsky (2017). This highlights a key contribution of our work: class-wise generalization analysis enables tighter MI-based bounds compared to previous methods.

Q3: There seems to be confusion about the contribution of our work here. First, the supersample technique, introduced by Steinke and Zakynthinou (2020), provides a general framework for studying generalization error and has been shown in recent works (Zhou et al., 2022; Wang & Mao, 2023) to yield tighter, practically computable bounds on generalization errors. To derive practical bounds for class-generalization error, in section 2.2, we extend our class-wise analysis to the supersample setting (CMI framework).
To this end, we introduce Definitions 2 and 3 and study them within this framework, which as explained in L222-L242 is different from generalization errors typically used in prior works and hence requires novel bounding techniques: To derive tight bounds, we first extend prior bounding techniques (Wang & Mao, 2023; Harutyunyan et al., 2021) in Lemma 2. The novel proof requires a combination of DV representation along with Hoeffding’s Lemma to obtain tight bounds using the indicator functions. More importantly, we derive a tighter bound in Theorem 4, eliminating the need for a max operation between two indicator functions. We propose to use the CMI between the label-dependent projection of the loss pair $∆y L$ (which we propose) and the random selection process to upper bound the class-generalization error.

Q4: There seems to be some confusion here. In our framework, the weights W are always learned using the entire training set S, not just the data from a single class y. As mentioned in Definition 1, $P_{W,Sy}$ is induced by the learning algorithm P_{W|S} and data generating distribution of entire dataset P_S by marginalizing $P_{W,S}$ over non $y$ samples. Similarly, P(W|S_y) is obtained in the same way and represents the distribution of the learned weights conditioned on the data from class y, which allows us to measure the class-specific generalization error. In practice, this does not imply that the model is trained solely on class y data, but rather it’s a conditional distribution used to isolate the generalization behavior for that class in the bound.

Q5: Kindly refer to L211-L215 and L222-L232 for detailed explanations of Definitions 2 and 3. In summary, to define a proper sample-based generalization error, Definition 2 normalizes using the expected number of samples n^y=nP (y), making it dependent on P(y), the true distribution of y. In contrast, Definition 3 relies on the empirical count of samples for class y within the supersample $n^y_{z_{[2n]}}$, which removes the explicit dependence on P(y). This approach avoids the need to estimate P(y), making it more practical for empirical analysis when working with real-world data where the true class distribution is often unknown.

Q6: U is a vector of Rademacher random variables that is not directly used in training. Instead, U determines which samples are used for training W and which for testing. If U can be inferred from the weights W (indicating high CMI), it suggests that the model is memorizing the selection of the training data, resulting in a large class-generalization error. Our experiments follow the same setup as in the CMI setting (Steinke & Zakynthinou 2020), and sample U to select training and testing samples. To clarify any misunderstandings regarding the information-theoretic bounding techniques, we kindly refer the reviewer to Steinke and Zakynthinou (2020) for a detailed explanation of how results are interpreted in the CMI framework.

Minor 1: Thank you for catching that. We have fixed this in the revised manuscript.

Minor 2: Thank you for your suggestion. The primary goal of this paper is to investigate the generalization puzzle related to the noticeable disparity in generalization behavior across different classes, even when the overall standard generalization error is negligible. To highlight this, we focus on "solved" problems like CIFAR-10 and CIFAR-100 with pretrained ResNet-50 models, where the standard generalization error is near zero. However, as demonstrated in Figures 1 and 2, significant class-generalization disparity remains, with some classes showing up to 20% error rates despite the overall low generalization error. This highlights that even in cases where the standard error is minimal, the disparity in generalization behavior across classes can still be substantial. It underscores the importance of addressing this class generalization puzzle in deep learning, providing strong motivation for our work to shed light on this often-overlooked issue in standard generalization studies. We will incorporate the reviewer's suggested experiments in the final version to further strengthen the paper.

We thank the reviewer for their time and efforts. We hope that we have provided clarifications to address your reviews to raise your initial score. As the rebuttal phase is ending and we did not receive any feedback yet, kindly let us know if you have any further concerns.