3
$\begingroup$

Let $p$ and $q$ be probability distributions on a metric space $X=(X, d)$ with densities $dp$ and $dq$, such that there exists $0 < \alpha < \beta < \infty$ satisfying

$$ \alpha d p \le dq \le \beta dp . $$

What is an upper bound for the Wasserstein distance $W_d(p,q)$ ?

Notes: $W_d(p, q) := \sup_{\|f\|_{\text{Lip}} \le 1} |\mathbb E_{x \sim p}[f(x)] - \mathbb E_{x \sim q}[f(x)]|$


Update

It's well known (e.g see Gabe K's response below or Theorem 4 of this paper) that

$$ W_d(p, q) \le \operatorname{diam}(X)\operatorname{TV}(p, q). $$

Thus if $X$ has finite diameter, it suffices to bound $\operatorname{TV}(p, q)$.

Recall the definition of total variation,

$$ \operatorname{TV}(p, q) := \sup_{A \subseteq X} \left|\int_A dq-\int_A dp\right|. $$ Now, for any $A \subseteq X$, one has $ \int_A dq - \int_A dp \ge \int_A(\alpha-1)dp = (\alpha-1)p(A). $ Similarly, one has $\int_A dq - \int_A dp \le (\beta-1)p(A)$. Thus $$ \left|\int_A dq - \int_A dp \le (\beta-1)p(A)\right| \le \max(1-\alpha,\beta-1)p(A) \le \max(1-\alpha,\beta-1), $$ and so $\operatorname{TV}(p,q) \le \max(1-\alpha,\beta-1)$. Putting things together, we get

$$ W_d(p,q) \le \operatorname{diam}(X)\max(1-\alpha,\beta-1). $$

Case of infinite diameter

In case of infinite diameter assuming that $p$ or $q$ satisfies a Talagrand transportation-cost inequality, i.e

$$W_{d,2}(p,r)\le \sqrt{(2/\rho)\operatorname{kl}(r\|p)} $$ for some $\rho > 0$ and for any distribution $r$ on $X$ relatively continuous w.r.t $p$,

with a similar story for $q$ (e.g for standard Gaussian, this holds with $\rho=1$), allows us to still get an upper bound, namely $$ W_{d,2}(p,q) \le \sqrt{2\min (\beta\log(\beta)/\rho_p,(1/\alpha)\log(1/\alpha)/\rho_q)}. $$

$\endgroup$
  • $\begingroup$ Do you want a bound using only $\alpha$ and $\beta$? $\endgroup$ – gerw Aug 29 '18 at 11:54
  • $\begingroup$ Ya sure, a bound in terms of $\alpha$ and $\beta$ (and perhaps a the diameter of the space $X$ w.r.t $p$ ?!) :) $\endgroup$ – dohmatob Aug 29 '18 at 12:15
  • $\begingroup$ Perhaps the dual form of $W_d(p,q)=\int_0^1 |F^{-1}_p(u)-F^{-1}_q(u) | \mathrm{d}u$ is useful here? $\endgroup$ – Jan Aug 29 '18 at 13:10
  • $\begingroup$ Nope. That's only valid in 1 dimension. $\endgroup$ – dohmatob Aug 29 '18 at 13:12
  • $\begingroup$ Does "densities" here just mean Radon-Nikodym derivatives with respect to some (unspecified, but the same for p and q) measure on $(X,d)$? $\endgroup$ – Steve Aug 29 '18 at 14:44
4
$\begingroup$

Any estimate will need to incorporate the diameter of $X$. To see this, consider the interval $[0,L]$ and the distribution with density,

$$\begin{cases} \frac{2}{L} & 0 \leq x \leq L/3 \\ \frac{1}{2L} & L/3 \leq x \leq L \\ \end{cases} $$

One can calculate the distance from the uniform distribution $1/L$ using the dual formulation of the Wasserstein distance, and it blows up as $L$ goes to infinity. Therefore, we cannot hope for an estimate solely in terms of $\alpha$ and $\beta$.

However, assuming a bound on the diameter $D$ of $X$, then we can say more. With $\alpha$ and $\beta$, we can derive a bound on $\delta(p,q)$ the total variation distance between $p$ and $q$. One possible transfer plan from $p$ to $q$ is to move the excess mass of $p$ to $q$, fixing the overlap. The total mass to be moved then is $\delta(p,q)$, and the cost to move the mass is no more than $D^d$. Skipping some derivations, this shows that the Wasserstein 2-distance is bounded by $D \sqrt{ \delta(p,q)}$, so this gives your desired result. This can be generalized to the other Wasserstein metrics as well.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ sure. Thanks for the response (upvoted). Sure, I suspected it involve the diameter of $X$ w.r.t to $p$. See my comment section above. More precisely, it would involve something like $\sup_{x_0} \mathbb E_{x \in p} d(x,x_0)$ (which is $\le D$). $\endgroup$ – dohmatob Aug 29 '18 at 15:03
  • 1
    $\begingroup$ OK, i can workout $TV(p,q) \le \max(1-\alpha,\beta-1)$ and so $W_d(p,q) \le \max(1-\alpha,\beta-1)\operatorname{diam}(X)$ $\endgroup$ – dohmatob Aug 29 '18 at 17:16
  • $\begingroup$ Also this document provides numerous useful inequalities between metrics on probability measures math.hmc.edu/~su/papers.dir/metrics.pdf. In general to upper bound $W$ metric with another metric, you need an upper bound on the diameter of the metric space. $\endgroup$ – dohmatob Aug 29 '18 at 17:19
  • 1
    $\begingroup$ Actually, in case of infinite diameter assuming that $p$ and $q$ both satisfy the Talagrand transportation-cost inequality, i.e $W_{d,2}(p,r)\le \sqrt{(2/\rho)\operatorname{kl}(r\|p)}$ for any distribution $r$ on $X$ relatively continuous w.r.t $p$, with a similar story for $q$ (e.g for standard Gaussian, this holds with $\rho=1$), allows us to still get an upper bound, namely $w_{d,2}(p,q) \le \sqrt{2\min (\beta\log(\beta),(1/\alpha)\log(1/\alpha))/\rho}$. $\endgroup$ – dohmatob Aug 30 '18 at 4:20
  • $\begingroup$ For sure. In fact, you only need to assume that either $p$ or $q$ (not both) satisfies a log-Sobolev inequality to get this. This estimate depend on the $\rho$ in the log-Sobolev inequality, so this introduces another ingredient while eliminating the diameter. $\endgroup$ – Gabe K Aug 30 '18 at 14:20

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.