论文标题
关于自适应和动态遗憾最小化的计算效率
On the Computational Efficiency of Adaptive and Dynamic Regret Minimization
论文作者
论文摘要
在在线凸优化中，玩家旨在最大程度地减少遗憾，或者她的损失与在整个重复游戏中最佳固定决定之间的差异。最小化（标准）遗憾的算法可能会收敛到固定决策，这在改变或动态环境中是不可能的。这激发了性能的更强指标，特别是适应性和动态的遗憾。自适应遗憾是对任何连续的子互动的最大遗憾。动态的遗憾是事后看来的总成本与最佳决策序列的差异之间的区别。 自适应和动态遗憾最小化的最先进的表现会受到计算惩罚 - 通常是基于乘法因素的顺序，在游戏迭代次数中对数进行对数。在本文中，我们展示了如何在游戏迭代次数中减少这种计算惩罚以双重对数，并保持几乎最佳的自适应和动态遗憾界限。
In online convex optimization, the player aims to minimize regret, or the difference between her loss and that of the best fixed decision in hindsight over the entire repeated game. Algorithms that minimize (standard) regret may converge to a fixed decision, which is undesirable in changing or dynamic environments. This motivates the stronger metrics of performance, notably adaptive and dynamic regret. Adaptive regret is the maximum regret over any continuous sub-interval in time. Dynamic regret is the difference between the total cost and that of the best sequence of decisions in hindsight. State-of-the-art performance in both adaptive and dynamic regret minimization suffers a computational penalty - typically on the order of a multiplicative factor that grows logarithmically in the number of game iterations. In this paper we show how to reduce this computational penalty to be doubly logarithmic in the number of game iterations, and retain near optimal adaptive and dynamic regret bounds.
