Enhancing Parallelism in Decentralized Stochastic Convex Optimization
Authors: Ofri Eisen
Ron Dorfman
Kfir Yehuda Levy
Venue: ICML 2025 poster (2025)
Keywords: Decentralized Learning
Stochastic Convex Optimization
Primary area: optimization->large_scale_parallel_and_distributed

Abstract: Decentralized learning has emerged as a powerful approach for handling large datasets across multiple machines in a communication-efficient manner. However, such methods often face scalability limitations, as increasing the number of machines beyond a certain point negatively impacts convergence rates. In this work, we propose *Decentralized Anytime SGD*, a novel decentralized learning algorithm that significantly extends the critical parallelism threshold, enabling the effective use of more machines without compromising performance. Within the stochastic convex optimization (SCO) framework, we establish a theoretical upper bound on parallelism that surpasses the current state-of-the-art, allowing larger networks to achieve favorable statistical guarantees and closing the gap with centralized learning in highly connected topologies.

Enhancing Parallelism in Decentralized Stochastic Convex Optimization
Ofri Eisen *1
Ron Dorfman *1
Kfir Y. Levy!
Abstract
this design simplifies training management, it faces scala- bility challenges due to communication bottlenecks and is inherently vulnerable to a single point of failure since the server is essential to system operation.
Decentralized learning has emerged power- ful approach for handling large datasets across multiple machines in a communication--fficiee manner. However, such methods often face scal- ability limitations, as increasing the number of machines beyond a certain point negatively im- pacts convergence rates. In this work, we propose Decentralized Anytime SGD, a novel decentral- ized learning algorithm that significantly extends the critical parallelism threshold, enabling the ef- fective use of more machines without compromis- ing performance. Within the stochastic convex optimization (SCO) framework, we establish a theoretical upper bound on parallelism that sur- passes the current state-of tfte-offthe--at, allowing larger networks to achieve favorable statistical guaran- tees and closing the gap with centralized learning in highly connected topologies.
In contrast, decentralized systems rely on direct interactions between neighboring machines, eliminating the need for a central PS (Kempe et al., 2003: Boyd et al., 2006; Nedic & Ozdaglar, 2009; Lian al., 2017). While this architec- ture introduces challenges in coordination and maintaining global model consistency, it offers significant advantages. By reducing the risk of single point of failure and en- hancing communication efficiency, decentralized systems provide greater flexibility and resilience (Assran et al., 2019; Kong et al.. 2021; Yuan et al., 2021: Li et al., 2022).
A central trade-off in distributed learning, both centralized and decentralized, lies in balancing parallelism with statisti- cal efficiency. While increasing parallelism- by incorporat- ing more machines accelerate training, it may degrade learning efficiency beyond a certain point. This issue is particularly acute in decentralized systems, where sparse communication topologies amplify performance degrada- tion, limiting the effective utilization of additional machines.
1. Introduction
Distributed learning has become key paradigm for large- scale machine learning (ML), where multiple machines train an MI. model by utilizing their collective data and computational resources (Verbraeken et al., 2020). This ap- proach enables efficient ML scaling by accelerating training through parallel computation. Distributed MI systems are especially useful when data is inherently distributed across multiple users, in federated learning (McMahan et al., 2017; Kairouz et al., 2021). where preserving local data privacy is a priority.
Existing decentralized methods reveal persistent gap be- tween centralized and decentralized learning in their ability to scale with the number of machines (Koloskova et al., 2020; 2021; He et al., 2022). Surprisingly. this gap is ob- served even in highly connected network topologies, where information between nodes propagates faster, effectively mimicking the behavior of centralized systems. This raises the question of whether decentralized methods are funda- mentally constrained in fully exploiting increased paral- lelism, even under ideal communication conditions.
Distributed learning systems are broadly categorized into two primary architectures: centralized and decentralized. Centralized systems rely on central parameter server (PS) to coordinate training by aggregating local computations and distributing global model updates (Li et al., 2014). While
In this work, we propose Decentralized Anytime SGD (DAT- SGD), a novel and simple algorithm designed enhance parallelism in decentralized systems. It relies on the Any- time SGD framework (Cutkosky, 2019), where stochastic gradient descent (SGD) updates are performed using gra- dients evaluated at averaged iterates. Each machine per- forms these updates locally and exchanges information with its neighbors. By relying on averaged query points that evolve more slowly than the iterates themselves, our ap- proach effectively mitigates the bias caused by local model inconsistencies, also known as consensus distance.
Eqqual contribution 'Department of Electrical and Computer Engineering. Technion, Haifa, Israel. Correspondence to: Ofri Eisen <ofti.eisen @ campus.teccnion...... acc.nio...c.il..
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Enhancing Parallelism in Decentralized SCO
& Ozdaglar, 2009; Lian et al., 2017). This design not only mitigates the risk of a single point of failure but also offers greater scalability and flexibility (Assran et al., 2019; Kong et al., 2021; Yuan et al., 2021). A common mechanism underpinning these benefits is the gossip averaging protocol (Xiao & Boyd, 2004; Boyd et al., 2006), a low-overhead communication method that efficiently disseminates model updates across the network.
Table Parallelism Bounds. Comparison of parallelism bounds for decentralized SCO across different network topologies for Decentralized SGD (D-SGD, Koloskova et al., 2020) and our method, expressed in terms of the total number of samples N = M For reference, the centralized case achieves a bound of O(vN). NC stands for near-complete graph. Higher parallelism bounds are better, allowing us to accelcrate the learning process without degrading performance.
In the context of stochastic optimization, decentralized train- ing approaches have garnered considerable interest in re- cent years. The stochastic convex case was explored by Lian et al. (2017), who analyzed the Decentralized (D-SGD) method. Later, Koloskova et al. (2020) extended this approach within a unified framework that accounts for changing topologies and randomized gossip communication. While these aforementioned methods degrade in the face of data heterogeneity, Koloskova et al. (2021) completely elim- inated this issue by employing an approach called gradient- tracking (Di Lorenzo & Scutari, 2016; Nedic et al., 2017; 7; Pu & Nedić, 2021). See Table for a comparison of conver- gence rates.
TOPOLOGY
1/p
D-SGD
DAT-SGD
RING
O(M²)
O(NU/S
O(N2/9) O(NV9)
TORUS
((M)
O(N2/6)
NC
R 1
((DVN)
We perform our analysis within the stochastic convex opti- mization (SCO) framework-a powerful framework which captures several classical problems like SVMs and linear regression, as well as serving as a testbed towards designing and analyzing ML algorithms.
For convex and smooth functions, our method achieves error of over decentralized network of M machines in T = O(1/Me² + p/pc) iterations, where P E (0, 1] is the spectral gap of the network, a parameter that cap- tures the connectivity of the network topology (see Def- inition 2.5 for a formal definition). This result implies that (1) for complete (or near-complete) topologies, where p (11), our algorithm recovers the convergence rate of centralized methods (Dekel et al., 2012), thus filling the gap implied by prior methods; and (2) for general topolo- gies, it improves upon the previously best-known rate of (11/M22+ + // (Koloskova et al., 2020), thereby enabling larger networks while maintaining linear speed-up: see Table 1 for comparison of parallelism bounds for com- mon network topologies. In Section 2.1, we elaborate on the computation of these parallelism bounds.
Curiously, all existing methods present convergence bounds that imply a clear gap between the centralized and decen- tralized cases, even for highly connected topologies. Con- cretely, in centralized systems one may use up to O(VN) machines to accelrrate the learning process without degrad- ing generalization (Dekel et al., 2012), where N is the total number of samples used in the process. Conversely, in de- centralized systems the best known parallelization limit is M I ((PVNN)1/)) which is substantially smaller. See Table for bounds regarding different topologies.
Decentralized training has also been extensively studied in the context of stochastic non-convex optimization. This was done in (Lian et al., 2017: Koloskova et al., 2020; 2021), which have derived analogous bounds to the ones they achieved in the convex setting. Additionally, Kong et al. (2021) empirically studied the interplay between the local model parameters and gossip communication. More recently. He et al. (2022) improved convergence rates for non-convex problems by replacing local SGD updates with local momentum updates, establishing a parallelization limit of M < (((p/))2/3) However, this remains below the centralized bound of M s O(VN), which applies in the non-convex setting.
1.1. Related Work
Centralized learning systems are widely adopted in both industry and academia, thanks to their simplicity and the effectiveness of Minibatch SGD (Dekel et al., 2012), which is the most widespread approach to training in such sys- tems. While alternative centralized methods like local-SGD have been explored in recent years (McMahan et al., 2017; Kairouz et al., 2021), Minibatch SGD still serves as a cor- nerstone in large-scale training due to its ease of implemen- tation and strong empirical performance.
To further improve the parallelism bound, we build on a re- cent technique that involves gradually shifting query points in SCO (Cutkosky, 2019). This approach has been lever- aged in recent works to improve asynchronous (Aviv et al., 2021) and local (Dahan & Levy, 2024) training methods, as well as to design universal accelerated algorithms (Kavis et al., 2019; Enc et al., 2021; Antonakopoulos et al., 2022).
Despite the enduring popularity of centralized training, de- centralized systems present an appealing alternative by clim- inating the need for a central parameter server and enabling direct communication among neighboring machines (Tsit- siklis, 1984; Kempe et al., 2003; Boyd et al., 2006; Nedic
2

---

Enhancing Parallelism in Decentralized SCO
We note that our bounded heterogeneity assumption has been widely adopted in prior works (Lian al., 2017; Tang et al., 2018a; Li et al., 2019; He et al., 2022). Notably, some studies have explored milder assumptions, requiring bounded heterogeneity only at the optimum (Koloskova et al., 2020) or at the origin (Lu & De Sa, 2021), or even removing this assumption entirely by leveraging techniques such as gradient tracking (Nedic al., 2017: Koloskova et al., 2021). In this work, we adopt the standard bounded heterogeneity assumption for simplicity, leaving potential relaxations to future work.
Table Convergence to e-aceuracy. Comparison of convergence rates with prior work in convex decentralized learning. Here, a denotes noise variance, { represents data heterogeneity, and p is the spectral gap. We note that the leading term o² /M e is statistically optimal (Nemirovski Yudin, 1983).
REFERENCE
CONVERGENCE RATE
KOLOSKOVA ET AL.. (2020)
O
2v0+S
Me
p63/2
Pe
KOLOSKOVA ET AL. (2021)
Mc²
o²
V0e372
+
PC
1
THIS WORK
0
a²
Vo+uE
M
Decentralized Training. We consider systems (networks) where nodes are connected through a communication graph, and each node can efficiently communicate with its neigh- bors. In such decentralized systems, nodes represent ma- chines, and edges correspond to communication links.
2. Problem Setup and Background
In this section, we formally define our problem setup and provide an overview of relevant background.
Gossip averaging is robust communication protocol that efficiently and reliably propagates information across the decentralized network without relying on a central coor- dinator (Xiao & Boyd, 2004; Boyd et al., 2006; Nedic & Ozdaglar, 2009; Shi et al., 2014; Koloskova et al., 2020).
We study decentralized SCO problems, where the objective to minimize a convex loss function f Rd defined as follows:
M Σ 1=1
[(x) = M
(1(=)==
Concretely, suppose each machine in the network holds a vector zj E Rd, and our goal is to efficiently and robustly communicate the consensus I = x Σ; #6 to all of the machines in the network. Gossip averaging is sequential process towards doing so, where each machine computes a sequence {æih such that xf eventually converges to F for all i. At every gossip step, each node updates its vector as a weighted average of its neighbors:
where fi : Rdd + R represents the loss function on ma- chine i E ......,,. Dj is the local data distribution, and fi(,.)) the destance-dependent loss for a given sample z on machine i.
We focus on first-order optimization methods, where in round 1, each machine i samples =t ~ 'D., computes stochastic gradient estimate V fa zf), and uses it to up- date its local iterate æf. The method ultimately produces an output Foutput: and its performance is measured by the expected excess loss, defined as:
M
Poja
E[Exxess-Loss,
([Foupu))) f(=),,
where Psj > O if nodes and j are connected, and P E [0, M|MM is given gossip matrix which satisfies the following properties.
where x² E arg min f(x is minimizer of f. and the expectation is taken over the randomness of the samples.
Definition 2.4 (Gossip matrix). A gossip matrix P [0, 1] a is symmetric, doubly stochastic matrix. That is. P satisfies p = pT as well as P1 = 1 and 1 P = 1
Throughout, we make the following standard assumptions. Assumption 2.1 (Smoothness). Each function fs is L- smooth, i.e., for any x. y E Rdd we have:
These properties imply that (i) for any node i then {Pi hje[M]] is a weight vector (i.e., has positive entries which sum to 1), and that (ii) the consensus is preserved i.e.
L 1y - 2||2
f((v) S f(() + ff(()) - x)
2
Assumption 2.2 (Bounded noise variance). There exists constant o² such that for all x E Rd and E [M]:
that Vt, z = + MM 2 = + 1 x].
As is standard in the literature we shall assume that the matrix P is given and satisfies the above properties.
E (f 2) (f((2) 02.
Assumption 2.3 (Bounded heterogeneity). There exists constant 5² such that for all E Rdd
Note that gossip averaging can be written in matrix form as:
X X,P.
1 M
M -(<))
where X, = (at of
a R
3

---

Enhancing Parallelism in Decentralized SCO
A key characteristic of the gossip matrix is the spectral gap, reflecting the connectivity degree of the network topology. Definition 2.5 (Spectral gap). For a gossip matrix P with eigenvalues 1 = A1 A21 2 2 1 the spectral gap is defined as:
Interestingly, the parallelism bound differs based data hetenogeneity. In homogeneous setups (C 0), we can scale up to M < O(p2/2N3/4), whereas in heterogeneous settings (C > 0). the limit tightens to M I O(pN'/4), which can be significantly lower for sparse topologies. It is worth mentioning that Koloskova et al. (2021) enhanced this bound, by incorporating a gradient tracking mechanism, eliminating the dependence on Ç altogether.
= - |aal E (0, 1].
An important property of gossip averaging is its contractive effect on the distance from the average of local vectors.
Note that even for dense graph topologies, where p = 1, the rate in (3) does not match the centralized case. As we establish in Section 4, our approach bridges this gap, achiev- ing an error rate of O(a/ /VT/ + (Vo+ v This improvement increases the parallelism bound to M S Opv/N). Table 2 provides a comparison of convergence rates with prior work.
Property 2.6. Let X E R.xMM and define X = X x 11 Let P E RMMx be a gossip matrix with spectral gap p. Then,
IXP S XXP-X|B-s1- p]|I XIE
The above, along with the consensus-preserss ensures that iterative gossip averaging converges to the con- sensus (i.e., the average of the local vectors) exponentially fast. Notably, in complete graph topologies where م = 1, consensus is achieved in a single gossip step, effectively mimicking centralized behavior.
property,
3. The Pitfall of Decentralized SGD
Next, we discuss the D-SGD algorithm and outline its key limitation. Given the structure of decentralized topologies, the D-SGD algorithm naturally extends SGD. As described in Algorithm 1, each machine alternates between updating its local model weights using the standard SGD rule and exchanging information with its neighbors via gossip av- eraging. However, unlike in centralized Minibatch SGD, where all machines compute gradients at the same query points, decentralized training lacks immediate synchroniza- tion. Since gossip-based communication does not instantly enforce consensus (unless p = 1), local models diverge, and each machine evolves independently.
2.1. Parallelism Bounds
has been well established in the literature that the con- vergence rate of SGD for convex functions is given by Olo/VT+ + 1/TT,, where T is the number of iterations (Ne- mirovski et al., 2009; Agarwal et al., 2012). Assuming each iteration processes single sample, we have N = I total samples.
In distributed systems, computation is distributed across M machines, therefore accelerating the training process. With M machines, process N samples in just T N/M iterations. However, introduces a trade-off, as increasing M can eventually re- duce efficiency, as we show next.
This lack of synchronization introduces fundamental chal- lenge: gradient estimates at each node become biased with respect to the global consensus, affecting conver- gence analysis. As shown in (Koloskova et al., 2019), this bias is closely tied to the consensus distance E. == Mf Σn ||w] w, I| where w, = 1M ΣM wi represents the global average of local models. The consensus dis- tance quantifies the discrepancy between local models, and limited communication makes it challenging to minimize. This issue can be framed as a competition between the rate of consensus achievement and the rate at which local pa- rameters evolve. If all machines synchronized instantly, D-SGD would elosely resemble centralized Minibatch SGD, However, for any p < 1, perfect synchronization remains unattainable, necessitating to control and bound this bias.
mentioned, this parallelization
For centralized systems, Dekel et al. (2012) derived the following convergence rate for Mini-batch (Parallel) SGD:
1) E E|EceessLooss] = (VinT T (-
o
+ M
Thus, as long as M < OVVN) (ignoring o), we can in- crease M without degrading performance.
For decentralized systems, Koloskova et al. (2020) analyzed the Decentralized SGD (D-SGD) algorithm, obtaining the error rate:
To gain intuition, consider the D-SGD update rule under the simplifying assumption that the gradient variance across nodes is bounded: V,, == + ΣM llof gel < G2 for all A
2/3 1/3 + 2/3
+
> where S. = / Σ i of the global average of local stochastic gradients.
VMT
2/3T2/3
pT
22/3/113 + 2/3 2
M
0
(3) Using standard gossip averaging analysis and the SGD up- date rule, we can obtain the following recursion for the
V
N2/3
pN
4

---

Enhancing Parallelism in Decentralized SCO
Algorithm 1 Decentralized SGD (D-SGD)
Algorithm 2 Decentralized Anytime SGD (DAT-SGD)
Input: Initial point w1 E R., learning rate 17, gossip
1: Input: Initial iterate w1, learning rate n, gossip matrix
matrix P. number of rounds T.
P. number of rounds T, non-negative weights (01)22
Initialize w/ = w1 for all i E [M]]
Initialize w/ æ = w1 for all i [M]
for 1. = 1,...,7 do
3: for /. ,,...?? T do
for i E [M]] in parallel do
4: for i [MM] in parallel do
Sample zi ~ 'D and set gf = (f(..
5: Sample 2 ~ Dj and set sf V(((r),)))
w = w|- - n
6: Local updates
wi+1 = أ w "4tPo Po
M
7:
"i+ = w - nnaa
end for end for
8:
o 2+4 = autt
and x + at w
Gossip communication 1+
10:
w = Σ
j=1
M
b+
Pi
consensus distance:
11:
r Σ j=1 x Pij
M
M
12: end for
1
E
=
M
| - 01+11
13:
end for
M
0
|105+1 - -Wo+g 11?
using the update rule W141 = Wi 1y--y -79t, where 9: is a stochas- tic gradient estimate computed at the current iterate wt. In contrast, the Anytime SGD framework (Cutkosky, 2019) computes stochastic gradients at different query points specifically, the weighted average of past iterates.
M
M
1- P
Σ
11 (g6i) - -(wee ng:))l
M
-=1
< (1 2) E, + C. G2m22
(4)
Formally, given a sequence of non-negative weights {arte Anytime SGD generates two sequences, {wrh, and { according to the update rules:
P
>>0 0. Solving this recursion yields the bound E, < (12 for all 2 1. In practice, Koloskova et al. (2020) conducted more refined analysis, obtaining an improved bound of order 0(1²/p) This leads to overall error rate of O(1/TT - 7 + n²² p). Optimizing the learning rate by balancing these terms suggests choosing 7 S (p/T))/3, which in turn results in the (31/2//812/3 term in (3), ultimately limiting the parallelism bound. Ide- ally, if we could tighten the bound on the consensus distance, it would lead to direct improvement in this term. In the next section, we achieve this by introducing gradually shift- ing anchor points.
for some constant C'
W++1 = W/ 1704gt.
(5)
T141 = a'
at Wh-1:
2x +
(6)
a1
a1
where = W1, 0. = Et a, for all t > 0, and 01:0 == 0. Here, gr is an estimate of the gradient at the weighted average Z₁.
Cutkosky (2019) introduced the Anytime framework to en- sure that the query points converge to the optimal solution- unlike standard SGD, where iterates may not. It was shown that Anytime SGD achieves the same convergence rates as SGD for convex functions. However, the averaged query points {ar J exhibit greater stability, changing slower than the iterates themselves. As we show next, this approach also enables establishing a last-iterate convergence guarantee.
4. DAT-SGD: Decentralized Anytime SGD
In this section, we introduce DAT-SGD. We begin in Sec- tion 4.1 by discussing the Anytime SGD method, which serves as the foundation of our approach. Then, in Sec- tion 4.2, we extend this framework to the decentralized set- ting. Finally, in Section 4.3, we provide an intuitive analysis and a proof sketch of the convergence statement, highlight- ing how Anytime SGD enables to mitigate the consensus distance an idea we further elaborate on in Section 4.4.
4.2. Extension to the Decentralized Setup
Our approach extends Anytime SGD to the decentralized setting, as outlined in Algorithm 2. In round t, each machine performs the updates given in Equations (5) and (6) locally and, similar D-SGD, shares both its model weights, wf. and query points, xt. through gossip averaging.
4.1. Anytime SGD
The convergence of Algorithm 2 is established in Theo- rem 4.1, with the full proof deferred to Appendix B.
For this part, consider a single-machine machine setup. The widely studied SGD method generates a sequence of iterates {we)
5

---

Enhancing Parallelism in Decentralized SCO
Theorem 4.1. Under Assumptions 2. 1-2.,, consider Algo- rithm 2 with linear weights Oit t. and learning rate given by
related the average consensus distance between the query points, defined as
M Σ
M Σ
T== = M 1 Tell?, where Fg
M x
=
p² DIVM
Dt 2K T
min
24LT' K' /30T3/2' V
Since the query points evolve more gradually than the it- erates, we can derive tighter bound on r,, To illustrate this, we consider a simplified setting with uniform weights a2 = for all t and assume V S G for all 2 1, as in Section 3. Using gossip averaging for the query points and the Anytime averaging, we can show that:
where D == 11wl - x=1 K² == 5120L?, and 8²
20² 62 Then, for all T 2 1, the following bound holds:
0D1 VT
1 D
Lo
LD' T
-
pT
M
1 M
T++1
|
11+1112
1 where TT= == M EE=1" m/7-
1=1
1- Σ
Let N = MT be the total number of samples after '' it- erations. From Theorem 4.1, ignoring dependencies on T. D1, a and Ç, we obtain the convergence rate (11/V/ + M/pN). This implies that the asymptotic upper bound on parallelism is N). Beyond this, the second term of M/pN dominates, leading to decline in learning efficiency when increasing the number of machines. This bound repre- sents a significant improvement over the prior O(p1/2 parallelism limit (Koloskova et al., 2020; 2021).
| #1++11²
M
1 1- P M
Σ
M
(1- (x) - -ae) + [ - -0e++)
1 (1- +)
(vi-
i=1
(1 (1-2) 9) li+ pl2
C (E, + +G
for some constant C 0. Recall that E, satisfies its own recursion, as derived in Equation (4). Using the refined bound E, S (G22n2//p) we obtain:
In addition, we can establish the convergence of the local iterates, as follows. The proof is provided in Appendix B.1.
T41 $ (1 2 D -
C
G97²
+
+
Corollary 4.2. Under the same assumptions and parame- ter selections as in Theorem 4.1, the local iterate at each machine i E (1.....M) .Y satisfies:
ptz
P
G2n
< (1- 2 r + 2C'
P)
(8)
0212
E[f(xt)
Summing over t E [T] and rearranging terms, we can get the bound Σx, S O(n²/p²). Since the final error rate is proportional to the average consensus distance over time, P He, the resulting error is of order O(1nnT + n + T). Tuning the learning rate by setting 1/ S P yields the (1/)2l)) term, which enables enhanced parallelism.
TD VMT
VOO
MōD1 LD T
PT
p²T2
The additional last term does not affect the established upper bound on parallelism, which remains M- < OpvVN).
This simplified analysis provides intuition on how slowly changing query points improve the rate. Next, we present a more formal proof sketch capturing finer transition details.
Transient Iteration Complexity. A complementary met- ric to the parallelism bound is the transient iteration com- plexity, which quantifies how many iterations are needed before the convergence rate matches that of centralized SGD, i.e., when the a/ V MT term dominates (Pu et al., 2021). From Theorem 4. it follows that the transient iteration complexity of our method is O(M/p²) representing an im- provement over D-SGD by a factor of M For instance, this complexity corresponds to (M5 for the ring topology and ((M) for the exponential graph (Ying et al., 2021).
Proof Sketch of Theorem 4.1. As we show in Lemma B. the consensus query point sequence { is an (0t)r21 weighted average of the consensus iterates sequence [wx) Moreover, the average iterates sequence evolves similarly to Equation (5), following the update rule W = w. nagge Thus, the consensus sequences {#t) and [we)es1 align with the structure of Anytime SGD, allowing to leverage standard results applicable to Anytime SGD, Specifically, defining A. == (ā)( f*). it follows for all t > 1 that (cf. Lemma A.3):
4.3. Proof Sketch
To complement the analysis in Section 3, we first provide an intuitive analysis of the consensus distance. As formally shown in Appendices A and B, the bias in Anytime SGD is
D2 a. S n
n Σ | + 4nT Br, (9)
6

---

Enhancing Parallelism in Decentralized SCO
where By == E
- a 1 - vf(ž,) Focusing
4.4. Bounding the Bias
on the middle term, we show using standard arguments that:
A central part of our analysis bounding the bias introduced by local model differences. The bias bound is formally stated in Lemma 4.3, and the complete proof can be found in Appendix B.2. A brief proof sketch is provided below.
30 + Eg
M
Plugging this into Equation (9) allows us to derive the fol- lowing bound:
Lemma 4.3. Consider the setting in Theorem 4.1 and let 9t Mi Ei= gi and H, == 31 Ei=ı bi denote the aver- age gradient and query point across machines at round t, respectively. Then, for linear weights or = t, and a learning rate bounded as rj S K the following bound holds:
D
30'n1 1
41
+
Σ
a +
BT
M
T
+ 3n
Σ
a
(10)
T B7 - E
T K²0212
B
-VS(E)]
Σ
a
2
2pa
key component in our proof is bounding Br, which is essentially the sum of weighted squared biases. As we show in Section 4.4, this term is bounded as follows:
T=1
where we recall that K2 = 512012 and 52 = 20 + C2
Proof Sketch. By Jensen's inequality and the smoothness of each fi, we can bound each term in the sum as follows:
12
BT S
2pa
M
Therefore, from Equation (10), we get:
B vf(++)) S
E
V f++-))l
M
D2
30'n1
T
T
T T
1=1
A1:A1 S
+
Σ
a?
r,2
11
M
E E
-
7=1
T=1
M
+ 3n
2 E V
(1+
(11)
As previously defined, let I, note the average consensus distance of the query points at round t. Thus,
E 12 de-
For the last sum, the smoothness of f implies that [+)(()) < 2x( (r) for all E Rd, yielding:
T Σ ([
S 2L
Σ o 4, S 4L Σ Ar
B S L
(13)
T=1
7=1
where the last inequality follows from a? = 72 201 Substituting this bound into (1I) and recalling that 1 <
Our objective is therefore to bound r, for every T E [T]. Using standard gossip averaging analysis and the query points averaging, we derive the following recursion for Iı:
24L7 we obtain:
aI A.
S
20
n
T
ar
1T
Σ
T
a
Tei S (1 (1- r.
()
48
(E.
(14)
11
M
A
1 T
M recalling that E, 1/ Di=
E Elw wr and V, =
+
(12)
2T
3 EE Bllgf le represent the average consensus dis- tances of the iterates and gradients at round t, respectively, and using 6, = _. Notably, E, satisfies its own recursion (see Lemma C.4):
T=1
Observe that = A, follows the structure a. < +
I ax, Vt E [T], which implies that a I 2b for all
2T
t E
Ti (see Lemma D.3). In particular, for t = T, we get:
2770a V E S (1 -1-2 = (1-
2D 1
60 6 Σ
8K202n2T
AT
2 a +
2
P
M
Solving this recursion yields the following for all E [T]:
Dividing by 01.7, noting that ΣT of < T for linear 01.7 weights, and appropriately tuning the learning rate con- cludes the proof.
E, S 2nj 2 t-1
(1 P 1-1-7
V-
P
2
7

---

Enhancing Parallelism in Decentralized SCO
Substituting this back into (14) gives:
0²=1, 2==1
o²=1, (==10
10 10
10-1
T++1 S (1 (1-2)r
10
10-2
10-3
10
10-4
4nf² 4n
v +
2 1-1
Σ
1
0
1-1-r
V
10
10-3
2
10
10-0
9
25
49
100
4
9
25
49
100
Number Machines (M)
Number of Machines (M)
In Lemma C.2, we show that V, I 55 + 10L21, for all t T Plugging this bound, noting that for linear weights 0. = O11), ), and using some algebra, we obtain:
o²=10, 2==
0²=10, ===10
10
10
10-2
T++1 1 (I-x+ GTG""
10
10-3
Tτ
10-1
10-4
Ki
10-5
10-5
t-1
2 n:3
10-1
10-
+
Σ 7=1
(1
(x))-1--T
9
25
49
100
4
25
49
100
x²
Number Machines (M)
Number of Machines (M)
DAT-SGD (Ringl
DAT-SGD (Torus)
DAT-SGD (Exp.)
where - - and = We have now derived recursion for I that no longer depends on E, or V,, For a sufficiently small learning rate, specifically n K. this recursion can be explicitly solved, yielding:
D-SGD (Ring)
D-SGD (Torus)
D-SGD (Exp.)
Figure I. Final error on synthetic least squares problem for dif- ferent numbers of machines and various gradient noise variance (o²) and heterogencity ((3) levels over ring, torus, and expo- nential graph topologies. We plot 1 Ex=1 |aa - x I|? and M
202
2
(
10211²
T
37 DM |lob - x²112 for DAT-SGD and D-SGD, respectively.
Injecting this bound into (13) yields the result:
T
120212
and 1-peer exponential graph (Ying et al., 2021). The exponential graph is a fast-mixing topology for which 1/p = Olog M). For each method and topology, we perform grid search over the learning rate n {0.0001, 0.0005, 0.001, 0.005, 0.01, 0.05, 0.1} and select the value that yields the lowest error after 100K iterations. For DAT-SGD, we use constant weights
BT S L
Σ
-²
=
p²
5. Experiments
1 for all t.
In this section, we empirically evaluate our method on both a synthetic least squares problem and an image classification task. All experiments are conducted using three random seeds, and we report the averaged results.
In Figure 1, we plot the final error as a function of the number of machines, across four configurations defined by o, S {1, 10), with different colors indicating the underly- ing topology. For D-SGD, we observe that performance de- grades on the ring and torus topologies starting from M = 4 and M = 9, respectively, while it remains relatively stable on the 1-peer exponential graph. In contrast, our method improves with larger M: performance steadily improves on the torus and exponential graphs, and performs better on the ring topology up M = -25 before deteriorating. This suggests that, beyond certain threshold (between M 25 and 49), the network-depender dependent error term (which scales as (1/pTT) = ((M2/T) for the ring) becomes dominant. Overall, the results align with our theoretical findings, as DAT-SGD enables performance improvement for larger M. We provide complete convergence curves in Appendix E.
5.1. Least Squares on Synthetic Data
We begin with a synthetic least squares problem to il- lustrate key theoretical properties of our algorithm. For each machine, the local objective function is defined as fa(z) - |A, - bill? where A, E Radxd is drawn from standard multivariate normal distribution. The targets vec- tor is set as 6, = Az - 6;), where zz ~ ~O, (a) is sampled once per configuration, and 6, ~ ~0, & in- troduces heterogeneity across machines! To incorporate stochasticity, we add Gaussian noise { ~ (00, 2² Ta) when querying local gradients, resulting in the noisy gradient estimate (z) + E. In our experiments, we set d = 50.
5.2. Image Classification with a Neural Network
We compare our method with D-SGD, evaluating per- formance across three network topologies: ring, torus,
Next, we evaluate our method on the Fashion MNIST (Xiao et al., 2017) image classification task using the LeNet (Le- Cun et al., 1998) architecture. The data is partitioned among
'eere, 5² quantifies heterogeneity at the optimum.
8

---

Enhancing Parallelism in Decentralized SCO
M=8, a=0.1
M=8, a=10
Ring, a=0.1
90
90
Accuracy
80
Accuracy
90
DAT-SGD
DSGD
85
88
D2
Final Accuracy
60
87
80
50
50
100
150
200
50
100
150
200
Epoch
Epoch
75
M=16, 0=0.1
M=16, 0=
90
70
Accuracy
80
Accuracy
90
65
89
70
60
66
16
32
50
86
Number of Machines (M)
50
100
150
200
50
100 Epoch
150 200
Epoch
DAT-SGD (Ring)
DSGD (Ring)
D2 (Ring)
Figure 3. Final test accuracy on Fashion MNIST for varying num- ber of machines the ring topology with heterogencous data.
DAT-SGD (Base-2)
DSGD (Base-2)
D2 (Base-2)
Figure 2. Test accuracy on Fashion MNIST for different numbers of machines (across rows) and varying heterogeneity levels (across columns) on the ring and the Base-2 graph topologies.
heterogeneous data (a = 0.1). Notably, the largest accu- racy drop for DAT-SGD occurs between = 8 and 16, whereas D-SGD and D2 degrade most between M 4 and 8, demonstrating our claim of improved parallelism.
workers following a Dirichlet distribution with parameter a, which controls the heterogeneity level (Hsu al., 2019).
We compare our method against D-SGD and D2 (Tang et al., 2018b), decentralized optimization method specifically designed to improve robustness to data heterogeneity. Exper- iments are performed on the ring topology and the Base-2 Graph (Takezawa et al., 2023)-a time-varying, state-of-the- art topology for decentralized learning. For our method and D-SGD, we use momentum with parameter 3 0.9. For each method and topology, the learning rate was selected via grid search over 1) (0.001,0.01 0.13.
6. Conclusion and Future Work
In this work, we presented DAT-SGD, a simple yet powerful approach to decentralized SCO that raises the parallelism threshold, enabling to increase the number of machines in the network while maintaining linear speed-up. This is achieved by effectively mitigating the consensus distance us- ing the Anytime SGD mechanism, which computes stochas- tic gradients at gradually changing query points, thereby limiting local model divergence.
Unlike the synthetic least squares problem, this task is non- convex. Following the heuristic proposed by Dahan & Levy (2025), we adopt momentum-like update for Anytime averaging of the form x++1 = 7h + (1 - 7)w,, using a fixed value of ? = 0.9. This choice was shown enhance training stability and adaptability in non-convex landscapes.
Several promising directions emerge from our work. One is integrating our method with gradient tracking, which has been shown to remove dependence on data heterogeneity (Koloskova et al., 2021). Moreover, we assume the gossip matrix is symmetric and doubly stochastic, allowing to use Property 2.6 for a clear and simple analysis. Extending our results to asymmetric or row/column stochastic matrices, as in, e.g., (Assran et al., 2019), remains an open problem. Finally, establishing convergence bounds in the non-convex setting a compelling challenge for future research.
Figure 2 depicts the test accuracy for M 8 and 16 ma- chines under heterogeneous (a = 0.1) and nearly homoge- neous (a = 10) data, with different colors indicating the compared methods. In the heterogeneous case, our method consistently outperforms the baselines across both topolo- gies, with results on the ring matching (for M 8) or nearly matching (for Md = 16) those of the baselines on the well-connected Base-2 Graph. Conversely, and perhaps unexpectedly, under homogeneous data, D-SGD and 2 achieve better performance, motivating further investigation into this gap across data regimes in non-convex settings. In Figure 3, similar to Figure/ 1, we show the final accuracy for different numbers machines on the ring topology with
Acknowledgments
We thank the reviewers for their valuable comments. This research was partially supported by Israel PBC-VATAT, by the Technion Artificial Intelligence Hub (Tech.Al), and by the Israel Science Foundation (grant No. 3109/24).

---

Enhancing Parallelism in Decentralized SCO
Impact Statement
Ene, A., Nguyen, H. L., and Vladu, A. Adaptive gradient methods for constrained convex optimization and varia- tional inequalities. In Proceedings of the AAAI Confer- ence on Artificial Intelligence, volume 35, pp. 7314-7321, 2021.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which feel must be specifically highlighted here.
He, L.., Karimireddy, S. P., and Jaggi, M. Byzantine-robust decentralized learning via clippedgossip. arXiv preprint arXiv:2202.01 2022.
References
Agarwal, A., Bartlett, P. L., Ravikumar, P., and Wainwright, M. J. thoormation-theoreiicc lower bounds on the ora- cle complexity of stochastic convex optimization. IEEE Transactions on Information Theory, 5865):3235-3249, 2012.
Hsu, T.-M. H.,, Qi, H., and Brown, M. Measuring the effects of non-identical data distribution for federated visual clas- sification. arXiv preprint arXiv: (et.:::999900333000 2019.
Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., et al. Advances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2)11-210 2021.
Antonakopoulos, K., Vu, D. Q.. Cevher, V., Levy, K., and Mertikopoulos, P. Undergrad: A universal black-box optimization method with almost dimension-free conver- gence rate guarantees. In International Conference on Machine Learning, pp. 772-795. PMLR, 2022.
Kavis, A., Levy, K. Y., Bach, F., and Cevher, V. Unixgrad: universal, adaptive algorithm with optimal guarantees for constrained optimization. Advances in neural information processing systems, 32, 2019.
Assran, M., Loizou, N., Ballas, N., and Rabbat, M. Stochas- tic gradient push for distributed deep learning. In Inter- national Conference on Machine Learning, pp. 344-353. PMLR, 2019.
Kempe, D., Dobra, A., and Gehrke, J. Gossip-based com-
Aviv, R. Z., Hakimi, I., Schuster, A., and Levy, K. Y. Asyn- chronous distributed learning: Adapting to gradient de- lays without prior knowledge. In International Confer- ence on Machine Learning, pp. 436-445. PMLR, 2021.
putation of aggregate information. In 44th Annual IEEE Symposium Foundations of Computer Science, 2003.
Proceedings. pp. 482-491. IEEE, 2003.
Koloskova, A., Stich, S., and Jaggi, M. Decentralized stochastic optimization and gossip algorithms with com- pressed communication. In International Conference on Machine Learning, pp. 3478 3487. PMLR, 2019.
Boyd, S., Ghosh, A., Prabhakar, B., and Shah, D. Random- ized gossip algorithms. IEEE transactions on information theory, 52(6):2508-253 2530, 2006.
Cutkosky, A. Anytime online-to to- tos-tto--bbte batch, optimism and accel- eration. In International conference on machine learning, pp. 1446-1454. PMLR, 2019.
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 Machine Learning, pp. 5381-5188 53933. PMLR, 2020.
Dahan, T. and Levy, K. Y. LowcalSGD: Slow Query Points Improve Local-SGD for Stochastic Convex Optimiza- tion. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https: //openreview net/ forum? 2tw--2991lee200 RellR22662 6z.
Koloskova, A., Lin, T., and Stich, S. U. An improved analysis of gradient tracking for decentralized machine learning. Advances in Neural Information Processing Systems, 34:1 34:11422-11435 2021.
Dahan, T. and Levy, K. Y. Do Stochastic, Feel Noiseless: Stable Stochastic Optimization via Double Momentum Mechanism. In The Thirteenth International Conference on Learning Representations, 2025. URL https:// openreview. nwt. wwwp:oommmddcnn 3bN.
Kong, L., Lin, T., Koloskova, A., Jaggi. M., and Stich, S. Consensus control for decentralized deep learning. In International Conference on Machine Learning, pp- 5686-5696. PMLR, 2021.
LeCun, Y., Bottou, L.,, Bengio, Y., and Haffner, P. Gradient- based learning applied to document recognition. Proceed- ings of the IEEE, 86(1 1) 12:2878 2324, 1998.
Dekel, O., Bachhabc R., Shamir, O., and Xiao, L. Optimal distributed online prediction using mini-batches. Journal of Machine Learning Research, 13(1), 2012.
Li, M., Andersen, D. G., Smola, A. J., and Yu, K. Com- munication efficient distributed machine learning with the parameter server. Advances in Neural Information Processing Systems, 27, 2014.
Di Lorenzo, P. and Scutari, G. Next: In-network nonconvex optimization. IEEE Transactions on Signal and Informa- tion Processing over Networks, 2(2):120-136, 2016.
10

---

Enhancing Parallelism in Decentralized SCO
Li, S., Zhou, T., Tian, X., and Tao, D. Learning to collabo- rate in decentralized learning of personalized models. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 9766-9775 2022.
Tang, H., Gan, S., Zhang, C., Zhang, T., and Liu, J. Com- munication compression for decentralized training. Ad- vances in Neural Information Processing Systems, 31, 2018a.
Li, X., Yang, W., Wang, S., and Zhang, Z. Communication- efficient local decentralized sgd methods. arXiv preprint arXiv: 1e0::19900000900 126, 2019.
Tang, H., Lian, X., Yan, M., Zhang, C., and Liu, J. D Decentralized training decentralized data. In Interna- tional Conference Machine Learning, pp. 4848-4855 PMLR, 2018b.
Lian, X., Zhang, C., Zhang, H., Hsieh, C.-J., Zhang, W., and Liu, J. Can decentralized algorithms outperform study for decentralized parallel stochastic gradient descent. Advances in neural information processing systems, 30, 2017.
Tsitsiklis, J. N. Problems in decentralized decision making and computation. PhD thesis, Massachusetts Institute of Technology. 1984.
centralized algorithms?
Verbraeken, J., Wolting, M., Katzy, J., Kloppenburg. J., Ver- belen, T., and Rellermeyer, S. survey on distributed machine learning. Acm computing surveys (csur), 53(2):
Lu, Y. and De Sa, C. Optimal complexity in decentralized training. In International conference on machine learning, pp. 7111-7123. PMLR, 2021.
1-33, 2020.
McMahan, B., Moore, E.,, Ramage, D., Hampson, S., and y Arcas, B. A. Communication-efficceet learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017.
Xiao, H., Rasul, K., and Vollgraf, R. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv: 1 1708.07747 2017.
Xiao, L. and Boyd, S. Fast linear iterations for distributed averaging. Systems & Control Letters, 53(1):65-78, 2004.
Nedic, A. and Ozdaglar, A. Distributed subgradient meth- ods for multi-agent optimization. IEEE Transactions on Automatic Control, 54(1):48-66 61, 2009.
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, 84:13975-1395 2021.
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.
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.
Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A. Ro- bust stochastic approximation approach to stochastic pro- gramming. SIAM Journal on optimization, 19(4) 1609, 2009.
Nemirovski, A. S. and Yudin, D. B. Problem complexity and method efficiency in optimization. 1983.
Pu, and Nedić, A. Distributed stochastic gradient tracking methods. Mathematical ProceeaaaPPPrrr Programming, (7(()):49-45)) 2021.
S., Olshevsky, A., and Paschalidis, I. C. A sharp estimate on the transient time of distributed stochastic gradient descent. IEEE Transactions on Automatic Control, 67 (11):5900-5915, 2021.
Shi, W., Ling, Q. Yuan, K., Wu, G., and Yin, W. On the lin- ear convergence the admm in decentralized consensus optimization. IEEE Transactions Signal Processing, 6777)1150-11611, 2014.
Takezawa, Y., Sato, R., Bao, H., Niwa, K., and Yamada, M. Beyond exponential graph: coammuncaation-fffccin topologies for decentralized learning via finite-tima con- vergence. Advances in Neural Information Processing Systems, 36:76692-76711 17, 2023.

---

Enhancing Parallelism in Decentralized SCO
A. Anytime SGD Analysis
In this section, we discuss key properties of Anytime SGD with biased gradients. The main result Lemma A.3, which will later be adapted to the decentralized, gossip-base based communication setup Appendix B
For initial iterate wh IRd, learning and ( defined by the update rules:
0, and non-negative weights {01) consider the sequences {w)) h22
Wc+1 Wt 1J049tt
(15)
01:11
Ot
F++1
De
+
w++1
with 21 = u1
(16)
0/1
014
Here, 9t is biased estimate of the gradient of some function f Zt- The following result mimics the gradient inequality for the (21) averages.
Lemma A.1 (Cutkosky, 2019; Theorem 1, Dahan & Levy, 2024). Let f R2 + RR be a convex function with global minimum f = f(x"), and let the sequence {arhe21 be defined as in Equation (16). Then, for any t 2 1, the following holds:
I and - f Σ a V (w, - x²)
Next, we present regret bound for online gradient descent with weighted gradients. Lemma A.2 (Cutkosky, 2019; Lemma 2, Dahan & Levy, 2024). Consider the update rule in Equation (15). Then, for all
I 12 1, it holds that:
Σ aagf T (w, x²)² |w| xx 11
1 2
1
2m
The following result is fundamental to our analysis and plays key role in establishing our main proof. The analysis closely follows that of Dahan & Levy (2024) and is included here for completeness; see Appendix F therein for further details.
Lemma A.3. For the sequences (wehe2 and {x)121 defined in Equations (15) and (16), the following holds for any 2 1:
[1 x=1
T
T
(f(x)) - f'1
17
Σ a T=1
g 12 + +nT Σ T=1
B Egr Vf(x))11
1
Proof. Lemma A.1 implies the following:
an (
Σ ar (f(x)) - x²)
E
Σ
a+d T
/ (w- -
-x²) x²)
+E Σ ar (Vf(x)) 9+)T (w- - x²)
||11
11
17
Σ
a
E
11
Σ
E ar (VS(s+) - gt) (w- =")
(17)
21
2
where the last inequality follows from Lemma A.2. Every element in the rightmost sum can be bounded using Cauchy- Schwarz inequality and Young's 's inequality, a b 1
||a||
+ 0 [|6]], which holds for any > 0, yielding: 2
20
E a (VS(x,) - )r) (w, x*)
E ar (VS(x;) - Egg)) (wr - x¹)]
< EE Ja, ||gg, vf(x=>)] ||| ||w, x111]
0
B| Eg- ff(2))11 + =Ell,, - x² x11
(18)
20
where the first equality follows from the law of total expectation.
12

---

Enhancing Parallelism in Decentralized SCO
Substituting (18) into (17) gives:
01 (f(x))
-
||-1
1²
+
11
a
B1g 11+
E Eg- - vx(==)]1
0 t +
E |0, x²1
211
2
20
2 -=1
r=1
==1
|/-1
x1
11
a
1
112
1
Bg. a
(x))))] 0
E [0,,, x=1
2n
2
20
2
where the last incquality follows from the last three terms being monotonically increasing with t. Lemma of Dahan & Levy (2024) guarantees that for sequences (wth121 and {a] as defined in Equations (15) and (16), the following holds:
T
T + 1 Σ
Σ w we x²11 S 2T
2T || - x²11 2 + 2T'n2
Σ
a Bg V {x(+))1?
which in turn implies that for 0 = bn/T
1.
T 1101 x²1 + (7 + MT
1
(1,B(f(z1) - f1
+ OT
Σ
a 9
27
T
1
+
+ 8012T22
a Eg, vf(=>)11
28
r=1
3
w1 - 1=
31
T
Blgge 12 + 4n/T Σ a Bf Eg- {z()))|
4n
4
==1
|w]
x 11
T
7
a
Blgg ge 1|
4nyT Σ
R Bg, vs(x))]1
1
thus concluding the proof.
B. Proof of Theorem 4.1
In this section, we prove our main result. To simplify the presentation and analysis, we first introduce some notations:
1
X, (at
xt a E d
X, X,
11
(Te 5t
F.) E R
M
1
W. = (w!
wM E RdxM
W, = W. 11
=(w;
=
i w E Rdx
MM-
G. = (gt
gi
g. E R
G = G M
11 = (ge
gt
g. E Rd
M with 5, M Σ 1 o W4
EM wi. and Ø. /े M gt-
Denoting 8 a...
ن our Decentralized Anytime SGD algorithm can be expressed using matrix notation follows:
W W = W na
Local update and averaging:
Xx+3 = (1 - 6)) X₂ + &.W, ++
Wi+1= -W+F3
Gossip communication:
Xo+1 = X P.
We also define the expected average distance between local elements and their mean, commonly referred to as the consensus distance. Specifically, we define consensus distances for the iterates, the query points (i.e., the (0t) -weighted iterates),
13

---

Enhancing Parallelism in Decentralized SCO
and the gradients:
M
P2 =
0t - T/
R3 X; Xellz
M
M
1=1
M
B| wf w/ 1| =
1/
BlllW Will
M
M
i=1
V M
Ellgt
9:
// M
1
B
First, we establish that the sequence of query points average over machines {0t indeed an fatht1- weeighted average of the sequence of iterates average over machines fwx) This allows us to apply the results from Appendix on Anytime SGD to analyze the consensus iterates.
Lemma B.1. The sequence {7thez an weighted average of the sequence (wther
Proof. Using matrix notation and the linearity of averaging, we have:
X = X X
011-11
X2 +
Olt
W
01:t-1
X,
Ot
W
W
01--1
X, + at
We-
a1:t
01:
O'
01:
a1d
where the second and fourth equalities follow from Lemma D.I, implying that gossip communication preserves averages.
Next, we establish the convergence of Algorithm 2, as stated in Theorem 4.1, which we restate here for ease of reference.
Theorem 4.1. Under Assumptions 2.1-2.3, consider Algorithu with linear weights a = and learning rate given by
1 p² DIVM
D1 P 2Kō T
min
24TT
K V3013/2
where DJ= = =|l1 x²1 K2 = 5120T?, and 02 = 20 + 2 Then, for all
2 1, the following bound holds:
oDi
3/2 Lō
LD$
- -
+
VMT
pT
T
where 5T == M Em 2/7-
Proof. For any E [T], define A, = E[f(E,)- f*) We analyze the consensus iterates, which (according to Lemma B.
follow the structure of Anytime SGD as defined in Equations (15) and (16), namely.
o++1 w. nong,, and 5441 (1 5.) + 5,0441
Therefore, by Lemma A.3, we have:
[1 - 121
T
T 4n/7
A. <
a |r
2
a EE VS(x+)12
"
DJ
+
O g-
1?
+4nT
Br
(19)
(A)
where Br = -T aFElEEg V)( and we also used wh w1-
14

---

Enhancing Parallelism in Decentralized SCO
Bounding (A). We focus on E Elgg I|?. By adding and subtracting Eg, and (z( and applying the inequality
||a + + ell s 3 ||aa] + 3 |b6122 + 3 ||c|? we obtain:
Bllg.1| 112 = Bllgr - Eg. + Eg, V[(E.)
S 3B Eg + Eg |=(=))|| (
s 3
+ 3IE [Bg, +3
M
[[(M] where the last inequality holds because {st - V[((++)) [E(M]
are independent, zero-mean, and have variance at most o²:
1 M
M Σ
o² M
B Eg 2
Σ
(0)
v(((E)))
E 9
M
M 1=1
1=1
Thus, (A) is bounded as follows,
T
302 T
T Σ
Σ
101
Σ
7 + 3BT + 3
V
M
1=1
Plugging this bound back into (19), we get:
D2
30
T
07 + 3V +3 +3 <
01 S
+ 1)
+ 4n/T Vir
M
Dt
30 11
T
T
Σ
a + (3n + 4n/) BT + 3n
Vf
M
r=1
D2
30 1)
T
T
0 + T By + 3n
E
V f
(20)
17
M
For linear weights a, = and learning rate upper bounded by e² Lemma 4.3 provides the following bound on By (see proof in Appendix B.2 below):
K20212 T 2p
By S
Σ a
1=1
Substituting this bound back to Equation (20), obtain:
Di_
30 n
4K 2K200
T
a <
Σ a +
a + 3n Σ
n M
p²
The rightmost term is be bounded as follows:
T
Σ (f < 2L
Σ
az A < 4L Σ
a1 A
T=1
where the first inequality follows from Lemma D.2 (i.e,,
|f(E,)| 12 22(((( f)),, and the second inequality arises
from af = 12 < 1(L 11) = 201.. Therefore,
D
3
1
T
4 ST
T
A
a7
a 12L
a1: A
π
M
p²
T=1
1=1
D3
302n 1
T
4K 2 2
3T
T
1
0
a1 Dr
7
M
p
2T
15

---

Enhancing Parallelism in Decentralized SCO
where the last inequality holds true for norn) n 212T"
Applying Lemma D.3 with ar = =014, and
Di
30
0
M
-=
4K20'n T D of yields (for t = T):
aIT S 26
2D}
6
8K
M Σ
a
p
2D}
Go G
8K 8K202
where the second inequality holds as
a = ' 1 v T3, Thus, employing Lemma D.6 with A -22 B G
M
8k² and 1/1 min 241T
C'
get:
p²
A + 2V
AT v
AB + 243//0214
7
< 2D
24LT +
K p²
12D4o2T
+ 2 (2D7)3/4
(SK3Ø2T4)
1/4
M
pz
4 4V3D/0T0/2
4 4/22
3/2 VKōT
2KD2
4 +
VM
Finally, dividing by a1.T
T(++1)
T
we obtain the result as:
2
2
Sv3D10 + 8V20 VKō
96LD?
4KD;
AT A - 1
VMT
PT
T
P²T2
Dio
D2/2 VL +C)
+ LD$
LD$
o
+
VMT
pT
T
p²T?
B.1. Proof Corollary 4.2
Next, we demonstrate the convergence of the local iterates.
Proof. Let [M]. By the smoothness of the f. it holds that:
[[f((/)) - f') B (( - f(ār)( -[((r) - f*]
Vf(rr) (af Fr) +
| 2r|
+ +E(f(Tr) f*1
0 0+L E p কт 1| B(f((r) fr)
E
20
2
where the last inequality holds for any 0 > 0 due to Young's 's inequality, a T < 20 ||||2 + b|| Setting & = L and using
Lemma D.2 to upper bound ||V (ā || by 2T( )*)), we get:
1 2L
E[f(a)) =
E | [7 11 + LE |aaj Fr
+ E[f((rr f
< ( - 1 + LE
| Trl""
M
s (x)) - f4 + L
E || 12
2EI 14] + LMTT
16

---

Enhancing Parallelism in Decentralized SCO
Using Lemma C.3, which applies under the conditions of Theorem 4.1, can bound Pr by 256052n /p", where x² == 2x + 5² In addition, the learning rate in Theorem 4.1 satisfies 17² S Dipp /2p/2 where K = V5120L.
Therefore, we obtain:
B[(())) M & ( - 1 + 2560LM
8V5MD1ō
< 2E M
p
T2T2
Plugging the bound on [[)(TT) [*]] from Theorem 4.1 establishes the result:
[[((x)) f*) S 16v3Dio 16 VKō VMT +
192LD
8KD.
8V3MD
PT
T
PPT2
PPT2
D10
D VTo
LDJ MD PºT²
=
VMT
+
pT
+
T
+
In terms the total of samples N = MT, the established rate is given by:
Dio
M
MLD? N
Mā p²
-(f(+t)-f1 - =o
+
VN
pN
Therefore, ignoring the dependence on L, D1, a and (i.e., assuming they all equal 1), the parallelism bound (i.c., the maximal asymptotic M for which the rate is O(1/VN)) is:
M S O min { (VVN, NN,
N.W.NNNN..... .1... =
=
B.2. Proof of Lemma 4.3
Proof. We aim to prove that:
T o Bg.
K2022² T 2p
Σ o
Br = E
<
where K² = 5120L and Ø² == 20 + c
Focusing on Egg - f(++)) and using the convexity of 11-11 we apply Jensen's 's inequality to obtain:
E Bgg - vf(E,)] = E
M (f(( vf((E)))
1 M
E E([[f((at) v)({=))1?
M
L M
E 2 Zx
M
I I
where the second inequality follows from the smoothness of ft. Using Lemma C.3, which applies specifically to linear weights a, t and learning rate bounded
p²
bound r, and derive corresponding bound for By:
8/80L
T By Σ -
2560L233 pt
T 2
K20212
< I Σ TT <
Σ T=1
Σ a
2p
T=1
T=1
which concludes the proof.
17

---

Enhancing Parallelism in Decentralized SCO
C. Consensus Recursion Analysis
In this section, we analyze the consensus distances rr, S. and v., We begin by observing that Ty follows a recursive relation (Equation (24)), where _ depends not only on I' but also on E, and vr, Similarly, E, satisfies its own recursion, with E depending on E, and , (Lemma C.4).
To simplify the analysis, we first solve the recursion for E. allowing us to express Ie in terms of v alone, eliminating the dependence on E, (Lemma C.I). Finally, in Lemma C.2, we bound vr in terms of the problem parameters (a and () and I,, enabling us to explicitly solve the recursion for I' (Lemma C.3).
C.1. Consensus of the Query Points
The next result establishes a recursion for the consensus distance of the query points X..
Lemma C.1. For all 2 1, the consensus distance of the query points (i.e., averaged iterates) Ft satisfies the following recursion:
4n2a,88
2 f
r, (1-2)r,-
To+1
V
P
2
7=1
Proof. The gossip averaging of the query points leads to the following inequality:
MT E1 X x P X x+ 11 s (1 p)E|Ix,+ X1+1112.
(21)
where we used Lemma D.I, stating that X P = 3 and the mixing property of the gossip matrix (Property 2.6).
Substituting the query points averaging. X = (1 - 5, X; + 6, and using ||a + b1I2 - (1+0-1) +11+++)1++))))))))) ||b|2 (which holds for any 3 > 0), we obtain:
MT S (1- - p) 4+3 - X 11:
= (1 - [] 5,)X, + 8, W. ((1 8,) + S.W, ++ 5, ))
$ (1 p) [1+ (1- 6.) X.11 + p) (1+ 13+ Wo+gl1
< (1 - p) (1+ MT, + (1 () + 3)08 W 4+ W ++ 11
(22)
where the last inequality follows from (1- < 1. Focusing on (+) and plugging the iterate update rule, we have for all >> 0:
BIIW 1+7 Wo+! 11:- EllWW, - na -
(W, - G1
EllWe Well + (1 (1+7) f -Gll?
1
ME, +11 (1+7)
(23)
Substituting (23) into (22), setting 3 2/p and 7- 1, and dividing by M, we get:
T (1 (1-pp) p) (1+ S4 () I + (1 p) 2) &² (2E, + 2n - (1-?) r + 46 (E.+ + 122
(24)
where in the second inequality we used (1- p) -1 - and (1 -
Note that we derived recursion for T,, which also involves E, The consensus distance of the iterates, E,, satisfies its own
18

---

Enhancing Parallelism in Decentralized SCO
recursion stated in Lemma C.4, from which an explicit bound is provided in Lemma C.5. Substituting this bound yields:
P T++1 - (1-2) Pt
46
2
2
t-1
P
v + 87
P
2
7=1
(1 r
P 2
2
Σ
1
P
1-1-
v
(25)
P
p
==1
thus concluding the proof.
Note that the sequence I...., v,, appears in the recursion given Lemma C.I. We next provide an upper bound on Vr in terms of ,, which will enable us derive an explicit bound for T
Lemma C.2. For every 2 1, M S 5 (2o² + 10L2r,
Proof. Using E un|12= & En ||un]] we have:
M
V.
Egi - 9rl12
M
E Egi Egg + Egi + Eg. 1g:- Vz.))))) + Vf((a.) VS(z)) V(
M
1=1
(Ellg 13g:11 + 1g Ege 1E (
El
-
(26)
Next, we individually bound each sum.
Bounding 1
Ei
Ellgi Egill
By the bounded variance assumption, it holds that:
M
1 M
M B - (
M
Blgg
Egil
<
02
M
M
M
Bounding Elg Eg. 1|2. Since of Egi are independent, zero mean, and have variance bounded by o², it follows that:
M Ellgi
0²
E ge
1E =
E
(of
Egi)
Eggil <
M
M
M
Bounding M MM El Vf(
By the smoothness of f.r
M
M
L M
B Egg - 2f())))1 = -
<
Σ Blaa -211== L
M
M
M
Bounding Ege
12 2
By Jensen's inequality and the smoothness of each fs. have:
M
M
E Ege vz(x)) = E
Σ
(Vf((z))
<
Σ
E (V((())) - vf(a)) s L'T,
M
M
1=1
19

---

Enhancing Parallelism in Decentralized SCO
Bounding * ΣM
(. (.))
By the heterogeneity assumption (Assumption 2.3),
1
E (())) - v
M
Substituting these bounds back into Equation (26) implies the result as,
V S 5 02 + o²
+ 55) S (202 + + 10L
M
Using this, we now derive an explicit bound for rú, specifically for linear weights and a sufficiently small learning rate. Lemma C.3. For linear weights {ar: = 122 and a learning rate 1) S
the consensus distance of the query points 8/80L'
I' is bounded as:
256002r1²
p
where 5² = 20² + c
Proof. First, observe that for linear weights 04 = I, we have 01
== ((++1)
which implies that for all 1:
at and a; =
2t
8
S
01
1+1
1 1+1 1
Thus, from Lemma C.I, we get:
Te+1 S (1 ()
4naz88
2 f-1
0
1-1-
2)
r, +
V +
1/-
p
P
2
1-1
$ (1
P Te +
16n
1
+
Σ
p)
1-1-T
V
2
p
-=
2
where the second inequality follows from af < 4. V < 562 + 10, Substituting this bound yields:
Let 0² = 20 + 2
Then, by Lemma C.2, for all 2, we have
T < 1 (1-2)
L) P.
80^2
1=+2LTT+4 +
2 f-1
1
P 1-1-7
(02 (²+2(9r+)
2
0 r=1
2
1 p S0L22
2
r + -80L?7
(2)
Σ
1
p
1-1-1
r +
80n2
1+
1+
2
Σ
1
P
1-1-7
0²
1)
2
P
p r=1
2
r=1
(1 (1-2) 0
2 1
2
2 t-1
1-1-7
2 2 2
4 pa
r, e7pp
Σ
1
1
p
2
P
(1 (1 1 + 2
0
2
r, 2?
(2)
2 [-1
Σ
2
p
1-1-
r + 2
2
2 3
(27)
0
where of = 80L2, c = 8082, the final inequality holds because 1 x following bound on the geometric sum:
p and the second inequality stems from the
Σ
(1-
p
= Σ
1-2
(1-2) 2
1
p) 2 2
2
T=0
0=0
20

---

Enhancing Parallelism in Decentralized SCO
the condition required to apply the lemma is satisfied. Applying the lemma with dr r, and K - yields the final result:
Equation (27) exhibits recursive structure in Lemma D.5. Since ry S sy80T.
2c2n2 25600
r -
p
C.2. Consensus of the Iterates
The following lemma provides recursive relation for the consensus distance of the iterates Wt- Lemma C.4. The consensus distance for the iterates Ex, satisfies the following recursive relation:
E41 S (1 (1-?)
() E
27 V
Proof. Similarly to Equation (21), we have by the gossip averaging of the iterates:
ME++1 E| e+1 W WE|[W ++ We+ 3/2 || S p) ++ W |
where the second equality is due to Lemma D.I, stating that W P W ! and the incquality follows from the mixing property the gossip matrix Property 2.6. Substituting the bound on EE [ We+g |1 in Equation (23) then yields:
ME S (1 (1- p) (1+ ME. + (1 ()1-))(11 a,
Dividing by M and setting 7 = 2/p finally gives:
E41 S (1- p) (1+ E, - (1-p) 1+ p
n/a v. - (1 (1-2) 2)
2 E +
2 21f0 Ves
where in the last inequality we used (1 p) + 5) = - o
d² 2
S - and (1 p) + ()) = - pt 2 < 2
Using this recursion, we derive an explicit bound on E as follows.
Lemma C.5. For any non-decreasing sequence {arhe the consensus distance E, is bounded as:
2n a
[-1
Σ
E, <
L
2
r=1
Proof. The recursion for E, in Lemma C.4 exhibits the structure in Lemma D.4. Applying the lemma with a, =E.. be = ? and x = p/2, we obtain:
E < Σ
(1-2)
1
?2 I
27 1-1
Σ (1 p
1-1-T
V
2
2
1=1
where in the last inequality we used a² < a² for all r St. t.
D. Technical Lemmas
In this section, we list some technical lemmas, starting with the following property that establishes the invariance of gossip communication when all machines hold the same vector.
Lemma D.1 (Proposition 1, Koloskova et al., 2020). Let E Rdd. For any matrix X = (x x x) E dx and a symmetric, doubly stochastic matrix P E RMx we have XP X.
21

---

Enhancing Parallelism in Decentralized SCO
Next, state classical result for smooth functions.
Lemma D.2. Let f Rd + R. be an L-smooth functionn and x" E arg ming f(z). Then, for every x E R it holds that:
(f(())
The following lemma proves to be useful as well. Lemma D.3. Consider a non-negative sequence a1 a...... QT satisfying the following relation for any t E [T]:
at S b
0
27
for some constant b R. Then, for all & [T), it holds that
S 2b.
Proof. Summing over E [T]. we have that:
T T
1 T
Tb +
Σ
ar
Tb
27
1=
r=1
Subtracting 1/2 E and multiplying by 2 results in
Σ
S 27b. Thus, we obtain:
T
a S b+
a
bb
2Tb 2b.
2T
2T
T=1
The following two lemmas are used derive explicit bounds for the consensus recursions discussed Appendix Lemma D.4. Lef K. E (0, 1] and consider sequence {ar)e21 satisfying the recursion:
bi11 with O,
at S (1 (1-1))a-11)
for some non-negative sequence (be) Then, for all t 2, the following bound holds:
1-1 (1 13) b
4 <
Proof. We prove the statement using induction.
Base case, For t = 2, since a1 = 0, it trivially follows that:
b
b
02 < (1 x)a1
k) 1-Tb,
Induction step. Assume that the induction hypothesis holds for some
> 2. We show that it holds for index + 1:
4++1 S (1 x)a; + by S 1-1
Σ x²) 1-1-1 by + by 1
Σ (1 xx) '- br + by 1 - k) 2>> by
x)
16
k
22

---

Enhancing Parallelism in Decentralized SCO
Lemma D.S. Let K (0, 1] and consider sequence (ar)e21 salisfying the recursion:
a1 - 1 1- K + cin²²
t-2 + x²
cn12 (1
22 x) a, + K3
a1-1
a
with a1 =0 0,
for some non-negative constants C1,02, and 13. Suppose n) S 20g
Then, for all 2 1, the following bound holds:
20
Ot S
k+
Proof. Similar to Lemma D.4, we prove this result by (strong) induction.
Base cases. For t I, the statement is trivial because a1 = 0 S 2c3nn /xt, For t 2, we have:
02 S 1I-x+
cin"² K
a1 +
in R²
Σ
0
(1-x)- a,
2 2
22
2cIn² 2
R3
R3
k
where the last inequality follows from 1 S
2 as S 1, thus verifying the base cases.
Induction step. Suppose that for some 2 3, the induction hypothesis holds for all indices 8 = =1,...... -,....,f. We shall prove that it then holds for + Specifically, denoting the upper bound by B 2c5n² at we assume that a, S B for ...... t and prove that a++1 S B. Plugging the induction hypothesis into the recursion, we get:
Gup +
G at
1-1
212
ac+1 S
1 1-k+
Σ
(1 x)) x)(-1------ 111-1aaa a, +
K
R²
R3
t-1
222²
1 K +
B
+
(1 x))
1-1-1
K
K2
K3
7=1
1 - K + 6
t-1
2
K) 1
B+
K
R3
G12
2
1 - K +
B
K
3
20717² 2
21 2
k
B
33
R3
where the last inequality holds because geometric series:
1 K
for any k S 1, and the penultimate inequality results from the bound on the
kJ
2-2
80
Σ
(1 --1-
Σ (1
(1 x)*
From the condition on n, it follows that
20 2²
Substituting this inequality and noting that
BB, we obtain:
2.
a1+1 < (1-1)
R
B
Ei
=
=(1-
K
B + K - B =
B,
2
k3
2
2
thus establishing the result.
We also utilize the following result, which prove using simple algebraic manipulation.
Lemma D.6. Let A 2 0 and B,C > O, and define n7 min { (n: AA/B for some m > 0. Then,
A Bn + Cyp² <
A A 2/A/
+
n
m
23

---

Enhancing Parallelism in Decentralized SCO
Proof. Since yf is the minimum between three terms, 1/1j is the maximum of their inverses. Therefore,
1/4
A < A max
B
Bn + Cit²
"
1/1
A
1
B
1/4
A +
A 3
A
+
+
+ B
111
A
C1/1
VAB + A3/4
VAB + 3 C1/4
1/1
A
AB AVAB
where the second inequality follows from the fact that the maximum of non non-negative terms is smaller than their sum, and from the monotonic increase of the terms By and Crt² with r).
E. Additional Experimental Results
In Figures 4 to 6, we present the full convergence curves for DAT-SGD and D-SGD on the synthetic least squares problem over the ring, torus, and 1-peer exponential graph topologies, respectively. These results are shown for varying numbers of machines and correspond to the final errors reported Figure 1.
the torus and exponential graph topologies, our method steadily improves with increasing numbers of machines, demonstrating the potential of our approach to effectively increase parallelism. For the ring topology, performance improves when transitioning from M 9 to 25 machines but degrades at M 100 machines, the topology-re -related error term becomes dominant. Conversely, D-SGD does not improve when increasing the number of machines. On the ring and torus topologies, performance is initially better for larger M, but then deteriorates, indicating that while we initially benefit from variance reduction, the optimization transitions to regime where the leading error term depends on topology and inefficient information flow hinders further improvement. For the well-connected exponential graph, initial performance improves with M, but all configurations eventually converge to approximately the same error level.
Ring
0²=1, 2²=1
0²=1, 2=110
10
10
10
100
Error
10-1
Error
10-1
10-2
10-2
10
10-3
10
10-4
10
10-5
10
10
100
10
10
10
10a
10a
100
10a
10a
10a
10a
10a
Iterations
Iterations
02=10,
0² =2=10,
10, 22=10
10
10
10a
100
Error
10-1
Error
10-1
10
10-2
10
10-3
10
10
10-5
10-5
10
10
10"
10S
10
10
10a
10s
100
10t
102
10a
10a
10s
Iterations
Iterations
DAT-SGD, M=9
DAT-SGD, M=25
DAT-SGD, M=100
D-SGD, M=9
D-SGD, M=25
D-SGD, M=100
Figure 4. Error curves for the least squares problem with varying noise, data heterogeneity, and # of machines in the ring topology.
24

---

Enhancing Parallelism in Decentralized SCO
Torus
,0=1,
=1
10.
10
10
100
Error
10 10
Error
10
10
10
10
10
10
10
10
10-5
10
10
100
10a
10
10
10a
10a
100
10a
102
10a
10*
10a
Iterations
Iterations
=²=10,
=²=1
00=10,22=10
10
101
10
10
Error
10
Error
10
10
10
10
10
10
10
10-5
10-5
10
10
100
10
10
10
104
105
100
10
102
103
10*
10a
Iterations
Iterations
DAT-SGD, M=9
DAT-SGD, M=25
DAT-SGD, M=100
D-SGD, M=9
D-SGD, M=25
D-SGD, M=100
Figure 5. Error curves for the least squares problem with varying noise, data heterogeneity, and # of machines in the torus topology.
Exponential Graph
02=1,
=2
101
101
10a
100
Error
10-1
10
Error
10-1
10
10
10-3
10
10
10
10-5
10
10-6
100
10t
102
10 104 105
100
10-
102
10
104
10s
Iterations
Iterations
02=10,
2²=1
22=10
10
101
10a
100
Error
10
Error
10
10 2
10
10
10-3
10-4
10
10-5
10-5
10
10-6.
100
101
102
10a
104
10s
100
10-
10a
10a
10
10a
Iterations
Iterations
DAT-SGD, M=9
DAT-SGD, M=
DAT-SGD, M=100
D-SGD, M=9
D-SGD, M=25
D-SGD, M=100
Figure 6. Error curves for the least squares problem with varying noise, data heterogeneity, and # of machines in the 1-peer exponential graph topology.
25


Reviews:
[{"review_id": "V4TSW53x3F", "reviewer": "Reviewer_3nY6", "summary": "The paper studies an anytime variant of decentralized SGD. It achieves bounds allowing a larger number of nodes successfully team up in decentralized training. It does so by using gradients at averaged query points, thus improving the consensus distance and thus convergence under large number of nodes, which is a valuable contribution.", "questions": "", "limitations": "", "rating": 4, "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 thank the reviewer for acknowledging our contributions and for the positive feedback. As suggested, we provide experiments to evaluate our method, including a synthetic least squares problem and an image classification task. All experiments are run with 3 random seeds, and we report the average performance. Results are available in the following anonymized GitHub repo; we recommend downloading the repo for optimal examination: https://anonymous.4open.science/r/DAT-SGD-figures-4378  \n\n**Synthetic Least Squares**: For machine $i\\in[1,...,M]$, the local objective is $f_i(x)=\\frac{1}{2}\\lVert A_ix-b_i\\rVert^2$, with $A_i\\in\\mathbb{R}^{d\\times{d}}$ drawn from $\\mathcal{N}(0,I)$. The targets are given by $b_i=A_i(x^\\sharp-\\delta_i)$, where $x^\\sharp\\sim\\mathcal{N}(0,I/d)$ is sampled once per run and $\\delta_i\\sim\\mathcal{N}(0,\\zeta^2 I/d)$ introduces heterogeneity. To incorporate stochasticity, we add noise $\\xi\\sim\\mathcal{N}(0,\\sigma^2 I/d)$, yielding the noisy gradient $\\nabla f_i(x)+\\xi$. \n\nWe compare our method with D-SGD over ring, torus, and exponential graph (for which $1/\\rho=\\mathcal{O}(\\log{M})$) topologies, varying $\\sigma,\\zeta\\in[1,10]$, number of machines $M\\in[4,9,25,49,100]$, and $d=50$. For each run, we tuned the learning rate via a grid search over $\\eta\\in[0.1,5e-2,1e-2,5e-3,1e-3,5e-4,1e-4]$. \n\nIn ‘least_squares_parallelization.pdf’, we plot final errors ($\\frac{1}{M}\\sum_{i=1}^{M}{\\lVert x_T^i - x^*\\rVert^2}$ and $\\frac{1}{M}\\sum_{i=1}^{M}{\\lVert w_T^i - x^*\\rVert^2}$ for DAT-SGD and D-SGD, respectively) vs the number of machines for varying $\\sigma$ and $\\zeta$ and across topologies. Colors represent different topologies; line-style denotes the method (solid:DAT-SGD, dashed:D-SGD). For D-SGD, performance deteriorates as $M$ increases, and more significantly for less connected graphs (lower $\\rho$). For ring, this degradation occurs from $M=4$, while for torus and exponential topologies performance is flat between $M=4$ and $M=9$ and degrades afterwards. In contrast, our method improves as $M$ grows: for torus and exponential topologies performance steadily improves, while for ring, it improves up to $M=25$ before deteriorating in a trend similar to that of D-SGD. This suggests that for some $M$ between 25 and 49, the network-related convergence term ($1/\\rho T=\\mathcal{O}(M^2/T)$ for ring) becomes dominant. Overall, this figure aligns with our theoretical findings: DAT-SGD enables performance improvement for larger $M$. We provide the complete convergence curves for different topologies and $M\\in[9, 25,100]$ in ‘least_squares_curves_X.pdf’, where X denotes the topology (ring/torus/exponential).  \n\n**Image Classification with a Neural Network**: We conduct experiments on Fashion MNIST using LeNet, comparing DAT-SGD with D-SGD and $D^2$ [1]. For DAT-SGD and D-SGD, we use momentum with $\\beta=0.9$. Data is distributed among machines using a Dirichlet distribution with parameter $\\alpha$ to control heterogeneity [2]. Experiments are performed on both a ring topology and the Base-2 Graph [3]-a time-varying, state-of-the-art topology for decentralized learning. Learning rates are tuned over $\\eta\\in[0.1,0.01,0.001]$. Colors represent methods and line styles indicate topology (solid:ring, dashed:Base-2).\n\nUnlike the convex least squares setting, this task is non-convex. Following the heuristic proposed by [4], we adopt a momentum-like Anytime update: $x_{t+1}=\\gamma_t x_t+(1-\\gamma_t)w_t$, with a fixed $\\gamma_t=0.9$. Their work shows this enhances training stability and adaptability in non-convex landscapes.\n\nIn ‘fashion_mnist_parallelization.pdf’, we plot final accuracy after 200 epochs vs $M$ for ring topology with heterogeneous data ($\\alpha=0.1$). Our method outperforms the baselines; in addition, the largest accuracy drop for DAT-SGD occurs between $M=8$ and $M=16$, while D-SGD and $D^2$ degrade most between $M=4$ and $M=8$, demonstrating our increased parallelism claim. \n \nIn ‘fashion_mnist_curves.pdf’, we show test accuracy vs epochs for $M\\in[8,16]$ and $\\alpha\\in[0.1,10]$ (heterogeneous and homogeneous setups). In the heterogeneous case, our method outperforms baselines consistently over both topologies, with ring topology performance matching ($M=8$) or nearly matching ($M=16$) the baselines on the well-connected Base-2 graph. Conversely, in the homogeneous case, D-SGD and $D^2$ achieve better performance, motivating further study of our anytime averaging heuristic in non-convex scenarios.\n\n[1] Tang et al., “D^2: decentralized training over decentralized data”, ‘18  \n[2] Hsu et al., “Measuring the effects of non-identical data distribution for federated visual classification”, ‘19  \n[3] Takezawa et al., “Beyond exponential graph: Communication-efficient topologies for decentralized learning via finite-time convergence”, ‘23  \n[4] Dahan & Levy, “Do stochastic, feel noiseless: stable stochastic optimization via a double momentum mechanism”, ‘25", "claims_and_evidence": "The paper improves the convergence results for decentralized SGD, and also gives a last-iterate convergence result, both being interesting additions to the understanding of such methods. \n\nThe algorithmic change is simple & elegant and has no implementation downsides, yet leads to the significantly improved convergence results mentioned.", "methods_and_evaluation_criteria": "Yes, this is a theory paper", "theoretical_claims": "See claims & evidence above\n\nIn terms of presentation, the proof sketch was very useful. I could not check the full proof in detail but overall the approach looks plausible and appropriate", "experimental_designs_or_analyses": "No experimental results are provided unfortuantely.\n\nI know this will sound as a typical ICML reviewer cliche, but I think here some experiments would improve the value of the paper. The claim of higher tolerance to larger number of nodes is very clear, well-supported by theory, so it would really add value to the work to verify this phenomenon on large graphs on simple settings, with the competing methods that you already theoretically compare. In addition, several methods which are more tolerant to data heterogeneity could be included in the comparison (e.g. D^2).\n\nThis would not be very hard to do as many good codebases simulating DSGD are available by now.\n\nUPDATE: I appreciate that the authors have added experiments along the main research aspects now, which I think adds value to the paper.\n\nGiven this, i have upgraded my rating to 'accept'.", "relation_to_broader_scientific_literature": "Looks appropriate", "essential_references_not_discussed": "-", "other_strengths_and_weaknesses": "-", "other_comments_or_suggestions": "-", "questions_for_authors": "see above", "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": "GzUanzf6vX", "reviewer": "Reviewer_ejda", "summary": "The paper introduces Decentralized Anytime SGD (DAT-SGD) to enhance parallelism in decentralized stochastic convex optimization (SCO).\n\nMain Findings\nDAT-SGD extends the parallelism threshold to O(ρ√N), matching centralized learning, while prior decentralized methods were limited to O(ρ¹/²N¹/⁴).\n\nMain Results\nThe algorithm achieves an improved error bound of O(σ/√MT + (√σ+√ζ)/ρT + 1/T), enabling efficient large-scale decentralized training.\n\nMain Algorithmic Idea\nDAT-SGD builds on Anytime SGD, using averaged iterates and gossip averaging to reduce consensus bias, improving convergence and scalability in decentralized networks.", "questions": "", "limitations": "", "rating": 2, "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 appreciate the reviewer’s constructive feedback. It appears that the reviewer’s primary concern is the lack of experimental results. In response, we have included experiments evaluating our method on both a synthetic convex problem and non-convex neural network training. We refer the reviewer to our response to **Reviewer 3nY6** for a detailed discussion of the results.", "claims_and_evidence": "The paper’s claims are well-supported by rigorous theoretical analysis and comparisons with prior work. It effectively demonstrates that DAT-SGD improves parallelism to O(ρ√N), surpassing previous decentralized methods. The claim that DAT-SGD mitigates consensus distance is backed by mathematical proofs, showing reduced model divergence through averaged iterates. Additionally, the improved error bound provides strong evidence for faster and more stable convergence.\n\nHowever, the paper lacks empirical validation. Experimental results comparing DAT-SGD with existing decentralized methods would further strengthen the claims and demonstrate its real-world applicability.", "methods_and_evaluation_criteria": "The proposed DAT-SGD method is well-grounded in theoretical analysis, focusing on improving parallelism in decentralized stochastic convex optimization. The convergence bounds and parallelism limits provide strong analytical validation. However, the paper lacks empirical evaluation, which is crucial for assessing real-world performance. Including experiments on benchmark datasets and various network topologies would strengthen the evaluation. While the theoretical framework is solid, practical testing would provide a more comprehensive understanding of scalability, robustness, and efficiency in real decentralized learning environments", "theoretical_claims": "The proofs in Sections 4.3 and 4.4 were reviewed, particularly the proof sketches outlining the convergence analysis and bias reduction in DAT-SGD. The arguments appear logically sound, with a clear derivation of key results such as the improved parallelism bound O(ρ√N). The analysis effectively builds on Anytime SGD and consensus distance reduction. No major issues were found", "experimental_designs_or_analyses": "The paper does not include an experimental section, making it difficult to validate the practical effectiveness of DAT-SGD.", "relation_to_broader_scientific_literature": "This paper builds on two key works: Koloskova et al. (2020) and Cutkosky (2019). Koloskova et al. (2020) developed a unified theory for decentralized SGD, addressing topology changes and local updates but with limited parallelism scalability. DAT-SGD improves upon this by enhancing parallelism to O(ρ√N) while maintaining strong convergence guarantees.\n\nCutkosky (2019) introduced Anytime SGD, which leverages averaged iterates for stable updates. The authors extend this idea to decentralized settings, using it to mitigate consensus distance and improve statistical efficiency.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "The primary weakness of the paper is the lack of an experimental section, making it difficult to assess the practical effectiveness of DAT-SGD. Without empirical validation, it remains unclear how the method performs in real-world decentralized learning scenarios. Benchmark experiments on different network topologies and datasets would significantly strengthen the paper.", "other_comments_or_suggestions": "NA", "questions_for_authors": "Do you plan to include experiments in an extended version or supplementary material?\nIf there are ongoing or planned experiments, providing preliminary results or an outline of the experimental setup would help in evaluating the method’s real-world applicability.", "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": "d3wAiLFkNh", "reviewer": "Reviewer_75sX", "summary": "The paper proposes Decentralized Anytime SGD — a noved algorithm for decentralized optimization. The algorithm is based on anytime SGD algorithm proposed by (Cutkosky, 2019). The paper provides the convergence rate of their method for convex functions, showing improvement over D-SGD in the middle convergence term, as well as showing the convergence for the last iterate averaged across the nodes, instead of the priorly used average of losses from all the iterates.\n\n## update after rebuttal\n\nI would like to thank the authors for their response and for adding the experiments. While some of my concerns have cleared, I have some of the remaining concerns and therefore I keep my score. \n- I disagree with the authors that their method always improves over the baselines theoretically. For example, when data heterogeniety term is large, then Gradient Tracking is expected to have the better convergence (see Table 2 in this submission). Even with this, I believe that the paper provides an interesting improvements over the existing decentralized methods in the homogeneous case, however, I would like to see a more rigorous discussion of this.\n- Given that, I am a bit surprised that experiments show the opposite from theory: that D-SGD and D^2 improve in the homogeneous case, while DAT-SGD improves in the heterogeneous case.\n- I beleive that the Gradient Tracking method is not orthogonal, but a direct baseline mehtod, and therefore it should be included in the experimental comparison. For example, in the theoretical comparison in Table 2 of this submission, the proposed algortihm DAT-SGD was combared with Gradient Tracking but was not compared with D^2. Thus, I do not understand the choice of the baseline of D^2 instead of Gradient Tracking in experiments. \n- For tuning hyperparameters in experimental comparison, please ensure that the optimal learning rate is not on the end of the grid by extending the grid when necessary. E.g. in neral network experiments the learning rate was chosen only from 3 values, which makes it very likely that for some experiments, the found learning rate was on the end of the tuned grid.", "questions": "", "limitations": "", "rating": 2, "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 thank the reviewer for their time and valuable input. We address the reviewer’s concerns and questions separately:\n\n**Correctness of the proof and Lemma A.1**: We divide our answer into 2 parts:\n- First, the reviewer’s concern about the appearance of the term $x_{-1}$ in the analysis of [1] refers specifically to the equality $\\alpha_{\\tau}(x_{\\tau}-w_{\\tau}) = \\alpha_{0:\\tau-1}(x_{\\tau-1} - x_{\\tau})$, which is applied for $\\tau=0,...,T$ (in Appendix D therein). Although the authors of [1] did not explicitly state this, by definition we have $\\alpha_{0:-1}=0$ (also see the first line in the proof of Theorem 1 in [2]; they start at $t=1$ like we do, thus defining $\\alpha_{1:0}=0$). Therefore, at $\\tau=0$, both sides of this equality trivially evaluate to zero, since $w_{0}=x_{0}$ and $\\alpha_{0:-1}=0$. Consequently, despite the formal appearance of the term $x_{-1}$, it can be defined arbitrarily since it is multiplied by zero; thus, the equality (and therefore Theorem 1 in [1]) remains valid.  \n- Second, regarding Lemma A.1, we thank the reviewer for helping us spot a typo; however, we clarify that the typo does not occur within Lemma A.1 itself and does not impact our results in any way. Nevertheless, the typo requires slight adjustments to the text, as we elaborate below. The error appears in Eq. (6) (and similarly in Eq. (16)), where the coefficients should be corrected to: $x_{t+1}=\\frac{\\alpha_{1:t}}{\\alpha_{1:{t+1}}}x_{t}+\\frac{\\alpha_{{t+1}}}{\\alpha_{1:{t+1}}}w_{t+1}$.   \n   - With this correction, our Lemma A.1 aligns precisely with Theorem 1 in [1], except for the indexing of iterations—[1] starts indexing from $t=0$, while we start from $t=1$. Therefore, all summations in our analysis (including terms like $\\alpha_{1:t}$) begin from $\\tau=1$ instead of $\\tau=0$. After this correction, Lemma A.1 is accurate and correctly stated in its current form.  \n   - The typo correction also necessitates a minor update in the definition of $\\delta_t$ at Line 594: it should now be $\\delta_{t}=\\alpha_{t+1}/\\alpha_{1:t+1}$ instead of $\\alpha_{t}/\\alpha_{1:t}$. Importantly, this adjustment does not affect Lemma C.3, since for $\\alpha_{t}=t$, we now have $\\delta_{t} = 2/(t+2)$ and consequently $\\alpha_{t}\\delta_{t}=2t/(t+2)$, which still satisfies the condition $\\alpha_{t}\\delta_{t}\\leq 2$ (Lines 903-904).  \n   - The only additional proof requiring modification is Lemma B.1, which remains correct once these coefficients are appropriately updated.\n\nWe hope this clarification resolves any potential confusion.  \n\n**Experiments**: We have added experimental results and refer the reviewer to our response to **Reviewer 3nY6** for further discussion. In the experiments, we compare our method with both D-SGD and $D^2$ (for the non-convex image classification task; as suggested by **Reviewer 3nY6**), with the latter being “more tolerant to data heterogeneity”. We note that Gradient Tracking (GT) is orthogonal to our method; the tracking mechanism can also be applied to our approach by tracking the gradients at the query points $x_t^i​$. Investigating the effect of GT, both theoretically and practically, is a valuable future direction.\n\n**Last-iterate convergence**: To the best of our knowledge, there is no other work in the decentralized setup showing last-iterate convergence. \n\n**Lower bounds for decentralized SCO**: The first statistical term, of order $\\sigma/\\sqrt{MT}$, matches the centralized rate and is unimprovable; see, e.g., [3,4]. While we are not aware of any lower bound for the second term (of order $1/\\rho T$ in our rate), which is related to the network topology, our derived parallelism bound of $M\\leq\\mathcal{O}(\\rho\\sqrt{N})$ is unimprovable in terms of $N$ (i.e., $\\sqrt{N}$), as it matches the centralized case. It remains an interesting open question whether the dependence on $\\rho$ can be further improved.  \n\n**Convex analysis**: The reviewer is correct – our analysis is valid for convex functions. We have included experiments on neural network training to demonstrate our method's potential in non-convex optimization scenarios. Establishing convergence bounds for non-convex functions is a non-trivial task we leave for future work.\n\n**Improvement w.r.t prior work**: Our proposed method improves over prior work for any value of $\\rho$. Note that the second term in our rate, of order $1/\\rho T$, also appears in the convergence bounds of D-SGD and GT. However, our analysis removes the term that scales with $1/\\rho^{1/3}T^{2/3}$, which limits the achievable parallelism bound.\n\n[1] Dahan & Levy, “SLowcal-SGD: Slow Query Points Improve Local-SGD for Stochastic Convex Optimization”, '24   \n[2] Cutkosky, “Anytime Online-to-Batch, Optimism and Acceleration”, '19  \n[3] Woodworth et al., “Graph oracle models, lower bounds, and gaps for parallel stochastic optimization”, '18  \n[4] Woodworth et al., “The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication”, '21", "claims_and_evidence": "The algorithm is interesting and the proposed algorithm provides an interesting and non-trivial improvement in some cases over the prior decentralized SGD algorithms for the convex smooth functions.", "methods_and_evaluation_criteria": "theoretical part yes, however there is no empirical evaluation of the proposed algorithm.", "theoretical_claims": "I am not sure of correctness of the proofs since when I started to check the proof, already statement of Lemma A.1. seems to have a typo: it should be alpha_{tau - 1} instead of alpha_{tau}. Moreover while checking the proof of Theorem 1 from (Dahan & Levy), I noticed that it uses iterates x_{tau - 1} for tau = 0, however x_{-1} was never defined. Please clarify these points, as right now the proof seem to be incorrect.", "experimental_designs_or_analyses": "How does the proposed algoritm compares to D-SGD and GT emperically? Can we see in practice the benefit of the improved convergence rate?", "relation_to_broader_scientific_literature": "Has there been any other work on decentralized optimization methods showing last-iterate convergence? \n\nHas there been any lower bounds for the convex decentralized optimization? How does the provided convergence rate compare to those lower bounds?", "essential_references_not_discussed": "-", "other_strengths_and_weaknesses": "The method is limited to the convex functions only", "other_comments_or_suggestions": "-", "questions_for_authors": "Could you characterize, under which conditions the proposed method improves over the prior works? I.e. what are the conditions on \\rho and \\zeta, under which the proposed algorithm improves convergence? Also, e.g. could highlight the case of the homogeneous function with zeta=0 and give a condition on rho. \n\nCan the proposed method be generalized for non-convex smooth functions?", "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": "WpEsDDB2az", "reviewer": "Reviewer_X6LA", "summary": "This paper presents Decentralized Anytime SGD, a decentralization optimization algorithms that is based on Anytime SGD. The authors presents the convergence analysis of Decentralized Anytime SGD. Decentralized Anytime SGD achieves linear speedup and has a better sample complexity than that of D-SGD under the non-convex scenario.", "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 thank the reviewer for their time and feedback. We address the reviewer’s questions individually:\n\n**Experiments**: We have included experiments evaluating our method on both a synthetic, convex least squares problem and non-convex neural network training. We refer the reviewer to our response to **Reviewer 3nY6** for a discussion of the results. \n\n**Linear speedup and transient time**: We will add a discussion about the transient complexity in the revised version. It can be inferred from Theorem 4.1 that the transient time for our method is $T\\geq\\mathcal{O}(M/\\rho^2)$; this improves upon D-SGD by a factor of $M^2$. For example, this implies a transient complexity of $\\mathcal{O}(M^5)$ for a ring and $\\tilde{\\mathcal{O}}(M)$ for a static exponential graph. Should the reviewer have any further comparisons in mind, we would be happy to incorporate them into our text.\n\n**Symmetric gossip matrix assumption**: Thank you for raising this insightful point. Our analysis relies on the contraction property stated in Property 2.6 (Eq. (2)), which holds when the communication matrix is symmetric and doubly stochastic. This assumption is standard in the literature and has been used in many prior works, including [1,2,3,4]. We acknowledge that there is a growing body of work analyzing more general communication matrices—such as asymmetric and/or only row-/column-stochastic matrices—e.g., [5,6,7]. Our goal in this work was to provide a clean and interpretable analysis under a widely adopted and well-studied assumption. We believe our results open the door to extending the analysis to more general settings with non-symmetric or non-doubly-stochastic matrices. We will include a discussion of this direction in the 'Conclusion and Future Work' section.\n\n[1] Lian et al., “Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent”, '17   \n[2] Tang et al., “Communication compression for decentralized training”, '18  \n[3] Koloskova et al., “A unified theory of decentralized sgd with changing topology and local updates”, '20  \n[4] Koloskova et al., “An improved analysis of gradient tracking for decentralized machine learning”, '21  \n[5] Assran et al., “Stochastic gradient push for distributed deep learning”, '19  \n[6] Pu & Nedic. “Distributed stochastic gradient tracking methods”, '21  \n[7] Lu & De Sa. “Optimal Complexity in Decentralized Training”, '21", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "The reviewer has check the theoretical claims and proofs in this paper and has not found any fatal issues.", "experimental_designs_or_analyses": "There is no experiments in this paper. However, as a decentralized optimization algorithm, it is essential to present numerical experiments to compare the proposed algorithm with other classial decentralized algorithms (including D-SGD and more), which can validate the practical performance of the proposed algorithms.", "relation_to_broader_scientific_literature": "NA", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "**Strengthes**\n1. Present a proof sketch of the convergence rate.\n2. Achieves linear speedup.\n\n**Weakness**\n1. Lack of the analysis of transit complexity.", "other_comments_or_suggestions": "Linear speedup is a significant character of decentralized algorithms. Although the proposed algorithm achieves the linear speedup, the authors fail to high it and use the sample complexity $N$ in the convergence result. The reviewer suggest the author to add more discussion on linear speedup and highlight it in the theoretical result.", "questions_for_authors": "1. Whether the authors can present additional experiments to compare the proposed algorithm to other decentralized algorithms? \n2. Can the author provide any discussion on linear speedup and transient complexity?\n3. Whether the symmetric assumption of the gossip matrix $P$ can reduce? Why?\n\nThe reviewer would to update the final rating according to the response to those weaknesses and questions, as well as the experimental performance.", "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: The paper gives a tighter convergence analysis of decentralized SGD than prior works such as Koloskova et al. The key idea that enables this improvement is Anytime SGD, extending the framework proposed in Cutoksky et al, where the algorithm maintains a slowly moving average iteration in addition to local models at the nodes. This slowly moving iterate helps reduce the consensus gap and improve convergence bounds. Here are some points due to which the paper is on the borderline.
* The paper did not have empirical evaluations, however, the authors did show some results during the rebuttal phase which they plan to add to the paper. This convinced some reviewers to increase their scores. 
* The analysis only applies to stochastic convex optimization
* The improvement is in the higher order terms of the convergence bound, not the dominant term. 
* The practical applicability of the proposed algorithm is limited due to the need to maintain average iterates
Decision: Accept (poster)