Prediction by random-walk perturbation

Luc Devroye, Gábor Lugosi, Gergely Neu
Proceedings of the 26th Annual Conference on Learning Theory, PMLR 30:460-473, 2013.

Abstract

We propose a version of the follow-the-perturbed-leader online prediction algorithm in which the cumulative losses are perturbed by independent symmetric random walks. The forecaster is shown to achieve an expected regret of the optimal order O(\sqrtn \log N) where n is the time horizon and N is the number of experts. More importantly, it is shown that the forecaster changes its prediction at most O(\sqrtn \log N) times, in expectation. We also extend the analysis to online combinatorial optimization and show that even in this more general setting, the forecaster rarely switches between experts while having a regret of near-optimal order.

Cite this Paper

BibTeX
@InProceedings{pmlr-v30-Devroye13, title = {Prediction by random-walk perturbation}, author = {Devroye, Luc and Lugosi, Gábor and Neu, Gergely}, booktitle = {Proceedings of the 26th Annual Conference on Learning Theory}, pages = {460--473}, year = {2013}, editor = {Shalev-Shwartz, Shai and Steinwart, Ingo}, volume = {30}, series = {Proceedings of Machine Learning Research}, address = {Princeton, NJ, USA}, month = {12--14 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v30/Devroye13.pdf}, url = {https://proceedings.mlr.press/v30/Devroye13.html}, abstract = {We propose a version of the follow-the-perturbed-leader online prediction algorithm in which the cumulative losses are perturbed by independent symmetric random walks. The forecaster is shown to achieve an expected regret of the optimal order O(\sqrtn \log N) where n is the time horizon and N is the number of experts. More importantly, it is shown that the forecaster changes its prediction at most O(\sqrtn \log N) times, in expectation. We also extend the analysis to online combinatorial optimization and show that even in this more general setting, the forecaster rarely switches between experts while having a regret of near-optimal order. } }
Endnote
%0 Conference Paper %T Prediction by random-walk perturbation %A Luc Devroye %A Gábor Lugosi %A Gergely Neu %B Proceedings of the 26th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2013 %E Shai Shalev-Shwartz %E Ingo Steinwart %F pmlr-v30-Devroye13 %I PMLR %P 460--473 %U https://proceedings.mlr.press/v30/Devroye13.html %V 30 %X We propose a version of the follow-the-perturbed-leader online prediction algorithm in which the cumulative losses are perturbed by independent symmetric random walks. The forecaster is shown to achieve an expected regret of the optimal order O(\sqrtn \log N) where n is the time horizon and N is the number of experts. More importantly, it is shown that the forecaster changes its prediction at most O(\sqrtn \log N) times, in expectation. We also extend the analysis to online combinatorial optimization and show that even in this more general setting, the forecaster rarely switches between experts while having a regret of near-optimal order.
RIS
TY - CPAPER TI - Prediction by random-walk perturbation AU - Luc Devroye AU - Gábor Lugosi AU - Gergely Neu BT - Proceedings of the 26th Annual Conference on Learning Theory DA - 2013/06/13 ED - Shai Shalev-Shwartz ED - Ingo Steinwart ID - pmlr-v30-Devroye13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 30 SP - 460 EP - 473 L1 - http://proceedings.mlr.press/v30/Devroye13.pdf UR - https://proceedings.mlr.press/v30/Devroye13.html AB - We propose a version of the follow-the-perturbed-leader online prediction algorithm in which the cumulative losses are perturbed by independent symmetric random walks. The forecaster is shown to achieve an expected regret of the optimal order O(\sqrtn \log N) where n is the time horizon and N is the number of experts. More importantly, it is shown that the forecaster changes its prediction at most O(\sqrtn \log N) times, in expectation. We also extend the analysis to online combinatorial optimization and show that even in this more general setting, the forecaster rarely switches between experts while having a regret of near-optimal order. ER -
APA
Devroye, L., Lugosi, G. & Neu, G.. (2013). Prediction by random-walk perturbation. Proceedings of the 26th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 30:460-473 Available from https://proceedings.mlr.press/v30/Devroye13.html.

Related Material