Beyond Exponential Graph: Communication-Efficient Topologies for Decentralized Learning via Finite-time Convergence
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-$\left(k+1\right)$ Graph. Unlike the existing topologies, the Base-$\left(k+1\right)$ 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-$\left(k+1\right)$ 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-$\left(k+1\right)$ Graph enables various decentralized learning methods to achieve higher accuracy with better communication efficiency than the existing topologies. Our code is available at https://github.com/yukiTakezawa/BaseGraph.
Code (1)
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Exponential Graph is Provably Efficient for Decentralized Deep Training
Decentralized SGD is an emerging training method for deep learning known for its much less (thus faster) communication per iteration, which relaxes the averaging step in parallel SGD to inexact averaging. The less exact …
Coordinated Path Following of UAVs using Event-Triggered Communication over Time-Varying Networks with Digraph Topologies
In this article, a novel time-coordination algorithm based on event-triggered communications is proposed to achieve coordinated path-following of UAVs. To be specific, in the approach adopted a UAV transmits its progress…
Coordinated Path Following of UAVs using Event-Triggered Communication over Networks with Digraph Topologies
This article presents a novel time-coordination algorithm based on event-triggered communication to ensure multiple UAVs progress along their desired paths in coordination with one another. In the proposed algorithm, a U…
Communication-Efficient Topologies for Decentralized Learning with $O(1)$ Consensus Rate
Decentralized optimization is an emerging paradigm in distributed learning in which agents achieve network-wide solutions by peer-to-peer communication without the central server. Since communication tends to be slower t…
Designing Asymmetric Shift Operators for Decentralized Subspace Projection
A large number of applications in wireless sensor networks include projecting a vector of noisy observations onto a subspace dictated by prior information about the field being monitored. In general, accomplishing such a…