# On Markov Chain Gradient Descent

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

## Key facts

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

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

- [Stochastic Gradient Descent under Markovian Sampling Schemes](https://mlsanity.com/paper/2302.14428/) (2023)
- [Adapting to Mixing Time in Stochastic Optimization with Markovian Data](https://mlsanity.com/paper/2202.04428/) (2022)
- [A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning](https://mlsanity.com/paper/2109.14756/) (2021)
- [Concentration of Contractive Stochastic Approximation and Reinforcement Learning](https://mlsanity.com/paper/2106.14308/) (2021)
- [Fed-ensemble: Improving Generalization through Model Ensembling in Federated Learning](https://mlsanity.com/paper/2107.10663/) (2021)
- [Simple Stochastic and Online Gradient Descent Algorithms for Pairwise Learning](https://mlsanity.com/paper/2111.12050/) (2021)
- [Walk for Learning: A Random Walk Approach for Federated Learning from Heterogeneous Data](https://mlsanity.com/paper/2206.00737/) (2022)
- [Federated Learning under Heterogeneous and Correlated Client Availability](https://mlsanity.com/paper/2301.04632/) (2023)
- [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)
- [DIGEST: Fast and Communication Efficient Decentralized Learning with Local Updates](https://mlsanity.com/paper/2307.07652/) (2023)
- [Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic Approximation under Markovian Noise](https://mlsanity.com/paper/2104.01627/) (2021)
- [Streaming PCA for Markovian Data](https://mlsanity.com/paper/2305.02456/) (2023)
- [Self-Repellent Random Walks on General Graphs -- Achieving Minimal Sampling Variance via Nonlinear Markov Chains](https://mlsanity.com/paper/2305.05097/) (2023)
- [Differentially Private Decentralized Learning with Random Walks](https://mlsanity.com/paper/2402.07471/) (2024)
- [Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Data](https://mlsanity.com/paper/2203.15797/) (2022)
- [Online covariance estimation for stochastic gradient descent under Markovian sampling](https://mlsanity.com/paper/2308.01481/) (2023)
- [Learning to Coordinate in Multi-Agent Systems: A Coordinated Actor-Critic Algorithm and Finite-Time Guarantees](https://mlsanity.com/paper/2110.05597/) (2021)
- [Markov Chain Score Ascent: A Unifying Framework of Variational Inference with Markovian Gradients](https://mlsanity.com/paper/2206.06295/) (2022)
- [Constrained Stochastic Nonconvex Optimization with State-dependent Markov Data](https://mlsanity.com/paper/2206.11346/) (2022)
- [Efficiency Ordering of Stochastic Gradient Descent](https://mlsanity.com/paper/2209.07446/) (2022)
- [On the Performance of Temporal Difference Learning With Neural Networks](https://mlsanity.com/paper/2312.05397/) (2023)
- [On the Global Convergence of Natural Actor-Critic with Two-layer Neural Network Parametrization](https://mlsanity.com/paper/2306.10486/) (2023)
- [Non-asymptotic Analysis of Biased Adaptive Stochastic Approximation](https://mlsanity.com/paper/2402.02857/) (2024)
- [Finite-Time Analysis of Asynchronous Q-learning under Diminishing Step-Size from Control-Theoretic View](https://mlsanity.com/paper/2207.12217/) (2022)
- [Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Data](https://mlsanity.com/paper/2405.19463/) (2024)
- [The Entrapment Problem in Random Walk Decentralized Learning](https://mlsanity.com/paper/2407.20611/) (2024)
- [On the Global Convergence of Fitted Q-Iteration with Two-layer Neural Network Parametrization](https://mlsanity.com/paper/2211.07675/) (2022)
- [Straggler-Resilient Differentially-Private Decentralized Learning](https://mlsanity.com/paper/2212.03080/) (2022)
- [Convergence Analysis of Stochastic Gradient Descent with MCMC Estimators](https://mlsanity.com/paper/2303.10599/) (2023)

## 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.