論文の概要: Instance-Dependent Regret Analysis of Kernelized Bandits
- arxiv url: http://arxiv.org/abs/2203.06297v1
- Date: Sat, 12 Mar 2022 00:53:59 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-15 14:02:30.612093
- Title: Instance-Dependent Regret Analysis of Kernelized Bandits
- Title（参考訳）: カーネル化帯域のインスタンス依存レグレト解析
- Authors: Shubhanshu Shekhar, Tara Javidi
- Abstract要約: 雑音の多いゼロオーダーオーラを問合せするための適応戦略を設計することを含む、カーネル化された帯域幅問題について検討する。
正規化された累積後悔を解消する(関数クラス上)アルゴリズムに対して、不一致依存的後悔の下限を導出する。
- 参考スコア（独自算出の注目度）: 19.252319300590653
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the kernelized bandit problem, that involves designing an adaptive
strategy for querying a noisy zeroth-order-oracle to efficiently learn about
the optimizer of an unknown function $f$ with a norm bounded by $M<\infty$ in a
Reproducing Kernel Hilbert Space~(RKHS) associated with a positive definite
kernel $K$. Prior results, working in a \emph{minimax framework}, have
characterized the worst-case~(over all functions in the problem class) limits
on regret achievable by \emph{any} algorithm, and have constructed algorithms
with matching~(modulo polylogarithmic factors) worst-case performance for the
\matern family of kernels. These results suffer from two drawbacks. First, the
minimax lower bound gives no information about the limits of regret achievable
by the commonly used algorithms on specific problem instances. Second, due to
their worst-case nature, the existing upper bound analysis fails to adapt to
easier problem instances within the function class. Our work takes steps to
address both these issues. First, we derive \emph{instance-dependent} regret
lower bounds for algorithms with uniformly~(over the function class) vanishing
normalized cumulative regret. Our result, valid for all the practically
relevant kernelized bandits algorithms, such as, GP-UCB, GP-TS and
SupKernelUCB, identifies a fundamental complexity measure associated with every
problem instance. We then address the second issue, by proposing a new minimax
near-optimal algorithm which also adapts to easier problem instances.
- Abstract（参考訳）: 我々は,無名の関数$f$ のオプティマイザを再生カーネル hilbert space~(rkhs) において$m<\infty$ で有界なノルムで効率的に学習するために,ノイズの多いゼロ次oracle に問い合わせる適応戦略を設計することを含む,カーネル化されたバンドイット問題について検討する。
以前の結果は \emph{minimax framework} で動作し、(問題クラスのすべての関数よりも)最悪の場合を、 \emph{any} アルゴリズムによって達成可能な後悔の限界に特徴付け、(モジュロ多対数因子) カーネルファミリーの最悪の場合のパフォーマンスをマッチングするアルゴリズムを構築した。
これらの結果には2つの欠点がある。
第一に、ミニマックスの下限は、特定の問題インスタンスでよく使われるアルゴリズムによって達成される後悔の限界に関する情報を与えない。
第二に、その最悪の性質のため、既存の上限解析は関数クラス内のより簡単な問題インスタンスに適応できない。
私たちの仕事はこれらの問題に対処するためのステップを踏む。
まず、正規化された累積的後悔を解消する(関数クラス上)アルゴリズムに対する「emph{instance-dependent} regret lower bounds」を導出する。
その結果,GP-UCB,GP-TS,SupKernelUCBなどの実効的なカーネル化バンディットアルゴリズムに有効であり,すべての問題インスタンスに関連する基本的な複雑性尺度を同定した。
次に,問題インスタンスにも適応する新しいminimaxニアオプティマイズアルゴリズムを提案することで,第2の課題に対処した。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Second Order Methods for Bandit Optimization and Control [34.51425758864638]
我々は,大規模な凸関数に対して,このアルゴリズムが最適($kappa$-2020と呼ぶ凸関数の観点で)となることを示す。
また,メモリを用いたオンライン凸最適化への2次帯域幅アルゴリズムの適用について検討した。
論文 参考訳（メタデータ） (2024-02-14T04:03:38Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。
本稿では,2種類のミニマックスアルゴリズムを提案する。
そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
論文 参考訳（メタデータ） (2023-02-08T01:42:45Z) - A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for
Nonconvex Functional Constrained Optimization [27.07082875330508]
制約のない不等式問題は、マルチクラスネイマンオラクルのような多くの機械学習問題をモデル化するために用いられる。
このような緩やかな規則性の条件下では、値損失の交互化と制約違反の低減のバランスをとることは困難である。
本稿では,新しい不等式制約問題アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-07-12T16:30:34Z) - Asymptotic Instance-Optimal Algorithms for Interactive Decision Making [35.76184529520015]
本稿では,軽度条件下での有限個の判定問題に対して,対話型意思決定のための最初のインスタンス最適化アルゴリズムを設計する。
本研究の結果は, 具体的問題に着目し, 多腕バンディットの古典的ギャップ依存境界と, 線形バンディットに関する先行研究を復元した。
論文 参考訳（メタデータ） (2022-06-06T02:56:10Z) - Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
カーネル化されたバンディットアルゴリズムは、この問題に対して強い経験的および理論的性能を示した。
本稿では、未知関数を$epsilon$-一様近似で近似できるエンフェミス特定カーネル化帯域設定を、ある再生カーネルヒルベルト空間(RKHS)において有界ノルムを持つ関数で導入する。
提案アルゴリズムは,不特定性に関する事前知識を伴わず,$epsilon$への最適依存を実現する。
論文 参考訳（メタデータ） (2021-11-09T09:00:02Z) - 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) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。