Year: 2021

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 ( 1 Nε4 ) iteration complexity for finding an ε-stationary point, where N is the number of machines. This indicates that our algorithm enjoys linear speedup. Our experiments on several benchmark datasets and various scenarios demonstrate that our algorithm indeed exhibits fast convergence speed in practice and validate our theory.

text: ( 1
Nϵ4
) iteration complexity for finding
an ϵ-stationary point, where N is the number of machines. This indicates that our algorithm enjoys linear speedup. Our experiments on several benchmark datasets and various scenarios demonstrate that our algorithm indeed exhibits fast convergence speed in practice and validate our theory.

heading: 1 INTRODUCTION
text: Deep learning has achieved tremendous successes in many domains including computer vision (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 a huge amount of data, and it is usually very computationally expensive. To speedup the training process, distributed training becomes indispensable (Dean et al., 2012). For example, Goyal et al. (2017) trained a ResNet-50 on ImageNet dataset by distributed SGD with minibatch size 8192 on 256 GPUs in only one hour, which not only matches the small minibatch accuracy but also enjoys parallel speedup, and hence improves the running time. Recently, there is an increasing interest in an variant of distributed learning, namely Federated Learning (FL) (McMahan et al., 2017), which focuses on the cases where the training data is non-i.i.d. across devices and only limited communication 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 gradient clipping from nonconvex optimization’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 as the relaxed smoothness condition (i.e., (L0, L1)-smoothness defined in Definition 2), which generalizes but strictly relaxes the usual smoothness condition (i.e., L-smoothness defined in Definition 1). Under the relaxed smoothness
condition, Zhang et al. (2019; 2020) proved that gradient clipping enjoys polynomial-time 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 accelerate 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:

heading: 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 machines and limited communication?
text: 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 a communication-efficient 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 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 version. These key features make our algorithm amenable to the FL setting and it 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 simultaneously. Our main contribution is summarized as the following:
• We design a novel communication-efficient 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-efficient 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 ϵ-stationary point. First, comparing with (Zhang et al., 2020), we prove that our algorithm enjoys linear speedup, which means that the iteration complexity of our algorithm is reduced by a factor of N (the number of machines). Second, comparing with naive parallel verion of the algorithm of (Zhang et al., 2020), we
1In this setting, we assume the gradient norm is upper bounded by M such that the gradient is (L0+L1M)Lipschitz. However, we want to emphasize that the original paper of (Ghadimi & Lan, 2013) does not require bounded gradient assumption, instead they require L-Lipschitz gradient and bounded variance σ2. Under their assumption, their complexity result is O ( ∆Lϵ−2 +∆Lσ2ϵ−4 ) .
2Naive Parallel of (Zhang et al. 2020) is different from our algorithm (CELGC) with I = 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.
prove that our algorithm enjoys better communication complexity. Specifically, our algorithm’s communication complexity is smaller than naive parallel clipping algorithm if the number of machines is not too large (i.e., N ≤ O(1/ϵ)). The detailed comparison over existing algorithms under the same relaxed smoothness condition is described in Table 1. Please refer to (Koloskova et 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 participation of machines. The experimental results demonstrate that our proposed algorithm indeed exhibit speedup in practice.

heading: 2 RELATED WORK
text: Gradient Clipping/Normalization 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 in 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 an 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 algorithms 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 et al. (2019) and Zhang et 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.
Communication-Efficient 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 stochastic approximation algorithm and averages the model weights across machines only at the very last iteration. One-shot averaging scheme is communication-efficient and enjoys statistical convergence with one pass of the data (Zhang et al., 2013; Shamir & Srebro, 2014; Jain et al., 2017; Koloskova et al., 2019), but the training error may not converge in practice. McMahan et al. (2017) considered 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-efficient since every node communicates with 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 a while. Stich (2018) also showed that local SGD enjoys linear speedup for stronglyconvex 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 et 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; Lin et al., 2018; Basu et al.,
2019; Haddadpour et al., 2019; Karimireddy et al., 2020). Recently, Woodworth et al. (2020a;b) analyzed advantages and drawbacks of local SGD compared with minibatch SGD for convex objectives. Woodworth et al. (2021) proved hardness results for distributed stochastic convex optimization. Reddi et al. (2021) introduced a general framework of federated optimization and designed several federated versions of adaptive optimizers. Zhang et al. (2021) considered to employ gradient clipping to optimize L-smooth functions and achieve differential privacy. Due to a 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 is the first communication-efficient algorithm which does not rely on these assumptions but still enjoys linear speedup.

heading: 3 PRELIMINARIES, NOTATIONS AND PROBLEM SETUP
text: Preliminaries and Notations Denote ∥ · ∥ by the Euclidean norm. We denote f : Rd → R as the overall loss function, and fi : Rd → R as the loss function on i-th machine, where i = 1, . . . , N . Denote ∇h(x) as the gradient of h evaluated at the point x, and denote ∇h(x; ξ) as the stochastic gradient of h calculated based on sample ξ. Definition 1 (L-smoothness). A function h is L-smooth if ∥∇h(x) −∇h(y)∥ ≤ L∥x − y∥ for all x,y ∈ Rd. Definition 2 ((L0, L1)-smoothness). A second order differentiable function h is (L0, L1)-smooth if ∥∇2h(x)∥ ≤ L0 + L1∥∇h(x)∥ for any x ∈ Rd. Definition 3 (ϵ-stationary point). x ∈ Rd is an ϵ-stationary point of the function h if ∥∇h(x)∥ ≤ ϵ.
Remark: From definitions, we know that the (L0, L1)-smoothness is strictly weaker than Lsmoothness. To see this, first, we know that L-smooth functions is (L0, L1)-smooth with L0 = L and L1 = 0. However the reverse is not true. For example, consider the function h(x) = x4, we know that the gradient is not Lipschitz continuous and hence is not L-smooth, but |h′′(x)| = 12x2 ≤ 12 + 3 × 4|x|3 = 12 + 3|h′(x)|, so h(x) = x4 is (12, 3)-smooth. Zhang et al. (2019) empirically showed that the (L0, L1)-smoothness 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 ϵ-stationary point since it is NP-hard to find a global optimal solution for a general nonconvex function.
Problem Setup In this paper, we consider the following optimization problem:
min x∈Rd
f(x) = 1
N N∑ i=1 fi(x), (1)
where N is the number of nodes and each fi(x) := Eξi∼Di [Fi(x; ξi)] is a nonconvex function where Di can be possibly different for different i. This formulation has broad applications in distributed deep learning and FL. For example, in FL setting, fi stands for the loss function on i-th machine, Di represents the data distribution on i-th machine, and N machines want to jointly optimize the objective function f .
We make the following assumptions throughout the paper. Assumption 1. (i) Each function fi(x) is (L0, L1)-smooth, i.e., ∥∇2fi(x)∥ ≤ L0 +
L1∥∇fi(x)∥, for ∀x ∈ Rd and i = 1, . . . , N .
(ii) There exists ∆ > 0 such that f(x0)− f∗ ≤ ∆, where f∗ is the global optimal value of f .
(iii) For all x ∈ Rd, Eξi∼Di [∇Fi(x; ξi)] = ∇fi(x), and ∥∇Fi(x; ξ) − ∇fi(x)∥ ≤ σ almost surely.
(iv) 1N ∑N i=1 ∥∇fi(x)−∇f(x)∥ ≤ κ.
Remark: The Assumption 1 (i) means that that the loss function defined on each machine satisfies the relaxed-smoothness condition, and it holds when we want to train a language model using LSTMs. Assumption 1 (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
Algorithm 1 Communication Efficient Local Gradient Clipping (CELGC) 1: for t = 0, . . . , T do 2: Each node i samples its stochastic gradient ∇Fi(xit; ξit), where ξit ∼ Di. 3: Each node i updates it local solution in parallel:
xit+1 = x i t −min
( η,
γ
∥∇Fi(xit; ξit)∥
) ∇Fi(xit; ξit) (2)
4: if t is a multiple of I then 5: Each worker resets the local solution as the averaged solution across nodes:
xit = x̂ := 1
N N∑ j=1 xjt ∀i ∈ {1, . . . , N} (3)
6: end if 7: end for
stronger assumption than the bounded variance, but it is a normal assumption when encountering relaxed smoothness. Assumption 1 (iv) quantifies the averaged heterogeneity across nodes, which is frequently used in the FL literature (e.g., Yu et al. (2019a)).

heading: 4 ALGORITHM AND THEORETICAL ANALYSIS

heading: 4.1 MAIN DIFFICULTY AND THE ALGORITHM DESIGN
text: 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 we 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 it 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 L-smooth, so the usual local SGD analysis for L-smooth 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 1. The algorithm calculates a 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. Note that the naive version of the parallel gradient clipping algorithm in (Zhang et al., 2020) needs to aggregates model parameters and gradients across all machines at every iteration, and perform one step of gradient 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 communication 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-asymptotic convergence guarantees are not established yet. In other words, we aim to establish iteration and communication complexity for Algorithm 1 for finding an ϵ-stationary point. We present our main theoretical results as below.

heading: 4.2 MAIN RESULTS
text: Theorem 1. Suppose Assumption 1 holds and σ+κ ≥ 1. Take ϵ ≤ min(AL0BL1 , 0.1) be a small enough constant and N ≤ min( 1ϵ , 14AL0 5BL1ϵ ). In Algorithm 1, choose I ≤ 12Nϵ , γ ≤ Nϵ 28(σ+κ) min{ ϵ AL0 , 1BL1 } and the fixed ratio γη = 5(σ + κ), where A ≥ 1 and B ≥ 1 are constants which will be specified in the proof, and run Algorithm 1 for T = O ( ∆L0 Nϵ4 ) iterations. Then we have
1
T T∑ t=1 E∥∇f(x̄t)∥ ≤ 4ϵ.
Remark: We have some implications of Theorem 1. When the number of machines is not large (i.e., N ≤ O(1/ϵ)) and the number of skipped communications is not large (i.e., I ≤ O(1/ϵN)), then with proper setting of learning rate, we have following observations. First, our algorithm enjoys linear speedup, since the number of iterations we need to find an ϵ-stationary point is divided by the number of machines N when comparing the single machine algorithm in (Zhang et al., 2020). Second, our algorithm is communication-efficient, since the communication complexity is T/I = O ( ∆L0(σ + κ) 2ϵ−3 ) , which provably improves the naive parallel gradient clipping algorithm of (Zhang et al., 2020) with O(∆L0σ2/(Nϵ4)) communication complexity when N ≤ O(1/ϵ). Another important fact is that both iteration complexity and communication complexity only depend on L0, independent of L1 and the gradient upper bound M . This indicates that our algorithm does not suffer from slow convergence even if these quantities are large. 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).

heading: 4.3 SKETCH OF THE PROOF OF THEOREM 1
text: In this section, we present the sketch of our proof of Theorem 1 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(x̄t)}Tt=0 in the FL setting under the relaxed smoothness condition, where x̄t = 1N ∑t i=1 x i t is the averaged weight across all machines at t-th iteration. The main challenge is that the descent property of (L0, L1)-smooth 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 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 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, we 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 magnitude is an indicator of whether the clipping operation happens or not. For each fixed iteration t, we define J(t) = {i ∈ {1 : N} : ∥∇Fi(xit, ξit)∥ ≥ γ/η} and J̄(t) = {1 : N}\J(t). Briefly speaking, J(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 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 t = 0, . . . , T , we can get an upper bound of the gradient in the ergodic sense.
Second, Zhang et al. (2020) inspect their algorithm’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 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 (η, γ, I) and using an amortized analysis, we prove that our 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 to 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 to proceed with the proof in detail.
Lemma 1 characterizes the ℓ2 error between averaged weight and individual weights at t-th iteration. Intuitively, the ℓ2 error scales linearly in terms of the length of node synchronization interval I .
Lemma 1. Under Assumption 1, for any i and t, Algorithm 1 ensures ∥x̄t−xit∥ ≤ 2γI holds almost surely.
Lemma 4 and Lemma 5 (included in Appendix A) are some properties of (L0, L1)-smooth functions and we need to use them frequently in our paper. To make sure they work, we need 2γI ≤ c/L1 for
some c > 0. This inequality follows from the choice of parameters in Theorem 1 and details will be shown in Appendix B. We denote A = 1 + ec − e
c−1 c and B = ec−1 c .
Let J(t) be the index set of i such that ∥∇Fi(xit, ξit)∥ ≥ γ η at fixed iteration t, i.e., J(t) = {i ∈ [1, . . . , N ] | ∥∇Fi(xit, ξit)∥ ≥ γ η }. Lemma 2 characterizes how much progress we can get in one iteration of Algorithm 1, and the progress is decomposed into contributions from every machine (note that J(t) ∪ J̄(t) = {1, . . . , N} for every t). Lemma 2. Let J(t) be the set defined as above. If 2γI ≤ c/L1 for some c > 0,If AL0η ≤ 1/2, then we have
E[f(x̄t+1)− f(x̄t)]
≤ 1 N
E ∑
i∈J(t)
[ −2γ
5 ∥∇f(x̄t)∥ −
3γ2
5η +
7γ
5 ∥∇Fi(xit; ξit)−∇f(x̄t)∥+AL0γ2 + BL1γ 2∥∇f(x̄t)∥ 2 + AL0η 2σ2 N
]
+E 1
N ∑ i∈J̄(t) [ −η 2 ∥∇f(x̄t)∥2 + 4γ2I2A2L20η + 4γ2I2B2L21η∥∇f(x̄t)∥2 + AL0η 2σ2 N + BL1γ 2∥∇f(x̄t)∥ 2 ] ,
where A = 1 + ec − e c−1 c and B = ec−1 c .
Lemma 3 quantifies an upper bound of the averaged ℓ2 error between local gradient evaluated at the local weight and the gradient evaluated at the averaged weight. The upper bound contains the noise term in stochastic gradient σ, the data heterogeneity κ, and another error term which scales linearly with the length of node synchronization interval I . Lemma 3. Suppose Assumption 1 holds. If 2γI ≤ c/L1 for some c > 0, then we obtain
1
N N∑ i=1 ∥∥∇Fi(xit; ξit)−∇f(x̄t)∥∥ ≤ σ + κ+ 2γI(AL0 +BL1∥∇f(x̄t)∥) almost surely, where A = 1 + ec − e
c−1 c and B = ec−1 c .
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 to get an upper bound of∑T−1
t=0 E [f(x̄t+1)− f(x̄t)] = E [f(x̄T )− f(x̄0)]. Note that E [f(x̄T )− f(x̄0)] ≥ −∆ due to Assumption 1, 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.

heading: 5 EXPERIMENTS
text: We conduct extensive experiments to 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 is 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 experiments, 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 framework are implemented in Pytorch 1.4. Due to limited computational resources, we 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.

heading: 5.1 EFFECTS OF SKIPPING COMMUNICATION
text: 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
other nodes periodically with node synchronization interval length I . To study how communication skipping affects the convergence of Algorithm 1, we run it with I ∈ {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 architecture. Specifically, we use the initial learning rate η = 0.3, the clipping threshold γ = 1.0, and decrease the learning rate by a factor of 10 at epoch 80 and 120. The local batch size at each GPU is 64. These parameter settings follow that of Yu et al. (2019a).
The results are illustrated in Figure 1. Figure 1a 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, if the x-axis value is 8, then each GPU runs 1 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 v.s. 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 et al., 2018) to do language modeling on Penn Treebank (PTB) dataset (Marcus et al., 1993)(word
level). We use SGD with clipping as the baseline algorithm with the initial learning rate η = 30 and the clipping threshold γ = 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-wise in terms of validation perplexity, we do better in training, and gains substantial speedup (2x faster for I = 16) wall-clock-wise.
Language modeling with LSTM on Wikitext-2. We again adopt the 3-layer AWD-LSTM (Merity et al., 2018) to do language modeling on Wikitext-2 dataset (Marcus et al., 1993)(word level). We use SGD with clipping as the baseline algorithm with the initial learning rate η = 30 and the clipping threshold γ = 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 in both training loss and validation perplexity epoch wise, but we again obtain large speedup (2.5x faster for I = 16) wall-clockwise. 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 1 can allow relatively large I without hurting the convergence behavior.

heading: 5.2 VERIFYING PARALLEL SPEEDUP
text: Figure 4 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 1 on all machine; 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 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, 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 1.

heading: 5.3 CLIPPING OPERATION HAPPENS FREQUENTLY
text: 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 like 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.

heading: 6 CONCLUSION
text: In this paper, we design a communication-efficient 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, we theoretically prove both the linear speedup property and the improved communication complexity. Our empirical studies show that our algorithm indeed enjoys parallel speedup and greatly improves the runtime performance due to skipping communication rounds in various scenarios.

heading: APPENDIX
text: A PROPERTIES OF (L0, L1) FUNCTIONS AND USEFUL LEMMAS
Lemma 4 (Descent inequality in Zhang et al. (2020)). Let f be (L0, L1)-smooth, and c > 0 be a constant. For any xk and xk+1, as long as ∥xk − xk+1∥ ≤ c/L1, we have
f(xk+1) ≤ f(xk) + ⟨∇f(xk),xk+1 − xk⟩+ AL0 +BL1∥∇f(xk)∥
2 ∥xk+1 − xk∥2, (4)
where A = 1 + ec − e c−1 c and B = ec−1 c .
Lemma 5 (Zhang et al. (2020)). Let f be (L0, L1)-smooth, and c > 0 be a constant. For any xk and xk+1, as long as ∥xk − xk+1∥ ≤ c/L1, we have
∥∇f(xk+1)−∇f(xk)∥ ≤ (AL0 +BL1∥∇f(xk)∥) ∥xk+1 − xk∥, (5)
where A = 1 + ec − e c−1 c and B = ec−1 c .
Lemma 6 (Zhang et al. (2020)). Let µ ≥ 0 be a real constant. For any vector u and v,
−⟨u,v⟩ ∥v∥ ≤ −µ∥u∥ − (1− µ)∥v∥+ (1 + µ)∥v − u∥. (6)

heading: B PROOF OF THEOREM 1
text: During the proof of Theorem 1, we need the following simple fact for our algorithm.
Fact Recall the definition of x̄t = 1N ∑N i=1 x i t for a fixed iteration t, Algorithm 1 immediately
gives us x̄t+1 − x̄t = − 1N ∑N i=1 min ( η, γ∥∇Fi(xit;ξit)∥ ) ∇Fi(xit; ξit), and hence ∥x̄t+1 − x̄t∥2 ≤ γ2 holds for any t.

heading: B.1 PROOF OF LEMMA 1
text: Lemma 1 restated Under Assumption 1, Algorithm 1 ensures
∥x̄t − xit∥ ≤ 2γI,∀i,∀t almost surely. (7)
Proof. Fix t ≥ 1 and i. Note that Algorithm 1 calculates the node average every I iterations. Let t0 ≤ t to be the largest multiple of I . Then we know x̄t0 = xit for all i. (Note that t− t0 ≤ I). We further notice that
xit = x̄t0 − t−1∑ τ=t0 min ( η,
γ
∥∇Fi(xit, ξit)∥
) ∇Fi(xit, ξit).
By the definition of x̄t, we have
x̄t = x̄t0 − t−1∑ τ=t0 1 N N∑ j=1 min
( η,
γ
∥∇Fj(xjt , ξ j t )∥
) ∇Fj(xjt , ξ j t )
Thus, we have
∥x̄t − xit∥2
= ∥∥∥∥∥∥ t−1∑ τ=t0 min ( η,
γ
∥∇Fi(xit, ξit)∥
) ∇Fi(xit, ξit)− t−1∑ τ=t0 1 N N∑ j=1 min ( η,
γ
∥∇Fj(xjt , ξ j t )∥
) ∇Fi(xjt , ξ j t ) ∥∥∥∥∥∥ 2
≤ 2 ∥∥∥∥∥ t−1∑ τ=t0 min ( η,
γ
∥∇Fi(xit, ξit)∥
) ∇Fi(xit, ξit) ∥∥∥∥∥ 2 + 2 ∥∥∥∥∥∥ t−1∑ τ=t0 1 N N∑ j=1 min ( η,
γ
∥∇Fj(xjt , ξ j t )∥
) ∇Fj(xjt , ξ j t ) ∥∥∥∥∥∥ 2
≤ 2(t− t0) t−1∑ τ=t0 ∥∥∥∥min(η, γ∥∇Fi(xit, ξit)∥ ) ∇Fi(xit, ξit) ∥∥∥∥2 + 2(t− t0)N2 t−1∑ τ=t0 ∥∥∥∥∥∥ N∑ j=1 min ( η,
γ
∥∇Fj(xjt , ξ j t )∥
) ∇Fj(xjt , ξ j t ) ∥∥∥∥∥∥ 2
≤ 2γ2(t− t0) t−1∑ τ=t0 ∥∥∥∥ ∇Fi(xit, ξit)∥∇Fi(xit, ξit)∥ ∥∥∥∥2 + 2(t− t0)N2 N t−1∑ τ=t0 N∑ j=1 γ2 ∥∥∥∥∥ ∇Fj(xjt , ξjt )∥∇Fi(xjt , ξjt )∥ ∥∥∥∥∥ 2
≤ 2γ2I2 + 2(t− t0) N t∑ τ=t0+1 N∑ j=1 γ2
≤ 4γ2I2. (8)
The technique we mainly use in this proof is the inequality ∥ ∑K j=1 zj∥2 ≤ K ∑K
j=1 ∥zj∥2 for any K vectors z1, . . . , zK . Taking the square root for both sides, then we obtain the desired result.

heading: B.2 PROOF OF LEMMA 2
text: Note that J(t) = {i ∈ [1, . . . , N ] | ∥∇Fi(xit, ξit)∥ ≥ γ η }.
Lemma 2 restated If AL0η ≤ 1/2 and 2γI ≤ c/L1 for some c > 0, then we have E[f(x̄t+1)− f(x̄t)]
≤ 1 N
E ∑
i∈J(t)
[ −2γ
5 ∥∇f(x̄t)∥ −
3γ2
5η +
7γ
5 ∥∇Fi(xit; ξit)−∇f(x̄t)∥+AL0γ2 + BL1γ 2∥∇f(x̄t)∥ 2
]
+ 1
N ∑ i∈J̄(t) E [ −η 2 ∥∇f(x̄t)∥2 + 4γ2I2A2L20η + 4γ2I2B2L21η∥∇f(x̄t)∥2 + AL0η 2σ2 N + BL1γ 2∥∇f(x̄t)∥ 2 ] ,
where A = 1 + ec − e c−1 c and B = ec−1 c .
Proof. By the (L0, L1)-smoothness and invoking Lemma 4 and noting that ∥x̄t+1 − x̄t∥ ≤ γ for any t, we have
E [f(x̄t+1)− f(x̄t)]
≤E⟨∇f(x̄t), x̄t+1 − x̄t⟩+ (AL0 +BL1 ∥∇f(x̄t)∥)
2 E∥x̄t+1 − x̄t∥2
≤− γE
〈 1
N ∑ i∈J(t) ∇Fi(xit, ξit) ∥∇Fi(xit; ξit)∥ ,∇f(x̄t)
〉 − ηE 〈 1
N ∑ i∈J̄(t) ∇Fi(xit, ξit),∇f(x̄t)
〉
+ AL0 2 E∥x̄t+1 − x̄t∥2 + BL1∥∇f(x̄t)∥γ2 2 .
(9)
For each iteration t, we first consider the case where i ∈ J(t), i.e. ∥∇Fi(xit, ξit)∥ ≥ γ η . We use Lemma 6 with µ = 25 to obtain the following result
−γ 〈 ∇Fi(xit, ξit),∇f(x̄t) 〉 ∥∇Fi(xit; ξit)∥ ≤ −2γ 5 ∥∇f(x̄t)∥ − 3γ2 5η + 7γ 5 ∥∇Fi(xit; ξit)−∇f(x̄t)∥. (10)
Taking the expectation for both sides of above inequality, then we obtain
− γE
〈 1
N ∑ i∈J(t) ∇Fi(xit, ξit) ∥∇Fi(xit; ξit)∥ ,∇f(x̄t)
〉 ≤ 1 N E ∑
i∈J(t)
[ −2γ
5 ∥∇f(x̄t)∥ −
3γ2
5η +
7γ
5 ∥∇Fi(xit; ξit)−∇f(x̄t)∥
] .
(11)
Next, we consider the case in which i ∈ J̄(t), i.e. ∥∇Fi(xit, ξit)∥ ≤ γ η at fixed iteration t. Denote ξ[t−1] by the σ-algebra generated by all random variables until (t − 1)-th iteration, i.e., ξ[t−1] = σ(ξ10 , . . . , ξ N 0 , ξ 1 1 , . . . , ξ N 1 , . . . , ξ 1 t−1, . . . , ξ N t−1). We notice that
− ηE
〈 1
N ∑ i∈J̄(t) ∇Fi(xit, ξit), E [ |J̄(t)| ] N ∇f(x̄t) 〉 = −ηE E〈 1 N ∑ i∈J̄(t) ∇Fi(xit, ξit), E [ |J̄(t)| ] N ∇f(x̄t) ∣∣∣∣∣∣ ξ[t−1] 〉
= −ηE 〈E  1 N ∑ i∈J̄(t) ∇Fi(xit, ξit) ∣∣∣∣∣∣ ξ[t−1]  , E [|J̄(t)|] N ∇f(x̄t) 〉 = −ηE [〈 E [ 1
N N∑ i=1 ∇Fi(xit, ξit)I(i ∈ J̄(t)) ∣∣∣∣∣ ξ[t−1] ] , E [ |J̄(t)| ] N ∇f(x̄t) 〉] (a) = −ηE [〈 1
N N∑ i=1 pi∇fi(xit), E [ |J̄(t)| ] N ∇f(x̄t) 〉]
(b) = −η
2 E ∥∥∥∥∥E [ |J̄(t)| ] N ∇f(x̄t) ∥∥∥∥∥ 2 + ∥∥∥∥∥ 1N N∑ i=1 pi∇fi(xit) ∥∥∥∥∥ 2 − ∥∥∥∥∥ 1N N∑ i=1 pi∇fi(xit)− E [ |J̄(t)| ] N ∇f(x̄t) ∥∥∥∥∥ 2 
= −η(E|J̄(t)|) 2
2N2 E ∥∇f(x̄t)∥2 −
η 2 E ∥∥∥∥∥ 1N N∑ i=1 pi∇fi(xit) ∥∥∥∥∥ 2 + η 2 E ∥∥∥∥∥ 1N N∑ i=1 pi(∇f(x̄t)−∇fi(xit)) ∥∥∥∥∥ 2
(c) ≤ −η(E|J̄(t)|) 2
2N2 E ∥∇f(x̄t)∥2 −
η 2 E ∥∥∥∥∥ 1N N∑ i=1 pi∇fi(xit) ∥∥∥∥∥ 2 + η 2 (E|J̄(t)|)2 N2 1 N E N∑ i=1 ∥∥(∇fi(x̄t)−∇fi(xit))∥∥2 (d)
≤ −η(E|J̄(t)|) 2
2N2 E ∥∇f(x̄t)∥2 −
η 2 E ∥∥∥∥∥ 1N N∑ i=1 pi∇fi(xit) ∥∥∥∥∥ 2 + η 2 (E|J̄(t)|)2 N2 E [ 4γ2I2 (AL0 +BL1∥∇f(x̄t)∥)2 ] (e)
≤ −η(E|J̄(t)|) 2
2N2 E ∥∇f(x̄t)∥2 −
η 2 E ∥∥∥∥∥ 1N N∑ i=1 pi∇fi(xit) ∥∥∥∥∥ 2 + η 2 (E|J̄(t)|)2 N2 E [ 2γ2I2 ( 2A2L20 + 2B 2L21∥∇f(x̄t)∥2 )]
≤ −η(E|J̄(t)|) 2
2N2 E ∥∇f(x̄t)∥2 −
η 2 E ∥∥∥∥∥ 1N N∑ i=1 pi∇fi(xit) ∥∥∥∥∥ 2 + (E|J̄(t)|)2 N2 E [ 4γ2I2A2L20η + 4γ 2I2B2L21η∥∇f(x̄t)∥2 ] ,
(12) where (a) holds due to Lemma 8 with Ai = ∇Fi(xit; ξit), Bi = I(i ∈ J̄(t)), 0 ≤ pi ≤ 1 is the corresponding constant defined in Lemma 8 and ∑N i=1 pi = E [ |J̄(t)| ] ; (b) holds by using the basic
identity ⟨x1,x2⟩ = 12 ( ∥x1∥2 + ∥x2∥2 − ∥x1 − x2∥2 ) for any two vectors x1,x2; (c) holds due to
Jensen’s inequality and ∑N
i=1 pi = E|J̄(t)|. (d) holds due to Lemma 1 and Lemma 5, (e) holds since (a+ b)2 ≤ 2a2 + 2b2.
Next, we compute E∥x̄t+1 − x̄t∥2. By definition, we have
E∥x̄t+1 − x̄t∥2 = E ∥∥∥∥∥ 1N N∑ i=1 min ( η,
γ
∥∇Fi(xit; ξit)∥
) ∇Fi(xit, ξit) ∥∥∥∥∥ 2
= 1
N2 E ∥∥∥∥∥ N∑ i=1 min ( η,
γ
∥∇Fi(xit; ξit)∥
) ∇Fi(xit, ξit) ∥∥∥∥∥ 2 = 1 N2 E ∥∥∥∥∥∥γ ∑
i∈J(t)
∇Fi(xit, ξit) ∥∇Fi(xit; ξit)∥
+ η ∑
i∈J̄(t)
η∇Fi(xit; ξit) ∥∥∥∥∥∥ 2
≤ 2γ2E ∥∥∥∥∥∥ 1N ∑
i∈J(t)
∇Fi(xit, ξit) ∥∇Fi(xit; ξit)∥ ∥∥∥∥∥∥ 2 + 2η2E ∥∥∥∥∥ 1N N∑ i=1 ∇Fi(xit, ξit)I ( i ∈ J̄(t) )∥∥∥∥∥ 2
≤ 2γ 2
N2 E ∥∥∥∥∥∥ ∑
i∈J(t)
∇Fi(xit, ξit) ∥∇Fi(xit; ξit)∥ ∥∥∥∥∥∥ 2 + 2η2E ∥∥∥∥∥ 1N N∑ i=1 ∇Fi(xit, ξit)I ( i ∈ J̄(t) ) − E [ 1 N N∑ i=1 ∇Fi(xit, ξit)I ( i ∈ J̄(t) )]∥∥∥∥∥ 2
+ 2η2 ∥∥∥∥∥E ( 1 N N∑ i=1 ∇Fi(xit, ξit)I ( i ∈ J̄(t) ))∥∥∥∥∥ 2
(a) ≤ 2γ 2(E|J(t)|)2
N2 + 2η2E ∥∥∥∥∥ 1N N∑ i=1 ∇Fi(xit, ξit)− E [ 1 N N∑ i=1 ∇Fi(xit, ξit) ]∥∥∥∥∥ 2 + 2η2 ∥∥∥∥∥E ( 1 N N∑ i=1 ∇Fi(xit, ξit)I ( i ∈ J̄(t) ))∥∥∥∥∥ 2
≤ 2γ 2(E|J(t)|)2
N2 +
2η2σ2
N + 2η2 ∥∥∥∥∥E ( 1 N N∑ i=1 ∇Fi(xit, ξit)I ( i ∈ J̄(t) ))∥∥∥∥∥ 2
(b) =
2γ2(E|J(t)|)2
N2 +
2η2σ2
N + 2η2 ∥∥∥∥∥E ( N∑ i=1 pi∇fi(xit) )∥∥∥∥∥ 2
(13) where (a) holds due to Lemma 7 with Ai = ∇Fi(xit; ξit), Bi = I ( i ∈ J̄(t) ) ; (b) holds due to Lemma 8 with Ai = ∇Fi(xit; ξit), Bi = I(i ∈ J̄(t)), 0 ≤ pi ≤ 1 is the corresponding constant defined in Lemma 8 and ∑N i=1 pi = E [ |J̄(t)| ] .
Substituting (11), (12) and (13) into (9) yields
E[f(x̄t+1)− f(x̄t)]
≤ 1 N
E ∑
i∈J(t)
[ −2γ
5 ∥∇f(x̄t)∥ −
3γ2
5η +
7γ
5 ∥∥∇Fi(xit; ξit)−∇f(x̄t)∥∥]− ηE|J̄(t)|2N E∥∇f(x̄t)∥2 −η 2 N E|J̄(t)| E ∥∥∥∥∥ 1N N∑ i=1 pi∇fi(xit) ∥∥∥∥∥ 2 + E|J̄(t)| N E [ 4γ2I2A2L20η + 4γ 2I2B2L21η∥∇f(x̄t)∥2 ]
+ AL0γ
2(E|J(t)|)2
N2 +
AL0η 2σ2
N +AL0η
2 ∥∥∥∥∥E ( N∑ i=1 pi∇fi(xit) )∥∥∥∥∥ 2 + BL1γ 2E ∥∇f(x̄t)∥ 2
≤ 1 N
E ∑
i∈J(t)
[ −2γ
5 ∥∇f(x̄t)∥ −
3γ2
5η +
7γ
5 ∥∇Fi(xit; ξit)−∇f(x̄t)∥+AL0γ2 + BL1γ 2∥∇f(x̄t)∥ 2 + AL0η 2σ2 N
]
+ 1 N E ∑
i∈J̄(t)
[ −η 2 ∥∇f(x̄t)∥2 + 4γ2I2A2L20η + 4γ2I2B2L21η∥∇f(x̄t)∥2 + AL0η 2σ2 N + BL1γ 2∥∇f(x̄t)∥ 2 ] ,
(14) where the last inequality holds if AL0η ≤ 12 and E∥X∥ 2 ≥ ∥EX∥2.

heading: B.3 PROOF OF LEMMA 3
text: Lemma 3 restated Suppose Assumption 1 holds. If 2γI ≤ c/L1 for some c > 0, then we obtain
1
N N∑ i=1 ∥∇Fi(xit; ξit)−∇f(x̄t)∥ ≤ σ + κ+ 2γI(AL0 +BL1∥∇f(x̄t)∥) almost surely,
where A = 1 + ec − e c−1 c and B = ec−1 c .
Proof. By using triangular inequality and Lemma 5, we obtain
∥∇Fi(xit; ξit)−∇f(x̄t)∥ ≤ ∥∇Fi(xit; ξit)−∇fi(xit)∥+ ∥∇fi(xit)−∇f(xit)∥+ ∥∇f(xit)−∇f(x̄t)∥ ≤ σ + ∥∇fi(xit)−∇f(xit)∥+ 2γI(AL0 +BL1∥f(x̄t)∥).
Summing over i = 1 to N and by Assumption 1, we have
1
N N∑ i=1 ∥∇Fi(xit; ξit)−∇f(x̄t)∥ ≤ σ + κ+ 2γI(AL0 +BL1∥f(x̄t)∥).

heading: B.4 MAIN PROOF OF THEOREM 1
text: Proof. We consider 0 < ϵ ≤ min(AL0BL1 , 0.1) be a small enough constant and choose N ≤ min{ 1ϵ , 14AL0 5BL1ϵ }, γ ≤ Nϵ28(σ+κ) min{ ϵ AL0 , 1BL1 }, ratio γ/η = 5(σ + κ) and I ≤ 1 2Nϵ , we first check several important conditions which were used in previous Lemmas and we will use in our later proof.
AL0η ≤ AL0 Nϵ 5(σ + κ) · 28(σ + κ) ϵ
AL0
(a) ≤ ϵ 140(σ + κ)2 (b) ≤ ϵ 140 ≤ 1 2 ,
where (a) holds because of Nϵ ≤ 1 and (b) is true due to σ + κ ≥ 1. Note that Nϵ ≤ 1, σ + κ ≥ 1, A ≥ 1, B ≥ 1, and so we have
2γI ≤ 2 Nϵ 28(σ + κ) 1
BL1
1 2Nϵ ≤ 1 28L1 = c L1 ,
where c = 128 . Recall the descent inequality (Lemma 4), we can explicitly define
A = 1 + e1/28 − e 1/28 − 1 1/28
B = e1/28 − 1 1/28 .
We can show that our choice of ϵ guarantees that ϵAL0 ≤ 1 BL1 . Then, the upper bound of the parameter γ becomes Nϵ 2
28AL0(σ+κ) . Based on Lemma 2 and Lemma 3, we take summation over t
and obtain
E [ T−1∑ t=0 f(x̄t+1)− f(x̄t) ] (a) ≤ 1 N T−1∑ t=0 E ∑ i∈J(t) [P1 + P2∥∇f(x̄t)∥]
+ 1
N T−1∑ t=0 ∑ i∈J̄(t) E [ −η 2 ∥∇f(x̄t)∥2 + 4γ2I2A2L20η + 4γ2I2B2L21η∥∇f(x̄t)∥2 + AL0η 2σ2 N + BL1γ 2∥∇f(x̄t)∥ 2 ] (b) ≤ 1 N T−1∑ t=0 E ∑ i∈J(t) [P1 + P2∥∇f(x̄t)∥]
+ 1
N T−1∑ t=0 ∑ i∈J̄(t) E [ −η 4 ∥∇f(x̄t)∥2 + 4γ2I2A2L20η + AL0η 2σ2 N + BL1γ 2∥∇f(x̄t)∥ 2 ] ,
(15) where (a) holds due to Lemma 2, and
P1 = − 3γ2
5η +
7γ
5 (σ + κ) + 14γ2IAL0 5 +AL0γ 2 + AL0η 2σ2 N ,
P2 = − 2γ
5 + 14γ2IBL1 5 + BL1γ 2 2 ,
(b) is derived by computing
4γ2I2B2L21η ≤ 4N2ϵ4I2B2L21η 282(σ + κ)2A2L20 ≤ 4B 2L21ϵ 4η 282(σ + κ)2A2L20 282A2L20 25B2L21ϵ
2︸ ︷︷ ︸ bound of N2
1
4N2ϵ2︸ ︷︷ ︸ bound of I2
≤ η 4 (16)
with N ≤ min{ 1ϵ , 14AL0 5BL1ϵ }, γ ≤ Nϵ28(σ+κ) min{ ϵ AL0 , 1BL1 } and I ≤ 1 2Nϵ .
Now we give the upper bound of P1 and P2.
From the choice of N ≤ min{ 1ϵ , 14AL0 5BL1ϵ }, γ ≤ Nϵ 2 28AL0(σ+κ) , I ≤ 12Nϵ and the fixed ratio γ η = 5(σ + κ), and noting that σ + κ ≥ 1, we have
P1 ≤ ( −3 5 · 5(σ + κ) + 7 5 (σ + κ) + ϵ 20 + ϵ 28 ) γ ≤ − 3 10 γ(σ + κ) + AL0η 2σ2 N
P2 ≤ ( −2 5 + 1 20 + ϵ 10 ) γ ≤ − 1 10 γ
(17)
Plugging (17) back to (15), we obtain
−∆ ≤ −(f(x̄0)− f∗) ≤ Ef(x̄T )− f(x̄0) ≤ E  1 T T−1∑ t=0 ∑ i∈J(t) U(x̄t) + 1 T T−1∑ t=0 ∑ i∈J̄(t) V (x̄t)  , where
U(x̄t) = − 1
10 γ∥∇f(x̄t)∥ −
3
10 γ(σ + κ) +
AL0η 2σ2
N
V (x̄t) = − η
4 ∥∇f(x̄t)∥2 + 4γ2I2A2L20η +
AL0η 2σ2
N + BL1γ 2∥∇f(x̄t)∥ 2
(a) ≤ −ηϵ 2 ∥∇f(x̄t)∥+ BL1γ 2∥∇f(x̄t)∥ 2 + ηϵ2 2 + 4γ2I2A2L20η +AL0 η2 N σ2
(b) ≤ −ηϵ 4 ∥∇f(x̄t)∥+ ηϵ2 4 + 4γ2I2A2L20η +AL0 η2 N σ2.
Inequality (a) follows by using the standard inequality x2 ≥ 2ϵx− ϵ2 and (b) is true because
−ηϵ 2 + BL1γ
2 2 ≤ −ηϵ 4 . (18)
To check (18), we compute
BL1γ 2 ≤ BL15η(σ + κ)
Nϵ2
28AL0(σ + κ) = η
5BL1Nϵ 2
28AL0 ≤ ηϵ 2 , (19)
where the last inequality holds because we assume N ≤ 14AL05BL1ϵ .
It’s clear that U(x) ≤ V (x). Then we obtain
−∆ ≤ −(Ef(x̄0)− f∗) ≤ E [ T−1∑ t=0 V (x̄t) ] ≤ T−1∑ t=0 [ −ηϵ 4 E∥∇f(x̄t)∥+ ηϵ2 4 + 4γ2I2A2L20η +AL0 η2 N σ2 ] .
Then we rearrange above inequality and get
1
T T∑ t=1 E∥∇f(x̄t)∥ ≤ 4∆ ϵηT + ϵ+ 4AL0ησ 2 Nϵ + 16γ2I2A2L20 ϵ < 4ϵ,
as long as T ≥ 560AL0∆(σ+κ) 2
Nϵ4 and I ≤ 1 2Nϵ .

heading: C EXPERIMENTS DETAILS AND OTHER RESULTS

heading: C.1 CIFAR-10 CLASSIFICATION WITH RESNET-32
text: Apart from the 56 layer Resnet used in Section 5, we also trained the 32 layer Resnet on CIFAR-10. Here, we used a 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 η = 0.1 and the clipping parameter γ = 1.0. We decrease both η and γ by a factor of 10 at epoch 80 and 120. These parameter settings follow that of Zhang et al. (2020).
Results reported in Figure 6 again shows that our 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 .

heading: D USEFUL LEMMAS
text: Lemma 7. Suppose {Ai}Ni=1 is an sequence of vector-valued independent random variables, {Bi}Ni=1 is a sequence of independent random variables where Bi ∈ {0, 1} for every i. Suppose E∥Ai∥2 < +∞ for every i. Then we have
E ∥∥∥∥∥ 1N N∑ i=1 AiBi − E [ 1 N N∑ i=1 AiBi ]∥∥∥∥∥ 2 ≤ E ∥∥∥∥∥ 1N N∑ i=1 Ai − E [ 1 N N∑ i=1 Ai ]∥∥∥∥∥ 2 .
Proof. It suffices to show that E ∥AiBi − E [AiBi]∥2 ≤ E ∥Ai − E [Ai]∥2, since both {AiBi − E [AiBi]}Ni=1 and {Ai − E [Ai]}Ni=1 are sequences of independent random vectors with zero mean. Define Ci = 1 − Bi, and hence BiCi = 0 with probablity 1. Without loss of generality, we can assume E [Ai] = 0. Note that
E ∥Ai − E [Ai]∥2 = E ∥AiBi +AiCi∥2 = E ∥AiBi∥2 + E ∥AiCi∥2 + 2E⟨AiBi, AiCi⟩ = E ∥AiBi∥2 + E ∥AiCi∥2 ≥ E ∥AiBi∥2 = E ∥AiBi − E [AiBi]∥2 + ∥E (AiBi)∥2
≥ E ∥AiBi − E [AiBi]∥2 .
It completes the proof.
Lemma 8. Suppose {Ai}Ni=1 is an sequence of vector-valued independent random variables, {Bi}Ni=1 is a sequence of independent random variables where Bi ∈ {0, 1} for every i. Ai and Bj are independent of each other if i ̸= j. Then there exists (p1, . . . , pN ) where 0 ≤ pi ≤ 1 and∑N
i=1 pi = E [∑N i=1 Bi ] such that
E [ N∑ i=1 AiBi ] = N∑ i=1 piEAi. (20)
Proof. Without loss of generality, we can assume the sequence {Bi}Ni=1 is sorted in a decreasing order, i.e., B1 ≥ B2 ≥ . . . ≥ BN , since otherwise we can switch the order of summation in both LHS and RHS of the Equation (20). Define T̃ = sup{1 ≤ i ≤ N : Bi = 1}, and define Fs = σ(A1, B1, . . . , As, Bs), where σ(·) denotes σ-algebra generated by random variables in the argument. Since {T̃ = s} ∈ Fs for all s, we know that T̃ is a stopping time, and T̃ ≤ N almost surely. Hence we have
E [ N∑ i=1 AiBi ] = E  T̃∑ i=1 Ai  = E[+∞∑ i=1 AiI(T̃ ≥ i) ] = +∞∑ i=1 E [ E [ AiI(T̃ ≥ i)|Ft−1 ]] .
Note that I(T̃ ≥ i) = 1− I(T̃ ≤ i− 1) ∈ Fi−1, and Ai is independent of Fi−1, we know that +∞∑ i=1 E [ E [ AiI(T̃ ≥ i)|Ft−1 ]] = +∞∑ i=1 E [ I(T̃ ≥ i)E [Ai] ] = +∞∑ i=1 E [Ai]Pr(T̃ ≥ i) = N∑ i=1 E [Ai]Pr(T̃ ≥ i).
Define pi = Pr(T̃ ≥ i), we have 0 ≤ pi ≤ 1 and ∑N i=1 pi = E(T̃ ) = E [∑N i=1 Bi ] . Hence (20) is proved.

heading: E MORE EXPERIMENT RESULTS

heading: E.1 PARALLEL SPEEDUP ON NLP TASKS
text: 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 use minibatch size 3 on 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 to converge to the same targets (e.g., training loss, validation perplexity). This observation is consistent with our iteration complexity results in Theorem 1.

heading: E.2 GRADIENT NORM DYNAMICS
text: The careful reader might notice that in Theorem 1 we require N ≤ O ( 1 ϵ ) where ϵ is the desired ℓ2 norm of the gradient when converging and wonder if this is too strict and impractical.
Therefore, we draw the dynamics of the ℓ2 norm of gradients over epochs for training the Resnet-56 model to do image classification on CIFAR10 in Figure 8. It can be clearly seen that the gradient ℓ2 norm decreases to less than 0.1 after epoch 100 and eventually reaches around 0.06 at the epoch 200. Since 1/0.06 ≈ 17, this means that the N = 8 setting we used in our experiments is consistent with our theory.

heading: E.3 HETEROGENEOUS SETTING
text: In the previous experiments, all machines can access the whole dataset. Yet, in practice, each machine might only access a subset of the whole dataset and the data might not be evenly distributed across machines. Therefore, we conduct an experiment on this heterogeneous setting. Specifically, we take the Penn Treebank training set which is a text file and divide it into 8 non-overlapping consecutive parts which contain {10.64%, 11.17%, 11.70%, 12.23%, 12.77%, 13.30%, 13.83%, 14.36%} of the whole text file respectively. We then train the AWD-LSTM of the same structure as 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.
The results are reported in Figure 9. Note that, as the size of training data in 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, our 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.

heading: E.4 PERFORMANCE VS. COMMUNICATION ROUNDS
text: 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 are very close to that w.r.t. the wall-clock time which is as expected.

heading: E.5 PARTIAL PARTICIPATION
text: 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 (different) subset of nodes participate in communication each time. Therefore, we conduct an experiment 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 a communication across nodes, we randomly select 6 out of the total 8 nodes to communicate 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 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.
The results are reported in Figure 11. We can see that, though the partial participation setting slightly deteriorates the performance for both the baseline and our algorithm as compared with Figure 2a, our algorithm is still able to closely match the baseline for both the training loss and the validation
perplexity epoch-wise, but also note that our algorithm greatly saves wall-clock time. This indicates that our algorithm is robust in the partial participation setting.

heading: E.6 LARGE MINI-BATCH
text: The distributed learning paradigm is especially desirable with training using large mini-batches. To this end, we trained a Resnet-56 model on CIFAR10 with batch-size 256 on each node which sums up to a 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 to 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 our algorithm.

Review summaries:
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).

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.

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.