{"id":"arxiv/2609.29833","url":"https://arxiv.org/abs/2609.29833","tags":["math.OC","stat.ME","stat.ML"],"score":0,"title":"Shrinking-Tube Concentration for Adaptive Markovian Stochastic Approximation","domain":"math.OC","source":"arxiv","authors":["Jin Li","Ye Luo","Xiaowei Zhang"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-24","reactions":{}}