Statistical inference · Statistical learning theory / Open question
The True Sample Cost of Distribution Testing
Two distributions with equally large support can require very different amounts of data to distinguish from a reference. A sharp instance-dependent bound would capture that difference.
Seed catalog · Showing the bundled record.
Problem statement
Given a rational distribution on symbols and , let be the least fixed sample size for testing against , with both error probabilities at most . Find a functional computable in polynomial time in the binary input length such that for universal positive constants. The approximation must use the same on both sides, including near-point-mass references.
Assumptions and scope
- The tester receives ordinary i.i.d. samples from arbitrary unknown p and the full explicit q; conditional sampling and other strengthened oracles are excluded. Total variation is one half the l1 distance.
- The finite-rational, polynomial-time-functional formulation makes the source's 'succinctness' requirement precise. The characterization concerns statistical sample complexity, not a tautological definition through an optimal test.
- For the Valiant–Valiant benchmark, Phi_VV(q,rho) is the two-thirds quasinorm after deleting q's largest entry and a maximal smallest-probability tail of mass at most rho. The known upper bound uses max{1/epsilon, Phi_VV(q,epsilon/16)/epsilon^2}; the nominal lower counterpart uses epsilon, not epsilon/16.
What would settle it?
An efficiently evaluable constant-factor characterization valid at the original accuracy for every finite rational reference, with upper and lower testing proofs. Replacing epsilon by a constant multiple is insufficient when that changes sample complexity by an unbounded factor.
Selected for a theoretical or computational target. A fitted scaling curve or improved benchmark score alone does not establish the stated learning-theoretic guarantee.
Status and evidence
The worst-case Theta(sqrt(k)/epsilon^2) rate is known. Canonne's Question 1 explains why existing truncated-norm and separation-radius results leave an arbitrarily large instancewise gap. Section 4 flags a lower-bound proof gap near point masses; this corner cannot be silently assumed settled. Our polynomial-time functional is an explicit specialization of the source's succinctness requirement. This is an editorial reformulation of a published open problem. The preliminary review through 2026-11-19 does not certify novelty or exclude an unlocated resolution.
Preliminary source check; not an expert-verified open status or an independent audit of proposed proofs. The compilation date is not a literature-review cutoff.
Sources and further reading
- Canonne — Open Problem: Tight Characterization of Instance-Optimal Identity Testing ↗problem statement · source checked 2026-11-19
All five PDF pages checked: Question 1 asks for a constant-factor characterization at the same epsilon. Trimming at epsilon versus epsilon/16 can create an arbitrarily large gap; Section 4 also flags a lower-bound proof gap near point masses.
- Valiant and Valiant — An Automatic Inequality Prover and Instance Optimal Identity Testing ↗partial theory · source checked 2026-11-19
Truncated two-thirds-quasinorm bounds checked through Canonne's equations (1)–(3). The full proof was not independently read; retain the later source's explicit near-point-mass qualification.