Dynamic Regret Reduces to Kernelized Static Regret

We study dynamic regret in online convex optimization, where the objective is to achieve low cumulative loss relative to an arbitrary benchmark sequence. By observing that competing with an arbitrary sequence of comparators u1,ldots,uT in Wsubseteqℝd is equivalent to competing with a fixed comparator function u:[1,T]→ W, we frame dynamic regret minimization as a static regret problem in a function space. By carefully constructing a suitable function space in the form of a Reproducing Kernel Hilbert Space (RKHS), our reduction enables us to recover the optimal RT(u1,ldots,uT) = O(√sumt|ut-ut-1|T) dynamic regret guarantee in the setting of linear losses, and yields new scale-free and directionally-adaptive dynamic regret guarantees. Moreover, unlike prior dynamic-to-static reductions -- which are valid only for linear losses -- our reduction holds for any sequence of losses, allowing us to recover Obig(|u|2H+deff(λ)ln Tbig) bounds in exp-concave and improper linear regression settings, where deff(λ) is a measure of complexity of the RKHS. Despite working in an infinite-dimensional space, the resulting reduction leads to algorithms that are computable in practice, due to the reproducing property of RKHSs.