Part of Advances in Neural Information Processing Systems 33 (NeurIPS 2020)
Ian Waudby-Smith, Aaditya Ramdas
Many practical tasks involve sampling sequentially without replacement (WoR) from a finite population of size N, in an attempt to estimate some parameter θ⋆. 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 θ⋆. A CS is a sequence of confidence sets (Cn)Nn=1, that shrink in size, and all contain θ⋆ 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.