Uncertainty about Uncertainty: Optimal Adaptive Algorithms for Estimating Mixtures of Unknown Coins
This provides optimal adaptive algorithms for crowdsourcing applications, particularly in rare events regimes, though it is incremental in refining bounds for a specific statistical problem.
The paper tackles the problem of estimating the fraction of positive coins in a mixture with unknown biases, achieving tight sample complexity bounds of Θ(ρ/(ε²Δ²) log(1/δ)) for additive error ε and success probability 1-δ, with a lower bound applying to all fully-adaptive algorithms.
Given a mixture between two populations of coins, "positive" coins that each have -- unknown and potentially different -- bias $\geq\frac{1}{2}+Δ$ and "negative" coins with bias $\leq\frac{1}{2}-Δ$, we consider the task of estimating the fraction $ρ$ of positive coins to within additive error $ε$. We achieve an upper and lower bound of $Θ(\fracρ{ε^2Δ^2}\log\frac{1}δ)$ samples for a $1-δ$ probability of success, where crucially, our lower bound applies to all fully-adaptive algorithms. Thus, our sample complexity bounds have tight dependence for every relevant problem parameter. A crucial component of our lower bound proof is a decomposition lemma (see Lemmas 17 and 18) showing how to assemble partially-adaptive bounds into a fully-adaptive bound, which may be of independent interest: though we invoke it for the special case of Bernoulli random variables (coins), it applies to general distributions. We present simulation results to demonstrate the practical efficacy of our approach for realistic problem parameters for crowdsourcing applications, focusing on the "rare events" regime where $ρ$ is small. The fine-grained adaptive flavor of both our algorithm and lower bound contrasts with much previous work in distributional testing and learning.