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.
