論文の概要: Fixing the Loose Brake: Exponential-Tailed Stopping Time in Best Arm Identification
- arxiv url: http://arxiv.org/abs/2411.01808v1
- Date: Mon, 04 Nov 2024 05:26:05 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-05 14:44:00.829068
- Title: Fixing the Loose Brake: Exponential-Tailed Stopping Time in Best Arm Identification
- Title（参考訳）: ルースブレーキの固定:ベストアーム識別における指数シフト停止時間
- Authors: Kapilan Balagopalan, Tuan Ngo Nguyen, Yao Zhao, Kwang-Sung Jun,
- Abstract要約: 固定された信頼設定では、アルゴリズムはデータ依存的に停止し、推定されたベストアームを正当性保証で返さなければならない。
私たちは、この不可能なイベントが、いくつかの人気のあるアルゴリズムで実際に起こりうることを証明しています。
最初のアルゴリズムはSequential Halvingと呼ばれる固定予算アルゴリズムと2倍のトリックに基づいている。
第2のアルゴリズムは、確度の高い任意の信頼度アルゴリズムを高い確率で阻止し、指数関数的に制限された停止時間を楽しむアルゴリズムに変換するメタアルゴリズムである。
- 参考スコア（独自算出の注目度）: 39.751528705097414
- License:
- Abstract: The best arm identification problem requires identifying the best alternative (i.e., arm) in active experimentation using the smallest number of experiments (i.e., arm pulls), which is crucial for cost-efficient and timely decision-making processes. In the fixed confidence setting, an algorithm must stop data-dependently and return the estimated best arm with a correctness guarantee. Since this stopping time is random, we desire its distribution to have light tails. Unfortunately, many existing studies focus on high probability or in expectation bounds on the stopping time, which allow heavy tails and, for high probability bounds, even not stopping at all. We first prove that this never-stopping event can indeed happen for some popular algorithms. Motivated by this, we propose algorithms that provably enjoy an exponential-tailed stopping time, which improves upon the polynomial tail bound reported by Kalyanakrishnan et al. (2012). The first algorithm is based on a fixed budget algorithm called Sequential Halving along with a doubling trick. The second algorithm is a meta algorithm that takes in any fixed confidence algorithm with a high probability stopping guarantee and turns it into one that enjoys an exponential-tailed stopping time. Our results imply that there is much more to be desired for contemporary fixed confidence algorithms.
- Abstract（参考訳）: 最高の腕識別問題は、コスト効率とタイムリーな意思決定プロセスに不可欠である最小限の実験(アームプル)を用いて、アクティブな実験において最適な選択肢(腕)を特定することを必要とする。
固定された信頼設定では、アルゴリズムはデータ依存的に停止し、推定されたベストアームを正当性保証で返さなければならない。
この停止時間はランダムであるため、その分布は軽い尾を持つことを望んでいます。
残念なことに、多くの既存の研究は停止時間に高い確率や期待境界に焦点を合わせており、これは重い尾と高い確率境界を全く止まらなかったとしても許容できる。
私たちはまず、この絶え間ない出来事が、いくつかの人気のあるアルゴリズムで実際に起こりうることを証明した。
そこで我々は,Kalyanakrishnan et al (2012) によって報告された多項式の尾辺を改良し,指数的尾辺停止時間を確実に楽しむアルゴリズムを提案する。
最初のアルゴリズムはSequential Halvingと呼ばれる固定予算アルゴリズムと2倍のトリックに基づいている。
第2のアルゴリズムは、確度の高い任意の信頼度アルゴリズムを高い確率で阻止し、指数関数的に制限された停止時間を楽しむアルゴリズムに変換するメタアルゴリズムである。
以上の結果から,同時代の固定信頼アルゴリズムにはもっと多くのことが望まれていることが示唆された。
関連論文リスト
- Best-Arm Identification in Unimodal Bandits [24.001611176749158]
本研究では, 固定信頼度ベストアーム識別問題について検討する。
我々は任意の境界の停止時間で2つ下げる。
腕の数に対する線形依存は、信頼性に依存しないコストでは避けられないことを示す。
論文 参考訳（メタデータ） (2024-11-04T09:05:11Z) - Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust [5.037313459134419]
本稿では,ErdHos-R'enyiランダムグラフのエッジ密度を推定するアルゴリズムについて述べる。
我々は,アルゴリズムの誤り率を対数的因子まで最適とする情報理論的下界を証明した。
論文 参考訳（メタデータ） (2024-05-26T18:59:44Z) - Concentration Tail-Bound Analysis of Coevolutionary and Bandit Learning Algorithms [1.104960878651584]
本稿では,アルゴリズムの実行時/実行時/実行時における集中テールバウンドを導出する問題について考察する。
この定理は、正、弱、零、負のドリフトが与えられた正確な指数的なテールバウンドを与える新しいドリフト定理を提供する。
我々のドリフト定理は、AIにおけるアルゴリズムのランタイム/レグレットの強い集中力を証明するのに使うことができる。
論文 参考訳（メタデータ） (2024-05-07T16:45:15Z) - Replicability is Asymptotically Free in Multi-armed Bandits [45.729105054410745]
この仕事の動機は、再現可能な機械学習の需要の増加にある。
特に、高い確率で、アルゴリズムのアクション列がデータセットに固有のランダム性の影響を受けないように、複製可能なアルゴリズムを考える。
論文 参考訳（メタデータ） (2024-02-12T03:31:34Z) - Federated Best Arm Identification with Heterogeneous Clients [62.36929749450298]
中央サーバと複数のクライアントを備えた多腕バンディット・セッティングにおける腕の識別について検討した。
予測停止時間上の上限が乗算定数までの下限と一致するアルゴリズム(ほぼ最適アルゴリズムの場合)について示す。
本稿では,指数時間瞬間に通信する新しいアルゴリズムを提案し,ほぼ最適であることを実証する。
論文 参考訳（メタデータ） (2022-10-14T13:09:11Z) - Double Coverage with Machine-Learned Advice [100.23487145400833]
オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。
我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
論文 参考訳（メタデータ） (2021-03-02T11:04:33Z) - Resource Allocation in Multi-armed Bandit Exploration: Overcoming
Sublinear Scaling with Adaptive Parallelism [107.48538091418412]
腕の引っ張りに様々な量の資源を割り当てることができる分割可能な資源にアクセス可能な場合,マルチアームの帯状地における探索について検討する。
特に、分散コンピューティングリソースの割り当てに重点を置いており、プル毎により多くのリソースを割り当てることで、結果をより早く得ることができます。
論文 参考訳（メタデータ） (2020-10-31T18:19:29Z) - Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。
既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
論文 参考訳（メタデータ） (2020-06-29T14:25:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。