Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper introduces SwarmSGD, a novel method that makes use of a graph of computational workers without central synchronisation. To minimize synchronisation overhead but maintain consistency between the workers' versions of the model, asynchronous, non-blocking random peer-to-peer averaging takes place every few local gradient steps, and quantization is supported.
The paper then provides theoretical analysis (under fairly restrictive assumptions), illustrating in which regime this extremely decentralised algorithm can be expected to converge (in average).
Finally, a thorough experimental section on significant benchmarks is run, demonstrating the actual potential of the method.
main_review: Generally speaking, the paper is clearly written, and is easy to follow. The authors provide valuable insights both in the description of the methods themselves, in the theoretical results and (perhaps most importantly) in their proofs. The Discussions part are very appreciated, and this type of analysis should become a staple for this type of paper.

The presented algorithm is novel and presents some very interesting characteristics, leading to potential gains in real-world ML workloads.

The experimental section contains very large scale experiments (at least for a paper in this theme), and demonstrate real potential.

There remains a few weaknesses in the paper, which I believe can be addressed with a bit more work.

The first one is some clarity issues. 
- In the initial description of the algorithm, it's hard to understand whether the general model is quantized or not. (l65 does not reference the crucial dequantization step before applying the gradient steps)
- l85 'convergence for non-convex objectives' is not defined, making the statement harder to interpret.
- some assumptions are not explicit: being able to simply replace T by nT in the bound relies on the strong assumption that computing gradients on different devices takes the same time.
- how expensive the quantization/dequantization steps are compared to computing gradients is not explicited. That would be quite helpful to assess how useful quantization is.
- that the optimal speedup is O(sqrt(n)) is not explained. Typically, using n machines one expects the optimal speedup to be O(n). This is the case even when analyzing linearly convergent algorithms. If we were to instead rely on the dependency in T, the optimal speedup there would be O(exp(n)).

The second issue is that there appears to be some overclaiming in terms of the theoretical results. While the paper promises non-blocking  updates, these are later supposed to be atomic. Similarly, the assumption l254 that Xi_t and Enc(Xi_t) are 'simutaneous' seems like a pretty strong assumption. Of course it simplifies the analysis but the crucial question is: can the proof be carried out without it? If not, then it is an integral assumption, which should be made explicit.
The results also suffer from fairly restrictive assumptions. While not unheard of, the necessary bounds are strong restrictions.

Finally, perhaps not enough space is devoted to the experimental section.
- It would be nice to describe the exact models trained in more details. The WMT model is in particular rather elliptically referred to.
- the WMT results for SGD are quite surprising: why does the 32-devices run converge to a worse performance than the 16 one? It could conceivably be slower, but as it's got a bigger batch size should converge to a better end BLEU performance
- BLEU is referred to several times as 'accuracy'. It's not an accuracy, it's a score.
- for machine translation tasks using transformers, practitioners typically do not use SGD but Adam instead. Is there a clear path to SwarmAdam?

All told, this is a nice paper, whose potential is not quite fully exploited in its current form. I recommend acceptance, and would be willing tu upgrade my score depending on the authors' response.
limitations_and_societal_impact: Could lead to faster network training, which would reduce the energy footprint.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: In this paper, authors propose the asynchronous algorithm for convex optimization in distributed decentralized model. This algorithm consists of two major components - local model estimation and quantization mechanism.
main_review: In this paper, authors propose the asynchronous algorithm for convex optimization in distributed decentralized model that's main idea is to decrease the communication complexity of the algorithm and figure out the communication bottleneck. The idea of the algorithm is the following: we randomly select some node $i$ in the network graph G and then randomly select one of its neighbors $j$.  After this, for node $J$ we save the average of quantized values for $i$ and $j$; however, for node $i$ we also update the model estimator via the local model update. This combination of local updates together with quantization technique allows to gain in communication complexity in comparison with local SGD that was shown in the experimental part of the paper. 


The presented algorithm is not restricted to some specific quantization techniques since the requirement to the Encoding and Decoding procedure is quite soft. However, it makes harder to follow the intuition without any example of applicable quantizations (only reference to the another article is provided). 

Due to the Corollary 4.2 the theoretical result is close to the optimal one that is a strong point of the paper. Also, the experimental results show that the SwarmSGD algorithm works well in practice too; however, I found figures too  small and hard to read.

limitations_and_societal_impact: yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a decentralized optimization method, SwarmSGD, for reducing the communication overhead in distributed deep learning. The proposed method combines asynchronous pair-wise gossip, quantized communication, and local updates into a single method and a unified analysis. Convergence guarantees are provided for smooth non-convex function, using the quantizer from Davies et al., 2021, and a bounded second moment assumption. Numerical results are provided on image classification (CIFAR, ImageNet) and machine translation (WMT En-Ge) tasks.
main_review: ### Originality and Significance
This paper mostly combines many related ideas from the literature (asynchronous pair-wise gossip, quantized communication, local updates) into a single method and so originality is limited. However, there is significance in the work since it is necessary for all these orthogonal communication reduction techniques to eventually be integrated together. In this sense, this paper fits nicely in the literature.

### Quality
I only have a couple of concerns about the quality of the empirical and theoretical contribution, and would appreciate if the authors could address these in their rebuttal.

The assumptions made consist of
- Static communication graph
- L-smooth
- Bounded variance
- Bounded second moment
- Poisson point process for asynchronous activation of nodes

To the best of my knowledge, the analysis applies standard tools from the literature, e.g., the supermartingale-esque iteration, used heavily in the analysis of subgradient push methods, as well as perron-frobenius for consensus. However, in my opinion the bounded second momentum assumption is a non-trivial limitation of the theoretical contribution. It may be ok in a quantized setting, but this assumption is still used in Corollary 4.2 after removing the quantization effects.

The Poisson point process assumption is *fine* for the theoretical assumptions, but then it is approximated in practice by setting the number of local gradient steps for each node to be a geometric random variable, which I would expect to impractically degrade performance in practice, since more frequent asynchronous non-blocking communication is likely to result in better convergence.

The baseline numbers for SwarmSGD seem good and consistent with the literature. Specifically, the proposed method looks to recover standard numbers for the chosen benchmarks. However the timing comparison with other gossip-based methods looks highly misleading. For example, it seems odd to use a fully-connected topology for the comparison of general gossip-based methods like SGP and D-PSGD with the pair-wise methods like SwarmSGD. Especially since the whole motivation for gossip-based deep learning methods is to reduce communication overhead by leveraging sparse topologies.
limitations_and_societal_impact: There don't seem to be any obvious negative societal implications of this work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper discusses a new variant for asynchronous decentralized SGD called SwarmSGD. Different from many previous algorithms SwarmSGD does not suffer from deadlocks. A new compression algorithm is used in SwarmSGD, which is different from commonly used ones such as stochastic rounding. Convergence rates of SwarmSGD are given with discussion on the assumption of second moment bound on the gradients, and experiments on language modeling and ImageNet are conducted.
main_review: The paper addresses an important question in asynchronous decentralized optimization, and is well written. The content is generally easy to follow. 

Pros:
==
- The application of (Davies et al., 2021) in decentralized optimization seems interesting. The idea of compressing the distance of model rather than model itself is well-motivated. 

- The paper provides detailed comparison to previous algorithms such as AD-PSGD and SGP (some of them are in the appendix), which clearly states the contribution and the challenges.

- I didn't check all the proof line by line, but the overall logic and the asymptotic complexity seems reasonable to me.

- The experiments are comparatively large-scale compared to other algorithm-type papers in the community.

Cons:
==
- In Theorem 4.1, the last term in the convergence rate is a little counter-intuitive. If SwarmSGD runs on a fully connected graph, it is expected to converge faster since the spectral gap increases. However, if we replace $\rho_{max}=n$ from complete graph into the last term, it becomes $O(n^5)$; and if in such case we need the $1/\sqrt{T}$ to be the leading term, we would require $T\geq O(n^{10})$. This seems a little diverged from reality, could you elaborate why using a better graph worsen the convergence rate?

- I'm a little confused by the statement of non-blocking and staleness in this paper. For starters, if worker $i$ is updating the communication buffer of worker $j$ while worker $j$ needs to read from its communication buffer for interacting with worker $m$, it should be waiting for $i$ to finish writing the buffer. Otherwise, it causes additional error like the Hogwild setting. A completely asynchronous execution should be one-sided writing such as ADDP algorithm in this paper: (https://arxiv.org/pdf/1901.08215.pdf). In fact, the line 4 in Algorithm 1 already implicitly assumes some sort of blocking: two workers cannot be sampled simultaneously and the updates in one iteration is completely atomic. Same thing applies to the staleness: if node $i$ is sampled uniformly, a staleness bound is implicitly placed. 

- In the abstract the author states the algorithm works for heterogeneous data case, which does not seem to hold in the main theorem. Specifically, a bound of $\varsigma^2$ is still assumed in Equation (3) and shown in all the convergence rate. An algorithm robust to the heterogeneous case should be invariant to this bound. See the Theorem 2 of D$^2$: http://proceedings.mlr.press/v80/tang18a/tang18a.pdf. 

-  A minor concern: In AD-PSGD, the $T$ is the number of query to gradient oracles while in this paper, $T$ is defined as the total number of interactions. Since each node is performing $H$ local steps. For fair comparison, the $T$ in convergence rate should be replaced by $TH$. However, this calibrated rate seems to have an additional $\sqrt{H}$ term on the sample complexity term $\sigma^2$. Why having local steps if it compromises the convergence rate while not having explicit benefits in the experiments?

**Updates**

I thank the authors for adequately addressing my concerns. I suggest including some of these points in the paper to make it clearer.

limitations_and_societal_impact: I don't see any potential negative societal impact of this paper.
review_title: null

Meta-review: This paper presents a gossip-style method to perform distributed optimization of a sum of individual functions, combining stochastic gradient updates with quantization mechanisms. In addition to a theoretical guarantee on the scheme's convergence, the paper reports on experiments training i) ResNets in pytorch on CIFAR-10/100 and ImageNet datasets, and a larger Transformer-XL model in tensor flow on the WMT17 dataset. 
The reviews for this paper all recommend acceptance, being especially laudative about the scale of the experiments performed to validate the proposed approach. The reviews also point to an implicit assumption of atomic updates in the algorithm's operation, which the authors acknowledge and will make explicit in the final version.

The authors' experimental work is indeed quite significant. It is nice to have a theoretical guarantee; a discussion of the meaning in theory and in the experiments of the assumptions (especially the 'Bounded Local Function Variance' assumption) would be enlightening.
Decision: Accept (Poster)