Fugu-MT 論文翻訳(概要): Sparsity-Based Interpolation of External, Internal and Swap Regret

論文の概要: Sparsity-Based Interpolation of External, Internal and Swap Regret

arxiv url: http://arxiv.org/abs/2502.04543v2
Date: Tue, 17 Jun 2025 19:29:10 GMT
ステータス: 翻訳完了
システム内更新日: 2025-06-19 16:34:05.29185
Title: Sparsity-Based Interpolation of External, Internal and Swap Regret
Title（参考訳）: 外部・内部・スワップレグレットの空間的補間
Authors: Zhou Lu, Y. Jennifer Sun, Zhiyu Zhang,
Abstract要約: 本稿では,オンライン学習におけるエキスパート問題に焦点をあてる。最適な$O(sqrtTlog d)$external regret bound when $dmathrmunif_phi=d$, the standard $tilde O(sqrtT)$ internal regret bound when $dmathrmself_phi=d-1$, and the optimal $tilde O(sqrtdT)$ swap regret bound in the worst case, we improve on existing algorithm in the intermediate regimes。
参考スコア（独自算出の注目度）: 4.753557469026313
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Focusing on the expert problem in online learning, this paper studies the interpolation of several performance metrics via $\phi$-regret minimization, which measures the total loss of an algorithm by its regret with respect to an arbitrary action modification rule $\phi$. With $d$ experts and $T\gg d$ rounds in total, we present a single algorithm achieving the instance-adaptive $\phi$-regret bound \begin{equation*} \tilde O\left(\min\left\{\sqrt{d-d^{\mathrm{unif}}_\phi+1},\sqrt{d-d^{\mathrm{self}}_\phi}\right\}\cdot\sqrt{T}\right), \end{equation*} where $d^{\mathrm{unif}}_\phi$ is the maximum amount of experts modified identically by $\phi$, and $d^{\mathrm{self}}_\phi$ is the amount of experts that $\phi$ trivially modifies to themselves. By recovering the optimal $O(\sqrt{T\log d})$ external regret bound when $d^{\mathrm{unif}}_\phi=d$, the standard $\tilde O(\sqrt{T})$ internal regret bound when $d^{\mathrm{self}}_\phi=d-1$ and the optimal $\tilde O(\sqrt{dT})$ swap regret bound in the worst case, we improve upon existing algorithms in the intermediate regimes. In addition, the computational complexity of our algorithm matches that of the standard swap-regret minimization algorithm due to (Blum and Mansour, 2007). Technically, building on the well-known reduction from $\phi$-regret minimization to external regret minimization on stochastic matrices, our main idea is to further convert the latter to online linear regression using Haar-wavelet-inspired matrix features. Then, by associating the complexity of each $\phi$ instance with its sparsity under the feature representation, we apply techniques from comparator-adaptive online learning to exploit the sparsity in this regression subroutine.
Abstract（参考訳）: 本稿では,オンライン学習における専門的問題に着目し,任意の行動修正規則である$\phi$-regret最小化($\phi$-regret minimization)によるいくつかのパフォーマンス指標の補間について検討する。合計$d$のエキスパートと$T\gg d$のラウンドで、インスタンス適応型$\phi$-regret bound \begin{equation*} \tilde O\left(\min\left\{\sqrt{d-d^{\mathrm{unif}}_\phi+1},\sqrt{d-d^{\mathrm{self}}_\phi}\right\cdot\sqrt{T}\right), \end{equation*} ここで$d^{\mathrm{unif}}_\phi$は、$\phi$と$d^{\mathrm{self}}_\phi$によって修正された専門家の最大値である。最適な$O(\sqrt{T\log d})$external regret bound if $d^{\mathrm{unif}}_\phi=d$, the standard $\tilde O(\sqrt{T})$ internal regret bound when $d^{\mathrm{self}}_\phi=d-1$, and the optimal $\tilde O(\sqrt{dT})$ swap regret bound in the worst case, we improve on existing algorithm in the intermediate regimes。さらに,本アルゴリズムの計算複雑性は, (Blum and Mansour, 2007) による標準スワップ-レグレット最小化アルゴリズムの計算量と一致する。技術的には、よく知られた$\phi$-regretの最小化から、確率行列に対する外部後悔の最小化への還元を基礎として、Haar-wavelet に着想を得た行列特徴を用いて、後者をオンライン線形回帰に変換することを目的としている。次に,各$\phi$インスタンスの複雑さと特徴表現の下でのスパーシティを関連付けることで,コンパレータ適応型オンライン学習の手法を適用し,この回帰サブルーチンのスパーシティを利用する。

論文の概要: Sparsity-Based Interpolation of External, Internal and Swap Regret

関連論文リスト