Towards Optimal Communication Complexity in Distributed Non-Convex Optimization
Authors: Kumar Kshitij Patel
Lingxiao Wang
Blake Woodworth
Brian Bullins
Nathan Srebro
Venue: NeurIPS 2022 Accept (2022)
Keywords: Distributed Optimization
Intermittent Communication Setting
Federated Learning
Non-convex Optimization
Lower Bounds
Stochastic Optimization

Abstract: We study the problem of distributed stochastic non-convex optimization with intermittent communication. We consider the full participation setting where $M$ machines work in parallel over $R$ communication rounds and the partial participation setting where $M$ machines are sampled independently every round from some meta-distribution over machines. We propose and analyze a new algorithm that improves existing methods by requiring fewer and lighter variance reduction operations. We also present lower bounds, showing our algorithm is either $\textit{optimal}$ or $\textit{almost optimal}$ in most settings. Numerical experiments demonstrate the superior performance of our algorithm.

Towards Optimal Communication Complexity in Distributed Non-Convex Optimization
Kumar Kshitij Patel" TTIC kxpatel@ttic.edu
Lingxiao Wang" TTIC Lingxw@ttic.edu
Blake Woodworth SIERRA, INRIA
blakesoottorri@@aal..commm com
Brian Bullins
Nati Srebro TTIC nati@ttic.edu
Purdue University
bbullins@purdue.cmmm edu
Abstract
We study the problem of distributed stochastic non-convex optimization with in- termittent communication. We consider the full participation setting where M machines work in parallel over R communication rounds and the partial participa- tion setting where M machines are sampled independently every round from some meta meta-distribution over machines. We propose and analyze new algorithm that improves existing methods by requiring fewer and lighter variance reduction opera- tions. We also present lower bounds, showing our algorithm is either optimal or almost optimal in most settings. Numerical experiments demonstrate the superior performance of our algorithm.
Introduction
We consider the following distributed optimization problem with M machines:
M
min F(x) ZER"
= M
Σ Fm(z),
(1.1)
m=1
where Fn, which denotes the objective on machine m, is a non-convex function for all m, as is the average objective F. We want solve this problem in the intermittent communication (IC) setting [1, 2] where the machines work in parallel and are allowed to make K oracle calls between two communication rounds for R. consecutive rounds. The IC setting has been widely studied [3, 4, 5, 8, 9, 10. 11, 2. 12] over the past decade. Many recent works have focused on the problem with non-convex and heterogeneous objectives [13, 14, 15] which are common cross-device federated learning (FL. [16, 17J. Towards this end, several algorithms [18, 19, 20, 21, 22, 23], all involving local updates local-SGD [3, 16)), have been proposed and analyzed under assumptions bounding the heterogeneity of machines' objectives. Although these algorithms demonstrate promising empirical performances, it remains elusive whether these algorithms provably dominate the embarrassingly parallelizable alternatives, i.e., mini-batch variants of the optimal sequential algorithms [24, 25, 26] (a.k.a. centralized algorithms).
Until very recently, the situation was similar even in the simpler convex homogeneous setting where F 's are all identical and convex, and Woodworth al. [2] showed that the optimal algorithm often does not require local updates at all. Even when F,, 's are not identical, for high levels of
Equul contribution.
*hiis work was done while BB was a research assistant professor at TTTC.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

heterogeneity, accelerated mini- batch SGD [27] is optimal [28]. Should we expect something similar in the non-convex setting? Or, can we prove that in some regime local- pocal-update algorithms improve over the naive centralized baselines?
Method (Reference) (Oracles used)
Convergence Rate, i.c. E V =
Full Participation Setting
SCAFFOLD MB-SGD [18]
1/2
(Stochastic)
AL π
+
CAAL MKR
MB-STORM (Thm. C.2, [26)) (Stochastic)
da
2/3
π
MKR
+
(MRR
Lower Bound (Centralized)
AL
CAL MMR
2/3
(Theorem 2.1)
MKR
STEM [20] (Stochastic)
(AL + a² (2) (t (MKR)373
BVR-L-SGD* [22]
CE-LSGD (Thm. 3.1)
Ar
AL VKR
+ a² MKR
+
MKR
CAL
(Stochastic)
CE-LGD (Thm. 3.1) (Exact)
Az
AL KR
R
Lower Bound (Theorem 3.2)
Ar It
J² MKR +
CAAL 2/3 MMR
min
Partial Participation Setting
MB-STORM (Thm. D.4) (Stochastic)
AL
o² MKR
GAL
2/3
C²
CAL
2/3
m. K
mä
mif
Lower Bound (Centralized) (Theorem D.2)
AL
o²
+
GAL mKK
2/3
CAL
2/3
mKR
mn
mit
MIMELITEMVR(21] (Stochastic + Exact)
Ar
AL
2
(C+o)Ar 1
2/3
H
KR
R
MIMEMVR [21]
(Exact)
Ar
KR
AL
mR
e
+
Vm
CAr
2/3
CE-LSGD (Thm. 3.3)
Ar R
VKR
AL
mKR
o²
+
mKR
GAL
2/3
me mn/KR KR
GAT
2/3
+
(Stochastic)
2/3
CAT
CAL
+
mvKR
CE-LGD (Thm. 3.3) (Exact)
2/3
A π
+
KR
AL
+
mR
+
CAr mil
Lower Bound (Thm. 3.4)
min
Ar
c²
J
+
KR
AL
2² mKR
GAL mKR
22 mit
2/3
CAL
mKH
Table 1: Comparison of convergence rate for different algorithms in the intermittent communication setting. and 7 are the first and second-order heterogeneity (see Section 2) of the problem. Note that T S 2L can be much smaller than L. *See Section for detailed comparison with BVR-L-SGD. We expect the red and blue terms in the bounds to match by improving our bounds (c.f., Section 5). 'The variance term is optimal as the algorithms' analyses don't 't assume mean squared smoothness.
In this paper, we start by noting that in the absence of any heterogeneity assumption (c.f., Section 2), centralized algorithms already have the best worst-case convergence guarantee. Thus, only when

---

the heterogeneity is low can the local-updare algorithms potentially have an advantage. This was the motivation behind some of the recent works [18. 21, 22]. However, in the absence of any lower bound that explicitly depends on the heterogeneity parameter (such as in [15, 29]), it is not possible to definitively claim such an improvement. To alleviate this, we provide new communication lower bounds which explicitly depends on the heterogeneity parameter. In addition, we develop novel algorithm which can take advantage of low heterogeneity and (almost) optimal.
Method (Reference)
Communication Complexity (R)
Oracle Complexity (N)
Full Participation Setting
SCAFFOLD', MB-SGD [18]
AA
a² AA 6
MB-STORM (Theorem C.2)
AL
2AL e3/2
[26]
Lower Bound (Centralized)
AL
dAL 237
(Theorem 2.1)
STEM
A
(AL)%/+0'04
[20]
237
BVR-LSGD* [22]
CE-LSGD (Theorem 3.1)
23/2
Lower Bound
min Az 52
gAL 3/7
(Theorem 3.2)
Partial Participation Setting
MB-STORM (Theorem C.2)
CAL
dAL e3/2
(1 + g
mc3/2
Lower Bound (Centralized) (Theorem 2.1)
CAL m/372
377
MIMEMVR
CAT 37723377
Uses Exact Oracles
[21]
MIMELITEMVR [21]
too² + (Cto)Ar 23/2
Uses Exact Oracles
CE-LSGD
CAT me3
CAL 677
gAL e//2
(Theorem 3.3)
CT.
Lower Bound (Theorem 3.4)
min
Ar
CAL
AAL
Table 2: Comparison of optimal communication and oracle complexity required by different algo- rithms to attain V 1 < Ç and the heterogeneity (see Section 2) of the problem. T S 2L and can be much smaller than L. The results suppress only numerical constants and assume that e/2 I min((a/M) (r/L), AL/aa, Ar/S. C/m], i.e., c is small enough. The first inequality ensures we are in the green regime described Figure and guarantees that A LLM 3 ALL/2//2 the second inequality guarantees that a²/e I AT the third inequality guarantees that <²/me 3 ÇAT A///m33/2; and the fourth inequality guarantees that AL/c < ÇAL/me3/2 We ex- pect the red, green, and blue terms in the upper and lower bounds to match by improving our bounds (c.f., Section 5). *Although AVR-L-SGI and CE-LSGD have the same fast convergence rate in the full participation setting, many rounds of communications and thus less communication efficient in practice (see discussion in Section 3). Note that the oracle complexity is optimal for these algorithms,, as they were analyzed under the bounded variance assumption (see Section 2).
requires each client compute large batch gradients for
3

---

We summarize the contributions of our work as follows:
We provide novel communication complexity lower bounds, under the assumption that Fin have bounded first-order or second-order heterogeneity (see Section 2). We show that centralized algorithms [24, 25, 26] can never achieve this optimal communication complexity, and most of the existing local-update algorithms cannot attain it either.
We develop a new algorithm CE-LSGD that we show to be min-max optimal when equipped with exact gradient oracles and near-optimal when provided with stochastic gradient oracles (c.f., Section 2). Our algorithm, like many other local-update algorithms, uses variance reduction techniques [24, 26] but requires both fewer and lighter "heavy-batch" operations compared the existing methods (see discussion in Section 3).
We also study the partial client participation setting, which of particular interest in cross-device federated learning (FL) [17] where there is extremely large number of clients. Not only does CE-LSGD improve over the best-known communication complexity, but it is the only algorithm that doesn't 't require exact oracle queries for variance reduction and still manages to be nearly optimal. Our analysis also provides a convergence guarantee for MB-STORM (a special case of CE-LSGD) in this setting that wasn't 't known before. Furthermore, if endowed with exact oracles, CE-LGD is almost min-max optimal even in the partial participation setting. Thus, results demonstrate the optimality of local update methods, at least in some regimes. Even in simpler convex settings, we don't know of any local update method (exact or stochastic) known be min-max optimal in the heterogeneous setting [30, 15]. We summarize our results and the comparison to important baselines in Tables and 2.
As an auxiliary contribution, we provide a variant of our algorithm which uses stochastic hessian vector product oracles and is thus useful for settings where only single copy of the model can be stored on the edge device. We also empirically compare our method against centralized and local-update algorithms, demonstrating faster convergence and better communication efficiency.
Notation. We use denote the index set and [B] to denote its cardinality. For x E RRd, we use |>||| to denote its fz-norm. For E Rdxd || denotes the operator norm, [n] denotes the set (1.2....,n} nI. We use 2,, 3, ł to denote equality and inequality up to numerical constants.
2 Our Setting and the Centralized Baselines
In this section, we introduce some definitions and assumptions that will be used in our analysis. Our goal is to find an c-approximate stationary point of F, i.e., a point E I2 such that || VF()))] S c, where the expectation is w.r.t. any randomness in the choice of x. We consider client objectives the class F(L) of differentiable and L-smooth functions, i.e., for all G E F(L), [[ - VG(y)] < L I| yll- We also make assumptions that relate the functions of different clients to one another. These are typically known as assumptions on the "heterogeneity" " of the problem, and we consider two classes of problems.
Definition 1. Assume {Fm E F(L))M are first-order {-heterogeneous, i.e., SUPZER2 Em [VFm (x) - VF(x)) S S. And for all A 2 0, F(0) iinfzex F(x) S A, iee. the average objective has bounded sub-optimality at zero. Then we say that (EmImEIM) F (L,
Definition 2. Assume twice diffe-differentaalle {Fm E F(L) are second-order T T-heterogeneous, Le., (URRE ( F2F())) S r. And for all A 2 0, F(0) inf F(x) S A. i.e. the average objective has bounded sub-optimality at zero. Then we say that {Fm IMEIM E F² (L,
We assume that each machine has access to the following multi-point oracle [31] [Section 5.3, 2].
Definition 3. Given a function G E F(L, A), On On. (Rdd) x Z + (R)" x (Rd))
multi-point stochastic first order oracle for some distribution D Z, and for all æı, . In
Rd. the oracle samples random seed ~ D and returns estimators Op Or (zi,.... In. 2)
(ff(zz =))e [g(x; 2) hejj)) such that Vi E [n], Ez=D(f(x; z), g(z;; 2)) = (G(x,), VG(x.))
and E,~D (19(xx;)) VG(x:)l smoothness, i.e., for all y E R2, E.-D [1)g(;;) g(v: 2)ll - L L|| v/I.
o². Furthermore, the unbiased gradients satisfy L-mean

---

As we mentioned before, we want to solve the problem in equation 1.1 in the the intermittent communication (IC) setting, i.e., M machines work in parallel and are allowed make K oracle calls between two communication rounds for R consecutive rounds (see [1. 2] for detailed definition). Therefore, we consider a generalization of zero-respecting algorithms denoted by Azn (see Appendix A) in the IC setting. This class captures various distributed optimization algorithms, including mini- batch SGD, accelcrated mini-batch SGD, local SGD, and all the variance-reduction algorithms. Algorithms that are not distributed zero-respecting are those whose iterates have components in directions about which the algorithm has no information, meaning that, some sense, is just "wild guessing". We also denote the class of centralized algorithms in Azæ by AzR (see Appendix A). These algorithms query the oracles at the same point within each communication round and use the combined MK oracle queries each round get "mini-batch" estimate of the gradient. Thus, the class AZR includes algorithms such as mini-batch SGD, mini-batch SARAH [24] and mini-batch STORM [26], but doesn't 't include local-update algorithms in Azn such local-SGID. Furthermore, these mini-batch algorithms can be naturally implemented in the IC setting.
We first present a lower bound result applicable to centralized algorithms.
Theorem 2.1 (Centralized Lower Bound). For all A.S. a 2 O, and 2L 2 T, every algorithm A E 2R optimizing problem in F& (L, A, UM, T), with access to oracle O7 over R communication rounds must output x such that,
|F(
AL R MKR
O²
GAL (MK
2/3
=
The proof of this theorem follows the known oracle complexity lower bounds [32, 31] and is included in Appendix B. This theorem shows that, mini-batch batch SARAH/STORM which are centralized algorithms,, already achieve the optimal communication and oracle complexity (see Table 1) for algorithms in A optimizing problems in F&, (L, A, r). In fact most existing non-centralized methods including FEDAvG[16), SCAFFOLD [18] and FEDPAGE [19] do not have any analysis showing improvement over the centralized haselines for problems in F&, (T, A, T). These analyses do not improve with smaller heterogeneity т, even for convex optimization problems. At the same time, the lower bound result holds for all T S. 2L, which highlights the limitation of the centralized baselines, showing they can not improve with lower heterogeneity. Certain existing local-update algorithms such as MIMEMVR [21] and B algorithms in the low heterogeneity regime. In the next section, we quantify this improvement and show that our algorithm strictly dominates the centralized baselines and almost matches our lower bound for algorithms in Azn-
[22] can indeed improve upon centralized
3 Our Algorithm and Min-max Optimality
In this section, we present our communication-eficceentt algorithm abbreviated CE-LSGD and illustrate it in Algorithm 1. Note that for m E [M]. we use the notation F.m, (r) == Eiegm g 21 BB to denote the stochastic mini-batch gradient obtained by querying
02L. for m8Th) many times. Pm
At each iteration of Algorithm 1, need two rounds of communication, i.e., two back and forth communications between the server and all clients. Our method uses the extra round of communication, i.c., line line 9, update the variance-reduced gradient e, using the current and previous server models Ir, -1, respectively, In the following discussion, we will use the iteration number It and communication complexity of Algorithm interchangeably.
At the core of our proposed method is the variance reduction term v, and the local gradient es- timator 2 (lines 9 and 15 in Algorithm 1). The construction of the local gradient estimator is motivated by the variance reduction technique of SARAH [24, 25). Intuitively, the estimation error between the proposed local gradient estimator eith and the full gradient V F(( i.e.,
E 1
VF(W Il. can be decomposed into two dominating terms: Elle,
(2,))) and
" W || The first term is the estimation error between the variance reduction term U, and the full gradient V F(z,). Since is updated based the momentum-base
K Σ
E| Elj
k=
5

---

Algorithm 1 Communication Efficient Local Stochastic Gradient Descent (CE-LSGD)
input Initialization Zo, iteration number R, step size 7/, parameters bo, b, T and 3 [0, 1
1: Let T 20
2: for 0, ....,.................
do = Q=
= by else set = 4: Communicate (send) (Fr, 1r-1) clients
3: if 0 set
5: on client m E [M]] do
6: Sample 8 DDB get Br (I+)) V FF m. (Iy- where | =
7:
Communicate (rec) (V mm (Ir), V m, (x. to the server
8:
end on client d Or M
9:
Vm (3rr
p) Uy-1 M Em=1 V V (m
10: Communicate (send) (Iy, 14.) to client my, where m, ~ Unis ([M)
11:
on client My do
1 = w w == Zr. 400 Ur
for l = 1,..., do
14:
Sample 7
& get V mm (41.)) V m. (w (4+1180-1) )) where 18 = b
15:
r,
FF
(w,+1,)) + r,k-1
VF th
16:
w 111,1+11
= w
741,
mr
17:
end for
Communicate (rec) (w1+1.Q+1) the server
end client
20:
end for ++1.41
Let Ir+1 w th
21:
output Choose uniformly from ) (ee(l))
variance reduction technique [26], this estimation error is dominated by
L L2
Zr- 1|2
which
approaches zero the algorithm converges. Similarly, the second term
[ w ||
approaches zero as the algorithm converges and the 7 factor controls the benefit we obtain from small heterogeneity. Intuitively, we can make more local updates for smaller values of т, and the algorithm converges faster. Our method reduces mini-batch STORM if we choose the number of local updates Q to be one (see Appendix C.I).
As mentioned before, are considering the IC setting, and thus want to implement Algorithm I in this setting. To this end, we can choose the input T = K and = 1 (see line 14) in Algorithm 1, and present the convergence guarantees of our method in the IC setting the following discussions. Next we present the convergence guarantee of CE-LSGD in the intermittent communication: Theorem 3.1. Suppose M
for A, 2 0, < 2T. then,
(a) if each client m E [M] has a stochastic oracle Fm and assuming (MK)
AL R
1 /MR
then
the output of Algorithm I ussin B max
{ R -478 }. bn KR, and n
min {1 1 1/2 satisfies
11 Kr LK
AT
AL KR
Q² +
GAL 2/3
E V
MKR
MKR
(b) if each client E [M]] has a deterministic oracle Fm. 3 and n7 min { KT satisfies
then the output 7 of Algorithm 1 using
AT
AL KR
VF
R
In Appendix C, we derive this result by carefully tuning 8, by. We show that the convergence rate attained by our algorithm is almost optimal by proving the following lower bound result.

---

Theorem 3.2. For all L,0,T,A
S VAL, every algorithm A E Agr. optimizing a problem F (L, A. with K > intermittent accesses two-point first-order Fi Ime[M] on all the machines, outputs I Rt after R = 1 rounds such that
oracles
{ Ar R
AL
0² +
2/3 OAL (MKR)
E |
= min
KR
MKR
We can make two observations by comparing the upper and lower bounds for problems in Fls (I, A, T). First, in the deterministic setting (a 0), upper bound matches the lower bound; hence CE-LGD is min-max optimal. Thus, our result improves over all the existing results in this setting, including MIMEMVR [21]. Second, in the stochastic setting (o 0), our algorithm's s upper bound is optimal except for the second term in Theorem 3.1, which has AL/ (v/ R) factor as opposed to the A term in the lower bound. We discuss this gap further in Section C.2.
Our construction for Theorem 3.2 uses the non-convex hard instance proposed by Carmon al. [32] and splits it across different machines to get a communication complexity lower bound. This idea has been used previously to give lower bounds in the heterogeneous setting [33, 15, 34). We prove the result in Appendix B. From looking at Table 1, we can note that BVR-L-SGD [22] also attains similar upper bound
method. In Appendix C.2, we show that with deterministic oracle BVR-L-SGD also attains the min-max optimal rate. This is not surprising. knowing that several variance-reduced algorithms [25, 26, 24] are simultaneously optimal even in the sequential setting. Still, our method requires fewer and lighter variance reduction operations, which leads to better scalability from the algorithmic design perspective. In the next section, carefully examine the difference between these methods.
3.1 The Perspective of Reducing Communication
So far, we have looked at convergence rates in the intermittent communication model, where K, R is fixed. However, another perspective is reducing the communication complexity to the minimum possible with the minimum required oracle complexity. Both these complexities can be expressed in terms of c using the convergence guarantees we showed, where we want to attain an e-approximate stationary point. This view is often more useful when communication rounds comprise the bulk of the required physical time. This scenario is common in FL, where devices become available intermittently. which delays the synchronous updates. With this in mind, we summarize the communication and oracle complexities attained by both our method and BVR-L-SGD [22] in Figure when optimizing with stochastic oracles. Notice that the figure has three different regimes based on the relative scaling of versus e. We focus on the green regime characterized by 1/2 E (0. (o.ra/(T.M) (I.M))- This regime of most practical interest in deep learning, where modern over wee-parameterized models often drive to really small values. And when small enough, this regime covers wide range of values of 7.3.
A.M
n1
Ar
Figure 1: Illustration of the best communication complexity R and oracle complexity N that our method can obtain for different and т. Green regime: Our method can obtain the optimal com- munication and oracle complexity. Orange regime: Our method can obtain the optimal communication using a larger oracle complexity. Red regime: Our method only needs one round of communication using a larger oracle complexity.
In the green regime, both CE-LSGD and B BVR-L-SGD require K oL/(TMe) local steps to achieve the optimal communication and oracle complexities. However, BVR-L-SGD requires multiple heavy-batch stochastic gradient computations on each machine with batch size bman- In particular, for BVR-L-SGD, we have ØBVR bmoz/ KK (L))),, which suggests that for = LA communication rounds, requires each machine to compute ΦBVR times heavier batch stochastic gradients compared to the other communication rounds. As for CE-LSGD, we have
3 We talk about the other regimes while giving the full statement of Theorem 3.1 in Appendix
7

---

K- 64
K - 1024
BVR-LSGD CE-LSGD
-1.0
L18
logpalTrain Loss)
Iogai Loss)
11:55
-1.9
-1.20
-1.44
-1.6
-1:35
-128
200 25 30
35
1.0
35 4.0
1ogro(Number of Communication Rounds)
Iogio(Number of Communi cation Rounds)
Figure 2: Training loss of CE-LSGD and BVR-L- of communication rounds in the intermittent communication setting with different local-updates K. We use M = 10 machines, and synthetically generate heterogeneous data-sets (see Section 4) with q = 0.1. All oracle queries use a mini-batch of size b = 16, i.e., each machine has K'b oracle queries between communication rounds. We note that our method has faster convergence in all the settings, which highlights its communication efficiency. Fixed step-sizes for both the methods were tuned in {0.001, 0.005, 0.01, 0.05, 0.1, 0.5) } (to obtain best loss) following [22], our method set the K, while LBVE Rt 5000 according to [22]. max
CIFAR- 10 data-set versus the number
momentum B = 0.3, bour
bo - -² (LA(()))))) which gives us Pour = - only requires each machine to compute Poor times larger batch stochastic gradient, and that too only once. Furthermore, Pour! PAvR = /e//2/(LA) < 1. Thus, the size of our large batch gradient is also smaller than the one for BVR-L-SGD, and our method has fewer and lighter heavy-batch operations.
This suggests that our method
Suppose one implements both these methods in the intermittent communication model, i.c., by breaking the large batch computation across multiple rounds, with local budget K = oT/(TMe In that case, the effective communication complexity of both methods is AT/c, and this subtle difference gets washed away. However, in Figure 2, we show that this equivalence up to numerical constants doesn't 't hold in practice, where our method converges faster than BVR-L-SGD, Table 2, we summarize the communication and oracle complexities attained by different algorithms in the green regime.
3.2
The Partial Participation Setting
In settings such as cross-device federated learning [17], there are often millions of clients (think of android mobile users), and it is not feasible to consider training all of the clients synchronously. It is more natural to consider a partial sampling of clients for each communication round. More formally, we can re-state our distributed optimization problem follows:
min #ERd
Fzz) := Em-p [x)],,
(3.1)
where is probability distribution on the clients, assume at each communication round, we can sample M clients independently from P. We also need to modify the IC setting: during each communication round, S, pm clients participate, and each queries their oracle K times. This setting has also been considered in Karimireddy et al. [21]. We consider the problem classes Fp (L, A. <) and F3 (L, A) that are natural generalizations Fl (L, A, {) and (L, to the partial participation setting as follows, formally defined in Appendix A.
We adapt Algorithm
the partial participation setting in Algorithm 2 by communicating with only M clients at each round and using M, clients for the first round to initialize the variance reduction term. We prove the following guarantee for Algorithm 2.
Theorem 3.3. Suppose for all m in support of P. Fm E ( then,
(a) if each client m has a stochastic oracle O2.L. and assuming that
Ar
AL
o²
R
VKR
VMK
VM
AlT+L/NKWM
2/3)
the output ă of Algorithm 2 using 60 = K, Mo = MR, = max
R(o2/K+CC5)
8

---

and nj min
1
VEM VKL
VBM TK
satisfies
Kr
VRL
AT
AL
o²
OAL MKR
2/3
C²
(ÇAT
2/3
+
+
+ (2)
2/3
R
VRR
MKR
MR
MR
(b) if each client has deterministic oracle O2I.., Fin
and assuming that Ar 3 e
JM
then the oulput
2/3
I of Algorithm 2 using Mo = MR, 3 = max
AAr/M) R:
1
and 11 = min { KF
JBM TK
5-R
satisfies
BI 3 AT
AL KR
2²
ÇAT
2/3
MR
MR
In Tables 1 and 2, we show that with an exact oracle (i.e., a= 0), CE-LGD attains a strictly faster convergence rate than the best-known algorithm MIMEMVR [21] that also uses an exact oracle. More specifically, CE-LGD's communication complexity ÇAT/Me improves over the communication complexity of ÇÂT/ /Mr//Me// 2/2 for MIME-MVED We can also recover the guarantee for MB- STORM in the partial participation setting, noting that it a special case of CE-LSGD (see Appendix C.I). As far as we know, this guarantee isn't t known in the literature but straightforwardly follows from our analysis. Furthermore, we prove the following lower bounds showing that the convergence rates of CE-LSGD are almost optimal.
Theorem 3.4. For all L, T, A,C20,
SS VAL, every algorithm Agr optimizing U.C)),P((L,AA7 with K > 0 intermittent accesses to two-point first-ordrr
problem in 2..77 JmEuppon(P) on all the machines output x after R. > rounds such that
oracles (OP
A 22 R R
AL
o²
+ ( GAL MMR +
2/3
S
+ ( CAL
2/3
E |
ž min
KR
MKR
MR
MKR
According to Theorem 3.3 and Theorem 3.4, in the deterministic setting (i.e., a 0), the only gap between the rate for CE-L.G and the lower bound is in the last term of CE-L.GI's upper bound, i.c. the blue term in Table 1. We conjecture that CE-LGD is optimal in the partial participation setting, and our lower bound can be improved. This would also imply gap between the optimal communication complexity of the full and partial participation settings (O(1/c) v/s ((1/c3/2), see Table 2). All of the known results with our partial participation setting [21] attain best order 3/2 communication complexity, which is consistent with our conjecture. More discussions about the gaps in this setting can be found in Appendix D.1.
Simulations
We evaluate the performance of our method by optimizing a two-layer fully connected network for
multi-class classification on the CIFAR-10 [35] data-set. Since we are in the heterogeneous setting, we need to artificially generate data-set. We follow the same data processing procedure as in [22]. We first make sure that all the ten classes in CIFAR-10 10 have the same number of samples (roughly around 5000), and assign q x 100% of class m's 's samples to client m E [10) where q is chosen from (0.1, 0.35, 0.6, 0.85). For each class m, we evenly split the remaining (1 4) x 100% samples to the other clients except client m. Thus, controls the heterogeneity of our data-set, with small corresponding to small heterogeneity.
We perform two diffferent experiments. In the first experiment, we directly compare our method, i.c. CE-LSGD, with BVR-L-SGD in the intermittent communication setting (see Figure 2). We observe that while both the methods converge similar quality of solution eventually. our method is more communication efficient. In the second experiment, we compare our method with BVR-L-SGD [22] as well as FEDAVG [16], SCAFFOLD [18], MB-SARAI [24] and MB-SGD [5] for the same number of updates/iterations. The last two methods are centralized baselines, and we use the local computation to compute a mini-batch stochastic gradient. We again observe that CE-L.GD and
B BVR-L-SGD have comparable performance which is better than all the other methods.

---

-325
Inglulraiin Look)
329
ND SARAR
Figure 3: Comparing CE-LSGD centralized and local-update methods, for fixed K 32 and varying heterogeneity controlled by on CIFAR-10 [35] data-set. Like Figure 2 we use mini-batch size 16 for each oracle query. Thus each method makes Kbb oracle queries every round per machine. All the methods for different are tuned separately, following similar hyper-parameter search in Figure 2.
5 Discussion and Open Problems
In this paper, we provide analyze in the full and partial client participation settings with intermittent communication. In the deterministic setting, i.e., with access exact oracles, our algorithm is optimal for the full participation setting and almost optimal for the partial participation setting. Moreover, when equipped with stochastic oracles, our algorithm attains the best-known convergence guarantees to our knowledge in both participation models. Our lower bound results provide a much-needed baseline to measure algorithmic developments in non-convex distributed optimization and help us characterize CE-LGD's optimality.
communication--ffcceent local update algorithm CE-LSGD and
In Appendix E, provide an extension of CE-LSGI which uses stochastic Hessian vector product oracle [12, 36] instead of a multi-point oracle, and recovers similar optimal communication complexity. This is relevant for memory-constrained online settings where it might not be feasible to preserve several copies of a model on the client device for making simultaneous queries for variance reduction algorithms.
Our work leaves several open questions. We believe our lower bound is loose in the deterministic partial participation setting. We expect a (AT/M 3/2 term the lower bound, just like our upper bound in Theorem 3.3 (c.f., the blue terms in Tables 1 and 2). Thus, we conjecture that there is gap between the optimal communication complexities the full and partial participation settings, order I/c versus 3/2 We hope improve our lower bound in the future work.
We expect that CE-LSGD should attain the min-max optimal rate in the stochastic full participation setting. There is 1/VK K gap in our optimization term for both participation models, which vanishes in the deterministic setting (see Table 1). As discussed in Section C.2, it is unclear to how to remove this gap.
There are several gaps w.r.t. the lower bounds in the stochastic partial participation setting (c.f., the blue, green, and red terms in Table 2). We believe some these can alleviated by improving the deterministic lower bound, but others seem to imply that our analysis is loose. As we discussed before, one indication that our upper bound is loose the gap in the rate we obtain for MB-STORM by adapting analysis for Theorem 3.3 (c.f., the red term in Table 1, section D.1).
Acknowledgements
We thank the anonymous reviewers who helped us improve the writing of the paper. We would also like to thank Mladen Kolar, Boxiang Lyu, Boxin Zhao, and Sebastian Stich for several useful discussions. This research was supported part by NSF-BSF award 1718970, NSF TRIPOD IDEAL. award and the NSF-Simons funded Collaboration the Theoretical Foundations of Deep Learning.
10

---

References
[1] Blake E. Woodworth, Jialei Wang, Adam Smith, Brendan McMahan, and Nati Srebro. Graph oracle models, lower bounds, and gaps for parallel stochastic optimization. Advances in neural information processing systems, 31, 2018.
[2] Blake Woodworth, Brian Bullins, Ohad Shamir, and Nathan Srebro. The min-max complexity of distributed stochastic convex optimization with intermittent communication. In Conference on Learning Theory, pages 4386-4433 PMLR, 2021.
[3] Martin Zinkevich, Markus Weimer, Lihong Li, and Alex Smola. Parallelized stochastic gradient descent. Advances in neural information processing systems, 23, 2010.
[4] Andrew Cotter, Ohad Shamir, Nati Srebro, and Karthik Sridharan. Better mini-batch algorithms via accelerated gradient methods. Advances in neural information processing systems, 24, 201
[5] Ofer Dekel, Ran prediction using mini-batches. Journal of Machine Learning Research, 13(1), 2012.
Ohad Shamir, and Lin Xiao. Optimal distributed online
[6] Yuchen Zhang, John Duchi, Michael Jordan, and Martin Wainwright. Coormation-theorelle lower bounds for distributed statistical estimation with communication constraints. Advances in Neural Information Processing Systems, 26, 2013.
[7] Yuchen Zhang, John Duchi, and Martin Wainwright. Divide and conquer kernel ridge regression: distributed algorithm with minimax optimal rates. The Journal of Machine Learning Research, 16(1):3299-3340, 2015.
[8] Ohad Shamir, Nati Srebro, and Tong Zhang. Communication-effiiinee distributed optimization using an approximate newton-type method. In International conference on machine learning. pages 1000-1008. PMLR, 2014.
[9] Sebastian U Stich. Local sgd converges fast and communicates little. arXiv preprint arXiv:1805.09767 2018.
[10] Aymeric Dieuleveut and Kumar Kshitij Patel. Communication trade-offs for local-sgd with large step size. Advances in Neural Information Processing Systems, 32, 2019.
[11] Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Mcmahan, Ohad Shamir, and Nathan Srebro. Is local sgd better than minibatch sgd? In International Conference on Machine Learning, pages 10334-10344 PMLR, 2020.
[12] Brian Bullins, Kshitij Patel, Ohad Shamir, Nathan Srebro, and Blake E Woodworth. stochas- tic newton algorithm for distributed convex optimization. Advances in Neural Information Processing Systems, 34, 2021.
[13] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning, pages 5381-5393. PMLR, 2020.
[14] Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pages 4529.. PMLR, 2020.
[15] Blake Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch vs local sgd for heteroge- neous distributed learning. Advances in Neural Information Processing Systems, 33:6281 33:6281-6292 2020.
[16] Brendan McMahan, Fider Moore, Daniel Ramage, S Hampson, and B Agüera y Areas. Communication-effiiienn learning of deep networks from decentralized data (2016). arXiv preprint arXiv: 2016.
[17] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, al. Advances and open problems federated learning. corr. arXiv preprint arXiv 1912,04977, 2019.

---

[18] 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 on Machine Learning, pages 5132-5143. PMLR, 2020.
[19] Haoyu Zhao, Zhize Li, and Peter Richtárik. Fedpage: A fast local stochastic gradient method for communication-effiiiee federated learning. arXiv preprint arXiv:2108. 04755, 2021.
[20] Prashant Khanduri, Pranay Sharma, Haibo Yang, Mingyi Hong, Jia Liu, Ketan Rajawat, and Pramod Varshney. Stem: A stochastic two-sided momentum algorithm achieving near-optimal sample and communication complexities for federated learning. Advances in Neural Information Processing Systems, 34, 2021.
[21] Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank J Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning, arXiv preprint arXiv:2008. 2006000000000666 2020.
[22] Tomoya Murata and Taiji Suzuki. Bias-variance reduced local sgd for less heterogeneous federated learning. arXiv preprint arXiv:2102.03//98 2021.
[23] Rudrajit Das, Anish Acharya, Abolfazl Hashemi, Sujay Sanghavi, Inderjit S Dhillon, and Ufuk Topcu. Faster non-convex federated learning via global and local momentum, arXiv preprint arXiv:2012.04006 2020.
[24] Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: A novel method for machine learning problems using stochastic recursive gradient. In International Conference on Machine Learning, pages
PMLR, 2017.
[25] Cong Fang. Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non- convex optimization via stochastic path- anth-integrated differential estimator. Advances in Neural Information Processing Systems, 31, 2018.
[26] Ashok Cutkosky and Francesco Orabona. Momentum- based variance reduction in non-convex sgd. Advances in neural information processing systems, 32, 2019.
[27] Saeed Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework. SIAM Journal on Optimization, 22((): 1469-142, 2012.
[28] Blake Woodworth. The minimax complexity of distributed optimization. arXiv preprint DxXiv:2009000544 2021.
[29] Margalit R Glasgow, Honglin Yuan, and Tengyu Ma. Sharp bounds for federated averaging (local sgd) and continuous perspective. International Conference on Artificial Intelligence and Statistics, pages 9050-9090. PMLR, 2022.
[30] Jianyu Wang, Rudrajit Das, Gauri Joshi, Satyen Kale, Zheng Xu, and Tong Zhang. On the unreasonable effectiveness of federated averaging with heterogeneous data. arXiv preprint arXiv:2206.0477 047233, 2022.
[31] Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Wood- worth. Lower bounds for non-convex stochastic optimization. arXiv preprint 17X.v.191..02365. 2019.
[32] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, 184(1):71-120, 2020.
[33] Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimization. Advances in neural information processing systems, 28, 2015.
[34] Xinwei Zhang, Mingyi Hong, Sairaj Dhople, Wotao Yin, and Yang Liu. Fedpd: A feder- ated learning framework with optimal rates and adaptivity to non-iid data. arXiv preprint arXiv:2005.1 1418, 2020.
[35] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Citeseer, 2009.
12

---

[36] Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Ayush Sekhari, and Karthik Sridha- ran. Sedond-order information in non-convex stochastic optimization: Power and limitations. In Conference on Learning Theory, pages 242-299. PMLR, 2020.
[37] Yurii Nesterov et al. Lectures convex optimization, volume 137. Springer, 2018.
[38] Arkadi Nemirovski. Efficient methods in convex programming. Lecture notes, 1994.
[39]
Tao Lin, Sebastian U Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini-batches, use local sgd. arXiv preprint arXiv: (008:v//00..72220 2018.
[40] Christopher J Shallue, Jaehoon Lee, Joseph Antognini, Jascha Sohl- Sohl-Dickstein, Roy Frostig, and George E Dahl. Measuring the effects of data parallelism on neural network training. arXiv preprint arXiv:1811.03600, 2018.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report bars (e.g., with respect the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] In the appendix
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "zZycgOD9Crm", "reviewer": "Reviewer_jnY7", "summary": "The paper proposes a new algorithm for non-convex optimization -- CE-LSGD, which is optimal under certain heterogeneity assumptions. The authors show the algorithm optimality via matching upper-bound (convergence rate of CE-LSGD) and lower-bound (on the discussed problem class). The algorithm is analyzed for different regimes: full and partial client participation and full and stochastic gradients. Experiments on two-layer NNs support the theory.", "questions": "Questions naturally arise from weaknesses:\n- Do you mean generalization losses in the theorems mentioned? If yes, then vital, in my opinion, test loss comparison experiments are missing. If not, what is the role of multi-point oracles? It seems the paper lacks clarity on this question.\n- Is the case when $\\tau$ is much smaller than $L$ is interesting, and why? Is it practical, and why?", "limitations": "The second weakness (\"$\\tau$ is much smaller than $L$\") can be considered a limitation. ", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- the paper presents a good survey of existing algorithms (table 1&2);\n- a lower bound for the class of functions is derived;\n- the proposed algorithm matches the lower bound, thus, proving optimality;\n\nWeaknesses:\n- As far as I understood, Theorems 2.1&3.1&3.2 establish generalization bounds (in Definition 3, when defining oracles, samples $z$ are derived from the distribution ${\\cal D}$). Meanwhile, experiments depict the train losses only.\n- Theorem 2.1. requires $\\tau \\leq L$, although the question regarding how often this condition is satisfied is not discussed. The only guaranteed inequality is $\\tau \\leq 2L$. The paper says that $\\tau$ can be much smaller but, for example, in the case of convex functions (what is a subclass of non-convex functions) $\\tau \\geq \\frac{M-1}{M} L$.\n\nTypos/suggestions:\n- line 59: usually, the optimization problem is ${\\mathbb{E}} \\|\\nabla F(x)\\|^2 \\leq \\varepsilon^2$;\n- page 4: I would suggest adding the definition of class ${\\cal F}(\\Delta, L)$ in the environment of “definition” in the text so that the reader does not search for it in the text;\n- Definition 3 presumable contains two typos: on line 73, $x$ is not defined; on line 74 $\\sup_{x, y}$ is redundant (otherwise, the last sentence does not make sense);\n- line 100: in ${\\cal O}^{2, l, \\sigma^2}_{F_m}$ $l$ must be capital\n- Algorithm 1, line 3: what is $b_0$? (defined only later, in Theorem 3.1)\n- Algorithm 1, line 12: $x_t \\longrightarrow x_r$\n- Algorithm 1: I would suggest leaving a tilde out over $\\widetilde{m}_r$; the tilde makes the full of different notations (e.g. line 14) algorithm even more complicated; \n- Theorem 3.1: $b_0$ is an integer, rounding in the theorem is absent;\n- Theorem 3.1: $1/L$ is always larger $1/\\sqrt{K}L$", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "UYPDq0rMoKk", "reviewer": "Reviewer_pZGN", "summary": "The authors provide a communication-efficient algorithm under centralized stochastic setting. They prove both upper bound of convergence of the algorithm and the lower bound for a class of the algorithm. Together with the upper bound and lower bound, the algorithm is min-max optimal algorithm under full participation setting and near optimal for partial participation setting.", "questions": "1.  Table 1 seems to be confusing because it seems that the lower bound is larger than the upper bounds.\n\n2. [33] also claims that they give algorithms with the optimal rates, what is the difference between the lower bounds and the algorithms?\n\n3. There are lots of definitions missing in the main text, it would be better to move those algorithm definitions and some main technical difficulties in the main text, by compressing Table 1 and Table 2.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "strengths:\n\n1. The authors provide a new algorithm that meets the min-max optimal bounds.  \n\n2. For Herterogenety, the author does not only consider the first order but the second-order heterogeneity.\n\nWeaknesses see the questions part.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8fqjTiAmFgL", "reviewer": "Reviewer_ssxz", "summary": "The paper considers the nonconvex optimization problem in the centralized distributed setting and in the partial participation setting. The paper provides a new method CE-LSGD that improves previous methods by performing lighter batch stochastic gradient computations. Moreover, the paper provides the lower bounds under two heterogeneous assumptions.", "questions": "Can the authors get more details on why the oracle complexity of CE-LSGD is suboptimal in the partial participation setting? It is not clear how they obtained $N = O(\\frac{1}{\\epsilon^2}).$ Moreover, how do the authors calculate the oracle complexity of Mini-batch STORM in the partial participation setting?", "limitations": ",", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. The first contributions **(C.1)** of the paper are the lower bounds. For simplicity, I consider Definition 2 only. Under this definition, in Theorem B.3, the authors show that $E ||\\nabla f||^2 \\geq \\frac{\\Delta \\tau}{R} + ...,$ where $\\tau$ is the parameters from Definition 2, while the centralized algorithm have the lower bound $E ||\\nabla f||^2 \\geq \\frac{\\Delta L}{R} + ....,$ where $L$ is Lipschitz constant such that $L \\geq \\tau$. I believe that these results have the following weaknesses:\n\n    1. **Theorem B.1 (or Theorem B.3) doesn't show that $\\tau$ is significantly smaller than L.** It is not clear from the example in the lower bound theorem. It means that $\\tau$ and $L$ can be equal, and the author reproved the previous results. In Theorem B.3, the authors don't show that $L$ is a **tight** Lipschitz constant. In their example, the **tight** Lipschitz constant can be equal to $\\tau,$ then, obviously, every constant $L \\geq \\tau$ is also a Lipschitz constant.\n    2. The author copy-pasted the proof from Lower Bounds for Finding Stationary Points I Carmon et al., and in the proofs substituted $L$ with $\\tau.$ Do not misunderstand me; there is nothing wrong with reusing (copy-pasting) the previous results and making tiny changes, but only if it leads to new results.\n\n2. The other contributions are related to the CE-LSGD algorithm. At its core, the method is STORM (MVR) method from Momentum-based variance reduction in non-convex SGD Cutkosky el al (see also An Optimal Hybrid Variance-Reduced Algorithm for Stochastic Composite Nonconvex Optimization Liu et al.) that is extended to distributed optimization setting. As the author noted in line 117, **CE-LSGD is a mini-batch STORM, where the mini-batches are formed from the mini-batches calculated on clients**. And mini-batch STORM gets the same convergence rate as CE-LSGD. I would admit that the analysis of STORM in the distributed setting is an impactful contribution if it was not analyzed previously in the following papers:\n    1. **STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learning Khanduri et al.** This method does not have an issue with large batch sizes, but it gets slightly worse rates due to adaptivity. \n    2. **Distributed stochastic non-convex optimization: Momentum-based variance reduction. Khanduri et al.** This method does not have an issue with large batch sizes, but it gets slightly worse rates due to adaptivity.\n    3. **DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization Tyurin et al.** This method does not have an issue with large batch sizes and gets the same rate as CE-LSGD or BVR-L-SGD.\n\n    At least 3 papers analyzed STORM in the distributed setting. All in all, CE-LSGD improved the analysis of the previous method by considering Definition 1 and Definition 2. \n\n3. In the partial participation setting, the oracle complexity of CE-LSGD is suboptimal w.r.t. $\\epsilon.$ (see Table 2) and equals to $O(\\frac{1}{\\epsilon^2})$. For this method and Mini-batch STORM I would expect to get $O(\\frac{1}{\\epsilon^{3/2}})$ as in the full participation setting. (see Questions below)\n\nI think that the authors are on the right way, and it is possible to improve the lower bounds by considering Definition 2 and Definition 3, but the current lower bounds theorems are not strong enough and can be misleading in the community. Moreover, a new method, CE-LSGD, doesn't provide a significant novelty that would be helpful in future research.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept