Beyond Exponential Graph: Communication-Efficient Topologies for Decentralized Learning via Finite-time Convergence

Summary

This paper studies communication-efficient topologies for decentralized learning. The proposed topology has four merits: (1) finite-time exact consensus; (2) fast consensus rate (having exact consensus using $O(\log_{k+1} n)$ graphs); (3) arbitrary maximum degree ($1 \leq k \leq n-1$); (4) arbitrary number of nodes. The most related works to this paper are 1-peer exponential graphs, 1-peer hypercube graphs. Given the existing algorithms, to the best of my knowledge, this paper is the first to get exact consensus using graphs of length $O(\log_{k+1} n)$ instead of $O(\log_2 n)$ with arbitrary number of nodes, where $k$ is the maximum degree. The main algorithm relies on k-peer hyper-hypercube graph. and simple base-(k+1) graph. The k-peer hyper-hypercube graph is a generalization of the 1-peer hypercube graph. The simple base-(k+1) graph is constructed by dividing the graph into subgraphs with node numbers being a power of k, and then applying the 1-peer hypercube graphs, and using the communication between subgraphs. The base-(k+1) graphs are constructed by decomposing $n = p\times q$, where $p$ is prime to $q$ and the factors of $q$ are larger than k+1, and then, apply the sub-algorithms respectively. The paper is generally well-written. The authors provide sufficient illustrations to show how the algorithms work and some numerical experiments to demonstrate the efficiency of their topologies.

Strengths

* the length of graphs needed to have exact consensus is $O(\log_{k+1} n)$, which improves upon the length $O(\log_2 n)$ of the 1-peer exponential graphs. * the authors use lots of illustrations to show the implementation of the algorithms, which are very clear.

Weaknesses

* The proof for the exact consensus of Algorithm 1 (k-peer hyper hypercube graph) is lacking. * Considering that the algorithm often divides the graph into many subgraphs, while the nodes do not have equal status, the topologies proposed in this paper are relatively complicated. The intricate graph structures could possibly limit its applications in practice, like delayed communication, compressed communication, and information loss. * The descriptions of the algorithm are only from a panoramic view. It is not clear whether there is a simple way for each node to know its neighbor in each graph efficiently.

Questions

* Is it possible to give theoretical guarantees for the claim that base-(k+1) graphs have shorter lengths than simple base-(k+1) graphs? * Are there efficient methods for each node to know its neighbors in each graph instead of generating the entire graph by each node? * Is it possible to extend the algorithm to more restricted topologies where each node can only communicate with a subset of nodes directly?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

I would suggest the authors provide formal proof, or at least a sketch of proof, for the exact consensus of algorithm 1 (k-peer hyper hypercube graph).

Summary

This paper introduces time-varying communication topologies to tackle the problem of communication efficiency in decentralized learning. These topologies, inspired by the idea of the 1-peer exponential graph, achieve finite-time exact consensus, meaning that the exact average of values is obtained after a finite number of steps. The graph is obtained through an iterative process: starting from the k-peer hyper-hypercube graph (an extension of the 1-peer hypercube graph), the simple-(k+1) graph is introduced to handle the case when $n$ has large prime factors, using k-peer hyper-hypercube graph as a subroutine. Finally, the base-(k+1) algorithm is developed based on the two previous graphs to remove redundancy and obtain exact consensus in fewer iterations. Then, a convergence result is given based on the bound from Koloskova et al. (2020b), and experimental results suggest that the base-(k+1) graph improves over the (1-peer) exponential graph indeed. Unsurprisingly, more connected topologies lead to better accuracies in heterogeneous settings.

Strengths

- Finite-time consensus for any number of nodes. - The bandwidth / speed trade-off can be controlled through parameter k (max degree at each iteration). - Great efforts are made to make the constructions understandable (though they still remain quite hard to grasp), through figures and step-by-step introduction.

Weaknesses

- I find the state of the art is not discussed in enough details. While decentralized methods are discussed in details, the finite-time consensus aspect calls to comparing with efficient allreduce methods as well, that are used to scale modern deep learning algorithms. I am not an expert in this domain, but a quick search led me to, e.g., refs [A,B,C] (but there are probably many relevant others). The advantage of finite-time consensus is that updates can be done after each iteration, which is not necessarily the case with allreduce methods. At the same time, there are no guarantee on how close to the mean the iterates are before finite-time convergence, so several SGD steps without communication could also be performed between allreduce SGD for instance (local SGD style), which would not be too different. This could / should also be compared against. Minor comment: One can always have a number of nodes equal to a power of 2 by introducing some nodes with value 0 (and upweighing the other nodes), and making it so that each actual node owns at most 1 virtual node, thus at most doubling the effective degree. It's an easy way to use 1-peer exponential graphs for all n. [A] Rabenseifner, Rolf. "Optimization of collective reduction operations." Computational Science-ICCS 2004: 4th International Conference, Kraków, Poland, June 6-9, 2004, Proceedings, Part I 4. Springer Berlin Heidelberg, 2004. [B] Mikami, Hiroaki, et al. "Massively distributed SGD: ImageNet/ResNet-50 training in a flash." arXiv preprint arXiv:1811.05233 (2018). [C] Ueno, Yuichiro, and Rio Yokota. "Exhaustive study of hierarchical allreduce patterns for large messages between gpus." 2019 19th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGRID). IEEE, 2019.

Questions

- Can you clarify how your method compares with optimized allreduce methods? For instance if you use it until exact consensus each time. What are the bandwidth/latency trade-offs achieved? How do they compare to existing results? - How robust is the Base-(k+1) graph approach to failures/packet drops? Finite-time exact consensus would be lost in this case, but can we recover good approximation properties or is everything lost in this case?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

N/A

Summary

This paper introduces the BASE-(k+1) GRAPH, a new way of designing topology for decentralized learning that is shown to enjoy a fast consensus rate while maintaining small maximum degree. The authors validate the effectiveness of the BASE-(k+1) GRAPH through experiments, demonstrating its finite-time convergence for certain number of nodes and its effectiveness for decentralized learning. Overall, the BASE-(k + 1) GRAPH offers improved communication efficiency and convergence rate for decentralized learning methods.

Strengths

- The paper proposes a new way of designing topology for decentralized learning, the BASE-(k + 1) GRAPH, which allows for a fast consensus rate while maintaining small maximum degree to enable more communication-efficient decentralized learning. - The authors provide a theoretical analysis of the proposed method which ensures the property of small maximum degree and several experiments are conducted to validate their claims. - The paper is well written and organized, with a logical flow of ideas. The authors provide a clear explanation of the proposed approach, and also includes helpful figures and tables to illustrate the concepts and results.

Weaknesses

- The numerical experiments are still not sufficient; it would be more convincing if they compared the BASE-(k + 1) GRAPH with a more comprehensive set of topologies to demonstrate its superiority. As far as the reviewer know, there are several other topologies that can also achieve fast consensus rate and small maximum degree, such as Ring All-Reduce where maximum degree is 1 [a] , Tree All-Reduce where maximum degree is 2 [b] which and optimization-based topology [c]. - The paper does not explain how to decompose n, whether different decomposition methods will produce different results and how to decompose n to get the best results. - The paper assumes a homogeneous network, which may not be practical in some real-world scenarios, where communication bandwidth and underlying topology constraints may affect the communication between nodes. [a] Alexander Sergeev and Mike Del Balso. Horovod: fast and easy distributed deep learning in tensorflow. arXiv preprint arXiv:1802.05799, 2018. [b] https://developer.nvidia.com/blog/massively-scale-deep-learning-training-nccl-2-4/ [c] Sun, Chuangchuang, Ran Dai, and Mehran Mesbahi. "Weighted network design with cardinality constraints via alternating direction method of multipliers." IEEE Transactions on Control of Network Systems 5.4 (2018): 2073-2084.

Questions

- The reviewer would also like to know how the method can be extended to heterogeneous networks where the topology may not exhibit regular structures. - There are several other topologies that can also achieve fast consensus rate and small maximum degree; how the proposed method compares with them? - For a given number of nodes n, there exists several ways of decomposition, and different way of decomposition will lead to different maximum degree and consensus rate. The reviewer would like to know how one can find the optimal decomposition method to properly balance the maximum degree and consensus rate.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

- The paper could benefit from a more detailed discussion of the limitations of the proposed approach, such as its sensitivity to certain types of data heterogeneity or its applicability to heterogeneous networks. - A more detailed description of the algorithm and its implementation (such as the decomposition method of node number n) would be helpful for readers who want to replicate the experiments or apply the method to their own problems. - The BASE-(k + 1) GRAPH should be compared with a wider range of existing topologies. - The derivation of Theorem 2 should be shown to help readers better understand the influence of BASE-(k + 1) GRAPH on the convergence of decentralized SGD.

Summary

The paper considers the problem of decentralized optimization and proposes a novel time-varying communication topology that has better properties than prior topologies, especially when the number of nodes n is not a power of 2 i.e. (i) it is sparse, and (ii) has good spectral properties, translating to the good optimization behavior. Paper provides a description of the proposed topology, its properties, and evaluates its effectiveness in practice.

Strengths

- The paper is very well written and clear - Proposed topology clearly improves over the previously known topologies, especially when the number of nodes n is not a power of 2.

Weaknesses

1. Paper gives consensus rate (in e.g. Table 1) in O-notation, i.e. hiding the constants. However, actual constants do matter a lot. If we allow the use of O-notation, then expander graphs would be the best theoretical graphs, as they have constant consensus rate, as well as constant maximum degree. However, expanders do not work well in practice for relatively small graphs as the constants are quite large. Therefore, I believe it is important to get good constants while designing a new communication topology. 2. Description of the algorithm for Base-(k + 1) graph is not fully clear. In step 1. of the algorithm (line 181), it was not clear why n can always be decomposed in this way? What if n is a prime number ?

Questions

1. If the number of nodes n is a power of two, is it still beneficial to use your proposed topologies ? Including the larger range of n in figure 8 that covers power of 2 might be good. 2. Why did you not include the gradient tracking in comparison in figure 9? 3. When reading Figure 3, I got confused why the number of averaging steps is 5, while log_2(5) < 3. 4. In the Experiments section (Fig. 6, 7, 8, 9), having a Base-6 graph might still potentially be better than the Exponential graph, as its maximum degree would be the same, but it would lead to the faster convergence. Why did you not include the Base-6 graph in the comparison? Minor suggestions: 5. It might be good to provide the open-source code of generating proposed topologies. 6. Might be helpful for the reader to indicate how large is log_2(n) for each of the experiments. 7. When giving an example in Figures 3 & 4, I felt it might be better to have the same number of nodes n in both cases, so that the reader can see how is the Base-(k + 1) graph can reduce the number of steps from the Simple Base-(k + 1) graph

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

4 excellent

Limitations

yes

Thanks for the response.

Thanks for the clarification.