Importance Sampling

1. Importance Sampling

Suppose we want to compute $$I={\mathbb{E}}_{\pi }[\phi (X)]={\int }_{\mathbb{X}}\phi (x)\pi (x)\text{d}x$$ where we do not know how to sample from the target $\pi$ but have access to a proposal or importance distribution of density $q$, satisfying $\pi (x)>0\Rightarrow q(x)>0$, i.e. the support of $q$ includes the support of $\pi$. Then we have $$I={\mathbb{E}}_{\pi }[\phi (X)]={\mathbb{E}}_q[\phi (X)w(X)]$$ where $w:\mathbb{X}\to {\mathbb{R}}^{+}$ is the importance weight function $$w(x)=\frac{\pi (x)}{q(x)}.$$ Hence for $X_1,\dots ,X_n\stackrel{\text{i.i.d.}}{\sim }q$, $${\hat{I}}_n^{\text{IS}}=\frac{1}{n}\sum _{i=1}^n\phi (X_i)w(X_i).$$

We have $$\begin{array}{rl}{\mathbb{E}}_{\pi }[\phi (X)]& ={\int }_{\mathbb{X}}\phi (x)\pi (x)\text{d}x\\ & ={\int }_{\mathbb{X}}\phi (x)\frac{\pi (x)}{q(x)}q(x)\text{d}x\\ & ={\int }_{\mathbb{X}}\phi (x)w(x)q(x)\text{d}x\\ & ={\mathbb{E}}_q[\phi (X)w(X)].\end{array}$$

1.1. Property

Proposition 1.1    Importance sampler satisfies:

    (1) (Unbiasedness) ${\mathbb{E}}_q[{\hat{I}}_n^{\text{IS}}]=I$;

    (2) (Strong Consistency) if ${\mathbb{E}}_q[|\phi (X)|w(X)]<\mathrm{\infty }$, then ${\displaystyle \underset{n\to \mathrm{\infty }}{lim}{\hat{I}}_n^{\text{IS}}=I\text{a.s.}}$;

    (3) (CLT) ${\displaystyle {\mathbb{V}}_q[{\hat{I}}_n^{\text{IS}}]=\frac{{\sigma }_{\text{IS}}^2}{n}}$ where ${\sigma }_{\text{IS}}^2={\mathbb{V}}_q[\phi (X)w(X)]$; if ${\sigma }_{\text{IS}}^2<\mathrm{\infty }$ then ${\displaystyle \underset{n\to \mathrm{\infty }}{lim}\sqrt{n}({\hat{I}}_n^{\text{IS}}-I)\stackrel{\text{D}}{\to }\mathcal{N}(0,{\sigma }_{\text{IS}}^2)}$.

Proposition 1.2    The optimal proposal minimizing ${\mathbb{V}}_q[{\hat{I}}_n^{\text{IS}}]$ is given by $$q_{\text{opt}}(x)=\frac{|\phi (x)|\pi (x)}{{\int }_{\mathbb{X}}|\phi (x)|\pi (x)\text{d}x}.$$

Proof. We have $${\sigma }_{\text{IS}}^2={\mathbb{V}}_q[\phi (X)w(X)]={\mathbb{E}}_q[{\phi }^2(X)w^2(X)]-I^2.$$ By Jensen's inequality, we have $${\mathbb{E}}_q[{\phi }^2(X)w^2(X)]={\mathbb{E}}_q[(|\phi (X)|w(X){)}^2]\ge ({\mathbb{E}}_q[|\phi (X)|w(X)]{)}^2={({\int }_{\mathbb{X}}|\phi (x)|\pi (x)\text{d}x)}^2.$$ For $q=q_{\text{opt}}$, we have $$\begin{array}{rl}{\mathbb{E}}_{q_{\text{opt}}}[{\phi }^2(X)w^2(X)]& ={\int }_{\mathbb{X}}{\phi }^2(x)w^2(x)q_{\text{opt}}(x)\text{d}x\\ & ={\int }_{\mathbb{X}}{\phi }^2(x)\frac{{\pi }^2(x)}{q_{\text{opt}}(x)}\text{d}x\\ & ={\int }_{\mathbb{X}}\frac{{\phi }^2(x){\pi }^2(x)}{|\phi (x)|\pi (x)}\text{d}x{\int }_{\mathbb{X}}|\phi (x)|\pi (x)\text{d}x\\ & ={({\int }_{\mathbb{X}}|\phi (x)|\pi (x)\text{d}x)}^2.\end{array}$$ Therefore, $q_{\text{opt}}(x)$ minimizes ${\mathbb{V}}_q[{\hat{I}}_n^{\text{IS}}]$.

$◻$

$q_{\text{opt}}(x)$ can NEVER be used in practice.

For $\phi (x)>0$, we have ${\displaystyle q_{\text{opt}}(x)=\frac{\phi (x)\pi (x)}{I}}$ and ${\mathbb{V}}_{q_{\text{opt}}}[{\hat{I}}_n^{\text{IS}}]=0$ but $$\phi (x)w(x)=\phi (x)\frac{\pi (x)}{q_{\text{opt}}(x)}=I$$ i.e. using $q_{\text{opt}}(x)$ requires knowing $I$.

2. Normalized Importance Sampling

Standard IS has limited applications in statistics as it requires knowing $\pi (x)$ and $q(x)$ exactly. Assume $$\pi (x)=\frac{\tilde{\pi }(x)}{Z_{\pi }}\text{and}q(x)=\frac{\tilde{q}(x)}{Z_q}$$ where $\pi (x)>0\Rightarrow q(x)>0$. Define $$\tilde{w}(x)=\frac{\tilde{\pi }(x)}{\tilde{q}(x)},$$ then we have $$I={\mathbb{E}}_{\pi }[\phi (X)]=\frac{{\int }_{\mathbb{X}}\phi (x)\tilde{w}(x)q(x)\text{d}x}{{\int }_{\mathbb{X}}\tilde{w}(x)q(x)\text{d}x}.$$

We have $$\begin{array}{rl}{\mathbb{E}}_{\pi }[\phi (X)]& ={\int }_{\mathbb{X}}\phi (x)\pi (x)\text{d}x\\ & =\frac{{\int }_{\mathbb{X}}\phi (x)\frac{\pi (x)}{q(x)}q(x)\text{d}x}{{\int }_{\mathbb{X}}\frac{\pi (x)}{q(x)}q(x)\text{d}x}\\ & =\frac{{\int }_{\mathbb{X}}\phi (x)\frac{\tilde{\pi }(x)/Z_{\pi }}{\tilde{q}(x)/Z_q}q(x)\text{d}x}{{\int }_{\mathbb{X}}\frac{\tilde{\pi }(x)/Z_{\pi }}{\tilde{q}(x)/Z_q}q(x)\text{d}x}\\ & =\frac{{\int }_{\mathbb{X}}\phi (x)\tilde{w}(x)q(x)\text{d}x}{{\int }_{\mathbb{X}}\tilde{w}(x)q(x)\text{d}x}\\ & =\frac{{\mathbb{E}}_q[\phi (X)\tilde{w}(X)]}{{\mathbb{E}}_q[\tilde{w}(X)]}.\end{array}$$

2.1. Property

Proposition 2.1 (Strong Consistency)    Let $X_1,\dots ,X_n\stackrel{\text{i.i.d.}}{\sim }q$ and assume that ${\mathbb{E}}_q[|\phi (X)|w(X)]<\mathrm{\infty }$. Then $${\hat{I}}_n^{\text{NIS}}=\frac{\sum _{i=1}^n\phi (X_i)\tilde{w}(X_i)}{\sum _{i=1}^n\tilde{w}(X_i)}$$ is strongly consistent.

Proof. We have $${\hat{I}}_n^{\text{NIS}}=\frac{\sum _{i=1}^n\phi (X_i)\tilde{w}(X_i)}{\sum _{i=1}^n\tilde{w}(X_i)}=\frac{n^{-1}\sum _{i=1}^n\phi (X_i)\tilde{w}(X_i)}{n^{-1}\sum _{i=1}^n\tilde{w}(X_i)}\stackrel{\text{a.s.}}{\to }\frac{{\mathbb{E}}_q[\phi (X)\tilde{w}(X)]}{{\mathbb{E}}_q[\tilde{w}(X)]}=I.$$

$◻$

Proposition 2.2 (CLT)    If ${\mathbb{V}}_q[\phi (X)w(X)]<\mathrm{\infty }$ and ${\mathbb{V}}_q[w(X)]<\mathrm{\infty }$, then $$\sqrt{n}({\hat{I}}_n^{\text{NIS}}-I)\stackrel{\text{D}}{\to }\mathcal{N}(0,{\sigma }_{\text{NIS}}^2)$$ where $${\sigma }_{\text{NIS}}^2={\mathbb{V}}_q[w(X)(\phi (X)-I)]={\int }_{\mathbb{X}}\frac{{\pi }^2(x)(\phi (x)-I{)}^2}{q(x)}\text{d}x.$$

Proof. With $X_1,\dots ,X_n\stackrel{\text{i.i.d.}}{\sim }q$, we have $$\sqrt{n}({\hat{I}}_n^{\text{NIS}}-I)=\frac{n^{-1/2}\sum _{i=1}^n\tilde{w}(X_i)(\phi (X_i)-I)}{n^{-1}\sum _{i=1}^n\tilde{w}(X_i)}.$$

Since $${\mathbb{E}}_q[\tilde{w}(X)(\phi (X)-I)]={\mathbb{E}}_q[\tilde{w}(X)\phi (X)]-\frac{{\mathbb{E}}_q[\phi (X)\tilde{w}(X)]}{{\mathbb{E}}_q[\tilde{w}(X)]}{\mathbb{E}}_q[\tilde{w}(X)]=0$$ and ${\mathbb{V}}_q[\phi (X)w(X)]<\mathrm{\infty }$, then by CLT, $$\sum _{i=1}^n\tilde{w}(X_i)(\phi (X_i)-I)\stackrel{\text{D}}{\to }\mathcal{N}(0,n{\mathbb{V}}_q[\tilde{w}(X)(\phi (X)-I)],$$ and thus $$\frac{1}{\sqrt{n}}\sum _{i=1}^n\tilde{w}(X_i)(\phi (X_i)-I)\stackrel{\text{D}}{\to }\mathcal{N}(0,{\mathbb{V}}_q[\tilde{w}(X)(\phi (X)-I)].$$

By SLLN, we have $$\frac{1}{n}\sum _{i=1}^n\tilde{w}(X_i)\stackrel{\text{a.s.}}{\to }{\mathbb{E}}_q[\tilde{w}(X)]=\frac{Z_{\pi }}{Z_q}.$$

Therefore, by Slutsky's theorem, we have $$\sqrt{n}({\hat{I}}_n^{\text{NIS}}-I)=\frac{n^{-1/2}\sum _{i=1}^n\tilde{w}(X_i)(\phi (X_i)-I)}{n^{-1}\sum _{i=1}^n\tilde{w}(X_i)}\stackrel{\text{D}}{\to }\mathcal{N}(0,\frac{Z_q^2}{Z_{\pi }^2}{\mathbb{V}}_q[\tilde{w}(X)(\phi (X)-I)])$$ where $$\frac{Z_q^2}{Z_{\pi }^2}{\mathbb{V}}_q[\tilde{w}(X)(\phi (X)-I)]={\int }_{\mathbb{X}}\frac{Z_q^2}{Z_{\pi }^2}{\tilde{w}}^2(x)(\phi (x)-I{)}^{2}q(x)\text{d}x={\int }_{\mathbb{X}}\frac{{\pi }^2(x)(\phi (x)-I{)}^2}{q(x)}\text{d}x={\sigma }_{\text{NIS}}^2.$$ Thus $$\sqrt{n}({\hat{I}}_n^{\text{NIS}}-I)\stackrel{\text{D}}{\to }\mathcal{N}(0,{\sigma }_{\text{NIS}}^2).$$

$◻$

3. Variance of Importance Sampling Estimator

Suppose $X_1,\dots ,X_n\stackrel{\text{i.i.d.}}{\sim }q$, then $${\hat{I}}_n^{\text{IS}}=\frac{1}{n}\sum _{i=1}^n\phi (X_i)w(X_i)\text{and}{\hat{I}}_n^{\text{NIS}}=\frac{\sum _{i=1}^n\phi (X_i)\tilde{w}(X_i)}{\sum _{i=1}^n\tilde{w}(X_i)}.$$

• The asymptotic variance for ${\hat{I}}_n^{\text{IS}}$ is $${\mathbb{V}}_{\text{as}}[{\hat{I}}_n^{\text{IS}}]={\mathbb{E}}_q[(\phi (X)w(X)-{\mathbb{E}}_q[\phi (X)w(X)]{)}^2]\approx \frac{1}{n}\sum _{i=1}^n(\phi (X_i)w(X_i)-{\hat{I}}_n^{\text{IS}}{)}^2.$$

• The asymptotic variance for ${\hat{I}}_n^{\text{NIS}}$ is $${\mathbb{V}}_{\text{as}}[{\hat{I}}_n^{\text{NIS}}]=\frac{{\mathbb{E}}_q[(w(X)(\phi (X)-I){)}^2]}{({\mathbb{E}}_q[w(X)]{)}^2}\approx \frac{n^{-1}\sum _{i=1}^n{\tilde{w}}^2(X_i)(\phi (X_i)-{\hat{I}}_n^{\text{NIS}}{)}^2}{(n^{-1}\sum _{i=1}^n\tilde{w}(X_i){)}^2}.$$

4. Diagnostic

We solve for $n_e$ in $$\frac{1}{n}{\mathbb{V}}_{\text{as}}[{\hat{I}}_n^{\text{NIS}}]=\frac{{\sigma }^2}{n_e}$$ where ${\displaystyle \frac{{\sigma }^2}{n_e}}$ corresponds to the variance of an unweighted sample of size $n_e$. The solution is $$n_e=\frac{(\sum _{i=1}^n\tilde{w}(X_i){)}^2}{\sum _{i=1}^n{\tilde{w}}^2(X_i)}$$ which is called the effective sample size.