# Private Weighted Random Walk Stochastic Gradient Descent

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Sep 2020.

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

- [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)
- [DIGEST: Fast and Communication Efficient Decentralized Learning with Local Updates](https://mlsanity.com/paper/2307.07652/) (2023)
- [Bayesian Variational Federated Learning and Unlearning in Decentralized Networks](https://mlsanity.com/paper/2104.03834/) (2021)
- [Efficiency Ordering of Stochastic Gradient Descent](https://mlsanity.com/paper/2209.07446/) (2022)
- [The Entrapment Problem in Random Walk Decentralized Learning](https://mlsanity.com/paper/2407.20611/) (2024)
- [Straggler-Resilient Differentially-Private Decentralized Learning](https://mlsanity.com/paper/2212.03080/) (2022)
- [Decentralized Graph Neural Network for Privacy-Preserving Recommendation](https://mlsanity.com/paper/2308.08072/) (2023)
- [Accelerating Distributed Stochastic Optimization via Self-Repellent Random Walks](https://mlsanity.com/paper/2401.09665/) (2024)
- [Self-Regulating Random Walks for Resilient Decentralized Learning on Graphs](https://mlsanity.com/paper/2407.11762/) (2024)
- [Source Anonymity for Private Random Walk Decentralized Learning](https://mlsanity.com/paper/2505.07011/) (2025)
- [RW-LoRA: Communication-Efficient Decentralized LoRA Fine-Tuning via Random Walks](https://mlsanity.com/paper/2609.00078/) (2026)
- [A Tale of Two Learning Algorithms: Multiple Stream Random Walk and Asynchronous Gossip](https://mlsanity.com/paper/2504.09792/) (2025)
- [Decentralized Learning via Random Walk with Jumps](https://mlsanity.com/paper/2604.12260/) (2026)

## Abstract (arXiv)

We consider a decentralized learning setting in which data is distributed over nodes in a graph. The goal is to learn a global model on the distributed data without involving any central entity that needs to be trusted. While gossip-based stochastic gradient descent (SGD) can be used to achieve this learning objective, it incurs high communication and computation costs, since it has to wait for all the local models at all the nodes to converge. To speed up the convergence, we propose instead to study random walk based SGD in which a global model is updated based on a random walk on the graph. We propose two algorithms based on two types of random walks that achieve, in a decentralized way, uniform sampling and importance sampling of the data. We provide a non-asymptotic analysis on the rate of convergence, taking into account the constants related to the data and the graph. Our numerical results show that the weighted random walk based algorithm has a better performance for high-variance data. Moreover, we propose a privacy-preserving random walk algorithm that achieves local differential privacy based on a Gamma noise mechanism that we propose. We also give numerical results on the convergence of this algorithm and show that it outperforms additive Laplace-based privacy mechanisms.