Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper did comprehensive experimental study on how DPSGD and SSGD converge in different tasks. Some intuition is provided to explain why DPSGD usually performs better than SSGD under large batch settings. Training with large batch size is a very important topic nowadays to speedup deep learning pipelines. In this paper different models, learning rates, and datasets are evaluated. Overall I feel the experiments show a good sign that decentralization is helpful in this case. 

In my opinion the experiments in this paper are valuable, but I would be more happy to see this paper to inspire some solid theoretical studies on exactly why decentralized (and other tricks) can help the large batch training problem (and when they will fail). 

Some additional things I would love to see in the revision:
* comparing with SSGD with "warmup" where the learning rate increases from a small value at the beginning of training. This kind of warmup lr schedule has been shown effective in some existing work (for example, Goyal, Priya, et al. "Accurate, large minibatch sgd: Training imagenet in 1 hour." arXiv preprint arXiv:1706.02677 (2017).), and should mitigate that convergence issue mentioned in this paper.
* code to help other practitioners verify the results

I wanted to give a accept but the formatting of this paper has a lot of room to improve. To list a few:
* duplicated references in the reference section
* page 2 footnote 2, the line below equation (2): quote should be fixed
* sections titles formatting (capital letter or not) should be consistent
review_title: Comprehensive experimental study. Paper formatting should be improved.

final_score: rating: 3: Clear rejection
review_content: This paper gives some empirical comparison of centralized sgd and decentralized sgd for relatively large batch size. The authors claim that decentralized sgd performs better than centralized version and that this is because the noise introduced by the decentralized version helps escape the local minima.

While it is claimed that "We show, both theoretically and empirically, that the intrinsic noise in DPSGD can...", it is hardly possible to find any theoretical insight. The theoretical analysis part, Section 2, contains a figure (Figure 2) with an entire subsection (Section 2.2) discussing it, but include no theorem, lemma, or even proposition! There is clearly stated noise comparison between centralized sgd and decentralized sgd and thus it is not clear why one can claim decentralized sgd does better becomes of noise.

Second, as a paper studying the large batch setting, it is necessary to define what large batch means and how batch size relates to the convergence, none of which is included in the paper. In fact, in the theoretical analysis part (Section 2), batch size does not appear at all. Why is large batch size important, or is decentralized sgd always better than centralized one? The entire Section 2 is far away from understandable.

The experiment section also fails to justify the claim. The authors compared decentralized and centralized sgd for batch size = 1024, 2048, 4096, 8192. Are those all large batch, or is 1024 small and the other large? From Table 3 I guess it is the former case. But then a nature question is: does decentralized version perform poorly for small batch size? The experiment section  fails to show a "phase transition", which cannot support the claim. Furthermore, for vision tasks, evaluation on a single dataset (CIFAR10) is certainly not enough. Same thing for ASR task. Most importantly, there is no empirical evidence supporting the claim that decentralized sgd " 1) [it] automatically adjusts the learning rate to improve convergence; 2) [it] enhances weight space search by escaping local traps (e.g., saddle points) to find flat minima with better generalization".  Figure 3 and Figure 4 simply show properties of the neural network and the datasets and has nothing to do with optimization methods. Table 2,3,5,6 only shows final accuracy produced by the optimizers, but say nothing about how the optimizers reach the solutions.

The paper writing is problematic too. A single section (Section 3) talking about methodology with less than 1/3 page is awkward. Discussing empirical results in the analysis part (Section 2) is misleading. It is also not acceptable to have "Please refer to Appendix F." for a whole subsection (4.4). Many sentences do not make sense. For example,  "In a large batch setting, the learning rate must be increased to compensate for the reduced number of parameter updates". Why is number of parameters updates reduced? "While there was anecdotal evidence that DPSGD outperforms SSGD in the large-batch setting". What is the evidence? Which paper claims this? There are numerous typos too.

In short, this paper is sloppy and far away from publishable in its current stage. 
review_title: This paper gives some empirical comparison of centralized sgd and decentralized sgd for relatively large batch size

final_score: rating: 3: Clear rejection
review_content: This paper claims that decentralized parallel SGD (DPSGD) performs better than synchronous SGD (SSGD) and noisy version of synchronous SGD (SSGD*) in large batch setting. Theoretically, it shows that the noise in DPSGD is landscape-dependent, which may help generalization. Experimental results on CV and ASR tasks show that DPSGD can outperform baselines when batch size is very large. Meanwhile, DPSGD is observed to adaptively adjust the effective learning rate and converge to flatter minima.

Although the idea in the paper is insightful, most of the claims are lack of sufficient supports and in-depth discussion. For the theoretical part, Eq(4) only shows the differences of noise between SSGD and DPSGD. The explicit relation between Delta^(2) and generalization is not provided. After reading Eq.(4), I still do not know why Delta^(2) can help generalization. In my mind, Delta_S is also landscape-dependent because the covariance matrix of \Delta_S aligns well with Hessian in some cases [1][2].

The explicit relation between decreasing effective learning rate and convergence rate of an optimization algorithm is not provided too. The convergence not only depends on the tendency of the learning rate but its decreasing rate. For an extreme instance, if the effective learning rate decreases rapidly, it is hard to imagine that it will help convergence. 

Besides, there are many writing issues in the paper. Please see the details comments below.

Detailed comments:

(1) For a scientific paper, every claim should be objective. There are many subjective claims in this paper. For example, "Recently, ASGD has lost popularity due to....."(in Intro), "One possible reason is that the complexity of escaping a saddle point....."(in Intro), "The poor performance is likely due to......"(in Sec2.1), etc. These claims are lack of sufficient supports  and are not convincing.

(2) There are redundant notations which make the paper hard to follow. For example, the "SSGD+noise" in Figure 1 and "SSGD*" in Figure 2; the subscript of a letter sometimes denotes the learner, sometimes denotes the average or subset average.

(3) Some claims are ambiguous. For example, "It is clear that \Delta^(2)" depends on the loss landscape-it is larger in rough landscapes and smaller in flat landscapes". What is the measure of the loss landscape and the flatness? Both landscape and flatness are descriptive terms and their measures should be clearly introduced. Why does the noise in SSGD not depend on landscape?

(4) The term "Multiple learners" is misleading, especially for SSGD. It is better to name them local workers because they only calculated gradients and SSGD outputs a unified model. 

(5) I suggest to use the original format because this version looks too crowded. For example, the space between sections is too small and the paragraphs in the introduction are merged.

In summary, the current version is not ready to be published.

[1] Wen, et al., An Empirical Study of Large-Batch Stochastic Gradient Descent with Structured Covariance Noise

[2] Zhu, et al,. The Anisotropic Noise in Stochastic Gradient Descent: Its Behavior of Escaping from Minima and Regularization Effects.

review_title: Interesting idea, but lack of solid theoretical supports and in-depth discussion

final_score: rating: 5: Marginally below acceptance threshold
review_content: #### Summary
This paper posits that gossip-based SGD methods for distributed deep learning are more stable, and generalize better, than synchronous SGD in large-batch settings. There is some intuitive discussion, but the hypothesis is mostly validated empirically on MNIST, CIFAR10, and several ASR tasks, for a wide variety of model architectures. I found this hypothesis very interesting, and to be of significant value to the community. I also found the approach sufficiently novel. The empirical evidence was convincing, but was restricted to very small-scale tasks, and so on larger datasets, it is not clear to me what the limiting batch-size is going to be where one observes the behaviour outlined in this work, or whether such a limiting batch-size even exists. The paper was also missing a study on the magnitude of the consensus error $\Delta^{(2)}$ (via the graph topology) on model performance.

Including a study on i) larger datasets and ii) various consensus errors $\Delta^{(2)}$ via the graph topology, would strengthen the paper, and I would be happy to increase my support for this work.

---
#### Originality
Most of the literature in this area has demonstrated that gossip-based methods converge faster (i.e., in wall-clock time), but to possibly higher error solutions. Previous literature has also demonstrated that this gap can be bridged with longer training. By consider extremely large batch-sizes, this work demonstrates that there may be a regime in which gossip-based methods are more stable and generalize better.

The paper first sets out to intuitively describe this phenomenon by decomposing the noise in the gradient-based updates. The decomposition is provided as the sum of a "true" gradient term and an orthogonal component. I quite liked this approach to the decomposition because it then allows the author to describe what they refer to as the effective learning-rate — a quantity that they can empirically measure in practice. While I generally liked this exposition, there is a minor error, which seems inconsequential for the rest of the paper: it is stated that these noise terms $\eta$ are unbiased, which as far as I understand doesn't appear to be correct. Generally speaking, under unbiased sampling, the noise term $\eta$ has zero mean if the gradients are evaluated at $w_\alpha$ (or are linear in their argument), but not if they are evaluated at $w_j$, as in DPSGD; i.e., $E[\frac{1}{n}\sum_{j}g_j(w_j)] \neq E[g(w_a)]$, where the expectation is with respect to the mini-batch sampled across all workers. Though more generally, I also liked the highlighted relationship between the noise strength $\Delta$ and the effective learning learning rate $\alpha_\epsilon$, which does not depend on this (possibly erroneous) zero-mean property.

The hypothesis is thereafter tested through extensive experiments on MNIST, CIFAR10, and various ASR tasks for a broad range of hyperparameters.  Both the goal of the paper, and the approach taken to address it (i.e., through the reasoning of effective learning rates), are sufficiently novel in my opinion.

---
#### Quality and Significance

Large batch deep-learning is of significant interest for parallelizing deep learning workflows. There do exist known limitations for scaling large-batch training, and therefore finding a regime (in the limit of large batches) in which certain methods are not only more efficient, but also more effective, is certainly of value to the community.

I am not familiar with ASR baselines, but the vision baselines look reasonable. I was actually quite surprised by Figure 1. I was not aware of this behaviour for SGD with large batch sizes on CIFAR10. However, I would be interested to see if this observation is particular to CIFAR10 on vision tasks, or whether similar results hold on ImageNet, which is much more stable to large batch-sizes. For example, training on ImageNet with the same batch-size is known to work well. One question I have concerns a subtle point that could explain the results you’re seeing in Fig.1: is the loss (and accuracy) being computed before or after averaging/gossiping the weights? The step-size is scaled according to the batch-size, and your large-batch update is only complete after averaging/gossiping, therefore $w_j$ is a poorly specified set of model weights, and the curves should be evaluated at $w_a$.

More generally, modulo this important distinction in my opinion, I found the empirical evidence convincing. However, my main concern is that the analysis was only on very small-scale tasks, and so on larger datasets, it is not clear to me what the limiting batch-size is going to be where one observes the behaviour outlined in this work, or whether such a limiting batch-size even exists.

What was missing was also a study on the effect of the graph topology. It is stated in the appendix that 16 learners with randomized communication was found to work well, but I think crucial to this discussion is how the consensus error $\Delta^{(2)}$, which depends on the graph topology, affects this aforementioned behaviour.

Are the observations of the 2D contour and hessian plots consistent across multiple sampled directions? I ask because the parameters are 100-dimensional, and so it may not be the case that the level sets are entirely characterized by these 2 random vectors.

---
#### Clarity

The work is clear for the most part. Some minor comments on the exposition
* The last approximation in equation 4 is not clear to me (e.g., what is the double subscript on the weights), though I agree with the following sentence, that the consensus error is going to be larger in sharper landscapes.
* Not sure what qualifies as a “generic algorithm” so I would remove the phrase "To the best of our knowledge, we are unaware of any generic algorithm that can improve SSGD large batch training on this many models/tasks."
* I would temper sharp vs flat minima arguments, since these arguments have been shown to depend on the parameterization of the objective.
* Decentralized training can be synchronous (e.g., via all-reduce), and so I don’t think the real distinction (i.e., gossip-based vs globally synchronous methods) is well captured in the title or the exposition.
* The common argument that large batches converge to sharp minima is still a largely experimental idea, and so basing an argument on these principles does not provide convincing evidence (especially since such arguments depend on the parameterization of the objective).
* How is the complexity of escaping a saddle point computed, and why is it assumed that the models in Figure 1 are stuck in saddle points. Phrases like this should be somewhat tempered, or at least discussed in more detail: “However, this is not a good solution for high-dimensional DL training as shown in the blue curves of Figure 1. One possible reason is that the complexity of escaping a saddle point by adding isotropic noise has a polynomial dependency on the dimension of the parameter space, so adding such noise in a high dimensional space (such as deep learning) does not bring significant benefits"
review_title: Interesting take on gossip-based algorithms for deep learning

Meta-review: This paper did experimental studies on how DPSGD and SSGD converge in different tasks. Some concerns were raised regarding the clarity, some unjustified claims, baselines and etc, and partially addressed after the rebuttal and discussions. However, some critical concerns remains. The reviewers agreed that the paper would be more appealing if these concerns can be well addressed.
Decision: Reject