Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies static exponential and one-peer exponential graphs for Decentralized momentum SGD.  The results show that these two exponential graphs have a better balance between per-iteration communication and iteration complexity compared to the existing communication topology. Especially, they show that one-peer exponential graphs converge as fast as static exponential graphs but require less per-iteration communication. In the end, this paper provides adequate empirical evaluations of the exponential graphs in decentralized (momentum) SGD training.
main_review: This paper is overall technically sound and well written. The advantage of the exponential graphs claimed in this paper are well supported by theoretical analysis. The experimental results show that the one-peer exponential graph for DmSGD is very promising. I think the framework is potentially useful for deep learning training.

Comments and questions:
1.	How would these exponential graphs work for decentralized SGD? Is momentum necessary in this decentralized setting?
2.	how does the convergence bound in Corollary 1 compare with existing bounds
3.	Line 253, ‘Comparing (11) with (1)’, should it be (10) instead of (1)?
4.	Could the author comment on why the baseline Bi-RandMatch is competitive compare to the one-peer exponential graph?


---------
After reading the authors‘ response, most of my concerns have been addressed. I would like to increase my score to 7.
limitations_and_societal_impact: This paper does not focus on the potential impact.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The work proposes efficient communication topologies for Decentralized momentum Stochastic Gradient Descent (DmSGD)  algorithms used for training deep learning models. In particular, they focus on exponential graphs, where each nodes is connected to O(log(n)) other nodes. They analyze the spectral gap, which shows the graph connectivity, for exponential graphs and establish a logarithmic bound on it and claim that it was reported incorrectly in the literature to be constant.  Moreover, they propose to communicate over one-peer exponential graphs, in which each node communicates to a single neighbor. They theoretically show that a sequence of O(log(n))  one-peer exponential graphs achieve the same convergence rates, despite being far more efficient in terms of communication. They further confirm the effectiveness of their proposed method by running experiments on real datasets and applications and comparing them to other topologies and methods. 
main_review: The paper provides efficient communication topologies for running Decentralized  momentum Stochastic Gradient Descent (DmSGD) algorithms. In these algorithms the data is distributed over some nodes, the nodes compute gradients in parallel and the gradients are averaged based on the underlying topology. In particular, they focus on exponential graphs and a one-peer variant. The main motivation for considering such topologies is that they are sparse and lead to efficient communication. They further theoretically show that the sparsity in communication does not hurt the convergence rate. Finally, they show the effectiveness of their proposed method by running experiments on real datasets and real applications and comparing them to other topologies and methods. The paper is well-presented and well-organized and provide generic methods that are highly interesting for the machine learning community. 
limitations_and_societal_impact: The work presents strong theoretical and empirical results. Here are few minor issues, I don't believe these should be ground for rejection. 

(a) It would be helpful if running times were also reported in Table 3 to understand how using these topologies speed up the running time (if that is the case at all). Also, it would be helpful to see Fig. 3 with respect to time, as well.

(b) The reported metrics are quite close to each other for different methods and topologies. However, the results for the one-peer exponential graphs is generally better. 

(c) The functions f_i are defined inside Eq. (1), which is a bit confusing. It would read nicer, if the authors defined the functions f_i below Eq. (1).
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the exponential graph used for decentralized training in theory, and shows it effectively reduces the convergence bound and speeds up the deep learning tasks. A novel analysis for the spectral gap bound on exponential graph is given, which is tighter than the one shown in previous papers. Various experiments on large-scale vision tasks are conducted, the results seem to be aligned with the theory.
main_review: This paper addresses an important topic in decentralized training: how do we construct a communication graph to further improve communication complexity? The main contribution is the derivation and empirical verification on the spectral gap bound of exponential graph, which is novel. 

My main concern is in the baseline comparison. As we know, decentralized training utilizes the gossip algorithm, which is a well-studied topic in the literature especially in wireless network and control theory. Having said this, the main content in this paper is invariant to deep learning, but rather a discussion on the mixing time of the gossip matrix in terms of different graphs. Table 1 (and some in the appendix) in this paper lists some of the graph, but does not include many related algorithms and analysis. For example, [1][2][3][4]; also some optimality analysis is given in [5]. The authors should consider having a detailed discussion on how exponential graph compares to these algorithms and why it should be preferred over them.

In my experience, usually when we scale up the experiments to hundreds of GPUs, the speedup will become sublinear in terms of number of GPUs since communication gradually becomes the bottleneck. However, in Table 2 we observe nearly perfect linear speed up. This seems interesting and I wonder if the authors have any insights on this.

Some minor comments:

(1) In the complexity expression, constants should be written as $\Omega(1)$ in Table 2.

(2) In the experiments, std over the accuracy should be provided.


== Reference

[1] CRITICAL RANDOM GRAPHS: DIAMETER AND MIXING TIME
https://arxiv.org/pdf/math/0701316.pdf

[2] The mixing time of the giant component of a random graph
https://arxiv.org/pdf/math/0610459.pdf

[3] The best mixing time for random walks on trees
https://arxiv.org/pdf/1410.5112.pdf

[4] Mixing Times for Random Walks on Geometric Random Graphs
https://archive.siam.org/meetings/analco05/papers/07SBoyd2.pdf

[5] Fastest Mixing Markov Chain on a Graph
https://web.stanford.edu/~boyd/papers/pdf/fmmc.pdf
limitations_and_societal_impact: This paper does not reflect any potential negative societal impact.
review_title: null

Meta-review: This paper deals with fully decentralized learning with SGD and shows that network topologies in the form of exponential graphs provide fast convergence and accurate models.

The reviews were quite positive and the author response helped to consolidate the scores. Overall, the theoretical and empirical results were found to be strong and relevant for practitioners in a increasingly popular topic. Therefore, the paper is accepted.
Decision: Accept (Poster)