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

arXiv: https://arxiv.org/abs/2601.01160 · HTML: https://mlsanity.com/paper/2601.01160/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 58 references that are in the map.
- First posted on arXiv 3 Jan 2026.

## Builds on (most cited first, 29 of 29)

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models](https://mlsanity.com/paper/1708.03999/) (2017)
- [Evolution Strategies as a Scalable Alternative to Reinforcement Learning](https://mlsanity.com/paper/1703.03864/) (2017)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization](https://mlsanity.com/paper/1506.08272/) (2015)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1805.10367/) (2018)
- [Practical Multi-fidelity Bayesian Optimization for Hyperparameter Tuning](https://mlsanity.com/paper/1903.04703/) (2019)
- [Unified Optimal Analysis of the (Stochastic) Gradient Method](https://mlsanity.com/paper/1907.04232/) (2019)
- [Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming](https://mlsanity.com/paper/1310.3787/) (2013)
- [Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression](https://mlsanity.com/paper/1602.05419/) (2016)
- [Structured Evolution with Compact Architectures for Scalable Policy Optimization](https://mlsanity.com/paper/1804.02395/) (2018)
- [Stochastic Gradient Descent under Markovian Sampling Schemes](https://mlsanity.com/paper/2302.14428/) (2023)
- [Adapting to Mixing Time in Stochastic Optimization with Markovian Data](https://mlsanity.com/paper/2202.04428/) (2022)
- [Stochastic Three Points Method for Unconstrained Smooth Minimization](https://mlsanity.com/paper/1902.03591/) (2019)
- [On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/2102.00185/) (2021)
- [Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits](https://mlsanity.com/paper/2006.07862/) (2020)
- [Convergence Rates of Accelerated Markov Gradient Descent with Applications in Reinforcement Learning](https://mlsanity.com/paper/2002.02873/) (2020)
- [First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities](https://mlsanity.com/paper/2305.15938/) (2023)
- [Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm](https://mlsanity.com/paper/2306.02159/) (2023)
- [The Power of First-Order Smooth Optimization for Black-Box Non-Smooth Problems](https://mlsanity.com/paper/2201.12289/) (2022)
- [An Accelerated Method for Derivative-Free Smooth Stochastic Convex Optimization](https://mlsanity.com/paper/1802.09022/) (2018)
- [An Accelerated Directional Derivative Method for Smooth Stochastic Convex Optimization](https://mlsanity.com/paper/1804.02394/) (2018)
- [Methods for Optimization Problems with Markovian Stochasticity and Non-Euclidean Geometry](https://mlsanity.com/paper/2408.01848/) (2024)
- [Markov Chain Mirror Descent On Data Federation](https://mlsanity.com/paper/2309.14775/) (2023)

## Abstract (arXiv)

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 τ of the underlying noise sequence is less than the dimension of the problem d, the convergence estimates of our method do not depend on τ. 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.