FaiREE: fair classification with finite-sample and distribution-free guarantee
Authors: Puheng Li
James Zou
Linjun Zhang
Venue: ICLR 2023 poster (2023)
Keywords: algorithmic fairness
distribution-free
finite-sample
classification

Abstract: Algorithmic fairness plays an increasingly critical role in machine learning research. Several group fairness notions and algorithms have been proposed. However, the fairness guarantee of existing fair classification methods mainly depend on specific data distributional assumptions, often requiring large sample sizes, and fairness could be violated when there is a modest number of samples, which is often the case in practice. In this paper, we propose FaiREE, a fair classification algorithm which can satisfy group fairness constraints with finite-sample and distribution-free theoretical guarantees. FaiREE can be adapted to satisfying various group fairness notions (e.g., Equality of Opportunity, Equalized Odds, Demographic Parity, etc.) and achieve the optimal accuracy. These theoretical guarantees are further supported by experiments on both synthetic and real data. FaiREE is shown to have favorable performance over state-of-the-art algorithms.

Published as a conference paper at ICLR 2023
FAIREE: FAIR CLASSIFICATION WITH FINITE-SAMPLE AND DISTRIBUTION- FREE GUARANTEE
Puheng Li
James Zou
Linjun Zhang
Peking University
Stanford University
Rutgers University
1phleo@pku.
hwwppkkueede...om edu. en
james 8 taanforrrd edu
linjun zhangerutgers..dd
ABSTRACT
Algorithmic fairness plays an increasingly critical role in machine learning re- search. Several group fairness notions and algorithms have been proposed. How- ever, the faimess guarantee of existing fair classification methods mainly depends on specific data distributional assumptions, often requiring large sample sizes, and faimeess could be violated when there is modest number of samples, which is often the case practice. this paper, we propose FaiREE, a fair classifica- tion algorithm that can satisfy group fairness constraints with finite-sample and distribution- free theoretical guarantees. FaiREE can be adapted to satisfy various group faimess notions (e.g., Equality of Opportunity, Equalized Odds, Demo- graphic Parity, etc.) and achieve the optimal accuracy. These theoretical guaran- tees are further supported by experiments both synthetic and real data. FaiREE is shown to have favorable performance over state-of-the-ar algorithms.
INTRODUCTION
As machine learning algorithms have been increasingly used in consequential domains such as college admission Chouldechova & Roth (2018), loan application Ma et al. (2018), and disease diagnosis Fatima et al. (2017), there are emerging concerns about the algorithmic fairness re- cent years. When standard machine learning algorithms provided by humans, the outputs are sometimes found to be biased towards certain sensitive at- tribute that we want protect (race, gender, etc). To quantify the fairness in machine learn- ing algorithms. many fairness notions have been proposed, including the individual fairness no- tion [Begga et al. (2018), group fairness notions such as Demographic Parity, Equality of Op- portunity, Predictive Parity, and Equalized Odds (Dieterich et al. 2016) Hardt et al. 2016 Ga- jane Pechenizkiyl [017]] Verma & Rubin 2018). and multi-group group fairness notions including multi-calibration Héberr-JJhnson et al. (2018) and multi-accuracy Kim et al. (2019). Based on these fairness notions or constraints, corresponding algorithms were designed to help satisfy the fairness constraints (Hardt et al. 2016 Pleiss et al. 2017: Zafar et al. 2017b Krishnaswamy
directly applied to the biased data
ct al. 2021; Valera et al. 2018 Chzhen et al. 2019
Zeng et al. 2022
Thomas et al. 2019).
Among these fairness algorithms, post- processing is popular type of algo- rithm which modifies the output of the model satisfy fairness constraints. How-
0.99
0.25
0.25
50.30
ever, recent post-processing algorithms are found lack the ability realize accu- racy-fairness trade-off and perform poorly when the sample size is limited (Hardt et al.) 2016; Pleiss et al. 2017). In ad- dition, since most fairness constraints are non-convex, some papers propose con- vex ieaixaatiobbaseee methods Zafar et al.) (2017b); Krishnaswamy et al. (022)) This type algorithms generally do not have the theoretical guarantee of how the output satisfies the exact original faimess constraint. Another
500
037
332
6314
033
6116
0.537 0545 0.55 WESS OEE 01S dee
Figure 1: Comparison FairBayes and FaiREE on the syn- thetic data with sample size = 1000. See Table D for detailed numerical results. Left: DEOO v.s. Right: DEOO v.s. Test accuracy. Here, DEO0 is the degree of violation fairness constraint Equality of Opportunity and a the pre- specified desired level to upper bound DE00 for both meth- ads. See Eq. (T) in Section 2 for more detailed definition.

---

Published as a conference paper at ICLR 2023
line of research considers recalibrating the Bayes classifier by a group-dependent threshold (Valera et al. 2018 Chzhen et al. 2019 Zeng et al. 2022). However, their results require either some distributional assumptions infinite sample size, which is hard to verify/satisfy in practice.
In this paper, we propose a post-proesssing algorithm FaiREE that provably achieves group fairness guarantees with only finite-sample and free of distributional assumptions (this property is also called "distribution-fee free" in the literature (Maritz) 1995 Clarke 2007] Györfi et al. (002)). To the best of our knowledge, this is the first algorithm in fair classification with finite-sample and distribution- free guarantee. A brief pipeline of FaiREE is to first score the dataset with the given classifier, and select candidate set based on these scores which can fit the fairness constraint with a theoretical guarantee. As there are possibly multiple classifiers that can satisfy this constraint, we further de- velop a distribution-free estimate of the test mis-classification error, resulting in an algorithm that produces the optimal mis-classification error given the faimesss constraints. As a motivating exam- ple, (shows that applying state-of-the-
FairBayes method in [Zeng et al.) (2022) on a dataset with 1000 samples results in substantial fairness violation on the test data and incorrect behavior of fairness- accuuacy trade-off due to lack of fairness generalization. Our proposed FaiREE improved fairness generalization in these finite sample settings.
Additional Related Works. The fairness algorithms in the literature can be roughly categorized
into three types: 1). Pre-processing algorithms that learn a fair representation improve fairness
(Zemel et al. [013 Louizos L et al. (2015] Lum [um]2016]
| Adder et al. 2018 Calmon et al. 2017 Gordal-
iza al. Madrass et 2018 Kilbertus et al. 20200) 2). In-processing algorithms that optimize
during training time (Calders et al.) 20099; Woodworth et al.
2017 Zafar et al. 2017b Agarwal et al. | Celis al. 2019 3). Post- processinn algorithms
al. 2018 Russell al. 2017:
that try to modify the output of the original method to fit faimess constraints (Kamiran et al.
2012
Feldman 2015; Hardt et al. 2016: Fish et al. 2016 Pleiss et al. 2017 Corbett-Daviee et
2017
Menon & Williamson 2018
Hébert-Johnson et al. 2018 Kim et al. 2019 Deng et al. 2023).
The design of post-processing algorithms with distribution-fie free and finite-sample guarantees gains much attention recently due to its flexibility in practice Shafer & Vovk
et al.] (2019), as it can be applied to any given algorithm (eg. a black-box neural network), and achieve desired theoretical guarantee with almost no assumption. One of the research areas that satisfies this property is conformal prediction (Shafer & Vovk 2008) Lei et al.] 2018 Romano et al. (019) whose aim is to construct prediction intervals that cover future response with high probability. In this paper, we extend this line of research beyond prediction intervals, by designing classification algorithms that satisfy certain group fairness with distribution-free and finite-sample guarantees.
Paper Organization. Section[]provinn provides the general pipeline of FaiREE. In Section 4 we further extend the results to other fairness notions. Finally, Section 5 conducts experiments on both synthetic and real data and compares with several of-rt- algorithms to show that FaiREE has desirable performance
the definitions and notations we use in the paper. Section 3
2 PRELIMINARY
In this paper, we consider two types of features in classification: the standard feature E X, and the sensitive attribute, which we want the output to be fair on, is denoted as A E A = {0, 1). For the simplicity of presentation, we consider the binary classification problem with labels in y = {0. 1). We note that our analysis can be similarly extended to the multi-class and mulli-attribuu Under the binary classification setting, we use the score-hased classifier that outputs a prediction
setting.
γ y (xx a) E {0, 1} based on a score function f(x, a) E [0, 1] that depends on X and A:
Definition 1. (Score-based classifier) A score-based classifier is indication function Ý
o(z, = 1 [f (z.00) a) > c} for a measurable score function f : X x {0.1) + [0,1] and some
threshold c > 0.
To address the algorithmic fairness problem, several group fairness notions have been developed in the literature. In the following, introduce two of the popular notions, Equality of Opportunity and Equalized Odds. We will discuss other fairness notions in Section A.8 of the Appendix.
Equality of Opportunity requires comparable true positive rates across different protected groups
Code is available at httttpps//ggghhhb...m/////..l.pp
2

---

Published as a conference paper at ICLR 2023
Definition 2. (Equality of Opportunity (Hardt et al. 2016)) A classifier satisfies Equality of Oppor- funity if it satisfies the same true positive rate among protected groups: Px A=LY==1= 1)
PxIA-oy=-(Y- =).
Equalized Odds is an extension of Equality of Opportunity, requiring both false positive rate and true positive rate are similar across different attributes.
Definition 3. (Equalized Odds ([ard et al. 2 classifier satisfies Equalized Odds if satisfies the following equality: TP P'IA=ILY=I(Y = (X 1) and XX|A=1Y==OPP = Px|A=0,y=o(P=000
Sometimes is too strict to require the classifier to satisfy Equality of Opportunity or Equalized Odds exactly, which may sacrifice a lot of accuracy (as very simple example is [(z, a) = 1). In practice, to strike a balance between fairness and accuracy, it makes sense to relax the equality above to an inequality with small error bound. We use the difference with respect to Equality of Opportunity, denoted by D DEOO, to measure the disparate impact:
DEOO =FxjA=1,Y=10* 1) P (Y
For a classifier o following (Zeng et al., 2022 Cho et al., 2020 (EOO S a denotes an a-tolerance fairness constraint that controls the difference between the true positive rates below
Similarly, we define the following difference with Equalized Odds. Since Equalized Odds, the difference is a two-dimensional vector:
DEO (PxjA=L,Y= -x)) (f 1), PX -1)--==ooo1i1--Paaaa-----a- - 1)).
For notational simplicity, we use the notation N for the element- comparison between vectors, that is, DEO I (2) if and only if TP
Xx|A= P
1) -x
S on and
Px Fx|A-1y- = 1) P 1) a2
Additional Notation. We denote the proportion of group a by Pa := IP(A = a) for a E f0, 1}: the proportion of group Y conditioned A for Py,a P(Y = group Y conditioned on A and X for na (z) == IP(Y = A= a, = .). Also, we denote by (x) and (xy respectively the distribution function of X and the distribution function of X conditioned on A and Y. The score function of standard Bayes-optimal classifier without fairness constraint defined as 6" (xxx,) a)
a): the proportion of
Lff a) 1/2]. where f E arg mig, [IP(Y * ax) > 1/2])]- We denote U(A) as the 4thh ordered value of sequence v in non-decreasing order. For set T. we denote sorl(T) as a function that returns in non-decreasing order. For a number R. use [a] to denote the ceiling function that maps the least integer greater than or equal to a. For positive integer n, we use [n] to denote the set 21,2...., n..
FAIREE: A FINITE SAMPLE BASED ALGORITHM
In this section, we propose FaiREE, a general post post-processing algorithm that produces Fair clas- sifier in a sinite-sample and distribution fREE manner, and can be applied to wide range of group fairness notions. We will illustrate its use in Equality of Opportunity an example in this section, and discuss more applications in later sections.
3.1 THE GENERAL PIPELINE OF FAIREE
is the set of features associated with label Y = {0, 1} and protected attribute A E [0,1) We denote the size of 5v.e by v. Throughout the paper, we assume that x; 2. i {l..... nB.a are independently and identically distributed given Y = y, A We define n.0 + + +
Suppose we have dataset S 50.0 U 50.1 $1.0 U 51.1, where $9.4 = {a.taa , 9-a
1.1 to be the total number of samples. Our goal is to post-process any given classifier to make satisfy certain group fairness constraints.
FaiREE is a post-processing algorithm that can transform any pre-trained classification function score f in order to satisfy fairness constraints. In particular, FaiREE consists of three main steps,
3

---

Published as a conference paper at ICLR 2023
scoring, candidate construction, and candidate selection. See Figure 2 for illustration. We would like to note that the procedure that first chooses a candidate set tuning parameters and then selects the best one has been commonly used in machine learning, such in Seldonian algorithm framework to control safety and fairness (Thomas et al. (2019); Giguere et al.
(2022); Weber et al.
(2022), the Learn then Test framework for risk control Angelopoulos et al. 2021) and in high- dimensional statistics Wang et al. (2022).
OQ
0
+
Step 1:
Step 2:
Step 3:
Data Preparation
Scoring
Candidate Set Construction
Candidate Selection
Figure A concrete pipeline of FaiREE Equality of Opportunity. Edges in Step represent selected candidate pair and the red edge in Step 3 represents the final optimal candidate selected from all the edges. Each pair represents two different thresholds of a single classifier.
Step 1: Scoring. FaiREE takes input as 1). given fairness guarantee G, such as Equality of Opportunity or Equalized Odds; 2). an error bound which controls the violation with respect to our given fairness notion; 3). a small tolerance level 5, which makes sure our final classifier satisfies our requirement with probability at least 1 5; 4). dataset S.
For scoring, we first apply the given classifier f to S and denote the outcome t. := fa as scores for each sample. These scores are then sorted within each subset in non-decreasing order respectively and obtain Ty.a [([])...... ....,............ 1y-a
(n.
Step 2: Candidate Set Construction. We first present a key observation for this step, which holds for many group fairness notions such as Equality of Opportunity, Equalized Odds (see details of more fairness notions in S..tion[3.2
Any classifier can fit the fairness constraint with high probability by setting the decision threshold appropriately, regardless of the data distribution.
The insight of this observation comes from recent literature post-processing algorithms and Neyman-Pearson classification algorithm (Fish et al.) 2016 Corbett-Davies et al.) 2017 Valera et al., 2018 [Meon & Williamson| 2018; Tong al. 20188) Chzhen |l.1 Under Equality of Op- portunity, this observation is formalized in Proposition | We also establish similar results under other fairness notions beyond Equality of Opportumity
Section 33.2] From this observation we can build an algorithm to calculate the probability that a classifier with a certain threshold will satisfy the fairness constraint: (J' S a where DJf is generic notation to denote the violation rate of under some fairness notion G. Then choose the classifiers with the probability (fi > a) < as our candidate set C. This candidate set consists of a set of threshold values, with potentially different thresholds for different subpopulations.
Step 3: Candidate Selection. Furthermore, as there might be multiple classifiers that satisfy given fairness constraints, aim choose a classifier with small classsaassiiiattoo error. To do this, FaiREE estimates the mis-classification error err(f) of the classifier f. and chooses the one with the smallest error among the candidate constructed in the second step.
In the rest part of the section, as an example, we consider Equality of Opportunity as our target group faimess constraint and provide algorithm in detail.
3.2 APPLICATION TO EQUALITY OPPORTUNITY
In this section, we apply FaiREE to the fairness notion Equality of Opportunity. The following two subsections explain the steps Candidate Set Construction and Candidate Selection in detail.
4

---

Published as a conference paper at ICLR 2023
3.2.1 CANDIDATE SET CONSTRUCTION
We first formalize our observation in the following proposition. Using the property of order statis- tics, the following proposition states that it is sufficient to choose the threshold of the score-based classifier from the sorted scores to control the faimess violation in a distribution and finite- sample manner. Here, kl.0 is the index from which we select the threshold in T'
Proposition 1. Consider kL.a E {I,.... n.11) for a E {0, 1], and the score-based classifier alia
a(x,a)= al((x,)) > ((Wn))), Let g) BE (Qul- - a) -QQ11-a
a))="(-? " with Q1.a a Beta(k, nl a k + 1), then we have:
P(DEO0(0) > a) S 91(h"), 1,6"",,10 1) + gkkk",
Additionally, if (kt.a) is a continuous random variable, the inequality above becomes tight equality.
Here, 91 function constructed using the property of order statistics so that gi (k:1.1, 1) and gi (k1.0, 0) upper bound P(DEOO()) a) and F(DEOO()) < -a) respectively. We note that 9I can be efficiently compute using Monte Carlo simulations. In our experiments, we approx- imate d1 by randomly sampling from the Beta distribution for 1000 times and achieve satisfactory approximation. This proposition ensures that the DEOO of given classifier can be controlled with high probability if we choose appropriate threshold value when prosesrocsssigg.
Based on the above proposition, we then build our classifiers for an arbitrarily given score function as below. We define I(A:'.0, kI.1)= gi (k.1.1, 1) + 91 (k-1., 0)- Recall that the error tolerance a, and is the tolerance level. Our candidate set is then constructed as K = [(k1,,, k...) L(k10, .2.1) < 8).
Before we proceed to the theoretical guarantee for this candidate set, we introduce a bit more notation. Let us denote the size of the candidate set K by M, and the elements in the set K by (k) k=-1),,... ....., (k1 k11). Additionally, we let å.(x, a) (ff(x,a) (a i ... M.
Lia B. for
To ensure that there exists at least one valid classifier (i.e. M 2 1), we should have E[(Qu0- a)" + + E[(Qu.1 a))* < 8, which requires necessary and sufficient lower bound requirement on the sample size, as formulated the following proposition:
Theorem 1. If min(n"", (
log $ log(1 (all-a) 1, for each (l...., M3 in the candidate set, we
have (EO0 < a with probability 6.
As there are at most n 1'''1 elements in the candidate set, the size of K, M, can be as large as On?)). To further reduce the computational complexity, in the following part, we provide a method to shrink the candidate set.
Our construction is inspired by the following lemma, which gives the analytical form of the fair Bayes-optimal classifier under the Equality of Opportunity constraint. This Bayes-optimal classifier is defined as &5 = arg min ( a) Y).
Lemma 1 (Adapted from Theorem E.4 in Zeng et al. (2022)) The fair Bayes-optimal classifier under Equality of Opportunity can be explicitly written 0% (x, 11f (x, (.)). then P1Pr.11
bi 2P.Py.1 (1/0 2)-Pa
Note that in practice, the input classifier f can be the classifier trained by classification algorithm on the training set, which means close to f". Thus from this observation, we can adopt a new way of building a much smaller candidate set. Note that our original candidate set is defined
as K {(K1.0 k1.1) L(k 1111) < 8}
{(k] 1.0
A 1.l
)..).....
1.0 k k }}. Now, for every )...., (k
PIPY 1 S S n.00 from Lemma we denote in (k) arg min (a) 26. (1/C 2) where
P. 7.
n 4.
and Py.a t.. We then build our candidate set as below:
ni.
K' 11.1.0 un (K1))) I(k un (x:110)) 8).
(2)
5

---

Published as a conference paper at ICLR 2023
This candidate set K' has cardinality most Since next step, Candidate Selection, has computational complexity that is linear in the size of the candidate set, using the new set K' would help us reduce the computational complexity from O(n²) O(n).
3.2.2 CANDIDATE SELECTION
In this subsection, we explain in detail how choose the classifier with the smallest mis- classification enrrr from the candidate constructed in the last step. For given pair (x, ky)") in the candidate set of index (i [M]. we need know the rank of t :1.0 and 41,1 (Ag..) in the sorted set T and T respectively in order to compute the test error where we need to consider both = and 1. Specifically, we find the 60.0 such that goa (1
(k!-2)
I $1.0 (2) <
10.0 (10:+11
for a {0, 1}.
To estimate the test mis-classification error of (1 a) 1 (f(s, a)
12. ((tta)) we divide the error
into four terms by different values of y and a. We then estimate each part using the property of order statistics respectively, and obtain the following proposition:
Proposition 2. Suppose the density functions of S under
= a, = are contimuous. Let
k..0 n²..
ki.1 n² atl+i n + 7.00+ -k. no.00 n ko nd1 ffo = 1,2, M. Then,
& n
40.0+1
nol
there exist two constants 01, C2 0 such that ((, a),,a) *Y) é s / min(n n..)) with
probability larger than - exp( 10--mnnn.. m n).
The above proposition enables us to efficiently estimate the test error of the M classifiers O. de- fined above. from which we can choose classifier with the lowest test error ø. The algorithm is In the following, we provide the theory showing that the output of summarized in Algorithm [
Algorithm 1: FaiREE for Equality of Opportunity
Input: Training data S 50.0 U 5 U.$..0 USL); the error bound a; the tolerance level ò; given pre-trained classifier f Tv.a {f( ).....
}}
((y..)) (1)..... ................................ tt//a
=son(Tw..)
Define 91 (k, a) as in Proposition
and let L(k2.0 k2.1) 91 (k: 91 (k2.0 10.0000 .0)
Build candidate set K' as in Eq.
and write K"
= [kk 1,
ki )...., (
Find k. 0.1, to0 I $1.0 (a.2-0) "1000)
0,0
0,1
0,1
(k 0 1)" (
S (1:21)) ((6221)
1x arg min(é:] (é; is defined in Proposition iE[M']
Output: ò(z,a) a) (f a) (
Algorithm T is approaching the optimal clsscaassification error under Equality of Opportunity. The following theorem states that the final output of FaiREE has both controlled DEOO, and achieved almost minimum clssciassiiioatoon error when the input classifier is properly chosen.
Theorem 2. Given any a' a. Set co/ M for some co > O, where M is the candidate set size. log _
Suppose min (n nli1) 2 logil aa) 1. & is the output of FaiREE, then:
(I). [DE < a with probability 1 co-
(2). Suppose the density functions of f and f under A a, = are continuous. For any 8',eu > O, there exist 0 < c
and e₁ > such that when the input classi- fier f(x, satisfies ||f fl1o I co and the constructed candidate set is K', have
P(Ō((z,) Y)- (2,)) # Y) S 2F(+, 8' with probability larger than minminn"" 1.0 n
ni1), (F()(()) is defined in Lemma in the appendix.)
Theorem 2 ensures that classifier will approximate fair Bayes-optimal classifier if the input classifier is close to f". Here, < a any positive constant, which we adopt to promise that our candidate set is not empty.

---

Published as a conference paper at ICLR 2023
Remark: We remark that FaiREE requires assumption data distribution except for minimum sample size. It has the advantage over existing literature which generally imposes different assump- tions to data distribution. For example, Chzhen et al. (2019) assumes ny(2, a) must surpass the level on a set of non-zero measure. Valera et al. (018)) assumes that the shifting threshold of the clas-
sifier follows the beta distribution. Also, Zeng et (2022)'s 's result only holds for population-level, and the sinite-sample version is not studied.
4 APPLICATION TO MORE FAIRNESS NOTIONS
4.1 EQUALIZED ODDS
In this section, we apply our algorithm the fairesss notion Equalized Odds, which has two fairness constraints simultancously. To ensure the two constraints, the algorithm of equalized odds should be different from Algorithm| [ violation to fairness constraint in the step Candidate Set Construction. Thus we add function 9u that deals with data with protected attribute A in the last section.
We should consider all Sv.a instead of just 51.a when estimating the
perfect our algorithm together with ø1 defined
Similar to Proposition 1 the following proposition assures that choosing an appropriate threshold during post-processing enables the high probability control of given classifier's s DEO.
Proposition 3. Given k1.0, k1.11 satisfying ka.a E fl...., (a = 0, 1). Define o(I, a) = (Quilo a1 - (Qu.1-a - a))) with
a((xaa)) >
laa (g gy a) = E
E j=k
Qua ~ Betaakk + 1 y. n.a -k k + v). then have:
P(IDEO(0) 1 (a, a)) 2 1 - 91 [
1 1)
1,000,00000 0) (o ,1 go0kko, 0). (1
Similar to Proposition Oo and 91 jointly control the probability of Φ violating the DEO constraint.
Algorithm 2: FaiREE for Equalized Odds
Input: Training data S 5 U 50. U 5 U Sl, the error bound o; the tolerance level ó; given pre-trained classifier f Tv.a (x .....,
[x.... (xx%,.)) (1): (L)):...,, 13.0
(ny.))) =son(Tv..))
Define (k; a) and 9i (k:, a) as in Proposition 3 (K ,.1.1. 91 (k-11 1) 9n (k ,), and
Lo(k0,0 k0.1) (ko.11 1) + (o..000 0).
For every k1.00 k1.,. there exists 10.0 k0.1 such that ,0,0
((.0.0)
S
2.0
(12.0)
(10.0+1))
4.00
f0.1
(10.1)) S
+1.1
(k1.1) < t0.1 (10.1+1))
Build the candidate set as
((k) ) ..... (K kbd)) )) Compute é, as in Proposition 2) and let i, = arg (
K =[(11,00 R.111 T, 1k1.0 1 + [k000 RO.11) 5)
aE[M]
Output: ò(z, = 1(f
Proposition 3 yields the following proposition on the DEO of classifiers in the candidate set.
Theorem 3. If min(n"" n n,2,,,22.1) 2
I, then for each E (I...., M}, we have log(1 aj
log
[DEO( = (a, with probability 1 -
The theoretical analysis of test error is similar the algorithm for Equality of Opportunity.
Theorem 4. Given a' < a. Set 8 = co/M for some Co > O, where M is the candidate set size. Suppose min(n n0.1, n 1.0 1.11 2 [
log log(1-a) 1- & is the final output of FaiREE, then:
(1). (DEO()) 3 (a, a) with probability 1 co-
(2). Suppose the density functions of f under A = a.Y = 1 are continuous. We denote
d' = arg oo, P(O(z, a) # Y). For any 8' en > 0, there exist e
7

---

Published as a conference paper at ICLR 2023
1 and e1 > 0 such that when the input classifier f satisfies ((z,a)-f(zz,d)) I co, have P (( a) * Y) P( ar (2, a) + Y) S (F)+ 8' with probability larger than Cj m (n 1.0 ni" 1 no m Bil 3. (F((4) is defined in Lemma 6 in the appendix.)
4.2 ON COMPARING DIFFERENT FAIRNESS CONSTRAINTS
In this subsection, we further extend our algorithms to more fairness notions. The detailed technical results and derivations are deferred to Section A.8 in the appendix. Specifically, compare the sample size requirement to make any given score function f to achieve certain fairness constraint. We note that our algorithm is almost assumption-fres except for the i.i.d. assumption and neces- sary and sufficient condition of the sample size. Therefore, we make a chart below to recommend different fairness notions used in practice when the sample sizes are limited. We summarize our results in the following table:
Table I: Sample complexity requirements for FaiREF to achieve different fairness constraints. We consider the following fairness notions: DP (Demographic Parity), EOO (Equality of Opportunity), EO (Equalized Odds), PE (Predictive Equality), EA (Equalized Accuracy), and n² n n2...
DP
BOO
PE
EO
EA
n
Iog (og(1-a)
n
log(1-00
Iog $
log. 4 log ())
na.
log(l 00
Ing
From this table, we find that Demographic Parity requires the least sample size, Equality of Opportu- nity and Predictive Equality need lightly larger sample size, and Equalized Odds is the notion that requires the largest sample size among the first four faimness notions. The sample size requirement for Equalized Accuracy is similar to that of Equalized Odds, but does not have a strict dominance.
EXPERIMENTS
In this section, we conduct experiments to test and understand the effectiveness of FaiREE, For both synthetic data and real data analysis, we compare FaiREE with the following representative meth- ods for fair classification:
Ceject-Option-Clane Classification (ROC) method in Kamiran et al.] (2012) Eqodds- Pottroesss (Eq) method in Hardt et al. (2016). Calibrated
Poouldd-Pottpooessingg (C- Eq) method in Pleiss al. (2017) and FairBayes method in Zeng et al. (2022). first three base- lines designed cope with Equalized Odds and the last one is for Equality of Opportunity.
5.1 SYNTHETIC DATA
To show the distribution-fia and imite-sample guarantee of FaiREE, we generate the synthetic data from mixed distributions. Real world data are generally heavy-tailed [Resnick] (1997)) Thus, we consider the following models with various heavy-tailed distributions for generating synthetic data:
Model
We generate the protected attribute and label with probability Pl = P(A = 1) 0.7, Po PAA = 0) 0.3, Py.1 = P(Y = A = 1) 0.7 and Py.0 IPY = A = 0) = 0.4 for E {0, 10. The dimension of features set to 60, and we generate
features with 0.0 i.idd
Fij
1(3), where t(k) denotes the I-distribution with degree of freedom 1.0 s.i.d.
1.1 s.dd. (H, 1), where (0, and the scale ~ parameter is fixed to be 1, for 1, 1,,,,.,,60.
k. 0.1 i.i.d. ~ X2. 2ú5 ~
X3 and x.
Model 2. We generate the protected attribute A and label Y with the probability, location param- eter and scale parameter the same as Model 1. The dimension of features is set to
80, and we generate features with 0.0 s.dd t(4). ii
0.1 sidd X2 x
i.idd. x2 and
iid. Laplace(J4, 1), for 1,2, 80. Fij
For each model, we generate 1000 i.i.d. samples, and the experimental results are summarized in Tables[ann and B
From these two tables, we find that our proposed FaiREE, when applied to different fairness notions Equality of Opportunity and Equality of Opportunity, is able to control the required fairness vio-
8

---

Published as a conference paper at ICLR 2023
Table 2: Experimental studies under Model 1. Here DEOO| denotes the sample average of the absolute value of DEOO defined in Eq. (.. and |DEOO)ss 990 denotes the sample upper 95% quantile. [DPE] and IDPElss are defined similarly for DPF defined in Eq. 13) ACC is the sample average of accuracy. We use "/" in the DPE line because FairBayes and FaiREF--OOO are not designed to control DPF.
Eq
C-Bq
ROC
FairBayes
FaiREE-EOO
FaiREE-EO
/
/
0.08
0.12
0.16
0.08
0.12
0.16
0.08
0.12
0.16
DEOO
0,061
0.132
0.255
0.117
0.149
0.170
0.028
0.046
0.063
0.025
0.031
0.042
DEOO 95
0.146
0.307
0.500
0.265
0.297
0.316
0.073
0.115
0.157
0.079
0.108
0.133
[DPE
0,051
0.029
0.511
0.039
0.042
0.045
DPE uc
0.110
0.091
0.850
/
/
0.075
0.084
0.106
ACC
0.472
0.606
0.637
0.663
0.656
0.646
0.621
0.657
0.669
0.552
0.562
0.615
Table 3: Experimental studies under Model 2, with the same notation as Table
2
Eq C-Eq
ROC
FairBayes
FaiREE-BOO
FaiREE-EO
/
/
0.08
0.12
0.16
0.08
0.12
0.16
0.08
0.12
0.16
DEOO
0.063
0.105
0.237
0.251
0.320
0.324
0.027
0.047
0.073
0.028
0.035
0.047
DEOO 99
0.080
0.137
0.502
0.676
0.742
0.765
0.075
0.112
0.153
0.077
0.114
0.143
DDE
0.043
0.107
0.209
1
/
0.041
0.044
0.056
IDPE 9s
0.066
0.144
0.443
0.071
0.090
0.127
ACC
0.380 0.600
0.616
0.606
0.598
0.589
0.595
0.627
0.639
0.575
0.589
0.606
lation respectively with high probability, while all the other methods cannot. In addition, although satisfying stronger constraints, the clsscaassiiication error FaiREE comparable to, and sometimes better than the state-of-the-as methods.
5.2 REAL DATA ANALYSIS
In this section, we apply FaiREE to a real data set, Adult Census dataset (Dua et al.) 2017). whose task is predict whether person's income is greater than $50,000. The protected attribute is gender, and the sample size is 45,222, including 32561 training samples and 12661 test samples. To facilitate the numerical study, we randomly split data into training set, calibration set and test set at each repetition and repeat for 500 times. FaiREE is compared the existing methods described in the last subsection. Again, as shown in Table the proposed FaiREE method controls the fairness constraints at the desired level, and achieve small missclassification error. More implementation details and experiments on other benchmark datasets are presented in A.9
Table 4: Result of different methods Adult Census dataset
Eq
C-Eq
ROC
FairBayes
FaiREE-EOO
FaiREE-EO
Q
/
0.07
0.1
0.14
0.07
0.1
0.14
0.07
0.1
0.14
DEOO
0.043
0.087
0.031
0.107
0.101
0.104
0.034
0.039
0.066
0.002
0.039
0.067
DEOO 95
0.112
0.154
0.097
0.140
0.153
0.153
0.065
0.090
0.124
0.008
0.094
0.125
DPE
0.027
0.048
0.044
/
/
/
/
0.030
0.066
0.074
DPE 95
0.058
0.105
0.117
/
/
/
0.056
0.078
0.086
ACC
0.815
0.823
0.691
0.847
0.847
0.847
0.845
0.846
0.847
0.512
0.845
0.846
6 CONCLUSION AND DISCUSSION
In this paper, we propose FaiREE, post-proee post-processing algorithm for fair classification with theoretical guarantees in a fimite-sample and distribution-fiet manner. FaiREE can be applied to a wide range of group fairness notions and is shown to achieve small miscclassification error while satisfying the fairness constraints. Numerical studies on both synthetic and real data show the practical value of FaiREE in achieving superior chimess-accuragy trade-off than the state-of oof-the-art methods. One in- teresting direction of future work is to extend the FaiREE techniques to multi multi-group group fairness notions such multi-calibration (Héhert-Johnson al. 2018) and multi-accuracy Kim et al. 2019).
9

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
The research of Linjun Zhang is partially supported by NSF DMS-2015378. The research of James Zou partially supported by funding from NSF CAREER and the Sloan Fellowship.
REFERENCES
Philip Adler, Casey Falk, Sorelle A Friedler, Tionney Nix, Gabriel Rybeck, Carlos Scheidegger, Brandon Smith, and Suresh Venkatasubramanian, Auditing black-box models for indirect influ- ence. Knowledge and Information Systems, 54(1):95-11 -222 2018.
Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna Wallach. A re- ductions approach fair classification. In International Conference on Machine Learning. pp- 60-69. PMLR, 2018.
Anastasios N Angelopoulos, Stephen Bates, Emmanuel J Candès, Michael Jordan, and Lihua Lei. Learn then test: Calibrating predictive algorithms to achieve risk control. arXiv preprint arXiv:21 2021.
Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias: across the country to predict future criminals. And it's biased against blacks. ProPublica, 23: 77-91, 2016.
There's software used
Asia Biega, Krishna P Gummadi, and Gerhard Weikum, Equity of attention: Amortizing individual fairness rankings. In The 41st international acm sigir conference on research & development in information retrieval, pp. 405-414, 2018.
Toon Calders, Faisal Kamiran, and Mykola Pechenizkiy. Building classifiers with independency constraints. In 2009 IEEE International Conference on Data Mining Workshops, pp. 13-18.
IEEE, 2009.
Flavio Calmon, Dennis Wei, Bhanukiran Vinzamuri, Karthikeyan Natesan Ramamurthy, and Kush R Varshney, Optimized pre-processing for discrimination prevention. Advances in neural informa- tion processing systems, 30, 2017.
I. Elisa Celis, Lingxiao Huang. Vijay Keswani, and Nisheeth K Vishnoi. Classification with fairness constraints: meta-algorithm with provable guarantees. In Proceedings of the conference on fairness, accountability, and transparency, pp. 319-328, 2019.
Jaewoong Cho, Gyeongjo Hwang, and Changho Suh. A fair classifier using kernel density estima- tion. Advances in Neural Information Processing Systems, 13:15088-15099, 2020.
Alexandra Chouldechova and Aaron Roth. The frontiers of faimess in machine learning. arXiv preprint arXiv:1810.0888 088100, 2018
Evgenii Chzhen, Christophe Denis. Mohamed Hebiri, Luca Oneto, and Massimiliano Pontil. Lever- aging labeled and unlabeled data for consistent fair binary classification. Advances in Neural Information Processing Systems, 32, 2019.
Kevin A Clarke. simple distribution-free test for nonnested model selection. Political Analysis, 15(3)3347363, 2007.
Sam Corbett-Davies Emma Pierson, Avi Feller, Sharad Goel, and Aziz. Huq. Algorithmic decision making and the cost of faimess. Proceedings of the 23rd acm sigkdd international conference on knowledge discovery and data mining, pp. 797-806, 2017.
Zhun Deng, Cynthia Dwork, and Linjun Zhang. Happymap: A generalized multicalibration method. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2023.
William Dieterich, Christina Mendoza, and Tim Brennan. Compas risk scales: Demonstrating ac- curacy equity and predictive parity. Northpointe Inc, 7(4), 2016.
10

---

Published as a conference paper at ICLR 2023
Dheeru Dua, Casey Graff, et al. Uci machine learning repository. 2017.
Meherwar Fatima, Maruf Pasha, et al. Survey of machine learning algorithms for disease diagnostic. Journal of Intelligent Learning Systems and Applications. 9(01):1, 2017.
Michael Feldman. Computational fairness: Preventing machine-learned discrimination. PhD thesis, 2015.
Benjamin Fish, Jeremy Kun, and Ádám D Lelkes. A confidence-based approach for balancing fairness and accuracy. In Proceedings of the 2016 SIAM international conference on data mining, pp. 144-152. SIAM, 2016.
Pratik Gajane and Mykola Pechenizkiy, On formalizing fairness in prediction with machine learning. arXiv preprint arXiv: 1710.03/84, 2017.
Stephen Giguere, Blossom Metevier, Bruno Castro da Silva, Yuriy Brun, Philip Thomas, and Scott Niekum. Fairness guarantees under demographic shift. In International Conference on Learning Representations, 2022.
Paula Gordaliza, Eustasio Del Barrio, Gamboa Fabrice, and Jean Mean-Michel Loubes. Obtaining fairness using optimal transport theory. In International Conference on Machine Learning, pp. 2357-2365. PMLR, 2019.
László Györfi, Michael Kohler, Adam Krzyzak, Harro Walk, et al. A distribution-free theory of nonparametric regression, volume 1. Springer, 2002.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29, 2016.
Ursula Héhert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum. Multicalibration: Cal- ibration for the computationall--deenffnaa masses. In International Conference Machine Learning, pp. 1939-1948. PMLR, 2018.
Faisal Kamiran and Toon Calders. Classifying without discriminating. In 2009 2nd international conference on computer, control and communication, pp. 1-6. IEEE, 2009.
Faisal Kamiran, Asim Karim, and Xiangliang Zhang. Decision theory for discrimination-as aware classification. In 2012 IEEE 12th International Conference Data Mining, pp. 924-929. IEEE, 2012.
Niki Kilbertus, Manuel Gomez Rodriguez, Bernhard Schölkopf, Krikamol Muandet, and Isabel Valera. Fair decisions despite imperfect predictions. In International Conference on Artificial Intelligence and Statistics, pp. 277-287. PMLR, 2020.
Michael P Kim, Amirata Ghorbani. and James Zou. Multiaccuracy: Black-box post-processing for fairness in classification. In Proceedings of the 2019 AAAI/ACM Conference on Al, Ethics, and Society, pp. 247-254, 2019.
Anilesh Krishnaswamy, Zhihao Jiang, Kangning Wang, Yu Cheng, and Kamesh Munagala. Fair for all: Best-effort fairness guarantees for classification. In International Conference on Artificial Intelligence and Statistics, pp. 3259-322 3267. PMLR, 2021.
Jing Lei, Max G' Gelll, Alessandro Rinaldo, Ryan J Tibshirani, and Larry Wasserman. Distribution- free predictive inference for regression. Journal of the American Statistical Association, 113 (523):1094-111 2018.
Christos Louizos. Kevin Swersky, Yujia Li. Max Welling, and Richard Zemel. The variational fair autoencoder. arXiv preprini 15Xiv:55/1.086 2015.
Kristian et al. Lum. A statistical framework for fair predictive algorithms. arXiv preprint arXiv: (aoo::610000000 2016.
11

---

Published as a conference paper at ICLR 2023
Xiaojun Ma, Jinglan Sha, Dehua Wang, Yuanbo Yu, Qian Yang, and Xueqi Niu. Study predic- tion of p2p network loan default based on the machine learning lightgbm and xgboost algorithms according to different high dimensional data cleaning. Electronic Commerce Research and Ap- plications, 31:24-39, 2018.
David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Learning adversarially fair and transferable representations. In International Conference on Machine Learning. pp. 3384-3393.
PMLR, 2018.
Johannes S Maritz. Distribution-free statistical methods, volume 17. CRC Press, 1995.
Aditya Krishna Menon and Robert C Williamson. The cost of faimess in binary classification. In Conference on Fairness, Accountability and Transparency, pp. 107-118. PMLR, 2018.
Geoff Pleiss, Manish Raghavan, Felix Wu, Jon Kleinberg, and Kilian Q Weinberger. On fairness and calibration. Advances neural information processing systems, 30, 2017.
Sidney I Resnick. Heavy tail modeling and teletraffic data: special invited paper. The Annals of Statistics, 25()):1805-186, 1997.
Yaniv Romano, Evan Patterson, and Emmanuel Candes. Conformalized quantile regression. Ad- vances in neural information processing systems, 32, 2019.
Chris Russell, Matt J Kusner, Joshua Loftus, and Ricardo Silva. When worlds collide: integrat- ing different counterfactual assumptions in fairness. Advances in neural information processing systems, 30, 2017.
Glenn Shafer and Vladimir Vovk. A tutorial conformal prediction. Journal of Machine Learning Research, 9(3), 2008
Philip S. Thomas, Bruno Castro da Silva, Andrew G. Barto, Stephen Giguere, Yuriy Brun, and Emma Brunskill. Preventing undesirable behavior of intelligent machines. Science, 366(6468): 999-1004, 2019.
Xin Tong, Yang Feng, and Jingyi Jessica Li. Neyman-pearse pearson classification algorithms and np receiver operating characteristics. Science advances, ((2)eeaa1655) 2018.
Isabel Valera, Adish Singla, and Manuel Gomez Rodriguez. Enhancing the accuracy and fairness of human decision making. Advances in Neural Information Processing Systems, 31, 2018.
Sahil Verma and Julia Rubin. Fairness definitions explained. In 2018 ieeelacm international work- shop on software fairness (fairware), pp. 1-7. IEEE, 2018.
Peng Wang, Min-Ge Xie, and Linjun Zhang. Finite-and large-sample inference for model and coefficients high-dimensional linear regression with repro samples. arXiv preprint 2rXhv:2209.09299, 2022.
Aline Weber, Blossom Metevier, Yuriy Brun, Philip Thomas, and Bruno Castro da Silva. Enforcing delayed-impace faimess guarantees. arXiv preprint arXiv:2208. /144, 2022.
Blake Woodworth, Suriya Gunasekar, Mesrob Ohannessian, and Nathan Srebro. Learning non- discriminatory predictors. Conference on Learning Theory, pp. 1920-1953. PMLR, 2017.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodrigue7, and Krishna P Gummadi. Fair- beyond disparate treatment & disparate impact: Learning classification without disparate mistreatment. In Proceedings of the 26th international conference on world wide web, pp. 1171- 1180, 2017a.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna Gummadi. Fair- ness constraints: Mechanisms for fair classification. In Artificial intelligence and statistics, pp- 962-970. PMLR, 2017b.
Rich Zemel, Yu WU, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representations. In International conference machine learning, pp. 325-333. PMLR, 2013.
12

---

Published as a conference paper at ICLR 2023
Xianli Zeng, Edgar Dobriban, and Guang Cheng. Bayes-optimal classifiers under group faimesss arXiv preprint arXiv:2202.09724, 2022.
Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adver- sarial learning. In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, pp. 335-340, 2018.
A APPENDIX
A.1 PROOF OF PROPOSITION II
Proof. The classifier is
1[[(x,0) > 20 / a=
(1f((x,1) > 111 a
we have:
(E00(O) = =
= [P(f(zz)) 0) > ((22,9) A = - 1(f(x,1)) ((..a) |A= 1,Y =)] 1)
= 11 1--1 (2 - ((.
= 1 - p1. - (1
Hence,
P(IDEO0(0) a) = P([ (12.) (1 p1. (1th,o)))) > a))
=P(FL (12 -P(FL)1(()).)))) - (l.0()))).))) > a) + (P(FL)(1)).)) (( -a)
A A
We then have
A P(F (1e..)) F1. (1().1)) > a)
P( ((FL0(())..) < (1222 (Bt.2) - a)
< EIP F1.0-1 (1)1))) (1))((((((()) - > 0} (
E(Plat least 2.0 of f are less than FL.0 1 (F (((k)1))
0) 0}| 1.1 (
Following this, obtain
1,0 Σ
A
B
Plexactly of the 1200 are less than FL.0 (1 (12. (12 >0} 11
(
j=k1.
n
1.
=
B
Pitlo
(110 -a)) (1- PI < F1.00 (F (F22 - -
1=
1f (F
a > 0} tfg..nt
1.0
1.0 ( a) (F2.1 (12211))tt..))) a))m (k1.a))
< E
(1l.)
Similarly, we have
1.1 B
n1111 (F" ((t..)))))))))) a) (F ((te.1))))))) -a))m²" - 12k
B
E
13

---

Published as a conference paper at ICLR 2023
Hence, we have
2000
(n
A+ B
S
Σ
(F ((b))))))))))))))))))))))))))) - a0 (00--(().11)) ((bb.)) - a))='a &(blag]
J=
==
(n!.1)
[ (F1.0 (bt11))) - aa) (F (F2.0
(1 (1(t).0)) - a))
21.0
(12.09)
1 k1.1
1.00
(Q) a1 (1-(1-')) -Q'"1 - -a))
<
j=k
(Q) - a1 - (Q'1: - -a))
jmkl.1
The last inequality holds because (l is stochastically dominated by Beta no
klla + 1).
If the is continuous random variable, the equality holds.
Now we complete the proof.
A.2 PROOF OF LEMMA
We first introduce the lemma (theorem E.4 Zeng et al. (002
Lemma 2. (Fair Bayes-oplimal Classifiers under Equality of Opportunity). Let E* DE00 (f*).
For any a >> O, fair Bayes-optimal classifiers fE. under the fairness constraint [DE00()) S a are given as follows:
Whhen E² S a. JE. f
When E a, suppose PXIA=LY=1 ([(x)=
PiPy,
0, then for all X and
2(PLYY
E A.
fE,(I,a)=1 [[(())> (
PoPY,a
2paPY,a + (1 2a)
where 1, is defined as
fg sup { t: t::Y
P1Py.1 - > PYIA=,,Y=1 (mo(X)
PoPy,0
E
(X)) >
2piPy.1 2p
+
2poPy:0 +
E
Now we come back to prove Proposition
Proof. From Lemma we have
PoPy.0 2popy:0 + t
(3)
PIPY,1
(4)
2p1Py,1
Combine Eq. B and together and we complete the proof.
A.3 PROOF OF PROPOSITION 2
We first provide lemma for the mis- mis-classification error of the classifier in the candidate set.
Lemma 3. (P( a) + Y) - I PoPy. + k1.3
A
9.00 E(R
PIPYY + 200
Poo1 - pY.o) +
n 0.1 -a...11
2.141 Pı (1 py.)]] ج
pot pr + 2(m.141)
p1(1-py1l
21x
14

---

Published as a conference paper at ICLR 2023
We also have the following lemma:
Lemma 4. ((..))))))) ~ Beta(ko0, 00.0 n0.000 - 1000 +1), ((b.()
~ Beta(ko1 no.1 -1.11 +1).
Proof of Lemma 4 Since F0.,, Fo. are the continuous cumulative distribution functions of the su and ss, we have (1000,, (1.(( UO, 1), thus ((..0()))))) is the 4u,0th order statistic of n iid samples from U and Fo, (f. (((o.))) is the k0,1 order statistic of n iid samples from (O, 1).
Thus, from the well known fact of the ordered statistics, we have (e ~ Beta(ko. 0.00 10.0 + 1) and Fo. (G)goa) ~ Beta(k".), n011 10.1 + 1).
Now we come back to the proof of Lemma
Proof of Lemma The classifier is:
[1f(2,0) ) J =0
(| 11
So have the mis-classification error:
P(Y * 8) P(Y 0) P.
= =P(Y = - -, = 1, 0, 0= 1)
+ PPY -, -
0, = 11,A=11
P(( = 0|Y = -,A= 1) =
1, 1)
+ = 1/8 0,4 - + P(Ý -
= 0,A =
1.0 =)
Y= 0) +100 (R PoPY.0
1.1 (
- 1) ((L. |PIPY1
+EP(((2,0)221000 1.0
- A 0) (10
1.0
10.l,o///oll pr;))
+EP(((,1)22 1.1
Y A 1) (KL.
111
P1 PV.1)
= (
1.0
0) (kL.0) PoPY.0
1.0
(
= 1,A 1) ((L.))
1.1
PIPY.1
+ {EP(((,,0)2 0.0 ((00)
= - = 0) 1.0
Po Pr.))
+ (E 0.1
Y = 0,A = 1) 1 ( (p
(1 pr.))
E[F (12.0))
1,0
PoPY.o + E (((1..))
1.1 (1A.,,)PPPY..
+ E - 0.0
0.0
((6000))
0.00
[Ro.0g]
1.0
1o -Py,)) + E[1 - E 0
(f(ao1))
0.1
1 - pY.1)
1111
n 0.0 +
B(K 0.0
0.1
+ B(k 0.1
1.0 + POPY;O
+
nI,11
+1
PIPY,
n0.0 +
Po pY:0)
no. +
PI -py.))
The last equality comes from Lemma 4 and from the fact that E( ((Bela(a, a+3 Similarly, we have
1 1.0
1,1
0,00
E(R. 0.0
0, E(ke 0.1
P(Y +8)
PoPY
n1.1 + PiPr,1
n0,1 + Pr (1-py.)
n 1.0
0,0 +
15

---

Published as a conference paper at ICLR 2023
200 R(
Thus, we have
(P (x. a) * Y) - PoPPo + p +
n0 po - PY,0) +
x0141 -B(K
Pi(1 py,1]] كN poll-pra
11) + p1(1-pra)
2(m0.11)
Now we complete the proof of Lemma
Next, we come to prove Proposition 2
Lemma 5 (Hoeffding's 's inequality). Let X1...., Xn be independent random variables. Assume that X; E [m,, Mi for every Then, for any t > O, we have
n
2+
(x, EX,) 1 Se (M,
Proof of Proposition 2
First, we notice that k, is the number of (0.0's such that 10, < 2,
i.e.
k..a = Σ 160
00
1.a (1..a)) )-
Thus, for a given
O, from Hoeffding's inequality, we have with probability 1 - 22n
9.1
Σ 110
1aa
Σ
B(Ile)
<
cla
(((11g))) })
SCc
n 0.a
00a
Similarly, with probability
22
0.1
k
(AA
Σ 1
< 1.0
(M
Σ
B(1
<
La
})
2 -6
n 0,0
n0.00
Thus,
k B(K 0.0
I with probability - 2e n.2
n0..
Then we estimate Pa and Pv.a by Pa nn P.o and pr xe (n is the number of the total
samples). Here, an Σ 112 and Yia
12(
where Z ~ B(1, Pa) and
zy PY,, From Hoeffding's inequality (Lemma 5 we have:
n,a
P( P. - -Pa 12
c) < 2e 2n
n0a
< 2e 2in
P( Py,a PYaa
Thus, with probability 1 - -2-2 have:
00.0
Pa - -Pal 1 1
n
0.a
Py -PY.a 5
0,a
E(R
0.a
16

---

Published as a conference paper at ICLR 2023
Hence, we have with probability 1 - 6(c-2((00)) 2.0 + t--20")1)
(P( a) Y) P( a) +
Y)
22.0
n 0.0
+ 0.5 - E((,,
Po(1 Pr.o) + n + 0.5 - E(h
<
n0 +1 PoPr,o +
n2 +1 1 PIPY,1 +
P2 - (1_1)
n0.0 +1 1
n1.1 +
k
no.
+ 0.5 - 000
no1 + 0.5 - k.
Popr.. + n + 1
PipY,1
Do 0v:0) +
Di (1 - bby,))l
'1.00 +1
n0,0 +1
n0.1 + 1
Po pr,0)
+ P1(1 PY,1)
+
2(n
+1)
2(n +1)
n0,0 k1.0
no.1
(pi + Pr.)) + 2(( n00 20m0
k 1
n 0.1 K
(po + Pr;0) +
n
+1
I.
+ 1
1.0 +1
51
n 700
n0,0
70,00
+
Po + PoPY.0
+ po + Pv.0 1)]
n0,0
+
n0
no.
n.
no. + 1 [p1 + PIPY, +
c+ P1 + py,1 + 1)]l
n
n
n
0.0
+ 0.5 - E(KA )
n0.0
0.0
+
+ Po + PY,0 +1
n0 +1
n
n
0,
+ 0.5 -
no.1
n2.1
Po(1 - pr:o)
+ pi(1 - -py.1) 2(n + 1)
+
cVV
c+ Py,1 + 1]
n0 +1
2(n + 1)
000
n0,1
+ 2( 0.0
01
(Po + pr:o) +
(pr + pr,1)]
n
n
n 0.0
n2.00
+
<|
p0 + PoPY.
+
+ po +
PY.0 + 1)]
0,0
+
n2
n,.
n2
00,1
1
[PI + PIPY,1 +
n
E(1
n
+
P1
+ py, + 1)]l
12,0
100
n0,1
U.
elv
+2o + py,0 + +
<|1
pi
pr,1 + 1]
n
n
n
n
Po(l pr,o)
+ P1(1- -py,1)
+
2(n
+1)
2(n +1)
<2c + 2 + =l 4e + 2] + 22 + 4e+ po pr:o)
(1 pv.1)
2(n +1) + p1(1 pr,1)
2(n 0.1 + 1)
po(1 pr,o) = + +6e2 + + 2(n0,0 + +)
2(1 + 1)
Thus we complete the proof.
A.4 THEOREM FOR THE ORIGINAL CANDIDATE SET K
Sometimes we would use the original candidate set K instead of the small set K' to achieve the optimal accuracy more precisely. Now we provide our results for the candidate set K.
To facilitate the theoretical analysis, we first introduce the following lemma which implies that the difference between the output of the function can be controlled by the difference between the input. (i.e. the cumulative distribution function won't 't increase drastically.)
Lemma 6. For a distribution F with continuous density function, suppose q(x) denotes the quan-
tile of x under F, then for x > y, we have F(-{(x y) S q(z) - q(1) S F(+)(x - y), where F(-)(z)) and F(t) (z) are two monotonically increasing functions, F(-)(c) > 0, (()(()) > 0 for any > and lim ((-)(t) = lim P(t)(e) =0. c00
c-1
17

---

Published as a conference paper at ICLR 2023
Proof of Lemma 6 Since the domain of ((x) is closed set and ((x) is continuous, know that ((x) is uniformly continuous. Thus we can easily find F(+) to satisfy the RHS. For F(-), we simply define ((-)(t) = inf (g(a b) - ((t)). Since g( + f) ((t) > for > 0 and the domain of
a closed set, we have (c))(c) > for e > and lim P(-> (c) O. Now we complete the proof. D
c0
Now we provide the following theorem.
Theorem 5. Given a' < a. If min nl.1 2
log log(1-a)
Suppose & the final output of
FaiREE, we have:
(1) (DFOO(()) < with probability (1 (1-8)M, where M is the size of the candidate set.
(2) Suppose the density distribution functions of f under A = a, Y = 1 are continuous. When
the input classifier f satisfies f(z,a) f (x, a) Is eD. for any > 0 such that ((t)(E) S
p-o' ((())(20), we have
Pu(1 py,u)
P1 - Pr,1)
P(O(z, a) P +Y) < 21 (0)
n0.0 +1
n0.1
with probability (2M + 22 + -222 )) (1-
- -11- -1-F))))) (26))
Proof of Theorem The (1) of the theorem is direct corollary from Theorem (2) of the theorem. The proof can be divided into two parts. The first part is to prove that there exist classifiers in candidate set that are close the fair Bayes-optimal classifier. The second part is to prove that our algorithm can successfully choose one of these classifiers with high probability,
prove the
We suppose the fair Bayes optimal classifier has the form di (z, a) (x"" Xa)- And the Aa).
output classifier of our algorithm is of the form Ö(z, a) = 1ff(x
For the first part, for any e > O, from Lemma t has a positive probability F (2e) to fall in the interval [X] e, X + +e,, which implies that the probability that there exists E {0, 1) such that all gl.a's fall of [Λ_ e, A + is less than (1- 1---. (2e))a² + (1 F())
So with
probability (1 ( (26))
(1 F22)(
there will exist g/,a in [X; e, Xg + c).
which we denote as Φu a) (xf a) 1.""). We also denote (5 a) (f a) > t.a). Hence the gap between the classifier Φn and the Bayes-optimal classifier will be very close. In detail,
we have
(( a) FY) (1) +Y)1
< (()o((z,)) a) 4 Y) F(O)(1, x)) + (Y) # Y) SP(t. S (r, S =1.a" + + F(min(t! X < (x, I mar(t );1
(Lemma 6 (2e0) + F(t) (mxx Xa m , (2E+)(260) (f)())(
complete the first part of the proof.
Now we come to the second part. First, we notice that DEOO((g) and DEOO are close to each other.
18

---

Published as a conference paper at ICLR 2023
(E) DE00
< (EO00 | DE00(()) ||] || (E00
= || 41 -==
- > 10 4 -
+ || -==
< "=
+ ""
+ ",""""""",,,,,,--0000"""""""""""
<P( - -000 +
+
P((" > X/ |+
22F (2c0) + P(min(t!"" <f 1 mar x)
(Lemma 6
(2F (260) + ([+) a x - min (t ,
(260) 22 (260) + (e)
Thus, (1F00((0)) |S| (E00( +2F (+) (26)) + 2F) = a' + 2F (F) (260) + (f)
If ((()(() < p-n' 2 (-) (2en). then there will exist at least one feasible classifier in the candidate
set.
From Lemma
3 we have the miscclassification error
(z)
a)
n 2..0 B(K * Y)= 1 PoPY,0 1.141PPPY.1 + Pi pr; )] Iا po
Po(1 pr,o) +
no.04
(1 21n
+11 +
If accurately estimate the mis- missclassification error, than the second part is almost done. For the estimation of (K)))))) ), we can easily use k..0. We notice that k..0 is the number of t0.0's such
n
that 0.a < 1. (k):a)
i.e. ko = Σ 110000 < La (g
Thus, from Hoeffding's inequality, we have with probability
1-6 e -2n Piae
0.1
Σ
16
0.a
la
Σ
B(1tt)
0.0
< <tha
0,a E(Ke
S C.
n 0.0
0.a
Similarly, with probability 1 - e 2n
2
Σ
1 0,
< 1,a
}
Σ 1=1
B(1
< 1.a
(1/99))
})
10.0
(k!
2 -E.
n0o0
10000
Thus,
I with probability 22 0.02
Then, it's easy to estimate Pa and PY,a with Pa 11 and py. Yi
(n is the number of the
(27-1)
total samples). Here, n1
and
where 2 ~ B(1,
and z. B(1,pY,a). From Hoeffding's inequality, we have:
n.a
12 c) S 2c 2n
P(1 p. - Pa 12
19

---

Published as a conference paper at ICLR 2023
n0.0
2
P( PY,a
PY, 12
s 2
n
Thus, with probability 1 - 6c u22
we have:
n.a
pa - Pa 1
n
n0a
PY,a
-PY, 1
n
kg 0,a
E(A:
S
0,a
Hence, we have with probability 1 - (2M + 4)(E 22 + t 22011))) for each i E (1.....M]
[P a) +Y- - (( a) # Y)
11.00
k!
0.0 + 0.5 EE(K
0.1 + 0.5 E(kl..)
PopY,0 +
n1.1 + PIPY,1 +
Po PY.o) +
D1 - pr.1)
1.0
n0.0 + 1
n0,1 +
k!.0
k!
0.0
0.5
k0.0
n1 + 0.5 k0.1
Popr,o +
prpr.1
1o pv,0)) +
11 6r,1))1
n 1.0
n1.1 +
0,0 + 1
n0,1 +
Po - py.0)
P1 - .
+
0n0
+1)
2(n +1)
0.0
n2
(pi + PY.)) + 2
n0.
k. 1.0
0.1 K 1.1
(Po
PY.0) +
72
n
1.0
+1 1
n 1.1
n
n 1,0 +
n n
0.0
0,0
7,000
n
+ c(
PPo + PoPY.0 +
+ po + PY.0 + 1)]
0,0
+
n 0,1
n
(Pi + PIPYa +
+ + py,1 + 1)]]
10. +1
0.0
0.5 E(Ko0 0.0
0.D
72000
Po + PY,0 1]
000
+1
n
n
0.1 0.5
E(A
no.
U.III
6
+
Pı
+ Py,1 +
n1 +
n
7
Po pY.0)
(1 1r.1)
+
+
2(n0,0
1)
2(n + 1)
20

---

Published as a conference paper at ICLR 2023
Further, we obtain
(( a) (Y) - (() # Y)
n00
(Pu + pY, + V n.1
+ 22( no
n0,1
<cl
(pr + pY.1)
+
n
n
n2
72 0.0
'000
100
+ c
[po + POPY,O +
e(V
+ Po + PY, + 1)
000
+1
n2
nO.1 c((
n0.1
[P) +IPPYI +
+pi Pi + +P.1 + 1)]l
n0.1
10,00
n0.0
E Do
PY,0 + 1]
n
n
no.
n0I
+
dV
c+ ++11+ + PY,1 + 1]
n2
n
+ po(1 - pY,o)
+ pi(1 - -pr.1)
2(n +1 +1)
2(n0.11 +1)
2e + ? + +ele + de + 2| + + de
+ 2(n + + pI(1 - -Py.)
po(1 pr.0)
2(n +
= 3 + 6e + 8E + po py:0)
+ (1 - pr.1)
2n0 +}
2(n 1)
Combining two parts together, we have: with probability 1 (2M + 4) 0002
+ ) -1 -11-F(2(2))) -(1-F(2) (26))
po(1 pr.o)
pI - pv.1)
P(o(x, a) # P (x. x 2F()) (1++ + +1222+1cc++
n0.0 +1 n0 +
Now we complete the proof.
A.5 PROOF OF THEOREM 2
now we prove the (2) of the Proof. The (1) of the theorem is a direct corollary from Theorem | theorem.
It's sufficient to modify the first part of the proof of Theorem 5 and the second part simply follows Theorem 5
For the first part, for any 6 > 0, from Lemma 6 110 has a positive probability Fl-9 (2x) to fall in the interval [YB e, Aŭ + e). which implics that the probability that all f1.0's fall out of [Λg e, A5 + e]
less than (1 F(-) (2c)) So with probability 1 (1 Fi2) (26)) there will exist 14. in
[Ag - e, X +e), which we denote as Ag. We denote the corresponding classifier as (1ff(zaa) > Aa).
From the proof of Theorem we have with probability - 4e 2n. 0,,, (1 (2)()
00a Pa Pa S
n
0,0
1rya - -PY,a 1
e
n
IAo 1 Ao S
21

---

Published as a conference paper at ICLR 2023
We have the following equalities:
2)popy,o
2
PIPY.1
1
A1
( -2)popr
2
Aidr,1
Hence,
PoPY.0
PIPY,1
2(popy,o + PIPY.))
A6
X
POPY,0
P1PY,1 A1
2(porr. +1bv,1)
A0
By subtracting, we have
1
1
(2
1oiDy,1
(2 -
1IPP. = T
2) - -N5 2)popr,
A
A1
We have
1
1
2)podro
22)ooPr.
A0
1
(P + V 100
0,0
(pr,o +
c) ( Xu
2)popr:o
70
nn
2) + pr.o + v /r00 r)
popr.o + V
c(
c)
\ō -
Similarly, we have
1
2)porr.
N/5 2)poPY..
1
POPY.0 + V Vimo
/n000
1
Py.o + /10,0 )
c(
2)(-Po
25 + c)
\o +
1
(2
PIPPY.1 - (2 \;
P1PY.1
+1 no.I
1
+ Py.1 + V no
<( M A
)PIPY.1
c(2
(pi
c);
A
1
(2 X1
JPIPY1 - 12 xi
11PYY11
)pIPY1 + V no
)-pr - Py, + no
2( Ni A
c2 -
c).
Now, we get:
n1.1
n0.1
PIPY, +
e22
(-pI P1 -P-1
Xj
X
n
X1
n
0.0
1
12000
POPP,
-P) + PY.O
t)
Ai
n.
)PIPY.I +
(22
(pi + PY.1 +
c)
Xi
A1
0.0
1
000
PoPY. +
22(
Py.o +
1g +
+
n
22

---

Published as a conference paper at ICLR 2023
Hence, we have:
A1 Xi
A
1,0
n0.0
101
no.1
PoPY,0 +
c(
-po + Py.0
c)
2\
c P1 PV, +
e)
Pipya 2G 6)
Ag
and
A1 - Xi
A1
n0,0
n0.00
no,1
n0.1 c)
"ıPya"
A5 + +c)
Popr,o
Y
El
25
+c
2)((pp Py.0 + [nn)) - 2/
<(p + P., +
Thus, we have:
Pop-o + cl x - 2) + +
A AT
pıpy,1
Now, combined with above, we have with probability
de
2.0
- (
(26))
n0,a
Pa Po s
nuaa .v. - -r,
n
No No S
A 1 11--i xils Ap PuPY.o + PuPy.
x
1 - 2)(2+ 4e
PIPY.
From the proof of Theorem
we have:
((t)(e) a-a' (2t)) then with probability (2M 4)(e 2) -2200)2)
(2))))))
P(O(z, *)) (2) #Y)
(2c))) + ((+)(() + ( PoPp + <xx= + +c)
+ 12e² + 16c.
PıPY,1
Now complete the pronf.
A.6 FAIR BAYES-OPTIMAL CLASSIFIERS UNDER EQUALIZED ODDS
Theorem 6 (Fair Bayes-optimal Classifiers under Equalized Odds). Let EO* = DEO (f*) = (E*,P* PP). For any a > there exist an S and < 0g S a such that all fair Bayes-optimal classifiers JEo under the fairness constraint [FO(()) 3 (0n, 022) are given below:
When |EO*| (2), fEO.a f
When E > an or P > a2 for all x E X and a e A, there exist t, and t 80,0
such that
(x,
Ry.. 1-PY. 12,00.a
I 11(x))
IpaPr 11(, TV.
Pr. 10, 10..
PoPY.- (20 p.. 10000.
+ aT (o(x)=
2paPr,a+ 1)(
pv. Py, 10,00 (.....))
PiPy,1 + T-Py.
10500
Here, we assume PXIA=TY==
(x(X)
2piPy.1 PV.1 15
10000
PiPr.1 PY.1 17 2pipy.+
P (x()=
0 and thus Tho [0.
PY.1 5, -1.80..
be arbitrary constant.
23

---

Published as a conference paper at ICLR 2023
To prove Theorem 6 we first introduce the Neyman- Paaaan- Lemma.
Lemma 7. (Generalized Neyman-Peate Peausnn lemma). Let for fi fm be m++1 real-valued functions defined on Euclidean space X, Assume they are -integrable for -finite measure v. Let d0 be any function of the form
fo(x) > > af(())
(x(
((x)
folx) = th Gf((z) Ei Li=1 Gf((z)
O,
fo(x)
where 0 Σ 7(x)) S for all x E X. For given constants , E IR, let T be the class of Borel functions Φ X + satisfying
[ of.du S ti i= 1,
(5)
and To be the set of & s in T satisfying (5) with all inequalities replaced by equalities. If dn E Too then do argmax Sx &Jodu. Moreover, if 2 for all -....1 m, then TETo
Φu E argmax Xx fudu.
PET
Then we come to prove the theorem.
Proof. If |EO*| 3 (a, a), we are done since f* is just our target classifier. Now, we assume |EO*| N (a, a) does not hold. Let f be a classifier that gives output Y = 1 with probability f(x, a)
under X and A The mis-classification error for f is
R(f) (P + Y) = -1 = 1, P(Y 0,Y
= IP = = 0) = -,, =
Thus, to minimize the miscclassification error is just equivalent to maximize P(δ = 1, = 0) P(ý 1,Y 1), which can be expressed as:
P(8 Y, 1) IP( 1,Y 0) = -PX (8 = 1)pIPy,1 + +FXIA-OY==1 = (1)))
-Px 1)p1 pr,1) PPIA=-oY=o(8 1) (1 -L-PP)
P1) (1 -pr.))
=p1 pra / / f(z, (IP. - -1 (11-))))-(p))) -pr1)) / f(x; (le:))dx
+ (1 (1-p)) pr.o /
(11-)))))) / f(F.0)dFx1
-/a/ ())
with
M (2, apı pr, d Expu=tvails) pr.1)
df vx
dxx(x)
dpx(z)
(6)
+(1 a)-o) prr, af xx
(1,py.))
dxx(x)
dx
Next, for any classifier f, we have,
DEO(F) = (I (PXIA-IYY=I = = - 1, = = (f=
= - f(x 1)dP ((x.))dFx)AAIIv=110))) - ([F,
[ f(x, Fl f
= =[a. ((2, [ o
24

---

Published as a conference paper at ICLR 2023
with
adPP X|A=IIy==12)
(1- (1-a)dP, x|=
Hg(æ,
pidll x (2)
Podl x (x)
adlP _dl
addl x (A=
Hp(x,a)
PidlP x (x)
Podl x (x)
Since lim
pir.1 PV.3 12
vy.
lim
p.py.- 1 PY.
PY.0
1, we have:
700 2pfpy.+1-py 4--1
t2 2pppy.0 1-PY,0 l2+4
PiPY.1
PY. L2
lim (x)1=1,y=1((((x)) > 2pipy, +
1-PY.1
100
Pv.
l2 11
PY.1
PâPy.o
PY.0 1/
lim Px)000,y=1100())>>
I-PY.0
420
2p0Py.0
1-vr.0
PV.0
1/2 + 11
and
pîpy,1
PY,1 12
lim (x) > 2pppy, + 420000
1-PY.1
PY.1 12
1-pY.1
PâPY.
Pv.o L2
lim Px(A=0,y=o((o(x)>
I-PY.0
400
2p.PY.0
I-Pr. t2 +
PV.0
So there exist a and 2 E0.00 such that: F
1,,00, E
> 0, 1,
p > 0, and
p
E (x]
PipY.1 I-Py.1 1 80.a
pipy;1 + I-Pr.1 12,80,0
T ) 2pipy, I-PY.1
F-
2pipy.1 + 1-pr.1 E00 81,00a
2,50 -1,50,0
Pv.0 pôpr I-py,0 2,00aa
-XIA=0Y=11((22)>
)] a1 <
2p:py:0
Py 2000 + +
T-py
P (o))))y-=(((()>>>>)))))))))))))) 2pppya + I-PY,1 12 11,00a
pipy. + PY.
1-PY.1 t,00aa
pipr.1 + 1-Pr.1 2,000
pv.1
) )+ (+ = 2pîpY.1 + I-PY,1 1, 1, 50,0
|P]|
PYJ
PY.1
PopY.o I-Py.0 1,E.0
Py.0
- -Px)a=0y=o(mm())>>>>
)) <
2p
I-PY.0 1000 + 4,00,a
We consider the constraint,
F
I f(a (( a x
E
(8)
F
[ 0 az.
Fr
Let f be the classifier of the form:
1. M(r,a) > E
g
He(z, a)
= p' Hr(a,a); a];
feree
at, M(2,a) He
82 82 Hr(
0, ((x,)) He(2,0)
82 (z)
25

---

Published as a conference paper at ICLR 2023
From
6
&
M (a,
a)
s1 "1 (e(e)) + 82 pt. " Hp(s, is equal
Pr.1 dP dPx|A_Ly=1(1) (1-1).) dlx (=1Y===0 dl dpx(x))
0p1
dPx(2)
dl 0| alpo Pr. dP (x) - -(1 -1- pp
(1
dx
(px(x)
E
adP x(Pxx==1y==10) (1 - A=
E+
(x)
Podl' x (x)
P
adP x|A_
(1 - a)dP X1 x|A=0,
(x)
padf x (I)
which is equal to
JP x (-1Y=1(0)
dl d[14=1L==04)) dPx(x)
E
E sIdP A= (x)
(py pt
s2df A ,0=1
PY11
dl (x)
- -PY.1)
PidPx(1)
dPx x A=0Y=1(0))
dl dPx1==0r==(x))
E x (x)
[P. a2d x| 0
po
Pra
dP d2x(x)
pr.u) dp)
PodPx(2)
Thus.
E" Hn(
pt H)(
M(x,))
82 ppl
E
dP x= (1 pr,a)
dl x
F" > (2a | 18-35101 sTlP X|A=a.Y (1 + 1F xxadfx)==ay==0((1
+ Pa
PY,a
x (x)
dpx(x)
xa
P.PY,a (20 1)
PV.a t2
pY,dPp x (=0
1-py,
PY. x (x) + (1 PY, Jol X(A=a,
2pâpy,a (2a 1]( 1-py.a t1)
PY.a
Er
p
where
E+ 81,
[ 52-
PaPY,a + (2a 1),
PY.e t2
- (a()) 2pÊpy, + (2a 1)(
1-
PY.a
1/ t1)
I-PY.-
As asaresult for .2..7 (x, a) in can be written
PaPY,a + (2a 1) PY. 12 py
P.P., + (2a 1) Py.a 1/
T-ppy
- = (x) 2paDy + (2a- - 1)(1=) 1 t1
(arl())())= 2pppy.a + (2a - 11)
PY,0 t2
PY.c to 1t)
(10)
Further, the constraint K for f in 10 is equivalent to
PY.1 pipy. + I-PY. 12
pápy.1 + I-Py.1
PY.1 L2
E P (x)
+ (xx))
2pppy:1 + PV.
l2 11
2p?pr;1 + Py.1 1/ 1
T-Py.1
T-py.1
porr,
1-Py,0 to
P -x11=_0y=1((((()
)| $
2pērr.
PY.0 +
1-pY.0
p
pipy.1 + T-py,1
PY.1 12
pipy,1 + Py.1
T-py.1 t2
| P (x)
+ (x)
2pfpy.1 + 1-py,1
PV,1 f2 f1
2pppr.1 + PY.1 bo
1-pY,1
popy,o 1-py,0 L2
PxIA-o,Y=o(To(a)
)] S 02
2p.pr.
pv.0
T--YY,0
(11)
Now, let To be the class of Borel functions f that satisfy ( and Tag.og.0 be the set of f-s in To that satisfy ( with all the inequalities being replaced by equalities.
From the definition of ti, and 1 E0, clearly ftj, "5 "i. (I, Ta Further, have sf =
so 2 > and s² = 12 8o. 2|P
p-
Hence, from Generalized Neyman Peaaann lemma, we have:
Jii.oo. (e, argmaa [Ale d TETa
26

---

Published as a conference paper at ICLR 2023
Now complete our proof.
A.7 PROOF OF PROPOSITION 3
Proof. The classifier is
(1[[(x,0) > 10 (000)): a =
(1(f(z, 12. )
we have:
[EEO = (I
(1 (Q....)) - F1. (((., )1 |F0. (12 ((itla)) (1t.o))))))))
-
10
nn
From Proposition
we have P(( ((tt.)))) p1
- ((
a) S El
Σ
(j)
(Q
1=bl.0
(Q - aa))mt -s + E
Σ
(Q110 - (1-00000000001100000000000001011 a))
j=
Also,
((1221)((1)))) F0.0
(t > a)
=P( 0.1 1111 (1 1:000 ( (1)3100) > a) + ((10)1)((bb)))) - ((000((())00))) < -a)
AB B
And we have
A = P(F 0.1
(Kt.1)) (t(o))))) > a)
= P(F0. (((11,0)
< F.o (ttel))))) (((1)))) a)
< P(F0.0 ((A0,)))
< pa.1 1a.1(11))) (1ig))
((,00) +1)) a)
I EIP(( 0.0
FO.0 F0.0-1 (1.1 (1))).+1)) a)) (F)) - a >0 (
(10.0)
= [l[at least 0.0 of 0.00s s are less than 10.00 (1001 -a0) 11100
- 03
= E(?
Σ
Plexactly j of the 00 are less than F 00.0 - 0.1
(F0.(((()1)))))) ((10144)) (((dd.14)))) - > 0} 0.1
((60.41)
2=00,0
0.0
n0000
E
Pit0.0 < F0.00) ((b0))4))))) a1) -1 (Fri (F0: (k(1).11)) -a)))
1=,
1 1 (1agt (1)))
a 3 0} 41)1
0,00
<
(1.0.1 00.1 (( - a))(L - (1 ((00((()))44))) - -a))m -
(100141))
0.1
A=A..0
Similarly, we have n
E Σ
(2000)00)00))) a)((1 - (10000100004) - -)))a(i ((000411)
0.00
j=
Hence, we have
n 0.0
0.0
+ B <
(F (1td - a)(11 - (F (1 - a))
-j
.011 1
j
j k=.000
011
n
+ E
(F (F00 (( - a)²(() (0000 (:0000000000000 (()0.041)) - -a))""
(200041)
0.0
k
27

---

Published as a conference paper at ICLR 2023
Since FO.a (f (1)) is stochastically dominated by Beta(kon 1, - kl.a), complete the proof.
A.8 ALGORITIMMS FOR OTHER GROUP FAIRNESS CONSTRAINTS
In addition to Equality of Opportunity and Equalized Odds, there are other common fairness con- straints and we can extend FaiREE them.
Definition (Demographic Parity). A classifier satisfies Demographic Parity if its prediction Y statistically independent of the sensitive attribute A:
P( 1) 1
Definition 5 (Predictive Equality). A classifier satisfies Predictive Equality it achieves the same TNR (or FPR) among protected groups:
Po =1 ==0==
Definition (Equalized Accuracy). A classifier satisfies Equalized Accuracy if mis-classification error is statistically independent of the sensitive attribute A:
PP * 1 A=
PP # A=
Similar to DEOO, we can define the following measures:
DDP = PXIA=I = 11) - (P =)
(12)
DPE PxIA=1YY= = - PxIA=0,Y=u(* = 1)
(13)
DEA P( #Y A= P(Ý Y A 0).
(14)
A.8.1 FAIREE FOR DEMOGRAPHIC PARITY
Algorithm 3: FaiREE for Demographic Parity
Input:
Training data: S 50.0 S U S1.0 s.1
a: error bound
8: small tolerance level
f: a classifier
Tv.a
{x V.0
f (x }}
(0)) (my.a)
13.0
T Tv.0 U7
((m))) =sor((T")
Define g(k, a) = =E (0)- (Q -a))==- with
j=
Q" ~ Beta(k, (k. n
1: + 1), L(k0.11 131) = (k0 + g((''
Build candidate set K {(k k.)
L(ke
k. _0 = [(K9, k(),. ..... (k2 kbd)
Find k.v0, 1n. < 10 (12) (1.."+1) p..1 (A..0)
0.0
< ( < pll
p +1)" E E {0,1}
1
1x f arg min(é)) (6; defined in Proposition *E(M]
Output: Ó(z, a) = (s((z 1
Similar to the algorithm for Equality Opportunity, we have the following propositions and as- sumption:
28

---

Published as a conference paper at ICLR 2023
Proposition 4. Given k0, kk' satisfying kst (1,,...,,?) (a 0,1). Define a(x,a)= =(f((x,)) aa)(1 -0000-0-0 -a)-(-Q-aaa->>) with Q" Betalk, K 1),
(bezh g(ks a) B M
then we have:
P(IDDP(0) a) S gkk".0) g(k',1)
If is continuous random variable, the equality holds.
Theorem 7. If min(n", n 2 log(1 (151aaa) we have [DDP())) < a with probability 1 8, for each i E [I,...,M};
log &
Theorem 8. Given a' < a. If mi nn 2
log 4
|. Suppose & is the final output of FaiREE,
log(1
we have:
(1) (DDP()) S a with probability (1- (1-5)M4, where M is the size of the candidate set.
(2) Suppose the density distribution functions of f under A = Y = 1 are continuous. DDDPa
S arg min a P(O(x, a) + Y). When the imput classifier f satisfies Ilf a) $
for any > O such that F (c) < a-a' (2c)) we have
((((zz.)) + Y) - P( (I, a) + Y) 15 2F 2F (2t0) + 2F + 3 + 12c² + 16c
with probability 1 - (2M + 4) 2n 20 + +e- 2n + 22 2.02 + 12
A.8.2 FAIREE FOR PREDICTIVE EQUALITY
Algorithm 4: FaiREE for Predictive Opportunity
Input:
Training data: S 50.0 U S0.1 U 81.0 U
a: error bound
8: small tolerance level
f: a classifier
T
(sx )..f(")).............). 1 (27gg))) }
(the ((x.a))
=son(Ty).))
0,0
Define g0 (k, a) E Σ j=k
(1) (Q0.1-a -Q011--a)((1 (Q0,1-a -a))a -1 with
Qu.a ~ Bela(k, n k: + 1), L(k0,0, ,.011)= go (k00000 00) + g011 1)
Build candidate set K = [1000 k0.1) L(k000 k0,1)
S 8) = [Kkp00 10.1 .....: 0.0
4011)
Find k.!" ..! 11.0 < 100 (1
1 1.0
11
< 0.1
11.1
(R) +11"
(
(11
ix arg min { (é, defined in Proposition iE[M]
Output: ò(z, a) = 1 (f(xx,
0.a (1.9.))
Similar to the algorithm for Equality of Opportunity, we have the following propositions and as- sumption:
Proposition 5. Given 10000 00.1 satisfying ki.0
E {1, n.....,no]] (a = 0) Define o(I, a) = (Qu11-a
0,0
1(((x,)) > for ( (k, a) E
(m) (Q01-a-a)) -1Q(01Q00111 -a))nn--1 with Qu.a
j=
Betalk, 1e ++11 1), then have:
P(DPE(() > a) S (k0.0 .0) + (k0.111,1) 1).
If f0 is continuous random variable, the equality holds.
Theorem 9. If mi n013 > each i dl...,,M.
Tog(1 -aj 1, we have IDPE( < a with probability 1 - 8, for
log
29

---

Published as a conference paper at ICLR 2023
Theorem 10. Given a' < a. If min(n 0.0 ..n...nn.. 2
log 3 log(I-o)
1. Suppose é is the final output of
FaiREE, we have:
(D)))](() S a with probability (1 (1-8)M, where M the size of the candidate set. (2) Suppose the density distribution functions f under A = a, = 1 are continuous. & = arg min (PE()))sa P(o(2, a) # Y). When the input classifier f satisfies [1 - (", S
forfor any > O such that F(+; S a-a' 2 F(t) (260), we have
(((((2,)) + Y) - P( (I, a) # Y) 15 (F) (t) (260) + 2F (F( (+) + +12 + 16c
with probability - (2M + 4) 2n 00 + +e- 22 - (1 p (26))
- -(1 -(1-1 (2e) (2))
8.8.3 FAIREE FOR EQUALIZED ACCURACY
Algorithm 5: FaiREE for Equalized Accuracy
Input:
Training data: = 50.0 U 80.1 U 81.0 U.1
a: error bound (a > |py,1 - PY,u))
8: small tolerance level
J: a classifier
Tv.a
(s )...........................)) l (24ga)) }
(00 (1))
(ing ((y.a)) soo((
Define 91 (k:, a) R
PP Q1110 (1
PY,1-a Q -a -annl -1
-1
with
DYa
PY.a
j=
Qlaa ~ Beta(k,nt n - kt + 1),LI (10 klll)) = (k61.. ,1) + 91 (k'.0.0)
Define go(ki,)) a)
E no.
E (")")((( ( (1-prr 110.1-0+p17 PY 1y (1- (1-pr. 200011- +py,1 PY, a ya -9-1
1-pY.0
1-py.a
with Quaa ~ Beta(k + 1, - k), [k0.00 ,.0.1) = (k0.111111 11) + so(k0.0,0)
Find 8000 20.1; 0.0 ((0000) I
+1.0
0.0
0.1
S { (k)1)) < +0.1
(11.0)
<
+10.0+1) (10.1)
(1).1411)
Build candidate set
K [(11.0 12111 | Li (k110, k211) + Lo (k0.0
1011) < 8} = ((1) (.t )...)................... (k11 k }}
i. arg min ( (és is defined in Proposition 2 iE[M]
Output: ò(2, a) = a()(x,)) t2. (
Similar to the algorithm for Equalized Odds, we have the following propositions and assumption:
Proposition 6. Given k.1,0. k1,1 satisfying kl.a E fl.....
mlaa (a = 0,1) and 1a (iingh g1(k,a)
[PY,1 py.ol-
Define 6(x,a) I(((r,)
La
j )( (Pr.-1 -ut.-aqut--- -ay(1 -h -00 with Qua Beta(k, nhe - k
E
Σ j=k
PY.a
PYa
n.a
1), (a) = tt
and golk: a) = E
Σ j=k
(n (aral())))
I-pr.-
(a) i) with Q0,a ~ Beta(k + 1, - k). Then we have:
P(IDE((0 > a) S 91 (k1 ,1,11,11111 1) + 91 (k 0) go ,1, + go .0)
Assumption 1. 000 N [ Tog
log
1. 0.1 2 hogg( -- 1. 1.0 2 log(
log
log a
1, n > PY.1-a
py,0 1
Py.0
log 4 1. in which [-] denotes the ceiling function.
log(" PY.D 57
Theorem 11. Under Assumption we have [DEA( S a with probability - 5, for each i (1,..., M).
30

---

Published as a conference paper at ICLR 2023
Corollary 1. Under Assumption 1 we have (DEA(0)) & with probability (1 8)M, where M the size of the candidate set.
A.9 IMPLEMENTATION DETAILS AND ADDITIONAL EXPERIMENTS
From Lemma 2 adopt a new way of building much smaller candidate set. Note that our shrunk candidate set for Equality of Opportunity is:
K' =1(''. ui (k (O)) L1 u1 "1(k'.0) - 66}.
Since Equalized Odds constraint is an extension of Equality of Opportunity. our target classifier should be in K'.
To select our target classifier, it's sufficient to add a condition of similar false positive rate between privileged and unprivileged groups. Specifically, we choose our final candidate set below:
K" [{ un (1:40)) Li (kt.", un (k*-2)) s 6, Lo k2100 s 5d}.
We also did experiments on other benchmark datasets.
First, we apply FaiREE to German Credit dataset (ataset(Kamrran & Calders 2009). whose task predict whether a bank account holder's credit is good or bad. The protected attribute is gender, and the sample size is 1000, with 800 training samples and 200 test samples. To facilitate the numerical study, we randomly split data into training set, calibration set, and test set at each repetition and repeat 500 times.
Table 5: Result of different methods German Credit dataset
Eq
C-Eg
ROC
FairBayes
FaiREE-EOO
FaiREE -EO
0.07
0.1
0.14
0.07
0.14
0.07
0.1
0.14
DEOO
0.078
0,093
0.100
0.126
0.125
0.126
0.020
0.029
0.034
0.001
0.025
0.048
DEOO 95
0.179
0.127
0.267
0.160
0.182
0.186 /
0.066 /
0.097
0.130
0.004
0.084
0.120
DDE
0.109
0.072
0.138
/
0,041
0.063
0.092
IDPE 9c
0.235
0.114
0.334
/
/
/
0.059
0.097
0.133
ACC
0.707
0.720
0.591
0.722
0.723
0.723
0.717
0.729
0.745
0.702
0.721
0.722
Then, we apply FaiREE to Compas Score dataset Angwin et al. (016)), whose task is to predict whether person will conduct crime in the future. The protected attribute is gender, and the sample size is 5278, with 4222 training samples and 1056 test samples. To facilitate the numerical study, randomly split data into training set, calibration and test set each repetition and repeat for 500 times.
Table 6: Result of different methods on Compas Score dataset
Eq
C-Eq
ROC
FairBayes
FaiREE-FOS EOO
FaiREE- EEO
/
0.07
0.1
0.14
0.07
0.1
0.14
0.07
0.1
0.14
DEOO
0.083
0.642
0.070
0.077
0.109
0.136
0.026
0.033
0.042
0.027
0.049
0.098
DEOO 85
0.101
0,684
0.174
0.145
0.186
0.250
0.066
0.097
0.131
0.068
0.090
0.140
DPE
0.025
0.291
0.067
/
0.026
0.048
0.060
DPE ls
0.047
0.332
0.148
/
/
0.057
0.092
0.114
ACC
0.629
0.664
0.652
0.658
0.6588
0.659
0.654
0.660
0.672
0.623
0.654
0.669
We further generate synthetic model where trained classifiers more informative.
Model 3.
We generate the protected attribute and label Y with the probability, location parameter and scale parameter the same Model 1. The dimension of features is set to 60, and
31

---

Published as a conference paper at ICLR 2023
generate features with 2000 1, 1,2,... 60. 2 t(1), 2ng t(4), 2ig xi and m
Lid.
iid.
itd. 1.0
i.d.
X4. for
Table 7: Experimental studies under Model Here DEOO| denotes the sample average of the absolute value DEOO defined Eq. ( and |DEOO)ss uo denotes sample upper 95% quantile. [DPE] and |DPE defined similarly for DPE defined Eq. [3.. ACC is the sample average of accuracy. We use "/" in the DPE line because FairBayes and FaiREE-EOO are not designed control DPE.
Eq
C-Bq
ROC
FairBayes
FaiREE-FOO
FaiREE-FO
/
0.04
0.06
0.08
0.04
0.06
0.08
0.04
0.06
0.08
DEOO
0.041
0.020
0.034
0.048
0.062
0.076
0.018
0.025
0.033
0.015
0.032
0.034
DEOO 95
0.115
0.042
0.070
0.080
0.113 /
0.143 /
0.038
0.054
0.076
0.036
0.058
0.069
DPE
0.093
0.106
0.062
0.026
0.034
0.046
|DPFl
0.272
0.191
0.101
0.039
0.055
0.077
ACC
0.887
0.921
0.834
0.898
0.901
0.912
0.946
0.950
0.963
0.900
0.914
0.933
A.9.1 COMPARISON WITH MORE ALGORITHMS
In this subsection, we further compare FaiREE with more baseline algorithms that are designed for achieving Equalized Odds Equality of Opportunity, including pre-processing algorithms (Fairde- cision in Kilbertus et al. (2020) and LAFTR in Madras et al. (208)) ) and in-processing algorithms (Meta-cl Celis et al. (2019) and Adv-debias in Zhang et al. (2018) under synthetic settings Model
and Model 2 described in Section 5.1 and the real dataset Adult Census in Section 5.22
The results
are summarized in Tables 9 and
From the experimental results, we can find that FaiREE has favorable results over these baseline methods, with respect to fairness and accuracy. In particular, the experimental results indicate that while the baseline methods are designed to minimize the fairness violation much as possible (i.e. desired
set a 0), these methods are unable to have an exact control of the fairness violation level a. For example, in the analysis of Adult Census dataset, the 95% quantile of the DEOO fairness violations Fairdecision 0.078, and that LAFTR, Meta-cl and Adv-debias are all above 0.2. Moreover, results found that If we allow the same fairness violation of DEOO and DEP for our proposed method FaiREE, we have a much higher accuracy (0.845) compared to the accuracy of those four baseline methods.
Table 8: Results of different methods on Adult Census dataset. Here IDE0O denotes the sample average of the absolute value of DEOO defined in Eq. (1). and DEEO0ss denotes the sample upper 95% quantile.
[DPE] and IDPE, os are defined similarly for DPE defined in Eq. (13) ACC is the sample average of accuracy. We use "/" in the DPE line because Fairdecision and FaiREE-EOO are not designed to control DPE.
Fairdecision
LAFTR Meta-cl
Adv-debias
FaiREE-BOO
FaiREE EO
& DEOO DEOO 95
/
0.07
0.1
0.14
0.07
0.1
0.14
0.041 0.078 /
0.124
0.172
0.199
0.034
0.039
0.066
0.002
0.039
0.067
0.203
0.253
0.248
0.065
0.090 /
0.124
0.008
0.094
0.125
DPE
0.044
0.194
0.074
/
0.030
0.066
0.074
/
IDE 95
0.083
0.271
0.094
/
/
0.056
0.078
0.086
ACC
0.772
0.822
0.688
0.791
0.845
0.846
0.847
0.512
0.845
0.846
32

---

Published as a conference paper at ICLR 2023
Table Experimental studies under Model with the notation Table
Fairdecision
LAFTR
Meta-cl
Ady-debias
FaiREF-FOO
FaiREE-O
0.08
0.12
0.16
0.08
0.12
0.16
DEOO DEOO 95
0.072 0.177 /
0.081
0.028
0.062
0,028
0.046
0.063
0.025
0.031
0.042
0.145
0.108
0.226
0.073
0.115
0.157
0.079
0.108
0.133
DDPE
0.061
0.118
0.179
/
/
0.039
0.042
0.045
/
DPE
0.104
0.272
0,412
0.075
0.084
0.106
ACC
0.616
0.533
0.620
0.645
0.621
0.657
0.669
0.552
0.562
0.615
Table Experimental studies under Model 2, with same notation as Table
Fairdecision
LAFTR
Meta-cl
Adv-debias
FaiREE-FOO
FaiREE-FO BO
/
/
0.08
0.12
0.16
0.08
0.12
0.16
DDOO
0.675 0.744 /
0.450
0.094
0.096
0.027
0.047
0.073
0.028
0.035
0.047
DEOO 95
0.633
0.208
0.263
0.075 /
0.112 /
0.153
0.077
0.114
0.143
DPE
/
0.502
0.120
0.140
0.041
0.044
0.056
DPE 15
0.686
0.312
0.418
/
/
0.071
0.090
0.127
ACC
0.584
0.647
0.606
0.628
0.595
0.627
0.639
0.575
0.589
0.606
A. SUPPLEMENTARY FIGURES
0.35
0.15
fultCS/mmert
0.14
0.25
8800
0500
0.05
0.15
0.04
0.640
0.645
0.650
0.655
0.660
0.665
0.670
0.645
0.647
0.650
0,002 0.
855
0.657 0.000 0.602
Figure 3: DEOO Accuracy, complementary figure for Figure
0.5
x
faIRCE-EO
Eq
0.4
C-Eq
ROC
FarRayes
DF00
0.5
0.4
0.2
0.1
0.50
0.55
0.60
0.65
0,475 0,500
0.525 0.550 0.575 a.600 0.625
Figure 4: DEOO v.s. Accuracy & DPE v.s. Accuracy for Model 1
33

---

Published as a conference paper at ICLR 2023
IsREE-E00 FaiREE-O
0.45
TeIREE-EO
0.40
Eq
0.6
CEEq
ROC
ROC
0.5
FairBayes
0.30
g 0.25
0.15
0.2
0.10
0.1
0.05
0.40
0.45
0.50
0.55
0.65
0.40
0:45
0.50
0.35
0.60
Accuracy
Figure 5: DEOO Accuracy DPE Accuracy for Model 2
0.14
FaiREE EDO FaiREE-EO
FaIREE:
0.12
C-Eq ROC FairBayes
ROC
8
0.06
0.04
0.88
0.90
0.92
0.94
0.96
0.84
0.86
0.90
0.92
Accuracy
Figure 6: DEOO Accuracy DPE Accuracy for Model 3
0.16
FaRREE-EO0 Pa/REE-E
FaIREE-EO
0.11
Eq
0.12
C-Eq
ROC
ROC
Tairaaees
x
0.09
0.08
0.08
0.06
0.04
0.02
0.06
0.35
0.05
0.70
0.75
0.80
0.50
0.55
0.60
0.65
0.70
0.90
0.85
Accuracy
Accuracy
Figure DEOO Accuracy & DPE v.s. Accuracy for Adult Census dataset
FAIREE-SO
0.25
ROC
0.15
g
0.20
0.10
PaREE-500 FaiREE-EO
0.15
Eq
0.05
0.10
ROC
FayrBayes
0.00
0.05
0.600 0.625 0.030 0.675 0.700
0.725 0.750
0.62
0.64
0.66
0.70
0.72
Accuracy
Accuracy
Figure 8: DEOO Accuracy & DPE Accuracy for German Credit dataset
34

---

Published as a conference paper at ICLR 2023
0.7
RiIREE
FaiREE-OO
Eq
Eq
C-Eq
ROC
ROC
Fairaayes
0.4
0.20
0.1
0.05
0.63
0.64
0.65
0.66
0.67
0.63
0.64
0.65
0.66
0.67
Accuracy
Accuracy
Figure 9; DEOO v.s. Accuracy DPE v.s. Accuracy for Compas Score dataset
35


Reviews:
[{"review_id": "gN-AnT1X9K", "reviewer": "Reviewer_6zkG", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a new post-processing algorithm (FaiREE) to satisfy group fairness constraints in classification with finite-sample and distribution-free theoretical guarantees. FaiREE can be adapted to satisfy various group fairness notions, e.g., Equality of Opportunity, Equalized Odds, and Demographic Parity. Synthetic and real data experiments further support these theoretical guarantees.", "summary_of_the_review": "This paper tackles an interesting problem with critical societal impacts, and I would recommend accepting the paper.", "strength_and_weaknesses": "Strength:\n\nThe proposed post-processing algorithm satisfies two theoretical guarantees (Thm 2 and 3), i.e., a) The output classifier satisfies fairness constraint with high probability, and b) if the input classifier is optimal, the output classifier will be near optimal with high probability. To my knowledge, these theoretical guarantees are novel and critical in trustworthy machine-learning applications.\n\n\nWeaknesses:\n\nThe second guarantee of the proposed post-processing algorithm in Theorem 2 requires a strong assumption that the input classifier is Bayes-optimal. Is there a way to bound the performance of the proposed algorithm with any classifier $f$ using the approximation error between $f$ and $f^*$?\n\nIn addition, if the classifier $f$ is first trained using some dataset $S_{train}$, all the theoretical results only hold when the dataset $S$ used in the post-processing is independent of $S_{train}$. Is it correct? Thus, a train/validation/test split is still needed in this setting, and the sample complexity results in table 2 should be interpreted as the validation sample complexity since it does not include the sample needed for training $f$.\n\nMinor comments:\n\nFigure 1 is really difficult for readers to digest at the beginning of the paper. Readers need to understand $\\alpha$ and DEOO to appreciate the results, so maybe deferring it to later sections will be better. Also, figures are more readable than tables, why not include more figures in the main body and move those tables to the appendix?\n\nTypo: 2 line above Paper Organization, should be “group” instead of “grup”\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "HRdI_Mu4W_u", "reviewer": "Reviewer_8rQh", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "\nThis paper considers the problem of fair classification by post-processing the decisions of an existing (possibly unfair) classifier. The authors focus on two metrics — equality of opportunity and equalized odds. The main idea is to set the decision threshold appropriately based on the protected group and true outcome. \n\nThe proposed algorithm consists of two main steps — (a) candidate set construction, and (b) candidate selection. For candidate set construction, the authors first provide a bound that measures the probability that the fairness constraint is violated for a given threshold. Based on this lemma and a recent result from fair Bayes classification, the algorithm selects a set of candidate threshold pairs. In the next step, the threshold pair with the best empirical performance is selected as the final pair of thresholds.\n\nThe proposed algorithm is evaluated on two simulated datasets, and several standard datasets on fair classification and compared against existing post-processing based fair classifiers. The results show that the proposed algorithm (FaiR-EE) has improved fairness guarantee, but it doesn’t seem to provide any Pareto improvement in terms of the fairness-accuracy trade-off.", "summary_of_the_review": "Overall, I think the paper considers an interesting approach for designing post-processing based fair classifier. However, the main proposed algorithm has some requirements (e.g. balanced data, knowledge of $g_1$, etc). Moreover, the experimental section seems weak and suggests that the proposed approach doesn't provide right trade-off between fairness and accuracy.", "strength_and_weaknesses": "Strengths:\n- The proposed method is quite general as a post-processing method and probably can be adapted for other fairness measures as well. I also like proposition 1 which provides a bound on the fairness violation of a score-based classifier given a threshold.\n- The experimental results show improved fairness guarantees compared to other post-processing based fair classifiers.\n\nWeaknesses:\n  - I think the proposed bound only holds when the dataset is not imbalanced. This is evident in the statement of theorem 2 where the bound scales with the minimum number of samples across different group, outcome pairs. Since most of the datasets encountered in fair classification are under-represented, this is a major concern.\n- The main weakness of the paper is experimental evaluation. Table 3 shows improvement in fairness but for smaller values of $\\alpha$ (e.g. 0.08 or 0.12) accuracy is significantly lower for FairEE-EO. The same observation holds for the Compass dataset (in the appendix). This makes me think that the proposed algorithm doesn’t provide right trade-off between accuracy and fairness.\n- Most of the guarantees are in-sample fairness guarantees. The authors didn’t provide generalization guarantees even though the lack of generalization of  post-processing based methods was emphasized in the motivation.\n- Finally, in order to implement the candidate set construction efficiently, one needs to implement functions $g_1$ (from proposition 1) efficiently. It was not mentioned how these statistics can be evaluated efficiently.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "2kz1NNmZ4m1", "reviewer": "Reviewer_sJJW", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes FaiREE, a post-processing algorithm for fair classification with theoretical guarantees in a finite-sample and distribution-free manner. FaiREE can be applied to a wide range of group fairness notions, and is shown to achieve small mis-classification error while the fairness constraints. Numerical studies on both synthetic and real data shows the practical value of FaiREE in achieving a superior fairness-accuracy trade-off than the state-of-the-art methods.", "summary_of_the_review": "The paper proposes FaiREE, a post-processing algorithm for fair classification with theoretical guarantees in a finite-sample and distribution-free manner. The approach is interesting that includes candidate set construction and selection. However, the empirical performance of FairREE does not have an advantage compared to baselines. Overall, I tend to reject the paper for the current version.", "strength_and_weaknesses": "Strength:\n- The considered problem of fair classification with finite samples is relevant.\n- The approach is interesting that includes candidate set construction and selection.\n- The empirical results show that previous fair classification has limitations with finite samples.\n\nWeaknesses:\n- The empirical performance of FairREE does not have an advantage compared to baselines. For example, in Figure 1, FairBayes can achieve higher accuracy than FairREE for small alpha.\n- The motivation of considering post-processing approaches seems not enough to me. Why do you select post-processing instead of pre/in-processing methods for the finite sample setting?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "00detx9ATu", "reviewer": "Reviewer_P2N4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper aims to address one challenge in post-processing fairness mitigation algorithms: they require either distributional assumptions or access to infinite data examples. This paper presents a framework that takes in any score-based black-box classifier and outputs group-wise thresholds to correct for the fairness violations. The advantage over existing literature is it doesn’t require additional assumption on data distribution except for a minimum sample size.\n\nThere are three steps in the FaiREE framework. First, score each data example using the given black-box classifier. Second, conform a candidate set of thresholds that promise the fairness constraints. Finally, select the classifier that has the smallest mis-classification error from the candidate set. The key improvement is that the authors provide an upper bound of the probability of fairness violations and lend the upper bound to shrink the candidate set.\n\nThe FaiREE framework can be extended to multi-group fairness notions. Experiments are conducted on both a synthetic dataset and the Adult dataset to validate the effectiveness of the post-processing algorithm.", "summary_of_the_review": "I did not have the time to go over any of the proofs, but I do have some concerns that this paper is not ready for publication. I would be open to adjust my score after receiving author's response.\n\nQuestions:\n1. Does Theorem 2 require the input classifier f to be Bayes-optimal? If true, how practical is this additional assumption?\n2. The big-$O$ notation after the w.p. phrases in Theorem 2 and Theorem 4 does not make sense to me. How do you interpret the big-O inside a probability?\n3. In the experiments, the baseline methods are compared on fairness notions of which the algorithms are not designed to mitigate the violations. For example, Eq is compared on predictive equality and equalized accuracy constraints. Is it a fair comparison?\n4. In Table 2 and Table 3, the accuracy of classifiers are around 0.5. Is that informative on the synthetic dataset?\n\n---------\nThe authors have properly addressed most of my concerns and made significant improvements over the draft. In consequence, I updated the score from 5 to 6 accordingly.", "strength_and_weaknesses": "Strengths:\n- The scope and motivation of this paper is very clear. The proposed algorithm seems to be a novel work in post-processing fairness mitigations.\n- The authors demonstrate how the proposed algorithm can be extended to multi-group fairness notions, which will be useful in practice.\n- The proposed algorithm has strong theoretical guarantee to bound the error of post-processed classifier.\n\nWeaknesses:\n- The writing of this paper is not in a good shape. There are many typos. The wordings are sometimes confusing. The heavy notations make it not easy to understand the paper. In this sense, I don't think this paper is ready for publication. Please see the comments below.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster