论文标题
非平稳在线学习中的二阶路径变化
Second Order Path Variationals in Non-Stationary Online Learning
论文作者
论文摘要
我们认为在Exp-Concave和平滑损失下，普遍动态遗憾的最小化问题。我们表明，适当设计的良好自适应算法使$ \ tilde o（d^2 n^{1/5} c_n^{2/5} {2/5} \ vee d^2）$具有动态的遗憾，其中$ n $是Time Horizon和$ c_n $基于比较序列的二阶差异差异。这样的路径变分天然编码是分段线性的比较序列 - 一个强大的家庭，跟踪实践中各种非平稳性模式（Kim等，2009）。上述动态遗憾率被证明是$ n $的最佳模量依赖性和多同源因素。我们的证明技术依赖于分析离线甲骨文的KKT条件，并且需要对Baby and Wang中的思想进行几个非平凡的概括，后者的工作仅导致$ \ tilde O（D^{2.5} n^{1/3} n^{1/3} c_n^$ def to $ \ tilde o（d^{2.5} c_n^$ d d d^$ def）
We consider the problem of universal dynamic regret minimization under exp-concave and smooth losses. We show that appropriately designed Strongly Adaptive algorithms achieve a dynamic regret of $\tilde O(d^2 n^{1/5} C_n^{2/5} \vee d^2)$, where $n$ is the time horizon and $C_n$ a path variational based on second order differences of the comparator sequence. Such a path variational naturally encodes comparator sequences that are piecewise linear -- a powerful family that tracks a variety of non-stationarity patterns in practice (Kim et al, 2009). The aforementioned dynamic regret rate is shown to be optimal modulo dimension dependencies and poly-logarithmic factors of $n$. Our proof techniques rely on analysing the KKT conditions of the offline oracle and requires several non-trivial generalizations of the ideas in Baby and Wang, 2021, where the latter work only leads to a slower dynamic regret rate of $\tilde O(d^{2.5}n^{1/3}C_n^{2/3} \vee d^{2.5})$ for the current problem.
