論文の概要: Impact of Redundancy on Resilience in Distributed Optimization and
Learning
- arxiv url: http://arxiv.org/abs/2211.08622v2
- Date: Thu, 14 Dec 2023 08:06:53 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-16 05:30:35.149505
- Title: Impact of Redundancy on Resilience in Distributed Optimization and
Learning
- Title（参考訳）: 分散最適化と学習のレジリエンスに及ぼす冗長性の影響
- Authors: Shuo Liu, Nirupam Gupta, Nitin H. Vaidya
- Abstract要約: 本稿では,サーバアーキテクチャにおける分散最適化と学習のレジリエンスの問題について考察する。
システムはサーバと複数のエージェントから構成され、各エージェントは独自のローカルコスト関数を持つ。
局所コスト関数が十分冗長であることを考えると、実際に$(f, r; epsilon)$-レジリエンスが達成できることが示される。
- 参考スコア（独自算出の注目度）: 4.664766612388049
- 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))$-レジリエンスが実際に達成可能であることを(理論的にも経験的にも)構築的に示す。
関連論文リスト
- Communication Efficient Decentralization for Smoothed Online Convex Optimization [9.449153668916098]
マルチエージェントSmoothed Online Convex Optimization(SOCO)問題について検討し,通信グラフを通してN$エージェントが対話する。
各ラウンドにおいて、各エージェント$i$は、オンラインの方法で、強い凸打撃コスト関数$fi_t$を受け取る。
通信グラフが時間とともに任意かつ適応的に変化する場合でも,我々の結果は維持される。
論文 参考訳（メタデータ） (2024-11-13T05:59:04Z) - 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) - On the Resilience of Multi-Agent Systems with Malicious Agents [58.79302663733702]
本稿では,悪意のあるエージェント下でのマルチエージェントシステムのレジリエンスについて検討する。
我々は、任意のエージェントを悪意のあるエージェントに変換する2つの方法、AutoTransformとAutoInjectを考案した。
各エージェントが他のエージェントの出力に挑戦するためのメカニズムを導入するか、あるいはメッセージのレビューと修正を行う追加のエージェントを導入することで、システムのレジリエンスを高めることができることを示す。
論文 参考訳（メタデータ） (2024-08-02T03:25:20Z) - Data Sharing for Mean Estimation Among Heterogeneous Strategic Agents [11.371461065112422]
通常の分布からサンプルを収集することにより,$m$エージェントがベクトル$muinmathbbRd$を推定する協調学習問題について検討する。
独自の作業を行う代わりに、エージェントはコストの安いデータを収集し、それと引き換えに他のデータと共有することができる。
論文 参考訳（メタデータ） (2024-07-20T17:45:40Z) - Self-Localized Collaborative Perception [49.86110931859302]
我々は,新しい自己局在型協調認識システムであるMathttCoBEVGlue$を提案する。
$mathttCoBEVGlue$は、エージェント間の相対的なポーズを提供する新しい空間アライメントモジュールである。
$mathttCoBEVGlue$は任意のローカライゼーションノイズとアタックの下で最先端の検出性能を達成する。
論文 参考訳（メタデータ） (2024-06-18T15:26:54Z) - Refined Sample Complexity for Markov Games with Independent Linear Function Approximation [49.5660193419984]
マルコフゲーム(MG)はマルチエージェント強化学習(MARL)の重要なモデルである
本稿では、WangらによるAVLPRフレームワークを改良し(2023年)、最適部分ギャップの悲観的推定を設計する。
マルチエージェントの呪いに取り組み、最適な$O(T-1/2)収束率を達成し、同時に$textpoly(A_max)$依存性を避ける最初のアルゴリズムを与える。
論文 参考訳（メタデータ） (2024-02-11T01:51:15Z) - Cooperative Multi-Agent Reinforcement Learning: Asynchronous
Communication and Linear Function Approximation [77.09836892653176]
マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。
本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。
我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
論文 参考訳（メタデータ） (2023-05-10T20:29:29Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。