2024-06-30-canonne24a.md

title	section	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
Open Problem: Tight Characterization of Instance-Optimal Identity Testing	Open Problems	In the “instance-optimal” identity testing introduced by Valiant and Valiant (2014), one is given the (succinct) description of a discrete probability distribution $q$, as well as a a parameter $\varepsilon\in(0,1]$ and i.i.d. samples from an (unknown, arbitrary) discrete distribution $p$. The goal is to distinguish with high probability between the cases (i) $p=q$ and (ii) $\textrm{TV}(p,q) > \varepsilon$, using the minimum number of samples possible as a function of (some simple functional of) $q$ and $\varepsilon$. This is in contrast with the standard formulation of identity testing, where the sample complexity is taken as worst-case over all possible reference distributions $q$. Valiant and Valiant provided upper and lower bounds on this question, where the sample complexity is expressed in terms of the “$\ell_{2/3}$ norm” of some (truncated version) of the reference distribution $q$. However, these upper and lower bounds do not always match up to constant factors, and can differ by an arbitrary multiplicative gap for some choices of $q$. The question then is: what is the tight characterization of the sample complexity of instance-optimal identity testing? What is the “right” functional $\Phi(q)$ for it?	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	canonne24a	0	Open Problem: Tight Characterization of Instance-Optimal Identity Testing	5312	5316	5312-5316	5312	false	Canonne, Cl\'ement	given family Clément Canonne	2024-06-30		Proceedings of Thirty Seventh Conference on Learning Theory	247	inproceedings	date-parts 2024 6 30	https://proceedings.mlr.press/v247/canonne24a/canonne24a.pdf