Achieving Optimal Complexity in Decentralized Learning over Row-Stochastic Networks

Authors: Liyuan Liang, Xinyi Chen, Gan Luo, Kun Yuan
Primary area: optimization
Keywords: decentralized stochastic optimization, directed graph, row-stochastic matrix, gradient tracking

Abstract:
A key challenge in decentralized optimization is determining the optimal convergence rate and designing algorithms that can achieve it. While this issue has been thoroughly addressed for doubly-stochastic and column-stochastic mixing matrices, the row-stochastic setting remains largely unexplored. This study establishes the first convergence lower bound for decentralized learning over row-stochastic networks. However, developing algorithms to achieve this lower bound is highly challenging due to several factors: (i) the widely used Row-Only gossip protocol,  Pull-Diag, suffers from significant instability in achieving average consensus; (ii)  Pull-Diag-based algorithms are sensitive to data heterogeneity; and (iii) there has been no analysis in nonconvex and stochastic settings to date. This work addresses these deficiencies by proposing and analyzing a new gossip protocol called Pull-Sum, along with its gradient tracking extension, Pull-Sum-GT. The Pull-Sum protocol mitigates the instability issues of Pull-Diag, while Pull-Sum-GT achieves the first linear speedup convergence rate without relying on data heterogeneity assumptions. Additionally, we introduce a multi-step strategy that enables Pull-Sum-GT to match the established lower bound up to logarithmic factors, demonstrating its near-optimal performance and the tightness of our established lower bound. Experiments validate our theoretical results.

Decision: reject

Reviews and discussion:

Metareview: