论文标题
最佳的动态遗憾在适当的在线学习和强烈凸出的损失及以后
Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond
论文作者
论文摘要
我们研究了通用动态遗憾最小化的框架，并强烈凸出损失。我们通过证明在适当的学习设置中，强烈的自适应算法可以实现$ \ tilde o（d^{1/3} n^{1/3} {1/3} {1/3} \ text {tv} [u__ {1：n}]^2/3} {2/3} = veee，在适当的学习设置中，我们可以回答婴儿和王2021中的一个空旷问题。 $ u_1，\ ldots，u_n $同时，其中$ n $是时间范围，$ \ text {tv} [u_ {1：n}] $是比较器的总变化。这些结果是通过利用KKT条件施加的许多新结构来促进的，而KKT条件在Baby和Wang 2021中未考虑，这也导致了对其结果的其他改进，例如：（a）处理非平滑损失的损失以及（b）改善对遗憾的维度的依赖性。此外，我们还为适当的在线学习和Exp-Concave损失和$ L_ \ Infty $约束决策集的特殊情况提供了几乎最佳的动态遗憾。
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.
