This paper delves into stochastic optimization problems that involve Markovian noise. We present a unified approach for the theoretical analysis of first-order gradient methods for stochastic optimization and variational inequalities. Our approach covers scenarios for both non-convex and strongly convex minimization problems. To achieve an optimal (linear) dependence on the mixing time of the underlying noise sequence, we use the randomized batching scheme, which is based on the multilevel Monte Carlo method. Moreover, our technique allows us to eliminate the limiting assumptions of previous research on Markov noise, such as the need for a bounded domain and uniformly bounded stochastic gradients. Our extension to variational inequalities under Markovian noise is original. Additionally, we provide lower bounds that match the oracle complexity of our method in the case of strongly convex optimization problems.

该论文提出了一种针对马尔可夫噪声的随机优化问题的优化方法，使用随机批处理方案和多层蒙特卡洛方法，在非凸和强凸情况下实现对梯度方法和变分不等式的统一理论分析。此外，该研究消除了以前关于马尔可夫噪声的限制假设，并提供了与优化问题的强凸情况相匹配的下界。

具有马尔可夫噪声的一阶方法：从加速到变分不等式