Doklady Mathematics General Mathematics

Optimization with Markovian Noise: Towards Optimal Rates in Strong Growth Case

S. Chebykin, B. Prokhorov, A. Beznosikov
Springer Nature · 2025-10-01 · DOI 10.1134/s1064562425700462

Abstract

Abstract This paper investigates stochastic optimization problems under Markovian noise and the strong growth condition, motivated by overparameterized ML models. We present an improved analysis of the Accelerated Gradient Descent algorithm from [1] in the strongly convex case, showing that in low-noise regimes, the effect of Markovianity can be ignored. Furthermore, we derive the first lower bound that simultaneously depends on the Markov chain’s mixing time and the problem’s noise level, establishing the near-optimality of our results.

Read at publisher →