FairBatch: Batch Selection for Model Fairness
Authors: Yuji Roh
Kangwook Lee
Steven Euijong Whang
Changho Suh
Venue: ICLR 2021 Poster (2021)
Keywords: model fairness
bilevel optimization
batch selection

Abstract: Training a fair machine learning model is essential to prevent demographic disparity. Existing techniques for improving model fairness require broad changes in either data preprocessing or model training, rendering themselves difficult-to-adopt for potentially already complex machine learning systems. We address this problem via the lens of bilevel optimization. While keeping the standard training algorithm as an inner optimizer, we incorporate an outer optimizer so as to equip the inner problem with an additional functionality: Adaptively selecting minibatch sizes for the purpose of improving model fairness. Our batch selection algorithm, which we call FairBatch, implements this optimization and supports prominent fairness measures: equal opportunity, equalized odds, and demographic parity. FairBatch comes with a significant implementation benefit -- it does not require any modification to data preprocessing or model training. For instance, a single-line change of PyTorch code for replacing batch selection part of model training suffices to employ FairBatch. Our experiments conducted both on synthetic and benchmark real data demonstrate that FairBatch can provide such functionalities while achieving comparable (or even greater) performances against the state of the arts.  Furthermore, FairBatch can readily improve fairness of any pre-trained model simply via fine-tuning. It is also compatible with existing batch selection techniques intended for different purposes, such as faster convergence, thus gracefully achieving multiple purposes.

Published as a conference paper at ICLR 2021
FAIRBATCH:
BATCH SELECTION FOR MODEL FAIRNESS
Yuji Roh', Kangwook Lee", Steven Euijong Whang", " Changho Suh KAIST, (yuji. rch, swhang, (hauhh@kaii st. ac.kr kr University of Wisconsin-Madison, kangwook. lee@wisc.
ABSTRACT
Training a fair machine learning model is essential to prevent demographic disparity. Existing techniques for improving model fairness require broad changes in either data preprocessing or model training, rendering themselves unfficult-to-adiee for potentially already complex machine learning systems. We address this problem via the lens of bilevel optimization. While keeping the standard training algorithm as an inner optimizer, incorporate outer optimizer
equip the inner problem with an additional functionality: Adaprively selecting minibatch sizes for the purpose of improving model fairesss Our batch selection algorithm, which call FairBatch, implements this optimization and supports prominent fairesss measures: equal opportunity, equalized odds, and demographic parity. FairBatch comes with a significant implementation benefit - it does not require any modification to data preprocessing model training. For instance, single-line change of Py Torch code for replacing batch selection part of model training suffices to employ FairBatch. Our experiments conducted both on synthetic and benchmark real data demonstrate that FairBatch can provide such functionalities while achieving comparable (or even greater) performances against the state of the arts. Furthermore, FairBatch can readily improve fairness of any pre-trained model simply via fine-tuning. It is also compatible with existing batch selection techniques intended for different purposes, such as faster convergence, thus gracefully achieving multiple purposes.
INTRODUCTION
Model fairness is becoming essential in a wide variety of machine learning applications. Fairness issues often arise in sensitive applications like healthcare and finance where trained model must not discriminate among different individuals based on age, gender, or race.
While many fairness techniques have recently been proposed, they require range of changes in either
data generation or algorithmic design. There are two popular faimess approaches: (i) pre processing re-weighted (Jiang and Nachum 2020). and (ii) in-processing in which an interested model is retrained via several fairness approaches such as faimess objectives (Zafar et al. 2017a b), adversarial training (Zhang al. 2018), boosting (losifidis and Ntoutsi 2019); see more related works discussed in depth in Sec. 5 However, these approaches may require nontrivial re-configurations modern machine learning systems, which often consist of many complex components.
where training data is debiased (Choi et al. (0200)
In an effort to enable easier-to-reconfiuuee implementation for fair machine learning, address the problem via the lens of bilevel optimization where one problem is embedded within another. While keeping the standard training algorithm as the inner optimizer, we design an outer optimizer that equips the inner problem with an added functionality of improving fairness through batch selection.
Our main contribution this optimization via adjusting the batch sizes w.r.t. sensitive groups based on the fairness measure of an intermediate model, measured in the current epoch. For example, consider a task of predicting whether individual criminals re-offend in the future subject to satisfying equalized odds (Hardt et al.) 2016) where the model accuracies must be the same across sensitive groups In case the model is less
develop a batch selection algorithm (called FairBatch) that implements
Corrrsponniig author

---

Published as a conference paper at ICLR 2021
fairsanpler FairBatch(rodal, critarion, train_data,
as
batch_size, alpha, terget_fairness)
DetaLoafer(train sampler fairsarpler)
Kyanbep 03
Initial point
for opoch in (apgo(opochs);
For 1, data in enurerate(laaee))
iget: the inputs; data is a list of [inguts, labels]
result
94
022
inputs, labels data
M
... oodel fonward, backword, and optiodization
(a) Accuracy difference across sensitive groups in the sense of equalized odds (that we denote "ED disparity"" when running FairBatch on the ProPub- lica COMPAS dataset.
(b) PyTorch code for model training where the batch selection is replaced with FairBatch.
Figure The black path the left figure shows how FairBatch adjusts the batch-size ratios of sensitive groups using two reweighting parameters A and Ag (hyperparameters employed in our framework to be described in Sec.2). thus minimizing their ED disparity, i.c., achieving equalized odds. The code in the right figure shows how easily FairBatch can be incorporated in Py PyTorch machine learning pipeline. It requires a single-line change to replace the existing sampler with FairBatch, marked in blue.
accurate for certain group, FairBatch increases the batch-size ratio of that group in the next batch see Sec. for our adjusting mechanism described in detail. Fig. Ta| shows FairBatch's 's behavior when running on the ProPublica COMPAS dataset (Angwin et al., 2016). For equalized odds, our framework (to be described in Sec. 2 introduces two reweighting parameters (А₁, 22) for the purpose of adjusting the batch-size ratios of two sensitive groups (in this experiment, men and women).
After a few epochs, FairBatch indeed achieves equalized odds, i.e., the accuracy disparity between sensitive groups conditioned on the true label (denoted "ED disparity") is minimized. FairBatch also supports other prominent group fairness measures: equal opportunity (Hardt et al. 2016 and demographic parity (Feldman al. 2015).
key feature of FairBatch is in its great usability and simplicity. It only requires a slight modification in the batch selection part of model training as demonstrated in Fig. Tb and does require any other changes in data preprocessing or model training. Experiments conducted both on synthetic and benchmark real datasets (ProPublica COMPAS (Angwin et al., 2016), AdultCensus (Kohavi) 1996), and UTKFaace (Zhang et al. 2017)) show that FairBatch exhibits greater (at least compa- rable) performances relative to the state of the (both spanning pre- pre-processing (Kamiran and Calders, 2011 IiJinn and Nachum 2020) and in-processing (Zafar et al. [2017a] b. Zhang et al. 2018 lositidis and Ntoutsi 2019) techniques) w.r.f. aspects consideration: accuracy, fairness, and runtime. In addition, FairBatch can improve fairness of any pre-trained model via fine-tuning. For example, Sec. shows how FairBatch reduces the ED disparities of ResNet18 (He et al. (0166) and GoogLeNet (Szegedy et al., 2015) pre-trained models. Finally, FairBatch can be gracefully merged with other batch selection techniques typically used for faster convergence, thereby improving fairness faster well.
Notation Let w be the parameter of an interested classifier. Let E X be an input feature to the classifier, and let ÿ E Y be the predicted class. Note that ý is function of (x, w). We consider group fairness that intends to ensure fairness across distinct sensitive groups (e.g., men versus women). Let z E L be sensitive attribute (e.g., gender). Consider the 0/1 loss: E(y, 1 o ý), and let m be ) be the empirical risk aggregated over samples subject
the total number of train samples. Let Lyy((w)
to and z = 2: (wn) == my. Diy.=gzze 8.))).) where my.z == { : y, = y. 7 = 2
Similarly, we define [.y.(()) = myg. E,y Eyy., 8,) and (w) = 1 Σ Eizz= 9,)
where my Hi y, y and m.. := 1i Z, = zH/. The overall empirical risk is written as L(w)) Σ, (.). We utilize V for gradient and @ for subdifferential.
2 BILEVEL OPTIMIZATION FOR FAIRNESS
In order to systematically design adaptive batch selection algorithm, formalize implicit connection between adaptive batch selection and bilevel optimization. Bilevel optimization consists of outer optimization problem and an inner optimization problem. The inner optimizer solves an
2

---

Published as a conference paper at ICLR 2021
Algorithm 1: Bilevel optimization with Mi bat
Minibatch sampling distribution +- Uniform sampling for each epoch do Draw minibatches according minibatch sampling distribution for each minibatch do
L ur Mi n ba t chsGG (w,, each minibatch)
Update minibatch sampling distribution
inner optimization problem, and the outer optimizer solves an outer optimization problem based on the outcomes of inner optimization. By viewing the standard training algorithm such as stochastic gradient descent (SGD) (Bottou) 2010) as an inner optimizer and viewing the batch selection algorithm as outer optimizer, the process of training fair classifier can be seen process of solving bilevel optimization problem.
Batch selection + minibatch SGD = bilevel optimization solver Consider scenario where one is minimizing the overall empirical risk L(w) via minibatch SGD. The minibatch SGD algo- rithm picks b of the indices uniformly at random, say f1, J2; ......... and updates its iterate with E Vely,; )j.). called a batch gradient. Note that batch gradient an unbiased estimate of the true gradient VL(w).
Since the empirical risk minimization (ERM) formulation does not take a faimess criterion into account, its minimizer usually does not satisfy the desired fairness criterion. To address this limitation of ERM, we adjust the way minibatches are drawn so that the desired fairnsss guarantee is satisfied. For instance, as we described in the introduction, we can draw minibatches with a larger number of train samples from a certain sensitive group so to achieve a higher accuracy w.r.t. the group.
Once the minibatch distribution deviates from the uniform distribution, the batch gradient estimate not anymore an unbiased gradient estimate of the overall empirical risk. Instead, it is an unbiased estimate of a reweighted empirical risk. In other words, if we draw train example with probability p. for all i such that Σp. P. = 1, the batch gradient is unbiased estimate of L'
Σ, p,lly 8.).
This observation enables us the following bilevel optimization- based interpretation how batch selection interacts with inner optimization algorithm. At initialization, minibatch SGD optimizes the (unweighted) empirical risk. Based on the outcome of the inner optimization, the outer optimizer refines p- (PI, (PI,P2.-. P2..... .......P .Pm). the sampling probability of each train example. The inner optimizer now takes minibatches drawn from new distribution and reoptimizes the inner objective function. Due to the new minibatch distribution, the inner objective now becomes a reweighted empirical risk w.r.t. P. This procedure is repeated until convergence. See Algorithm ] for pseudocode.
Therefore, batch selection algorithm together with an inner optimization algorithm can be viewed as pair of outer optimizer and inner optimizer for the following bilevel optimization problem:
min Cost( Wp), Wp arg min L' L'(w).
w
where Cost(-) captures the goal of the optimization.
Two questions arise. First, how can we design the cost function to capture a desired fairness criterion? Second, how can we design an update rule for the outer optimizer? Can we develop an algorithm with a provable guarantee? In the rest of this section, we show how one can design proper cost functions to capture various fairness criteria. In Sec. 3 we will develop an efficient update rule of FairBatch.
Equal opportunity For illustrative purpose, assume for now the binary setting (Y = Z= {0, 1)). model satisfies equal opportunity (Hardt et al. 2016) if we have equal positive prediction rates conditioned on y 1, i.e., [_ =T (w) Since the ERM formulation does not take the fairness criterion into account, these two quantities differ in general. To mitigate this, we adjust the sampling probability between L1.((w) and L1, (w). More specifically, we propose the following procedure to draw sample. First, we randomly pick which subset of data to sample data from. We pick the set 1, 0 with probability X, the set y 1, with probability mi.- X, and the set y 0 with probability ma.. We then pick sample from the chosen set, uniformly at random.
m
3

---

Published as a conference paper at ICLR 2021
This leaves us with dingle-dimensionn bias between data with y = 1, Z = O and data with = 1, = 1. Also, we design the cost function
outer optimization variable X, which controls the sampling
as (( L (wx)) ) to capture the equal opportunity criterion. Thus, we have the following
bilevel optimization problem:
min
[1,O(w>) - (wx)(, wy = arg mig (L1,0( + ( ( A)L1,((0) + mo.-
Lo.
XE(O, 11
m
Equalized odds Similarly, we can design a bilevel optimization problem to capture equalized odds (Hardt et al. 2016), which desires the prediction to be independent from the sensitive attribute conditional on the true label, i... (o,o(w) Lo. (w)) and (1)( = L1,1 (w). Again, the empirical risk minimizer does not satisfy these two conditions in general. To mitigate these disparities, we adjust (i) the sampling probability between Lo.0(u) (w) and (w)) and (ii) the sampling probability between L1.0( (w) and [ To achieve this, we use the following procedure to draw sample. First, we pick the set y = 0, z = 0 with probability A1 the set y = 0, 2 = with probability mo.. A1. the set y 1, = O with probability X2, and the set y 1,z = 1 with probability miz - A2- We then pick one data point at random from the chosen set. This leaves with wwoddimensional outer optimization variable À = (A1, A2). To capture the equalized odds criterion, design the outer objective function as: max Lo,, [w))(w)), (I1,0(w) I (w))): This gives us the following bilevel optimization problem:
min EEj 28022 1 |
max m [,,o)( - Lo.1 (w>)l [1,,( (.w(w)
WA arg min X1 (o))(w) + mo.. Lo) + )2 + (m 12)(1,1(W).
Demographic parity Demographic parity (Feldman al. 2015) is satisfied if two sensitive groups have equal positive prediction rates. If My.s's 's are all equal, then Lo (w) = L1,o (w) and Lo, (w) = L1,1 (w) can serve a sufficient condition for demographic parity; see Sec. Sec.AA.I for why and how to handle demographic parity when this condition does not hold. To satisfy this sufficient condition, we now adjust (i) the the sampling probability between (w))(w) and L1,0(w) and (ii) the the sampling probability between I and L1, (w). This gives us the following bilevel optimization problem:
min A ""..0 ] (0, 1
max Lo - (x)l()>)) (wx) - [ww(w
W arg min A Lo + m_.0 \ + dzLo, (w) + (" 12)
Beyond binary labels/sensitive attributes While the previous examples assumed binary-valued labels and sensitive attributes, our framework is applicable to the cases where the alphabet sizes are beyond binary. As an example, consider the equal opportunity criterion when Z {0. 1, n2 1}. The condition reads L1,0 (w) = L1,1 = = Li.n,- (w). To satisfy this condition, we adjust the sampling probability between
("-)-dimesiiona -dimensional outer optimization variable X, and design the outer objective function as max Li.j, (w) L1,j (w)l. In our imple- mentation, however,
by introducing (7,
only use (n.- 1) -iimenniiaa disparity objectives as approximation (i.e., maxj (0, [o..........-3 2) (L1,, (w) - L1.j++1 (w)) for better efficiency. Suppose the level of disparity is when FairBatch compares all possible combination pairs of sensitive groups. Now suppose we only optimize on the sequential (n= 1) disparity objectives. Then we will fail to ensure that other objec-
tives like (ww) - T1,1 (w)) are within In the worst case, the objective [T,,,, 1 (w) Ta,1 (m)) may be (n, - 1) x e, as we only guarantee that each [L. (w) L1.i++1 (w)l S If is small enough, the disparity of our approximation becomes reasonable as well. One can also handle other fairness criteria in a similar way.
3 UPDATE RULE OF FAIRBATCH
We design efficient update rules of FairBatch for different numbers of disparities. Let us define d as the dimension of the outer optimization variable X, which is the same as the total number of disparities. We first analyze the simplest case where d = 1. We show that a simple gradient descent algorithm can provably solve the outer optimization problem. The equal opportunity example in the previous section falls in this category. We then extend the algorithm developed for the one-dimensional case to the multi-dimenssonal (d > 1) case. Equalized odds and demographic parity fall in this category.
4

---

Published as a conference paper at ICLR 2021
3.1 UPDATE RULE FOR d =
When d = 1, the general form of our bilevel optimization problem can be written as follows:
min Ae(0,c1]
(fx(w)) - 91 (wx)l: wa arg min (1) + (c1 A)gı (w) + h(w), w
where 61 > 0 a constant. Let F()) = If (wx) - 91 (w>), I. The following lemma shows that (()) is quasiconvex in À under some mild conditions, and its signed gradient can be efficiently computed.
Lemma (Quasi-convexity of F())). For d = 1, if f1(), 91).,, and h(-) satisfy
1. h(w) = or
2. if fi).). 9-(-), and h(-) are twice differentiable, A AV fi + (a - () +
V <h((w)) > 0 for every X E [0,
then F(A) is quasi-conver, i.e., (1- t)X) S max (F(A), for all E 10, []d M. Also, if F.) # O, then 0₂ F(A) = {r} and sign (w) = sign (gi (1xx) ((xx)= f((w())))
Remark 1. The quasiconvexity of F(A) is valid when at least one of the conditions in Lemma holds. For the second condition, if f:(-). gi(-), and h(-) are convex, this condition will hold unless all the three functions share their stationary points, which is very unlikely. While there is no theoretical guarantee for the non-convex settings, FairBatch still shows on par or better results than the other fairness approaches in general settings where the functions may not be convex (see Sec. 4
The proof for Lemma I can be found in Sec. A.2 Note that quasiconvexity immediately implies unique minimum (Boyd et al., 2004). Thus, we design the following signed gradient-base optimization algorithm:
E (0, I.. ((+1) = (
(()) - fi (wx))
This algorithm increases by a if (wx) S (wx) and decreases À by a otherwise. Recall that this is consistent with our intuition: It increases the sampling probability of disadvantageous group and decreases that of an advantageous group. The following proposition shows that the proposed algorithm converges the optimal solution.
Proposition 1. Let X = arg miny F(A) and E 20 Then, [X0) max[[A0) a).
Remark 2. F(A) is not necessarily convex even when we assume the inner objective functions fi (.). and g1 (-) are convex even strongly convex. See Sec. A.3 counter example.
3.2 UPDATE RULE FOR d 2
We now develop an efficient update algorithm for the following general bilevel optimization:
min max [f((wx) gi(wx),, wx arg min M i- (vf((w) + (a. {x)g((w) + h(w). iEA.=I.....d
w
Here, A [0,cc] [0, .... J0, cal. where 's some positive constants. Denoting by F(A) the outer objective function, let us first derive the gradient of it. Under some mild conditions (see Sec. A.4 on fe(-)'s, 's. (i(-)ss and h(-):
% = sign (w: - for
- Vgr (g-((w)) (w) - Vg:(w)) F(A), Vi,
where 1" = arg max; (ur) g. (w)), and H is positive definite. See Sec. A.4 for the derivation. Since subdifferential is always a convex set, it follows that 7 == (71, 72.............................. 7a) E F(A). Com- puting the subgradient requires to compute HA, which involves the Hessian matrices of the inner objective function. To avoid this expensive computation, we approximate Y Rs (0, O...... . ..... 0). See Sec. A.5 for the rationale and intuition behind this approximation. Then, similar the case of d = 1, we have sign(>) (0, O,..,, siig (gi- (wx) Si- (w,)),,0,..... O,....)).. This gives us the general update rule of FairBatch (see Sec. A.6 for pseudocode):
1A (0, 1, ....) A/ ((+1)
X!! sign(gi- (wx) s(-(wx)), ((+2) 100 Vi vi
5

---

Published as a conference paper at ICLR 2021
4 EXPERIMENTS
We use logistic regression in all experiments except for Sec. 4.2 where we fine-tune ResNet18 (He) et al. 2016) and GoogLeNet (Szegedy et al. 2015) in order to demonstrate FairBatch's s ability to improve fairness of pre-trained models. We evaluate all models on separate test sets and repeat all experiments with 10 different random seeds. We use PyTorch and our experiments are performed on a server with Intel i7-6850 CPUs and NVIDIA TITAN Xp GPUs. See Sec. B.1 for more details.
Measuring Fairness Here we first focus on the equal opportunity (EO) and demographic parity (DP) measures in Sec. [..] and Sec. 4.3 The equalized odds (ED) measure is used in Sec. 4.2 and Sec. B.2 To quantify EO, ED. and DP, we compute the disparity between
sensitive groups: EO disparity = max,ez Pr(9- = 1/2 = y = 1) - Pr(y = 1lyy=)), ED disparity max ma. Pr(y- = 0/z y, y) Pr(y 5ly = y)|, and DP disparity max,ez Pr(y = 1|z= 2) - Pr(ý 1)). As we discussed in Sec. 3 EO has a single-dimension
outer optimization where the number of disparities d = 1 while ED and DP have multi-dimensional
outer optimizations where d > 1.
Datasets We generate a synthetic dataset of 3,000 examples with two non-sensitive attributes (X1- x2). a binary sensitive attribute z, and a binary label y, using a method similar to the one in Zafar et al. 2017a). A tuple (x1, X2, y) is randomly generated based on the two Gaussian distributions:
2]. [5, 1: 1, 5)). For z, we generate biased data using an unfair scenario Pr(z = 1) = Pr((x,, ,, xb)ly 1) ()/(P((xx) x2)ly = 0) Pr((x],, x2)ly = 1)] where (x1,x) xx) (x1 cOS(1T/ (T/
[x1,X2]1 Xy
(1-22 -2]. [10. 1: 1,) and (x,, X2)yy
X2 sin (T/ /4), X1 sin(T (T/4) + X2 (T/()/
We use the real benchmark datasets: ProPublica COMPAS (Angwin et al. 2016) and AdultCensus (Ko havi 1996) datasets with 5,278 and 43,131 examples, respectively. We use the same pre-processing 2019) and use GENDER as the sensitive attribute. We also employ the UTKFace dataset (Zhang et al. 2017) with 23,708 images to demonstrate the fine-tuning ability of FairBatch in Sec. 4.2
as in IBM's AI Fairness 360 (Bellamy et al.
Baselines We employ three types of baselines: (1) noi-fair training with logistic regression (LR); (2) fair training via pre-processing; and (3) fair training via in-processing.
For pre-processing methods, we first consider a simple approach that we call Cutting, which evens the data sizes of sensitive groups via saturating them to the smallest-grow -aalus data size. One can think of a similar alternative approach: Boosting all of the smaller- smaller-group group data sizes to the largest one, but we do not report herein due to similar performances that we found relative to Cutting. The other two are the state of the arts: reweighing (Kamiran and Calders, 2011) (RW) and Label Bias Correction (Jiang and Nachum] 2020) (LBC). RW intends to balance importance levels across sensitive groups via example weighting, but sticks with these weights throughout the entire model training, unlike FairBatch. LBC iteratively trains an entire model with example weighting towards an unbiased data distribution.
For in-processing methods, we compare with the following three: Fairness Constraints (Zafar et al. bb (FC), Adversarial Debiasing (Zhang et al., (018) (AD), and AdaFair (losifidis and Ntoutsi 2019). FC incorporates regularization term in an effort to reduce the disparities among sensitive groups. AD an adversarial learning approach that intends to maximize the independence between the predicted labels and sensitive attributes. In our experiments, a slight modification is made to AD for improving training stability: Not employing one regularization term used for restricting the training direction. AdaFair is an ensemble technique that equips the prominent AdaBoost (Friedman et al. 2000) with a fairness aspect. Here the examples that lead to unfair and inaccurate performances considered to be the difficult instances. In our experiments, natural generalization of AdaFair intended for ED is made to encompass EO and DP; see Sec. B.3 for the generalization. While AdaFair bears spiritual similarity to FairBatch in sense that mistreated examples are weighted progressively, it comes with a significant distinction in update scale. It is basically a boosting technique; hence such updates are done in distinctive predictors through different rounds; see Sec. 5 for details.
FairBatch Settings To set a, we start from a candidate set of values within the range [0.0001, 0.05] and use cross- valisattin the training set to choose the value that results in the highest accuracy with low fairness violation. The default batch sizes are: 100 (synthetic); 200 (COMPAS). 1,000 (AdultCensus); and 32 (UTKFace).
6

---

Published as a conference paper at ICLR 2021
Table Performances on the synthetic. COMPAS, and AdultCensus test sets w.r.t. equal opportunity
(EO). We compare FairBatch with three types of baselines: (1) non-fair method: LR; (2) fair
training via pre-processing: Cutting, RW (Kamiran and Calders [011). and LBC (Jiang and Nachum
2020); (3) fair training via in-processing: FC (Zafar et al. 2017b), AD (Zhang et al. 2018). and
AdaFair (losifidis and Ntoutsi 2019). Experiments are repeated 10 times.
Synthetic
COMPAS
AdultCensus
Method
Acc.
EO Disp.
Epochs
Acc.
EO Disp.
Epochs
Acc.
EO Disp.
Epochs
LR
8885+0000 . 110+0000
400
.681+0002
.239-+0006
300
.845+-001
.054+-0005
300
Cutting
858+.0011 .028++.002
800
.674:.005
.055+.018
600
.802+.002
.054+.007
600
RW
8888.000
.020+t.000
800
.685=.000
.137=.000
300
.8351.001
.134::.006
100
LBC
888++0001
.022++000
11200
.673++.002 .031+-006
3900
.841+0033 .011+-003
6300
FC
8333..011 .007:1.000
700
.6562.006
.0591.028
100
.8441.001
.021::004
300
AD
837+.010 .026+t.007
200
.683+.001
.067=.029
300
.841+0003
.016++.05
400
AdaFair
.888..00 .0433.0011
16000
.6644.004
.018+.004
9600
8844.0001
.03811.004
9000
FairBatch
.855:1.00 .012:1.011
300
.6811.001 .022:1.05
100
.8441.001 .011:1.003
400
Table 2: Performances on the synthetic. COMPAS, and AdultCensus test sets w.r.t. demographic
parity (DP). The other settings are identical to those in Table 1
Synthetic
COMPAS
AdultCensus
Method
Acc.
DP Disp.
Epochs
Acc.
DP Disp.
Epochs
Acc.
DP Disp.
Epochs
LR
885.1.000
.257:1.00
400
.6811.002
.192:1.006
300
.8451.001
.11
300
Cutting
885+.001 .258:1.001
500
.677:1.004
.205
400
884:1.001
.123:1.002
300
RW
857=.000
.164..001
400
.685=.000
.103=.000
300
.835..001
_052+t.03
300
LBC
.768:1.000
.042:1.001
16000
.671:1.002 .032:1.000
7800
.815+.003
,011::002
12600
FC
.785#.013 .058:.010
600
.684=.001
.083=.015
70
812::.009
.025=1006
100
AD
.81:+.008 .063:E.014
700
.683..002
.054:1.019
550
.815+.008
.018:1.004
400
AdaFair
.784:.001 .089:t.01
52000
.642..004
.033=.011
6300
.8255.002
.040:1.001
27000
FairBatch
.794:.001
.040:t.001
450
.681=.001
.0362.023
300
.8231.001
.010:1.005
600
4.1 ACCURACY, FAIRNESS, AND RUNTIME
comperes FairBatch against the other approaches on the synthetic, COMPAS, and AdultCensus test sets w.r.t. accuracy, EO disparity, and complexity (reflected in the number of epochs). In Sec. [.4] we also present the convergence plot of EO disparity as a function of the number of epochs. LR in row I is logistic regression without any fairness technique. The pre-processing techniques in rows 2-4 reduce EO disparity yet while sacrificing the accuracy performance. The inporocsssnng techniques in rows 5-7 further reduce EO disparity yet still sacrificing accuracy. FairBatch, presented in the last row, offers comparable (or even greater) fairness performance while sacrificing less accuracy. We also present accuracy and fairness trade-off curves of FairBatch in Sec. B.5 One key implementation benefit is reflected in the small numbers of epochs. We also obtain consistent wall clock times, presented in Sec. B.6] As mentioned earlier, AdaFair is the most similar spirit FairBatch as it adjusts example weights based on the fairness performances of prior models. We demonstrate in Sec. that that FaicBatch and AdaFair indeed show similar convergence behaviors yet in different scales (rounds for AdaFair vs. epochs for FairBatch). One distinctive feature of FairBatch relative to AdaFair is the use of a single model training, thus enabling much faster speed (22.5-96x). We also make similar comparisons yet w.r.t. another fairness measure: DP disparity. See Table 2 Recall that minimizing DP disparity involves adjusting two byperparameters (A1, X2), which also means that d = 2. Although FairBatch's 's theoretical guarantees hold only when using one hyperparameter (i.e.. d = 1), we nonetheless see similar results where FairBatch is on par or better than the other approaches, while being the most robust in all aspects.
7

---

Published as a conference paper at ICLR 2021
Table 3: Performances of the pre-trained models fine-tuned with FairBatch the UTKFace test set w.r.t. equalized odds (ED) for two faireess scenarios. While Tables and already demonstrate FairBatch's s performance against the state of the arts, the emphasis here is usability where it is easy to adopt and yet improves the faimesss of existing models.
FairBatch's
x: RACE, y: GENDER
Z: RACE, y: AGE
Pre-trained model
Method
Acc.
ED Disp.
Epochs
Acc.
ED Disp.
Epochs
Original
893110002
.8861.012
19
.7224.011
.3111.053
10
ResNet18
Cutling
.592+.020
.099=..014
18
.466+.018
.139:t.021
FairBatch
.8941.002
.063:.013
30
.7581.004 .2201.016
10
Original
888+.003
.105=.016
20
.746+.006
.294+.034
14
GoogLeNet
Cutting
.00:1.010
.0761.017
20
.4951.017 .1681.033
FairBatch
891+.002
.061=.006
11
.711
.202+.019
4.2 FINE-TUNING PRETRAINED UNFAIR MODELS FOR FAIRNESS
While Tables I and already demonstrate FairBatch's 's performance against the state of the arts, in this section we emphasize the usability of FairBatch by showing how it can improve fairness of any pretrained unfair model via fine-tuning and only compare it with Cutting. which is also easy to adopt. shows Thoos how FairBatch improves fairness of pre-trained models (ResNet18 (He et al.) 2016) and GoogLeNet (Szegedy al., 2015)) the UTKFaae dataset (Zhang al. (017). Each image has three types of attributes: GENDER, RACE, and AGE. We use RACE as the sensitive attribute and consider two scenarios where the label autribute GENDER AGE. While GENDER binary, AGE is multi-valued (<21, 21-40, 41-60, and 660) so we extend FairBatch in straightforward fashion; see Sec. B.8 for details. Both Cutting and FairBatch reduce the ED disparities of the original pre-trained models. However, only FairBatch does so without sacrificing accuracy performance.
4.3 COMPATIBILITY WITH OTHER BATCH SELECTION TECHNIQUES
We demonstrate another key aspect of FairBatch: Compatibility with existing batch selection ap- proaches that use importance sampling for faster convergence in training. 'he key functionality of the prior batch selection techniques is that examples considered be "important" are given higher weights so as to be sampled more frequently. FairBatch can easily be tuned to accommodate such functionality: determining the batch-ratios of sensitive groups and then sampling using the importance weights per group. We evaluate FairBatch combined with one prominent technique, loss-based weighting (Loshchilov and Hutter, 2016), on our synthetic dataset using EO and DP. We find that FairBatch indeed converges more quickly. It uses about 50 fewer epochs with similar fairness performances; see Sec. B.9 for the EO and DP convergence plots.
5 RELATED WORK
Model Fairness Various faimesss measures have been proposed to reflect legal and social is- sues Narayanan 2018). Among them, we focus on group fairness measures: equal opportunity (Hardt
let al. 2016), equalized odds (Hardt al.) 2016), and demographic parity (Feldman al. 2015).
variety of techniques have been proposed and can be categorized into (1) pre-processing tech-
2013 Feldman al., 2015 du Pin Calmon et al.) 2017 Choi et al. |020) Jiang and Nachum 2020) which debias or reweight data, (2) in processing techniques (Kamishima et al. 2012
niques (Kamiran and Calders 2011 Zemel
/afarr /afar et al.] 2017a Agarwal et al. 2018 Zhang al. 2018
Cotter et al.) 2019: Roh et 2000),. which tailor the model training for fairness, and (3) post-
processing techniques (Kamiran et al. 2012: Hardt et al. 2016 Pleiss et al. 2017, Chzhen et al.) 2019), which perturb only the model output without touching upon the inside. Most of these methods require broad changes in data preprocessing, model training, or model outputs in machine learning systems Venkatasubramanian. 2019). In contrast, FairBatch only requires single- line change in code to replace batch selection while achieving comparable or even greater performances against the state of the arts.
8

---

Published as a conference paper at ICLR 2021
Among the fairness techniques, AdaFair (losifidis and Ntoutsi 2019) is the most similar in spirit to FairBatch. AdaFair extends the well-known AdaBoost (Friedman et al. 2000) where examples that lead to poor accuracy fairness are boosted, i.., given higher weights during the next round of training a new model that is added to the ensemble. In comparison, FairBatch is based on theoretical foundations of bilevel optimization and effectively performs the reweighting during each epoch (not through rounds), which leads to an order of magnitude improvement in speed as shown in Sec. [4.1
Although not our immediate focus, there are other noteworthy fairness measures: (1) individual faimess (Dwork et al. 2012) where close examples should be treated similarly, (2) causality-based
fairness (Kilbertus et al. 2017 Kusner et al. 2017 Zhang and Bareinboim, 2018 Nabi and Shpitser 2018; Khademi et al. 2019)) which aims to overcome the limitations of non-causa approaches by understanding the causal relationship between attributes, and (3) distributionally robust optimization (DRO) (Sinha et al., boased fairness (Hashimoto et al., 2018), which achieves accuracy parity without the knowledge of sensitive attribute by balancing the risks across all distributions. Extending FairBatch to support these measures is an interesting future work.
Finally, Chouldechova and Roth (2018) describe three causes of unfairness that help clarify Fair- Batch's fairness contributions: ()) minimizing average error fits majority populations, (2) bias encoded in data, and (3) the need to explore and gather more data. FairBatch addresses the cause (1) via balancing the sensitive group ratios within a batch. FairBatch also addresses (2) in some cases. For example, consider the recidivism prediction problem described in (Chouldechova and Roth 2018) where minority populations have biased labels. In this case, FairBatch can be configured to make the recidivism prediction rate for the minority population similar to those of other populations. There may be other types of data bias that FairBatch not able address. Finally, FairBatch does not directly address (3) where one must gather more data for better fairness. Instead, there is a recent line of work that studies data collection techniques (Te and Whang, 2021 for fairness.
Batch Selection The batch selection literature for SGD focuses analyzing the effect of batch sizes (Keskar et al. [2017 Masters and Luschi] (2018) and various sampling techniques (Shamir 2016 Gürbüzbalaban al. 2019)). More recently, importance sampling techniques have been proposed for faster convergence (Loshchilov and Hutter 2016 Alain et al. 2016 Stich et al. 2017 Csiba
and Richtárik 2018 Katharopoulos and Fleuret 2018 Johnson and Guestrin 2018). In comparison,
FairBatch takes the novel approach of using batch selection for better faimess and is compatible with
other existing techniques.
6 CONCLUSION
We addressed model fairness via the lens of bilevel optimization and proposed the FairBatch batch selection algorithm. The bilevel optimization provides natural framework where the inner optimizer SGD, and the outer optimizer performs adaptive batch selection to improve fairness. We presented FairBatch for implementing this optimization and showed how its underlying theory supports the fairness measures: equal opportunity, equalized odds, and demographic parity. We showed that FairBatch offers respectful performances that are on par even better than the state of the arts w.r.t. all aspects in consideration: accuracy, fairness, and runtime. Also, FairBatch can readily be adopted to machine learning systems with a minimal change of replacing the batch selection with single-line of code and be gracefully merged with other batch selection techniques used for faster convergence.
ACKNOWLEDGEMENTS
Yuji Roh and Steven F. Whang were supported by a Google AI Focused Research Award and by the Engineering Research Center Program through the National Research Foundation of Korea (NRF) funded by the Korean Government MSIT (NRF-201 ASA 1059921). Kangwook Lee was supported by NSF//nnel Partnership on Machine Learning for Wireless Networking Program Changho Suh was supported by Institute for Information &
under Grant No. communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (No. 2019-0-01396, Development of framework for analyzing, detecting, mitigating of bias in Al model and training data).

---

Published as a conference paper at ICLR 2021
REFERENCES
Kristy Choi, Aditya Grover, Trisha Singh, Rui Shu, and Stefano Ermon. Fair generative modeling via weak supervision. In ICML., 2020.
Heinrich Jiang and Ofir Nachum. Identifying and correcting label bias in machine learning. In AISTATS, pages 702-712, 2020.
Muhammad Bilal Zafar, Isabel Valera, Manuel GodezzRodriguez, and Krishna P. Gummadi. Fairness constraints: Mechanisms for fair classification. AISTATS, pages 962-970, 2017a.
Muhammad Bilal 7afar, Isabel Valera, Manuel Gomez-Rodriguez, and Krishna P. Gummadi. Fair- ness beyond disparate treatment disparate impact: Learning classification without disparate mistreatment. In WWW, pages 11 1171-1180, 2017b.
Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adversarial learning. In AIES, pages 335-340, 2018.
Vasileios Iosifidis and Eirini Ntoutsi. 781-790, 2019.
Adafair: Cumulative faimess adaptive boosting. In CIKM, page
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In NeurIPS, pages 3315-3323, 2016.
Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias: There's 's software used across the country to predict future criminals. And its biased against blacks. ProPublica, 2016.
Michael Feldman, Sorelle A. Friedler, John Moeller, Carlos Scheidegger. and Suresh Venkatasubra- manian. Certifying and removing disparate impact. In KDD, pages 259-268, 2015.
Ron Kohavi. Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid. In KDD, pages 202-207, 1996.
Zhifei Zhang, Yang Song, and Hairong Qi. Age progressionnregression by conditional adversarial autoencoder. CVPR, pages 4352-4360, 2017.
Faisal Kamiran and Toon Calders. Data preprocessing techniques for classification without discrimi- nation. Knowl. Inf. Syst., 33(1):1-33, 2011.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. CVPR, pages 770-778, 2016.
Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott E. Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In CVPR, pages 1-9, 2015.
Léon Bottou. Large-scale machine learning with stochastic gradient descent. In COMPSTAT, pages 177-186. Springer, 2010.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Rachel K. E. Bellamy, Kuntal Dey, Michael Hind, Samuel C. Hoffman, Stephanie Houde, Kalapriya Kannan, Pranay Lohia, Jacquelyn Martino, Sameep Mehta, Aleksandra Mojsilovic, Seema Na- gar, Karthikeyan Natesan Ramamurthy, John T. Richards, Diptikalyan Saha, Prasanna Sattigeri, Moninder Singh, Kush R. Varshney, and Yunfeng Zhang Al fairness 360: An extensible toolkit for detecting and mitigating algorithmic bias. IBM Res. Dev. 63(4/5):4:1 2019.
Jerome Friedman, Trevor Hastie, and Robert Tibshirani. Additive Logistic Regression: a Statistical
View of Boosting. The Annals of Statistics, 38(2), 2000.
Ilya Loshchilov and Frank Hutter. Online batch selection for faster training of neural networks. In ICLR 2016 Workshop Track, 2016.
10

---

Learning fair Published as a conference paper at ICLR 2021
Arvind Narayanan. Translation tutorial: 21 faimess definitions and their polities. In FAccT, volume 1170, 2018.
Richard S. Zemel, Yu Wu, Kevin Swersky, Toniann Pitassi, and Cynthia Dwork. representations. ICML, pages 325-333 3333, 2013.
Flávio du Pin Calmon, Dennis Wei, Bhanukiran Vinzamuri, Karthikeyan Natesan Ramamurthy, and Kush R. Varshney. Optimized pee-proeessing for discrimination prevention. In NeurlPS, pages 3995-4004, 2017.
Toshihiro Kamishima, Shotaro Akaho, Hideki Asoh, and Jun Sakuma. Fairness-aware classifier with prejudice remover regularizer. In ECML PKDD, pages 35-50, 2012.
Alekh Agarwal, Alina Beygelzimer, Miroslav Dudfk, John Langford, and Hanna M. Wallach. A reductions approach fair classification. In ICML, pages 60-69, 2018.
Andrew Cotter, Heinrich Jiang, and Karthik Sridharan, Two-player games for efficient non-convex constrained optimization. In ALT, pages 300-332, 2019.
Yuji Roh, Kangwook Lee, Steven Euijong Whang, and Changho Suh. FR-Train: A mutual information-bast approach to fair and robust training. In ICML, 2020.
Faisal Kamiran, Asim Karim, and Xiangliang Zhang. Decision theory for discrimination-aware classification. In ICDM, pages 924-929, 2012.
Geoff Pleiss, Manish Raghavan, Felix Wu, Jon M. Kleinberg, and Kilian Q. Weinberger. On fairness and calibration. In NeurlPS, pages 5684-5693, 2017.
Evgenii Chzhen, Christophe Denis, Mohamed Hebiri, Luca Oneto, and Massimiliano Pontil. Lever- aging labeled and unlabeled data for consistent fair binary classification. In NeurlPS, pages 12770- 2019.
Suresh Venkatasubramanian. Algorithmic faimess: Measures, methods and representations. In PODS, page 481, 2019.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard S. Zemel. Fairness through awareness. In ITCS, pages 214-220 226, 2012.
Niki Kilbertus, Mateo Rojas-Carulla, Giambattista Parascandolo, Moritz Hardt, Dominik Janzing, and Bernhard Schölkopf. Avoiding discrimination through causal reasoning. In NeurlPS, pages 656-666, 2017.
Matt J Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. Counterfactual faimess. In NeurIPS, pages 4066-4076. 2017.
Junzhe Zhang and Elias Bareinboim. Fairness in decision decision-making the causal explanation formula. In AAAI, 2018
Razieh Nabi and Ilya Shpitser. Fair inference on outcomes. In AAAL, pages 1931-1940, 2018.
Aria Khademi, Sanghack Lee, David Foley, and Vasant Honavar. Fairness algorithmic decision making: An excursion through the lens of causality. In WWW, pages 2907-2914, 2019.
Aman Sinha, Hongseok Namkoong, and John C. Duchi. Certifying some distributional robustness with principled adversarial training. In ICLR, 2017.
Tatsunori Hashimoto, Megha Srivastava. Hongseok Namkoong, and Percy Liang. Faireess without demographics in repeated loss minimization. In ICML, pages 1929,1938, 2018.
Alexandra Chouldechova and Aaron Roth. The frontiers of fairness in machine learning. CoRR. abs/1810.088100 2018.
Ki Hyun Tae and Steven Euijong Whang. Slice tuner: A selective data acquisition framework for accurate and fair machine learning models. In SIGMOD, 2021.
11

---

Published as a conference paper at ICLR 2021
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In ICLR, 2017.
Dominic Masters and Carlo Luschi. Revisiting small batch training for deep neural networks. CoRR, abs/1 0es//804,7762,, 2018.
Ohad Shamir. Without-replacement sampling for stochastic gradient methods. In NIPS, pages 46-54. 2016.
Mert Gürbüzbalaban, Asu Ozdaglar, and PA Parrilo. Why random reshuffling beats stochastic gradient descent. Mathematical Programming, pages 1-36, 2019.
Guillaume Alain, Alex Lamb, Chinnadhurai Sankar, Aaron Courville, and Yoshua Bengio. Variance reduction in sgd by distributed importance sampling. ICLR Workshop, 2016.
Sebastian U Stich, Anant Raj, and Martin Jaggi. Safe adaptive importance sampling. In NIPS, pages 4381-4391, 2017.
Dominik Csiba and Peter Richtárik. Importance sampling for minibatches. The Journal of Machine Learning Research, 19(1):962 99222, 2018.
Angelos Katharopoulos and François Fleuret. Not all samples created equal: Deep learning with importance sampling. In ICML, pages 2530-2539, 2018.
Tyler B Johnson and Carlos Guestrin. Training deep models faster with robust, approximate impor- tance sampling. In NIPS, pages 7265-7275, 2018.
12

---

Published as a conference paper at ICLR 2021
A
APPENDIX - THEORY AND ALGORITHMS
A.1 DEMOGRAPHIC PARITY
We continue from Sec. 2 and provide more details on how we can capture demographic parity using our bilevel optimization framework.
Proposition 2. If mo,o mp,1 = m1,0 = m1,1, then [o,o(ur) = [1,,(ur) and To,1 (w) (w)) can serve as a sufficient condition for demographic parity.
Proof. Slightly abusing the notation, we denote by Pr(-) the empirical probability. The demographic
parity is satisfied when Pr(ý 1/2 0) Pr(ý 1 1) holds. Thus,
Pr(ý = 1.y = 0/2 = 0) + Pr(ý = y, = 1/2 = 0) = Pr(ý = 1,y = 0/z = 1) + Pr(ý 1, = 1/2 1).
Since f[[ yl. = {(y :), we have
1
Σ
(1 - E(yi 1:)) (()::
+
Σ
l(yi, 1h))
m.,0 =
m. =gg==1,,,=
Σ
(1 llys: Ki)) + m.,1 1.
Σ
llyi, B.).
m4,1 1: 0,2,
By replacing Ein, (Vl: v1))
myy T,y,
Mo.0 (1 Lo,oww) +
1h10 LI (w) = ma,1 (1 Lo,((w) + 11,1 (w))
m².00
+
m,,1
m,,1
If mo,0 Mg,1 m1,0 m1,1, 1. this reduces (o, [_1,((0)) and (w)) I1,1 (10); the above condition reduces to
(w) + (1w((w) = - 1 ) (w))
sufficient condition the above condition Lo,o(w) (w)) and Lo, (wv) (,,)
In general, the condition of the above proposition does not hold. Observe that another sufficient condition to demographic parity is as follows:
m1.0
(1w)
m1.1
L1,1 (w)
0
m.
m.,1
Mu.0
(o,
Mu.1
Lo. (w)
mo.0
Mo.1
m..0
m-,1
m
m4,1
Let us define (ww) = mi.0 1/,1 (w) = me.1 m.,! Lo.1 (w), and c
I L1o(w),
mi.1
L (w), (w))
mo.0
Lo.0 (w).
m..0
m..1
m..c
mp.o
mo.1
Also, define |xle = maxf# - c, - x}. Then, we
m.
have the following bilevel optimization problem:
min max T (wx) [ ( (uxx)le)) {e(0.1]x(0.1]
+ (1 X2) W arg arg min \ (w) +11 A1)L( + (2T
A.2 PROOF FOR LEMMA 1
We continue from Sec. 3.1 and provide a full proof for Lemma ! Here we recall Lemma
Lemma (Quasi-convexity of F())). For d = if ((()), 9)(), and h(.) satisfy
1. h(w)= = or
2. if fi(.), 91(-), and ht()) are twice differentiable, A f + (a - x)) + V Vh((w)) > 0 for every X [0,
then F(X) quave, i.e., F(t + (1- t)X) < max { F(A), F(X)) for all t [0, 1] and X.
Also, if F() & then F()) {r} and sign (w) sign (01 (wx) [w()))
13

---

Published as a conference paper at ICLR 2021
Proof. it known that a continuous function f R -> R is quasiconvex if and only if at least one of the following conditions holds: 1) nondecreasing, 2) nonincreasing, and 3) nonincreasing and then nondecreasing (Boyd et al. 2004). We will prove the lemma by showing that the function F()) is quasiconvex by showing that it is nonincreasing and then nondecreasing. More precisely, we will show that fi (2xx) 91 (wx) is nonincreasing function. It is easy see that this directly implies that If (xx) - 91 (w)) is nonincreasing and then nondecreasing.
Case (h(w)) = 0) Consider λ and A such that \ > X2. we can show [1 S Si (w and 91 (uex,) 2 91 (wxx.) then this implies that fi (wx)=9) (1xx) is nonincreasing function. Indeed, this is very intuitive: If we increase X, the inner optimization problems puts a higher weight on fi(.,, resulting in lower value of fi (wx) and a higher value of gi (w"). We formally show this by
contradiction. By the definition of wx, we have the following two conditions:
(wx)) S (1)) + (c1 \1) (w), Vw, (1o))))))))))))))))))))))))))( ) + (c1 ( )efi(w),,) + (c1 ) S Aefi(w) + (c1 - X2)9 (w), Vw.
(1)
(2)
If the lemma's 's statement is false, one of the following three events should occur:
1. fi(w5)) > f( and øi (wwx) 2 gi (ww),) By adding these two inequalities with
respective weights Åι and ci -1, we have x fi (tw, ) (c1 1-))))( This contradicts equation [
(1)) fi
2. fı(w,,) S fi fi and 9ı (wx,) ) < 91 (wxx): Similarly, by adding these two inequalities with respective weights X2 and C1 X2, we have X2 (2 + (cI - A2)91 (ww,) > ( + (cI ()))(w,, This contradicts equation 2
3. f( fi ((wx)) and 91 (wxx)) ) < gi(wxx)): By adding equation with w w and equation 2 with w wx, we have
(1 + (cr (1)) da (1 + (a1- x2)g1(w()) I (xff( + (a )1)91( + )2fi(w)))) + (c1 be)gi(w5,,
By rearranging terms, we have
(A1 - (2)
(( S (1 - - 91 (1(w5)))
By dividing both sides by A ~ > O. we have fi ) f( S 91 (w - -1 (w This contradicts the condition as the left-hand side is positive while the right-hand side negative.
This completes the proof of the first claim by contradiction.
The second claim immediately follows the first claim. Since F(A) = (-1i((w)) (wx) 91 (wx)), we have dF(A) dA sign (fi (wx)= - 91 (wx)) d (fi (wx) 91 (1w))). As shown in the earlier part of this proof. fi(w)) gi (Wx) is nonincreasing function, i.e., (1 < 0. Thus, sign( dF(A) sign(g1 (wx) - fi (w))).
dA
Case 2 (If' f1(-,, 91 (-), and h(-) are twice differentiable, AV fi (wx) + (c1 g) + (2h(wx) > 0 for every À E [0, c.) In this part of the proof, we will denote wx by w for simplicity. To show that fi(w) 91 (w) a nondecreasing function (in A), consider the derivative:
(f) 9 (w)) (V) (w) dw dx
we implicitly differentiate (with respect to X) the following stationary equation. To compute due Zx*
(w) + (A) Vh(w) ( + (cr ())
dw
dw
dw
+ + Yx
Yx + v2h(w)
0
14

---

Published as a conference paper at ICLR 2021
By rearranging terms, we have
(AV + (a- - ()) (2h(w)) dw
AA -V(ii(w) (g)(w))
By the SouupppionnPPP/ttttH---------v- v is positive definite and hence invertible. Thus,
dw
+ (a X)V vVh(w))) (Vii
(gi(w)).
Yx
Therefore.
Yx (Ji(w) ((ww) = (V/i( (w)) (A (cl X)V2 + (2h(w)) (Vfi(w) - V (w)).
Note that f1 + (a - 91 + vh(ww) is also positive definite.
Thus,
d (fi(w) 91 (w)) is always negative, and hence fi(w) 91 (w) is decreasing function.
Now, observe that
d
(fi(w) - 9n (w))
(1i (f)(w) 9n (w)) E FAF((A)
dx
Therefore, if F()) A O, then F(A = {o} and sign (v) = sign (91(w) (w) - f1 fi(w)).
A.3 INNER OBJECTIVE'S CONVEXITY DOES NOT IMPLY OUTER OBJECTIVE'S CONVEXITY
0.6
0.5
0.1
0.0
0.0
0.2
0.4
0.6
0.8
1.0
Figure 2: F(A) is not convex, but quasi-convex.
We continue from Sec. 3.2 and provide an example where inner objective's convexity does not imply
outer objective's 's convexity. Consider the following strongly convex functions f-) and gi (-)::
e" + 91 (w) (u 1)
fi(w)
5
Shown in Fig. 2 is the outer objective function F(A). One observe that it is not convex. Note that is quasiconvex by Lemma]]
A.4 GRADIENT WHEN 2
We continue from Sec. 3.2 and derive the gradient of the outer objective function. Recall how formulated the general bilevel optimization problem:
min max Il.....
(f((w)) (x w> arg min Ed (il((w)) + (c. {()s((w))] + h(ww).
w
In this section, we will prove the following:
sign (gi- (w) ft- (V (w) Vg: (w)) T H (V]:(w) Vg((w)) Ox, F(A), Vi.
Assume that Ed= [A V (()x) + (c: - (x + <2h(w>) for every À E A. this part of the proof, we will denote wx by for simplicity.
15

---

Published as a conference paper at ICLR 2021
dw To compute dA," implicitly differentiate (with respect to A₂) the following stationary equation.
My V. + (1) Vh(w)
dw Vii(ur) + (a: - >,) gi(()) 9;)
dw axi
7 Vh(w) + A, V2 li(w)
dw
Sw
Ow 0x:
Σ
(cg - 22 02,
+ (2h(ww)
0
02,
13idd i+i
By rearranging terms, we have
Ow
( [ + (g -o-- + <2h(w))
= - -V[((i( - Vy:(w)).
07;
By the assumption, H = E (f() + (cg 99) ((w) is positive definite and hence invertible. Thus,
dw
- H (V -V.(())))).((w)).
07:
Now observe that F(A) = fi- (wx) g (ur2)- ). Therefore,
sign (fi-(w) - gr- (un) 0
(fi((w) ge-(w)) E F(A).
07;
Since
(w) (uz((w) ad; (Ji-
- gi- (ur)) - (VVsi- Vgr H Vg((w)),
we have
sign (fi((w) gi- (V))(V(( (g-((w)) H (Vfi(w) Vg(ww) E F(A). (4)
A.5 RATIONALE AND INTUITION BEHIND THE APPROXIMATION
We continue from Sec, 3.2 and provide more justifications for the gradient approximation technique. Assume that Σ (> V f: (wx) + (c, - A, >.) g, (wx] + vhh(w>) > 0 for every À E A. Then,
the gradient can be fully characterized as in equation 4
The rationale behind the approximation 7 (0, 0, if ([[V((w)) Vgi (w)) (2 Vgz(w)
0) that hns will be maximized at i* (ff(w) Vga(w)) This is because - (w:) is an inner product between H 1/2 (V. (w) Vg.- (w)) and H 1/2 (V)( Vg,(w)) and they are always perfectly aligned when it.
(V - (w))
This approximation is also intuitive. Recall that changing A2- affects the weights associated with fi- (w) and ga (w) in the inner optimization problem. Thus, changes in dç- will directly affect F(A) = l.fe (w) - gi (w)l. On the other hand, changing A for i * i" does not affect the weights associated with fe- (w) and gs (w) but only affects the weights of other terms, so it will only indirectly and weakly affect F()).
A.6 FAIRBATCH ALGORITIMS IN PSEUDOCODE
We contimue from Sec. 3.2 and present the FairBatch algorithms in pseudocode. Algorithms and show how À is adjusted for equal opportunity, equalized odds, and demographic parity, respectively. From the intermediate model each epoch (or after a certain iterations), we first obtain f and g( (ww), which correspond to the losses conditioned on each class. Then, one can update the current value of À by comparing f (ww and g(w).
16

---

Published as a conference paper at ICLR 2021
Algorithm 2: Adaptive adjustment of À w.r.t. equal opportunity.
Input:
Intermediate model, criterion, train data (Itrain Stroin Vtroin). previous lambda X (6-1), and FairBatch's 's learning rate a
output = model (Itrain)
loss criterion (output, Vtraan))
mean(loss((>) 1,7 = 0)]) > mean(loss((y) 1,7 7 1)]) (4 ( a, if mean(loss((y = 1, 0)]) < mean 1,2 -)])
(A((-1) + a,
A((-1),
otherwise
Output Next lambda (()
Algorithm 3: Adaptive adjustment of À w.r.t. equalized odds.
Input: Intermediate model, criterion, train data (Itrain Stroén Utroin): previous lambda X (t-1), and FairBatch's ' learning rate
output model (Itrain)
loss criterion (output, Vtrain)
dy=0 mean(loss[(y = 0, Z 0)]) mean(loss] [y 0, 1)])
dy=1 mean(loss(( (y = 1, 0)) mean(loss (y = 1, = 1)])
Jdy oo > Idy=1| then
{ (e-1) +
if d > 0
( = 1 (t-1)
if dy <0 0 otherwise
(1-1)
else
1 (t-1) + a,
dy
1
22 (1-1) a,
if dy=1 <0 otherwise
(1-1)
Output : Next lambda (t)
B APPENDIX - EXPERIMENTS
B. OTHER EXPERIMENTAL SETTINGS
We continue from Sec. 4 and provide more details on experimental settings. We use the Adam optimizer for all trainings. We perform cross-validation on the training sets find the best hyper- parameters for each algorithm. We evaluate models on separate test sets, and the ratios of the train versus test data for the synthetic and real datasets are 2:1 and 4:1, respectively.
B.2 EQUALIZED ODDS RESULTS
We continue from Sec. and show Table which compares the performances of all the fair training techniques on the synthetic, COMPAS, and AdultCensus test sets w.r.t. equalized odds. The key observations are the same in Table ! where overall FairBatch has the most robust performance against the state of the arts w.r.t. accuracy, fairness, and runtime.
B.3 EXTENSION OF ADAFAIR
We continue from Sec. and provide more details on how we extend AdaFair, which already supports ED, also support EO and DP. The extension EO is straightforward as EO is relaxed version of ED where only the = 1 class is considered when measuring disparity. Hence, we only reweight examples in the y 1 class well. The extension DP is done by giving more weights the
17

---

Published as a conference paper at ICLR 2021
Algorithm 4: Adaptive adjustment of X w.r.t. demographic parity.
Input: Intermediate model, criterion, train data (Itrain Stroin Vtroin).
previous lambda X (t-1), and FairBatch's S learning rate
output model (Itrain)
loss criterion (output. 1)
dy=0= sum(loss (y 0, = 0))) (0])//enn /len/z 0) sum(loss (y = 0, 1)])/len(z = 1)
dy=1 sum (y = 1,2 = 0)1) /lenzz 0) sum(loss (y = 1, 1)])/len(z =
|dy=o > |dy=1| then
X (t-1)
if dy=0 0
1
1 (t-1) +
if dy=0 < 0
1 ((-1)
otherwise
else
b (t-1) + a,
dy= > dy==
1
(1-1) a,
(L-1)
otherwise
Output:Next lambda (()
Table 4: Performances on the synthetic, COMPAS, and AdultCensus test sets w.r.t. equalized odds
(ED). The other settings are identical to Table
Synthetic
COMPAS
AdultCensus
Method
Acc.
ED Disp.
Epochs
Acc.
ED Disp.
Epochs
Acc.
ED Disp.
Epochs
LR
885+.000
..00
400
.681=.002
.239=.006
300
8454.001
.056+t.033
300
Cutting
8594.001 .036:.004
650
.665=.005
.066=.008
400
.8224.001
.062+:.05
600
RW
856:1.000
.038:1.002
350
.685...000
.137:..00
300
.8351.001
.134:1.006
100
LBC
858#t0001
.026:t.000
8800
.673:.002 .063=.005
9000
.840+.002 .027:1.004
3300
FC
865:1.000
.030:1.001
800
.677:1.004
.101:.0044
50
84111.011
.038:1.003
300
AD
857:1.000 .030=:.001
1200
.683
.082=.0027
450
.8431.002
.033:1.02
500
AdaFair
868+.001 .029:t.022
22400
.675=.000
..666.002222
9600
.8434.001
.038+.002
7800
FairBatch
855.1.001 .038-1.002
400
.682.t (0)
.052 .014
100
.8434.001
.036:1.022
500
positive examples of a certain sensitive group z that suffers from a lower positive prediction rate than other groups
B.4 FAIRNESS CURVES
We continue from Sec. 4.1 and show in Figures and the the EO and DP disparity curves against the number of epochs for each fairness technique on the synthetic dataset. We also directly compare the curves of all fairness techniques one graph as shown in Figure Since LBC and AdaFair require more than 10x many epochs than other methods, we only show their first 1000 epochs. As result, FairBatch is one of the fastest methods to converge to low EO or DP disparities.
B.5 TRADE-OFF CURVES OF FAIRBATCH
We continue from Sec. 4.1 and show in Fig. 6 the accuracy-fairnee trade-off curves of FairBatch for EO and DP the synthetic dataset. FairBatch be tuned by making it "less sensitive" to disparity. In Algorithms 2 and 44 notice that the parameters are updated there is any disparity among sensitive groups. We modify this logic where the parameters only updated if the disparity is
18

---

Published as a conference paper at ICLR 2021
02
0.
100 disp.
0.2
1122
0.
0.1
4.0
X01
230
ac
26
30
240
120
1000
Epocha
Epaciss
Egochs
Epocha
(a) LR
(b) Cutting
(c) RW
(d) LBC
63
02
02
62
0.1
100
1200
Epochs
Epochs
Epociss
Mpocts
(e)
FC
AD
gg)
AdaFair
(h) FairBatch
Figure 3: EO disparity curves of algorithms on the synthetic dataset.
0:35
135
disp.
0.30
130
0.30
0.35
115
0.12
0.30
130
0.85
135
0.20
0.00
Epurchs
Epochs
Epocha
Epurcis
(a) LR
(b) Cutting
(c) RW
(d) LBC
895
8:55
3:55
DP disp.
8:11
1:15
810
110
000
8:0
110
1900g
Epochs
Egoche
Egochs
Epoche
(e) FC
(f) AD
AdaFair
(h) FairBatch
Figure 4: DP disparity curves of algorithms on the synthetic dataset.
above some threshold T. The trade-off curves in Fig. are thus generated by adjusting T. For both EO and DP, we observe that there is clear trade-off between accuracy and disparity.
B.6 WALL CLOCK TIMES
We continue from Sec. 4. and show in Table wall clock times (in seconds) of the experiments in Table where we compare FairBatch against all the faimess techniques on the synthetic, COMPAS, and AdultCensus datasets. As result, each runtime proportional the number of epochs shown in Table When comparing the runtimes of individual batches, FairBatch's 's batch takes 1.5x longer to run than LR's batch.
Table 5: Wall clock times (in seconds) of the experiments in Table using the same settings.
Dataset
I.R
Cutting
RW
LBC
FC
AD
AdaFair
FairBatch
Synthetic
5.71
5.67
17.24
208.47
16.05
3.97
294.31
5.25
COMPAS
6.07
3.34
7.48
94.10
2.76
6.93
215.39
3.00
AdultCensus
22.96
7.70
10.02
558.31
28.71
31.76
791.58
46.79
19

---

Published as a conference paper at ICLR 2021
LR
100 disp.
Reweighing LBC
DP disp.
3.20
Cutting
0.15
Reweighing
AD FairBatth
LBC
PC
0.1-
0465
Adaaair
FairBatch
0.0
2001
400
600
3M0
1000
3.0
0
2001
3.1
600
300
1000
Epochs
Epochs
(a) disparity curve FairBatch and baselines. (b) disparity curve FairBatch and baselines.
Figure 5: Epochs- fairness disparity curves of all algorithms together.
0.25
0.10
EO disp.
1.08
DP disp.
01.30
0.000
0.33
1..0
0.30
01:21
0.06
0.856
3800
0.965
0,800
0.875
0,880
0.80
01:0
0.84
0.86
0.86
Accuracy
Accuracy
(a) Accuracy- EO disparity trade-off curve.
(b) Accuracy-DDaa DP disparity trade-off curve.
Figure 6: Accuracy-faimess disparity trade-off curves of FairBatch on the synthetic dataset.
B.7 COMPARISON WITH ADAFAIR
We continue from Sec. and compare the class weights between FairBatch and the AdaFair algorithm. For AdaFair, the class weights calculated by adding all example weights in each class. Fig. shows the weight changes of each algorithm. Overall, the trends of the weights are similar. Again, the advantage of FairBatch is that it run within model training instead of using multiple model trainings as in AdaFair.
0.35
0.5
Class weights
Class weights
0.4
0.30
76.
8..55
0.70
0.1
0.15
(3)
1001
300
2:01
2001
300
Number models
Epochs
Number of models-class weight curve of AdaFair.
(b) Epochs-class weight curve of FairBatch.
Figure 7: Comparison of the weight changes on AdaFair and FairBatch w.r.t. equalized odds on the synthetic dataset.
B.8 EXTENSION FAIRBATCH TO MULTI CLASSIFICATION
We continue from Sec. 4.2 and explain how FairBatch can be extended to support multi classification by adjusting more À parameters. For example, for ED, the label attribute has classes, and each class connects to m As. We adjust m As in the class y = at each epoch, where the class = has the highest ED disparity at that epoch.
20

---

Published as a conference paper at ICLR 2021
B.9 FAIRBATCH WITH IMPORTANCE SAMPLING
We continue from Sec. 4.3 and show Fig. 8 which plots the convergence of FairBatch when merged with loss-based weighting batch selection. As result, FairBatch uses about 50 fewer epochs to converge to low disparities compared to not using loss-based weighting.
0.3
Fatch
0.55
FairBatch FairBusch importance sampling
FairBatch importance sampling
120 disp.
DP disp-
3.20
0.2
3.10
0065
3.00
Epnchs
Epochs
(a) EO disparity curve of FairBatch.
(b) DP disparity curve of FairBatch.
Figure 8: Fairness curves of FairBatch on the synthetic dataset, with/without loss-based weight- ing (Loshchilov and Hutter 2016).
21


Reviews:
[{"review_id": "sDe09X7uNcV", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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 problem is well-motivated. The paper is well-organized and written. The claims are well-supported by theoretical analysis and experimental results. In contrast with previous work that requires nontrivial re-configurations in machine learning, FairBatch formalizes the sampling probability as an implicit connection between the inner (for fairness criterion) and outer (task) optimizer in bilevel optimization.\n[Pro 1] This paper provides insights into fairness and machine learning from the lens of bilevel optimization, emphasizing the inverse proportional relationship between sampling probability and loss for sensitive groups.\n[Pro 2] FairBatch is not only consistent with intuition but also easy to implement.\n[Con 1] It would be helpful for the authors to summarize their contributions more from the fairness aspect. I am confused about the ability of FairBatch to mitigate disparate accuracy. Is it designed especially for the unfairness caused by minimizing average error that fits majority populations [to clarify my point, please refer to the 2nd cause in Section 2.1, abs-1810-08810]?\n[abs-1810-08810] Alexandra Chouldechova, Aaron Roth: The Frontiers of Fairness in Machine Learning. CoRR abs/1810.08810 (2018)\n[Con 2] Is the number of total disparities (as the authors claimed in Section 3.2) d in Section 3 the lambda dimension? No explanation is provided for this notion. If true, is d equal to n_z-1? Why not C(n_z, 2)? (C stands for Combination). In practice, when the sensitive space is sometimes continuous and big, there would be too many pairs to compute. More details about d will strengthen the submission. I am not requesting more experiments, but want to understand how FairBatch works in practice.\n[Con 3] As for the experiments, the analysis fails to go beyond single-dimensional performance summaries. Also, alpha is a vital hyper-parameter. However, the criterion used for selecting the final setting is not clear in this paper.", "extra_scores": {}, "extra_text": {}}, {"review_id": "izJPu1NCsPV", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work proposes a modification to stochastic gradient descent with the goal of having the resulting model satisfy fairness constraints. The modification entails changing the sampling procedure to select the minibatches. Rather than sampling the instances at random, the authors propose a procedure which first generates probabilities for each of the instances by first solving an optimization problem which corresponds to different fairness objectives. Training is otherwise carried out as usual. The authors outline the optimizations corresponding to several fairness objectives, and provide an empirical demonstration which compares the proposed approach to the current state of the art where the proposed method performs quite well.\n\nOverall, I think this is a nice, simple, idea which appears to work well in practice. The authors do a commendable job of describing both the problem and solution in plain terms while also providing technical details of the implicit weighting procedure.\n\nWhat I don’t quite understand is the advantage of modifying the batches versus incorporating the inclusion weights in the loss function itself. It seems that the proposed model will be equivalent to weighting the loss as the number of mini batches grows very large, however the experimental results seem to indicate otherwise. Can the authors provide some intuition for this? Specifically, should we expect equivalent performance between the proposed method and example reweighting if the same probability weights are used as proposed in the paper and we weight random examples by those probabilities as the number of minibatches grows? If so, how should we be thinking about this tradeoff in the case where we use a small to moderate number of minibatches? \n\nSmall edits:\n- In the first sentence of 3.1 there is a misspelling of optimization.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "eDL6yfhF_9", "reviewer": "AnonReviewer3", "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": "In this paper, the authors study the problem of training fair machine learning models through the lens of bi-level optimization. In particular, they propose a method, denoted FairBatch, that adaptively selects different batch-sizes for different protected groups to impose a certain measure of fairness. This is achieved by solving an outer optimization problem that imposes fairness by computing a batch-size ratio for different groups. This batch selection is then used to train the original model. The proposed approach can impose several prominent fairness measures, among which: equal opportunity, equalized odds, and demographic parity.  To demonstrate the efficiency of FairBatch, the authors conducted several experiments on synthetic and real datasets. The results show the proposed method is easily implementable, scalable and can achieve comparable performance when compared to existing methods. \n\nPros:\nThe authors approached the problem of fair machine learning by iteratively adapting the batch-size ratio for different protected groups. The approach is novel and was implemented through a novel bi-level optimization formulation. \n\nThe proposed method is easy to implement, scalable, and can readily improve fairness for any pre-trained model. \n\nClarity: The main body of the paper is concise and clearly written with very few typos.\n\nCons:\nThe theoretical part of the paper requires a more careful and detailed analysis. First, the inner minimization problem in section 3.1 has $w_{\\lambda}$ appearing in the objective. I think this should be $w$ instead. This also affects the proof of Lemma 2 in the supplementary material. Moreover, the author computes the gradient of the objective of the outer optimization problem, $F(\\lambda)$. Being a finite max, this function might not be differentiable. \n\nIt seems that positive definiteness assumptions in sections A.1 and A.4 are not easy to check. The authors did not comment on the practicality of these assumption nor they provided a method to check whether they hold. Moreover, I believe these assumptions should be moved to the main body of the paper.\n\nI believe the paper is worth publishing after re-working the theoretical part.\n\nMinor Comments:\n1.\tPage 3: In defining the bi-level optimization problem, the objective function of the inner minimization is a function of $w$. This should be explicitly included in the formulation (it is currently hidden in $\\hat{y_i}$) \n2.\tIn the proof of proposition 2 in Appendix A, should it be $\\ell(|1-y|, \\cdot) = 1 - \\ell(y,\\cdot)$?\n3.\tIn Sections A.2 and A.4, the subscript of the functions $f_i$ and $g_i$ are missing in some expressions (also in Lemma 1). \n\nThe related material are referenced and well-discussed in the paper. The authors clearly positioned their work in the related field and discussed their contributions in comparison to other similar works.\n\n-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\nUpdate after the author's response:\n\nI was not convinced by many of the authors' responses.\n\n1. While the author(s) agree that $F(\\lambda)$ is non-differentiable, they keep the gradient updates in the paper with a footnote referring to sub-gradient methods in (Boyd et al. 2004)? Moreover, it is not clear what the sub-gradient would refer too when the loss function is non-convex, what would $H_{\\lambda}$ refer to in section 3.2? One possible way to solve this issue might be through a mild smoothing technique. But as presented the theoretical part is not rigorous.\n\n2. The positive definiteness assumption in Lemma 1, although will most probably hold when the three functions are convex; this limits the application of the results as typical ML loss functions involve non-convexity.\n\n3. My comment on the subscript of the functions $f_i$ and $g_i$ in Lemma 1 was addresses by adding a comment mentioning that the subscript will removed for the simpler notation. I believe one subscript does not make the notation complex. Rather defining two notations might confuse the reader.\n\nDespite my tendency to have this novel idea and work published, I believe the authors need to be more careful in writing and dealing with the theoretical section of the paper. I will hence decrease the score to 4.\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "8N3DwN9pVU", "reviewer": "AnonReviewer4", "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": "The paper addresses the problem of fairness by viewing the task of learning as a bilevel optimization problem. The task of learning is decomposed to two levels: 1- Choosing a batch of data samples so as to satisfy a given fairness criterion; 2- training the model using the chosen batch. The main contribution of the paper is that it proposes a way to sample batches of data that would satisfy a given fairness criterion and incorporates that into model training. The authors show the performance of models using their proposed approach on synthetic and real-world data. \n\nThe paper is well-written and points to a promising direction in handling fairness using (non-causal) notions of fairness. The point is to find batches of data that mitigate disparities in prediction. The batches are chosen by finding lambdas that minimize the disparity in prediction as opposed to necessarily setting them to zero. This is a fine distinction. The update rules of the resulting optimization problem are also presented. \n\nThe proposed approach is tested on multiple datasets. According to Tables 1 and 2, FairBatch does not necessarily improve performance. In some cases, the performance is lower than that of other methods, but given that overall, the performance is comparable with other methods and FairBatch is sometimes also faster in number of epochs, one can say that the potential in FairBatch is worthwhile. \n\nMinor comments:\n\nIn Figures 3 and 4 of Section B4, it would be better if we can see the convergence rates plotted in one figure, using different colors for each algorithm. This way, one can compare the results more efficiently.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All the reviewers and I agree that the proposed approach is interesting and the paper is overall well written. However, I agree with R3 that the paper  need further re-working the theoretical part (see the post-rebuttal comments of R4). Thus, I would encourage the authors to carefully address the comments of the reviewers in the revised version of the paper, which would ultimately improve the quality of the paper. 
Decision: Accept (Poster)