Multiple tokens improve decentralized learning with different exchange methods
Multi-Token Random-Walk Learning via Meeting-Triggered Information Exchange
Machine Learning
Summary
Learning across networks can happen by passing around a single token carrying information, but carrying multiple tokens could allow faster and better learning. The authors explore how multiple tokens sharing updates when they meet can speed up learning, depending on how they combine their information. They find that combining full models leads to more consistent average performance, while combining gradients tends to produce the best single-token results but with a trade-off as networks get crowded. Their work quantifies how much faster learning can scale with more tokens in different scenarios.
What this means in practice
- •For distributed system engineers: Optimize token-based message passing strategies to improve learning speed on large decentralized networks.
- •For machine learning platform developers: Design distributed training frameworks that balance gradient and model averaging for different network-to-token ratios to enhance robustness and convergence rates.
Authors
Taichun Yeh, Xingran Chen
Abstract
Random walk (RW)-based algorithms are widely used in decentralized learning due to their low communication overhead and scalability. While most existing methods rely on a single token, multiple tokens can explore the network in parallel and exchange information upon meeting. However, the fundamental benefits of such meeting-triggered interactions remain unclear. In this work, we investigate multi-token RW learning under two information exchange policies: \textsc{Average-Gradient} and \textsc{Average-Model}, which average stochastic gradients and updated models, respectively, when tokens meet. We establish iteration complexity lower bounds for non-convex, convex, and strongly convex objectives on complete graphs, which apply to both exchange policies. Compared with single-token RW learning, the scaling factor in these bounds is reduced by a factor of $m^2$ for non-convex and convex objectives, and by an exponentially in $m$ for strongly convex objectives, where $m$ denotes the number of tokens. Numerical experiments reveal distinct behaviors of the two policies under two performance criteria: mean-token loss (the average loss across all tokens) and best-token loss (the minimum loss across all tokens). \textsc{Average-Model} achieves lower mean-token loss and is relatively insensitive to the network-to-token ratio $N/m$, where $N$ is the number of nodes. In contrast, \textsc{Average-Gradient} achieves lower best-token loss but exhibits a trade-off between parallel exploration and gradient interference as $N/m$ decreases.