A quantitative Robbins-Siegmund theorem
This work offers incremental improvements for researchers in stochastic optimization by enabling quantitative convergence analysis across algorithms relying on the Robbins-Siegmund theorem.
The paper tackles the problem of quantifying convergence in stochastic optimization by providing a quantitative version of the Robbins-Siegmund theorem, establishing bounds on locating metastable regions with a general methodology for stochastic processes reducible to supermartingales.
The Robbins-Siegmund theorem is one of the most important results in stochastic optimization, where it is widely used to prove the convergence of stochastic algorithms. We provide a quantitative version of the theorem, establishing a bound on how far one needs to look in order to locate a region of \emph{metastability} in the sense of Tao. Our proof involves a metastable analogue of Doob's theorem for $L_1$-supermartingales along with a series of technical lemmas that make precise how quantitative information propagates through sums and products of stochastic processes. In this way, our paper establishes a general methodology for finding metastable bounds for stochastic processes that can be reduced to supermartingales, and therefore for obtaining quantitative convergence information across a broad class of stochastic algorithms whose convergence proof relies on some variation of the Robbins-Siegmund theorem. We conclude by discussing how our general quantitative result might be used in practice.