Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions

2015/08/22 by Diakonikolas, Ilias, Kane, Daniel M., Nikishkin, Vladimir · 2 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.1508.05538

Abstract

We give a general unified method that can be used for L₁ \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 A_k-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 A_k-closeness testing problem is Θ(max\ k^4/5/ε^6/5, k^1/2/ε² \). 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.

Cited by

• Are Two Datasets Close Enough With Statistical Significance? A Kernel Distributional Closeness Testing Approach
• Replicable Distribution Testing

Related

• Optimal Algorithms for Testing Closeness of Discrete Distributions
• A New Approach for Testing Properties of Discrete Distributions
• Near-Optimal Closeness Testing of Discrete Histogram Distributions
• Testing Closeness of Multivariate Distributions via Ramsey Theory
• Local minimax rates for closeness testing of discrete distributions