論文の概要: Federated Bandit: A Gossiping Approach

• arxiv url: http://arxiv.org/abs/2010.12763v2
• Date: Wed, 7 Apr 2021 04:59:14 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-03 13:38:33.646367
• Title: Federated Bandit: A Gossiping Approach
• Title（参考訳）: Federated Bandit: ゴシップアプローチ
• Authors: Zhaowei Zhu, Jingxuan Zhu, Ji Liu, Yang Liu
• Abstract要約: 我々は、分散化されたマルチアーマッド・バンドイット問題であるemphFederated Banditを、$N$エージェントのセットで研究し、接続グラフ$G$で記述された隣人とのみローカルデータを通信できる。 Gossip_UCBは、ローカルな帯域学習をグローバルなゴシッププロセスに適応させ、接続されたエージェント間で情報を共有し、$O(max textttpoly(N,M) log T, textttpoly(N,M) log_lambda-1の順序で後悔を保証できることを示す。
• 参考スコア（独自算出の注目度）: 22.595542913855624
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study \emph{Federated Bandit}, a decentralized Multi-Armed Bandit problem with a set of $N$ agents, who can only communicate their local data with neighbors described by a connected graph $G$. Each agent makes a sequence of decisions on selecting an arm from $M$ candidates, yet they only have access to local and potentially biased feedback/evaluation of the true reward for each action taken. Learning only locally will lead agents to sub-optimal actions while converging to a no-regret strategy requires a collection of distributed data. Motivated by the proposal of federated learning, we aim for a solution with which agents will never share their local observations with a central entity, and will be allowed to only share a private copy of his/her own information with their neighbors. We first propose a decentralized bandit algorithm Gossip_UCB, which is a coupling of variants of both the classical gossiping algorithm and the celebrated Upper Confidence Bound (UCB) bandit algorithm. We show that Gossip_UCB successfully adapts local bandit learning into a global gossiping process for sharing information among connected agents, and achieves guaranteed regret at the order of $O(\max\{ \texttt{poly}(N,M) \log T, \texttt{poly}(N,M)\log_{\lambda_2^{-1}} N\})$ for all $N$ agents, where $\lambda_2\in(0,1)$ is the second largest eigenvalue of the expected gossip matrix, which is a function of $G$. We then propose Fed_UCB, a differentially private version of Gossip_UCB, in which the agents preserve $\epsilon$-differential privacy of their local data while achieving $O(\max \{\frac{\texttt{poly}(N,M)}{\epsilon}\log^{2.5} T, \texttt{poly}(N,M) (\log_{\lambda_2^{-1}} N + \log T) \})$ regret.
• Abstract（参考訳）: 本稿では,N$エージェントの集合を用いて分散化されたマルチアーマッド・バンドイット問題である \emph{Federated Bandit} について検討する。 各エージェントは、$m$の候補からarmを選択するという一連の決定を下しますが、各アクションに対する本当の報酬の、ローカルでバイアスのあるフィードバック/評価のみにアクセスできます。 ローカルでのみ学習することはエージェントを最適なサブアクションに導くと同時に、非リリース戦略に収束するためには、分散データの収集が必要である。 フェデレーション学習の提案に動機づけられ、エージェントがローカルな観察を中央のエンティティと決して共有せず、自分の情報のプライベートコピーを隣人とのみ共有できるようなソリューションを目指しています。 本稿ではまず,従来のゴシップアルゴリズムと有望なアッパー信頼境界(UCB)バンディットアルゴリズムの両変種を結合した分散バンドイットアルゴリズムGossip_UCBを提案する。 Gossip_UCBは、接続されたエージェント間で情報を共有するためのグローバルなゴシッププロセスにローカルバンディット学習を適用することに成功し、$O(\max\{ \textt{poly}(N,M) \log T, \texttt{poly}(N,M)\log_{\lambda_2^{-1}} N\})$ for all $N$エージェントに対して、$\lambda_2\in(0,1)$は期待されるゴシップ行列の2番目に大きな固有値であり、$G$の関数である。 次に、Fed_UCBを提案する。これはGossip_UCBの微分プライベートバージョンで、エージェントはローカルデータに対して$\epsilon$-differential privacy を保持し、$O(\max \{\frac{\texttt{poly}(N,M)}{\epsilon}\log^{2.5} T, \texttt{poly}(N,M) (\log_{\lambda_2^{-1}} N + \log T) \} を達成する。

関連論文リスト

• Cooperative Multi-Agent Constrained Stochastic Linear Bandits [2.099922236065961]
  N$エージェントのネットワークがローカルに通信し、期待されるコストを所定の閾値$tau$で保持しながら、全体的な後悔を最小限に抑える。 我々は、textitMA-OPLBと呼ばれる安全な分散上信頼度有界アルゴリズムを提案し、そのT$ラウンドの後悔に基づく高い確率を確立する。 我々の後悔の限界は次数$ MathcalOleft(fracdtau-c_0fraclog(NT)2sqrtNsqrtTlog (1/|lambda|)であることを示す。
  論文  参考訳（メタデータ） (2024-10-22T19:34:53Z)
• Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
  本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。 この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
  論文  参考訳（メタデータ） (2024-05-09T17:40:09Z)
• Federated Linear Bandits with Finite Adversarial Actions [20.1041278044797]
  我々は、M$のクライアントが中央サーバと通信し、線形文脈の帯域幅問題を解決するための連合線形帯域幅モデルについて検討する。 逆有限作用集合のユニークな問題に対処するため、FedSupLinUCBアルゴリズムを提案する。 我々は、FedSupLinUCBが$tildeO(sqrtd T)$の完全後悔を達成したことを証明している。
  論文  参考訳（メタデータ） (2023-11-02T03:41:58Z)
• Optimal Algorithms for Latent Bandits with Cluster Structure [50.44722775727619]
  本稿では,複数のユーザが存在するクラスタ構造を持つ潜伏包帯問題と関連するマルチアーム包帯問題とを考察する。 本稿では,潜伏クラスタ構造を利用して$widetildeO(sqrt(mathsfM+mathsfN)mathsfTの最小限の後悔を提供するLATTICEを提案する。
  論文  参考訳（メタデータ） (2023-01-17T17:49:04Z)
• A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Bandits [77.09836892653176]
  我々は,M$エージェントが相互に協力して,中央サーバの助けを借りて,グローバルなコンテキスト線形バンドイット問題を解決するためのフェデレーション付きコンテキスト線形バンドイットについて検討した。 すべてのエージェントが独立して動作し、ひとつのエージェントとサーバ間の通信が他のエージェントの通信をトリガーしない非同期設定を考える。 texttFedLinUCBの後悔は$tildeO(dsqrtsum_m=1M T_m)$で、通信の複雑さは$tildeO(dM)であることを示す。
  論文  参考訳（メタデータ） (2022-07-07T06:16:19Z)
• Distributed Contextual Linear Bandits with Minimax Optimal Communication Cost [48.288452411283444]
  そこでは,$N$エージェントが協調して,$d$次元の特徴を持つ線形帯域最適化問題を解く。 本稿では,LinUCBアルゴリズムの分散バッチ除去版であるDisBE-LUCBを提案する。 我々は、DisBE-LUCBの通信コストがわずか$tildemathcalO(dN)$であり、その後悔は少なくとも$tildemathcalO(dN)$であることを示す。
  論文  参考訳（メタデータ） (2022-05-26T05:56:23Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。 Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。 この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
  論文  参考訳（メタデータ） (2022-02-12T21:55:44Z)
• Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
  与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。 次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。 頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
  論文  参考訳（メタデータ） (2021-07-22T14:25:16Z)
• Multi-Agent Multi-Armed Bandits with Limited Communication [41.63062883750805]
  我々は、$N$エージェントが$K gg N$の$K$アームバンドイット問題のインスタンスと相互作用する問題を検討する。 エージェントは、合計でT$のタイムステップ、通信ラウンドの数、各通信ラウンドにおけるビット数について、すべてのエージェントに対する累積的後悔を同時に最小化することを目指している。 我々は、各エージェントがエポックの終わり後にのみ通信し、知っている最高の腕のインデックスを共有する2倍のエポックベースのアルゴリズムであるLimited Communication Collaboration - Upper Bound(LCC-UCB)を紹介します。
  論文  参考訳（メタデータ） (2021-02-10T06:28:37Z)

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

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