Timezone: »

Confidence sequences for sampling without replacement
Ian Waudby-Smith · Aaditya Ramdas

Thu Dec 10 08:10 AM -- 08:20 AM (PST) @ Orals & Spotlights: Probabilistic Models/Statistics
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 \textit{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.

Author Information

Ian Waudby-Smith (Carnegie Mellon University)
Aaditya Ramdas (CMU)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors