Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions

We give a general unified method that can be used for L1 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 Ak-distance metric: Given sample access to distributions with density functions p, q: I → ℝ, we want to distinguish between the cases that p=q and |p-q|Ak ≥ ε with probability at least 2/3. We show that for any k ≥ 2, ε>0, the em optimal sample complexity of the Ak-closeness testing problem is Theta(max k4/5/ε6/5, k1/2/ε2 ). This is the first o(k) sample algorithm for this problem, and yields new, simple L1 closeness testers, in most cases with optimal sample complexity, for broad classes of structured distributions.