Fairness Overfitting in Machine Learning: An Information-Theoretic Perspective
Authors: Firas Laakom
Haobo Chen
Jürgen Schmidhuber
Yuheng Bu
Venue: ICML 2025 poster (2025)
Keywords: information-theoretic bounds
fairness
generalization error bounds
fairness overfitting
Primary area: social_aspects->fairness
TL;DR: We propose a theoretical framework for analyzing fairness overfitting through an information-theoretic lens

Abstract: Despite substantial progress in promoting fairness in high-stake applications using machine learning models, existing methods often modify the training process, such as through regularizers or other interventions, but lack formal guarantees that fairness achieved during training will generalize to unseen data. Although overfitting with respect to prediction performance has been extensively studied, overfitting in terms of fairness loss has received far less attention. This paper proposes a theoretical framework for analyzing fairness generalization error through an information-theoretic lens. Our novel bounding technique is based on Efron–Stein inequality, which allows us to derive tight information-theoretic fairness generalization bounds with both Mutual Information (MI) and Conditional Mutual Information (CMI). Our empirical results validate the tightness and practical relevance of these bounds across diverse fairness-aware learning algorithms.
Our framework offers valuable insights to guide the design of algorithms improving fairness generalization.

Fairness Overfitting in Machine Learning: An Information-Theerriii Perspective
Firas Laakom Haobo Chen 2
Jürgen Schmidhuber 13 Yuheng Bu 2
Abstract
(Zemel et al., 2013). To mitigate these risks, various fairness interventions (Barocas et al., 2019; Zafar al., 2017; Lee et al., 2021), particularly regularization-bast based in- in-processing methods (Kamishima et al., 2012; Baharlouei et al., 2020; Mroueh et al., 2021; Li et al., 2022; Iee et al., 2022; Al- ghamdi et al., 2022; Shui et al., 2022), have been proposed to ensure equitable predictions without significantly com- promising model performance.
Despite substantial progress in promoting fairness in high-stake applications using machine learning models, existing methods often modify the train- ing process, such as through regularizers or other interventions, but lack formal guarantees that fair- ness achieved during training will generalize to unseen data. Although overfitting with respect to prediction performance has been extensively studied, overfitting in terms of fairness loss has received far less attention. This paper proposes a theoretical framework for analyzing fairness gen- eralization error through an lens. Our novel bounding technique is based on Efron-Stein inequality, which allows us to derive tight cooommttion-thoorttii fairness generalization bounds with both Mutual Information (MI) and Conditional Mutual Information (CMI). Our em- pirical results validate the tightness and practical relevance of these bounds across diverse fairesss- aware learning algorithms. Our framework offers valuable insights to guide the design of algorithms improving fairness generalization.
All these in-processing approaches are built the implicit assumption that imposing faimess constraints during train- ing will inherently generalize and maintain these fairness standards on new, unseen data. However, neural networks are known for their strong memorization capabilities, often leading overfitting with limited training data. This sug- gests that the aforementioned assumption may not hold, and neural networks could exhibit 'faireess overfitting.'
Is there a ffairnsss overfitting?" To investigate this ques- tion, we conduct experiments on the COMPAS dataset (Lar- son et al., 2016). We evaluate the performance of the stan- dard Empirical Risk Minimization (ERM) approach along- side three fairness regularization techniques. The results, presented in Figure 1, reveal that all these algorithms exhibit faimess overfitting, characterized by noticeable fairness generalization error, particularly in the low data regime. Furthermore, the impact of different fairness techniques on fairness generalization errors varies. While some ap- proaches slightly mitigate the generalization error, others worsen it, in certain cases doubling the generalization error compared to ERM. This highlights the need for a deeper theoretical understanding of fairness generalization, which is the main goal of this paper.
1. Introduction
As machine learning advances, its deployment in high- stakes applications, such as hiring, financial lending, and criminal justice, has raised critical fairness concerns (Mchrabi et al., 2021; Li & Liu, 2022; Barocas et al., 2019). Deep learning models often inherit biases from the data they trained on, potentially leading to inequitable outcomes for certain groups (Pessach & Shmueli, 2022; Ruggieri et al., 2023). Addressing these issues is particularly challenging because neural networks rely on high-dimensionall com- plex representations, which can obscure underlying biases
One key insight from these observations is that neural net- works exhibit fairness overfitiing and the faimess general- ization depends on both the data and the algorithms. This paper introduces theoretical framework for understanding fairness generalization through information-theoreti tools. These tools, which account for both data- and algorithm- dependent factors (Xu & Raginsky, 2017; Harutyunyan et al., 2021; Wang & Mao, 2023) rather than relying solely on model complexity as in traditional VC-dimension anal- ysis (Sontag et al., 1998; Harvey et al., 2017), provide a rigorous foundation for understanding and characterizing the thimess--enneralization behavior of machine learning
'Center of Excellence for Generative AI, KAUST, Saudi Arabia Uniieersity of Florida, Gainesville, USA "The Swiss AI Lab, IDSIA, USI & SUPSI, Switzerland. Correspondence to: Firas Laakom < firas larkom @ kausttedu.saa. Yuheng <buyuheng@unt @du...uu>>.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Fairness Overfitting in Machine Learning: An Information-Thoone Perspective
ERM
PRemover
HSIC
DiffDP
Fairness training error
Faimess testing error
0.04
0.15
0.15
Faimnss gen error
0.03
0.10
0.10
0.02
0.05
0.05
0.01
0.00
250 560 1000 1500 2000 2500 number of training samples
250 500 1000 1500 2000 2500
250 560 1000 1500 2000 2500 number of training samples
number of training samples
Figure 1. Fairness training error (left), Fairness test error (middle), and faimess generalization error (right), i.e., the difference hetween test fairness and training fairness error, are shown as functions of the number of training samples, using the COMPAS dataset with gender the sensitive attribute. Experimental details are provided in Section 6.
models.
Notations: We use upper-case letters to denote random variables, e.g., Z, and lower-case letters denote the realization of random variables. Ez-p denotes the ex- pectation of Z over distribution P. For pair of ran- dom variables W and Z, their joint distribution is de- noted as Pw.z- Let W be an independent copy of W, and Z be an independent copy of Z. such that Pw.
In the context of fairness generalization, prior work has de- rived guarantees for DP and EO within specific algorithmic frameworks and loss functions (Woodworth et al., 2017: Agarwal et al., 2018). While informative, these analyses primarily address sample complexity and do not account for broader algorithmic or data-dependent factors. More closely related the work of Oneto et al. (2020b), which provides bounds under randomized algorithms, but their KL-based formulation is not practically computable in mod- ern settings, e.g., deep neural network. In this paper, we aim to develop a more general and tractable framework for fairness generalization that accommodates a wider class of loss functions and learning algorithms, while capturing key data-specific and algorithmic factors. A detailed related work discussion is presented in Appendix A.
Pw @ Pz- For random variables X, Y and Z, T(X; Y) A D(Px, Y Px @ PPx) denotes the mutual information (MI), and (X; Y) - D(Px.y|z==// Px|zz= & Pyiz=s) denotes disintegrated conditional mutual information (CMI), and Ezlzz Y)] / (X; Y Y|Z) is the standard CMI. We will also use the notation X, Y| to simplify X, Y = 2 when it clear from the context.
2. Fairness Generalization error
Our main contributions are follows:
2.1. Problem Formulation
We introduce the concept of fairness generalization to quantify and analyze how faimess properties observed during training extend to unseen test data. This concept provides a foundation for understanding the challenges posed by fairness overfitting during model training.
Let X, T, and Y denote the spaces of features, sensitive attributes (e.g., race gender), and labels. respectively, with random variables X, T, and Y taking values in these spaces. Suppose that a training set S _ {(X,, T,, Y contains n i.i.d. samples Z, E 2 generated from the distribution Pz, where V; T.) E V. and Z, = (V,, Y,) = (X,; Tú, Y.). For simplicity, we consider the case of the binary sensitive attribute, i.e., T {0, 1). The learning algorithm A then takes S as input and produces hypothesis W E W. which is characterized by the con- ditional distribution Pwis- Furthermore, given a set of indices
We propose a novel bounding technique based on the Efron-Stein inequality, enabling the derivation of tighter informatioon-hhoortiic bounds tailored for fairness gen- eralization. Our bounds, presented in terms of Mutual Information (MI) and Conditional Mutual Information (CMI), offer rigorous insights into the different factors affecting fairness generalization.
{u, E {1,-... n.' with size m, let Zμ = (Z,, 1 be the set of training samples indexed by u. In addition, we denote by X,, (m and V. = {(.,, T )H, Furthermore, in the remaining part of the paper, denote by ny and n. the total number of samples in V with sensitive attribute T, 0 and T, 1, respectively.
We conduct extensive empirical experiments standard fairness datasets, including COMPAS and Adult. These experiments highlight the tightness of our bounds and their ability to capture the complex behavior of the fair- ness generalization error, providing valuable insights for future algorithm design.
2

---

Fairness Overfitting in Machine Learning: An Information- Perspective
Here, we illustrate the definition of faimess generalization using the widely recognized fairness metric "Demographic Parity" (DP) (Barocas et al., 2019), which aims to ensure that machine learning model's predictions are independent of the sensitive group. In Section 5, we show how to extend our analysis to other metrics, e.g., equalized odds. Formally, demographic parity is satisfied when the probability of a specific prediction (say 9 f(w, z:) is invariant the sensitive attribute, i.e., Y T T. To quantify this, we define the fairness- risk for DP as follows:
present separate bounds for DP and equalized odds (EO) in Section 5. This dependence adds additional complexity, making the derivation of tight bounds more challenging than in standard generalization eтror analyses.
No Sample-Based Formulation: Individual sample- based formulations (Bu et al., 2020; Wang & Mao, 2023; Laakom et al., 2024) are widely used to derive tighter bounds in anformationnthherreti generalization error anal- yses, leveraging the fact that the standard empirical risk is an average of the loss function over individual training samples. However, it is not the case for faimesss general- ization error, the fairness loss f (W. S) is inherently group-dependent, requiring multiple samples for compu- tation and cannot be reduced to individual sample-based terms. Consequently, existing bounding techniques (Bu et al., 2020; Wang Mao, 2023; Laakom et al., 2024) are not directly applicable in this context.
(E( A
Σ
f(w xi)
100 - 2
T==0
Σ T=1
f(1, mi) (1)
R1 +
where no and n1 denote the number of samples in S with
sensitive attribute 0 and I, respectively. Given a model
w and a dataset S, Ew, S) quantifies the discrepancy in predictions across sensitive groups.
Sub-Gauusianboounddeess Assumptions: In standard empirical risk, the loss function is averaged over i.i.d. sam- plcs, and generalization bounds are commonly derived using sub-Gaussian assumptions on f(w, X) to establish a 1 Vii convergence rate (Xu & Raginsky, 2017; Steinke & Zakynthinou, 2020). However, as e PP,WWP P's) is not a simple average of f(w, æz), sub-Gaussian assumptions or even boundedness leads loose bounds in our case.
Remark 1. In (1), we normalize using ny + 2 instead of directly using ne to prevent extreme cases of division by zero when Ro 0 or 71 = O.
The fairness- potiesssooop risk, which captures the expected discrepancy in model predictions across sensitive groups, averaged over the Bata-generating distribution P's is
(p(w, Ps) A E (w,
3. General Methodology
The idea of deriving information -theoretic bounds using a subset of data (of size m) rather than the full dataset was first introduced by Harutyunyan et al. (2021), which also demonstrated that individual-based bounds (m = 1) provide the tightest analysis for standard generalization. Building upon this idea and to address group-based losses, Dong et al. (2024) proposed bounding technique that decomposes the generalization error by leveraging different permutations of a subset of training data Z., and rewriting the generaliza- tion error as the average over the different errors defined using these permutations. Directly leveraging this approach, Lemma presents a preliminary bound for the faimess gen- eralization error, formalized in Definition 1:
Thus, the expected fairness generalization error, which quan- tifies the degree of fairness over-fitting can be defined as: Definition 1. The fairness generalization error is
gen fairness EPw s (W,
(W,Ps) Ps) - -ef (EWW)))
(3)
where Pw.s is induced by the learning algorithm P Pwis and data generating distribution Ps.
The generalization error, defined in Definition 1, measures the discrepancy between the fairness-populate hhirness-empirices risk. The primary goal of this paper is to understand and derive bounds for the fairness generalization error, a crucial aspect often overlooked in fairness-aware learning algorithms.
risk and the
Lemma 1. Assume that Ifl E [0, then for any .n),
2.2. Key Challenges
gen
Nertfairne fairness
Σ NEC
/2I(W:V.).
(4)
Compared to the standard generalization error, we outline the following key challenges in analyzing the fairness gen- eralization error:
where C is the set of m-combinations.
Dependence on Sensitive Attributes: The conditioning on the sensitive attribute T is pivotal in the fairness em- pirical risk, as expressed in (1). Designing bounds neces- sitates careful consideration of how the faimess loss func- tion depends on the sensitive attribute, which is why we
The proof is provided in E. In contrast to Dong et al. (2024), where m is predefined by the loss function, m here is a flexible hyperparameter, similar to Harutyunyan et al. (2021), that controls the number of samples used to decom- pose the loss in (1) when deriving the bound.
3

---

Fairness Overfitting in Machine Learning: An Information-Theowe Perspective
Although Lemma 1 provides an important first step toward bounding fairness generalization error, it does not explic- itly leverage the structure of fairness losses, resulting in an overly general bound but consequently too loose. This limitation can be rooted in the proof of Lemma 1, where the technique proposed by Dong et al. (2024) addresses the "No Sample-Based Formulation" challenge discussed in Sec- tion 2.2. However, its primary limitation that it still relies on the boundedness of f (W, Ps) to bound its log- og-moment generating function, encountered in Donsker-Varee Varadhan's ss variational representation, which yields the loose bound. Hence, while Lemma offers valuable starting point, it does not address all the challenges in Section 2.2.
In our setting, this condition is naturally satisfied because all the random variables involved (i.e., |f E [0, 1) are bounded. Since any bounded random variable is square-integrable, this ensures that the assumption holds in our case.
4. Demographic Parity
In this section, we present faimess generalization error bounds specifically tailored for the DP loss defined in (1).
4.1. Mutual Information Bounds
In order to leverage Lemma 2 in the context of Definition 1, we derive bound the sensitivity of (w, vu) with re- spect T.- The main result is presented in Lemma 3.
In the following, we propose an alternative technique that effectively addresses the remaining challenges and derives tight bounds for the log-mone mogmmmnnt generating function. The key result, presented in Lemma 2, represents the first major contribution of this paper.
Lemma 3. Assume that Ifl E [0, let g. : V + R be defined as g(v) g(vi...., ( u) is defined (1). Then. for a fixed w E W and a fixed ny and n", for any S i I m, we have
( v), where
Lemma 2. Let g(V) = 1( V2...., Vn) be a real- valued square- -itterrblte function of m i..dd random vari- ables. Given fixed v (V1,... vm,) and an index i E {I.....m. m). define ह² (ū).... (m) such that ūn Vj for all; j + except on i, i.e. ii & Vs. If g(v) satisfies the following condition for a fixed ny (and consequence ni- = -n)).
(g(e) g( 5 VEVT BEEV
sup
(n ni)'
where H. denotes shifted harmonic mean operator, i.e., Waa Hl(a,."..,,, .0k)
The proof is provided in Appendix C.I. Lemma 3 estab- lishes a direct link between the sensitivity of ( u) to individual perturbations in v and the group sizes nğ and nf for any fixed w. With the key component established in bound
sup REV.EEEE
(g(0) - g(00) 3, isism, m,
(5)
where 3 may depend on ng. Then, we have
Lemma 3, we present the first information-theoree for the fairness generalization error of DP in Definition 1, The main result is presented in Theorem I, which provides bound in terms of the MI between the output hypothesis W and subset of the training samples V..
Var(o(V)) I m E[
(6)
The proof of Lemma 2, provided in Appendix B.1, lever-
ages the Efron-Stein inequality (Boucheron et al., 2013) and the law of total expectation. Lemma 2 provides a bound for the variance of any smooth function defined over independent random variables. As will be shown in the proofs of all subsequent Theorems 1-5, this result offers flexible approach that, when combined with Hoeffding's lemma, serves a powerful alternative to the traditional sub- cuusiaan/boundedees assumption. This bounded difference setup is particularly well- for analyzing generalization errors of loss functions beyond simple average, e.g., the fairness loss in (1).
Theorem 1. Assume that |f| E [0, 1], then for any hyper- parameter m E (2, ,n}, ..,
we have
gen fairness
(8)
m Ev..
H(ng Vo, n Vu I(W, V.).
|C
2
where C is the set of m-combinations.
The proof, detailed in Appendix C.2, leverages Donsker- Varadhan's variational representation of KL. divergence along with both Lemmas 2 and 3. Theorem 1 sheds light on the behavior of fairness- generaliteenn performance, which implics that the less dependent the output hypothesis W is on the input samples = (X, T), the more effectively the learning algorithm generalizes.
Remark 2. The variational bounded difference condition introduced in (5) is similar to the condition in McDiarmid's 's inequality (Doob, 1940), as it captures the sensitivity of the function g(v) to perturbations in its inputs. However, notable distinction lies in the fact that in our case 8 is a random variable as depends on ny as opposed the fixed constants typically assumed in McDiarmid's inequality. Remark 3. The gguare-integrabille assumption in Lemma 2 required for the application of the Efron-Stedl inequality.
Remark 4. The MI terms encountered in conventional MI- generalization error bounds, e.g., (Bu et al., 2020; Wang & Mao, 2023; Harutyunyan et al., 2021), typically involve
4

---

Fairness Overfitting in Machine Learning: An Information-Thoone Perspective
dependence on the label Y, i.e., I(W, Z). However, an intriguing aspect of Theorem 1 is that the bound is label- independent, with the MI terms involving explicitly only
Relaxing the sub-Gaussianity. Similar the MI setting, we aim to provide an alternative to the sub-Gaussian condi- tion for the fairness generalization error in the CMI frame- work. Lemma 4 establishes an inequality that bounds the log-moment generating function of e (mr, in terms of the structure of the data.
V = (X, T). This observation underscores the distinct nature of the DP fairness generalization error.
(w, (w,
Remark 5. The term
H(n. "n, n "I +2 quan-
tifies the impact of group imbalances among different sen- sitive attributes, encapsulating how the relative sizes of the sensitive groups influence the fairness generalization error. Notably, this term is minimized when n = nu for a fixed sample size. To the best of our knowledge, Theorem I provides the first cairness-genrraiizee linking this error to group imbalance, offering new insights into this critical factor.
Lemma AA E R. and |fl E [0. 1), we have
log (ER.,, [2paa)] (Zpnn FPann) W [e (e (.).)
2²m
E
Su So 3. , no " )
(10)
8
H
bound explicitly
The detailed proof is available in Appendix C.3 and is based on Lemmas 2 and 3 along with Hoeffding's 's lemma. Lemma 4 is fundamental element in all the subsequent proofs, as it provides an alternative approach to tightly bound the log-moment generating function typically encountered in Varadhan's Donsker- Donsker-Varadhan's 's variational representation.
Remark 6. Unlike Dong et al. (2024), where the value of m is determined by the specific loss function, Theorem 5 introduces > 1 as hyperparameter of the bound, inde- pendent of the learning algorithm and the form of the loss function. This parameter governs both the size of the subset u and the number of terms considered in the bound's sum- mation. Notably, setting m = n (or m = n - 1) simplifies the bound to one term (or m terms) that scales as 1/ 3/vn and is easy to estimate. In contrast, choosing m n reduces I I(W, Vv) by incorporating more terms, albeit at the cost of increased estimation complexity.
Theorem 2 presents bound for the fairness generalization error defined in Definition 2 using the disintegrated CMI between W and the selection variable R., conditioned on super-sample Z[an].
Theorem (CMI bound). Assume that [fl E [0, 1], then any m E (2, ,,), we have
4.2. Conditional Mutual Information-basee Bounds
gen fairness
S
1
EZ
Σ
(11)
1
One drawback of the proposed bound in Theorem is that it can be vacuous and challenging to compute in practice, due to its dependence on the potentially high- nigh-dimensional model weights W. To address this issue, the conditional mutual information (CMI) framework, introduced by Steinke & Za- kynthinou (2020), has been demonstrated in recent studies (Hellström & Durisi, 2022; Wang & Mao, 2023; Laakom al., 2024) to yield practical generalization error bounds, even when W are high-dimensional and continuous.
uEC
m
ER..
(W, Rw))
2
[H((ng
S., , ,ni m m1 5,)
Su 3.
where C is the set of m-combinations.
The full proof is provided in Appendix C.4. The bound in Theorem 2 has an explicit dependency on the weights W. This dependency highlights that fairness overfitting is influenced by the extent to which the random selection process reveals information about the model's weights.
In this section. we extend our fairnes- genrreaiagennr anal- ysis using CMI with the super-sample framework. In par- ticular, we assume that there are n pairs of super-samples Zi20 = (Z) ,... Z E g i.i.d generated from Pz. The training data S- = (Z) R. Z
One approach tightening the bound in Theorem 2 is to leverage the model's predictions rather than its weights, as the f-CMI bound proposed by Harutyunyan et al. (2021). In this context, instead of directly using 1z (W; R.,), we consider the predictions F., (S(W, X9), J(W, x()).
ZR_) are selected
,R,)) E 10, is the se- lection vector composed of n independent uniform random variables. Intuitively, R, selects sample Z,R. from the super- sample Z. to be used in training, and the remaining z.R. ZR. Therefore,
from Ze2x). where R = (R.,
Theorem 3 (f-CMI bound). Assume that If E [0. 11. then
for any m E (2, 12....,77, ,n:), we have
is for the test. Let S- = (Z,, z analogous to Definition 1, we have a similar definition of fairness generalization error in the super-sample setting.
gen fairness
1
E Ezzza
Σ
(12)
C
ME
Definition 2. The fairness generalization error in the super- sample framework is:
m ER. 2
I2 (Fu; Ru)
3.
m
fairness A B Ziznn R (E(WW)) ef (W,S)) S)). (9)
where C is the set of m-combinations.
5

---

Fairness Overfitting in Machine Learning: An InformationnTheorciie Perspective
To achieve even tighter bounds, inspired by Hellström & Durisi (2022), we can incorporate the the faimesss loss pairs L. (W,, Vg), (W, V.)). This leads to the follow- ing main result established in Theorem 4.
This establishes that Theorem 5 is tighter than Theorems 3 and 4. Intuitively, the difference between AL conveys significantly less information about the se- lection process Ru, compared to the pair L..
loss values,
Theorem 4 (e-CMI bound). Assume that [/] E [0, 1]. then for any m E , .n., we have
5. Equalized Odds
gen fairness
1 [mml
BZ 2nl
Σ
(13)
In this section, we extend our general bounding framework to address fairness under separation bassedd----ad---- notion, i.e., the Equalized Odds (EO) (Hardt et al., 2016).
uEC#
m
1
BR...
I Span (Lui Ru))
2
Hn
Su Su.
m1 110"
11
Su
2
5.1. Problem Formulation for EO
where C. is the set of m- nn-cobiinatios..
Under separation-baxed fairness notion, the requirement is Y T T|Y, indicating that the predicted label Y is con- ditionally independent of the sensitive attribute T, given the true label Y. Extending our previous analysis of DP to this case introduces finer-grained faimess requirements by accounting for dependencies within each label class. In this section, we assume a binary label case, Y E {0, 1}. which is typical in EO formulations. In addition, our hypothesis W produces prediction outputs f(W, X) [0, 1].
Given Zinn). the sequence R., + W - f(W, x
L, forms a Markov chain. Therefore, by the data processing inequality, f- f-CMI bound in Theorem 3 is tighter than CMI bound in Theorem 2, and e-CMI bound in Theorem 4 is tighter than f-CMI in Theorem 3.
However, the main limitation of Theorem 4 remains its com- putational cost. Specifically, since R., is multidimensional (of size m) and L, is both continuous and multidimensional, estimating the bound becomes challenging in practice. To address this issue, we leverage the loss-difference technique proposed in (Dong et al., 2024), which reduces the dimen- sionality of both terms to one.
Comparison with DP. In the EO setting, we split samples not only by T E {0, 1} but also by Y E {0, 1}. For E {0, 1}. E {0, 1}, let ntyy = =E 1(T, = t, Y, = v}. Then the fairness empirical risk for EO can be written as
i=
To this end, we define b. {R,, + R., 1m E {0,1)"m- 1)mm,, where @ denotes the XOR operation. Given binary value b, we define b @ t. = (b. {.., @ b) ) E {0, 1m To simplify the notation, we denote 0 & P. and 1 ② 4. as o and t respectively. -
F3 E Sw - Fa S1Y FF (w, (w, S|Y (16)
where
- L L. denotes pair of losses, while A Lu. = L L denotes their difference. The main result is presented in Theorem 5. Theorem 5 (ALCMI bound). Assume that |/| E [0. 1). then for any m E (2..... ,n], we have
(| =
Σ
f(w, (17)
nooy +2
Ti=0,
1
Σ
kw,zz)
F1y +2 TEL
The BO differs from DP in its conditional requirement: DP evaluates dependence between predictions and T uncondi- tionally, while EO measures fairness by conditioning each label class Y. This distinction refines the faimesss loss to capture the influence of T on predictions within sub- populations defined by Y (a dependency reflected in the function e (W, S), which now accounts for the joint dis- tribution over both T and Y). Despite these conceptual differences, the bounding methodology remains similar, uti- lizing Lemma 2 in the context of Definition I with EO loss. We maintain the same notation and subset enumeration as in the DP setting to ensure continuity in the analysis.
gen fairness
1
EZ p2n)
Σ
(14)
1Cm
m
ER.
(AL th Rus))
HI Hlnng
Su mi 10 11]
Sa Sa 8.
where CT is the set of mn-combinations.
Given Zpa. the sequence R - (Iu, P.,) a Markov chain. Using the data processing inequality and the independence of L., and Ru,, we obtain
AL forms
Ru. RRT)) S Tappn (Imu Lui R(n)) T Tzjaw) (AL
5.2. Generalization Error Bounds for EO
Tajana (Ty; Rug (T.)
We will show that FFs (W, S) satisfies a similar bounded- differences condition as in the DP setting, but with subgroup sizes partitioned by both T and Y.
Iniina LLy Ru) - L zn) (La; D.)
5 42p (Lai R.y)
(15)
6

---

Fairness Overfitting in Machine Learning: An Information- Perspective
COMPAS (Gender): DiffDP
COMPAS (Gender): HSIC
COMPAS (Gender): PRemover
0.20
0.20
0.20
Faimess (DP)
AL CMI bound
Faimess lass (DP)
AL CMI bound
AL CMI bound
0.15
Faimess gen error
Falme gen error
0.15
Falmess gen error
Faimess loss
0.10
0.10
0.10
0.05
0.05
0.05
0.00
0.00
0.00
250
500
1000
1500
2000
2500
250
500
1000
1500
2000
2500
250
500
1000
1500 2000 2500
number of training samples
number of training samples
number of training samples
COMPAS (Gender): DiffEodd
COMPAS (Gender): DiffEopp
Scatter plots (DP) with COMPAS
0.20
0.20
0.10
Fairesss (EO)
bound
Fairesss loss (EO)
bound
con:: 0.876
0.15
Fairness gen error
0.15
Faimess gen error
Faimess loss
0.10
0.10
0.05
0.05
0.00
0.00
0.00
250
500
1000 1500 2000
2500
250
500
1000
1500
2000
2500
0.00
0.05
0,10
number of training samples
number training samples
AL-CMI bound
Figure 2. Evaluation of fairness generalization bounds the COMPAS datasct (gender sensitive attribute) a function of training set size n. Top: DP methods and corresponding bound from Theorem 5. Bottom-lef&&middllc EO methods and corresponding bound from Theorem 7. Bottom-right: Scatter plot showing the correlation between our DP bound and observed fairness generalization error. The results confirm the tightness and reliability of our bounds across different methods.
Lemma 5. Fix w E W and fixed no. 11,00 no, n1,11 Let t + R be defined as follows: g(z,,...y 7m) FF (W, ku). where FS (w, zu) is defined (16). Then, for any E
Zu Za Zu Zy
For any m E (2. m2).
gem fairness
(19)
1 S i S n, we have
1
2mLEz..
(n + 2) 2 1(W, Z.).
Cm
min
2
sup [0(2u)= s(25)1= S 2u.
(18)
min(e.g) (n +
(n
2)
Compared to the DP bound in Theorem 1, the bound in
Theorem 6 depends the smallest subgroup across both T and Y, while also capturing the dependence between W and the joint distribution of (T, Y).
where If(w, x15)l bounded by I in the binary case, and min(e.)) (Te.g 2) is the smallest subgroup size across all and y.
Theorem 7. (EO Fairness AL Bound) Assume |fl E [0, 1].
The proof is provided in Appendix D.I. Lemma employs similar bounding methodology as Lemma 3, which ex- tends the bounded-differemee
For any m E {4.-.. ,n), let
HCM = H mimn mnin(nsy)) Su) min(n(g)) (t.3)
property the EO setting. Both results are grounded in analyzing the sensitivity of the function g(-) with input perturbations to derive an upper bound that incorporates the number of subgroups. Notably, Lemma 2 remains applicable across different fairnsss mea- sures, serving as general tool for bounding sensitivity to individual sample perturbations, while adapting to distinct loss functions and partitioning structures. In the of EO, the fairness risk e is determined by the smallest (T, Y)- specific subgroup. This adaptation refines the bounded- differences property to account for the joint structure of T and Y.
(t.a)
where ming (nE.g) and min (nE,)) are the smallest subgroup sizes in t, y for the training set S, and test set S.. then
Σ
gen fairneas
E
Z:2m]
(20)
n
uECO
2m ER,
I Ippz)) (AL @
R.,.)
Remark 7. Theorem 7 quantifies the dependence between R,, and the EO loss difference (AL. via CMI, isolating T's influence on predictions given Y. More details can be found Appendix D.3.
Building on this result, we analyze the EO fairness gener- alization gap, leveraging both mutual information and loss- difference dependencies to quantify the impact of subgroup imbalances fairesss generalization error.
As we show here, the proposed bound remains valid across different subgroup structures and loss formulations, high- lighting the framework's wide applicability. Unlike DP,
Theorem (EO Fairness MI Bound) Assume |fl [0, 1].
7

---

Fairness Overfitting in Machine Learning: An Information- Perspective
where bounds depend solely on group sizes defined by T, our EO analysis explicitly accounts for the joint distribu- tion of (T, Y). As a result, the bound captures subgroup imbalances (via (yy R1,y and AL and their impact on faimess generalization errors.
relationship between our bounds and faimess generalization error, we generate scatter plots comparing the bound from Theorem 5 with the true observed DP faimess error on the COMPAS datasets. The plot, in the bottom-right corner of Figure 2, reveals that our bound exhibits a strong linear relationship with the true fairness generalization, reinforcing its reliability as an indicator of generalization performance.
6. Experiments
Batch Balancing: One of the key insights of Theorem I is the connection between faimess generalization error and group imbalance, highlighting that balancing groups in train- ing data can result in tighter generalization bounds. Moti- vated by this result, we introduce a simple batch- balanbannnn technique, where we ensure that the different groups are proportionally balanced within each training butch. In par- ticular, we sample half of the batch samples from each sensitive group (e.g., gender: Male and Female), ensuring equal representation in each batch, thereby mitigating the impact of group imbalance.
Empirical Setup In this section, we empirically assess the effectiveness of our faimess generalization error bounds. Specifically, we evaluate the bounds from Theorems 4 and 7 in the context of deep neural networks. Following Han et al. (2024), we conduct experiments using on two widely studied datasets in fairness research with gender or race used as the sensitive attribute: i) The COMPAS (Larson et al., 2016) dataset, which involves recidivism prediction based on criminal and demographic records. ii) The Adult (Kohavi & Becker, 1996) dataset, derived from U.S. Census data, which focuses on income prediction.
To evaluate the effectiveness of this technique, we conduct extensive experiments with various methods, measuring its impact on DP over unseen test data. The results, summa- rized in Table for COMPAS and Table 2 (Appendix F.3) for Adult, demonstrate that our approach consistently re- duces DP on test data across all methods for dataset sizes. Remarkably, in some cases, it decreases the error by a factor of 10, highlighting its impact on improving the performance of different fairness methods. These findings not only vali- date our theoretical results but also highlight their practical relevance in developing effective strategies for enhancing faimess in real-world applications.
We compare multiple fairness algorithms, including Em- pirical Risk Minimization (ERM), three DP in-processing approaches (Demographic Schheet-SShmidt Independence Criterion (HSIC) (Baharlouei et al., 2020; Li et al., 2022), DifIDP (Mrouch et al., 2021), and Prejudice Remover (PRe- mover) (Kamishima et al., 2012)) (0))),. as well as two EO meth- ods (DiffOdd and DiffEopp (Mroueh et al., 2021)). All approaches follow the same training protocol (architectures, hyperparameters, etc.) as in Han et al. (2024).
To evaluate our bounds, we adopt the same setup as in Haru- tyunyan al. (2021), reporting the mean and standard devi- ation over the Zrzn] realizations. The CMI terms in Theo- rems 5 and 7, which involve one discrete and one continuous variable, are estimated using the method from Ross (2)14). Additional details about the experimental setup are provided in Appendix F.I. Each data point in our experiments corre- sponds a total of 1050 runs.
7. Multiclass Extension
In this paper, our analysis mainly focuses on the binary classification setting, where the label space y = {0, 1}. In this context, we adopt the widely used group fairness criteria: demographic parity defined as P(Y T= - P T=
Bound tightness: In Figure 2, we present the fairnsss gener- alization error of models trained with different algorithms on the COMPAS dataset with gender as the sensitive attribute. The top row reports the results for different DP approaches along with our corresponding bound (Theorem 5), while the first two columns of the second row show the results for different EO approaches along with our corresponding bound (Theorem 7). As can be seen, the proposed bounds consistently capture the true fairness generalization error across the various settings. These findings validate the theo- retical results and underscore the utility of our framework in providing meaningful guarantees for fairness generaliza- tion in real-world applications. The additional results on the other datasets, provided in Appendix F.2, are consistent with these findings.
1) and equalized odds P(Ý =1 T=), P(Y=
T = 0, Y = y) for y E {0, 13. These criteria are equivalent to the notions of independence and separation, respectively, as formalized in prior work (Mroueh et al., 2021; Madras et al., 2018).
Extending DP and EO beyond binary labels to multiclass settings is nontrivial and remains an open challenge, with no universally accepted definition of the loss function. Sev- eral approaches have been proposed, including information- theoretic formulations based mutual information (Gupta et al., 2021), dependence measures such as distance correla- tion (Guo et al., 2022), and direct multiclass analogues of binary fairness criteria (Denis et al., 2021). To demonstrate the flexibility of our framework, we consider a concrete multiclass extension aligned with the definition in (Denis
Bound-error correlation analysis: To further analyze the
8

---

Fairness Overfitting in Machine Learning: An Information-Theone Perspective
Table 1. Effect of hatch balancing on DP errors with the COMPAS dataset. We report DP test data for various approaches, with and
without our proposed balancbalnncing strategy. The results show that balancing consistently reduces DP by an order of magnitude. This empirically supports the theoretical insights of Theorems regarding the role of group imbalance in faireess generalization error.
sensitive attribute: gender
sensitive attribute: race
250
500
1000
1500
2000
2500
250
500
1000
1500
2000
2500
DiffDP
0.056
0.044
0.035
0.028
0.025
0.026
0.053
0.037
0.026
0.020
0.017
0.017
DiffDP (ours)
0.042
0.025
0.009
0.005
0.003
0.003
0.045
0.024
0.011
0.007
0.006
0.005
HSIC
0.101
0.098
0.101
0.099
0.097
0.098
0.088
0.072
0.062
0.056
0.055
0.055
HSIC (ours)
0.059
0.044
0.022
0.016
0.010
0.008
0.069
0.048
0.027
0.022
0.018
0.016
PRremover
0.128
0.134
0.138
0.137
0.137
0.136
0.159
0.162
0.154
0.149
0.150
0.151
PRremover(ours)
0.106
0.119
0.125
0.126
0.126
0.126
0.144
0.149
0.147
0.142
0.143
0.142
et al., 2021), showing that our proof technique is general and easily extends to more complex output spaces.
obtained in this case. Interestingly, the value of a, i.e., the number of classes, does not affect (24) and the final bound. The key point is that, even if the prediction function f is allowed to take any value in [0, a]. changing one sample affects the probability estimates (and hence the TV loss) by at most a fixed amount (i.e., at most 1) regardless of a. In other words, while f's output may be scaled by a, the impact on the faimess loss (measured in terms of probability differences) remains unchanged.
In the multiclass case, the predictor 9 = f(w; maps into a broader output range, specifically [0, a] rather than {0, 13. the context BO, consider our use the Total Variation (TV) loss as a fairness measure to quantify the difference between prediction distributions conditioned on different labels. Specifically, we use y' {0. 2,3) demonstration.
For each true label y E {0, 1,233, we define the TV loss as follows:
8. Conclusion & Future Work
Our thcoretical analysis of fairness generalization reveals key interactions between sensitive group imbalances, model capacity, and fairness overfitting through MI and CMI bounds. Additionally, introduce new variance-biie based bounding technique using Efron-Stein incquality that im- proves upon traditional sub- Gabssannii assumptions, leading to tighter results. Empirical evaluations validate both the effectiveness and tightness of the proposed bounds.
3 Σ
f (W,S Y=y) =
P(Y= c Y y=y,T=0)
c=0
- -P(Y =c Y v. T
(21)
which, in practice, can be approximated by
Crucially, our framework provides unified approach for an- alyzing concentration properties across different loss struc- tures. By leveraging Lemma 2 and Hocffding's 's lemma, we ensure that the variance is bounded by sensitivity to indi- vidual sample perturbations. Integrating variance control with information-theoreii mutual information bounds, our framework provides guarantees for generalization across various fairness criteria. This demonstrates the wide appli- cability and the potential of our bounding approach.
E (W.)) Y y) Σ
no.ycc
n1.ycc
No.y
+2
N1y +
(22)
Here, nigge Ei= LTT, = Y, Y c) counts the number of specific pairs in the training data.
We then define an aggregate function over the true labels:
9 (Z.)) = Σ
Es [W, Zu |rmY = v). (23)
E
2E(0.
Future work could involve extending our theoretical frame- work to cases where the sensitive attributes are non-binary sensitive attributes or continuous. Another potential direc- tion is leveraging our bounding techniques in other contexts that have similar challenges, i.e., grsep- non-i.i.d loss functions.
Based on this multi-class extension of the EO loss, similar to the proof of Lemma 5, we can establish the following
2
sup (g(2u) -0(-)) St
(24)
min [ + 2}
Thus, our technical arguments extend naturally to the multi- class setting, and similar bounds to Theorems 6 and can be
9

---

Fairness Overfitting in Machine Learning: An Information- Information-Thhoreti Perspective
Acknowledgment
Calmon, F,, Wei, D., Vinzamuri, B., Natesan Ramamurthy,
K., and Varshney, K. R. Optimized pre- pre-processing for dis- crimination prevention. Advances in neural information processing systems, 30, 2017.
The research reported in 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.
Chen, Q.
Shui, C., and Marchand, M. Generalization bounds for meta-learning: An information-theerrtic anal- ysis. Advances in Neural Information Processing Systems, 34:25878-2588 2021.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which feel must be specifically highlighted here.
Chen, Y., Raab, R., Wang. J., and Liu, Y. Fairness transfer- ability subject to bounded distribution shift. Advances in neural information processing systems, 35:11266-11278. 2022.
References
Chouldechova, A. Fair prediction with disparate impact: study of bias in recidivism prediction instruments. Big data, 5(2):153-1633 2017.
Agarwal, A., Beygelzimer, A., Dudík, M., Langford, J., and Wallach, H. A reductions approach to fair classification. In International conference on machine learning, pp. 60- 69. PMLR, 2018.
Corbett-Davies S., Pierson, E., Feller, A., Goel, S., and Huq, A. Algorithmic decision making and the cost of fair- ness. Proceedings of the 23rd aem sigkdd international conference knowledge discovery and data mining, pp. 797-806. 2017.
Alabdulmohsin. I. Towards unified theory of learning and information. Entropy, 22(4))438, 2020.
Alghamdi, W., Hsu, H., Jeong, H., Wang, H., Michalak, P., Asoodeh, S., and Calmon, F. Beyond adult and compas: Fair multi-class prediction via information projection. Advances in Neural Information Processing Systems, 35: 38747-38760, 2022.
Coston, A., Ramamurthy, K. N., Wei, D., Varshney, K. R., Speakman, S., Mustahsan, Z., and Chakraborty, S. Fair transfer learning with missing protected attributes. In Proceedings of the 2019 AAAI/ACM Conference AI, Ethics, and Society, pp. 91-98, 2019.
Aminian, G., Bu, Y., Toni, L., Rodrigues, M., and Wornell, G. An exact characterization the generalization enror the gibbs algorithm. Advances in Neural Information Processing Systems, 34:8106-81 18188-8188, 2021.
Darbellay, G. A. and Vajda. I. Estimation of the information by adaptive partitioning of the observation space. IEEE Transactions Information Theory, 45(4):1315-1321, 1999.
Baharlouei, S., Nouiehed, M., Beirami, A., and Razaviyayn, M. R enyi fair inference. In International Conference on Learning Representations, 2020.
Denis, C., Elie, R., Hebiri, M., and Hu, F. Fairness guarantee in multi-class classification. arXiv preprint arXiv:2109. 2021.
Barocas, S., Hardt, M., and Narayanan, A. Fairness and machine learning. fairmlbook. org, 2019.
Dong, Y., Gong, T., Chen, H., He, Z., Li, M., Song, S., and Li, C. Towards generalization beyond pointwise learning: A unified information -theoretic perspective. In Forty-first International Conference on Machine Learning, 2024.
Biswas, A. and Mukherjee. S. Ensuring fairness under prior probability shifts. In Proceedings of the 2021 AAAI/ACM Conference AI, Ethics, and Society, pp. 414 424, 2021.
Doob, J. L. Regularity properties certain families of chance variables. Transactions of the American Mathe- matical Society, 47(3):455 486, 1940.
Boucheron, S., Lugosi, G., and Massart, P. Con-
centration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013.
Dwork, C., Hardt, M., Pitassi, T., Reingold, O., and Zemel, R. Fairness through awareness. In Proceedings of the 3rd innovations theoretical computer science conference, pp. 214-226, 2012.
doi:
10. 10.1099/appproo//7770993333300.3
URL
http::////oi.o01111..1911.. os0/ 777780999535255.00111
Bu, Y.. Zou, S., and Veeravalli, V. V. Tightening mutual information- based bounds on generalization error. IEEE Journal on Selected Areas in Information Theory, 1(1): 121-130, 2020.
Gao, W., Kannan, S., Oh, S., and Viswanath, P. Estimat- ing mutual information for discrete-continuon mixtures. Advances in neural information processing systems, 30, 2017.
10

---

Fairness Overfitting in Machine Learning: An Information-Thoowe Perspective
Giguere, S., Metevier, B., Brun, Y., Da Silva, B. C., Thomas, P. S., and Niekum, S. Faimess guarantees under demo- graphic shift. In Proceedings of the 10th International Conference on Learning Representations (ICLR), 2022.
European Conference, ECML PKDD 2012, Bristol, UK, September 24-28, 2012. Proceedings, Part II 23, pp. 35-50, Springer, 2012.
in Dutabases:
Kleinberg. J., Mullainathan, S., and Raghavan, M. Inherent trade-offs in the fair determination of risk scores. arXiv preprint 16Xiv: 00800, 2016.
Guo, D., Wang, C., Wang, B., and Zha, H. Learning fair rep- resentations via distance correlation minimization. JEEE Transactions Neural Networks and Learning Systems, 35(2):213-2152, 2022.
Kohavi, R. and Becker, B. Adult data set. UCI machine learning repository, 5:2093, 1996.
Gupta, U.. Ferber, A. M., Dilkina, B., and Steeg, G. V. Controllable guarantees for fair outcomes via contrastive information estimation, 2021. URL https: / /arxiv. org/ hts//bs/220 /201. 04108.
Kraskov, A., Stögbauer, H., and Grassberger, P. Estimat- ing mutual information. Physical Review E Statistical, Nonlinear, and Soft Matter Physics, 69(6):06118, 2004,
Laakom, F., Bu, Y., and Gabbouj, M. Class-wise general- ization error: an information-theoree analysis. arXiv preprint arXiv:2401.0290 2024.
Han, X., Chi, J., Chen, Y., Wang, Q., Zhao, H., Zou, N., and Hu, X. Ffb: A fair fairness benchmark for in pr-processing group fairness methods. In International Conference on Learning Representations, 2024.
Larson, J., Mattu, S., Kirchner, L., and Angwin, J. Prop- daty
ublica compas analysis- data and analysis for 'machine bias.'. https:/ggithu. con/ppopublic/ccmppsssnndy 2016.
Hardt, M., Price, E., and Srebro, N. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29, 2016.
Harutyunyan, H., Raginsky, M., Ver Steeg, G., and Galstyan, generalization bounds for black- box learning algorithms. Advances in Neural Information Processing Systems, 34:24670-24682. 2021.
Lee, J., Bu, Y., Sattigeri, P., Panda, R., Wornell, G., Karlin- sky, L., and Feris, R. A maximal correlation approach to imposing fairness in machine learning. In ICASSP 2022 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3523-3527. IEEE, 2022.
A.
Harvey, N., Liaw, C., and Mehrabian, A. Nearly-tight ve- dimension bounds for piecewise linear neural networks. In Conference on learning theory, pp. 1064-1068. PMLR, 2017.
Lee, J. K., Bu, Y., Rajan, D., Sattigeri, P., Panda, R., Das, S., and Wornell, G. W. Fair selective classification via suffi- ciency. In International conference on machine learning, pp. 6076-6086. PMLR, 2021.
Hellström, and Durisi, G. new family of generaliza- tion bounds using samplewise evaluated emi. Advances in Neural Information Processing Systems, 35:10108- 10121, 2022.
Li, P. and Liu, H. Achieving fairness no utility cost via data reweighing with influence. In International Confer- ence on Machine Learning, pp. 12917-12930. PMI., 2022.
Huang, R. and Liu, H. Bridging fairness gaps: A (condi- tional) distance covariance perspective in fairness learn- ing. arXiv preprint arXiv:2412.00720. 2024.
Li, Z.,, Pérez-Suay, A., Camps G., and Sejdinovic, D. Kernel dependence regularizers and gaussian pro- cesses with applications to algorithmic faimess. Pattern Recognition, 132: 108922, 2022.
Jiang, R., Pacchiano, A., Stepleton. T., Jiang, H., and Chi- appa, S. Wasserstein fair classification. In Uncertainty in artificial intelligence, pp. 862-872. PMLR, 2020.
Madras, D., Creager, E., Pitassi, T., and Zemel. Learning adversarially fair and transferable representations, 2018. URL https: arxivv.vvvv/ .wweiiiioorr/ooooooo wwwooogg/bb....oooooooo 1t1//180..000 06309.
Jose, S. T. and Simeone, O. coormatiiontthoreetee gen- eralization bounds for meta-leaming and applications. Entropy, 23(1):126, 2021.
Mehrabi, N., Morstatter, F., Saxena, N., Lerman, K., and
Kamiran, and Calders, Data preprocessing techniques for classification without discrimination. Knowledge and information systems, 33(1):1-33, 2012.
Galstyan, A. survey on bias and fairness in machine learning. ACM computing surveys (CSUR), 54(6):1-35, 2021.
Kamishima, T., Akaho, S., Asoh, H., and Sakuma, Faimess-aware classifier with prejudice remover regu- larizer. In Machine Learning and Knowledge Discovery
Mehrotra, A. and Vishnoi, N. Fair ranking with noisy pro- tected attributes. Advances in Neural Information Pro- cessing Systems, 35:31711-31725, 2022.

---

Fairness Overfitting in Machine Learning: An Information- Information-Thhorcii Perspective
Modak, E., Asnani, H., and Prabhakaran, V. M. Rényi divergence based bounds generalization error. In 2021 IEEE Information Theory Workshop (ITW), pp. 1-6. IEEE, 2021.
Shah, A., Bu, Y., Lee, J. K., Das, S., Panda, R., Sattigeri, P., and Wornell, G. W. Selective regression under fair- ness criteria. In International Conference Machine Learning, pp. 11598-196111 PMLR, 2022.
Mroueh, Y. et al. Fair mixup: Fairnsss via interpolation. In International Conference on Learning Representations, 2021.
Sharifi-Malvjjeddi, S., Kearns, M., and Roth, A. Average individual fairness: Algorithms, generalization and ex- periments. Advances in neural information processing systems, 32, 2019.
Neu, G., Dziugaite, G. K., Haghifam, M., and Roy, D. M. Information-theorete generalization bounds for stochas- tic gradient descent. In Conference on Learning Theory, pp. 3526-334233 3345. PMLR, 2021.
Shui, C., Chen, Q. Wen, J., Zhou, F., Gagné, C., and Wang, B. Beyond b-divergence: Domain adaptation theory with jensen- divergence. arXiv preprint FrXiv:2007.15560 6, 2020.
Oneto, L., Donini, M., Pontil, M., and Maurer, A. Learning fair and transferable representations with theoretical guar- antees. In 2020 IEEE 7th International Conference on Data Science and Advanced Analytics (DSAA), pp. 30-39. IEEE, 2020a.
Shui, C., Xu, G., Chen, Q., Li, J., Ling, C. X., Arbel, T., Wang. B., and Gagné, C. On learning fairness and accu- racy on multiple subgroups. Advances in Neural Informa- tion Processing Systems, 1133112--3135,,, 2022.
Oneto, L., Donini, M., Pontil, M., and Shawe-Taalor, J. Ran- domized learning and generalization of fair and private classifiers: From pac-bayes to stability and differential privacy. Neurocomputting. 416:231-243: --33,, 2020b.
Singh, H., Singh, R., Mhasawade, V., and Chunara, R. Fair- ness violations and mitigation under covariate shift. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, pp. 3-13, 2021.
Pessach, D. and Shmueli, F. review on fairness in machine learning, ACM Computing Surveys (CSUR), 55(3):1-44, 2022.
Sontag, D. et. Ve dimension of neural networks. NATO ASI Series F Computer and Systems Sciences, 168:69-96. 1998.
Pham, T.-H., Zhang. X., and Zhang, P. Fairness and accuracy under domain generalization. ArXiv, 2023.
Steinke, and Zakynthinou, L. Reasoning about general- ization via conditional mutual information. In Conference on Learning Theory, pp. -452. PMLR, 2020.
Rezaei, A., Liu, A., Memarrast, O., and Ziebart, B. D. Ro- bust fairness under covariate shift. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 9419-9427, 2021.
Tang, Z. and Zhang. K. Attainability and optimality: The equalized odds faimess revisited. In Conference on Causal Learning and Reasoning, pp. 754-786. PMLR, 2022.
Rezazadeh, A., Jose, S. T., Durisi, G., and Simeone, O. Con- ditional mutual information-basee generalization bound for meta learning. In 2021 IEEE International Sympo- sium on Information Theory (ISIT), pp. 1 1176-1181. IEEE, 2021.
Wang, H., Gao, R., and Calmon, F. P. Generalization bounds for noisy iterative algorithms using properties of additive noise channels. J. Mach. Learn. Res., 24:26-1, 2023.
Wang. Z. and Mao, Y. On the generalization of models trained with sgd: Information--theorrtiic bounds and im- plications. arXiv preprint arXiv:2110.033228 2021.
Rodríguez Gálvez, B., Bassi, G., Thobaben, R., and Skoglund, M. Tighter expected generalization error bounds via wasserstein distance. Advances in Neural Information Processing Systems, 34:19199-19121, 2021.
Wang. Z. and Mao, Y. Tighter ieformationnthhoredee gen- eralization bounds from supersamples. arXiv preprint urXiv:2302.02432. 2023.
Ross, B. C. Mutual information between discrete and con- tinuous data sets. PloS one, 9(2):887357, 2014.
Woodworth, B., Gunasekar, S., Ohannessian, M. I., and Srebro, N. Learning non-diseriminatory predictors. In Conference on learning theory, pp. 1920-1953. PMLR, 2017.
Ruggieri, S., Alvarez, J. M., Pugnana, A., Turini, F., et al. Can we trust fair-ai? In Proceedings of the AAAI Con- ference on Artificial Intelligence, volume 37, pp. 15421- 15430, 2023.
Wu, Manton, J. H., Aickelin, U., and Zhu, J. Information- theoretic analysis for transfer learning. In 2020 IEEE International Symposium on Information Theory (ISIT), pp. 2824. IEEE, 2020.
Schumann, C., Wang, X., Beutel, A., Chen, J.. Qian, H., and Chi, E. H. Transfer of machine learning fairness across domains. arXiv preprint arXiv: /906:900.000 09688, 2019.
12

---

Fairness Overfitting in Machine Learning: An Information- Theooreti Perspective
Wu, X., Manton, J. H., Aickelin, U., and Zhu, J. On the gen- eralization for transfer learning: An information-theoreiiic analysis. IEEE Transactions Information Theory, 2024.
Xu, A. and Raginsky, M. Information-theorele analysis of generalization capability of learning algorithms. Ad- vances in Neural Information Processing Systems, 30, 2017.
Yoon, T., Lee, J., and Lee, W. Joint transfer of model knowledge and fairness over domains using wasserstein distance. IEEE Access, 8: 8:123783-
2020.
Zafar, M. B., Valera, I., Rogriguez, M. G., and Gummadi, K. Fairness constraints: Mechanisms for fair classifica- tion. In Artificial intelligence and statistics, pp. 962-970. PMLR. 2017.
Zemel, R., Wu, Y., Swersky, K., Pitassi, T., and Dwork, C. Learning fair representations. In International conference on machine learning, pp. 325-333. PMLR, 2013.
Zhou, R., Tian, C., and Liu, T. Individually conditional individual mutual information bound on generalization eтror. IEEE Transactions on Information Theory, 68(5):
3304-3316, 2022.
Zhou, R., Tian, C., and Liu, T. Exactly tight information- theoretic generalization error bound for the quadratic gaussian problem. arXiv preprint arXiv:2305.008: 2023.
13

---

Fairness Overfitting in Machine Learning: An Sefformation-Thcortiiee Perspective
A. Extra Related Work
Information-theoree Bounds: Information- theorretic bounds have gained significant attention in recent years for charac- terizing the generalization behavior of learning algorithms (Neu al., 2021; Wu et al., 2020; Modak et al., 2021; Wang & Mao, 2021; Shui al., 2020; Wang et al., 2023; Alabdulmohsin, 2020). In the context of supervised learning, various generalization error bounds have been proposed, utilizing different information measures, such as KL divergence (Laakom et al., 2024; Zhou et al., 2023), Wasserstein distance (Rodríguez Gálvez et al., 2021), and mutual information between the samples and model weights (Xu & Raginsky, 2017; Bu et al., 2020). More recently, it has been demonstrated that tighter generalization bounds can be derived using conditional mutual information (CMI) (Steinke & Zakynthinou, 2020; Zhou et al., 2022). Building on this framework, Harutyunyan et al. (2021) introduced f-CMI bounds based on model outputs. Additionally, Hellström & Durisi (2022) proposed tighter bounds leveraging CMI of the loss function, further improved by Wang & Mao (2023) through the use of AL CMI. An exact characterization of the generalization error for the Gibbs algorithm is provided in (Aminian et al., 2021). Beyond standard supervised settings, have been used to study contrastive learning (Dong et al., 2024), meta-learning (Chen et al., 2021; Jose & Simeone, 2021; Rezazadeh et al., 2021), transfer learning (Wu et al., 2020; 2024), and class- class-eenrralization error (Laakom et al., 2024).
cettmmmtttooottorettte bounds
Algorithmic Fairness: Ensuring fairness in machine learning has become a critical area of research, aiming to mitigate biases that may disadvantage certain individuals or groups. Fairness is broadly categorized into group faireess (Dwork et al., 2012; Hardt et al., 2016; Corbett-Daviee et al., 2017), which seeks to ensure equitable treatment across predefined demographic groups, and individual fairness (Dwork et al., 2012: -Mariii-Malvajerdii al., 2019), which enforces the principle that similar individuals should receive similar predictions. Bias mitigation strategies are typically classified into three approaches: pre-processing methods that modify the data before training (Kamiran & Calders, 2012; Calmon et al., 2017),, post-processing approaches that adjust model predictions after training (Hardt et al., 2016; Jiang et al., 2020), and in-processing techniques, the main focus of this paper, that integrate faimess constraints within the learning algorithm (Kamishima et al., 2012; Baharlouei et al., 2020; Mrouch et al., 2021; Lee et al., 2021; 2022; Shah et al., 2022: Alghamdi et al., 2022; Shui et al., 2022; Mehrotra & Vishnoi, 2022).
Fairness Theory: In the theoretical analysis of fairness, prior works have primarily focused on the context of domain adaptation, imposing strong assumptions distributional shifts (Chen et al., 2022; Singh et al., 2021; Coston et al., 2019; Rezaei et al., 2021). For instance, several studies have considered faimess under covariate shifts (Singh et al., 2021; Coston et al., 2019; Rezaci et al., 2021). demographic shifts (Giguere et al., 2022), and prior probability shifts (Biswas & Mukherjee, 2021). However, these assumptions may not always hold in real-world scenarios, limiting their practical applicability (Chen et al., 2022: Singh et al., 2021; Coston et al., 2019; Rezaei et al., 2021; Oneto et al., 2020a; Schumann et al., 2019; Yoon et al., 2020). Beyond domain adaptation, Pham et al. (2023) provides a theoretical analysis of invariant representation learning for domain generalization, establishing upper bounds on both prediction error and unfairness in terms of the Jensen-Shannon (JS) distance. Additionally, Huang & Liu (2024) investigates the convergence rate between empirical and population-level conditional distance covariances, which measure the statistical dependence between model predictions and sensitive attributes. In this paper, we study different problem, i.c., fairness overfitting in a supervised learning setting, and derive nnformation-thhorell bounds for generalization errors of different fairness losses. Another line of research has focused on the impossibility of satisfying multiple group-level fairnsss criteria simultaneously Chouldechova (2017); Kleinberg et al. (2016); Tang & Zhang (2022), highlighting the fundamental trade-off's between different fairness notions. In contrast to these impossibility results, which establish lower bounds on population-level fairness risk, our work provides upper bounds on fairness generalization error. Notably, model can have low generalization error but still perform poorly in terms of fairness on the population level.
Fairness Generalization: In the context of fairness generalization, it is worth highlighting the work of Woodworth et al. (2017) and Agarwal et al. (2018), which derive generalization guarantees for loss functions corresponding to DP and EO within specific algorithms. In contrast, our work targets a more general algorithmic framework in the DP and EO setting, accommodating wider range of loss functions. Moreover, while their analysis primarily focuses on overall sample complexity, our bounds account for additional factors, including properties of the learning algorithm, the choice of loss function, dataset characteristics, and, importantly, the group balance in the data. A more closely related work is that of Oneto et al. (2020b), which derives generalization bound (Theorem 1) for fairness under randomized algorithms. However, their KL-divergence-baat Theorem 5, are computable even for modern deep neural networks. This makes our results not only theoretically sound but also practically applicable, enabling the study of fairness generalization in real-world scenarios.
bound is not computable in practice for realistic settings. In contrast, our bounds, particularly
14

---

Fairness Overfitting in Machine Learning: An sefformation-Thcordeee Perspective
B. Proofs of the Theorems/Lemmas in Section 3
This appendix includes the proofs of the results presented the main text Section 3.
Lemma 6. Let X be a bounded random variable, i.e., X E [a, b] almost surely. lfE[X] - 0, then X is (b -0--0 --suuggauussinn and we have:
B Se ses5
V.ER.
(25)
Lemma 7. (Efron-Stein Inequality) (Boucheron et al. (2013, Theorem 3.1)) Let X2....... Xn be independent random variables, and let Z [((1,, X2,..., be real-valued square square-integrable function of these variables. For each i, let X3 be independent copy of X,, and define for every
E f(X1, 1 X
X,).
(26)
Then, the variance of = f(X,, Xn) satisfies the following inequality:
n
Var Z S
Σ [Z z,)
inf Zi
E
[Z ].
(27)
where the infimum is over Z; = (
X1-1, 11+11,11.... X(+1..... X,) the class of all measurable functions x==1 + R.
B.1. Proof of Lemma
Lemma 2 (restated) Let g (V) = 9(V, V....., Vn) be real-valued function of m i.i.d random variables. Given fixed
V (UI,..., Um) and an index & (l,... .... define गن = -.,,...,,,, such that ūy = U for all j # except on i, i.e., 0 # uy. If g(v) satisfies the following condition for a fixed nă (and as a consequence ni = m m²))
(ø(v) 9( S B, 1 1sism.
(28)
vE BLev
where 3 is random variable that may depend n and hence is random variable. Then, we have
Var(g(V)) s ETS.
(29)
Proof. We will use Efron-Stein inequality in Lemma 7 to show this result. Using the Lemma statement on g ((V), we have
Var(g(V)) inf
(Q(V)) - 9: (V...........................( Vi-1 V4i Vnn)²²
(30)
where gi is an arbitrary function. Using the law of total expectation in (30), we have
m
Var(g(V)) & inf 9t
Σ R
(g(Vn) ge (V....... V Vi+i.... Vn)) Vnn))'nn
(31)
V we have also n V m mo V is fixed. As this is true for any arbitrary depending on (Vi...., Vi-1, V......., Vn), we select
Note that by conditioning no
1
gi( V....., Vi-1, V41. Vm)
sup g(V1..... Vi-1, Vii..... Vn) =fEx
(32)
2
+ inf g(V I,..., Vi- Vish..., Vm)) x
(33)
Hence, in the inner expectation in (31), ny and ny are fixed, using the main condition, we have
lg( V) (V....... V.- V4L..... V.nil < 2
(34)
15

---

Fairness Overfitting in Machine Learning: An Information- Thecoootei Perspective
Taking the square both sides,
(g(V)- -P: g. Vi-1, Viti...., vm))) = 7 32
(35)
Replacing the inner expectation in (31), we have
Var(o(V)) S
Σ
B
- 8d) = m
B13
(36)
4
C. Proof of the Theorems/Lemmas in Section
C.1. Proof of Lemma 3
Lemma 3 (restated) Assume that Ifl [0, 1]. let g Vm + R be defined as g(v) = (V1,...... um)) = (ww v). where
oF (ww v) is defined (I), Then, for a fixed w E W and fixed nž and nj, for any 1 S S m, we have
sup Ve VVV
(9(v) g(0')
(37)
H(ng, m4)
where IiI denotes shifted harmonic mean operator, i.e., V(ai H(aa, ".)
.xk)
Proof. For 1 S i S m, we have
1ø(u) - g0(0)) =
f(w,z,)
Σ f(w,zz)
(38)
11i +2 T==1
T==0
f(w,ūz)
f(w,ū;))
(39)
R1 +2 T,=0
ni +2 F==1
[10,
[w,
(40)
n 2
ni + T==1
===0
(1, +
Σ f(w,ūz)
(41)
+2 T,=0
n +2
T,=1
where the inequality comes from the fact ||.1- 1. 11 < ... Furthermore, as ūg = nj for all j * i, based on the values of t and E, we have 4 different cases:
case 4 = i, = 0: In this case, we have n. = ng n = n and f(u,, [ww 3, # Hence, based on (41),
we have:
1
1
l0(2) g(0t) <
ni + fw.,zs)
ni + 2 fw, 5::1
(42)
1
n + 2 lf xi)
-(w, xz:) S
(43)
n + 2
2nd case t, = = 1: Similar to the previous case, we can show that
1
IØ(e) g(o') < n 2
(44)
16

---

Fairness Overfitting in Machine Learning: An Information-Theone Perspective
3rd case 1, = 0, 1: In this case, we have ng ng 1, ni = ni + 1. Hence, we have:
(g(z) - -
1 xg)
1
Σ
fw,
(45)
"o +
ni +2
T,=0
Ty=1
Σ
f(w, 23)) +
Σ f(w,
(46)
nó +
ni +3
3
Tz=0
T3=1
1
Σ
f(w,zz) +
1
1
Σ
f(
ni + 2
ni +
ni +3
+
0=
1z=1,ii
Rz) +
I (w
(47)
n + 2
mi + 3
-1
Σ (w,
E )w,
+ (ni + 3) + 2)
(nß + +2) + 1)
f5=1,iti
+ ni + 2
fwW, xz) + ni + 3
f(w, 2t)
(48)
1
[ (w, x4)
1
Σ Sw,
(49)
ni + 2
(ng + 2)(n + 1)
0.
f
f(, xii
1
Σ
f(u, 2;)
11 + 3
(np - (n² + +2)
(==1,
1
(w;zz)
1
Σ f(w,zz)
(50)
n5 + 2
(ng + 2) + 11
10=0,izi
nē +3 3 s(u, Ri)
1
1
Σ f(w,,))
(nf + () + +2) 1-=1f
(51)
where the last inequality comes from the fact that 11-1-1-11 S -. Next as f(w, E [0, 1] is positive, we have:
((0))
S max
'i + 2 f(w, 2i); (nō + (n + 1) 1==0
Σ (ww22))
+ max
+ 3 [w, Tii: (nf + () +2)
Σ
[w
(52)
1,=1,
< max
Σ 1)
nn + 2' (nğ + 2n + 1)
1, 1,=0.iti
+ max
Σ
(53)
np + 3' (np + 3)(F + 2)
11=1,s
n/ + 2' (no + 2)(nn + 1) (nō -1)
max
+ max
n 33' (nf + 3) +2) (nj -1))
(54)
As, Vny, ny. we have
-1 mg 1
I 1 and
< 1. Hence, we have from (54),
nf+2 +2
1
lg(l) - g(
S max
+ max
(55)
n2 +
2 n6 +2
n"
+3'
n² +
1
1
1
1
5
(56)
ni +
n
+3
n
+
2
ni + 2
17

---

Fairness Overfitting in Machine Learning: An Information-Thhoreie Perspective
4th case 1, 1,4, 0: Similarly, can show that
1
Ig(v) g( - no
+
(57)
+3
ni
+
2
+
n1 + 2
Hence, using the cases discussed above, for a fixed we always have
1
(g(v) g(ū')
1sis m
(58)
n6 +2
"i +
For fixed nă and ni, taking the supremum with respect v, 8t in both sides of (58), have
sup "e stev
(g(u) g(8') -
ni +2 +
1 5 i n
(59)
ni +
which completes the proof.
C.2. Proof of Theorem
Theorem (restated) Assume that [fl E [0, 1], then for any m (2.....1))
gen
fairness
Cm
Ev V
n1
+2
+2
(60)
where C% is the of m-combinations.
Proof. Let m nu} be fixed number and let pm be the of m-permutations of For fixed pm the
corresponding (w, Zw) for the set Zu pmth is follows:
(w, (w, Zw)=
A
E - ni + Ti=1
Σ
f(w,x:)
(61)
Vn
no
+
T:=0
Then, using the notion of (W, Z.), starting from Definition we have:
gen fairness
P Ps (W. S)] - E (WW
(62)
EPW 2. L W, Zw)]
Σ
Epw 2. (W, Zw)]
(63)
Pmn
ue Pm
EPw.Z. Z
W. Zw.]]
Epw [C (W, Zw]]
(64)
pm
Hence, to bound gen fairness. we only need to bound E
Pwz.
IE W. Zwn) Erwzz z. (
(W Zw)]
Using the Varadhan variational representation the relative entropy, we have for any function h(.) and for every
T(W, V.) 2 Brw,v, (A( V.)] log E Erwony (
(65)
By taking h(w, v,)) = Ef (w, v.) - E (f V.))
1(W, V.) ZEA.. (WW v.)) - log E P Powpy (e (.WW.... VA E.
(66)
1(W, V.) BEAW..
A(CE(W V.) - Ep. 16 W V..I))
log -lggE ERRER XCE(W.V..)
F/ (W. F.)l W. V.
(67)
ZEA N. (( - E (W W. Vw]l)
Pp BRv. [e Ve - 16 V.
Y W - Y.
(68)
18

---

Fairness Overfitting in Machine Learning: An Information- Perspective
A (w. V.) B.y. l (V((w,V)) (o)() To this end, we want to bound the variance of Next, for fixed w, will bound E E (e (g, V.) -Byy (w, V.).. As Var + 5) = Var(X), Vs E sRt and (w Vu) is constant for fixed w, we have
Var ( V.)) BIE V.)l) - Var Var(eE(w, V.))
(69)
Hence, it is sufficient to bound the variance (ww, Vu). We will use the results of Lemma 3 and Lemma 2 to upper bound the aforementioned variance.
As lf] E [0, 1]. we have
fww, Vn) = 1 Σ
fi,
1 n1 + 2 7;=1
Σ
f(w, x.))
S max
1
Σ 7:=0
f(w, r.))
Σ
s(w, ((w,
n1o + 2 T;=0
no
+ 2
m1 + 2
T;=1
(70)
I max
71g
11
S max (1, =1
(71)
110 + 2' n +2
Hence, E(w, vn) is bounded and therefore square-integrable. Applying Lemma 3 with g(v))) = E(w, vn), we have for fixed w. no
sup (9(www - g(tt)) S V. Fu VH B.EV
+
isisn
(72)
no
+2
n1 +2
Vn
Hence, g(v.)) = E(w, u.)) verifies the condition in Lemma with B of the random variable (w, V can be bounded as
Thus, using Lemma 2, the variance
no
+2
nj
Varlfg(w, Vo)) <
m B[( V
(73)
V
11
4
11
+
for every w E W. Thus, from (69).we have
Var (e V.,)
Ele V.)I) Var w. V.)) S
m
El(
)21
(74)
4
V +
n1
V.
+2
So. the random variable (w, V.) El (w, (w, V.)] has bounded variance and expectation Epy, (L Vu) (w, Vw)ll = O. Hence, using Hoeffding's lemma, we have for every w E W:
22m E|(
E V. Aehhi V.)- l6 (o [.]ll Se
(75)
Replacing in (68), have
I(W, Vo) EPW.V.
(WE V.) ER [8E (W Vw)l)
22 -y 12 n. / 12
log Epw
W = w VA
(76)
1(W, V.) > Epw.V. ((E V.) - E
If (W, V Vw)l)
13m E[(
1
1
+
V..
(77)
no
+2
n +2
where the last inequality comes from the fact that {
+ ni
)2 is independent W. From (77), we have
ng
+2
22m m
1 - 2
(Erw.v.
[C, V.) +I(W, R.
-EW E...... I V.)))
8
n
V
+
n1 Vo
+ 2
(78)
19

---

Fairness Overfitting in Machine Learning: An Cepermattion-hhoreee Perspective
So, the parabola (with respect to X) the left side of (78) is always positive. Hence, its discriminant must be negative:
E Pw Zu le W. Z..]
E PPw.2.
Le W. Z.))
m V 2
E[
1
/ V.))
(79)
no
+2 2
n1 +
Vu
Replacing (64), we have
gen fairness
V
V
/ V.))
(80)
11
ac
In addition, mutual information is invariant sample permutations, we have
gen
fairness
C
acC
m
EI
n0
+
11
+
(W V.))
(81)
where C is the set of m-combinations.
C.3. Proof Lemma 4
Lemma (restated) AA E R, we have
2
E R. Zaa)) W=w L
Se
Su
"1
P0
(82)
Proof. we will bound log ER., [2ann) Fpo W W- ( (.,(, by bounding its variance using Lemma and Lemma 2.
Given a fixed 2[2n] E 2 and w E W, we define Izgei : v - R as follows: I (R.) = lfww, S.) (w, S.). Furthermore, given set ra = (r1,..., Tm) and an index i {1.....m} m), define ft, = (fi,...., Fm)) such that i, = rj for all j f i except on i, i.e. Fz # ry. The goal is to upper-bound 19ach (Fu) - Impm (Fw) for i E {l,.... m}.
For E m)], we have
Mapan (ra) - O2gan) (Fa) (w Sw) - (E (w) E. Su) + (E S.)l
(83)
< E (w, S.) - (w, 3w)l + (w, Sw) - (w, 3w)l
(84)
Hence, we can bound each term separately using Lemma 3. It follows that:
19 (rw) - 9mpm (F S
(85)
T2g
Su
2
11
S.
+
11
3
11
3.
+ 2
(86)
Hence we have
19mpm1 (Tw) 92pm) (Fi)
+
1 15 m
(87)
S. mi +
Su
+
2
3 110
+2
5 11
+
Furthermore, Ixpm) (R.), being the difference of two bounded random variables (see (70)), is itself bounded and hence iquare-interrabe. Now, we have all the ingredients to apply Lemma 2. Using the Lemma statement on Izp.. (R.,) (L S.) (w. S.), we have
20

---

Fairness Overfitting in Machine Learning: An inffrrmation-Thcoreiee Perspective
Var (eee(((, f 5.))
(w, - [
m Su R20
1
+
(88)
4
+
11
+2
n0
3u
11
3.
+
Furthermore, R, are independent Rademacher variables, have
R.. Zap 212 (w, S.) (w, S.)l
(89)
Hence, the random variable (w, S.)) E (w: that using Hoeffding's lemma, have the final results:
(w: S.) is centered and with bounded variance shown in (88)). It follows
22
E[chti(u.S..-eEEu...... Se
11
(90)
C.4. Proof of Theorem
Theorem 2 (restated) Assume that [f] E [0, 1], then for any m E f2,...
gen Jarnness
C
MEC
Σ
ER.
110
Su
+2
11
Su
4
3.
+
2
n1
+2
2 11 (W, R.))
(91)
where Cm is the set of m-combinations.
Proof.
Similar to the MI setting in Theorem the fairness generalization in the supersample setting, be bounded as
follows:
gen fairness
=IEE 2pm
(WW S) (W, S)]I
(92)
P2
Epw. 2(ann
[ (W(WWS)) (. S)]l
(93)
Epzgal (PW.Riz
( S.) - (W S.)l
(94)
Pm
de Pme
For a fixed E Pm let (W, R.,,) be an independent copy of (W, R.,). The disintegrated mutual information I Terpa) (W, R.,) is equal to:
Ipp (W,R..) = D(Ww... 12.. PWizzan
=2(pm PR..,
(95)
Thus, by the Nonsker-Varadhan variational representation KL divergence, AA E H, we have
E (W.WW).). 5.)) Tagan) (W: R..) 2 XE (.W.R../2a.))ppp... [ (W, W. W.S. S.))
(.C
log E W K.,, 2 |m 2
(96)
1mgan) (W:R,) 2 Ae.. ( (WSW)) S.) (W)3,)]
log T. w
E /pp =
W= Mel (e -
(97)
Using Lemma 4, we have
T Sipi (W:R,) 2 AEW R., Z:20 [m2mm (W,(WW W. S.) (W, (W,S.)) S.)
X2m
1
El(
+
+
(98)
11
S.
+2
11
S.
2
10
8
+
2
n
3.
+
21

---

Fairness Overfitting in Machine Learning: An Information- Cinormmttion-Thooeeeee Perspective
So the parabola (function of X)
[ (W. S.) E (W,,WS.))
RR. Z(an) [(an))
m
1
+
E[(
1 0,
(99)
8
Su
+
11
ng
3.
+ +
1
3.
+2
always positive. Hence, its discriminant always negative. follows:
m
[
1
1
1
T 9p2n)
(W; R.,.)
1/2
10
+
2
11
110
8.
+
2
11
S.
(100)
Replacing in (94), we have
1
1
gen fairness
pmm
uEP
RR,
Su 11g
+
2
+
11
Su
+2
710
3
+2
2
+
11
+
(W: R..))
(101)
As mutual information is invariant to permutations, we have the final results.
C.5. Proof of Theorem
Theorem 3 (restated) Assume that [f]
[0, 1]. then for any (2,...,,) .n]. we have
geni
fairness
EZian)
Σ
(102)
WECm I
m
ER...
F
R.,))
2
H (m
S.. Sy 3.. 3.
2/2m
,70 m1
where CT is the set of m-combinations.
Proof. We have
gelifairnes. fairness
P. Zinn
1e (((WW))) (W (WW()))
(103)
E Papan)
E P...iiz
(F( (W. S)]
(104)
E Pw Epppal
(W, Sw) - ( (W,S..... Sw)l
(105)
pm
Wc Pm
E Pw..Ri
Σ
f(w,,,)
1
Σ
f(w
(106)
pm
WE pm
no
+2 2
S.,Ti=0
n. +
S.,Ti=l
Σ
((wwx))
Σ
((w,z;))
(107)
5 mh
+2
m
+2
S,T:=0
S,T:=1
Σ
Epgpan
E Epr.. R22ipl
Σ
F
1
(108)
Pm
WE
S.
+
S..Ti=D
n1
S. 2
S..Ti==
1
Σ F
(109)
5
+
n
+ B,T:=1
5
For a fixed u E Pm, let (F,, R.,,
be an independent copy of (F R.).
By the Varadhann variational representation of KI. divergence, Aλ R, we have
22

---

Fairness Overfitting in Machine Learning: An Information- iinormmttion-Thooeeeee Perspective
T 1/22]] (uu Ru) 2 XEF 2.. E
S.S) E W S.)]
log E F. F. 12,.)
(110)
Iadtt (Fui Ra) 2 A.,,, R.ii2 (W, E ( SW))
R Z4an) - *2o Fu=FF (cAtE
log E2 F..
(111)
Using the result of Lemma 4, we have
I2tpil (Fu; Ru)) 2 AEF, 1ppp
( - ( (W,S,) S.)]
A2m
1
1
[
+
(112)
11
Su
+ 2
n1
5.
+
110
+
11
Hence, the discriminant is negative:
fairness
Pmm
Eyzgan
oc
Σ
RR.
110
S,
+ 2
+
11
Sn
+
10p
5.
+2
2
+
n1
+
(Fu; R.,))
(113)
As mutual information invariant permutations, we have the final results.
C.6. Proof Theorem
Theorem (restated) Assume that [f] E [0, 1]. then for any m E (2,... n.
gen
fairness
C
ucCm
ER,
Su n10
+ 2
+
11
S.
1
+
2
n1
+
2
+
11
8.
1
+
2
spmn
(Ius R.,)
(114)
where C is the of m-combinations.
Proof. We have
gen
fairness
EE ppm)
Te (F(W (W.S) S) - (W. (F.5)) W)
(115)
Brayzi
E E...R Z[2m]
( (WW))
(W.WW)))
(116)
EPagzn
E EPW.RIZIpn
LE S.) (W, ( S.)
(117)
pi
Pm
Ep
EPr. n. R122n
L
(118)
pm
WE PaN
where L,, (LR L = (W, (W,S., OF (W,Sw)) By the Donsker-Varadhan variational representation of KI. diver-
gence, VA E R, we have
RR., Imnpil Lui Ru)) 2 AE,,,,R,,,IZen 12pm))
[L L
[e ALF--RR)
llog E R.. Zia Mpm)
(119)
Imdie (Lu Ra)) 2 AEL, RR. (Zpan) [L LR
-log Ew E E 1p -(pn)) W We IR
(120)
23

---

Fairness Overfitting in Machine Learning: An Information- Copemmattoo-Thoociiie Perspective
Using the result of Lemma 4, we have
Tapasl (Lus Ru,) 2 L., R.. R..122. 19 (W, S..) - C (W, (W,, (W))
12m
[
1
+
1
2
(121)
8
n1
8u
+
2
n1
8n
+
10
+
8.
+
2
Hence, the discriminant is negative:
gen fairness
pm
w Pm
Σ
ER
110
+
2
11 Su
+
2
3-
1
+
+
n1
3.
1
s/2m
(Lu; R.u)
(122)
As mutual information invariant permutations, we have the final results.
C.7. Proof of Theorem
Let R., (R.,) ym where denotes the XOR operation. Given binary value b {0, 1}, define b @ t. (b, ( + b) D To simplify the notation, we denote @ 4, and @ 2, as 2, and t respectively. The notation 4. = (L th L 4 then represents a pair of losses, while A &. L,
5thh be the sequence of supersample variables indexed by u, and let t., (Ra, + Ru,
1=2 E B
o I. denotes their difference.
Theorem 5 (restated) Assume that ||| [0, 1). then for any m (2, ,n]
gen fairness
S
Cmm
Zizm)
171
2
E3
R.
110
8.
1
2
n1
8. +2
n0
+
11
S.
+ 2
U4 s/2aa (ALã Run)
(123)
where C is the set of m-combinations.
Proof. We have
gen fairness
E E pnn
[ef (W.S) - (.S))
(124)
E P p(Z
(F(,))) (.( S|]
(125)
E ErApa)
E EPW.RIZIpnl
[ (W, - eff W, S.))
(126)
pm
W Pm
TE. P2paa)
Ep EP,00 2u Rui 1222)
[(- (L, Φ!
L + )]
(127)
pm
Pm
Erzpnl
EP AL Bul2pan
Rm AL Pul
(128)
pm
WE
24

---

Fairness Overfitting in Machine Learning: An Information- Perspective
By the Donsker-Varadhan variational representation of KL divergence, AA R, we have
Ru; : 2 XE A RR., [Zaa [ 7/2m)
((-1) (-1))R, Ru, AL
[e ((1))) AL""
log IE
(129)
AL. .R.,, pan mmam]
I 2/2m1] [
Ru: ; 2 XE A RRuy (2pan) App)) ((-1) Ruy AL 9:-1
[c (
log Ew R.
(130)
Iatia " 2 ALE ALS Ri, [2an)=
[(-1) Ru, Ru, AL ".
apn) W -ww.eeNttlu.....
log E W
E E (2p
(131)
(132)
Using the result of Lemma 4, we have uu: Ru,)) ) 2 AE AL." Ruy
(111)
AL [a]
Zipnn "R.g
apa.
2
8
11
Sn.
+ 2
10
Su
+
2
+
140
5
+
11
3
+2 2
(133)
Hence, the discriminant is negative:
m
$1
(AL
th Rus)
gen
fairneas
pm
ue
2
710
S.
01
+
700
Su
2
11
3.
+ 2
(134)
As mutual information is invariant to permutations, we have the final results.
D. Proof of the Theorems/Lemmas in Section 5
EO Generalization Error. Analogously the DP setting, we define the population-level separation fairness loss as
WW = Ep L (W.
(135)
and the separation-baal based fairness generalization gap becomes
farnnss = E. [ee (W, Ps) - ( (W.S).
(136)
D.1. Proof of Lemma 5
Lemma (restated)
Fix w e W and fixed n n n nf,y. Let g T R be defined follows: g( 2m) efie (w, 2u). where Fg
E (w,, 2.) is defined (16). Then, for any 1 < S n, we have
2
sup (9(2u) g( 24
(137)
min Ene
2. + 2)
where [[w,, mxa) is bounded by and min (nt. + 2) is the smallest subgroup size across both and Y.
25

---

Fairness Overfitting in Machine Learning: An Information- Cepermattoo-Thooeeiee Perspective
Proof. For 1 Si m, consider the difference:
(0(za) g(2x)l =
I()
x(,,
2u
2u 1==1,v=0
14 1=00000 +
+
Tj
1==0
1==0
f(w,3z)
f(w,
(138)
20
11 1= +
11=1,8=0 +2
1-=0
1-
=
=
Σ
f(w,zz)
Σ
(w,wz))
1-y=- +2
2u
1=1=11 +2
2u
T
1==1
1
f(w,8g)
f(e, 3,)1
(139)
2.
2.
14
1=
+
1
=0
P4
11=1,8=1
+2
===1
y
1
Σ
Σ (W,))z)
7==00 +
20
11=1,y00 +2
2x
=,=0
T,=1
y,=0
1
1
f(w, Tgj)
flw, 3z))
(140)
%/0
2.
1==0=== +
T==0
11=1,1=0
+
2
=1
F==0
8,=0
Σ
f(w,z))
1
f(w,,z)
11
00=01
+
T
11=1,y=1 +2
2u
T,
X,=
Y,=1
+
1
Σ
f(w, āz) +
1
flw, 33)
(141)
20
2.
0=
+2
T==0
+2 2
7
Y,=1
Y, =1
(142)
The inequality in (139) follows from the triangle inequality | |a] - |6]|
S aa
bl.
Since žj 2j for all j * i, the change affects only the i-th component. Based on the values of t, and E, we have 8 different subeases within 4 main cases:
Case 1.1: 3/ and i 1 while t, Before the change:
Lo(zu) = ((==0,0(zw) - (z=1)(
(143)
After the change, n1=0,u 110000 1 and 1
Zx Zu Zu
12=0,11
2x
Loo
Σ
f(w (1=1,((2u)
(144)
1==0,00
2n
+1
(2(
Σ f(w, f(w, 24)
(145)
11 +3
26

---

Fairness Overfitting in Machine Learning: An Information- Cepermattoo-Thooeiiie Perspective
The change in g(zu) is:
l0(au) - g( g(2,)]= [Zo(zn) To(())) + [T1(
L1 (21))
x,)
2u
2u
1,000
+
11=0,00
+
y,=0
Y =
j#
Σ f(w, (5), + (ww
+
1=0,1
2u
+2
T
t=0,
2u
+3
y==1
<
+
(146)
10000
2.
+
00,0011
Zu
+2
Case 1.2: y: and Or 0 while 4 This scenario is symmetric Case 1.1, The bound is identical:
1
19(2w) - I
+
(147)
74=0,0
+
n=00,1 + 2
Case 2.1: y: = and Ø = while & =1 Before the change:
Lo(zu) = 1((=0,0(2u) - 10=11(
(148)
After the change, n n= = 1, and n, = n +
Lo(
(
1
Σ
[w,
(149)
n2,
11=100
2,=0
jfi
(x
Σ
f(w, xzy) f(w, 84)
(
(150)
14
2n
+3
The change in g(z)) is:
10(zw) s(2:)) = [o(zz) Lo + [L)(2n) - (z
f(, 3/
f(w,I;)
7.
1=
+
T1=1
1==100 +
7-=1
y==0
Y,=0
j
+
Σ
f(w,zy)
Σ flw, xz)) Iw
2
1,1
+ 2
20 n4
+3
Y,=1
1
+
(151)
n 1111,
2n
+2
n=
Zu
+2
27

---

Fairness Overfitting in Machine Learning: An Information-Thoone Perspective
Case 2.2: y: and 0 while 4 = This scenario is symmetric Case 2.1. The bound is identical:
(g(an) - -(( -
+
(152)
1/2 +2
1,=10
1=11,
Case 3.1: t2 and é while y 0. Before the change:
Lu(zu) (l(=0,((zu) - (==11(2u))
(153)
After the change, 2u = 1==0,00 and 1=100 -11=1.0" +
Lo(E
Σ
(w,
Σ
f(w, xz)
(154)
0,000
+1
7-=0
11=1,0
+3
Y,=0
jzi
The change in ((x) is:
(g(zw) - g((2)) = (o((z) Lo(E!)
<
(w,
x;))
n1 0,0
20
+ T-=0
n0 +
V,=0
Y
j#
+
Σ
f(w,zj)
Σ
f(w, + f(w,
2n
2n
1=
+
T
1= +3
T=
Y,=0
Y,=0
(155)
70 n
0,0
+
n4=1,0
Zu
+
Case 3.2: t, = and i = while y/ = O. This scenario is similar to Case 3.1. The bound is identical:
[9(zu) g( <
+
(156)
12000
7.
+2
n=
%,
Case 4.1: t, = and é = while y = 1. Before the change:
Li(zw) 111-0,, 1 (zu)l-
(157)
2n After the change, 1= = n 1 and m = -m + 1:
((
f(w + f(w, Ii)
f(w,zz)
(158)
0
1/
+3
n
1=1,1 +
2.
28

---

Fairness Overfitting in Machine Learning: An Information- Theiooenic Perspective
The change in g(z.) is:
[g(zz) g(22)) (zu) - (x
1
Σ
f(w, 23))
1
Σ
f(w, + f(w, 24)
2u
Zn 1==0,1
1=
+ 2
T,=
+3
Y==1
[W,zz)
1
Σ
(=
2n
+2
T-=1
11=1,11
2u
T
Y,=1
+
(159)
1=0,1
20
11=1,1
Zu
+2
Case 4.2: t2 0 and & while y: = 1.
This scenario is similar to Case 4.1. The bound is identical:
1
(9(zn) - -(( s
(160)
20 1 +2
Z. t=
+ 2
Case i, = to or V1 V/- In this case, the change affects only one group, either in t or y, while the other attribute remains unchanged. T For both scenarios, the counts updated follows:
1
(g(zu) g(
S
(161)
70
+2
Aggregate the Bounds
From Cases 1.1 to in each scenario where change occurs, we can write the following:
1
sup S.E2",,,E
lg(zu) s((()
max (t.v). v) (1
14
Zu
+
Zu n
+
(162)
< 2 max
(163)
2n 2
(1.3) 14,9
2
(164)
Z. + 2
mil((.y) 14.
This completes the proof.
D.2. Proof of Theorem 6
Theorem (restated) Assume that ff E [0, 1], then for any m E ...... ,n.
geTifairues
2m min((.y) (ne.g 2)
(2] Z..)
(165)
pm
And the label with fewer samples will typically dominate the maximum variance, so the upper bound depends not only on the expectation over the sensitive attribute but also on the number of samples for each label.
gen fairness A Erwa (CE(W, (GW,Ps) Ps) (W,S)
(166)
29

---

Fairness Overfitting in Machine Learning: An Information- Cenoommtttoo-hhoreiiee Perspective
Proof.
Var (W, Vaug ()) <
m E
4
t.y.t'
max
(% 20 -= +2
1== N-,,,,=- Y= + )9]
2u
(167)
(L.))((t .')
gen fairness
EPW L (W, V Y)
Ew. 8 clo (W, Vane [))l
(168)
Epw. Z. [ (W, Zw)]
Pw [ (W, Z,,]]
(169)
P
Pm
S
E..... fe (:: Iw)l
E E. Zu
8f's (W, Zu)l
(170)
pm
Wc Pr
m El
max
(7 - +2 " +
/ Z..)
(171)
pm
2
tyy
Pu
(t,))(tt w/)
2m
(t,) ntyy + + )
(172)
Pm
WE
In addition, as mutual information is invariant to sample permutations, we have
gen fairness
2ml
min Re, + / Z..)
(173)
1
where C is the set of m-combinations. And we have a for the binary label case. This completes the proof.
Lemma 8. Assume that fl E [0, 1). then for any E (2.... ,n)
geireeeness
pm
1
E
Σ
2mER, I(
2. min n4,y + (1.g)
min n4.y + (f.g)
1 2/an| (W; R.,.)
(174)
Similar to the result of Lemma 4. by applying the separation loss to the variance bound, we obtain:
Var
(
(w,SS) & (w, Sw))
m s E
2
2
(175)
4
min ni.9
+2
min 14,8
3.
2
Finally, using Hoeffding's Lemma, we get:
x2m
(1.)
2n
E
e
Se
min(s F1
(176)
For a fixed Pm let (W, R.,) be an independent copy of (W, R.,.. The disintegrated mutual information T (W, R..) equal to:
Iap W, R..) D(Pw, Za m2n) PP 2 pa =mp PR..).
(177)
And here we only change the independence loss function to the separation based loss
peirneirres.
F.w Zpzn)
()
(W.S)) 1e (W, S)
(178)
E Br
EPW Zp2m)
F (W.5))
(179)
Er
1 (W.S.) 4 (W, (W,5.)
(180)
pm
P
30

---

Fairness Overfitting in Machine Learning: An Information- Theioooti Perspective
Similar the proof in Theorem 2, we can have
gen
Pm
E
Z
Σ
Pm
2m R.
1(
min 2, (5.y)
Su +
min R4.9 (4.9)
S.
+
91 (W; Run)
(181)
As mutual information is invariant to permutations, we have the final results.
D.3. Proof of Theorem
Theorem 7 (restated) Assume that [fl
[0, 1), then for any f2, ,n]
gen
fairness
Crm
Σ
2mER
min(t.g) niyy +
1
Su
min nig +
99 T5spn)) (AL Rus )
(182)
Proof. We have
gen Jenlfarree fairness
E Pw 3pp
( (W.))) S)]
(183)
ER (.RRRI
(W(W))) (W, S)]l
(184)
E Pw.
(W, S.) - e W, S.)
(185)
pm
uEP pm
1
Expp
Ep 10 M2pmn
[(-1) Ras th L 4 )|
(186)
pm
WE Pm
PP A R2.12
[(- AL Pu]
(187)
P
WE
By the Donsker-Varadhan variational representation of KL divergence, AA R, we have Imnaaa ( RR,) :..,) 2 AE AL R.,, [Z22n)
[(- 1- R
AL
Je ((-1)) AL.
log AL. R.., Zpan F
(188)
Izpuil (AL :R..)) 2 AE ALS " Ruu (Zp2m) Ap20) ((-1) Ruy AL
(e (
log Ew R.
(189)
Iociaa (A ;R,, 2 ALE AL R.,, [22 1[ 1) R., AL ".1
E (mp apo.) W.....WW.. -e
log W
(190)
(191)
Using the result of Lemma 8, we have
I Tppa (AL Pu. Ray) 2 AE AL. R.,, =
1(-1) Rv.
AL Pu
1mm
)2
E
(192)
8
min ni (1.3)
Su
+
min 74, (1.8)
3.
+ 2
Hence, the discriminant is negative:
gen Fairness
pm
Ezpsi
pm)
ME Pm
Σ
2m a ER.
min n4 (f.9)
Sue 2
min T4. + 2 (t.3))
2 I (AL ". Rug))
(193)
As mutual information invariant to permutations and we have a = 1 for the binary label case, we have the final results.
31

---

Fairness Overfitting in Machine Learning: An Information- Theiioote Perspective
E. Bounds based on prior techniques
Lemma 9, Assume that [f] E [0, 11, then
(2 V.)
(194)
Proof. Using the Donsker-Varadhan variational representation of the relative entropy, we have
I(W, v.) 2 B.w.ssleeE V.)) log E T le V.
(195)
We have lfl E [0, 1]. Thus
()( = 1 Σ
x(, - - Σ T:=1
f(w, fw,xz;)
S max (1 f(w, (10, n11 7-=1
Σ f(u, mi))
(196)
Ti=0
T==0 < max =1
(197)
So FE(w, X²) [0, is bounded. Thus, using Hoeffding's lemma, have:
log P (eW( & NERROR V.)] + 2²
(198)
By replacing in 195, we have:
T(, V.) A(EAw.. (W, V.)I P (LE(W, V.))) + 2 > PAO E ER.
(199)
Thus, (199) must have non-positive discriminant.
(Ew,, V.)] - LEW (W)ll S V21(W. v.)
(200)
E.1. Proof of Lemma
Lemma (restated) Assume that [f] [0, 1]. then for any 12....,m0 ,n}
gen fairness
S
Σ
(2((WV
(201)
Cm
Proof.
gen fairness E Pa (W,, S)] - Er P (W S)]
(202)
Let m E (2) be a fixed number. Given the set Z1m ~ pmm the corresponding (f(w, Z1.m) is as follows:
(w, Z1:m)
f(u,xx))
Σ (w, T==1
(203)
Zzmm
Zr
no
T.=0
nh
Given a sequence of indices a = pm E
[1, n.)",
let Z. = 12, )m be the sequence of training samples indexed by w.
Let pm be the set of m permutaations of n. Then, using the notion of & W, Zim) we have:
gen foirness
I. & 165 (E(W))) E. (E W S)]I
(204)
EPw Zi.m
(W, Z Z1:m)]]
E E 1 (W, Z.)]
(205)
pm
Pm
EP W...
1 Z )] - Eraz. [L Z.,i
(206)
pm
aEPa Pm
32

---

Fairness Overfitting in Machine Learning: An Information- Theiiootiii Perspective
Assuming that |/| [0, 1], Similar to Lemma 9, show that
E W 1.m
L [W Z mlm]
PPw. 2., (W, Z..I S 22(W; V.)
(207)
where V, .X.,, T.)
By plugging (207) into (206), have
gen fairness
BP
LWW Zim)]
Epw. n. 1LE(W W, Zw)l
(208)
pm
Σ
(2I(WV
(209)
Pm
Pu
However, as mutual information is invariant to sample permutations, we have
gen
fairness
22((:
(210)
NEC
where C is the set of m-combinations.
33

---

Fairness Overfitting in Machine Learning: An Information- Copemmattoo-Thhoceiie Perspective
F. Additional Empirical results
F.. Experimental details
In all the experiments in this paper, similar to Harutyunyan et al. (2021), for every number of training data n, we randomly sample my 21 different samples from the original dataset. Next, for each 2[2n]. we draw m2 50 different train/test splits, i.e., me random realizations of R. Hence, each data point in the figures corresponds to a total of my 1050 experiments. We report the mean and standard deviation the my results.
We conducted experiments using the following datasets:
COMPAS (Larson al., 2016): The COMPAS dataset contains records of criminal defendants and is used predict whether the defendant will recidivate within two years. The dataset includes attributes such criminal history and demographic information, including race and gender.
Adult (Kohavi & Becker, 1996): The Adult dataset based on the 1994 U.S. Census and is widely used machine learning research. The goal is to predict whether individual earns more than $50K annually based on demographic and financial data. In fairnsss studies, gender is often used as the sensitive (binary) attribute.
The following fairness methods were evaluated in our experiments:
ERM: Empirical Risk Minimization (ERM) is standard machine learning approach that minimizes the empirical risk on the training data. It serves as baseline for fairness methods.
DifMP, DiffEopp, DiffEodd (Mroueh et al., 2021): These methods apply gap regularization for demographic parity, equalized opportunity, and equalized odds, respectively. Since these fairness metrics cannot be optimized directly, gap regularization provides a differentiable alternative loss that can be optimized using gradient descent.
PRemover (PrejudiceRemovvr)) (Kamishima et al., 2012): This method minimizes the mutual information between prediction accuracy and sensitive attributes.
HSIC (Baharlouei et al., 2020; Li et al., 2022): The Hilbert-Schmidt Independence Criterion (HSIC) is minimized to reduce the dependence between prediction accuracy and sensitive attributes.
F2. Extra Numerical results for our bound in Theorems 5
We report the experimental results of faimess generalization error and our bounds in Theorem 5 (DP) and Theorem 7 (EO) as a function of the the total number of training samples n on with COMPAS dataset with gender and race as sensitive attribute in Figure and Figure 4, respectively. In Figure 5 and Figure 6, we report the results of our bound in Theorem (DP) on Adult with Gender and Race as sensitive attributes, respectively.
The CMI terms Theorems (DP) and Theorem 7 (EO) involve both a continuous and a discrete variable. We evaluate different estimators for these terms. Specifically, in addition to the main estimator used in this paper, i.e., Ross (2014), experiment with the estimators proposed in Gao et al. (2017), Darbellay & Vajda (1999), and Kraskov et al. (2004). The main results of these comparisons are presented in Figure 7, showing that Ross (2014) is the most robust estimator in our case.
F.3. Extra Numerical results for batch balancing
In Table 2, we report the results for our batch balancing approach on the Adult dataset. The results are consistent with Table 1, highlighting the strength of our approach and its ability to improve faimess test errors of different algorithms.
In Figures 8, 9, and 10, we report the mean of test accuracy, the mean of fairness generalization error, and the mean of fairness test errors of the different approaches using COMPAS (gender) dataset with different number of training samples n.
34

---

Fairness Overfitting in Machine Learning: An Information-Theooe Perspective
COMPAS (Gender): ERM
COMPAS (Gender): HSIC
COMPAS (Gender): PRemover
0.20
0.20
0.20
AL-CNI bound
Fairness loss (DP)
AL-CMI bound Faimess error
AL-CMI bound
0.15
Faimess gen enror
0.15
0.15
Faimess error
Fairness loss
Fairness loss
0.10
0.10
0.10
0.05
0.05
0.05
0.00
0.00
0.00
250
500
1000
1500
2000
2500
250
500
1000
1500
2000
2500
250
2000 number training samples
500
1000
1500
2500
number of training samples
number of training samples
COMPAS (Gender): DiffDP
COMPAS (Gender): DiffEodd
COMPAS (Gender): DiffEopp
0.20
0.20
0.20
AL-CNI bound
Faimess loss (ED)
AL-CMI bound
Fairesss loss (EO)
AL-CMI bound
0.15
Faimess gen error
0.15
Falmess gon error
0.15
Falmess gen error
Falmess
0.10
0.10
0.10
0.05
0.05
0.05
0.00
0.00
0.00
250
500
1000
1500
2000
2500
250
500
1000
1500
2000
2500
250
500
1000
1500
2000 2500
number of training samples
number of training samples
number of training samples
Figure 3. Experimental results with COMPAS datasct (gender as sensitive attribute) of fairness generalization error and our bounds in Theorems (DP) and Theorem 7 (EO) as a function of the total number of training samples n.
COMPAS (Race): ERM
COMPAS (Race): HSIC
COMPAS (Race): Premover
0.20
0.20
0.20
Falmess (DP)
AL-CMI bound
Faireess loss (DP)
AL-CMI bound
Fairnsss loss (DP)
AL-CMI bound
0.15
Faimess gen error
0.15
Faimess gen error
0.15
Fairess gen error
0.10
0.10
0.10
0.05
0.05
0.05
0.00
0.00
0.00
250
500
1000
1500
2000
2500
250
500
1000
1500
2000
2500
250
2000 2500 number training samples
500
1000
1500
number of training samples
number of training samples
COMPAS (Race): DifiDP
COMPAS (Race): DiffEodd
COMPAS (Race): DiffEopp
0.20
0.20
0.20
AL-CMI bound
Faimess lass (EO)
AL-CMI bound
AL-CMI bound
0.15
Faimess gen
0.15
Faimess gen error
0.15
Falmess gen error
Fairmess loss
Faimess
0.10
0.10
0.10
0.05
0.05
0.05
0.00
0.00
0.00
250
500
1000
1500
2000
2500
1500 2000 2500
250
500
1000
1500 2000 2500
number of training samples
number of training samples
number of training samples
Figure 4. Experimental results with COMPAS dataset (Race as sensitive attribute) of fairness generalization error and our bounds in Thcorems (DP) and Theorem 7 (EO) as function of the total number of training samples
Table Effect of batch balancing on DP errors with the Adult dataset. We report DP on test data for various approaches, with and without our proposed batch- balanchblnning strategy. The results show that balancing consistently reduces DP by an order of magnitude. This empirically supports the theoretical insights of Theorems 5 regarding the role of group imbalance in faimess generalization error.
sensitive attribute: gender
sensitive attribute: race
7500
10000
15000
20000
7500
10000
15000
20000
DifIDP
0.038
0.037
0.039
0.038
0.083
0.083
0.084
0.084
DifiDP (ours)
0.020
0.020
0.021
0.020
0.063
0.063
0.064
0.063
HSIC
0.026
0.025
0.025
0.026
0.087
0.086
0.086
0.086
HSIC (ours)
0.009
0.005
0.007
0.007
0.026
0.023
0.019
0.0178
PRremover
0.027
0.026
0.026
0.026
0.035
0.033
0.032
0.031
PRremover (ours)
0.008
0.007
0.007
0.007
0.011
0.009
0.007
0.006
35

---

Fairness Overfitting in Machine Learning: An Information- iitormattion-hhoreieee Perspective
Adult (Gender): ERM
Adult (Gender): HSIC
0.05
Faimess loss (DP)
AL-CMI bound
Faimess loss (DR
0.05
AL-CMI bound
0.04
Fairness gen error
0.04
Faimess gen error
0.03
0.03
0.02
0.02
0.01
0.01
0.00
0.00
2500
7500 10000 15000 20000 number of training samples
5000
2500
7500 10000 15000 20000 number of training samples
5000
Adult (Gender): PRemover
Adult (Gender): DiffDP
0.05
0.05
Fairness loss (DP)
AL-CMI bound
AL-CMI bound
0.04
0..44
Fairness gen error
Fairness gen error
0.03
Faireess loss
0.03
0.02
0.02
0.01
0.01
0.00
0.00
2500
5000
7500 10000 15000 20000
2500
5000
7500 10000 15000 20000
number of training samples
number of training samples
Figure 5. Experimental results with Adult dataset (Gender as sensitive attribute) of faimess generalization error and our bound in Theorem 5 (DP) function of the total number of training samples
Adult (Race): ERM
Adult (Race): HSIC
0.20
0.20
Faimess loss (DP)
bound
Faimess loss (DP)
AL-CMI bound
0.15
Fairness gen error
0.15
Faimess gen error
0.10
0.10
0.05
0.05
0.00
0.00
2500
7500 10000 15000 20000 number of training samples
5000
2500
7500 10000 15000 20000 number of training samples
5000
Adult (Race): PRemover
Adult (Race): DiffDP
0.20
0.20
Faimess loss (DP)
AL-CMI bound
AL-CMI bound
0.15
Fairness gen error
0.15
Fairness gen error
Faimess loss
0.10
0.10
0.05
0.05
0.00
0.00
2500
5000
7500 10000 15000 20000
2500
5000
7500 10000 15000 20000
number of training samples
number of training samples
Figure 6. Experimental results with Adult dataset (Race as sensitive attribute) faireess generalization error and our bound in Theorem (DP) as function of the total number of training samples
36

---

Fairness Overfitting in Machine Learning: An Information- Theiioott-i Perspective
(Ross, 2014)
(Kraskov et al., 2004)
0.20
0.20
Fairesss loss (DP)
AL-CMI bound
Fairnsss loss (DP)
AL-CMI bound
0.15
Fairness gen error
0.15
Fairness gen error
0.10
0.10
0.05
0.05
0.00
0.00
250
500
1000
1500 2000
2500
250
1000
1500 2000
2500
number of training samples
number of training samples
(Gao et al., 2017)
COMPAS (Gender): DiffDP
0.20
Faimess loss (DP)
AL-CMI bound
0.20
AL-CMI bound Partitioning Faimess error
0.15
Fairness gen error
0.15
Fairness loss
0.10
0.05
0.05
0.00
0.00
250
500
1000
1500
2000
2500
250
500
1000
1500 2000 2500
number of training samples
number of training samples
Figure 7. Experimental results of our bound Theorem 5 (DP) with different MI estimators using the DifIDP approach on the COMPAS dataset (gender as sensitive attribute) as a function of the total number training samples n..
1.0
COMPAS: Classification Error (Gender)
COMPAS: Fairness Gap (Gender)
1.00
COMPAS: Fairness Validation (Gender)
Classitiation Error
diffdp
dirtdp toursi
④ Er
0.05
0.06
diffdp (ours)
diftdp
0.06
0.05
diftdg
diffdp (ours)
0.6
0.04
0.04
0.4
0.03
0.03
0.02
9.002
0.2
0.01
0.01
0.0
500
1000
1500
2000
2500
0.00
500
1000
1500
2000
2500
2 0.00
500
1000
1500
2000
2500
Training Samples
Training Samples
Training Samples
COMPAS: Classification Error (Race)
COMPAS: Faimess Gap (Race)
COMPAS: Faimess Validation (Race)
1.0
0.07
0.07
Clssitication Error
0.8
diffdp (aurs)
diffdp
0.06
diffdp
difídp (ours)
0.005
5..06
difidp
diffdo (ours)
0.6
0.04
0.4
0.02
0.2
0.01
0.01
0.0
2500
0.00
1000
2 0.00
2500
Training Samples
Training Samples
Training Samples
Figure 8. Experimental results with COMPAS (gender) dataset of batch-balancing technique for difiDP function of the total number of training samples n. We report the mean over m.
37

---

Fairness Overfitting in Machine Learning: An Information- Theiiootii Perspective
COMPAS: Classification Error (Gender)
COMPAS: Faimess Gap (Gender)
COMPAS: Fairness Validation (Gender)
1.0
0.20
Faimess Validatiio Error
0.20
Classtication Error
HISC
Faimess Gap Error
HISC
HISC
0.8
HISC
0.15
HISC (ours)
0.15
HISC (ours)
0.6
0.10
0.10
0.4
0.2
0.05
0.05
0.0
500
1000
1500
2000
2500
0.00
500
1000
1500
2000
2500
0.00
500
1000
1500
2000
2500
Training Samples
Training Samples
Training Samples
COMPAS: Classification Error (Race)
COMPAS: Faimess Gap (Race)
COMPAS: Faimess Validation (Race)
1.0
Fairness Validation Error
Classiiiation Emor
HISC (ours)
Faimess Gep Error
HISC
HISC
0.8
0.15
(ours)
0.15
HISC tours)
0.6
0.10
0.10
0.4
0.2
0.05
0.05
0.0
500
1000
1500
2000
2500
0.00
500
1000
1500
2000
2500
0.00
500
1000
1500
2000
2500
Training Samples
Training Samples
Training Samples
Figure 9. Experimental results with COMPAS (gender) dataset of our batch-balancing technique for HISC as function of the total number training samples n. report mean over m..
1.0
COMPAS: Classification Error (Gender)
0.20
COMPAS: Fairness Gap (Gender)
Faimess Validation Error
0.20
COMPAS: Fairness Validation (Gender)
Clasiticaion Error
PRremover (aurs)
Faimess Gap Error
PRremaver
0.8
PRremover
0.15
PAremover (ours)
0.15
0.6
0.10
0.10
0.4
0.2
PRremover
PRremover (ours)
0.0
500
1000
1500
2000
2500
500
1000
1500
2000
2500
500
1000
1500
2000
2500
Training Samples
Training Samples
Training Samples
COMPAS: Classification Error (Race)
COMPAS: Faimess Gap (Race)
COMPAS: Faimess Validation (Race)
1.0
Valiidatio Error
Classincation Eiror
PRremover (ours)
Faimess Gep Error
PRremover
PRremover
PAremover (ours)
0.6
0.10
0.10
0.4
0.2
0.05
0.05
PRremover
PRremover (ours)
0.0
500
1000
1500
2000
2500
0.00
500
1000
1500
2000
2500
0.00
500
1000
1500
2000
2500
Training Samples
Training Samples
Training Samples
Figure 10. Experimental results with COMPAS (gender) dataset of our batch-balancing technique for PRremover as function of the total number training samples n. We report the mean over mi.
38


Reviews:
[{"review_id": "Q8cloqOvfG", "reviewer": "Reviewer_mzyB", "summary": "This paper studies fairness generalization error, i.e., how does model fairness extend to new, unseen data. The fairness generalization error is defined (in Eq. (3)) as the discrepancy between the fairness-population risk and the fairness-empirical risk. The authors study this from an information theory perspective, and derive upper bounds for fairness generalization error using two widely used fairness metrics: Demographic Parity (DP) and Equalized Odds (EOd). The proposed fairness error bounds are validated through experiments on two datasets: COMPAS and Adult.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer’s thoughtful feedback on our work. Below, we address each concern point by point.\n\n**Motivation:** We respectfully disagree that there is a lack of motivation to study fairness generalization. As demonstrated in Figure 1, i) Compared to ERM, when fairness interventions are applied, the generalization error can become particularly significant (e.g., HSCI or PRemover), indicating that these techniques introduce generalization challenges that need further investigation. ii) In certain cases—especially with low-data— the fairness generalization error can be as high as 10–30% of the fairness training loss, which is significant. iii) Different fairness methods exhibit varying generalization behaviors, suggesting that multiple factors influence fairness generalization. Understanding these variations is essential for developing principled approaches to mitigating fairness-related overfitting.\n\n**Experiments:** We kindly refer the reviewer to lines 397-404. Estimating our proposed bound follows the well-established protocol (Harutyunyan et al. 2021; Wang & Mao 2023) and particularly Dong et al. (2024), where permutation-based bounds have been proposed for standard generalization error. The main difference is that here: i) we are targeting a fairness loss. ii) MI terms involve a continuous variable.\n\nQ:  $a$ and $m$ in practice? \\\nA: $a$ in our paper is the upper bound of the predictor function f. Since in this paper, we consider mainly the binary case {-1,1}, a=1 and does not require any estimation. We will clarify this in the final version. \\\n$m$ is a hyperparameter. Like in our experiments, we recommend setting  m=n−1 for practical reasons. ​\\\nQ: Re-training model for each permutation? \\\nA: No, computing the bound does not require retraining for each permutation. It only involves evaluating mutual information estimates over different subsets, with a computational complexity similar to Dong et al. (2024).\n\n**Insights from theory:**\\\n**Theoretical:** In this paper, we take a significant step toward addressing fairness generalization errors by deriving the first rigorous **computable bounds** in the MI and CMI settings, using a novel bounding technique. Our results demonstrate that models generalize differently depending on the fairness approach used, as they memorize the different data attributes (V) at different scales. Furthermore, our bounds shed some light on how data balance influences fairness overfitting. \\\n**Practical:** Beyond these theoretical insights, generalization bounds can also inform practical strategies for improving fairness performance. As a proof of concept, our results suggest that balanced representation (1/H(n_0,n_1)) reduces fairness generalization errors. To validate this, we experimented with batch-balancing, demonstrating that this indeed improves generalization further confirming our theoretical finding. Note that from this perspective, our work can be seen as a theoretical guarantee for the previous works on data balancing highlighted by the reviewers. Additionally, for example, our findings suggest that controlling the MI term—such as by introducing gradient noise during training—could further improve fairness generalization. \n\nQ: assumptions on A? \\\nA: A learning algorithm is a randomized mapping from the training data $S$ to the model weights $W$. Similar to other information-theoretic studies (e.g., Harutyunyan et al., 2021), we make no assumptions about A.\n\nQ: How to interpret the experimental results? the bound is tight? \\\nA: In general, the primary goal of generalization bounds is not solely tightness—achieving this requires strong additional assumptions—but rather to provide theoretical insights into generalization behavior and capture the key factors. Information-theoretic bounds are generally among the tightest in learning theory. For instance, Wang & Mao (2023) (in Figure 2) report bounds that, while sometimes over four times larger than the observed empirical generalization error, remain valid and notably tighter than previous results, as they successfully capture the overall trends. \\\nIn the context of fairness, using prior bounding techniques would yield overly loose bounds that fail to provide meaningful insights into fairness dynamics (see our discussion on Lemma 1). In contrast, our work introduces a novel bounding technique that not only results in tighter fairness bounds compared to previous techniques—e.g., Theorem 1 is tighter than Lemma 1 by a factor of $1/\\sqrt{n}$​—but also reveals fairness-specific properties, such as the influence of class balance (n0,n1​). Empirically, our derived bounds consistently track the observed fairness generalization error across different models and datasets, further validating their effectiveness.\n\nQ: p-value? \\\nA: The p-value for the scatter plot is 3.43×10⁻¹⁶, indicating an extremely strong statistical significance further validating our bounds.\n\nWe will fix the typos suggested by the reviewer.", "claims_and_evidence": "My first question about the paper is in terms of its motivation. The authors illustrated the fairness error in training and testing on COMPAS dataset in Figure 1, but the difference between training and testing error doesn't seem significant, even for ERM training. The authors show more COMPAS results in Figure 2, and in the appendix (which includes more results on COMPAS and Adult dataset), where the fairness generalization error (difference between training and testing fairness error) is not significant. \n\nThis raises the question of whether fairness overfitting is a significant issue, at least on the two datasets (COMPAS and Adult) presented. If the fairness generalization error remains small, the motivation for a theoretical study on fairness generalization error bounds may be weaker. Could the authors clarify why such an analysis is necessary given these findings?", "methods_and_evaluation_criteria": "The paper focuses on a theoretical study, but it is not quite clear how the proposed theory can be applied to practical estimation. To be specific:\n\nThe paper focuses on a theoretical study, but it is not quite clear how the proposed theory can be used in practice. Specifically:\n\n1. the description of the learning algorithm \\mathcal{A} and hypothesis W seems vague to me. Could the authors clarify line 108 (left column) - line 072 (right column)? Are there any assumptions or constraints on the learning algorithm AA?\n\n2. The assumption that $|f| \\in [0,a]$ is used in many theorems. Could the authors clarify how to determine the value of a in practice for estimating the upper bound?\n\n3. The derived error bounds rely on using different permutations of a subset of training data of size mm. However, there is no clear guideline on how to choose mm in practice. Could the authors elaborate on the discussion of mm in Remark 5?\n\n4. Could the authors discuss the time complexity of computing the bound estimation? Does obtaining the bound require re-training the model for each new permutation?\n\n5. From Figure 2 and more figures in the appendix, the derived bound seems to be the upper bound of the fairness generalization error. However, it's not clear if the derived upper bound is indeed tight. Could the authors elaborate more on how to interpret the experimental results? Or any evidence to support that the bound is tight?", "theoretical_claims": "This paper proposes to derive the upper bound of fairness generalization error. However, it's not quite clear what new insights can be obtained from the theoretical study. For example, in Section 6, \"Batch Balancing\", the authors mention that balancing training data between different sensitive groups can help improve fairness, but this conclusion has been studied in many existing works, which use different techniques like resampling, reweighting, counter-factual data generation to balance data [1,2,3]. It's not clear what new insights can be obtained from the theoretical analysis.\n\nBuilding on the points mentioned above: Based on Theorem 5 and 7, it seems that the mutual information term and the number of samples affect the upper bound. The authors may consider exploring potential new/practical insights from these two perspectives. For example, can we practically reduce the mutual information term (maybe through some regularization in training) or increase the training sample number (like data augmentation) to minimize the fairness error bound?\n\n[1] Buda, Mateusz, Atsuto Maki, and Maciej A. Mazurowski. \"A systematic study of the class imbalance problem in convolutional neural networks.\" Neural networks 106 (2018): 249-259.\n\n[2] Jang, Taeuk, Feng Zheng, and Xiaoqian Wang. \"Constructing a fair classifier with generated fair data.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 9. 2021.\n\n[3] Sagawa, Shiori, et al. \"Distributionally Robust Neural Networks.\" International Conference on Learning Representations. 2019.", "experimental_designs_or_analyses": "I understand that the paper primarily focuses on a theoretical study, but the experimental analysis is limited to only two datasets (COMPAS and Adult). Actually, the main paper presents results only on COMPAS, while all Adult dataset results are relegated to the appendix. To better demonstrate the practical applicability of the proposed theory, the authors may consider including a few larger datasets (like CelebA) and varying model architectures in their analysis.", "relation_to_broader_scientific_literature": "This paper is related to fairness in machine learning, an important topic in trustworthy machine learning.", "essential_references_not_discussed": "See in *Theoretical Claims*", "other_strengths_and_weaknesses": "None", "other_comments_or_suggestions": "1. In Eq. (4), is it gen_fairness or \\bar gen_fairness?\n\n2. Lemma 2: \"such that ... for all j \\not = i except on i, i.e., \\tilde v_i \\not = v_j\". Is it \\tilde v_i \\not = v_i instead?\n\n3. Theorem 1: the second square symbol seems not clear\n\n4. In Figure 2, second row, third column, the authors may consider reporting the correlation coefficient and p-value to validate the linear relationship", "questions_for_authors": "My major concerns regarding the paper are about the following:\n\n1. motivation to study fair generalization error bound\n\n2. applicability, parameter setting, efficiency, and validity of using the derived theorems for error bound estimation\n\n3. practical insights from the theory\n\n4. experimental validation of the derived bound\n\nPlease check my comments in above sections of Claims And Evidence, Methods And Evaluation Criteria, Theoretical Claims, Experimental Designs Or Analyses for details.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JYuNkd3XKT", "reviewer": "Reviewer_p9yH", "summary": "The paper considers the generalization of (in terms of empirical violation of) fairness when presented with unseen data. Specifically, the goal is to provide a formal guarantee through information-theoretic fairness generalization bounds with mutual information (MI) and conditional mutual information (CMI). The theoretical and empirical results are provided, and the tightness and practical relevance of the bounds are analyzed across several (group-level) fairness notions, including DP and EOdds.\n\n---\n\n### After Rebuttal\n\nThank authors for the rebuttal. The response is helpful and to-the-point, which further boosts my confidence in evaluation of an Accept (score 4). I confirm that I also carefully went through comments from other reviewers, as well as the rebuttals therein.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your thoughtful question about deriving lower bounds within our theoretical framework, especially considering existing challenges in achieving group-level fairness notions like Equalized Odds (EOdds).\nIn our work, we focus on understanding how fairness measures observed during training generalize to new, unseen data. While our framework sheds light on the behavior of fairness interventions and their generalization properties, directly deriving explicit lower bounds for the fairness-accuracy trade-off, particularly for specific notions like EOdds, is fundamentally different. In particular, Information-theoretic bounds, including ours, rely on the Donsker-Varadhan variational representation for upper-bound generalization error. Hence, deriving a lower bound would require an alternative variational formulation that directly lower bounds the difference in expectation between the joint distribution and the product of marginals of the specific loss function, which is not trivial.\n\nRegarding the impossibility results, as you've noted, prior research has shown that it's often impossible to satisfy all group-level fairness criteria simultaneously. For instance, Chouldechova (2017) and Kleinberg et al. (2017) discuss inherent trade-offs between different fairness measures. Additionally, Tang and Zhang (2022) highlight that achieving EOdds depends on specific data distribution properties; when these aren't met, deterministic classifiers may struggle to attain EOdds without incorporating randomness into their predictions. The key distinction is that impossibility results establish lower bounds on the population risk for different fairness loss functions, while our contribution provides upper bounds on fairness generalization error. Notably, a model can have low generalization error but still perform poorly in terms of fairness on the population level. \n\nAn interesting parallel future direction would be to explore connections between different fairness generalization bounds—for instance, relating DP-fairness generalization error to EO-fairness error. We will incorporate this discussion in the future directions section.", "claims_and_evidence": "The claims consists of several theoretical bounds, e.g., the relation of fairness generalization and the dependence between hypothesis and input data (Theorem 1), the relation between fairness overfitting and the selection mechanism (Theorem 2), the tightening of presented bounds (Theorems 3--4), the reduction of computational cost (Theorem 5), and the bounds for specific fairness notions (Theorems 6--7). The evidence includes the proofs of theorems and the empirical evaluations.", "methods_and_evaluation_criteria": "The method starts from theoretically capturing the bounds followed by improving them, and the further applying to specific group-level fairness notions. The evaluation criteria include the derived $\\Delta L$-CMI, with different methods including DiffDP, DiffEodd, DiffEopp, HSIC, PRemover, etc.", "theoretical_claims": "The theoretical claims are different generalization bounds for fairness, and the proofs are provided in appendix.", "experimental_designs_or_analyses": "The experimental analyses include different aspects of the evaluation of bounds, including bound tightness, bound-error correlation, and the implication of batch balancing (during training).", "relation_to_broader_scientific_literature": "The fairness overfitting and generalization bounds can have implications over broader fields where relevant group-level fairness notions are of interest.", "essential_references_not_discussed": "There are no significant missing references.", "other_strengths_and_weaknesses": "The strength of the paper comes from the organization of materials and the clear presentation of motivation, setting, theoretical analyses, and empirical evaluations.\n\nThe paper can be further improved by including some discussion from the side of lower bounds. While I understand that providing a lower bound might involve developing another set of theoretical results and is beyond the scope of current work, having some discussion (e.g., why a lower bound might be nontrivial, whether a lower bound can be shown to be above 0) can shed light on the whole picture and make it even more informative, i.e., the generalization bounds for fairness can be from both sides (instead of only gets upper bounded).", "other_comments_or_suggestions": "Nothing specific in addition to the comments in above sections.", "questions_for_authors": "Since the impossibility results in previous literature have shown that, in general, not all group-level fairness notions can be achieved at the same time (Chouldechova, 2017, Kleinberg et al., 2017), and also that, the group-level fairness notion EOdds may not be attainable if the data distribution itself does not satisfy certain properties (Tang and Zhang, 2022). I am curious about the possibility of directly deriving the lower bound with the proposed theoretical analyzing framework.\n\n---\n\nAlexandra Chouldechova. 2017. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. _Big Data_ 5, 2 (2017), 153–163.\n\nJon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. 2017. Inherent trade-offs in the fair determination of risk scores. In _Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS’17)_.\n\nZeyu Tang and Kun Zhang. 2022. Attainability and optimality: The equalized odds fairness revisited. In _Proceedings of the Conference on Causal Learning and Reasoning_, Vol. 177. PMLR, 754–786.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "N3fv0BWXcv", "reviewer": "Reviewer_H2i8", "summary": "This paper proposes new generalization bounds for fair machine learning. Based on the Mutual Information framework, these bounds show that the important factors governing fairness generalization are the size of the different subgroups and the mutual information between the distribution of hypothesis and subsets of the training set on which fairness is evaluated. Tighter versions of the bound based on more involved mesures of mutual information are also derived. Developed for both Demographic Parity and Equalized Odds, the tightness of the proposed bounds is empirically evaluated on several datasets.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Mismatch in Fairness Definitions for the Multiclass Problem\n\n In our original formulation for the binary case, the prediction function $f =\\hat{Y}$ outputs values in $\\{0,1\\}$ (i.e., a=1). For multiclass problems, we allow $f$ to take values in a bounded range $[0,a]$; however, the choice of $a$ does not affect the upper bound in our fairness guarantees.\n\nTo illustrate this in the context of Equalized Odds (EO), consider our use of the Total Variation (TV) loss as a fairness measure. For each true label $y \\in \\{0,1,2,3\\}$, we define the TV loss as follows:\n\n$$ \\ell^{F_S}\\_E(w,S \\mid Y=y) = \\frac{1}{2}\\sum\\_{c=0}^{3}\\Bigl|P(\\hat{Y}=c\\mid Y=y,T=0)-P(\\hat{Y}=c\\mid Y=y,T=1)\\Bigr|, $$\nwhich in practice is approximated by\n$$ \\ell^{F_S}\\_E(w,S \\mid Y=y) = \\frac{1}{2}\\sum\\_{c=0}^{3}\\left|\\frac{n\\_{0,y,c}}{n\\_{0,y}+2}-\\frac{n\\_{1,y,c}}{n_{1,y}+2}\\right|. $$\nWe then define an aggregate function over the true labels: $g(z_u) = \\sum\\_{y\\in\\{0,1,2,3\\}} \\ell^{F\\_S}\\_E(w,z_u \\mid Y=y) $. Our analysis shows that\n$$ \\sup\\_{z\\_u,\\tilde{z}\\_u^i} |g(z\\_u)-g(\\tilde{z}\\_u^i)| \\le \\frac{2}{\\min\\_{(t,y)}\\{n^{Z\\_u}\\_{t,y}+2\\}}$$\nThe key point is that—even if the prediction function $f$ is allowed to take any value in $[0,a]$—changing one sample affects the probability estimates (and hence the TV loss) by at most a fixed amount (i.e., at most 1) regardless of $a$. In other words, while $f$’s output may be scaled by $a$, the impact on the fairness loss (measured in terms of probability differences) remains unchanged.\n\nThus, our technical arguments extend naturally to the multiclass setting. We acknowledge that our previous explanation did not clearly separate the role of the prediction magnitude (bounded by $a$) from the fairness loss itself, and we appreciate the opportunity to clarify that the fairness definitions (including EO) are applicable to the multiclass case under our bounded prediction assumption.\n\n## Is the square-integrability assumption to apply the Efron-Stein inequality respected?\nThank you for carefully reading the proof. You are correct that the Efron-Stein inequality assumes square-integrability, and we acknowledge that this assumption was not explicitly stated in Lemma 2 in the paper. However, in our case, this assumption is naturally satisfied because all the random variables involved are bounded. Specifically, as  $f$ is bounded ($f<a$), the loss function $l$, for which we apply the Efron-Stein inequality through Lemma 2 (Eq. 65  or Eq 82), is also bounded ($l<a$ see Eq. 190-191 ). Since any bounded random variable is square-integrable, this guarantees that the assumption is met. Formally, we have: \\\n$$ |l| \\leq a. $$\n To verify square-integrability, we need to show that\n$\\mathbb{E}[l^2] < \\infty$.\nSince $l$ is bounded. We have\n$$ X^2 \\leq a^2$$\nTaking expectations on both sides,\n$$ \\mathbb{E}[l^2] \\leq \\mathbb{E}[a^2] = a^2 < \\infty. $$\nThus, our loss is always square-integrable. Therefore, the conditions for applying the Efron-Stein inequality are fully satisfied in our setting. \n\nWe will include this clarification and add the assumption explicitly to Lemma 2 in the revised version of the paper to ensure completeness.  Given that this addresses your concern, we kindly ask you to reconsider your score. We appreciate your openness to revisiting your evaluation and would be happy to discuss any further points if needed.\n\n## Related work:\n\nThank you for highlighting the related work on generalization guarantees in fair machine learning. We will address these references in the revision. \nHowever, while (Woodworth et al., 2017; Agarwal et al., 2018) derive generalization guarantees for loss functions corresponding to DP and EO within specific algorithms, our work targets a more general algorithmic framework in the DP and EO setting—even when using other loss functions. Moreover, their guarantees primarily focus on overall sample complexity, whereas our bounds incorporate not only the total sample size but also additional factors such as the properties of the learning algorithm, the particular loss function, the dataset characteristics, and, importantly, the group balance in the dataset. \n\nMore closely related work is Oneto et al. (2019), which derives a generalization bound in Theorem 1 for fairness generalization with randomized algorithms. However, their bound, being a KL-divergence bound, can not be computed and evaluated in practice for any realistic setting. In contrast, our bounds—particularly Theorem 5—are computable, even for modern deep neural networks. This ensures that our results are not only theoretically rigorous but also practical and computable, allowing us to study fairness generalization errors in real-world settings.\nWe will incorporate this discussion into the paper and revise our claim accordingly.\n\nThank you for catching the typos. We will fix all these typos and the flipped axis labels iof the Figure in the final version.", "claims_and_evidence": "The proposed fairness definitions do not seem to match the usual ones in the multiclass case:\n- The fairness definition considered in Equation (1) for demographic parity seems to assume binary classes (at least to match the usual demographic parity definition, see the work of Agarwal et al. 2018 for example). However, in the paper, it is assumed that the predictions lie in a range $[0,a]$ which suggests a multi-label predictions setting, it is then not clear what the proposed formula really represents.\n- To match the definition of equalized odds, $f$ should be the probability of having a positive label given a sample. While this initially fits the setup proposed in the paper (line 320, 1st column), it is later mentioned that it is possible to extend the proposed approach to the multiclass case by considering $f$ in $[0,a]$ (line 365, second column). It is then not clear what this measure really represents.", "methods_and_evaluation_criteria": "The methods and evaluation criteria appear to be appropriate. This is mainly a theoretical paper and complete proofs are provided.", "theoretical_claims": "I only skimmed through the proof of Lemma 2 as it is one of the central results of the paper:\n- The Efron-Stein inequality (Boucheron et al. 2013, Theorem 3.1) assumes that the function $g$ is square-integrable. However, this assumption is not mentioned in the paper and it is never formally proved that the considered functions respect this assumption.", "experimental_designs_or_analyses": "To improve fairness, the paper proposes, in Section 6, to use a batch balancing approach. This is reminiscing of the work of Roh et al. (FairBatch: Batch Seleection for Model Fairness, 2021) and connections should be discussed.", "relation_to_broader_scientific_literature": "Line 191 to 198, it is mentioned that the proposed result is the first to link generalization error to group imbalance. However, this is something that already appears in previous fairness generalization bounds based on the VC dimension where the bound is smallest when all the groups have the same size (for example, see Woodworth et al. 2017 in the list of missing references).", "essential_references_not_discussed": "The related work, relegated to Appendix A, misses several works that addressed the problem of generalization guarantees in fair machine learning, albeit with different proof techniques. A non-exhaustive list:\n- Learning Non-Discriminatory Predictors, Woodworth et al., 2017\n- A Reductions Approach to Fair Classification, Agarwal et al., 2018\n- Randomized Learning and Generalization of Fair and Private Classifiers: from PAC-Bayes to Stability and Differential Privacy, Oneto et al, 2019", "other_strengths_and_weaknesses": "The intuition behind the Mutual Information terms appearing in the different bounds is hard to grasp as there is only very sporadic discussion on what they really capture and when they can be expected to be small or large. From the experiments in Figure 2, they seem rather large since the bound does not converge to $0$ but, instead, seems to reach a plateau when the number of examples exceeds $1500$.", "other_comments_or_suggestions": "- There is a notation mismatch between the main paper and the proof of Lemma 1 ($\\ell_E^F$ seems to become $F_E$ for example).\n- Line 161, second column, it should be $\\tilde{v}_i \\neq v_i$.\n- In the experiments, the plot at the bottom right of Figure 2 suggests that the actual generalization error is larger than the bound. This is probably due to inverted axis labels.", "questions_for_authors": "1. Is the square-integrability assumption to apply the Efron-Stein inequality respected?\n\nWould this concern be addressed in a satisfactory manner, I could increase my score. Furthermore, would the other reviews or the rebuttal show that I missed or misunderstood some key points, I would reconsider my stance.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: It seems like the reviewers are on the positive side on this paper and agree that the paper has merits and is worth being accepted at ICML. The rebuttal definitely seemed to help clarify things for the reviewers. Please incorporate the clarifications into the final version of the paper.    Also please be sure to effectively and clearly clarify in the final paper, the details regarding the clarifications raised by reviewer H2i8
Decision: Accept (poster)