論文の概要: Delayed Feedback in Kernel Bandits
- arxiv url: http://arxiv.org/abs/2302.00392v1
- Date: Wed, 1 Feb 2023 12:03:19 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-02 13:08:00.660729
- Title: Delayed Feedback in Kernel Bandits
- Title（参考訳）: カーネルバンドにおける遅延フィードバック
- Authors: Sattar Vakili, Danyal Ahmed, Alberto Bernacchia, Ciara Pike-Burke
- Abstract要約: 未知の機能のブラックボックス最適化は、機械学習、学術研究、工業生産においてユビキタスな問題である。
カーネルの帯域幅問題について検討し,$tildemathcalO(sqrtGamma_k(T)T+mathbbE[tau]Gamma_k(T))$を用いたアルゴリズムを提案する。
これは、 $tildemathcalO(Gamma_k(T)sqrtT のアート・リトリート境界に対する顕著な改善を示している。
- 参考スコア（独自算出の注目度）: 16.11544965325835
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Black box optimisation of an unknown function from expensive and noisy
evaluations is a ubiquitous problem in machine learning, academic research and
industrial production. An abstraction of the problem can be formulated as a
kernel based bandit problem (also known as Bayesian optimisation), where a
learner aims at optimising a kernelized function through sequential noisy
observations. The existing work predominantly assumes feedback is immediately
available; an assumption which fails in many real world situations, including
recommendation systems, clinical trials and hyperparameter tuning. We consider
a kernel bandit problem under stochastically delayed feedback, and propose an
algorithm with $\tilde{\mathcal{O}}(\sqrt{\Gamma_k(T)T}+\mathbb{E}[\tau])$
regret, where $T$ is the number of time steps, $\Gamma_k(T)$ is the maximum
information gain of the kernel with $T$ observations, and $\tau$ is the delay
random variable. This represents a significant improvement over the state of
the art regret bound of
$\tilde{\mathcal{O}}(\Gamma_k(T)\sqrt{T}+\mathbb{E}[\tau]\Gamma_k(T))$ reported
in Verma et al. (2022). In particular, for very non-smooth kernels, the
information gain grows almost linearly in time, trivializing the existing
results. We also validate our theoretical results with simulations.
- Abstract（参考訳）: 高価でノイズの多い評価から未知の機能のブラックボックス最適化は、機械学習、学術研究、工業生産においてユビキタスな問題である。
問題の抽象化はカーネルベースの帯域幅問題(ベイズ最適化(Bayesian optimization)とも呼ばれる)として定式化することができる。
既存の研究は主にフィードバックがすぐに利用可能であると仮定しており、レコメンデーションシステム、臨床試験、ハイパーパラメータチューニングを含む多くの現実の状況で失敗する仮定である。
我々は、確率的に遅延したフィードバックの下でカーネルバンディットの問題を考え、$\tilde{\mathcal{O}}(\sqrt{\Gamma_k(T)T}+\mathbb{E}[\tau])$ regret, where $T$ is the number of time steps, $\Gamma_k(T)$ is the maximum information gain of the kernel with $T$ observed, $\tau$ is the delay random variable。
これは、Verma et al. (2022) で報告された $\tilde{\mathcal{O}}(\Gamma_k(T)\sqrt{T}+\mathbb{E}[\tau]\Gamma_k(T))$ のアート後悔の状態を著しく改善したことを意味する。
特に、非常に滑らかでないカーネルでは、情報ゲインはほぼ線形に成長し、既存の結果を自明にする。
また,シミュレーションにより理論結果を検証した。
関連論文リスト
- 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) - Procrastinated Tree Search: Black-box Optimization with Delayed, Noisy,
and Multi-fidelity Feedback [11.064341598231195]
ブラックボックス最適化問題では,評価やシミュレーションオラクルのフィードバックによってのみ機能にアクセス可能な未知の目的関数を最大化することを目的としている。
ProCrastinated Tree Search (PCTS) と呼ばれる階層的楽観木探索(HOO)の汎用的拡張を提案する。
我々は,PCTSの遅延,雑音,多面的フィードバックによる後悔を定量化する汎用的証明手法を提案する。
論文 参考訳（メタデータ） (2021-10-14T08:55:41Z) - Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。
本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
論文 参考訳（メタデータ） (2021-06-22T15:50:45Z) - Randomized Exploration for Reinforcement Learning with General Value
Function Approximation [122.70803181751135]
本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。
提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。
我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
論文 参考訳（メタデータ） (2021-06-15T02:23:07Z) - 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) - On Information Gain and Regret Bounds in Gaussian Process Bandits [8.499604625449907]
ノイズフィードバックの観測から、高い評価と、おそらくは非シーケンシャルな目的関数$f$の最適化を考える。
カーネルのMatern族では、$gamma_T$の低い境界と、頻繁な設定での後悔が知られている。
論文 参考訳（メタデータ） (2020-09-15T10:15:29Z) - Time-varying Gaussian Process Bandit Optimization with Non-constant
Evaluation Time [93.6788993843846]
非定常評価時間を効果的に処理できる新しい時間変化ベイズ最適化アルゴリズムを提案する。
我々の限界は、評価時間列のパターンが問題の難易度に大きな影響を与えることを決定づける。
論文 参考訳（メタデータ） (2020-03-10T13:28:33Z) - Naive Exploration is Optimal for Online LQR [49.681825576239355]
最適後悔尺度は$widetildeTheta(sqrtd_mathbfu2 d_mathbfx T)$で、$T$は時間ステップの数、$d_mathbfu$は入力空間の次元、$d_mathbfx$はシステム状態の次元である。
我々の下界は、かつての$mathrmpoly(logT)$-regretアルゴリズムの可能性を排除する。
論文 参考訳（メタデータ） (2020-01-27T03:44:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。