Fugu-MT 論文翻訳(概要): Dynamic Regret Reduces to Kernelized Static Regret

論文の概要: Dynamic Regret Reduces to Kernelized Static Regret

arxiv url: http://arxiv.org/abs/2507.05478v1
Date: Mon, 07 Jul 2025 21:09:33 GMT
ステータス: 翻訳完了
システム内更新日: 2025-07-09 16:34:37.347513
Title: Dynamic Regret Reduces to Kernelized Static Regret
Title（参考訳）: 動的レグレットがカーネル化された静的レグレットに還元される
Authors: Andrew Jacobsen, Alessandro Rudi, Francesco Orabona, Nicolo Cesa-Bianchi,
Abstract要約: 本研究では,オンライン凸最適化において,任意のベンチマークシーケンスに対して低累積損失を達成することを目的とした動的後悔について検討する。再生ケルネルヒルベルト空間 (RKHS) の形で適切な関数空間を構築することにより、最適$R_T(u_1,ldots,u_T) = MathcalO(sqrtsum_t|u_t-u_t-1|T)$ dynamic regret guarantee。
参考スコア（独自算出の注目度）: 63.36965242404415
License: http://creativecommons.org/licenses/by/4.0/
Abstract: 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+d_{\mathrm{eff}}(\lambda)\ln T\big)$ bounds in exp-concave and improper linear regression settings, where $d_{\mathrm{eff}}(\lambda)$ 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.
Abstract（参考訳）: 本研究では,オンライン凸最適化において,任意のベンチマークシーケンスに対して低累積損失を達成することを目的とした動的後悔について検討する。任意のコンパレータの列と競合する$u_{1},\ldots,u_{T}$ in $\mathcal{W}\subseteq\mathbb{R}^{d}$は固定コンパレータ関数 $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+d_{\mathrm{eff}}(\lambda)\ln T\big)$ exp-concaveと不適切な線形回帰設定のバウンダリで、$d_{\mathrm{eff}}(\lambda)$はRKHSの複雑さの尺度である。無限次元空間で作業しているにもかかわらず、その結果、RKHSの再現性のために実際に計算可能なアルゴリズムが導かれる。

論文の概要: Dynamic Regret Reduces to Kernelized Static Regret

関連論文リスト