Prediction by Random-Walk Perturbation
This work addresses online learning efficiency for scenarios requiring low switching costs, though it appears incremental as it builds on existing perturbed-leader methods.
The paper tackles the problem of online prediction by proposing a follow-the-perturbed-leader algorithm with random-walk perturbations, achieving an expected regret of O(sqrt(n log N)) and limiting prediction changes to O(sqrt(n log N)) times in expectation.
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(sqrt(n 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(sqrt(n 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.