Asymmetric sample use improves likelihood-free hypothesis testing efficiency
Asymmetric Likelihood-Free Hypothesis Testing
Machine LearningData Structures and AlgorithmsInformation Theory
Summary
The paper studies a way to tell apart two unknown groups by only looking at examples from each, even when you can take different numbers of examples from each group. The authors found that using unequal amounts of data from the known groups can make it easier to identify which group a new example belongs to. Their method uses fewer examples in some cases compared to previous approaches. They also show how these findings can help in grouping many unknown distributions when you decide how to divide your samples before seeing any data.
What this means in practice
- •For data engineers: Optimize data collection between known distributions to reduce samples needed for testing new data origins efficiently.
- •For machine learning system builders: Design non-adaptive clustering systems with improved sample allocation strategies to better sort multiple unknown data sources.
A theory result. No direct application yet.
Authors
Gunjan Kumar, Yash Pote, Jonathan Scarlett
Abstract
In likelihood-free hypothesis testing (LFHT), given samples from two unknown distributions $P,Q$ on $[n]$ with $\mathrm{d_{TV}}(P,Q)\geq\varepsilon$, and from a third distribution $D\in\{P,Q\}$, the goal is to identify whether $D=P$ or $D=Q$. We study asymmetric likelihood-free hypothesis testing, where the sample budgets $s_P$ and $s_Q$ for $P$ and $Q$ may differ, and characterize the feasible triples $(s_P,s_Q,s_D)$ up to logarithmic factors. We establish that unequal reference budgets can give a polynomial saving. For instance, for constant separation, $n$ samples from $P$ and $n^{3/4}$ from $Q$ allow testing with $\widetilde O(n^{1/4})$ samples from $D$, whereas both existing baselines---symmetric LFHT and unequal-sample closeness testing---require $Ω(\sqrt n)$ samples from $D$. We further apply our results to non-adaptive distribution 2-clustering, where the sample allocation among $k$ distributions must be fixed before observing any data. We obtain matching upper and lower bounds for this problem up to logarithmic factors in terms of the domain size, number of distributions, smaller cluster size, and separation, both with one cluster distribution known and with both unknown. Comparing with known bounds for adaptive sample allocation gives a worst-case adaptivity gap of $\widetildeΘ(k^{1/4})$.