Variance Reduced Local SGD with Lower Communication Complexity
Authors: Xianfeng Liang
Shuheng Shen
Jingchang Liu
Zhen Pan
Yifei Cheng
Enhong Chen
Venue:  (2020)
Keywords: variance reduction
local SGD
distributed optimization

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^{\frac{3}{4}} N^{\frac{3}{4}})$ communications to maintain its \emph{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 \emph{linear iteration speedup} with a lower communication complexity $O(T^{\frac{1}{2}} N^{\frac{3}{2}})$ 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
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 gra- dient descent (SGD) and its variants have been widely adopted, which apply mul- tiple 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 workers is non-identical, Local SGD requires O N commu- nications 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 lower communication complexity O(T N even if workers ac- cess non-identical datasets. We conduct experiments on three machine learning tasks, and the experimental results demonstrate that VRL-SGD performs impres- sively better than Local SGD when the data among workers are quite diverse.
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 mul- tiple workers to cooperatively optimize the model.
For large-scale machine learning problems, stochastic gradient descent (SGD) is fundamental tool. can be easily parallelized by collecting stochastic gradient from different workers and hence 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 non- convex 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 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 (Stch 2019) is 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 follow- ing 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 per- formance. 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 algo- rithms would encounter 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 optimiza- tion algorithm to further reduce the communication complexity. Benefiting from additional vari-

---

Under review as a conference paper at ICLR 2020
ance reduction component, VRL-SGD eliminates the extra assumption about bounded gradient vari- ance 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 to O N in VRL-SGID for the non-identical case, which is crucial for achieving 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 state-of-the-an communication complexity. Specifically, the communication complexity is reduced from N²) to OCT' N 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 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 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 conver- gence 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-batee SGD and thcoretically proved to achieve a linear iteration speedup with respect to the number of work- ers (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 al. 20177] Aji & Heafield 2017: Bernstein et al. 2019 Lin et al. 2018b; Karimireddy al.) [019 Tang et al. 2019). which use inexact approximations or partial data to represent the gradients, and methods Stich][[099 Yu et al. 2019b) based on the lower communication frequency.
Among them, Local SGD (Stich 2019). a representative method to lower the communication fre- quency, has been widely used in the training of large-scale machine learning models, and its superior performance is verified in several tasks (Povey et al. [0144] Su & Chen 2015 Lin et al.) 201 8a). In Local SGD, each worker conducts SGD updates locally and averages model with others period- ically. Previous studies have proven that Local SGD can attain a linear iteration speedup for both strongly convex (Stich) 2019) and non-convex (Yu et al. 2019b) problems. To fully utilize hardware resources, a variant of Local SGD, called CoCoD-SGD (hhnn et al. 2019). is proposed with the de- coupling of computation and communication. Furthermore, Yu et al. (2019a) provide a clear linear speedup analysis for Local SGD with momentum. However, most of the above algorithms assume that the gradient variance among workers is bounded, and some of them even depend on a stronger assumption, e.g., the data distribution on workers is identical. Dependence on these assumptions may lead to slow convergence rate for the non-identical case, which limits the further reduction of communication frequency and avoids better time speedup. [Haddadpour et al. (2019) verify that the use of redundant data can lead to lower communication complexity and hence faster conver- gence. The redundant data can help reduce the gradient variance among workers, thus it avoids the slow convergence rate. Nevertheless, this method may be constrained in some cases. For instance, it could not be widely applied federated learning (Konečný et al. 2016) as data cannot exchanged between workers for prreecc.preeerving..
Although there are many studies proposed to reduce the variance in SGD, e.g., SVRG (Johnson & Zhang 2013), SAGA (Defazio et al., 2014), and SARAH (Nguyen et al.) 2017). they could not directly deal with the gradient variance among workers in distributed optimization. In recent years, several studies (Shi et al. 2015 Mokhtari & Ribeiro 2016; Tang et al. 2018) have proposed to eliminate the gradient variance among workers in the decentralized setting. Among them, (Shi et al. (215)) propose a novel decentralized algorithm, EXTRA, which provides ergodic convergence
2

---

Under review as a conference paper at ICLR 2020
Table 1: Comparisons of the communication complexity for different algorithms. The second col- umn 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.
REFERENCE
IDENTICAL DATA
NON-IDENTICAL DATA
EXTRA ASSUMPTIONS
GHADIMI & LAN (2033)
T
T O(NTT) ONN O(N
NO
O(N O(NåT O(N
YU ET AL. (2019B)
(1)
SHEN 2019
(2)
THIS PAPER
NO
rate for convex problems and a linear convergence rate for strongly convex problems benefiting from eliminating the variance among workers. The D (Tang et al. 2018) algorithm further applies the variance reduction on non-convex stochastic decentralized optimization problems and removes the impact 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 theoret- ical analysis. For better comparison with related algorithms in terms of communication complexity and assumptions, we summarize the results in Table presents that our algorithm achieves better communication complexity compared with the previous algorithms for the non-identical case and does not need extra assumptions.
PRELIMINARY
3.1 PROBLEM DEFINITION
We focus on data tata-parrllll distributed training, where N workers collaboratively train machine learning model, and each worker may have data with different distributions, which is the non- identical case. We use D; to denote the local data distribution in the i-th worker. Specifically, we consider the following finite-sum optimization:
1
min f(x) mER
Σ f(().
where f((z) := Eg (f(x, 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 & norm of vector.
is the optimal value of equation 58
E denotes that the expectation is taken with respect to all random indexes sampled cal- culate stochastic gradients in iterations.
ot denotes the local model of the i-th worker at the 1-th iteration.
denotes the average local models over all N workers, and that is
N Σ x.
1
fa <f) is stochastic gradient the i-th worker at the t-th iteration.
t' represents the iteration of the last communication, and that is t' = [
k" represents the iteration of the penultimate communication, and that is l" (Lt) 1)k.

---

Under review as a conference paper at ICLR 2020
3.3 ASSUMPTIONS
Throughout this paper, we make the following assumptions. which are commonly used in the theo-
retical analysis of distributed algorithms (Stich) 2019 Yu et al. 2019a; Shen al. 2019).
Assumption
(1) Lipschitz gradient: All local functions fi have L-Lipschitz gradients
[Vf:(x)) V)((y))l & L|a= yll Vi, Vax y Rd..
(2)
(2) Bounded variance within each worker: There exists constant such that
Bg-D;IlV/: V[(())]1 o²; Va E IR. Vi.
(3)
(3) Dependence of random variables: G are independent random variables, where t E [0,1, - and E (1,
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 distri- bution on workers, while we do not require these assumptions.
ALGORITHM
In this section, we first introduce the proposed algorithm and then give 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 reduce the communication cost. But there few more steps in VRL-SGD to eliminate the gradient variance among workers. And in VRL-SGD, a worker:
1. Communicates with other workers get the average of all local models ø' \/ Σ z!-
2. Calculates A which denotes the average deviation of gradient between the local gradients and the global gradients in the previous period. And it defined as
A =
(
m
(4)
ky
where & is the communication period and is the learning rate.
3. Updates local model k times with a stochastic approximation gradient of in the form of
x ++ = x - 7u/.
(5)
The essential part of equation
5 the gradient approximation of. which formed by
of Vi( - A
(6)
The complete procedure of VRL-SGD summarized in Algorithm VRL-SGD allows each worker to maintain its local model æ. and gets the average of all local models every & steps. Note is equivalent S-SGD. While VRL-SGD with reduces the num-
that VRL-SGD with ber of communication rounds by l times compared with S-SGD. And VRL-SGD is equivalent to line Algorithm [ all the time.
Local SGD if we set A,
To achieve linear iteration speedup, Local SGD requires that T is more than O(N3 In other words, the communication period ie in Local SGD is bounded by O(T /N which Notice that better communication period 8 can be attained in the identical case in the previous studies (Shen et al. 2019 Yu et al. 2019a). Nevertheless, the proposed algorithm attain the communication period bound O N in both the identical case and the non-identical case.
duces the communication complexity to O(N bound O(T3 /N
4

---

5: A = A + by (ø' x Under review as a conference paper at ICLR 2020
Algorithm 1 Variance Reduced Local SGD (VRL-SGD)
1: Input: Initialize 2F a E IR A E IRd, Vi and / 0. Set learning rate y communication period & > 0.
and
2: while << 7 do
3: Worker W; does:
4: Communicate with other workers to get the average all local models: a' N Σn o
6: Update local model क; = a'. for 1 to t + do
7:
8:
Calculate a stochastic gradient V.
9:
u," = V ff(
A
Each worker updates its local model:
x x. YOT.
11:
end for
t= -++
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 see the update of A, in equation (4). By summing up all A, from 0 to l' and using the fact that A 0, we have
A
a=0
By summing up the above equality over
1, ,,.. N, we obtain
x
w
= 0.
ky
shows that the expectation of A over i is zero, thus we can obtain the new update form with respect to &
N Σ
N
N
(Vi(a)i))) af) -'- -7 Σ VM < Σ
(8)
It can be noticed that the update of a' in equation is in the form of the generalized stochastic gradient descent. In addition, we can obtain à new representation of A as below:
A
by
j=1
e'1
11
=
A
1
Σ
Vi(eT ( a:")
Σ
by
f
Σ
v
(9)
N
Substituting equation
into equation we have
f-1 N NE T= j=l
of Vi((ele))
Σ T=t!"
(10)
The representation of of in equation (10p can be regarded as the form of the generalized variance
reduction, which is similar to SVRG JJhnnon & Zhang 2013) and SAGA (Defazio et al. 2014).
5

---

Under review as a conference paper at ICLR 2020
To observe that the variance among workers is reduced. we assume that the gradient variance within each worker zero, which means that we calculate (a in line of Algorithm [ When all local model æ/ of and the average model &' converge to the local minimum Φ", it holds that
K-1 N Σ
of v.f((a)))
V(((
E
v)(a))
NR
1-1 N
Vfi((=))
V
Σ
Σ
(f)("')
Nl.
T=!"
d' 11 N NE
(1I)
Therefore, of can converge zero when the variance within each worker is zero, which helps VRL- SGD converge faster. On the other hand, the gradient (ar < in Local SGD) cannot converge to zero, which prevents the local model xद from converging to the local minimum x", so 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 not zero.
THEORETICAL ANALYSIS
In this section, 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 2019a).
Theorem 5.1 Under Assumption 1 have the following convergence result for VRL-SGD in Algoritium 1:
if the learning satisfies 7 2t and 72k2> <
T-1
3(ʃ(a)) - fr)
3g
12 L2C
FIVS(*>) 1=
56km200
T7
2N
where defined as
ΣΣ Σ
-V(()))-V((3)
(12)
The proof of Theorem 5.1 is given in Appendix C Note that C will be 0 if k according to equation (12). consistent with the fact that VRL-SGD when = is equivalent to S-SGD, where the convergence of S S-SGD is not related to the variance among workers.
By setting a suitable learning rate y, we have the following corollary.
Corollary 5.2 Under Assumption 1, when the learning rate is set "
VN oVT the communication
period is set as k O / and the total number of iterations satisfies > the following convergence result for Algorithm 1:
we have
0²
) - +3))
12NC G2T2
Σ
E
VNT
where C is defined in Theorem 5.1
The detailed proof of Corollary 5.2 given Appendix D
Remark 5.3 Warm-up. We can set the first communication period k to I in VRL-SGD, which VRL-SGD with a warm-up (VRL-SGD-W), then the variable C in Theorem 5.1 and Corollary
5.2 will be O. Essentially, this is equivalent to conduct one S-SGD update and initialize A Si(0" -g 1/2 E Vfz(&" e.). Therefore, the convergence result is not related to the extent of non-iid. We conduct additional experiments to verify this conclusion in Appendix B

---

Under review as a conference paper at ICLR 2020
Remark 5.4 Consistent with D In D² (Tang et al. 2018). the convergence rate is O T+04T2 ) where S represents the extent of non-iid in the first iteration. While the convergence rate in VRL-SGD Of O(VNT -áTz), where C is similar to Lo. However, we can reduce the dependence on C' by a warm-up, which leads to tighter convergence rate.
VNT +
Remark 5.5 Linear Speedup. For non-convex optimization, if there are N workers truining model collaboratively, according to Corollary 5.2 VRL-SGD converges at the rate 0(1 (TT), which is consistent with S-SGD and Local SGD. achieve c-optimal solutuioin, O ((se) iterations needed. Thus, VRL-SGD has a linear iteration speedup with respect to the number of workers.
Remark 5.6 Communication Complexity. By Corollary 5.2 to achieve the convergence rate O(T/VNT), the number of iterations T needs to satisfy T 2 O(N3R2) which requires the commu- nication period k I OT )) Consequently, by setting k = O ) VRL-SGD can reduce communication complexity by factor k. However, for the non-identical case, previous algorithms based Local SGD can only reduce communication complexity by factor O /N
Remark 5.7 Mini-batch VRL-SGD. Although we consider only a single stochastic gradient in each worker far. VRL-SGD calculate mini-batch gradients with size b in line & of Algorithu 7 It reduces the variance o² within each worker by a factor b. thus VRL-SGD can converge at the rate O(1/VbNT) by setting the learning rate
VbN ovT
EXPERIMENTS
6.1 EXPERIMENTAL. SETTINGS
Experimental Environment We implement algorithms with Pytorch 1.1 (Paszke et al. 2017). And we use 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 (Zhag et al. 2015) and S-SGD (Ghadimi & Lan 2013).
Stich 2019), EASGD
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) TexICNN (Kim 2014) on DBPedia (Lehmann et al. 2015 ; (3) transfer learning on tiny ImageNet J which is a subset of the ImageNet dataset (Deng et al. 2009). When training retain the first 50 words and trained model to extract 50 features for word representation. In transfer learning. we use an Inception V3 (Szegedy et al., pre-trained model as the feature extractor to extract 2,048 features for each image. Then we train multilayer perceptron with one fully-connected hidden layer of 1,024 nodes, 200 output nodes, and relu activation. All datasets are summarized in Table lot of deep learning models use batch normalization (Ioffe & Szegedy 2015), which assumes that the mini-batche 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.
TextCNN DB Pedia,
GloVe (Pennington et al., 2014) pre-
Hype prrer-pprammters For the above three different tasks, the weight decay to be 10 And we initialize model weights by performing 2 epoch SGD iterations in all experiments. Other detailed hyper-parameters can be found in Table 2
'The tiny ImageNet dataset can he downloaded from httph://ttttytt imggenteeemmmmmme..mmmmmmm www.://m..tttte.eraaapooooo

---

Under review as a conference paper at ICLR 2020
Table 2: Parameters used in experiments and summary of datasets. N denotes the number of workers, b denotes batch size on each worker, 7 is the learning rate, k is the communication period n represents the number of data samples and m represents the number of data categories.
Model
N
b
7
k
Dataset
T
m
LeNet
8
32
0.005
20
MNIST 60,000
10
TextCNN
64
0.01
50
DBPedia
560,000
14
Transfer Learning
8
32
0.025
20
Tiny ImageNet 100,000
200
Metries this paper, we mainly focus on the convergence rate of different algorithms, Local SGD has 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 minor change over Local SGD. So VRL-SGN and Local SGD have the same training time in one epoch and both 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, compare only the convergence rate (the training loss with regard to epochs) different algorithms.
LeNe, MNIST
TexCCNN DBPedia
Transffer
S-SGP
S-50D
5-5GD
BASGE
BASGD
DASGD
SGD
Local SGD
Local SGD
-GD
0.4
0.3
0.5
0.1
0.0
Epoch
Epsch
Epoch
Figure 1: Epoch loss for the non-identical case. VRL-SGD converges fast S-SGD, and Local
SGD, EASGD converge slowly or even cannot converge.
LeNet, MNIST
TexIUNN, DBPedis
Transfer Leaming. Tiny ImageNet
0.6
EASOD
EASOD
EAS00 Locel SCD
VAL-SGD
Loal SGD
0.5
VILL-50D
Local SGD
1.5
VRL 500
1055
0.2
1,o5s
1.0
0.3
0.3
0.2
25
50
75
100
0
25
50
75
100
0
160
200
300
Epoch
Epoch
Opoch
Figure 2: Epoch loss for the identical case. All of the algorithms have similar convergence rate.
6.2 NON-IDENTICAL CASE
This paper seeks to address the problem of poor convergence for Local SGD when the variance among workers is high. Therefore, focus comparing the convergence rate of all algorithms in the non-identical case, where the data variance among workers is maximized.
We choose three classical tasks: image classification, text classification, and transfer learning. Fig- ure [ shows the training loss with regard to epochs on the three tasks. The results are indicative of the strength of VRL-SGD in the non-identical case. Local SGD converges slowly compared with S-SGD when the communication period & is relatively large, while VRL-SGD enjoys the same convergence rate that of S-SGD. This is consistent with theoretical analysis that VRL-SGD has
8

---

Under review as a conference paper at ICLR 2020
better communication period bound compared to Local SGD. When the variance among work- ers is not zero, Local SGD requires that T is greater than k() to achieve a linear iteration speedup. Thus Local SGD losses this property if k is larger than O /Nå). However, benefiting from eliminating the dependency on the gradient variance among workers, VRL-SGD can attain better communication period bound O /N 3) than Local SGD as shown in Corollary 5.2 There- fore, under the same communication period, VRL-SGD can achieve linear iteration speedup and converges much faster than Local SGD. To maintain the same convergence rate, Local SGD needs to set 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 more experimental results to analyze the influence of parameter l in Appendix
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 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 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 linear iteration speedup for nonconvex functions with the optimal communication complexity à N ) whether each worker accesses identical data 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.
REFERENCES
Alham Fikri Aji and Kenneth Heafield. Sparse communication for distributed gradient descent. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pp- 440 445, 2017.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication-effiiinnnn sgd via gradient quantization and encoding. In Advances in Neural Information Processing Systems, pp. 1709-1720, 2017.
Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadenesheli, and Anima Anandkumar. signSGD with majority vote is communication efficient and fault tolerant. In International Conference on Learn- ing Representations, 2019. URL
net/ forum Bid=BBxxi JACY7
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in neural information processing systems, pp. 1646-1654, 2014.
Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, and Lin Xiao. Optimal distributed online prediction using mini-batches. Journal of Machine Learning Research, 13(Jan):165-005 2012.
J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. ImageNet: A Large-Scale Hierarchical Image Database. In CVPRO9, 2009.
Ahmed El-Sawy, El.-Barry Hazem, and Mohamed Loey. Can for handwritten arabic digits recog- nition based on lenet-5. In International Conference on Advanced Intelligent Systems and Infor- matics, pp. 566-575. Springer, 2016.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochas- tic programming. SIAM Journal Optimization, 23(4):2341-2366 2013.

---

Under review as a conference paper at ICLR 2020
Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Trading redundancy for communication: Speeding up distributed sgd for non-convex optimization. In ICML, pp. 2545-2554, 2019.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning, pp. 448 4484456, 2015.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in neural information processing systems, pp. 315-323, 2013.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In ICML, pp. 3252-3261, 2019.
Yoon Kim. Convolutional neural networks for sentence classification. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 1746-1751, 2014.
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:/6100 05492, 2016.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mmist/, 1998.
Jens Lehmann, Robert Isele, Max Jakob, Anja Jentzsch, Dimitris Kontokostas, Pablo N Mendes, Sebastian Hellmann, Mohamed Morsey, Patrick Van Kleef, Sören Auer, et al. Dbpedia-a large- scale, multilingual knowledge base extracted from wikipedia. Semuntic Web, 6(2):167-199 2015.
Tao Lin, Sebastian U Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large use local sgd. arXiv preprint arXiv: 07217, 2018a
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and Bill Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. In International Conference on Learning Representations, 2018b. URL URL /opp://vieeeeeeeeeeeeeeee mtt.:/forrun.ddds:kiii0000
Aryan Mokhtari and Alejandro Ribeiro. Dsa: Decentralized double stochastic averaging gradient algorithm. The Journal of Machine Learning Research, 17(1)2115-2119 2016.
Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: A novel method for machine learning problems using stochastic recursive gradient. In ICML, pp. 2613-2621, 2017.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Jeffrey Pennington, Richard Socher, and Christopher D. Manning. Glove: Global vectors for word representation. In Empirical Methods in Natural Language Processing (EMNLP), pp. 1532-1543, 2014. URL (htp:: www. wcwweb..wb.......... wwwp.ooog/athhoooogo////////////
Daniel Povey, Xiaohui Zhang, and Sanjeev Khudanpur. Parallel training of dnns with natural gradi- ent and parameter averaging. arXiv preprint arXiv:1410.7455, 2014.
Shuheng Shen, Linli Xu, Jingchang Liu, Xianfeng Liang, and Yifei Cheng. Faster distributed deep net training: Computation and communication decoupled stochastic gradient descent. In IJCAI, 2019.
Wei Shi, Qing Ling, Gang Wu, and Wotao Yin. Extra: An exact first-order algorithm for decentral- ized consensus optimization. SIAM Journal on Optimization, 25(2):944-966, 2015.
Sebastian Urban Stich. Local sgd converges fast and communicates little. In ICLR 2019 ICLR 2019 International Conference on Learning Representations, number CONF, 2019.
Hang Su and Haoyu Chen. Experiments on parallel training of deep neural network using model averaging. arXiv preprint 1rx 2015.
10

---

Under review as a conference paper at ICLR 2020
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zbigniew Wojna. Rethink- ing the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2818-282222 2016.
Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu. D2: Decentralized training decentralized data. In ICML, pp. 4855-4886 2018.
Hanlin Tang, Chen Yu, Xiangru Lian, Tong Zhang, and Ji Liu. Doublesqueeze: Parallel stochastic gradient descent with double-pass pasb crror-compensated compression. In ICML. pp. 6155-6165, 2019.
Jianyu Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of communication-effiieee sgd algorithms. arXiv preprint arXiv: /tti::8800.0000 1708,07576, 2018.
Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis communication efficient mo- mentum sgd for distributed non-convex optimization. In ICML, pp. 7184-7193, 2019a.
Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 5693-5700, 2019b.
Sixin Zhang, Anna Choromanska, and Yann LeCun. Deep learning with elastic averag- ing SGD. In Advances in Neural Information Processing Systems 28: Annual Con- ference on Neural Information Processing Systems 2015, December 7-12, 2015, Mon- treal, Quebec, Canada, pp. 685-693, 2015. URL http://papers. www.eer...ii....mm wip.. cctps.cc/ppper/
Fan Zhou and Guojing Cong. On the convergence properties of a k-step averaging stochastic gradient descent algorithm for nonconvex optimization. In Proceedings of the 27th International Joint
Conference on Artificial Intelligence, pp. 3219-3227. AAAI Press, 2018.

---

Under review as a conference paper at ICLR 2020
A PROOF OF PARTIALLY ACCUMULATED LOCAL GRADIENTS
In this section, we present Lemma] T and Lemma ents, which are defined
to bound the partially accumulated local gradi-
v ff + of
t< k
v((a)) + EF En-
( Vi - (
1 12 k
(13)
Lemma 1 Under Assumption 7
we have the following inequality for t 2 k
121. 2
B1
0f 1
S
Σ
Σ Ell=i - *'11" + Σ Σ Biia" - xt 11 + 2h Σ E1i²" xx 11²)
N
1-1
+12k
VV I11 18k0 (14)
Proof. By the definition of of in
13 we have
N
N
E
Vi
Via .5) V.ii( ,E(')
N
7'=e"
j=1
Viila [(((TT +
Σ
[īل , vly(aa)))
Ts
+Vi((=t') - (((=t' ( [v[((a))
N ( - vi(aEt
p'=""
N
Σ
V(((=(])) -
+ 1
[ .55) - v
Σ
N
r'=e"
N
Vl((oe ) vi(ao .55
ΣΣ
vf((xt)
+
Σ
N Σ ( -
-V
T2
(15)
where the inequality follows from Cauchy's 's inequality. We next bound Ti as
Ti
3
Σ
v fi(a ( - (x+)))
-3 (t -t))
f) Σ
T3s
+3E
(t- t')
#' 1
Vz -
(16)
k
N
-'=
T5
12

---

Under review as a conference paper at ICLR 2020
Because s are independent different time and workers, and the variance of stochastic gradient in each worker is bounded by o², we can bound T3, T2 and T3 as
T3 Σ EIVV)((TTT V/(=x))
+2
Σ (VVl.="..')) V.(()) (((m,, v((()))
"Snemntt1
Σ E -
$ ())
S ko"
(17)
(1 2)-
- -
T4
+2
E
B (V -
(t t2
Σ
E
1'1""
< ko?
(18)
Ta = (t-²')² E
Σ
V (1s (VV-(((())))
N2K²
r'aa"
(t- t)
(Vi(aj's .55 {,,(4T)))
N2K2
N (39 ))( Σ
+2
Σ
Σ (vS
(1= d-11
N
Σ
E
Σ
-vv(((()))))
N2R2
7'"
(t= 1-1
E
(z 55 "
N
7'20"
+2
Σ
(Vin
(2) 4) V1h (2%)) Thy ( -V/ v
(1-1)² f-1
Σ
Σ R
v
N
P/=!" j=1
ko² N
(19)
Substituting 17 (18) and 19
into (16). have
3(Ts + T. TT) 9ko2
(20)
13

---

Under review as a conference paper at ICLR 2020
We next bound T2 as
17
T2 =
E
V.((a)) + 1
Σ
1
K
.N
-'=!"
1-1
E
V/((])) 4/(17)+ + V.(((T)
k Σ Vii(a")
-'=1"
(V - ) 1
NE Σ
(V)((a))) ) 1 -v)(a)))
(vf(*') ) -V((7) + +V((*)
1 1-1
6
R
Σ - -
+
(((T)
k Σ V
+B
(V.((*))- - -VA(('))
- E
Σ Σ
-
k
Nk
t'
+ Σ f((*)) > IT)
Σ (v)(T))- -V
+E
+'='"
S 6(1 ())
BIV\A(a)) VI(07) + Vi((6))
K Σ v
-'=
+B
Σ (V/((3')) - - -V/
+
Σ
Víy(ay') - --
Nk
r'=!"
+E
- )
+EIIVS(")) !1(
S 6(1 - 1) Σ
-[VA((a)- - V/((T) + 2 Σ
E V -
k -'
Σ E (((aa) })(aa)/| I|'
+ Nk Σ
</s( J|" *
z'=!"
y=1
s 6(t 1 Σ
E | 1
R
El + "
,'=!"
1'=0"
Σ
1-11 n
R | 4 11)
+ 6(t {1) r=!
E [| 2
Nk
<= j=1
< 6L
t: Σ
E B| - x2I Σ Σ E x -
+
Σ
B -2;"
v=v²
T=ml
x'=0"
1-1 N
10 - x²(1²)
+ N
Σ Σ
6k Σ ||
(21)
j=1
14

---

Under review as a conference paper at ICLR 2020
where the first three inequalities follow from Cauchy's inequality, and the fourth inequality follows from the Lipschitz gradient assumption. According (2I). have
12L
N
||
Σ T=E r'=!!
E
-x
2k
Σ
B
x²"
xx
N
r'=e"
+12k
E
(22)
Substituting
20
22
into
we obtain Lemma
Lemma Under Assumption
we have the following inequality for 1. < k
N
4
c
Σ
Bla
11
[ 4ko²
(V -
(23)
N
Proof. By the definition of vf. <
k in
13
we have
E
N
E
(VVI( ( - VS((ET)) + (VA()))) vS(()))
(VS(( V V
E
Σ (Vii(, ,5) - v((a))))
+E
(Vf:(=]]) ():
N
Σ
+ Σ Vf((T)
+E
4 N
Σ
ko +
Σ
E
-
-
+
Σ (Vf((T)) v)(TT)
N
+k
Σ
N
ko² + KL2 Σ
B
2
+E
Σ
(V(((t)) - v)((T))
N
+ E [V)(()))
(24)
where the second inequalities can be obtained by using obtain Lemma
17 again. Rerrangeing the inequality, we
B PROOF OF LEMMA 3
In this section, we introduce Lemma which bounds the difference between the local model æf and the average model 4!.
15

---

Under review as a conference paper at ICLR 2020
Lemma 3 Under Lemma
7 and Lemma 2. when the learning rate "y and the communication period
k satisfy that 72-,11² 1, we have the following inequality
T-1
N Ellac
12
24 12
V((aa)) + 1- 36
B
8'
N
36k2
tmok r!=!"
18h7 2T
C7²C
(25)
36
36k22212'
where
C = N
ΣΣ Σ
(26)
Proof. According to the updating scheme in Algorithms 1, æ can be represented
x x
(27)
On the other hand, by the definition of at, we can represent it as
N
[-1
Σ
(28)
Substituting 27
and
28
into the left hand side of we have
25
B
|
N
Σ
E
8"
Yo;
j=1
r=t
1タE Y0."
B
Σ
N
T=
j=1
N
2
700
E
Yor"
oj
N
N
T= j=1
N
700
+
E
Σ
2B
Σ
N
N
==1
r-(
j=1
E
70.
(29)
According to the result in Lemma and Lemma 2 for t 2 k, we have
12y² L
Σ E
Blaa * 11 +2
Σ
Elit x'' 1P
N
Tmm! y'mtt!
e'-1
d'-1
+ 2k
Σ
Ello=
ac. =r'(1²
+ 12k??
Σ
|V )11 + 18k-702.0000
r'me"
r'me!!
and for 1 < ki we have
2
12
N --
2il1
Σ Σ
E E =²11" 11 4k-
[v
N
<=1 1=0
+4ky²
2
Σ (V Vf(*5)
(31)
N
16

---

Under review as a conference paper at ICLR 2020
Summing up
30 and 31
from f = 0 to T - 1, we obtain
T
2
N
12
T-1
Σ
Bla
El
x" 112 + 2k
Eli 255 11
N
t-k
T'=!"
T-1
1,2
k-
+12kg
Σ
[Vf(**)||+
18
Ela=i 1011
N
1=0 im1
+4k7
Σ
+3
47
(Vi((') V((())
N
1 L
3k 3 4
+ 2 1,2
T B - 11
N
1=1
[=k
41
+12k?y
V
[(()))|
+ 18k7 2T
VVi(())) -(()))
N
36
T-1
T-1
E B 112
24 1.2
B|a -F
N
T-1
4 k-1
+12kg
Σ
Σ I-u
Σ
(32)
N
1-0
where the second and the third inequalitics can be obtained by using a simple counting argument.
Denote C = Φ EE N
D (Vf.())) - V)()t) Rerrangeing the inequality, we ob-
tain
T-1
IV + 24k L T-1 d-11
(1-36k² 22
1
Σ
Σ
Ellat
1'11²
S 12k
Σ
Σ B x"' "12
N
+18ky o +
(33)
Dividing 1 - 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 S 1 have the following convergence result for Algorithm 7
27. and 72 < 1, we
+ Σ F 3(f(#)) --)
3rLo² + 56k 202 + 12-2L2C
T7 +
(34)
2N
Since f((.)² 1,2,... NN are L-smooth, it is easy to verify that f(.) is L-smooth. We have
Proof.
f(#++1) S f(a²) (Vf("'), +11 - + L
+1
$91
N
= =(a') - V)()'),
Σ nn
T
N 1=1
1=1
N
2
N
I((')
()((")) N
Σ
+
Vi
(35)
2
17

---

Under review as a conference paper at ICLR 2020
By applying expectation with respect to all the random variables at step t and conditional on the past (denote by E.g.). we have
(
$ [( -
(((6',
1
In2
Eej.
Σ 1=1
N
v
N
2
.
1=1
f(6')
7
||V
Σ
N
(z
Tf(2')
1
M
2
N
N
L7 +
N
Bel
Σ
V
(36)
2
Note that
N
Eej-
N
N
N
N Σ
+
Σ {z(
N
N
Bej-
1
(t)
1
Σ f((s))
+
1
fi((
N
N
N
1
+2
fi(s))
vf((m)))
N
N
1
Σ
Σ (((saa
+
1
Σ vi((a)))
(37)
N
N
N
where the last equality holds because Eej
( N
Vi(aot
- # EM Vsi(at))
= O. and
N
Baj-
1
Σ (m)))
N
N
fi < \=
N
2
Ey (ml, +4) v,., (m))). (aa Vic((tt))))
N
IShSDSN
= Ed
1
(((()))
N
(38)
N
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
N
1f(+++1
S Bf(+') - -EI
LA)E
S (a:))
N
N
1
Lo?
E
V
Σ
(39)
2
N
2N
18

---

Under review as a conference paper at ICLR 2020
We then bound the difference of fi*") and N E (zf)
NV N Σ {((s
N (Vi((=)) vΛ(at))
V(()))
i=1
Bl((VSi(a)) - v,((a)))|*
B
L
Σ
E||0 -=!l"
(40)
N
where the two inequalities follow from Cauchy's 's inequality and Lipschitz gradient assumption, re-
spectively. Substituting (40) into (39) yields
7
\ 70 Ly)B
N fi(tt)
7
x + 7 Lo²
+
Σ
Eliø"
(41)
2N
2N
Rearranging the inequality and summing up both sides from = to T 1, we have
N
2
+
(1-
L7)
((aat)
N
t=
22
Lo2
Lo
S
f fr
B|a
mt|
(42)
2N
2N
t=1 t=0
Substituting Lemma 3 into
42 and combing 722 < 1, we obtain
|| + a1
IT)E
1 N
V
fi
To²Lo²
6k22312
T
9
$ f(to) - ff +
VV((*)))
+
2N
36k22
36.211222
27 L20
1
T-1 Σ
E 4 -
1 36k2>212
36
t=k !!=!"
$ f(to) - -5 + To?
+ 12
[()()))) + 18 L²T
2N
T-1
+4.21'0 + 24
Σ
Σ
(43)
1 !!=!!
TB
19

---

Under review as a conference paper at ICLR 2020
Next, we bound TG-
Ts =
Σ
=
N
N
Σ
Σ E
Σ
( v(((())
v fi (1
t=0 7'm(!!
i=1
1-1
Σ
Σ
-
+
Σ
vi((a())
N
r'=!!
+2B
Σ
(vi(zi)))) vf(aa)),, ΣΣ Vf((zt)
1-1
N -V vf(ee()
T-1 1-1
1-1 N
Σ
Σ
E
ΣΣ
Σ
Σ
E
N2
N2
[=k 7'=!"
X=
t= y/=!"
17
(44)
Since Ef's are independent, we have
N
Ty
Σ
R
V - V[((a))))
a
+2
Σ
( V((aa))
(V -VV -V/(3)))))))))))
1-1
Σ E
Σ
( (((mm))
+2
Σ
(V,, (2, (1g() - Vsi (a(g))
ISUSESN
=
Σ E[V 3
(45)
Substituting 45 into 44
we have
T-1
22 T-1
Tb
EIVM vi(0)1
Σ
Nº
N2
t=k
t 7/1""
2k 2T
T-1
N
ΣΣ
(z
(46)
N
N
1=1
20

---

Under review as a conference paper at ICLR 2020
where the inequality holds since t - T' S st- -5" t" S 2k. Substituting 46 into
43
we obtain
Σ
[ 11 + 3 - LT)
S f(0o) - fr + Lo2
+ +12 10,
V V || + 18K77 o
2N
T-1
1172 + 21h 2
Σ
Σ
|
t=k
S f(āo)) - -f + Lo*
+
+12h"
|| + 11hh"""""*
2N
+4 + 48k 72 02 L'
24k
1
(47)
N
Rearranging this inequality and dividing both sides by Tr.
2 we get
1
Σ
(1 -
T
2( 1*)
872L2C fx
96h
L00
+
Tx
N
T
N
1 T-1
r'-1
+ T
48k,y 2 L
Σ
V
LT)B
(xx
(48)
N
TB
Then we prove T'ss S O. If the learnign rate 7 satisfies
S I 2I
then we have (1- - Lx) 2 1.-
vi((tt)) 17)
Ts
Σ b=b
9 2 L
Σ
ΣΣΣ v(()))
E
2T
N
Σ Vilcoty) )
N
192k 7
V(((())
-
-
E
2T
T-1 L
384K* A
Σ
E
N
Σ
v)(a)))
2T
1=0
20
3841",4 L
M(
(49)
2T
Since 122 < 1, then we have 7 2 < 1. and thus Ts S 0. Rearranging
48 and
dividing both sides by - LL?, we get
Σ E|
2(f(#)) (-)
362 L N(1 24)2
T
T7(1 24K2-PL2)
I 24
82.L30
96k 662
+ T(1 - 21122212)
N(1 - 11222-2122
3(f(=") - -8 +
To²
+ + 20222 12-21.20
2022
+
Tr
2N
T
N
3(f(2)) - -5")
3z
12-2
+ 56ky2 2 1.2 202??
(50)
Ty
2N
T
where the inequalities hold because 22,21,2 < 7g and
S 3.
21

---

Under review as a conference paper at ICLR 2020
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 oVT
J/N
and the total number
1,22 we have the following convergence result for Algorithm
satisfies
a²
30(f(E") - f" + +3L)
12NC
(51)
VNT
0272
Proof. Since
VN
T T2N"
12NK"L" 0²
we have 22 S 1 and
1
Then
ovT
ZI
have the result in
(4 and get
1
3(f(a") f)
+
3rL0
+
+ 00
12-²1.0C T
(52)
T
T7
2N
Combing 7 oVT
V
122
and
72N 12 R
1,22 8²
we have
72
o²
N
56h
T
56k
L T2
(53)
VT
VT
VT
3gLo²
3
(54)
2N
2/NT'
3( ((zo)) - 1n) (s)o) r
(55)
Ty
VNT
L2
12NC
(56)
T
G2T?
We can get the final result
+
T-1
30( - 3L)
12NC
(57)
VNT
a²T2
which completes the proof.
22

---

Under review as a conference paper at ICLR 2020
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
min f(z) == 2 (x) + f2(x)) = +xx" 2 + 6b", EER
(58)
where fi (æ) :- +x+ + 26) and fa(x) =- - respectively denote the local loss function of the first and the second worker.
We can set large variance among workers by adjusting b. Therefore, we can compare the con- vergence 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 B shows the gap with regard to iteration on different & and b. We can see that Local SGD converges slowly compared with VRL-SGD-VV W and VRL-SGD when the communication period k is relatively large. And VRL-SGD without warm-up is related to while VRL-SGD- W is to b. Figure 4 shows that the variance of of in VRL-SGD and VRL-SGD-W converges to O, while the variance of V f(( in Local SGD is 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.
not sensitive
b-10
b-10,
b-10, 1-16
b-10, k-64
-20
-10
-25
SGD
Local
-20
Local SGD
Local SGD VIL-522-V
-20
VIL 3GD-1V
-20
VIL VV
VIL-SGD-V WV
b-100, k-1
1-000 kmm
b-100, k-16
b-100,
1ap2 1op2-1000711
-00
-15
SED
Local
Local
500
-20
WIL
-20
MRL SGD
WIL
-10
b-1000,
b-1000,
b-1000, k-16
b-1000 k-64
7.3
(opR)
-2.5
-5.0
SED
Local
20
-20
-30.0
460
550
250
10000000
20
-30
-25
-20
-20
VEL-55241
520
200
200
Figure 3: Logarithm of distance the global minimum for different b and communication period k.
23

---

Under review as a conference paper at ICLR 2020
b=10.k=1
10,
b=100 K6
b=:00. km84
10
10
-10
-00
20
10
16
30.
SRD
Local
Local SGD
-GD--V
VAL-SGD-W
VRI-SCD-VV
-10
-20
-50
530
400
220
20
20
15
20
-20
-20
20
120
-40
Jacal
-20
Local
SGD
VBL
VRL-2GD-W
WV
VIL-522-V/
-30
-50
VRL-5DD
1000 kcr
1=0000, km
b=1000, kc:
b=0000, km
20
15
120
-20
20
-30
Local
50D-W
VHL
501-1/
500
-10
10000, km!
b-10000,
10000,
30
20
20
20
-20
Jacal
Local
Local
Figure 4: Logarithm of variance among workers for different b and communication period k.
24

---

Under review as a conference paper at ICLR 2020
F THE ANALYSIS OF PARAMETER K
In this section, we evaluate all algorithms with different communication period k.
As shown in Figure VRL-SGD converges fast S-SGD, while Local SGD, EASGD converge slowly even if we set the period k to half of it in Figure | The results show that l in Local SGD should be smaller, such as k = 2 or
5 in transfer learning, which is in line with T
NT
117,1877 3.9. However, we can set k r 117,1877 15 VRL-SGD. Figure compares x2 the convergence of different algorithms with larger k. We observe that the convergence of VRL- SGD will be affected with much large k, but VRL-SGD is still faster than Local SGD and EASGD, which is consistent with our theoretical analysis.
N
LeNet, MNIST
TeaCNN,
Tranffer Learning.
InapeNet
0.4
DANGIN--25)
0.3
0.4
Loos
1.0
0.5
0.1
0.0
25
30
100
25
50 Epacc
100
100
200
300
Fpoch
Epoch
Figure 5: Epoch loss for the non non-identical case, We set for LeNet, k 25 for TexICNN and
k = 10 for Transfer Learning.
Leaming. ImageNet
0.4
0.4
1,06
1oos
Less
1.0
0.2
0.5
0.1
100
50 Epach
160
Epoch
Epoch
Figure 6: Epoch loss for the non-identical case. We set k 40 for LeNet, k 110 for TexICNN
and 1: = 40 for Transfer Learning.
25


Reviews:
[{"review_id": "rJgPsOx6FS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.  \n\nThe following are my concerns:\n1) 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. \n\n2) In Corollary 5.2, the convergence result is not related to k. It is false to me.\n\n3) It is not clear in algorithm 1 how the \\delta^{t''} is updated.\n\n4) The assumption in equation (11)  \"When all local model x^t, x\\tau 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^*. \n\n5) In the experiment, the setting of k should affect the experiment. However, authors don't analyze this parameter.\n\n\n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HyxV4BPPtB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes the variance reduction to the local SGD algorithm and shows the proposed VRL-SGD can achieve better convergence than local SGD when the data are not identical over workers. The idea is interesting and the paper is easy to follow. However, the study does not go into depth. I do not support the acceptance for current situation. \n\n1. The paper does not show the convergence rate when the function is convex/strongly convex, which make it hard to compare with previous works e.g. EXTRA [Shi et al. 2015]. \n2. There are many alternatives to achieve communication efficiency. The paper does not argue why to choose variance reduced Local SGD. A natural idea to reduce the variance is to distribute the inner loop of SVRG to different workers as proposed in [Konecny et al. 2016]. Moreover, the analysis is given in [Lee et al. 2015] and [Cen et al. 2019]. Especially, [Cen et al. 2019] suggests using a regularization term to handle the data load is not balanced over the workers. \n3. The paper states that S-SGD cannot achieve linear iteration speedup due to communication bottleneck. Can we avoid the communication bottleneck by increasing the batch size? There are vast literatures on distributed training of deep neural network by using large batch size.  \n4. The experiment comparison is not complete given there are many related work in this area.\n\nQuestion: How to determine the number of local SGD steps for each communication round? In SVRG, the number of iterations in the inner loop is related to the condition number (strongly convex case). Does the number of local SGD steps have a similar correspondence\n\n[Jason Lee, et al.]  2015. Distributed Stochastic Variance Reduced Gradient Methods and A Lower Bound for Communication Complexity.\n[Shicong Cen, et al.] 2019 Convergence of Distributed Stochastic Variance Reduced Methods without Sampling Extra Data\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "HJelZJgJ9B", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper tackles the problem of data-parallel (synchronous) distributed SGD, to optimize the (finite) sum of N non-convex, possibly different (in the so-called non-identical case), loss functions. This paper focuses on improving the communication efficiency compared to several existing methods tackling this problem.\n\nTo that end, the authors contribute:\n· A novel algorithm and its asymptotic communication complexity.\n· The proof that the common metric of the sum over the training steps of the expected squared norm of the gradient at the average of the N parameters is bounded above.\n· Experimental results (training loss function of epoch number) comparing this algorithm with 2 existing ones, solving 3 problems under reasonable settings.\n\n  The training time per epoch of VRL-SGD is claimed to be identical to the one of Local SGD, as the algorithm only have minor differences.\n\n- strengths of the paper: \n\n· The main paper is very easy to follow.\n· Good effort to give intuitions on why VLR-SGD can improve the convergence rate of existing algorithms.\n  Such an effort is to be highlighted.\n· No obvious mistake in the main.   I have not thoroughly checked the full proof though.\n\n-  weaknesses of the paper: \n\n· The algorithm, while having differences, is quite reminiscent of Elastic Averaging SGD (EASGD) [1].\n  Indeed in both algorithms the model update at the workers consists in both descending the local gradient plus descending toward some \"moving-average\"obtained through averaging all the local models.\n  In EASGD, this \"moving-average\" is common to every worker and the master, which updates it every k steps.\n  In this paper, each worker has its own \"moving-average\", which update computations are different than in EASGD as the use the instant average of the workers' models instead of the previous \"moving-average\".\n\n[1]Sixin Zhang, Anna Choromanska, Yann LeCun, Deep learning with Elastic Averaging SGD,  NeurIPS, 2015\n\n- Questions I would like the authors to respond to during the rebuttal:\n\n· Could Elastic Averaging SGD (in particular their fastest variant EAMSGD) be applied as-is to solve the non-identical, non-convex optimization problem at hand?\n  Despite the authors of EASGD not studying their algorithm in the non-identical case, following what is done in the intuition part of VRL-SGD (in particular Equation (8)), it seems that the update rule of the \"moving-average\" in EASGD is then equivalent to having a momentumSGD with dampening (instead of the \"generalized SGD form\" obtained with the approach of VRL-SGD).  Hence my question.\n\nI suggest acceptance. However I'm willing to change my opinion after reading other more qualified reviewers in the sub-area of variance-reduction techniques.\n\nnote: If EASGD was to be sound in the non-identical case as well, my decision would not change much.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a novel variance reduction algorithm for SGD. The presentation is clear. But the theory is not good enough. The reivewers worry about the converge results and the technical part is not sound.
Decision: Reject