論文の概要: Gaussian Process Bandit Optimization with Few Batches

• arxiv url: http://arxiv.org/abs/2110.07788v1
• Date: Fri, 15 Oct 2021 00:54:04 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-18 13:17:36.962372
• Title: Gaussian Process Bandit Optimization with Few Batches
• Title（参考訳）: 少数バッチによるガウス過程帯域最適化
• Authors: Zihan Li and Jonathan Scarlett
• Abstract要約: 有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。 O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。 さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
• 参考スコア（独自算出の注目度）: 49.896920704012395
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we consider the problem of black-box optimization using Gaussian Process (GP) bandit optimization with a small number of batches. Assuming the unknown function has a low norm in the Reproducing Kernel Hilbert Space (RKHS), we introduce a batch algorithm inspired by batched finite-arm bandit algorithms, and show that it achieves the cumulative regret upper bound $O^\ast(\sqrt{T\gamma_T})$ using $O(\log\log T)$ batches within time horizon $T$, where the $O^\ast(\cdot)$ notation hides dimension-independent logarithmic factors and $\gamma_T$ is the maximum information gain associated with the kernel. This bound is near-optimal for several kernels of interest and improves on the typical $O^\ast(\sqrt{T}\gamma_T)$ bound, and our approach is arguably the simplest among algorithms attaining this improvement. In addition, in the case of a constant number of batches (not depending on $T$), we propose a modified version of our algorithm, and characterize how the regret is impacted by the number of batches, focusing on the squared exponential and Mat\'ern kernels. The algorithmic upper bounds are shown to be nearly minimax optimal via analogous algorithm-independent lower bounds.
• Abstract（参考訳）: 本稿では,ガウス過程(GP)バンドレート最適化を用いたブラックボックス最適化の問題について,少数のバッチで検討する。 未知関数が再生成核ヒルベルト空間 (rkhs) に低ノルムを持つと仮定すると、バッチ有限アームバンディットアルゴリズムに触発されたバッチアルゴリズムを導入し、累積後悔の上限値 $o^\ast(\sqrt{t\gamma_t})$ using $o(\log\log t)$ batches in time horizon $t$, ここで $o^\ast(\cdot)$ notation は次元非依存対数因子を隠蔽し、$\gamma_t$ はカーネルに関連する最大情報ゲインであることを示す。 このバウンドは、いくつかの興味を持つカーネルにとってほぼ最適であり、典型的な$o^\ast(\sqrt{t}\gamma_t)$バウンドで改善される。 さらに, 一定の数のバッチ($T$に依存しない)の場合, アルゴリズムの修正版を提案し, 帰納的指数とMate\'ernカーネルに焦点をあてて, バッチ数によって後悔がどう影響するかを特徴付ける。 アルゴリズム上界は、類似のアルゴリズムに依存しない下界によって、ほぼ極小となる。

関連論文リスト

• Achieving Tractable Minimax Optimal Regret in Average Reward MDPs [19.663336027878408]
  我々は,$widetildemathrmO(sqrtmathrmsp(h*) S A T)$のミニマックス最適後悔を伴う最初の抽出可能なアルゴリズムを提案する。 注目すべきは、我々のアルゴリズムは$mathrmsp(h*)$に関する事前情報を必要としないことである。
  論文  参考訳（メタデータ） (2024-06-03T11:53:44Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Lower Bounds on the Worst-Case Complexity of Efficient Global Optimization [11.523746174066702]
  我々は、その対応する再生核ヒルベルト空間(RKHS)における球の計量エントロピーの観点から、効率的な大域最適化の複雑さに対する統一された下界を導出する。 この下界は、一般に使用される2乗指数核とマタン核の非適応探索アルゴリズムによって達成された上界にほぼ一致することを示す。
  論文  参考訳（メタデータ） (2022-09-20T11:57:13Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
  カーネル化されたバンディットアルゴリズムは、この問題に対して強い経験的および理論的性能を示した。 本稿では、未知関数を$epsilon$-一様近似で近似できるエンフェミス特定カーネル化帯域設定を、ある再生カーネルヒルベルト空間(RKHS)において有界ノルムを持つ関数で導入する。 提案アルゴリズムは,不特定性に関する事前知識を伴わず,$epsilon$への最適依存を実現する。
  論文  参考訳（メタデータ） (2021-11-09T09:00:02Z)
• Optimal Order Simple Regret for Gaussian Process Bandits [6.84224661918159]
  純粋な探索アルゴリズムは既存の境界よりもかなり厳密であることを示す。 この後悔は、カーネル上の低い境界が知られている場合に、対数的に最適であることを示す。
  論文  参考訳（メタデータ） (2021-08-20T16:49:32Z)
• 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)
• Thresholded Lasso Bandit [70.17389393497125]
  Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。 一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
  論文  参考訳（メタデータ） (2020-10-22T19:14:37Z)
• 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)

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

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