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, . . . , uT
in W ⊆ Rd can be reframed as competing with a fixed comparator function
u : [1, T ] → W, we cast 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, . . . , uT ) = O(pP
t ∥ut − ut−1∥T ) dynamic regret guaran-
tee 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 O∥u∥2
H + deff (λ) ln T
bounds when
the losses have meaningful curvature, where deff (λ) is a measure of complexity of
the RKHS. Despite working in an infinite-dimensional space, the resulting reduc-
tion leads to algorithms that are computable in practice, due to the reproducing
property of RKHSs.