Prediction by Random-Walk Perturbation
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( p n logN) 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( p n logN) 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
Text
Devroye et al. "Prediction by Random-Walk Perturbation." Annual Conference on Computational Learning Theory, 2013.Markdown
[Devroye et al. "Prediction by Random-Walk Perturbation." Annual Conference on Computational Learning Theory, 2013.](https://mlanthology.org/colt/2013/devroye2013colt-prediction/)BibTeX
@inproceedings{devroye2013colt-prediction,
title = {{Prediction by Random-Walk Perturbation}},
author = {Devroye, Luc and Lugosi, Gábor and Neu, Gergely},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2013},
pages = {460-473},
url = {https://mlanthology.org/colt/2013/devroye2013colt-prediction/}
}