論文の概要: Federated Best Arm Identification with Heterogeneous Clients

• arxiv url: http://arxiv.org/abs/2210.07780v3
• Date: Tue, 19 Dec 2023 09:31:06 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-21 03:28:08.561428
• Title: Federated Best Arm Identification with Heterogeneous Clients
• Title（参考訳）: 不均一クライアントを用いたフェデレーションベストアーム識別
• Authors: Zhirui Chen, P. N. Karthik, Vincent Y. F. Tan, and Yeow Meng Chee
• Abstract要約: 中央サーバと複数のクライアントを備えた多腕バンディット・セッティングにおける腕の識別について検討した。 予測停止時間上の上限が乗算定数までの下限と一致するアルゴリズム(ほぼ最適アルゴリズムの場合)について示す。 本稿では,指数時間瞬間に通信する新しいアルゴリズムを提案し,ほぼ最適であることを実証する。
• 参考スコア（独自算出の注目度）: 62.36929749450298
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study best arm identification in a federated multi-armed bandit setting with a central server and multiple clients, when each client has access to a {\em subset} of arms and each arm yields independent Gaussian observations. The goal is to identify the best arm of each client subject to an upper bound on the error probability; here, the best arm is one that has the largest {\em average} value of the means averaged across all clients having access to the arm. Our interest is in the asymptotics as the error probability vanishes. We provide an asymptotic lower bound on the growth rate of the expected stopping time of any algorithm. Furthermore, we show that for any algorithm whose upper bound on the expected stopping time matches with the lower bound up to a multiplicative constant ({\em almost-optimal} algorithm), the ratio of any two consecutive communication time instants must be {\em bounded}, a result that is of independent interest. We thereby infer that an algorithm can communicate no more sparsely than at exponential time instants in order to be almost-optimal. For the class of almost-optimal algorithms, we present the first-of-its-kind asymptotic lower bound on the expected number of {\em communication rounds} until stoppage. We propose a novel algorithm that communicates at exponential time instants, and demonstrate that it is asymptotically almost-optimal.
• Abstract（参考訳）: 本研究は,各クライアントが腕の部分集合にアクセスでき,各アームが独立してガウス観測を行う場合に,中央サーバと複数のクライアントで連携した多腕バンディット設定における最適なアーム識別について検討する。 ここでは、最良のアームは、腕にアクセスしているすべてのクライアントで平均された平均値の最大値を持つものである。 我々の関心は、誤差確率が消えるにつれて漸近性にある。 任意のアルゴリズムの期待停止時間の成長速度に対する漸近的な下限を提供する。 さらに、期待停止時間上の上限が乗算定数まで下限と一致するようなアルゴリズム({\em almost-optimal} アルゴリズム)の場合、任意の2つの連続する通信時間の比率は、独立した関心を持つ結果である。 これにより,アルゴリズムがほぼ最適となるために,指数的なタイミングでしか通信できないことを推測する。 ほぼ最適なアルゴリズムのクラスでは、ストップページまで期待される「em通信ラウンド」の数の第一の漸近的下限を示す。 指数関数時間で通信する新しいアルゴリズムを提案し,漸近的にほぼ最適であることを示す。

関連論文リスト

• Best-Arm Identification in Unimodal Bandits [24.001611176749158]
  本研究では, 固定信頼度ベストアーム識別問題について検討する。 我々は任意の境界の停止時間で2つ下げる。 腕の数に対する線形依存は、信頼性に依存しないコストでは避けられないことを示す。
  論文  参考訳（メタデータ） (2024-11-04T09:05:11Z)
• Fixing the Loose Brake: Exponential-Tailed Stopping Time in Best Arm Identification [39.751528705097414]
  固定された信頼設定では、アルゴリズムはデータ依存的に停止し、推定されたベストアームを正当性保証で返さなければならない。 私たちは、この不可能なイベントが、いくつかの人気のあるアルゴリズムで実際に起こりうることを証明しています。 最初のアルゴリズムはSequential Halvingと呼ばれる固定予算アルゴリズムと2倍のトリックに基づいている。 第2のアルゴリズムは、確度の高い任意の信頼度アルゴリズムを高い確率で阻止し、指数関数的に制限された停止時間を楽しむアルゴリズムに変換するメタアルゴリズムである。
  論文  参考訳（メタデータ） (2024-11-04T05:26:05Z)
• A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
  我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。 誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
  論文  参考訳（メタデータ） (2024-09-08T12:19:12Z)
• Optimal Best Arm Identification with Fixed Confidence in Restless Bandits [66.700654953613]
  本研究は,有限個の腕を持つレスレス・マルチアーム・バンディット・セッティングにおけるベスト・アーム識別について検討する。 各アームによって生成された離散時間データは、共通の有限状態空間で値を取る同質マルコフ連鎖を形成する。 その結果,あるマルコフ決定過程の長期的挙動の追跡とその状態-行動的訪問比率が,逆および達成可能性境界を解析するための重要な要素であることが示唆された。
  論文  参考訳（メタデータ） (2023-10-20T10:04:05Z)
• Beyond the Best: Estimating Distribution Functionals in Infinite-Armed Bandits [40.71199236098642]
  無限武装バンディット問題では、各アームの平均報酬は未知の分布からサンプリングされる。 我々は、最大以上の分布関数の一般的なクラスを検討し、オフラインとオンラインの両方で統一されたメタアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-11-01T18:20:10Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
  サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。 既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
  論文  参考訳（メタデータ） (2020-06-29T14:25:51Z)

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

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