論文の概要: Fixed Budget is No Harder Than Fixed Confidence in Best-Arm Identification up to Logarithmic Factors

• arxiv url: http://arxiv.org/abs/2602.03972v1
• Date: Tue, 03 Feb 2026 19:49:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-05 19:45:11.252496
• Title: Fixed Budget is No Harder Than Fixed Confidence in Best-Arm Identification up to Logarithmic Factors
• Title（参考訳）: 対数因子によるベストアーム同定における固定予算は信頼の固定に勝るものではない
• Authors: Kapilan Balagopalan, Yinan Li, Yao Zhao, Tuan Nguyen, Anton Daitche, Houssam Nassif, Kwang-Sung Jun,
• Abstract要約: ベストアーム識別(BAI)問題は、インタラクティブ機械学習における最も基本的な問題の1つである。 ユニークなベストアームを備えた$Kの腕のバンディットでは、両方の設定に最適なサンプルの複雑さが解決されている。 FB は対数因子に比較して FC ほど難しくないことを示す。
• 参考スコア（独自算出の注目度）: 55.397453239422084
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The best-arm identification (BAI) problem is one of the most fundamental problems in interactive machine learning, which has two flavors: the fixed-budget setting (FB) and the fixed-confidence setting (FC). For $K$-armed bandits with the unique best arm, the optimal sample complexities for both settings have been settled down, and they match up to logarithmic factors. This prompts an interesting research question about the generic, potentially structured BAI problems: Is FB harder than FC or the other way around? In this paper, we show that FB is no harder than FC up to logarithmic factors. We do this constructively: we propose a novel algorithm called FC2FB (fixed confidence to fixed budget), which is a meta algorithm that takes in an FC algorithm $\mathcal{A}$ and turn it into an FB algorithm. We prove that this FC2FB enjoys a sample complexity that matches, up to logarithmic factors, that of the sample complexity of $\mathcal{A}$. This means that the optimal FC sample complexity is an upper bound of the optimal FB sample complexity up to logarithmic factors. Our result not only reveals a fundamental relationship between FB and FC, but also has a significant implication: FC2FB, combined with existing state-of-the-art FC algorithms, leads to improved sample complexity for a number of FB problems.
• Abstract（参考訳）: ベストアーム識別(BAI)問題は、対話型機械学習における最も基本的な問題の1つであり、固定予算設定(FB)と固定信頼設定(FC)の2つのフレーバーがある。 ユニークなベストアームを備えた$Kの腕のバンディットでは、両方の設定に最適なサンプルの複雑さが解決され、対数的要因にマッチする。 これにより、汎用的で潜在的に構造化されたBAI問題に関する興味深い研究の疑問が提起される。 本稿では, FB が対数因子に比較して FC ほど難しくないことを示す。 我々は、FCアルゴリズムを$\mathcal{A}$からFBアルゴリズムに変換するメタアルゴリズムであるFC2FB(固定予算に対する信頼度固定)という新しいアルゴリズムを提案する。 このFC2FBは、対数的因子まで、サンプルの複雑さが$\mathcal{A}$と一致するようなサンプル複雑性を享受していることを証明している。 これは、最適なFCサンプルの複雑さは、対数因子までの最適なFBサンプルの複雑さの上限であることを意味する。 FB と FC の基本的な関係を明らかにするだけでなく,FC2FB と既存の最先端の FC アルゴリズムを組み合わせることで,多くの FB 問題に対するサンプルの複雑さが向上する。

関連論文リスト

• Breaking the $\log(1/Δ_2)$ Barrier: Better Batched Best Arm Identification with Adaptive Grids [28.547030766096956]
  ほぼ最適なサンプル複雑性を実現するアルゴリズムを導入し、インスタンスに敏感なバッチ複雑性を特徴とする。 我々は、この枠組みを線形包帯におけるバッチ化されたベストアーム識別の問題に拡張し、同様の改善を実現する。
  論文  参考訳（メタデータ） (2025-01-29T01:40:36Z)
• Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations [92.1840862558718]
  実用的な分散システムでは、労働者は概して均質ではなく、非常に多様な処理時間を持つ。 本稿では、任意に遅い計算を扱うための新しい並列手法Freyaを提案する。 Freyaは従来の手法と比較して,複雑性の保証が大幅に向上していることを示す。
  論文  参考訳（メタデータ） (2024-05-24T13:33:30Z)
• Fixed Confidence Best Arm Identification in the Bayesian Setting [6.083234045523298]
  ベイズ設定における固定信頼度ベストアーム識別(FC-BAI)問題を考察する。 この問題は、既知の既知値からバンディットモデルがサンプリングされたときに、信頼度が固定された最大の平均のアームを見つけることを目的としている。
  論文  参考訳（メタデータ） (2024-02-16T03:36:03Z)
• Solving a Class of Non-Convex Minimax Optimization in Federated Learning [84.98927714326908]
  ミニマックス問題は、機械学習のトレーニングから大規模学習まで、機械学習アプリケーション全体にわたって発生する。 本稿では,非ミニマックス問題 (emphi) に対するアルゴリズムのクラスを提案し,複雑性を$varepsilon-6)$に減らした。 我々は、FedSGDA-Mが$O(kappa2-3)$と$O(kappa2-3)$の最もよく知られた通信量を持つことを示す。
  論文  参考訳（メタデータ） (2023-10-05T15:48:41Z)
• SPRT-based Efficient Best Arm Identification in Stochastic Bandits [31.359578768463752]
  本稿では,固定信頼度設定におけるマルチアームバンディットの腕識別問題について検討する。 バンドイットの指数族に対する既存のアルゴリズムは計算上の課題に直面している。 逐次テストに有効であることが知られている確率比ベースのテストを採用するフレームワークが提案されている。
  論文  参考訳（メタデータ） (2022-07-22T15:54:53Z)
• Problem Dependent View on Structured Thresholding Bandit Problems [73.70176003598449]
  我々は、Thresholding Bandit problem (TBP)における問題依存体制について検討する。 学習者の目的は、シーケンシャルゲームの終わりに、所定のしきい値を超える手段を持つアームセットを出力することである。 コンケーブ設定と単調設定の両方で誤差の確率を上下に設定する。
  論文  参考訳（メタデータ） (2021-06-18T15:01:01Z)
• FANOK: Knockoffs in Linear Time [73.5154025911318]
  本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。 当社のメソッドは、最大50,000ドルという問題でテストしています。
  論文  参考訳（メタデータ） (2020-06-15T21:55:34Z)

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

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