Which Distribution Distances are Sublinearly Testable?

zbMATH Open1409.62043arXiv1708.00002MaRDI QIDQ4608070

Author name not available (Why is that?)

Publication date: 15 March 2018

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,

e l l_{2}

, Hellinger, Kullback-Leibler, and

c h 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 - g a m m a})

for some

g a m m a > 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

c h 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.

Full work available at URL: https://arxiv.org/abs/1708.00002

zbMATH Keywords

distribution distances sublinearly testable

Mathematics Subject Classification ID

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