Improved Lower Bounds for First-order Stochastic Non-convex Optimization under Markov Sampling

Unlike its vanilla counterpart with i.i.d. samples, stochastic optimization with Markovian sampling allows the sampling scheme following a Markov chain. This problem encompasses various applications that range from asynchronous distributed optimization to reinforcement learning. In this work, we lower bound the sample complexity of finding ϵ-approximate critical solutions for any first-order methods when sampling is Markovian. We show that for samples drawn from stationary Markov processes with countable state space, any algorithm that accesses smooth, non-convex functions through queries to a stochastic gradient oracle, requires at least Ω(ϵ -4 ) samples. Moreover, for finite Markov chains, we show a Ω(ϵ -2 ) lower bound and propose a new algorithm, called MaC-SAGE, that is proved to (nearly) match our lower bound.