Near-Exponential Savings for Population Mean Estimation with Active Learning

We study the problem of efficiently estimating the mean of a $k$-class random variable, $Y$, using a limited number of labels, $N$, in settings where the analyst has access to auxiliary information (i.e.: covariates) $X$ that may be informative about $Y$. We propose an active learning algorithm (PartiBandits) to estimate $\mathbb{E}[Y]$.