# Finite-Time Analysis of Stochastic Gradient Descent under Markov Randomness

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

## Key facts

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

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

- [Concentration of Contractive Stochastic Approximation and Reinforcement Learning](https://mlsanity.com/paper/2106.14308/) (2021)
- [Federated Learning under Heterogeneous and Correlated Client Availability](https://mlsanity.com/paper/2301.04632/) (2023)
- [Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes](https://mlsanity.com/paper/2110.11383/) (2021)
- [Stability and Generalization for Markov Chain Stochastic Gradient Methods](https://mlsanity.com/paper/2209.08005/) (2022)
- [Distributed TD(0) with Almost No Communication](https://mlsanity.com/paper/2305.16246/) (2023)
- [Robust Markov Decision Processes without Model Estimation](https://mlsanity.com/paper/2302.01248/) (2023)
- [Streaming PCA for Markovian Data](https://mlsanity.com/paper/2305.02456/) (2023)
- [Markov Chain Score Ascent: A Unifying Framework of Variational Inference with Markovian Gradients](https://mlsanity.com/paper/2206.06295/) (2022)
- [Efficiency Ordering of Stochastic Gradient Descent](https://mlsanity.com/paper/2209.07446/) (2022)
- [Non-asymptotic Analysis of Biased Adaptive Stochastic Approximation](https://mlsanity.com/paper/2402.02857/) (2024)
- [Process-Tensor Tomography of SGD: Measuring Non-Markovian Memory via Back-Flow of Distinguishability](https://mlsanity.com/paper/2601.16563/) (2026)
- [High-Probability Bounds for SGD under the Polyak-Lojasiewicz Condition with Markovian Noise](https://mlsanity.com/paper/2603.14514/) (2026)
- [Resonance in Weight Space: Covariate Shift Can Drive Divergence of SGD with Momentum](https://mlsanity.com/paper/2203.11992/) (2022)
- [Distributed TD(0) with Almost No Communication](https://mlsanity.com/paper/2104.07855/) (2021)
- [Enhancing Stochastic Optimization for Statistical Efficiency Using ROOT-SGD with Diminishing Stepsize](https://mlsanity.com/paper/2407.10955/) (2024)
- [Markov Chain Gradient Descent in Hilbert Spaces](https://mlsanity.com/paper/2410.08361/) (2024)
- [GRAB: An LLM-Inspired Sequence-First Click-Through Rate Prediction Modeling Paradigm](https://mlsanity.com/paper/2602.01865/) (2026)
- [High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependence](https://mlsanity.com/paper/2606.26316/) (2026)

## Abstract (arXiv)

Motivated by broad applications in reinforcement learning and machine learning, this paper considers the popular stochastic gradient descent (SGD) when the gradients of the underlying objective function are sampled from Markov processes. This Markov sampling leads to the gradient samples being biased and not independent. The existing results for the convergence of SGD under Markov randomness are often established under the assumptions on the boundedness of either the iterates or the gradient samples. Our main focus is to study the finite-time convergence of SGD for different types of objective functions, without requiring these assumptions. We show that SGD converges nearly at the same rate with Markovian gradient samples as with independent gradient samples. The only difference is a logarithmic factor that accounts for the mixing time of the Markov chain.