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

arXiv: https://arxiv.org/abs/2511.19513 · HTML: https://mlsanity.com/paper/2511.19513/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 60 references that are in the map.
- First posted on arXiv 24 Nov 2025.

## Builds on (most cited first, 30 of 30)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication](https://mlsanity.com/paper/1902.00340/) (2019)
- [Fixup Initialization: Residual Learning Without Normalization](https://mlsanity.com/paper/1901.09321/) (2019)
- [On the Convergence of Decentralized Gradient Descent](https://mlsanity.com/paper/1310.7063/) (2013)
- [Stochastic Gradient Push for Distributed Deep Learning](https://mlsanity.com/paper/1811.10792/) (2018)
- [Distributed Stochastic Gradient Tracking Methods](https://mlsanity.com/paper/1805.11454/) (2018)
- [Communication Compression for Decentralized Training](https://mlsanity.com/paper/1803.06443/) (2018)
- [Distributed optimization over time-varying directed graphs](https://mlsanity.com/paper/1303.2289/) (2013)
- [An Improved Analysis of Gradient Tracking for Decentralized Machine Learning](https://mlsanity.com/paper/2202.03836/) (2022)
- [The alignment property of SGD noise and how it helps select flat minima: A stability analysis](https://mlsanity.com/paper/2207.02628/) (2022)
- [Exponential Graph is Provably Efficient for Decentralized Deep Training](https://mlsanity.com/paper/2110.13363/) (2021)
- [Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Development](https://mlsanity.com/paper/1702.05122/) (2017)
- [A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learning](https://mlsanity.com/paper/2110.09993/) (2021)
- [Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD](https://mlsanity.com/paper/2105.08023/) (2021)
- [On the Learning Behavior of Adaptive Networks - Part I: Transient Analysis](https://mlsanity.com/paper/1312.7581/) (2013)
- [Exact Diffusion for Distributed Optimization and Learning --- Part II: Convergence Analysis](https://mlsanity.com/paper/1702.05142/) (2017)
- [FROST -- Fast row-stochastic optimization with uncoordinated step-sizes](https://mlsanity.com/paper/1803.09169/) (2018)
- [Differentially Private Decentralized Learning with Random Walks](https://mlsanity.com/paper/2402.07471/) (2024)
- [Distributed Nesterov gradient methods over arbitrary graphs](https://mlsanity.com/paper/1901.06995/) (2019)
- [Information Exchange and Learning Dynamics over Weakly-Connected Adaptive Networks](https://mlsanity.com/paper/1412.1523/) (2014)
- [Decentralized Bilevel Optimization: A Perspective from Transient Iteration Complexity](https://mlsanity.com/paper/2402.03167/) (2024)
- [A Fast Row-Stochastic Decentralized Method for Distributed Optimization Over Directed Graphs](https://mlsanity.com/paper/2112.13257/) (2021)
- [Understanding the Influence of Digraphs on Decentralized Optimization: Effective Metrics, Lower Bound, and Optimal Algorithm](https://mlsanity.com/paper/2312.04928/) (2023)
- [SPARKLE: A Unified Single-Loop Primal-Dual Framework for Decentralized Bilevel Optimization](https://mlsanity.com/paper/2411.14166/) (2024)
- [Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-stochastic Networks](https://mlsanity.com/paper/2506.04600/) (2025)
- [DICE: Data Influence Cascade in Decentralized Learning](https://mlsanity.com/paper/2507.06931/) (2025)

## Abstract (arXiv)

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 L2(λ;ℝ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.