论文标题
尽量减少动态遗憾和自适应遗憾
Minimizing Dynamic Regret and Adaptive Regret Simultaneously
论文作者
论文摘要
遗憾的最小化被视为传统的在线学习研究中的黄金法则。但是，遗憾的最小化算法倾向于融合到静态最佳限制，因此对于不断变化的环境而言是优越的。为了解决这一限制，已经提出了新的绩效措施，包括动态遗憾和自适应遗憾，以指导在线算法的设计。前者的目的是最大程度地减少一系列更改比较者的遗憾，而后者试图最大程度地减少对固定比较器的每一个本地遗憾。现有的动态遗憾和自适应遗憾的算法是独立发展的，仅针对一种绩效指标。在本文中，我们通过提出新颖的在线算法来弥合这一差距，这些算法能够同时减少动态的遗憾和自适应遗憾。实际上，我们的理论保证甚至更强大，因为一种算法能够最大程度地减少任何间隔的动态遗憾。
Regret minimization is treated as the golden rule in the traditional study of online learning. However, regret minimization algorithms tend to converge to the static optimum, thus being suboptimal for changing environments. To address this limitation, new performance measures, including dynamic regret and adaptive regret have been proposed to guide the design of online algorithms. The former one aims to minimize the global regret with respect to a sequence of changing comparators, and the latter one attempts to minimize every local regret with respect to a fixed comparator. Existing algorithms for dynamic regret and adaptive regret are developed independently, and only target one performance measure. In this paper, we bridge this gap by proposing novel online algorithms that are able to minimize the dynamic regret and adaptive regret simultaneously. In fact, our theoretical guarantee is even stronger in the sense that one algorithm is able to minimize the dynamic regret over any interval.
