Gradient-Free Approaches is a Key to an Efficient Interaction with Markovian Stochasticity

This paper deals with stochastic optimization problems involving Markovian noise with a zero-order oracle. We present and analyze a novel derivative-free method for solving such problems in strongly convex smooth and non-smooth settings with both one-point and two-point feedback oracles. Using a randomized batching scheme, we show that when mixing time $\tau$ of the underlying noise sequence is less than the dimension of the problem $d$, the convergence estimates of our method do not depend on $\tau$. This observation provides an efficient way to interact with Markovian stochasticity: instead of invoking the expensive first-order oracle, one should use the zero-order oracle. Finally, we complement our upper bounds with the corresponding lower bounds. This confirms the optimality of our results.

This paper is in the field of stochastic optimization, where the goal is, given an objective function, to find a combination of arguments minimizing its output. Traditional algorithms for solving this problem assume access to an approximation of this function’s gradient. The approximation is assumed to be “noisy”, randomly deviating from the true gradient, like flipping a coin and adding plus or minus 1 to the result. In the real world those assumptions do not always hold: for example interacting with live, stateful systems, like financial markets, may introduce correlated noise. In the coin analogy, imagine that after flipping heads\tails you would have a 90% chance to flip heads\tails again. Prior research showed this setting to be much harder, because you are essentially forced to wait out the resulting short-term biases. Additionally, as the gradient may also be inaccessible due to limited computational resources or black-box nature of the objective, we assume that only the function value may be calculated. We developed an algorithm to cope with these more constrained assumptions, analyzed its performance and showed its optimality. The surprising result is that gradient-free algorithms suffer from the correlation in noise much less compared to gradient-based ones.