Fair Classifiers that Abstain without Harm
Authors: Tongxin Yin
Jean-Francois Ton
Ruocheng Guo
Yuanshun Yao
Mingyan Liu
Yang Liu
Venue: ICLR 2024 poster (2024)
Keywords: Fairness
Classification with abstention
Primary area: societal considerations including fairness, safety, privacy
TL;DR: In this work, we develop an algorithm for training classifiers that abstain to obtain a favorable fairness guarantee, while simultaneously demonstrating that our abstaining process does not incur harm to each individual group's baseline accuracy.

Abstract: In critical applications, it is vital for classifiers to defer decision-making to humans. We propose a post-hoc method that makes existing classifiers selectively abstain from predicting certain samples. Our abstaining classifier is incentivized to maintain the original accuracy for each sub-population (i.e. no harm) while achieving a set of group fairness definitions to a user specified degree. To this end, we design an Integer Programming (IP) procedure that assigns abstention decisions for each training sample to satisfy a set of constraints. To generalize the abstaining decisions to test samples, we then train a surrogate model to learn the abstaining decisions based on the IP solutions in an end-to-end manner. We analyze the feasibility of the IP procedure to determine the possible abstention rate for different levels of unfairness tolerance and accuracy constraint for achieving no harm. To the best of our knowledge, this work is the first to identify the theoretical relationships between the constraint parameters and the required abstention rate. Our theoretical results are important since a high abstention rate is often infeasible in practice due to a lack of human resources. Our framework outperforms existing methods in terms of fairness disparity without sacrificing accuracy at similar abstention rates.

Published as a conference paper at ICLR 2024
FAIR CLASSIFIERS THAT ABSTAIN WITHOUT HARM
Tongxin Yin'; Jean-François Ton", Ruocheng Guo?, Yuanshun Yao", Mingyan Liu', Yang Liu?
University of Michigan
2 ByteDance Research
tyine umi ch. edu, kevin. yaoebytedanceeeeeeo com, mingyan@umiin edu, yang. 1iu01 Boytedaceecccooo
com, rguo aew com,
ABSTRACT
In critical applications, it is vital for classifiers to defer decision-making to humans. We propose a post-hoc method that makes existing classifiers selectively abstain from predicting certain samples. Our abstaining classifier is incentivized to main- tain the original accuracy for each sub-population (i.e. no harm) while achieving a set of group fairness definitions to user specified degree. To this end, we design an Integer Programming (IP) procedure that assigns abstention decisions for each training sample to satisfy a set of constraints. To generalize the abstaining decisions to test samples, we then train surrogate model to learn the abstaining decisions based on the IP solutions in end-to-end manner. We analyze the feasibility of the IP procedure to determine the possible abstention rate for different levels of unfairness tolerance and accuracy constraint for achieving no harm. To the best of our knowledge, this work is the first to identify the theoretical relationships between the constraint parameters and the required abstention rate. Our theoretical results are important since a high abstention rate is often infeasible in practice due lack of human resources. Our framework outperforms existing methods in terms of faimnsss disparity without sacrificing accuracy at similar abstention rates.
INTRODUCTION
Enabling machine learning (ML) systems to abstain from decision-making is essential in high-stakes scenarios. The development of classifiers with appropriate abstention mechanisms has recently attracted significant research attention and found various applications (Herbei & Wegkamp) [2066] Cortes et al., 2016 Madras al. 2018a| Lee et al. 2021 Mozannar et al. | 2023). In this paper, we demonstrate that allowing a classifier to abstain judiciously enhances fairness guarantees in model outputs while maintaining, or even improving, the accuracy for each sub-group in the data.
Our work is primarily anchored in addressing the persistent dilemma of the faimess--accuray tradcoff' a prevalent constraint suggesting that the incorporation of fairness into an optimization problem invariably compromises achievable accuracy (Kleinberg al. 2016). To circumvent this problem, we propose to use classifiers with abstentions. Conventionally, the chirness-accuragy tradeoff arises due the invariance of data distribution and the rigid model hypothesis space. Intuitively, by facilitating abstentions within our model, we introduce a framework that permits the relaxation of both limiting factors (distribution & model space). This transformation occurs the abstention mechanism inherently changes the distributions upon which the classifier's 's accuracy and faimess are computed. In addition, since the final model output combination of the abstention decision and the original model prediction, the model hypothesis space expands. This adaptability paves the way for our approach to breaking the aaiuuesy curse.
There exist several works that explore abstaining classifiers to achieve better faimess (Madras) et al. 2018b Lee et al., (02T). contrast, we aim to achieve the following four requirements simultaneously, y, a rather ambitious goal that separates our work from the prior ones:
Feasibility of Abstention: We need to determine if achieving faimess with no harm is feasible or not at given abstention rate.
Part of the work is done intern Bytedance.

---

Published as a conference paper at ICLR 2024
Related Works
Abstention Rate Control Multiple Fairness
Fairness Guarantee
No Harm
LTD Madras et al 20186
FSCS [ee ot al. 2021
FAN (Our work)
Table I: A summary of key properties of our work and closely related works.
Compatible with Multiple Common Fairness Definitions: We seek a flexible solution that can adapt to different fairness definitions.
Fairness Guarantee: We aim for solution that provides strong guarantee for fairness violations,
i.e., impose hard constraint on disparity.
No Harm: We desire solution that provably guarantees each group's accuracy is no worse than the original (i.e. abstaining-fres classifier.
We propose post-hoc solution that abstains from given classifier to achieve the above requirements. Our solution has two stages. In Stage I, we use an integer programming (IP) procedure that decides whether it is feasible to satisfy all our requirements with a specific abstention rate. If feasible, Stage I will return the optimal abstention decisions for each training sample. However, solution that satisfies all our constraints might not exist. To expand the feasible space of the solution, we also selectively flip the model prediction. Stage I informs how abstain the training samples; to expand the abstention (and flipping) decisions to unseen data, Stage II trains a surrogate model to encode and generalize the optimal abstention and flipping patterns an end-to-end manner.
We name our solution as Fair Abstention classifier with No harm (FAN), Compared to the prior works, our solution guarantees the four desired properties mentioned before, shown in Table To the best of our knowledge, our method is the first to develop an abstention framework that incorporates variety of constraints, including feasible abstention rates, compatibility with different fairness definition. fairness guarantees and no harm. We theoretically analyze the conditions under which the problem feasible our work is the first to characterize the feasibility region for an abstaining mechanism to achieve some of the above-listed constraints. We have carried out extensive experiments to demonstrate the benefits of our solution compared to strong existing baselines.
1.1 RELATED WORK
Fair Classification. Our work relates broadly fairness in machine learning literature (Dwork et al.
2012 Hardt et al. [0166] Kusner et al. 2017 ( Menon & Williamson| 2018 Ustun et 2019). Our work is particularly inspired by the reported fairness-utility tradeoff (Menon Williamson 2018 Kleinberg et al.) 2016). One way to resolve the problem is to decouple the training of classifiers to guarantee each group receives model that is no worse than the baseline but this line of work often requires knowing the sensitive attribute at test time and is less flexible to incorporate different fairness definitions (Ustun et al. 2019). There's a wide range approaches available to achieve fairness, including pre- pre-processing methods (Nabi & Shpitser [018 Madras et al. 2018a Luong et al.
2011 Kamiran & Calders 2012). in-processing techniques (Pleiss et al. [201] 7 Mooriea-Caapprr
al. 2019 Kim et al. | 2018), and post-processing methods (Ustun al. 2019] Agarwal et al. 2018
Kamishima et al.) 2012). Our work specifically focuses on post-processing techniques.
Abstain Classifier. Existing literature provides expansive exploration of abstention or selective classifiers (Cortes et al. 2016 Chow 1957; Hellman 1970 Herbei & Wegkamp) [0066] Geifman
& El-Yaniy 2017). Typically, selective classification predicts outcomes for high-certainty samples and abstains on lower ones, where the softmax outputs of the classifier are employed (Cordella et al.
1995 Yaniv et al. (010)). Interestingly. (Jones et al.) (2020) highlights a potential pitfall, suggesting that selective classifiers can inadvertently exacerbate faimesss problems if not used judiciously. This finding underscores the importance of careful application and has inspired various fair selective methodologies (Shah et al., 2022 Lee et al. 2021 [Schreuder & Chzhen 2021 Mozannar & Son-
tag 2020 Madras et al. 2018b). However, these methodologies primarily focus on regression or incorporate fairness constraints in their optimization objectives to create selective classifiers. For instance, LTD (Madras et al. 2018b) introduces a penalty term to address high abstention rates and unfairesss. However, it lacks robust mechanisms for controlling both abstention rates and faimess. On the other hand, FSCS (Lee et al. (202I) presents an abstention framework specifically designed to reduce precision disparities among different groups, but it does not accommodate other fairness
2

---

Published as a conference paper at ICLR 2024
R(())
271
0.9
Abstention Blook
Filp Block
4fg
Baawiin Fro
0.1
AB
0.3
Paso
Arlo) -
0.7
Nalz) m1
0.6
0.8
hA
h
No Rp Aplei 6
NA
Abwain
Ax/A)
Figure 1: Overview of FAN. We first get the baseline classifier h's confidence score on data, i.c. (zx). We then forward the confidence scores to Abstention Block AB where a model ha either tells us to abstain (i.e. h (z. 8) = 0) or to pass to the Flip Block FB (i.e. ha s) = 1). If abstained, then it is the final outcome. Otherwise, FB will decided on the unabstained samples if their predicted labels yb- = $ 2 to should be flipped or not. ý is the final outcome.
definitions. Additionally, neither of these approaches offers way monitor control the accuracy reduction for each group.
Our paper proposes a novel approach that first utilizes exact integer programming to establish the optimal classifier that satisfies all the aforementioned constraints, then trains a surrogate model on the output of said IP. The most relevant work to ours (Mozannar et al. 2023), which applies Mixed-Integer Programming (MIP) to the selective classification problem, but differs in terms of the fairness, no harm, and feasibility guarantees. Furthermore, we introduce distinctive strategies that can be deployed without requiring knowledge of the true label. These strategies involve training model based on the IP's output, which not only enhances efficiency but also substantially reduces computational requirements, especially in large-scale problems. Whereas the MIP design proposed in Mozannar et al. (023) is limited to moderately-size problems and relies on the availability of true labels at the inference time.
2 PRELIMINARIES AND OVERVIEW
Let DD be a data distribution defined for a set of random variables (X, Y),), representing each feature (e.g., application profile in a loan application), protected attribute (c.g.. gender race), and label (qualified or not in a loan application), respectively. Consider a discrete Z E Z and binary classification problem where Y
indicates the model predicts positive (i.e. to the favorable outcome) on the sample, Y = 0 indicates negative (i.e., unfavorable), and X E X. We assume training dataset sampled i.i.d. from D with N samples: (ar1æ1) y/), (I22, #2, M2), ... (NN,, 2N, WN) We aim to develop a post-hoc framework, named FAN, that takes in trained classifier h : X - (0, 1), ie.. the baseline classifier, and outputs its abstaining decisions. Denote = h(X) [o, 1] the
confidence score for individual X, and the predicted label Y, = ([) 2 to] based on a user- specified threshold to-
Figure shows the overview of FAN. We will use two modules, Abstention Block (AB) and Flip Block (FB), determine from which samples the classifier should abstain. The goal of AB is decide which samples to abstain in order to satisfy our set of constraints; the goal of FB is to expand the feasibility region of the final decision outcomes, enabling larger feasibility region of the formulated problem (see Section 3.1 for the explanation).
AB, i.e. hA* : [X, h(x)) + {0, 1}. takes the feature X of the given individual, and the corresponding confidence score S predicted from the baseline model as inputs, and decides whether to abstain the prediction. h (X, lx))) = indicates that the prediction should abstain. Samples that are not abstained by AB will be forwarded to FB. FB, i.e. he XX ((())) + (0, 1) decides whether to flip the prediction of or not, which is the final decision of FAN:
{
8o (X, =
8 8=
(I)
otherwise
3

---

Published as a conference paper at ICLR 2024
3
METHOD
We explain how we formulate the problem to achieve our goal and our two-stage algorithm.
3.1 PROBLEM FORMULATION
In general, improving fairnsss often results in decreased accuracy (Kleinberg et al. 2016). In our case, though, we enable abstention, which allows us to prioritize faimess while still maintaining accuracy, Furthermore, we desire formulation that imposes hard constraints for both fairness and accuracy, as compared to prior works that only incorporate a soft penalty term into the objective function (Madras al., 2018b Lee et 2021
Specifically, we use the following optimization problem to obtain hA, hF in our AB and FB:
min hA- RD (h(( v.) + -11-11(X,, (x,xx( # Y ha (X,4(X)) = =1]
(Error Rate)
s.t.
2) E
(Disparity)
ED hA (X, h (X)) 7 = 2 82
(Ahstention Rate)
h (x,(XX,(x))) -%) RD
(11-hx (11-Mx(X, # ha (X, =1, S
(No Harm)
where e¹3 h. 82. 1)= a "slack" we allow for the no harm constraint and is chosen such that 0 (1 + nz)e2 1.
e₂ ED [h(X)= + Y Z = 2] is the error rate of baseline optimal classifier
Error Rate. Our main objective is to minimize 0-1 loss for all samples that are not abstained.
Disparity. We enforce a faimess constraint between every pair of groups 2, 2' Z, by bounding the disparity 9 within the predefined design parameter 6. There are several fairness definitions that can be applied. In this paper, we utilize three specific fairness notions, Demographic Parity (DP) (woor et al. 2012), Equal Opportunity (EOp) (Hardt et al. 2016), Equalized Odds (EOd) (Hardi
al. 2016). Details are shown Table
Abstention Rate. Although abstention can lead to better model performance, high abstention rate can be impractical due to a lack of human resources. Therefore, is crucial to limit the abstention rate. To address this issue, we set maximum threshold for the proportion of instances that the system can abstain in each group. The abstention rate should not exceed user-specified threshold 8, for each group 2. Intuitively, this means that we cannot simply decide to forgo giving predictions on the majority the samples (or the majority from a certain group), because even though would satisfy all the other constraints it would not be practically useful. Note that to introduce more flexibility, we enable independent control the abstention rates for each group.
No Harm. We ensure the classifier does not compromise the accuracy of the groups The extent of relaxation is determined by a user-specified 77., which establishes the maximum allowable reduction in accuracy. When 1) 0, IP permits certain degree of relaxation the error rate bound for each group. Conversely, when 7)= < 0, it implies that a lower group error rate is mandated.
Why Need FB.The faimess and no harm constraints specified in Disparity and No Harm jointly impose challenging constraints for the decision rule to satisfy. For instance, the no harm constraint only allows certain predictions to be abstained, this constraint essentially requires us abstain more from wrongly predicted samples. When a classifier is relatively accurate, and when the abstention rate is constrained, we are left with only small feasibility region. The FB block opens up more design space for the abstention policy, as we flip properly, the disparity and no harm conditions could become easier to satisfy. Note that flipping model predictions is popular post hoc way of expanding the model decision space towards improving fairness (Menon & Williamson 2018). We illustrate it using the following example:
Example 3.1. Consider Demographic Parity (DP) the faireess measure, imagine system with two groups, where the allowed abstention rate is 61 = 82 = 0.1. If we set = 0.1 as the permissible the baseline classifier, the acceptance rate for group I and 2 are 0.3 and 0.7 respectively. Even if we abstain only from the positive samples in group 2, the adjusted acceptance rates would be 0.3 and 0.6 respectively, while the resulting disparity
disparity in demographic parity (DP), according
4

---

Published as a conference paper at ICLR 2024
(0.3) is still greater than However, if flipping is allowed, we can further flip 0.2 positive samples of group to negative, resulting in final adjusted acceptance rates of 0.3 and 0.4.
3.2 TWO-STAGE PROCEDURE
Directly solving the optimization problem in Sec- tion is challenging because would require joint training of a and hy. In addition, the analysis of its feasibility would also highly rely on the hypoth- esis space for learning a and hp. Lastly, the com- position of multiple sets of constraints adds to the difficulty of solving and analyzing it. To solve those challenges, we propose two-stage approach to train hA and hp. Instead of solving the inflexible and costly optimization problem on the fly, it learns the optimal abstention patterns end to end.
0.9
ha
0.3
0.7
0.6
08
Fig BAck
by
Figure 2: Illustration of the two-stage design.
Stage I: Integer Programming. For a dataset with N individuals, the goal of Stage is to learn two N-length vectors: w = JN and f J.f.Jr which represent predictions of h ( h(X)) and (X,, h(X)) on this dataset, respectively. In other words, Wn h (zx)) E {0, 1), and fn = ( h((n)) 10,
N
min
Σ Wp 1[ # uol =
Σ
wa [(0tm (1 - (n) + (1 (n,) + yn]
(IP-Main)
w./
s.t.
< 8, Vz, E
(Disparity)
Σ mml Wp 11/2 =2
N
2 -21-66)
(Abstention Rate)
Em 1[2n
Σ Wn 1[in * you 3n = 2}{
Σ Wn 1|2n = 2] . Je
(No Harm)
Wh E f. E {0, 1),
Solving it gives us the abstention (i.e. w) and flipping decision (i.e. f) for each of the training data. The empirical version of the (Disparity) constraints can be found in Table 4 in the Appendix.
Stage II: Learning to Abstain. Although IP results offer an optimal solution for the training data, they are not applicable at inference time. This is due to two main reasons. First, accessing the ground truth label y is impossible during inference, which is a necessary input for IP. Second, solving IP is too consumnng to perform during inference. To solve this problem, we train surrogate models to learn the abstaining and flipping patterns in end-to-end manner (i.e. from features to abstention and flipping decisions). We use the IP solutions (on the training samples) as the surrogate models' training data, and we want the surrogate model to generalize the patterns to the unseen test samples. Figure 2 illustraaee our design and we will describe the details in Appendix B
Note that we only need to solve IP-Main and train surrogate models during the training process, and when we deploy FAN, we only need to run inference on the trained AB and FB, and therefore the inference overhead is small.
4 THEORETICAL ANALISIS: FEASIBILITY AND FAIRNESS IN ABSTENTION
The selection of design parameters (including 82, M2. plays crucial role in training AB and FB, therefore the overall performance of F FAN. A higher level of disparity restriction can intuitively result in higher rate of data samples being abstained from classification, while more stringent accuracy requirement can also increase the abstention rate and make the problem infcasible. In this section, we focus on theoretically analysis of Stage Specifically we answer the following research questions:
"To keep the example simple, we do not consider accuracy here. While in our formulation, Error Ratelande No together ensure that flipping would not cause harm but rather incentivize improvements accuracy.
5

---

Published as a conference paper at ICLR 2024
Under what conditions will Problem [P-Main become feasible for each fairness notion? What is the relationship between the design parameters?
We derive the feasibility condition for the IP formulation (P-MMiin) in Stage I. The task of theoreti- cally bounding the performance gap between predictions (surrogate models in Stage II) and ground truth (IP solution in Stage I) is generally challenging the models are neural networks, therefore study it empirically Section
We summarize the key parameters used in this section:
dz Abstention rate allowed for x
1]=
Tx (TBD 4.1)
Fairness Disparity
Error rate by
Error rate slack restrictiveness compared to baseline
Qualification rate of group
4.1 FEASIBILITY
Define T2 En, 1/an=alun the proportion of qualified individuals of group 2, i.c., qualification rate of [|=_
group 2. We prove the following results for demographic parity:
Theorem 4.1. (Feasibility Demographic Parity (DP)) IP-Main is feasible under DP if and only
V2 E Z such that Ts 2 T2
88 221- 1+ + (1 +11+10 72 +
1/
Theorem 4.1 demonstrates the feasibility of the IP to achieve Demographic Parity. Specifically, the theorem establishes the minimum value 8₂ that is allowed, subject to upper bounds on disparity and relaxation parameter for the eπror rate. This highlights the importance of abstention by the more qualified group (higher qualification rate) for achieving fair model without compromising accuracy, while the less qualified group need not abstain. Later in Section 4.2 we provide further treatment to remedy the concern over an imbalanced abstention rate.
Specifically, for the values of 7/= and 7/z will lead to smaller values of 8z, indicating that a relaxation of the error rate can allow the more qualified group abstain from fewer samples. Additionally, looser bound on disparity will also enable the more qualified group to abstain from fewer samples. In practice, determining an appropriate value of is of paramount importance. To this end, we present the following illustrative example.
group scenario (2 (z, 2)). results demonstrate that increasing the
Example 4.2. a) If = Tz i.c., the dataset is balanced, and (1 + m=)es < 1, we have that 1 ++t+(11+=eee T= < 0, therefore the problem is always feasible. b) Ts - = 0.3, 1- 1-(1+
Eg cg = 0.1, 71 1l2 = 0, when e = 0.05, 83 > 0.056; when E = 0.1, 6g has no restriction.
Further for Equal Opportunity and Equalized Odds we have the following results:
Theorem 4.3, (Feasibility of Equal Opportunity (EOp)) PPMMain is always feasible under EOp.
Theorem 4.4. (Feasibility of Equalized Odds (EOd)) PPMain is always feasible under EOd.
Theorems 4.3 and demonstrate the feasibility of the under Equal Opportunity and Equalized Odds. Specifically, regardless of the design parameters' values, our results indicate that feasible solution to the problem always exists. Notably, our results imply that even when the abstention rate is O, the IP can solely adjust the flip decisions fa to satisfy constraints disparate impact, abstention rate, and no harm. More discussion on this can be found in Appendix
4.2 EQUAL ABSTENTION RATE
An objection may arise that the model's excessive abstention from a particular group, while not abstaining from others. Moreover, if such abstention occurs solely on data samples with positive or negative labels. further concerns may be raised, In this section, we delve into a scenario where differences in abstention rates across groups and labels are constrained. We show that under equal abstention rate constraints, the performance of IP will become worse (higher overall error rate)

---

Published as a conference paper at ICLR 2024
compared to Problem IP-Main
min w.f
IP-Main
(3)
Σ n= Wn 120 = 2 = vl
En We = Mn v/
s.t.a.
S oy, V2, E Z, E {0, 1}
1(z 2,
Σx=1 1[zm =2, yn y]
Theorem 4.5. (Feasibility of Demographic Parity with Constraint Disparity of Abstention Rate)
sufficient condition for Problem 3 being feasible is V2, 2 E 2 such that T= T2)
1 + + 7/2 e= Tz Tz (1 + 7=)02
8g S T:01, T201,
62 2
We similarly show that for Equal Opportunity and Equalized Odds the problem remains feasible even under equal abstention rate constraints. We defer these details to Appendix.
5 EXPERIMENTS
In this section, we evaluate FAN using various real-world datasets, comparing it against baselines and to better understand its components. We start by explaining our experimental settings and then move on to how FAN performs in comparison to other methods. We also analyze the separate components of FAN to get clearer picture of how each contributes the overall performance. Additionally, we compare our trained models, specifically AB and FB, with integer programming (IP) solutions.
In our study, we primarily focus on setting involving only two distinct groups. We set the same abstention rate across all groups, i.e., 8_ = 8. F FAN is evaluated against two baselines: LTD (Madras) al. 2018b) and FSCS (Lee al.) (02T). shown in Table [ For LTD, we employ the learning-to reject framework, specifically referring to Equation 4 in (Madras et al. 201 We adopt three real-world datasets: Adult (Dua & Graff, 2017). Compas (Bellamy et al. 2018), and Law (Bellamy) al.) 2018). During training, Equalized Odds incorporate two separate constraints, while to facilitate a straightforward interpretation, the average disparity is shown. The details of data preprocessing and model setting can be found in Appendix E
Baseline Optimal. For FAN, we use an optimal classifier trained solely to minimize the loss as the baseline h, naming it "baseline optimal". We use Multi- Perceptron (MLP) to train baseline optimal, AB, and FB. Details can be found in Appendix E Table Appendix shows the performance of the baseline optimal model both the training and test datasets (including overall accuracy and group accuracy, along with disparities measured under DP, EOp, and EOd.) Specifically, the overall training accuracy on Adult, Compas and Law are 92.08%, 72.33%, 82.86% respectively.
Overall Performance. Figure 3 illlutraate how FAN compares to LTD and FSCS across different datasets and abstention rates. In the LTD method, abstention is introduced as a penalty term in the objective function, making it difficult to precisely control the abstention rate. To work around this, we adjust the penalty term's coefficient and chart the resulting actual abstention rate. The first row of the figure highlights the disparity reduction each algorithm achieves compared to the baseline optimal h. The second row shows the minimum increase in group accuracy for all groups. Generally, FAN yields the most significant reduction in disparity without sacrificing much accuracy, unlike FSC5 and L,DD, which focus more on fairness at the cost of accuracy. Using the no-harm constraint No Harm FAN often matches or even surpasses the bascline optimal classifier in terms of accuracy. Nevertheless, there are a few instances where accuracy slightly drops, which we discuss further below.
Stage II Analysis: Performance of Surrogate Model. The no-harm constraint is imposed to encourage FAN to maintain or even improve group- accuracy when compared to the baseline. The integer programming formulation in Equation [P-Main] is designed to strictly satisfy this constraint. However, FAN may not strictly meet this due to the surrogate model training of AB and FB in what refer to Stage II. As seen in the second row of Figure 3 there are instances where accuracy slightly decreases. Table provvides insights into this by illustrating the training accuracy of AB and FB. This suggests that the surrogate models are effective learning from the IP outcomes. Figure 17 also shows the loss of AB and FB on Adult t under Demographic parity, as an example.
'Code: https: / /t///g/tttt gigtttth thu.. ccm/tsy 1 9/FAN
-learmeng-to-dcfer schema requires an additional Decision Maker, which does apply to our focal scenario.
7

---

Published as a conference paper at ICLR 2024
Disparity Reduction
0.1
Disparity Reduction
Disparity Redurtion
0.15
0.0
0.15
0.10
FSCS
FAN
0.10
0.2
FSCS
0.05
FSCS
0.3
0.05
FAN
FAN
0.0
0.3
0.1
0.3
0.1
0.2
0.3
0.0
Increase in Accuracy
Increase in Accuracy
Increase in Accuracy
-0.05
00.
-0.10
-0.1
-0.15
FSCS
-0.20
FSCS
-0.2
FSCS
FAN
-0.25
FAN
FAN
0.0
0.1
0.2
0.3
0.0
0.1
0.2
0.0
0.1
0.2
0.3
(a) Adult, BOd
(b) Compas, DP
(c) Law, DP
Figure 3: Comparison of FAN with baseline algorithms. The 1st row depicts disparity reduction, and the 2nd row presents the minimum group accuracy increase, both compared to baseline optimal. (a) Evaluation on the Adult t under Equalized Odds. (b) Evaluation on the Compas under Demographic Parity. (c) Evaluation on the Law under Demographic Parity. For FAN, is set to O.
Adult EOp
Compas EOp
Law EOp
Accuracy (%)
DP
EOd
DP
EOd
DP
EOd
AB
94.23
93.29
93.55
90.26
90.32
95.22
96.09
91.42
92.03
5 = 0.1
94.26
94.01
94.54
79.87
79.57
76.15
88.12
91.38
90.14
AB
92.20
89.93
88.48
82.94
90.32
91.44
96.12
95.75
92.11
5 = 0.2
FB
97.79
95.33
95.86
86.07
79.63
77.03
87.90
87.90
90.29
AB
89.94
87.42
87.43
80.28
79.99
82.82
86.50
86.39
94.82
5 = 0.3
FB
97.18
96.31
96.33
87.72
88.55
85.53
93.00
93.92
88.17
Table 2: Performance Evaluation of Surrogate Model Training. We use MLP as the network structure for both AB and FB. Each cell displays the average training accuracy (from 5 individual runs) of AB (first row) and FB (second row) for specific ó, fairness notion, and dataset employed. Generally, both AB and FB demonstrate strong ability learn the IP outcomes effectively and achieve high accuracy, underscoring the success of Stage II. It is worth mentioning that, under some settings, the accuracy on the Compas low, for example the training accuracy with abstention rate 0.1 is 76. 15%. However, the issue lies not with our Stage II design but rather with the limitations of the MI.. demonstrated in Table [ the performance of the baseline optimal classifier (training accuracy 72.33%) on the Compas is also low.
under EOd on Compas
Comparison to Baseline Optimal Classifier. We conduct comprehensive set of experiments to examine the impact of FAN on both disparity and accuracy. Figure 4 depicts the performance metrics when applying EOp on the training and test data for the Adult dataset. These results offer comparative benchmark against the baseline optimal classifier ht assessing how FAN enhances model performance regarding fairness and accuracy. The figure shows FAN successfully optimizes for equitable model without sacrificing accuracy. Notably, as the permissible abstention rate (8) increases, both groups experience a significant improvement accuracy, while simultancously reducing the overall disparity. These findings indicate that FAN has the ability train models that are both fairer and more effective, particularly when higher levels of abstention are allowed.
All constraints strictly satisfied. As increases, the impact on reducing disparity diminishes due to the inherent allowance for greater disparity in the IP formulation. As increases, the accuracy improvement for both demographic
IP Solution. Figure the IP solution corresponding Figure 4
8

---

Published as a conference paper at ICLR 2024
Disparity Reduction
Accuracy
Increase In Accuracy
0.05
0.085
0.04
0.03
0.04
0.03
0.03
0.004
0.01
0.02
0.02
0.00
0.03
-0.01
0.01
0.01
0.015
0.00
0.1
0.2
0.3
-0.02
0.00
0.1
0.2
0.3
0.002
0.00
0.0
0.1
0.2
0.3
Disparity
Increase in Accuracy
Increase Accuracy
0.05
0.18
0.18
0.0090
0.020
0.04
0.0085
0.04
0.015
0.03
0.12
0,0075
0.02
0.02
0.0070
9.08
0.01
3.06
0.0
6.1
0.2
0.5
0.0
0.1
0.2
0.3
0.0
0.1
0.2
0.3
(a) Disparity, EOp
(b) Accuracy, Group
(c) Accuracy, Group 0
Figure 4: Disparity reduction and increased accuracy for each group performed Adult, compared to baseline optimal. The first row shows the performance on the training data while the second row is on test data. (a) demonstrates the disparity reduction in terms of EOp, while (b) and (c) showcase the increases in accuracy for both groups. x-axis represents ó, while y-axis represents e.
0.05
Disparity Reduction
Increase in Accuracy
0.05
Increase Ac Accuracy
0.057660
9.0124
0.04
6.8
0.84
0.09/853
0.05
0.03
0.01240
0.057650
0.52
0.01238
0.02
0.097645
0.01
0.01
0.01
0.097660
0.51
0.412M
0.00
0.00
0.00
0.097635
(a) Disparity, EOp
(b) Accuracy, Group
(c) Accuracy, Group
Figure This figure illustrates the result of the solution, under the same setting of Figure
groups stays stable across configurations, mainly due to already nearing optimality in this experiment. Comparison between Figure 5 and Segure[unnerseeeee the successful learning of the IP solution by the AB and FB models in the second stage.
CONCLUSION & DISCUSSION
In this work, we develop an algorithm for training classifiers that abstain to obtain a favorable faimess guarantee. Simultaneously, we show that our abstaining process incurs much less harm to each individual group's 's baseline accuracy, compared to existing algorithms. We theoretically analyzed the feasibility of our goal and relate multiple system design parameters the required abstention rates. We empirically verified the benefits of our proposal. Interesting future directions for our research involve extending our method beyond binary classification tasks to encompass multi-class scenarios. Preliminary considerations suggest transforming the problem into series of binary classification tasks, with additional design required to refine the flipping mechanism. Another avenue is to include human subject study, incorporating human annotation for abstained samples into the performance evaluation. Additionally, exploring the reduction of constraints could further reduce computational complexity, providing valuable insights for future developments.

---

Published as a conference paper at ICLR 2024
REFERENCES
Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna Wallach. A reductions approach to fair classification. International Conference on Machine Learning, pp- 60-69, PMLR, 2018.
Rachel KE Bellamy, Kuntal Dey, Michael Hind, Samuel C Hoffman, Stephanie Houde, Kalapriya Kannan, Pranay Lohia, Jacquelyn Martino, Sameep Mehta, Aleksandra Mojsilovic, et al. Ai fairness 360: An extensible toolkit for detecting, understanding, and mitigating unwanted algorithmic bias. arXiv preprini arXiv: 1810.01943, 2018.
Chi-Keung Chow. An optimum character recognition system using decision functions. IRE Transac- tions on Electronic Computers, (4):247-254, 1957.
Luigi Pietro Cordella, Claudio De Stefano, Francesco Tortorella, and Mario Vento. A method for improving classification reliability of multilayer perceptrons. IEEE Transactions on Neural Networks, 6(5): 4441114, 1995.
Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri. Boosting with abstention. Advances in Neural Information Processing Systems, 29, 2016.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http:ht/ttcchheeeee
ics. uci edd/ml
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pp. 214-226, 2012.
Ran El- Yaniv al. On the foundations of noise-free selective classification. Journal of Machine Learning Research, 11(5), 2010.
Yonatan Geifman and Ran El-Yaniv Yaniv. Selective classification for deep neural networks. Advances in neural information processing systems, 30, 2017.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29, 2016.
Martin E Hellman. The nearest neighbor classification rule with reject option. IEEE Transactions on Systems Science and Cybernetics, 6(3):199-185, 1970.
Radu Herbei and Marten H Wegkamp. Classification with reject option. The Canadian Journal of Statistics/La Revue Canadienne de Statistique, pp. 709-721, 2006.
Erik Jones, Shiori Sagawa, Pang Wei Koh, Ananya Kumar, and Percy Liang. Selective classification can magnify disparities across groups. arXiv preprint arXiv:2010. 14134, 2020.
Faisal Kamiran and Toon Calders. Data preprocessing techniques for classification without discrimi- nation. Knowledge and information systems, 33(1):1-33, 2012.
Toshihiro Kamishima, Shotaro Akaho, Hideki Asoh, and Jun Sakuma. Fairness-aware classifier with prejudice remover regularizer. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2012, Bristol, UK, September 24-28, 2012. Proceedings, Part II 23, pp. 35-50. Springer, 2012.
Michael Kim, Omer Reingold, and Guy Rothblum. Fairness through computaaionaaly-bounnee awareness. Advances in Neural Information Processing Systems, 31, 2018. 88
Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs in the fair determi- nation of risk scores. arXiv preprint arXiv:1609.05800 2016.
Matt Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. Counterfactual faimness. Advances in neural information processing systems, 30, 2017.
10

---

Published as a conference paper at ICLR 2024
Joshua K Lee. Yuheng Bu, Deepta Rajan, Prasanna Sattigeri, Rameswar Panda, Subhro Das, and Gregory W Wornell. Fair selective classification via sufficiency. In International Conference on Machine Learning, pp.
PMLR, 2021.
Binh Thanh Luong, Salvatore Ruggieri, and Franco Turini. k-nn an implementation of situation testing for discrimination discovery and prevention. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 502-510, 2011.
David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Learning adversarially fair and transferable representations. In International Conference Machine Learning, pp. 3384-3393. PMLR, 2018a.
David Madras, Toni Pitassi, and Richard Zemel. Predict responsibly: improving faimess and accuracy by learning defer. Advances in Neural Information Processing Systems, 31, 201 8b.
Aditya Krishna Menon and Robert C Williamson. The cost of fairness in binary classification. In Conference on Fairness, accountability and transparency, pp. 107-118. PMLR, 2018.
Hussein Mozannar and David Sontag. Consistent estimators for learning to defer to an expert. In International Conference on Machine Learning, pp. 7076-7087. PMLR, 2020.
Hussein Mozannar, Hunter Lang, Dennis Wei, Prasanna Sattigeri, Subhro Das, and David Son- tag. Who should predict? exact algorithms for learning to defer humans. arXiv preprint arXiv:2301.06 2023.
Razieh Nabi and Ilya Shpitser. Fair inference on outcomes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018
Alejandro
Michiel A Bakker, Bernardo Garcia-Bulle, and Alex'Sande Sandy' Pentland. Active fairness in algorithmic decision making. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, pp. 77-83, 2019.
Geoff Pleiss, Manish Raghavan, Felix Wu, Jon Kleinberg, and Kilian Q Weinberger. On faimess and calibration. Advances in neural information processing systems, 30, 2017.
Nicolas Schreuder and Evgenii Chzhen. Classification with abstention but without disparities. In Uncertainty in Artificial Intelligence, pp. 1227-1236. PMLR, 2021.
Abhin Shah, Yuheng Bu, Joshua K Lee, Subhro Das, Rameswar Panda, Prasanna Sattigeri, and Gregory W Wornell. Selective regression under fairness criteria. International Conference on Machine Learning, pp. 19615. PMLR, 2022.
Berk Ustun, Yang Liu, and David Parkes. Faimess without harm: preference guarantees. In International Conference on Machine Learning, pp. 6373-6382, PMLR, 2019.
Decoupled classifiers with

---

Published as a conference paper at ICLR 2024
A
FAIRNESS NOTION
Fairness Notion
9
Demographic Parity
P(ř 1/2 2) P(Υ 1|2 2')
Equal Opportunity
P( 1|Y 1 2) P( 1 1,2 =2
P(Ý 1 1, 2) P(У 1 1,2 2')
Equalized Odds
P(Y- 0|Y 0, Z
P(Y OJY 0,
Table 3: Fairness notion utilized for Constraint Disparity Demographic Parity (DP) (Dwork et al. 2012). Equal Opportunity (EOp) (Hardt et al. 2016).
We utilize three specific fairness notions,
Equalized Odds (EOd) (Hardt et al. 2016).
Fairness Notion
8
Demographic Parity
F Wy Ion -0 =
MN
[
2n wi 1Br
8
Equal Opportunity
ا 2 -1
We 1
N
Σn 1/2n -s yy -..
E
Du up
En un 160n 1,9m 1.pmm
Equalized Odds
-1-1 -,,,
--- 1/2 =z' =1]
E
Σ> we 10, 2ii 10=
Σ [b =0, =0,
Σ 1/2 =x vx
Table 4:
The emperical version of fairness notions utilized for Constraint Disparity in IP-Main
Tables Jand display the formulation of three fairness notions we have adopted. It's worth mentioning that all fairness measurements are not conditioned on h This means that fairness is measured across the entire dataset, not just for non-abstained samples. We now provide an example of Demographic Parity (Disparity of accept rate) to demonstrate why we take this approach.
Example A.1. Consider a group with an acceptance rate of 0.3 from the baseline classifier. If FAN abstains at a rate of 0.1 on samples with negative predictions, our measurement of the acceptance rate, not conditioned on abstentions, should yield a unchanged acceptance rate of 0.3. However, condition it on non-abstentions, the new acceptance rate should be 0.3/(0.3 + 0.6) z 0.33. The former is a more valid measure than the latter, as it takes into account the presence of abstained samples still in the system and the abstention on the negative samples should not impact the accept rate.
B DETAILS OF TWO-STAGE TRAINING
Solving Problem IP-Main provides us with two N-dimensional vectors, namely w and f. The vector denotes whether abstain from predicting for every input in the training data, while the vector represents whether the final prediction ý needs to be flipped compared to the bascline optimal model h. As we have illustrated in Figure 2 we will utilize w and f as labels, paired with X, Y as training features, train the Abstention Block hA (X, h(X)) and the Flip Block hf (X, ((X)).
B. ELIMINATING RANDOMNESS OF IP OUTCOMES USING PREDICTION ADJUSTMENT
Although IP provides optimal solution in terms of and f, this section discusses the non- uniqueness of this solution in most cases. As a result, randomness can affect the ability of AB and FB learn IP decisions effectively.
The input of IP is z, y, 8. The way IP uses confidence score is mapping it to ft = 1(s 2 4g). Note that IP is not using the feature x directly. Instead, the information of x is captured by ÿt. Therefore the IP solution exhibits a certain degree of randomness. Specifically, the IP model does not differentiate between data samples with identical labels and optimal predictions, if they belong to the same group (i.e., /1 = y2, D61 = 062, 21 22). If the decisions for two samples xi and 22 are interchanged, the resulting solution would still be optimal for IP. This characteristic can hinder the complete capture of feature information and adversely affect the performance of model training for AB and FB. We provide an illustrative figure for this observation Figure 7a
12

---

Published as a conference paper at ICLR 2024
To mitigate the effects of randomness in the IP solution, a Prediction Adjustmentt (PA) step is incorporated after solving the IP and before the model training, outlined in Algorithm| and illurstrated in Figure 6 The core idea of PA is that abstain from predicting those with the low- est confidence scores predicted by the optimal classifier according the optimal fraction we learned from the IP solver. Of the remaining, we further select the samples with the lowest confidence scores for flipping B). Sam- ples with the highest confidence scores, on the other hand, will remain unaffected by this process. This approach is founded on the premise that the highest confidence scores correspond to the most certain predictions made by the optimal classifier. Therefore, it is prudent to prioritize abstaining and flipping those with lower confidence scores first. Specifically, for each (y. 0b, 2) tuples, PA procedure takes the following steps:
&
==
0.8
0.75
0.6
0.56
abstendon
Figure 6: Illustration of Prediction Ad- justment.
Count the number of individuals that have been abstained, i.e., no E: 1ww; = 0]: the number that has not been abstained but the decision flipped, i.c., R111 = =>,, 1, fx
Sort the individuals based on their confidence score predicted by baseline optimal h.
Abstain no individuals with lowest confidence; for the rest, flip the decision of 711 individuals.
Algorithm Prediction Adjustment
Input: (r, 2), 0b, h,w, for E do
for y1 {0. 1} do
for y2 E {0.1] do
(x, V. w. f) contains all data samples with 2, a, Un V1, H6,n V2-
For all data samples with w,, O, set Jn 0.
711 = number of the data samples with wn = 1, fn 1.
R10 number of the data samples with wn 1, fn O.
Ro = number of the data samples with wh, = O.
Compute the confidence score h(z).
Adjust w. f: With increasing in confidence score, reassign data samples with wn 0,
nio samples with w,, 1, fn nu samples with wn 1, fa 1, sequentially. end for end for end for
Return w. f-
Robustness: Prediction Consistency. The Prediction adjustment technique not only mitigates the randomness introduced by the Iterative Pruning algorithm but also preserves prediction consistency when changes made to the training data. In practical scenarios, when new data points are added to the training set, sampled from the same distribution D, they are expected to be distributed proportionally across all regions guarantees that the labels of the original data the training set remain unchanged while incorporating the new data points. For experiment verification of Prediction Consistency see Appendix E
illustrated in Figure [bb The Prediction adjustment policy
13

---

Published as a conference paper at ICLR 2024
Group z
Group
t6 =
ú =
9b 1
1/ 0
y
w-//=1
y
mma
und
==
==
(a)
(b)
Figure 7: Illustration of the Non- Uniqueness of IP Solutions (a) and prediction consistency Concept (b): (a) The figure depicts the inherent randomness of solutions. For a given group 2, IP can only observe the ground truth label y and the predicted label ýb- Hence, for instances with the same y and lr.. cannot differentiate between them. For example, swapping the decisions # and 22 yields new optimal solution. (b) This figure depicts the concept of prediction consistency, wherein newly sampled data, obtained from the same distribution as the original data, are incorporated into the training set. Given that the newly sampled data independent and identically distributed (iid), they are expected to be distributed proportionally across all regions. The Prediction adjustment policy employed to ensure that the labels of the original data remain unchanged.
B.2 LINEAR INTEGER PROGRAMMING
In Problem IP-Main the presence of quadratic terms in the form of Unwn incurs higher computational costs and renders the problem more difficult solve than linear IP. In this section, we present methodology to transform Problem IP-Main intoo an equivalent linear IP problem. To achieve this, we employ McCormick envelopes and define U, Unwn. Since In and wn, are binary, the following set of linear constraints can be used to represent Un:
Un 2 0 S Wn Un S hn (1 01)(1 w.) 0 <> Un 2 Hn
Uh = Un +
(5)
Wn
Intuitively, because we are in the binary setting. we are able to turn a quadratic optimization problem into a linear one. It is important to note that Equation 5 does not introduce any relaxation. Moreover, all the constraints Equation 5 are linear. Thus, we can replace all the quadratic terms in Problem
IP-Main with un and incorporate the linear constraints specified in Equation 5
C NON-TRIVIALITY
At the end of Section our results indicate that a feasible solution to the IP problem always exists for equal opportunity and equalized odds, regardless of the design parameter values. Notably, our results imply that even when the abstention rate O. the IP can solely adjust the flip decisions fa to satisfy constraints disparate impact, abstention rate, and harm. This is because IP has access to the true label y.
However, this causes problem. For example, to achieve a "perfect" classifier, IP doesn't 't abstain from individuals but only flips the decision of 96 to make the final outcome exactly equal to y, resulting 100% accuracy across all groups. Additionally, the true positive rate and true negative rate will both be 100%, eliminating any disparities. However, such "perfect" classifier is trivial. It requires strong FB to memorize the flipping decision. To eliminate such trivial solutions, more reasonable approach is to ensure that the IP solution is no better than the optimal classifier
h arg min Ep (D(C(((X))Y) NER
(6)
without considering abstentions.
14

---

Published as a conference paper at ICLR 2024
We introduce non-triviality constraint to the IP with Equal Opportunity example:
min w
IP-Main
(Equal Opportunity)
S.L.a.
10 * Un: =
Σ 1[an = =1
Co,,, Vz E 2
(Non-triviality)
Here Co.s is the error rate of the optimal classifier for group z. above s.t.a. stands for "subject to additional" constraints. The non-triviality constraint enforces realistic requirement that flipping module alone should not lead to a higher group accuracy compared to the optimal classifier. We prove the following theorem:
Theorem C.1. When the baseline optimal, i.e., h hos ifr all E 2,e, ez S Tz, T2 6)
(1 (1 S 1, and O. problem is feasible.
D PROOF
D.1 NOTATIONS
For simplicity, introduce some notations that will be used in the proof. Figure illustrates the distribution ratios different regions of two groups
Group 0
Group 1
tu (w
1,9
rin (w1-)
==1
(w
rl fw = 0
Aio : (w 1,9 0)
ruu (w 1,0 11
(w 0)
the - 1,9 1)
== 0
(w= 0)
r (w 1,9
rho = 1,9
Figure 8: Division of individuals into four regions based on their sensitive attribute and label. The ratio, denoted as r Fijk, represents the proportion of individuals of group with specific combinations of = i, w = j. and ý = k. For w = O, define r 1000 + roi- By definition, rin + rho + río rōu1 + r + rō0 r (rin, rfio- rio ro r000:000
holds true, ensuring the sum of all ratios within group is equal to one. Define
Note that e = (1 + nh ee. For notation simplicity, define a' = e's.
D.2 PROOF OF LEMMA D.
Lemma D.1. Under fairness notion Demographic Parity Equal Opportunity, if Problem MP-Main feasible, there must exist solution such that the resulting classifier does not abstain any samples with label 0, for all such that yn. 0, holds that wn. 1.
Lemma D.I indicates abstaining data samples with label 0 are not required by IP.
Proof. Without loss of generality. we consider group 0. Since Problem IP-Main is feasible, there
exist a 0 that Constraints Abstention Rate Disparity
hold.
15

---

Published as a conference paper at ICLR 2024
Constraint No Harm can be written
110 + 2011 S Eo + df(0210 +ron) S <6(r +
(8)
70 r0n1 + 010
111
Constraint Abstention Rate can be written as
0 + r0o - 60
(9)
For Demographic Parity, constraint Disparity indicates
iu ron - S riu + ro1 S riin + rōn + +
(10)
If the feasible solution 700 > O, define ru1o = r010 + Too. 700
or
O, then it's not hard to verify that
constraints and 10 still hold for ruio and rou 0. r0o
indicates abstaining individual
with label O.
For Equal Opportunity, constraint Disparity indicates
rin
7
ri11
S
+ t,, V2
(11)
Tz
70
Tz
Similarly, if the feasible solution r define 7010
9 + -000- 00o then it's not hard to
verify that constraints 8 and 11 still hold for and noo = 0. T00
Or
or
indicates abstaining no
individual with label 0.
D.3 PROOF OF THEOREM
By Lemma D.1 have Problem MP-Main feasible iff there exist solution that rōo 0, Vz.
For any two group 2 = 0, 1, without loss of generality, assume T S To- Define Ar = To Ti.
Similar to 9 8 and 10 the constraint of IP-Main can be written
0
T0o0 - AT - <<
r010
0
0
AT + 8
1 V010
111
< 61 ri
110 < 5g
df + < 66(r)) + r
df +ru)) (r +r
(12)
H + +r =
r +r 0 = To
rom + +r =1 T1
Tow rou + fu -
r r 2 0
Let r/n = - Ti T/ 70
Tp - - 11o = Ti - 7 T00 10
5o
0
111
-
12
becomes
16

---

Published as a conference paper at ICLR 2024
'i1 r010
AT - 111 To10
"i1
Ar + 8 .i11 1
100 2 61
r - 60 ih + afri0 + r0o 2 aj
Ii + 46 10 + + 2 %
(13)
i + STI I11 + r S T0
To1o S 11-T1 T1 - - TO
Piu T1: 010 T11 10 010 2 0
Extract the condition of r1 from 13
we have
0 0 rio S 81
d r010 - rlu
Tio
d'
(14)
r1o In rin
To let 14 feasible, the following additional inequalities need to be added to 13
d
m00
rin
S6
a1
a
T000
rin
(15)
S TI-
rin
0 S
rhn
Similar requirements hold for group 0. Thus,
rin T010 AT 8 8 ri11 010
Phn T010
AT + E 2 ri1
1010
r1o
T1
0 $ 1 TO
T010 + m111
0
de(1 5u)
Bs is feasible +
1 + +
2 d/(1 m))
(16)
ri S
d + 1
d{ - -5)
er + 1010 2 d1 -7) 71)
111 $ m
Th T1o Im 1010 20 0
Further extract conditions of 0 -0 have
17

---

Published as a conference paper at ICLR 2024
7010 S 1 f1
A S T 1 + + 2 d 61)
Gri + + 2 d -m)
rin S n
1 is feasible +
I -1-7+ 1 +
(17)
2ri11 2 40(1 - 60) + Ar - -
i 2 ()) -0 -1
(1 + c6)r 2 dg(1 To) + Ar A - 010
in11 2 År - To1o
rin 7000 0 2
Extract conditions of ri we have
1 S 1 T Thn + r/n d 81)
ef + 1000 2 d((1 - -m)
r 11 $ In +
| - 1
13
feasible <
(18)
1111 - T0n0
1
To + - - dj
2
To + TI
+ 1)e - 25 r r010
6
ih rh10 2 dl(1 6n) + To + - -2 -
A r01 20 0
Define r = r|u + rdio: r1 = =rlu rolo- then we have 0 0 1 1, n - 1 s m s..
r 2 df (1-
r! 2r + -
s(++<(1+))r - 20 (1 - -T)
r 52-
r +8- 06
13 is feasible +
(19)
r 22 t 7 - -
2
+ +1) -
r 2 26(11 60) + T0 + π - 2 -
r! 1
r1 -
Extract conditions of rl, we have
18

---

Published as a conference paper at ICLR 2024
r 2 0
r4 2 4 (1- t0
+ +1 - - r 2 de (1- 50) + At -
1+ 2
K is feasible e
(20)
r r a 71)
42 To
r4 52+ do (1 500 AT
K feasible e db (1 - 60) + AT s1+E+e
(21)
Thus, if for any two groups 2, 2' E Z such that T= 2 T2,, d' (1 6.) + TT= -=- 11+ holds, then Problem IP-Main is feasible.
D.4 PROOF OF THEOREM 4.3
Proof. Similarly, for any two groups 0, the constraints of Problem PP-Main under Equal Opportu- nity are
riu
riu
ii11
To
71
To
rio S 81
1 < 60
71 - ej S ri ta'rio
(22)
Tu - 6 S ri + 0
in + r1 ST
M + 0 1 T 0 Tu 110 - 1 2 0
Extract the conditions of rlo and rf-- we have the following equivalent constraints:
TH I (1 + +e)
1 Ti S ml +e)
Tm 2 π. é d STi
(23)
TO
TI Tin 2 - c d ETO
To -
0 0 5
0 0 m Sn
To let the above feasible, we need
(TI - e - díō - -ET
< To
T1
(24)
(To
eg d ETO)TT
S Ti
To
24 always holds. Thus, Problem IP-Main always feasible under Equal Opportunity.
19

---

Published as a conference paper at ICLR 2024
D.5 PROOF OF THEOREM 4.4
Proof. Under Equalized Odds, for any group 2, let rfu = Ts, 1e,7ju 0, rio 0,
= 0, r,10 =
roo O, then verify that all the constraints of Problem IP-Main hold.
D.6 PROOF OF THEOREM C.1
For any group 1, the constraints Problem 7 are
Iiu es riu To
'111 +e
7
TD
rloi + +r000 + 0000
+ 0001
S 81
111o + +
S e
Tho + riu + Tmn + 010
(25)
rho + 100
el
the +ro rio
1000 T1
ron + + + roo0 001
T1
20
where group 0 represents any group other than group
If 25 feasible, there must exists solution such that rio1 7000 Here we provide proof for
T101 = O. Note that the proof of rooo = 0 is similar.
rlo1 x > O, we can easily adjust rloo increase by x, rl01 so that the new solution also
satisfy
25
Thus, let rl 10o0
0 and riso Ti -r1 rin r001
ti r011
Toiu
Problem
holds iff
r E thu
Thu
<
+
To
T
To
rho + ron + +r
+ rono 2 1 81
o' (rh1o ruu)
e (rin + ro10)
(26)
Ih + rdo Sa
tho + 5n
rdu r0 $
Using similar method the proof of Theorem 4.1 to solve 26
D.7 PROOF OF THEOREM
Note that when the equal abstention rate constraints added, Lemma D.I still holds. The reason rlo = r = 0 already yields equal abstention rate, since the abstention rates of individuals with negative label are both O.
20

---

Published as a conference paper at ICLR 2024
Similar to 12
the constraints of Problem 3 can be written
'11 r010
Ar - S rin
r010
.
0 -r010
At
+ 7 111
1010
1 S 81
110 - 60
100
S
10
0
T101
70
2 10
0
T101 010)
10
(27)
delrn + ron) - 6/
+ 0
+ 10
+ s ( +roio)
Iu +r +ho0 =
i +r +r
Tono + +
r ron1 To
rl r 2 0
Compare to the additional constraints of rio are 1 m 11 S 1110 them and extract the condition of rlo yields
S 0 5 7700
+ 1101 Plug in
0 O Sb
0 S r 6n
2010 rin
110
df
d
0 1i11
rin
(28)
% ri0 S T rin
0 S T I
T1r S Torlo + T0T101
mr Torlo T0T101
The last inequalities are the additional constraints introduced by equal abstention rate constraints.
Thus, if T0o1 2 6n and 8, < T hold, then the fcasibility of Problem 3 will reduce to the non equal abstention rate case MP-Main (Equation 16). Therefore, sufficient condition of Problem 3 is
1 + (m)m))
m))1 To T1
81 S TIO 80 S TOOL, 80 >
(29)
(1 + m0
D.8 EQUAL ABSTENTION RATE UNDER EQUAL OPPORTUNITY AND EQUALIZED ODDS
Theorem D.2. Problem 3 is always feasible under Equal Opportunity (Equalized Odds).
This theorem holds because Problem IP-Main always feasible even when all the groups have abstention rate for the individuals with either positive or negative labels. In this case, the abstention rates already equal.
21

---

Published as a conference paper at ICLR 2024
D.9 WORSE PERFORMANCE UNDER EQUAL ABSTENTION RATE
Theorem D.3. (Worse Performance) Let , f be the result of Problem MP-Main be the result of Problem 3
let w(() , ((2]
then
N
N
Σ
(1)
Fyn] S Σ 117h
.1// ynn]
11
n=1
Σ Wn
(1) -1(m * yn 2n =1
Σ n=1 wn .1(hh + yn 2n =
(2)
22 E Z
En=1 Wii (1) 1/2 =]
Σ n= wn
(2)
1 12n = 2)
2(f(), s ( ,w(t))
(30)
E EXPERIMENTS
Dataset
Adult
Compas
Law
Train data
37969
8467
12928
Val data
7911
1765
2694
Test data 9888
2206
3368
Table 5: Size of train, val, test data of each dataset.
Dataset. We utilized three woal-world datasets, namely Adult Dua Graff (2017). Compas Bellamy et al. (2018), and Law (Belaayy al. (2018). The sizes of the training, validation, and test data can be found in Table 5 The task the Adult dataset to predict whether a person's 's income exceeds $50k per year based on various demographic and empllyyment-rlltee features. The sensitive attribute is sex, with group representing ma le and group 2 representing female. In the Compas dataset, the task is predict the likelihood of defendant committing a future crime, aiming assist judges in making more informed decisions about pretrial detention and release. The task has been categorized, and the sensitive attribute is race, with group 1 representing Caucas s and group representing Afri can maan-Ann Ameri can. The Law dataset aims to predict the likelihood of a law school student dropping out within the first two years based on various academic and demographic attributes. The task has been categorized, and the sensitive attribute is race, with group representing Wh te and group 0 representing Black.
Neural Network. To train the models, namely Basel in Opt imallmaly m, AR, and FB, we utilized Multi-Layer Perceptron (MLP) neural network architecture implemented in PyTorch. The architecture configuration for the Adult dataset consists of two layers, each with dimension of 300. For the Compas and Law datasets, we employed two layers, each with a dimension of 100. A dropout layer with dropout probability of 0.5 was applied between the two hidden layers. The Rectified Linear Unit (ReLU) function was used as the activation function. We run the experiments on a single T100 GPU.
E.
BASELINE OPTIMAL
Table shows the performance of the baseline optimal model on both the training and test datasets.
Adult
Compas
Law
Accuracy (%) (Overall)
92.08 (89.11)
72.33 (70.31)
82.86 (8I.23)
Accuracy (%) (Group 1)
98.81 (96.67)
68.99 (66.11)
82.04 (81.04)
Accuracy (%) (Group 2)
90.28 (87.07)
75.70 (74.33)
84.21 (81.57)
Disparity (DP)
0.59 (0.61)
0.19 (0.19)
0.16 (0.13)
Disparity (EOp)
0.05 (0.20)
0.26 (0.22)
0.11 (0.09)
Disparity (EOd)
0.13 (0.23)
0.18 (0.18)
0.08 (0.08)
Table 6: Performance of the Bascline Optimal Classifier, (Values in parentheses represent results on test data.)
22

---

Published as a conference paper at ICLR 2024
E.2 OVERALL PERFORMANCE
The performance comparison of FAN with LTD, FSCS on each dataset are shown in this section. preform 5 runs for FAN, under each setting. In most case, FAN achieves best performance on both accuracy and disparity.
Dissweto Nledicte
0.0
Disse to Redducion
LTD
6.0
LTD
1SC3
PSC3
PSCS
FAX
PAN
Disse
-22
0.
6.3
0.0
0.1
Inerase Accors
Incrusee incere/
Incrosein
0.1
-0.
Incrusein
LTD
LTD
LTD
LTD
-83
FAN
F5C5
-03
FAN
FSCS
FSCS
FAN
FSCS
FAN
0.0
61
02
0.3
9.0
6.1
0/2
0.3
0.0
02
93
3.0
0.1
0.
93
(a) train, EOp
(b) train, BOd
(c) test, EOp
(d) test, EOd
Figure 9: Comparison of FAN with baseline algorithms on Adult. The first row shows the disparity reduction compared to baseline optimal), while the second row shows the minimum increase in group accuracy compared to baseline optimal. For FAN, 7)= is set to 0, i.c. no tolerance for reducing accuracy.
per ty Nelwezin
Dlquatty Redtue restuctonn
hapany/ttaaaa Netaciin
0.20
8.1
0.10
Daganay
FSCS
FSCS
0.05
FSCS
0.0
0.3
0.3
0.00
0.000
+0.00
+2.05
1012
-0.10
-2.10
-0.18
-3.15
LTD
2-.15
-0.0
ESCS
FSCS
FAN
0.2
0.3
5.0
0.2
03
(a) train, DP
(b) train, EOp
(c) test, DP
(d) test, EOp
Figure 10: Comparison FAN with baseline algorithms on Compas. The first row shows disparity reduction compared to baseline optimal), while the second row shows the minimum group accuracy increase compared to bascline optimal. For FAN, 7) is set to i.c. no tolerance for reducing accuracy.
23

---

Published as a conference paper at ICLR 2024
Departy beturteo
Restration
0.04
to Relusioo
0.00
0.02
0.08
0.00
0.06
0.04
Inreeoo B-CCU/OOY
0.30
0.00
+3.05
-0.
-01
-2.10
-2.15
-62
$SC5
-3.20
-320
-2.25
train, DP
(b) train, EOd
(c) test, DP
(d) test, EOd
Figure 11: Comparison of FAN with baseline algorithms on Law. The first row shows the disparity reduction compared baseline optimal), while the second shows the minimum group accuracy increase compared to baseline optimal. For F AN, is set to 0, i.c. no tolerance for reducing accuracy.
E.3 COMPARE TO BASELINE OPTIMAL CLASSIFIER
In this section, FAN is compared with baseline optimal classifier under various abstention rate and disparity tolerance.
Disparity Reduction
Increase in Accuracy
Increase Accuracy
0.05
016
0.04
0.04
0.03
312
0.10
0 0.004
0.030
0.01
0.06
0.01
0,002
0.01
6.005
3.04
0.0
0.2
0.3
0.2
6.3
0.0
0.1
0.2
0.3
(a) Disparity, EOd
(b) Accuracy, Group
(c) Accuracy, Group 0
Figure 12: Disparity reduction and increased accuracy for each group performed on Adu t, compared baseline optimal classifier. This plot illustrates the performance on the testing data. (a) demonstrates the disparity reduction in terms of Equalized odds, while (b) and (c) showcase the increases accuracy for group I and group 0, separately. The x-axis represents the maximum permissible abstention rate, while the y-axis represents the maximum allowable disparity.
24

---

Published as a conference paper at ICLR 2024
Disparity Reduction
Accuracy
0.01
Accuracy
0.14
0.125
0.14
0.00
0.14
0.12
0.01
0.075
0.02
00.03
-0.33
0.04
0.06
6.06
-0.34
0.06
0.05
0.04
6.04
00.05
0.04
-0.06
6.000
-0.96
0.0
0.1
0.2
0.3
0.0
0.2
0.3
0.0
0.1
0.2
0.3
(a) Disparity, DP
(b) Accuracy, Group
(c) Accuracy, Group O
Figure 13: Disparity reduction and increased accuracy for each group performed Compas, s, compared to baseline optimal classifier. This plot illustrates the performance on the testing data. (a) demonstrates the disparity reduction terms of Demographic Parity, while (b) and (c) showcase the increases in accuracy for group and group O, separately. The x-axis represents the maximum permissible abstention rate, while the y-axis represents the maximum allowable disparity.
Disparity Reduction
Increase In Accuracy
Increase in Accuracy
0.04
0.06
0.06
0.33
0.52
0.04
0.04
300
0.02
0.01
0.02
001
-0.01
0.00
-0.00
0.2
0.3
0.3
(a) Disparity, EOp
(b) Accuracy, Group
(c) Accuracy, Group O
Figure Disparity reduction and increased accuracy for each group performed on Law, compared baseline optimal classifier. This plot illustrates the performance on the testing data. (a) demonstrates the disparity reduction in terms of Equal Opportunity, while (b) and (c) showcase the increases in accuracy for group and group O, separately. The x-axis represents the maximum permissible abstention rate, while the y-axis represents the maximum allowable disparity.
E.4
IMPACT OF 1
0.08
n=0
0=0
0.1
0=0.1
0.994
0.06
Dispanity
0.93
0.04
0.92
0.990
0.02
0.91
0.988
0.00
0.986
0.0
0.0
Figure 15: Impact of 17. This experiment is performed Adult under Equal Opportunity, training data. 77 takes O, 0.1. The left shows the disparity of under each setting; the middle shows the accuracy of group the right shows the accuracy of group 0. Relax the error rate control yields similar result, since the objective of will still encourage the system to be more accurate.
E.5 PREDICTION CONSISTENCY
To demonstrate the consistency of IP predictions, which involves abstaining and flipping decisions for individuals with identical features within the same group, duplicated & of the data across all
25

---

Published as a conference paper at ICLR 2024
This duplication serves to illustrate that IP make the same prediction to these duplicated instances. Details referred to Table
datasets.
Dataset
Adult (EO)
Adult (EOs)
Compas (DP)
Compas (EO)
(DP)
Law (BO)
Consistent (w)
0.99
0.99
1.0
1.0
0.99
0.99
Consistent rate (f)
1.0
0.99
1.0
0.99
1.0
Table Prediction Consistency Evaluation IP.
E.6
STAGE II: SURROGATE MODEL TRAINING LOSS
039
0.3
0.3
3.2
0.9
3.2
0.5
3.2
022
332
335
Figure 16: Loss of AB (a) and F3 (b), performed on Adult, under Demographic parity. ó = 0.1,8 0.02. We perform runs and plot the average and standard deviation. The corresponding average accuracy is 92.20% and 97.79%
E.7 FEASIBILITY REGION
We perform experiments to verify the correctness of Theorem
Feaelbility
Feasiblity
(Ninimum
0.10
0.10
0.06
0.06
0.02
0.00
0.150 0:75
0,200
0.225 6.25 0.300
0:00
0.58 0:15 0.00
6225
3220 0.75 0300
Figure 17: Minimum allowed for each 8, performed Adult, under Demographic parity. The left figure shows the result under = 0.1, while the right figure shows the result under = 0. Both figures show the linearity proved in Theorem 4.1
E.8
TIME COST
Adult
Compas EO
Law
DP
EO
EOd
DP
EOd
DP
EO
EOd
36.76
22.05
33.85
5.02
4.92
10.74
12.58
15.95
16.81
IP
(1.08)
(1.25)
(1.58)
(1.53)
(0.92)
(0.61)
(0.84)
(0.79)
(0.93)
14.33
20.06
18.39
7.24
7.12
14.16
27.68
28.99
64.04
AB
(1.02)
(0.98)
(1.14)
(1.67)
(0.89)
(0.73)
(0.97)
(0.84)
(1.20)
14.72
9.59
22.05
6.90
9.88
10.52
28.00
26.82
41.87
FB
(1.65)
(0.72)
(0.96)
(1.31)
(0.75)
(0.65)
(0.81)
(0.87)
(0.88)
Table 8: Average time cost (in seconds) of solving IP, training AB and FB, respectively. The experiments run single T100 GPU. The numbers in parentheses are the corresponding std.
26

---

Published as a conference paper at ICLR 2024
F HUMAN ANNOTATION
In the case that human annotation exists for training data, our method can be applied with some modifications of the IP. For example, under Demographie Parity,
min w.f
Σ [uin Un + ynl + 1w0 O, yeu ynl
(IP-Main)
(2)) D(=')l S V2, EZ
(Disparity)
n=1 Wn 1n2n = 2]
2 (1- 02),
(Abstention Rate)
Σm= 1[2n = 2]
N
N
Σ n=1
Ilwn = 1h * Un Zn = 2] + 1[wn = 0, Mdn + yau
2] S e
1z = 2], 22 E Z
n=1
(No Harm)
Wn (0,1), E V0.
Where Ya is the human annotation, D(=) = Σ 100 1,,, 2,0 1 -م,t, 2, The modification does not add any new constraint, the computational complexity remains the same. And Stage II can still be applied directly.
> ||,,
27


Reviews:
[{"review_id": "cRGOttX2vV", "reviewer": "Reviewer_JZKB", "summary": "The paper is considering the problem of enhancing fairness guarantees in model outputs. The specific problem considered is focusing on classification with abstention while increasing group fairness and maintaining model performance. \nThe authors argue that the previous approaches on fair classification or abstention don’t incorporate control over accuracy. They propose a 2-stage procedure to overcome this: (1) Integer Programming stage to generate abstention and flipping outcomes for each data point while maintaining accuracy, (2) Training a surrogate model against outputs of stage 1. They test their approach against two baselines on three real-world fairness datasets.", "questions": "Could the authors show  the comparative performance on multi-group scenario in case of the Law and Compas datasets with the other baselines?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Paper is well structured and easy to read\n\n2. The problem’s scope and methodology is well defined\n\n3. The proposed method seems motivated; they seem to include the “no-harm” constraint along with giving feasibility conditions for disparity thresholds\n\n4. The method is performant in the tasks considered", "weaknesses": "The reviewer is not convinced on the feasibility of the IP and the ability of surrogate to learn the patterns in AB or FB. Not a weakness as such, but would like to see a discussion from the authors.", "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": "", "extra_scores": {}}, {"review_id": "HR4x41xylx", "reviewer": "Reviewer_GsZB", "summary": "The paper focuses on the problem of selective binary classification under fairness, abstention and harm constraints.  To accommodate for all the constraints the authors propose a framework with two basic components: a mechanism deciding from which instances the classifier should abstain and a mechanism deciding to flip the predictions of the classifier. Using these components the authors first formulate the problem of minimizing the classification error under disparity, abstention rate, and no harm constraints with IP.  Then they propose solving the IP problem for a small dataset and use these solutions to train models on the abstention and flipping component to predict near optimal decisions on unseen data. Finally, the authors deploy their framework on several datasets and compare it with competitive baselines.", "questions": "1. With FB one could use any arbitrary vector of random predictions (not necessarily from a classifier) and learn when to flip then or not. If so why would one need a classifier in the first place?\n2. It is not clear what is the motivation for section 4.2. Since in IP-Main one does provide a desired abstention constraint for each $z \\in \\mathcal{Z}$ why would one would like to further constraint the difference of abstention rate?  \n3. why would one would like to further constraint the difference of abstention rate? Also it is not clear in what sense “the performance will become worse”. It might more helpful to clarify if the authors mean that the IP problem will be harder to solve or if the solution of the problem will have a higher error rate. Not sure that 4.2 adds much, maybe remove it?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The work appears to be the first to consider the problem of selective classification under fairness, abstention rate, and no harm constraints on the same time. The proposed approach seems quite interesting especially for being flexible about the type of fairness constraints that one may impose.  In addition,  achieving fairness guarantees without sacrificing accuracy seems of great importance for real world applications. \n\nThe paper appears very-well structured and nicely written. The authors clearly describe their contributions and sufficiently discuss relation to contemporary literature. Moreover, they present the experimental setup in detail. The experimental evaluation appears thorough and the results seem promising.", "weaknesses": "Even though the paper is nicely and clearly written, there are a few points that could confuse the reader:\n\nIn the Paragraph “Stage I: Integer Programming. We approximate h_A and h_F…” “approximate” is confusing as  $h_A$ and $h_F$  are already defined as binary parameters. \n\nIn the optimization problem in section 3.1 the abstention rate and the no harm constraints are not defined for any $z \\in \\mathcal{Z}$, whereas in the IP-Main these constraints are defined for each $z  \\in \\mathcal{Z}$. If IP-Main is a way to practically solve of the optimization problem in section 3.1, the definitions should be consistent. If there is a reason why these definitions should be different, this reason should be made clear.\n\nIt is not clear what is the motivation for section 4.2. Since in IP-Main one does provide a desired abstention rate constraint for each $z \\in \\mathcal{Z}$ it is not clear what benefit would bring further constraints on the difference on the abstention rates. Especially in the case that the cardinality of $\\mathcal{Z}$ is large, additional pairwise  constraints  for each pair $z,z’ \\in \\mathcal{Z}$ would add significant overhead in solving (3). Also, in (3) $z’$ is not defined.\n\nThe reported results in Figure 3 are over only 5 different runs. One could argue that this is a quite limited evaluation. Given that the results do look promising and the error bars are relatively small, showing results over more runs would strengthen the significance of the results. If there are computational limitations that prevented the authors from evaluating their method for more runs, these should be made clear. The same applies for the results of Table 2. In addition, Table 2 is missing confidence intervals and the type of the error bars in Figure 3 are not  specified.\n\nThe authors should consider adding a (brief) discussion on limitations of their approach and on perspectives for future work.\n\n\n\n Typos/Misc:\n- 1st paragraph in section 2 “i.e.” —> “i.e.,” and “e.g.” —> “e.g.,”\n- 2nd paragraph  “to determine which samples to abstain” is not very clear. Suggestion “to determine from which samples the classifier should abstain”\n- Section 4 first paragraph “hyperparameter” —> “hyperparameters” \n- Bottom of page 5 “as the models are neural network” —> “as the models are neural networks”\n- Top of page 6 right most column of the Table “TBD in 3.1” do the authors mean “TBD in 4.1”? \n- “An objection may arise that the model’s excessive abstention from a particular group, while not observed in others.” This seems as an incomplete sentence. What do the authors mean here? \n- Missing “.” In footnote 2.\n- Page 8 top “DO”—> “DP”\n- Conclusion “our abstaining process incur” —> “our abstaining process incurs”", "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": "", "extra_scores": {}}, {"review_id": "mgxILohXRo", "reviewer": "Reviewer_RYdg", "summary": "The paper addresses the problem of training fair classifiers, but also caters to other constraints such as not reducing group-wise accuracy and providing a \"do not predict\" option. The main idea of the paper is to increase the feasibility region of the fair classification problem (and other constraints) by abstaining and flipping predictions. The overall constrained problem is solved by Integer Programming. To use the models on unseen data, the paper trains surrogate models to the Integer Programming solution.", "questions": "1. It would be great to get the answers to points 1-3 in the \"Weaknesses\" section.\n\n2. Is it possible to extend no-harm to individual samples, e.g., the prediction on individual samples should not flip from positive to negative?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper is quite well-written. Most design choices are appropriately motivated. Terminology is clean and easy to understand despite the large number of components involved.\n\n2. The experimental results are encouraging.\n\n3. The paper solves a mix of problems that are all quite useful: fairness, abstaining from making decisions, and not reducing accuracy for groups in the data. All of these components are individually addressed elsewhere in prior work, but putting them all together is a nice contribution.", "weaknesses": "I think the paper needs to address a couple of points before it is ready for publication:\n\n1. The paper claims to provide hard constraint satisfaction guarantees but does not discuss how these guarantees are supposed to hold when replacing AB and FB modules with surrogate models, and when replacing the true label predictor with a surrogate model. Does the generalization ability of these surrogate models not affect the constraint satisfaction? If yes, how? Or is that the guarantees only hold when assuming Bayers Optimal predictors?\n\n2. On a related note, the paper should provide some discussion into the functional form of the surrogate models. In the appendix, the paper mentions using different Neural Net architectures for different datasets. Is there some guidance on how the architectures should be selected? Should one select the optimal architectures using hyperparameter tuning in isolation (one surrogate model at a time) or should the tuning procedure consider the whole end-to-end Integer Program?\n\n3. Perhaps I missed it, but the paper does not provide information about training cost (e.g., wallclock time). Seeing how the training cost scales with number of data points is essential in judging the effectiveness of the proposed procedure.", "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": "", "extra_scores": {}}, {"review_id": "YIFXCXy2AP", "reviewer": "Reviewer_7v7y", "summary": "The authors shed light on the challenge of fair classification with the option of abstaining from a prediction. Their objective is to develop a post-hoc fair classification algorithm that meets the following four criteria: 1) the accuracy across groups should be almost as good as the provided classifier, 2) the fairness criteria should be maintained within a prescribed threshold, 3) the feasibility of achieving both the aforementioned accuracy and fairness, given a specified abstention rate, must be ascertainable, and 4) a range of fairness criteria can be applied. The suggested algorithm employs a mixed integer problem solver to determine the best abstentions and label flips that minimize classification errors while simultaneously ensuring the desired levels of accuracy, fairness, and abstention rate. Subsequently, the algorithm constructs a neural network to predict these optimal abstentions and label flips. As theoretical findings, the authors highlight the essential conditions needed for the accuracy, fairness, and abstention rate constraints to be feasible, considering various fairness criteria, including demographic parity, equalized odds, and equal opportunity. Experimental outcomes indicate that the new algorithm maintains fairness without compromising accuracy, a distinction from existing methods, which often trade off one for the other.", "questions": "1. Can the authors illustrate a specific scenario in which the constraints of their proposed algorithm are essential?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is clearly written and easy to understand.\n\n2. The experimental results robustly confirm the improvement of fairness without compromising accuracy, distinguishing the proposed algorithm from existing methods like LTD and FSCS.\n\n3. The theoretical analyses provide insightful results that may elucidate the conditions under which the best classifier with optimal abstention satisfies the requirements. This could potentially characterize the Bayes optimal classifier with abstentions, contributing valuable insights into the trade-off between accuracy and fairness.", "weaknesses": "1. The method proposed evalates the fairness of the learning classifier using abstained sample. This approach seems impractical in real-world scenarios, where actionable decisions are often needed even for abstained cases. Previous studies, like those of LTD and FSCS, suppose that abstained decisions default to human intervention. Consequently, the fairness of the complete system should encompass both algorithmic and human decisions. Unlike these studies, the proposed algorithm's rationale behind its fairness constraints remains ambiguous. It would benefit readers if the authors presented a real-world scenario validating their algorithm's constraints.\n\n2. Using both an error rate objective function and a no-harm constraint seems redundant as they essentially serve the same purpose.\n\n3. The authors state that their algorithm upholds hard fairness constraints. However, the optimization problem they designed utilizes an approximate fairness constraint. Moreover, the second stage might infringe upon this strict fairness constraint since it merely constructs a function that mimics the labels derived from Stage I.\n\n4. While the fairness requirements of the proposed algorithm differ from those in existing studies (LTD and FSCS), the authors use the evaluation metric of the proposed algorithm's fairness in the experiments. This approach is unfair to the existing methods.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)