Online Learning with Sleeping Experts and Feedback Graphs

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

Research output: Contribution to conferencePaperpeer-review


We consider the scenario of online learning with sleeping experts, where not all experts are available at each round, and analyze the general framework of learning with feedback graphs, where the loss observations associated with each expert are characterized by a graph. A critical assumption in this framework is that the loss observations and the set of sleeping experts at each round are independent. We first extend the classical sleeping experts algorithm of Kleinberg et al. (2008) to the feedback graphs scenario, and prove matching upper and lower bounds for the sleeping regret of the resulting algorithm under the independence assumption. Our main contribution is then to relax this assumption, present a more general notion of sleeping regret, and derive a general algorithm with strong theoretical guarantees. We apply this new framework to the important scenario of online learning with abstention, where a learner can elect to abstain from making a prediction at the price of a certain cost. We empirically validate our algorithm against multiple online abstention algorithms on several real-world datasets, showing substantial performance improvements.

Original languageEnglish (US)
Number of pages9
StatePublished - 2019
Event36th International Conference on Machine Learning, ICML 2019 - Long Beach, United States
Duration: Jun 9 2019Jun 15 2019


Conference36th International Conference on Machine Learning, ICML 2019
Country/TerritoryUnited States
CityLong Beach

ASJC Scopus subject areas

  • Education
  • Computer Science Applications
  • Human-Computer Interaction


Dive into the research topics of 'Online Learning with Sleeping Experts and Feedback Graphs'. Together they form a unique fingerprint.

Cite this