論文の概要: DASA: Delay-Adaptive Multi-Agent Stochastic Approximation

• arxiv url: http://arxiv.org/abs/2403.17247v3
• Date: Fri, 2 Aug 2024 09:03:09 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-05 18:13:29.879092
• Title: DASA: Delay-Adaptive Multi-Agent Stochastic Approximation
• Title（参考訳）: DASA: 遅延適応型マルチエージェント確率近似
• Authors: Nicolò Dal Fabbro, Arman Adibi, H. Vincent Poor, Sanjeev R. Kulkarni, Aritra Mitra, George J. Pappas,
• Abstract要約: 我々は,N$エージェントが並列に動作し,中央サーバと通信することで,一般的な近似問題を高速化することを目的とした設定を考える。 遅延とストラグラーの効果を軽減するために,マルチエージェント近似のための遅延適応アルゴリズムである textttDASA を提案する。
• 参考スコア（独自算出の注目度）: 64.32538247395627
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider a setting in which $N$ agents aim to speedup a common Stochastic Approximation (SA) problem by acting in parallel and communicating with a central server. We assume that the up-link transmissions to the server are subject to asynchronous and potentially unbounded time-varying delays. To mitigate the effect of delays and stragglers while reaping the benefits of distributed computation, we propose \texttt{DASA}, a Delay-Adaptive algorithm for multi-agent Stochastic Approximation. We provide a finite-time analysis of \texttt{DASA} assuming that the agents' stochastic observation processes are independent Markov chains. Significantly advancing existing results, \texttt{DASA} is the first algorithm whose convergence rate depends only on the mixing time $\tau_{mix}$ and on the average delay $\tau_{avg}$ while jointly achieving an $N$-fold convergence speedup under Markovian sampling. Our work is relevant for various SA applications, including multi-agent and distributed temporal difference (TD) learning, Q-learning and stochastic optimization with correlated data.
• Abstract（参考訳）: 我々は,Stochastic Approximation (SA) 問題を並列に動作し,中央サーバと通信することで高速化することを目的としている。 サーバへのアップリンク送信は、非同期で潜在的に非バウンドな時間変化の遅延にさらされていると仮定する。 分散計算の利点を享受しながら遅延とストラグラーの効果を緩和するため,マルチエージェント確率近似のための遅延適応アルゴリズムである \texttt{DASA} を提案する。 エージェントの確率的観察過程が独立なマルコフ連鎖であることを仮定して、 texttt{DASA} の有限時間解析を行う。 既存の結果を前進させる最初のアルゴリズムは、収束速度が混合時間$\tau_{mix}$と平均遅延$\tau_{avg}$にのみ依存するが、マルコヴィアンサンプリングでは$N$倍収束速度を共同で達成する。 我々の研究は、マルチエージェントおよび分散時間差学習(TD)、Qラーニング、相関データによる確率的最適化など、様々なSAアプリケーションに関係している。

関連論文リスト

• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。 我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
  論文  参考訳（メタデータ） (2024-02-19T03:08:02Z)
• Federated Learning Using Variance Reduced Stochastic Gradient for Probabilistically Activated Agents [0.0]
  本稿では,各エージェントが各反復において任意の選択の確率を持つような最適解に対して,分散低減と高速収束率の両方を達成する2層構造を持つフェデレートラーニング(FL)のアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-10-25T22:04:49Z)
• Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
  通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。 本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。 また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
  論文  参考訳（メタデータ） (2022-06-16T17:10:57Z)
• Distributed gradient-based optimization in the presence of dependent aperiodic communication [4.34720256795424]
  反復分散最適化アルゴリズムは、グローバルな目的を最小化/最大化するために、時間とともに相互に通信する複数のエージェントを含む。 信頼できない通信網の存在下では、受信したデータの鮮度を測定するAOI( Age-of-Information)は、大きくなり、アルゴリズムの収束を妨げる可能性がある。 AoIプロセスに付随する確率変数が有限な第一モーメントを持つ確率変数に支配されている場合、収束が保証されることを示す。
  論文  参考訳（メタデータ） (2022-01-27T06:44:04Z)
• Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
  集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。 $varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。 この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
  論文  参考訳（メタデータ） (2021-10-24T04:03:00Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
  論文  参考訳（メタデータ） (2021-07-06T21:59:49Z)
• Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
  遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。 本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
  論文  参考訳（メタデータ） (2021-06-22T15:50:45Z)
• Decentralized Optimization with Heterogeneous Delays: a Continuous-Time Approach [6.187780920448871]
  非同期アルゴリズムを解析するための新しい連続時間フレームワークを提案する。 我々は,スムーズな凸関数と強い凸関数の和を最小化するために,完全に非同期な分散アルゴリズムを記述する。
  論文  参考訳（メタデータ） (2021-06-07T13:09:25Z)
• Accelerating Distributed SGD for Linear Regression using Iterative Pre-Conditioning [0.966840768820136]
  繰り返しプレコンディショニングされたグラディエント・ディフレッシュ法(IPSG)は,既存の分散アルゴリズムよりも高速に収束することを示した。 IPSG法の収束速度は、サーバベースネットワークにおける線形最小二乗問題を解くための顕著なアルゴリズムと比較して好意的に比較される。
  論文  参考訳（メタデータ） (2020-11-15T18:09:13Z)

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

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