Efficient Active Learning with Abstention

Yinglun Zhu, Robert Nowak

Introduction

Active learning (AL) promises to train accurate classifiers using a fraction of the labeled data required by passive learning. However, fundamental statistical lower bounds show that in general "noisy" settings, AL struggles to significantly outperform passive learning. The bottleneck lies in ambiguous data points near the decision boundary. Distinguishing between a 51% and 49% probability of a positive label requires massive amounts of data.

This paper asks a practical question: Do we really need the classifier to be perfect on these ambiguous points? In high-stakes fields like medical imaging, it is often better for an AI to admit uncertainty and defer to a human expert. By allowing the model to abstain from predicting on "hard" examples—a concept formalized as learning with abstention or Chow's error—the authors bypass traditional statistical barriers, achieving exponential savings in label complexity without requiring restrictive low-noise assumptions.

The Core Innovation

Previous theoretical work demonstrated that abstention could yield exponential savings in label complexity. Unfortunately, the proposed algorithms relied on Empirical Risk Minimization (ERM), rendering them computationally NP-Hard. This paper introduces the first computationally efficient active learning algorithm with abstention, bridging the gap between theoretical promise and practical feasibility.

Methodology: Epochs, Confidence, and Proper Abstention

The proposed algorithm shifts away from intractable ERM, utilizing a weighted square-loss regression oracle that allows it to run in polynomial time. The process relies on several key mechanisms:

  • Epoch-based Version Space: The algorithm operates in stages (epochs), maintaining a set of "surviving" candidate functions that remain consistent with the labels seen so far.
  • Confidence Intervals: For any new data point, the algorithm calculates a Lower Confidence Bound (LCB) and Upper Confidence Bound (UCB) based on the surviving functions.
  • The Abstention Rule: If the entire confidence interval $[LCB, UCB]$ falls within a narrow "uncertainty zone" around the 50/50 mark (defined by a parameter $\gamma$), the algorithm chooses to abstain and does not request a label.

A critical theoretical contribution is proper abstention. The algorithm is mathematically guaranteed to only abstain when it is the optimal choice under Chow's error, preventing it from wastefully "giving up" on easy examples.

Key Results and Theoretical Breakthroughs

As a purely theoretical paper, the authors provide rigorous mathematical proofs and complexity analyses to support several major breakthroughs:

  • Exponential Label Savings: By optimizing for Chow's error (where abstaining costs slightly less than a random guess), the algorithm achieves $O(\text{polylog}(1/\epsilon))$ label complexity. This is an exponential improvement over the $O(1/\epsilon^2)$ required by standard active learning.
  • Avoiding "Noise-Seeking" Traps: Standard AL often wastes its label budget on essentially random coin-flip examples. This algorithm identifies these noisy regions and abstains, focusing its budget where clear decisions can actually be made.
  • Constant Label Complexity: Under specific conditions like Massart noise, the required number of labels becomes constant, meaning it does not increase even as the target accuracy approaches perfection ($\epsilon \to 0$).
  • Minimax Optimality & Robustness: If forced to convert abstentions into random guesses, the algorithm still recovers minimax optimal rates for standard classification. Furthermore, it includes extensions to handle model misspecification, maintaining performance even if the "true" relationship isn't perfectly captured by the chosen set of functions.

Limitations and Future Directions

While computationally efficient in a complexity-theory sense, real-world performance and hyperparameter tuning (especially the abstention parameter $\gamma$) require practical testing, as the algorithm still requires multiple calls to a regression oracle per epoch.

Additionally, the current proof for handling model misspecification requires the approximation error to be smaller than the target accuracy ($\epsilon$). Handling larger, more general approximation errors remains a significant open challenge. Finally, the paper assumes a fixed cost for abstention; future work could explore dynamic costs based on the availability or expertise of a human-in-the-loop fallback observer.

Summary updated

Abstract

The goal of active learning is to achieve the same accuracy achievable by passive learning, while using much fewer labels. Exponential savings in terms of label complexity have been proved in very special cases, but fundamental lower bounds show that such improvements are impossible in general. This suggests a need to explore alternative goals for active learning. Learning with abstention is one such alternative. In this setting, the active learning algorithm may abstain from prediction and incur an error that is marginally smaller than random guessing. We develop the first computationally efficient active learning algorithm with abstention. Our algorithm provably achieves $\mathsf{polylog}(\frac{1}{\varepsilon})$ label complexity, without any low noise conditions. Such performance guarantee reduces the label complexity by an exponential factor, relative to passive learning and active learning that is not allowed to abstain. Furthermore, our algorithm is guaranteed to only abstain on hard examples (where the true label distribution is close to a fair coin), a novel property we term \emph{proper abstention} that also leads to a host of other desirable characteristics (e.g., recovering minimax guarantees in the standard setting, and avoiding the undesirable ``noise-seeking'' behavior often seen in active learning). We also provide novel extensions of our algorithm that achieve \emph{constant} label complexity and deal with model misspecification.
BibTeX
@inproceedings{zhu2022efficient,
  author = {Yinglun Zhu and Robert Nowak},
  title = {{Efficient Active Learning with Abstention}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=9tyrKLOhIN},
}
Figure