Online Selective Classification with Limited Feedback
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 \smash{$\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.
Code (1)
Tasks
ClassificationvalidSimilar Papers 제목 키워드 기반
A Regret Perspective on Online Selective Generation
Large language generative models increasingly interact with humans, while their falsified responses raise concerns. To address this hallucination effect, selectively abstaining from answering, called selective generation…
HallucinationLEMMASelective Sampling and Imitation Learning via Online Regression
We consider the problem of Imitation Learning (IL) by actively querying noisy expert for feedback. While imitation learning has been empirically successful, much of prior work assumes access to noiseless expert feedback …
Imitation LearningregressionLearning to Defer in Content Moderation: The Human-AI Interplay
Successful content moderation in online platforms relies on a human-AI collaboration approach. A typical heuristic estimates the expected harmfulness of a post and uses fixed thresholds to decide whether to remove it and…
SchedulingFederated Neuromorphic Learning of Spiking Neural Networks for Low-Power Edge Intelligence
Spiking Neural Networks (SNNs) offer a promising alternative to conventional Artificial Neural Networks (ANNs) for the implementation of on-device low-power online learning and inference. On-device training is, however, …
Federated LearningGeneralization Error Bounds for Learning under Censored Feedback
Generalization error bounds from learning theory provide statistical guarantees on how well an algorithm will perform on previously unseen data. In this paper, we characterize the impacts of data non-IIDness due to censo…
Learning TheoryRecommendation Systems