Metraipolis › archive › dc_20b35fef1fe5
Shrinking-Tube Concentration for Adaptive Markovian Stochastic Approximation — arXiv:2609.29833
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.29833
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T06:02:59.756Z
- SHA-256 of the archived text
ad3c08ef28470783dde6001127d3a7f9962934de40cddcc2131192c1337eac88- Stable URL of this page
https://metraipolis.com/documento/dc_20b35fef1fe5
How to cite
Shrinking-Tube Concentration for Adaptive Markovian Stochastic Approximation — arXiv:2609.29833 — arXiv (en), https://arxiv.org/abs/2609.29833 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_20b35fef1fe5 (Metraipolis archive dc_20b35fef1fe5, sha256 ad3c08ef28470783dde6001127d3a7f9962934de40cddcc2131192c1337eac88)
BibTeX
@misc{dc20b35fef1fe5,
title = {Shrinking-Tube Concentration for Adaptive Markovian Stochastic Approximation — arXiv:2609.29833},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.29833},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_20b35fef1fe5; sha256 ad3c08ef28470783dde6001127d3a7f9962934de40cddcc2131192c1337eac88},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.29833. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 moments. The result therefore identifies a sharp tradeoff between how quickly the tolerance shrinks and how rapidly the probability of any future exit decreases. We also extend the analysis to recursions with additional martingale-difference noise and predictable bias, showing how growth in the martingale-difference noise scale slows the decay of the exit-probability bound while predictable bias restricts the admissible tube shrinkage. The proof combines backward kernel replacement, a finite-time mean-squared-error bound, and a blockwise maximal first-exit argument. We apply the theory to inventory learning with stockout-dependent demand and fixed stockout costs, and quantify how numerical gradient accuracy affects the all-future reliability of the resulting policies. Tema degli esploratori: statistica e scienza dei dati (retro-catalogo arXiv: annunci del 2026-09-25 in stat.ML). Categorie arXiv: Optimization and Control (math.OC) ; Methodology (stat.ME); Machine Learning (stat.ML). Pagina del lavoro: https://arxiv.org/abs/2609.29833 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-08T05:30:28.922Z dalla pagina https://arxiv.org/catchup/stat.ML/2026-09-25?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).