Consider the importance sampling estimation error $$ e_n(f) = \int f d\mu - \frac{1}{n}\sum_{i=1}^n f(x_i) \rho(x_i), \qquad x_i \sim \lambda,\, \rho = \tfrac{d\mu}{d\lambda}, $$ where $\mu$ and $\lambda$ the target and proposal distributions, respectively. I know a few probabilistic upper bounds on $|e_n(f)|$, from $$ \text{Var}(e_n(f)) \le \frac{\|\rho\|_\infty \|f\|_{L^2(\mu)}^2 }{n}, $$ which can be refined to $$ \mathbb{E}|e_n(f)| \le \|f\|_{L^2(\mu)}\left( \sqrt{a}/\sqrt{n} +2 \sqrt{\mathbb{P}(\rho(X) > a)} \right), \quad \forall a > 0,\, X \sim \mu. $$ Similarily to the first inequality, we have $$ \text{Var}(e_n(f)) \le \frac{\|f\|_\infty^2 D_{\chi^2}(\mu, \lambda) }{n}. $$ The first and the third inequalities are immediate; the second inequality is from Chatterjee and Diaconis (2015)). Here $d_{\chi^2}(\mu, \lambda) = \int \rho d\mu - 1$.

Question. What are other known (and interesting) approaches to bounding $e_n$ in probability?

I did some research, but couldn't find anything more. (I could be using the wrong keywords; the references I found were very applied.)

Note. I'm not interested in asymptotic results, unless they come with an explicit convergence rate. The error should be quantified when approximations are used.

Background on importance sampling.

Let $\mathbb{M}$ be a measurable space, let $\mu$ and $\lambda$ be two probability measures on $\mathbb{M}$, with $\mu$ absolutely continuous with respect to $\lambda$, and let $f : \mathbb{M} \rightarrow \mathbb{R}$ be measurable. The problem is to estimate $$ I = \int f d\mu $$ given a random sample $\{x_i\}_{i=1}^n$ from $\lambda$. The (un-normalized) importance sampling estimate of $I $ is $$ I_n = \frac{1}{n} \sum_{i=1}^{n} f(x_i)\tfrac{d\mu}{d\lambda}(x_i). $$


Your Answer

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

Browse other questions tagged or ask your own question.