Finite-Time Analysis of Stochastic Gradient Descent under Markov
  Randomness
  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.
