論文の概要: Distributed Learning over Arbitrary Topology: Linear Speed-Up with Polynomial Transient Time

• arxiv url: http://arxiv.org/abs/2503.16123v2
• Date: Sun, 27 Jul 2025 06:22:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-29 14:15:45.93454
• Title: Distributed Learning over Arbitrary Topology: Linear Speed-Up with Polynomial Transient Time
• Title（参考訳）: 任意位相上の分散学習:多項式過渡時間による線形高速化
• Authors: Runze You, Shi Pu,
• Abstract要約: 本研究では, ピアツーピア通信によるローカルコスト関数の和を協調的に共有する分散学習問題について検討する。 本稿では、一般的な通信グラフから抽出した2本の木を用いて、モデルパラメータと位相パラメータの両方を分散する新しいEmph Tree PushPull-(STPP)を提案する。
• 参考スコア（独自算出の注目度）: 3.1789549088190414
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• 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, \emph{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 $\mathcal{O}(n^7)$ for smooth nonconvex objectives and $\tilde{\mathcal{O}}(n^3)$ for smooth strongly convex objectives -- under arbitrary network topologies. Moreover, compared with existing methods, STPP achieves faster convergence rates on sparse and non-regular topologies (e.g., directed rings) and reduces communication overhead on dense networks (e.g., static exponential graphs). Numerical experiments further demonstrate the strong performance of STPP across various graph architectures.
• Abstract（参考訳）: ピアツーピア通信による局所的コスト関数の和を最小化する分散学習問題について検討する。 本稿では, 一般的な通信グラフから抽出した2本のスパンニング木を用いて, モデルパラメータと確率勾配を分散する新しいアルゴリズム, \emph{Spanning Tree Push-Pull} (STPP) を提案する。 スペクトルギャップ特性に大きく依存する従来のアプローチとは異なり、STPPはより柔軟な位相特性を活用し、堅牢な情報フローと効率的な更新を可能にする。 理論的には、スムーズな非凸目的に対して$\mathcal{O}(n^7)$、スムーズな強凸目的に対して$\tilde{\mathcal{O}}(n^3)$まで、任意のネットワークトポロジーの下で、STPPが線形スピードアップおよび多項式過渡反復複雑性を達成することを証明している。 さらに、既存の手法と比較して、STPPはスパースおよび非正則位相(例えば、有向環)の収束速度を高速化し、高密度ネットワーク(例えば、静的指数グラフ)での通信オーバーヘッドを低減する。 数値実験は、様々なグラフアーキテクチャにおけるSTPPの強い性能をさらに実証する。

関連論文リスト

• Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time [45.72323731094864]
  本稿では,2層ReLULUネットワーク間における重み減衰と凸緩和の最適性ギャップについて検討する。 私たちの研究は、なぜローカルメソッドがうまく機能するのかを理解することに新たな光を当てています。
  論文  参考訳（メタデータ） (2024-02-06T01:29:35Z)
• 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)
• Topological Graph Signal Compression [7.836468889756101]
  本稿では,グラフ上での信号圧縮のための新しいTDL法を提案する。 我々のフレームワークは標準GNNとフィードフォワードアーキテクチャの両方を改善している。
  論文  参考訳（メタデータ） (2023-08-21T22:26:21Z)
• 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)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• 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)
• Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
  単純複体は多方向順序関係を明示的にエンコードするグラフの高次元一般化と見なすことができる。 単体錯体の$k$-homological特徴によってパラメータ化された関数のグラフ畳み込みモデルを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:59:41Z)
• 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)
• $p$-Norm Flow Diffusion for Local Graph Clustering [18.90840167452118]
  我々は、p-ノルムネットワークフローとの拡散を$pin (1,infty)$とする凸最適化定式化の族を示す。 局所クラスタリングでは,入力種子の周囲の低コンダクタンスカットの発見に有用であることを示す。 提案手法は,pge 2$の強い局所実行時間で解き,合成グラフと実世界のグラフの両方で実験的な評価を行い,既存の手法とよく比較できることを示す。
  論文  参考訳（メタデータ） (2020-05-20T01:08:17Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。 我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。 いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
  論文  参考訳（メタデータ） (2020-05-05T18:08:23Z)
• Fully Asynchronous Policy Evaluation in Distributed Reinforcement Learning over Networks [14.636457985379746]
  本稿では,有向ピアツーピアネットワーク上での分散強化学習(DisRL)のポリシー評価問題に対する非同期手法を提案する。 ネットワークの他のノードを待つことなく、各ノードは隣人からの(おそらく遅れた)情報を使用して、いつでもローカルに値関数を更新できる。
  論文  参考訳（メタデータ） (2020-03-01T08:12:08Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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