Online Learning with Abstention

Corinna Cortes, Giulia DeSalvo, Claudio Gentile, Mehryar Mohri, Scott Yang
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:1059-1067, 2018.

Abstract

We present an extensive study of a key problem in online learning where the learner can opt to abstain from making a prediction, at a certain cost. In the adversarial setting, we show how existing online algorithms and guarantees can be adapted to this problem. In the stochastic setting, we first point out a bias problem that limits the straightforward extension of algorithms such as UCB-N to this context. Next, we give a new algorithm, UCB-GT, that exploits historical data and time-varying feedback graphs. We show that this algorithm benefits from more favorable regret guarantees than a natural extension of UCB-N . We further report the results of a series of experiments demonstrating that UCB-GT largely outperforms that extension of UCB-N, as well as other standard baselines.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-cortes18a, title = {Online Learning with Abstention}, author = {Cortes, Corinna and DeSalvo, Giulia and Gentile, Claudio and Mohri, Mehryar and Yang, Scott}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {1059--1067}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/cortes18a/cortes18a.pdf}, url = {https://proceedings.mlr.press/v80/cortes18a.html}, abstract = {We present an extensive study of a key problem in online learning where the learner can opt to abstain from making a prediction, at a certain cost. In the adversarial setting, we show how existing online algorithms and guarantees can be adapted to this problem. In the stochastic setting, we first point out a bias problem that limits the straightforward extension of algorithms such as UCB-N to this context. Next, we give a new algorithm, UCB-GT, that exploits historical data and time-varying feedback graphs. We show that this algorithm benefits from more favorable regret guarantees than a natural extension of UCB-N . We further report the results of a series of experiments demonstrating that UCB-GT largely outperforms that extension of UCB-N, as well as other standard baselines.} }
Endnote
%0 Conference Paper %T Online Learning with Abstention %A Corinna Cortes %A Giulia DeSalvo %A Claudio Gentile %A Mehryar Mohri %A Scott Yang %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-cortes18a %I PMLR %P 1059--1067 %U https://proceedings.mlr.press/v80/cortes18a.html %V 80 %X We present an extensive study of a key problem in online learning where the learner can opt to abstain from making a prediction, at a certain cost. In the adversarial setting, we show how existing online algorithms and guarantees can be adapted to this problem. In the stochastic setting, we first point out a bias problem that limits the straightforward extension of algorithms such as UCB-N to this context. Next, we give a new algorithm, UCB-GT, that exploits historical data and time-varying feedback graphs. We show that this algorithm benefits from more favorable regret guarantees than a natural extension of UCB-N . We further report the results of a series of experiments demonstrating that UCB-GT largely outperforms that extension of UCB-N, as well as other standard baselines.
APA
Cortes, C., DeSalvo, G., Gentile, C., Mohri, M. & Yang, S.. (2018). Online Learning with Abstention. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:1059-1067 Available from https://proceedings.mlr.press/v80/cortes18a.html.

Related Material