PaperlayerView exact revision on arXiv

Source-linked AI summary

Asymmetric Likelihood-Free Hypothesis Testing

Gunjan Kumar, Yash Pote, Jonathan Scarlett

arXiv:2610.29798v1cs.LGcs.DScs.ITmath.ITmath.STstat.MLstat.TH

TL;DR

LFHT asks whether a target D equals one of two unknown distributions P and Q that are separated in total variation, using samples from all three. The paper characterizes feasible asymmetric LFHT sample budgets and applies the bounds to clustering by using exemplar distributions for asymmetric classification. With n samples from one reference distribution and n^3/4 from the other, eO(n^1/4) target samples suffice, versus prior work’s Ω(√n); non-adaptive 2-clustering has an adaptivity gap up to eO(k^1/4).

  • Problem

    LFHT asks whether a target D equals one of two unknown distributions P and Q that are separated in total variation, using samples from all three.

    Source: §1 · p. 1

  • Method

    The paper characterizes feasible asymmetric LFHT sample budgets and applies the bounds to clustering by using exemplar distributions for asymmetric classification.

    Source: §3 · p. 3, §6 · p. 11

  • Results

    With n samples from one reference distribution and n^3/4 from the other, eO(n^1/4) target samples suffice, versus prior work’s Ω(√n); non-adaptive 2-clustering has an adaptivity gap up to eO(k^1/4).

    Source: §7 · p. 12

  • Takeaways & Limitations

    Unequal reference budgets can polynomially reduce the target-sample requirement, and asymmetric LFHT bounds yield non-adaptive clustering bounds up to logarithmic factors.

    Source: §1 · p. 1, §7 · p. 12

    The non-adaptive allocation is fixed before observing samples and may depend only on n, k, ε, and the minority cluster size r.

    Source: §6 · p. 10

Abstract

from arXiv · show

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 $\Omega(\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\Theta(k^{1/4})$.

1 Introduction

The paper studies how unequal reference-sample budgets affect likelihood-free hypothesis testing, then applies the resulting bounds to non-adaptive distribution 2-clustering. It reports polynomial savings for asymmetric testing and a worst-case adaptivity gap for clustering.

1 Introduction

  • LFHT identifies whether a target D equals P or Q using samples from both unknown references, assumed to have TV distance at least ε.The goal is success probability at least 2/3.Source: §1 · p. 1
  • The paper asks how extra samples from one reference distribution reduce the target-sample requirement when the reference budgets differ.The motivation includes settings where an existing model has many simulated samples but a new model has few.Source: §1 · p. 1
  • For constant separation, n samples from P and n^3/4 from Q permit testing with eΘ(n^1/4) target samples, versus Ω(√n) for both cited baselines.The baselines are symmetric LFHT and unequal-sample closeness testing.Source: §1 · p. 1

1.1 Application to Non-Adaptive Clustering

  • Non-adaptive 2-clustering fixes the sample allocation before observing data, and the paper obtains matching bounds up to logarithmic factors when one cluster distribution is known.The allocation concerns k distributions and a smaller cluster of known size r.Source: §1.1 · pp. 1–2
  • For known smaller-cluster size r and two unknown cluster distributions, the paper determines the optimal non-adaptive total budget and reports a worst-case adaptivity gap of eΘ(k^1/4).When n=k, r ≍ k, and ε is constant, adaptive and non-adaptive budgets are eΘ(k) and eΘ(k^5/4), respectively.Source: §1.1 · p. 2
  • After identifying one exemplar from each cluster, classifying the remaining distributions reduces to asymmetric LFHT because the exemplars may have unequal sample budgets.Source: §1.1 · p. 2

2 Preliminaries and Background

The background defines the sample-budget setting and places asymmetric LFHT alongside prior distribution-testing and clustering work. Earlier LFHT results treated equal reference budgets; this paper studies the tradeoff when those budgets differ.

2 Preliminaries and Background

  • The feasible-budget problem considers triples (sP, sQ, sD) that allow testing with error at most 1/3 for every separated pair P,Q and either target choice.The setup assumes sP ≥ sQ; the notation suppresses constant and polylogarithmic factors in specified bounds.Source: §2 · p. 2
  • The three LFHT conditions roughly require enough target samples, adequate sampling of at least one reference, and sufficient joint information from the sample counts.Source: §2 · p. 2

2.1 Related Work

  • Distribution testing includes identity testing against a known distribution and closeness testing when both distributions are unknown; this paper’s test uses ingredients from closeness testers.The cited ingredients include squared ℓ2-distance estimators and sample-based flattening.Source: §2.1 · p. 2
  • Prior LFHT work characterized finite-sample guarantees for equal reference budgets; this paper determines the tradeoff when sP and sQ differ.Gerber et al. (2023) also provide a lower-bound construction adapted in Section 5.Source: §2.1 · p. 3
  • Adaptive clustering work found matching bounds up to logarithmic factors, while the non-adaptive allocation constraint yields a worst-case gap of eΘ(k^1/4).In non-adaptive sampling, classification budgets cannot depend on which exemplars are found.Source: §2.1 · p. 3

3 Main Result

The main result characterizes feasible asymmetric LFHT sample budgets up to logarithmic factors and describes how the boundary changes with the reference budgets. The proof ideas combine flattening and a quadratic statistic for the upper bound with collision-based lower-bound constructions.

3 Main Result

  • The three conditions require enough target samples even with known references, sufficient samples from at least one reference, and allow extra D-samples to compensate for fewer Q-samples.Source: §3 · p. 3
  • At sP=n, sQ=n^3/4, and constant ε, the target requirement is eΘ(n^1/4), while both baselines require at least √n samples.The example satisfies the third condition with sD(n^3/4+sD) ≳ n.Source: §3 · p. 3
  • Figure 1 shows fixed-sP slices of the feasible region; its lower boundary can include horizontal, diagonal, and vertical parts.The diagonal part appears only when sP>n^2/3, and additional P-samples stop helping once sP=n.Source: §3 · p. 3, Figure 1 · p. 4

3.1 Proof Ideas

  • For the upper bound, the test flattens P and Q while preserving their TV distance, then estimates the difference between squared ℓ2 distances from D to the flattened references.The better-sampled P helps control variance terms involving Q.Source: §3.1 · p. 4
  • For the lower bound, light pairs require D–D or D–Q collisions to reveal useful information, while heavy pairs hide which collisions matter and add dependence on sP below n.On light pairs, a single sample is uninformative; on heavy pairs, P, Q, and D coincide.Source: §3.1 · p. 4

4 Upper Bound

The upper bound uses different testing strategies across budget regimes, with the main algorithm flattening the distributions before estimating a signed squared-distance statistic. Its analysis controls the statistic’s variance and converts Poissonized batches to fixed budgets.

4 Upper Bound

  • The test selects a closeness tester, symmetric LFHT, or Algorithm 1 according to the sample-budget regime.When using Algorithm 1, it truncates the P budget to n if needed.Source: §4 · p. 5

4.1.1 Flattening

  • Flattening splits domain elements using P- and Q-samples, preserves total variation, and controls the largest probabilities of the transformed distributions.The same transformation is applied to P, Q, and D.Source: §4.1 · p. 6, §4.1.1 · p. 6

4.1 Our Algorithm

  • The sign of T_LF identifies whether D=P or D=Q because its target has opposite signs under the two hypotheses.T_LF is an unbiased estimator of the signed difference of squared distances.Source: §4.1 · p. 6

4.1.2 Expectation, Variance, and Correctness

  • Conditional on a valid flattening realization, the proof bounds the statistic’s variance relative to the fourth power of the flattened P–Q distance.The sign-based decision then succeeds when the statistic’s deviation is controlled.Source: §4.1.2 · p. 7
  • Poissonized testing batches are implemented with fixed budgets by drawing twice each budget and using the first Poisson number of samples.The stated overflow probability and other error terms sum to at most 3/10, below 1/3.Source: §4.1.2 · p. 7

5 Lower Bound

The lower bound shows that the three conditions in Theorem 1 are necessary up to constant factors. For the regime sD ≤ sP ≤ n/100, it constructs hard instances in which heavy pairs mask the collision information carried by light pairs.

5 Lower Bound

  • The proof establishes that all three conditions in Theorem 1 are necessary up to constant factors for ε in (0, 1/8].For sD ≤ sP ≤ n/100, the third condition is proved by making the induced sample distributions hard to distinguish when the budget is too small.Source: §5 · p. 7, §5.1 · p. 8
  • The first two conditions follow by reducing an asymmetric tester to a symmetric one with the same sD and unchanged α.For the third condition, the proof also uses a one-distribution-known LFHT lower bound when sP is sufficiently large.Source: §5 · p. 8

5.1 Proof for the Case sD ⩽sP ⩽

  • Heavy pairs create uninformative within-pair collisions that mask the informative collisions on light pairs.A single light-pair sample has the same distribution under both hypotheses; D–D and D–Q collisions provide the signals, while D–P collisions do not.Source: §5.1 · p. 8
  • The prior construction yields valid separated instances with high probability, and a sufficiently small sample budget makes the two induced sample distributions too close to distinguish.The contradiction with the testing requirement gives the lower bound for this regime.Source: §5.1 · pp. 9–10

6 Application: Non-Adaptive Distribution 2-Clustering

The paper gives nearly tight non-adaptive sample-complexity bounds for distribution 2-clustering, both when one cluster distribution is known and when both are unknown. It uses exemplar selection followed by LFHT classification, and compares the resulting complexity with adaptive sampling.

6 Application: Non-Adaptive Distribution 2-Clustering

  • The paper establishes nearly tight upper and lower bounds for non-adaptive clustering with one known distribution and with both distributions unknown.The stated characterizations apply for k ≥ 200 and ε ∈ (0, 1/8].Source: §6 · pp. 11–12
  • When both distributions are unknown, the algorithm uses a pivot to find an exemplar from the other cluster, then classifies against both exemplars using asymmetric LFHT.Because allocation is fixed in advance, every distribution in the candidate subset must receive enough samples to become an exemplar.Source: §6 · p. 11
  • With one distribution known, the algorithm finds an exemplar of the other cluster and classifies all distributions against the known distribution and that exemplar using asymmetric LFHT.A uniformity test is run on every member of a subset to find the unknown-cluster exemplar.Source: §6 · p. 11
  • The lower-bound reductions turn a clustering algorithm into a tester by planting distributions at lightly sampled indices and using the induced sample budgets.The both-unknown analysis uses a three-way sample tradeoff; the unequal-samples closeness-testing construction alone gives a weaker bound.Source: §6 · pp. 11–12
  • The non-adaptive-to-adaptive sample-complexity ratio is eO(k^1/4) throughout the stated parameter range.The upper limit is attained up to logarithmic factors when n=k and ε is constant.Source: §6 · p. 12

7 Conclusion

The paper characterizes feasible asymmetric LFHT sample budgets up to logarithmic factors and applies the characterization to non-adaptive distribution 2-clustering.

7 Conclusion

  • With n samples from one reference and n^3/4 from the other, O-tilde(n^1/4) target samples suffice, versus Omega(sqrt(n)) required by prior work.The paper also reports an adaptivity gap of up to O-tilde(k^1/4) for non-adaptive 2-clustering.Source: §7 · p. 12
  • The paper characterizes feasible asymmetric LFHT sample-budget triples (s_P, s_Q, s_D) up to logarithmic factors.Source: §7 · p. 12
  • The characterization yields optimal non-adaptive distribution 2-clustering sample complexity up to logarithmic factors and an adaptivity gap of up to O-tilde(k^1/4).Source: §7 · p. 12

AI Disclosure

The authors disclose AI assistance with a lower-bound proof and proof checking, while taking responsibility for the paper’s results and presentation.

AI Disclosure

  • An AI model helped develop the Section 5 lower bound and check most other proofs; the authors reworked the argument and accept responsibility for correctness and presentation.Source: AI Disclosure · p. 12

A Proofs for the Upper Bound

The appendix proves upper-bound tools for flattening distributions and controlling the test statistic’s variance, then uses these bounds to analyze the statistic.

A.1 Flattening

  • Flattening splits each element into B_i pieces of mass p(i)/B_i, with B_i=1+N(i); concentration and a union bound control the largest resulting masses for P and Q.When s_P p(i) is large, the proof uses a Chernoff bound to ensure enough pieces; otherwise the original mass is already small enough.Source: §A.1 · p. 14

A.2 Poisson Moments and Variance

  • For independent Poisson counts with means lambda and mu, the product variance is lambda^2 mu + lambda mu^2 + lambda mu.The appendix adapts quadratic-statistic analysis to independent Poisson batches with unequal sizes.Source: §A.2 · pp. 14–15
  • The TLF statistic is decomposed into four signed components, and its variance is bounded by a constant-factor sum of their variances.Source: §A.2 · p. 15

A.3 Norm Bounds

  • Conditional on a flattening sample satisfying Lemma 2, the statistic’s expectation is -Delta^2 when D=P and Delta^2 when D=Q, while the proof bounds its variance using norm bounds.The stated lemma assumes s_P >= s_Q ≳ s_D.Source: §A.3 · p. 16

B Proofs for the Lower Bound

The lower-bound proof constructs priors with high-probability instances that retain separation, then relates fixed-sample testing to testing with Poisson sample counts.

B Proofs for the Lower Bound

  • With probability at least 24/25, event E holds, ensuring total mass M is at least 1/5 and dTV(P,Q) is at least epsilon.On heavy pairs the weights coincide, while each light pair contributes 8 epsilon/n to their L1 distance.Source: B Proofs for the Lower Bound · p. 17
  • Any algorithm using the stated fixed sample sizes can be converted to a Poisson-sample algorithm by retaining the required samples when all three batches are large enough.The lemma assumes 1 <= s_D <= s_P <= n/100 and s_Q >= 1.Source: B Proofs for the Lower Bound · p. 18
  • The reduction bounds the resulting error below 2/5 by combining the LFHT error with the failure probabilities of events E and F.Source: B Proofs for the Lower Bound · p. 18

B.1 Proof of Lemma 6

This section establishes lower bounds for non-adaptive 2-clustering by reducing it to LFHT, including settings with one or both cluster distributions known. It also develops clustering upper bounds for those settings using screening or exemplar selection with asymmetric LFHT.

B.1 Proof of Lemma 6

  • The proof of Lemma 6 compares heavy- and light-pair count probabilities; the difference B(y,z) vanishes unless |z| ≥ 1 and |y| + |z| ≥ 2.For a light pair, the two possible Q-weight orientations are averaged; under Λ₁, D = Q, so the combined Q- and D-counts share the same orientation.Source: §B.1 · pp. 18–19

B.2 Average-Case Lower Bound

  • The average-case lower bound remains valid when error is at most 1/3 under each conditional prior Λβ(· | E); the proof adjusts only its Poissonization step.Adding Pr(Eᶜ) ≤ 1/25 and Pr(Fᶜ | E) < 10⁻³ yields the same unconditioned error bound, less than 2/5.Source: §B.2 · p. 21

C.1.1 Baseline

  • The baseline with one known distribution runs a uniformity test on each input against U, using the identity tester of Diakonikolas and Kane (2016, Proposition 2.7).The tester applies throughout the parameter range; the proof cites Paninski (2008) for sparse-regime uniformity testing.Source: §C.1.1 · p. 22

C.1.2 Improved Upper Bound

  • The one-known-distribution algorithm screens a random subset for a nonuniform input, then classifies all inputs by asymmetric LFHT against the known uniform distribution.Stage 1 costs eO(k√n/(rε²)) and succeeds with probability at least 7/9; the LFHT budgets require s₂ ≳ 1/ε² and s₁s₂ = rs₂² ≳ n/ε⁴ before polylogarithmic increases.Source: §C.1.2 · pp. 22–23

C.2.1 Baseline

  • The baseline with both distributions unknown chooses a pivot and runs a closeness test between it and each other input, reusing the pivot's samples.The proof cites Chan et al. (2014) for the closeness test.Source: §C.2.1 · p. 23

C.2.2 Improved Upper Bounds

  • s_Qs_D ≳ nα/ε⁴ and s_P² ≳ nα/ε⁴, with s_D ≳ 1/ε², suffice for the LFHT stage; when n ≲ r log k, all three terms are eO(k/ε²).Here α = max{1, n/s_P }; the two-stage algorithm first finds exemplars from opposite clusters, then classifies all inputs against them.Source: §C.2.2 · pp. 23, 25

C.3 Lower Bounds

  • A clustering algorithm with total budget T yields an LFHT tester with s_P = T and s_Q = O(Tr^k), to which the lower bounds apply with one or both distributions known.Source: §C.3 · p. 25
  • Repeating the clustering algorithm a constant number of times and taking a majority output raises success probability to at least 99/100, multiplies T by a constant, and preserves non-adaptivity.Source: §C.3 · p. 25

C.3.1 The Reduction from LFHT

The reduction turns a non-adaptive clustering algorithm into an LFHT tester by placing the unknown distribution at a lightly sampled index. Applying LFHT bounds yields clustering characterizations in both known- and unknown-distribution settings, while comparison with adaptive sampling gives an adaptivity-gap bound.

C.3.1 The Reduction from LFHT

  • Non-adaptivity lets the reduction use a smaller Q-budget, O(Tr/k), instead of T samples from each reference as in the earlier reduction.The unknown D is placed at a lightly sampled index, and an averaging argument chooses one whose candidate partition is rarely returned under D = P.Source: §C.3.1 · pp. 25–26

C.3.2 Application with One Known Distribution

  • With one cluster distribution known, applying the reduction to the average-case LFHT lower bound and combining it with Theorem 14 proves the characterization.The proof takes the large-cluster distribution to be U.Source: §C.3.2 · p. 27

C.3.3 Application with Both Distributions Unknown

  • With both cluster distributions unknown, the known-distribution lower bound still applies, and hard pairs yield an additional bound that, with Theorem 16, proves the characterization.The proof uses the common distribution of hard pairs conditioned on E.Source: §C.3.3 · pp. 27–28

C.4 Proof of the Adaptivity Gap

  • T_na/T_a = eO(k^1/4), and the Section 6 example attains this adaptivity-gap bound up to logarithmic factors.The proof compares the non-adaptive and adaptive complexities.Source: §C.4 · p. 28

D Extension to Multiple Hypotheses

For testing among d candidate distributions, the paper characterizes feasibility through the two least-sampled candidates and the target budget. Its upper bound uses amplified pairwise tests, while its lower bound reduces to pairwise testing.

D Extension to Multiple Hypotheses

  • The upper bound runs amplified pairwise comparisons and outputs the candidate that wins all its comparisons.O(log d) repetitions reduce the per-comparison error to at most 1/(3d), with repetitions reused across comparisons.Source: D Extension to Multiple Hypotheses · p. 28
  • The pairwise problem with reference budgets s(2) and s(1) controls feasibility for d candidates, up to an O(log d) amplification factor in each sample size.The lower-bound reduction embeds the pairwise problem on [n−1] using those two budgets and sD.Source: D Extension to Multiple Hypotheses · pp. 28–29
Loading 2610.29798v1…