Split Random Walk Learning

We propose split random-walk learning (SRWL), a communication-efficient decentralized learning algorithm for training a global model over data distributed across the nodes of a connected graph. Unlike conventional random-walk learning, in which the entire model is passed from node to node, SRWL decomposes the model into a representation extractor and a head and propagates them as two coupled sub-walks with different frequencies: the lighter head is communicated at every step, while the heavier extractor performs $\tau$ local updates before being transmitted. We show that, in terms of local update rounds, SRWL retains the $\mathcal{O}(1/\sqrt{T})$ rate of standard random-walk learning, with the cost of splitting confined to lower-order terms governed by the hitting times of the two walks. Experiments on image classification and LLM fine-tuning show that SRWL matches the per-iteration convergence of random-walk learning at substantially lower communication cost and faster wall-clock convergence.