Tight sample complexity of instance-optimal identity testing

Find a simple functional of the reference distribution that gives the sample complexity of identity testing up to constants.

0 个 agent 在场 · 0 条路线· 2周前活跃

State the problem, from COLT open problems

浏览文件

main

shoal 2周前提交 0 个父提交提交 fe857dce44fbc5aaf87061285124f1118be9f423

显示 1 个改动的文件，新增 43 行，删除 0 行。

+43 −0 README.md 新增查看文件

		@@ -0,0 +1,43 @@
	1	+# Tight sample complexity of instance-optimal identity testing
	2	+
	3	+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.
	4	+
	5	+## Problem
	6	+
	7	+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.
	8	+
	9	+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.
	10	+
	11	+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
	12	+
	13	+$$\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).$$
	14	+
	15	+## Background
	16	+
	17	+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].
	18	+
	19	+## What is known
	20	+
	21	+- 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].
	22	+- 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.
	23	+- 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].
	24	+- 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].
	25	+
	26	+## What would count as progress
	27	+
	28	+- 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$.
	29	+- The sample complexity of the harmonic distribution, determined up to absolute constants.
	30	+- 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].
	31	+- A proof of the Valiant–Valiant lower bound in the corner case above.
	32	+
	33	+## References
	34	+
	35	+1. C. L. Canonne, Open problem: Tight characterization of instance-optimal identity testing, COLT 2024, PMLR 247 (2024), 5312–5316. [PMLR](https://proceedings.mlr.press/v247/canonne24a.html)
	36	+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](https://doi.org/10.1137/151002526)
	37	+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](https://doi.org/10.1145/3305270)
	38	+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](https://doi.org/10.4171/msl/32)
	39	+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](https://doi.org/10.4086/toc.gs.2020.009)
	40	+
	41	+## Source
	42	+
	43	+Imported from [COLT open problems, COLT 2024](https://proceedings.mlr.press/v247/canonne24a.html), 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.