新算法实现任意网络下的线性加速，且收敛更快。
Distributed Learning over Arbitrary Topology: Linear Speed-Up with Polynomial Transient Time
- 用两棵生成树传递参数和梯度，适应任意通信拓扑
- 非凸目标下迭代复杂度为O(n⁷)，强凸目标下为Õ(n³)
- 在稀疏或密集网络中都表现更优，适合大规模分布式学习
我们研究了在任意通信拓扑下，n个拥有异构本地数据的代理通过点对点通信协作最小化各自局部代价函数之和的分布式学习问题。提出一种新算法——生成树推拉（STPP），利用从一般通信图中提取的两棵生成树来分发模型参数和随机梯度。与依赖谱间隙的方法不同，STPP采用更灵活的拓扑刻画，确保信息高效流动与更新。理论上证明，无论网络结构如何，该算法均能实现线性加速，并具有多项式暂态迭代复杂度：光滑非凸目标下为 𝒪(n⁷)，光滑强凸目标下为 Õ(n³)。相较于现有方法，STPP在稀疏及非规则拓扑（如有向环）上收敛更快，在稠密网络（如静态指数图）上通信开销更低。数值实验进一步验证了其在多种图结构中的优异性能。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。