Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: 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.

To that end, the authors contribute:
· A novel algorithm and its asymptotic communication complexity.
· 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.
· Experimental results (training loss function of epoch number) comparing this algorithm with 2 existing ones, solving 3 problems under reasonable settings.

  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.

- strengths of the paper: 

· The main paper is very easy to follow.
· Good effort to give intuitions on why VLR-SGD can improve the convergence rate of existing algorithms.
  Such an effort is to be highlighted.
· No obvious mistake in the main.   I have not thoroughly checked the full proof though.

-  weaknesses of the paper: 

· The algorithm, while having differences, is quite reminiscent of Elastic Averaging SGD (EASGD) [1].
  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.
  In EASGD, this "moving-average" is common to every worker and the master, which updates it every k steps.
  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".

[1]Sixin Zhang, Anna Choromanska, Yann LeCun, Deep learning with Elastic Averaging SGD,  NeurIPS, 2015

- Questions I would like the authors to respond to during the rebuttal:

· 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?
  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.

I suggest acceptance. However I'm willing to change my opinion after reading other more qualified reviewers in the sub-area of variance-reduction techniques.

note: If EASGD was to be sound in the non-identical case as well, my decision would not change much.
review_title: Official Blind Review #3

final_score: rating: 1: Reject
review_content: 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\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^*. 

5) In the experiment, the setting of k should affect the experiment. However, authors don't analyze this parameter.




review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: 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. 

1. 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]. 
2. 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. 
3. 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.  
4. The experiment comparison is not complete given there are many related work in this area.

Question: 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

[Jason Lee, et al.]  2015. Distributed Stochastic Variance Reduced Gradient Methods and A Lower Bound for Communication Complexity.
[Shicong Cen, et al.] 2019 Convergence of Distributed Stochastic Variance Reduced Methods without Sampling Extra Data

review_title: Official Blind Review #2

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