High-probability Convergence of Gradient Methods under Markovian Stochasticity

Markovian stochasticity naturally arises in many modern learning problems, including optimization with dependent data streams and reinforcement learning. Despite extensive research on convergence of stochastic gradient methods under such stochasticity, high-probability convergence remains largely unexplored. To close this gap, we provide the first high-probability convergence guarantees for gradient-based methods under Markovian stochasticity. We study SGD with a specialized mini-batch-based gradient estimator and establish high-probability convergence results in the non-convex setting under the classical bounded stochasticity assumption, and further extend the analysis to a weaker bounded-variance assumption by incorporating gradient clipping, yielding convergence guarantees for accelerated stochastic gradient descent in the convex setting. For both methods, we characterize the oracle complexity via a concentration inequality that explicitly captures the effect of Markovian dependence on the resulting convergence rates.