論文の概要: 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通信ラウンド」の数の第一の漸近的下限を示す。 指数関数時間で通信する新しいアルゴリズムを提案し,漸近的にほぼ最適であることを示す。

関連論文リスト

• Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem [10.994427113326996]
  この問題の例としては、$k$のアームがあり、それぞれの報酬関数は凹凸であり、腕が引き抜かれた回数の関数が増加する。 任意のランダム化オンラインアルゴリズムに対して、最適報酬に対して少なくとも$Omega(sqrtk)$近似係数を負わなければならない事例が存在することを示す。 次に、この仮定を余分な$O(sqrtk log k)$近似係数のコストで除去する方法を示し、全体的な$O(sqrtk)を達成する。
  論文  参考訳（メタデータ） (2024-04-01T15:55:45Z)
• Optimal Best Arm Identification with Fixed Confidence in Restless Bandits [66.700654953613]
  本研究は,有限個の腕を持つレスレス・マルチアーム・バンディット・セッティングにおけるベスト・アーム識別について検討する。 各アームによって生成された離散時間データは、共通の有限状態空間で値を取る同質マルコフ連鎖を形成する。 その結果,あるマルコフ決定過程の長期的挙動の追跡とその状態-行動的訪問比率が,逆および達成可能性境界を解析するための重要な要素であることが示唆された。
  論文  参考訳（メタデータ） (2023-10-20T10:04:05Z)
• Best arm identification in rare events [0.43012765978447565]
  このフレームワークのキーとなる応用は、オンライン広告において、広告のクリックレートが1パーセントのごく一部であり、売上への最終的な転換率は高い利益であるが、再びクリックレートのごく一部になるかもしれない。 近年,BAI問題に対するアルゴリズムが開発され,正確なアーム選択に関する統計的保証を提供しながら,サンプルの複雑さを最小化している。 両腕の報酬過程は複合ポアソン法によりよく近似され、より高速なアルゴリズムに到達し、サンプルの複雑さはわずかに増大する。
  論文  参考訳（メタデータ） (2023-03-14T04:51:24Z)
• Beyond the Best: Estimating Distribution Functionals in Infinite-Armed Bandits [40.71199236098642]
  無限武装バンディット問題では、各アームの平均報酬は未知の分布からサンプリングされる。 我々は、最大以上の分布関数の一般的なクラスを検討し、オフラインとオンラインの両方で統一されたメタアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-11-01T18:20:10Z)
• Almost Cost-Free Communication in Federated Best Arm Identification [76.12303738941254]
  中央サーバと複数のクライアントを備えた多腕バンディット構成の連合学習における最適なアーム識別の問題について検討する。 逐次除去に基づく指数時間ステップでのみ通信を行う新しいアルゴリズム sc FedElim を提案する。
  論文  参考訳（メタデータ） (2022-08-19T08:37:09Z)
• Globally Optimal Algorithms for Fixed-Budget Best Arm Identification [16.500749121196986]
  すべての可能なパラメータに対する大域的最適化の結果,最適速度を特徴付ける。 遅延最適追跡(DOT)と呼ばれる概念的アルゴリズムを導入することで、この速度が実際に達成可能であることを示す。
  論文  参考訳（メタデータ） (2022-06-09T17:42:19Z)
• 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)

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

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