Non-Ergodic Markovian Mirror Descent with Unbounded Noise
Abstract
We analyze stochastic mirror descent for minimizing a convex objective expressed as an expectation under the stationary distribution of a Markov chain, using noisy subgradient observations along a single sample path. Through Poisson's equation, we decompose the Markovian noise and control its contribution under regularity and moment conditions that allow the stochastic subgradients and the Poisson solution to be unbounded across the state space. We establish an O(T−1/2) bound on the expected suboptimality gap of the weighted-average iterate for an appropriately chosen step size. The analysis does not require aperiodicity or convergence of the chain's marginal distributions to stationarity. For irreducible finite-state chains, we verify the required conditions on the Poisson solution and derive explicit bounds that quantify the effect of periodicity. For irreducible countable-state chains, we verify the required regularity and moment conditions under a geometric Lyapunov drift condition and suitable growth bounds on the stochastic subgradients.
Related
BibTeX
@misc{biyikoglu2026nonergodic,
title = {{Non-Ergodic Markovian Mirror Descent with Unbounded Noise}},
author = {Yunus Alp Biyikoglu and R. Srikant},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.34433},
eprint = {2610.34433},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.34433},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Non-Ergodic Markovian Mirror Descent with Unbounded Noise
AU - Yunus Alp Biyikoglu
AU - R. Srikant
PY - 2026
DA - 2026/10/25
PB - arXiv
DO - 10.48550/arxiv.2610.34433
UR - https://arxiv.org/abs/2610.34433
AB - We analyze stochastic mirror descent for minimizing a convex objective expressed as an expectation under the stationary distribution of a Markov chain, using noisy subgradient observations along a single sample path. Through Poisson's equation, we decompose the Markovian noise and control its contribution under regularity and moment conditions that allow the stochastic subgradients and the Poisson solution to be unbounded across the state space. We establish an O(T^−1/2) bound on the expected suboptimality gap of the weighted-average iterate for an appropriately chosen step size. The analysis does not require aperiodicity or convergence of the chain's marginal distributions to stationarity. For irreducible finite-state chains, we verify the required conditions on the Poisson solution and derive explicit bounds that quantify the effect of periodicity. For irreducible countable-state chains, we verify the required regularity and moment conditions under a geometric Lyapunov drift condition and suitable growth bounds on the stochastic subgradients.
ER -