論文の概要: Almost Cost-Free Communication in Federated Best Arm Identification

• arxiv url: http://arxiv.org/abs/2208.09215v1
• Date: Fri, 19 Aug 2022 08:37:09 GMT
• ステータス: 処理完了
• システム内更新日: 2022-08-22 17:01:19.671866
• Title: Almost Cost-Free Communication in Federated Best Arm Identification
• Title（参考訳）: フェデレーションベストアーム識別におけるほぼ無償通信
• Authors: Kota Srinivas Reddy, P. N. Karthik, and Vincent Y. F. Tan
• Abstract要約: 中央サーバと複数のクライアントを備えた多腕バンディット構成の連合学習における最適なアーム識別の問題について検討する。 逐次除去に基づく指数時間ステップでのみ通信を行う新しいアルゴリズム sc FedElim を提案する。
• 参考スコア（独自算出の注目度）: 76.12303738941254
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of best arm identification in a federated learning multi-armed bandit setup with a central server and multiple clients. Each client is associated with a multi-armed bandit in which each arm yields {\em i.i.d.}\ rewards following a Gaussian distribution with an unknown mean and known variance. The set of arms is assumed to be the same at all the clients. We define two notions of best arm -- local and global. The local best arm at a client is the arm with the largest mean among the arms local to the client, whereas the global best arm is the arm with the largest average mean across all the clients. We assume that each client can only observe the rewards from its local arms and thereby estimate its local best arm. The clients communicate with a central server on uplinks that entail a cost of $C\ge0$ units per usage per uplink. The global best arm is estimated at the server. The goal is to identify the local best arms and the global best arm with minimal total cost, defined as the sum of the total number of arm selections at all the clients and the total communication cost, subject to an upper bound on the error probability. We propose a novel algorithm {\sc FedElim} that is based on successive elimination and communicates only in exponential time steps and obtain a high probability instance-dependent upper bound on its total cost. The key takeaway from our paper is that for any $C\geq 0$ and error probabilities sufficiently small, the total number of arm selections (resp.\ the total cost) under {\sc FedElim} is at most~$2$ (resp.~$3$) times the maximum total number of arm selections under its variant that communicates in every time step. Additionally, we show that the latter is optimal in expectation up to a constant factor, thereby demonstrating that communication is almost cost-free in {\sc FedElim}. We numerically validate the efficacy of {\sc FedElim}.
• Abstract（参考訳）: 中央サーバと複数のクライアントを備えた多腕バンディット構成の連合学習における最適なアーム識別の問題について検討する。 それぞれのクライアントは多腕のバンディットに関連付けられており、各アームはガウス分布に従えば、未知の平均と既知の分散を持つ。 腕のセットは、すべてのクライアントで同じであると仮定されます。 ベストアームの2つの概念 — ローカルとグローバル – を定義します。 クライアントのローカルな最高の腕は、クライアントのローカルな腕の中で最大の平均を持つ腕であり、グローバルな最高の腕は、すべてのクライアントに対して最も平均的な平均を持つ腕である。 各クライアントは、そのローカルアームからのみ報酬を観察でき、それによってローカルのベストアームを推定できると仮定する。 クライアントはアップリンク上の中央サーバと通信し、アップリンクあたりの使用量あたり$c\ge0$のコストがかかる。 グローバルなベストアームはサーバで推定されます。 目標は、すべてのクライアントにおけるアーム選択の総数と通信コストの総和として定義され、エラー確率の上限が上限となるような、最小限のコストで、ローカルなベストアームとグローバルベストアームを特定することである。 本研究では,逐次除去法に基づく新しいアルゴリズムであるscフェデリアムを提案し,指数時間ステップでのみ通信し,その総コストに対して高い確率インスタンス依存上限を求める。 我々の論文から得られる重要な点は、C\geq 0$とエラー確率が十分に小さい場合、腕の選択総数(resp)である。 総コスト ( \ the total cost) {\sc fedelim} は最大で 2$ (resp.~$3$) であり、全ての時間ステップで通信するその変種の下でのarm選択の最大数である。 さらに、後者は、一定要素まで期待する上で最適であることを示し、したがって、通信が {\sc FedElim} においてほとんど費用がかからないことを示す。 我々は, {\sc FedElim} の有効性を数値的に検証した。

関連論文リスト

• A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
  我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。 誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
  論文  参考訳（メタデータ） (2024-09-08T12:19:12Z)
• Representative Arm Identification: A fixed confidence approach to identify cluster representatives [7.459521930846415]
  マルチアームバンディット(MAB)フレームワークにおける代表腕識別問題について検討する。 RAI問題は、最高の腕や、上位の$K$から$M$を識別するなど、いくつかのよく研究されたMAB問題としてカバーされている。 本稿では,信頼区間の概念に基づく2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-08-26T11:47:52Z)
• Optimal Best Arm Identification with Fixed Confidence in Restless Bandits [66.700654953613]
  本研究は,有限個の腕を持つレスレス・マルチアーム・バンディット・セッティングにおけるベスト・アーム識別について検討する。 各アームによって生成された離散時間データは、共通の有限状態空間で値を取る同質マルコフ連鎖を形成する。 その結果,あるマルコフ決定過程の長期的挙動の追跡とその状態-行動的訪問比率が,逆および達成可能性境界を解析するための重要な要素であることが示唆された。
  論文  参考訳（メタデータ） (2023-10-20T10:04:05Z)
• Federated Best Arm Identification with Heterogeneous Clients [62.36929749450298]
  中央サーバと複数のクライアントを備えた多腕バンディット・セッティングにおける腕の識別について検討した。 予測停止時間上の上限が乗算定数までの下限と一致するアルゴリズム(ほぼ最適アルゴリズムの場合)について示す。 本稿では,指数時間瞬間に通信する新しいアルゴリズムを提案し,ほぼ最適であることを実証する。
  論文  参考訳（メタデータ） (2022-10-14T13:09:11Z)
• Max-Quantile Grouped Infinite-Arm Bandits [39.7239093424124]
  無限に多くの腕からなる群が多数存在するバンド問題。 本稿では,まず各グループから一定数のアームを要求し,次に有限腕グループ化された最大量子帯域幅アルゴリズムを実行する2段階アルゴリズムを提案する。 インスタンス依存と最悪のケースの後悔の両方を特徴付け、後者に一致する下位境界を提供します。
  論文  参考訳（メタデータ） (2022-10-04T00:46:49Z)
• Best Arm Identification in Restless Markov Multi-Armed Bandits [85.55466536537293]
  マルチアームバンディット環境における最適な腕を特定することの問題点について検討する。 決定エンティティは、上限誤差確率を条件として、ベストアームのインデックスをできるだけ早く見つけることを希望する。 このポリシーは、$R$に依存する上限を達成し、$Rtoinfty$として単調に増加しないことを示す。
  論文  参考訳（メタデータ） (2022-03-29T04:58:04Z)
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
  我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。 まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。 我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
  論文  参考訳（メタデータ） (2021-02-15T19:10:52Z)

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

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