Optimal Algorithms for Testing Closeness of Discrete Distributions

Abstract

We study the question of closeness testing for two discrete distributions. More precisely, given samples from two distributions $p$ and $q$ over an $n$-element set, we wish to distinguish whether $p=q$ versus $p$ is at least $\eps$-far from $q$, in either ${\ell }_1$ or ${\ell }_2$ distance. Batu et al. gave the first sub-linear time algorithms for these problems, which matched the lower bounds of Valiant up to a logarithmic factor in $n$, and a polynomial factor of $\eps.$ In this work, we present simple (and new) testers for both the ${\ell }_1$ and ${\ell }_2$ settings, with sample complexity that is information-theoretically optimal, to constant factors, both in the dependence on $n$, and the dependence on $\eps$; for the ${\ell }_1$ testing problem we establish that the sample complexity is $Θ(\max\{n^{2/3}/\eps^{4/3}, n^{1/2}/\eps^2 \}).$

References in corpus (1)

• Testing Distribution Identity Efficiently

Cited by in corpus (52)

• Optimal Testing for Properties of Distributions
• A Survey of Quantum Property Testing
• Differentially Private Testing of Identity and Closeness of Discrete Distributions
• Property Testing of Joint Distributions using Conditional Samples
• Distributed Simulation and Distributed Inference
• Minimax optimality of permutation tests
• Testing Closeness With Unequal Sized Samples
• Near-Optimal Closeness Testing of Discrete Histogram Distributions
• Differentially Private Identity and Closeness Testing of Discrete Distributions
• A Chasm Between Identity and Equivalence Testing with Conditional Queries
• Learning Discrete Distributions from Untrusted Batches
• Instance Optimal Learning
• Private Identity Testing for High-Dimensional Distributions
• ${\ell }_p$ Testing and Learning of Discrete Distributions
• Entanglement is Necessary for Optimal Quantum Property Testing
• Sharp Bounds for Generalized Uniformity Testing
• Pan-Private Uniformity Testing
• Estimating Learnability in the Sublinear Data Regime
• Efficient Intervention Design for Causal Discovery with Latents
• Robust Testing and Estimation under Manipulation Attacks
• Recovering Structured Probability Matrices
• Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning
• Sequential Change Detection by Optimal Weighted ${\ell }_2$ Divergence
• Statistical Inference in the Differential Privacy Model
• Two-Sample Testing on Ranked Preference Data and the Role of Modeling Assumptions
• Testing Markov Chains without Hitting
• Sample Amplification: Increasing Dataset Size even when Learning is Impossible
• Data-Driven Nonparametric Existence and Association Problems
• Sample optimal Quantum identity testing via Pauli Measurements
• Wasserstein Identity Testing
• The Sample Complexity of Robust Covariance Testing
• Testing Product Distributions: A Closer Look
• Quantum Communication Complexity of Distribution Testing
• Quantum Chebyshev's Inequality and Applications
• Second-Order Asymptotically Optimal Statistical Classification
• Optimal Identity Testing with High Probability
• Graph-based Discriminators: Sample Complexity and Expressiveness
• Empirical Distribution of Equilibrium Play and Its Testing Application
• Communication and Memory Efficient Testing of Discrete Distributions
• The Broad Optimality of Profile Maximum Likelihood
• The Price of Tolerance in Distribution Testing
• The Use of Presence Data in Modelling Demand for Transportation
• As Easy as ABC: Adaptive Binning Coincidence Test for Uniformity Testing
• Testing Determinantal Point Processes
• Testing Mixtures of Discrete Distributions
• Testing identity of collections of quantum states: sample complexity analysis
• Testing Properties of Multiple Distributions with Few Samples
• Distribution-free inference for regression: discrete, continuous, and in between
• Goodness-of-Fit Testing for Hölder-Continuous Densities: Sharp Local Minimax Rates
• Inference under Information Constraints III: Local Privacy Constraints
• Asymptotic Distribution and Detection Thresholds for Two-Sample Tests Based on Geometric Graphs
• Spectral methods for testing cluster structure of graphs