Confidence sequences for sampling without replacement
Ian Waudby-Smith, Aaditya Ramdas
Spotlight presentation: Orals & Spotlights Track 25: Probabilistic Models/Statistics
on 2020-12-10T08:10:00-08:00 - 2020-12-10T08:20:00-08:00
on 2020-12-10T08:10:00-08:00 - 2020-12-10T08:20:00-08:00
Toggle Abstract Paper (in Proceedings / .pdf)
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 \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 first exploit a relationship between Bayesian posteriors and martingales to construct a (frequentist) CS for the parameters of a hypergeometric distribution. 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.