Multi-Token Random-Walk Learning via Meeting-Triggered Information Exchange
Authors: Taichun Yeh, Xingran Chen
Organizations: Department of Electrical and Computer Engineering, Rutgers University, Piscataway Township, NJ 08854, USA · Engineering Systems and Design Pillar, Singapore University of Technology and Design, Singapore 487372, Singapore
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: Average-Gradient and 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 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). 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, Average-Gradient achieves lower best-token loss but exhibits a trade-off between parallel exploration and gradient interference as N/m decreases.
Figures & tables
Fig. 1 : Percentage improvement relative to single-token-algoritm for N=100 and m=50 .
Fig. 2 : Mean-token and best-token global MSE under Average-Gradient for different values of m , averaged over 20 trials.
Fig. 3 : Mean-token and best-token global MSE under Average-Model for different values of m , averaged over 20 trials.
We study decentralized learning over networks where data are distributed across nodes without a central coordinator. Random walk learning is a token-based approach in which a single model is propagated across the network and updated at each visited node using local data, thereby incurring low communication and computational overheads. In weighted random-walk learning, the transition matrix is designed to achieve a desired sampling distribution, thereby speeding up convergence under data heterogeneity. We show that implementing weighted sampling via the Metropolis-Hastings algorithm can lead to a previously unexplored phenomenon we term entrapment. The random walk may become trapped in a small region of the network, resulting in highly correlated updates and severely degraded convergence. To address this issue, we propose Metropolis-Hastings with Levy jumps, which introduces occasional long-range transitions to restore exploration while respecting local information constraints. We establish a convergence rate that explicitly characterizes the roles of data heterogeneity, network spectral gap, and jump probability, and demonstrate through experiments that MHLJ effectively eliminates entrapment and significantly speeds up decentralized learning.
Zonghong Liu, Matthew Dwyer, Salim El Rouayheb
Department of Electrical and Computer Engineering, Rutgers University, Piscataway, NJ, USA · DEVCOM Army Research Laboratory, Adelphi, MD, USA
Random walk (RW)-based algorithms have long been popular in distributed systems due to low overheads and scalability, with recent growing applications in decentralized learning. However, their reliance on local interactions makes them inherently vulnerable to malicious behavior. In this work, we investigate an adversarial threat that we term the ``Pac-Man'' attack, in which a malicious node probabilistically terminates any RW that visits it. This stealthy behavior gradually eliminates active RWs from the network, effectively halting the learning process without triggering failure alarms. To counter this threat, we propose the Average Crossing (AC) algorithm--a fully decentralized mechanism for duplicating RWs to prevent RW extinction in the presence of Pac-Man. Our theoretical analysis establishes that (i) the RW population remains almost surely bounded under AC and (ii) RW-based stochastic gradient descent remains convergent under AC, even in the presence of Pac-Man, with a quantifiable deviation from the true optimum. Our extensive empirical results on both synthetic and real-world datasets corroborate our theoretical findings. Furthermore, they uncover a phase transition in the extinction probability as a function of the duplication threshold. We offer theoretical insights by analyzing a simplified variant of the AC, which sheds light on the observed phase transition.
Xingran Chen, Parimal Parag, Rohit Bhagat +2
Department of Electrical and Computer Engineering, Rutgers University, Piscataway Township, NJ 08854, USA · Department of Electrical Communication Engineering, Indian Institute of Science, Bangalore, Karnataka 560012, India
Parameter-efficient fine-tuning methods such as LoRA have become a standard approach for adapting large foundation models. Adopting fine-tuning to distributed settings faces several challenges. Most existing distributed LoRA methods rely on centralized aggregation, and gossip-based decentralized LoRA requires repeated synchronization among multiple model copies. Both methods incur significant communication overhead and introduce errors due to simultaneous aggregation of multiple model updates. In this paper, we take a different perspective and propose a random-walk-based LoRA fine-tuning scheme. Instead of maintaining multiple model replicas, a single model token traverses the network and is updated sequentially using local fine-tuning objectives. This design eliminates the need for global synchronization, substantially reduces communication and computation costs, and avoids aggregation errors. We provide rigorous convergence guarantees for non-convex objectives under standard assumptions. Through empirical results on multiple NLP tasks and graph topologies, we show that the proposed method achieves competitive task performance with substantially less communication and computation than gossip-based LoRA.
Xingran Chen, Rohit Bhagat, Ghadir Ayache +3
Engineering Systems and Design Pillar, Singapore University of Technology and Design, Singapore 487372 · Department of Electrical and Computer Engineering, Rutgers University, Piscataway Township, NJ 08854, USA · LinkedIn, New York, NY 10118, USA +2