Stochastic Mirror Descent under Iterate-Dependent Markov Noise: Analysis in the Asymptotic and Finite Time Regimes
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911687686225920 |
|---|---|
| author | Paul, Anik Kumar Bhatnagar, Shalabh |
| author_facet | Paul, Anik Kumar Bhatnagar, Shalabh |
| contents | We study a stochastic optimization problem in which the sampling distribution depends on the decision variable, and the available samples are generated through an iterate-dependent Markov chain. Such settings arise naturally in problems with decision-dependent uncertainty; however, they introduce bias and temporal dependence, which render standard techniques developed for i.i.d.\ noise inapplicable. In this work, we analyze the stochastic mirror descent algorithm under iterate-dependent Markov noise. We first establish almost sure convergence for both convex and non-convex problems under the mild assumption of Lipschitz continuity of the objective function, without requiring differentiability. We then derive finite-time concentration bounds for smooth objectives. In the convex setting, the resulting sample complexity matches the classical rate of stochastic mirror descent under i.i.d.\ noise. In the non-convex setting, we obtain a sample complexity bound in terms of the norm of the Riemannian gradient over the probability simplex. Overall, our results establish a unified convergence framework for stochastic mirror descent with state-dependent Markov noise, and highlight its behavior in both convex and non-convex regimes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_15538 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Stochastic Mirror Descent under Iterate-Dependent Markov Noise: Analysis in the Asymptotic and Finite Time Regimes Paul, Anik Kumar Bhatnagar, Shalabh Optimization and Control Systems and Control We study a stochastic optimization problem in which the sampling distribution depends on the decision variable, and the available samples are generated through an iterate-dependent Markov chain. Such settings arise naturally in problems with decision-dependent uncertainty; however, they introduce bias and temporal dependence, which render standard techniques developed for i.i.d.\ noise inapplicable. In this work, we analyze the stochastic mirror descent algorithm under iterate-dependent Markov noise. We first establish almost sure convergence for both convex and non-convex problems under the mild assumption of Lipschitz continuity of the objective function, without requiring differentiability. We then derive finite-time concentration bounds for smooth objectives. In the convex setting, the resulting sample complexity matches the classical rate of stochastic mirror descent under i.i.d.\ noise. In the non-convex setting, we obtain a sample complexity bound in terms of the norm of the Riemannian gradient over the probability simplex. Overall, our results establish a unified convergence framework for stochastic mirror descent with state-dependent Markov noise, and highlight its behavior in both convex and non-convex regimes. |
| title | Stochastic Mirror Descent under Iterate-Dependent Markov Noise: Analysis in the Asymptotic and Finite Time Regimes |
| topic | Optimization and Control Systems and Control |
| url | https://arxiv.org/abs/2605.15538 |