Time-uniform, nonparametric, nonasymptotic confidence sequences

Abstract

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ér-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.

48 pages, 10 figures

References in corpus (7)

• Empirical Bernstein Bounds and Sample Variance Penalization
• Time-uniform Chernoff bounds via nonnegative supermartingales
• Self-normalized processes: exponential inequalities, moment bounds and iterated logarithm laws
• Pseudo-maximization and self-normalized processes
• Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals
• A framework for Multi-A(rmed)/B(andit) testing with online FDR control
• A Bandit Approach to Multiple Testing with False Discovery Control

Cited by in corpus (16)

• E-values: Calibration, combination, and applications
• Sequential estimation of quantiles with applications to A/B-testing and best-arm identification
• Catoni-style confidence sequences for heavy-tailed mean estimation
• Hypothesis testing with e-values
• Martingale Methods for Sequential Estimation of Convex Functionals and Divergences
• Comparing Sequential Forecasters
• Post-selection inference for e-value based confidence intervals
• Evidential Calibration of Confidence Intervals
• Anytime-Valid Confidence Sequences in an Enterprise A/B Testing Platform
• Anytime-Valid Linear Models and Regression Adjusted Causal Inference in Randomized Experiments
• ALL-IN meta-analysis: breathing life into living systematic reviews and prospective meta-analyses
• Anytime valid and asymptotically optimal inference driven by predictive recursion
• Design-Based Confidence Sequences: A General Approach to Risk Mitigation in Panel Experiments
• On Confidence Sequences for Bounded Random Processes via Universal Gambling Strategies
• Revisiting Stochastic Gradient Descent for Strongly Convex Objectives: Tight Uniform-in-Time Bounds
• Sequential Monte-Carlo testing by betting