Revisiting 1-peer exponential graph for enhancing decentralized learning efficiency

For communication-efficient decentralized learning, it is essential to employ dynamic graphs designed to improve the expected spectral gap by reducing deviations from global averaging. The 1-peer exponential graph demonstrates its finite-time convergence property-achieved by maximizing the expected spectral gap-but only when the number of nodes n is a power of two. However, its efficiency across any nand the commutativity of mixing matrices remain unexplored. We delve into the principles underlying the 1-peer exponential graph to explain its efficiency across any nand leverage them to develop new dynamic graphs. We propose two new dynamic graphs: the k-peer exponential graph and the nullcascade graph. Notably, the null-cascade graph achieves finite-time convergence for any nwhile ensuring commutativity. Our experiments confirm the effectiveness of these new graphs, particularly the null-cascade graph, in most test settings.