Communication-efficient SGD: From Local SGD to One-Shot Averaging

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 Ω( √ 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 Ω (N ( poly(log T ))) 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 Ω(N) communications are sufficient. Empirical evidence suggests this bound is close to tight as we further show that √ N or N 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.

text: √ 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 Ω (N ( poly(log T ))) 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 Ω(N) communications are sufficient. Empirical evidence suggests this bound is close to tight as we further show that √ N or N3/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.

heading: 1 Introduction
text: Stochastic Gradient Descent (SGD) is a widely used algorithm to minimize convex functions f in which model parameters are updated iteratively as
xt+1 = xt − ηtĝt,
where ĝt is a stochastic gradient of f at the point xt and ηt is the learning rate. This algorithm can be naively parallelized by adding more workers independently to compute a gradient and then average
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
them at each step to reduce the variance in estimation of the true gradient∇f(xt) (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; Konečnỳ et al., 2016; Lin et al., 2018b). Often, mini-batch parallel SGD is suggested to address this issue by increasing the computation to communication ratio. Nonetheless, too large mini-batch size might degrade performance (Lin et al., 2018a). 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 a 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 to fully synchronized SGD. Therefore, there is a tradeoff 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; Konečnỳ 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 a factor of H = O( √ T/N), without affecting the asymptotic convergence rate (up to 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-Lojasiewicz condition, Haddadpour et al. (2019) demonstrate that only R = Ω((TN)1/3) communication rounds are sufficient to 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 Ω (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 as the case of data being heterogeneously distributed among workers. More recently, Yuan, Ma (2020) proposed a new accelerated method that requires only Ω ( N1/3 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; Godichon-Baggioni, Saadane, 2020). This method can be seen as an extreme case of Local SGD with R = 1 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 in this work, is whether these assumptions can be relaxed and OSA can achieve linear speed-up in more general scenarios.
In this work, we focus on smooth and strongly convex functions with a general noise model. Our contributions are three-fold:
We notice that FedAC (Yuan, Ma, 2020) has a better dependence on the number of workers N , in expense of (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.
It is worth mentioning that although the the communication complexity by Woodworth et al. (2020) depends on T , their bound has a lower dependence on condition number κ. Hence, their results are stronger than ours only when κ = Ω(log T ).
The rest of this paper is organized as follows. In the following subsection we outline the related literature and ongoing works. In 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 in Section 5.

heading: 1.1 Related work
text: There has been a lot of effort in the recent research to take into account the communication delays and training time in designing faster algorithms (McDonald et al., 2010; Zhang et al., 2015; Bijral et al., 2016; Kairouz et al., 2019). See (Tang et al., 2020) for a 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 et al., 2020) and statistical estimation (Zhang et al., 2013b). Woodworth et al. (2020) present a rigorous comparison of Local SGD with H local steps and minibatch SGD with H 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 a lower bound on the worst case of Local SGD that is higher than the worst-case error of large mini-batch SGD in a certain regime. Zhang et al. (2013b) 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.
A 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 et 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 et 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 error-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 differences are small. Sharing the data set across multiple workers in this way is a popular strategy to speed up training. For example, such data sharing is implemented in (Chen et al., 2012; Yadan et al., 2013; Zhang et al., 2013a) to speed up training of deep neural networks with multiple GPUs within a single server. While there are many widely used mechanisms such as Horovod (Sergeev, Del Balso, 2018) for synchronous data-parallel distributed training, they share a 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 to a smaller number of rounds during the entire optimization process. Our approach further reduces the communication overhead by communicating less as the number of iterations grows.

heading: 1.2 Notation
text: For a positive integer s, we define [s] := {1, . . . , s}. We use bold letters to represent vectors. We denote vectors of all 0s and 1s by 0 and 1, respectively. We use ‖ · ‖ for the Euclidean norm of a vector and spectral norm of a matrix. Finally, N (µ, σ2) denotes a normal distribution with mean µ and variance σ2.

heading: 2 Problem formulation
text: Suppose there are N workers V = {1, . . . , N}, trying to minimize f : Rd → R 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 i holds a local parameter xti at iteration t. There is a set I ⊂ [T ] of communication times and nodes perform the following update:
xt+1i = { xti − ηtĝti , if t+ 1 /∈ I, 1 N ∑N j=1(x t j − ηtĝtj), if t+ 1 ∈ I,
(1)
where ĝti is an unbiased stochastic gradient of f at x t i. When I = [T ], we recover fully synchronized parallel SGD while I = {T} recovers one-shot averaging. Pseudo-code for Local SGD is provided as Algorithm 1.
Algorithm 1 Local SGD
1: Input: x0i = x 0 for all i ∈ [n], total number of iterations T , the step-size sequence {ηt}T−1t=0 , and
I ⊆ [T ] 2: for t = 0, . . . , T − 1 do 3: for j = 1, . . . , N do 4: evaluate a stochastic gradient ĝtj 5: if t+ 1 ∈ I then 6: xt+1j = 1 N ∑N i=1(x t i − ηtĝti) 7: else 8: xt+1j = x t j − ηtĝtj
9: end if 10: end for 11: end for
Next we state the assumptions that we will use in our results. Note that we will not require all of them to hold at once. Assumption 1 (smoothness). The function f : Rd → R is continuously differentiable and its gradients are L-Lipschitz, i.e.,
‖∇f(x)−∇f(y)‖ ≤ L‖x− y‖, ∀x,y. Assumption 2 (strong convexity). f is µ-strongly convex with µ > 0, i.e.,
f(x) + 〈g,y − x〉+ µ 2 ‖x− y‖2 ≤ f(y), ∀x,y ∈ Rd,∀g ∈ ∂f(x),
where ∂f(x) denotes the set of subgradients of f at x. When f is also continuously differentiable, ∂f(x) = {∇f(x)}.
Note that when f satisfies Assumption 2, it has a unique optimal point x∗ where f(x∗) = f∗ where f∗ = minx f(x). Assumption 3 (Polyak-Łohasiewicz condition). f is µ-Polyak-Łohasiewicz (µ-PL for short) if
‖∇f(x)‖2 ≥ 2µ(f(x)− f∗), ∀x. where f∗ = minx f(x) is the global minimum of f . We further assume that f has a unique optimal point x∗ where f(x∗) = f∗.
When f satisfies both Assumptions 1 and 2 or Assumptions 1 and 3, we define κ = L/µ as the condition number of 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, a PL function is not even necessarily convex. Charles, Papailiopoulos (2018) show that deep networks with linear activation functions are PL almost everywhere in the parameter space. Allen-Zhu et al. (2018) show, with high probability over random initializations, that sufficiently wide recurrent neural networks satisfy the PL condition. Therefore, the PL condition is more applicable, especially in the context of neural networks (Madden et al., 2020).
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 of stochastic gradients, using wti = ĝ t i −∇f(xti) to denote the difference between the stochastic and true gradients. Assumption 5 (uniform with strong-growth noise). Conditioned on the iterate xti, the random variable wti is zero-mean and independent with its expected squared norm error bounded as,
E[‖wti‖2|xti] ≤ c‖∇f(xti)‖2 + σ2, where σ2, c ≥ 0 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/σ2 is large. Therefore, to study Local SGD, it is important to consider a 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 c = 0. SGD under this noise model with c > 0 and σ2 = 0 was first studied in Schmidt, Roux (2013) under the name strong-growth condition. Therefore we refer to the noise model considered in this work as uniform with strong-growth. Assumption 6 (sub-Gaussian noise). Conditioned on the iterate xti, random variable wti is zero-mean, independent and [wti ]l is (σ/ √ d)-sub-Gaussian, for l = 1, . . . , d, i.e.,
E[exp(λ([wti ]l − E[wti ]l))|xti] ≤ exp ( λ2σ2
2d
) , ∀λ ∈ R, l = 1, . . . , d.
Thus, it has uniformly bounded variance E[‖wti‖2|xti] ≤ σ2.
A sub-Gaussian noise model is commonly assumed for deriving concentration bounds for SGD, which we will use to prove our results for OSA.
As already mentioned in the Introduction, the main goal of this paper is 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 a small number of communication instances. Moreover, we will obtain a set of sufficient conditions for OSA to achieve linear speed-up.

heading: 3 Convergence results
text: In this section we present our main convergence results for Local SGD and OSA. In what follows, we denote by x̄t := ( ∑N i=1 x t i)/N the average of the iterates of all workers. Notice that x t i = x̄
t for t ∈ I and i = 1, . . . , N .

heading: 3.1 Local SGD
text: Let us introduce the notation 0 = τ0 < τ1 < . . . < τR = T, for the communication times. Further, let us define Hi := τi+1 − τi to be the i’th interccommunication interval. Our first theorem gives a performance bound under the assumption that Hi grows linearly with i. Theorem 1. Suppose Assumptions 1 (smoothness), 2 (strong convexity) and 5 (uniform with strong growth noise) hold. Choose the parameters as follows: R such that 1 ≤ R ≤ √
2T and a := d2T/R2e ≥ 1,Hi = a(i+1) and τi+1 = min(τi +Hi, T ) for i = 0, . . . , R− 1. Choose β ≥ max{9κ, 12κ2cmax{ln(3), ln(1 + T/(4κR2))}+ 3κ(1 + c/N)} and set the learning rate as ηt = 3/µ(t+ β), t = 0, 1, . . . , T − 1. Then using Algorithm 1 we have,
E[f(x̄T )]− f∗ ≤ β 2(f(x̄0)− f∗)
T 2 +
9Lσ2
2µ2NT +
144L2σ2
µ3RT .
Corrollary 1. Under the assumptions of Theorem 1, selecting the number of communications R = Ω(κN) we obtain
E[f(x̄T )]− f∗ ≤ β 2(f(x̄0)− f∗)
T 2 +O
( Lσ2
µ2NT
) .
The choice of communication times in Theorem 1 aligns with the intuition that workers need to communicate more frequently at the beginning of the optimization. As the the step-sizes become smaller and workers’ local parameters get closer to 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 1 can be found in Appendix B.

heading: 3.2 One-shot averaging
text: 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, GodichonBaggioni, 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 Cm and all x ∈ Rd,∥∥∇f(x)−∇2f(x∗)(x− x∗)∥∥ ≤ Cm‖x− x∗‖2. 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 {θt} as
θt =
{ 1 L , for t = 0, . . . , t0 − 1,
2t µ(t+1)2 , for t ≥ t0,
(2)
where t0 = b2L/µc. Notice that θt ≤ 1/L for all t. Theorem 2. Under Assumptions 1 (smoothness), 3 (PL condition), 4 (twice differentiability at the optimum) and 6 (sub-Gaussian noise) and with step-size sequence {ηt} = {θt} defined in (2), we have for T ≥ t0,
E [∥∥x̄T − x∗∥∥2] ≤ 4σ2
3µ2NT + o
( 1
T
) .
We are thus able to 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 at a single point. As a bonus, we also replace strong convexity with the PL condition.
This theorem is proved in Appendix C. The main difference between Theorem 2 and Corollary 1 is that Theorem 2 shows a linear speed-up with only one communication round but with slightly more restrictive assumptions such as sub-Gaussian noise model and twice-differentiable objective function at the optimal point. On the other hand, our results for OSA only require the PL-condition instead of strong convexity.

heading: 4 Numerical experiments
text: To verify our findings and compare different communication strategies in Local SGD, we performed the following numerical experiments, using an Nvidia GTX-1060 GPU and Intel Core i7-7700k processor.

heading: 4.1 Quadratic function with strong-growth condition
text: As discussed in Zhang et al. (2016); Dieuleveut, Patel (2019), under uniformly bounded variance, oneshot averaging performs asymptotically as well as mini-batch SGD, at least for quadratic functions.
Therefore, to fully capture the importance of the choice of communication times I , we design a hard problem, where noise variance is uniform with strong-growth condition, defined in Assumption 5. Let us define,
F (x) = Eζf(x, ζ), f(x, ζ) := d∑ i=1 i 2 x2i (1 + z1,i) + x >z2, (3)
where ζ = (z1, z2) and z1, z2 ∈ Rd, z1,i ∼ N (0, c1) and z2,i ∼ N (0, c2), ∀i ∈ [d], are random variables with normal distributions. We assume at each iteration t, each worker i samples a ζti and uses ∇f(x, ζti ) as a stochastic estimate of ∇F (x). It is easy to verify that F (x) is 1-strongly convex and d-smooth, F ∗ = 0 and Eζ [‖∇f(x, ζ) − ∇F (x)‖2] = c‖∇F (x)‖2 + σ2, where c = c1 and σ2 = dc2.
We use Local SGD to minimize F (x) using different communication strategies, namely, synchronized SGD where H = 1, H ≈ √ TN Stich (2019), H ≈ (TN)1/3 Haddadpour et al. (2019), R = N with constant H ≈ T/N Stich, Karimireddy (2019); Khaled et al. (2020) and finally the communication strategy proposed in this work with R = N and linearly growing Hi local steps. We used N = 20 workers, T = 1000 iterations, c1 = 1.0 and c2 = 10−10 with d = 3 and step-size sequence ηt = 3/(µ(t+ 1)). To estimate the expected value of errors, we repeated the optimization using each strategy 100 times and reported the average and 1-standard-deviation error bar in Figure 1.
We make the following observations from Figure 1:
• Figure 1(a) shows that a communication strategy with increasing local steps (proposed in this work), outperforms all the other methods, both in transient and final error performance, specifically the one with the same number of communication rounds evenly spread throughout the whole optimization. This confirms the advantage of more frequent communication at the beginning of the optimization, especially when the ratio of c to σ2 in the noise with growth condition is large (see the definition in Assumption 5).
• Figure1(b) shows that our communication method uses fewer communication rounds, 20 versus 28 (Haddadpour et 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 is 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, as long as it communicates at least once, will succeed.

heading: 4.2 Speed-up curves
text: In this experiment, we minimize a one-dimensional function defined as,
F (x) =
{ 1 2x
2, x ≤ 0, x2, x > 0,
(4)
using Local SGD with gradients corrupted by a normal noise N (0, σ2). We chose this specific cost function since it is not twice continuously differentiable at the minimizer x∗ = 0 and does not 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 is a necessary assumption for OSA to obtain a linear speed-up.
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 to see a straight line on the graph.
We plot the speed-up curve for N workers using different communication strategies: synchronized SGD, R = N communication rounds with linearly increasing number of local steps Hi, R = N with constant number of local steps H ≈ T/R, as well as OSA with only R = 1 communication at the end. We use the step-size sequence ηt = min{1/L, 2/(µ(t + 1))} with µ = 1, L = 2, and σ = 8, T = 1000.
Our results in Figure 2(a) show that Local SGD with R = N (increasing or constant H) achieves linear speed-up in the number of workers, albeit with a worse constant compared to synchronized SGD. However, OSA fails to scale as N 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 onR 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 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 , as expected and R = 1 and R ≈ N1/2 fail to speed-up. However, R ≈ N3/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 ≈ N0.9 or even R ≈ N0.99 but this would require much larger values of N and T and thus more repeated simulations, which is 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 in this experiment is simply uniformly bounded, without strong-growth condition. This further endorses the use of more frequent averaging at the beginning of optimization, when paired with decreasing step-size sequence.

heading: 4.3 Regularized logistic regression
text: We also performed additional numerical experiments with regularized logistic regression using two large real datasets: (i) a 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, 2011) which includes 32561 data points with d = 124 features. The results of these experiments are presented and discussed in Appendix A.

heading: 5 Conclusion
text: In this work, we studied the communication complexity of Local SGD and provided an analysis that shows that R = Ω(N) number of communication rounds, independent of the total number of iterations T , is sufficient to achieve linear speed-up. Moreover, we showed only a single round of averaging is needed provided that the objective is twice differentiable at the optimum point. This assumption appears to be necessary, as our simulations show that not only one-shot averaging but using N1/2 or N3/4 communications in local SGD fails to deliver linear speed-up on a simple example which is not twice differentiable at the optimum.
Acknowledgments and Disclosure of Funding
The research was partially supported by the NSF under grants DMS-1664644, CNS-1645681, ECCS1933027 and IIS-1914792, by the ONR under grants N00014-19-1-2571 and N00014-21-1-2844, by the ARO under grant W911NF-1-1-0072, by the NIH under grants R01 GM135930 and UL54 TR004130, by the DOE under grants DE-AR-0001282 and NETL-EE0009696, and by the Boston University Kilachand Fund for Integrated Life Science and Engineering.

Review summaries:
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.    **References**  Yuan, Honglin, and Tengyu Ma. "Federated Accelerated Stochastic Gradient Descent." Advances in Neural Information Processing Systems 33 (2020).

## Update after rebuttall  I am satisfied with the authors' response and elevate my score to 6.  ##  This 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:  1. 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.  2. 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.   3. 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.  I 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.

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.

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.