論文の概要: Procrastinated Tree Search: Black-box Optimization with Delayed, Noisy,
and Multi-fidelity Feedback
- arxiv url: http://arxiv.org/abs/2110.07232v1
- Date: Thu, 14 Oct 2021 08:55:41 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-15 14:03:58.753052
- Title: Procrastinated Tree Search: Black-box Optimization with Delayed, Noisy,
and Multi-fidelity Feedback
- Title(参考訳): Procrastinated Tree Search: 遅延、ノイズ、多要素フィードバックによるブラックボックス最適化
- Authors: Junxiong Wang, Debabrota Basu, Immanuel Trummer
- Abstract要約: ブラックボックス最適化問題では,評価やシミュレーションオラクルのフィードバックによってのみ機能にアクセス可能な未知の目的関数を最大化することを目的としている。
ProCrastinated Tree Search (PCTS) と呼ばれる階層的楽観木探索(HOO)の汎用的拡張を提案する。
我々は,PCTSの遅延,雑音,多面的フィードバックによる後悔を定量化する汎用的証明手法を提案する。
- 参考スコア(独自算出の注目度): 11.064341598231195
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: In black-box optimization problems, we aim to maximize an unknown objective
function, where the function is only accessible through feedbacks of an
evaluation or simulation oracle. In real-life, the feedbacks of such oracles
are often noisy and available after some unknown delay that may depend on the
computation time of the oracle. Additionally, if the exact evaluations are
expensive but coarse approximations are available at a lower cost, the
feedbacks can have multi-fidelity. In order to address this problem, we propose
a generic extension of hierarchical optimistic tree search (HOO), called
ProCrastinated Tree Search (PCTS), that flexibly accommodates a delay and
noise-tolerant bandit algorithm. We provide a generic proof technique to
quantify regret of PCTS under delayed, noisy, and multi-fidelity feedbacks.
Specifically, we derive regret bounds of PCTS enabled with delayed-UCB1 (DUCB1)
and delayed-UCB-V (DUCBV) algorithms. Given a horizon $T$, PCTS retains the
regret bound of non-delayed HOO for expected delay of $O(\log T)$ and worsens
by $O(T^{\frac{1-\alpha}{d+2}})$ for expected delays of $O(T^{1-\alpha})$ for
$\alpha \in (0,1]$. We experimentally validate on multiple synthetic functions
and hyperparameter tuning problems that PCTS outperforms the state-of-the-art
black-box optimization methods for feedbacks with different noise levels,
delays, and fidelity.
- Abstract(参考訳): ブラックボックス最適化問題では,評価やシミュレーションオラクルのフィードバックによってのみ機能にアクセス可能な未知の目的関数を最大化する。
実生活では、そのようなオラクルのフィードバックはしばしばノイズがあり、オラクルの計算時間に依存する可能性のある未知の遅延の後、利用できる。
さらに、正確な評価が高価であるが、粗い近似が低コストで利用可能であれば、フィードバックは多元性を持つことができる。
この問題に対処するため,階層型楽観木探索(HOO)の汎用拡張であるProCrastinated Tree Search(PCTS)を提案する。
我々は,PCTSの遅延,雑音,多面的フィードバックによる後悔を定量化する汎用的証明手法を提案する。
具体的には,遅延UCB1 (DUCBV) と遅延UCB-V (DUCBV) アルゴリズムで実現されたPCTSの残差を導出する。
ホライズン$t$ が与えられると、pcts は期待遅延が $o(\log t)$ で非遅延hoo の後悔の束縛を保持し、さらに$o(t^{\frac{1-\alpha}{d+2}})$ で遅延が$o(t^{1-\alpha})$ で$\alpha \in (0,1]$ となる。
ノイズレベル,遅延,忠実度が異なるフィードバックに対して,PCTSが最先端のブラックボックス最適化手法よりも優れる複数の合成関数とハイパーパラメータチューニング問題を実験的に検証した。
関連論文リスト
- Stochastic Approximation with Delayed Updates: Finite-Time Rates under
Markovian Sampling [76.72850243028888]
マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。
我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
論文 参考訳(メタデータ) (2024-02-19T03:08:02Z) - Improved Regret for Bandit Convex Optimization with Delayed Feedback [55.13328423837296]
本稿では,遅延した帯域幅のフィードバックをブロッキング更新機構によって注意深く活用する,新たなアルゴリズムを開発した。
制約のない作用集合を持つ特別な場合、それは強凸かつ滑らかな函数に対して$O(sqrtTlog T+dlog T)$の後悔境界を達成するために単純に拡張することができる。
論文 参考訳(メタデータ) (2024-02-14T13:08:26Z) - Posterior Sampling with Delayed Feedback for Reinforcement Learning with
Linear Function Approximation [62.969796245827006]
Delayed-PSVI は楽観的な値に基づくアルゴリズムであり、後続サンプリングによる雑音摂動により値関数空間を探索する。
我々のアルゴリズムは、未知の遅延が存在する場合に、$widetildeO(sqrtd3H3 T + d2H2 E[tau]$最悪の後悔を実現する。
遅延LPSVIのための勾配に基づく近似サンプリングスキームをLangevin動的に組み込んだ。
論文 参考訳(メタデータ) (2023-10-29T06:12:43Z) - Min-Max Optimization under Delays [26.830212508878162]
大規模な機械学習問題では遅延と非同期は避けられない。
min-max最適化に類似した理論は存在しない。
たとえ小さな遅延であっても、エクストラグラディエントのような顕著なアルゴリズムが分岐する可能性があることを示す。
論文 参考訳(メタデータ) (2023-07-13T16:39:01Z) - Non-stationary Online Convex Optimization with Arbitrary Delays [55.13328423837296]
本稿では,非定常環境における遅延オンライン凸最適化(OCO)について検討する。
まず, 遅延勾配の勾配降下ステップを, 到着順に応じて行う単純なアルゴリズム, DOGDを提案する。
DOGDが達成した動的後悔境界を$O(sqrtbardT(P_T+1))$に削減する改良アルゴリズムを開発した。
論文 参考訳(メタデータ) (2023-05-20T07:54:07Z) - Bayesian Optimization under Stochastic Delayed Feedback [36.16843889404038]
既存のBOメソッドは、関数評価(フィードバック)が学習者の即時または固定遅延後に利用可能であると仮定する。
本稿では,遅延フィードバックを待ちながら新しい関数クエリを選択するジレンマに効率よく対処する,線形後悔保証付きアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-06-19T07:34:08Z) - Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。
本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
論文 参考訳(メタデータ) (2021-06-22T15:50:45Z) - Online Strongly Convex Optimization with Unknown Delays [30.931538196386672]
オンライン凸最適化の問題点を未知の遅延で検討する。
まず、OGDの遅延変形を強凸関数に拡張する。
我々は、$d$が最大遅延である$O(dlog T)$のより良い後悔の境界を確立します。
論文 参考訳(メタデータ) (2021-03-21T10:16:15Z) - Adapting to Delays and Data in Adversarial Multi-Armed Bandits [7.310043452300736]
決定時に利用可能な情報のみを用いてステップサイズを調整するExp3アルゴリズムの変種を分析する。
我々は、観測された(最悪の場合ではなく)遅延や損失のシーケンスに適応する後悔の保証を得る。
論文 参考訳(メタデータ) (2020-10-12T20:53:52Z) - Time-varying Gaussian Process Bandit Optimization with Non-constant
Evaluation Time [93.6788993843846]
非定常評価時間を効果的に処理できる新しい時間変化ベイズ最適化アルゴリズムを提案する。
我々の限界は、評価時間列のパターンが問題の難易度に大きな影響を与えることを決定づける。
論文 参考訳(メタデータ) (2020-03-10T13:28:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。