Material Detail
Prediction by random-walk perturbation
This video was recorded at 26th Annual Conference on Learning Theory (COLT), Princeton 2013. 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(√nlogN) 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(√nlogN) 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.
Quality
- User Rating
- Comments
- Learning Exercises
- Bookmark Collections
- Course ePortfolios
- Accessibility Info