Which distribution distances are sublinearly testable?

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 [VV11a, ADK15, DP17], 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, ℓ₂, Hellinger, Kullback-Leibler, and χ². For each pair of distances d₁ and d², we study the complexity of testing if p and q are close in d₁ versus far in d₂, with a focus on identifying which problems allow strongly sublinear testers (i.e., those with complexity O(n^1−γ) for some γ > 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 χ²-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.