Class-wise Generalization Error: an Information-Theoretic analysis
Authors: Firas Laakom
Moncef Gabbouj
Jürgen Schmidhuber
Yuheng Bu
Venue: Accepted by TMLR ()

Abstract: Existing generalization theories for supervised learning typically take a holistic approach and provide bounds for the expected generalization over the whole data distribution, which implicitly assumes that the model generalizes similarly for all different classes. In practice, however, there are significant variations in generalization performance among different classes, which cannot be captured by the existing generalization bounds. In this work, we tackle this problem by theoretically studying the class-generalization error, which quantifies the generalization performance of the model for each individual class. We derive a novel information-theoretic bound for class-generalization error using the KL divergence, and we further obtain several tighter bounds using recent advances in conditional mutual information
bound, which enables practical evaluation. We empirically validate our proposed bounds in various neural networks and show that they accurately capture the complex class-generalization behavior. Moreover, we demonstrate that the theoretical tools developed in
this work can be applied in several other applications.

Published in Transactions on Machine Learning Research (07 (07/2025)
Class-wise Generalization Error: an Information-Theoretii analysis
Firas Laakom
fhws.laakomm@ooust.eedee
Center of Excellence for Generative A/
KAUST, Saudi Arabia
Moncef Gabbouj
moneef..abbouuSSuur..
Paculty of Information Technology and Communication Sciences Tampere University, Finland
Jürgen Schmidhuber
Center of Excellence for Generative AI, KAUST, Saudi Arabia The Swiss Al Lab, IDSIA, Switzerland
Yuheng Bu
buynheng@ucsb.cco edu
Department of Computer Science Universily of California, Santa Barbara, CA, USA"
Reviewed on OpenReview: https: // openrevie.. net/ foru?? id= asw4 VcDFpi
Abstract
Existing generalization thcories for supervised learning typically take holistic approach and provide bounds for the expected generalization over the whole data distribution, which implicitly assumes that the model generalizes similarly for all different classes. In prac- tice, however, there are significant variations in generalization performance among different classes, which cannot be captured by the existing generalization bounds. In this work, we tackle this problem by theoretically studying the alass-generalization error, which quantifies the generalization performance of the model for cach individual class. We derive a novel informaiionn-thorrdiee bound for class-generalizatiinn lizaationn error using the KL divergence, and further obtain several tighter bounds using recent advances in conditional mutual in- formation bound, which enables practical evaluation. We empirically validate our proposed bounds in various neural networks and show that they accurately capture the complex class- generalization behavior. Moreover, we demonstrate that the theoretical tools developed in this work can be applied several other applications.
1 Introduction
Despite the considerable progress towards theoretical foundation for neural networks (He Tao 2020) comprehensive understanding of the generalization behavior of deep learning is still elusive (Zhang
2016 2021). Over the past decade, several approaches have been proposed to uncover and provide the-
oretical understanding of the different facets of generalization (He & Tao 2020: Kawaguchi et al.) 2017
Hochreiter & Schmidhuber] 1997 Roberts et al. 2022). In particular, multiple tools have boen used to characterize the expected generalization error of neural networks, such as VC dimension (Sontag et al. 1998 Elisseeff 2000 Hardt et al.] 2016b), algorithmic robustness (Xu & Mannor] (0112) Kawaguchi et al. [002)), and information-theorciic measures (Xu Ra-
Harvey et al. 2017), algorithmic stability (Bousquet
ginsky 2017 Steinke & Zakynthinou, 2020 Wang & Mao 2023). However, relying solely on the analysis
*This work conducted while Yuheng Bu was with the Department of Electrical and Computer Engineering the University of Florida, Gainesville, FL,, USA.

---

Published in Transactions on Machine Learning Research (07 (025)
+
"cats" gen error
"airplanes" gen error
"trucks" gen error
standard gen error
Harutyunyan et al. (2021)
0.5
0.20
0.4
0.15
Error
0.3
0.10
0.2
0.05
0.1
1000
3000
5000
10000
500
800
1000
2000
3000
Number of training samples
Number of training samples
(a) CIFARI0
(b) Noisy CIFAR10
Figure 1: (a): The standard generalization error, i.e., test loss minus train loss, and the generalization errors for several classes on CIFARIO as a function of the number of training samples. (b): The standard generalization error, bound proposed by Harutyunyan et al. (2021), and the generalization errors for several classes on noisy CIFAR10. By comparing both datasets, we can see that even minor corruptions in data distribution can lead to significant disparities class-wise generalization behavior. It worth-noting here that CIFAR1O is balanced dataset, and results are averaged over x 20 and 5 15 for CIFAR10 and its noisy variant, respectively. Experimental details are available in Section 4 and Appendix C.2
of the expected generalization over the entire data distribution may not provide a complete picture. One fundamental limitation of the standard expected generalization error is that it does not give any insight into the class-specific generalization behavior, as it implicitly assunes that the model generalizes similarly for all the classes.
Does the model generalize equally for all classes? To answer this question, conduct periment using deep neural networks, namely ResNet50 (He et al. 2016 Srivastava et al.) 2015 the CIFAR10 dataset (Krizhevsky et al.] 2009). We plot the standard generalization error along with the class- generalization errors, L.e, the gap between the test error of the samples from the selected class and the corresponding training error, for three different classes of CIFAR10 in Figure (a). As can be seen, there are significant. variants in generalization performance among different classes. For instance, the model overfits the "cats" class, i.c., large generalization error, and generalizes relatively well for the "trucks" class, with generalization error of the former class consistently four times larger than the latter. This suggests that neural networks do not generalize equally for all classes. Therefore, reasoning only concerning the standard generalization error (red curve), which averages over the classes, cannot capture this class-wise behavior.
Motivated by these observations, we conduct an additional experiment by introducing label noise (5%) the CIFAR10 dataset to study how slight change in data can affect the class- generalization behavior. Results presented in Figure (a). Intriguingly, despite the low noise level, the disparities between the class-wise generalization errors aggravated, with some classes generalizing up to eight times worse than others. Further, as shown in this example, different classes do not even exhibit the same trend when the number of training samples increases. For instance, unlike the other classes, the generalization error of the "trucks" class increases when more training data is available. To further illustrate the issuc of standard generalization analysis, we plot the informaliion-therrdiee generalization bound proposed in Harutyunyan et al. (2021). Although the bound captures the behavior of the standard generalization error well and can be used to explain the behavior of some classes (o.g., "cat"), it becomes invalid upper bound for the "trucks" class]]
When comparing the results on both datasets, it is worth noting that the generalization error of the same class "trucks" behaves significantly differently on the two datasets. This suggests that class-wise generalization highly depends on factors beyond the intrinsic class difficulty itself, including the data distribution, existence
We that the bound by Harutyunyan 2021 is proposed for the standard generalization error instead of the class generalizaaii..oon..... Here, plot only for illustrative purposes.
2

---

Published in Transactions on Machine Learning Research (07/2025)
of label noise, and the number of training samples. Moreover, in alignment with our findings, Balestricro et al. (2022); Kirichenko et al. (2023) showed that standard data augmentation and regularization techniques, e.g., weight decay and dropout (Krizhevsky et al. 2012 Hanson 1990) improve standard average generalization. However, it is surprising to note that these techniques inadvertently increase the disparity of generalization
among different classes.
The main conclusion of all the aforementioned observations is that neural networks do not generalize equally for all classes, and their class-wise generalization depends all ingredients of a supervised learning prob- lem. Furthermore, having more data may also exacerbate overfitting for certain classes. This paper aims to provide some theoretical understanding of this phenomenon using information-theorciie generalization bounds, as such bounds are both data-dependent and algorithmm-dependen (Xu & Raginsky 2017 Neu iet al. 2021p. This makes them an ideal tool to characterize the class maassgeenralliztionn properties of a learn- ing algorithm. From a practical perspective, class-wise analysis becomes particularly relevant in scenarios involving high-stakes decisions tied to specific classes (o.g., medical diagnosis). In such cases, relying on averaged generalization errors can obscure critical performance gaps.
Our main contributions are as follows:
We introduce the concept of "class- geteraggenrrliinaiionn error," " which quantifies the generalization performance of each individual class. We derive a novel information-theoreiic bound for this quantity based on KI. divergence (Theorem 1 Then, using the super-sample technique proposed by [Steinke & Zakynthinou (2020), we derive various tighter bounds based on conditional mutual information that are significantly
easier to estimate and do not require access to the model's parameters (Theorems 3 and 4 A visual
overview is presented in Figure 2
We validate our proposed bounds empirically in different neural networks using CIFAR1O and its noisy variant in Section 4. We show that the proposed bounds can accurately caplure the complex behavior of the class- generazzziiiiiooo error behavior in different contexts.
We show that our novel theoretical tools can be applied to the following cases beyond the class- generalization error: (i) Derive first class-dependent standard generalization crror bounds highlighting how the glass-enneralization affects the standard generalization (Section 5.1] and in some cases tighten- ing the existing standard generalization error bounds using class-dependency. ; (ii) provide first practical tight bounds for the subtask problem, where the test data only encompasses specific subset of the
classes encountered during training (Section 5.2) ; (iii) derive generalization error bounds for learning in the presence of sensitive attributes (Section 5.3)
We use upper-case letters to denote random variables, e.g., Z, and lower-case letters to denote the realization of random variables. Ez-p denotes the expectation of Z over a distribution P. Consider a pair of random variables W and Z = YX with joint distribution Pw.z- Let W be an independent copy of W, and Z = (X,Y) Y) be an independent copy of Z, such that Pw,z (wr, 2) = Pw(w) Pz(2). For Py) denotes the mutual information (MI), and
Notations:
random variables X, Y and Z, I(X; Y) A D(Px,Y IX(X; Y) A D(Px,y|z=e)) | 3 PYIz=z) denotes disintegrated conditional mutual information (CMT), which capture how much information X provides about Y, not just globally, but conditioned on finer- grained instances of Z. Ez Ez[[z(X; Y) I(X; Z is the standard CMI. We will also use the notation X, Y|2 to simplify X, Y = z when it is clear from the context.
2
Related Work
Information-theorrtic gencralization error bounds: Information- bounds have attracted a
lot of attention recently to characterize the generalization of learning algorithms [Solomonol] 1960: Neu
et al. 2021 Waag et al., 2010 Aminian et al. 2021 Schmidluber 1997 Wu et al. 2020; Wang & Mao
2022 Modak et al. 2021 Wang & Mao 2021 Shui et al. 2020 Wang et al. 2023 Alabdulmohsin 2020)
terms of information shared between the training data, and the learned hypothesis, providing insight into how data-dependent and algorithm-dependent interactions govern overfitting.
3

---

Published in Transactions on Machine Learning Research (07/2025)
Class-generalization
Standard generalization
Theorem 1
Ml-setting 3.1
Definition 1
Corollary 1
D(Pwxxly PW8PIIx-
Theorem 2
CMI-setting 3.2
Definition 2
I (W; U;)
Improved by
Theorem 3
Definition 3
Iz (
Corollary 2
Improved by
Theorem 4 Iz pm [ y
L; U,)
Figure 2: Overview of the main Definitions, Theorems, and Corollaries Sections 3 and 5.1 We use dark gray to refer the MI setting and the light gray to refer the supersample setting
in our paper.
In the supervised learning context, several standard generalization error bounds have been proposed based on different information measures, e.g., KL divergence (Zhou al. 2023), Wasserstein distance (Ro- dríguez Gálvez et al. 2021 mutual information between the samples and the weights (Xu & Raginsky 2017 Bu et al. 2020). Recently, it was shown that tighter generalization bounds could be obtained based on the conditional mutual information (CMI) in the super-sample setting (Steinke & Zakyuthinou 2020: Zhou et al. (022). Based on this framework, Harutyunyan et al. (2021) derived f-CMI bounds based on the model output. In Hellström & Durisi 2022). tighter bounds have been obtained based on the CMI of the loss function, which is further lighlened by Wang & Mao (2023) using the AL CMT.
Class-dependent analysis: Incorporating label information in generalization analysis is not entirely new, given previous literature He & Sul (2020); Chen et al. (2020); Deng et al. (2021). For example, in He & Su (2020), the questions "When and how does the update of weights of neural networks using induced gradient at an example impact the prediction of another example?" have been extensively studied and it was observed that the impact is significant the two samples are from the same class. In Balestriero et al. (0022) Kirichenko et al. (2023) Bitterwolf et al. (2022) Lee et al. (2023) it has been showed that while standard data augmentation techniques (Bishop & Nasrabadi] 2006) help improve overall performance, yields lower performance on minority classes. From a theoretical perspective, (Deng et al., 2021) noticed that in uniform stability context, the sensitivity of neural networks is highly dependent the label information and thus proposed the concept of "Locally Elastic Stability" to derive tighter algorithmic stability generalization bounds. In (Tisbby et al. (2000), an information bottleneck principle is proposed, which states that an optimal feature map sinultaneously minimizes its mutual information with the feature distribution and maximizes its mutual information with the label distribution, thus incorporating the class information. Tishby & Zaslavsky (2015): Saxe et al. (2019); Kawaguchi et al. (2023), this principle was used explain the generalization of neural networks. is also worth mentioning the work Morvant et al. (2012), which focuses bounding the entries of the confusion matrix understand multi-class classification with PAC-
4

---

Published in Transactions on Machine Learning Research (07 (075))25)
Bayesian bounds. In contrast, work takes different perspective. Specifically, introduce the concept of Mlass-eneraliiation error, which quantifies the generalization of a specific class and our theoretical results are not restricted to the Gibbs algorithm, like Morvant et al. (2012), and are valid for any learning algorithm.
3
(lass-Generalizatioon Error
3.1 MI-setting
Typically, in supervised learning, the training dataset S = {(X,, YOJ- = {Z, contains ii.d. samples Z; E Z generated from the distribution Pz. Here, we are interested in the performance of model with weights w E W for data coming from a specific class E V. To this end, we define Sy as the subset of S composed of samples only in class y. For any model w E W and fixed training sets s and Sy, the class-wise empirical risk can be defined as follows:
Lg(w, 8y) Tly (c..)))
1
Σ (10,
(1)
where my the size of 8y ( ny S n), and f: Wxxxxx. xxXxx) R a non-negative loss function. In addition, the class-wise population risk that quantifics how well we performs on the conditional data distribution Px|y=y is defined
LP(w,Px/Y=)) = B [X(,, X,
A learning algorithm can be characterized by a randomized mapping from the entire training dataset S to model weights W according to a conditional distribution Pwis- The gap between Lp(w, Px and Le(w, sy) measures how well the trained model W overfits the training data with label y, and the expected glasraeenerllization error is formally defined as follows.
Definition (class-generaliaation error) Given y E E, the class-generuuliaation ervor
gen, (Px,y, Pwis)) EpwlLp(W) Pxx=)l Epw.s, Ia,,,,LEVV B. (W,,
(3)
where Pw and Pw.s, are marginal distributions induced by the learning algorithm Pwis and data generuting distribution Pg.
KL divergence bound For most learning algorithms used in practice, e.g., Stochastic Gradient descent (SGD), the index of training samples will not affect the distribution of the learned model due the random batch selection. Thus, similar to prior works (Bu et al., 2020 Zhou et al., 2022), we assume that the conditional distribution Pwiz, obtained from the entire learning algorithm Pwis, satisfies Pwiz, Pwiz, Vi * j, when each Z; is i.i.d. drawn from Pz. Under this assumption, have the following lemma that simplifies the class-genocte maas-goncralizationn error
Lemma 1. The class- elass-generallzzatin error in definition is given by
gen (Px,y, Pwis) = B W X. v)1
E. [((W, X, y)],
(4)
where Pw. is the conditional distribution of the shared Pw.z given Y =
The proof is available in Appendix A.1 Lemma 1 shows that, similar to the standard generalization error [Xu & Raginsky 2017 Bu et al.) 2020 Zhou et al. 2022), the class-wise generalization error can be ex- pressed as the difference between the loss evaluated under the joint distribution and the product-of-marze -fargiinal distribution. The key difference is that both expectations are taken with respect conditional distributions given Y ==y-
The following Theorem provides upper bound for the guasaaeenerliizttion error in Definition I Theorem 1. For y E Y, assume the loss E( [. X y) is ay sub- Sab-Gaussian under Pw & P Pxwy then the class- generalization error of class y in Definition 1 can be bounded as:
gen (Px.,, Pw]s)) 5 2 203 D(P. @ Px Y=y))
(5)
5

---

Published in Transactions on Machine Learning Research (07 (07/2025)
The full proof is given in Appendix A.2 which utilizes Lemma I and Donsker- Varadhan's variational rep- resentation of the KT, divergence. Theorem | shows that the class-generalivation error can be bounded using class-dependent conditional KL divergence. This sheds some light on the puzzling behavior of daas-generalizztion performance, implying that classes with a lower conditional KL divergence between the conditional joint, distribution and the product of the marginal distributions tend to generalize better. To our best knowledge, the bound in Theorem | the first label-dependent bound that aims to explain the variation of generalization errors among the different classes.
We note that our bound is obtained by considering the class- gengeeeezeaziiiinnn gap of each individual sample with label This approach, as shown in [uu et al. (2020): Zhou et al. (2022); Harutyunyan et al. (2021), yields tighter bounds using the mutual information between an individual sample and the output of the learning algorithm, compared to the conventional bounds relying on the MI of the entire training set and the algorithm's output (Xu Raginsky 2017
3.2 Supersample-setting
One limitation of the proposed bound in Theorem 1 is that it can be vacuous and intractable to estimate in practice, as the bound involves a high dimensional entity the model weights W. To this end, the conditional mutual information (CMI) framework, as pioneered by SSteinke & Zakynthinou (2020), has been shown in recent studies (Zhou al., 2022 Wang & MMoo 2023) to offer tighter bounds on generalization error that are always finite even if the W is high dimensional and continuous.
In this section, we extend our class-wise analysis using the CMT framework. In particular, we assume that there are n super-samples Z/2n] = ....... 2+ E 2 iid generated from Pz. The training data S - ,,,..... = are selected from [[nn), where U (U1,... Un) {-1,1)" is the selection vector composed of n independent Rademacher random variables. Intuitively, U, selects sample z from z to be used in training, and the remaining one Z, Z.U; for the test.
One potential approach define class- gearraennril in the supersample setting is to construct it equivalently to the class generalization error in the MI setting (Definition D
Definition 2. geduss-generruliaaaion error with global + ) For any y E Y, the class-generakiattonn ervor is defined
A gen y
1 12
Ez (2n)
n Σ 1
Eu., Wizpa WiZpal [ (v. u wi ((W, Z " - 1 -y eW. 2.
(6)
where n = nn P is the true probability of class y, and 1 (a=b) is the indicator function, returning when a = b and zero otherwise.
We can show the exact equivalence between Definition D and Definition 2 with details presented in Ap- pendix B.I. Similarly to Definition [ the gaaas-gnneralization error in Delinition measures the expected error gap between the training set and the test set relative to one specific class y.
2
As the giaraaiencaliiotiion error defined in Definition 2 depends explicitly P(y), it has significant practical limitation: Ply) is not typically available in practice. Consequently, any empirical analysis based on this variant necessitates the estimation of P(y), which in turn introduces an additional layer of estimation bias To overcome this issue, we propose another variant of class-goneralization crror within the supersample setting. To this end, given a supersample 2[2n] and for a specific class E V, let no denote half the number of samples with class y within 2/2]]- Using " instead of n², class-generalizzation error becomes:
Definition 3. (super-sample-bass based class deasrieenrttiitiionn error) For any y E Y, the duas-ggnneriiiationn ervor is defined as
2 EU, W Zpni [1
gen 4
EZ
1x (W, U:) (v-' ((W z 10
(7)
(2))
ny 2p
Tnn Steinke & Zakynthinou 2020), the term supersample refers the Zipn)- Here, refers pair z
6

---

Published in Transactions on Machine Learning Research (07/2025)
Compared to Definition Definition does not have a direct connection to Definition I Its main advantage, however, lies in using " which can be computed for every Zini making it more practical for studying
class generalization. Hence, in the rest of this Section and Section | we focus mainly on this definition of
maas-gennraaliztion error. Note that all the bounds derived in this section based on Definition 3
can also be
obtained for Definition 2 in a similar manner and are therefore omitted for simplicity.
Compared to the standard generalization error definition typically used in the super-sample setting Steinke
& Zakyuthinou 2020 Zhou et al. 2022). we highlight two key differences in Definition 2 and 3 (i) Our
class-wise ceneralization error involves indicator functions to consider only samples belonging to a specific
instead of the total number of samples class y; (ii) Our generalization error is normalized by n (or ny 2p2s n.
The indicators are critical in Definition 2 and serving the vital purpose of delimiting errors relative to the class of interest It is worth noting that alternative definitions for class generalization, aside from Definitions 3 and 2 also exist: a notion of class generalization ion error could be defined using a single indicator function by making each pair of super-samples have the same label, i.e., Y = =Y, However, this alternative requires fundamental modification of the supersample setting and lacks direct insights into the interrelation between class generalization and standard generalization errors. In contrast, Definition 2 as illustrated later in Section 5.1 not only provides direct connection to the standard generalization error but also enables to derive the first label-dependent standard generalization bounds. A detailed discussion of the technical concerns for this alternative is provided in Appendix B.2
The loss term involved in Definition 3 i.c., 1l (v:- -yy)" (WW Z, U.) (v
[W, _ has a specific depen-
dency with respect to the indicators. Thus, prior techniques (Wang & Mao
2023 Harutyunyan et al. 2021
designed for any generic loss function yicld loose bounds. We provide a novel CMI-basod bound by exploring
the structure of these indicator functions in the loss function. The main technical result. is presented in
Lemma 2
Lemma 2. Consider the super-sample setting, for a fixed 2|2n], let V E V be random variable depending on the learned weights W. For any function g that can be wrillen as g(V, Ui, 2/20)) 11 [,) (V, U.)
1l Uy> N(V, 22 ), where h E [0,1] is a bounded function, we have
Ev.U. - =m2m) (V U. mpm))] S m (v. = 1 [0, [ 22 UV;
(8)
The presence of the indicator functions introduces a notable technical complexity, as they depend on both U, and Y, The proof is based on Donsker-Varade Varadhan's variational representation of the KL divergence and Hoeffding's Lemna (Hoefiingg 1994h and is provided in Appendix A.3 Notably, Lemma 2 forms the
foundational element for all subsequent bounds in Theorems 2 andd]
Class bound. The following thcorem provides a bound for the super-sample-based class- generalization error using the disintegrated conditional mutual information between W and the selection variable U, conditioned on super-sample Zi2n]-
Theorem 2 (class-CMI). Assume that the loss ((w,z,) v) E [0, 1] is bounded, then the glastiaennttiiiatiin error for class y in Definition 3 can be bounded as
gen y EZiaa
2 max (Y, mn) =2) (W:U.)
ny
The full proof is provided in Appendix A.4 Theorem provides bound of the class- caasaaencrai error with explicit dependency on the weights W, which implies that the class-general generalization error depends on how much information the random selection reveals about the weights when at lcast one of the two samples of 2 corresponds to the class of interest y. Note that the links between everfitting and memorization have been established in Zhang et al. (2016); [rpit et al. (2017); Chatterjee (2018). Here, Theorem 2 highlights the role of model sensitivity to the training data- specificccllll.. a high conditional mutual information between W and U, indicates that changes in the selection of training data lead to significant changes in the learned model, resulting in looser bounds and potentially worse generalization for some classes.
7

---

Published in Transactions on Machine Learning Research (07/2025)
Class-f-CMI bound. While the bound in Theorem is always finite as U, is binary, evaluating pz (W; U:) can be challenging, especially when W is high-dimensional as in deep networks. One way to overcome this issue is by considering the predictions of the model fw (XF) instead of the model weights W, as proposed by HHarutyunyan et. al. (2021) Here, we denote the loss function & based the prediction I fa) as f(w, I, v) E(G.3) y) (f), y). Throughout the rest of the paper, we use these two notations of loss interchangeably when it is clear from the context.
In the following theorem, we bound the class-generalization error based on the disintegrated CMT ween the model prediction fw(x;) and the random selection, i.e., Izzzi (fw(x:+) U.).
Theorem 3. (class-f- CMI) Assume that the loss E(D, v) E [0, 1] is bounded, then the class-generulization error for class y in Definition 3 can be bounded as
gen y
EZizal m Zian)
2 mmxx(1 (V7=))) wy> 1 (r; wy Zzp, (Sw ( U.)
(10)
Moreover, the class-f-MM, bound is always tighter than the class-CMr bound in Theorem
The proof is available in Appendix A.5 The main benefit of the class-f-CMI bound, compared to all previously presented bounds, lies in the evaluation of the CMT term involving low-dimensional random variable fw(x+) and binary random variable U, For example, in the case of binary classification, fw (X;)) will be pair of two binary variables, which enables us to estimate the class-f-CMI bound efficiently and accurately, as will be shown in Section
Remark 1. In contrast to the bound in Theorem g the bound in Theorem 3 does not require access to the model parameters W. It only requires the model output f()), which makes it suitable even for non-porametric approaches or blx evaluation.
Remark 2.
An issue of both bounds in Theorems 2 and is that they depend on informalion quanlilies irrelevant to the class The term max(1 1 (Y, =y} = (v, filters out the CMI terms where neither sample
Z nor Z corresponds to the class However, this term does not require both somples Z to belong to class y. In the case that one sample in the pair ,Z,ZZ;) ) is from class y and the other is from a different class, this term is non-zero and the information from both samples of the pair, i.e., Iz (fw(X;); U:), contributes to the bound. From this perspective, samples from other classes (+ y) con still affect the bounds, potentially leading to less tight bounds for class y-
Class- A, L-CI bound. In the following, we show that it is possible to address the issuc discussed in Remark 2 To this end, we consider a new random variable L,L, based on the indicator function and the
11 (X,) ,,,") As shown in Wang & Mao (003)) Hellström & Durisi (0022), using the difference of the loss functions on Z instead of the model output yields tighter generalization bounds for the standard generalization error. In addition, this AyL, only subsumes terms related to class y, which hurther tightens the bound for class-wise generalization. The following Theorem provides bound based on the CMI using the newly introduced variable.
loss, which is defined as A,L, A 1 ((fww((((()))))
Theorem 4. Cclas-AAyL-Crr CMM) Assume that the loss ((s, v) [0, 1] is bounded, then the glass-generutization
error of class y defined in 3 can be bounded
gen
EZ
Zppl
V 2lzz LAg U.)
(11)
Z 2ml
i=1
Moreover, the A-L-CMI bound is always tighter than the class-f-CMd bound in Theorem
The proof is available in Appendix A.7 Unlike Theorem 3 the bound in Theorem g does not directly rely on the model output f(-). Instead, it only requires the loss values for Z to compute A,L, Intuitively, the difference between two weighted loss values, A,,,, revcals much less information about the seloction process U, compared to the pair fw (XF). In Appendix A.7 we formally show that indeed the L-LICMI bound is always tighter than the CCMS bound. Another key advantage of Theorem is that computing the
8

---

Published in Transactions on Machine Learning Research (07/2025)
0.5
"trucks" gen
"cats" gen error
n-1000
0.6
class-f-CMI bound
0.6
class-f-CMI bound
Class-AL -CMI bound
0.4
n=3000
class-M,,-MM CMI bound
class-At, bound
n=5000
Error
0.4
Error
0.4
0.3
n=10000
0.2
0.2
0.2
0.1
0.0
1000
3000
5000
10000
0.0
1000
3000
5000
10000
8
0.05
0.10
0.15
Number of training samples
Number of training samples
Class-generalization error
(a) Truck (CIFAR10)
(b) Cat (CIFAR10)
(c) Scatter (CIFARI0)
1.2
1.2
0.5
"cats" gen gap
n-500
1.0
1.0
class-f-CMI bound
Class Ad. CMI bound
0.4
n=800
0.8
0.8
class-&l,-CMI bound
n=1000
"trucks" gen gap
0.3
n=2000
class F-CMI bound
0.6
n-3000
class y CMI hound
0.4
0.4
0.2
0.2
0.2
0.1
0.0
500
800
1000
2000
3000
500
800
1000
2000 3000
0..00
Number training samples
Number of training samples
0.15 Class-generallzation error
0,05
0.10
(d) Truck (Noisy CIFARIO)
(e) Cat (Noisy CIFAR10)
(f) Scatter (Noisy CIFARIO)
Figure Experimental results of class- class-generalin generalization error and our bounds in Theorems and for CI- FAR10 and noisy CIFAR1O, as we increase the number of training samples The right column shows the relationship between the bound in Theorem 4 and the true class-generalization error for all classes in each
dataset.
CMI term Iz (A,, Le; U,) is even simpler, given that A, is a one-dimensional scalar, as opposed to the two-dimensional fw (x:).
Interestingly, it should also be noted that a similar class A,, L-CMI bound can be derived based on the alternative Definition 2 using Theorem 3.1 in Wang & Mao (202)): As their result is valid for any loss, consider in particular the loss lgf. However, note that such proof technique can not be used to derive the Theorem for Definition due to the presence of p2
In corroboration with the results in Figure ! Theorems and 4 show that having more samples from class y (larger nyy) cannot guarantee strong class moaasseennalliztiin, as ny is not the sole factor. Indood, our bounds highlight fundamental dependency of the class-generllization error with the CMT between the model and the class data. Moreover, this shows that having more balanced dataset (equal ny) does not guarantee equal class-general seaasseeneralizttion error, as it does not guarantee equal relative CMI, which can explain the observed disparity of overfitting as shown in Figure and Balestriero et al. (002)) Kirichenko et al. 2023)).
4 Empirical Evaluations
In this section, we empirically evaluate the effectiveness of our class-wise generalization error bounds. As mentioned earlier, The bounds in Section 3.2 are significantly easy to estimate in practical scenarios. Here, we evaluate the error bounds in Thcorems 3 and 4 for deep neural networks. We follow the same experimental settings in Harutyunyan et al. (2021). i.e., we fine-tune a ResNet-50 (He el 2016)) on the CIFAR10 dataset (Krizhevsky et al. 2009) (pretrained (Schmidhuber 1992) on ImageNet (Deng et al., 2009)). Moreover, to understand how well our bounds perform in more challenging situation and further highlight their effectiveness, we conduct an additional experiment with a noisy variant (5% label noise) of CIFAR10. The details are provided in Appendix C.1
9

---

Published in Transactions on Machine Learning Research (07/2025)
The class-wise generalization error of two classes from CIFAR10 "trucks" and "cats", along with the bounds in Theorems 3 and are presented in the first two columns of Figure 3 The results on all the ten classes for both datasets, along with additional experiments, are presented in Appendix C.3 Figure 3 shows that both bounds can capture the behavior of the class-generalization error. As expected, the Mlass-A,L-CM. is consistently Lighter and more stable compared to the class-f-CMI bound for all the different scenarios. For CIFARI0 in Figure 3 (top), as we increase the number of training samples, the "trucks" class has a relatively constant class-geneallization error, while the "cats" class has large slope at the start and then steady incremental decrease. For both classes, the class- AyL-MII precisely captures the behavior of class-genraliizttinn error.
The results on noisy CIFARIO in Figure 3 (bottom) and the results in Appendix these observations. Notably, the "trucks" generalization error decreases for CIFAR10 and increases for noisy CIFAR10 with respect to the number of samples. Moreover, the class-generalization error of "cat" is worse than "trucks" in CIFAR10, but the opposite true for the noisy CIFAR1O. Our Class-A,I-CMI bound successfully captures all these complex behaviors.
C.3 are consistent with
The left and middle plots in Figure show that the class A,L-CMI bound scales proportionally with the ac- tual glasraennerllizttion error, i.c., higher Llass-A,L-CMI bound value indicate higher class- gaassgeeneralization error. To further highlight. this dependency, Figure 3 (right) presents the scatter plot between the differ- ent class-genen geaaaazeenlli errors and their corresponding class-A, bound values for all classes in CIFAR1O (top) and Noisy CIFARIO (bottom) under different number of samples. Our bound is linearly correlated with the true error and can efficiently predict its behavior. A similar pattern is observed for the f-CMI bound, as detailed in Appendix C.3 Further validation on the more complex CIFAR100 dataset, provided in Appendix C.4 confirms the bounds' capacity to effectively capture class-specific generalization patterns.
in traditional ML approaches: Although the primary focus of this paper is class- generalization in neural networks, it is worth noting that our theoretical results are valid for any random learning algorithm, including classic approaches such as SVM and decision trees. The empirical results of these two models with MNIST are available in Appendix C.5 The empirical results further corroborate our findings and show that our bounds are generic and effectively capture the glassgeenerllization behavior of traditional ML algorithms. These results highlight that class-wise disparitics exist even in low-capacity models, and our bounds can meaningfully quantify them.
Class-generalizer
Recall and Specificity: Standard generalization bounds (Xu & Raginsky 2017 Harutyunyan et al. 2021 focus on classification error or accuracy, but these metrics are often inadequate for imbalanced datascts. detecting rare cancers, for example, recall and specificity are more relevant performance measures. However, existing bounds (Wu et al. 2020: Wang & Mao 2023) offer no thcoretical insights into these metrics. This paper addresses this gap by providing a framework analyze generalization in terms of recall and specificity. In the special case of binary classification with 0-1 loss, the dlass-generalizatioon errors studied here correspond to recall and specificity, as detailed in Appendix C.6 Empirical results on MNIST, presented in Figure 4 validate the tightness of our bounds and their utility in providing generalization certificates for recall and specificity, essential in sensitive applications. This connection enables principled evaluation of critical metrics in domains where traditional
cauuracy-based bounds are insufficient.
To sum up, (i) one can use our bound to predict which classes will generalize better than others or which classes can benifit. from having more data; (ii) in corroboration with theoretical results in Section 3 the MI/CMI between the model and the class data can be used proxy for class-generallzation error. Such
result provides new perspective on improving class- glass-gencralization by reducing MI/CMI The initial empirical results in Appendix C.8 show that this is promising research direction to mitigate the class- generalization disparity.
5 Other Applications
Besides enabling us to study class-wise generalization errors, the tools developed in this work can also be used to provide thcoretical insights into several other applications. In this section, we explore several use cases with detailed proofs provided in Appendix D
10

---

Published in Transactions on Machine Learning Research (07 2022)
0.00
recall AL-CMI bound
specificity gen gep
0.07
0.07
T-CMI bound
0.06
0.06
0.05
0.05
Entrr
0.04
0.04
1000
2000
3000
1000
4000
(a) Recall Generalization error
(b) Specificity Generalization error
Figure 4: Recall generalization error (left) and specificity generalization error (right) for the binary classifi- cation vs 9 from MNIST. The digit. 4 is considered the positive class.
5.1 From Class-generalization to Standard Generalization Error
Here, we study the connection between the standard generalization and the class- ceaasaenneaaiiitionnn errors. We extend the bounds presented in Section 3 into class-dependent expected generalization error bounds. First, notice that taking the expectation over Py for the class- muss-gencralizztion error in Definition | yields the standard expected generalization error. Thus, can obtain class-dependent bound for the slandard generalization error by taking the expectation of y ~ Py in Theorem !
Corollary 1. Assume that for every E V, the loss ((W, X, v) is By sub- Guob-Gassian under Pw 8 Px|Y=v' then
|P gen < Ex 20 & ( Px|x=r)
(12)
We note that if the sub-Ganssian paramcter dg = a is independent of y, we can further show that the bound in is lighter than the individual sample bound in Bu el al. (2020p. The proof is provided in Appeudix D. This shows that the technique proposed this paper, i.e., deriving bounds by conditioning on the class then converting the bound to standard generalization, can indeed tighten existing information-theoree in the MI setting. For the supersamples setting,
bounds use the class- gaas-generalizztion error as Defined in 2 i.e., gen for this variant, we have gen Ey [gen,) and hence can derive the following bound:
Corollary 2. Assume that the loss E(g. v) [0, 1], then
Ey E
21Z (AYLi U.)
To the best of our knowledge, Corollaries 1 and are the first generalization bounds to provide explicit
label-dependency. Although prior bounds (Harutyunyan et al. 2021 Wang & Mao 2022 2023) might be tighter or more efficient to estimate, they do not provide any information on how different classes affect the standard generalization error. The results presented here address this gap and provide explicit label- dependent bounds. In m-way classification tasks, the bounds become sum of cach glass-gencralizattoon error weighted by the probability of the class, ie.,, P(Y y), suggesting that classes with a higher occurrence probability affect the generalization error more. From this perspective, our results can also provide insights into developing algorithms with better generalization by focusing on the dass-gennealizzation error. For example, one can employ data augmentation targeted at the classes with higher class generalization error attenuate their respective error and thus improve the standard generalization of the model.
11

---

Published in Transactions on Machine Learning Research (07/ 2205)
5.2 Sub-task Problem
Sublask problem refers to a specific case of distribution shift. in supervised learning, where the training data generated from the source domain Px,Y Y consists of multiple classes, while the test data for the target domain Qx.Y only encompasses a specific known subset of the classes encountered during training. This problem is motivated by the situation where a large model has been trained on mumerous classes, potentially over thousands, but is being utilized a target environment where only a few classes, observed during training, exist. By tackling the problem as a standard domain adaptation task, the generalization error of the subtask problem can be bounded as follows:
E. A Erwss (LQ (W) (WW < V
+ (2:
(13)
where (w(w)= = (w, yx,x) denotes the population risk of w under distribution Qx We note that (Wu
et al. 2020) further tightens the result equation 13 but these bounds are all based on the KT. divergence
xx.x) Px.y) for any generic distribution shift problem and do not leverage the fact that the target task is encapsulated in the source task.
D(Qx,y
Obtaining tighter generalization error bounds for the subtask problem is straightforward using our class-wise generalization tools. In fact, the generalization error of the subtask can be bounded by summing the class- wise generalization over the space of the subtask classes A. Formally, by taking the expectation of ~ QY we obtain the following notion of the subtask generalization error:
genq,Eq Eq
A Egr [gōny] E. [LQ(w) LE (W, S)].
(14)
where LEq (w, S) - 1 EmEEA (Ww Ti vi) is the empirical risk relative to the targel domain Q, and nA is the number of samples in S such that their labels yi E A. We are interested in deriving generalization bounds for Eo as it only differs from genq.EE by the difference in the empirical risk LEg (W, ( S) - LE (WS)), S), which can be computed easily in practice.
aa
can use the results from Section 3 obtain tighter bounds. For example, using Theorem 4 we can obtain the subtask generalization error bound in Theorem 5
As shown in Appendix D.2.
Assume that the loss E(w, x, v) E [0, 1] is bounded, Then the subtask generalization ertor defived in equation 14 can be bounded us
Theorem 5. (subtask-AyL-
gen geo Ex-ox EZpz
22 L U.)
(15)
n
Y
Similarly, we can extend Theorems 2 or 3 to construct subtask generalization error bounds using the model's weights or output instead of L, In Appendix D.2.I we empirically validate our subtask bounds and show its ability to capture the generalization behavior practical subtask scenarios.
Remark 3. Existing distribution shift bounds, e.g., the bound in Eg. 13, typically depend on some measure that quantifies the discrepancy between the true target and true domain distributions, e.g., KL divergence. Note that the difference between Eq. 13 and Eq. 14 is simply the difference between the empirical losses on Eq and Ep. Hence, the bound dericed in Theorem 3 can be converted to bounds for Eq. 13 by simply adding (Eq - E on both sides, which can be directly computed from the training data, eliminating the need for intractable discrepancy measures.
5.3 Generalization Certificates with Sensitive Attributes
One main concern hindering the use of machine learning models in high-stakes applications is the potential biases on sensitive altributes such as gender and skin color (Mehrabi et al., 2021 Barocas el al. 2017). Thus, is critical not only to reduce the sensitivity to such attributes but also to be able to provide guarantces on the fairness of the models (Holstein et al., 2019 Rajkomar et al., 2018). One aspect of fairness is that the machine learning model should generalize equally well for each group with different sensitive attributes (Barocas et al. 2017 Williamson & Menon 2019)
12

---

Published in Transactions on Machine Learning Research (07 (025)
AL-CMI bound "Male" gen error
AL-CMI bound
0.20
0.20
"Female" gen error
0.15
0.15
Erro
0.10
0.10
0.05
0.05
0.00
0.00
250
500
1000
1500
2000
250
500
1000
1500
2000
Number of training samples
Number of training samples
(a) COMPAS: Male
(b) COMPAS: Female
Figure Empiriaal evaluation of our bounds for generalization with sensitive altributes using using the COMPAS dataset.
By tweaking the definition of our dlass-genraalizttion error, show that the theoretical tools developed in this paper can be used to obtain bounds for curriute-generraizatti errors. Suppose that we have random variable T E T representing a sensitive feature. One might be interested in studying the generalization of the model for the sub-population with the attribute T T= l. Inspired by our class-eeneraliaation, we define the attribute-gee cerrruute-gnneraizattin error as follows:
Definition 4. (attribule-generrlizattae error) Given T, the atträbude-genemmliaation error is defined
follows:
gen = - ((W [)].
(16)
By exchanging X and Y with and T in Theorem respectively, we can show the following bound for the cerribtto-gnneaalizttin error.
Theorem 6. Given t T, assume that the loss 8(W, Z) is sub-Gaussian under Pw Pz. then the attribute- perributegennemlization error of the sub-population T = t, can be bounded as follows:
gen,l < 2202 (og2D(Pwp) @ Pw @ P2i))
We note exlending results to the super-sample settings is also straightforward.
Prior works on fairness in machine learning [Barccas et al, 2019 Han et al. 2024 Giguere et al. 2022
primarily focus on between-group comparisons-ovallatiing whether a model's performance consistent across sensitive subpopulations (e.g., male vs. female) and measuring disparities using subpopulation-leve metrics such as Equalized Odds (Hardt et al. 2016a or Demographic Parity (Barocas al. 2019 In contrast, our theoretical result in Theorem provides a within--ubpppulation perspective: it characterizes the generalization behavior of the model on fixed sensitive group (e.g., conditioned on "male") across the train-test split. This shift in perspective enables a complementary form of fairness analysis. Empirical evaluation of our bound in this case, on COMPAS [Larson et al., 2016) datasct are available in Figure Additionally, in Figure 13 of appendix C.7 we provide extra results using Adult (Kohavi & Becker 1996) dataset. As can be seen, our framework yields bounds that consistently capture sub-population based. gencralization crrors, further highlighting its versatility.
Furthermore, using the altribute generalization, can show that the standard generalization error can be bounded follows:
Corollary 3. Assume that the loss E(W, Z) is a uub-Gaussian under Pxp & Pz. then
ET 20 D(w @ P Pw X PZTT-T)
The result of Corollary 3 shows that the average generalization error is upper-bounded by the expectation over the attribute-wist generalization. This shows that it is possible to improve the overall generalization by reducing the generalization of each population relative to the sensitive attribute.
13

---

Published in Transactions on Machine Learning Research (07 (07/2025)
6 Conclusion & Future Work
This paper studied the puzzle of noticeable disparity of generalization behavior among different classes by introducing and exploring the concept of "class-generalliation error". To our knowledge, we provided the first rigorous generalization bounds for this concept using either MI or CMI. We also empirically strengthened the findings with supporting experiments validating the efficiency of the proposed bounds. Furthermore, we demonstrated the versatility of our theoretical tools in providing tight bounds for various contexts.
Overall, goal is to understand generalization in deep learning through the lens of information theory, which motivates future work on preventing high class-generaiization error variability and ensuring 'equal' generalization among the different classes. Other possible future research endeavors focus on obtaining tighter bounds for the class-generalization error, e-g., using the chaining technique (Clerico et al. 2022) and studying this concept in different contexts beyond supervised learning, e.g., self-supervised learning.
Acknowledgment
The research reported this publication was supported by funding from King Abdullah University of Science and Technology (KAUST) Center of Excellence for Generative AI, under award number 5940. This research also supported by Business Finland (BF)-AMALIA and NFS IUCRC CBL. Yuheng Bu was supported by the Department of Electrical and Computer Enginecring at the University of Florida.
References
Tbrahim Alabdulmohsin. Towards unified theory of learning and information. Entropy, 22(4):438, 2020.
Gholamali Aminian, Yuheng Bu, Laura Toni, Miguel Rodrigues, and Gregory Wornell. An exact charac- terization of the generalization error for the gibbs algorithm. Advances in Newral Information Processing Systems, 34:8106-8118, 2021.
Devansh Arpit, Stanistaw Jastrzkebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S Kan- wal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, et al. A closer look at memorization in deep networks. In International conference on machine learning, pp. 233 242. PMLR, 2017.
Randall Balestricro, Leon Bottou, and Yann LeCun. The effects of regularization and data augmentation are class dependent. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 37878 37781- Curran Associates, Inc., 2022.
Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness in machine learning. Nips tutorial, 1:2017, 2017.
Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and machine learning. fairmlbook. org, 2019.
Christopher M Bishop and Nasser M Nasrabadi. Pattern recognition and machine learning, volume 4. Springer, 2006.
Julian Bitterwolf, Alexander Meinke, Valentyn Boreiko, and Matthias Hein. Classifiers should do well even on their worst classes. In ICML 2022 Shift Happens Workshop, 2022.
Olivier Bousquet and André Elissceff. Algorithmic stability and generalization performance. Advances in Newral Information Processing Systems, 13, 2000.
Yuheng Bu, Shaofeng Zou, and Venugopal V Veeravalli. Tightening mutual information-based bounds on generalization error. IEEE Journal Selected Areas in Information Theory, 1(1):121-13) 2020.
Satrajit Chatterjee. Learning and memorization. In International conference on machine learning, pp. 755-763. PMLR, 2018.
Shuxiao Chen, Hangfeng He, and Weijie Su. Label-aware neural tangent kernel: Toward better generalization and local elasticity. Advances in Neural Information Processing Systems, 13:15547-15588 2020.
14

---

Published in Transactions on Machine Learning Research (07/2025)
Eugenio Clerico, Amitis Shidani, George Deligiannidis, and Arnaud Doucet. Chained generalisation bounds. In Conference on Learning Theory, pp. 4212-422222 -2257. PMLRR 2022.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference computer vision and pattern recognition, pp. 248-255, leee, 2009.
Zhun Deng, Hangfeng He, and Weijie Su. Toward better generalization bounds with locally elastic stability, In International Conference on Machine Learning, pp. 2590-2600. PMLR, 2021.
Stephen Giguere, Blossom Metevier, Yuriy Brun, Bruno Castro Da Silva, Philip Thomas, and Scott Niekum. Fairness guarantees under demographic shift. In Proceedings of the 10th International Conference on Learning Representations (ICLR), 2022.
Xiaotian Han, Jianseng Chi, Yu Chen, Qifan Wang, Han Zhao, Na Zou, and Xia Hu. Ffb: A fair fairness benchmark for in- in-processing group fairness methods. In International Conference on Learning Represen- tations, 2024.
Stephen José Hanson. stochastic version of the delta rule. Physica D: Nonlinear Phenomena, 42(1-3): 265 272, 1990.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29, 2016a.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference on machine learning, pp. 1225-1234. PMLR, 2016b.
Hrayr Harutyunyan, Maxim Raginsky, Greg Ver Steeg, and Aram Galstyan. Information- gener- alization bounds for black-box lcarning algorithms. Advances in Neural Information Processing Systems, 34:24670 24682, 2021.
Nick Harvey Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve-dimension bounds for piecewise linear neural networks. In Conference on learning theory, pp. 1064-1068. PMLR, 2017.
Fengxiang He and Dacheng Tao. Recent advances in deep learning theory. arXie preprint arXh::2012.10911 2020.
Hangfeng He and Weijie Su. The local elasticity of neural networks. In International Conference on
Learning Representations, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Fredrik Hellström and Giuseppe Durisi. A new family of generalization bounds using samplewise evaluated cmi. Advances in Neural Information Processing Systems, 35:10108 10121,, 2022.
Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Neural computation, 9(1):1 12111-42--10 1997.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. The collected works of Wassily Hoeffding, pp. 409-426, 1994.
Kenneth Holstein, Jennifer Wortman Vaughan, Hal Daumé III, Miro Dudik, and Hanna Wallach. Improving fairness in machine learning systems: What do industry practitioners need? In Proccedings of the 2019 CHll conference on human factors in computing systems, pp. 1 16, 2019.
Kenji Kawaguchi, Leslie Pack Kaelbling, and Yoshua Bengio. Generalization in deep learning. orXiv preprint wwXiv:1710.05403. 1(8), 2017.
Kenji Kawaguchi, Zhun Deng, Kyle Luh, and Jiaoyang Huang. Robustness implics gencralization data- dependent generalization bounds. In International Conference on Machine Learning, pp. 10866-10894. PMLRR, 2022.
15

---

Published in Transactions on Machine Learning Research (07/2025)
Kenji Kawaguchi, Zhun Deng, Xu Ji, and Jiaoyang Huang. How does information bottleneck help deep learning? arXie preprint arXin:2305.1888 18887, 2023.
Polina Kirichenko, Randall Balestriero, Mark Tbrahim, Shanmukha Ramakrishna Vedantam, Hamed Firooz, and Andrew Gordon Wilson, Understanding the class-specific effects of data augmentations. In ICLR 2023 Workshop on Pitfalls of limited data and compulation for Trustworthy ML, 2023.
Ronny Kohavi and Barry Becker. Adult data set. UCI machine learning repository, 5:2093, 1996.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Alex Krizhevsky, Πlya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. Advances in newral information processing systems, 25, 2012.
Jeff Larson, Surya Mattu, Lauren Kirchner, and Julia Angwin. Propublica compas analysis data and analysis for 'machine bias.. hllps://gilleub. com/propublica/ hatp:p/aiiia//mmppsssaaaaatttite 2016.
Haeil Lee, Hansang Lee, and Junmo Kim. Dropmix: Reducing class dependency in mixed sample data augmentation. arXiv preprint ar Xix:2907.09136 2023.
Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey on bias and fairness in machine learning. ACM computing surveys (CSUR), 54(6))1135, 2021.
Eeshan Modak, Himanshu Asnani, and Vinod M Prabhakaran. Rényi divergence based bounds on general- ization error. In 2021 IEEE Information Theory Workshop (ITW), pp. 1-6. IEEE, 2021.
Emilic Morvant, Sokol Koço, and Liva Ralaivola. Pac-bayesian generalization bound on confusion matrix for multi-class classification. arXiv preprint arXiv:1202. 6228, 2012.
Gergely Neu, Gintare Karolina Dziugaite, Mahdi Haghifam, and Daniel M Roy. iformattinn-thereedee gen- eralization bounds for stochastic gradient descent. In Conference on Learning Theory, pp. 3526 -545. PMLR, 2021.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring generalization in deep learning. Advances in neural information processing systems, 30, 2017.
Alvin Rajkomar, Michacla Hardt, Michael D Howell, Greg Corrado, and Marshall H Chin. Ensuring fairness in machine learning to advance health equity. Arnals of internal medicine, 169(12):866 071-866667,,7 2018.
Daniel A. Roberts, Sho Yaida, and Boris Hanin. Frontmatter, pp. i-iv. Cambridge University Press, 2022.
Borja Rodriguez Gálvez, Germán Bassi, Ragnar Thobaben, and Mikael Skoglund. Tighter expected gener- alization error bounds via wasserstein distance. Advances in Neural Information Processing Systems, 34:
19109-19121, 2021.
Andrew M Saxc, Yamini Bansal, Joel Dapello, Madhu Advani, Artemy Kolchinsky, Brendan Traccy, and David D Cox. On the information bottleneck theory of deep learning. Journal of Statistical Mechanics: Theory and Esperiment, 20) 2019.
Jürgen Schmidhuber. Learning complex, extended sequences using the principle of history compression. Newral Computation, 4(2):234-242, 1992.
Jürgen Schmidhuber. Discovering neural nets with low kolmogorov complexity and high generalization capability. Neural Networks, 10(5):857 873, 1997.
Changjian Shui, Qi Chen, Jun Wen, Fan Zhou, Christian Gagné, and Boyu Wang. Beyond h-divergence: Domain adaptation theory with jensen-shannon divergence. Xi preprint 200 15567, 6, 2020.
Ray Solomonoff. A preliminary report on general theory of inductive inference. Zator Company Cam- bridge, MA, 1960.
16

---

Published in Transactions on Machine Learning Research (07/2025)
Eduardo D Sontag et al. Ve dimension of neural networks. NATO ASI Series F Computer and Systems Sciences, 168:69-96 1998.
Rupesh Kumar Srivastava, Klaus Greff, and Jürgen Schmidhuber. Highway networks.
orXiv preprint
arXi::1505000887, 2015.
Thomas Steinke and Lydia Zakynthinou. Reasoning about generalization via conditional mutual information. In Conference on Learning Theory, pp. 3437 3452. PMLR, 2020.
Naftali Tishby and Noga Zaslavsky. Deep learning and the information bottleneck principle. In 2015 ieee information theory workshop (itw), pp. 1 5. IEEE, 2015.
Naftali Tishby, Fernando C Pereira, and William Bialek. The information bottleneck method. orXiv preprint Chegiics/0004000 2000.
Hao Wang, Rui Gao, and Flavio P Calmon. Generalization bounds for noisy iterative algorithms using properties of additive noise channels. J. Mach. Learn. Res., 24:26-1, 2023.
Wei Wang, Martin J Wainwright, and Kannan Ramchandran. cnermattionthhoreete bounds on model selec- tion for gaussian markov random fields. In 2010 TEEF International Symposium on Information Theory, pp. 1373 1377. IEEE, 2010.
Ziqiao Wang and Yongyi Mao. On the generalization of models trained with sgd: Information-theoredl bounds and implications. arXiv preprint 1rXix:2110.01120 2021.
Ziqiao Wang and Yongyi Mao. Information-theoreer analysis of unsupervised domain adaptation. arXiv preprint arXiv:2210.000 007006, 2022.
Ziqiao Wang and Yongyi Mao. Tighter information-theorctia generalization bounds from supersamples. arXiv preprinl ar (rxi:22302.000 02432, 2023.
Robert Williamson and Aditya Menon. Fairness risk mcasures. In International conference on machine learning, pp. 6786-6799 PMLR, 2019.
Xuetong Wu, Jonathan H Manton, Uwe Aickelin, and Jingge Zhu. Information-theorrliee analysis for transfer learning. In 2020 IEEE International Symposium Information Theory (ISIT), pp. IEEE, 2020.
Aolin Xu and Maxim Raginsky. Information--hcooriicc analysis generalization capability of learning algo- rithms. Advances in Neural Information Processing Systems, 30, 2017.
Huan Xu and Shic Mannor. Robustness and generalization. Machine learning, 86:391-423, 2012.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep
learning requires rethinking generalization. In International Conference on Learning Represenlations, 2016.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
Ruida Zhou, Chao Tian, and Tie Liu. Individually conditional individual mutual information bound on generalization error. JEFE Transactions on Information. Theory, 68(5):3304-33 33166 2022.
Ruida Zhou, Chao Tian, and Tie Liu. Exactly tight information-theoredia generalization error bound for the quadratic gaussian problem. Xivee preprint orXiv:2305. 00876, 2023.
17

---

Published in Transactions on Machine Learning Research (07 (07/2025)
A Proofs of the Theorems in Section 3
This scction inchudes all the proofs of the results presented in the main text in Section 3 We start by the formal definition of sub-Gaussian random variable and the Hoeldding's lemma (Hoeflding 1994).
Definition 5. A random variable X is called sub- Gaussian if there erists posilive constamt such that
[22/2
E eep (1(X B[XIM S exp
2 for all t E R.
(17)
Lemma 3. Let X be a bounded random variable, i.e,, X [a, b] almost surely. If [||] = 0, then X is (b Gaussian and we have:
13
E AX
V.ER.
(18)
A.1 Proof Lemma 1
With the Assumption that Pw.z. Pw.z, Vi + J, follows directly that all the terms the sum in Definition
] become identical and we obtain Lemma i.e., the individual-samplee based expression of the class-wise wise generalization.
Lemma restate) The class-generalizatioon error in definition is given by
gen gen, (Pxyy, Pwis) Br X [[( X. y)] E x/s [((W, X. y)).
(19)
where Xly the conditional distribution of the shared Pw,z given = y.
Proof. Starting from Definition 1 the class-generalization error of class y can be rewritten as
gen (e Y, Pwis) Epw (p (W, Px]Y= E Eww.s LL W. Sy)]
EEw (E X, y)ll E Eww.s By Tyy (#l12)
Σ
((w,x,,) xi, v)l
- Pxp [1( X, 8)]
Σ
Epw.x, (lW, ([(,,,,,)))
(20)
Ty (m, E**
Given the assumption that Pw.z, = Pw.zy, Vi + j, we have all the terms in the sum in equation 20 are identical. Thus we have
(P Pwis) = Ep E [e(w,X, x)] (a..u)E
Σ
Epw. x [[(,, X. v)
= -E [W W. X, y) E. [e( X,1),
(21)
which completes the proof.
A.2 Proof of Theorem 1
Theorem (restated) For y, assume the loss 8(W, X, v) is By sub-Gaussian under Pw & P then
the class- maasaeeneraliiztion error of class in Definition I can be bounded as:
(Prs (P (oom://A..Pllllsssoooo///wlvll PxIY=v)
(22)
Proof. From lemma we have
gen (Px,V, Pw]s) = Ep & [((W, X, v)] E. [e(W, x)).
(23)
x|v=
18

---

Published in Transactions on Machine Learning Research (07/2025)
Using the Donsker-Varenn variational representation of the relative entropy, we have
Ex De x)1) log E PPOOR [e B (..)).
(24)
for all A E IR On the other hand, we have:
log W (((W.X.)-
(. WBBE( -.
log E P
log E w X
AE AE X , (( X. v))
Using the sub-Gav Gaussin assumption, we have
< AE O (e(W.X, y)) + 2²07
log Bp Px x
(ede(W.X.y))
(25)
By replacing in equation 24
we have
X207
D(Pw.xY==glPWw @ Px|x= 2 A
IIW, (((,, y)] Ex P 1e ((W,,,
2
Thus,
D(PW.xIX=ylI/W & Px(Y=1) - A(B www, v)] BP [e(W, x)))
+ 20 0, E
(26)
Equation equation 26
non-negative parabola with respect to X, which implies its discriminant must be
non-positive. Thus,
B [ W. X. y)
O - [Q (W.X, S (P & Px
which completes the proof.
A.3 Proof of Lemma 2
We use Lemma 2 a main tool to prove Theorem and in Section 3.2 in the super-sample setting.
Lemma (restated) Consider the super-sample setting, and let V V be random variable, possi- bly depending on W. For any function g that can be written s(V, U, =pm() (y hVV U: 1 [ (yy- hVV, 2, --,),, where h E [0, 1] a bounded function, we have
Ba. (V, U, mpm])] < / max (v. = 1 - (V:U.).
(27)
Proof. Let (V,U) be independent copy of (V, U.). The disintegrated mutual information Izpm (V; U+) is equal to:
Zpm (U; V) U /Pliitii==iii Pu.), Thus, by the Konsker-Varadhie variational representation of KL. divergence, VA R and for every function 9, have
(28)
V:
YE, lo U,, 2(2n)] - log Ev,U, V. (Zp Ao (.
(29)
mpm
Next, let (V, U, 2gmn) can be rewritten follows:
U. h A(V,211) Ui) - 1 u. U. I(, U.). It easy to see that g(V, U., Zppn))
V. U =pm: = U. (, ( 2V, - fot =y) (V,27)).
(30)
19

---

Published in Transactions on Machine Learning Research (07 (025)
Thus, we have
[e (V....)))))) log 1E V.U, [(mm
AU
t0 =y) NVV.2 (x) (VV.et))
log Bv, p.. =
e
Note that T. U1 (v,==)) =v) /V, 25) [1x / [. +()
and U, E (-1,+1}. By Hoeffding's Lemma,
we have
22 10, - ((V (o/ A ((V
log F
V. [izn [/20] (e (e I log 12.) # Fe
As h e [0, 1l hv (xr (y (V. 2x max(1 {u. =ロ} 1l ((xt= Thus,
X²
2² max 11 (r, =yن (n)=
1 log Sg. V.U. Fpm (V....))))))
max 11 (v. =yp (ut (n==
2
2
Replacing in equation 29 we have
1 Aane (V;U,) 2 XEEv U. 2mm1= ( |اا 1,V, 21
[s U==y) h(W, u U1
(31)
2²
max (ax((1(1))))) (,,
"y 1 (vr =w))
2
Therefore, AA E R,
X2
2 max 11 (M, my) 1 lut -y)) www. (g(V (, U. 2/21]] + 1apm (V; 2 0.
(32)
The equation which implies
32 is a non-negative parabola with respect to A. Thus, its discriminant must be non-positive,
B [V(V, U, 2|2n)] ) S 2 max (v, =y} 1 (v. =yح T UV:
(33)
A.4 Proof of Theorem 2
Theorem 2 (restated) Assume that the loss ((w,,, 2, [0, 1] is bounded, then the dasss-enncralization error for class y in Definition can be bounded as
gen Px,, Pwis)] S
Ez Ezgznl
max (Y,=u)) =9) 1 [xx =v) ) (WUU)
(
(34)
Proof. Using Lemma 2 with V W and h(V,2) ((W,2) 2) in, have
Ew.u. lg( W. Uú 2p2m)) 2 12 (v. =y} I (xt (u)t=)) Hapa (orren(W; (W; U:),
(35)
where (W, U, Fpni) 1 (y WW 24 U ((-vi ((,, 2 U.). Thus, by summing over the different
terms in Definition 8 and taking expectation over Zi2n)
gen, (en,, Pwis)l Eziann
V 2 max (X, (mxxx((Xx==))) 11 ((xt=0)) Tzzzn (W:U,)
(36)
Z
20

---

Published in Transactions on Machine Learning Research (07 (025)
A.5 Proof of Theorem 3
Theorem restated) Assume that the loss ((W,X, x,y) [0, 1], then the class-generalliattion error of class in Definition 8
be bounded as
gen , (Px,y, Pwis)] & Bz
V (X,= (x] =v) /y
(fw(X;): (
(37)
Z i=1
Moreover, the class-fCMMe bound always tighter than the Mlass-MML bound in Theorem
Proof. Similar to the proof of Theorem in, we have
Using Lemma with V = (w(277 and h(V, 24) = ((.w(x))))) (n)
E Aw(a (2.0 (o(s X.), Us mpmni] V max (u. =v} 1l (ut -n) ) (fw(x;)) U:).
(38)
Thus taking expoctation with respect to Zizn) yields the desired result
gen Jen,(Pxxxy (Px,x, Pw]s)] < EZ (l i=1
2 max (Y, (x ([w(XF)UU,)
(39)
Due to the data processing incquality, we have U + W + fw(+)) given Z[an]- then follows directly that the Class---MMl bound always tighter than the class-CMI bound.
A.6 Extra Bound of Class- generalization Error using the Loss Pair L.::
Theorem 7. (class-e-Cll) CMI) Assume that the loss E(g. v) [0, 1], then the class-genemmlization error of class in Desinilion can be bounded as
gen (Px Pwis)] S Ezizni
2 max (1) - (x+ ) Iza (L U,)
(40)
nz (pni 2ml
Proof. Similar to the proof of Theorems have
2 and
3
Using Lemma with V L and h(V 2;) = L, in, we
E. =(am) m(..) (o(fw (X,), U, m(mm) ) S max(1 (u) = 1 (vo =v3 ) Jypgn (L U.).
(41)
Thus, taking expectation with respect to Z yields the desired result
gen (PxY, Pwis)] S Ezjanl
max 1 (Y, =y} 1 (x I (L U,)
(42)
i=1
A.7 Proof of Theorem 4
Theorem 4 (restated) Define L,L 11 (w,--)) ((W()))) -1 (0t
(u--v) -v) ([J([X,)+,,)) Assume that the
loss {(G.v) y) [o, 1] bounded, then the class meaaaaennraalioiionn error of class y in Definition can be bounded
as
gen, (Px,,, Pwis)) & E2iaa)
v 2T (AyLe U.)
(43)
n
i=1
21

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Proof. First, notice that for fixed realization 2[2]], ( ) 1 vi- ( = L
((W, 24 U.)
U.(1 (0T my 2 ) 1 (x, -) (W
Next, let L U:) be an independent copy of (A, U.). Using the Donsker Varadhan variational rep- resentation of KL divergence, we have AA E R and for every function
(g( Li U. 2(2m)) 7 (A, U.) U. [(pa)
(44)
log E A,L, U. =
U,AyLS and we have Next, let I U1, ((2)))
log E A, A, (apnn F(en)
[e (.
U.appa))] = log E U.I, Fjan I
(45)
Note that U [U,A,L L, and U. (-1,+1) Thus, by Hoeffding's Lemma, we have
log R L 1,12 L. I log E. LL, (2,2m [Rpa)
[e 22 A
(46)
As E [0, 1], it follows that L,L, E [-11, and AاL, S1 1. Thus,
12
log E B,,,, U, 2 From) [c (A U. Ppa 5
(47)
2
Replacing in equation 44
we have
X²
1 Tapall (A U.) 2 AEA,LL U,A,L L.]
(48)
2
Therefore, AA E R
2 2
- U, Lo(AyLi, U. [pmn)) + Lap (AyL;; U,) 2 0.
(49)
The equation which implies
49 is a non-negative parabola with respect to A. Thus, its discriminant must be non-positive,
E Up [g([ (((ow(X)))))))) U2, =ppn)) s 2T (A, U.). U.).
(50)
Taking expectation with respect to Zinn yields the desired result
(Px,, Pwis)) S Bzian
2Tzza (AyLi; U:)
(51)
n x=1
In the following, we will show that the A,L-CMI is always tighter than the class- class-f-CMI bound in Theorem 3 Duc to the data processing incquality, we have U + W + fx;+ + A,L; given Z For a fixed Z we have four diflerent possible cases for each term in the sum:
1. If # y and 4t * y: In this case, max 1 [Y, (Y; (x,==)) =w) (fw(x:); U.)
On the other hand, we have A&L. 0. Therefore, Iz (AyLe U.) max(1 (Y, = 1l (xy (fw
U.).
2. y1 = y and yt = y: In this case, max 11 (Y. my} |x, 1z (Fw(X=);U
Iz (X ).)
Due to the data processing inequality, Iz (A,Les S,اiB U.) <
Izian (fw(X) xx;;;;;; = max ( =)) (xx
-x)==)) =g) = Uzpa (/w (xx))))
22

---

Published in Transactions on Machine Learning Research (07 (225))
3. If Di y and Vi y: In this case, max 11 (X, =w} = (fw (fw(X:):U,)
Izp (/w(X) ); U.) and - L, As W /w(X; L is also Markov chain, using the data processing inequality, we have ppn UI) S Iz (fw((5)) U,) and thus Izzao (AyLe U,) - Izp (fw(X:F;UU)
=,
4. If vt - y and Vi + y: This case will be the same as the previous situation by swapping the and
Based on this discussion, we can conclude that
Iz (AyLi; U:) S max(1 (yT-v)) my>> I [ v) 1Z (fw(X;) ;); U:)
(52)
A.T-CMT is always tighter than the class-f-CMI bound.
B Discussions on Definition 3
B.1 Equivalence between Definition I and Definition
2
Here, we show the exact equivalence between Definition and Definition 2
n
gen,
Ezaaan n2
EU,.WIzaan
wiz [ 00:00" ((W, Z (,,.UU,) U.) (r v) ((W, 2. }]
1
Ez Ezzan BU. W. Σ [1 C
=w) (WW (.z,1)) U. (x," =y} ((W, 2.
(x,"==n>
P(y)
-Eu,w.Zer
((W, Z, U.) (x," ((W, 2 IG
P(y)
= -Ew BwWBeMPIp (((,, ] - Ez,wly e(W, 2) = gen (Px Px,x,.Piss)) Pwis).
(53)
Hence, class-gencralization bounds based on this variants can be converted directly to standard generalization bounds by laking expectation over y, i.e., gen Ey [geng)
B.2
Other possible Definition by changing the sappr-samples setting
Another possible approach to study class- gessaaeneraiiitiion error requires tweaking the super-sanee sample setting as follows:
Let Y [n = (Y,,... Yn) E ym be a collection be a collection of n i.idd samples from Py. Let X X(20] = (X ] E 2 such each pair X are drawn independently from the distribution Px|y,- Then the supersamples Z ( , z E g2n is obtained such that Z (X+, Y,) and Z (X,, Y,). The training data [n] (z R. z , ZRR) is selected from the data 2:20| where Rin = (R,, .R,)) e {-1,1]" is the vector composed of independent Rademacher random variables. Basically, R, selects which sample from Z to be included in the training data and the other one for the test. The main difference compared to the CMI formulation in the main paper is that we construct our data such that for each 1 1, n, Z and Z are guaranteed to share the same label, while this is not necessarily the case for the prior formulations (Steinke & Zakynthinou 2020 Zhou et al. 2022). Hence, in this setting, the two indicator functions in Definition 3 are equal and can be replaced with only one indicator function to define the gaas-generalization error.
The key issue with such a formulation lies in creating some dependency between the training set 2R and the test set 2 R Therefore, the difference between the loss evaluated using 2n1 and Z can no longer be interpreted as the true generalization error. Formally, in the main paper setup, by taking the expectation
23

---

Published in Transactions on Machine Learning Research (07 (07/202) /025)
over Y over Definition 2
we find
Ez U.W
(e(W
- ((W, - 1)
= Σ U.W (((,, 2, U.) - e(W, 2
71
= Ew ( Z)] Ew.s ((W.)) .S]
(54)
= gen Pz. Pwis).
This shows that the standard expected generalization error can be obtained by taking the expectation over Y for the chas-genorallization error. This would no longer be the case in the alternative formulation presented
above. The equality in equation 54 can no longer be achieved due to the dependency between 2 and
x)
2R Hence, the bounds for the standard generalization error via the class-wise analysis (Section 5.1 can
(m)
no longer be obtained directly. To see this, consider the following partition of the sample space z 0 UUN
such that ! { 2²,y² } only contains sample pairs with the same label,
1 gen( Pwis) =B =B2 2n) U.W n Σ (e(W, R. ((W,2, 2...1)
=P(2; 2 [an)
U.W U.W I Σ (e(W,2, R1) -(( ) E en]
-
(55)
+ (1 - P(ž E 12) 2an). U.W
[] nn Σ
E(W )) E E?]
The above decomposition of the generalization error contains two terms: The first term measures the general- ization gap between samples with the same label. Thus, it can be interpreted as a 'within-class generalization error! The second term measures the generalization error between the samples with different labels. It can be interpreted as "betwcen-class generalization error.' Taking the expectation over Y of the glass-gencralization error, in the setting considered with 2gn] will only include the first term in equation 55 Thus, we consider the class-gent generaeeneriiiiooonn error given by Definitions 2 instead of the setting discussed here.
C Additional Empirical Results
C.1 Experiment Setup
Here, we fully describe the experimental setup used in the main body of the paper. In our study, we focused balanced datasets such as DOPAR-10/CIFARCE where each class is represented equally, to ensure that the observed dass--enerallzattion disparities are not confounded by class imbalance. This balance allows us to attribute disparities in class- generainniiinnnoio error to intrinsic properties of the model and data distribution rather than to skewed class proportions.
We use the same setup as in Harutyunyan et al. 2021), where the code is publicly available For every num- ber of training data n, we run my number of Monte- Carlo trials, i.e., we select mi different 2n samples from the original dataset. Then, for each 2/2n], we draw my different train/test splits, i.e., my random realizations of U. In total, we have mi m2 experiments. We report the mean and standard deviation on the results. For the CIFERIO experiments, we select mi = 2 and m2 = 20. For its noisy variant, we select m. = and m2 = 15. For both datasets, we use ResNet50 pre-trained on ImageNet. The training is conducted for 40 epochs using SGD with a learning rate of 0.01 and a batch size of 256.
C.2 Full Class caasaageneralizttion Error vs. Standard Generalization Results on CIFAR10
As a supplement to Figure 1 (bb,, we plot the standard generalization error along with the class-ggnnrallization error of all the classes of CIFAR1O in Figure 0 Consistent with Section 1 we observe significant variability in generalization performance across different classes
24

---

Published in Transactions on Machine Learning Research (07/2025)
0.20
standard
"airplanes" gen
"cars" gen
0.15
"birds" gen
Error
"cats" gen
0.10
"deer" gen
"dogs" gen
"frogs" gen
0.05
"horses" gen
"ships" gen
1000
3000
5000
10000
"trucks" gen
Number of training samples
Figure 6: The standard generalization error and the gencralization crror relative for all classes on CIFAR10 as function the number of training data.
C.3 Numerical Results for All Classes of CIFAR10 and Its Noisy Variants
In Figure 7 present the empirical evaluation of our bounds all the classes of CIFAR10. Morcover, generate the scatter plot between the dass-generallzaaton error and the class-f-CMI bound. We note that similar to the class-AT,y results in Figure our bound scales linearly with the true glass-enerallzzation error. The results of noisy CIFAR10 with clean validation, presented in Figure S are also consistent with these findings. We also experimented with noisy CIFAR10 with noise added to both the train and validations. The results are presented in Our bounds, this case, are able capture the behavior of the class- gencralization error for the different classos.
25

---

Published in Transactions on Machine Learning Research (07 2275))
0.6
"airplenes" gen error class CMI bound
0.6
"birds" gen error class CMII bound
0.6
dlass&&CMM bound
gen error
cless-ddy-CMi bound
cless-ddy-CMi bound
class-ddy-CM bound
Erro
0.4
Error
0.4
Eroo
0.44
0.2
0.2
0.0
1000
3000
5000
10000
0.0
1000
3000
5000
10000
0.0
1000
3000
5000
10000
Number of training samples
Number of training samples
Number of training samples
0.6
class-f-CMI bound
"cats" gen error
0.6
cless-f-CMI bound
"deer" gan error
0.6
"dogs" gen error
class-f-CMI bound
cl bound
(ass--Al-CMM bound
class-AL, CMI bound
Error
0.4
Error
0.4
0.2
0.2
0.2
0.0
0.0
0.0
1000
3000
5000
10000
1000
3000
5000
10000
1000
3000
5000
10000
Number of training samples
Number of training samples
Number training samples
"trogs" gen error
"horses" gen error
"ships" gen error
0.6
class-f-CMI bound
0.6
cless-f-CM bound
0.6
cless-fCMI bound
class-MM,- CMI bound
class-Ad,-CMI bound
class-Ml--CM bound
Error
0.4
Error
0.4
Error
0.4
0.2
0.2
0.2
0.0
1000
3000
5000
10000
0.0
0.0
1000
3000
5000
10000
0.0
1000
3000
5000
10000
Number of training samples
Number of training samples
Number of training samples
0.7
0.6
"trucks" gen error class-f-CMI bound class-Af bound
0.6
Class-f-CM bound
0.5
Error
0.4
0.3
n= 1=100
0.2
0.2
n= 3000
5000
0.1
10000
0.0
1000
3000
5000
10000
0.000
0.05
0.10
0.15
0.20
Number of training samples
Class-generallzatton error
Figure 7: Class-wise generalization on the ten classes of CIFARIO and the scatter plot between class-
generalization error and the class-f-CMI bound in Theorem 3
C.4 Numerical results for CIFAR100
Here, we present the empirical evaluation of our bounds on a more complex dateset. namely CIFAR100. Wo use the same experimental setup as for CIFARIO (in Section C.3 In Figure 10 we generate the scatter- plots between the class- geaaaaennraiiiotionn error and both the class- class-f-CML and the class-ALy bounds under different number of samples. As can be see, our bounds, espocially the class-AL, bound, are indoed linearly correlated with the class- geaaraanneiiiiooo error and can efficiently predict its behavior, even for a dataset with high number of classes.
26

---

Published in Transactions on Machine Learning Research (07 (07/2025)
1.2
1.2
1.2
"airplanes" gen gap class-6CMM bound
"birds" gen gap
"arss gen gap
1.0
class-f-CMI bound
1.0
class-f-CMI bound
ddy bound
class CMy bound
dd,
0.8
0.8
0.8
0.6
0.6
0 0.6
0.4
0.4
0.2
0.2
0.2
0.0
0.0
0.0
500
1000
2000 3000
800
1000
2000
3000
500
1000
2000 3000
Number of training samples
Number of training samples
Number of training samples
1.2
1.2
1.2
"cats" gen gap
"dogs" gen gap
1.0
bound
1.0
1.0
bound
0.8
diass-Ai, CCMI bound
0.8
class-At, bound
0.6
0.6
2
0.6
0.4
0.4
"deer" gen gep class 4 CMI bound class -lss-bly-CMi bound
0.4
0.2
0.2
0.0
0.0
0.0
500
800
1000
2000
3000
500
800
1000 2000
3000
500
800
1000
2000
3000
Number of training samples
Number training samples
Number of training samples
1.2
1.2
1.2
"frogs" gen gap
gen gep
gen gep
1.0
class 6 CMI bound
class: (-CMs bound
1.0
class 6.CMI bound
0.8
class-bt, bound
0.8
class-&l,- bound
0.8
class-dd, bound
0.6
0.6
0.4
0.4
0.2
0.2
0.2
0.0
0.0
500
800
1000
2000
3000
500
800
1000
2000
3000
500
800
1000
2000
3000
Number of training samples
Number of training samples
Number of training samples
1.0
1.2
1.0
Class-f-CMI bound
0.8
"trucks' gen gep bound
0.6
0.6
n=500
0.4
class-Ml,-Cie CMMI bound
0.4
n=800
n=1000
0.2
n=2000
0.0
n=3000
500
800
1000 2000 3000
0.00 0.05 0.10 0.15
Number of training samples
0.20
0.25
glass-generalizztion error
Figure 8: Class-wise generalization on the ten classes of noisy CIFAR10 (clean validation) and the scatter
plot. between class-generalization error and the class-f-CMI bound in Theorem
C.5 Numerical results for SVM & Decision Trees
Here, present the empirical evaluation of our bounds for two classic ML approaches, namely SVM and Random Forest Classifier on MNIST dataset. The main results for both approaches are presented in Fig- ures and 12 respectively. As can be seen, the results for both approaches are consistent with the neural networks' experiments further confirming the ability of our bounds to capture the complex behavior of dlass-generalization.
C.6
Extra Results: Expected Recall & Specificity Generalization
In the special case of binary classification with the 0-1 loss, the class- dass-generaalzaatonn errors studied within this paper correspond to generalization in terms of recall and specificity:
27

---

Published in Transactions on Machine Learning Research (07 (275))
1.2
1.2
1.2
"airplanes" gen gap
"birds" gen
"cars" gen gap
1.0
F-CMI bound
[-CMI bound
1.0
T-CMI bound
Bl,
Bly
ML, bound
0.8
0.8
0.8
0.6
0.6
0 0.6
8
0.4
0.4
0.2
0.2
0.2
0.0
1000
3000
5000
10000
0.0
1000
3000
5000
10000
0.0
1000
3000
5000
10000
Number of training samples
Number of training samples
Number of training samples
1.2
1.2
1.2
"cets" gen gap
"dogs" gen gep
1.0
1.0
1.0
f-CMI bound
0.8
Mi -CMI bound
0.8
-CM bound
"deer" gen gap
0.6
0.6
F-CMI bound
0.6
DL, CMI bound
0.4
0.4
0.4
0.2
0.2
0.0
0.0
0.0
1000
3000
5000
10000
1000
3000
5000
10000
1000
3000
5000
10000
Number of training samples
Number of training samples
Number of training samples
1.2
1.2
1.2
"frogs" gen gap
gen gep
"ships" gen gap
1.0
F-CMI bound
F-CMI bound
1.0
F-CMI bound
0.8
-CMI bound
0.8
ACM bound
0.8
-L,- bound
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
1.00000
3000
5000
10000
0.0
3000
5000
10000
0.0
1000
3000
5000
10000
Number of training samples
Number of training samples
Number of training samples
1.2
1.0
1.0
M-Ss---CIII bound
0.8
0.8-
"trucks" gen gap
0.6
Error
0.6
F-CMI bound
AL, CMI bound
0.4
n-1000
0.4
n-000
0.2
0.2
5000
n-10000
0.0
1000
3000
5000
10000
8.00 0.05 0.10
0.15
0.20 0.25
Number training samples
Class-generalization error
error
Figure 9: Class-wise generalization on the ten classes of noisy CIFAR1O (noise added to both train and validation) and the scatter plot between class-generalization error and the class-f-MMI bound in Theorem 3
expected recall - empirical recall = genp, where p is the positive class.
expecled specificity empirical picily = gennn where n is the negative class.
Standard Generalization bounds (Xu & Raginsky 2017 Harutyunyan et al. 2021) provide theoretical cer-
tificates for learning algorithms regarding classification error eroo/accuracy. However, in several ML applications, e.g., an imbalanced binary dalaset, accuracy /error are not considered good performance metrics. For exam-
ple, consider the binary classification problem of detecting a rare cancer type. While analyzing the model's gencralization error important, we might be more interested in understanding generalization in terms of
recall, as that more critical in this case. Standard theoretical bounds (Neyshabur al.) 2017 Wu et al. 2020 Wang & Mao 2023) do not provide any insights for such metrics.
28

---

Published in Transactions on Machine Learning Research (07 (07/2025)
2.0
2.0
Class-ALy- .M-MMII bound
Class-fCCMI bound
1.5
1.5
1.0
1.0
n=1000
10100
n=3000
n=3000
0.5
n=5000
0.5
n=5000
10000
10000
0.0.0
0.8.0
0.2 0.4 0.6
0.8
1.0
0.2 0.4 0.6
0.8
1.0
glaraggenerl error
Ulass-generalizatioo error
Experimental results of class- geaassgennralizttionn error and our bounds in Theorems and for CIFAR100. We provide the scatter plots between the bound in the true class-generalization error and both: i) our bound in Theorem (left); ii) our bound in Theorem 4 (right) for the different classes for CIFAR100.
Figure 10:
The tools developed in this paper can be used to close this gap and allow us to understand generalization for recall and specificity theoretically.
We conduct an experiment of binary MNIST (digit vs. digit 9), similar to Harutyunyan et al 2021) mi and m2 discussed in Section C.1 are selected to mn and m2 = 30. Empirical results for this case are presented in Figure As can be seen in the Figure, our bounds efficiently estimate the expected recall and specificity errors.
C.7
Extra Results: Generalization Certificates with Sensitive Attributes
Here, we present the empirical evaluation of our bounds for gencralization with sensitive attributes using two datasets, namely using the COMPAS (Larson et al.] 2016) and Adult (Kohavi & Becker 1996) dataset.
The main results for the different sub- sub-population are presented in Figures and 13 respectively. As can
seen, the results are consistent with the previous experiments further confirming the ability of our bounds capture the complex behavior of sub-population based generalization
C.8 Class-specific Gradient Noise Improves Class-generalization
In this paper, studied the phenomenon that the generalization errors for the model can differ significantly among different classes by introducing and exploring the concept of "class-generaaizattin error." This provides a first theoretical step toward understanding this puzzling phenomenon. Our results show that the mutual information between the model and the class data can be used as proxy for this class- generalization error. In other words, when the mutual information between the class samples and the model's parameters high (high memorization), the model overfits this class (poor generalization) and vice versa.
Therefore, to improve the model's generalization performance for specific important class y, our results suggest reducing the MI/CMI between the training samples with class y and the model weights/outpp A straightforward approach to achieve this is by adding noise to the gradient updates during training when a sample in the batch has the label y.
We validate and confirm the effectiveness of this idea with two learning scenarios with target classes: (i) "cars" and (ii) "cats" from the CIFAR10 dataset. We use random Gaussian noise with zero mean and variance of 0.005. The results are reported in Table D As can be seen, using this simple regularization consistently reduces the generalization error and the test error of these classes in both scenarios. This further confirms
29

---

Published in Transactions on Machine Learning Research (07 (025)
"O" gen error
*1" gen error
0.8
'2" gen error
class-f-CMi bound
bound
class-f-CM bound
cless cless-dL, CMI bound
cless CCB bound
cless CM, bound
0.6
0.6
0.4
0.4
0.2
0.2
0.2
0.0
0.0
0.0
500
1000
2000
3000
3000
500
1000
2000
3000
Number of training samples
Number of training samples
Number of training samples
0.8
gen
0.8
gen
0.8
class f CMI bound
cless: f CMI bound
class-Al,- CMMI bound
clase-Al, y-MM bound
0.6
0.6
0.6
Enro
"5" gen error
class-f-CMI bound
0.4
0.4
0.4
class CMI bound
0.2
0.2
0.2
0.0
0.0
0.0
500
1000
2000
3000
500
1000
2000
3000
500
1000
2000
3000
Number of training samples
Number training samples
Number of training samples
0.8
"6" gen error
0.8
-.... *7' gen error
0.8
class:
class Al y-CMI bound
class-Al, y-MM bound
0.6
0.6
"8" gen error
Errr
class-f-CMI bound
0.4
0.4
class-AL, CMI bound
0.2
0.2
0.0
0.0
500
1000
2000
3000
500
1000
2000
3000
500
1000
2000
3000
Number of training samples
Number of training samples
Number of training samples
1.0
0.8
0.8
"9" gen error
Class-f-CMI bound
0.8
Class-AL, MMMl CMl bound
0.6
class-f-CMI bound
class CMM bound
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.0
500
1000
2000
3000
0..0
0.1 Class-generaliiattion error
0.2
0.3
0.000
0.2
Number of training samples
Class-generalization error
Figure 11: SVM: Class-wisc genoralization on the ten classes of MNIST and the scatter plot between class- generalization error and the class-f-MMI bound in Theorem 3
the theoretical findings of our paper and provides some insights into potential approaches improve class generalization in the desired applications.
30

---

Published in Transactions on Machine Learning Research (07 (025))
"O" gen error
*1" gen error
0.8
'2" gen error
class-f-CMi bound
bound
class-f-CM bound
cless cless-dL, CMI bound
cless CCB bound
cless Moss--d,-CM) bound
0.6
0.6
0.4
0.4
0.2
0.2
0.2
0.0
0.0
0.0
500
1000
2000
3000
2000
3000
500
1000
2000
3000
Number of training samples
Number of training samples
Number of training samples
0.8
gen class o CMI bound
0.8
gen
0.8
gen
class: f CMI bound
class f CMI bound
class-Al, MMM, CMI bound
clase-Al, y-MM bound
class-Al C-MI bound
0.6
0.6
0.6
Ento
0.4
0.4
0.4
0.2
0.2
0.2
0.0
0.0
0.0
500
1000
2000
3000
500
1000
2000
3000
500
1000
2000
3000
Number of training samples
Number training samples
Number of training samples
0.8
"6" gen error
0.8
*7' gen error
0.8
'8" gen error
class Al y-CMI bound
class-Al, y-MI bound
class-Al, Al, --CMI bound
0.6
0.6
Errr
0.4
0.4
0.2
0.2
0.0
0.0
500
1000
2000
3000
500
1000
2000
3000
500
1000
2000
3000
Number of training samples
Number of training samples
Number of training samples
1.0
0.8
0.8
"9" gen error
Class-f-CMI bound
0.8
Class-AL, AMMll bound
0.6
class-f-CMi bound
0.6
class CMI bound
0.6
CMl
0.4
0.4
0.4
17
0.2
0.2
0.2
0.0
0..0
0.0%0
500
1000
2000
3000
0.1
0.2
0.3
0.1
0.2
0.3
Number of training samples
Class-generalization error
gesseereeelllzooonn error
Figure 12:
Random Forest: Class-wisc generalization on the ten classes of MNIST and the scatter plot
between class-gen ceneaaeeneraliitiion error and the class-f-MMI bound in Theorem 3
D Details for Results in Section 5
D.1 Full Details of Section 5.1
Standard Generalization Error
Corollary 1 (restated) Assume that for every y E V, the loss ((WXX,y) y) is oy sub-Gaussian under Pw Yx then
gen Px,x, Pwis)) < Σ Ey D(w....... & Px.
(56)
1=1
31

---

Published in Transactions on Machine Learning Research (07 (07/202) 2025)
0.08
0.08
AL-CMI bound "Male" gen error
AL-CMI bound
0.06
0.06
"Female" gen error
Error
Error
0.04
0.04
0.02
0.02
0.00
0.00
2500
5000
7500
10000
2500
5000
7500
10000
Number of training samples
Number of training samples
(a) Adult: Male
(b) Adult: Female
Figure 13: Empiriaal evaluation of our bounds for generalization with sensitive altributes using using the Adult dataset.
Table 1: average class-classificatiinn errors and generalization errors of the larget class in the different sce- narios.
"cars"
"cats" 7
method
testy
genly
testy
geny
ERM
3.91%
3.91%
12.27% 12.11%
12.24% 12.09%
Ours
3.55%
3.54%
Proof.
The generalization error can be written as
gen Px,x Y. Pwis) 71
(Ew z (WW Z)
Ew. 2. (((, Z,))).
(57)
As the loss l is σy sub- nub-Gaussian, using Theorem
have
Epw.XIVs, ((W, X, Y)] - [(( X, Y) (2 @ PxIY=
(58)
Taking the expectation over Y in both sides, we have
(wwxy(((W.) Y) Erwsr
Y) Ey 20 D (Pw.xxj=yylIPP Px|Y=
(59)
Applying equation 59 on each term of equation 57 for each Z, completes the proof.
Comparison between Corollary 1 and bounds in Bu et al. (2020) the case of standard loss Sub-Gaussianity assumption, i.e, o, o is independent of y, it is possible to show that the bound in is tighter than the bound Bu al. (2020). This is bocause
Pw.xiyPy
Ey 220 @ Pxx)) = EMy / 20 202Er log Pw 8 PXIX
Pwx,Y S 12 Z))
Epy 2 log Pw @ Px,
(60)
where the last inequality comes from Jensen's inequality. This shows that class-wise analysis can be used derive tighter generalization bounds.
32

---

Published in Transactions on Machine Learning Research (07 (025))
In the supersamples setting, extending the results in Theorems 2 and into standard generalization bounds is not strightforward, as we do not have gen y Igen y. However, it is still possible to show that gen &. By (geggn and hence the bounds in Theorems for the standard generalization error in the supersample setting. For example, in Corollary 2
2
3 and can be used to derive dlass-dependent bounds
we provide
such an exlension of Theorem
by taking the expectation over y Py. In Corollaries 4 and Theorems
we provide such an extension of
8 and 4 respectively.
Corollary 2 restated) Assume that the loss E(D.V) E [0, I], then
gen Px.Y, Pwis)] S Ey Eziand n V 22 (AyL;
(61)
Corollary 4. (extra resull) Assume that the loss (( E [0, 1], then
gen (xx,, Pwis)l & Ey Ez nY 2max =X, 1xx =x) I (W; U:)
(62)
Corollary (extra result) Assume that the loss ((0.0) E 10, then
gen Sx.x,PWish S Ey Ez Ln
2 max (1 =X xx;=x) (fw(
(63)
Corollary 6. (extra result) Assume that the loss e(D.u) E [0, then
1
gen Px,y, Pwis)) S Ey
2max (o v; Y. xx I [2
(I U,)
(64)
n
D.2 Full Details of Section 5.2 Sub-task Problem
Consider a supervised learning problem where the machine learning model fw((), parameterized with E W. is obtained with a training dataset. S consisting of n i.i.d samples z; = (#:38) E X' x y & Z generated from distribution Pxy. The quality the model with parameter w is evaluated with a loss function l: W ++
For any w E W, the population risk defined as follows
Lp(w)= = llw, Y)).
(65)
and the empirical risk is:
1 71 Σ (w0 ni, vs).
LEP (w, S)
(66)
Here, we are interested the subtask problem, which is special case of distribution shift, ie., the test performance of the model is evaluated using a specific subset of classes A y of the source distribution Pxy. Thus, the target distribution Qxy is defined Qxy(x. (xy(e.y) The population risk on Py(vE.)
the target domain of the subtask problem is
Lo(w)= = Eexx X, Y)).
(67)
A learning algorithm can be modeled as a randomized mapping from the training set S onto a model parameter w W according to the conditional distribution Pwis- The expected generalization error on the subtask problem the difference between the population risk of Q and the empirical risk evaluated using all samples from
gen =Erw (TQ(W) LEp (W,S))
(68)
33

---

Published in Transactions on Machine Learning Research (07/2025)
where the expectation is taken over the joint distribution Pw.s Pwis @ Pz.
The generalization error defined above can be decompased as follows:
F. EPw (EwlLL(W) (P((L)(W))))) Bpw.s (ww.s LEp (W,
(69)
The first term quantifies the gap of the population risks in two different domains, and the second term is the source domain generalization error. Assuming that loss is o-sub-Gaussian under Pz. it is shown in Wang & that the first term can be bounded using the KL divergence between P and Q:
Mao 2022)
Eew [LQ(w) - Lp(w)] S D20)D(Q)P).
(70)
The second term can be bounded using the standard mutual information approach in Xu & Raginsky (2017)
as
Brw. (W) LEp (W,S) (W;
(71)
Thus, the generalization error of the subtask problem can be bounded as follows:
geng, S 220=D(Q11)) + (2)5)
(72)
Obtaining tighter generalization error bounds for the subtask problem is straightforward using our wlsss-wise generalization bounds. In fact, the generalization error bound of the subtask can be obtained by taking the expectation of Y Qr
Using Jensen's 's inequality, we have gell. = YY genyy < EY~ genyy]. Thus, we can use the results from Section 3 to obtain tighter bounds.
Theorem Buublask-Ab,-CMMM (restated) Assume that the loss ((,,,, E [0, 1] is bounded, Then the subtask generalization error defined in 14 can be bounded as
1 n
Q. Eq
$ Ex~
Ezjam
2Zz (AyL; U.)
1=1
Similarly, we can also exlend the result of Theorem and 3 to the sublask as follows:
Theorem 8. (subtask- CMI) (extra result) Assume that the loss ((w,,,)) x, E [0, 1] is bounded, then the subtask generalization error defined in 14 can be bounded as
n Σ /2 m A xx,=x) (W; W.))
Igenq,EEl Ex-ox
Ezzpal
Theorem Seubtask-fCCMi (extra result) Assume that the loss f(w,x, [0, 1] is bounded, then the be bounded
subtask generalization error defined in 14
q. S Ex-ex Ezigan
2 max (oaxxlyy==x xY l -x) (x U.)
D.2.1 Empirical Validation of Bounds for Sub-task problem
We conduct experiment of the CIFAR10 dataset, similar to Section We design two subtask problems with this dataset. In the first scenario, referred to here by subtask1, we consider the target distribution to be composed of the two classes "airplanes" and "cars". Whereas in the second scenario, referred to here by subtask2, we construct the target distribution using three classes, namely "airplanes", "cars" and "birds".
my and my discussod Scction C.I are selected be m, and m2 15. Empirical results of the bounds in Theorems g and are presented in Figure 14] As can be seen in the Figure, our bounds efficiently estimate the generalization errors for the subtask problem.
34

---

Published in Transactions on Machine Learning Research (07 (025)
"subtask 1" gen error subtask-f-CMI bound SUbtask-ALy-CM bound
"subtask 2" gen error
0.6
0.6
subtask-f-CMi bound
Subtask-ALy-CM bound
Error
0.4
Error
0.4
0.2
0.2
0.0
0.0
800
1000
2000
3000
5000
800
1000
2000 3000
5000
Number of training samples
Number of training samples
Figure 14:
Generalization performance on two subtask1 ("airplanes" and "cars") and subtask2 "airplanes", "cars" and "birds") problems constructed using CTFAR10 dataset for different training sample sizes.
D.3 Full Details of Section 5.3
Generalization Certificates with Sensitive Attributes
Theorem (restated) Given / T, assume that the loss 6(W, Z) sub-Gaussian under Pw @ Pz. then the attribute-gennn generaiziennnniiiiiinnnn error of the sub-population T as defined in be bounded as follows:
gen, gen, (wixs, & 220
@ Par-= Pw @ P P
(73)
Proof. We have
gen, (Px,y, Pwis) = O ((W,)) Z)
EEw ((W Z)].
(74)
Using the Konskor-Varadiee variational reprosentation of the relative entropy, we have
D D(Pwiz& @ P & PZIT=r) 2 /e Z)] log E P A((
AA R.
(75)
On the other hand, we have:
log w Ti
A.((W.)) XEIRCW.
log E S T-
log E.
(e(W22)) Z)
XE Sr S (W.2)) Z
T-T
Using the uub-Gaussian assumption, we have
1202
log E Ep O
(((W Z) + [e [ < & (!(W,
(76)
2
By replacing in equation 75
we have
X²o
D(Pwzz & Pa @ PZTT=1) 2 (WP Ep -p ((
(77)
2
Thus, we have:
D(Pwiz & PP & PZ)T-r)= XBP (((W, Z)]
E Ep & P T-
(WW, Z)))
+ 2 1 (78)
35

---

Published in Transactions on Machine Learning Research (07/2025)
equation 78 is non-negative parabola with respect to X. Thus, its discriminant must be non-positive. This implies
P Z]]
Ep B ((W Z)]l S (202 @ PZ/T-=IlPW @ P2)T-I),
(79)
which completes the proof.
36


Reviews:
[{"review_id": "cKVW5H7rdD", "reviewer": "Reviewer_UMUd", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n- The idea and contributions are interesting.\n- I appreciated Section 5 (Other applications). I especially found 5.3 very compelling and relevant to modern ML. \n- I found Figure 2 very useful.\n- I think that the literature review touches on the key topics, namely the theoretical framework that is used and prior work on the class-dependent analysis. \n- The proofs don't have any obvious faults; I haven't scrutinized them deeply.\n- The experimental results look good, particularly when including the results in the Appendices. Further, the right column of Figure 3 shows key point that the methods in the paper track the true class-generalization error appropriately. \n\n### Weaknesses\n- The writing and presentation can sometimes be unclear. See the comments in the `Requested Changes` section.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper tackles addresses the fact that neural networks in classification often have different performances for different classification classes and that standard generalization bounds do not account for this. The paper therefore presents a class-generalization error and presents tractable versions in the super-sampling setting using the Conditional Mutual Information framework. These are evaluated using the CIFAR10 dataset; the Appendix provides further analysis with other classical ML methods (SVM and Decision trees).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Note that I have bundled minor and major changes together below. I should also note that I am not directly involved in this specific sub-field of work, so my review is based on how someone like that would read the paper; if there are any sub-field specific conventions or knowledge that I have missed, then please let me know in the rebuttal. \n\n### Introduction\n\n- 'Therefore, reasoning only concerning the standard generalization error (red curve) cannot capture this class-wise behavior.' -> 'Therefore, reasoning that only concerns the standard generalization error (red curve)**, which averages over the classes,** cannot capture this class-wise behavior.' : I think it would be good to reword as such to emphasize that standard generalization errors average the error over the different classes. \n\n- Figure 1: Could you add figure titles to the left and right cases? Furthermore, why not use subfigure titles, such as Figure 1a and Figure 1b, rather than (left) and (right)?\n\n- Figure 1: Could the caption say how many repetitions were done?\n\n- Figure 1: Can the markers be made larger; they are quite difficult to see at the moment. \n\n- 'this phenomenon using information-theoretic generalization bounds, as they are both data-dependent and algorithm-dependent' -> 'this phenomenon using information-theoretic generalization bounds, as **such bounds** are both data-dependent and algorithm-dependent': This makes it clear that 'they' in the original sentence refers to the generalization bounds. \n\n- Figure 1: I think it would better to show the uncertainty as error bars, rather than interpolating.\n\n- First paragraph page 2: \n\n- 'When comparing the results on both datasets, it is worth noting that the generalization error of the same class “trucks” behaves significantly differently on the two datasets. This suggests that class-wise generalization highly depends on factors beyond the class itself, including the data distribution, the learning algorithm, and the number of training samples.' : I am not sure that I fully agree that the second sentence can be concluded from the first. My understanding is that the only difference between the two figures is that a small amount of noise was added; so how can this imply that _the learning algorithm_ affects the generalization? I am not saying that it doesn't, but that Figure 1 doesn't imply this. \n\n- Notations: Why are random variables in bold? \n\n- Notations: Can you write a sentence about that the intuition behind the _disintegrated conditional mutual information_ is? Since this is an important part of Theorem 2, I believe it would be useful for the reader to understand if they hadn't come across the term before. \n\n### Related Work\n- Information-theoretic generalization error bounds: Can a sentence or two be written that explains what _Information-theoretic generalization error bounds_ are? Specifically I am interested in why they were developed and what benefit they bring. \n\n### Class-Generalization Error\n- I found it slightly confusing that the notation $\\mathbf{Z}$ exists. Why not just use $\\mathbf{X}, \\mathbf{Y}$? I think this is mainly because the text often uses some variation of $x, y$, $\\mathbf{X} | y$, etc, and for just the specific case of $\\mathbf{X}, \\mathbf{Y}$, it changes to $\\mathbf{Z}$. I am of the opinion that this isn't necessary. Furthermore, what is the difference between $\\mathbf{S}$ and $\\mathbf{Z}$?\n\n### Empirical Evaluations\n- Based on this section and the Introduction, it is not clear to me why the 5% label noise dataset is significant. As in, why was the case of added noise considered, and why this level of noise? Why not a large amount on noise?\n\n- Figure 3: Same as Figure 1; please put titles to each sub-figure. Perhaps a grid-like notation can be used, where each column and row has a title on the top and left edges.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "nt8QNoQOxc", "reviewer": "Reviewer_Ejav", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "First and foremost, I would like to express my sincere appreciation for the authors’ efforts in developing this paper.\nI would also like to note that the following review is written with the understanding that TMLR places a strong emphasis on accuracy, persuasiveness, and clear evidence, as well as capturing the interest of readers, rather than solely focusing on novelty or impact.\n\n\n## Strengths\n\n- The derivation of KL and CMI-based bounds for class-wise generalization error is rigorous and well-structured.\n- The bounds are empirically validated across different scenarios, including noisy data and traditional ML models.\n- The proposed framework is shown to extend naturally to other settings such as subtask generalization and fairness-related concerns.\n\n\n## Weakness\n\n- **Limited discussion of practical applicability**: The practical significance of estimating class-wise generalization error remains underexplored.\n  - For instance, while Section 5.3 presents a theoretical extension to attribute-wise generalization for fairness evaluation, the paper does not investigate how meaningful or actionable the proposed bounds are in actual fairness-sensitive settings. Personally, I find the idea of evaluating generalization through the lens of fairness more compelling than simply observing that deep networks generalize unequally across labels---a phenomenon that might be anticipated to some extent, considering that neural networks are known to be poorly calibrated in classification (as suggested by prior calibration literature such as [Guo et al., 2017](https://arxiv.org/pdf/1706.04599)).\n  A deeper discussion of how class-wise generalization could be used as a tool for fairness auditing would greatly strengthen the paper’s contribution.\n\n- Underutilization of empirical insights in the appendix: Appendix C.5 (on traditional models) and C.6 (on recall/specificity connections) contain promising results that are not sufficiently discussed in the main text. Especially in the context of fairness, these experiments could have served as strong support for the practical value of the proposed approach.\n\n- Limited diversity of experiments: While the theoretical focus of the paper is clear and appreciated, the empirical results are mostly limited to CIFAR10, MNIST, and their noisy variants. Including experiments on diverse benchmarks—such as fairness-oriented datasets, or even non-vision domains—would help showcase the generality and broader applicability of the proposed framework.\n\n\n## Concerns regarding the interest of TMLR readers\n\nThis paper is likely to interest TMLR readers working on generalization theory, information-theoretic analysis, and fair ML. \nHowever, to reach a broader audience, the paper would benefit from a more concrete discussion of the practical motivations and downstream benefits of class-wise generalization error analysis—particularly in real-world applications such as fairness.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces the notion of class-wise generalization error—a measure of how well a learning algorithm generalizes for each class individually, as opposed to the standard average generalization error across all classes. The authors propose information-theoretic bounds on class-wise generalization using KL divergence and Conditional Mutual Information (CMI), including a tighter variant using the so-called $\\Delta\\_y L$-CMI.\n\nKey contributions are as follows:\n\n- The derivation of upper bounds for class-generalization error using KL divergence and multiple CMI-based quantities.\n- They show the connection between the standard average generalization error and proposed bounds.\n- Empirical validation on MNIST / CIFAR10 and a noisy variant, showing the tightness and class-dependence of the proposed bounds.\n- Extension of the theoretical tools to standard generalization bounds, subtask problems, and fairness analysis (e.g., sensitive attributes).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "To address the shortcomings identified earlier, I believe it is important to clarify and correct the points summarized below. If I have misunderstood anything, I would greatly appreciate your guidance in identifying the inaccuracies.\n\n**Discuss in more depth the practical implications of class-generalization bounds:**\n- When is it better to analyze class-wise error instead of standard generalization in practice?\n- As a more speculative question: if one can estimate the class-wise generalization gap (even via an upper bound), could this information be used to adjust or correct the predicted probabilities for specific classes in terms of generalization? For instance, classes with large generalization gaps might systematically exhibit overconfidence, and class-wise bounds may provide a way to recalibrate such predictions. \n\n**Strengthen the fairness-related discussion in Section 5.3:**\n- Can the proposed bounds provide meaningful fairness guarantees in practice?\n- How do they relate to existing fairness metrics or frameworks?\n\n**Move or summarize key empirical results from the appendix into the main paper, especially:**\n- The evaluation on classical models (Appendix C.5).\n- The connection between class-generalization error and recall/specificity (Appendix C.6).\n\nOptionally, include experiments on a more diverse benchmark (e.g., UCI benchmarks) to highlight the flexibility of the proposed framework.", "broader_impact_concerns": "I believe this work does not raise any ethical concerns, as it is a theoretical study focused on the fundamental issue of generalization error in the context of machine learning.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "xtfaITzkJm", "reviewer": "Reviewer_uLVn", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strenghts:\nThe problem under study is well motivated, and the theoretical tools derived provide insights into the varying performance of supervised learning algorithms on different classes, and can be further used in other machine learning problems as detailed in section 5.\nExperiments further demonstrate that both the class-$f$-CMI and class-$\\Delta$-CMI bounds capture well the behaviour of the class generalization error bounds.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work introduces the concept of class-generalization error, a measure designed to quantify how supervised learning algorithms generalize for each individual class within a data distribution. Using a class-dependent approach, the authors derive class-specific generalization bounds by adapting standard information-theoretic generalization analyses to this novel class-specific setting. The following results are important:\n1. Bounds within the mutual information setting:\n     1. The class generalization error of a given class can be upper bounded using the KL divergence between the joint distribution of weights and data, and their marginal distribution, both conditioned on the class occurence (Theorem 1). By taking the expectation over all classes, this yields a tighter global generalization bound than the traditional individual sample bound (Corollary 1).\n2. Bounds within the conditional mutual information setting:\n     1. Using the super-sample setting, the authors derive class-specific generalization upper bounds involving the conditional mutual information between the weights and the selection variables conditioned on a super-sample. (Theorem 2)\n     2. The authors further derive tighter bounds that are easier to estimate and allow for black-box estimation. The bounds involve respectively the conditional mutual information between the model's output and the selection variables (Theorem 3) and between the difference of loss functions evaluated at the examples containing the class in question and selection variables, providing a tighter bound (Theorem 4).\n    3. Using these bounds, the authors derive a generic generalization bound by taking the expectation over all classes (Corollary 2).\n3. Extension to sub-task problems: The authors obtain tighter generalization bounds using the class-wise generalization results they have derived\n4. Generalization error bounds with respect to sensitive attributes: A really interesting extension of the results developed by the authors is the derivation of attribute-wise generalization error, which provided a great potential for deriving bias-reducing methods in machine learning.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The following changes would strengthen the work but are not critical to securing our recommendation for acceptance:\n 1. The experiments were conducted on CIFAR10 and CIFAR100, which are both balanced datasets. It would be a good comparison to run the same experiments on a different dataset, in order to unveil the effect of class imbalance on the estimated bounds, especially to see if the bounds are still linearly correlated with the true error.\n2. No insight is provided into why noisy CIFAR10 is used alongside CIFAR10.\n3. The notation is sometimes heavy for the reader, and this is understandably due to the mathematical objects involved in the CMI setting. A more careful expression of which variables are conditioned on $Y=y$ is recommended.\n4. In the paragraph following the statement of Theorem 2, it is stated that when the model memorizes training data, the class-generalization error will be large. However, theorem 2 only implies that the upper bound on the class-generalization error becomes large, and there is a number of works highlighting that memorization can sometimes improve generalization. \n5. In the paragraph preceding section 5, point i) states (paraphrased): \"one can use our bound to predict which classes will generalize better than others\" but there is no argument in the paper justifying this claim.\n6. The results in appendix C.7 show a slight improvement and are not sufficient to corroborate the claim \"Such a result provides a new perspective on improving class-generalization by reducing MI/CMI. The initial empirical results in Appendix C.7 show that this is a promising research direction to mitigate the class generalization disparity.\"", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces the concept of class-generalization error, which reviewers found to be a novel and well-motivated approach to understanding why learning algorithms perform differently across classes. While this is a known issue, it's been an under-studied phenomenon in ML.

Reviewers carefully evaluated the theoretical contributions and proofs, and found them to be rigorous. 

One of the things noted by all reviewers was that the theoretical framework extends to other important areas. for example, providing generalization guarantees for sensitive attributes in fairness contexts were seen very promising for future work. In response, the authors strengthened their submission by adding additional experiments on fairness-related tasks.
Decision: Accept (poster)