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.
The Challenge of Hard Examples
Active Learning (AL) promises high accuracy with minimal labeling by strategically selecting data points. However, AL often hits a "statistical wall" in general settings, performing no better than passive learning. This bottleneck is caused by "hard" examples—data points near the decision boundary where the true label is ambiguous. Resolving these points requires a massive number of samples, often leading to "noise-seeking" behavior where algorithms waste their budget on regions that are essentially a coin flip.
Learning with abstention offers a workaround: if a model can choose to abstain from a prediction (incurring a small, fixed penalty), it can ignore these impossible boundary cases and focus on informative regions. While theoretically sound, previous approaches relied on NP-Hard optimization problems, making them impractical for real-world use.
Methodology: Efficient Active Learning
The authors introduce Algorithm 1: Efficient Active Learning with Abstention, the first computationally efficient algorithm in this space. Its primary innovation is replacing intractable optimization oracles with a Regression Oracle (weighted square loss), which is widely used and computationally feasible.
Key components of the algorithm include:
- Epoch-based Learning: The algorithm operates in stages of increasing length to refine its model.
- Confidence Intervals: In each epoch, it maintains an "active set" of candidate functions, calculating Lower Confidence Bounds (LCB) and Upper Confidence Bounds (UCB) for class probabilities.
- Proper Abstention Rule: The model only abstains if it is "certainly" optimal to do so—specifically, when the true probability is very close to 0.5.
- Selective Querying: Labels are requested only if the current confidence interval is uncertain (contains 0.5) and the model has not yet decided to abstain on that point.
Key Insights and Proper Abstention
A major contribution of this work is the "Proper Abstention" property. This ensures the model only abstains on truly hard cases, preventing it from being "lazy" and abstaining on easy examples just to save labels. By allowing for abstention, the label complexity drops from polynomial ($1/\epsilon^2$) to logarithmic ($polylog(1/\epsilon)$), representing a massive leap in efficiency.
As illustrated in the figure above, the algorithm identifies specific regions where it can confidently predict positive or negative labels, while designating "flexible" or "abstention" regions for ambiguous data points. This spatial partitioning allows the algorithm to avoid the "noise-seeking" traps that defeat traditional uncertainty-based learners.
Key Results
- Computational Efficiency: The algorithm is implementable via standard convex optimization (regression oracles).
- Exponential Savings: The authors prove a label complexity of $O\left(\frac{\theta \cdot Pdim(\mathcal{F})}{\gamma^2} \cdot polylog(\frac{1}{\epsilon})\right)$, where $\theta$ is the disagreement coefficient and $Pdim$ is the Pseudo-dimension.
- Constant Complexity: Under Massart noise conditions, the algorithm can achieve a target error $\epsilon$ with a number of labels that is independent of $\epsilon$.
- Minimax Optimality: The algorithm recovers the best possible theoretical rates in standard settings when forced to make a prediction.
Limitations and Future Work
While the paper provides an extension for misspecified models (Algorithm 3), the resulting error bound includes an additive term related to the level of misspecification. Achieving computational efficiency while handling general approximation error remains an open challenge. Additionally, the approach's efficiency depends on the underlying regression oracle; in high-dimensional, non-convex settings like deep learning, the oracle itself may become a bottleneck. Future research will likely explore the relationship between computational efficiency and learning with general, non-bounded approximation errors.
Summary updated