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

Boris Prokhorov; Semyon Chebykin; Alexander Gasnikov; Aleksandr Beznosikov

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

Boris Prokhorov, Semyon Chebykin, Alexander Gasnikov, Aleksandr Beznosikov

arXivarxiv/2601.01160Jan 3, 2026math.OCscore 0

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…

Source JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2601.01160
curl -X POST /api/v1/records/arxiv/2601.01160/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.01160/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'