arXiv:2511.19513cs.LG2025-11

行随机矩阵在去中心化学习中比双随机矩阵收敛更快,理论可证。

Row-Stochastic Matrices Can Provably Outperform Doubly Stochastic Matrices in Decentralized Learning

  • 引入加权希尔伯特空间,揭示行随机矩阵更优的数学机制。
  • 行随机设计即使谱隙更小,也能更快收敛,因无额外惩罚项。
  • 给出拓扑设计准则,指导实际网络结构优化。

去中心化学习常涉及异构节点权重 $λ$ 的加权全局损失。本文对比两种策略:(i) 将权重嵌入局部损失以保持均匀权重(即使用双随机矩阵),(ii) 保留原始损失并采用 $λ$-诱导的行随机矩阵。尽管两者均优化同一 $λ$-加权全局损失,其欧氏空间下的收敛保证是否紧致、行为差异本质仍不明确。为此,本文构建加权希尔伯特空间 $L^2(λ;\bR^d)$,推导出严格优于标准欧氏分析的收敛速率。在此几何下,行随机矩阵为自伴算子,而双随机矩阵不是,导致后者产生额外惩罚项,放大一致性误差,从而减缓收敛。因此,收敛差异不仅源于谱隙,还来自这些惩罚项。进一步,我们给出行随机设计更快收敛的充分条件,并通过瑞利商与Loewner序特征值比较,获得保证该优势的拓扑条件,进而提供实用的拓扑设计指南。

原文摘要 · Abstract (English)

Decentralized learning often involves a weighted global loss with heterogeneous node weights $λ$. We revisit two natural strategies for incorporating these weights: (i) embedding them into the local losses to retain a uniform weight (and thus a doubly stochastic matrix), and (ii) keeping the original losses while employing a $λ$-induced row-stochastic matrix. Although prior work shows that both strategies target the same $λ$-weighted global loss, it remains unclear whether the Euclidean-space guarantees are tight and what fundamentally differentiates their behaviors. To clarify this, we develop a weighted Hilbert-space framework $L^2(λ;\mathbb{R}^d)$ and obtain convergence rates that are strictly tighter than those from standard Euclidean analysis. In this geometry, the row-stochastic matrix becomes \emph{self-adjoint} whereas the doubly stochastic one does not, creating additional \emph{penalty terms} that amplify consensus error, thereby slowing convergence. Consequently, the difference in convergence arises not only from spectral gaps but also from these penalty terms. We then derive sufficient conditions under which the row-stochastic design converges faster even with a smaller spectral gap. Finally, by using a Rayleigh-quotient and Loewner-order eigenvalue comparison, we further obtain topology conditions that guarantee this advantage and yield practical topology-design guidelines.

去中心化学习矩阵设计收敛分析拓扑优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。