Abstract
This paper investigates the "online selective classification" paradigm, where a learner can choose to abstain from making a prediction to query an external expert. A critical constraint in this setting is that the model only receives the ground truth label when it chooses to abstain. We establish a fundamental, tight trade-off between the number of mistakes and the number of "excess" abstentions. We introduce the Versioned Uniform Explorer (VUE) family of algorithms, which achieve optimal regret bounds in both adversarial and stochastic environments.
Introduction
In many safety-critical or resource-constrained applications, such as medical diagnostics or IoT sensors, a local model must decide whether to provide a prediction or defer to a more capable but expensive resource (e.g., a human expert or a cloud server). This is known as selective classification.
Existing theoretical frameworks often overlook two practical realities:
- Limited Feedback: Ground truth labels are typically only available when the expensive resource is invoked.
- Non-Realisability: In noisy environments, no single classifier may be perfect, making permanent abstention a necessity for certain instances.
This work addresses these gaps by formalizing the trade-off between Mistakes (incorrect predictions) and Excess Abstentions (unnecessary queries to the expert).
Methodology
The proposed approach centers on the concept of a Version Space—the set of candidate classifiers that have not yet been invalidated by observed feedback.
VUE (Versioned Uniform Explorer)
VUE is designed for adversarial settings. It employs an exploratory mechanism: at each step, it tosses a biased coin with probability $p$.
- Heads: The model abstains to receive feedback, using the label to prune any classifier in the version space that would have predicted incorrectly.
- Tails: The model predicts using the current version space.
VUE-PROD and MIXED-LOSS-PROD
For stochastic environments, VUE-PROD (Algorithm 2) utilizes a weighted approach to maintain the version space. This improves the regret's dependence on the number of candidate classifiers $N$ from polynomial to logarithmic. MIXED-LOSS-PROD extends these ideas to adversarial settings using a weighted loss function to balance mistake and abstention costs.
Theoretical Analysis: The Pareto Frontier
A central contribution of this research is the characterization of the fundamental trade-off between mistakes and abstentions. The authors prove that for any $\mu \in (0, 1]$, an algorithm making at most $O(T^\mu)$ mistakes must incur at least $\tilde{O}(T^{1-\mu})$ excess abstentions.
This trade-off is "tight," meaning the VUE algorithm's performance sits on the boundary of what is mathematically possible. The analysis relies on a novel Adversarial Law of Large Numbers (ALLN), which ensures that random sampling of feedback is sufficient to eliminate mistake-prone classifiers at an optimal rate.
Experimental Evaluation
The algorithms were tested on two datasets:
- CIFAR-10: Simulating a scenario where a local model queries a high-accuracy expert model.
- GAS Sensor Array: A resource-constrained task where the local learner has access to a subset of sensors, while the expert has access to the full array.
In both cases, the "Price of Being Online"—the performance gap between the online learner and an offline optimal strategy—was shown to grow sublinearly over time, confirming that the models effectively learn optimal abstention strategies.
Conclusion
This work provides a rigorous foundation for online selective classification under limited feedback. While the current theory handles finite classifier sets, future research will focus on extending these bounds to infinite hypothesis classes (e.g., via VC dimension) and further formalizing "agnostic" settings where no perfect classifier exists in the hypothesis set.
Summary updated