Toward a General Theory of Online Selective Sampling: Trading Off Mistakes and Queries

Steve Hanneke, Liu YangAISTATS 2021 · OpenReview

Abstract

While the literature on the theory of pool-based active learning has seen much progress in the past 15 years, and is now fairly mature, much less is known about its cousin problem: online selective sampling. In the stochastic online learning setting, there is a stream of iid data, and the learner is required to predict a label for each instance, and we are interested in the rate of growth of the number of mistakes the learner makes. In the selective sampling variant of this problem, after each prediction, the learner can optionally request to observe the true classification of the point. This introduces a trade-off between the number of these queries and the number of mistakes as a function of the number T of samples in the sequence. This work explores various properties of the optimal trade-off curve, both abstractly (for general VC classes), and more-concretely for several constructed examples that expose important properties of the trade-off.

Introduction

In standard online learning, a model predicts a label for an incoming data point and immediately receives feedback. However, in many real-world scenarios, obtaining the ground truth label is costly. Online selective sampling addresses this by allowing the learner to choose whether to query the label after making a prediction. This necessitates a careful balance: querying more frequently reduces mistakes but increases costs, while querying less frequently saves resources at the risk of higher error rates. This paper establishes a foundational theory to characterize the optimal trade-off curve between mistakes and queries in this online setting.

Methodological Framework

The authors analyze selective sampling strategies across three levels of complexity, moving from general to specific assumptions about the data.

Distribution-Free Strategies

When the data distribution is unknown, the learner must rely on general disagreement-based strategies. The Cohn-Atlas-Ladner (CAL) algorithm serves as the primary baseline. CAL only queries a label if there is disagreement among the hypotheses in the current version space $V_{t-1}$ regarding the label of the current instance $X_t$.

Algorithm CAL: A baseline selective sampling approach based on hypothesis disagreement.

The paper proves that "trivial modifications" of CAL—such as querying every $k$-th point or following a fixed schedule—are nearly minimax optimal in the distribution-free setting.

Distribution-Dependent Strategies

If the data distribution is known, more sophisticated "picky" algorithms can be employed. The authors introduce PickyActive, which refines the querying criteria. Instead of querying every point of disagreement, PickyActive waits for points that are highly informative—those that would significantly prune the hypothesis space.

Algorithm PickyActive: A distribution-dependent strategy that queries labels only for highly informative points.

To handle the online nature of informativeness, the authors adapt a strategy similar to the "Secretary Problem": they observe a batch of points to establish a baseline for informativeness and then query the first point in the subsequent batch that exceeds this threshold.

Target-Dependent Strategies

For specific hypothesis classes like the union of $k$ intervals, the authors propose UIntActivek. This approach exploits both the distribution and the structure of the target function to achieve simultaneous low mistake and query counts.

Key Insights and Results

The theoretical analysis yields several critical findings:

  • The Power of Being Picky: In distribution-dependent scenarios, picky algorithms can achieve "super-linear" improvements over trivial strategies. For example, the authors demonstrate a case where a picky algorithm achieves $O(\log^2 T)$ queries and $O(\sqrt{T \log T})$ mistakes, significantly outperforming any trivial CAL modification.
  • Informativeness Thresholds: Effective online sampling requires querying not just based on uncertainty, but on the potential of a point to reduce future uncertainty relative to the average point in the stream.
  • Unions of Intervals: For the class of $k$-intervals, it is possible to achieve $O(\log T)$ mistakes and $O(\log T)$ queries simultaneously, representing an ideal "best of both worlds" scenario.

Discussion and Future Work

While this work provides a robust framework, it operates under the "realizability" assumption, where a perfect hypothesis exists within the class. Future research is needed to extend these theories to agnostic settings involving noise. Additionally, the bounds for general algorithms like PickySplitting remain coarse and require refinement into more concise complexity measures. Finally, the "Open Problem" of achieving $O(\log T)$ mistakes with $o(T)$ queries for all finite VC classes remains a significant challenge for the field.

Summary updated

Abstract

While the literature on the theory of pool-based active learning has seen much progress in the past 15 years, and is now fairly mature, much less is known about its cousin problem: online selective sampling. In the stochastic online learning setting, there is a stream of iid data, and the learner is required to predict a label for each instance, and we are interested in the rate of growth of the number of mistakes the learner makes. In the selective sampling variant of this problem, after each prediction, the learner can optionally request to observe the true classification of the point. This introduces a trade-off between the number of these queries and the number of mistakes as a function of the number T of samples in the sequence. This work explores various properties of the optimal trade-off curve, both abstractly (for general VC classes), and more-concretely for several constructed examples that expose important properties of the trade-off.
BibTeX
@inproceedings{hanneke2021toward,
  author = {Steve Hanneke and Liu Yang},
  title = {{Toward a General Theory of Online Selective Sampling: Trading Off Mistakes and Queries}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=cVFCvFDgOd},
}
Figure