A Communication-Efficient Distributed Gradient Clipping Algorithm for Training Deep Neural Networks
Authors: Chunyang Liao
Zhenxun Zhuang
Mingrui Liu
Venue: ICLR 2022 Submitted (2022)
Keywords: Distributed Training
Federated Learning
Gradient Clipping
Communication-Efficient
Optimization

Abstract: In distributed training of deep neural networks or Federated Learning (FL), people usually run Stochastic Gradient Descent (SGD) or its variants on each machine and communicate with other machines periodically. However, SGD might converge slowly in training some deep neural networks (e.g., RNN, LSTM) because of the exploding gradient issue. Gradient clipping is usually employed to address this issue in the single machine setting, but exploring this technique in the FL setting is still in its infancy: it remains mysterious whether the gradient clipping scheme can take advantage of multiple machines to enjoy parallel speedup in the FL setting. The main technical difficulty lies at dealing with nonconvex loss function, non-Lipschitz continuous gradient, and skipping communication rounds simultaneously. In this paper, we explore a relaxed-smoothness assumption of the loss landscape which LSTM was shown to satisfy in previous works, and design a communication-efficient gradient clipping algorithm. This algorithm can be run on multiple machines, where each machine employs a gradient clipping scheme and communicate with other machines after multiple steps of gradient-based updates. Our algorithm is proved to have $O\left(\frac{1}{N\epsilon^4}\right)$ iteration complexity for finding an $\epsilon$-stationary point, where $N$ is the number of machines. This indicates that our algorithm enjoys linear speedup. Our experiments on several benchmark datasets demonstrate that our algorithm indeed exhibits fast convergence speed in practice and validate our theory.

Under review as a conference paper at ICLR 2022
A COMMUNICATION-EEFIIENN DISTRIBUTED GRA- DIENT CLIPPING ALGORITHM FOR TRAINING DEEP NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
In distributed training of deep neural networks or Federated Learning (FL), peo- ple usually run Stochastic Gradient Descent (SGD) or its variants on each ma- chine and communicate with other machines periodically. However, SGD might converge slowly in training some deep neural networks (c.g., RNN, LSTM) be- cause of the exploding gradient issue. Gradient clipping is usually employed to address this issue in the single machine setting, but exploring this technique in the FL setting is still in its infancy: it remains mysterious whether the gradient clip- ping scheme can take advantage of multiple machines to enjoy parallel speedup in the FL setting. The main technical difficulty lies at dealing with nonconvex loss function, non-Lipschitz continuous gradient, and skipping communication rounds simultaneously. this paper. we explore a loss landscape which LSTM was shown to satisfy in previous works, and design communicationneffciiee gradient clipping algorithm. This algorithm can be run on multiple machines, where each machine employs gradient clipping scheme and communicate with other machines after multiple steps of gradient-based up- dates. Our algorithm is proved to have O NET iteration complexity for finding an e-stationary point, where N the number of machines. This indicates that our algorithm enjoys linear speedup. Our experiments and various scenarios demonstrate that our algorithm indeed exhibits fast conver- gence speed in practice and validate our theory.
assumption of the
several benchmark datasets
INTRODUCTION
Deep learning has achieved tremendous successes in many domains including computer vi- sion (Krizhevsky et al., 2012; He et al., 2016) and natural language processing (Devlin et al., 2018), game (Silver et al., 2016). To obtain good empirical performance, people usually need to train large models on huge amount of data, and it is usually very computationally expensive. To speedup the training process, distributed training becomes indispensable (Dean al., 2012). For example, Goyal et al. (2017) trained ResNet-50 on ImageNet dataset by distributed SGD with minibatch size 8192 on 256 GPUs only one hour, which not only matches the small minibatch accuracy but also enjoys parallel speedup, and hence improves the rumning time. Recently, there is an increasing interest in an variant of distributed learning, namely Federated Learning (FL) (McMahan et al., 2017), which focuses the cases where the training data is non-i.i.d. across devices and only limited communi- cation is allowed. McMahan et al. (2017) proposed an algorithm named Federated Averaging, which runs multiple steps of SGD on each clients before communicating with other clients.
Despite the empirical success of distributed SGD and its variants (e.g.. Federated Averaging) in deep learning, they may not exhibit good performance when training some neural networks (e.g.. Recurrent Neural Networks, LSTMs), due to the exploding gradient problem (Pascanu et al., 2012; 2013). To address this issue, Pascanu et al. (2013) proposed to use the gradient clipping strategy, and it has become a standard technique when training language models (Gehring et al., 2017: Peters et al., 2018; Merity et al., 2018). There are some recent works trying to theoretically explain gra- dient clipping from nonconvex optimization's 's perspective (Zhang et al., 2019; 2020). These works are built upon an important observation made in (Zhang et al., 2019): for certain neural networks such as LSTM, the gradient does not vary uniformly over the loss landscape (i.e., the gradient is not Lipschitz continuous with a uniform constant), and the gradient Lipschitz constant can scale linearly with respect to the gradient norm. This is referred to the relaxed smoothness condition (i.e.. (Lo, smmooththsssss defined in Definition 2), which generalizes but strictly relaxes the usual smoothness condition (i.e., /=smmothhness defined in Definition 1). Under the relaxed smoothness

---

Under review as a conference paper at ICLR 2022
Table 1: Comparison of Iteration and Communication Complexity of Different Algorithms for find- ing a point whose gradient's 's magnitude is smaller than (i.e., c-stationary point defined in Defini tion 3), N is the number of machines, the meaning of other constants can be found in Assumption
Algorithm
Setting
Iteration Complexity
Communication Complexity
SGD
Single'
O ( L + A(Lo + 1
N/A
(Ghadimi & Lan, 2013)
Clipped SGD
Single
O((A (Ln 1 Liojo? oL8/
N/A
(Zhang 2019)
Clipping Framework
Single
o (ALog'ec
N/A
(Zhung ul., 2020)
Naive Parallel of
Distributed
0 (ALogo/(NNe))
O (ALe)*)(NNe))
(Zhang el ul., 2020)
Ours (this work)
FL
O(ALolo 139 ((((())
O (ALulo 1x)
condition, Zhang al. (2019; 2020) proved that gradient clipping enjoys polynomial-timm iteration complexity for finding the first-order stationary point in the single machine setting, and it can be arbitrarily faster than fix-step gradient descent.
In practice, both distributed learning (or FL) and gradient clipping are important techniques to accel- erate neural network training. However, the theoretical analysis of gradient clipping is only restricted to the single machine setting (Zhang et al., 2019; 2020). Hence it naturally motivates us to consider the following question:
Is it possible that the gradient clipping scheme can take advantage of multiple machines to enjoy parallel speedup in training deep neural networks, with data heterogeneity across ma- chines and limited communication?
In this paper, we give an affirmative answer to the above question. Built upon the relaxed smoothness condition as in (Zhang et al., 2019; 2020), we design communication--efiiiee distributed gradient clipping algorithm. The key characteristics of our algorithm are: (i) unlike naive parallel gradient clipping algorithm which requires averaging model weights and gradients from all machines for every iteration, our algorithm only aggregates weights with other machines after certain number of local updates each machine; (ii) our algorithm clips the gradient according the norm of the local gradient on each machine, instead of the norm of the averaged gradients across machines as in the naive parallel version. These key features make our algorithm amenable the FL setting and is nontrivial to establish desired theoretical guarantees (e.g.. linear speedup, reduced communication complexity). The main difficulty in the analysis lies at dealing with nonconvex objective function, non-Lipschitz continuous gradient, and skipping communication rounds simultancously. Our main contribution is summarized as the following:
We design a novel communication-efficcaa distributed stochastic local gradient clipping al- gorithm, namely CELGC, for solving nonconvex optimization problem under the relaxed smoothness condition. The algorithm only needs to clip the gradient according to the local gradient's 's magnitude and globally averages the weights on all machines periodically. To the best of our knowledge, this is the first work proposing stochastic gradient clipping algorithms under the relaxed smoothness condition.
coammmicatioo-efffciee distributed
Under the relaxed smoothness condition, we prove iteration and communication complex- ity results of our algorithm for finding e-stationary point. First, comparing with (Zhang et al., 2020), we prove that our algorithm enjoys linear speedup, which means that the iter- ation complexity of our algorithm is reduced by factor of N (the number of machines). Second, comparing with naive parallel verion of the algorithm of (Zhang et al., 2020), we
'In this setting, we assume the gradient norm is upper bounded by M such that the gradient (La + L1 M) )- Lipschitz. However, we want to emphasize that the original paper of (Ghadimi & Lan, 2013) does not require bounded gradient assumption. instead they require L- L-Lipschitz gradient and bounded variance o², Under their assumption, their complexity result is O (A + ALo?e
"Navve Parallel of (Zhang et al. 2020) different from our algorithm (CELGC) with / 1 in that the naive version requires averaging gradients across all machines to update the model while CELGC only updates the model using local gradients computed in that machine. This also means that in each iteration, naive version clips the gradient based on the globally averaged gradient while ours only bases on the local gradient.
2

---

Under review as a conference paper at ICLR 2022
prove that our algorithm enjoys better communication complexity. Specifically, our algo- rithm's 's communication complexity is smaller than naive parallel clipping algorithm if the number of machines is not too large (i.e., N I O(1/e)). The detailed comparison over existing algorithms under the same relaxed smoothness condition is described in Table 1. Please refer to (Koloskova al., 2020) for local SGD complexity results for L-smooth functions.
We empirically verify our theoretical results by conducting experiments on different neural network architectures on benchmark datasets and on various scenarios including small to large batch-sizes, homogeneous and heterogeneous data distributions, and partial participa- tion of machines. The experimental results demonstrate that our proposed algorithm indeed exhibit speedup in practice.
RELATED WORK
Gradient ClippingNorrmalizationn Algorithms In deep learning literature, gradient clipping (normalization) technique was initially proposed by (Pascanu et al., 2013) to address the issue of exploding gradient problem in (Pascanu et al., 2012), and it has become a standard technique when training language models (Gehring et al., 2017: Peters et al., 2018; Merity et al., 2018). Menon et al. (2019) showed that gradient clipping is robust and can mitigate label noise. Recently gradient normalization techniques (You et al., 2017: 2019) were applied to train deep neural networks on the very large batch setting. For example, You et al. (2017) designed LARS algorithm to train a ResNet50 on ImageNet with batch size 32k, which utilized different learning rate according to the norm of the weights and the norm of the gradient.
In optimization literature, gradient clipping (normalization) was used early days in the field of convex optimization (Ermoliev, 1988; Alber et al., 1998; Shor, 2012). Nesterov (1984) and Hazan et al. (2015) considered normalized gradient descent for quasi-convex functions in deterministic and stochastic cases respectively. Gorbunov et al. (2020) designed accelerated gradient clipping method to solve convex optimization problem with heavy-tailed noise in stochastic gradients. Mai & Johansson (2021) established the stability and convergence of stochastic gradient clipping algo- rithms for convex and weakly convex functions. In nonconvex optimization, Levy (2016) showed that normalized gradient descent can escape from saddle points. Cutkosky & Mehta (2020) showed that adding a momentum provably improves the normalized SGD in nonconvex optimization. Zhang al. (2019) and Zhang al. (2020) analyzed the gradient clipping for nonconvex optimization under the relaxed smoothness condition rather than the traditional L-smoothness condition in nonconvex optimization (Ghadimi & Lan, 2013).
However, all of them only consider the algorithm in the single machine setting or the naive parallel setting, and none of them can apply to FL. setting where data on different nodes is heterogeneous and only limited communication is allowed.
Coamunication-Efficiee Algorithms in Distributed and Federated Learning In large-scale machine learning, people usually train their model using first-order methods on multiple machines and these machines communicate and aggregate their model parameters periodically. When the function is convex, there is scheme named one-shot averaging (Zinkevich et al., 2010; McDonald et al., 2010; Zhang et al., 2013; Shamir & Srebro, 2014), in which every machine runs an stochas- tic approximation algorithm and averages the model weights across machines only the very last iteration. One-shot averaging scheme is communicaioon-efficenn and enjoys statistical convergence with one pass of the data (Zhang et al., 2013; Shamir & Srebro, 2014; Jain al., 2017: Koloskova et al., 2019), but the training error may not converge in practice. McMahan et al. (2017) consid- ered the Federated Learning setting where the data is decentralized and might be non-i.i.d across devices and communication is expensive. McMahan et al. (2017) designed the very first algorithm for FL (a.k.a,, FedAvg), which is communication-efficee. other nodes infrequently. Stich (2018) considered a concrete case of FedAvg, namely local SGD, which runs SGD independently in parallel on different works and averages the model parameters only once in while. Stich (2018) also showed that local SGD enjoys linear speedup for strongly- convex objective function. There are also some works analyzing local SGD and its variants on convex (Dieuleveut & Patel, 2019; Khaled et al., 2020; Karimireddy et al., 2020; Woodworth al., 2020a;b; Gorbunov et al., 2021; Yuan et al., 2021) and nonconvex smooth functions (Zhou & Cong, 2017; Yu et al., 2019a;b; Jiang & Agrawal, 2018; Wang & Joshi, 2018 1018; Lin et al., 2018 8; Basu al.,
since every node communicates with
3

---

Under review as a conference paper at ICLR 2022
2019; Haddadpour et al., 2019; Karimireddy al., 2020). Recently, Woodworth al. (2020a;b) analyzed advantages and drawbacks of local SGD compared with minibatch SGD for convex objec- tives. Woodworth al. (2021) proved hardness results for distributed stochastic convex optimiza- tion. Reddi et al. (2021) introduced a general framework of federated optimization and designed several federated versions of adaptive optimizers. Zhang al. (2021) considered employ gradient clipping to optimize L-smooth functions and achieve differential privacy. Due to vast amount of literature of FL and limited space, we refer readers to (Kairouz et al., 2019) and references therein.
However, all of these works either assume the objective function is convex or L-smooth. To the best of our knowledge, our algorithm the first communication-effictte algorithm which does not rely on these assumptions but still enjoys linear speedup.
PRELIMINARIES, NOTATIONS AND PROBLEM SETUP
Preliminaries and Notations Denote || || by the Euclidean norm. We denote s Rd - IR as the overall loss function, and J: IR + as the loss function i-th machine, where 1, 1,...; N. Denote Vh(x) as the gradient of h evaluated at the point x, and denote ()(x; as the stochastic
gradient of & calculated based on sample Ç.
Definition 1 (L-smoothness), A function h is L-smooth if VV((x) - Vh(y)ll s L||x -yll
yll for all
x.y E R
Definition 2 ((Lo; I1) smmoohnte,)s A second order differentiable function h is (To, L )smmoohhh if [|V*h(x)]| & Lo + [ any RR.
Definition (e-stationary point). x E Rd is an e-stationary point of the function if [V((x)] S
Remark: From definitions, we know that the (Lo, Li Limmmottssssss is strictly weaker than L- smoothness. To see this, first, we know that L-smooth functions is (Lo, L1 -smoohh with Lg = and L1 = 0. However the reverse is not true. For example, consider the function hxx) = x²
know that the gradient is not Lipschitz continuous and hence is not L-smooth, but [b((2)] = 12.² <
12 + 4|rr|" 3 12 3/4' (x)) so h(x) = x² is (12, 3)-smotth. Zhang et al. (2019) empirically showed that the (Lo. L1 -mmothhnssss holds for the AWD-LSTM (Merity et al., 2018). In nonconvex optimization literature (Ghadimi & Lan, 2013; Zhang et al.. 2020), the goal is to find an e-stationary point since it is NP-hard to find a global optimal solution for a general nonconvex function.
Problem Setup In this paper, consider the following optimization problem:
N
min f(x) XER
N Σ f(x),
where N is the number of nodes and each fx(x) == :xx:=IEE.>D, [x; Ed)] is a nonconvex function where D; can be possibly different for different i. This formulation has broad applications in distributed deep learning and FI.. For example, in FL setting, S1 stands for the loss function on i-th machine, Dj represents the data distribution on i-th machine, and N machines want jointly optimize the objective function f.
We make the following assumptions throughout the paper.
Assumption 1.
(i) Each function f((x) is (Lo, Li)-smooth. i.e., [()]](x)]| < Lo +
L. fl for Vx IRd and = 1, I,...,N. N.
(ii) There exists > 0 such that f(xo) - f. < A. where f. is the global optimal value of f.
(iii) For all x E Rd,, EE,-D, (VF((x;)) 6. = (f((x), and [x;(, - Vs((x)]I S a almost surely.
(iv) N EN IV V [x() <
The Assumption (i) means that that the loss function defined on each machine satis- fies the relaxed-smoothness condition, and it holds when we want to train a language model using LSTMs. Assumption (ii) and (iii) are standard assumptions in nonconvex optimization (Ghadimi & Lan, 2013; Zhang et al., 2019). Note that it is usually assumed that the stochastic gradient is unbiased and has bounded variance (Ghadimi & Lan, 2013), but we follow (Zhang et al., 2019) to assume we have unbiased stochastic gradient with almost surely bounded deviation This is an
Remark:
4

---

Under review as a conference paper at ICLR 2022
Algorithm 1 Communication Efficient Local Gradient Clipping (CELGC)
1: for t = ...... T do
2: Each node i samples its stochastic gradient (x;; Et), where Ej ~ D,.
3: Each node i updates it local solution in parallel:
min
? (x) 4DI
VF (x
4: if t is multiple of / then
5: Each worker resets the local solution as the averaged solution across nodes:
N
vi (I,...,NN
(3)
6: end if'
7: end for
stronger assumption than the bounded variance, but it is a normal assumption when encountering relaxed smoothness. Assumption (iv) quantifies the averaged heterogeneity across nodes, which is frequently used in the FL literature (e.g.. Yu et al. (2019a)).
4 ALGORITHM AND THEORETICAL ANALYSIS MAIN DIFFICULTY AND THE ALGORITHM DESIGN
4.1
We briefly present the main difficulty in extending the single machine setting (Zhang et al., 2020) to the FL. setting. In (Zhang et al., 2020), they split the contribution of decreasing objective value by considering two cases: clipping large gradients and keeping small gradients. If communication is allowed at every iteration, then we can aggregate gradients on each machine and determine whether should clip or keep the averaged gradient or not. However, in FL setting, communicating with other machines at every iteration is not allowed. This would lead to the following difficulties: (i) the averaged gradient may not be available to the algorithm if communication is limited, so is hard to determine whether clipping operation should be performed or not; (ii) the model weight on every machine may not be the same when communication does not happen at the current iteration; (iii) the loss function is not T-soooth, so the usual local SGD analysis for I-smooth functions cannot be applicd in this case.
To address this issue, design new algorithm, namely Communication-EEfiiiii Local Gradi- ent Clipping (CELGC), which is presented in Algorithm 1. The algorithm calculates a stochastic gradient and then performs multiple local gradient clipping steps each machine in parallel, and aggregates model parameters on all machines after every I steps of local updates. Note that the naive version of the parallel gradient clipping algorithm in (Zhang et al., 2020) needs aggregates model parameters and gradients across all machines at every iteration, and perform one step of gra- dient clipping operation based on the aggregated gradient. Conceptually speaking, our algorithm is expected to have better performance. The reason is that our algorithm is able to skip communica- tion rounds, and does not need to transmit gradient information across machines (note that it only averages the weights). The remaining issue is that the non-asyne asymptooo convergence guarantees are not established yet. other words, we aim establish iteration and communication complexity for Algorithm for finding an e-ttationary point. We present our main theoretical results as below.
4.2 MAIN RESULTS
Theorem 1. Suppose Assumption I holds and a+ 2 L. Take S min( ALa, 0.1) be a small enough
BL. 1 7 S 2ι( min( ALo BL,) constant and N I min( )- In Algorithm I, choose 1 S 2Ne and the fixed ratio 7 = 5(0 + k), where A 2 1 and B 2 1 are constants which will be specified in the proof. and run Algorithm for = O ( ALg iterations. Then we have
Ne
T
[Xx))l < 4e.
T t=1
5

---

Under review as a conference paper at ICLR 2022
Remark: We have some implications of Theorem 1. When the number of machines is not large (i.e.. . v O(/ee) and the number of skipped communications is not large (i.e., I I O(1/EN)), then with proper setting of learning rate, have following observations. First, our algorithm enjoys linear speedup, since the number of iterations we need to find an e-stationary point is di- vided by the number of machines N when comparing the single machine algorithm in (Zhang et al., 2020). Second, our algorithm is communication-efiicii plexity is T/I = O (ALo (o + x))&==)) "), which provably improves the naive parallel gradient clip- ping algorithm of (Zhang et al., 2020) with ((Lggo /(Ne)) communication complexity when N S O(1ee)
since the communication com-
Another important fact that both iteration complexity and communication complexity only depend on Lo. independent of L1 and the gradient upper bound M. This indicates that our algorithm does not suffer from slow convergence even these quantities are large. addition, local gradient clip- ping is good mechanism to alleviate the bad effects brought by rapidly changing loss landscape (e.g., some language models such as LSTM).
4.3 SKETCH OF THE PROOF OF THEOREM In this section, we present the sketch of our proof of Theorem I and the detailed proof can be found in Appendix B. The key idea in our proof is to establish the descent property of the sequence {f the FL setting under the relaxed smoothness condition, where X; = ,े4 Ei= x is the averaged weight across all machines at t-th iteration. The main challenge is that the descent property of (Lo. I-m-moothh function in the FL setting does not naturally hold, which is in sharp contrast to the usual local SGD proof for L-smooth functions. To address this challenge, we need to carefully study whether the algorithm able to decrease the objective function in different situations. Our main technical innovations in the proof are listed as the following.
First, we monitor the algorithm's 's progress in decreasing the objective value according to some novel measures. The measures we use are the magnitude of the gradient evaluated at the averaged weight and the magnitude of local gradients evaluated at the individual weights on every machine. Please note that our algorithm does not have access to the gradient evaluated at the averaged weight, but it can be served as a proxy in our proof even if we do not have knowledge about it. To this end, introduce Lemma 2, whose goal is to carefully inspect how much progress the algorithm makes, according to the magnitude of local gradients calculated on each machine. The reason is that the local gradient's 's magnitude is indicator of whether the clipping operation happens not. For each fixed iteration t, we define (t) = {i E {1: (x) Ei 2 / and ((t) = {1 : J(t). Briefly speaking, J() contains all machines that perform clipping operation iteration and J(t) is the set of machines that do not perform clip operation at iteration t. In Lemma 2, we perform one-step analysis and consider all machines with different clipping behaviors at the iteration t. By considering all cases together and taking the telescoping sum over f O...., T, we can get an upper bound of the gradient in the ergodic sense.
Second, Zhang et al. (2020) inspect their algorithm's 's progress by considering the magnitude of gradient at different iterations, so they treat every iteration differently. However, this approach does not work in FL setting since one cannot get access to the averaged gradient across machines every iteration. Instead, we treat every iteration of the algorithm as the same but consider the progress made by each machine.
Third, by properly choosing hyperparameters (17 7, I) and using an amortized analysis, we prove that algorithm can decrease the objective value by an sufficient amount, and the sufficient decrease is mainly due to the case where the gradient is not too large (i.e., clipping operations do not happen). This important insight allows us better characterize the training dynamics without worrying too much about the case that where gradient is large(i.e., the clipping operation is performed).
With the idea mentioned above, now we present how proceed with the proof in detail.
Lemma I characterizes the &a error between averaged weight and individual weights at 1-th iteration. Intuitively, the &g error scales linearly in terms of the length of node synchronization interval I.
Lemma 1. Under Assumption 1. fny any and I, Algorithm I ensures || - -xil < 2 holds almost surely.
Lemma 4 and Lemma 5 (included in Appendix A) are some properties of (Lo. L ) -mooohh functions and we need use them frequently in our paper. To make sure they work, need 2 S c/ Ln for

---

Under review as a conference paper at ICLR 2022
some O. This inequality follows from the choice of parameters in Theorem and details will be shown in Appendix B. We denote A 1 1+ e ='= and B =-=1
Let (() be the index set of such that | 4t1l > 2 at fixed iteration i, i... J(() {i e [L....,N] .N] F Et)ll 2 }. Lemma 2 characterizes how much progress we can get one iteration of Algorithm 1, and the progress is decomposed into contributions from every machine
(note that (1) U J()) -1, (1....,N) N) for every l).
Lemma 2. Let [t) be the set defined as above. 2 S c/ for some c > 0,1f ALon S 1/2, then have
[xx))
2%
3y²
7
ALon
E
Σ
V
fxx,)l
(V)
Vf(x)) ALo +
5n
N
iEJ(E)
+B N
Σ
" IV + 1 42
ALon
+
B
N
2
i()(
where A = 6 c'-1 and B 11
Lemma 3 quantifies upper bound of the averaged lg error between local gradient evaluated the local weight and the gradient evaluated at the averaged weight. The upper bound contains the noise term in stochastic gradient a, the data heterogeneity K, and another error term which scales linearly with the length of node synchronization interval T.
Lemma 3. Suppose Assumption I holds. I c/ L1 for some 0, then we obtain
N
Vi /x()))) Sa+ k (ATo + BL, ( almost surely,
where
لنع and B ا-ع
Putting all together Suppose our algorithm runs T iterations. Taking summation on both sides of Lemma 2 over all t 0, T 1, we are able get an upper bound of E [f f (xo)]. Note that [x(rx) - f(x)) 2 - due to Assumption I, so we are able to get a upper bound of gradient norm. For details, please refer to the proof of Theorem 1 in Appendix B.
Et=o E [f(++1)
f(x)]
5 EXPERIMENTS
We conduct extensive experiments validate the merits of our algorithm in realistic settings and find the distributed clipping algorithm indeed consistently exhibits substantial speedup compared with the baseline, which the naive parallel version of the algorithm in (Zhang et al., 2020). We want to re-emphasize that the major difference is that the baseline algorithm needs to average the model weights and local gradients at every iteration while ours only requires averaging the model weights after I iterations and does not need to average the gradients at all. This immediately suggests that our algorithm will gain substantial speedup in terms of the wall clock time, which is also supported by our empirical experiments in this section.
We conduct each experiment in two nodes with 4 Nvidia- V100 GPUs for each node, In our experi- ments, one "machine" corresponds to one GPU, and we use the word "GPU" and "machine" in this section interchangeably. We compared our algorithm with the baseline across three deep learning benchmarks: CIFAR-10 image classification with ResNet, Penn Treebank language modeling with LSTM, and Wikitext-2 language modeling with LSTM. All algorithms and the the training frame- work are implemented in Pytorch 1.4. Due to limited computational resources, choose the same hyperparameters (learning rates, clipping thresholds) according to the best-tuned baselines unless otherwise specified. For more results including small and large batch-sizes, heterogeneous data distribution, and partial participation of machines, we kindly refer readers to the Appendix C. and E.
5.1 EFFECTS OF SKIPPING COMMUNICATION
We focus on one feature of our algorithm: skipping communication. Theorem 1 says that our algorithm enjoys reduced communication complexity since every node only communicates with
7

---

Under review as a conference paper at ICLR 2022
300
Ours
Ours
25
0.0
20
Ours i 10
Ours 1
Tost Acourcyy
0.6
g2.0
Test ACCUUENCS
1.5
Ours 32
Naive Parallel S0DC
Our
Ours
115
Ours 1
1m
1.0
0.4
Ours 1- 16
Dur B
1.0
1-
0.2
Nnive Paraliel SCDCIo
Duss
0.5
02
50
1.00
200
200
20c
400
600
800
1000
Epoch
Epoch
Wallcheck Jime bsscndd)
Wil kic Gime (eecand)
(a) Over epoch
(b) Over wall clock time
Figure I: Algorithm with different I: Training loss and test accuracy v.s. (Left) epoch and (right) wall clock time on training 56 layer Resnet do image classification on CIFARIO.
6.5
200
6.5
200
Ou's --4
Ours i
180
Outs --4
Ours
6.0
Durs -=
Cure
Curs 1
Gurs --2
Ours i
160
Ours -11
Ours +1
5.5
16
180
Curs
Curs
5.0
Ours 22
140
Ours 322
Trahnigg
140
Curs
Neive Penatel SGDCap
120
Nahre Penille Sc23Cap
4.5
120
4.6
100
4.0
100
50
150
202
100
150
12t
18k
6k
12%
18k
Epoch
Epoch
Wulldlock time (eccond)
Wulkdock Lime (sacond)
(a) Over epoch
(b) Over Wall clock time
Figure2 2: Algorithm I with different /: Training loss and validation perplexity v.s. (Left) epoch and (right) wall clock time training an AWD-LSTM to do language modeling on Penn Treebank.
6.5
200
Ou's -
Ours i
180
Outs m-4
Ours
6.0
Curs
Curs =
555
Ours i=
Ours 36
Ours 166
Ours 0
5.5
16
180
Curs
3.
Ours =2
140
Ours 32
140
Perallel SGDCUp
120
Natre Parsilel 360C
4.5
120
an
100
4.0
100
35
100 Esoch
60g
Epoch
Welidlok time (secord)
Welldook time (sncand)
(a) Over epoch
(b) Over Wall clock time
Figure 3: Algorithm with different /: Training loss and validation perplexity v.s. (Left) epoch and (right) wall clock time training AWD-LSTM to do language modeling on Wikitext-2.
other nodes periodically with node synchronization interval length 7. To study how communication skipping affects the convergence of Algorithm 1, we run it with / {2, 4, 8, 16, 32).
CIFAR-10 classification with ResNet-56. We train the standard 56-layer ResNet (He et al., 2016) architecture on CIFAR-10. We use SGD with clipping as the baseline algorithm with a stagewise decaying learning rate schedule, following the widely adopted fashion on training the ResNet archi- tecture. Specifically, we use the initial learning rate 17 0.3, the clipping threshold y 1.0, and decrease the learning rate by factor of 10 at epoch 80 and 120. The local batch size at each GPU 64. These parameter settings follow that Yu et (2019a).
The results are illustrated in Figure 1. Figure Ia shows the convergence of training loss and test accuracy v.s. the number of epochs that are jointly accessed by all GPUs. This means that, the x-axis value is 8, then each GPU runs I epoch of training data. The same convention applied to all other figures for multiple GPU training in this paper. Figure 1b verifies our algorithm's advantage of skipping communication by plotting the convergence of training loss and test accuracy the wall clock time. Overall, we can clearly see that our algorithm matches the baseline epoch-wise but greatly speeds up wall-clock-wise.
Language modeling with LSTM on Penn Treebank. We adopt the 3-layer AWD-LSTM (Merity al., 2018) to do language modeling Penn Treebank (PTB) dataset (Marcus al., 1993)(word
8

---

Under review as a conference paper at ICLR 2022
3.0
Curs 1-
B.8
My
Durt
200
Dars 16
Curs 1 32
Tert Acturecy
Duri
0.6
0.6
Quisi=2
115
Halue Phoelee Sc0cEp
Outs
Relvo Porolid 500C
500c
nopettara
0u151= 6
Durs
0.2
Qura muullm3
0urt] 10
0.5
Naken Persiia S2DCEP
2..00
Mave Virald SGXCkp
bingle UPU SUDLE
45%
80k
100c
Bik
100k
Epech
Spech
(a) ResNet-56
(b) Penn Treebank
Figure 4: Performance v.s. # of iterations each GPU runs on training ResNet-56 on CIFAR-I0 showing the parallel speedup.
Figure 5: Proportions of iterations in each epoch in which clipping is triggered v.s. epochs show- ing clipping is very frequent.
level). We use SGD with clipping as the baseline algorithm with the initial learning rate 30 and the clipping threshold y 7.5. The local batch size at each GPU is 3. These parameter settings follow that of Zhang et al. (2020).
We report the results in Figure 2. Though we slightly fall behind the baseline epoch- in terms of validation perplexity, we do better in training, and gains substantial speedup (2x faster for I = 16) nall-clock-wise
Language modeling with LSTM on Wikitext-2. We again adopt the 3-layer AWD-LSTM (Merity al., 2018) to do language modeling on Wikitext-2 dataset (Marcus et al., 199r) (word level). We use SGD with clipping as the baseline algorithm with the initial learning rate rj = 30 and the clipping threshold 7 = 7.5. The local batch size at each GPU is 10. These parameter settings follow that of Merity et al. (2018).
We report the results in Figure 3. We can match the baseline both training loss and validation perplexity epoch wise, but we again obtain large speedup (2.5x faster for / 16) wall-clock- wise. This, together with the above two experiments, clearly show our algorithm's 's effectiveness in speeding up the training in distributed settings. Another observation is that Algorithm 1 can allow relatively large without hurting the convergence behavior.
5.2 VERIFYING PARALLEL SPEEDUP
Figure shows the training loss and test accuracy v.s. the number of iterations. In the distributed setting, one iteration means running one step of Algorithm I on all machine; while in the single machine setting, one iteration means running one step of SGD with clipping. In our experiment, minibatch size 64 every GPU in distributed setting to run Algorithm 1, while we also use 64 minibatch size on the single GPU to run SGD with clipping. In Figure 4, we can clearly find that even with I > 1, algorithm still enjoys parallel speedup, since algorithm requires less number of iterations to converge to the same targets (e.g.. training loss, test accuracy). This observation is consistent with iteration complexity results in Theorem 1.
5.3 CLIPPING OPERATION HAPPENS FREQUENTLY
Figure 5 reports the proportion of iterations in each epoch that clipping is triggered. We observe that for our algorithm, clipping happens more frequently than the baseline, especially for NL. tasks. We conjecture that this is because we only used local gradients in each GPU to do the clipping without averaging them across all machines like the baseline did. This leads to more stochasticity of the norm of the gradient in algorithm than the baseline, and thus causes more clippings to happen. This observation highlights the importance of studying clipping algorithms in the distributed setting. Another interesting observation is that clipping happens much more frequently when training lan- guage models than image classification models. Hence this algorithm is presumably more effective in training deep models in NL.P tasks.
6 CONCLUSION In this paper, we design a communication-efiiiii distributed stochastic local gradient clipping al- gorithm to train deep neural networks. By exploring the relaxed smoothness condition which was shown to be satisfied for certain neural networks, we theoretically prove both the linear speedup property and the improved communication complexity. Our empirical studies show that our algo- rithm indeed enjoys parallel speedup and greatly improves the runtime performance due to skipping communication rounds in various scenarios.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Ya Alber, Alfredo N. lusem, and Mikhail V. Solodov. On the projected subgradient method for nonsmooth convex optimization in a hilbert space. Mathematical Programming, 81(1):23-35, 1998.
Debraj Basu, Deepesh Data, Can Karakus, and Suhas Diggavi. Qsparse-local-sgd: Distributed sgd with quantization, sparsification and local computations. In Advances in Neural Information Processing Systems, pp. 16668-14679 2019.
Ashok Cutkosky and Harsh Mehta. Momentum improves normalized sgd. In International Confer- ence on Machine Learning, pp. 2260-2268. PMLR, 2020.
Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, aureloo Ranzato, Andrew Senior, Paul Tucker, Ke Yang, et al. Large scale distributed deep networks. In Advances in neural information processing systems, pp. 1223-1231, 2012.
Jacob Devlin, Ming- Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint wxXiv:181000400, 2018.
Aymeric Dieuleveut and Kumar Kshitij Patel. Communication trade-offs for local-sgd with large step size. Advances in Neural Information Processing Systems, 32:13601-1361,, 2019.
Yuri Ermoliev. Stochastic quasigradient methods. numerical techniques for stochastic optimization. Springer Series in Computational Mathematics, (10):141-185, 1988.
Jonas Gehring, Michael Auli, David Grangier, Denis Yarats, and Yann N Dauphin. Convolutional sequence to sequence learning. In International Conference on Machine Learning, pp. 1243- 1252. PMLR, 2017.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochas- tic programming, SIAM Journal on Optimization, 23(4):2341-2363 2013.
Eduard Gorbunov, Marina Danilova, and Alexander Gasnikov. Stochastic optimization with heavy- tailed noise via accelerated gradient clipping. arXiv preprint arXiv:2005.10785, 2020.
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. Local sgd: Unified theory and new efficient methods. In International Conference on Artificial Intelligence and Statistics, pp.
PMLR, 2021.
Priya Goyal, Piotr Dollár, Ross Girshick, Picter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, An- drew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in hour. arXiv preprint arXiv: arXivv:776.008 706.02667, 2017.
Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Lo- cal sgd with periodic averaging: Tighter analysis and adaptive synchronization. In Advances in Neural Information Processing Systems, pp. 11080-11022, 2019.
Elad Hazan, Kfir Y Levy, and Shai Shalev-Shwartz. Beyond convexity: Stochastic quasi-convex optimization. arXiv preprint arXiv:1507.00 02030, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Prateek Jain, Sham Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Paralleliz- ing stochastic gradient descent for least squares regression: Mini-batching, averaging, and model misspecification. Journal of Machine Learning Research, 18:223-1, 2017.
Peng Jiang and Gagan Agrawal. A linear speedup analysis of distributed deep learning with sparse and quantized communication. In Advances Neural Information Processing Systems, pp. 2525- 2536, 2018.
10

---

Under review as a conference paper at ICLR 2022
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. arXiv preprint arXiv::912.044990 2019.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference Machine Learning, pp. 5132-5121100 5143, PMLR, 2020.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identi- cal and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pp. 4519-4529, PMLR, 2020.
Anastasia Koloskova, Sebastian U. Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In Proceedings of the 36th International Conference on Machine Learning. ICML 2019, 9-15 June 2019, Long Beach, California, USA, pp. 3478-3487, 2019.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. unified theory of decentralized sgd with changing topology and local updates. In International Confer- ence on Machine Learning, pp. 5381-5393. PMLR, 2020.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Kfrr Levy. The power of normalization: Faster evasion of saddle points. arXiv preprint arXiv: 1,00431, 2016.
Tao Lin, Sebastian U Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini-batches, use local sgd. arXiv preprint arXiv:1808.07211 2018.
Vien V Mai and Mikael Johansson. Stability and convergence of stochastic gradient clipping: Be- yond lipschitz continuity and smoothness. arXiv preprini arXiv:2102.06488) 2021.
Mitchell P. Marcus, Mary Ann Marcinkiewicz, and Beatrice Santorini. Building a large annotated corpus of english: The penn treebank. Comput. Linguist., 19(2):313-330) June 1993. ISSN
0891-2017.
Ryan McDonald, Keith Hall, and Gideon Mann. Distributed training strategies for the structured perceptron. In Human Language Technologies: The 2010 Annual Conference of the North Amer- ican Chapter of the Association for Computational Linguistics, pp. 456-464. Association for Computational Linguistics, 2010.
H Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, et al. Communicationn-fficccnnn learning of deep networks from decentralized data. AISTATS, 2017.
Aditya Krishna Menon, Ankit Singh Rawat, Sashank J Reddi, and Sanjiv Kumar. Can gradient clipping mitigate label noise? In International Conference Learning Representations, 2019.
Stephen Merity, Nitish Shirish Keskar, and Richard Socher. Regularizing and optimizing LSTM language models. In International Conference on Learning Representations, 2018. URL. https: / /popneevviiw.. net www.://ee/fotmiiteeem. SoooummiddSyyGPPP
Yurii E Nesterov. Minimization methods for nonsmooth convex and quasiconvex functions. Matekon, 29:519-531, 1984.
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. Understanding the exploding gradient prob- lem. corr abs/1211.5006 (2012). arXiv preprint arXiv:1211.5063 2012.
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In International conference on machine learning, pp. 1310-1318. PMLR, 2013.
Matthew E Peters, Mark Neumann, Mohit lyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. Deep contextualized word representations. arXiv preprint crXiv:1802.05363 2018.
11

---

Under review as a conference paper at ICLR 2022
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konevený, Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. ICLR, 2021.
Ohad Shamir and Nathan Srebro. Distributed stochastic optimization and learning. In 2014 52nd Annual Allerton Conference Communication, Control, and Computing (Allerton), pp. 850- 857. IEEE, 2014.
Naum Zuselevich Shor. Minimization methods for non-diferrentiable functiinn volume 3. Springer Science & Business Media, 2012.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587)4484, 2016.
Sebastian U Stich. Local sgd converges fast and communicates arXivv1805.09767, 2018.
little.
arXiv preprint
Jianyu Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of communication-effiieent sgd algorithms. arXiv preprint arXiv:/808.077 070.07776, 2018.
Blake Woodworth, Kumar Kshitij Patel, and Nathan Srebro. Minibatch local sgd for heteroge- neous distributed learning. arXiv preprint arXiv:2006. 047335, 2020a.
Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Mema- han, Ohad Shamir, and Nathan Srebro. Is local sgd better than minibatch sgd? In International Conference on Machine Learning, pp. 10334-10343. PMLR, 2020b.
Blake Woodworth, Brian Bullins, Ohad Shamir, and Nathan Srebro. The min-max complexity of distributed stochastic convex optimization with intermittent communication. arXiv preprint arXiv:2102.01583 2021.
Yang You, Igor Gitman, and Boris Ginsburg. Scaling sgd batch size to 32k for imagenet training. arXiv preprint arXiv: 033888, 6:12, 2017.
Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsich. Large batch optimization for deep learning: Training bert in 76 minutes. arXiv preprint arXiv: 1904.0094. 2019.
Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient mo- mentum SGD for distributed non-convex optimization. Proceedings of the 36th International Conference on Machine Learning, ICMI. 2019, 9-15 June 2019, Long Beach, California, USA, pp. 7184-7193, 2019a
Hao Yu, Sen Yang. and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 5693-5700, 2019b.
Honglin Yuan, Manzil Zaheer, and Sashank Reddi. Federated composite optimization. In Interna- tional Conference on Machine Learning, pp. 12253-12266. PMLR, 2021.
Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non-convex optimization. arXiv preprint arXiv:2010.02519 2020.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. arXiv preprint arXiv: 1881, 2019.
Xinwei Zhang, Xiangyi Chen, Mingyi Hong, Zhiwei Steven Wu, and Jinfeng Yi. Understanding clipping for federated learning: Convergence and client-level differential privacy. arXiv preprint arXiv:2106.1 13673, 2021.
Yuchen Zhang, John C Duchi, and Martin J Wainwright. Communication-effiienn algorithms for statistical optimization. The Journal of Machine Learning Research, (4(1):3321-366) 2013.
Fan Zhou and Guojing Cong. On the convergence properties of k-step averaging stochastic gradi- ent descent algorithm for nonconvex optimization. arXiv preprint / 0/0/22 2017.
12

---

Under review as a conference paper at ICLR 2022
Martin Zinkevich, Markus Weimer, Lihong Li, and Alex J Smola. Parallelized stochastic gradient
descent. In Advances in neural information processing systems, pp. 2595-2603, 2010.
13

---

Under review as a conference paper at ICLR 2022
APPENDIX
A PROPERTIES OF (Lu, L1) FUNCTIONS AND USEFUL LEMMAS
Lemma 4 (Descent inequality in Zhang et al. (2020)). Let f be (Lo. smooth, and c >> 0 be constant. For any X and Xk+1, 1, as long as Xx Xk+1 || S c/ I.,, we have
(xx++1) S f(xx) (Vf((x),, Xx+1 Ik) + ALo BL1 V [ XR+1
xx|1?
(4)
where A E11 and B = E-11
Lemma 5 (Zhang et al. (2020)). Let f be (Ta, L L-m-moothh, and c > be a constant. For any X and X as long as || Xk+1ll S cf L1, we have
[Vf(x=-1) - fx(xx)) $ (ALo + Bf |x++1
xxll.
(5)
where A = 1=1+6 - e-1 and B E-1
Lemma 6 (Zhang et al. (2020)). Let 2 0 be real constant. For any vector and u,
u, v) v
-u||ul| (1 A)lvll + (1 p)ll - ull.
(6)
B PROOF THEOREM
During the proof of Theorem 1, we need the following simple fact for our algorithm.
Fact Recall the definition of & N EN x for a fixed iteration t, Algorithm immediately
1
gives us X++1 Xx holds for any t.
N En im min 1/ [VPA
(.(( Ef), and hence |x++1 xx|1² S 7
B. PROOF OF LEMMA
Lemma restated
Under Assumption 1, Algorithm ensures
|x x;|l < 2yI, Vi, Vt almost surely.
Proof. Fix t 2 1 and i. Note that Algorithm I calculates the node average every I iterations. Let to S t be the largest multiple of I. Then we know Xt., x for all (Note that t to S I). We further notice that
x;
X1o
Σ
min 1/ VVF.
VF((s,
By the definition of X,, we have
x; Xto
Σ
min 1 "iivir
N
14

---

Under review as a conference paper at ICLR 2022
Thus, have
X x
N
- Σ
min
1/ (V[V,[(x; EII
min
N
T=ta
==1
N
2
Σ
1/
7 (x; E
+2
min
"
[IFF,(((( +Xl
(x2
N
5 - to)
Σ min
77. [V (XF EIII
VF((1)))) 56)
2(t - to)
Σ
Σ
N
min (" [VEE E/)
(F 5t)
N2
r=to
T=to
V F +
2
2(1 10)
[-1
(F 4)
2 - 1o) Σ
N
Σ
?
[ 1
N
(x²
t=
2(1 - to)
22,21 S 4.
Σ
N
1=
(8) The technique we mainly use in this proof is the inequality || Eド 21 S K K Izz 1 for any K vectors ,k....,Kk. Taking the square root for both sides, then we obtain the desired result. O
K
K
B.2 PROOF OF LEMMA 2
Note that J(t) = {i E [L...., N] [X) +| 2 331.
Lemma 2 restated If ALo s 1/2 and 2 S L/L2 L1 for some > 0, then we have
[if(x++1)
f(x))
E Σ
2%
[Vf(((]]
3y²
7"
vf(x:)] ALo? +
B |||
57
(E)(E)
ALonio² N
BL B f(x))]
Σ
E
1
[((())) 2 12
12 1BIV/.))
N
kEJ(()
where A=1+ e
+اع and B 3= E-1
Proof. By the (La, In) -smoothness and invoking Lemma and noting that ||x - xell S 7 for any E, we have
E (x(++1) fxx:]
EV( ), 8441 xx,) (ALO + BLI [V
< E
E E| - xx,1²
2
5- yB
1
[ Vf((i))
VFI(() Ef
-nE
Σ VF)( E)), v/(())
(9)
(EJ(C)
iEJ(1)
ALo E||x,111111 - 12 + ((x))( +
2
For each iteration
first consider the case where J(t), i.e. [[VF(()) 7- We use
Lemma 6 with μ = 2 to obtain the following result
V.. xx e.), f((x))
< 1511
1
27
322
+
7
5 v.(x.))
(10)
5n
5
15

---

Under review as a conference paper at ICLR 2022
Taking the expectation for both sides of above inequality, then we obtain
Σ (EJ(C)
(F((), (+I
Vf(x))
$
Σ (EJ(()
27 5
fxxx)l
372 77 5m 5
+
[F((()))) vs(x))]]
N
N
(11)
Next, we consider the case which i E J(t), ie. elt-1] by the o-algebra generated by all random variables until (t - 1)-th iteration, i.e., g(t
(VF stIl S 7 at fixed iteration t. Denote
(E)...., 56", 1.60......0'
.t.....,1".... _ ................................ We notice that
E
[
E [(OI]]
5-11) 1
Σ
vs(x,)
= -nllE
E
Σ
VPP(
V (xx))
N
N
N
N
iEJ(t)
[J(OI]
E
E
Σ (..(()..))
glt-2]
vf(x))
N
N
(EJ(I)
N
E
[[((t]]
)
E
E
Σ
(F
VF
E J(t))
(/c-1)
N
N
(4)
T
Pe (.())
E
[1(0
VS(S))
N
N
E [ITO0
E [[(0]]]
(
E
fx((x))
+
P (1
ps V
2
N
(E)J(()))
(xx))
7E
P: ((((())))
+ E
pc (V)(z)) v(((Et)
2N
2
{t))
1 N
n (E]J(())
2N2
E
f(x)))
V
- BB
2
N
Σ ()()))
2
N2
E
[V VS(()))
T(O)22))
+ " (E)
E
-"P
7
Σ
p.())(
E
T2 (ALo + (f
2N2
N
2 N2
(E)
E
(x)))
"E
1
Σ
(
n (E]
E E (2AP1A + 2B² 1
2N2
2
N
2 N2
S (E)(()) 2N
(E ({))2
7
N Ps (
E 24 + 4-2 [x)
2
N2
(12)
where (a) holds due to Lemma 8 with A, VF((1: B, T(i J()).0 < 1 is the corresponding constant defined in Lemma 8 and ΣN P = [I(0): (b) holds by using the basic identity (x1, = -/4 (||x 1|2 + +||x||| - ||x: X2 I2) for any two vectors x1, X2: (c) holds due to Jensen's inequality and E Ps EJJ()). (d) holds due Lemma and Lemma 5, (e) holds
since (a + 6)2 < 2a² + 2
16

---

Under review as a conference paper at ICLR 2022
Next, we compute E||x+11
x1l?. By definition, we have
N
B|| x
x=11==1
E
min 1/ IVP. EiIl
(B((2,
N
N
VR +)
N
E
Σ
min
13 (x): EDIl
VE 4
= No
1
7 Σ
[VE
+n Σ (
(EJ(I)
iEJ())
1
V (x + V I
1
$
+ 2
(II J(t))
N
N
iE)(
272
( +
N N
N VR
+ 2
vn(( J(O) -E
(I
N2
[x;; 1
N
AEJ(L)
+ +27
E
VE J(()
(0) 2y² (B)(())
1 N
N
+ 21
V.
E
v (i((x
+ +21
E
Σ
N2
N
N
(1)(())))
2n202
1 N
+ +2²²
E
Σ
(F
N²
N
N
( 27 (B
2z
Σ Ps V )
N
+27²
E
N2
N
(13) =i( e J()): (b) holds due to
where (a) holds due to Lemma 7 with A, = V.((); B, =
Lemma 8 with A, = Fx 4t,, B = T(i E J(t), 0 S p S 1 is the corresponding constant
defined in Lemma 8 and Σ P E [J(I]]
Substituting (11), (12) and (13) into (9) yields
E (x++1
fxx)]
2%
3y²
77
nET((t)
E Σ
[x,(,
+
E
[x
N (E)(1)
5n
5
2N
7 N
1 N
BJJ(1)
E
P.
E
[4 L2 - 4,2 23 V (xx))1
2
EJJ(()
E
N
N
ALo (E)
AL
Σ E2. CRAAA(1)) )(
N
BL [xx,)|
+ ALO
E
N2
N
2
E
27
[+(x)||
3y2
Thi
T
I
( vf(xa)I + ALO + B
ALonz
N
5n
N
(t)(
ALonpo2
B
E
Σ
+
442
+
N
2
TEJ(t)
(14)
where the last inequality holds if ALon S 1/2 and 2 ||XI||2
17

---

Under review as a conference paper at ICLR 2022
B.3
PROOF OF LEMMA
Lemma restated
Suppose Assumption
holds. 1f & c/ L1 for some > 0, then we obtain
VF (x) V((x))| Sa+ Sot BL
almost surely,
where A 1 e e-11 and B = e'-1
Proof. By using triangular inequality and Lemma obtain
[VFF(()))) (f()))
$ [ VS((x)I +[V + vs(()))
- o + [V(x) V (ALo + (()
Summing over i = to N and by Assumption 1, we have
VF - vx(x)|| <o Sotk+t 241(ALo + BLI
B.4 MAIN PROOF OF THEOREM
Proof. We consider < 6 S min( Ala Bl. 0.1) be small enough constant and choose S 28( min < BI, ). ratio 7/n 5(0 and I I 2Nr first
14ALo ), 7 minf? ee 5BI.e
Nr
check several important conditions which were used in previous Lemmas and we will use in our later proof.
Ne
(a)
(6)
1
ALon S ALa
5(0 + K) 28(a + K) AL 140( + x)²
140
where (a) holds because of Ne < 1 and (b) true due to o + K 2 Note that Ne $1
A 2 1, B 2 1, and so we have
Ne
2T 2
28( + R) BL, 2Nc S
28L
L1
where
Recall the descent inequality (Lemma 4), explicitly define
11/28
A 1 1 1/28/28
1/28
2/228
1/28
We can show that choice of guarantees that ALe < BLr Then, the upper bound of the 2ea
parameter 7 becomes 2-
Based on Lemma 2 and Lemma 3, we take summation t
18

---

Under review as a conference paper at ICLR 2022
and obtain
E
1(++1)) ((xi))
(a)
E
[P + P21 Vf(x
(EJ(()
ALo
(xx)))
Σ
Σ
+
N
2
(E)(
(6) T-1
E Σ
P + Pal Vxlx
N 1=
(E(())
T-1
ALoro
Σ
Σ
+
N
N
2
(EJ(()
(15)
where (a) holds due to Lemma 2, and
322 77
14y
ALonfo²
P1
(a
k)) +
ALo7?
5n
5
5
N
P2 2y
IBT
Bl,
5
2
(b) is derived by computing
LB*L
28 A
42212B21315 < 28 + A2)
(16)
28 (a + x:) A2T.3 25B2T1e
4
bound of Na bound of fa
with N s min L
14ALB 5BL.e J. 7 S 28(a+e)) minf Alo BLg } and I S 2Nc
Now we give the upper bound of P1 and Pz.
N₂² From the choice of N I min 1 14ALo }. 7 S 28ALa(o+H))
: 5BL1c
1 S 2Ne and the fixed ratio 3 =
5(a + nt,, and noting that + k 2 1, we have
3 + k)
7
e
E
7/0 + k)) + ALorro²
P1 <
5(0
+
(o + k)
+
+
5
5
5
20
28
10
N
(17)
2
1
P2 <
+ +
~
7
5
20
10
10
Plugging (17) back to (15), we obtain
1
+ - Σ Σ v(sl)
T-1
-A - - S.) s ES(xT) - 1(x0) S E
U(x.)
(E)())
te)(
where
7a + k)+ + ALOTPo²
3
Uxx.)
1 (x.))l
10
10
N
12 + ALoTNo2
V(x.)
2
N
2
(0)
TE
BLI ||
2 12 + AL n T002
5 2
2
(6)
< 4
17
|V/(
+
TJE2
2 A 12 + ALO 12
4
19

---

Under review as a conference paper at ICLR 2022
300
Ours
Ours
6.8
255
20
Durs 1
Durs i 15
Text Accarocy
6.6
g2.0
Test AcCuEeNC
1.5
Navv Paralee S0DC1p
Ours 32
Duns =
Ours m-4
115
Ours 1
1m44
1.0
444
Ouns 16
Duns =
100
1-
C22
Ours
Porallet SCDC
0.5
0.
100
150
500
750 1000 1250
500 750 1000 1250 1520
Epoch
Epoch
Wallskokk Jine Isscnnd)
Wark toc unee (eccand)
(a) Over epoch
(b) Over wall clock time
Figure 6: Training loss and test accuracy v.s. (Left) epoch and (right) wall clock time on training a 32 layer Resnet do image classification CIFARIO.
Inequality (a) follows by using the standard inequality x² > 2cx - c² and (b) is true because
1/E
BLT
TJE
(18)
2
2
To check (18), compute
BL BLi5n(o 8)
Ne²
11
5BL
77E
(19)
28ALo + k)
28ALo
2
where the last inequality holds because we assume N S 14ALa 5BLiC*
It's clear that Uxx) - Vxx). Then we obtain
Vf(x)l+ TE²
772 ALu
x022
- < (Ef(x)) f.) < E
Σ V(K))
E
+44
N
t=
Then we rearrange above inequality and get
4A
4ALONO
16
E [|Vx(l
+e+
+
4e,
T
Ne
long T 560Ato&(o+N) and I
2NC
C EXPERIMENTS DETAILS AND OTHER RESULTS
C.I CIFAR- CLASSIFICATION WITH RESNET-32
Apart from the 56 layer Resnet used in Section we also trained the 32 layer Resnet on CIFAR-IO. Here, used smaller minibatch size of 16 per GPU. We also used SGD with clipping for the baseline algorithm with a stagewise decaying learning rate schedule, We set the initial learning rate v 0.1 and the clipping parameter 7 1.0. We decrease both vj and y by factor of 10 epoch 80 and 120. These parameter settings follow that of Zhang et al. (2020).
Results reported in Figure 6 again shows that algorithm can not only match the baseline in both training loss and test accuracy epoch-wise, but is way better in terms of wall clock time for moderate values of I.
D USEFUL LEMMAS
Lemma Suppose {Ai is an sequence of vector-valued independent random variables, N is sequence independent random variables where B, E {0, 1) for every i. Suppose
E
< +00 for every i. Then we have
N A,B. - E
N
N E
N
E
A,B,
A
A
N
N i=1
N 1=1
N
1=1
20

---

Under review as a conference paper at ICLR 2022
Proof. It suffices to show that E I, [|,l < EIJ, E[ since both {A,B, E B, N and {A, - E [A,]]=
N 1= are sequences of independent random vectors with zero mean. Define C3 1 B;, and hence B 0 with probablity 1. Without loss of generality, we can
assume E [A.] = O. Note that
E A| E [A.]I = BIIA, A.C. BII.B. - + E A.C. + 2B,A, A.C.)
= A. 2 + TE |IA.I| 2 BII = = A
B [[ 2 + (A,
2 E || - E [,].
It completes the proof.
Lemma 8. Suppose { is an sequence of vector-valued independent random variables,
(B: is sequence of independent random variables where B; E {0,1] 13 for every i. Ag and Bj are independent of each other if + j. Then there exists (p)...., where O S pi S 1 and
Σ P; = -E B,) such that
N L P.A,,
E
Σ A
(20)
J. Proof. Without loss of generality, we can assume the sequence [B: sorted in a decreasing
order, i.e., B, 2 B2 2.. 2 Bx, since otherwise we can switch the order of summation in both LHS and RHS of the Equation (20).
Define T = sup(11 s N B, = 1}, and define F, = AI,.,AA,. Bs), where (-) denotes alalgebra generated by random variables in the argument. Since (T= 8) E Fa for all 8, know that 7' is stopping time, and T < N almost surely. Hence we have
N
E
A,B
=
E
A
=
E
Σ
ATT 2
-ΣE E E ATTTT
2 ))
L==1
Note that 2T' = 1 I[T
Si
1)
F. 2. and A; independent of Fe-1. we know that
+00
+
+oc
N
Σ
E
E
AT 2 F) |] = Σ
T ž 1) [4.]]
Σ R [A.] Pr T 2 Σ
[[AA]P((T 2 1).
-=1
Define p. = Pr(T 2 i), we have 0 S p4 S 1 and
Σ p.
B(T) = E ΣN B,
Hence (20) is
proved.
E MORE EXPERIMENT RESULTS
E. PARALLEL SPEEDUP ON NLP TASKS
In Section 5.2 we have shown the parallel speedup effects of our algorithm on training a Resnet model on the CIFAR10 dataset. Here we present the same phenomena but on training AWD-LSTMs on doing language modeling on Penn Treebank and Wikitext-2 in Figure 7.
Again, note that in the distributed setting, one iteration means running one step of Algorithm 1 on all machine; while in the single machine setting, one iteration means running one step of SGD with clipping. For Penn Treebank, we minibatch size 3 every GPU in distributed setting to run Algorithm 1, while we also use 3 minibatch size on the single GPU to run SGD with clipping. For Wikitext-2, the corresponding minibatch size is 10.
Figure/ 7 again clearly shows that even with I > 1, our algorithm still enjoys parallel speedup, since our algorithm requires less number of iterations converge to the same targets (e.g., training loss, validation perplexity). This observation is consistent with our iteration complexity results in Theorem 1.
21

---

Under review as a conference paper at ICLR 2022
6.5
200
6.5
200
Curs
0-m
180
6.0
180
Durs 16
160
Oum
5.5
0L15
184
0.m
0.15 16
5.0
Nehe Perelle 5230pp
Cus 32
Neku Feredel SCDC
OL1S 32
3.0
Nale Parale sgpcip
Dum 12
140
0um i 12
Nove Forolie 59pcIp
Sligh OFU 5000
Single GPU 500dp
4.5
Single GPU
Single GPU SGDC
100
35
35
5 200k 4005 5006 Bilk
Im
1aam
60
200h 4006 Bo0k BiOk 1% 1.2m
200k
400%
500k
B0Ds
Im
200x
4006
500k
800k 1m
(a) Penn Treebank
(b) Wikitext-2
Figure 7: Performance v.s. of iterations each GPU training AWD-LSTMS do language
modeling on Penn Treebank (left) and Wikitext-2 (right) showing the parallel speedup.
10
Gradient 12 Norm
Ours = 2
10-1
0
50
100
150
200
Epoch
Figure l norm of gradients over epoch on training ResNet-56 on CIFAR-10.
E.2 GRADIENT NORM DYNAMICS
The careful reader might notice that in Theorem we require N S (?) where is the desired & norm of the gradient when converging and wonder if this is too strict and impractical.
Therefore, we draw the dynamics of the l2 norm of gradients over epochs for training the Resnet-56 model to do image classification on CIFAR10 10 in Figure 8. It can be clearly seen that the gradient l2 norm decreases to less than 0.1 after epoch 100 and eventually reaches around 0.06 at the epoch 200. Since 1/0.06 Rs 17, this means that the N = 8 setting used in our experiments is consistent with our theory.
E.3 HETEROGENEOUS SETTING
In the previous experiments, all machines access the whole dataset. Yet, in prac- tice, each machine might only access a subset of the whole dataset and the data might be evenly distributed across machines. Therefore, ment on this heterogeneous setting. Specifically, we take the Penn Treebank training set which is a text file and divide into 8 non-overlapping consecutive parts which contain (10.64%, 11.17%, 11.70% 12, 12.77% 13.30%, 13. 83%, 14.36%) of the whole text file re- spectively. We then train the AWD-LSTM of the same structure in Section 5.1 to do language modeling. Considering that the heterogeneous setting introduces big difference compared with the setting we adopted in Section 5.1. we finely tuned the initial learning rate for both the baseline and our algorithm and picked the one that gives the smallest training loss.
conduct experi-
The results are reported in Figure 9. Note that, as the size of training data each machine is different, we draw the training and testing performance curves over the number of iterations each machine runs instead of epochs. This means that, if the x-axis value is 1000, then each GPU runs 1000 iterations. We can see that, though the unbalancing and heterogeneity of the training data deteriorates the performance for both the baseline and our algorithm as compared with Figure 2a, algorithm is still able to surpass the baseline in training losses though it falls slightly behind in testing; meanwhile, our algorithm obtains significant speedup in terms of wall-clock time. This suggests that our algorithm is robust to the heterogeneous setting.
22

---

Under review as a conference paper at ICLR 2022
200
6.5
200
180
Oursi
Ourst
Curs 1
Durkim
150
Curs 124
G m
Ours1
Oatel 11
100
Outs 16
Ours1
5.5
Curs -
Curs - 16
Curs 1
Curs =
5.0
Ouesl
Curst 32
5.0
12
140
Curs 32
Nalve 5CDCrip
Notve Peralee Sc00
Naice Parn SCRCie
120
Nalue Panslee SC0Clp
100
4.0
100
80
0k 20k
40k. 63k Iteratiion
50c.
100L 125k
0k
23k
40% 60k 30 100h
1256
34.
66
96.
15%
18h
21k
12: Walkiock (wessnd)
56
Ieeret
Welktlock Unn und
(a) Over epoch
(b) Over Wall clock time
Figure 9: Training an AWD-LSTM to do language modeling on Penn Treebank in a heterogeneous setting where each node accesses only different subset of the whole dataset.
6.5
200
Outs
6.0
130
220
Ours
Ours
160
Oum
215
Natve Paraliel S00C
Ours1
5.0
Ours
Natve Perallel SGOCH
Nave Paro SC0CIp
Oum
0.5
Nawe Peratel Sta3Cle
35
Communcation
Communication
Communication
(a) CIFARIO
(b) Penn Treebank
6.0
160
140
4.5
S00C
120
S00C
25k
Communiction rouncs
Commun Catlon rounds
(c) Wikitext-2
Figure 10: Performance v.s. # of communication rounds each GPU conducts on training (a) Resnet- 56 on CIFARIO (b) AWD-LSTM on Penn Treebank (c) AWD-LSTM on Wikitext-2.
E.4 PERFORMANCE VS. COMMUNICATION ROUNDS
The reader might be interested in how the training and testing performance changes w.r.t. the number of communications each machine does for both the Naive Parallel SGDClip and our CELGC with different I. Thus, we show such results in Figure 10. The results very close to that w.r.t. the wall-clock time which is as expected.
E.5 PARTIAL PARTICIPATION
In the previous experiments, when communication between nodes occurs, all nodes send their model and/or gradients for averaging and update accordingly. Yet, in practice, it might be that only a (dif- ferent) subset of nodes participate in communication each time. Therefore, we conduct an exper- iment on this setting. Specifically, we take the Penn Treebank dataset and train the AWD-LSTM of the same structure as in Section 5.1 to do language modeling. However, when the algorithm requires communication across nodes, we randomly select 6 out of the total 8 nodes to commu- nicate and average the model and/or gradient and update those 6 nodes only; the rest 2 nodes will be left untouched. Considering that this setting introduces big difference compared with the setting adopted in Section 5.1, we finely tuned the initial learning rate for both the baseline and our algorithm and picked the one that gives the smallest training loss.
The results are reported in Figure 11. We deteriorates the performance for both the baseline and our algorithm as compared with Figure 2a, algorithm is still able to closely match the baseline for both the training loss and the validation
that, though the partial participation setting slightly
23

---

Under review as a conference paper at ICLR 2022
200
6.5
200
Gurs
180
Durs
Durs
Ours m
Curs -
150
Curs --44
Curs m
55
Ours =
Gurs =6
100
Ours 1 8
Duns 1- 16
5.5
Curs -
10
Curs -
Curs 1b
500
Ours i
Ours i 32
5.0
12
2 140
Curt 12
Naive Poralld S02CXp
120
Nave Faralel SCDCIp
4.5
Fora 5o0Cle
120
Nalve Paralee
100
4.0
100
50
100
150 Epocs
200
250
100
150 Epoch
200
250
02
9t.
13k
18k
60g
06
10c
Wallclock time (second)
Walidlck time (second)
(a) Over epoch
(b) Over wall clock time
Figure 11: Train an AWD-LSTM to do language modeling on Penn Treebank where only a subset of nodes participate in each communication.
30
Ou's 2
Gurs m-44
0.0
20
Ours -6
Ours i
Recusery
06
Ours 2
Toliing 169
2.0
Teet Accureey:
15
SGDCIp
Ours
1.5
SoDCle
1.0
0.4
Ours =8
Ouncl
0:2
8.
02
SCDCip
0.0g
Cpoch
Epoch
Wallclock time (sccond)
Walc tine (sccond)
(a) Over epoch
(b) Over wall clock time
25
Outs
Oum
0.8
2.0
Oura
Test Accuricy
Single 5500
1.0
Ourt 16
Ouris -2
0.5
0.2
Farailal SCDCEp
Terasions
Itarations
(c) Over of iterations each GPU runs
Figure 12: Algorithm with different I: Training loss and test accuracy v.s. (a) epoch, (b) wall clock time, and (c) of iterations each GPU runs on training 56 layer Resnet do image classification on CIFAR10.
perplexity epoch-wise, but also note that our algorithm greatly saves wall-clock time. This indicates that algorithm robust in the partial participation setting.
E.6 LARGE MINI-BATCH
The distributed learning paradigm is especially desirable with training using large mini-batches. To this end, we trained Resnet-56 model on CIFAR10 with batch-size 256 on each node which sums up to batch-size of 2048 globally. Compared with the experment in Section 5.1, considering the large batch-size, we trained for 300 epochs instead of 200, decrease the learning rate by a factor of 10 at epoch 150 and 250, and finely tuned the initial learning rate for each variant and picked the one that gives the smallest training loss. Results are shown in Figure 12. Similar to small batch case reported in Figure 1, our algorithm with skipped communication is able match the naive parallel SGDClip in terms of epochs but greatly speeds up wall-clock-wise. Also, Figure 12c again verifies the parallel speed-up property of algorithm.
24


Reviews:
[{"review_id": "wY8_OnbaZo-", "reviewer": "Reviewer_nQu7", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "## Strengths\n1. **Motivation and clarity.** The paper is well-motivated and easy to follow. The authors also provide a sketch of the proof in the main text which is useful.\n\n2. **Related work** section provides a good summary of existing works relevant to the topic. However, Table 1 is not accurate and should be improved (see **General questions and comments** below).\n\n\n\n\n## Weaknesses\n1. **The proofs contain mathematical mistakes that break the main result of the paper.** In the proof of Lemma 2 the authors rely on the following formula (page 15, the third step at formula (12)): $\\mathbb{E}\\left[ \\sum_{i\\in \\overline J(t)} \\nabla F_i(x_t^i, \\xi_t^i) | \\xi^{[t-1]}\\right] = \\sum_{i\\in \\overline J(t)} \\nabla f_i(x_t^i)$. This is not true since the set $\\overline J(t)$ depends on the stochasticity at iteration $t$ of the algorithm. Moreover, the authors repeat this mistake several times throughout the proof when \"move\" the factor $|\\overline J(t)|$ outside the expectations (e.g., later in the same formula and also when applying (12) to (9) in (14)). Due to the same issue, one cannot use second-moment representation in the fourth row of the formula (13). Finally, even if we assume that everything is correct before the last step in formula (13), there is another issue: in the last row of (13), the second term should be $2\\frac{\\eta^2 |\\overline J(t)|^{\\color{red}2}}{N^2}$. Therefore, in the final bound, instead of the term $\\frac{AL_0\\eta^2\\sigma^2}{N}$ one should have $AL_0\\eta^2\\sigma^2$. As the result, in the last upper bound from the proof of Theorem 1 the third term should be $\\frac{AL_0\\eta^2\\sigma^2}{\\epsilon}$ instead of $\\frac{AL_0\\eta^2\\sigma^2}{{\\color{red}N}\\epsilon}$. Therefore, the number of iterations $T$ is not proportional to $\\frac{1}{N}$, i.e., **linear speed-up is not proven**. Since it is claimed as one of the main contributions of the paper, the described issue is a very strong reason for the rejection of the paper.\n\n2. **Assumptions on the parameters in Theorem 1** are strong and not well-defined for some special cases. First of all, the condition $N \\leq \\frac{1}{\\epsilon}$ is strong and in FL-applications, where $N$ can be large, it is typically satisfied for very small values of $\\epsilon$, meaning that the problem should be solved with too high accuracy. In practice, it is often sufficient to solve the optimization problem with not too high accuracy. Next, the authors also assume that the number of local steps between two subsequent communications satisfies $I \\leq \\frac{1}{2N\\epsilon}$. Since $I$ is a positive integer one should have $N \\leq \\frac{1}{2\\epsilon}$. So, in fact, it means that either $\\epsilon$ is extremely small, or $I = O(1)$, or $N$ is small. The drawbacks of the first and the third options are covered above. The second option describes a theoretically simple case since the number of local steps is small. Moreover, in this case, $N\\epsilon = \\Omega(1)$ meaning that the derived communication complexity bound is not better than for Naive Parallel SGD with clipping. Finally, the assumptions on $\\gamma$ and $\\eta$ are not well-defined when $\\sigma = 0$ and $\\kappa = 0$: the condition $\\frac{\\gamma}{\\eta} = 5(\\sigma + \\kappa)$ implies that $\\frac{\\gamma}{\\eta} = 0$ in this case meaning that either $\\gamma = 0$ (no clipping) or $\\eta = \\infty$. This means that the assumptions on $\\gamma$ and $\\eta$ are incorrect.\n\n3. **Numerical experiments** are conducted for the system with $N = 2$ workers, which is a too small number to demonstrate parallel speed-up properly. Moreover, it would be better to show the dependence on the number of communications rounds in the experiments. Moreover, to have a fair comparison of the method with local updates and the method without them (Naive Parallel SGDClip) one should use I times larger batchsizes for Naive Parallel SGDClip. It seems that the authors used the same batchsizes for local and non-local methods for each iteration.\n\n\n\n## General questions and comments\n1. **Page 2, \"... and hence is communication-efficient\".** This sentence should be rewritten since in the current form it implicitly says that local steps ensure communication efficiency. In fact, it is not true for highly heterogeneous or arbitrary heterogeneous cases (e.g., see Woodworth et al. (2020a) and Gorbunov et al. (2020)).\n\n2. **Table 1** requires clarifications. First of all, Ghadimi & Lan (2013) do not use the bounded gradients assumption. They derive the results under classical smoothness and bounded variance assumptions. This should be explicitly stated either in the table or in the caption of the table. The complexity guarantee should contain two terms: one is proportional to $\\epsilon^{-2}$ and the second one is proportional to $\\epsilon^{-4}$. Moreover, their result can be easily generalized to the naive parallel settings without any assumptions on bounded data. Secondly, in the current form, the complexity bounds for the methods are incorrect for the special case when $\\sigma = 0$ or/and $\\kappa = 0$ since the terms with better dependence on $\\epsilon$ are omitted. This should be fixed. Next, the table should contain the results for Local-SGD under the classical assumptions to have a clear comparison (e.g., from Koloskova, Anastasia, et al. \"A unified theory of decentralized SGD with changing topology and local updates.\" International Conference on Machine Learning. PMLR, 2020). Finally, I have not found the rate presented in the row \"Naive Parallel of (Zhang et al., 2020)\" in (Zhang et al., 2020). This should be clarified (ideally, rigorous proof should be provided).\n\n3. **Missing references.** I believe the authors should at least mention the work Reddi, Sashank, et al. \"Adaptive federated optimization.\" arXiv preprint arXiv:2003.00295 (2020) since this paper considers very relevant methods such as Federated Adam.\n\n4. **Assumption 1 and the remark after it.** Assumption (iii) is too restrictive: it is not satisfied for the noise with the unbounded domain such as Gaussian noise. The authors claim that \"it is a normal assumption when encountering relaxed smoothness\". However, this claim is not explained. I do not see any evidence of why this assumption is reasonable in this case. I understand that it is used in prior works, but I guess it is because of the difficulty of analyzing the methods under relaxed smoothness. Next, assumption (iv) is also quite restrictive. For example, in the convex case, one can analyze Local SGD and its variants without this assumption. I understand that in the non-convex case it is used in prior works, but it is better to write about this explicitly.\n\n5. **Page 5, \"... our algorithm is expected to have better performance.\"** This is not true when $\\kappa$ is large: even Local SGD does not benefit from local steps in this case.\n\n6. **Additional comments about Theorem 1.** Assuming that the formula for the communication complexity is correct, it is still not clear why it is better than the mentioned complexity of Naive Parallel SGD with clipping since $\\kappa$ can be large.\n\n7. **Page 6, \"Another interesting fact is that both iteration complexity and communication complexity only depend on $L_0$.\"** Most likely it means that the authors just omitted some important dependencies in the complexity estimates.\n\n8. **Page 18, lower bound for $T$.** The detailed derivation should be added after fixing all mistakes in the proof.\n\n\n## Minor comments\n1. **Lemma 2, \"If $2\\gamma I \\leq c/L_1$ for some $c > 0$, then $\\gamma \\leq 2\\gamma I \\leq \\frac{c}{L_1}$\".** This is a trivial statement.\n\n2. **Page 14, \"For each iteration $t$, We\"** $\\longrightarrow$ \"For each iteration $t$, we\"\n\n3. **Page 15, \"and (b) holds due to Lemma 1 and Lemma 5\"** $\\longrightarrow$ \"and (d) holds due to Lemma 1 and Lemma 5\"\n\n4. **Lemma 3 restated, page 16:** in the RHS one should have $\\|\\nabla f(\\overline x_t)\\|$\n\n5. **Inequality (17), the second part**: dependencies on $\\sigma + \\kappa$ are missing.\n\n6. **Page 18, definition of $V(x)$:** $\\widetilde{A} \\longrightarrow A$", "summary_of_the_paper": "The paper proposes a new variant of SGD with clipping and infrequent communications (local updates) called Communication Efficient Local Gradient Clipping (CELGC) aimed at solving non-convex federated learning problems under the generalized smoothness ($(L_0, L_1)$-smoothness) assumption. The authors derive ergodic convergence guarantees for the convergence of CELGC to the first-order $\\epsilon$-stationary point assuming additionally that the noise in stochastic gradients is bounded with probability $1$ and heterogeneity of the local data on clients is also bounded. Although the authors claim that their result shows that CELGC achieves linear speed-up and has better communication complexity than the naive version of parallel Clipped SGD, the proofs contain several significant inaccuracies making the main result of the paper incorrect in general. Moreover, several assumptions about the parameters such as the number of workers $N$ and the number of local steps between two consequent communication steps $I$ are restrictive.", "summary_of_the_review": "To sum up, several parts of the proof should be corrected and the theory should be extended to support more general choices of $N$ and $I$. Moreover, several parts of the paper such as the comparison of the known complexity results with the derived ones and numerical experiments require improvements.\n\nUnfortunately, the current version of the paper cannot be accepted to the conference. If the authors resolve the mentioned issues during the rebuttal, I will increase my score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Knxgf1OMRP", "reviewer": "Reviewer_oVjB", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "Gradient clipping has become a de facto approach in training the deep neural networks especially for LSTM and Transformer. When communication bandwidth is limited and sharing gradient can leak privacy in federated learning, global gradient clipping is impractical. In this case, practitioners use local gradient clipping as workaround. However, there is no theoretical understanding on this approach, This paper bridges the gap between theory and practice. Overall, I think the paper is well written and easy to understand. But the contribution is incremental. In addition, I have a few comments regarding theory and experiments:\n\n1. Theorem 1 holds when $N \\leq O(1/\\epsilon)$ and $I \\leq O(1/(\\epsilon N))$. On one hand, if we need to use many workers such as $N = 1/\\epsilon$, then $I \\leq O(1)$, which means there is no local iterations at all. On the other hand, if we just need a rough solution (e.g., a moderate $\\epsilon$), which is typically the case in deep learning, then $N$ has to be small. It seems to me the theory does not apply to common cases in practice. It is good to plot the norm of the gradient to see how many cases in the experiments satisfy the assumption.\n\n2. All the experiments focus on homogeneous local data in classic distributed settings. There is no experiment considering federated learning settings where the local data is heterogeneous and only a subset of clients participate in each training round. For the classic distributed training, global gradient clipping is applicable because of high-speed InfiniBand on the cloud and fast NCCL implementation.\n", "summary_of_the_paper": "Gradient clipping is an important technique in training deep neural network. Typically, ones need to use the globally averaged gradient to estimate the norm. However, it requires gradient synchronization for every iterations, which is not practical in federated learning. In practice, practitioners only apply local gradient clipping to the local iterates while the theoretical analysis is lacking. This paper analyzes the convergence of the local gradient clipping. The theoretical results show that the convergence is guaranteed when both the number of workers and the number of local iterations are not too large.", "summary_of_the_review": "The paper provides theoretical analysis for local gradient clipping under the federated learning settings. However, the practical cases where the theoretical analysis can be applied is unclear. And, the experiments are based on homogeneous local data in classic distributed settings. The contribution is also incremental.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "GEwJZnoYtcz", "reviewer": "Reviewer_qwWt", "summary": "", "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": "Gradient clipping is known to be an effective tool in training RNNs and mitigating the gradient explosion. However, there is not much work on analyzing its effect in distributed or federated learning scenarios. This paper is among the few ones that tries to theoretically analyze the behavior of FedAvg and similar algorithms when the workers use gradient clipping in their local SGD updates.\nThe paper is generally well-written and the claims are well-supported. One missing recent paper in this area (which was published recently and I don't expect the authors to be aware of it) is the \"Understanding Clipping for Federated Learning ...\" by Xinwei Zhang, et. al., published recently at ICML'21 Workshop on Federated Learning. It would be nice if the authors can comment and compare their results with the findings in that paper and other similar works.\n\nSome minor suggestions:\n - One nice addition to the paper might be to show empirically how tight the theoretical bounds are (at least for a toy example).\n - Assumption 1, iii, $\\\\nabla$ is missing in the first equation.\n - The paragraph after Lemma 2, last sentence, the error is quadratic in $I$, not linear.", "summary_of_the_paper": "The paper considers the effect of gradient clipping in Federated Learning and how it affects the convergence rate. They focused on the relaxed-smooth loss function. Each worker uses local gradient clipping and runs multiple steps of SGD before communicating and averaging the local models. The authors theoretically analyzed the algorithm and showed that for $N$ workers, the algorithm has $O(1/N\\\\epsilon^4)$ iteration complexity to find an $\\\\epsilon$-stationary point. Finally, the theoretical results are experimentally verified on CIFAR-10 (Resent-56 model), Penn Treebank and WikiText (LSTM models).", "summary_of_the_review": "The paper has theoretically analyzed the effect of gradient clipping in local SGD updates in Federated Learning and FedAvg. To the best of my knowledge, the technical analysis and results are incrementally novel and improves the results of existing works. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "97U0OOuDTFH", "reviewer": "Reviewer_63cQ", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The proposed CELGC is simple yet effective. The only difference from local sgd is that CELGC adopts normalized gradient if the norm of gradient is large. The authors also prove its convergence rate for relaxed smooth and non-convex functions.\n\nIn addition to convergence theorem, I care more about the practicality of the proposed algorithm and I have the following questions:\n1. CELGC has many hyper-parameters, e.g., learning rate, clipping threshold and batch size. I notice that in the three experiments, these hyper-parameters are quite different. How to tune these hyper-parameters in a new training problems if we do not have any previous experience (In the experiments, authors often set parameters according to other papers). Is it possible to give an approximate range for these parameters?\n2. The authors claim that CELGC can achieve the linear speedup with proper setting. But they seems do not conduct speedup experiment.\n3. What the difference between the naive version of the parallel gradient clipping algorithm and CELGC with i=1?. I think they are the same one, i.e. \\kappa = 0, so that the performance of the baseline should be better than CELGC with I>1 in the comparison of epochs. This is not consistent with Figure1(a). Besides, I think the authors should set a large batch size for the baseline in the experiments. Normalized gradients may lead to a bad performance when the batch size is small [1]\n\n[1] Beyond convexity- Stochastic quasi-convex optimization. NIPS, 2015.", "summary_of_the_paper": "This paper propose a novel distributed optimization method CELGC. CELGC adopts normalized gradient for local training (e.g., FL) so that it achieves better performance than SGD.", "summary_of_the_review": "This paper has many things to be improved.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper made a solid contribution studying the convergence rate of a simple distributed gradient clipping algorithm. The proposed algorithm simply clips the gradients on each local machine and then do simple distributed update of the parameters. 

The result, if correct, is quite strong and significant: The proposed algorithm is simple, and shows some benefit comparing to previously proposed algorithms -- The strongest part of the paper is that it comes with a convergence rate bound (which is typically hard to prove for gradient clipping methods).


However, during the rebuttal period it was discovered that a number of places in the proofs are not well-supported, the paper has to go through major revision in order to meet the publication standard.
Decision: Reject