Time-uniform Chernoff bounds via nonnegative supermartingales

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

220 citations recorded by the source corpus.

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\~na; 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\'er-Chernoff method, self-normalized processes, and other parts of the literature.

Subfields: Applied Mathematics, Discrete Mathematics and Combinatorics, Statistics and Probability, Evaluation & Benchmarks

How researchers see this paper

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

In Applied Mathematics

In Discrete Mathematics and Combinatorics

In Statistics and Probability

In Evaluation & Benchmarks

Citations in the corpus

Dueling RL: Reinforcement Learning with Trajectory Preferences (2021, positive): “By invoking a time-uniform Hoeffding-style concentration inequality (Howard et al., 2020, Equation (11)) we find that Pr [ ∀ 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 Pr [ ∀ t ∈ N : T∑ t=1 xt ≤ 2ζ √ T ( log…”
Admissible anytime-valid sequential inference must rely on nonnegative martingales. (2020, methodology): “…to a nonparametric example that ﬁrst appears in de la Peña [5] but the core idea can be traced back to Efron [7], who was interested in the robustness of the t -test to heavy tailed (but symmetric) distributions; further, it has recently been extended to the matrix setting by Howard et al. [10].”
Chatbot Arena: An Open Platform for Evaluating LLMs by Human Preference (2024, methodology): “…to detecting harmful users could be improved and made more formally rigorous by using the theory of nonnegative supermartingales and E-values (Howard et al., 2020; Waudby-Smith & Ramdas, 2020; Vovk & Wang, 2021; Ramdas et al., 2023); this would deal with the dependence, but the variants we…”
E-values: Calibration, combination and applications (2019, unknown): “Recent research includes exponential line-crossing inequalities [Howard et al., 2020a], nonparametric conﬁdence sequences [Howard et al., 2020b], and universal inference [Wasserman et al., 2020].”
Time-uniform, nonparametric, nonasymptotic confidence sequences (2018, methodology): “[25], we have emphasized the nonparametric applicability of our boundaries.”
Sequential estimation of quantiles with applications to A/B testing and best-arm identification (2019, methodology): “First, Corollary 1 of Howard et al. (2021) implies that P(B(1) t infinitely often) = 0, while Theorem 2 implies P(B(2) t infinitely often) = 0.”
Time-uniform central limit theory and asymptotic confidence sequences (2021, unknown): “Step 2: Mixing over λ P p0,8q to obtain a mixture NSM Let us now construct a one-sided sub-Gaussian mixture NSM.”