論文の概要: 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が最先端のブラックボックス最適化手法よりも優れる複数の合成関数とハイパーパラメータチューニング問題を実験的に検証した。
関連論文リスト
- Tree Search-Based Policy Optimization under Stochastic Execution Delay [46.849634120584646]
遅延実行 MDP は、状態拡張に頼ることなく、ランダムな遅延に対処する新しい形式である。
観測された遅延値から、マルコフポリシーのクラスでポリシー探索を行うのに十分であることを示す。
我々はマルコフポリシーのクラスを最適化するモデルベースのアルゴリズムであるDEZを考案した。
論文 参考訳（メタデータ） (2024-04-08T12:19:04Z) - Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。
我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
論文 参考訳（メタデータ） (2024-02-19T03:08:02Z) - Improved Regret for Bandit Convex Optimization with Delayed Feedback [50.46856739179311]
遅延フィードバックを伴うバンド凸最適化(BCO)。
我々は,新しいアルゴリズムを開発し,一般にO(sqrtnT3/4+sqrtdT)$の後悔境界を満足していることを証明する。
提案アルゴリズムは,強い凸関数に対して$O((nT)2/3log/3T+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 [50.46856739179311]
本稿では,非定常環境における遅延オンライン凸最適化(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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。