Proof: Accelerating Approximate Aggregation Queries with Expensive
  Predicates
  Given a dataset $\mathcal{D}$, we are interested in computing the mean of a
subset of $\mathcal{D}$ which matches a predicate. ABae leverages stratified
sampling and proxy models to efficiently compute this statistic given a
sampling budget $N$. In this document, we theoretically analyze ABae and show
that the MSE of the estimate decays at rate $O(N_1^{-1} + N_2^{-1} +
N_1^{1/2}N_2^{-3/2})$, where $N=K \cdot N_1+N_2$ for some integer constant $K$
and $K \cdot N_1$ and $N_2$ represent the number of samples used in Stage 1 and
Stage 2 of ABae respectively. Hence, if a constant fraction of the total sample
budget $N$ is allocated to each stage, we will achieve a mean squared error of
$O(N^{-1})$ which matches the rate of mean squared error of the optimal
stratified sampling algorithm given a priori knowledge of the predicate
positive rate and standard deviation per stratum.
