What question did this study set out to answer?

The aim is to improve understanding of optimization under Markovian noise in stochastic settings.

March 21, 2026Open Access

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

SCS. ChebykinZhejiang Lab BPB. ProkhorovZhejiang Lab ABAleksandr BeznosikovAIRI - Artificial Intelligence Research Institute

Key Points

The aim is to improve understanding of optimization under Markovian noise in stochastic settings.
Analyzed the Accelerated Gradient Descent algorithm in the presence of Markovian noise
Examined conditions of strong convexity
Established a lower bound based on mixing time and noise level
Showed that Markovianity has negligible effects in low-noise scenarios
Derived near-optimal rates for the algorithm in the strong growth case
Identified how the mixing time influences optimization performance

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.

Ask AI

Helpful

Bookmark

View Full Paper