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

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: textscAverage-Gradient and textscAverage-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 m2 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). textscAverage-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, textscAverage-Gradient achieves lower best-token loss but exhibits a trade-off between parallel exploration and gradient interference as N/m decreases.