Dynamic Regret of Strongly Adaptive Methods
  To cope with changing environments, recent developments in online learning
have introduced the concepts of adaptive regret and dynamic regret
independently. In this paper, we illustrate an intrinsic connection between
these two concepts by showing that the dynamic regret can be expressed in terms
of the adaptive regret and the functional variation. This observation implies
that strongly adaptive algorithms can be directly leveraged to minimize the
dynamic regret. As a result, we present a series of strongly adaptive
algorithms that have small dynamic regrets for convex functions, exponentially
concave functions, and strongly convex functions, respectively. To the best of
our knowledge, this is the first time that exponential concavity is utilized to
upper bound the dynamic regret. Moreover, all of those adaptive algorithms do
not need any prior knowledge of the functional variation, which is a
significant advantage over previous specialized methods for minimizing dynamic
regret.
