論文の概要: Near-Optimal Regret in Adversarial Kernel Bandits
- arxiv url: http://arxiv.org/abs/2605.26585v1
- Date: Tue, 26 May 2026 06:10:24 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-27 17:51:41.696749
- Title: Near-Optimal Regret in Adversarial Kernel Bandits
- Title（参考訳）: 逆カーネル帯域における準最適レグレット
- Authors: Yu-Jie Zhang, Hao Qiu, Jonathan Scarlett, Kevin Jamieson,
- Abstract要約: 本稿では,各ラウンドにおける損失が任意の有界要素によって誘導される逆カーネルバンドイット問題について検討する。
我々の主な結果は、$widetildeObig(sqrtT, d_*(),log|X|big)$, ここでは$d_*()$は有効次元の広く解釈された概念である。
- 参考スコア（独自算出の注目度）: 50.68324062892194
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the adversarial kernel bandit problem, in which the loss at each round is induced by an arbitrary bounded element of a reproducing kernel Hilbert space (RKHS). We propose an exponential-weights algorithm built on a regularized importance-weighted loss estimator, together with an explicit correction term that cancels the bias introduced by the regularization. Our main result bounds the regret by $\widetilde{O}\big(\sqrt{T\, d_*(λ)\,\log|{X}|}\big)$, where $d_*(λ)$ is a widely-adopted notion of effective dimension that captures the complexity of the kernel. Up to logarithmic factors, this matches the known rate achieved in the related stochastic kernel bandit problem. A notable application is the Matérn$(ν,d)$ kernel with smoothness parameter $ν$ on $\mathbb{R}^d$, for which our bound specializes to $\widetilde{O}\big(T^{(ν+d)/(2ν+d)}\big)$, improving over the best-known prior rate of Chatterji et al. [2019] while simultaneously removing the rank-one adversary assumption required by their analysis. Moreover, this rate is the same as the known optimal rate for stochastic kernel bandits, and also matches a lower bound from concurrent work up to a $\log T$ factor.
- Abstract（参考訳）: 本稿では、各ラウンドにおける損失が再生カーネルヒルベルト空間(RKHS)の任意の有界要素によって誘導される逆カーネルバンドイット問題について検討する。
本稿では,正規化重み付き損失推定器上に構築した指数重み付けアルゴリズムと,正規化によるバイアスを解消する明示的な補正項を提案する。
我々の主な結果は、$\widetilde{O}\big(\sqrt{T\, d_*(λ)\,\log|{X}|}\big)$, ここで $d_*(λ)$ は、カーネルの複雑さを捉えた有効次元の概念である。
対数的因子により、これは関連する確率的カーネルバンドイット問題において達成された既知の速度と一致する。
注目すべき応用は滑らか性パラメータ $ν$ on $\mathbb{R}^d$ で、この境界は $\widetilde{O}\big(T^{(ν+d)/(2ν+d)}\big)$ に特殊化され、Chatterji et al [2019] の最もよく知られた先行レートよりも改善され、同時に解析によって要求されるランク1逆の仮定を除去する。
さらに、このレートは確率的カーネルブレイビットの既知の最適レートと同じであり、並行処理から$\log T$ factorまでの低いバウンドと一致する。
関連論文リスト
- Nearly-Optimal Algorithm for Adversarial Kernelized Bandits [5.753274939310764]
本稿では,敵対的環境下での核化バンディット(ガウス過程バンディットとも呼ばれる)について検討する。
指数関数的重み付けアルゴリズムは$tildeO(sqrtT _T)$逆後悔を達成し,$T$と$_T$はラウンド数と最大情報ゲインを示す。
論文 参考訳（メタデータ） (2026-05-11T09:56:18Z) - Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hypersphere [5.753274939310764]
本稿では,ガウス過程(GP)バンディット問題に対するアルゴリズムに依存しない最悪の下界について,頻繁な設定で検討する。
具体的には,GPバンディットにおいて最も広く用いられているカーネル関数の1つである2乗指数関数(SE)カーネルに着目した。
任意のアルゴリズムが$(sqrtT (ln T)d (ln ln T)-d)$ cumulative regret, ここでは$T$と$d$は超球面領域の歩数と次元を表す。
論文 参考訳（メタデータ） (2026-02-20T02:17:47Z) - Differential Privacy in Kernelized Contextual Bandits via Random Projections [8.658538065693206]
コンテキストによるカーネルの帯域幅の問題について考察する。
基礎となる報酬関数は、既知の再生ケルネルヒルベルト空間に属する。
我々は、$widetildemathcalO(sqrtgamma_TT+fracgamma_Tvarepsilon_mathrmDP)の最先端の累積後悔を実現する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-07-18T03:54:49Z) - Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。
既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。
G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
論文 参考訳（メタデータ） (2024-01-14T14:14:19Z) - Adversarial Contextual Bandits Go Kernelized [21.007410990554522]
本研究では、ヒルベルト核空間に属する損失関数を組み込むことにより、逆線形文脈帯域におけるオンライン学習の問題を一般化する。
本稿では,損失関数を推定し,ほぼ最適の後悔の保証を再現するための新しい楽観的偏り推定器を提案する。
論文 参考訳（メタデータ） (2023-10-02T19:59:39Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。
O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。
さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
論文 参考訳（メタデータ） (2021-10-15T00:54:04Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。
代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文 参考訳（メタデータ） (2020-06-12T10:21:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。