arXiv preprint ·
Shrinking-Tube Concentration for Adaptive Markovian Stochastic Approximation
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Optimization & Control
Human-AI-Powered Hypothesis Testing: Cost-Aware Selective AI Scoring and Sequential Human Escalation
MARCEDES: Score-based causal discovery under non-Gaussianity with continuous optimization
Sufficiently Reduced Distributional Regression
Design-Ignoring versus Design-Respecting World Models for Epidemiology
Structured Bayesian Modeling of Dynamic Receptive1 Fields in Salamander Retinal Ganglion Cells
Get the few papers worth your time in Optimization & Control every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.