Blind Pareto Fairness and Subgroup Robustness
Authors: Natalia Martinez
Martin Bertran
Afroditi Papadaki
Miguel R. D. Rodrigues
Guillermo Sapiro
Venue:  (2021)
Keywords: fairness
fairness in machine learning
fairness without demographics
robustness
subgroup robustness
blind fairness
pareto fairness

Abstract: With the wide adoption of machine learning algorithms across various application domains, there is a growing interest in the fairness properties of such algorithms. The vast majority of the activity in the field of group fairness addresses disparities between predeﬁned groups based on protected features such as gender, age, and race, which need to be available at train, and often also at test, time. These approaches are static and retrospective, since algorithms designed to protect groups identified  a priori cannot anticipate and protect the needs of different at-risk groups in the future. In this work we analyze the space of solutions for worst-case fairness beyond demographics, and propose Blind Pareto Fairness (BPF), a method that leverages no-regret dynamics to recover a fair minimax classiﬁer that reduces worst-case risk of  any potential subgroup of sufﬁcient size, and guarantees that the remaining population receives the best possible level of service. BPF addresses  fairness beyond demographics, that is, it  does not rely on predeﬁned notions of at-risk groups, neither at train nor at test time. Our experimental results show that the proposed framework improves worst-case risk in multiple standard datasets, while simultaneously providing better levels of service for the remaining population, in comparison to competing methods.

Under review as a conference paper at ICLR 2021
BLIND PARETO FAIRNESS AND SUBGROUP ROBUSTNESS
Anonymous authors Paper under double-blind review
ABSTRACT
With the wide adoption of machine learning algorithms across various applica- tion domains, there is growing interest in the fairnsss properties of such algo- rithms. The vast majority of the activity in the field of group faireess addresses disparities between predefined groups based on protected features such gen- der, age, and race, which need to be available at train, and often also at test, time. These approaches
static and retrospective, since algorithms designed to protect groups identified a priori cannot anticipate and protect the needs of different at- risk groups the future. In this work we analyze the space of solutions for worst- case faimess beyond demographics, and propose Blind Pareto Fairness (BPF), a method that leverages no-regret dynamics to recover a fair minimax classifier that reduces worst-case risk of any potential subgroup of sufficient size, and guaran- tees that the remaining population receives the best possible level of service BPF addresses fairness beyond demographics, that is, it does not rely on predefined notions of at-risk groups, neither at train nor test time. Our experimental results show that the proposed framework improves worst-case risk in multiple standard datasets, while simultaneously providing better levels of service for the remaining population, in comparison to competing methods.
1 INTRODUCTION
A large body of literature has shown that machine learning (ML) algorithms trained to maximize average performance on existing datasets may present discriminatory behaviour across pre-defined demographic groups (Barocas Selbst (2016); Hajjan et al. (2016)), meaning that segments of the overall population (data) are measurably under-served by the ML model. This has sparked interest in the study on why these disparities arise, and on how they can be addressed (Mitchell et al. (2018); Chouldechova & Roth (2018); 8); Barocas et al. (2019)). One popular notion is group fairness, where the algorithm has access to a set of predefined demographic groups during training, and the goal is to learn model that satisfies a certain notion of fairness across these groups (e.g., statistical par- ity, equality of opportunity) (Dwork et al. (2012); Hardt et al. (2016)); this is usually achieved by adding a constraint to the standard optimization objective. It has been shown that optimality may be in conflict with some notions of fairness (e.g., the optimal risk different across groups) (Kaplow & Shavell (1999); Chen et al. (2018)), and perfect faimess can, in general, only be achieved by degrading the performance on the benefited groups without improving the disadvantaged ones. This conflicts with notions of no-harm faireess such as in (Ustun et al. (2019)), which appropriate where quality of service is paramount. Notions such as minimax fairness, commonly known as Rawlsian max-min fairness from an utility maximization perspective (Rawls (2001: 2009)), com- bined with Pareto efficiency, naturally address this no-harm concern (Martinez et al. (2020)).
Recent works study fairness in ML when information about the protected demographics is avail- able, for example, due to privacy or legal regulations (Kallus et al. (2019)). This is an important research direction and has been identified stein et al. (2019)), since many applications and datasets in ML currently lack demographic records. We therefore study the problem of building minimax Pareto fair algorithms beyond demographics, meaning that not only we lack group membership records but also have no prior knowledge about the demographics to be considered (e.g., any subset of the population can be a valid protected group). This has the advantage of making the model robust to any potential demographic even if they are
major industry concern (Veale & Binns (2017); Hol-

---

Under review as a conference paper at ICLR 2021
unknown at the time of design, or change through time; it is also efficient, since the model offers the best level of service to all the remaining (i.e., non-critical) population.
Main Contributions. We analyze subgroup robustness, where a model is minimax fair w.r.t any group of sufficient size (regardless of any preconceived notion of protected groups); we also adhere to the notion of no-harm fairness by requiring our minimax model to be Pareto efficient (Mas-Colell et al. (1995)) by providing the best level of service the remaining population. A model with these characteristics has performance guarantee even for unidentified protected classes.
We show that being subgroup robust w.r.t. an unknown number of groups, where no individual group is smaller than a certain size, is mathematically equivalent in terms of worst group performance to solving a simplified two-group problem, where the population divided into high and low risk groups, thereby providing a clear means to design "universal" minimax fair ML models. We further show the critical role of the minimum group size by proving that, for standard classification losses (cross- (cross-entropy and Brier score), there is limit to the smallest group size we can consider before the solution degenerates to a trivial, uniform classifier. We additionally study the cost of subgroup robustness when compared to learning model that is minimax fair w.r.t. predefined demographics.
We then propose Blind Pareto Fairness (BPF), simple training procedure that leverages recent methods in no-regret dynamics Chen et al. (2017) to solve subgroup robustness subject to a user- defined minimum subgroup size. Our method is provably convergent and can be used on classifi- cation and regression tasks. We experimentally evaluate our method on a variety of standard ML datasets and show that effectively reduces worst-case risk and outperforms previous works in the area. Although our work is motivated by fairness, subgroup robustness has applications beyond this important problem, see for example (Sohoni al. (2020a); Duchi et al. (2020)).
2 RELATED WORK
A body of work has addressed fairness without (explicit) demographics by using proxy variables to discover the (unobserved) protected population labels (Elliott et al. (2008); Gupta et al. (2018); Zhang (2018)). These methods contrast with our assumptions by relying on a preconceived notion on what the protected demographics are (i.e., the protected demographics are known, but unobserved), since prior knowledge needed to design useful proxy variables. Moreover, it has been reported that these approaches can exacerbate disparities by introducing undesired bias (Chen et al. (2019); Kallus al. (2019)); aiming be fair by inferring protected attributes may be in conflict with privacy or anonymity concerns. These works might need re- re-training if new protected classes are identified, since model trained under these conditions may be considerably harmful on an unknown population. This phenomena further supports the value of blind subgroup robustness.
Individual fairness (Dwork et al. (2012)) provides guarantees beyond protected attributes. but re- quires predefined similarity functions which may be hard or infeasible to design for real-world tasks. The works of (Hébert-Johnson et al. (2017); Kearns al. (2018)) address fairness w.r.t. subgroups based solely on input features, and while these works greatly extend the scope of the protected de- mographics, they still rely on labeled protected features for guidance. The work of Sohoni et al. (2020b) partitions the input space to address robust accuracy. We note that partitions,' based only on the input space of the model do not modify the solution of risk-based Pareto optimal models, since the optimal classifier for any input value remains unchanged (i.e., there is no conflict between objectives for any value of the input space, see Theorem 4.1 in Martinez et al. (2020)). In our work we consider subgroups based not only all input features but also on outcome. which broadens the scope to all conceivable subgroups based on the information available to the model. For many risk-based measures of utility, such crossentropy. Brier score, or L2 regression loss, the optimal classifier can be expressed as a function of the conditional output probability p(Y X)), X being the input (features) and Y the output. In particular, if we only consider groups that introduce covariate shift (i.e., p(X A) varies across different values of the group membership A) but do not change the conditional target distribution (p(YIX, A) = p(Y for all A), then the set of Pareto classifiers only contain one element and the Pareto curve degenerates to the utopia point. By specifically tak- ing outcomes into account in our partition function, we allow for robustness perturbations on the conditional distribution A)
In this work we consider "partition" and "subgroup" interchangeable.

---

Under review as a conference paper at ICLR 2021
There are two recent approaches that are the closest to our objective (that of protecting unknown and unobserved demographics). One is distributional robust optimization (DRO) (Hashimoto et al. (2018); Duchi et al. (2020)), where the goal is to achieve minimax fairness for unknown popula- tions of sufficient size. Similar to our work, they minimize the risk of the worst-case group for the worst-case group partition, they use results from distributional robustness that focus the attention of the model exclusively on the high-risk samples (i.e., their model reduces the tail of the risk distribu- tion). However, they do nol explicitly accouni for Pareto efficiency, meaning that their solution may be sub-optimal on the population segment that lies below their high-risk threshold (doing unneces- sary harm). The other recent method that tackles the minimax objective is adversarially reweighted learning (ARL) (Lahoti et al. (2020)), where the model trained to reduce positive linear combi- nation of the sample errors, these weighting coefficients are proposed by an adversary (implemented as a neural network), with the goal of maximizing the weighted empirical error. This method, while computationally attractive, provides no guarantees about the optimality of the adversary, tradeoffs are also indirectly controlled by adversary capacity and training parameters, which may less inter- pretable than constrains on group size or risk thresholds. Our results on critical group size indicate that a sufficiently large capacity adversary should produce trivial uniform classifier if no additional constraint is provided. We experimentally compare with these two methods when appropriate.
3 PROBLEM FORMULATION
3.1 MINIMAX FAIRNESS
We first consider the supervised group fairness classification scenario (Barocas al. (2019)), where we have access to dataset D = {1 yi, a;) a,)) p(X, Y, A)8" containing i.idd triplets. Here E X denoles the input features,
E y the categorical target variable, and E A group membership. We consider classifier h H belonging to an hypothesis class H whose goal is to predict Y from X, h X + A 1 note that h(X) can take any value in the simplex and is readily interpretable as distribution over labels Y. Given loss function L A 1 x A 11 + Rt, fairness considered in the context of a Multi-Objectiin Optimization Problem (MOOP), where the objective is to learn a classifier that minimizes the conditional group risks {R, (1)))a)).
min R4 (h), RIA (h)), RCH R. (h) = (x.YIA=ul((((X)) Y)).
(1)
The solution to this MOOP may not be unique (e.g., the optimal classifier of different groups differs), and therefore there is a set of optimal (Pareto) solutions that can be achieved. It is possible that none of these Pareto solutions satisfy some group fairness criteria (e.g., equality of risk), meaning that achieving perfect fairness comes at the cost of optimality (Kaplow & Shavell (1999); Bertsimas et al. (2011)). In this work we do not to compromise optimality, meaning that we do not degrade the performance of a low-risk group if it does not directly benefit another, and consider minimax fairness approach (Rawls (2001; 2009)), where the goal is to find a Pareto-optimal classifier that minimizes the worst-case group risk,
min max (h), PA.H = (h ThE::YM E H (h) 3a E A with Ra(h) < (a())). NE aEA
(2) PA.N represent the set of optimal (Pareto) classifiers in H. given group set A, meaning that there is no other model in the hypothesis class whose associated group risks are uniformly better for all groups. If the loss function is convex w.r.t. the model h, and the hypothesis class H is convex set,?, linear weighting problem on the conditional group risks (minkEH. EM R. (h): Σ Ma 1, H, > 0) characterizes all of the Pareto solutions. Solving Problem 2 is equivalent to finding the weighting coefficients such that classifier with the minimum worst-case group risk is the solution (Geoffriion (1968); Chen et al. (2017); Martinez et al. (2020)).
3.2 BLIND PARETO FAIRNESS
In this work we consider more challenging problem, namely Blind Pareto Fairness (BPF), where the group variable a and the conditional distribution p(A[X, Y' are completely unknown (not just
Meaning that for any h, h² E 76 and À E [0, 1). exists hy E 7. hx(x) = Xh(x) + (1- X) X.

---

Under review as a conference paper at ICLR 2021
unobserved), even at training time. Here the goal is to learn a model that has the best performance the worst-group risk of the worst partition density p(A|X, Y) ("sensitive" group assignment), subject to a group size constraint (p(1= 2 p. Va). We formulate the following new problem,
R
min REPAN
max p Y) s.t. p( A a) 2 P. Va
max (h). acA
(3)
Here R is the minimum worst group error achieved for the worst partition density with known number of partitions |AI. The partition size constraint plays key role on the solution to Problem 3, as we will show below,?. 3 Problem 3 is undetermined in the sense that it admits several worst partition densities and classifiers for |A] > Fortunately, it is possible show that the minimum worst group error R in Problem 3 is the same as the one achieved if we were to consider an alternative formulation where a variable A C (0, 1} represents the worst-group risk membership, this is shown in Lemma 3.1. This makes the study of the binary problem attractive when we wish to minimize the number of assumptions we make on the protected groups. Here the objective becomes
ht . (A|X, R² = ={rgg] min НEPA.
max Ra (h), ac(0,
max p ((A(X,Y) s.t. p(A=(A > P. Va E 10,
(4)
where we overload the notation PA.H in the context of Problem 4 to refer to the Pareto set for binary group distribution. Lemma 3.1 shows that the minimum worst risk R is the same for problems 3 and 4, hence, we focus our analysis the latter throughout the text. There are two main advantages of working with the binary problem, the first is that finding the worst partition p(A X, Y) for given h is straightforward when Al = 2. The second is that in general not know the number of groups we wish to be fair to, and this equivalence shows that it is sufficient to specify the minimum size group must have before it is considered for the purposes of minimax fairness.
may
Lemma 3.1. Given an hypothesis class H and a finite alphabet, A |A] 2 2, problems 3 and 4 have the same minimum worst-group risk solution R if [
A question that arises from Problem is how the optimal classifier and partition function depend on the partition size. In Lemma 3.2, we show the existence of a critical size p" for standard classification losses (cross-entropy and Brier score) whereby solving Problem for partitions smaller than p leads to uniformly random classifier. This result shows that attempting to be minimax fair w.r.t arbitrarily small group sizes yields trivial classifier with limited practical utility.
Lemma 3.2. Given Problem 4 with x) > 0 VX,Y; Y,4 and let the classification loss be cross- entropy or Brier score. Let
1
h(X): : :x(())
vx, Vi (o....,Vi 13, [>]
be the uniform classifier, and let h H. There exists a critical partition size
p² = [ X)] S
log [3]
if tcE
such that solutions to Problem 4, Ap S p", are h = and R = R
D--1 DT if Ens
That is, any partitions smaller than p² yield the uniform classifier with constant risk R.
It is straightforward to prove that R is non-increasing with p (see Supplementary Material A. 1). A natural question that arises is what is the additional cost in optimality we pay if we apply subgroup robustness instead of optimizing for a known partition. Lemma 3.3 provides an upper bound for the cost of blind fairness, showing that it is most the difference between R* and the risk of the baseline model, and can be zero (no cost) if the known group happens to be the worst case partition for the dataset. Moreover, the upper bound decreases with larger group size, and is in no scenario larger than the difference between the risk of the uniform classifier and the baseline classifier for BE and CE losses. Figure shows these concepts graphically.
'Attempting to be minimax optimal w.r.t. P smaller than value will result in random classifier, the minimax risk of the partition directly dependent on p. "This restriction can be lifted and a similar result holds, see Supplementary Material for details.

---

Under review as a conference paper at ICLR 2021
Lemma 3.3. Given a distribution p(X,Y) and any predefined partition group p(A' with A' E A' ,|A' finite. Let h, R = {arg} min max (h) be the minimax fair solution for this heH a'E.A'
partition and its corresponding minimax risk. Let h'' and R be the classifier and risks that solve Problem with p = mina' p(a'). Then the price of minimax fairness can be upper bounded by
max R (h²) EA
R"
min R(h). hEH
(5)
pre-detined partition
Best (remaining) group risk
Equal risk Inc EPF its worst partition
0.5
BPF on its worst partition
of worst group
pre-defined partition
0.3
Minimax result on its worst partition
Optimal average classifier
Subrgrose
robosttoest
0.3
0.1
0.2
0.2
0.4
0.6
0.8
0.0
0.1
0.2
0.3
0.4
Worst group size P
Worst group risk
Figure 1: Left figure illustrates Lemma 3.3 by comparing worst casc risk with known and unknown partitions. BPF compared against minimax fairness on their own worst partition and the predefined partition,optimg average risk (minaE R(h)) is shown blue. The price (blind) fairness is the difference in risk we incur when the groups are not known beforehand (BPF vs minimax fairness on predefined partition), represented by the difference between continuous red and black curves. Conversely, optimizing for known partition (continuous black) leaves another group of the same size with significantly larger risks (dashed black) than what could have been achieved with BPF (dashed red). Right figure highlights the importance of the Pareto optimality constraint, since the space solutions for subgroup robustness without it contains sub-optimal models that do unnecessary harm on the remaining population. The group risks over the worst partition of the minimax classifier are shown in black for reference; values corresponding to the same group size are linked by arrows. Values shown are Brier scores obtained synthetic example, details in Supplementary Material A.2.
In the following section, we provide practical algorithm that asymptotically, solves Problem and yields classifier that both minimizes the worst-group risk and is also Pareto-efficient w.r.t. the remaining population. (All proofs are presented in the Supplementary Material A.
4 OPTIMIZATION
In order to develop our optimization approach, we begin by showing that for group sizes p S 1 we can drop the innermost max operator in Problem 4, and we only need to consider the risk for the a = partition on a partition of size exactly equal to p (i.c., p(A = 1) = p). This is presented in the following lemma, proved in the Supplementary Material.
1 Lemma 4.1. Given Problem 4 with minimum group size S 2. the following problems are equiva-
lent:
min AEPA,
max P(A Y) s.t. p(A a) P. Va 10,1}
max (h) (E
min НEPAR
max P(A X, Y) s.t. p A 1) p
(
(6)
We note that the right hand side in Eq. is in itself valuable optimization problem for p > 1/2, since it equates to efficiently minimizing the risk of the at-risk majority. The Pareto optimality constraint in this scenario is easy to enforce if the base loss function {fh(x), y) is both bounded (i.e., E(h(z), y) < C Vz, h h E X x y x H), and strictly convex w.r.t. model h. The result is shown in the following lemma.
Lemma 4.2. Given the problem on the right hand side of Eq. 6, a convex hypothesis class H. and bounded loss function 0 S E(h(z),g) & C Va. y, E X x y x H that is strictly convex w.r.t its
*R(h) Ex.y (e(h(X) Y)
"The algorithm is iterative, we prove convergence to the optimal solution with the number of iterations.

---

Under review as a conference paper at ICLR 2021
first imput h(r), the following problems are equivalent:
{arg} min bEPAW
max
Rh) = =arg) min hET
sup p(A|X, Y) s.t. (
1
p Y) s.t. p A A=11 =
p(A=1|X,)) > 0, 4X,Y
Where we explicitly add {arg) to both sides of the equivalence to indicate that these problems are also equivalent in terms of the models h that achieve these minimax solutions. The BS loss satisfies both conditions in Lemma 4.2, CE loss also satisfies these conditions if we restrict the hypothesis set such that h E H S {h h,(2)) 2 > OVi E [>]. X) (i.e., the classifier assigns minimum label probability for all values). the &g loss over bounded set also satisfies these conditions. To deal with the supremum constraint the distribution in practice, slightly limit adversary capacity and ensure p(A = 1|X, Y) 2 OVX, Y E X X
We solve Problem 7 using no-regret dynamics (Freund & Schapire (1999)), the solution is the Nash cquilibrium of a two-player zero-sum game, where one player, the adversary, iteratively proposes partition distributions p (A|[,, Y), the modeler then responds near optimally with model h, and incurs loss R (h). Based on the history of losses, the adversary iteratively refines its proposed partition function into the worst-case partition.
solve the above problem with parameter e > O, we leverage the theoretical results presented in Chen et al. (2017) for improper robust optimization of infinite loss sets with oracles. We first present the results in terms to {x,, 34 V game. In each round f, the modeler produces classifier and the adversary proposes an empirical distribution of x( Y), denoted a' { af E le, 1], Σg a p. where p is the minimum partition size. The empirical risk (cost) of round is L' L(h a²), with
finite dataset with n samples; assume that both players have access P(X, 8)8", and let t E {O...., T) indicate the current round of the zero
L(h, a)
(8)
np
In order to find the Nash equilibrium of this game, we use projected gradient descent on the ad- versary, while the modeler uses approximate best response with Bayesian oracle ht (aa). In particular, we use a variant proposed in Chen et al. (2017) for robust non-convex optimization. Algorithm shows the proposed approach.
Algorithm Blind Pareto Fairness
Require: Inputs: Dataset ((x, y))) minimum partition size P
Require: Hyper-parameters: Number of rounds T, parameter 7), adversary boundary coefficient < >> 0, 1-approximate Bayesian solver M(-) = arg min L(h,-)
Initialize a = å = {p) Initialize classifier and loss
no = (()), L = L(h,.a) (
for round t 1, .., T do
Adversary updates its partition function by gradient descent and projec-
tion:
a' t- a-1l + L. 6) a- +
E(h',v .v) ap
x
II(a')
C. =i Solver provides a model that approximately solves for the current partition:
h M(a) end for
return No-regret classifier 1,T
The proposed Algorithm in instantiation of Algorithm 3 in (Chen et al. (2017)) for oracle efficient improper robust optimization with infinite loss sets. To implement the projection operator II()) we use Dykstra's projection algorithm (Boyle & Dykstra (1986)), using the fact 1.3.

---

Under review as a conference paper at ICLR 2021
that the set can be seen as the intersection of the [e, 1] hypercube and the (a, 1) = np plane, where both of these sets have known and exact projection functions individually. We can then immediately leverage their results (Theorem 7 in Chen et al. (2017)) to show that the algorithm converges (proof presented in the Supplementary Material).
Lemma 4.3. Consider the setting of Algorithm 1, with parameter e. > and " (zp. and L a I-Lipschitz function w.r.t. a, let P be a uniform aEfarauele.ll... ==pp V2T S VV2"
||ll|
max
distribution over the of models {h! ...., ,,"), and let R be the minimax solution to the loss presented in Eq. 8. Then we have
[m-p((h, S SRR + 2np T
max
As in Chen et al. (2017), we use h² instead of the ensemble descent (SGD) as our 7-approximate Bayesian oracle, We note that the 1-Lipschitz constraint can be relaxed to any G-Lipschitz function by working through the no regrets guarantees for projected gradient descent of G-Lipschitz functions in the proof provided in Chen et al. (2017).
h." We use stochastic gradient
Figure 2 shows how group risks evolve across game rounds, results are shown for several minimum partition size values. We observe that cross-entropy (CE) on the worst group gradually converges to value that depends on p. the rounds trade performance between low and high risk groups
Worst Group
Best Group
20
50 Game
60
60
100
Game
Figure Risk trade-off between low and high group risks & Graff (2017) dataset as a function of game rounds. Left figure indicates worst group cross-entropy, right corresponds to low risk groups Traces are shown for several P values. Small values make the risk of the worst group converge that of the random classifier, as expected from Lemma 3.2, larger values show more stratified behaviour. We observe how performance between worst and best groups traded off between game rounds.
BPF algorithm over the UCI adult Dua
5 EXPERIMENTAL RESULTS
We experimentally validate our methods and theoretical results on a variety of standard datasets, we compare performance against DRO (Hashimoto al. (2018)), ARL (Lahoti et (2020)), and baseline (naive) classifier. We show the trade-offs of each method remaining population. The baseline method is, as expected, the one that performs best on the low- risk population, but it suffers from large, fat tails in terms of loss distribution. We also show how both DRO and BPF empirically achieve the theoretical results laid in Lemma 3.2, with BPF having better results on the low-risk population than DRO, owing to the Parcto optimality constraint.
their worst group and the
Datasets. We used four standard fairness datasets for comparison. The UCI Adult dataset (Dua & Graff (2017)) which contains 48, 000 records of individual's 's annual income as well as 13 other attributes, including race, gender, relationship status, and education level. The target task is income prediction (binary, indicating above below 50K). The Law School dataset (Wightman (1998)) contains law school admission data used to predict successful bar exam candidates based on various factors including family income, race, and gender. The COMPAS dataset (Barenstein (2019)) which contains the criminal history, serving time, and demographic information such as sex, age, and race of convicted criminals. The goal is prediction of recidivism per individual." Lastly used the
This dataset is the source of extensive and very legitimate controversy in the faimess community, and is here used for benchmarking only.

---

Under review as a conference paper at ICLR 2021
MIMIC-III dataset, which consists of clinical records collected from adult ICU patients at the Beth Israel Deaconess Medical Center Johnson et al. (2016). The objective is predicting patient mortality from clinical notes. We analyze clinical notes acquired during the first 48 hours of ICU admission following the pre-processing methodology in Chen al. (2018), ICU stays under 48 hours and discharge notes are excluded from the analysis. Ti-idf statistics on the 10, 000 most frequent words in clinical notes are taken input features.
UCI Adult
Law school
Compas
MIMIC-III
UCI Adult
Law school
Compas
MIMIC-III
Figure 3: Cross-entropy (CE) and accuracy (Acc) metrics on best and worst groups as a function of group size for BPF, DRO, ARL, and baseline classifiers, random classifier shown for reference. Results are provided for UCI adult, law school, COMPAS, and MIMIC-III datasets. Cross-entropy of both ARL and baseline classifiers for the worst group are very large for small group size, DRO and BPF both approximate the theoretical result shown in Lemma 3.2. The main difference between DRO and the proposed BPF is that BPF exhibits better results on the best group partition than DRO for the same level of worst group performance, owing to the Pareto restriction on the BPF classifier resulting in no- sameecsssary-harte for any group (see also right panel of Figure I). Accuracy results largely mimic the observations the cross-entropy metric.
Setup and Results. We train BPF for minimum group sizes p = (0.15,0.20.... 0.5), we report cross-entropy loss and accuracy, on the worst partition of the dataset (i.e., average over the worst 100 * p% samples based on cross-entropy loss), the values for the remaining low risk group is also reported (to evaluate optimality). DRO models were trained on 20 equispaced values of their threshold parameter (1) E [0, 1)). For ARL, we use the code provided in (Lahoti et al. (2020)): since it lacks tuning hyper-parameter, besides the original setup, we tried four configurations for their adversarial network (adversary with 1 to 4 hidden layers of 512 units each). The classifier architecture for BPF, ARL, and DRO was standardized to 4-yyrr MLP with 512 hidden units. In all cases we use cross-entropy loss and same input data. Results correspond to the best hyper-parameter for each group size; mean and standard deviations are computed using 5-fold cross-validation.
Figure 3 shows the performance of the best and worst groups across partition sizes. Both DRO and BPF recover results close the random classifier for the smaller group sizes, which aligns with the results shown in Lemma 3.2, that is, below a certain partition size (e.g.. ~ 0.3 for adult dataset) the average cross-entropy of the worst group the risk of the uniform classifier (log 2). We observe that, in general, BPF obtains better results for the low risk group than DRO for the same worst group risk. ARL slightly reduces the worst group risk compared to the baseline classifier, but in general not able to reduce worst-case risk significantly.
Although none of the compared models address disparities along predefined populations, in some cases they are nonetheless able to improve the worst group performance on the set. Consider the Adult dataset, an unbalanced problem (NV 23.6% of the samples present an income higher than 50k) where sample accuracy may be a misleading statistic (c.g., bascline classificr achieves > 81% accuracy across male and female populations). Table shows accuracy conditioned on both gender and income, and on race and income for each competing method. We observe that both BPF and DRO achieve results close to the uniform classifier for small partition sizes as expected, and no predefined group larger than their partition size gets a masse-than-randoon cases, the results for BPF is better than DRO for each protected attribute (at same p value). We also observe that on several minorities, the BPF model provides the best utility values out of all the competing methods, BPF is also the best model at preserving worst group performance.
performance. In many
'Accuracy is computed on the randomized classifier Y ~ -(X).

---

Under review as a conference paper at ICLR 2021
Table shows how target labels and predefined sensitive groups are represented in the high risk group identified by BPF. We observe that, for low partition sizes, outcomes balanced across groups (in concordance with Lemma 3.2). As the partition size increases, the composition of the
high risk group becomes
similar to the base distribution. Similar results to tables and are
provided in Supplementary Material A.3 for law school, COMPAS and MIMIC-III datasets.
Group
Prop (%)
baseline
ARL.
DRO. .15
BPF .15
DRO .4
BPF .4
DRO 5
BFF
Race/Income (1 250k, Of <50k)
Male/O
46.7
82.7+:0.1
81.3-0.3
51.2.+0.9
50,7
68.44:166
70.2=2.1
74.0==16
78:9:004
Male/1
20.0
59.3++0.9
59.400.5
50.6=0.3
51.1#122
$4.2+00.8
57.5=133
55.3#112
58.8+00.11
Female/0
93.5+-0.2
76.8+:
84.9
90.2::066
Pemule/1
3.6
50.8.12.2
50.0.10.5
50.6.10.3
51.6.1.3
50.5.11.1
52.5
$0.1.114
52.2.1.00
Eihmseity/Incooe (1 2,00, ou <50))
Whitol0
64.2
86.2::022
85.240.22
51.4111
$2.74:2.1
70.7+:1.7
68.32244
17.11:
82.5::0.5
White/1
21.4
58
$8.6:1:1
5844004
50.6:0.33
51.1#:23
53.910088
17.0=
$4,9112
58.1=:0.1
Black/0
8.5
91.9004
51.02.
7822117
85.6.199
Black/1
1.1
52:2:1:.00
51.9110
50.620.3
508842
514419
53.2-114
51.7424
54.0::77
Asian-PacI00
2.1
86.5+077
83811111
51.0=0.7
50.64:1
713428
68.1-211
7154322
80.94077
Astan-Pact/1
0.8
59.3:::1.5
60.2+-2.0
50.8:004
52.342
52.442
62.2-2.1
53.243300
58.941999
Otber/O
1.5
93.3.102
93.2..044
$1.7.113
508811
77.6119
73.9
85.5.12.
89.5.11.5
Other/1
0.3
4144221
39412.7
50.520.3
51.4125
44.922.
46.7
42.5134
4..61111
Table 1: Accuracy across gender and ethnicity partitions (groups given special consideration by the algo- rithms) in Adult dataset for ARI., DRO and BPF models varying partition sizes.
Table 2: Demographic composition of
Group
Prop(()
BPF .15
BPF 33
BPF .4
BPF .5
worst groups function of minimum partition size on the Adult dataset. BPF homogenizes outcomes across parti- tions and protected attributes. For
Proportion Worst Partition, Elbmicity/nnceme
White/O
64,2
41.8:10.9
44.810.4
48.9=0.1
53.5.100
White/1
21.4
47.31:00
44 44.960.6
41.0=0.0
35.61:0.1
Black/0
2.7=0.2
30::::00
3.4::0.0
4.620.0
Black/1
1.1
2.9-0.1
2.5++0.0
2.2+-0.0
1.8+0.0
larger group sizes, the demographics of
Asian-PacIiO
2.1
18--0.1
1.7.1.22
19400.
the partition approach of the base-
Asian-PacI/I
0.8
2.000.0
18:100
16:000
14400.0
line population.
Othen/O
1.5
0,4:0.0
04::00
0.5:0:00
0.100.0
Other/1
0.3
1.0:0.0
0.8:1:000
0.6:1:0.9
0.5
6 DISCUSSION
In this work we analyze subgroup robustness, particularly the context of fairness without demo- graphics labels. Our goal is to recover model that minimizes the risk of the worst-case partition of the input data subject to a minimum size constraint, while we additionally constrain this model to be Pareto efficient w.r.t. the low-risk population well. This means that worst unknown subgroup without causing unnecessary harm on the rest of the data. We show that it is possible only the size of the smallest one, and that there is a minimum partition size under which the random classifier is the only minimax option for cross-entropy and Brier score losses.
optimizing for the
protect high risk groups without explicit knowledge of their number structure,
We propose BPF, an algorithm that provably converges to the Pareto minimax solution. Our results variety of standard fairness datasets show that this approach reduces worst-case risk as expected, and produces better models than competing methods for the low-risk population, thereby avoiding unnecessary harm.
If a policymaker has a desired risk tradeoff instead of a target group size, we can search for the smallest partition size achieving this tradeoff using the proposed BPF; this now guarantees that the recovered model can satisfy this risk tradeoff for the worst possible partition up to size and for any smaller partition size there exists partition such that this tradeoff violated.
Future work includes incorporating additional domain-specific constraints on the worst partition and developing an algorithm that combines BPF with knowledge about some subgroups that must be protected as well.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Matias Barenstein. Propublica's compas data revisited. arXiv preprint arXiv: 047711 2019.
Solon Barocas and Andrew D Selbst. Big data's disparate impact. Calif. Rev., 104:671, 2016. 2016.
Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and Machine Learning. fairml- book.org, 2019. http:///wwir fww.wwwwwiaaa..a...o............ maabookooo org..
Dimitris Bertsimas, Vivek F Farias, and Nikolaos Trichakis. The price of fairness. Operations Research, 59(1):17-31, 2011.
James Boyle and Richard L Dykstra. A method for finding projections onto the intersection of convex sets in hilbert spaces. In Advances in order restricted statistical inference, pp. 28-47. Springer, 1986.
Irene Chen, Fredrik D Johansson, and David Sontag. Why is my classifier discriminatory? In Advances in Neural Information Processing Systems, pp. 3539-3550, 2018.
Jiahao Chen, Nathan Kallus, Xiaojie Mao, Geoffry Svacha, and Madeleine Udell. Fairness under unawareness: Assessing disparity when protected class is unobserved. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pp. 339-348, 2019.
Robert S Chen, Brendan Lucier, Yaron Singer, and Vasilis Syrgkanis. Robust optimization for non- convex objectives. In Advances in Neural Information Processing Systems, pp. 4705-4714, 2017.
Alexandra Chouldechova and Aaron Roth. The frontiers of faimess in machine learning. arXiv preprint arXiv: 1xX00:8110008810, 2018
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://///a/ctiee ics uci. edu/ml.
John Duchi, Tatsunori Hashimoto, and Hongseok Namkoong. Distributionally robust losses for latent covariate mixtures. arXiv preprint arXiv:2007. /3982, 2020.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd Innovations in Theoretical Computer Science Con- ference, pp. 214-226, 2012.
Marc N Elliott, Allen Fremont, Peter A Morrison, Philip Pantoja, and Nicole Lurie. A new method for estimating race/ethnicity and associated disparities where administrative records lack self- reported race/ethnicity. Health Services Research, 43(5p1): 2008
Yoav Freund and Robert E Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1-2):79-103, 1999.
Arthur M Geoffrion. Proper efficiency and the theory of vector maximization. Journal of Mathe- matical Analysis and Applications, 22(3):618-63)) 1968.
Maya Gupta, Andrew Cotter, Mahdi Milani Fard, and Serena Wang. Proxy fairness. arXiv preprint 2018
Sara Hajian, Francesco Bonchi, and Carlos Castillo. Algorithmic bias: From discrinination dis- covery to faimess-aware data mining. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 2125-2126, 2016.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In Advances Neural Information Processing Systems, pp. 3315-3323, 2016.
Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang. Fairness without demographies in repeated loss minimization. arXiv preprint arXiv:1806.08000 080000 2018.
Ursula Hébert Johnssn, Michael P Kim, Omer Reingold, and Guy N Rothblum. Calibration for the cammuutationall-idennfnna masses, arXiv preprint 1rXiv:1711.0888 2017.

---

Under review as a conference paper at ICLR 2021
Kenneth Holstein, Jennifer Wortman Vaughan, Hal Daumé II, Miro Dudik, and Hanna Wallach. Improving fairness machine learning systems: What do industry practitioners need? In Pro- ceedings of the 2019 CHI Conference on Human Factors in Computing Systems, pp. 1-16, 2019.
Alistair EW Johnson, Tom J Pollard, Lu Shen, H Lehman Li-wei, Mengling Feng, Mohammad Ghassemi, Benjamin Moody, Peter Szolovits, Leo Anthony Ccli, and Roger G Mark. Mimic-iii, a freely accessible critical care database. Scientific data, 3:160035, 2016.
Nathan Kallus, Xiaojie Mao, and Angela Zhou. Assessing algorithmic faimess with unobserved protected class using data combination. arXiv preprint arXiv: 1906. 002.00 2019.
Louis Kaplow and Steven Shavell. The conflict between notions fairness and the Pareto principle. American Law and Economics Review, 1(1):63-77, 1999.
Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing fairness gerryman- dering: Auditing and learning for subgroup fairness. In International Conference on Machine Learning, pp. 2564-2572 2018.
Preethi Lahoti, Alex Beutel, Jilin Chen, Kang Lee, Flavien Prost, Nithum Thain, Xuezhi Wang, and Ed H Chi. Fairness without demographics through adversarially reweighted learning, arXiv preprint arXiv:2006. 13114, 2020.
Natalia Martinez, Martin Bertran, and Guillermo Sapiro. Minimax Pareto fairness: A multi objective perspective. In International Conference on Machine Learning. 2020.
Andreu Mas-Colell, Michael Dennis Whinston, Jerry R Green, et al. Microeconomic Theory, vol- ume Oxford University Press New York, 1995.
Shira Mitchell, Eric Potash, Solon Barocas, Alexander D' D'Amour, and Kristian Lum. Prediction-
based decisions and fairness: A catalogue of choices, assumptions, and definitions. arXiv preprint arXiv:1811.07866 2018
John Rawls. Justice as Fairness: A Restatement. Harvard University Press, 2001.
John Rawls. A Theory of Justice. Harvard University Press, 2009.
Nimit Sohoni, Jared Dunnmon, Geiffrey Angus, Albert Gu, and Chris Re. Addressing hidden stratification: Fine-grained robustness coarse- searse-grained classification problems, 2020a. http: / //hazyresearchh stanforde www.nnfwr...ddd.ioooooo stat fication, July2020.
Nimit S. Sohoni, Jared A. Dunnmon, Geoffrey Angus, Albert Gu, and Christopher Ré. No sub- class left behind: Fine-grained robustness in coarsc-grained classification problems. To Appear in Neural Information Processing Systems, 2020b. http: http://saaoforrr www.:ooddddddd/eedeeeeeeeeeeeeee edd//niisssseeeeeeeeeee.ediii -nima/o Saaoclass_left_eelee
pdf.
Berk Ustun, Yang Liu, and David Parkes. Fairness without harm: Decoupled classifiers with prefer-
ence guarantees. In International Conference Machine Learning, pp. 6373-6382, 2019.
Michael Veale and Reuben Binns. Fairer machine learning the real world: Mitigating discrimina- tion without collecting sensitive data. Big Data & Society, 44),205995711744333, 2017.
Linda F. Wightman. LSAC National Longitudinal Bar Passage Study. LSAC Research Report Series. 1998.
Yan Zhang. Assessing fair lending risks using race/ethnicity proxies. Management Science, 64(1): 178-197, 2018.


Reviews:
[{"review_id": "jl9JKpJoh-m", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary ##\n\nThis paper considers the relevant problem of group fairness in ML when there are no predefined groups. They aim to provide an algorithm that outputs a classifier that minimizes the risk of any group (of sufficient size) while at the same time being Pareto efficient. They do this by first showing that this problem is equivalent to the case when there are only two groups and then using no-regret dynamics to provide an algorithm which asymptotically converges to the optimal solution.\n\nThey also show empirically, using multiple datasets, that their algorithm is marginally better than the state of the art in terms of fairness and in some cases, efficiency.\n\n\n## Strengths ##\nThis is clearly a very relevant problem since (as they mention) in a lot of cases, we may not have the group labels for each point in the dataset. Furthermore, being robust to any subgroup allows for the algorithm to be fair to groups who have not yet been declared as protected groups.\n\nThe algorithm asymptotically converges to the optimal solution. This algorithm not only minimizes the risk of the worst case group but also does not do any unnecessary harm to other groups while ensuring fairness.\nThe experimental section is very comprehensive and compares their algorithm to the state of the art using multiple datasets. It shows that in almost all of them, their algorithm does marginally better than the state of the art. This section also gives us an idea about the trade-off between efficiency and fairness.\nWeaknesses:\n\n* The improvement over the current state of the art in this problem (DRO) is very marginal and in some cases (the Compas Dataset), DRO does slightly better than BPF.\n* There is no discussion about the result in Lemma 3.3. It is unclear whether this bound is reasonable or whether the loss in efficiency is significant.\n* Lastly, in a lot of cases, the accuracy of groups which are not the worst-off group is significantly worse than that of the baseline while the accuracy of the worst off group is only marginally better than that of the baseline. While it is clear that this loss in accuracy is necessary to improve the accuracy of the worst off group, there is very little discussion on why this tradeoff is worth it, or whether there exists another way to address this trade-off. \n\n## Typos ##\n* Unnecessary Parenthesis around Utsun et al (2019) (Introduction)\n* $Y$ should be $\\mathcal Y$ (Section 3.1, Line 6)\n* $\\Delta^{|Y| - 1}$ should be $\\Delta^{|Y|}$ (Section 3.1)\n* $p(A = a) \\ge \\rho$ should be $p(A = 1) \\ge \\rho$ (Proof of Lemma 3.1, Line 6)\n* There is a typo in the equation $P(Y|A = 0, X) = \\dots$ (Proof of Lemma 3.2)\n* $a^*$ is not defined (Proof of Lemma 3.3)\n\n## Other structural feedback ##\nThe classes of hypothesis functions that can be used is unclear throughout. It would help to discuss it for the readers who have not read Martinez et al (2020)\n\n## After Rebuttal ##\n\nI thank the authors for their clarifications and efforts to improve their work. I still support acceptance.", "extra_scores": {}, "extra_text": {}}, {"review_id": "VXWWlGm45rD", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### POST-REVISION\nThanks for revising your algorithm and clarifying its theoretical properties.\n\nI think the changes made to the algorithm do seem substantial: you've changed a complicated combination of multiplicative and best response updates on alpha to a simpler projected gradient update  (I am assuming that the experimental results have also been revised accordingly). The description is now easier to follow and the convergence results now follow directly from Chen et al.\n\nI'm raising my score to 6, but still find the novelty in the formulation to be somewhat limited.\n\nOne pending concern is that the algorithm maintains one parameter \\alpha_i per training example, which can be prohibitively expensive for large datasets. Of course, one way to alleviate this difficulty would be to replace \\alpha_i with a parameterized function of the features, which however, would make your formulation very similar to Lahoti et al. (2020).\n\nIs there a way you could measure the violation in the pareto constraint in your experiments, to showcase how the classifiers learned by your method are different from those learned by the approach of Lahoti et al?\n******\n\nThe authors seek to learn a classifier which is a pareto-efficient and achieves the min-max risk across different subgroups. They are particularly interested in a setting where neither the group memberships nor the number of groups is known a priori. Prior work by Martinez et al. (2020) propose an approach for learning min-max pareto fair classifier when the group identities are known beforehand. This paper's proposal is to formulate a min-max optimization problem: like Martinez et al. the minimization is over the space of pareto-efficient classifiers, whereas the maximization is over all (soft) partitions of the data into two groups. \n\nThe authors show that the solution to this problem degenerates into a trivial classifier when the size of the smallest group is below a certain threshold. They then propose an algorithm inspired from Chen at al. (NeurIPS 2017) to solve the min-max problem.\n\nI like the problem formulation and find the problem setup to be practically relevant (given that there's an increasing emphasis in the fairness community on addressing scenarios where the protected group information is noisy or unknown).\n\nHowever, I'm unable to verify correctness of algorithm and guarantee\n- The authors say they adapt Algorithm 3 from Chen at al., but I find the proposed algorithm to be different from the one in Chen et al. Unfortunately, the textual description doesn't delve into any of these differences. I am also unable to see how the no-regret guarantee the authors provide in Lemma 4.1 follows from results in Chen et al. They provide a one line proof stating \"Immediate application of Theorem 11 in Chen et al. (2017)\" but I don't see how Theorem 11 directly applies to the specific problem setup the authors consider.\n\nBelow, I elaborate the discrepancy I see with Chen et al.\n\nAlgorithm 3 in Chen et al., which the authors adapt, consider the following setup: there's an objective L(x, w) which is possibly non-convex in \"x\" and is convex in \"w\", and the goal is to minimize L over x and maximize it over w. They assume access to an oracle that can minimize L(., w) over \"x\" for a fixed \"w\", and provide an algorithm which performs gradient ascent updates on \"w\" and performs full optimization over \"x\" using the oracle. They show convergence guarantees for this algorithm.\n\nThe min-max problem considered in the present paper also has two sets of parameters \"alpha\" and classifiers \"h\". The objective is non-convex in alpha (see eq. 6), and convex w.r.t. \"h\" (Sec 3.1). So the natural analogue of the algorithm of Chen et al. for this setup, would be to perform full optimization over alpha (which the authors do), and to perform (projected) gradient updates on \"h\". However, instead what the authors use for \"h\" is some form of a multiplicative weights update, which I find confusing. What you have is a multiplicative update again on alpha, and an invocation of another algorithm by Martinez et al.  to learn a pareto-efficient classifier. Was the idea to perform a multiplicative update on \"h\" and project it back to the space of pareto-efficient classifiers? \n\nI agree that like gradient ascent, multiplicative weights (MW) also enjoys no-regret guarantees but to apply MW, won't you need to maintain an explicit weight for each classifier \"h\"? Instead, why is the MW update applied again to the alpha's?\n\nAt the very least, I think authors need to elaborate on how exactly they apply the algorithm from Chen et al. The current discussion is light on the details.", "extra_scores": {}, "extra_text": {}}, {"review_id": "PmUtZQI4EnM", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary: \nThe authors analyze the space of solutions for worst case fairness beyond demographics, and propose Blind Pareto Fairness (BPF), a method that leverages no-regret dynamics (i.e., Multiplicative Weight Update) to recover a fair minimax classifier that reduces worst-case risk of any potential subgroup of sufficient size (learnt over worst-case partitions, such that the smallest size/density is at least a minimum), and guarantees that the remaining population receives the best possible level of service. They show promising experimental results over three data sets: UCI dataset on Adult Income, Law School dataset, and Compas Dataset. \n\n\n##########################################################################\n\nReasons for score: \nThe idea for establishing performance for unknown groups is interesting, simply because the set of protected attributes (e.g., nationality, race, genetic information) is evolving with time. In this regard, I find the premise of the paper interesting. To obtain a minimax classifier, the authors deploy a multiplicative weight update based method, which is somewhat standard.  Their setting is a bit incremental compared to multiple recent papers on minimax Pareto fairness guarantees, and not motivated beyond unknown groups (see cons). I therefore support (weak) acceptance of this work since they move away from \"given groups\" and show an improvement in the experiments for the worst-off group. \n\n##########################################################################\n\nPros: \n\nBPF addresses fairness beyond demographics, that is, it does not rely on predefined\nnotions of at-risk groups, neither at train nor at test time. \n\nExperimental results show that the proposed framework improves worst-case risk in multiple standard datasets, while simultaneously providing better levels of service for the remaining\npopulation, in comparison to competing methods. \n\n\n##########################################################################\n\nCons: \n\nComparisons from related work are weak. For example, the authors claim that \"In our work\nwe consider subgroups based not only on all input features but also on outcome, which broadens the\nscope to all conceivable subgroups based on the information available to the model.\" in comparison to Martinez et. al, which already considers minimax pareto fairness, for instance. Why are subgroups based on outcomes relevant? Why would it make sense in any application to consider based on outcomes. \n\nIn comparison to Duchi et. al 2020, and Hashimoto et a. 2018, the authors say that \"can be sub-optimal on the population segment that lies below their high-risk threshold (doing unnecessary harm)\", however one can imagine that in some applications these high risk samples are in fact more important than the low risk ones. For which applications do the authors argue that distribution independent results are more useful, compared to these recent distributionally robust results? \n\n##########################################################################\n\nQuestions during rebuttal period: \n\n \nPlease address and clarify the cons above \n\n \n#########################################################################\n\nTypos: \n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of Pareto fairness without having pre-defined protected groups. The reviewers agree that the problem studied here is interesting and relevant. During the initial review period, reviewers identified a major correctness issue. The authors have then substantially changed the algorithm and experiments in the rebuttal period in order to address the issues. Now the convergence result in the paper follows more directly from the prior work of Chen et al. Overall, the technical novelty of the paper appears to be limited. Even though the authors have also strengthened the related work discussion, they should also consider discussing the comparison between their work with that of Lahoti et al., as suggested by one of the reviewers. 

Decision: Reject