How to choose best proposal distribution for importance sampling

Question

From Robert & Casella p95, we know that the choice of proposal distribution $g(x)$ with minimal variance is the $g$ proportional to $|h(x)|f(x)$. If we restrict our proposal distribution to cetain function class, for example, The normal distribution $N(\mu,\sigma^2)$, is there an algorithm to choose best parameter $\mu$ and $\sigma$ that is most "proportional" to $|h(x)|f(x)$? I mean, is there a score for the "proportionality" between 2 functions?

Answer 1

This is definitely an interesting question, but there is no clear answer as far as I can tell. Indeed, first, one has to define a criterion to optimise. For instance, this could be the variance: $$\min_{\mu,\sigma}\,\text{var}_{\mu,\sigma}\, h(X)f(X)\big/g_{\mu,\sigma}(X)$$or equivalently$$\min_{\mu,\sigma}\,\int \frac{h^2(x)f^2(x)}{g_{\mu,\sigma}(x)}\,\text{d}x$$for which there does exist a solution but one that is unlikely to be derived analytically. In a series of papers on population Monte Carlo methods that we wrote between 2005 and 2008, we construct a sequence of $\mu,\sigma$ towards deriving this optimum. Here is another reference aiming at an optimal step function.

Other criteria could be used though, like minimising a functional distance between $|h(\cdot)|f(\cdot)$ and $g_{\mu,\sigma}(\cdot)$: $$\min_{\mu,\sigma}\,\mathcal{H}\{|h(\cdot)|f(\cdot),g_{\mu,\sigma}(\cdot)\}$$ where $\mathcal{H}$ can be the Hellinger distance, the Kullback-Leibler distance, the Wasserstein distance, or something else.

The second issue is about the derivation of this optimum, which like the original one (which derivation dates back to the early days of importance sampling and not to our book),is most likely unavailable in realistic settings.

Answer 2

According to the paper "The sample size required in importance sampling" (Chatterjee & Diaconis, 2007, https://arxiv.org/pdf/1511.01437.pdf) the sample size required for importance sampling is approximately $$ \exp (D_{KL}(|h(\cdot)|f(\cdot) \ || \ g)) $$ Therefore, $D_{KL}(|h(\cdot)|f(\cdot) \ || \ g)$ should be used as a criterion if computationally tractable.