Prediction by random-walk perturbation
published: Aug. 9, 2013, recorded: June 2013, views: 3577
Report a problem or upload filesIf you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
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.
Link this pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !