First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities

Stochastic gradient methods are an essential ingredient for solving various optimization problems, with a wide range of applications in various fields such as machine learning [Goodfellow et al., 2014, 2016], empirical risk minimization problems [Van der Vaart, 2000], and reinforcement learning [Sutton and Barto, 2018, Schulman et al., 2015, Mnih et al., 2015]. Various stochastic gradient descent methods (SGD) and their accelerated versions [Nesterov, 1983, Ghadimi and Lan, 2013] have been extensively studied under different statistical frameworks [Dieuleveut et al., 2017, Vaswani et al., 2019a]. The standard assumption for stochastic optimization algorithms is to consider independent and identically distributed noise variables. However, the growing usage of stochastic optimization methods in reinforcement learning [Bhandari et al., 2018, Srikant and Ying, 2019, Durmus et al., 2021] and distributed optimization [Lopes and Sayed, 2007, Dimakis et al., 2010, Mao et al., 2020] has led to increased interest in problems with Markovian noise. Despite this, existing theoretical works that consider Markov noise have significant limitations, and their analysis often results in suboptimal finite-time error bounds. Our research aims to fill the gap in the existing literature on the first-order Markovian setting. By focusing on uniformly geometrically ergodic Markov chains, we obtain finite-time complexity bounds for achieving ε-accurate solutions that scale linearly with the mixing time of the underlying Markov chain. Our approach is based on careful applications of randomized batch size schemes and provides a unified view on both non-convex and strongly convex minimization problems, as well as variational inequalities.