Communication-efficient SGD: From Local SGD to One-Shot Averaging
Authors: Artin Spiridonoff
Alexander Olshevsky
Ioannis Paschalidis
Venue: NeurIPS 2021 Poster (2021)
Keywords: Local SGD
Convex Optimization
Stochastic Gradient Descent
Speed-up

Abstract: We consider speeding up stochastic gradient descent (SGD) by parallelizing it across multiple workers. We assume the same data set is shared among $N$ workers, who can take SGD steps and coordinate with a central server. While it is possible to obtain a linear reduction in the variance by averaging all the stochastic gradients at every step, this requires a lot of communication between the workers and the server, which can dramatically reduce the gains from parallelism.
The Local SGD method, proposed and analyzed in the earlier literature, suggests machines should make many local steps between such communications. While the initial analysis of Local SGD showed it needs $\Omega ( \sqrt{T} )$ communications for $T$ local gradient steps in order for the error to scale proportionately to $1/(NT)$, this has been successively improved in a string of papers, with the state of the art requiring  $\Omega \left( N \left( \mbox{ poly} (\log T) \right) \right)$ communications. In this paper, we suggest a Local SGD scheme that communicates less overall by communicating less frequently as the number of iterations grows.  Our analysis shows that this can achieve an error that scales as $1/(NT)$ with a number of communications that is completely independent of $T$. In particular, we show that $\Omega(N)$ communications are sufficient. Empirical evidence suggests this bound is close to tight as we further show that $\sqrt{N}$ or $N^{3/4}$ communications fail to achieve linear speed-up in simulations. Moreover, we show that under mild assumptions, the main of which is twice differentiability on any neighborhood of the optimal solution, one-shot averaging which only uses a single round of communication can also achieve the optimal convergence rate asymptotically.

Communication-effiienn SGD: From Local SGD to One-Shot Averaging
Artin Spiridonoff
Alex Olshevsky
Division of Systems Engineering
Division of Systems Engineering
Boston University
Boston University
Boston, MA 02215
Boston, MA 02215
artin@bu.
alexols@bu. edu
loannis Ch. Paschalidis
Division of Systems Engineering
Boston University Boston, MA 02215
yannispōbu. edu
Abstract
We consider speeding up stochastic gradient descent (SGD) by parallelizing it across multiple workers. We assume the same data set is shared among N workers, who can take SGD steps and coordinate with central server. While is possible to obtain linear reduction in the variance by averaging all the stochastic gradients at every step, this requires a lot communication between the workers and the server, which can dramatically reduce the gains from parallelism. The Local SGD method, proposed and analyzed in the earlier literature, suggests machines should make many local steps between such communications. While the initial analysis of Local SGD showed it needs R(VT) communications for T local gradient steps in order for the error to scale proportionately to I/(NT), this has been successively improved in string of papers, with the state of the art requiring 2 (N poly(log T))) communications. In this paper, we suggest a Local SGD scheme that communicates less overall by communicating less frequently the number of iterations grows. Our analysis shows that this can achieve an error that scales 1/(NT) with number of communications that is completely independent Tf T In particular, we show that ((N) communications are sufficient. Empirical evidence suggests this bound is close to tight as we further show that VN or 3//4 communications fail achieve linear speed-up in simulations. Moreover, we show that under mild assumptions, the main of which is twice differentiability on any neighborhood of the optimal solution, one-shot averaging which only uses single round of communication can also achieve the optimal convergence rate asymptotically.
1 Introduction
Stochastic Gradient Descent (SGD) is widely used algorithm minimize convex functions f in which model parameters are updated iteratively
x++ = g
where g is stochastic gradient of the point x' and n is the learning rate. This algorithm be naively parallelized by adding more workers independently to compute a gradient and then average
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

them at each step to reduce the variance in estimation of the true gradient fx(x') (Dekel et al., 2012). This method requires each worker to share their computed gradients with each other at every iteration. We will refer to this method as "synchronized parallel SGD."
However, it is widely acknowledged that communication is a major bottleneck of this method for large scale optimization applications (McMahan et al., 2017; Konečný et al., 2016; Lin et al., 2018b), Often, mini-batch parallel SGD suggested to address this issue by increasing the computation to communication ratio. Nonetheless, too large mini-batch size might degrade performance (Lin et al., 201 8a). Along the same lines of increasing the computation over communication effort, local SGD has been proposed to reduce communications (McMahan et al., 2017: Dieuleveut, Patel, 2019). In this method, workers compute (stochastic) gradients and update their parameters locally, and communicate only once in while to obtain the average of their parameters, Local SGD improves the communication efficiency not only by reducing the number of communication rounds, but also alleviates the synchronization delay caused by waiting for slow workers and evens out the variations in workers' computing time (Wang, Joshi, 2018b).
On the other hand, since individual gradients of each worker are calculated at different points, this method introduces residual error as opposed fully synchronized SGD. Therefore, there is a trade- off between having fewer communication rounds and introducing additional errors to the gradient estimates.
The idea of making local updates is not new and has been used in practice for a while (Mangasarian, 1995; Konečný et al., 2016). However, until recently, there have been few successful efforts to analyze Local SGD) theoretically and therefore it is not fully understood yet. Zhang et al. (2016) show that for quadratic functions, when the variance of the noise is higher far from the optimum, frequent averaging leads to faster convergence. The first question we try to answer in this work is: how many communication rounds are needed for Local SGD to have the similar convergence rate of a synchronized parallel SGD while achieving performance that linearly improves in the number of workers?
Stich (2019) was among the first who sought to answer this question for general strongly convex and smooth functions and showed that the communication rounds can be reduced up to factor of H ((VT/N,, without affecting the asymptotic convergence rate (up constant factors), where T is the total number of iterations and N is number of parallel workers.
Focusing on smooth and possibly non-convex functions which satisfy a Polyak-Lojasiewice condition, Haddadpour et al. (2019) demonstrate that only R = ((TTN) communication rounds are sufficient achieve asymptotic performance that scales proportionately to 1/N.
Recently, Khaled et al. (2020) and Stich, Karimireddy (2019) improve upon the previous works by showing linear speed-up for Local SGD with only 2 (N poly log (T)) communication rounds when data is identically distributed among workers and f is strongly convex. Their works also consider the cases when f is not necessarily strongly convex as well the case of data being heterogeneously distributed among workers.
More recently, Yuan, Ma (2020) proposed new accelerated method that requires only Ω (N1 poly log (T)) communication rounds for linear speed-up- While their results improve upon the earlier work, the communication requirements remain dependent on the total iterations T.
One-Shot Averaging (OSA), a method that takes an extreme approach to reducing communication, involves workers performing local updates until the very end when they average their parameters (Mcdonald et al., 2009; Zinkevich et al., 2010; Zhang et al., 2013c; Rosenblatt, Nadler, 2016; Saadane, 2020). This method can be seen as an extreme case of Local SGD with R = and H- = T local steps. Dieuleveut, Patel (2019); Godichon- Baggioni, Saadane (2020) provide an analysis of OSA and show that asymptotically, linear speed-up in the number of workers is achieved for a weighted average of iterates. However, both of these works make restrictive assumptions such as uniformly three-times continuously differentiability and bounded second and third derivatives or twice differentiability almost everywhere with bounded Hessian, respectively. The second question we attempt to answer this work, is whether these assumptions can be relaxed and OSA can achieve linear speed-up in more general scenarios.
Modichon-Baggiones
Godichon-Baggioni,
In this work, we focus on smooth and strongly convex functions with general noise model. Our contributions are three-fold:
2

---

Table Comparison of Similar Works
Convergence rate
Communication Rounds R
Noise model
Reference
f(x")
Stich (2019)
((vTN)
uniform
PNT
Haddadpour et al. (2019)
0
2
(((TN))/))
uniform with
PNTR
stronggrrowhh
Stich, Karimireddy (2019)
exp. decay
g² JNT
R(N poly T))
uniform with
strong-growth
Woodworth et al. (2020)
exp. decay +
J.T
_a
no logi9+T//M I/s)
9(N poly(log 7')
uniform
Khaled et al. (2020)
no? RNT
u²a²
A(N * poly(log 7')
uniform
NTR
Yuan, Ma (2020)
exp. decay + KNT
o²
PTT
x²
INN poly(log
uniform
This Paper
LLoc --
R(N)
uniform with strong groggg
PAT
PTR
Depending the work, x* is either the last iterate weighted average of iterates up to T. is the uniform upper bound assumed for the l2 norm of gradients in the corresponding work.
This noise model is defined in Assumption 5.
O.) ignores the poly-logarithmic and constant factors.
This is the bound for FedAC-II FedAC-I requires R Q(N * poly(log T)).
c is the multiplicative factor in the noise model defined in Assumption
We propose a communication strategy which requires only R = (?(N) communication rounds to achieve performance that scales as 1/N in the number of workers. To the best of the authors' knowledge, this the only work to show that the number of communications be taken to be completely independent of T. All previous papers required number communications which was at least N times a polynomial in log(T) or had a stronger scaling with T. A comparison of our result the available literature can be found in Table 1.
2. We show under mild additional assumptions, in particular twice differentiability on neighborhood of the optimal point, OSA reaches linear speed-up asymptotically, i.c., with only one communication round we achieve the convergence rate of (L/(TT))
3. We simulate a simple example which is not twice differentiable at the optimum and observe that our bounds for part 1. are reasonably close to being tight. In particular, using 1 or / N or N3/4 communications does not appear to result in a linear speed-up in the number of workers (while N communications does give linear speed-up).
We notice that FedAC (Yuan, Ma, 2020) has better dependence the number of workers N, in expense (poly logarithmic) dependence on T. With that in mind, we still believe our communication strategy is of independent interest, particularly in the framework of non-accelerated methods. We have performed extensive numerical experiments and comparisons between the two methods and highlighted the regimes where each method outperforms the other.
is worth mentioning that although the the communication complexity by Woodworth et al. (2020) depends T, their bound has lower dependence condition number K. Hence, their results are stronger than ours only when A = 2(log T').
The rest of this paper is organized as follows. In the following subsection we outline the related literature and ongoing works. Section 2 we define the main problem and state our assumptions. We present our theoretical findings in Section 3 followed by numerical experiments in Section 4 and conclusion remarks Section 5.
1.1 Related work
There has been lot of effort in the recent research to take into account the communication delays and training time in designing faster algorithms (McDonald al., 2010: Zhang et al., 2015; Bijral et al., 2016; Kairouz et al., 2019). See (Tang et al., 2020) for comprehensive survey of commu-

---

nication efficient distributed training algorithms considering both system-level and algorithm-level optimizations.
Many works study the communication complexity of distributed methods for convex optimization (Arjevani, Shamir, 2015; Woodworth al., 2020) and statistical estimation (Zhang et al., 2013b). Woodworth et al. (2020) present a rigorous comparison of Local SGD with / local steps and mini- batch SGD with I/ times larger mini-batch size and the same number of communication rounds (we will refer to such a method as large mini-batch SGD) and show regimes in which each algorithm performs better: they show that Local SGD is strictly better than large mini-batch SGD when the functions are quadratic. Moreover, they prove lower bound on the worst case of Local SGD that is higher than the worst-case error of large study the minimum amount of communication required to achieve centralized minimax-optimal rates by establishing lower bounds on minimax risks for distributed statistical estimation under a communication budget.
SGD in a certain regime. Zhang et al. (2013b)
parallel line of work studies the convergence of Local SGD with non-convex functions Zhou, Cong (2018). Yu et al. (2019) was among the first works to present provable guarantees of Local SGD with linear speed-up. Wang. Joshi (2018b) and Koloskova al. (2020) present unified frameworks for analyzing decentralized SGD with local updates, elastic averaging or changing topology. The follow-up work of Wang. Joshi (2018a) presents ADACOMM, an adaptive communication strategy that starts with infrequent averaging and then increases the communication frequency in order to achieve a low error floor. They analyze the error-runtime trade-off of Local SGD with nonconvex functions and propose communication times to achieve faster runtime.
Another line of work reduces the communication by compressing the gradients and hence limiting the number of bits transmitted in every message between workers (Lin et al., 2018b; Alistarh et al., 2017; Wangni al., 2018; Stich et al., 2018; Stich, Karimireddy, 2019).
Asynchronous methods have been studied widely due to their advantages over synchronized methods which suffer from synchronization delays due to the slower workers (Spiridonoff et al., 2020). Wang et al. (2019) study the curor-runtime trade-off in decentralized optimization and proposes MATCHA, an algorithm which parallelizes inter-node communication by decomposing the topology into matchings. However, these methods are relatively more involved and they often require full knowledge of the network, solving a semi-definite program and/or calculating communication probabilities (schedules) as in Hendrikx et al. (2019).
The homogeneous data assumption. In this work, we focus on the case when the data distribution is the same across workers. A number of previous works (Khaled et al., 2020; Haddadpour et al., 2019: Stich, 2019; Dieuleveut, Patel, 2019) studied local SGD under this assumption. The assumption is valid when the same data set is either shared across multiple workers in the same cluster, or the assignment of data points to workers is random so that any distributional diffcrences are small. Sharing the data set across multiple workers in this way is popular strategy speed up training. For example, such data sharing is implemented in (Chen et al., 2012: Yadan et al., 2013; Zhang et al., 2013a) speed up training of deep neural networks with multiple GPUs within single server. While there are many widely used mechanisms such as Horovod (Sergeev, Del Balso, 2018) for synchronous data-parallel distributed training, they share major communication bottleneck of broadcasting gradients to all workers (Grubic et al., 2018). Local SGD improves on these methods by reducing the communication of model parameters from every iteration smaller number of rounds during the entire optimization process. Our approach further reduces the communication overhead by communicating less the number of iterations grows
1.2 Notation
For positive integer 8, we define [=]:= {1, s8......). s}. We use bold letters to represent vectors. We denote vectors of all Os and 1s by 0 and 1, respectively. We use || for the Fuclidean norm of vector and spectral norm of matrix. Finally, (u,, o²) denotes a normal distribution with mean jr and variance o².

---

2 Problem formulation
Suppose there are N workers V (1, (1,..., N), trying minimize IRd - IR in parallel. We assume all workers have access to f through noisy gradients. In Local SGD, workers perform local gradient steps and occasionally calculate the average of all workers' iterates. Each worker holds local parameter x at iteration t. There is a set I C [I] of communication times and nodes perform the following update:
m (x) ng),
i 1 I if lee,
where g is an unbiased stochastic gradient of f at xt. When I [2]. we recover fully synchronized parallel SGD while I = } recovers one-shot averaging, Pseudo-code for Local SGD is provided Algorithm
Algorithm Local SGD
1: Input: x x0 for all E [n]. total number of iterations T, the step-size sequence (m T and
I C [7]]
2: for = ................................ T do
3: for j NN... do
4:
evaluate stochastic gradient gj
5:
if + 1 then
6:
x
Σ (x m7:8.
N
7:
else
8:
x
= x3 -n:8)
9:
end if
10:
end for
11:
end for
Next state the assumptions that we will use in results. Note that will not require all of them to hold at once.
Assumption 1 (smoothness). The function f Rdd IR is continuously differentiable and its gradients are L-Lippchitz i.e.,
[V V T||x yll:
Vx,y.
Assumption 2 (strong convexity). f is ju-strongly convex with μ 0, iee,
f(x) ggy x) + - xx f(y), Vx,y E R E 0f(x),
where (x) denotes the set of subgradients of f at When f is also continuously differentiable, 0f(x) = {x)()))
Note that when f satisfies Assumption 2, it has unique optimal point x* where f(x") = where f = minx (xx Assumption 3 Looasa--oo condition). f is P-Poolya--Lohsseviiii PL short) if |V 2 2x(f(x)) - f²), Vx.
where f ming f(x) the global minimum of f. We further assume that has unique optimal point x" where f(x") f
When f satisfies both Assumptions and or Assumptions 1 and 3, we define k L/j as the condition number f.
Strong convexity implies the PL condition but the reverse does not always hold. For instance, the logistic regression loss function satisfies the PL condition over any compact set (Karimi et al., 2016). In fact, PL function is not even necessarily convex. Charles, Papailiopoulos (2018) show that deep networks with linear activation functions are PL almost everywhere the parameter space. Allen-Zhu et al. (2018) show, with high probability over random initializations, that sufficiently wide recurrent neural networks satisfy the PI. condition. Therefore, the condition more applicable, especially in the context of neural networks (Madden et al., 2020).
5

---

Assumption 4 (twice differentiability at the optimum), f is twice continuously differentiable on an open set containing the optimal point x".
We make the following assumption on the noise stochastic gradients, using w = gi V - fx{) to denote the difference between the stochastic and true gradients.
Assumption 5 (uniform with strong-growth noise). Conditioned on the iterate x3, the random variable w is zero-mean and independent with its expected squared norm error bounded as,
[|[l | [x]] S 11
where ,², O are constants.
The noise model of Assumption 5 is very general and it includes the common case with uniformly bounded squared norm error when c = 0. As it is noted by Zhang et al. (2016), the advantage of periodic averaging compared to one-shot averaging only appears when c/ is large. Therefore, to study Local SGD, it is important to consider noise model as in Assumption 5 to capture the effects of frequent averaging. Among the related works mentioned in Table 1, only Stich, Karimireddy (2019) and Haddadpour et al. (2019) analyze this noise model while the rest study the special case with O. SGD under this noise model with 0 and o² O was first studied in Schmidt, Roux (2013) under the name strong growth condition. Therefore we refer to the noise model considered in this work uniform with strong strong-growth,
Assumption 6 (sub-Gaussian noise). Conditioned on the iterate x/, random variable w² is zero-mean, independent and [w]]r is (a/v (al)-s---Gasssinnn for I = 1,.... d, i.e.
A²
[lex)(A([w:]] B[w!ld)]< S exp
WE d.
2d
Thus, it has uniformly bounded variance [|[[ [2 S 5
sub-Gart Gaussian noise model is commonly assumed for deriving concentration bounds for SGD, which we will prove our results for OSA.
As already mentioned in the Introduction, the main goal of this paper to study the effect of communication times on the convergence of the Local SGD and provide better theoretical guarantees. In what follows, we claim that by carefully choosing the communication times, linear speed-up of parallel SGD can be attained with only small number of communication instances. Moreover, we will obtain a set of sufficient conditions for OSA to achieve linear speed-up.
Convergence results
In this section we present our main convergence results for Local SGD and OSA. In what follows, denote by x = f x xt)/N the average of the iterates of all workers. Notice that x xf for t e and I....,N..
3.1 Local SGD
Let us introduce the notation
0 To < T1 ... < <TR T
for the communication times. Further, let us define H, = T,+1 - Tu to be the i'th interc- communication interval. Our first theorem gives performance bound under the assumption that H; grows linearly with i.
Theorem 1. Suppose Assumptions I (smoothness), 2 (strong convexity) and 5 (uniform with strong growth noise) hold.
Choose the parameters as follows: R such that < R < /2T and := [2 1, H; = a(i+1) and Ts+1 = min(T; + H,,T)) for O....,R R R-1 1. Choose 3 2 max 9k. 12x² mmn (/(Ax²²)) - 3x(1 c/N)} and set the learning rate as πi 3/ + 3), = 0, 0.
Then using Algorithm / we have,
82(f(x)) -
9L0² 144L2
[x 8
+
T
NT

---

Corrollary 1. Under the assumptions of Theorem 1, selecting the number of communications R ((KN) we obtain
- ((((*) - M*) +o T
L p2NT)
The choice of communication times in Theorem aligns with the intuition that workers need to communicate more frequently at the begimning of the optimization. As the the step-sizes become smaller and workers' local parameters get closer the global minimum, they diverge more slowly from each other and therefore, less communication is required to re-align them. The advantage of this communication strategy over fixed periodic averaging has been only empirically shown in Haddadpour et al. (2019). The proof of Theorem can be found in Appendix B.
3.2 One-shot averaging
The previous literature literature has shown OSA achieves asymptotic linear speed-up under some restrictive assumptions. For instance, Dieuleveut, Patel (2019) show this for three times continuously differentiable functions with second and third uniformly bounded derivatives. Similarly, Godichon- Baggioni, Saadane (2020) require the objective function to be strongly convex, twice continuously differentiable almost everywhere, with a bounded Hessian everywhere and gradients satisfying the following condition for some constant C. and all x E IRd
Vf(x) - fxxxx) x')] S
This inequality is similar to the assumption from Dieuleveut, Patel (2019) of uniformly bounded third derivatives. In the following theorem, we relax these assumptions and show that OSA achieves linear speed-up under considerably milder assumptions.
Before proceeding, let us define the step-size sequence {0r) as
for t 0, to
0.
L:
2t m(t+1)=
for 2 fo.
where to [2L/u]. Notice that 0, S 1/L for all t. Theorem 2. Under Assumptions I (smoothness), (PL condition), (twice differentiability at the optimum) and (sub-Gaussian noise) and with step-size sequence {me {0,} defined in (2), have for to.
402
E
T
NT
We thus able relax the conditions from the earlier literature, which required everywhere or almost everywhere higher derivatives with uniform bounds on third derivatives to merely twice differentiability single point. As a bonus, also replace strong convexity with the PL condition.
This thcorem is proved in Appendix C. The main difference between Theorem and Corollary is that Theorem 2 shows linear speed-up with only communication round but with slightly more restrictive assumptions such as sub-Gi Sabb-aassiin noise model and wwice-differentie objective function the optimal point. On the other hand, results for OSA only require the PL-condition instead of strong convexity.
Numerical experiments
To verify our findings and compare different communication strategies in Local SGD, performed the following numerical experiments, using an Nvidia GTX-1060 GPU and Intel Core i7-7700k processor.
4.1 Quadratic function with strong-growth condition
As discussed Zhang al. (2016); Dieuleveut, Patel (2019), under uniformly bounded variance, one- shot averaging performs asymptotically as well mini-batch SGD, at least for quadratic functions.

---

Sytrhoneee 5613
Syndronou 5CD
21m (2012))
19019
Z1 26 BIOUCII
12
A. 60 (Thi Paper
42 11 Maperi Fim 50 (7700
Hi 50 (1W)
10"
N1 (OGA)
Nin (004))
0/001-
10
10
-00
300
10"
10'
Reration 17)
Communiction soand
(a) Error over iteration.
(b) Ertor over communication round.
Figure I: Minimizing (3) using Local SGD with different communication strategies. Figures (a) and (b) show the error over iteration and communication rounds, respectively.
Therefore, to fully capture the importance of the choice of communication times I, we design a hard problem, where noise variance uniform with strong-grows condition, defined in Assumption Let us define,
F(x) = BcX(x,)),
((x,))= = Σ 22 (1 + 21,1) + 22.
2 1=1
where (= (=(z), (2) and 21, 22 E Rd 21, ~ (N. ci) and 22,1 ~ NoO, 62), Vi E [d]. are random variables with normal distributions. We assume each iteration I,, each worker samples Ç and uses Vf((, ) as a stochastic estimate of (x). It is easy to verify that F(x) is 1-strongly convex and EellV () [F())] v + o², where c c1 and
and d-smooth, F
²² do2.
We use Local SGD to minimize F(x) using different communication strategies, namely, synchronized
SGD where = 1, H se VTN Stich (2019), H z (/3 Haddadpour et al. (2019), R = with constant / R= T/N Stich, Karimireddy (2019); Khaled et al. (2020) and finally the communication strategy proposed in this work with R = and linearly growing H, local steps. We used = 20 workers, T 1000 iterations, C₁ 1.0 and 02 10-10 with = 3 and step-size sequence ? = 3/3(((tt + 1)). To estimate the expected value of errors, we repeated the optimization using each strategy 100 times and reported the average and --standard-deviatee error bar in Figure 1.
We make the following observations from Figure
Figure ((a) shows that communication strategy with increasing local steps (proposed in this work), outperforms the other methods, both in transient and final error performance, specifically the one with the same number of communication rounds evenly spread through- out the whole optimization. This confirms the advantage of more frequent communication at the beginning of the optimization, especially when the ratio of o² in the noise with growth condition is large (see the definition in Assumption 5).
Figure (bb shows that our communication method uses fewer communication rounds, 20 versus 28 (Haddadpour al., 2019), 143 (Stich, 2019) and 1000 rounds for synchronized SGD.
OSA appears to perform relatively well despite using only one communication round, though not quite as well as other methods. This shows that the choice of communication important in this experiment. In other words, it is not true that the success of our communication strategy is merely a byproduct of the experiment design, where any communication strategy, long it communicates at least once, will succeed.

---

30
140
Synchronaus SGD
A N. increasing H
25
N1 increasing
120
N, constant
N. constant H
N increasing
(OSA)
100
Ni consonnt
20
A NAi, Increasing
Speed-up
Spend-up
A 1 (OSA)
15
60
10
0
012
4
8
16 24
32
0
32 64
126
192 256
Number
Number
(a)
(b)
Figure 2: Speed-up curves for different communication strategies, over different ranges of N and T. Figure (a) establishes the linear speed-up of local SGD with A = .N communication rounds as well as failure of OSA achieve speed-up up even with small number of workers N S over 1000 iterations. Figure (b) additionally plots speed-up curves for R Rs N3/4 and R N1/2 for larger values of 32 < N < 256 and T 8000.
4.2 Speed-up curves
In this experiment, we minimize a nneedimensional function defined as,
1 x²
S 0, 0,
F(x)
(4)
using Local SGD with gradients corrupted by normal noise A( o?). We chose this specific cost function since is not twice continuously differentiable at the minimizer satisfy Assumption 4 required by Theorem 2 for OSA to achieve linear speed-up. The results of this experiment will help us understand whether twice differentiability necessary assumption for OSA to obtain linear speed-up.
and does not
The speed-up curve is derived by dividing the expected error of a single worker SGD by the expected error of each method at the final iterate T, over different number of workers N. Thus in the case where the error decreases linearly in the number of workers, we should expect see straight line on the graph.
We plot the speed-up curve for N workers using different communication strategics: synchronized SGD, R = communication rounds with linearly increasing number of local steps H,, = with constant number of local steps H T/R, well as OSA with only R communication the end. We use the step-size sequence 7) = min 2 2/(((t + 1))) with μ = 1, = 2, and o 8, T = 1000.
Our results in Figure 2(a) show that Local SGD with = (increasing or constant H) achieves linear speed-up in the number of workers, albeit with worse constant compared to synchronized SGD, However, OSA fails to scale as increases. This suggests that the condition of twice differentiability (Assumption 4) is necessary for Theorem 2, as this function satisfies all the other assumptions of that theorem.
While our theoretical results provide only an upper bound on R to achieve linear speed-up, this setting gives us a chance to find out if smaller number of communication rounds are enough. Therefore we repeat this experiment for larger number of workers N and T 8000, using It R N3/4 and R N1/2 communication rounds. Our results in Figure 2(b) show that R N clearly achieves speed-up for larger values of N, expected and R and R xs 1/2 fail speed-up. However, R = 33/4 also struggles to linearly speed-up in the number of workers, as the slope of the speed-up curve declines with N increasing. It would be of interest to look into a more granular choice of communication rounds such as R ss No.9 or even R as N7.99 but this would require much larger values of N and and thus more repeated simulations, which beyond our computational resources. which were already exhausted by generating Figure 2(b).

---

It is worth mentioning that in both experiments of Figure 2(a) and 2(b). R = N with increasing H outperforms the one with constant H, even though the noise model used this experiment is simply uniformly bounded, without strong-growe growth condition. This further endorses the use of more frequent averaging at the beginning of optimization, when paired with decreasing step-size sequence.
4.3 Regularized logistic regression
We also performed additional numerical experiments with regularized logistic regression using two large real datasets: (i) national dataset (NSQIP) of surgeries performed in the U.S., seeking to predict short-term hospital re-admissions, which consists of 722101 data points (surgeries) each characterized by d 231 features, (ii) the a9a dataset from LIBSVM (Chang, Lin, 201 I) which includes 32561 data points with d = 124 features. The results of these experiments are presented and discussed in Appendix
Conclusion
In this work, studied the communication complexity of Local SGD and provided analysis that shows that = (2NN number of communication rounds, independent of the total number of iterations T, is sufficient to achieve linear speed-up. Moreover, we showed only single round of averaging is needed provided that the objective twice differentiable at the optimum point. This assumption appears be necessary.
simulations show that not only one-shot averaging but using 1/2 or 33/4 communications in local SGD fails deliver linear speed-up simple example which is not twice differentiable at the optimum.
10

---

Acknowledgments and Disclosure of Funding
The research was partially supported by the NSF under grants DMS- 16641664644, CNS- ECCS- 1933027 and IIS-1914792, by the ONR under grants N00014-19-1-2571 and N00014-21-1-2844, by the ARO under grant INF------, by the NIH under grants RO1 GM135930 and UL54 TR004130, by the DOE under grants DE-AR-0001282 and NETL-EE0000966, and by the Boston University Kilachand Fund for Integrated Life Science and Engineering.
References
Alistarh Dan. Grubic Demjan, Li Jerry, Tomioka Ryota, Vojnovic Milan. QSGD: Communication efficient SGD via gradient quantization and encoding // Advances in Neural Information Processing Systems. 2017. 1709-1720.
Allen-Zhu Zeyuan, Yuanzhi, Song Zhao. On the convergence rate of training recurrent neural networks // arXiv preprint arXiv: 180..12065. 2018.
Arjevani Yossi, Shamir Ohad. Communication complexity of distributed convex learning and optimization // Advances in neural information processing systems. 2015. 1756-1764.
Beck Amir. Introduction to nonlinear optimization: Theory, algorithms, and applications with MATLAB. 2014.
Bijral Avleen S, Sarwate Anand D, Srebro Nathan. On data dependence in distributed stochastic optimization // arXiv preprint NTt.:16003043777 2016.
Chang Chih-Chung, Lin Chih-Jen. LIBSVM: A library for support vector machines // ACM Transactions on Intelligent Systems and Technology. 2011. 2. 27:1-27:27. Software available at http:/ //www//wwwwwaaaa/ csie ntu, edu. tw/ htt///cliinnnieeee
Charles Zachary, Papailiopoulos Dimitris. Stability and generalization of learning algorithms that converge to global optima // International Conference on Machine Learning. 2018. 745-754.
Chen Xie, Eversole Adam, Gang, Yu Dong. Seide Frank. Pipelined back bock-propagation for context- dependent deep neural networks // Thirteenth Annual Conference of the International Speech Communication Association. 2012.
Dekel Ofer, Gilad-Bachrace Ran, Shamir Ohad, Xiao Lin. Optimal distributed online prediction using mini-batches // Journal Machine Learning Research. 2012. 13, Jan. 165-202.
Dieuleveut Aymeric, Patel Kumar Kshitij. Communication trade-off's for Local-SGD with large step size Advances in Neural Information Processing Systems. 2019. 13579-13590.
Godichon-Bagee Baggioni Antoine, Saadane Sofiane. On the rates of convergence of parallelized averaged stochastic gradient algorithms // Statistics. 2020. 54,3, 3. 618-635.
Grubic Demjan, Tam Leo K, Alistarh Dan, Zhang Ce. Synchronous multi-gp gpu deep learning with low-precision communication: An experimental study // Proceedings of the 2 International Conference on Extending Database Technology. 2018. 145-156.
Haddadpour Farzin, Kamani Mohammad Mahdi, Mahdavi Mehrdad, Cadambe Viveck. Local SGD with periodic averaging: Tighter analysis and adaptive synchronization // Advances in Neural Information Processing Systems. 2019. 11080-11092.
Hendrikx Hadrien, Bach Francis, Massoulié Laurent. An accelerated decentralized stochastic proximal algorithm for finite sums // Advances in Neural Information Processing Systems. 2019, 952-962.
Kairouz Peter, McMahan H Brendan, Avent Brendan, Bellet Aurélien, Bennis Mehdi, Bhagoji Ar- jun Nitin, Bonawitz Keith, Charles Zachary, Cormode Graham, Cummings Rachel, others. Ad- vances and open problems in federated learning If arXiv preprint
2019.
11

---

Karimi Hamed, Nutini Julie, Schmiddt Mark. Linear convergence of gradient and proximal-gradient methods under the polyak-tojasiewiez condition // Joint European Conference on Machine Learning and Knowledge Discovery in Databases. 2016. 795-811.
Khaled A, Mishchenko K, Richtárik P. Tighter theory for local SGD on identical and heterogeneous data // The 23rd International Conference on Artificial Intelligence and Statistics (AISTATS 2020).
2020.
Koloskova Anastasia, Loizou Nicolas, Boreiri Sadra, Jaggi Martin, Stich Sebastian U. A Unified Theory of Decentralized SGD with Changing Topology and Local Updates // arXiv preprint arXiv:2003. 10422.. 2020.
Konečný Jakub, McMahun H Brendan, Yu Felix X, Richtárik Peter, Suresh Ananda Theertha, Bacon Dave. Federated learning: Strategies for improving communication efficiency // arXiv preprint arXiv:1610.05492. 2016.
Lin Tao. Stich Sebastian U, Patel Kumar Kshitij. Jaggi Martin. Don't Use Large Sini-Batches, Use Local SGD // arXiv preprint EEXiv:180..072) 2018a.
Lin Yujun, Han Song, Mao Huizi, Wang Yu, Dally Bill. Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training // International Conference on Learning Representations. 2018b.
Madden Liam, Dall' Anese Emiliano, Becker Stephen. High probability convergence and uniform stability bounds for nonconvex stochastic gradient descent // arXiv preprint arXiv:2006.05610. 2020.
Mangusarian LO. Parallel gradient distribution in unconstrained optimization // SIAM Journal on Control and Optimization. 1995. 33, 6. 1916-1925.
McDonald Ryan, Hall Keith, Mann Gideon. Distributed training strategies for the structured percep- tron // Human language technologies: The 2010 annual conference of the North American chapter of the association for computational linguistics. 2010. 45644566666
McMahan Brendan, Moore Eider, Ramage Daniel, Hampson Seth, Arcas Blaise Aguera y. Communication Efficcien Learning of Deep Networks from Decentralized Data Artificial Intelligence and Statistics. 2017. 1273-1282.
Medonald Ryan, Mohri Mehryar, Silberman Nathan, Walker Dan, Mann Gideon S. Efficient large- scale distributed training of conditional maximum entropy models // Advances in neural information processing systems. 2009. 1231-1239.
Rosenblatt Jonathan D, Nadler Boaz. On the optimality of averaging in distributed statistical learning Information and Inference: A Journal of the IMA. 2016. 4. 379.404.
Schmidt Mark, Roux Nicolas Le. Fast convergence of stochastic gradient descent under strong growth condition // arXiv preprint arXiv: 1308.6370. 2013.
Sergeev Alexander, Del Balso Mike. Horovod: fast and easy distributed deep learning in TensorFlow || arXiv preprint arXiv: Ntt.:1802.00799. 2018.
Spiridonoff Artin, Olshevsky Alex, Paschalidis loannis Ch. Robust asynchronous stochastic gradient- push: asymptotically optimal and network-independen performance for strongly convex functions Journal of Machine Learning Research. 2020.
Stich Sebastian U. Local SGD Converges Fast and Communicates Little // International Conference on Learning Representations, 2019.
Stich Sebastian U, Cordonnier Jean-Baptiste, Jaggi Martin. Sparsified SGD with memory // Advances in Neural Information Processing Systems. 2018. 4447-4458.
Stich Sebastian U, Karimireddy Sai Praneeth. The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication // arXiv preprint arXiv:1909.05333 2019.
12

---

Tang Zhenheng, Shi Shaohuai, Chu Xiaowen, Wang Wei, Li Bo. Communication-Efiice Distributed Deep Learning: A Comprehensive Survey // arxiv preprint arXiv:2003.06307, 2020.
Wang Jianyu, Joshi Gauri. Adaptive communication strategies to achieve the best error-runtime trade-off in local-update SGD // Systems for ML. 2018a.
Wang Jianyu, Joshi Gauri. Cooperative SGD: A unified framework for the design and analysis of SGD algorithms // arXiv preprint arXiv:1808.07 00756.. 2018b.
communication-
Wang Jianyu, Sahu Anit Kumar, Yang Zhouyi, Joshi Gauri, Kar Soummya. MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling // arXiv preprint arXiv: 1eXXiv11005000 1905.09435. 2019.
Wangni Jianqiao. Wang Jialei, Liu Ji. Zhang Tong. Gradient sparsification for communication efficient distributed optimization // Advances Neural Information Processing Systems. 2018. 1299-1309.
Woodworth Blake. Patel Kumar Kshitij. Stich Sebastian U. Dai Zhen, Bullins Brian, McMahan H Brendan, Shamir Ohad, Srebro Nathan. Is Local SGD Better than Minibatch SGD? // arv preprint uXXiv:2002.078399 2020.
Yadan Omry, Adams Keith, Taigman Yaniv, Ranzato Marc'Aurelio. Multi-gpu training of convnets // arXiv preprint arXiv: 1312.5853. 2013.
Yu Hao, Yang Sen, Zhu Shenghuo. Parallel restarted SGD with faster convergence and less communi- cation: Demystifying why model averaging works for deep learning // Proceedings of the AAAI Conference on Artificial Intelligence. 33. 2019. 5693-5700.
Yuan Honglin, Ma Tengyu. Federated Accelerated Stochastic Gradient Descent // Advances in Neural Information Processing Systems. 33. 2020. 5332-5344.
Zhang Jian, De Sa Christopher, Mitliagkas loannis, Ré Christopher. Parallel SGD: When does averaging help? // arXiv preprint 1xXiv:1606003665 2016.
Zhang Shanshan, Zhang Ce, You Zhao, Zheng Rong, Xu Bo. Asynchronous stochastic gradient descent for DNN training // 2013 IEEE International Conference on Acoustics, Speech and Signal Processing. 2013a. 6660-6663.
Zhang Sixin, Choromanska Anna E, LeCun Yann. Deep learning with elastic averaging SGD Advances in neural information processing systems. 2015. 685 6633.
Zhang Yuchen, Duchi John, Jordan Michael I, Wainwright Martin J. Information-theoreii lower bounds for distributed statistical estimation with communication constraints // Advances in Neural Information Processing Systems. 2013b. 2328-2336.
Zhang Yuchen, Duchi John C, Waimwright Martin J. Communication-effiient algorithms for statistical optimization // Journal of Machine Learning Research, 2013c. 14, 1. 3321-3363.
Zhou Fan, Cong Guojing. On the convergence properties of a K-step averaging stochastic gradient descent algorithm for nonconvex optimization // Proceedings of the 27th International Joint Conference on Artificial Intelligence. 2018. 3219-3227.
Zinkevich Martin, Weiner Markus, Li Lihong, Smola Alex J. Parallelized stochastic gradient descent Advances in neural information processing systems. 2010. 2595-2603.
13

---

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] See Appendix
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
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 in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) 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 to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "K3Do4M8FSlk", "reviewer": "Reviewer_d1us", "summary": "This paper investigates the gap between local SGD and One-Shot averaging in communication efficacy and linear speed-up with respect to the number of workers. Through extensive analysis, they show that they can tighten the bound for the number of communication required for local SGD to $\\Omega\\left(N\\right)$, which is the number of workers. They have proved this bound for strongly convex and objectives with PL condition, where the strong convexity can be a special case of it. They use the idea of adaptive local step to have a more frequent communication at the beginning of the training and less frequent one at the end. In their experimental section, they show that their proposal can converge to the same rate as other local SGD approaches and Sync SGD using  $\\Omega\\left(N\\right)$ communication rounds.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "This paper bridges the gap from the local SGD and one-shot averaging to tighten the communication bound required for linear speed-up in local SGD. They are using heuristic ideas from Haddadpour et al. (2019) to use an adaptive and increasing number of iterations for each round of communication. Their theoretical analysis proves the effectiveness of this approach for strongly convex and PL-condition objectives. From the theoretical perspective, the contribution of this paper is important for tightening the bounds on the number of communication rounds required for linear speed-up, and hence it is a significant improvement over the previous works in this domain. The claims of the paper are clear and the comparison with other SOTA methods in this domain is fair. The empirical results are consistent with the theoretical results claimed in the paper and show the effectiveness of the proposed approach. I have some questions regarding the claims in the paper:\n\n1. Although the theoretical results are focused on strongly convex and PL-condition objectives. However, I would like to know how this approach would work in non-convex objectives using local SGD.\n 2. The theoretical results are mainly based on the adaptive local step sizes, however, in practice the difference between adaptive and non-adaptive cases are marginal. Could you please explain the difference and the significance of the adaptive local step?\n3. How does the value of $a$ is decided? Are there any theoretical bounds on the size of local steps for this algorithm?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not think that this will be applied to this paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "HG6F_AHCWtP", "reviewer": "Reviewer_ReEQ", "summary": "In this paper, the authors study the theoretical speedup of local SGD and one-shot averaging. A synchronization scheme that communicates more frequently at the beginning is also suggested. Some simple numerical experiments are provided to verify the theoretical results.", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "The paper is well-written. I recommend highlighting the communication scheme in Theorem 1 by putting it into a standalone definition, which will make it more friendly to the readers. \nThis paper focuses on the theoretical analysis of the speedup of local SGD and one-shot averaging, and provides some improved results compared to the previous work. \nSome typos: line 140: sever -> server\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1. This paper uses the homogeneous data assumption. However, most of the recent deep-learning applications require non-iid settings, especially for large-scale problems where communication reduction via local SGD is more useful. Since the results of this paper only applies to the iid cases, such results are less useful in practical work.\n2. Some strong assumptions such as strong convexity or PL condition are used. It will be more interesting to have the theoretical results under the assumption of smoothness without strong convexity or PL.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Df76kz7aAHG", "reviewer": "Reviewer_7aRm", "summary": "## Update after rebuttall\n\nI am satisfied with the authors' response and elevate my score to 6.\n\n##\n\nThis paper presents several new theoretical results on the convergence of Local SGD as well as numerical experiments to check the tightness of the theory. In particular, the authors try and remove logarithmic terms from the bounds of Local SGD by making the communication less frequent as the iteration counter increases. The main results of the paper are:\n\n1. Theorem 1 gives convergence for strongly convex functions under uniform-with-strong-growth noise. I argue in my detailed review that this result looks suboptimal.\n\n2. Theorem 2 gives a result for PL functions with sub-Gaussian noise for one-shot averaging. This result is interesting as it promises a linear speed-up, although under somewhat restrictive assumptions. \n\n3. The experiments show that linear speed-up is lost when the number of communication rounds is chosen smaller than predicted by the theory of Theorem 1.\n\nI tend to vote for rejection of this work, even though I appreciate some of the results obtained here. My main concerns are 1) applicability of the message to neural network training, which is highly relevant to FL; 2) the theoretical improvements appear to be small; 3) some small flaws in the proofs.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "## Weaknesses\n1. From the numerical studies on Local SGD in training neural networks one can see that the proposed ideas are unrealistic. For instance, by reading the paper (Lin et al. \"Don't Use Large Mini-Batches, Use Local SGD\") one can mention that a relatively small number of local steps, such as 16, is used in practice. Increasing this number linearly as in Theorem 1 seems exotic, and without a numerical study by the authors I cannot conclude positively on the promise of such ideas.\n\n2. Theorem 1 does not look very good to me. Since beta is lower bounded by kappa^2, it also holds that the stepsize is smaller than 1/(kappa * L), which does not seem to be a good assumption. Moreover, the upper bound in Theorem 1 includes the term kappa^2/(R*T), which seems to be kappa times worse than the similar term kappa*H/T^2 in Corollary 1 of Khaled et al. I am also puzzled as to why the authors used beta=1 in their experiments as explained in Appendix A, which is clearly against their theoretical results.\n\n3. The proofs are a bit unexplained, some definitions seem missing. For instance, I guess from some equations that g_i^t (without any hats or bars) is the expectation of \\hat g_i^t, but I didn't find the definition in the text. As far as I can see, the epsilon in the proof of Lemma 4 was not introduced either.\n\nI did not understand the first step in equation (16). Why does it hold that sum_i ||g_i^t - overline g^t||^2 <= sum_i ||g_i^t - nabla f(\\overline x^t)||^2 ?\n\n## Proposed improvements\n1. In the strongly convex case, the analysis could be done with the variance of gradients measured at the optimum instead of the global bound.\n2. (Completely optional) I have a wild guess that additional results can be obtained under the setting of statistical similarity (Hendrikx et al., 2020), because for homogeneous data (sigma=0) the bounds significantly improve. Since the authors already perform analysis based on the Hessian at the optimum. I only suggest this in case the authors decide to resubmit their paper to a different venue or to write a new paper,  I do not ask the authors to do this during the rebuttal period.\n\nHendrikx et al., 2020, \"Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization\"\n\n## Missing references\n\"Parallel Gradient Distribution in Unconstrained Optimization\" by O. Mangasarian (1995) is probably the first work to introduce the idea if Local SGD and do (asymptotic) analysis. I believe this paper should be cited\n\n## Typos and minor comments\n1. Abstract: I suggest writing Omega(poly(log T)) instead of Omega(polynomial in log T)  \n2. Abstract line 11: \"state-of-the-art\" is adjective and \"state of the art\" is a noun, so please fix it\n3. Page 2, line 64: \"strongly-convex\" -> \"strongly convex\"\n4. Page 3, line 89: \"at the optimizer\" -> \"at the optimum\"\n5. \"Charles, Papailiopoulos (2018) shows\" (and many other examples): it feels rather strange that you refer to papers with multiple authors as to a singular noun.\n6. \"Lohasiewicz\" -> \"{\\L}ojasiewicz\"\n7. Page 4, line 208: \"for t\\in I and i.\" What does this mean?\n8. Page 8, line 293: \"to obtain a linear up\" -> \"to obtain a linear speed-up\"\n9. Page 15, line 552: \"the the\"\n10. Page 17, equation (13) and the lines after: \"f(x^t) - F*\" -> \"f(x^t) - f*\", \"smoothness of F\" -> \"smoothness of f\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "8BSEugMV09w", "reviewer": "Reviewer_3FSZ", "summary": "This paper analyzes local SGD with progressively decreasing communication frequency under the homogeneous data assumption. Unfortunately, the obtained convergence rates are worse than the best-known convergence rates for FedAC (Yuan and Ma) under the same set of assumptions. The paper also analyses One-shot averaging under a slightly different set of assumptions, showing it retains its linear convergence in settings less restrictive than pre-existing literature. Since the major result of this paper is worse than FedAC's guarantee, it is very incremental.  \n\n**References**\n\nYuan, Honglin, and Tengyu Ma. \"Federated Accelerated Stochastic Gradient Descent.\" Advances in Neural Information Processing Systems 33 (2020).", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "It seems the authors are unaware of FedAC, which requires $N^{1/3}$ synchronization for a linear speedup, and is a first-order algorithm analyzed under strong convexity, smoothness and uniform bounded variance. This is my major concern with the paper, since proving a lower communication complexity for Local SGD was its main (claimed) contribution. \n\nOne-shot averaging is known to be minimax optimal for quadratic functions (after adding acceleration) (Woodworth et. al.). Previous works require higher-order assumptions (satisfied by quadratics) to show such speed-up for one-shot SGD. Thus, I understand the appeal to somehow push the result for OSA to a larger class of functions. But again, in absence of comparison to results from FedAC for both their A1 and A2 assumptions, I am hesitant to make a judgment on these results. \n\nFinally, I don't think the real-data experiments demonstrate any statistically significant advantage. Moreover, without comparison to FedAC, I am not ready to buy any experimental claims here. \n\n# After a discussion about FedAC\n\nAfter the authors acknowledged that they missed a fair comparison to FedAC, and have listed some of its theoretical limitations, I am increasing my score to 5. If my concerns regarding empirical comparison to FedAC are resolved then I will further increase my score. \n\n# Final Verdict\n\nAfter the authors made the required empirical comparison with FedAC, I am more satisfied with the paper. I would urge the authors to include more experiments in the final version of the paper with a larger tuning grid, larger condition number, with clear comparison against FedAC and the other baselines. In light of all the back and forth discussion, as well as the proposed changes I am increasing my score to a 6 and am fine with the paper being accepted.\n\n**References**\n\nWoodworth, Blake, et al. \"Is local SGD better than minibatch SGD?.\" International Conference on Machine Learning. PMLR, 2020.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have not compared to the most important baseline FedAC, which is detrimental for this paper. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the oracle (gradient) complexity of the local SGD algorithm (and one-shot averaging as a special case). The paper makes two main contributions (see additional comments below), (1) a slightly improved complexity estimate for local SGD with non-equally spaced (linearly increasing) intermissions between communication rounds, and (2) a novel asymptotic result for one-shot averaging under PL and second order smoothness assumption.

The paper has prompted lengthy discussions, both publicly and internally among the reviewers. 

The main focus of the paper is currently on result (1). However, all reviewers unanimously find this result not very significant, since, for example a discussion of a corresponding lower complexity bound is missing and thus a log factor improvement seems very marginal. For the final version, we urge the authors 
- to carefully discuss the improvement over Theorem 2 (strongly convex case) in [[Woodworth et al, ICML 2020](https://arxiv.org/pdf/2002.07839.pdf)] (essentially, it seems the new result improves under the condition $\kappa \leq \log (T)$ only.
- the reviewers mentioned the suboptimal dependence on e.g. the condition number and found the author's response (speculating on an inherent trade-off) very interesting. However, I would strongly encourage authors to be very precise when including such claims, as the trade-off may just be a consequence of the proof technique.

The reviewers found result (2) interesting. Although strong assumptions are being made at the moment, the result could possibly stipulate further research.

To conclude, the contribution regarding (2), as well as the proposed modifications in the discussion with the reviewers (including discussion on FedAC and additional numerical results), gave the impetus to argue for acceptance for this work.
Decision: Accept (Poster)