論文の概要: Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning

• arxiv url: http://arxiv.org/abs/2206.08307v1
• Date: Thu, 16 Jun 2022 17:10:57 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-17 16:52:38.065288
• Title: Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning
• Title（参考訳）: 分散・フェデレーション学習のための非同期SGDのためのシャーパ収束保証
• Authors: Anastasia Koloskova, Sebastian U. Stich, Martin Jaggi
• Abstract要約: 通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。 本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。 また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
• 参考スコア（独自算出の注目度）: 77.22019100456595
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the asynchronous stochastic gradient descent algorithm for distributed training over $n$ workers which have varying computation and communication frequency over time. In this algorithm, workers compute stochastic gradients in parallel at their own pace and return those to the server without any synchronization. Existing convergence rates of this algorithm for non-convex smooth objectives depend on the maximum gradient delay $\tau_{\max}$ and show that an $\epsilon$-stationary point is reached after $\mathcal{O}\!\left(\sigma^2\epsilon^{-2}+ \tau_{\max}\epsilon^{-1}\right)$ iterations, where $\sigma$ denotes the variance of stochastic gradients. In this work (i) we obtain a tighter convergence rate of $\mathcal{O}\!\left(\sigma^2\epsilon^{-2}+ \sqrt{\tau_{\max}\tau_{avg}}\epsilon^{-1}\right)$ without any change in the algorithm where $\tau_{avg}$ is the average delay, which can be significantly smaller than $\tau_{\max}$. We also provide (ii) a simple delay-adaptive learning rate scheme, under which asynchronous SGD achieves a convergence rate of $\mathcal{O}\!\left(\sigma^2\epsilon^{-2}+ \tau_{avg}\epsilon^{-1}\right)$, and does not require any extra hyperparameter tuning nor extra communications. Our result allows to show for the first time that asynchronous SGD is always faster than mini-batch SGD. In addition, (iii) we consider the case of heterogeneous functions motivated by federated learning applications and improve the convergence rate by proving a weaker dependence on the maximum delay compared to prior works. In particular, we show that the heterogeneity term in convergence rate is only affected by the average delay within each worker.
• Abstract（参考訳）: 分散学習のための非同期確率的勾配降下アルゴリズムを,計算時間と通信周波数の異なるn$ワーカーに対して検討した。 このアルゴリズムでは、作業者は自身のペースで確率勾配を並列に計算し、同期なしでサーバに返す。 非凸滑らかな目的に対するこのアルゴリズムの既存の収束速度は、最大勾配遅延$\tau_{\max}$に依存し、$\epsilon$-stationary pointが$\mathcal{O}\! \left(\sigma^2\epsilon^{-2}+ \tau_{\max}\epsilon^{-1}\right)$ iterations ここで$\sigma$は確率勾配の分散を表す。 この作品では (i)よりタイトな収束率は$\mathcal{o}\! \left(\sigma^2\epsilon^{-2}+ \sqrt{\tau_{\max}\tau_{avg}}\epsilon^{-1}\right)$\tau_{avg}$が平均遅延であり、$\tau_{\max}$よりもかなり小さい。 私たちはまた (ii)単純な遅延適応学習率スキームで、非同期sgdは$\mathcal{o}\! \left(\sigma^2\epsilon^{-2}+ \tau_{avg}\epsilon^{-1}\right)$, 余分なハイパーパラメータチューニングや余分な通信は不要である。 その結果、非同期SGDは常にミニバッチSGDよりも高速であることを示すことができる。 また、 (iii)フェデレーション学習による不均一関数の場合について検討し,先行研究に比べて最大遅延依存性の弱さを証明し,収束率の向上を図る。 特に、収束率の不均一性項は、各作業者の平均遅延によってのみ影響を受けることを示す。

関連論文リスト

• Faster Stochastic Optimization with Arbitrary Delays via Asynchronous Mini-Batching [25.95786289683455]
  遅延に関する事前の知識を必要とせずに、全ての量子化に同時に適応する手法を示す。 さらに、非サイズの$O(inf_q tau_q2/(q T)2+sigma/sqrtqT)$と、凸問題に対する$O(tau_q2/(q T)2+sigma/sqrtqT)$の収束率を得る。
  論文  参考訳（メタデータ） (2024-08-14T12:30:51Z)
• Convergence Analysis of Decentralized ASGD [1.8710230264817358]
  本稿では,ノード間の部分同期や制限的ネットワークトポロジを必要としない分散非同期SGD(DASGD)に対する新しい収束速度解析法を提案する。 我々の収束証明は、固定段数と任意の非滑らかで同質でL字型の目的函数を仮定する。
  論文  参考訳（メタデータ） (2023-09-07T14:50:31Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization [0.0]
  DADAOは、L$-smooth と $mu$-strongly convex 関数の和を最小化する最初の分散化、高速化、非同期化、プライマリ化、一階述語アルゴリズムである。 我々のアルゴリズムは、$mathcalO(nsqrtchisqrtfracLmulog(frac1epsilon)$ localと$mathcalO(nsqrtchisqrtfracLmulog()のみを必要とすることを示す。
  論文  参考訳（メタデータ） (2022-07-26T08:47:54Z)
• Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
  遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。 本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
  論文  参考訳（メタデータ） (2021-06-22T15:50:45Z)
• 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)
• Differentially Quantized Gradient Methods [53.3186247068836]
  微分量子化グラディエントDescence (DQ-GD) が$maxsigma_mathrmGD, rhon 2-R$の線形収縮係数を得ることを示す。 あるクラス内のアルゴリズムは$maxsigma_mathrmGD, 2-R$よりも早く収束できない。
  論文  参考訳（メタデータ） (2020-02-06T20:40:53Z)

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

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