Fast Rates in Pool-Based Batch Active Learning
This work addresses the practical challenge of efficient labeling in machine learning for applications involving human oracles, providing theoretical guarantees for batch active learning, though it is incremental as it builds on existing minimax rate frameworks.
The paper tackles the problem of batch active learning in pool-based scenarios, where issuing batches of points reduces interactive rounds but can lead to suboptimal results due to reduced adaptivity. The authors propose a stage-wise greedy algorithm that balances informativeness and diversity, achieving excess risk matching known minimax rates in standard statistical learning settings with mild dependence on batch size.
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.