Prediction by Random-Walk Perturbation
arXiv:1302.5797
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(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.
References in corpus (2)
Cited by in corpus (12)
- Online Linear Optimization via Smoothing
- Online learning with noisy side observations
- Fighting Bandits with a New Kind of Smoothness
- First-order regret bounds for combinatorial semi-bandits
- A half-normal distribution scheme for generating functions
- Towards Minimax Online Learning with Unknown Time Horizon
- Importance weighting without importance weights: An efficient algorithm for combinatorial semi-bandits
- Minimax Regret of Switching-Constrained Online Convex Optimization: No Phase Transition
- Learning in Non-convex Games with an Optimization Oracle
- On the Optimality of Perturbations in Stochastic and Adversarial Multi-armed Bandit Problems
- Lazy OCO: Online Convex Optimization on a Switching Budget
- Sampled Fictitious Play is Hannan Consistent