Distribution Testing in the Presence of Arbitrarily Dominant Noise with Verification Queries

We study distribution testing without direct access to a source of relevant data, but rather to a highly contaminated one, from which only a tiny fraction (e.g. 1%) is relevant. To enable this, we introduce the following verification query model. The goal is to perform a statistical task on distribution p given sample access to a mixture r = λp + (1 -λ)q and the ability to query whether a sample x ∼ r was generated by p (relevant) or by q (irrelevant). This captures scenarios where it is cheap to acquire data from a massive pool, but expensive to verify whether it is of interest for the specific task. In general, if m0 clean samples from p suffice for a task, then O(m0/λ) samples and verification queries trivially suffice in our model. We ask, are there tasks for which the number of queries can be significantly reduced?

We show that for the canonical problems in distribution testing (uniformity, identity, and closeness), the answer is yes. In fact, we obtain matching upper and lower bounds that reveal smooth trade-offs between sample and query complexity. For all m ≤ n, we obtain (i) a uniformity and identity tester using O(m + √ n