General method for adaptive confidence bounds in iterative algorithms
A general recipe for data-adaptive anytime-valid envelopes for iterative algorithms
Machine Learning
Summary
Stopping an iterative algorithm at a good time often depends on the data it produces, but most methods only guarantee results at fixed steps, not when you stop early or late based on observed data. The authors provide a general approach to create reliable, data-based confidence bounds that hold no matter when the algorithm stops. Their method works across many algorithms and improves or matches existing bounds for popular techniques like stochastic gradient descent. They also provide practical details and show their approach works in examples.
What this means in practice
- •For machine learning engineers: Set reliable early stopping rules in training models with stochastic gradient descent that adapt to observed data for better performance guarantees.
- •For reinforcement learning developers: Use data-adaptive confidence bounds to decide when to stop iterative learning algorithms like temporal difference learning safely and reliably.
Authors
Soham Bonnerjee, Aaditya Ramdas
Abstract
Most convergence guarantees for iterative stochastic algorithms are stated at a fixed iteration count and do not justify stopping at a data-dependent time. Recent work has constructed anytime-valid envelopes that do, but deterministic envelopes are typically too conservative for practical stopping, and existing data-adaptive ones are derived case-by-case, each coupling a specific algorithm to a specific noise model and boundary construction. This paper provides a general recipe for constructing such anytime-valid data-adaptive boundaries for a large class of iterative algorithms. Performance measures of many of these algorithms satisfy a one-step recursion that reduces the entire error analysis to a single general requirement: time-uniform concentration for predictably weighted sums of noise. We formalize this through a strongly adapted sub-$ψ$ condition, and derive off-the-shelf boundary constructions via continuous and discrete mixtures, stitching, and product betting martingales. We show how these boundaries can be directly coupled with a separate algorithmic analysis that derives the one-step recursion to provide a class of readymade anytime-valid envelopes across diverse settings including stochastic gradient descent (SGD), temporal difference learning, and Bures-Wasserstein SGD. In particular, for SGD, our framework either recovers or significantly sharpens every existing envelope we are aware of. Our constructions come with explicit implementation details and are substantiated by numerical experiments.