Aleatoric and Epistemic Discrimination: Fundamental Limits of Fairness Interventions
Authors: Hao Wang
Luxi He
Rui Gao
Flavio Calmon
Venue: NeurIPS 2023 spotlight (2023)
Keywords: information theory
fair machine learning
TL;DR: https://github.com/Lumos23/aleatoric_epistemic_discrimination

Abstract: Machine learning (ML) models can underperform on certain population groups due to choices made during model development and bias inherent in the data. We categorize sources of discrimination in the ML pipeline into two classes: aleatoric discrimination, which is inherent in the data distribution, and epistemic discrimination, which is due to decisions made during model development. We quantify aleatoric discrimination by determining the performance limits of a model under fairness constraints, assuming perfect knowledge of the data distribution. We demonstrate how to characterize aleatoric discrimination by applying Blackwell's results on comparing statistical experiments. We then quantify epistemic discrimination as the gap between a model's accuracy when fairness constraints are applied and the limit posed by aleatoric discrimination. We apply this approach to benchmark existing fairness interventions and investigate fairness risks in data with missing values. Our results indicate that state-of-the-art fairness interventions are effective at removing epistemic discrimination on standard (overused) tabular datasets. However, when data has missing values, there is still significant room for improvement in handling aleatoric discrimination.

Aleatoric and Epistemic Discrimination: Fundamental Limits of Fairness Interventions
Hao Wang MIT-IBM Watson AI Lab hao@ibm.
Luxi (Luey) He Harvard College
luxihe@college. www.aarrdde...........
Rui Gao
Flavio Calmon
The University of Texas at Austin rui gaw@mccombs....ooooo utexas. edu
Harvard University flavio@seas. harvard.
Abstract
Machine learning (ML.) models can underperform on certain population groups due to choices made during model development and bias inherent in the data. We categorize sources discrimination in the ML pipeline into two classes; aleatoric discrimination, which is inherent in the data distribution, and epistemic discrimi- nation, which is due to decisions made during model development. We quantify aleatoric discrimination by determining the performance limits of model under fairness constraints, assuming perfect knowledge of the data distribution. We demonstrate how to characterize aleatoric discrimination by applying Blackwell's results on comparing statistical experiments. We then quantify epistemic dis- crimination the gap between model's accuracy when faireess constraints applied and the limit posed by aleatoric discrimination. We apply this approach benchmark existing fairness interventions and investigate fairness risks in data with missing values. Our results indicate that state-of-the-an fairness interventions are effective at removing epistemic discrimination on standard (overused) tabular datasets. However, when data has missing values, there is still significant room for improvement in handling aleatoric discrimination.
Introduction
Algorithmic discrimination may occur in different stages of the machine learning (ML) pipeline. For example, historical biases in the data-generating process can propagate downstream tasks; human biases can influence a MI. model through inductive bias; optimizing solely for accuracy can lead to disparate model performance across groups in the data (Suresh and Guttag, 2019; Mayson, 2019). The past years have seen a rapid increase in algorithmic interventions that aim to mitigate biases in ML models (see e.g., Zemel al., 2013; Feldman et al., 2015; Calmon al., 2017: Menon and Williamson, 2018; Zhang et al., 2018; Zafar et al., 2019; Friedler et al., 2019; Bellamy et al., 2019;
Kim al., 2019: Celis et al., 2019; Yang et al., 2020: Jiang and Nachum, 2020; Jiang al., 2020; Martinez et al., 2020; Lowy et al.. 2021; Alghamdi et al., 2022). A recent survey (Hort et al., 2022) found nearty 400 cainess-intervenneee algorithms, including 123 pre-pree pre-processing. 212 in-processing. and 56 post-processing algorithms introduced in the past decade.
Which sources of biases are (the hundreds of) existing fairness interventions trying control? In order to create effective strategies for reducing algorithmic discrimination, is critical to disentangle where biases in model performance originate. For instance, a certain population group has significantly more missing features in training data, then it is more beneficial to collect data than selecting more complex model class or training strategy. Conversely, if the model class does accurately represent
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the underlying distribution of a specific population group, then collecting more data for that group will not resolve performance disparities.
We divide algorithmic discrimination' ! into two categories: aleatoric and epistemic discrimination. 2 Aleatoric discrimination captures inherent biases in the data distribution that can lead to unfair decisions in downstream tasks. Epistemic discrimination, in turn, is due to algorithmic choices made during model development and lack of knowledge about the optimal "fair" predictive model.
In this paper, we provide methods for measuring aleatoric and epistemic discrimination in classifica- tion tasks for group fairness metrics. Since aleatoric discrimination only depends on properties of the data distribution and the faimnsss measure of choice, we quantify it by asking a fundamental question:
For a given data distribution, what is the best achievable performance (e.g.. accuracy) under set of group fairness constraints?
We refer to the answer the fairness Pareto frontier. This frontier delineates the optimal performance achievable by a classifier when unlimited data and computing power are available. For a fixed data distribution, the faimess Pareto frontier represents the ultimate, accuracy and group fairness beyond which no model can achieve. Characterizing this limit enables us to (i) separate sources of discrimination and create strategies to control them accordingly; (ii) evaluate the effectiveness of existing fairness interventions for reducing epistemic discrimination; and (iii) inform the development of data collection methods that promote fairness in downstream tasks.
limit for
At first, computing the fairness Pareto frontier can appear to an intractable problem since it requires searching over all possible classifiers-evei if the data distribution is known exactly. Our main technical contribution is to provide an upper bound estimate for this frontier by solving a sequence of optimization problems. The proof technique is based on Blackwell's seminal results (Blackwell, 1953), which proposed the notion of comparisons of statistical experiments and inspired a line of works introducing alternative comparison criteria (see e.g.. Shamnon, 1958; Cam, 1964; Torgersen, 1991; Cohen et al., 1998; Raginsky, 2011). Here, we apply these results to develop an algorithm that iteratively refines the achievable fairness Pareto frontier. We also prove convergence guarantees for our algorithm and demonstrate how it can be used to benchmark existing fairness interventions.
We quantify epistemic discrimination by comparing classifier's performance with the information- theoretic optimal given by the fairness Pareto frontier. Our experiments indicate that given sufficient data, sate-of-the-art (SOTA) group fairness interventions are effective reducing epistemic discrim- coeemaaton-thhooret limit is small (see Figure and 2). Consequently,
ination as their gap to the there are diminishing returns in benchmarking new fairness interventions on standard (overused) tabular datasets (e.g., UCI Adult and ProPublica COMPAS datasets). However, existing interventions do not eliminate aleatoric discrimination as this type of discrimination is not caused by choice of learning algorithm or model class, and is due to the data distribution. Factors such as data missing values can significantly contribute to aleatoric discrimination. We observe that when population groups have disparate missing patterns, aleatoric discrimination escalates, leading to a sharp decline in the effectiveness of fairness intervention algorithms (see Figure 3).
Related Work
There is significant work analyzing the tension between group fairness measures and model perfor- mance metrics (see e.g., Kleinberg et al., 2016; Chouldechova, 2017; Corbett-Davies al., 2017; Chen et al., 2018; 8; Wick et al., 2019; Dutta et al., 2020; Wang et al., 2021). For example, there is growing body of work on omnipredictors (Gopalan et al., 2021: Hu et al., 2023; Globus-Harris et al., 2023) discussing how, and under which conditions, the fair Bayes optimal classifier can be derived using post-processing techniques from multicalibrated regressors. While previous studies (Hardt et al., 2016; Corbett-Davies et al., 2017; Menon and Williamson, 2018; Chzhen et al., 2019; Yang et al., 2020; Zeng al., 2022a,b) have investigated the fairness Pareto frontier and fair Bayes
'There are various measures to quantify algorithmic discrimination, and the choice should be based on the specific application of interest (see Blodgett et al., 2020; Varshney, 2021; Katzman et al., 2023, for a more detailed discussion). In this paper. we focus on group fairness measures (see Table I for some examples), which are crucial contexts like hiring and recidivism prediction.
"e borrow this notion from ML uncertainty literature (see Hüllermeier and Waegeman, 2021, for survey) and defer detailed comparison in Appendix D.2.

---

optimal classifier, our approach differs from this prior work in the following aspects: our approach is applicable to multiclass classification problems with multiple protected groups; it avoids disparate treafment by not requiring the classifier to use group attributes as an input variable; and it can handle multiple fairness constraints simultaneously and produce fairness-accuracy trade-off curves (instead of a single point). A Additionally, our proof techniques based on Blackwell's results on comparing statistical experiments are unique and may be of particular interest to fair ML and information theory communities. We present detailed comparison with this line of work in Table 2 of Appendix E.
We recast the fairness Pareto frontier in terms of the conditional distribution Py/r, of predicted
outcome Y given true label Y and group attributes S. This conditional distribution is related to confusion matrices conditioned on each subgroup. In this regard, our work related to Verma and Rubin (2018); Alghamdi al. (2020); Kim et al. (2020); Yang et al. (2020); Berk et al. (2021), which observed that many group fairness metrics can be written in terms of the confusion matrices for each subgroup. Among them, the closest work and fairness objectives over these confusion matrices and proposed a post-processing technique for training fair classifiers. However, they only imposed marginal sum constraints for the confusion matrices. We demonstrate that the feasible region of confusion matrices can be much smaller (see Remark 2 for an example), leading a tighter approximation of the fairness Pareto frontier.
is Kim al. (2020), which optimized accuracy
Recently, many strategies have been proposed to reduce the tension between group fairness and model performance by investigating properties of the data distribution. For example, Blum and Stangl (2019); Suresh and Guttag (2019); Fogliato et al. (2020); Wang et al. (2020); Mehrotra and Celis (2021); Fernando et al. (2021): Wang and Singh (2021); Zhang and Long (2021); ); Tomasev et al.
(2021); Jacobs and Wallach (2021); Kallus et al. (2022); Jeong et al. (2022) studied how noisy or missing data affect faimess and model accuracy. Dwork et al. (2018); Ustun et al. (2019); Wang et al. (2021) considered training a separate classifier for each subgroup when their data distributions are different. Another line of research introduces data pre-processing techniques that manipulate data distribution for reducing its bias (c.g., Calmon et al., 2017; Kamiran and Calders, 2012). Among all these works, the closest one ours is Chen et al. (2018), which decomposed group fairness measures into bias, variance, and noise (see their Theorem 1) and proposed strategies for reducing each term. Compared with Chen et al. (2018), the main difference that we characterize a faimess Pareto frontier that depends on fairness metrics and a performance measure, giving complete picture of how the data distribution influences fairness and accuracy.
2 Preliminaries
Next, we introduce notation, overview the key results in Blackwell (1953) on comparisons of experiments, and outline the fair classification setup considered in this paper.
Notation. For a positive integer n, let [n]] - (1,... n). We denote all probability distributions on the set X' by P(X). Morcover, we define the probability simplex Am & P((m)). When random variables A. X, form a Markov chain, we write A X- Z. We write the mutual information Pax(A.X) between A, X as X(A:X) A Epa. log Px(A)Tx(X) Since I(A;X) is determined by the marginal distribution PA and the conditional distribution PXJA, we also write [AA X) as [(P:: Px)a). When A, X are independent, we write X.I.X.
If a random variable A E [n] has finite support, the conditional distribution PXIA : [m] + P(x') can be equivalently written as P & (Pi...., ,P,) where each P. PxxAmi E PP()). Additionally, if X is finite set [m]. then PXIA can be fully characterized by transition matrix. We use T(m|n) to denote
all transition matrices from [n] to [m]: { Raxm
PaJ < 11 Paj 1, e [n]]
Comparisons of Experiments
Given two statistical experiments (i.e., conditional distributions) P and Q is there a way to decide which one is more informative? Here P and Q have the common input alphabet [n] and potentially different output spaces. Blackwell gave an answer in his seminal work (Blackwell, 1953) from decision-theoreti perspective. We review these results next.
3

---

DERIITTION
FAIRNESS METRIC
ABBR.
EXPRESSION W.R.T. P
Pr(Y = g/s = 5) Pr(Ý = 8/5 = 8') S as
Statistical Parity
SP S
En=n Has P(ava)i Mal P(ota))))) S asp
PrrY = 8/S = 8, Y = 4) Pr(Y = -//S = 6', Y y) am
Equalized Odds
E0 Otop
P(ri) Pio S 000
PPr(Y Y|S 5) Pr(ý Y/S 5 Plu..)).)) Ouis
Overall Accuracy Equality
OAE S CLOaE
Σy= [Pe. P(..a). Mara May
My
Table Standard group fairness metries under multi- grout and multi class classification tasks. Here Ose: Ogo. Coxx, E [o, 1] are threshold parameters, Ø. y E [C], s, s' E [A], and Pa,y, He are defined in Proposition 1. Our analysis can extended to many other group fairness metrics (see e.g., Table in Kim et al., 2020).
Let A be closed, bounded, convex subset of R" A decision function f(x = (a1 (x)) .M " (x)) is any mapping from X' to A. It is associated with a loss vector:
vff) (ʃ |a1 (1)())R)(())) .f..(o)P..)))))
(1)
The collection of all ef)) is denoted by (().A). Blackwell defined that P more informative than Q if for every A, ((P, A) 2 A). Intuitively, this result means any risk achievable with Q is also achievable with P. Moreover, Blackwell considered the standard measure p which the probability distribution of p(X) where p(x) X An is function defined as
dP
dPn
dP
dP,
dP
dP,
and X follows the probability distribution B One of the most important findings by Blackwell in his paper is to discover the following equivalent conditions.
Lemma (Blackwell (1951, 1953)). The following three conditions are equivalent:
P is more informative than Q;
for any continuous and convex function An RR (())dP(()) 2 S dlD)dQ (p):
there is a stochastic transformation T s.t. TP: Qi In other words, there exists a Markov chain A - X for any distributions on A such that P Pxia and Q = PaJx
If Pxja is more informative than Q = P2A. by the third condition of Lemma and the data processing inequality, I [PAx; PxJA) 2 I(Px; Pz,a) holds for any marginal distribution PA. However, the converse does not hold in general-even if the above inequality holds for any PA. P is not necessarily more informative than Q (Rauh et al., 2017). this regard, Blackwell's conditions are "stronger" than the mutual information based data processing inequality.
Group Fair Classification
Consider multi-class classification task, where the goal is to train a probabilistic classifier h X' -> Ac that uses input features X predict their true label Y E [C). Additionally, assume the classifier produces predicted outcome Y [C] and let S E [A] represent group attributes (c.g., race and sex). Depending on the domain of interest, X can either include or exclude S as an input to the classifier. Our framework can be easily extended the setting where multiple subgroups overlap (Kearns et al., 2018). Throughout this paper, we focus on three standard group fairness measures: statistical parity (SP) (Feldman et al., 2015), equalized odds (EO) (Hardt et al., 2016; Pleiss al., 2017), and overall accuracy equality (OAE) (Berk et al., 2021) (see Table for their definitions) but our analysis can be extended to many other group fairness metrics, including the ones Table of Kim et al. (2020), as well as alternative performance measures beyond accuracy.

---

3 Fairness Pareto Frontier
In this section, we introduce our main concept- faimess Pareto frontier (FairFront). We use it to measure aleatoric discrimination and quantify epistemic discrimination by comparing a classifier's performance to the FairFront. We recast FairFront in terms of the conditional distribution Pris, and apply Blackwell's conditions characterize the feasible region of this conditional distribution. This effort converts a functional optimization problem into a convex program with a small number of variables. However, this convex program may involve infinitely many constraints. Hence, introduce greedy improvement algorithm that iteratively refines the approximation of FairFront and tightens the feasible region of PyJs.y- Finally, we establish convergence guarantee for our algorithm.
Recall that we refer to aleatoric discrimination as the inherent biases of the data distribution that can lead to unfair or inaccurate classifier. As its definition suggests, aleatoric discrimination only relies on properties of the data distribution and fairness metric of choice-it does not depend on the hypothesis class optimization method. Below we introduce FairFront that delineates curve of optimal accuracy over all probabilistic classifiers under certain faimess constraints for given data distribution P's.x Y. We use FairFront quantify aleatoric discrimination.
Definition 1. For Okgus Oxgo: PAA 2 0 and a given Ps,x,,, we define FairFront (ggr Ohpo Ohaa)) by
FairFront(aspr Oggo, CRoNs) max E [-
(3a)
SP S Org; EO S Omn, OAE ChTar:
(3b)
where T is the indicator function; Y is produced by applying the classifier h to X; the maximum is taken over all measurable h; and the definitions of SP, EO, and OAE are in Table As special case, if ass, Ogas COAE 2 1, then FairFront(asa) (ase, ago, (loss) is the accuracy of the Bayes optimal classifier.
Solving this functional optimization problem is difficult since it optimizes over all measurable classifiers. There is a line of works that proposed different fairness-interventioon algorithms for training group-fair classifiers (see e.g.. Menon and Williamson, 2018; Zhang et al., 2018; Zafar et al., 2019; Celis al., 2019; Yang et al., 2020; Wei al., 2021; Alghamdi et al., 2022). They restrict the model class and vary loss functions and optimizers to find classifiers that approach FairFront as close as possible. However, these algorithms only describe a lower bound for FairFront. They do not determine what is the best achievable accuracy for given set of faimess constraints.
We circumvent the above-mentione challenges by rewriting FairFront in terms of the conditional distribution Prjs,y- The caveat is that although each classifier yields Pyis, y not every conditional distribution corresponds to valid classifier. Hence, we introduce the following definition which characterizes all feasible PyJs.x-
Definition 2.
Given Pxis,Y, define C the set of all conditional distributions PyJs,Y where Ý is produced by some probabilistic classifier h. In other words,
C (Pyss (S, Y) Y-
Throughout this paper, we write PrIs,Y or its corresponding transition matrix P E T(CIAC) interchangeably. Specifically, the (C(s 1) + y)-th row, ÿ-th column of P represents P (ūls,)( and we denote it by P(o.g).8.
Remark We demonstrate the connection between the conditional distribution PaJs,y and confusion matrices in the setting of binary classification with binary groups. We define Ć as the counterpart of C when we replace PxJs.v with an empirical distribution PxJs.Y computed from dataset. The confusion matrix for group {0, 1} consists of four numbers: True Positive (TP.). False Positive (FP.). False Negative (FN,), True Negative (TN,). Assume that the number of positive-label data n TP. FN, and negative-label data nz TN, + FP, are given- thhse numbers do not depend on the classifier. Then there is a one-to-one mapping from each element in Ć to a confusion matrix:
P (1s,y(1|s,1)= =
TP.. Pr)s,)(11s;0)
FP.-.
n
1
Pyis.
FN.: Pyjsr(00ss,0) = TN
n2
n2
5

---

Hence, é essentially characterizes all feasible confusion matrices and C is the population counterpart of Ć. Note that C is determined by the underlying data distribution while é (and confusion matrices) are tailored to a specific dataset.
Proposition 1. FairFront(Ose>) Own, Oloss) in (3) is equal to the solution of the following convex optimization:
A
C
ΣΣ
max PERACXC
Us,y SayPP(sa) (3.2))
(5a)
s=1 s=1 y=1
s.t. SP S Csp,, EO & Cgo, OAE & Clous
(5b)
PEC.
(5c)
Here the constants Ps.yy _ Pr(S = 8, Y= y) and μs, - Pr(S= for 8 E [A], , E [A] and P( denotes the (C(s-1) + y) row, ÿ-th column of the transition matrix P. which Y
For example, in binary classification with a binary group attribute, the above optimization only has 8 variables, 14 linear constraints + single convex constraint P C. Hence, standard convex optimization solvers can directly compute its optimal value as long as we know how to characterize C.
Note that Kim et al. (2020) investigated fairness Pareto frontiers via confusion matrices. The main difference that Definition 1 in Kim et al. (2020) relaxed the constraint (5c) to A(C)AC) where T AC) represents all transition matrices from [AC] to [C]. This leads to a loose approximation of the frontier because C is often a strict subset of TTCIAC) To demonstrate this point, consider the scenario where (S, Y). Then (L, Y) by data processing inequality so
Remark 2.
C= [ E T(CIAC) each row of P is the same).
Optimizing over C rather than T(C1AC) can significantly tighten the fairness Pareto frontier.
Before diving into the analysis, first introduce function g X + AAC defined as g(x) (Ps,yix(1, 1 ... Ps.vix( (A, Cl=)) To obtain this function in practice, a common strategy among various cost-processing fairness interventions (see e.g.. Menon and Williamson, 2018: Alghamdi et al., 2022) is to train probabilistic classifier that uses input features X to predict (S, Y). The output probability generated by this classifier then utilized as an approximation the function g.
The following theorem is the main theoretical result in this paper. It provides a precise characterization of the set C through series of convex constraints.
Theorem 1. The set C is the collection of all transition matrices P E T(CIAC) such that the following condition holds:
For any k N and any {a, a, E [-1,,]]A, , [k]],
Σ max (TAApps) S EE max a 9(x)) KE(M)
[(((k]
where Pý is the ÿ-th column of P and A, = diag(Mi, .HA.C)))
Intuitively, (7) uses piecewise linear functions to approximate the boundary of the convex set C where i represents the number of linear pieces. Unfortunately, replacing P E with this series of constraints in (5) may result in an intractable problem since standard duality-based approaches will lead to infinitely many dual variables. To resolve this issue, we first fix h and let C₁ be the define FairFronte (agey Ogas aass) as the optimal value of (5) when replacing C with Cs. Since C₁ 2 C2 2 2 C. we have FairFront; (Aegr Oigo: Olass) FairFronty (Kse, asoi Qoos) > ... FairFront( agao Clone). However, computing FairFronty (A (Cise, Ogo, Orons) still involves infinitely many constraints.
set of P such that (7) holds under this fixed k. Accordingly,
Next, we introduce greedy improvement algorithm that consists of solving a sequence of tractable optimization problems for approximating FairFront, (Oksr, Ohoo (RDan). We use A to collect the con- straints of P and set A = 0 initially. At each iteration, our algorithm solves a convex program to find an optimal P that maximizes the accuracy while satisfying the desired group fairness constraints and the constraints in A; then we verify if this P is within the set C2 by solving a DC (difference of

---

Algorithm Approximate the fairness Pareto frontier.
Input: {(Z:s, Wh, ==)]== max number of iterations T; max pieces k; classifier g(z); Ose, Clans CLAR-
Initialize:
set Paa (ap+=
Repeat:
Solve a convex program:
max ΣΣ Pag Pa.gi
s.t. P E T(C]AC), S as; EO Ceeo OAE I
Σ max 8=1
af A SE
max fa g(X)}
V(ai,"..,, E A.
FE|R]
[E(A)
Let v² and P' be the optimal value and optimal solution. Solve a DC program:
c
min a.6
E max
9(X)3
- Σ
max sE(M]
a A.A'p'
the optimal value is = stop:
otherwise.
add the optimal (al,-.., ;aa) A and =t+1
return: P.P. A.
convex) program (Shen et al., 2016; Horst and Thoai, 1999). If E Ca. then the algorithm stops. Otherwise, the algorithm will find the constraint that mostly violated by P and add this constraint to A. Specifically, we determine a piecewise linear function that divides the space into two distinet regions: one containing P and the other containing C+- By "mostly violated", is constructed to maximize the distance between P and the boundary defined by the function. We describe our algorithm Algorithm and establish convergence guarantee below.
mean the function
Theorem 2.
If Algorithm 1 stops, its output p is optimal solution of FairFront, (a O'gnr (. Otherwise, any convergent sub-sequence of {P*) converges to an optimal solution of FairFronty (asye Cgaos Qase)-
Let T
Note that the output 2² from Algorithm is always an upper bound for FairFront(asp agos Coss) assuming the estimation error is sufficiently small. The tightness of this upper bound is determined by (i.e., how well the piecewise linear functions approximate the boundary C), T (i.e., the total number of iterations). On the other hand, running off-the-shelf in-processing and post-processing fairness interventions can only yield lower bounds for FairFront ((rsn Ogo, Orean).
4 Numerical Experiments
In this section, we demonstrate the tightness our upper bound approximation of FairFront, apply to benchmark existing group fairness interventions, and show how data biases, specifically missing values, impact their efffectiveness. We find that given sufficient data, SOTA fairness interventions successful at reducing epistemic discrimination as their gap (our upper bound estimate of) FairFront small. However, we also discover that when different population groups have varying missing data patterns, aleatoric discrimination increases, which diminishes the performance of faimess intervention algorithms. Our numerical experiments are semi-synthetic since we apply fairness interventions to train classifiers using the entire dataset and resample from it as the test set. This setup enables us to eliminate the estimation error associated with Algorithm (see Appendix E for a discussion). We provide additional experimental results and details in Appendix C.
7

---

Adult
COMPAS
84.5
77.0
84.2
Accuracy (%)
84.0
Accuracy (%)
76.8
83.7
76.6
83.5
63.2
83.0
Bosolitte ParProjection Redducion
Baseline
FarProjection
82.7
76.2
Reduction
2.5
7.50
10.0
10.0
15.0
20.0
Max equalized odds (%)
Max equalized odds (%)
Figure 1: We compare Reduction and FairProjection with (our upper bound estimate of) FairFront on the Adult (Left) and COMPAS (Right) datasets. We train a classifier that approximates the Bayes optimal and use basis for Reductio and FairProject demonstrates the tightness of our approximation but also shows that SOTA fairness interventions have already achieved near-optimal accuracy curves.
This result not only
4.1 Benchmark Fairness Interventions
Setup. We evaluate our results on the UCI Adult dataset (Bache and Lichman, 2013), the ProPublica COMPAS dataset (Angwin al., 2016), the German Credit dataset (Bache and Lichman, 2013), and HSLS (High School Longitudinal Study) dataset (Ingels et al., 2011; Jeong et al., 2022). We recognize that Adult, COMPAS, and German Credit datasets overused and acknowledge the recent calls to move away from them (see c.g., Ding et al., 2021). We adopt these datasets for benchmarking purposes only since most fairness interventions have available code for these datasets. The HSLS dataset is a new dataset that first appeared in the fair MI. literature last year and captures a common use-case case of ML in education (student performance prediction, see Jeong et al., 2022). It has multi-class labels and multiple protected groups. We apply existing (group) fairness interventions to these datasets and measure their fairness violations via Max equalized odds:
max Pr(Y = 0|s
v) Pr(Y = G/S -
y)l
where the max is taken over y. ÿ, 8, s. We run Algorithm with = 6 pieces, 20 iterations, and varying Oho estimate FairFront each dataset. We compute the expectations and the g function from the empirical distributions and solve the DC program by using the package in Shen et al. (2016). The details about how pre-process these datasets and additional experimental results the German Credit and HSLS datasets are deferred to Appendix C.
Group fairness interventions. We consider five existing fairness-intervention algorithms: Reduction (Agarwal et al., 2018), EqOdds (Hardt et al., 2016), CalEqOdds (Pleiss et al., 2017), LevEqOpp (Chzhen et al., 2019), and FairProjection Alghamdi et al. (2022). Among them, Reduction is an in-processing method and the rest are all post-processing methods. For the first three benchmarks, we use the implementations from IBM AIF360 library (Bellamy et al., 2018); for LevEq0pp and FairProjection, in Alghamdi et al. (2022). For Reduction and FairProj FairProjection, we can vary their tolerance of fairness violations produce a faireess- accuracy curve; for EqOdds, CalEgOdds, and LevEqOpp. each of them produces a single point since they only allow hard equality constraint. We note that FairPro peroject jection is optimized for transforming probabilistic classifier outputs (see also Wei et al., 2021), but here we threshold the probabilistic outputs to generate binary predictions which may limit its performance. Finally, train random forest the Baselire classifier.
the Python implementations from the Github repo
Results. We observe that if we run Algorithm 1 for single iteration, which is equivalent to solving Proposition without (5c), its solution is very close for all Ogo- This demonstrates the benefits of incorporating Blackwell's conditions into the fairness Pareto frontier.

---

Adult
COMPAS
Aleatoric
Epistemic
77.0
discrimination
discrimination
84.0
76.0
Accuracy (%)
Accuracy (%)
83.5
75.0
83.0
FarFront
74.0
Fairfront
82.5
ra Projecttttoonn
Basoline
Partrrjectoo
82.0
LevExpOpo CaEadOod EqDdds
73.0
+
Ca EqDods
LavExOpp
Exjodds
81.5
72.0
2.5
5.0
7.50
10.0
12.5
0
5.0
15.0
20.0
Max equalized odds (%)
Max equalized odds (%)
Figure 2: We benchmark existing faimess interventions using (our upper bound estimate of) Front. We use FairFront to quantify aleatoric discrimination and measure epistemic discrimination by comparing classifier's accuracy and fairnsss violation with FairFront. The results show that SOTA fairness interventions are effective at reducing epistemic discrimination.
We train classifier that approximates the Bayes optimal and use it basis for both Reduction and FairProjection, which are SOTA faireess interventions. We then apply these two fairness interventions to the entire dataset and evaluate their performance on the same dataset. Figure shows that in this infinite sample regime, the fairness-accuracy curves produced by Reduction i and FairProjection can approach upper bound estimate of FairFront. This result not only demonstrates the tightness of our approximation (recall that Algorithm 1 gives an upper bound of FairFront and existing fairness interventions give lower bounds) but also shows that SOTA fairness interventions have already achieved near-optimal fairness-accuracy curves.
Recall that achievable accuracy among all classifiers satisfying the desired fairness constraints. Additionally, measure epistemic discrimination by comparing classifier's accuracy and fairness violation with FairFront. Given that our Algorithm provides a tight approximation of FairFront, we use benchmark existing fairness interventions. Specifically, we first train base classifier which may not achieve Bayes optimal accuracy. Then we use it as a basis for all existing fairness interventions. The results in Figure show that SOTA fairness interventions remain effective at reducing epistemic discrimination. In what follows, we demonstrate how missing values in data can increase alcatoric discrimination and dramatically reduce the effectiveness of SOTA fairness interventions.
FairFront to quantify aleatoric diserimination since it characterizes the highest
4.2 Fairness Risks Missing Values
Real-world data often have missing values and the missing patterns can be different across different protected groups (see Jeong et al., 2022, for some examples). There is growing line of research (see e.g., Jeong et al., 2022; Fernando et al., 2021; Wang and Singh, 2021; Subramonian al., 2022; Caton et al., 2022: Zhang and Long, 2021; Schelter et al., 2019) studying the fairness risks of data with missing values. In this section, apply our result to demonstrate how disparate missing patterns influence the faimess-accuracy accuracy curves.
Setup. We choose sex (group O: female, group 1: male) as the group attribute for the Adult dataset, and race (group O: Amerrcan,,,,,nn, group 1: Caucasian) for the COMPAS dataset. To investigate the impact of disparate missing patterns on aleatoric discrimination, we artificially generate missing values in both datasets. This is necessary as the datasets do not contain sufficient missing data. The missing values are generated according to different probabilities for different population groups. For each data point from group 0, we erase each input feature with varying probability Po E {10%, 50%, 70%). while for group 1, we erase each input feature with a fixed probability P1 = 10%. We then apply mode imputation to the missing values, replacing them with the mode of non-missing values for each feature. Finally, we apply Algorithm along with Reducti on and Baseline to the imputed data. The experimental results are shown in Figure 3.

---

Adult
COMPAS
84.5
75.0
84.0
72.5
Accuracy (%)
83.5
Accuracy (%)
70.0
67.5
83.0
Fairfront; 10%, 10%)
65.0
FairFiont (10%, 10%
82.5
Fainfrrntt (97%, 10%)
FoirFront 190%, 10%)
Suseline -
Feinfront (208, 00%)
62.5
-
FairFront (90%, 10%)
foowline (109s 1099
82.0
Gossline (90%)
60.0
Basedine 10%
Redi (107)
81.5
57.5
10.0
20.0
30.0
40.0
50.0
20.0
40.0
60.0
Max equalized odds (%)
Max equalized odds (%)
Figure 3: Fairness risks of disparate missing patterns. The missing probabilities of group 0 (female in Atuut/AfrrcannAmeriica in COMPAS) and group (male in Adult/Caucasian in COMPAS) are varying among {10%, 10%). (50%, 10%) ), (70%, 10%)). We apply Reduction and Baseline to the imputed data and plot their fairness- accuuesyy curves against FairFront. As shown, the effectiveness of fairness interventions substantially decrease with increasing disparate missing patterns in data.
Results. As we increase the missing probability of group O, (our upper bound estimate of) FairFront decreases since becomes more difficult accurately predict outcomes for group This in turn affects the overall model performance, since the faimesss constraint requires that the model performs similarly for both groups. We also observe the faimess- accuurcy curves of Reduction decrease as the missing data for group O become more prevalent. In other words, as the missing data for group increase, it becomes more difficult maintain both high accuracy and fairness in the model's prediction.
5 Final Remarks
The past years have witnessed a growing line of research introducing various group fairness- intervention algorithms. Most of these interventions focus optimizing model performance subject to group fairness constraints. Though comparing and benchmarking these methods on various datasets valuable (e.g., see benchmarks in Friedler et al., 2019; Bellamy et al., 2019; Wei et al., 2021), this does not reveal there still room for improvement in their fairesss fairness-accurae accuraac curves, or existing methods approach the ceemmatiionthhhoreee optimal limit when infinite data is available. Our results address this gap by introducing the fairness Pareto frontier, which measures the highest possible accu- racy under set of group fairness constraints. We precisely characterize the fairness Pareto frontier using Blackwell's conditions and present a greedy improvement algorithm that approximates from data. Our results show that the fairress-accuracy curves produced by SOTA fairness interventions very close to the fairness Pareto frontier on standard datasets.
Additionally, demonstrate that when data are biased due to missing values, the fairness Pareto frontier degrades. Although existing fairness interventions can still reduce performance disparities, they come the cost of significantly lowering overall model accuracy. The methods present for computing the fairness Pareto frontier can also be applied to analyze other sources of aleatoric discrimination, such when individuals may misreport their data when there are measurement errors. Overall, the fairness Pareto frontier can serve as valuable framework for guiding data collection and cleaning. Our results indicate that existing fairness interventions in reducing epistemic discrimination, and there are diminishing returns in developing new fairness interventions focused solely on optimizing accuracy for a given group fairness constraint on pristine data. However, existing fairness interventions have yet to effectively provide both fair and accurate classification when additional sources of aleatoric discrimination are present (such missing values in data). This suggests that there is still significant need for research on handling aleatoric sources of discrimination that appear throughout the data collection process.
be effective
We provide an in-depth discussion on future work in Appendix
10

---

Acknowledgement
This material based upon work supported by the National Science Foundation under grants CAREER 1845852, CIF 2312667, FAI 2040880, CIF 1900750.
References
Agarwal, A., Beygelzimer, A., Dudík, M., Langford, J., and Wallach, H. (2018). reductions approach to fair classification. In International Conference Machine Learning, pages 60-69.
PMLR.
Alghamdi, W., Asoodeh, S., Wang, H., Calmon, F. P., Wei, D., and Ramamurthy, K. N. (2020). Model projection: Theory and applications to fair machine learning. In 2020 IEEE International Symposium on Information Theory (ISIT), pages 2711-221111111 1-2716. IEEE.
Alghamdi, W., Hsu, H., Jeong, H., Wang, H., Michalak, P. W., Asoodeh, S., and Calmon, F. P. (2022). Beyond Adult and COMPAS: Fair multi-class prediction via information projection. In Advances in Neural Information Processing Systems.
Angwin, J., Larson, J., Mattu, S., and Kirchner, L. (2016). Machine bias. ProPublica.
Bache, K. and Lichman, M. (2013). UCI Machine Learning Repository.
Bellamy, R. K., Dey, K., Hind, M., Hoffman, S. C., Houde, S., Kannan, K., Lohia, P., Martino, J., Mehta, S., Mojsilovic, A., et al. (2018). Ai faimess 360: An extensible toolkit for detecting, understanding, and mitigating unwanted algorithmic bias. arXiv preprint
Bellamy, R. K., Dey, K., Hind, M., Hoffman, S. C., Houde, S., Kannan, K., Lohia, P., Martino, J., Mehta, S., Mojsilović, A., al. (2019). Ai fairness 360: An extensible toolkit for detecting and mitigating algorithmic bias. IBM Journal of Research and Development, 4-44
Berk, R., Heidari, H., Jabbari, S., Kearns, M., and Roth, A. (2021). Fairness in criminal justice risk assessments: The state of the art. Sociological Methods & Research, 50(1):3-44
Blackwell, D. (1951). Comparison of experiments. Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, pages 93-102.
Blackwell, D. (1953). Equivalent comparisons of experiments. The annals of mathematical statistics, pages 265-272.
Blodgett, S. L.. Barocas, S., Daumé III. H., and Wallach, H. (2020). Language (technology) is power: A critical survey of" bias" in nlp. arXiv preprint arXiv:2005.1400
Blum, A. and Stangl, K. (2019). Recovering from biased data: Can fairness constraints improve accuracy? arXiv preprint arXiv:1912.01095
Calmon, F., Wei, D., Vinzamuri, B., Natesan Ramamurthy, K., and Varshney, K. R. (2017). Optimized pre-processing for discrimination prevention. Advances in neural information processing systems, 30.
Cam, L. L. (1964). Sufficiency and approximate sufficiency. The Annals of Mathematical Statistics, pages 1419-1455.
Caton, S., Malisetty, S., and Haas, C. (2022). Impact of imputation strategies on fairness machine learning. Journal of Artificial Intelligence Research, 74:1011-1035
Celis, L. E., Huang, L., Keswani, V., and Vishnoi, N. K. (2019). Classification with fairness constraints: meta-algorithm with provable guarantees. In Proceedings of the conference on fuirness, accountability, and trunsparency, pages 319-328.
Chen, I., Johansson, F. D., and Sontag, D. (2018). Why is my classifier discriminatory? Advances in neural information processing systems, 31.
Chouldechova, A. (2017). Fair prediction with disparate impact: study of bias in recidivism prediction instruments. Big data, 552):153-163.

---

Chzhen, E., Denis, C., Hebiri, M., Oneto, L., and Pontil, M. (2019). Leveraging labeled and unlabeled data for consistent fair binary classification. Advances in Neural Information Processing Systems, 32.
Cohen, J.. Kempermann, J. H., and Zbaganu, G. (1998), Comparisons of stochastic matrices with applications in information theory, statistics, economics and population. Springer Science & Business Media.
Corbett-Davies, S., Pierson, E., Feller, A., Goel, S., and Huq, A. (2017). Algorithmic decision making and the cost of fairness. In Proceedings of the 23rd acm sigkdd international conference on knowledge discovery and data mining, pages 797-806.
Ding, F., Hardt, M., Miller, J., and Schmidt, L. (2021). Retiring adult: New datasets for fair machine learning. Advances in neural information processing systems, 34:6478-6493
Dutta, S., Wei, D., Yueksel, H., Chen, P.-Y., Liu, S., and Varshney, K. (2020). Is there trade-off' between fairness and accuracy? a perspective using mismatched hypothesis testing. In International Conference Machine Learning, pages 2803-2815 13. PMLR.
Dwork, C., Immorlica, N., Kalai, A. T., and Leiserson, M. (2018). Decoupled classifiers for group-fair and efficient machine learning. In Conference on fairness, accountability and transparency, pages 119-133. PMLR.
Feldman. M., Friedler. S. A.. Moeller, J., Scheidegger, C.,, and Venkatasubramanninn, S. (2015). Certifying and removing disparate impact. In proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 259-268.
Fernando, M.-P., Cèsar, F., David, N., and José, H.-O. (2021). Missing the missing values: The ugly duckling of fairness in machine learnin.. International Journal of Intelligent Systems, 36(7):2217-328.
Fogliato, R., Chouldechova, A., and G' G'lell, M. (2020). Fairness evaluation in presence of biased noisy labels. In International Conference on Artificial Intelligence and Stafistics, pages 2325-2336. PMLR.
Friedler, S. A., Scheidegger, C., Venkatasubramanian, S., Choudhary, S., Hamilton, E. P., and Roth, D. (2019). comparative study of taimess-enhancing interventions machine learning. In Proceedings of the conference on fairness, accountabiliry, and transparency, pages 329-338.
Globus-Harris, I., Gupta, V. Jung, C., Kearns, M., Morgenstern, J., and Roth, A. (2023). Multicali- brated regression for downstream faimesss. Proceedings of the 2023 AAAI/ACM Conference on AI, Ethics, and Society, pages 259-286.
Gopalan, P., Kalai, A. T., Reingold, O., Sharan, V., and Wieder, U. (2021). Omnipredictors. arXiv preprint arXiv:2 100.05389.
Hardt, M., Price, E., and Srebro, N. (2016). Equality of opportunity in supervised learning. In Advances in Neural Information Processing Systems, volume 29.
Horst, and Thoai, N. (1999), De programming: overview. Journal of Optimization Theory and Applications, 103(1): (:(1):1-44 1-43.
Hort, M., Chen, Z., Zhang, J. M., Sarro, F,, and Harman, M. (2022). Bia mitigation for machine learning classifiers: A comprehensive survey, arXiv preprint arXiv:2207.07068
Hu, L., Navon, R. L., Reingold, O., and Yang, C. (2023). Omnipredictors for constrained optimization. In International Conference Machine Learning, pages 13497-13527. PMLR.
Hüllermeier, and Wacgeman, W. (2021). Aleatoric and epistemic uncertainty in machine learning: An introduction to concepts and methods. Machine Learning, 110(3)4557-06.
Ingels, S. J., Pratt, D. J., Herget, D. R., Burns, L. J., Dever, J. A., Ottem, R., Rogers, J. E., Jin, Y., and Leinwand, S. (201 1). High school longitudinal study of 2009 (hsls: 09): Base-year data file documentation. nees 2011-328. National Center for Education Statistics.
12

---

Jacobs, A. Z. and Wallach, H. (2021). Measurement and faimess. In Proceedings of the 2021 ACM conference on faimesss accountabilityy and transparency, pages 375-385.
Jeong, H., Wang, H., and Calmon, F. P. (2022). Faimess without imputation: A decision tree approach for fair prediction with missing values. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 9558-9566.
Jiang, H. and Nachum, O. (2020). Identifying and correcting label bias in machine learning. In International Conference on Artificial Intelligence and Statistics, pages 702-712. PMLR.
Jiang, R., Pacchiano, A., Stepleton, T., Jiang, H., and Chiappa, S. (2020). Wasserstein fair classifica- tion. In Uncertainty Artificial Intelligence, pages 662-872.15 PMLR.
Kallus, N., Mao, X., and Zhou, A. (2022). Assessing algorithmic faimess with unobserved protected class using data combination. Management Science, 68(3):199--198
Kamiran, F. and Calders, T. (2012). Data preprocessing techniques for classification without discrim- ination. Knowledge and information systems, 33(1):1-33,
Katzman, J., Wang, A., Scheuerman, M., Blodgett, S. L.,, Laird, K., Wallach, H., and Barocas, S. (2023). Taxonomizing and measuring representational harms: A look at image tagging. arXiv preprint arXiv:2305.01770
Kearns, M., Neel, S., Roth, A., and Wu, Z. S. (2018). Preventing faimess gerrymandering: Auditing and learning for subgroup fairness. International Conference on Machine Learning, pages PMLR.
Kim, J. S., Chen, J., and Talwalkar, A. (2020). Fact: A diagnostic for group fairness trade-offs. In International Conference Machine Learning, pages 5264-5274. PMLR.
Kim, M. P., Ghorbani, A., and Zou, J. (2019). Multiaccuracy: Black-box post- post-processing for fairness in classification. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, pages 247-254.
Kleinberg, J., Mullainathan, S., and Raghavan, M. (2016). Inherent trade-off's in the fair determination of risk scores. arXiv preprint arXiv:1609.05807
Lowy, A., Pavan, R., Baharlouei, S., Razaviyayn, M., and Beirami, A. (2021). Fermi: Fair empirical risk minimization via exponential Rényi mutual information. arXiv preprint 128.5
Martinez, N., Bertran, M., and Sapiro, G. (2020). Minimax pareto fairness: A multi objective perspective. In International Conference Machine Learning, pages 6755-6764. PMLR.
Mayson, G. (2019). Bias in, bias out. The Yale Law Journal, 128(8)
Mehrotra, A. and Celis, L. E. (2021). Mitigating bias in set selection with noisy protected attributes. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, pages 237-248.
Menon, A. K. and Williamson, R. C. (2018). The cost of faimess in binary classification. In Conference on Fairness, Accountability and Transparency, pages 107-118. PMLR.
Pedregosa, F. Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhoferr P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., and Duchesmay, F. (2011) Scikit-leamm: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2833
Pleiss, G., Raghavan, M., Wu, F., Kleinberg, J., and Weinberger, K. Q. (2017). On fairness and calibration. Advances in neural information processing systems, 30.
Raginsky, M. (2011). Shannon meets blackwell and le cam: Channels, codes, and statistical experiments. 20/1 IEEE International Symposium on Information Theory Proceedings, pages 1220-1224. IEEE.
13

---

Rauh, J., Banerjee, P. K., Olbrich, E., Jost, J., Bertschinger, N., and Wolpert, D. (2017). Coarse- graining and the blackwell order. Entropy, 19(1))527.
Schelter, S., He, Y., Khilnani, J., and Stoyamovich, J. (2019). Fairprep: Promoting data to a first-class citizen in studies fairness-enhancing interventions. arXiv preprini urXiv:1911.122
Shannon, C. (1958). note on partial ordering for communication channels. Information and control, 1(4):390-397.
Shen, X., Diamond, S., Gu, Y., and Boyd, S. (2016). Disciplined convex-concave programming. In 2016 IEEE 55th Conference on Decision and Control (CDC), pages 1009-1014, IEEE.
Subramonian, A., Chang, K.-W., and Sun, Y. (2022). On the discrimination risk of mean aggregation feature imputation in graphs. Advances in Neural Information Processing Systems.
Suresh, H. and Guttag, J. V. (2019). A framework for understanding unintended consequences of machine learning. arXiv preprint arXiv: 10002, 2:8.
Tomasev, N., McKee, K. R., Kay, J., and Mohamed, S. (2021). Fairness for unobserved characteristics: Insights from technological impacts queer communities. In Proceedings the 2021 AAAI/ACM Conference on AI, Ethics, and Society, pages 254-265.
Torgersen, E. (1991). Comparison of statistical experiments, volume 36. Cambridge University Press.
Ustun, B., Liu, Y., and Parkes, D. (2019). Faimess without harm: Decoupled classifiers with preference guarantees. In International Conference on Machine Learning, pages 6373-6382. PMLR.
Varshney, K. R. (2021). Trustworthy machine learning. Chappaqua, NY.
Verma, S. and Rubin, J. (2018). Fairness definitions explained. In 2018 ieeelacm international workshop software fairness (fairware), pages 1-7. IEEE.
Wang, H., Hsu, H., Diaz, M., and Calmon, (2021). To split or not to split: The impact of disparate treatment in classification. IEEE Transactions Information Theory, 6710))6673--6777
Wang, S., Guo, W., Narasimhan, H., Cotter, A., Gupta, M., and Jordan, M. (2020). Robust optimiza- tion for faimesss with noisy protected groups. Advances in Neural Information Processing Systems, 33:5190-5203.
Wang, and Singh, I.. (2021). Analyzing the impact of missing values and selection bias on fairness. International Journal Data Science and Analytics, 12(2):011-119
Wei, D., Ramamurthy, K. N., and Calmon, (2021). Optimized score transformation for consistent fair classification. J. Mach. Learn. Res., 22:258-1.
Wick, M., Tristan, J.-B., et al. (2019). Unlocking faireess: trade-off revisited. Advances in neural information processing systems, 32.
Yang, F. Cisse, M., and Koyejo, S. (2020). Fairnsss with overlapping groups; a probabilistic perspective. In Advances Neural Information Processing Systems, volume 33, pages 4067
Zafar, M. B., Valera, I., Gomez-Rodriguez, M., and Gummadi, K. (2019). Fairness constraints: A flexible approach for fair classification. The Journal of Machine Learning Research, 20(1):2737- 2778.
Zemel, R., Wu, Y., Swersky, K., Pitassi, T., and Dwork, C. (2013). Learning fair representations, In International conference on machine learning, pages 325-333. PMLR.
Zeng, X., Dobriban, E., and Cheng, G. (2022a). Bayes-optimal classifiers under group fairness. arXiv preprint ar Xrv: 220.
Zeng, X., Dobriban, E., and Cheng, (2022b). Fair Bayes-optimal classifiers under predictive parity. In Advances in Neural Information Processing Systems.
14

---

Zhang, B. H.. Lemoine, B., and Mitchell, M. (2018). Mitigating unwanted biases with adversarial learning. In Proceedings of the 2018 AAAI/ACM Conference on Al. Ethics, and Society, pages 335-340.
Zhang, Y. and Long, Q (2021). Assessing fairness in the presence of missing data. Advances in neural information processing systems, 34:16007-16019.
15

---

A Technical Background
In this section, we extend some results in Blackwell (1951, 1953) to our setting. For a random variable X, we denote its probability distribution by L(X). A conditional distribution fx|A [x]] + P(2) can be equivalently written as P - (Pi,... Pn)) where each P. PX|A= E P(X). Let be a closed, bounded, convex subset of IR.. A decision function is mapping f X - A, which can also be written as f(x) (01 (z), ... an
, (2)).. A decision function is associated a loss vector:
p(f) = (/ 01 (I)
(9)
The collection of all v(f) is denoted by A) or B)). For a vector An such that À > O, we define function PA Px(x) : + An:
ATdPi did +... X,,P,
dn
(x
(10)
AiiPP + + XaPP,
Note that Px (X) is sufficient statistic for X, considering A as the parameter (it can be proved by Fisher-Nee Neyman factorization theorem). In other words, two Markov chains hold: Px(X) X
and A X Px (X) for any distribution on A.
Consider new set of probability distributions Px & (CI)) ... (X,))) where L(X,) = P.. Here Px can be viewed conditional distribution from [n]] to P(An) since each [(px (X:) probability distribution over A, The following lemma follows from the sufficiency of px (X).
Lemma 2 (Adaptation of Theorem 3 in Blackwell (1951)). For any A. ()).A) = B(Px A).
Proof. Suppose that ('(p) = (p). .a, (p)) is a decision function for (Px. .A.. Accordingly. we define f(x) (a (P)),,, a, (px())) where the function pA defined in (10). Then is clear that f is a decision function for (P,A) By the law of unconscious statistician, we have
J (p)dP (p) = El; (pxx))) = a di
(11)
Hence, v(f')= = v(f), which implies A C B(P,A). For the other direction, suppose
((x) (an (2), (u](x) is decision function for (P, Let ("(p) (ai(p). (.)).... , a (p))
where at (p) e (X,) PA (X,) p). Since PA (X) a sufficient statisties, for any E [n]
C(X, Px (X.) p) ((x)lpx(x)) =p).
(12)
Therefore, (p (x p). Since A is convex set, f is decision function for (P*, By the law of total expectation, we have
/ a (p)PPP =
( (=()))P((())
(13)
Hence, v(f) = v(f"), which implics A) A))))
For a vector À E A, such that À > O, the condition distribution PXIa induces a weighted standard measure Px & L (px (X)) where ((X) X1 + .... + Pr,
Theorem 3 (Adaptation of Theorem 4 in Blackwell (1951)). For any two conditional distributions PXIA and QxIA, let P and Q2 be their weighted standard measures, respectively. Then B (x)A), 2 B(QYAA A) for any closed, bounded, convex set A if and only for any continuous convex Φ An - R. ( 2 p(p)dQx(p)
Proof. First, by Lemma 2, we know B(Px)A, A) = B(Pr A) and B(QY)A. = B(Q},AA) We denote A diag(>1,"". An). Consider any A conv(a)) (a, ..., .x). Let
(p) = argmin p" ''A -laa
(14)
aEA
16

---

Note that (p) E fai.... , since this set contains all the extreme points of A.' By definition, for any decision function w.r.t. (Px A),, we have
A f()) 2 p (D)) Vp.
(15)
Let v(f). By the same reason with (11), have
1/ = a (P2(())))P((1)
(16)
A,dP, dj / ()((x(())) XidPi A,,P,
1
(x)(A) +... (z)
(17)
1
/ (1(p)(())) + +.. (2))
(18)
A
1 E (o)(axx (X))
(19)
Dj
2 a/(p)),dP((())
1
/
(20)
where the last step is due to the law of unconscious statistician. Therefore,
/ / (2'A->(pp)pP((000
(21)
2 p (p)
(22)
/
(23)
The equality is achieved by vff*). Hence, for any conv(a1...... akk
min (
Σ Us
min A A
(p)P
(24)
Recall that Theorem 2.(3) in Blackwell (1951) states
B(PxA, A) 2 ((Pr)..A) for every closed, bounded, convex A
min vEB(Ps A.AA
Σe, U, S min vEB(PrIA.A)
V/y for every closed, bounded, convex A.
j=1
By approximation theory, the second condition be relaxed any A that is convex hull of finite set. By (24), this relaxed condition equivalent to
/ (())))( > f ((p))QX(p)
(25)
for all @(p) that are the maximum of finitely many linear functions. By approximation theory again, the above condition is equivalent to the one holding for any continuous convex function ó.
B Omitted Proofs
B.1 Proof of Lemma 3
Proof. Clearly, C is subset of T(CIAC). Let À E (0,1) and Pr. E C. Now introduce a Bernoulli random variable B such that Pr(B = 0) = X. Finally, we define Y, BY, + (1 B) By definition, we have (S, Y) - X Y, so PrAIs. C. Moreover,
PrAIS.Y XP Yo + (1 P)
If (14) has multiple optimal solutions, always choose the from (ai,..., ax)-
17

---

Hence, C is convex.
Let (0, 1). Assume P and P achieve the maximal values of Proposition 1 under (awgy Onny Olonn and (iks, Oaoo (, respectively. We define PA XP + (1 (1-X) X) which satisfies the constraints of Proposition with thresholds (Ao=++(11 (1-X) A0 + (1 (1-X) X)) Xoou + (1-X)0ouu)) Finally, since
the objective function of Proposition is a linear function, it is equal to XFairFront((sss (Ksp, Ago Clove) A)FairFront((ar Cggs CoAE) under Px.
B.2 Proof of Theorem 1
Proof.
The proof relies on Theorem 3 and Lemma 1. For simplicity, we write the conditional PYJs, as its corresponding transition matrix P. Let μ (Pr(S = Y 1),-.. Pr((S = A, = C)).
The function (10) in our setting can be written as:
(1.11(1.11..
MAC.PA, Exy Us Py
(0())= -
(26)
Ex.y Ma.y P(ax).
M1,1d xis=IXiS=YYYI
Pn(#)= =
(z), E,y PxIssPPiss.....
(z)
(27)
Ee, Ma.y dP' x \ss=
Note that Pa = g(x) due to Bayes' rule. By Lemma I, we can rewrite in Definition as
C c= (p(P) PxIs,y more informative than P)
(28)
By Lemma and Theorem 3, the above set is further equivalent to all transition matrices P E
AC) satisfying
Σ
c
M1.1P(L.1.8
M.C.PAA,
EPasPlowie S [o(g((() 8.9)
(29)
En.y Mayy Ma P(
EsyH
8=1
for any function ø: AAC + E which the maximum of finitely many linear functions. Now we can
write x(p) maX { we
we ignore the bias term because a² + b; = (a; 6,1)" p. Then inequality in (29) can be simplified as
Σ max (a Apps) SE KE(K]
max 9(X)3 [E(k)
(30)
where P3 is the ÿ-th column of and A, = diag(/1... MA,C). Finally, we can always normalize the above inequality so that each a: E [-11
B.3
Proof of Theorem 2
Proof. We denote
A c f(P) &
Σ>
es,y P(..))))
s= y=
g(P: a1, .. .aa) A max {a A.Pp) E iElk
max a 9(x)) iE(k]
F F F&GNPPETCICCC) SP Osr EO Onn OAE S Omnan
Let J be the constraint set of P at the t-th iteration of our algorithm. Note that F C C by definition. AC the algorithm stops at the t-th iteration, then for any {a; a, E [-1, AC E [k], P satisfies
g(P':
.a)) 0,
which implies P E F. Consequently,
f( f(P")
max f(P)
max (PP 2 (P').
PEF
PEF
18

---

As result, f(P') = maxper f(P) so P is an optimal solution of FairFronty Qgo CooE)
If the algorithm never stops, consider any convergent sub-sequence of p that converges to limit point P E (C))C)) To simplify our notation, we assume P + P as + co. Since (F*) )21 non-increasing and they all contain F, there exists set F such that
lim F = F FSF t1000
Therefore, we have
f(P") lim f(P')
lim max f(P) t0000 PEF
max f(P). PEF
Since F S F', we have
S(P") max S(P) 2 max S(P). PEF
PEF
If P & F, then there exists a (Ø1, ag), such that g (P":; ; ", ..) 0. Let (a1,t,"" (gg,))
be the output of Step 2 at t-th iteration. Since P E E for all t, we have
;(P";aa,. ,ax,) 50. 0.
(31)
By the optimality of (a1,) (k we have
( a1., ahi)) 2 (P:: āl. ax).
(32)
Suppose that some sub-sequence of (aI,,, (k.1) converges to vector (aj.... , a.). For the
sake of simplicity, we assume (a1.1. ... ax,1) + (ai... , ag) as t + oc. On the one hand, taking limit of on both sides of (32) leads to
g(P" aj,
a 2 PP a ax).
On the other hand, taking limit L + xo on both sides of (31) leads to
g(P";
a < 0.
Therefore,
0 M g P aj, ..... a 2 g P P
a., ax)) > 0,
which is impossible. Therefore, P F and, as a result, we have
f(P") = max f(P) 2 max f(P) 2 f(P") = max PEF
PEF
PEF
B.4 Additional Results
We establish basic properties of C and FairFront(aw,, Ogao Goaa)) in the following lemma.
Lemma 3. C is a convex subset of (CC)AC) and FairFront(acg, Osg. agas aasE) is a concave function Oisr, Oha: Ouaur Here the constants A and C denote the number of protected groups and the number of classes.
Next, we discuss a special case is discrete-undee under which C has a simple characterization.
Remark 3. If is discrete variable with a finite support [D], we can write Pxis,y transition matrix + E T(D|AC). By introducing an auxiliary variable M E D)C we can write P C cquivalently as linear constraints: P + M by using the last condition of Lemma Consequently, Proposition boils down to a linear program. However, this characterization fails to generalize to continuous data because & and M will have infinite dimension; for categorical data, this charac- terization suffers from the curse of dimensionality since the support size of X grows exponentially fast w.r.t. the number of features.
C Details on the Experimental Results
C.1 Additional Experiments
In this section, we present additional experimental results to further support our findings. We reproduce our experimental results on the German Credit dataset (Bache and Lichman, 2013) and HSLS (High School Longitudinal Study) dataset (Ingels et al., 201 1; Jeong et al., 2022) in Figure 4 and Figure In particular, the HSLS dataset experiment a multi-group, multi-label experiment. Our observation is consistent with those on the previous two datasets- the fairness-accurace curves given by SOTA fairness interventions, such as Reduction on and FairProjection, are close to the information- -hommation-theoretie limit.
19

---

German Credit
German Credit
86.0
86.0
85.5
85.9
85.0
85.9
Accuracy (%)
84.5
85.8
Accuracy
84.0
85.8
85.7
FaliFront
83.0
FarFrojectin
85.7
FaiFrrott
85.6
Rasedin
82.5
EsO
FairPro cotion
EepCcts
85.6
Reduction
5.0
10.0
15.0
20.0
5.0
10.0
15.0
20.0
25.0
Max equalized odds (%)
Max equalized odds (%)
Figure 4: We reproduce our experiments on the German Credit dataset. Our observation is consistent with those on the previous two datasets the aaiuness-accuracy curves given by SOTA fairness interventions, such as Reduction and FairProjection, are close to the coormation-thhoree
limit.
HSLS
HSLS
82.0
80.0
81.0
Accuracy (%)
Apcuracy (%)
78.0
76.0
74.0
79.0
72.0
Peintrent
78.0
FoxFrojpction
70.0
Ki
20.0 Max equalized adds (%)
Max equalized odds (%)
Figure 5: We reproduce our experiments the HSLS dataset with multi-group and multi-label pre-processing. On the right, we also demonstrate that FairFront can take into account multiple fairness considerations at once. We show how the fairness-accuracy curve changes we add new types of group fairness constraints (i.e., adding OAE and SP constraints in addition to EO).
C.2 Dataset
Adult. We use sex (female or male) as the group attribute and income (> 50K <= 50K) as the target for prediction. We use sex, hours-per-week education-num, age, marital status, relationship status (husband or wife) the input features- we include the group attribute as an input feature. We group age into total of 12 disjoint intervals: [0, 20). [20, 25), [65, 70), [70, oo); we group hours-per-weet into a total of 14 disjoint intervals: [0, 10), [10, 15), ... [65, 70), [70, oo).
COMPAS. We use race (African-Ameriaan or Caucasian) as the group attribute and is recid (recid. sex, priors_count
or no recid.) as the target for prediction. We use race, age, s_chaarge_degree e_jail in, c_jail_ out as the input features we include the group attribute an input feature. We use the last two features by taking their difference to their length _ta_t stay. We remove entries where COMPAS case could not be found iisirrecid- = -1) and entries with inconsistent arrest information. also binarize sex and remove traffic offenses. We quantize age the same way we in the Adult dataset and quantize length of _ta_stay by every 30 days and let 0 be separate category.
German Credit. We use age (below or above years old) as the group attribute and the credit column, which represents whether the loan was good decision, as the target for prediction. We use
20

---

loan duration in month, credit amount, age, number of existing credits at this bank, sex, credit history. savings, and length of present employment as input features. We include the group attribute age as an input feature. We group credit amount into three disjoint intervals: [0, 5000), [5000, 10000), (10000,00). We group duration of loan into two categories: under 36 months and over months.
HSLS. We use race as the group attribute and mathematics test score (number of questions an- swered correctly of 72) as the target for prediction. This is multi-group and multi-label dataset. The entire population is grouped by 4 categories: White, Asian, African American, and Others. We seek predict the mathematics test performance from set of attributes, including the scale of student's mathematical identity, scale of student's 's mathematics utility, scale of one's mathemat- ics self-efficacy, parent's 's education, parent's income, scale of student's sense of school belonging, race, and sex. Note that we include the group attribute as an input feature. We group the target column (estimated number of questions answered correctly) into a total of 5 disjoint intervals: [o, 30), [30, 40), [40, 50), [50, 60), [60, oo); we group the scale of student's 's mathematical identity, mathemat- ies utilityy mathematics self-efficacy, and sense of school belonging into a total of 4 disjoint intervals, characterized by standard deviations away from the mean: (-o0, -1), [-1, 0), [0, 1), (0)
C.3 Benchmark
Each benchmark method's hyper-parametter values are provided below. Each point in Figure for Baseline, EqOdda, CalEqOdds, Reduction, LevEqOpp. and FairProjection is obtained by applying the obtained classifier to 10 different test sets. For the Adult dataset, we use Ran- dom Forest with __ estimators=15, min samples_lcaf=3, criterion = log loss, bootstrap False as our baseline classifier; for the COMPAS dataset, we use Random Forest with n_ estimators as our baseline classifier. For the German Credit dataset, we use Random Forest with leaf=1 as our baseline classifier. They are all
estimators=100,min 1atimmattrrs110.mm_aaaammpppelp saaiilssmmmmpsseeee fhilesssstttt_t_eeeeee implemented by Scikit-learn (Pedregosa et al., 2011).
EqOdds (Hardt et al., 2016). We use AIF360 implementation of Eapddssostproceessing and the default byper-parameter setup.
CalEgOdds (Pleiss al., 2017). We use AIF360
implementation of
GelbbrateegggdssPoopprressss and the default hyper-parameter setup.
Reduction (Agarwal et al., 2018). We use AIF360 implementation of arppmeattaateddCrrddenedddceee
We vary the allowed fairness constraint violation c E 0.2, {0.001, 0.01, 0.2, 0.5, 1, 5, 10, 15) for Adult dataset and E (0.001, 0.01, 0.2, 0.5, 0,, 1, 10, 15)
for Adult with missing values. We vary e E (0.001, 2, 5, 10, 15, 20, 25, 30, 35, 40} for COMPAS to obtain fairness-accuracy curve, and {0.001, 0.1, 0.5, 1,2,7,8, 10, 10, 15, 20, 20.30) for COMPAS with 50% missing values in the minority group. We use E (20,50) 80, 95) for German Credit dataset and e (5, 8, 10, 20, 23] when using Bayes Optimal classifier.
Opp (Chzhen et al., 2019). We use the Python implementation of LevEqopp from the Github repo in Alghamdi et al. (2022). We follow the same hyperparameters setup as in the original method.
FairProjection Alghamdi et al. (2022). We use the implementation from the Github repo in Al- ghamdi al. (2022) and set use_ goe_prrtected
True. We use Random Forest with n estimators 17 as the baseline classifier to predict S from (X, Y). We set the list of fairness viola- tion tolerance be (0.07. 0.075, 0.08, 0.085, 0.09. 0.095, 0.1, 0.5, 0.75, 1.0] for Adult dataset and (0.02, 0.03, 0.04, 0.05, 0.06, 0.07, 0.08, 0.1, 1.0] for COMPAS dataset to obtain fairness- accuracy curve. We set the list of fairness violation tolerance to (0.005, 0.01, 0.02, 0.07, 0.1, 0.15) on the German Credit dataset experiment, and (0.0001, 0.001, 0.005, 0.01, 0.015, 0.02, 0.05) when using a Bayes optimal baseline classifier. For the HSLS dataset, the list of tolerance (0.06, 0.065, 0.07, 0.08, 0.1, 0.09. 0.15, 0.2, 0.33.
21

---

Aveid
Multiclass
Multigroup
Multi-sonstrann
Curve
disparatc trasmnett
Hand (2016)
Codbet-Davies ct (2017)
Menon and Williamson (2018)
X
x
X
/
Cluhien (2019)
x
x
X
X
Yang et al. (2020)
/
Zong et al. (2022a)
/
Zeng et al. (2022h)
X
Our approach
Table 2: Comparison with existing work that investigate the fairness Pareto frontier. Multi- class/multigroup:: can handle multiclass classification problems with multiple protected groups; Avoid disparate treatment: not require the classifier to use group attributes an input variable; Multi-constraint: can handle multiple (group) fairness constraints simultancously; Curve: produce faimess-acccuaacy accuracy trade-off curves (instead of a single point).
D More on Related Work
We provide detailed comparison with existing work fairness Pareto frontier and ML uncertainty in this section.
D.1 Fairness Pareto Frontier
We present in Table 2 detailed comparison of approach with previous studies that have investi- gated the fairness Pareto frontier and fair Bayes optimal classifier, In short, our approach different from this line of research it simultaneously combines several important aspects: it is applicable to multiclass classification problems with multiple protected groups; avoids disparate treatment by not requiring the classifier to use group attributes input variable; and it can handle multiple faimess constraints simultaneously and produce fairress-accuracy trade-off curves (instead of single point).
D.2 Aleatoric and Epistemic Uncertainty
In this paper, divide algorithmic discrimination into alcatoric and epistemic discrimination. We borrow this notion from MI. uncertainty literature (see Hüllermeier and Waegeman, 2021, for survey). Here provide detailed comparison between them.
In terms of their definitions, epistemic uncertainty arises from lack of knowledge about the best model, such as the Bayes predictor, while epistemic discrimination results from lack of knowledge about the optimal "fair" predictive model. On the other hand, aleatoric uncertainty is the irreducible part of uncertainty caused by the random relationship between input features and label, while aleatoric discrimination is due to inherent biases in the date-genera distribution.
In terms of their characterization, epistemic uncertainty can in principle be reduced by including additional information (e.g.. more data); epistemic discrimination can be reduced a similar approach since data scientist can choose more effective fairness-intervention algorithm with access to more information.
Finally, in the infinite sample regime, a consistent learner will be able to remove all epistemic uncertainty, assuming the model class is large enough and there no computational constraints. Analogously, we demonstrate in Figure that when the underlying distribution known, SOTA fairness interventions able eliminate epistemic discrimination their fairness-accuracy curves are close to the fair front.
E More on Future Work
In this paper, we present an upper bound estimate for FairFront in Algorithm 1. is important to note that this estimate may be subjected to errors originating from various sources. These include (i)
22

---

the approximation error of the function (ii) estimation errors from computing the expectation in (7) with a finite dataset, and (iii) the influence of hyperparameters, T (number of running iterations of Algorithm 1) and & (number of segments in the piece-wise linear functions). Regarding the dependence on T. our Theorem 2 ensures the algorithm's 's asymptotic convergence as However, we have not established a proof for its behavior at a finite T. Regarding the dependence on k, we conjecture that is the number of labels. While Blackwell proved this result for k 2 in Theorem 10 of Blackwell (1953), an extension of this proof a general value of k appears to remain an open problem.
co.
A should suffice, where is the number protected groups and C
We define aleatoric and epistemic discrimination with respect to the entire population. Investigating their per-instance counterparts and the relationship to individual fairness would be compelling area of future research. Additionally, more nuanced analysis of aleatoric and epistemic discrimination desirable, further breaking them down into fine-grainn one-grained components. For instance, epistemic discrimination may be attributed to various factors including limited training data, noisy observations of labels or sensitive attributes, and limitations of learning algorithms. Finally, investigating other criteria, such as scalability, generalization, and robustness in evaluating existing fairness interventions a significant topic for future exploration.
23


Reviews:
[{"review_id": "Wz53BytBCy", "reviewer": "Reviewer_iE9m", "summary": "In this manuscript, the authors make two main contributions to the technical study of algorithmic fairness.\n\nFirstly, on the conceptual level, they propose to distinguish between aleatoric and epistemic discrimination. By the former term, they refer to the notion that the optimal achievable performance level may differ between different (e.g., racial or gender-based) groups, corresponding to notions of differing task difficulty. No algorithmic bias mitigation approach can resolve aleatoric discrimination, which is a property of a dataset, not a model. Epistemic discrimination, on the other hand, refers to a model that performs sub-optimally on a given group, compared to the performance level it could achieve on this dataset.\n\nSecondly, the authors develop a new way to characterize an upper bound on the Fairness Pareto frontier, i.e., the frontier characterizing optimal trade-offs between overall model accuracy and various fairness constraints. The characterization is based on an old theoretical result by Blackwell and facilitates an efficient implementation by means of a greedy algorithm developed by the authors. This second contribution relates to the first in that it provides a lower bound on the level of aleatoric discrimination in a given dataset.\n\nSeveral numerical experiments in standard (low-dimensional, tabular) algorithmic fairness datasets confirm the validity of the bound and the relative tightness of some previously proposed bias mitigation techniques, emphasizing that significantly better trade-offs are unlikely to be achievable in these datasets. An experiment with artificially induced missing data shows how this increases aleatoric discrimination, as would be expected.", "questions": "1. As outlined in detail above: what are the implications of the approximation on g? How does this impact potential other application domains, such as image analysis? Do I understand correctly that in the tabular cases considered in the paper, g is not approximated but in fact computed exactly?\n2. I was a little confused by the notation in some places. For instance, the authors write that they \"define FairFront(αSP, αEO, αOAE) as the solution of the following optimization problem\", where the following optimization problem optimizes over a classifier h. However, later on, the authors use notation such as \"FairFront1(αSP, αEO, αOAE) ≥ FairFront2(αSP, αEO, αOAE)\", prompting me to ask: what exactly *is* \"FairFront\"? Is it the model? Its achieved accuracy? Something else? This could be made clearer by a notation such as \"FairFront = arg max ...\", for instance.\n3. How does the complexity of the algorithm scale with, e.g., the number of sensitive groups to be considered? The authors emphasize that their approach \"can be easily extended to the setting where multiple subgroups overlap\"; how exactly would this work? In the case of multiple non-binary sensitive attributes, the number of subgroups to consider grows combinatorially; will that present practical problems?\n4. To give practitioners some sense of the complexity of Algorithm 1, could the authors provide run time measurements for the case studies?", "limitations": "1. Like outlined above, the limitations induced by approximating g are presently not obvious to me; I could imagine these to be quite consequential if they effectively limit the applicability of the presented work to low-dimensional tabular data.\n2. More generally, the authors do not discuss any limitations of their approach. One limitation that comes to my mind is that it has been shown repeatedly that fairness-accuracy trade-offs may be illusory in the case of group-dependent label noise or selection biases, see, e.g., Blum and Stangl (2020), Wick et al. (2019), Dutta et al. (2020). Another limitation seems to be that the presented approach relies on the availability, correctness, and validity of sensitive attributes, which is often not given; see, e.g., Jacobs and Wallach (2021) and Tomasev et al. (2021).\n\nBlum and Stangl (FORC 2020): Recovering from Biased Data: Can Fairness Constraints Improve Accuracy? https://drops.dagstuhl.de/opus/volltexte/2020/12019/pdf/LIPIcs-FORC-2020-3.pdf\n\nDutta et al. (ICML 2020): Is There a Trade-Off Between Fairness and Accuracy? A Perspective Using Mismatched Hypothesis Testing. https://proceedings.mlr.press/v119/dutta20a.html\n\nJacobs and Wallach (FAccT 2021): Measurement and Fairness. https://dl.acm.org/doi/10.1145/3442188.3445901\n\nTomasev et al. (FAccT 2021): Fairness for Unobserved Characteristics: Insights from Technological Impacts on Queer Communities. https://dl.acm.org/doi/10.1145/3461702.3462540\n\nWick et al. (NeurIPS 2019): Unlocking Fairness: a Trade-off Revisited. Unlocking Fairness: a Trade-off Revisitedhttps://papers.nips.cc/paper/2019/file/373e4c5d8edfa8b74fd4b6791d0cf6dc-Paper.pdf", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper makes several highly original and important contributions to the algorithmic fairness field.\n\nThe framing of different sources of algorithmic discrimination as separated into aleatoric and epistemic discrimination is novel, and it importantly helps in understanding and characterizing the limitations of bias mitigation techniques, which can only ever aim to reduce epistemic discrimination. While similar distinctions have been made before, I find the framing and formulation presented in the manuscript particularly clear and useful.\n\nTo my knowledge, the manuscript provides the first characterization of an *upper* bound on the Pareto frontier, the latter being an essential object of study in algorithmic fairness. It also treats the general case of both multiple sensitive groups and multiple output labels, which is relatively rare in the field (which mostly focuses on the binary setting for both.)\n\nThe manuscript introduces a novel theoretical tool, based on the old results of Blackwell, into the field of algorithmic fairness, which may spark further theoretical innovations beyond the present paper. I consider this alone to be an important creative contribution.\n\nThe paper is very well written, the results are clearly presented, and prior work is comprehensively discussed and acknowledged.", "weaknesses": "I do not see many weaknesses in the manuscript, but there is one issue that I think deserves a more comprehensive discussion. This is related to the approximation of g, which maps inputs X to P(S,Y | X), where Y is the output label and S the sensitive group. As I understand it, the correctness of the approximated upper bound depends crucially on the correctness of this approximation. In the simple low-dimensional tabular data cases considered in the manuscript, g can be computed efficiently and precisely, but in the case of more complex (continuous, image?) domains, I would imagine this to be a serious limitation. Do I understand correctly that if g is approximated poorly, the computed bound may in fact not be an upper bound? I would appreciate a more comprehensive discussion of the impact of this approximation on the correctness of the estimated upper bound.\n\nAlso, can the authors provide some hints at important future extensions of the presented work, or important limitations of the approach? Section 5 is called \"Final Remarks and Limitations\", but it actually only summarizes the contributions of the present manuscript and lists no limitations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful comments and for appreciating the novelty of the work!\n\n---\n**Q1. Approximation of $g$ and the impact on the estimated upper bound.**\n\nA1. Yes, your understanding is correct! The approximation error of $g$ can influence the estimation of $FairFront$. If $g$ is not approximated accurately, the estimation might not serve as an upper bound any longer.\n\nTo circumvent this issue, we applied fairness interventions to the entire dataset in our experiments and subsequently resampled 30% of the data for the test set (see lines 276-278). In this case, $g$ can be precisely computed from the empirical distribution without any error, and FairFront gives an information-theoretic upper bound. Generally, for low-dimensional tabular data, we anticipate that the approximation error of $g$ won't be significant, given the relative ease of training well-calibrated base models like random forests to predict S and Y from X. We acknowledge that in other domains, this approximation error might be significant. A practical solution would be bootstrapping confidence intervals for refitting the curve over data splits. Nonetheless, a theoretical characterization of the extent to which this error impacts the estimation of $FairFront$ remains an open problem (please refer to our A2 for discussions about the limitations which will be included in the last section).\n\n---\n**Q2. Future extensions and important limitations.**\n\nA2. Thank you for highlighting this matter. In response to your concerns, we provide a discussion on the limitations and potential future directions below. We will ensure this discussion is incorporated into the revised paper.\n\nIn this paper, we present an upper bound estimate for $FairFront$. However, it is important to note that this estimate may be subjected to errors originating from various sources. These include (i) the approximation error of the function $g$, (ii) estimation errors from computing the expectation in Eq. (6) with a finite dataset, and (iii) the influence of hyperparameters, $T$ (number of running iterations of Algorithm 1) and $k$ (number of segments in the piecewise linear functions). Regarding the dependence on $T$, our Theorem 2 ensures the algorithm's asymptotic convergence as $T \\to \\infty$. However, we have not established a proof for its behavior at a finite $T$. Regarding the dependence on $k$, we conjecture that $k = A * C$ should suffice, where $A$ is the number of subgroups and $C$ is the number of labels. While Blackwell proved this result for $k=2$ in his 1953 paper's Theorem 10, an extension of this proof to a general value of $k$ is an open problem.\n\nWe define aleatoric and epistemic discrimination with respect to the entire population. Investigating their per-instance counterparts and the relationship to individual fairness would be a compelling area of future inquiry. Additionally, a more nuanced analysis of aleatoric and epistemic discrimination is desirable, further breaking them down into fine-grained components. For instance, epistemic discrimination may be attributed to various factors including limited training data, noisy observations of labels or sensitive attributes, and constraints of learning algorithms. Characterizing each of these components and devising appropriate solutions to mitigate them can lead to a more comprehensive taxonomy of sources of bias and (un)fairness in classification and prediction. Lastly, further exploration of other evaluation criteria, such as scalability, generalization, and robustness against partial knowledge of group attributes in the context of benchmarking existing fairness interventions is a valuable avenue for future research.\n\n---\n**Q3. Implications of the approximation on $g$ and how this impacts potential other application domains.**\n\nA3. Please refer to A1.\n\n---\n**Q4. What exactly is FairFront?**\n\nA4. Thank you for bringing up this concern. To clarify, $FairFront(\\alpha)$ measures the maximal *achieved accuracy* of the model, given that its discrimination violation is upper bounded by $\\alpha$.\n\nMathematically, \n$$FairFront(\\alpha_{SP}, …) := \\max_{h} Accuracy(h)\\ s.t. SP(h) \\leq \\alpha_{SP}, ...$$\n\n$FairFront_{k}$ is an upper bound approximation of $FairFront$ using $k$-piecewise linear functions. We will clarify this in the revised paper.\n\n---\n**Q5. Scalability with the number of sensitive groups.**\n\nA5. As the number of protected groups, denoted by $A$, increases, both the number of variables in the convex program and the DC program in Alg. 1 increase linearly with $A$. Note that the running time of standard convex/DC program solvers is only mildly dependent on the number of variables (see e.g., the dimension-indep. convergence bounds in Cor. 4.1 in Abbaszadehpeivasti et al. 2023 and Thm. 5 in Faust et al. 2023). In our experiments, we also observed that even when doubling the number of groups and labels, 20 iterations consistently suffice for our algorithms to converge.\n\n–Abbaszadehpeivasti etal., 2023. On the rate of convergence of the difference-of-convex algorithm (DCA).\n\n–Faust etal., 2023. A Bregman Divergence View on the Difference-of-Convex Algorithm.\n\n---\n**Q6. Provide run time measurements for the case studies**\n\nA6. Below, we present the runtime of Alg. 1 across various datasets of different scales. All experiments were run on a personal computer with 10 CPU cores and 16GB memory. We did not optimize our Python implementation (e.g., using GPUs) so the run time could be further reduced.\n\nGerman credit (1000 rows, 21 features): 0.53 mins\n\nCOMPAS (5278 rows, 7 features): 1.73 mins\n\nAdult (46447 rows, 8 features): 6.11 mins\n\nHSLS (10937 rows, 9 features): 12.33 mins\n\n---\n**Q7. The limitations induced by approximating g**\n\nA7. Please refer to A1.\n\n---\n**Q8. Not discuss any limitations of their approach.**\n\nA8. Thank you for sharing your thoughtful insights and providing the associated references. Please refer to A2 for a detailed discussion regarding limitations."}, {"review_id": "t8LGrk3v4s", "reviewer": "Reviewer_CXu9", "summary": "The paper casts the issue of fairness in machine learning from the perspective of two classes of discrimination: those due to aleatoric uncertainty, or where the inherent limitations of the data distribution, and epistemic discrimination, which is due to modeling choices. It then uses this framework to analyze a common set of fairness metrics, showing that epistemic discrimination can be reduced by optimizing for these fairness measures, but not necessarily aleatoric discrimination. ", "questions": "Are you able to run experiments that involve a bit more complex sources of data variability (e.g. a natural language task with different dialects, so more than 2 group labels, and using more state-of-the-art models like GPT series)? ", "limitations": "I think the paper could also be more clear on the importance of the overall result. Lacking in thorough experimentation, the paper largely presents a framework but does not argue for its utility. Do the authors intend their framework to be used as a rigorous benchmark? If so, they should focus on more comprehensive set of experiments. Otherwise, what is the core message of knowing that methods that are not data-specific do not address dataset-specific sources of discrimination? ", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "- The choice to disentangle sources of discrimination due to modeling choices vs. data properties is sound and reasonable. \n- To the best of my knowledge, studying aleatoric discrimination via Blackwell's equations is novel (the reviewer is not familiar with this set of techniques, so can offer little here)\n- The choice to study missing data values is natural. ", "weaknesses": "My main concern with this paper was that its contribution feels quite limited both in terms of thoroughness of the experiments (it would have been interesting to study different sources of data properties beyond miss values, such as Khani & Liang, 2020) do with spurious features, as well as its relevance in modern machine learning (the only data studied is the well-known COMPAS dataset, and it could have been interesting to consider situations where more advanced models -- such as language or vision models -- are applied, as well as settings where the motivation to apply ML is well justified unlike risk assessment). \n\nI also think the authors could clarify quite early on they specific a particular subset of fairness interventions - group fairness with defined subgroup labels. This is not always possible when subgroups aren't clearly defined, challenging to measure, or are intractable. \n\nIn a similar vein, the writing could be more precise to properly convey the scope of FairFront. For example, sentences like \" For instance, if the training set contains few samples from a given population group, then increasing sample diversity is a more effective strategy than  selecting a more complex model class or training strategy.\" --> there are training methods that try to account for unequal group size (e.g. Hashimoto, 2018)) when group labels are inaccessible, and increasing sample diversity is hard. These sentences could just be qualified more that we are in a particular setting where we know the groups we want to be fair over, and can measure them. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the kind comments and the encouragement!\n\n---\n**Q1. Contribution feels limited both in terms of experiments and its relevance in modern machine learning.**\n\nA1. Thank you for raising this important point. First, please note that we provide numerical results for **four** benchmark datasets: Adult, COMPAS, German Credit, and HSLS. Both German Credit and HSLS results are presented in Appendix C. We highlight that the HSLS dataset is a multi-class classification task with multiple protected groups that first appeared in the ML literature last year, and captures a common use-case of ML in education (student performance prediction, see Jeong etal., 2022). We also compared FairFront against **five** group fairness interventions (see 265-278). These include Reduction and FairProjection which are, to our knowledge, the state-of-the-art in terms of fairness-accuracy frontiers. The scale of our numerical results is comparable to recent comprehensive benchmarks of fairness interventions with publicly available reproducible code (cf. Alghamdi etal. in NeurIPS 2022).\n\nWe highlight that our choice of presenting Adult and COMPAS in the main text was strategic. These datasets, and especially COMPAS, have been extensively used as benchmarks in fairness research. Our findings on them show that there are *diminishing returns* in benchmarking new fairness interventions on these datasets and that existing methods approach the information-theoretically optimal Pareto frontier given by FairFront (see line 323). We believe this sends a pivotal, theoretically-grounded message to the community to innovate beyond these overused datasets. The choice of these two datasets for the main text was also practical: most interventions can be readily applied to them without change, allowing for more comprehensive benchmarks of existing methods against FairFront (see the five methods in Figure 1).\n\nWe certainly appreciate the suggestion on exploring more advanced models and other data properties. It aligns well with our vision, as we touch upon in lines 26-27 and in our final remarks. Our intent is to drive the field towards addressing fresh challenges in responsible ML rather than refining on established datasets. Again, a main contribution of our paper is that there is no room for improvement in terms of vanilla group fairness/accuracy values of these overused datasets. As a field, we should perhaps close this research chapter and move to new challenges in responsible ML such as the ones you mentioned.\n\n---\n**Q2. Group fairness with defined subgroup labels. This is not always possible when subgroups aren't clearly defined, challenging to measure, or are intractable.**\n\nA2. Thank you for pointing this out – we will clarify this in the introduction. As we mentioned above, one of our main goals is to demonstrate that the subset of fairness interventions optimized solely for group fairness metrics where groups are well-defined appear to achieve the information-theoretic best on standard benchmarks. There are hundreds of such interventions proposed in the past decade, and we hope our results provide theoretical backing for the field to move on to more realistic and pressing issues such as the ones you suggest. The case where subgroups aren't clearly defined (or represented by a set of functions, such as in multiaccuracy and multicalibration) is not covered by our results, but is indeed an important research direction. We will stress this limitation in the final section.\n\n---\n**Q3. There are training methods that try to account for unequal group size (e.g. Hashimoto, 2018)) when group labels are inaccessible, and increasing sample diversity is hard.**\n\nA3. You are correct, and we will qualify the scope of FairFront in a revised manuscript. Specifically, we will add that:\n\n\"When group labels are inaccessible or only partially accessible, increasing sample diversity can be challenging. In such cases, fairness interventions that account for only partially observed group attributes (e.g., Hasimoto, 2018) are a compelling alternative.\"\n\n---\n**Q4. Run experiments that involve more complex sources of data variability (e.g. a natural language task with different dialects, so more than 2 group labels, and using more state-of-the-art models like GPT series)?**\n\nA4. Thank you for your suggestion about exploring tasks like natural language with varied dialects and using advanced models such as the GPT series. We note that our scope is tabular datasets, since this allows us to benchmark state-of-the-art fairness interventions against the theoretical optimum given by FairFront.\n\nWhile gathering dialect-based datasets and training and/or probing LLMs is challenging given our limited resources, we reiterate the additional results in Appendix C that include other datasets (e.g., HSLS, where there are multiple groups). As we mentioned in the response to your Q1, a central theme in our paper is to demonstrate that existing fairness interventions are approaching the information-theoretic optimal fairness-accuracy Pareto frontier on widely-used datasets. We are excited to include your suggestion in our concluding section as a compelling direction for future work, particularly in light of our findings on the diminishing returns of focusing on overused tabular datasets.\n\n---\n**Q5. Importance of the overall result. Lacking in thorough experimentation. What is the core message?**\n\nA5. Please refer to our responses to your Q1, Q2, and Q4. In short, the core message in this study is that there are *diminishing returns* in benchmarking new fairness interventions on standard (overused) datasets as existing methods are approaching the information-theoretically optimal Pareto frontier delineated by FairFront. We back this claim with numerical results from 4 benchmark datasets, tested against 5 state-of-the-art fairness interventions."}, {"review_id": "9UqWrbJqWU", "reviewer": "Reviewer_wKi3", "summary": "This paper proposes a decomposition of discrimination (in ML classifiers) into aleatoric (irreducible) and epistemic (reducible) components. The paper surveys related work in fairness. It then introduces and discusses the Fairness Pareto Frontier, which is essentially an upper bound on the accuracy of the best possible fairness constrained classifier. The paper proposes an algorithm for estimating aleatoric discrimination (this upper bound) which utilizes Blackwell’s results on comparing statistical experiments. It then demonstrates the applicability of the algorithm through experiments on 5 datasets. Finally, it identifies missing values in the dataset as a source of aleatoric discrimination,  providing experimental evidence to support the discussion. ", "questions": "When the fairness constraints are trivially satisfied, for example $\\alpha_{\\text{SP}}, \\alpha_{\\text{EO}}, \\alpha_{\\text{OAE}} = \\inf$, how should one interpret the FairFront? \n\nLine 231: what is meant by “mostly violated”?\n", "limitations": "The paper refers to fairness and discrimination, but makes no effort to connect these concepts to the harms or benefits experienced by real people. This is fairly common practice in the field and not unique to this paper. However, it is nonetheless a noteworthy limitation. That is to say, one cannot truly comment on the fairness (or discrimination) of a machine learning system without a broader understanding of the social impacts–beyond just its predictions. \n\nIt is unclear whether the method can be applied in the numerous important situations whereby the prediction outcome is unobserved (or partially observed), and what effects estimating these counterfactuals would have on the method, e.g., in lending–where the outcomes of the rejected cohort are counterfactuals. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "Though I was admittedly not familiar with Blackwell’s results, the paper’s technical contributions are insightful and convincing. \nThe paper makes a novel connection to statistical results that (as far as I am aware) had not been considered previously in fairness research.\nThe theoretical framework and results, as well as the estimation method are applicable to a wide range of fairness-constrained predictive modelling problems (multi-class, multi-attribute), and thus are a substantial contribution to the field.\nThe paper does a good job of surveying related work, and distinguishing its contributions. \nThe writing is concise and of high quality. \n", "weaknesses": "The paper is dense and would benefit considerably from an illustrative example, helping to build intuition about the terms and concepts introduced. Specifically to help digest the main theoretical result, Theorem 1, and the piece-wise linear approximation. \n\nThe paper presents FairFront as an upper bound whose estimate depends on k, and T. However, for a given data distribution, it is unclear how the k-dependence is affected by the quantity of available data. As a practitioner, I would want to understand the robustness of this upper bound to data availability. Some experiments that subsample the dataset would be a helpful starting point. Perhaps a version of the experiment discussed in Appendix C.2 with varying levels of data availability (up to the infinite data regime). \n\nThe region described as epistemic discrimination (if Figure 1) is effectively a gap between an upper bound (FairFront) and a lower bound (some fairness-constrained modelling approaches). As such, the true fairness Pareto Frontier is somewhere in between. It is unclear why the reader should interpret FairFront as the more accurate bound, and thus interpret the gap as epistemic discrimination (rather than FairFront estimation error). That is to say, the paper could elaborate on the tightness of this approximate upper bound based on choices of k and T. \n\nThe use of transparency in Figure 2 makes it difficult to compare scenarios (missing probabilities), especially when printed. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful review and for appreciating the merits of the work!\n\n---\n**Q1. An illustrative example, helping to build intuition about the terms and concepts introduced.**\n\nA1. We thank the reviewer for this valuable suggestion. One concrete example is the COMPAS dataset. It has been overused in the field, leading to recent calls to move on from it as a benchmark. Nevertheless, since its public release, hundreds of group fairness interventions have been proposed and benchmarked on this dataset, amounting to hundreds of achievable fairness-accuracy pairs. A natural question to ask is: are we close to the optimal Pareto Frontier on this dataset? FairFront – a theoretical upper bound for the *best* achievable fairness accuracy frontier – proves that we are indeed close to the optimal frontier when these datasets reflect the true underlying distribution. This provides theoretical backing to the sentiment of moving on from such datasets and optimizing solely for group fairness and accuracy.\n\nPlease also refer to Appendix B.4 for two technical examples that illustrate our results in special cases (Remark 2: $X$ and $(S,Y)$ are independent; Remark 3: $X$ is discrete). \n\n---\n**Q2. The estimate of FairFront depends on $k$ and $T$. It is unclear how the k-dependence is affected by the quantity of available data.**\n\nA2. This is a great suggestion! Regarding k-dependence, we conjecture that $k = A * C$ should suffice, where $A$ is the number of protected groups and $C$ is the number of labels. While Blackwell proved this result for $k=2$ in his 1953 paper's Theorem 10, he didn't extend his proof for a general $k$. In the context of infinite data, our experiments have numerically verified this conjecture, and it has consistently held true. As for T-dependence, we observed in our experiments that setting $T = 20$ always ensured algorithm convergence.\n\n---\n**Q3. The gap between an upper bound (FairFront) and a lower bound (fairness-constrained approaches). The tightness of this approximate upper bound based on choices of $k$ and $T$.**\n\nA3. You are right: the gap can be the result of the estimation error or epistemic discrimination. Nonetheless, we observed in our experiments that the estimation error tends to be quite small when $k\\geq A*C$ and $T=20$. Broadly, the theoretical characterization of the estimation error of FairFront, as well as its dependence on $k$ and $T$ remains an open question. We will address this issue in the limitations section of our revised paper.\n\n---\n**Q4. The use of transparency in Figure 2.**\n\nA4. We apologize for this inconvenience and will use distinct colors to represent different missing probabilities. \n\n---\n**Q5. When $\\alpha_{SP}, … = \\inf$, how to interpret FairFront?**\n\nA5. When the fairness constraints are trivially satisfied, FairFront evaluates the accuracy of the Bayes optimal classifier.\n\n---\n**Q6. What is meant by “mostly violated”?**\n\nA6. Suppose $P$ does not belong to $\\mathcal{C}_k$. We will find a piecewise linear function that partitions the space into two regions. One region contains $P$ and the other one contains $\\mathcal{C}_k$. “Mostly violated” means we construct this function by *maximizing* the distance between $P$ and the boundary defined by the function. \n\n---\n**Q7. The paper refers to fairness and discrimination but makes no effort to connect these concepts to the harms or benefits experienced by real people.**\n\nA7. Thank you for highlighting this critical aspect. We fully agree: understanding the real-world impacts and harms on real people goes well beyond the limited technical and mathematical metrics often emphasized in ML research. \n\nOur paper's main message is that existing fairness interventions optimized solely for group fairness and validated on overused datasets like Adult and COMPAS are provably nearing their theoretical best in terms of specific group fairness metrics and accuracy. Rather than just adding to such interventions, our results provide theoretical backing to your sentiment that it's time for the community to move on from incremental improvements on these benchmarks. For example, as we argue in Section 4.2, addressing real-world challenges, like data with missing values where these patterns correlate with group attributes, is crucial. Our findings partially close the chapter on the myopic approach of designing interventions optimized entirely for group fairness metrics and benchmarking on overused datasets: in this limited setting – for which hundreds of interventions have been produced – we are already close to the information-theoretic best!\n\nYou're right; we could have delved deeper into the broader social implications of our findings. In our final remarks, we'll stress the importance of moving beyond just numbers to consider the tangible effects on real individuals and the practical factors impacting data quality – this was indeed the core motivation for our work, and we hope to send a signal that we should focus on other problems beyond simply group fairness and accuracy on datasets such as COMAPS. We value your feedback and will emphasize this perspective in the revised manuscript.\n\n---\n**Q8. Whether the method can be applied when the prediction outcome is unobserved (or partially observed).**\n\nA8. Thank you for pointing out this scenario. Indeed, our technique can be applied to estimate FairFront where prediction outcomes are unobserved or partially observed. This is because Algorithm 1 only requires a classifier $g$ that predicts $(S,Y)$ from $X$, along with the probability distribution of unlabeled data for computing the expectation. If the prediction outcome is unobserved, one could learn the function $g$ using a one-class classification method. However, we caveat that the approximation error of $g$ may increase, potentially affecting the accuracy of estimating FairFront."}, {"review_id": "ol4t6oA0DL", "reviewer": "Reviewer_7W2X", "summary": "This paper splits discrimination in machine learning into aleatoric (which is that inherent to the data distribution), and epistemic (which is that due to choices in the model). They use Blackwell’s results to characterize the fairness Pareto frontier curve. Then, on 4 datasets with 5 fairness interventions, they characterize how close to their upper bound the algorithms are able to achieve.", "questions": "Listed above in weaknesses. ", "limitations": "I think that the authors could be more upfront about the limitation that their work maps out the upper bound of the FairFront rather than the FairFront exactly, and also that they have taken a rather narrow lens of fairness, neglecting broader societal concerns.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "- Comprehensive set of experiments on a number of datasets and fairness interventions\n- Clear writing and presentation of work\n- Claims are backed up by theories and proofs", "weaknesses": "- Given that the output from the algorithm (L236) is always the upper bound for FairFront, rather than exactly FairFront, I wish the paper would have been more upfront with this throughout, especially in the introduction and abstract, because I found this a bit misleading\n- Even though the names of aleatoric and epistemic discrimination are taken from prior work, I think they should be potentially rethought because for example, “epistemic discrimination” feels like a term that should be restricted to the philosophical foundations of the word “epistemology,” e.g., as it is used in epistemic injustice (https://academic.oup.com/book/32817), rather than a not-so related mathematical constraint\n- Given that a primary differentiation from prior work (L76) is that it works on multiclass classification as well as multiple protected groups, I would have liked to see empirical results on this rather than just claiming this is true\n- Given how similar the motivation of this work is to Chen, I. et al. (NeurIPS 2018)’s, I would have liked to see a deeper comparison of the findings of both works\n- “Discrimination” as used in this paper is only restricted to different forms of measurement disparities, e.g., statistical parity, equalized odds, and excludes many other forms of algorithmic discrimination that are more structural. So, sentences like L35 “We divide algorithmic discrimination into two categories” should be caveated that this is only a very specific form of algorithmic discrimination that is being divided into two categories (https://aclanthology.org/2020.acl-main.485/)\n  - As further explanation, taxonomies of algorithmic discrimination are its own genre of normative research, for example the distinction between representational vs allocational harms (https://www.youtube.com/watch?v=fMym_BKWQzk), or a taxonomy of harms within representational harms (https://arxiv.org/abs/2305.01776)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the reviewer for the kind comments and the encouragement!\n\n---\n**Q1. Algorithm (L236) is always the upper bound for FairFront. More upfront with this throughout.**\n\nA1. Thank you for raising this concern. We will clarify that we provide an upper bound estimate of $FairFront$ in the introduction and abstract. \n\n---\n**Q2. The names of aleatoric and epistemic discrimination.**\n\nA2. We appreciate your insightful comment regarding the potential ambiguity associated with our terminology. We will address this confusion in the revised paper. For clarity, we borrow these terms from the uncertainty literature (see Appendix D.2). Therein, epistemic uncertainty refers to the reducible uncertainty stemming from a lack of knowledge about the best model, while aleatoric uncertainty is the inherent, irreducible uncertainty due to random associations between input features and labels. Analogously, epistemic discrimination arises from a lack of knowledge about the optimal fair predictive model, whereas aleatoric discrimination pertains to the irreducible aspects attributed to inherent biases in the data-generating distribution.\n\n---\n**Q3. Empirical results on multiclass classification and multiple protected groups.**\n\nA3. Please refer to Figure 4 in Appendix where we conducted experiments on the HSLS dataset with 4 groups and 5 labels. In short, our observation is consistent: state-of-the-art fairness interventions are effective at reducing epistemic discrimination as their fairness-accuracy curves are close to FairFront.\n\n---\n**Q4. Deeper comparison with Chen et al. (NeurIPS 2018).**\n\nA4. Chen et al. (2018) decomposed group fairness measures into bias, variance, and noise in their Theorem 1 and proposed strategies for reducing each term accordingly. There are two notable differences compared with their work.\n\nFirst, Theorem 1 in Chen et al. (2018) provides a decomposition for only a *single* group fairness metric. In contrast, our FairFront provides a more comprehensive analysis, characterizing the fundamental trade-offs between *multiple* group fairness metrics and *accuracy* among all classifiers. This analysis is more technically complex, as the interactions between different group fairness metrics and accuracy can incur tradeoffs, or in some cases, may even be mutually exclusive (as evidenced by the impossibility results [Kleinberg etal., 2016; Chouldechova, 2017]). \n\nSecond, the applications of our method are different from Chen et al. (2018). We specifically applied our method to benchmark existing fairness interventions, showcasing their effectiveness in eliminating epistemic discrimination across group fairness metrics. The analysis in Chen et al. (2018) is not suited for this purpose, as it solely considers a singular fairness metric. Additionally, we studied how the presence of missing values can impact aleatoric discrimination, thereby diminishing the effectiveness of fairness interventions. Note that the challenge posed by missing values has been generally neglected in the existing literature, including in the work of Chen et al. (2018). We hope that our efforts can inspire further research into this subject, contributing to the development of algorithms aimed at reducing biases under these conditions.\n\n---\n**Q5. “Discrimination” used in this paper is only restricted to different forms of measurement disparities.**\n\nA5. We appreciate the reviewer for highlighting this crucial issue. We will explicitly state that our focus is limited to a specific form of algorithmic discrimination, namely, performance disparity across protected groups; other types of algorithmic discrimination or situations where group attributes are not clearly defined would require a non-trivial extension of our results.\n\n---\n**Q6. Taxonomies of algorithmic discrimination are its own genre of normative research, for example the distinction between representational vs allocational harms, or a taxonomy of harms within representational harms.**\n\nA6. We thank the reviewer for pointing out these important references. As mentioned above, we will highlight that our focus is on statistical aspects of a specific form of algorithmic discrimination (performance disparities). We will also add the references you mentioned, specifically on the distinction between representation and allocational harms, as well as on active research on disentangling the range of normative concerns often bundled as \"unfairness\" or \"discrimination.\" We will also highlight that, as posed by Katzman et al. (2023), no single measurement approach for \"fairness\" is definitive, particularly across different contexts and use cases.\n\n---\n**Q7. More upfront about the limitation that their work maps out the upper bound of the FairFront. A rather narrow lens of fairness, neglecting broader societal concerns.**\n\nA7. Thank you for raising these important points. We hope our response in A1, A5, and A6 has addressed all of your comments. Please feel free to let us know if you have any additional comments that can help us further improve the paper."}, {"review_id": "va9LqBid0M", "reviewer": "Reviewer_D24A", "summary": "The manuscript introduces FairFront i.e., an estimation for the upper bound on the Pareto Frontier for Fairness and Accuracy. The authors empirically show the tightness of this bound by showing how SOTA approaches perform close to the FairFront, while the gap may be attributed to the distributional variations.", "questions": "It is hard to see intuitively why FairFront works e.g., why is the markov chain $(S, Y) - X- \\hat(Y)$? How does it filter out valid classifiers?\n\nI acknowledge that I read the response and I feel overall the rebuttal was satisfying.", "limitations": "No. \n\n- From Lemma 1, it appears that one of the limitations of this work is that the FairFront is only applicable to convex classifiers.\n- I would highly suggest renaming the terms 'epistemic' and 'aleatoric' discrimination since they do not portray the corresponding uncertainty counterparts accurately and may lead to confusion. Terms such as 'Distributional Discrimination' may be more fitting.", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The authors tackle the problem of finding the upper bound on the Pareto frontier in contrast to prior works which focus on the lower bound.\n- The approach presented in the manuscript is theoretically grounded (by the essence of using Blackwell's results).\n- SOTA approaches are used to show the tightness of the bound empirically.", "weaknesses": "- The biggest weakness is that epistemic and aleatoric discrimination are terms introduced in the paper which have a link to the corresponding concepts in the uncertainty literature. However, the way these terms are used contradicts the definitions of the uncertainty counterparts e.g., Aleatoric uncertainty is linked to missing data (line 14-15, 65-66, 250-251). In prior literature, the lack of data falls in the domain of epistemic uncertainty [1][2][3].\n- In the manuscript, Aleatoric discrimination is linked to distributional differences. However, prior work either differentiates it from both aleatoric and epistemic uncertainty[4] or considers it as a part of epistemic uncertainty [5 (Section 9.2 dedicated to this topic)].\n- It is mentioned that distributional differences are largely a grey area in prior work. However, works such as FairBatch [6] and FairMixup [7], tackle such cases and are ideal for inclusion in the experiments.\n- The manuscript is a bit hard to follow. Even though it has content for describing which components are used formally, there is little intuitive background. Some links are hard to follow. e.g. it is not immediately obvious that $(S, Y) - X - \\hat{Y})$ refers to the Markov chain in Definition 2. It is not evident why this is used as the Markov chain.\n\n\n[1] Swiler, Laura P., Thomas L. Paez, and Randall L. Mayes. \"Epistemic uncertainty quantification tutorial.\" _Proceedings of the 27th International Modal Analysis Conference_. 2009.\n[2] Shaker, Mohammad Hossein, and Eyke Hüllermeier. \"Aleatoric and epistemic uncertainty with random forests.\" _Advances in Intelligent Data Analysis XVIII: 18th International Symposium on Intelligent Data Analysis, IDA 2020, Konstanz, Germany, April 27–29, 2020, Proceedings 18_. Springer International Publishing, 2020.\n[3] https://docs.aws.amazon.com/prescriptive-guidance/latest/ml-quantifying-uncertainty/epistemic-uncertainty.html\n[4] Amini, Alexander, et al. \"Deep evidential regression.\" _Advances in Neural Information Processing Systems_ 33 (2020): 14927-14937.\n[5] Varshney, Kush R. \"Trustworthy Machine Learning.\" _Chappaqua, NY_ (2021).\n[6] Roh, Yuji, et al. \"FairBatch: Batch Selection for Model Fairness.\" _International Conference on Learning Representations_.\n[7] Mroueh, Youssef. \"Fair Mixup: Fairness via Interpolation.\" _International Conference on Learning Representations_. 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer’s their careful reading of our paper and thoughtful comments! \n\n---\n**Q1. Epistemic and aleatoric discrimination and their link to uncertainty literature.**\n\nA1. We thank the reviewer for highlighting this crucial point. Below, we discuss their link to uncertainty literature.\n\nIn terms of their definitions, epistemic uncertainty arises from a lack of knowledge about the best model, such as the Bayes predictor, while epistemic discrimination results from a lack of knowledge about the optimal fair predictive model. On the other hand, aleatoric uncertainty is the irreducible part of uncertainty caused by the random relationship between input features and label, while aleatoric discrimination is also the irreducible part due to inherent biases in the data-generating distribution.\n\nIn terms of their characterization, epistemic uncertainty can in principle be reduced by including additional information; epistemic discrimination can be reduced in a similar approach by e.g., adding more data, as a data scientist can choose a more effective fairness-intervention algorithm with access to more information.\n\nIn the infinite sample regime, a consistent learner will be able to remove all epistemic uncertainty, assuming the model class is large enough and there are no computational constraints. Analogously, we demonstrate in Fig. 5 that when the underlying distribution is known, SOTA fairness interventions are able to eliminate epistemic discrimination as their fairness-accuracy curves are close to the fair front.\n\nYou are right: the lack of data falls in the domain of epistemic uncertainty. However, the missing data we are discussing is not about missing rows, but rather missing feature values. Indeed, this aligns with the literature on uncertainty, see Fig. 5 on page 466 of [Hüllermeier and Waegeman, 2020] for a discussion on how missing feature values can amplify aleatoric uncertainty.\n\nReferences:\n\n--Hüllermeier, E. and Waegeman, W., 2021. Aleatoric and epistemic uncertainty in machine learning: An introduction to concepts and methods.\n\n---\n**Q2. Aleatoric discrimination and distributional differences.**\n\nA2. We’d like to clarify that distributional shift is a form of epistemic discrimination. To understand this, recall that aleatoric discrimination is only based on the properties of the deployed data distribution. It is quantified under the assumption of having complete knowledge of this data distribution (that is, as if an infinite amount of deployed data is available). In contrast, distributional shift arises due to the imperfect knowledge of the deployed data distribution as we can only observe $P_{train}$ which differs from $P_{deploy}$. Hence, by observing more samples from $P_{deploy}$, $P_{train}$ would be “closer” to $P_{deploy}$, and as a result, fairness interventions trained on $P_{train}$ and tested on $P_{deploy}$ could demonstrate an improved fairness-accuracy curve. This would lead to a reduction in epistemic discrimination.\n\n\n\n\n---\n**Q3. Distributional differences are largely a grey area in prior work. However, works such as FairBatch and FairMixup, tackle such cases and are ideal for inclusion in the experiments.**\n\nA3. We thank the reviewer for pointing out the missing references, which will be cited in the revised paper. As mentioned in A2, distributional difference is related to the form of epistemic discrimination. Hence, these two works align with the line of fairness interventions aimed at reducing epistemic discrimination, and we will discuss them in the updated paper.\n\n---\n**Q4. Little intuitive background. Not obvious that $(S,Y) – X – \\hat{Y}$ refers to the Markov chain in Def. 2.**\n\nA4. Thank you for highlighting the issue and we will provide more background information in the revised paper. Regarding the Markov chain, it is a rather simple condition and holds if $\\hat{Y}$ is generated from $X$ (that is, the classifier only uses $X$ as input). This is always the case in practice – otherwise the classifier would be rather trivial (i.e., it would use $Y$ to predict itself). Also, observe that $S$ can be incorporated as a feature of $X$, so there is no loss of generality in this assumption. \n\n---\n**Q5. Hard to see intuitively why FairFront works e.g., why is the markov chain $(S,Y) – X – \\hat{Y}$? How does it filter out valid classifiers?**\n\nA5. Here is a short summary about how $FairFront$ works:\n\nFirst, computing $FairFront$ directly is intractable as it requires optimizing over a large, or even infinite-dimensional function space. To circumvent this issue, we write $FairFront$ as a function of a transition matrix $P_{\\hat{Y}|S,Y}$ and use $\\mathcal{C}$ to denote the set of all $P_{\\hat{Y}|S,Y}$ that correspond to a feasible classifier. This is a much lower dimensional problem since it does not directly depend on the cardinality of the input features $X$. The markov chain $(S,Y) – X – \\hat{Y}$ eliminates the transition matrices that are not associated with a feasible classifier (please refer to Remark 2 in Appendix B.4 on page 17 for an illustrative example). By leveraging Blackwell’s results, we approximate the convex set $\\mathcal{C}$ via piecewise linear functions with coefficients $a_i$. Algorithm 1 outlines a method that alternatively tightens the approximation of $\\mathcal{C}$ and computes $FairFront$ under this approximation. \n\n---\n**Q6. From Lem. 1, it appears that the FairFront is only applicable to convex classifiers.**\n\nA6. We would like to clarify that FairFront characterizes the fundamental fairness-accuracy trade-offs among ALL types of classifiers, not just the convex ones. The function $\\phi$ in Lemma 1 is not a classifier but rather will be approximated by piecewise linear functions in Algorithm 1 for characterizing $\\mathcal{C}$ in Definition 2.\n\n---\n**Q7. Epistemic and aleatoric discrimination and the corresponding uncertainty counterparts.**\n\nA7. Please refer to our response to your Q1 and Q2."}]

Author rebuttal:

Meta-review: This paper draws on the decomposition of uncertainty unto aleatoric and epistemic, to make a similar decomposition for algorithmic discrimination, and derive bounds on the Pareto frontier to provide lower bounds for the aleatoric discrimination. This relies on classical mathematical results by Blackwell, whose introduction to algorithmic fairness is novel and could lead to further new develowments.

The paper has received the reviewer scores 8, 4, 7, 6, 4, and the reviewers generally emphasize the same strengths in the paper. Of the accepts, two are quite enthusiastic about the paper, in particular highlighting its originality. Of the rejects, one would have liked to see more elaborate experiments on more complicated data, whereas the other finds that the use of the words "aleatoric" and "epistemic" differ from the way they are used in uncertainty modelling.

As the paper's main contributions are in the modelling and theoretical results, the lack of experiments on image or large language models is less of an an issue. While the authors are encouraged to consider whether wording could be in closer analogy with uncertainty modelling, this is not detrimental to what is otherwise a very strong paper.

The authors should include their promised updates to the final paper, and consider the reviews carefully and use them to further improve the clarity and accessibility of the paper.
Decision: Accept (spotlight)