Timezone: »

 
Poster
Online Learning with Abstention
Corinna Cortes · Giulia DeSalvo · Claudio Gentile · Mehryar Mohri · Scott Yang

Fri Jul 13 09:15 AM -- 12:00 PM (PDT) @ Hall B #116
in Posters Fri »

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 certain 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 benefits 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.

[ PDF] 

Author Information

Corinna Cortes (Google Research)
Giulia DeSalvo (Google Research)
Claudio Gentile (INRIA)
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