Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions
Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin · 2015
We give a general unified method that can be used for L1closeness 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 → R, 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 optimal sample complexity of the Ak-closeness testing problem is Θ(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.