Fast Rates for Online Prediction with Abstention
In the setting of sequential prediction of individual $\{0, 1\}$-sequences with expert advice, we show that by allowing the learner to abstain from the prediction by paying a cost marginally smaller than $\frac 12$ (say, $0.49$), it is possible to achieve expected regret bounds that are independent of the time horizon $T$. We exactly characterize the dependence on the abstention cost $c$ and the number of experts $N$ by providing matching upper and lower bounds of order $\frac{\log N}{1-2c}$, which is to be contrasted with the best possible rate of $\sqrt{T\log N}$ that is available without the option to abstain. We also discuss various extensions of our model, including a setting where the sequence of abstention costs can change arbitrarily over time, where we show regret bounds interpolating between the slow and the fast rates mentioned above, under some natural assumptions on the sequence of abstention costs.
Code (0)
등록된 구현이 없습니다.
Tasks
PredictionSimilar Papers 제목 키워드 기반
Classification with abstention but without disparities
Classification with abstention has gained a lot of attention in recent years as it allows to incorporate human decision-makers in the process. Yet, abstention can potentially amplify disparities and lead to discriminator…
ClassificationFairnessGeneral ClassificationMulti-Armed Bandits with Abstention
We introduce a novel extension of the canonical multi-armed bandit problem that incorporates an additional strategic element: abstention. In this enhanced framework, the agent is not only tasked with selecting an arm at …
Decision MakingMulti-Armed BanditsStructured Output Learning with Abstention: Application to Accurate Opinion Prediction
Motivated by Supervised Opinion Analysis, we propose a novel framework devoted to Structured Output Learning with Abstention (SOLA). The structure prediction model is able to abstain from predicting some labels in the st…
Opinion MiningPredictionSentencePolicy Learning with Abstention
Policy learning algorithms are widely used in areas such as personalized medicine and advertising to develop individualized treatment regimes. However, most methods force a decision even when predictions are uncertain, w…
Controlled abstention neural networks for identifying skillful predictions for regression problems
The earth system is exceedingly complex and often chaotic in nature, making prediction incredibly challenging: we cannot expect to make perfect predictions all of the time. Instead, we look for specific states of the sys…
regression