The Extended Littlestone's Dimension for Learning with Mistakes and Abstentions
This addresses optimality gaps in online learning with abstentions, offering theoretical insights for scenarios where learners can avoid predictions, but it is incremental as it builds on prior work in this niche area.
The paper tackles the problem of online classification with an abstention option, introducing the Extended Littlestone's Dimension to quantify abstentions needed for a given mistake bound and providing bounds for the non-realizable case.
This paper studies classification with an abstention option in the online setting. In this setting, examples arrive sequentially, the learner is given a hypothesis class $\mathcal H$, and the goal of the learner is to either predict a label on each example or abstain, while ensuring that it does not make more than a pre-specified number of mistakes when it does predict a label. Previous work on this problem has left open two main challenges. First, not much is known about the optimality of algorithms, and in particular, about what an optimal algorithmic strategy is for any individual hypothesis class. Second, while the realizable case has been studied, the more realistic non-realizable scenario is not well-understood. In this paper, we address both challenges. First, we provide a novel measure, called the Extended Littlestone's Dimension, which captures the number of abstentions needed to ensure a certain number of mistakes. Second, we explore the non-realizable case, and provide upper and lower bounds on the number of abstentions required by an algorithm to guarantee a specified number of mistakes.