論文の概要: On the Sublinear Regret of GP-UCB

• arxiv url: http://arxiv.org/abs/2307.07539v2
• Date: Mon, 14 Aug 2023 17:22:21 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-15 19:11:26.511404
• Title: On the Sublinear Regret of GP-UCB
• Title（参考訳）: GP-UCBのサブ線形回帰について
• Authors: Justin Whitehouse, Zhiwei Steven Wu, Aaditya Ramdas
• Abstract要約: ガウス過程上信頼境界 (GP-UCB) アルゴリズムは, ほぼ最適の後悔率を有することを示す。 私たちの改善は、基盤となるカーネルの滑らかさに比例してカーネルリッジ推定を正規化するという、重要な技術的貢献に依存しています。
• 参考スコア（独自算出の注目度）: 58.25014663727544
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the kernelized bandit problem, a learner aims to sequentially compute the optimum of a function lying in a reproducing kernel Hilbert space given only noisy evaluations at sequentially chosen points. In particular, the learner aims to minimize regret, which is a measure of the suboptimality of the choices made. Arguably the most popular algorithm is the Gaussian Process Upper Confidence Bound (GP-UCB) algorithm, which involves acting based on a simple linear estimator of the unknown function. Despite its popularity, existing analyses of GP-UCB give a suboptimal regret rate, which fails to be sublinear for many commonly used kernels such as the Mat\'ern kernel. This has led to a longstanding open question: are existing regret analyses for GP-UCB tight, or can bounds be improved by using more sophisticated analytical techniques? In this work, we resolve this open question and show that GP-UCB enjoys nearly optimal regret. In particular, our results yield sublinear regret rates for the Mat\'ern kernel, improving over the state-of-the-art analyses and partially resolving a COLT open problem posed by Vakili et al. Our improvements rely on a key technical contribution -- regularizing kernel ridge estimators in proportion to the smoothness of the underlying kernel $k$. Applying this key idea together with a largely overlooked concentration result in separable Hilbert spaces (for which we provide an independent, simplified derivation), we are able to provide a tighter analysis of the GP-UCB algorithm.
• Abstract（参考訳）: カーネル化帯域問題において、学習者は、逐次選択された点におけるノイズ評価のみを与えられた再生カーネルヒルベルト空間に横たわる関数の最適度を逐次計算することを目的とする。 特に、学習者は後悔を最小限に抑えることを目的としており、これは選択の最適度を測る尺度である。 おそらく最も一般的なアルゴリズムは、未知関数の単純な線形推定子に基づいて行動するガウス過程uper confidence bound (gp-ucb)アルゴリズムである。 その人気にもかかわらず、既存のGP-UCBの分析は、Mate\'ernカーネルのような多くのよく使われるカーネルのサブライン化に失敗する、最適以下の後悔率を与えている。 既存のGP-UCBの後悔の分析は厳密なのか、それともより洗練された分析技術を用いて境界を改善することができるのか? 本研究では,GP-UCBがほぼ最適に後悔していることを示す。 特に,この結果はmat\'ernカーネルに対して,最先端解析よりも改善し,vakiliらによって提起されたcoltオープン問題を部分的に解決した。 私たちの改善は重要な技術的貢献に依存します -- 基盤となるカーネル$k$の滑らかさに比例してカーネルリッジ推定を正規化します。 この重要なアイデアと概ね見過ごされる濃度を組み合わせることで、分離可能なヒルベルト空間(独立で簡明な導出を提供する)となり、gp-ucbアルゴリズムのより厳密な解析が可能になる。

関連論文リスト

• Regret Analysis for Randomized Gaussian Process Upper Confidence Bound [9.967062483758632]
  本稿では,GP-UCBの改良型であるGP-UCBのランダム化変異を解析する。 両方の後悔解析において、IRGP-UCBは入力領域が有限であれば信頼パラメータを増大させることなく、サブ線形後悔上限を達成する。
  論文  参考訳（メタデータ） (2024-09-02T06:49:29Z)
• Regret Optimality of GP-UCB [12.323109084902228]
  ガウス過程 上信頼境界 (GP-UCB) は、ノイズの多い観測でブラックボックス関数を最適化する最も一般的な方法の1つである。 GP-UCB の単純かつ累積的後悔の両面に新たな上限を確立する。 同じレベルの探索で、GP-UCBは単純かつ累積的後悔の両方において、同時に最適性を達成することができる。
  論文  参考訳（メタデータ） (2023-12-03T13:20:08Z)
• Quantum Bayesian Optimization [64.58749619145908]
  本稿では,量子ガウスプロセスアップパー信頼度境界(Q-GP-UCB)アルゴリズムを提案する。 O(polylog T) は古典的設定における Omega(sqrt(T)) の左下限よりもかなり小さい。 線形核を持つQ-GP-UCBは、新しい信頼楕円体解析により、量子線形 UCB アルゴリズムよりも小さな後悔を実現する。
  論文  参考訳（メタデータ） (2023-10-09T03:10:42Z)
• Randomized Gaussian Process Upper Confidence Bound with Tighter Bayesian Regret Bounds [9.89553853547974]
  本研究はまず,RGP-UCBの後悔解析をガンマ分布を含むより広範な分布に一般化する。 本稿では,2パラメータ指数分布に基づく改良されたRGP-UCBを提案する。 IRGP-UCBの広汎な実験による有効性を示す。
  論文  参考訳（メタデータ） (2023-02-03T02:48:48Z)
• Sample-Then-Optimize Batch Neural Thompson Sampling [50.800944138278474]
  我々はトンプソンサンプリング(TS)ポリシーに基づくブラックボックス最適化のための2つのアルゴリズムを提案する。 入力クエリを選択するには、NNをトレーニングし、トレーニングされたNNを最大化してクエリを選択するだけです。 我々のアルゴリズムは、大きなパラメータ行列を逆転する必要性を助長するが、TSポリシーの妥当性は保たれている。
  論文  参考訳（メタデータ） (2022-10-13T09:01:58Z)
• On the Benefits of Large Learning Rates for Kernel Methods [110.03020563291788]
  本稿では,カーネル手法のコンテキストにおいて,現象を正確に特徴付けることができることを示す。 分離可能なヒルベルト空間における2次対象の最小化を考慮し、早期停止の場合、学習速度の選択が得られた解のスペクトル分解に影響を及ぼすことを示す。
  論文  参考訳（メタデータ） (2022-02-28T13:01:04Z)
• Meta-Learning Hypothesis Spaces for Sequential Decision-making [79.73213540203389]
  オフラインデータ(Meta-KeL)からカーネルをメタ学習することを提案する。 穏やかな条件下では、推定されたRKHSが有効な信頼セットを得られることを保証します。 また,ベイズ最適化におけるアプローチの有効性を実証的に評価した。
  論文  参考訳（メタデータ） (2022-02-01T17:46:51Z)
• Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
  カーネル化されたバンディットアルゴリズムは、この問題に対して強い経験的および理論的性能を示した。 本稿では、未知関数を$epsilon$-一様近似で近似できるエンフェミス特定カーネル化帯域設定を、ある再生カーネルヒルベルト空間(RKHS)において有界ノルムを持つ関数で導入する。 提案アルゴリズムは,不特定性に関する事前知識を伴わず,$epsilon$への最適依存を実現する。
  論文  参考訳（メタデータ） (2021-11-09T09:00:02Z)
• Weighted Gaussian Process Bandits for Non-stationary Environments [30.49357960656324]
  We developed WGP-UCB, a novel UCB-type algorithm based on weighted Gaussian process regression。 鍵となる課題は、無限次元の特徴写像を扱う方法である。 重み付き最大情報ゲインに対して、普遍的上界と重み依存上界を提供する。
  論文  参考訳（メタデータ） (2021-07-06T03:37:33Z)
• No-Regret Algorithms for Time-Varying Bayesian Optimization [0.0]
  我々は,時間変動環境を捉えるために,一般変動予算モデルを採用する。 R-GP-UCBとSW-GP-UCBの2つのGP-UCB型アルゴリズムを紹介します。 この結果は,線形カーネルを用いた場合の先行線形バンディット結果を回復するだけでなく,時間変動ガウス過程バンディットの先行後悔解析を補完するものである。
  論文  参考訳（メタデータ） (2021-02-11T22:35:32Z)

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

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