Fast Rates for Online Prediction with Abstention
This work addresses the challenge of improving regret bounds in online learning for scenarios where abstention is permissible, offering a significant speedup over traditional methods.
The paper tackles the problem of sequential prediction with expert advice by allowing the learner to abstain at a cost, achieving expected regret bounds independent of the time horizon T. It provides matching upper and lower bounds of order (log N)/(1-2c), contrasting with the sqrt(T log N) rate without 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.