aiqbench analysis
This paper gives convergence guarantees for stochastic mirror descent when gradients come from a single trajectory of a Markov chain rather than independent samples, a setting common in reinforcement learning and sequential data. It proves an O(T^(-1/2)) rate for the weighted-average iterate without requiring aperiodicity or marginal convergence, and allows unbounded subgradients under Lyapunov-based conditions. Readers building on online or RL-style optimizers should note that the guarantees are theoretical and rest on regularity and moment assumptions that may be hard to verify in practice.
Non-Ergodic Markovian Mirror Descent with Unbounded Noise
arXiv:2610.34433v1 Announce Type: cross 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.
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.
Optimization and Control (math.OC); Machine Learning (cs.LG); Probability (math.PR)
arXiv:2610.34433 [math.OC]
(or arXiv:2610.34433v1 [math.OC] for this version)
https://doi.org/10.48550/arXiv.2610.34433 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 248 words