# Multi-Group Fairness Evaluation via Conditional Value-at-Risk Testing

Lucas Monteiro Paes, Ananda Theertha Suresh, Alex Beutel, Flavio P. Calmon,
and Ahmad Beirami The work of Lucas Monteiro Paes and Flavio P. Calmon was
supported in part by the National Science Foundation under grants CAREER
1845852, CIF 2312667, FAI 2040880, and also in part by a gift from Google.
Lucas Monteiro Paes and Flavio P. Calmon are with the School of Engineering
and Applied Sciences, Harvard University, Cambridge, MA 02134, USA (e-mail:
<EMAIL_ADDRESS>flavio@seas.harvard.edu). Ananda Theertha Suresh and
Ahmad Beirami are with Google Research, New York, NY 10011, USA (e-mail:
<EMAIL_ADDRESS>beirami@google.com). Alex Beutel contributed to this
research while at Google Research, New York, NY 10011, USA. He is currently
with OpenAI (e-mail<EMAIL_ADDRESS>.

###### Abstract

Machine learning (ML) models used in prediction and classification tasks may
display performance disparities across population groups determined by
sensitive attributes (e.g., race, sex, age). We consider the problem of
evaluating the performance of a fixed ML model across population groups
defined by multiple sensitive attributes (e.g., race and sex and age). Here,
the sample complexity for estimating the worst-case performance gap across
groups (e.g., the largest difference in error rates) increases exponentially
with the number of group-denoting sensitive attributes. To address this issue,
we propose an approach to test for performance disparities based on
Conditional Value-at-Risk (CVaR). By allowing a small probabilistic slack on
the groups over which a model has approximately equal performance, we show
that the sample complexity required for discovering performance violations is
reduced exponentially to be at most upper bounded by the square root of the
number of groups. As a byproduct of our analysis, when the groups are weighted
by a specific prior distribution, we show that Rényi entropy of order $2/3$ of
the prior distribution captures the sample complexity of the proposed CVaR
test algorithm. Finally, we also show that there exists a non-i.i.d. data
collection strategy that results in a sample complexity independent of the
number of groups.

###### Index Terms:

multi-group fairness, intersectional fairness, hypothesis testing,
intersectionality

##  I Introduction

Machine learning (ML) algorithms are increasingly used in domains of
consequence such as hiring [1], lending [2, 3], policing [4], and healthcare
[5, 6]. These algorithms may display performance disparities across groups
determined by legally protected attributes [7, 8] (e.g., sex and race).
Discovering and reducing performance disparities across population groups is a
recognized desideratum in ML. Over the past decade, hundreds of fairness
interventions have been proposed to close performance gaps in a range of
prediction and classification tasks while preserving overall accuracy [9, 10,
11, 12, 13, 14, 15, 16].

While there are many notions of fairness in ML [17], we focus on group
fairness [18, 19, 20, 13]. Group fairness is usually concerned with a small
number (e.g., two) of pre-determined demographic groups $\mathcal{G}$ and
requires a certain performance metric to be approximately equal across the
groups in $\mathcal{G}$ — different choices of performance metric lead to
different notions of fairness. For example, equal opportunity [13], a popular
variation of group fairness, requires that false positive rates (FPR) be
approximately equal across groups in $\mathcal{G}$. A widely accepted
mathematical formalization of group fairness is the _largest_ gap between a
model’s performance for a group in $\mathcal{G}$ and its average performance
across the entire population. We refer to such worst-case group fairness
metrics as _max-gap fairness metrics_.

Multi-group fairness notions aim to increase the granularity of groups in
$\mathcal{G}$ for which model performance is measured and compared [21, 22,
23, 24, 25]. Multi-group fairness metrics answer recent calls for testing for
performance disparities across groups determined by intersectional demographic
attributes [23, 24, 25] (e.g., groups determined by sex and race instead of
separate evaluation for each attribute). A fine-grained characterization of
groups is critical for discovering performance disparities that may lead to
systematic disadvantages across intersecting dimensions [24].

Though socially critical, the need for multi-group fairness and the discovery
of max-gap fairness violations pose competing statistical objectives.
Intuitively, as the number of groups increases (i.e., $|\mathcal{G}|$ becomes
large), so does the sample complexity of evaluating max-gap fairness metrics.
In such cases, even testing for multi-group fairness is challenging [26, 22,
21]. For instance, Kearns et al. [21] show that a model can be reliably tested
for multi-group fairness with a test dataset of size $O(|\mathcal{G}|)$.
Testing for multi-group fairness may be infeasible when $|\mathcal{G}|$ is
large, such as when $\mathcal{G}$ is a product set of several group-denoting
attributes such as sex, age, race, etc.

In this paper, we derive fundamental performance limits for testing for multi-
group fairness and propose a notion of multi-group fairness based on
conditional value-at-risk (CVaR) [27] that allows practitioners to relax
fairness guarantees to decrease the sample complexity for reliably testing for
multi-group fairness — we call it CVaR fairness. CVaR is a popular metric that
is a convex relaxation of the “maximum,” making it a suitable objective for
optimization as well. As we shall see, CVaR fairness also leads to a much
improved sample complexity as compared to the max-gap fairness allowing us to
scale the number of groups in a tractable manner. Remarkably, for non-i.i.d.
datasets, we propose an algorithm for reliably testing for CVaR fairness
violations with a number of samples independent of the number of demographic
groups.

Formally, each individual has sensitive attributes denoted by
$(s_{1},...,s_{k})$ for some $k\in\mathbb{N}$, and $s_{i}\in\mathcal{S}^{i}$.
Intersectionality argues that all the population groups defined by the
combinations
$(s_{1},...,s_{k})\in\mathcal{S}^{1}\times...\times\mathcal{S}^{k}$ have
unique sources of discrimination and privilege [28]. Therefore, it is
important to discover and treat disparities in performance across groups
$g\in\mathcal{G}=\mathcal{S}^{1}\times...\times\mathcal{S}^{k}$ [24, 29, 23,
30]. In this case, the number of groups that we aim to ensure that the ML
algorithm treats similarly is
$|\mathcal{G}|=|\mathcal{S}^{1}|\cdot|\mathcal{S}^{2}|...\cdot|\mathcal{S}^{k}|$.
When each $\mathcal{S}^{i}$ is at least binary for all $i\in[k]$,
$\mathcal{G}$ has an exponential number of groups $|\mathcal{G}|\geq 2^{k}$.

Let $\mathbf{w}=(w_{1},...,w_{|\mathcal{G}|})$ be a stochastic vector that
defines a distribution over groups. Broadly speaking, we can think of
$\mathbf{w}$ as a vector of fairness aware importance scores for every group
$g\in\mathcal{G}$; for example, $\mathbf{w}$ can be given by the percentage of
each group in the population, an importance weight for each group, or uniform
$\left(\text{i.e., }w_{g}=\frac{1}{|\mathcal{G}|}\right)$ when assuming a non-
informative prior on the group distributions. Our main contributions are:

  * •

We provide an impossibility result, showing that _any hypothesis test_ that
uses i.i.d. samples from the data distribution needs at least
$n=\Omega(|\mathcal{G}|)$ points to reliably test if max-gap fairness metrics
are greater than a fixed threshold — Proposition 24. Our result complements
the achievability result in [21], where it was shown that multi-group fairness
can be tested with $n=O(|\mathcal{G}|)$ samples. Hence, scaling $\mathcal{G}$
to intersectional groups determined by a combination of features can be
infeasible due to the cost of acquiring an exponential number of samples.

  * •

Motivated by the first negative result, we propose a multi-group fairness
metric that is a relaxation for max-gap fairness metrics based on the
conditional value-at-risk (CVaR) — namely CVaR fairness in Definition 3. We
show that it is possible to recover max-gap fairness metrics from CVaR
fairness (Proposition 2) and that CVaR fairness lower bounds max-gap fairness
metrics (Proposition 33).

  * •

We propose two natural sampling techniques for data collection: _weighted
sampling_ and _attribute specific sampling_ thus providing flexibility for the
auditor to collect datasets.

  * •

We propose an algorithm to test if the CVaR fairness metric is greater than a
fixed threshold $\epsilon$ (Algorithm 1). To do so, we use an estimator for
the CVaR fairness metric, use data samples to compute the estimator based on
either sampling technique, and perform a threshold test that outputs if the
CVaR fairness metric is bigger than the fixed threshold ($\epsilon$) or equal
to zero.

  * •

We prove that the proposed Algorithm 1, with weighted sampling, can reliably
test for CVaR fairness using at most
$n=O\left(2^{\frac{1}{2}H_{2/3}(\mathbf{w})}\right)$ samples, where
$H_{2/3}(\cdot)$ is the Rényi entropy of order $\frac{2}{3}$, which is
formally defined in (38) (Theorem 1). Our result shows that using Algorithm 1
for the CVaR fairness metric allows us to decrease the sample complexity of
testing, achieving a complexity of
$2^{\frac{1}{2}H_{2/3}(\mathbf{w})}\leq\sqrt{|\mathcal{G}|}<|\mathcal{G}|$.

  * •

We also show a lower bound for the sample complexity for testing CVar fairness
under weighted sampling when $\mathbf{w}$ is a uniform distribution over all
groups. We show that when $\mathbf{w}$ is a uniform distribution over all
groups we need $n=\Omega\left(\sqrt{|\mathcal{G}|}\right)$ samples to reliably
test for CVaR fairness (Theorem 45). When $\mathbf{w}$ is the uniform
distribution, this bound matches the upper bound of the proposed algorithm
under weighted sampling tehcnique.

  * •

Finally, we prove that if we have access to $2$ samples of any group
$g\in\mathcal{G}$ (we will not necessarily use them), it is possible to use
Algorithm 1 with attribute specific sampling to reliably test for CVaR
fairness utilizing a number of samples ($n$) that is independent of the number
of groups $|\mathcal{G}|$. Specifically, when testing if the CVaR fairness
metric is bigger than a threshold $\epsilon$, we only need
$O\left(\frac{1}{\epsilon^{4}}\right)$ samples to test reliably. Making the
number of samples to test for multi-group fairness independent of the number
of groups.

The paper is organized as follows. In Section II, we introduce the notation
used in the paper and the hypothesis test framework for auditing a model for
multi-group fairness. In Section III, we define the max-gap fairness metric
and provide a converse result for auditing a model for max-gap fairness — this
result indicates when auditing a model for max-gap fairness is infeasible. In
Section IV, we define the conditional value-at-risk fairness metric and
describe its properties. In Section V, we define an algorithm along with
sampling strategies for efficiently testing if the CVaR fairness metric is
greater than a threshold equal to zero. Finally, in Section VI we show a
converse result for auditing a model for CVaR fairness under certain
assumptions, showing that the proposed testing algorithm achieves optimal
order, and providing an operational meaning for the Rényi entropy of order
$2/3$.

##  II Background & Notation

We start by describing each individual as a tuple $(x,g,y)$ where
$x\in\mathcal{X}$ is the attribute vector, $g\in\mathcal{G}$ is the
_protected_ group variable (e.g., $(\texttt{sex, race, age})=(\texttt{male,
asian, 20--30})$), and $y\in\\{0,1\\}$ is a binary label to be predicted —
note that $x\in\mathcal{X}$ may contain $g\in\mathcal{G}$. Let
$\widehat{y}=f_{\theta}(x)\in\\{0,1\\}$ denote a model that aims to predict
$y$ and where the model is parameterized by $\theta$ e.g., weights of a neural
network. We denote the data of each individual by
$z=(x,g,y,\widehat{y})\in\mathcal{Z}$, when using a random variable instead of
the data samples, we write $Z=(X,G,Y,\widehat{Y})$, and assume that the data
is drawn from an unknown distribution $\widetilde{P}_{Z}$. We sample from
$\widetilde{P}_{Z}$ to create a model auditing dataset with $n\in\mathbb{N}$
samples $\mathcal{D}_{\text{audit}}=\\{z_{i}\\}_{i=1}^{n}$ — the data points
are not necessarily i.i.d. sampled. Note that the samples
$z=(x,g,y,\widehat{y})$ are realizations of the random variable
$Z=(X,G,Y,\widehat{Y})$.

We also define
$\mathbf{w}\triangleq(w_{1},...,w_{|\mathcal{G}|})\in\Delta^{|\mathcal{G}|}$
to be a prior distribution on the groups of the audit dataset — the model
auditor has full control over $\mathbf{w}$. For example, when testing for
fairness, the model auditor may choose $\mathbf{w}$ to be given by a non-
informative prior, i.e., $w_{g}=\frac{1}{|\mathcal{G}|}$. This way, all groups
would be equally represented in the audit dataset and would receive equal
fairness guarantees. The model auditor may choose $\mathbf{w}$ to increase the
weight of such groups, reflecting some desired policy.

Group fairness notions such as equal opportunity [13], equal odds [13], and
representation disparity [31] are widely used in practice. These notions
quantify “fairness” in terms of differences (or lack thereof) of a given
performance metric (e.g., FPR) across population groups. In general, group
fairness notions can be represented in terms of a _fairness violation metric_
, which will be zero if there is no performance disparity across groups, and
positive if some performance disparity exists (e.g., one group has a higher
FPR than the rest). We use fairness violation metrics to test if a given
machine learning model follows a specific fairness notion. Let F be a fairness
violation metric that takes the test dataset distribution $\widetilde{P}_{Z}$
as input and outputs a real number — F will depend on the group distribution
vector $\mathbf{w}$.

We are interested in testing if most groups $g\in\mathcal{G}$ are treated
similarly accordingly to the metric (i.e., $\texttt{F}(\widetilde{P}_{Z})=0$)
or if there exists a group that is being treated differently than the others
(i.e., $\texttt{F}(\widetilde{P}_{Z})\geq\epsilon$). Hence, we propose to use
a hypothesis test framework for testing if multi-group fairness metrics are
bigger than a fixed threshold. This is equivalent to the hypothesis test in
Definition 2.

######  Definition 1 ($\epsilon$-Test)

Given a fairness violation metric F for the dataset distribution
$\widetilde{P}_{Z}$ over $\mathcal{Z}$, we call the following hypothesis test
an $\epsilon$-test.

$\begin{cases}\text{H}_{0}:&\texttt{F}(\widetilde{P}_{Z})=0\\\
\text{H}_{1}:&\texttt{F}(\widetilde{P}_{Z})\geq\epsilon.\end{cases}$ (1)

We denote by $\psi_{\epsilon}:\mathcal{Z}^{n}\rightarrow\\{0,1\\}$ the
decision function that takes the dataset
$\mathcal{D}_{\text{audit}}=\\{z_{i}\\}_{0\leq i\leq n}$ such that
$z_{i}\in\mathcal{Z}$ and predicts

$\psi_{\epsilon}\left(\mathcal{D}_{\text{audit}}\right)=\begin{cases}0&\text{if
$\text{H}_{0}$ is true}\\\ 1&\text{if $\text{H}_{1}$ is true}.\end{cases}$ (2)

The decision function in Definition 2 aims to differentiate between
distributions from two separate decision regions ($\mathcal{P}_{0}$ and
$\mathcal{P}_{1}(\epsilon)$) in the set of all distributions in $\mathcal{Z}$.
Specifically, the decision regions $\mathcal{P}_{0}$ and
$\mathcal{P}_{1}(\epsilon)$ are given respectively by (3) and (4).

$\displaystyle\mathcal{P}_{0}$
$\displaystyle=\left\\{\left.\widetilde{P}_{Z}\sim\mathcal{Z}\right|\
\texttt{F}(\widetilde{P}_{Z})=0\right\\}$ (3)
$\displaystyle\mathcal{P}_{1}(\epsilon)$
$\displaystyle=\left\\{\left.\widetilde{P}_{Z}\sim\mathcal{Z}\right|\
\texttt{F}(\widetilde{P}_{Z})\geq\epsilon\right\\}$ (4)

where $\widetilde{P}_{Z}\sim\mathcal{Z}$ denotes that $\widetilde{P}_{Z}$ is
the dataset probability distribution with support on $\mathcal{Z}$. Assuming a
non-informative prior on the hypothesis $\text{H}_{0}$ and $\text{H}_{1}$, the
decision function has a probability of error equal to:

$P_{\text{error}}=\frac{\Pr(\psi_{\epsilon}=1|\text{H}_{0})+\Pr(\psi_{\epsilon}=0|\text{H}_{1})}{2}.$
(5)

Since we are distinguishing a single distribution from a set of distributions,
the above hypothesis test is a composite hypothesis test. Composite hypothesis
tests have been recently popularized under _distribution property testing_ ,
see [32] for a detailed survey on the topic.

In this section, we defined fairness violation metrics (F) and how to use them
to audit a model for multi-group fairness. In the next section, we study a
particular case of fairness violation metrics that we call max-gap fairness
(Definition 2) and show that performing a reliable $\epsilon$-test for max-gap
fairness require at least $O(|\mathcal{G}|/\epsilon^{2})$ samples.

##  III Max-Gap Fairness

Several fairness violation metrics F measure the magnitude of the difference
between model performance for a group and the average performance across all
the groups [22, 21, 13, 31, 26]. We call these metrics the max-gap fairness
and denote it by F_MaxGap. Formally, we define the max-gap fairness metrics as
follows.

######  Definition 2 (Max-Gap Fairness)

Let $L:\mathcal{Z}\rightarrow\\{0,1\\}$ be the quality of service function,
$\mathbf{w}\in\Delta^{|\mathcal{G}|}$ be the group weight vector, $P$ be a
distribution in $\mathcal{Z}$ that measures the average quality of service,
and define the average quality of service to be given by (6).

$\overline{L}(\mathbf{w})\triangleq\sum_{g\in\mathcal{G}}w_{g}\mathbb{E}_{P}[L(Z)|G=g].$
(6)

The fairness gap per group is denoted as $\Delta(g;P,L)$ an given by (7).

$\Delta(g;P,L,\mathbf{w})\triangleq\left|\mathbb{E}_{P}[L(Z)|G=g]-\overline{L}(\mathbf{w})\right|$
(7)

The _max-gap_ fairness metric F_MaxGap is the maximum fairness gap per group
$\Delta(g;P,L,\mathbf{w})$ for $g\in\mathcal{G}$ (8).

$\displaystyle\texttt{F\\_MaxGap}(P,L,\mathbf{w})$
$\displaystyle\triangleq\max_{g\in\mathcal{G}}\Delta(g;P,L,\mathbf{w}),$ (8)

when $L$, $P$, and $\mathbf{w}$ are clear from the context we just write
$\texttt{F\\_MaxGap}\triangleq\texttt{F\\_MaxGap}(P,L,\mathbf{w})$.

We demonstrate next how group fairness metrics such as Equal Opportunity (EO)
and Statistical Parity (SP) can be expressed in terms of the above max-gap
fairness definition.

######  Example 1 (Equal Opportunity)

Recall that the equal opportunity violation metric is given by

$\displaystyle\texttt{F}_{EO}$
$\displaystyle=\max_{g\in\mathcal{G}}\left|\Pr(\widehat{Y}=1|Y=0,G=g)-\Pr(\widehat{Y}=1|Y=0)\right|$
(9)
$\displaystyle=\max_{g\in\mathcal{G}}\left|\Pr(\widehat{Y}=1|Y=0,G=g)-\sum_{g\in\mathcal{G}}w_{g}\Pr(\widehat{Y}=1|Y=0,G=g))\right|.$
(10)

Note that we can recover $\texttt{F}_{EO}$ from the max-gap fairness
definition by taking

$\displaystyle L_{EO}(z)$ $\displaystyle=\mathbb{I}_{\widehat{y}=1},$ (11)
$\displaystyle P_{EO}(z)$ $\displaystyle=\widetilde{P}_{Z}(z|Y=0).$ (12)

We have that the fairness gap per group is given by

$\displaystyle\Delta(g;P_{EO},L_{EO},\mathbf{w})=\left|\Pr(\widehat{Y}=1|Y=0,G=g)-\sum_{g\in\mathcal{G}}w_{g}\Pr(\widehat{Y}=1|Y=0,G=g)\right|.$
(13)

Hence, we recover the equal opportunity violation metric

$\displaystyle\texttt{F}_{EO}$
$\displaystyle=\max_{g\in\mathcal{G}}\left|\Pr(\widehat{Y}=1|Y=0,G=g)-\sum_{g\in\mathcal{G}}w_{g}\Pr(\widehat{Y}=1|Y=0,G=g))\right|$
(14)
$\displaystyle=\max_{g\in\mathcal{G}}\Delta(g;P_{EO},L_{EO},\mathbf{w})=\texttt{F\\_MaxGap}(P_{EO},L_{EO},\mathbf{w}).$
(15)

######  Example 2 (Statistical Parity)

Recall that the statistical parity violation metric is given by

$\displaystyle\texttt{F}_{SP}$
$\displaystyle=\max_{g\in\mathcal{G}}\left|\Pr(\widehat{Y}=1|G=g)-\Pr(\widehat{Y}=1)\right|$
(16)
$\displaystyle=\max_{g\in\mathcal{G}}\left|\Pr(\widehat{Y}=1|G=g)-\sum_{g\in\mathcal{G}}w_{g}\Pr(\widehat{Y}=1|G=g))\right|.$
(17)

Note that we can recover $\texttt{F}_{SP}$ from the max-gap fairness
definition by taking

$\displaystyle L_{SP}(z)$ $\displaystyle=\mathbb{I}_{\widehat{y}=1},$ (18)
$\displaystyle P_{SP}(z)$ $\displaystyle=\widetilde{P}_{Z}(z).$ (19)

we have that the fairness gap per group is given by

$\displaystyle\Delta(g;P_{SP}(z),L_{SP},\mathbf{w})=\left|\Pr(\widehat{Y}=1|G=g)-\sum_{g\in\mathcal{G}}w_{g}\Pr(\widehat{Y}=1|G=g))\right|.$
(20)

Hence, we recover the statistical parity violation metric

$\displaystyle\texttt{F}_{SP}$
$\displaystyle=\max_{g\in\mathcal{G}}\left|\Pr(\widehat{Y}=1|G=g)-\sum_{g\in\mathcal{G}}w_{g}\Pr(\widehat{Y}=1|G=g))\right|$
(21)
$\displaystyle=\max_{g\in\mathcal{G}}\Delta(g;P_{SP}(z),L_{SP},\mathbf{w})=\texttt{F\\_MaxGap}(P_{SP}(z),L_{SP},\mathbf{w}).$
(22)

Using a similar process, we can recover other fairness metrics such as
calibration [33].

Since max-gap fairness measures the violation in fairness metrics, we aim to
ensure that the gap $\texttt{F\\_MaxGap}(P,L,\mathbf{w})\approx 0$. Achieving
this condition implies that the model $f_{\theta}$ is “treating” all groups
$\mathcal{G}$ in the population similarly per the chosen fairness notion.
However, in general, we don’t have access to the distribution $P$; therefore,
it is not possible to compute $\mathbb{E}_{P}[L(Z)|G=g]$ for all
$g\in\mathcal{G}$ exactly. Hence, we can’t exactly compute
$\texttt{F\\_MaxGap}(P,L,\mathbf{w})$ the fairness metric we are interested
in. Regardless, we can estimate $\texttt{F\\_MaxGap}(P,L,\mathbf{w})$ using
$n$ i.i.d. samples from $P$. When we are interested in ensuring that the model
is treating only two groups similarly, i.e., when $\mathcal{G}=\\{0,1\\}$, We
can estimate $\texttt{F\\_MaxGap}(P,L,\mathbf{w})$ using $n=O(1/\epsilon^{2})$
i.i.d. samples from $P$ and then reliably test if
$\texttt{F\\_MaxGap}(P,L,\mathbf{w})\approx 0$ — this result is an immediate
application of Chebyshev inequality [34]. Also, in [21, Theorem 2.11], it was
shown that using the same procedure we can estimate
$\texttt{F\\_MaxGap}(P,L,\mathbf{w})$ for multi-group fairness using
$n=O(|\mathcal{G}|/\epsilon^{2})$ i.i.d. samples from $P$

In this work, we are interested in the case where $|\mathcal{G}|$ is large —
for example, when it contains exponentially many combinations of sensitive
attributes, and intersectionality is considered. Here, the fairness
definitions of interest will be the maximum gap fairness as in (8), but
$|\mathcal{G}|$ can grow exponentially. In this regime, estimating the
fairness metrics given by F_MaxGap (8) is challenging. It is necessary to
estimate $\mathbb{E}_{P}[L(Z)|G=g]$ for all $g\in\mathcal{G}$; hence, if
$|\mathcal{G}|$ is sufficiently large, performing all these estimations is
impractical [21, 26, 22]. In fact, we show that even _testing_ if F_MaxGap is
above a given threshold is challenging, requiring further assumptions on the
hypothesis test procedure to reduce sample complexity.

Next, we show that the max-gap fairness metrics discussed in Definition 2
_require_ at least $O(|\mathcal{G}|/\epsilon^{2})$ samples for the
$\epsilon$-test to have a small probability of error. In Proposition 24, we
use the fact that there exist two distributions $P_{0}\in\mathcal{P}_{0}$ and
$P_{1}\in\mathcal{P}_{1}(\epsilon)$ that are close in the space of
distributions in terms of Hellinger divergence [35]. Intuitively, the fact
that the hypothesis regions are close indicates that it is difficult to
distinguish between certain distributions in them. In Proposition 24, we show
that the probability of error of the $\epsilon$-test is bounded away from $0$.

###### Proposition 1

[Converse for Max-Gap Fairness] For max-gap fairness metrics F_MaxGap (e.g.,
equal opportunity in Example 1 and statistical parity in Example 2) with
quality of service function $L$ and measuring the average quality of service
using the distribution $P$ such that
$(L,P)\in\\{(L_{EO},P_{EO}),(L_{SP},P_{SP})\\}$. If $\epsilon\in[0,0.5]$ and
$w_{g}=P(G=g)=\frac{1}{|\mathcal{G}|}$ for all $g\in\mathcal{G}$, using $n$
i.i.d. samples from $P$ the minimum probability of error of performing an
$\epsilon$-test for F_MaxGap in Definition 2 is lower bounded by

$2\inf_{\psi_{\epsilon}}P_{\text{error}}\geq
1-\left[2\left(1-\left(1-\frac{2\epsilon^{2}}{|\mathcal{G}|}\right)^{n}\right)\right]^{1/2}.$
(23)

Furthermore, it is necessary to have access to $n$ given in (24) i.i.d.
samples from $P$ to test if $\texttt{F\\_MaxGap}=0$ or
$\texttt{F\\_MaxGap}\geq\epsilon$ correctly with probability $0.99$.

$n=\Omega\left(\frac{|\mathcal{G}|}{\epsilon^{2}}\right).$ (24)

We provide the proof for this result in Appendix A.

In Proposition 24, we have shown that the probability of error in the
hypothesis test is lower bounded by a function of $n$ the number of samples
from $P_{|Y=0}$, $|\mathcal{G}|$ the number of groups, and $\epsilon$ and
111The results in Proposition 24 were given in terms of the equal opportunity
fairness metric. However, our proof can be trivially extended to several
fairness metrics with $L:\mathcal{Z}\rightarrow\\{0,1\\}$. it is necessary to
have at least $n=O\left({|\mathcal{G}|}/{\epsilon^{2}}\right)$ samples to
audit a model for max-gap fairness. Thus, a hypothesis test approach cannot
decrease the sample complexity of auditing a model for max-gap fairness. Next,
we define a fairness metric based on the conditional value-at-risk, aiming to
decrease the sample complexity of testing for multi-group fairness.

##  IV CVaR Multi-Group Fairness Metrics

In this section, we define the conditional value-at-risk (CVaR) fairness and
prove the properties of this multi-group fairness metric. Our definition of
CVaR fairness is motivated by conditional value-at-risk [27] and its use in
the fairness literature [36]. The CVaR fairness is an extension of the usual
definition of fairness given in Definition 2,i.e., we will show that it is
possible to recover Definition 2 from the CVaR fairness in Definition 3.

The definition of CVaR for a random variable $W$ starts by computing
$q_{\alpha}(W)$ the $\alpha$-quantile of $W$ for $\alpha\in[0,1)$. The
$\alpha$-quantile of a random variable $W$ is defined to be a number
$q_{\alpha}(W)$ such that

$\displaystyle\Pr[W\geq q_{\alpha}(W)]$ $\displaystyle\geq 1-\alpha$ (25)
$\displaystyle\Pr[W\leq q_{\alpha}(W)]$ $\displaystyle\geq\alpha.$ (26)

Then, the conditional value-at-risk at level $\alpha$ is denoted by
$\text{CVaR}_{\alpha}(W)$ and given by 27 – CVaR was proposed by [27].

$\text{CVaR}_{\alpha}(W)\triangleq\mathbb{E}[W|W\geq q_{\alpha}(W)]$ (27)

Intuitively, $\text{CVaR}_{\alpha}(W)$ measures the tail behavior of $W$. For
example, when $\alpha=1$ the conditional value-at-risk becomes the maximum
over all possible values of $W$ an event that may have vanishing probability.
The case of interest in multi-group fairness (when testing is hard) is when
only a small group is treated differently from all others, i.e., when
$g\in\mathcal{G}$ is small ($w_{g}$ is small) but $\Delta(g)\geq\epsilon$.
Hence, we are interested in the tail behavior of $\Delta(g)$. For this reason,
next, we define CVaR fairness to capture the desired tail behavior.

######  Definition 3 (CVaR Fairness)

Let $L:\mathcal{Z}\rightarrow\\{0,1\\}$ be the quality of service function,
$\mathbf{w}$ be the group importance weight vector defined by the auditor, and
$P$ be the distribution that measures the average quality of service
$\overline{L}(\mathbf{w})$. Recall that

$\Delta(g)=\left|\mathbb{E}_{P}[L(Z)|G=g]-\overline{L}(\mathbf{w})\right|.$

For all $\alpha\in[0,1)$, we denote CVaR fairness as
$\texttt{F\\_CVaR}_{\alpha}(\mathbf{w};P,L,\overline{L}(\mathbf{w}))$ and
define it by

$\displaystyle Q_{\alpha}$ $\displaystyle\triangleq\arg\max_{\sum_{g\in
Q\subset\mathcal{G}}w_{g}\leq 1-\alpha}\sum_{g\in Q_{\alpha}}w_{g}\Delta(g)$
(28)
$\displaystyle\texttt{F\\_CVaR}_{\alpha}(\mathbf{w};P,L,\overline{L}(\mathbf{w}))$
$\displaystyle\triangleq\frac{1}{1-\alpha}\sum_{g\in
Q_{\alpha}}w_{g}\Delta(g).$ (29)

We can also write
$\texttt{F\\_CVaR}_{\alpha}(\mathbf{w};P,L,\overline{L}(\mathbf{w}))$ as

$\texttt{F\\_CVaR}_{\alpha}(\mathbf{w};P,L,\overline{L}(\mathbf{w}))=\frac{1}{1-\alpha}\max_{\sum_{g\in
Q\subset\mathcal{G}}w_{g}\leq\alpha}\sum_{g\in Q}w_{g}\Delta(g).$

When $P,L,\overline{L}(\mathbf{w})$ are clear from the context we denote
$\texttt{F\\_CVaR}_{\alpha}(\mathbf{w};P,L,\overline{L}(\mathbf{w}))$ by
$\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})$.

Our definition for the CVaR fairness is more lenient than the usual multi-
group fairness in Definition 2. Particularly, CVaR fairness gives stronger
fairness guarantees when $\alpha$ is close to $1$. However, it gives
practitioners the flexibility of allowing $\alpha$ to be smaller and make
$\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})$ easier to estimate — i.e., decrease
the sample complexity to perform an $\epsilon$-test for
$\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})$.

Note that when $\alpha=0$, $\texttt{F\\_CVaR}_{0}(\mathbf{w})$ corresponds to
the average fairness gap of all groups. In this case, we can estimate
$\texttt{F\\_CVaR}_{0}(\mathbf{w})$ with precision $\epsilon$ using
$n=O\left(\frac{1}{\epsilon^{2}}\right)$ samples from $P$. Thus, it is
possible to perform the $\epsilon$-test reliably using
$O\left(\frac{1}{\epsilon^{2}}\right)$ samples from $P$ — we conclude that by
a simple application of Chebyshev’s inequality [34].

As a middle ground example between easy testing ($\alpha=0$) and the max-gap
fairness in Definition 2, consider the following example.

######  Example 3 (CVaR Equal Opportunity)

Let $\alpha=0.75$, the quality of service function be $L_{EO}$, and $P_{EO}$
be given by the equal opportunity fairness metric in Example 1. The fairness
gap per group is given by

$\Delta(g)=\left|\Pr(\hat{Y}=1|Y=0,G=g)-\sum_{g\in\mathcal{G}}w_{g}\Pr(\widehat{Y}=1|Y=0,G=g))\right|.$
(30)

Therefore, the CVaR Equal Opportunity is given by

$\texttt{F\\_CVaR}_{0.75}(\mathbf{w})=\frac{1}{0.25}\max_{\sum_{g\in
Q\subset\mathcal{G}}w_{g}\leq 0.25}\sum_{g\in Q}w_{g}\Delta(g).$ (31)

Therefore, we need to estimate a quantity with probability mass $0.25$, in
contrast with Example 1, where estimating a quantity with potentially
vanishing probability was necessary.

In Proposition 2, we show that we can recover max-gap fairness (Definition 2)
by choosing an appropriate value for $\alpha$ — max-gap fairness is hard to
estimate and may demand $O\left(|\mathcal{G}|\right)$ samples from $P$ to
perform an $\epsilon$-test reliably as saw in Proposition 24.

###### Proposition 2

[$\texttt{F\\_CVaR}_{\alpha}$ recovers F_MaxGap] For all
$\mathbf{w}\in\Delta^{|\mathcal{G}|}$, $L:\mathcal{Z}\rightarrow\\{0,1\\}$,
and any distribution $P$ with support on $\mathcal{Z}$, there exists
$\alpha^{*}\in[0,1)$ such that

$\texttt{F\\_MaxGap}(P,L,\overline{L}(\mathbf{w}))=\texttt{F\\_CVaR}_{\alpha^{*}}(\mathbf{w};P,L,\overline{L}(\mathbf{w})).$
(32)

When
$\mathbf{w}=\left(\frac{1}{|\mathcal{G}|},...,\frac{1}{|\mathcal{G}|}\right)$
we have that $\alpha^{*}=1-\frac{1}{|\mathcal{G}|}$.

We show this result in Appendix B. Proposition 2 indicates that by choosing a
suitable $\alpha\in[0,1)$ we can obtain a reasonable trade-off between sample
complexity and fairness guarantees. In Sections V-C, we show how to leverage
the flexibility provided by $\alpha$ to efficiently test for multi-group
fairness.

For all choices of $\alpha\in[0,1)$ we prove that
$\texttt{F\\_MaxGap}(P,L,\overline{L}(\mathbf{w}))$ is lower bounded by
$\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})$. This shows why CVaR fairness is a
lenient version of the standard multi-group fairness in Definition 2. In
Proposition 33, we show that $\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})$ lower
bounds $\texttt{F\\_MaxGap}(P,L,\overline{L}(\mathbf{w}))$.

###### Proposition 3

[$\texttt{F\\_CVaR}_{\alpha}$ is a lower bound for F_MaxGap] For all
$L:\mathcal{Z}\rightarrow\\{0,1\\}$, distribution $P$ with support on
$\mathcal{Z}$ and distribution $P$ with support on $\mathcal{Z}$,
$\mathbf{w}\in\Delta^{|\mathcal{G}|}$, and $\alpha\in[0,1)$ we have that

$0\leq\texttt{F\\_CVaR}_{\alpha}(\mathbf{w};P,L,\overline{L}(\mathbf{w}))\leq\texttt{F\\_MaxGap}(P,L,\overline{L}(\mathbf{w}))\leq
1.$ (33)

We provide a proof for this result in Appendix B.

Proposition 33 shows that
$\texttt{F\\_MaxGap}(P,L,\overline{L}(\mathbf{w}))\geq\epsilon$ does not
necessarily imply $\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})\geq\epsilon$. For
this reason, performing an $\epsilon$-test using
$\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})$ is more lenient than performing the
same test for $\texttt{F\\_MaxGap}(L,\overline{L}(\mathbf{w}))$. However,
Proposition 33 ensures that if
$\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})\geq\epsilon$ then
$\texttt{F\\_MaxGap}(L,\overline{L}(\mathbf{w}))\geq\epsilon$ which is what we
will test in Section V-C.

In this section, we have defined the CVaR fairness and showed that (i) it is
an extension of the standard multi-group fairness metrics given in Definition
2 (Proposition 2), (ii) CVaR fairness is a more lenient metric than the max-
gap fairness metrics in Definition 2, and (iii) CVaR fairness is a value in
the square $[0,1]$ as max-gap fairness (Proposition 33). Moreover, we
exemplified that by carefully choosing $\alpha$ we can leverage the trade-off
between sample complexity to perform a $\epsilon$-testing and fairness –
Example 3 and Proposition 33.

In the next section, we propose a testing algorithm that leverages the trade-
off between sample complexity and fairness guarantees from CVaR fairness to
efficiently perform an $\epsilon$-test.

##  V Testing for CVaR Fairness

###  V-A Data collection process

In order to test for $\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})$, we need to
collect an audit dataset $\mathcal{D}_{\text{audit}}$. We propose two ways of
collecting this dataset — weighted sampling (Definition 5) and attribute-
specific sampling (Definition 6). We denote $M_{g}$ as the number of samples
from group $g$ in the audit dataset. In general, $M_{g}$ can be a random
variable.

Due to the cost of acquiring new samples, there is a limit on the dataset size
one can collect. For this reason, next, we define the notion of a data budget
that a practitioner may have when testing for CVaR fairness.

######  Definition 4 (Data Budget)

A model is audited with a data budget equal to $n\in\mathbb{N}$ when the
expected number of samples used to audit the model is equal to $n$ — i.e.,
(34) holds.

$n\triangleq\sum_{g\in\mathcal{G}}\mathbb{E}[M_{g}].$ (34)

We now propose two ways of collecting data. We start with the weighted
sampling, when the audit dataset $\mathcal{D}_{\text{audit}}$ is constructed
using i.i.d. samples.

######  Definition 5 (Weighted Sampling)

Let $M_{g}$ be the number of samples from group $g\in\mathcal{G}$. Under a
data budget $n$, we define the number of samples per group as

$M_{g}\triangleq\text{Bin}(n,v_{g})\ \ \forall g\in\mathcal{G}.$

Where $\text{Bin}(n,v_{g})$ represents the Binomial distribution with
parameters $n\in\mathbb{N}$. Moreover,
$\mathbf{v}=(v_{1},...,v_{|\mathcal{G}|})\in\Delta^{|\mathcal{G}|}$ is the
group marginal distribution from the audit dataset
$\mathcal{D}_{\text{audit}}$, i.e., $v_{g}=P_{Z}(G=g)$, and
$\sum_{g\in\mathcal{G}}\mathbb{E}[M_{g}]=n$.

Note that the group marginal $v_{g}$ may be different from $\mathbf{w}$ (the
underlying or prior group distribution). To provide additional flexibility for
model auditor, we set

$v_{g}=\frac{w^{\eta}_{g}}{\sum_{g^{\prime}}w^{\eta}_{g^{\prime}}},$ (35)

where $\eta\in[0,\infty)$. Of these, two special cases are $\eta=0$ (uniform
distribution) and $\eta=1$ (when $v_{g}=w_{g}$).

The model auditor may also decide to collect the data without ensuring that
samples are i.i.d. from some distribution to optimize the sample complexity of
performing an $\epsilon$-test. Next, we define attribute specific sampling, a
non-i.i.d. sampling strategy that will allow the model auditor to achieve a
sample complexity that is independent of the number of groups $|\mathcal{G}|$
— Corollary 2.

######  Definition 6 (Attribute Specific Sampling)

Let $M_{g}$ be the number of samples from group $g\in\mathcal{G}$, and
$\mathbf{w}=(w_{1},...,w_{|\mathcal{G}|})$ be the group weight vector. Under a
data budget $n$, we define the number of samples per group as

$M_{g}\triangleq\text{Ber}(\min\\{\gamma w_{g},1\\})\frac{n}{\gamma}\ \
\forall g\in\mathcal{G}.$

Where $\text{Ber}(\min\\{\gamma w_{g},1\\})$ represents the Bernoulli
distribution with parameter $\min\\{\gamma w_{g},1\\}$,
$\gamma\in[0,+\infty)$, and $\sum_{g\in\mathcal{G}}\mathbb{E}[M_{g}]=n$.

In the next section we propose an estimator $\widehat{F}(\mathbf{w})$ that we
will use to audit the model for CVaR fairness.

###  V-B Estimator

Estimating the value of the CVaR fairness metric
($\texttt{F\\_CVaR}_{\alpha}$) may still be difficult and require a high
sample complexity. However, in this work, we are only interested in performing
an $\epsilon$-test, i.e., testing if the CVaR fairness metric is bigger than
$\epsilon$ or equal to zero. For this reason, instead of defining an estimator
that tries to approximate $\texttt{F\\_CVaR}_{\alpha}$, we define it with the
sole objective of testing if $\texttt{F\\_CVaR}_{\alpha}>\epsilon$. Definition
36 formalizes the definition of the estimator for testing
$\texttt{F\\_CVaR}_{\alpha}$.

######  Definition 7 (Estimator for testing $\texttt{F\\_CVaR}_{\alpha}$)

Let $\texttt{F\\_CVaR}_{\alpha}$ be the CVaR fairness metric that uses the
quality of service function $L:\mathcal{Z}\rightarrow\\{0,1\\}$, the average
quality of service $\overline{L}(\mathbf{w})$, and uses the distribution $P$
for $\mathcal{Z}$. Define $M_{g}$ to be a random variable in $\mathbb{N}$, and
assume we have access to $M_{g}$ samples from $P(Z|G=g)$ for each group
$g\in\mathcal{G}$ — note that some $M_{g}$ may be equal to $0$.

If $M_{g}=0$ then define:

$\frac{\sum_{j=1}^{M_{g}}L(z_{j})}{M_{{g}}}\triangleq 0$

If $M_{g}\in\\{0,1\\}$ then define:

$\frac{\sum_{i=1}^{M_{g}}L(z_{i})}{M_{g}}\frac{(\sum_{i=1}^{M_{g}}L(z_{i})-1)}{M_{g}-1}\triangleq
0$

Then, define the estimators $\widehat{F}_{1}$ and $\widehat{F}_{2}$ as
follows.

$\displaystyle\widehat{F}_{1}(\mathbf{w})$
$\displaystyle\triangleq\sum_{{g}\in\mathcal{G}}\frac{w_{g}}{P\left[M_{{g}}\geq
2\right]}\frac{\sum_{i=1}^{M_{g}}L(z_{i})}{M_{g}}\frac{(\sum_{i=1}^{M_{g}}L(z_{i})-1)}{M_{g}-1}$
$\displaystyle\widehat{F}_{2}(\mathbf{w})$
$\displaystyle\triangleq\sum_{{g}\in\mathcal{G}}\frac{w_{g}}{P\left[M_{{g}}\geq
1\right]}\frac{\sum_{j=1}^{M_{g}}L(z_{j})}{M_{{g}}}$

Therefore, define the estimator for $\texttt{F\\_CVaR}_{\alpha}$ as:

$\widehat{F}(\mathbf{w})\triangleq\widehat{F}_{1}(\mathbf{w})-\left(\widehat{F}_{2}(\mathbf{w})\right)^{2}.$
(36)

In Appendix C we derive some of the properties, such as the mean and the
variance, of the proposed estimator $\widehat{F}(\mathbf{w})$.

The estimator in Definition 36 gives practitioners flexibility by allowing
them to sample the number of data points $M_{g}$ they will use from each group
$g\in\mathcal{G}$. Moreover, allowing the number of samples for a group to be
zero ($M_{g}=0$) may allow a better sample complexity than $O(|\mathcal{G}|)$
— which is why we use this strategy. In the next section we use the proposed
estimator along with the introduced sampling strategies to efficiently perform
the $\epsilon$-test for the CVaR fairness metric.

In the next section we propose an specific decision function $\psi_{\epsilon}$
that uses the auditing dataset $\mathcal{D}_{\text{audit}}$ to compute the
estimator in Definition 36 and output if the model is CVaR multi-group fair.

###  V-C An Efficient Test For Multi-Group Fairness

In this section, we provide an algorithm to perform the $\epsilon$-test for
the CVaR fairness metric. We show that our algorithm can perform
$\epsilon$-test reliably with at most
$n=O\left(\frac{2^{\frac{1}{2}H_{2/3}(w)}}{\epsilon^{2}(1-\alpha)}+\frac{2^{\frac{1}{3}H_{2/3}(w)}}{\epsilon^{4}(1-\alpha)^{2}}\right)$
samples when using weight sampling — where $H_{2/3}$ denotes the Rényi entropy
of order $2/3$. Additionally, we show that when using attribute specific
sampling, we can perform $\epsilon$-test for CVaR fairness reliably with at
most $n=O\left(\frac{1}{\epsilon^{4}(1-\alpha)^{2}}\right)$.

We propose Algorithm 1 to perform an $\epsilon$-test by using the estimator
for the CVaR fairness metric proposed in Section V-B. The algorithm takes a
data budget $n$, the information about the multi-group fairness metric being
used, and returns which hypothesis is true (i.e., $\text{H}_{0}$ is true or
$\text{H}_{1}$ is true).

The proposed algorithm starts by defining the number of samples per group
$M_{g}$. When the dataset is fixed, $M_{g}$ is a prefixed constant. However,
if the model auditor has control of the dataset construction, they can use
weighted sampling (Definition 5) or attribute specific sampling (Definition 6)
to define $M_{g}$. Next, it computes the CVaR fairness metric estimator
$\widehat{F}(\mathbf{w})$ in Definition 36. Finally, it performs a threshold
test comparing $\widehat{F}(\mathbf{w})$ with
$\frac{(1-\alpha)\epsilon^{2}}{2}$. We formalize this process in Algorithm 1.

Algorithm 1 CVaR Test

$n\geq 0$, $L$, $\overline{L}(\mathbf{w})$, $P$, and
$\\{Q_{g}\\}_{g\in\mathcal{G}}$.

$M_{g}\sim Q_{g}$ $\triangleright$ Sample $M_{g}$ from $Q_{g}$ s.t.
$\Pr(M_{g}=k)=Q_{g}(k)$.

Sample $M_{g}$ i.i.d. points from $P_{|G=g}\ \ \forall g\in\mathcal{G}$

Compute $\widehat{F}(\mathbf{w})$ as in Def. 36

if $\widehat{F}(\mathbf{w})\geq\frac{(1-\alpha)\epsilon^{2}}{2}$ then

return $\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})\geq\epsilon$

else if $\widehat{F}(\mathbf{w})<\frac{(1-\alpha)\epsilon^{2}}{2}$ then

return $\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})=0$

end if

We show that the sample complexity for an $\epsilon$-test to differentiate
between $\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})=0$ and
$\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})>\epsilon$ using Algorithm 1 is more
favorable than $O(|\mathcal{G}|/\epsilon^{2})$ — differently than the standard
multi-group fairness metrics in Definition 2 which needs at least
$\Omega(|\mathcal{G}|/\epsilon^{2})$ samples to perform a reliable
$\epsilon$-test.

We first prove that the probability of error in (5) is bounded when using
Algorithm 1 as the decision function. Theorem 37 shows that the probability of
error is bounded when using weighted sampling, and it depends on the test data
group distribution $\mathbf{v}=(v_{1},...,v_{|\mathcal{G}|})$.

###### Theorem 1

[Achievability with weighted sampling] Let
$\mathbf{w}\in\Delta^{|\mathcal{G}|}$ be the group weight vector,
$L:\mathcal{Z}\rightarrow\\{0,1\\}$ be the quality of service function, and
$\overline{L}(\mathbf{w})$ is the average quality of service. Suppose we have
access to $n$ i.i.d. samples using, i.e., we used weighted sampling in
Algorithm 1. Then,

$Q_{g}(k)=\Pr(\text{Bin}(n,v_{g})=k),$

where $\mathbf{v}=(v_{1},...,v_{|\mathcal{G}|})$ is the group marginal from
$P_{Z}$ that we sampled i.i.d. to generate $\mathcal{D}_{\text{audit}}$.

The probability of error ($P_{\text{error}}$ in (5)) for Algorithm 1 to
differentiate $\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})=0$ from
$\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})>\epsilon$ is such that

$P_{\text{error}}=O\left(\frac{1}{(1-\alpha)^{2}\epsilon^{4}n^{2}}\sum_{g}\frac{w_{g}^{2}}{v_{g}^{2}}+\frac{1}{n(1-\alpha)^{2}\epsilon^{4}}\sum_{g}\frac{w_{g}^{2}}{v_{g}}\right).$
(37)

We show this result in Appendix C. Next, we show how large $n$ needs to be to
ensure that the upper bound in Theorem 37 is smaller than a fixed $\delta>0$.
This result gives an upper bound for the sample complexity of testing for CVaR
fairness using Algorithm 1.

Recall that the Rényi entropy of order $\rho$ for $\rho\geq-1$ is defined
as222We extend the definition at $\rho=1$ via continuous extension.

$H_{\rho}(\mathbf{w}):=\frac{1}{1-\rho}{\log_{2}}\sum_{s\in\mathcal{S}}(w_{s})^{\rho}.$
(38)

Notice that $H_{1}(\mathbf{w})=-\sum_{g\in\mathcal{G}}w_{g}\log w_{g}$ is the
Shannon entropy; and $H_{0}(\mathbf{w})=|\mathcal{G}|$ is the max-entropy.
Corollary 1 gives the upper bound in terms of the Rényi entropy of order $2/3$
of the group distribution $\mathbf{w}$.

###### Corollary 1

[Sample complexity of Algorithm 1] Under the same assumption of Theorem 37
(using weighted sampling). With probability at least $0.99$, comparing
$\widehat{F}(\mathbf{w})$ to $(1-\alpha)\epsilon^{2}/2$, one can differentiate
between $\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})=0$ and
$\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})>\epsilon$ using at most the following
number of samples

$n=O\left(\frac{\left(\sum_{g\in\mathcal{G}}\frac{w_{g}^{2}}{v_{g}^{2}}\right)^{1/2}}{\epsilon^{2}(1-\alpha)}+\frac{\sum_{g}\frac{w_{g}^{2}}{v_{g}}}{\epsilon^{4}(1-\alpha)^{2}}\right).$
(39)

Moreover, when the model auditor can control the choice of group marginal in
the test dataset and set
$v_{g}=\frac{w_{g}^{2/3}}{\sum_{g^{*}}w_{g^{*}}^{2/3}}$, it is only necessary
to have access to $n$ samples such that

$n=O\left(\frac{2^{\frac{1}{2}H_{2/3}(w)}}{\epsilon^{2}(1-\alpha)}+\frac{2^{\frac{1}{3}H_{2/3}(w)}}{\epsilon^{4}(1-\alpha)^{2}}\right).$
(40)

We show this result in Appendix C. Note that we show the result for error
probability $0.01$, this may be improved by using the median of the means
technique, improving the dependence to $\log(1/\delta)$, as in [37, Page 8].

Note that when $\epsilon$ and $1-\alpha$ are constants and bounded away from
zero, the dominant term in the sample complexity is the first term
$O\left(\frac{2^{\frac{1}{2}H_{2/3}(w)}}{\epsilon^{2}(1-\alpha)}\right)$.
Corollary 1 shows that the sample complexity of performing an $\epsilon$-test
CVaR fairness using Algorithm 1 with weighted sampling ($v_{g}\propto
w_{g}^{2/3}$) has a smaller exponent than testing for standard multi-group
fairness metrics as shown in Proposition 24 (testing for standard multi-group
fairness has sample complexity $O\left(|\mathcal{G}|\right)$), because

$2^{\frac{1}{2}H_{2/3}(\mathbf{w})}\leq
2^{\frac{1}{2}\log(|\mathcal{G}|)}=|\mathcal{G}|^{\frac{1}{2}}\leq|\mathcal{G}|.$
(41)

In the worst-case-scenario, when $\mathbf{w}$ maximizes the Rényi entropy the
sample complexity is upper bounded by
$O\left(|\mathcal{G}|^{\frac{1}{2}}\big{/}((1-\alpha)\epsilon^{2})\right)$
providing a smaller sample complexity than i.i.d. testing using standard
multi-group fairness metrics as shown in Proposition 24 — Rényi entropy is
maximized for $w_{g}=\frac{1}{|\mathcal{G}|}$ for all $g\in\mathcal{G}$.

Moreover, when the model auditor can control the data collection process, they
can choose to sample according to Algorithm 1 to decrease the sample
complexity further. For example, when the model auditor has access to at least
$2$ samples of any given group $g\in\mathcal{G}$ in the population and can
perform non-i.i.d. sampling, they can use attribute specific sampling. Next,
we show that by choosing $M_{g}$ using attribute specific sampling (Definition
6), we can get a bound on the probability of error for the $\epsilon$-test
that is independent of $\mathbf{w}$. We show this result in Theorem 2.

###### Theorem 2

[Achievability with attribute specific sampling] Let $\mathbf{w}$ be such that
$\max_{g}w_{g}\leq c\cdot\epsilon^{4}$ for a sufficiently small constant $c$,
$L:\mathcal{Z}\rightarrow\\{0,1\\}$ the quality of service function, and
$\overline{L}(\mathbf{w})$ the average quality of service. Using attribute
specific sampling in Algorithm 1, i.e.

$Q_{g}(k)=\Pr\left(\text{Ber}(\min(1,\gamma w_{g}))\frac{n}{\gamma}=k\right),$

where $\gamma=\frac{n}{2}$.

The probability of error ($P_{\text{error}}$ in (5)) for Algorithm 1 to
differentiate $\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})=0$ from
$\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})>\epsilon$ is bounded by:

$P_{\text{error}}=O\left(\frac{1}{\epsilon^{4}(1-\alpha)^{2}n}\right).$ (42)

We show this result in Appendix C. As an immediate consequence of Theorem 2,
we can compute the sample complexity of testing using Algorithm 1 with
attribute specific sampling. In Corollary 2, we show that using attribute
specific sampling allows us to confidently perform an $\epsilon$-test using a
number of data points that do not depend on the number of group
$|\mathcal{G}|$.

###### Corollary 2

[Sample complexity of Algorithm 1 using attribute specific sampling] Let
$\mathbf{w}$ be such that $\max_{g}w_{g}\leq c\cdot\epsilon^{4}$ for a
sufficiently small constant $c$. With probability at least $0.99$, comparing
$\widehat{F}(\mathbf{w})$ to $(1-\alpha)\epsilon^{2}/2$, one can differentiate
between $\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})=0$ and
$\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})>\epsilon$ using at most the following
number of samples $n$:

$n=O\left(\frac{1}{\epsilon^{4}(1-\alpha)^{2}}\right).$

We provide the proof for this result in Appendix C. In this section, we have
shown that it is possible to perform an $\epsilon$-test for CVaR fairness
reliably using
$O\left(\frac{2^{\frac{1}{2}H_{2/3}(w)}}{\epsilon^{2}(1-\alpha)}+\frac{2^{\frac{1}{3}H_{2/3}(w)}}{\epsilon^{4}(1-\alpha)^{2}}\right)$
samples from $P$ when using Algorithm 1 with weighted sampling — which is
i.i.d. We also showed that, by using Algorithm 1 with attribute specific
sampling (which is non-i.i.d.), we can reliably test for CVaR fairness with
$n=O\left(\frac{1}{\epsilon^{4}(1-\alpha)^{2}}\right)$ samples from $P$.

In the next section, we show that by using weighted sampling with $\mathbf{w}$
uniform, it is actually necessary to use
$O\left(\frac{2^{\frac{1}{2}H_{2/3}(\mathbf{w})}}{(1-\alpha)^{1/2}\epsilon^{2}}\right)=O\left(\frac{|\mathcal{G}|^{1/2}}{(1-\alpha)^{\frac{1}{2}}\epsilon^{2}}\right)$
samples from $P$ for performing an $\epsilon$-test reliably. Indicating that
Algorithm 1 has optimal dependency on $\mathbf{w}$ and $|\mathcal{G}|$.

##  VI Converse Result for CVaR Fairness Testing under weighted sampling

We present next a converse result for the sample complexity of the
$\epsilon$-test for CVaR fairness under weighted sampling. Our result ensures
that the performance of Algorithm 1 has optimal order when $\mathbf{w}$ is a
uniform distribution over all groups. We prove this optimality by showing that
no test can differentiate between $\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})=0$
and $\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})\geq\epsilon$ using less than
$\Omega\left(\frac{\sqrt{|\mathcal{G}|}}{\epsilon^{2}}\right)$ i.i.d. samples
— Theorem 45. As a consequence of this result, we provide an operational
meaning for the Rényi entropy of order $2/3$ as the log of the number of
samples that is necessary to perform an $\epsilon$-test for CVaR reliably.

We proved a similar converse result for the max-gap fairness metrics in
Proposition 24. For max-gap fairness we were able to design two distributions
$P_{0}$ and $P_{1}$ that are close together in the space of all distributions
in $\mathcal{Z}$ according to the Hellinger divergence but at the same time
$\texttt{F\\_CVaR}_{\alpha}(\mathbf{w};P_{0})=0$ and
$\texttt{F\\_CVaR}_{\alpha}(\mathbf{w};P_{1})\geq\epsilon$ — Proposition 24.
Using these distributions, we leveraged the Le Cam Lemma [38] from the binary
hypothesis test literature and showed that it is necessary to have
$n=\Omega(|\mathcal{G}|)$ samples to perform an $\epsilon$-test for max-gap
fairness reliably — Proposition 24.

Alas, the proof strategy for deriving a converse result for max-gap fairness
testing does not directly apply to CVaR testing. The reason is that it is not
possible to design distributions $P_{0}$ and $P_{1}$ as before. In fact, we
can show that if two distributions have CVaR fairness far apart, then the
total variation distance between them is also far apart. Specifically, if we
design $\texttt{F\\_CVaR}_{\alpha}(\mathbf{w};P_{0})=0$ and
$\texttt{F\\_CVaR}_{\alpha}(\mathbf{w};P_{1})\geq\epsilon$ we cannot guarantee
that $\text{TV}(P_{0}||P_{1})$ is sufficiently small to match our achievable
sample complexity bound. Hence, the approach from Proposition 24 fails.

As an alternative to the approach in Proposition 24, we take a different route
and use the Generalized Le Cam Lemma for a mixture of distributions [39].
Instead of showing that there exist distributions $P_{0}$ and $P_{1}$ with
distant CVaR fairness metric but close distance in the space of distributions,
we design a sequence of distributions $\\{P_{u}\\}_{\mathcal{U}}$ indexed by
$\mathcal{U}$ such that
$\texttt{F\\_CVaR}_{\alpha}(\mathbf{w};P_{u})\geq\epsilon$ for all
$u\in\mathcal{U}$, and also $P_{0}$ such that
$\texttt{F\\_CVaR}_{\alpha}(\mathbf{w};P_{0})=0$. We then show that the
mixture of distributions $\\{P_{u}\\}_{\mathcal{U}}$ is close to $P_{0}$
according to the $\chi^{2}$ divergence — Lemma 44.

Recall that the $\chi^{2}$ divergence between $P\ll Q$ (i.e., $P$ is
absolutely continuous with respect to $Q$) is given by

$\chi^{2}(P||Q)\triangleq\mathbb{E}_{Q}\left[\left(\frac{P(Z)}{Q(Z)}-1\right)^{2}\right].$
(43)

In Lemma 44, we design the mixture distribution
$P_{u}\in\mathcal{P}_{1}(\epsilon)$ and show that the mixture is close to a
distribution $P_{0}\in\mathcal{P}_{0}$ according to the $\chi^{2}$ divergence.

###### Lemma 1

[Close Mixture of Distributions] For CVaR fairness metrics
$\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})$ with quality of service function $L$
and measuring the average quality of service using the distribution $P$ such
that $(L,P)\in\\{(L_{EO},P_{EO}),(L_{SP},P_{SP})\\}$. Consider the hypothesis
regions $\mathcal{P}_{0}$ (3) and $\mathcal{P}_{1}(\epsilon)$ (4). Assume that
$\mathbf{w}$ is a uniform distribution over all groups, i.e.,
$\mathbf{w}=\left(\frac{1}{|\mathcal{G}|},...,\frac{1}{|\mathcal{G}|}\right)$,
For all $\alpha\in[0,1)$ and
$\frac{\alpha|\mathcal{G}|^{1/3}}{4}\geq\epsilon>0$ there exist a sequence of
distributions $P_{0}\in\mathcal{P}_{0}$ and
$\\{P_{u}\\}_{u\in\mathcal{U}}\subset\mathcal{P}_{1}(\epsilon)$ indexed by
elements of the set $\mathcal{U}$ such that if $u\sim\pi$ we have that

${\chi}^{2}\left(\mathbb{E}_{u}\left[P_{u}^{n}\right]\biggl{|}\biggl{|}P_{0}^{n}\right)\leq
e^{\frac{128(1-\alpha)n^{2}\epsilon^{4}}{\alpha^{4}|\mathcal{G}|}}-1.$ (44)

We prove this result in Appendix D. In Lemma 44, we showed that there exists a
mixture of distributions with CVaR fairness greater than $\epsilon$ that is
close to a distribution $P_{0}$ with CVaR fairness equal to $0$. Hence, we can
use the generalized Le Cam Lemma to compute the minimum number of samples that
is necessary to perform an $\epsilon$-test reliably. In Theorem 45 we show
that it is necessary to have
$n=\Omega\left(\frac{\sqrt{|\mathcal{G}|}}{(1-\alpha)^{1/2}\epsilon^{2}}\right)$
samples to perform an $\epsilon$-test reliably.

###### Theorem 3

[Minimum Sample Complexity] For CVaR fairness metrics
$\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})$ with quality of service function $L$
and measuring the average quality of service using the distribution $P$ such
that $(L,P)\in\\{(L_{EO},P_{EO}),(L_{SP},P_{SP})\\}$. Consider the hypothesis
regions $\mathcal{P}_{0}$ (3) and $\mathcal{P}_{1}(\epsilon)$ (4). Assume that
$\mathbf{w}$ is a uniform distribution over all groups, i.e.,
$\mathbf{w}=\left(\frac{1}{|\mathcal{G}|},...,\frac{1}{|\mathcal{G}|}\right)$.
For all $\alpha\in[0,1)$, $\frac{\alpha|\mathcal{G}|^{1/3}}{4}\geq\epsilon>0$
, it is necessary to have $n$ i.i.d. samples from $P$ to distinguish between
$\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})=0$ and
$\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})\geq\epsilon$ with probability of error
smaller than $0.01$, where $n$ is such that

$n=\Omega\left(\frac{\alpha^{2}\sqrt{|\mathcal{G}|}}{(1-\alpha)^{1/2}\epsilon^{2}}\right).$
(45)

We prove this result in Appendix D. In Theorem 45, we showed that the order of
the sample complexity of the Algorithm 1 is optimal when using weighted
sampling and $\mathbf{w}$ is uniform. The results in Lemma 44 and Theorem 45
were given in terms of the equal opportunity fairness metric. However, our
result can be trivially extended to several fairness metrics, such as
statistical parity and equalized odds.

We highlight that the result in Theorem 45 together with Corollary 1 give an
operational meaning for the Rényi entropy of order $2/3$ as the log of the
number of samples that is necessary to perform an $\epsilon$-test for CVaR
reliably.

##  VII Conclusion

This paper proposes a multi-group fairness metric called conditional value-at-
risk Fairness (CVaR fairness) inspired by conditional value-at-risk in
finance. In fair machine learning, we are interested in testing if a given
fairness metric is greater than a fixed threshold or equal to zero. We show
that the usual multi-group fairness metrics (we call it max-gap fairness) have
a high sample complexity, making testing for multi-group fairness infeasible.
This motivates CVaR fairness, a metric that allows practitioners to relax
fairness guarantees to decrease the sample complexity for reliably testing for
multi-group fairness. We prove that it is possible to recover max-gap fairness
from CVaR fairness by controlling one parameter in CVaR fairness. Next, we
propose algorithms that test if the CVaR fairness is bigger than a threshold
or equal to zero. We show that the proposed algorithms can reliably perform
the hypothesis test with a more favorable sample complexity using an i.i.d.
sample strategy (weighted sampling), improving the previous sample complexity
in at least a square root factor. Moreover, we provided a non-i.i.d. sampling
strategy (attribute specific sampling) that, paired with our proposed
algorithm, can test for CVaR fairness with a test dataset size independent of
the number of groups. Finally, we also provided a converse result on testing
for CVaR fairness using weighted sampling, showing that the order of the
sample complexity of the proposed algorithm is optimal under some assumptions.
Our results show that by using CVaR fairness and the proposed algorithms, ML
practitioners can reliably test for multi-group fairness by trading off
fairness guarantees for a more favorable sample complexity.

We hope that future work explores the empirical implications of our testing
proposal to demonstrate the trade-off between sample complexity and fairness
guarantees from CVaR fairness. Additionally, by shifting from max-gap fairness
to CVaR fairness, we are able to gradually improve sample complexity but this
could come at the cost of possibly overlooking performance gaps for uniquely
rare and unsampled groups. While we believe this should be rare in practice
and our framework is tunable, it would be valuable for future work to
empirically examine this on multiple real-world use cases. Moreover, our
results only hold for binary group-specific losses, i.e., $L\in\\{0,1\\}$.
Hence, developing theoretical guarantees for multi-group fairness notions with
non-binary $L$, such as multicalibration is another direction for future
investigation.

##  VIII Acknowledgetments

Authors thank Flavien Prost (Google Research) and Alexandru Tifrea (ETHZ) for
helpful comments and discussions on an earlier version of this paper.

## References

  * [1] P. K. Roy, S. S. Chowdhary, and R. Bhatia, “A machine learning approach for automation of resume recommendation system,” _Procedia Computer Science_ , vol. 167, pp. 2318–2327, 2020.
  * [2] J. Zhou, W. Li, J. Wang, S. Ding, and C. Xia, “Default prediction in p2p lending from high-dimensional data based on machine learning,” _Physica A: Statistical Mechanics and its Applications_ , vol. 534, 2019.
  * [3] L. Brotcke, “Time to assess bias in machine learning models for credit decisions,” _Journal of Risk and Financial Management_ , vol. 15, 2022.
  * [4] T. Wang, C. Rudin, D. Wagner, and R. Sevieri, “Learning to detect patterns of crime,” in _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_ , 2013, pp. 515––530.
  * [5] D. Csillag, L. Monteiro Paes, T. Ramos, J. Romano, R. Oliveira, R. Seixas, and P. Orenstein, “Amnioml: Amniotic fluid segmentation and volume prediction with uncertainty quantification,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2023, pp. 15 494–15 502.
  * [6] E. Dritsas and M. Trigka, “Stroke risk prediction with machine learning techniques,” _Sensors_ , vol. 22, 2021.
  * [7] “Civil rights act of 1964,” in _Enrolled Acts and Resolutions of Congress_ , General Records of the United States Government. U.S. Government Publishing Office, 1964.
  * [8] S. Lo Piano, “Ethical principles in machine learning and artificial intelligence: cases from the field and possible ways forward,” _Humanities and Social Sciences Communications_ , vol. 7, 2020.
  * [9] M. Hort, Z. Chen, J. M. Zhang, F. Sarro, and M. Harman, “Bias mitigation for machine learning classifiers: A comprehensive survey,” _arXiv preprint arXiv:2207.07068_ , 2022.
  * [10] A. Lowy, S. Baharlouei, R. Pavan, M. Razaviyayn, and A. Beirami, “A stochastic optimization framework for fair risk minimization,” _Transactions on Machine Learning Research_ , 2022, expert Certification. [Online]. Available: https://openreview.net/forum?id=P9Cj6RJmN2
  * [11] W. Alghamdi, H. Hsu, H. Jeong, H. Wang, P. Winston Michalak, S. Asoodeh, and F. Calmon, “Beyond adult and COMPAS: Fair multi-class prediction via information projection,” in _Advances in Neural Information Processing Systems_ , A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, Eds., 2022. [Online]. Available: https://openreview.net/forum?id=0e0es11XAIM
  * [12] S. Baharlouei, M. Nouiehed, A. Beirami, and M. Razaviyayn, “Rényi fair inference,” in _International Conference on Learning Representations_ , 2019.
  * [13] M. Hardt, E. Price, and N. Srebro, “Equality of opportunity in supervised learning,” _Advances in neural information processing systems_ , vol. 29, 2016.
  * [14] A. Agarwal, A. Beygelzimer, M. Dudík, J. Langford, and H. Wallach, “A reductions approach to fair classification,” in _Proceedings of the 35th International Conference on Machine Learning_ , 2018.
  * [15] F. Calmon, D. Wei, B. Vinzamuri, K. Natesan Ramamurthy, and K. R. Varshney, “Optimized pre-processing for discrimination prevention,” in _Advances in Neural Information Processing Systems_ , I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, Eds., 2017. [Online]. Available: https://proceedings.neurips.cc/paper_files/paper/2017/file/9a49a25d845a483fae4be7e341368e36-Paper.pdf
  * [16] R. Zemel, Y. Wu, K. Swersky, T. Pitassi, and C. Dwork, “Learning fair representations,” in _Proceedings of the 30th International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, S. Dasgupta and D. McAllester, Eds., vol. 28, no. 3. Atlanta, Georgia, USA: PMLR, 17–19 Jun 2013, pp. 325–333. [Online]. Available: https://proceedings.mlr.press/v28/zemel13.html
  * [17] N. Mehrabi, F. Morstatter, N. Saxena, K. Lerman, and A. Galstyan, “A survey on bias and fairness in machine learning,” _ACM computing surveys (CSUR)_ , vol. 54, no. 6, pp. 1–35, 2021.
  * [18] F. Kamiran, T. Calders, and M. Pechenizkiy, “Discrimination aware decision tree learning,” in _2010 IEEE International Conference on Data Mining_ , 2010, pp. 869–874.
  * [19] C. Dwork, M. Hardt, T. Pitassi, O. Reingold, and R. Zemel, “Fairness through awareness,” in _Proceedings of the 3rd Innovations in Theoretical Computer Science Conference_. ACM, 2012, pp. 214–226.
  * [20] R. Zemel, Y. Wu, K. Swersky, T. Pitassi, and C. Dwork, “Learning fair representations,” in _International conference on machine learning_. PMLR, 2013, pp. 325–333.
  * [21] M. Kearns, S. Neel, A. Roth, and Z. S. Wu, “Preventing fairness gerrymandering: Auditing and learning for subgroup fairness,” in _International Conference on Machine Learning_. PMLR, 2018, pp. 2564–2572.
  * [22] U. Hebert-Johnson, M. Kim, O. Reingold, and G. Rothblum, “Multicalibration: Calibration for the (Computationally-identifiable) masses,” in _Proceedings of the 35th International Conference on Machine Learning_ , 2018, pp. 1939–1948.
  * [23] A. Wang, V. V. Ramaswamy, and O. Russakovsky, “Towards Intersectionality in Machine Learning: Including More Identities, Handling Underrepresentation, and Performing Evaluation,” _ACM Conference on Fairness, Accountability, and Transparency (FAccT)_ , 2022.
  * [24] J. R. Foulds, R. Islam, K. N. Keya, and S. Pan, “An intersectional definition of fairness,” in _2020 IEEE 36th International Conference on Data Engineering (ICDE)_. IEEE, 2020, pp. 1918–1921.
  * [25] Y. Kong, “Are “Intersectionally Fair” AI Algorithms Really Fair to Women of Color? A Philosophical Analysis,” in _2022 ACM Conference on Fairness, Accountability, and Transparency_ , 2022, pp. 485–494.
  * [26] L. Monteiro Paes, C. Long, B. Ustun, and F. Calmon, “On the epistemic limits of personalized prediction,” in _Advances in Neural Information Processing Systems_ , 2022, pp. 1979–1991.
  * [27] R. T. Rockafellar, S. Uryasev _et al._ , “Optimization of conditional value-at-risk,” _Journal of risk_ , vol. 2, pp. 21–42, 2000.
  * [28] B. Hooks, _Ain’t I a woman: Black women and feminism_. South End Press, 1992.
  * [29] M. Kearns, S. Neel, A. Roth, and Z. S. Wu, “An empirical study of rich subgroup fairness for machine learning,” in _Proceedings of the Conference on Fairness, Accountability, and Transparency_ , ser. FAT* ’19. New York, NY, USA: Association for Computing Machinery, 2019, p. 100–109. [Online]. Available: https://doi.org/10.1145/3287560.3287592
  * [30] E. Lett and W. G. La Cava, “Translating intersectionality to fair machine learning in health sciences,” _Nature Machine Intelligence_ , vol. 5, pp. 476––479, 2023.
  * [31] T. Hashimoto, M. Srivastava, H. Namkoong, and P. Liang, “Fairness without demographics in repeated loss minimization,” in _International Conference on Machine Learning_. PMLR, 2018, pp. 1929–1938.
  * [32] C. L. Canonne, “A survey on distribution testing: Your data is big. but is it blue?” _Theory of Computing_ , pp. 1–100, 2020.
  * [33] G. Pleiss, M. Raghavan, F. Wu, J. Kleinberg, and K. Q. Weinberger, “On fairness and calibration,” in _Advances in Neural Information Processing Systems 30_ , 2017.
  * [34] P. Tchébychef, “Des valeurs moyennes (traduction du russe, n. de khanikof.” _Journal de Mathématiques Pures et Appliquées_ , pp. 177–184, 1867.
  * [35] E. Hellinger, “Neue begründung der theorie quadratischer formen von unendlichvielen veränderlichen.” _Journal für die reine und angewandte Mathematik_ , pp. 210–271, 1909.
  * [36] R. Williamson and A. Menon, “Fairness risk measures,” in _International Conference on Machine Learning_. PMLR, 2019, pp. 6786–6797.
  * [37] M. Falahatgar, A. Jafarpour, A. Orlitsky, V. Pichapati, and A. Theertha Suresh, “Faster algorithms for testing under conditional sampling,” in _Proceedings of The 28th Conference on Learning Theory_ , 2015, pp. 607–636.
  * [38] L. Le Cam, “Convergence of estimates under dimensionality restrictions,” _The Annals of Statistics_ , vol. 1, 1973.
  * [39] Y. Polyanskiy and Y. Wu, “Dualizing le cam’s method for functional estimation, with applications to estimating the unseens,” _arXiv preprint arXiv:1902.05616_ , 2019.
  * [40] Y. Ingster and I. Suslina, _Nonparametric Goodness-of-Fit Testing Under Gaussian Models_. Springer, 01 2003, vol. 169.

##  Appendix A Lower Bounds for Hypothesis Testing for Max-Gap Fairness

This section shows the lower bounds for the hypothesis test using the standard
max-gap fairness metrics in Definition 2. Particularly, we focus on Equal
Opportunity fairness. The results here were discussed in Section III.

Recall that the Hellinger divergence between two distributions $P,Q$ on
$\mathcal{Z}$ is given by

$\displaystyle\textsc{H}^{2}(P||Q)$
$\displaystyle=\sum_{z\in\mathcal{Z}}\left(\sqrt{p(z)}-\sqrt{q(z)}\right)^{2}.$

######  Lemma 2 (Close Distributions)

For max-gap fairness metrics F_MaxGap (e.g., equal opportunity in Example 1
and statistical parity in Example 2) with quality of service function $L$ and
measuring the average quality of service using the distribution $P$ such that
$(L,P)\in\\{(L_{EO},P_{EO}),(L_{SP},P_{SP})\\}$. If $\epsilon\leq 0.5$ there
exists a distribution $P_{0}\in\mathcal{P}_{0}$ and
$P_{1}\in\mathcal{P}_{1}(\epsilon)$ such that:

$\text{H}^{2}(P_{0}||P_{1})\leq
2-2\left(1-\frac{2\epsilon^{2}}{|\mathcal{G}|}\right).$ (46)

###### Proof:

We will prove the desired result for equal opportunity described in Example 1.
The result for other fairness metrics, such as statistical parity in Example
2, and equal odds [13], is analogous. We start by assuming that

$P_{0}(Z|(\hat{Y},Y,G))=P_{0}(X|(\hat{Y},Y,G))=P_{1}(Z|(\hat{Y},Y,G))=P_{1}(X|(\hat{Y},Y,G)),$

i.e., the conditional distribution of $X$ from $P_{0}$ and $P_{1}$ are equal

$P_{0}(X|(\hat{Y},Y,G))=P_{1}(X|(\hat{Y},Y,G)).$ (47)

Now, from (47), we conclude that it is only necessary to bound the Hellinger
divergence for the marginal distributions of $(\hat{Y},Y,G)$, because

$\displaystyle\textsc{H}^{2}(P_{0}||P_{1})$
$\displaystyle=\mathbb{E}_{Q}\left[\left(\sqrt{\frac{P_{1}(Z)}{P_{0}(Z)}}-1\right)^{2}\right]=\mathbb{E}\left[\left(\sqrt{\frac{P_{1}(\hat{Y},Y,G)}{P_{0}(\hat{Y},Y,G)}}-1\right)^{2}\right].$

Next, we compute the divergence of the marginals.

$\displaystyle\ \ \textsc{H}^{2}(P_{0}||P_{1})$ (48)
$\displaystyle=\sum_{\begin{subarray}{c}g\in\mathcal{G}\\\ y\in\\{0,1\\}\\\
\hat{y}\in\\{0,1\\}\end{subarray}}\biggl{(}\sqrt{P_{0}(\hat{Y}=\hat{y},Y=y,G=g)}-\sqrt{P_{1}(\hat{Y}=\hat{y},Y=y,G=g)}\biggl{)}^{2}$
(49) $\displaystyle=\sum_{\begin{subarray}{c}g\in\mathcal{G}\\\
y\in\\{0,1\\}\\\
\hat{y}\in\\{0,1\\}\end{subarray}}\biggl{(}\sqrt{P_{0}(\hat{Y}=\hat{y}\mid
Y=y,G=g)P_{0}(Y=y\mid G=g)P_{0}(G=g)}$
$\displaystyle-\sqrt{P_{1}(\hat{Y}=\hat{y}\mid Y=y,G=g)P_{1}(Y=y\mid
G=g)P_{1}(G=g)}\biggl{)}^{2}$ (50)
$\displaystyle=\sum_{\begin{subarray}{c}g\in\mathcal{G}\\\
\hat{y}\in\\{0,1\\}\end{subarray}}\biggl{(}\sqrt{P_{0}(\hat{Y}=\hat{y}\mid
Y=1,G=g)P_{0}(G=g)}$ $\displaystyle-\sqrt{P_{1}(\hat{Y}=\hat{y}\mid
Y=1,G=g)P_{1}(G=g)}\biggl{)}^{2}$ (51)
$\displaystyle=\sum_{\begin{subarray}{c}g\in\mathcal{G}\\\
\hat{y}\in\\{0,1\\}\end{subarray}}P_{0}(\hat{Y}=\hat{y}\mid
Y=1,G=g)w_{g}+P_{1}(\hat{Y}=\hat{y}\mid Y=1,G=g){w}_{g}$
$\displaystyle-2w_{g}\sqrt{P_{1}(\hat{Y}=\hat{y}\mid
Y=1,G=g)P_{0}(\hat{Y}=\hat{y}\mid Y=1,G=g)}$ (52)
$\displaystyle=2-2\sum_{\begin{subarray}{c}g\in\mathcal{G}\end{subarray}}w_{g}\biggl{(}\sqrt{P_{1}(\hat{Y}=1\mid
Y=1,G=g)P_{0}(\hat{Y}=1\mid Y=1,G=g)}$
$\displaystyle+\sqrt{P_{1}(\hat{Y}=0\mid Y=1,G=g)P_{0}(\hat{Y}=0\mid
Y=1,G=g)}\biggl{)}$ (53)

Now, take $w_{g}=\frac{1}{|\mathcal{G}|}$. Also, let $P_{0}$ and $P_{1}$ be :

$P_{0}(\hat{Y}=\hat{y}\mid Y=1,G=g)=\frac{1}{2}\ \ \forall g\in\mathcal{G}.$
(54) $\displaystyle P_{1}(\hat{Y}$ $\displaystyle=\hat{y}\mid
Y=1,G=g)=\frac{1}{2}\ \ \forall g\in\mathcal{G}\setminus\\{g_{1}\\}.$ (55)
$\displaystyle P_{1}(\hat{Y}$ $\displaystyle=\hat{y}\mid
Y=1,G=g_{1})=\frac{1}{2}+\epsilon\frac{|\mathcal{G}|}{|\mathcal{G}|-1}.$ (56)

Note that $P_{0}\in\mathcal{P}_{0}$ and $P_{1}\in\mathcal{P}_{1}(\epsilon)$.

Therefore, by plug in the distributions in (54) and (56) in the equality from
(53), we have that

$\displaystyle\textsc{H}^{2}(P_{0}||P_{1})$
$\displaystyle=2-2\biggl{(}1+\frac{1}{|\mathcal{G}|}\biggl{(}\sqrt{\frac{1}{2}\left(\frac{1}{2}+\frac{|\mathcal{G}|}{|\mathcal{G}|-1}\epsilon\right)}+\sqrt{\frac{1}{2}\left(\frac{1}{2}-\frac{|\mathcal{G}|}{|\mathcal{G}|-1}\epsilon\right)}-1\biggl{)}\biggl{)}$
$\displaystyle\leq
2-2\biggl{(}1+\frac{1}{|\mathcal{G}|}\biggl{(}\sqrt{\frac{1}{2}\left(\frac{1}{2}+\epsilon\right)}+\sqrt{\frac{1}{2}\left(\frac{1}{2}-\epsilon\right)}-1\biggl{)}\biggl{)}$
$\displaystyle\leq 2-2\left(1-\frac{2\epsilon^{2}}{|\mathcal{G}|}\right),$

which completes the proof. ∎

Recall that the total variation divergence $\textsc{TV}(.||.)$ takes a pair of
distributions $P$ and $Q$ and returns

$\textsc{TV}(P||Q)\triangleq\frac{1}{2}\sum_{z\in\mathcal{Z}}\left|P(z)-Q(z)\right|.$
(57)

See 1

###### Proof:

We will prove the desired result for equal opportunity described in Example 1.
The result for other fairness metrics, such as statistical parity in Example
2, and equal odds [13], is analogous.

We start with $n$ samples from two distributions $P_{0}\in\mathcal{P}_{0}$ and
$P_{1}\in\mathcal{P}_{1}(\epsilon)$. Recall that the probability of error is
given by

$P_{\text{error}}(\psi)=\frac{1}{2}(P_{0}(\psi=1)+P_{1}(\psi=0)).$ (58)

Therefore, by choosing the best decision function $\psi$, by the Le Cam lemma
[38], and the fact that for all distributions $P$ and $Q$

$\textsc{TV}(P||Q)\leq\textsc{H}(P||Q),$

we conclude that

$\displaystyle\inf_{\psi}2P_{\text{error}}(\psi)$
$\displaystyle=1-\textsc{TV}(P_{0}^{n}||P_{1}^{n})$ $\displaystyle\geq
1-\sqrt{\textsc{H}^{2}(P_{0}^{n}||P_{1}^{n})}$ $\displaystyle\geq
1-\biggl{(}2\left(1-\left(1-\frac{1}{2}\textsc{H}^{2}(P_{0}||P_{1})\right)^{n}\right)\biggl{)}^{1/2}$

From Lemma 46 we have that there exists $P_{0}\in\mathcal{P}_{0}$ and
$P_{1}\in\mathcal{P}_{1}(\epsilon)$ such that

$\text{H}^{2}(P_{0}||P_{1})\leq
2-2\left(1-\frac{2\epsilon^{2}}{|\mathcal{G}|}\right),$ (59)

and $\mathbf{w}$ uniform.

Taking the $P_{0}\in\mathcal{P}_{0}$ and $P_{1}\in\mathcal{P}_{1}(\epsilon)$
from Lemma 46, we have that

$\displaystyle\inf_{\psi}2P_{\text{error}}(\psi)$ $\displaystyle\geq
1-\biggl{(}2\left(1-\left(1-\frac{1}{2}\textsc{H}^{2}(P_{0}||P_{1})\right)^{n}\right)\biggl{)}^{1/2}$
$\displaystyle\geq
1-\biggl{(}2\left(1-\left(1-\frac{2\epsilon^{2}}{|\mathcal{G}|}\right)^{n}\right)\biggl{)}^{1/2}$
(60)

We now provide the lower bound on sample complexity. We start to
differentiating between the distributions $P_{0}\in\mathcal{P}_{0}$ and
$P_{1}\in\mathcal{P}_{1}(\epsilon)$ from Lemma 46. We want to ensure that

$\delta\geq\inf_{\psi}P_{e}(\psi).$ (61)

Next, we compute how large $n$ needs to be to ensure that (60) holds.

$\displaystyle 2\delta\geq
1-\biggl{(}2\left(1-\left(1-\frac{2\epsilon^{2}}{|\mathcal{G}|}\right)^{n}\right)\biggl{)}^{1/2}$
(62) $\displaystyle\Rightarrow
1-\frac{(1-2\delta)^{2}}{2}\geq\left(1-\frac{2\epsilon^{2}}{|\mathcal{G}|}\right)^{n}$
(63)
$\displaystyle\Rightarrow\ln{\left(1-\frac{(1-2\delta)^{2}}{2}\right)}\geq
n\ln\left(1-\frac{2\epsilon^{2}}{|\mathcal{G}|}\right)$ (64)
$\displaystyle\Rightarrow\ln{\left(1-\frac{(1-2\delta)^{2}}{2}\right)}\geq
n\frac{-2\epsilon^{2}}{-2\epsilon^{2}+|\mathcal{G}|}$ (65)
$\displaystyle\Rightarrow
n\geq\ln{\left(1-\frac{(1-2\delta)^{2}}{2}\right)}\frac{-2\epsilon^{2}+|\mathcal{G}|}{-2\epsilon^{2}}$
(66) $\displaystyle\Rightarrow
n=\Omega\left(\frac{|\mathcal{G}|}{\epsilon^{2}}\right)$ (67)

Hence, we have the desired result. ∎

##  Appendix B Properties of CVaR Fairness

In this section, we prove the properties from CVaR fairness discussed in
Section IV.

######  Lemma 3 (F_MaxGap is bounded)

For all distributions $P$ with support on $\mathcal{Z}$, if
$L:\mathcal{Z}\rightarrow\\{0,1\\}$ then

$0\leq\texttt{F\\_MaxGap}(P,L,\overline{L}(\mathbf{w}))\leq 1.$ (68)

###### Proof:

Recall that

$\displaystyle\Delta(g)$
$\displaystyle=\left|\mathbb{E}_{P}[L(Z)|G=g]-\overline{L}(\mathbf{w})\right|$
(69)
$\displaystyle=\left|\mathbb{E}_{P}[L(Z)|G=g]-\sum_{g\in\mathcal{G}}w_{g}\mathbb{E}_{P}[L(Z)|G=g]\right|.$
(70)

Where $\overline{L}(\mathbf{w})\in[0,1]$ and
$\mathbb{E}_{P}[L(Z)|G=g]\in[0,1]$. Therefore,

$\displaystyle\Delta(g)\leq 1\Rightarrow\texttt{F\\_MaxGap}=\max_{g}\Delta(g)$
$\displaystyle\leq 1.$ (71)

∎

See 3

###### Proof:

From the definition of CVaR fairness we know that:

$\displaystyle\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})$
$\displaystyle=\frac{1}{(1-\alpha)}\max_{\sum_{g\in
Q\subset\mathcal{G}}w_{g}\leq(1-\alpha)}\sum_{g\in Q}w_{g}\Delta(g)\geq 0$

because from the definition of $\Delta(g)$, $\Delta(g)\geq 0$ for all
$g\in\mathcal{G}$ and $w_{g}\geq 0$ for all $g\in\mathcal{G}$.

Moreover, we have that:

$\displaystyle\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})$
$\displaystyle=\frac{1}{(1-\alpha)}\max_{\sum_{g\in
Q\subset\mathcal{G}}w_{g}\leq(1-\alpha)}\sum_{g\in Q}w_{g}\Delta(g)$
$\displaystyle\leq\frac{1}{(1-\alpha)}\max_{\sum_{g\in
Q\subset\mathcal{G}}}\sum_{g\in Q}w_{g}\max_{g\in\mathcal{G}}\Delta(g)$
$\displaystyle=\max_{g\in\mathcal{G}}\Delta(g)\max_{\sum_{g\in
Q\subset\mathcal{G}}}\frac{1}{(1-\alpha)}\sum_{g\in Q}w_{g}$
$\displaystyle\leq\max_{g\in\mathcal{G}}\Delta(g)$
$\displaystyle=\texttt{F\\_MaxGap}(P,L,\overline{L}(\mathbf{w})).$

∎

See 2

###### Proof:

From proposition 33, we already know that

$\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})\leq\texttt{F\\_MaxGap}(L,\overline{L}(\mathbf{w})).$

However, by taking $\alpha=1-w_{g^{*}}$, the set $Q=\\{w_{g^{*}}\\}$ for some
$g^{*}\in\arg\max_{g}\Delta(g)$ achieves the maximum

$\displaystyle\frac{1}{(1-\alpha)}\sum_{g\in Q}w_{g}\Delta(g)$
$\displaystyle=\frac{1}{w_{g^{*}}}w_{g^{*}}\Delta(g^{*})$
$\displaystyle=\Delta(g^{*})$
$\displaystyle=\texttt{F\\_MaxGap}(L,\overline{L}(\mathbf{w})).$

Moreover, $\sum_{g\in Q\subset\mathcal{G}}w_{g}=w_{g^{*}}\leq
w_{g^{*}}=1-\alpha$. Hence, the desired result follows from the fact that $Q$
achieves the maximum because

$\displaystyle\texttt{F\\_MaxGap}(L,\overline{L}(\mathbf{w}))$
$\displaystyle=\frac{1}{(1-\alpha)}\sum_{g\in Q}w_{g}\Delta(g)$ (72)
$\displaystyle\leq\frac{1}{(1-\alpha)}\max_{\sum_{g\in
Q\subset\mathcal{G}}w_{g}\leq(1-\alpha)}\sum_{g\in Q}w_{g}\Delta(g)$ (73)
$\displaystyle=\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})\leq\texttt{F\\_MaxGap}(L,\overline{L}(\mathbf{w})).$
(74)

Note that if
$\mathbf{w}=\left(\frac{1}{|\mathcal{G}|},...,\frac{1}{|\mathcal{G}|}\right)$,
then $\alpha=1-w_{g^{*}}=1-\frac{1}{|\mathcal{G}|}$.

∎

##  Appendix C Upper Bound for CVaR Testing

This section proves the results in Section V-C.

###### Lemma 4

Under weighted sampling, if $nv_{g}\leq 1$ and $n\geq 2$,

$\Pr(M_{{g}}\geq 1)\geq nv_{g}/e,$

and

$\Pr(M_{{g}}\geq 2)\geq n^{2}v^{2}_{g}/4e.$

###### Proof:

Since $nv_{g}\leq 1$,

$\Pr(M_{{s}}\geq 1)\geq\Pr(M_{{s}}=1)=nv_{g}(1-v_{g})^{n-1}\geq nv_{g}/e,$

Similarly $nv_{g}\leq 1$,

$\Pr(M_{{s}}\geq 2)\geq\Pr(M_{{s}}=2)=n(n-1)/2(v_{g})^{2}(1-v_{g})^{n-2}\geq
n^{2}v^{2}_{s}/4e,$

where the last inequality follows from $n\geq 2$. ∎

######  Lemma 5 (Computing Average of First Order Estimation)

Define $\frac{\sum_{i=1}^{M_{g}}{L}(z_{i})}{M_{g}}=0$ if $M_{g}=0$ and recall
that $z=(x,g,y)$. If $L:\mathcal{Z}\rightarrow\\{0,1\\}$, then

$\mathbb{E}\left[\frac{\sum_{i=1}^{M_{g}}{L}(z_{i})}{M_{g}}\right]=\mathbb{E}[{L}(z)\mid
G=g]\Pr(M_{g}\geq 1)$ (75)

###### Proof:

By the conditional law of expectation,

$\displaystyle\mathbb{E}\left[\frac{\sum_{i=1}^{M_{g}}{L}(z_{i})}{M_{{g}}}\right]$
$\displaystyle=\mathbb{E}\left[\left.\mathbb{E}\left[\frac{\sum_{i=1}^{M_{g}}{L}(z_{i})}{M_{{g}}}\right|M_{{g}}=m_{g}\right]\right].$

If $m_{{g}}=0$, by definition,

$\left.\mathbb{E}\left[\frac{\sum_{i=1}^{M_{g}}{L}(z_{i})}{M_{{g}}}\right|M_{{g}}=m_{{g}}\right]=0.$
(76)

If $m_{{g}}\geq 1$, then

$\displaystyle\mathbb{E}\left[\left.\frac{\sum_{i=1}^{M_{g}}{L}(z_{i})}{M_{{g}}}\right|M_{{g}}=m_{{g}}\right]=$
$\displaystyle\sum_{i=1}^{m_{g}}\frac{\mathbb{E}\left[\left.{L}(z_{i})\right|M_{{g}}=m_{{g}}\right]}{m_{{g}}}$
(77) $\displaystyle=$
$\displaystyle\sum_{i=1}^{m_{g}}\frac{\mathbb{E}\left[\left.{L}(z)\right|G=g\right]}{m_{{g}}}$
(78) $\displaystyle=$
$\displaystyle\mathbb{E}\left[\left.{L}(z)\right|G=g\right]$ (79)

Combining the above two equations yields

$\left.\mathbb{E}\left[\frac{\sum_{i=1}^{M_{g}}{L}(z_{i})}{M_{{g}}}\right|M_{{g}}=m_{g}\right]=\mathbb{E}\left[\left.{L}(z)\right|G=g\right]\mathbb{I}[M_{{g}}\geq
1].$

Taking the expectation on both sides w.r.t. $M_{{g}}$ yields the lemma. ∎

######  Lemma 6 (Computing Variance of First Order Estimation)

Define $\frac{\sum_{i=1}^{M_{g}}{L}(z_{i})}{M_{g}}=0$ for $M_{g}=0$ and recall
that $z=(x,g,y)$. If $L:\mathcal{Z}\rightarrow\\{0,1\\}$, then

$\displaystyle\text{Var}\left[\frac{\sum_{i=1}^{M_{g}}{L}(z_{i})}{M_{g}}\right]\leq
2\Pr(M_{g}\geq 1)$

###### Proof:

By the law of total variance,

$\displaystyle\text{Var}\left[\frac{\sum_{i=1}^{M_{g}}{L}(z_{i})}{M_{g}}\right]=\mathbb{E}\left[\text{Var}\left[\left.\frac{\sum_{i=1}^{M_{g}}{L}(z_{i})}{M_{g}}\right|M_{{g}}\right]\right]+\text{Var}\left[\left.\mathbb{E}\left[\frac{\sum_{i=1}^{M_{g}}{L}(z_{i})}{M_{g}}\right|M_{{g}}\right]\right].$
(80)

We first compute the second term in the RHS of the above equation (80). By
Lemma 75 we have that:

$\displaystyle\text{Var}\left[\left.\mathbb{E}\left[\frac{\sum_{i=1}^{M_{g}}L(z_{i})}{M_{g}}\frac{\sum_{i=1}^{M_{g}}L(z_{i})-1}{M_{g}-1}\right|M_{{g}}\right]\right]$
$\displaystyle=\text{Var}\left[\mathbb{E}\left[\left.{L}(z)\right|G=g\right]\mathbb{I}[M_{{g}}\geq
1]\right]$ (81)
$\displaystyle=\mathbb{E}\left[\left.{L}(z)\right|G=g\right]^{2}\text{Var}\left[\mathbb{I}[M_{{g}}\geq
1]\right]$ (82)
$\displaystyle\leq\mathbb{E}\left[\left.{L}(z)\right|G=g\right]^{2}\Pr\left(\mathbb{I}[M_{{g}}\geq
1]\right)$ (83) $\displaystyle\leq\Pr\left(\mathbb{I}[M_{{g}}\geq 1]\right)$
(84)

Now, let’s bound the first term in the first term in the RHS of (80). Let’s
star by bounding
$\text{Var}\left[\left.\frac{\sum_{i=1}^{M_{g}}{L}(z_{i})}{M_{g}}\right|M_{{g}}=m_{g}\right]$.

If $m_{g}=0$ then:

$\text{Var}\left[\left.\frac{\sum_{i=1}^{M_{g}}{L}(z_{i})}{M_{g}}\right|M_{{g}}\right]=0$

If $m_{g}\geq 1$, then by Popoviciu’s inequality on variances:

$\displaystyle\text{Var}\left[\left.\frac{\sum_{i=1}^{M_{g}}{L}(z_{i})}{M_{g}}\right|M_{{g}}\right]$
$\displaystyle\leq\frac{1}{4}\Bigg{(}\max_{z_{i}}\left(\frac{\sum_{i=1}^{M_{g}}{L}(z_{i})}{M_{g}}\right)-\min_{z_{i}}\left(\frac{\sum_{i=1}^{M_{g}}{L}(z_{i})}{M_{g}}\right)\Bigg{)}^{2}$
$\displaystyle\leq\frac{1}{4}(0-(-1)1)^{2}=\frac{1}{4}$

By the two last equations, we conclude that:

$\displaystyle\text{Var}\left[\left.\frac{\sum_{i=1}^{M_{g}}{L}(z_{i})}{M_{g}}\right|M_{{g}}=m_{g}\right]\leq\frac{1}{4}\mathbb{I}[m_{{g}}\geq
1]$ (85)

and by taking expectations on both sides:

$\displaystyle\mathbb{E}\left[\text{Var}\left[\left.\frac{\sum_{i=1}^{M_{g}}{L}(z_{i})}{M_{g}}\right|M_{{g}}=m_{g}\right]\right]\leq\frac{1}{4}\Pr(m_{{g}}\geq
1)$ (86)

Combining equation 80, 84, and 86 we conclude that:

$\displaystyle\text{Var}\left[\frac{\sum_{i=1}^{M_{g}}{L}(z_{i})}{M_{g}}\right]\leq\left(1+\frac{1}{4}\right)\Pr(m_{{g}}\geq
1)\leq 2\Pr(m_{{g}}\geq 1)$ (87)

∎

######  Lemma 7 (Computing Average of Second Order Estimation)

Define
$\frac{\sum_{i=1}^{M_{g}}L(z_{i})}{M_{g}}\frac{\sum_{i=1}^{M_{g}}L(z_{i})-1}{M_{g}-1}=0$
if $M_{g}=0,1$, and recall that $z=(x,g,y)$. If
$L:\mathcal{Z}\rightarrow\\{0,1\\}$, then

$\displaystyle\mathbb{E}\left[\frac{\sum_{i=1}^{M_{g}}L(z_{i})}{M_{g}}\frac{\sum_{i=1}^{M_{g}}L(z_{i})-1}{M_{g}-1}\right]=$
$\displaystyle\mathbb{E}[L(z)\mid G=g]^{2}\Pr(M_{g}\geq 2)$

###### Proof:

By the conditional law of expectation,

$\displaystyle\mathbb{E}\left[\frac{\sum_{i=1}^{M_{g}}L(z_{i})}{M_{g}}\frac{\sum_{i=1}^{M_{g}}L(z_{i})-1}{M_{g}-1}\right]=$
$\displaystyle\mathbb{E}\left[\mathbb{E}\left[\left.\frac{\sum_{i=1}^{M_{g}}L(z_{i})}{M_{g}}\frac{\sum_{i=1}^{M_{g}}L(z_{i})-1}{M_{g}-1}\right|M_{g}=m_{g}\right]\right]$
(88)

If $m_{g}\in\\{0,1\\}$ then:

$\mathbb{E}\left[\left.\frac{\sum_{i=1}^{M_{g}}L(z_{i})}{M_{g}}\frac{\sum_{i=1}^{M_{g}}L(z_{i})-1}{M_{g}-1}\right|M_{g}=m_{g}\right]=0$
(90)

If $m_{g}\geq 2$ then:

$\displaystyle\mathbb{E}\left[\left.\frac{\sum_{i=1}^{M_{g}}L(z_{i})}{M_{g}}\frac{\sum_{i=1}^{M_{g}}L(z_{i})-1}{M_{g}-1}\right|M_{g}=m_{g}\right]$
(91) $\displaystyle=$
$\displaystyle\mathbb{E}\left[\left.\frac{\sum_{i=1}^{m_{g}}L(z_{i})}{m_{g}}\frac{\sum_{i=1}^{m_{g}}L(z_{i})-1}{m_{g}-1}\right|M_{g}=m_{g}\right]$
(92) $\displaystyle=$
$\displaystyle\mathbb{E}\left[\left.\frac{\left(\sum_{i=1}^{m_{g}}L(z_{i})\right)^{2}-\sum_{i=1}^{m_{g}}L(z_{i})}{m_{g}(m_{g}-1)}\right|M_{g}=m_{g}\right]$
(93) $\displaystyle=$
$\displaystyle\mathbb{E}\left[\left.\frac{\sum_{i=1}^{m_{g}}L(z_{i})^{2}+\sum_{i\neq
j}L(z_{i})L(z_{j})-\sum_{i=1}^{m_{g}}L(z_{i})}{m_{g}(m_{g}-1)}\right|M_{g}=m_{g}\right]$
(94) $\displaystyle=$
$\displaystyle\frac{m_{g}\mathbb{E}\left[L(z)^{2}-L(z)|G=g\right]+m_{g}(m_{g}-1)\mathbb{E}\left[L(z)|G=g\right]^{2}}{m_{g}(m_{g}-1)}$
(95) $\displaystyle=$ $\displaystyle\mathbb{E}\left[L(z)|G=g\right]^{2},$ (96)

where the last inequality comes from the fact that
$\mathbb{E}\left[L(z)^{2}-L(z)|G=g\right]=0$ because $L(z)\in\\{0,1\\}$
therefore $L(z)^{2}-L(z)=0$ for all $z$.

Combining (90) and (96) yields

$\displaystyle\mathbb{E}\left[\left.\frac{\sum_{i=1}^{M_{g}}L(z_{i})}{M_{g}}\frac{\sum_{i=1}^{M_{g}}L(z_{i})-1}{M_{g}-1}\right|M_{g}=m_{g}\right]=$
$\displaystyle\mathbb{E}\left[L(z)|G=g\right]^{2}\mathbb{I}[M_{{g}}\geq 2].$
(97)

Taking the expectation on both sides w.r.t. $M_{{g}}$ give us the lemma. ∎

######  Lemma 8 (Computing Variance of Second Order Estimation)

Define
$\frac{\sum_{i=1}^{M_{g}}L(z_{i})}{M_{g}}\frac{\sum_{i=1}^{M_{g}}L(z_{i})-1}{M_{g}-1}=0$
if $M_{g}=0,1$, and recall that $z=(x,g,y)$. If
$L:\mathcal{Z}\rightarrow\\{0,1\\}$, then

$\displaystyle\text{Var}\left[\frac{\sum_{i=1}^{M_{g}}L(z_{i})}{M_{g}}\frac{\sum_{i=1}^{M_{g}}L(z_{i})-1}{M_{g}-1}\right]\leq$
$\displaystyle 2\Pr(M_{g}\geq 2)$

###### Proof:

By the law of total variance,

$\displaystyle\text{Var}\left[\frac{\sum_{i=1}^{M_{g}}L(z_{i})}{M_{g}}\frac{\sum_{i=1}^{M_{g}}L(z_{i})-1}{M_{g}-1}\right]$
$\displaystyle=\mathbb{E}\left[\text{Var}\left[\left.\frac{\sum_{i=1}^{M_{g}}L(z_{i})}{M_{g}}\frac{\sum_{i=1}^{M_{g}}L(z_{i})-1}{M_{g}-1}\right|M_{{g}}\right]\right]$
$\displaystyle+\text{Var}\left[\left.\mathbb{E}\left[\frac{\sum_{i=1}^{M_{g}}L(z_{i})}{M_{g}}\frac{\sum_{i=1}^{M_{g}}L(z_{i})-1}{M_{g}-1}\right|M_{{g}}\right]\right].$
(98)

We first compute the second term in the RHS of the above equation (98). By
Lemma 7 we have that:

$\displaystyle\text{Var}\left[\left.\mathbb{E}\left[\frac{\sum_{i=1}^{M_{g}}L(z_{i})}{M_{g}}\frac{\sum_{i=1}^{M_{g}}L(z_{i})-1}{M_{g}-1}\right|M_{{g}}\right]\right]$
$\displaystyle=\text{Var}\Bigg{[}\Bigg{(}\frac{\mathbb{E}\left[L(z)^{2}-L(z)|G=g\right]}{(m_{g}-1)}+\mathbb{E}\left[L(z)|G=g\right]^{2}\Bigg{)}\mathbb{I}[m_{{g}}\geq
2]\Bigg{]}$ (99)

Note that $\mathbb{E}\left[L(z)^{2}-L(z)|G=g\right]=0$.

Now, we can bound Eq. 99 by

$\displaystyle=\text{Var}\Bigg{[}\Bigg{(}\frac{\mathbb{E}\left[L(z)^{2}-L(z)|G=g\right]}{(m_{g}-1)}+\mathbb{E}\left[L(z)|G=g\right]^{2}\Bigg{)}\mathbb{I}[m_{{g}}\geq
2]\Bigg{]}$
$\displaystyle=\text{Var}\left[\left(\mathbb{E}\left[L(z)|G=g\right]^{2}\right)\mathbb{I}[m_{{g}}\geq
2]\right]$ (100)
$\displaystyle=\mathbb{E}\left[\left(\mathbb{E}\left[L(z)|G=g\right]^{2}\right)^{2}\mathbb{I}[m_{{g}}\geq
2]\right]-\mathbb{E}\left[\left(\mathbb{E}\left[L(z)|G=g\right]^{2}\right)\mathbb{I}[m_{{g}}\geq
2]\right]^{2}$ (101)
$\displaystyle\leq\mathbb{E}\left[\left(\mathbb{E}\left[L(z)|G=g\right]^{2}\right)^{2}\mathbb{I}[m_{{g}}\geq
2]\right]$ (102)
$\displaystyle\leq\left|\left|\left(\mathbb{E}\left[L(z)|G=g\right]^{2}\right)^{2}\right|\right|_{\infty}\mathbb{E}\left[\mathbb{I}[m_{{g}}\geq
2]\right]$ $\displaystyle\leq\Pr(m_{{g}}\geq 2)$ (103)

Where the last inequality comes from the fact that $L\in\\{0,1\\}$.

Now, let’s bound the first term in the first term in the RHS of (98). Let’s
star by bounding
$\text{Var}\left[\left.\frac{\sum_{i=1}^{M_{g}}L(z_{i})}{M_{g}}\frac{\sum_{i=1}^{M_{g}}L(z_{i})-1}{M_{g}-1}\right|M_{{g}}=m_{g}\right]$.

If $m_{g}\in\\{0,1\\}$ then:

$\text{Var}\left[\left.\frac{\sum_{i=1}^{M_{g}}L(z_{i})}{M_{g}}\frac{\sum_{i=1}^{M_{g}}L(z_{i})-1}{M_{g}-1}\right|M_{{g}}=m_{g}\right]=0$

If $m_{g}\geq 2$ then, by Popoviciu’s inequality on variances:

$\displaystyle\text{Var}\left[\left.\frac{\sum_{i=1}^{M_{g}}L(z_{i})}{M_{g}}\frac{\sum_{i=1}^{M_{g}}L(z_{i})-1}{M_{g}-1}\right|M_{{g}}=m_{g}\right]$
$\displaystyle\leq\frac{1}{4}\Bigg{(}\max_{z_{i}}\left(\frac{\sum_{i=1}^{M_{g}}L(z_{i})}{M_{g}}\frac{\sum_{i=1}^{M_{g}}L(z_{i})-1}{M_{g}-1}\right)$
$\displaystyle-\min_{z_{i}}\left(\frac{\sum_{i=1}^{M_{g}}L(z_{i})}{M_{g}}\frac{\sum_{i=1}^{M_{g}}L(z_{i})-1}{M_{g}-1}\right)\Bigg{)}^{2}$
$\displaystyle\leq\frac{1}{4}(1-0)^{2}=\frac{1}{4}$

By the two last equations, we conclude that:

$\displaystyle\text{Var}\left[\left.\frac{\sum_{i=1}^{M_{g}}L(z_{i})}{M_{g}}\frac{\sum_{i=1}^{M_{g}}L(z_{i})-1}{M_{g}-1}\right|M_{{g}}=m_{g}\right]\leq\frac{1}{4}\mathbb{I}[m_{{g}}\geq
2]$ (104)

By taking averages on both sides, we get:

$\displaystyle\mathbb{E}\left[\text{Var}\left[\left.\frac{\sum_{i=1}^{M_{g}}L(z_{i})}{M_{g}}\frac{\sum_{i=1}^{M_{g}}L(z_{i})-1}{M_{g}-1}\right|M_{{g}}\right]\right]\leq\frac{1}{4}\Pr(M_{{g}}\geq
2).$ (105)

Bounding the RHS of (98) by using the result in (103) and (105) we conclude
that

$\displaystyle\text{Var}\left[\frac{\sum_{i=1}^{M_{g}}L(z_{i})}{M_{g}}\frac{\sum_{i=1}^{M_{g}}L(z_{i})-1}{M_{g}-1}\right]$
$\displaystyle\leq\frac{5}{4}\Pr(M_{{g}}\geq 2)$ (106) $\displaystyle\leq
2\Pr(M_{{g}}\geq 2).$ (107)

∎

###### Lemma 9

Denote $E_{g}=\mathbb{E}\left[L(z)|G=g\right]$, if
$L:\mathcal{Z}\rightarrow\\{0,1\\}$, then

$\displaystyle\sum_{s\in\mathcal{S}}w_{g}E_{g}^{2}-\overline{L}(\mathbf{w})^{2}\geq(1-\alpha)(\texttt{F\\_CVaR}_{\alpha}(w))^{2}.$
(108)

###### Proof:

The proof follows from algebraic manipulation as follows.

$\displaystyle(1-\alpha)\left(\texttt{F\\_CVaR}_{\alpha}(w)\right)^{2}+\overline{L}(\mathbf{w})^{2}=$
$\displaystyle(1-\alpha)\left(\max_{\sum w_{g}\leq
1-\alpha}\sum\frac{w_{g}}{(1-\alpha)}\Delta(g)\right)^{2}+\overline{L}(\mathbf{w})^{2}$
(109) $\displaystyle\leq$ $\displaystyle(1-\alpha)\left(\sum_{g\in
Q_{\alpha}}\frac{\sqrt{w_{g}}}{\sqrt{(1-\alpha)}}\frac{\sqrt{w_{g}}\Delta(g)}{\sqrt{(1-\alpha)}}\right)^{2}+\overline{L}(\mathbf{w})^{2}$
$\displaystyle\leq$ $\displaystyle(1-\alpha)\left(\sum_{g\in
Q_{\alpha}}\frac{w_{g}}{{(1-\alpha)}}\right)\left(\sum_{g\in
Q_{\alpha}}\frac{{w_{g}}\Delta(g)^{2}}{{(1-\alpha)}}\right)+\overline{L}(\mathbf{w})^{2}$
(110) $\displaystyle\leq$ $\displaystyle\sum_{g\in
Q_{\alpha}}{{w_{g}}\Delta(g)^{2}}+\overline{L}(\mathbf{w})^{2}$
$\displaystyle=$ $\displaystyle\sum_{g\in
Q_{\alpha}}{{w_{g}}(E_{g}-\overline{L}(\mathbf{w}))^{2}}+\overline{L}(\mathbf{w})^{2}$
$\displaystyle\leq$
$\displaystyle\sum_{g\in\mathcal{G}}{{w_{g}}(E_{g}-\overline{L}(\mathbf{w}))^{2}}+\overline{L}(\mathbf{w})^{2}$
$\displaystyle=$
$\displaystyle\sum_{g\in\mathcal{G}}{w_{g}}E_{g}^{2}-2\overline{L}(\mathbf{w})\left(\sum_{g\in\mathcal{G}}{w_{g}}E_{g}-\overline{L}(\mathbf{w})\right)$
$\displaystyle=$ $\displaystyle\sum_{g\in\mathcal{G}}{w_{g}}E_{g}^{2},$

where the inequality in 110 follows by invoking Cauchy-Schwartz inequality. ∎

###### Lemma 10

If $L:\mathcal{Z}\rightarrow\\{0,1\\}$ is the quality of service function and
${L}$ be the avrage quality of service, then

(a) If $\texttt{F\\_CVaR}_{\alpha}(w,\alpha)=0$, then

$\Pr\left(\widehat{F}>(1-\alpha)\epsilon^{2}/2\right)\leq\sum_{g}\frac{64w_{g}^{2}}{(1-\alpha)^{2}\epsilon^{4}P\left[M_{{g}}\geq
2\right]}+\frac{128}{(1-\alpha)^{2}\epsilon^{4}}\sum_{g}\frac{w^{2}_{g}}{P\left[M_{{g}}\geq
1\right]}.$

Similarly,

(b) if $\texttt{F\\_CVaR}_{\alpha}(w,\alpha)\geq\epsilon$, then

$\Pr\left(\widehat{F}<(1-\alpha)\epsilon^{2}/2\right)\leq\sum_{g}\frac{64w_{g}^{2}}{(1-\alpha)^{2}\epsilon^{4}P\left[M_{{g}}\geq
2\right]}+\frac{128}{(1-\alpha)^{2}\epsilon^{4}}\sum_{g}\frac{w^{2}_{g}}{P\left[M_{{g}}\geq
1\right]}.$

###### Proof:

Denote $E_{g}=\mathbb{E}\left[L(z)|G=g\right]$.

Recall that the estimator is given by

$\displaystyle\widehat{F}$
$\displaystyle=\sum_{{g}\in\mathcal{G}}\frac{w_{g}}{P\left[M_{{s}}\geq
2\right]}\frac{\sum_{i=1}^{M_{g}}L(z_{i})}{M_{g}}\frac{(\sum_{i=1}^{M_{g}}L(z_{i})-1)}{M_{g}-1}-\left(\sum_{{g}\in\mathcal{G}}\frac{w_{g}}{P\left[M_{{s}}\geq
1\right]}\frac{\sum_{j=1}^{M_{g}}{L}(z_{j})}{M_{{g}}}\right)^{2}$ (111)

We first show the result under the null hypothesis.

$\displaystyle\Pr(\widehat{F}>(1-\alpha)\epsilon^{2}/2)$ (112)
$\displaystyle=\Pr\left(\widehat{F}-\left(\sum_{g\in\mathcal{G}}w_{g}E_{g}^{2}-\overline{L}(\mathbf{w})^{2}\right)>(1-\alpha)\epsilon^{2}/2\right)$
(113)
$\displaystyle\leq\Pr\Bigg{(}\sum_{{g}\in\mathcal{G}}\frac{w_{g}\sum_{i=1}^{M_{g}}L(z_{i})(\sum_{i=1}^{M_{g}}L(z_{i})-1)}{P\left[M_{{s}}\geq
2\right]M_{g}(M_{g}-1)}-\sum_{g\in\mathcal{G}}w_{g}E_{g}^{2}>\frac{(1-\alpha)\epsilon^{2}}{4}\Bigg{)}$
$\displaystyle+\Pr\left(\overline{L}(\mathbf{w})^{2}-\left(\sum_{{g}\in\mathcal{G}}\frac{w_{g}}{P\left[M_{{s}}\geq
1\right]}\frac{\sum_{j=1}^{M_{g}}{L}(z_{j})}{M_{{g}}}\right)^{2}>\frac{(1-\alpha)\epsilon^{2}}{4}\right)$
(114)
$\displaystyle\leq\Pr\Bigg{(}\sum_{{g}\in\mathcal{G}}\frac{w_{g}\sum_{i=1}^{M_{g}}L(z_{i})(\sum_{i=1}^{M_{g}}L(z_{i})-1)}{P\left[M_{{s}}\geq
2\right]M_{g}(M_{g}-1)}-\sum_{g\in\mathcal{G}}w_{g}E_{g}^{2}>\frac{(1-\alpha)\epsilon^{2}}{4}\Bigg{)}$
$\displaystyle+\Pr\left(\left(\sum_{{g}\in\mathcal{G}}\frac{w_{g}}{P\left[M_{{s}}\geq
1\right]}\frac{\sum_{j=1}^{M_{g}}{L}(z_{j})}{M_{{g}}}\right)<\overline{L}(\mathbf{w})-\frac{(1-\alpha)\epsilon^{2}}{8}\right),$
(115)

where the last inequality follows by observing that $a^{2}-b^{2}>c$ implies
$b<a^{2}-c<a-c/2a<a-c/2$ for $a<1$ — here is where we use $L\in\\{0,1\\}$.

Next, we bound each of the terms on the right-hand side of the above equation
using Chebyshev’s inequality.

First, define $\widehat{E}_{1}$ such that:

$\widehat{E}_{1}=\sum_{{g}\in\mathcal{G}}\frac{w_{g}\sum_{i=1}^{M_{g}}L(z_{i})(\sum_{i=1}^{M_{g}}L(z_{i})-1)}{P\left[M_{{s}}\geq
2\right]M_{g}(M_{g}-1)}-\sum_{g\in\mathcal{G}}w_{g}E_{g}^{2}$ (116)

By Lemma 7,

$\mathbb{E}[\widehat{E}_{1}]=0,$

and by Lemma 8

$\displaystyle\text{Var}(\widehat{E}_{1})$
$\displaystyle\leq\sum_{g}\frac{4w_{g}^{2}}{P\left[M_{{s}}\geq 2\right]}.$

Hence by Chebyshev’s inequality,

$\displaystyle\Pr\left(\widehat{E}_{1}>(1-\alpha)\epsilon^{2}/4\right)$
$\displaystyle\leq\Pr\left(\widehat{E}_{1}-\mathbb{E}[\widehat{E}_{1}]>(1-\alpha)\epsilon^{2}/4\right)$
(117)
$\displaystyle\leq\Pr\left(\left|\widehat{E}_{1}-\mathbb{E}[\widehat{E}_{1}]\right|>(1-\alpha)\epsilon^{2}/4\right)$
(118)
$\displaystyle\leq\sum_{g}\frac{64w_{g}^{2}}{(1-\alpha)^{2}\epsilon^{4}P\left[M_{{g}}\geq
2\right]}$ (119)

Additionally, denote $\widehat{E}_{2}$ by:

$\widehat{E}_{2}=\sum_{{g}\in\mathcal{G}}\frac{w_{g}}{P\left[M_{{g}}\geq
1\right]}\frac{\sum_{j=1}^{M_{g}}{L}(z_{j})}{M_{{g}}}-\overline{L}(\mathbf{w})$
(120)

Similar to the previous argument, we conclude that:

$\mathbb{E}[\widehat{E}_{2}]=0,$

and by Lemma 6

$\displaystyle\text{Var}(\widehat{E}_{1})$
$\displaystyle\leq\sum_{g}\frac{2w_{g}^{2}}{P\left[M_{{g}}\geq 1\right]}.$

Hence, by applying Chebyshev’s inequality,

$\displaystyle\Pr\left(\widehat{E}_{2}<-(1-\alpha)\epsilon^{2}/8\right)=$
$\displaystyle\Pr\left(\mathbb{E}[\widehat{E}_{2}]-\widehat{E}_{2}>(1-\alpha)\epsilon^{2}/8\right)$
$\displaystyle\leq$
$\displaystyle\Pr\left(\left|\mathbb{E}[\widehat{E}_{2}]-\widehat{E}_{2}\right|>(1-\alpha)\epsilon^{2}/8\right)$
$\displaystyle\leq$
$\displaystyle\frac{128}{(1-\alpha)^{2}\epsilon^{4}}\sum_{g}\frac{w^{2}_{g}}{P\left[M_{{g}}\geq
1\right]}$

Hence,

$\displaystyle\Pr(\widehat{F}>(1-\alpha)\epsilon^{2}/2)$
$\displaystyle\leq\sum_{g}\frac{64w_{g}^{2}}{(1-\alpha)^{2}\epsilon^{4}P\left[M_{{g}}\geq
2\right]}+\frac{128}{(1-\alpha)^{2}\epsilon^{4}}\sum_{g}\frac{w^{2}_{g}}{P\left[M_{{g}}\geq
1\right]},$

completing the proof.

Next, we show the result under the hypothesis $\text{H}_{1}$, i.e., when
$\texttt{F\\_CVaR}_{\alpha}\geq\epsilon$. We are interested in bounding:

$\displaystyle\Pr(\widehat{F}<(1-\alpha)\epsilon^{2}/2)$ (121)

From Lemma 9, we have that

$\displaystyle\Pr(\widehat{F}<(1-\alpha)\epsilon^{2}/2)$
$\displaystyle\leq\Pr\left(\widehat{F}-\left(\sum_{g\in\mathcal{G}}w_{g}E_{g}^{2}-\overline{L}(\mathbf{w})^{2}\right)<-(1-\alpha)\epsilon^{2}+(1-\alpha)\epsilon^{2}/2\right)$
$\displaystyle\leq\Pr\left(\widehat{F}-\left(\sum_{g\in\mathcal{G}}w_{g}E_{g}^{2}-\overline{L}(\mathbf{w})^{2}\right)<-(1-\alpha)\epsilon^{2}/2\right)$
$\displaystyle\leq\Pr\left(-\widehat{F}+\left(\sum_{g\in\mathcal{G}}w_{g}E_{g}^{2}-\overline{L}(\mathbf{w})^{2}\right)>(1-\alpha)\epsilon^{2}/2\right)$
(122)

Using the bound in (122), and the same procedure we used in for bounding the
probability of error when $\texttt{F\\_CVaR}_{\alpha}=0$, we can show that
under $\texttt{F\\_CVaR}_{\alpha}\geq\epsilon$

$\displaystyle\Pr(\widehat{F}>(1-\alpha)\epsilon^{2}/2)$
$\displaystyle\leq\sum_{g}\frac{64w_{g}^{2}}{(1-\alpha)^{2}\epsilon^{4}P\left[M_{{g}}\geq
2\right]}+\frac{128}{(1-\alpha)^{2}\epsilon^{4}}\sum_{g}\frac{w^{2}_{g}}{P\left[M_{{g}}\geq
1\right]},$

∎

See 1

###### Proof:

Using Algorithm 1, we have that:

$\displaystyle P_{\text{error}}$
$\displaystyle=\Pr\left(\left.\widehat{F}\geq\frac{\alpha\epsilon^{2}}{2}\right|\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})=0\right)\Pr\left(\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})=0\right)$
(123)
$\displaystyle+\Pr\left(\left.\widehat{F}<\frac{\alpha\epsilon^{2}}{2}\right|\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})\geq\epsilon\right)\Pr\left(\texttt{F\\_CVaR}_{\alpha}(\mathbf{w})\geq\epsilon\right)$
(124)

then, by Lemma 10, we can bound the RHS (124) and conclude that

$\displaystyle
P_{\text{error}}\leq\sum_{g}\frac{64w_{g}^{2}}{(1-\alpha)^{2}\epsilon^{4}P\left[M_{{g}}\geq
2\right]}+\frac{128}{(1-\alpha)^{2}\epsilon^{4}}\sum_{g}\frac{w^{2}_{g}}{P\left[M_{{g}}\geq
1\right]}$ (125)

By using weighted sampling we can lower bound the probabilities
$P\left[M_{{g}}\geq 2\right]$ and $P\left[M_{{g}}\geq 1\right]$ as in Lemma 4.
Using this lower bound, we can upper bound the RHS of (125) and conclude that

$\displaystyle P_{\text{error}}$
$\displaystyle\leq\sum_{g}\frac{64ew_{g}^{2}}{(1-\alpha)^{2}\epsilon^{4}n^{2}(v_{g})^{2}}+\frac{128e}{(1-\alpha)^{2}\epsilon^{4}}\sum_{g}\frac{w^{2}_{g}}{nv_{g}}$
(126)

Hence, we have the desired result

$P_{\text{error}}=O\left(\sum_{g}\frac{w_{g}^{2}}{(1-\alpha)^{2}\epsilon^{4}n^{2}(v_{g})^{2}}+\frac{1}{(1-\alpha)^{2}\epsilon^{4}}\sum_{g}\frac{w^{2}_{g}}{nv_{g}}\right).$
(127)

∎

See 1

###### Proof:

The bound on $n$ for general $\mathbf{v}$ and $\mathbf{w}$ follows from the
error probability in Theorem 1. We now prove the result when $v_{g}\propto
w^{2/3}_{g}$. From Theorem 1 we have that

$\displaystyle P_{\text{error}}$
$\displaystyle\leq\sum_{g}\frac{64ew_{g}^{2}}{(1-\alpha)^{2}\epsilon^{4}n^{2}(v_{g})^{2}}+\frac{128e}{(1-\alpha)^{2}\epsilon^{4}}\sum_{g}\frac{w^{2}_{g}}{nv_{g}}$
(128)
$\displaystyle=64e\frac{\left(\sum_{g}w_{g}^{2/3}\right)^{3}}{(1-\alpha)^{2}\epsilon^{4}n^{2}}+\frac{128e}{(1-\alpha)^{2}\epsilon^{4}}\frac{(\sum_{g}w_{g}^{2/3})\sum_{g}w^{4/3}_{g}}{n}$
(129) $\displaystyle\leq
64e\frac{\left(\sum_{g}w_{g}^{2/3}\right)^{3}}{(1-\alpha)^{2}\epsilon^{4}n^{2}}+\frac{128e}{(1-\alpha)^{2}\epsilon^{4}}\frac{(\sum_{g}w_{g}^{2/3})}{n}$
(130)

only need to ensure that

$\delta\geq
64e\frac{\left(\sum_{g}w_{g}^{2/3}\right)^{3}}{(1-\alpha)^{2}\epsilon^{4}n^{2}}+\frac{128e}{(1-\alpha)^{2}\epsilon^{4}}\frac{(\sum_{g}w_{g}^{2/3})}{n}$
(131)

Therefore, it is only necessary to use $n$ samples to test for CvaR fairness
reliably, where $n$ is such that

$\displaystyle n$
$\displaystyle=O\left(\frac{\left(\sum_{g}w_{g}^{2/3}\right)^{3/2}}{{\delta}\epsilon^{2}(1-\alpha)}+\frac{\left(\sum_{g}w_{g}^{2/3}\right)}{{\delta}\epsilon^{4}(1-\alpha)^{2}}\right)$
(132) $\displaystyle\iff n$
$\displaystyle=O\left(\frac{2^{\frac{3}{2}\log(\sum_{g}w_{g}^{2/3})}}{{\delta}\epsilon^{2}(1-\alpha)}+\frac{2^{\log(\sum_{g}w_{g}^{2/3})}}{{\delta}\epsilon^{4}(1-\alpha)^{2}}\right)$
(133) $\displaystyle\iff n$
$\displaystyle=O\left(\frac{2^{\frac{1}{2}H_{2/3}(w)}}{{\delta}\epsilon^{2}(1-\alpha)}+\frac{2^{\frac{1}{3}H_{2/3}(w)}}{{\delta}\epsilon^{4}(1-\alpha)^{2}}\right)$
(134)

Setting $\delta=0.01$ yields the result.

∎

See 2

###### Proof:

Let $\delta=0.01$. As in the proof of Theorem 1, we have that

$\displaystyle
P_{\text{error}}\leq\sum_{g}\frac{64w_{g}^{2}}{(1-\alpha)^{2}\epsilon^{4}P\left[M_{{g}}\geq
2\right]}+\frac{128}{(1-\alpha)^{2}\epsilon^{4}}\sum_{g}\frac{w^{2}_{g}}{P\left[M_{{g}}\geq
1\right]}$ (135)

Using attribute specific sampling with $\gamma=\frac{n}{2}$ we conclude that
$P\left[M_{{g}}\geq 1\right]=P\left[M_{{g}}\geq 2\right]=\min(1,\gamma
w_{g})$. Therefore, we can bound the probability of error in (135) as:

$\displaystyle P_{\text{error}}$
$\displaystyle\leq\sum_{g}\frac{64w_{g}^{2}}{(1-\alpha)^{2}\epsilon^{4}\min(1,\gamma
w_{g})}+\frac{128}{(1-\alpha)^{2}\epsilon^{4}}\sum_{g}\frac{w^{2}_{g}}{\min(1,\gamma
w_{g})}$ (136)
$\displaystyle=\sum_{g}\frac{128w_{g}}{(1-\alpha)^{2}\epsilon^{4}n}+\frac{256}{(1-\alpha)^{2}\epsilon^{4}}\sum_{g}\frac{w_{g}}{n}$
(137) $\displaystyle\leq\frac{256}{(1-\alpha)^{2}\epsilon^{4}n}$ (138)

Therefore, we conclude that

$P_{\text{error}}=O\left(\frac{1}{\epsilon^{4}(1-\alpha)^{2}n}\right).$ (139)

∎

See 2

###### Proof:

Let $\delta=0.01$. From Theorem 2, we just need to ensure that:

$P_{\text{error}}\leq\frac{256}{(1-\alpha)^{2}\epsilon^{4}n}\leq\delta$ (140)

Therefore,

$\frac{256}{(1-\alpha)^{2}\epsilon^{4}\delta}\leq n$ (141)

Concluding the proof. ∎

##  Appendix D Converse of Testing for CVaR under weighted sampling

See 1

###### Proof:

We will prove the desired result for equal opportunity described in Example 1.
The result for other fairness metrics, such as statistical parity in Example
2, and equal odds [13], is analogous.

Let $\mathbf{w}$ be the uniform distribution over all groups. Note that under
this definition $\mathbf{v}=\mathbf{w}$ for any $\eta$. Let
$Q\subset\mathcal{G}$ be such that
$|Q|=\lfloor(1-\alpha)|\mathcal{G}|\rfloor$. We define the set
$\mathcal{U}(Q)$ to be

$\mathcal{U}(Q)\triangleq\\{-1,1\\}^{|Q|}.$ (142)

$\mathcal{U}(Q)$ is the set of vector with entries equal to $+1$ or $-1$. We
will use $\mathcal{U}(Q)$ to perturb the distributions of groups $g\in Q$.
Denote the group distribution vector
$\mathbf{w}=(w_{1},...,w_{|\mathcal{G}|})$. And define

$\displaystyle P_{0}(G=g)$ $\displaystyle=w_{g},$ (143) $\displaystyle
P_{u}(G=g)$ $\displaystyle=w_{g}\ \ \forall u\in\mathcal{U}(Q).$ (144)

Hence, we define the conditional distribution of $\hat{Y}$ given $G$
accordingly with $P_{0}$ and $P_{u}$ to be

$\displaystyle P_{0}(\hat{Y}=1|G=g,Y=0)$ $\displaystyle=\frac{1}{2}\ \ $
$\displaystyle\ \ \forall g\in\mathcal{G}$ (145) $\displaystyle
P_{u}(\hat{Y}=1|G=g,Y=0)$ $\displaystyle=\frac{1}{2}\ \ $
$\displaystyle\forall g\notin Q$ (146) $\displaystyle
P_{u}(\hat{Y}=1|G=g,Y=0)$
$\displaystyle=\frac{1}{2}+\frac{\tau\epsilon_{g}u_{g}}{w_{g}}$
$\displaystyle\ \ \forall g\in Q.$ (147)

Where $u=(u_{1},...,u_{|Q|})$, $\epsilon_{g}$ is such that

$\epsilon_{g}\triangleq\frac{\epsilon w_{g}^{2/3}}{\left(\sum_{g\in
Q}w_{g}^{2/3}\right)},$ (148)

and $\tau$ is given by

$\tau\triangleq\frac{1-\alpha}{\alpha}.$ (149)

Notice that we need to show that the probability distributions are well
defined. To do so, it is only necessary to ensure that
$\frac{\tau\epsilon_{g}}{w_{g}}\leq\frac{1}{2}$.

$\tau\frac{\epsilon_{g}}{w_{g}}=\tau\frac{\epsilon
w_{g}^{-1/3}}{\left(\sum_{g^{\prime}\in
Q}w^{2/3}_{g^{\prime}}\right)}=\tau\frac{\epsilon|\mathcal{G}|^{1/3}}{\lfloor(1-\alpha)|\mathcal{G}|\rfloor\frac{1}{|\mathcal{G}|^{1/3}}}\leq\tau\frac{2\epsilon}{(1-\alpha)|\mathcal{G}|^{1/3}}\leq\frac{2\epsilon}{\alpha|\mathcal{G}|^{1/3}}\leq\frac{1}{2}.$
(150)

Once we have shown that $P_{0}$ and $P_{u}$ are probability distributions for
all $u\in\mathcal{U}(Q)$, let’s prove that

  1. 1.

$\texttt{F\\_CVaR}_{\alpha}(P_{0},\mathbf{w})=0$

  2. 2.

$\texttt{F\\_CVaR}_{\alpha}(P_{u},\mathbf{w})\geq\epsilon$ for all
$u\in\mathcal{U}(Q)$.

Recall that CVaR fairness is given by

$\texttt{F\\_CVaR}_{\alpha}(P,\mathbf{w})=\frac{1}{1-\alpha}\max_{\sum_{g\in
A\subset\mathcal{G}}w_{g}\leq\alpha}\sum_{g\in A}w_{g}\Delta(P,g),\\\ $ (151)

where $\Delta(g,P)$ is such that

$\Delta(P,g)=\left|P(\hat{Y}=1|G=g,Y=0)-P(\hat{Y}=1|Y=0)\right|.$ (152)

Item 1): Let’s show that $\texttt{F\\_CVaR}_{\alpha}(P_{0},\mathbf{w})=0$.
Note that for all $g\in\mathcal{G}$

$P_{0}(\hat{Y}=1|Y=0)=\sum_{g\in\mathcal{G}}w_{g}P_{0}(\hat{Y}=1|G=g,Y=0)=\frac{1}{2}=P_{0}(\hat{Y}=1|G=g,Y=0),$
(153)

therefore,

$\Delta(P_{0},g)=0\ \ \forall g\in\mathcal{G},$ (154)

concluding that

$\texttt{F\\_CVaR}_{\alpha}(P_{0},\mathbf{w})=\frac{1}{1-\alpha}\max_{\sum_{g\in
A\subset\mathcal{G}}w_{g}\leq\alpha}\sum_{g\in A}w_{g}\Delta(P_{0},g)=0.$
(155)

Item 2): Let’s show that
$\texttt{F\\_CVaR}_{\alpha}(P_{u},\mathbf{w})\geq\epsilon$ for all
$u\in\mathcal{U}(Q)$.

Note that

$P_{u}(\hat{Y}=1|Y=0)=\sum_{g\in\mathcal{G}}w_{g}P_{u}(\hat{Y}=1|G=g,Y=0)=\frac{1}{2}+\sum_{g\in
Q}\tau\epsilon_{g}u_{g}.$ (156)

Hence, we show that $\Delta(P_{u},g^{\prime})$ for $g^{\prime}\in Q$ is

$\Delta(P_{u},g^{\prime})=\tau\left|\frac{\epsilon_{g^{\prime}}u_{g^{\prime}}}{w_{g^{\prime}}}-\sum_{g\in
Q}\epsilon_{g}u_{g}\right|.$ (157)

Hence we can lower bound the CVaR fairness gap using (157).

$\displaystyle\texttt{F\\_CVaR}_{\alpha}(P_{u},\mathbf{w})$
$\displaystyle=\frac{1}{1-\alpha}\max_{\sum_{g\in
A\subset\mathcal{G}}w_{g}\leq 1-\alpha}\sum_{g^{\prime}\in
A}w_{g^{\prime}}\Delta(P_{u},g^{\prime})$ (158)
$\displaystyle\geq\frac{1}{1-\alpha}\sum_{g\in Q}w_{g}\Delta(g)$ (159)
$\displaystyle=\frac{1}{1-\alpha}\sum_{g^{\prime}\in
Q}w_{g^{\prime}}\left|\frac{\epsilon_{g^{\prime}}\tau
u_{g^{\prime}}}{w_{g^{\prime}}}-\sum_{g\in Q}\epsilon_{g}\tau u_{g}\right|$
(160) $\displaystyle=\frac{\tau}{1-\alpha}\sum_{{g^{\prime}}\in
Q}\left|{\epsilon_{g^{\prime}}u_{g^{\prime}}}-w_{g^{\prime}}\sum_{g\in
Q}\epsilon_{g}u_{g}\right|$ (161)
$\displaystyle\geq\frac{\tau}{1-\alpha}\sum_{{g^{\prime}}\in
Q}{|\epsilon_{g^{\prime}}u_{g^{\prime}}|}-w_{g^{\prime}}\left|\sum_{g\in
Q}\epsilon_{g}u_{g}\right|$ (162)
$\displaystyle\geq\frac{\tau}{1-\alpha}\sum_{{g^{\prime}}\in
Q}{\epsilon_{g^{\prime}}}-w_{g^{\prime}}\sum_{g\in Q}\epsilon_{g}|u_{g}|$
(163) $\displaystyle=\frac{\tau}{1-\alpha}\sum_{{g^{\prime}}\in
Q}{\epsilon_{g^{\prime}}}-w_{g^{\prime}}\sum_{g\in Q}\epsilon_{g}$ (164)
$\displaystyle=\frac{\tau}{1-\alpha}\sum_{{g^{\prime}}\in
Q}{\epsilon_{g^{\prime}}}-w_{g^{\prime}}\epsilon$ (165)
$\displaystyle=\frac{\tau}{1-\alpha}\epsilon\left(1-\sum_{{g^{\prime}}\in
Q}w_{g^{\prime}}\right)$ (166)
$\displaystyle\geq\frac{\tau}{1-\alpha}\epsilon\alpha=\epsilon.$ (167)

We then conclude that
$\texttt{F\\_CVaR}_{\alpha}(P_{u},\mathbf{w})\geq\epsilon$ for all
$u\in\mathcal{U}(Q)$ and from item 1 we had that
$\texttt{F\\_CVaR}_{\alpha}(P_{0},\mathbf{w})=0$.

Now, let’s show that, using these distributions, we can make the $\chi^{2}$
distribution be small considering the mixture of distributions. Our main
objective is to upper bound
${\chi}^{2}\left(\mathbb{E}_{u}\left[P_{u}^{n}\right]\biggl{|}\biggl{|}P_{0}^{n}\right)$
by a quantity that (i) goes to zero when the number of samples $n$ increase,
and (ii) increases when the number of groups $|\mathcal{G}|$ increases.

To bound $\chi^{2}$ of a mixture, we will use the Ingster–Suslina method [40].
Hence, we assume that each $u$ is chosen at random from a distribution $\pi$.
The method ensures that

${\chi}^{2}\left(\mathbb{E}_{u}\left[P_{u}^{n}\right]\biggl{|}\biggl{|}P_{0}^{n}\right)=\mathbb{E}_{u,u^{\prime}\sim\pi}\left[\prod_{i=1}^{n}\sum_{z_{i}\in\mathcal{Z}}\frac{P_{u}(z_{i})P_{u^{\prime}}(z_{i})}{P_{0}(z_{i})}\right]-1.$
(168)

Hence, we just need to compute
$\sum_{z_{i}\in\mathcal{Z}}\frac{P_{v}(z_{i})P_{v^{\prime}}(z_{i})}{P=_{0}(z_{i})}$.

$\displaystyle\sum_{z_{i}\in\mathcal{Z}}\frac{P_{u}(z_{i})P_{u^{\prime}}(z_{i})}{P_{0}(z_{i})}$
(169)
$\displaystyle=\sum_{\hat{y},g}\frac{P_{u}(\hat{Y}=\hat{y},G=g|Y=0)P_{u^{\prime}}(\hat{Y}=\hat{y},G=g|Y=0)}{P_{0}(\hat{Y}=\hat{y},G=g|Y=0)}$
(170) $\displaystyle=\sum_{\hat{y},g\in
Q}\frac{P_{u}(\hat{Y}=\hat{y},G=g|Y=1)P_{u^{\prime}}(\hat{Y}=\hat{y},G=g|Y=0)}{P_{0}(\hat{Y}=\hat{y},G=g|Y=0)}$
(171) $\displaystyle+\sum_{\hat{y},g\notin
Q}\frac{P_{u}(\hat{Y}=\hat{y},G=g|Y=0)P_{u^{\prime}}(\hat{Y}=\hat{y},G=g|Y=0)}{P_{0}(\hat{Y}=\hat{y},G=g|Y=0)}$
(172) $\displaystyle=\sum_{g\in Q}\frac{\left(\frac{w_{g}}{2}+\tau
u_{g}\epsilon_{g}\right)\left(\frac{w_{g}}{2}+\tau
u_{g}^{{}^{\prime}}\epsilon_{g}\right)+\left(\frac{w_{g}}{2}-\tau
u_{g}\epsilon_{g}\right)\left(\frac{w_{g}}{2}-\tau
u_{g}^{{}^{\prime}}\epsilon_{g}\right)}{\frac{w_{g}}{2}}+\sum_{g\notin
Q}\frac{2\frac{w_{g}}{2}\frac{w_{g}}{2}}{\frac{w_{g}}{2}}$ (173)
$\displaystyle=\sum_{g\in
Q}\frac{\left(\frac{w_{g}^{2}}{2}+2\tau^{2}\epsilon_{g}^{2}u_{g}u_{g}^{{}^{\prime}}\right)}{\frac{w_{g}}{2}}+\sum_{g\notin
Q}\frac{2\frac{w_{g}}{2}\frac{w_{g}}{2}}{\frac{w_{g}}{2}}$ (174)
$\displaystyle=\sum_{g\in
Q}\frac{4\tau^{2}\epsilon_{g}^{2}u_{g}u_{g}^{{}^{\prime}}}{w_{g}}+\sum_{g\in
Q}{w_{g}}+\sum_{g\notin Q}{w_{g}}{}$ (175) $\displaystyle=\sum_{g\in
Q}\frac{4\tau^{2}\epsilon_{g}^{2}u_{g}u_{g}^{{}^{\prime}}}{w_{g}}+1.$ (176)

Now, using Ingster–Suslina inequality (168) and the bound in (175), we have

$\displaystyle{\chi}^{2}\left(\mathbb{E}_{u}\left[P_{u}^{n}\right]\biggl{|}\biggl{|}P_{0}^{n}\right)$
$\displaystyle=\mathbb{E}_{u,u^{\prime}\sim\pi}\left[\prod_{i=1}^{n}\sum_{z_{i}\in\mathcal{Z}}\frac{P_{u}(z_{i})P_{u^{\prime}}(z_{i})}{P_{0}(z_{i})}\right]-1$
(177) $\displaystyle=\mathbb{E}_{u,u^{\prime}\sim\pi}\left[\left(\sum_{g\in
Q}\frac{4\tau^{2}\epsilon_{g}^{2}u_{g}u_{g}^{{}^{\prime}}}{w_{g}}+1\right)^{n}\right]-1$
(178) $\displaystyle\leq\mathbb{E}_{u,u^{\prime}\sim\pi}\left[e^{n\sum_{g\in
Q}\frac{4\tau^{2}\epsilon_{g}^{2}u_{g}u_{g}^{{}^{\prime}}}{w_{g}}}\right]-1$
(179)
$\displaystyle\leq\mathbb{E}_{u\sim\pi}\mathbb{E}_{u^{\prime}\sim\pi}\left[e^{n\sum_{g\in
Q}\frac{4\tau^{2}\epsilon_{g}^{2}u_{g}u_{g}^{{}^{\prime}}}{w_{g}}}\right]-1.$
(180)

We note that $u$ and $u^{\prime}$ are $1$-subgasian, hence, we can bound (180)
by

$\displaystyle\mathbb{E}_{u\sim\pi}\mathbb{E}_{u^{\prime}\sim\pi}\left[e^{n\sum_{g\in
Q}\frac{4\tau^{2}\epsilon_{g}^{2}u_{g}u_{g}^{{}^{\prime}}}{w_{g}}}\right]-1$
$\displaystyle=\mathbb{E}_{u\sim\pi}\mathbb{E}_{u^{\prime}\sim\pi}\left[\prod_{g\in
Q}e^{n\frac{4\tau^{2}\epsilon_{g}^{2}u_{g}u_{g}^{{}^{\prime}}}{w_{g}}}\right]-1$
(181) $\displaystyle=\mathbb{E}_{u\sim\pi}\prod_{g\in
Q}\mathbb{E}_{u^{\prime}\sim\pi}\left[e^{n\frac{4\tau^{2}\epsilon_{g}^{2}u_{g}u_{g}^{{}^{\prime}}}{w_{g}}}\right]-1$
(182) $\displaystyle\leq\mathbb{E}_{u\sim\pi}\prod_{g\in
Q}\mathbb{E}_{u^{\prime}\sim\pi}\left[e^{n^{2}\frac{16\tau^{4}\epsilon_{g}^{4}u_{g}^{2}}{w_{g}^{2}}}\right]-1$
(183) $\displaystyle\leq\mathbb{E}_{u\sim\pi}\left[e^{n^{2}\sum_{g\in
Q}\frac{16\tau^{4}\epsilon_{g}^{4}u_{g}^{2}}{w_{g}^{2}}}\right]-1$ (184)
$\displaystyle\leq e^{n^{2}\sum_{g\in
Q}\frac{16\tau^{4}\epsilon_{g}^{4}}{w_{g}^{2}}}-1$ (185)

Now, by plugging in $\epsilon_{g}$ (148) in (185) we conclude that

$\displaystyle\mathbb{E}_{u\sim\pi}\mathbb{E}_{u^{\prime}\sim\pi}\left[e^{n\sum_{g\in
Q}\frac{4\tau^{2}\epsilon_{g}^{2}u_{g}u_{g}^{{}^{\prime}}}{w_{g}}}\right]-1$
$\displaystyle\leq e^{n^{2}\sum_{g\in
Q}\frac{16\tau^{4}\epsilon_{g}^{4}}{w_{g}^{2}}}-1\leq
e^{\frac{16\tau^{4}n^{2}\epsilon^{4}}{\left(\sum_{g\in
Q}w_{g}^{2/3}\right)^{3}}}-1$ (186)

But, from the definition of $Q$, i.e., $\sum_{g\in
Q}w_{g}^{2/3}=\lfloor(1-\alpha)|\mathcal{G}|\rfloor\frac{1}{|\mathcal{G}|^{1/3}}\geq\frac{3(1-\alpha)}{8}\sum_{g\in\mathcal{G}}w_{g}^{2/3}$.
Hence, plugging (186) in (186) we have that

$\displaystyle\mathbb{E}_{u\sim\pi}\mathbb{E}_{u^{\prime}\sim\pi}\left[e^{n\sum_{g\in
Q}\frac{4\tau^{2}\epsilon_{g}^{2}u_{g}u_{g}^{{}^{\prime}}}{w_{g}}}\right]-1$
$\displaystyle\leq e^{n^{2}\sum_{g\in
Q}\frac{16\tau^{4}\epsilon_{g}^{4}}{w_{g}^{2}}}-1\leq
e^{\frac{1024\tau^{4}n^{2}\epsilon^{4}}{\left((1-\alpha)\sum_{g\in\mathcal{G}}w_{g}^{2/3}\right)^{3}}}-1.$
(187)

Concluding the proof of the lemma by combining the inequality in (180) with
(187) and getting

$\displaystyle{\chi}^{2}\left(\mathbb{E}_{u}\left[P_{u}^{n}\right]\biggl{|}\biggl{|}P_{0}^{n}\right)$
$\displaystyle\leq
e^{\frac{1024\tau^{4}n^{2}\epsilon^{4}}{\left((1-\alpha)\sum_{g\in\mathcal{G}}w_{g}^{2/3}\right)^{3}}}-1$
(188) $\displaystyle\leq
e^{\frac{1024(1-\alpha)n^{2}\epsilon^{4}}{\alpha^{4}\left(\sum_{g\in\mathcal{G}}w_{g}^{2/3}\right)^{3}}}-1.$
(189)

∎

See 3

###### Proof:

From Lemma 44 we know that there exist a sequence of distributions
$P_{0}\in\mathcal{P}_{0}(\epsilon)$ and
$\\{P_{u}\\}_{u\in\mathcal{U}}\in\mathcal{P}_{1}(\epsilon)$ indexed by
elements of the set $\mathcal{U}$ such that if $u\sim\pi$ we have that

${\chi}^{2}\left(\mathbb{E}_{u}\left[P_{u}^{n}\right]\biggl{|}\biggl{|}P_{0}^{n}\right)\leq
e^{\frac{1024(1-\alpha)n^{2}\epsilon^{4}}{\alpha^{4}|\mathcal{G}|}}-1.$ (190)

On the other hand, by the generalized Le Cam lemma [39], we have that

$\displaystyle 2\inf_{\psi}P_{\text{error}}$ $\displaystyle\geq
1-\text{TV}\left(\mathbb{E}_{u}\left[P_{u}^{n}\right]\biggl{|}\biggl{|}P_{0}^{n}\right)$
(191) $\displaystyle\geq
1-\frac{1}{2}\sqrt{{\chi}^{2}\left(\mathbb{E}_{u}\left[P_{u}^{n}\right]\biggl{|}\biggl{|}P_{0}^{n}\right)}$
(192)

Plugging (190) in (192), we have that:

$2\inf_{\psi}P_{\text{error}}\geq
1-\frac{1}{2}\sqrt{e^{\frac{1024(1-\alpha)n^{2}\epsilon^{4}}{\alpha^{4}|\mathcal{G}|}}-1}.$
(193)

Therefore, if the probability of error is smaller than $0.01$ we need to
ensure that:

$0.02\geq
1-\frac{1}{2}\sqrt{e^{\frac{1024(1-\alpha)n^{2}\epsilon^{4}}{\alpha^{4}|\mathcal{G}|}}-1}.$
(194)

From where we conclude that

$\displaystyle n$
$\displaystyle=\Omega\left(\frac{\alpha^{2}\sqrt{|\mathcal{G}|}}{(1-\alpha)^{1/2}\epsilon^{2}}\right),$
(195)

which is the desired result. ∎