Confidence sequences for sampling without replacement

Abstract

Many practical tasks involve sampling sequentially without replacement (WoR) from a finite population of size $N$, in an attempt to estimate some parameter ${\theta }^{\star }$. Accurately quantifying uncertainty throughout this process is a nontrivial task, but is necessary because it often determines when we stop collecting samples and confidently report a result. We present a suite of tools for designing confidence sequences (CS) for ${\theta }^{\star }$. A CS is a sequence of confidence sets $(C_n{)}_{n=1}^N$, that shrink in size, and all contain ${\theta }^{\star }$ simultaneously with high probability. We present a generic approach to constructing a frequentist CS using Bayesian tools, based on the fact that the ratio of a prior to the posterior at the ground truth is a martingale. We then present Hoeffding- and empirical-Bernstein-type time-uniform CSs and fixed-time confidence intervals for sampling WoR, which improve on previous bounds in the literature and explicitly quantify the benefit of WoR sampling.

References in corpus (6)

• Empirical Bernstein Bounds and Sample Variance Penalization
• lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits
• Universal Inference
• Time-uniform Chernoff bounds via nonnegative supermartingales
• Sequential estimation of quantiles with applications to A/B-testing and best-arm identification
• Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals

Cited by in corpus (1)

• Anytime-Valid Confidence Sequences in an Enterprise A/B Testing Platform