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}$ is equivalent to competing with a fixed comparator function $u:[1,T]\to \mathcal{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 $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 -- which are valid only for linear losses -- our reduction holds for any sequence of losses, allowing us to recover $\mathcal{O}\big(\|u\|^2_{\mathcal{H}}+d_{\mathrm{eff}}(λ)\ln T\big)$ bounds in exp-concave and improper linear regression settings, where $d_{\mathrm{eff}}(λ)$ 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.

翻译：我们研究在线凸优化中的动态遗憾问题，其目标在于实现相对于任意基准序列的低累积损失。通过观察到在$\mathcal{W}\subseteq\mathbb{R}^{d}$中与任意比较器序列$u_{1},\ldots,u_{T}$竞争等价于与固定比较器函数$u:[1,T]\to \mathcal{W}$竞争，我们将动态遗憾最小化问题转化为函数空间中的静态遗憾问题。通过以再生核希尔伯特空间（RKHS）的形式精心构造合适的函数空间，我们的归约方法使我们能够在线性损失设定中恢复最优的动态遗憾保证$R_{T}(u_{1},\ldots,u_{T}) = \mathcal{O}(\sqrt{\sum_{t}\|u_{t}-u_{t-1}\|T})$，并得到新的尺度无关和方向自适应的动态遗憾保证。此外，与先前仅适用于线性损失的动态到静态归约方法不同，我们的归约适用于任意损失序列，从而能够在指数凹损失和非恰当线性回归设定中恢复$\mathcal{O}\big(\|u\|^2_{\mathcal{H}}+d_{\mathrm{eff}}(λ)\ln T\big)$的界，其中$d_{\mathrm{eff}}(λ)$是RKHS复杂度的度量。尽管在无限维空间中工作，由于RKHS的再生性质，所得归约导出的算法在实践中是可计算的。