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.

本文研究了强凸损失函数下的动态遗憾最小化框架，通过利用 KKT 条件所施加的许多新约束条件，我们回答了 Baby 和 Wang 2021 年提出的一个开放性问题，并展示了强适应算法在适当的学习设置下可以同时针对任何比较序列达到几乎最优的动态遗憾。此外，在处理非平滑损失和改善回避维度依赖性等方面，我们还取得了 Baby 和 Wang 2021 年工作的其他改进，并针对 exp-concave 损失和一个 L∞受限决策集的特殊情况导出了几乎最优的动态遗憾率。

强凸损失理论在适当在线学习中的最优动态遗憾及其扩展

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

We consider the problem of the Zinkevich (2003)-style dynamic regret
minimization in online learning with exp-concave losses. We show that whenever
improper learning is allowed, a Strongly Adaptive online learner achieves the
dynamic regret of $\tilde O^*(n^{1/3}C_n^{2/3} \vee 1)$ where $C_n$ is the
total variation (a.k.a. path length) of the an arbitrary sequence of
comparators that may not be known to the learner ahead of time. Achieving this
rate was highly nontrivial even for squared losses in 1D where the best known
upper bound was $O(\sqrt{nC_n} \vee \log n)$ (Yuan and Lamperski, 2019). Our
new proof techniques make elegant use of the intricate structures of the primal
and dual variables imposed by the KKT conditions and could be of independent
interest. Finally, we apply our results to the classical statistical problem of
locally adaptive non-parametric regression (Mammen, 1991; Donoho and Johnstone,
1998) and obtain a stronger and more flexible algorithm that do not require any
statistical assumptions or any hyperparameter tuning.

使用先进的证明技术和 Zinkevich-style 动态遗憾最小化框架，本研究提出了一个强适应的在线学习算法，其总变化控制下的动态遗憾为 O (n^(1/3)*C_n^(2/3))，并且可以扩展到局部自适应非参数回归问题中。