Online Learning with Sleeping Experts and Feedback Graphs

Corinna Cortes, Giulia Desalvo, Claudio Gentile, Mehryar Mohri, Scott Yang
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:1370-1378, 2019.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-cortes19a, title = {Online Learning with Sleeping Experts and Feedback Graphs}, author = {Cortes, Corinna and Desalvo, Giulia and Gentile, Claudio and Mohri, Mehryar and Yang, Scott}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {1370--1378}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/cortes19a/cortes19a.pdf}, url = {https://proceedings.mlr.press/v97/cortes19a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Online Learning with Sleeping Experts and Feedback Graphs %A Corinna Cortes %A Giulia Desalvo %A Claudio Gentile %A Mehryar Mohri %A Scott Yang %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-cortes19a %I PMLR %P 1370--1378 %U https://proceedings.mlr.press/v97/cortes19a.html %V 97 %X 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.
APA
Cortes, C., Desalvo, G., Gentile, C., Mohri, M. & Yang, S.. (2019). Online Learning with Sleeping Experts and Feedback Graphs. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:1370-1378 Available from https://proceedings.mlr.press/v97/cortes19a.html.

Related Material