Minimax estimation of the Wasserstein distance in the spiked transport model
Jonathan Niles-Weed (New York University)
The Monge–Kantorovich or Wasserstein distance between probability measures is the central object of study in optimal transport. From the statistical standpoint, the fundamental question is how well this object can be estimated from random data. We give a nearly sharp answer to this question, showing that a naive estimator is essentially unimprovable. Motivated by applications in biology, we propose a new statistical model, the spiked transport model, under which there does exist a strictly better estimator. This estimator takes exponential time to compute, and we give evidence that this limitation is fundamental, that is, that any computationally efficient estimator is bound to suffer from significantly worse performance.