Scholarlink

Abstract <p>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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年10月1日

查看全文
  • S. Chebykin,
  • B. Prokhorov,
  • A. Beznosikov

摘要

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.