Asymmetric Likelihood-Free Hypothesis Testing

Gunjan Kumar; Yash Pote; Jonathan Scarlett

cs.LGOct 21, 2026

Asymmetric Likelihood-Free Hypothesis Testing

Authors: Gunjan Kumar, Yash Pote, Jonathan Scarlett

Organizations: IIT Kanpur · National University of Singapore

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})$ .

Figures & tables

Panel of Figure 1 — Figure 1: Slices of the feasible region of Theorem 1 at four values of $s_{P}$ , with $\varepsilon$ constant. Constant and logarithmic factors are suppressed, and both axes are logarithmic.

Regime	One known distribution	Both distributions unknown
$n\gtrsim\frac{k^{2}}{r\varepsilon^{4}}$	$\widetilde{\Theta}\!\left(\frac{k\sqrt{n}}{\sqrt{r}\,\varepsilon^{2}}\right)$	$\widetilde{\Theta}\!\left(\frac{k^{2/3}n^{2/3}}{r^{1/3}\varepsilon^{4/3}}\right)$
$r\log k\lesssim n\lesssim\frac{k^{2}}{r\varepsilon^{4}}$	$\widetilde{\Theta}\!\left(\frac{k\sqrt{n}}{\sqrt{r}\,\varepsilon^{2}}\right)$	$\widetilde{\Theta}\!\left(\frac{k\sqrt{n}}{\sqrt{r}\,\varepsilon^{2}}\right)$
$n\lesssim r\log k$	$\widetilde{\Theta}\!\left(\frac{k}{\varepsilon^{2}}\right)$	$\widetilde{\Theta}\!\left(\frac{k}{\varepsilon^{2}}\right)$

Table 1: Non-adaptive sample complexity

T_{\mathrm{na}}

for

k\geqslant 200

and

\varepsilon\in(0,1/8]

. The notation

\widetilde{\Theta}

hides polylogarithmic factors. The bounds follow from Theorems 14 , 19 , 16 and 20 .

Statistical Hypothesis Testing

Statistical hypothesis testing develops methods for assessing evidence against a stated null while controlling false-positive and false-negative rates.

See all 101 papers

May 22, 2026

Entropy Equivalence Testing

We introduce the problem of entropy equivalence testing for probability distributions, a relaxation of the well-studied closeness testing problem, where the distribution testing algorithm is now only required to distinguish, given samples from two unknown distributions

p,q

and a parameter

\varepsilon \in(0,1/2]

, between

p=q

and

|H(p)-H(q)| \geq \varepsilon

(where

H

denotes the Shannon entropy). We provide a time- and sample-efficient algorithm for this task, showing that the optimal sample complexity for this task can be significantly lower than that of closeness testing. As an application, we leverage this result to provide the first non-trivial testing algorithm for (standard) closeness of low-degree Bayesian networks, which significantly improves on either the sample or time complexity of a baseline based on full learning.

Clément L. Canonne, Yash Pote, Jonathan Scarlett +1

University of Sydney · National University of Singapore

Distribution Matching

Ask PDF

Jun 7, 2026

LOTTERY: Learning from Reference-Only Samples in Two-Sample Testing under Size Asymmetry

Data-adaptive two-sample testing assesses if two samples come from the same distribution, using a discrepancy learned from the data (e.g., via kernel-based feature representations). Such methods typically rely on data splitting to decouple learning from testing and control type I error. However, this paradigm is ill-suited to few-shot settings with severe sample-size imbalance: abundant reference samples are available, while only a handful of query samples arrive. In this paper, we show how this imbalance can be leveraged constructively. Using abundant reference data, we learn reference-dependent representations that summarize salient structure of the reference distribution and provide informative signals for detecting departures. We incorporate a collection of representation families that capture both global and local structure, and adaptively weight them using only reference samples via an uncertainty-guided principle. Theoretically, we establish permutation-based type I error control and show consistency of the aggregated test: as the sample sizes grow, the test power converges to one whenever the representation set contains at least one consistent representation. Empirically, our aggregation achieves strong performance across a range of benchmarks while retaining type I error control.

Xunye Tian, Zhijian Zhou, Liuhua Peng +1

University of Melbourne · Maincode

Two-Sample Testing Permutation Testing Statistical Hypothesis Testing

Ask PDF

Oct 6, 2026

Anytime-valid simulation-based hypothesis testing

For a given data distribution

(X_t)_{t \in \mathbb{N}} \sim Q

i.i.d., we investigate the hypothesis testing problem:

H_0: Q = P_0

vs.

H_1: Q = P_1

, for two different model probability distributions

P_0

and

P_1

. In contrast to the standard setting, where analytic densities

p_0

and

p_1

are given, here, we consider the density-free setting, where we only have access to i.i.d. simulations

(Z^0_t)_{t \in \mathbb{N}} \sim P_0

and

(Z^1_t)_{t \in \mathbb{N}} \sim P_1

. For this simulation-based hypothesis testing setting, we construct an e-test martingale, resulting in a sequential test with anytime-valid type-I error guarantees, approximate growth optimality, geometrically decaying type-II error bounds, and asymptotic power one. Most ingredients used in our constructions are variants of well known concepts. The value of this paper lies in the compact presentation of an effective, anytime-valid solution for the density-free simulation-based sequential hypothesis testing case.

Patrick Forré, Lydia Brenner

University of Amsterdam · Nikhef

Simulation-Based Inference Sequential Hypothesis Testing

Ask PDF

Abstract

Statistical Hypothesis Testing

Explore similar work

Entropy Equivalence Testing

LOTTERY: Learning from Reference-Only Samples in Two-Sample Testing under Size Asymmetry

Anytime-valid simulation-based hypothesis testing