# Minimax AUC Fairness: Efficient Algorithm with Provable Convergence

Zhenhuan Yang1 Yan Lok Ko1 Kush R. Varshney2 Yiming Ying1

###### Abstract

The use of machine learning models in consequential decision making often
exacerbates societal inequity, in particular yielding disparate impact on
members of marginalized groups defined by race and gender. The area under the
ROC curve (AUC) is widely used to evaluate the performance of a scoring
function in machine learning, but is studied in algorithmic fairness less than
other performance metrics. Due to the pairwise nature of the AUC, defining an
AUC-based group fairness metric is pairwise-dependent and may involve both
_intra-group_ and _inter-group_ AUCs. Importantly, considering only one
category of AUCs is not sufficient to mitigate unfairness in AUC optimization.
In this paper, we propose a minimax learning and bias mitigation framework
that incorporates both intra-group and inter-group AUCs while maintaining
utility. Based on this Rawlsian framework, we design an efficient stochastic
optimization algorithm and prove its convergence to the minimum group-level
AUC. We conduct numerical experiments on both synthetic and real-world
datasets to validate the effectiveness of the minimax framework and the
proposed optimization algorithm.

## Introduction

Recent years have witnessed an increasing recognition that allocation
decisions unfavorable to people from vulnerable groups (defined by sensitive
attributes such as race, gender, and age) worsen with the use of machine
learning. Alongside, a burgeoning set of mitigation algorithms has been
developed (Agarwal et al. 2018; Calders, Kamiran, and Pechenizkiy 2009; Calmon
et al. 2017; Chouldechova and Roth 2020; Donini et al. 2018; Hardt, Price, and
Srebro 2016; Lohia et al. 2019; Pleiss et al. 2017; Zafar et al. 2017).
Recognizing that they are only a small sliver of all actions that may be taken
when viewing the program of justice holistically, the aim of bias mitigation
is to ensure that the output of a classifier is not dependent on sensitive
attributes. Most existing work focuses on statistical fairness metrics
composed of entries of the classifier’s confusion matrix.

On another front of machine learning, the area under the ROC curve (AUC)
(Hanley and McNeil 1982) is one of the most widely used performance metrics in
classification tasks with class-imbalance and when the relative costs of false
positives and false negatives are difficult to pin down, and in bipartite
ranking tasks. Learning a scoring function by maximizing its AUC — instead of
the accuracy — has received increasing attention (Cortes and Mohri 2003; Gao
et al. 2013; Ying, Wen, and Lyu 2016; Liu et al. 2020; Lei and Ying 2021; Yang
and Ying 2022; Zhao et al. 2011). However, there is not yet much work on AUC-
related fairness in machine learning.

Properly defining group-level AUC fairness leads to two categories of metrics,
depending on the specific groups to which the positive and negative examples
belong. The first type, intra-group AUC, constrains both positive and negative
examples to the same group. The second type, inter-group AUC,111Kallus and
Zhou (2019) originally name this xAUC. computes the metric with positive and
negative examples being from different groups. On one hand, by only focusing
on intra-group AUC, one does not fully account for all possible disparate
impacts.222We use the term disparate impact in the general sense of inequality
in outcomes across groups, not in the specific sense of the ratio of selection
rates across groups. Indeed, as observed by Kallus and Zhou (2019), similar
intra-group AUCs may still lead to a disparate impact where positive examples
of one group are misranked below negative examples of another group. On the
other hand, we also witness from the synthetic experiment in Figure 1 that
solely relying on inter-group AUC fairness can overlook unfairness with
respect to the intra-group AUC.

(a) Inter-group ROC curves and Positive/negative KDE comparison

(b) Intra-group ROC curves and Positive/negative KDE comparison

Figure 1: Illustration of the discrepancy between inter-group AUC and intra-
group AUC. In this example, inter-group AUC is in a fair situation and intra-
group AUC is in an unfair situation. Here $f$ denotes the synthetic scoring
function sampled from Gaussian distribution and KDE denote the kernel density
estimation of $f$, $Y$ denotes the class label and $Z$ denotes the protected
attribute (see Appendix E for more details). In part (a), the gap of the peaks
in KDE is obvious. In part (b), the gap of the peaks is small and the overlap
is large when $Z=Z^{\prime}=a$, which indicates probability of positive sample
being misranked than negative sample is higher than $Z=Z^{\prime}=b$.

These two observations strongly suggest that to mitigate disparate impact when
the performance metric is the AUC score, one should consider _both_ inter- and
intra-group AUC fairness during the learning process.

In this paper, we follow the Rawlsian principle of maximin welfare for
distributive justice (Rawls 2001) and formalize our fairness goal as follows:

Find a scoring function that maximizes the minimum of inter-group AUC and
intra-group AUC.

Unlike usual discrimination-aware approaches that put constraints on the norm
of fairness metrics, the maximin principle does not introduce unnecessary harm
(Ustun, Liu, and Parkes 2019; Martinez, Bertran, and Sapiro 2020). Hence it is
more natural for our initial purpose of learning via AUC maximization.

Our main contributions are summarized as follows.

  1. 1.

We justify the necessity of simultaneously achieving fairness in terms of
intra-group and inter-group AUCs. We then propose a minimax learning framework
under the Rawlsian principle, collecting the objectives of both into one.

  2. 2.

We propose a stochastic algorithm that updates the model parameter by gradient
descent and the group weight by mirror ascent. We then prove the maximum re-
weighted group error is guaranteed to be minimized by our algorithm in the
nonconvex-concave setting.

  3. 3.

We conduct numerical experiments on real-world datasets. We demonstrate the
effectiveness of the minimax AUC fairness framework by observing substantial
utility improvement over the notion of equality of error rates, and also
fairness improvement over frameworks dealing with intra-group or inter-group
AUC alone.

### Related Work

Algorithmic fairness has received much attention recently, especially in the
context of classification. There are three main strategies for bias
mitigation: pre-processing the training data (Dwork et al. 2012; Feldman et
al. 2015; Calmon et al. 2017), enforcing fairness directly during the training
step (known as in-processing) (Kamishima, Akaho, and Sakuma 2011; Agarwal et
al. 2018; Donini et al. 2018), and post-processing the classifications (Hardt,
Price, and Srebro 2016; Pleiss et al. 2017; Lohia et al. 2019). Our work fits
in the middle category of in-processing.

#### AUC-Related Fairness Metrics.

Several works have attempted to address unfairness concerns in AUC-related
problems (See Appendix A for a complete discussion). Dixon et al. (2018)
propose the Pinned AUC fairness metric, which works by resampling the data
such that each of the two groups make up 50% of the data, and then calculating
the AUC on the resampled dataset. Beutel et al. (2019) propose ranking
pairwise fairness definitions and a methodology that regularizes the training
objective through a term that measures the correlation between the residual of
selected and unselected people. Kallus and Zhou (2019) observe inter-group AUC
(xAUC) unfairness in the COMPAS dataset and propose a post-processing approach
to achieve xAUC similarity. Narasimhan et al. (2020) propose a cross-group
fairness metric for general pairwise ranking problems and propose to maximize
AUC under cross-group fairness constraints. Vogel, Bellet, and Clémençon
(2021) define a fairness metric in terms of the ROC itself and propose a
regularization method to achieve fairness. It is worth mentioning that all of
the above works only focus on closing the gap of either intra-group metric or
inter-group metric, but ignore the interplay between them. Furthermore,
forcing unrealistic small group differences could harm the overall AUC
maximization target.

#### Minimax Principle in Algorithmic Fairness.

The Rawlsian principle has inspired several recent works to develop minimax
frameworks to mitigate the disparate impact of machine learning models during
training. In particular, Mohri, Sivek, and Suresh (2019) apply the agnostic
federated learning framework in the minimax group fairness context. Martinez,
Bertran, and Sapiro (2020) view the minimax fairness framework as a multi-
objective function and pursue the Pareto front solution. Lahoti et al. (2020)
study fairness without demographics and update group weights via adversarial
learning. Shekhar et al. (2021) propose an adaptive sampling algorithm based
on the principle of optimism to update group weights. Diana et al. (2021)
utilize minimax group errors as a fairness constraint upper bound for further
optimization.

The above minimax fairness frameworks all focus on classification and none has
considered the AUC metric. Thus, the work herein is unique in applying the
Rawlsian principle to AUC problems and considering both inter- and intra-group
AUC simultaneously.

## The Minimax Pairwise-Group Fairness Framework For Optimizing AUC

Let $X$ and $Y$ be two random variables. Here $Y\in\mathcal{Y}=\\{\pm 1\\}$
denotes the binary output label and $X\in\mathcal{X}$ denotes the input
features where $\mathcal{X}$ is a closed and bounded domain in
$\mathbb{R}^{d}$. Define a scoring function
$f_{\theta}:\mathcal{X}\rightarrow\mathbb{R}$, where $\theta$ is the model
parameter taking values in $\Theta$. The AUC of $f_{\theta}$ measures the
probability that it correctly ranks a positive example above a negative
example, i.e.,

$\operatorname{AUC}(f_{\theta})=\mathbb{E}[\mathbb{I}[f_{\theta}(X)>f_{\theta}(X^{\prime})]|Y=1,Y^{\prime}=-1],$
(1)

where $\mathbb{I}$ is the indicator function taking value $1$ when the event
is true, and $0$ otherwise. Observe that the definition (1) depends on a pair
of examples $(X,Y)$ and $(X^{\prime},Y^{\prime})$.

In the context of fairness, we consider a third random variable
$Z\in\mathcal{Z}$ to denote the sensitive group attribute, such as gender. For
notational simplicity, we restrict our current interest to the case of two
groups, i.e., $\mathcal{Z}=\\{a,b\\}$. However, our results can easily be
extended to the general setting of multiple groups. The distribution
$\mathcal{D}$ of the triplet $(X,Y,Z)$ can be expressed as a mixture of the
distributions of $X,Y|Z=z$. We define the group-level AUC as

$\operatorname{AUC}_{z,z^{\prime}}(f_{\theta})=\\\
\mathbb{E}[\mathbb{I}[f_{\theta}(X)\\!>\\!f_{\theta}(X^{\prime})]|Y\\!=\\!1,Y^{\prime}\\!=\\!-1,Z\\!=\\!z,Z^{\prime}\\!=\\!z^{\prime}].$

It is worth mentioning the group-level AUC naturally enjoys a pairwise
dependence w.r.t. groups $Z,Z^{\prime}$. Following the terminology in Beutel
et al. (2019), we name such group-level AUC as intra-group AUC when
$Z=Z^{\prime}$, and inter-group AUC when $Z\neq Z^{\prime}$. Previous work has
aimed for fairness in these definitions separately (Beutel et al. 2019; Kallus
and Zhou 2019; Narasimhan et al. 2020), i.e. either

$\displaystyle\operatorname{AUC}_{a,a}(f_{\theta})$
$\displaystyle=\operatorname{AUC}_{b,b}(f_{\theta}),\textrm{ or}$
$\displaystyle\operatorname{AUC}_{a,b}(f_{\theta})$
$\displaystyle=\operatorname{AUC}_{b,a}(f_{\theta}).$

However, if one only requires fair treatment in terms of intra-group (resp.
inter-group) AUCs, the model may still suffer from unfair treatment in terms
of inter-group (resp. intra-group) AUCs as argued by Kallus and Zhou (2019)
and Figure 1. To address this issue, one naive solution is to require fairness
in both of them so that
$\operatorname{AUC}_{a,a}(f_{\theta})\approx\operatorname{AUC}_{b,b}(f_{\theta})=\kappa_{1}$
and
$\operatorname{AUC}_{a,b}(f_{\theta})\approx\operatorname{AUC}_{b,a}(f_{\theta})=\kappa_{2}$.
However, the potential discrepancy of $\kappa_{1}\neq\kappa_{2}$ could also
lead to unfairness. We elaborate in the following practical example.

Consider finding qualified candidates with gender as the sensitive attribute.
In this scenario, AUC measures the probability of a qualified candidate being
ranked higher than an unqualified candidate. Assuming the fair intra-group AUC
is approximately 80%, which indicates the chance of a qualified female ranking
higher than an unqualified female is more or less the same 80% as the male.
Further assuming the fair inter-group AUC is approximately 60%, which means
the chance of a qualified female ranking higher than an unqualified male is
more or less the same 60% as the reverse case. Nevertheless, this leads to the
unfair situation that a qualified female ranking higher than an unqualified
male (60%) is lower than herself ranking higher than another unqualified
female (80%)! Moreover, if male candidates are the majority of the applicant
pool, her qualification is likely to be overwhelmed.

The above example demonstrates that disparity between intra-group AUCs and
inter-group AUCs should not be allowed. Ideally speaking, group-level AUC
fairness should be cast as

$\operatorname{AUC}_{a,a}(f_{\theta})\\!=\\!\operatorname{AUC}_{a,b}(f_{\theta})\\!=\\!\operatorname{AUC}_{b,a}(f_{\theta})\\!=\\!\operatorname{AUC}_{b,b}(f_{\theta}).$
(2)

In the fair hiring example, the above identity can be interpreted as

The chance of a qualified candidate from any gender ranking higher than an
unqualified candidate from any gender is the same.

While the above discussion naturally leads to a regularization or a
constrained optimization fairness scheme, we adapt the minimax fairness scheme
(Martinez, Bertran, and Sapiro 2020; Diana et al. 2021). To explain our
choice, we first decompose the overall AUC as a mixture of the intra-group and
the inter-group AUCs.

$\operatorname{AUC}(f_{\theta})=\sum_{z\in\mathcal{Z}}\mathbb{P}[Z=z,Z^{\prime}=z]\operatorname{AUC}_{z,z}(f_{\theta})\\\
+\sum_{z\neq
z^{\prime}}\mathbb{P}[Z=z,Z^{\prime}=z^{\prime}]\operatorname{AUC}_{z,z^{\prime}}(f_{\theta}),$

where $\mathbb{P}[Z,Z^{\prime}]$ is the prior distribution of a pair of
sensitive attributes. Recall that the target is to optimize AUC, or to
maximize the probability of a qualified candidate ranking higher than an
unqualifed one in the example. Eq. (The Minimax Pairwise-Group Fairness
Framework For Optimizing AUC) indicates that maximizing intra-group or inter-
group AUC does not conflict with the interest of this target. Therefore,
maximizing the minimum group-level AUC should preserve the utility in overall
AUC while boosting the similarity on Eq. (2). Based on the above discussion,
we are in position to formalize the learning problem in a maximin sense.

$\max_{\theta\in\Theta}\min_{z,z^{\prime}\in\mathcal{Z}}\operatorname{AUC}_{z,z^{\prime}}(f_{\theta}).$
(3)

Eq. (3) is intractable for two reasons. First, the true distribution
$\mathcal{D}$ is unknown. In practice, we only have access to a sample
$S=\\{S_{1},\cdots,S_{n}\\}$ drawn from $\mathcal{D}$. For convenience, we
denote $S_{i}\in S$ by $\mathbf{x}_{i}^{z+}$ (resp. $\mathbf{x}_{i}^{z-}$) if
it is coming from group $z$ with positive (resp. negative) label, we further
denote $S^{z+}=\\{\mathbf{x}_{i}^{z+}|i\in[n]\\}$ and
$S^{z-}=\\{\mathbf{x}_{i}^{z-}|i\in[n]\\}$ as two subsets of such examples. We
can therefore define the empirical group-level AUC as:

$\widehat{\operatorname{AUC}}_{z,z^{\prime}}(f)=\widehat{\operatorname{AUC}}(f;S^{z+},S^{z^{\prime}-})\\\
=\frac{1}{n^{z+}n^{z^{\prime}-}}\sum_{i=1}^{n^{z+}}\sum_{j=1}^{n^{z^{\prime}-}}\mathbb{I}[f_{\theta}(\mathbf{x}_{i}^{z+})>f_{\theta}(\mathbf{x}_{j}^{z^{\prime}-})],$

where $n^{z+}$ and $n^{z^{\prime}-}$ denote the number of samples from
$S^{z+},S^{z^{\prime}-}$, respectively. Furthermore, we replace the non-
differentiable indicator function $\mathbb{I}$ with some (sub)-differentiable
and non-increasing surrogate loss function $\ell$. Let
$\hat{R}^{\ell}_{z,z^{\prime}}=\hat{R}^{\ell}(\,\cdot\,;S^{z+},S^{z^{\prime}-})$
denote the $\ell$-surrogated empirical risk for AUC with group $z,z^{\prime}$.
And let
$\hat{R}^{\ell}(\cdot)=\hat{R}^{\ell}(\,\cdot\,;S)=(\hat{R}^{\ell}(\,\cdot\,;S^{z+},S^{z^{\prime}-}))_{z,z^{\prime}\in\\{a,b\\}}$.
The problem therefore becomes minimizing the largest group-level risk, which
can be formulated as

$\min_{\theta\in\Theta}\max_{z,z^{\prime}\in\mathcal{Z}}\hat{R}^{\ell}_{z,z^{\prime}}(\theta).$
(4)

The above problem is again non-differntiable. We introduce an additional
variable $\lambda\in\mathbb{R}^{4}$ and relax the problem as a zero-sum game
between two players $\theta$ and $\lambda$. At each round, player $\theta$
intends to find a better position to minimizes the weighted risk, while player
$\lambda$ assigns weights to each group that maximizes the weighted risk.
Formally speaking, we arrive at the following minimax problem

$\min_{\theta\in\Theta}\max_{\lambda\in\Lambda}F(\theta,\lambda)=\lambda^{\top}\hat{R}^{\ell}(\theta)=\sum_{z,z^{\prime}\in\mathcal{Z}}\lambda_{z,z^{\prime}}\hat{R}^{\ell}_{z,z^{\prime}}(\theta),$
(5)

where
$\Lambda=\\{\lambda\in\mathbb{R}^{4}|\sum_{z,z^{\prime}\in\mathcal{Z}}\lambda_{z,z^{\prime}}=1,\lambda_{z,z^{\prime}}\geq
0\\}$ is a $2\times 2$-dimensional simplex.

## Efficient Optimization Algorithm with Convergence Guarantee

In this section, we introduce a stochastic gradient method summarized in
Algorithm 1 to solve the minimax optimization problem (5).

Algorithm 1 MinimaxFairAUC

1: Inputs: Training set $S$ with label $Y$ and protected attribute $Z$, model
$f_{\theta}$, number of iterations $T$, batch size $m$, learning rates
$\\{\eta_{\theta},\eta_{\lambda}\\}$

2: Initialize $\theta_{0}\in\Theta$ and $\lambda_{0}\in\Lambda$ with
$\lambda_{z,z^{\prime}}=\frac{n^{z+}n^{z^{\prime}-}}{n^{+}n^{-}}$ for all
$z,z^{\prime}\in\mathcal{Z}$

3: for $t=1$ to $T-1$ do

4: $B_{t}=\texttt{StratifiedSampler}_{m}(S;Y,Z)$

5:
$\theta_{t}=\theta_{t-1}-\eta_{\theta}\lambda_{t-1}^{\top}\nabla\hat{R}^{\ell}(\theta_{t-1};B_{t})$

6:
$\gamma_{t}=\lambda_{t-1}\exp(\eta_{\lambda}\hat{R}^{\ell}(\theta_{t-1};B_{t}))$

7: $\lambda_{t}=\gamma_{t}/\|\gamma_{t}\|_{1}$

8: end for

9: Outputs: $\theta_{\tau}\sim\texttt{Unif}(\\{\theta_{t}\\}_{t=1}^{T})$

Let us illustrate Algorithm 1 in detail. At Line 4, the StratifiedSampler
operator randomly sub-samples mini-batch by dividing the training set $S$ into
strata based on the label and the group attribute. We note that this sub-
sampling scheme will later guarantee the stochastic gradients being unbiased
estimators of the full sample gradients, which is essential for the stochastic
optimization analysis. We summarize this result in the following proposition.

######  Proposition 1.

For any fixed $\theta\in\Theta$, let $B\subset S$ be given by
StratifiedSampler. The following statement holds

$\displaystyle\mathbb{E}_{B}[\hat{R}^{\ell}(\theta;B)]=$
$\displaystyle\hat{R}^{\ell}(\theta;S),$
$\displaystyle\mathbb{E}_{B}[\nabla\hat{R}^{\ell}(\theta;B)]=$
$\displaystyle\nabla\hat{R}^{\ell}(\theta;S).$

The detailed description of StratifiedSampler and the proof of Proposition 1
are deferred to Appendix B. While a uniform sampler over the full dataset $S$
also can be shown to construct unbiased estimators, this procedure can miss
certain groups or labels during training, especially when the dataset is
imbalanced in groups or labels (Shekhar et al. 2021).

At Line 5, the player $\theta$ performs stochastic gradient descent with
learning rate $\eta_{\theta}$. Here we slightly abuse the notation and use
$\lambda_{t}$ to denote the $t$-th iteration of $\lambda\in\mathbb{R}^{4}$. At
Line 6-7, the player $\lambda$ performs the well-known exponential weight
updates. For the purpose of convergence analysis, we note that the exponential
weight update is equivalent to mirror ascent when the mirror map
$\Phi:\Lambda\rightarrow\mathbb{R}$ is given by the negative entropy (Bubeck
et al. 2015), i.e.
$\Phi(\lambda)=\sum_{z,z^{\prime}\in\mathcal{Z}}\lambda_{z,z^{\prime}}\log(\lambda_{z,z^{\prime}})$.
The exact update is given by

$\displaystyle\nabla\Phi(\gamma_{t})=$
$\displaystyle\nabla\Phi(\lambda_{t-1})+\eta_{t}\hat{R}^{\ell}(\theta_{t-1};B_{t}),$
$\displaystyle\lambda_{t}=$
$\displaystyle\arg\min_{\lambda\in\Lambda}D_{\Phi}(\lambda\parallel\gamma_{t}),$

where
$D_{\Phi}(\lambda\parallel\lambda^{\prime})=\Phi(\lambda)-\Phi(\lambda^{\prime})-\nabla\Phi(\lambda^{\prime})^{\top}(\lambda-\lambda^{\prime})$
is the Bregman divergence associated with $\Phi$. Therefore, Algorithm 1 can
be viewed as a stochastic gradient descent mirror ascent method. Next we
introduce some standard assumptions for our convergence analysis.

######  Assumption 1.

For any $\theta\in\Theta$ and $\lambda\in\Lambda$, the gradients of $F$ are
bounded by $G_{\theta}$ and $G_{\lambda}$ respectively, i.e.
$\|\lambda^{\top}\nabla\hat{R}^{\ell}(\theta;S)\|_{2}\leq G_{\theta}$, and
$\|\hat{R}^{\ell}(\theta;S)\|_{\infty}\leq G_{\lambda}$.

######  Assumption 2.

The objective $F$ is $L_{\theta}$ and $L_{\lambda}$ smooth respectively, i.e.
$\|\lambda^{\top}\nabla\hat{R}^{\ell}(\theta;S)-\lambda^{\top}\nabla\hat{R}^{\ell}(\theta^{\prime};S)\|_{2}\leq
L_{\theta}\|\theta-\theta^{\prime}\|_{2}$ and
$\|\hat{R}^{\ell}(\theta;S)-\hat{R}^{\ell}(\theta^{\prime};S)\|_{\infty}\leq
L_{\theta}\|\lambda-\lambda^{\prime}\|_{1}$ for any
$\theta,\theta^{\prime}\in\Theta$ and $\lambda,\lambda^{\prime}\in\Lambda$.

######  Assumption 3.

For any fixed $\theta\in\Theta,\lambda\in\Lambda$ and randomly sampled pair
$\xi=\\{(x,y,z),(x^{\prime},y^{\prime},z^{\prime})\\}\\!\subset\\!S$, the
variances of the stochastic gradients of the function $F(\cdot,\cdot;\xi)$ are
bounded by $\sigma_{\theta}^{2}$ and $\sigma_{\lambda}^{2}$ respectively, i.e.
$\mathbb{E}_{\xi}[\|\lambda^{\top}\nabla\hat{R}^{\ell}(\theta;\xi)\\!-\\!\lambda^{\top}\nabla\hat{R}^{\ell}(\theta;S)\|_{2}^{2}]\\!\leq\\!\sigma_{\theta}^{2}$
and
$\mathbb{E}_{\xi}[\|\hat{R}^{\ell}(\theta;\xi)\\!-\\!\hat{R}^{\ell}(\theta;S)\|_{\infty}^{2}]\\!\leq\\!\sigma_{\lambda}^{2}$.

Denote $G=\max\\{G_{\theta},G_{\lambda}\\}$,
$L=\max\\{L_{\theta},L_{\lambda}\\}$ and
$\sigma=\max\\{\sigma_{\theta},\sigma_{\lambda}\\}$. Now let
$P(\theta)=\max_{\lambda\in\Lambda}F(\theta,\lambda)$. Its Moreau envelope
$P_{1/2L}$ is defined as
$P_{1/2L}(\omega)=\min_{\theta}P(\theta)+L\|\theta-\omega\|_{2}^{2}$. With the
above setup, we are in position to present the convergence of Algorithm 1.

######  Theorem 2 (Informal).

Suppose Assumption 1, 2 and 3 hold true. Then the output $\theta_{\tau}$ of
Algorithm 1 satisfies

$\mathbb{E}[\|\nabla
P_{1/2L}(\theta_{\tau})\|_{2}\leq\epsilon(T,\eta_{\theta},\eta_{\lambda}),$
(6)

where $\epsilon(T,\eta_{\theta},\eta_{\lambda})$ is an absolute constant. In
particular, to achieve some small
$\epsilon=\epsilon(T,\eta_{\theta},\eta_{\lambda})$, one choose
$\eta_{\theta}=\Theta(\epsilon^{4})$, $\eta_{\lambda}=\Theta(\epsilon^{2})$
and $T=\mathcal{O}(\epsilon^{-8})$. Furthermore, there exists
$\hat{\theta}\in\Theta$ such that
$\mathbb{E}[\|\hat{\theta}-\theta_{\tau}\|_{2}]\leq\epsilon/2L$ and it
satisfies

$\mathbb{E}[\min_{\xi\in\partial P(\hat{\theta})}\|\xi\|_{2}]\leq\epsilon.$
(7)

The exact statement and detailed proof are deferred to Appendix C. The proof
of Theorem 2 is non-trivial and consists of several intermediate lemmas. The
main idea is to derive a telescoping upper bound on the error term

$\Delta_{t}=\mathbb{E}_{B_{t}}[\max_{\lambda}F(\theta_{t},\lambda)-F(\theta_{t},\lambda_{t})]$

by utilizing the concavity of $F(\theta_{t},\cdot)$ and the Pythagorean
inequality w.r.t. the Bergman divergence $D_{\Phi}$. It is worth noting that
this result even holds for general nonconvex-concave problems over the
simplex, which is of interest in its own right. We end this section with
several remarks on the implications of Theorem 2 and the comparison of
Algorithm 1 with other minimax fairness algorithms.

######  Remark 1.

Eq. (6) characterizes the local gradient convergence of the output
$\theta_{\tau}$ on the Moreau envelope $P_{1/2L}$. Such a convergence bound
can be transferred to the objective at concern $P$ in (7) (Davis and
Drusvyatskiy 2019). We call $P$ the primal objective as it has been taken out
of the maximization on the dual variable $\lambda\in\Lambda$. In the ideal
case, the group weights $\lambda$ only represent the maximum group risk.
Therefore the convergence on the primal objective is exactly seeking the
(local) minimum of the maximum group risk, defined as the original problem
(4). Furthermore, the primal objective also provides guidance on the stopping
criterion in empirical evaluations, which is known to be vague for general
minimax optimization. That is, to stop when the maximum group-level AUC risk
is saturated.

######  Remark 2.

One of the main focuses of minimax fairness algorithms is how to update the
model parameter and the group weights. The most closely related algorithm by
Diana et al. (2021) also applies the exponential weights update on the group
weights. However, the model update in that algorithm requires the exact
solution on the weighted group risks at each iteration. This is time-
consuming, aside from being intractable in most cases. On the contrary,
Algorithm 1 is iteration-efficient as it alternately updates the model
parameter and the group weight based on the stochastic mini-batch. The
stochastic gradient method in Martinez, Bertran, and Sapiro (2020) relieves
the intractability, yet still require a computationally-expensive inner loop
to update the model parameter. Moreover, since the algorithm is heuristic, the
authors provide no convergence analysis. Mohri, Sivek, and Suresh (2019) also
apply an efficient stochastic optimization algorithm by updating the group
weights by stochastic gradient ascent. However, such an update is sub-optimal
compared to our stochastic mirror ascent on simplex (Beck and Teboulle 2003).
Furthermore, their convergence relies on a convexity assumption while our
results hold for the general nonconvex model class. Finally, it is worth
noting the above minimax fairness frameworks all focus on classification and
confusion matrix-based metrics; our algorithm is the first for group-level
AUCs.

## Empirical Evaluations

In this section, we evaluate the performance of Algorithm 1 in terms of
utility and fairness.

(a) Adult

(b) Bank

(c) COMPAS

(d) Default

Figure 2: Convergence plots on training set (upper half) and ROC plots on test
set (lower half) of Algorithm 1 (solid curves) versus AUCMax (dashed curves).
For convergence plots, the x-axis indicates the number of epochs, and the
y-axis indicates the AUC score. For ROC plots, the x-axis indicates the FPR
and the y-axis indicates the TPR.

### Experimental Details

Datasets Information and Feature Engineering. We evaluate our algorithms on
four datasets that have been commonly used in the fair machine learning
literature (Zafar et al. 2017; Donini et al. 2018). The summary statistics of
the datasets are given in Table 1.

  * •

The Adult dataset is based on US census data and consists in predicting
whether income exceeds $\$50K$ a year. The sensitive attribute is the gender
of the individual, i.e. female ($Z=a$) or male ($Z=b$).

  * •

The Bank dataset consists in predicting whether a client will subscribe to a
term deposit. The sensitive attribute is the age of the individual: $Z=a$ when
the age is less than 25 or over 60 and $Z=b$ otherwise.

  * •

The Compas dataset consists in predicting recidivism of convicts in the US.
The sensitive variable is the race of the individual, precisely $Z=a$ if the
individual is categorized as non Caucasian and $Z=b$ if the individual is
categorized as Caucasian.

  * •

The Default dataset (Yeh and Lien 2009) investigates customers’ default
payments. The goal is to predict whether a customer will face the default
situation in the next month or not. The sensitive attribute is the gender of
the individual, i.e. female ($Z=a$) or male ($Z=b$).

Name | # instances | # attributes | Group ratio | Class ratio
---|---|---|---|---
Adult | 48,842 | 15 | 0.48:1 | 3.03:1
Bank | 41,188 | 21 | 0.05:1 | 7.55:1
Compas | 11,757 | 53 | 1.86:1 | 1.94:1
Default | 30,000 | 24 | 1.52:1 | 3.52:1
Table 1: Dataset Statistics. The group ratio is given by the protective
attribute $Z=a$ versus $Z=b$. The Class ratio is given by negative versus
positive class.

We partition the datasets and use 60% for training, 20% for validation and 20%
for testing. We apply one-hot encoding to all categorical attributes.

#### Choice of Models and Loss Functions.

To parameterize the family of scoring functions, we used a simple neural
network of 2 hidden layers. Each layer has the same width $d$ (the dimension
of the input space), except for the output layer which outputs a real score.
We used ReLU’s as activation functions after each layer except for the output
layer. To center and scale the output score we used batch normalization (BN)
with fixed values $\gamma=1,\beta=0$ for the output value of the network. The
surrogate loss function $\ell$ is chosen as the logistic loss, i.e.
$\ell:s\mapsto\log(1+\exp(-s))$.

#### Baselines.

We compare our framework with three in-processing baselines that have been
proposed to 1) achieve fair group-level AUC scores; or 2) address unfair
impact in terms of the Rawlsian principle.

  * •

The AUCMax algorithm conducts AUC maximization on the full dataset without
differentiating any groups. It updates the model parameter by mini-batch SGD.

  * •

The MinimaxFair algorithm by Diana et al. (2021) aims to minimize the maximum
group-level misclassification error.

  * •

There are regularization methods (Beutel et al. 2019) or constrained
optimization methods (Narasimhan et al. 2020) targeting inter-group AUC
fairness. We pick the one by Vogel, Bellet, and Clémençon (2021) as a
representative since the authors considered the same datasets. Vogel, Bellet,
and Clémençon learn fair AUC scores by regularization on the difference of
inter-group AUCs, which we refer to as InterFairAUC.

  * •

We also consider AUC maximization under the constraint of (2) as an
alternative to our AUC fairness criterion. We name this algorithm EqualAUC.
See Appendix D for details.

#### Implementation Details.

The batch size $|B|$, initial stepsizes $\eta^{\theta}_{0},\eta^{\lambda}_{0}$
and other hyperparameters are chosen based on the validation set of each
dataset. For Algorithm 1, early stopping is implemented based on the maximum
group loss over the validation set. We repeat each experiment over 25 runs of
different random seeds and report the average result on the testing set. More
details are given in Appendix E.

### Results on Real Datasets

We first investigate the convergence property of Algorithm 1. We initialize
the model parameters $\theta_{0}$ as the one trained from AUCMax to better
illustrate the improvement over the baseline. As shown in Figure 2 upper half,
the inter-group AUC unfairness is prevalent in all four datasets, and intra-
group AUC unfairness exists in Adult and Bank. When there is only inter-group
AUC unfairness, Algorithm 1 mainly lifts the lowest inter-group AUC score.
This can potentially benefit intra-group AUC (cf. Compas and Default.) When
both intra-group and inter-group AUC unfairness exist, Algorithm 1 alternately
lifts the lowest AUCs from inter-group then from intra-group, leading to a
smaller gap in both of them separately. We next investigate the
generalization/test performance of Algorithm 1. In Figure 2 lower half, the
ROC curves of Algorithm 1 narrows the gaps of AUCMax towards the middle.

We next develop a quantitative understanding of Algorithm 1 on its utility and
fairness performance. We apply the same network in Algorithm 1 and all other
baselines for the purpose of fair comparison. Such model update in MinimaxFair
is intractible hence we replace it by 10 epochs of SGD. First, as shown in
Table 2, MinimaxFair struggles on both metrics. This is due to the objective
differences: MinimaxFair is aiming at classification and the disparity in
accuracy. Therefore it may overlook the disparity caused by group-level AUCs.
InterFairAUC does not perform too well on fairness as expected. This is
because the regularization only focuses on the difference of inter-group AUCs
and eventually the unfairness of intra-group AUCs will dominate the min/max
ratio, especially on Adult and Bank where original gaps of intra-group AUCs
are large. It only increase the overall AUC on Bank because the dataset is
imbalanced. EqualAUC achieves the highest min/max ratios on all datasets.
However it suffers from a large utility drop compared to the non-fairness
intended baseline AUCMax. Algorithm 1 preserves the largest overall AUC
scores. It achieves over 99% on Adult and Bank compared to AUCMax, and
achieves even higher score on Compas and Default. This phenomenon is
consistent with our argument in (3) that the proposed minimax objective does
not conflict with AUC maximization. The further improvement may due to the
initialization via AUCMax. In the meantime, for the fairness measurement,
Algorithm 1 provides a competitive min/max ratio versus EqualAUC. On Bank,
Algorithm 1 has better trade-off between utility and fairness than EqualAUC
since the overall AUC is preserved. On Compas, Algorithm 1 even reaches the
best overall score and the ratio simultaneously.

| Adult | Bank | Compas | Default
---|---|---|---|---
Algorithm Metric | Overall | Min/Max | Overall | Min/Max | Overall | Min/Max | Overall | Min/Max
AUCMax | $\mathbf{.902\pm.002}$ | $.823\pm.005$ | $\underline{.910\pm.002}$ | $.780\pm.018$ | $.732\pm.004$ | $.779\pm.041$ | $.763\pm.005$ | $.871\pm.017$
MinimaxFair | $.894\pm.007$ | $.905\pm.010$ | $.885\pm.003$ | $.827\pm.004$ | $.730\pm.001$ | $.913\pm.029$ | $.753\pm.002$ | $.909\pm.021$
InterFairAUC | $.894\pm.004$ | $.950\pm.003$ | $\mathbf{.912\pm.001}$ | $.836\pm.018$ | $\underline{.738\pm.003}$ | $.939\pm.014$ | $\underline{.763\pm.003}$ | $.952\pm.024$
EqualAUC | $.886\pm.003$ | $\mathbf{.953\pm.004}$ | $.866\pm.005$ | $\mathbf{.893\pm.023}$ | $.731\pm.003$ | $\underline{.956\pm.012}$ | $\underline{.761\pm.002}$ | $\mathbf{.972\pm.020}$
Algorithm 1 | $\underline{.901\pm.004}$ | $\underline{.953\pm.002}$ | $.907\pm.004$ | $\underline{.852\pm.013}$ | $\mathbf{.741\pm.004}$ | $\mathbf{.961\pm.012}$ | $\mathbf{.767\pm.002}$ | $\underline{.968\pm.013}$
Table 2: Comparison of Algorithm 1 versus baselines. ’Overall’ is the AUC
score on the full dataset, measuring the utility. ’Min/Max’ is the minimum
group-level AUC score over the maximum one, measuring the fairness. The
numbers are reported as ’Mean $\pm$ Standard Deviation’. Best results at each
column are highlighted in bold. Second best are highlighted in underline.
Figure 3: Experiments on synthetic datasets. Dashed curves are baseline
results via AUCMax.

### Synthetic Datasets Experiments

(a) Intra-group AUCs only

(b) Inter-group AUCs only

Figure 4: Ablation study of Algorithm 1 (solid curves) versus AUCMax (dashed
curves) on Adult.

In this subsection, we design synthetic datasets to further understand the
effectiveness of minimax AUC Algorithm 1 versus the unfair baseline. In
particular, we generate two dimensional data points from different Gaussian
distributions conditioned on the class label and the group attribute. See
Appendix E for more details. The generated data points are shown in the left
most plot in Figure 3. We generate the same number of samples for each label
and group partition so that the priors in (The Minimax Pairwise-Group Fairness
Framework For Optimizing AUC) can be ignored and all group-level AUCs
contribute the same towards the overall AUC. Furthermore, we intentionally
design the overlap between the positive and negative samples for group $a$ so
that the scoring function faces difficulty differentiating them. As we see
from the middle left plot in Figure 3, the baseline AUCMax learns almost
nothing from group $a$ as the positive and negative KDEs are largely
overlapped. Yet this fact does not stop the algorithm from maximizing the
overall AUC as it keeps the negative KDE from group $b$ low. Therefore all
three $AUC_{a,b},AUC_{b,a},AUC_{b,b}$ are optimized except $AUC_{a,a}$.
However this is severely unfair for the positive sample from group $a$.
Algorithm 1 mitigates this issue by separating the positive and negative KDEs
from group $a$ to the correct direction. It also pushes the negative KDE from
group $b$ to be lower so that positives from group $a$ maintain higher scores
than negatives from group $b$. This is based on the sacrifice of the
positives’ scores from group $b$. Yet it may be acceptable as they are
originally high enough.

### Ablation Studies

In this subsection, we apply Algorithm 1 on the maximin AUC problem (3) with
only intra-group AUCs or inter-group AUCs. We only report the results on Adult
due to space limits. See Appendix E for results on other datasets. In Figure
4(a), when intra-group AUCs are the only objective, Algorithm 1 slightly
mitigates the intra-group AUC unfairness, yet it can potentially help mitigate
the inter-group AUC unfairness as well. However, this improvement is very
limited compared to lower half in Figure 2(a), where the unfairness is almost
eliminated. In Figure 4(b), when inter-group AUCs are the only objective,
inter-group fairness is more or less achieved with crossing of two curves, yet
it is not guaranteed to mitigate the unfairness within intra-group AUCs.

## Conclusion

In this paper, we propose a minimax learning framework for AUC maximization
with fairness concern. Our framework addresses both intra-group and inter-
group AUC unfairness as well as the discrepancy in between. Based on this
framework, we design Algorithm 1: an efficient algorithm with stochastic
gradient descent on the model and mirror ascent on the group weights. We
provide a non-trivial analysis and show that Algorithm 1 converges to the
optimal solution in terms of the minimum group-level AUC in the nonconvex-
concave setting. We conduct numerical experiments on both synthetic and real-
world datasets to validate the utility and the fairness performance of the
approach. One interesting future direction is to consider fairness metrics
involving group-level partial AUCs.

## Acknowledgement

This work is supported by SUNY-IBM AI Alliance Research and NSF grants
(IIS-2103450, IIS-2110546 and DMS-2110836).

## References

  * Agarwal et al. (2018) Agarwal, A.; Beygelzimer, A.; Dudík, M.; Langford, J.; and Wallach, H. 2018\.  A reductions approach to fair classification.  In _International Conference on Machine Learning_ , 60–69. PMLR.
  * Beck and Teboulle (2003) Beck, A.; and Teboulle, M. 2003.  Mirror descent and nonlinear projected subgradient methods for convex optimization.  _Operations Research Letters_ , 31(3): 167–175.
  * Beutel et al. (2019) Beutel, A.; Chen, J.; Doshi, T.; Qian, H.; Wei, L.; Wu, Y.; Heldt, L.; Zhao, Z.; Hong, L.; Chi, E. H.; et al. 2019.  Fairness in recommendation ranking through pairwise comparisons.  In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2212–2220.
  * Borkan et al. (2019) Borkan, D.; Dixon, L.; Sorensen, J.; Thain, N.; and Vasserman, L. 2019.  Nuanced metrics for measuring unintended bias with real data for text classification.  In _Companion proceedings of the 2019 world wide web conference_ , 491–500.
  * Bubeck et al. (2015) Bubeck, S.; et al. 2015.  Convex optimization: Algorithms and complexity.  _Foundations and Trends® in Machine Learning_ , 8(3-4): 231–357.
  * Calders, Kamiran, and Pechenizkiy (2009) Calders, T.; Kamiran, F.; and Pechenizkiy, M. 2009.  Building classifiers with independency constraints.  In _2009 IEEE International Conference on Data Mining Workshops_ , 13–18. IEEE.
  * Calmon et al. (2017) Calmon, F.; Wei, D.; Vinzamuri, B.; Natesan Ramamurthy, K.; and Varshney, K. R. 2017\.  Optimized pre-processing for discrimination prevention.  _Advances in neural information processing systems_ , 30.
  * Chouldechova and Roth (2020) Chouldechova, A.; and Roth, A. 2020.  A snapshot of the frontiers of fairness in machine learning.  _Communications of the ACM_ , 63(5): 82–89.
  * Clémençon, Lugosi, and Vayatis (2008) Clémençon, S.; Lugosi, G.; and Vayatis, N. 2008.  Ranking and empirical minimization of U-statistics.  _The Annals of Statistics_ , 36(2): 844–874.
  * Cortes and Mohri (2003) Cortes, C.; and Mohri, M. 2003.  AUC Optimization vs. Error Rate Minimization.  In _NIPS_.
  * Davis and Drusvyatskiy (2019) Davis, D.; and Drusvyatskiy, D. 2019.  Stochastic model-based minimization of weakly convex functions.  _SIAM Journal on Optimization_ , 29(1): 207–239.
  * Diana et al. (2021) Diana, E.; Gill, W.; Kearns, M.; Kenthapadi, K.; and Roth, A. 2021.  Minimax group fairness: Algorithms and experiments.  In _Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society_ , 66–76.
  * Dixon et al. (2018) Dixon, L.; Li, J.; Sorensen, J.; Thain, N.; and Vasserman, L. 2018.  Measuring and mitigating unintended bias in text classification.  In _Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society_ , 67–73.
  * Donini et al. (2018) Donini, M.; Oneto, L.; Ben-David, S.; Shawe-Taylor, J. S.; and Pontil, M. 2018.  Empirical risk minimization under fairness constraints.  _Advances in Neural Information Processing Systems_ , 31.
  * Dwork et al. (2012) Dwork, C.; Hardt, M.; Pitassi, T.; Reingold, O.; and Zemel, R. 2012.  Fairness through awareness.  In _Proceedings of the 3rd innovations in theoretical computer science conference_ , 214–226.
  * Feldman et al. (2015) Feldman, M.; Friedler, S. A.; Moeller, J.; Scheidegger, C.; and Venkatasubramanian, S. 2015.  Certifying and removing disparate impact.  In _proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining_ , 259–268.
  * Gao et al. (2013) Gao, W.; Jin, R.; Zhu, S.; and Zhou, Z.-H. 2013.  One-pass AUC optimization.  In _International conference on machine learning_ , 906–914.
  * Hanley and McNeil (1982) Hanley, J. A.; and McNeil, B. J. 1982.  The meaning and use of the area under a receiver operating characteristic (ROC) curve.  _Radiology_ , 143(1): 29–36.
  * Hardt, Price, and Srebro (2016) Hardt, M.; Price, E.; and Srebro, N. 2016.  Equality of opportunity in supervised learning.  _Advances in neural information processing systems_ , 29.
  * Kallus and Zhou (2019) Kallus, N.; and Zhou, A. 2019.  The fairness of risk scores beyond classification: Bipartite ranking and the xauc metric.  _Advances in neural information processing systems_ , 32.
  * Kamishima, Akaho, and Sakuma (2011) Kamishima, T.; Akaho, S.; and Sakuma, J. 2011.  Fairness-aware learning through regularization approach.  In _2011 IEEE 11th International Conference on Data Mining Workshops_ , 643–650. IEEE.
  * Lahoti et al. (2020) Lahoti, P.; Beutel, A.; Chen, J.; Lee, K.; Prost, F.; Thain, N.; Wang, X.; and Chi, E. 2020.  Fairness without demographics through adversarially reweighted learning.  _Advances in neural information processing systems_ , 33: 728–740.
  * Lei and Ying (2021) Lei, Y.; and Ying, Y. 2021.  Stochastic Proximal AUC Maximization.  _J. Mach. Learn. Res._ , 22(61): 1–45.
  * Lin, Jin, and Jordan (2020) Lin, T.; Jin, C.; and Jordan, M. I. 2020.  On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems.  In _Proceedings of the 37th International Conference on Machine Learning (ICML)_ , 6083–6093.
  * Liu et al. (2020) Liu, M.; Yuan, Z.; Ying, Y.; and Yang, T. 2020.  Stochastic AUC Maximization with Deep Neural Networks.  In _8th International Conference on Learning Representations (ICLR)_.
  * Lohia et al. (2019) Lohia, P. K.; Ramamurthy, K. N.; Bhide, M.; Saha, D.; Varshney, K. R.; and Puri, R. 2019.  Bias mitigation post-processing for individual and group fairness.  In _Icassp 2019-2019 ieee international conference on acoustics, speech and signal processing (icassp)_ , 2847–2851. IEEE.
  * Martinez, Bertran, and Sapiro (2020) Martinez, N.; Bertran, M.; and Sapiro, G. 2020.  Minimax pareto fairness: A multi objective perspective.  In _International Conference on Machine Learning_ , 6755–6764. PMLR.
  * Mohri, Sivek, and Suresh (2019) Mohri, M.; Sivek, G.; and Suresh, A. T. 2019.  Agnostic federated learning.  In _International Conference on Machine Learning_ , 4615–4625. PMLR.
  * Narasimhan et al. (2020) Narasimhan, H.; Cotter, A.; Gupta, M.; and Wang, S. 2020.  Pairwise fairness for ranking and regression.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34(04), 5248–5255.
  * Pleiss et al. (2017) Pleiss, G.; Raghavan, M.; Wu, F.; Kleinberg, J.; and Weinberger, K. Q. 2017.  On fairness and calibration.  _Advances in neural information processing systems_ , 30.
  * Rawls (2001) Rawls, J. 2001.  _Justice as fairness: A restatement_.  Harvard University Press.
  * Shekhar et al. (2021) Shekhar, S.; Fields, G.; Ghavamzadeh, M.; and Javidi, T. 2021.  Adaptive sampling for minimax fair classification.  _Advances in Neural Information Processing Systems_ , 34: 24535–24544.
  * Ustun, Liu, and Parkes (2019) Ustun, B.; Liu, Y.; and Parkes, D. 2019.  Fairness without harm: Decoupled classifiers with preference guarantees.  In _International Conference on Machine Learning_ , 6373–6382. PMLR.
  * Vogel, Bellet, and Clémençon (2021) Vogel, R.; Bellet, A.; and Clémençon, S. 2021.  Learning fair scoring functions: Bipartite ranking under ROC-based fairness constraints.  In _International Conference on Artificial Intelligence and Statistics_ , 784–792. PMLR.
  * Yang and Ying (2022) Yang, T.; and Ying, Y. 2022.  AUC maximization in the era of big data and AI: A survey.  _ACM Computing Surveys (CSUR)_.
  * Yeh and Lien (2009) Yeh, I.-C.; and Lien, C.-h. 2009.  The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients.  _Expert systems with applications_ , 36(2): 2473–2480.
  * Ying, Wen, and Lyu (2016) Ying, Y.; Wen, L.; and Lyu, S. 2016.  Stochastic online AUC maximization.  _Advances in neural information processing systems_ , 29.
  * Zafar et al. (2017) Zafar, M. B.; Valera, I.; Gomez Rodriguez, M.; and Gummadi, K. P. 2017.  Fairness beyond disparate treatment & disparate impact: Learning classification without disparate mistreatment.  In _Proceedings of the 26th international conference on world wide web_ , 1171–1180.
  * Zhao et al. (2011) Zhao, P.; Hoi, S. C. H.; Jin, R.; and Yang, T. 2011.  Online AUC Maximization.  In _ICML_ , 233–240.

Appendix for ”Minimax AUC Fairness: Efficient Algorithm with Provable
Convergence”

##  Appendix A AUC Related Fairness Metrics

In this section, we provide throughout discussion on the related work which
define and address unfairness concerns in AUC-related problems in the
literature. We apply the notation in the main text for consistency.

Borkan et al. (2019) is one of the first work which study the intra-group AUC
fairness under the name of subgroup AUC fairness. Dixon et al. (2018) also
target at similar intra-group AUC scores but is defined based on subsampling
$B\subset S$, so that

$\widehat{\operatorname{AUC}}(f_{\theta};B^{z^{+}},B^{z-})=\widehat{\operatorname{AUC}}(f_{\theta};B^{z^{\prime}+},B^{z^{\prime}-}),$

where $|B^{z+}|+|B^{z-}|=|B^{z^{\prime}+}|+|B^{z^{\prime}-}|$ is required. For
inter-group AUC fairness, Kallus and Zhou (2019) observe the unfairness in
this cross group definition. Beutel et al. (2019) define both of these
pairwise fairness metrics in the task of pairwise ranking for recommendation
systems, which are named intra-group pairiwse accuracy and inter-group
pairwise accuracy originally in their work. In an independent work, Narasimhan
et al. (2020) also study intra-group and inter-group pairwise accuracy. It is
worth noting that they briefly mention the fairness metric

$\operatorname{AUC}_{z,z^{\prime}}=\kappa,\forall z,z^{\prime}\in\mathcal{Z},$

which coincides with our Eq. (2) to a large extent. Such identity is named as
pairwise equal opportunity in their work, as an analogy of the equal
opportunity for the binary classification task (Hardt, Price, and Srebro
2016).

Our work is different from the work (Narasimhan et al. 2020) in the following
aspects. Firstly, the motivation and application setting are unrelated.
Narasimhan et al. (2020) consider pairwise ranking task whereas we focus on
AUC maximization, which can be applied to in bipartite ranking and imbalanced
classification tasks. Moreover, we provide a concrete application scenario
(cf. fair hiring) to justify the necessity of debiasing all group-level AUCs.
Secondly, our learning objective and theirs are not the same. Narasimhan et
al. (2020) integrates the discrepancy of group-level AUCs into their framework
as either constrained optimization or robust optimization problem. This is
because their fairness metric naturally requires an pre-defined ”fairness
level” $\kappa$, which could be difficult to determine before
training/learning. On the other hand, our learning objective actually put both
intra- and inter- group AUCs inside following the Rawlsian principle, which
does not depend on the choice of ”fairness level” and hence does not introduce
additional harm towards the AUC maximization goal. Thirdly, the training
procedure is different. Narasimhan et al. also apply a minimax framework to
train their model. However, the minimax reformulation there is based on the
introduction of Lagrange multipliers and it still solves the original
constrained optimization problem, such minimax problem can have a vague
stopping criterion especially when the model complexity is high (e.g. deep
neural networks). As we argued in Remark 1, our convergence analysis provides
a natural stopping criterion for the algorithm by looking at the saturation of
the maximum group-level AUC, even for the nonconvex problem involving deep
neural networks. Finally, there are experimental differences between our work
and Narasimhan et al. (2020). For the ranking task with discrete groups,
Narasimhan et al. only consider either inter-group AUC fairness or BNSP which
we will introduce later. As we discussed in Figure 1 and observed in our
experiment, this treatment can overlook the concern of intra-group AUC
fairness, whereas our approach can handle both intra-group and inter-group AUC
fairness as demonstrated in the experiments on the datasets of Adult and Bank.

There are AUC related fairness metrics beyond intra-group and inter-group
AUCs. Borkan et al. (2019) propose 1) the Backgroup Negative Subgroup Positice
(BNSP) AUC fairness,

$\widehat{\operatorname{AUC}}(f_{\theta};S^{z+},S^{-})=\widehat{\operatorname{AUC}}(f_{\theta};S^{z^{\prime}+},S^{-})$

which enforces that the positive example from any group has the same
probability of being ranked higher than a negative example, and 2) the
Backgroup Positive Subgroup Negative (BPSN) AUC fairness,

$\widehat{\operatorname{AUC}}(f_{\theta};S^{+},S^{z-})=\widehat{\operatorname{AUC}}(f_{\theta};S^{+},S^{z^{\prime}-}),$

which can be viewed as the ranking extension of parity in false positive rates
in binary classification (Hardt, Price, and Srebro 2016). Vogel, Bellet, and
Clémençon (2021) extend all the discussion above into ROC based fairness
metrics. Note that group level TPR and FPR are given as

$\displaystyle\operatorname{TPR}_{z}(t,f_{\theta})=$
$\displaystyle\mathbb{P}[f_{\theta}(X)>t|Y=1,Z=z],$
$\displaystyle\operatorname{FPR}_{z}(t,f_{\theta})=$
$\displaystyle\mathbb{P}[f_{\theta}(X)>t|Y=-1,Z=z].$

The ROC curve is then defined as the plot of
$\operatorname{TPR}(t,f_{\theta})$ against $\operatorname{FPR}(t,f_{\theta})$
for different values of $t$, i.e., for $t\in[0,1]$, group level ROC is given
as

$\text{ROC}_{z,z^{\prime}}:t\mapsto\operatorname{TPR}_{z}\circ\operatorname{FPR}_{z^{\prime}}^{-1}(t).$

Consider the intra-group ROC fairness as an example. It can be similarly
defined as the AUC case as follows

$\text{ROC}_{a,a}(t)=\text{ROC}_{b,b}(t),\quad\forall t\in[0,1].$

##  Appendix B Stratified Random Sampling

In this section, we introduce the StratifiedSampler used in Algorithm 1 and
prove the unbiasedness of subsampled gradients in Proposition 1. The
StratifiedSampler is described in Algorithm 2.

Algorithm 2 Per Group and Label Stratified Sampler

1: Inputs: Dataset $S$ with label $Y$ and protected attribute $Z$, batch size
$m$

2: for $z\in\\{a,b\\}$ and $y\in\\{\pm 1\\}$ do

3: Uniformly sample without replacement $B^{zy}$ from $S^{zy}$ with size
$m^{zy}\coloneqq\lceil m\cdot(n^{zy}/n)\rceil$

4: end for

5: Outputs: $B=\cup_{z,y}B^{zy}$

The next proposition shows that the stochastic gradients constructed by
Algorithm 2 are unbiased estimators of the full sample gradients. The proof is
inspired by classical U-statistics theory (Clémençon, Lugosi, and Vayatis
2008).

######  Proposition B.1 (Proposition 1 restated).

For any fixed $\theta\in\Theta$. Let $B\subset S$ be given by Algorithm 2. The
following statement holds

$\displaystyle\mathbb{E}_{B}[\hat{R}^{\ell}(\theta;B)]=$
$\displaystyle\hat{R}^{\ell}(\theta;S),$
$\displaystyle\mathbb{E}_{B}[\nabla\hat{R}^{\ell}(\theta;B)]=$
$\displaystyle\nabla\hat{R}^{\ell}(\theta;S).$

###### Proof.

The gradient w.r.t. $\lambda$ is given by

$(\partial_{\lambda}F(\theta,\lambda;S))_{z,z^{\prime}}=\partial_{\lambda_{z,z^{\prime}}}F(\theta,\lambda;S^{z+}\cup
S^{z^{\prime}-})=\frac{1}{n^{z+}}\frac{1}{n^{z^{\prime}-}}\sum_{i=1}^{n^{z+}}\sum_{j=1}^{n^{z^{\prime}-}}\ell(f_{\theta}(\mathbf{x}_{i}^{z+})-f_{\theta}(\mathbf{x}_{j}^{z^{\prime}-})),\,\forall
z,z^{\prime}\in\mathcal{Z},$

and the gradient w.r.t. $\theta$ is given by

$\partial_{\theta}F(\theta,\lambda;S)=\sum_{z=1}^{k}\sum_{z^{\prime}=1}^{k}\lambda_{z,z^{\prime}}\partial_{\theta}\hat{R}^{\ell}(\theta;S^{z+}\cup
S^{z^{\prime}-})=\sum_{z=1}^{k}\sum_{z^{\prime}=1}^{k}\frac{\lambda_{z,z^{\prime}}}{n^{z+}n^{z^{\prime}-}}\sum_{i=1}^{n^{z+}}\sum_{j=1}^{n^{z^{\prime}-}}\nabla_{\theta}\ell(f_{\theta}(\mathbf{x}_{i}^{z+})-f_{\theta}(\mathbf{x}_{j}^{z^{\prime}-})).$

We first consider the proof on the gradient w.r.t. $\lambda$. In particular,
the expectation of the stochastic gradient w.r.t. $\lambda$ is given by

$\displaystyle\mathbb{E}_{B\sim\texttt{Alg \ref{alg:group-label-
sampler}}}[\partial_{\lambda}F(\theta,\lambda;B)]_{z,z^{\prime}}=\mathbb{E}_{B^{z+},B^{z^{\prime}-}}[\partial_{\lambda_{z,z^{\prime}}}F(\theta,\lambda;B^{z+}\cup
B^{z^{\prime}-})]$ $\displaystyle=$ $\displaystyle\sum_{B^{z+}\subset
S^{z+}}\sum_{B^{z^{\prime}-}\subset
S^{z^{\prime}-}}\frac{1}{\binom{n^{z+}}{m^{z+}}}\frac{1}{\binom{n^{z^{\prime}-}}{m^{z^{\prime}-}}}\partial_{\lambda_{z,z^{\prime}}}F(\theta,\lambda;B^{z+}\cup
B^{z^{\prime}-})$ $\displaystyle=$ $\displaystyle\sum_{B^{z+}\subset
S^{z+}}\sum_{B^{z^{\prime}-}\subset
S^{z^{\prime}-}}\frac{1}{\binom{n^{z+}}{m^{z+}}}\frac{1}{\binom{n^{z^{\prime}-}}{m^{z^{\prime}-}}}\frac{1}{m^{z+}}\frac{1}{m^{z^{\prime}-}}\sum_{\mathbf{x}_{i}^{z^{+}}\in
B^{z+}}\sum_{\mathbf{x}_{j}^{z^{\prime}-}\in
B^{z^{\prime}-}}\ell(f_{\theta}(\mathbf{x}_{i}^{z+})-f_{\theta}(\mathbf{x}_{j}^{z^{\prime}-}))$
$\displaystyle=$
$\displaystyle\frac{1}{\binom{n^{z+}}{m^{z+}}}\frac{1}{\binom{n^{z^{\prime}-}}{m^{z^{\prime}-}}}\frac{1}{m^{z+}}\frac{1}{m^{z^{\prime}-}}\sum_{\begin{subarray}{c}\mathbf{x}_{i}^{z^{+}}\in
S^{z+}\\\ \mathbf{x}_{j}^{z^{\prime}-}\in
S^{z^{\prime}-}\end{subarray}}\sum_{\begin{subarray}{c}B^{z+}\setminus\\{\mathbf{x}_{i}^{z+}\\}\subset
S^{z+}\setminus\\{\mathbf{x}_{i}^{z+}\\}\\\
B^{z^{\prime}-}\setminus\\{\mathbf{x}_{j}^{z^{\prime}-}\\}\subset
S^{z^{\prime}-}\setminus\\{\mathbf{x}_{j}^{z^{\prime}-}\\}\end{subarray}}\ell(f_{\theta}(\mathbf{x}_{i}^{z+})-f_{\theta}(\mathbf{x}_{j}^{z^{\prime}-}))$
$\displaystyle=$
$\displaystyle\frac{1}{\binom{n^{z+}}{m^{z+}}}\frac{1}{\binom{n^{z^{\prime}-}}{m^{z^{\prime}-}}}\frac{1}{m^{z+}}\frac{1}{m^{z^{\prime}-}}\sum_{i=1}^{n^{z+}}\sum_{j=1}^{n^{z^{\prime}-}}\binom{n^{z+}-1}{m^{z+}-1}\binom{n^{z^{\prime}-}-1}{m^{z^{\prime}-}-1}\ell(f_{\theta}(\mathbf{x}_{i}^{z+})-f_{\theta}(\mathbf{x}_{j}^{z^{\prime}-}))$
$\displaystyle=$
$\displaystyle\frac{1}{n^{z+}}\frac{1}{n^{z^{\prime}-}}\sum_{i=1}^{n^{z+}}\sum_{j=1}^{n^{z^{\prime}-}}\ell(f_{\theta}(\mathbf{x}_{i}^{z+})-f_{\theta}(\mathbf{x}_{j}^{z^{\prime}-})),\,\forall
z,z^{\prime}\in\mathcal{Z}.$

The expectation of the stochastic gradient w.r.t. $\theta$ is given by

$\displaystyle\mathbb{E}_{B\sim\texttt{Alg \ref{alg:group-label-
sampler}}}[\partial_{\theta}F(\theta,\lambda;B)]=$
$\displaystyle\mathbb{E}_{B\sim\texttt{Alg \ref{alg:group-label-
sampler}}}[\sum_{z=1}^{k}\sum_{z^{\prime}=1}^{k}\lambda_{z,z^{\prime}}\partial_{\theta}\hat{R}^{\ell}(\theta;B^{z+}\cup
B^{z^{\prime}-})]$ $\displaystyle=$
$\displaystyle\sum_{z=1}^{k}\sum_{z^{\prime}=1}^{k}\lambda_{z,z^{\prime}}\mathbb{E}_{B^{z+},B^{z^{\prime}-}}[\partial_{\theta}\hat{R}^{\ell}(\theta;B^{z+}\cup
B^{z^{\prime}-})]$ $\displaystyle=$
$\displaystyle\sum_{z=1}^{k}\sum_{z^{\prime}=1}^{k}\frac{\lambda_{z,z^{\prime}}}{n^{z+}n^{z^{\prime}-}}\sum_{i=1}^{n^{z+}}\sum_{j=1}^{n^{z^{\prime}-}}\nabla_{\theta}\ell(f_{\theta}(\mathbf{x}_{i}^{z+})-f_{\theta}(\mathbf{x}_{j}^{z^{\prime}-})).$

THe proof is complete by calling the definiton of $\hat{R}$. ∎

##  Appendix C Convergence Analysis

In this section, we provide theoretical justification of Theorem 2. Our
analysis is inspired by the convergence of stochastic gradient descent ascent
(SGDA) in the nonconvex-concave Euclidean space (Lin, Jin, and Jordan 2020).
We provide novel analysis on visualizing the exponential weights update as the
gradient ascent in the $\ell_{1}$ setting. It is worth noting that $P$ is not
necessarily differentiable even if $R$ is Lipschitz continuous and smooth.
Fortunately, the following structural lemma shows that $P$ is weakly convex
and Lipschitz continuous.

######  Lemma C.1 ((Lin, Jin, and Jordan 2020)).

Assume Assumption 1 and 2 hold, the function
$P(\cdot;S)=\max_{\lambda\in\Lambda_{k^{2}}}F(\cdot,\lambda;S)$ is $L$-weakly
convex and $G$-Lipschitz with
$\partial_{\theta}F(\theta,\hat{\lambda}(\theta);S)\in\partial P(\theta;S)$.

For weakly convex function $P$, Davis and Drusvyatskiy (2019) proposed an
alternative notion of stationarity based on the Moreau envolope, i.e.
$P_{1/2L}(\theta)=\min_{\gamma}P(\gamma)+L\|\gamma-\theta\|_{2}^{2}$. Once the
norm of the gradient of Moreau envelope is small, i.e. $\|\nabla
P_{1/2L}(\theta)\|_{2}\leq\epsilon$, one can show that $\theta$ is close to a
point $\hat{\theta}$ which has at least one small subgradient.

######  Lemma C.2 ((Davis and Drusvyatskiy 2019)).

If $\theta$ satisfies $\|\nabla P_{1/2L}(\theta)\|_{2}\leq\epsilon$, there
exists $\hat{\theta}$ such that $\min_{\xi\in\partial
P(\hat{\theta})}\|\xi\|_{2}\leq\epsilon$ and
$\|\theta-\hat{\theta}\|_{2}\leq\epsilon/2L$.

The analysis of inexact nonconvex subgradient descent (Davis and Drusvyatskiy
2019) implies the following descent inequality on $P_{1/2L}(\theta_{t};S)$.
The proof of this lemma is a direct application of Lemma D.3 in Lin, Jin, and
Jordan (2020) hence it is omitted. One can easily check the $\ell_{1}$ setting
on the dual variable $\lambda$ does not hurt the definition and the descent
lemma on $P_{1/2L}$, which is defined again in the Euclidean space.

######  Lemma C.3.

Assume Assumption 1, 2 and 3 hold, let
$\Delta_{t}=\mathbb{E}[P(\theta_{t};S)-F(\theta_{t},\lambda_{t};S)]$. Then
Algorithm 1 yields

$\mathbb{E}[P_{1/2L}(\theta_{t};S)]\leq\mathbb{E}[P_{1/2L}(\theta_{t-1};S)]+2\eta_{\theta}L\Delta_{t-1}-\frac{\eta_{\theta}}{4}\mathbb{E}[\|\nabla
P_{1/2L}(\theta_{t-1};S)\|_{2}^{2}]+\eta_{\theta}^{2}L^{2}(G^{2}+\sigma^{2}/m).$

Our key technical novelty is to show that the error term $\Delta_{t}$ in the
above lemma enjoys a recursive relation. The proof’s idea is based on the
Pythagorean ineuqlaity w.r.t. the Bergman divergence $D_{\Phi}$ in the
$\ell_{1}$ setting.

######  Lemma C.4.

Assume Assumption 1, 2 and 3 hold. Let
$\Delta_{t}=\mathbb{E}_{t}[P(\theta_{t})-F(\theta_{t},\lambda_{t})]$. Then the
following statement holds true for any $\tau\leq t-1$,

$\Delta_{t-1}\leq\eta_{\theta}G\sqrt{G^{2}+\sigma^{2}/m}(2t-2\tau-1)+(\mathbb{E}_{t}[F(\theta_{t},\lambda_{t})]-F(\theta_{t-1},\lambda_{t-1}))\\\
+\frac{1}{\eta_{\lambda}}(D(\lambda^{\star}(\theta_{\tau})\parallel\lambda_{t-1})-\mathbb{E}_{t}[D(\lambda^{\star}(\theta_{\tau})\parallel\lambda_{t})])+\eta_{\lambda}^{2}\sigma^{2}/m$

###### Proof.

For any $\lambda\in\Lambda_{k^{2}}$, the convexity of $\Lambda_{k^{2}}$ and
the update formula of $\lambda_{t}$ imply that

$(\lambda-\lambda_{t})^{\top}(\nabla\Phi(\lambda_{t})-\nabla\Phi(\lambda_{t-1})-\eta_{\lambda}\nabla_{\lambda}F(\theta_{t-1},\lambda_{t-1};B_{t}))\geq
0.$

By the definition of Bregman divergence, we have

$\eta_{\lambda}(\lambda-\lambda_{t})^{\top}\nabla_{\lambda}F(\theta_{t-1},\lambda_{t-1};B_{t})\leq
D(\lambda\parallel\lambda_{t-1})-D(\lambda\parallel\lambda_{t})-D(\lambda_{t}\parallel\lambda_{t-1}).$

Rearranging the inequality yields that

$\eta_{\lambda}(\lambda-\lambda_{t-1})^{\top}\nabla_{\lambda}F(\theta_{t-1},\lambda_{t-1};B_{t})+\eta_{\lambda}(\lambda_{t-1}-\lambda_{t})^{\top}\nabla_{\lambda}F(\theta_{t-1},\lambda_{t-1};S)\\\
\leq
D(\lambda\parallel\lambda_{t-1})-D(\lambda\parallel\lambda_{t})-D(\lambda_{t}\parallel\lambda_{t-1})+\eta_{\lambda}(\lambda_{t-1}-\lambda_{t})^{\top}(\nabla_{\lambda}F(\theta_{t-1},\lambda_{t-1};S)-\nabla
F(\theta_{t-1},\lambda_{t-1};B_{t})).$

Using the Young’s inequality and the $1$-strong convexity of $\Phi$, we have

$\displaystyle\eta_{\lambda}(\lambda_{t-1}-\lambda_{t})^{\top}(\nabla_{\lambda}F(\theta_{t-1},\lambda_{t-1};S)-\nabla
F(\theta_{t-1},\lambda_{t-1};B_{t}))$ $\displaystyle\leq$
$\displaystyle\frac{\|\lambda_{t}-\lambda_{t-1}\|_{1}^{2}}{4}+\eta_{\lambda}^{2}\|\nabla_{\lambda}F(\theta_{t-1},\lambda_{t-1};S)-\nabla
F(\theta_{t-1},\lambda_{t-1};B_{t})\|_{\infty}^{2}$ $\displaystyle\leq$
$\displaystyle\frac{D(\lambda_{t}\parallel\lambda_{t-1})}{2}+\eta_{\lambda}^{2}\|\nabla_{\lambda}F(\theta_{t-1},\lambda_{t-1};S)-\nabla
F(\theta_{t-1},\lambda_{t-1};B_{t})\|_{\infty}^{2}.$

Taking an expectation of both sides of the above inequality, conditioned on
$(\theta_{t-1},\lambda_{t-1})$, together with Assumption 3 yields that

$\eta_{\lambda}(\lambda-\lambda_{t-1})^{\top}\nabla_{\lambda}F(\theta_{t-1},\lambda_{t-1};S)+\mathbb{E}_{t}[\eta_{\lambda}(\lambda_{t-1}-\lambda_{t})^{\top}\nabla_{\lambda}F(\theta_{t-1},\lambda_{t-1};S)]\\\
\leq
D(\lambda\parallel\lambda_{t-1})-\mathbb{E}_{t}[D(\lambda\parallel\lambda_{t})]-\frac{1}{2}\mathbb{E}_{t}[D(\lambda_{t}\parallel\lambda_{t-1})]+\frac{\eta_{\lambda}^{2}\sigma^{2}}{m}$

Since $F(\theta_{t-1},\cdot;S)$ is concave, we have

$F(\theta_{t-1},\lambda;S)\leq
F(\theta_{t-1},\lambda_{t-1};S)+(\lambda-\lambda_{t-1})^{\top}\nabla_{\lambda}F(\theta_{t-1},\lambda_{t-1};S).$

Since $F(\theta_{t-1},\cdot;S)$ is $L$-smooth w.r.t. $\|\cdot\|_{1}$ and
$\Phi$ is $1$-strongly convex w.r.t. $\|\cdot\|_{1}$, we have

$\displaystyle-F(\theta_{t-1},\lambda_{t};S)\leq$
$\displaystyle-F(\theta_{t-1},\lambda_{t-1};S)-(\lambda_{t}-\lambda_{t-1})^{\top}\nabla_{\lambda}F(\theta_{t-1},\lambda_{t-1};S)+\frac{L}{2}\|\lambda_{t}-\lambda_{t-1}\|_{1}^{2}$
$\displaystyle\leq$
$\displaystyle-F(\theta_{t-1},\lambda_{t-1};S)-(\lambda_{t}-\lambda_{t-1})^{\top}\nabla_{\lambda}F(\theta_{t-1},\lambda_{t-1};S)+LD(\lambda_{t}\parallel\lambda_{t-1}).$

Summing up the above two inequalities and taking conditional expectation on
both sides, we have

$F(\theta_{t-1},\lambda;S)-\mathbb{E}_{t}[F(\theta_{t-1},\lambda_{t};S)]\leq(\lambda-\lambda_{t-1})^{\top}\nabla_{\lambda}F(\theta_{t-1},\lambda_{t-1};S)\\\
+\mathbb{E}_{t}[(\lambda_{t-1}-\lambda_{t})^{\top}\nabla_{\lambda}F(\theta_{t-1},\lambda_{t-1};S)]+L\mathbb{E}_{t}[D(\lambda_{t}\parallel\lambda_{t-1})].$

By picking $\eta_{\lambda}\leq\frac{1}{2L}$ and putting Eq. (C) into the above
inequality, we have

$F(\theta_{t-1},\lambda)-\mathbb{E}_{t}[F(\theta_{t-1},\lambda_{t})]\leq\frac{1}{\eta_{\lambda}}(D(\lambda\parallel\lambda_{t-1})-\mathbb{E}_{t}[D(\lambda\parallel\lambda_{t})])+\frac{\eta_{\lambda}^{2}\sigma^{2}}{m}.$
(C.2)

Plugging $\lambda=\lambda^{\star}(\theta_{\tau})$ ($\tau\leq t-1$) in the
above inequality yields that

$F(\theta_{t-1},\lambda^{\star}(\theta_{\tau}))-\mathbb{E}_{t}[F(\theta_{t-1},\lambda_{t})]\leq\frac{1}{\eta_{\lambda}}(D(\lambda^{\star}(\theta_{\tau})\parallel\lambda_{t-1})-\mathbb{E}_{t}[D(\lambda^{\star}(\theta_{\tau})\parallel\lambda_{t})])+\frac{\eta_{\lambda}^{2}\sigma^{2}}{m}.$

By the definition of $\Delta_{t-1}$, we have

$\Delta_{t-1}\leq(F(\theta_{t-1},\lambda^{\star}(\theta_{t-1}))-F(\theta_{t-1},\lambda^{\star}(\theta_{\tau})))+(\mathbb{E}_{t}[F(\theta_{t},\lambda_{t})]-F(\theta_{t-1},\lambda_{t-1}))+(\mathbb{E}_{t}[F(\theta_{t-1},\lambda_{t})]-\mathbb{E}_{t}[F(\theta_{t},\lambda_{t})])\\\
+\frac{1}{\eta_{\lambda}}(D(\lambda^{\star}(\theta_{\tau})\parallel\lambda_{t-1})-\mathbb{E}_{t}[D(\lambda^{\star}(\theta_{\tau})\parallel\lambda_{t})])+\frac{\eta_{\lambda}^{2}\sigma^{2}}{m}.$

By the optimality of $\lambda^{\star}(\theta_{\tau})$, we have
$F(\theta_{\tau},\lambda^{\star}(\theta_{\tau}))\geq F(\theta_{\tau},\lambda)$
for all $\lambda\in\Lambda_{k^{2}}$. It implies that

$\displaystyle
F(\theta_{t-1},\lambda^{\star}(\theta_{t-1}))-F(\theta_{t-1},\lambda^{\star}(\theta_{\tau}))=$
$\displaystyle
F(\theta_{t-1},\lambda^{\star}(\theta_{t-1}))-F(\theta_{\tau},\lambda^{\star}(\theta_{t-1}))+F(\theta_{\tau},\lambda^{\star}(\theta_{t-1}))-F(\theta_{t-1},\lambda^{\star}(\theta_{\tau}))$
$\displaystyle\leq$ $\displaystyle
F(\theta_{t-1},\lambda^{\star}(\theta_{t-1}))-F(\theta_{\tau},\lambda^{\star}(\theta_{t-1}))+F(\theta_{\tau},\lambda^{\star}(\theta_{\tau}))-F(\theta_{t-1},\lambda^{\star}(\theta_{\tau})).$

By the $G$-Lipschitz continuity of $F(\cdot,\lambda)$ and Assumption 3, we
have

$\displaystyle
F(\theta_{t-1},\lambda^{\star}(\theta_{t-1}))-F(\theta_{\tau},\lambda^{\star}(\theta_{t-1}))\leq$
$\displaystyle
G\mathbb{E}_{t}[\|\theta_{t-1}-\theta_{\tau}\|_{2}]\leq\eta_{\theta}G\sqrt{G^{2}+\sigma^{2}/m}(t-1-\tau),$
$\displaystyle
F(\theta_{\tau},\lambda^{\star}(\theta_{\tau}))-F(\theta_{t-1},\lambda^{\star}(\theta_{\tau}))\leq$
$\displaystyle
G\mathbb{E}_{t}[\|\theta_{\tau}-\theta_{t-1}\|_{2}]\leq\eta_{\theta}G\sqrt{G^{2}+\sigma^{2}/m}(t-1-\tau),$
$\displaystyle\mathbb{E}_{t}[F(\theta_{t-1},\lambda_{t})-F(\theta_{t},\lambda_{t})]\leq$
$\displaystyle
G\mathbb{E}_{t}[\|\theta_{t-1}-\theta_{t}\|_{2}]\leq\eta_{\theta}G\sqrt{G^{2}+\sigma^{2}/m}.$

Putting theses pieces together and taking expectation on both sides of Eq. (C)
yields the desired inequality. ∎

Based on the recursive relation in Lemma C.4, the next lemma provides an upper
bound for $\frac{1}{T+1}\sum_{t=0}^{T}\Delta_{t}$ using both telescoping and
localization technique.

######  Lemma C.5.

Let $B\leq T+1$ and assume $(T+1)/B$ is an integer. The following statement
holds true

$\frac{1}{T+1}\sum_{t=0}^{T}\Delta_{t}\leq\eta_{\theta}G\sqrt{G^{2}+\sigma^{2}/m}(B+1)+\frac{\widehat{\Delta}_{0}}{T+1}+\frac{D^{2}}{\eta_{\lambda}B}+\frac{\eta_{\lambda}\sigma^{2}}{m}.$

###### Proof.

We divide $\\{\Delta_{t}\\}_{t=0}^{T}$ into several blocks in which each block
contains at most $B$ terms, given by

$\\{\Delta_{t}\\}_{t=0}^{B-1},\\{\Delta_{t}\\}_{t=B}^{2B-1},\cdots,\\{\Delta_{t}\\}_{t=T-B+1}^{T}.$

Then we have

$\frac{1}{T+1}\sum_{t=0}^{T}\Delta_{t}\leq\frac{B}{T+1}\Big{(}\sum_{i=0}^{(T+1)/B-1}\Big{(}\frac{1}{B}\sum_{t=iB}^{(i+1)B-1}\Delta_{t}\Big{)}\Big{)}.$
(C.3)

Furthermore, letting $\tau=iB$ in the inequality in Lemma C.4 yields that

$\displaystyle\sum_{t=iB}^{(i+1)B-1}\Delta_{t}\leq$
$\displaystyle\eta_{\theta}G\sqrt{G^{2}+\sigma^{2}/m}B^{2}+\frac{\eta_{\lambda}^{2}\sigma^{2}B}{m}+\frac{1}{\eta_{\lambda}}D(\lambda^{\star}(\theta_{iB})\parallel\lambda_{iB})+(\mathbb{E}[F(\theta_{(i+1)B},\lambda_{(i+1)B})]-\mathbb{E}[F(\theta_{iB},\lambda_{iB})])$
$\displaystyle\leq$
$\displaystyle\eta_{\theta}G\sqrt{G^{2}+\sigma^{2}/m}B^{2}+\frac{\eta_{\lambda}^{2}\sigma^{2}B}{m}+\frac{D^{2}}{\eta_{\lambda}}+(\mathbb{E}[F(\theta_{(i+1)B},\lambda_{(i+1)B})]-\mathbb{E}[F(\theta_{iB},\lambda_{iB})])$

Plugging the above inequality into Eq. (C.3) yields

$\frac{1}{T+1}\sum_{t=0}^{T}\Delta_{t}\leq\eta_{\theta}G\sqrt{G^{2}+\sigma^{2}/m}B+\frac{\eta_{\lambda}^{2}\sigma^{2}}{m}+\frac{D^{2}}{\eta_{\lambda}B}+\frac{\mathbb{E}[F(\theta_{T+1},\lambda_{T+1})]-\mathbb{E}[F(\theta_{0},\lambda_{0})]}{T+1}.$
(C.4)

Since $F(\cdot,\lambda)$ is $G$-Lipschitz continuous, we have

$\displaystyle\mathbb{E}[F(\theta_{T+1},\lambda_{T+1})]-\mathbb{E}[F(\theta_{0},\lambda_{0})]\leq$
$\displaystyle\mathbb{E}[F(\theta_{T+1},\lambda_{T+1})]-\mathbb{E}[F(\theta_{0},\lambda_{T+1})]+\mathbb{E}[F(\theta_{0},\lambda_{T+1})]-\mathbb{E}[F(\theta_{0},\lambda_{0})]$
$\displaystyle\leq$
$\displaystyle\eta_{\theta}G\sqrt{G^{2}+\sigma^{2}/m}(T+1)+\widehat{\Delta}_{0}.$

Plugging the above inequality into Eq. (C.4) yields the desired inequality. ∎

Now we are at the position to formally state Theorem 2. In particular,

######  Theorem C.6 (Theorem 2 restated).

Let Assumption 1, 2, 3 hold true. Let the step sizes be chosen as
$\eta_{\theta}=\Theta(\epsilon^{4}/(L^{3}D^{2}(G^{2}+\sigma^{2}/m)))$ and
$\eta_{\lambda}=\Theta(\epsilon^{2}/(L\sigma^{2}/m))$. Then, after $T$
iteration, the output $\theta_{\tau}$ of Algorithm 1 satisfies The iteration
complexity of Algorithm 1 to return an $\epsilon$-stationary point is bounded
by

$\mathbb{E}[\|\nabla
P_{1/2L}(\theta_{\tau};S)\|_{2}^{2}]\leq\frac{4\widehat{\Delta}_{P}}{\eta_{\theta}(T+1)}+\frac{8L\widehat{\Delta}_{0}}{T+1}+\frac{3\epsilon^{2}}{4}.$

Furthermore, there exists $\hat{\theta}$ such that $\min_{\xi\in\partial
P(\hat{\theta})}\|\xi\|_{2}\leq\epsilon$ and
$\|\theta_{\tau}-\hat{\theta}\|_{2}\leq\epsilon/2L$ by picking

$T=\mathcal{O}\Big{(}\Big{(}\frac{L^{3}(G^{2}+\sigma^{2}/m)D^{2}\widehat{\Delta}_{P}}{\epsilon^{4}}+\frac{L^{3}D^{2}\widehat{\Delta}_{0}}{\epsilon^{2}}\Big{)}\max\Big{\\{}1,\frac{\sigma^{2}}{\epsilon^{2}}\Big{\\}}\Big{)}.$

###### Proof of Theorem 2.

Summing up the inequality in Lemma C.3 over $t=1,2,\cdots T+1$ yields that

$\mathbb{E}[P_{1/2L}(\theta_{T+1};S)]\leq\mathbb{E}[P_{1/2L}(\theta_{0};S)]+2\eta_{\theta}L\sum_{t=0}^{T}\Delta_{t}-\frac{\eta_{\theta}}{4}\sum_{t=0}^{T}\mathbb{E}[\|\nabla
P_{1/2L}(\theta_{t};S)\|_{2}^{2}]+\eta_{\theta}^{2}L^{2}(G^{2}+\sigma^{2}/m)(T+1).$

Combining the above inequality with the inequality in Lemma C.5 yields that

$\mathbb{E}[P_{1/2L}(\theta_{T+1};S)]\leq\mathbb{E}[P_{1/2L}(\theta_{0};S)]+2\eta_{\theta}L(T+1)\Big{(}\eta_{\theta}G\sqrt{G^{2}+\sigma^{2}/m}(B+1)+\frac{D^{2}}{\eta_{\lambda}B}+\frac{\eta_{\lambda}\sigma^{2}}{m}\Big{)}+2\eta_{\theta}L\widehat{\Delta}_{0}\\\
-\frac{\eta_{\theta}}{4}\sum_{t=0}^{T}\mathbb{E}[\|\nabla
P_{1/2L}(\theta_{t};S)\|_{2}^{2}]+\eta_{\theta}^{2}L^{2}(G^{2}+\sigma^{2}/m)(T+1).$

By the definition of $\widehat{\Delta}_{P}$, we have

$\frac{1}{T+1}\sum_{t=0}^{T}\mathbb{E}[\|\nabla
P_{1/2L}(\theta_{t};S)\|_{2}^{2}]\leq\frac{4\widehat{\Delta}_{P}}{\eta_{\theta}(T+1)}+8L\Big{(}\eta_{\theta}G\sqrt{G^{2}+\sigma^{2}/m}(B+1)+\frac{D^{2}}{\eta_{\lambda}B}+\frac{\eta_{\lambda}\sigma^{2}}{m}\Big{)}+\frac{8L\widehat{\Delta}_{0}}{T+1}+4\eta_{\theta}L^{2}(G^{2}+\sigma^{2}/m).$

Letting
$B=\frac{D}{2}\sqrt{\frac{1}{\eta_{\theta}\eta_{\lambda}G\sqrt{G^{2}+\sigma^{2}/m}}}$,
we have

$\frac{1}{T+1}\sum_{t=0}^{T}\mathbb{E}[\|\nabla
P_{1/2L}(\theta_{t};S)\|_{2}^{2}]\leq\frac{4\widehat{\Delta}_{P}}{\eta_{\theta}(T+1)}+16LD\sqrt{\frac{\eta_{\theta}G\sqrt{G^{2}+\sigma^{2}/m}}{\eta_{\lambda}}}+\frac{8L\widehat{\Delta}_{0}}{T+1}+\frac{8\eta_{\lambda}L^{2}\sigma^{2}}{m}+4\eta_{\theta}L^{2}(G^{2}+\sigma^{2}/m).$

By picking
$\eta_{\theta}=\min\big{\\{}\frac{\epsilon^{2}}{16L(G^{2}+\sigma^{2}/m)},\frac{\epsilon^{4}}{8192L^{3}D^{2}G\sqrt{G^{2}+\sigma^{2}/m}},\frac{\epsilon^{6}}{65536L^{3}D^{2}(\sigma^{2}/m)G\sqrt{G^{2}+\sigma^{2}/m}}\big{\\}}$
and
$\eta_{\lambda}=\min\big{\\{}\frac{1}{2L},\frac{\epsilon^{2}}{16L^{2}\sigma^{2}/m}\big{\\}}$,
we have

$\frac{1}{T+1}\sum_{t=0}^{T}\mathbb{E}[\|\nabla
P_{1/2L}(\theta_{t};S)\|_{2}^{2}]\leq\frac{4\widehat{\Delta}_{P}}{\eta_{\theta}(T+1)}+\frac{8L\widehat{\Delta}_{0}}{T+1}+\frac{3\epsilon^{2}}{4}.$

The above inequality yields the first claim in the theorem by taking the
expectation of $\theta_{\tau}$ due to the uniform sampling. Furthermore, by
Lemma C.2, it implies that the number of iterations required by Algorithm 1 to
return an $\epsilon$-stationary point is bounded by

$\mathcal{O}\Big{(}\Big{(}\frac{L(G^{2}+\sigma^{2}/m)\widehat{\Delta}_{P}}{\epsilon^{4}}+\frac{L\widehat{\Delta}_{0}}{\epsilon^{2}}\Big{)}\max\Big{\\{}1,\frac{L^{2}D^{2}}{\epsilon^{2}},\frac{L^{2}D^{2}\sigma^{2}}{\epsilon^{4}}\Big{\\}}\Big{)},$

which gives the same total gradient complexity in the second claim. ∎

##  Appendix D Equal Error Rates for AUC

In this section, we describe the equal error rates framework mentioned in
empirical evaluations for achieving intra-group and inter-group AUC fairness
as in Eq. (2) and . The goal is to maximizes overall AUC while keeping all the
group-level AUC score to be the same as the overall AUC.

$\displaystyle\min_{\theta\in\Theta}$ $\displaystyle\hat{R}^{\ell}(\theta)$
s.t.
$\displaystyle\hat{R}_{z,z^{\prime}}^{\ell}(\theta)=\hat{R}^{\ell}(\theta),z,z^{\prime}=1,\cdots
k.$ (D.1)

Let $p_{z,z^{\prime}}=\frac{n^{z+}n^{z^{\prime}-}}{n^{+}n^{-}}$ be group
proportions and it is straightforward to check that
$\hat{R}^{\ell}(\theta)=\sum_{z=1}^{k}\sum_{z^{\prime}=1}^{k}p_{z,z^{\prime}}\hat{R}_{z,z^{\prime}}^{\ell}(\theta)$.
The Lagrangian dual function of Problem (D) is given by

$\displaystyle F(\theta,\lambda)=$
$\displaystyle\lambda_{0,0}\hat{R}^{\ell}(\theta)+\sum_{z=1}^{k}\sum_{z^{\prime}=1}^{k}\lambda_{z,z^{\prime}}(\hat{R}_{z,z^{\prime}}^{\ell}(\theta)-\hat{R}^{\ell}(\theta))$
$\displaystyle=$
$\displaystyle(\lambda_{0,0}-\sum_{z=1}^{k}\sum_{z^{\prime}=1}^{k}\lambda_{z,z^{\prime}})\hat{R}^{\ell}(\theta)+\sum_{z=1}^{k}\sum_{z^{\prime}=1}^{k}\lambda_{z,z^{\prime}}\hat{R}_{z,z^{\prime}}^{\ell}(\theta)$
$\displaystyle=$
$\displaystyle(\lambda_{0,0}-\sum_{z=1}^{k}\sum_{z^{\prime}=1}^{k}\lambda_{z,z^{\prime}})\sum_{z=1}^{k}\sum_{z^{\prime}=1}^{k}p_{z,z^{\prime}}\hat{R}_{z,z^{\prime}}^{\ell}(\theta)+\sum_{z=1}^{k}\sum_{z^{\prime}=1}^{k}\lambda_{z,z^{\prime}}\hat{R}_{z,z^{\prime}}^{\ell}(\theta)$
$\displaystyle=$
$\displaystyle\sum_{z=1}^{k}\sum_{z^{\prime}=1}^{k}\Big{(}\lambda_{z,z^{\prime}}+\Big{(}\lambda_{0,0}-\sum_{z=1}^{k}\sum_{z^{\prime}=1}^{k}\lambda_{z,z^{\prime}}\Big{)}p_{z,z^{\prime}}\Big{)}\hat{R}_{z,z^{\prime}}^{\ell}(\theta).$

When only intra-group AUCs are considered, we have $\lambda_{z,z^{\prime}}=0$
for all $z\neq z^{\prime}$. When only inter-group AUCs are considered, we have
$\lambda_{z,z}=0$ for all $z=1,\cdots k$. The empirical average of play
converges to a Nash equilibrium, where an equilibrium corresponds to an
optimal solution to the original constrained optimization problem (D). It is
worth noting that our equal error rates framework is different from the
constrained optimization framework in Narasimhan et al. (2020). Firstly, we do
not require a pre-defined ”fairness level” $\kappa$ in the constraint of Eq.
(D) whereas it is required in their work. Instead we require the group-level
AUC to be the same as the overall AUC. This treatment can avoid fixing
unrealistic small $\kappa$ and hurting the utility too much. Secondly, our
training scheme is based on stochastic gradient descent ascent algorithm which
is described in Algorithm 3, whereas Narasimhan et al. use a proxy loss
function for updating the group weights.

Algorithm 3 EqualAUC

1: Inputs: Training set $S$ with label $Y$ and protected attribute $Z$, model
$f_{\theta}$, number of iterations $T$, batch size $m$, learning rates
$\\{\eta_{\theta},\eta_{\lambda}\\}$

2: Initialize $\theta\in\Theta$ and $\lambda_{z,z^{\prime}}=0$

3: for $t=1$ to $T-1$ do

4: $B_{t}=\texttt{Sample}_{m}(S)$

5:
$\theta_{t}=\theta_{t-1}-\eta_{\theta}(\lambda_{t-1}+(1-1^{\top}\lambda_{t-1})p)^{\top}\partial_{\theta}\hat{R}^{\ell}(\theta_{t-1};B_{t})$

6:
$\lambda_{z,z^{\prime}}=\lambda_{z,z^{\prime}}+\eta_{\lambda}(\hat{R}_{z,z^{\prime}}^{\ell}(\theta)-\hat{R}^{\ell}(\theta))$

7: end for

8: Outputs: Uniform distribution over the set of models
$\theta_{1},\cdots,\theta_{T}$

##  Appendix E Additional Experiments

In this section, we describe the empirical evaluation setup in details and
provide more experimental results.

#### Implementation Details On Real Datasets.

We summarize implementation details of generating Table 2.

  * •

The Adult, Bank and Compas datasets are all pre-processed according to Vogel,
Bellet, and Clémençon (2021). The Default dataset is pre-processed according
to Donini et al. (2018).

  * •

All experiments were implemented in Python with dependence on standard
libraries: pandas, NumPy, PyTorch, scikit-learn and matplotlib for plots. All
experiments were implemented on a server with the CPUs as Intel(R) Xeon(R)
Silver 4214 @ 2.20GHz and the GPU as NVIDIA GeForce RTX 2080 Ti.

  * •

All the hyperparameter are chosen based on 25 runs of the cross-validation
with 60% training, 20% validation and 20% testing. In particular, the batch
size parameter $m$ is chosen from the candidate set
$\\{256,512,1024,2048,4096,8192\\}$ except $m=8192$ is too large to consider
for Compas. The model stepsize parameter $\eta_{\theta}$ is chosen from the
candidate set $\\{0.2,0.1,0.05,0.01\\}$ and the stepsize for group weights,
$\eta_{\lambda}$, is determined by $\eta_{\lambda}=\kappa\times\eta_{\theta}$
where the ratio $\kappa$ is chosen from the candidate set
$\\{100,10,1,0.1,0.01\\}$. Furthermore, we also apply a weight decay parameter
$\omega$ chosen from the candidate set $\\{0.1,0.01,0.001\\}$.

#### Generation Details For Synthetic Datasets.

Firstly, we discuss the generation of the scoring function in Figure 1. The
distribution of the scoring function conditioned on the label $Y$ and
protected attribute $Z$, i.e., $f_{\theta}|Y,Z$, is given as follow

$f_{\theta}|Y=y,Z=z\sim\text{logit}(\mathcal{N}(\mu_{y,z},\sigma^{2}_{y,z}))$

where logit is the logistic function. For every partition of a $(y,z)$ pair,
we generate 1,000 scores. We apply
$\mu_{0a}=0.3,\mu_{1a}=0.7,\mu_{0b}=0.0,\mu_{0b}=1.0$ and
$\sigma_{y,z}^{2}=0.5$ for all $y\in\\{\pm 1\\},z\in\\{a,b\\}$. Such choices
allow the same gap between $\mu_{1a}-\mu_{0b}$ and $\mu_{1b}-\mu_{0a}$,
leading towards fair inter-group AUCs. However, one has
$\mu_{1a}-\mu_{0a}<\mu_{1b}-\mu_{0b}$, leading towards unfair intra-group AUCs
in this one-dimensional example.

Next we discuss the generation of the two-dimensional dataset in Figure 3. The
distribution of the feature vector $X$ conditioned on the label $Y$ and
protected attribute $Z$ is given as follow

$X|Y=y,Z=z\sim\mathcal{N}(\mu_{y,z},\sigma^{2}_{y,z}\mathbb{I}_{2\times 2})$

with
$\mu_{0a}=(-1.0,1.0)^{\top},\mu_{1a}=(-1.5,0.5)^{\top},\mu_{0b}=(-2.0,-1.0)^{\top},\mu_{1b}=(1.0,0.0)^{\top}$
and $\sigma^{2}_{0a}=\sigma^{2}_{1a}=0.5,\sigma^{2}_{0b}=\sigma^{2}_{1b}=1.0$.
For every partition of a $(y,z)$ pair, we generate 1,000 data points. Such
distribution makes sure both intra-group and inter-group AUC unfairness exist
while the intra-group AUC unfairness will be more severe.

#### More On Ablation Studies.

We continue on reporting maximin AUC problem (3) with only intra-group AUCs or
inter-group AUCs on Bank, Compas and Default. In general, we can roughly see
only applying intra-group (resp. inter-group) AUC fairness may help but it is
limited towards inter-group (resp. intra-group) AUC fairness.

(a) Intra-group AUCs only

(b) Inter-group AUCs only

Figure E.1: Ablation study on Bank.

(a) Intra-group AUCs only

(b) Inter-group AUCs only

Figure E.2: Ablation study on COMPAS.

(a) Intra-group AUCs only

(b) Inter-group AUCs only

Figure E.3: Ablation study on Default.