Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper proposes a method to address the "local scalability" problem in decentralized SGD. The authors study existing data parallel approaches and building upon the limitations, they propose two approaches - a synchronous and asynchronous non-blocking methods which aim to utilize compute resources optimally and avoid using large batch sizes.

I have a few comments:
- In the introduction, the paper mentions problems of finite-sum minimization form but it is missing the regularizer terms. Is this intended? It is much more common to see finite-sum minimization optimization with l1/l2 regularizers to control model complexity. I am bit surprised if the authors did not consider this.

- Degradation in accuracy upon increasing batch sizes is a popular problem and there has been lot of important work in this work (e.g. LARS [1], LAMB [2] to mention just a few). I don't see what the advantages of the proposed method are in comparison to these approaches which approach the problem differently but end up ultimately solving the large-batch accuracy issues. Can the authors comment this? on whether they investigated this empirically?

- From what I see, the proposed method does not "intelligently sample" the data points based on some structure/theoretical observation/heuristics etc. Correct me if I mis-understood. If so, how does proposed approach compare with other methods which aim to construct mini-batches or sub-sets of data on local workers more intelligently? such as [3] or [4]. I feel these related works also can extend to distributed decentralized SGD well.

- The scale of datasets is not large enough for distributed method. I would like to see experiments on datasets with larger # of data points, classes than what is currently presented.

- Did the authors perform any experiments on dense vs sparse datasets to see how the methods perform? The non-uniform distribution of data on various workers in my opinion can affect the optimization a lot and it would be good to see the authors comment on this.

- Table 2 is not convincing to me.
   (a) What if we go larger than 256 batch size? How does the accuracy look like in that case?
   (b) The gains are only marginal and don't seem significant. Did the authors perform any statistical significance tests or multiple random trials? If so, what was the variance of this experiment?

- The paper obtains a convergence rate of 1/\sqrt{T} based on what I understand? I am curious if the authors could comment on what assumptions need to be changed or what fundamentally stops the method from achieving a linear rate?

- Organization of paper can be improved. Minor: equation numbers are missing. The Quality/Perf column in Table 1 is confusing - what to quantify "ok", "good", "poor"?

I feel the paper does not meet the technical bar for an ICLR paper due to incomplete related work, unconvincing experiments. Proposed approaches do not seem very novel to me.


[1] https://arxiv.org/pdf/1708.03888.pdf

[2] https://arxiv.org/pdf/1904.00962.pdf

[3] https://negative-dependence-in-ml-workshop.lids.mit.edu/wp-content/uploads/sites/29/2019/06/SMDL_ICML_2019_ND_Workshop.pdf

[4] https://arxiv.org/pdf/1704.06731.pdf
review_title: Paper does not pass the bar (technically strengths and novelty aspects) for acceptance at ICLR

final_score: rating: 4: Ok but not good enough - rejection
review_content: In this paper, the authors argue that the mini-batch method and local SGD method suffers generalization performance degradation for large local mini-batch size. An asynchronous method is proposed to improve the generalization performance. A sublinear convergence rate is provided for the non-convex objective. As there are some missing definitions and little explanation of the proposed method, the reviewer finds the paper hard to read.

1. The comparison shown in table 1 is problematic. When the local batch size is increased from 128 to 1024, the learning rate also needs to be scaled accordingly. It is not surprising that we observe performance issue if we do not increase the learning rate. This makes the motivation of the proposed algorithm questionable.

2. It is not clear to the reviewer about the intuition of why local asynchrony can mitigate the generalization issue. In particular, compared to local SGD, the asynchrony introduces additional staleness, which can hinder the convergence.

3. What are the definitions of a^q and U^q? These two symbols are used in many places in the paper. But there are no definitions of them. And, what is s_j^q in Algorithm 1b?

4. What is the motivation of having the process alternate between a full and a partitioned lock-free asynchronous gradient updates to the model $x^q$? It seems to the reviewer that you are switching between SGD and block coordinate descent. This can reduce computational complexity but worsen the convergence at the same time.

5. Theorem 2.1 does not show any improvement by using more workers.
review_title: Official Blind Review #2

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper  proposes a class of  asynchronous local SGD by combining the local SGD with shared-memory based asynchronous gradient updates. Moreover, it proves that the proposed methods guarantee ergodic convergence for non-convex objectives, and achieves the classic sub-linear rate under standard assumptions. Some experimental results verify the efficiency of the proposed methods.  Unfortunately, I do not find Appendix of the paper, so I can not judge the contribution of this paper.  I hope the authors to upload the supplementary materials.  
In addition, because there are too many notations in this paper, it is easy to be confused. I hope the authors will introduce these notations in a table for readers.

review_title: This paper  proposes a class of  asynchronous local SGD by combining the local SGD with shared-memory based asynchronous gradient updates.

Meta-review: I think this paper has more positives than the reviews might indicate. And I do not share all the reviewers' concerns about the content of the paper. I think that there are a few concerns, though, that still suggest this paper should not be accepted as it is, when taken in conjunction with the concerns brought up by the reviewers.

On the positive side:

 - Asynchronous methods often give significant improvements, and the throughput benefits can even be seen here in Table 6.
 - The experiments are detailed with a lot of results comparing against many alternatives, including for ImageNet.

On the negative side:

 - The biggest concern I have with this paper is the scale of the experiments. This is supposedly about "distributed" SGD, but the largest-scale experiment was run on only two workstations, and many experiments were run in the S1 and S2 settings which don't seem to be distributed at all (run on a single workstation). That is, there's a mismatch between the scale at which these experiments were run and the scale at which people want to run distributed deep learning.
 - The theory seems to be only an incremental change to the standard local-SGD theory. The paper says "At a naive first glance, studying the convergence properties of locally asynchronous SGD would be an incremental to existing analyses for local SGD" but then it does not satisfactorily explain _why_ the approach is _not_ incremental. Not enough is done in the paper to explain why the analysis is not just a trivial combination of the local SGD with the standard approach to make an algorithmic analysis asynchronous. (Or, if the theoretical result _is_ incremental, the paper should make less of a big deal out of it.)
 - The description of the algorithm in Section 1.2 is confusing. I think it would benefit from being more concrete.

The paper should also compare against the paper "Asynchronous Decentralized Parallel Stochastic Gradient Descent" (Lian et al, 2017). It is actually not clear to me whether the method proposed here is a subset (or superset) of the method described in that paper, but they seem _very_ similar.
Decision: Reject