論文の概要: On Elimination Strategies for Bandit Fixed-Confidence Identification

• arxiv url: http://arxiv.org/abs/2205.10936v1
• Date: Sun, 22 May 2022 21:41:57 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-24 16:02:16.119740
• Title: On Elimination Strategies for Bandit Fixed-Confidence Identification
• Title（参考訳）: バンディット固定信頼識別のための除去戦略について
• Authors: Andrea Tirinzoni, R\'emy Degenne
• Abstract要約: 提案手法は, 停止法とサンプリング法の両方において, 除去法を用いて修正可能であることを示す。 我々はこれらの利点を実験的に確認し、除去は適応的手法の計算複雑性を大幅に改善する。
• 参考スコア（独自算出の注目度）: 12.782423203398094
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Elimination algorithms for bandit identification, which prune the plausible correct answers sequentially until only one remains, are computationally convenient since they reduce the problem size over time. However, existing elimination strategies are often not fully adaptive (they update their sampling rule infrequently) and are not easy to extend to combinatorial settings, where the set of answers is exponentially large in the problem dimension. On the other hand, most existing fully-adaptive strategies to tackle general identification problems are computationally demanding since they repeatedly test the correctness of every answer, without ever reducing the problem size. We show that adaptive methods can be modified to use elimination in both their stopping and sampling rules, hence obtaining the best of these two worlds: the algorithms (1) remain fully adaptive, (2) suffer a sample complexity that is never worse of their non-elimination counterpart, and (3) provably eliminate certain wrong answers early. We confirm these benefits experimentally, where elimination improves significantly the computational complexity of adaptive methods on common tasks like best-arm identification in linear bandits.
• Abstract（参考訳）: 有効な正解を1つだけ残すまで順次引き起こす帯域識別の除去アルゴリズムは、時間とともに問題のサイズを減らすので、計算上便利である。 しかし、既存の除去戦略は完全適応的ではなく(サンプリング規則を頻繁に更新する)、問題次元において解の集合が指数関数的に大きい組合せ設定に拡張するのは容易ではない。 一方、一般的な識別問題に対処する既存の完全適応戦略は、問題のサイズを小さくすることなく、全ての回答の正しさを繰り返しテストするため、計算的に要求される。 その結果,(1) アルゴリズムは完全な適応性を維持し,(2) サンプルの複雑さに悩まされ,(3) 特定の誤った答えを早期に確実に排除する,という2つの世界の長所が得られた。 我々はこれらの利点を実験的に確認し、線形帯域における最良腕識別のような共通タスクにおける適応手法の計算複雑性を大幅に改善する。

関連論文リスト

• Truly No-Regret Learning in Constrained MDPs [61.78619476991494]
  未知のCMDPで学習するモデルベース原始双対アルゴリズムを提案する。 提案アルゴリズムは,誤差のキャンセルを伴わずにサブ線形後悔を実現する。
  論文  参考訳（メタデータ） (2024-02-24T09:47:46Z)
• An efficient, provably exact, practical algorithm for the 0-1 loss linear classification problem [4.418462313508022]
  インクリメンタルセル(ICE)は,0-1損失分類問題を正確に時間内に解くことができることを示す。 この長年の問題に対する、厳格に証明された実用的なアルゴリズムとしては、これが初めてだ。
  論文  参考訳（メタデータ） (2023-06-21T15:41:34Z)
• Infinite-Dimensional Sparse Learning in Linear System Identification [0.2867517731896504]
  本稿では,原子ノルム正規化に基づく無限次元スパース学習アルゴリズムを提案する。 この問題の解決の難しさは、無限の原子モデルが存在するという事実にある。
  論文  参考訳（メタデータ） (2022-03-28T13:18:48Z)
• Dealing With Misspecification In Fixed-Confidence Linear Top-m Identification [0.0]
  固定誤差率$delta$(固定信頼度Top-m識別)の下で最大の手段を持つmアームの識別問題について検討する。 この問題は、特に医療やレコメンデーションシステムにおける実践的な応用によって動機付けられている。
  論文  参考訳（メタデータ） (2021-11-02T10:27:17Z)
• A Mutual Information Maximization Approach for the Spurious Solution Problem in Weakly Supervised Question Answering [60.768146126094955]
  弱々しい教師付き質問応答は通常、最終的な答えのみを監督信号として持つ。 偶然に正解を導出する刺激的な解が多数存在するかもしれないが、そのような解の訓練はモデルの性能を損なう可能性がある。 本稿では,質問応答対と予測解間の相互情報の最大化により,このような意味的相関を明示的に活用することを提案する。
  論文  参考訳（メタデータ） (2021-06-14T05:47:41Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Fast OSCAR and OWL Regression via Safe Screening Rules [97.28167655721766]
  順序付き$L_1$ (OWL)正規化回帰は、高次元スパース学習のための新しい回帰分析である。 近勾配法はOWL回帰を解くための標準手法として用いられる。 未知の順序構造を持つ原始解の順序を探索することにより、OWL回帰の最初の安全なスクリーニングルールを提案する。
  論文  参考訳（メタデータ） (2020-06-29T23:35:53Z)
• Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
  サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。 既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
  論文  参考訳（メタデータ） (2020-06-29T14:25:51Z)
• Inexact Derivative-Free Optimization for Bilevel Learning [0.27074235008521236]
  変分正則化技術は数理イメージングの分野で支配的である。 この問題を解決するための一般的な戦略は、これらのパラメータをデータから学習することだ。 上層問題の解法では、下層問題の正確な解にアクセスできると仮定することが一般的であり、実際は不可能である。 本稿では, 厳密な低レベル問題解を必要としない不正確な微分自由最適化アルゴリズムを用いて, これらの問題を解くことを提案する。
  論文  参考訳（メタデータ） (2020-06-23T00:17:32Z)
• Quasi-Newton Solver for Robust Non-Rigid Registration [35.66014845211251]
  データフィッティングと正規化のための大域的スムーズなロバスト推定器に基づくロバストな非剛性登録のための定式化を提案する。 本稿では,L-BFGS を用いた最小二乗問題の解法に,各繰り返しを減らし,最大化最小化アルゴリズムを適用した。
  論文  参考訳（メタデータ） (2020-04-09T01:45:05Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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