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.
Complexity Lower Bounds
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
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.