标题： 在线优化：与动态比较器竞争 显示英文标题

标题： Online Optimization : Competing with Dynamic Comparators

摘要： 最近关于在线学习的文献集中在开发利用观察序列规律性的自适应算法，同时保持最坏情况下的性能保证。 一种互补的方向是开发在复杂基准上表现良好的预测方法。 在本文中，我们同时处理这两个方向。 我们提出了一种完全自适应的方法，在其中遗憾保证与成本函数序列和比较器的规律性相关。 值得注意的是，遗憾界适应于问题环境中的较小复杂度度量。 最后，我们将我们的结果应用于漂移零和、两人博弈，在这种情况下，两名玩家都能在事后最佳动作序列上实现无遗憾保证。 显示英文摘要

摘要： Recent literature on online learning has focused on developing adaptive algorithms that take advantage of a regularity of the sequence of observations, yet retain worst-case performance guarantees. A complementary direction is to develop prediction methods that perform well against complex benchmarks. In this paper, we address these two directions together. We present a fully adaptive method that competes with dynamic benchmarks in which regret guarantee scales with regularity of the sequence of cost functions and comparators. Notably, the regret bound adapts to the smaller complexity measure in the problem environment. Finally, we apply our results to drifting zero-sum, two-player games where both players achieve no regret guarantees against best sequences of actions in hindsight.