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

• arxiv url: http://arxiv.org/abs/2403.15654v1
• Date: Sat, 23 Mar 2024 00:01:34 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-26 21:41:55.400621
• Title: The Effectiveness of Local Updates for Decentralized Learning under Data Heterogeneity
• Title（参考訳）: データ不均一性を考慮した分散学習におけるローカル更新の有効性
• Authors: Tongle Wu, Ying Sun,
• Abstract要約: DGT(Decentralized Gradient Tracking)とDGD(Decentralized Gradient Descent)の2つの基本的な分散最適化手法を再検討する。 K > 1$ ローカル更新のステップを組み込むことで通信の複雑さを低減できることを示す。
• 参考スコア（独自算出の注目度）: 2.845817138242963
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 $K > 1$ 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} + \frac{\delta}{\mu (1 - \rho)} + \frac{\rho }{(1 - \rho)^2} \cdot \frac{L+ \delta}{\mu}\Big)$, where $\rho$ measures the network connectivity and $\delta$ measures the second-order heterogeneity of the local loss. Our result reveals the tradeoff between communication and computation and shows 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, can yield a similar effect as DGT in reducing communication complexity. Numerical experiments validate our theoretical results.
• Abstract（参考訳）: 本稿では,DGT (Decentralized Gradient Tracking) とDGD (Decentralized Gradient Descent) の2つの基本的な分散最適化手法を再検討する。 2つの設定を考慮し、$K > 1$ ローカル更新手順を組み込むことで通信の複雑さを低減できることを示す。 具体的には、$\mu$-strongly convex および $L$-smooth loss function に対して、局所DGT が通信複雑性を達成できることを証明した。 $\tilde{\mathcal{O}} \Big(\frac{L}{\mu K} + \frac{\delta}{\mu (1 - \rho)} + \frac{\rho }{(1 - \rho)^2} \cdot \frac{L+ \delta}{\mu}\Big)$。 その結果、通信と計算のトレードオフを明らかにし、データ不均一性が低くネットワークが十分に接続されている場合、K$の増加は通信コストを効果的に削減できることを示した。 次に、局所的な損失が同じ最小値を共有する過度パラメータ化方式を考察し、DGDの局所的な更新を用いることで、勾配補正がなくても通信複雑性の低減にDGTと同じような効果が得られることを示した。 数値実験により理論的結果が検証された。

関連論文リスト

• A Proximal Gradient Method With Probabilistic Multi-Gossip Communications for Decentralized Composite Optimization [36.777745196161035]
  本稿では,分散合成(平滑+非平滑)最適化のための通信効率の良いMG-Skipを提案する。 MG-Skipは通信の複雑さを最適に達成し,非滑らかなセットアップにおけるローカル更新の利点を確認する。
  論文  参考訳（メタデータ） (2023-12-19T05:13:16Z)
• 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)
• Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
  集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。 $varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。 この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
  論文  参考訳（メタデータ） (2021-10-24T04:03:00Z)
• 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)
• Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD [15.112499553818953]
  D$2$/Exact-diffusionアルゴリズムの非同相収束特性について検討する。 既存の分散アルゴリズムと比較して、D$2$/Exact-diffusionはネットワークトポロジに最も敏感です。
  論文  参考訳（メタデータ） (2021-05-17T17:16:52Z)
• Hogwild! over Distributed Local Data Sets with Linearly Increasing Mini-Batch Sizes [26.9902939745173]
  Hogwild!は非同期のGradient Descentを実装し、複数のスレッドが並列に、トレーニングデータを含む共通のリポジトリにアクセスする。 通信コストを削減するため,ローカルな計算ノードがより小さなミニバッチサイズを選択し始める方法を示す。
  論文  参考訳（メタデータ） (2020-10-27T03:46:09Z)

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

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