論文の概要: The Simulator: Understanding Adaptive Sampling in the
Moderate-Confidence Regime
- arxiv url: http://arxiv.org/abs/1702.05186v2
- Date: Sun, 23 Apr 2023 15:48:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-26 02:05:16.222176
- Title: The Simulator: Understanding Adaptive Sampling in the
Moderate-Confidence Regime
- Title（参考訳）: シミュレーター:適度信頼体制における適応的サンプリングの理解
- Authors: Max Simchowitz and Kevin Jamieson and Benjamin Recht
- Abstract要約: エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。
適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。
我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
- 参考スコア（独自算出の注目度）: 52.38455827779212
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a novel technique for analyzing adaptive sampling called the {\em
Simulator}. Our approach differs from the existing methods by considering not
how much information could be gathered by any fixed sampling strategy, but how
difficult it is to distinguish a good sampling strategy from a bad one given
the limited amount of data collected up to any given time. This change of
perspective allows us to match the strength of both Fano and change-of-measure
techniques, without succumbing to the limitations of either method. For
concreteness, we apply our techniques to a structured multi-arm bandit problem
in the fixed-confidence pure exploration setting, where we show that the
constraints on the means imply a substantial gap between the
moderate-confidence sample complexity, and the asymptotic sample complexity as
$\delta \to 0$ found in the literature. We also prove the first instance-based
lower bounds for the top-k problem which incorporate the appropriate
log-factors. Moreover, our lower bounds zero-in on the number of times each
\emph{individual} arm needs to be pulled, uncovering new phenomena which are
drowned out in the aggregate sample complexity. Our new analysis inspires a
simple and near-optimal algorithm for the best-arm and top-k identification,
the first {\em practical} algorithm of its kind for the latter problem which
removes extraneous log factors, and outperforms the state-of-the-art in
experiments.
- Abstract（参考訳）: 本稿では,適応サンプリングを解析する新しい手法である {\em Simulatorを提案する。
提案手法は, 一定のサンプリング戦略によってどれだけの情報を集めることができるかではなく, 適切なサンプリング戦略と, 与えられた時間に収集される限られたデータ量とを区別することがいかに難しいかを考えることで, 既存の手法と異なる。
この視点の変化により,両手法の限界を克服することなく,ファノ法と測定方法の双方の強度を一致させることができる。
具体的には,本手法を固定信頼純粋探索条件における構造的マルチアームバンディット問題に適用し,本手法の制約は,中程度信頼標本の複雑性と漸近サンプルの複雑性とを,文献で見られる$\delta \to 0$として有意なギャップを示唆することを示す。
また、適切なログファクタを組み込んだトップk問題に対する、最初のインスタンスベースの下限も証明する。
さらに、我々の下界は、それぞれの 'emph{individual} アームの回数でゼロインであり、集合的なサンプルの複雑さに埋もれてしまう新しい現象を明らかにする必要がある。
我々の新しい分析は、最良腕と最上位kの識別のための単純でほぼ最適のアルゴリズムを刺激し、後者の問題に対する最初の実用的アルゴリズムは、異常なログファクタを除去し、実験において最先端のアルゴリズムよりも優れている。
関連論文リスト
- Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-08T16:06:29Z) - Learning Rate Free Sampling in Constrained Domains [21.853333421463603]
我々は、完全に学習率の低い制約付き領域をサンプリングするための新しい粒子ベースのアルゴリズム一式を導入する。
我々は,本アルゴリズムの性能を,単純度に基づくターゲットからのサンプリングを含む,様々な数値的な例で示す。
論文 参考訳（メタデータ） (2023-05-24T09:31:18Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳（メタデータ） (2021-06-05T09:16:28Z) - A Non-asymptotic Approach to Best-Arm Identification for Gaussian
Bandits [0.0]
本稿では,ガウス変数の信頼度を一定に保ち,有界な手段と単位分散を持つベストアーム識別のための新しい戦略を提案する。
探索バイアスサンプリング(Exploration-Biased Sampling)と呼ばれるこの戦略は、必ずしも最適ではない。
論文 参考訳（メタデータ） (2021-05-27T07:42:49Z) - Improved Algorithms for Agnostic Pool-based Active Classification [20.12178157010804]
プールに依存しない環境でのバイナリ分類のためのアクティブラーニングを検討する。
我々のアルゴリズムは、画像分類データセットにおけるアートアクティブな学習アルゴリズムの状況よりも優れている。
論文 参考訳（メタデータ） (2021-05-13T18:24:30Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - An Empirical Process Approach to the Union Bound: Practical Algorithms
for Combinatorial and Linear Bandits [34.06611065493047]
本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。
サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。
また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-21T00:56:33Z) - Beyond Worst-Case Analysis in Stochastic Approximation: Moment
Estimation Improves Instance Complexity [58.70807593332932]
近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。
最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。
提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
論文 参考訳（メタデータ） (2020-06-08T09:25:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。