論文の概要: 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の課題に対処した。
関連論文リスト
- 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) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for
Online Convex Optimization [93.14387921542709]
非定常環境におけるオンライン凸最適化について検討する。
エンファンダイナミックな後悔をパフォーマンス指標として選びます。
本研究では,スムーズさを生かし,動的後悔の中で$T$に依存する新しいオンラインアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - 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) - Optimal Order Simple Regret for Gaussian Process Bandits [6.84224661918159]
純粋な探索アルゴリズムは既存の境界よりもかなり厳密であることを示す。
この後悔は、カーネル上の低い境界が知られている場合に、対数的に最適であることを示す。
論文 参考訳（メタデータ） (2021-08-20T16:49:32Z) - Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel
Optimization [62.87181271021217]
機械学習に多くの応用がある非SBO問題を考察する。
本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-05T18:28:42Z) - 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) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-14T10:42:23Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。