Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-stochastic Networks
Authors: Liyuan Liang
Xinyi Chen
Gan Luo
Kun Yuan
Venue: ICML 2025 spotlightposter (2025)
Keywords: decentralized optimization
stochastic optimization
non-convex
row stochastic network
Primary area: optimization->large_scale_parallel_and_distributed

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.

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-stochastic Networks
Liyuan Liang'
Xinyi Chen
Gan Luo
Kun Yuan"
2
Abstract
mization over network of nodes:
min ZERd
f(x)
[(x)) ==
(1)
A key challenge in decentralized optimization is determining the optimal convergence rate and de- signing algorithms to achieve it. While this prob- lem has been extensively addressed for doubly- stochastic and column- - mixing matri- ces, the row-stochastic scenario remains unex- plored. This paper bridges this gap by intro- ducing effective metries to capture the influence of row-stochastic mixing matrices and establish- ing the first convergence lower bound for decen- tralized 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 de- scent deviation, we propose a novel analysis framework demonstrating that PULL-DIAG-GT achieves linear speedup- the first such result for row-stochastic decentralized optimization. More- over, by incorporating multi-step gossip (MG) protocol, resolve the instability issue and at- tain the lower bound, achieving near-optimal com- plexity for decentralized optimization over row- stochastic networks.
where & is a random data vector supported on E, S R with some distribution D,, and F; Rd x IR9 - R is a Borel- measurable function. Each loss function fü is accessible only by node i and is assumed be smooth and potentially nonconvex. Note that data heterogeneity typically exists, i.e., the local data distributions {D:} 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 commu- nication may be infeasible due to differences in node power ranges (Yang al., 2019) 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 chal- lenge in decentralized optimization is determining the opti- mal convergence rate and designing algorithms that achieve it. This requires a theoretical understanding of how net- work topologies influence decentralized algorithms. For any given connected network, its topology can be represented by a mixing matrix that reflects its connectivity pattern, serv- ing as a critical tool for evaluating the network's impact. In undirected networks, symmetric and doublicstochastic 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-stochaste (Nedić & Olshevsky, 2014; Nedić et al., 2017) or row-stochastic (Sayed, 2014; Mai & Abed, 2), but not both.
1. Introduction
Scaling machine learning tasks to large datasets and mod- els requires efficient distributed computing across multiple nodes. This paper investigates decentralized stochastic opti-
'Scooo of Mathematics Science, Peking University, Beijing, China *Center for Machine Learning Research, Peking Uni- versity, Beijing, China. Correspondence to: Kun Yuan <kun- yuan laine@puu.du....
Optimal complexity over doubly-stochaste networks is well-established. The connectivity of doubly-stochasti 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 con- vergence rates for decentralized algorithms. For example,
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks
references (Scaman et al., 2017; 2018; Sun & Hong. 2019; Kovalev et al., 2021) derive optimal convergence rates for convex or non-stochastic decentralized optimization. Lu &
ONLY setting. Some fundamental open problems are:
QI. 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?
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-stochasee time-varying networks has been established in (Huang &
Q2. Given these metrics, what is the lower bound on the convergence rate for ROW-ONLY algorithms in the non-convex and stochastic setting?
Yuan, 2022; Li & Lin, 2024; Kovalev et al., 2021).
Optimal complexity over column-stochastie networks is established recently. If out-degree information is avail- able prior to communication, a column-stochasee stochastic matrix can be readily constructed. When decentralized algorithms rely solely on column-stochasti matrices, this is referred to as the COL-ONLY setting. The PUSH-SUM gossip pro- tocol (Kempe et al., 2003; Tsianos et al., 2012) forms the foundation of COL-OONLY algorithms. Many algorithms based on PUSHI-SUM achieve superior convergence rates, e.g., Nedić & Olshevsky (2015); Tsianos et al. (2012); Zeng & Yin (2017); Xi & Khan (2017); Xi al. (2017); Nedić et al. (2017); Assran al. (2019); Qureshi al. (2020). However, these works fail precisely capture the influence of volumn-stochastie networks and, result, do not clar- ify 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-stochasti, networks, establishes the op- timal lower bound for the COL-ONLY setting, and proposes algorithms that achieve this bound.
Q3. Can existing ROW-ONTY algorithms readily achieve the optimal convergence rate? If not, what limitations do they face?
Q4.
Can we develop new ROW-ONLY algorithms that over- come the limitations of existing algorithms and attain the aforementioned lower bound?
Main contributions. This paper improves the understand- ing of decentralized methods over row-stochastic networks by addressing these open questions. Our contributions are: :
CI. We find that the metrics generalized speciral gap and equilibrium skewness, proposed by (Liang et al., 2023) to characterize the influence of column-stochasee net- works, can also effectively capture the impact of row- stochastic networks on decentralized algorithms.
C2.
Using these metrics, we establish the firs/ 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 network size n and captures the influ- ence of gradient noise, the mixing matrix, the number of nodes and the smoothness of the loss function.
Optimal complexity over row-stochastic networks re- mains unclear yet. If out-degree information is unavail- able, column-stochastic matrices cannot be directly con- structed. However, row-stochastic matrices can be formed using in-degree information, which can be easily obtained by counting received messages. This referred to as the Row- setting. Similar to how PUSH-SUp serves as the basis for COL-ONLY algorithms, the foundation of Row- ONLY methods is the PUT.I--IAG gossip protocol (Mai & Abed, 2016). Building on PULL-DIAL -DAAG, Mai & Abed (2016) adapted the distributed gradient descent (DGD) algorithm for the Row-ONI 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-basee Row-ONLY gradient tracking. However, the convergence analysis for ROW-ONIA 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-
C3.
We find existing ROW-ONLY algorithms cannot attain the aforementioned lower bound due two challenges. First, the use of row-stochastic mixing matrices alone introduces a deviation in the descent direction from the globally averaged gradient, preventing existing analy- ses from achieving linear speedup convergence. Sec- ond, the PULI.-DIAG protocol introduces inversion of small values during operation, which introduces insta- bility in ROW-ONLY algorithms.
C4. We develop a novel analysis framework proving that PULL-DIAG-GT achieves linear speedup. marking the first such result in ROW-ONLY scenarios. Moreover, when integrated with a multistep gossip (MG) protocol, MGG-UULI-DIAG-GT addresses the instability caused by the inversion of small values and achieves the estab- lished lower bound. Therefore, both the lower bound and our algorithm achieve optimal complexity for de- centralized learning over oow-stochastic networks.
2

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks
Notations. Let 1, denote the vector of all-ones of n dimen- sions and n, E [R the identity matrix. We let matrix A denote the row-stochastic matrix (A1,, = L.). The set [n] represents the indices 21, m.. Diag(A) refers to the diagonal matrix composed of the diagonal entries of A. while diag(v) is the diagonal matrix derived from vec- tor v. The Perron vector of matrix is 7 i.e., TA 2 0, A AA n7 A 1. By letting IIĄ := diag(TA). we define || = ||n vll, which is associated with the
trace, then A is primitive. It is straightforward to make A row-stochastic by setting Gij 1/(11 d(") if (i, & or j = otherwise aij = 0, where & is the set of directed edges and di- is the in-degree of node excluding the self- loop. With Assumption 1, we have the following result:
Proposition (Perron-Frobente theorem (Perron, 1907)). If matrix A satisfies Assumption 1, there exists unique equilibrium vector TA E IR" with positive entries such that
induced matrix norm ||W]| = ||1/"/wn,'/1l>>> We define A = I, A- The vector a! (k) Rd represents the
.. TA==TA- TA 1, and lim A = 11 40000
local model at node i during iteration k. We also define n x d matrices
2.2. Effective Metries to Characterize Row-stochastic A
Most decentralized algorithms rely on gossip protocols like (2), where local variables are partially mixed to ap- proximate the global average. The properties of the mixing matrix A play a critical role in determining both the feasibil- ity of achieving the global average and the efficiency of this process. These properties serve as key metries for assessing the influence of A on algorithmic performance.
(1k)= = -[aee ((= (x22 ) ;... (1
(1)
VF (1)) = FV (a) (=a (x)))
5n ) (8) T.... F (1),
()(x()))= == V (x (k) TT:.... ;..
by stacking all local variables. The upright bold symbols (e.g- x, w. g) always denote network-level quantities. We detine filtration Fg as the collection of all the information available up to x(4 (4), excluding the stochastic gradient evalu- ated at (*) We use the symbol S to represent inequality up to absolute constants.
Now we examine the A-protocol (2) where A is a row- stochastic mixing matrix A. Suppose that each node has local variable z; E Rdd we let = [z] = = E Raxd and initialize x0) z. Following the gossip protocol as in (2), we have the following recursions:
2. Metrics for Row-stochastic Networks
(A) = Ax(x-1) x (0) k=000,
11 nn
(3)
We consider a directed network with n computing nodes that is associated with a mixing matrix A [a.]],)= Raxa where azj E (0, 1] if node j can send information to node otherwise aij = O. Decentralized optimization is built upon partial averaging "," = ΣJEN, azy², in which z; E Rd is local vector held by node i and Ai denotes the in-neighbors of node i, including node itself. Since every node conducts partial averaging simultaneously, we have
where we utilize the property limg- A In (see Proposition 1). It is evident that the matrix A influences both whether and how quickly x*)) approaches the global average 1 11, z/n. Inspired by (3), we use the following two metrics to characterize the row-stochastic matrix A:
The generalized spectral gap 1 - B3 of the row- stochastic matrix A, where
A-protncol zz Az
2
A = ||4 1, I = IAA Ao0l E 10
where A- protocol represents partial averaging with mixing matrix A. Evidently, the algebraic characteristics of A sub- stantially affect the convergence of partial averaging and the corresponding decentralized optimization. This section explores metrics that capture the characteristics of A.
quantifies the convergence rate of (()) to the weighted average 1,, / in (3). The 'A -nor was defined in the notations in Sec. 1. As BA approaches 0, the iterates (*) converge more rapidly to the fixed point 1, z of the A-protocol (3).
2.1. Row-stochastic Mixing Matrix
This paper focuses on static directed network G = (V,E) associated with row-stochastic matrix A [aij]exn-
The equilibrium skewness
Assumption 1 (Primitive and cow-stochastic). The mixing matrix A is nonnegative, primitive and satisfies AI,, = 11, The weight 0ij E (0, 1), if (i j)) E E, otherwise dij- O.
KA == max ( min( (TA) E [1, (oo)
captures the disagreement between the equilibrium vec- tor T and the uniform vector n 11,,, When KA - 1, it holds that nA + In/n, and hence, the weighted av- erage aligns better with the global average II, 1, z/n.
i.e., there exists a directed path from each node to every other node, and A has a positive
If 9 is strongly-
3

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks
The spectral gap gauges the rate of the A-protocol when converging the fixed point 1 12, while equilibrium skewness measures the proximity of the fixed point to the desired global average 1, z/1,, Together, these metrics effectively capture the influence of row-stochastic mixing matrices and directed networks on decentralized algorithms.
10a
10a
Ra Ro 55..3+
1k-0.77,,
10
Ra-0.9, Ka 603
R Ra 2.7 +05
10 2
0.-0,92,
10-2
8a 007
-.-0.35,,,
R 1.7. e10
10-5
10-5
10-
10
10-11
10-11
10 14
10-14
Omitting either would lead to an incomplete understanding of their impact. Figure shows examples that the spectral gap and equilibrium skewness jointly impact the conver- gence to average consensus. The protocol used in Figure is called PUL.I-- and will be discussed in Sec. 2.3.
200 300 Comm. Rounds
100
400
0
300 400 Comm. Rounds
100 200
Figure I. Convergence of PULL-DIAG protocol on different mix- ing matrices with varying spectral gaps (3x) and equilibrium skew- ness (KA). The y-axis represents the consensus error ||z(*) 1, 1,, z/nil- The left plot shows fixed KA with different BA, while the right plot shows fixed BA with different RAA.
is important to note that these two metrics are not new; they were proposed in (Xin et al., 2019;; Liang et al., 2023) to assess the influence of column-stochaste mixing matrices. Our contribution lies in demonstrating that these metries are also applicable to row-stochastic mixing matrices. Prior to our work, no literature had examined the metrics that can gauge the influence of row-stochastic mixing matrices on decentralized algorithms.
Function class. We define the function class FA,L as the set of functions that satisfy Assumption 2, for any given dimension d E N and any initialization point x( E Rd.
Assumption 2 (Smoothness). There exists constants
L, 2 0 such that
[v) Vf(lv)l S D| yll ViE, and for initial model parameter x0
2.3. Pull-Diag Protocol Corrects Weighted Average
According to (3), A-protocol alone cannot achieve the desired global average. The bias between the limiting weighted average z and the desired global average 1, n2 z/n can be corrected by the following manner:
f() inf
f((x) S SA Vi e [n].
wERd
Gradient oracle class. We assume that each node i pro- cesses its local cost function f, using stochastic gradient oracle V F(x; Et), which provides unbiased estimates of the exact gradient ff with bounded variance. Specifically, we define the stochastic gradient oracle class O, as the set of all oracles (F &,) that satisfy Assumption 3.
A diag(( 'z
10 IT diag(nv (T a) -,,1,,,,,111 1//.
(4)
Although the above strategy is effective, the quantity TA is not known beforehand. To estimate AA, prior works (Mai & Abed, 2016; Xin et al., 2019c; Ghaderyan et al., 2023) use power iterations, resulting in a practical and efficient approach referred to as PULL-DIAG in this paper:
Assumption 3 (Gradient oracles). There exists a constant N such that for all x E Rdd i [n]] we have
E [[) f.(w), t<(Var(VF((<<)) S o².
We also assume thut the gradient noise is linearly indepen- dent, i.e., Vi + E [m] we have
V = AVk, D4+1 = Diag(nVe+1), z (b+1)= Vi+1DT111.
(5a)
(5b)
Cor(VF(((R))) (E((E;(()) =0.
With initialization Vo In. we have V/2 A and DE = Diag(nAA). It holds that V2x + I and DA + diag(nTA) as A + oc. Substituting these facts into (5b), we asymptotically achieve the bias correction il- lustrated in (4). The distributed implementation details of the PULL-DIAG protocol can be found in Appendix B. It is shown in Figure that PULL-DIAG protocol corrects the weighted average and converges exponentially fast.
Algorithm class description. We focus on decentralized algorithms where each node maintains a local solution at iteration & and communicates using the A A-protocol defined in (2). These algorithms also adhere to the linear- spanning property, as defined in (Carmon et al., 2020; 2021; Yuan et al., 2022; Lu & De Sa, 2021). Informally, this prop- erty ensures that each local solution x! (k) resides within the linear space spanned by x; its local stochastic gradients, and interactions with neighboring nodes. Upon completion of K iterations, the final output (K) can be any variable in span (f {{ (=: (4) y 1 Let A denote the set of all algo- rithms that adhere to partial averaging via mixing matrix and satisfy the sinear-spanning property.
(k)
x;
3. Convergence Lower Bounds
3.1. Assumptions
This subsection specifies the category of decentralized algo- rithms to which our lower bound applies.
4

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks
3.2. Lower Bound
4.1. Pull-DIAG-GT Algorithm
With AA and KA at hand, we show, for the first time, that the convergence rate of any non-convex decentralized stochastic first-order algorithm with row-stochastic mixing matrix is lower-bounded by the following theorem.
We begin by reviewing the state-of-the-art ROW-ONLY al- gorithms (Li et al., 2019; Xin et al., 2019c; Ghaderyan et al., 2023; Lü et al., 2020; Xin et al., 2019a), all of which are based on PULI.-DAGG-GT tracking (Nedic et al., 2017; Di Lorenzo & Scutari, 2016;
adaptation of gradient
Xu et al., 2015; Qu & Li, 2017) designed specifically for ROW-ONLY scenarios.
Theorem (Lower bound). For any given L 2 0, n 2 2. 2 0, and B [0.01, 1/ni,, there exists set of loss functions {fi] E F..L.. set of stochastic gradient oracles in Oog, and row-stochastic matrix A E R with A^ = 3 and In(KA) = Mnn(1 - 3A)), such that the convergence of any algorithm a E AA (0) = (0), i E [n] with K iterations is starting from z; lower bounded by
x(++1) = A(x!!) ay(kk)
(7a)
ylk+1) = A(y(K) + D Diti (k+1) Di D'x'((1) (k))
(7b)
Here, DR = Diag(A*), Vk: 2 1, Do = In. Matrix x (( denotes the stacked model parameters and (()) denotes the gradient tracking term. g (k) denotes the stochastic gradi- ent, defined as (()) ; g(h)). with y g (0)) The details of algorithm implementation is provided in Ap- pendix B. As recursion (7) incorporates the PULL-DIAG protocol (5) into gradient tracking, it is termed PULL-DIAG- GT throughout this paper.
OVLA (1+
EI (() 12
VnK (1- (1-BA)K
(6)
where K, L,, and A represent the total number of iterations, the gradient variance, the smoothness param- eter of the functions, and the initial gap in the function values, respectively. The proof is in Appendix A.
It is noteworthy D may involve inversion of zeros. There- fore, the following assumption is necessary:
Assumption 4 (Bounded Diagonals). There exists a con- stant A 0 such that
Linear speedup. The first term, o/ 8/VnK, dominates the lower bound (6) when K is sufficiently large, indicating that decentralized algorithms with row-stochastic mixing matrices could achieve linear speedup with respect to net- work size n (i.e., convergence improves as the number of computing nodes n increases).
[A S 2 [n].
Remarkably, under Assumption I, the existence of O can be guaranteed if and only if every node has a self-loop.
Algorithm insight. As shown in A-protocol (3), communi- cation utilizing age = + πI z. In PULL- we can left-multiply A on both sides of (7a) and observe the following dynamics:
stochastic matrix yields biased aver-
Network topology impact. The lower bound in (6) ex- plicitly highlights the combined impact of the generalized spectral gap BA and the equilibrium skewness NA on decen- tralized algorithms utilizing tow-stochastic mixing matrices. Omitting either metric would provide an incomplete under- standing of the algorithmic performance.
π (x+11 = -T
an Ty (8)
(8)
If (k) represents the stacked stochastic gradients, i.e., y(()) ( the descent direction т T devi- ates from the desired globally averaged gradient 1 (8) /n, (8)
Deterministic scenario. When the gradient noise a = O, the established lower bound in (6) for stochastic settings simplifies to the first lower bound for deterministic decen- tralized algorithms with row-stochastic mixing matrices.
preventing π xx()) from converging to the solution to prob- lem (1). To ensure convergence, PULL-DIAG-OL corrects the descent direction using D in (7b). Left-multilling o on both sides of (7b) yields
11
4. Achieving Linear Speedup Using Row-stochastic Matrix Alone
T (T((++1) - T k+
D-1
n. TT a A 11 (k+1)
(0)
(a) 0,
The lower bound (6) reveals linear speedup convergence rate of a VnK as K grows large. However, no existing ROW-ONLY decentralized stochastic algorithm has theoreti- cally achieved this rate, highlighting a significant gap from the lower bound. This section identifies the challenges and presents a novel analysis framework that achieves the first theoretical linear speedup for Row-ONI algorithms.
where equality (a) holds due (0))) g (0), This implies
x. Ty (k) = T Di g
g
(8) و ng
(k)
(9)
where (b) holds because D2 = Dia ~ (TA) and (k) (1/n)1 The combined dynamics of (8)
5

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks
and (9) ensure that PULL-DIAG-GI converges along the globally averaged gradient, ultimately solving problem (1). a 2nI. for any k 2 0 we have
Lemma 2 (Descent lemma). Under Assumptions 1-4, when
Challenges in establishing linear speedup. Although the rationale behind PULL-DIAG-GT' convergence to the de- sired solution is clear, to the best of our knowledge, no existing analysis has established its linear speedup conver- gence with respect to the network size n. This subsection highlights the key challenges involved.
na
s( (K) )12 S (w - -B (w (1++)++)111)00 [Fad
2
+ aL?
1 2
1
a
E TT Ay (k) ng (k) |u,]l
consensus envor
descent deviation
a Lo²
2 dR 4n
1 (f(
(11)
We first define two emror terms to facilitate analysis:
where w(k) == x xx((() is the centroid variable, dk ==
Σド= [Tal]] )2 is a constant. A! == x(a) 11 Axx [Duls and g = (F (())
Consensus error: Let क. T (x) be the centroid variable for x()), We introduce [|x{(6] 11, xx as the consensus error to gauge the difference between each
local variable x to the centroid π. x
As anticipated, the descent lemma incorporates both the consensus error and the descent deviation. Due the con- ditional expectation operation, the descent deviation in the lemma appears as [|E[=]] the descent lemma for gradient tracking using doubly or column-stochastie mixing matrices ensures g(k) = gl))
Descent deviation. We define Ty ng 112 as the descent deviation, measuring the discrepancy between the PULL--DAGG-GT descent direction and the desired globally averaged stochastic gradient.
ng( Fie]l In contrast,
thereby accounting solely for the consensus crror.
If the aforementioned two error terms are guaranteed to diminish to zero, PULL-DIAG-GT enables each o; to converge to centroid (*) = 지 (*), and the update of (* asymptotically approximate centralized parallel SGD:
Estimate descent deviation. According to (9), we have T (k) 7 D (k) This implies that
| T Ay (R) ng" (8) Falll D( [xxxx((((
Therefore, we can use the following lemma to provide an estimate for the descent deviation.
w (k+1) = w (k)
nag (h)
(10)
(A) = where gw = (1/m) Eh= (F x.*)) is the globally averaged gradient over centroid. This ensures (k) to con- verge to the desired solution to problem (1).
Lemma 3. Under Assumptions 2 and for all k: 2 1,
-1', S 2nxx 22 ( 1 + (nL(((( - -S)).
(
Linear speedup analysis in distributed stochastic optimiza- tion relies heavily on the descent structure aligned with the globally averaged stochastic gradient (Yu et al., 2019; Xin et al., 2019b; Koloskova et al., 2020; Yang et al., 2021). When each local stochastic gradient 9: introduces mean- square gradient noise o², the globally averaged gradient ý benefits from reduced noise o² /n. forming the foundation for linear speedup. Gradient tracking with doubly or column- stochastic mixing matrices preserves the globally averaged gradient descent direction g. enabling well-established lin- car speedup convergence (Koloskova et al., 2020; Lu & De Sa, 2021; Assran et al., 2019; Kungurtsev et al., 2023; Liang et al., 2023). In contrast, PULL-DIAG-GU suffers from an additional descent deviation between TI and g. making existing linear speedup analyses inapplicable and necessitating new techniques to address this limitation.
where =n=
Lemma 3 employs (()(())) l establish upper bound the norm of the stacked gradients. In many instances, this approach can negatively impact the recursive nature of the descent lemma. Nevertheless, in this particular situation, we can effectively accommodate it due to its ((32k) coefficient. Details are provided in Lemma 13 in Appendix C.
Estimate consensus error. We present a novel method to establish bounds on the consensus error, which is based on converting A, into rolling sums.
Lemma (Informal). Denote Ag y(k)) 1n Ty(), (i)
A 1) = (0)) A g (+11) (1) Vi 2 O. For any k 2 0,
it follows that
4 (k+1) - Σ (A-A) (A-Aoo) )ot AA.
4.2. Achieving linear speedup in Pull-Diag-GT
This subsection presents a new analytical framework to establish the linear speedup rate for PULL-DIAG-GT.
i=0
A = Σ ((A - A ) k+1 + A90
(k+1) 9
Descent lemma. Our analysis begins with descent lemma.
6

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks
The following lemma tells how to estimate rolling sums: Lemma 5 (Rolling sum). For A E Raxx satisfying As- sumption 1, the following estimation holds for any matrices A
Removing OA with multiple gossips. The requirement for 0 (and Assumption 4) arises from the use of Diag( ( for gradient correction in the PULL-DIAG-GT update (7b), For small values of k, the diagonal elements of AAth can become extremely small due to network sparsity, leading to significant instability in the inversion Diag(A*) during the initial phase. As k increases, Diag( (A*) converges to diag(TA). which stabilizes the correction. This behavior formally stated in the following lemma:
E Ruxd and for any K 2 0:
K
K A
A00)
(A
(8) 13
S
Σ k=0
P
1=0
where S a constant decided by A.
Lemma 7. For A E RR*x satisfying Assumption 1, if k Σ
Under the L-smooth assumption, is straightforward de-
2 2lu(xa)+22n(n we have 1-Ba
rive an upper bound for the sum Σx= و 12. Following
the sequence of steps A - م + A,, Lemmas 4 and 5
[A > 0 and [AT]]] S 2NNiA Vi E [m].
together lead to the following consensus lemma.
Lemma 7 implies that for sufficiently large k the diagonals of A are naturally bounded without any extra assumptions. This motivates the use of the multiple gossip strategy to eliminate Assumption 4 and the dependence on 9 in Theo-
Lemma (Consensus lemma, informal). With Assump- tions 1, 2, 3 and 4, we have
K
K
E (K+
S Caya
E B ()(((()
rem 2. Instead of single gossip step z A-Protocol, Az, we perform R consecutive gossip steps z during each communication phase, where the gossip round R is determined as indicated in Lemma 7.
k=0
Multiple Gossip A
a ( f1((( Cn 1)0²,
where Cz.y, Cz, and Cz,o are constants.
Pull-DIAG-GT with multiple gossips. We now introduce NG-PULL-DIACE
Achieving linear speedup. Building on Lemmas 2, 3 and 6, we finally achieve the convergence Theorem 2.
to remove Assumption 4 and the the reliance on 0 Here, "MG" is short for multiple gossips.
Theorem 2 (PULL-DIAG-GT convergence). Under as-
x (++1)
A Ax(x!") - (1)
(12a)
sumptions 1, 2, 3 and 4, when total iteration K > 28.02, there exists a learning rate a (see Section C.8 1 1-5A
1 R
g (++1)
Σ FF ((
(12b)
R
in Appendix C) such that
(((+1) A (y Difi -
-Di -Digg())
(12c)
1 K
E V (K)
OVLA CA(1+CA) Vnk
Here Dj = Diag(A (A At 2 1, D. = In, (() (0)
K
K=
1/ E VF(x ((0.))) The implementation details are provided in Appendix B. It observed that for each iteration t, recursions (12a) and (12c) incur R rounds of communi- cation, and (12b) requires R samples to compute the mini- batch stochastic gradient. To ensure a fair comparison with for each K-iteration run of PULL-DIAG- GT, we run MG-PULI.-DIACE thereby fixing the total number of communication rounds and data samples at K.
where (h()) = - xx00, CA is positive constant de- cided by the mixing matrix A. Proof is in Appendix C.
Remark 1. Theorem 2 establishes the first linear speedup convergence utilizing solely row-stockee www-stcchsttcc mixing matrices. The term CALA signifies the influence of the network, where K+I
for T K/ / R iterations,
C' is rational function of K A, 3 and AA
5. Achieving Near-Optimal Convergence Rate
Achieving optimal convergence rate. Technically, by per- forming multiple gossip steps, we improve the spectral pa- rameter from 33 to 3 which exponentially reduces all terms associated with decentralized communication. Addi- tionally, by utilizing an R--mini-batch stochastic gradient, reduce the gradient variance from x² to o² R. However, reducing the outer iterations from K to K/ may polyno- mially slow the convergence. By carefully balancing this exponential gain against the polynomial cost with an ap- propriately chosen R, we can improve overall convergence, ultimately achieving optimal performance:
Comparing Theorem 2 with the lower bound in Theorem I, we identify two key discrepancies preventing PULL-DIAGE GT from achieving the lower bound. First, Theorem 2 relies on Assumption 4, which the lower bound does not require. Second, the constant CA in Theorem 2 depends on 0,, the upper bound of the diagonals, which is absent from the lower bound and can grow arbitrarily large even for fixed BA and to
KA. This section introduces a variant of PULL-DIAG address these discrepancies and achieve the lower bound.
7

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks
Exponential
Ring
Theorem 3. Suppose Assumptions 1,2 and 3 hold, and set T - K/R. When R = - (3(4+liia)) ++m(m))) and a being selected properly, we have
Gradient Norm
n=1
n=16
Gradient Norm
n=1
n=
10
n=2
n=128
10
n=5
n-16
1- BA
n=512
10-
10
T E PIIVS(W)) (11
10
10
10-
1500 3000 4500 6000
250 560 750 1000 0
LA (1+ (n(AA) + In(n))LA
Comm. Rounds
Comm. Rounds(1e2)
Vnk
Figure 2. Performance of PULL-DIAG-ON GT for non non-convex logistic regression evaluated across exponential graphs and ring graphs. Number n denotes the number of nodes.
where (x) == (K), The proof in Appendix D.
6.2. Neural Network for Multi-Class Classification
Remark It is observed that Theorem 3 is independent of Assumption 4 and A due to the multiple gossip strategy.
In the second group of experiment, we focus on a digit- classification task using the MNIST dataset. We evaluate the performance of MG-PULL-DIAG- PUL.I-DIAG-GT across four distinet network topologies: a ring graph, an undirected grid graph, geometric graph, and nearest neighbor graph, each comprising 16 nodes. These topologies are illustrated in Figure Al in Appendix E. The weights of the mixing matrices are determined using the Metropolis rule (Nedić et al., 2018), which produces row-stochastic but not doubly-stochastic matrices.
against the vanilla
Remark 3. When In(n) is negligible compared to In(KA),, Theorem 3 aligns with our lower bound (Theorem 1), making both the lower bound and the algorithm optimal. Otherwise, say that PULL-DIAG-
achieves near-optimal complexity (rather than optimal complexity) due to the exis-
tence of the logarithmic gap In(n).
6. Experiments
In this section, we empirically validate the theoretical results presented in Theorems 2 and 3. For the stochastic gradient oracle, we focus on the case where each node has access to a finite dataset, and the stochastic gradient is computed with respect to randomly chosen data sample at each iteration. To assess the performance of the algorithms, we conduct experiments on a synthetic dataset, MNIST dataset and CIFAR-10 dataset. Implementation details are provided in Appendix E for reference.
Ring
Grid
MG=1 (Vanilla)
MG=1 (Vanilla)
MG=5
MG=5
Loss
10a
MG=10
Loss
10
MG=10
0 200 400 600 800 Comm. Rounds
0
80
160
240
Comm. Rounds
Geometric
Nearest Neighbor
6.1. Non-convex Logistic Regression for Classification
MG=1 (Vanilla)
MG=1 (Vanilla)
MG=5
MG=5
In this first group of experiment, we minimize a synthetic nonconvex loss function (Antoniadis et al., 2011; Xin et al.,
Loss
100
MG=10
Loss
10
MG=10
2021; Alghunaim & Yuan, 2022; Liang al., 2023) that satisfies the L-smooth property. Our experiments are con- ducted on directed exponential graphs (Xin et al., 2021; Ying et al., 2021) and directed ring graphs (see Figure A1 in Appendix 1). For exponential graphs, we evaluate the performance across network sizes of (single node), 2, 8, 16, 128 and 512. For ring graphs, we evaluate the per- formance across network sizes of 1 (single node), 5, 10, 16.
80 160 240
80 160 240 Comm. Rounds
Comm. Rounds
Figure 3. Averaged training loss of neural networks on MNIST dataset. Networks trained using PULL-DIAG-GT and vanilla PULL-DIAG-GI Here, "MG" denotes the number of gossip steps.
The results in Figure 2 reveal that, for each fixed topology, the gradient curve decreases proportionally to the square root of the number of nodes after the same number of com- munication rounds. This numerically validates our Theo- rem 2 that PULL.-DAAG-Gi able achieve linear speedup.
Figure 3 demonstrates that MG-PULL-DIAG-GR achieves a consistently faster convergence rate in training loss across all tested topologies, while the corresponding test accuracy is detailed in Figure A2 in Appendix E.
8

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks
6.3. Neural Network for Image Classification
Acknowledgment
In the third set of experiments, we conducted training of the ResNet-18 18 model (He et al., 2016) on the CIFAR-I0 10 dataset using a distributed approach. Consistent with our previous MNIST dataset experiment, we evaluated and compared the performance of MG-PULL-DIAG-GT against the stan- dard FUUL--DAGGGO over different topologies. Figure 4
The work is supported by the National Natural Science Foundation of China under Grants 92370121, 12301392, and W2441021.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Ring
Grid
MG=1 (Vanilla)
MG=1 (Vanilla)
MG=4
10
MG=5
Loss
10
MG=8
Loss
MG=10
References
M
10
Alghunaim, S. A. and Yuan, K. A unified and refined con- vergence analysis for non-convex decentralized learning. IEEE Transactions Signal Processing, 70:3264-3279, 2022.
60 120 180 240
60
120
180 240
Comm Rounds
Comm. Rounds
Geometric
Nearest Neighbor
MG=1 (Vanilla)
MG=1 (Vanilla) MG=5
10
MG=5
10
Antoniadis, A., Gijbels, I., and Nikolova, M. Penalized likelihood regression for generalized linear models with non-quadratic penalties. Annals of the Institute of Statis- tical Mathematics 63:585-615, 2011.
Loss
MG=10
Loss
MG=10
10
10-1
Arjevani, Y., Carmon, Y., Duchi, J. C., Foster, D. J., Srebro, N., and Woodworth, B. E. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199:165-214, 2019. URL https:
30 60
90
120
0
150 200 Comm. Rounds
50
100
Comm. Rounds
Figure 4. Averaged training loss of neural networks on CIFAR-10 dataset. Networks trained using FULL-DIAG-GT and vanilla PULL--DIGGGT. Here, "MG" denotes the number of gossip steps.
/ //app.ssmmaticsccooo..ooooo http://attt.cccco....ooooooaapaa orq/CorpusID: 208637439.
illustrates the stability of MG-PULL-DDAN plied to a larger real-world dataset. the context of sparse topologies like the ring and grid graphs, MG-PULL-DIAG- GT effectively reduces the influence of sparse structures, resulting in superior performance compared to the vanilla PULL-DIAG-GrT The corresponding test accuracy is de- tailed in Figure A3 in Appendix E.
when ap-
Assran, M., Loizou, N., Ballas, N., and Rabbat, M. Stochas- tic gradient push for distributed deep learning. In Inter- national Conference Machine Learning, pp. 353-353. PMLR, 2019.
Bottou, L., Curtis, F. E., and Nocedal, Optimization methods for large-scale machine learning. SIAM review, 60(2):223-31) 2018.
7. Conclusions and Limitations
Carmon, Y., Duchi, C., Hinder, O., and Sidford, A. Lower bounds for finding stationary points i. Mathematical Programming, 184(1-2):71-120 2020.
In this paper, investigate nonconvex, stochastic decen- tralized optimization over row-stochastic networks. We establish the first lower bound on the convergence rate for this setting. Additionally, we present the first linear speedup convergence rate achieved by PULL-DIAG-GT. To further improve performance, we introduce the multiple gossip tech- nique, leading to the development of MG-PULL-DIA This algorithm matches our lower bound up to logarith- mic gap. rendering both the lower bound and the algorithm nearly optimal. Numerical experiments validate our the- oretical findings and demonstrate the effectiveness of our approach. A main limitation of our work is that the network impact on BOLL-DIAG-GT such as the explicit influence of A, remains unclear, leaving it for future research.
Carmon, Y., Duchi, J. C., Hinder, O., and Sidford, A. Lower bounds for finding stationary points ii: first-order meth- ods. Mathematical Programming. 185(1-2):315-355 2021.
Di Lorenzo, P. and Scutari, G. Next: In-network nonconvex optimization. IEEE Transactions on Signal and Informa- tion Processing over Networks, 2(2): 2016.
Ghaderyan, D., Aybat, N. S., Aguiar, A. P., and Pereira, F. L. A fast row-stochastic decentralized method for distributed optimization over directed graphs. IEEE Transactions on Automatic Control, 69(1):275-29) 289, 2023.

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learn- ing for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Lu, Y. and De Sa, C. OOpiimll complexity in decentral- ized training. In International Conference Machine Learning, pp. 7111-7123, PMLR, 2021.
Mai, V. S. and Abed, F. H. Distributed optimization over weighted directed graphs using row stochastic matrix. 2016 American Control Conference (ACC), pp. 7165- 7170. IEEE, 2016.
Huang, X. and Yuan, K. Optimal complexity in non-convex decentralized learning over time-varying networks. arXiv preprint arXiv:22/ /. .00533, 2022.
Huang, X., Chen, Y., Yin, W., and Yuan, K. Lower bounds and nearly optimal algorithms in distributed learning with communication compression. Advances in Neural Infor- mation Processing Systems, 15:18955-18999 2022.
Nedić, A. and Olshevsky, A. Distributed optimization over time-varying directed graphs. IEEE Transactions on Au- tomatic Control, 60(3):601-615 2014.
Nedić, A., Olshevsky, A., and Shi, W. Achieving geomet-
Kempe, D.,
Dobra, A., and Gehrke, J. Gossip-based com- putation of aggregate information. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003.
ric convergence for distributed optimization over time- varying graphs. SIAM Journal on Optimization, 27(4): 2597-2633, 2017. doi: 10. 00.1137/661004316
Proceedings., pp. 482-491. IEEE, 2003.
Nedic, A., Olshevsky, A., and Shi, W. Achieving geomet- ric convergence for distributed optimization over time- varying graphs. SIAM Journal on Optimization, 27(4): 2597-2633, 2017.
Koloskova, A., Loizou, N., Boreiri, S., Jaggi, M., and Stich, S. A unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning, pp. 5381-5392 PMLR, 2020.
Nedić, A., Olshevsky, A., and Rabbat, M. G. Network topology and communication-comppaaaii tradeoffs in decentralized optimization. Proceedings of the IEEE, 106 (5):953-9766 2018.
Kovalev, D., Gasanov, E., Gasnikov, A., and Richtarik, P. Lower bounds and optimal algorithms for smooth and strongly convex decentralized optimization over time- varying networks. Advances Neural Information Pro- cessing Systems (NeurIPS), 34, 2021.
Nedić, A. and Olshevsky, A. Distributed optimization over time-varying directed graphs. IEEE Transactions on Au- lomatic Control, 60()):001615, 2015. doi: 10.1109/ TAC.2014.266009..
Kungurtsev, V., Morafah, M., Javidi, T., and Scutari, G. Decentralized asynchronous non-convex stochastic op- timization on directed graphs. IEEE Transactions Control of Network Systems, 2023.
Perron, O. Zur theorie der matrices. Mathematis- che Annalen, 64(2):248 263, 1907. doi: 10.1007/ BF01449896. URL ht https: wow....og/...10..77777 BF01449896.
Li, H. and Lin, Z. Accelerated gradient tracking over time- varying graphs for decentralized optimization. Journal of Machine Learning Research, 15227)):155,,200
Qu, G. and Li, N. Harnessing smoothness to accelerate distributed optimization. IEEE Transactions on Control of Network Systems, 5(3):1245-1260) 2017.
Li, H., Wang, J., and Wang, Z. Row-stochastic matrices based distributed optimization algorithm with uncoordi- nated step-sizes. In 2019 6th International Conference on Information, Cybernetics, and Compustaioonal Social Systems (ICCSS), pp. 131. IEEE, 2019.
Qureshi, M. I., Xin, R., Kar, S., and Khan, U. A. S-addopt: Decentralized stochastic first-order optimization over di- rected graphs. IEEE Control Systems Letters, 5(3):953- 958, 2020.
Li, W., Lv, T., Ni, W., Zhao, J., Hossain, E., and Poor, H. V. Decentralized federated learning over imperfect communication channels. IEEE Transactions Commu- nications. 2024.
Sayed, A. H. Adaptive networks. Proceedings of the IEEE, 102(4):460-44) 2014.
Scaman, K., Bach, F., Bubeck, S., Lee, Y. T., and Massoulié, Optimal algorithms for smooth and strongly convex distributed optimization in networks. In international conference machine learning, pp. 3027-3036. PMLR, 2017.
Liang, L., Huang, X., Xin, R., and Yuan, K. Towards better understanding the influence of directed networks on decentralized stochastic optimization. arXiv preprint arXiv:2312.04998, 2023.
Lü, Q., Liao, x., Li, H., and Huang, T. A nesterov-like gra- dient tracking algorithm for distributed optimization over directed networks. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 51(10))6258-622 2020.
Scaman, K., Bach, F., Bubeck, S., Massoulié, L., and Lee, Y. T. Optimal algorithms for non-smooth distributed opti- mization in networks. In Advances in Neural Information Processing Systems (NeurIPS), pp. 2740 2749, 2018.
10

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks
Sun, H. and Hong, M. Distributed non-convex first-order op- timization and information processing: Lower complexity bounds and rate optimal algorithms. IEEE Transactions on Signal processing, 67(22):5912-5922 5928, 2019.
Ying, B., Yuan, K., Chen, Y., Hu, H., Pan, P., and Yin, W. Exponential graph is provably efficient for decentralized deep training. Advances in Neural Information Process- ing Systems, 14:11975-13987, 2021.
Tsianos, K. I., Lawlor, S., and Rabbat, M. Push-sum distributed dual averaging for convex optimization. In 2012 ieee 51st ieee conference decision and control IEEE, 2012.
Yu, H., Jin, R., and Yang. S. On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization. In International Conference on Machine Learning, pp.
(cdc), pp.
PMLR, 2019.
Xi, C. and Khan, U. A. Dextra: A fast algorithm for op- timization over directed graphs. IEEE Transactions on Automatic Control, 62(10)):980-4999 4990, 2017.
Yuan, K., Chen, Y., Huang, X., Zhang, Y., Pan, P., Xu, Y., and Yin, W. Decentlam: Decentralized momentum sgd for large-batch deep training. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 3029-3039, 2021.
Xi, C., Xin, R., and Khan, U. A. Add-opt: Accelerated distributed directed optimization. IEEE Transactions on Automatic Control, 63(5): (3(5)::329-1339 2017.
Yuan, K., Huang, X., Chen, Y., Zhang, X., Zhang, Y., and Pan, P. Revisiting optimal convergence rate for smooth and non-convex stochastic decentralized optimization. Advances in Neural Information Processing Systems, 35:
Xin, R., Jakovetić, D., and Khan, U. A. Distributed nesterov gradient methods over arbitrary graphs. IEEE Signal Processing Letters, 2678):1247-125,, 2019a.
36382-36395 2022.
Xin, R., Sahu, A. K., Khan, U. A., and Kar, S. Dis- tributed stochastic optimization with gradient tracking over strongly-connecten networks. In 2019 IEEE 58th Conference on Decision and Control (CDC), pp. 8353- 8358. IEEE, 2019b.
Zeng, J. and Yin, W. Extrapush for convex smooth decen- tralized optimization over directed networks. Journal of Computational Mathematics, pp. 383-396, 2017.
Xin, R., xi, C., and Khan, U. fast row-stochastic op- timization with uncoordinated step-sizes. EURASIP Jour- nal on Advances in Signal Prucessing, 2019, 01 2019c. doi: 10. 10.1186610 0..1186/113334-111 0596-y.
Xin, R., Khan, U., and Kar, S. An improved convergence analysis for decentralized online stochastic non-convex optimization. IEEE Transactions on Signal Process- ing. 69:1842-1855 1858, 01 2021. doi: 10.1109/TSP.2021. 3062553.
Xu, J., Zhu, S., Soh, Y. C., and Xie, L. Augmented dis- tributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes. IEEE Con- ference on Decision and Control (CDC), pp. 2055-2060, Osaka, Japan, 2015.
Yang. H., Fang, M., and Liu, J. Achieving lincar speedup with partial worker participation in non-iid federated learning. Proceedings of ICLR, 2021.
Yang, T., Yi, X., Wu, J., Yuan, Y., Wu, D., Meng, Z., Hong, Y., Wang, H., Lin, Z., and Johansson, K. H. A survey of distributed optimization. Annual Reviews in Control, 47: 278 305, 2019.
Yemini, M., Saha, R., Ozfatura, E., Gündüzz D., and Gold- smith, A. J. Robust federated learning with connectivity failures: A semm-deccetrallzee framework with collabora- tive relaying. arXiv preprint arXiv:2202.1 /850, 2022.

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks
Content of Appendix
Appendix A. Lower Bound
13
Matrix Example
13
Proof of Theorem
13
Appendix B. Algorithm Implementation Details
14
Appendix C. Convergence of PULL-DIAG-GT
15
Notations
15
Linear Algebra Inequalities
16
Proof of Lemma 2
18
Estimate Descent Deviation
19
Absorb extra [ww) - l
19
Proof of Lemma
20
Proof of Lemma
20
Proof of Theorem 2
20
Appendix D. Convergence of MG-PULL-DIAG-GT
24
Appendix E. Experiment Details
25
12

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks
A. Lower Bound
A.1. A Matrix Example
//2 but Proposition 8. For any 2 2, there exists row-stochastic, primitive matrix A E 1 satisfying BA 2
RA
Proof. Proposition 2.5 of Liang et al. (2023) tells us that for any 2 2, there exists a column-stochaste primitive matrix
W R=x= satisfying 3w v2 but aw 2n-1, Taking A B", their Perron vectors are the same, i.e. TA aw.
Therefore, NA Kw. By the definition of the π-norm, know that BA ||A - Aco A =111 (A Aoo I 1/2 122 [K 1/2 (W - >x M ) Tlla || Bw.
A.2. Proof of Theorem 1
The core idea of the proof is derived from (Liang et al., 2023). The first complexity term, 9 (V proof can be found in works such as Lu & De Sa (2021) and Yuan et al. (2022). Therefore, concentrate proving the second term, (((1 + In(ka))LA/KS K).
vnk ) is standard, and its
To proceed, let [xly represent the j-th coordinate of a vector x E IRd for 1 S S d, and define:
0
if x = 0; otherwise.
prog(#))
maxigssa : [xlly + 0}
We also introduce several important lemmas, which have been established in previous research.
Lemma (Lemma of Arjevani et al. (2019)). Consider the function
M(x) == - (1))((()))) + ΣØ= ( (((-(=))))((<lllpp) - ((()))))(()))))))) (
where for any R,
2 2 1/2;
and 6(z) = ve 5 E t dt.
(22)
exp (1 (22-1)2)
1/2,
The function h(z) has the following properties:
1. h zero-chain, ie., prog (v(()) S prog(r) + for all a e Rdd
2. h(x) - inff M(x)= S ood, for all x E IRd with Ao = 12.
3. h is La-smooth with Lo 152.
4. [/V S Goo. for all Rd with Gos 23.
5. [[V(())l 2 1 for any x E Rdd with [x)a = 0.
Lemma 10 (Lemma 4 of (Huang et al., 2022)). Letting functions
hi(x) -2b((1) + E, even, ocjeed (asced(y((--o (v(((a1)))0(((aa)))) (<(x=)))<)([)))
and
hz(x) == 2= 2i add o<jed
then hı and h2 satisfy the following properties:
1. (hn h2) h, where h is defined in Lemma 9.
2. h and h2 are zero-chain, i.e., prog (z) S prog(z) + for all x E Rd and i == 1,2. Furthermore, if prog(I) odd, then prog(Vhu S prog(r); if prog(x) is even, then prog( (Vgg())))) S prog(r).
13

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks
3. 11 and liz are also Ly-smooth with Lg 152.
We are now ready to prove our lower bound. This proceeds in three steps. Without loss of generality, we assume n can be divided by 3.
(Step 1.) We let ft LX2hi (a/A(// Vi Ei A { j S n/33 and fo LX Lx//////A/LLo vi Bg - {i
2n/3 - S n), where hı and h2 defined in Lemma 10, and À 0 will be specified later. By the definitions of hı and h2, have that fi. A1 S < n, is zero-chain and f(x) n ΣE= fi( 2LA9h(r/A)/3Lo Since hı and h2 also Ta-smooth, [= are T-smooth, Furthermore, since
s(0) infa ((x)
2LA² (h(0) inf, h(x))
~ LAPAnd
3Ln
to ensure (f) satisfy L-smooth Assumption, it suffices to let
And 1oo
A.
i.e. X -
Lod T.Add'
(13)
With the functions defined above, we have ((x) n (r) is even and E E1 or prog(z) odd and E Eg. otherwise P f((x)) I prog(x). Therefore, to make progress (i.e., to increase (r))( for any gossip algorithm A E Aww one must take the gossip communication protocol to transmit information between Ej and E2 alternatively.
1 Σ 1 fi(x) - (1)(33)))((3)) and prog(V/f(r)) - prog(z)+1
(Step 2.) We consider the noiseless gradient oracles and the constructed mixing matrix W in Subsection 8 with 2,3 1+In(Ka) (n)) Note the directed distance from E, to Eg is n/3. Consequently, starting from x:() = 0, it takes so that 1-34 of at least n/3 communications for any possible algorithm E AA to increase prog($) by is odd. Therefore, we have [prog(((4)) //2 5
V k 2
0. This further implies
2m/3
(kk) S
3k/n+
4k O.
(14)
2n/3
(Step 3.) We finally show the error B[|| fx) is lower bounded by Q
(1+In(()))LA (1-BA)K
with any algorithm A E Aw
1/2
with K communication rounds. For any 2 n, we d 2
K
2 S 3K/ / < 5K and
|n (3L
Then (13) naturally holds. Since (rog( < by (14), using the last point of Lemma 9 and the value of X, we obtain [ 2 mingg]== //
x² DL
Finally, by using n 9(( (n(a)))/ -BA),, we complete the proof of Theorem 1.
B. Algorithm Implementation Details
We provide complete expression and pseudo code for PULL-DIAG protocol, PULL-DIAG-GT and MG-PULL-DIAG-GT here
For PULL.-DIAG protocol, the iteration is:
Vk-1 = AVk, D Diag(nVa+1).
2 (k+1) n -V D-1 2412
where Vo= In.
For PULL-DIAG-GU the iteration is:
x (k+11 = A(x(()) (1)
(16a)
D >ADx
(16b)
D₁ = Diag( (Dx)
(16c)
((++)) (() D Dxtig
(k+1) (r)g())
(16d)
14

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks
Algorithm 1 PULL-DIAG protocol
Require: Initialize v (0) ei Z..
for 1 0,,1.... K each node i in parallel do
Update of (((tt)) = EjENa" , (k), end for
Update 2/ = 2:/nu ;
for 0, 1........ K 1, each node parallel do Update [k+1)= = Ejevi" 0ij2] (R),
end for
Algorithm 2 PULL-DIAG-GT
Require: Initialize 8. (0,0)
Ci w(0) = =x(0), g.
y, (0)
(x(x(0); : the mixing matrix A |aiylaxn-
for k = 0, , K 1, each node i in parallel do
Let ((+++) Z:
(k) 7y! (k);
Update 2 (k+1) EEENT" aig (++1) and (1+1)) Ejext! ! (K)
Compute gi
(k+1) (a (k+1),
:::
Let ///
(k+1)
yj + [0 11=
g: (1+1) (1) 1-
(k+1) Σ EjE,, asz a)g (1t2))
Update yi
end for
where Dg In-
For MG-PULL-DIAG-GTT its iteration runs as:
((+1) = =A (xx()__a'')) ayy
(17a)
Di41 D
(17b)
D. = =Diag(D) D.)
(17c)
R
g
((++1) FF(((t+)) g(1+l.r)) (((ttt)))
(17d)
R
r=1
y((-1) = (y + D (t+1) Dr
(17e)
where Do In-
C. Convergence of PULL-DIAG-GT
C.I. Notation
Most of notations in the proof are the same with notations defined in Section 1. We repeat them follows:
We denote 1 as an n-dimensional all-ones vector. We define I, E IR=x as the identity matrix. Throughout the paper, is always row-stochastic matrix, ie., All, = 1,, We denote [r]] as the index set (1, ..). We denote Diag( A) as the the diagonal matrix generated from the diagonal entries of A. We denote diag(v) as the diagonal matrix whose diagonal entries comes from vector v. We denote n as the left Perron vector of A. We denote II diag(*=)) TT norm || \ ell and the induced π -atrixx norm as || FA
1/2 We define A 1 I, E E2 denote the local model copy at 3A = ||A - A KA = max(#A)) // min(m Throughout the paper, we let x (k) node iteration Furthermore, we define the matrices
15

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks
Algorithm 3 MG-PULL-DIAG-GIT) PULL-DIAG-GT with multi-round gossip
Require: Initialize v; 0:000 ei, w(0)) x gi (0) the multi-round number R.
(0)
((0r1). the mixing matrix A [aiglnxn
for 0, o,.,.................. (K/R) L, each node in parallel do Let (6(+1.0) = 0 yy: (
for 0..,..., R 1, each node in parallel do
Update Φ; ((t11,++) Ejenp" aij 03 (++1.) and o. (f(r+t)) = =Ejenç" assu, (tr)) end for
Update (++1) (1+1,R) (t-1,0)
0i (
8;
vi
Compute 9: (1+1] ΣR (bmma (bbma ((+1), ((+1.)));
Ss
Let /// (1-1.0) Vi
(1) [0 (+t10 9
(++1)
[ (0 9;
(0
for = 0,
R - 1, each node in parallel do
Update ub!
(1+1,++1) jE ai a ((-1))
end for
Update y,
((+1)
1/ (1+1.00
end for
(k) = [(m)) (K) ; (222 T j... ( Raad
VF(x ((()) = |VF ( );; VF, ) E Raxd
Vf.- (- (1)) (2. :.... (x e Rexd
by stacking all local variables. The upright bold symbols (e.g. w.g E Rxxd) always denote stacked network-level quantities.
Besides, we define [(((()) n - (((((()) A (1 1x))xx A g -g(1)) vk 2 0. -.- =0)"),
C.2. Linear Algebra Inequalities
We outline useful inequalities which will be frequently used in the proof.
Lemma 11 (ROLLING SUM LEMMA). Ifl and Rxxn row-stochastic matrix satisfying Assumption 1, the following estimation holds for VT 2 O.
T
Σ
-
S 2 Σ 1 1p.
(18)
k=0
where 10 E Raad are arbitrary matrices, and is defined by:
1 1+1 1 In(xx)
SA = max A Abol22- #21
1 1-3. BA
Proof. First, prove that
| A I VRABA, vi
(19)
Notice that 3A : [|A Abc FA and
AbollEA =8A- || AbelIZA = [1(A Aoc)' S S1A
we have
||AA Az)) = 1|11 Aoc)oolaa S VTaBllllllz S &VRAAAlol)
The last inequality comes from
|||||Ta S TT/l Therefore, (19) holds.
16

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks Second, want prove that for all 0, we have
Σ || Abal22 S..-
(20)
Towards this end, we define MA. == max ||.4 Acoll2. According to (19). MA is well-defined. We also define
In( Iu( 0 then we can verify that |A4' - Acol2 & MA MAPA of " vi 2 1. With this inequality,
max
In(3a)
we can bound Σ i== |Ak+l-i Aoe 1/2 as follows:
min [p].k]
A
Aoa
|| - Anal12
Σ
| |Aollo
immin [m]n([p].)] k]
min [p].k)
k+1
MA +
Σ
MASATP
v=min [ (14
1
<MA (1 + min kb)
MA
3
(21)
3,
If pp- = 0, (21) is simplified to Σxzo || Ao S MA 1-8A
and (20) is naturally satisfied. If p > 0, let
min( k) + p E [0, 1), (20) is simplified to
B p+ 1- 3
A Abol22 S Ma(
) Ma(P+ 1- BA
Noting that S 1 In(aa)
1-BA we finish the proof of (20).
Finally, to obtain (18), we use Jensen's inequality. For positive numbers a,, i E []: + +]] satisfying k-+1 aj = 1, we have
[Ak+1-i_ A0)
(1))
ak+1-;
2=0
ab+1-1 01 1 (a)))
(1) 11 < Σ a (
A
(22)
By choosing a++1-; (E/ || 1 Ab -
1|
Abol12 112 in (22), we obtain that
k Σ
Σ
| Aoe Abell2 Σ
| |
-
(23)
1=0
1=0
By summing up (23) from & = 0 to T, we obtain that
T
T k
A
Ax)
S SA
Σ>>>>
|A 1
Aoc |2
km0
Am i=0
T
141-- A
<
Σ 1
0=0
k=
1=0
which finishes the proof of this lemma.
Lemma 12 (CONVERGENCE OF DIAGONAL MATRIX). The following inequalities hold for all k > 1.
1. || D TTl S SAATTKA
17

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks
2. ||0 - - 122 s SAV w g
3. ||DE" 1 2 20 V ni 3
Proof. Denote II = d and A malk
The first conclusion comes from
A
1 S | I - diag(A*))l S 0al1 diag(A*)]l
I BAll Axclle S vndallA* Abolle S PAVTRASH
The second conclusion can be derived from the first conclusion:
| A 1l2 S D Inll2 = _ max 17 S nn n - s
- /ev n
Finally, note that | 1 D 1++1la lla
1 11alll + 11 k+1 11a11la 112, we obtain the third conclusion.
C.3. Proof of Lemma 2
Left-multiply T. on both sides of (7a), we have (k+1) w(()) - -aTTy Using Assumption 2, we know that
a²1
((1 S ()) - n ta (' +
2 A 181
(24)
By taking expectations on F(2) both sides of (24), we have
a²I
([ S (()) n aaa ( ()
[F5]]
+
Bl|l
A A (k) 10
2
a²
L
f(w)(()) -a (nVf(((())) 'x
+
||
D
DE
2
+ a²L Var [ar[TT] D [vf(((1))
(a)
$ (() - n tt nV n f (k))
' v((((())
L²L
n D vf(x |12 a²Lo²
[TAL] )²
+ 2
| Di
2
=
- a a--
na L a--aa²
) ,
||3]
na
V (k) 1|2
k
2n
2
Lo
+ 2n
|n f(u - TT -
- V |1)
dr
(k)
4n | TT (V
1))
V |V (1)
a²Lo"
a - I + + + ()) - n - 11 (f
n TT. (f
2 dx
where (a)
holds because the gradient noise is linearly independent,
Var DT V (x((+))
Var Σn j=1
[FAli FF [ [aae Var (F)()))))) x
[KAle]) )2 = oddr. de is defind 0² Σラ= ( (allss
(
Dales
as dy
Σド=
[sals )2
Da
Note that (V)(((()) -n - - -
S 1 I [+){{a - V)((2(()) S
n- 1 1,2 12 || (1))
( 1
n -1, 1 we thus obtain Lemma 2.
18

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks
C.4. Estimate Descent Deviation
Using the first statement of Lemma 12, we know that
T ( Ii S PAAREASO 4 1.
Next, with Assumption 2 we know that Va, y E RR, i [m]]
( + (Vii(z), x) + - 11 =t1².
2
By taking y = x - fz)) we obtain that 1 [V & f((x) - f((1) S f((Ø) - fi Furthermore, using L-smoothness property and
27 inequality, we have
[v S 2ll
vf(w(()) )12- + f22ll/
- 2
17 2
(t)
S A2 11 113 4L Σ (fi(w(()) fi)
(8) 24 x
13 + (f - f*),
By combining the two parts, we complete the proof of Lemma 3.
C.5. Absorb extra [(w) - lr Lemma 13. For any A Sk TR. , (0,1), if
S& S (1 + ca.*))a
Doti + Fai
Ak 2 1,
1-8 then, by selecting a < cB we obtain
K Σ
K
S 3A1 +3 Σ
Fk.
k=1
Suppose that S S (1 ac3*) - Art1 + Fe, Vk 2 Define Us = IT (1 + acB*), AA 2 1,U = Then we have
S S SU Ux A U Fk, v
(25)
By summing up (25) from & to K, we have
S Sv A URIAR+I Σ U
When a <
1-9 A a2, we have Up = exp
In(1 + acFi)) < Exp E 1= acB+t S exp( 1-3 Sec 3. Therefore,
c3
K
K
K
K
Σ
S
S UK|
U. St) S UK - UR A + Σ
k F F2) S 34, + Σ
F
k=1
k=1
k=1
k=1
19

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks
C.6. Proof of Lemma 4
The following lemma is the formal version of Lemma
Lemma 14. For any & 2 0, we have
A 11+1)
(A
1=0
A 1b+1) y
Σ (A Abc) 16+1 1-:11-1;i1111 1
b
k
(A Aso
| (D D
1=0
We prove this lemma by induction. Easy to verify that the transformation holds for h = 0. Suppose the transformation holds for k- - 1, then we have
(1-Ax)00
Aox (k+1) = (A- Alo An (k) + A ( k+11 (k+1) -D/= 1z1g((1) ((()
k-1
k-
Σ (A Ago 1 100
(A Abx )
141 - DJ DT
1=0
I=i
+(A - A0x D x+1 |/40
(k) + (A
(D
k+1 D gg())
&
k
Σ (A A 1 Σ
(4 A
(D )
1-1
0=
1=0
which finishes the proof.
C.7. Proof of Lemma 6
We start with the following Lemma.
Lemma 15 (Consensus Lemma for ).
E|I[II - Aoo (1+)) S (K + 1)0² + a² Cyn Σ du + [1
k=
K
K
+ L Σ
E x
(k+1)) + 22L
Σ k==0
El T D
V f(x (1)
(26)
v.N
k=0
where Cg = A M +
Bn 3n
C2 = 1-83
Snx² 82 (1-8513)
Cy = 185309
144m 83 [1-
Cy. = 9n + (1-83)a*
72n
Proof. Using Lemma 4, we know that (I - (k+1) can be decomposed to two rolling sums Σk (A Aoo) D and D LA A Dj Dا! For the first rolling sum, using Assump- - (x((()) and two noise parts, thus applying tion 3 that noise are linearly independent, we can divide (1) into ()((+++))) the Cauchy-Schware inequality:
&
E
(A
Axx
k+l 1- D 1
< EnE Σ
[I(A - ) DD 1302
(27)
==0
1=0
+ 3E
Σ
(A A
-+1 Di+h (V (V[(x(++1)) V)((
20

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks
Sum up (27) from l to K, we have:
k
E
(A
A
(28)
0=
1=0
$ 6no
EII(A
A0o) A00)*+1 ) 1itta122
K
+ 3
E
(A
Ama)
- (V/( (+1)) -
k=0
1m0
< S6nSAMa03(K (K + 1)0² + 3530
Σ
E
V (( ()(x())
1=0
2 + +1)0² + 33309
B (+))) - - at
K
K
s M (K + +1)0² + 18
Σ
TE A
(1+1) 1/ + 902
Σ E|| A (
1=0
where the second inequality uses the rolling sum lemma, the third inequality uses the L-smooth assumption, the final inequality uses Cauchy-Schward inequality.
Next, we consider the second part. Similar to (27), we have
E
(A- Abo)
(0)))++11 - - 4
Dj
(29)
0= i=i
k
k
< 8no 2
Σ> (A
Ao0)
)
1+1 ( - 1
1=0
1=i
k
+ 4F|
(A A00
k+l
(D - -
1=1 L=1
+ 4E|
Σ
(A A
)
-D
1=0
< 8
2
2 g2k+2
+4k
(A - A
-7 - v 1)
1=0
imi
k
+ 4||
Σ (A A
)+11111
D
DJ 11 ((xx
1=0
< 8 + 1) 32k+2
+ 46.
nn 3 32k+2 E3 (((((0) - (((((-11))1
1=1
+ 4(k + +1) n2
22
V fx (1) )|
where the first inequality is similar to the first inequality of (27), the second and third inequality use the fact that [|(A
A - Dj 1|3 & nx=3,,2t 32h+2
21

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks
Sum up (29) from k to K, we have:
K
k (A Abd) 10 113
(30)
0=0
Y=0
8n NAA
(k+ + 1)002 + 33 [ (0) |1 Σ
(k: 1)
k==
K k
+ + 88
k.
k=
8n 3/ 3 (K'
+ 1)02
8MB (
1 39
(1 B23s
24 2, 3.22
+ (1 -3
Σ
BlV - ( 11
8n²x3 3 + 1)0²
33
1-33
(1-33)
144 (1 822
72c L2 K
Σ
(1-B2))
Finally, from the proof of Lemma 2 we know that E| Bl (1I [2:] we obtain the lemma for Ag.
[13] no + Dx ( By replacing
The following Lemma is a formal version of Lemma 6.
2x 1-BA"
Lemma 16 (Consensus Lemma for x). When a S
and K >
we have
s 2/
E A (k+1)
1 20 (C
3na 3na21: v., (K ((K+1)) 110² + Anna2Ls AnaZLs"ACy.0l
(31)
0=
+ 20 3 L' y.u
k=0
where Cy,z, Cg.o, Cy,0 and Cy.y are defined as in Lemma 15.
Proof. Note that A
(k+1) = - a 4
Ato A we apply the rolling sum lemma and obtain that Ei (A
Σ E A 1++
F S a² A Σ | 1
(32)
K
Lemma 15
<
2 3 Cy (K + 1)o² +
(x)x
+
9.M
Σ
dx
a² 22 y.u
Σ E + - v.v Σ El (k)
0=
To estimate KK dh, notice that
72
[TaLi )2 Σ (1+
n
2(TTA]y - [DDbb)
(TAA) - 1Dxl,)2
dg
[Duli
[Duli
[Dv1]
1=1
j=1
<2n
21| DT
11,11 < 2n + 20 202
22

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks
Therefore, Σ dx Σ 2n(K + 1) + 200 az, C2.x S 1/2. Therefore, we can subtract 1 Ek Bl 1|3
28 RAR 1-31
When 2
2xa04 1-3a we have Σk d & 3n(K + 1). When a S
( 1 from both sides of (32). Finally,
2
note that || LA, we obtain the lemma.
C.8. Proof of Theorem 2
Using Lemma 3 estimate the descent deviation in Lemma 2, we have
no F w ()) )1 < [ (10 - ((w
+ (1 + A J 1 + 4000 (AnIR[([[ - -)
Lo
2 du E n D
Ak 2 1.
Then, we can apply Lemma 13, where we set 8 = 3A, c= M L, 4 = - = na V (w)(() (1 +
d =Bll= 'i.D.iV/// (x(xx))
Fs
a² -'to" du + a (1
2 |3 A 11 When a S =n0
1-8A
we obtain that
K
K
n
1 Fll ) < 3B]s(w0 - fr|
a
BlI
(
11)
(33)
2
4n
K
La
K
30T.² + (
A
(1)
Σ
dp
2
k=1
For k= O, note that A (0)
0 and Do Ln, the descent lemma provides
())(w(()) - +
na
V f(x (0)) + f(xx(0)) - 5
- F
[[ 1 (0x
(0)
aLo²
2 do
4n
aLo²
A
[i )1
E A
V
1 | 11,11
||
do
4n
2
A
na
)12
E -. VT
2aLA +
aLo²
do
(34)
2
4n
2
Using (34) and estimate of Σ d# in (33), we obtain that
K
K
TACK
(1)
< 3(1 + 2aLAA
a
Ell
TT
D 1 V f( [1
(35)
2
4n
k=0
K
Ina
2
(.2 + 20
|
(K)
(K +1)
2
k=1
Note that ___
3(1 + 20 < 6. We further plug in Lemma 16 in (33) and obtain that
2n
k
(w
K +1
k=0
12A
+ 15aLo² + (12n-'a'' (1 0.5n -2)
1
B B [E
na(K 1)
K
k=
+ +6n +
6na L22
127.3 20
KA
83
)a² 5 o
(36)
K +
When
(x) is negative. When as, (2 A as). the coefficient 6n 8² a0 L + A3, +
as the coefficient of Σ
E
|
D
< min!
V 24C . (188,,
23

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks
6na²1?Cyy.)) & aL. When a V Therefore, with sufficiently small we have
-
07, the last term
12L k Ja²s3
Cr.0
LA
3 1300
K+1
K+1
K
12A no: K +1)
LA
Σ
E
(
16aTo +
K+
K +
The here should be smaller than minisig7 {as}. where at 2mL 022
Jnll
1-DA NANAT.
03
2AL,/20,,0
24mo3 (1 Cy,r, Cy.s Cy.or C2 positive constants defined in Lemma 15 and only decided by the mixing matrix A. Finally, by selecting a = 1/l1
a5
224C,.o (4
y.v
SALV (1+205AA7)CG)
E 0; ) which smaller than mitligist {as), we have
32
LAo nn(K+ +1)
E 03
Σ
El|l (1
K +11-
V
K +
Define n- n-
21=1 0; -1 1
LCA, where CA is positive constant decided by the mixing matrix A, we have
1 K
LAo2
AL(1 + CA)
V
nK +
K
K
k=
D. Convergence of MG-PULL-DIAG-GT
Compared to vanilla PULL-DIAG-GT, MG-PULL-DIAG-GT introduces two notable changes: multiple gossip and the utilization of batch-average gradients. By calculating the gradient across R batches, under Assumption 3, it follows that the variance of decreases from o² to 0² F The term multiple gossip signifies the substitution of A with A R, in this scenario, S.. SA, A and CA are all modified according to the respective measure of A Therefore, we define AA Aa- || A IT O sup&>1 [(ding(A' A R));"); }, 8 8A" suP | R A 2(1+1((8a) 1-8A
a²
CA = CAR. We define a; has the same expression with ag, but their BA, 8,, O are replaced with B S.A. O respectively,
Using the conclusion of Theorem we obtain
OVLA VnT
LA +
CCA
T= OVLA
LA(1 + CCAR
Σ [
(37)
T
Vnk
K
Next, we demonstrate that when I-9, and r 3 (m(xa) + (n)) Č necessarily an absolute constant. Under definition, Ć^ En so suffices establish that (nLag) is an absolute constant, V1 S $ For á1 = 2
1. (nLāz) = Before estimating (nLo,) 1 # E 7, we show that - BB = 22(), 0 S 2nK
BA 1|A - AboIITA $IA - A =B exp(r In(3a),
1 1 1- (1- 1/e,11111 1].
I exp(-r)
1 1- 3,
When & 2 1,
[A Ja [TT]] [AKR Asolii 2 TA -TA-I|A AbolI 2TA HA
/ V A
IIKA
exaeexp(eee -r)
nKA
TIK
2nK
2n
Therefore, θ, supez1 max; [1#R] S 2nKA. Additionally, we have
24

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks
2(1 + In(xa))
A sup #21
|
A0ol12
1 4VEABAA + In([a)) S AA/Ra(1 In((s)) exp(--r)))))()))) S
- AA
nAA
Note that â2
1-84
exp(r) 8n B
2 nI.
1
thus, L L- - 1.
For 03, we have
$ SA
3682 0 +
288 89
(1 (1-
$2 RAA + VINABA 100.
(nLåg)
100
For 04, we have
21 + (9n
n2 (1-8A")
7
8 S^ + =n2x3 exp( (2pp--2))
(nLág)=1=
S 10
10.
n2
12
For åş, we have
8n2
(nL - / M4
)1 + 03 & 408
ASAMARK + nn22339 < 80.
1 1-BA
Here use the fact that MA sup ||AR Axol22 S /RABA S ana
For åg. we have
72n2R9,3
$ $ 36 1 +n²n383) < 72.
(nLās) (985 +
(1 (1-
For å7, we have
8x3
(nLās) = SAN (1+ 20 NA n11 - )3)3
148ANABA 14.
By combining these inequalities, demonstrate that Ć2 < 300 is absolute constant. Finally, notice that is any constant larger than + 3 In((x)) + 3 In(n), therefore, by choosing 1+31n(K, 4)433) In(x) in (37), we have
1-9A
OVLA (()))( Vnk
LA(1 + ČAJR
OVLA
LA(1 + In(RA) + In(n))
Elll
+
T+1
K
Vnk
(1 BA)
Finally, we discuss the range of I which ensures Σ deR < 3n + 1). Note that do = || < 1, and for any 2 1 we have
deR = b 21 + 2D 1T < 2n + + diag(A' (A' R)
s 2n 16n R3 AAAAAA 2n + 16c S 3n.
So we can cancel the requirement on the range of T or K.
25

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks
E. Experiment Details
In this section, we provide unexplained details experimental setup the article.
E.1. Network Design
In this subsection, we present the networks used our experiments.
Figure A.. Directed exponential graphs with and nodes, and directed ring graph (top three); undirected grid graph, undirected geometric graph, and an undirected nearest neighbor graph (bottum three).
Here list the network metrics of the graphs above:
Directed exponential graph with 8 nodes: A 0.5, KA 1.
Directed exponential graph with 16 nodes: B^ 0.6, K. 1.
Directed ring graph with 16 nodes: AA 0.924, KA 2.
Undirected grid graph with 16 nodes: 3 = 0.887, KAA = 6.25.
Undirected geometric graph with 16 nodes: A = 0.916, KAA = 3.
Undirected nearest neighbor graph with nodes: 3 0.907, K, 1.74.
E.2. Synthetic Data Experiment
conduct numerical experiments on synthetic decentralized learning problem with non-convex regularization. The optimization function is given by:
n f(x)
[(x), E dd
26

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks
where
1 In (1 + exp+exxp(-iill (xp(-uaah((a))
d
[
(1)
+
LE M = L.ccal
T
+
jm
Data Synthesis Process:
1. Global Data Generation:
Generate optimal parameters: Topt (0, Ta)
Create global feature matrix H E RR La xd with haj ~ (),
Compute labels IR Aun with y E {-1,+1} via randomized thresholding:
1 > 1 exp(-hi sopi) 21 ~~
V1
-1
otherwise
2. Data Distribution:
Partition H and across n nodes using:
H = H (i+ 1)M, : y = v(M: :
(1+ 1)M],
M Iuwaa/ /n
where Litil must be divisible by
3. Local Initial Points:
x = Topt + Eis & ~ ah
Gradient Computation: At each iteration, each node independently computes its stochastic gradient by randomly sampling a minibatch of size B from its local dataset of size L, Lioul/n. /n. The gradient computation consists of two components:
[i,((+)) = B
1
Σ b=1
B
2 [z1 (1 1
(38)
exp(y.ch
j=1
Logistic
Non-comvex Regularization
where the minibatch (hi,,, Mi is drawn uniformly from the L; local samples without replacement. Notice that the gradient each node computed the local parameter n. RR.d.
Implementation Details:
Global dataset size Local 204800, batch size B 200
Dimension d = 10, regularization p 0.01
Node configurations: n E {1,2,8, 8, 16, 128, 512]
Notice that Lical 204800 512 200 Tmmax B.
Evaluation Metric: We track
|1, V fx(()))] as gradient norm, where
1 n Σ (i.a( M = L
n a-11 1T
The experimental results shown in our plots represent the average performance across 20 independent repetitions, where each trial is conducted with the fixed random seed 42 for reproducibility.
27

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks
E.3. Neural Network Experiment
Firstly, we employ four-layer fully connected neural network for MNIST classification. The experiments are conducted on four distinet network topologies, each consisting of 16 nodes: directed ring graph, undirected grid graph, a geometric graph, and nearest neighbor graph, illustrated in Figure Al.
The MNIST training dataset, comprising 60,000 images, is evenly distributed across n. 16 nodes, each node maintaining an independent instance of the neural network model. At the end of each batch (that is, communication round), we record key performance metrics, including loss and accuracy. The communication is then executed based on the predefined network topology.
The complete experiment results shown in A2. The accuracy cannot reach 100% because we using constant learning rate and the network is very simple.
Ring
Ring
Grid
Grid
100%
100%
MG=1 (Vanilla)
MG=1 (Vanilla)
10a
MG=5
Accuracy
80%
MG=5
Accuracy
80%
Loss
MG=10
Loss
10
MG=10
40%
MG-1 (Vanilla)
40%
MG-1 (Vanilla)
MG=5
20%
20%
MG=10
MG=10
10
200 400 600 800
200 400 600 800
160
240
Comm. Rounds
Comm. Rounds
Com m. Rounds Nearest Neighbor
Comm. Rounds
Geometric
Geometric
Nearest Neighbor
100%
MG=1 (Vanilla)
MG=1 (Vanilla)
MG=5
Accuracy
80%
MG=5
Accuracy
80%
10
MG=10
MG=10
Loss
60%
Loss
60%
MG=1 (Vanilla) MG-5
MG=1 (Vanilla)
MG=5
20%
20%
MG=10
MG=10
Comm. Rounds
80
160
240
0%
Comm.
80
160
Rounds
240
0
Comm. Rounds
80
160
240
0%
0
Comm. Rounds
80
160
240
Figure A2. Training loss and test accuracy for models trained IIC-PULL-DIAG-OE and PULL-DIAG-GT MNIST dataset. MG- BULL-DIAG-GT outperforms on all topologies.
Secondly, we employ ResNet18 for CIFAR10 classification. The experiments are conducted on four distinct network topologies, each consisting of 16 nodes: a directed ring graph, an undirected grid graph, a geometric graph, and a nearest neighbor graph, as illustrated in Figure A1.
The experimental results are as follows:
28

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks
Ring
Ring
Grid
Grid
100%
100%
MG=1 (Vanilla)
MG-1 (Vanilla)
MG=4
Accuracy
80%
10
MG=5
Accuracy
80%
Loss
10
MG=8
60%
Loss
MG-10
60%
40%
MG=1 (Vanilla)
40%
MG=1 (Vanilla)
MG=4
MG=5
20%
MG=8
10 1
20%
MG=10
60 120 180 240 Comm. Rounds
0%
60
120 180 240
60
120
180
240
0%
0
60
120
180 240
Comm. Rounds
Comm. Rounds
Comm. Rounds
Geometric
Geometric
Nearest Neighbor
Nearest Neighbor
100%
MG=1 (Vanilla)
(Vanilla)
10c
MG-5
Accuracy
80%
10
MG=5
Accuracy
80%
Loss
MG=10
Loss
MG=10
60%
40%
MG=1 (Vanilla) MG-5
40%
MG=1 (Vanilla)
10-1
MG=5
20%
20%
MG-10
MG=10
10:
30
60
90
120
0%
30
60
90
120
0
50
100
150
200
100
150 200
Comm Rounds
Comm. Rounds
Comm. Rounds
Comm. Rounds
Figure A3. Training loss and test accuracy for models trained by MG-PULL-DIAG-GT outperforms on all topologics.
and PULL-DIAG-GT on CIFAR-10 dataset.
Lastly, we provide an experiment on the heterogeneous MNIST dataset where each node possesses a unique data distribution, see Figure A4.
Uniform Distribution
Heterogeneous Distribution
392
378
35.6
352
369
365
404
342
120
285
2B
254
120
691
460
828
1800
375
356
390
1115
345
275
391
347
370
1254
127
273
1400
377
4M4
366
337
195
340
389
379
372
m
344
615
507
631
20
577
139
301
396
443
326
394
341
372
359
395
352
382
55
722
130
978
30
133
15
507
46
18
1200
340
420
185
187
360
390
172
63
12
1430
131
73
167
Node Index
1000
384
390
381
351
373
404
220
857
371
237
138
378
413
362
367
380
346
382
396
353
353
324
439
72
38
791
1577
498
258
65
400
451
347
364
345
329
374
403
376
361
440
1149
245
64
665
229
171
681
4-1
313
425
396
340
330
393
9
21
43
128
165
1688
406
369
354
337
373
391
394
24
585
93
552
510
69
1207
366
429
386
412
388
338
357
391
362
35L
98
34
408
95
37
258
45
171
93
555
267
433
373
352
570
339
370
393
572
371
62
671
137
625
190
530
203
531
252
104
359
365
306
415
19
254
259
531
121
1
2
4
6
6 0
2
Class Index
Class Index
Figure A4. Left: Uniform MNIST data distribution used in the experiments in Section 6. Right: Heterogencous MNIST data distribution used in the additional experiment shown in Figure A5.
29

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks
Ring
Ring
Grid
Grid
100%
MG=1 (Vanilla)
MG=1 (Vanilla)
MG=5
Accuracy
10-1
MG-5
Accuracy
80%
Loss
MG=10
60%
Loss
60%
MG=1 (Vanilla)
MG=1 (Vanilla)
MG=5
MG=5
10
20%
10-3
20%
MG=10
60
120
180 240
0%
60
120
180
240
0%
0
80
160 240 320
Comm. Rounds
Comm. Rounds
Comm. Rounds
Comm. Rounds
Geometric
Geometric
Nearest Neighbor
Nearest Neighbor
10
100%
100%
MG=1 (Vanilla)
MG=1 (Vanilla)
10
MG=5
Accuracy
10
MG-5
Accuracy
80%
Loss
MG-10
60%
Lose
10-2
MG=10
60%
10
40%
MG=1 (Vanilla)
40%
MG=1 (Vanilla)
10
MG=5
10-3
20%
MG=5
MG=10
MG-10
80
160
240
0%
160
10-4
0%
100
200
300
400
Comm. Rounds
Comm. Rounds
Comm. Rounds
Comm. Rounds
Geometric
Nearest Neighbor
100%
100%
80%
80%
$6.3%
Accuracy
87.3%
Accuracy
$1.3%
60%
60%
97.3%
220
182
200
61.7
152
224
40%
MG=1 (Vanilla)
40%
MG=1 (Vanilla)
MG=5
MG=5
20%
MG=10
20%
MG=10
0%
0%
80
160
100
200
300
400
Comm. Rounds
Comm. Rounds
Figure A5. Training loss test accuracy 4-layer neural network trained using MG-Pull-Diag-GTT and vanilla Pull-Diag-GT on the MNIST dataset. The data is distributed in a heterogeneous manner (see Figure A4).
30

---

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-Stochastic Networks
E.4. Learning Rates
In Figure 2:
Exponential graph of n nodes:
na = 0.512.
Ring graph of nodes:
na 0.002
In Figure 3 and 4:
For ring graph with times of multiple gossips, the learning rate om satisfies:
01
0.005, as 0.01, a 0.02.
Grid graph:
01 = 0.02, 05 = 0.03, 0:0 = 0.03.
Geometric graph:
Q1 = 0.02, 05 = 0.02, 010 = 0.03.
Nearest neighbor graph:
Q1 = 0.02, 0t = 0.02, 010 = 0.02.
Here, the learning rates are chosen in non-decreasing order, as the MG mechanism typically permits a wider range of stable learning rates.
31


Reviews:
[{"review_id": "jUOmVcs4DP", "reviewer": "Reviewer_MwZe", "summary": "This paper presents a theoretical analysis of decentralized optimization with row-stochastic mixing matrices. It is the first to establish a lower bound for convergence. Gradient tracking-based algorithms are shown to achieve linear speedup in convergence under an additional assumption. To overcome this limitation and attain a near-optimal convergence rate, the authors propose a new algorithm that incorporates multiple gossips. Experimental results validate the theoretical findings.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their insightful feedback and constructive comments. Below, we address each point in detail. **All newly added experiments can be found in the Rebuttal Experiment Sheet (RES)** https://anonymous.4open.science/r/ICML-2025-Rebuttal-Experiment-Sheet-B6C0/\n\n**Experimental Designs Or Analyses**\n\n1. We add an experiment training ResNet-18 on CIFAR-10, using both vanilla Pull-Diag and its MG versions. Data is uniformly distributed. See Figure 1 in RES.\n\n2. Both $\\beta_A$ and $\\kappa_A$ will affect the results. For most topologies (including random graphs), $\\kappa_A$ is typically a small number and convergence rate is mainly affected by $\\beta_A$. For special mixing matrices, as shown in our Proposition 8, $\\kappa_A$ can be exponentially large. In this case, vanilla Pull-Diag-GT suffers a lot, while its MG version can achieve quick convergence and higher precision. We present experiments for large $\\kappa_A$ in Figure 2 in RES.\n\n3. Yes, MNIST data is uniformly distributed. For heterogeneous results, see Figures 3,4 in RES.\n\n4. Since we use a constant learning rate and a simple 4-layer neural network, the test accuracy will not reach 100\\% in the end.\n\n**Relation To Broader Scientific Literature**\n\nOur work addresses a series of new challenges with original techniques. **These challenges and techniques are detailed in our response to Reviewer zni5.** For reviewer's convenience, we also provide a brief summary as follows:\n\ni. **Consensus protocol: Pull-Diag is fundamentally different from Push-Sum.** Pull-Diag introduces stronger nonlinearities and disrupts the linear structure exploited in Push-Sum analysis. It is not a dual or transpose of Push-Sum, thus new analytical tools are needed. See Lemma 12.\n\nii. **New error terms.** Liang et al. only handle consensus error. In our case, we must additionally control descent deviation, which arises from the interaction between Pull-Diag and gradient tracking. This term is new in nonconvex settings and is analyzed via Lemmas 2 and 3.\n\niii. **Non-uniform gradient tracking**: In Push-DiGing, all gradients carry the same weight, allowing standard $L$-smoothness arguments. In our method (Eq. 5b), gradient coefficients vary, breaking this symmetry. We introduce Lemma 4 to handle this non-uniformity.\n\niv. **Inversion of small values.** Pull-Diag involves inverting diagonal entries that can be arbitrarily small, making it hard to control bounds. In Lemma 7, we show that MG guarantees a positive lower bound on these values, allowing us to derive clear convergence rates in terms of $\\kappa$ and $\\beta$. While this matches a conclusion in Liang et al., the underlying logic is different.\n\nIn a nutshell, our work provides new analytical tools to handle the unique challenges introduced by Pull-Diag and Row-Only settings. These tools can be extended to analyze other algorithms in similar settings. \n\n**Essential References Not Discussed**\n\nWe will discuss connection failure (Yemini et al.,2022, Li et al 2024) and include more recent literature on Row-Only algorithms (Jeong and Kountouris, 2024, Nguyen et al. 2023, Xing et al., 2024).\n\n**Other Comments Or Suggestions**\n\n1. The problem in Figure 1 is ''achieving average consensus''. Initially, every agent $i$ has vector $z_i$. Agents communicate with their neighbors and all want$\\frac{1}{n}\\sum_{i=1}^n z_i$ in the end. The $y$-axis denotes the distance between their current state and $\\frac{1}{n}\\sum_{i=1}^n z_i$. This can be seen as a strongly convex optimization problem. We plot Figure 1 to show the impact of $\\beta_A$ and $\\kappa_A$ on Pull-Diag, thereby justifying their use in characterizing row-stochastic matrices. However, we do not use Figure 1 to support our theoretical results in non-convex settings.\n\n2. Our abstract will be modified as:\n\n... deviation in the descent direction caused by the adapted gradient tracking (GT) and instability introduced by the PULL-DIAG protocol.\n\n3. Under Assumption 1, an equivalent statement of Assumption 4 is: $A$ has a positive diagonal (every node has a self-loop). This equivalence can be derived using Lemma 7. We will include this in a future version.\n\n4. $(i,j) \\in E$ represents an edge from $i$ to $j$. \n\n**Questions For Authors**\n\nFor Question 1,\n- Our work differs from Liang et al. (2023) in both setting and analysis. Please check our response to **Relation To Broader Scientific Literature** and a more detailed version can be found in our response to Reviewer zni5.\n\n- The key novelty is that, our analysis framework is more general. Liang et al. analyzes **exact** descent method, while our method addresses **inexact** descent with disturbacnes.  Detailed explanation of this distinction can also be found in our response to Reviewer zni5.\n\n- We have discussed this distinction in our paper pages 5 and 6, and a further clarification will be included in Appendix due to page limits.\n\nFor Question 2,\n- Yes. We would use near-optimal in title in a future version.", "claims_and_evidence": "The claims in the theory part are clear, with step-by-step sketch of the proofs, which are easy to understand. However, the experiments are not as convincing as the math derivations.", "methods_and_evaluation_criteria": "Yes, techniques used in this paper, as well as the performance evaluation, are widely accepted in this field.", "theoretical_claims": "Yes, theoretical claims look good to me.", "experimental_designs_or_analyses": "Experiments look traditional. I have a few questions on the design:\n1. Is it possible to showcase the MG component in a larger real dataset? \n2. The graph structure is either un-directed or directed with good structure. How will the graph topology change the results? For example, a random directed graph, and/or even with high $\\kappa_A$?\n3. How is the MNIST data distributed. Are they homogenous (uniform)?\n4. Is there any explanation on the plateau-like stage of the accuracy in the neural net experiments?", "relation_to_broader_scientific_literature": "This paper inherits ideas from Liang et al. (2023) with same metric definitions, similar MG remedy for the convergence, and analogous bounds. Therefore, the results in this paper sounds reasonable as everything looks like a transpose (to me). It could be better if the authors are able to emphasize the technical difference between their results and that literature work.", "essential_references_not_discussed": "I suggest adding more recent works. For example, in Section 1, most papers look like before pandemic. In addition, I would like to see more practical evidences of analyzing directed graph. E.g., there is one paper for differences in node power ranges, and what about channel disruptions?", "other_strengths_and_weaknesses": "No more comments here. Important questions or suggestions are **numbered** in the corresponding parts.", "other_comments_or_suggestions": "1. In Section 2.3, right before Section 3, the referred Figure 1 shows exponential rate of convergence. I would guess it is because it works on a strongly-convex problem. However, I did not find where the description of the setting locates (or I missed it). This might cause misunderstanding of the claim of convergence rate, as your assumptions are much milder than strong convexity.\n2. I suggest explaining the abbreviation GT before using it in the abstract, similar to MG.\n3. it could be better to discuss the limitation of Assumption 4, as it looks unnatural and it is hard to tell which scenarios satisfy or un-satisfy this assumption. \n4. In Section 2 Assumption 1, the meaning of $(i,j)\\in\\mathcal{E}$ needs clarification, as this is a directed graph.", "questions_for_authors": "1. This paper closely follows the approach of Liang et al. (2023), including the use of a specific metric, a similar multi-gossip (MG) strategy to address optimal convergence, and analogous forms of the resulting bounds. As a result, the theoretical originality here sounds unclear to me. To strengthen the contribution, it is important for the authors to clearly articulate the technical novelties and distinctions from the literature, beyond applying known ideas in a slightly different setting.\n\n2. Would it be more accurate to describe the result as near-optimal, given the logarithmic gap between Theorem 3 and Theorem 1? I find the phrasing in the title of Section 5—“near-optimal rate”—both appropriate and reflective of the paper’s contributions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "v5qBg6ZykT", "reviewer": "Reviewer_zni5", "summary": "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,\nthe row-stochastic scenario remains unexplored.\nThis paper bridges this gap by introducing effective metrics to capture the influence of row-stochastic mixing matrices and establishing the\nfirst convergence lower bound for decentralized\nlearning over row-stochastic networks.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Reviewer's Comment:** \n\nWeakness: The techniques used in this paper are mainly from ''Towards better understanding the influence of directed networks on decentralized stochastic optimization''. (Liang et al. (2023))\n\n**Authors' Response:**\n\nWe sincerely thank the reviewer for their insightful feedback and constructive comments. \n\nWhile our work is inspired by Liang et al. (2023), it differs significantly in both **problem setting** and **analytical techniques**. We encountered many new challenges and we developed original techniques for each of them,  listed as follows:\n\n**1. Challenges in Consensus Protocols.**\n\n- Liang's work studied Push-Sum protocol. In Push-Sum protocol, for a column-stochastic matrix $B$, its Perron vector $\\pi_B$ is estimated by  $v^{(k)}:=n^{-1}B^k 1_n$. Due to the **linear** relationship $v^{(k+1)}=Bv^{(k)}$, the estimate from Push-Sum is consistent and enjoys good monotone properties (Lemma 2.1 in Liang et al. (2023)).\n\n- **Our work** studied Pull-Diag protocol. In Pull-Diag protocol, for a row-stochastic matrix $A$, the Perron vector $\\pi_A$ can only be estimated by $d^{(k)}:=\\rm{Diag}(A^k)$. Note that $d^{(k+1)}$ is **nonlinear** corresponding to $d^{(k)}$, we need to propose a novel analysis to study the property of Pull-Diag. See our Lemma 12.\n\n**2. Challenges in Obtaining Linear Speedup (Inexact Descent).**\n\n- Liang's work studied Push-Diging algorithm, which is an **exact** descent algorithm because the update follows (after proper projection):\n$$\\hat{x}^{(k+1)}=\\hat{x}^{(k)}-\\gamma n\\bar{g}^{(k)},$$\nwhere $\\hat{x}^{(k)}$ is the projected parameter and $\\bar{g}^{(k)}$ is the average of local gradients. This resembles **centralized SGD**, making the linear speedup result easy to be obtained.\n\n- **Our work** studied Pull-Diag-GT, which is an **inexact** descent algorithm because the update follows\n$$\\hat{x}^{(k+1)}=\\hat{x}^{(k)}-\\gamma \\pi_A^\\top y^{(k)}.$$\nCompared to exact descent, we have an extra gap: $\\pi_A^\\top y^{(k)}-n\\bar{g}^{(k)}$. This term, called **descent deviation**, typically prevents us from obtaining a linear speedup. Prior to our work, this term can only be dealt under the strongly-convex and deterministic setting. Our work is the **first** to rigorously handle such descent deviation in the nonconvex, $L$-smooth and stochastic setting. Lemmas 3, 4, 6, and 13 provide the tools for bounding and controlling this term. These lemmas can also be applied on similar inexact descent problems.\n\n**3. Challenges in Adapted Gradient Tracking.**\n\n- Liang's work studied standard gradient tracking, which is\n$$y^{(k+1)}=By^{(k)}+g^{(k+1)}-g^{(k)}.$$\nIn standard gradient tracking, $g^{(k+1)}-g^{(k)}$ can be easily bounded using the $L$-smoothness property. This also enables a straightforward estimate for  $y^{(k)}$.\n\n- **Our work** studied adapted gradient tracking, which is\n$$y^{(k+1)}=Ay^{(k)}+D_{k+1}^{-1}g^{(k+1)}-D_k^{-1}g^{(k)}.$$\nThe different coefficients $D_{k+1}$ and $D_k$ make it highly nontrivial to apply $L$-smoothness property. Our Lemma 4 provided valuable insights on how to address this problem.\n\n**4. Challenges Raised from Inversion of Small Values.**\n\n- In Push-Sum protocol studied by Liang et al (2023), the estimate of Perron vector $v^{(k)}$ is naturally lower bounded by a $\\kappa$-related constant. They do not need to worry about the numerical instability.\n\n- **Our work** studies Pull-Diag protocol, which uses inversion of diagonal entries to do corrections. However, these diagonal entries can be arbitrarily small or zero, even for fixed $\\kappa_A$ and $\\beta_A$. To avoid being divided by zero, we must have Assumption 4 to provide a lower bound for diagonal entries. Altough this is a weak assumption (See our response to Reviewer MwZe, 3rd problem in 'Other Comments Or Suggestions'), this will prevent us from attaining the lower bound.   \nFortunately, in Lemma 7, we discover that MG will guarantee a positive lower bound on diagonal entries. This allows us to remove Assumption 4 and to derive a clear convergence rate using only $\\kappa_A$ and $\\beta_A$. While the final conclusion matches the conclusion in Liang et al. (2023), the underlying logic is quite different.\n\nIn summary, our analysis provides a more general framework capable of handling richer sources of inexactness in decentralized optimization. We developed original techniques which differs from Liang et al. (2023).\n\nThe challenges and distinctions above have also been discussed in our paper, pages 5 and 6.  A further clarification will be included in Appendix due to page limits.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "A good extension of previous work.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strength: This paper  introduces effective metrics to capture the influence of row-stochastic mixing matrices and establishing the\nfirst convergence lower bound for decentralized\nlearning over row-stochastic networks. \nWeakness: The techniques used in this paper are mainly from ``Towards better understanding the influence of directed networks\non decentralized stochastic optimization''.", "other_comments_or_suggestions": "No", "questions_for_authors": "No", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wPmKV2cUv9", "reviewer": "Reviewer_Si9i", "summary": "This paper studied the decentralized optimization problem where the mixing matrix is row-stochastic. This paper first derived the lower bound. Then, this paper analyzed PULL-DIAG-GT, showing that PULL-DIAG-GT requires an additional assumption, Assumption 4, to converge to the stationary point. Finally, this paper proposed a novel method, MG-PULL-DIAG-GT, which uses gradient accumulation and multiple gossip averaging. Then, this paper showed that MG-PULL-DIAG-GT can achieve almost the same convergence rate as the lower bound.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their insightful feedback and constructive comments. Below, we address each point in detail.\n\n**Q1:** Could you please describe how the authors tuned hyperparameters, e.g., learning rate, in Sec. 6? This information is very important for reproducing the experimental results.\n\n**A1:** Thank you for your reminder. We will briefly describe how we tuned the learning rates and the logics behind it. \n- Figure 2: For exponential graph of $n$ nodes, the learning rate $\\alpha_n$ satisfies $$\\alpha_n\\times n=0.0512.$$ For ring graph of $n$ nodes, the learning rate $\\alpha_n$ satisfies $$\\alpha_n\\times n=0.002.$$ We set $n\\times \\alpha$ as a constant because, as shown in Appendix (lines 1268-1271), we have the bound\n$$\\frac{1}{K+1}\\sum_{k=0}^K \\mathbb{E}[\\|\\nabla f(w^{(k)})\\|^2] \\le \\frac{12\\Delta}{ n\\alpha(K+1)}+16\\alpha L\\sigma^2+  \\frac{L\\Delta}{K+1}.$$\nThis implies that $n\\alpha$ effectively controls the _descent rate_. By fixing $n\\alpha$, we ensure that all curves decay at the same rate and only differ in their final noise-dominated error level. \n\n- Figure 3: For ring graph with $m$ times of multiple gossips,  the learning rate $\\alpha_m$ satisfies: $$\\alpha_1=0.005,\\alpha_5=0.01,\\alpha_{10}=0.02.$$\nFor grid graph with $m$ times of multiple gossips,  the learning rate $\\alpha_m$ satisfies: $$\\alpha_1=0.02,\\alpha_5=0.03,\\alpha_{10}=0.03.$$\nFor geometric graph with $m$ times of multiple gossips,  the learning rate $\\alpha_m$ satisfies: $$\\alpha_1=0.02,\\alpha_5=0.02,\\alpha_{10}=0.03.$$\nFor nearest neighbor graph with $m$ times of multiple gossips,  the learning rate $\\alpha_m$ satisfies: $$\\alpha_1=0.02,\\alpha_5=0.02,\\alpha_{10}=0.02.$$\nHere, the learning rates are chosen in a non-decreasing order, as the MG mechanism typically permits a wider range of stable learning rates. \n\nWe will include these in Appendix E in a future version.\n\n**Q2:** The authors used exponential graph, grid, and ring as the network topology, all of these graphs have a doubly stochastic mixing matrix. Could you please show some additional experimental results with a graph whose mixing matrix is not doubly stochastic?\n\n**A2:** Thank you for the question. While these graphs can support doubly stochastic matrices, we generate **row-stochastic** matrices over them, not doubly stochastic. We construct these matrices using the Metropolis rule (Nedic et al., 2018), where  \n$$\na_{ij} = \\begin{cases}\n\\frac{1}{1 + d_j^{\\text{in}}}, & \\text{if } (i \\to j) \\text{ exists} \\\\\\\\\n0, & \\text{otherwise}\n\\end{cases}\n$$\nThis typically yields a row-stochastic matrix. Only in the special case of regular graphs does the Metropolis rule produce a doubly stochastic matrix. We will emphasize that we used row-stochastic matrices in a future version.\n\nOn the other hand, the row-stochasticity of these matrices can be verified by examining $\\kappa_A$ listed in Appendix E (lines 1413–1421). Recall that $$\\kappa_A = 1, \\quad  \\text{if and only if } A \\text{ is doubly stochastic.}$$  For graphs ring, grid, geometric, and nearest neighbor, we have $\\kappa_A > 1$, confirming that the mixing matrices are not doubly stochastic.\n\n**Q3:**  Can the authors explain why acceleration is impossible (or unnecessary) when the mixing matrix is row-stochastic?\n\n**A3:** Thank you for your insightful question. We will cite [1,2] and carefully discuss them in related works. \n\n- In [1,2], accelerated gossip relies on the mixing matrix being **doubly-stochastic and symmetric (or having real spectrum)**. This structure is crucial: after each power iteration (e.g., $A \\to A^2$), the eigenvalues remain real and lie on the positive real axis. This allows a spectral shift (e.g., via Chebyshev polynomials) to center the spectrum around zero, reducing the spectral radius and enabling acceleration. In contrast, our setting involves **row-stochastic and generally non-symmetric** mixing matrices, for which the eigenvalues are complex and not aligned along the real axis. Without symmetry or spectral knowledge, Chebyshev-type acceleration becomes ineffective or even impossible.\n\n- Another reason lies in the network dependence on $1 - \\beta$. In doubly-stochastic scenarios, the optimal dependence is $1/\\sqrt{1 - \\beta}$, which requires Chebyshev acceleration to achieve. In contrast, for row-stochastic matrices, the optimal dependence is $1/(1 - \\beta)$, which is worse than in the doubly-stochastic case. Such $1/(1 - \\beta)$ dependence can be attained without Chebyshev acceleration.\n\n**Other Comments:**\n\nWhile our proposed optimal algorithm combines existing algorithmic components, the **analysis technique is original** and departs from prior work in several key aspects. In particular, our work is the **first to handle \"inexact descent\"** in the nonconvex setting, whereas existing analyses focus on exact descent methods. We provide a detailed explanation of this distinction in our response to Reviewer zni5.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "No", "experimental_designs_or_analyses": "See the comments in the suggestion.", "relation_to_broader_scientific_literature": "The proposed method seems to be a combination of existing techniques, gradient accumulation, multiple gossip averaging, and gradient tracking. However, deriving the lower bound of the convergence rate and showing that the proposed method can achieve almost the same rate as the lower bound are solid contributions to the research community.", "essential_references_not_discussed": "The related papers seem to be well discussed in this paper.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "* Could you please describe how the authors tuned hyperparameters, e.g., learning rate, in Sec. 6? This information is very important for reproducing the experimental results.\n* The authors used the exponential graph, grid, and ring as the network topology, while all of these graphs have a doubly stochastic mixing matrix. Could you please show some additional experimental results with a graph whose mixing matrix is not doubly stochastic?\n* If the mixing matrix is doubly-stochastic, we need to use accelerated gossip averaging to achieve the optimal convergence rate [1,2]. The proposed method seems to achieve the lower bound without using this acceleration. Can the authors explain why acceleration is impossible (or unnecessary) when the mixing matrix is row-stochastic?\n\n\n### Reference\n[1] Tian, Y., Scutari, G., Cao, T., and Gasnikov, A. Acceleration in distributed optimization under similarity. In ICML 2022.\n\n[2] Yuan, K., Huang, X., Chen, Y., Zhang, X., Zhang, Y., and Pan, P. Revisiting optimal convergence rate for smooth and non-convex stochastic decentralized optimization. In NeurIPS 2022", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper aims at determining the optimal convergence rate for decentralized optimization over a row stochastic network and designing an algorithm to achieve it. For the former, new metrics are designed to capture the influence of row-stochastic mixing matrices. For the latter, a novel analytical framework and a multiple-step gossip protocol are combined so as to design an optimal algorithm. Although the proposed method is a combination of existing techniques, the reviewers agree that the contributions are solid. The authors are encouraged to further highlight the new features compared to the existing works. All reviewers unanimously recommend acceptance.
Decision: Accept (spotlight poster)