論文の概要: Dual-Directed Algorithm Design for Efficient Pure Exploration

• arxiv url: http://arxiv.org/abs/2310.19319v2
• Date: Wed, 11 Dec 2024 14:10:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-12 14:00:02.644143
• Title: Dual-Directed Algorithm Design for Efficient Pure Exploration
• Title（参考訳）: 効率的純探索のためのデュアル指向アルゴリズムの設計
• Authors: Chao Qin, Wei You,
• Abstract要約: 有限組の代替品を用いた逐次適応実験の文脈における純粋探索問題を考える。 固定予算, 固定信頼度, 後収束率設定に対する最大最適化問題として問題複雑性尺度を定式化する。 我々のアルゴリズムは、$varepsilon$-best-armの識別(または、良好な選択保証の確率でランク付けと選択)としきい値の帯域幅で最適性を得る。
• 参考スコア（独自算出の注目度）: 9.728332815218181
• License:
• Abstract: We consider pure-exploration problems in the context of stochastic sequential adaptive experiments with a finite set of alternatives. The central objective is to answer a query regarding the alternatives with high confidence while minimizing measurement efforts. One canonical example is identifying the best-performing alternative, a problem known as ranking and selection in simulation or best-arm identification in machine learning. We formulate the problem complexity measure as a maximin optimization problem for the static fixed-budget, fixed-confidence, and posterior convergence rate settings. By incorporating dual variables directly into the analysis, we derive necessary and sufficient conditions for an allocation's optimality. The introduction of dual variables allows us to sidestep the combinatorial complexity that arises when considering only primal variables. These optimality conditions enable the extension of the top-two algorithm design principle to more general pure-exploration problems. Moreover, our analysis yields a straightforward and effective information-directed selection rule that adaptively chooses from a candidate set based on the informational value of the candidates. We demonstrate the broad range of contexts in which our design principle can be implemented. In particular, when combined with information-directed selection, top-two Thompson sampling achieves asymptotic optimality in Gaussian best-arm identification, resolving a notable open question in the pure-exploration literature. Our algorithm attains optimality in $\varepsilon$-best-arm identification (or ranking and selection with a probability of good selection guarantee) and thresholding bandits. Our results provide a general principle for adapting Thompson sampling to general pure-exploration problems. Numerical experiments highlight the efficiency of our proposed algorithms compared to existing methods.
• Abstract（参考訳）: 確率的逐次適応実験の文脈における純粋探索問題を考える。 中心的な目的は、測定作業を最小化しつつ、高い信頼性で代替案に関する質問に答えることである。 模範的な例の1つは、最高のパフォーマンスの代替品、シミュレーションにおけるランキングと選択、機械学習におけるベストアーム識別と呼ばれる問題を特定することである。 固定予算, 固定信頼度, 後収束率設定に対する最大最適化問題として問題複雑性尺度を定式化する。 解析に双対変数を直接組み込むことで、割り当ての最適性に必要かつ十分な条件を導出する。 双対変数の導入により、原始変数のみを考える際に生じる組合せの複雑さを回避できる。 これらの最適条件により、トップ2のアルゴリズム設計原則をより一般的な純粋探索問題に拡張することができる。 さらに,本分析では,候補者の情報量に基づいて候補集合から適応的に選択する,単純かつ効果的な情報指向選択規則を導出する。 設計原則を実装可能な範囲のコンテキストを実証する。 特に、情報指向選択と組み合わせると、トップ2のトンプソンサンプリングはガウスのベストアーム識別において漸近的最適性を達成する。 我々のアルゴリズムは、$\varepsilon$-best-armの識別(または、良好な選択保証の確率でランク付けと選択)としきい値の帯域幅で最適性を得る。 この結果は、トンプソンサンプリングを一般純粋探索問題に適用するための一般的な原理を提供する。 従来の手法と比較して,提案アルゴリズムの効率性を示す数値実験を行った。

関連論文リスト

• An incremental preference elicitation-based approach to learning potentially non-monotonic preferences in multi-criteria sorting [53.36437745983783]
  まず最適化モデルを構築し,非単調な選好をモデル化する。 本稿では,情報量測定手法と質問選択戦略を考案し,各イテレーションにおいて最も情報に富む選択肢を特定する。 2つのインクリメンタルな選好に基づくアルゴリズムは、潜在的に単調な選好を学習するために開発された。
  論文  参考訳（メタデータ） (2024-09-04T14:36:20Z)
• Dynamic Incremental Optimization for Best Subset Selection [15.8362578568708]
  最良のサブセット選択は、多くの学習問題に対する金の標準と見なされている。 主問題構造と双対問題構造に基づいて,効率的な部分集合双対アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-02-04T02:26:40Z)
• Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
  確率に基づく推論の原理を再検討し、確率比を用いて妥当な信頼シーケンスを構築することを提案する。 本手法は, 精度の高い問題に特に適している。 提案手法は,オンライン凸最適化への接続に光を当てることにより,推定器の最適シーケンスを確実に選択する方法を示す。
  論文  参考訳（メタデータ） (2023-11-08T00:10:21Z)
• Generalizing Bayesian Optimization with Decision-theoretic Entropies [102.82152945324381]
  統計的決定論の研究からシャノンエントロピーの一般化を考える。 まず,このエントロピーの特殊なケースがBO手順でよく用いられる獲得関数に繋がることを示す。 次に、損失に対する選択肢の選択が、どのようにして柔軟な獲得関数の族をもたらすかを示す。
  論文  参考訳（メタデータ） (2022-10-04T04:43:58Z)
• Best Subset Selection with Efficient Primal-Dual Algorithm [24.568094642425837]
  多くの学習問題に対するベストサブセット選択は「ゴールドスタンダード」と見なされている。 本稿では,$ell$-regularized問題系の二重形式について検討する。 主問題構造と双対問題構造に基づく効率的な主対法が開発されている。
  論文  参考訳（メタデータ） (2022-07-05T14:07:52Z)
• Information-Directed Selection for Top-Two Algorithms [13.339829037245963]
  マルチアームバンディットにおける最良のk腕識別問題について考察する。 目的は、測定努力を逐次割当てることにより、最高の平均報酬でk腕の正確なセットを選択することである。 情報ゲインの尺度に基づいて上位2候補の1つを選択する情報指向選択(IDS)を提案する。
  論文  参考訳（メタデータ） (2022-05-24T14:07:13Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Gamification of Pure Exploration for Linear Bandits [34.16123941778227]
  線形バンディットの文脈において、ベストアーム識別を含む活発な純粋探索環境について検討する。 標準的なマルチアームバンディットには最適アルゴリズムが存在するが、リニアバンディットにおけるベストアーム識別のためのアルゴリズムの存在は明白である。 線形帯域における固定信頼純粋探索のための第一の洞察的最適アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-07-02T08:20:35Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。