# Intrinsic Fairness-Accuracy Tradeoffs under Equalized Odds

Meiyu Zhong Ravi Tandon  Department of Electrical and Computer Engineering
University of Arizona, Tucson, USA
E-mail: {meiyuzhong<EMAIL_ADDRESS>
###### Abstract

With the growing adoption of machine learning (ML) systems in areas like law
enforcement, criminal justice, finance, hiring, and admissions, it is
increasingly critical to guarantee the fairness of decisions assisted by ML.
In this paper, we study the tradeoff between fairness and accuracy under the
statistical notion of equalized odds. We present a new upper bound on the
accuracy (that holds for any classifier), as a function of the fairness
budget. In addition, our bounds also exhibit dependence on the underlying
statistics of the data, labels and the sensitive group attributes. We validate
our theoretical upper bounds through empirical analysis on three real-world
datasets: COMPAS, Adult, and Law School. Specifically, we compare our upper
bound to the tradeoffs that are achieved by various existing fair classifiers
in the literature. Our results show that achieving high accuracy subject to a
low-bias could be fundamentally limited based on the statistical disparity
across the groups.

##  I Introduction

Machine learning-based solutions are increasingly being implemented across
various sectors, including criminal justice, law enforcement, hiring, and
admissions. These systems have demonstrated remarkable predictive
capabilities. However, recent studies [1, 2, 3] indicate a significant
downside to data-driven approaches: bias in decision-making. To address this
problem, there is a vast amount of research focused on various concepts of
fairness [4, 5, 6], which mainly falls into three categories: (1) Group
Fairness [7, 8, 9] which requires that the subjects in the subgroups have an
equal probability of being assigned to the same predicted class. (2)
Individual Fairness [4, 6, 10] which requires that similar individuals
(measured by a domain specific similarity metric) should be treated similarly.
(3) Causality-based Fairness [11, 6]: which uses causality-based tools to
design notions of fairness.

In this paper, we focus on group fairness (also known as statistical
fairness). There are three types of statistical fairness notions which have
been widely studied: demographic parity (DP) [3, 4]; equalized odds (EO) [9,
5] and predictive rate parity (PP) [5]. DP requires that the classifier’s
decision be independent of the sensitive group attribute. The notion of DP
however suffers from two drawbacks: first, when the sensitive group attribute
is correlated with the class labels, this may rule out the perfect predictor
(and hurt accuracy) [12]; second, the fairness notion of DP does not take into
account the true label into account; if the distribution of data across
subgroups is uneven, then enforcing DP may be unfair to those individuals
which were worthy of a positive outcome. To avoid such disparity, the notion
of Equalized Odds (EO) requires the classifier’s prediction should be
independent of sensitive attributes given the true class label. In addition,
Predictive Rate Parity (PP) is defined as the condition where different groups
have equal predictive values, meaning that the probability of a true positive
(or negative) result is consistent across all groups.

The techniques for learning a fair classifier subject to one of the group
fairness notions can be mainly divided into three categories: (1) Pre-
processing methods [2], which focus on mitigating bias by altering the
training data (e.g., by creating a more balanced or fair dataset) before it is
utilized in the training phase. (2) In-processing methods [3, 13], which
involve integrating fairness constraints directly into the model training
process (for instance, via explicit fairness aware regularization). (3) Post-
processing methods [14], which entail adjusting the model’s parameters after
training. This technique involves fine-tuning the trained model to rectify any
unfair biases that may have been introduced during the training process.
However, experimental results [15, 3, 5, 9] have demonstrated, and recent
theoretical evidence [16, 17] has further confirmed, that there is often a
drop in accuracy when enforcing fairness constraints, when compared to
unconstrained training.

Overview of recent work on Fairness-Accuracy Tradeoffs: The above observations
motivate a theoretical treatment of the tradeoff between fairness and
accuracy. Recent works [16, 17, 18] have studied this tradeoff for the case of
demographic parity (DP), and have obtained bounds which quantify the minimal
drop in accuracy as a function of the fairness budget. Additionally, Dutta et
al. [19] employ mismatched hypothesis testing to demonstrate that there exist
distributions for which there is no trade-off between fairness and accuracy.
However, they also show that these trade-offs do exist in real-world datasets.
Wang et al. [20] suggest that randomized prediction methods might more
consistently meet equalized odds in classification (also see [21, 22, 23,
24]). Another line of works [17, 25] study fair Bayes-optimal classifiers
subject to equal opportunity (which is a related, but weaker notion than EO);
the idea herein is to change the Bayes-optimal classifier by designing
subgroup-specific decision thresholds to satisfy the fairness constraint.
Another research direction, as explored in [26], concentrates on determining
whether it’s possible to establish a bound on the accuracy of a given
classifier relative to its allocated fairness budget. However, these bounds
are intrinsically linked to the characteristics of the classifier itself and
do not directly give an insight to the fundamental fairness-accuracy tradeoff.

Main Contributions. In this paper, we focus on the problem of binary ($0/1$)
classification subject to equalized odds (EO) fairness constraints and present
a new upper bound on the accuracy as a function of the fairness budget. Our
bounds are classifier-independent (i.e., they must hold for any classifier)
and are determined by the underlying statistics of the data, labels, and
sensitive groups. Our primary technique for deriving these bounds involves
adapting Le Cam’s bound [27, 28], which is traditionally used for binary
classification problems; encompassing the Equalized Odds (EO) fairness
constraints. The original Le Cam’s bound is based on the total variation
distance between two class distributions (i.e., $d_{TV}(P_{0},P_{1})$). Our EO
constrained bound depends on the total variation distances within sensitive
subgroups (i.e., $d_{TV}(P_{0}^{a},P_{1}^{a}),d_{TV}(P_{0}^{b},P_{1}^{b})$,
where $a,b$ denotes the two subgroups), as well as the relative proportions of
the subgroups. The extent of statistical discrepancy across the subgroups
plays a critical role in influencing the behavior of our bound. As the
subgroup discrepancy increases, our bound becomes tighter compared to the
classical Le Cam’s bound.

We also present experimental results using three real-world datasets: COMPAS,
Adult, and the Law School dataset. We estimate our bounds for these datasets
by employing an estimator for the total variation distance. Additionally, we
compare our upper bounds with the trade-offs between fairness and accuracy
achieved by various fair classifiers on these datasets.

##  II Preliminaries and Problem Statement

We consider a supervised classification problem, where we are given a dataset
of $n$ users: ${\\{x_{i},\;y_{i},\;z_{i}\\}}_{i=1}^{n}$, where
$x_{i}\in\mathcal{X}\subseteq\mathbb{R}^{d}$ denotes the set of features of
$i$th training sample; $y_{i}\in\mathcal{Y}=\\{0,1\\}$ represents the
corresponding binary class label; $z_{i}\in\mathcal{Z}=\\{a,b\\}$ denotes the
set of binary sensitive attributes of $i$th training sample, which depends on
the dataset and underlying context. For instance, if we consider gender as a
sensitive attribute (or subgroup), we could designate $a$ to represent females
and $b$ to represent males. Consider a classifier $f$ which maps from input
data space to output labels: $f:\mathcal{X}\rightarrow\mathcal{Y}$, i.e.,
$f(x)\in\\{0,1\\}$ denotes the classifier’s decision for an input $x$.

Notation: For the scope of this paper, we use capital letters to represent the
random variables/vectors ($X,Y,Z$) and use lowercase letters ($x,y,z$) to
denote a specific realization. We next define the following quantities which
will appear in our results:

  * •

$\alpha=\mathbb{P}(Y=1)$ (probability of the label $Y=1$).

  * •

$\beta=\mathbb{P}(Z=a)$ (probability of sensitive attribute $Z=a$).

  * •

$\phi(x)=\mathbb{P}(Y=1|x)$ (posterior probability of class $1$)

  * •

$P(x)$ represents the unconditional PDF of $X$.

  * •

$P_{0}(x)$ (respectively, $P_{1}(x)$) represents the conditional PDF of
$X|Y=0$ (respectively, $X|Y=1$).

  * •

$P^{a}_{0}(x)$ (respectively, $P^{b}_{0}(x)$) represents the conditional PDF
of $X|(Y=0,Z=a)$ (respectively, $X|(Y=0,Z=b)$). Similarly, $P^{a}_{1}(x)$
(respectively, $P^{b}_{1}(x)$) represents the conditional PDF of $X|(Y=1,Z=a)$
(respectively, $X|(Y=1,Z=b)$).

Problem Statement From the scope of this paper, our goal is to explore
tradeoff between fairness and accuracy for any classifier. We mainly focus on
the group fairness notion: equalized odds, which is defined as follows.

######  Definition 1.

(Approximate Equalized Odds) A binary classifier $f$ satisfies
$\epsilon_{EO}$-Equalized Odds (EO) if $\Delta_{EO}\leq\epsilon_{EO}$, where,
for $y\in\\{0,1\\}$, $\Delta_{EO}:=$

$\displaystyle\underset{y}{\max}|\mathbb{P}(f(X)=1|Z=a,Y=y)-\mathbb{P}(f(X)=1|Z=b,Y=y)|.$

When $\epsilon_{EO}=0$, the input $X$’s prediction $f(X)$ is conditionally
independent of its sensitive attribute $Z$ given the label $Y$ (equivalent to
the Markov chain $f(X)\rightarrow Y\rightarrow Z$) which corresponds to the
notion of perfect equalized odds [7, 5]. Following prior works, [29, 13, 5],
we focus on the approximate EO setting, $\Delta_{EO}\leq\epsilon_{EO}$, and
$\epsilon_{EO}$ refers to the fairness budget.

######  Definition 2.

(Total Variation (TV) Distance) Consider P and Q as two probability
distributions over a common probability space $\Omega$. Then, the total
variation distance between them, denoted $d_{TV}(P,Q)$, is defined as follows

$\displaystyle
d_{TV}(P,Q)=\underset{A\subseteq\Omega}{\text{sup}}|P(A)-Q(A)|=\frac{1}{2}\int_{x}|P(x)-Q(x)|dx$

##  III Main Results and Discussion

In this section, we present our main results on the fundamental trade-off
between fairness constraints (subject to EO) and accuracy for binary
classification. Our results are organized as follows. First, we present an
upper bound on accuracy based on Le Cam’s method without any fairness
constraint. This bound is attainable by the Bayes optimal classifier for three
cases: when the class distribution is either balanced $\alpha=0.5$ or
extremely unbalanced $\alpha=0/1$. We then present the main result of this
paper: a new classifier-independent upper bound on accuracy as a function of
the EO budget $(\epsilon_{EO})$, taking into account the underlying statistics
of the data, labels, and the proportions of subgroups.

We first present an upper bound on the accuracy for any arbitrary binary
classifier, which is given as follows:

######  Theorem 1.

(Unconstrained Upper Bound on Accuracy) For any binary classifier $f$, its
accuracy $Acc(f)$ satisfies $\text{Acc}(f)\leq\overline{\text{Acc}}$, where
$\overline{\text{Acc}}$ is given as follows:

$\displaystyle\overline{\text{Acc}}=\max(1-\alpha,\alpha)+\min(1-\alpha,\alpha)\cdot
d_{TV}(P_{1},P_{0}).$ (1)

Furthermore, the upper bound can be attained by the Bayes optimal classifier
when $\alpha=0,0.5$ or $1$.

Figure 1: (a) Illustration of the relationship between Theorem 1 and Theorem
2, where the red dotted line represents the bound established in Theorem 1,
while the orange fluorescent line depicts the minimum of the two functions
$T_{1}$ and $T_{2}$ in Theorem 2, where $T_{1}$ and $T_{2}$ have slopes of
$1-\beta$ and $\beta$, respectively. (b) Dataset-related parameters and upper-
bound-related parameters in the real world datasets: COMPAS, Adult and Law
School dataset.

We can draw the following insights from the above result: for a fixed value of
$\alpha$, accuracy is directly proportional to $d_{TV}(P_{1},P_{0})$. On the
other hand, for a fixed value of $d_{TV}(P_{1},P_{0})$, the lowest accuracy
occurs when $\alpha=0.5$, i.e., when both the classes $0/1$ appear in a
balanced manner. We next present the proof of the above result, which will
allow us to contrast the corresponding bounds we obtain subject to equalized
odds fairness constraints.

###### Proof.

We expand the expression for accuracy of a binary classifier using total
probability theorem as follows:

$\displaystyle\text{Acc}(f)=E_{(X,Y)}[\mathbbm{1}(f(X)=Y)]=\mathbb{P}(f(X)=Y)$
$\displaystyle=\mathbb{P}(Y=1,f(X)=1)+\mathbb{P}(Y=0,f(X)=0)$
$\displaystyle=\alpha\mathbb{P}(f(X)=1|Y=1)+(1-\alpha)\mathbb{P}(f(X)=0|Y=0)$
(2)

We can re-write the above expression for $Acc(f)$ in two different ways as
follows, where $\text{Acc}(f)$

$\displaystyle\overset{(a)}{=}\alpha\mathbb{P}(f(X)=1|Y=1)+(1-\alpha)(1-\mathbb{P}(f(X)=1|Y=0))$
$\displaystyle\overset{(b)}{=}\alpha(1-\mathbb{P}(f(X)=0|Y=1))+(1-\alpha)\mathbb{P}(f(X)=0|Y=0)$

We now consider two scenarios based on the value of $\alpha$. In the first
case, when $\alpha\leq 0.5$, we use the expression in $(a)$ and upper bound it
as follows:

$\displaystyle\text{Acc}(f)\leq
1-\alpha+\alpha(\mathbb{P}(f(X)=1|Y=1)-\mathbb{P}(f(X)=1|Y=0))$
$\displaystyle\leq
1-\alpha+\underset{f}{\text{sup}}~{}\alpha(\mathbb{P}(f(X)=1|Y=1)-\mathbb{P}(f(X)=1|Y=0))$
$\displaystyle\leq
1-\alpha+\alpha~{}\underset{f}{\text{sup}}~{}|\mathbb{P}(f(X)=1|Y=1)-\mathbb{P}(f(X)=1|Y=0)|$
$\displaystyle=1-\alpha+\alpha\cdot d_{TV}(P_{0},P_{1}).$ (3)

Similarly, for the case when $\alpha>0.5$, we use the expression in $(b)$ and
bound it in a similar manner to arrive at

$\displaystyle Acc(f)\leq\alpha+(1-\alpha)\cdot d_{TV}(P_{1},P_{0})$ (4)

Combining (3) and (4), we obtain the upper bound stated in the Theorem 1:

$\displaystyle Acc(f)\leq\max(\alpha,1-\alpha)+\min(\alpha,1-\alpha)\cdot
d_{TV}(P_{1},P_{0}).$

Let us now consider the Bayes optimal classifier:

$\displaystyle f_{\text{Bayes}}(x)=\begin{cases}1,&\text{if}~{}~{}\phi(x)\geq
1-\phi(x)\\\ 0,&\text{otherwise}.\end{cases}$ (5)

where $\phi(x)=\mathbb{P}(Y=1|X=x)$. The accuracy of Bayes optimal classifier
can be readily computed as:

$\displaystyle
Acc(f_{\text{Bayes}})=\mathbbm{E}_{X}\left[\text{max}(\phi(X),1-\phi(X))\right]$
(6)
$\displaystyle=\frac{1}{2}+\frac{1}{2}\int_{x}|\alpha\mathbb{P}(x|y=1)-(1-\alpha)\mathbb{P}(x|y=0)|dx$
(7)

It is straightforward to verify that the Bayes’ classifier accuracy matches
with our upper bound when $\alpha=0.5,0~{}\text{or}~{}1$. This completes the
proof of Theorem 1. ∎

We next present our main result, which is an upper bound on accuracy as a
function of the fairness budget $\epsilon_{EO}$.

######  Theorem 2.

For any binary classifier which satisfies equalized odds
($\Delta_{EO}\leq\epsilon_{EO}$), its accuracy $\text{Acc}(f,\epsilon_{EO})$
satisfies
$\text{Acc}(f,\epsilon_{EO})\leq\overline{\text{Acc}}(\epsilon_{EO})$, where
$\overline{\text{Acc}}(\epsilon_{EO})$ is given as follows:

$\displaystyle\overline{\text{Acc}}(\epsilon_{EO})=\max(1-\alpha,\alpha)+\min(T_{1},T_{2}),\vspace{-8pt}$
(8)

where

$\displaystyle T_{1}$ $\displaystyle\triangleq\min(1-\alpha,\alpha)\cdot
d_{TV}(P^{b}_{1},P^{b}_{0})+\beta\epsilon_{EO}$ (9) $\displaystyle T_{2}$
$\displaystyle\triangleq\min(1-\alpha,\alpha)\cdot
d_{TV}(P^{a}_{1},P^{a}_{0})+(1-\beta)\epsilon_{EO}.$ (10)

We next present a sequence of remarks which give an operational interpretation
of the above bound.

######  Remark 1.

We note that the upper bound is a piece-wise linear function of the fairness
budget $\epsilon_{EO}$, and obtained as a minimum over two expressions related
to $T_{1},T_{2}$ as shown in Fig. 1(a). The expressions in $T_{1}$ depend upon
the $d_{TV}(P^{b}_{1},P^{b}_{0})$, which reflect the difference in the class
conditional probabilities for subgroup $b$. Similarly, the bound in $T_{2}$
depends on $d_{TV}(P^{a}_{1},P^{a}_{0})$, which reflects the difference in the
class conditional probabilities for subgroup $a$. When $\epsilon_{EO}=0$,
i.e., perfect EO fairness constraint, the upper bound shows that the accuracy
of any classifier will always be limited by the minimum of
$d_{TV}(P^{b}_{1},P^{b}_{0})$ and $d_{TV}(P^{a}_{1},P^{a}_{0})$, i.e., the
subgroup with the worst classification accuracy.

######  Remark 2.

For the case when $\epsilon_{EO}>0$, i.e., approximate EO fairness constraint,
the bound is given by the minimum over two linear functions of
$\epsilon_{EO}$. The slopes of these two lines are given by $\beta=P(Z=a)$,
and $1-\beta=P(Z=b)$, i.e., relative proportion/size of the two subgroups
shown in Fig. 1 (a). The interplay between $(\beta,1-\beta)$ and the subgroup
wise statistical distances dictate the overall behaviour of the upper bound.
For instance, suppose subgroup $a$ is a minority group with $\beta<<1-\beta$,
then there always exists a threshold $\epsilon_{EO}$, for which the
classification accuracy will be dictated by the statistical distance
corresponding to the majority subgroup $b$.

######  Remark 3.

In the next sub-section, we discuss a methodology to estimate the upper bounds
for real-world datasets by leveraging tools for statistical estimation of
$f$-divergence (e.g., TV distance). In Fig. 1(b), we show the corresponding
experimental results we obtained on three datasets (COMPAS, Law-School
admissions and Adult Income prediction). Specifically, for each of these
datasets, we estimate the corresponding values of
$\beta,\alpha,d_{TV}(P_{0},P_{1}),d_{TV}(P^{a}_{0},P^{a}_{1})~{}\text{and}~{}d_{TV}(P^{b}_{0},P^{b}_{1})$
from the datasets and then show the bounds obtained from the two Theorems. We
show the corresponding bounds for $\epsilon_{EO}=0$ and for
$\epsilon_{EO}=0.05$ (more experiments are presented in the next Section).
Specifically, we can observe the estimated bound from Theorem 1 (corresponding
to unconstrained classifiers) is always larger than those provided by Theorem
2 (the upper bound on accuracy with EO constraints), as well as the interplay
between the statistical properties, namely $\beta,1-\beta$ and the statistical
disparity across the two subgroups.

We next present the proof of Theorem 2.

###### Proof.

Figure 2: Comparison of the upper bound of the test accuracy in real world
datasets: (a) COMPAS dataset, (b) Adult dataset, (c) Law School dataset under
three fair classifiers ($C_{1}$ [15], $C_{2}$ [30] and $C_{3}$ [5]). We can
observe that Theorem 2 is consistently tighter than the unconstrained upper
bound (Theorem 1), and Theorem 2 provides the tightly upper bound on the
tradeoffs achieved by three classifiers for three real world datasets.

To simplify the notation used in the proof, we denote
$\eta=\mathbb{P}(Z=a|Y=1)$ and denote $\gamma=\mathbb{P}(Z=a|Y=0)$. We start
by the definition of the total accuracy of the binary classifier using total
probability theorem as follows:

$\displaystyle\text{Acc}(f)=E_{(X,Y)}[\mathbbm{1}(f(X)=Y)]=\mathbb{P}(f(X)=Y)$
$\displaystyle=\alpha\mathbb{P}(f(X)=1|Y=1)+(1-\alpha)\mathbb{P}(f(X)=0|Y=0)$
(11)
$\displaystyle\overset{(a)}{=}\alpha\mathbb{P}(f(X)=1|Y=1)+(1-\alpha)(1-\mathbb{P}(f(X)=1|Y=0))$
$\displaystyle\overset{(b)}{=}\alpha(1-\mathbb{P}(f(X)=0|Y=1))+(1-\alpha)\mathbb{P}(f(X)=0|Y=0)$

Then we further apply total probability theorem on $\mathbb{P}(f(X)=1|Y=1)$
with respect to $Z$ in $(a)$. Therefore, we can express
$\mathbb{P}(f(X)=1|Y=1)$ as follows:

$\displaystyle\eta\mathbb{P}(f(X)=1|Y=1,Z=a)+(1-\eta)\mathbb{P}(f(X)=1|Y=1,Z=b)$

Similarly, we can also take the advantage of total probability theorem on
$\mathbb{P}(f(X)=1|Y=0)$ with respect to $Z$ in $(a)$, where
$\mathbb{P}(f(X)=1|Y=0)$ can be written as:

$\displaystyle\gamma\mathbb{P}(f(X)=1|Y=0,Z=a)+(1-\gamma)\mathbb{P}(f(X)=1|Y=0,Z=b)$

Since the classifier satisfies the fairness constraints
$\Delta_{EO}\leq\epsilon_{EO}$, we have:

$\displaystyle|\mathbb{P}(f(X)=1|Y=1,Z=a)-\mathbb{P}(f(X)=1|Y=1,Z=b)|\leq\epsilon_{EO}$
$\displaystyle|\mathbb{P}(f(X)=1|Y=0,Z=a)-\mathbb{P}(f(X)=1|Y=0,Z=b)|\leq\epsilon_{EO}.$

By incorporating the above inequalities, we can bound $\mathbb{P}(f(X)=1|Y=1)$
and $\mathbb{P}(f(X)=1|Y=0)$ as follows:

$\displaystyle\mathbb{P}(f(X)=1|Y=1)\leq\eta\epsilon_{EO}+\mathbb{P}(f(X)=1|Y=1,Z=b)$
(12)
$\displaystyle\mathbb{P}(f(X)=1|Y=0)\geq-\gamma\epsilon_{EO}+\mathbb{P}(f(X)=1|Y=0,Z=b).$
(13)

By plugging (12) and (13) into (a), the total accuracy can be bounded by:

$\displaystyle\text{Acc}(f)$
$\displaystyle\leq(1-\alpha)+\alpha\mathbb{P}(f(X)=1|Y=1,Z=b)$
$\displaystyle\hskip
5.0pt-(1-\alpha)\mathbb{P}(f(X)=1|Y=0,Z=b)+\beta\epsilon_{EO},$ (14)

where $\beta=\alpha\eta+(1-\alpha)\gamma=P(Z=a)$. Similar to the proof of
Theorem 1, we next consider two cases with respect to $\alpha$. If $\alpha\leq
0.5$, then (14) can be further upper bounded by taking a supremum over $f$. We
thus arrive at the following:

$\displaystyle\text{Acc}(f)\leq(1-\alpha)+\beta\epsilon_{EO}+$
$\displaystyle\alpha\cdot\underset{f}{\text{sup}}~{}|\mathbb{P}(f(X)=1|Y=1,Z=b)-\mathbb{P}(f(X)=1|Y=0,Z=b)|$
$\displaystyle=(1-\alpha)+\alpha
d_{TV}(P_{1}^{b},P_{0}^{b})+\beta\epsilon_{EO}.$ (15)

When $\alpha>0.5$, we focus on (b), where we derive the upper bound subject to
accuracy following the same steps above as (a). we arrive at the upper bound:

$\displaystyle\text{Acc}(f)\leq\alpha+(1-\alpha)\cdot
d_{TV}(P_{1}^{b},P_{0}^{b})+\beta\epsilon_{EO}.$ (16)

To this end, combining two inequalities (15) and (16), we have the upper bound
of accuracy as a function of $\epsilon_{EO}$ with respect to the subgroup
$Z=b$ and the proportion of another subgroup $Z=a$, which can be compactly
written as:

$\displaystyle\max(\alpha,1-\alpha)+\min(\alpha,1-\alpha)\cdot
d_{TV}(P_{1}^{b},P_{0}^{b})+\beta\epsilon_{EO}$

Note that we can also bound $\mathbb{P}(f(X)=1|Y=1),~{}\mathbb{P}(f(X)=1|Y=0)$
and $\mathbb{P}(f(X)=0|Y=1),\mathbb{P}(f(X)=0|Y=0)$ by another subgroup $Z=a$
in (12) and (13). By doing so, we arrive at another upper bound of accuracy as
a function of $\epsilon_{EO}$ with respect to the subgroup $Z=a$ and the
proportion of another subgroup $Z=b$, which can be expressed as:

$\displaystyle\max(\alpha,1-\alpha)+\min(\alpha,1-\alpha)\cdot
d_{TV}(P_{1}^{a},P_{0}^{a})+(1-\beta)\epsilon_{EO}$

Combining the two upper bounds, we arrive at Theorem 2. ∎

Estimation of Upper Bounds. We next describe a methodology for estimating the
upper bounds for real-world datasets. For Theorem 1 and Theorem 2, estimating
the fraction of the label or sensitive group (i.e., $\alpha$, $\beta$) are
quite straightforward. In addition, in order to obtain estimates of these
bounds, we need an estimate of
$d_{TV}(P_{1},P_{0}),d_{TV}(P_{1}^{a},P_{0}^{a})$, and
$d_{TV}(P_{1}^{b},P_{0}^{b})$. To this end, we can leverage the fact that TV
distance between two distributions is a special case of $F$-divergence, which
is known to admit a variational representation [31, 32] expressed as follows:

$\displaystyle D_{f}(P\parallel Q)=\underset{T(\cdot)}{sup}~{}E_{X\sim
P}\left[T(X)\right]-E_{X\sim Q}\left[f^{*}(T(X))\right],$ (17)

where the function $f^{\ast}(t)=\underset{x\in dom_{f}}{sup}\\{xt-f(x)\\}$
denotes the convex conjugate (also known as the Fenchel conjugate) of the
function $f$. The above variational representation involves a supremum over
all possible functions $T(\cdot)$. We can obtain an estimate for TV distance
by replacing the supremum over a restricted class of functions. Specifically,
if we use a parametric model $T_{\theta}$, (e.g., a neural network) with
parameters $\theta$, then taking the supremum over the parameters $\theta$
yields a lower bound on $F$-divergence in (17) as stated next:

$\displaystyle D_{f}(P\parallel Q)\geq\underset{\theta}{sup}\hskip
1.0ptE_{X\sim P}\left[T_{\theta}(X)\right]-E_{X\sim
Q}\left[f^{*}(T_{\theta}(X))\right].$ (18)

We use the above variational lower bound to estimate the TV distance as
described next. Take the $d_{TV}(P_{1},P_{0})$ as an example, we need to
estimate TV distance between joint distributions of feature $X$ in different
class. The variational lower bound on $F$-divergence in (18) can then be
estimated as:

$\displaystyle\underset{\theta}{\max}\frac{1}{M}\left(\sum_{m=1}^{M}T_{\theta}\left(X_{1}^{(m)}\right)-\sum_{m=1}^{M}f^{\ast}\left(T_{\theta}\left(X_{0}^{(m)}\right)\right)\right),$
(19)

where in (19), we have replaced the expectation operators with their empirical
estimates, and $\\{X_{1}^{(m)}\\}$ (respectively, $\\{X_{0}^{(m)}\\}$) denote
i.i.d. samples drawn from the distribution $P_{1}$ (respectively, $P_{0}$).
The consistency and convergence of the above estimator to the true divergence
has been studied in [31] under some mild assumptions. For our experiments, we
modeled $T_{\theta}$ using two-layer neural networks, each with $10$ hidden
nodes and followed by a sigmoid non-linearity activation layer.

##  IV Experiments

In this section, we show the experimental results to verify the tightness of
our theoretical bounds. We consider three real world datasets: COMPAS, Adult
and Law school admission dataset. We describe the dataset as follows: a)
COMPAS Dataset: This dataset consists of data from $N=7,214$ users
($N_{train}=5,049$, $N_{test}=2,165$), with 10 features (including age, prior
criminal history, charge degree etc.) which are used for predicting the risk
of recidivism in the next two years. b) Adult Dataset: This dataset includes
income related data with 14 features (i.e., age, work class, occupation,
education etc.) of $N=45,222$ users ($N_{train}=32,561$, $N_{test}=12,661$) to
predict whether the income of a person exceeds a threshold (e.g., $50k) in a
year. c) Law School Dataset: This dataset includes the admission related data
with 7 features (LSAT score, gender, undergraduate GPA etc.) of $N=4,862$
applicants ($N_{train}=3,403$, $N_{test}=1,459$) to predict the likelihood of
passing the bar. For all the above datasets, we use race as the sensitive
attribute. Specifically we consider the situation when $|Z|=2,Z\in\\{C,O\\}$,
where $C=\text{``Caucasian"}$ or $O=\text{``Other race"}$, corresponding to
two groups.

For the methodology of training a fair classifier, we applied three in-
processing mechanisms: (a) Zafar er al. [5] ($C_{3}$ (Covariance)) employ the
covariance between sensitive attributes and the signed distance from
misclassified data’s feature vectors to the classifier decision boundary as a
regularization term. (b) Bechavod et al. [30] ($C_{2}$ (FNR-FPR)) use the
differences in False Negative Rate (FNR) and False Positive Rate (FPR) across
subgroups as the regularization term. (c) Zhong et al. [15] ($C_{1}$
(F-divergence)) propose the F-divergence between the conditional probability
of predictions among subgroups as the regularization term. For the above
mechanisms, they added fairness constraints (covariance, FNR-FPR,
F-divergence) as a regularization in the loss function to learn a fair
classifier subject to equalized odds.

Fig 2 shows the corresponding tradeoffs achieved by the three fair classifiers
as the budget $\epsilon_{EO}$ is increased; we also show the upper bounds of
Theorems 1 and 2 as a function of $\epsilon_{EO}$. Notably, our upper bound
incorporating EO constraints (Theorem 2) is tighter compared to the accuracy
upper bound without fairness constraints (Theorem 1). Additionally, it is
observed that Theorem 2 closely approximates the upper bound of the
classifier’s test accuracy under varying EO constraints, until it aligns with
Theorem 1. Our experimental findings reinforce the validity of our theorems,
demonstrating a tight correlation between the trade-offs in fairness and
accuracy. These results not only align with the trends predicted by our
theorems but also underscore the practical applicability of the theoretical
framework in diverse real-world scenarios.

##  V Conclusion

We presented a new upper bound on accuracy for binary classification subject
to equalized odds, where the fairness budget is measured by $\epsilon_{EO}$.
Our results show that in addition to the fairness budget, relative subgroup
sizes $(\beta,1-\beta)$ as well as the statistical differences across
subgroups (measured by
$d_{TV}(P_{1}^{a},P_{0}^{a}),d_{TV}(P_{1}^{b},P_{0}^{b})$) impose a
fundamental limit on the accuracy. We also validated these bounds using
empirical estimation of TV-distance and compared them with the tradeoffs
achieved by various fair classifiers. There are several directions for future
work including generalization to other notions of statistical fairness (such
as predictive parity); furthermore, it would be interesting to use the upper
bounds as a guideline for designing fair classifiers (such as design of group-
wise thresholding rules which maximize accuracy).

## Acknowledgment

This work was supported by NSF grants CCF 2100013, CNS 2209951, CCF 1651492,
CNS 2317192, CNS 1822071 and U.S. Department of Energy, Office of Science,
Office of Advanced Scientific Computing under Award Number DE-SC-ERKJ422, and
by NIH through Award 1R01CA261457-01A1.

## References

  * [1] N. Mehrabi, F. Morstatter, N. Saxena, K. Lerman, and A. Galstyan, “A survey on bias and fairness in machine learning,” ACM Computing Surveys (CSUR), vol. 54, no. 6, pp. 1–35, 2021.
  * [2] R. Zemel, Y. Wu, K. Swersky, T. Pitassi, and C. Dwork, “Learning fair representations,” in International Conference on Machine Learning, pp. 325–333, PMLR, 2013.
  * [3] M. B. Zafar, I. Valera, M. G. Rogriguez, and K. P. Gummadi, “Fairness constraints: Mechanisms for fair classification,” in Artificial Intelligence and Statistics, pp. 962–970, PMLR, 2017.
  * [4] C. Dwork, M. Hardt, T. Pitassi, O. Reingold, and R. Zemel, “Fairness through awareness,” in Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pp. 214–226, 2012.
  * [5] M. B. Zafar, I. Valera, M. Gomez Rodriguez, and K. P. Gummadi, “Fairness beyond disparate treatment & disparate impact: Learning classification without disparate mistreatment,” in Proceedings of the 26th International Conference on World Wide Web, pp. 1171–1180, 2017.
  * [6] M. J. Kusner, J. Loftus, C. Russell, and R. Silva, “Counterfactual fairness,” in Advances in Neural Information Processing Systems (I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, eds.), vol. 30, Curran Associates, Inc., 2017.
  * [7] S. Barocas and A. D. Selbst, “Big data’s disparate impact,” Calif. L. Rev., vol. 104, p. 671, 2016.
  * [8] M. Feldman, S. A. Friedler, J. Moeller, C. Scheidegger, and S. Venkatasubramanian, “Certifying and removing disparate impact,” in proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 259–268, 2015.
  * [9] M. Hardt, E. Price, and N. Srebro, “Equality of opportunity in supervised learning,” Advances in Neural Information Processing Systems, vol. 29, 2016.
  * [10] M. Yurochkin, A. Bower, and Y. Sun, “Training individually fair ML models with sensitive subspace robustness,” in International Conference on Learning Representations, 2020.
  * [11] N. Kilbertus, M. Rojas Carulla, G. Parascandolo, M. Hardt, D. Janzing, and B. Schölkopf, “Avoiding discrimination through causal reasoning,” Advances in Neural Information Processing Systems, vol. 30, 2017.
  * [12] S. Barocas, M. Hardt, and A. Narayanan, Fairness and machine learning: Limitations and opportunities.  MIT Press, 2023.
  * [13] J. Cho, G. Hwang, and C. Suh, “A fair classifier using mutual information,” in 2020 IEEE International Symposium on Information Theory (ISIT), pp. 2521–2526, IEEE, 2020.
  * [14] G. Pleiss, M. Raghavan, F. Wu, J. Kleinberg, and K. Q. Weinberger, “On fairness and calibration,” Advances in Neural Information Processing Systems, vol. 30, 2017.
  * [15] M. Zhong and R. Tandon, “Learning fair classifiers via min-max f-divergence regularization,” in 2023 59th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1–8, IEEE, 2023.
  * [16] H. Zhao and G. J. Gordon, “Inherent tradeoffs in learning fair representations,” The Journal of Machine Learning Research, vol. 23, no. 1, pp. 2527–2552, 2022.
  * [17] X. Zeng, E. Dobriban, and G. Cheng, “Bayes-optimal classifiers under group fairness,” arXiv preprint arXiv:2202.09724, 2022.
  * [18] A. K. Menon and R. C. Williamson, “The cost of fairness in binary classification,” in Conference on Fairness, accountability and transparency, pp. 107–118, PMLR, 2018.
  * [19] S. Dutta, D. Wei, H. Yueksel, P.-Y. Chen, S. Liu, and K. Varshney, “Is there a trade-off between fairness and accuracy? a perspective using mismatched hypothesis testing,” in International Conference on Machine Learning, pp. 2803–2813, PMLR, 2020.
  * [20] H. Wang, L. He, R. Gao, and F. Calmon, “Aleatoric and epistemic discrimination: Fundamental limits of fairness interventions,” in Thirty-seventh Conference on Neural Information Processing Systems, 2023.
  * [21] Z. Tang and K. Zhang, “Attainability and optimality: The equalized odds fairness revisited,” in Conference on Causal Learning and Reasoning, pp. 754–786, PMLR, 2022.
  * [22] J. S. Kim, J. Chen, and A. Talwalkar, “Fact: A diagnostic for group fairness trade-offs,” in International Conference on Machine Learning, pp. 5264–5274, PMLR, 2020.
  * [23] F. Hamman and S. Dutta, “Demystifying local and global fairness trade-offs in federated learning using partial information decomposition,” arXiv preprint arXiv:2307.11333, 2023.
  * [24] S. Sabato and E. Yom-Tov, “Bounding the fairness and accuracy of classifiers from population statistics,” in International Conference on Machine Learning, pp. 8316–8325, PMLR, 2020.
  * [25] E. Chzhen, C. Denis, M. Hebiri, L. Oneto, and M. Pontil, “Leveraging labeled and unlabeled data for consistent fair binary classification,” Advances in Neural Information Processing Systems, vol. 32, 2019.
  * [26] H. Zhao, A. Coston, T. Adel, and G. J. Gordon, “Conditional learning of fair representations,” arXiv preprint arXiv:1910.07162, 2019.
  * [27] L. Le Cam, “On the asymptotic theory of estimation and testing hypotheses,” in Proceedings of the Third Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics, vol. 3, pp. 129–157, University of California Press, 1956.
  * [28] B. Yu, “Assouad, Fano, and Le Cam,” in Festschrift for Lucien Le Cam: research papers in probability and statistics, pp. 423–435, Springer, 1997.
  * [29] J. Cho, G. Hwang, and C. Suh, “A fair classifier using kernel density estimation,” Advances in Neural Information Processing Systems, vol. 33, pp. 15088–15099, 2020.
  * [30] Y. Bechavod and K. Ligett, “Learning fair classifiers: A regularization-inspired approach,” Workshop on Fairness, Accountability, and Transparency in Machine Learning (FAT/ML), 2017.
  * [31] X. Nguyen, M. J. Wainwright, and M. I. Jordan, “Estimating divergence functionals and the likelihood ratio by convex risk minimization,” IEEE Transactions on Information Theory, vol. 56, no. 11, pp. 5847–5861, 2010.
  * [32] X. Nguyen, M. J. Wainwright, and M. Jordan, “Estimating divergence functionals and the likelihood ratio by penalized convex risk minimization,” Advances in Neural Information Processing Systems, vol. 20, 2007.