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

Decentralized learning often involves a weighted global loss with heterogeneous node weights $\lambda$. 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 $\lambda$-induced row-stochastic matrix. Although prior work shows that both strategies target the same $\lambda$-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(\lambda;\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 *self-adjoint* whereas the doubly stochastic one does not, creating additional *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.

Modern machine learning models are often trained across many devices without gathering all data in one place. In such decentralized learning systems, different nodes may have different amounts of data or different importance, so the final model should not always treat every node equally. A key question is how to correctly and efficiently handle these unequal node weights during training. This paper studies two common ways to include node weights. One way puts the weights directly into each node’s local training loss. The other keeps the local losses unchanged but changes how nodes communicate and average information. Although both strategies aim to optimize the same weighted learning problem, they can behave quite differently during training. We show that the difference comes from the geometry of the communication process. By analyzing the problem in a weighted space that matches the node weights, we find that one communication design has a cleaner mathematical structure and avoids extra penalty terms that slow down convergence. This explains why it can train faster even when standard analyses suggest otherwise. Our results also give practical guidance on how to design communication networks for decentralized learning with heterogeneous node weights.