2025/06/05 by Liyuan Liang, Xinyi Chen, Liang, Liyuan +5 · 1 citation
Computer Science · #Distributed Control Multi-Agent Systems #FOS: Mathematics #Optimization and Control (math.OC) #Privacy-Preserving Technologies in Data #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2506.04600
openalex publication_date 2025/06/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A key challenge in decentralized optimization is determining the optimal convergence rate and designing algorithms to achieve it. While this problem has been extensively addressed for doubly-stochastic and column-stochastic mixing matrices, the row-stochastic scenario remains unexplored. This paper bridges this gap by introducing effective metrics to capture the influence of row-stochastic mixing matrices and establishing the first convergence lower bound for decentralized learning over row-stochastic networks. However, existing algorithms fail to attain this lower bound due to two key issues: deviation in the descent direction caused by the adapted gradient tracking (GT) and instability introduced by the Pull-Diag protocol. To address descent deviation, we propose a novel analysis framework demonstrating that Pull-Diag-GT achieves linear speedup, the first such result for row-stochastic decentralized optimization. Moreover, by incorporating a multi-step gossip (MG) protocol, we resolve the instability issue and attain the lower bound, achieving near-optimal complexity for decentralized optimization over row-stochastic networks.