論文の概要: Impact of Redundancy on Resilience in Distributed Optimization and
Learning
- arxiv url: http://arxiv.org/abs/2211.08622v1
- Date: Wed, 16 Nov 2022 02:23:34 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-17 16:42:23.616730
- Title: Impact of Redundancy on Resilience in Distributed Optimization and
Learning
- Title(参考訳): 分散最適化と学習のレジリエンスに及ぼす冗長性の影響
- Authors: Shuo Liu, Nirupam Gupta, Nitin H. Vaidya
- Abstract要約: 本稿では,サーバアーキテクチャにおける分散最適化と学習のレジリエンスの問題について考察する。
システムはサーバと複数のエージェントから構成され、各エージェントは独自のローカルコスト関数を持つ。
局所コスト関数が十分冗長であることを考えると、実際に$(f, r; epsilon)$-レジリエンスが達成できることが示される。
- 参考スコア(独自算出の注目度): 2.582633087903328
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This report considers the problem of resilient distributed optimization and
stochastic learning in a server-based architecture. The system comprises a
server and multiple agents, where each agent has its own local cost function.
The agents collaborate with the server to find a minimum of the aggregate of
the local cost functions. In the context of stochastic learning, the local cost
of an agent is the loss function computed over the data at that agent. In this
report, we consider this problem in a system wherein some of the agents may be
Byzantine faulty and some of the agents may be slow (also called stragglers).
In this setting, we investigate the conditions under which it is possible to
obtain an "approximate" solution to the above problem. In particular, we
introduce the notion of $(f, r; \epsilon)$-resilience to characterize how well
the true solution is approximated in the presence of up to $f$ Byzantine faulty
agents, and up to $r$ slow agents (or stragglers) -- smaller $\epsilon$
represents a better approximation. We also introduce a measure named $(f, r;
\epsilon)$-redundancy to characterize the redundancy in the cost functions of
the agents. Greater redundancy allows for a better approximation when solving
the problem of aggregate cost minimization.
In this report, we constructively show (both theoretically and empirically)
that $(f, r; \mathcal{O}(\epsilon))$-resilience can indeed be achieved in
practice, given that the local cost functions are sufficiently redundant.
- Abstract(参考訳): 本稿では,サーバアーキテクチャにおけるレジリエントな分散最適化と確率学習の問題について考察する。
システムはサーバと複数のエージェントから構成され、各エージェントは独自のローカルコスト関数を持つ。
エージェントはサーバと連携して、ローカルコスト関数の集約の最小値を求める。
確率学習の文脈において、エージェントの局所的なコストは、エージェントのデータ上で計算された損失関数である。
本報告では, エージェントのいくつかがビザンチンの欠陥であり, エージェントのいくつかが遅い(ストラグラーとも呼ばれる)システムでこの問題を考察する。
本研究では,上記の問題に対する「近似」解を求めることができる条件について検討する。
特に、$(f, r; \epsilon)$-レジリエンスの概念を導入して、真の解が最大$f$ビザンチン欠陥エージェントの存在下でどのように近似しているかを特徴付け、最大$r$遅いエージェント(またはストラグラー) -- 小さな$\epsilon$はより良い近似を表す。
また、エージェントのコスト関数の冗長性を特徴付けるために、$(f, r; \epsilon)$-redundancyという尺度も導入する。
より大きな冗長性は、総コスト最小化の問題を解決する際により良い近似を可能にする。
本報告では、局所コスト関数が十分冗長であることを考えると、$(f, r; \mathcal{O}(\epsilon))$-レジリエンスが実際に達成可能であることを(理論的にも経験的にも)構築的に示す。
関連論文リスト
- Cooperative Multi-Agent Reinforcement Learning: Asynchronous
Communication and Linear Function Approximation [77.09836892653176]
マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。
本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。
我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
論文 参考訳(メタデータ) (2023-05-10T20:29:29Z) - Compressed Regression over Adaptive Networks [58.79251288443156]
分散エージェントのネットワークによって達成可能な性能を導出し,通信制約や回帰問題を解消し,適応的に解決する。
エージェントによって最適化に必要なパラメータをオンラインで学習できる最適化アロケーション戦略を考案する。
論文 参考訳(メタデータ) (2023-04-07T13:41:08Z) - PRECISION: Decentralized Constrained Min-Max Learning with Low
Communication and Sample Complexities [25.153506493249854]
min-max最適化問題に対する適応型マルチエージェント学習手法を提案する。
また,反復回数を削減できるPrecisionというアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-03-05T00:26:10Z) - 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) - 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) - Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。
$varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。
この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
論文 参考訳(メタデータ) (2021-10-24T04:03:00Z) - Utilizing Redundancy in Cost Functions for Resilience in Distributed
Optimization and Learning [1.8414221462731502]
本稿では,サーバアーキテクチャにおけるレジリエントな分散最適化と機械学習の問題について考察する。
システムはサーバと複数のエージェントから構成され、各エージェントはローカルなコスト関数を持つ。
エージェントのいくつかが非同期で、/またはビザンティンの欠陥がある場合を考えます。
論文 参考訳(メタデータ) (2021-10-21T02:41:19Z) - Byzantine Fault-Tolerance in Federated Local SGD under 2f-Redundancy [1.7188280334580197]
フェデレーション機械学習におけるビザンチンフォールトトレランスの問題点を考察する。
故障のない環境では、エージェントはコーディネータと協力し、局所的なコスト関数の集合の最小化を見つける。
我々は,2f$-redundancy以下では,CE を用いた局所アルゴリズムで正確なフォールトトレランスが得られることを示す。
論文 参考訳(メタデータ) (2021-08-26T13:04:28Z) - A Multi-Agent Primal-Dual Strategy for Composite Optimization over
Distributed Features [52.856801164425086]
目的関数を滑らかな局所関数と凸(おそらく非滑らか)結合関数の和とするマルチエージェント共有最適化問題について検討する。
論文 参考訳(メタデータ) (2020-06-15T19:40:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。