Gradient-Free Approaches is a Key to an Efficient Interaction with Markovian Stochasticity
Not on the map. Why?
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.
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
29 of 58 references.
References · 29
- 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
- 2017ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Modelscited by 666
- 2017Evolution Strategies as a Scalable Alternative to Reinforcement Learningcited by 574
- 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 250
- 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
- 2013Optimal rates for zero-order convex optimization: the power of two function evaluationscited by 198
- 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
- 2013Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithmcited by 133
- 2015Asynchronous Parallel Stochastic Gradient for Nonconvex Optimizationcited by 116
- 2015An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedbackcited by 111
- 2018Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimizationcited by 111
- 2019Practical Multi-fidelity Bayesian Optimization for Hyperparameter Tuningcited by 93
17 more
- 2019Unified Optimal Analysis of the (Stochastic) Gradient Methodcited by 82
- 2013Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programmingcited by 75
- 2016Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regressioncited by 64
- 2018Structured Evolution with Compact Architectures for Scalable Policy Optimizationcited by 48
- 2023Stochastic Gradient Descent under Markovian Sampling Schemescited by 38
- 2022Adapting to Mixing Time in Stochastic Optimization with Markovian Datacited by 36
- 2019Stochastic Three Points Method for Unconstrained Smooth Minimizationcited by 24
- 2021On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learningcited by 23
- 2020Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Banditscited by 17
- 2020Convergence Rates of Accelerated Markov Gradient Descent with Applications in Reinforcement Learningcited by 15
- 2023First Order Methods with Markovian Noise: from Acceleration to Variational Inequalitiescited by 14
- 2023Gradient-free optimization of highly smooth functions: improved analysis and a new algorithmcited by 12
- 2022The Power of First-Order Smooth Optimization for Black-Box Non-Smooth Problemscited by 9
- 2018An Accelerated Method for Derivative-Free Smooth Stochastic Convex Optimizationcited by 8
- 2018An Accelerated Directional Derivative Method for Smooth Stochastic Convex Optimizationcited by 5
- 2024Methods for Optimization Problems with Markovian Stochasticity and Non-Euclidean Geometrycited by 2
- 2023Markov Chain Mirror Descent On Data Federationcited by 1
Built on by
Not cited yet.