Near-Optimal Non-Parametric Sequential Tests and Confidence Sequences with Possibly Dependent Observations - Nathan Kallus

Sequential tests and their implied confidence sequences, which are valid at arbitrary stopping times, promise flexible statistical inference and on-the-fly decision making. However, strong guarantees are limited to parametric sequential tests, which suffer high type-I error rates in practice because reality isn't parametric, or to concentration-bound-based sequences, which are overly conservative so we get wide intervals and take too long to detect effects. We consider a classic delayed-start normal-mixture sequential probability ratio test and provide the first asymptotic (in the delay) analysis under general non-parametric data generating processes. We guarantee type-I-error rates approach a user-specified α-level (primarily by leveraging a martingale strong invariance principle). Moreover, we show that the expected time-to-reject approaches the minimum possible among all α-level tests (primarily by leveraging an identity inspired by Itô's lemma). Together, our results establish these (ostensibly parametric) tests as general-purpose, non-parametric, and near-optimal. We illustrate this via numerical experiments and a retrospective re-analysis of A/B tests at Netflix.