Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-stochastic Networks
Liyuan Liang, Xinyi Chen, Gan Luo, Kun Yuan · 2025
Read Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-stochastic Networks by Liyuan Liang, Xinyi Chen, Gan Luo, Kun Yuan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-04600.txt.
Introduction
Liyuan Liang, Xinyi Chen, Gan Luo, and Kun Yuan set the best rate for shared optimization on one way networks. Their paper, from twenty twenty-five, deals with decentralized learning. Nodes tune a shared model by swaps with peers, set by a mixing matrix. When that matrix is row stochastic, swaps pull in one direction only. Past work had solved the two way cases but left this one bare.
They built gauges for how such matrices bend the learn path and proved the first lower bound on speed. Known methods miss that bound for two named flaws: drift in the step direction and shake from the pull scheme. Their new frame aims at both. Readers get a bound and a path to hit it.
Catalog record
| CREATOR | Liyuan Liang, Xinyi Chen, Gan Luo, Kun Yuan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 95 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-04600
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-stochastic Networks Liyuan Liang, Xinyi Chen, Gan Luo, Kun Yuan Abstract 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. 1 Introduction Scaling machine learning tasks to large datasets and models requires efficient distributed computing across multiple nodes. This paper investigates decentralized stochastic optimization over a network of n nodes: \displaystyle\min_{x\in\mathbb{R}^{d}}\quad f(x)=\frac{1}{n}\sum_{i=1}^{n}\Big[f_{i}(x):=\mathbb{E}_{\xi_{i}\sim\mathcal{D}_{i}}[F(x;\xi_{i})]\Big] (1) where \xi_{i} is a random data vector supported on \Xi_{i}\subseteq\mathbb{R}^{q} with some distribution \mathcal{D}_{i} , and F:\mathbb{R}^{d}\times\mathbb{R}^{q}\rightarrow\mathbb{R} is a Borel-measurable function. Each loss function f_{i} is accessible only by node i and is assumed to be smooth and potentially nonconvex. Note that data heterogeneity typically exists, i.e., the local data distributions \{\mathcal{D}_{i}\}_{i=1}^{n} vary across nodes. In this paper, we model decentralized communication between nodes as a directed graph , a scenario frequently encountered in practical applications. For example, bidirectional communication may be infeasible due to differences in node power ranges ( Yang et al. 2019 ) or connection failures ( Yemini et al. 2022 ; Li et al. 2024 ) . In distributed deep learning, carefully designed directed topologies can achieve sparser and faster communication than their undirected counterparts, thereby reducing the training wall clock time ( Bottou et al. 2018 ; Assran et al. 2019 ; Yuan et al. 2021 ) . Network topology and mixing matrix. A central challenge in decentralized optimization is determining the optimal convergence rate and designing algorithms that achieve it. This requires a theoretical understanding of how network topologies influence decentralized algorithms. For any given connected network, its topology can be represented by a mixing matrix that reflects its connectivity pattern, serving as a critical tool for evaluating the network’s impact. In undirected networks, symmetric and doubly-stochastic matrices can be readily constructed. However, in directed networks, constructing a doubly-stochastic mixing matrix is generally infeasible. Instead, mixing matrices are typically either column-stochastic ( Nedić & Olshevsky 2014 ; Nedić et al. 2017 ) or row-stochastic ( Sayed 2014 ; Mai & Abed 2016 ) , but not both. Optimal complexity over doubly-stochastic networks is well-established. The connectivity of a doubly-stochastic mixing matrix can be effectively assessed using the spectral gap, a metric that quantifies how closely a decentralized network approximates a fully connected one. Leveraging this metric, several studies have established the optimal convergence rates for decentralized algorithms. For example, references ( Scaman et al. 2017 ; Scaman et al. 2018 ; Sun & Hong 2019 ; Kovalev et al. 2021 ) derive optimal convergence rates for convex or non-stochastic decentralized optimization. Lu & De Sa 2021 determine the optimal complexity for non-convex and stochastic decentralized optimization over a specific type of linear network, while Yuan et al. 2022 extend this complexity to a significantly broader class of networks. The optimal complexity for doubly-stochastic time-varying networks has been established in ( Huang & Yuan 2022 ; Li & Lin 2024 ; Kovalev et al. 2021 ) . Optimal complexity over column-stochastic networks is established recently. If out-degree information is available prior to communication, a column-stochastic matrix can be readily constructed. When decentralized algorithms rely solely on column-stochastic matrices, this is referred to as the Col-Only setting. The Push-Sum gossip protocol ( Kempe et al. 2003 ; Tsianos et al. 2012 ) forms the foundation of Col-Only algorithms. Many algorithms based on Push-Sum achieve superior convergence rates, e.g., Nedić & Olshevsky 2015 ; Tsianos et al. 2012 ; Zeng & Yin 2017 ; Xi & Khan 2017 ; Xi et al. 2017 ; Nedić et al. 2017 ; Assran et al. 2019 ; Qureshi et al. 2020 . However, these works fail to precisely capture the influence of column-stochastic networks and, as a result, do not clarify the optimal complexity in the Col-Only setting. This open question is addressed in a recent study by Liang et al. 2023 , which introduces effective metrics to evaluate the influence of column-stochastic networks, establishes the optimal lower bound for the Col-Only setting, and proposes algorithms that achieve this bound. Optimal complexity over row-stochastic networks remains unclear yet. If out-degree information is unavailable, column-stochastic matrices cannot be directly constructed. However, row-stochastic matrices can be formed using in-degree information, which can be easily obtained by counting received messages. This is referred to as the Row-Only setting. Similar to how Push-Sum serves as the basis for Col-Only algorithms, the foundation of Row-Only methods is the Pull-Diag gossip protocol ( Mai & Abed 2016 ) . Building on Pull-Diag , Mai & Abed 2016 adapted the distributed gradient descent (DGD) algorithm for the Row-Only setting, while Li et al. 2019 ; Xin et al. 2019c extended gradient tracking methods, and Ghaderyan et al. 2023 ; Lü et al. 2020 ; Xin et al. 2019a introduced momentum-based Row-Only gradient tracking. However, the convergence analysis for Row-Only algorithms is still quite limited. Current analyses focus only on deterministic and strongly convex loss functions, leaving the performance of Row-Only algorithms in non-convex and stochastic settings unknown. More importantly, the impact of row-stochastic networks on the convergence rate of Row-Only algorithms remains unclear. These gaps present significant obstacles to determining the optimal complexity in the Row-Only setting. Some fundamental open problems are: Q1. What are the effective metrics that can fully capture the impact of row-stochastic networks on decentralized stochastic optimization, and how do they influence the convergence of prevalent Row-Only algorithms? Q2. Given these metrics, what is the lower bound on the convergence rate for Row-Only algorithms in the non-convex and stochastic setting? Q3. Can existing Row-Only algorithms readily achieve the optimal convergence rate? If not, what limitations do they face? Q4. Can we develop new Row-Only algorithms that overcome the limitations of existing algorithms and attain the aforementioned lower bound? Main contributions. This paper improves the understanding of decentralized methods over row-stochastic networks by addressing these open questions. Our contributions are : C1. We find that the metrics generalized spectral gap and equilibrium skewness , proposed by ( Liang et al. 2023 ) to characterize the influence of column-stochastic networks, can also effectively capture the impact of row-stochastic networks on decentralized algorithms. C2. Using these metrics, we establish the first lower bound on the convergence rate for nonconvex decentralized stochastic first-order algorithms with a row-stochastic mixing matrix. This bound achieves linear speedup with respect to network size n and captures the influence of gradient noise, the mixing matrix, the number of