# Disagreement-based Active Learning in Online Settings

arXiv: https://arxiv.org/abs/1904.09056 · HTML: https://mlsanity.com/paper/1904.09056/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Apr 2019.

## Built on by (most cited first, 2 of 2)

- [Active learning for data streams: a survey](https://mlsanity.com/paper/2302.08893/) (2023)
- [Adaptive Selective Sampling for Online Prediction with Experts](https://mlsanity.com/paper/2302.08397/) (2023)

## Abstract (arXiv)

We study online active learning for classifying streaming instances within the framework of statistical learning theory. At each time, the learner either queries the label of the current instance or predicts the label based on past seen examples. The objective is to minimize the number of queries while constraining the number of prediction errors over a horizon of length T. We develop a disagreement-based online learning algorithm for a general hypothesis space and under the Tsybakov noise. We show that the proposed algorithm has a label complexity of O(dT^frac2-2α2-αlog2 T) under a constraint of bounded regret in terms of classification errors, where d is the VC dimension of the hypothesis space and α is the Tsybakov noise parameter. We further establish a matching (up to a poly-logarithmic factor) lower bound, demonstrating the order optimality of the proposed algorithm. We address the tradeoff between label complexity and regret and show that the algorithm can be modified to operate at a different point on the tradeoff curve.