Timezone: »

 
Poster
Online Learning with Sleeping Experts and Feedback Graphs
Corinna Cortes · Giulia DeSalvo · Claudio Gentile · Mehryar Mohri · Scott Yang

Thu Jun 13 06:30 PM -- 09:00 PM (PDT) @ Pacific Ballroom #152
in Posters Thu »

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.

Keywords: Online Learning · Statistical Learning Theory

Author Information

Corinna Cortes (Google Research)
Giulia DeSalvo (Google Research)
Claudio Gentile (INRIA and Google)
Mehryar Mohri (Courant Institute and Google Research)
Scott Yang (D. E. Shaw & Co.)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors