Faster Convergence with Less Communication: Broadcast-Based Subgraph
  Sampling for Decentralized Learning over Wireless Networks
Daniel Pérez Herrera Zheng Chen Erik G. Larsson
Consensus-based decentralized stochastic gradient descent (D-SGD) is a widely
adopted algorithm for decentralized training of machine learning models across
networked agents. A crucial part of D-SGD is the consensus-based model
averaging, which heavily relies on information exchange and fusion among the
nodes. Specifically, for consensus averaging over wireless networks,
communication coordination is necessary to determine when and how a node can
access the channel and transmit (or receive) information to (or from) its
neighbors. In this work, we propose $\texttt{BASS}$, a broadcast-based subgraph
sampling method designed to accelerate the convergence of D-SGD while
considering the actual communication cost per iteration. $\texttt{BASS}$
creates a set of mixing matrix candidates that represent sparser subgraphs of
the base topology. In each consensus iteration, one mixing matrix is sampled,
leading to a specific scheduling decision that activates multiple
collision-free subsets of nodes. The sampling occurs in a probabilistic manner,
and the elements of the mixing matrices, along with their sampling
probabilities, are jointly optimized. Simulation results demonstrate that
$\texttt{BASS}$ enables faster convergence with fewer transmission slots
compared to existing link-based scheduling methods. In conclusion, the inherent
broadcasting nature of wireless channels offers intrinsic advantages in
accelerating the convergence of decentralized optimization and learning.