# FIFA: Making Fairness More Generalizable in Classifiers Trained on
Imbalanced Data

Zhun Deng Corresponding authors<EMAIL_ADDRESS><EMAIL_ADDRESS>Harvard University  Jiayao Zhang  University of Pennsylvania  Linjun Zhang
Rutgers University  Ting Ye  University of Washington  Yates Coley  University
of Washington  Kaiser Permanente Washington Health Research Institute  Weijie
J. Su  University of Pennsylvania  James Zou  Stanford University

###### 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 Flexible approach that is Imbalance-Fairness-
Aware (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.

##  1 Introduction

Figure 1: Each marker corresponds to a sufficiently well-trained ResNet-10
model trained on an imbalanced image classification dataset CelebA ([44]). The
generalization of fairness constraints (EO) is of magnitudes poorer compared
that onclassification error.

Machine learning systems are becoming increasingly vital in our daily lives.
The growing concern that they may inadvertently discriminate against
minorities and other protected groups when identifying or allocating resources
has attracted numerous attention from various communities both inside and
outside academia. While significant efforts have been devoted in understanding
and correcting biases in classical models such as logistic regressions and
supported vector machines (SVM), see, e.g., [1, 29], those derived tools are
far less effective on modern over-parameterized models such as neural networks
(NN). Over-parameterization can lead to poor generalization, as extensive
efforts in both theoretical and empirical studies have exhibited ([62, 50,
4]). Furthermore, in large models, it is also difficult for _measures of
fairness_ (such as equalized odds to be introduced shortly) to generalize, as
shown in Fig. 1. Here we find that sufficiently trained ResNet-10 models
generalize well on classification error but poorly on fairness constraints—the
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.

Figure 2: The subgroups (sensitive attribute, either Male or Female, and label
class, either + or \--) are very imbalanced in many popular datasets across
different domains.

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 [10, 47, 30, 2, 31, 40], it’s unclear how
well fairness properties generalize. It is also an open challenge how to
improve the generalization of fairness in over-parameterized models.

##### Our contributions.

In this paper, we initiate the study for this open challenge of fairness
generalization for supervised classification tasks in imbalanced datasets.
Inspired by recent works on regularizing the minority classes more strongly
than the frequent classes by imposing class-dependent margins [10] in standard
supervised learning, we design a theoretically-principled, Flexible and
Imbalance-Fairness-Aware (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 methods
with logits-based losses such as the soft margin loss [43] by encouraging
larger margins for minority subgroups. While our method appears to be
motivated for over-parameterized models such as neural networks, it
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.

##### Related work.

Over-parameterized models such as neural network has achieved great
performance in modern learning, however, the nature of optimization [17, 22,
34, 33, 36, 64], robustness [18, 21, 19], and generalization [19, 20, 63, 57,
58] of neural networks remains mysterious. Even worse, the inherent imbalance
in certain label classes bring great trouble for neural networks to generalize
in supervised learning, which has attracted significant interest in the
machine learning communities. Several methods including resampling,
reweighting, and data augmentation have been developed and deployed in
practice [47, 30, 2, 31, 40, 11, 28, 51, 56, 16, 9]. Theoretical analyses of
those methods include margin-based approaches [42, 35, 37, 10]. Somewhat
tangentially, an outstanding and emerging problem faced by modern models with
real-world data is _algorithmic fairness_ [25, 3, 14, 54, 45, 49, 13, 8],
where practical algorithms are developed for pre-processing [27], in-
processing [61, 26, 59, 23, 46, 48, 41], and post-processing [29, 38, 12]
steps. Nonetheless, there are several challenges when applying fairness
algorithms in practice [5, 52, 32, 45]. Specifically, as hinted in Fig. 1, the
fairness generalization guarantee, especially in over-parameterized models and
large datasets, is not well-understood, leading to various practical concerns.
We remark that although [39] 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. In another closely related work, [15], classical learning theory is
being studied without addressing issues raised by imbalanced data. To the best
of our knowledge, this is the first work tackling the open challenge of
fairness generalization with imbalanced data.

##  2 Background

##### Notation.

For any $k\in\mathbb{N}^{+}$, we use $[k]$ to denote the set
$\\{1,2,\cdots,k\\}$. For a vector $v$, let $v_{i}$ be the $i$-th coordinate
of $v$. We use $\bm{1}$ to denote the indicator function. For a set $S$, we
use $|S|$ to denote the cardinality of $S$. For two positive sequences
$\\{a_{k}\\}$ and $\\{b_{k}\\}$, we write $a_{k}=O(b_{k})$ (or $a_{n}\lesssim
b_{n}$), and $a_{k}=o(b_{k})$, if
$\lim_{k\rightarrow\infty}(a_{k}/b_{k})<\infty$ and
$\lim_{k\rightarrow\infty}(a_{k}/b_{k})=0$, respectively. We use $\mathbb{P}$
for probability and $\mathbb{E}$ for expectation, and we use
$\hat{\mathbb{P}}$ and $\hat{\mathbb{E}}$ for empirical probability and
expectation. For the two distributions ${\mathcal{D}}_{1}$ and
${\mathcal{D}}_{2}$, we use $p{\mathcal{D}}_{1}+(1-p){\mathcal{D}}_{2}$ for
$p\in(0,1)$ to denote the mixture distribution such that a sample is drawn
with probabilities $p$ and $(1-p)$ from ${\mathcal{D}}_{1}$ and
${\mathcal{D}}_{2}$ respectively. We use ${\mathcal{N}}_{p}(\mu,\Sigma)$ to
denote $p$-dimensional Gaussian distribution with mean $\mu$ and variance
$\Sigma$.

##### Fairness notions.

Throughout the paper, we consider datasets consisting of triplets of the form
$(x,y,a)$, where $x\in{\mathcal{X}}$ is a feature vector, $a\in{\mathcal{A}}$
is a sensitive attribute such as race and gender, and $y\in{\mathcal{Y}}$ is
the corresponding label. The underlying random triplets corresponding to
$(x,y,a)$ is denoted as $(X,Y,A)$. Our goal is to learn a predictor
$h\in{\mathcal{H}}:{\mathcal{X}}\mapsto{\mathcal{Y}}$, where $h(X)$ is a
prediction of the label $Y$ of input $X$. In this paper, we mainly consider
equalized odds (EO) [29] 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. Specifically, the notions mentioned above
are defined as follows.

  * (i).

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$:
$\mathbb{P}(h(X)=y|Y=y,A=a)=\mathbb{P}(h(X)=y|Y=y).$ If
${\mathcal{Y}}=\\{0,1\\}$ and we only require
$\mathbb{P}(h(X)=1|Y=1,A=a)=\mathbb{P}(h(X)=1|Y=1),$ we say $h$ satisfies
equalized opportunity.

  * (ii).

Demographic parity (DP). A predictor $h$ satisfies demographic parity if
$h(X)$ is statistically independent of the sensitive attribute $A$:
$\mathbb{P}(h(X)=Y|A=a)=\mathbb{P}(h(X)=Y).$

##  3 Theory-inspired derivation

While we will formally introduce our new approach in Section 4, this section
gives an informal derivation, with an emphasis on insights. We design an
imbalance-fairness-aware approach that can be flexibly combined with fair
learning methods with logits-based losses.

Consider the supervised $k$-class classification problem, where a model
$f:{\mathcal{X}}\mapsto{\mathbb{R}}^{k}$ provides $k$ scores, and the label is
assigned as the class label with the highest score. The corresponding
predictor $h(x)=\operatorname*{arg\,max}_{i}f(x)_{i}$ if there are no ties.
Let us use ${\mathcal{P}}_{i}={\mathcal{P}}(X|Y=i)$ to denote the conditional
distribution when the class label is $i$ for $i\in[k]$ and
${\mathcal{P}}_{\text{bal}}$ to denote the balanced distribution
${\mathcal{P}}_{\text{Idx}}$, where Idx is uniformly drawn from $[k]$.
Similarly, let us use ${\mathcal{P}}_{i,s}={\mathcal{P}}(X|Y=i,A=s)$ to denote
the conditional distribution when $Y=i$ and $A=s$. The corresponding empirical
distributions induced by the training data are $\hat{\mathcal{P}}_{i}$,
$\hat{\mathcal{P}}_{\text{bal}}$ and $\hat{\mathcal{P}}_{i,s}$. For the
training dataset $\\{(x_{j},y_{j},a_{j})\\}_{j}$, let $S_{i}=\\{j:y_{j}=i\\}$,
$S_{i,a}=\\{j:y_{j}=i,a_{j}=a\\}$, and the corresponding sample sizes be
$n_{i}$ and $n_{i,a}$, respectively. Although ${\mathcal{P}}_{i}$,
${\mathcal{P}}_{\text{bal}}$ and ${\mathcal{P}}_{i,s}$ are all distributions
on ${\mathcal{X}}$, we sometimes use notations like
$(x,y)\sim{\mathcal{P}}_{i}$ to denote the distribution of $(x,i)$, where
$x\sim{\mathcal{P}}_{i}$ . Our goal is to ensure
${\mathcal{L}}_{\text{bal}}[f]=\mathbb{P}_{(x,y)\sim{\mathcal{P}}_{\text{bal}}}[f(x)_{y}<\max_{l\neq
y}f(x)_{l}]$ and 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.

##### Margin trade-off between classes of equalized odds.

In the setting of standard classification with imbalanced training datasets
such as in [10, 51], the aim is to reach a small balanced test error
${\mathcal{L}}_{\text{bal}}[f]$. However, in a fair classification setting,
our aim is not only to reach a small ${\mathcal{L}}_{\text{bal}}[f]$, but also
to satisfy certain fairness constraints at test time. Specifically, for EO,
the aim is:

$\displaystyle\min_{f}{\mathcal{L}}_{\text{bal}}[f]$
$\displaystyle\text{s.t.}~{}\forall
y\in{\mathcal{Y}},a\in{\mathcal{A}},~{}~{}\mathbb{P}(h(X)$
$\displaystyle=y|Y=y,A=a)=\mathbb{P}(h(X)=y|Y=y),$

where we recall that $h(\cdot)=\operatorname*{arg\,max}_{i}f(\cdot)_{i}$. We
remark here that in addition to the class-balanced loss
${\mathcal{L}}_{\text{bal}}[f]$, we can also consider the loss function that
is balanced across all demographic subgroups in different classes, the
derivation is similar and we omit it here.

Recall our motivating example in Figure 1. Whether the fairness violation
error is small at test time should also be taken into account. Thus, our
performance criterion for optimization should be:

${\mathcal{L}}_{\text{bal}}[f]+\alpha{\mathcal{L}}_{\text{fv}},$ (1)

where ${\mathcal{L}}_{\text{fv}}$ is a measure of fairness constraints
violation that we will specify later, and $\alpha$ is a weight parameter
chosen according to how much we care about the fairness constraints violation.

For simplicity, we start with ${\mathcal{Y}}=\\{0,1\\}$ and
${\mathcal{A}}=\\{a_{1},a_{2}\\}$. In the Appendix, we will further discuss
the case when there are multiple classes and multiple demographic groups. We
also 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 [10] and can be satisfied if the model class is
rich, for instance, for over-parameterized models such as neural networks.
Specifically, if all the training samples are classified perfectly by $h$, not
only $\mathbb{P}_{(x,y)\sim\hat{\mathcal{P}}_{\text{bal}}}(h(x)\neq y)=0$ is
satisfied, we also have that
$\mathbb{P}_{(x,y)\sim\hat{{\mathcal{P}}}_{i,a_{j}}}(h(x)\neq y)=0$ for all
$i\in{\mathcal{Y}}$ and $a_{j}\in{\mathcal{A}}$. We remark here that
$\mathbb{P}(h(X)=i|Y=i,A=a)=1-\mathbb{P}_{(x,y)\sim{\mathcal{P}}_{i,a}}(h(x)\neq
y)$. Denote the margin for class $i$ by $\gamma_{i}=\min_{j\in
S_{i}}\gamma(x_{j},y_{j})$, where $\gamma(x,y)=f(x)_{y}-\max_{l\neq
y}f(x)_{l}$. One natural way to choose ${\mathcal{L}}_{\text{fv}}$ is to take
$\sum_{i\in{\mathcal{Y}}}|\mathbb{P}(h(X)=i|Y=i,A=a_{1})-\mathbb{P}(h(X)=i|Y=i,A=a_{2})|.$
Then, our performance criterion for optimization in (A.4) is:

${\mathcal{M}}[f]={\mathcal{L}}_{\text{bal}}[f]+\alpha\sum_{i\in{\mathcal{Y}}}\left|\mathbb{P}(h(X)=i|Y=i,A=a_{1})-\mathbb{P}(h(X)=i|Y=i,A=a_{2})\right|.$

By a similar margin-based generalization arguments in [10, 35], we proved the
following theorem.

######  Theorem 3.1 (Informal)

With high probability over the randomness of the training data, for
${\mathcal{Y}}=\\{0,1\\}$, ${\mathcal{A}}=\\{a_{1},a_{2}\\}$, and for some
proper complexity measure of class ${\mathcal{F}}$, for any
$f\in{\mathcal{F}}$,

$\displaystyle\begin{split}{\mathcal{M}}[f]\lesssim\sum_{i\in{\mathcal{Y}}}\frac{1}{\gamma_{i}}\sqrt{\frac{C({\mathcal{F}})}{n_{i}}}+\sum_{i\in{\mathcal{Y}},a\in{\mathcal{A}}}\frac{\alpha}{\gamma_{i,a}}\sqrt{\frac{C({\mathcal{F}})}{n_{i,a}}}\leq\sum_{i\in{\mathcal{Y}}}\frac{1}{\gamma_{i}}\sqrt{\frac{C({\mathcal{F}})}{n_{i}}}+\sum_{i\in{\mathcal{Y}},a\in{\mathcal{A}}}\frac{\alpha}{\gamma_{i}}\sqrt{\frac{C({\mathcal{F}})}{n_{i,a}}},\end{split}$
(2)

where $\gamma_{i}$ is the margin of the $i$-th class’s sample set $S_{i}$ and
$\gamma_{i,a}$ is the margin of demographic subgroup’s sample set $S_{i,a}$.

Optimizing the upper bound in (A.5) with respect to margins in the sense that
$g(\gamma_{0},\gamma_{1})\leq g(\gamma_{0}-\delta,\gamma_{1}+\delta)$ for
$g(\gamma_{0},\gamma_{1})=\sum_{i\in{\mathcal{Y}}}\frac{1}{\gamma_{i}\sqrt{n_{i}}}+\alpha\sum_{i\in{\mathcal{Y}},a\in{\mathcal{A}}}\frac{1}{\gamma_{i}\sqrt{n_{i,a}}}$
and all $\delta\in[-\gamma_{1},\gamma_{0}]$, we obtain

$\gamma_{0}/\gamma_{1}=\tilde{n}_{0}^{-1/4}/\tilde{n}_{1}^{-1/4},$

where the adjusted sample size

$\tilde{n}_{i}=\frac{n_{i}\Pi_{a\in{\mathcal{A}}}n_{i,a}}{(\sqrt{\Pi_{a\in{\mathcal{A}}}n_{i,a}}+\alpha\sum_{a\in{\mathcal{A}}}\sqrt{n_{i}n_{i,a}})^{2}}$

for $i\in\\{0,1\\}$. From Theorem 3.1, 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 [10],
but their focus is only on the classification error 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 $\alpha=0$, and the effective sample
sizes degenerate to $\tilde{n}_{i}=n_{i}$.

For illustration, we demonstrate the advantage of applying our approach to
select margins over directly using the margin selection in [10] by considering
Gaussian models, which is widely used in machine learning theory [53, 64, 21].
Specifically, our training data follow distribution: $x\mid
y=0\sim\sum_{i=1}^{2}\pi_{0,a_{i}}{\mathcal{N}}_{p}(\mu_{i},I),~{}~{}x\mid
y=1\sim\sum_{i=1}^{2}\pi_{1,a_{i}}{\mathcal{N}}_{p}(\mu_{i}+\beta^{*},I).$
Here, in class $j$, subgroup $a_{i}$ is drawn with probability
$\pi_{j,a_{i}}$, then, given the sample is from subgroup $a_{i}$ in class $j$,
the data is distributed as a Gaussian random vector. Recall the corresponding
training dataset indices of subgroup $a_{i}$ in class $j$ is denoted as
$S_{j,a_{i}}$, and $|S_{j,a_{i}}|=n_{j,a_{i}}$. Consider the case $\alpha=1$ ,
$\pi_{0,a_{1}}=\pi_{0,a_{2}}$, and the following class of classifiers:
$\mathcal{F}=\Big{\\{}\bm{1}\\{\beta^{*\top}x>c\\}:c\in\mathbb{R}\Big{\\}},$
which is a 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$, let $\operatorname{dist}(f,S)=\min_{x,s\in
S}\|f(x)-s\|_{2}.$ Consider two classifiers $\tilde{f},f\in{\mathcal{F}}$ such
that

$\operatorname{dist}(\tilde{f},S_{0})/\operatorname{dist}(\tilde{f},S_{1})=\tilde{n}_{0}^{-1/4}/\tilde{n}_{1}^{-1/4}$

and
$\operatorname{dist}(f^{\prime},S_{0})/\operatorname{dist}(f^{\prime},S_{1})=n_{0}^{-1/4}/n_{1}^{-1/4}$.
Suppose $\|\beta^{*}\|\gg\sqrt{p\log n}$, $\|\mu_{i}\|<C$,
$(\mu_{1}^{*}-\mu_{2}^{*})^{\top}\beta=0$, and $\pi_{1,a_{2}}\leq
c_{1}\pi_{1,a_{1}}$ for a sufficiently small $c_{1}>0$, then when
$n_{0},n_{1}$ are sufficiently large, with high probability we have
${\mathcal{M}}[\tilde{f}]<{\mathcal{M}}[f].$

###### Remark 3.1

(1). 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 use surrogates such as the softmax-cross-entropy loss for the
$0$-$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. (2). Our analysis can be readily applied to EqOpt and
DP constraints under certain conditions. We provide analyses and experiments
for DP in the Appendix.

##  4 Flexible combination with logits-based losses

Figure 3: Illustration of $\delta_{i,a}$ and the margin $\gamma$ of
classifier: $\delta_{1,a_{1}}$ is set to be non-negative and
$\delta_{1,a_{2}}$ is set to be zero as the subgroup $(1,a_{2})$ is closer to
the decision boundary than $(1,a_{1})$.

For ease of exposition, we focus solely on the EO constraint hereafter and
discuss other constraints in the Appendix. Inspired by the margin trade-off
characterized in Section 3, we propose our FIFA approach for Flexible
Imbalance-Fairness-Aware classification that can be easily combined with
different types of logits-based losses, and further incorporated into any
existing fairness algorithms such as those discussed in Section 5.

Let us recall that in Theorem 3.1, $\gamma_{i,a}=\gamma_{i}+\delta_{i,a}$ and
$\delta_{i,a}\geq 0$ (since
$\gamma_{i}=\min\\{\gamma_{i,a_{1}},\gamma_{i,a_{2}}\\}$, also see Fig. 3 for
illustration), hence the middle term of Eq. (3) can be further upper bounded
by the last term in Eq. (A.5). The final upper bound in Eq. (A.5) 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. Specifically, in Section 3, we have
identified a way to select $\gamma_{0}/\gamma_{1}$, based on which we propose
to enforce margins for each demographic subgroup’s training set $S_{i,a}$ of
the form

$\gamma_{i,a}=\frac{C}{\tilde{n}_{i}^{1/4}}+\delta_{i,a},$ (3)

where $\delta_{i,a}$ and $C$ are all non-negative tuning parameters. In light
of the trade-off between the class margins
$\gamma_{0}/\gamma_{1}=\tilde{n}_{0}^{-1/4}/\tilde{n}_{1}^{-1/4}$, we can set
$\gamma_{i}$ of the form $C/\tilde{n}_{i}^{-1/4}$. Given
$\gamma_{i,a}\geq\gamma_{i}$, a natural choice for margins for subgroups is
Eq. (3).

##### How to select $\delta_{i,a}$?

Knowing the form of margins from the preceding discussions, an outstanding
question remains: how to select $\delta_{i,a}$ for imbalanced datasets? Let
${\mathcal{Y}}=\\{0,1\\}$ and ${\mathcal{A}}=\\{a_{1},a_{2}\\}$, within each
class $i$, we identify $S_{i,a}$ with the largest cardinality $|S_{i,a}|$ and
set the corresponding $\delta_{i,a}=0$. The remaining
$\delta_{i,{\mathcal{A}}\backslash a}$ are tuned as a non-negative parameter.
As a further illustration, without loss of generality, assume for all $i$,
$|S_{i,a_{1}}|\geq|S_{i,a_{2}}|$. Thus selected $\\{\delta_{i,a}\\}_{i,a}$
ensures the upper bound in the middle of Eq. (A.5) is tighter in the sense
that for any $\delta>0$,

$\sum_{i\in{\mathcal{Y}}}\Big{(}\frac{1}{\gamma_{i}\sqrt{n_{i,a_{1}}}}+\frac{1}{(\gamma_{i}+\delta)\sqrt{n_{i,a_{2}}}}\Big{)}\leq\sum_{i\in{\mathcal{Y}}}\Big{(}\frac{1}{(\gamma_{i}+\delta)\sqrt{n_{i,a_{1}}}}+\frac{1}{\gamma_{i}\sqrt{n_{i,a_{2}}}}\Big{)}.$

In the Appendix, we will present how to choose $\delta_{i,a}$’s when there are
multiple demographic groups. Briefly speaking, our results similar to the
above inequality are proved by an application of the 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-frequent subgroup
than the more-frequent subgroup to ensure better fairness generalization.

##### Flexible imbalance-fairness-aware (FIFA) approach.

We will demonstrate how to apply the above motivations to design better margin
losses. Loosely speaking, we consider a logits-based loss

$\ell((x,y);f)=\ell(f(x)_{y},\\{f(x)_{i}\\}_{i\in{\mathcal{Y}}\backslash y}),$

which is non-increasing with respect to its first coordinate if we fix the
second coordinate. Such losses include (i). $0$-$1$ loss:
$\bm{1}\\{f(x)_{y}<\max_{i\in{\mathcal{Y}}\backslash y}f(x)_{i}\\}$. (ii).
Hinge loss: $\max\\{\max_{i\in{\mathcal{Y}}\backslash
y}f(x)_{i}-f(x)_{y},0\\}$. (iii). Softmax-cross-entropy loss: $-\log
e^{f(x)_{y}}/(e^{f(x)_{y}}+\sum_{i\neq y}e^{f(x)_{i}})$.

Our flexible imbalance-fairness-aware (FIFA) approach modifies the above
losses by enforcing margin of the form in Eq. (3). Specifically, we use the
following loss function during training

$\ell_{\text{FIFA}}((x,y,a);f)=\ell(f(x)_{y}-\Delta_{y,a},\\{f(x)_{i}\\}_{i\in{\mathcal{Y}}\backslash
y})$ (4)

where $\Delta_{i,a}=C/\tilde{n}_{i}^{1/4}+\delta_{i,a}$. We remark here
$\ell_{\text{FIFA}}((x,y,a);f)$ is used only during training phase, where we
allow access to sensitive attribute $a$. In the test time, we only need to use
$f$ but not $a$.

##  5 Example: combining FIFA with reductions-based fair algorithms

In this section, we demonstrate the power of our approach by combining it with
a popular reduction-based fair classification algorithm [1] as an example. In
Section 6, we show that incorporating our approach 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 proposed in [1] has two versions: (i).
Exponentiated gradient (ExpGrad) that produces a randomized classifier; and
(ii). Grid search (GridS) that produces a deterministic classifier. Our
approach can be combined with both.

##### Exponentiated gradient (ExpGrad).

We first briefly describe the algorithm here. For ${\mathcal{Y}}=\\{0,1\\}$,
by [1], EO constraints could be rewritten as $M\mu(h)\leq c$ for certain $M$
and $c$, where $\mu_{j}(h)=\mathbb{E}[h(X)|E_{j}]$ for $j\in\mathcal{J}$,
$M\in{\mathbb{R}}^{|{\mathcal{K}}|\times|\mathcal{J}|}$, and
$c\in{\mathbb{R}}^{{\mathcal{K}}}$. Here,
${\mathcal{K}}={\mathcal{A}}\times{\mathcal{Y}}\times\\{+,-\\}$ ($+,-$ impose
positive/negative sign so as to recover $|\cdot|$ in constraints) and
$\mathcal{J}=({\mathcal{A}}\cup\\{*\\})\times\\{0,1\\}$.
$E_{(a,y)}=\\{A=a,Y=y\\}$ and $E_{(*,y)}=\\{Y=y\\}$. Let
$\operatorname{err}(h)=\mathbb{P}(h(X)\neq Y)$, instead of considering
$\min_{h\in{\mathcal{H}}}\operatorname{err}(h)$ such that $M\mu(h)\leq c$,
ExpGrad obtains the best _randomized classifier_ , by sampling a classifier
$h\in{\mathcal{H}}$ from a distribution over ${\mathcal{H}}$. Formally, this
optimization can be formulated as

$\min_{Q\in\Delta_{{\mathcal{H}}}}\operatorname{err}(Q)~{}~{}\text{such
that}~{}~{}M\mu(Q)\leq c,$

where

$\operatorname{err}(Q)=\sum_{h\in{\mathcal{H}}}Q(h)\operatorname{err}(h),$

and $\mu(Q)=\sum_{h\in{\mathcal{H}}}Q(h)\mu(h)$, $Q$ is a distribution over
${\mathcal{H}}$, and $\Delta_{\mathcal{H}}$ is the collection of distributions
on ${\mathcal{H}}$. Let us further use $\widehat{\operatorname{err}}(Q)$ and
$\hat{\mu}(Q)$ to denote the empirical versions and also allows relaxation on
constraints by using $\hat{c}=c+\epsilon$, where
$\hat{c}_{k}=c_{k}+\epsilon_{k}$ for relaxation $\varepsilon_{k}\geq 0$. By
classic optimization theory, it could be transferred to a saddle point
problem, and [1] aims to solve the following prime dual problems
simultaneously for
$L(Q,\lambda)=\widehat{\operatorname{err}}(Q)+\lambda^{\top}(M\hat{\mu}(Q)-\hat{c})$:

$\displaystyle(\textbf{P}):~{}\min_{Q\in\Delta}\max_{\lambda\in{\mathbb{R}}^{|{\mathcal{K}}|}_{+},\|\lambda\|_{1}\leq
B}L(Q,\lambda),\qquad(\textbf{D}):~{}\max_{\lambda\in{\mathbb{R}}^{|{\mathcal{K}}|}_{+},\|\lambda\|_{1}\leq
B}\min_{Q\in\Delta}L(Q,\lambda).$

To summarize, ExpGrad takes training data
$\\{(x_{i},y_{i},a_{i})\\}_{i=1}^{n}$, function class ${\mathcal{H}}$,
constraint parameters $M,\hat{c}$, bound $B$, accuracy tolerance $v>0$, and
learning rate $\eta$ as inputs and outputs $(\hat{Q},\hat{\lambda})$, such
that $L(\hat{Q},\hat{\lambda})\leq L(Q,\hat{\lambda})+\nu$ for all
$Q\in\Delta_{\mathcal{H}}$ and $L(\hat{Q},\hat{\lambda})\leq
L(\hat{Q},\lambda)-\nu$ for all
$\lambda\in{\mathbb{R}}^{|{\mathcal{K}}|}_{+},\|\lambda\|_{1}\leq B$, and
$(\hat{Q},\hat{\lambda})$ is called a $\nu$-approximate saddle point. As
implemented in [1], ${\mathcal{H}}$ roughly consists of
$h(x)=\bm{1}\\{f(x)_{1}\geq f(x)_{0}\\}$ for $f\in{\mathcal{F}}$ (in fact, a
smoothed version is considered in [1]) and gives

$\widehat{\operatorname{err}}(Q)=\sum_{h\in{\mathcal{H}}}\hat{\mathbb{P}}(h(X)\neq
Y)Q(h)=\hat{\mathbb{P}}(f(X)_{Y}<f(X)_{\\{0,1\\}\backslash Y})Q(h).$

To combine our approach, we consider optimizing

$\widehat{\operatorname{err}}^{\text{new}}(Q)=\sum_{h\in{\mathcal{H}}}\hat{\mathbb{P}}(f(X)_{Y}-\Delta_{Y,A}\leq
f(X)_{\\{0,1\\}\backslash Y})Q(h),$

such that $M\hat{\mu}^{\text{new}}(Q)\leq\hat{c}$, where
$\hat{\mu}^{\text{new}}(Q)=\sum_{h\in{\mathcal{H}}}Q(h)\hat{\mu}^{\text{new}}(f)$
and
$\hat{\mu}^{\text{new}}_{j}(f)=\hat{\mathbb{P}}(f(X)_{Y}-\Delta_{Y,A}>f(X)_{\\{0,1\\}\backslash
Y}|E_{j})$. We can modify ExpGrad to optimize prime dual problems
simultaneously for

$L^{\text{new}}(Q,\lambda)=\widehat{\operatorname{err}}^{\text{new}}(Q)+\lambda^{\top}(M\hat{\mu}^{\text{new}}(Q)-\hat{c}).$

In practice, while Section 3 is motivated for deterministic classifiers, FIFA
works for the randomized version too – the modified ExpGrad can be viewed as
encouraging a 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.

Algorithm 1 FIFA Combined Grid Search

0: fairness algorithm GridS, training data set
$\\{x_{i},y_{i},a_{i}\\}_{i=1}^{n}$, fairness tolerance $\epsilon$, margins
$\\{\Delta_{y,a}\\}_{y,a}$, a classifier $h(\cdot;\theta)$.

0: the learnt classifier $h^{*}$.

1: Load training data to GridS.

2: GridS produces a set of reduction-labels $\hat{y}_{\text{train}}$ and a set
of sample weights $w_{\text{train}}$ based on the type of fairness constraint
and tolerance $\epsilon$.

3: for $t=1,2,\ldots,T$ do

4: Compute the FIFA loss $\ell_{\text{FIFA}}$ via (4) using reduction-labels
$\hat{y}_{\text{train}}$ (in mini-batches).

5: Update $\theta$ in $h$ using back-propagation.

6: Logging training metrics using true labels $\\{y_{i}\\}_{i=1}^{n}$ and
attributes $\\{a_{i}\\}_{i=1}^{n}$.

7: end for

###### Theorem 5.1

Let $\rho=\max_{f}\|M\hat{\mu}^{\text{new}}(f)-\hat{c}\|_{\infty}$. For
$\eta=\nu/(2\rho^{2}B)$, the modified ExpGrad will return a $\nu$-approximate
saddle point of $L^{\text{new}}$ in at most
$4\rho^{2}B^{2}\log(|{\mathcal{K}}|+1)/\nu^{2}$ 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 $\lambda$
vectors to identify the _deterministic classifier_ that attains the best
trade-off between accuracy and fairness. In practice, GridS is preferred for
larger models due to 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-parameterized models. We describe our flexible
approach in Algorithm 1 that combines with GridS used in practice in the
official code base FairLearn ([7]).

###### Remark 5.1

As we stated, the above algorithm is just one of the examples that can be
combined with our approach. FIFA can also be applied to many other popular
algorithms such as fair representation [46] and decision boundary approach
[60]. We will discuss them in more detail in the Appendix.

##  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 [1] 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 a 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 ([44]): the task is to predict whether the person
in the image has blond hair or not where the sensitive attribute is the gender
of the person. (ii). AdultIncome ([24]): the task is to predict whether the
income is above $50$K per year, where the sensitive attribute is the gender.
(iii). DutchConsensus ([55]): the task is predict whether an individual has a
prestigious occupation and the sensitive attribute is the gender. Both
AdultIncome and DutchConsensus datasets are also used in [1].

Figure 4: Histogram (cumulative density) of hyper-parameter $C$ in the sweeps
for FIFA and LDAM. Vertical lines mark the values corresponding to the best
performing models in Table 1.

##### 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 $\delta_{i,a}$, we
also treat $\alpha$ as tuning parameters (in Eq. (A.5)). We then perform
hyper-parameter sweeps on the grids (if used) over $C$, $\delta_{i,a}$ and
$\alpha$ for FIFA, and grids (if used) for vanilla training (combine fairness
algorithms with the vanilla softmax-cross-entropy loss). The sweeps are done
on the wandb platform [6], 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 a 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. More details are included in the Appendix.
We compare FIFA with directly applying fair algorithms to NN’s trained with
softmax-cross-entropy loss, which is the most natural baseline. Also as a
special case of FIFA, when $\delta_{i,a}=0$ for all $i,a$ and $\alpha=0$ the
FIFA loss degenerates to the LDAM loss proposed in [10] that is not as
fairness-aware as FIFA, so we briefly discuss it in Table 1 too. FIFA further
finetunes $\delta_{i,a}$ and $\alpha$, and to ensure a fair comparison, we set
the same coverage for the the common hyper-parameter $C$ in the sweeps, as
shown in Fig. 4.

##### 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 violation and balanced error. We define the combined loss as
${\mathcal{L}}_{\text{cb}}[f]=\frac{1}{2}{\mathcal{L}}_{\text{bal}}[f]+\frac{1}{2}{\mathcal{L}}_{\text{fv}}[f]$,
which favors those classifiers that have a equally well-performance in terms
of classification and fairness. We consider both the value of the combined
loss evaluated on the test set ${\mathcal{S}}_{\text{test}}$, and the
_generalization gap_ for a loss ${\mathcal{L}}$ is defined as
$\operatorname{gap}[{\mathcal{L}},f]=\left\lvert{\mathcal{L}}[f]({\mathcal{S}}_{\text{test}})-{\mathcal{L}}[f]({\mathcal{S}}_{\text{train}})\right\rvert.$

###  6.1 Effectiveness of FIFA on over-parameterized models

Fairness Tolerance $\epsilon$ | 0.01 | 0.05 | 0.10
---|---|---|---
Method | FIFA | LDAM | Vanilla | FIFA | LDAM | Vanilla | FIFA | LDAM | Vanilla
Combined Loss | Train | 7.37% | 5.22% | 7.14% | 5.46% | 5.47% | 8.84% | 5.92% | 8.48% | 8.90%
Test | 6.71% | 7.29% | 14.01% | 6.34% | 7.38% | 13.05% | 6.54% | 7.34% | 16.71%
Gap | 0.66% | 2.07% | 6.87% | 0.88% | 1.91% | 4.21% | 0.62% | 1.14% | 7.82%
Fairness Violation | Train | 5.31% | 2.32% | 6.69% | 2.63% | 2.57% | 9.45% | 3.11% | 6.93% | 11.37%
Test | 2.75% | 5.39% | 20.29% | 3.29% | 5.57% | 17.92% | 2.65% | 2.96% | 26.15%
Gap | 2.57% | 3.07% | 13.59% | 0.66% | 3.00% | 8.47% | 0.46% | 3.97% | 14.78%

Table 1: Grid search with EO constraint on CelebA dataset [44] using
ResNet-18, best results with respect to test combined loss among sweeps of
hyper-parameters are shown. As an interesting special case of our FIFA method,
we note that although the LDAM method improves the performance compared with
vanilla GS, it is not as effective as our method.

(a) ${\mathcal{L}}_{\text{cb}}[f]({\mathcal{S}}_{\text{test}})$.

(b) ${\mathcal{L}}_{\text{fv}}[f]({\mathcal{S}}_{\text{test}})$.

(c) $\widehat{\operatorname{gap}}[{\mathcal{L}}_{\text{cb}},f]$.

(d) $\widehat{\operatorname{gap}}[{\mathcal{L}}_{\text{fv}},f]$.

Figure 5: Loss on test set (5(a),5(b)) and generalization gaps (5(c),5(d)) of
the combined loss and the fairness loss on CelebA dataset. We repeat the
experiment for $20$ times using the hyper-parameters corresponding to the
best-performing models in Table 1. Solid blue line marks the grid search
combined with vanilla training whereas dashed orange line marks grid search
combined with the FIFA loss. We also plot $95\%$ confidence band based on $20$
repeated runs. We observe that our method FIFA has significantly better
generalization performance in terms of both smaller losses on the test set as
well as narrower generalization gaps.

In this subsection, we thoroughly analyze the results from applying FIFA to
over-parameterized models for the CelebA dataset using ResNet-18. We use the
grid search algorithm with fairness violation tolerance parameter
$\epsilon\in\\{0.01,0.05,0.1\\}$ (with a little abuse of notation) for all
constraints. We perform sweeps on hyper-parameters $C\in[0,0.01]$,
$\alpha\in[0,0.01]$,
$\delta_{0,\text{Male}},\delta_{1,\text{Male}}\in[0,0.01]$, and
$\delta_{0,\text{Female}}=\delta_{1,\text{Female}}=0$. As a special case that
may be of interest, when $\alpha=0$ and
$\delta_{0,\text{Male}}=\delta_{1,\text{Male}}=0$, the FIFA loss coincides
with the LDAM loss proposed in [24], with one common hyper-parameter
$C\in[0,0.01]$. We log the losses on the whole training and test set. We
summarize our main findings below and give more details in the Appendix
including experiments with DP constraints, delayed-reweighting (DRW, [10]),
and reweighting methods.

##### Logits-based methods improve fairness generalization.

We summarize the best results for each method under different tolerance
parameter $\epsilon$ in Table 1. We note that both FIFA and LDAM significantly
improve the test performance of both combined loss and fairness violation
among all three choices of $\epsilon$, while having comparable training
performance This implies the effectiveness and necessity of using logits-based
methods to ensure a better fairness generalization.

##### FIFA accommodates for both fairness generalization and dataset
imbalance.

Although both logits-based method improve generalization as seen in Table 1,
our method FIFA has significantly better generalization performance compared
with LDAM, especially in terms of fairness violation. For example, when
$\epsilon=0.01$ and $0.05$, FIFA achieves a 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 gap
between the training and test set. We compute the generalization gap in Table
1 for both combined loss and fairness violation. We observe that FIFA
generally dominates LDAM and vanilla in terms of both test performance and
generalization gap. We further illustrate this behavior in Fig. 5, 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 are mostly due to better fairness
generalization. In fact, as suggested by the similarity in the shapes of
curves between Fig. 5(c) and Fig. 5(d), fairness generalization dominates
classification generalization, and thus improvements in fairness
generalization elicit more prominently overall.

##### Towards a more efficient Pareto frontier.

Let us recall our motivating example in Fig. 1 where a sufficiently well-
trained ResNet-10 demonstrate stellar classification and fairness performance
on the training set but poor fairness generalization on the test set. In Fig.
6 we plot the Pareto frontier of balanced classification error
(${\mathcal{L}}_{\text{bal}}$) and fairness violation
(${\mathcal{L}}_{\text{fv}}$) for all three choices of $\epsilon$. We observe
that the models trained by combining grid search with the FIFA loss achieve
frontiers that are lower and more centered compared with those trained in
vanilla losses with grid search. This reaffirms that our FIFA approach
mitigates the fairness generalization problem decently well.

Dataset | AdultIncome | DutchConsensus
---|---|---
Metric | Combined Loss | Fairness Violation | Combined Loss | Fairness Violation
$\epsilon$ | Method | Train | Test | Train | Test | Train | Test | Train | Test
0.01 | FIFA | 15.7217% | 13.4812% | 7.8863% | 2.7776% | 12.8013% | 13.1686% | 3.7220% | 4.3532%
Vanilla | 13.9561% | 14.3001% | 6.7861% | 6.7475% | 12.8444% | 13.2267% | 3.7935% | 4.4323%
0.05 | FIFA | 13.5634% | 13.5491% | 5.7088% | 4.9315% | 12.8820% | 13.2228% | 3.8525% | 4.4323%
Vanilla | 14.4697% | 14.8647% | 7.5962% | 7.8575% | 12.8818% | 13.2236% | 3.8525% | 4.4323%
0.10 | FIFA | 13.5857% | 13.9043% | 6.1217% | 5.9689% | 12.8717% | 13.1748% | 3.8326% | 4.3532%
Vanilla | 15.5342% | 15.9387% | 9.7514% | 10.0750% | 12.8757% | 13.2099% | 3.8392% | 4.4059%

Table 2: Exponentiated gradient with EO constraint on the AdultIncome and
DutchConsensus datasets using logistc regression (as a one-layer neural net),
best results with respect to test combined loss among sweeps of hyper-
parameters are shown.

(a) $\epsilon=0.01$.

(b) $\epsilon=0.05$.

(c) $\epsilon=0.10$.

Figure 6: Pareto frontiers of the balanced loss (${\mathcal{L}}_{\text{bal}}$)
and fairness loss (${\mathcal{L}}_{\text{fv}}$) of CelebA using ResNet-18 with
grid search combined with FIFA and vanilla softmax-cross-entropy loss
respectively. Best-performing hyper-parameters from Table 1 are 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 correspond to training and testing metrics respectively. We observe
that our FIFA method is effective in significantly lowering the Pareto
frontier comparing with the vanilla method, implying that FIFA mitigates
fairness generalization issues as seen in Figure 1.

###  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 DutchConsensus datasets with similar sweeping procedure are
similar to those described in Section 6.1 except that we set
$\delta_{0,\text{Female}},\delta_{1,\text{Female}}\in[0,0.01]$, and
$\delta_{0,\text{Male}}=\delta_{1,\text{Male}}=0$ for the AdultIncome dataset
and $\delta_{0,\text{Male}},\delta_{1,\text{Female}}\in[0,0.01]$, and
$\delta_{0,\text{Female}}=\delta_{1,\text{Male}}=0$ for the DutchConsensus
Dataset.

##### Results.

We tabulate the best-performing models (in terms of test combined loss) among
sweeps in Table 2 and include more details in the Appendix. From Table 2, we
observe the same message as we did in Section 6.1, namely, our method FIFA
outperforms vanilla on both dataset across three different tolerance parameter
$\epsilon$, illustrating the effectiveness of FIFA on boosting fairness
generalization on smaller datasets and models as well. Nonetheless, since the
datasets are much simpler in this case, the improvements are not as large as
in the case for CelebA and larger models.

##  7 Conclusions

Generalization (especially in over-parameterized models) has always been an
important and difficult problem in machine learning research. In this paper,
we set out the first exposition in the study of the generalization of
_fairness constraints_ that has previously been overlooked. Our theoretically-
backed FIFA approach is shown to mitigate poor fairness generalization
observed in vanilla models large or small. In our paper, the analysis is based
on margin upper bounds. We will leave a more fine-grained analysis of the
margins to the future work. Our work is motivated by the societal impact of
improving fairness across subpopulations. Methods like FIFA should be used
with care and may not fully mitigate bias; better training data is still
needed in many settings.

## Acknowledgements

The research of Z. Deng is supported by the Sloan Foundation grants, the NSF
grant 1763665, and the Simons Foundation Collaboration on the Theory of
Algorithmic Fairness. J. Zhang is supported by ONR Contract N00015-19-1-2620.
W.J. Su is supported in part by NSF through CCF-1934876, an Alfred Sloan
Research Fellowship, and the Wharton Dean’s Research Fund. We would like to
thank Dan Roth and the Cognitive Computation Group at the University of
Pennsylvania for stimulating discussions and for providing computational
resources. J. Zhang also thanks Chenwei Wu from Duke University for helpful
discussions.

## References

  * Agarwal et al. [2018] A. Agarwal, A. Beygelzimer, M. Dudík, J. Langford, and H. Wallach.  A reductions approach to fair classification.  In _International Conference on Machine Learning (ICML)_ , pages 60–69. PMLR, 2018.
  * An et al. [2021] J. An, L. Ying, and Y. Zhu.  Why resampling outperforms reweighting for correcting sampling bias with stochastic gradients.  In _International Conference on Learning Representations (ICLR)_ , 2021.  URL https://openreview.net/forum?id=iQQK02mxVIT.
  * Barocas and Selbst [2016] S. Barocas and A. D. Selbst.  Big data’s disparate impact.  _California Law Review_ , 104:671, 2016.
  * Bartlett et al. [2020] P. L. Bartlett, P. M. Long, G. Lugosi, and A. Tsigler.  Benign overfitting in linear regression.  _Proceedings of the National Academy of Sciences_ , 117(48):30063–30070, 2020.  doi: 10.1073/pnas.1907378117.  URL https://www.pnas.org/doi/abs/10.1073/pnas.1907378117.
  * Beutel et al. [2019] A. Beutel, J. Chen, T. Doshi, H. Qian, A. Woodruff, C. Luu, P. Kreitmann, J. Bischof, and E. H. Chi.  Putting fairness principles into practice: Challenges, metrics, and improvements.  In _AAAI/ACM Conference on AI, Ethics, and Society_ , pages 453–459, 2019.
  * Biewald [2020] L. Biewald.  Experiment tracking with weights and biases, 2020.  URL https://www.wandb.com/.  Software available from wandb.com.
  * Bird et al. [2020] S. Bird, M. Dudík, R. Edgar, B. Horn, R. Lutz, V. Milan, M. Sameki, H. Wallach, and K. Walker.  Fairlearn: A toolkit for assessing and improving fairness in AI.  Technical Report MSR-TR-2020-32, Microsoft, May 2020.  URL https://www.microsoft.com/en-us/research/publication/fairlearn-a-toolkit-for-assessing-and-improving-fairness-in-ai/.
  * Burhanpurkar et al. [2021] M. Burhanpurkar, Z. Deng, C. Dwork, and L. Zhang.  Scaffolding sets.  _arXiv_ , 2111.03135, 2021.
  * Byrd and Lipton [2019] J. Byrd and Z. Lipton.  What is the effect of importance weighting in deep learning?  In _International Conference on Machine Learning (ICML)_ , pages 872–881. PMLR, 2019.
  * Cao et al. [2019] K. Cao, C. Wei, A. Gaidon, N. Arechiga, and T. Ma.  Learning imbalanced datasets with label-distribution-aware margin loss.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2019.
  * Chang et al. [2017] H.-S. Chang, E. Learned-Miller, and A. McCallum.  Active bias: Training more accurate neural networks by emphasizing high variance samples.  _Advances in Neural Information Processing Systems (NeurIPS)_ , 30, 2017.
  * Cherepanova et al. [2021] V. Cherepanova, V. Nanda, M. Goldblum, J. P. Dickerson, and T. Goldstein.  Technical challenges for training fair neural networks.  _arXiv_ , 2102.06764, 2021.
  * Coley et al. [2021] R. Y. Coley, E. Johnson, G. E. Simon, M. Cruz, and S. M. Shortreed.  Racial/ethnic disparities in the performance of prediction models for death by suicide after mental health visits.  _JAMA Psychiatry_ , 2021.
  * Corbett-Davies and Goel [2018] S. Corbett-Davies and S. Goel.  The measure and mismeasure of fairness: A critical review of fair machine learning.  _arXiv_ , 1808.00023, 2018.
  * Cotter et al. [2019] A. Cotter, M. Gupta, H. Jiang, N. Srebro, K. Sridharan, S. Wang, B. Woodworth, and S. You.  Training well-generalizing classifiers for fairness metrics and other data-dependent constraints.  In _International Conference on Machine Learning (ICML)_ , pages 1397–1405. PMLR, 2019.
  * Cui et al. [2019] Y. Cui, M. Jia, T.-Y. Lin, Y. Song, and S. Belongie.  Class-balanced loss based on effective number of samples.  In _Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 9268–9277, 2019.
  * Deng et al. [2020a] Z. Deng, F. Ding, C. Dwork, R. Hong, G. Parmigiani, P. Patil, and P. Sur.  Representation via representations: Domain generalization via adversarially learned invariant representations.  _arXiv_ , 2006.11478, 2020a.
  * Deng et al. [2020b] Z. Deng, C. Dwork, J. Wang, and L. Zhang.  Interpreting robust optimization via adversarial influence functions.  In _International Conference on Machine Learning_ , pages 2464–2473. PMLR, 2020b.
  * Deng et al. [2020c] Z. Deng, H. He, J. Huang, and W. Su.  Towards understanding the dynamics of the first-order adversaries.  In _International Conference on Machine Learning_ , pages 2484–2493. PMLR, 2020c.
  * Deng et al. [2021a] Z. Deng, J. Huang, and K. Kawaguchi.  How shrinking gradient noise helps the performance of neural networks.  In _2021 IEEE International Conference on Big Data (Big Data)_ , pages 1002–1007. IEEE, 2021a.
  * Deng et al. [2021b] Z. Deng, L. Zhang, A. Ghorbani, and J. Zou.  Improving adversarial robustness via unlabeled out-of-domain data.  In _International Conference on Artificial Intelligence and Statistics (AISTATS)_ , pages 2845–2853. PMLR, 2021b.
  * Deng et al. [2021c] Z. Deng, L. Zhang, K. Vodrahalli, K. Kawaguchi, and J. Y. Zou.  Adversarial training helps transfer learning via better representations.  _Advances in Neural Information Processing Systems_ , 34, 2021c.
  * Donini et al. [2018] M. Donini, L. Oneto, S. Ben-David, J. S. Shawe-Taylor, and M. Pontil.  Empirical risk minimization under fairness constraints.  _Advances in Neural Information Processing Systems (NeurIPS)_ , 31, 2018.
  * Dua and Graff [2017] D. Dua and C. Graff.  UCI machine learning repository, 2017.  URL http://archive.ics.uci.edu/ml.
  * Dwork et al. [2012] C. Dwork, M. Hardt, T. Pitassi, O. Reingold, and R. Zemel.  Fairness through awareness.  In _Innovations in Theoretical Computer Science Conference (ITCS)_ , pages 214–226, 2012.
  * Edwards and Storkey [2015] H. Edwards and A. Storkey.  Censoring representations with an adversary.  _arXiv_ , 1511.05897, 2015.
  * Feldman et al. [2015] M. Feldman, S. A. Friedler, J. Moeller, C. Scheidegger, and S. Venkatasubramanian.  Certifying and removing disparate impact.  In _International Conference on Knowledge Discovery and Data Mining (KDD)_ , pages 259–268, 2015.
  * Haixiang et al. [2017] G. Haixiang, L. Yijing, J. Shang, G. Mingyun, H. Yuanyue, and G. Bing.  Learning from class-imbalanced data: Review of methods and applications.  _Expert Systems with Applications_ , 73:220–239, 2017.
  * Hardt et al. [2016] M. Hardt, E. Price, and N. Srebro.  Equality of opportunity in supervised learning.  _Advances in neural information processing systems_ , 29, 2016.
  * He and Garcia [2009] H. He and E. A. Garcia.  Learning from imbalanced data.  _IEEE Transactions on Knowledge and Data Engineering_ , 21(9):1263–1284, 2009.
  * He and Ma [2013] H. He and Y. Ma.  _Imbalanced learning: foundations, algorithms, and applications_.  Wiley-IEEE Press, 2013.
  * Holstein et al. [2019] K. Holstein, J. Wortman Vaughan, H. Daumé III, M. Dudik, and H. Wallach.  Improving fairness in machine learning systems: What do industry practitioners need?  In _CHI Conference on Fuman Factors in Computing Systems (CHI)_ , pages 1–16, 2019.
  * Ji et al. [2021a] W. Ji, Z. Deng, R. Nakada, J. Zou, and L. Zhang.  The power of contrast for feature learning: A theoretical analysis.  _arXiv_ , 2110.02473, 2021a.
  * Ji et al. [2021b] W. Ji, Y. Lu, Y. Zhang, Z. Deng, and W. J. Su.  An unconstrained layer-peeled perspective on neural collapse.  _arXiv_ , 2110.02796, 2021b.
  * Kakade et al. [2008] S. M. Kakade, K. Sridharan, and A. Tewari.  On the complexity of linear prediction: Risk bounds, margin bounds, and regularization.  _Advances in Neural Information Processing Systems (NeurIPS)_ , 21, 2008.
  * Kawaguchi et al. [2022] K. Kawaguchi, L. Zhang, and Z. Deng.  Understanding dynamics of nonlinear representation learning and its application.  _Neural Computation_ , 34(4):991–1018, 2022.
  * Khan et al. [2019] S. Khan, M. Hayat, S. W. Zamir, J. Shen, and L. Shao.  Striking the right balance with uncertainty.  In _Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 103–112, 2019.
  * Kim et al. [2019] M. P. Kim, A. Ghorbani, and J. Zou.  Multiaccuracy: Black-box post-processing for fairness in classification.  In _AAAI/ACM Conference on AI, Ethics, and Society_ , pages 247–254, 2019.
  * Kini et al. [2021] G. R. Kini, O. Paraskevas, S. Oymak, and C. Thrampoulidis.  Label-imbalanced and group-sensitive classification under overparameterization.  _Advances in Neural Information Processing Systems (NeurIPS)_ , 34, 2021.
  * Krawczyk [2016] B. Krawczyk.  Learning from imbalanced data: open challenges and future directions.  _Progress in Artificial Intelligence_ , 5(4):221–232, 2016.
  * Lahoti et al. [2020] P. Lahoti, A. Beutel, J. Chen, K. Lee, F. Prost, N. Thain, X. Wang, and E. Chi.  Fairness without demographics through adversarially reweighted learning.  _Advances in Neural Information Processing Systems (NeurIPS)_ , 33:728–740, 2020.
  * Li et al. [2002] Y. Li, H. Zaragoza, R. Herbrich, J. Shawe-Taylor, and J. Kandola.  The perceptron algorithm with uneven margins.  In _International Conference on Machine Learning (ICML)_ , volume 2, pages 379–386, 2002.
  * Liu et al. [2016] W. Liu, Y. Wen, Z. Yu, and M. Yang.  Large-margin softmax loss for convolutional neural networks.  In _International Conference on Machine Learning (ICML)_ , volume 2, page 7, 2016.
  * Liu et al. [2015] Z. Liu, P. Luo, X. Wang, and X. Tang.  Deep learning face attributes in the wild.  In _International Conference on Computer Vision (ICCV)_ , December 2015.
  * Madaio et al. [2020] M. A. Madaio, L. Stark, J. Wortman Vaughan, and H. Wallach.  Co-designing checklists to understand organizational challenges and opportunities around fairness in ai.  In _CHI Conference on Human Factors in Computing Systems (CHI)_ , pages 1–14, 2020.
  * Madras et al. [2018] D. Madras, E. Creager, T. Pitassi, and R. Zemel.  Learning adversarially fair and transferable representations.  In _International Conference on Machine Learning (ICML)_ , pages 3384–3393. PMLR, 2018.
  * Mani and Zhang [2003] I. Mani and I. Zhang.  kNN approach to unbalanced data distributions: a case study involving information extraction.  In _Workshop on Learning from Imbalanced Datasets_ , volume 126, pages 1–7. International Conference on Machine Learning (ICML), 2003.
  * Martinez et al. [2020] N. Martinez, M. Bertran, and G. Sapiro.  Minimax Pareto fairness: A multi objective perspective.  In _International Conference on Machine Learning (ICML)_ , pages 6755–6764. PMLR, 2020.
  * Mehrabi et al. [2021] N. Mehrabi, F. Morstatter, N. Saxena, K. Lerman, and A. Galstyan.  A survey on bias and fairness in machine learning.  _ACM Computing Surveys (CSUR)_ , 54(6):1–35, 2021\.
  * Nakkiran et al. [2020] P. Nakkiran, G. Kaplun, Y. Bansal, T. Yang, B. Barak, and I. Sutskever.  Deep double descent: Where bigger models and more data hurt.  In _International Conference on Learning Representations (ICLR)_ , 2020.  URL https://openreview.net/forum?id=B1g5sA4twr.
  * Sagawa et al. [2020] S. Sagawa, A. Raghunathan, P. W. Koh, and P. Liang.  An investigation of why overparameterization exacerbates spurious correlations.  In _International Conference on Machine Learning (ICML)_ , pages 8346–8356. PMLR, 2020.
  * Saha et al. [2020] D. Saha, C. Schumann, D. Mcelfresh, J. Dickerson, M. Mazurek, and M. Tschantz.  Measuring non-expert comprehension of machine learning fairness metrics.  In _International Conference on Machine Learning (ICML)_ , pages 8377–8387. PMLR, 2020.
  * Schmidt et al. [2018] L. Schmidt, S. Santurkar, D. Tsipras, K. Talwar, and A. Madry.  Adversarially robust generalization requires more data.  _Advances in Neural Information Processing Systems (NeurIPS)_ , 31, 2018.
  * Selbst et al. [2019] A. D. Selbst, D. Boyd, S. A. Friedler, S. Venkatasubramanian, and J. Vertesi.  Fairness and abstraction in sociotechnical systems.  In _Conference on Fairness, Accountability, and Transparency_ , pages 59–68, 2019.
  * voor de Statistiek [Statistics Netherlands] C. B. voor de Statistiek (Statistics Netherlands) and M. P. Center.  The Dutch virtual census of 2001, 2001.  URL https://microdata.worldbank.org/index.php/catalog/2102.
  * Wang et al. [2017] Y.-X. Wang, D. Ramanan, and M. Hebert.  Learning to model the tail.  _Advances in Neural Information Processing Systems (NeurIPS)_ , 30, 2017.
  * Yao et al. [2021a] H. Yao, L.-K. Huang, L. Zhang, Y. Wei, L. Tian, J. Zou, J. Huang, et al.  Improving generalization in meta-learning via task augmentation.  In _International Conference on Machine Learning_ , pages 11887–11897. PMLR, 2021a.
  * Yao et al. [2021b] H. Yao, L. Zhang, and C. Finn.  Meta-learning with fewer tasks through task interpolation.  _arXiv_ , 2106.02695, 2021b.
  * Zafar et al. [2017] M. B. Zafar, I. Valera, M. G. Rogriguez, and K. P. Gummadi.  Fairness constraints: Mechanisms for fair classification.  In _International Conference on Artificial Intelligence and Statistics (AISTATS)_ , pages 962–970. PMLR, 2017.
  * Zafar et al. [2019] M. B. Zafar, I. Valera, M. Gomez-Rodriguez, and K. P. Gummadi.  Fairness constraints: A flexible approach for fair classification.  _The Journal of Machine Learning Research_ , 20(1):2737–2778, 2019.
  * Zemel et al. [2013] R. Zemel, Y. Wu, K. Swersky, T. Pitassi, and C. Dwork.  Learning fair representations.  In _International Conference on Machine Learning (ICML)_ , pages 325–333. PMLR, 2013.
  * Zhang et al. [2017] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals.  Understanding deep learning requires rethinking generalization.  In _International Conference on Learning Representations (ICLR)_. OpenReview.net, 2017.  URL https://openreview.net/forum?id=Sy8gdB9xx.
  * Zhang et al. [2020] L. Zhang, Z. Deng, K. Kawaguchi, A. Ghorbani, and J. Zou.  How does mixup help with robustness and generalization?  _arXiv_ , 2010.04819, 2020.
  * Zhang et al. [2021] L. Zhang, Z. Deng, K. Kawaguchi, and J. Y. Zou.  When and how mixup improves calibration.  _arXiv_ , 2102.06289, 2021.

Appendix

##  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 multi-groups for equalized odds

We discussed the case that ${\mathcal{Y}}=\\{0,1\\}$ and
${\mathcal{A}}=\\{a_{1},a_{2}\\}$ in the main context. In this subsection, we
discuss the extension to multi-classes and multi-groups.

First, we extend the case to ${\mathcal{Y}}=\\{0,1\\}$ and
$|{\mathcal{A}}|\geq 2$. In that case, we can consider the constraints

$\sum_{a,a^{\prime}\in{\mathcal{A}},a\neq
a^{\prime}}\sum_{i\in{\mathcal{Y}}}\left|\mathbb{P}(h(X)=i|Y=i,A=a)-\mathbb{P}(h(X)=i|Y=i,A=a^{\prime})\right|,$

regardless of the order of $(a,a^{\prime})$, and there are
$|{\mathcal{A}}|\choose 2$ pairs of $(a,a^{\prime})$’s.

Thus, our performance criteria ${\mathcal{M}}_{\text{multi-groups}}[f]$ can be
taken as:

${\mathcal{L}}_{\text{bal}}[f]+\alpha\sum_{a,a^{\prime}\in{\mathcal{A}},a\neq
a^{\prime}}\sum_{i\in{\mathcal{Y}}}\left|\mathbb{P}(h(X)=i|Y=i,A=a)-\mathbb{P}(h(X)=i|Y=i,A=a^{\prime})\right|.$

Then, via Lemma A.2, for all $f\in{\mathcal{F}}$

$\displaystyle{\mathcal{M}}_{\text{multi-groups}}[f]$
$\displaystyle\lesssim\sum_{i\in{\mathcal{Y}}}\frac{1}{\gamma_{i}}\sqrt{\frac{C({\mathcal{F}})}{n_{i}}}+\sum_{i\in{\mathcal{Y}},a\in{\mathcal{A}}}\frac{\alpha(|A|-1)}{\gamma_{i,a}}\sqrt{\frac{C({\mathcal{F}})}{n_{i,a}}}$
$\displaystyle\leq\sum_{i\in{\mathcal{Y}}}\frac{1}{\gamma_{i}}\sqrt{\frac{C({\mathcal{F}})}{n_{i}}}+\sum_{i\in{\mathcal{Y}},a\in{\mathcal{A}}}\frac{\alpha(|A|-1)}{\gamma_{i}}\sqrt{\frac{C({\mathcal{F}})}{n_{i,a}}}.$

We overload the notation $\alpha$, then we have

${\mathcal{M}}_{\text{multi-
groups}}[f]\lesssim\sum_{i\in{\mathcal{Y}}}\frac{1}{\gamma_{i}}\sqrt{\frac{C({\mathcal{F}})}{n_{i}}}+\sum_{i\in{\mathcal{Y}},a\in{\mathcal{A}}}\frac{\alpha}{\gamma_{i}}\sqrt{\frac{C({\mathcal{F}})}{n_{i,a}}}.$
(A.1)

Notice the difference between Eq. (A.1) and Eq. (A.5) is that in Eq. (A.1),
$|{\mathcal{A}}|\geq 2$. Thus, by similar proof as in Theorem A.1, we can
obtain

$\gamma_{0}/\gamma_{1}=\tilde{n}_{0}^{-1/4}/\tilde{n}_{1}^{-1/4},$

where the adjusted sample size

$\tilde{n}_{i}=\frac{n_{i}\Pi_{a}n_{i,a}}{(\sqrt{\Pi_{a}n_{i,a}}+\alpha\sum_{j\in{\mathcal{A}}}\sqrt{n_{i}\Pi_{a\in{\mathcal{A}}^{\backslash
j}}n_{i,a}})^{2}},$

for $i\in\\{0,1\\}$.

Given the results above, for multiple classes with multiple groups, for
$i,j\in{\mathcal{Y}}$,

$\gamma_{i}/\gamma_{j}=\tilde{n}_{i}^{-1/4}/\tilde{n}_{j}^{-1/4},$

where the adjusted sample size
$\tilde{n}_{i}=\frac{n_{i}\Pi_{a}n_{i,a}}{(\sqrt{\Pi_{a}n_{i,a}}+\alpha\sum_{j\in{\mathcal{A}}}\sqrt{n_{i}\Pi_{a\in{\mathcal{A}}^{\backslash
j}}n_{i,a}})^{2}}$ for $i\in{\mathcal{Y}}$.

##### FIFA for multi-classes and multi-groups.

We will demonstrate how to apply the above motivations to design better margin
losses. Consider a logits-based loss

$\ell((x,y);f)=\ell(f(x)_{y},\\{f(x)_{i}\\}_{i\in{\mathcal{Y}}\backslash y}),$

which is non-increasing with respect to its first coordinate if we fix the
second coordinate.

Our flexible imbalance-fairness-aware (FIFA) approach modifies the above
losses during training

$\ell_{\text{FIFA}}((x,y,a);f)=\ell(f(x)_{y}-\Delta_{y,a},\\{f(x)_{i}\\}_{i\in{\mathcal{Y}}\backslash
y})$ (A.2)

where $\Delta_{i,a}=C/\tilde{n}_{i}^{1/4}+\delta_{i,a}$, and $\delta_{i,a}\geq
0$. The specific assignment of $\delta_{i,a}\geq 0$ is described in Section
A.2.

###  A.2 Assignment of $\delta_{i,a}$ for multi-groups

In this subsection, we describe how to choose $\delta_{i,a}$ for multiple
demographic groups. Recall in Section A.1, for multiple demographic groups,

$\displaystyle{\mathcal{M}}_{\text{multi-groups}}[f]$
$\displaystyle\lesssim\sum_{i\in{\mathcal{Y}}}\frac{1}{\gamma_{i}}\sqrt{\frac{C({\mathcal{F}})}{n_{i}}}+\sum_{i\in{\mathcal{Y}},a\in{\mathcal{A}}}\frac{\alpha}{\gamma_{i,a}}\sqrt{\frac{C({\mathcal{F}})}{n_{i,a}}}.$
(A.3)

Given $\gamma_{i,a}\geq\gamma_{i}$, similar as in the main context, we can
take $\gamma_{i,a}=\gamma_{i}+\delta_{i,a}$, where $\delta_{i,a}\geq 0$ are
tuning parameters.

Assume there are $k$ groups. Let us first ordering $|S_{i,a}|$ by in a
decreasing order. Without loss of generality,
$|S_{i,a_{1}}|\geq|S_{i,a_{2}}|\geq\cdots\geq|S_{i,a_{k}}|$. Thus, when tune
the parameters $\delta_{i,a}$’s, we set $\delta_{i,a_{1}}=0$ (or we can
randomly choose other $a$’s to set $\delta_{i,a}=0$ if there are ties and
$|S_{i,a}|=|S_{i,a_{1}}|$, but for simplicity, we ignore this case), and we
make sure $\delta_{i,a_{1}}\leq\delta_{i,a_{2}}\leq\cdots\delta_{i,a_{k}}$.
This is optimal in the sense that if there are $k$ constants
$0=\delta_{1}\leq\delta_{2}\leq\delta_{3}\leq\cdots\leq\delta_{k}$, then

$\sum_{i\in{\mathcal{Y}},a_{j}\in{\mathcal{A}}}\frac{\alpha}{\gamma_{i}+\delta_{i,a_{j}}}\sqrt{\frac{C({\mathcal{F}})}{n_{i,a_{j}}}}\leq\sum_{i\in{\mathcal{Y}},a_{j}\in{\mathcal{A}}}\frac{\alpha}{\gamma_{i}+\delta_{i,a_{\sigma(j)}}}\sqrt{\frac{C({\mathcal{F}})}{n_{i,a_{j}}}},$

where $\sigma(\cdot)$ is a permutation. In other words, our way to assign
$\delta_{i,a}$’s can make the upper boupnd on RHS of Eq. (A.3) optimal. This
is a direct application of rearrangement inequality, see Lemma A.1.

###### Lemma A.1

For $x_{1}\leq x_{2}\leq\cdots\leq x_{k}$, $y_{1}\leq y_{2}\leq\cdots\leq
y_{k}$, any permutation $\sigma(\cdot)$

$x_{k}y_{1}+x_{k-1}y_{2}+\cdots+x_{1}y_{k}\leq
x_{\sigma(1)}y_{1}+x_{\sigma(2)}y_{2}+\cdots+x_{\sigma(k)}y_{k}\leq
x_{1}y_{1}+x_{2}y_{2}+\cdots+x_{k}y_{k}.$

###  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
${\mathcal{Y}}=\\{0,1\\}$ (this is necessary for EqOpt) and
${\mathcal{A}}=\\{a_{1},a_{2}\\}$. Given the derivation in this subsection, we
can further derive FIFA for other fairness notions as in Section A.1.

##### Equalized opportunity.

Specifically, for EqOpt, the aim is:

$\displaystyle\min_{f}{\mathcal{L}}_{\text{bal}}[f]$
$\displaystyle\text{s.t.}~{}\forall
y\in{\mathcal{Y}},a\in{\mathcal{A}},~{}~{}\mathbb{P}(h(X)$
$\displaystyle=1|Y=1,A=a)=\mathbb{P}(h(X)=1|Y=1),$

This is a simple version of EO in some sense. Directly using the derivation in
Section A.1, we have

$\gamma_{0}/\gamma_{1}=n_{0}^{-1/4}/\tilde{n}_{1}^{-1/4},$

where the adjusted sample size

$\tilde{n}_{1}=\frac{n_{1}n_{1,a_{1}}n_{1,a_{2}}}{(\sqrt{n_{1,a_{1}}n_{1,a_{2}}}+\alpha(\sqrt{n_{1}n_{1,a_{2}}}+\sqrt{n_{1}n_{1,a_{1}}}))^{2}}.$

##### Demographic parity.

Similar to EO, for DP, the optimization aims to:

$\displaystyle\min_{f}{\mathcal{L}}_{\text{bal}}[f]$ $\displaystyle
s.t.~{}\forall y\in{\mathcal{Y}},a\in{\mathcal{A}},~{}~{}\mathbb{P}$
$\displaystyle(h(X)=y|A=a)=\mathbb{P}(h(X)=y).$

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. $|\mathbb{P}(h(X)=y|A=a)-\mathbb{P}(h(X)=y)|<\epsilon$ for
some $\epsilon>0$ (if there are only two groups, one can alternatively use
$|\mathbb{P}(h(X)=y|A=a_{1})-\mathbb{P}(h(X)=y)|A=a_{2}|\leq\epsilon$). When
$\epsilon$ is large enough (or $\hat{\mathbb{P}}(Y=1|A=a_{1})$ is close to
$\hat{\mathbb{P}}(Y=1|A=a_{2})$), if we use suitable models, similar as in the
EO setting, we would expect all the training examples are classified perfectly
while satisfying
$|\hat{\mathbb{P}}(h(X)=y|A=a_{1})-\hat{\mathbb{P}}(h(X)=y)|A=a_{2}|\leq\epsilon$.
Then, we can use similar techniques to characterize a trade-off between
margins.

Specifically, simple calculation leads to
$\sum_{i\in{\mathcal{Y}}}|\mathbb{P}(h(X)=i|A=a_{1})-\mathbb{P}(h(X)=i|A=a_{2})|\leq\sum_{j\in\\{1,2\\}}\sum_{i\in\\{0,1\\}}\mathbb{P}(Y=i|A=a_{j}){\mathcal{L}}_{i,a_{j}}[f]+I$,
where $I$ is a term not related to $f$. Thus, our optimization objective (not
performance criterion) for DP can be taken as:

${\mathcal{L}}_{\text{bal}}[f]+\alpha\sum_{i,a}\mathbb{P}(Y=i|A=a){\mathcal{L}}_{i,a}[f],$
(A.4)

for weight $\alpha$. We can use training data to estimate
$\mathbb{P}(Y=i|A=a)$. For simplicity, we can also use
${\mathcal{L}}_{\text{bal}}[f]+\alpha\sum_{i,a}{\mathcal{L}}_{i,a}[f]$, which
shares the same upper bound as in Theorem 3.1 and also implies
$\gamma_{0}/\gamma_{1}=\tilde{n}_{0}^{-1/4}/\tilde{n}_{1}^{-1/4},$ that will
also be used in the experiments in later sections. We should also remark that
when $\epsilon$ is too small, our method may not work, this can also be
reflected in Table 4, when $\epsilon=0.01$.

###  A.4 Omitted proofs

####  A.4.1 Proof of Theorem 3.1

######  Theorem A.1 (Restatement of Theorem 3.1)

With high probability over the randomness of the training data, for
${\mathcal{Y}}=\\{0,1\\}$, ${\mathcal{A}}=\\{a_{1},a_{2}\\}$, and for some
proper complexity measure of class ${\mathcal{F}}$, for any
$f\in{\mathcal{F}}$,

$\displaystyle\begin{split}{\mathcal{M}}[f]\lesssim\sum_{i\in{\mathcal{Y}}}\frac{1}{\gamma_{i}}\sqrt{\frac{C({\mathcal{F}})}{n_{i}}}+\sum_{i\in{\mathcal{Y}},a\in{\mathcal{A}}}\frac{\alpha}{\gamma_{i,a}}\sqrt{\frac{C({\mathcal{F}})}{n_{i,a}}}\leq\sum_{i\in{\mathcal{Y}}}\frac{1}{\gamma_{i}}\sqrt{\frac{C({\mathcal{F}})}{n_{i}}}+\sum_{i\in{\mathcal{Y}},a\in{\mathcal{A}}}\frac{\alpha}{\gamma_{i}}\sqrt{\frac{C({\mathcal{F}})}{n_{i,a}}},\end{split}$

where $\gamma_{i}$ is the margin of the $i$-th class’s sample set $S_{i}$ and
$\gamma_{i,a}$ is the margin of demographic subgroup’s sample set $S_{i,a}$.

This following lemma is the key lemma we will use. Let us define the empirical
Rademacher complexity of ${\mathcal{F}}$ of subgroup/class margin on $S_{*}$
as

$\hat{{\mathcal{R}}}_{i}({\mathcal{F}})=\frac{1}{n_{i}}\mathbb{E}_{\xi}[\sup_{f\in{\mathcal{F}}}\sum_{j\in
S_{i}}\xi_{j}[f(x_{j})_{i}-\max_{i^{\prime}\neq i}f(x_{j})_{i^{\prime}}]],$

$\hat{{\mathcal{R}}}_{i,a}({\mathcal{F}})=\frac{1}{n_{i,a}}\mathbb{E}_{\xi}[\sup_{f\in{\mathcal{F}}}\sum_{j\in
S_{i,a}}\xi_{j}[f(x_{j})_{i}-\max_{i^{\prime}\neq i}f(x_{j})_{i^{\prime}}]],$

where $\xi_{j}$ is i.i.d. drawn from a uniform distribution $\\{-1,1\\}$.

###### Lemma A.2

Let
$\hat{{\mathcal{L}}}_{\gamma,i}[f]=\mathbb{P}_{x\sim\hat{{\mathcal{P}}}_{i}}(\max_{j\neq
i}f(x)_{j}>f(x)_{i}-\gamma)$ and
$\hat{{\mathcal{L}}}_{\gamma,(i,a)}[f]=\mathbb{P}_{x\sim\hat{{\mathcal{P}}}_{i,a}}(\max_{j\neq
i}f(x)_{j}>f(x)_{i}-\gamma)$. With probability at least $1-\delta$ over the
the randomness of the training data, for some proper complexity measure of
class ${\mathcal{F}}$, for any $f\in{\mathcal{F}}$,
$*\in\\{i,(i,a)|i\in{\mathcal{Y}},a\in{\mathcal{A}}\\}$, and all margins
$\gamma>0$

${\mathcal{L}}_{*}[f]\lesssim\hat{{\mathcal{L}}}_{\gamma,*}[f]+\frac{1}{\gamma}\hat{{\mathcal{R}}}_{*}({\mathcal{F}})+\epsilon_{*}(n_{*},\delta,\gamma_{*}),$
(A.5)

where $\hat{{\mathcal{R}}}_{*}({\mathcal{F}})$ is the empirical Rademacher
complexity of ${\mathcal{F}}$ of subgroup/class margin on training dataset
corresponding to index set $S_{*}$, which can be further upper bnounded by
$\sqrt{\frac{C({\mathcal{F}})}{n_{*}}}$. Also,
$\epsilon_{*}(n_{*},\delta,\gamma_{*})$ is usually a low-order term in $n_{*}$

Proof: This is a direct application of the standard margin-based
generalization bound in [35]. $\square$

##### Proof of Theorem A.1.

Notice that all the training samples are classified perfectly by $h$, not only
$\mathbb{P}_{(x,y)\sim\hat{\mathcal{P}}_{\text{bal}}}(h(x)\neq y)=0$ is
satisfied, we also have that
$\mathbb{P}_{(x,y)\sim\hat{{\mathcal{P}}}_{i,a_{j}}}(h(x)\neq y)=0$ for all
$i\in{\mathcal{Y}}$ and $a_{j}\in{\mathcal{A}}$. We remark here that
$\mathbb{P}(h(X)=i|Y=i,A=a)=1-\mathbb{P}_{(x,y)\sim{\mathcal{P}}_{i,a}}(h(x)\neq
y)=1-\mathbb{P}(f(x)_{y}<\max_{j\neq y}f(x)_{j})$.

$\displaystyle{\mathcal{L}}_{\text{bal}}[f]+\alpha\sum_{i\in{\mathcal{Y}}}\left|\mathbb{P}(h(X)=i|Y=i,A=a_{1})-\mathbb{P}(h(X)=i|Y=i,A=a_{2})\right|$
$\displaystyle\leq{\mathcal{L}}_{\text{bal}}[f]+\alpha(\mathbb{P}_{(x,y)\sim{\mathcal{P}}_{i,a_{1}}}(h(x)\neq
y)+\mathbb{P}_{(x,y)\sim{\mathcal{P}}_{i,a_{2}}}(h(x)\neq y)).$

Then, plug in Lemma A.2, the proof is complete.

####  A.4.2 Optimization of $\gamma_{0}/\gamma_{1}$

###### Theorem A.2

For binary classification, let ${\mathcal{F}}$ be a class of neural networks
with a bias term, i.e. ${\mathcal{F}}=\\{f+b\\}$ where $f$ is a neural net
function and $b\in{\mathbb{R}}^{2}$ is a bas, with Rademacher complexity upper
bound
$\hat{{\mathcal{R}}}_{*}({\mathcal{F}})\leq\sqrt{\frac{C({\mathcal{F}})}{n_{*}}}$.
Suppose some classifier $f\in{\mathcal{F}}$ can achieve a total sum of margins
$\gamma^{\prime}_{0}+\gamma^{\prime}_{1}=\beta$ with
$\gamma^{\prime}_{0},\gamma^{\prime}_{1}>0.$ Then, there exists a classifier
$f^{*}\in{\mathcal{F}}$ with margin ratio

$\gamma^{*}_{0}/\gamma^{*}_{1}=\tilde{n}_{i}^{-1/4}/\tilde{n}_{j}^{-1/4},$

where the adjusted sample size
$\tilde{n}_{i}=\frac{n_{i}\Pi_{a}n_{i,a}}{(\sqrt{\Pi_{a}n_{i,a}}+\alpha\sum_{j\in{\mathcal{A}}}\sqrt{n_{i}\Pi_{a\in{\mathcal{A}}^{\backslash
j}}n_{i,a}})^{2}}$ for $i\in{\mathcal{Y}}$.

Proof: This can directly follow simliar proof in Theorem 3 in [10]. The only
difference is that we need to solve

$\min_{\gamma_{0}+\gamma_{1}=\beta}\sum_{i\in{\mathcal{Y}}}\frac{1}{\gamma_{i}}\sqrt{\frac{1}{n_{i}}}+\sum_{i\in{\mathcal{Y}},a\in{\mathcal{A}}}\frac{\alpha}{\gamma_{i}}\sqrt{\frac{1}{n_{i,a}}},$

which yields the final result. $\square$

####  A.4.3 Proof of Example 3.1.

######  Example A.1 (Restatement of Example 3.1)

Given function $f$ and set $S$, let

$\operatorname{dist}(f,S)=\min_{x,s\in S}\|f(x)-s\|_{2}.$

Consider two classifiers $\tilde{f},f\in{\mathcal{F}}$ such that

$\operatorname{dist}(\tilde{f},S_{0})/\operatorname{dist}(\tilde{f},S_{1})=\tilde{n}_{0}^{-1/4}/\tilde{n}_{1}^{-1/4}$

and
$\operatorname{dist}(f^{\prime},S_{0})/\operatorname{dist}(f^{\prime},S_{1})=n_{0}^{-1/4}/n_{1}^{-1/4}$.
Suppose $\|\beta^{*}\|\gg\sqrt{p\log n}$, $\|\mu_{i}\|<C$,
$(\mu_{1}^{*}-\mu_{2}^{*})^{\top}\beta=0$, and $\pi_{1,a_{2}}\leq
c_{1}\pi_{1,a_{1}}$ for a sufficiently small $c_{1}>0$, then when
$n_{0},n_{1}$ are sufficiently large, with high probability we have
${\mathcal{M}}[\tilde{f}]<{\mathcal{M}}[f].$

Proof: Recall that
$\tilde{n}_{i}=\frac{n_{i}\Pi_{a\in{\mathcal{A}}}n_{i,a}}{(\sqrt{\Pi_{a\in{\mathcal{A}}}n_{i,a}}+\alpha\sum_{a\in{\mathcal{A}}}\sqrt{n_{i}n_{i,a}})^{2}}$
for $i\in\\{0,1\\}$, and our training data follow distribution: $x\mid
y=0\sim\sum_{i=1}^{2}\pi_{0,a_{i}}{\mathcal{N}}_{p}(\mu_{i},I),~{}~{}x\mid
y=1\sim\sum_{i=1}^{2}\pi_{1,a_{i}}{\mathcal{N}}_{p}(\mu_{i}+\beta^{*},I).$

$\displaystyle{\mathcal{M}}[f]=$
$\displaystyle\frac{1}{2}\mathbb{P}(h(X)=1|Y=0)+\frac{1}{2}\mathbb{P}(h(X)=0|Y=1)$
$\displaystyle+\alpha\sum_{i\in{\mathcal{Y}}}\left|\mathbb{P}(h(X)=i|Y=i,A=a_{1})-\mathbb{P}(h(X)=i|Y=i,A=a_{2})\right|$
$\displaystyle=$
$\displaystyle\frac{1}{2}\sum_{i=1}^{2}\pi_{0,a_{i}}\Phi(\frac{\beta^{*\top}\mu_{i}-c}{\|\beta^{*}\|})+\frac{1}{2}\sum_{i=1}^{2}\pi_{1,a_{i}}\Phi(\frac{c-\beta^{*\top}\mu_{i}-\|\beta^{*}\|^{2}}{\|\beta^{*}\|})$
$\displaystyle+\alpha\cdot|\Phi(\frac{\beta^{*\top}\mu_{0}-c}{\|\beta^{*}\|})-\Phi(\frac{\beta^{*\top}\mu_{1}-c}{\|\beta^{*}\|})|+\alpha\cdot|\Phi(\frac{\beta^{*\top}\mu_{0}+\|\beta^{*}\|^{2}-c}{\|\beta^{*}\|})-\Phi(\frac{\beta^{*\top}\mu_{1}+\|\beta^{*}\|^{2}-c}{\|\beta^{*}\|})|$

For different margin ratio $\gamma$, we have
$c=\mu_{1}^{\top}\beta^{*}+\frac{1}{1+\gamma}\|\beta^{*}\|^{2}+O_{P}(\sqrt{p\log
n})$, where the $O_{P}(\sqrt{p\log n})$ term accounts for the variation of
random samples and is based on the fact that $\|Z\|^{2}\sim\chi_{p}^{2}$ if
$Z\sim\mathcal{N}_{p}(0,I)$ and $\max Z_{i}=O_{P}(p\log n)$ if
$Z_{1},...,Z_{n}\stackrel{{\scriptstyle i.i.d.}}{{\sim}}\chi_{p}^{2}$.

Using the fact that $\|\beta^{*}\|\gg\sqrt{p\log n}$ and $\|\mu_{i}\|<C$, we
then have $c=(\frac{1}{1+\gamma}+o_{P}(1))\|\beta^{*}\|^{2}.$

Similarly, we have

${\mathcal{M}}[f]=\Phi(-\frac{c}{\|\beta^{*}\|})+\Phi(\frac{c-\|\beta^{*}\|^{2}}{\|\beta^{*}\|})+o(1)$

Then let’s consider the two ratios $\gamma=n_{0}^{-1/4}/n_{1}^{-1/4}$ and
$\tilde{\gamma}=\tilde{n}_{0}^{-1/4}/\tilde{n}_{1}^{-1/4}$.

In the following we compute $\tilde{n}_{0}$ and $\tilde{n}_{1}$:

When $\pi_{1,a_{2}}\leq c_{1}\pi_{1,a_{1}}$
$\tilde{n}_{1}=\frac{n_{1}\Pi_{a\in{\mathcal{A}}}n_{1,a}}{(\sqrt{\Pi_{a\in{\mathcal{A}}}n_{1,a}}+\alpha\sum_{a\in{\mathcal{A}}}\sqrt{n_{1}n_{1,a}})^{2}}\in(0.9n_{1},n_{1})$

When $\pi_{0,a_{2}}=\pi_{0,a_{1}}$
$\tilde{n}_{0}=\frac{n_{0}\Pi_{a\in{\mathcal{A}}}n_{0,a}}{(\sqrt{\Pi_{a\in{\mathcal{A}}}n_{0,a}}+\alpha\sum_{a\in{\mathcal{A}}}\sqrt{n_{0}n_{0,a}})^{2}}=(\frac{1}{1+2\sqrt{2}})^{2}n_{0}.$

As a result, we have $\frac{\tilde{\gamma}}{\gamma}\in[1.9,2]$. When the data
is imbalanced such that $\gamma=(\frac{n_{1}}{n_{0}})^{1/4}>1$, we have
$0<\frac{1}{1+\tilde{\gamma}}<\frac{1}{1+\gamma}<1/2$, and consequently

$\Phi(-\frac{\frac{1}{1+\tilde{\gamma}}\|\beta^{*}\|^{2}}{\|\beta^{*}\|})+\Phi(\frac{\frac{1}{1+\tilde{\gamma}}\|\beta^{*}\|^{2}-\|\beta^{*}\|^{2}}{\|\beta^{*}\|})<\Phi(-\frac{\frac{1}{1+\tilde{\gamma}}\|\beta^{*}\|^{2}}{\|\beta^{*}\|})+\Phi(\frac{\frac{1}{1+\tilde{\gamma}}\|\beta^{*}\|^{2}-\|\beta^{*}\|^{2}}{\|\beta^{*}\|}).$

Additionally, we have that when $\|\beta^{*}\|\to\infty$, the second term in
the ${\mathcal{M}}[f]$, the fairness violation error is $o(1)$. Combining all
the pieces, we have ${\mathcal{M}}[\tilde{f}]<{\mathcal{M}}[f].$

$\square$

####  A.4.4 Proof of Theorem 5.1.

######  Theorem A.3 (Restatement of Theorem 5.1)

Let $\rho=\max_{f}\|M\hat{\mu}^{\text{new}}(f)-\hat{c}\|_{\infty}$. For
$\eta=\nu/(2\rho^{2}B)$, the modified ExpGrad will return a $\nu$-approximate
saddle point of $L^{\text{new}}$ in at most
$4\rho^{2}B^{2}\log(|{\mathcal{K}}|+1)/\nu^{2}$ iterations.

Proof: We consider an extended version of $h$ in [1], which is a function of
(x,y,a) instead of just be a function of $x$. $h:(x,y,a)\mapsto\\{0,1\\}$.
Notice that $\mu(h)$ also satisfies the requirement in [1] with the extend
version $h$. Thus, directly by classic result of in Freund & Scapire (1996)
and theorm $1$ in [1], the result follows. $\square$

###  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 be applied to
many other popular algorithms such as fair representation [46]. We here show
how to combine with fair representation.

In [46], there are several parts, an encoder $\rho$, an adversary $v$, a
decoder $k$ and a predictor $g$. The optimization is:

$\min_{g,\rho,k}\max_{v}\mathbb{E}_{X,Y,A}L(g,\rho,k,v),$

where

$\displaystyle
L(g,\rho,k,v)=\lambda_{1}\ell_{c}(g(\rho(X)),Y)+\lambda_{2}\ell_{\text{dec}}(k(\rho(X),A),X)+\lambda_{3}\ell_{\text{adv}}(v(\rho(X),A)),$

for cross entropy loss $\ell_{c}$, decoding loss $\ell_{\text{dec}}$, and
adversary loss $\ell_{\text{adv}}$. We can modify the cross entropy loss to
$\ell_{c}$ to $\ell_{\text{FIFA}}$. So,

$\displaystyle
L_{\text{FIFA}}(g,\rho,k,v)=\lambda_{1}\ell_{\text{FIFA}}(g(\rho(X)),Y)+\lambda_{2}\ell_{\text{dec}}(k(\rho(X),A),X)+\lambda_{3}\ell_{\text{adv}}(v(\rho(X),A)).$

Actually, for $\ell_{\text{adv}}$, we can similarly modify for indices, but it
is a little complicated and notation heavy, so we omit it here.

##  Appendix B Implementation details

Data | AdultIncome | CelebA | DutchConsensus
---|---|---|---
Label | - | + | - | + | - | +
Gender | Female | Male | Female | Male | Female | Male | Female | Male | Female | Male | Female | Male
Train | 9592 | 15128 | 1179 | 6662 | 71629 | 66874 | 22880 | 1387 | 69117 | 59608 | 7991 | 15064
Test | 4831 | 7604 | 590 | 3256 | 9767 | 7535 | 2480 | 180 | 17231 | 15006 | 1912 | 3796

Table 3: Training and testing sample sizes for CelebA and AdultIncome datasets
across labels (Label) and sensitive attributes (Gender).

We use the official train-test split for the CelebA dataset. For AdultIncome
and DutchConsensus, we use the train_test_split procedure of the scikit-learn
package with training-test set ratio of $0.8$ and random seed of 1 to generate
the training and test set. We tabulate the sizes for subgroups in Table 3.

##### Details on CelebA.

We use the same pre-processing steps as in [51] to crop the images in CelebA
into $224\times 224\times 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 [10] that ensures the
input as well as the columns of the wight matrix (with $2$ rows corresponding
to each label class) has norm $1$. This ensures our adjustments on the logits
are comparable. We use the Adam optimizer with learning rate $1\times 10^{-4}$
and weight decay $5\times 10^{-5}$ to train these models with stochastic
batches of sizes $128$. We performed pilot experiments and learnt 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 to roughly four epochs.

##### AdultIncome and DutchConsensus.

AdultIncome and DutchConsensus are two relatively smaller datasets that have
been used for benchmarking for various fair classification algorithms such as
[1]. We convert all categorical variables to dummies and use the standard
$z$-normalization to pre-process the data. There are $107$ features in
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 implement it as a one-layer neural net for
consistency concerns, which is trained using full-batch gradient descent using
Adam with learning rate $1\times 10^{-4}$ and weight decay $5\times 10^{-5}$
for $10000$ epochs. All models converge after this training measured by the
training metrics. Although the exact pre-processing procedures for these two
datasets are not available in [1], we found that on vanilla models under both
GridSearch and ExponentiatedGradient methods, the training and test
performance (measured by total accuracy and fairness violation) are comparable
with those reported in [1].

##### 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 on
AdultIncome and DutchConsensus takes less than ten minutes.

##  Appendix C Additional experimental results

###  C.1 A trajectory analysis on CelebA

(a) Total accuracy.

(b) Combined loss.

(c) Fairness violation.

(d) Balanced error.

Figure 7: Training and test trajectories of different metrics of ResNet-18 on
CelebA dataset under FIFA and vanilla losses respectively. We note that the
generalization performance of vanilla models are consistently poor as training
time increases, suggesting that it is difficult to cultivate an early-stopping
scheme that might alleviate poor fairness generalization.

One observation we made in Table 1 is that the improvements of the
generalization of combined loss on CelebA is largely due to the improved
generalization performance on fairness violations. It is 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 a 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.

To explore these two questions, we plot the trajectories of training and test
metrics for FIFA and vanilla (hyper-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 a reasonable early stopping criterion that improves
the generalization performances thereof.

###  C.2 CelebA and the DP constraint

We presented in Table 1 our main results, CelebA dataset trained with grid
search under EO constraint. We show in Table 4 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, we 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.

$\epsilon$ | Method | EO | DP
---|---|---|---
Combined Loss | Fairness Violation | Combined Loss | Fairness Violation
Train | Test | Train | Test | Train | Test | Train | Test
0.01 | FIFA | 7.37% | 6.71% | 5.31% | 2.75% | 8.65% | 7.21% | 4.84% | 1.45%
Vanilla | 7.14% | 14.01% | 6.69% | 20.29% | 10.74% | 10.43% | 4.72% | 1.35%
0.05 | FIFA | 5.46% | 6.34% | 2.63% | 3.29% | 10.02% | 9.40% | 4.73% | 1.07%
Vanilla | 8.84% | 13.05% | 9.45% | 17.92% | 12.14% | 11.60% | 8.34% | 5.17%
0.10 | FIFA | 5.92% | 6.54% | 3.11% | 2.65% | 9.04% | 8.32% | 2.98% | 0.04%
Vanilla | 8.90% | 16.71% | 11.37% | 26.15% | 12.13% | 11.66% | 9.77% | 6.83%

Table 4: Grid search with EO and DP constraint on CelebA dataset [44] using
ResNet-18, best results with respect to test combined loss among sweeps of
hyper-parameters are shown.

###  C.3 Grid search on AdultIncome (DP and EO)

$\epsilon$ | Method | EO | DP
---|---|---|---
Combined Loss | Fairness Violation | Combined Loss | Fairness Violation
Train | Test | Train | Test | Train | Test | Train | Test
0.01 | FIFA | 14.77618% | 14.93573% | 8.53851% | 8.50086% | 13.75700% | 14.05881% | 0.08609% | 0.00999%
Vanilla | 16.68724% | 17.28659% | 10.39000% | 10.92794% | 14.83347% | 15.09909% | 3.32436% | 3.65903%
0.05 | FIFA | 14.79263% | 14.91599% | 8.57436% | 8.50841% | 13.74952% | 14.03440% | 0.11811% | 0.01008%
Vanilla | 16.68724% | 17.28659% | 10.39000% | 10.92794% | 14.83475% | 15.09909% | 3.32895% | 3.65903%
0.10 | FIFA | 14.70959% | 14.88935% | 8.17597% | 8.16283% | 13.72278% | 14.03193% | 0.11331% | 0.01011%
Vanilla | 16.68724% | 17.28659% | 10.39000% | 10.92794% | 14.82782% | 15.09909% | 3.31507% | 3.65903%

Table 5: Grid search with EO and DP constraint on AdultIncome dataset using
logistic regression, best results with respect to test combined loss among
sweeps of hyper-parameters are shown.

We also give in Table 5 the grid search results on AdultIncome dataset, for
both EO and DP constraints. We observe that on this small dataset and small
model, FIFA can also improve generalization performances for both EO and DP
constraints. This further exhibits the flexibility of the FIFA approach.