Bottleneck Communication Delay Minimization for Communication-Efficient Decentralized Learning

For communication-efficient decentralized learning, advanced network (NW) topologies, such as exponential and 1-peer exponential graphs, have been studied under homogeneous communication delays. However, real-world NWs exhibit heterogeneous communication delays, making node assignment optimization crucial for minimizing the Bottleneck Communication Delay (BCD). We propose BTSP-MSR, an approximate method for minimizing BCD on circulant digraphs, including exponential and 1-peer exponential graphs. Leveraging the fact that circulant digraphs can be viewed as a union of (directed) ring graphs, we derive an upper bound on the BCD by combining the ring-graph BCD (BTSP) with a deviation term (MSR). We then construct a solver that sequentially minimizes these two terms. Numerical experiments show that BTSP-MSR consistently reduces BCD across several circulant digraphs with large numbers of nodes. Notably, incorporating the exponential or 1-peer exponential graph enables communication-efficient decentralized learning under heterogeneous delay settings.

Decentralized learning of AI models, such as image classification and language processing models, has been studied to efficiently use many computing resources in places such as data centers. To reduce communication overhead while still sharing information effectively, previous studies have designed network topologies that connect computers sparsely while allowing the trained model to approximate a fully averaged model. However, in real-world data center networks, communication delays between computers differ depending on locations and paths. As a result, the larger maximum communication delay (bottleneck communication delay), the fewer model updates can be performed, reducing the efficiency of decentralized learning. To reduce the bottleneck communication delay, we propose BTSP-MSR, which enables given network topologies used in decentralized learning to be deployed with smaller bottleneck communication delays. BTSP-MSR uses the structure of the network topologies to decompose the problem into two tractable parts and find an approximately optimal assignment before training begins. Experiments based on simulated and real-world data center networks show that BTSP-MSR consistently reduces bottleneck communication delay. By reducing such delays while using suitable network topologies, this work helps make decentralized learning of AI models faster and more practical.