Exploiting Similarity for Computation and Communication-Efficient Decentralized Optimization
Authors: Yuki Takezawa
Xiaowen Jiang
Anton Rodomanov
Sebastian U Stich
Venue: ICML 2025 poster (2025)
Keywords: decentralized optimization
distributed optimization
Primary area: theory->optimization
TL;DR: We propose communication and computational-effecient decentralized optimization methods based on proximal-point method.

Abstract: Reducing communication complexity is critical for efficient decentralized optimization. The proximal decentralized optimization (PDO) framework is particularly appealing, as methods within this framework can exploit functional similarity among nodes to reduce communication rounds. Specifically, when local functions at different nodes are similar, these methods achieve faster convergence with fewer communication steps. However, existing PDO methods often require highly accurate solutions to subproblems associated with the proximal operator, resulting in significant computational overhead. In this work, we propose the Stabilized Proximal Decentralized Optimization (SPDO) method, which achieves state-of-the-art communication and computational complexities within the PDO framework. Additionally, we refine the analysis of existing PDO methods by relaxing subproblem accuracy requirements and leveraging average functional similarity. Experimental results demonstrate that SPDO significantly outperforms existing methods.

Exploiting Similarity for Computation and Communication--ficient Decentralized Optimization
Yuki Takezawa 12
Xiaowen Jiang 34
Anton Rodomanoy Sebastian U. Stich
Abstract
mization is reducing communication costs since parameter exchanges between nodes are often more expensive than local computation at each node due to high latency and lim- ited bandwidth of the network (Lian et al., 2017; Wang et al., 2019). A key technique to reduce the communication com- plexity is for each node to perform multiple local updates before the communication. The concept of multiple local updates was initially applied for Decentralized Gradient Descent (Nedic & Ozdaglar, 2009; Lian et al., 2017) and Gradient Tracking (Lorenzo & Scutari, 2016; Pu & Nedic, 2021). However, increasing the number of local steps re- quires a smaller learning rate, which ultimately requires the same communication cost to achieve the desired accuracy level (Koloskova al., 2020; Liu et al., 2024a). This is because, in Decentralized Gradient Descent, each node tries to minimize its own local loss function by performing gra- dient descent multiple times, but fully minimizing its local loss function is not desirable. Gradient Tracking also has the same issue, and this inconsistency hinders the use of multiple local updates to reduce communication complexity. Thus, to take advantage of multiple local updates, we need to resolve this inconsistency.
Reducing communication complexity is critical for efficient decentralized optimization. The prox- imal decentralized optimization (PDO) frame- work is particularly appealing, as methods within this framework can exploit functional similarity among nodes to reduce communication rounds. Specifically, when local functions at different nodes are similar, these methods achieve faster convergence with fewer communication steps. However, existing PDO methods often require highly accurate solutions to subproblems asso- ciated with the proximal operator, resulting in significant computational overhead.
In this work, we propose the Stabilized Proxi- mal Decentralized Optimization (SPDO) method, which achieves state-of-the-art communication and computational complexities within the PDO framework. Additionally, we refine the analysis of existing PDO methods by relaxing subprob- lem accuracy requirements and leveraging aver- age functional similarity. Experimental results demonstrate that SPDO significantly outperforms existing methods.
An effective approach to address this challenge is to develop decentralized optimization methods based on the proximal- point method, where nodes solve the subproblem associated with the proximal operator in their local updates (termed PDO framework this work). Scutari & Sun (2019) demon- strated that combining proximal-point updates with gradi- ent tracking yields efficient decentralized optimization scheme, known as SONATA. This method effectively ex- ploits the similarity of local loss functions across nodes to significantly reduce communication complexity (Sun et al., 2022; Tian et al., 2022). However, achieving such low communication complexity requires solving the proximal subproblem with high accuracy at each node, leading to suboptimal computational overhead during local updates.
1. Introduction
Decentralized optimization is coming to be pivotal paradigm due to its use for privacy preservation and ef- ficient training on large-scale datasets (Nedic & Ozdaglar, 2009; Lian et al., 2017; Koloskova et al., 2020). In decen- tralized optimization, nodes have different loss functions and are connected by an underlying network topology. Then, the nodes exchange parameters with their neighbors every round and minimize the average loss function.
One of the most important challenges in decentralized opti-
In this work, we pose the following question: Can we de- velop proximal decentralized optimization (PDO) method that achieves low communication complexity without sacri- ficing computational efficiency? We provide an affirmative answer by introducing the Stabilized Proximal Decentral- ized Optimization (SPDO) method. SPDO improves upon
"yyoto University "OIST CCISAA Helmholtz Center for Infor- mation Security 'Saarland University. Correspondence to: Yuki Takezawa tyukiitakezzwwr it.iiiisttootou.a........
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Exploiting Similarity for Computation and Communication-PFiicee Decentralized Optimization
Table 1. Summary of communication communication and computational complexities in the strongly-convex setting (our additional
results for the convex case are summarized in Appendix A). "# communication" represents the number of times that each node exchanges parameters with neighboring nodes to reach the target accuracy c, and "# computation" represents the number of gradient oracle queries required by each node. Since Tian et al. (2022) only showed the convergence rate of Accelcrated Exact/ Inexact-PDDO with j S Ómax, we show the convergence rates under the assumption that μ S 6 and μ S 6 for simplicity.
Algorithm
Reference
Communication
Computation
Assumptions
Gradient Tracking
Koloskova et al. (2021)
o pit
of log(
(8)
- log(2)
1,
log( f lug( (9)
Exact-PDO (SONATA)
Sun et al. (2022), Th. 199
n.a. (c)
1,2.4
Inexact-PDO
Th. 1,2
p(- log( # log(:
<x22 log (+) log (4)
1,2,4
Stabilized-PDO [new]
Th. 3, 4
pC lug( ( 1og(H)
WE log (+)
1,2.4
"
(10
Accelcrated SONATA
Tian et ul. (2022)
0
V
prd pT logt 4) log log(
n.a. (c)
1,2,
61
Vinu l (log())))) (4)
Inexact Accelerated SONATA
Tian et ul. (2022)
0
Sun pri p] logt 4) log + log(
1,2,
Accelerated Stabilized-PPO [new]
Th. 5,
pp logi (.) log(
2 log(?)
1,2,4
(a) It holds that < L,, and < holds when nodes have similar datasets.
(b) Sun et al. (2022) showed that the communication complexity of SONATA is O onn shows that the dependence on ōmix can be reduced to 6.
log(t)) while our new theorem, Theorem 1,
m(1-p)
(c) "n.a." represents that we need to solve the subproblem exactly.
(d) 5 is smaller than max and can be up to vn times smaller than mmxx.
existing approaches in several key aspects: (i) it requires less accurate solutions to local subproblems, resulting in better computational efficiency, and (ii) it leverages the average functional similarity across nodes, leading to more effective optimization. Furthermore, (iii) the accelerated variant of our method, Sccllrraed-SPPDO achieves state-of-the-art communication and computational complexities among de- centralized optimization methods, as summarized in Table 1. More specifically, we make the following contributions.
2022; Tian et al., 2022, etc) analyzed the convergence rate only in the strongly-convex case, while we analyze all methods in both convex and strongly-convex cases.
Notation:
We write ||>||| for Euclidean norm of Rdd and use O() and 22-)) to hide polylogarithmic factors.
2. Related Work
We propose (ccelerated-SPDOG which can attain the best communication and computational complexities among the existing decentralized optimization methods.
Decentralized Optimization: The most basic decentral- ized optimization method is Decentralized Gradient Descent (Nedic & Ozdaglar, 2009; Lian et al., 2017; Koloskova et al., 2020), while due the data heterogeneity, Decentralized Gradient Descent cannot achieve the linear convergence rate in the strongly-conve case. Many researchers have tried to achieve the linear convergence rate, proposing EXTRA (Shi et al., 2015), NIDS (Li et al., 2019), Gradient Track- ing (Lorenzo & Scutari, 2016; Pu & Nedic, 2021; Yuan et al., 2019; Takezawa et al., 2023; Liu et al., 2024b), and on (Scaman et al., 2017; Kovalev et al., 2021). These methods can achieve the linear convergence rate, while they still involve a certain amount of communication cost even though nodes have very similar loss functions. The concept of second-order similarity was introduced to capture this phenomenon, in which å and 8max measure the similarity among the loss functions held by nodes (see Definition I and Assumption 3) (Karimireddy et al., 2021; Murata & Suzuki, 2021; Kovalev et al., 2022). The quantities 5 and 8mx approach zero when the local loss functions come to be similar. To exploit this similarity, many variants of the prox- imal decentralized optimization method have been proposed (Li et al., 2020; Sun et al., 2022; Tian et al., 2022; Cao et al., 2025; Jiang et al., 2024a;b). Second-order similarity also
We also propose non-accelerated methods, called SPDO, which can attain the best communication and computa- tional complexities among the existing non-accelerated decentralized optimization methods.
To clarify the difference between (Accelerated-JSPDO and the existing methods, we provide a refined conver- gence analysis of various methods in the PDO frame- work. Our analysis recovers Exact-PDO, also known as SONATA (Sun et al., 2022), as a special instance. While SONATA assumed that the subproblem was ex- actly solved, our approach allows us to solve the sub- problems approximately (Inexact-PDO). We then show that SPDO can solve the subproblem even more coarsely than Inexact-PDO.
The existing analysis of SONATA showed that the com- munication complexity depends on the maximum dissim- ilarity of local functions δmax (Sun et al., 2022), while we prove that it depends only on the average dissimilarity 8, which can significantly reduce communication costs.
Moreover, the prior papers on PDO methods (Sun et al.,
2

---

Exploiting Similarity for Computation and Communication--Piicee Decentralized Optimization
plays crucial role in governing communication complexity in distributed learning (Karimireddy et al., 2021; Khaled & Jin, 2022; Zindari et al., 2023; Patel et al., 2024).
Assumption 1 (Strong Convexity). There exists μ 2 0 such that for any æ; y E R and i, it holds that
1 21 yll (1) fi(x) fv( (fi(y), y)
2
Proximal-point Methods: In this section, we briefly in- troduce Proximal-point Method. Applying Proximal-poo ppint Method to minimize / yields the following update rule:
Assumption (Smoothness). There exists 2 such that for any x. y R and it holds that
A | 1 ""
Vf(x)) - fi - -| - yll-
(2)
x. (r(+1) arg min agRd
(+((z)= = f(x)
2
Definition 1 (Similarity). Under Assumption 2, let 5 2 the the smallest number such that it holds that
0
where >> 0 is hyperparameter. The vanilla Proximal-point Method needs to solve the above subproblem exactly, which is infeasible in general. Many researchers have tried to avoid the exact proximal evaluations (Rockafellar, 1976;
1 -Vh,(a)
S 5 y (3)
Solodov & Svaiter, 1999; 2001; Monteiro & Svaiter, 2013).
for any x. y E Rd where h₂(x)) = f(x) - f((z).
Rockafellar (1976) showed that Proximal-point Method can attain the same convergence rate when (+F = O [|=x(++1) - (+) is satisfied. It implies that more accurate subproblem solution is required as the number of iterations increases. To mitigate this issue, Solodov & Svaiter (1999) proposed Hybrid Projection Proximal -piint Method, which can achieve the same convergence rate if (xx s O(X||=((+1) - (r()) []) is satísfied. This condition is significantly weaker than the condition for the vanilla Proximal-pone pponnt Method.
Lemma 1. If Assumption 2 holds, there exists 5 such that 8 S L and Eq. (3) holds.
Apart from Definition 1, Assumption 3 is also commonly used in the existing literature (Tian et al., 2022; Sun et al., 2022). However, Assumption 3 needs to assume that ft is twice differentiable, and can be much smaller than dmax. We use Definition instead of Assumption
this study. 0 such that for any
Assumption 3. There exists Smax xr E Rd and i, it holds that
The accelerated Proximal-poin Method (Gliler, 1992) also has the same issue, requiring a more accurate subproblem solution as the number of iterations increases. Based on Hy- brid Projection Proximal point Method, Monteiro & Svaiter (2013) proposed its accelerated method and relaxed the con- dition for an approximate solution of the subproblem.
f(x)) - v+((()) S 6max.
(4)
Remark 1. It holds that 5 S 8max. Moreover, 5 can be at most v times smaller than 6max.
Then, we assume that edge weights (Wij hi satisfy the following assumption.
A recent line of work developed distributed versions of the Proximal-poin Method (Shamir& & Srebro, 2014; Li et al., 2020; Sun et al., 2022; Jiang et al., 2024a;b). We will further discuss these approaches See. below.
Assumption 4 (Spectral Gap). For any i and j. Waj = Wj and Σ Wij = 1. Then, there exists E [0, 1) such that for any 3τ. Ø2 T. E 1ed, it holds that
3. Problem Setup
n Σ
Wy m|| S p
2
x
(5)
In this work, we consider the following problem where the loss functions are distributed among n nodes:
where 2i=1 Zz.
min f(x), f(x) EERd
Σ f(()),
Evaluation Metric: As communication is often more ex- pensive than local computation, the primary goal in de- veloping decentralized optimization methods is to reduce communication complexity. If methods can achieve the same communication complexity, the method with less com- putational complexity is superior.
where æ is the model parameter and f; is the loss function of i-th node. The nodes are connected by an undirected graph, in which Way E [0, 1] represents the edge weight between modes and j. and Wij > if and only if nodes i and j connected. The Metropolis-Hastiee 2005) is a commonly used choice for (Wi) jaj. Following the previous work (Li et al., 2020; Tian et al., 2022; Sun et al., 2022; Lin et al., 2023; Khaled & Jin, 2023; Jiang et al., 2024b), we assume that the loss functions satisfy the following assumptions.
weight (Xiao et al.,
4. Refined Analysis of Proximal Decentralized Optimization Method
In this section, we briefly explain the framework of Proximal Decentralized Optimization (PDO) methods and provide the
3

---

Exploiting Similarity for Computation and Communication--fiiccenn Dec.nrtt Optimization
Algorithm 1 Proximal Decentralized Optimization Method (PDO)
1: Input: The number of rounds R. and hyperparameters M and X.
2: for 0.1,...,Af R 1 do
3: for i = 1....,, n in parallel do
2; (r+ za arg ming (a) where (x) = fi(x)) + (h.") .x) + 211 - xz! 12.
4:
5: z (r+1) MULTIGOSSIP (1+t) W. W.M,i).
(r-1) MULTIGOSSIP h ( V () ), W. -fi(at
6:
h
7: end for
8: end for
Algorithm 2 Multiple Gossip Averaging
the condition
1: function MULTGGosSPP((:)EL W, M)
5 p 6L
2: a; (0)
a; for all i.
3: for m 0, M 1 do
prove in Lemma 11 in the appendix. This flexibility extends to other averaging mechanisms, provided they meet the same error guarantees.
4: a (m+11
リー= Ei y (r)
5: end for
6: return a: (M)
7: end function
In many practical scenarios, the choice M = may not suffice, as it requires the network topology to be sufficiently dense to ensure adequate communication accuracy. When the network is sparse, a common approach is perform mul- tiple iterations of gossip averaging (i.e., Alg. 2) to improve the averaging accuracy. Specifically, if gossip averaging is performed M times, it holds that:
convergence analysis. PDO contains SONATA (Sun et al., 2022) as a special instance when the proximal subproblem is solved exactly. The proofs are deferred to Sec. D and G.2.
In decentralized optimization, each node would like to mini- mize f. but node can access only the local loss function ft For PDO, each node approximates f as follows:
Σ a
=1 S P 2M
x - 1=
f(z) = f((x)) + hx(
(6)
where {æ; and { J==1 are the input and output of Alg, 2, and æ = 1 Ei= Ty. Thus, if we perform gossip averaging more than M T-p log( (L) times, PM is less 5 than or equal to 6Z. and then PDO works for arbitrary
(") = f(()) + (Vhr(o) ), x))
2o 1 x 2
A
where 2 is the hyperparameter and we approximate (x) by linear approximation. Furthermore, PDO cannot compute (=.(") since node i can exchange parameters only with its neighbors. Thus, PDO estimates (ha(a,)") (t) by gradient tracking. We show the pseudo-codk in Alg. 1. In
4.1. Convergence Analysis
We now present the convergence analysis of PDO. The proofs are deferred to Sec. D and G.2.
Theorem 1. Consider Alg. 1. Suppose that Assumptions 1,
line 4, PDO solves the subproblem associated with Eq. (6), and in lines 5 and 6, PDO estimates 1 - (m+ and
2, and 4 hold, and h ()) Vh,( ("), 20!0)
=0),, and
(a (r+))) by gossip averaging and gradient tracking.
V Fi (ar (+t
Arbitrary Approximate Averaging Operators: While Alg. is demonstrated using Alg. as subroutine, it im- portant emphasize that the PDO framework is not limited to this specific mechanism. Instead, PDO can be combined with any arbitrary averaging operator that achieves a suffi- cient level of accuracy.
< 8(40 1)
Σ x
n
(r+
-a(->/= -//0)?? (8)
4(r + 1)(r + 2)
Strongly-convex Case: Suppose that μ O. When X = 45 and M 2 T-p log( (Z) ) it holds that
I R-1 w (f(((++))) - (((+t)))(((=)))) < after R W
For instance, is sufficient to use a single gossip averaging step (i.e., M = 1) if the spectral gap parameter p satisfies
O u+O log( "lll" ""l"")-"'''')) rounds where w((r (1+ y

---

Exploiting Similarity for Computation and Communication--Piicen Decentralized Optimization
and WR R.
-EPD
R-1 w(r),
Thus, it requires most
exactly solved, which is infeasible in general. Our new theo- significantly relaxes this condition and shows that PDO can achieve the same communication complexity without solving the subproblem exactly. To clarify this difference from Sun et al. (2022), we refer to PDO with the inexact subproblem solution as Inexact-PDO.
u log
L (
|l|
x=11
O
log
(a(1
communication where x(r) E x!!"!
Convex Case: Suppose that μ = 0. When A = 48 and M 2 T-p log( (1) it holds that
R PR-1 (( - f(x)) S
Reducing Dependence on ómax to 8: Sun al. (2022)
showed that SONATA achieve Ö(
- log( {)) com-
after O ((|l IIe rounds. Thus, requires at most
p(l p(1-p) p)
munication complexity in the strongly- convex case. How- ever, Theorem improves to O KT-pP log( This improvement indicates a more favorable dependence on the functional dissimilarity, which can lead significantly lower communication costs, shown in Remark 1.
1²
L )
o
log
(1-P)e P)E
communication.
Any optimization algorithm can be used to approximately solve the subproblem that Eq. (8) is satisfied, For in- stance, if we use Nesterov's 's Accelerated Gradient Descent (Nesterov, 2018), we can achieve the following result.
New Analysis in Convex Case: SONATA was analyzed only in the strongly-come case (Sun et al., 2022). Our theorem is the first to provide the analysis in both convex and strongly-convex cases.
Theorem 2. Consider Alg. 1. Suppose that Assumptions 1, 2, and 4 hold, and we use the same initial parameters, X, and M as in Theorem 1. Then, if we use Nesterov's Accelerated Gradient Descent with initial parameter a to approximately solve the subproblem in line 4, each node requires at most
Initial Values: Computing the initial value of h, requires dg communications where dg is the diameter of the underly- ing network. However, this overhead is negligible compared to the total communication cost. If the initial values are instead set to zero, additional terms may appear in the com- munication costs (see Koloskova et al. (2021)).
o
1. (V=+= log (r + 2)²)
8(6 + p) ))
5. Stabilized Proximal Decentralized Optimization Method
iterations to satisfy Eq. (8).
Theorem shows that PDO can achieve the best communica- tion complexity among the existing non-accelerated decen- tralized methods. However, Eq. (8) implies that PDO needs solve the subproblem more accurately as the number of rounds increases, which involves the suboptimal computa- tional complexity. In this section, we propose Stabilized Proximal Decentralized Optimization (SPDO), which can
4.2. Discussion
New Analysis with Inexact Subproblem Solution: The framework of PDO initially introduced by Li et al. (2020) and Sun et al. (2022), and Sun et al. (2022) proposed SONATA. However, they assumed that the subproblem was
Algorithm Stabilized Proximal Decentralized Optimization Method (SPDO)
1: Input: The number rounds R, and hyperparameters M and X.
2: for r == 0, L,...,R
do 3: for 1, 1,...,, n in parallel do
(r+1) z arg mingeR Fir (2) where (x)( = fi(x) + (1 x)) + - - 13 +h(") ..) + 1 - mt (++1) -0ll - 13
4:
x
(x+1) arg min 0.
(Vii (r+1)
5:
(r+1) MULTIGOSSIP
(r+ W, i,
6:
U.
U
7:
h
(r-1)
MULTIGOSSIP
(r)
Viil
(r+1)) W, M.. v5i(o!
8:
end for
9:
end for
This update rule can be rewritten v.
(r+b)
(pc (r+1) (oa V((aatr1)) - h!9))
a+d
5

---

Exploiting Similarity for Computation and Communication-EPiiieal Decentralized Optimization
achieve the same communication complexity while enjoying better computational complexity than PDO.
Strongly-conver Case: Suppose that p O. When À 200 and M 2 T-p log( o it holds that WR E/=D win) (f(x(++1)) - ((x))) S after R
I
For simplicity, we consider that case when μ 0 and M = 1. To relax the condition for an approximate subproblem solution, we use the idea of Hybrid Projection Proximal- point Method (Solodov & Svaiter, 1999). Straightforwardly adapting Hybrid Projection-proxtee yields the following update rules:'
O (ut log( ( -x'1()) rounds where w = (1+
+ 208 206)"
and WR = 2nmo wir). Thus, it requires at most
Point Method to PDO
0 p 8 n01 p)
L 5
H (lll(0)) - -00113
log
log
(r+1)
arg min EE
f((x)) (11 100",,,)
.0) + 2 |l - 0; (1)
communication where ((() == 1 > Li=l 1.T)
Convex Case: Suppose that μ = O. When X 206 and M 2 T-p log( ( it holds that R Em= f(x(1)
v.
arg min vERd
(V (1))))
0, + 2
110 - 0. / |p]
R
f(x') S after R O (6ll =IIl() rounds. Thus, it
(r+1)=
Wo Woj (+t))
(+++)
requires at most
j=1
( x=11 log
L 8 (1))
(r+1]] = Σ Wi (n/") + (ffoottt)) (((
p)E
h
j=1
communication.
However, we found that the above update rules do not work. In the above update rule, vi (r+ * an(+z)) even though the subproblem is solved exactly. That is, the above update rules do not recover PDO when the subproblem is exactly solved. This discrepancy can hinder the convergence of the parameters to the optimal solution. Intuitively, when solve the subproblem exactly, 0; (r+1) should equal to (r+1) since the above technique is not necessary. Moti- (r+ 4) vated by this intuition, we modify the update rule of v; as in Alg. 3, in which the modification is highlighted in blue. We refer to this method as Stabilized Proximal Decentral- ized Optimization (SPDO). As a special instance of SPDO, recover PDO. When the subproblem is exactly solved, ie., (x. (r+1)) = 0, it holds
Theorem 4. Consider Alg. 3. Suppose that Assumptions 1, 2, and 4 hold, and we use the same initial purameters, X, and M as in Theorem 3. If we use the algoritim proposed in Remark 1 in Nesterov et al. (2018) with initial parameter wlth approximately solve the subproblem in line 4, each node requires at most O 0(//)) iterations to satisfy Eq. (9). ()) Remark 2. Suppose that the same assumptions hold as in Theorem 4. Then, if we use Nesterov's Accelerated Gra- dient Descent with initial parameter v!"" to approximately solve the subproblem in line 4, each node requires at most L O(V n+o log( ( )) iterations satisfy Eq. (9).
z;
Discussion: Eq. (8) shows that Inexact-PDO needs to solve the subproblem more accurately as the number of rounds increases, whereas Eq. (9) indicates that SPDO does not. Thus, as shown in Theorem 1, 2, 3, and 4, SPDO can attain the same communication complexity PDO while enjoying better computational complexity.
(r+1) - -0.")) = O, vf(a 1) + h(rr) + A (
and with this choice of h ((o(1)) (((tt1))
V f((((t))) Alg.
Alg. 3 recovers PDO.
6. Accelerated Stabilized Proximal Decentralized Optimization Method
5.1. Convergence Analysis
In this section, we show the convergence analysis of SPDO. The proofs are deferred to Sec. E and G.3.
In this section, propose Accelerated-SPDO, which can attain the best communication and computational complex- ities among the existing methods. We present the pseudo- code in Alg. 4. We use Monteiro and Svaiter acceleration (Monteiro & Svaiter, 2013) and accelcrated gossip averag- ing (Liu & Morse, 2011) in Accelerated-SPDo
Theorem 3. Consider Alg. 3. Suppose that Assumptions 1, 2, and 4 hold. Then, suppose that h (h, ())))
(0) n; = (0), and
X2
p (9)
V (a)
<
x
6.1. Convergence Analysis
10
We now provide the convergence analysis of Accelerated- SPDO. The proofs are deferred to Sec. F and G.5.
Note that arg minogae (.) has a closed-form solution.
6

---

Exploiting Similarity for Computation and Communication-Pliccall Decentralized Optimization
Algorithm 4 Accelerated Stabilized Proximal Decentralized Optimization Method (Accelerated-SPDOO
1: Input: The number rounds R, and hyperparameters 7, M, and
2: Au 0 and Bu 1.
3: for 0, ,, .......
do
4: Find ar+1 > O that satisfies À (A.ta.1))B
4741
5:
A,+1 = A, + a,+1-
6:
Br+1 = B, + pa,+1-
7:
for i ,.... parallel do
(r) A. 1
8:
y
A++1
9:
if 2 1 then
10:
h
FASTGOSSIP hh:
(1 (1
W, W, +VF((BI
))
end
(rti)) 2) arg eed
(x) where (x)) f((x) + (h1 (r) ,x) + +
(r)
a
yi
13:
0,
(r+1) arg min
ar+1
(Vii( (r+ b)) (" ,)) + # - z (- 2
1|3
+ B
110
(-2 1|2
W, 7, (++1) FASTGOSSIP
a (r++)
14:
2.
15:
(r+1) FASTGOSSIP
W, M, 7,
16:
end for
end for
(r+h)
B,41 (Brv (1) p0r410; (rt ar+1 (Vii(m (1+ + )()))))
This update rule can be rewritten v;
Algorithm 5 Fast Gossip Averaging
communication where ((r) == 1 E D (r)
1: function FASTGOSSIP((a: J W. 7)
Conver Case: Suppose that = O. When x = 2085,
2: a a; and a (-1) a; for all i.
M Z 2/1-p log(max( 121, 203846]/z
=1"""" }), and ?
for m 0, ..... M do
4: a (m=+1) (1 + 7) Σラ= Wija (m) ya;
(m-1)
I-p it holds that f(x(R)) - f(xx) S holds after 1 1+0=
5: end for
6: return a: (M)
O(v
rounds. Thus, it requires at most
7:
end function
8 [())) x
log max [ 81) x= 11
Theorem 5. Consider Alg. 4. Suppose that Assumptions
p)c
2, and hold. Then, suppose that h Vh; (v)
communication.
(0) (0) 600), and
4; U.
Theorem 6. Consider Alg. 4. Suppose that Assumptions 1,
Σ
(m )
2
22 (10)
(++))
2. and 4 hold, and we use the same initial parameters, % X, and M as in Theorem 5. Then, if we use the algorithm proposed in Remark in Nesterov et al. (2018) with initial parameter y; (r) to approximately solve the subproblem in line 12, it requires most Oly 4t) iterations satisfy Eq. (10).
352 1=1
1=1
Strongly-convex Case: Suppose that > O. When A =
1- 965, M si-p log( (192619))H)) ) and 7 14 26a
it holds that (R) f(x*) < holds after R
Remark Suppose that the same assumptions hold as in Theorem 6. Then, if we use Nesterov's Accelerated Gradient Descent with initial parameter y,
0 V 1 log(1 + min( -a''l")) rounds. Thus, it requires at most
(r) to approxi- mately solve the subproblem in line 12, it requires at most O u+8 log(())) iterations to satisfy Eq. (10).
0 (v
p 5
(22 + 8)
log
p(1 pp)
1
6.2. Discussion
min [1, (0)) x 1
log 1+
In this section, we compare Accelerated-SPP5 with the existing state-of-the-are method, (Inexact) Accelerated

---

Exploiting Similarity for Computation and Communication-EEfiicce Decentralized Optimization
Regularization:
L2 Regularization: 0
L2 Regularization: 0.01
L2 Regularization: 0.01
10P
10a
16f
10:1
10:1
10
10
30--
10-2
10:3
10-3
10:4
19-
10-4
10:4
10
10-5
10-4
10:4
500
1500
2000
500
1000
1500
2000
4500
6000
Communication Cost
Computational Cost
Communicction Cost
Computational Cost
Adaptive number of local steps
L2 Regularization: 0
L2 Regularization: 0
L2 Regularization: 0.01
L2 Regularization: 0.01
10a
10a
10a
10a
10r4
19a3
10-3
10-1
10-3
10-2
10-1
10
10:4
10-4
10
10:4
10
10:4
10:4
10:4
500
1000
1500
2000
200
400
600
800
1000
1200
5:00
1000
1500
2000
200
400
600
600
1600 1200
Communication Cost
Computational Cost
Communication Cost
Computational Cost
Gradient Tracking
Inexact-PDO
SPDO (ours)
Inexact Accelerated SONATA
Acce Pccelerated-SPDE (ours)
(b) Fixed number local steps
Figure 1. Convergence of the gradient with a 0.1. In (a), ran gradient descent until the condition for approximate subproblem solution was satisfied for all methods except for Gradient Tracking. For Gradient Tracking, we ran gradient descent for 10 times, (b), we ran gradient descent for 10 times approximately solve the subproblem. See See. H for more detailed setting.
SONATA (Tian et al., 2022). Tian et al. (2022) assumed that f is strongly convex and μ S 6max. Thus, in the following, discuss the case when fi is strongly-convex, μ S and
the strongly-convex case, whereas Sicelerated-SPDD can accelerate in both convex and strongly-convex cases.
4 8mxx See Table for the results.
6.3. Discussion on Federated Learning
In this section, we discuss the relationship between our PDO-based methods and the existing methods developed for federated learning. Decentralized optimization gen- eralizes federated learning, and when the underlying net- work is a complete graph, decentralized learning becomes equivalent to federated learning. PDO recovers DANE (Shamir et al., 2014) when the graph is fully-connected (i.c., Wi = 1.) SPDO and Accelerated-SDD S-DANE and Accelerated-S-DA.r special instance, respectively. Note that when the graph is fully-connected, p and multiple gossip averaging is not necessary. Furthermore, since Σm= h 0, the technique we proposed in Sec. is also not required (see the discussion Sec. 5). However, in decentralized optimiza- tion, the network is generally not fully connected; hence, these techniques become essential to ensure convergence.
Computational Complexity: Accelerated-SPPE can achieve the best computational complexity among the ex- isting decentralized optimization methods. Accelerated SONATA needs to solve the subproblem exactly, which is in- feasible in general. Inexact Accelerated SONATA solves the subproblem approximately and can achieve ((log( ()) computational complexity. Compared with these results, Accelerated-SPIe SPDO can achieve (log( )) computational complexity. This is because Inexact Accelerated SONATA requires more precise subproblem solution the number of rounds increases, while Accelerated-SPDO does not.
contain
(Jiang et al., 2024b) as
Communication Complexity: Accelerated-SPDO can achieve the best communication complexity among the isting methods. In the worst case, 8 can be equal to d m and Soeeleraeed-SPDo attains the same communication com- plexity as (Inexact) Accelerated SONATA up to logarithmic factors. However, can be significantly smaller than 8max- In this case, Accelerated-SPie can achieve better commu- nication complexity.
7. Numerical Evaluation
Experimental Sctup: We used MNIST (Lecun et al., 1998) and logistic loss with L. regularization, We set the coefficient of L2 regularization ber of nodes to 25. We used the ring as the underlying
and 0.01 and the num-
Acceleration in Convex Case: (Inexact) Accelerated SONATA has been shown to accelerate the rate only in
8

---

Exploiting Similarity for Computation and Communication-EPiiienn Decentralized Optimization
Gradient Tracking
SPDO (ours)
We first introduce the proximal decentralized optimization (PDO) methods and analyze the communication and com- putational complexities. We then propose SPDO, which can achieve the same communication complexity as PDO while enjoying a better computational complexity. Finally, we propose Accelerated-SPDO, which can achieve the best communication and computational complexities among the existing methods. Throughout the numerical experiments, confirmed that proposed method can outperform the existing methods as shown by our analysis.
at 0.1 (large 8)
07 1.0 (small 6)
10
10
17/000
10--
10-3
10-3
10-3
10
10
10-1
10-9
500
1000
1500
2000
500
1000 1500 2000
Communication Cost
Communication Cost
Figure 2. Convergence the gradient norm with different a. We set the coefficient of 1.2 regularization to 0.01. For SPDO, we approximately solve the subproblem as in Fig. I(a).
Impact Statement
network topology and distributed the data to nodes by us- ing Dirichlet distribution with parameter 2019). For Inexact-PDO, Inexact Accelerated SONATA, we used gradient descent
0 (Hsu al.,
This paper studies communication and computation-efficinn decentralized optimization methods. Our work mainly fo- cuses on theoretical aspects of decentralized optimization, and there specific societal consequences that must be highlighted here.
SPDO, and Accelerated-SPDD with stepsize to solve the subproblem approximately. We set the number of communications to 2000 for all methods and tuned other hyperparameters, e.g., A, M, and v/, to min- imize the norm of the last gradient for each method. See Sec. H for more detailed setting.
A Acknowledgments
This work was done while YT visited the CISPA Helmholtz Center for Information Security. YT was supported by JSPS KAKENHI Grant Number 23KJ1336.
Results: Fig. ((a) indicates that Accelerated-SPDO can achieve the best communication and computational com- plexities. SPDO achieved the same communication com- plexity as Inexact-PDO while enjoying a better computation complexity. These results are consistent with Theorem and 3. In Fig. 1(b), we ran gradient descent for 10 times to solve the subproblem approximately. Accelerated-SPPe SPDO achieved the best communication and computational com- plexities as in Fig. (a)) The results indicate that SPDO outperforms Inexact-PDO in both communication and com- putational complexities. This is because the condition for an approximate subproblem solution Eq. (8) is not satis- fied when the number rounds is sufficiently large, which makes Inexact-PDO need to communicate more.
References
Bubeck, S. Convex optimization: Algorithms and complex- ity. In Foundations and Trends in Machine Learning, 2015.
Cao, T., Chen, X., and Scutari, G. Deatalyst: A unified accelerated framework for decentralized optimization. In arXiv, 2025.
Güler, O. New proximal point algorithms for convex mini- mization. In SIAM Jourmal on Optimization, 1992.
Hsu, T.-M. H., Qi, H., and Brown, Measuring the effects of non-identical data distribution for federated visual clas- sification. In arXiv, 2019.
Efffet of Similarity 5: Figure 2 compares the convergence behavior with different a. As a increases, nodes come to have similar datasets, i.e., ö comes to be small. The convergence behaviors of Gradient Tracking were almost the same in both cases, whereas SPDO can converge faster as a increases. This observation was consistent with the comparison in Table 1. Gradient Tracking is not affected by data heterogeneity, while it still requires a certain amount of communication even though nodes have very similar functions. In contrast, SPDO can exploit the similarity of local functions and reduce the communication complexity when nods have similar functions.
Jiang, X., Rodomanov, A., and Stich, S. U. Federated optimization with doubly regularized drift correction. In International Conference on Machine Learning, 2024a.
Jiang, X., Rodomanov, A., and Stich, S. U. Stabilized proximal-poine methods for federated optimization. Ad- vances in Neural Information Processing Systems, 2024b.
Karimireddy, S. P., Jaggi, M., Kale, S., Mohri, M., Reddi, S. J., Stich, S. U., and Suresh, A. T. Mime: Mimicking centralized stochastic algorithms in federated learning. In arXiv, 2021.
8. Conclusion
In this work, we develop a communication and computation- efficient decentralized optimization method. To achieve this,
Khaled, A. and Jin, C. Faster federated optimization under second-order similarity. In arXiv, 2022.

---

Exploiting Similarity for Computation and Communication--Piieen Decentralized Optimization
Khaled, A. and Jin, C. Faster federated optimization under second-order similarity. In International Conference Learning Representations, 2023.
Liu, Y., Lin, T., Koloskova, A., and Stich, S. U. Decentral- ized gradient tracking with local steps. In Optimization Methods and Software, 2024b.
Koloskova, A., Loizou, N., Boreiri, S., Jaggi, M., and Stich, S. A unified theory of decentralized SGD with changing topology and local updates. In International Conference on Machine Learning. 2020.
Lorenzo, P. D. and Scutari, G. Next: In-network noncon- vex optimization. In IEEE Transactions on Signal and Information Processing over Networks, 2016.
Monteiro, R. C. and Svaiter, B. F. An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods. In SIAM Journal Optimization, 2013.
Koloskova, A.,
Lin, T., and Stich, S. U. improved analysis of gradient tracking for decentralized machine learning. In Advances in Neural Information Processing Systems, 2021.
Murata, T. and Suzuki, T. Bias- variance reduced local SGD for less heterogeneous federated learning. In Interna- tional Conference Machine Learning, 2021.
Kovalev, D., Koloskova, A., Jaggi, M., Richtarik, P., and Stich, S. A linearly convergent algorithm for decentral- ized optimization: Sending less bits for free! In Interna- tional Conference Artificial Intelligence and Statistics, 2021.
Nedic, A. and Ozdaglar, A. Distributed subgradient methods for multi-agent optimization. In IEEE Transactions on Automatic Control, 2009.
Kovalev, D., Beznosikov, A., Borodich, F. D., Gasnikov, A., and Scutari, G. Optimal gradient sliding and its applica- tion to optimal distributed optimization under similarity. In Advances in Neural Information Processing Systems, 2022.
Nesterov, Y. Lectures on convex optimization. In Springer, 2018.
Nesterov, Y., Gasnikov, A. V., Guminov, S., and Dvurechen- sky, P. E. Primal-duse accelerated gradient methods with sialll-diennsional relaxation oracle. In Optimization Methods and Software, 2018.
Lecun, Y., Bottou, L., Bengio, Y., and Haffner, P. Gradient- based learning applied to document recognition. In IEEE, 1998.
Patel, K. K., Glasgow, M., Zindari, A., Wang, L.,, Stich, S. U., Cheng, Z., Joshi, N., and Srebro, N. The limits and potentials of local SGD for distributed heterogeneous learning with intermittent communication. In Conference Learning Theorry 2024.
Li, B., Cen, S., Chen, Y., and Chi, Y. Communication- efficient distributed optimization in networks with gradi- ent tracking and variance reduction. In Journal of Ma- chine Learning Research, 2020.
Pu, S. and Nedic, A. Distributed stochastic gradient tracking methods. In Mathematical Programming, 2021.
Li, Z., Shi, W., and Yan, M. A decentralized proximal- gradient method with network independent step-sizes and separated convergence rates. In IEEE Transactions on Signal Processing, 2019.
Rockafellar, R. T. Monotone operators and the proximal point algorithm. In SIAM Journal on Control and Opti- mization, 1976.
Lian, X., Zhang, C., Zhang, H., Hsich, C.-J., Zhang, W., and Liu, J. Can decentralized algorithms outperform central- ized algorithms? case study for decentralized parallel stochastic gradient descent. In Advances in Neural Infor- mation Processing Systems, 2017.
Scaman, K., Bach, F., Bubeck, S., Lee, Y. T., and Massoulié, L. Optimal algorithms for smooth and strongly convex distributed optimization in networks. In International Conference on Machine Learning, 2017.
Lin, D., Han, Y., Ye, H., and Zhang, Z. Stochastic distributed optimization under average second-order similarity: Al- gorithms and analysis. In Advances in Neural Information Processing Systems, 2023.
Scutari, G. and Sun, Y. Distributed nonconvex constrained optimization over time-varying digraphs. In Mathemati- cal Programming, 2019.
Shamir, O. and Srebro, N. Distributed stochastic optimiza- tion and learning. In Annual Allerton Conference on Communication, Control, and Computing, 2014.
Liu, J. and Morse, A. Accelerated linear iterations for distributed averaging. In Annual Reviews in Control, 2011.
Shamir, O., Srebro, N., and Zhang, T. Communication- efficient distributed optimization using an approximate newton- method. In International Conference on Machine Learning, 2014
Liu, Y., Lin, T., Koloskova, A., and Stich, S. U. Decentral- ized gradient tracking with local steps. In Optimization Methods and Software, 2024a.
10

---

Exploiting Similarity for Computation and Communication-Pficien Decentralized Optimization
Shi, W., Ling, Q. Wu, G., and Yin, W. Extra: An exact first- order algorithm for decentralized consensus optimization. In SIAM Journal Optimization, 2015.
Solodov, and Svaiter, B. hybrid wrojection-proxima point algorithm. In Journal of Convex Analysis, 1999.
Solodov, M. V. and Svaiter, B. F. A unified framework for some inexact proximal point algorithms. In Numerical Functional Analysis and Optimization, 2001.
Sun, Y., Scutari, G., and Daneshmand, A. Distributed opti- mization based on gradient tracking revisited: Enhancing convergence rate via surrogation. In SIAM Journal on Optimization, 2022.
Takezawa, Y., Bao, H., Niwa, K., Sato, R., and Yamada, M. Momentum tracking: Momentum acceleration for decentralized deep learning on heterogeneous data. In Transactions on Machine Learning Research, 2023.
Tian, Y., Scutari, G., Cao, T., and Gasnikov, A. Acceleration in distributed optimization under similarity. In Interna- tional Conference on Artificial Intelligence and Statistics, 2022.
Wang, J., Sahu, A. K., Yang, Z., Joshi, G., and Kar, S. Matcha: Speeding up decentralized SGD via matching decomposition sampling. In Indian Control Conference, 2019.
Xiao, L., Boyd, S., and Lall, S. A scheme for robust dis- tributed sensor fusion based on average consensus. In International Symposium on Information Processing in Sensor Networks, 2005.
Yuan, K., Ying. B., Zhao, X., and Sayed, A. H. Exact diffusion for distributed optimization and learning -pat Algorithm development. In IEEE Transactions on Signal Processing, 2019.
Yuan, K., Huang, X., Chen, Y., Zhang, X., Zhang, Y., and Pan, P. Revisiting optimal convergence rate for smooth and non-convex stochastic decentralized optimization. In Advances in Neural Information Processing Systems, 2022.
Zindari, A., Luo, R., and Stich, S. U. On the convergence of local SGD under third-order smoothness and hessian similarity. In Optimization for Machine Learning, 2023.

---

Exploiting Similarity for Computation and Communication-Efiicent Decentralized Optimization
A. Comparison of Communication and Computational Complexities in Convex Case
Table 2. Summary communication communication and computational complexities in the convex setting.
Algorithm
Reference
# Communication
# Computation
Assumptions
Gradient Tracking
Koloskova et al. (2021)
0
Ldc
(e)
1,2,4
(1-p)
[1 [1-00
Exact-PDO (SONATA)
Theorems 1, 2
(1-p)t
448
log (1)
n.a.
1, 4
Inexact-PDO
Theorems 2
6dh
log
(4)
VaLah log
1,
1T-ple
(8)
Stabilized-PUI [new]
Theorems 3, 4
[1 log (*)
1,2,4
Accelerated SONATA
Tian (2022) Tian et al. (2022)
n.a.fc)
Inexact Accelerated SONATA
Accelerated Stabillied-PDO [new]
Theorems 6
Ed (1-p)-
log max
8
dif
1,2,4
(a) It holds that < L, and & L holds when nodes have similar datasets.
(b) Sun et al. (2022) did not analyze the communication complexity of SONATA in the convex case, while our new theorem, Theorem 1, is the first analyze it.
(c) "n.a." represents that we need solve the subproblem exactly.
(d) ó is smaller than dmn and be most / times smaller than dmix.
12

---

Exploiting Similarity for Computation and Communication-Efiiient Decenttt Optimization
B. Comparison with Lower Bound
In this section, we compare the communication and computational complexities of Accelerated SPDO and the lower bound. Communication Complexity:
Tian et al. (2022) showed that lower bound requires at least
log
communication to achieve f(x) f(x*)= = c. Our Accelerated SPDO can achieve the following communication complexity:
1 + p log
[1 +
min 8) [[x)) xx' 1=1
log 1
1252
Thus, when 8 2 μ. Accelerated SPDO is optimal up to the logarithmic factor.
Computational Complexity: For non-distributed cases, any first-order algorithm requires at least
T,
xx
Ω
log
gradient-oracles to satisfy f(x)- f f achieve the following computational complexity:
< c (See Theorem 2.1.13 in Nesterov (2018)). When 5 2 14, Accelerated SPDO can
o
(V
L 14
M u||
x=1 1|2
log
1
when we use the algorithm shown in Remark in Nesterov et al. (2018) (see Theorem 6). Thus, computational complexity of Accelerated SPDO optimal up to constant factors.
13

---

Exploiting Similarity for Computation and Communication-Plicce Decentralized Optimization
C. Technical Lemmas
C.1. Basic Lemmas
Lemma 2. For any a, b E Rd, it holds that for any a
Ka, b)l - 2a
||a|2
+ a
マ 111b1
(11)
Lemma 3. For any a, b E & and y > 0, it holds that
||a + bll? & (1+
|all
+ (1) [|61].
(12)
Lemma 4. For any a1, a2, On E Rd, it holds that
1 Σ |
||a|| -
(13)
1=1
where à = -ド=1 aç.
Lemma 5. For any a,,..., an E R and b E IR, it holds that
1 Σ
a. b112 laa
b||2 +
1a
-
(14)
1=1
Proof. See Lemma 14 in Jiang et al. (2024a).
C.2. Useful Lemmas
Lemma 6. Let 21 ....... Na be vectors in Rdd and W E Raxn be matrix that satisfies Ei= WTj = 1. Let x. = Σラ=1 Wy Then, it holds that
Bi.
Proof. We have
W Wy
Wip
Ejj.
i=
1=1
i=1
j=1
This concludes the statement.
Lemma 7. For any matrix X E BRdd and any matrix W E TRaxn that satisfies Assumption 4, it holds that
IIW - x|x| || $ |
(15)
Proof. We have
[I
f)x
5
W
1 1 X
+
1 -
-1)
7
(5)
L 1 T
(0
+ 1)
x
<
1
1
|
op
where 1, is n-dementional vector with all ones and we use < the last inequality. Using obtain the desired result.
| 11, llop S 1, we
14

---

Exploiting Similarity for Computation and Communication--Piiienn Decentralized Optimization
Lemma 8. Let J&: R - Ik be a function that satisfies Assumptions 2 and W E B be a matrix that satisfies Assumption
p Let (12) yn R.R. be a set of vectors in Red and define the update rule of (h
1 Timi as follows:
(r+1) h
Σ Wii (n +V(s(a)))) V.((a))).
Then, when Ei= !n = 0. holds that for all r
h 0,
(16)
and
g(r+1) S 4p2 + 4p2282 - + -3222=((+1)
(17)
where g(r) = = Σ. (1 - V/u(E!t))12 and =(++1) = E ||ا! (r+1) (12
Proof. We have
Σ
Σ Wij (n + v[b(att1)) ((i(a((t))
i=1
1=1
>
n
Σ Wis (n)* + v((a)()1) - (V((((tt))
h
Since Σm= h
0, it holds that Ei (r())
0 for any r. For the second statement, we have
(++1 Vh, (
2
Σ Wis (
+ (iz(t((t))) -vF()))))))
2
Σ (Wig - -== (ff)(a//t))) - (
n
2
Σ Wij (h," v(( [[(x((+1)
32
()((az ( |
1=1
2
Σ Wij (n)" ([
v[(x(++1)
321,2 n
(r+1)
x
n
n
15

---

Exploiting Similarity for Computation and Communication-Pfiicenl Decentralized Optimization
where 1= is indicator function. Using Eq. (16), we obtain
1
(++1)_
(ha(a(rt!>!!
(5) 2p
( 32L 2
Σ
1/2" (=
(r+1)
2;
=11
i=1
(12) 40²
Σ
) |n.7)
4p²
n
(o:(t)))1)) ()())
/
32L " +
x (r+1))
(1(+1))
"
n
40
32L
Σ
+ 162
(r-1)
x
This concludes the statement.
Lemma 1. If Assumption 2 holds, there exists 8 such that 5 S L and Eq. (3) holds.
Proof. We have
2
[V((()) - 2
(Vi(()) - VVly), Vf(x) - v)(2)) + [V/(2) - v
[V+( V
< L - - -
where we use Assumption 2 in the last inequality.
16

---

Exploiting Similarity for Computation and Communication-lffiieee Decentralizd Optimization
D. Proof of Theorem 1
Lemma 9. Suppose that Assumptions 1 and 4 hold, and Ei=1 (0) = 0 and M = 1. Then, it holds that
f(x²)
A
(r)
x
+
1
g(r)
(18)
2n
20
i=
1
2
((
+
1 + A
n
(1+1)
x
|
+
1
11
+ X
- 5
1++ A
E(++1)
2n
x²
2
2
i=1
6) 2)
|
A
Σ
n
(r+
(r)
+
z
x
4
4n
n
VF,, (1+t {)) -z, ((+
x
n
where E(r)= == 1 Ei=1
|00 (r) - 1 and g(r) = -/ -ー (1 [1b())- - (1)))
Proof. We have
fi(x²)
+ 2
(r)
- ==11
2 [(x0 (()) + (0) b) b)) + A (0; (r+2)
- =!!") x² - -x0 a((+b))
(r+b)
-20(0) 2
+ x
(r+ 2))
2
+ 2
x
+
xx"
!)
2 1(x()+1))= + ([(((((+)))) ), 2 (r+2) - xx(++1))
(V ((t)) + x a (rtb) - =x("²) x - -x; (2,(+)))
(r+b))
A (r+ + Σ 2
- {
(r+b)
2
x
x
2
where we use the fact that f((x)) + } [| m! 1011 is (μ + st-stnlygly convex in the first inequality. From the definition of (), we have
(z (++ = Ví(a (1 + nna") + A (z, (1- - 2!"))
-x("))
Using the above equality, we obtain
f(x²) + > | - 0²12 2
2 (((()+1))++ + V (
(r+b) ( x((2)) ) + ( (1("") 2i
(1) (r+b) x
+ (VF,,. (z) ( x - x (1+2))
A (++ - -0(""1] ||
r + A
(r+ b2
+ ž |
+
x
x='
2
By summing up the above inequality from i = 1 to = n, we obtain
Ao
x ( - x. 001
f(x*) +
2n
2 f(z(r+1)
+
1 11
(f(((()))),
x (++ - - + (h!" 1z
(r+
x²)
n
+ Fir ( x
- (+t))
+ d (++ x x-(r)) l| + 1e A (r+
x+1 001
x
2 x
2
)(((r+())
1 1 Σ (
) 20 ((())t) x((+t)) -
+ (V/i(z())) ():( x (m-b)) x(++1))
+
n
+ ( (2) (
x -2((+x+))) (+))))
+ 2 x
- 2//0||²
(r+
+
x x
2
2
17

---

Exploiting Similarity for Computation and Communication--Piicee Decentralized Optimization
where we use Eq. (16) in the last equality. Then, we have
1 n
(r+
x²'
(r+1)=
x²
(++
(++ 2
n1
i=1
(11)
(r+1)
x
fr+1) - x| ? + ||ا (1+ - -
i=1
(5) 1
Σ
(((++())
x
||
1) | - alrto|())
+
n
1=1
where we use the fact that we have
Σn=
(r+ 2)
Em=
(r+1) in the first equality (see Lemma 6). Using the above inequality,
A a
f(x²)
+
x²
2n
1=1
2
(
+
11 + A
/
(r+1)
x² 2
2n
1
Σ
hh: (h.(z!))), xi (x+ x((2))) + (h()))()))
(h.(t((t1))).a ((( s((21))
+
n
(VFr.(ac x= m (r+))))
+ A 2 1z (+t))) - mm!h||
+ ++ x
p2 -1) | -
Then, using Eq. (11) with a 8, we obtain
fax0)
+ x
x
(r)
xx"
2n
1=1
(3)
f(x(r11)) + + x
(r+1)
2
x=*
2m
1=1
h - <)>( ||²
5
(,)) - x 2
|² 8 |n! (, x(( ?
26
2
(=1
(z. (
)²
x - xz
(rtb)))
(r+
- //"'// -ao-->"")
a a+ (// -1) | (ot - -
2
(5)
2 f(f(r+1))
+ #
(r+1) x²
2n
+ Σ
n
h - Vh((z(>>))'
l|²
5
[(( - -((+ ?
28
2
(1F (1+b))) ,x
x - -x ((+))))
+ d
(x+
- mp /-)12
p 1++0
111--
6
(14)) - x ((+ 12)
+
+
x
2
2
(13)
2 ((
+ 1e + x
Σl
n
|00 (o((tt))
0.1 |
2n
n
14 - /i((a(t))))
||=
+ (A)
6
()()))  2
n
28
V. (a) (((+t)))))).) x - (1++))
+ >
(r+
x
|0>|²
+
[++ x
-1)
x
x+1) 260+1)
4
2
p2
2
18

---

Exploiting Similarity for Computation and Communication-Pfiiienn Decentttriiinieeeeaellerliiia Optimization
This concludes the statement.
Lemma 10. Suppose that Assumptions 1, 2 and 4 hold, Di=1 i=1 h2 = 0, M- = 1, and
(0)
p
S
79
Then, when x= = 45, it holds that
fxx)) +
26 2
Σ
(r)
x²
2
1
E(r)
(19)
11
8
2 f( + ( +
1
26
(r+1)
x²
|| x
2
(1+
H g(r+1) 48
46
i=1
n
(r+2)
- x 1/("//²
Fii (1+2)) ) x= x; (r+b))
(r+
Proof. Since 8 S L.
p S 67. implies that p S 3. Using p S 1 and Lemma 8, we obtain
g(r+1)= S pp + 5²p - - + +3212
(20)
Using x = 45 and Eq. (18) + +1 ) Eq. (20), we obtain
f(x²)
+ 46
| (r)
xx
P
11 +
11
) g())
25
45
((t(++1))
+
+ 48
Σ
(r+1)
x
1
[ +
g(r+1)
2n
45
i=1
1
+
46
1
+ 48
32L
(1+
1
3(+33)
2
2
8
48
6
(1
6p
2
48
5
(r+
b)
(n)
2
1
(z) (1+ x - x2 (1+t))
V
Using the assumption on p. we have
1
P
+
S 8'
28 8
48
u +
46
1 + 48
L2L
8
(1
2 0,
2
2
8
48
8
8p
(1
+ /
2 0,
2
48
where we use μ S L and 8 < L. This concludes the statement.
Lemma 11. Suppose that Assumptions 1, 2 and 4 hold, M 1. x = 2(0), (0) = vf(z - (z(( and
8
p S GL
F (2)
er+1
a + (7)
x0
19

---

Exploiting Similarity for Computation and Communictionn-Piiccent Dicentttiiiieteeeeaelaalaaiia Optimization
Then, when x= = 45 and Σ er S
6(46+1)) we obtain
E f(ā(r)) -f(x*)
2 -
46
(0)
x²
x²
9"
P 45
R
R
Proof. From Eq. (19), we have
f( - f(x²) + (1+
1²)
26
(1+1)
x² 2
11
1
+ 5
(r+
(r)
+ 8
4
==1
28
(r) x² ||
|
+ x
1
g())
+
V (2 (,+t))
1 (r+
xr
x²))
1=1
x=1
28 N
(r)
2 x² ||
1 8
E(r)
y V
(rt b) 11²)
Σ
(rt
2)
-0- 17)
+
2
T
where we use Cauchy-Schward inequality in the last inequality. Using ( = 0 and dividing the above inequality by 46 we obtain
2
2
( - -(xx))
+
1
Σ5
(r+1)
x=
25
(r+
- a!! (13)
45 + 10
72
45 + 1
1=1
t=1
45
1
(r)
x=1
11
2
1
Virr (3 +) ()))))
12)
12)
1
Σ
(r+ () x= 11
46 + u.n
x
+
46 + # \
n
n
x
Using the following notation.
1
(r+1)
2
Ar41 ==
2
x²"
n
i=1
1 n
(r+ b)
xx //
B,41
2
n
1
CM+1 ==
71 i=1
48
q == 48 + p
we can simplify the above inequality as follows:
2 ( + Art1 +
28
2 / Ar+11
By4 S 9A, +
45 + 1
48 +
45 + p
Dividing the above inequality by gr+11 and summing up the above inequality from r = tor = R 1, we get
2
(x f(x*)
An +
28
Br <
2
R
VCA,
Ao +
48 + P
R
46
1
48 + 1
9"
Define QR as follows:
2
R
VC,.A
QR Ao +
46 +
q"
20

---

Exploiting Similarity for Computation and Communnication-Pfiicce Decentralized Optimization
The above inequality implies that AR S QRQ for any R. Using this inequality, get
2
VCR+1AR+1
Qn+1 -Qn
45 + 1
2
CntIQR+1
46 +
gftt1
Since we now get the recursive inequality about QR. we obtain the following by using Lemma 12 in Jiang et al. (2024a).
R
QR S 2A0
Σ
(40 + 11)2
q"
Then, by using
|VF Σm=
(2;
(r+ ( S cx+1 Ei=
(r+
x
(r)
11 we have
2
R
f( - =(xx)
+
Ar
+
20
Σ
Br
S 2Ap +
8
Σ
R
Exbi
48
9"
q
46
+
df
(48 + p)
o
r=1
r=1
8
Br
$ 2A
cr
(48 + pt)
q'
where we use Cauchy- Schwwrz inequality in the last inequality. Using the assumption that >
er
S
6(48-1) pn)
we get
4
((x(r))
f(x))
a
(0)
2
x
45 + 1
7
Thus, we have
E r=1
R
[(x(r) - f(x²)
d¹
(1
15)
P
1 n
Σ
2
(0)
x²
1
<
46 1
R
x
(0)
x² 1|2
i=1
1=1
This concludes the statement.
Lemma 12. Suppose that Assumptions 1, 2 and 4 hold, and x. (0) =00), 110) v)(((0)) - (.((
and
(x. (1+ 8) 1| v 4(r + 1) + 2)
5(45 + 14)
(r+
x (r)
1=1
log( o4)
Then, when X 45 and M 2
1-p we obtain
R
(r) f(x²)
2
46
(0)
x.
())
xx*
R
9"
(1
R
R
1=1
46
Proof. When M log( (
holds that
1-p
M 8
6T.
where we use log(z) 2 1- - 1 Furthermore, it holds that
R 8(45 + +1)
5(48 + 1))
1
1
8(45 + 1)
4r(r+1)
4
T
r+1
Thus, from Lemma 11, we obtain the desired result.
21

---

Exploiting Similarity for Computation and Communication--fiiee Decentralized Optimization
E. Proof of Theorem 3
Lemma 13. Suppose that Assumptions I and 4 hold and the following inequality is satisfied:
Σ (el 11
2²
o -x x; 1
(21)
10
Then, when Ei=1 11 = 0 and M- = 1. it holds that
f(x²)= + 2n i=1
x
+
1
g(r)
+ +252(r)
(22)
20
2 f(x()+)))
+ 11
+ A
n
(1+11)
x01
+
A + 1
(
2/2 -1)))
-1 g(+t))
+ A
- v(rt1) 2
2n
2 p²
8
( A
36)
|0(1) - x (r+
+
12
2
where 3(r) == 1 >
(0.0) - slal|
and g(r) = Σi
Proof. We have
A n
0/ x²1 11
f(x²)
+
Σ/
2n i=1
fx(") + 2/1 -1000) xx0 11)
M(x ((()) + ( (\iiaa (11)) ) x - xz! ).!t1))
+ /1 (r+1)
x - -x11( -
+ 2 0. - x" 201²²)
2
n 1
Σ
+ (v (((
x. (1+1) (
+ (Vri(a) (+t)_)))))))
) x x ((+t1))
4
(r+1))
x11 + 2タ " -
-, =01²))
x
2
Using the following equation,
a - (o((t)))) a((t1)).
(((a((+!)) (r+2) x(0+1))
get
f(x')
+
A
|| 1/!")
x= ||
2n
i=1
2 ((((++))
+ 1
Σ
n
Vh.
(2 x ((11)) - a
1=1
+ Vfllz( (1) x= - xi
(r+1))
1
(r+1)
A (1)
2 1
(1+1)
+
x
x²
+
x=-
+
x
2
2
2
T
Note that hy (x)= = f(x) - f((x)) Using Eq. (16), we obtain
n Σ Vii(a + n,", .x)) + (V/i(a((t)) --xt))))=((+)))) (o((tt))) + a -x
(16)
n
(r+1)
x+|
+ X
101
x=*
x
2
2
22

---

Exploiting Similarity for Computation and Communication-Pficcee Decentralized Optimization
We define (v) = (V)(aa{())) + 2 v) + - - m
11
1|2 + 1 of 1p..
By using that fact that Gi is
(m + A)-strongly convex, we get
n
Σ
1/ (.(( (11)) + h (r), vi
( + (V (1 - -m(rtti)
+ 1
2 m 11(--))
of 2
?
12
A
+)
p| +
u
| (r+t)) x
2
-
ia
2
(14)
1
Σ
( (ar (++ 11
+ n n² ii (())))) + ( (Vri(as (1 -a0 ( ) +
(r+1)
(++
ax
ii
(++ b)
A 1
(++b) bi++
2 + A
H H (f(t))) x=* ||]
2
(14)
1
Σ
fi 1
+ 11. n1,7,, 2
(
+ (vfilae
) x (0+1))
)
+ M
(r+1) - 2/ (
x
2
0/7") - -
(r+ 2)
2
A x+ F
(r+b)
- و
+
2
2
x + 14
|| (1+1) x²
x + /
(r+1)
- 50-t2/19 119
2
2
Using the above inequality, we obtain
A
x=" 2
1xx) +
2n
+ A
(1+1) - x:" 2
||
2 [(xx(-11)
+
2n
Vh, (1s ) xx! (r+1) - 2 (r+))) ) + 1
2 a (r+1) - 3
- - ( 2
1=1
++/ / (++ - // A + 1
!oo |og - o[ ?
+ 2
2
([(((tttt)) + 1(()) u (((+)))= + (Vi(a((t))) -ao (iri
T
From the definition of Pi,., we have
V Fi. (x) = /i(x) + 11 + +(xx - v..)).
By using the above equality, T, ** can be rewritten as follows:
V Vi(an (1t)) ), my (++ - -. ,.(tt)) + (n!") (r) (r+2))
T
V Pi (1+1)) xxo0 - x ((+t1)), ) D. (+++)
20 (r+1)) ) + (n. , x (
(af(tt))))) ) o(()) - 2 1 + A | -z/
1/ 1|
+ ( (((+))))
(air ()) + \(o!!) - ((( u (++ )7"))
7:-
Then, Th can be bounded as follows:
T:
(11)
2
2
(ain (1t1)) + X(o!")
- x ( |-
31
8 p
|0! (r+
- (((1) 2
=-2 2
(ai
||= ? 4
(v.... (o.-"))
w. (r) - xz (1+1))
2x
(r)
(r+2)
2
31
(r+
0. (-
3x
3
3
8
x
8
2
23

---

Exploiting Similarity for Computation and Communication--Riieee Decentralizd Optimization
Using the above inequality, we get
7
A
3 0 x 1 + (n12 (1,",t oj
(r)
((+t))
2
(1 /²
3 (o oo -0 )
1
31
31
8 10 (++ 0, ?
(11) A (r) 2
|
||
2
+
n ,
(r) 10 (1+1))
5
V
P (1c (ar 11)
31 (r+
8 /
0. (r) 1
6Λ
Using the assumption that Σ E V.
(oi (2ttt)) 2
s t/b Σー |
- x
2
we get
n
n
0 (0)
x. // + (n"" _.(+))))
31 8
(r+
27
Using the above inequalities, we get
72
f(x') +
xx*
2n
2 (z((+)
/6 + x
(++1]
xx 1
+
0
2n
1
11
(++
+) 2
2
(0.") Di
(1 2
X (++
A 1
( - |1/t))) -g(+t||2
n
8
A
(n, (r) _0 (++)))) + (-V))( (- so! (1++1)
)(++1))
12
Ti
Th can be bounded by blow as follows:
n
T x*x
(16)
7
h (r)
(h((a(++1))) a.+t1) - 8(r)
1=1
i=1
())() -6(1) + (V -vh((a(t))) x - l(^))
-
b - V).()(()))
1|2 6 10. (11 -/r>)²²
(h)))()))- [ []]
28
28
(m) - </>(66>>)//
/|² - 8 xa (1+1) -
- 1/
(+))) a
28
2
28 x (++1) -, ?!-0]/
8 .( 20/12)19
28
28
2
24

---

Exploiting Similarity for Computation and Communication-lfiiienn Decentttriiiieeeeaitllaiaiiia Optimization
Using the above inequality, we obtain
f(x²)
+
U/
x²
)
/|=
+
28
Σ
12
2n i=1
28n
f(
11
+ A
(r+1) x*1
=12
2
+
2n
1
1
(r+1)
(1 2
X
(++
x+
A
(r+))
x (r+1) v(++1) /
0,
+
n
2
8
2
+
X
26)
r+
8
(()))
((+
12
(6)
(ax(+)2)
+
+
Σ
o! (++1)
x=1 || |
+
A + 1
-1 1
Σ
(++1)
(((+1) 2
2n
2n
i=1
11
(++1)
/
(r) Di
(+
>
- 26 -,:-) - x 1/
5 2
| - 2
+ o
+
n 2
12
Using Eq. (16), we get the desired result.
Lemma 14. Suppose that Assumptions I and 4 hold and the following inequality is satisfied:
VF, (x |
0/0 x 2r
(23)
10
Then, when X = 200, Ex= h (0)
0, M = 1, and p S 5
5T. it holds that
f(x²) + 100
(0(7) x
2
+ g + 28
i=1
2 ((x()))) + (1 +
108
(r+1) xx 2 1
_ g(rtt) + 28=
(24)
205
where E(r) ;= 1, Eim lo.")
- sluil? and g(r) = Ex |n00 - Vho
Proof. Since 8 S L.p p S 5t implies p S 1. Thus, using Lemma 8, we obtain
p 2 g(r+1) - poo 1000)) -32
(25)
By calculating Eq. (22) + Eq. (25) x {1 + 4), we obtain
||
1
+ p (1+ 4) g00) +205(r)
()
f(x*)+ +
x
+ 8
2n 1=1
2
2 (( + 1 >
Σ
|0. (1+11
2
1
[ + | g(r+1) + (1 + #)
( + -1
321²
2n
+ +(3
A - (1+ (1) gه ( |
x
36)
35
(p()) - -
12
2
25

---

Exploiting Similarity for Computation and Communication- Decentralized Optimization
By inserting À 200, we obtain
106 f(x)) +
(r)
2
1
(11
)) gir) + 2222())
x²
+
p
8
208
2 ((((++1)
108
(1+
+
(r+1)
x= 2=12
+
1 + 206
g(r+1)
208
1=1
+ 1
( 100
1
32L
((++1)
158
( +
pd)
|0000 00041)12
-
200
8
2
105
S 5Z implies that
1
+
P
1
+
1,
2
200
1
32L
106
26
0
56
(1
+
pd 2 0,
2
20
where we use u S L and μ
L. Using the above inequalities, we get
f(x*) +
108
(r)
xx
g(r) + 2r
n
2 f( +
105
1
+
11
x
+
1 [1+ 8
1b 208
g(r+1)
+2 (1+
205
206
1=1
Thus, can get the desired result.
Lemma 15. Suppose that Assumptions I and 4 hold and the following inequality is satisfied:
VF. (.. )
1
(r+1)
x;
(26)
10
Then, when x = 200, M- = 1, 11!0) ((0), h1 (U) [5(((())
v (0) and p Ps
5L we obtain
1
Σ wir) (f(z()+1)) - f(0')) -
1
(10)
x /|² 5
106
((0)
2
x=
WR R
2((1
#
R
R
206
where ur)r (1
208 y and Wn = RR-1 wt)
Proof. From Eq. (24), we have
f()(r+1)) - -f(x*)
< 1005
n
x²
+
1082
((r)
+
5
1 =0)
-108 (1
+
206
11
Σ
4
(r+1)
x
+
1082
1
g(++1)
+
5
1
-(+++1)
We define (r)
== (1 +
#. )r We obtain
205
R-1
1
Σ
(
- -fx))))))())))))))))))))}))))-
<
108
0
(0)
x=
+
1
WR
W R
n
1052
5
26

---

Exploiting Similarity for Computation and Communication-Pficcan Decentttaiiiieeeeilllaaaaiiia Optimization
where WR Ex=0
R-1 w Using g()) 0 and = 0, obtain
R
Σ (r)
() - -(xx))
106
x='
WR 1=
WR
Using WR 208 (1 +
1), we obtain
203
1 WR
Σ
R
wir
(f(alr())) - f(x*)) $
p
1
(0)
x²
1
106
0
(
2((1 +
R
R
==
Lemma 16. Suppose that Assumptions 1, 2, and 4 hold and the following inequality is satisfied:
VF, (2, (2t(t1))))
1
of x
(27)
10
When 0 = 6(0), (0)0 = v)(((())- ()(((())) x = 206, and M 2
log 1t)
holds that
I-p
Σ w (f(x()t))) - f(x*)) $ 2((1 +
R-1
p
11 0000
x²11
106
(())
x²
WR
R
1)
R
r=0
205
where wrrr (1+
# yr and WR D wit) 208
Proof. When M 2 I-p log( ( ), it holds that
8
DM
5T.
where we use log(x) 2 1 From Lemma 15, we obtain the desired result.
27

---

Exploiting Similarity for Computation and Communication-Elicceee Decenttalliieeee Optimization
F. Proof of Theorem 5
F.I Useful Lemmas
Lemma 17. When μ 44,11 it holds that for any r 2
(1+1
73
,2
A, z 4p
11
1
1
47
4A
4X
Otherwise, for any r 2 1, it holds that
1(r-1)
1
A,
2
1 1+
41
4A
Proof. See Lemma 12 in Jiang et al. (2024b).
Lemma 18. When = 0, it holds that for any 0 r R. R.
A, 1 X
(28)
Proof. Denote C. VAr. From the definition of A, and a,, it holds that
A(Crt1 - C2) C X(C+ C,,² A(Cr+1 +
+ C,)
Thus, have
C41-C; /
This concludes the statement.
Lemma 19. holds that for any 1,
-1
11 -1 1
41 v
A, <
2
1
+
(29)
p
ac+1
p
Furthermore, when μ = 0, it holds that for any r 2 1,
r Ar rr. r.
(30)
5 ac+1
Note that the inequalities on the right-hand side also hold when r 0 since a1
Ao
0.
Proof. From the definition of ar+1, we have
1 UA, + (1 + MA,)) 41A,(1 + HAA,)
nAA
0,41
2A
2A
1 + 14 + + (AA,)² 4XA,(1 +MA,)
+ MAr
41
0,41
1
1+
2X
2A
4
When = 0, we have
1+ 4AA
A.
A.
0
21
VAA,
1 VI 4AA,
5
5A,
0,41
A,
2A
XA,
T
where we use Lemma 17 and 18. This concludes the statement.
28

---

Exploiting Similarity for Computation and Communication-Ificccall Decenttral Optimization
Lemma 20. For all 0, it holds that
2) ( [+ 21) ( ( 41
ar-2
1
S 2
1+
(31)
ar+1
Furthermore, when μ = O, it holds that for all r 2 0,
Or+2
1 1
S 4.
(32)
0p+1
Proof. From Lemma 19, we get
(29)
Ar+1
41
S 2
(1 (1
1 1 1
A, + Or+1
(I+ () 1 +
41
(29)
ar+l
(1+ 21 22)
(1 4)
( (1+11
41
1+
S 2
p
p
1
When μ ===000000 0, we get
a,+1
Ar-1 1
(r
(r) 1)2
2(r + 1)
S
I 4,
0r
Ag
r2
ar+1
A A
21,
Gr
A,
where we use A,41 = Ar + 0x41 2 A,. This concludes the statement.
F.2. Main Proof Lemma 21. Suppose that Assumptions I and 4 hold and the following inequality is satisfied:
Fir (1t))))))))))))))))) /|
2
Σ
n
(r+b)
(r) 2
2
yi
352
1=1
Then, when M = 1, it holds that
(x(()))) + ar+1s(0*)
Br
0
(r)
x
Art1 g(r) + AA
333
+6
E(r) + 0804+150') =(r)
(33)
16
2 Art1 Art1s(1((t1))
+
Br+1
(r+1)
xx
2
UAA41
(r+11)
Br+1
1
-1
=
=(++1)
2n
2p²
2
12
i=1
+ AA+1 )
(r+
(r)
2
B,
(r++)
2
pa
n Σ
(r+
(r+
25
x
y
+
0
+
x
n 32
12m
2n
i=1
1=1
where =(1) := Σ
2
=(0))
= 100
- 560)
and (()) = Σ
|m - -0)
29

---

Exploiting Similarity for Computation and Communication-Eliciee Decentralizd Optimization
Proof. We have
n B
0 x=1 1
Arf(((l)) + #0+1f(x*)+
+
2n
im1
(1)
Art
fa
(1+b))
1
V (z) (1)) AA,,5() - A (r+b)
+ #a+1x*)
11
B
U/ (r)
x*1 ||
+
A.A,,
(r+2)
- =1/0 +
u0r+1
(r+ b))
- =x0
2n
2n
2n
i=1
1=1
A,41
fila; (r+4))
-
1
Σ
(2) (r)) ) AAt
(r+2))
+ H.A,
n
(r+
(3) |
+
-A,+10
n
2n
i=1
ar+1
(VVA((a!")) (")
h2
(n)
x
-
M (r+ x0*1
2 0
B,
(r)
n
2n
(0)
Ar+1
Si(2;; [1(x+t))) +
(++
1 (1x ), (r
A 12 (r+2))
P.A.
(r+
+
-
n
2n
0,+1
( (3) - h (0) vi
(++b)}
)
>
11
(r+b)
(r+ 1) 11))
Br
| 8/
(
+
+
n
2
2n
i=1
Br+1
(x+
x11 1|
+ 2n
0
where we use the fact that a ( (VV in (a). By using the above inequalities.
(1+t)) + h
0) + =11l0 e)
x. ( + + || 1/2 is strongly convex
;
Bp+1
n
(r+
2 (14)
Bp+1
(r(+))
12 + 2n.
Br+1
n
| (1+ 5( |
x²
x²"
2n
2
(14)
Br+1
(r+1)
|
Br+1
(r+1) - 5
B,+1 +
(r+
p(r+1)| 2
xx¹
1/
2n
2n
2n
i=1
i=1
(5)
B
Br+1
(++1) g(++1) 1?
2
(r+1)
x²
p2 -1
Σ
2n
2n
1=1
2=1
we get
A, + (r++)(x"')+
+
Br
0 x= ||
(r)
|
2n
1=1
Ar+1
f(
(1+ ) +
Ar+1
h 2z;
(r+)))
+
B,+1
2
(1+1)
- x 2
n
n
2n
1=1
1=1
1
(i((o(")) ) + +h! (1)) AA (r) Ar+1æ, (x+b))
+ ar+10; (r+2))
MA, Σ
(r+
(r)
x
n 1=1
2n
T.
pa,+1
(r+2)
(r+ (r+
Br
Σ
(r+ 1 2
+
vi
+
v
2n
2n
1=1
1=1
+
Br+1
-1)
Σ
n
b. (++1) - p
2
2n
0²
From the definition of Fi,r, we have
(x, Vf()) + +h( (r) + +xxx )²
30

---

Exploiting Similarity for Computation and Communication- Decentralized Optimization
Using the above equality, we get
V Fi, (2c (1)) + x (1, ax ) A, - Art1 (1+ + a.+10 ) (r+t))
T
(a. (++))) + x (v!") - =2 x((+t)) ,,, (x())= - =x("") + Ar+1 (3!") x ((++))) + ar+1 (1(t))) -
(v(tt)))o!"))
-b(-)) )
11
1
(a) (++))), Ar (011))
a!(T) + Ar+1 (g1") - si (((+)))) + ar+1 o (1(t))) - -m!")) -0( )(()))
12
A
Vi zj Ar (x!!) x!()) + +a++1
(r)
(1+
[ (((+t))) 0z.1) ) dA
(r+ (r) |
23z
yi
n
(11)
1
V (0)
(1+t)
(x(r) A,
Ar
(r)
+ Ar+1
(b!")) -2i _ (1++t) + ar+1 ( (1+ - m
Am1
2
x0)) x. (r) ?
B,
n
(r+
AA
n 2
|0(
(1+
b) - y 1111
2i
+
n
3n
8n
1=1
We have
Ar ( (VFi,r(a) (2. (1())))) ((() -1) )
(11) 44
2
(xt)))))
AA,
xx x
16
V (Vri (1t2)) 21 y
(r) - -xi
-x (+
(1I)
2- 4Ar+1
(0tt)))
AAr+1
(r- 1)
(r)
Ar+1
y
X
16
ar+1 (V (r+
(++ (1
))) ), 00 -0(")) (1)) 3Ar+1
Vk
(z)
(r+
})
1|2
2
B,
(++1)
of 2
12
2 in the last inequality. By using the above inequalities, we get where we use x = Ap- 1 B
T 2 11Ar+1
V (0
(r+2)
X
3
(r)
2
5B,
(r+
0/00|/++
AAr+1
(r+
(r) (
x
+
x
y,
16n
12n
16n
Then, using
E
V Verr(ar
)
2 1|²
5
x²
Ex=1
(r- b)
y! (r) 1 we obtain
n
352n
T 2
AAp+1
12
x
()
33AA,
Σ
n
x00)- - xz("") 1301
5B,
n
0
(r+
2 0
32n
16n
12n
We have
B, n
A, Az) + (r+t)(a"))
Σ
(0 (r) xz.
+
2n
Art1 n
f1(1
(1+
)
Ar+1
n
h
(r)
x
(r+b)
B,+1
Σ
n
(r+1)
x= 2
n
n
2n
i=1
1=1
+ 32n
AA,11
(r+ }
y!
(2)
33
(l(r)
x
(r)
2
+
AA,
x
(r+ +)
x (r)
16n
2n
i=1
+ +1
(r+)))
(r+
(r+b) 2
B,
(r (+))
v
2n
12n
i=1
+ 2n
B
1
-1
n
0
(r+1)
((r-1)
31

---

Exploiting Similarity for Computation and Caammunication-Efiiieeee Decentralized Optimization
Using the following inequality,
1,+1
fi(2; (t))
"1
2 Ar+1 (a +
Ar+1
( (rt2)
-0 - xlrtt))
uAr+1
(rt
-x x(+t))
+
n
2n
we get
)))((()) + #a+11((a")
+
B,
(//1) x0
2n
i=1
2 Art1(
Ar+1
((((((((1))) + n1!") ;i
a - (++1)
(rtt)
T
+ UAr+1
(r+3)
(++11)
By41
(n+1) xx- ||²
+
2n
2n
1=1
AA,+1
(r+4)
+)
ys 1/>1
33AA,
n
(t))
(r) (r)
n,A,
(r+
(r)
+ 32n
x
+
x
16n
2n
i=1
+1
(r+ }
(++
B,
(+
+ 2n
12n
Br+1
1
(r+1)
+
2n
1
0
Using the following inequality, we obtain
Art1 n
T
(1(((++11)) + hi - ()(x(++1)), a0 (++b)
- g((r)
n
(11)
Ar+1
+ (n (x(1))
64r+1
Σ
(x+
g/0) 2
x
28n
2n
1=1
(12).33
2
-8Ar+1
(((+1)_ - g(1)
A
(z) + h10)
vf(g (r)
2
8Ar+1
Σ 2
(r+ +)
- g(
8n
2n
(13)
28A
(r+
A g(r)
8A,41
Σ !9! -000 12
x y;
n
n
28A,+1
n
(r+
(r) 2
A (())
n 5A,
(o("") 0(1)'
8a
n
y
n
8
n
n
32

---

Exploiting Similarity for Computation and Communication--fiiee Decentralized Optimization
where we use Jensen's inequality in the last inequality. Using the above inequality, we get
A.f(a!!)) + #a+1f(("))
Br
n
(r)
x²'
2
Ar+1
g(r)
2n
2 A (x
+ Br+1
(r+1)
1
x²
2n
1=1
80
n
(0(") - 0(() |
MA
Ir+ +) ((++))
n1
2n
im1
Ar+1
A
20
n
(n+
y
(r)
2
33AA,,
+
SA
x
x
|
U.A,
a
(rt
3)
x (r))
n
32
16n
n
2n
+1
(rt
(++2))
2
Br
(r+
(r) |
vi
+
1/3
vi
2n
12n
i=1
Br+1
(r+1)
(-++1)
2
-1-1
Vi
2n
p2
i=1
2 f
+
Bi+1
Σ
(r+1)
0011
2n
80,41
MAr+1
(r+1)
-x
1/
n1
2p
A,41
A
20
(r+ +
y,
(r)
2
133AA,
+
5A,
x
(r)
x001
MA,
(r+ 1
x (r)
32
16n
2m i=1
1=1
i=1
+1
(r+
(1+3))1
Br
(r+
x
+
2n
12n
iml
Br+1
1
n
(r+1)
0(++1)
2
2n
By summarizing the above inequality, we obtain
A.)(((()) + ar+1f(x*)
B,
n
x=
||
+
Ar41 glr g())
2n
8
(
+ By41
(((+t))) x ||
2n
Art1
28
+)
yi
(r) 2
+
B
1
(r
+)
1.
1-
Br+1
1
- 1
Σ
(r-1)
g60+1) 2
32
12n
2n
p²
1=1
==1
3
5A,
(r))
80,41 11
(r)
())
2
MAr+1
n
(r+1)
(++1)
2
x
x
16n
n2
2p2n
im1
1ml
p1,+1
()
(r
x
2n
This concludes the statement.
33

---

Exploiting Similarity for Computation and Communication-Eliiee Decentralized Optimization
Lemma 22. Suppose that Assumptions 2 and 5 hold. Then, when M holds that
4p² 2 g(++1)
-8p²82
9r+2 Ar+2
g(++1)
- (1(+1]
- 82
y.
(1)
-3212 Art1=((+1) 32L2
42 22
(34)
Ar+2
A,+2
where =[-²= = 1 Ei= b - x
= = E
|000
5(7) and g(r) = 1 Ei=1
h - Vhi(o(>))|
Proof. From Lemma 8, we have
g(r+1) S 4p2g(r) + 4p202 (1b-t1)-g1) (1-11)-(11 + +32122
(35)
Using ((++1) Ar 10(111) 40.120(-11)
have
Ar42
g(++1) < 4p² + 8p282 / ar+2
(((+1) (0-1)--((11)) ((r-1)
Ap42
+ 88p28² (z(+1)) 7())
3212
A Ar+1 [(--1)
+ +2222 ar+2
( E(r+1)
An+2
Ar+2
S 4p2066) + =8p282 4r+2
(((++1)
(++1)
A,+2
+ +8p288 ((411) (r)
+ 32L2
Art1 ((r-1) + 32L2
(rt22(++11) =(++1)
Ar42
Ar42
S 4p2 8p282
ar+2
| (((+1)
Ar42
+ 8p²0"= 82
1
(r+
[r]
+ +32L Ar Ar-1=(+11) + +2L2
ar+2 =(++1)
n2
A,_
Ap42
This concludes the statement.
Lemma 23. Suppose that Assumptions I and 4 hold. Then, when M = 1, it holds that
- 1|
(36)
Ar App1
| (00) - 10
4Ar41 ar+1
Σ 2
(r+
y, 1/
2A
Σ
(r+b)
0.-2 0//
1
0
1=1
Proof. For all 71 > 0, it holds that
(((+1)) x(r+1)|
(12)
S (1+ (1+7)) |060) - =1/+t11 + [+ i
1 | -
(12)
< (1+ (1+ (1)0)) - -/oi| + (1 m1+ (1+1) _ |
8 + 11 (1+ | - 0|rsap
-5()
A A ) - + +1++))
) - gin>|? + (1+ ( 060)
-
$(1+)) + 72)
34

---

Exploiting Similarity for Computation and Communication-Pfiicee Decentralized Optimization
Substituting 711 72 min(1, v
Art1
1}. we obtain
1,41
+ (1+ -
Ar
1
Ar+1 (Att1 vA,))
I max {2, 2A
2A,+1
|+ 7
max
2,
Ar+1 - Ar
ar+1
ax+1
(1 m)
1
_
S
max
4A
4Ap+1
722
0y+1
Op-1
where we use Ar+1 2 Ar and A,41 2 ar+1. Using the above inequalities, we obtain the statement.
Lemma 24. Suppose that Assumption holds. Then, when M = 1, it holds that
A-+13(++1) pA, A 1
(++
p (r))
+
(37)
p
1 p
where =(? = 1 Σ [ - z and = 1 Σ 11.00 5(7)
Proof. It holds that for all y >>>0 0,
x
((++1)
(1+t)
x(++1) /
11
(14)
(r+
-g/zl|? pp² p² ( =
22
(1+ p)p²
Σ
(r+
y!
(+) 2
+ | 1 0² Σ
yi - 8
0² | _ - yi
1=1
(1 7)+
a
(r+
+ 1+ 1 A
Σ ar
m + +1+
p²ar+1 1
Σ
n1
vn(r) σ(1) /
n
nA4+1
nA,+1
1=1
2² (x+1))
-
g/nl|2
where we use Jensen's inequality in the last inequality. Substituting Y
I we obtain the statement.
F33 Convex Case
Lemma 25. Suppose that Assumptions 1, 2, and 4 hold with μ and the following inequality is satisfied:
V (z (++
2
(r+
<
352
Then, when X = 2085, M = 1, and
8
p min
1600'' 6L 48(R +
1)3
35

---

Exploiting Similarity for Computation and Communication-Pfiiient Decenttaallieeee Optimization
it holds that
n2
Arf(z!()) - =x+11(("') +
(r)
x²
2n
1=1
+ 2A g(r) + -9900A,,
11 (())
+
Rp
x -00)=((1)
24(R + 1)2
2 A +
1
(r+1) x²
2n 1=1
+ 2A g(r+t) + 999990644 A, 1 1r+1) + 52,425 (1+1) +
Rp
(( (011))$000 -
24(R + 1)2
where =(") = 1 Ei=1
(t) 2 = = = Σ of - -B(7)] and g(r) = 12
= - 10/0 )h:(o(>))
Proof. Using S 1.2 we can simplify Lemmas 22 and 24 as follows:
p 2 g(r+1) 8p282 4
g(r+1)
(1(+1)
Ar+2
- 8pp222_ 8-_ _
(r+ 2)
- yj
(r)
-22L2
A
((+1)
-32L,
0r+2 =(++1)
(38)
Ar+2
Ar+2
1=1
(4 2 A A
(1+1)
p
Art1
1
Σ
(r+3)
yi
(1)
2
4
1
=(r)
(39)
11
3
Using Lemma 19, we can simplify Lemma 23 as follows:
R R+1
[0()) -
- ( 00022)12
4A 1
(r+
-y
(n)
2A,+1 1
(r+
2.
(r)
(40)
a
a++1
From Eq. (33) + 2Ax12 Eq. (38) + 22((+11 x Eq. (40) + 5606
Eq. (39) and X 2088, we obtain
p
1 n
||² + Ar
2A,+2
A g(r)
A.)(1(1)) + ar+1((x"))
+
x01
p
2n
8
Rp
(r()) (()) 2
+ -9008,,E(1) + ((r) +
24(R
+12
2 A (zx1((1(+
(1+1)
xx" |
2A g(r+1)
+ 2n 1=1
1
+
5600
321,2
A Ar41=((+3) (1+11)
+
1
-1)
321,2
2240ar+1 5p dr+2=(r+1)
P
20
0²
8
30,
- 166.
xx(+2)]
/
+
24 1)
+
=
9
8
16Ar+2
128
0
2240
8p
A
n
x
(r+
y
(r)
2
Ar41
6a, (1
3
n
A
1
(x+
(r)
+
(R + 1) ()
12a,
m
36

---

Exploiting Similarity for Computation and Communication-Pliieel Decentralized Optimization
where we use that fact that B,
for all when μ 0. From Lemmas 18, 19, 19, and 20, we have
Ar+1 (30) S 1 R
Ar+2 (30)
ar+1
(32)
1
(32)
1
(32)
(30).(28)
R+1
A,+1 4,
1,
2086,
2086,
ax+2
dr+1
4x
dr+2
Q1
0r+1
406
Using the above inequalities, we obtain
Arf(z!!) + ax+1f(x"))))+
+
1 n
0 a'1
+ +(++8p)
Ar- g(r)
2n i=1
Rp
|0(0) 1661-=$1 x00) ?
+ 9906
+ (()) +
24(R + 1)3
(r+1) x=1 |
2Ar+2 g(r+1)
2 Art1 A
2n
8
5600
32L
A
((+11)
1048
-1 1
32L2
7505p am425((+3)
P
8
8
2(R + 1)
0²)
|
(r(11) |
24 + 1)
5
35
2240
A
(r+2)
(r)
+
8- 16p8
8p
6p
x
y;
2
(R
+
1)
3
1
1
1
Σ
(r-
b)
+
12
p
-
2
12
71
i=1
Then, using the assumption on p. we have
1 8p S 2,
5606
32L
2 9008,
8
32L
1048
-1
7500p 2 8,
8
2(R + 1)
Rp
0²
24(R + 1)
5
24(R + 1)2
9
35
2240
- - 165p
8p
0p 2 0.
2
R +
3
Thus, we can simplify the above inequality as follows:
A,f(((r)) a,+11((=*) +
1
Σ (000) x+
2n
+ 2A g(r) + -9905,,3 + 14.4 +
Rp
24(R + 1)2
> Ar+1f (x((11))
1 (+)
+
x²
2n
1=1
2Ap=2 + 9908 A (
+ 8a,42 1((+1)
[(++1) +
Rp
g(++1) - -
24(R + 1)²
Thus, we obtain the desired result.
Lemma 26. Suppose that Assumptions 1, 2, and 4 hold with y O, and the the following inequality is satisfied:
v Ve,r (0 (r((t)) 1|²
x²
(r+b)
b)
y (r)
352
37

---

Exploiting Similarity for Computation and Communication-Pficceel Decentralized Optimization
Then, when À 2086, M 1, and
8
S min
1600
6L
48(R
+ 1)3
it holds that f(x!10) f(x*) S after
4168 [1 xx
R
rounds.
Proof. From Lemma 25, have
Ar+1 (f(x(r-1) - f(x'))
2 A, (f(*(1)) - -1xx0)
+
1
n
0. x²
1
n
0
(r+1)
x²1
2n
2n 1=1
i=1
2Ar+1 g(r)
2A ((+22g())) 9908 (A,=(r) A 1 -++11(+11
(a++
-.422
8
R(1 p)
(1000) (1g6))_am -5(1)
2
(((+1)
24 + 1)
Telescoping the sum from 0 to R and using =0) = (()) and (0) (0)
=x. have
(() - f(xx)) 1
( x=
2.AR
Using Lemma 17, we obtain the desired result.
Lemma 27. Suppose that Assumptions 1, 2, and 4 hold with μ 0, and the following inequality is satisfied:
V VF. (a )
1|?
2
(r++)
(r)
S
352
Then, when x = 2085, f(x*) S after
1-p1-p² and M 2
2 (mg(max| 12L
203846|| (1) -= 2 }}, it holds that f(x(R)
1+ ++pp
8 (
x 112
R=
rounds.
Proof. Define (m) as follows:
((11) =
i((0)
(m++1) (1 (1+)) (m)) W - (mm-1))
Then, the output of Alg. 5 is equivalent to
W aj.
]=1
38

---

Exploiting Similarity for Computation and Communication-Pfiiienn Decentralized Optimization From Proposition in Yuan et al. (2022), it holds that for any d1 (22 ,......,.00. On R
a V/ (1 -1-
(M)
aj
Σ
a all
where à 2in ag Thus, When
1
6v2L
1600
22
M 2
log
max
VI
8
we can satisfy the condition on in Lemma 26. We used R 2 1 to simplify the condition on p. From Lemma 26, we obtain the desired result.
F.4. Strongly Convex Case
Lemma 28, Suppose that Assumptions I and 4 hold and the following inequality is satisfied:
V F (a: (rb))
X² n
Σ
(r+
y5 2
2
352
Then, when x = 966, M- 1 and
μu
4882 μ
p S min V 172812
260L2(1926 + n))
[+2 [+
11
[1+ 3848
/ (1++
966
(1 11
1928
)
(1+ 1+11+
1+
3848
965
4
1
1
it holds that
B, n
2A g() +2006,,E77 + 1
A)f(((1) + ar+1f(x*)
+
0,
(r)
x='
(41)
2n
2 (+ +
Br+1
x 12
2A g(r+1) 200 + 50.425((+1)
2n
==1
where =(1) = + (2(") - x
2
=(-)
+ 1040 56/)| and ((r) = E -Vvh-()()())))
A (-11 4a. (0.120(-11)
Proof. From Lemma 8, p.p < and (rr-1)
have
Ant2
p0 2 g(r+1)
-2p52
4x+2
(((+1) - -0000x((+))))) x((+1)
Art2
2282
x
(r+ 1))
y
(r)
3212
A
(r+1)
-212 201220+22((+)
(42)
n
A
Art2
39

---

Exploiting Similarity for Computation and Communication-Pfiicent Decentralized Optimization
From Eq. (33) + 2 Eq. (42) and À 968, we have
)) + #x++1f(2")
+
B.
(r)
x² 1|
Ar+1 (1
1
2Ar+2P
g(r) + 2005A, + 60,+12
2n
8
Ar+1
1=1
2 A1+1f(2((+11)
Br+1
(r+1)
| +
2A g(r+1)
x²
2n
8Ar+1
1
64L
((++1)
+ da,+2
By+1
(
-11
64L
=(++1)
B,
v.
(r+
28p²
82
28ay+2
0²
82
12n
5
Ar+1 4pAr+2
Σ
n
(++
1
par+1
4pdar+2
Σ
n
(r+
1)
(m+
(r+
n
n2
2
Using Lemmas 19, and 20, 5 S L, and the condition of we have
2A,+2 p=1+ 1
(1 1+
ar-
p=
p PS. 2,
A,+1
Art1
/
641.2
200,
26p²
B,41
1
-1
64I.2
48a,+2 (1
(2 -1)
641?
1,
28ar+2
02
Ar+2
Ar+1
4pAr+2 0,
par+1
4p8a,+2 2 O.
Using the above inequalities, we obtain the desired result.
Lemma 29. Suppose that Assumptions 1, 2, and 4 hold and the following inequality is satisfied:
(o (n+
1|?
(r+b)
b)
12
<
2
352
Then, when A = 966, M- = 1, and
nd 1728L2*
4882p μ
p min
260L? + p)
3846
))
965 ((++
(1 (1+ 1
1020)
)
( 1 1+11= 1+
3848
[++2 (1
1 V
968
46
p
it holds that (z)( f(x*) after
R R=O1 0
(v
8
8+1 log
(
min [11, 8) [[ )
1
1
rounds.
Proof. We have
Ar (f( - -((x))
+
B,
Σ
x²
2
+
2A
g(r) + 2008A,E{ + da,41E(")
2n
8
1=1
> Ar41 ( -s(x*))
B,41 2n
a
(r+1)
x ||
24 2 g(++1) 1) + 2005 (,1064 + 80,42
+
0
+
40

---

Exploiting Similarity for Computation and Communication--Piiccalll Decentralized Optimization
Telescoping the sum from to = 1 and using =
==
=E(0)-
0, we have
Ar (1 - -s(x0)
Bo
1 (0)
-
x²
x
2n
2
From Lemma 17, we obtain
x²1" if 1s S 3846,
f(x(R)) - -(x²)) S
(I+v
3548
4R-2
966
(0)
x²
p > 3845
for any R 2 1. Then, we obtain the desired result.
Lemma 30. Suppose that Assumptions 1, 2, and 4 hold and the following inequality is satisfied:
VF Var (1t))())))))) /|(
X
11
(r+
y! 1|
352
Then, when x = 968, 7 1- 1-v1-p²
and M 2 -i-p log(
8L (1328+ holds that f(x!!t)) -s(x)) S c after
1+
(10tt log
8 10tH 1
min u, 8) [z x0122
R=
1+
H
rounds.
Proof. Define (mm) as follows:
(-11)
(0 I
W (m++) (1 + (1+)) Wm)) W (mm-1)
Then, the output of Alg. 5 is equivalent to
n
Σ
w (M)
aj.
From Proposition 1 in Yuan et al. (2022), it holds that for any ai a2 .... an Rd
n
n
2 22(1 (1-v1-p) 2M n
W
6j
a
aa a
1=1
where à = 1 n a;
When M2 -i-p log( /22
we have v2(1 vT M S c. Thus, when
4
1892 + 1))
M 2 log
V1
we can satisfy the condition of p in Lemma 29 where we use L and L μs. Thus, from Lemma 29, we obtain the desired result.

---

Exploiting Similarity for Computation and Communication-Pficiall Decenttraiiiieeeeiiiiiaiiiiii Decentralized Optimization
G. Analysis of Computational Complexity
G.1. Useful Lemmas
Lemma 31. Let F R + I. be a p-strongly convex function and x" be a minimizer of F. If the following satisfied for some a S yt and x, y E Rd
VF(2)] S a y x=11.
holds that
|F(x))] - #
op
|| y
Proof. We have
yl
y x=1|
x²'
x=1|
||
where we use the strongly-convexity of F in the last inequality. Using [VF(2)] S a ly æ'Il. we obtain the desired result.
Lemma 32. Let F Rd + R. be a p-strongly convex and L-smooth function and x² be a minimizer of F. If we use Nesterov's Accelerated Gradient Descent with initial parameter (0) E TRd, holds that for any
(F(a s (0) -xx 1m
after
== T. log (V-
[Tu+ (I L) 332 )))) 12
(Vi'
iterations where a. (T) is the output of Nesterov's Accelerated Gradient Descent.
Proof. From Theorem 3.18 in Bubeck (2015), it holds that
((x(T))-FF < 11 + I 2
(0)
x²
exp -T
11 11) -TVV"
Using the I-smoothness, we have
(F | < L(H + L.) [o
x²1
exp -T 11
T.
Thus, when T > V log( () it holds that
(F s a 20 x11
Thus, using Lemma 31, we obtain the desired result.
Lemma 33. Let F: Rd - R be a p-strongly convex and L-smooth function and x² be a minimizer of F. If we use the algorithm proposed in Remark in Nesterov et al. (2018) with initial parameter (0) E Rdd it holds that for any B >
< x x
after
(1
L(u [(u+ 3)
T=
iterations where x. (T) is the output.
42

---

Exploiting Similarity for Computation and Communication--/iiccaall Decentralized Optimization
Proof. From Remark in Nesterov et al. (2018), it holds that
[VF(2 D) 0O ((1) [1(xx(7) -
x="
T
Thus, when T 2 V a it holds that
s (a(al())))) x01)
Thus, using Lemma 31, we obtain the desired result.
G.2. Proof of Theorem 2
Lemma 34. Consider Alg. 1. Suppose that Assumptions 1, and 4 hold, and h² = V (0))) x = x and we use the same À and M as Lemma 12. Then, if we use Nesterov's 's Accelerated Gradient Descent with initial parameter a; to approximately solve the subproblem in line 4, each node requires at most
(
( 220
0
log 1r 1
8(6 + 11)
iterations to satisfy Eq. (8).
Proof. F,,, is Q( + stroongy convex and OL + 8)-smooth. Thus, using Lemma 32, p S L, and s L, we obtain the desired result.
G.3. Proof of Theorem 4
Lemma 35. Consider Alg. 3. Suppose that Assumptions 1, 2, and hold, and h and we use the same À and M as in Lemma 16. Then, if we use the algorithm proposed in Remark Nesterov et al. (2018) with initial parameter v( to approximately solve the subproblem in line 4, each node requires at most
Vf(: Vf(( af = (00)
L 1
iterations to satisfy Eq. (9).
Proof. Fi, is O( stronnyy convex and O( + 80-smoohh. Thus, using Lemma 33, p S L,, and S L,, we obtain the desired result.
G.4. Proof of Remark 2
Lemma 36. Consider Alg. 3. Suppose that Assumptions 1, 2, and hold, and (1 = VVw - V (0) 0 o()) and we use the same X and M as Lemma 16. Then, we use Nesterov's 's Accelerated Gradient Descent with initial parameter ( to approximately solve the subproblem in line 4, each node requires at most
о (V T. Vutto log (1))
iterations to satisfy Eq. (9).
Proof. Fs,, is O(u + stronnyy convex and O(L + -mosthh. Thus, using Lemma 32, p S L, and S L, we obtain the desired result.
43

---

Exploiting Similarity for Computation and Communication-Pficiinn Decentralized Optimization
G.S. Proof of Theorem 6
Lemma 37. Consider Alg. 4. Suppose that Assumptions 1, 2, and hold, and h 00 ) V -0 and we use the same "is M, and X Theorem S. Then, we the algorithm proposed in Remark I in Nesterov al. (2018) with initial parameter y; ) to approximately solve the subproblem in line 12, each node requires at most
T V
iterations to satisfy Eq. (10).
Proof. F,r is Oi + -tstoonyyy convex and O + 6)-smooth. Thus, using Lemma 33, p S I,, and S I,, we obtain the desired result.
G.6. Proof of Remark
Lemma 38. Consider Alg. 4. Suppose that Assumptions 1, 2, and hold, and h h0) = Vf(, (f.o of 5(0) and we use the same 7, M, and as Theorem 5. Then, if we use Nesterov's Accelerated Gradient Descent with initial parameter ) to approximately solve the subproblem in line 12, each node requires at most
(
o
L log
1
iterations to satisfy Eq. (10).
Proof. Für is Q( + -tstnogyy convex and OL + 8-))smoooh. Thus, using Lemma 32, p S L, and 5 S L, we obtain the desired result.
44

---

Exploiting Similarity for Computation and Communication-Plicccee Decentralized Optimization
H. Experimental Setup
H.1. Setup for Adaptive Number Local Steps
In Fig. (()), we ram gradient descent until the following condition was satisfied.
Inexact-PDO:
(+ ( y12 (a;
M(++u) (r+ (++1)(++2)
|| ||
x, 112
SPDO: |V (a
(1(rt)) S Al1ce (++1)
Inexact Accelerated SONATA: (ar (1+1)) || S
where is the number of inner (1) (r+1) x
loop.
Accelerated-SPDO: [V (a (r+ f)) S 2110 (r+ y: 1.
Tian et al. (2022) showed that Accelerated SONATA can achieve low communication complexity shown in Table if (ar (=) Fir (art,))) is sufficiently small, where a is the minimizer of Pi.r- However, unlike the condition for proposed methods, e.g., Eq. (9), this condition cannot be computed in practice. Therefore, slightly modified this condition in our experiments to make it actually computable.
H.2. Hyperparameter Setting
In Fig. 1, we tuned the hyperparameters by grid search. Specifically, ran grid search the hyperparameters listed in Table 3 and chose the hyperparameter that minimizes the norm of the last gradient.
Table Experimental setups. Note that for Inexact Accelcrated SONATA, 8 is the coefficient of the additional 1.2 regularization in the subproblem, and different from Definition 1.
(0.05, 0.01, 0.005, 0.001
Gradient Tracking
{10, 20, 20,30)
(0.05, 0.01, 0.005, 0.001)
Inexact-PDO
{1, 10) { {10, 20)
the value the cnefficient 1.2 regularization.
(0.05, 0.01, 0.005, 0.001)
(Aceelerate))-SPOO
11, { 110, 20, 303
M
(0.05, 0.01, 0.0001
11,
Inxacc Accelerated SONATA
{10, 20, 20,
The number of inner loop T
{1, 2,4,
The coefficient of the regularizer
f0.1, 1, 10)
45

---

Exploiting Similarity for Computation and Communication-Eliieee Decettteeieeeeeeeeiiillaii Decentralized Optimization
I. Additional Experimental Results
I.I. Relationship between a and
In our experiments, we used the Dirichlet distribution with hyperparameter a to control In this section, we numerically verified that increasing a can decrease 8. We randomly sampled 100 points from NoO, /22 of 6. Table 4 indicates that 5 decreases as a increases. Thus, examining the performance of methods with various a is a proper way to evaluate the effect of 6.
1 I) and reported the approximation
Table Relationship between a and
0.01
0.1
1.0
10.0
Approximation of 6 1.6 10
x 10
2.1
10-3
5.0 x 10-4
1.2. Sensitivity to Hyperparameters
In this section, we evaluated the sensitivity of SPDO hyperparameters. Fig. 3, we fixed one hyperparameter, such as M, and tuned the other hyperparameters in Fig. ((a).
Figure 3(a) indicates that setting M to 3 is optimal. Comparing the results with M 1, increasing the number of gossip averaging decreased the gradient norm. This implies that performing gossip averaging multiple times is important. Furthermore, increasing the number of gossip averaging too much increases the gradient norm since the total number of communications fixed. These observations are consistent with Theorem 3.
In Fig. 3(b), we evaluated how the choice of affects the convergence behavior SPDO. The results indicate that setting is optimal. use very large A, SPDO requires more communication since the parameters are almost the same even after solving the subproblem. We consistent observations in Fig. 3(b).
L2 Regularization: 0
L2 Regularization: 0
10a
M 1
0.1 ==1
M 3
10-1
10
[
M 5
1
10-2
M 10
10-2
= 50
M 20
10
M 30
10
10
0
500
1000
1500
2000
500
1000
1500
2000
Communication Cost
Communication Cost
(a)
(b)
Figure 3. Convergence of the gradient norm of SPDO with various M and X. The experimental setting Fig. 1(a).
46

---

Exploiting Similarity for Computation and Communication-Efiieenn Decentralized Optimization
1.3. Experiments with Different Seed Value
Figure shows the results when using a different seed value for the experiments shown in Fig. 1.
Regularization:
L2 Regularizatio:: 0
Regularization: 0.01
L2 Regularization: 0.01
10a
10:1
10.9
10.1
10
101t3
10-2
10-7
10-4
10-
10-4
10-1
10-1
10a1
10.3
10-3
10.4
10:4
500
1000
1500
2000
1500
2000
4500
e000
7500
500
1000
1500
2000
1500
2000
4509
60.00
7500
Communication Cost
Computational Cost
Communication Cost
Computational Cost
(a) Adaptive numher of local steps
Regularization:
L2 Regularization:
L2 Regularization: 0.01
Regularization: 0.01
107
10a
10-3
10-1
10-4
10a
10r2
10a4
30-4
10-1
30
10-4
10-3
10-1
10-1
10-1
10
10
2000
200
460
500
1500
2000
Communication Cost
Computational Cost
Communication Cost
Computational Cost
Gradient Tracking
Inexact-PDO
SPDO (ours)
Accelerated inexact-PDO
Accelerated-SPDO (ours)
(b) Fixed number of local steps
Figure Convergence of the gradient norm with 0.1 when different seed value used for the experiments shown in Fig. 1. In (a), we ran gradient descent until the condition for an approximate subproblem solution was satisfied for all methods except for Gradient gradient descent for 10 times. In (b), gradient descent for 10 times approximately
Tracking. For Gradient Tracking, solve the subproblem. See Sec. for a more detailed setting.
47


Reviews:
[{"review_id": "cIxHIEcn0H", "reviewer": "Reviewer_aFm6", "summary": "This paper provides a decentralized optimization method for convex optimization under the second-order similarity. The main contribution is improving the term $\\delta_{\\max}$ or $L$ to $\\delta$ in the complexity to $\\delta$.\n\n## update after rebuttal\nThe authors have addressed my questions, and I decided to keep my overall rating.", "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 the positive feedback and careful review.\n\n> The main idea seems be to directly combine the inexact gradient sliding (Kovalev et al., 2022) with Multiple Gossip and gradient tracking. Can you highlight the main technical novelty in the algorithm and analysis?\n\nWe would like to emphasize that **a straightforward combination of gradient sliding, multiple gossip averaging, and gradient tracking does not work**. To overcome this, we proposed a carefully designed modification in Algorithm 3 (see the update rule highlighted in blue).\n\nSpecifically, straightforwardly combining them yields the update rules shown in lines 263-274. However, as we described in lines 275-289, this simple combination does not work. \nOur paper is the first to analyze this challenge and develop a principled modification that ensures low communication and computational complexities.\n\n> The domains of $x$ and $v$ in lines 4-5 of Algorithm 3 and lines 12-13 in Algorithm 4 should be presented.\n\nThe domains of $x$ and $v$ are $\\mathbb{R}^d$. We will clarify them in the camera-ready version.\n\n\n> The experimental results only includes the comparison on the communication cost. I think the comparison on the computational cost is also required.\n\nThe comparison of the computational costs is shown in the second and fourth figures in Figure 1.\nThe first and third figures from the left show the communication complexities.\nWe will clarify it in the revised manuscript.\n\n> Can we avoid the term $1/\\sqrt{1-\\rho}$ in the computational cost?\n\nWe deeply appreciate the reviewer for checking it carefully.\nThere are typos in Table 1; the computational costs for methods other than Gradient Tracking do not depend on $\\rho$ since $\\tfrac{1}{\\sqrt{1 - \\rho}}$ in communication complexity comes from the multiple gossip averaging, which does not affect the total computational complexity.\nThe statements of our theorems in the paper are correct, and this correction does not affect the discussion in the entire paper. \nWe apologize for your confusion.\nWe promise to replace Table 1 with the following version in the revised manuscript.\n\n| Method                        | # Computation |\n|--------------------------------|---------------------------------------------|\n| Gradient Tracking             | $\\tilde{\\mathcal{O}} (\\frac{L}{\\mu (1 - \\rho)^2} \\log (\\frac{1}{\\epsilon}))$ |\n| Exact-PDO (SONATA)            | n.a. |\n| Inexact-PDO                   | $\\tilde{\\mathcal{O}} (\\frac{\\sqrt{\\delta L}}{\\mu} \\log (\\frac{1}{\\epsilon}) \\log \\log (\\frac{1}{\\epsilon}))$ |\n| Stabilized-PDO                | $\\tilde{\\mathcal{O}} (\\frac{\\sqrt{\\delta L}}{\\mu} \\log (\\frac{1}{\\epsilon}))$ |\n| Accelerated SONATA            | n.a. |\n| Inexact Accelerated SONATA    | $\\tilde{\\mathcal{O}} (\\frac{\\sqrt{\\delta L}}{\\mu} \\log (\\frac{1}{\\epsilon})^2)$ |\n| Accelerated Stabilized-PDO    | $\\tilde{\\mathcal{O}} (\\sqrt{\\frac{L}{\\mu}} \\log (\\frac{1}{\\epsilon}))$ |\n\n> Can we provide the lower bound the verify the optimality of proposed algorithms?\n\nThank you for the comments. We will add the following discussion in the camera-ready version.\n\n**Communication Complexity:**\n[1] showed that lower bound requires at least\n\\begin{align*}\n    \\Omega \\left( \\sqrt{\\frac{\\delta}{\\mu (1 - \\rho)}} \\log \\left( \\frac{\\mu \\| x^\\star \\|^2}{\\epsilon} \\right) \\right)\n\\end{align*}\ncommunication to achieve $f (x) - f (x^\\star) \\leq \\epsilon$.\nOur Accelerated SPDO can achieve the following communication complexity:\n\\begin{align*}\n    \\tilde{\\mathcal{O}} \\left( \\sqrt{\\frac{1 + \\frac{\\delta}{\\mu}}{1 - \\rho}} \\log \\left( 1 + \\sqrt{\\frac{\\min \\\\{ \\mu, \\delta\\\\} \\|x^{(0)} - x^\\star \\|^2}{\\epsilon}} \\right) \\right)\n\\end{align*}\nThus, when $\\delta \\geq \\mu$, Accelerated SPDO is optimal up to the logarithmic factor.\n\n**Computational Complexity:**\nFor non-distributed cases, any first-order algorithms requires at least  \n\\begin{align*}\n    \\Omega \\left( \\sqrt{\\frac{L}{\\mu}} \\log \\left(\\frac{\\mu \\| x^{(0)} - x^\\star \\|^2}{\\epsilon} \\right) \\right)\n\\end{align*}\ngradient-oracles to satisfy $f(x) - f^\\star \\leq \\epsilon$ (See Theorem 2.1.13 in [2]).\nAccelerated SPDO can achieve the following computational complexity:\n\\begin{align*}\n    \\tilde{\\mathcal{O}} \\left( \\sqrt{\\frac{L}{\\mu}} \\log \\left( 1 + \\sqrt{\\frac{\\min \\\\{ \\mu, \\delta\\\\} \\|x^{(0)} - x^\\star \\|^2}{\\epsilon}} \\right) \\right)\n\\end{align*}\nThus, the computational complexity of Accelerated SPDO is optimal up to logarithmic factors.\n\n## Reference\n\n[1] Tian, Y., Scutari, G., Cao, T., and Gasnikov, A. Acceleration in distributed optimization under similarity. In AISTATS, 2022.\n\n[2] Nesterov, Y. Lectures on convex optimization. In Springer, 2018.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I have briefly read the proofs and it sounds correct.", "experimental_designs_or_analyses": "The comparison on the computational cost should be involved.", "relation_to_broader_scientific_literature": "See questions.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "See questions.", "other_comments_or_suggestions": "See questions.", "questions_for_authors": "This paper is well-written and well-motivated. I have briefly sketched the proof, which sounds correct. There are some comments:\n1. The main idea seems be to directly combine the inexact gradient sliding (Kovalev et al., 2022) with Multiple Gossip and gradient tracking. Can you highlight the main technical novelty in the algorithm and analysis?\n2. The domains of $\\bf x$ and $\\bf v$ in lines 4-5 of Algorithm 3 and lines 12-13 in Algorithm 4 should be presented.\n3. The experimental results only includes the comparison on the communication cost. I think the comparison on the computational cost is also required.\n4. Although the main theorems improve the previous ones, the further discussion for the potentially better results is desired:\n\n      a) Can we avoid the term $1/\\sqrt{1-\\rho}$ in the computational cost? \n\n      b) Can we introduce the partial participate framework to reduce the complexity of local first-order oracle?\n\n      c) Can we provide the lower bound the verify the optimality of proposed algorithms?\n\n    The following references may be helpful to the discussion:\n\n[1] Haishan Ye, Luo Luo, Ziang Zhou, and Tong Zhang. Multi-consensus decentralized accelerated gradient descent. Journal of machine learning research 24(306):1-50, 2023. \n\n[2] Qihao Zhou, Haishan Ye, and Luo Luo. Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity. In Advances in Neural Information Processing Systems, 2024.\n\n[3] Aleksandr Beznosikov, Gesualdo Scutari, Alexander Rogozin, and Alexander Gasnikov. Distributed saddle-point problems under data similarity. In Advances in Neural Information Processing Systems, 2021.", "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": "VUoXOL907d", "reviewer": "Reviewer_6acg", "summary": "The paper studies decentralized optimization where multiple nodes, each holding a local function f_i, aim to minimize the average f(x) = \\tfrac{1}{n}\\sum_i f_i(x). Traditional decentralized methods are constrained by communication overhead and data heterogeneity. The authors propose a Proximal Decentralized Optimization (PDO) framework that leverages (1) a proximal-point formulation (improving upon naive gradient-based updates) and (2) a refined measure of local function similarity (replacing reliance on the worst-case delta_{\\max} with an average \\delta).\nTo handle large models realistically, they introduce two variants:\n1. Stabilized-PDO (SPDO)– A “stabilized” method that relaxes the requirement for exact subproblem solutions, ensuring that even inexact local solves yield competitive global convergence rates.\n2. Accelerated-SPDO – Extends the above approach with an acceleration scheme (inspired by Monteiro–Svaiter) and faster gossip averaging, targeting improved communication complexities in both convex and strongly convex settings.", "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 your constructive comments.\nWe have addressed the concerns about missing ablation studies and included the results in our rebuttal below. We agree that these additional experiments significantly strengthen our paper. We kindly ask the reviewer to reconsider the evaluation and, if possible, adjust the score to reflect these changes.\n\n> The authors do not measure or estimate $\\delta$ (the second-order similarity measure) directly on these data splits [...]\n\nThank you for your suggestion.\nWe randomly sampled $100$ points from $\\mathcal{N}(0, I / \\sqrt{2d})$ and reported the approximation of $\\delta$.\nThe following table indicates that $\\delta$ decreases as $\\alpha$ increases.\nThus, examining the performance of methods with various $\\alpha$ is a proper way to evaluate the effect of $\\delta$.\nWe promise to add this table in the camera-ready version.\n\n|  $\\alpha$ | $0.01$ | $0.1$ | $1.0$ | $10.0$  |\n|---|---|---|---|---|\n| Approximation of $\\delta$ | $1.6 \\times 10^{-2}$ | $9.2 \\times 10^{-3}$ | $2.1 \\times 10^{-3}$ | $5.0 \\times 10^{-4}$ |\n\n > The authors do not show error bars or repeated runs to reveal the variance.\n\nWe promise to run our experiments several times and report their variance in the camera-ready version.\n\n> Real distributed environments might have node-level heterogeneity in CPU/GPU power.\n\nWe agree with the importance of considering the settings where each node has different computational resources. However, developing algorithms in this simple setting is an important first step for studying algorithms in the more challenging setting, as the reviewer mentioned. We believe that our work provides helpful insights that could contribute to the development of future algorithms for more realistic settings.\n\n> It would strengthen the experimental section if the authors demonstrated at least one experiment systematically varying M—for instance, letting $M$ take on $\\{1, 5, 10, 20\\}$ [...]\n\nThank you for the suggestion.\nIn the following table, we fixed the number of multiple gossip averaging $M$ of SPDO and listed the gradient norm reached after $2000$ communication.\n\n| $M$  | $1$ | $2$ | $3$ | $5$ | $10$ | $20$ |\n|---|---|---|---|---|---|---|\n| $\\| \\nabla f (\\bar{x}) \\|^2$ (SPDO) | $9.13 \\times 10^{-5}$ | $8.32 \\times 10^{-5}$ | $2.24 \\times 10^{-5}$ | $1.01 \\times 10^{-5}$ | $8.55 \\times 10^{-5}$ | $5.13 \\times 10^{-4}$ |\n\nThe hyperparameters, except for $M$, were tuned as in Figure 1(a) with $0.01$ L2 regularization.\nThe table indicates that setting $M$ to $5$ is optimal.\nComparing the results with $M=1, 2, 3, 5$, increasing the number of gossip averaging decreased the gradient norm.\nThis implies that performing gossip averaging multiple times is important.\nFurthermore, increasing the number of gossip averaging too much increases the gradient norm since the total number of communication is fixed (See lines 422-425).\nThese observations are consistent with Theorem 3.\n\nWe promise to add this table to the revised manuscript.\n\n> It would be more persuasive to include plots (or at least a table) that show how the final performance depends on each hyperparameter. [...]\n\nAccording to the reviewer's suggestion, we examined the sensitivity of $\\lambda$.\nThe following table shows the gradient norm reached after running algorithms for $2000$ communication. \n|  $\\lambda$ | $0.1$ | $1$ | $10$ | $50$ |\n|----|---|---|---|---|\n| $\\| \\nabla f (\\bar{x})\\|^2$ (SPDO) | $1.13 \\times 10^{-1}$ | $8.55 \\times 10^{-5}$  | $1.69 \\times 10^{-2}$  | $2.44 \\times 10^{-1}$  |\n\nIf we use a very large $\\lambda$, the number of iterations of a local solver can decrease (see Lemma 31), while it requires more communication since the parameters are almost the same even after solving the subproblem, which ultimately requires a large number of communications.\nWe can see consistent observations in the above table.\n\nWe will numerically analyze the sensitivity of other hyperparameters and promise to report the results in the revised manuscript.\n\n> When $\\delta\\approx L$, do the improvements over classical decentralized methods persist or vanish? \n\nIn the worst case, such as $\\delta \\approx L$, Stabilized PDO and Gradient Tracking require the same communication complexities.\nHowever, in many practical scenarios, $\\delta$ is smaller than $L$ [2,3].\nFor instance, many existing papers, e.g., [1], considered that Dirichlet distribution with $\\alpha=0.1$ was heterogeneous. Even in this setting, Figure 1 indicates that our proposed methods can achieve lower communication complexities than Gradient Tracking.\nWe will clarify it in the revised manuscript.\n\n## Reference\n[1] Lin et. al., Quasi-global momentum: Accelerating decentralized deep learning on heterogeneous data. In ICML 2021\n\n[2] Chayti et. al., Optimization with Access to Auxiliary Information, In TMLR 2024\n\n[3] Kovalev et. al., Optimal gradient sliding and its application to optimal distributed optimization under similarity.\nIn NeurIPS 2022.", "claims_and_evidence": "1. The authors do not measure or estimate 𝛿 (the second-order similarity measure) directly on these data splits, so the link between “Dirichlet 𝛼” and actual functional similarity is inferred but not verified.\n\n2. The paper does not compare the cost of multiple gossip rounds vs. direct use of a more advanced averaging approach (like exponentiated gradient-based gossip). Hence, the evaluation partly relies on a simplified measure of “communication rounds” that may not reflect real overhead in heterogeneous network conditions.\n\n3. The authors do not show error bars or repeated runs to reveal the variance. If the approach can converge quickly in a median sense but sometimes fails or stalls, that variability matters.\n\n4. Real distributed environments might have node-level heterogeneity in CPU/GPU power. The paper’s simple model (uniform local iteration cost) might mask how well the proposed method handles uneven computation resources.\n\n5. They do not evaluate generalization or test accuracy on complex tasks, even though logistic regression on MNIST is at least somewhat classification-driven. Since they focus on the training objective, it remains unclear whether the improved convergence speed translates to superior test-time performance or any difference in model quality for real tasks.", "methods_and_evaluation_criteria": "1. The paper focuses on scenarios where nodes each hold unique local data and where communication is expensive (ring, mesh, or general sparse networks). The proposed proximal-point-based methods (Inexact-PDO, SPDO, Accelerated-SPDO) are appropriate because they are designed to exploit partial overlap or “similarity” among local data while mitigating the high cost of frequent parameter exchanges.  \n   - **Proximal Decentralized Framework**: The premise that each node solves a proximal subproblem (to reduce the discrepancy introduced by local data differences) matches well with the objective of improving the method’s tolerance to data heterogeneity. By explicitly modeling subproblem accuracy, the approach is well-suited for large-scale problems where exact solutions would be prohibitive.\n\n2. **Evaluation Criteria in Experiments**  \n   - **Communication Cost vs. Computation Cost**: The paper measures success primarily through (i) *communication rounds* needed to achieve a target accuracy and (ii) total *local gradient steps* or “computation.” These criteria are standard in the literature for decentralized and federated settings, where the ratio of communication time to local computation time can be crucial.  \n   - **Choice of Datasets**: MNIST is typical for small-scale proof-of-concept experiments, and the authors artificially control heterogeneity (via the Dirichlet parameter \\(\\alpha\\)), which *does* illustrate how the algorithms handle varying levels of data similarity. Although it is limited in scope, it still effectively shows the benefit of reduced communication for more homogeneous local data.  \n   - **Metric of Accuracy**: The authors primarily track objective function decrease or gradient-norm decrease as a function of both communication and computational steps, consistent with standard optimization benchmarks.\n\n3. **Potential Gaps or Areas for Improvement**  \n   - **More Diverse Benchmarks**: While MNIST is a reasonable start, real-world distributed data could be more irregular than a simple Dirichlet partition. Adding more varied datasets (e.g., from large-scale text or image tasks, or from industry-scale streaming data) would broaden the demonstration of the method’s performance.  \n   - **Full Validation of \\(\\delta\\)**: The authors claim that as \\(\\alpha\\) increases, local objectives become more similar (\\(\\delta\\) decreases). However, they do not empirically measure or approximate \\(\\delta\\). A direct empirical validation of \\(\\delta\\)’s role would strengthen the link between method and claimed advantages.\n\nOverall, the proposed methods and evaluation criteria (communication rounds, local gradient steps, final training loss or gradient norm) are coherent for the paper’s decentralized-learning context. While the experimental design could be expanded with more datasets and more direct measurement of data similarity, the chosen metrics and problem setups do largely align with how such methods are tested in the broader decentralized optimization literature.", "theoretical_claims": "1. The paper introduces \\delta via\n       \\frac{1}{n} sum_{i=1}^n \\|\\nabla h_i(x) - \\nabla h_i(y)\\|^2 \n       \\delta^2 \\,\\|x - y\\|^2,\n       where h_i(x) = f(x) - f_i(x).\n\n     This condition implies a “second-order” type similarity across nodes. However, in practical large-scale systems, it often suffices to assume the simpler Lipschitz-smooth condition on each f_i. Your proposed approach places an emphasis on the difference h_i as if each node’s local function is nearly identical to f. \nThe text does not thoroughly discuss the real-world consequences if \\delta is not as small as assumed. In particular, while \\delta\\leq L always holds when each f_i is L-smooth, the presentation glosses over the implications of \\delta being close to L. When \\delta\\approx L, do the improvements over classical decentralized methods persist or vanish? A deeper quantitative exploration would strengthen the argument.\n\n2. In the “Inexact-PDO” framework, one solves, at each node i:\n       x_{i}^{(r + 1/2)} \n       \\approx\n       \\arg\\min_{x} (\n         f_i(x)+\\;\\langle h_i^{(r)},\\,x\\rangle + \\tfrac{\\lambda}{2}\\|x - x_{i}^{(r)}\\|^2\n       ).\n\n     This subproblem solution is then subjected to a gradient-norm accuracy requirement, for instance\n\n       \\sum_{i=1}^n \\|\\nabla F_{i,r}(x_{i}^{(r + 1/2)})\\|^2  \n       \\frac{\\delta\\,(4\\,\\delta+\\mu)}{4(r+1)(r+2)} \n      \\sum_{i=1}^n\n       \\|x_{i}^{(r + 1/2)} - x_i^{(r)}\\|^2.\n     or something of that flavor depending on the theorem. \nThe paper asserts (e.g., Theorem 1 and subsequent corollaries) that as long as these local subproblems are solved “just enough,” one obtains the same rate as an exact solution. However, it leaves open the question of how many iterations of, say, Nesterov’s or plain gradient descent one actually needs on typical problem instances before the sum of squared gradient norms condition is met. In a typical large neural-net scenario, bounding the subproblem error explicitly would require non-trivial additional assumptions. The paper’s guidelines could be clearer, for example by including bounds on the per-round local iteration cost or enumerating precisely how local complexity scales with \\delta \\mu, and the network size n.\n\n3.  The authors emphasize that the new method “only” needs \\mathcal{\\tilde O}(\\frac{\\delta}{\\mu(1-\\rho)}\\log(\\frac{1}{\\varepsilon}) communications in the strongly convex case, improving from \\delta_{\\max} to \\delta. \nAt the same time, they do not solve each local subproblem exactly, so the iteration cost is typically \\mathcal{\\tilde O}(\\sqrt{\\tfrac{L}{\\delta+\\mu}}) or something close (depending on the theorem) for each subproblem.  Although the paper is correct that \\delta < \\delta_{\\max} may confer a significant advantage if local data are indeed “similar,” it might also be that local subproblems require many gradient steps if \\delta is not truly small relative to L. The statements about “lower communication cost” can be somewhat overshadowed if the local computations blow up. \n\n4.  While the authors adapt the classic Hybrid Projection Proximal-Point idea (Solodov & Svaiter style) to the decentralized setting, the transitions from \\mathbf{x}-updates to \\mathbf{v}-updates are presented somewhat abruptly. The role of the stabilizing variable \\mathbf{v}, especially in how it prevents the subproblems from requiring ever-increasing precision, is mathematically elegant but might be clearer if placed in a stand-alone lemma that (i) proves stability and (ii) ensures the same or better rate as the simpler approach. Currently, the text interweaves the definitions with the main theorems, and it is easy for the reader to lose track of the key steps that guarantee the claimed \\mathcal{\\tilde O}(\\log(\\frac{1}{\\varepsilon})) complexity.", "experimental_designs_or_analyses": "1.  Nowhere do the authors directly measure or approximate \\delta (the second-order dissimilarity measure) in the actual experiments. Instead, they rely on \\alpha from the Dirichlet distribution as a surrogate. Mathematically, it would be more rigorous to approximate \\delta in practice—for instance by sampling the norms \\|\\nabla f_i(x)-\\nabla f_j(x)\\| for random x values—and plotting them, so the audience can see how \\delta scales with \\alpha. This would confirm that changes in \\alpha truly reflect the second-order similarity the theorems rely on.\n\n2. When regularization is small or absent \\mu \\approx 0, the theoretical bounds predict the “convex case” complexities. However, the experiments do not provide a quantitative link between \\mu and the actual speed. In particular, one expects the theoretical number of rounds for a certain \\varepsilon-accuracy to be on the order of \\mathcal{O}(\\tfrac{\\delta}{(1-\\rho)\\varepsilon}) if \\mu = 0. Yet the main figures only show *empirical* curves without clarifying whether they align with or deviate from \\mathcal{O}(\\frac{1}{\\varepsilon} or \\mathcal{O}(\\log(\\tfrac{1}{\\varepsilon})). It would be helpful to fit the observed convergence data to a model or produce a slope in log–log space, so the experimental results can be interpreted alongside the proposed theorems.\n\n3. It would strengthen the experimental section if the authors demonstrated at least one experiment systematically varying M—for instance, letting M take on \\{1, 5, 10, 20\\}—so that one can see how error from incomplete averaging impacts performance. For example, if \\rho is large (due to a sparse topology), the authors claim we need more gossip steps to maintain \\rho^M \\le \\tfrac{\\delta}{6L}. But no chart in the paper explicitly shows how changing M in practice affects communication overhead, final test accuracy, or speed of convergence. This is a missed opportunity to confirm the theory.\n\n4.  In the main results, multiple hyperparameters—\\(\\lambda\\), \\(M\\), local-step learning rate \\(\\eta\\), etc.—are presumably tuned. However, the paper shows only a single set of final curves comparing the proposed method with baselines.  It would be more persuasive to include plots (or at least a table) that show how the final performance depends on each hyperparameter. For example, if \\(\\lambda\\) is set too large, do local subproblems become trivial or degenerate, and does that hamper performance? If \\(\\eta\\) in the local subproblem solver is too large, do we see instability? The authors do mention some tuning, but they do not systematically present the experimental process. This makes reproducibility more difficult, and it also leaves open the question of how sensitive the proposed method is to hyperparameters compared to classical gradient tracking or SONATA.\n\n5. The paper’s plots do not show confidence intervals or variance across runs. This is standard practice in many experimental ML contexts to gauge robustness.  If the proposed method’s advantage is that it converges faster in both “communication rounds” and “computation steps,” but at the cost of some potential variance from the approximate subproblem solutions, readers should see that tradeoff empirically. For instance, one might observe that fewer gossip steps or fewer local subproblem iterations lead to higher variance in the final solution. The paper could show standard deviation bands or quartiles across multiple random seeds.", "relation_to_broader_scientific_literature": "1. The paper fundamentally relies on the classic Proximal-Point Method, originally studied in the single-node, centralized setting. Past work has shown that one can address inexact subproblem solutions via “hybrid” or “projection-based” proximal iterations (Solodov, Mikhail V., and Benar Fux Svaiter. \"A new projection method for variational inequality problems.\" SIAM Journal on Control and Optimization 37.3 (1999): 765-776. Monteiro, Renato DC, and Benar F. Svaiter. \"Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers.\" SIAM Journal on Optimization 23.1 (2013): 475-507.). By adapting these ideas to the decentralized environment, this paper continues a line of research on how to relax exact subproblem requirements while still maintaining strong theoretical guarantees.  \n\n2. In the decentralized setting, accelerating methods like SONATA or gradient-based approaches often requires delicate handling of local steps or momentum terms. (Tian, Ye, et al. \"Acceleration in distributed optimization under similarity.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2022) for second-order similarity (with \\delta_{\\max}) but mandated exact or high-precision subproblem solves at each round.", "essential_references_not_discussed": "NA.", "other_strengths_and_weaknesses": "1. While the paper introduces a well-crafted approach, it is also somewhat incremental: it adapts prior tools (e.g. Monteiro–Svaiter acceleration, Gossip averaging, SONATA) rather than introducing a wholly new algorithmic paradigm. The novelty lies chiefly in how these ideas are fused, rather than in an entirely new foundational concept.\n2. Although the appendices are extensive, the main body can feel dense at times. Key distinctions—like why the new “stabilized” scheme so dramatically eases local subproblem accuracy demands—could be emphasized more. Some readers may need more immediate intuition or examples within the text (rather than buried in appendices).\n3. The methods involve multiple hyperparameters (λ, 𝑀, local step sizes, acceleration constants). The paper gives guidelines, but does not comprehensively detail how sensitive the final performance is to these parameters.", "other_comments_or_suggestions": "NA", "questions_for_authors": "NA", "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": "TW0baePl39", "reviewer": "Reviewer_pn8d", "summary": "This paper studies decentralized optimization, and it proposes several decentralized methods and analyses their convergence. Specifically, they show that their methods achieve the state-of-the-art communication and computation complexity.", "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 examining our paper.\n\n> The methods are closely related to two existing works (Scutari \\& Sun, Li 2020) as discussed in the paper. However, the connection is not clear enough: [...]\n\nOur paper and existing papers [1,2] use a slightly different notation, which might confuse the reviewer.\nWe clarify it in the following.\n\nLet define $y_i^{(r)} :=  h_i^{(r)} + \\nabla f_i (x_i^{(r)})$. If we replace $h_i$ with $y_i$ in PDO, we obtain almost the same algorithm as Algorithm 1 shown in [1] as SONATA.\nThe difference is that PDO solves the subproblem approximately, while SONATA needs to solve it exactly.\nNote that the original SONATA [2] has an additional hyperparameter $\\alpha$ (See Algorithm 1 in [2]), but as shown in [1], $\\alpha$ is not essential, and we can set $\\alpha=1$.\nThus, more precisely speaking, PDO contains the original SONATA with $\\alpha=1$ as a special instance.\n\nIf the reviewer still has concerns, we would appreciate being informed. \nWe will be happy to resolve them.\n\n> It is difficult for me to understand the difference between PDO and Stablized PDO. [...] If this is true, then the novelty and contribution of SPDO will be questionable.\n\nWe respectfully disagree with this reviewer's comment.\nThanks to the update rule of $v$, Stabilized PDO can solve the subproblem more coarsely than PDO (see Eqs. (8) and (9)) and is computationally less expensive.\n\nSpecifically, the update rule of $v$ is not a simple gradient descent step.\nWhen $\\mu=0$, the update rule of $v$ is $v_i^{(r)} - \\frac{1}{\\lambda} (\\nabla f_i (x_i^{(r+1)}) + h_i^{(r)})$. The gradient is computed at $x$ instead of $v$, and it is not a simple gradient descent.\nIt plays a crucial role in reducing computational complexity.\n\n> In Algorithm 1, the last term in the update of $h_i$ should be $\\nabla f_i(x_i^{(r+1)})$ or $\\nabla f_i(x_i^{(r)})$? [...]\n\nThank you for carefully checking our algorithm.\nThis is not a typo, and Algorithm 1 is correct.\nWe wonder if the reviewer might be confused since we use slightly different notations from [1] and [2].\nSee our response to your first comment.\nIf the reviewer still has concerns, we would be glad to resolve them.\n\n> Typo: In Line 4 of Algorithm 2, it should be $a_j^{(m)}$ rather than $a_j^{(r)}$.\n\nThank you for pointing this out.\nWe will fix it in the revised manuscript.\n\n> Regarding the theorem itself, the assumption seems to be very strong, and except for affine functions, it is difficult for me to find any other functions that satisfy Assumption 3.\n\nWe would respectfully disagree with this reviewer's comment.\n**All of our theorems, Theorems 1-6, use only Assumptions 1, 2, and 4 and do not use Assumption 3.**\n\nAs we explained in lines 120-126, the existing methods, SONATA and Accelerated SONATA, used Assumption 3, while our proposed methods and theorems successfully omit Assumption 3. Instead of using Assumption 3, we use Definition 1. As we mentioned in Remark 1, Definition 1 is not an assumption since **all $L$-smooth functions satisfy Eq. (3) with $\\delta \\leq 2 L$.**\nWe can check this by the following inequalities:\n\\begin{align*}\n\\frac{1}{n} \\sum_{i=1}^n \\| \\nabla h_i(x) - \\nabla h_i (y)\\|^2 \n\\leq 2 \\| \\nabla f (x) - \\nabla f(y)\\|^2 + \\frac{2}{n} \\sum_{i=1}^n \\| \\nabla f_i(x) - \\nabla f_i (y)\\|^2 \\leq 4 L^2 \\| x - y\\|^2\n\\end{align*}\n\n> [...] I suggest them to also include primal-dual type methods for comparison.\n\nThank you for your suggestion.\nThe papers the reviewer mentioned [A,B,C,D] do not utilize the similarity $\\delta$. Thus, our proposed methods, PDO, Stabilized PDO, and Accelerated-PDO, can achieve better communication complexity by utilizing the similarity of local functions, especially when $\\delta \\ll L$.\nWe will cite the papers the reviewer mentioned and add the discussion in the revised manuscript.\n\n\nWe believe these additions clarify the relationship between existing and our proposed methods, strengthening our paper.\nTherefore, we kindly ask the reviewer to reassess their score. If further concerns remain, we are happy to address them.\n\n\n## Reference\n[1] Tian, Y., Scutari, G., Cao, T., and Gasnikov, A. Acceleration in distributed optimization under similarity. In AISTATS, 2022.\n\n[2] Sun, Y., Scutari, G., and Daneshmand, A. Distributed optimization based on gradient tracking revisited: Enhancing convergence rate via surrogation. In SIAM Journal on Optimization, 2022.", "claims_and_evidence": "The claims are fair.", "methods_and_evaluation_criteria": "1. The methods are closely related to two existing works (Scutari & Sun, Li 2020) as discussed in the paper. However, the connection is not clear enough:\n\n- In Page 3, they said that \"PDO contains SONATA (Sun et al., 2022) as a special instance when the proximal subproblem is solved exactly. The proofs are deferred to Sec. C and F.2.\". I tried to find the explanation of why SONATA is a special case, but didn't find it in Appendix C and F.2.\n\n- In Page 5, it says that \"The framework of PDO was initially introduced by Li et al. (2020) and Sun et al. (2022)\". However, it's difficult for me to understand their connection when I checked the two references.\n\n2. It is difficult for me to understand the difference between PDO and Stablized PDO. It seems that the update of v in SPDO is simply a gradient descent step with respect to the objective function in the update of x. If so, then $v_i^{(r+1)}$ is also an approximate solution to the minimization problem associated with the update of $x_i$. If this is true, then the novelty and contribution of SPDO will be questionable.\n\n3. The authors should provide more details on the algorithm development. I mean, it is important for the readers to understand the philosophy of the algorithm development and in the current version, it is not easy to understand these methods.\n\n4. Question: In Algorithm 1, the last term in the update of h_i should be $\\nabla f_i(x_i^{(r+1)})$ or $\\nabla f_i(x_i^{(r)})$? I ask this question mainly because that in gradient-tracking type methods, the updates usually involve old gradients.\n\n5. Typo: In Line 4 of Algorithm 2, it should be $a_j^{(m)}$ rather than $a_j^{(r)}$.", "theoretical_claims": "I didn't check the proof. Regarding the theorem itself, the assumption seems to be very strong, and except for affine functions, it is difficult for me to find any other functions that satisfy Assumption 3.", "experimental_designs_or_analyses": "Didn't find any issue with the experimental design.", "relation_to_broader_scientific_literature": "Unclear.", "essential_references_not_discussed": "They mainly discuss gradient-tracking type methods when comparing the computation and communication complexity. I suggest them to also include primal-dual type methods for comparison. To list a few:\n\n[A] S. A. Alghunaim, E. Ryu, K. Yuan, and A. H. Sayed, “Decentralized proximal gradient algorithms with linear convergence rates,” IEEE Trans. Autom. Control, vol. 66, no. 6, pp. 2787–2794, Jun. 2021.\n\n[B] J. Xu, Y. Tian, Y. Sun, and G. Scutari, “Distributed algorithms for com- posite optimization: Unified framework and convergence analysis,” IEEE Trans. Signal Process., vol. 69, pp. 3555–3570, Jun. 2021.\n\n[C] A. Makhdoumi and A. Ozdaglar, “Convergence rate of distributed ADMM over networks,” IEEE Trans. Autom. Control, vol. 62, no. 10, pp. 5082–5095, Oct. 2017.\n\n[D] X. Wu and J. Lu, \"A Unifying Approximate Method of Multipliers for Distributed Composite Optimization,\" in IEEE Transactions on Automatic Control, vol. 68, no. 4, pp. 2154-2169, 2023\n\nThe communication complexity of these primal-dual methods are often competitive. For example, the communication complexity of [C] is $O(\\frac{\\sqrt{\\kappa}}{1-\\rho})$ where $\\kappa$ is the condition number. This communication complexity is competitive compare to that of the non-accelerated methods discussed in Table 1.", "other_strengths_and_weaknesses": "Discussed above.", "other_comments_or_suggestions": "No", "questions_for_authors": "No", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "C7UKcO69OC", "reviewer": "Reviewer_vkTV", "summary": "This paper introduces the Stabilized Proximal Decentralized Optimization (SPDO) method, which achieves state-of-the-art communication and computational complexities within the Proximal Decentralized Optimization (PDO) framework. The authors also propose an accelerated variant (Accelerated-SPDO) based on the Monteiro and Svaiter acceleration method. The paper is well-written, and the proposed algorithms appear promising. Below are detailed comments and suggestions to further improve the paper.\n\n\n## update after rebuttal\nAfter the rebuttal, the authors promised to add the proof sketch in the camera-ready version and fix the paper to clarify the contribution.", "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 the positive feedback.\n\n> The paper would benefit from providing a proof sketch for key theoretical results, particularly for the convergence analysis.\n\nThank you for the suggestion.\nWe promise to add the proof sketch in the camera-ready version.\n\n> The Accelerated-SPDO algorithm seems to be a straightforward extension of SPDO by incorporating the Monteiro and Svaiter acceleration method. However, are there any unique challenges or modifications required to apply this acceleration in the decentralized optimization setting?\n\nThe primary challenge of proposing our methods is that a straightforward combination of Hybrid Projection Proximal-point Method, multiple gossip averaging, and gradient tracking does not work (See the update rule in lines 262-274 and discussion in lines 275-295).\nTo overcome this, we proposed a carefully designed modification in Algorithm 3 (see the update rule highlighted in blue).\nThe same modification is also necessary for Accelerated SPDO, which is one of the primary novelties of our paper.\n\n> [...] the contribution bullets list the accelerated method first. To improve clarity and consistency, it would be better to align the sequence of the contribution bullets with the flow of the paper.\n\nThank you for the suggestion.\nWe will fix the paper to clarify the contribution.\n\n> Can the proposed SPDO and Accelerated-SPDO algorithms be applicable to nonconvex optimization problems?\n\nPDO, SPDO, and Accelerated-SPDO are designed specifically for convex optimization problems, and their applicability to non-convex optimization is not guaranteed. \nHowever, developing algorithms in the convex case is an important first step for studying algorithms in the more challenging non-convex case. \nWe believe that our work provides valuable insights that could contribute to the development of future algorithms for non-convex optimization problems.\n\n> [...] Can the authors provide more intuition or insight into why SPDO achieves this improvement?\n\nThe main drawback of existing methods, including Decentralized SGD and Gradient Tracking, is that they cannot utilize the multiple local steps.\nIn their local update, each node performs gradient descent, but fully minimizing the objective function is not desirable.\nFor Decentralized SGD, [1] showed that we need to decrease the stepsize when we increase the number of local updates to not fully minimize the objective function.\nCompared with them, PDO, SPDO, and Accelerated PDO can solve the subproblem in their local update, which leads to lower communication complexities.\n\n## Reference\n\n[1] Koloskova, A., Loizou, N., Boreiri, S., Jaggi, M., and Stich, S. A unified theory of decentralized SGD with changing topology and local updates. In ICML, 2020.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "No", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "This paper addresses key challenges in the literature, particularly in terms of computation and communication efficiency.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths: \n- The paper is well-written, and the proposed algorithms appear promising with rigorous theoretical validation. \n\nWeaknesses: \n- The paper would benefit from providing a proof sketch for key theoretical results, particularly for the convergence analysis. This would make the paper more accessible to readers.\n- The Accelerated-SPDO algorithm seems to be a straightforward extension of SPDO by incorporating the Monteiro and Svaiter acceleration method. However, are there any unique challenges or modifications required to apply this acceleration in the decentralized optimization setting? If so, these challenges should be highlighted and discussed in detail.\n- The experimental section is promising but could be significantly strengthened if including experiments on additional datasets and models to validate the generality of the proposed methods.", "other_comments_or_suggestions": "Suggestion:\n\n- In the main body of the paper, the authors first present the non-accelerated SPDO method followed by the accelerated version. However, the contribution bullets list the accelerated method first. To improve clarity and consistency, it would be better to align the sequence of the contribution bullets with the flow of the paper.", "questions_for_authors": "- Can the proposed SPDO and Accelerated-SPDO algorithms be applicable to nonconvex optimization problems? \n- The authors claim that SPDO achieves improved communication complexity compared to existing methods. Can the authors provide more intuition or insight into why SPDO achieves this improvement?", "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: All reviewers agree that this paper makes a solid contribution to the field of decentralized optimization and recommend acceptance. The paper addresses a key limitation of existing DPO methods, which often rely on highly accurate solutions to proximal subproblems and thus incur high computational costs. The proposed SPDO method effectively overcomes this issue, achieving state-of-the-art communication and computation complexities. Additionally, the authors provide a refined theoretical analysis by relaxing subproblem accuracy requirements and leveraging average functional similarity. The results are well-motivated, clearly presented, and supported by solid theoretical and empirical evidence. I recommend acceptance.
Decision: Accept (poster)