Second Order Path Variationals in Non-Stationary Online Learning. (arXiv:2205.01921v1 [cs.LG])

Web: http://arxiv.org/abs/2205.01921

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 …

arxiv learning online online learning path