# Decentralized Learning via Random Walk with Jumps

arXiv: https://arxiv.org/abs/2604.12260 · HTML: https://mlsanity.com/paper/2604.12260/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 50 references that are in the map.
- First posted on arXiv 14 Apr 2026.

## Builds on (most cited first, 22 of 22)

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [The Hidden Vulnerability of Distributed Learning in Byzantium](https://mlsanity.com/paper/1802.07927/) (2018)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization](https://mlsanity.com/paper/1709.08765/) (2017)
- [Stochastic Optimization with Importance Sampling](https://mlsanity.com/paper/1401.2753/) (2014)
- [On Markov Chain Gradient Descent](https://mlsanity.com/paper/1809.04216/) (2018)
- [Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Survey](https://mlsanity.com/paper/1507.01030/) (2015)
- [A Survey on Heterogeneous Federated Learning](https://mlsanity.com/paper/2210.04505/) (2022)
- [Stochastic Gradient Descent under Markovian Sampling Schemes](https://mlsanity.com/paper/2302.14428/) (2023)
- [Importance Sampling for Minibatches](https://mlsanity.com/paper/1602.02283/) (2016)
- [Adapting to Mixing Time in Stochastic Optimization with Markovian Data](https://mlsanity.com/paper/2202.04428/) (2022)
- [Decentralized Gradient Tracking with Local Steps](https://mlsanity.com/paper/2301.01313/) (2023)
- [Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization](https://mlsanity.com/paper/1804.06568/) (2018)
- [Walk for Learning: A Random Walk Approach for Federated Learning from Heterogeneous Data](https://mlsanity.com/paper/2206.00737/) (2022)
- [A principled framework for the design and analysis of token algorithms](https://mlsanity.com/paper/2205.15015/) (2022)
- [LocalNewton: Reducing Communication Bottleneck for Distributed Learning](https://mlsanity.com/paper/2105.07320/) (2021)
- [Private Weighted Random Walk Stochastic Gradient Descent](https://mlsanity.com/paper/2009.01790/) (2020)
- [DIGEST: Fast and Communication Efficient Decentralized Learning with Local Updates](https://mlsanity.com/paper/2307.07652/) (2023)
- [Asynchronous Adaptation and Learning over Networks --- Part I: Modeling and Stability Analysis](https://mlsanity.com/paper/1312.5434/) (2013)
- [SUCAG: Stochastic Unbiased Curvature-aided Gradient Method for Distributed Optimization](https://mlsanity.com/paper/1803.08198/) (2018)
- [The Entrapment Problem in Random Walk Decentralized Learning](https://mlsanity.com/paper/2407.20611/) (2024)

## Abstract (arXiv)

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.