# Prediction by Random-Walk Perturbation

arXiv: https://arxiv.org/abs/1302.5797 · HTML: https://mlsanity.com/paper/1302.5797/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Feb 2013.

## Built on by (most cited first, 7 of 7)

- [Smoothed Online Learning is as Easy as Statistical Learning](https://mlsanity.com/paper/2202.04690/) (2022)
- [Lazy OCO: Online Convex Optimization on a Switching Budget](https://mlsanity.com/paper/2102.03803/) (2021)
- [Online learning with noisy side observations](https://mlsanity.com/paper/2604.13740/) (2026)
- [No-regret incentive-compatible online learning under exact truthfulness with non-myopic experts](https://mlsanity.com/paper/2502.11483/) (2025)
- [Bayesian Algorithms for Adversarial Online Learning: from Finite to Infinite Action Spaces](https://mlsanity.com/paper/2502.14790/) (2025)
- [Prediction with Expert Advice under Local Differential Privacy](https://mlsanity.com/paper/2512.06971/) (2025)
- [No-Regret Mixing of LRU and LFU with Optimal Switching Cost](https://mlsanity.com/paper/2609.07566/) (2026)

## Abstract (arXiv)

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.