  We propose near-optimal overlay networks based on $d$-regular expander graphs
to accelerate decentralized federated learning (DFL) and improve its
generalization. In DFL a massive number of clients are connected by an overlay
network, and they solve machine learning problems collaboratively without
sharing raw data. Our overlay network design integrates spectral graph theory
and the theoretical convergence and generalization bounds for DFL. As such, our
proposed overlay networks accelerate convergence, improve generalization, and
enhance robustness to clients failures in DFL with theoretical guarantees.
Also, we present an efficient algorithm to convert a given graph to a practical
overlay network and maintaining the network topology after potential client
failures. We numerically verify the advantages of DFL with our proposed
networks on various benchmark tasks, ranging from image classification to
language modeling using hundreds of clients.
