Abstract
Given a mixture between two populations of coins, "positive" coins that each have -- unknown and potentially different -- bias $\geq\frac{1}{2}+\Delta$ and "negative" coins with bias $\leq\frac{1}{2}-\Delta$, we consider the task of estimating the fraction $\rho$ of positive coins to within additive error $\epsilon$. We achieve an upper and lower bound of $\Theta(\frac{\rho}{\epsilon^2\Delta^2}\log\frac{1}{\delta})$ samples for a $1-\delta$ 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 showing how to assemble partially-adaptive bounds into a fully-adaptive bound, which may be of independent interest. 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 $\rho$ is small.
Introduction
The challenge of estimating the composition of a binary mixture is pervasive in data science, particularly in scenarios like crowdsourcing where individual observations are noisy. Imagine a database where you need to estimate the fraction $\rho$ of "erroneous" records. Using crowdsourced workers to verify records introduces noise: workers may misidentify correct records or miss errors.
This paper models this problem as a mixture of two coin populations:
- "Positive" coins: Bias $\ge \frac{1}{2} + \Delta$ (representing the target items).
- "Negative" coins: Bias $\le \frac{1}{2} - \Delta$ (representing the background items).
The goal is to estimate $\rho$ within an additive error $\epsilon$ using the minimum number of total coin flips. The "uncertainty about uncertainty" refers to the unknown exact biases of the coins, with only a known gap $2\Delta$ separating the two populations.
Algorithmic Approach
The authors propose a hybrid methodology that leverages adaptivity to improve efficiency, particularly when the target population is rare (small $\rho$).
1. The Triangular Walk (Algorithm 2)
This is a single-coin adaptive estimator. It treats the sequence of flips for an individual coin as a 1D random walk. The algorithm can "give up" early on coins that hit a "majority-tails" threshold, identifying them as likely negative. This early stopping conserves the sampling budget for rarer positive coins. The output coefficients are designed using the classical Ballot Theorem to ensure the estimator remains unbiased despite early termination.
2. Refined Sampling (Algorithm 3)
For high-precision estimation, the authors use a "telescoping" estimator. Coins are flipped $n$ times (where $n$ is a power of 2), with coefficients carefully selected so that high-variance terms cancel out in expectation. This provides an unbiased estimate with low variance, even when the distribution of biases within the $\Delta$ intervals is unknown.
Theoretical Contributions and Key Results
The primary contribution of this work is the establishment of matching upper and lower bounds for the sample complexity of this estimation task.
As shown in the table above, the authors achieve a sample complexity of $\Theta\left(\frac{\rho}{\epsilon^2 \Delta^2} \log \frac{1}{\delta}\right)$ for adaptive algorithms. This bound is tight for every parameter ($\rho, \epsilon, \Delta, \delta$).
Crucially, the authors prove a Decomposition Lemma that allows them to extend lower bounds from partially-adaptive settings to fully-adaptive ones. This lemma demonstrates that while adaptivity is powerful—saving a factor of $\log(1/\rho)$ over non-adaptive methods in the rare-event regime—cross-coin adaptivity (deciding which coin to flip next) does not fundamentally improve the lower bound over single-coin adaptivity.
Practical Performance
Simulation results on synthetic data, mimicking crowdsourcing applications with $\rho$ as low as 0.005, demonstrate the practical efficacy of the "T-WALK" algorithm. It consistently converges to the ground truth faster than standard majority voting and existing state-of-the-art heuristics like "SWITCH."
Conclusion and Future Directions
This work provides the first optimal adaptive algorithm for binary mixture estimation with unknown biases. While the model assumes a known gap $2\Delta$, future work could explore scenarios with overlapping distributions or unknown gaps. Additionally, extending these techniques to multi-class mixtures or continuous bias distributions remains an open and promising area of research.
Summary updated