Online Selective Classification with Limited Feedback

Aditya Gangrade, Anil Kag, Ashok Cutkosky, Venkatesh Saligrama

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:

  1. Limited Feedback: Ground truth labels are typically only available when the expensive resource is invoked.
  2. 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.

Algorithm 2: VUE-PROD, designed for stochastic environments.

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.

The fundamental trade-off between mistakes ($T^\mu$) and excess abstentions ($T^\alpha$).

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:

  1. CIFAR-10: Simulating a scenario where a local model queries a high-accuracy expert model.
  2. 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

Abstract

Motivated by applications to resource-limited and safety-critical domains, we study selective classification in the online learning model, wherein a predictor may abstain from classifying an instance. For example, this may model an adaptive decision to invoke more resources on this instance. Two salient aspects of the setting we consider are that the data may be non-realisable, due to which abstention may be a valid long-term action, and that feedback is only received when the learner abstains, which models the fact that reliable labels are only available when the resource intensive processing is invoked. Within this framework, we explore strategies that make few mistakes, while not abstaining too many times more than the best-in-hindsight error-free classifier from a given class. That is, the one that makes no mistakes, while abstaining the fewest number of times. We construct simple versioning-based schemes for any $\mu \in (0,1],$ that make most $T^\mu$ mistakes while incurring $\tilde{O}(T^{1-\mu})$ excess abstention against adaptive adversaries. We further show that this dependence on $T$ is tight, and provide illustrative experiments on realistic datasets.
BibTeX
@inproceedings{gangrade2021online,
  author = {Aditya Gangrade and Anil Kag and Ashok Cutkosky and Venkatesh Saligrama},
  title = {{Online Selective Classification with Limited Feedback}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=cCQAzuT5q4},
}
Figure