Optimal Dynamic Regret in Proper Online Learning with Strongly Convex
  Losses and Beyond
  We study the framework of universal dynamic regret minimization with strongly
convex losses. We answer an open problem in Baby and Wang 2021 by showing that
in a proper learning setup, Strongly Adaptive algorithms can achieve the near
optimal dynamic regret of $\tilde O(d^{1/3} n^{1/3}\text{TV}[u_{1:n}]^{2/3}
\vee d)$ against any comparator sequence $u_1,\ldots,u_n$ simultaneously, where
$n$ is the time horizon and $\text{TV}[u_{1:n}]$ is the Total Variation of
comparator. These results are facilitated by exploiting a number of new
structures imposed by the KKT conditions that were not considered in Baby and
Wang 2021 which also lead to other improvements over their results such as: (a)
handling non-smooth losses and (b) improving the dimension dependence on
regret. Further, we also derive near optimal dynamic regret rates for the
special case of proper online learning with exp-concave losses and an
$L_\infty$ constrained decision set.
