Dynamic Regret Reduces to Kernelized Static Regret

Francesco Orabona (KAUST) · Nicolò Cesa-Bianchi (Università degli Studi di Milano, Italy) · Alessandro Rudi (INRIA, Ecole Normale Superieure) · Andrew Jacobsen (Politecnico Milan, University of Milan)

benchmark sequencecomputable algorithmscumulative losscurvaturedirectionally-adaptive guaranteesdynamic regretfixed comparator functionfunction spaceinfinite-dimensional spacelinear lossesmeasure of complexityonline convex optimization reproducing kernel hilbert spacereproducing propertyscale-free guaranteesstatic regret problem

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 $u_{1},\ldots,u_{T}$ in $\mathcal{W}\subseteq\mathbb{R}^{d}$ can be reframed as competing with a *fixed* comparator *function* $u:[1,T]\to \mathcal{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 $R_{T}(u_{1},\ldots,u_{T}) = \mathcal{O}(\sqrt{\sum_{t}\\|u_{t}-u_{t-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