Beyond Exponential Graph: Communication-Efficient Topologies for Decentralized Learning via Finite-time Convergence
This work addresses communication bottlenecks in decentralized learning for applications in parallel computation and privacy preservation, offering a novel topology that improves efficiency without sacrificing performance.
The paper tackles the problem of balancing fast consensus rates and low communication costs in decentralized learning topologies by proposing the Base-$(k + 1)$ Graph, which achieves exact consensus in finite iterations and demonstrates higher accuracy and better communication efficiency than existing topologies like the exponential graph in experiments.
Decentralized learning has recently been attracting increasing attention for its applications in parallel computation and privacy preservation. Many recent studies stated that the underlying network topology with a faster consensus rate (a.k.a. spectral gap) leads to a better convergence rate and accuracy for decentralized learning. However, a topology with a fast consensus rate, e.g., the exponential graph, generally has a large maximum degree, which incurs significant communication costs. Thus, seeking topologies with both a fast consensus rate and small maximum degree is important. In this study, we propose a novel topology combining both a fast consensus rate and small maximum degree called the Base-$(k + 1)$ Graph. Unlike the existing topologies, the Base-$(k + 1)$ Graph enables all nodes to reach the exact consensus after a finite number of iterations for any number of nodes and maximum degree k. Thanks to this favorable property, the Base-$(k + 1)$ Graph endows Decentralized SGD (DSGD) with both a faster convergence rate and more communication efficiency than the exponential graph. We conducted experiments with various topologies, demonstrating that the Base-$(k + 1)$ Graph enables various decentralized learning methods to achieve higher accuracy with better communication efficiency than the existing topologies.