The Wasserstein cost of Importance Sampling

Abstract

Importance sampling (IS) consists in biasing samples from a distribution $f$ towards another distribution $g$. Concretely, given samples $X_i$ from $f$, the IS measure is $${\hat{g}}_n=\frac{1}{Z_n}\sum _{i=1}^n\frac{g(X_i)}{f(X_i)}{\delta }_{X_i},$$ with $Z_n={\sum }_{i=1}^n\frac{g(X_i)}{f(X_i)}$. The random measure ${\hat{g}}_n$ approximates $g$, and is used in many contexts ranging from Monte Carlo integration to Bayesian inference. We show that, in high dimension ($d⩾3$), the Wasserstein cost $W_p^p({\hat{g}}_n,g)$ has order $n^{-p/d}$ in expectation, i.e. $${\beta }_{p,d}^{\mathrm{low}}\int g{f}^{-p/d}⩽\underset{n\to \infty }{\mathrm{liminf}}{n}^{p/d}\mathbb{E}[W_p^p({\hat{g}}_n,g)]⩽\underset{n\to \infty }{\mathrm{limsup}}{n}^{p/d}\mathbb{E}[W_p^p({\hat{g}}_n,g)]⩽{\beta }_{p,d}\int g{f}^{-p/d}$$ where $0<{\beta }_{p,d}^{\mathrm{low}}⩽{\beta }_{p,d}$ are constants depending only on $p$ and $d$, which are equal for $p=2$ and conjectured to be equal for any $p⩾1$. Our results are valid for all $p⩾1$ and $d⩾3$. In the case where ${\beta }_{p,d}^{\mathrm{low}}={\beta }_{p,d}$, we show that the asymptotically optimal sampling distribution $f^{\ast }$ for importance sampling is not equal to $g$ but to a tempered version of $g$, namely $f^{\ast }\propto g^{d/(p+d)}$, which is reminiscent of Zador's theorem in the domain of measure quantization.

20 pages