Wasserstein Identity Testing

10/28/2017

∙

by   Shichuan Deng, et al.

∙

0

∙

share

Uniformity testing and the more general identity testing are well studied problems in distributional property testing. Most previous work focuses on testing under L_1-distance. However, when the support is very large or even continuous, testing under L_1-distance may require a huge (even infinite) number of samples. Motivated by such issues, we consider the identity testing in Wasserstein distance (a.k.a. transportation distance and earthmover distance) on a metric space (discrete or continuous). In this paper, we propose the Wasserstein identity testing problem (Identity Testing in Wasserstein distance). We obtain nearly optimal worst-case sample complexity for the problem. Moreover, for a large class of probability distributions satisfying the so-called "Doubling Condition", we provide nearly instance-optimal sample complexity.