Tight sample complexity of instance-optimal identity testing

You know a distribution $q$ exactly and receive samples from an unknown $p$. How many samples do you need to tell whether $p$ equals $q$ or is far from it? The answer depends on $q$, and the best characterizations of that dependence are loose by factors that can be arbitrarily large.

Problem

Let $q$ be a probability distribution on a countable set $X$, given explicitly, and let $\varepsilon \in (0, 1]$. A tester receives $q$, $\varepsilon$ and $n$ independent samples from an unknown distribution $p$ on $X$. It must accept with probability at least $2/3$ if $p = q$, and reject with probability at least $2/3$ if $d_{\mathrm{TV}}(p, q) > \varepsilon$, where $d_{\mathrm{TV}}(p, q) = \sup_{S \subseteq X} (p(S) - q(S))$. Let $n(q, \varepsilon)$ be the least $n$ for which such a tester exists.

Question. Is there a succinct functional $\Phi(q, \varepsilon)$, with a closed form or efficiently computable from $q$, such that $n(q, \varepsilon) = \Theta(\Phi(q, \varepsilon))$ up to absolute constant factors? If so, what is it? If not, prove that no such functional exists.

The leading candidate comes from Valiant and Valiant [2]. Sort $q$ in non-increasing order, delete its largest entry, then delete as many of the smallest entries as possible while their total mass stays at most $\varepsilon$, and let $\Phi_{\mathrm{VV}}(q, \varepsilon) = \big(\sum_i q_i^{2/3}\big)^{3/2}$ over the entries that remain. They proved

$$\Omega\Big(\max\Big\{\frac{1}{\varepsilon}, \frac{\Phi_{\mathrm{VV}}(q, \varepsilon)}{\varepsilon^2}\Big\}\Big) \le n(q, \varepsilon) \le O\Big(\max\Big\{\frac{1}{\varepsilon}, \frac{\Phi_{\mathrm{VV}}(q, \varepsilon/16)}{\varepsilon^2}\Big\}\Big).$$

Background

Identity testing, or goodness of fit, is a basic problem of statistics and of distribution testing in computer science. Over all distributions on $k$ elements the answer is known up to constants: $\Theta(\sqrt{k}/\varepsilon^2)$ samples [5]. That worst case is attained by the uniform distribution and hides how much easier testing can be for a concentrated $q$, or for $q$ on an infinite domain. Valiant and Valiant introduced the instance-optimal version in 2014, where the sample complexity is a function of $q$ itself [2]. Canonne posed the question of a tight characterization at COLT 2024, offering a prize of 200 Australian dollars [1].

What is known

• The Valiant–Valiant bounds above differ only in $\varepsilon$ versus $\varepsilon/16$, but that can matter a lot. For the harmonic distribution $q(i) \propto 1/i$ on $k$ elements, $\Phi_{\mathrm{VV}}(q, \varepsilon) = k^{(1-\varepsilon)/2 + o(1)}$, so the two bounds differ by a factor $k^{\Theta(\varepsilon)}$ [1, 3].
• A second characterization. Blais, Canonne and Gur bounded $n(q, \varepsilon)$ through the K-functional between $\ell_1$ and $\ell_2$, $\kappa_q(t) = \inf_{q' + q'' = q} \big(\|q'\|_1 + t \|q''\|_2\big)$, with $\Phi_{\mathrm{BCG}}(q, \varepsilon) = \kappa_q^{-1}(1 - 2\varepsilon)$ [3]. Their bounds are incomparable with those of [2] and show the same kind of gap, again for the harmonic distribution.
• Other distances. Chhor and Carpentier found the optimal separation radius for $\ell_p$ distances, $1 \le p \le 2$; translated into sample complexity, it has the same constant-factor slack in $\varepsilon$ [4].
• A corner case. The lower-bound proof in [2] does not cover reference distributions whose largest probability exceeds $1 - 2\varepsilon$. The poser believes the bound still holds there [1].

What would count as progress

• A functional $\Phi$ together with a tester using $O(\Phi(q, \varepsilon))$ samples and a matching lower bound $\Omega(\Phi(q, \varepsilon))$, both proved for every $q$ and $\varepsilon$.
• The sample complexity of the harmonic distribution, determined up to absolute constants.
• A direct proof relating $\Phi_{\mathrm{VV}}$ to $\Phi_{\mathrm{BCG}}$; at present their relation follows only by comparing the bounds of [2] and [3].
• A proof of the Valiant–Valiant lower bound in the corner case above.

References

1. C. L. Canonne, Open problem: Tight characterization of instance-optimal identity testing, COLT 2024, PMLR 247 (2024), 5312–5316. PMLR
2. G. Valiant and P. Valiant, An automatic inequality prover and instance optimal identity testing, SIAM J. Comput. 46(1) (2017), 429–455; conference version FOCS (2014). doi:10.1137/151002526
3. E. Blais, C. L. Canonne and T. Gur, Distribution testing lower bounds via reductions from communication complexity, ACM Trans. Comput. Theory (2019); conference version CCC (2017). doi:10.1145/3305270
4. J. Chhor and A. Carpentier, Sharp local minimax rates for goodness-of-fit testing in multivariate binomial and Poisson families and in multinomials, Math. Stat. Learn. 5(1–2) (2022), 1–54. doi:10.4171/msl/32
5. C. L. Canonne, A survey on distribution testing: your data is big. But is it blue?, Theory of Computing Graduate Surveys 9 (2020). doi:10.4086/toc.gs.2020.009

Source

Imported from COLT open problems, COLT 2024, curated by the Conference on Learning Theory (COLT). Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.