On the asymptotic behaviour of stochastic processes, with applications to supermartingale convergence, Dvoretzky's approximation theorem, and stochastic quasi-Fejér monotonicity
This work offers incremental improvements by providing quantitative rates for existing stochastic approximation theorems, benefiting researchers in mathematical optimization and probability theory.
The paper tackles the problem of analyzing the asymptotic behavior of stochastic processes under relaxed supermartingale conditions, providing explicit and effective rates of convergence in mean and almost surely, with applications yielding new quantitative versions of theorems like Robbins-Siegmund and Dvoretzky's convergence.
We prove a novel and general result on the asymptotic behavior of stochastic processes which conform to a certain relaxed supermartingale condition. Our result provides quantitative information in the form of an explicit and effective construction of a rate of convergence for this process, both in mean and almost surely, that is moreover highly uniform in that it only depends on very few data of the surrounding objects involved in the iteration. We then apply this result to derive new quantitative versions of well-known concepts and theorems from stochastic approximation, in particular providing effective rates for a variant of the Robbins-Siegmund theorem, Dvoretzky's convergence theorem, as well as the convergence of stochastic quasi-Fejér monotone sequences, the latter of which formulated in a novel and highly general metric context. We utilize the classic and widely studied Robbins-Monro procedure as a template to evaluate our quantitative results and their applicability in greater detail. We conclude by illustrating the breadth of potential further applications with a brief discussion on a variety of other well-known iterative procedures from stochastic approximation. Throughout, we isolate and discuss special cases of our results which allow for the construction of fast, and in particular linear, rates.