A Near-Optimal Algorithm for Debiasing Trained Machine Learning Models
Year: 2022

Abstract:
We present a scalable post-processing algorithm for debiasing trained models, including deep neural networks (DNNs), which we prove to be near-optimal by bounding its excess Bayes risk. We empirically validate its advantages on standard benchmark datasets across both classical algorithms as well as modern DNN architectures and demonstrate that it outperforms previous post-processing methods while performing on par with in-processing. In addition, we show that the proposed algorithm is particularly effective for models trained at scale where post-processing is a natural and practical choice.

heading: 1 Introduction
text: Background. Machine learning is increasingly applied to critical decisions which can have a lasting impact on individual lives, such as for credit lending [Bruckner, 2018], medical applications [Deo, 2015], and criminal justice [Brennan et al., 2009]. Consequently, it is imperative to understand and improve the degree of bias of such automated decision-making.
Unfortunately, despite the fact that bias (or “fairness") is a central concept in our society today, it is difficult 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 universallyagreed upon definition for bias exists. Moreover, bias may depend on the application and might even be ignored in favor of accuracy when the stakes are high, such as in medical diagnosis [Kleinberg et al., 2016]. As such, it is not surprising that several measures of bias have been introduced, such as statistical parity [Dwork et al., 2012, Zafar et al., 2017a], equality of opportunity [Hardt et al., 2016], and equalized odds [Hardt et al., 2016, Kleinberg et al., 2016], and these are not generally mutually compatible [Chouldechova, 2017, Kleinberg et al., 2016].
Let X be an instance space and let Y = {0, 1} be the target set in a binary classification problem. In the fair classification setting, we may further assume the existence of a sensitive attribute s : X → {1, . . . ,K}, where s(x) = k if and only if x ∈ Xk for some total partition X = ∪kXk. For example, X might correspond to the set of job applicants while s indicates their sex. Then, a commonly used criterion for fairness is to require similar mean outcomes across the sensitive attribute (a.k.a. statistical parity) [Dwork et al., 2012, Zafar et al., 2017a, Mehrabi et al., 2019]: Definition 1 (Statistical Parity). Let X be an instance space and X = ∪kXk be a total partition of X . A predictor h : X → [0, 1] satisfies statistical parity across all groups X1, . . . , XK if:
max k∈[K] Ex[h(x) | x ∈ Xk]− min k∈[K] Ex[h(x) | x ∈ Xk] ≤ ,
where [K] denotes the set {1, . . . ,K}.
Our main contribution is to derive a near-optimal recipe for debiasing models, including deep neural networks, according to Definition 1. Specifically, we formulate the task of debiasing learned models
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
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 a regularization hyperparamter. We also prove that randomization near the threshold is, in general, necessary for Bayes risk consistency. In Appendix D, we show how the proposed algorithm can be modified to handle a weaker notion of bias as well. We refer to the proposed algorithm as Randomized Threshold Optimizer (RTO).
Besides the theoretical guarantees, we empirically validate RTO on benchmark datasets across both classical algorithms as well as modern DNN architectures. Our experiments demonstrate that the proposed algorithm significantly outperforms previous post-processing methods and performs competitively with in-processing (Section 5). While we focus on binary sensitive attributes in the experiments, our algorithm and its guarantees continue to hold for non-binary attributes as well.
In addition, we show that RTO is particularly effective for models trained at scale where postprocessing is a natural and practical choice. Qualitatively speaking, for a fixed downstream task D, such as predicting facial attributes in the CelebA dataset [Liu et al., 2015], we say that the model is “trained at scale" if it is both: (1) heavily overparameterized, and (2) pretrained on large datasets before fine-tuning on the downstream task D. We show that the impact of debiasing models on their performance using the proposed algorithm can be improved with scale.
Remark. Because “bias" is a societal concept that cannot be reduced to metrics such as statistical parity [Chouldechova, 2017, Dixon et al., 2018, Selbst et al., 2019], our conclusions do not necessarily pertain to “fairness" in its broader sense. Rather, they hold for the narrow technical definition of statistical parity. Similarly, we conduct experiments on standard benchmark datasets, such as CelebA [Liu et al., 2015] and COCO [Lin et al., 2014], which are commonly used in the literature, as a way of validating the technical claims of this paper. Our experiments are, hence, not to be interpreted as an endorsement of those visions tasks, such as predicting facial attributes.

heading: 2 Related Work
text: Algorithms for fair machine learning can be broadly classified into three groups: (1) pre-processing methods, (2) in-processing methods, and (3) post-processing methods [Zafar et al., 2019].
Preprocessing algorithms transform the data into a different representation such that any classifier trained on it will not exhibit bias. This includes methods for learning a fair representation [Zemel et al., 2013, Lum and Johndrow, 2016, Bolukbasi et al., 2016, Calmon et al., 2017, Madras et al., 2018, Kamiran and Calders, 2012], label manipulation [Kamiran and Calders, 2009], data augmentation [Dixon et al., 2018], or disentanglement [Locatello et al., 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 training [Zhang et al., 2018] and constraintbased classification, such as by incorporating constraints on the decision margin [Zafar et al., 2019] or features [Grgić-Hlača et al., 2018]. Agarwal et al. [2018] showed that the task of learning an unbiased classifier could be reduced to a sequence of cost-sensitive classification problems, which could be applied to any black-box classifier. One caveat of the latter approach is 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 a post-processing method, which can be justified theoretically [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 twostage approach that requires changes to the original training algorithm. Kamiran et al. [2012] also proposes a post-processing algorithm, called Reject Option Classifier (ROC), without 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 to randomize around the threshold (Figure 1(a)) and this randomization is key to our algorithm both theoretically as well as experimentally (Appendix B and Section 5). Hardt et al. [2016] learns a randomized post-processing rule but our proposed algorithm outperforms it in all of our experiments (Section 5). Also, [Wei et al., 2019] is a post-processing method but it requires solving a non-linear optimization problem (for the dual variables) via ADMM and provides guarantees for approximate fairness only.
Woodworth et al. [2017] showed that the post-processing approach can be suboptimal. Nevertheless, the latter result does not contradict the statement that our post-processing rule is near-optimal because we assume that the original classifier outputs a score (i.e. a monotone transformation of an approximation to the posterior p(y = 1 | x) such as margin or softmax output) whereas Woodworth et al. [2017] assumed 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 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 a proxy, such as the margin as in some previous works [Zafar et al., 2017b, 2019]. Third, unlike previous reduction methods that would require retraining a deep neural network several times until convergence [Agarwal et al., 2018], which can be prohibitively expensive, our algorithm does not require retraining. Also, post-processing can be the only available option, such as when using machine learning as a service with out-of-the-box predictive models or due to various other constrains in data and computation [Yang et al., 2020b].

heading: 3 Near-Optimal Algorithm for Statistical Parity
text: Notation. We reserve boldface letters for random variables (e.g. x), small letters for instances (e.g. x), capital letters for sets (e.g. X), and calligraphic typeface for universal sets (e.g. the instance space X ). Given a set S, 1S(x) ∈ {0, 1} is its characteristic function. Also, we denote [N ] = {1, . . . , N} and [x]+ = max{0, x}. We reserve η(x) for the Bayes regressor: η(x) = p(y = 1 | x = x).
Algorithm. Given a classifier outputting a probability score p̂(y = 1 | x = x), let f(x) = 2p̂(y = 1 | x = x) − 1. We refer to f(x) ∈ [−1, +1] as the classifier’s output. Our goal is to post-process the predictions made by the classifier to control statistical parity with respect to a sensitive attribute s : X → [K] according to Definition 1. To this end, instead of learning a deterministic rule, we consider randomized prediction rules h(x), where h(x) is the probability of predicting the positive class given f(x) and s(x). Note that we have the Markov chain: x→ (s(x), f(x))→ h(x). A simple approach of achieving statistical parity is to output a constant prediction in each subpopulation, which is clearly suboptimal in general. As such, there is a tradeoff between accuracy and fairness. The approach we take in this work is to modify the original classifier such that the original predictions are matched as much as possible while satisfying the fairness constraints. Minimizing the probability of altering the binary predictions of the original classifier can be achieved by maximizing the inner product Ex[h(x) ·f(x)] (cf. Appendix B). However, maximizing this objective alone leads to deterministic thresholding rules which have a major drawback as illustrated in the following example. Example 1 (Randomization is necessary). Suppose that X = {−1, 0, 1} where p(x = −1) = 1/2, p(x = 0) = 1/3 and p(x = 1) = 1/6. Let η(−1) = 0, η(0) = 1/2 and η(1) = 1. In addition, let s ∈ {0, 1} be a sensitive attribute, where p(s = 1|x = −1) = 1/2, p(s = 1|x = 0) = 1, and p(s = 1|x = 1) = 0. Then, the Bayes optimal prediction rule h?(x) subject to statistical parity ( = 0) satisfies: p(h?(x) = 1|x = −1) = 0, p(h?(x) = 1|x = 0) = 7/10 and p(h?(x) = 1|x = 1) = 1.
As a result, randomization close to the threshold is necessary in the general case to achieve Bayes risk consistency. This conclusion in Example 1 remains true with approximate fairness ( < 12/70). In this work, we propose to achieve this by minimizing the following regularized objective for some hyperparameter γ > 0: (γ/2)Ex[h(x)2] − Ex[h(x) · f(x)]. (4) We prove in Appendix A that this regularization term leads to randomization around the threshold, which is critical, both theoretically (Section 4 and Appendix B) and experimentally (Section 5). Informally, γ controls the width of randomization as illustrated in Figure 1.
Let X = ∪kXk be a total partition of the instance space according to the sensitive attribute s : X → [K]. Denote a finite training sample by S = {(x1, y1), . . . , (xN , yN )} and write Sk = S ∩Xk. For each group Sk, the fairness constraint in Definition 1 over the training sample can be written as:
1
|Sk| ∣∣∣ ∑ xi∈Sk (h(xi)− ρ) ∣∣∣ ≤ 2 , (5)
for some hyper-parameter ρ ∈ [0, 1]. Precisely, if the optimization variables h(xi) satisfy the constraint (5), then Definition 1 holds over the training sample by the triangle inequality. Conversely,
Algorithm 1: Pseudocode of the Randomized Threshold Optimizer (RTO).
Input: γ > 0; ρ ∈ [0, 1]; ≥ 0; f : X → [−1, 1]; s : X → [K] Output: Prediction rule: hγ(x) Training: Initialize (λ1, µ1), . . . , (λK , µK) to zeros. Then, repeat until convergence:
1. Sample an instance x ∼ p(x) 2. Perform the updates:
λs(x) ← [λs(x) − ηgλs(x) ] +, µs(x) ← [µs(x) − ηgµs(x) ] + (1)
where: gλs(x) =
2 + ρ+
∂ ∂λs(x) ξγ ( f(x)− (λs(x) − µs(x)) ) gµs(x) =
2 − ρ+ ∂ ∂µs(x) ξγ ( f(x)− (λs(x) − µs(x)) ) .
and:
ξγ(w) = w2
2γ · I{0 ≤ w ≤ γ} +
( w − γ
2
) · I{w > γ} (2)
Prediction: Given an instance x in the group Xk, predict the label +1 with probability hγ(x), where: hγ(x) = [ min{1, (f(x)− λk + µk)/γ ]+ (3)
if Definition 1 holds, then the constraint (5) also holds where: 2ρ = max
k∈[K] Ex[h(x) | x ∈ Sk] + min k∈[K] Ex[h(x) | x ∈ Sk].
Therefore, to learn the post-processing rule h(x), we solve the optimization problem:
min 0≤h(xi)≤1
∑ xi∈S (γ/2)h(xi) 2 − f(xi)h(xi)
s.t. ∀k ∈ [K] : ∣∣ ∑ xi∈Sk (h(xi)− ρ) ∣∣ ≤ k, (6)
in which k = |Sk| /2 for all k ∈ [K]. Using Lagrange duality we show in Appendix A that solving the above optimization problem is equivalent to Algorithm 1. In Appendix D, we show that if = 0, an alternative formulation can be used to minimize the same objective while satisfying the fairness constraint but without introducing a hyperparameter ρ. To reiterate, ρ ∈ [0, 1] is tuned via a validation dataset and γ > 0 is a hyperparameter that controls randomization.

heading: 4 Theoretical Analysis
text: Our first theoretical result is to show that RTO satisfies the desired fairness guarantees. Theorem 1 (Correctness). Let hγ : X → [0, 1] be the randomized predictor in Equation 3 learned by applying the update rules in Equation 1 on a fresh sample of size N until convergence with learning rates satisfying the Robbins and Monro condition [Robbins and Monro, 1951]. Then, hγ satisfies statistical parity on the training sample. Moreover, with a probability of at least 1− δ, the following bound on bias holds w.r.t. the underlying distribution:
max k∈[K] E[h(x) | x ∈ Xk] − min k∈[K] E[h(x) | x ∈ Xk] ≤ + 8 √ 2 log eN2 N + 2 √ log 2Kδ N . (7)
Proof. The proof is in Appendix A. We make use of strong duality, which holds by Slater’s condition [Boyd and Vandenberghe, 2004]. The update rules correspond to the projected SGD method on the dual problem. This establishes the guarantee on the training sample. For the underlying distribution, we bound the Rademacher complexity [Bousquet et al., 2003] of the function classHγ of Figure 1(a) by that of 0-1 thresholding rules over R, from which a generalization bound is derived.
The following guarantee shows that the randomized prediction rule converges to the Bayes optimal unbiased classifier if the original classifier is Bayes consistent. Theorem 2. Let h? = arg minh∈H E[h(x) 6= y], whereH is the set of binary predictors on X that satisfy fairness on the training sample according to Definition 1 for ≥ 0. Let hγ : X → [0, 1] be the randomized rule in Algorithm 1. If hγ is trained on a fresh data of size N , then there exists a value of ρ ∈ [0, 1] independent of N such that the following holds with a probability of at least 1− δ:
E[I{hγ(x) 6=y}] ≤ E[I{h?(x) 6= y}] + 2γ + 8(2 + 1γ )
N 1 3
+ E|2η(x)− 1− f(x)|+ 4
√ 2K + 2 log 2δ
N ,
where η(x) = p(y = 1|x = x) is the Bayes regressor and K is the number of groups Xk.
Proof. The full proof is in Appendix B. First, we show that minimizing the probability of error can be achieved by maximizing E[f(x) · (2η(x) − 1)]. We use the regularized loss instead, which is strongly convex. Using Lipschitz continuity of the decision rule when γ > 0 (cf. Figure 1(a)), and the robustness framework of Xu and Mannor [2012], we prove a generalization bound and proceed with a series of inequalities to establish the main theorem.
Thus, if the original classifier is Bayes consistent, namely E |2η(x)− 1− f(x)| → 0 as the sample size goes to infinity, and ifN →∞, γ → 0+ and γN 13 →∞, then E[hγ(x) 6= y]
P−→ E[h?(x) 6= y]. Hence, Algorithm 1 converges to the optimal prediction rule subject to the fairness constraints.
Convergence Rate. As we show in Appendix A, the update rules in Equation 1 perform a projected stochastic gradient descent on the following optimization problem:
min µ,λ≥0
F = Ex [ (λs(x) + µs(x)) + ρ (λs(x) − µs(x)) + ξγ(f(x)− (λs(x) − µs(x))) ] , (8)
where ξγ is given by Equation 2. The following proposition shows that the post-processing rule can be efficiently computed. In practice, we observe fast convergence as demonstrated in Figure 1(b). Proposition 1. Let µ(0) = λ(0) = 0 and write µ(t), λ(t) ∈ RK for the value of the optimization variables after t updates defined in Equation 1 for some fixed learning rate αt = α. Let µ̄ = (1/T ) ∑T t=1 µ (t)(x) and λ̄ = (1/T ) ∑T t=1 λ (t)(x). Then,
E[F̄ ]− F ? ≤ (1 + ρ+ )2α+ ||µ ?||22 + ||λ?||22
2Tα , (9)
where F̄ : RK × RK → R is the objective function in (8) using the averaged solution µ̄ and λ̄ while F ? is its optimal value. In particular, E[F̄ ]− F ? = O( √ K/T ) when α = O( √ K/T ).
The proof of Proposition 1 is in Appendix C. As shown in Figure 1(a), the hyperparameter γ controls the width of randomization around the thresholds. A large value of γ may reduce the accuracy of the classifier. On the other hand, γ cannot be zero because randomization around the threshold is, in general, necessary for Bayes risk consistency as shown earlier in Example 1.

heading: 5 Experiments
text: Baselines and Experimental Setup. We compare against three post-processing methods: (1) the algorithm of Hardt et al. [2016] (2) the shift inference method, first introduced in Saerens et al. [2002] and used more recently in Wang et al. [2020b], and (3) the Reject Option Classifier (ROC) [Kamiran et al., 2012]. We also include the reduction approach of Agarwal et al. [2018] to compare the performance against in-processing rules. We briefly review each of these methods next.
The post-processing method of Hardt et al. [2016] is a randomized post-processing rule. It was originally developed for equalized odds and equality of opportunity. Nevertheless, it can be modified to accommodate other criteria, such as statistical parity [Agarwal et al., 2018, Dudik et al., 2020].
The shift inference rule, on the other hand, is a post-hoc correction that views bias as a shift in distribution, hence the name. It is based on the identity r(y|s, x) ∝ q(y|s, x) · r(y, s)/q(y, s), which holds for any two distributions r and q on the product space of labels y, sensitive attributes s, and instances x if they share the same marginal r(x) = q(x) [Wang et al., 2020b]. By equating, q(y|s, x) with the classifier’s output based on the biased distribution and r(y|s, x) with the unbiased classifier, the predictions of the classifier q(y|s, x) can be post-hoc corrected for bias by multiplying its probability score with the ratio p(y)p(s)/p(y, s).
The reject option classifier (ROC) proposed by Kamiran et al. [2012] is a deterministic thresholding rule. It enumerates all possible values of some tunable parameter θ up to a given precision, where θ = 0 corresponds to the original classifier. Candidate thresholds are then tested on the data.
Finally, the reduction approach of Agarwal et al. [2018] is an in-processing method that can be applied to black-box classifiers but it requires retraining the model several times. More precisely, let h be a hypothesis in the spaceH and M be a matrix, Agarwal et al. [2018] showed that minimizing the error of h subject to constraints of the form Mµ(h) ≤ c, where µ(h) is a vector of conditional moments on h of a particular form, can be reduced (with some relaxation) to a sequence of cost-sensitive classification tasks for which many algorithms can be employed.
We use the implementations of Hardt et al. [2016] and Agarwal et al. [2018] in the FairLearn software package [Dudik et al., 2020]. The training data used for the post-processing methods is always a fresh sample, i.e. different from the data used to train the original classifiers. Specifically, we split the data that was not used in the original classifier into three subsets of equal size: (1) training data for the post-processing rules, (2) validation for hyperparameter selection, and (3) test data. The value of the hyper-parameter θ of the ROC algorithm is chosen in the grid {0.01, 0.02, . . . , 1.0}. In the proposed algorithm, the parameter γ is chosen in the grid {0.01, 0.02, 0.05, 0.1, 0.2} while ρ is chosen in the gird E[y]± {0, 0.05, 0.1}. All hyper-parameters are selected based on a separate validation dataset. For the in-processing approach, we used the Exponentiated Gradient method as proposed by Agarwal et al. [2018] with its default settings in the FairLearn package (e.g. max iterations of 50).
Tabular Data. We evaluate performance on two real-world datasets, namely the Adult income dataset [Kohavi, 1996] and the Default of Credit Card Clients (DCCC) dataset [Yeh and Lien, 2009], both 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 if the income of an individual exceeds $50K per year. The DCCC dataset contains 30,000 records with 24 attributes, and the goal is to predict if a client will default on their credit card payment. We set sex as a sensitive attribute. In DCCC, we introduce bias to the training set to study the case in which bias shows up in the training data only (e.g. due to the data curation process) but the test data remains unbiased (cf. [Torralba and Efros, 2011] and [de Vries et al., 2019] who discuss similar observations in common benchmark datasets). Specifically, if s(x) = y(x) we keep the instance and otherwise drop it with probability 0.5.
We train four classifiers: (1) random forests with depth 10, (2) k-NN with k = 10, (3) a two-layer neural network with 128 hidden nodes, and (4) logistic regression whose parameter C is fine-tuned from a grid of values in a logarithmic scale between 10−4 and 104 using 10-fold cross validation. The learning rate in our algorithm is fixed to 10−1(K/T )1/2, where T is the number of steps, and = 0.
Table 1 (Top and Middle) shows the bias on test data after applying each post-processing method. The column marked as “original" corresponds to the original classifier without alteration. As shown in the table, the shift-inference method does not succeed at controlling statistical parity while ROC can fail when the original classifier’s output is concentrated on a few points because it does not randomize.
CelebA Dataset. Our second set of experiments builds on the task of predicting the “attractiveness" attribute in the CelebA dataset [Liu et al., 2015]. We reiterate that we do not endorse the usage of vision models for such tasks, and that we report these results because they exhibit sex-related bias. CelebA contains 202,599 images of celebrities annotated with 40 binary attributes, including sex. We use two standard architectures: ResNet50 [He et al., 2016] and MobileNet [Howard et al., 2017], trained from scratch or pretrained on ImageNet ILSVRC2012 [Deng et al., 2009]. We resize images to 224× 224 and train with a fixed learning rate of 0.001 until the validation error converges. We present the bias results in Table 1 (bottom). We observe that randomization is indeed necessary: ROC and Shift Inference both fail at debiasing the neural networks because they do not learn to randomize when most scores produced by neural networks are concentrated around the set {−1, +1}. Impact on Test Accuracy. As shown in Table 2, the proposed algorithm has a much lower impact on the test accuracy compared to Hardt et al. [2016] and even improves the test accuracy in DCCC because bias was introduced in DCCC to the training data only as discussed earlier. The tradeoff curves between accuracy and bias for both the proposed algorithm and Hardt et al. [2016] are shown in Figure 2 (LEFT). Also, for a comparison with in-processing rules, we observe that the post-processing algorithm performs competitively with the reduction approach of Agarwal et al. [2018]. Impact of Scale. Models trained at scale transfer better and enjoy improved out-of-distribution robustness [Djolonga et al., 2021]. As these models are now often used in practice, we assess to which extent can these models be debiased while retaining high accuracy. We conduct 768 experiments on 16 deep neural networks architectures, pretrained on either ILSVRC2012, ImageNet-21k (a superset of ILSVRC2012 that contains 21k classes [Deng et al., 2009]), or JFT-300M (a proprietary dataset with 300M examples and 18k classes [Sun et al., 2017]). The 16 architectures are listed in Appendix E and include MobileNet [Howard et al., 2017], DenseNet [Huang et al., 2017], Big Trasnfer (BiT) models [Kolesnikov et al., 2020], and NASNetMobile [Zoph et al., 2018]. The classification tasks contain seven attribute prediction tasks in CelebA [Liu et al., 2015] as well as five classification tasks based on the COCO dataset [Lin et al., 2014]. We describe how the tasks were selected in Appendix E. The sensitive attribute is always sex in our experiments and all classification tasks are binary. Unless explicitly stated, we use = 0. Moreover, in the COCO dataset, we follow the procedure of [Wang et al., 2020a] in inferring the sensitive attribute based on the image caption: we use images that contain either the word “woman" or the word “man" in their captions but not both.
In every task, we build a linear classifier on top of the pretrained features. Inspired by the HyperRule in [Kolesnikov et al., 2020], we train for 50 epochs with an initial learning rate of 0.003, which is dropped by factor of 10 after 20, 30, and 40 epochs. All images are resized to 224 × 224. For augmentation, we use random horizontal flipping and cropping, where we increase the dimension of the image to 248× 248 before cropping an image of size 224× 224 at random.
Scaling up the Model Size. First, we examine the impact of over-parameterization in pretrained models on the effectiveness of the proposed post-processing algorithm. We fix the upstream dataset to ILSVRC2012 (8 models in total, cf. Appendix E) and aggregate the test error rates across tasks by placing them on a common scale using soft ranking. Specifically, we rescale all error rates in a given task linearly, so that the best error achieved is zero while the largest error is one. After that, we average the performance of each model across all tasks. Aggregated results are given in Figure 3. The impact of the proposed algorithm on test errors improves by scaling up the size of pretrained models.
Scaling up the Data. Second, we look into the impact of the size of the upstream data. We take the four BiT models ResNet50x1, ResNet50x3, ResNet101x1 and ResNet101x3, each is pretrained on either ILSVRC2012, ImageNet-21k, or JFT-300K [Kolesnikov et al., 2020]. For each model and every downstream task, we rank the upstream datasets according to the test error on the downstream task and report the average ranking. Figure 4 shows that pretraining each model on JFT-300M yields the best test accuracy when it is debiased using the proposed algorithm. To ensure that the improvement is not solely due to the data collection process, we pretrain ResNet50 on subsets of ImageNet-21k before fine-tuning on the 12 downstream tasks. Figure 5 shows, again, that the impact of the proposed post-processing rule on test errors improve when pretraining on large datasets.

heading: 6 Conclusion
text: The post-processing approach in fair classification enjoys many advantages. It can be applied to any classification algorithm and does not require retraining. In addition, it is sometimes the only option available, such as when using machine learning as a service with out-of-the-box predictive models [Obermeyer et al., 2019] or due to other constraints in data and computation [Yang et al., 2020a].
In this paper, we propose a near-optimal scalable post-processing algorithm for debiasing trained models according to statistical parity. In addition to its strong theoretical guarantees, we show that it outperforms previous post-processing methods on standard benchmark datasets across classical and modern machine learning models, and performs favorably with even in-processing methods. Finally, we show that the algorithm is particularly effective for models trained at scale, in which heavily overparameterized models are pretrained on large datasets before fine-tuning on the downstream task.

heading: Acknowledgement
text: The authors are grateful to Lucas Dixon, Daniel Keysers, Ben Zevenbergen, Philippe Gervais, Mike Mozer and Olivier Bousquet for the valuable comments and discussions.
Funding Disclosure
This work was performed at and funded by Google. The authors declare that there is no conflict of interest.

Review summaries:
In this paper, the authors propose a post-processing method for debiasing trained models. The authors defined statistical parity as a 'bias'. The paper proposes a constrained optimization problem that takes the input data, sensitive attribute, partitioning and a trained model to yield a probabilistic decision rule. The authors proved theoretical properties and empirically validate its advantages on standard benchmark datasets across both classical algorithms.