  We consider the problem of estimating confidence intervals for the mean of a
random variable, where the goal is to produce the smallest possible interval
for a given number of samples. While minimax optimal algorithms are known for
this problem in the general case, improved performance is possible under
additional assumptions. In particular, we design an estimation algorithm to
take advantage of side information in the form of a control variate, leveraging
order statistics. Under certain conditions on the quality of the control
variates, we show improved asymptotic efficiency compared to existing
estimation algorithms. Empirically, we demonstrate superior performance on
several real world surveying and estimation tasks where we use the output of
regression models as the control variates.
