論文の概要: The Effectiveness of Local Updates for Decentralized Learning under Data Heterogeneity

• arxiv url: http://arxiv.org/abs/2403.15654v3
• Date: Tue, 24 Dec 2024 03:37:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-25 15:52:14.869090
• Title: The Effectiveness of Local Updates for Decentralized Learning under Data Heterogeneity
• Title（参考訳）: データ不均一性を考慮した分散学習におけるローカル更新の有効性
• Authors: Tongle Wu, Zhize Li, Ying Sun,
• Abstract要約: DGT(Decentralized Gradient Tracking)とDGD(Decentralized Gradient Descent)の2つの基本的な分散最適化手法を再検討する。 ローカルDGTが通信複雑性を$tildemathcalO Big(fracLmu(K+1) + fracdelta + mumu (1 - rho) + fracrho (1 - rho)2 cdot fracL+ deltamuBig)$, %zhizeを達成することを証明した。
• 参考スコア（独自算出の注目度）: 15.394956794959615
• License:
• Abstract: We revisit two fundamental decentralized optimization methods, Decentralized Gradient Tracking (DGT) and Decentralized Gradient Descent (DGD), with multiple local updates. We consider two settings and demonstrate that incorporating local update steps can reduce communication complexity. Specifically, for $\mu$-strongly convex and $L$-smooth loss functions, we proved that local DGT achieves communication complexity {}{$\tilde{\mathcal{O}} \Big(\frac{L}{\mu(K+1)} + \frac{\delta + {}{\mu}}{\mu (1 - \rho)} + \frac{\rho }{(1 - \rho)^2} \cdot \frac{L+ \delta}{\mu}\Big)$}, %\zhize{seems to be $\tilde{\mathcal{O}}$} {where $K$ is the number of additional local update}, $\rho$ measures the network connectivity and $\delta$ measures the second-order heterogeneity of the local losses. Our results reveal the tradeoff between communication and computation and show increasing $K$ can effectively reduce communication costs when the data heterogeneity is low and the network is well-connected. We then consider the over-parameterization regime where the local losses share the same minimums. We proved that employing local updates in DGD, even without gradient correction, achieves exact linear convergence under the Polyak-{\L}ojasiewicz (PL) condition, which can yield a similar effect as DGT in reducing communication complexity. {}{Customization of the result to linear models is further provided, with improved rate expression. }Numerical experiments validate our theoretical results.
• Abstract（参考訳）: 本稿では,DGT (Decentralized Gradient Tracking) とDGD (Decentralized Gradient Descent) の2つの基本的な分散最適化手法を再検討する。 2つの設定を考慮し、ローカル更新手順を組み込むことで通信の複雑さを低減できることを実証する。 具体的には、$\mu$-strongly convex と $L$-smooth loss function に対して、局所DGT が通信複雑性 {}{$\tilde{\mathcal{O}} \Big(\frac{L}{\mu(K+1)} + \frac{\delta + {}{\mu}}{\mu (1 - \rho)} + \frac{\rho }{(1 - \rho)^2} \cdot \frac{L+ \delta}{\mu}\Big)$} であることを示す。 この結果から,通信と計算のトレードオフが明らかとなり,データ不均一性が低く,ネットワークが十分に接続された場合の通信コストを効果的に削減できることを示す。 次に、局所的な損失が同じ最小値を共有する過度パラメータ化体制について考察する。 我々は,DGDの局所的な更新を勾配補正なしで行うことで,Plyak-{\L}ojasiewicz (PL)条件下での正確な線形収束が達成され,通信複雑性の低減にDGTと類似した効果が得られることを示した。 さらに、リニアモデルに対する結果の}{Customizationが提供され、レート式が向上した。 数値実験は、我々の理論結果を検証する。

関連論文リスト

• Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition [71.33787410075577]
  線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。 我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-03-07T15:03:50Z)
• DFedADMM: Dual Constraints Controlled Model Inconsistency for Decentralized Federated Learning [52.83811558753284]
  分散学習(DFL)は、中央サーバーを捨て、分散通信ネットワークを確立する。 既存のDFL手法は依然として、局所的な矛盾と局所的な過度なオーバーフィッティングという2つの大きな課題に悩まされている。
  論文  参考訳（メタデータ） (2023-08-16T11:22:36Z)
• 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)
• On the Performance of Gradient Tracking with Local Updates [10.14746251086461]
  LU-GTは通信品質は同じであるが、任意のネットワークトポロジが可能であることを示す。 数値的な例では、局所的な更新は特定のレシエーションにおける通信コストを低下させる可能性がある。
  論文  参考訳（メタデータ） (2022-10-10T15:13:23Z)
• DR-DSGD: A Distributionally Robust Decentralized Learning Algorithm over Graphs [54.08445874064361]
  本稿では,分散環境下での正規化された分散ロバストな学習問題を解くことを提案する。 Kullback-Liebler正規化関数をロバストなmin-max最適化問題に追加することにより、学習問題を修正されたロバストな問題に還元することができる。 提案アルゴリズムは, 最低分布検定精度を最大10%向上できることを示す。
  論文  参考訳（メタデータ） (2022-08-29T18:01:42Z)
• Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD for Communication Efficient Nonconvex Distributed Learning [58.79085525115987]
  ローカル手法は通信時間を短縮する有望なアプローチの1つである。 局所的データセットが局所的損失の滑らかさよりも小さい場合,通信の複雑さは非局所的手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-02-12T15:12:17Z)
• An Improved Analysis of Gradient Tracking for Decentralized Machine Learning [34.144764431505486]
  トレーニングデータが$n$エージェントに分散されるネットワーク上での分散機械学習を検討する。 エージェントの共通の目標は、すべての局所損失関数の平均を最小化するモデルを見つけることである。 ノイズのない場合、$p$を$mathcalO(p-1)$から$mathcalO(p-1)$に改善します。
  論文  参考訳（メタデータ） (2022-02-08T12:58:14Z)
• Decentralized Sparse Linear Regression via Gradient-Tracking: Linear Convergence and Statistical Guarantees [23.256961881716595]
  エージェントネットワーク上の疎線形回帰を非指向グラフとしてモデル化し,サーバノードを持たない。 分布予測勾配追跡に基づくアルゴリズムの収束率と統計的保証を解析する。
  論文  参考訳（メタデータ） (2022-01-21T01:26:08Z)
• Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
  与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。 次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。 頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
  論文  参考訳（メタデータ） (2021-07-22T14:25:16Z)
• Communication-efficient SGD: From Local SGD to One-Shot Averaging [16.00658606157781]
  複数の作業者に対して並列化することで,勾配降下(SGD)の高速化を検討する。 そこで本研究では,反復数の増加に伴って通信頻度を小さくすることで,全体の通信を減らし,局所的なSGD方式を提案する。
  論文  参考訳（メタデータ） (2021-06-09T01:10:34Z)
• Hogwild! over Distributed Local Data Sets with Linearly Increasing Mini-Batch Sizes [26.9902939745173]
  Hogwild!は非同期のGradient Descentを実装し、複数のスレッドが並列に、トレーニングデータを含む共通のリポジトリにアクセスする。 通信コストを削減するため,ローカルな計算ノードがより小さなミニバッチサイズを選択し始める方法を示す。
  論文  参考訳（メタデータ） (2020-10-27T03:46:09Z)

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

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