Timezone: »

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

Thu Jun 13 09:30 AM -- 09:35 AM (PDT) @ Room 102
in Online Learning »

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 stochastic feedback graphs, where 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 expert 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 finer notion of sleeping regret, and derive a general algorithm with strong theoretical guarantees. We instantiate our 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.

[ Slides]  [ Oral] 

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