Fast Rates in Pool-Based Batch Active Learning
  We consider a batch active learning scenario where the learner adaptively
issues batches of points to a labeling oracle. Sampling labels in batches is
highly desirable in practice due to the smaller number of interactive rounds
with the labeling oracle (often human beings). However, batch active learning
typically pays the price of a reduced adaptivity, leading to suboptimal
results. In this paper we propose a solution which requires a careful trade off
between the informativeness of the queried points and their diversity. We
theoretically investigate batch active learning in the practically relevant
scenario where the unlabeled pool of data is available beforehand ({\em
pool-based} active learning). We analyze a novel stage-wise greedy algorithm
and show that, as a function of the label complexity, the excess risk of this
algorithm matches the known minimax rates in standard statistical learning
settings. Our results also exhibit a mild dependence on the batch size. These
are the first theoretical results that employ careful trade offs between
informativeness and diversity to rigorously quantify the statistical
performance of batch active learning in the pool-based scenario.
