Title: VARIANCE REDUCED LOCAL SGD WITH LOWER COMMUNICATION COMPLEXITY Anonymous authors Paper under double-blind review

Abstract: To accelerate the training of machine learning models, distributed stochastic gradient descent (SGD) and its variants have been widely adopted, which apply multiple workers in parallel to speed up training. Among them, Local SGD has gained much attention due to its lower communication cost. Nevertheless, when the data distribution on workers is non-identical, Local SGD requires O(T
) communications to maintain its linear iteration speedup property, where T is the total number of iterations and N is the number of workers. In this paper, we propose Variance Reduced Local SGD (VRL-SGD) to further reduce the communication complexity. Benefiting from eliminating the dependency on the gradient variance among workers, we theoretically prove that VRL-SGD achieves a linear iteration speedup with a lower communication complexity O(T
) even if workers access non-identical datasets. We conduct experiments on three machine learning tasks, and the experimental results demonstrate that VRL-SGD performs impressively better than Local SGD when the data among workers are quite diverse.
Under review as a conference paper at ICLR 2020 ance reduction component, VRL-SGD eliminates the extra assumption about bounded gradient variance among workers in previous studies based on Local SGD (Yu et al., 2019a;b; Shen et al., 2019) . Thus the communication complexity can be reduced from O(T
) in VRL-SGD for the non-identical case, which is crucial for achieving a better time speedup. Therefore, VRL-SGD is more suitable than Local SGD for the scenarios, such as federated learning (Konečnỳ et al., 2016) , where the gradient variance across workers might be large.
Contributions of this paper are summarized as follows:
• We propose VRL-SGD, a novel distributed optimization algorithm with a state-of-the-art communication complexity. Specifically, the communication complexity is reduced from O(T
2 ) for the non-identical case. To the best of our knowledge, this is the first time that an algorithm based on Local SGD possesses such a communication complexity for the non-identical case. Meanwhile, VRL-SGD also achieves the optimal communication complexity for the identical case.
• We provide a theoretical analysis and prove that VRL-SGD has a linear iteration speedup with respect to the number of workers. Our method does not require the extra assumptions, e.g. the gradient variance across workers is bounded. • We validate the effectiveness of VRL-SGD on three standard machine learning tasks. And experimental results show that the proposed algorithm performs significantly better than Local SGD if data distribution in workers is different, while maintains the same convergence rate as Local SGD if all workers access identical datasets. 2 RELATED WORK Synchronous stochastic gradient descent (S-SGD) is a parallelized version of mini-batch SGD and is theoretically proved to achieve a linear iteration speedup with respect to the number of workers (Dekel et al., 2012; Ghadimi & Lan, 2013). Nevertheless, due to the communication bottleneck, it is difficult to obtain the property of linear time speedup. To eliminate communication bottlenecks, many distributed SGD-based methods are proposed, such as lossy compression methods (Alistarh et al.,

1. INTRODUCTION:

With the expansion of data and model scale, the training of machine learning models, especially deep learning models has become increasingly time-consuming. To accelerate the training process, distributed parallel optimization has attracted widespread interests recently, which encourages multiple workers to cooperatively optimize the model.

For large-scale machine learning problems, stochastic gradient descent (SGD) is a fundamental tool. It can be easily parallelized by collecting stochastic gradient from different workers and hence it is widely adopted. Previous studies (Dekel et al., 2012; Ghadimi & Lan, 2013) justify that synchronous stochastic gradient descent (S-SGD) has a linear iteration speedup for both general convex and nonconvex objectives, which means that the total number of iterations is reduced by N times with N workers. However, S-SGD suffers from a major drawback: the communication cost among workers is expensive when the number of workers is large, which prevents S-SGD from achieving a linear time speedup. Therefore, it is crucial to overcome the communication bottleneck.

To reduce communication cost, several studies (Wang & Joshi, 2018; Zhou & Cong, 2018; Stich, 2019; Yu et al., 2019b; Shen et al., 2019) have managed to lower the communication frequency. Among them, Local SGD (Stich, 2019) is a representative distributed algorithm, where workers can conduct SGD locally and average model with each other every k iterations. Compared with S-SGD, the algorithms based on Local SGD reduce the communication rounds from O(T ) to O(T /k). To deal with the gradient variance among workers, previous studies require at least one of the following extra assumptions: (1) the bounded gradient variance among workers; (2) an upper bound for gradients; (3) identical data on all workers. When the data distribution on workers is identical, which is the so-called identical case, the algorithms based on Local SGD can exhibit superior performance. Nevertheless, the identical data assumption is not always valid in real cases. When the data distribution on workers is non-identical, which is the so-called non-identical case, these algorithms would encounter a significant degradation in the convergence rate due to the gradient variance among workers. We seek to eliminate the gradient variance among workers, which may make the algorithm converge much faster than the vanilla Local SGD.

In this paper, we propose Variance Reduced Local SGD (VRL-SGD), a novel distributed optimization algorithm to further reduce the communication complexity. Benefiting from an additional vari-Table 1 : Comparisons of the communication complexity for different algorithms. The second column and the third column show communication complexity for identical and non-identical datasets respectively. Here, we regard the following assumptions as extra assumptions: (1) an upper bound for gradients; (2) the bounded gradient variance among workers. ) NO rate for convex problems and a linear convergence rate for strongly convex problems benefiting from eliminating the variance among workers. The D 2 (Tang et al., 2018) algorithm further applies the variance reduction on non-convex stochastic decentralized optimization problems and removes the impact of the gradient variance among workers on the convergence rate.

To eliminate the gradient variance among workers and accelerate the training, we incorporate the variance reduction technique into Local SGD, and hence reduce the extra assumptions in the theoretical analysis. For a better comparison with related algorithms in terms of communication complexity and assumptions, we summarize the results in Table 1 . It presents that our algorithm achieves better communication complexity compared with the previous algorithms for the non-identical case and does not need extra assumptions.

3. PRELIMINARY:



3.1. PROBLEM DEFINITION:

We focus on data-parallel distributed training, where N workers collaboratively train a machine learning model, and each worker may have its data with different distributions, which is the nonidentical case. We use D i to denote the local data distribution in the i-th worker. Specifically, we consider the following finite-sum optimization:

EQUATION

where

f i (x) := E ξi∼Di [f i (x, ξ i )]

is the local loss function of the i-th worker.

3.2. NOTATIONS:

First of all, we summarize the key notations of this paper as follows.

• • denotes the 2 norm of a vector.

• f * is the optimal value of equation ( 58).

• E denotes that the expectation is taken with respect to all random indexes sampled to calculate stochastic gradients in all iterations.

• x t i denotes the local model of the i-th worker at the t-th iteration. • xt denotes the average of local models over all N workers, and that is

xt = 1 N N i=1 x t i . • ∇f i (x t i , ξ t i

) is a stochastic gradient of the i-th worker at the t-th iteration. • t represents the iteration of the last communication, and that is t = t k k. • t represents the iteration of the penultimate communication, and that is t = ( t k -1)k.

3.3. ASSUMPTIONS:

Throughout this paper, we make the following assumptions, which are commonly used in the theoretical analysis of distributed algorithms (Stich, 2019; Yu et al., 2019a; Shen et al., 2019) .

Assumption 1

(1) Lipschitz gradient: All local functions f i 's have L-Lipschitz gradients

EQUATION

(2) Bounded variance within each worker: There exists a constant σ such that

EQUATION

(3) Dependence of random variables: ξ t i 's are independent random variables, where

t ∈ {0, 1, • • • , T -1} and i ∈ {1, 2, • • • , N }.

Previous studies based on Local SGD assume that the gradient variance among workers is bounded, or even depend on a stronger assumption, e.g., an upper bound for gradients or identical data distribution on workers, while we do not require these assumptions.

4. ALGORITHM:

In this section, we first introduce the proposed algorithm and then give an intuitive explanation.

4.1. VARIANCE REDUCED LOCAL SGD:

We propose VRL-SGD, a variant of Local SGD. VRL-SGD allows locally updating in each worker to reduce the communication cost. But there are a few more steps in VRL-SGD to eliminate the gradient variance among workers. And in VRL-SGD, a worker: 1. Communicates with other workers to get the average of all local models xt = 1 N N i=1 x t i . 2. Calculates ∆ t i , which denotes the average deviation of gradient between the local gradients and the global gradients in the previous period. And it is defined as

EQUATION

where k is the communication period and γ is the learning rate. 3. Updates local model k times with a stochastic approximation gradient v t i in the form of

EQUATION

The essential part of equation ( 5) is the gradient approximation v t i , which is formed by

EQUATION

The complete procedure of VRL-SGD is summarized in Algorithm 1. VRL-SGD allows each worker to maintain its local model x t i and gets the average of all local models every k steps. Note that VRL-SGD with k = 1 is equivalent to S-SGD. While VRL-SGD with k > 1 reduces the number of communication rounds by k times compared with S-SGD. And VRL-SGD is equivalent to Local SGD if we set ∆ i be 0 in line 5 of Algorithm 1 all the time.

To achieve a linear iteration speedup, Local SGD requires that T is more than O(N 3 k 4 ). In other words, the communication period k in Local SGD is bounded by O(T ) can be attained in the identical case in the previous studies (Shen et al., 2019; Yu et al., 2019a) . Nevertheless, the proposed algorithm can attain the communication period bound O(T 1 2 /N 3 2 ) in both the identical case and the non-identical case. for τ = t to t + k -1 do 8:

Algorithm 1 Variance Reduced Local SGD (VRL-SGD) 1: Input: Initialize x 0 i = x0 ∈ R d , ∆ 0 i = 0 ∈ R d ,

Calculate a stochastic gradient ∇f i (x τ i , ξ τ i ).

9:

v i τ = ∇f i (x τ i , ξ τ i ) -∆ t i .

10:

Each worker updates its local model:

x τ +1 i = x τ i -γv τ i .

11:

end for 12: t = t + k. 13: end while One might wonder why VRL-SGD can improve the convergence rate of Local SGD. VRL-SGD uses an inexact variance reduction technique to reduce the variance among workers. To better understand the intuition of VRL-SGD, let us see the update of ∆ i in equation (4). By summing up all ∆ i from 0 to t and using the fact that ∆ 0 i = 0, we have

EQUATION

By summing up the above equality over i = 1, • • • , N , we obtain

N i=1 ∆ t i = 1 kγ N i=1 t k s=0 xks -x ks i = 1 kγ   N t k s=0 xks - N i=1 t k s=0 x ks i   = 0.

It shows that the expectation of ∆ t i over i is zero, thus we can obtain the new update form with respect to xt .

xt = xt-1 -γ 1 N N i=1 v t-1 i = xt-1 -γ 1 N N i=1 ∇fi(x t i , ξ t i ) -∆ t i = xt-1 -γ 1 N N i=1 ∇fi(x t i , ξ t i ). (8)

It can be noticed that the update of xt in equation ( 8) is in the form of the generalized stochastic gradient descent. In addition, we can obtain a new representation of ∆ t i as below:

EQUATION

Substituting equation ( 9) into equation ( 6), we have

EQUATION

)

The representation of v t i in equation ( 10) can be regarded as the form of the generalized variance reduction, which is similar to SVRG (Johnson & Zhang, 2013) and SAGA (Defazio et al., 2014) .

To observe that the variance among workers is reduced, we assume that the gradient variance within each worker is zero, which means that we calculate ∇f i (x t i ) in line 8 of Algorithm 1. When all local model x t i , x τ i and the average model xt converge to the local minimum x * , it holds that

EQUATION

Therefore, v t i can converge to zero when the variance within each worker is zero, which helps VRL-SGD converge faster. On the other hand, the gradient ∇f i (x t i , ξ t i ) in Local SGD cannot converge to zero, which prevents the local model x τ i from converging to the local minimum x * , so it is hard to converge for Local SGD. In summary, that is why VRL-SGD performs better than Local SGD for the non-identical case, where the gradient variance among workers is not zero.

5. THEORETICAL ANALYSIS:

In this section, we provide a theoretical analysis of VRL-SGD. We bound the expected squared gradient norm of the average model, which is the commonly used metric to prove the convergence rate for non-convex problems (Ghadimi & Lan, 2013; Tang et al., 2018; Yu et al., 2019a) .

Theorem 5.1 Under Assumption 1, if the learning rate satisfies γ ≤ 1 2L and 72k 2 γ 2 L 2 ≤ 1, we have the following convergence result for VRL-SGD in Algorithm 1:

1 T T -1 t=0 E ∇f ( xt ) 2 ≤ 3(f ( x0 ) -f * ) T γ + 3γLσ 2 2N + 56kγ 2 σ 2 L 2 + 12γ 2 L 2 C T ,

where C is defined as

EQUATION

)

The proof of Theorem 5.1 is given in Appendix C. Note that C will be 0 if k = 1 according to equation ( 12). It is consistent with the fact that VRL-SGD when k = 1 is equivalent to S-SGD, where the convergence of S-SGD is not related to the variance among workers.

By setting a suitable learning rate γ, we have the following corollary.

Corollary 5.2 Under Assumption 1, when the learning rate is set as

γ = √ N σ √ T , the communication period is set as k = O(T 1 2 /N 3 2 ) and the total number of iterations satisfies T ≥ 72N 3 L 2 k 2 σ 2

, we have the following convergence result for Algorithm 1:

1 T T -1 t=0 E ∇f ( xt ) ≤ 3σ(f ( x0 ) -f * + 3L) √ N T + 12N C σ 2 T 2 ,

where C is defined in Theorem 5.1.

The detailed proof of Corollary 5.2 is given in Appendix D.

Remark 5.3 Warm-up. We can set the first communication period k to 1 in VRL-SGD, which is VRL-SGD with a warm-up (VRL-SGD-W), then the variable C in Theorem 5.1 and Corollary 5.2 will be 0. Essentially, this is equivalent to conduct one S-SGD update and initialize

∆ i = ∇f i ( x0 , ξ 0 i ) -1 N N j=1 ∇f j ( x0 , ξ 0 j ).

Therefore, the convergence result is not related to the extent of non-iid. We conduct additional experiments to verify this conclusion in Appendix E.

Remark 5.4 Consistent with D 2 . In D 2 (Tang et al., 2018) , the convergence rate is O(

1 √ N T + ζ 2 0 T +σ 2 T 2 ), where ζ 2 0 represents the extent of non-iid in the first iteration. While the convergence rate in VRL-SGD is O( 1 √ N T + C σ 2 T 2 )

, where C is similar to ζ 2 0 . However, we can reduce the dependence on C by a warm-up, which leads to a tighter convergence rate.

Remark 5.5 Linear Speedup. For non-convex optimization, if there are N workers training a model collaboratively, according to Corollary 5.2, VRL-SGD converges at the rate O(1/ √ N T ), which is consistent with S-SGD and Local SGD. To achieve -optimal solutuioin, O( 1N 2 ) iterations are needed. Thus, VRL-SGD has a linear iteration speedup with respect to the number of workers. 

6. EXPERIMENTS:



6.1. EXPERIMENTAL SETTINGS:

Experimental Environment We implement algorithms with Pytorch 1.1 (Paszke et al., 2017) . And we use a machine with 8 Nvidia Geforce GTX 1080Ti GPUs, 2 Xeon(R) E5-2620 cores and 256 GB RAM Memory. Each GPU is regarded as one worker in experiments.

Baselines We compare the proposed algorithm VRL-SGD with Local SGD (Stich, 2019), EASGD (Zhang et al., 2015) and S-SGD (Ghadimi & Lan, 2013) .

Data Partitioning To validate the effectiveness of VRL-SGD in various scenarios, we consider two cases: the non-identical case and the identical case. In the non-identical case, each worker can only access a subset of data. For example, when 5 workers are used to train a model on 10 classes of data, each worker can only access to two classes of data. In the identical case, we allow each worker to access all data.

Datasets and Models We consider three typical tasks: (1) LeNet (El-Sawy et al., 2016) on MNIST (LeCun, 1998); (2) TextCNN (Kim, 2014) on DBPedia (Lehmann et al., 2015) ; (3) transfer learning on tiny ImageNet1 , which is a subset of the ImageNet dataset (Deng et al., 2009) . When training TextCNN on DBPedia, we retain the first 50 words and use a GloVe (Pennington et al., 2014) pretrained model to extract 50 features for word representation. In transfer learning, we use an Inception V3 (Szegedy et al., 2016) pre-trained model as the feature extractor to extract 2,048 features for each image. Then we train a multilayer perceptron with one fully-connected hidden layer of 1,024 nodes, 200 output nodes, and relu activation. All datasets are summarized in Table 2 . A lot of deep learning models use batch normalization (Ioffe & Szegedy, 2015) , which assumes that the mini-batches are sampled from the same distribution. Applying batch normalization directly to the non-identical case may lead to some other issues, which is beyond the scope of this paper.

Hyper-parameters For the above three different tasks, we set the weight decay to be 10 -4 . And we initialize model weights by performing 2 epoch SGD iterations in all experiments. Other detailed hyper-parameters can be found in Table 2 . ). However, benefiting from eliminating the dependency on the gradient variance among workers, VRL-SGD can attain a better communication period bound O(T 1 2 /N 3 2 ) than Local SGD as shown in Corollary 5.2. Therefore, under the same communication period, VRL-SGD can achieve a linear iteration speedup and converges much faster than Local SGD. To maintain the same convergence rate, Local SGD needs to set a smaller communication period, which will result in higher communication cost. EASGD converges the worst under the same communication period in the non-identical case.

There are more experimental results to analyze the influence of parameter k in Appendix F.

6.3. IDENTICAL CASE:

In addition to the above extreme case, we also validate the effectiveness of VRL-SGD in the identical case. As shown in Figure 2 , all algorithms have a similar convergence rate. VRL-SGD, EASGD and Local SGD converge as fast as S-SGD when workers can observe unbiased stochastic gradients.

7. CONCLUSION & FUTURE WORK:

In this paper, we propose a novel distributed algorithm VRL-SGD for accelerating the training of machine learning models. VRL-SGD incorporates the variance reduction technique into Local SGD to further reduce the communication complexity. We theoretically prove that VRL-SGD can achieve a linear iteration speedup for nonconvex functions with the optimal communication complexity O(T

1 2 N 3 2

) whether each worker accesses identical data or not. Experimental results verify the effectiveness of VRL-SGD, where VRL-SGD is significantly better than traditional Local SGD for the non-identical case and enjoys the same convergence rate as that of Local SGD.

In the future, we will consider the deep learning models with batch normalization layers, which may lead to an unstable convergence in the non-identical case.

A PROOF OF PARTIALLY ACCUMULATED LOCAL GRADIENTS:

In this section, we present Lemma 1 and Lemma 2 to bound the partially accumulated local gradients, which are defined as

v t i = ∇f (x t i , ξ t i ), t < k ∇f (x t i , ξ t i ) + 1 k t -1 τ =t ( 1 N N j=1 ∇f j (x τ j , ξ τ j ) -∇f i (x τ i , ξ τ i )). t ≥ k (13)

Lemma 1 Under Assumption 1, we have the following inequality for t ≥ k

EQUATION

)

Proof. By the definition of v t i in (13), we have

EQUATION

)

where the inequality follows from Cauchy's inequality. We next bound T 1 as

EQUATION

)

Because ξ t i 's are independent at different time and workers, and the variance of stochastic gradient in each worker is bounded by σ 2 , we can bound T 3 , T 4 and T 5 as

EQUATION

EQUATION

EQUATION

Substituting ( 17), ( 18) and ( 19) into ( 16), we have

EQUATION

)

We next bound T 2 as

EQUATION

)

where the first three inequalities follow from Cauchy's inequality, and the fourth inequality follows from the Lipschitz gradient assumption. According to (21), we have

EQUATION

Substituting ( 20), ( 22) into (15), we obtain Lemma 1.

Lemma 2 Under Assumption 1, we have the following inequality for t < k,

EQUATION

)

Proof. By the definition of v t i , t < k in (13), we have

EQUATION

)

where the second inequalities can be obtained by using (17) again. Rerrangeing the inequality, we obtain Lemma 2.

B PROOF OF LEMMA 3:

In this section, we introduce Lemma 3, which bounds the difference between the local model x t i and the average model xt .

Lemma 3 Under Lemma 1 and Lemma 2 , when the learning rate γ and the communication period k satisfy that 72γ 2 k 2 L 2 ≤ 1, we have the following inequality

EQUATION

)

where

EQUATION

)

Proof. According to the updating scheme in Algorithms 1, x t i can be represented as

EQUATION

On the other hand, by the definition of xt , we can represent it as

xt = xt - γ N N i=1 t-1 τ =t v τ i (28)

Substituting ( 27) and ( 28) into the left hand side of ( 25) , we have

EQUATION

)

According to the result in Lemma 1 and Lemma 2, for t ≥ k, we have

EQUATION

)

and for t < k, we have

1 N N i=1 E xt -x t i 2 ≤ 4kγ 2 L 2 N N i=1 t-1 τ =0 E x τ i -xτ 2 + 4kγ 2 t-1 τ =0 ∇f ( xτ ) 2 +4kγ 2 σ 2 + 4γ 2 N N i=1 t-1 τ =t (∇fi( xτ ) -∇f ( xτ )) 2 (31)

Under review as a conference paper at ICLR 2020 Summing up ( 30) and ( 31) from t = 0 to T -1, we obtain

EQUATION

where the second and the third inequalities can be obtained by using a simple counting argument.

Denote C = 1 N k-1 t=0 N i=1 t-1 τ =0 (∇f i ( xτ ) -∇f ( xτ )) 2 .

Rerrangeing the inequality, we obtain

EQUATION

Dividing 1 -36k 2 γ 2 L 2 on both sides completes the proof.

C PROOF OF THEOREM 5.1

In this section, we give the proof of Theorem 5.1.

Theorem 5.1 Under Assumption 1, if the learning rate satisfies γ ≤ 1 2L and 72k 2 γ 2 L 2 ≤ 1, we have the following convergence result for Algorithm 1:

EQUATION

Proof.

EQUATION

)

By applying expectation with respect to all the random variables at step t and conditional on the past (denote by E t|• ), we have

EQUATION

)

Note that

EQUATION

where the last equality holds because

E t|• 1 N N i=1 ∇f i (x t i , ξ t i ) -1 N N i=1 ∇f i (x t i ) = 0

, and

EQUATION

where the second equality holds because the random variables on different workers are independent. Substituting (37) into (36) and applying expectation with respect to all the random variables, we obtain

EQUATION

)

We then bound the difference of ∇f ( xt ) and 1

EQUATION

)

where the two inequalities follow from Cauchy's inequality and Lipschitz gradient assumption, respectively. Substituting ( 40) into (39) yields

EQUATION

Rearranging the inequality and summing up both sides from t = 0 to T -1, we have

EQUATION

)

Substituting Lemma 3 into (42) and combing 72k 2 γ 2 L 2 ≤ 1, we obtain

EQUATION

Next, we bound T 6 .

EQUATION

Since ξ t i 's are independent, we have

EQUATION

)

Substituting ( 45) into (44), we have

T6 = γ 2 N 2 T -1 t=k t -1 τ =t t-1 s=τ N i=1 E ∇fi(x s i , ξ s i ) -∇fi(x s i ) 2 + γ 2 N 2 T -1 t=k t -1 τ =t E t-1 s=τ N i=1 ∇fi(x s i ) 2 ≤ 2k 2 γ 2 σ 2 T N + T -1 t=k t -1 τ =t E γ N t-1 s=τ N i=1 ∇fi(x s i )

where the inequality holds since t -τ ≤ k ≤ t -t ≤ 2k. Substituting ( 46) into (43), we obtain

EQUATION

)

Rearranging this inequality and dividing both sides by T γ 2 , we get

EQUATION

Then we prove T 8 ≤ 0. If the learnign rate γ satisfies γ ≤ 1 2L , then we have

EQUATION

)

Since 72k 2 γ 2 L 2 ≤ 1, then we have 384k 4 γ 4 L 4 ≤ 1, and thus T 8 ≤ 0. Rearranging (48) and dividing both sides by 1 -24k 2 γ 2 L 2 , we get

EQUATION

where the inequalities hold because k 2 γ 2 L 2 ≤ 1 72 and

1 1-24k 2 γ 2 L 2 ≤ 3 2 .

D PROOF OF COROLLARY 5.2

In this section, we give the proof of Corollary 5.2.

Corollary 5.2 Under Assumption 1, when the learning rate is set as γ = √ N σ √ T and the total number satisfies T ≥ 64N 3 L 2 k 2 σ 2 , we have the following convergence result for Algorithm 1:

1 T T -1 t=0 E ∇f ( xt ) ≤ 3σ(f ( x0 ) -f * + 3L) √ N T + 12N C σ 2 T 2 . (51) Proof. Since γ = √ N σ √ T , T ≥ 72N 3 L 2 k 2 σ 2 ≥ 72N k 2 L 2 σ 2

, we have 72γ 2 k 2 L 2 ≤ 1 and γ ≤ 1 2L . Then we can have the result in (34) and get

EQUATION

) Combing γ = √ N σ √ T , k 2 γ 2 L 2 ≤ 1 72 and T ≥ 72N 3 L 2 k 2 σ 2 ≥ 64N 3 L 2 k 2 σ 2

, we have

EQUATION

EQUATION

EQUATION

EQUATION

)

We can get the final result

EQUATION

which completes the proof.

E MORE EXPERIMENTS:

In this section, we evaluate the effectiveness of our algorithm on different variance among workers. Specifically, we consider the following finite-sum optimization

EQUATION

where f 1 (x) := (x + 2b) 2 and f 2 (x) := 2(x -b) 2 respectively denote the local loss function of the first and the second worker.

We can set a large variance among workers by adjusting b. Therefore, we can compare the convergence rate of algorithms in different variance, where the variance among workers is large with a large b. VRL-SGD-W denotes VRL-SGD with a warm-up, where the first communication period is set to 1. Figure 3 shows the gap with regard to iteration on different k and b. We can see that Local SGD converges slowly compared with VRL-SGD-W and VRL-SGD when the communication period k is relatively large. And VRL-SGD without warm-up is related to b while VRL-SGD-W is not sensitive to b. Figure 4 shows that the variance of v t i in VRL-SGD and VRL-SGD-W converges to 0, while the variance of ∇f i (x) in Local SGD is a constant related to b. The experimental results verify our conclusion that VRL-SGD has a better convergence rate compared with Local SGD in the non-identical case, and VRL-SGD with a warm-up is more robustness to the variance among workers. 

:

The tiny ImageNet dataset can be downloaded from https://tiny-imagenet.herokuapp.com.

,(46)

Figures and Tables:

which reduces the communication complexity to O(N

Remark 5.6 Communication Complexity. By Corollary 5.2, to achieve the convergence rate O(1/ √ N T ), the number of iterations T needs to satisfy T ≥ O(N 3 k 2 ), which requires the communication period k ≤ OVRL-SGD can reduce communication complexity by a factor k. However, for the non-identical case, previous algorithms based on Local SGD can only reduce communication complexity by a factor O7 Mini-batch VRL-SGD. Although we consider only a single stochastic gradient in each worker so far, VRL-SGD can calculate mini-batch gradients with size b in line 8 of Algorithm 1. It reduces the variance σ 2 within each worker by a factor b, thus VRL-SGD can converge at the rate O(1/ √ bN T ) by setting the learning rate γ = √ bN σ √ T .

Figure 3: Logarithm of distance to the global minimum for different b and communication period k.

Figure 4: Logarithm of variance among workers for different b and communication period k.

∀i and t = 0. Set learning rate γ > 0 and communication period k > 0.

Table content: <table><tr><td colspan="2">2: while t &lt; T do</td><td/></tr><tr><td>3:</td><td>Worker W i does:</td><td/></tr><tr><td>4:</td><td>Communicate with other workers to get the average of all local models: xt = 1 N</td><td>N i=1 x t i .</td></tr><tr><td>5:</td><td>∆ t i = ∆ t i + 1 kγ ( xt -x t i ) .</td><td/></tr><tr><td>6:</td><td>Update local model x t i = xt .</td><td/></tr></table>

Parameters used in experiments and a summary of datasets. N denotes the number of workers, b denotes batch size on each worker, γ is the learning rate, k is the communication period, n represents the number of data samples and m represents the number of data categories.Metrics In this paper, we mainly focus on the convergence rate of different algorithms. Local SGD has a more superior training speed performance than S-SGD, which has been empirically observed in various machine learning tasks(Povey et al., 2014;Su & Chen, 2015). Besides, VRL-SGD has only a minor change over Local SGD. So VRL-SGD and Local SGD have the same training time in one epoch and both of them have a faster training speed compared with S-SGD. VRL-SGD and EASGD would have the same communication complexity under the same period k. Therefore, we compare only the convergence rate (the training loss with regard to epochs) of different algorithms.Figure 2: Epoch loss for the identical case. All of the algorithms have a similar convergence rate.6.2 NON-IDENTICAL CASEThis paper seeks to address the problem of poor convergence for Local SGD when the variance among workers is high. Therefore, we focus on comparing the convergence rate of all algorithms in the non-identical case, where the data variance among workers is maximized. communication period bound compared to Local SGD. When the variance among workers is not zero, Local SGD requires that T is greater than O(N 3 k 4 ) to achieve a linear iteration speedup. Thus Local SGD losses this property if k is larger than O(T

Table content: <table><tr><td>Model</td><td>N</td><td>b</td><td>γ</td><td>k</td><td>Dataset</td><td>n</td><td>m</td></tr><tr><td>LeNet</td><td colspan="4">8 32 0.005 20</td><td>MNIST</td><td>60,000</td><td>10</td></tr><tr><td>TextCNN</td><td colspan="4">8 64 0.01 50</td><td>DBPedia</td><td colspan="2">560,000 14</td></tr><tr><td colspan="8">Transfer Learning 8 32 0.025 20 Tiny ImageNet 100,000 200</td></tr></table>

Peer review (iclr2020):
In the paper, the authors propose a variance reduced local SGD and prove its convergence rate. In the experiments, they show that the proposed method converges faster than local SGD. The following are my concerns: 1) I am concerned about the convergence result, it shows that the convergence of the proposed method has nothing to do with the extent of non-iid. However, it is not correct intuitively. It is easy to imagine that non-iid data will converge slower than iid data. 2) In Corollary 5.2, the convergence result is not related to k. It is false to me. 3) It is not clear in algorithm 1 how the delta^{t**} is updated. 4) The assumption in equation (11) *When all local model x^t, x	au and the average model hat x converge to the local minimum x?* is not correct when data is non-iid distributed. Suppose x^t and hat x is x^*, and Delta^{t**} = 0. Because data is non-iid, the solution of the local problem is not equal to the global problem, therefore, x^t will go away from x^*. 5) In the experiment, the setting of k should affect the experiment. However, authors don*t analyze this parameter.