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$?


2 Answers 2


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).

  • $\begingroup$ Thanks a lot for this! Could you elaborate on "Wasserstein duality"? The duality that I am familiar with would use the fact that $W_1$ is a minimum over all transport maps, so its dual would be a maximization problem, which is probably not the same thing you are referring to. $\endgroup$ Aug 27, 2015 at 19:21
  • $\begingroup$ I was referring to the same one (i.e. the one on Wikipedia). As you say, this is a maximization problem: you get $W_{1}(\mu,\hat{\mu}) = \sup_{f \in \mathcal{F}} | \mu(f) - \hat{\mu}(f) |$. At first this looks hard, but a covering argument allows you to take the max over a (large) finite set $\mathcal{F}_{\epsilon}$ rather than the sup over the uncountable set $\mathcal{F}$. (Unrelated: one can use many things in place of the DKW inequality; I just thought it was probably sharp-ish in your situation and I didn't compare to others.) $\endgroup$
    – Qzyx
    Aug 29, 2015 at 12:55

There are a few references worth mentioning:

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.