論文の概要: Distributed Online Learning for Joint Regret with Communication
Constraints
- arxiv url: http://arxiv.org/abs/2102.07521v1
- Date: Mon, 15 Feb 2021 12:48:33 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-17 12:10:09.858891
- Title: Distributed Online Learning for Joint Regret with Communication
Constraints
- Title(参考訳): コミュニケーション制約付き共同レジストの分散オンライン学習
- Authors: Dirk van der Hoeven, H\'edi Hadiji, Tim van Erven
- Abstract要約: コミュニケーションの制約との共同後悔のための分散オンライン学習環境を検討する。
すべてのエージェントのサブセットは、グラフ内の隣人に$b$-bitメッセージを送信することができる。
アルゴリズムのコンパレータ適応特性を利用して、最適なパーティションの集合から最適なパーティションを学習する。
- 参考スコア(独自算出の注目度): 17.080853582489073
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper we consider a distributed online learning
setting for joint regret with communication constraints. This is a
multi-agent setting in which in each round $t$ an adversary activates an agent,
which has to issue a prediction. A subset of all the agents may then
communicate a $b$-bit message to their neighbors in a graph. All agents
cooperate to control the joint regret, which is the sum of the losses of the
agents minus the losses evaluated at the best fixed common comparator
parameters $\pmb{u}$. We provide a comparator-adaptive algorithm for this
setting, which means that the joint regret scales with the norm of the
comparator $\|\pmb{u}\|$. To address communication constraints we provide
deterministic and stochastic gradient compression schemes and show that with
these compression schemes our algorithm has worst-case optimal regret for the
case that all agents communicate in every round. Additionally, we exploit the
comparator-adaptive property of our algorithm to learn the best partition from
a set of candidate partitions, which allows different subsets of agents to
learn a different comparator.
- Abstract(参考訳): 本論文では,コミュニケーション制約との共同後悔のための分散オンライン学習環境を検討する。
これは、各ラウンド$t$のマルチエージェント設定で、敵がエージェントを起動し、予測を発行しなければならない。
すべてのエージェントのサブセットは、グラフ内の隣人に$b$-bitメッセージを送信することができる。
すべてのエージェントは共同後悔を制御するために協力し、最良の固定された共通コンパレータパラメータである$\pmb{u}$で評価された損失を減らすエージェントの損失の合計である。
この設定に対するコンパレータ適応アルゴリズムは、共同後悔はコンパレータ $\|\pmb{u}\|$ のノルムと共にスケールすることを意味する。
コミュニケーションの制約に対処するため、我々は決定論的かつ確率的勾配圧縮スキームを提供し、これらの圧縮スキームにより、全てのエージェントがラウンドごとに通信する場合に、アルゴリズムが最悪の場合に最適に後悔することを示す。
さらに、アルゴリズムのコンパレータ適応性を利用して、候補パーティションの集合から最適なパーティションを学習し、エージェントの異なるサブセットが異なるコンパレータを学習できるようにする。
関連論文リスト
- Compressed Regression over Adaptive Networks [58.79251288443156]
分散エージェントのネットワークによって達成可能な性能を導出し,通信制約や回帰問題を解消し,適応的に解決する。
エージェントによって最適化に必要なパラメータをオンラインで学習できる最適化アロケーション戦略を考案する。
論文 参考訳(メタデータ) (2023-04-07T13:41:08Z) - On Regret-optimal Cooperative Nonstochastic Multi-armed Bandits [4.721069729610892]
我々は,FTRLアルゴリズムが,下界を一定要素に整合した個々の後悔の上界を有することを示す。
また、エッジ遅延パラメータによるスケーリングに関して、適切な正規化器を持つFTRLアルゴリズムが最適であることを示す。
論文 参考訳(メタデータ) (2022-11-30T16:46:41Z) - Regret Minimization and Convergence to Equilibria in General-sum Markov
Games [57.568118148036376]
汎用マルコフゲームにおいて,全てのエージェントが実行した場合のサブ線形後悔保証を提供する学習アルゴリズムを初めて提示する。
我々のアルゴリズムは分散化され、計算効率が良く、エージェント間の通信は不要である。
論文 参考訳(メタデータ) (2022-07-28T16:27:59Z) - Contextual Model Aggregation for Fast and Robust Federated Learning in
Edge Computing [88.76112371510999]
フェデレーション学習は、ネットワークエッジにおける分散機械学習の第一候補である。
既存のアルゴリズムは、性能の緩やかな収束や堅牢性の問題に直面している。
そこで本稿では,損失低減に対する最適コンテキスト依存境界を実現するためのコンテキストアグリゲーション手法を提案する。
論文 参考訳(メタデータ) (2022-03-23T21:42:31Z) - Optimal Clustering with Bandit Feedback [84.04424523097168]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳(メタデータ) (2022-02-09T06:05:05Z) - Distributed Bandits with Heterogeneous Agents [38.90376765616447]
本稿では、M$エージェントが協力して$K$武器の盗賊問題を解くマルチエージェントの盗賊設定に取り組む。
本稿では,ucbo と AAE の2つの学習アルゴリズムを提案する。
Oleft(sum_i:tildeDelta_i>0 log T/tildeDelta_iright)$, $tildeDelta_i$は報酬平均の最小部分最適差である。
論文 参考訳(メタデータ) (2022-01-23T20:04:15Z) - Distributed Adaptive Learning Under Communication Constraints [54.22472738551687]
本研究では,コミュニケーション制約下での運用を目的とした適応型分散学習戦略について検討する。
我々は,ストリーミングデータの連続的な観察から,オンライン最適化問題を解決しなければならないエージェントのネットワークを考える。
論文 参考訳(メタデータ) (2021-12-03T19:23:48Z) - An Efficient Algorithm for Cooperative Semi-Bandits [0.0]
本稿では,有名なFollow The Perturbed Leaderアルゴリズムの協調バージョンであるCoop-FTPLを紹介する。
T 時間ステップ後のアルゴリズムの期待された後悔は QT log(k)(k$alpha$ 1 /Q + m) であり、Q は総アクティベーション確率質量である。
論文 参考訳(メタデータ) (2020-10-05T07:08:26Z) - Comparator-adaptive Convex Bandits [77.43350984086119]
我々は,コンパレータのノルムが小さい場合,残差が小さい凸バンディットアルゴリズムを開発した。
アイデアを拡張して、リプシッツや滑らかな損失関数で包帯を凸する。
論文 参考訳(メタデータ) (2020-07-16T16:33:35Z) - The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits [19.457336747088593]
N$エージェントからなる分散マルチエージェントMulti Armed Bandit (MAB) のセットアップを検討する。
我々のモデルでは、エージェントは任意の連結グラフ上で、ペアワイズなゴシップスタイルの通信を通じてメッセージを交換することで協調する。
論文 参考訳(メタデータ) (2020-01-15T17:49:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。