Online Learning with Abstention

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

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


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)
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


Other35th International Conference on Machine Learning, ICML 2018

ASJC Scopus subject areas

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


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

Cite this