Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions

We give a general unified method that can be used for $L_1$ {\em closeness testing} of a wide range of univariate structured distribution families. More specifically, we design a sample optimal and computationally efficient algorithm for testing the equivalence of two unknown (potentially arbitrary) univariate distributions under the ${\mathcal{A}}_k$-distance metric: Given sample access to distributions with density functions $p,q:I\to \mathbb{R}$, we want to distinguish between the cases that $p=q$ and $\mathrm{\parallel }p-q{\mathrm{\parallel }}_{{\mathcal{A}}_k}\ge ϵ$ with probability at least $2\mathrm{/}3$. We show that for any $k\ge 2,ϵ>0$, the {\em optimal} sample complexity of the ${\mathcal{A}}_k$-closeness testing problem is $\Theta(\max{ k^{4/5}/\epsilon^{6/5}, k^{1/2}/\epsilon^2 })$\mathrm{.}Thisisthefirst$o(k)$samplealgorithmforthisproblem,andyieldsnew,simple$L_1$ closeness testers, in most cases with optimal sample complexity, for broad classes of structured distributions.