# Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Apr 2018.

## Built on by (most cited first, 30 of 31)

- [Decentralized Federated Learning: Fundamentals, State of the Art, Frameworks, Trends, and Challenges](https://mlsanity.com/paper/2211.08413/) (2022)
- [Stochastic Gradient Descent under Markovian Sampling Schemes](https://mlsanity.com/paper/2302.14428/) (2023)
- [Fed-ensemble: Improving Generalization through Model Ensembling in Federated Learning](https://mlsanity.com/paper/2107.10663/) (2021)
- [Walk for Learning: A Random Walk Approach for Federated Learning from Heterogeneous Data](https://mlsanity.com/paper/2206.00737/) (2022)
- [Stability and Generalization for Markov Chain Stochastic Gradient Methods](https://mlsanity.com/paper/2209.08005/) (2022)
- [First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities](https://mlsanity.com/paper/2305.15938/) (2023)
- [Efficiency Ordering of Stochastic Gradient Descent](https://mlsanity.com/paper/2209.07446/) (2022)
- [From Noisy Fixed-Point Iterations to Private ADMM for Centralized and Federated Learning](https://mlsanity.com/paper/2302.12559/) (2023)
- [DRACO: Decentralized Asynchronous Federated Learning over Row-Stochastic Wireless Networks](https://mlsanity.com/paper/2406.13533/) (2024)
- [The Entrapment Problem in Random Walk Decentralized Learning](https://mlsanity.com/paper/2407.20611/) (2024)
- [Mobilizing Personalized Federated Learning in Infrastructure-Less and Heterogeneous Environments via Random Walk Stochastic ADMM](https://mlsanity.com/paper/2304.12534/) (2023)
- [A Multi-Token Coordinate Descent Method for Semi-Decentralized Vertical Federated Learning](https://mlsanity.com/paper/2309.09977/) (2023)
- [Review of Mathematical Optimization in Federated Learning](https://mlsanity.com/paper/2412.01630/) (2024)
- [Random Walk Learning and the Pac-Man Attack](https://mlsanity.com/paper/2508.05663/) (2025)
- [Mitigating Privacy-Utility Trade-off in Decentralized Federated Learning via f-Differential Privacy](https://mlsanity.com/paper/2510.19934/) (2025)
- [Self-Regulating Random Walks for Resilient Decentralized Learning on Graphs](https://mlsanity.com/paper/2407.11762/) (2024)
- [Differential Privacy Analysis of Decentralized Gossip Averaging under Varying Threat Models](https://mlsanity.com/paper/2505.19969/) (2025)
- [Self-Creating Random Walks for Decentralized Learning under Pac-Man Attacks](https://mlsanity.com/paper/2601.07674/) (2026)
- [Asynchronous Parallel Incremental Block-Coordinate Descent for Decentralized Machine Learning](https://mlsanity.com/paper/2202.03263/) (2022)
- [Decentralized Entropic Optimal Transport for Distributed Distribution Comparison](https://mlsanity.com/paper/2301.12065/) (2023)
- [Markov Chain Mirror Descent On Data Federation](https://mlsanity.com/paper/2309.14775/) (2023)
- [Sequential Federated Learning in Hierarchical Architecture on Non-IID Datasets](https://mlsanity.com/paper/2408.09762/) (2024)
- [Fedivertex: a Graph Dataset based on Decentralized Social Networks for Trustworthy Machine Learning](https://mlsanity.com/paper/2505.20882/) (2025)
- [Decentralized Optimization with Topology-Independent Communication](https://mlsanity.com/paper/2509.14488/) (2025)
- [Adaptive Stochastic ADMM for Decentralized Reinforcement Learning in Edge Industrial IoT](https://mlsanity.com/paper/2107.00481/) (2021)
- [Stochastic optimization with arbitrary recurrent data sampling](https://mlsanity.com/paper/2401.07694/) (2024)
- [Communication-Efficient and Privacy-Preserving Decentralized Meta-Learning](https://mlsanity.com/paper/2406.13183/) (2024)
- [Decentralized Learning via Random Walk with Jumps](https://mlsanity.com/paper/2604.12260/) (2026)
- [Stability and Generalization for Decentralized Markov SGD](https://mlsanity.com/paper/2605.01701/) (2026)
- [High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependence](https://mlsanity.com/paper/2606.26316/) (2026)

## Abstract (arXiv)

This paper addresses consensus optimization problems in a multi-agent network, where all agents collaboratively find a minimizer for the sum of their private functions. We develop a new decentralized algorithm in which each agent communicates only with its neighbors. State-of-the-art decentralized algorithms use communications between either all pairs of adjacent agents or a random subset of them at each iteration. Another class of algorithms uses a random walk incremental strategy, which sequentially activates a succession of nodes; these incremental algorithms require diminishing step sizes to converge to the solution, so their convergence is relatively slow. In this work, we propose a random walk algorithm that uses a fixed step size and converges faster than the existing random walk incremental algorithms. Our algorithm is also communication efficient. Each iteration uses only one link to communicate the latest information for an agent to another. Since this communication rule mimics a man walking around the network, we call our new algorithm Walkman. We establish convergence for convex and nonconvex objectives. For decentralized least squares, we derive a linear rate of convergence and obtain a better communication complexity than those of other decentralized algorithms. Numerical experiments verify our analysis results.