en
0.25
0.5
0.75
1.25
1.5
1.75
2
Prediction by random-walk perturbation
Published on Aug 09, 20133603 Views
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 achie
Related categories
Chapter list
Prediction by random-walk perturbation00:00
Example: sequential routing00:27
Switching costs - 101:14
Switching costs - 201:26
Switching costs - 301:41
Switching costs - 401:43
Switching costs - 501:50
Online combinatorial optimization - 102:12
Online combinatorial optimization - 202:35
Online combinatorial optimization - 303:09
Online combinatorial optimization - 403:25
Previous results - 103:39
Previous results - 205:26
Previous results - 305:58
Follow the perturbed leader06:36
Prediction by random-walk perturbation07:25
Analysis for 𝑚=108:00
Number of switches, 𝑑=1009:05
Number of switches, 𝑑=5009:12
Number of switches, 𝑑=100 - 109:27
Number of switches, 𝑑=100 - 209:42
Proof idea (𝑚=1) 10:27
Main result for 𝑚=111:43
Combinatorial action set (𝑚>1)11:58
Proof idea (𝑚>1)12:39
Main result for 𝑚>113:22
Conclusions & open problems13:54