論文の概要: Distributed Learning over Arbitrary Topology: Linear Speed-Up with Polynomial Transient Time
- arxiv url: http://arxiv.org/abs/2503.16123v1
- Date: Thu, 20 Mar 2025 13:11:44 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-21 22:27:01.014745
- Title: Distributed Learning over Arbitrary Topology: Linear Speed-Up with Polynomial Transient Time
- Title（参考訳）: 任意位相上の分散学習:多項式過渡時間による線形高速化
- Authors: Runze You, Shi Pu,
- Abstract要約: ピアツーピア通信によるローカルコスト関数の和を協調的に行う分散学習問題について検討する。
本稿では、一般的な通信グラフから抽出した2本の木を用いて、モデルパラメータとパラメータの両方を分散するSpanning Tree Push-Pull(STPP)を提案する。
- 参考スコア（独自算出の注目度）: 3.1789549088190414
- License:
- Abstract: We study a distributed learning problem in which $n$ agents, each with potentially heterogeneous local data, collaboratively minimize the sum of their local cost functions via peer-to-peer communication. We propose a novel algorithm, Spanning Tree Push-Pull (STPP), which employs two spanning trees extracted from a general communication graph to distribute both model parameters and stochastic gradients. Unlike prior approaches that rely heavily on spectral gap properties, STPP leverages a more flexible topological characterization, enabling robust information flow and efficient updates. Theoretically, we prove that STPP achieves linear speedup and polynomial transient iteration complexity, up to $O(n^7)$ for smooth nonconvex objectives and $\tilde{O}(n^3)$ for smooth strongly convex objectives, under arbitrary network topologies. Moreover, compared with the existing methods, STPP achieves faster convergence rates on sparse and non-regular topologies (e.g., directed ring) and reduces communication overhead on dense networks (e.g., static exponential graph). These results significantly advance the state of the art, especially when $n$ is large. Numerical experiments further demonstrate the strong performance of STPP and confirm the practical relevance of its theoretical convergence rates across various common graph architectures. Our code is available at https://anonymous.4open.science/r/SpanningTreePushPull-5D3E.
- Abstract（参考訳）: ピアツーピア通信による局所的コスト関数の和を最小化する分散学習問題について検討する。
本稿では,一般的な通信グラフから抽出した2本のスパンニング木を用いて,モデルパラメータと確率勾配の両方を分散する新しいアルゴリズム,Spanning Tree Push-Pull (STPP)を提案する。
スペクトルギャップ特性に大きく依存する従来のアプローチとは異なり、STPPはより柔軟な位相特性を活用し、堅牢な情報フローと効率的な更新を可能にする。
理論的には、STPPは、滑らかな非凸対象に対して最大$O(n^7)$、滑らかな強凸対象に対して$\tilde{O}(n^3)$まで、任意のネットワークトポロジーの下で線形スピードアップおよび多項式過渡反復の複雑性を達成することを証明している。
さらに、既存の手法と比較して、STPPはスパースおよび非正則位相(例えば、有向環)の収束速度を高速化し、高密度ネットワーク(例えば、静的指数グラフ)での通信オーバーヘッドを低減する。
これらの結果は、特に$n$が大きければ、最先端を著しく推し進める。
数値実験により、STPPの強い性能を実証し、様々な共通グラフアーキテクチャにおける理論収束率の実用的妥当性を確認する。
私たちのコードはhttps://anonymous.4open.science/r/SpanningTreePushPull-5D3Eで利用可能です。
関連論文リスト
- Epidemic Learning: Boosting Decentralized Learning with Randomized
Communication [8.685687713892193]
本稿では,単純だが強力な分散学習(DL)アルゴリズムであるエピデミック学習(EL)を提案する。
ELはベースラインのDLアルゴリズムよりも高速に1.7times$1.7timesまで収束し、同じ通信量に対して2.2$%高い精度を達成する。
我々の結果は、ELがベースラインDLアルゴリズムよりも高速に1.7times$1.7timesまで収束し、同じ通信量に対して2.2$%高い精度に達することを示している。
論文 参考訳（メタデータ） (2023-10-03T11:28:54Z) - Beyond Exponential Graph: Communication-Efficient Topologies for
Decentralized Learning via Finite-time Convergence [31.933103173481964]
高速なコンセンサス率と最小の最大度を組み合わせた新しいトポロジーを提案する。
Base-$(k + 1)$ Graph は指数グラフよりも高速収束率と通信効率の高い分散 SGD (DSGD) を提供する。
論文 参考訳（メタデータ） (2023-05-19T04:08:07Z) - Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。
第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
論文 参考訳（メタデータ） (2023-02-02T08:33: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) - Deep Architecture Connectivity Matters for Its Convergence: A
Fine-Grained Analysis [94.64007376939735]
我々は、勾配降下訓練におけるディープニューラルネットワーク(DNN)の収束に対する接続パターンの影響を理論的に特徴づける。
接続パターンの単純なフィルタリングによって、評価対象のモデルの数を削減できることが示される。
論文 参考訳（メタデータ） (2022-05-11T17:43:54Z) - Decentralized Sparse Linear Regression via Gradient-Tracking: Linear Convergence and Statistical Guarantees [23.256961881716595]
エージェントネットワーク上の疎線形回帰を非指向グラフとしてモデル化し,サーバノードを持たない。
分布予測勾配追跡に基づくアルゴリズムの収束率と統計的保証を解析する。
論文 参考訳（メタデータ） (2022-01-21T01:26:08Z) - Distributed Sparse Feature Selection in Communication-Restricted
Networks [6.9257380648471765]
疎線形回帰と特徴選択のための新しい分散スキームを提案し,理論的に解析する。
データセット全体から因果次元を推定するために,ネットワーク内の情報共有をシンプルかつ効果的に行う手法を提案する。
論文 参考訳（メタデータ） (2021-11-02T05:02:24Z) - Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。
$varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。
この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
論文 参考訳（メタデータ） (2021-10-24T04:03:00Z) - Towards an Understanding of Benign Overfitting in Neural Networks [104.2956323934544]
現代の機械学習モデルは、しばしば膨大な数のパラメータを使用し、通常、トレーニング損失がゼロになるように最適化されている。
ニューラルネットワークの2層構成において、これらの良質な過適合現象がどのように起こるかを検討する。
本稿では,2層型ReLUネットワーク補間器を極小最適学習率で実現可能であることを示す。
論文 参考訳（メタデータ） (2021-06-06T19:08:53Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。