arXiv preprint ·
Multi-Token Random-Walk Learning via Meeting-Triggered Information Exchange
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning
PotentialEP: Backprop-Free Training of CIFAR-Scale Generative Models via Equilibrium Propagation
Explicit Bounds on Hoffman Constants for Sparse Polyhedral Regularizers
Coarse-Graining Recursive Expert Computation: Continuation-Relative Interfaces and Failure Modes
EvolvAttack: Backdooring self Evolving VLM Agents
Scaling Laws for Multimodal Data Mixtures
Get the few papers worth your time in Machine Learning every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.