TY - GEN
T1 - Online learning with dependent stochastic feedback graphs
AU - Cortes, Corinna
AU - DeSalvo, Giulia
AU - Gentile, Claudio
AU - Mohri, Mehryar
AU - Zhang, Ningshan
N1 - Publisher Copyright:
© 37th International Conference on Machine Learning, ICML 2020.
PY - 2020
Y1 - 2020
N2 - A general framework for online learning with partial information is one where feedback graphs specify which losses can be observed by the learner. We study a challenging scenario where feedback graphs vary stochastically with time and, more importantly, where graphs and losses are dependent. This scenario appears in several real-world applications that we describe where the outcome of actions are correlated. We devise a new algorithm for this setting that exploits the stochastic properties of the graphs and that benefits from favorable regret guarantees. We present a detailed theoretical analysis of this algorithm, and also report the results of a series of experiments on real-world datasets, which show that our algorithm outperforms standard baselines for online learning with feedback graphs.
AB - A general framework for online learning with partial information is one where feedback graphs specify which losses can be observed by the learner. We study a challenging scenario where feedback graphs vary stochastically with time and, more importantly, where graphs and losses are dependent. This scenario appears in several real-world applications that we describe where the outcome of actions are correlated. We devise a new algorithm for this setting that exploits the stochastic properties of the graphs and that benefits from favorable regret guarantees. We present a detailed theoretical analysis of this algorithm, and also report the results of a series of experiments on real-world datasets, which show that our algorithm outperforms standard baselines for online learning with feedback graphs.
UR - http://www.scopus.com/inward/record.url?scp=85105244529&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85105244529&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85105244529
T3 - 37th International Conference on Machine Learning, ICML 2020
SP - 2132
EP - 2141
BT - 37th International Conference on Machine Learning, ICML 2020
A2 - Daume, Hal
A2 - Singh, Aarti
PB - International Machine Learning Society (IMLS)
T2 - 37th International Conference on Machine Learning, ICML 2020
Y2 - 13 July 2020 through 18 July 2020
ER -