A General Recipe: Building Data-Adaptive Anytime-Valid Bounds for Iterative Algorithms

Why do iterative algorithms need "anytime-valid" bounds?

Most convergence guarantees for iterative stochastic algorithms (such as stochastic gradient descent and temporal-difference learning) are stated for a fixed number of iterations. This means that when you decide in practice, based on how the training is going, when to stop, these theoretical guarantees no longer apply—they cannot justify the decision to "stop at iteration T."

Recent work has begun to construct "anytime-valid envelopes" that allow stopping at data-dependent times while preserving statistical validity. But the problem is that deterministic bounds tend to be too conservative and are barely usable in practice for stopping decisions, while existing data-adaptive bounds are derived case by case—each algorithm needs its own noise model and bound construction, so there is no generality.

A new paper attempts to change this by proposing a general recipe for constructing data-adaptive anytime-valid bounds for a large class of iterative algorithms.

An anytime-valid envelope is a special case of anytime-valid inference in statistics. Traditional confidence intervals or convergence guarantees are typically valid only for a pre-fixed sample size or number of iterations; once you decide when to stop based on observed data, using a fixed-sample-size guarantee leads to selection bias, and the actual coverage falls below the nominal level. An anytime-valid bound requires that, for any data-dependent stopping time τ, the bound still holds with probability at least 1-α at τ, i.e., it satisfies time-uniform coverage. This allows researchers to monitor the bound continuously during training and stop at any time without breaking statistical validity. In sequential analysis, such bounds are often implemented by constructing nonnegative supermartingales and applying Ville's inequality, which is fundamentally different from concentration inequalities at a fixed sample size.

Core insight: reduce error analysis to a one-step recursion

The key observation of the paper is that the performance measure of many iterative algorithms satisfies a one-step recursion. That is, the error at step t can be expressed as a function of the error at step t-1 and the current noise term.

Once this recursive structure is identified, the entire error analysis reduces to a general requirement: time-uniform concentration for predictably weighted sums of noise. In other words, as long as the tail behavior of the accumulated noise can be controlled, an effective error bound can be provided for the algorithm.

The significance of this reduction lies in decoupling: the algorithm analysis is responsible for deriving the one-step recursion, while the bound construction is responsible for handling the noise concentration. The two can be carried out independently and then combined.

A predictably weighted sum of noise is a random sum of the form Σ_{i=1}^t w_i ε_i, where the weight w_i is determined before each step i based on historical information (hence "predictable"), and the noise ε_i has conditional mean zero or some conditional symmetry given the past information. In the analysis of iterative algorithms, error recursions often produce this structure: the current error equals a contraction term of the past error plus the current noise term multiplied by a coefficient that depends on the historical state. Since this coefficient is determined before the noise is realized, the noise sum has predictable weights. Controlling the tail probability of such sums is far more difficult than controlling sums of independent and identically distributed noise, because the weights are correlated with the noise history and the bound must hold simultaneously for all t. Time-uniform concentration inequalities (e.g., constructed via mixing martingales or betting) are designed exactly for this: they allow the weights to adapt to the history while guaranteeing validity at any stopping time.

Formal tool: the strongly adapted sub-ψ condition

To rigorously characterize the above requirement, the authors introduce the strongly adapted sub-ψ condition. This condition captures the concentration properties of the noise sequence under an adapted filtration, so that time-uniform concentration inequalities can be applied to predictably weighted sums.

On this basis, the paper provides several off-the-shelf bound construction methods:

• Continuous mixtures: obtain adaptivity by mixing bounds with different parameters
• Discrete mixtures: mix over a discrete grid
• Stitching: stitch bounds for different time intervals into a global bound
• Product betting martingales: construct bounds using betting strategies

These construction methods provide flexible choices for different scenarios.

The sub-ψ condition originates from martingale concentration inequality theory and is used to characterize the tail behavior of random variables. If a random variable X satisfies the sub-ψ condition, its moment-generating function is bounded by a bound controlled by a ψ function; common special cases include sub-Gaussian (ψ(x)=x^2/2) and sub-exponential (ψ(x) is x^2 near the origin and linear in the tail). The strongly adapted version further requires that this condition hold at every time step under an adapted filtration, i.e., the conditional moment-generating function is controlled by ψ. This allows researchers to construct exponential supermartingales and apply Ville's inequality to obtain time-uniform bounds. Unlike Hoeffding or Bernstein inequalities under i.i.d. assumptions, the strongly adapted sub-ψ condition allows the noise to be dependent, as long as the conditional tail behavior is controllable, making it applicable to the complex noise sequences arising in iterative algorithms.

Product betting martingales are a general technique for constructing time-uniform bounds, originating from modeling betting strategies in a game. The core idea is to choose a predictable "betting" function such that, under the null hypothesis or the error process, the expectation of the product martingale is at most 1; then, by applying Ville's inequality, the probability that the martingale exceeds 1/α is at most α. By mixing multiple betting strategies (i.e., continuous or discrete mixtures), bounds adapted to different noise scales and time scales can be obtained. Compared with traditional Chernoff bounds, the betting approach does not rely on pre-known variance or tail distribution parameters, but instead learns adaptively from the data, so the resulting bounds are usually tighter and naturally satisfy anytime validity. This technique has been widely used in sequential testing and confidence sequences, and this paper systematically introduces it into the error analysis of iterative algorithms.

Plug-and-play scope of application

The paper shows how to couple these bounds with separate algorithm analyses to provide off-the-shelf anytime-valid bounds for a variety of settings:

Stochastic gradient descent (SGD): For SGD, the framework either recovers or significantly sharpens all existing bounds known to the authors. This means the new method is theoretically at least as good as existing results and is tighter in many cases.

Temporal-difference (TD) learning: A core algorithm in reinforcement learning can also benefit from this framework.

Bures-Wasserstein SGD: Stochastic optimization in Wasserstein space is also covered.

These applications show that the recipe is not a trick for a single algorithm, but a general tool with broad applicability.

Implementation details and experimental validation

The paper does not stop at the theoretical level; it also provides explicit implementation details and validates them through numerical experiments. The experimental results show that the constructed bounds are competitive in practice and can support data-dependent stopping decisions.

For practitioners, this means they can monitor these bounds during training and stop iterating when the bound is small enough, without worrying about losing statistical guarantees.

Significance for algorithm practice

This work resolves a long-standing tension: theoretical convergence guarantees usually assume a fixed number of iterations, whereas practical applications need to decide when to stop based on the data. The general recipe makes it possible to quickly construct anytime-valid bounds for different algorithms, lowering the barrier of case-by-case derivation.

Of course, the paper also leaves some open questions, such as how to further optimize the tightness of the bounds and how to extend to more complex noise models. But overall, this general framework provides a solid statistical foundation for reliable stopping decisions in iterative algorithms.

One-line Summary

A new paper proposes a general recipe for constructing data-adaptive anytime-valid bounds for iterative algorithms.

Paragraph Summary

The paper addresses the problem that convergence guarantees for iterative stochastic algorithms apply only to a fixed number of iterations, and proposes a general recipe for constructing anytime-valid envelopes. The core insight is to reduce error analysis to a one-step recursion, thereby decoupling the problem into algorithm analysis (deriving the recursion) and noise concentration (constructing bounds). The authors introduce the strongly adapted sub-ψ condition to characterize the time-uniform concentration properties of the noise, and provide several bound construction methods such as continuous mixtures, discrete mixtures, stitching, and product betting martingales. The framework applies plug-and-play to SGD, temporal-difference learning, and Bures-Wasserstein SGD; for SGD it recovers or sharpens existing bounds, and it provides implementation details and numerical experimental validation, supporting data-dependent stopping decisions.