Iterative stochastic algorithms such as stochastic gradient descent are usually analyzed at a fixed iteration count, which does not justify stopping at a data-dependent time. Anytime-valid envelopes address this by providing error bounds that hold uniformly over time, but deterministic versions tend to be too conservative, and existing data-adaptive constructions are derived case by case, coupling a specific algorithm to a specific noise model and boundary construction.

The paper proposes a general recipe for constructing data-adaptive anytime-valid boundaries for a large class of iterative algorithms. The authors observe that performance measures of many such algorithms satisfy a one-step recursion, reducing the entire error analysis to a single requirement: time-uniform concentration for predictably weighted sums of noise. They formalize this through a strongly adapted sub-ψ condition and derive off-the-shelf boundary constructions using continuous and discrete mixtures, stitching, and product betting martingales.

The framework is demonstrated on stochastic gradient descent, temporal difference learning, and Bures-Wasserstein SGD. For SGD, the authors report that their approach either recovers or significantly sharpens every existing envelope they are aware of. The paper also includes explicit implementation details and numerical experiments, making the method ready for practical use.