Revisiting 1-peer exponential graph for enhancing decentralized learning efficiency

Yuki Takezawa (Kyoto Univ. / OIST) · Kenta Niwa (NTT Corporation) · Guoqiang Zhang (University of Exeter) · W. Kleijn (Victoria University of Wellington)

$1$-peer exponential graph$k$-peer exponential graphalgorithmic design communication efficiencycommutativityconvergence propertiesdecentralized learningdynamic graphs experimental validation finite-time convergenceglobal averagingmixing matricesnull-cascade graphspectral gap

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 $n$ and the commutativity of mixing matrices remain unexplored. We delve into the principles underlying the $1$-peer exponential graph to explain its efficiency across any $n$ and leverage them to develop new dynamic graphs. We propose two new dynamic graphs: the $k$-peer exponential graph and the null-cascade graph. Notably, the null-cascade graph achieves finite-time convergence for any $n$ while ensuring commutativity. Our experiments confirm the effectiveness of these new graphs, particularly the null-cascade graph, in most test settings.