論文の概要: Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hypersphere
- arxiv url: http://arxiv.org/abs/2602.17940v1
- Date: Fri, 20 Feb 2026 02:17:47 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-23 18:01:41.205156
- Title: Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hypersphere
- Title（参考訳）: 超球面における正方形指数核を持つガウス過程帯域に対するタイターレグレト下界
- Authors: Shogo Iwazaki,
- Abstract要約: 本稿では,ガウス過程(GP)バンディット問題に対するアルゴリズムに依存しない最悪の下界について,頻繁な設定で検討する。
具体的には,GPバンディットにおいて最も広く用いられているカーネル関数の1つである2乗指数関数(SE)カーネルに着目した。
任意のアルゴリズムが$(sqrtT (ln T)d (ln ln T)-d)$ cumulative regret, ここでは$T$と$d$は超球面領域の歩数と次元を表す。
- 参考スコア（独自算出の注目度）: 5.753274939310764
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study an algorithm-independent, worst-case lower bound for the Gaussian process (GP) bandit problem in the frequentist setting, where the reward function is fixed and has a bounded norm in the known reproducing kernel Hilbert space (RKHS). Specifically, we focus on the squared exponential (SE) kernel, one of the most widely used kernel functions in GP bandits. One of the remaining open questions for this problem is the gap in the \emph{dimension-dependent} logarithmic factors between upper and lower bounds. This paper partially resolves this open question under a hyperspherical input domain. We show that any algorithm suffers $Ω(\sqrt{T (\ln T)^{d} (\ln \ln T)^{-d}})$ cumulative regret, where $T$ and $d$ represent the total number of steps and the dimension of the hyperspherical domain, respectively. Regarding the simple regret, we show that any algorithm requires $Ω(ε^{-2}(\ln \frac{1}ε)^d (\ln \ln \frac{1}ε)^{-d})$ time steps to find an $ε$-optimal point. We also provide the improved $O((\ln T)^{d+1}(\ln \ln T)^{-d})$ upper bound on the maximum information gain for the SE kernel. Our results guarantee the optimality of the existing best algorithm up to \emph{dimension-independent} logarithmic factors under a hyperspherical input domain.
- Abstract（参考訳）: 本稿では,ガウス過程(GP)バンディット問題に対するアルゴリズム非依存の最悪の下界について,報酬関数が固定され,既知の再生カーネルヒルベルト空間(RKHS)に有界ノルムを持つような頻繁な条件下で検討する。
具体的には,GPバンディットにおいて最も広く用いられているカーネル関数の1つである2乗指数関数(SE)カーネルに着目した。
この問題の残る未解決問題の1つは、上界と下界の間の \emph{dimension-dependent} 対数係数のギャップである。
本稿では、超球面入力領域の下で、この開問題を部分的に解決する。
任意のアルゴリズムが$Ω(\sqrt{T (\ln T)^{d} (\ln \ln T)^{-d}})$ cumulative regret, ここでは$T$と$d$はそれぞれ超球面領域の歩数と次元を表す。
単純な後悔については、任意のアルゴリズムが$Ω(ε^{-2}(\ln \frac{1}ε)^d (\ln \ln \frac{1}ε)^{-d})$ ε$-最適点を見つけるための時間ステップを必要とすることを示す。
また、改良された$O((\ln T)^{d+1}(\ln \ln T)^{-d})$上界をSEカーネルの最大情報ゲインとして提供する。
この結果から,超球面入力領域下での既設最適アルゴリズムの対数係数の最適性が保証された。
関連論文リスト
- 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) - Lower Bounds on the Worst-Case Complexity of Efficient Global
Optimization [11.523746174066702]
我々は、その対応する再生核ヒルベルト空間(RKHS)における球の計量エントロピーの観点から、効率的な大域最適化の複雑さに対する統一された下界を導出する。
この下界は、一般に使用される2乗指数核とマタン核の非適応探索アルゴリズムによって達成された上界にほぼ一致することを示す。
論文 参考訳（メタデータ） (2022-09-20T11:57:13Z) - Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。
本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
論文 参考訳（メタデータ） (2022-09-09T08:54:13Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Order-Optimal Error Bounds for Noisy Kernel-Based Bayesian Quadrature [42.129843613950285]
我々は、Match'ern-$nu$ kernel を用いて、Em Reproduction Kernel Hilbert Space (RKHS) の関数を考える。
ブラックボックスクエリが分散$sigma2$のガウスノイズを受ける場合、最大で$T$のアルゴリズムは平均絶対誤差$Omega(T-fracnud-1 + sigma T-frac12)$を発生しなければならない。
論文 参考訳（メタデータ） (2022-02-22T01:49:41Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。