将动态后悔值问题转化为函数空间中的静态后悔,实现更优的在线优化性能。
Dynamic Regret Reduces to Kernelized Static Regret
- 通过再生核希尔伯特空间构造函数空间,将动态后悔转为静态问题。
- 在线性损失下达到最优动态后悔界,且适用于任意损失序列。
- 算法可计算且对复杂度自适应,适合高维在线学习场景。
我们研究在线凸优化中的动态后悔问题,目标是使累积损失相对于任意参考序列保持较低。通过观察到在 $ Wigsubseteqb R^d$ 中与任意比较序列 $u_1, dots,u_T$ 竞争,等价于在函数空间中与固定比较函数 $u:[1,T] o W$ 竞争,我们将动态后悔最小化问题重新建模为函数空间中的静态后悔问题。通过精心构建再生核希尔伯特空间(RKHS),该还原方法在线性损失设定下恢复了最优动态后悔界 $R_T(u_1, dots,u_T) = O( sqrt{ sum_t norm{u_t - u_{t-1}} T})$,并得到新的无量纲和方向自适应动态后悔界。此外,不同于仅适用于线性损失的以往动态转静态还原,本方法适用于任意损失序列,可在指数凹性和非正则线性回归设置中恢复 $ O( norm{u}^2_{ H} + d_{ eff}(λ) ln T)$ 的边界,其中 $d_{ eff}(λ)$ 是 RKHS 复杂度的度量。尽管工作于无限维空间,由于 RKHS 的再生性质,所导出算法仍具有实际可计算性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。