Skip to main content
7 of 7
added 23 characters in body
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

wasserstein distance between distributions with bounded ratio

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

dohmatob
  • 6.9k
  • 1
  • 18
  • 76