Which Distribution Distances are Sublinearly Testable?

MaRDI QIDQ4608070zbMATH OpenFDO

Authors

Publication date 15 March 2018

Full work available at URL https://arxiv.org/abs/1708.00002, http://dl.acm.org/citation.cfm?id=3175479

zbMATH Keywords

distribution distancessublinearly testable

Mathematics Subject Classification ID

Characterization and structure theory of statistical distributions (62E10) Nonparametric hypothesis testing (62G10) Analysis of algorithms and problem complexity (68Q25)

Abstract: Given samples from an unknown distribution $p$ and a description of a distribution $q$, are $p$ and $q$ close or far? This question of "identity testing" has received significant attention in the case of testing whether $p$ and $q$ are equal or far in total variation distance. However, in recent work, the following questions have been been critical to solving problems at the frontiers of distribution testing: -Alternative Distances: Can we test whether $p$ and $q$ are far in other distances, say Hellinger? -Tolerance: Can we test when $p$ and $q$ are close, rather than equal? And if so, close in which distances? Motivated by these questions, we characterize the complexity of distribution testing under a variety of distances, including total variation, $el{l}_2$, Hellinger, Kullback-Leibler, and $ch{i}^2$. For each pair of distances $d_1$ and $d_2$, we study the complexity of testing if $p$ and $q$ are close in $d_1$ versus far in $d_2$, with a focus on identifying which problems allow strongly sublinear testers (i.e., those with complexity $O(n^{1-gamma})$ for some $gamma>0$ where $n$ is the size of the support of the distributions $p$ and $q$). We provide matching upper and lower bounds for each case. We also study these questions in the case where we only have samples from $q$ (equivalence testing), showing qualitative differences from identity testing in terms of when tolerance can be achieved. Our algorithms fall into the classical paradigm of $ch{i}^2$-statistics, but require crucial changes to handle the challenges introduced by each distance we consider. Finally, we survey other recent results in an attempt to serve as a reference for the complexity of various distribution testing problems.

Recommendations

• Optimal algorithms for testing closeness of discrete distributions
• Sublinear algorithms for testing monotone and unimodal distributions
• Is submodularity testable?
• Testing closeness of discrete distributions
• Distribution-free tests of subhypotheses
• Distribution-free testing for monomials with a sublinear number of queries
• Near-Optimal Closeness Testing of Discrete Histogram Distributions
• Distribution testing lower bounds via reductions from communication complexity
• Distribution testing lower bounds via reductions from communication complexity
• Distribution-free testing algorithms for monomials with a sublinear number of queries

Cited in

(15)

• Hypothesis testing for high-dimensional multinomials: a selective review
• Analysis of COVID-19 evolution based on testing closeness of sequential data
• An automatic inequality prover and instance optimal identity testing
• _p testing and learning of discrete distributions
• Sample-optimal identity testing with high probability
• Distribution testing lower bounds via reductions from communication complexity
• Near-Optimal Closeness Testing of Discrete Histogram Distributions
• Distribution testing lower bounds via reductions from communication complexity
• Collision-based Testers are Optimal for Uniformity and Closeness
• Optimal algorithms for testing closeness of discrete distributions
• Testing closeness of discrete distributions
• Sublinear time algorithms for earth mover's distance
• Local goodness-of-fit testing for Hölder-continuous densities: minimax rates
• Complexity of high-dimensional identity testing with coordinate conditional sampling
• Testing product distributions: a closer look

This page was built for publication: Which Distribution Distances are Sublinearly Testable?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608070)