Fast Rates for Online Prediction with Abstention

Gergely Neu, Nikita Zhivotovskiy
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3030-3048, 2020.

Abstract

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 $0.5$ (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

Cite this Paper

BibTeX
@InProceedings{pmlr-v125-neu20a, title = {Fast Rates for Online Prediction with Abstention}, author = {Neu, Gergely and Zhivotovskiy, Nikita}, booktitle = {Proceedings of Thirty Third Conference on Learning Theory}, pages = {3030--3048}, year = {2020}, editor = {Abernethy, Jacob and Agarwal, Shivani}, volume = {125}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v125/neu20a/neu20a.pdf}, url = {https://proceedings.mlr.press/v125/neu20a.html}, abstract = { 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 $0.5$ (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} }
Endnote
%0 Conference Paper %T Fast Rates for Online Prediction with Abstention %A Gergely Neu %A Nikita Zhivotovskiy %B Proceedings of Thirty Third Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Jacob Abernethy %E Shivani Agarwal %F pmlr-v125-neu20a %I PMLR %P 3030--3048 %U https://proceedings.mlr.press/v125/neu20a.html %V 125 %X 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 $0.5$ (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
APA
Neu, G. & Zhivotovskiy, N.. (2020). Fast Rates for Online Prediction with Abstention. Proceedings of Thirty Third Conference on Learning Theory, in Proceedings of Machine Learning Research 125:3030-3048 Available from https://proceedings.mlr.press/v125/neu20a.html.

Related Material