Material Detail

Prediction by random-walk perturbation

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.


  • User Rating
  • Comments
  • Learning Exercises
  • Bookmark Collections
  • Course ePortfolios
  • Accessibility Info

More about this material


Log in to participate in the discussions or sign up if you are not already a MERLOT member.