SPECIAL ISSUE: ARTIFICIAL INTELLIGENCE AND MACHINE LEARNING TECHNOLOGIES

Optimization with Markovian noise: towards optimal rates in strong growth case

S. P. Chebykin^ab, B. I. Prokhorov^ab, A. N. Beznosikov<sup>abcd

a</sup> Basic Research of Artificial Intelligence Laboratory (BRAIn Lab), Москва, Россия
^b Moscow Center for Advanced Studies, Москва, Россия
^c Federated Learning Problems Laboratory, Москва, Россия
^d Innopolis University

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.

Keywords: stochastic optimization, Markovian stochasticity.

UDC: 004.8

Received: 20.08.2025
Accepted: 22.09.2025

DOI: 10.7868/S2686954325070434

Bibliographic databases:

•