mlsanityData to 7 Oct 2026

The Entrapment Problem in Random Walk Decentralized Learning

arXiv 2407.20611 ↗First posted 30 Jul 2024cs.LG cs.DC cs.ITcited by 4

Not on the map. Why?

Abstract (arXiv)

This paper explores decentralized learning in a graph-based setting, where data is distributed across nodes. We investigate a decentralized SGD algorithm that utilizes a random walk to update a global model based on local data. Our focus is on designing the transition probability matrix to speed up convergence. While importance sampling can enhance centralized learning, its decentralized counterpart, using the Metropolis-Hastings (MH) algorithm, can lead to the entrapment problem, where the random walk becomes stuck at certain nodes, slowing convergence. To address this, we propose the Metropolis-Hastings with L'evy Jumps (MHLJ) algorithm, which incorporates random perturbations (jumps) to overcome entrapment. We theoretically establish the convergence rate and error gap of MHLJ and validate our findings through numerical experiments.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 17 of its 39 references that are in the map. First posted on arXiv 30 Jul 2024.

Builds on

17 of 39 references.

References · 17

  1. 2019Advances and Open Problems in Federated Learningcited by 3,021
  2. 2018The Hidden Vulnerability of Distributed Learning in Byzantiumcited by 324
  3. 2013Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithmcited by 132
  4. 2017Network Topology and Communication-Computation Tradeoffs in Decentralized Optimizationcited by 119
  5. 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 112
  6. 2014Stochastic Optimization with Importance Samplingcited by 91
  7. 2018On Markov Chain Gradient Descentcited by 63
  8. 2015Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Surveycited by 44
  9. 2023Stochastic Gradient Descent under Markovian Sampling Schemescited by 37
  10. 2016Importance Sampling for Minibatchescited by 36
  11. 2022Adapting to Mixing Time in Stochastic Optimization with Markovian Datacited by 35
  12. 2018Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimizationcited by 30
5 more
  1. 2022Walk for Learning: A Random Walk Approach for Federated Learning from Heterogeneous Datacited by 18
  2. 2022A principled framework for the design and analysis of token algorithmscited by 17
  3. 2021LocalNewton: Reducing Communication Bottleneck for Distributed Learningcited by 15
  4. 2020Private Weighted Random Walk Stochastic Gradient Descentcited by 14
  5. 2018SUCAG: Stochastic Unbiased Curvature-aided Gradient Method for Distributed Optimizationcited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 2; 2026: 2.

4 papers.

  1. 2025Learning to Help in Multi-Class Settingscited by 2
  2. 2025Random Walk Learning and the Pac-Man Attackcited by 2
  3. 2026Self-Creating Random Walks for Decentralized Learning under Pac-Man Attackscited by 1
  4. 2026Decentralized Learning via Random Walk with Jumpscited by 0