# Online Selective Classification with Limited Feedback

arXiv: https://arxiv.org/abs/2110.14243 · HTML: https://mlsanity.com/paper/2110.14243/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 49 references that are in the map.
- First posted on arXiv 27 Oct 2021.

## Builds on (most cited first, 11 of 11)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [SelectiveNet: A Deep Neural Network with an Integrated Reject Option](https://mlsanity.com/paper/1901.09192/) (2019)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [Adversarial Laws of Large Numbers and Optimal Regret in Online Classification](https://mlsanity.com/paper/2101.09054/) (2021)
- [Selective Classification via One-Sided Prediction](https://mlsanity.com/paper/2010.07853/) (2020)
- [Online Learning with Abstention](https://mlsanity.com/paper/1703.03478/) (2017)
- [Fast Rates for Online Prediction with Abstention](https://mlsanity.com/paper/2001.10623/) (2020)
- [The Adversarial Robustness of Sampling](https://mlsanity.com/paper/1906.11327/) (2019)
- [Adaptive Classification for Prediction Under a Budget](https://mlsanity.com/paper/1705.10194/) (2017)
- [The Extended Littlestone's Dimension for Learning with Mistakes and Abstentions](https://mlsanity.com/paper/1604.06162/) (2016)

## Built on by (most cited first, 9 of 9)

- [When to Trust the Cheap Check: Weak and Strong Verification for Reasoning](https://mlsanity.com/paper/2602.17633/) (2026)
- [Zero-Shot End-to-End Spoken Language Understanding via Cross-Modal Selective Self-Training](https://mlsanity.com/paper/2305.12793/) (2023)
- [Learning to Abstain From Uninformative Data](https://mlsanity.com/paper/2309.14240/) (2023)
- [Online Learning with Sublinear Best-Action Queries](https://mlsanity.com/paper/2407.16355/) (2024)
- [Online Prediction with Limited Selectivity](https://mlsanity.com/paper/2508.09592/) (2025)
- [The Good, the Bad, and the Sampled: a No-Regret Approach to Safe Online Classification](https://mlsanity.com/paper/2510.01020/) (2025)
- [Discriminative Feature Feedback with General Teacher Classes](https://mlsanity.com/paper/2510.07245/) (2025)
- [Online Convex Optimization with Sublinear Noisy Probes](https://mlsanity.com/paper/2606.14640/) (2026)
- [Online Verification of Language Model Responses Under Cost Constraints](https://mlsanity.com/paper/2610.02632/) (2026)

## Abstract (arXiv)

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 μ ∈ (0,1], that make most Tμ mistakes while incurring smashtildeO(T1-μ) excess abstention against adaptive adversaries. We further show that this dependence on T is tight, and provide illustrative experiments on realistic datasets.