mlsanityData to 7 Oct 2026

On Markov Chain Gradient Descent

arXiv 1809.04216 ↗First posted 12 Sep 2018math.OC stat.MLcited by 63

Not on the map. Why?

Abstract (arXiv)

Stochastic gradient methods are the workhorse (algorithms) of large-scale optimization problems in machine learning, signal processing, and other computational sciences and engineering. This paper studies Markov chain gradient descent, a variant of stochastic gradient descent where the random samples are taken on the trajectory of a Markov chain. Existing results of this method assume convex objectives and a reversible Markov chain and thus have their limitations. We establish new non-ergodic convergence under wider step sizes, for nonconvex problems, and for non-reversible finite-state Markov chains. Nonconvexity makes our method applicable to broader problem classes. Non-reversible finite-state Markov chains, on the other hand, can mix substatially faster. To obtain these results, we introduce a new technique that varies the mixing levels of the Markov chains. The reported numerical results validate our contributions.

Key facts. Cited by 63 papers in the map (data through 7 Oct 2026). First posted on arXiv 12 Sep 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 7; 2022: 15; 2023: 14; 2024: 12; 2025: 6; 2026: 9.

63 papers.

Sort:

By area:

  1. 2023Stochastic Gradient Descent under Markovian Sampling Schemescited by 37
  2. 2022Adapting to Mixing Time in Stochastic Optimization with Markovian Datacited by 35
  3. 2021Concentration of Contractive Stochastic Approximation and Reinforcement Learningcited by 23
  4. 2021Fed-ensemble: Improving Generalization through Model Ensembling in Federated Learningcited by 23
  5. 2021A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learningcited by 20
  6. 2021Simple Stochastic and Online Gradient Descent Algorithms for Pairwise Learningcited by 20
  7. 2022Walk for Learning: A Random Walk Approach for Federated Learning from Heterogeneous Datacited by 18
  8. 2023Federated Learning under Heterogeneous and Correlated Client Availabilitycited by 18
  9. 2022Stability and Generalization for Markov Chain Stochastic Gradient Methodscited by 14
  10. 2023First Order Methods with Markovian Noise: from Acceleration to Variational Inequalitiescited by 14
  11. 2023DIGEST: Fast and Communication Efficient Decentralized Learning with Local Updatescited by 12
  12. 2021Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic Approximation under Markovian Noisecited by 10
38 more
  1. 2023Streaming PCA for Markovian Datacited by 9
  2. 2023Self-Repellent Random Walks on General Graphs -- Achieving Minimal Sampling Variance via Nonlinear Markov Chainscited by 8
  3. 2024Differentially Private Decentralized Learning with Random Walkscited by 8
  4. 2022Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Datacited by 7
  5. 2023Online covariance estimation for stochastic gradient descent under Markovian samplingcited by 7
  6. 2021Learning to Coordinate in Multi-Agent Systems: A Coordinated Actor-Critic Algorithm and Finite-Time Guaranteescited by 6
  7. 2022Markov Chain Score Ascent: A Unifying Framework of Variational Inference with Markovian Gradientscited by 6
  8. 2022Constrained Stochastic Nonconvex Optimization with State-dependent Markov Datacited by 6
  9. 2022Efficiency Ordering of Stochastic Gradient Descentcited by 6
  10. 2023On the Performance of Temporal Difference Learning With Neural Networkscited by 6
  11. 2023On the Global Convergence of Natural Actor-Critic with Two-layer Neural Network Parametrizationcited by 5
  12. 2022Finite-Time Analysis of Asynchronous Q-learning under Diminishing Step-Size from Control-Theoretic Viewcited by 4
  13. 2024Non-asymptotic Analysis of Biased Adaptive Stochastic Approximationcited by 4
  14. 2024Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Datacited by 4
  15. 2024The Entrapment Problem in Random Walk Decentralized Learningcited by 4
  16. 2022On the Global Convergence of Fitted Q-Iteration with Two-layer Neural Network Parametrizationcited by 3
  17. 2022Straggler-Resilient Differentially-Private Decentralized Learningcited by 3
  18. 2023Convergence Analysis of Stochastic Gradient Descent with MCMC Estimatorscited by 3
  19. 2023Mobilizing Personalized Federated Learning in Infrastructure-Less and Heterogeneous Environments via Random Walk Stochastic ADMMcited by 3
  20. 2022Stochastic regularized majorization-minimization with weakly convex and multi-convex surrogatescited by 2
  21. 2022Stochastic Gradient Descent with Dependent Data for Offline Reinforcement Learningcited by 2
  22. 2023Controlling Federated Learning for Covertnesscited by 2
  23. 2024Accelerating Distributed Stochastic Optimization via Self-Repellent Random Walkscited by 2
  24. 2024Self-Regulating Random Walks for Resilient Decentralized Learning on Graphscited by 2
  25. 2024Does Worst-Performing Agent Lead the Pack? Analyzing Agent Dynamics in Unified Distributed SGDcited by 2
  26. 2024Stochastic Gradient Descent with Adaptive Datacited by 2
  27. 2025Random Walk Learning and the Pac-Man Attackcited by 2
  28. 2026High-Probability Bounds for SGD under the Polyak-Lojasiewicz Condition with Markovian Noisecited by 2
  29. 2022Asynchronous Parallel Incremental Block-Coordinate Descent for Decentralized Machine Learningcited by 1
  30. 2022Resonance in Weight Space: Covariate Shift Can Drive Divergence of SGD with Momentumcited by 1
  31. 2022Supervised Dictionary Learning with Auxiliary Covariatescited by 1
  32. 2023Stability-based Generalization Analysis for Mixtures of Pointwise and Pairwise Learningcited by 1
  33. 2023Markov Chain Mirror Descent On Data Federationcited by 1
  34. 2024EMC2: Efficient MCMC Negative Sampling for Contrastive Learning with Global Convergencecited by 1
  35. 2025Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Samplingcited by 1
  36. 2025Beyond Self-Repellent Kernels: History-Driven Target Towards Efficient Nonlinear MCMC on General Graphscited by 1
  37. 2026Self-Creating Random Walks for Decentralized Learning under Pac-Man Attackscited by 1
  38. 2021Markov subsampling based Huber Criterioncited by 0

50 most cited of 63 All 63 (JSON)