Online Learning with Abstention

Corinna Cortes, Giulia Desalvo, Claudio Gentile, Mehryar Mohri, Scott Yang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 ccrtain 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 ben: cfits 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.

Original languageEnglish (US)
Title of host publication35th International Conference on Machine Learning, ICML 2018
EditorsAndreas Krause, Jennifer Dy
PublisherInternational Machine Learning Society (IMLS)
Pages1726-1734
Number of pages9
ISBN (Electronic)9781510867963
StatePublished - 2018
Event35th International Conference on Machine Learning, ICML 2018 - Stockholm, Sweden
Duration: Jul 10 2018Jul 15 2018

Publication series

Name35th International Conference on Machine Learning, ICML 2018
Volume3

Other

Other35th International Conference on Machine Learning, ICML 2018
CountrySweden
CityStockholm
Period7/10/187/15/18

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Human-Computer Interaction
  • Software

Fingerprint Dive into the research topics of 'Online Learning with Abstention'. Together they form a unique fingerprint.

  • Cite this

    Cortes, C., Desalvo, G., Gentile, C., Mohri, M., & Yang, S. (2018). Online Learning with Abstention. In A. Krause, & J. Dy (Eds.), 35th International Conference on Machine Learning, ICML 2018 (pp. 1726-1734). (35th International Conference on Machine Learning, ICML 2018; Vol. 3). International Machine Learning Society (IMLS).