  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.
