Multi-Token Random-Walk Learning via Meeting-Triggered Information Exchange

arXiv:2610.14716v1 Announce Type: new 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: extsc{Average-Gradient} and extsc{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). extsc{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, extsc{Average-Gradient} achieves lower best-token loss but exhibits a trade-off between parallel exploration and gradient interference as N/m decreases.

Related

• A Tale of Two Learning Algorithms: Multiple Stream Random Walk and Asynchronous Gossip
• Decentralized Learning via Random Walk with Jumps
• Decentralized SGD under Heavy-Tailed Noise: Optimal Convergence Rates and the Role of Gradient Clipping

Source: arXiv cs.LG | 2026-10-14