图 书 馆
随机游走扰动预测Prediction by random-walk perturbation |
|
| 课程网址: | http://videolectures.net/colt2013_neu_prediction/ |
| 主讲教师: | Gergely Neu |
| 开课单位: | INRIA研究机构 |
| 开课时间: | 2013-08-09 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | 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. |
| 关 键 词: | 线预测算法; 线组合优化 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2020-07-29：yumf |
| 阅读次数: | 59 |