Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions

Original · EN

We give a general unified method that can be used for L₁ 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 Aₖ-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ₐₖ ≥ ε with probability at least 2/3. We show that for any k ≥ 2, ε>0, the optimal sample complexity of the Aₖ-closeness testing problem is Θ({ k⁴/⁵/ε⁶/⁵, k¹/²/ε² }). This is the first o(k) sample algorithm for this problem, and yields new, simple L₁ closeness testers, in most cases with optimal sample complexity, for broad classes of structured distributions.