# Adaptive Sampling for Minimax Fair Classification

Shubhanshu Shekhar
ECE Department, UCSD
<EMAIL_ADDRESS>Mohammad Ghavamzadeh
Google Research
<EMAIL_ADDRESS>Tara Javidi
ECE Department, UCSD
<EMAIL_ADDRESS>
###### Abstract

Machine learning models trained on imbalanced datasets can often end up
adversely affecting inputs belonging to the underrepresented groups. To
address this issue, we consider the problem of adaptively constructing
training sets which allow us to learn classifiers that are fair in a minimax
sense. We first propose an adaptive sampling algorithm based on the principle
of _optimism_ , and derive theoretical bounds on its performance. We then
suitably adapt the techniques developed for the analysis of our proposed
algorithm to derive bounds on the performance of a related $\epsilon$-greedy
strategy recently proposed in the literature. Next, by deriving algorithm
independent lower-bounds for a specific class of problems, we show that the
performance achieved by our adaptive scheme cannot be improved in general. We
then validate the benefits of adaptively constructing training sets via
experiments on synthetic tasks with logistic regression classifiers, as well
as on several real-world tasks using convolutional neural networks.

##  1 Introduction

Machine learning (ML) models are increasingly being applied for automating the
decision-making process in several sensitive applications, such as loan
approval and employment screening. The rationale for using data-driven methods
in these applications is that they remove the possibility of human bias
influencing the decisions. However, recent work has demonstrated that ML
models can often adversely impact members of some protected groups in rather
subtle ways. For instance, in Part I of their paper, Barocas and Selbst,
(2016) explain how discriminatory behaviour might get encoded in the model at
various stages of the ML pipeline, such as data collection, labelling, feature
selection and training. In this paper, we focus on the data-collection stage
of the ML pipeline, and in particular, study the following question: _given a
finite sampling budget, how should a learner construct a ‘balanced’ training
set consisting of elements from different protected groups in appropriate
proportions to ensure that a classifier trained on this dataset achieves equal
predictive error for all the groups?_

Our work is motivated by the following scenario: suppose we have to learn a
common ML model for performing a task (e.g., loan approval) for inputs
belonging to different groups based on protected attributes, such as race or
gender. Depending upon the distribution of input-label pairs from different
groups, the given task may be statistically harder for some groups and easier
for others. Our goal is to ensure that the eventual ML model has equal (or
comparable) predictive accuracy over all groups. One approach for this might
be to train separate classifiers for each group. However, this is often not
possible as the group-membership information may not be available at the
deployment time, or it may be forbidden by law to explicitly use the protected
characteristics as an input in the prediction process (Lipton et al.,, 2017, §
1). Hence to ensure equal accuracy, the training set must have a higher
proportion of samples from the _harder_ groups and fewer from the _easier_
ones. Since the identity of the hard or easy groups are not known apriori, we
consider this problem in an _active setting_ , where a learner has to
incrementally construct a training set by drawing samples one at a time (or a
batch at a time) from different groups. Towards this goal, we propose and
analyze an adaptive sampling scheme based on the principle of _optimism_ ,
used in bandits literature (e.g., Auer et al., 2002), that detects the
_harder_ groups and populates the training set with more samples from such
groups in an adaptive manner. We formally describe the problem in Section 2.

An important design choice for the learner in this problem is the notion used
to quantify _fairness_. The practical meaning of the term fairness is often
context and problem dependent, and hence, formally defining a fairness metric
which works in all cases is a challenging task. As a result, a large number of
fairness measures have been introduced in the literature. Some of the
important ones include demographic parity (Zemel et al.,, 2013), equal odds,
equal opportunity (Hardt et al.,, 2016), individual fairness (Dwork et al.,,
2012), and minimax fairness (Feldman et al.,, 2015). In this paper, we
primarily focus on the notion of minimax fairness in terms of the predictive
loss.

The closest work to ours in the literature is by Abernethy et al., (2020),
where they propose a variant of the $\epsilon$-greedy adaptive sampling
strategy. They present some preliminary theoretical analysis (see Section 4.4
for details) and also empirically demonstrate the benefits of their strategy
over some baselines. In another related work, Anahideh et al., (2020) propose
a fair adaptive sampling strategy which selects points based on a linear
combination of model accuracy and fairness measures, and empirically study its
performance. These results, however, do not characterize the convergence rates
of the excess risk of their respective methods. As one of our contributions,
we employ the tools we develop to analyze our algorithm and perform a thorough
analysis of the excess risk of the $\epsilon$-greedy strategy in Abernethy et
al., (2020) in Section 4.4.

The above results study the problem of fair classification in an active
setting and target the data-collection stage of the ML pipeline. There are
also works that take a passive approach to this problem and focus of the
training phase of the pipeline Agarwal et al., (2018); Martinez et al.,
(2020); Diana et al., (2020). Agarwal et al., (2018) design a scheme for
learning fair binary classifiers with fairness metrics that can be written as
linear constraints involving certain conditional moments. This class of
fairness metrics, however, do not contain the minimax fairness measure studied
in this paper. Diana et al., (2020) propose a method for constructing
(randomized) classifiers for minimax fairness w.r.t. the empirical loss
calculated on the given training set. Similarly, Martinez et al., (2020)
derive an algorithm for learning a pareto optimal minimax fair classifier,
under the assumption that the learner has access to the true expected loss
functions. Thus, the theoretical guarantees in Diana et al., (2020) and
Martinez et al., (2020) hold under the assumption of large training sets. Our
work, in contrast, constructs the training set incrementally (active setting)
from scratch while carefully taking into account the effects of the finite
sample size. Finally, we note that the data-collection strategies proposed in
our paper can, in principle, be combined with the training methods presented
in Diana et al., (2020) and Martinez et al., (2020) to further guarantee the
(minimax) fairness of the resulting classifier. We leave the investigation of
this approach for future work.

Besides data-collection and training, there have been studies in the fair ML
literature on other aspects of the ML pipeline, such as pre-processing (Celis
et al.,, 2020), learning feature representations (Zemel et al.,, 2013) and
post-processing (Hardt et al.,, 2016). We refer the readers to a recent survey
by Caton and Haas, (2020) for more detailed description of these results.

We conclude this section with a summary of the main contributions of our
paper.

  * •

After formally defining the problem in Sec. 2, we propose an optimistic
adaptive sampling strategy, $\mathcal{A}_{\texttt{opt}}$, for training set
construction in Sec. 3.1. Our sampling strategy appropriately adapts the
algorithmic ideas of _optimism under uncertainty_ and _tracking_ from the
multi-armed bandit literature to our problem. We then introduce a heuristic
variant of $\mathcal{A}_{\texttt{opt}}$ which is scaled better and is more
suited to practical ML problems.

  * •

Under certain mild assumptions (described in Sec. 4.1), we prove high
probability upper-bounds on the excess risk of the classifier learned using
the training set generated by our adaptive sampling algorithm,
$\mathcal{A}_{\texttt{opt}}$, in Sec. 4.3.

  * •

In Sec. 4.4, we show that the technical ideas developed for analyzing
$\mathcal{A}_{\texttt{opt}}$ can be used to study the $\epsilon$-greedy
strategy in Abernethy et al., (2020). In particular, we obtain sufficient
conditions on $\epsilon$ under which the excess risk of the $\epsilon$-greedy
strategy converges to zero, and the rate at which this convergence occurs.

  * •

In Sec. 4.5, we demonstrate that the convergence rate achieved by
$\mathcal{A}_{\texttt{opt}}$ and $\epsilon$-greedy (with appropriately
selected $\epsilon$) cannot be improved in general by deriving matching lower-
bounds for a particular class of problems.

  * •

In Sec. 5, we empirically compare the performance of our algorithm with some
baselines on both synthetic and real datasets. The experiments with the
synthetic data serve to validate the performance of the _exact_ version of our
algorithm. For the real datasets, with deep neural network (DNN) classifiers,
we employ our _heuristic_ algorithm and demonstrate the benefits of
constructing balanced datasets for practical classification problems.

##  2 Problem Formulation

We now formally describe our problem setting. Consider a classification
problem with the feature (input) space $\mathcal{X}$, label set $\mathcal{Y}$,
and a protected attribute set $\mathcal{Z}=\\{z_{1},\ldots,z_{m}\\}$. For any
$z\in\mathcal{Z}$, we use $P_{z}(x,y)$ as a shorthand for
$P_{XY|Z=z}\left(X=x,Y=y\mid Z=z\right)$ to denote the feature-label joint
distribution given that the protected feature value is $Z=z$. We also use
$\mathbb{E}_{z}[\cdot]$ as a shorthand for the expectation w.r.t. $P_{z}$. A
(non-randomized) classifier is a mapping $f:\mathcal{X}\mapsto\mathcal{Y}$,
which assigns a label $y\in\mathcal{Y}$ to every feature $x\in\mathcal{X}$.
For a family of classifiers $\mathcal{F}\subset\mathcal{Y}^{\mathcal{X}}$, a
loss function
$\ell:\mathcal{F}\times\mathcal{X}\times\mathcal{Y}\mapsto\mathbb{R}$, and a
mixture distribution over the protected attributes denoted by
$\pi=\\{\pi(z):\sum_{z\in\mathcal{Z}}\pi(z)=1\\}$, we define the _$\pi$
-optimal classifier_ $f_{\pi}$ as

$\displaystyle
f_{\pi}\in\operatorname*{arg\,min}_{f\in\mathcal{F}}\;\overbrace{\sum_{z\in\mathcal{Z}}\pi(z)\;\mathbb{E}_{z}\left[\ell(f,X,Y)\right]}^{:=\mathbb{E}_{\pi}\left[\ell(f,X,Y)\right]}.$
(1)

When the mixture distribution $\pi$ lies on the corners of the simplex
$\Delta_{m}$ (recall that $m=|\mathcal{Z}|$), i.e., $\pi(z)=1$ for a
$z\in\mathcal{Z}$, we use the notation $f_{z}$ instead of $f_{\pi}$. For $\pi$
in the interior of $\Delta_{m}$, it is clear that the resulting expected loss
of $f_{\pi}$ conditioned on $Z=z$, i.e.,
$\mathbb{E}_{z}\left[\ell(f_{\pi},X,Y)\right]$, must be larger than the best
possible classification loss for $P_{XY|Z=z}$. In this paper, we focus on the
goal of finding the most fair mixture distribution $\pi^{*}$ in a minimax
sense, i.e.,

$\displaystyle\pi^{*}\in\operatorname*{arg\,min}_{\pi\in\Delta_{m}}\;\max_{z\in\mathcal{Z}}\;\underbrace{\mathbb{E}_{z}\left[\ell(f_{\pi},X,Y)\right]}_{\coloneqq
L(z,f_{\pi})}.$ (2)

We consider this problem in the _active_ setting where the _learner_ can
request samples from the conditional distributions
$\\{P_{z}=P_{XY|Z=z}:z\in\mathcal{Z}\\}$. Given a sampling budget $n$, a
function class $\mathcal{F}$, and a loss function $\ell$, the learner’s goal
is to allocate these $n$ samples to the $m$ distributions
$\\{P_{z_{i}}\\}_{i=1}^{m}$ in order to construct a training set that can be
used to learn fair classifiers. Informally, this means that the learner should
draw more samples from the distributions of the attributes $z$ that are
_harder_ , and fewer samples from the _easier_ distributions (see Sec. 2.1 for
an illustrative example).

We conclude this section with a formal problem statement.

######  Problem Statement.

Suppose $\mathcal{F}\subset\mathcal{Y}^{\mathcal{X}}$ denotes a family of
classifiers, $\ell$ a loss function, and
$\mathcal{O}:\mathcal{Z}\mapsto\mathcal{X}\times\mathcal{Y}$ an oracle that
takes in an attribute $z\in\mathcal{Z}$ as input and returns a feature-label
pair $(X,Y)\sim P_{z}=P_{XY|Z=z}$. Given a sampling budget $n$, the goal of
the learner is to design an adaptive sampling scheme $\mathcal{A}$ that
comprises a sequence of mappings $(A_{t})_{t=1}^{n}$ with
$A_{t}:(\mathcal{X}\times\mathcal{Y})^{t-1}\mapsto\mathcal{Z}$ to adaptively
query $\mathcal{O}$ and construct a dataset of size $n$. Let
$\pi_{n}\in\Delta_{m}$ denote the resulting empirical mixture distribution
over $\mathcal{Z}$, where $\pi_{n}(z)=N_{z,n}/n$ and $N_{z,n}$ is the number
of times that $\mathcal{A}$ draws a sample from $P_{z}$ in $n$ rounds. Then,
the quality of the resulting dataset is measured by the excess risk, or the
sub-optimality, of the $\pi_{n}$-optimal classifier $f_{\pi_{n}}$, that is
formally defined as

$\displaystyle\mathcal{R}_{n}\left(\mathcal{A}\right)\coloneqq\max_{z\in\mathcal{Z}}\;L\left(z,f_{\pi_{n}}\right)\;-\;\max_{z\in\mathcal{Z}}\;L(z,f_{\pi^{*}})\;.$
(3)

Hence, the goal of the learner is to design a strategy $\mathcal{A}$ which has
a small value of $\mathcal{R}_{n}$.

###  2.1 A Class of Synthetic Models

We introduce a stylized class of synthetic models which we use as a running
example throughout the paper.

######  Definition 1 (SyntheticModel).

Set $\mathcal{X}=\mathbb{R}^{2}$, $\mathcal{Y}=\\{0,1\\}$, and
$\mathcal{Z}=\\{u,v\\}$. Each instance of our synthetic model is defined by
the set of distributions $\\{P_{z}:z\in\mathcal{Z}\\}$, where $P_{XY|Z}$
satisfies the following: $P_{Y|Z}(Y=1|Z=z)=0.5$ for both $z\in\mathcal{Z}$,
and $P_{X|Y=y,Z=z}=\mathcal{N}(\mu_{yz},I_{2})$ for all
$(y,z)\in\mathcal{Y}\times\mathcal{Z}$. Here $I_{2}$ is the $2\times 2$
identity matrix. Thus, each instance of this model can be represented by a
mean vector $\bm{\mu}=(\mu_{yz}:y\in\mathcal{Y},\;z\in\mathcal{Z})$.

The idea behind this class of models is that the ‘hardness’ of the
classification problem for a value of $z\in\mathcal{Z}$ depends on the
distance between $\mu_{0z}$ and $\mu_{1z}$. The more separated these two mean
vectors are, the easier it is to distinguish the labels. Thus, depending on
this distance, it is expected that different protected attributes may require
different fractions of samples in the training set to achieve equal test
accuracy. To illustrate this, we consider two instances of the SyntheticModel:
I. $\mu_{0u}=(-2,2)$, $\mu_{1u}=(2,-2)$, $\mu_{0v}=(-1,-1)$, and
$\mu_{1v}=(1,1)$, and II. $\mu_{0u}=(-1.5,1.5)$, $\mu_{1u}\\!=(1.5,-1.5)$,
$\mu_{0v}=(-2,-2)$, and $\mu_{1v}=(2,2)$.

For both model instances, we trained a logistic regression classifier over
training sets with $1001$ equally spaced values of $\pi(u)$ in $[0,1]$. Figure
1 shows the test accuracy of the learned classifier for both attributes (blue
and red curves) as well as their minimum (black curve) for different values of
$\pi(u)$. Since the pair $(\mu_{0u},\mu_{1u})$ is better separated than
$(\mu_{0v},\mu_{1v})$ in the first instance, it is easier to classify inputs
with $Z=u$ than those with $Z=v$, and thus, it requires fewer training samples
from $P_{z=u}$ than $P_{z=v}$ to achieve the same accuracy. This is reflected
in Figure 1 (left) that shows the best (min-max) performance is achieved at
$\pi(u)\approx 0.23$. An opposite trend is observed in the second instance
(right plot in Figure 1), where the mean vectors corresponding to the
attribute $Z=v$ are better separated, and hence, require fewer training
samples to achieve the same accuracy.

(a) (b)

Figure 1: The figures show the variation of the minimum prediction accuracy
over the two attributes $\mathcal{Z}=\\{u,v\\}$ with $\pi(u)$, for Instance I
(left) and Instance II (right) of the SyntheticModel.

##  3 Adaptive Sampling Schemes

In this section, we present adaptive sampling strategies for the minimax fair
classification problem, formally stated in Section 2. We first describe our
optimistic adaptive sampling algorithm ($\mathcal{A}_{\texttt{opt}}$) in
Section 3.1. The proposed strategy requires retraining a classifier in every
iteration, and hence, it is mainly suitable for smaller scale problems. Then,
in Section 3.2, we propose a heuristic variant of
$\mathcal{A}_{\texttt{opt}}$, which is suitable for large scale ML models.

###  3.1 Optimistic Adaptive Sampling Strategy

We now present an outline of our optimistic adaptive sampling strategy
$\mathcal{A}_{\texttt{opt}}$, whose pseudo-code is presented in Algorithm 1.
We also provide a more detailed and formal pseudo-code for
$\mathcal{A}_{\texttt{opt}}$ in Algorithm 2 in Appendix B.1. The algorithm
proceeds in the following phases:

Phase 1. In the initial phase $t\leq m=|\mathcal{Z}|$, for each
$z\in\mathcal{Z}$, we draw two independent samples from $P_{z}=P_{XY|Z=z}$ and
add one to the dataset $\mathcal{D}_{t}$ and the other one to
$\mathcal{D}_{z}$. The training dataset $\mathcal{D}_{t}$ is used to learn and
update a common (over all values of $z\in\mathcal{Z}$) classifier
$\hat{f}_{t}$ via _empirical risk minimization_ (ERM). The additional
independent datasets $\\{\mathcal{D}_{z_{i}}\\}_{i=1}^{m}$ are used for
estimating the performance of $\hat{f}_{t}$ for each protected attribute
$z\in\mathcal{Z}$.

Phase 2. In each round $t>m$, we choose an attribute $z_{t}$ according to the
following selection rule:

  * •

if there exists an attribute $z$ whose number of samples in $\mathcal{D}_{t}$
is fewer than $\sqrt{t}$ (Line 1), then we set it as $z_{t}$ (Line 1),

  * •

else we set $z_{t}$ as the attribute which has the largest upper confidence
bound (UCB) (described below) for the expected loss of the classifier
$f_{\pi_{t}}$ (Line 1). Here $N_{z_{t},t}$ and $\pi_{t}$ denote the number of
samples from $P_{z_{t}}$ in the dataset $\mathcal{D}_{t}$ and the empirical
mixture distribution (over the attributes $z$) of $\mathcal{D}_{t}$,
respectively.

Phase 3. When the attribute $z_{t}$ is selected in Phase 2, the algorithm
draws a pair of independent samples from $P_{z_{t}}$, add one to
$\mathcal{D}_{t}$ and the other one to $\mathcal{D}_{z_{t}}$, and finally
updates $N_{z_{t},t}$, $\pi_{t}$, and the uniform deviation bound
$e_{z_{t}}(N_{z_{t},t})$ (described below) (Lines 1 to 1). The updated dataset
$\mathcal{D}_{t}$ is then used to learn a new candidate classifier
$\hat{f}_{t}$ (Line 1).

Phases 2 and 3 are repeated until the sampling budget is exhausted, i.e.,
$t=n/2$ (we sample twice at each round).

Calculating UCB. To complete the description of our strategy, we need to
explain how we construct the UCB for $L(z,f_{\pi_{t}})$. We use the following
expression for the UCB:

$\begin{split}U_{t}(z,\hat{f}_{t})&\coloneqq\frac{1}{|\mathcal{D}_{z}|}\sum_{(x,y)\in\mathcal{D}_{z}}\\!\\!\\!\\!\ell(\hat{f}_{t},x,y)\;+\;e_{z}\left(N_{z,t}\right)\\\
&\qquad+\frac{2C}{\pi_{t}(z)}\sum_{z^{\prime}\in\mathcal{Z}}\pi_{t}(z^{\prime})e_{z^{\prime}}(N_{z^{\prime},t})\;.\end{split}$
(4)

The first term on the RHS of (4) is the empirical loss of the classifier
$\hat{f}_{t}$ on the dataset $\mathcal{D}_{z}$ (consisting of $N_{z,t}$
elements). The second term, $e_{z}(N_{z,t})$, which we formally introduce it
in Assumption 4, is a high probability uniform deviation bound between the
empirical and true loss of any function $f\in\mathcal{F}$. Together these two
terms give us an upper-bound on $L(z,\hat{f}_{t})$, i.e., the expected loss of
$\hat{f}_{t}$ conditioned on $Z=z$, defined in (2). Finally, the third term is
an upper-bound on the quantity $|L(z,f_{\pi_{t}})-L(z,\hat{f}_{t})|$, which
when added to the first two terms, gives us the required UCB on
$L(z,f_{\pi_{t}})$. The specific form of the third term is a consequence of
Assumption 3, which we will discuss it in Section 4.

######  Remark 1.

Our formulation of adaptive training set construction for fair classification
resembles the general problem of active learning in multi-armed bandits (ALB)
(e.g., Antos et al., 2008; Carpentier et al., 2011; Shekhar et al., 2020),
where the goal is to allocate samples to learn about $m$ distributions ($m$
protected attributes in our case) uniformly well. Despite the similarity,
there is an important and subtle difference between these two problems. In
ALB, querying an arm (i.e., sampling from a distribution) does not affect the
accuracy of the learner’s estimates of the other arms. This is in contrast to
our problem, where allocating more samples to one attribute may result in a
classifier whose performance degrades on the other attributes (see Appendix
B.4 for a more detailed discussion). Although the similarity allows us to
borrow ideas from the ALB literature, addressing this subtle difference
requires designing new algorithmic ideas and developing novel analysis
techniques, which is one of the main contributions of this paper.

1

Input: $n$ (budget), $\mathcal{F}$ (function class), $\ell$ (loss function),
$C$ (Assumption 3)

2 Initialize: $\;\mathcal{D}_{1}=\emptyset$;
$\;\\{\mathcal{D}_{z_{i}}\\}_{i=1}^{m}=\emptyset$;
$\;\\{N_{z_{i},1}\\}_{i=1}^{m}=0$;

3for  _$\;t=1,\ldots,n/2\;$_ do

/* Select attribute */

4 if  _ $t\leq m$_ then

5 $z_{t}=z_{t}$;

6 else if  _$\;\min_{z\in\mathcal{Z}}\;N_{z,t} <\sqrt{t}\;$ _ then

7 $z_{t}\in\operatorname*{arg\,min}_{z\in\mathcal{Z}}\;N_{z,t}$;

8 else

$z_{t}=\operatorname*{arg\,max}_{z\in\mathcal{Z}}\;U_{t}(z,\hat{f}_{t})$; //
see Eq. 4

9

10 end if

11

/* Collect data */

12 Draw two independent samples from $P_{z_{t}}$;

/* Perform the updates */

13 Add the first one to $\mathcal{D}_{t}$ and the second one to
$\mathcal{D}_{z_{t}}$;

14 Update $N_{z_{t},t}$; $\;\pi_{t}$; $\;e_{z_{t}}(N_{z_{t},t})$;

15 Learn classifier $\hat{f}_{t}$ by ERM using $\mathcal{D}_{t}$;

16 end for

Output: $\pi_{n/2}$ and $\hat{f}_{n/2}$

Algorithm 1 An Optimistic Adaptive Sampling Scheme
($\mathcal{A}_{\texttt{opt}}$) for Minimax Fair Classification.

###  3.2 A Heuristic Adaptive Sampling Strategy

As described in Section 3.1, our optimistic adaptive sampling strategy
$\mathcal{A}_{\texttt{opt}}$ (Algorithm 1) requires re-training the classifier
$\hat{f}_{t}$ in every iteration. While this can be implemented in small
problems, it becomes infeasible for classification problems involving large
models, such as deep neural networks (DNNs). For dealing with such practical
scenarios, we now describe a heuristic variant of Algorithm 1.

The Heuristic variant of Alg. 1 proceeds by repeating the following steps
until the sampling budget is exhausted.

  1. 1.

It begins with an initial phase of length $n_{0}$, in which pairs of samples
are drawn from $\\{P_{z_{i}}\\}_{i=1}^{m}$ according to some fixed mixture
distribution (proportion) $\pi_{0}$ (e.g., uniform). As in
$\mathcal{A}_{\texttt{opt}}$, half of the samples are added to
$\mathcal{D}_{t}$ and the other half to the respective
$\\{\mathcal{D}_{z_{i}}\\}_{i=1}^{m}$. The dataset $\mathcal{D}_{t}$ at the
end of the $n_{0}$ rounds is used to train a classifier $\hat{f}_{n_{0}}$.

  2. 2.

For the rounds $t>n_{0}$, it selects the attribute $z_{t}$ with the largest
value of

$\widetilde{U}_{t}(z,\hat{f}_{t})\coloneqq\frac{1}{|\mathcal{D}_{z}|}\sum_{(x,y)\in\mathcal{D}_{z}}\\!\\!\\!\\!\ell(\hat{f}_{t},x,y)\;+\,\frac{c_{0}}{\sqrt{N_{z,t}}}\;,$

where $c_{0}$ is a free parameter that controls the amount of exploration
undertaken by the sampling scheme.

  3. 3.

It then draws $2k_{0}$ mini-batches of size $b_{0}$ from $P_{z_{t}}$, of which
the first $k_{0}$ are added to $\mathcal{D}_{t}$ and the rest to
$\mathcal{D}_{z_{t}}$.

  4. 4.

It performs $k_{0}$ steps of the stochastic gradient descent (SGD) with the
drawn mini-batches.

The terms $c_{0}$, $k_{0}$, and $b_{0}$ should be chosen appropriately
depending on the specific problem as well as the computational resources. We
describe our choices of these terms for some commonly used classification
problems in Section 5.2.

##  4 Theoretical Analysis

In this section, we derive an upper-bound on the excess risk
$\mathcal{R}_{n}(\mathcal{A}_{\texttt{opt}})$ of the optimistic adaptive
sampling scheme $\mathcal{A}_{\texttt{opt}}$ (Algorithm 1). We begin by
describing the assumptions required for our theoretical analysis in Section
4.1. Then in Section 4.2, we prove that under Assumptions 1 and 2, there
exists an _ideal_ mixture distribution $\pi^{*}$ at which the optimal
classifier optimizes the loss for all attributes. We present and discuss our
bound on the excess of Algorithm 1 in Section 4.3. In Section 4.4, we formally
introduce the $\epsilon$-greedy sampling strategy proposed in Abernethy et
al., (2020) and go beyond their analysis to obtain a bound on its excess risk
using the techniques that we have developed in Section 4.3. Finally, in
Section 4.5, we show that the performance achieved by the our algorithm cannot
in general be improved, by obtaining an algorithm independent lower-bound on
the excess risk for a particular class of problems.

###  4.1 Assumptions

We now state our assumptions on the set of distributions
$\\{P_{z}:z\in\mathcal{Z}\\}$, function class $\mathcal{F}$, and loss function
$\ell$ needed for analysing our proposed adaptive sampling scheme.

######  Assumption 1.

The mapping
$\pi\mapsto\mathbb{E}_{z}\left[\ell\left(f_{\pi},X,Y\right)\right]$ is
continuous for all attributes $z\in\mathcal{Z}$. Furthermore, if
$\pi,\nu\in\Delta_{m}$ are such that $\pi(z)>\nu(z)$ for an attribute
$z\in\mathcal{Z}$, then
$\mathbb{E}_{z}\left[\ell(f_{\pi},X,Y)\right]<\mathbb{E}_{z}\left[\ell(f_{\nu},X,Y)\right]$.

The above assumption indicates that increasing the weight of an attribute $z$
in the mixture distribution must lead to an increase in the performance of the
resulting classifier on the distribution $P_{z}$. This assumption provides a
natural framework for studying the effect of the composition of the training
set on the resulting fairness properties of the learned classifier, which is
our focus in this paper.

######  Assumption 2.

For any two distinct attributes $z,z^{\prime}\in\mathcal{Z}$, we must have
$\mathbb{E}_{z}\left[\ell(f^{*}_{z},X,Y)\right]<\mathbb{E}_{z^{\prime}}\left[\ell(f^{*}_{z},X,Y)\right]$,
for any
$f^{*}_{z}\in\operatorname*{arg\,min}_{f\in\mathcal{F}}\,\mathbb{E}_{z}\left[\ell(f,X,Y)\right]$.

This assumption requires that any optimal classifier corresponding to
distribution $P_{z}$ to have higher loss w.r.t. the distribution
$P_{z^{\prime}}$ of any other attribute $z^{\prime}\in\mathcal{Z}$. While it
may not always hold (e.g., if one attribute is _significantly_ easier to
classify than another), this assumption, together with Assumption 1, ensure
the existence of an optimal mixture distribution $\pi^{*}$ that equalizes the
performance of $f_{\pi^{*}}$ over all attributes (see Proposition 1). In other
words, these two assumptions define a regime where it is possible to achieve
complete parity in the classification performance across all attributes, by
selecting an appropriate mixture $\pi^{*}$.

######  Assumption 3.

There exist positive constants $\epsilon_{0},C>0$ such that for any function
$f\in\mathcal{F}$ and any $\pi\in\Delta_{m}$ with $\pi(z)>0,\;\forall
z\in\mathcal{Z}$, if we have
$\mathbb{E}_{\pi}\left[\ell\left(f,X,Y\right)\right]\leq\mathbb{E}_{\pi}\left[\ell\left(f_{\pi},X,Y\right)\right]+\epsilon$,
for some $0<\epsilon\leq\epsilon_{0}$, then
$\pi(z)\times\lvert\mathbb{E}_{z}\left[\ell\left(f,X,Y\right)\right]-\mathbb{E}_{z}\left[\ell\left(f_{\pi},X,Y\right)\right]\rvert\leq
C\epsilon,\;\forall z\in\mathcal{Z}$.

This assumption requires that whenever for a $f$ and a $\pi$,
$\sum_{z}\pi(z)\big{(}\mathbb{E}_{z}\left[\ell(f,X,Y)\right]-\mathbb{E}_{z}\left[\ell(f_{\pi},X,Y)\right]\big{)}$
is small, the _absolute value_ of the individual components of the sum, i.e.,
$\pi(z)\lvert\mathbb{E}_{z}\left[\ell(f,X,Y)\right]-\mathbb{E}_{z}\left[\ell(f_{\pi},X,Y)\right]\rvert$,
cannot be too large. Note that this does not exclude the chance that
$\lvert\mathbb{E}_{z}\left[\ell(f,X,Y)\right]-\mathbb{E}_{z}\left[\ell(f_{\pi},X,Y)\right]\rvert$
is large; for instance, when $\pi(z)$ is small for some $z$. A sufficient
condition for this assumption to hold is that the mapping $\pi\mapsto f_{\pi}$
is injective, and any other local optimizer is at least $\epsilon_{0}$ sub-
optimal.

######  Assumption 4.

Let $\delta\in[0,1]$ be a confidence parameter. For each $z\in\mathcal{Z}$,
there exists a monotonically non-increasing sequence
$\\{e_{z}\left(N,\mathcal{F},\delta\right):N\geq 1\\}$ with
$\lim_{N\to\infty}e_{z}\left(N,\mathcal{F},\delta\right)=0$, such that the
following event holds with probability at least $1-\delta/2$:

$\displaystyle\Omega=\bigcap_{z\in\mathcal{Z}}\bigcap_{N=1}^{\infty}\Big{\\{}\sup_{f\in\mathcal{F}}\,\big{|}\widehat{L}_{N}(z,f)-L(z,f)\big{|}\leq
e_{z}(N,\mathcal{F},\delta)\Big{\\}},$

where
$\widehat{L}_{N}(z,f)\coloneqq\frac{1}{N}\sum_{i=1}^{N}\ell\big{(}f,X^{(i)}_{z},Y^{(i)}_{z}\big{)},\;\forall
z\in\mathcal{Z}$, with $\big{(}X^{(i)}_{z},Y^{(i)}_{z}\big{)}_{i=1}^{N}$ being
an i.i.d. sequence of input-label pairs drawn from $P_{z}$.

The above assumption is a standard uniform convergence requirement which is
satisfied by many commonly used families of classifiers. In the sequel, we
will drop the $\mathcal{F}$ and $\delta$ dependence of
$e_{z}(N,\mathcal{F},\delta)$ and only refer to these terms as $e_{z}(N)$, for
all $z\in\mathcal{Z}$ and $N\geq 1$.

###  4.2 Existence of Loss Equalizing Mixture Distribution

Before proceeding to the analysis of Algorithm 1, we present a key result
which states that under Assumptions 1 and 2, there exists a unique optimal
mixture distribution $\pi^{*}$ that ensures the loss of all attributes,
$\\{L(z_{i},f_{\pi^{*}})\\}_{i=1}^{m}$, are equal.

######  Proposition 1.

Suppose the conditional distributions $\\{P_{z}:z\in\mathcal{Z}\\}$, the loss
function $\ell$, and the function class $\mathcal{F}$ satisfy Assumptions 1
and 2. Then, there exists a unique $\pi^{*}\in\Delta_{m}$ that achieves the
optimal value for problem (2) and satisfies

$\displaystyle
L(z_{1},f_{\pi^{*}})=L(z_{2},f_{\pi^{*}})=\cdots=L(z_{m},f_{\pi^{*}})\coloneqq
M^{*}.$

We report the proof of this proposition in Appendix A.

###  4.3 Analysis of Algorithm 1

We now proceed to the analysis of our proposed optimistic adaptive sampling
scheme ($\mathcal{A}_{\texttt{opt}}$) and state our main result, which is the
convergence rate of the excess risk of $\mathcal{A}_{\texttt{opt}}$. Then in
Remark 2, we discuss how this general bound can be instantiated to obtain an
explicit dependence on the budget $n$ for several important classifiers.

######  Theorem 1.

Let Assumptions 1-4 hold and
$\pi_{\min}\coloneqq\min_{z\in\mathcal{Z}}\pi^{*}(z)$. Fix any $A$ such that
$\pi_{\min}/2\leq A<\pi_{\min}$. Suppose the query budget $n$ is sufficiently
large, as defined in Eq. 19 in Appendix B.2. Then, with probability
$1-\delta$, the excess risk of Algorithm 1 can be upper-bounded as

$\begin{split}\mathcal{R}_{n}(\mathcal{A}_{\texttt{opt}})&=\max_{z\in\mathcal{Z}}\;L(z,f_{\pi_{n}})-M^{*}\\\
&=\mathcal{O}\Big{(}\frac{|\mathcal{Z}|C}{\pi_{\min}}\;\max_{z\in\mathcal{Z}}\;e_{z}(N_{A})\Big{)},\end{split}$
(5)

where $M^{*}=L(z,f_{\pi^{*}}),\;\forall z\in\mathcal{Z}$ (see Proposition 1),
$N_{A}=n\pi^{2}_{\min}/(2\pi_{\min}-A)$, and $C$ is the parameter introduced
in Assumption 3.

We provide a proof sketch for Theorem 1 at the end of this section and report
its detailed proof in Appendix B.2. The result of Theorem 1 implies the
following asymptotic rate of convergence for the expected excess risk of
$\mathcal{A}_{\texttt{opt}}$.

######  Corollary 1.

Let the sequences $\big{(}e_{z}(N,\mathcal{F},\delta)\big{)}_{N\geq
1},\;\forall z\in\mathcal{Z}$, from Assumption 4 satisfy the condition that
$\lim_{n\to\infty}e_{z}(\sqrt{n},\mathcal{F},1/n)=0$. Then, by setting
$\delta=1/n$ in Theorem 1, we have

$\displaystyle\limsup_{n\to\infty}\;\frac{\mathbb{E}\big{[}\mathcal{R}_{n}(\mathcal{A}_{\texttt{opt}})\big{]}}{\max_{z\in\mathcal{Z}}\;e_{z}(N_{A})}\;=\;\mathcal{O}\Big{(}\frac{|\mathcal{Z}|C}{\pi_{\min}}\Big{)}.$

Since the choice of $A<\pi_{\min}$ is arbitrary, $N_{A}$ can be made
arbitrarily close to $n\pi_{\min}$. Thus, informally, the result of Corollary
1 indicates that the excess risk of $\mathcal{A}_{\texttt{opt}}$ converges to
zero at the same rate as $\max_{z\in\mathcal{Z}}e_{z}(n\pi_{\min})$.

######  Remark 2.

The bound on the excess risk of Algorithm 1 ($\mathcal{A}_{\texttt{opt}}$)
derived in Theorem 1 (Eq. 5) can be instantiated for several commonly used
classifiers (function classes $\mathcal{F}$) to obtain an explicit convergence
rate in $n$. If $\mathcal{F}$ has a finite VC dimension, $d_{VC}$, then we
have $e_{z}(N)=\mathcal{O}\left(\nicefrac{{d_{VC}}}{{\sqrt{N}}}\right)$, which
implies an asymptotic excess risk of
$\mathcal{O}\left(\nicefrac{{d_{VC}|\mathcal{Z}|C}}{{\pi^{1.5}_{\min}\sqrt{n}}}\right)$
for $\mathcal{A}_{\texttt{opt}}$. If $\mathcal{F}$ has a Rademacher complexity
of $\mathcal{O}\left(n^{-\alpha}\right)$, for some $\alpha>0$, then we obtain
an excess risk bound of
$\mathcal{O}\left(\nicefrac{{|\mathcal{Z}|C}}{{\pi^{1+\alpha}_{\min}n^{\alpha}}}\right)$
for $\mathcal{A}_{\texttt{opt}}$. These conditions on $\mathcal{F}$ are
satisfied by several commonly used classifiers, such as linear, SVM, and
multi-layer perceptron.

######  Remark 3 (Knowledge of parameter $C$).

The implementation of Algorithm 1, as described in Section 3, requires the
knowledge of the parameter $C$ (see Eq. 4) introduced in Assumption 3. This is
primarily because we use the abstract expression
$\\{e_{z}(N):z\in\mathcal{Z},\;N\in\mathbb{N}\\}$ in presenting and analyzing
the algorithm. However, knowing $C$ is not strictly necessary to achieve the
same asymptotic convergence rate as in Thm. 1 and Corollary 1. For instance,
if we know a constant $0<\zeta<1$, such that
$1/e_{z}(N)=o(N^{\zeta}),\;\forall z\in\mathcal{Z}$, then we can achieve the
same asymptotic excess risk rate by replacing $\sqrt{N_{z,t}}$ with
$N_{z,t}^{\zeta}$ in Line 1 of Algorithm 1 and removing the $C$ dependent term
from Line 1. For most commonly used function classes $\mathcal{F}$, any choice
of $\zeta>0.5$ should suffice. Further details are in Appendix B.3.

Proof Sketch of Theorem 1. The proof proceeds in several ‘phases’ (see Example
1 in Appendix B.2) by partitioning the interval $[1,n]_{\mathbb{N}}$ into
$[1,t_{0}]_{\mathbb{N}},[t_{0}+1,t_{1}]_{\mathbb{N}},\ldots,[t_{s-1}+1,t_{s}=n]_{\mathbb{N}}$,
for some integer $0<s<|\mathcal{Z}|=m$. Here we use the notation
$[u,v]_{\mathbb{N}}$ to represent $[u,v]\cap\mathbb{N}$. As we describe below,
the end of each phase is marked by the last time an attribute from a certain
non-empty subset of $\mathcal{Z}$ is sampled by the algorithm, and hence, the
total number of phases, $s+1$, is smaller than $m$.

We first note that unless $\pi_{n}=\pi^{*}$, in which case
$\mathcal{R}_{n}(\mathcal{A}_{\texttt{opt}})$ is zero, there must exist
attributes $z$ for which $\pi_{n}(z)>\pi^{*}(z)$. We define $t_{0}$ as the
last round that $\mathcal{A}_{\texttt{opt}}$ samples one such attribute and
denote the corresponding attribute by $z_{0}$. Since $t_{0}<n$, we must have
$\pi_{t_{0}}(z_{0})>\pi_{n}(z_{0})>\pi^{*}(z_{0})$, which due to the
Assumption 1 implies that
$L(z_{0},f_{\pi_{t_{0}}})<L(z_{0},f_{\pi^{*}})=M^{*}$. Using this fact, we can
show that $U_{t_{0}}(z_{0},\hat{f}_{t_{0}})\leq M^{*}+B_{0}$, where $B_{0}$
depends on $\big{(}e_{z}(N_{z,t_{0}})\big{)}_{z\in\mathcal{Z}}$ and
$\pi^{*}(z_{0})$ (see Lemma 1 in Appendix B.2). Next, we observe that since
$N_{z_{0},t_{0}}>n\pi_{\min}$, for $n$ larger than $1/\pi_{\min}^{2}$, $z_{0}$
must have been selected at time $t_{0}$ due to the attribute selection rule in
Line 1 of Algorithm 1. We then use this to show that
$U_{t_{0}}(z,\hat{f}_{t_{0}})\leq U_{t_{0}}(z_{0},\hat{f}_{t_{0}})$ for all
$z\neq z_{0}$, which implies that $L(z,f_{\pi_{t_{0}}})\leq M^{*}+B_{0}$ for
all $z\in\mathcal{Z}$. Thus, at the end of the first phase (i.e., at time
$t_{0}$), the excess risk of $\mathcal{A}_{\texttt{opt}}$ is upper-bounded by
$B_{0}$.

Then, a technical result derived in Lemma 3 (in Appendix B.2) ensures that
there exists a non-empty subset $\mathcal{Z}_{o}^{(1)}$ among the remaining
attributes for which $\pi_{t_{0}}(z)<\pi_{n}(z),\;\forall
z\in\mathcal{Z}_{o}^{(1)}$. We can then define $t_{1}$ as the last time an
attribute from $\mathcal{Z}_{o}^{(1)}$ is queried, and denote it by $z_{1}$.
Similar to the previous case, we can then bound the value of
$\max_{z\in\mathcal{Z}}L(z,f_{\pi_{t_{1}}})$ with $M^{*}+B_{0}+B_{1}$, where
$B_{1}$ depends on $\big{(}e_{z}(N_{z,t_{1}})\big{)}_{z\in\mathcal{Z}}$ and
$\pi^{*}(z_{1})$. We repeat this process $s-1$ more times until the entire
sampling budget is exhausted. The details of combining the above results to
obtain the final statement of Theorem 1 are in Lemma 5 (Appendix B.2). ∎

###  4.4 Analysis of the $\epsilon$-greedy Sampling Strategy

The $\epsilon$-greedy strategy proposed in Abernethy et al., (2020) proceeds
as follows: for any $t\geq 1$, it maintains a candidate classifier
$\hat{f}_{t}$ along with its empirical loss on $m$ validation sets
corresponding to the attributes $z\in\mathcal{Z}$. At each round $t$, the
algorithm selects an attribute $z_{t}$ as follows: with probability
$\epsilon$, $z_{t}$ is drawn from a fixed distribution over $\mathcal{Z}$, and
with probability $1-\epsilon$, it is set to the distribution with the largest
empirical loss. Having chosen $z_{t}$, the algorithm draws a pair of samples
from $P_{z_{t}}$ and updates the training and validation sets, as well as the
classifier $\hat{f}_{t}$. This process is continued until the sampling budget
is exhausted.

Abernethy et al., (2020) present two theoretical results on the performance of
their $\epsilon$-greedy strategy. The first one (Abernethy et al.,, 2020, Thm.
1), is an asymptotic consistency result derived under somewhat restrictive
assumptions: $\mathcal{X}=\mathbb{R}$, $\mathcal{F}$ is the class of threshold
classifiers, and the learner has access to an oracle which returns the exact
loss, $L(z,f_{\pi_{t}})$, for every $\pi_{t}$. In their second result
(Abernethy et al.,, 2020, Thm. 2), they analyze the greedy version (i.e.,
$\epsilon=0$) of the algorithm with $|\mathcal{Z}|=2$, and show that at time
$n$, either the excess risk is of
$\mathcal{O}\big{(}\max_{z\in\mathcal{Z}}\sqrt{\nicefrac{{2d_{VC}\left(\ell\circ\mathcal{F}\right)\log(2/\delta)}}{{N_{z,n}}}}\big{)}$,
or the algorithm draws a sample from the attribute with the largest loss.
However, due to the greedy nature of the algorithm analyzed, there are no
guarantees that $N_{z,n}=\Omega(n)$, and thus, in the worst case the above
excess risk bound is $\mathcal{O}(1)$.

We now show how the techniques we developed for the analysis of Algorithm 1
can be suitably employed to study the $\epsilon$-greedy strategy under the
assumptions of Section 4.1. In our results, we assume that the distribution
according to which $\epsilon$-greedy selects an attribute with probability
$\epsilon$ at each round $t$ is uniform. This is just for simplicity and all
our results hold for any distribution which places non-zero mass on all
$z\in\mathcal{Z}$.

We first present an intuitive result that says if the $\epsilon$-greedy
strategy is too exploratory ($\epsilon$ is large), the excess risk will not
converge to zero. We present an illustration of this result using Instance I
of the SyntheticModel introduced in Section 2.1 in Figure 5 in Appendix C.

######  Proposition 2.

If the $\epsilon$-greedy strategy is implemented with
$\epsilon>m\pi_{\min}:=|\mathcal{Z}|\min_{z\in\mathcal{Z}}\pi^{*}(z)$, then
its excess risk is $\Omega\left(1\right)$ with probability at least $1-\delta$
for $n$ large enough (see Eq. 20 in Appendix C.3 for the precise condition on
$n$).

_Proof Outline._ The result follows from two observations: (i) For all $t$
larger than a term $\tau_{0}(\delta,\epsilon,\pi_{\min})$, defined in (20),
with probability at least $1-\delta$, for any $z\in\mathcal{Z}$, we must have
$\pi_{t}(z)\geq\frac{\pi_{\min}+\epsilon/m}{2}$, and (ii) Suppose $\pi_{\min}$
is achieved by some attribute $z_{\min}$, i.e.,
$\pi^{*}(z_{\min})=\pi_{\min}$. Then, the first statement implies that the
excess risk of the $\epsilon$-greedy algorithm is at least
$\min_{\pi:\pi(z_{\min})\geq(\pi_{\min}+\epsilon/m)/2}\;L(z_{\min},f_{\pi})-M^{*}$,
which is strictly greater than zero by Assumption 1. The detailed proof is
reported in Appendix C.3. ∎

According to Proposition 2, for the excess risk to converge to zero, the
$\epsilon$-greedy strategy must be implemented with
$\epsilon\leq\pi_{\min}/m$. We next derive an upper-bound on the excess risk
of $\epsilon$-greedy, similar to the one in Thm. 1 for Algorithm 1.

######  Theorem 2.

Let Assumptions 1-4 hold and $\epsilon$-greedy implemented with
$0<\epsilon<m\pi_{\min}$. If the query budget $n$ is sufficiently large (see
Eqs. 22 and 23 in Appendix C.3 for the exact requirements), then for any
$0<\beta<\frac{m\pi_{\min}}{\epsilon}-1$, with probability at least
$1-2\delta$, we have

$\mathcal{R}_{n}(\text{$\epsilon$-{greedy}})=\mathcal{O}\Big{(}\frac{|\mathcal{Z}|C}{q}\max_{z\in\mathcal{Z}}\;e_{z}(N_{q})\Big{)},$
(6)

where $q=\epsilon/m$, $N_{q}=qn\big{(}\pi_{\min}-q(1+\beta)\big{)}(1-\beta)$,
and $C$ is the parameter introduced in Assumption 3.

######  Remark 4.

The assumption on $\epsilon$ in Thm. 2 implies that $q=\epsilon/m<\pi_{\min}$,
and as a result $qn\pi_{\min}<\pi_{\min}^{2}n$. Given this and the
monotonicity of the size of the confidence interval $e_{z}(N)$ w.r.t. $N$, we
may conclude that the bound on the excess risk of Alg. 1 (Eq. 5) is always
tighter than the one for $\epsilon$-greedy strategy (Eq. 6). Note that for the
classifiers discussed in Remark 2, the bound in (6) is of the same order in
$n$ as the one in (5), but with a larger leading constant.

###  4.5 Lower Bound

We first introduce some notation for presenting our lower-bound results. We
denote by $\mathcal{M}$ the class of SyntheticModels introduced in Definition
1. We also define the following class of problems:

######  Definition 2.

We use $\mathcal{Q}$ to denote the class of problems defined by the triplets
$(\bm{\mu},\mathcal{F},\ell_{01})$, where $\bm{\mu}\in\mathcal{M}$ is an
instance of the SyntheticModel, $\mathcal{F}$ is the class of linear
classifiers in two dimensions, and $\ell_{01}$ is the $0-1$ loss.

For the function class $\mathcal{F}$, we know that
$e_{z}(N)=\mathcal{O}(1/\sqrt{N})$ for both $z\in\mathcal{Z}=\\{u,v\\}$, which
implies that the excess risk achieved by both $\mathcal{A}_{\texttt{opt}}$ and
$\epsilon$-greedy strategies is of $\mathcal{O}\left(1/\sqrt{n}\right)$. We
now prove (in Appendix D) that this convergence rate (in terms of $n$) cannot
in general be improved.

######  Proposition 3.

Suppose $\mathcal{A}$ is any adaptive sampling scheme which is applied with a
budget $n$ to a problem $Q\in\mathcal{Q}$ introduced in Definition 2. Then, we
have

$\displaystyle\max_{Q\in\mathcal{Q}}\;\mathbb{E}_{Q}\left[\mathcal{R}_{n}\left(\mathcal{A}\right)\right]=\Omega\left(1/\sqrt{n}\right).$
(7)

##  5 Empirical Results

We evaluate the performance of our proposed active sampling algorithm
$\mathcal{A}_{\texttt{opt}}$ on both synthetic and real datasets, and compare
it with the following baselines: 1) $\epsilon$-greedy scheme of Abernethy et
al., (2020), 2) Empirical scheme, which is equivalent to $\epsilon$-greedy
with $\epsilon=0$, and 3) Uniform (only in the case of real datasets).

###  5.1 Synthetic Dataset

In this experiment, we compare how the $\pi_{n}(u)$ returned by the different
algorithms converge to $\pi^{*}(u)$ for the two synthetic models introduced in
Sec. 2.1 with $\mathcal{F}$ chosen as the family of logistic regression
classifiers. Since the feature space is two dimensional, we use the version of
$\mathcal{A}_{\texttt{opt}}$, $\epsilon$-greedy, and Empirical schemes in
which we train (from scratch) the classifier in each round. For
$\mathcal{A}_{\texttt{opt}}$, we use UCB of the form
$\widetilde{U}_{t}(z,\hat{f}_{t})=\widehat{L}_{N_{z,t}}(z,\hat{f}_{t})+c_{0}/\sqrt{N_{z,t}}$
with $c_{0}=0.1$ and for $\epsilon$-greedy, we use $\epsilon=0.1$. These
values of $c_{0}$ and $\epsilon$ are selected via a grid search.

Fig. 2 shows how $\pi_{n}(u)$ changes with $n$ for the three algorithms
averaged over $100$ trials. As expected, the algorithms with an exploration
component (i.e., $\mathcal{A}_{\texttt{opt}}$ and $\epsilon$-greedy)
eventually converge to the optimal $\pi^{*}(u)$ value in both cases, whereas
the Empirical scheme that acts greedily often gets stuck with a wrong mixture
distribution, resulting in high variability in its performance.

(a) (b)

Figure 2: The figure shows the convergence of $\pi_{n}(u)$ for the three
algorithms $\mathcal{A}_{\texttt{opt}}$, $\epsilon$-greedy (with
$\epsilon=0.1$) and Empirical (i.e., $\epsilon$-greedy with $\epsilon=0$), to
the optimal value $\pi^{*}(u)$ for the two instances of the SyntheticModel
introduced in Sec. 2.1.

###  5.2 Real Datasets

We now compare the performance of the different sampling schemes on 4 image
datasets: UTKFace, MNIST, FashionMNIST, and Cifar10, using CNN classifiers.
Since our goal is to demonstrate the benefits of adaptive dataset
construction, and not to achieve the highest accuracy, we use a small CNN and
run the experiments with small values of $n$ ($\leq 1000$). We report the
details of the CNN architecture and data transforms in Appendix E.

For this experiment, we use the heuristic variants of
$\mathcal{A}_{\texttt{opt}}$, $\epsilon$-greedy, and Empirical algorithms with
parameters $(n_{0},k_{0},b_{0})=(10,4,50)$. The term $c_{0}$ for
$\mathcal{A}_{\texttt{opt}}$ and $\epsilon$ for $\epsilon$-greedy are both set
to $0.1$. The UTKFace dataset consists of face images with annotations of age,
gender, and ethnicity. We choose $Y=\\{\texttt{Male,Female}\\}$ and set
$\mathcal{Z}$ to the five ethnicities. We run 5 trials of each algorithm with
$n=1000$. The other three datasets: MNIST, FashionMNIST, and Cifar10, all have
10 labels. In each case, we pair the labels to get 5 binary classification
tasks (one for each pair), and consider the problem of drawing samples from
these 5 pairs to learn a binary classifier which performs equally well on all
5 tasks. The choice of the pairs (described in Appendix E) is based on the
existing confusion matrices to include pairs that are both _easy_ and _hard_
to classify. We again run 5 trials of all the schemes with $n=500$ for MNIST
and FashionMNIST, and $n=1000$ for Cifar10.

We report the performance (i.e., the minimum test accuracy of the final
classifier over 5 attributes/tasks) of the algorithms in Table 1. We also show
how the performance changes with $n$ for FashionMNIST and Cifar10 in Fig. 3,
and for the other two datasets in Appendix E. The results show that the
adaptive schemes consistently outperform the Uniform baseline, thus, providing
evidence for the benefits of active dataset construction for practical ML
problems.

(a) (b)

Figure 3: Minimum test accuracy (over the 5 binary classification tasks) as a
function of the sampling budget $n$.

Dataset | $\bm{\mathcal{A}_{opt}}$ |  $\bm{\epsilon}$-greedy | Empirical | Uniform
---|---|---|---|---
UTKFace | $0.708\pm 0.019$ | $0.696\pm 0.013$ | $0.692\pm 0.015$ | $0.644\pm 0.010$
MNIST | $0.939\pm 0.011$ | $0.925\pm 0.021$ | $0.918\pm 0.019$ | $0.881\pm 0.022$
FashionMNIST | $0.807\pm 0.013$ | $0.771\pm 0.007$ | $0.781\pm 0.014$ | $0.735\pm 0.019$
Cifar10 | $0.707\pm 0.010$ | $0.701\pm 0.017$ | $0.688\pm 0.015$ | $0.661\pm 0.006$

Table 1: Minimum test accuracy over different attributes achieved by the
classifiers returned by the 4 sampling schemes.

##  6 Conclusion

We considered the problem of actively constructing a training set in order to
learn a classifier that achieves minimax fairness in terms of predictive loss.
We proposed a new strategy for this problem ($\mathcal{A}_{\texttt{opt}}$) and
obtained theoretical guarantees on its performance. We then suitably modified
the ideas used for analyzing $\mathcal{A}_{\texttt{opt}}$ to derive bounds for
an $\epsilon$-greedy strategy, recently proposed by Abernethy et al., (2020).
We then showed that the theoretical performance achieved by
$\mathcal{A}_{\texttt{opt}}$ and $\epsilon$-greedy cannot be improved in
general, by obtaining algorithm independent lower-bounds for the problem.
Finally, we empirically demonstrated the benefits of adaptively constructing
training sets through experiments on synthetic and real tasks.

Our theoretical results rely on the existence of a unique risk equalizing
mixture distribution $\pi^{*}$, a condition that may not always hold. Thus, an
important future work is to relax this assumption, and to design and analyze
algorithms that identify pareto optimal mixture distributions that achieve
minimax fairness. Another direction is to derive and analyze active sampling
strategies for other fairness measures.

## References

  * Abernethy et al., (2020) Abernethy, J., Awasthi, P., Kleindessner, M., Morgenstern, J., and Zhang, J. (2020).  Adaptive sampling to reduce disparate performance.  arXiv:2006.06879.
  * Agarwal et al., (2018) Agarwal, A., Beygelzimer, A., Dudík, M., Langford, J., and Wallach, H. (2018).  A reductions approach to fair classification.  In Proceedings of the 35th International Conference on Machine Learning, pages 60–69.
  * Anahideh et al., (2020) Anahideh, H., Asudeh, A., and Thirumuruganathan, S. (2020).  Fair active learning.  arXiv:2001.01796.
  * Antos et al., (2008) Antos, A., Grover, V., and Szepesvári, C. (2008).  Active learning in multi-armed bandits.  In International Conference on Algorithmic Learning Theory, pages 287–302.
  * Auer et al., (2002) Auer, P., Cesa-Bianchi, N., and Fischer, P. (2002).  Finite-time analysis of the multiarmed bandit problem.  Machine Learning, 47:235–256.
  * Barocas and Selbst, (2016) Barocas, S. and Selbst, A. (2016).  Big data’s disparate impact.  California Law Review, 104.
  * Carpentier et al., (2011) Carpentier, A., Lazaric, A., Ghavamzadeh, M., Munos, R., and Auer, P. (2011).  Upper-confidence-bound algorithms for active learning in multi-armed bandits.  In International Conference on Algorithmic Learning Theory, pages 189–203.
  * Caton and Haas, (2020) Caton, S. and Haas, C. (2020).  Fairness in machine learning: A survey.  arXiv:2010.04053.
  * Celis et al., (2020) Celis, L. E., Keswani, V., and Vishnoi, N. (2020).  Data preprocessing to mitigate bias: A maximum entropy based approach.  In International Conference on Machine Learning, pages 1349–1359.
  * Diana et al., (2020) Diana, E., Gill, W., Kearns, M., Kenthapadi, K., and Roth, A. (2020).  Convergent algorithms for (relaxed) minimax fairness.  arXiv:2011.03108.
  * Dwork et al., (2012) Dwork, C., Hardt, M., Pitassi, T., Reingold, O., and Zemel, R. (2012).  Fairness through awareness.  In Proceedings of the 3rd innovations in theoretical computer science conference, pages 214–226.
  * Feldman et al., (2015) Feldman, M., Friedler, S., Moeller, J., Scheidegger, C., and Venkatasubramanian, S. (2015).  Certifying and removing disparate impact.  In proceedings of the 21th international conference on knowledge discovery and data mining, pages 259–268.
  * Hardt et al., (2016) Hardt, M., Price, E., and Srebro, N. (2016).  Equality of opportunity in supervised learning.  In Advances in neural information processing systems, pages 3315–3323.
  * Lattimore and Szepesvári, (2020) Lattimore, T. and Szepesvári, C. (2020).  Bandit algorithms.  Cambridge University Press.
  * Lipton et al., (2017) Lipton, Z., Chouldechova, A., and McAuley, J. (2017).  Does mitigating ML’s impact disparity require treatment disparity?  arXiv:1711.07076.
  * Martinez et al., (2020) Martinez, N., Bertran, M., and Sapiro, G. (2020).  Minimax pareto fairness: A multi objective perspective.  In International Conference on Machine Learning, pages 6755–6764.
  * Polyanskiy and Wu, (2015) Polyanskiy, Y. and Wu, Y. (2015).  Lecture notes on information theory.
  * Shekhar et al., (2020) Shekhar, S., Javidi, T., and Ghavamzadeh, M. (2020).  Adaptive sampling for estimating probability distributions.  In International Conference on Machine Learning, pages 8687–8696.
  * Zemel et al., (2013) Zemel, R., Wu, Y., Swersky, K., Pitassi, T., and Dwork, C. (2013).  Learning fair representations.  In International Conference on Machine Learning, pages 325–333.

##  Appendix A Proof of Proposition 1

###### Proof.

First we note that there must exist at least one optimum mixture distribution
$\pi^{*}$ since by the Assumption 1, the objective function is continuous and
the domain of optimization, $\Delta_{m}$, is compact. We also note that any
optimal $\pi^{*}$ must lie in the interior of the simplex $\Delta_{m}$ as a
consequence of Assumption 2 (this follows by contradiction).

Next, we show that any such $\pi^{*}$ must equalize the
$L(z,f_{\pi^{*}}\coloneqq\mathbb{E}_{z}\left[\ell\left(f_{\pi^{*}},X,Y\right)\right]$
for all $z\in\mathcal{Z}$. Indeed, assume that this is not the case and
enumerate the elements of $\mathcal{Z}$ as $z_{1},\ldots,z_{m}$ in decreasing
order of $L(z,f_{\pi^{*}})$ value. Also introduce $\varrho$ to denote
$\min_{z\neq z_{1}}L(z_{1},f_{\pi^{*}})-L(z,f_{\pi^{*}})$ and (for now) assume
that $\varrho>0$.

Now define $\pi_{\epsilon}$ as follows: $\pi_{\epsilon}(z)=\pi^{*}(z)$ for
$z\in\mathcal{Z}^{\prime}\coloneqq\mathcal{Z}\setminus\\{z_{1},z_{m}\\}$,
$\pi_{\epsilon}(z_{1})=\pi^{*}(z_{1})+\epsilon$ and
$\pi_{\epsilon}(z_{m})=\pi^{*}(z_{m})-\epsilon$. Due to the continuity
assumption on the mapping $\pi\mapsto L(z,f_{\pi})$ for all $z\in\mathcal{Z}$
in Assumption 1, we note that there exists
$\epsilon_{0}<\pi_{\min}\coloneqq\min_{z\in\mathcal{Z}}\pi^{*}(z)$, such that
for all $z\neq z_{1}$ we have $L(z,f_{\pi_{\epsilon}})\leq
L(z_{1},f_{\pi^{*}})-\varrho/2$ for all $\epsilon\leq\epsilon_{0}$. Note that
$\pi_{\min}$ must be strictly greater than $0$, since $\pi^{*}$ lies in the
interior of $\Delta_{m}$. Finally, due to the monotonicity assumption in
Assumption 1, there must exist $\varrho_{1}>0$ such that
$L(z_{1},f_{\pi_{\epsilon_{0}}})=L(z_{1},f_{\pi^{*}})-\varrho_{1}<L(z_{1},f_{\pi^{*}})$.
Together, these results imply that

$\displaystyle\max_{z\in\mathcal{Z}}L(z,f_{\pi_{\epsilon_{0}}})$
$\displaystyle\leq\max\\{L(z_{1},f_{\pi^{*}})-\varrho/2,\;L(z_{1},f_{\pi^{*}})-\varrho_{1}\\}<L(z_{1},f_{\pi^{*}}),$

thus contradicting the optimality assumption on $\pi^{*}$. This completes the
proof of the statement that any optimal $\pi^{*}$ must ensure that
$L(z,f_{\pi^{*}})=L(z^{\prime},f_{\pi^{*}})$ for all
$z,z^{\prime}\in\mathcal{Z}$.

Finally, the fact that $L(z,f_{\pi^{*}})=L(z^{\prime},f_{\pi^{*}})$ for any
optimal $\pi^{*}$ also ensures the uniqueness of the optimum mixture
distribution. Again, assume that this is not the case and there exists another
optimal $\tilde{\pi}^{*}\neq\pi^{*}$ achieving optimum value in (1). Then
there must exist a $z$ such that $\pi(z)\neq\pi^{*}(z)$, and hence
$L(z,f_{\pi^{*}})\neq L(z,f_{\tilde{\pi}^{*}})$. Hence, by Assumption 1, we
have
$\max_{z\in\mathcal{Z}}L(z,f_{\pi^{*}})\neq\max_{z\in\mathcal{Z}}L(z,f_{\tilde{\pi}^{*}})$,
which contradicts our hypothesis that both $\pi^{*}$ and $\tilde{\pi}^{*}$
achieve the optimum value in (2). This concludes the proof of the uniqueness
of $\pi^{*}$. ∎

##  Appendix B Details of Algorithm 1

###  B.1 Complete Pseudo-code of $\mathcal{A}_{\texttt{opt}}$

The detailed pseudo-code of $\mathcal{A}_{\texttt{opt}}$ is given in Algorithm
2.

1

Input: $n$ (budget), $\mathcal{F}$ (function class), $\ell$ (loss function),
$C$ (Assumption 1)

2 Initialize: $\mathcal{D}_{0}=\emptyset$; $e_{z,1}=+\infty$ and
$\mathcal{D}_{(z)}=\emptyset$, for all $z\in\mathcal{Z}$;

/* Draw two independent samples from each $z\in\mathcal{Z}$ */

3 for  _$t=1,\ldots,m$_ do

4 $z\leftarrow z_{t}\in\mathcal{Z}$;

5 $\left(X_{t}^{(i)},Y_{t}^{(i)}\right)_{i=1,2}\sim P_{z}$;
$\quad\mathcal{D}_{(z)}=\\{(X_{t}^{(1)},Y_{t}^{(1)})\\}$;
$\quad\mathcal{D}_{t}\leftarrow\mathcal{D}_{t-1}\cup\\{(X_{t}^{(2)},Y_{t}^{(2)})\\}$;

6 end for

7

8$\pi_{t}\leftarrow\left(\frac{1}{m},\ldots,\frac{1}{m}\right)$;
$\quad\hat{f}_{t}\in\operatorname*{arg\,min}_{f\in\mathcal{F}}\;\frac{1}{t}\sum_{(x,y)\in\mathcal{D}_{t}}\,\ell(f,x,y)$;
$\quad N_{z,t}\leftarrow 1,\;\forall z\in\mathcal{Z}$;

9 for  _$t=m+1,\ldots,n$_ do

/* choose the next distribution $P_{XY|Z=z}$ to sample */

10 if  _$\min_{z\in\mathcal{Z}}\;N_{z,t} <\sqrt{t}$_ then

$z_{t}\in\operatorname*{arg\,min}_{z\in\mathcal{Z}}\;N_{z,t}$ // Forced
exploration

11

12 else

13
$z_{t}=\operatorname*{arg\,max}_{z\in\mathcal{Z}}\;\left[\left(\frac{1}{|\mathcal{D}_{(z)}|}\sum_{(x,y)\in\mathcal{D}_{(z)}}\,\ell(\hat{f}_{t},x,y)\right)+e_{z}(N_{z,t})+\frac{4C}{\pi_{t}(z)}\rho_{t}\right]$

14 end if

15

/* Collect data */

16 $\left(X_{t}^{(i)},Y_{t}^{(i)}\right)_{i=1,2}\sim P_{z_{t}}$

/* Perform the updates */

17 Update $\big{(}e_{z}(N_{z,t})\big{)}_{z\in\mathcal{Z}}$,
$\mathcal{D}_{t}\leftarrow\mathcal{D}_{t-1}\cup\\{(X_{t}^{(1)},Y_{t}^{(1)})\\},\quad\mathcal{D}_{(z_{t})}\leftarrow\mathcal{D}_{(z_{t})}\cup\\{(X_{t}^{(2)},Y_{t}^{(2)}\\}$.

18 Update
$\pi_{t}\leftarrow\frac{t-1}{t}\pi_{t}+\frac{1}{t}\mathbbm{1}_{\\{z_{t}\\}}$
(SS: fix the notation)

/* Update the classifier $\hat{f}_{t}$ */

19
$\hat{f}_{t}\in\operatorname*{arg\,min}_{f\in\mathcal{F}}\;\frac{1}{t}\sum_{(x,y)\in\mathcal{D}_{t}}\,\ell(f,x,y)$

20

21 end for

22

Output: $\pi_{n}$

Algorithm 2 Optimistic Sampling for Fair Classification
($\mathcal{A}_{\texttt{opt}}$)

###  B.2 Proof of Theorem 1

Introduce the following notation:

  * •

For any $z\in\mathcal{Z}$ and at any time $t\leq n$, we use $N_{z,t}$ to refer
to the number of samples drawn corresponding to the feature $z$ prior to time
$t$, i.e., $N_{z,t}=\sum_{i=1}^{t-1}\mathbbm{1}_{\\{z_{i}=z\\}}$.

  * •

$\widehat{L}_{t}(z,f)=\frac{1}{N_{z,t}}\sum_{(x,y)\in\mathcal{D}_{(z)}}\ell(f,x,y)$,
denotes the empirical risk of a classifier $f$ on the samples corresponding to
attribute $z$,

  * •

$L(z,f)=\mathbb{E}_{z}\left[\ell(f,X,Y)\right]$ denotes the population risk of
classifier $f$ corresponding to attribute $z$.

  * •

$\rho_{t}=\sum_{z\in\mathcal{Z}}\pi_{t}(z)e_{z,N_{z,t}}$ will be used to
quantify the uniform deviation of the classifier $\hat{f}_{t}$ from the
corresponding optimal classifier $f_{\pi_{t}}$. Recall that $\pi_{t}$ is the
mixture distribution of the $|\mathcal{Z}|$ attributes at time $t$ constructed
by the algorithm, i.e., $\pi_{t}(z)=\frac{N_{z,t}}{t}$ for $z\in\mathcal{Z}$.

Suppose at the end of $n$ rounds, the resulting mixture distribution is
$\pi_{n}$. Then introduce the set of _over-represented_ attributes,
$\mathcal{Z}_{o}\subset\mathcal{Z}$, defined as
$\mathcal{Z}_{o}\coloneqq\\{z\in\mathcal{Z}:\pi_{n}(z)>\pi^{*}(z)\\}$ and
refer to the set $\mathcal{Z}_{u}\coloneqq\mathcal{Z}\setminus\mathcal{Z}_{o}$
as the _under-represented_ attributes. Note that $\mathcal{Z}_{o}$ is empty
only if $\pi_{n}=\pi^{*}$. In this case, the sampling algorithm has learned
the optimal mixing distribution resulting in zero excess risk. Hence, for the
rest of the proof, we will assume that $\mathcal{Z}_{o}$ is non-empty. Note
that for any $z_{0}\in\mathcal{Z}_{o}$, Assumption 1 ensures that we must have
$L(z_{0},f_{\pi_{n}})<L(z_{0},f_{\pi^{*}})$ since
$\pi_{n}(z_{0})>\pi^{*}(z_{0})$.

######  Lemma 1.

Suppose $t_{0}\leq n$ denotes the last time that Algorithm 1 queried any
feature belonging to the subset $\mathcal{Z}_{o}$, and denote the
corresponding feature by $z_{0}$. Then, if $n\geq\frac{1}{\pi_{\min}^{2}}$
where $\pi_{\min}=\min_{z\in\mathcal{Z}}\pi^{*}(z)$, we have the following
with probability at least $1-\delta$:

$\displaystyle
L(z,f_{\pi_{t_{0}}})\leq\underbrace{L(z,f_{\pi^{*}})}_{\coloneqq
M^{*}}\;+\;\underbrace{2e_{z_{0}}(N_{z_{0},t_{0}})+\left(\nicefrac{{4C}}{{\pi^{*}(z_{0})}}\right)\rho_{t_{0}}}_{\coloneqq
B_{0}}.$ (8)

Recall that $\rho_{t}=\sum_{z}\pi_{t}(z)e_{z}(N_{z,t})$, $C$ is the constant
from Assumption 3, and $\pi^{*}$ is the optimal mixture distribution defined
in (2).

###### Proof.

Throughout this proof we assume that the $1-\delta/2$ probability event
introduced in Assumption 4 occurs for the two sequence of samples drawn by
Algorithm 1: the first used in updating $\mathcal{D}_{t}$ for training the
classifier $\hat{f}_{t}$, and the second used in updating
$\left(\mathcal{D}_{z}\right)_{z\in\mathcal{Z}}$ for estimating the loss of
$\hat{f}_{t}$. Thus, both of these events occur with probability at least
$1-\delta$.

First note the following chain of inequalities:
$\pi_{t_{0}}(z_{0})\geq\pi_{n}(z_{0})>\pi^{*}(z_{0})\geq\pi_{\min}$. Then at
time $t_{0}$, it must be the case that $N_{z_{0},t_{0}}\geq\pi_{\min}n$ as
$z_{0}$ belongs to $\mathcal{Z}_{o}$. This, along with the fact that $n\geq
1/(\pi_{\min})^{2}$ means that
$N_{z_{0},t_{0}}\geq\pi_{\min}n\geq\frac{1}{\sqrt{n}}n=\sqrt{n}$, and hence
the query to $z_{0}$ must have been made due to the condition in Line 2 of
Algorithm 1, and not due to the forced exploration step in Line 2.

Next, we have the following chain of inequalities for any $z\neq z_{0}$:

$\displaystyle L(z,f_{\pi_{t_{0}}})$
$\displaystyle\stackrel{{\scriptstyle\text{(a)}}}{{\leq}}L(z,\hat{f}_{t_{0}})+\lvert
L(z,\hat{f}_{t_{0}})-L(z,f_{\pi_{t_{0}}})\rvert$
$\displaystyle\stackrel{{\scriptstyle\text{(b)}}}{{\leq}}L(z,\hat{f}_{t_{0}})+\left(\nicefrac{{2C}}{{\pi_{t_{0}(z)}}}\right)\rho_{t_{0}}$
$\displaystyle\stackrel{{\scriptstyle\text{(c)}}}{{\leq}}\widehat{L}_{z,t_{0}}(\hat{f}_{t_{0}})+e_{z}(N_{z,t})+\left(\nicefrac{{2C}}{{\pi_{t_{0}(z)}}}\right)\rho_{t_{0}}$
$\displaystyle\stackrel{{\scriptstyle\text{(d)}}}{{\leq}}\widehat{L}_{z_{0},t_{0}}(\hat{f}_{t_{0}})+e_{z_{0}}(N_{z_{0},t})+\left(\nicefrac{{2C}}{{\pi_{t_{0}}(z_{0})}}\right)\rho_{t_{0}}$
$\displaystyle\stackrel{{\scriptstyle\text{(e)}}}{{\leq}}L(z_{0},\hat{f}_{t_{0}})+2e_{z_{0}}(N_{z_{0},t_{0}})+\left(\nicefrac{{2C}}{{\pi_{t_{0}}(z_{0})}}\right)\rho_{t_{0}}$
$\displaystyle\stackrel{{\scriptstyle\text{(f)}}}{{\leq}}L(z_{0},f_{\pi_{t_{0}}})+2e_{z_{0}}(N_{z_{0},t_{0}})+\left(\nicefrac{{4C}}{{\pi_{t_{0}}(z_{0})}}\right)\rho_{t_{0}}$
$\displaystyle\stackrel{{\scriptstyle\text{(g)}}}{{\leq}}L(z_{0},f_{\pi^{*}})+2e_{z_{0}}(N_{z_{0},t_{0}})+\left(\nicefrac{{4C}}{{\pi^{*}(z_{0})}}\right)\rho_{t_{0}}$
$\displaystyle\stackrel{{\scriptstyle\text{(h)}}}{{=}}L(z,f_{\pi^{*}})\;+\;2e_{z_{0}}(N_{z_{0},t_{0}})+\left(\nicefrac{{4C}}{{\pi^{*}(z_{0})}}\right)\rho_{t_{0}}$
$\displaystyle=M^{*}+B_{0}.$

In the above display:
(a) follows from an application of triangle inequality,
(b) applies Assumption 3,
(c) follows from the definition of event $\Omega_{2}$,
(d) follows from the attribute selection rule in Line 2,
(e) again uses the uniform deviation event $\Omega_{2}$,
(f) follows from another application of Assumption 3,
(g) uses the fact that $\pi_{t_{0}}(z_{0})>\pi^{*}(z_{0})$, the monotonicity
condition from Assumption 1,
(h) uses the result of Proposition 1 to write
$L(z_{0},f_{\pi^{*}})=L(z,f_{\pi^{*}})\coloneqq M^{*}$. ∎

Next, we show that for a large enough value of $n$, due to the forced
exploration step (Line 2 in Algorithm 1), the values of $\pi_{t_{0}}(z)$ for
$z\in\mathcal{Z}_{u}$ are not too small.

######  Lemma 2.

For any given $A<\pi_{\min}=\min_{z\in\mathcal{Z}}\pi^{*}(z)$, there exists an
$n_{0}<\infty$ , defined in (12) below, such that for all $n\geq n_{0}$, the
following are true at time $t_{0}$ (recall that $t_{0}$ denotes the last time
at which an attribute from $\mathcal{Z}_{o}$ was queried by the algorithm):

$\displaystyle\pi_{t_{0}}(z)\geq\frac{(m-1)\pi^{*}(z)}{m}+\frac{A}{m},\qquad\text{for
all}\;\;z\in\mathcal{Z}_{u},$ (9) and $\displaystyle t_{0}\geq
n\;\left(\frac{\pi_{\min}}{2\pi_{\min}-A}\right).$ (10)

Recall that in the above display $m=|\mathcal{Z}|$.

###### Proof.

First note that for any $z\in\mathcal{Z}_{u}$, we have

$M^{*}\leq L(z,f_{\pi_{t_{0}}})\leq M^{*}+B_{0},$

where we have used the notation $M^{*}=L(z,f_{\pi^{*}})$ introduced in (8).
The left inequality above is due to the monontonicity condition of Assumption
1, while the right inequality is from Lemma 1.

Introducing the notation $\pi_{\min}=\min_{z\in\mathcal{Z}}\pi^{*}(z)$, we
note that by definition $t_{0}\geq\pi_{\min}n$. Recall that the term $B_{0}$
is defined as
$B_{0}=2e_{z_{0}}(N_{z_{0},t_{0}})+\left(\nicefrac{{4C}}{{\pi^{*}(z_{0})}}\right)\rho_{t_{0}}$.
Now, since $N_{z_{0},t_{0}}\geq\pi_{\min}n$ and due to the monotonicity of
$e_{z}(N_{z,t})$, we can upper bound $e_{z_{0}}(N_{z_{0},t_{0}})$ with
$e_{z_{0}}(\pi_{\min}n)$. Next, recall that
$\rho_{t_{0}}=\sum_{z\in\mathcal{Z}}\pi_{t_{0}}(z)e_{z}(N_{z,t_{0}})\leq\max_{z\in\mathcal{Z}}e_{z}(N_{z,t_{0}})$.
Since $t_{0}\geq N_{z_{0},t_{0}}\geq\pi_{\min}n$, and due to the fact that
forced-exploration step, i.e., Line 2 of Algorithm 1, was not needed at time
$t_{0}$, we must have $N_{z,t_{0}}\geq\sqrt{\pi_{\min}n}$ for all
$z\in\mathcal{Z}_{u}$. Thus the second term in the definition of $B_{0}$ can
be simply bounded with
$\nicefrac{{4C}}{{\pi^{*}(z_{0})}}\max_{z\in\mathcal{Z}}e_{z}(\sqrt{\pi_{\min}n})\leq\nicefrac{{4C}}{{\pi_{\min}}}\max_{z\in\mathcal{Z}}e_{z}(\sqrt{\pi_{\min}n})$.
Combining these two steps, we finally get that
$B_{0}\leq\left(\nicefrac{{4C}}{{\pi_{\min}}}+2\right)\max_{z\in\mathcal{Z}}e_{z}(\sqrt{\pi_{\min}n})$.

By the monotonicity of the terms $e_{z}(N_{z,t})$ and $\rho_{t}$, we note that
$\lim_{n\to\infty}B_{0}=0$, since
$\lim_{n\to\infty}\max_{z\in\mathcal{Z}}e_{z}(\sqrt{\pi_{\min}n})=0$. Thus as
$n$ goes to infinity, $L(z,f_{\pi_{t_{0}}})$ converges to the optimal value
$M^{*}$, which by continuity of the mapping $\pi\mapsto L(z,f_{\pi})$ for all
$z\in\mathcal{Z}$ implies that $\pi_{t_{0}}\to\pi^{*}$. We can use this fact
to define a sufficient number of samples, denoted by $n_{0}$, beyond which it
can be ensured that $\pi_{t_{0}}$ satisfies the statement in (9).

$\displaystyle\pi_{\min}$
$\displaystyle=\min_{z\in\mathcal{Z}}\;\pi^{*}(z);\qquad\qquad\qquad\;b=\inf\left\\{\max_{z\in\mathcal{Z}}\;L(z,f_{\pi})-M^{*}:\|\pi^{*}-\pi\|_{\infty}>\frac{\pi_{\min}-A}{m}\right\\};$
(11) $\displaystyle n_{0}$
$\displaystyle\coloneqq\max\left\\{n_{0}^{\prime},\;\frac{1}{\pi_{\min}^{2}}\right\\};\qquad\quad
n_{0}^{\prime}\coloneqq\min\left\\{n\geq
1:\left(\frac{4C}{\pi_{\min}}+2\right)\max_{z\in\mathcal{Z}}\;e_{z}(\sqrt{\pi_{\min}n})\;\leq\;b\right\\}.$
(12)

Thus the definition of the term $b$, combined with the upper bound on $B_{0}$
due to Lemma 1 and the forced-exploration rule ensure that for $n\geq n_{0}$,
we must have $\pi_{t_{0}}(z)\geq\pi^{*}(z)/2$ for all $z\in\mathcal{Z}_{u}$ as
required by (9).

Since we will use the above computation of $n_{0}^{\prime}$ several times, we
formalize it in terms of the following definition.

######  Definition 3 (SmallestBudget).

Given constants $c>0,\,p,q\text{ and }r\in(0,1]$, the function SmallestBudget
returns the following

$\displaystyle\texttt{SmallestBudget}(c,p,q,r)=\min\left\\{n\geq
1:\max_{z}e_{z}(N_{pq})\,\leq\,\gamma/c\right\\},\quad\text{where }$
$\displaystyle\gamma=\inf\left\\{\max_{z\in\mathcal{Z}}L(z,f_{\pi})-M^{*}:\|\pi^{*}-\pi\|_{\infty}>r\right\\}\quad\text{
and }\quad N_{pq}=(pn)^{q}.$

Note that $n_{0}^{\prime}$ in (12) is equal to
$\texttt{SmallestBudget}\left((4C/\pi_{\min}+2),\,\pi_{\min},\,0.5,\,(\pi_{\min}-A)/m\right)$.

For the proof of the statement in (10), we note that since
$\pi_{t_{0}}(z)\geq\pi^{*}(z)-\frac{\pi_{\min}-A}{m}$ for all $z\neq z_{0}$,
the time $t_{0}$ must satisfy the following:

$\displaystyle t_{0}$ $\displaystyle=N_{z_{0},t_{0}}+\sum_{z\neq
z_{0}}N_{z,t_{0}}\geq\pi^{*}(z_{0})n+\sum_{z\neq
z_{0}}\left(\pi^{*}(z)-\frac{\pi_{\min}-A}{m}\right)t_{0}$
$\displaystyle=\pi^{*}(z_{0})n+\left(1-\pi^{*}(z_{0})+\frac{(m-1)(\pi_{\min}-A)}{m}\right)t_{0}.$

This, in turn, implies that

$t_{0}\geq
n\,\left(\frac{\pi^{*}(z_{0})}{\pi^{*}(z_{0})+\frac{m-1}{m}(\pi_{\min}-A)}\right)\geq
n\,\left(\frac{\pi_{\min}}{2\pi_{\min}-A}\right).$

This completes the proof of (10). ∎

We now state a basic result about the behavior of $\pi_{t}$:

######  Lemma 3.

Suppose the empirical mixture distribution is $\pi_{r}$ at some time $r$, and
in the time interval $\\{r+1,\ldots,t\\}$ the agent only queries attributes
$z$ from $\mathcal{Z}^{\prime}\subset\mathcal{Z}$ such that
$\sum_{z\in\mathcal{Z}^{\prime}}\pi_{r}(z)<1$. Then there exists at least one
$z\in\mathcal{Z}^{\prime}$ such that $\pi_{t}(z)>\pi_{r}(z)$.

###### Proof.

The statement follows by contradiction. Assume that the conclusion stated
above is not true, and $\pi_{t}(z)\leq\pi_{r}(z)$ for all
$z\in\mathcal{Z}^{\prime}$. Introducing $b_{z}$ to denote the number of times
attribute $z\in\mathcal{Z}^{\prime}$ is queried in the time interval
$\\{r+1,\ldots,t\\}$, we then have

$\pi_{t}(z)=\frac{r\pi_{r}(z)+b_{z}}{t}\;\Rightarrow\;(t-r)\pi_{t}(z)+r\underbrace{\left(\pi_{t}(z)-\pi_{r}(z)\right)}_{\leq
0}=b_{z}\;\Rightarrow\;(t-r)\pi_{t}(z)\geq b_{z}.$ (13)

Note that
$\sum_{z\in\mathcal{Z}^{\prime}}\pi_{t}(z)=\frac{t-r(1-\sum_{z}\pi_{r}(z))}{t}<1$
by assumption that $\sum_{z\in\mathcal{Z}^{\prime}}\pi_{r}(z)<1$. Combining
this with (13), we get the required contradiction as follows:

$(t-r)>(t-r)\sum_{z\in\mathcal{Z}^{\prime}}\;\pi_{t}(z)\geq\sum_{z\in\mathcal{Z}^{\prime}}\;b_{z}=(t-r).$

∎

Before proceeding, we introduce some notations. As stated earlier, due to the
definition of the term $t_{0}$, we know that in the rounds
$t\in\\{t_{0}+1,\ldots,n\\}$, the algorithm only queries the attributes
belonging to the set $\mathcal{Z}_{u}$. If the set $\mathcal{Z}_{u}$ is empty,
that means $t_{0}$ must be equal to $n$ and the algorithm stops there.
Otherwise, the interval $\\{t_{0}+1,\ldots,n\\}$ can be partitioned into
$\\{t_{0}+1,\ldots,t_{1}\\}$, $\\{t_{1}+1,\ldots,t_{2}\\}$, …,
$\\{t_{s}+1,\ldots,n\\}$ for appropriately defined $t_{1},\ldots,t_{s}$ and
$s\leq|\mathcal{Z}|-1$ as follows.

  * •

First we introduce the term $\mathcal{Z}_{t}$ to denote the ‘active set’ of
attributes at time $t$, i.e., the set of attributes that are queried at least
once after time $t$. Note that we have $\mathcal{Z}_{t_{0}}=\mathcal{Z}_{u}$.

  * •

Then (for $t\geq t_{0}$) we define a subset $\mathcal{Z}_{o}^{(1)}$ of
$\mathcal{Z}_{t}$ as those attributes $z\in\mathcal{Z}_{t}$ for which we have
$\pi_{t_{0}}(z)<\pi_{n}(z)$. By Lemma 3, we know that $\mathcal{Z}_{o}^{(1)}$
must be non-empty.

  * •

Next, we define $t_{1}$ as the last time $t\leq n$ at which an attribute
$z\in\mathcal{Z}_{o}^{(1)}$ is queried by the algorithm.

  * •

If $t_{1}=n$, then we stop and $s=1$. Otherwise, we repeat the previous two
steps with
$\mathcal{Z}_{t_{1}}=\mathcal{Z}_{t_{0}}\setminus\mathcal{Z}_{o}^{(1)}$.

To clarify the above introduced notation, we present an example.

######  Example 1.

Consider a problem with set of attributes
$\mathcal{Z}=\\{\mathfrak{a}_{1},\mathfrak{a}_{2},\mathfrak{a}_{3},\mathfrak{a}_{4}\\}$,
$n=20$ and $\pi^{*}=\left(0.25,0.25,0.25,0.25\right)$. Suppose an adaptive
algorithm111note that the sequence of attributes have been chosen only for
illustrating the notation, and do not satisfy the forced exploration condition
in Algorithm 1 selects the following sequence of attributes (given a budget of
$20$):

$\displaystyle\mathfrak{a}_{1},\;\mathfrak{a}_{2},\;\mathfrak{a}_{3},\;\mathfrak{a}_{4},\;\mathfrak{a}_{1},\;\mathfrak{a}_{1},\;\mathfrak{a}_{1},\;\mathfrak{a}_{1},\;\mathfrak{a}_{1},\;\mathfrak{a}_{1},\;\mathfrak{a}_{4},\;\mathfrak{a}_{1},\;\mathfrak{a}_{1},\quad\mathfrak{a}_{2},\;\mathfrak{a}_{2},\;\mathfrak{a}_{2},\;\mathfrak{a}_{3},\;\mathfrak{a}_{3},\;\mathfrak{a}_{3},\quad\mathfrak{a}_{4}.$
(14)

Then as we can see, the algorithm ends up with $\pi_{n}=(9/20,1/5,1/5,3/20)$.

  * •

Comparing $\pi_{n}$ with $\pi^{*}$, we observe that the set $\mathcal{Z}_{o}$
is $\\{\mathfrak{a}_{1}\\}$ and
$\mathcal{Z}_{u}=\\{\mathfrak{a}_{2},\mathfrak{a}_{3},\mathfrak{a}_{4}\\}$.

  * •

The last time an element of $\mathcal{Z}_{o}$ is queried, that is $t_{0}$, is
equal to $13$ and the corresponding attribute is $z_{0}=\mathfrak{a}_{1}$. The
mixture distribution at time $t_{0}$ is $\pi_{t_{0}}=(9/13,1/13,1/13,2/13)$.

  * •

Comparing $\pi_{t_{0}}$ with $\pi_{n}$, we observe that the set
$\mathcal{Z}_{o}^{(1)}$ is $\\{\mathfrak{a}_{2},\mathfrak{a}_{3}\\}$ since
their fractions increase in the period $[t_{0}+1,n]_{\mathbb{N}}$, and
$\mathcal{Z}_{u}^{(1)}=\\{\mathfrak{a}_{4}\\}$. The last time an element of
$\mathcal{Z}_{o}^{(1)}$ is queried is $t_{1}=19$, and the corresponding
attribute is $z_{1}=\mathfrak{a}_{3}$.

  * •

Finally, since only one element remains, we have
$\mathcal{Z}_{o}^{(2)}=\\{\mathfrak{a}_{4}\\}$,
$\mathcal{Z}_{u}^{(2)}=\emptyset$ and thus $t_{2}=n$ and
$z_{2}=\mathfrak{a}_{4}$. Also note that the total number of phases above is
$3$ and hence the term $s=3-1=2$.

######  Lemma 4.

Suppose, $z_{1}$ is the element of $\mathcal{Z}_{o}^{(1)}$ (introduced above)
queried by the algorithm at time $t_{1}$. Then, the following is true at time
$t_{1}$ for all $z\in\mathcal{Z}\setminus\\{z_{1}\\}$

$\displaystyle L(z,f_{\pi_{t_{1}}})\leq
M^{*}+B_{0}+B_{1},\qquad\text{where}\qquad
B_{1}=2e_{z_{1}}(N_{z_{1},t_{1}})+\left(\nicefrac{{8C}}{{\pi^{*}(z_{1})}}\right)\rho_{t_{1}}$
(15)

Furthermore, repeating this process till the budget is exhausted, we get for
any $z\in\mathcal{Z}$ and an $s<m$

$\displaystyle L(z,f_{\pi_{n}})\leq
M^{*}+\sum_{i=0}^{s}B_{i},\qquad\text{where}\qquad
B_{i}=2e_{z_{i},N_{z_{i},t_{i}}}+\left(\nicefrac{{8C}}{{\pi_{\min}\pi^{*}(z_{i})}}\right)\rho_{t_{i}},\;\;\text{
for }\;i>1.$ (16)

Here $s$ is the (random) number of ‘phases’ (see Example 1), and is always
upper bounded by $m=|\mathcal{Z}|$.

###### Proof.

To prove (15), we note that at time $t_{1}$ for any $z\neq z_{1}$, we have

$\displaystyle L(z,f_{\pi_{t_{1}}})$
$\displaystyle\;\stackrel{{\scriptstyle\text{(a)}}}{{\leq}}\;L(z,\hat{f}_{t_{1}})+\frac{2C}{\pi_{t_{1}}(z)}\rho_{t_{1}}\;\leq\;\widehat{L}_{t_{1}}(z,\hat{f}_{t_{1}})+e_{z,N_{z,t_{1}}}+\frac{2C}{\pi_{t_{1}}(z)}\rho_{t_{1}}$
$\displaystyle\;\stackrel{{\scriptstyle\text{(b)}}}{{\leq}}\;\widehat{L}_{t_{1}}(z_{1},\hat{f}_{t_{1}})+e_{z_{1},N_{z_{1},t_{1}}}+\frac{2C}{\pi_{t_{1}}(z_{1})}\rho_{t_{1}}$
$\displaystyle\;\stackrel{{\scriptstyle\text{(c)}}}{{\leq}}\;L(z_{1},f_{\pi_{t_{1}}})+2e_{z_{1},N_{z_{1},t_{1}}}+\frac{4C}{\pi_{t_{1}}(z_{1})}\rho_{t_{1}}$
$\displaystyle\;\stackrel{{\scriptstyle\text{(d)}}}{{\leq}}\;L(z_{1},f_{\pi_{t_{0}}})+2e_{z_{1},N_{z_{1},t_{1}}}+\frac{4C}{\pi_{t_{1}}(z_{1})}\rho_{t_{1}}$
$\displaystyle\;\stackrel{{\scriptstyle\text{(e)}}}{{\leq}}\;L(z_{1},f_{\pi_{t_{0}}})+2e_{z_{1},N_{z_{1},t_{1}}}+\frac{4C}{\frac{(m-1)\pi^{*}(z_{1})}{m}+\frac{A}{m}}\rho_{t_{1}}$
$\displaystyle\;\stackrel{{\scriptstyle\text{(f)}}}{{=}}\;L(z_{1},f_{\pi_{t_{0}}})+B_{1}\;\leq\;M^{*}+B_{0}+B_{1}.$

In the above display
(a) uses Assumption 3 and the event $\Omega_{2}$ in Assumption 4,
(b) follows from the point selection rule in Line 2 of Algorithm 1,
(c) uses Assumption 3,
(d) uses that from the definition of $z_{1}$, we must have
$\pi_{t_{1}}(z_{1})\geq\pi_{t_{0}}(z_{1})$, and due to monotonicity assumption
(Assumption 1), $L(z_{1},f_{\pi_{t_{0}}})>L(z_{1},f_{\pi_{t_{1}}})$, and
(e) uses the fact that
$\pi_{t_{1}}(z_{1})\geq\pi_{t_{0}}(z_{1})\geq\pi^{*}(z_{1})/2$ proved in (9),
and
(f) uses Lemma 1 to bound $L(z_{1},f_{\pi_{t_{0}}})$ with $M^{*}+B_{0}$ to get
(15).

Now, assume that the budget $n$ satisfies $n\geq
n_{1}\coloneqq\max\\{n_{0},n_{1}^{\prime}\\}$; where

$\displaystyle n_{1}^{\prime}$
$\displaystyle=\texttt{SmallestBudget}\left(c_{0}+c_{1},\;\pi_{\min},\;0.5,\;\frac{2(\pi_{\min}-A)}{m}\right),\quad\text{
where }$ (17) $\displaystyle c_{0}$ $\displaystyle=\frac{4C}{A_{0}}+2;\quad
c_{1}=\frac{4C}{A_{1}}+2;\quad\text{and}\quad
A_{i}\coloneqq\frac{i}{m}A+\frac{(m-i)\pi_{\min}}{m},\;\text{for }0\leq i\leq
m.$ (18)

Then by the definition of the SmallestBudget function (introduced in Def. 3 in
Appendix B.2), we must have
$\pi_{t_{1}}(z)\geq\frac{(m-2)\pi^{*}(z)}{m}+\frac{2A}{m}$ for all
$z\in\mathcal{Z}$.

The proof of (16) essentially follows by repeating the above argument a
further $s-1$ times. However, there is one minor difference. In proving (15),
specifically in Step (e), we used the fact that $\pi_{t_{1}}(z_{1})\geq
A_{1}\coloneqq\frac{A}{m}+\frac{(m-1)\pi_{\min}}{m}$. For $i\geq 2$, we can
similarly use the fact that $\pi_{t_{i}}(z_{i})\geq
A_{i}\coloneqq\frac{iA+(m-1)\pi_{\min}}{m}$. The corresponding requirement on
$n$ is that, with

$\displaystyle n$ $\displaystyle\geq
n_{i}\coloneqq\max\\{n_{0},\ldots,n_{i-1},n^{\prime}_{i}\\},\qquad\text{ where
}$ (19) $\displaystyle n^{\prime}_{i}$
$\displaystyle=\texttt{SmallestBudget}\left(c_{0}+\ldots
c_{i},\;\pi_{\min},\;0.5,\;\frac{(i+1)(\pi_{\min}-A)}{m}\right),\qquad\text{and}$
$\displaystyle c_{i}$ $\displaystyle=\frac{4C}{A_{i}}+2,\qquad\text{ for all
}\;\;0\leq i\leq m.$

∎

######  Lemma 5.

Finally, we obtain that
$\max_{z\in\mathcal{Z}}L(z,\hat{f}_{\pi_{n}})-M^{*}=\mathcal{O}\left(\frac{|\mathcal{Z}|C}{\pi_{\min}}\max_{z\in\mathcal{Z}}e_{z}(N_{A})\right)$,
where $N=A\left(\frac{\pi_{\min}}{2\pi_{\min}-A}\right)n$.

###### Proof.

First note that for all $t_{i}$, $i=1,2,\ldots,s$, we have
$\rho_{t}\leq\max_{z\in\mathcal{Z}}e_{z}(N_{z,t})$. Now, we note the
following: for any $i=0,\ldots s$, we have
$\min_{z\in\mathcal{Z}}\pi_{t_{i}}(z)\geq A_{i}\geq A$. Also for all
$i=0,\ldots s$, we also have trivially, using (10), $t_{i}\geq
N_{A}\coloneqq\pi_{\min}/(2\pi_{\min}-A)n$. Together these two statements
imply the following:

  * •

$B_{0}\leq c_{0}\max_{z\in\mathcal{Z}}e_{z}(N_{z,t_{0}})\leq
c_{0}\max_{z\in\mathcal{Z}}e_{z}(N_{A})=\left(\frac{4C}{\pi_{\min}}+2\right)\max_{z\in\mathcal{Z}}e_{z}(N_{A})$.

  * •

Similarly, for $i\geq 1$ we have $B_{i}\leq
c_{i}\max_{z\in\mathcal{Z}}e_{z}(N_{z,t_{i}})\leq
c_{i}\max_{z\in\mathcal{Z}}e_{z}(N_{A})\leq\left(\frac{4C}{A_{i}}+2\right)\max_{z\in\mathcal{Z}}e_{z}(N_{A})$.

Combining the above two points, we get the following

$\sum_{i=1}^{s}B_{i}\leq\sum_{i=1}^{s}\left(\frac{4C}{A_{i-1}}+2\right)\max_{z\in\mathcal{Z}}e_{z}(N_{A})\;$

which, if $A\geq\pi_{\min}/2$, implies

$\max_{z\in\mathcal{Z}}L(z,f_{\pi_{n}})-M^{*}=\mathcal{O}\left(\frac{|\mathcal{Z}|C}{\pi_{\min}}\max_{z\in\mathcal{Z}}e_{z}(N_{A})\right)$

as required. Note that the above result holds under the assumption that $n$ is
large enough to ensure that the conditions in (19) is satisfied for all $0\leq
i\leq s$. Since $s\leq m-1$, a sufficient condition for this is that the
condition in (19) is satisfied for all $0\leq i\leq m-1$. ∎

###  B.3 Knowledge of parameter $C$

We now show that if for some $0<\zeta<1$, it is known that
$\lim_{N\to\infty}\max_{z\in\mathcal{Z}}\frac{e_{z}(N^{\zeta})}{N^{\zeta-1}}=0$,
then we can obtain the same guarantees for $\mathcal{A}_{\texttt{opt}}$ as in
Theorem 1 without the knowledge of the parameter $C$ by making the following
changes to $\mathcal{A}_{\texttt{opt}}$:

  * •

Remove the third term (i.e., the $C$ dependent term) from the definition of
$U_{t}$ in (4).

  * •

Replace the $\sqrt{N_{z,t}}$ with $N_{z,t}^{\zeta}$ in Line 1 of Algorithm 1.

Then with the same definition of $t_{0}$ and $z_{0}$ as in Lemma 1 and Lemma
2, the following is true at time $t_{0}$:

$\displaystyle L(z,f_{\pi_{t_{0}}})$
$\displaystyle\leq\widehat{L}_{t_{0}}(z,f_{\pi_{t_{0}}})+e_{z}(N_{z,t_{0}})$
$\displaystyle\leq\underbrace{\widehat{L}_{t_{0}}(z,\hat{f}_{t_{0}})+e_{z}(N_{z,t_{0}})}_{=U_{t_{0}}(z,\hat{f}_{t_{0}})}+\frac{2C}{\pi_{t_{0}}(z)}\rho_{t_{0}}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}U_{t_{0}}(z_{0},\hat{f}_{t_{0}})+\frac{2C}{\pi_{t_{0}}(z)}\rho_{t_{0}}$
$\displaystyle\leq
L(z_{0},f_{\pi_{t_{0}}})+2e_{z}(N_{z_{0},t_{0}})+2C\rho_{t_{0}}\left(\frac{1}{\pi_{t_{0}}(z_{0})}+\frac{1}{\pi_{t_{0}}(z)}\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}L(z_{0},f_{\pi_{t_{0}}})+\left(\frac{2C}{\pi_{\min}}+\frac{2C}{t_{0}^{\zeta-1}}\right)\rho_{t_{0}}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}L(z_{0},f_{\pi_{t_{0}}})+\underbrace{\left(\frac{2C}{\pi_{\min}}+\frac{2C}{t_{0}^{\zeta-1}}\right)\max_{z\in\mathcal{Z}}e_{z}(t_{0}^{\zeta})}_{\coloneqq
B_{0}^{\prime}}$

In the above display,
(a) uses the fact that at time $t_{0}$, the attribute $z_{0}$ was selected by
maximizing $U_{t_{0}}(z,\hat{f}_{t_{0}})$,
(b) uses the fact that $\pi_{t_{0}}(z_{0})>\pi_{\min}$ and $\pi_{t_{0}}(z)\geq
t_{0}^{\zeta-1}$ for all $z\neq z_{0}$ since the forced exploration step was
not invoked at time $t_{0}$, and
(c) uses the fact that
$\rho_{t_{0}}\leq\max_{z\in\mathcal{Z}}e_{z}(N_{z,t_{0}})\leq\max_{z\in\mathcal{Z}}e_{z}(t_{0}^{\zeta})$
due to the monotonicity of $e_{z}(N)$ and the fact that $N_{z,t_{0}}\geq
t_{0}^{\zeta}$ for all $z\in\mathcal{Z}$ at time $t_{0}$.

Now, to continue with the rest of the proof as in Appendix B.2, we need that
the term $B_{0}^{\prime}$ converges to zero as $n$ (and hence, $t_{0}$) goes
to infinity. The first term of $B_{0}^{\prime}$, i.e.,
$2C\max_{z}e_{z}(t_{0}^{\zeta})/\pi_{\min}$, converges to zero from the
condition in Assumption 4, while the second term,
$\frac{2C}{t_{0}^{\zeta-1}}\max_{z}e_{z}(t_{0}^{\zeta})$ converges to zero
from the assumption on $\zeta$ made at the beginning of this section. Using
this fact, we can then proceed as in Lemmas 2, 4, and 5 to get the final
result.

###  B.4 Relation to Active Learning in Bandits

As mentioned in Remark 1, our formulation of the minimax fair classification
problem diverges from the Active learning in bandit (ALB) problem due to the
fact that drawing samples from one attribute can reduce the performance of
another. To make the discussion concrete, consider an ALB problem with two
distributions $Q_{1}\sim N(\mu_{1},\sigma_{1}^{2})$ and $Q_{2}\sim
N(\mu_{2},\sigma_{2}^{2})$ for $\mu_{1},\mu_{2}\in\mathbb{R}$ and
$\sigma_{1}^{2},\sigma_{2}^{2}\in(0,\infty)$. Let $N_{i,t}$ denote the number
of samples allocated by an agent to $Q_{i}$ for $i=1,2$ and $t\geq 1$. Then,
we can construct high probability confidence sequences around
$\hat{\mu}_{i,t}$ (the empirical counterparts to $\mu_{i}$ at time $t$) of
non-increasing (in $t$) lengths $e_{i,t}$ such that
$|\hat{\mu}_{i,t}-\mu_{i}|\leq e_{i,t}$. If at time $t$, the agent decides to
draw a sample from arm $1$, it would not change the quality of its estimate of
$Q_{2}$ at time $t+1$ and beyond.

On the other hand, let us consider Instance 2 of
SyntheticModel$(\boldsymbol{\mu})$ (introduced in Definition 1) with
$\mathcal{F}$ being the set of all linear classifiers passing through origin.
This is illustrated in Figure 4, where the circles denote the one-square-
deviation region around the mean values. The shaded circles correspond to the
attribute $Z=v$, and the circles with dashed boundaries correspond to the
label $Y=0$. For example, $P_{X|YZ}(\cdot|Y=0,Z=u)$ is denoted by the top left
circle. Suppose at some time $t_{1}$, the current classifier $\hat{f}_{t_{1}}$
(represented by the solid gray line passing through origin in Figure 4) has
low (resp. high) accuracy for the protected attribute $Z=v$ (resp. $Z=u$). To
remedy this, the agent may draw more samples from the distribution of
attribute $Z=v$ to skew the training dataset distribution towards $Z=v$. This
would result in the updated classifier $\hat{f}_{t_{2}}$ (the dashed gray line
in Figure 4) at some time $t_{2}>t_{1}$ to achieve high accuracy for the
attribute $Z=v$. But this increased accuracy for $Z=v$ comes at the cost of a
reduction in the prediction accuracy for the attribute $Z=u$, as shown in
Figure 4.

The above discussion highlights the key distinguishing feature of our problem
from the prior work in ALB. Because of this distinction, the existing analyses
of the ALB algorithms do not carry over directly to our case. As a result, to
quantify the performance of Algorithm 1, we device a new ‘multi-phase’
approach which is described in detail in Sec. 4.3 and Appendix. B.2.

Figure 4: Figure demonstrates the second instance of SyntheticModel introduced
in Sec. 2.1. Here the circles denote the one-standard-deviation regions of the
distributions of features $X$ conditioned on $Y$ and $Z$. Shaded circles
correspond to $Z=u$ and circles with dashed boundaries represent $Y=0$. The
solid gray line represents a possible linear classifier that may be learned if
the dataset has fewer examples from $Z=v$. If an adaptive algorithm addresses
this by populating the data-set with numerous examples from $Z=v$, a possible
updated linear classifier is shown by the dashed gray line. This demonstrates
the main distinguishing feature of our problem w.r.t. the active learning in
bandits (ALB) problem: _allocating samples to improve the performance on one
attribute can have an adverse effect on the performance of the resulting
classifier on other attributes_.

##  Appendix C Details of $\epsilon$-greedy strategy

The $\epsilon$-greedy strategy originally proposed by Abernethy et al., (2020)
proceeds as follows at time $t$: with probability $1-\epsilon$, draw a pair
$(X_{t},Y_{t})$ from the distribution $P_{z_{t}}$ where $z_{t}$ is the
attribute with largest empirical loss; and with probability $\epsilon$ draw
$(Z_{t},X_{t},Y_{t})$ from the population distribution $P_{XYZ}$. If
$\pi_{Z}(\cdot)$ denotes the marginal of the population distribution over
$\mathcal{Z}$, i.e., $\pi_{Z}(z)=\sum_{x,y}P_{XYZ}(x,y,z)$; then the
$\epsilon$-greedy strategy can be equivalently described as follows:
For any $t=1,2,\ldots$, do

  * •

Draw a random variable $Q_{t}\sim\texttt{Bernoulli}(\epsilon)$.

  * •

If $Q_{t}=1$, draw $Z_{t}\sim\pi_{Z}$. Else set
$Z_{t}\in\operatorname*{arg\,max}_{z\in\mathcal{Z}}\hat{L}_{t}(z,\hat{f}_{t})$.

  * •

Draw a pair of samples from the distribution $P_{Z_{t}}$.

For simplicity of presentation, we assume that $\pi_{Z}$ is the uniform
distribution, i.e., $\pi_{Z}(z)=1/m$ for all $z\in\mathcal{Z}$. However, our
theoretical results can be easily generalized to the case of any $\pi_{Z}$
which places non-zero mass on all $z\in\mathcal{Z}$.

###  C.1 Proof of Proposition 2

Fix any $z\in\mathcal{Z}$, and decompose $N_{z,t}$ into
$N_{z,t}^{(0)}+N_{z,t}^{(1)}$ where,
$N_{z,t}^{(1)}=\sum_{i=1}^{t}\mathbbm{1}_{\\{z_{i}=z\\}}Q_{i}$ is the number
of times up to round $t$ the attribute $z$ was queried due to the exploration
step (i.e., $Q_{t}=1$) of the $\epsilon$-greedy algorithm.

Now, define $M_{z,0}=0$ and
$M_{z,t}=M_{z,t-1}+Q_{t}\mathbbm{1}_{\\{\tilde{z}_{t}=z\\}}-\epsilon/m$. Due
to the fact that $Q_{t}$ and $\tilde{z}_{t}$ are independent, it is easy to
check that $(M_{z,t})_{t\geq 0}$ forms a martingale sequence. For some given
$\delta>0$, introduce the notation $\delta_{t}=\frac{6\delta}{m\pi^{2}t^{2}}$
and $b_{t}=\sqrt{\frac{t\log\left(\nicefrac{{2}}{{\delta_{t}}}\right)}{2}}$.
We then have the following:

$\displaystyle\sum_{t=1}^{n}P\left(M_{z,t}>b_{t}\right)$
$\displaystyle\leq\sum_{t=1}^{n}\left(\prod_{i=1}^{t}\mathbb{E}\left[\exp\left(\lambda
Q_{i}\mathbbm{1}_{\\{\tilde{z}_{i}=z\\}}-\epsilon/m\right)\middle|(Q_{j})_{j=1}^{i-1}\right]\right)e^{-\lambda
b_{t}}$ $\displaystyle\leq\sum_{t=1}^{n}e^{t\lambda^{2}/8-\lambda
b_{t}}\stackrel{{\scriptstyle(a)}}{{=}}\sum_{t=1}^{n}e^{-2b_{t}^{2}/t}\leq\sum_{t=1}^{\infty}\frac{\delta_{t}}{2}=\frac{\delta}{2m}.$

In the above display, (a) follows by setting $\lambda=4b_{t}/t$. By repeating
the same argument with the martingale sequence $\\{-M_{z,t}:t\geq 0\\}$, we
get that $P\left(|M_{z,t}|\leq b_{t},\forall t\geq 1,\;\forall
z\in\mathcal{Z}\right)\geq 1-\delta$. In other words, it implies that, with
probability at least $1-\delta$, we have the following:

$N_{z,t}^{(1)}\geq\frac{t}{\epsilon}-b_{t},\quad\forall\;t\geq 1,\;\forall
z\in\mathcal{Z}.$

This implies that $N_{z,t}\geq\nicefrac{{\epsilon}}{{m}}-b_{t}$ for all $z,t$.
In particular, if $z_{\min}$ is the attribute such that
$\pi^{*}(z_{\min})=\min_{z\in\mathcal{Z}}\pi^{*}(z)=\pi_{\min}$, then this
implies that $\hat{\pi}_{t}(z_{\min})\geq\epsilon/m-b_{t}/t$ for all $t,z$.
Using the fact that $\lim_{t\to\infty}b_{t}/t=0$, we define
$\tau_{0}=\tau_{0}(\delta,\epsilon,\pi_{\min})$, as follows:

$\displaystyle\tau_{0}(\delta,\epsilon,\pi_{\min})\coloneqq\min\left\\{t\geq
1:\sqrt{\frac{\log\left(\nicefrac{{m\pi^{2}t^{2}}}{{3\delta}}\right)}{2t}}\leq\frac{\epsilon-m\pi_{\min}}{2m}\right\\}.$
(20)

This implies that with probability at least $1-\delta$,
$\pi_{t}(z_{\min})\geq(\pi_{\min}+\epsilon/m)/2$ for all $t\geq\tau_{0}$.
Hence the excess risk of the $\epsilon$-greedy algorithm under these
conditions is at least
$\min_{\pi:\pi(z_{\min})\geq(\pi_{\min}+\epsilon/m)/2}\mathbb{E}_{z_{\min}}\left[\ell\left(f_{\pi},X,Y\right)\right]-M^{*}$,
which is an $\Omega(1)$ term due to Assumption 1.

###  C.2 Proof of Theorem 2

First we partition the interval $[1,n]_{\mathbb{N}}$ into $\mathrm{T}_{0}$ and
$\mathrm{T}_{1}$, where $\mathrm{T}_{j}=\\{t:Q_{t}=j\\}$ for $j=0,1$. In other
words, $\mathrm{T}_{0}$ denotes the times at which the $\epsilon$-greedy
strategy is _greedy_ while $\mathrm{T}_{1}$ denotes the times at which
$Q_{t}=1$ and the $\epsilon$-greedy strategy is exploratory.

Then we introduce the following terms:

  * •

Define $\mathcal{Z}_{o}$ and $\mathcal{Z}_{u}$ as in the proof of Theorem 1.
That is, $\mathcal{Z}_{o}=\\{z\in\mathcal{Z}:\pi_{n}(z)>\pi^{*}(z)\\}$ and
$\mathcal{Z}_{u}=\mathcal{Z}\setminus\mathcal{Z}_{o}$. We assume, as before,
that $\mathcal{Z}_{o}\neq\emptyset$. Then, we define
$t_{0}\coloneqq\max\\{t\in\mathrm{T}_{0}:z_{t}\in\mathcal{Z}_{o}\\}$, and
denote the corresponding attribute (queried at time $t_{0}$) with $z_{0}$.

  * •

Then, by appealing to Lemma 3, we note that there must exist a nonempty
$\mathcal{Z}_{o}^{(1)}\subset\mathcal{Z}_{u}$ such that
$\pi_{n}(z)>\pi_{t_{0}}(z)$ for all $z\in\mathcal{Z}_{o}^{(1)}$. Using this
define $t_{1}=\max\\{t\in\mathrm{T}_{0}:z_{t}\in\mathcal{Z}_{o}^{(1)}\\}$ and
use $z_{1}$ to denote the corresponding attribute queried at time $t_{1}$. We
can proceed in this way to define $\\{(t_{j},z_{j}):2\leq j\leq s\\}$ for an
appropriate $s\leq m-1$ (such that $t_{s}=n$).

First, we define the $1-\delta$ probability event $\Omega_{3}$ as follows (see
proof of Proposition 2 in Appendix C.3 for derivation):

$\displaystyle\Omega_{3}=\left\\{\left\lvert
N_{z,t}^{(1)}-\frac{\epsilon}{m}t\right\rvert\leq\underbrace{\sqrt{\frac{t\log(m\pi^{2}t^{2}/3\delta)}{2}}}_{\coloneqq
b_{t}}\right\\}.$ (21)

For the rest of this proof, we will assume that the $(1-2\delta)$ probability
event $\cap_{i=1}^{3}\Omega_{i}$ holds, where $\Omega_{1}$ and $\Omega_{2}$
were introduced in Assumption 4.

Then we have the following:

######  Lemma 6.

At time $t_{0}$, we have $L(z,f_{\pi_{t_{0}}})\leq M^{*}+\tilde{B}_{0}$ where
$\tilde{B}_{0}\coloneqq
4\left(1+\nicefrac{{C}}{{q-\beta_{t_{0}}/t_{0}}}\right)\max_{z\in\mathcal{Z}}e_{z,N_{z,t_{0}}}$
and $q=\epsilon/m$.

###### Proof.

$\displaystyle L(z,f_{\pi_{t_{0}}})$
$\displaystyle\leq\widehat{L}_{t_{0}}(z,f_{\pi_{t_{0}}})+2e_{z}(N_{z,t_{0}})$
$\displaystyle\leq\widehat{L}_{t_{0}}(z,\hat{f}_{t_{0}})+2e_{z}(N_{z,t_{0}})+\frac{2C}{\pi_{t_{0}}(z)}\rho_{t_{0}}$
$\displaystyle\leq\widehat{L}_{t_{0}}(z_{0},\hat{f}_{t_{0}})+2e_{z}(N_{z,t_{0}})+\frac{2C}{\pi_{t_{0}}(z)}\rho_{t_{0}}$
$\displaystyle\leq
L(z_{0},f_{\pi_{t_{0}}})+2\left(e_{z}(N_{z,t_{0}})+e_{z_{0}}(N_{z_{0},t_{0}})\right)+2C\rho_{t_{0}}\left(\frac{1}{\pi_{t_{0}}(z_{0})}+\frac{1}{\pi_{t_{0}}(z)}\right)$
$\displaystyle\leq
L(z_{0},f_{\pi_{t_{0}}})+4\left(1+\frac{C}{\epsilon/m-b_{t_{0}}/t_{0}}\right)\max_{z\in\mathcal{Z}}e_{z}(N_{z,t_{0}})$
$\displaystyle=L(z_{0},f_{\pi_{t_{0}}})+\tilde{B}_{0}.$

∎

######  Lemma 7.

Suppose $n$ is large enough to satisfy the conditions in (23) for some fixed
$0<\beta<\pi_{\min}/q-1$. Then we have $\tilde{B}_{0}\leq
4\left(1+\nicefrac{{C}}{{q(1-\beta)}}\right)\max_{z\in\mathcal{Z}}e_{z}(N_{q})$,
where $N_{q}\coloneqq nq\left(\pi_{\min}-q(1+\beta)\right)(1-\beta)$.

Due to the definitions of event $\Omega_{3}$ and the time $t_{0}$, it must be
the case that $N_{z_{0},t_{0}}\geq
N_{z_{0},n}^{(0)}\geq\pi^{*}(z_{0})n-N_{z_{0},n}^{(1)}\geq\left(\pi^{*}(z_{0})-\epsilon/m=-b_{n}/n\right)n$.
Next, we assume that $n$ is large enough, such that the following are
satisfied for some $0<\beta$:

  * •

First, we assume that $n$ is large enough to ensure that
$b_{n}/n\leq\beta\epsilon/m$ for some $0<\beta<m\pi_{\min}/\epsilon-1$, i.e.,

$\displaystyle n\geq\tilde{n_{0}}(\beta)\coloneqq\min\left\\{t\geq
1:\frac{\log
t}{t}\leq\frac{\beta^{2}\epsilon^{2}}{m^{2}}-\frac{1}{2}\log\left(\nicefrac{{m\pi^{2}}}{{3\delta}}\right)\right\\}.$
(22)

This implies that $t_{0}\geq
n\left(\pi^{*}(z_{0})-\epsilon/m(1+\beta)\right)\geq
n\left(\pi_{\min}-\frac{\epsilon(1+\beta)}{m}\right)$.

  * •

Next, we assume that $b_{t_{0}}/t_{0}\leq\beta\epsilon/m$. A sufficient
condition for this is

$\displaystyle
n\left(\pi_{\min}-\frac{\epsilon(1+\beta)}{m}\right)\;\geq\;\tilde{n}_{0}(\beta)\quad\Rightarrow\quad
n\;\geq\;\frac{\tilde{n}_{0}(\beta)}{\pi_{\min}-\nicefrac{{\epsilon(1+\beta)}}{{m}}}.$
(23)

Then, with the notation
$N_{q}=n\left(\pi_{\min}-q(1+\beta)\right)\left(q(1-\beta)\right)$, where
$q=\epsilon/m$, we have the following:

$\tilde{B}_{0}=4\left(1+\frac{C}{q-b_{t_{0}}{t_{0}}}\right)\max_{z\in\mathcal{Z}}e_{z}(N_{z,t_{0}})\leq
4\left(1+\frac{C}{q(1-\beta)}\right)\max_{z\in\mathcal{Z}}e_{z}(N_{q}).$

Now, proceeding in the same way as in Lemma 4 and Lemma 5, we can define the
terms $\tilde{B}_{j}$ for $j\geq 1$ (analogous to the terms $B_{j}$ introduced
in Lemma 4) to show that with probability at least $1-2\delta$, the excess
risk resulting from the $\epsilon$-greedy strategy satisfies:

$\max_{z\in\mathcal{Z}}L(z,f_{\pi_{n}})-M^{*}\leq\sum_{j=0}^{s-1}\tilde{B}_{j}=\mathcal{O}\left(\frac{|\mathcal{Z}|C}{q(1-\beta)}\right)\max_{z\in\mathcal{Z}}e_{z}(N_{q}),$

as required.

###  C.3 Comparison with $\mathcal{A}_{\texttt{opt}}$

The $\epsilon$-greedy strategy differs from $\mathcal{A}_{\texttt{opt}}$ in
two major ways:

  1. 1.

As discussed in Remark 4, the excess risk bound derived in Theorem 1 for
$\mathcal{A}_{\texttt{opt}}$ is always tighter than the corresponding bound
for $\epsilon$-greedy strategy in Theorem 2. In particular, for the family of
classifiers considered in Remark 2, both the algorithms achieve same
convergence rates w.r.t. $n$, but the $\epsilon$-greedy strategy has a larger
leading constant.

  2. 2.

From a practical point of view, the $\epsilon$-greedy strategy is less robust
to the choice of parameter $\epsilon$ as compared to the
$\mathcal{A}_{\texttt{opt}}$ strategy. For instance, as shown in Figure 5,
choosing a large value of $\epsilon$ may result in the mixture distribution
$(\pi_{t})$ not converging to $\pi^{*}$, whereas even with much larger values
of $c_{0}$, the $\pi_{t}$ from $\mathcal{A}_{\texttt{opt}}$ algorithm still
eventually converges to $\pi^{*}$.

Figure 5: This figure shows an instance when the $\epsilon$-greedy strategy is
over-exploratory which results in the empirical mixture distribution $\pi_{t}$
being strictly away from $\pi^{*}$, and thus resulting in $\Omega(1)$ excess
risk even as $n$ goes to infinity. For the $\epsilon$-greedy strategy in this
particular figure, we used $\epsilon=.5$ with $m=2$ and
$\pi_{\min}=\min_{z}\pi^{*}(z)\approx 0.23$. This provides a numerical
demonstration of the statement of Proposition 2. Note that the
$\mathcal{A}_{\texttt{opt}}$ strategy is more resilient to the wrong choice of
the exploration parameter $c_{0}$: in this figure we used $c_{0}=1.0$ (much
larger than the $0.1$ value used in experiments) and the corresponding
$\pi_{n}(u)$ for $\mathcal{A}_{\texttt{opt}}$ still eventually converges
towards $\pi^{*}(u)$.

##  Appendix D Proof of Lower Bound (Proposition 3)

We consider two problem instances in the class of problems, $\mathcal{Q}$,
used in the statement of Proposition 3, denoted by $Q_{\mu}$ and $Q_{\gamma}$.
The instance $Q_{\mu}$ has the synthetic model with mean vectors
$\mu_{0u}=(-r,r),\mu_{1u}=(r,-r),\mu_{0v}=(-r^{\prime},-r^{\prime})$ and
$\mu_{1v}=(r^{\prime},r^{\prime})$ for some $r^{\prime}>r>0$, and $Q_{\gamma}$
has the mean vectors
$\mu_{0u}=(-r^{\prime},r^{\prime}),\mu_{1u}=(r^{\prime},-r^{\prime}),\mu_{0v}=(-r,-r)$
and $\mu_{1v}=(r,r)$. For both these problem instances, implementing an
adaptive sampling algorithm $\mathcal{A}$ with a budget $n$ induces a
probability measure on the space
$(\mathcal{X}\times\mathcal{Y}\times\mathcal{Z})^{n}$. We use
$\mathbb{P}_{\mu}$ and $\mathbb{P}_{\gamma}$ (resp. $\mathbb{E}_{\mu}$ and
$\mathbb{E}_{\gamma}$) to denote the probability measures (resp. expectations)
for the problem instances $Q_{\mu}$ and $Q_{\gamma}$ respectively.

Then we have the following KL-divergence decomposition result.

######  Lemma 8.

For any event $E$, we have the following:

$\frac{n(r^{\prime}-r)^{2}}{2}=D_{KL}\left(\mathbb{P}_{\mu},\mathbb{P}_{\gamma}\right)\geq
d_{KL}\left(\mathbb{P}_{\mu}(E),\,\mathbb{P}_{\gamma}(E)\right)\geq
2\left(\mathbb{P}_{\mu}(E)-\mathbb{P}_{\gamma}(E)\right)^{2}.$

In the above display, $d_{KL}(a_{1},a_{2})$ for $a_{1},a_{2}\in[0,1]$ denotes
the KL-divergence between two Bernoulli random variables with parameters
$a_{1}$ and $a_{2}$ respectively.

As a consequence of the above result, we have
$|\mathbb{P}_{\mu}(E)-\mathbb{P}_{\gamma}(E)|\leq(r^{\prime}-r)\sqrt{n/2}$.

###### Proof.

The first inequality is a direct consequence of the data-processing inequality
for KL-divergence (Polyanskiy and Wu,, 2015, Corollary 2.2), while the second
inequality follows from an application Pinsker’s inequality (Polyanskiy and
Wu,, 2015, Theorem 6.5).

We now show the derivation of the first equality in the statement. Let
$\mathcal{H}_{t}$ denote the history at the beginning of round $t$, i.e.,
$\mathcal{H}_{t}=\left(Z_{1},X_{1},Y_{1},\ldots,Z_{t-1},X_{t-1},Y_{t-1}\right)$.
Then for any sequence of
$\left(Z_{1},X_{1},Y_{1},\ldots,Z_{n},X_{n},Y_{n}\right)$, we have

$\displaystyle\mathbb{P}_{\mu}\left(Z_{1},\ldots,Y_{n}\right)=\prod_{t=1}^{n}\mathcal{A}\left(Z_{t}|\mathcal{H}_{t-1}\right)Q_{\mu}\left(Y_{t}|Z_{t}\right)Q_{\mu}\left(X_{t}|Y_{t},Z_{t}\right).$

We can write a similar expression for $\mathbb{P}_{\gamma}$ as well. Now,
proceeding as in (Lattimore and Szepesvári,, 2020, Lemma 15.1), we get the
following divergence decomposition result

$\displaystyle D_{KL}\left(\mathbb{P}_{\mu},\mathbb{P}_{\gamma}\right)$
$\displaystyle=\mathbb{E}_{\mu}\left[N_{u,n}\right]D_{KL}\left(Q_{\mu}(\cdot,\cdot|Z=u),Q_{\gamma}(\cdot,\cdot|Z=u)\right)+\mathbb{E}_{\mu}\left[N_{v,n}\right]D_{KL}\left(Q_{\mu}(\cdot,\cdot|Z=v),Q_{\gamma}(\cdot,\cdot|Z=v)\right)$
$\displaystyle=\left(\mathbb{E}_{\mu}\left[N_{u,n}\right]+\mathbb{E}_{\mu}\left[N_{v,n}\right]\right)\frac{(r^{\prime}-r)^{2}}{2}=\frac{n(r^{\prime}-r)^{2}}{2},$

where the last equality uses the expression for KL-divergence between two
multi-variate Gaussian distributions.

∎

######  Lemma 9.

Suppose $\pi_{n}$ denotes the mixture distribution returned by the algorithm
$\mathcal{A}$ after $n$ rounds when applied to a problem
$Q\in\\{Q_{\mu},Q_{\gamma}\\}$. Introduce the event $E=\\{\pi_{n}(u)>0.5\\}$
and assume that $r^{\prime}<2r$. Then we have the following:

$\mathbb{E}_{\mu}\left[\mathcal{R}_{n}(\mathcal{A})\right]\geq\frac{c_{r}}{2\sqrt{2}}(r^{\prime}-r)\mathbb{P}_{\mu}(E^{c})\quad\text{and}\quad\mathbb{E}_{\gamma}\left[\mathcal{R}_{n}(\mathcal{A})\right]\geq\frac{c_{r}}{2\sqrt{2}}(r^{\prime}-r)\mathbb{P}_{\gamma}(E),$

where
$c_{r}\coloneqq\min_{x\in[r,2r]}\left|\Phi^{\prime}\left(\frac{x}{\sqrt{2}}\right)\right|$
and $\Phi(\cdot)$ denotes the cumulative distribution function (cdf) of a
standard Normal random variable.

###### Proof.

We present the details only for the first inequality as the second inequality
follows in an entirely analogous manner by replacing $E^{c}$ with $E$.

$\displaystyle\mathbb{E}_{\mu}\left[\mathcal{R}_{n}(\mathcal{A})\right]$
$\displaystyle=\mathbb{E}_{\mu}\left[\mathcal{R}_{n}(\mathcal{A})\mathbbm{1}_{\\{E\\}}\right]+\mathbb{E}_{\mu}\left[\mathcal{R}_{n}(\mathcal{A})\mathbbm{1}_{\\{E^{c}\\}}\right]$
$\displaystyle\geq\mathbb{E}_{\mu}\left[\mathcal{R}_{n}(\mathcal{A})\mathbbm{1}_{\\{E^{c}\\}}\right]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}\left(\frac{\Phi(r/\sqrt{2})-\Phi(r^{\prime}/\sqrt{2})}{2}\right)\mathbb{P}_{\mu}(E^{c})$
$\displaystyle\geq\min_{x\in[r,2r]}\left|\Phi(x/\sqrt{2})\right|\left(\frac{r^{\prime}-r}{2\sqrt{2}}\right)\mathbb{P}_{\mu}\left(E^{c}\right)$
$\displaystyle=\frac{c_{r}}{2\sqrt{2}}(r^{\prime}-r)\mathbb{P}_{\mu}\left(E^{c}\right).$

The key observation in the proof which relies on the choice of $\mathcal{F}$
as the set of all linear classifiers, is in step (a) above. This step uses the
fact that under the event $E^{c}$, when $\pi_{n}(u)\leq 0.5$, the minimax loss
must be at least greater than
$\frac{\Phi(r/\sqrt{2})-\Phi(r^{\prime}/\sqrt{2})}{2}$. Here $\Phi(\cdot)$
denotes the cdf of the standard normal random variable. ∎

The final result now follows by combining the results of Lemma 8 and Lemma 9.
In particular, we have the following:

$\displaystyle\max_{Q\in\mathcal{Q}}\mathbb{E}_{Q}\left[\mathcal{R}_{n}\left(\mathcal{A}\right)\right]\geq\max_{Q\in\\{Q_{\mu},Q_{\gamma}\\}}\mathbb{E}_{Q}[\mathcal{R}_{n}\left(\mathcal{A}\right)]$
$\displaystyle\stackrel{{\scriptstyle\text{(a)}}}{{\geq}}\frac{1}{2}\left(\mathbb{E}_{\mu}\left[\mathcal{R}_{n}\left(\mathcal{A}\right)\right]+\mathbb{E}_{\gamma}\left[\mathcal{R}_{n}\left(\mathcal{A}\right)\right]\right)$
$\displaystyle\stackrel{{\scriptstyle\text{(b)}}}{{\geq}}\frac{c_{r}}{4\sqrt{2}}(r^{\prime}-r)\left(\mathbb{P}_{\mu}\left(E^{c}\right)+\mathbb{P}_{\gamma}\left(E\right)\right)$
$\displaystyle\stackrel{{\scriptstyle\text{(c)}}}{{\geq}}\frac{c_{r}}{4\sqrt{2}}(r^{\prime}-r)\left(1-\left\lvert\mathbb{P}_{\mu}\left(E\right)-\mathbb{P}_{\gamma}\left(E\right)\right\rvert\right)$
$\displaystyle\stackrel{{\scriptstyle\text{(d)}}}{{\geq}}\frac{c_{r}}{4\sqrt{2}}(r^{\prime}-r)\left(1-(r^{\prime}-r)\sqrt{\frac{n}{2}}\,\right)$
$\displaystyle\stackrel{{\scriptstyle\text{(e)}}}{{\geq}}\frac{c_{r}}{16\sqrt{n}}.$

In the above display:
(a) uses the fact that average is smaller than maximum,
(b) lower bounds
$\mathbb{E}_{\mu}\left[\mathcal{R}_{n}\left(\mathcal{A}\right)\right]$ and
$\mathbb{E}_{\gamma}\left[\mathcal{R}_{n}\left(\mathcal{A}\right)\right]$
using the result of Lemma 9,
(c) uses the fact that
$\mathbb{P}_{\mu}(E^{c})+\mathbb{P}_{\gamma}(E)=1-\mathbb{P}_{\mu}(E^{c})+\mathbb{P}_{\gamma}(E)\geq
1-|\mathbb{P}_{\mu}(E^{c})-\mathbb{P}_{\gamma}(E)|$,
(d) follows by using the bound
$|\mathbb{P}_{\mu}(E^{c})-\mathbb{P}_{\gamma}(E)|\leq(r^{\prime}-r)\sqrt{n/2}$
derived in Lemma 8, and finally,
(e) follows by setting $r^{\prime}=r+1/\sqrt{2n}$.

##  Appendix E Details of Experiments

###  E.1 Synthetic Dataset

_Data._ We used the two synthetic models introduced in Sec. 2.1 for generating
the training set.

_Classifier._ We set $\mathcal{F}$ to the set of logistic regression
classifiers. More specifically we used the LogisticRegression implementation
in the scikit-learn package.

_Details of experiment._ For each trial, we set $n=1000$, and tracked the
$\pi_{t}(u)$ values for the three algorithms. We repeated the experiment for
$100$ trials and plot the resulting mean $\pi_{t}(u)$ values in the curves,
along with the one-standard-deviation regions.

###  E.2 Real Datasets

We used the following datasets:

  * •

_UTKFace_ dataset. This dataset consists of large number of face images with
annotations of age, gender and ethnicity. We used $Y=\\{\texttt{Male,
Female}\\}$ and set $\mathcal{Z}=\\{\texttt{White, Black, Asian, Indian,
Other}\\}$.

  * •

_MNIST_ dataset. This dataset consists of images the 10 digits from $0$ to
$9$. We paired them off to create five binary classification tasks. The five
resulting tasks were to distinguish between the following pairs:
$\\{(0,6),(2,4),(1,3),(5,8),(7,9)\\}$. Thus, in this case,
$Z=\\{z_{1},\ldots,z_{5}\\}$ where $z_{1}$ corresponds to the task of
distinguishing between $0$ and $6$; $z_{2}$ corresponds to the task of
distinguishing between $2$ and $4$; and so on.

  * •

_FashionMNIST_ dataset. This dataset consists of $10$ different classes, which
were paired off to get five different binary classification tasks: {(Tshirt,
Shirt), (Trousers, Dress), (Pullover, Coat), (Sandals, Bag), (Sneakers,
AnkleBoots)}

  * •

_Cifar10_ dataset. This dataset also consists of $10$ different classes, which
were paired off as follows: { (airplane, ship), (automobile, truck), (bird,
cat), (deer, dog), (frog, horse)}.

_Data Transforms and Augmentation._ We used the following pre-processing
operations for the different datasets:

  * •

_UTKFace._ For this dataset, we first resized the dataset to size $3\times
50\times 50$ from the original $3\times 200\times 200$. Then we also applied
random horizontal flip with probability $0.5$. For training we used the images
from the file UTKFace.tar.gz, while for testing we used the file
crop_part1.tar.gz. (Both of these files can be found at this link shared by
the owner of the dataset).

  * •

_MNIST & FashionMNIST._ We only employed the normalization transform in these
two cases, and used the default training and test splits.

  * •

_Cifar10._ We employed a random crop transform (to size $3\times 28\times 28$
with padding $1$), a random horizontal flip transform (with probability $0.5$)
and a normalization transform, and used the default training and test split.

_Details of CNN._ We implemented the CNN using Pytorch. The CNN used for all
the datasets had the same architecture consisting of:

  * •

First Conv2d layer with $32$ output channels, kernel size $3$, padding = $1$,
followed by ReLU followed by a MaxPool2d layer with kernel size $2$ and stride
$2$.

  * •

Second Conv2d layer with $64$ output channels, kernel size $3$, followed by
ReLU followed by MaxPool2d with kernel size $2$.

  * •

The two Conv2d layers were followed by $3$ fully connected layers with output
sizes $600$, $120$ and $2$ respectively.

  * •

For training the neural network we used the Adam optimizer with
$\texttt{lr}=0.001$.

(a) (b)

Figure 6: The figure on the left plots the minimum test accuracy over $5$
tasks for the MNIST dataset. The figure on the right shows the minimum test
accuracy over the five different attributes for the UTKFace dataset.