Year: 2019

Abstract:
Common fairness definitions in machine learning focus on balancing various notions of disparity and utility. In this work we study fairness in the context of risk disparity among sub-populations. We introduce the framework of Pareto-optimal fairness, where the goal of reducing risk disparity gaps is secondary only to the principle of not doing unnecessary harm, a concept that is especially applicable to high-stakes domains such as healthcare. We provide analysis and methodology to obtain maximally-fair no-unnecessary-harm classifiers on finite datasets. We argue that even in domains where fairness at cost is required, no-unnecesary-harm fairness can prove to be the optimal first step. This same methodology can also be applied to any unbalanced classification task, where we want to dynamically equalize the misclassification risks across outcomes without degrading overall performance any more than strictly necessary. We test the proposed methodology on real case-studies of predicting income, ICU patient mortality, classifying skin lesions from images, and assessing credit risk, demonstrating how the proposed framework compares favorably to other traditional approaches.

heading: 1 INTRODUCTION
text: Machine learning algorithms play an important role in decision making in society. When these algorithms are used to make high-impact decisions such as hiring, credit-lending, predicting mortality for intensive care unit patients, or classifying benign/malign skin lesions, it is paramount to guarantee that these decisions are both accurate and unbiased with respect to sensitive attributes such as gender or ethnicity. A model that is trained naively may not have these properties by default; see, for example Barocas & Selbst (2016).
In these critical applications, it is desirable to impose some fairness criteria. Much of the fairness in machine learning literature attempts to produce algorithms that satisfy Demographic Parity, which aims to make algorithm’s predictions independent of the sensitive populations (Louizos et al. (2015); Zemel et al. (2013); Feldman et al. (2015)); or Equality of Odds or Equality of Opportunity, which aims to produce predictions that are independent of the sensitive attributes given the ground truth (Hardt et al. (2016); Woodworth et al. (2017)). Notions of Individual Fairness have also been advanced (Dwork et al. (2012); Joseph et al. (2016); Zemel et al. (2013)). These notions of fairness can be appropriate in many scenarios, but in domains where quality of service is paramount, such as healthcare, we argue that it is necessary to strive for models that are as close to fair as possible without introducing any unnecessary harm to any subgroup (Ustun et al. (2019)). Even if the overall fairness goal is a potentially harmful, zero-gap classifier, pursuing first a Pareto-fair classifier and later applying other harmful methodologies ensures that all possible non-harmful trade-offs are covered before explicitly degrading performance, therefore minimal harm is introduced to the decision.
In this work we make use of the concept of Pareto optimality to measure and analyze discrimination (unfairness) in terms of the difference in predictive risks across sub-populations defined by our sensitive attributes, a fairness metric that has been explored in other recent works such as Calders & Verwer (2010); Dwork et al. (2012); Feldman et al. (2015); Chen et al. (2018); Ustun et al. (2019). We examine the subset of models from our hypothesis class that have the best trade-offs between sub-population risks, and select from this set the one with the smallest risk disparity gap. This is in direct contrast to common post-hoc correction methods like the ones proposed in Hardt et al. (2016); Woodworth et al. (2017), where noise is potentially added to the decisions of the best performing sub-population. While this latter type of approach diminishes the risk-disparity gap, it does so by degrading performance on advantaged groups, the previously disadvantaged groups do not directly benefit from this treatment. Since our proposed methodology does not require test-time
access to sensitive attributes, and can be applied to any standard classification or regression task, it can also be used to reduce risk disparity between outcomes, acting as an adaptive risk equalization loss compatible with unbalanced classification scenarios.
Main Contributions. We formalize the notion of no-harm risk fairness1 using Pareto optimality (Mas-Colell et al. (1995)), a state of resource allocations from which it is impossible to reallocate without making one subgroup worse. We show that finding a Pareto-fair classifier is equivalent to finding a model in our hypothesis class that belongs to the Pareto front (the set of all Pareto optimal allocations) with respect to the sub-population risks with the smallest possible risk disparity. This general notion is already amenable to non-binary sensitive attributes. We analyze the fairness performance trade-offs that can be expected from different approaches with an illustrative example. We provide a concrete algorithm that promotes fair solutions belonging to the Pareto front; this algorithm can be applied to any standard classifier or regression task that can be trained using (Stochastic) Gradient Descent. We show that if the goal is to obtain a zero-gap classifier, first recovering the fairest Pareto optimal solution and then adding harmful post-hoc corrections ensures the lowest risk levels across all subgroups. We demonstrate how our methodology performs on synthetic and real tasks such as inferring income status in the Adult dataset Dua & Graff (2017a) irrespective of their ethnicity or gender, predicting ICU mortality rates in the MIMIC-III dataset from hospital notes Johnson et al. (2016), classifying skin lesions in the HAM10000 dataset Tschandl et al. (2018), and assessing credit risk on the German Credit dataset Dua & Graff (2017b).

heading: 2 RELATED WORK
text: There is an extensive body of work on fairness in machine learning. Following Friedler et al. (2019), we compare our methodology against the works of Feldman et al. (2015); Kamishima et al. (2012); Zafar et al. (2017). Our method shares conceptual similarities with Zafar et al. (2017); Woodworth et al. (2017); Agarwal et al. (2018), with differences on how we define our fairness objective and adapt it to work with standard neural networks. Although optimality is often discussed in the fairness literature, it is usually in the context of utility-discrimination tradeoffs. To the best of our knowledge, this is the first work to discuss optimality with respect to subgroup risks on a unified classifier, a distinction that disallows extreme performance degradation in the pursuit of fairness.
The work presented in Hashimoto et al. (2018) discusses decoupled classifiers as a way of minimizing group-risk disparity, but simultaneously cautions against this methodology when presented with insufficiently large datasets. The works of Chen et al. (2018); Ustun et al. (2019) also empirically report the disadvantages of decoupled classifiers as a way to mitigate risk disparity. Here we argue for the use of a single classifier because it allows transfer learning between diverse sub-populations. We do not need access to the sensitive attribute during test time, but in cases where this is possible, we instead choose to incorporate it as part of our observation features.
The work of Chen et al. (2018) uses the unified bias-variance decomposition advanced in Domingos (2000) to identify that noise levels across different sub-populations may differ, making perfect fairness parity impossible without explicitly degrading performance on one subclass. Their methodology attempts to bridge the disparity gap by collecting additional samples from high-risk sub-populations. Here we modify our classifier loss to bridge the disparity gap without inducing unnecessary harm, which could prove to be synergistic with their methodology.

heading: 3 PROBLEM STATEMENT
text: Consider we have access to a datasetD = {(xi, yi, ai)}ni=1 containing n independent triplet samples drawn from a joint distribution (xi, yi, ai) ∼ P (X,Y,A) where xi ∈ X are our input features (e.g., images, tabular data, etc.), yi ∈ Y is our target variable, and ai ∈ A indicates group membership or sensitive status (e.g., ethnicity, gender); our input features X may or may not explicitly contain A.
Let h ∈ H be a classifier from a compact hypothesis class H trained to infer y from x, h : X → Y; and a loss function ` : Y ×Y → R. We define the class-specific risk of classifier h on subgroup a as Ra(h) = EX,Y |A=a[`(h(X), Y )]. The risk discrimination gap between two subgroups a, a′ ∈ A is
1In this paper we use “no-harm” to mean “no-unnecessary-harm,” in other words, the system doesn’t degrade performance on any class unless it is strictly necessary to improve performance in a disadvantaged class.
measured as Γa,a′(h) = |Ra(h)−Ra′(h)|, and we define the pairwise discrimination gap vector as ~ΓA(h) = {Γa,a′(h)}a,a′∈A. Our goal is to obtain a classifier h ∈ H that minimizes this gap without causing unnecessary harm to any particular group in A. To formalize this notion, we define: Definition 3.1. Dominant risk vector: A vector r′ ∈ Rk is said to dominate r ∈ Rk, noted as r r′, if ri ≥ r′i,∀i = 1, ..., k and ∃j : rj > r′j (i.e., strict inequality on at least one component). Definition 3.2. Dominant risk classifier: Classifier h′ is said to dominate h, noted as h h′, if the risks vector r′ = {Ra(h′)}|A|a=1 dominates r = {Ra(h)} |A| a=1. Definition 3.3. Pareto front: We define the Pareto front as P(H,A) = {h ∈ H : @h′ ∈ H | h h′}. This means that there is no other classifier in H that is at least as good in all risks and strictly better in at least one of them. It is the set of classifiers such that improving one group’s risk comes at the cost of increasing other’s.
The Pareto front defines the best achievable trade-offs between population risks Ra(h). This definition is already suited for classification and regression tasks where the sensitive attributes are categorical. Constraining the classifier to be in the Pareto front disallows laziness, there exists no other classifier in the hypothesis classH that is at least as good on all class-specific risks and strictly better in one of them. As shown in Chen et al. (2018); Domingos (2000), the risk can be decomposed in bias, variance and noise for some loss functions, where the noise is the smallest achievable risk for infinitely large datasets (Bayes-optimal risk). If the noise differs between sensitive groups, zero-discrimination (perfect fairness) can only be achieved by introducing bias or variance.
Literature on fairness has focused on putting constraints on the norm of discrimination gaps (Zafar et al. (2017; 2015); Creager et al. (2019); Woodworth et al. (2017)). We follow a similar criteria in Definition 3.4 and define the Pareto-fair classifier as the classifier in the Pareto front that minimizes ||~ΓA(h)||∞ (the maximum risk discrimination gap). Note that one could alternatively choose to find the Pareto classifier that minimizes the maximum subgroup risk. Definition 3.4. Pareto-fair classifier and Pareto-fair vector: A classifier h∗ is an optimal Paretofair classifier if it minimizes the discrimination gap among all Pareto front classifiers, h∗ = arg min h∈P(H,A) ||~ΓA(h)||∞. The Pareto-fair vector r∗ ∈ R|A| is defined as r∗ = {Ra(h∗)}a∈A.
Even when perfect equality of risk is desirable, Pareto classifiers still serve as useful intermediaries. To this end, Lemma 3.1, shows that applying a mechanism for reaching equality of risk on a dominated classifier h ∈ H leads to equal or worse risks than applying it to a Pareto classifier hp ∈ P(H,A) that dominates h. Lemma 3.1. If h 6∈ P(H,A)→ ∃hp ∈ P(H,A) : hp h ∧ Ra(hERp ) ≤ Ra(hER)∀a, with hER an equal-risk classifier : Ra(hER) = max
a′∈A Ra′ (h),∀a and hERp : Ra(hERp ) = max a′∈A Ra′ (hp).
To exemplify these notions graphically, Figure 1 shows a scenario with binary sensitive attributes a and binary output variable y where none of the Pareto front classifiers achieve equality of risk. Here the noise level differs between subgroups, and the Pareto-fair vector r∗ is not achieved by either a Naive classifier (minimizes expected global risk), or a classifier where subgroups are re-sampled to appear with equal probability (rebalanced Naive classifier). Note that the amount of performance degradation required to enforce perfect fairness starting from the Naive classifier is higher than when starting from the Pareto-fair vector.
Our objective is to find the Pareto-fair classifier h∗ as in Definition 3.4. In particular, we will give regularity conditions on the hypothesis class H and the loss function `(h(X), Y ). It can be shown that for a sufficiently rich class of hypothesis functions H and for risk functions Ra(h) that are convex with respect to h, the space of risk vectors is convex (see Geoffrion (1968); Koski (1985); Miettinen (2012)). Under these conditions, we can find an auxiliary loss function φ : R|A| → R defined in terms of the subgroup risks {Ra(h)}a∈A (denoted from here on as r ∈ R|A|) that has a global minima on r∗.
To prove the existence of loss function φ with the desired global minimum r∗, it is convenient to think of the convex set of risk vectors as the intersection of a convex Pareto set (defined by a convex Pareto front and all risks that are dominated by it), and an additional convex set Ω. We further require both this Pareto set and Ω to be smooth, so that we can apply standard tools from smooth convex optimization and prove that for every risk vector r′ in the Pareto front there exists a function φ that has r′ as its global optima. This is formalized in Lemma 3.3. Definition 3.5. Pareto field: A function P : Ω → R is a Pareto field over a convex set Ω ⊂ Rk if P ∈ C1 is a continuously differentiable function such that∇iP (r) > 0 ∀r ∈ Ω,∀i = 1, . . . , k.
Lemma 3.2. Let Ω ⊂ Rk be a convex set, and P : Ω → R a Pareto field. Then the set D = {r ∈ Ω : P (r) = 0} is a Pareto set in Ω, and the set D+ = {r ∈ Ω : P (r) > 0} is the set of dominated points, i.e., D+ = {r ∈ Ω : ∃r′ ∈ D | r r′} Lemma 3.3. Let Ω ⊂ Rk be a convex set defined by Ω = {r ∈ Rk : gc(r) ≥ 0 ∀ c ∈ {1, . . . , C}, gc continuously differentiable}; let P : Ω → R be a convex Pareto field with corresponding proper Pareto set D = {r ∈ Ω : P (r) = 0}. Let r̂ ∈ D and φ(r,µ) =∑k i=1 ri + µi(ri − c)+2, with c < r̂, where we denote (x)+2 = max2(x, 0). There exists a set of vectors µ̂ 0 such that: r̂ = arg min
r∈Rk φ(r, µ̂) s.t. : P (r) ≥ 0, gc(r) ≥ 0∀c ∈ {1, . . . , C}.
Where C is the number of constraints that characterized Ω. Proofs for all lemmas are given in the supplementary material, Section A.1. Lemma 3.3 motivates our loss function to take the form φ(r,µ) = ∑|A| i=1 ri+µi(ri−c)+2, with |A| the number of sensitive groups. The challenge is to find µ∗ such that our Pareto-fair vector r∗ minimizes φ(r,µ∗). In Section 4 we provide an algorithm to approximately recover the Pareto-fair classifier h∗ by adaptively searching for µ∗ and optimizing a classifier on φ(·,µ) using tools from standard Stochastic Gradient Descent.

heading: 4 OPTIMIZATION METHODS
text: Recall that we wish to recover the Pareto-fair classifier h∗ within our hypothesis class. From Lemma 3.3, there exists a loss function of the form
φ(r;µ, c) = |A|∑ i=1 ri + µi(ri − c)+2,
φ(h;µ, c) = ∑ a∈A Ra(h) + µa(Ra(h)− c)+2, (1)
such that h∗ = arg min h∈H φ(h;µ, c). Note that we can state the loss function directly on the risk vectors r, or implicitly on the classifier h. Since Ra(h) is differentiable with respect to h, φ(h;µ, c) can be directly minimized using gradient descent on h for any choice of values µ, c. Let DTr =
{x, y, a}NTi=1, DVal = {x, y, a} NV i=1 be our training and validation datasets respectively. The proposed implementation of the Pareto-fair framework is formalized in Algorithm 1 where we specify how to update the penalty coefficients ~µ, c.
Algorithm 1: ParetoFairOptimization Given: hθ, `,DTr,DVal, nµ, np, nmax, γ > 0, k ≥ 1, ξ, ζ ∈ (0, 1), lr,B µ← 1, µ∗ ← 1, µcount ← 0, ecount ← 0, c← 0, Γ∗ ←∞, h∗ ← hθ while ecount ≤ nmax and µcount ≤ nµ do
µcount ← µcount + 1, ecount ← ecount + 1 hθ, r
Val ← AdaptiveOptimize(hθ, `,µ, c,DTr,DVal, np, lr,B) // Optimize current loss // Check that solution is Pareto efficient and reduces fairness gap
if ||~ΓA(h)||∞ < Γ∗ and rVal is not dominated by previous validation risks then h∗ ← hθ, Γ∗ ← ||~ΓA(h)||∞, cold ← c, c← mina r Val a k
µ∗ ← µ · (r Val−cold)+ (rVal−c)+ , a ′ ← arg maxa rVala , µcount ← 0
else lr← ζ lr, µ← µ∗, γ ← γξ, hθ ← h∗ end µa′ ← (1 + γ)µa′
end // Exit loop due to excessive iterations or no improvement in fairness Return: h∗
We regularly check that reductions in the fairness gap generalize to the validation set; we additionally check if the trade-offs are in the non-dominated solution set (i.e., we have not observed a universally better classifier during training). Algorithm 2 (AdaptiveOptimize, shown in Section A.2) summarizes how we perform stochastic gradient descent steps with early stopping in-between µ, c updates. Lemma A.5 (shown in supplementary material, Section A.1) shows that this algorithm is convergent for |A| = 2 when the minimization step for a fixed µ, c is performed exactly. To conclude this section, we stress that the proposed framework is independent of the desired algorithm class H and loss function `; these are kept from the original application. The Pareto-fair classifier uses the same inputs as the Naive classifier, with parameters that have been optimized towards Pareto fairness. Code will be made available.

heading: 5 EXPERIMENTS AND RESULTS
text: We applied the methodology described in Section 4 to learn a Pareto-fair classifier (classifier in the group-risk Pareto front with the smallest risk disparity). We first validate our methodology on synthetic data with known Pareto-fair classifiers. Observations are drawn from a Gaussian mixture model where each sensitive attribute is encoded by a corresponding Gaussian mode, and target attributes are binary. We demonstrate our methodology on publicly available fairness datasets, and show how the risk disparity gaps are subsequently reduced. Where applicable, we compare our results against the methodologies proposed in Zafar et al. (2017); Kamishima et al. (2012); Hardt et al. (2016); Feldman et al. (2015).

heading: 5.1 SYNTHETIC DATA
text: We tested our approach on synthetic data where the observations are drawn from conditional Gaussian distributions X|A = a ∼ N(µA, 1), the target variable y is a conditional Bernoulli variable with distribution Y |X = x,A = a ∼ Ber ( fa(x) ) with fa(x) = ρlowa 1[x ≤ ca] + ρhigha 1[x > ca] ) , and |A| = 3. We used Brier Score (BS, refer to Section A.4) as our loss function. Under these conditions, the Bayes-optimal classifier for each subgroup is h(x) = fa(x). The subgroup risk function for any classifier h can be computed as Ra(h) = EX|A=a[Y − h(X))2] = EX|A=a[fa(X)(1 − h(X))2 + (1 − fa(X))h(X)2]. Network details are given in the supplementary material, Section A.6. Figure 2 shows the analytically-derived Pareto-fair classifier, as well as the trade-off obtained by the proposed algorithm. We remark that the Pareto-fair classifier in this scenario cannot be achieved using linear logistic regression, something that can be seen from the functional form of the Bayes Optimal classifier derived in Section A.8 in supplementary material. From the center graph in Figure 2 we can see that the approximated Pareto-Fair risks (dashed
lines) are close to the theoretical best (solid lines).The achieved maximum risk discrimination is also close to the theoretical best. The algorithm is able to correctly trade risks from the two advantaged subgroups to reduce the risk of the worst performing subgroup.

heading: 5.2 REAL DATASETS
text: We evaluate the performace of our algorithm on mortality prediction (MIMIC-III), skin lesion classification (HAM10000), income prediction (Adult), and credit lending (German). We also compared with several state of the art methods (Zafar et al. (2017); Kamishima et al. (2012); Hardt et al. (2016); Feldman et al. (2015)) and with a model trained to minimize the average risk (Naive) and one that undersamples the minority class (Naive Balanced or NaiveB). A description of these methods is provided in Section A.3 of Supplementary material. Metrics used for evaluation include accuracy (Acc), confidence (Conf), expected and maximum calibration error (ECE and MCE respectively), Brier score (BS) and cross-entropy (CE). Values for every metric are reported per sensitive attribute. The dataset average is reported as (sample mean), and the group-normalized average as (group mean). The best and worst performing groups are also shown as (group max) and (group min), and the worst case difference between subgroups is reported as (disc). For an in-depth description of the the metrics and datasets used for evaluation, refer to Sections A.4 and A.5 of Supplementary material. Here we present a comparison of the performance in terms of accuracy and ECE but an extensive comparison is available in additional results Section A.7 in supplementary material.
Similarly to Chen et al. (2018); Zafar et al. (2017); Hardt et al. (2016); Woodworth et al. (2017), we omit the sensitive attribute a ∈ A from our observation features. Our method trains a single classifier for the entire dataset to avoid needing test-time access to sensitive attributes whenever possible. All classifiers shown in this section are implemented using neural networks and/or logistic regression, we used either cross-entropy or Brier score as our training loss depending on the dataset. For details on the architecture and hyperparameters used on each dataset, refer to the supplementary material, Section A.6. We show how the proposed Pareto-fair approach produces well calibrated models that reduce group disparities across several metrics.

heading: 5.2.1 PREDICTING MORTALITY IN INTENSIVE CARE PATIENTS
text: Medical decisions in general and mortality prediction in particular are examples where notions of fairness among sub-populations are of paramount importance, and where ethical considerations make no-harm fairness a very attractive paradigm. To that end, we used clinical notes collected from adult ICU patients at the Beth Israel Deaconess Medical Center (MIMIC-III dataset) Johnson et al. (2016) to predict patient mortality. We study fairness with respect to age (adult or senior), ethnicity (white or nonwhite), and outcome (alive/deceased). This leads to a total of 8 sensitive groups. We included outcome (alive/deceased) as a sensitive sub-population criteria to demonstrate a case where sensitive attributes would not be available at test-time, and because in our experiments patients who ultimately passed away on ICU were under-served by a Naive classifier. Table 1 shows empirical accuracies and expected calibration errors of all tested methodologies. It is important to note how imbalanced these groups are by looking at the ’ratio’ column. Here one can see that 56.7% of the samples correspond to the majority class (alive, white, senior) and only 0.4% to the minority
class (deceased, nonwhite, adult). Our methodology produces low discrimination classifiers with high group accuracies, for example, ParetoFair trained with brier score loss (BS) increased the classification accuracy of the most under-served group by over 50% while reducing the accuracy of the best-served group by 12% when compared to the Naive classifier.

heading: 5.2.2 SKIN LESION CLASSIFICATION
text: The HAM10000 dataset Tschandl et al. (2018) collects over 10, 000 dermatoscopic images of skin lesions over a diverse population. Lesions are classified according to diagnostic categories. We found that a Naive classifier exhibited almost no measurable discrimination based on age or race on this dataset. We instead chose to use the diagnosis class as both the target and sensitive variable, casting balanced risk minimization as a particular use-case for Pareto fairness. This is possible since our methodology does not require test-time access to sensitive labels. It was not possible to show comparisons against Hardt et al. (2016) since the sensitive attribute is perfectly predictive of the outcome. Table 3 shows accuracies and ECE for all tested methodologies. The Pareto-fair classifier has the overall best calibration results and smallest accuracy disparities across methodologies. Comparisons against other methods were not possible because the target labels are non-binary.

heading: 5.2.3 INCOME PREDICTION AND CREDIT RISK ASSESMENT
text: We tested the proposed method on the Adult UCI dataset Dua & Graff (2017a) and on the German Credit dataset Dua & Graff (2017b). In the Adult UCI dataset the goal is to predict a person’s
income, which can be an important factor on meaningful decisions such as credit lending. In the German Credit dataset the goal is predicting credit risk. We select gender and ethnicity as our sensitive attributes. To compare ourselves against state of the art methods Zafar et al. (2017); Feldman et al. (2015); Kamishima et al. (2012) we binarize the sensitive attributes into White-Male and Other when dealing with ethnicity and gender simultaneously, or Male and Female when dealing with gender, and use the unified testbed provided in Friedler et al. (2019). We limit our hypothesis class H to linear logistic regression to compare evenly against these standard baselines. Results on both datasets are shown in Table 5.

heading: 6 DISCUSSION
text: There exists a rich literature of fairness in machine learning in general, and risk-based fairness in particular. Here we explore a relatively untapped sub-problem where the goal is to reduce risk disparity gaps in the most ethical way possible (i.e., minimizing unnecessary harm). Unlike other works in the area, our problem investigates on how to reduce this disparity gap without collecting additional data samples, using the entirety of the available training data to produce an algorithm that is maximally fair with respect to sub-populations, and that does not necessarily require test-time access to sensitive attributes.
We provide a concrete algorithmic adaptation to any standard classification or regression loss to bridge this disparity gap at no unnecessary harm, and demonstrate its performance on several realworld case studies. Even for applications where the need for strict fairness outweighs the need for no-harm classifiers, this methodology can be applied before any post-hoc corrections to ensure that the risk disparity gap is closed in the most risk-efficient way for all involved sub-populations. The proposed algorithm does not sweep through different disparity constraint values, as previously done in related works, making it a simpler alternative.
As an avenue of future research, it could be of interest to analyze if we can automatically identify high-risk sub-populations as part of the learning process and attack risk disparities as they arise, rather than relying on preexisting notions of disadvantaged groups or populations. We strongly believe that no-unnecessary-harm notions of fairness are of great interest for several applications, especially so on domains such as healthcare and lending, where decisions are highly impactful.

heading: A APPENDIX

heading: A.1 PROOFS
text: Here we restate the Lemmas shown in Section 3 along with a sketch of the proofs.
Lemma 3.1 If h 6∈ P(H,A) → ∃hp h ∈ P(H,A) : Ra(hERp ) ≤ Ra(hER),∀a, where hER is a equality of risks classifier in H such that Ra(hER) = max
a′∈A Ra′ (h),∀a and hERp : Ra(hERp ) =
max a′∈A Ra′ (hp),∀a.
Proof. If hp dominates h→ Ra(hERp ) = max a′∈A Ra′ (hp) ≤ max a′∈A Ra′ (h) = Ra(h ER) ∀a ∈ A.
Definition A.1. Dominant vector: A vector r′ ∈ Rk is said to dominate r ∈ Rk, noted as r′ r, if ri ≥ r′i,∀i = 1, ..., k and ∃j : rj > r′j (i.e., strict inequality on at least one component). Definition A.2. Pareto field: A function P : Ω → R is defined as a Pareto field over a convex set Ω ⊂ Rk if P ∈ C1 is a continuously differentiable function such that ∇iP (r) > 0∀r ∈ Ω,∀i = 1, . . . , k. Lemma A.1. Let Ω ⊂ Rk be a convex set, and P : Ω → R a Pareto field. Then the set D = {r ∈ Ω : P (r) = 0} is a proper Pareto set in Ω, and the set D+ = {r ∈ Ω : P (r) > 0} is the set of dominated points, i.e., D+ = {r ∈ Ω : ∃r′ ∈ D | r r′}.
Proof. First we prove that D = {r ∈ Ω : P (r) = 0} is a Pareto set. Assume by contradiction that there exists r, r′ ∈ D | r′ r, then r′ − r = c = ∑ i δiei δi ≥ 0∀i ∈ {1, . . . , k}, ∃j ∈ {1, . . . , k} | δj > 0. ei is a standard basis vector. Using the Gradient theorem we have
P (r′) = P (r) + ∫ r→r′ ∇P (λ)dλ,
= P (r) + ∫ 1 0 〈(δ1, . . . , δk), (∇P0(r + λc), . . . ,∇Pk(r + λc))〉dλ,
= P (r) + ∑ i δi ∫ 1 0 ∇Pi(r + λc)︸ ︷︷ ︸ >0 dλ,
> P (r),
which directly contradicts r′, r ∈ D. No point in set D is dominated by another point in set D, making set D a proper Pareto set.
To show that the set D+ is the set of dominated points, we first note that for all r ∈ Ω | r′ ∈ D, r r′ we have P (r) > P (r′) using the same arguments as above, meaning that the set of dominated points is included in D+. Similarly, for all r ∈ Ω | r′ ∈ D, r′ r we have P (r′) ≥ P (r), meaning that non-dominated points are not a part of set D+.
Lemma A.2. Let Ω ⊂ R|A| be a convex set defined by Ω = {r ∈ R|A| : gc(r) ≥ 0 ∀ c ∈ {1, . . . , C}, gc continuously differentiable}; let P : Ω → R be a convex Pareto field with corresponding Pareto set D = {r ∈ Ω : P (r) = 0}. Let r∗ ∈ D and φ(r, µ) = ∑|A| i=1 ri+µi(ri− c)2+, with c < r∗. There exists a set of µ∗ 0 such that: r∗ = arg min
r∈R|A| φ(r, µ∗) s.t. : P (r) ≥ 0, gc(r) ≥ 0∀c ∈ {1, . . . , C}
.
Proof. By hypothesis, both Ω and {r ∈ Ω : P (r) ≥ 0} are convex, so the intersection is also convex. For µ 0, φ(r, µ) is a convex function of r. Under these hypothesis, the Karush-KuhnTucker (KKT) conditions are necessary and sufficient to recover a global minimizer. So it suffices to find a set µ∗ such that the KKT conditions are exactly satisfied at r∗.
Let J∗ = {j : gj(r∗) = 0} be the set of indices of active gc constraints at r∗, note that by hypothesis, r∗ ∈ D and therefore P (r∗) is always active. Focusing on the first KKT condition on the active set we get∇φ(r∗, ~µ) = λ∇P (r∗) + ∑ j∈J∗ ηj∇gj(r∗), in matrix form:1...
1
+ 2(r ∗ 1 − c)+ 0
. . . 0 2(r∗A − c)+
µ = [ | | |∇P ∇gj1 . . . ∇gj|J∗| | | | ] λ η1 ... ηc∗  . By hypothesis, we have ri − c > 0 and therefore
µi = λ∇Pi(r∗) +
∑ j∈J∗ ηj∇g j i (r ∗)− 1 2(r∗i − c) .
In particular, for ηj = 0 ∀j and µ1 > [∇Pi(r ∗)
∇P1(r∗) − 1] 1 2(r∗1−c)+ ∀i 6= 1 we get
µi = [(µ12(r ∗ 1 − c)+ + 1) ∇Pi(r∗) ∇P1(r∗) − 1] 1 2(r∗i − c)+ > 0∀i 6= j,
µ1 > 0,
λ = µ12(r ∗ 1 − c)+ + 1 ∇P1(r∗) > 0,
which satisfies the KKT conditions and produces the required minimizer r∗ for all points r∗ ∈ D.
Lemma A.3. Let Ω ⊂ R2 be a convex set defined by Ω = {r ∈ R2 : gc(r) ≥ 0 ∀ c ∈ {1, . . . , C}, gc continuously differentiable}; let P : Ω → R be a convex Pareto field with corresponding Pareto set D = {r ∈ Ω : P (r) = 0}. Let > 0, r∗ = arg min
r∈D [maxi ri − minj rj ]
then c = min(r1, r2)− < min(r∗1 , r∗2) ∀(r1, r2) ∈ D.
Proof. case r∗1 = r∗2: Assume r ∈ D : mini ri > r∗1 . Then r r∗, which contradicts the hypothesis r ∈ D. case r∗1 6= r∗2: Without loss of generality, we can take r∗1 > r∗2 . We can then prove by couterpositive that r ∈ D implies r1 > r2. Assume by contrapositive that there exists r′ ∈ D : r′2 > r′1. By hypothesis D is a continuous curve, and we can find a path R(t) : R(0) = r∗, R(1) = r′, R(t) ∈ D∀t ∈ [0, 1], which would imply there exists t̂ : R(t̂) = (r̂, r̂), in which case r∗1 = r∗2 , which contradicts r∗1 6= r∗2 . We then have that for r ∈ D, r1 > r2. Assume by counterpositive that r2 = min(r1, r2) > min(r∗1 , r ∗ 2) = r ∗ 2 then r1 < r ∗ 1 (since both r, r
∗ ∈ D), but then |r1 − r2| < |r∗1 − r∗2 | which contradicts the hypothesis.
Putting both statements together, we proved that if r∗1 > r ∗ 2 , then ∀r ∈ D,min(r1, r2) = r2 ≤ min(r∗1 , r ∗ 2) = r ∗ 2 .
Lemma A.4. Let Ω ⊂ R2 be a convex set defined by Ω = {r ∈ R2 : gc(r) ≥ 0 ∀ c ∈ {1, . . . , C}, gc continuously differentiable}; let P : Ω → R be a convex Pareto field with corresponding Pareto set D = {r ∈ Ω : P (r) = 0}. Let µ = (µ1, µ2) > 0, µ′ = (µ1, µ′2); µ′2 > µ2. Define φ(r, µ, c) = ∑2 i=1 ri + µi(ri − c)2+ and
r = arg min s. t.P (r)≥0
r∈Ω
φ(r, µ, c),
r′ = arg min s. t.P (r)≥0
r∈Ω
φ(r, µ′, c).
With c < r2, then, r′1 ≥ r1, r′2 ≤ r2, with equality if and only if r′ = r̂ = arg min s. t. r∈{P (r)≥0}∩Ω r2
Proof. By hypothesis, we have φ(r, µ′, c) ≥ φ(r′, µ′, c)
φ(r, µ, c) + (µ′2 − µ2)(r2 − c)2+ ≥ φ(r′, µ, c) + (µ′2 − µ2)(r′2 − c)2+
φ(r, µ, c) ≥ φ(r′, µ, c) + (µ′2 − µ2)[(r′2 − c)2+ − (r2 − c)2+] since by hypothesis φ(r, µ, c) ≤ φ(r′, µ, c), it follows r′2 ≤ r2, and therefore r′1 ≥ r1, because they both belong to the Pareto set.
Case r′ = r. To analyze when the equality arises, note that the tangent to D at r is τ(r) = (∇2P (r),−∇1P (r)) and that r + δτ(r), δ > 0 is a valid search direction if r 6= r̂ (r does not minimize r2). Also note that∇φ(r, µ′, c) = ∇φ(r, µ, c) + (0, 2(µ′2 − µ2)(r2 − c)+) By contradiction, assume r 6= r̂, then r + δτ(r), δ > 0 is a valid search direction and 〈(δτ(r)),∇φ(r, µ′, c〉 > 0, which implies r′ 6= arg min
s. t.P (r)≥0 r∈Ω
φ(r, µ′, c) and contradicts the hypoth-
esis.
Therefore, if r′ = r it follows r′ = r = r̂
Lemma A.5. Let Ω ⊂ R|A| be a convex set defined by Ω = {r ∈ R|A| : gc(r) ≥ 0 ∀ c ∈ {1, . . . , C}, gc continuously differentiable}; let P : Ω → R be a convex Pareto field with corresponding Pareto set D = {r ∈ Ω : P (r) = 0}. Let r∗ = arg min
r∈D (maxi ri − minj rj) and φ(r, µ, c) = ∑|A| i=1 ri + µi(ri − c)2+. Let µ0 > 0 be an initial penalty vector, r0 = arg min
r∈D
∑ i ri,
> 0, c0 = mini r0i − ,γ > 0, ξ ∈ (0, 1). Define the following auxiliary variables ck+1 = min
i rki −
Γk = max i rki −min i rki a† = arg max a (rka)
µ† a† = (γ + 1)µka†
µ†\a† = µ k \a†
r† = arg min s. t.P (r)≥0
r∈Ω
φ(r, µ†, ck+1)
c† = min i r†i − Γ† = max i r†i −min j r†j
(2)
We define the following iteration procedure compute Eq 2
If Γk = Γ†
terminate
While Γ† > Γk
γ ← ξγ Recompute Eq 2
End While
µk+1 = µ† · (r † − ck)+
(r† − c†)+
rk+1 = r†
The procedure is convergent to r∗ for |A| = 2.
Proof. From Lemma A.3 we have ck < mini r∗i ∀k, we can then apply Lemma A.2 and state that there exists a set µ∗k such that r∗ = arg min
s. t.P (r)≥0 r∈Ω
φ(r, µ∗k, ck).
We split the proof in two scenarios, one where Γ∗ = 0 and then Γ∗ > 0, since they show different convergence properties.
case Γ∗ = 0. Assume without loss of generality that rk1 = arg maxi rki , from Lemma A.4 we have µk1 < µ k∗ 1 , and further, for all µ † 1 ∈ (µk1 , µk∗1 ), we have rk1 < r † 1 < r ∗ 1 . Since |A| = 2 and rk, r†, r∗ all belong to D, we also have rk2 > r † 2 > r ∗ 2 , which implies Γ
k > Γ† > Γ∗ = 0. The subiteration procedure is always successful, and we get a sequence of iterates such that Γk > Γk+1, a strictly decreasing sequence bounded below by 0, which implies asymptotic convergence to r∗. Procedure never terminates with probability 1 (event µk ∈ µ∗k has probability 0). case Γ∗ > 0 Assume without loss of generality that r∗1 < r∗2 . Following the arguments from Lemma A.3 we observe that r1 < r2 ∀(r1, r2) ∈ D. In these conditions, we have that µ k 2
µk1 < µk+12 µk+11 and
ck+1 > ck. We will re-derive the KKT conditions in this scenario to show that convergence is guaranteed for µk2 > µ2∗, and that this µ2∗ is independent of ck, meaning that convergence to the optimal r∗ can be achieved in a finite number of steps.
Let ∇P (r∗) = (dP1, dP2) > 0, with corresponding tangent vector τ∗ = (dP2,−dP1), for r∗ to be the risk with minimal gap, r∗ + δτ∗ must be an infeasible descent direction for δ > 0. Therefore, there is an active constraint from Ω, g(r), with ∇g(r∗) = (dg1, dg2) such that 〈(dg1, dg2), (dP2,−dP1)〉 < 0. Deriving the first KKT conditions, we get
1 + µ12(r ∗ 1 − c) = λdP1 + ηdg1, 1 + µ22(r ∗ 2 − c) = λdP2 + ηdg2,
and in terms of λ, η
λ = 1 + µ12(r ∗ 1 − c)− ηdg1 dP1 ,
η = dP1(1 + µ22(r ∗ 2 − c)− dP2(1 + µ12(r∗1 − c)) dg2dP1 − dP2dg1 .
Note that dg2dP1 − dP2dg1 > 0 from 〈(dg1, dg2), (dP2,−dP1)〉 < 0. To recover a valid set of Lagrange multipliers η, λ > 0 , it suffices to have
dP1(1 + µ22(r ∗ 2 − c)) > dP2(1 + µ12(r∗1 − c)),
µ2 > (1 + µ12(r
∗ 1 − c))dP2dP1 − 1
2(r∗2 − c) ,
µ2 > (1 + µ12(r
∗ 1 − c0))dP2dP1 − 1
2 ,
where we used that c0 < ck < ∀k. Therefore, for µ k 2
µk1 large enough, rk = r∗ and the algorithm
terminates.

heading: A.2 ALGORITHMIC DETAILS
text: Here we provide details on how we optimize our adaptive loss in-between penalty update (µa) steps, shown in Algorithm 2.

heading: A.3 METHODS
text: We compare the performance of the following methods:
Algorithm 2: AdaptiveOptimize Given: hθ, L, ~µ, c,DTr,DVal, np, lr,B p← 0, φ∗ ←∞ h∗ ← hθ while p ≤ np // Making loss progress do
for {(xi, yi, ai}Bi=1 ∈ DTr // Run one epoch of SGD on training set do
Ia = {i ∈ {1, . . . , B} ∧ ai = a}, R̄Ba(hθ) = 1|Ia| ∑ i∈Ia L(hθ(xi), yi) // Empirical risks
φB(hθ) = ∑ a∈A R̄ B a(hθ) + µa(R̄ B a(hθ)− c)+2
θ ← θ − lr∇θφB(hθ) // Gradient step end if φVal(hθ) < φ∗ // Evaluate improvement on Val and update target risks then
h∗ ← hθ; φ∗ ← φVal(hθ); p← 0 else
p← p+ 1; end RVal ← R̄Val(h)
end Return: h∗, RVal
Kamishima. Kamishima et al. (2012) uses logistic regression as a baseline classifier, and requires numerical input (observations), and binary sensitive attribute and target variable. Fairness is controlled via a regularization term with a tuning parameter η that controls trade-off between fairness and overall accuracy. η is optimized via grid search with η ∈ (0, 300) as in the original paper. We report results on the hyperparameter configuration that produces the smallest accuracy disparity between sensitive subgroups.
Feldman. Feldman et al. (2015) provides a preprocessing algorithm to sanitize input observations. It modifies each input attribute so that the marginal distribution of each coordinate is independent on the sensitive attribute. The degree to which these marginal distributions match is controlled by a λ parameter between 0 and 1. It can handle numerical and categorical observations, as well as non-binary sensitive attributes, and arbitrary target variables. Following Friedler et al. (2019), we train a linear logistic regressor on top of the sanitized attributes. λ is optimized via grid search with increments of 0.05. We report results on the hyperparameter configuration that produces the smallest accuracy disparity between sensitive subgroups.
Zafar. Zafar et al. (2017) Addresses disparate mistreatment via a convex relaxation. Specifically, in the implementation provided in Friedler et al. (2019), they train a logistic regression classifier with a fairness constraint that minimizes the covariance between the sensitive attribute and the classifier decision boundary. This algorithm can handle categorical sensitive attributes and binary target variables, and numerical observations. The maximum admissible covariance is handled by a hyperparameter c, tuned by logarithmic gridsearch with values between 0.001 and 1. We report results on the hyperparameter configuration that produces the smallest accuracy disparity between sensitive subgroups.
Hardt. Hardt et al. (2016) proposes a post-processing algorithm that takes in an arbitrary predictor and the sensitive attribute as input, and produces a new, fair predictor that satisfies equalized odds. This algorithm can handle binary target variables, an arbitrary number of sensitive attributes, and any baseline predictor, but requires test-time access to sensitive attributes. it does not contain any tuning parameter. We apply this method on top of both the Naive Classifier and our Pareto Fair classifier.
Naive Classifier (Naive). Standard classifier, trained to minimize an expected risk h = arg min h∈H EX,A,Y [L(h(X), Y )]. The baseline classifier class H is implemented as a neural network and varies by experiment as described in Section A.6, the loss function also varies by experiment and is also described in Section A.6. Optimization is done via stochastic gradient descent.
Naive Balanced (NaiveB). Baseline classifier designed to address undersampling of minority classes, trained to mimimize a class-rebalanced expected risk h = arg min h∈H EA∼U [1,...,|A|],(X,Y )∼P (X,Y |A)[L(h(X), Y )]. Like the Naive classifier, it is implemented as a neural network and optimized via stochastic gradient descent. The sole difference with the Naive classifier is that, during training, training samples are drawn from the new input distribution A ∼ U [1, . . . , |A|]; X,Y |A ∼ P (X,Y |A), which is achieved by re-weighted sampling of the original training dataset.
Pareto Fair. Our proposed methodology, trained to minimize an adaptive loss function using the procedure described in Algorithm 1. Addresses risk disparity minimization without introducing unnecessary harm to any subgroup. The baseline classifier class H is implemented as a neural network and varies by experiment as described in Section A.6, the loss function also varies by experiment and is also described in Section A.6.

heading: A.4 EVALUATION METRICS
text: Here we describe the metrics used to evaluate the performance of all tested methods. We are given a set of test samples Dt = {(xi, yi)}Ni=1 where xi ∈ X is a realization of our model input and yi ∈ Y the corresponding objective. We assume that Y is a finite alphabet, as in a classification problem, and we will represent the one-hot encoding of yi as ~ei. Given a trained model h : X → [0, 1]|Y| the predicted output for a an input xi is a vector h(xi) = ~pi such that (~pi)j ∈ [0, 1],∀j ∈ {1, ..., |Y|} and | ∑|Y| j=1(~pi)j = 1 (e.g.: output of a softmax layer). The predicted class is ŷi = arg maxj(~pi)j and its associated confidence is p̂i = maxj(~pi)j . Ideally ŷi should be the same as yi. Using these definitions, we compute the following metrics.
Accuracy (AC): 1N ∑N i=1 1(yi = ŷi). Fraction of correct classifications in dataset.
Confidence (CO): 1N ∑N i=1 p̂i. Average magnitude of the predicted class probability.
Brier Score (BS): 1N ∑N i=1 ||~ei − ~pi||2 where ~ei is the one-hot representation of the categorical ground truth value yi. This quantity is also known as Mean square error (MSE).
Cross-Entropy (CE): − 1N ∑N i=1 ∑|Y| j=1(~ei)j log(~pi)j also known as negative log-likelihood (NLL) of the multinomial distribution.
Expected Calibration Error (ECE): 1N ∑M m=1 ∣∣∑ i∈Bm [1(yi = ŷi)− p̂i] ∣∣ where M is the number of bins to divide the interval [0, 1] such that Bm = {i ∈ {1, .., N} : p̂i ∈ (m−1M , m M ]} are the group of samples that our model assigns a confidence (p̂i) in the interval (m−1M , m M ]. Measures how closely the predicted probabilities match the true base rates.
Maximum Calibration Error (MCE): maxm∈{1,...,M} ∣∣ 1 |Bm| ∑ i∈Bm [1(yi = ŷi)− p̂i] ∣∣. Measures worst-case miscalibration errors.
These metrics are computed independently for each sensitive subgroup on the test set and reported in Section A.7.

heading: A.5 EXPERIMENTS ON REAL DATA
text: The following is a description of the data and experiments for each of the real datasets. The information present here is summarized in Table 7.
MIMIC-III. This dataset consist of clinical records collected from adult ICU patients at the Beth Israel Deaconess Medical Center (MIMIC-III dataset) Johnson et al. (2016). The goal is predicting patient mortality from clinical notes. We follow the pre-processing methodology outlined in Chen et al. (2018), where we analyze clinical notes acquired during the first 48 hours of ICU admission; discharge notes where excluded, as where ICU stays under 48 hours. Tf-idf statistics on the 10, 000 most frequent words in clinical notes are taken as input features.
We identify 8 sensitive groups as the combination of age (under/over 55 years old), ethnicity as determined by the majority group (white/nonwhite) and outcome (alive/deceased). Here we will use the term adult to refer to people under 55 years old and senior otherwise. This dataset shows large sample disparities since 56.7% of corresponds to the overall majority group (alive-senior-white) and only 0.4% to the overall minority group (deceased-adult-nonwhite).
We used a fully connected neural network as described in table 8 as the baseline classifier for our proposed Pareto Fair algorithm. We compare our results against both the Naive and Naive Balanced algorithms using the same neural network architecture, and crossentropy (CE) as our training loss. We also evaluate the performance of Zafar applied on the feature embeddings learned by the Naive Balanced classifier (Results for Zafar over the original input features were not promising).
We report the performance across a 5-fold split of the data, we used a 60/20/20 train-validation-test partition as described on Table 7 and report results over the test set. We denote the overall sensitive attribute as the combination of outcome (A:alive/D:deceased), age (A:adult/S: senior) and ethnicity (W:white, NW:nonwhite) with shorthand notation of the form D/A/W to denote, for example deceased, white adult. We also note that results on both Zafar and Hardt were done over only the sensitive attributes Adult/Senior and White/Nonwhite, outcome was not considered as a sensitive attribute for both methods since Hardt requires test-time access to sensitive attributes, which would not be possible in this case, and Zafar attempts to decorrelate sensitive attributes and classification decision boundaries, which is counterproductive when the sensitive attribute includes the correct decision outcome.
HAM10000. This dataset contains over 10, 000 dermatoscopic images of skin lesions over a diverse population Tschandl et al. (2018). Lesions are classified in 7 diagnostic categories, and the goal is to learn a model capable of identifying the category from the lesion image. The dataset is highly unbalanced since 81% of the samples correspond to a melanocytic nevi lesion (nv), and 0.5% to dermatofibroma (df).
Here we chose to use the diagnosis class as both the target and sensitive variable, casting balanced risk minimization as a particular use-case for Pareto fairness.
We load a pre-trained DenseNet121 network Huang et al. (2017) and train it to classify skin lesions from dermatoscopic images using our Pareto fairness algorithm. We compared against the Naive and the Naive balanced training setup. Note that in the naive balance approach we use a batch sampler where images from each class have the same probability, this can be seen as a naive oversampling technique. Table 8 shows the details of the implementation.
We used the original train-validation-test (80/10/10) split, and report results on the test set. Notation for each group follows the original notation: Actinic keratoses and intraepithelial carcinoma / Bowen’s disease (akiec), basal cell carcinoma (bcc), benign keratosis-like lesions (bkl), dermatofibroma (df), melanoma (mel), melanocytic nevi (nv) and vascular lesions (vasc).
Adult. The Adult UCI dataset Dua & Graff (2017a) is based on the 1994 U.S. Census and contains data on 32, 561 adults. The data contains 105 binarized observations representing education status, age, ethnicity, gender, and marital status and a target variable indicating income status (binary attribute representing over or under $50, 000). Following Friedler et al. (2019), we take ethnicity and gender as our target sensitive attributes, defining two subgroups (White Males and Other). We also present results taking just the gender as sensitive attribute (Male/Female). To compare our Pareto Fair algorithm evenly against the other methods, we limit our hypothesis class to linear logistic regression.
German. The German credit dataset Dua & Graff (2017a) contains 20 observations collected across 1000 individuals, and a binary target variable assessing the individual’s credit score as good or bad. We take gender (Male/Female) as the sensitive attribute, which is not included in the data but can be inferred. As in the Adult dataset, we limit our hypothesis class to linear logistic regression to compare evenly across methodologies.

heading: A.6 NEURAL ARCHITECTURES AND PARAMETERS
text: Table 8 summarizes network architectures and loss functions for all experiments in Section 5. Note that all networks have a standard dense softmax as their final layer. The training optimizer is standard ADAM Kingma & Ba (2014), loss functions were either crossentropy (CE) or brier score (BS), also known as categorical mean square error (MSE).

heading: A.7 SUPPLEMENTARY RESULTS
text: The following tables show a quantitative performance comparisons between the various fairness methods described in Section A.3 over the datasets described in Section A.5. All metrics presented are described in Section A.4 and computed per sensitive attribute. We additionally provide results for the overall mean across the dataset (sample mean), as well as results on the group-balanced mean across groups (group mean). We use group max and group min to denote the maximum and minimum metric values attained over all sensitive groups. We denote group max - group min as Discrimination, which is the worst case difference in performance across groups. When the dataset contains multiple splits, we report both split mean and split standard deviation.

heading: A.8 ANALYSIS OF PARETO-OPTIMAL CLASSIFIERS IN THE INFINITE DATA AND MODEL CAPACITY REGIME
text: In this section we analyze the form of Pareto-optimal solutions to classification (and regression) tasks in the asymptotically ideal case where we have infinite capacity hypothesis classes, that is, our hypothesis classH contains every function mapping points from the observation space X to the classification or regression space R|Y|.
We additionally assume that the joint distributions between target variables Y and observation variables X given every sensitive attribute are known (i.e., P (Y,X|A) is known), and that the loss function L(h(x), y) is convex with respect to h(x).
Any joint loss of the form φPA({Ra(h)}) = EX,Y,A[L(h(X), Y ] = ∑ a∈A PaRa(h), (3)
produces solutions which are already in the Pareto front of {Ra(h)} for any distribution ofA ∼ PA. Since the loss function is convex with respect to h(X) and the hypothesis class is complete, it can also be shown that for any point in the Pareto front, there exists a value of PA such that that point is reached by minimizing φPA({Ra(h)}) Geoffrion (1968); Koski (1985); Miettinen (2012) We can therefore analyze the Bayes-optimal classifier hPA which minimizes the Naive risk φPA({Ra(h)}), and analytically compute the sub-population risks Ra(hPA) induced. In general, we can write
E[Y |x] = ∑ a∈A E[Y |x, a]P (a|x),
=
∑ a∈A
E[Y |x,a]P (x|a)Pa∑ a∈A P (x|a)Pa ,
hPA(X) = arg min η
E[L(η, Y )|X],
Ra(hPA) = EX,Y [L(hPA(X), Y )|A = a],
(4)
and in the particular case where target variable Y is categorical, and the classifier loss is an L2 loss against the one-hot encoding of variable Y the equations reduce to
E[Y |x] = ∑
a∈A ~P [Y |x,a]P (x|a)Pa∑ a∈A P (x|a)Pa ,
hPA(X) = E[Y |x], Ra(hPA) = EX [ ∑ y P (y|a,X) ∑ y′(h y′ PA (X)− δ[y − y′])2].
(5)

Review summaries:
This paper introduces a new kind of algorithmic fairness framework where the focus is on first finding a fair classifier that does "no harm" and then in a subsequent step potentially allow doing harm in order to achieve even fairer outcomes. Fairness is here understood as risk disparity: how different are the risks achieved by our model in the various subgroups. The risk is task-dependent and can be something like a cross-entropy loss for classification problems. The goal is to have similar risks in the subgroups that correspond to sensitive attributes.

This paper considers the notion of "no-harm" group fairness, i.e. trying to reduce the risk gap between minority and majority groups without excessive reduction in performance on the majority groups. Authors formalize the problem by defining a Pareto fair classifier, i.e. one that minimizes the risk gaps between groups and belongs to the family of Pareto classifiers containing the classifier minimizing the empirical risk. Authors suggest an optimization procedure for finding the Pareto fair classifier and demonstrate its performance on multiple datasets.