Time-uniform, nonparametric, nonasymptotic confidence sequences

By Steven R. Howard, Aaditya Ramdas, Jon D. McAuliffe, Jasjeet S. Sekhon. 2018

383 citations recorded by the source corpus.

A confidence sequence is a sequence of confidence intervals that is uniformly valid over an unbounded time horizon. Our work develops confidence sequences whose widths go to zero, with nonasymptotic coverage guarantees under nonparametric conditions. We draw connections between the Cram\'er-Chernoff method for exponential concentration, the law of the iterated logarithm (LIL), and the sequential probability ratio test---our confidence sequences are time-uniform extensions of the first; provide tight, nonasymptotic characterizations of the second; and generalize the third to nonparametric settings, including sub-Gaussian and Bernstein conditions, self-normalized processes, and matrix martingales. We illustrate the generality of our proof techniques by deriving an empirical-Bernstein bound growing at a LIL rate, as well as a novel upper LIL for the maximum eigenvalue of a sum of random matrices. Finally, we apply our methods to covariance matrix estimation and to estimation of sample average treatment effect under the Neyman-Rubin potential outcomes model.

Subfields: Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Statistics and Probability

Citations in the corpus

Dueling RL: Reinforcement Learning with Trajectory Preferences (2021, background): “In the terminology of Howard et al. (2021), let St = ∑t i=1 Yi be a sub-ψP process with parameter c > 0 and variance process Wt.”
Time-uniform central limit theory and asymptotic confidence sequences (2021, methodology): “[19] take a while to adapt to the variance (while those of Robbins [41] never will).”
Estimating means of bounded random variables by betting (2020, methodology): “Figure 2: Empirical Bernstein CSs produced via predictable mixtures with (λt)t=1 from (16) essentially match those obtained via conjugate mixtures [1]; the former is closed-form, but the latter is not and requires numerical methods.”
On the Theory of Reinforcement Learning with Once-per-Episode Feedback (2021, positive): “By invoking a time-uniform Hoeffding-style concentration inequality (Howard et al., 2021, Equation (11)) we find that P [ ∀ t ∈ N : T∑ t=1 xt ζ ≤ 1.7 √ T ( log log(T ) + 0.72 log ( 5.2 δ ))] ≥ 1− δ. Rounding up the constants for the sake of simplicity we get P [ ∀ t ∈ N : T∑ t=1 xt ≤ 2ζ √ T ( log (…”
Sequential estimation of quantiles with applications to A/B testing and best-arm identification (2019, background): “In effect, we spell out the less-known duality between sequential tests and confidence sequences (Howard et al., 2021), analogous to the well-known duality between (standard, fixed time) hypothesis tests and confidence intervals.”
Sequential statistical inference for Large Language Models: Representation, validity, and monitoring (2026, unknown): “Repeated prompting or selective use of model outputs also raises optional-stopping issues, making anytime-valid reasoning a natural fit (Howard et al., 2021).”