Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: The authors propose a comparison between two methods of parallelization of the SGD, namely SSGD and DPSGD. They prove theoretically that the decentralized one (DPSGD) adds a smoothing effect to the naive SSGD, and shows that DPSGD is better than SSGD as the batch size increases.
strengths_and_weaknesses: ## Strengths

This paper makes a tiny link between some distributed methods and second-order methods. It helps to understand their dynamics. Furthermore, the computation of an "effective learning rate" for DPSGD is useful to illustrate the implicit mechanisms of this method.

The experiments on large datasets, such as ImageNet, are valuable.

According to the experiments, DPSGD seems to perform way better than the alternative choices when the batch size increases.

### Control experiments

It is noticeable that the authors have tested a modification of the SSGD, called ``SSGD*'', in order to test fairly SSGD against DPSGD. 

## Weaknesses

### Theory

Theorem 1 contains at least two major issues:
 * The hypothesis: ``$\| \frac{1}{n} \sum\_{i = 1}^n X\_i - \frac{1}{n-1} \sum\_{i = 1}^{n - 1} X\_i \| \leq \epsilon$ almost surely'' is not reasonable when the $X\_i$ are i.i.d. and without compact support. So, we cannot consider the simple case where the $X\_i = \nabla L^{\mu\_i(t)}(\vec{w}\_i(t))$ are i.i.d. Gaussian random variables.
 * In the proof: it is true that, conditionally to $\mathcal{F}\_{t-1}$, the $\vec{w}\_{i}(t)$ are independent, but it is false for the $\delta w\_i(t)$. 
Let us recall that: $\delta \vec{w}\_{i}(t) = \vec{w}\_{a}(t) - \vec{w}\_{i}(t) = \frac{1}{n} \sum\_{j = 1}^n \vec{w}\_{j}(t) - \vec{w}\_{i}(t)$.Thus, all $\delta \vec{w}\_{i}(t)$ are linear combinations of the same set of variables, with only non-zero coefficients. It is thus impossible that two $\vec{w}\_{i}(t)$ are independent. Besides, independence has nothing to do with the fact the $\sum_{i=1}^n \delta \vec{w}\_{i}(t) = 0$... on the contrary, this equation indicates a strong dependence between the terms.

However, it is probable that this theorem can be made useful and rigorous. But, anyway, it does not seem to be useful in the presented work. 

### Experiments

Error margins: there is no mention of any variance or error margin in the results. So, we cannot evaluate the significance of the presented results: if a reported result seems to be better than another, it may be luck... 

The main drawback of the experimental setup is its complexity. In particular, a huge preliminary phase of fine-tuning seems to be necessary, without proposing a reproducible procedure to recover the proposed hyperparameters (which are very numerous). The authors only provide citations of preceding works, where the fine-tuning has already been done. 

It is clear that the authors claim to prove the reliability of DPSGD as the batch size increases; they do not claim to beat the state of the art. So, there is no point of testing architecture trained with highly fine-tuned optimization procedures. A unified and simplified optimization process should have been considered.

### Clarity

The paper suffers from several writing issues.
 * The "related works" section must not be put in appendix. This section is fundamental to draw a line between existing works and actual contributions, and to evaluate fairly the significance of the paper.
 * Using $\vec{w}_j$, where $j$ is an index standing for an integer, and $\vec{w}_a$, where $a$ is a simple letter (standing for "average"), is confusing. Why not using $\hat{w}$ instead of $\vec{w}_a$? Same issue with $\vec{w}_{s, j}$. Besides, arrows can easily be removed, or replaced by bold text: $\mathbf{w}_j$ instead of $\vec{w}_j$.
 * If the authors do not use the general version of DPSGD presented in [33], then the general notation $\vec{w}_{s, j}$ can be removed.

questions: There is a beginning of theoretical analysis of the proposed method though the Hessian of the loss. SSGD and DPSGD provide information about the loss surface, and, intuitively, DPSGD provides richer information. Is it possible to formulate SSGD and DPSGD as second-order methods, where the approximation of the preconditioning matrix (usually the Hessian) is computed in a distributed way? Is this the optimal second-order method with acceleration through distributed computing? Etc.

Note: Fig2b shows an evolution of the learning rate, which appears also when using second-order methods.
limitations: The authors have tested an improved version of SSGD against DPSGD, in order to compare them fairly.

The main unchecked limitations are (as mentioned above):
 * no error margins in the results;
 * lack of reproducibility: the reader lacks information to obtain the same hyperparameters.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: The paper studies two distributed learning algorithm for training large-scale deep learning models.
The authors argue that the decentralized parallel stochastic gradient descent (DPSGD) has a series of advantages over the more commonly employed Synchronous SGD (SSGD). They argue that the optimization dynamics of DPSGD injects noise which smooths the optimization landscape and allows for larger learning rates. This is especially beneficial in the large-batch-size setting.
The paper contains one main theoretical result concerning the smoothness of the objective function that DPSGD implicitly minimizes. 
Several experiments with various tasks and architecture are conducted.
strengths_and_weaknesses: **Strengths:**
- The experimental section contains several diverse tasks and architectures, therefore having large coverage
- The intuitive and empirical arguments in favor of DPSGD are interesting; somewhat helping build up confidence in this algorithm which has other advantages wrt SSGD

**Weaknesses:**
- I am not quite convinced of the utility of the theoretical results, especially regarding the Gaussian hypothesis (see below in questions)
- Even factoring this concern out, I believe the theoretical contribution to be very limited as it is basically the application of a know Lemma
- The presentation is unclear in various passages, including the proof of the theorem; notation is too often overloaded (see eq (3)) making it difficult to understand what is what. This is especially bad in section 2.2: e.g. in equation (4) one might expect the authors to discuss about the DPSGD algorithm, but there is no mention of the gradient $g_j=\nabla L^{\mu_j}(w_j)$. Other important quantities such as the total loss are never explicitly defined and the reader is left with the need to self-interpret the paper at various points.
- The layout of the paper should be revised: the abstract is too long and the related work section cannot be relegated to the appendix. Space can be saved by avoiding repetitions, focusing discussion and removing unnecessary "summary" sentences at the end of each experimental section.
- The claim that DPSGD needs very little to no tuning is exaggerated and not backed up by the experiments. In particular, note that in the NLP experiment DPSGD still needs the learning rate warm-up stage, although shorter. 
- The paper would benefit from a more complete (also formally) introduction of the two algorithms. For instance it is not clear what happens at the end of the optimization with DPSGD. Are the weights averaged over all the worker?

questions: *Major*
- I do not understand why the assumption that $\delta_i w |\\mathcal{F}_{t-1}$ should be Gaussian with zero mean and especially equal (scalar) variance. Why this should make sense? In the appendix the authors call for the central limit theorem, but 1) I do not understand to what it should be applied 2) I think that at least the multidimensional version of the CLT should be considered here. On the contrary, the empirical results with SSGD + Gaussian noise (which show poor performances) seem to suggest that there is a fundamental difference between the noise induced by DPSGD and Gaussian noise. 
- One might hypothesize that the advantage of  DPSGD is that the noise is adaptive (but still Gaussian). To empirically verify this, the authors could run an experiment where the Gaussian noise added to SSGD is scheduled after what the authors find by running DPSGD (e.g. figure 2 b) for the MNIST setting. If the resulting methods performs on par with DPSGD, then I could be more willing to accept the assumption, although questions would remain. 
- Otherwise, I would argue that Th 1. is not useful to understand the advantages of DPSGD. 

*Others*
- From Lemma 2 of Random Gradient-Free Minimization of Convex Functions [39] it would follow that the smoothness coefficient should be $\frac{\sqrt{n}}{\sigma} G$ where $n$ is the dimension of the parameter vector. From where do you obtain $\frac{2}{\sigma} G$ that you report in the paper?
- I do not quite understand how the theoretical result cannot involve the mixing matrix. As the authors note, for a complete mixing matrix DPSGD is equivalent to SSGD; this should be reflected in the statement and formulation of the theorem.
- In eq. (2) is it intentional that there are 2 sets of weights $w_j$ and $w_{s,j}$? Isn't it that the loss is also computed at $w_{s,j}$? Or does each worker maintain 2 sets of weights?

*Minor*
- Why only limiting to the cross-entropy loss? 
- I do not understand the reason behind "self" of self-adjusting. Why "self"? Usually one speaks about adaptive method.
- Typos: allow [for]; tasks -> models in line 29; inconsistencies between figures and tables and texts (e.g. Fig 1 SSGD-noise vs SSGD* in the text).

limitations: - Negative societal impacts are not discussed, but I do not see any visible one, so I think missing that discussion is fine for this paper. 
- Limitations of the proposed analysis are not discussed, and should be added, e.g. in relation to the assumptions of the theorem.
- I do not think it is proper to have one paragraph sketching out very informally a possible result suggesting that other "people" (line 144) then can fill the gaps. One might suggest this as a potential interesting future work (briefly and in the conclusions). Or spell out the theorem and include the proof. As it stands, the passage starting at 144 should be removed.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This work compares two stochastic gradient descent methods for Distributed Deep Learning (DDL), one is Synchronous Stochastic Gradient Descent (SSGD), and the other is Decentralized Parallel SGD (DPSGD), in a large batch setting. The authors empirically find that DPSGD not only has a runtime benefit but also a significant convergence benefit over SSGD in the large batch setting, which is due to additional landscape-dependent noise brought by DPSGD.

To understand this phenomenon, the authors perform both theoretical analysis and experimental investigation. They claim that the introduced noise smooths the loss landscape. They also conduct extensive studies over 18 state-of-the-art DL models/tasks and demonstrate that DPSGD often converges in cases where SSGD diverges when training is sensitive to large learning rates.
strengths_and_weaknesses: Strengths

(1) The authors provide a theoretical analysis to compare the smoothness of the two methods.

(2) This work conducts experiments on an adequate number of tasks and datasets.

Weaknesses

(1) The writing of this work has a big problem. The authors put important context including Related Works and DPSGD and SSGD Runtime Comparison in the appendix. 

Related work is almost an indispensable chapter of an article. Besides, whether DPSGD has an advantage in runtime compared to SSGD is also important. Since the authors claim that DPSGD can have an advantage in terms of convergence, it is to be expected whether this advantage can bring about a saving in runtime. Although the conference has body content restrictions, putting very important content in the appendix is ​​a discouraged behavior.

(2) Although this article emphasizes that DPSGD has great benefits, from the perspective of actual performance, the results are not very satisfactory when the learning rate is very large. Therefore, whether a large learning rate brings a great improvement in efficiency will be a very important question, and I don't think the author provide a detailed analysis in the text.
questions: (1) The orthogonal decomposition of noise in Equation (4) is based on the expectation of users. In other words, it only holds when the number of users is very large. However, the experiment shown in Figure 2 only performs with 5 learners. In this case, is the results of the experiment consistent with the theoretical analysis?


(2) In Table 1, the best performance comes from when lr=1x, and the performance drops significantly when lr is very large. What are the advantages of a large learning rate?
limitations: Even though the authors claim that they describe the limitations of their work. However, I cannot an explicit description. I would like to ask the authors if they can show me where is the limitation during the rebuttal.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper compares the convergence behavior of two common training schemes for distributed stochastic gradient descent optimization on large batch sizes. In particular, Synchronous Stochastic Gradient Descent (SSGD), where weight updates are computed by synchronizing all distributed learners globally, is being evaluated against Decentralized Parallel Stochastic Gradient Descent (DPSGD), where only a random selection of neighboring distributed learners is used to compute the weight update. The authors observe a much better convergence behavior with DPSGD and explore the hypothesis that this is due to an inherent quality of this training scheme to introduce stabilizing noise in the weight update rule, which automatically scales the learning rate depending on the landscape of the loss function. The paper continues to give a theoretical explanation for this observation and finally provides a very extensive evaluation on various machine learning tasks in a large distributed training environment. The results demonstrate a clear advantage of DPSGD for large batch sizes and a more robust convergence behavior that doesn't require to reduce the learning rates drastically, as it is the case for SSGD.
strengths_and_weaknesses: The claim of this paper is very adequately examined. The biggest strength of this paper is clearly the very deep evaluation, taking large CV, NLP and ASR tasks into account. The authors hereby build on top of previously published modern state-of-the-art training recipes with warm-up periods and adaptive gradient optimizers in order to ensure optimal performance. The thorough evaluation and the conclusions drawn from the experiments is convincing and of high significance to the field.

The scope of this work seems to be a bit too large for this conference. At various points in the paper it is noticeable that the authors were struggling with the page limit. It is particularly unfortunate that the description of related work had to be put into the appendix. One way to reduce the scope of this paper would be to leave out the evaluation of noise-injection, which appears rather limited by sticking to Gaussian noise injection at various points in the training process. While these results somehow support the claims by the authors, that the advantages of DPSGD are related to their inherent noise introduction, it is far from being proven to be the case given that manual noise injection experiments with SSGD contain many heuristics and best effort attempts to simulate the effect of DPSGD. In my opinion this could have been studied in a separate publication.
questions: It is not very clear to me why only Gaussian noise has been considered, it appears like the noise simulation could have been designed such that it is more similar to the noise introduced by DPSGD.

line 213: numbers up to twelve (12) should be written as words

limitations: The authors did not really discuss the limitations of their evaluation, which is unfortunate. As mentioned earlier, especially the simulated noise injection has a lot of room for further considerations. It again appears that this discussion has been omitted due to the page limit. An outlook on potential societal impact is also not provided. Since the important results of this paper mostly benefit groups with very large training resources, some discussion on this topic would have been appropriate.
review_title: null

Meta-review: metareview: This paper compares all-reduce SGD (SSGD) with decentralized SGD (DPSGD) and argues that the latter can tolerate lager stepsize due to a smoothing effect induced by noise in DPSGD. 

The reviewers found that the theoretical contribution is overclaimed. By the strong assumptions needed in the theory section (such as e.g. assuming Gaussian updates) the analysis becomes somewhat disconnected from the experiments, and, in addition, reviewers found several typos and issues in Section 2 of the original submission. Even though the numerical evaluation was judged more positively by all reviewers (and championed by one), we came to the consensus that the paper should be rejected in its current form.

(Minor comments:) In the discussion, we also found that that the term “self-adjusting” might be a bit misleading (as learning rates are kept fixed and are not self-adjusting), and that the paper would benefit of a brief discussion of related works that study the benefitting effect of smoothing in large-batch training (such as https://arxiv.org/abs/1805.07898 or https://arxiv.org/abs/1906.10822, etc.).

confidence: Certain
Decision: Reject