論文の概要: 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トラックアンドストップ」戦略に基づく新しいアルゴリズムを提案する。
関連論文リスト
- Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
我々は、各アームが選択時にM$Dのベクトル報酬を得られる多腕バンディット設定を考える。
最終的なゴールは、最も短い(予想される)時間において、エラーの確率の上限に従属する全ての目的の最良のアームを特定することである。
本稿では,各ステップでアームをサンプリングするために,エミュロゲート比例という新しいアイデアを用いたアルゴリズムを提案し,各ステップにおける最大最小最適化問題を解く必要をなくした。
論文 参考訳（メタデータ） (2025-01-23T12:28:09Z) - Best-Arm Identification in Unimodal Bandits [24.001611176749158]
本研究では, 固定信頼度ベストアーム識別問題について検討する。
我々は任意の境界の停止時間で2つ下げる。
腕の数に対する線形依存は、信頼性に依存しないコストでは避けられないことを示す。
論文 参考訳（メタデータ） (2024-11-04T09:05:11Z) - A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。
誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
我々の洗練された分析により、アルゴリズムの平均的なアームプル数が、$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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。