Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a decentralized SGD method, RelaySGD, for faster mixing in distributed deep learning, with the aim of improving performance on nodes with heterogeneous data sources. Convergence guarantees are provided for smooth non-convex functions under the weak growth condition, as well as for smooth strongly convex functions under the weak growth condition. The method relies on undirected, static, spanning-tree graphs.
main_review: The clarity of this paper can be improved, but ultimately, I found this work interesting and sufficiently significant. I do however have some questions about the correctness of the theory and significance of the results that I hope the authors can address in their rebuttal.

- The proposed RelaySGD is equivalent (analytically) to running gossip SGD over an all-to-all graph with fixed delay along each edge based on the number of hops between nodes in your spanning tree. This may result in faster mixing than regular gossip, and the experiments are convincing. However, precisely demonstrating this result would strengthen the paper, for example by constructing an augmented graph (see Chapter 10 of "Convex optimization in signal processing and communications" 2010 by Nedic and Ozdaglar) with the appropriate mixing weights, and comparing the spectral radius of that augmented graph to the spectral radius of a regular doubly-stochastic gossip matrix over various topologies.

On the theory:
- I may be missing something, but the matrix W does not look row-stochastic. Consider \tau=0, i=0, j=1 in a chain. Then [W]_{0, n+1} = 1/n and the rest of the row is equal to 0. Therefore, the rows of W do not sum 1.
Note that for the analysis you can simply apply known results in the literature for gossip with augmented graphs (e.g., see the reference about), hence I am not concerned about the empirical convergence of the method.

Practicality:
- Compared to regular gossip, the method requires each node to store one memory buffer for each neighbor, but has same communication cost, as parcels are summed before communicating. The memory overhead is not great, but as long as the number of neighbours remains small, this should be find and comparable to adaptive gradient methods like Adam.
limitations_and_societal_impact: No obvious negative societal limitations or impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work presents a novel decentralized deep learning algorithm on heterogeneous data. Specifically, the authors develop a RelaySum protocol for handling the information propagation in the networked systems with spanning trees, and RelaySGD for optimizing the learning problems. Different from the popular gossip averaging, RelaySum enables to relay messages through the whole network without decaying each node’s weight at every hop. The authors theoretically prove that RelaySGD is not affected by differences in workers’ data distributions, and that its convergence does not rely on the spectral gap of the graph, but instead on the network diameter. To validate the proposed algorithm, a few baselines and different datasets are used for the comparison. The empirical results show that RelaySGD outperforms baselines in terms of accuracy and convergence speed.
main_review: This paper is easy to follow and well written. The investigated topic is particularly critical as decentralized learning has been demanding in the era of big data. However, several major issues came up to my mind when I reviewed the paper carefully.
1.	Issue of topology. The authors mentioned in line 121 that the key insight of this work is that, on tree networks , the RelaySGD update rule can be implemented while using the same communication volume per step as gossip averaging, using additional memory linear in the number of a worker’s direct neighbors. It looks like the RelaySGD has specifically been designed for such a structure of networks. Though the authors in lines 137 and 138 have emphasized that RelaySGD can be used in any communication graph if a corresponding spanning tree is constructed. However, throughout the paper, I have not seen any techniques of converting any communication graph into a spanning tree. Additionally, all experimental results have been shown in terms of spanning trees for RelaySGD. It is difficult to evaluate if RelaySGD really works for other communications graphs.
Further, as the additional memory is linear in the number of a worker’s direct neighbors, it means that for a large-scale network, the computational overhead will increase exponentially?
2.	Unfair comparison in experimental results. As shown in Table 1, the topologies considered for different algorithms are different. In the empirical results, the accuracies were obtained for different algorithms with different topologies, which rendered the unfair comparison. Probably as the authors suggested, some conversion can be done to turn any communication topology into a spanning tree, but the empirical results presented in the paper cannot convince myself that the proposed RelaySGD has superiority over existing methods. For example, in Table 3, RelaySGD w/ momentum seems to perform better than SGP w/ momentum. But it is difficult to tell if the different is just caused by the difference between topologies. Moreover, why for SGP w/ momentum and D^2 w/momentum (or DP-SGD w/ momentum), do they also need different topologies in this work?
3.	Confusing and/or problematic analysis. (a) In the supplementary materials, the authors introduced Assumption H for the bounded noise at the optimum. While the similar property has been defined in Assumption B. Any relation between these two? Why did the authors define such an assumption for the optimum point, which has not typically been seen in the previous works. (b) The complexity for strongly convex case in Theorem looks problematic. As the $\epsilon$ has been used to signify the complexity, why did the authors still include the time $T$ in the complexity, which hasn’t been seen in any previous works? That way, the exact time $T$ required to achieve the $\epsilon$-accuracy is not obtained. (c) In Assumption I, the authors defined $M$ to be 0. Why is this case? I think Assumption I has been quite generic in previous works. That way, could the authors directly define Assumption I at the beginning? Why is the motivation to define two slightly different assumptions in the work? (d) In the proof, a matrix is denoted by a capital bold letter. However, in Lemma 11 and Lemma 12, the authors just used capital letter, which can be confusing. Also, in terms the norm, the authors at the beginning have defined that $||\cdot||$ is spectral norm for a matrix while 2-norm for a vector. It is easy to know that $||\cdot||_F$ represents Frobenius norm. What is $||B||_2$? Also, Lemma 9 – Lemma 12 are trivial and typically the authors can only mention in the proof. There is no need to give formal statements for these. (e) In line 183, the authors mentioned that the dominant term is a function of $\mathcal{O}(1/\epsilon^2)$, while in line 191, the leading term became $\mathcal{O}(1/\epsilon)$. Is it a typo or anything else?
4.	In lines 39 and 40, the authors said that the slow distribution of updates not only slows down training, but also makes decentralized learning sensitive to heterogeneity in workers’ data distributions. Why is this true? The second half may not be true. If each agent in a networked system has quite different data distributions, without effective techniques, even if the distribution of updates is fast, the performance is still poor. Since each agent tries to converge to its own optimal solution, the consensus among them enables a suboptimal solution to the global objective function. Therefore, regardless of the distribution rate of updates, decentralized learning is always sensitive to the heterogeneity.
5.	The dependence of RelaySGD/Grad on the data heterogeneity is a bit surprising to me. Though the table before Algorithm 6 illustrates the difference between RelaySGD and RelaySGD/Grad, it is confusing to me why the authors have introduced the RelaySGD/Grad in the work. It is also not robust to lost messages and workers joining/leaving. What is the motivation here? Are there any scenarios in which RelaySGD/Grad has superiority? 
Overall, the paper in the current form still requires substantial changes, particularly for the experimental results and some theoretical complexity analysis. I hope my comments can help the authors address these potential issues.

============Review Update=============

After carefully reading the rebuttal from the authors, and other reviewers' comments, I decided to raise my score. The responses from the authors clarified most of my major comments. Hopefully the authors can include the corresponding changes in the final draft to make it solid.
limitations_and_societal_impact: The authors have not adequately addressed the limitations and potential negative societal impact of their work. It would be great for the authors to add one paragraph to briefly discuss.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: A method to reduce communication costs when performing distributed training in networks where communication between nodes requires more than one hop. The trade off is increased memory usage and delayed communication (parameters arrive at a later iteration).

=== Review Update ===

Thank you for the clarifications. In particular, it is true that all virtual topologies used by modern distributed ML systems are sparse, so I retract my comment regarding "comparison on fully-connected" topologies as it certainly does not make sense.

After reading both the authors' response and the other reviewers' comments, I've decided to keep my score as-is.
main_review: Originality
- Delayed optimization over a distributed network is not a new idea, see Distributed Delayed Stochastic Optimization (Duchi and Agarwal, 2011). This paper should have been cited and discussed in the related work, though I still lean towards acceptance in spite of this issue.
- The paper's main idea is that messages are aggregated in a way that the memory and network costs are independent of network diameter (i.e. no need to maintain multiple delayed messages "in-flight"). I believe this is an original contribution.

Quality
- Wide coverage across multiple experimental factors: simulation vs real data, multiple competing baselines, various network toplogies, covers both SGD and Adam, and at least one model from CV (VGG, ResNet) and NLP (Bert).
- Interesting and insightful experiments that go beyond mere benchmark-chasing
- Theoretical proofs are sufficient and welcome, though I do not believe there is innovation in the proof techniques

Clarity
- Clear organization of ideas, writing and illustrations are a cut above the typical NeurIPS paper
- Minor issue: the main writing should state clearly that VGG is used for CIFAR10 experiments. This fact is only briefly mentioned in figure captions.

Significance
- Reducing communication in distributed training is a crucial topic, especially when model sizes have grown several orders of magnitude over the last few years
- However, even in Federated Learning, it is not clear to me if applications truly benefit from multiple communication hops. The issue is that topologies are usually "virtual" in peer-to-peer FL applications - it is up to the implementer to decide whether to use a fully connected topology (which does not need delayed communication) or not. Thus, the network topology is not an immutable constraint; it is merely a design choice.
- In connection with the previous point: there is one ablation experiment that is missing from the paper, and that is to compare the method on different non-fully-connected topologies vs the state of the art on a fully-connected one, under realistic assumptions for peer to peer applications. Such an experiment would have made the paper much stronger

limitations_and_societal_impact: No issues
review_title: null

Meta-review: The paper presents a new communication protocol for decentralized learning when the nodes have significant data heterogeneity. The reviewers all agreed about several of the positives of the current draft: good presentation, extensive experiments, interesting ideas. The main concern was the algorithmic novelty of the scheme (similar to tree-reduce, and gossip with delays), and the memory overhead proportional to the number of neighbors. However, it was agreed during discussions that this work carries enough technical depth to be interesting to the related communities (decentralized/fed learning).
Decision: Accept (Poster)