FIFA: Making Fairness More Generalizable in Classifiers Trained on Imbalanced Data
Authors: Zhun Deng
Jiayao Zhang
Linjun Zhang
Ting Ye
Yates Coley
Weijie J Su
James Zou
Venue: ICLR 2023 poster (2023)
Keywords: Fairness
Generalization

Abstract: Algorithmic fairness plays an important role in machine learning and imposing fairness constraints during learning is a common approach. However, many datasets are imbalanced in certain label classes (e.g. "healthy") and sensitive subgroups (e.g. "older patients"). Empirically, this imbalance leads to a lack of generalizability not only of classification but also of fairness properties, especially in over-parameterized models. For example, fairness-aware training may 
ensure equalized odds (EO) on the training data, but EO is far from being satisfied on new users. In this paper, we propose a theoretically-principled, yet {\bf F}lexible approach that is {\bf I}mbalance-{\bf F}airness-{\bf A}ware ({\bf FIFA}). Specifically, FIFA encourages both classification and fairness generalization and can be flexibly combined with many existing fair learning methods with logits-based losses. While our main focus is on EO, FIFA can be directly applied to achieve equalized opportunity (EqOpt); and under certain conditions, it can also be applied to other fairness notions. We demonstrate the power of FIFA by combining it with a popular fair classification algorithm, and the resulting algorithm achieves significantly better fairness generalization on several real-world datasets.

Published as a conference paper at ICLR 2023
FIFA: MAKING FAIRNESS MORE GENERALIZABLE IN CLASSIFIERS TRAINED ON IMBALANCED DATA
Zhun Deng
Jiayao Zhang
Linjum Zhang
Columbia University zd2322@col umbi edu
University of Pennsylvania zj i ayao edu
Rutgers University 1z41 1z4128stat. www.grrttr..... rutgerss....ttr.......... edd:
Ting Ye
Yates Coley
Weijie Su
University of Washington Lingyel@uw.ee
Kaiser Permanente Washington Health Research Institute
University of Pennsylvania
suw@wharton, upenn edu
& University of Washington Rebecca Co eeekkpooor
James Zou Stanford University jame s sz aesstanoorddee.. edu
ABSTRACT
Algorithmic fairness plays important role in machine learning and imposing fair- ness constraints during learning is a common approach. However, many datasets are imbalanced in certain label classes (e.g. "healthy") and sensitive subgroups (e.g. "older patients"). Empirically, this imbalance leads to a lack of general- izability not only of classification, but also of fairness properties, especially in wer-parameterizzd models. For example, fairness-aware training may ensure equal- ized odds (EO) the training data, but EO is far from being satisfied In this paper, we propose a theoretically-prneiii Oiballace-Fairnessse
users.
yet Flexible approach that is ware (FIFA). Specifically, FIFA encourages both classifica- tion and fairness generalization and can be flexibly combined with many existing fair learning methods with logits- based losses. While our main focus is on EO, FIFA can be directly applied to achieve equalized opportunity (EqOpt); and under certain conditions, it can also applied to other fairness notions. We demonstrate the power of FIFA by combining it with popular fair classification algorithm, and the resulting algorithm achieves significantly better fairness generalization on several real- world datasets.
INTRODUCTION
Machine learning systems are becoming increasingly vital in our daily lives. The growing concern that they may inad- vertently discriminate against minorities and other protected groups when identifying allocating resources has attracted numerous attention from various communities. While signif- icant efforts have been devoted in understanding and correct- ing biases in classical models such as logistic regressions and supported vector machines (SVM), see, e.g.. (Agarwal et al. 2018; Hardt et al., 2016), those derived tools are far less ef- fective modern over-parameteriizd models such as neural networks (NN). Furthermore, in large models, it is also dif- ficult for measures of fairness (such as equalized odds to be introduced shortly) to generalize, as shown in Fig. In other
Fiirnes (BX) Vinlition
Train
E Ex
000
0.1
11.9
0.3
0.4
0.5
Classéfication Error
Figure 1: Each marker corresponds suffi- ciently well-trained ResNet-10 model trained on imbalanced image classificaiinn datasel CelebA [ii al. (015)). The generalization of faimess constraints (EqualizedOdds) is substantially worse than the gencralization of classification crror.
"This work done when the author Harvard University.

---

Published as a conference paper at ICLR 2023
words, fairness- aware training (for instance. by imposing fairness constraints in training) may ensure measures of fairness on the training data, but those measures of faimess are far from being satisfied on test data. Here we find that sufficiently trained ResNet- 10 models generalize well on classification error but poorly on fairness constraints- gap in equalized odds between the test and training data is more than ten times larger than the gap for classification error between test and training.
In parallel, another outstanding challenge for generalization with real-world datasets is that they are often imbalanced across label and demographic groups (see Fig. 2 for imbalance in three commonly used datasets across various domains). This inherent nature of real-world data, greatly hinders the generalization of classifiers that are unaware of this innate imbalance, especially when the performance measure places substantial emphasis on minority classes or subgroups without sufficient samples (e.g., when considering the average classification error for each label class). Although generalizations with imbalanced data has been extensively studied and mitigation strategies are proposed (Cao et al., 2019 Mani & Zhang, 2003: He & Garcial 2009 An et al., [02T] He Ma 2013 Krawczyk| 2016), it's s unclear how well faimess properties generalize. And in this paper, we initiate the study of the open challenge: how to ensure fairness generalization of pver-parameterized models for supervised classification tasks on imbalanced datasets?
Our contributions. Inspired by recent works on regularizing the minority classes more strongly than the frequent classes by imposing class-dependent margins (Cao et al. 2019) in stan- dard supervised learning, we design theoretically-princii Flexible and Umbalance-Fairreee A ware (FIFA) approach that takes both classification error and fairness constraints violation into account when training the model. Our proposed method FIFA can be flexibly combined with many fair learning meth- ods with logits- baste losses such as the soft margin loss (Liu jet al. 2016) by encouraging larger margins for minority sub- groups While our method appears to be motivated for over- parameterized models such as neural networks, nonetheless also helps simpler models such as logistic regressions. Experiments on both large datasets using over- parameterized models as well as smaller datasets using simpler models demonstrate the effectiveness, and flexibility of our approach in ensuring a better fairness generalization while preserving good classification generalization.
0.5
Subgroup
Relative Urequecc
03
0.2
Cabdid
Dalaset
Figure 2: The sabgroups (sensitive attribute, ei- ther Ma Fema le, and label class, either -) are very imbalanced in many popular datascts across different domains.
Related work. Supervised learning with imbalanced datasets have attracted significant interest in the machine learning communities, where several methods including resampling, reweighting, and data
augmentation have been developed and deployed in practice (Mani & Zhang 2003 He & Garcial
2009; An et al. 2021). Theoretical analyses of those methods include margin- based approaches
(Li al. 2002 Kakade et al. 2008 Khan al. 2019; Cao et al. 2019). Somewhat tangentially,
an outstanding and emerging problem faced by modern models with real-world data is algorithmic fairness (Dwork et al. 2012) Coley et al. [22T]] Deng et al.) 2023), where practical algorithms are
developed for pre-processing (Feldman et al. 2015). in-processing (Zemel et al. 2013 Edwards
& Storkey| 2015| Zafar et al. Donini et al. 2018 Madras et | Martinez et al.) 20200] 2020), and post-processing (Hardt et al. 2016]] Kim et al. 2019) steps.
Lahoti et al. 20220 Deng et al. Nonetheless, there are several challenges when applying fairness algorithms in practice (Beutel et al.)
2019 Saha et al. 2020 Deng et al. 2022 Holstein et al. 2019). Specifically, as hinted in Fig. the fairness generalization guarantee, especially in over-parameterized models and large datasets, i8 not well-understood, leading to various practical concerns. We remark that although Kini et al. (2021) claims it is necessary to use multiplicative instead of additive logits adjustments, their motivating example is different from ours and they studied SVM with fixed and specified budgets for all inputs. Cotter et al. (2019) investigate the generalization of optimization with data -ata-dependent constraints, but they do not address the inherent imbalance in real datasets, and their experimental results are not implemented with large neural networks used in practice. To the best of our knowledge, this paper is the first tackling the open challenge of faimess generalization with imbalanced data.
BACKGROUND
Notation. For any l E N we use [k] to denote the set f1,2, ...,.....A.... k.) For a vector U, let v; be the i-th coordinate of v. We use to denote the indicator function. For set S, we use [SS] denote
2

---

Published as a conference paper at ICLR 2023
the cardinality of S. For two positive sequences } and } we write an (bb)) (or an 2 by), and a₁ = obb)), if cim /bb) < oc and limms-ae (Qk/b²) ) = O. respectively. We use P for probability and E for expectation, and we use IP and E for empirical probability and expectation. For the two distributions D1 and D2, we use pD1 + (1 D) for p E (0, 1) to denote the mixture distribution such that sample is drawn with probabilities and (1 -Ppp p) from D1 and D2 respectively. We use (1, Σ) to denote p-dimensional Gaussian distribution with mean μ and variance Σ.
Fairness notions. Throughout the paper, we consider datasets consisting of triplets of the form y/ (z,y,,)
where x E X' feature vector, a E A is sensitive attribute such as race and gender, and y E y is the corresponding label. The underlying random triplets corresponding to (z, y, a) is denoted as (X, A). Our goal is to learn a predictor h E H X + y where ((x)) is a prediction of the label Y of input X. In this paper, we mainly consider equalized odds (EO) (Hardt al. 2016) that has been widely used in previous literature on fairness. But our method could also be directly used to equalized opportunity (EqOpt) given that EqOpt is quite similar to EO. In addition, under certain conditions, our method could also be used to demographic parity (DP), which we will mainly discuss in the Appendix.
(). Equalized odds (EO) and Equalized opportunity (EqOpt). A predictor h satisfies equalized odds if h(X) is conditionally independent of the sensitive attribute A given Y: P(h(X) y y y, A a) = ((h(X)) y = y). If y = {0,, } and we only require (X) = 1|Y = 1, A a) P((()= -Y = 1), we say h satisfies equalized opportunity.
(ii). Demographic parity (DP). A predictor / satisfies demographic parity if lx() is statistically independent of the sensitive attribute A: P(h(X) Y = a) = P(h(X) = =Y).
THEORY-INSPIRED DERIVATION
While we will formally introduce new approach in Section 4 this section gives informal derivation, with an emphasis on insights. We design an fabbalance-firness--ee be flexibly combined with fair learning methods with logits-based losses.
approach that can
Throughout the paper, we use the lower letters, e.g. I. for realizations and capital letters, e.g. X, for random variables. Consider the supervised k-class classification problem, where model f + & provides k scores, and the label is assigned as the class label with the highest score. The corresponding predictor h(x)= = arg max; fxr;; if there are no ties. Let us use P; = P(X = i) to denote the conditional distribution when the class label is i for i E [k] and Poul to denote the balanced distribution Pus. where Idx is uniformly drawn from [K]. i.e. -i= Pi/k: /k. Peul can be viewed distribution weighting each class equally. Similarly, let us use P.,. P(X = i, A = 8) to denote the conditional distribution when Y i and A- s. The corresponding empirical distributions induced by the training data are P., Poal and Pi..- For the training dataset {(=g) Vy.ay) a,)},, let S; = {j= yj = i}. Si.a = {j Mj i, aj = a}. and the corresponding sample sizes be n. and Ni,as respectively. Although P:, Pos and Pa.s are all distributions on X, we sometimes use notations like (X.Y)- ~ P, to denote the distribution of (X, i), where X ~ P.. In classical imbalanced data analysis, the goal is to ensure a small [hals] = P.x.Y)>A.,l((X goal, we not only want to ensure a small Loal [f], we also hope to keep the fairness violation error to be as small as possible. In order to do that, we need to take the margin of subgroups divided according to sensitive attributes in each label class (so called demographic subgroups in different classes) into account.
< max f(X):). For our
Margin trade-off between classes of equalized odds. the setting of standard elassification with imbalanced training datasets such as in Cao et al. (2019); Sagawa et al. (2020), the aim is to reach small balanced test error [f). However, in a fair classification setting, our aim is not only to reach small Lealf)) but also to satisfy certain faimeess constraints at test time. Specifically, for EO, the aim is:
min Lbal /
s.t. Vy E V, A, P(h(X) - V/Y y, v, a) P(M(X)= y =)) where we recall that h(-) arg max; f(-), We remark here that in addition to the loss Lfalf), we can also consider the loss function that is balanced across all demographic subgroups in different classes, the derivation is similar and omit it here.
v),
3

---

Published as a conference paper at ICLR 2023
Recall our motivating example in Figure I should also be taken into account. Thus, our performance criterion for optimization should be:
Whether the fairesss violation error is small test time
L + aLiv,
where Lty is measure of fairesss constraints violation that we will specify later, and is a weight parameter chosen according to how much we care about the fairness constraints violation.
For simplicity, start with y (0, } and A {a1,az}. In the Appendix, will further discuss the case when there are multiple classes and multiple demographic groups. We also want to clarify here the case we study is different from by naively viewing each demographic groups as class and applying the method in Cao et al. (2019). The main difference is that our aim is to identify the class labels at test time, and we do not assume we have access to sensitive attributes at test time. As a result, the method in Cao et al. (2019) can not be directly used. Given that we mainly consider over-pel parameterized models, we assume the training data is well-separated that all the training samples are perfectly classified and fairness constraints are perfectly satisfied. The setting has been considered in (Cao et al.) 2019) and can be satisfied if the model class is rich, for instance, for over per-parameterized models such neural networks. We also want to emphasize even though our theory derived method assumes well-separation, our method can be applied to not well-separated datasets, please refer to the Section 6 for more details. If all the training samples are classified perfectly by h, not only
F ((x,))-A.
(X) + Y) = 0 is satisfied, we also have that IP ((.Y))-P.., (h(X) * Y) = 0 for all i, A a) = 1- (x (h(X) + Y).
i Y and a, E A. We remark here that ((h(X) Y
Our performance criterion for optimization in (A.4) is:
Mj = [f] + a Σ [P()(X) 1EY
i = i, A a1) - P()(X) +|Y = i, = a=)l
By using classical margin theory bounds, We can establish the connection between margins for each demographic subgroups and the generalization performance in classification as well as fairness constraint, as proved in Theorem
3.1 Denote the margin for class i by 7/6 = minjes, (zz.81).
where (xx y) = f(x)(,, y max ] J. One natural way to choose Liv is to take Σiey [P(h(X)=
Y i, A a1) P(h(X)= Y = A a=))l.
Theorem 3.1 (Informal) With high probability over the randomness of the training data, for y = 10, A = {a1,a2) (2), and for some proper complexity measure of class F, iee. C(F) (see more details in the Appendix), for any f FF
C(F)
2a
C(F) Ri,a
C(F) n4
2a
C(F)
MIfl S KEY
n2
Tia
Ri,a
VEY,EAA
KEY
KEY,EAA
where T is the margin of the i-th class's sample set St and Va is the margin of demographic subgroup's 's sample set Sta.
Optimizing the upper bound in 2 with respect to margins in the sense that g(70.7) S g(70 8, 21 + 8) for g(10. 7) Eiey minni + 2a EiEV. ponis and all 8 [-71, 70]. we obtain
% //1 1/4 1/4 ///4////4
where the adjusted sample size nū (II.EARL, EneA ynunc,a) for i E {0, 1). From Theo- we see how sample sizes of each subgroups are taken into account and how they affect the optimal ratio between class margins. Based on this theorem, we will propose our theoretical framework in Section 4 A closely related derivation has been used in Cao et al. (2019). but their focus is only on the classification eгтor and its generalization. As we will show in Example 3.1 when fairness constraints are also considered, their methods could sometimes perform poorly with respect to the generalization of those constraints. We remark here that if we do not consider the fairness constraints violation, then 0, and the effective sample sizes degenerate to n. 74.
rem 3.1
For illustration, we demonstrate the advantage of applying our approach to select margins over directly using the margin selection in Cao al. 2019) by considering Gaussian models, which is
4

---

Published as a conference paper at ICLR 2023
widely used in machine learning theory (Schmidt al. 2018 Zhang al. 2021 Deng et al. 2021). Specifically, our training data follow distribution: X|Y
Ei=1 Np D), X|Y
1 Ei= No,u,N + 3", : I). Here, in class j. subgroup a; is drawn with probability Ja then, given the sample is from subgroup a; in class j, the data is distributed
Gaussian random vector. Recall the corresponding training dataset indices of subgroup a, in class j is denoted as SJ,,, and No,a: T0,02- and the following class of classifiers:
153.al Rjaa.- Consider the case a
F [1 x>>a c} : c R). which is linear classifier class that contains classifiers differ from each other by a translation in a particular direction.
Example 3.1 Given function f and set S, ler (f = ming. llf(x) - s112. Consider two clas- sifiers f. E F such that dist(f. So)/ (fst(ff,. S1) // 1/4 and dist(f' / dist (f', Po 1-1// /n Suppose |1,3*11 > Vplogn, || < C. (14 -mt) = 0. and T1,az S La. for a sufficiently small ci then when no, ni are sufficiently large, with high probability we have M[f] [M[]]. Here Lials]]
(P)s(X); {P((())) [(X)alY 1] }P(S(X)o < I(X))
denotes the balanced mis-classification error.
Remark. We provide analyses for the 0-1 loss as our ultimate goal is to strike a balance between good test accuracy and small fairness constraints violation. If we surrogates such as the nettmax-cross-entree
loss for the ()-1 loss in training, our theoretical analyses still stand since we always adjust margins based on the 0-1 loss as our interests are in quantities such as test accuracy. We provide analyses and experiments for DP in the Appendix.
4 FLEXIBLE COMBINATION WITH LOGITS-BASHE LOSSES
For ease of exposition, we focus soiely on the EO constraint hereafter and discuss other constraints in the Appendix. Inspired by the margin trade- off characterized in Section we propose our FIFA approach for Flexible Imbalance- Faeee-Faainissaeeeeeeee ware classification that can easily combined with different types of logits-based losses, and further incorporated into any existing fairness algorithms such as those discussed in Section [5] Recall Yi,a is the margin for demographic subgroups in Theorem 3.1 and it could be written as Ya = % + 6ū.a and òi,a 2 (since % min Yi ). also Fig. 3 illustration), hence the middle term of Eq. 33) can be further upper bounded by the last term in Eq. 2 The final upper bound in Eq. ( is indeed sufficient for obtaining the margin trade-off between classes Nonetheless, if we want to further enforce margins for each demographic subgroup in each class, we need to use the refined bound.
Cimns
Figure 3: Illustration of 6,.a and the margin classifie:: 61 set to be non negative and 61,02 set to zero as subgroup (1, az) is closer the decision boundary than (I, a.).
Specifically, in Section 3 we have identified a way to select 7/0711. based on which we propose to enforce margins for each demographic subgroup's training set Si,a of the form
%aa = C/f 1/4
81.a.
(3)
where δū, and C are all non-negative tuning parameters. In light of the trade-off between the class margins 70/71 n 1/4 1/4 we can set of the form C/n Given "/a 2 7/t natural choice for margins for subgroups is Eq. (3)
/no
How to select ō Knowing the form of margins from the preceding discussions, an outstanding question remains: how to select &,,a for imbalanced datasets? Let ) = {0, 1} and A {ai, d2 }. within each class i, we identify St, with the largest cardinality |St.al and set the corresponding d', O. The remaining δi, are tuned as a non-negative parameter. As a further illustration, without loss of generality, assume for all [Sh.a,l 2 |S Thus selected (ōr,)i,a ensures the upper bound in the middle of Eq. (2) is tighter in the sense that for any ō > 0,
Σ KEY
1
1
X KEY
1
+ (n + +)) T2
+ ma.ai
In the Appendix, we will present how to choose ó 's when there are multiple demographic groups Briefly speaking, results similar to the above inequality are proved by application of the
5

---

Published as a conference paper at ICLR 2023
rearrangement inequality. Simple as it is, the high-level view is meaningful the decision boundaries of a fair predictor should be farther away from the less- ees--freqeent subgroup than the more- freeufttt subgroup to ensure better fairesss generalization.
Flexible imbalance- imbalance-fairnessseeee aairness-wware (FIFA) approach. We will demonstrate how to apply the above motivations design better margin losses. Loosely speaking, consider logits-based loss
(( y); f) (()()) (()))))))))))
which is non-increasing with respect to its first coordinate we fix the second coordinate. Such losses include (i). 0-1 loss: {z)x), < max [z))). (īi). Hinge loss: max m (max)e)" f(xx):
(z) 0}. (iii). Softmax-cross-entnon loss: - log ( /(eftrr + Eity e.()).)
Our flexible mubbllance-faireess--nn margin of the form in Eq. (3) Specifically, we use the following loss function during training
(FIFA) approach modifies the above losses by enforeing
EFIRA (z., 1) {([(r) y,a (J11))
where Ai,- = C/f./ + 8/.a- We remark here (FFFa((, (z. y, a): f) used only during training phase, where we allow access to sensitive attribute a. In the test time, we only need to use ʃ but not a.
5 EXAMPLE: COMBINING FIFA WITH REDUCTIONS-BASER FAIR ALGORITTMS
In this section, we demonstrate the power of our approach by combining with a popu- lar reduction based fair classification algorithm (Agarwal et al.) (018) as an example. In Sec- tion [6] we show that incorporating our ap- proach can bring a significant gain in terms of both combined loss and fairness generalization comparing with directly applying their method in vanilla models trained with softmax-cross- entropy losses. The reduction approach pro- posed in Agarwal et al. (20T8) has two versions: (i). Exponentiated gradient (ExpGrad) that produces randomized classifier; and (ii). Grid search (GridS) that produces deterministic classifier. Our approach can be combined with both. From high level point, the above two methods are mainly based on putting the fairness constraint as a penalty along with the objective loss function then perform a min-max optimization. The only difference is that the first algorithm ExpGrad aims to produce randomized classifier and GridS aims to produce a deterministic classifier. To incorporate our framework with the two algorithms above, only need to slightly modify the error function by adding margin related term.
Algorithm 1 FIFA Combined Grid Search
Input: Training data set (2i, yc: Yim.. faimess toler- ance 6, margins { (Ag.a hwa classifier ((-;0).
Output: the learnt classifier h"
I: Load training data to GridS.
2: GridS produces a set of reduction-labels Amin and
a set of sample weights Waain based the type of fairness constraint and tolerance c.
3: for tort= = 1.2...., T do
4: Compute the FIFA loss ÉEFA via 4 using
reduction-labels tunin (in mini-batches).
5: Updatc in h using back-propagation.
6: Logging training metrics using true labels
{ur yi=1 and attributes {a.)
7: end for
Exponentiated gradient (ExpGrad). We first briefly describe the algorithm here. For y = {0, 1}. by Agarwal et al. (2018), EO constraints could rewritten as Mu(h) S e for certain M and e, where (1) = E (x) E,) for j E J. M E | and c RR Here, K. -C=AA A y x {+.-} (+. impose positive/negative sign so
recover |.] in constraints) and
(AU (x) (((()) *
{A a, Y = y) and E(..)) (Y y). Let crr(h) instead of considering minseH err(h) such that Ma S c, ExpGrad obtains the best randomized classifier, by sampling a classifier h E from a distribution over H. Formally, this optimization can be formulated as mingEAn err(Q) such that Mu()) I c, where cQr(Q) = Ene (hh). u())= = EnER (h)) Q is a distribution over H. and Á is the collection of distributions on H. Let us further use (Q) and (i( to denote the empirical versions and also allows relaxation on constraints by using = + e, where & = Ck c for relaxation EK 2 0. By classic optimization
10. E(o.0)
theory, it could be transferred to a saddle point problem, and Agarwal et al. (2018) aims to solve the
following prime dual problems simultaneously for L(Q,A) eri () + (M)(Q) é):
(
min
max L(Q,A), (D)
max A J
min QEA
I(Q.
QEA KKR KE S1
To summarize, ExpGrad takes training data (1,, Vi, a, function class H. constraint parame- ters M, bound B, accuracy tolerance u > 0, and learning rate v as inputs and outputs (Q, Å), such

---

Published as a conference paper at ICLR 2023
that 1(Q,A) S L(Q. ~ for all Q AH and 2) S L(Q,A)- all X E R
| S B,
and (Q. A) is called a v-approximate saddle point. As implemented in Agarwal et al. 2018). H
roughly consists of h(x) = 1[f(z) 2 f(z)o for f E F (in fact, a smoothed version is considered
in Agarwal et al. 2018 ) and gives
enr(Q) = Σ
P(M()) + ()Q()) = P(((X) < ((x)).1x))))()) MCR
To combine our approach, consider optimizing eTT (Q) EnEN P(f()((())))) AY, S (o.)x))))) such that Ma (Q) I è, where (Q)((Q) ZNEH Q()) (f) and (f) = (()(X)y - AY,A > (o.nvv E2). We can modify ExpGrad to optimize prime dual problems simultaneously for
= err new (Q) + + +TTTTMMM (M - ê). In practice, while Section is is motivated for deterministic classifiers, FIFA works for the randomized version too- the modified ExpGrad can be viewed as encouraging distribution Q that puts more weights on classifiers with a certain type of margin trade-off between classes. Moreover, the modified algorithm enjoys similar convergence guarantee as the original one.
err
Theorem 5.1 Let = max, [| fite (f) - alooo For 11 = u/ B), the modified ExpGrad will return a v-approximate saddle point of nne in at most 4p² B² log( + 1)/v² iterations.
Grid search (GridS). When the number of constraints is small, e.g., when there are only few sensitive attributes, one may directly perform a grid search on the À vectors identify the deterministic classifier that attains the best trade-off between accuracy and fairness. In practice. GridS is preferred for larger models due its memory efficiency, since ExpGrad needs to store all intermediate models to compute the randomized classifier at prediction time, which is less feasible for over-parandn parameterized models. We describe our flexible approach in Algorithm|] that combines with GridS used in practice in the official code base Fairlearn (Bird et al. 2020).
6 EXPERIMENTS
We now use our flexible approach on several datasets in the classification task with a sensitive attribute. Although our method is proposed for over-parameterized models, it can also boost the performance on small models. Depending on the specific dataset and model architectures, we use either the grid search or the exponentiated gradient method developed by |Agarwal et al. (2018) as fairness algorithms to enforce the fairness constraints, while adding our FIFA loss in the inner training loop. Note that our method can be combined with other fairness algorithms.
Datasets. We choose both large image dataset and two simpler datasets. We use the official train-test split of these datasets. More details and statistics are in the Appendix. (i). CelebA (Liu al. 2015)): the task is to predict whether the person in the image has blond hair not where the sensitive attribute is the gender of the person. (ii). AdultIncome (Dua & Graff 2017)): the task is to predict whether the income is above 50K per year, where the sensitive attribute the gender. We also use the new AdultIncome (from California in 2021) introduced by Ding et al. (202T), where the sensitive attribute is the race. (iii). DutchConsensus ((voor de Statistiek [Statistics Netherlands)) the task is predict whether an individual has prestigious occupation and the sensitive attribute is the gender. Both AdultIncome and DutchConsensus datasets are also used in IAAgrraal et al. (2018).
Method. Due to computational feasibility (ExpGrad needs to store all intermediate models at prediction time), we combine Grid Search with FIFA for the CelebA dataset and ResNet-18 and use both Grid Search and Exponentiated Gradient on the AdultIncome with logistic regression. Besides C' and ds we also treat a as tuning parameters (in Eq. 2). We then perform hyper-parameter sweeps on the grids (if used) over C, di. and a for FIFA, and grids (if used) for vanilla training (combine fairness algorithms with the vanilla in the Appendix.
loss). More details are included
Evaluation and Generalization. When evaluating the model, we are mostly interested in the generalization performance measured by a combined loss that take into consideration both fairness } [n(]), which
violation and balanced error. We define the combined loss as Lollf] = 1 Lewl + favors those classifiers that have a equally well- performance in terms of classification and faimess. We consider both the value of the combined loss evaluated on the test set Sua, and the generalization error for loss L is defined as GenErr C, f] (Seee) [[]
7

---

Published as a conference paper at ICLR 2023
Fairness Tolerance Method
0.01
0,05
0.10
FIFA
Vanilla
LDAM
Vanilla
I.AMM
Vanilla
Combined Loss
Test
6.71% %
7.29%
14.01%
6.34%
7.38%
13.05%
6.54%
7.34%
16.71%
Gen Error
0.66%
2,07%
6.87%
0.88% %
1991%
4.21%
0.62%
1.14%
7.82%
Fairness Violation
Test
2.75%
5.39%
20.298
3.29%
5.57%
17.92%
2.65%
2.96%
26.15%
Gen Frror
2.57%
3.07%
13.59%
0.66%
3.00%
8.47%
0.46%
3.97%
14.78%
Tist
10.67%
9.20%
7.74%
9.39%
9.19%
8.17%
10.43%
11.72%
7.27%
Balanced Error
Gen Error
1.07%
1.10%
0.83%
0.05%
1.70%
0.85%
Grid search with FO construint on CelebA dataset (Lu et al, 2015 using ResNet. 18, hest results with respect to test combined loss unong sweeps of hyper parumneters are shown. As am interesting special case of our FIFA method, we note that although the LDAM method improves the performance compared with vanilla GS, it is effective method.
Table I:
Teat Coumbree Lews
Test Paimans Visiation
Contined Gencraliozion
Exirnss Viviation Gonreslaatonn
0.8
Mithoel
Mathod
Mathed Vizila FIEA
Mathed
Varile
Nizila
Vazila
0.5
310
1108
112
0:31
1154
112
0:31
1154
(8) Cas (5
(h) Eyy (Ses))
GenEi (Cet fl.
(d) GeuEire[an f)-
Figure 4: Loss an test set 4 4h and generalization gaps 44 Md of the combined loss and the fairesss loss on CelehA dataset. We repeat the
experiment for 20 times using the hyper-perameters corresponding the besf-perforning models [able Solid blue line marks the grid search combined with vanilla training whereas dasbed orange line marks grid search combined with the FIFA loss. We also plot 95% confidence based on 20 repeated runs. We observe that method FIFA has significanlly better genemlizattinn performance in terms of both smaller losses the test well as narrower gencralization gaps.
6.1 EFFECTIVENESS OF FIFA ON
MODELS
In this subsection, we thoroughly analyze the results from applying FIFA to over wee-parameterized models for the CelebA dataset using ResNet-18. We use the grid search algorithm with fairness
violation tolerance parameter e E {0.01, 0.05, 0.13 (with a little abuse of notation) for all constraints. We perform sweeps on syper-parameters C E [0, 0.01], a E [0, 0.01. do Ma M,,M E [0, 0.01]. and 60. Female = 81 Femaee = 0. As special case that may be of interest, when a = 0 and do Ma 81,Male = 0, the FIFA loss coincides with the LDAM loss proposed in Dua Graff (2017). with one common byper-parameee summarize our main findings below and give more details in the Appendix including experiments with DP constraints, delayed-reweighting (DRW, (Cao et al. 2019)), and reweighting methods.
C' E [0, 0.01]. We log the losses on the whole training and test set. We
Logits-based methods improve fairness generalization. We summarize the best results for each method under different tolerance parameter in Table Note that the actual violation may exceed the tolerance on test data. We note that both FIFA and LDAM significantly improve the test performance of both combined loss and fairness violation among all three choices of e, while having comparable training performance (omitted in the table). Interestingly, directly applying reductions- based method using vanilla model in the inner loop (the "Vanilla" columns) seems inferior, likely due to the imbalance across subgroups. This implies the effectiveness and necessity of using logits-based methods ensure better faimeess generalization.
FIFA accommodates for both fairness generalization and dataset imbalance. Although both logits-based method improve generalization as seen in Table [ our method FIFA has significantly better generalization performance compared with LDAM, especially in terms of fairness violation. For example, when 0.01 and 0.05, FIFA achieves test fairness violation that is at least 2% smaller compared with LDAM. This further demonstrates the importance of our theoretical motivations.
Improvements of generalization are two-fold for FIFA. When it comes to generalization, two relevant notions are often used, namely the absolute performance on the test set, and also the generalization error between the training and test set. We compute the generalization error in Table T for both combined loss and faimess violation. We observe that FIFA generally dominates LDAM and vanilla in terms of both test performance and generalization error. We further illustrate this behavior in Fig. where we give 95% confidence band over randomness in training. We note that our FIFA significantly outperforms vanilla in a large margin in terms of both generalization notions, and the improvements mostly due to better fairess generalization. In fact, as suggested by the similarity in the shapes of curves between Fig. 4c and Fig, Ad fairness generalization dominates classification generalization, and thus improvements in fairness generalization elicit more prominently overall.
8

---

Published as a conference paper at ICLR 2023
Dataset Metric
AdultIncume
DutchConsensus
Combined Loss
Fairness Violation
Combined Loss
Fairness
Violation
Method
Train
Test
Train
Test
Train
Test
Train
Test
FIFA
15.7217%
13.4812%
7,8863%
2.7776% %
12.80 12.8013%
13.1686%
3.7220%
4.3532%
0.01
Vanilla
13.9561%
14,3001 %
6.7861%
6.7475%
12.8444%
13.2267%
3,7935%
4.43233%
FIFA
13.5634%
13.5491%
5.7088%
4.9315%
12.8820%
13.2228%
3.8525%
4.4323%
0.05
Vanilla
14.4697%
14.8647%
7.5962%
7.8575%
12.8818%
13.22369
3.8525%
4.4323%
FIFA 13.5857%
13.9043%
6.1217%
5,9689 %
12.8717%
13.1748%
3.8326%
4.3532%
0.10
Vanilla
15.5342%
15.9387%
9.7514%
10.0750%
12.8757%
13.2099%
3.8392%
4.4059%
Table 2: Exponentiated gradient with EO constraint the Adultincome and DutchConsensus datasets using logistc regression one-layer
neural nel), best results with respect to test combined loss among sweeps of hyper parameters are shown.
Falmese (BO) Vialation
Pareto Frontier (e 0.01)
Vaimese (BO) Viallatio
Pareto Frontier 0.05)
Faimoos (DO) Vialution
Pareto Frontier (e
Visila (Teass)
Visiila (Teass)
Viniila ("inas)
Visile
Masill (Tox)
H NoW--opte
Visilla
FERA (Thiis) PIFA (Tiet)
(Trnic)
FIRA (lisiz)
DEFA (Tiet)
FIPA (Teee)
0300
Gus Rolewad Clesiffeatio Frror
0.10
0.15
0.31
0:33
1.30
030
CJDS
1.10
0.31
6:33
1.30
030
CJ1
B.D
1.15
0.31
0:21
0.30
Ri lewae Clesificaion Error
Balaneol Classificatin Error
(a) 0.01.
(b) 0.05.
(0) 0.10.
X-Combine Loss (e = 0.01)
X-Combine Loss (c 0.05)
X-Combine Loss (e = 0.1)
Method
Method
Mothod
VaniLa
VaniLa
Vanilla FIPA
FIFA
FIFA
0.0
06
06
(((()) Figure 5: Pareto frontiers of the balanced loss (Cna) and fairness loss (Cn) of CelebA using ResNet 18 with grid search combined with FIFA vanilla softmax-cne ceftma--crss-enttiie eross-entmpy loss respectively. (a)-(e) exhibit
2x ((See))
U.01.
(/((a)) with
Best- Bert-peeforning rypor-parametes from Table used, where each configuration is repeated 20 times independently. Here blue and orange markers correspond to vanilla and FIFA respectively, and circular and cross markers corespond to training and testing metrics respectively. We observe that our FIFA method ellective significunlly lowering the Pareto fromtier comparing with the vanilla method, implying that FIFA miligales fairness generiiization issues as seen in Figure
and (d)-(f) illustrate X-combined
Towards a more efficient Pareto frontier. In Fig. (la)-(c) we plot the Pareto frontier of balanced classification error (Ceat and fairness violation (Lxv) for all three choices of e. practice, one may be interested in specific convex combination of the fairness violation and balanced error. We thus consider A- weighted combined loss Lx = XCtv + (1 - A) with E [0, 1] being a user-specific weight. In Fig. d))) we compute L) for grid of 100 values of À under the same setup. We observe that FIFA with GridS achieves frontiers that are lower and more centered compared with those trained in vanilla losses with GridS. Furthermore, for most of the combining weight X, FIFA achieves better test performance.
6.2 EFFECTIVENESS OF FIFA ON SMALLER DATASETS AND MODELS
We use logistic regression (implemented as a one-layer neural net) for the AdultIncome and Dutch- Consensus datasets with similar sweeping procedure are similar to those described in Section 6.
Results. We tabulate the besf-performing models (in terms of test combined loss) among sweeps in Table include more details in the Appendix. The observations are similar as in Section FIFA outperforms vanilla on both dataset across three different tolerance parameter e; since the datasets are much simpler in this case, the improvements are less significant.
7 DISCUSSIONS AND CONCLUSIONS
Generalization (especially in over-parameterized models) has always been important and difficult problem in machine learning research. this paper, we set out the first exposition in the study the generalization of fairness constraints that has previously been overlooked. Our theoretically-bacee backed FIFA approach shown to mitigate poor faimess generalization observed in vanilla models large or small. We leave more fine-grained analysis of the margins the future work.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
The research of Jiayao Zhang is partially supported by DARPA FA8750-19-2- 1904-1044, IARPA 2019- 1905 160000006 and ONR 100014-19-1-2620 The research of Linjun Zhang is partially supported by NSF DMS-2015377 CAREER and the Sloan Fellowship. We would also like to thank the support of Kaiser Permanente Washington Health Research Institute and funding RO1 MH125821.
The research of James Zou is partially supported by funding from NSF
ETHICS STATEMENT
We mainly consider specific type of fairness constraints such as equalized odds, equalized opportunity, and demographic parity. That may be a restriction in ethics. We hope our argument could be generalized other fairness notions in the future.
REPRODUCIBILITY STATEMENT
Our code is available the public on GitHub https://github. cotm//jaaa////a///// fifa-iclr23.
REFERENCES
Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna Wallach. reductions approach to fair classification. International Conference on Machine Learning (ICML), pp. 60-69. PMLR, 2018.
Jing An, Lexing Ying, and Yuhua Zhu Why resampling outperforms reweighting for correcting sampling bias with stochastic gradients. In International Conference Learning Representations (ICLR), 2021. URL
https://cpenreviiev. www.nnttt/ooofiiioooooooo QQKO2mXV
Alex Beutel, Jilin Chen, Tulsee Doshi, Hai Qian, Allison Woodruff, Christine Luu, Pierre Kreitmann, Jonathan Bischof, and Ed H Chi. Putting fairness principles into practice: Challenges, metrics, and improvements. In AAAI/ACM Conference AI, Ethics, and Society, pp. 453-459, 2019.
Lukas Biewald. Experiment tracking with weights biases, 2020. URL https:: /tt/://www www..wwwo wandb. com/
Software available from wandb.com.
Sarah Bird, Miro Dudík, Richard Edgar, Brandon Horn, Roman Lutz, Vanessa Milan, Mehrnoosh Sameki, Hanna Wallach, and Kathleen Walker. Fairlearn:
A toolkit for
sessing and improving fairness in AL. Technical Report MSR- 2020-32, Microsoft,
www.erccccppliicaaiioo May 2020. org.a//eeee.....oaooaaaaaaoaaaan in- ai/ Fairiearn- a- toolki: for aesssssssssssnngggee and on
URL lhttps://wwt http://wwwww...ooo.ootooo com/ wttp:/oww...ooeeeeee//eeeeeeeeee
Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga. and Tengyu Ma. Learning imbalanced datasets with aubel-distribution-aaaa margin loss. In Advances Neural Information Processing Systems (NeurIPS). 2019.
R Yates Coley, Eric Johnson, Gregory E Simon, Maricela Cruz, and Susan M Shortreed. Racial/ethnic disparities in the performance of prediction models for death by suicide after mental health visits. JAMA Psychiatry, 2021.
Andrew Cotter, Maya Gupta, Heinrich Jiang, Nathan Srebro, Karthik Sridharan, Serena Wang, Blake Woodworth, and Seungil You. Training well-genen gell-generalizing classifiers for fairness metrics and other data-dependent constraints. In International Conference Machine Learning (ICML), pp. 1397-1405. PMLR, 2019.
Zhun Deng, Frances Ding, Cynthia Dwork, Rachel Hong, Giovanni Parmigiani, Prasad Patil, Pragya Sur. Representation via representations: Domain generalization via adversarially learned invariant representations. arXiv preprint arXiv:2006.1 1478, 2020.
Zhun Deng, Linjun Zhang, Amirata Ghorbani, and James Zou. Improving adversarial robustness via unlabeled out-of-domain data. International Conference on Artificial Intelligence and Statistics (AISTATS), pp- 2845-2853. PMLR, 2021.
Zhun Deng, He Sun, Zhiwei Steven Wu, Linjun Zhang, and David C Parkes. Reinforcement learning with stepwise faimess constraints. arXiv preprint arXiv:2211.039000 2022.
10

---

Published as a conference paper at ICLR 2023
Zhun Deng, Cynthia Dwork, and Linjun Zhang. Happymap: generalized multicalibration method. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Schloss Dagstuhi-Lciinni--Zonnn für Informatik, 2023.
Frances Ding. Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine learning. Advances in Neural Information Processing Systems, 34, 2021.
Michele Donini, Luca Oneto, Shai Ben- Ben-David, John Shawe- Taywer and Massimiliano Pontil. Empirical risk minimization under faimess constraints. Advances in Neural Information Processing Systems (NewrIPS), 31, 2018.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL edu/ml
uci
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Faimesss through awareness. In Innovations in Theoretical Computer Science Conference (ITCS), pp. 214 226, 2012.
Harrison Edwards and Amos Storkey. Censoring representations with an adversary. arXiv preprint arXiv:1511.0589. 2015.
Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubramaniinn. Certifying and removing disparate impact. In International Conference on Knowledge Discovery and Data Mining (KDD), pp. 259-268, 2015.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29, 2016.
Haibo He and Edwardo A Garcia. Learning from imbalanced data. IEEE Transactions on Knowledge and Data Engineering, 21(0):223--2284 2009.
Haiho Hc and Yunqian Ma. Imbalanced learning: foundations, algorithms, and applications. Wiley-IEFF Press, 2013.
Kenneth Holstein, Jennifer Wortman Vaughan, Hal Daumé III, Miro Dudik, and Hanna Wallach. Improving fairness in machine learning systems: What do industry practitioners need? In CHI Conference on Fuman Factors in Computing Systems (CHI). pp. 1-16, 2019.
Sham M Kakade, Karthik Sridharan, and Ambuj Tewari. On the complexity of linear prediction: Risk bounds. margin bounds, and regularization, Advances in Neural Information Processing Systems (NeurIPS), 21, 2008.
Salman Khan, Munawar Hayat, Syed Waqas Zamir, Jianhing Shen, and Ling Shao. Striking the right balance with uncertainty. In Conference on Computer Vision and Puttern Recognition (CVPR). pp. 103-112, 2019.
Michael Kim, Amirata Ghorbani, and James Zou. Multiaccuracy: Black-box proc-procssiing for faimess in classification, AAAI/ACM Conference on AI, Ethics, and Society, pp. 247-254, 2019.
Ganesh Ramachandra Kimi, Orestis Paraskevas, Samet Oymak, and Christos Thrampoulidis. Labell-mbalancedd and group-sensitive classification under overparameterization.. Advances in Neural Information Processing Systems (NeurIPS), 34, 2021.
Bartosz Krawezyk. Learning from imbalanced data: open challenges and future directions. Progress Artificial Intelligence, 5(4):221-232, 2016.
Preethi Lahoti, Alex Beutel, Jilin Chen, Kang Lee, Flavien Prost, Nithum Thain, Xuezhi Wang, and Ed Chi. Fairness without demographics through adversarially reweighted learning. Advances in Neural Information Processing Systems (NeurIPS), 33:728-740, 2020.
Yaoyong Li, Hugo Zaragoza, Ralf Herbrich, John Shawe-Taylee and Jaz Kandola. The perceptron algorithm with uneven margins. In International Conference Machine Learning (ICML), volume 2, pp. 379.386, 2002.
Weiyang Liu, Yandong Wen, Zhiding Yu, and Meng Yang. Large-margin softmax loss for convolutional neural networks. In International Conference Machine Learning (ICML.) volume pp- 2016.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In International Conference on Computer Vision (ICCV), December 2015.
David Madras, Flliot Creager, Toniann Pitassi, and Richard Zemel. Learning adversarially fair and transferable representations. In International Conference Machine Learning (ICMI.). pp. 3384-3393. PMLR, 2018.
11

---

Published as a conference paper at ICLR 2023
Inderjeet Mani and I Zhang. kNN approach unbalanced data distributions: study involving informa- tion extraction. In Workshop on Learning from Imbalanced Datasets, volume 126, pp. 1-7. International Conference on Machine Learning (ICML), 2003.
Natalia Martinez, Martin Bertran, and Guillermo Sapiro. Minimax Pareto faimess: A multi objective perspective. In International Conference on Machine Learning (ICML), pp. 6755-6764. PMIR, 2020.
Shiori Sagawa, Aditi Raghunathan, Pang Wei Koh, and Perey Liang. An investigation why overparameter ization exacerbates spurious correlations. In International Conference on Machine Learning (ICML), pp. 8346 8356. PMLR, 2020.
Debjani Saha, Candice Schumann, Duncan Meelfresh, John Dickerson, Michelle Mazurek, and Michael Tschantz. Mcasuring non-expert comprehension of machine learning fairness metrics. In International Conference on Machine Learning (ICML), pp. 8377-883 -3877. PMLR, 2020.
Ludwig Schmidt. Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Adversarially robust generalization requires more data. Advances in Neural Information Processing Systems (NeurlPS), 31, 2018.
Centraal Burcau voor de Statistick (Statistics Netherlands) and Minnesota Population Center. The Dutch vir- tual census of 2001, 2001. URL httpa:://iccrodtaa wor dbank hhbbanx..rr//nneex..pp//c..a... 2102
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna P Gummadi, Faimess constraints: Mechanisms for fair classification. International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 962-970. PMLR, 2017.
Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representations. In International Conference on Machine Learning (ICML), pp. 325-333. PMLR, 2013.
Linjun Zhang, Zhun Deng, Kenji Kawaguchi, and James Y. Zou, When and how mixup improves calibration. ArXiv, ahs/2102.00688) 2021.
12

---

Published as a conference paper at ICLR 2023
Appendix
A OMITTED DERIVATION
In this section, we will talk about several missing details in the main context.
A.1 EXTENSION TO MULTI-CLASSES AND MCLPI-GROUPS FOR EQUALIZED ODDS
We discussed the case that y {0, 1 and A {ai, 02) in the main context. In this subsection, discuss the extension to multi-classes and multi-groups.
First, we extend the case to y/ {0, 1) and |A] 2. In that case, can consider the constraints
Σ
Σ (P() = i|Y = i, A a) P()())()))))))))))))))))))) = i| = = i, = ad)],
0,8' a' IEV
regardless the order (a, a'), and there are (12) pairs (a, d')'s.
Thus, our performance criteria grout- [f] can be taken as;
Lhal
Σ Σ
(P(M(X) = = i, A =
= = = d')l
0,a' EA,aaa KEY
Then, via Lemma
A.2 for all EEF
C(F)
20(1A| 1)
C(F)
Mmulti groups [f] <
7i
Vi,a
ni,a
iEy
iEY,aAA
1
C(F)
2a( - 1)
C(F)
%
74
Pi
niça
iEy
iEY,aEA
We overload the notation ā 2cx - 1), then we have
Mmulti-groops [f]
Σ
á
C(F)
(A.1)
ni.o
E
aEE
Notice the difference between Eq. A.I
and Eq. 2 is that in A.I
Eq.
|A| 2 2. Thus, by similar
proof as in Theorem A.I we can obtain
70/71 no
1/4 111
where the adjusted sample size
n.
(Llati EjeA VTallae
for E {0, 1}.
Given the results above, for multiple classes with multiple groups, for i,j E V,
74/73 n 1/4 /5g
where the adjusted sample size n, (1,,,, EiEA V As )
no, A.
for E V.
FIFA for multi-classes and multi-groups. We will demonstrate how apply the above motivations to design better margin losses. Consider logits-based loss
E((x, v): = (z) (er))) which is non-increasing with respect to its first coordinate if we fix the second coordinate.
Our flexible wawaancce-aines--aaaa (FIFA) approach modifies the above losses during training fFuAa ((x, a); f) = {(f(x), Ag.a, {f(z)) where A 1/4 + 8 and ~ 2 The specific assignment of 6 2 is described in
(A.2)
C/n//
Section A.2
13

---

Published as a conference paper at ICLR 2023
A.2 ASSIGNMENT OF ò1,a FOR MULTI-GROUPS
In this subsection, we describe how to choose òū,a for multiple demographic groups Recall in Section A.T for multiple demographic groups,
ΣΣ C(F) + Σ à ((F)
Mmultti grauutiigroupl//e [f] -
n4 V nia
(A.3)
KEy 76
iEY,eEA
Given Vi. 2 7/. similar as in the main context, we can take Vi, = 7/ + 83 where dú,a tuning parameters.
Assume there are k groups. Let us first ordering S by in a decreasing order. Without loss of generality, | 2 |St 2 ... 2 |S Thus, when tune the parameters 6 's, we set 8 = 0 if there are ties and |Stal = |S but for
(or we can randomly choose other a's to set 6iaa simplicity, we ignore this case), and we make sure 8s,a; S di,0z I ... Si,ay This is optimal in the
sense that if there are constants 61 S 62 S d3 S ... S òk. then
((F) V
c(F) n1.a5
Σ EE 7/s + de,a;
E iEV.ayEA
a + 64
Ti,a;
where (.) is a permutation. In other words, our way to assign ó,, 's can make the upper boupnd on RHS of Eq. (A.3) optimal. This is direct application of rearrangement inequality, see Lemma A.1
Lemma A.1 For x1 S
2k. y1 S y2 S S yk. any permutation a(-)
J&DI + 2k-19/ Tidk S (1)1 Io(2)1/2 + Io(k)Bl x191 T23/2
A.3 DERIVATION FOR OTHER FAIRNESS NOTIONS
In this subsection, we consider theory-inspired derivation for other fairness notions. For simplicity. we still focus on the case that y f0. 1} (this necessary for EqOpt) and A {ai, a2). Given the derivation in this subsection, we can further derive FIFA for other fairness notions in Section A.
Equalized opportunity. Specifically, for EqOpt, the aim is:
min Lbwlf]
s.t. Vy V, A, P(N(X) = 1/2 1, A a) PP((X) 1|2 -1),
This is simple version of EO in some sense. Directly using the derivation in Section A.1 have
70/11 = no 1/4 1//+/// 1/4
where the adjusted sample size
11 1, 1,02
(TT1, 11,02 + 2a ( 7, (
Demographic parity.
Similar to EO, for DP, the optimization aims to:
min Coal [f]
4
s.t. Vy V., P(h(X) = a))
In this setting, we no longer can expect all the training samples are perfectly classified and fairness constraints violation is perfectly satisfied because there exists fairness and accuracy trade-off in training phase for DP. However, in real application, people always adopt relaxation in fairness constraints, i.e. [P(h(X)) y a) (P((X) v) < for some > 0 (if there are only two groups, one can alternatively use [P(h(X) v/A= a,) P(h(X) = g) A azl S c). When large enough (or P(Y = 1|A = a,) is close to P(YY = 1/A = az)). if we use suitable models, similar in the EO setting, would expect all the training examples classified perfectly while
14

---

Published as a conference paper at ICLR 2023
satisfying (X)) = y|A a1) P = v)(4 02l S Then, to characterize a trade-off between margins.
similar techniques
Specifically, simple calculation leads to Eiey [P(((X) i| a1) P i|A a2) - Eje() (o.) P(Y i| Cj)Ci.a [f] + L. where is a term not related to f. Thus, our optimization objective (not performance criterion) for DP can be taken as:
Coal + a Σ P(Y i| Ci,f, 1,0
(A.4)
for weight a. We can use training data to estimate P(Y = = = a). For simplicity, we can also use Loalf + Σi, Li [f], which shares the same upper bound in Theorem 3.1 and also implies ju/n ng 1/4 / 1/4 that will also be used in the experiments in later sections. We should also remark that when is too small, our method may not work, this can also be reflected in Table when =.0.1.
A.4 OMITTED PROOFS
A.4.1 PROOF OF THEOREM
Theorem A.1 (Restatement of Theorem 3.1) With high probability over the randomness of the training data, for y {0, 1}. A = {a1,a2), a. and for some proper complexity measure of class F, iee. f(r) any f E F.
C(F)
2a
C(F)
C(F)
2a
C(F)
MISI S KEY
REy,aEA
Tiaa
Tia
iEy
iEY,aEA
%
ni.a
where "i is the margin of the i-th class's sample set S and Vi is the margin of demographic subgroup's 's sample set Sia-
This following lemma is the key lemma we will use. Let us define the empirical Rademacher complexity of of subgroup/class margin on as
R((F) = Eg ssup Σ - - max [(x))e]], ni fEr JES:
841
Ria
Relsup Σ $[((z)); "
max f(x;)x]]
Tiiaa
JeF JES.a
where E, is i.i.d. drawn from a uniform distribution {-1,1}-
Lemma A.2 Let E
P Px-P, (max)4i f()) f(X); 7) and Eygii P Px-P.n. (maxj4s f(X), > f(X); 7) With probability least 1 5 over the the random- ness of the training data, for some proper complexity measure of class for any f F. E (i,a)) E,, A}, and all margins >>0
1 RR.(F) ca (n.,5,, L. S L. 7.
(A.5)
where R., is the empirical Rademacher complexity of F of subgroup/class margin on training
dataset corresponding to index set S., which can further upper brounded by v C(F) Also,
(n,,, 8, 7x) is usually low-order term in nu
margin-based Proof: This is direct application of the standard margin- based generalization bound in Kakade et al. (2008).
15

---

Published as a conference paper at ICLR 2023
Proof of Theorem A.1 Notice that all the training samples classified perfectly by h, not only P ((x,y) (h(X)= i E y and aj E A. remark here that P(h(X) = i|y = i, = a) = P(X,Y) (l(X) +
= O is satisfied, we also have that IP (x,Y)~PP.g (h(X) # Y) = for all
Y) = 1 (( < maxj+y {());) Thus, we have
Cralls] + ((h(X) = i|y = i, A-A= ai) P(N(X) iiy = i, a2)l
iEy
S Loullf + (X(())))), (M(X) + Y) + P(XY)) (h(X) # Y)).
P(xY)) (h(X) # Y). then, plug in Lemma A.2 and realizing Ly,* = 0 (all training errors are 0) by our assumption and ignoring low order terms e, (n-, ò, 7+), we have
Notice Lbot =
Gmall/1 + +
((P(x.))xPP,
+Y)+ Pox.))wi.,, - +Y)
Σ
2
colft ta Σ
(Notice Li,aff] = P(x.))-P... (h(X)+ Y))
Ey
iEVinEA
S (O(F)
20
Thay/14,
KEY
KEV,eEA
In the last formula, we multiple for nicer looking expression, it won't affect the optimal ratio for 7o/ "1. Also, notice that Kta 2 %. have
VC( iE
+ 2a
Σ
S VC(F) iEY
1
+ 20 Σ
Tayynia
iE)'aEA
iEY,aEA
The proof is complete.
A.4.2 OPTIMIZATION OF 70/7
Theorem A.2 For binary classification, let F. be a class of neural networks with a bias term, i.e. F = (S + b) where I is neural net function and b RR² bas, with Rademacher complexity upper bound RF) S / ((F), Suppose some classifier f can achieve total sum of margins 7á 71 = 3 with %o: 7 0. Then, there exists classifier 8 E F with margin ratio
n = i 1/1 /
/ 2//4 1m0 ///4//1//1
where the adjusted sample size ni (l,nua, EyeA m for i E y.
millenss
Proof: This can directly follow the proof in Theorem 3 in Cao (019)). that we need to solve
The only difference is
C(F)
2a
C(F)
min To +
Tii
Vi
ni.a
aE
More specifically, by simple calculation, for y (0, 1},
= (d1,a2h
2a
C(F)
C(F)
KEY
aE
Vi
ni,a
70
7
then by applying Theorem 3 in Cao et al.
2019 by replacing nt's with n. it gives the final result.
16

---

Published as a conference paper at ICLR 2023
A.4.3 PROOF OF EXAMPLE 3.1
Example A.1 (Restatement Example 3.1
Given function f and set S, let
dist(f.
min [f) - -s|12-
a,SES
Consider two classifiers f,f E F such that
1/4 (ist(f,Soo// dist( = N/ /m1 1//1
1/11//n1 and di So)/ dfst(f', = no 1/1 /n 1/1 Suppose || > Vplogn, I| < C. (AÂ (G) = 0. and #1.02 I 11.1 for a sufficiently small 01 > 0, then when no, ny are sufficiently large, with high probability we have M[f] < M[f].
Proof: Recall that ñ; =
(v Macammia to EaEd (m for i E (0, 13, and our training data follow
n,llneAmsa
distribution: x = 0 ~ Σ Tu, Np(ts: x 1 ylyy- E Ti. NL. Ng(M + +,,1))
M[f] -2 - ((((X) 1|Y 0) + 1 P(h(X) 2 0 1)
Σ
[P(((X) i|Y = -iA=aaa a1) P(((X) =ilY= =iAA
iey
2
T0,a; $1 T H4 -
c 8r 14 113111
c
+
T1,0; $1
2 1=1
|/01|
2 i=1
|1
+
|00(
Te
9
T
P1
)1 + |
T
+ 118-111
C
3 #n
+ 11
||311
||31||
|
|
For different margin ratio 7, we have c uT + + 18-1 + Op(vplogn) where the Op(vplogm n) term accounts for the variation of random samples and is based the fact that ||-]| ~ x if Z 10, and max Zi = Or(plog n) if Ei.... Zn it.d
Xx.
Using the fact that ||,3||| > vplog n and ||ب/|| < C, we then have (1I + (1)
Similarly, we have
+ 2 c- 118+112
M[f o6 1|801
o(1)
||811|
Then let's consider the two ratios 7 = n2y In the following we compute No and u.: When T1,0g S C1 fu
114 /n1 -1-1/ 1/4
and 5 = ng 1-4 / 1/4
(Il EaEd ] E (0.9m1 m
N: Nillucan1e
When T0,02 #0,01 uo ( All:AAto.ua Eoea )
ng A
142/2 2no
As result, we have $ E [1.9, 2]. When the data is imbalanced such that 7
[11) (21)2/4 1, we have
0 < 1- < 14y < 1/22, and consequently
1 1/ ) Φ 145 |18
1
112
113-11
1+5 1181112
I+9 113-112- 11
1
Φ 1+9 ||81|
+ 4
||+0|
|
18+1
Additionally, we have that when || + co, the second term in the Mif]. the fairness violation error is o(1). Combining all the pieces, we have Mifi < <M.].
17

---

Published as a conference paper at ICLR 2023
A.4.4 PROOF OF THEOREM 5.1
Theorem A.3 (Restatement of Theoreem 5.1) Let p max p (f) alloo- For n
12pp B), the modified ExpGrad will return v-approximate saddle point of Loe in at most 4p B log( [C] + iterations.
Proof: We consider an extended version of h Agarwal et al. (018), which a function of (x.y.a) instead of just be function of xt h (ar, y. - (0, 1). Notice that ju(h) also satisfies the requirement in Agarwal et al. (2018) with the extend version h. Thus, directly by classic result of in Freund & Scapire (1996) and theorm Agarwal al. 2018), the result follows.
A.5 COMBINATION WITH OTHER ALGORITHMS
As we stated, the algorithm stated in the main context is just one of the examples that can be combined with our approach. FIFA can also applied to many other popular algorithms such as fair representation (Madras et al. 2018). We here show how to combine with fair representation.
In Madras et al. (2018), there are several parts, an encoder p, an adversary v, a decoder and predictor g. The optimization is:
min max m.x.xx...llgg...... S.P.k
where
1) + + X2 *2facc (K(x)))) + Aglanv ()((()) A)),
for cross entropy loss e.. decoding loss ldes, and adversary loss Enáv- We can modify the cross entropy loss &e EFIFA- So,
TIFFA (gn p. k) = X AI (g((()(()(()))
X2/ae X), + Ag (X)()XX))))))))))))))())))) A)).
Actually, for laav, we can similarly modify for indices, but it little complicated and notation heavy, so we omit it here.
B IMPLEMENTATION DETAILS
We use the official train-test split for the CelebA dataset. For AdultIncome and DutchConsensus, we use the train_test__pp of the scikit-less test set ratio of 0.8 and random seed of to generate the training and test set. We tabulate the sizes for subgroups Table
Adulthucome
CdebA
Labi Gender
Female
Male
Female
Fenale
Female
Male
procedure package with training-
Tran
9592
15128
11.9
6662
71629
66674
22630
1387
Text
4831
7684
9767
Table 3: Training and testing sample sizes ColobA AdultIncomne datasets across labels (Label) and sensitive attributes (Gender).
The sweeps are done on the wandoo platform (Biewald 2020), where all hyper-parameters except for the grid, are searched using its built-in Bayesian backend. All models for the same dataset are trained with fixed number of epochs where the training accuracies converge. Batch training with size 128 is used for CelebA and full batch training is used for AdultIncome. As special case of FIFA, when 0 loss proposed in Cao et al, (2019); FIFA further finetunes óū,a and a, and to ensure fair comparison, we set the same coverage for the the common byper-parameter C in the sweeps. In Fig. (6, we show the histogram of the hyper-parameter C in the sweeps for FIFA and LDAM. Note that the sweeps cover approximately the same range for this common hyper-parameter
for all and
the FIFA loss degenerates
non fairness-aware LDAM
Details on CelebA. We use the same pre-processing steps as in (Sagawa et al.) 2020) to crop the images in CelebA into 224 x 224 x 3 and perform the same z-normalization for both training and test set. We use ResNet- 18 models for training with the last layer being replaced to the NormLinear layer used by Cao et al. (2019) that ensures the imput as well as the columns of the wight matrix (with 2 rows corresponding to each label class) has norm 1. This ensures our adjustments the logits comparable. We use the Adam optimizer with learning rate x 10-4 and weight decay 10 10-5 to train these models with stochastic batches of sizes 128. We performed pilot experiments and learnt
18

---

Published as a conference paper at ICLR 2023
Meshod
Split Tharin
Total Accurary
Combined Loss
0.25
Vonilla
FIFA
Text
0.20
0.6
0.15
Method
Split
Vanilla
Train Test
0.10
0.4
FIFA
10
(a) Total accuracy.
(b) Combined loss.
Balanced Classification Error
Fairness (BO) Violation
Method
Spilt
0.5
Method
Split
Vinilla
Train
Vanilla
Train
FIFA
Test
0.4
FIFA
Test
0.3
0.2
0.2
0.1
0.9
Fairness
(d) Balanced errer.
Figure 7: Training and test traeectories different metries of ResNot- CelchA dataset under FIFA and vanilla losses respectively. that the generalization performance of vanilla models are consistently poor as training time increases, suggesting that it is difficult to cultivate an sarly-stopping that might alleviate poor generalization.
that under this configuration the models usually converges within the first 1500 iterations in terms of training losses and thus we fix the training time as 8000 iterations which corresponds roughly four epochs.
AdultIncome and Consennusss AdultIncome and Dutch- Consensus are two relatively smaller datasets that have been used for benchmarking for various fair classification algorithms such as Agarwal al. (018). We convert all categorical variables dum- mies and use the standard s-normalization to pre- pre-process the data. There are 107 features AdultIncome and 59 in DutchConsensus, both counting the senstive attribute, gender. We intend to use these datasets to test smaller models such as logistic regression, and we im- plement it one-layer neural net for consistency concerns, which is trained using full-bar ball-batch gradient descent using Adam with learning rate 1 x 10-4 and weight decay 5 x 10-5 for 10000 epochs. We do,Femule, Fermle [0. 0.01], and Mate = 51,Male = for the AdultIncome dataset and Ó0,Male, 51,Female E [0, 0.01), and Female Male O for the DutchConsensus Dataset. All models converge after this train-
Histogram of in ED 30-Cusstriied Sweepe
Method
PIFA
Denstry
LEAM
Figure 6: Histogram (cumulative density) of parammearretter C the sweeps for FIFA and LDAM. Vertical lines mark the values conreponndngg to models in Table
performing
ing measured by the training metrics. Although the exact pre-processing procedures for these two datasets are not available in Agarwal al, (20T8), found that on vanilla models under both GridSearch and ExponentiatedGradion
methods, the training and test performance (measured by total accuracy and fairness violation) are comparable with those reported in InAarwaal al. (2018).
Computational resource considerations. We perform all experiments on NVIDIA GPUs RTX 2080 Ti. Each experiment on CelebA usually takes less than two hours (clocktime) and each experiment Adultincome and DutchConsensus takes less than ten minutes.
19

---

Published as a conference paper at ICLR 2023
C ADDITIONAL EXPERIMENTAL RESULTS
C.I A TRAJECTORY ANALYSIS ON CELEBA
One observation we made in Table is that the improvements of the generalization of combined loss CelebA is largely due the improved generalization performance natural to wonder whether this behavior suggests that the sweet spots of generalization performance for balanced error and fairness violation may not be aligned, i.e., there is difference in training time scales for these two metrics to reach their optimal generalization. Furthermore, it is also open that whether one could enforce certain early stopping procedure (e.g., on the combined loss or the fairness violation) such that the generalizations on vanilla models may be improved.
fairness violations. It is
To explore these two questions, we plot the trajectories of training and test metrics for FIFA and vanilla (byper-paramette parameter chosen to be those corresponding to the best-performing models in Table 1) in Fig. 7 We observe that it is difficulty to (i) identify sweet spots of generalization gaps for the vanilla models; and (ii) enforce reasonable early stopping criterion that improves the generalization performances thereof.
C.2 CELEBA AND THE DP CONSTRAINT
We presented in Table our main results, CelebA dataset trained with grid search under EO constraint. We show in Table O the results on the DP constraints. Here all training configurations are the same as Table 1, except that we replace the EO constraint by the DP constraint. For ease of comparison, also recall the results on EO in Table 4 The observations are similar to those we made for Table 1, namely, FIFA improves significantly on the combined loss compared with vanilla.
Method
Combined Loss
Fairness Violation
Combined Loss
Fairness Violation
Train
Test
Train
Test
Train
Test
Train
Test
FIFA
7.37%
6.71%
5.31%
2.75%
8.65%
7.21%
4.84%
1.45%
0.01
Vanilla
7.14%
14.01%
6.69%
20.29%
10.74%
10.43%
4.72%
1.35%
FIFA
5.46%
6.34%
2.63%
3.29%
10.02%
9.40%
4.73%
1.07%
0.05
Vanilla
8.84%
13.05%
9.45%
17.92%
12.14%
11.60%
8.34%
5.17%
FIFA 5.92%
6. 6.54%
3.11% 11.37%
2.65% 26.15%
9.04%
8.32% 11.66%
2.98% 9.77%
0.04% 6.83%
0.10
Vanilla
8.90%
16.71% 1%
12. 13%
Table 4: Grid scarch with EO and DP constraint on CelebA datasct (Liu ct al. among sweeps hyper-parameters
2015 using ResNet-18, best results with respect to test combined
C.3
GRID SEARCH ON ADULTINCOME (DP AND EO)
EO
DP
Method
Combined Loss Train
Fairness Violation Train
Combined I Loss
Fairness
Violation
Test
Test
Train
Test
Train
Test
0.01
FIFA Vanilla
14.77618%
14.93573%
8.53851%
8,50086
13.75700%
14.05881%
0.08609%
0.00999g
16.68724%
17.28659%
10.39000%
10.92794%
14.83347%
15.09909%
3.32436%
3.65903%
14.79263%
14.91599%
8.508419
13.7495256
14.03440%
0.01008%
0.05
Vanilla
16.68724%
17.286599.
10.39000%
10.92794<g
14.83475%
15,1990955
3.32895%
3.659039
FIFA
14. 74.00999%
14,88935%
8. 1.5977%
8.1628386 10.92794%
13.722785
14.03193% 15,099098
033133
0.0101 1%
0.10
Vanilla
16.68724%
17.28659%
10.39000%
14.82782%
3.31507%
3.65903%
Table 5: Grid search with and constraint AdultIncome dataset using logistic regression, best resalts with respect combined loss among sweeps of byper-parameters are showa.
We also give in Table the grid search results on AdultIncome dataset, for both EO and DP constraints. We observe that on this small dataset and small model, FIFA also improve generalization performances for both EO and DP constraints. This further exhibits the flexibility of the FIFA approach.
20

---

Published as a conference paper at ICLR 2023
Combined Loss
Fairness Train
Violation Test
Balanced Error
Train
Test
Train
Test
Method
FIFA
14.26%
13.60%
5.39%
4.53%
23.12%
22.67%
0.01
Vanilla
14.22%
13.68%
5.33%
4.69%
23.10%
22.67%
FIFA
14.02%
13.22%
4.93%
3.71%
23.11%
22.73%
0.05
Vanilla
14.00%
13.23%
4.89%
3.71%
23.11%
22.74%
FIFA
14.20%
13.67%
5.29%
4.67%
23.10%
22.67%
0.10
Vanilla
14.20%
13.68%
5.30%
4.67%
23.10%
22.68%
Table FIFA-ExpGrad the New Adult Income datasct.
C.4 EXPGRAD ON THE NEW ADULTINCOME DATASET
We give in Table the results by applying EXFA+E on the new adult income dataset. We use the employment data from California in 2021 and set the same threshold of yearly income being 50K construct the label. However, the sensitive attributes becomes the race, where for White and for Black. We use the recommended covariates, which after dummification. results in 20 covariates and 129563 samples. split the samples randomly into 80% training set and 20% test set. The other configurations remain the same.
C.5 PER-GROUP RESULTS
To have better understanding of the per-group performance, we take a deeper look at (i) CelebA using FIFA+GridS; (ii) AdultIncome using FIFA+GridS; and (iii) New AdultIncome using FIFA+ExpGrad, all optimizing over the EO constraint. We show in Table T per-group accuracies and in Table I0 the differences between FPR and FNR across sensitive groups. Note that since the New Adultincome only conatins 20 covariates, the performances of different methods differ insignificantly.
Non-Blond Female Train
Non-Blond Male Train
Blond Female Train
Blond Male
Test
Test
Test
Train
Test
Method
FIFA-GS
95.28%
95.50%
93.01% %
92.70%
88.20%
87.22%
92.86%
84.44%
0.01
LDAM-GS
95.37%
95.47%
94.21%
94.19%%
88.81%
87.06%
91.13%
81.67%
Vanilla-GS
89.15%
90.29%
95.85%
96.12%
92.78%
93.06%
86.88%
72.78%
FIFA-GS
93.13%
95.11%
93.50%
93.19%
88.93%
87. 18%
91.56%
83.89%
0.05
LDAM-GS
94.97%
94,90%
91.83%
92.01%
87.15%
86.29%
92.86%
82.22%
Vanilla-GS
86.15%
87.50%
94.72%
95.16%
93.81%
94.03%
84.35%
76.11%
FIFA-GS
95.61%
95.75%
93.15%
93.10%
87.95%
84.68%
91.06%
82.78%
0.10
LDAM-GS
96.14%
96.15%
93.69%
93.19%
84.57%
81.85%
91.49%
79.44%
Vanilla-GS
87.07%
88.03%
97.75%
97.56%
95.58%
95.04%
84.21%
68.89%
Per-group accuracy
from
(EO).
<5K Female
<50K Male
50K Female
>=50K Male
Train
Test
Train
Test
Train
Test
Train
Test
Method
FIFA-GS
95.30%
95.22%
86.76%
86.72%
65.73%
63 56%
68.28%
67.91%
0.01
Vanilla-GS
74.64%
74.39%
64.25%
63.47%
89.91%
88.3 88.31%
85.02%
84.40%
FIFA-GS
95.29%
95.24%
86.71%
86.73%
65.65%
63.39%
68.34%
68.03%
0.05
Vanilla-GS
74.64%
74.39%
64.25%
63.47%
89.91% 911
88.31 %
85.02%
84.40%
FIFA-GS
95.32%
95.30%
87.14%
87.14%
65.22%
63.22%
67.55%
67.05%
0.10
Vanilla-GS
74.64%
74.39%
64.25%
63.47%
89.91%
88.31 %
85.02%
84.40%
Table 8: Per group accuracy on the AdultIncome datavet from FIFA+GridS (IOO).
21

---

Published as a conference paper at ICLR 2023
<50K White
<50K Black
>=50K White
>= Black
Train
Test
Train
Test
Train
Test
Train
Test
Method
FIFA-GS
71.34%
71.96%
70.03%
72.40%
82.79%
82.92%
77.40%
78.38%
0.01
Vanilla-GS
71.41%
71.99%
69.96%
72.22%
82.78%
82.91 %6
77.44%
78.22%
FIFA-GS
71.53%
72.01 %
69.37%
71.68%
82.67%
82.76%
77.74%
79.04%
0.05
Vanilla-GS
71.54%
72.00%
69.30%
71.58%
82.67%
82.76%
77.78%.
79.04%
FIFA-GS
71.40%
72.00%
69.96%
72.22%
82.78%
82.89%
77.48%
78.22%
0.10
Vanilla-GS
71.40%
71.98%
69.96%
72.22%
82.78%
82.89%
77.48%
78.22%
Table Per-group accuracy
Adultlacome
ElFA+ExpGrad
ColebA (Grids)
Adultlncome (GridS)
New Adullnnomme (Exp(irad)
FPR
FNR
FPR
FNR
FPR
ENR
Train
Method
FIFA
2.27%
2.79%
4.66%
2.77%
8.54%
8.50%
1.55%
4.35%
1.31%
0.64%
5,39%
4.53%
0.01
Vanilla
6.69%
5.83%
5.9096
20.29%
10.39%
10.93%
4.89%
3.91%
1.45%.
0.23%
5.33%
4.69%
1.63%
2.17%
Vanilla
8.57%
7.66%
9.15%
17.92%
10.39%
10.93/9
1.89%
3.91%
2.21%
0.41%
4.89%
3.71%
FIFA
2.46%
2.65%
3.11%
1.90%
8.18%
8.16%
2.32%
3.83%
1.44%
0.22%
5.29%
4.67%
0.10
Vanilla
11.37%
Table 10: EPR/ENR differences across sensitivy groups on three datasets.
22


Reviews:
[{"review_id": "g87trcy4P4", "reviewer": "Reviewer_Kgun", "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": "In settings where the goal is to learn a classifier that does not exhibit disparate impact, it is common to constrain the learning process via fairness constraints or an adversarial learning procedure. Typically, the disparate impact effects are reduced on the training set, but bias is still observed on the test set. In this paper, the authors propose a new margin-based loss function that is then minimized via exponentiated gradient descent. The intuition behind the loss is that the decision boundary of the final classifier should be further away from small sub-groups in the dataset.", "summary_of_the_review": "Overall, the work addresses an important problem with a new margin-based loss function that improves the generalization of the fairness property of a model at test-time.", "strength_and_weaknesses": "**Strengths**\\\nThe paper addresses an important problem and the choice of the loss does indeed make intuition sense. Further, the empirical results indeed suggest that one makes significant improvements using the proposed loss function modifications in this work. \n\n**Weaknesses**\n- Clarification about the importance of group sizes: I am confused about why the bounds in the paper and the key intuition is around group size as opposed to some other measure of group difficulty. One could envision a case where a smaller group is perhaps more homogenous, so it still easy to 'learn' with smaller samples versus a larger group whose inputs have more feature noise. I would've expected a term in these bounds that captures group difficulty. Any insight on this issue?\n- Adult dataset: I'd suggest the authors consider the recently introduced adult dataset by Ding et. al. (Retiring Adult dataset) as a replacement for the standard Adult dataset.\n- On first reading, it was unclear what parts of section 5 are new to this work, and which ones aren't. For example, I know the ExpGrad formulation is due to Agarwal, but several parts of that section are not well-delineated. For example, is Theorem 5.1 also based on the modification of the equivalent theorem from the Agarwal paper? \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "XSyjiTOTHn", "reviewer": "Reviewer_WVpp", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The work studies the generalization of fairness constraints  in Machine Learning systems.  The authors argue that while current algorithms are optimized for generalizing on the whole dataset, their efficacy on minority classes for imbalanced datasets have not been extensively covered They introduce their Flexible Imbalance Fairness Aware (FIFA) classification, combined with logit based losses.  The authors conclude their work by empirically showcasing the performance on relevant datasets for over-parameterized models.", "summary_of_the_review": "Overall, the paper tackles an important problem in the domain, especially with the rapid growth of large overparameterized. The paper is clear, well written and easy to follow. While the empirical significance is reasonably novel, the introduced technical novelty isn't as significant. ", "strength_and_weaknesses": "Strengths\n* The paper is well written, clear to follow.\n* It motivates the problem and lists the related work reasonably.It tackles an important problem in the domain, especially with the advent of large  overparameterized models.\n\n\nWeakness\n* The novelty of the technical contributions itself doesn't seem quite significant, specifically the integration with existing classification based approaches.\n* The overall empirical evaluation is  reasonably extensive, answering the questions raised in the introduction. However, it would be nice if the authors could elucidate further the  complexity/real world mapping of these datasets to real world challenges we observe.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "8bY0qFXicXo", "reviewer": "Reviewer_XQ8s", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents a regularization-based training loss modification that promotes larger margins for minority subgroups in order to improve fairness constraint generalization.", "summary_of_the_review": "The paper presents a somewhat novel approach to improving fairness constraint generalization based on enlarging margins of minority subgroups. It is missing some discussion of important related work, and important baselines for fairness constraint generalization as well.", "strength_and_weaknesses": "Strengths:\n1. Margin-based approach makes sense in theory and by intuition.\n2. Good comparisons against the well-known reductions-based approaches by Agarwal et al. (2018).\n3. Good empirical results.\n\nWeaknesses:\n- Would be interesting to have comparisons against more than a single work; namely, a glaring baseline that's missing is the TensorFlow Constrained Optimization package, even more so given that this work focuses on over-parameterized models (NNs).\n  - The same authors of the TFCO package also published work specifically focused on generalization of fairness constraints:\n> Cotter, Gupta, Jiang, Srebro, Sridharan, Wang, Woodworth and You. \"Training Well-Generalizing Classifiers for Fairness Metrics and Other Data-Dependent Constraints\".\n  - These references should at least be discussed in related work, but in truth they should also serve as baselines for empirical results.\n- Bad fairness constraint generalization can only mean that performance on one subgroup generalizes better than performance on the other group; it would be interesting to see group-wise loss (or group-wise TPR or FPR), and how these change with difference values for fairness constraint tolerance.\n  - Since this difference in generalization between different subgroups likely stems from the imbalanced nature of the dataset, it would be interesting to see comparison against methods from the imbalanced learning literature (not only the single method from fairness literature).\n\nMinor point:\n- Most references have double parentheses.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster