# A quantitative Robbins-Siegmund theorem

arXiv: https://arxiv.org/abs/2410.15986 · HTML: https://mlsanity.com/paper/2410.15986/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 30 references that are in the map.
- First posted on arXiv 21 Oct 2024.

## Builds on (most cited first, 6 of 6)

- [Averaging Stochastic Gradient Descent on Riemannian Manifolds](https://mlsanity.com/paper/1802.09128/) (2018)
- [On Almost Sure Convergence Rates of Stochastic Gradient Methods](https://mlsanity.com/paper/2202.04295/) (2022)
- [Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applications](https://mlsanity.com/paper/2312.02828/) (2023)
- [A Unified Convergence Theorem for Stochastic Optimization Methods](https://mlsanity.com/paper/2206.03907/) (2022)
- [Convergence of sequences: a survey](https://mlsanity.com/paper/2111.11374/) (2021)
- [A computational study of a class of recursive inequalities](https://mlsanity.com/paper/2207.14559/) (2022)

## Built on by (most cited first, 4 of 4)

- [Asymptotic regularity of a generalised stochastic Halpern scheme](https://mlsanity.com/paper/2411.04845/) (2024)
- [Statistical Inference for Online Algorithms](https://mlsanity.com/paper/2505.17300/) (2025)
- [An abstract effective convergence theorem for stochastic processes, with applications to stochastic approximation](https://mlsanity.com/paper/2504.12922/) (2025)
- [Mean-square and sublinear convergence of a stochastic proximal point algorithm in metric spaces of nonpositive curvature](https://mlsanity.com/paper/2510.10697/) (2025)

## Abstract (arXiv)

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 metastability in the sense of Tao. Our proof involves a metastable analogue of Doob's theorem for L1-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.