Time-uniform Chernoff bounds via nonnegative supermartingales

Abstract

We develop a class of exponential bounds for the probability that a martingale sequence crosses a time-dependent linear threshold. Our key insight is that it is both natural and fruitful to formulate exponential concentration inequalities in this way. We illustrate this point by presenting a single assumption and theorem that together unify and strengthen many tail bounds for martingales, including classical inequalities (1960-80) by Bernstein, Bennett, Hoeffding, and Freedman; contemporary inequalities (1980-2000) by Shorack and Wellner, Pinelis, Blackwell, van de Geer, and de la Peña; and several modern inequalities (post-2000) by Khan, Tropp, Bercu and Touati, Delyon, and others. In each of these cases, we give the strongest and most general statements to date, quantifying the time-uniform concentration of scalar, matrix, and Banach-space-valued martingales, under a variety of nonparametric assumptions in discrete and continuous time. In doing so, we bridge the gap between existing line-crossing inequalities, the sequential probability ratio test, the Cramér-Chernoff method, self-normalized processes, and other parts of the literature.

63 pages, 7 figures

References in corpus (10)

• User-friendly tail bounds for sums of random matrices
• Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence (1998)
• Exponential inequalities for self-normalized martingales with applications
• Matrix concentration inequalities via the method of exchangeable pairs
• Large Deviation Methods for Approximate Probabilistic Inference
• Self-normalized processes: exponential inequalities, moment bounds and iterated logarithm laws
• An introduction to Lévy processes with applications in finance
• Pseudo-maximization and self-normalized processes
• Concentration of Measure Inequalities in Information Theory, Communications and Coding (Second Edition)
• New Optional Stopping Theorems and Maximal Inequalities on Stochastic Processes

Cited by in corpus (27)

• Universal Inference
• Time-uniform, nonparametric, nonasymptotic confidence sequences
• Sequential estimation of quantiles with applications to A/B-testing and best-arm identification
• Admissible anytime-valid sequential inference must rely on nonnegative martingales
• Optional Stopping with Bayes Factors: a categorization and extension of folklore results, with an application to invariant situations
• Catoni-style confidence sequences for heavy-tailed mean estimation
• On the bias, risk and consistency of sample means in multi-armed bandits
• Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrieval
• Comparing Sequential Forecasters
• Martingale Methods for Sequential Estimation of Convex Functionals and Divergences
• Distribution-free binary classification: prediction sets, confidence intervals and calibration
• Confidence sequences for sampling without replacement
• Post-selection inference for e-value based confidence intervals
• False discovery rate control with e-values
• Interactive Martingale Tests for the Global Null
• Uncertainty quantification using martingales for misspecified Gaussian processes
• Dueling RL: Reinforcement Learning with Trajectory Preferences
• Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticity
• Risk-Monotonicity in Statistical Learning
• Uncertainty Inference with Applications to Control and Decision
• Uncertainty Quantification for Inferring Hawkes Networks
• Bregman Deviations of Generic Exponential Families
• PAC Mode Estimation using PPR Martingale Confidence Sequences
• Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case
• Semantics and Axiomatization for Stochastic Differential Dynamic Logic
• Testing exchangeability: fork-convexity, supermartingales, and e-processes
• Finite sample inference for generic autoregressive models