SOURCE-LINKED INTELLIGENCE

Shrinking-Tube Concentration for Adaptive Markovian Stochastic Approximation

arXiv · AI, language, vision and robotics · article · Sep 24, 2026 · UTC

Adaptive algorithms increasingly make decisions while reshaping the dynamics that generate their future data. We establish a shrinking-tube concentration bound for projected stochastic approximation driven by an adaptive Markov chain. The bound guarantees, with high probability, that every iterate after a chosen time remains within a tolerance around the target that tightens over time. The probability of any exit after the chosen time admits a polynomially decaying upper bound, and a matching lower bound shows that its polynomial exponent cannot be improved in general under finite second momen

Read original source ↗ Open in workspace

recordType

paper

region

Global