論文の概要: Convergence Rates of Gaussian Process Thompson Sampling for Efficient Global Optimization

• arxiv url: http://arxiv.org/abs/2610.19925v1
• Date: Wed, 14 Oct 2026 10:15:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-15 21:06:16.097151
• Title: Convergence Rates of Gaussian Process Thompson Sampling for Efficient Global Optimization
• Title（参考訳）: 効率的なグローバル最適化のためのガウス過程トンプソンサンプリングの収束率
• Abstract要約: ガウス過程トンプソンサンプリング(GP-TS)の無雑音観測における収束速度について検討した。 この制限により、我々はガウス過程キャップトンプソンサンプリング(GP-CTS)を提案する。 この修正は対数ペナルティをうまく排除し、離散実装と連続実装の両方に対してミニマックス最適率$(N-/d)を達成している。
• 参考スコア（独自算出の注目度）: 6.38553502068596
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Efficient global optimization aims to identify a global optimum of an expensive black-box function within a limited evaluation budget $N$. We investigate the convergence rates of Gaussian process Thompson sampling (GP-TS) under noiseless observations, assuming a fixed objective function in a reproducing kernel Hilbert space (RKHS). For Matérn kernels with smoothness parameter $ν$ in dimension $d$, we establish a worst-case expected simple-regret upper bound of $O(N^{-ν/d}\sqrt{\log N})$ for both discrete GP-TS on sufficiently fine grids and its continuous counterpart. For the continuous implementation, we develop a nested-grid argument to control posterior sample paths over the entire domain. We further establish matching lower bounds of $Ω(N^{-5/2}\sqrt{\log N})$ for both implementations under a fixed one-dimensional Matérn-$5/2$ kernel, demonstrating that the logarithmic penalty is intrinsic to standard GP-TS in this setting. Motivated by this limitation, we propose Gaussian Process Capped Thompson Sampling (GP-CTS), which caps posterior sample paths using a valid RKHS norm upper bound while preserving optimism. This modification successfully eliminates the logarithmic penalty and achieves the minimax-optimal rate $Θ(N^{-ν/d})$ for both discrete and continuous implementations.
• Abstract（参考訳）: 効率的なグローバル最適化は、限られた評価予算$N$の範囲内で、高価なブラックボックス関数のグローバルな最適化を特定することを目的としている。 我々は、再生カーネルヒルベルト空間(RKHS)における固定目的関数を仮定し、ノイズのない観測下でのガウス過程トンプソンサンプリング(GP-TS)の収束率について検討する。 滑らかさパラメータ $ν$ in dimension $d$ を持つマテラン核に対しては、十分に微細な格子上の離散GP-TSと、その連続的な格子上での$O(N^{-ν/d}\sqrt{\log N})$の最悪のケース予測単純回帰上限を確立する。 連続的な実装のために、ドメイン全体の後部サンプルパスを制御するネスト-グリッド引数を開発する。 さらに、固定された1次元のマテラン-$5/2$カーネルの下で、両方の実装に対して$Ω(N^{-5/2}\sqrt{\log N})$の一致した下界を確立し、この設定において対数ペナルティが標準GP-TSに固有のものであることを示す。 この制限により,楽観性を保ちつつ,有効な RKHS 標準上界を用いて後部サンプルパスをカプセル化するガウス的プロセスキャップ型トンプソンサンプリング(GP-CTS)を提案する。 この修正は対数ペナルティをうまく排除し、離散的な実装と連続的な実装の両方に対して極小マックス-最適率(N^{-ν/d})$を達成する。

関連論文リスト

• Towards Scalable Persistence-Based Topological Optimization [44.16669776030478]
  永続性に基づく位相最適化は、点クラウド $X の部分集合 mathbbRd$ を $L(X) = ell(mathrmDgm(X))$ という形の目的を最小化することによって変形する。 実際、最適化は2つの結合した問題によって制限される: 永続ホモロジーは典型的にはサブサンプル上で計算され、結果として生じる位相勾配は非常にスパースであり、非ゼロ更新を受けるアンカーポイントはわずかである。
  論文  参考訳（メタデータ） (2026-05-09T15:47:20Z)
• Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization [85.91302339486673]
  我々は、s-正方形および非正方形不確実性集合の下で、一般的な政策パラメータ化を伴うロバストマルコフ決定過程(RMDP)について検討する。 無限状態空間に拡張する一般政策パラメタライゼーションに対する新しいリプシッツ・リプシッツ・スムースネス特性を証明した。 本研究では,S-正方形不確かさに対する勾配降下アルゴリズムと非正方形不確かさに対するFrank-Wolfeアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2026-02-11T21:44:20Z)
• Can SGD Handle Heavy-Tailed Noise? [6.111519084375339]
  Gradient Descent (SGD) は大規模最適化のための機械学習プロジェクトであるが、重尾雑音下での理論的挙動は理解されていない。 このような悪条件下でSGDが確実に成功できるかどうかを精査する。
  論文  参考訳（メタデータ） (2025-08-06T20:09:41Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
  機械学習とネットワーク最適化では、ミスの数と優れたキャッシュを最小化するため、シャッフルSGDのようなアルゴリズムが人気である。 本稿では任意のデータ順序付けによる収束特性SGDアルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2023-05-30T17:47:27Z)
• Lower Bounds on the Worst-Case Complexity of Efficient Global Optimization [11.523746174066702]
  我々は、その対応する再生核ヒルベルト空間(RKHS)における球の計量エントロピーの観点から、効率的な大域最適化の複雑さに対する統一された下界を導出する。 この下界は、一般に使用される2乗指数核とマタン核の非適応探索アルゴリズムによって達成された上界にほぼ一致することを示す。
  論文  参考訳（メタデータ） (2022-09-20T11:57:13Z)
• 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)
• Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
  現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。 本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。 次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-10T13:07:44Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  関数評価のみに基づく滑らかな関数のグローバル最小化を考える。 本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
  論文  参考訳（メタデータ） (2020-12-22T12:59:30Z)
• Multi-Scale Zero-Order Optimization of Smooth Functions in an RKHS [19.252319300590653]
  ブラックボックス関数 $f:mathcalX mapto mathbbR$ は、$f$がよりスムーズで、与えられたカーネル $K$ に関連する RKHS の有界ノルムを持つという仮定の下で最適化される。 本稿では,H の局所多項式 (LP) 推定器を用いて通常の GP 代理モデルを拡張した新しいアルゴリズム (textttLP-GP-UCB) を提案する。
  論文  参考訳（メタデータ） (2020-05-11T01:55:39Z)

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

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