[edit]

# Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond

*Proceedings of The 25th International Conference on Artificial Intelligence and Statistics*, PMLR 151:1805-1845, 2022.

#### Abstract

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.