Understanding the Effects of Batching in Online Active Learning

Kareem Amin, Corinna Cortes, Giulia DeSalvo, Afshin RostamizadehAISTATS 2020 · OpenReview

Abstract

Online active learning (AL) algorithms often assume immediate access to a label once a query has been made. However, due to practical constraints, the labels of these queried examples are generally provided in batches. This paper provides the first rigorous theoretical proof that this "batching" has a surprisingly mild impact, adding only a small, linear cost to the number of labels required while leaving accuracy guarantees virtually unchanged.

Introduction

Active Learning (AL) is a strategy used to train machine learning models with as few labeled examples as possible by intelligently choosing which data points a human should label. Most theoretical research assumes an "online" setting: the algorithm sees a point, decides to label it, gets the label immediately, and updates its model before seeing the next point.

In practice, this is impossible. Labeling usually involves human raters, and it is inefficient to send them one point at a time. Instead, requests are queued into batches. Until now, there was a gap in the theory: does waiting for a batch of labels to return "stale" the model so much that it loses its efficiency or accuracy? This paper addresses this gap by analyzing how batching affects both label complexity (the number of labels required) and generalization (the accuracy of the final model).

Methodology

The authors introduce a generic Batch Online AL Meta-Algorithm. The core idea is to "freeze" the learner's state while a batch of $B$ labels is being collected. During this round, the algorithm makes labeling decisions based on its last updated state. Once $B$ labels are received, it performs a batched update and moves to the next round.

To analyze this, they define a condition called the Time-Decreasing Labeling Rate, assuming that as an active learner improves, its probability of requesting a label naturally decreases. This framework was applied to three classic algorithms: IWAL (Importance Weighted Active Learning), ORIWAL (a region-based version of IWAL), and DHM (a disagreement-based algorithm). These variants were evaluated on six public benchmark datasets: a9a, cod-rna, covtype, HIGGS, mnist, and phishing.

Key Results and Empirical Validation

The most significant finding is that the penalty for batching is purely additive and linear with respect to the batch size ($B$). Specifically, the label complexity increases by roughly $\tilde{O}(B)$. This is essentially the "best-case scenario" because an algorithm must request at least $B$ labels to get any feedback in a batch setting. Furthermore, the theory shows that while the model is "frozen" during a batch, it eventually "catches up" once the batch is processed, ensuring that generalization error does not degrade.

Performance of batched active learning algorithms (B-IWAL, B-ORIWAL, B-DHM) across different batch sizes (1, 16, 64, 256) on the phishing dataset. The top row shows label efficiency, while the bottom row shows classification accuracy.

As shown in Figure 1, empirical tests on the phishing dataset confirm these theoretical insights. The classification accuracy curves (bottom row) for batch sizes ranging from 1 to 256 are nearly identical, demonstrating the robustness of the algorithms. The top row illustrates that the number of labels requested increases with the batch size, but only by a small additive constant, exactly as predicted by the $\tilde{O}(B)$ bound.

Conclusion

This work demonstrates that batching in online active learning is both theoretically sound and practically efficient. The "staleness" introduced by waiting for batches does not fundamentally compromise model performance. Future research directions include exploring batching effects in pool-based settings and investigating methods to enforce diversity within batches to further optimize performance.

Summary updated

Abstract

Online active learning (AL) algorithms often assume immediate access to a label once a query has been made. However, due to practical constraints, the labels of these queried examples are generally...
BibTeX
@inproceedings{amin2020understanding,
  author = {Kareem Amin and Corinna Cortes and Giulia DeSalvo and Afshin Rostamizadeh},
  title = {{Understanding the Effects of Batching in Online Active Learning}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=DkhthwTkFG},
}
Figure