{"ID":2823072,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2601.01160","arxiv_id":"2601.01160","title":"Gradient-Free Approaches is a Key to an Efficient Interaction with Markovian Stochasticity","abstract":"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.","short_abstract":"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 sch...","url_abs":"https://arxiv.org/abs/2601.01160","url_pdf":"https://arxiv.org/pdf/2601.01160v1","authors":"[\"Boris Prokhorov\",\"Semyon Chebykin\",\"Alexander Gasnikov\",\"Aleksandr Beznosikov\"]","published":"2026-01-03T11:27:07Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.LG\"]","methods":"[]","has_code":false}