Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysis
Authors: Dachao Lin
Yuze Han
Haishan Ye
Zhihua Zhang
Venue: NeurIPS 2023 poster (2023)
Keywords: distributed optimization
convex optimization
second-order similarity
client sampling
TL;DR: We propose two new algorithms (SVRS and AccSVRS) that achieve better communication complexity in distributed optimization under similarity condition.

Abstract: We study finite-sum distributed optimization problems involving a master node and $n-1$ local nodes under the popular $\delta$-similarity and $\mu$-strong convexity conditions. We propose two new algorithms, SVRS and AccSVRS, motivated by previous works. The non-accelerated SVRS method combines the techniques of gradient sliding and variance reduction and achieves a better communication complexity of $\tilde{\mathcal{O}}(n {+} \sqrt{n}\delta/\mu)$ compared to existing non-accelerated algorithms. Applying the framework proposed in Katyusha X, we also develop a directly accelerated version named AccSVRS with the $\tilde{\mathcal{O}}(n {+} n^{3/4}\sqrt{\delta/\mu})$ communication complexity. In contrast to existing results, our complexity bounds are entirely smoothness-free and exhibit superiority in ill-conditioned cases. Furthermore, we establish a nearly matched lower bound to verify the tightness of our AccSVRS method.

Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysis
Dachao Lin
+
Yuze Han +
Haishan Ye
Zhihua Zhang
Abstract
We study finite-sum distributed optimization problems involving a master node and n 1 local nodes under the popular 5-similarity and ju-strong convexity conditions. We propose two new algorithms, SVRS and AceSVRS, motivated by previous works. The non-accelerated SVRS method combines the techniques of gradient sliding and variance reduction and achieves a better communication complexity of Onn+VVni ()) compared to existing non-accelerated algorithms. Applying the framework proposed in Katyusha X [6]. we also develop directly accelerated version named AccSVRS with the On++n3/4 /8// communication complexity. In contrast to existing results, our complexity bounds are entirely smoothness free and exhibit superiority in ill-conditioned cases. Furthermore, establish nearly matched lower bound to verify the tightness of our AccSVRS method.
Introduction
We have witnessed the development of distributed optimization in recent years. Distributed opti- mization aims to cooperatively solve learning task over predefined social network by exchanging information exclusively with immediate neighbors. This class of problems has found extensive applications in various fields, including machine learning, healthcare, network information process- ing, telecommunications, manufacturing, natural language processing tasks, and multi-agent control In this paper, we focus the following classical finite-sum optimization problem in a centralized setting:
(54 30 48
45 60
n min f(x) = n Σ f((z).
WEE
where each fa differentiable and corresponds to a client or node, and the target objective their average function f. Without loss of generality, we assume fi is the master node and the others are local nodes. In each round, every local node can communicate with the master node certain information, such as the local parameter local gradient V fi()), and some global information gathered the master node. Such scheme can also be viewed as decentralized optimization over a star network [55].
Following the wisdom of statistical similarity residing in the data different nodes, many previous works study scenarios where the individual functions exhibit relationships or, more specifically, certain homogeneity shared among the local f and f. The most common one under the 5-second-order
Equual Contribution.
AAcademy for Advanced Interdisciplinary Studies: Peking University: lindachao@pku. edw.eeppkkuuuuuueee.. en;
$ 'School of Mathematical Sciences; Peking University: hanyuze97ēpku. edu.. en:
*Corresponding Author; School of Management; Xi'an Jiaotong University: SGIT Al Lab, State Grid Corporation China; yehaishan@xjjt tu. edu.cn:
School of Mathematical Sciences; Peking University; zhzhang@math, .ku..puuu edu. en.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

similarity assumption 33 35 that is,
V (z)) - - 5, Va E R E (1......n).
Such an assumption also has different names in the literature, such as d-related assumption, bounded Hessian dissimilarity, or function similarity 7 32 51 55 62]. The rigorous definitions are deferred to Section 2 Moreover, the second-order similarity assumption can hold with a relatively small compared to the smoothness coefficient of f in many practical settings, such statistical learning. More insights on this can be found in the discussion presented in [54] Section 2J. The similarity assumption indicates that the data across different clients share common information on the second- order derivative, potentially leading to reduction in communication among clients, Meanwhile, the cost of communication is often much higher than that of local computation in distributed optimization settings [9] 44 30 Hence, researchers are motivated to develop efficient algorithms characterized by low communication complexity, which is the primary objective of this paper as well.
Furthermore, we need to emphasize that prior research 225 56
63 19
5 has shown tightly
matched lower and upper bounds computation complexity for the finite-sum objective in Eq. ( These works focus on gradient complexity under (average) smoothness complexity under similarity. Indeed, we will also discuss and compare the gradient complexity as
(63
instead of communication
shown in 35 to explore the trade-off between communication and gradient complexity.
Although the development of distributed optimization with similarity has lasted for years, the optimal complexity under full participation was only recently achieved by Kovalev et al. [35]. They employed
gradient-sliding (37] and obtained the optimal communication complexity On / /8/H) for p-strongly convex f and ô-related fi's in Eq. (T. However, the full participation model requires the calculation of the whole gradient f.()), which incurs a communication cost of n-1 in each round. In contrast, partial participation could reduce the communication burden and yield improved complexity. Hence, Khaled and Jin (33) introduced client sampling, a technique that selects one client for updating in each round. They developed non-accelerated algorithm SVRP, which achieves the communication complexity of O(++52/ //²).. Additionally, they proposed Catalyzed version of SVRP with the complexity Ö(n+n3/4 Saama/////// V0/p), which better than the rates obtained in the full participation setting.
We believe there are several potential avenues for improvement inspired by [33. 1) Khaled and Jin [33 introduced the requirement that each individual function is strongly convex (see [33 Assumption 2I). However, this constraint is absent in prior works. Notably, in the context of full participation, even approach to solving where each component is smooth and non-convex, but the average function remains convex. Thus doubt the necessity of requiring strong convexity for individual components. 2) In hindsight, it seems that the directly accelerated SVRP could only achieve bound of Ö( /n-vnn 5/p) based on the current analysis, which is far from being satisfactory compared to its Catalyzed version. Consequently, there might be room for the development of more effective algorithm for direct acceleration. 3) It is essential to note that the Catalyst framework introduces an additional log term in the overall complexity, along with the challenge of parameter tuning. This aspect is discussed in detail in [6) Section 1.2]. Therefore, we intend to address the aforementioned concerns, particularly on designing directly accelerated methods under the second-order similarity assumption.
non-convexity is deemed acceptable A prominent example the shift-and-inet
PCA 52 23
1.1 Main Contributions
In this paper, we address the above concerns under the average similarity condition. Our contributions presented in detail below and we provide comparison with previous works in Table T
First, we combine gradient sliding and client sampling techniques to develop an improved non-accelerated algorithm named SVRS (Algorithms) I. SVRS achieves a communication complexity of Ö(n + Vn- 5/μx). surpassing SVRP in ill-conditioned cases. Notably, this rate does not need component strong convexity and applies to the function value gap instead of the parameter distance.
Second, building SVRS, we employ classical interpolation framework motivated by Katyusha X 6 to introduce the directly accelerated SVRS (AceSVRS, Algorithm 2
'Readers can check that the proof of (35) only requires fa + 29 11:11 is strongly convex, which can be guaranteed by d-second-orde similarity since f p-strongly convex and 0 1/(28) therein.

---

Table Comparison communication under similarity for the strongly convex objective.
Method/Reference
Communication complexity
Assumptions
No Sampling
AccExtragradicnt 35
O
7
log
SS only for fi
Lower bound
log
1
SS for fi's
SVRP 33
72 +
log
SC for f:'s, AveSS
Catalyzed SVRP
33
O
+
n/4
log
log
SC for fi AveSS
Client Sampling
SVRS (Thm 3.3
nu + vn 8 x
log
AveSS
AccSVRS (Thm
3.6
n 3/4
log
AveSS
Lower bound (Thm 4.4
n2 3/4
log
AveSS
The rate only applics E [[ ot 113, otherwise it would introduce L in the log term; The temm L/(())) comes from Catalyst framework. Appendix C for the detail. (2.) Here only list
the common ill-conditioned case: Ja (L) See Appendices the remaining case. Notation: desimilarity parameter (both Lexmoohhess consiant of f. pesttron convexity constant f(or fi's), c=emor of the solution for (.f(xs (((x)))ffe (-((m)). Here O. Abbreviation: SC=strong convexity, SS=second order similarity, AveSS=average SS.
AveSS),
L L 8 2
AccSVRS achieves the same communication bound of Ö(n + n3/4 /o/u)) as Catalyzed SVRP. Specifically, our bound is entirely smoothness- free and slightly outperforms Cat- alyzed SVRP, featuring log improvement and not requiring component strong convexity.
Third, by considering the proximal incremental first-order oracle in the centralized dis- tributed framework, we establish a lower bound, which nearly matches the upper bound of AccSVRS in ill-conditioned cases.
1.2 Related Work
Gradient sliding/Orack Complexity Separation. For optimization problems with separated structure multiple building blocks, such as Eq. ( there are scenarios where computing the gradients/values of some parts (or the whole) is more expensive than the others (or partial one).
In response this challenge, techniques such as the gradient-sliding method 37 and the concept of oracle complexity separation [28) have emerged. These methods advocate for the infrequent use of more expensive oracles compared to their less resource-intensivy counterparts. This strategy has found applications in zero-order [12 21 28 53 first-order (37-39 39 31 and high-order methods
31 24 3 as well as addressing saddle point problems 4 13 Our algorithms can viewed as variance-reduced version of gradient sliding tailored to leverage the similarity assumption.
Distributed optimization under similarity. Distributed optimization has long history with plethora of existing works and surveys. To streamline our discussion, we only list the most relevant references, particularly under the similarity and strong convexity assumptions. In the full participation setting, which involves deterministic methods, the first algorithm credits to DANE (5T). though its analysis is limited quadratic objectives. Subsequently, AIDE [50). DANE-LS and DANE-HB (58) improved the rates for quadratic objective; Disco [62] SPAG (27), ACN II and DiRegINA (18) improved the rates for self-concordant objectives. As for general strongly convex objectives, Sun et al. [54] introduced the SONATA algorithm. and Tian et al. (55) proposed accelerated SONATA. However, their complexity bounds include additional log factors. These factors have recently been removed by Accelerated Extragradient [35), whose complexity bound perfectly matches the lower bound in 77. We highly recommend the comparison of rates in 35 Table 1] for a comprehensive overview. Once the discussion of deterministic methods is concluded, Khaled and Jin (33 shifted their focus to stochastic methods using client sampling. They proposed SVRP and its Catalyzed version, both of which exhibited superior rates compared to deterministic methods.
3

---

2 Preliminaries
Notation. We denote vectors by lowercase bold letters (e.g.,
w. w,,) .)), and matrices by capital bold letters (e.g., A, B). We let || be the f2-norm for vectors, or induced fz-norm for a given matrix: ||| = sup ||Aul|/ / ||u]| We abbreviate [n]] = [I.....,n) and La E Rdxd is the identity matrix. We use 0 for the all-zero vector/matrix, whose size will be specified by subscript, if necessary. and otherwise is clear from the context. We denote SS) as the uniform distribution over set S. We say T ~ Geom(p) for p E (0, 10 if IP(T
k) (1 p)- Ak E 2,,2,... ). i.e., T obeys geometric distribution. We adopt E, as the expectation for all randomness appeared in step k, and A as the indicator function on event A, i.c., LA = if event A holds, and 0 otherwise. We use O(),, (()),, (-) and Ó(.) notation to hide universal constants and log-factors. We define the Bregman divergence induced by a differentiable (convex) function h: Fd as DA (a. y) == h(x) h(y) - (Vh(y), y)-
Definitions. We present the following common definitions used in this paper.
Definition 2.1 differentiable function g: Rd + p-sttrongyy convex (SC) if glu) 2 g(œ) + (Vg(z), y x)) + Lh lly x01 Vx, IR Particularly, fp= 0, we say that is convex.
(2)
2
Definition 2.2 A differentiable function g: IR + L- L-smothh if
( S g(x) + (z) y x) + yy x Vx, Rd.
(3)
2
There are many basic inequalities involving strong convexity and smoothness, see [22 Appendix A.1] for introduction. Next, we present the definition of second-order similarity in distributed optimization.
Definition 2.3 The differentiable functions fo 's satisfy ô-average second-order similarity (AveSS) if the following inequality holds for 's and a 2 Lim
functioon
1 Σ
(AveSS)
[[ [(x)) ViS A( < 5² || 10--y Var, y TR..
Definition 2.4 The differentiable functions ft's satisfy 8-component second-orter similarity (SS) if the following inequality holds for f. 's' and n I:=1ft fr:
(SS) II[
f1(x) - Vif f1')]]1 8 | yll Yx, y E Rdd [n]]
(5)
Definitions 2.3 and 2.44 first appear in 133 which is an analogy to (average) smoothness in prior literature [63]. Partieularly, fi's satisfy A-AveSS implies that (f-f.)'s 's satisfy --average smoothness, while ft' satisfy d-SS implies that (f-fs)'s 's satisfy d-smoothness. Additionally, many researchers
62 54 35] use the equivalent one defined by Hessian similarity (HS) if assuming that f, are twice differentiable. Thus we also list them below and leave the derivation in Appendix
32 7 51
n
(AveHS)
Σ [T)(()) V2'()))>((<)]]
< (HS) (HS) [<) V V2 f(x))
||
S 6, Vi E [n].
(6)
n i=1
Since our algorithm is first-order method, we adopt the gradient description of similarity (Definitions 2.3 and 2.4) without assuming twice differentiability for brevity.
As mentioned in 7 54), if fi's satisfy 8-AveSS (or SS), and is jı-strongly convex and L-smooth. then generally L > >> fu > 0 for large datasets in practice. Therefore, researchers aim to develop algorithms that achieve communication complexity solely related to 8, μ (or log terms of L). This also our objective. To finish this section, we will clarify several straightforward yet essential propositions, and the proofs are deferred to Appendix A
Proposition 2.5 We have the following properties among SS, AveSS, and SC: 1) 8-SS implies 8-Ave5S, but 5-AveSS only implies VnS-SS. 2) If f. 's satisfy 8-SS and f is p-strongly convex, then for all 2 11-112 is convex, i.e., fo is (6 p))almost convex D4].
i f((-) + 8-2

---

3 Algorithm and Theory
In this section, we introduce our main algorithms. which are developed to solve the distributed optimization problem in Eq. ① under Assumption [bbel:::ooobwww::::
Assumption We assume that fi satisfy 8-AveSS, and f is jestrrongly convex with 8 82 μt O.
Assumption D does not need each f: to be p-strongly convex. In fact, it is acceptable that fü are non-convex, since by Proposition 2.5 fi are (/nd-p)--lmoo convex [14]. In the following. we first propose our new algorithm SVRS, which combines the techniques of gradient sliding and variance reduction, resulting improved rates. Then we establish the directly accelerated method motivated by [6].
3.1 No Acceleration Version: SVRS
We first show the one-epoch Stochastic Variance- Sliding (SVRSleP) method in Algorithm Before delving into the theoretical analysis, we present some key insights into our method. These insights aim to enhance comprehension and facilitate connections with other algorithms.
Variance Reduction. Our algorithm can be viewed as adding variance reduction from the acceleration step, the main difference lies in the proximal step, where Kovalev al. 35 solved:
35
Besides
1 F+++ s arg min B/g (x) == <V fx.)) - Vf( x xx)) + 20 I| x, 2 + (x)
#E
To save the heavy communication burden of calculating V f(e,), we apply client sampling by selecting random fi, (x+) the t-th step. However, this substitution introduces significant noise.
To mitigate this, we incorporate a correction term g: = fi, (wo) Vf(w)) from previous wisdom
29 to reduce the variance.
Gradient sliding. Our algorithm can be viewed as adding gradient sliding from SVRP [3). The main difference also lies in the proximal point problem, where Khaled and Jin (33 solved:
1c+1 se arg min (x) == (-9r, x - xx) + 20 1 x.11 + (z))
zER4
Here we adopt a fixed proximal function fi instead of fi,, which can be viewed as approximating
Ji fa (a)))f(()+((0))) [f))(=)+)))+++++++ /f xx)) 297 ||x- with properly chosen 0' >
Such a modification is motivated by (35). where they reformulated the objective as f(x))
[f(x) (z)] (x). Thus they could employ gradient sliding to skip heavy computations of - (i) by utilizing the easy computations
V (x) more times. Fixing the proximal function fi leads to the same metric space owned by fi in each step, which could benefit the analysis and alleviate the requirements on ft's compared to SVRP. Indeed, in our setting fi can be replaced by any other fixed client fu, [m]. In this case, the master node would be fe instead of f1-
Bregman-SVRG. Our algorithm can be viewed as the classical Bregman-SVel -VRGG 20 with the reference function fi(-) + 29 11-112 after introducing the Bregman divergence:
0t++1 RJ arg min (x) arg min (i,i(a))) [i, f[(w)) x.)) + D D11++ +o IM| (1, (.)
#ER
zERd
We need to emphasize that the proof of Bregman-S SVRG requires additional structural assumptions 20 Assumpotion 3), which is not directly applicable in our setting. Hence, the rigorous proof of Bregman-SVRG under our similarity assumption is still meaningful as far as we are concerned.
3.1.1
Communication Complexity under Distributed Settings
When applied to the distributed system, the communication complexity of SVRS1ePcan be described as follows: At the beginning of each epoch, the master (corresponding to fi) sends we to all clients. Each client computes V (w)) from local data and sends back to the master. The master then builds V f (wo) after collecting all V. (wo)))ss Ys. The communication complexity is 2(n 1) in this
5

---

Algorithm SVRS (ʃ, wp, p)
1: Input: wo E R p E (0, 1), 0>0000000000 0
2: Initialize Vo - Wo, compute V.((w), and set Geom (p)
3: for t = 0, 1, 2, ..... T
do
4: Sample i ~ (nif([n) [n]) and compute 9: Vi, (wy) vf(w0)
5: Approximately solve the local proximal point problem:
E++1 Fs arg min Ag(z) == (V;i, - Vf((z:)) 9r, x xx) + 20 11
xel1 + fi f()))
#ER"
6: end for
7: Output: 2T
case. Next, the algorithm enters into the loop iterations. In each iteration, the master only sends current Dy to the chosen client i,. The i,-th client computes Vf, (xy) and sends it to the master (the first client). Then the master solves (inexactly) the local problem (Line in Algorithm [ to get an inexact solution #++1- The communication complexity is 2 in this case. Thus, the total communication complexity of SVRS is 2(n 1) + 2T. Note that ET = 1/p and generally p 1/n. We obtain that one epoch communication complexity is 4n 2 in expectation.
We would like to emphasize that our setup differs from that 41 46), where the authors assume the nodes can perform calculations and transmit vectors in parallel. We recognize the significance of both setups. However, there are situations where communication is more expensive than computation. For instance, in business network communication network the communication between any two nodes can result charges and the risk of information leakage. To mitigate these costs, we should reduce the frequency of communication. Thus, we focus the nonparallel setting.
3.1.2 Convergence Analysis of SVRS
Based on the one-epoch method SVRS1eP, we could introduce our non-accelerated algorithm SVRS, which starts from wy E Rd and repeatedly performs the update"
W = SVRS (f. wk. O p), A4 0.
Now we derive the convergence rate of SVRS The main technique we apply is replacing the Euclidean distance with the Bergman divergence. Denote the reference function
h(x) = (1 20
| - f(x).
(8)
By Assumption I and 1) in Proposition 2.5
we see that fi's are Vnd-SS. SS. i.c., [f-- f](-) ())))ss is (Vπd)-
smooth. Thus, h((-) is ( /nd))strongh -stoongly convex and ( - if < Vno that is,
0
1 - Vne5
v11
DA y)
+
x
y
(9)
29
20
Hence, if n = (1), h(-) is nearly a rescaled Euclidean norm since its condition number related to ||-I| is 1+ym05 @(1). Next, employ the properties of the Bregman divergence Dr.., to
1-vn06
build the one-epoch progress of SVRSIePas as shown below:
Lemma 3.1 Suppose Assumption I holds. Let w SVRSS<P (f, wo, 0,p) with 0 = 1/(4/n0),
and the approximated solution T++1 satisfies
V (
/1
Et arg min A}(z) wERd
Vt 2 0.
(10)
200
"See Algorithm in Appendix D for the details.
SSimilar results for the popular loopless version
34 can also be derived, Appendix D.5 for the detail.

---

Algorithm 2 Accelerated SVRS (AccSVRS)
1: Input: 2a yo R p,7 7 (0, 1),
0, (1,2..)
2: for k = 0. 2,
K do
3: 2k+1 T2k -
4: yk+1 SVRS (ʃ, 26+1, 0,
5: GK+1 (Vlf- feel f (x f[ f3 + (Ix+1 yk+1)) .ik Unif((n))
6: Zk++1 arg minl Za || - z4 12 + (g++1, z) 3y
20 --y+++ll* zu 1..t0p.pay--1--0 19 1+0.3pa
7: end for
8:
Output: yK
Then for all x Rd that is independent of the indices i,, i2, .2....,17 ir in SVRS wo, O, we have
2 ) (wo: w+) 2pd Dn Dn( w wt).
B S SE Epppe wo Vh(ww) - -Vh(wo)) - (p- 9n
(11)
Remark 3.2 We note that some papers 11 TTV assume the smoothmess and convexity of compo- nent functions, and udopt local updates for solving the proximal step. However, we replace these assumptions with a proximal approximately solvable assumption (10), which could even cover some nonsmooth and non-convex but proximal trackable component functions. We regard our assumption as more essential since the local updates can be viewed as partially solving this proximal step.
The proof of Lemma 3.1 is left in Appendix D.I From Lemmal 3.1
we find a well-behaved proximal operator is sufficient ensure favorable progress. Finally, establish the convergence rate and communication complexity of the SVRS method, and the proof is deferred to Appendix D.2
Theorem 3.3 Suppose Assumption 1 holds. If in SVRS (PRSSI((Algooiiiii (Algorithm []. the hyperparameterss are set as =1/(4/n0), 1/n, and the approximate solution x4+1 in each proximal step satisfies Eq. (TO.. Then for any error E >> O, when
3 31+
[f(wr)) f(xx))
56
k K1 == max 2, uVn
log
E
i.e. after Ö(n + v communications in expectation, obtain that (.( - f(x.) S
Remark 3.4 Our results enjoy the following advantages over SVRP 33:: The convergence of SVRP (13 Theorem 2]) only applied to E l[w,, x=11² which also be derived by results from strong convexity: f(wx) f f(x)) ) 2 1/2 ||wx x.1l However, the reverse is not applicable since we do not assume the smoothness of f, or indeed the smoothness coefficient is very large. Moreover for ill- colciondttoneed problems (e.g.. 8/μi > vn), our step size 1/ 1/44/n8) much larger than p/ (2(2))
used in SVRP, and the convergence rate also faster than SVRP: (n + /nd/ μ)) vs. Ô (n+ 82/ Finally, we do not need the strong convexity assumption of component functions.
3.2 Acceleration Version: AceSVRS
Now we apply the classical interpolation technique motivated by Katyusha X (6) to establish acceler- ated SVRS (AceSVRS, Algorithmm2). The main difference between AccSVRS and Katyusha X is due to the different choices distance spaces. Specifically, we adopt (s instead of the Euclidean distance used in Katyusha X. Thus, the gradient mapping step (corresponding to Step 2 in 6 (4.1))) should be built on the reference function h(.) defined Eq. 8 i.e., Vh(I*++7 - Vh(g++1) instead
of (I W... Moreover, noting that Vh(-) could involve the heavy gradient computing part V (.), we further employ its stochastic version (Step 5 in Algorithm 2 to reduce the overall
communication complexity.
Next, we delve into the convergence analysis. We first give the core lemma for AceSVRS, which also motivated by the framework of Katyusha X (6). The proof is deferred to Appendix D.3
7

---

Lemma 3.5 Suppose Assumption 7 holds, and 0 = 1/(4/n5), 1/n.a S nd/ in Algo-
rithm 2 where SVRSLeP(f *f P) satisfies Eq. (T0) in each iteration. Then for all æ E R that
independent of the random indices ((4)) (14)) TT in SVRS
(R) /ep
(f. Ik+1, 8 p), we have that
Es a [f(UR+1) f(x)) - E 1)- a
[s(k)) - f(=)] - =x 1 0.3
a z 11
2
2
(12)
Finally, we present the convergence rate and communication complexity of AccSVRS based on Lemma 3.5 and the proof is left in Appendix D.4
Theorem 3.6 Suppose Assumption holds. Consider AccSVRS with the following hyperparameters
2/44
vn
0
4 n min
2
8
a
85T*
and Eq. 100 is satisfied in each iteration of SVRS lop (f. 1k+1, 8, p). Then for any E > 0, when
{ 8n 1/4 /o log ( [(x.))
k K2 max
L.., after Ô (n 3/44 V /0/u) communications in expectation, obtain that Ef(yk) ffae))-((aa f(xx)
Remark 3.7 Although roughly the same as the communication complexity obtained by Catalyzed SVRP in [33 Theorem 31, our results have the following advantages.
Fewer assumptions. Except for the strong convexity of f and AveSS of fi we do not need to assume component strong convexity appearing in [33 Assumption 2).
Inexact proximal step. Khaled and Jin 133 Theorem 3] require exact evaluations of the proximal operator, though they mention that this is only for the convenience of analysis. Our framework allows approximated solutions in each proximal step, and the upproximation criterion (TO) is error- independent, i.e., irrelevant to the final error E. Since the local proximal function is strongly convex, could solve the problem in few steps if additionally assuming the smoothness of f1-
Smoothness-free bound. As shown in [33 Appendix G.1] or Appendix even if an exact proximal step is allowed, dependence on the smoothness coefficient would be introduced in the total commu- nication iterations of Catalyzed SVRP, though only a log scale. Our directly accelerated method has no dependence on the smoothness coefficient.
3.3 Gradient Complexity under Smooth Assumption
Due to the importance of total computation in the machine learning and optimization community, we consider a more common setup by additionally assuming that fi is L-smooth with L 2 5 2 p > 0. which together with Assumption facilitates the quantification of Eq. (10). Then can compute the total gradient complexity for AceSVRS as shown below. By Proposition 2.5 and our assumptions, A (z: is () ( convex and () + -mmooohh Using accelerated methods starting from Et. we can guarantee that Eq. (10p holds after Tapp = Ö (v
1+9L
ò 11++=1/AVL//
/nos
iterations with the choice of 0 in Theorem 3.6 Hence, the total gradient calls in expectation are
On'Tapp K2) = Ô n 3/4 (V0/u+ VV/5) VL/8)
+ VnL/u).
Since E [j,, L.). we recover the optimal gradient complexity Ö(n + 3/4 / LL/pp) for the average smooth setting [63] Table 1] if neglecting log factors. Particularly, when = O(VUL,, we even obtain the nearly optimal gradient complexity Ö(n + //L/H) for the component smooth setting (25 26 (56). We leave the details in Appendix [E] Although the gradient complexity is not the primary focus of our work, we have demonstrated that the gradient complexity bound of AccSVRS is nearly optimal for certain values of in specific cases.
4 Lower Bound
In this section, we establish the lower bound of the communication complexity, which nearly matches the upper bound of AccSVRS.
8

---

4.1 Definition of Algorithms
In this subsection, we specify the class of algorithms to which our lower bound can apply. We first introduce the Proximal Incremental First-order Oracle (PIFO) [56] 251. which is defined as hy, (z,7) (f(()., fz)) prox), (x)] with y > O. Here the proximal operator defined as prox], (a) arg min,, (Ji(w) 27 || =ll"). In addition to the local zero-order and first-order information of fi at æ, the PIFO /f, (a: 7) also provides some global information through the proximal operator Then assume the algorithm has access to the PIFO and the definition of algorithms is presented as follows.
Definition 4.1 Consider a randomized algorithm A to solve problem ( Suppose the number of communication rounds T. the initialization stage, the master node communicates with all the others. In round t. (0 S S T - 1), the algorithm samples a node it Unif((rl), and node 1 communicates with node it. Then the algorithm samples Bernoulli random variable at with constant expectation co/n. If a, = 1, node communicates with all the others. Define the information set I++1 as the set of all the possible points can obtain after round t. The algorithm updates I++1 based on the linear-span operation and PIFO, and finally oulputs certain point in IT.
At the initialization stage, the communication cost is 2(n 1). In each communication round, the Bernoulli random variable a determines whether the master node communicates with all the others, i.e. whether calculate the full gradient. Since Ea, = co /n, the expected communication cost of each round is of the order (1). Thus the total communication cost is of the order O + 7") and we can use T to measure the communication complexity. Moreover, one can check Algorithm satisfies Definition 4.1 The formal definition and detailed analysis are deferred to Appendix F.
4.2 The Construction and Results
In this section, we construct hard instance of problem ① and then use it to establish the lower bound. Due to space limitations, we only present several key properties. The complete framework of construction is deferred to Appendix F.2
Inspired by 25 we consider the class of matrices B(m, () =
E TR M This class
of matrices is widely used to establish lower bounds for minimax optimization problems 61. 49, 59 and (m,, <) == (m, <) B (m, () the well-known tridiagonal matrix in the analysis of lower
bounds for convex optimization 47 40 15). Denote the 1-th row of B(m, () as b (m, Ç) T. We partition the row vectors of B (m, {) according to the index sets L; = {l < < m, I =
(mod (n }})} for 2 S i S n and C, 1 These sets are mutually exclusive and their union is [m]. Then we consider the following problem
c
||=||] 2 ||
n
(e1, x) Σ
for i 1,
min r(z; (,0)= n Σ m
ra(:; m. C)))==
2
bi(mm () x0|" for +
(13)
2
LEC
Here e; E Rm denotes the unit vector with the i-th element equal to 1 and others equal to 0. Then one can check r(r; m. (. = - A(m, () æ + ||>]| (e1, a). Clearly, r is c-strongly convex. We also determine the AveSS parameter follows. The proof is deferred Appendix H3
Proposition 4.2 Suppose that 0 < 5 V2, n 3 and m 2 3. Then r;'s satisfy /8n + 4-AveSS.
Define the subspaces [Fr] as Fo = {0) and Fu = span(ei, e2,ei,,,,..... . Ex for S k S m. The next lemma is fundamental our analysis. The proof deferred to Appendix E5
Lemma 4.3 Suppose the algorithm A satisfies Definition 4.1 and apply to solve problem 13 with
n > 3 and m 2 4. We have (i) In Fi. (ii) Suppose I. C Fx (1 < k < m - 3). If i, satisfies k L,, or a, = 1, then I++1 C FK43i otherwise, I41 Ft.
9If we l + no, prox7, (ar) converges the exact minimizer of ft, irrelevant to the choice of æ. 'uuchh& a way of partitioning is also inspired by (25) and similar to that in [36). However, our setting is different from theirs.

---

30"
30
21
23032
2283
Cor Cor.uiatton
0C055
00005
119.32
2389
4283
CCR5
00555
22333
Figure I: Numerical experiments on synthetic data. The corresponding coefficients are shown the title of each graph. We plot the function gap a log scale versus the number of communication steps, where one exchange of vectors counts as communication step.
Lemma guarantees that in each round, only when a specific component is sampled or the expand the information set by at most three dimensions. For problem (33). we could never obtain an approximate solution unless we expand the information set to the whole space (see Proposition F.6 in Appendix F.2), while Lemma 4.3 implies that the process of expanding is very slow. Then we can establish the following lower bound.
full gradient is calculated,
Theorem 4.4 For any n. 2 3, 8, O, algorithm A satisfying Definition 4.1 and sufficiently small e > O, there exists a rescaled version of problem 13) such that (i) Assumplion 7 Tholds; (ïi) In order to find e-suboptimal solution o such that Er(w -iin r(x) e by A. the communication complexity in expectation is Q(n 3/4 v8
This lower bound nearly matches the upper bound in Theorem 3.6 up to log factors, implying Algorithm is nearly optimal in terms of communication complexity. The detailed statement and proof are deferred to Appendices F.2 and
5
Experiments
To demonstrate the advantages of our algorithms, we conduct the same numerical experiments as those in 35 333. We focus the linear ridge regression problem with E regularization, where the average loss has the formulation: f(x) = Σ" [f((z) := t/- Σド= (z,,, - -yt.) 2 ||=||
Here Zi,j E Rd and Vi.j E R. Vi E [m]. [m] serve the feature and label respectively, and m can be viewed as data size in each local client. We consider synthetic dataset generated by adding small random noise matrix to the center matrix. ensuring small ò. To capture the differences in convergence rates between our methods and SVRP caused by different magnitudes of μu, we vary μ 10 E 1,). We compare KatyushaX, SVRP (Catalyzed SVRP is somehow hard to tune so we omit it), and Accelerated Extragradient (AccEG) using their theoretical step sizes, except that scale the interpolation parameter t in KatyushaX and AccSVRS for producing practical performance (see Appendix for detail). From Figure ! we can observe that for large μ4, SVRP outperforms existing algorithms due to its high-order dependence on However, when the problem becomes ill-conditioned with a small ,r, AcSSVRS exhibits significant improvements compared to other algorithms.
methods (SVRS and AccSVRS) against SVRG,
Conclusion
In this paper, we have introduced two new algorithms, SVRS and its directly accelerated version AccSVRS, and established improved communication complexity bounds for distributed optimization under the similarity assumption. Our rates are entirely smoothness- free and only require strong convexity of the objective, average similarity, and proximal friendliness of components. Moreover, our methods also have nearly optimal gradient complexity (leaving out the log term) when applied to smooth components in specific cases. It would be interesting to remove additional log terms to achieve both optimal communication and local gradient calls as (5), as well as investigating the complexity under other similarity assumptions (such as SS instead of AveSS) in future research.
10

---

Acknowledgments and Disclosure of Funding
Lin, Han, and Zhang have been supported by the National Key Research and Development Project of China (No. 2022YFA 1004002) and the National Natural Science Foundation of China (No. 12271011). Ye has been supported by the National Natural Science Foundation China (No.
12101491).
References
[1] Artem Agafonov, Pavel Dvurechensky, Gesualdo Scutari, Alexander Gasnikov, Dmitry Kam- zolov, Aleksandr Lukashevich, and Amir Daneshmand. An accelerated second-order method for distributed stochastic optimization. In 2021 60th IEEE Conference Decision and Control (CDC), pages 2407-2413. IEEE, 2021.
[2] Alekh Agarwal and Leon Bottou. A lower bound for the optimization of finite sums. In ICML, 2015.
[3] Masoud Ahookhosh and Yurii Nesterov. High-order methods beyond the classical complexity bounds, ii: inexact high-order proximal-point methods with segment search. arXiv preprint arXiv:2109.12303. 2021.
[4] Mohammad S Alkousa, Alexander Vladimirovich Gasnikov, Darina Mikhailovna Dvinskikh, Dmitry A Kovalev, and Fedor Sergeevich Stonyakin. Accelerated methods for saddle- suddle-point problem. Compulational Mathematics and Mathematical Physics, 60:1787-1809, 2020.
[5] Zeyuan Allen-Zhu. Katyusha: the first direct acceleration of stochastic gradient methods. The Journal of Machine Leurning Research, (8(1):8144-8244 2017.
[6] Zeyuan Allen-Zhu. Katyusha x: Practical momentum method for stochastic sum-of-nonconvex optimization. arXiv preprint arXiv:/802.03866 2018.
[7] Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimization. Advances neural information processing systems, 28, 2015.
[8] Syreen Banabilah, Moayad Aloqaily, Eitaa Alsayed, Nida Malik, and Yaser Jararweh. Federated learning review: Fundamentals, enabling technologies, and future applications. Information processing & management, 5936), 2022.
[9] Ron Bekkerman, Mikhail Bilenko, and John Langford. Scaling up machine learning: Parallel and distributed approaches. Cambridge University Press, 2011.
[10] Aleksandr Beznosikov and Alexander Gasnikov. Compression and data similarity: Combination of two techniques for communication-efficie solving of distributed variational inequalities. In International Conference on Optimization and Applications, pages 151-162. Springer, 2022.
[11] Alcksandr Beznosikov and Alexander Gasnikov. Similarity, compression and local steps: Three pillars of efficient communications for distributed variational incqualities. arXiv preprint arXiv:2302.076615 2023.
[12] Aleksandr Beznosikov, Eduard Gorbunov, and Alexander Gasnikov. Derivative-free method for composite optimization with applications to decentralized distributed optimization. IFAC- PapersOnLine, 53(2):4038 4043, 2020.
[13] Aleksandr Beznosikov, Gesualdo Scutari, Alexander Rogozin, and Alexander Gasnikov. Dis- tributed saddle-pois problems under data similarity. Advances in Neural Information Processing Systems, 34:8172-811 1788 2021.
[14] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Accelerated methods for nonconvex optimization. SIAM Journal on Optimization, 28(2):155-1172,, 2018.
[15] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points ii: first-order methods. Mathematical Programming, 185(1-2):315-355 2021.
11

---

[16] Chih-Chunp Chang and Chih-Jen Lin. Libsvm: library for support vector machines. ACM transactions on intelligent systems and technology (TIST). 2(3): 2011.
[17] Gong Chen and Mare Teboulle. Convergence analysis of proximal-like minimization algorithm using bregman functions. SIAM Journal on Optimization, 3(3):538-54) 1993.
[18] Amir Daneshmand, Gesualdo Scutari, Pavel Dvurechensky, and Alexander Gasnikov. Newton method over networks is fast up to the statistical precision. International Conference on Machine Learning, pages 2398-2409. PMLR, 2021.
[19] Aaron Defazio. simple practical accelerated method for finite sums. Advances neural information processing systems, 29, 2016.
[20] Radu Alexandru Dragomir, Mathieu Even, and Hadrien Hendrikx. Fast stochastic bregman gradient methods: Sharp analysis and variance reduction. In International Conference on Machine Learning, pages 2815-2825. PMLR, 2021.
[21] Darina Mikhailovna Dvinskikh, Sergey Sergeevich Omelchenko, Alexander Vladimirovich Gasnikov, and AI Tyurin. Accelerated gradient sliding for minimizing a sum of functions. In Doklady Mathematics, volume 101, pages 244-246. Springer, 2020.
[22] Alexandre d' Aspremont, Damien Scicur, Adrien Taylor, et al. Acceleration methods. Founda- tions and Trends@ in Optimization, 5(1-2):1-245, 2021.
[23] Dan Garber, Elad Hazan, Chi Jin, Cameron Musco, Pranecth Netrapalli, Aaron Sidford, et al. Faster cigenvector computation via shift-and-invert preconditioning. In International Conference on Machine Learning, pages 2626-2634. PMLR, 2016.
[24] Geovani Nunes Grapiglia and Yurii Nesterov. Adaptive third-order methods for composite convex optimization. arXiv preprint arXiv:2202. 12730, 2022.
[25] Yuze Han, Guangzeng Xie, and Zhihua Zhang. Lower complexity bounds of finite-sum optimization problems: The results and construction. arXiv preprint arXiv:2103.082880 2021.
[26] Robert Hannah, Yanli Liu, Daniel O' Connor, and Wotao Yin. Breaking the span assumption yields fast finite-sum minimization. Advances in Neural Information Processing Systems, 31, 2018.
[27] Hadrien Hendrikx, Lin Xiao, Sebastien Bubeck, Francis Bach, and Laurent Massoulie. Statisti- cally preconditioned accelerated gradient method for distributed optimization. In International conference on machine learning, pages 4203-4227. PMLR, 2020.
[28] Anastasiya Ivanova, Pavel Dvurechensky, Evgeniya Vorontsova, Dmitry Pasechnyuk, Alexander Gasnikov, Darina Dvinskikh, and Alexander Tyurin. Oracle complexity separation in convex optimization. Journal of Optimization Theory and Applications, 193(1-3):4624499 2022.
[29] Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26, 2013.
[30] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning, Foundations and Trends in Machine Learning. 14(1 (1(11)))1110 22:1-211:1. 2021.
[31] Dmitry Kamzolov, Alexander Gasnikov, and Pavel Dvurechensky. Optimal combination of tensor optimization methods. In Optimization and Applications: 11th International Conference, OPTIMA 2020, Moscow, Russia, September 28-October 2, 2020, Proceedings I1, pages 166- 183. Springer, 2020.
[32] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference Machine Learning, pages 5132-5143, PMLR, 2020.
12

---

[33] Ahmed Khaled and Chi Jin. Faster federated optimization under second-order similarity. In The Eleventh International Conference on Learning Representations, 2023. URL https
7 //openreview. 1ett/forum2ddd211GG00AA
[34] Dmitry Kovalev, Samuel Horváth, and Peter Richtárik, Don't jump
jump through hoops and remove those loops: Svrg and katyusha are better without the outer loop. In Algorithmic Learning Theory, pages 451 167. PMLR, 2020.
[35] Dmitry Kovalev, Alcksandr Beznosikov, Ekaterina Dmiirievna Borodich, Alexander Gasnikov, and Gesualdo Scutari. Optimal gradient sliding and its application to optimal distributed optimization under similarity. In Advances in Neural Information Processing Systems, 2022.
[36] Dmitry Kovalev, Alcksandr Beznosikov, Abdurakhmon Sadiev, Michael Persiaanv, Peter Richtárik, and Alexander Gasnikov. Optimal algorithms for decentralized stochastic variational inequalities. Advances in Neural Information Processing Systems, 35:31073-31068 2022.
[37] Guanghui Lan. Gradient sliding for composite optimization. Mathematical Programming, 159: 201-235, 2016.
[38] Guanghui Lan and Yuyuan Ouyang. Accelerated gradient sliding for structured convex opti- mization. Computational Optimization and Applications, 82(2):361-394, 2022.
[39] Guanghui Lan and Yi Zhou. Conditional gradient sliding for convex optimization. SIAM Journal on Optimization, 26(2):1379-1409, 2016.
[40] Guanghui Lan and Yi Zhou. An optimal randomized incremental gradient method. Mathematical programming, 171:167-21 -115, 2018.
[41] Kfir Levy. Sloweal-sgd: Slow query points improve local-sgd for stochastic convex optimiza- tion. arXiv preprint 2:XX:::2300.041699 2023.
[42] Bingcong Li, Meng Ma, and Georgios B Giannakis. On the convergence of sarah and beyond. In International Conference Artificial Intelligence and Statistics, pages 223-233. PMLR, 2020.
[43] Zhize Li. Anita: An optimal loopless accelerated variance-reduced gradient method. arXiv preprint arXiv:2103. 11000,11133,..0 2021.
[44] Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. Advances in neural information processing systems, 30, 2017.
[45] Ming Liu, Stella Ho, Mengqi Wang, Longxiang Gao, Yuan Jin, and He Zhang. Federated learning meets natural language processing: A survey. arXiv preprint arXiv:2107.12603, 2021.
[46] Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárik. Proxskip: Yes! local gradient steps provably lead to communication acceleration! finally! In International Conference on Machine Learning, pages 15750-15769. PMLR, 2022.
[47] Yurii Nesterov et al. Lectures on convex optimization, volume 137. Springer, 2018
[48] Dinh C Nguyen, Quoc-Viet Pham, Pubudu N Pathirana, Ming Ding, Aruna Seneviratne, Zihuai Lin. Octavia Dobre, and Won-Joo Hwang. Federated learning for smart healthcare: survey. ACM Computing Surveys (CSUR), 55(3):1-37, 2022.
[49] Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. Mathematical Programming, 2021.
[50] Sashank J Reddi, Jakub Konečný, Peter Richtárik, Barnabás Póczós, and Alex Smola. Aide: Fast and communication efficient distributed optimization. arXiv preprint arXiv: 1608.06879 2016.
13

---

[51] Ohad Shamir, Nati Srebro, and Tong Zhang. Communication- efficcient distributed optimization using an approximate newton-type method. In International conference on machine learning. pages 1000-1008. PMLR, 2014.
[52] Danny C Sorensen. Numerical methods for large eigenvalue problems. Acta Numerica, 11: 519-584, 2002.
[53] Ivan Stepanov, Artyom Voronov, Aleksandr Beznosikov, and Alexander Gasnikov. One-point gradient-free methods for composite optimization with applications distributed optimization. arXiv preprini urXiv:2107.05951 2021.
[54] Ying Sun, Gesualdo Scutari, and Amir Daneshmand. Distributed optimization based on gradient tracking revisited: Enhancing convergence rate via surrogation. SIAM Journal on Optimization, 32(2):354-382 385, 2022.
[55] Ye Tian, Gesualdo Scutari, Tianyu Cao, and Alexander Gasnikov. Acceleration in distributed op- timization under similarity. In International Conference on Artificial Intelligence and Statistics, pages 5721-5756. PMLR, 2022.
[56] Blake E Woodworth and Nati Srebro. Tight complexity bounds for optimizing composite objectives. Advances in neural information processing systems, 29, 2016.
[57] Lin Xiao and Tong Zhang. A proximal stochastic gradient method with progressive variance reduction. SIAM Journal on Optimization, 24(4):2057-2075, 2014.
[58] Xiao-Tong Yuan and Ping Li. On convergence of distributed approximate newton methods: Globalization, sharper bounds and beyond. The Journal of Machine Learning Research, 21(1): 8502 8552, 2020.
[59] Junyu Zhang, Mingyi Hong, and Shuzhong Zhang. On lower iteration complexity bounds for the convex concave saddle point problems. Mathematical Programming, 194(1-2):0119935 2022.
[60] Sai Qian Zhang, Jieyu Lin, and Qi Zhang. A multi-agent reinforcement learning approach for efficient client selection in federated learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pages 9091-9099, 2022.
[61] Siqi Zhang, Junchi Yang, Cristóbal Guzmán, Negar Kiyavash, and Niao He. The complexity of nonconvex-stronglyycoomm connavve minimax optimization. In Uncertainty in Artificial Intelligence, pages 482-492. PMLR, 2021.
[62] Yuchen Zhang and Xiao Lin. Disco: Distributed optimization for self-concordant empirical loss. In International conference on machine learning, pages 362-370. PMLR, 2015.
[63] Dongruo Zhou and Quanquan Gu. Lower bounds for smooth nonconvex finite-sum optimization.
In International Conference on Machine Learning, pages 7574-7583 PMLR, 2019.
14


Reviews:
[{"review_id": "hCBa6snTD2", "reviewer": "Reviewer_pJR8", "summary": "This work considers finite-sum (distributed) optimization problems in the strongly convex and second-order similar regime. The authors proposed SVRS and its acceleration, AccSVRS, to solve the problem and provided the corresponding communication and computation complexities, which outperform existing works in several perspectives. The authors further characterized the lower bound for solving such problems, which validates the near optimality of the proposed AccSVRS algorithm.", "questions": "1. Line 232, you mentioned you recovered the optimal complexity of the average smooth setting. While with the additional AveSS setting, I may expect the complexity possibly can be (strictly) better than the classical $L$-smooth $\\mu$-strongly convex case (assuming all components are $L$-smooth here for convenience). \n\n   In your proof of Appendix E, you mentioned the obtained complexity is only smaller than that of the average smooth setting (Line 590), but should it be equivalence (rather than smaller only) here to be verified? \n  \n2. With the current result in Section 3.3, can we argue that possibly second-order similarity does not help in the gradient complexity of the classical case?\n\n3. Line 591 in Appendix E (or Line 234), why do you drop the $O(n^{3/4}(L/\\mu)^{1/4})$ term? Compared to the last $O(\\sqrt{nL/\\mu})$ term, is there a possibility that the $n^{3/4}$ term will dominate? Do I miss anything here?", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The study is comprehensive in general, covering both upper and lower bounds\n2. Proposed algorithm achieves near-optimal communication/computation complexity. \n3. The design of the algorithm, which incorporates PPA, VR, gradient sliding and Katyusha, is interesting.\n4. The paper is well-written, and the flow is clear.", "weaknesses": "1. The design of the AccSVRS, as the core algorithm achieving near optimality, can be further elaborated. For now, I do not have a clear understanding on Steps 5 and 6 in AccSVRS. Some discussions similar to Section 3.1 connecting Katyusha X paper will be appreciated.\n2. Some more questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and suggestions. Here we list the reply point by point.\n\n1. Reply to Weakness 1: We are sorry for the unclearness due to the space limit of pages. We need to recognize that Steps 5 and 6 in AccSVRS are somehow tricky, so we only list some shallow understanding here.  \n**The difference between AccSVRS and KatyushaX is due to the different choice of distance space.** \nRecapping the connection with Bregman-SVRG in Section 3.1, we adopt the reference function $f_1(\\cdot)+\\frac{1}{2\\theta}||\\cdot||^2$ to control $f(\\cdot)$ instead of $\\frac{1}{2\\theta}||\\cdot||^2$ in the original SVRG, leading to the distance space in our proof is produced by the Bregman divergence of $h(\\cdot)=f_1(\\cdot)+\\frac{1}{2\\theta}||\\cdot||^2-f(\\cdot)$ shown in Lemma 3.1 and thereafter.\nNow we turn back to AccSVRS, which is motivated by the general framework of KatyushaX (see (4.1) in its arxiv version: https://arxiv.org/pdf/1802.03866.pdf). Thus you can see that AccSVRS (Alg. 2) shares the same structure as KatyushaX. \nThe main difference is that in our setup, the gradient mapping step for computing $\\mathcal G_{k+1}$ is not based on the original standard norm $\\frac{1}{2\\theta}||\\cdot||^2$, but the space produced by Bregman divergence $D_h(\\cdot, \\cdot)$. \nHence, the gradient mapping should be $\\nabla h(x_{k+1}) - \\nabla h(y_{k+1})$ instead of $\\frac{x_{k+1} -  y_{k+1}}{\\theta}$. \nNext, noting that $\\nabla h(x) = \\nabla f_1(x) - \\nabla f(x) + \\frac{x}{\\theta}$ could introduce the heavy gradient computing part $\\nabla f(x)$, so we further adopt its stochastic version $\\nabla f_1(x) - \\nabla f_{j_k}(x) + \\frac{x}{\\theta}$ by uniformly sampling $j_k \\sim \\mathrm {Unif} ([n])$ to reduce the communication complexity. \n(P.S. Indeed, using $\\nabla h(x)$ directly for computing $\\mathcal G_{k+1}$ in AccSVRS is fine since the communication complexity of $\\mathrm {SVRS^{1ep}}$ is $\\Theta(n)$ when $p=1/n$. Here we employ a stochastic version to further reduce the communication complexity.) \nIf the reviewer considers such an explanation helpful, we will add it to the later version. \n2. Reply to Questions 1& 2: We consider there are some misleading in our description. **Our setting is unable to be compared with the classical smooth and strongly convex setting generally.**   \nFirst, we reclarify the entire assumption of our problem: 1) the finite-sum objective is strongly convex, 2) the finite-sum objective satisfies average second-order similarity, and 3) the proximal operator of just one part (or each part) is approximately solvable, meaning that we can get an approximate solution of the proximal step (like Eq. (9) in our paper). And our main results are related to the communication complexity.  \nAs you can see, the computation complexity (i.e., gradient complexity) is not available in our main theorems since we do not know the gradient complexity of getting an approximate solution of the proximal operator without further assumptions. \n(P.S. Note that our lower bound is also in this framework, but we enhance 3) from approximately solvable to analytically solvable. This is fine since we consider the lower bound there.)    \nDue to the importance of total computation in the machine learning and optimization community, we turn to consider a more common setup by assuming 4) each part (or just one part) of the finite-sum objective is smooth, which appears in many previous works (e.g., the references [29, 31] in our paper).  \nThe computation complexity in Sec 3.3 is a by-product of our results with a smaller function class due to the additional smoothness assumption 4). Meanwhile, compared to the classical smooth and strongly convex case, we further need to assume 2). Thus, we may wonder if the computation complexity in this stricter setting is *at least as good as* the optimal complexity excluding 2), since such a setting is well-studied.  \nThe discussion in Sec 3.3 only confirms that our algorithm could recover the optimal computation complexity of the classical (average-)smooth and strongly convex case *under some relationship between smoothness and similarity constant*. \nWe do not know the optimal gradient complexity under 1), 2), and 4) up to now, but we are willing to see the relative work or try such a setting in the future. \nWe agree with the reviewer's conjecture that the computation complexity may be better after assuming 2), but it is not able to conclude that second-order similarity does not help in the gradient complexity based on our paper.\n3. Reply to Question 3: Thank you for your careful review even on the Appendix. Noting that $n+\\sqrt{n L/\\mu} \\geq 2\\sqrt{n \\cdot \\sqrt{n L/\\mu}} = 2 n^{3/4}(L/\\mu)^{1/4}$, we could drop the term $n^{3/4}(L/\\mu)^{1/4}$ compared to the remaining term $n+\\sqrt{n L/\\mu}$ in the final complexity after hidding some constants.\n"}, {"review_id": "8wAyjl7vj5", "reviewer": "Reviewer_LQ8y", "summary": "The paper considers distributed strongly convex optimization problems in the setting where the communication between nodes is bottleneck. The authors propose new methods, SVRS and AccSVRS, that guarantee new communication complexities. Also, they proved the lower bound that ensures the optimality of the AccSVRS method.", "questions": "-", "limitations": "-", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "I think that the paper is strong. The authors provide new theoretical guarantees in the considered setting. They improve the previous methods. I haven't checked the proofs in detail and I can miss some essential parts, but the theory sounds to me. ", "weaknesses": "It is well known that the (Loopless-)Katyusha method converges after $n + \\sqrt{n \\frac{L}{\\mu}}$ iterations. By applying Katyusha to the authors' problem, we can get the communication complexity $n + \\sqrt{n \\frac{L}{\\mu}},$ since Katyusha requires only one gradient in each iteration. In the regime when $\\delta = L$ the Katyusha method has better communication complexity than $n + n^{3/4} \\sqrt{\\frac{L}{\\mu}}.$ Why doesn't it contradict the lower bound (Theorem G.7 and Theorem 4.4)? Does it mean that your method is only better in the regimes when $\\delta \\ll L$?\n\nMinor comments:\n\nThe paper's setup can be slightly confusing. Many other papers (e.g., \\[1,2\\]) assume that the nodes can do calculations and send vectors *in parallel,* meaning that they count each round as *one* communication, *one round = one communication*. In comparison, this paper assumes that *one round = $n$ communications* in the full participation regime. Can the authors write a small text *in the paper* explaining the difference between the setups? It seems that we have at least two different setups that both have the right to life.\n\nTypos:\n\nEq. (18): $\\nabla$ is missed.\n\n\\[1\\]: https://arxiv.org/abs/2202.09357\n\\[2\\]: https://arxiv.org/abs/2304.04169", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We consider there are some misleading due to the unclearness in our paper.  \n**Our setting is unable to be compared with the classical smooth and strongly convex setting generally.** \nFirst of all, we reclarify the framework we studied: 1) the finite-sum objective is $\\mu$-strongly convex, 2) the finite-sum objective satisfies $\\delta$-average second-order similarity, and 3) the proximal operator of just one part (or each part) is approximately solvable (e.g., Eq. (9) in our paper). \nUnder assumptions 1), 2), and 3), we improve the communication complexity compared to the previous work. \nThus, *the gradient complexity is not the main contribution.*  \nIndeed, the computation complexity (i.e., gradient complexity) is *not available* in our main theorems since we do not know the gradient complexity of getting an approximate solution of the proximal operator without further assumptions.   \n**Our lower bound is also in the framework under 1), 2) and 3)**, but we enhance 3) from approximately solvable into entirely solvable, i.e., we can obtain the solution of the proximal operator of each part function. This is fine since we consider the lower bound there.\nIn summary, the main results in our paper are built on 1), 2), and 3), and are only related to the communication complexity.   \nMoreover, since the gradient complexity is also important in the machine learning and optimization community, we turn to consider a more common setup by additionally assuming 4) each part (or just one part) of the finite-sum objective is $L$-smooth in Sec 3.3, which appears in many previous works (e.g., the references [29, 31] in our paper). \n\nNow we turn to answer the reviewer's questions. \n1. Katyusha admits optimal gradient complexity under the assumption 1) and 4), which differs from our setup. So the direct comparison is unsuitable. However, if we study the setup under 1), 2), and 4), both algorithms could apply since 2) and 4) could guarantee 3) in our setup. \nAt this time, we need to recognize that *our current method (AccSVRS) is not optimal in the gradient complexity generally*, meaning that our method could be worse than Katyusha, but when the coefficient $\\delta$ in assumption 2) lies in the proper range: $\\delta = \\Theta(\\sqrt{\\mu L})$, our AccSVRS could nearly recover the optimal gradient complexity under assumptions 1) and 4) and is comparable to Katyusha.\nFinally, as we reply to the first reviewer, the discussion in Sec 3.3 only confirms that our algorithm could recover the optimal computation complexity of the classical (average-)smooth and strongly convex case *under some relationship between smoothness and similarity constants*. The discussion in Section 3.3 is to show the minor benefit of gradient complexity under 4) in some restricted cases, instead of affirming that our method is optimal in gradient complexity, since under Assumptions 1), 2), 3), gradient complexity is even not available.\n2. Now we explain why the communication complexity of (Loopless-)Katyusha does not contradict our lower bounds. It is worth emphasizing that (Loopless-)Katyusha requires that each component is $L'$-smooth (we adopt a different symbol here to avoid ambiguity). Then the gradient complexity and the communication complexity of Katyusha are indeed the same, i.e., $n + \\sqrt{n \\frac{L'}{\\mu} }$. Meanwhile, one can check that the hard instance constructed for our lower bound only satisfies that each component is $c \\sqrt{n} \\delta$-smooth for some constant $c>0$ (if necessary, we will add the detailed computation in the later version).  If $\\delta = L$, applying Katyusha to our hard instance in fact yields the $n + n^{3/4} \\sqrt{\\frac{L}{\\mu}}$ communication complexity instead of $n + \\sqrt{ n \\frac{L}{\\mu} }$. This implies that for the special case with $L'  = \\Theta( \\sqrt{n} \\delta )$, Katyusha attains the optimal communication complexity. As a comparison, the optimality of our method in terms of communication complexity does not require the smoothness of component functions or the relationship between the smoothness and similarity constants.\n3. We thank the reviewer for pointing out the two setups in distributed optimization. We consider both setups important.\nWe only list the case of our setting. For example, in a business network or communications network, the communication between any two nodes could produce the charge and the risk, which indeed could not be viewed as one communication in parallel at all. \nMoreover, the entire parallel is not available since the environment behind each node is roughly different and complex. \nHowever, if the environment is similar, the parallel is possible and could save the total time. We will add some explanation in a later version.\n"}, {"review_id": "ASlgL37vHA", "reviewer": "Reviewer_FHTz", "summary": "The paper presents a novel algorithm for distributed optimization, named Accelerated Stochastic Variance-Reduced Sliding (ASVRS). The authors focus on the problem of minimizing the average of a large number of smooth and strongly convex functions, a common scenario in machine learning and data analysis. The proposed ASVRS algorithm combines the techniques of gradient-sliding and variance reduction, aiming to improve the convergence rate and reduce the communication cost in distributed settings.", "questions": "How sensitive is the ASVRS algorithm to its parameters? Could you provide some guidance on how to set the parameters in practice.", "limitations": "The limitation has been adequately addressed. ", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The ASVRS algorithm is a novel contribution that combines gradient-sliding and variance reduction techniques in a unique way. This combination appears to be original and innovative. The authors provide detailed proofs for the convergence rate and communication complexity of the ASVRS algorithm, demonstrating its theoretical advantages over existing methods. I didn't check the details but the result seems reasonable. \n", "weaknesses": "The theoretical analysis relies on several assumptions, such as the strong convexity of the functions. This makes the application of the work rather limited.  It would be helpful to discuss the implications of these assumptions and how the algorithm's performance might be affected if they are not met.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and advice. \n\nThe assumptions in our paper include 1) the finite-sum objective is strongly convex, 2) the finite-sum objective satisfies average second-order similarity, and 3) the proximal operator of just one part (or each part) is approximately solvable.\nThese assumptions also appear in previous work (e.g., references [29, 31] in our paper). \nAssumption 1) is a common assumption in convex optimization, which could be satisfied after adding regularization for the common convex loss function. Assumption 2) is the core assumption in our setup, which appears in a large body of work, and has the practical scene from statistical learning, as well as the intuition of similar data in each client. Assumption 3) is related to the proximal operator, which also has much literature, particularly on nonsmooth optimization.\nAssumption 1) guarantees the benign property of the finite-sum objective, which serves as the whole property; \nAssumption 2) shows the connection between each component in the objective, which serves as the property between parts;\nFinally, Assumption 3) shows the requirement of one component (or each component), which serves as the part property.\n\nThe hyper-parameters in ASVRS include interpolation coefficients $\\tau, \\alpha$, learning rate $\\theta$, and full gradient step probability $p$. ASVRS is an accelerated method. \nHence, ASVRS may display the oscillation when the learning rate is large and the interpolation coefficients are improper. Our theorems already give a proper combination of these parameters. \nHowever, in practice, the parameter in theory may not be optimal. Here we list one common tuning method based on our experience in experiments. We can choose $p=1/n$ and fix the relationship between interpolation coefficients $\\tau$ and $\\alpha$ as in Theorem 3.5, and then fine-tune the learning rate $\\theta$ and only one interpolation coefficient $\\tau \\in (0, 1)$. In detail, we may scale $\\theta$ and $\\tau$ based on its theoretical value."}, {"review_id": "ZnCBX9rvsZ", "reviewer": "Reviewer_ZtXX", "summary": "The authors consider distributed minimization problems under data similarity (hessian similarity). The authors consider stochastic methods that reduce communication complexity via device sampling. In particular, from the stochastic point of view, the variance reduction techniques: SVRG and Katyusha, are taken. The sliding (stochastic preconditioning/mirror descent with unusual Bregman divergence) technique is used for dealing with similarity. The authors obtain record results in communication complexity (the previous ones were beaten by the logarithmic factor). To complete the picture, the authors provide lower bounds that give the optimality of their upper bounds. Synthetic experiments are also given. ", "questions": "-", "limitations": "The paper is theoretical, therefore there is no need to discuss the social negative impact.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1) Direct acceleration (without envelops) is an interesting and important result. In theory it removes the extra logarithmic factor, and in practice it works better. \n\n2) The lower bounds complete the picture. \n\n", "weaknesses": "1) I think the literature review is not complete. In particular I find two papers also about the hessian similarity, which also use the variance reduction technique and obtain such non-accelerated results as the authors have. A detailed comparison in approaches and results is needed. \n\nBeznosikov, A., & Gasnikov, A. (2023). Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalities. arXiv preprint arXiv:2302.07615.\n\nBeznosikov, A., & Gasnikov, A. (2022, September). Compression and data similarity: Combination of two techniques for communication-efficient solving of distributed variational inequalities. In International Conference on Optimization and Applications (pp. 151-162). Cham: Springer Nature Switzerland.\n\n2) The lower bounds are a good supplement to the upper bounds, but they are to be expected. The idea of getting them is also known. Unfortunately, here the authors  don not  also give a complete summary of the literature: the problem with a matrix A is classical (the authors note it), but the partition of the problem into columns is also classical - see the papers:\n\nZhang, M., Shu, Y., & He, K. (2020). Tight Lower Complexity Bounds for Strongly Convex Finite-Sum Optimization. arXiv preprint arXiv:2010.08766.\n\nHan, Y., Xie, G., & Zhang, Z. (2021). Lower complexity bounds of finite-sum optimization problems: The results and construction. arXiv preprint arXiv:2103.08280.\n\nKovalev, D., Beznosikov, A., Sadiev, A., Persiianov, M., Richtárik, P., & Gasnikov, A. (2022). Optimal algorithms for decentralized stochastic variational inequalities. Advances in Neural Information Processing Systems, 35, 31073-31088.\n\n3) Experiments for me are not the most important thing in this paper, which is primarily theoretical. But I would still like to see real datasets (3 for symmetry with synthetic data). I would also advise authors to change not \\mu, but to change \\delta in synthetic experiments, this way the effect of similarity will be noticeable. \n\nSummary: For me, this is a borderline paper. For now I put a (weak) rejection, but I hope the authors will take part in discussion and make the changes I asked for. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and for pointing out these interesting and meaningful references. We are sorry for the incompleteness of the reference. \nWe will add the reference you posted in a later version because revision is not allowed in the rebuttal period this year.\nIn addition, we find there are still some differences compared to these works.\n1. Reply to Weakness 1: Despite the similar assumptions and techniques with similar communication bounds, we find that our paper still has some differences compared to Beznosikov, A., & Gasnikov, A. (2022, 2023):\n- We do not assume the smoothness and convexity of the component or the objective but replace it with a more general proximal approximately solvable assumption (see Eq. (9) in our main paper), which could even cover some nonsmooth and non-convex but proximal trackable component functions. \nWe consider such an assumption more essential since the local update step in the paper of Beznosikov, A., & Gasnikov, A. (2022, 2023) can be viewed as partially solving the proximal step.\n- Our algorithm (Alg. 1) is more concise with easy-choosing parameters. Particularly, the choice of hyper-parameters, such as learning rate, is totally smoothness-free. This can also be viewed as the benefit of our proximal solvable assumption.\n- More importantly, except for the diversity in the non-accelerated method, we also give a simple directly accelerated method with a better communication complexity bound.  \nHowever, Beznosikov, A., & Gasnikov, A. (2022, 2023) provide really meaningful work by considering a more general setting for solving variational inequalities, which could cover our simple minimization setup and many common problems. \nMoreover, they also adopt the famous compression technique to further reduce communication complexity. \nDue to these challenges, the algorithms introduced by Beznosikov, A., & Gasnikov, A. (2022, 2023) are more complex their ours.\n\n2. Reply to Weakness 2: Our way of partitioning the matrix $A$ is inspired by Han, Y., et al. (2021) (as we claimed in Section 4) and indeed closely related to Kovalev, D., et al. (2022), but different from Zhang, M., et al. (2020), where the authors duplicate the matrix $n$ times instead of partitioning it. Moreover, our settings are different from these papers. Zhang, M., et al. (2020) and Han, Y., et al. (2021) both focus on the gradient complexity, while our concern is the communication complexity. Kovalev, D., et al. (2022) study the communication complexity (as well as the gradient complexity) for smooth variational inequalities, while we aim to give a more refined analysis of communication complexity for minimization problems even without the smoothness assumption, though we find that constructing a smooth hard instance suffices to yield the desired lower bound. Despite the similarity in construction, our results and theirs are not directly comparable.\n\n3. Reply to Weakness 3: Since the communication bound in all literature is related to $\\delta/\\mu$, so we only need to change one parameter and fix another to see the effect. Meanwhile, adjusting the strong-convex coefficient $\\mu$ is rather easy, but the similarity coefficient would change the dataset entirely. \nHence, we adopt an easy-tuning way to conduct experiments for horizontal comparison of the different condition numbers with the same prefixed dataset.\n"}, {"review_id": "unaF57y5iA", "reviewer": "Reviewer_Y65R", "summary": "**Summary** \n\nThe paper studies finite-sum minimization ($\\min_{x} f(x):= \\frac{1}{n} \\sum_{i= 1}^n f_i(x)$) in the distributed setting with a central node and $n-1$ non-central (client) nodes. The setup and the paper's assumptions are as follows. \n\n1. Each function $f_i$ is held in the $i$-th client node, and the first node is designated the central node. The machines on the non-central nodes can communicate function values and gradients with each other as well as with the central node. \n\n2. The different $f_i$'s are assumed to be related to each other via the notion of \"second-order similarity\", which essentially means that the Hessians of $f_i$ and $f$ evaluated at the same point do not differ from each other by too much in the operator norm. A benefit of this assumption is that different clients do not need to all send their Hessian information. \n\n3. The $f_i$'s are all convex, $f$ is $\\mu$-strongly convex, and the $f_i$'s all satisfy $\\delta$-average-second-order-similarity as described in 2. \n\nThe paper's results are three-fold: \n\n1. A non-accelerated algorithm called SVRS, which attains a communication cost of $\\widetilde{O}(n + \\sqrt{n} \\delta/\\mu)$. This result improves upon the previous best result of Khaled and Jin when $\\delta \\geq \\sqrt{n} \\mu$. \n\n2. An accelerated algorithm called AccSVRS, which attains a communication cost of $O((n+ n^{3/4} \\sqrt{\\delta/\\mu})\\log|\\epsilon|)$, which improves upon the previous best accelerated rate by Khaled and Jin by a factor of $\\log(L/\\mu)$. Therefore, this new rate is \"smoothness-free\". \n\n3. Lower bounds for 2. \n\nThe paper's technique is based, broadly, on the use of Bregman-SVRG: instead of calculating exactly in each iteration, we calculate the approximate entities every time and periodically offset the error by exact calculations; additionally, through the use of a Bregman divergence term, the update rule ensures that the next iterate is not too far from the current one in some chosen distance metric. \n\n", "questions": "**Questions** \n\n\n1. In Algorithm 1, should line 4 be $g_t = \\nabla f_{i_t} (w_t) - \\nabla f(w_t)$ and should there be an update rule for $w_t$ somewhere? (That's what Line 176 seems to suggest.) If not, it would be great to have intuition for why the same $w_0$ is used through the entire algorithm. \n\n2. Please see the Weaknesses section above for more questions. \n", "limitations": "N/A ", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "\n**Strengths** \nI think the paper scores highly on the story-telling aspect: it reads quite well! I also think the paper studies an important problem (faster communication complexity for distributed optimization). \n", "weaknesses": "\n\nIn results: \n\n1. Line 64: The paper's result from SVRS beats that of SVRP by Khaled and Jin when $\\delta \\geq \\sqrt{n} \\mu$. As of now it's not clear to me what the scope of this assumption is: are there many cases where this inequality holds? It appears to me that Lines 124 and 198 allude to this but it's not entirely clear to me. Can the authors please elaborate?  \n\n2. Line 68 - 70: The paper's result with acceleration shaves a log factor from the previous best result as well as removes a component-wise strong convexity assumption from the previous best result. It would be nice to see some intuition for why the removal of log factor here is important and why the component-wise strong convexity is that much stronger than total strong convexity. \n\n\nIn the writing: \n\n1. In lines 14 - 17, there are no references for these stated applications. It would be much more convincing to have citations for each of the stated applications. \n\n2. The problem parameter $\\mu$ should be introduced separately, rather than as part of the related work in lines 40 - 48, since it's an important parameter that comes up repeatedly. \n\n3. The inclusion of Lemma $3.1$ in the main body does not serve (in my opinion) much purpose because it's mathematically quite dense to parse Equation $(10)$. Theorem $3.2$ is ok since it clearly gives the claimed rate. Instead of Lemma $3.1$, I'd have preferred to have a proof sketch for Theorem $3.2$. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your advice. We reply to your comments one by one below.\n\n1. Reply to Weaknesses in Results 1: We are sorry for the confusing argument. Indeed, SVRS is always no worse than SVRP by Khaled and Jin since\n$O(n+\\delta^2/\\mu^2)=O(n)$ and $O(n+\\sqrt{n}\\delta/\\mu) = O(n)$ when $\\delta<\\sqrt{n}\\mu$. \nWe emphasize the case of $\\delta \\geq \\sqrt{n}\\mu$ to show the benefit of our method in the ill-conditioning case that $\\mu$ is very small. \n2. Reply to Weaknesses in Results 2: Thank you for your suggestions. Not only do we remove the log factor, but also we give a directly accelerated method. \nAs mentioned in the paper of KatyushaX (see reference [6, Section 1.2] in our paper), the Catalyst SVRP needs to run each SVRP until a very accurate point is obtained since the error propagates. \nMoreover, to optimize the complexity, one needs to terminate each call of SVRP at a different accuracy, while this may be difficult for a random algorithm. Finally, one needs to tune three parameters in a Catalyzed method. \nThus, we wonder whether a directly accelerated method exists. The contribution should not only be limited to removing the log factor (though it is also important from the poor theoretical view) but also the directly accelerated method.  \nAs for the improvements from the component-wise strong convexity to the total strong convexity, much literature has mentioned the reason. Overall, when we remove the component-wise strong convexity, then each component in the finite-sum objective could even be non-convex! This greatly expands the suitable scene. The most famous example is the shift-and-invert approach to solving PCA [1,2] (or see Sec 1.1 Motivating Examples in the paper of KatyushaX), where each component is smooth and non-convex, but the average function is convex. Thus, we consider our improvement meaningful.\n3. Reply to Weaknesses in writing: Thank you for the advice, we will add references and adjust the structure in the later version.\n4. Reply to Question 1: this is not a typo. Note that the Algorithm is one epoch (1ep in short) version of our SVRS. Thus, in the one epoch of SVRS, the anchor point is fixed just like SVRG. Line 176 shows the multi-epoch SVRS, where we update the anchor point $w_t$ based on 1ep SVRS.\n\n\n[1] Youcef Saad. Numerical methods for large eigenvalue problems. Manchester University Press, 1992.\n\n[2] Garber, Dan, et al. Faster eigenvector computation via shift-and-invert preconditioning. International Conference on Machine Learning. PMLR, 2016."}]

Author rebuttal:

Meta-review: The paper presents and analyzes the SVRS and AccSVRS methods in the distributed finite-sum setting, under a second-order similarity condition. The techniques, based on gradient sliding and variance reduction, lead to rates which improve upon previous results, and these improvements are complemented by nearly matching lower bounds. While the use of variance reduction for these types of settings may not be entirely new, the results provide a meaningful contribution in terms of better communication complexity, and so acceptance is recommended.
Decision: Accept (poster)