论文标题
用反馈图的随机在线学习：有限的时间和渐近最优性
Stochastic Online Learning with Feedback Graphs: Finite-Time and Asymptotic Optimality
论文作者
论文摘要
我们通过反馈图来重新审视随机在线学习的问题，目的是设计最佳的算法，均非常数，无论是渐近还是有限的时间。我们表明，令人惊讶的是，在这种情况下，最佳有限时间遗憾的概念并不是一个唯一定义的属性，并且总的来说，它与渐近率是脱在一起的。我们讨论了替代选择，并提出了有限时间最优性的概念，我们认为是\ emph {有意义的}。对于这个概念，我们给出了一种算法，在有限的时间和渐近的情况下都承认了准最佳的遗憾。
We revisit the problem of stochastic online learning with feedback graphs, with the goal of devising algorithms that are optimal, up to constants, both asymptotically and in finite time. We show that, surprisingly, the notion of optimal finite-time regret is not a uniquely defined property in this context and that, in general, it is decoupled from the asymptotic rate. We discuss alternative choices and propose a notion of finite-time optimality that we argue is \emph{meaningful}. For that notion, we give an algorithm that admits quasi-optimal regret both in finite-time and asymptotically.
