First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities
This provides improved theoretical guarantees for optimization problems affected by correlated noise, which is incremental but addresses limitations in prior work.
The paper tackles stochastic optimization with Markovian noise by developing a unified theoretical framework for first-order gradient methods that achieves optimal linear dependence on mixing time using randomized batching, and extends this to variational inequalities while removing previous assumptions like bounded domains.
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.