論文の概要: A General $\widetildeΩ(\sqrt{T γ_T})$ Lower Bound for Kernel Bandits

• arxiv url: http://arxiv.org/abs/2610.11082v1
• Date: Thu, 08 Oct 2026 01:44:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-10 02:36:53.729033
• Title: A General $\widetildeΩ(\sqrt{T γ_T})$ Lower Bound for Kernel Bandits
• Title（参考訳）: A general $\widetildeΩ(\sqrt{T γ_T})$ lower bound for Kernel Bandits
• Abstract要約: カーネルバンディット問題は、ノイズフィードバックで未知の関数を逐次最適化することである。 ミニマックス最適化スケーリングは、正確に$(sqrtT_T)$(定数係数内)であり、Metérn-$$カーネルであることを示す。
• 参考スコア（独自算出の注目度）: 37.12020581383693
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The kernel bandit problem consists of sequentially optimizing an unknown function with noisy feedback, where the function has bounded norm in a given Reproducing Kernel Hilbert Space (RKHS). A central quantity in the regret analysis of kernel bandits is the maximum information gain $γ_T$. In particular, the best existing upper bounds scale as $\sqrt{Tγ_T}$ up to log factors, and nearly-matching lower bounds have been derived for specific kernels such as squared exponential and Matérn. However, lower bounds for general kernels are lacking, thus making it unclear in what generality the upper bounds are near-optimal. In this paper, we establish a general $Ω(\sqrt{Tγ_T/\log T})$ minimax regret lower bound for non-constant continuous kernels on compact domains, establishing near-optimality (within log factors) in a very general sense. We show that the log factor appearing in this bound is unavoidable in general, but that it can be removed under certain conditions. Among other things, our findings imply that the minimax-optimal scaling is exactly $Θ(\sqrt{Tγ_T})$ (i.e., within constant factors) for the Matérn-$ν$ kernel with $ν\in (0,2)$, $γ$-exponential kernel with $γ\in (0,2)$, and certain piecewise-polynomial kernels.
• Abstract（参考訳）: カーネルバンドイット問題は、与えられた再生ケルネルヒルベルト空間(RKHS)において、関数が有界ノルムを持つノイズフィードバックを持つ未知の関数を逐次最適化することからなる。 カーネルブレイディットの後悔解析における中心的な量は、最大情報ゲイン$γ_T$である。 特に、最良の上界は$\sqrt{Tγ_T}$ の対数因子までスケールし、平方指数やマテランのような特定の核に対してほぼ一致する下界が導出された。 しかし、一般の核に対する下界は不足しているため、上界がどの一般性はほぼ最適かは不明である。 本稿では,コンパクト領域上の非コンスタント連続核に対する最小限の最小限の最小限の最小限の最小限の値として,一般の意味での準最適性(ログ係数)を確立する。 この境界に現れるログ係数は一般には避けられないが、特定の条件下で取り除くことができることを示す。 とりわけ、最小値-最適スケーリングは、$ν\in (0,2)$,$γ$-指数核と$γ\in (0,2)$,および一部の分数-多項式核に対して、正確に$(\sqrt{Tγ_T})$(すなわち定数因子内で)であることを示す。

関連論文リスト

• Near-Optimal Regret in Adversarial Kernel Bandits [50.68324062892194]
  本稿では,各ラウンドにおける損失が任意の有界要素によって誘導される逆カーネルバンドイット問題について検討する。 我々の主な結果は、$widetildeObig(sqrtT, d_*(),log|X|big)$, ここでは$d_*()$は有効次元の広く解釈された概念である。
  論文  参考訳（メタデータ） (2026-05-26T06:10:24Z)
• 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)
• Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
  分散オンライン凸最適化(D-OCO)は、局所計算と通信のみを用いて、グローバルな損失関数の列を最小化するように設計されている。 我々は,凸関数と強凸関数の残差を$tildeO(nrho-1/4sqrtT)$と$tildeO(nrho-1/2log T)$に削減できる新しいD-OCOアルゴリズムを開発した。 我々の分析によると、射影自由多様体は$O(nT3/4)$と$O(n)を達成できる。
  論文  参考訳（メタデータ） (2024-02-14T13:44:16Z)
• Stronger Coreset Bounds for Kernel Density Estimators via Chaining [0.5454560484178483]
  本稿では,カーネル関数のコアセットの複雑性を改善するために,差分法と連鎖法を適用した。 我々の結果は、ガウスカーネルとラプラシアカーネルのコアセットとして$Obig(fracsqrtdvarepsilonsqrtloglog frac1varepsilonbig)をランダムに生成する時間アルゴリズムを与える。 また、最もよく知られた$Obig(fracsqrtdvarepsilonsqrtlog (2max1,
  論文  参考訳（メタデータ） (2023-10-12T17:44:59Z)
• Non-asymptotic spectral bounds on the $\varepsilon$-entropy of kernel classes [4.178980693837599]
  この話題は、カーネルベースの手法の現代的な統計理論において重要な方向である。 我々は、我々の境界の多くの結果について議論し、それらが一般のカーネルのバウンドよりもかなり厳密であることを示す。
  論文  参考訳（メタデータ） (2022-04-09T16:45:22Z)
• 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)
• Tight Regret Bounds for Bayesian Optimization in One Dimension [47.51554144092745]
  ガウス過程とガウスサンプリングノイズの下で,ベイズ最適化(BO)の問題を一次元で考察する。 我々は、カーネル上のかなり穏やかな技術的仮定の下で、最大$T$は$Omega(sqrtT)$および$O(sqrtTlog T)$として振る舞う。
  論文  参考訳（メタデータ） (2018-05-30T03:33:37Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。