BriefGPT.xyz
Feb, 2013
随机行走扰动预测
Prediction by Random-Walk Perturbation
HTML
PDF
Luc Devroye, Gábor Lugosi, Gergely Neu
TL;DR
本文提出了一种基于扰动随从最优策略算法版本，可以将累积损失通过独立的对称随机游动进行扰动，预测者能够实现期望遗憾最优阶O(sqrt(n log N)),且预测者的改变在预期下最多为O(sqrt(n log N))，同时拓展分析在线组合优化，表明即使在更一般的情况下，预测者也很少在专家之间切换，同时达到近乎最优的遗憾级别。
Abstract
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 expect
→