A Communication-Efficient Distributed Gradient Clipping Algorithm for Training Deep Neural Networks
Authors: Mingrui Liu
Zhenxun Zhuang
Yunwen Lei
Chunyang Liao
Venue: NeurIPS 2022 Accept (2022)
Keywords: Distributed Training
Gradient Clipping
Communication-Efficient
Optimization

Abstract: In distributed training of deep neural networks, 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 distributed setting is still in its infancy: it remains mysterious whether the gradient clipping scheme can take advantage of multiple machines to enjoy parallel speedup. The main technical difficulty lies in 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 and $O(\frac{1}{\epsilon^3})$ communication complexity for finding an $\epsilon$-stationary point in the homogeneous data setting, where $N$ is the number of machines. This indicates that our algorithm enjoys linear speedup and reduced communication rounds. Our proof relies on novel analysis techniques of estimating truncated random variables, which we believe are of independent interest. Our experiments on several benchmark datasets and various scenarios demonstrate that our algorithm indeed exhibits fast convergence speed in practice and thus validates our theory.

A Communication-ffiiien Distributed Gradient Clipping Algorithm for Training Deep Neural Networks
Mingrui Liu Zhenxun Zhuang", Yunwen Lei', Chunyang Liao 1 Department of Computer Science, George Mason University, Fairfax, VA 22030, USA Meta Platforms, Inc., Bellevue, WA, 98004, USA
3 School of Computer Science, University of Birmingham, United Kingdom Department of Mathematics, Texas A&M University, College Station, Texas 77840, USA mingrui 10gu. edu, oldboymls@gmail. com, yunwen 1ei@hotmail. com
Abstract
In distributed training of deep neural networks, 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 distributed setting is still in take
its infancy: remains mysterious whether the gradient clipping scheme advantage of multiple machines to enjoy parallel speedup. The main technical difficulty lies in dealing with nonconvex loss function. non-Liischitz continuous gradient, and skipping communication rounds simultancously. In this paper, we explore a relaxed-smoothness assumption of the loss landscape which L.TTM was gradient
shown to satisfy in previous works, and design a communication-effiiie 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- bbased updates. Our algorithm is proved have O NeT iteration complexity and O (+))) communication complexity for finding an e-stationary point in the homogeneous data setting, where the number machines. This indicates that our algorithm enjoys linear specdup and reduced communication rounds. Our proof relies on novel analysis techniques estimating truncated random variables, which we believe are of independent interest. Our experiments on several benchmark datasets and various scenarios demonstrate that our algorithm indeed exhibits fast convergence speed in practice and thus validates our theory.
1 Introduction
Deep learning has achieved tremendous successes in many domains including computer vision P3 15), natural language processing 5 and game (39). To obtain good empirical performance, people usually need to train large models on a huge amount of data, and it is usually very computationally expensive. To speed up the training process, distributed training becomes indispensable 4 For example, Goyal et al. [12] trained a ResNet-50 on ImageNet dataset by distributed SGD with minibatch size 8192 256 GPUs in only one hour, which not only matches the small minibatch
"Corresponding Author: Mingrui Liu iningruil@gmar edu). The code is available at https://github com/ com/MingruiLiu- ML- Lab/ http:/Commniiaaiiin cationn sefficient-Locar Cradient---e--neee Clippiiin
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table I: Comparison of Iteration and Communication Complexity of Different Algorithms for finding
a point whose gradient's 's magnitude is smaller than c (i.e., c-stationary point defined Definition B N is the number of machines, the meaning of other constants the complexity of [9] in this table, we assume the gradient norm is upper bounded by M such that
be found in Assumption I For
the gradient is (Lo + Li M--Liscchitz. However, the original paper of ? does not require bounded
gradient; instead, they require I.-Lipschitz gradient and bounded variance o². Under their assumption, their complexity result O (ALE ALOPE-
Algorithm SGD
Setting
Iteration Complexity
Communication Complexity
Single
( + LIM) ALLo + L
N/A
Clipped SGD
Single
O ( + (Lo L10)0² +oLB/L1)))))
N/A
[]
Clipping Framework
Single
0 (AAln02c-))
N/A
Naive Paralicl of
Distributed
0 ([ALooo/(Ne)))
O (ALoo
Ours (this work)
Distributed
O(Algo/((Ne))
O (A
accuracy but also enjoys parallel speedup, and hence improves the running time. Recently, local SGD 40 77 as a variant of distributed SGD, achieved tremendous attention in federated learning community [ The local SGD algorithm runs multiple steps of SGD on each machine before communicating with other clients.
Despite the empirical success of distributed SGD and its variants (e.g., local SGD) 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 [33 c
To address this issue, Pascanu et al. 34 proposed to use the gradient clipping strategy, and it has become a standard technique
when training language models N 35 31I. There are some recent works trying to theoretically
explain gradient clipping from the perspective of non-convex optimization [1 50 These works are built upon an important observation made in [31]: 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 as the relaxed smoothness condition (i.e.. (Lo. Li >mmoothhesss defined in Definition 2). which generalizes but strictly relaxes the usual smoothness condition (i.e., T-smoothness defined in Definition D Under the relaxed smoothness condition, Zhang et al. [51] 50 proved that gradient clipping enjoys polynomial-timm stationary point in the single machine setting, and it can be arbitrarily faster than fix-step gradient descent. In practice, both distributed learning and gradient clipping are important techniques to accelerate neural network training. However, the theoretical analysis of gradient clipping is only Hence naturally motivates us to consider the
iteration complexity for finding the first-order
restricted to the single machine setting 51 50 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 only infrequent communication?
In this paper, we give an affirmative answer the above question. Built upon the relaxed smoothness condition as in [51 (50]. we design a communication-efficii
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 a certain number of local updates on each machine; (ii) our algorithm clips the gradient according to the norm of the local gradient on each machine, instead of the norm of the averaged gradients across machines as in the naive parallel algorithm. These key features make our algorithm amenable to the distributed setting with infrequent communication, and it is nontrivial to establish desired theoretical guarantees (e.g., linear speedup, reduced communication complexity). The main difficulty in the analysis lies in dealing with the nonconvex objective function, non- Non-hiisc continuous gradient, and skipping communication rounds simultancously. Our main contribution is summarized the following:
Naive Parallel of 50 stands for the algorithm which clips the gradient based on the globally averaged gradient at every iteration with constant minibatch size.

---

We design novel commumication-effei distributed stochastic local gradient clipping algorithm, namely CELGC, for solving a nonconvex optimization problem under the relaxed smoothness condition. The algorithm only needs to clip the gradient according to the local gradient's ' magnitude and globally averages the weights on all machines periodically. To the best of our knowledge, this is the first work proposing communication-effiiie distributed stochastic gradient clipping algorithms under the relaxed smoothness condition.
Under the relaxed smoothness condition, we prove iteration and communication complexity results of our algorithm for finding an e-stationary point, when each machine has access to the same data distribution. First, comparing with [50], we prove that our algorithm enjoys linear speedup, which means that the iteration complexity of our algorithm is reduced by factor of N (the number of machines). Second, comparing with the naive parallel version of the algorithm of [50], we prove that our algorithm enjoys better communication complexity. The detailed comparison over existing algorithms under the same relaxed smoothness
condition is described in Table T To achieve this result, we introduce a novel technique of estimating truncated random variables, which is of independent interest and could be applied in related problems involving truncation operations such as gradient clipping.
We empirically verify our theoretical results by conducting experiments on different neural network architectures benchmark datasets. The experimental results demonstrate that our proposed algorithm indeed exhibits speedup in practice.
2 Related Work
Gradient Clipping/Normalizatto (normalization) technique was initially proposed by [A4] to address the issue of exploding gradient problem in [33] and it has become a standard technique when training language models E 35 31 IIt
Algorithms In deep learning literature, gradient clipping
is shown that gradient clipping is robust and can mitigate label noise BC Recently gradient normalization techniques [45 46 were applied to train deep neural networks on the very large batch setting. For example, You et al. 4 designed the LARS algorithm to train a ResNet50 on ImageNet with batch size 32k, which utilized different learning rates according to the norm of the weights and the norm of the gradient. In optimization literature, gradient clipping (normalization) was used in early days in the field of convex optimization considered normalized gradient descent for quasi-convex functions in deterministic and stochastic cases respectively. Gorbunov et al. [C designed an accelerated gradient clipping method to solve convex optimization problems with heavy-tailed noise in stochastic gradients. Mai and Johansson 26 established the stability and convergence of stochastic gradient clipping algorithms for convex and weakly convex functions. In nonconvex optimization, Levy |4 showed that normalized gradient descent can escape from saddle points. Cutosky and Mehta provably improves the normalized SGD in nonconvex optimization. Zhang et al. [5]] and Zhang et al. (500 analyzed the gradient clipping for nonconvex optimization under the relaxed smoothness condition rather than the traditional T-smoothness condition in nonconvex optimization ( 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 the distributed setting where only limited communication is allowed.
Nesterov 32) and Hazan et al. [4]]
3] showed that adding a momentum
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 machine runs a stochastic approximation algorithm and averages the model weights across machines only at the very last iteration. The one-shot averaging scheme is coaammmncation-fffcicee and enjoys statistical convergence with one pass of the data [54] 37 16 22 but the training error may not converge in practice. Memahan et al. 2 considered the Federated Learning setting where the data is decentralized and might be non-i.i.d. across devices and communication is expensive and designed the very first algorithm for federated learning (a.k.a,, FedAvg). Stich 40 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 a while. Stich [40] also showed that local SGD enjoys linear speedup for strongly-convex objective functions. There are also some works analyzing local SGD and its variants on convex
Communication-Efficai
55
28
54
371. in which every
and nonconvex smooth Recently, Woodworth et al. 1 analyzed advantages
G 20
functions
155 47
48
41 25 2 1 19
3

---

and drawbacks of local SGD compared with minibatch SGD for convex objectives. Woodworth al. 12 proved hardness results for distributed stochastic convex optimization. Reddi et F6
introduced a general framework of federated optimization and designed several federated versions of adaptive optimizers. Zhang et al. [52] considered employing gradient clipping to optimize L.- smooth functions and achieve differential privacy. Koloskova et al. 21 developed unified theory of decentralized SGD with changing topology and local updates for smooth functions. Zhang et al. [5 developed federated learning framework for nonconvex smooth functions for non-i.i.d. data. Due to a vast amount of literature on federated learning and limited space, we refer readers to IS and references therein. However, all of these works either assume the objective function is convex or s-sohhh. To the best of our knowledge, our algorithm is the first communication- -ffficctt algorithm that does not rely on these assumptions but still enjoys linear speedup.
3 Preliminaries, Notations and Problem Setup
Preliminaries and Notations Denote || by the Euclidean norm. We denote f IR R as the overall loss function, and F R + R as the loss function i-th machine, where i E [M] := {l....,N .N. Denote (h(x) as the gradient
evaluated at the point x, and denote Vh(x: {) as the
stochastic gradient of h calculated based on sample
Definition 1 (L- (L-shoothness). function h is L-smooth if l[V Vh(y)) S L| - yll for all x,y E Rd.
Definition ((Lo, Li smmoothessss A second order d is (Lo, Lsm-mhotth if [[V"h(x)]| S Lo + L1 Vh(x))] for any x Rdd.
Definition 3 (e-stationary point). x E R. is an c-stationary point of the function h if Vh(x)]l S
Remark: (Lo, ((L)-smoothness is strictly weaker than L-smoothness. First, know that L-smooth functions is (Lo, -smoohh with Lo = and L1- = However the reverse is not true. For example, consider the function h(x) 2 we know that the gradient is not Lipschitz continuous and hence is not I-smooth, but [x"(x] = 12x²2 < 12 + 3 x 4|x]/ = 12 + (/)((x),,
I. so h(x) = xA is
(12,3) -mmoohh.. Zhang al. [51] empirically showed that the (I.n, In] >smoothnesss holds for the AWD-LSTM BT. In nonconvex optimization literature g [50). the goal is to find an e-stationary point since is NP-hard to find global optimal solution for a general nonconvex function.
Problem Setup In this paper, we consider the following optimization problem using N machines: min xER
f(x) = EE-D [x(x;)) E)],
(I)
where DD stands for the data distribution which each machine has access to, and f is the population loss function.
We make the following assumptions throughout the paper.
Assumption 1. (i) f(x) is (Lo, L1) -smoothh,, i.e., [|V*](x)]| S Lo + [or Vx
R
(ii There exists > 0 such that f(xu) - f. I A, where f. is the global optimal value of f-
(iii) For all x E Idd EE-D [V {)] V fx),, and | FFx(; E) - fx())] S a almost surely.
(iv) The distribution of F {) is symmetric around its mean V fx). and the density is monotonically decreasing over the & distance between the mean and the value of random variable.
The Assumption (i) means that the loss function satisfies the relaxed-smoothness condition, and holds when traiinn a language model with LSTMs. We consider the homogeneous distributed learning setting, where each machine has access to same data distribution as in [44] Assumption (i) and (iii) are standard assumptions in nonconvex optimization 9 51. Note that it is usually assumed that the stochastic gradient is unbiased and has bounded variance (9) but in the relaxed smoothness setting, we follow (5T to assume we have unbiased stochastic gradient with almost surely bounded deviation a. Assumption I (iv) assumes the noise is unimodal and symmetric around its mean, which we empirically verify in Appendix Examples satisfying (iii) and (iv) include truncated Gaussian distribution, truncated student's 's t-distribution, etc.
Remark:

---

Algorithm Communication Efficient Local Gradient Clipping (CELGC)
1: for = O,...,? T' do
2: Each node i samples its stochastic gradient V Fx(x {t), where & D.
3: Each node i updates it local solution in parallel:
x
min
VF(x):
(2)
4: if t is multiple of / then
5: Each worker resets the local solution as the averaged solution across nodes:
N
Vi (I,..,,,
(3)
=1
6: end if
7:
end for
4 Algorithm and Theoretical Analysis
4.1 Main Difficulty and the Algorithm Design
We briefly present the main difficulty in extending the single machine setting [50 to the distributed setting. In [50] they split the contribution of decreasing objective value by considering two cases: clipping large gradients and keeping small gradients. If communication allowed every iteration, then we can aggregate gradients on each machine and determine whether we should clip or keep the averaged gradient or not. However, in our setting, communicating with other machines 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 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 not L-smooth, so the usual local SGD analysis for L-soooth functions cannot be applied in this case.
To address this issue, we design a new algorithm, namely Communication Efficient Local Gradient Clipping (CELGC), which is presented in Algorithm [ The algorithm calculates stochastic gradient and then performs multiple local gradient clipping steps on each machine in parallel, and aggregates model parameters on all machines after every I steps of local updates. We aim to establish iteration and communication complexity for Algorithm for finding an c-stationary point when > 1.
4.2 A Lemma for Truncated Random Variables
As indicated in the previous subsection, Algorithm clipp gradient on each local machine. This feature greatly complicates the analysis: it is difficult to get an unbiased estimate of the stochastic gradient when its magnitude is not so large such that clipping does not happen. The reason due the dependency between random variables (i.e., stochastic gradient and the indicator of clipping). To get around of this difficulty, we introduce the following Lemma for estimating truncated random variables.
Lemma 1. Denote by g E Rdd random vector. Suppose the distribution of g is symmetric around its mean, and the density is monotonically decreasing over the E distance between the mean and the value of random variable, then there exists A diag(C) (Ct, and 0 < C S with i -1...., d such that
E Eg < a]] Pr(lell S ag)
where a > 0 is constant, I(-) is the indicator function.
The proof of Lemma T is included Appendix B
This Lemma provides an unbiased estimate for truncated random variable. In the subsequent of this paper, we regard g in the Lemma as the stochastic gradient and a as the clipping threshold. In addition, we define Cmin = min((1,....... Ca),
and Cmax max(ci..... ea). We have 0 < Cmin Crax < 1.
5

---

4.3 Main Results
Theorem 1. Suppose Assumption holds and a 2 1. Take S min( ALa
0.1) be a small
BLI
enough constant and N I m ( IAAL)). ). In Algorithm 1 choose I S
Cmin Ne 7
Ne min( xi. Bे, and the fixed ratio I 50, where A 2 1 and B 2 are constants
Cmin 28
which will be specified in the proof, and run Algorithm / f T = 0 ALoo Ne
iterations. Define
Ei= x Then we have + + DEeIE//// [X)))()))] X, N
S 9c.
Remark: We have some implications of Theorem [ When the number of machines is not large (i.e., N S O()/e)) and the number of skipped communications is not large (i.e., I S O WNo/eN/ //N)), then with proper setting of the learning rate, we have following observations. First, our algorithm enjoys linear speedup, since the number of iterations by the number of machines N when comparing the single machine algorithm [50]. Second, our algorithm is communication--fficient since the communication complexity (a.k.a., number of rounds) is T/1 = O (ALgre "), which provably improves the naive parallel gradient clipping algorithm of (50 with ( (aLLgo"((Ne)) /(Ne)) communication complexity when N < O(1/c).
need to find e-stationary point is divided
Another important fact is that both iteration complexity and communication complexity only depend on Lo while being independent of I. and the gradient upper bound M. This indicates that our algorithm does not suffer from slow convergence even if these quantities are large. This is in line with [50] as well. In addition, local gradient clipping is a good mechanism to alleviate the bad effects brought by a rapidly changing loss landscape (e.g., some language models such as LSTM).
4.4 Sketch of the Proof of Theorem
In this section, we present the sketch of our proof of Theorem The detailed proof can be found in Appendix C The key idea in our proof is to establish the descent property of the sequence {f TT in the distributed setting under the relaxed smoothness condition, where x, = t/4 Ei=1 x3 is the averaged weight across all machines at f-th iteration. The main challenge is that the descent property of (Lo. L1 -smooth function in the distributed setting does not naturally hold, which is in sharp contrast the usual local SGD proof for L-smooth functions. To address this challenge, we need to carefully study whether the algorithm is 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 the averaged weight and the magnitude of local gradients evaluated at the individual weights on every machine. To this end, we introduce Lemma whose goal is 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 an indicator of whether the clipping operation happens or not, For each fixed iteration f, we define (t) = (i E [M] | [x Il 2 7/n} and (tt) = [N] \ (t). Briefly speaking. (t) contains all machines that perform clipping operation at iteration t and J(t) is the set of machines that do not perform clip operation at iteration t. In Lemma 3 we perform
the one-step analysis and consider all machines with different clipping behaviors at the iteration t.
The proof of Lemma 3 crucially relies on the lemma for estimating truncated random variables (i.e.. Lemma M to calculate the expectation of non-clipped gradients.
Second, Zhang et al. [50 inspect their algorithm's progress by considering the magnitude of the gradient at differrntt iterations, so they treat every iteration differently. However, this approach does not work in the distributed setting with infrequent communication since one cannot get access to the averaged gradient across machines at 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 (n, I) and using an amortized analysis, we prove that our algorithm can decrease the objective value by a 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 to better characterize the training dynamics.
Now present how to proceed with the proof in detail.

---

Lemma
characterizes the & error between averaged weight and individual weights at t-th iteration.
Lemma 2. Under Assumption for any and 6, Algorithm ensures ||x xi| S 2 holds almost
surely.
Lemma 5 and Lemma 6 (in Appendix A are properties of (Lo, L functions we need to use. To make sure they work, we need / S Li for some > 0. This is proved in the proof of
Theorem (in Appendix O
Let (t) be the index set of i such that VF 2 2 at fixed iteration t. i.e., J(t) = {i e
?7
r/n). Lemma characterizes how much progress we can get in one iteration of Algorithm D which is decomposed into contributions from every machine (note that
[N] FIV +tll
((t) U J(t) (t, [I......Ny ,
for every t).
Lemma 3. Let (t) be the set defined as above. 1f S Li for some e > 0, ALon S 1/2, and 7/1 = 50, then we have
(xf(x(11) [xx:]]
Σ SEJ(()
27
[V
3
+
50ALon
7 1IF((())))) - Vs(x,)]
ATo?? BL V ((x))]
5n
+
Σ
M7nin
[x(x))] + 1,
50
B
2
1EJ(()
where 1 = cn-1 and B e"11
Lemma 4 quantifies an upper bound of the averaged l error between the local gradient evaluated at the local weight and the gradient evaluated the averaged weight.
Lemma 4. Suppose Assumption 1 holds. When 2 S L1 L for some > 0, the following inequality holds for every almost surely with A = 1 e e'-1 and B c'-1;
VF(x) vf(x)) + 20 BLIIVS(R))I))
Putting all together Suppose our algorithm runs T iterations. Taking summation on both sides of Lemma 3 over all t = O....,T - 1, we are able to get an upper bound of T-1 [f(x++1) - [(x,)] = E ( - [xx)]. Note that E (x(r)) [(x))] 2 ー due to
Assumption ! so we are able to get an upper bound of gradient norm, For details, please refer to the proof of Theorem I in Appendix C
5 Experiments
We conduct extensive experiments to validate the merits of our algorithm on various tasks (c.g.. image classification, language modeling). In the main text below, we consider the homogencous data setting where each machine has the same data distribution and every machine participate the communication at each round. In the Appendix [ we also test algorithm in the general federated learning setting (e.g., partial participation of machines), ablation study on small/large batch-sizes, and other experiments, etc.
We conduct each experiment in two nodes with Nvidia- V100 GPUs on each node, In our experi- ments, one "machine" corresponds to one GPU, and we use the word "GPU" and "machine" in this section interchangcably. We compared our algorithm with the bascline across three deep learning benchmarks: CIFAR-10 image classification with ResNet, Penn Treebank language modeling with LSTM, and Wikitext-2 language modeling with LSTM, and ImageNet classification with ResNet. All algorithms and the training framework are implemented in Pytorch 1.4. Due to limited computational resources, for our algorithms, we choose same hyperparameters like the clipping thresholds according to the best-tuned baselines unless otherwise specified.
We compare our algorithm of different with the baseline, which is the naive parallel version of the algorithm in (50] We want to re-emphasize that the 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 every I iterations. We find that algorithm with range of values of / can
7

---

25
0.8
200
0.000
Teet Aruuecy
1992
2.0
Ter AccumNy
0025
L5
1.5
160
180
220
1.0
0.9075
0.5
0.2
360
100
0.0
50
105
150
230
50
100
150
200
400
1000
20c
400
2000
Epoch
Welchock time (second)
le time (second)
Outs
Ours
16
(a) Over epoch
(b) Over wall clock time
Figure 1: Algorithm D with different /: Training loss and test accuracy v.s. (Left) epoch and (right) wall clock time on training 56 layer Resnet to do image classification on CIFARIO.
65
200
6.0
3.7
180
180
160
67
5.5
160
3.6
140
5.0
150
200
250
120
66
150
200
120
100
4.0
100
3.5
355
50
100
150
20C
250
0
100
150
200
250
31
6K
9.
12%
15k
16k
21k
EK
12x
15k
Oura m
Gurs =
Curs
Dure
Peralle: SGDCIp
36
Porstiel SGDCEp
(a) Over epoch
(b) Over Wall clock time
Figure 2: Algorithm D with different Training loss and validation perplexity v.s. (Left) epoch and (right) wall clock time training AWD-LSTM to do language modeling Penn Treebank.
match the results of the baseline in terms of epochs on different models and data. This immediately suggests that our algorithm will gain substantial speedup in terms of the wall clock time, which is also supported by our experiments.
5.1 Effects of Skipping Communication
We focus one feature of our algorithm:
skipping communication rounds. Theorem says that our algorithm enjoys reduced communication complexity since every node only communicates with other nodes periodically with node synchronization interval length 7. To study how communication skipping affects the convergence of Algorithm 1
we run it with / E {2, 4, 8, 16,32).
CIFAR-10 classification with ResNet-56. We train the standard 56-layer ResNet 15 architecture CIFAR-10. 10. We use SGD with clipping as the baseline algorithm with a stagewise decaying learning rate schedule, following the widely adopted fashion training the ResNet architecture. Specifically, we use the initial learning rate 7 = 0.3, the clipping threshold = 1.0, and decrease the learning rate by factor of 10 at epoch 80 and 120. The local batch size each GPU is 64. These parameter settings follow that of
The results are illustrated in Figure Figure shows the convergence of training loss and test accuracy v.s. the number 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 Ib verifies our algorithm's advantage of skipping communication by plotting the convergence of training loss and test accuracy v.s. the wall clock time. Overall, we can clearly see that our algorithm matches the bascline epoch-wise but greatly speeds up wall-clock-wise.
Language modeling with LSTM on Penn Treebank. We adopt the 3-layer AWD-LSTM B1 to do language modeling on Penn Treebank (PTB) dataset [27] (word level). We use SGD with clipping as the baseline algorithm with the clipping threshold 7 = 7.5. The local batch size at each GPU is 3. These parameter settings follow that of [50]. We fine-tuned the initial learning rate for all algorithms (including the baseline) by choosing the one giving the smallest final training loss the
range (0.1, 0.5, 1, 5, 10, 20, 30, 40, 50, 100).

---

200
6.5
200
3.8
180
180
3.7
160
27.0
5.5
5.0
140
76.5
5.0
140
200
230
A03
120
230
250
300
120
100
4.0
200
3.5
15
100
200
350
0
100
200
300
31. 66
12t
15k
18k
21k
22x
13k
10k
Epoch
Epoch
Waliclock time (secend)
Walidook (second)
16
(a) Over epoch
(b) Over Wall clock time
Figure 3: Algorithm D with different 7: Training loss and validation perplexity v.s. (Left) epoch and
(right) wall clock time on training an AWD-LSTM to do language modeling on Wikitext-2.
We report the results in Figure 2 It can be seen that we can match the baseline in both training loss and validation perplexity epoch-wise while gaining substantial speedup (4x faster for 4) wall-clock-wise.
Language modeling with LSTM on Wikitext-2. We adopt the 3-layer AWD-LSTM +1 to do language modeling on Wikitext-2 dataset (27 level). We use SGD with clipping as the baseline algorithm with the clipping threshold y = 7.5. The local batch size each GPU 10. These parameter settings follow that of [1I. We fine-tuned the initial learning rate for all algorithms (including the baseline) by choosing the one giving the smallest final training loss in the range {0.1, 0.5, 1, 5, 10, 20, 30, 40, 50, 100).
We report the results in Figure We can match the baseline in both training loss and validation perplexity epoch-wise, but we again obtain large speedup (4x faster for /=4) 4) wall-clock-wise. This, together with the above two experiments, clearly show our algorithm's effectiveness in speeding up the training in distributed settings. Another observation is that Algorithm | can allow relatively large I without hurting the convergence behavior.
ImageNet Classification with ResNet-50 We compared our algorithm with several basclines in training a ResNet-50 on ImageNet. We compared with two strong baselines: one is the Naive Parallel SGDClip, another is a well-accepted baseline for ImageNet by [2] We run the experiments on GPUs. We follow the settings of [2] to setup hyperparameter for baselines. Specifically, for every method, the initial learning rate 0.0125, and we use the warmup with epochs, batch size 32, momentum parameter 0.9, the weight decay 5 x 10-4. The learning rate multiplying factor is 1 for the epoch ~ 30, and 0.1 for epoch 30 ~ 60, 0.01 for epochs
80, and 0.001 for epoch 80 ~ 90. The clipping threshold for Naive Parallel SGDClip and our method CELGC are both set to be We consider our algorithm with = 4, i.e., our algorithm CELGG performs weight averaging after 4 steps of local stochastic gradient descent with gradient clipping each GPU.
The results are shown in Figure 6 We report the performance of these methods from several different perspectives (training accuracy/validation accuracy versus epoch, and training accuracy/validation accuracy versus wallelock time). We can see that the training accuracy of our algorithm CELGC with I = 4 can match both baselines in terms of epoch (Figure ba). but it is much better in terms of running time (Figure
5.2 Verifying Parallel Speedup
Figure 4 show the training loss and test accuracy v.s. the number of iterations. In the distributed setting, one iteration means running one step of Algorithm [ on all machines; while in the single machine setting, one iteration means running one step of SGD with clipping. In our experiment, we use minibatch size 64 on every GPU in the distributed setting to run Algorithm [ while we also use 64 minibatch size on the single GPU to run SGD with clipping. In the left two panels Figure 4 we can clearly find that even with >> 1, our algorithm still enjoys parallel speedup, since our algorithm requires less number of iterations to converge to the same targets (e.g., training loss, test accuracy). This observation is consistent with our iteration complexity results in Theorem

---

g20
2.5
0.050
Thet betiies
0.8
0.6
Durs
Dus m-
0,225
16000
10000
100
0ursi=
0.2
0 16
Ours 52
Mave Tarale 50X0
0.5
40c
terations
100k
20k
40h
1922
ba0ch
tpoch
Oura
Ours
Ours
Single SCDCIp
(a) CIFAR-10
(b) Penn Treebank
Ourr
Ourr 26
Naboe Fara CCC
Figure 5: Proportions iterations in each epoch in which clipping is triggered v.s. epochs show- ing clipping is very frequent.
Figure 4: Performance v.s. # of iterations each GPU runs on training ResNet-56 on CIFAR- showing the parallel speedup.
Woldaaiionn Accurser
0.6
Taiing Accunicy
8.6
0.6
0.760
0.4
0.76
0.735
0.2
0.74
0.750
60
80
10tk
100k:
Epech
Epoch
Wallelok (second)
Vellc (second)
Goyal et oi.. 2018
Nalue Para SGDCIp
CELGC I+4
Goyal 2018
hol Parallal SCOK3p
CEUGE iw
(a) Performance over epoch
(b) Performance over wall clock time
Figure 6: Training loss and test accuracy v.s. epoch (left) and wall clock time (right) on training Resnet-50 to do image classification on ImageNet.
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 NLP 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 as the baseline did. This leads to more stochasticity of the norm of the gradient in our 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 language models than image classification models. Hence this algorithm is presumably more effective in training deep models in NLP tasks.
Conclusion
In this paper, we design communication-efficiee distributed stochastic local gradient clipping algorithm to train deep neural networks. By exploring the relaxed smoothness condition which was shown to be satisfied for certain neural networks, theoretically prove both the linear speedup property and the improved communication complexity when the data distribution across machines homogeneous. Our empirical studies show that algorithm indeed enjoys parallel speedup and greatly improves the runtime performance in various federated learning scenarios (e.g., partial client participation). One limitation of our work is that our convergence analysis is only applicable for homogencous data, and would be interesting to analyze the settings of heterogeneous data theoretically in the future.
Acknowledgements
We would like to thank the anonymous reviewers for their help comments. Mingrui Liu is sup- ported by a grant at George Mason University. Computations were run on ARGO, research computing cluster provided by the Office of Research Computing at George Mason University (URL: https://orc.gn cettoorrggm.eeee. gmu. The majority of work of Zhenxun Zhuang was done when he was a Ph.D. student at Boston University.
10

---

References
[1] Ya I Alber, Alfredo N. lusem, and Mikhail V. Solodov. On the projected subgradient method for nonsmooth convex optimization in hilbert space. Mathematical Programming, 81(1):23-35, 1998.
[2] 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, pages 14668-14677 2019.
[3] Ashok Cutkosky and Harsh Mehta. Momentum improves normalized sgd. In International Conference Machine Learning, pages 2260-2268, PMLR, 2020.
[4] Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Marc' aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, et al. Large scale distributed deep networks. In Advances neural information processing systems, pages 1223-1231, 2012.
[5] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.0440 04805, 2018.
[6] Aymeric Dieuleveut and Kumar Kshitij Patel. Communication trade-offs for local-sgd with large step size. Advances in Neural Information Processing Systems, 1211131161612,, 2019.
[7] Yuri Ermoliev. Stochastic quasigradient methods. numerical techniques for stochastic optimiza- tion. Springer Series in Computational Mathematics, (10):141-185, 1988.
[8] Jonas Gehring, Michael Auli, David Grangier, Denis Yarats, and Yann N Dauphin. Convolutional sequence to sequence learning. In International Conference on Machine Learning, pages 1243- 1252. PMLR, 2017.
[9] Saced Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2368 2013.
[10] Eduard Gorbunov, Marina Danilova, and Alexander Gasnikov. Stochastic optimization with heavy-tailed noise via accelerated gradient clipping. arXiv preprint UrXiv:2005.10760 2020.
[11] Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. Local sgd: Unified theory and new efficient methods. In International Conference on Artificial Intelligence and Statistics, pages 3556-3564. PMLR, 2021.
[12] Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in hour. arXiv preprint arXiv: 10dp:170600677, 2017.
[13] Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Local sgd with periodic averaging: Tighter analysis and adaptive synchronization. In Advances in Neural Information Processing Systems, pages 11880-11092. 2019.
[14] Elad Hazan, Kfir Y Levy, and Shai Shalev-Shwartz. Beyond convexity: Stochastic quasi-convex optimization. arXiv preprint rrXiv:1507.02030 2015.
[15] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[16] Prateek Jain, Sham M Kakade, Rahul Kidambi, Pranceth Netrapalli, and Aaron Sidford. Paral- lelizing stochastic gradient descent for least squares regression: Mini-batching, averaging, and model misspecifiicatinn. Journal of Machine Learning Research, 18:223-1, 2017.
[17] Peng Jiang and Gagan Agrawal. A linear speedup analysis of distributed deep learning with sparse and quantized communication. Advances in Neural Information Processing Systems, pages 2525-2536, 2018.

---

[18] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji. Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings. et al. Advances and open problems in federated learning. arXiv preprint arXiv: 1912.49977, 2019.
[19] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning, In International Conference on Machine Learning. pages $132-5143. PMLR, 2020.
[20] Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pages 4519 4529. PMLR, 2020.
[21] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning, pages 5381-5393. PMLR, 2020.
[22] Anastasia Koloskova, Sebastian U. Stich, and Martin Jaggi. Decentralized stochastic opti- mization 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, pages 3478-3487, 2019.
[23] Alex Krizhevsky, lya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems, pages 1097-1105, 2012.
[24] Kfir Y Levy. The power of normalization: Faster evasion of saddle points. arXiv preprint arXiv:1611.04833 2016.
[25] Tao Lin, Sebastian U Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't 't use large nini-batches, use local sgd. arXiv preprint 0rXiv:1808.07211 2018.
[26] Vien Mai and Mikael Johansson. Stability and convergence of stochastic gradient clipping: Beyond lipschitz continuity and smoothness. arXiv preprint arXiv:2102.06449, 2021.
[27] Mitchell P. Marcus, Mary Ann Mareinkiewicz, and Beatrice Santorini. Building a large annotated corpus of english: The penn treebank. Comput. Linguist., 19(2)313--33, June 1993.
[28] 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 American Chapter of the Association for Computational Linguistics, pages 456 464. Association for Computational Linguistics, 2010.
[29] H Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, et al. Communication efficient learning of deep networks from decentralized data. AISTATS, 2017.
[30] Aditya Krishna Menon, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Can gradient clipping mitigate label noise? In International Conference on Learning Representations, 2019,
[31] Stephen Merity, Nitish Shirish Keskar, and Richard Socher. Regularizing and optimizing LSTM language models. In International Conference on Learning Representations, 2018.
[32] Yurii E Nesterov. Minimization methods for nonsmooth convex and quasiconvex functions. Matekon, 29:519-531 1984.
[33] Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. Understanding the exploding gradient problem. corr
(2012). arXiv preprint arXiv: 2012.
[34] Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. International conference on machine learning, pages 1310-1318. PMLR, 2013.
[35] Matthew E Peters, Mark Neumann, Mohit Tyyer, Matt Gardner, Christopher Clark, Ken- ton Lee, and Luke Zettlemoyer. Deep contextualized word representations. arXiv preprint 10X.00800.003655 2018.
12

---

[36] Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush. Jakub Konecny, Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. ICLR, 2021.
[37] Ohad Shamir and Nathan Srebro. Distributed stochastic optimization and learning. 2014 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 850-857, 857. IEEE, 2014.
[38] Naum Zuselevich Shor. Minimization methods for non-difeerentiable functions, volume 3. Springer Science & Business Media, 2012.
[39] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484, 2016.
[40] Sebastian U Stich. Local sgd converges fast and communicates little. arXiv preprint 18Xv:0880500976 2018.
[41] Jianyu Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of communication-effiient sgd algorithms. arXiv preprint arXiv: 18X.v08808.07770 2018.
[42] 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.
[43] Blake Woodworth, Kumar Kshitij Patel, and Nathan Srebro. Minibatch vs local sgd for heterogeneous distributed learning, arXiv preprint arXiv:2006.0473 2020.
[44] Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Mcmahan, Ohad Shamir, and Nathan Srebro. Is local sgd better than minibatch sgd? In International Conference Machine Learning, pages
PMLR, 2020.
[45] Yang You, Igor Gitman, and Boris Ginsburg. Scaling sgd batch size 32k for imagenet training. arXiv preprint arXiv: 1 7708. 03888, 6:12, 2017.
[46] Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar. Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large batch optimization for deep learning: Training bert in 76 minutes. arXiv preprint arXiv: 1900:09624 2019.
[47] Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient momentum SGD for distributed non-convex optimization. In Proceedings of the 36th Interna- tional Conference Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pages 7184-7193, 2019.
[48] 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, pages 5693-5700, 2019.
[49] Honglin Yuan, Manzil Zaheer, and Sashank Reddi. Federated composite optimization. In International Conference on Machine Learning. pages 12253-12266 PMLR, 2021.
[50] Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non-convex optimization. arXiv preprint arXiv:2010.02519, 2020.
[51] Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. arXiv preprint /905.//90..//888 2019.
[52] 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. 13673, 2021.
[53] Xinwei Zhang, Mingyi Hong, Sairaj Dhople, Wotao Yin, and Yang Liu. Fedpd: A feder- ated learning framework with optimal rates and adaptivity to non-iid data. arXiv preprint arXiv:2005.11418, 2020.
13

---

[54] Yuchen Zhang, John C Duchi, and Martin J Wainwright. Communication-efiicnn algorithms for statistical optimization. The Journal of Machine Learning Research, 14(1):3321-3363, 2013.
[55] Fan Zhou and Guojing Cong. On the convergence properties of k-step averaging stochastic gradient descent algorithm for nonconvex optimization. arXiv preprint arXiv:1708.01011 2017.
[56] Martin Zinkevich, Markus Weimer, Lihong Li, and Alex Smola. Parallelized stochastic gradient descent. In Advances in neural information processing systems, pages 2595-2603, 2010.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See the Section 6
(C) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section
(b) Did you include complete proofs of all theoretical results? [Yes] See the Appendix
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material URL)? [Yes] in the supplemental material
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See the Section 5
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See the Section 5
4. If you are using existing assets (e.g., code, data, models) or curating/relcasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "qQZGJqgw8g6", "reviewer": "Reviewer_xkbT", "summary": "This paper studied the local stochastic gradient clipping method for nonconvex distributed optimization. Meanwhile, it provided the convergence analysis of the proposed CELGC algorithm under i.i.d. setting. It also conducted the empirical experiments to verify the efficiency of the proposed algorithm. ", "questions": "1)\tFrom algorithm’ view, the proposed CELGC algorithm only extend the classic FedAvg algorithm to  gradient clipping setting.\n\n2)\tFrom theoretical analysis’ view, although the given convergence analysis relax the smoothness condition, it strictly relies on the i.i.d. setting. In convergence analysis, the given relaxation of the smoothness condition is also popular, so it does not take any challenge.  \n\n3)\tIn the experiments, the given comparative methods only including gradient clipping methods are not reasonable. You should add some existing standard gradient-based methods such as FedAvg as comparative methods. ", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper studied the local stochastic gradient clipping method for nonconvex distributed optimization. Meanwhile, it provided the convergence analysis of the proposed CELGC algorithm under i.i.d. setting. It also conducted the empirical experiments to verify the efficiency of the proposed algorithm. \n\n1)\tFrom algorithm’ view, the proposed CELGC algorithm only extend the classic FedAvg algorithm to  gradient clipping setting.\n\n2)\tFrom theoretical analysis’ view, although the given convergence analysis relax the smoothness condition, it strictly relies on the i.i.d. setting. In convergence analysis, the given relaxation of the smoothness condition is also popular, so it does not take any challenge.  \n\nOverall, the novelties and contributions of this paper do not reach the level of NeurIPS.  ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "esXDz-nC0B2", "reviewer": "Reviewer_rnQp", "summary": "The authors provide a decentralized gradient clipping algorithm. The authors show that under some conditions the algorithm will converge to the $\\epsilon$-stationary point with sample complexity $O(1/(N\\epsilon^4))$ and communication complexity $O(1/\\epsilon^3)$. And the algorithm performance shows the benefit of the proposed algorithm against naive parallel SGDclip.", "questions": "See weaknesses.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Instead of using L-smoothness, the algorithm can converge under a weaker condition (L0,L1)-smoothness.\n\n2. The experiments compare with the algorithm with wall clock time, which shows the speed up in the training phase.\n\nWeaknesses:\n1. With L-smoothness, [1] show the lower bound of communication iterations is lower bounded by $1/\\epsilon^2$. But even when $L_1 = 0$, the number of communication iterations is still in the order of $1/\\epsilon^3$.\n\n2. (iv) in Assumption 1 is somehow strong. Even it can be shown in some layers for some experiments in Appendix E. Maybe change of Lemma 1 will be more important.\n\n3. The hardest part of showing the result under the heterogeneous setting. in the homogenous setting, it seems that the most difficult part is dealing with I, the rest part will be the same as [51](ref in the paper).\n\n4. The experiment would compare with more algorithms (e.g. clipping version of FedAVG)\n\n\nRef\n[1] Zhang, X., Hong, M., Dhople, S., Yin, W., & Liu, Y. (2020). Fedpd: A federated learning framework with optimal rates and adaptivity to non-iid data. arXiv preprint arXiv:2005.11418.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Wa9qzlgGvY9", "reviewer": "Reviewer_ZjNg", "summary": "This paper combines local sgd with gradient clipping. Local sgd is a communication-efficient method by skipping some aggregation rounds. Gradient clipping is a common technique to address the gradient exploding issue for some neural networks such as RNN and LSTM. By combining these two techniques, this paper achieves communication-efficiency and resolves the gradient exploding issue.", "questions": "In addition to my concerns as mentioned in the weaknesses above, I have the following questions:\n* In Table 1 where the iteration and communication complexity of different methods are compared. Will the communication frequency I impact the communication complexity of the proposed method? I don’t see I in the table. \n* In Figure 1a (right) where test accuracy vs epoch is shown, it looks like all methods (baseline and proposed methods with different I) converge to the same test accuracy. When I is very large (i.e., communication is less frequent), should the converged performance become worse? I noticed that same phenomenon in Figure 2a(right) and 3a(right).\n\n", "limitations": "none", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The motivation is clear. I think combining local sgd and gradient clipping makes sense.\n* Theoretical analysis is provided. Especially, the communication complexity of the proposed method is proved to be better than the naive parallel method of the baseline gradient clipping. \n* Experiments demonstrate that the proposed method is faster than the baseline in terms of wall-clock time in some cases.\n\nWeaknesses:\n* LSTM used to be the default method for processing sequential data such as in Natural Language Processing (NLP). However, now we can see the trend that transformer-based methods such as BERT has become the dominating method in NLP and related sequential data tasks. The benefits of transformer-based methods are obvious: easier parallelism leading to faster wall-clock time for training, and no need for back propagation via time (which would cause issues like gradient exploding). Given the current state-of-the-art established by transformer-based methods, I am afraid that the usefulness of the proposed method in this paper may be limited. \n* Local SGD is primarily used in federated learning where the communication between clients and central server has a very high cost. I think it’s better if more experiments on federated learning (heterogeneous data distribution across clients, partial precipitation, etc) can be included.\n\n==========after author response==========      \nI appreciate the authors' response. I understand there are some merits for the proposed method. I intend to keep my score unchanged mainly because I am still concerned with the usefulness of the proposed method due to the more recent transformer-based models as the current dominant methods in sequential data processing. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "B1bF5IhmP-z", "reviewer": "Reviewer_ucfd", "summary": "The paper focuses on training neural networks in the infrequent-communication setting (such as Local-SGD) with gradient clipping. Prior works have shown that gradient clipping is an important technique to stabilize the training of neural networks. Local-SGD is a communication-efficient distributed training algorithm that can significantly reduce the communication overhead and lead to totraining speedup. However, using the two is not straightforward as gradient clipping is applied on the averaged gradient whereas Local-SGD conducts several local steps before executing any communications.\n\nTo overcome this issue the paper proposes CELGC, which relies on prior work by [1]. The paper provides a theoretical and empirical study of CELGC. The experiments include an evaluation of the ResNet-34 and AWD-LSTM neural architectures.\n\n\n[1] Zhang, Bohang, et al. \"Improved analysis of clipping algorithms for non-convex optimization.\" Advances in Neural Information Processing Systems 33 (2020): 15511-15521.", "questions": "1. It is common today to train neural networks with more advanced optimizers ( such as Momentum or Adam) than vanilla SGD which was used in the paper. What is the compatibility of CELGC with these relatively newer optimizers?\n2. Today, it is common to apply gradient clipping locally in the Local-SGD or federated setting. Why was CELGC not compared to this simple approach?\n3. The Naive Parallel SGDClip was defined as using [3] and synchronizing at every iteration. Why can't [3] simply be applied locally when training in the Local-SGD setting?\n4. In Figure 1 the Naive Parallel SGDClip is much more volatile compared to CELGC, why is that?\n\n[1] Kingma, Diederik P., and Jimmy Ba. \"Adam: A method for stochastic optimization.\" arXiv preprint arXiv:1412.6980 (2014).\n\n[2] Zhang, Xinwei, et al. \"Understanding Clipping for Federated Learning: Convergence and Client-Level Differential Privacy.\" arXiv preprint arXiv:2106.13673 (2021).\n\n[3] Zhang, Bohang, et al. \"Improved analysis of clipping algorithms for non-convex optimization.\" Advances in Neural Information Processing Systems 33 (2020): 15511-15521.\n\n---\n> Improving the empirical study would help improve the score:\n- Stronger empirical results, such as ResNet-50 on ImagNet.\n- Comparison to the \"naive\" algorithms stated above (2 and 3).\n- Adding zoomed-in figures to see the convergence rate.\n- Listing the final results in a table.\n- Hyperparameter robustness tests.\n- Confidence intervals for figures. \n", "limitations": "The paper addresses some of the limitations of CELGC in the conclusion section. For example, the limitation of being restricted to homogenous data makes it incompatible with the federated setting where the data is often heterogeneous.  A second limitation, which is not discussed, is that the CELGC requires tuning \\gamma as it cannot be directly inferred from the existing gradient clipping hyperparameter. This adds additional computational cost when using CELGC on an existing neural architecture.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "> **TL;DR:**\nThe paper presents an algorithm called CELGC that makes gradient clipping compatible with the Local-SGD setting. The paper provides both a theoretical and an empirical study of the algorithm. However, the algorithm is lacking novelty due to the high similarity with [1] and completely disregards very relevant papers such as [2]. Furthermore, the empirical results are hard to read and not convincing enough.\n---\n**Update Following Rebuttal with imageNet Results**\nThroughout the rebuttal process, the authors have responded to my concerns and I appreciate the answers. The authors have made great efforts to improve the paper by adding confidence intervals to the figures and clearly listing the final accuracies. The authors also added ImageNet experiments that both show strong empirical results and the usefulness of the proposed CELGC algorithm. I'm still concerned about usefulness of the CELGC, since it requires re-tuning the $\\gamma$ hyper-parameter. However, I believe that CELGC is robust and provides both strong empirical and theoretical results. Therefore, I think that this paper should accepted after its rebuttal improvements.\n---\n\n**Pros:**\n1. The paper is well written and addresses an important problem that allows Local-SGD to use gradient clipping.\n2. The theoretical analysis seems correct with no significant errors.\n3. The experiments include many different configurations, such as a federated learning experiment with homogenous data (although heterogeneous data would be preferable in this configuration).\n4. The experiments used a learning-rate hyperparameter grid search for tuning each algorithm.\n\n**Cons:**\n1. The Figures in the experiment section are hard to read and often confusing. For example, in the two left plots in Figure 4 the comparison of convergence speed or final accuracy to the single GPU (baseline) is not possible. This specific figure is also misleading, as the X-axis is not the amount of processed data but rather some sort of execution time combined with iterations. Adding a zoomed-in figure and listing the final results in a table would significantly improve this. Furthermore, many figures are missing a valid comparison to the single GPU scenario (baseline) in order to show true linear scalability.\n2. The figures do not have error bars or any confidence intervals. This is crucial for justifying the empirical results. Furthermore, I expect a robustness evaluation as listing the best-tuned results does not provide the whole picture.\n3. The two right plots in Figure 4 are not described and can only be understood after collecting the pieces of information myself and solving the puzzle. It is not clearly stated which plot refers to which neural network. Figure 4 should be split into two separate plots (the two right and two left) with proper sub-captions.\n4. A comparison to known scalable architecture-dataset combination is required. Figure 10 does not convince the scalability as it is not evaluated on a scalable configuration, such as ResNet-50 on Imagenet that was used in [1].\n\n**Typos:**\n1. Line #32: \"in federated\" --> \"in the federated\"\n2. Algorithm 1 Line #3: \"it\" --> \"its\"\n3. Line #239: \"the iteration\" --> \"iteration\"\n\n[1] Zhang, Bohang, et al. \"Improved analysis of clipping algorithms for non-convex optimization.\" Advances in Neural Information Processing Systems 33 (2020): 15511-15521.\n\n[2] Zhang, Xinwei, et al. \"Understanding Clipping for Federated Learning: Convergence and Client-Level Differential Privacy.\" arXiv preprint arXiv:2106.13673 (2021).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept