{"id":"arxiv/2601.01160","url":"https://arxiv.org/abs/2601.01160","tags":["math.OC","cs.LG"],"score":0,"title":"Gradient-Free Approaches is a Key to an Efficient Interaction with Markovian Stochasticity","domain":"math.OC","source":"arxiv","authors":["Boris Prokhorov","Semyon Chebykin","Alexander Gasnikov","Aleksandr Beznosikov"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-03","reactions":{}}