Practical bounds for the Wasserstein distance in 2 dimensions

Question

Let $X_1,\dots,X_n$ be a set of independent samples of a distribution $\mu$ on the unit square, let $\hat\mu_n$ be the empirical distribution on the points $X_1,\dots,X_n$, and let $W_1(\mu,\hat\mu_n)$ denote the $1$-Wasserstein distance between $\hat\mu_n$ and $\mu$. Are there any simple, concrete bounds on $\Pr(W_1(\mu,\hat\mu_n)\geq t)$, where $n\leq 100$ and $t$ is fairly large (e.g. order of $n^{-1/2}$)?.

There are many results that describe the asymptotic behavior of this quantity, such as the papers http://www.emis.ams.org/journals/EJP-ECP/article/download/958/1147.pdf and http://link.springer.com/article/10.1007/s00440-014-0583-7 , but these tend to take the form of existence proofs and limiting statements (e.g. "There exist constants $C$ and $c$ such that $\Pr(W_1(\mu,\hat\mu_n)\geq t)\to (*)$). Are there any simple "ad-hoc" bounds that can bound $\Pr(W_1(\mu,\hat\mu_n)\geq t)$ for fixed values of $n$ and $t$?

Answer 1

Sorry, I don't have the reputation to comment.

1. Most of the bounds in the first paper you cite are completely explicit as you go through the proofs, and can be used to obtain a bound of the form you want. Of course, the constants they write down are a little more complicated than the ones you normally get in e.g. Hoeffding's inequality, but you can always do something a little bit lazy.

2. You can get rather poor bounds without much work by combining the Dvoretzky–Kiefer–Wolfowitz inequality, the Wasserstein duality theorem and a covering argument. An argument would go something like: A. By Wasserstein duality, $W_{1}(\mu, \hat{\mu}) \leq \sup_{f \in \mathcal{F}} | \mu(f) - \hat{\mu}(f) |$ for some `nice' family $\mathcal{F}$. B. By a covering argument, for all $\epsilon > 0$ there exists a finite set $\mathcal{F}_{\epsilon} \subset \mathcal{F}$ s.t. $W_{1}(\mu, \hat{\mu}) \leq \sup_{f \in \mathcal{F}_{\epsilon}} | \mu(f) - \hat{\mu}(f) | + \epsilon$. C. Look at a particular $f \in \mathcal{F}_{\epsilon}$. The Dvoretzky–Kiefer–Wolfowitz theorem gives us a bound on $P[ | \mu(f) - \hat{\mu}(f) | > \epsilon]$. Taking a union bound over $f \in \mathcal{F}_{\epsilon}$ and applying 2.B gives the result you want.

Unfortunately, I don't remember where to find the `right' covering argument for the 1-Wasserstein distance and the unit square (the details of which Wasserstein distance you're using and the target space make a difference to the efficiency of this bound).

Answer 2

There are a few references worth mentioning:

• https://hal.archives-ouvertes.fr/hal-00915365/document
• https://www.lpsm.paris/pageperso/bolley/bgv.pdf
• https://arxiv.org/pdf/1804.10556.pdf

Example of a bound you could hope to get

Let $d \ge 2p$ be the dimensionality of your square. Suppse $\mu$ is light-tailed, i.e suppose there exists $\alpha > p$ such that $\int \exp(|X|^\alpha) d\mu < \infty $. Then for every $t > 0$, one has $$ P(W_p(\mu,\hat{\mu}_n) \ge t) \le \begin{cases}c_1\exp(-c_2Nt^{d/p}),&\mbox{ if }t \le 1,\\ c_1\exp(-c_2Nt^{\alpha/p}),&\mbox{ else,}\end{cases} $$ where $c_1$ and $c_2$ are positive constants independent of $N$ and $t$. This is a direct consequence of Theorem 2 of the first paper.

You can get an even finer bound by using Proposition 10.