Finite-Time Analysis of Stochastic Gradient Descent under Markov Randomness

Abstract

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.

References in corpus (3)

• SGD and Hogwild! Convergence Without the Bounded Gradients Assumption
• Non-asymptotic Analysis of Biased Stochastic Approximation Scheme
• Convergence Rates of Accelerated Markov Gradient Descent with Applications in Reinforcement Learning

Cited by in corpus (6)

• Distributed TD(0) with Almost No Communication
• A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning
• State Dependent Performative Prediction with Stochastic Approximation
• Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes
• On the Convergence of Consensus Algorithms with Markovian Noise and Gradient Bias
• Score-Aware Policy-Gradient and Performance Guarantees using Local Lyapunov Stability