Online Learning with Feedback Graphs Without the Graphs

Alon Cohen, Tamir Hazan, Tomer Koren
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:811-819, 2016.

Abstract

We study an online learning framework introduced by Mannor and Shamir (2011) in which the feedback is specified by a graph, in a setting where the graph may vary from round to round and is \emphnever fully revealed to the learner. We show a large gap between the adversarial and the stochastic cases. In the adversarial case, we prove that even for dense feedback graphs, the learner cannot improve upon a trivial regret bound obtained by ignoring any additional feedback besides her own loss. In contrast, in the stochastic case we give an algorithm that achieves \widetildeΘ(\sqrtαT) regret over T rounds, provided that the independence numbers of the hidden feedback graphs are at most α. We also extend our results to a more general feedback model, in which the learner does not necessarily observe her own loss, and show that, even in simple cases, concealing the feedback graphs might render the problem unlearnable.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-cohena16, title = {Online Learning with Feedback Graphs Without the Graphs}, author = {Cohen, Alon and Hazan, Tamir and Koren, Tomer}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {811--819}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/cohena16.pdf}, url = {https://proceedings.mlr.press/v48/cohena16.html}, abstract = {We study an online learning framework introduced by Mannor and Shamir (2011) in which the feedback is specified by a graph, in a setting where the graph may vary from round to round and is \emphnever fully revealed to the learner. We show a large gap between the adversarial and the stochastic cases. In the adversarial case, we prove that even for dense feedback graphs, the learner cannot improve upon a trivial regret bound obtained by ignoring any additional feedback besides her own loss. In contrast, in the stochastic case we give an algorithm that achieves \widetildeΘ(\sqrtαT) regret over T rounds, provided that the independence numbers of the hidden feedback graphs are at most α. We also extend our results to a more general feedback model, in which the learner does not necessarily observe her own loss, and show that, even in simple cases, concealing the feedback graphs might render the problem unlearnable.} }
Endnote
%0 Conference Paper %T Online Learning with Feedback Graphs Without the Graphs %A Alon Cohen %A Tamir Hazan %A Tomer Koren %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-cohena16 %I PMLR %P 811--819 %U https://proceedings.mlr.press/v48/cohena16.html %V 48 %X We study an online learning framework introduced by Mannor and Shamir (2011) in which the feedback is specified by a graph, in a setting where the graph may vary from round to round and is \emphnever fully revealed to the learner. We show a large gap between the adversarial and the stochastic cases. In the adversarial case, we prove that even for dense feedback graphs, the learner cannot improve upon a trivial regret bound obtained by ignoring any additional feedback besides her own loss. In contrast, in the stochastic case we give an algorithm that achieves \widetildeΘ(\sqrtαT) regret over T rounds, provided that the independence numbers of the hidden feedback graphs are at most α. We also extend our results to a more general feedback model, in which the learner does not necessarily observe her own loss, and show that, even in simple cases, concealing the feedback graphs might render the problem unlearnable.
RIS
TY - CPAPER TI - Online Learning with Feedback Graphs Without the Graphs AU - Alon Cohen AU - Tamir Hazan AU - Tomer Koren BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-cohena16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 811 EP - 819 L1 - http://proceedings.mlr.press/v48/cohena16.pdf UR - https://proceedings.mlr.press/v48/cohena16.html AB - We study an online learning framework introduced by Mannor and Shamir (2011) in which the feedback is specified by a graph, in a setting where the graph may vary from round to round and is \emphnever fully revealed to the learner. We show a large gap between the adversarial and the stochastic cases. In the adversarial case, we prove that even for dense feedback graphs, the learner cannot improve upon a trivial regret bound obtained by ignoring any additional feedback besides her own loss. In contrast, in the stochastic case we give an algorithm that achieves \widetildeΘ(\sqrtαT) regret over T rounds, provided that the independence numbers of the hidden feedback graphs are at most α. We also extend our results to a more general feedback model, in which the learner does not necessarily observe her own loss, and show that, even in simple cases, concealing the feedback graphs might render the problem unlearnable. ER -
APA
Cohen, A., Hazan, T. & Koren, T.. (2016). Online Learning with Feedback Graphs Without the Graphs. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:811-819 Available from https://proceedings.mlr.press/v48/cohena16.html.

Related Material