Time-uniform, nonparametric, nonasymptotic confidence sequences

2018/10/18 by Steven R. Howard, Aaditya Ramdas, Jon McAuliffe +1 · 2 voices · 106 citations
Mathematics · #Advanced Causal Inference Techniques #CDF-based nonparametric confidence interval #Confidence distribution #Confidence interval #Iterated function #Law of the iterated logarithm #Logarithm #Matrix (chemical analysis) #Nonparametric statistics #Random Matrices and Applications #Sequence (biology) #Statistical Methods and Inference #math.PR #math.ST #stat.ME #stat.TH

paper · pdf · open access · doi:10.1214/20-aos1991

published in The Annals of Statistics 49(2) (Institute of Mathematical Statistics) · 48 pages, 10 figures

arxiv published 2018/10/18 · openalex created_date 2020/06/05 · openalex publication_date 2021/04/01 · arxiv created 2022/08/06 · arxiv updated 2022/08/09 · openalex updated_date 2026/08/06

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.

Citations

• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A Multiple Testing Procedure for Clinical Trials
• Group sequential methods in the design and analysis of clinical trials
• Estimating causal effects of treatments in randomized and nonrandomized studies.

Cited by

• Hypothesis Testing with E-values
• Combining e-values using demi-supermartingales
• Efficient Sequential Evaluation of Large Language Models
• Anytime Detection of Strategic Deviations in Multi-Agent Systems
• Anytime-Valid Confirmation of Covariate Balance for Prespecified Corrections
• Closed-form empirical Bernstein confidence sequences for scalars and matrices
• Stopping Rules for Stochastic Gradient Descent via Anytime-Valid Confidence Sequences
• Eventually LIL Regret: Almost Sure lnln T Regret for a sub-Gaussian Mixture on Unbounded Data
• A Sensitivity Approach to Causal Inference Under Limited Overlap
• Self-Normalized Concentration Inequalities of Marginal Mean with Sample Variance Only
• Choosing the nominal level post-hoc with knockoffs using e-values
• Bernstein-von Mises for Adaptively Collected Data
• Vector-valued self-normalized concentration inequalities beyond sub-Gaussianity
• Concentration inequalities for strong laws and laws of the iterated logarithm
• E-Scores for (In)Correctness Assessment of Generative Model Outputs
• Post-Training at the Edge of Detectability: A Game-Theoretic Approach to Fine-Tuning
• Certified Self-Consistency: Statistical Guarantees and Test-Time Training for Reliable Reasoning in LLMs
• SIEVE: Towards Verifiable Certification for Code-datasets
• Valid Stopping for LLM Generation via Empirical Dynamic Formal Lift
• Technical note on Sequential Test-Time Adaptation via Martingale-Driven Fisher Prompting
• Nonparametric inference under shape constraints: past, present and future
• An exploration of sequential Bayesian variable selection -- A comment on García-Donato et al. (2025). "Model uncertainty and missing data: An objective Bayesian perspective"
• Agents That Certify Their Own Exploits: Confidence-Scheduled Restricted Responses for Safe Opponent Exploitation
• Game-Theoretic Statistics and Safe Anytime-Valid Inference
• The Root Finding Problem Revisited: Beyond the Robbins-Monro procedure
• Adaptive Algorithms with Sharp Convergence Rates for Stochastic Hierarchical Optimization
• A Scalable Formula for the Moments of a Family of Self-Normalized Statistics
• Fuzzy Prediction Sets: Conformal Prediction with E-values
• Selecting the Best Arm in One-Shot Multi-Arm RCTs: The Asymptotic Minimax-Regret Decision Framework for the Best-Population Selection Problem
• Online Learning of Optimal Sequential Testing Policies
• Revisit Stochastic Gradient Descent for Strongly Convex Objectives: Tight Uniform-in-Time Bounds
• Sequential Correct Screening and Post-Screening Inference
• Anytime validity is free: inducing sequential tests
• A variational approach to dimension-free self-normalized concentration
• Generalized Kernelized Bandits: A Novel Self-Normalized Bernstein-Like Dimension-Free Inequality and Regret Bounds
• Risk-inclusive Contextual Bandits for Early Phase Clinical Trials
• Bernstein-type dimension-free concentration for self-normalised martingales
• Algorithmic Fairness: A Runtime Perspective
• Alignment Monitoring
• ALL-IN meta-analysis: breathing life into living systematic reviews and prospective meta-analyses
• Monitoring Risks in Test-Time Adaptation
• Monitoring of Static Fairness
• Confidence sequences with informative, bounded-influence priors
• Simulation-Based Inference for Adaptive Experiments
• Catoni-Style Change Point Detection for Regret Minimization in Non-Stationary Heavy-Tailed Bandits
• Anytime-valid, Bayes-assisted, Prediction-Powered Inference
• ParEvalLayer: When Partial LLM-Agent Evaluations Support a Decision
• When May a Model Replace the Experiment? Audits, Licenses, and the Price of Trust in Surrogate-Driven Design
• Sharp Empirical Bernstein Bounds for the Variance of Bounded Random Variables
• Online Shift Detection and Conformal Adaptation for Deployed Safety Classifiers
• Monitoring Discounted Sum Properties
• Online Safety Monitoring for LLMs
• Asymptotically Log-Optimal Bayes-Assisted Confidence Sequences for Bounded Means
• E-values for Adaptive Clinical Trials: Anytime-Valid Monitoring in Practice
• Optimism Stabilizes Thompson Sampling for Adaptive Inference
• On Stopping Times of Power-one Sequential Tests: Tight Lower and Upper Bounds
• Near-optimal algorithms for private estimation and sequential testing of collision probability
• Post-Hoc Trajectory-Risk Certification for Modular LLM-Based Security Agents

Discussions

• arxiv.org/pdf/1810.08240 [bsky, 2 points, 1 comments]
• This Howard et al. paper nice for an introduction arxiv.org/abs/1810.08240 [bsky, 0 points, 1 comments]

Related

• A new and flexible class of sharp asymptotic time-uniform confidence sequences
• Time-uniform central limit theory and asymptotic confidence sequences
• Nonparametric iterated-logarithm extensions of the sequential generalized likelihood ratio test
• A lower confidence sequence for the changing mean of non-negative right heavy-tailed observations with bounded mean
• On the near-optimality of betting confidence sets for bounded means