论文标题
在随机和对抗性在线凸优化之间：通过平稳性改善后悔界限
Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothness
论文作者
论文摘要
随机数据和对抗性数据是在线学习中进行了两个广泛研究的设置。但是许多优化任务都不是I.I.D.也不完全对抗，这使得对这些极端之间的世界有更好的理论理解具有根本的利益。在这项工作中，我们在在随机I.I.D.之间插值的环境中建立了在线凸优化的新颖遗憾界限。和完全的对抗损失。通过利用预期损失的平滑度，这些边界用梯度的方差取代对最大梯度长度的依赖，这以前仅以线性损失而闻名。此外，它们削弱了I.I.D.假设通过允许对抗中毒的回合，以前在专家和强盗设置中考虑过。我们的结果将其扩展到在线凸优化框架上。在完全I.I.D.中情况，我们的界限与随机加速的结果相匹配，在完全对抗的情况下，它们优雅地恶化以符合Minimax的遗憾。我们进一步提供了下限，表明所有中级机制的遗憾上限都很紧张，从随机方差和损失梯度的对抗变异方面。
Stochastic and adversarial data are two widely studied settings in online learning. But many optimization tasks are neither i.i.d. nor fully adversarial, which makes it of fundamental interest to get a better theoretical understanding of the world between these extremes. In this work we establish novel regret bounds for online convex optimization in a setting that interpolates between stochastic i.i.d. and fully adversarial losses. By exploiting smoothness of the expected losses, these bounds replace a dependence on the maximum gradient length by the variance of the gradients, which was previously known only for linear losses. In addition, they weaken the i.i.d. assumption by allowing, for example, adversarially poisoned rounds, which were previously considered in the expert and bandit setting. Our results extend this to the online convex optimization framework. In the fully i.i.d. case, our bounds match the rates one would expect from results in stochastic acceleration, and in the fully adversarial case they gracefully deteriorate to match the minimax regret. We further provide lower bounds showing that our regret upper bounds are tight for all intermediate regimes in terms of the stochastic variance and the adversarial variation of the loss gradients.
