Agnostic Multi-Group Active Learning
Nick Rittler Kamalika Chaudhuri
Inspired by the problem of improving classification accuracy on rare or hard
subsets of a population, there has been recent interest in models of learning
where the goal is to generalize to a collection of distributions, each
representing a ``group''. We consider a variant of this problem from the
perspective of active learning, where the learner is endowed with the power to
decide which examples are labeled from each distribution in the collection, and
the goal is to minimize the number of label queries while maintaining
PAC-learning guarantees. Our main challenge is that standard active learning
techniques such as disagreement-based active learning do not directly apply to
the multi-group learning objective. We modify existing algorithms to provide a
consistent active learning algorithm for an agnostic formulation of multi-group
learning, which given a collection of $G$ distributions and a hypothesis class
$\mathcal{H}$ with VC-dimension $d$, outputs an $\epsilon$-optimal hypothesis
using $\tilde{O}\left( (\nu^2/\epsilon^2+1) G d \theta_{\mathcal{G}}^2
\log^2(1/\epsilon) + G\log(1/\epsilon)/\epsilon^2 \right)$ label queries, where
$\theta_{\mathcal{G}}$ is the worst-case disagreement coefficient over the
collection. Roughly speaking, this guarantee improves upon the label complexity
of standard multi-group learning in regimes where disagreement-based active
learning algorithms may be expected to succeed, and the number of groups is not
too large. We also consider the special case where each distribution in the
collection is individually realizable with respect to $\mathcal{H}$, and
demonstrate $\tilde{O}\left( G d \theta_{\mathcal{G}} \log(1/\epsilon) \right)$
label queries are sufficient for learning in this case. We further give an
approximation result for the full agnostic case inspired by the group
realizable strategy.