# Walk for Learning: A Random Walk Approach for Federated Learning from Heterogeneous Data

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 54 references that are in the map.
- First posted on arXiv 1 Jun 2022.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [Federated Learning with Non-IID Data](https://mlsanity.com/paper/1806.00582/) (2018)
- [Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization](https://mlsanity.com/paper/2007.07481/) (2020)
- [Adaptive Federated Learning in Resource Constrained Edge Computing Systems](https://mlsanity.com/paper/1804.05271/) (2018)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [On the Convergence of Local Descent Methods in Federated Learning](https://mlsanity.com/paper/1910.14425/) (2019)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [Variance Reduction in SGD by Distributed Importance Sampling](https://mlsanity.com/paper/1511.06481/) (2015)
- [A Proximal Stochastic Gradient Method with Progressive Variance Reduction](https://mlsanity.com/paper/1403.4699/) (2014)
- [On Markov Chain Gradient Descent](https://mlsanity.com/paper/1809.04216/) (2018)
- [Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization](https://mlsanity.com/paper/1804.06568/) (2018)
- [Safe Adaptive Importance Sampling](https://mlsanity.com/paper/1711.02637/) (2017)
- [Private Weighted Random Walk Stochastic Gradient Descent](https://mlsanity.com/paper/2009.01790/) (2020)
- [Improved Sleeping Bandits with Stochastic Actions Sets and Adversarial Rewards](https://mlsanity.com/paper/2004.06248/) (2020)
- [Online Variance Reduction for Stochastic Optimization](https://mlsanity.com/paper/1802.04715/) (2018)
- [Online Learning to Sample](https://mlsanity.com/paper/1506.09016/) (2015)
- [Adaptive Importance Sampling for Finite-Sum Optimization and Sampling with Decreasing Step-Sizes](https://mlsanity.com/paper/2103.12243/) (2021)
- [Stochastic Optimization with Bandit Sampling](https://mlsanity.com/paper/1708.02544/) (2017)
- [Curvature-aided Incremental Aggregated Gradient Method](https://mlsanity.com/paper/1710.08936/) (2017)

## Built on by (most cited first, 19 of 19)

- [Mobility Accelerates Learning: Convergence Analysis on Hierarchical Federated Learning in Vehicular Networks](https://mlsanity.com/paper/2401.09656/) (2024)
- [Decentralized Federated Learning Over Imperfect Communication Channels](https://mlsanity.com/paper/2405.12894/) (2024)
- [Unbiased and Sign Compression in Distributed Learning: Comparing Noise Resilience via SDEs](https://mlsanity.com/paper/2502.17009/) (2025)
- [The Entrapment Problem in Random Walk Decentralized Learning](https://mlsanity.com/paper/2407.20611/) (2024)
- [Resource-Efficient Federated Fine-Tuning Large Language Models for Heterogeneous Data](https://mlsanity.com/paper/2503.21213/) (2025)
- [Random Walk Learning and the Pac-Man Attack](https://mlsanity.com/paper/2508.05663/) (2025)
- [Data-Heterogeneous Hierarchical Federated Learning with Mobility](https://mlsanity.com/paper/2306.10692/) (2023)
- [Limited Communications Distributed Optimization via Deep Unfolded Distributed ADMM](https://mlsanity.com/paper/2309.14353/) (2023)
- [Self-Regulating Random Walks for Resilient Decentralized Learning on Graphs](https://mlsanity.com/paper/2407.11762/) (2024)
- [Does Worst-Performing Agent Lead the Pack? Analyzing Agent Dynamics in Unified Distributed SGD](https://mlsanity.com/paper/2409.17499/) (2024)
- [Self-Creating Random Walks for Decentralized Learning under Pac-Man Attacks](https://mlsanity.com/paper/2601.07674/) (2026)
- [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)
- [Source Anonymity for Private Random Walk Decentralized Learning](https://mlsanity.com/paper/2505.07011/) (2025)
- [Beyond Self-Repellent Kernels: History-Driven Target Towards Efficient Nonlinear MCMC on General Graphs](https://mlsanity.com/paper/2505.18300/) (2025)
- [From Federated Learning to X-Learning: Breaking the Barriers of Decentrality Through Random Walks](https://mlsanity.com/paper/2509.03709/) (2025)
- [Decentralized Learning via Random Walk with Jumps](https://mlsanity.com/paper/2604.12260/) (2026)
- [Joint Optimization for Federated Learning and Transmission over Unreliable Wireless Networks with Heterogeneous Data](https://mlsanity.com/paper/2609.14246/) (2026)
- [Multi-Token Random-Walk Learning via Meeting-Triggered Information Exchange](https://mlsanity.com/paper/2610.14716/) (2026)

## Abstract (arXiv)

We consider the problem of a Parameter Server (PS) that wishes to learn a model that fits data distributed on the nodes of a graph. We focus on Federated Learning (FL) as a canonical application. One of the main challenges of FL is the communication bottleneck between the nodes and the parameter server. A popular solution in the literature is to allow each node to do several local updates on the model in each iteration before sending it back to the PS. While this mitigates the communication bottleneck, the statistical heterogeneity of the data owned by the different nodes has proven to delay convergence and bias the model. In this work, we study random walk (RW) learning algorithms for tackling the communication and data heterogeneity problems. The main idea is to leverage available direct connections among the nodes themselves, which are typically "cheaper" than the communication to the PS. In a random walk, the model is thought of as a "baton" that is passed from a node to one of its neighbors after being updated in each iteration. The challenge in designing the RW is the data heterogeneity and the uncertainty about the data distributions. Ideally, we would want to visit more often nodes that hold more informative data. We cast this problem as a sleeping multi-armed bandit (MAB) to design a near-optimal node sampling strategy that achieves variance-reduced gradient estimates and approaches sub-linearly the optimal sampling strategy. Based on this framework, we present an adaptive random walk learning algorithm. We provide theoretical guarantees on its convergence. Our numerical results validate our theoretical findings and show that our algorithm outperforms existing random walk algorithms.