A Near-Optimal Recipe for Debiasing Trained Machine Learning Models
Authors: Ibrahim Alabdulmohsin
Mario Lucic
Venue:  (2021)
Keywords: Fairness
Classification
Statistical Parity
Deep Learning

Abstract: We present an efficient and scalable algorithm for debiasing trained models, including deep neural networks (DNNs), which we prove to be near-optimal by bounding its excess Bayes risk.  Unlike previous black-box reduction methods to cost-sensitive classification rules, the proposed algorithm operates on models that have been trained without having to retrain the model. Furthermore, as the algorithm is based on projected stochastic gradient descent (SGD), it is particularly attractive for deep learning applications. We empirically validate the proposed algorithm on standard benchmark datasets across both classical algorithms and modern DNN architectures and demonstrate that it outperforms previous post-processing approaches for unbiased classification.

Under review as a conference paper at ICLR 2021
A NEAR-OPTIMAL ALGORITHM FOR DEBIASING TRAINED MACHINE LEARNING MODELS
Anonymous authors Paper under double-blind review
ABSTRACT
We present an efficient and scalable algorithm for debiasing trained models, in- cluding deep neural networks (DNNs), which we prove to be near-optimal by bounding its excess Bayes risk. Unlike previous black-box reduction methods cost-sensitive classification rules, the proposed algorithm operates on models that have been trained without having retrain the model. Furthermore, as the algo- rithm is based on projected stochastic gradient descent (SGD), it is particularly attractive for deep learning applications. We empirically validate the proposed algorithm on standard benchmark datasets across both classical algorithms and modern DNN architectures and demonstrate that it outperforms previous post- processing approaches for unbiased classification.
INTRODUCTION
Machine learning increasingly applied critical decisions which can have a lasting impact on individual lives, such as for credit lending (Bruckner) 2018), medical applications (Deo) (015)), and criminal justice (Brennan et al. 2009). Consequently, it is imperative to understand and improve the degree of bias of such automated mecksion-making.
Unfortunately, despite the fact that bias (or "fairness") is a central concept in our society today, it is difficuul to define it in precise terms. In fact, as people perceive ethical matters differently depending on a plethora of factors including geographical location or culture (Awad et al., 2018), no universally-agres upon definition for bias exists. Moreover, the definition of bias may depend the application and might even be ignored in favor of accuracy when the stakes are high, such as in medical diagnosis (Kleinberg et al. 2017 Ingold and Soper 2016). As such, is not surprising that several definitions of "unbiased classification" have been introduced. These include statistical parity (Dwork al., [2012 Zafar et al. 2017a). equality of opportunity (Hardt al.. (016)), and equalized odds (Hardt et al. 2016 Kleinberg et al.] (207)). Unfortunately, such definitions are not generally compatible (Chouldechova) 2017) and some might even be in conflict with calibration (Kleinberg
et al. 2017). In addition, because fairness is societal concept, it does not necessarily translate into a statistical criteria (Chouldechova 2017
Dixon et al. 2018).
Statistical parity Let X' be an instance space and let y = {0, 1} be the target set in a standard binary classification problem. In the fair classification setting, we may further assume the existence of a (possibly randomized) sensitive attribute s : X' + 10, K), where s(x) = if and only if E X for some total partition X' U For example, X' might correspond to the set of job applicants while s indicates their gender. Here, the sensitive attribute can be randomized if, for instance, the gender of applicant is not deterministic function of the full instance E X' (e.g. number of publications, years of experience, ...etc). Then, a commonly used criterion for fairness to require similar mean outcomes across the sensitive attribute. This property well-captured through the notion of statistical parity (a.k.a. demographic parity) Corbett-Davire et al. 2017 Dwork et al. 2012 Zafar et al. 2017a Mehrabi et al. 2019):
Definition (Statistical Parity). Let X be an instance space and X Us. be a total partition of X. A classifier f X + {0. 1} satisfies statistical parity across all groups XI...., Xx if:
(x) xx Xx]
min Ex(f(x) x Xa) Se
kE.,......KK
kE(1,2.....K)

---

Under review as a conference paper at ICLR 2021
Random
hbours
Multilayer perceptron
0.20
Males
0.29
Males
Males
Frequency
0.15
Frequency
0.115
Eraqurnes
0.30
0.08
0.10
0.06
0.00
0.05
0.05
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
ply=11x)
ply=1ix)
ply=1k
Random forest
k-Nearest neighbours
107
Multlaayer perceptron
Orggnal
10-4
10-2
10-1
10a2
10-3
10-3
10-3
American
American
Figure 1: Top: Histogram of classifiers' predictions on both subpopulations, demonstrating clear gender bias in all cases. Bottom: The bias defiedd as the absolute difference in mean outcome between genders within different demographic groups, before and after applying the proposed al- gorithm. Blue bars show the results of the unmodified classifier, orange bars show the results of optimizing for statistical parity with no regard for demographic information. Finally, green bars are the results of applying statistical parity the cross product of gender and ethnicity.
To motivate and further clarify the definition, we showcase the empirical results on the Adult bench- mark dataset (Blake and Merz 1998) in Figure When tasked with predicting whether the income of individuals above S50K per year, all considered classifiers exhibit gender-related bias. One way of removing such bias is enforce statistical parity across genders. Crucially. however, with- out taking ethnicity into account, different demographic groups may experience different outcomes. In fact, gender bias actually increase in some minority groups after enforeing statistical parity. This can be fixed by redefining the sensitive attribute to be the cross product of both gender and ethnicity (green bars).
Our main contribution to present a near-optimal recipe for debiasing models, including deep neural networks, according Definition I Specifically, we formulate the task of debiasing learned models as a regularized optimization problem that is solved efficiently using the projected SGD method. We show how the algorithm produces thresholding rules with randomization near the thresholds, where the width of randomization is controlled by the regularization parameter. We also show that randomization near the threshold necessary for Bayes risk consistency. While we focus on binary sensitive attributes in our experiments in Section [ our algorithm and its theoretical guarantees continue to hold for non-binary sensitive attributes as well.
Statement of Contribution
1. We derive near-optimal post-processing algorithm for debiasing learned models (Section 3
2. We prove theoretical guarantees for the proposed algorithm, including a proof correctness and an explicit bound on the Bayes excess risk (Section 4).
3. We empirically validate the proposed algorithm on benchmark datasets across both classical algorithms and modern DNN architectures. Our experiments demonstrate that the proposed algorithm significantly outperforms previous post-processing methods (Section 5
In Appendix E we also show how the proposed algorithm can be modified to handle other criteria of bias as well.
RELATED WORK
Algorithms for fair machine learning can broadly classified into three groups: (1) pre- procesocss methods, (2) in-processing methods, and post-processing methods /aafar et al. 2019)
2

---

Under review as a conference paper at ICLR 2021
Preprocessing algorithms transform the data into different representation such that any classifier trained on will not exhibit bias. This includes methods for learning a fair representation (Zemel
et al. 2013: Lum and Johndrow 2016 Bolukbasi al. 2016: Calmon et al. 2017 [Madras et al.)
2018
Kamiran and Calders 2012), label manipulation (Kamiran and Calders, 2009 data augmen-
tation
(Dixnn al. 2018). or disentanglement (Locatello et 2019).
On the other hand, in-processing methods constrain the behavior of learning algorithms in order to control bias. This includes methods based on adversarial learning (Zhang et al.] 2018) and constraint-based classification, such as by incorporating constrains on the decision margin ZZafar al. 2019) or features (Grgié- Hllča et al., 2018). Agarwal et al. (2018) showed that the task of learning an unbiased classifier could be reduced to sequence of cost-sensitive classification prob- lems, which could be applied to any black-box classifier. One caveat of the latter approach that it requires solving a linear program (LP) and retraining classifiers, such as neural networks, many times before convergence.
The algorithm we propose in this paper is post- cost-proeessing method, which can be justified theo- retically (Corbett-Davies et al.) 2017: Hardt et al. 2016 Menon and Williamson| 2018: Celis et al.) 2019). Fish et al. (2016) and Woodworth et al. (2017) fall under this category. However, the former only provides generalization guarantees without consistency results while the latter proposes a two- stage approach that requires changes to the original training algorithm. Kamiran al. (2012) also proposes a vost-processing algorithm, called Reject Option Classifier (ROC), without providing any theoretical guarantees. In contrast, our algorithm is Bayes consistent and does not alter the original classification method. In [Celis et al. (2019) and Menon and Williamson 2018), instance-dependent thresholding rules are also learned. However, our algorithm also learns randomize around the threshold (Figure 2 a)) and this randomization is key to our algorithm both theoretically as well as experimentally (Appendix(lane Section 5 Hardt et al. (2016) learns a randomized post-pret post-processing rule but our proposed algorithm outperforms it in all of our experiments (Section 5)
Woodworth al. (2017) showed that the post-processing approach can, sometimes, be highly sub- optimal. Nevertheless, the latter result does not contradict the statement that our post-processing rule near-optimal because we assume that the original classifier outputs a monotone transforma- tion of some approximation to the posterior probability p(y = 1 x) (e.g. margin or softmax output) whereas Woodworth et al. (2017) assumed in their construction that the post-processing rule had access to the binary predictions only.
We argue that the proposed algorithm has distinct advantages, particularly for deep neural networks (DNNs). First, stochastic convex optimization methods are well-understood and can scale well to massive amounts of data (Bottou 2010), which is often the case in deep learning today. Second, the guarantees provided by our algorithm hold w.r.t. the binary predictions instead of using proxy, such as the margin as in some previous works (Zafrr et al. [00 2019). Third, unlike previous reduction methods that would require retraining deep neural network several times until convergence (Agar- wal et al. 2018), which can be prohibitively expensive, our algorithm operates on learned models that are trained once and does not require retraining.
Besides developing algorithms for fair classification, several recent works focused on other related aspects, such as proposing new definitions for fairness; e.g. demographic parity (Dwork et al.) 2012 Mehrabi et al. 2019). equalized odds (Hardt et al. 2016). equality of opportunity/disparal mistreatment (Zafar et al.) 20177 Hardt et 2016)), and individual fairness (Dwork et al.) 2012). Recent works have also established several impossibility results related to fair classification, such as Kleinberg et al. (2017); y Chouldechova (2017). In our case, we derive a new impossibility result that holds for any deterministic binary classifier and relate it to the task of controlling the covariance between the classifier's predictions and the sensitive attribute (Appendix
NEAR-OPTIMAL ALGORITHM FOR STATISTICAL PARITY
Notation We reserve boldface letters for random variables (e.g. x), small letters for instances (e.g. I)), capital letters for sets (e.g. X), and calligraphic typeface for universal sets (e.g. the instance space X). Given a set S, (z) E {0, 1} is the characteristic function indicating whether x E S. We denote by [n] the set of integers (1....,n) and [x]+ max (0, 2).
3

---

Under review as a conference paper at ICLR 2021
Algorithm Given classifier f : 1-1, +1] our goal is post- process the predictions made
by J in order to control the bias with respect to a sensitive attribute $ - [K] as in Definition | To this end, instead of learning deterministic classifier, of the form
consider randomized prediction rules
h X' (1, Kj x [-1, - [0,
where i(x) represents the probability predicting the positive class given (i) instance x E X, (ii) sensitive attribute sx)), and (iii) classifier's output fxx).
As discussed in Appendix B for post-processing rule i(z), and for cach group X₁ S X, the fair- ness constraint in Definition can be written as [E, (x(x) x Xx] pl C, where p [0, 1] is a hyper-parameter tuned via validation dataset. On the other hand, minimizing the probability of altering the predictions of the original classifier can be achieved by maximizing the inner product (x( f(x]]. Instead of optimizing this quantity directly, which would lead pure thresholding
rule, we minimize the regularized objective: (7/2) [h()) Ex(h(x) f(x) for some regulariza- tion parameter y >> O. This regularization leads to randomization around the threshold, which we show to be critical, both theoretically (Section | and Appendix C and experimentally (Section (5) Using Lagrange duality we show that the solution reduces to the update rules in Equation 2 with optimization variables {Ak: MR [K(]]] and the corresponding predictor which outputs + for group
X₁ with probability h (1)) is given by
0,
f(x) A 14:
hx(2)
d + pk)/7, (f(x)
d - ph S f(x) S d4
pe +Y
1,
f(x) z d - p +
where Ey is given by Eq. (3).
Update rules
To learn these parameters, one can apply the following update rules (Appendix B):
Xatx) max {0, Xa(x)= - n(= + p+
E, (f(x)
-(Na(x) (o(r))))
()a(s)
0 [a(()) max {0, Ma(xx) " p Ops(x)
(x(
-Aa(( (2(x))
where, again, p [0. 1] is hyperparameter tuned via validation dataset, s X [K] is the sensitive attribute, and 7 >> is a regularization parameter that controls the level of randomization. + is given by:
In addition, the function E R E
Voswsyy w²
(w 3) I(w 7
(w)
27
Note that &,, is convex and its derivative 5 is (1/s)-Lipshhizz continuous; it can be interpreted as differentiable approximation the ReLU unit (Nair and Hinton 2010). A full pseudocode of the proposed algorithm is presented in Appendix A
4 THEORETICAL ANALYSIS
Next, we analyze the algorithm. Our first theoretical result is to show that the prediction rule in Equation [ learned through the update rules presented in Section 3 satisfies the desired fairness guarantees on the training sample.
Theorem (Correctness).. Let h : X 1] be the randomized predictor in Equation 1 learned by applying the update rules in Equation 2 starting with pa = 0, A 0, Vk E [K] until conver- gence. Then, hy satisfies e statistical parity w.r.t. {Xe)xe(K] in the training sample.
The proof of Theorem is presented in Appendix B The following guarantee, which holds w.r.. the underlying data distribution, shows that the randomized prediction rule converges to the Bayes
'Ideally an estimate of some monotone transformation of 21y(x) - 1, where 17(x) = ply = 1|x 2) is the Bayes regressor. This is not strong assumption because many algorithms can be calibrated to provide probability scores (Platt et al. 1999 Guo et al. 2017).
4

---

Under review as a conference paper at ICLR 2021
h(x)
X 40
2
4
0
5
10
15
20
25
f(x)
Epoch
(a) Decision rule
(b) Convergence
Figure 2: (a) The learned post-processing decision rule h(x) in Equation as a function of the classifier's score f(z). Randomization applied when h(z) E (0, (),, which can be controlled using the regularization parameter 7 > 0. (b) The value of Xg Un is plotted against the number of epochs in the projected SGD method applied to the output the random forests classifier trained on the Adult dataset implement statistical parity with respect to the gender attribute (cf. Section
S 5ldd Figure D. We observe fast convergence in agreement with Proposition
optimal unbiased classifier if the original classifier f is Bayes consistent. The proof of the following theorem (Appendix C) based on the Lipschitz continuity of the decision rule when 7 > and the robustness framework of Xu and Mannor (2010).
Theorem 2. Let h* arg min [x((x) * y). where He is the set of binary predictors on X
that satisfy fairness according to Definition for e O. Let h : X - [0, 1] be the randomized learning rule in Equation 7 If h., is trained on freshly sampled data of size N, then there exists value of p E [0, 1] such that the following holds with probability of at least 8:
8(2+ +
2K 2 22 2
th (x) ス (1 + - 1 f(x 2
41
N
N
where n(()) = ply ||x = 2) is the Bayes regressor and is the number of groups X
Consequently, if the original classifier is Bayes consistent and have: N oo, Y + 0* and 7N-3 + co, then Ei,,, (x) + f. Ex)"(x) + y]. Hence, the updates converge to the optimal prediction rule subject the chosen fairness constraint.
Running time As shown in Appendix B the update rules in Equation stochastic gradient descent on the following optimization problem:
2 perform projected
min (M1 (A.
F= Ex (A,(s) (5 (bam)) (4)
- (s))))
We assume with no loss of generality that ((x) E [-1, 1, 1] since f (xx) is assumed to be an estimator to
21)(z) - 1 (see Section 3 and Appendix B and any thresholding rule over f(r) can be transformed
into an equivalent rule over a monotone increasing function of f (i.e. using the hyperbolic tangent).
and write p(t),(()) E R for the value of the optimization variables after updutes defined in Equation [ some fixed learning rate = a. Let jt.
Proposition Let eم) ())
(1/T) E (1)) and Ā (1/T) ΣL x(1) Then,
[[F] F(x))) < (1 (1+p+c)
|| +
(5)
2Ta
where F: R.K. x K TR. is the objective function in
( using the averaged solution and X while F* is its optimal value. In particular, E|F] F(u")) O(/K/T) when O(/K/T).
The proof is in Appendix D Hence, the post-prost post-processing rule can be efficiently computed. In practice, observe fast convergence shown in (
As shown in Figure a),, the hyperparameter y controls the width of randomization around the thresholds. A large value of 7 may reduce the accuracy of the classifier. On the other hand, ?
5

---

Under review as a conference paper at ICLR 2021
Bias
Dataset
Classifier
Original
Proposed
Hardt et al.
2016
Shift Inference
ROC
RF
.38 1: .02
.01 +: .003
011 1 0003
.16 + .011
.02 1 .002
KNN
.24 19:::00 .02
.02 + .005
.01 + .004
.08 + .006
.08 .006
.006
ADULT
MLP
.29
+
.02 =
.10 .012
.02 .003
LR
.39 .02
.11 + .004
.02 = .077
.10 .020
.01 = .002
.07 .03
+ .01 .005
.01 = .002
.09 +010
.02 .004
KNN
.10 -2
.01 = .001
+
.02 + .005
MLP
.13 .02
.01 + 005
.01 = .003
12
.02 - .003
LR
.12 .02
.01 + .003
.01 0011
113 .003
.01 = .003
Test error
Dataset
Classifier
Original
Proposed
Hardt et al.
2016
Shift Inference
ROC
RF
34.1%.2%
35%
38.0.1.
34.5.1.1%
36.0.1.3%
&NN
39.911.%%
39.711.2%
42.0.1.2%
39.2:1.2%
39.51.22%
ADULT
MLP
34.8.1.1%
36.8.1.1%
37.4.1.2%
35.7.1.2%
36.3.1.1%
LR
35.3+.1%
36.6 .2%
38.8
35.9 1%
36.5+.2%
RF 18.811.2%
18.2.1.1%
19.4..2%
19.0.1.1%
18.511.%%
KNN
20.4.1.%%
19.6.1.2%
21.31..1%
22.7:1.2%
19.6.1.2%
CDDD
MLP 19.5#.1%
18.7:.2%
21.21.2%
19.4:.1%
19.0%t2%
LR
19.4:.2%%
18.3
21.7
19.8t..2%
19.5
Table 1: A comparison of the four post- post-processing methods on two datasets with four different original classifiers Only the proposed algorithm and the algorithm of Hardt et al.) (2016) eliminate bias in all cases whereas ROC can fail in ANN (c.g. ADULT dataset) because debiasing kNN can require randomization at the thresholds. Bias here the absolute difference mean outcomes across the sensitive attribute (Definition
cannot zero because randomization around the threshold is, general, necessary for Bayes risk consistency illustrated in the following example:
Example (Randomization necessary). Suppose that = (-1,0, where p(x - 1/2.
p(x 0) = 1/3 and p(x = 1) 1/6. Let 17(-1) 0, 17(0) = 1/2 and 1)(1) = In addition, let
s E [0, be a sensitive attribute, where p(s 1|x = -1) =11==10 1/2. p(s = 1xx = 0) = 1, and p(s
1x = 1) O. Then, the Bayes optimal prediction rule (z) subject to statistical parity (c 0)
satisfies: (xf 1 = 1) = 0, p(f (x) = 1|x = 0) = 7/10 and p(f = 1
1.
Note that the Bayes excess risk bound in Theorem 2 is vacuous when y 0. Therefore, y controls a trade-off depending on how crucial randomization around the thresholds (e.g. in k-NN where the classifter's scores come from finite set in deep neural networks that tend to produce scores concentrated around (-1, +1}). our experiments, y is always chosen using a validation set.
EMPIRICAL EVALUATION
Experiment Setup We compare against three post-processing methods: (1) the post-processing algorithm of Hardt et al. (016) (2) the shift inference method, first introduced in (Saerens et al. 2002) and used more recently in (Wang et al. 2020). and (3) the Reject Option Classifirr (ROC) (Kamiran et al. 2012). We use the implementation of the algorithm of Hardt et al. (2016) in the Fair- Learn software package (Dudik al. 2020 The training data used for the post-processing meth- ods is always fresh sample, i.e. different from the data used to train the original classifiers. The value of the hyper-parameter 9 of the ROC algorithm is chosen in the grid (0.01, 0.02, ..., 1.0). When ROC fails, its solution with the minimum bias is reported. In the proposed algorithm. the parameter y is chosen the grid (0.01, 0.02, 0.05. 0.1, 0.2, 1.0) while is chosen the gird Ely) + (0, 0.05, 0.1). All papee-parameters selected based separate validation dataset.
Tabular Data We empirically evaluate the performance of the proposed algorithm and the base- lines two real-world datasets, namely the Adult income dataset and the Default of Credit Card

---

Under review as a conference paper at ICLR 2021
0.68
RF
KNN
MLP
LR
Algorithm
Adult
0.63
Proposed
Hardt, et al. 2016
ROC
0.58
0.2
0.4
0.2
0.4
0.2
0.4
0
0.2
0.4
0.84
RF
KNN
MLP
LR
Algorithm
CDDD
0.81
Proposed
Hardt, et al. 2016
ROC
0.78
0.2
0.4
0.2
0.4
0.2
0.4
0.2
0.4
0.80
Res/ett50/ccatcch
Resheet50/mmgeriit
Mobileteet/Scraech
Mobilitteet/lageete
CelebA
Algorithm Proposed Hardt, et 2016 ROC
0.70
0.60
Figure 3: The tradeoff curves are displayed for each classification problem. The x-axis corresponds to bias (Definition[]) I while the y-axis is the test accuracy. In general, debiasing CDDD improves test accuracy because blas introduced the training data only. In addition, ROC fails at debiasing four classifiers (see also Tables] and 2 due to the absence of randomization.
Clients (DCCC) dataset, both taken from the UCI Machine Learning Repository (Blake and Merz, 1998). The Adult dataset contains 48,842 records with 14 attributes each and the goal is to predict the income of an individual exceeds $50K per year. The DCCC dataset contains 30,000 records with 24 attributes, and the goal is predict if a client will default their credit card payment. Both datasets include sensitive attributes, such as sex and age. In Figure [ we showcased why, in some cases, the sensitive attribute be the cross product of multiple features (e.g. religion, gen- der, and race). our experiments in this section, we define the sensitive class to be the class of females. In the DCCC dataset, additionally introduce bias in the training for the purpose of the experiment: (x) = y(x) we keep the instance and otherwise drop it with probability 0.5.
We train four classifiers each dataset: (1) random forests with maximum depth 10, (2) k-NN with & = 10, (3) a two-layer fully connected neural network with 128 hidden nodes, and (4) logistic regression. For the latter, we fine-tune the parameter C grid of values chosen in a logarithmic scale between 10-4 and 10t using 10-fold cross validation. The learning rate in our algorithm is fixed to (K/T)/) where T is the number of steps, and e 0.
Table D shows the bias and accuracy on test data after applying each post-processing method. The column marked as "original" corresponds to the original classifier without any alteration. As shown the table, both our proposed algorithm and the algorithm of Hardt al. (2016) eliminate bias in all classifiers. By contrast, the shift-inference method does not succeed at controlling statistical parity while the ROC method can fail when the output of the original classifier discrete, such as in ANN, because it does not learn to randomize. Moreover, the proposed algorithm has a much lower impact on the test accuracy compared to Hardt et al. (2016) and can even improve in certain cases. The fact that fairness can sometimes improve accuracy recently noted by Blum and Stang] (2020) The full tradeoff curves between bias and performance are provided in Figure
CelebA Dataset Our second set of experiments builds on the task of predicting the "attractive- ness" attribute in the CelebA dataset (Liu al.) 2015). CelebA contains 202,599 images of celebri- ties annotated with 40 binary attributes, including gender. We use two standard deep neural network architectures: ResNet50 (He et al. 2016) and MobileNet (Howard et al. 2017). trained from scratch or pretrained on ImageNet. We present the results in Table 2 We observe that the proposed algo- rithm significantly outperforms the post-processing algorithm of Hardt et al. (2016) and performs, at least, well as the ROC algorithm whenever the latter algorithm succeeds. Often, however, ROC fails at debiasing the deep neural networks because does not learn to randomize when most scores produced by neural networks concentrated around the set {-1, +1).

---

Under review as a conference paper at ICLR 2021
Bias
Model
Training
Original
Proposed
Hardt
2016)
Shift Inference
ROC
SCRATCH
.43
.01
.01
.38
.08
RESNET50
IMAGENET
.40
.02
.01
.35
.15
SCRATCH
.35
.24
MOBILENET
IMAGENET
.38
.002
.002
.34
.10
Test error
Model
Training
Original
Proposed
Hardt et al. (2016)
Shift Inference
ROC
SCRATCH
22.2%
28.7% 7%
34.1%
37.8%
26.9%
RESNET5O
IMAGENET
20.3%
28.3%
32.5%
20.7%
22.8%
SCRATCH 23.1%
28.2%
33.6%
24.1%
28.3%
MOBILENET
IMAGENET
20.7%
27.2%
32.5%
21.0%
24.5%
Table 2: A comparison of the four post-processing methods on CelebA (predict attractiveness) ap- plied to the output of ResNet50 and MobileNet, each trained either from scratch or on ImageNet. The proposed algorithm performs much better than ROC in terms of bias and much better than Hardt al. (2016) in terms accuracy. Shift inference performs poorly both objectives.
Females
Males
Frequency
Proposed
Frequency
Proposed
Hardt, et al. 2016
Hardt, et al. 2016
10-2
10-2
10-5
10-5
-1.0
-0.5
0.0
0.5
-1.0
-05
1.0
2p(y=1|x)
2p(y=1|x)
Figure 4: The distribution of the scores produced by ResNet50 trained from scratch are shown for both subpopulations. The curves correspond to the randomized post-processing rules, ie. p(y 1 x)), of Hardt et al. (2016) and the proposed algorithm with y = 0.1 and EEy]]
We investigated the strong performance compared to that of Hardt al. (2016) and found that it due to the specific form of randomization used by the proposed algorithm. As shown in Figure the post-processing algorithm of Hardt al. (2016) uses fixed probability when randomizing between two thresholds. For CelebA trained from scratch, for example, the post-processing rule of Hardt et al. (2016) predicts nearly uniformly random when ResNet50 predicts the negative class for males. In contrast, our algorithm uses a ramp function that takes the confidence of the scores into account. In Figure in particular, the male instances with scores close to -1 are flipped with probability = 0.15, as opposed to ~ 0.5 in Hardt et al. (2016), and this difference is compensated for by flipping all examples with scores larger than -0.9 and all female instances with scores less than R 0.9. Hence, less randomization is applied when the original classifier is more confident.
Lastly, one important observation we note Table is the impact of pre-training - pretraining in our experiments helps in achieving lower test error rate even after eliminating bias. In other words, pretraining seems to reduce the cost of debiasing trained models.
CONCLUDING REMARKS
In this paper, we propose near-optimal post-processing algorithm for debiasing trained machine learning models. The proposed algorithm is scalable, does not require retraining the classifiers, and has a limited impact on the test accuracy. In addition to providing strong theoretical guarantees, we show that it outperforms previous post-processing methods for unbiased classification on standard benchmarks across classical and modern machine learning models.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
M. A. Bruckner, "The promise and perils of algorithmic lenders' use of big data," Chi.-Kent L. Rev., 2018.
R. Deo, "Machine learning in medicine," Circulation, 2015.
T. Brennan, W. Dieterich, and B. Ehret, "Evaluating the predictive validity of the COMPAS risk and needs assessment system," Criminal Justice and Behavior, 2009.
E. Awad, S. Dsouza, R. Kim, Schulz, J. Henrich, A. Shariff, J.-F. Bonnefon, and I. Rahwan, "The moral machine experiment," Nature, 2018.
J. Kleinberg, S. Mullainathan, and M. Raghavan, "Inherent trade-offs in the fair determination of risk scores," 2017.
D. Ingold and S. Soper, "Amazon doesnt consider the race of its customers. should it," Bloomberg News, 2016.
C. Dwork, M. Hardt, T. Pitassi, O. Reingold, and R. Zemel, "Fairness through awareness"" in Inno- vations in Theoretical Computer Science, 2012.
M. B. Zafar, I. Valera, M. Gomez Rodriguez, and K. P. Gummadi, "Fairness beyond disparate treat- ment disparate impact: Learning classification without disparate mistreatment," Interna- tional Conference on World Wide Web, 2017.
M. Hardt, E. Price, N. Srebro et al., "Bquality of opportunity in supervised learning." in Advances in Neural Information Processing Systems, 2016.
A. Chouldechova, "Fair prediction with disparate impact: A study of bias in recidivism prediction instruments." Big data, 2017.
Dixon, J. Li, J. Sorensen, Thain, and Vasserman, "Measuring and mitigating unintended bias in text classification," in Conference on AI, Ethics, and Society, 2018.
S. Corbett-Davies, E. Pierson, A. Feller, S. Goel, and A. Huq, "Algorithmic decision making and the cost of fairness," in International Conference on Knowledge Discovery and Data Mining, 2017.
N. Mehrabi, F. Morstatter, N. Saxena, K. Lerman, and A. Galstyan, "A survey on bias and fairness in machine learning." arXiv preprint arXiv:1908. 09635, 2019.
C. Blake and C. J. Merz, "UCI repository of machine learning databases," Irvine, CA, 1998.
M. B. Zafar, Valera, M. Hoomez-Rorrguuee and K. P. Gummadi, "Faireess Constraints: A Flexible Approach for Fair Classification," Journal of Machine Learning Research, 2019.
R. Zemel, Y. Wu, K. Swersky, T. Pitassi, and C. Dwork, "Learning fair representations," in Interna- lional Conference on Machine Learning, 2013.
K. Lum and J. Johndrow, "A statistical framework for fair predictive algorithms." arXiv preprint arXiv:1610.08077, 2016.
Bolukbasi, K.-W. Chang, J. Y. Zou, V. Saligrama, and A. T. Kalai, "Man is to computer program- mer as woman is to homemaker? debiasing word embeddings." in Advances in Neural Informa- tion Processing Systems, 2016.
F. Calmon, D. Wei, B. Vinzamuri, K. N. Ramamurthy, and K. R. Varshney, "Optimized pre- processing for discrimination prevention." Advances in Neural Information Processing Sys- tems, 2017.
D. Madras, E. Creager, T. Pitassi, and R. Zemel, "Learring adversarially fair and transferable repre- sentations," in International Conference on Machine Learning, 2018.
Kamiran and T. Calders, "Data preprocessing techniques for classification without discrimina- tion," Knowledge and Information Systems, 2012.

---

Under review as a conference paper at ICLR 2021
"Classifying without discriminating," in International Conference Computer, Control and Communication, 2009.
Locatello, G. Abbati, T. Rainforth, S. Bauer, B. Schölkopf, and O. Bachem, "On the fairness of disentangled representations," in Advances in Neural Information Processing Systems, 2019.
B. H. Zhang, B. Lemoine, and M. Mitchell, "Mitigating unwanted biases with adversarial learning." in Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, 2018.
N. Grgié-Hlača, M. B. Zafar, K. P. Gummadi, and A. Weller, "Beyond distributive faimeess in algo- rithmic decision making: Feature selection for procedurally fair learning." in AAAI Conference on Artificial Intelligence, 2018.
A. Agarwal, A. Beygelzimer, M. Dudik, J. Langford, and H. Wallach, "A reductions approach to fair classification," International Conference on Machine Learning, 2018
A. K. Menon and R. C. Williamson, "The cost of fairness in binary c Conference on Fairness, Accountability and Transparency, 2018.
L. E. Celis, L. Huang, V. Keswani, and N. K. Vishnoi, "Classification with faimess constraints: A meta-algorithm with provable guarantees," in Conference on Fairness, Accountability, and Trans- parency, 2019.
B. Fish, J. Kun, and Á. D. Lelkes, "A confidence-based approach for balancing fairness and accu- racy," in International Conference on Data Mining, 2016.
B. Woodworth, S. Gunasekar, M. I. Ohannessian, and N. Srebro, "Learning non-discriminatory predictors," arXiv preprint 1xXvx/702.000000 2017.
F. Kamiran, A. Karim, and X. Zhang, "Decision theory for discrimination-awware classification," " in 2012 IEEE 12th International Conference on Data Mining. IEEE, 2012, pp. 924-929.
L. Bottou, "Large-scale machine learning with stochastic gradient descent," in International Con- ference on Computational Statistics, 2010.
M. B. Zafar, I. Valera, M. G. Rogriguez, and K. P. Gummadi, "Fairesss Constraints: Mechanisms for Fair Classification,"" " in Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 2017.
J. Platt et al., "Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods," Advances in Large Margin Classifiers, 1999.
C. Guo, G. Pleiss, Y. Sun, and K. Q. Weinberger, "On calibration of modern neural networks," in International Conference Machine Learning, 2017.
V. Nair and G. E. Hinton, "Rectified linear units improve restricted boltzmann machines," in Inter- national Conference on Machine Learning, 2010.
H. Xu and S. Mannor, "Robustness and generalization," 2010.
M. Saerens, P. Latinne, and C. Decaestecker, "Adjusting the outputs of a classifier to new a priori probabilities: simple procedure," Neural Computation, 2002.
Z. Wang, K. Qinami, C. Karakozis, K. Genova, P. Nair, K. Hata, and O. Russakovsky, "Towards faimess in visual recognition: Effective strategies for bias mitigation," in Conference on Computer Vision and Puttern Recognition, 2020.
M. Dudik, Edgar, B. Horn and R. Lutz, "fairlearn 0.4.6," 2020. [Online]. Available:
https://yyp.oorghrojeehhaaaaaa
A. Blum and K. Stangl, "Recovering from biased data: Can faireess constraints improve accuracy?" FROC, 2020.
Z. Liu, P. Luo, X. Wang, and X. Tang, "Deep learning face attributes in the wild," in International Conference Computer Vision, 2015.
10

---

Under review as a conference paper at ICLR 2021
K. He, X. Zhang, S. Ren, and J. Sun, "Deep residual learning for image recognition," in Conference on Computer Vision and Pattern Recognition, 2016.
A. G. Howard, M. Zhu, B. Chen, D. Kalenichenko, W. Wang, T. Weyand, M. Andreetto, and H. Adam, "Mobilenets: Efficient convolutional neural networks for mobile vision applications." arXiv preprint arXiv: 17X.::7704.0866,, 2017.
S. Boyd and A. Mutapcic, "Stochastic subgradient methods." 2008. [Online]. Available: wwt.://sesaototllllmmaaaallllaee
stoch_subgrad_nont notes.ppff
Boyd and L. Vandenberghe, Convex optimization. Cambridge University Press, 2004.

---

Under review as a conference paper at ICLR 2021
A FULL ALGORITHM
Algorithm 1: A Pseudocode of the Proposed Algorithm for Conditional Statistical Parity.
Data: y > 0; e [o, 1); e 2 0; f X + +1:+8 8: X + [K]
Result: Optimal values of thresholds: Jr),,...... (Ak, .K).
Training: Initialize (1), (Av,, (x) to zeros. Then, repeat until convergence:
1. Sample instance ~ p(2)
2. Perform the updates:
Au(s) +- max {0, Aa(x) - ( +- 22.00
(f((x) (Au(1 - -Mass)))
[a((] f max (D, (a(x)) - 17 1 p+ 5, (f(x) (Dats0 - Ma(s)))
(p.(s
where Ey is given by Eq.
Prediction: Given an instance in the group Xs, predict the label +1 with probability:
0.
f(a) S A psk
h(x)=
(f(z) (A+ p2))/T,
d p f(x) S ph: +Y
f(z) 2 x 1* +7
B PROOF OF THEOREM
B. CONSTRAINED CONVEX FORMULATION
Suppose we have binary classifier on the instance space X. We would like to construct an algorithm for postpprocessing the predictions made by that classifier such that control the bias with respect to set of pairwise disjoint groups X1, .I,...: Xx C according to Definition T We assume that the output of the classifier X - [-1, +1] is estimate to (n)2z) 1, where ()x) = p(y 1|x x) the Bayes regressor. This is not a strong assumption because many algorithms can be calibrated
to provide probability scores (Platt et al. 1999 Guo et al. 2017) so the assumption is valid. We
consider randomized rules the form:
h X (1, K) x 1- [0,
whose arguments are: (1) the instance E X. (2) the sensitive attribute s(x) E [K]. and (3) the original classifier's score fz)). Because randomization is sometimes necessary as proved in Section (x)) is the probability predicting the positive class when the instance is x E X.
Suppose we have a training sample of size N, which we will denote by S. Let q, = h(x,) E [0, 1] for the i-th instance in S. For each group X₁ C S, the fairness constraint in Definition [ over the training sample can be written as:
Σ tEXX
<
Xx
2'
for some hyper-paramest > 0. This holds by the triangle inequality.
To learn f. we propose solving the following regularized optimization problem:
min 05
Σ (6/2) f(x.) q s.t. VX E::
Σ
pl S c
(6)
TEX1
where 7 > 0 is regularization parameter and c c/2l
B.2 REDUCTION TO UNCONSTRAINED OPTIMIZATION
Because the groups X₁ are pairwise disjoint, the optimization problems in 6 decomposes into K
separate suboptimization problems, for each group Xς. Each sub-optimization problem can be
12

---

Under review as a conference paper at ICLR 2021
written in the following general form:
7 46 f1x))g
min oS S1
M
M
s.t.
Σ
(2iq: b) sc
Σ 1=1
(2: b) <
To recall, c' = Mc/2. The Lagrangian is:
L(g, a, B.).
Σ a -(azaa)) + A E (zeq: b) -6) - 1l) > (2:q: - b) + 5 + Σ 0:(:: - -1) -1)- Σ Bigs
Taking the derivative w.r.t. qi gives us:
qi 1 ( (A- (1-11)a - ai + 31)
Plugging this back, the dual problem becomes:
EGei b() -n)) (A + w)e' + Σ ai
min
q.
(f(z.) - -( -) as + 8i)
s.t.
2,H,
Next, we eliminate variables. By eliminating 33 we have:
Σ Ge + b(A - 14) + (A + 1))' + Σ ai
min
g.A.p.
1 (f(x.) (A- -A-1)) oz)) 20
s.t.
4. 7
X, 0, 20
Equivalently:
Σ ΣGe + b() - -1)) + (A m)e' + Eai a
min a.
s.t.
a; 2 (x;) 7% (2 - -1)z
X, ,,,0 20 0
Next, we eliminate ag to obtain:
Σ
G b(A p)) + (A+m)e' + (((x)) 70 - -+)=]]]
min g.A.p
X
Finally, let's eliminate the q; variables. For a given optimal a and X, it straightforward to observe that the minimizer qº 7/29² + ww -7g]' must lie in the set {0, w/y, 1}. In particular, if w/y $ 0, then 9- = 0. If w/7 2 1. then qº = 1. Note here that we make use of the fact that y > 0.
So, the optimal value of q² to 7/24² + ww 79]* is:
w
< 0
(w)
u²
<
1
2-
2 1
From this, the optimization problem reduces to:
min Auz0
Σ 1=1
( - (1) + c(A +
+)) - -(A -1)=z))
(7)
13

---

Under review as a conference paper at ICLR 2021
This is differentiable objective function and can be solved quickly using the projected gradient descent method (Boyd and Mutapcic 2008). The projection step here is taking the positive parts of À and μ. This leads the update rules in Algorithml]
What about the solution? Given À and 14, the solution of is a minimizer to;
2 [f(z)) 79, (A -=)=
As stated earlier, the solution is:
f(x,) S (A- -u)z
9: = (A-
7(x - u)2 $ f(x,) 2 (A - 11 +7 f(x;) 2 (A 1)² +7
(8)
So, we have a ramp function. In the proposed algorithm, we have 2; = 1 and for all examples. This proves Theorem T
C PROOF OF THEOREM 2
C.1 OPTIMAL UNBIASED PREDICTORS
We begin by proving the following result, which can be of independent interest.
Theorem 3. Let f arg min (0.1) [(I(f((x) # y}] be the Bayes optimal decision rule subject group-wise affine constraints the form Rl[E (x) f(x)
X&] for some fixed partition
X = Xx If wk X - and by E R are such that there exists a constant e E (0, 1) in which
((f())=1) will satisfy all the affine constraints, then f* satisfies p(f*(x) 1) [((((() >
4 + 1 (x), where Tπ(x) = ply = 1|x x) is the Bayes regressor, ta E [0 is
threshold specific to the group Xx X. and T [0.
Proof. Minimizing the expected misclassification error rate of a classifier f is equivalent to maxi- mizing:
[xf(x) + (1- f())) -1 -)] E [x) x
f(x)) (1 y)] EE E[ (2n(x) 1)] x] + E[1-7(x)
Hence, selecting that minimizes the misclassification error rate is equivalent to maximizing:
[x (21)(x)- 11]
Instead of maximizing this directly, we consider the regularized form first. Writing g(x) = 2n((x) 1, the optimization problem is:
(x/2)E[((x)* - Exf(x) [()] OSf())11
min
s.t. E[w((x) [x)] =
Here, focused optimization problems, one for each Xt. If there exists a constant E (0, 1) such that f(z) c satisfies all the equality constraints, then Slater's condition holds so strong duality holds (Boyd and Vandenberghe| 2004).
subset Xş because the optimization problem decomposes into K separate
The Lagrangian is:
(7/2)E[f(x)² - Exf(x) g(x)] + [(B[w(x) f(x)] 6) + Efa(x)(f(x) - 1)] -(xxx)
where (x), and μ the dual variables.
Taking the derivative w.r.t. the optimization variable f(z) yields:
>f(x) g(x) / p=(x)) axx) + ((x)
(10)
Therefore, the dual problem becomes:
max
-(27)- (x( - μ (x) axx) + (1 bμ - E[a(x)]
a(x),0(2)20
14

---

Under review as a conference paper at ICLR 2021
We use the substitution in Eq. (10) to rewrite it as:
min (n/2) Elf(x) by B[a(x)] a (()))
S.L.V. E X (z)) - g(z) v ( a()) 3(x)
Next, we eliminate the multiplier (z) by replacing the equality constraint with an inequality:
min (n/2) (x) + by + [[(((x))
a(2)20
s.L.V* E X g - (x) - -w((x) a(x) 0
Finally, since (x)) 2 0 and (2)) 2 g()) - -x(()) -uw(x), the optimal solution the minimizer to:
(x/2)E|ʃ(x)* + by + ElImax(O, g(x) - 7x(x) - (ww(x) f-
min
Next, let μ² be the optimal solution of the dual variable μ.. Then, the optimization problem over f decomposes into separate problems, one for each X. We have:
f(x)
arg min { FER (1/22)²² [g(x)) - yT - p² w<x)+*
Using the same argument in Appendix B deduce that f(x) is of the form:
0. f(x) 1 (1/h) (g(x) pt w(x))
g(x) μ w(x) S 0
g Pr w(xx)
otherwise
Finally, the statement of the theorem holds by taking the limit as 7 0+
C.2 EXCESS RISK BOUND
In this section, we write 'D to denote the underlying probability distribution and write S to denote the uniform distribution over the training sample (a.k.a. empirical distribution).
The parameter stated in the theorem is given by:
max kE((.2....KK
[x(h"(x) X Xn] + min RE(1,2....KK
[x(h"(x X Xs!)
Note that, by definition, the optimal classifier ht* that satisfies statistical parity also satisfies the constraint in (6) with this choice of p. Hence, with this choice of p, h² remains optimal among all possible classifiers.
Observe that the decision rule depends on only via f(x) E [-1,+1]. Hence, we write f(x). Since the thresholds are learned based on a fresh sample of data, the random variables are i.i.d.
In light of Eq.
9 we would like to minimize the expectation of the loss ((h,, x) -(()) (x)
(x)
-z qZ) ((z) for some function q [-1,+1] + [0, 1] of the form shown in [[). Note that
is 2(1 + Liisscits continuous within the same group and sensitive class. This is because the
thresholds are always in the interval [-1 - y, + 7]: otherwise moving beyond this interval would not change the decision rule.
Let hy be the decision rule learned by the algorithm. Using Corollary 5 in Xu and Mannor 2010 we conclude that with a probability of at least 1 1-66 8:
4 (1 )) - {
2(R + K) log + log (11)
Ep (h, x Es (h,, x)]| s inf
R21
N
Here, used the fact that the observations (xx are bounded in the domain [-1, and that can first partition the domain into groups X₃ (K subsets) in addition to partitioning the interval [-1,1] 1] into R smaller sub-intervals and using the Lipschitz constant. Choosing R = N and simplifying
gives us with a probability of at least 88:
4(2 !)
2K + 2 log 3
Ep (h, x)] Es x)]l 5
2
N
N
15

---

Under review as a conference paper at ICLR 2021
The same bound also applies to the decision rule h that results from applying optimal threshold with width y > 0 (here, "optimal" is with respect to the underlying distribution) because the e-cover (Definition 1 in (Xu and Mannor 2010) is independent of the choice of the thresholds. By the union bound, we have with a probability of at least - 6, both of the following inequalities hold:
4(2 1)
2K + 2 log
x)] - Es|((h,,))) x]]| -
+
(12)
N3
N
4(2 +
2K + 2 log N
ED | -es [s(((h,,,))] -[]
5
+1
(13)
N
In particular:
4(2 1
2K + 2 2log'
Ep x)] S Es(((h,, +
+ 2//
3
N
N
4(2 11)
2K + 2 2og
I Es(((b;, +
+ +
N
N
8(2 + 2)
2K + +lgog
EEp(i(h x)] + +
+ +//
N
N
The first inequality follows from Eq. 12. The second inequality follows from the fact that h, an empirical risk minimizer to the regularized loss, where [x] s since f(x) E [0, 1]. The last inequality follows from Eq. (3).
Finally, we know that the thresholding rule h with width y > is, by definition, a minimizer to:
(7/2) [[((x) -f fx))
among all possible bounded functions + [0, .] subject to the desired fairness constraints. Therefore, we have:
- (>) f(x)] (x/2) (x) - Ehh (x) f(x)
Hence:
Bii x)] = - Eh (x)) < 7 E((((h,,)) x)]
This implies the desired bound:
8(2 + 1 ED ED x)] S Ep Ep (o""[(hh,, x)] + 2y N
2K + 2 2og A
+ VV
N
Therefore, we have consistency N + xo, 7 + 0+ and >/3 co. For example, this holds
? ON.
So far, we have assumed that the output of the original classifier coincides with the Bayes regressor. If the original classifier is Bayes consistent, i.e. [
f(x)ll as N - co, then we have Bayes consistency of the post-processing rule by the triangle inequality.
D PROOF OF PROPOSITION I
Proof. Since (w)) < 1, the gradient at a point x during SGD has a square f--norm bounded by [[(1 + + c)2 at all rounds. Following the proof steps of (Boyd and Mutapcic 2008) and using the fact that projections are contraction mappings, one obtains:
1
E (1) F(())) < || + 11>~ + (1+ + p TT
T
27a
(1 +
||
1
2
2Ta
16

---

Under review as a conference paper at ICLR 2021
By Jensen's inequality, we have 1 Σl= B[F(]] yields:
S [[F(D)]. Plugging this into the earlier results
5 (1 (1+p+c)
||00|
11=111
E E| F(n*))
2
2Ta
E EXTENSION TO OTHER CRITERIA
E.1 CONTROLLING THE COVARIANCE
The proposed algorithm can, sometimes, be adjusted to control bias according to other criteria as well besides statistical parity. For example, we demonstrate in this section how the proposed post- processing algorithm can be adjusted to control the covariance between the classifier's prediction and the sensitive attribute when both are binary random variables.
Let a, b, e E {0, 1} be random variables. Let C(a, b) = Ela b] - E[a] E[b] be their covariance, and C(a, b c) their covariance conditioned on
C'a.b c= c) = Ela b c= = c] E
c) E c].
(14)
Then, one possible criterion for measuring bias to measure the conditional/uncondttonal covari- ance between the classifier's predictions and the sensitive attribute when both are binary random variables. Because the random variables are binary, it is straightforward show that achieving zero covariance implies independence.
Suppose we have a binary classifier on the instance space X. We would like to construct an algorithm for post-processing the predictions made by that classifier such that we guarantee [x()(x), (s(x) x E Xx)] I e, where X' = U is a total partition of the instance space. Infor- mally, this states that the fairness guarantee with respect the senstiive attribute 15 : X {0, 1} holds within each subgroup X₁-
We assume, again, that the output of the classifier f : X [-1, +1] is an estimate to 27)(x) 1, where 71x) ply = 1 1 2) is the Bayes regressor and consider randomized rules of the form:
h X {0, 1} K) [-1,
1] [0, 1].
whose arguments are: (i) the instance x X, (ii) the sensitive attribute 1s - (0.1) (iii) the sub-group membership
X [K]. and (iv) the original classifier's score f(x). Because
randomization is sometimes necessary as proved in Section (xx) is the probability of predicting the positive class when the instance is X.
Suppose we have training sample of size N, which will denote by S. Let 4 h(x,)) [0, I] for the i-th instance in S. For each group X S S. the desired fairness constraint on the covariance can be written as:
Eas(() px) q8 S
X
TEXx
where Pk = Ex(1s(x) X Xx). This is because:
Σ (1s(1) -pk) t
Σ ls(i) f(i)
Pk
Σ f(i)
XM
[&
[
iEX
Exls(x) f(x) x
Xx] x Elf(x) x Xa]
=C(((x) [x Xx),
where the expectation is over the training sample. Therefore, order to learn h, we solve the regularized optimization problem:
min 059.51
Σ (f f(zz) s.t. VX2 e 9::
Σ (Ls(1) pk) qil S e₁ (15) x
where > > 0 is a regularization parameter and é, = |X This is of the same general form analyzed in Section B.2 Hence, the same algorithm can be applied with b = 0 and 2, ss(i) Pk-
17

---

Under review as a conference paper at ICLR 2021
E.2 IMPOSSIBILITY RESULT
The previous algorithm for controlling covariance requires that the subgroups X be known in ad- vance. Indeed, our next impossibility result shows that this is, in general, necessary. In other words, a deterministic classifier f' : X' + {0, } cannot be universally unbiased with respect to a sensitive class S across all possible known and unknown groups unless the representation x has zero mutual information with the sensitive attribute or if f is constant almost everywhere. As corollary, the groups X5 have to be known advance.
Proposition 2 (Impossibilityy result). Let X' be the instance space and y = {0, 13 be a target set. Let 1s X - {0, 1) be an arbitrary (possibly randomized) binary-valued function on X and define y X + [0. 1] by ((x)) = p(1s(x) = 1 x), where the probability is evaluated
the randommess of 1s X [0, Write 7 [xx(((x)]. Then, for any binary predictor f: x + {0, 11 it holds that
sup (0,1)
(BZ( ((f(x),nx)) [(x)) 2
Ex (x))(x) - 71- Ef 117711-Ef1 Ef}. (16)
2
where (((xx))(x))))))))))))))))))))()) x(x) is defined in Equation 14
Proof. Fix 0 < B < 1 and consider the subset:
W {- E X (л(x) 7) (f(x) -f)((())))))) 3) 0},
and its complement W = X' \ W. Since f(x) E 1). the sets W and W are independent of B as
long as remains in the open interval (0, 1). More precisely:
(x) - 0 7(x)) - S
f(x)=1
W
Now, for any set X S X, let px be the projection of the probability measure p(x) on the set X (i.e. px(x)= = p(x)/p(X)). Then, with a simple algebraic manipulation, one has the identity:
Ex-px [x)(x) - 7) (f(x) - B]] = f X)+ (Ex~px - 7) (Exxpx [f] -3)
(17)
By definition of W, we have:
Ex-pw [(>(x) - (x()) - B)] Ex-pp (h(x) (x) - 31 2 min m (3, ExExp 1x(x) - -7
Combining this with Eq. 17 we have:
((x(x), [(x;; E W) 2 min 3---8 1x(x) -5 51+ (Ex~pw [7] -Bx (S] (18)
Since the set W does not change when 3 is varied in the open interval (0, 1), the lower bound holds
for any value of 3 E 1). W set:
B = f
E Ex~pu f(x) + Exxpa fxx)
(19)
Substituting the last equation into Eq. (18) gives the lower bound:
f(x;)) W) min f. f} Ex-p hnxx) - 71
(Bx-pw h]
(Ex~pw [(x) Ex-ry
(20)
2
Repeating the same analysis for the subset W, we arrive at the incquality: (():x) W) < min(ff. 1 - ʃ} Ex-ow 1x(x) -1
2 (Eumpw hl - 7) (Ex-pw f(x) Exmpre
(21)
Writing =(x) (at), we have by the reverse triangle inequality:
Em(x) (C(((x,, ((x); x(x)) 2 min(f, 1 ʃ} E. (x(x) -1
(22)
Finally:
2/ p(x W) Ex-pw (x) + p(x E W) -Ex-py f(x) EM
Similarly, we have 2(1 f) > 1 E[S] Therefore:
1
min ff, 1 f} 2 2 min(Ef, 1 1-
Combining this with Eq. establishes the statement of the proposition.
18


Reviews:
[{"review_id": "RUD0_h25-1Y", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Evaluation and improvement of fairness of machine learning algorithms is a very important issue. To this end, the authors of this paper propose a post-processing algorithm to enforce fairness in a narrowly defined notion of fairness. Unfortunately, I have serious concerns about the validity of the results and conclusions of the paper, and hence I cannot recommend the paper to be accepted.\n\n[**Definition**] This entire paper is only applicable to a narrow definition of fairness in Definition 1. Given that $a$ and $b$ are binary, Definition 1 (page 2) is essentially equivalent to assuming that $P[a= b =1 |c] = P[a= 1 |c]  P[b= 1 |c]$ which is weaker than the well-known demographic (statistical) parity, and is only applicable to a binary setting. Hence, the applicability of the proposed algorithm is extremely limited.\n\n[**Theory**] The theoretical exposure in this paper is confusing and not rigorous. The trouble begins from the unnumbered equation in page 4, where the authors define $\\widetilde{h}$. It is unclear what $\\widetilde{h}$ depends on. Also, the output is seemingly binary, but the authors claim this a _randomized prediction rule_ and $\\widetilde{h}(\\mathbf{x})$ represents the probability of predicting the positive class. **Proposition 1** is an obvious statement and not relevant to the claims of this paper, and hence should be removed. **Theorem 1:** In the proof of Theorem 1, the authors make an assumption about what the output of $f$ is. In different places the output is assumed to be in $[0,1]$ and $[-1, 1]$!! Even worse, they claim that the empirical average of some loss value is equal to its expectation (_what happened to generalization?_). That is where I stopped reading.\n\n[**Experiments**] The experiments are very weak and not convincing. The paper only compares with Hardt et al. but in an unconvincing way as detailed here. **(a)** the comparisons should be made in terms of a tradeoff curve between _fairness_ and _performance_. In the currently reported results, there are instances where Hard et al. and the proposed method are not comparable, e.g., kNN. **(b)** The comparisons are unfair because they are done with respect to Definition 1, which is a very narrow sense of fairness while Hard et al. impose fairness either with respect to _equalized odds_ or _equal opportiunity_  which require conditional independence of $\\widehat{Y}$ and $S$ given $Y (=1)$. Hence, the comparison with Hard et al. is unjustified. At the very least the authors should compare with a plethora of baselines designed for demographic parity (e.g., Kamiran et al. 2012, Zemel et al. 2013, Feldman et al. 2015, Zafar et al. 2017, Jiang et al. 2019, Baharlouei at al. 2020). Even then, the comparison should be done with respect to the statistical parity violation as defined in Dwork et al. 2012, which is a more established notion of fairness.\n\n===== after rebuttal =====\n\nI'd like to thank the authors for their revisions, which have significantly improved the readability of the paper, and the presentation of the results. The addition of fairness violation/accuracy tradeoffs and also (Kamiran et al. 2012) add a lot of value in putting this paper in the right context. After reading the rebuttal, I still remain unconvinced about the contributions of this paper. From a practical point of view, the performance of the proposed algorithm is on a par with (Kamiran et al. 2012), which is a baseline for demographic parity and has been improved on several times in the past 8 years. On the other hand, the main claim of the paper seems to be theoretical optimality. Unfortunately, although several previous mistakes have been corrected in the proofs, I cannot still follow the proofs of Theorems 1 and 2. New notation pops up all over the proof, and it is unclear how to follow some lines from the others. Given this, I am increasing my rating to 4 in acknowledgement of my previous misunderstanding of the definition of the statistical parity, which was cleared by the authors during the discussion period. However, I am still unable to recommend this paper in the current form for publication in the conference proceedings.", "extra_scores": {}, "extra_text": {}}, {"review_id": "LadiTNwuO_", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors propose a post-processing method for removing bias from a trained model. The bias is defined as conditional statistical parity — for a given partitioning of the data, the predicted label should be conditionally uncorrelated with the sensitive (bias inducing) attribute for each partition. The authors relax this strong requirement to an epsilon-constraint on the conditional covariance for each partition. As an example, race (sensitive attribute) should be conditionally uncorrelated to whether an individual will default on their loan (predicted target) for each city (data partition). The authors propose a constrained optimization problem that takes the input data, sensitive attribute, partitioning and a trained model to yield a probabilistic decision rule. Subsequently, they propose an iterative solution to the problem, proving some theoretical properties as well as showing how the method compares to different baselines.\n\nFairness is an important consideration as machine learning models find purchase in sensitive applications like loan approvals, job candidate filtering, compensation decisions, and so on. This clearly written paper summarizes the different ways of removing data bias, and proposes a sensible and fairly general post-processing solution. The paper is easy to follow, and while the main body skims on some details to assist readability (and adhere to the page limit), the appendix, which I only quickly scanned, is well-done. I did have some concerns:\n\n1. The assumption that “the original classifier outputs a monotone transformation of some approximation to the posterior probability p(y = 1 | x)” needs further justification since models often tend to be overconfident of the wrong predictions violating the monotonicity assumption [Guo, Chuan, et al. \"On calibration of modern neural networks.\" arXiv preprint arXiv:1706.04599 (2017)]. How central is this assumption to the analysis?\n\n2. In section 3 (Algorithm subsection) doesn’t \\tilde{h} represent probability? If so, the function range should be [0,1], and not {0,1}.\n\n3. Right below, a bar is missing in the absolute value: “can be written as |.| < \\epsilon”.\n\n4. Theorem 2 notation: h(x) \\neq y would be more cleanly written with an indication function: I(h(x) \\neq y).\n\n5. In baseline comparison, using only conditional statistical parity might be unfair to other methods which don’t optimize this notion of bias explicitly. Did you consider evaluating for other metrics?\n\nOverall, this is a well-written paper that tackles an important problem, and it would make for a good addition to the conference. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "CJfpSi4InBd", "reviewer": "AnonReviewer4", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers the fair classification problem with respect to conditional statistical parity. It proposes a near-optimal post-processing algorithm for debiasing trained machine learning models, including deep neural networks. The empirical results show that the algorithm outperforms existing post-processing approaches for fair classification. \n\nOverall, I vote for accepting. Existing post-processing algorithms usually lack theoretical guarantees but not this paper. My main concern is the clarity; see cons.\n\nPros:\n    1. The paper provides provable guarantees from both the impossible side and the algorithmic side.\n    2. The post-processing approach does not require retraining the classifiers, and the impact on the test accuracy is limited.\n\nCons:\n    1. Several symbols or notions lack explanations. E.g., what $\\gamma$ means in Eq. (1)? What $\\eta$ means in Eq. (2)?\n    2. Theorems lack explanations. E.g., in Theorem 2, it is better to explain each term of the right side, including why these terms exist and when they are small. \n    3. Equations lack explanations. E.g., why the update rules should be formulated as (2)? It is better to explain the intuition.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers feel this paper addresses and important topic, and has many merits. However, it is difficult to recommend publication at this time. The primary concern is that the paper has its theoretical optimality as an important contribution, but the reviewers and myself (in a non-public thread) were unable to verify the correctness of the proofs. In part unfortunately this is due to edits to the proofs happening late in the revision period, too late for further discussion with the authors. Some of the particular questions in the proof of theorem 1 (appendix B) include: clarifying the value of $\rho$ which makes the unnumbered equation above equation (6) equivalent to definition 1, and in particular whether the $1/|X_k|$ term should be inside or outside the absolute value; and clarifying various undefined symbols which are introduced in the equation at the top of page 13, but are never defined, including $M$, $b$, and $z_i$. Reviewers also had some concern that the algorithm should be benchmarked against more recent / better performant baselines than Kamiran et al. (2012).
Decision: Reject