論文の概要: Federated Best Arm Identification with Heterogeneous Clients
- arxiv url: http://arxiv.org/abs/2210.07780v2
- Date: Mon, 17 Oct 2022 06:36:45 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-18 13:32:16.555520
- Title: Federated Best Arm Identification with Heterogeneous Clients
- Title（参考訳）: 不均一クライアントを用いたフェデレーションベストアーム識別
- Authors: Zhirui Chen, P. N. Karthik, Vincent Y. F. Tan, and Yeow Meng Chee
- Abstract要約: 中央サーバと複数のクライアントを備えた多腕バンディット・セッティングにおける腕の識別について検討した。
本稿では,指数時間瞬間にのみ通信を行うエム・トラック・アンド・ストップ戦略に基づく新しいアルゴリズムを提案する。
最適なアームを見つけるための期待時間に上限があるアルゴリズムが乗算定数まで下限と一致する場合、任意の2つの連続する通信時間の比率は有界でなければならないことを示す。
- 参考スコア（独自算出の注目度）: 79.973538434633
- 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
{\em reward} from an arm at any given time is defined as the average of the
observations generated at this time across all the clients that have access to
the arm. The end goal is to identify the best arm (the arm with the largest
mean reward) of each client with the least expected stopping time, subject to
an upper bound on the error probability (i.e., the {\em fixed-confidence
regime}). We provide a lower bound on the growth rate of the expected time to
find the best arm of each client. Furthermore, we show that for any algorithm
whose upper bound on the expected time to find the best arms matches with the
lower bound up to a multiplicative constant, the ratio of any two consecutive
communication time instants must be bounded, a result that is of independent
interest. We then provide the first-known lower bound on the expected number of
{\em communication rounds} required to find the best arms. We propose a novel
algorithm based on the well-known {\em Track-and-Stop} strategy that
communicates only at exponential time instants, and derive asymptotic upper
bounds on its expected time to find the best arms and the expected number of
communication rounds, where the asymptotics is one of vanishing error
probabilities.
- Abstract（参考訳）: 本研究は,各クライアントが腕の部分集合にアクセスでき,各アームが独立してガウス観測を行う場合に,中央サーバと複数のクライアントで連携した多腕バンディット設定における最適なアーム識別について検討する。
任意のタイミングで腕から得られる報酬は、腕にアクセスする全てのクライアントに対して、この時点で発生した観測の平均として定義される。
最終目標は、各クライアントの最高のアーム(平均報酬が最も大きい腕)を最小の停止時間で識別することであり、エラー確率の上限(すなわち、"em fixed-confidence regime})である。
各クライアントの最適なアームを見つけるために、期待される時間の成長率に低いバウンダリを提供する。
さらに,最善のアームを求める推定時間上の上限が乗算定数まで下限と一致するアルゴリズムであれば,任意の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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。