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.
abstractText: 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.
authors.name: Alex Olshevsky
references.authors: Alistarh Dan Grubic Demjan Li Jerry Tomioka Ryota Vojnovic Milan
references.title: QSGD: Communicationefficient SGD via gradient quantization and encoding
references.venue: Advances in Neural Information Processing Systems
references.authors: Allen-Zhu Zeyuan Li Yuanzhi Song Zhao
references.title: On the convergence rate of training recurrent neural networks
references.authors: Arjevani Yossi Shamir Ohad
references.title: Communication complexity of distributed convex learning and optimization // Advances in neural information processing systems
references.authors: Beck Amir
references.title: Introduction to nonlinear optimization: Theory, algorithms, and applications with MATLAB
references.authors: S Bijral Avleen D Sarwate Anand Nathan. Srebro
references.title: On data dependence in distributed stochastic optimization // arXiv preprint arXiv:1603.04379
references.authors: Chang Chih-Chung Lin Chih-Jen
references.title: LIBSVM: A library for support vector machines
references.venue: ACM Transactions on Intelligent Systems and Technology
references.authors: Charles Zachary Papailiopoulos Dimitris
references.title: Stability and generalization of learning algorithms that converge to global optima
references.venue: International Conference on Machine Learning
references.authors: Chen Xie Eversole Adam Li Gang Yu Dong Seide Frank
references.title: Pipelined back-propagation for contextdependent deep neural networks
references.venue: Thirteenth Annual Conference of the International Speech Communication Association
references.authors: Dekel Ofer Gilad-Bachrach Ran Shamir Ohad Xiao Lin
references.title: Optimal distributed online prediction using mini-batches
references.venue: Journal of Machine Learning Research
references.authors: Dieuleveut Aymeric Patel Kumar Kshitij
references.title: Communication trade-offs for Local-SGD with large step size
references.venue: Advances in Neural Information Processing Systems
references.authors: Godichon-Baggioni Antoine Saadane Sofiane
references.title: On the rates of convergence of parallelized averaged stochastic gradient algorithms // Statistics
references.authors: Grubic Demjan Tam Leo K Alistarh Dan Zhang Ce
references.title: Synchronous multi-gpu deep learning with low-precision communication: An experimental study
references.venue: Proceedings of the 21st International Conference on Extending Database Technology
references.authors: Haddadpour Farzin Kamani Mohammad Mahdi Mahdavi Mehrdad Cadambe Viveck
references.title: Local SGD with periodic averaging: Tighter analysis and adaptive synchronization
references.venue: Advances in Neural Information Processing Systems
references.authors: Hendrikx Hadrien Bach Francis Massoulié Laurent
references.title: An accelerated decentralized stochastic proximal algorithm for finite sums
references.venue: Advances in Neural Information Processing Systems
references.authors: Kairouz Peter McMahan H Brendan Avent Brendan Bellet Aurélien Bennis Mehdi Bhagoji Arjun Nitin Bonawitz Keith Charles Zachary Cormode Graham Cummings Rachel
references.title: Advances and open problems in federated learning
references.authors: Karimi Hamed Nutini Julie Schmidt Mark
references.title: Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition
references.venue: Joint European Conference on Machine Learning and Knowledge Discovery in Databases
references.authors: A Khaled K Mishchenko P. Richtárik
references.title: Tighter theory for local SGD on identical and heterogeneous data
references.venue: The 23rd International Conference on Artificial Intelligence and Statistics (AISTATS
references.authors: Koloskova Anastasia Loizou Nicolas Boreiri Sadra Jaggi Martin Stich Sebastian U
references.title: A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
references.authors: Konečnỳ Jakub McMahan H Brendan Yu Felix X Richtárik Peter Suresh Ananda Theertha Bacon Dave
references.title: Federated learning: Strategies for improving communication efficiency
references.venue: arXiv preprint arXiv:1610.05492
references.authors: Lin Tao Stich Sebastian U Patel Kumar Kshitij Jaggi Martin
references.title: Don’t Use Large Mini-Batches
references.venue: Use Local SGD // arXiv preprint arXiv:1808.07217
references.authors: Lin Yujun Han Song Mao Huizi Wang Yu Dally Bill
references.title: Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training
references.venue: International Conference on Learning Representations
references.authors: Madden Liam Dall’Anese Emiliano Becker Stephen
references.title: High probability convergence and uniform stability bounds for nonconvex stochastic gradient descent
references.authors: Mangasarian LO
references.title: Parallel gradient distribution in unconstrained optimization
references.venue: SIAM Journal on Control and Optimization
references.authors: McDonald Ryan Hall Keith Mann Gideon
references.title: Distributed training strategies for the structured perceptron // Human language technologies: The 2010 annual conference of the North American chapter of the association for computational linguistics
references.authors: McMahan Brendan Moore Eider Ramage Daniel Hampson Seth Arcas Blaise Aguera y
references.title: Communication-Efficient Learning of Deep Networks from Decentralized Data
references.venue: Artificial Intelligence and Statistics
references.authors: Mcdonald Ryan Mohri Mehryar Silberman Nathan Walker Dan Mann Gideon S
references.title: Efficient largescale distributed training of conditional maximum entropy models // Advances in neural information processing systems
references.authors: Rosenblatt Jonathan D Nadler Boaz
references.title: On the optimality of averaging in distributed statistical learning // Information and Inference: A Journal of the IMA
references.authors: Schmidt Mark Roux Nicolas Le
references.title: Fast convergence of stochastic gradient descent under a strong growth condition // arXiv preprint arXiv:1308.6370
references.authors: Sergeev Alexander Del Balso Mike
references.title: Horovod: fast and easy distributed deep learning in TensorFlow
references.venue: arXiv preprint arXiv:1802.05799
references.authors: Spiridonoff Artin Olshevsky Alex Paschalidis Ioannis Ch
references.title: Robust asynchronous stochastic gradientpush: asymptotically optimal and network-independent performance for strongly convex functions
references.venue: Journal of Machine Learning Research
references.authors: U. Stich Sebastian
references.title: Local SGD Converges
references.venue: Fast and Communicates Little // International Conference on Learning Representations
references.authors: Stich Sebastian U Cordonnier Jean-Baptiste Jaggi Martin
references.title: Sparsified SGD with memory
references.venue: Advances in Neural Information Processing Systems
references.authors: Stich Sebastian U Karimireddy Sai Praneeth
references.title: The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication
references.authors: Tang Zhenheng Shi Shaohuai Chu Xiaowen Wang Wei Li Bo
references.title: Communication-Efficient Distributed Deep Learning: A Comprehensive Survey
references.authors: Wang Jianyu Joshi Gauri
references.title: Adaptive communication strategies to achieve the best error-runtime trade-off in local-update SGD // Systems for ML
references.authors: Wang Jianyu Joshi Gauri
references.title: Cooperative SGD: A unified framework for the design and analysis of communication-efficient SGD algorithms // arXiv preprint arXiv:1808.07576
references.authors: Wang Jianyu Sahu Anit Kumar Yang Zhouyi Joshi Gauri Kar Soummya
references.title: MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling
references.authors: Wangni Jianqiao Wang Jialei Liu Ji Zhang Tong
references.title: Gradient sparsification for communicationefficient distributed optimization
references.venue: Advances in Neural Information Processing Systems
references.authors: Woodworth Blake Patel Kumar Kshitij Stich Sebastian U Dai Zhen Bullins Brian McMahan H Brendan Shamir Ohad Srebro Nathan
references.title: Is Local SGD Better than Minibatch SGD
references.authors: Yadan Omry Adams Keith Taigman Yaniv Ranzato
references.title: Marc’Aurelio. Multi-gpu training of convnets
references.venue: arXiv preprint arXiv:1312.5853
references.authors: Yu Hao Yang Sen Zhu Shenghuo
references.title: Parallel restarted SGD with faster convergence and less communication: Demystifying why model averaging works for deep learning
references.venue: Proceedings of the AAAI Conference on Artificial Intelligence
references.authors: Yuan Honglin Ma Tengyu
references.title: Federated Accelerated Stochastic Gradient Descent
references.venue: Advances in Neural Information Processing Systems
references.authors: Zhang Jian De Sa Christopher Mitliagkas Ioannis Ré Christopher
references.title: Parallel SGD: When does averaging help
references.venue: arXiv preprint arXiv:1606.07365
references.authors: Zhang Shanshan Zhang Ce You Zhao Zheng Rong Xu Bo
references.title: Asynchronous stochastic gradient descent for DNN training
references.venue: IEEE International Conference on Acoustics, Speech and Signal Processing
references.authors: Zhang Sixin Choromanska Anna E LeCun Yann
references.title: Deep learning with elastic averaging SGD // Advances in neural information processing systems
references.authors: Zhang Yuchen Duchi John Jordan Michael I Wainwright Martin J
references.title: Information-theoretic lower bounds for distributed statistical estimation with communication constraints
references.venue: Advances in Neural Information Processing Systems
references.authors: Yuchen Zhang C Duchi John J. Wainwright Martin
references.title: Communication-efficient algorithms for statistical optimization
references.venue: Journal of Machine Learning Research. 2013c
references.authors: Zhou Fan Cong Guojing
references.title: On the convergence properties of a K-step averaging stochastic gradient descent algorithm for nonconvex optimization
references.venue: Proceedings of the 27th International Joint Conference on Artificial Intelligence
references.authors: Zinkevich Martin Weimer Markus Li Lihong Smola Alex J
references.title: Parallelized stochastic gradient descent // Advances in neural information processing systems
sections.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.
sections.heading: 1 Introduction
sections.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.
sections.heading: 1.1 Related work
sections.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.
sections.heading: 1.2 Notation
sections.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.
sections.heading: 2 Problem formulation
sections.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.
sections.heading: 3 Convergence results
sections.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 .
sections.heading: 3.1 Local SGD
sections.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.
sections.heading: 3.2 One-shot averaging
sections.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.
sections.heading: 4 Numerical experiments
sections.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.
sections.heading: 4.1 Quadratic function with strong-growth condition
sections.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.
sections.heading: 4.2 Speed-up curves
sections.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.
sections.heading: 4.3 Regularized logistic regression
sections.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.
sections.heading: 5 Conclusion
sections.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.
title: Communication-efficient SGD: From Local SGD to One-Shot Averaging