Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2601.01160 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909980937945088 |
|---|---|
| author | Prokhorov, Boris Chebykin, Semyon Gasnikov, Alexander Beznosikov, Aleksandr |
| author_facet | Prokhorov, Boris Chebykin, Semyon Gasnikov, Alexander Beznosikov, Aleksandr |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_01160 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Gradient-Free Approaches is a Key to an Efficient Interaction with Markovian Stochasticity Prokhorov, Boris Chebykin, Semyon Gasnikov, Alexander Beznosikov, Aleksandr Optimization and Control Machine Learning 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. |
| title | Gradient-Free Approaches is a Key to an Efficient Interaction with Markovian Stochasticity |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2601.01160 |