論文の概要: DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization for Time-Varying Gossips

• arxiv url: http://arxiv.org/abs/2208.00779v1
• Date: Tue, 26 Jul 2022 08:47:54 GMT
• ステータス: 処理完了
• システム内更新日: 2022-08-07 14:21:42.501203
• Title: DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization for Time-Varying Gossips
• Title（参考訳）: dadao: 時間変動ゴシップに対する分散分散非同期最適化
• Authors: Adel Nabli (MLIA, ISIR), Edouard Oyallon (MLIA, ISIR)
• Abstract要約: DADAOは、分散非同期計算アルゴリズムである。 我々のアルゴリズムは、$mathcalO(nsqrtfracLmulog epsilon)$局所勾配と$mathcalO(nsqrtchi*sqrtfracLmulog epsilon)$通信で精度が$epsilon$に達する必要がある。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: DADAO is a novel decentralized asynchronous stochastic algorithm to minimize a sum of $L$-smooth and $\mu$-strongly convex functions distributed over a time-varying connectivity network of size $n$. We model the local gradient updates and gossip communication procedures with separate independent Poisson Point Processes, decoupling the computation and communication steps in addition to making the whole approach completely asynchronous. Our method employs primal gradients and do not use a multi-consensus inner loop nor other ad-hoc mechanisms as Error Feedback, Gradient Tracking or a Proximal operator. By relating spatial quantities of our graphs $\chi^*_1,\chi_2^*$ to a necessary minimal communication rate between nodes of the network, we show that our algorithm requires $\mathcal{O}(n\sqrt{\frac{L}{\mu}}\log \epsilon)$ local gradients and only $\mathcal{O}(n\sqrt{\chi_1^*\chi_2^*}\sqrt{\frac{L}{\mu}}\log \epsilon)$ communications to reach a precision $\epsilon$. If SGD with uniform noise $\sigma^2$ is used, we reach a precision $\epsilon$ with same speed, up to a bias term in $\mathcal{O}(\frac{\sigma^2}{\sqrt{\mu L}})$. This improves upon the bounds obtained with current state-of-the-art approaches, our simulations validating the strength of our relatively unconstrained method. Our source-code is released on a public repository.
• Abstract（参考訳）: DADAOは、$L$-smoothと$\mu$-strongly convex関数の合計を、サイズ$n$の時間変化接続ネットワーク上で分散する、分散化された非同期確率論的アルゴリズムである。 我々は、独立したポアソンポイントプロセスで局所的な勾配の更新とゴシップ通信の手順をモデル化し、計算と通信のステップを分離し、アプローチ全体を完全に非同期にする。 提案手法は一次勾配を用いており,マルチコンセンサス内ループや,エラーフィードバック,勾配追従,近似演算子などのアドホック機構は使用していない。 我々のグラフの空間的量 $\chi^*_1,\chi_2^*$ をネットワークノード間の必要最小限の通信速度に関連付けることにより、我々のアルゴリズムは$\mathcal{O}(n\sqrt {\frac{L}{\mu}}\log \epsilon)$局所勾配と$\mathcal{O}(n\sqrt{\chi_1^*\chi_2^*}\sqrt {\frac{L}{\mu}}\log \epsilon)$通信のみを必要とすることを示す。 均一ノイズ$\sigma^2$を使用すると、同じ速度で精度$\epsilon$に達し、$\mathcal{O}(\frac{\sigma^2}{\sqrt{\mu L}})$のバイアス項に達する。 これにより、現在の最先端手法で得られる限界を改善し、比較的制約のない手法の強度をシミュレーションで検証する。 ソースコードはパブリックリポジトリで公開されています。

関連論文リスト

• Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation [77.09836892653176]
  マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。 本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。 我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
  論文  参考訳（メタデータ） (2023-05-10T20:29:29Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。 我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
  論文  参考訳（メタデータ） (2022-10-14T01:42:05Z)
• Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
  通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。 本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。 また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
  論文  参考訳（メタデータ） (2022-06-16T17:10:57Z)
• Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
  集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。 $varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。 この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
  論文  参考訳（メタデータ） (2021-10-24T04:03:00Z)
• Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
  遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。 本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
  論文  参考訳（メタデータ） (2021-06-22T15:50:45Z)
• Communication-efficient SGD: From Local SGD to One-Shot Averaging [16.00658606157781]
  複数の作業者に対して並列化することで,勾配降下(SGD)の高速化を検討する。 そこで本研究では,反復数の増加に伴って通信頻度を小さくすることで,全体の通信を減らし,局所的なSGD方式を提案する。
  論文  参考訳（メタデータ） (2021-06-09T01:10:34Z)
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
  実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。 我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
  論文  参考訳（メタデータ） (2021-04-06T15:34:14Z)
• On the Benefits of Multiple Gossip Steps in Communication-Constrained Decentralized Optimization [29.42301299741866]
  ステップサイズが一定である$O(logfrac1epsilon)$の反復を$O(logfrac1epsilon)$とすることで、スムーズな非圧縮勾配目的に対する最適値の$epsilon$に収束できることを示す。 我々の知る限り、これは圧縮された通信圧縮パラメータの下での非最適化の収束結果を導出した最初の研究である。
  論文  参考訳（メタデータ） (2020-11-20T21:17:32Z)

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

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