Prediction by random-walk perturbation
author: Gergely Neu,
SequeL, INRIA Lille - Nord Europe
published: Aug. 9, 2013, recorded: June 2013, views: 3579
published: Aug. 9, 2013, recorded: June 2013, views: 3579
Slides
Related content
Report a problem or upload files
If 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.
Description
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 page
Would you like to put a link to this lecture on your homepage?Go ahead! Copy the HTML snippet !
Write your own review or comment: