Multilevel Monte Carlo in approximate Bayesian computation

Abstract

In the following article, we consider approximate Bayesian computation (ABC) inference. We introduce a method for numerically approximating ABC posteriors using the multilevel Monte Carlo (MLMC). A sequential Monte Carlo version of the approach is developed and it is shown under some assumptions that for a given level of mean square error, this method for ABC has a lower cost than i.i.d. sampling from the most accurate ABC approximation. Several numerical examples are given.

Keywords:

• Approximate Bayesian computation
• multilevel Monte Carlo
• sequential Monte Carlo

Acknowledgements

AJ, SJ, DN, and CS were all supported by grant number R-069-000-074-646, Operations research cluster funding, NUS. AJ and RT were additionally supported by KAUST CRG4 Award Ref: 2584.

Appendix A: Proof of Proposition 3.1

Proof.

We give the proof in the case n = 1; the general case is the same, except with some minor complications in notations. We have (5) $$\frac{Z_{l-1}}{Z_l}{G}_{l-1}\left(x\right)-1=\frac{Z_{l-1}}{Z_l}\left(G_{l-1}\right(x)-\frac{{ϵ}_l^2}{{ϵ}_{l-1}^2})+\frac{{ϵ}_l^2}{{ϵ}_{l-1}^2}\frac{Z_{l-1}}{Z_l}-1.$$(5)

We will deal with the two expressions on the R.H.S. of Equation (5)(5) $$\frac{Z_{l-1}}{Z_l}{G}_{l-1}\left(x\right)-1=\frac{Z_{l-1}}{Z_l}\left(G_{l-1}\right(x)-\frac{{ϵ}_l^2}{{ϵ}_{l-1}^2})+\frac{{ϵ}_l^2}{{ϵ}_{l-1}^2}\frac{Z_{l-1}}{Z_l}-1.$$(5) separately. Throughout C is a constant that does not depend on a level index l but whose value may change upon appearance.

First Term on the R.H.S. of Equation (5)(5) $$\frac{Z_{l-1}}{Z_l}{G}_{l-1}\left(x\right)-1=\frac{Z_{l-1}}{Z_l}\left(G_{l-1}\right(x)-\frac{{ϵ}_l^2}{{ϵ}_{l-1}^2})+\frac{{ϵ}_l^2}{{ϵ}_{l-1}^2}\frac{Z_{l-1}}{Z_l}-1.$$(5)

We will show that $$\Vert (G_{l-1}-\frac{{ϵ}_l^2}{{ϵ}_{l-1}^2}){\Vert }_{\infty }\le C{ϵ}_{l-1}^2$$ and that $\frac{Z_{l-1}}{Z_l}\le C$. We start with the first task. We have $$G_{l-1}\left(x\right)-\frac{{ϵ}_l^2}{{ϵ}_{l-1}^2}=\frac{{ϵ}_l^2}{{ϵ}_{l-1}^2}[\frac{{ϵ}_{l-1}^2+c}{{ϵ}_l^2+c}-1].$$ where we have set $c={(y-u)}^2$. Then elementary calculations yield $$G_{l-1}\left(x\right)-\frac{{ϵ}_l^2}{{ϵ}_{l-1}^2}=\frac{{ϵ}_l^2}{{ϵ}_l^2+c}(1-\frac{{ϵ}_l^2}{{ϵ}_{l-1}^2}).$$

Now as $$\frac{{ϵ}_l^2}{{ϵ}_{l-1}^2}\le 1$$ and as $c\ge C$ $$\frac{1}{{ϵ}_l^2+c}\le \frac{1}{c}\le C$$ we have (6) $$\Vert (G_{l-1}-\frac{{ϵ}_l^2}{{ϵ}_{l-1}^2}){\Vert }_{\infty }\le C{ϵ}_l^2\le C{ϵ}_{l-1}^2.$$(6)

Now $$\frac{Z_{l-1}}{Z_l}={\int }_E\frac{1}{1+\frac{c}{{ϵ}_{l-1}^2}}f\left(u\right|\theta )\pi (\theta \left)d\right(\theta ,u){\left({\int }_E\frac{1}{1+\frac{c}{{ϵ}_l^2}}f\right(u|\theta )\pi (\theta )d(\theta ,u))}^{-1}.$$

Now $$\frac{1}{1+\frac{c}{{ϵ}_{l-1}^2}}\le C{ϵ}_{l-1}^2$$ so that $$Z_{l-1}\le C{ϵ}_{l-1}^2.$$

We now will show that ${ϵ}_{l-1}^{-2}{Z}_l$ is lower bounded uniformly in l which will show that $\frac{Z_{l-1}}{Z_l}\le C$. $${ϵ}_{l-1}^{-2}{Z}_l={\int }_E\frac{1}{{ϵ}_{l-1}^2+\frac{c{ϵ}_{l-1}^2}{{ϵ}_l^2}}f\left(u\right|\theta )\pi (\theta \left)d\right(\theta ,u).$$

Then $$\frac{1}{{ϵ}_{l-1}^2+\frac{c{ϵ}_{l-1}^2}{{ϵ}_l^2}}\ge \frac{1}{1+C}$$ as ${ϵ}_{l-1}^2\le 1$ and $\frac{c{ϵ}_{l-1}^2}{{ϵ}_l^2}\le C$. So we have that ${ϵ}_{l-1}^{-2}{Z}_l\ge C$ and (7) $$\frac{Z_{l-1}}{Z_l}\le C.$$(7)

Combining Equations (6)(6) $$\Vert (G_{l-1}-\frac{{ϵ}_l^2}{{ϵ}_{l-1}^2}){\Vert }_{\infty }\le C{ϵ}_l^2\le C{ϵ}_{l-1}^2.$$(6) and (7)(7) $$\frac{Z_{l-1}}{Z_l}\le C.$$(7) yields (8) $$\Vert (G_{l-1}-\frac{{ϵ}_l^2}{{ϵ}_{l-1}^2}){\Vert }_{\infty }\le C{ϵ}_{l-1}^2.$$(8)

Second Term on the R.H.S. of Equation (5)(5) $$\frac{Z_{l-1}}{Z_l}{G}_{l-1}\left(x\right)-1=\frac{Z_{l-1}}{Z_l}\left(G_{l-1}\right(x)-\frac{{ϵ}_l^2}{{ϵ}_{l-1}^2})+\frac{{ϵ}_l^2}{{ϵ}_{l-1}^2}\frac{Z_{l-1}}{Z_l}-1.$$(5)

Clearly (9) $$\frac{{ϵ}_l^2}{{ϵ}_{l-1}^2}\frac{Z_{l-1}}{Z_l}-1=\frac{{ϵ}_l^2{Z}_{l-1}-{ϵ}_{l-1}^2{Z}_l}{{ϵ}_{l-1}^2{Z}_l}.$$(9)

We first deal with the numerator on the R.H.S.: $$\begin{array}{c}{ϵ}_l^2{Z}_{l-1}-{ϵ}_{l-1}^2{Z}_l={\int }_E[\frac{{ϵ}_{l-1}^2{ϵ}_l^2}{c+{ϵ}_{l-1}^2}-\frac{{ϵ}_{l-1}^2{ϵ}_l^2}{c+{ϵ}_l^2}\left]f\right(u|\theta )\pi (\theta )d(\theta ,u)\\ ={\int }_E[\frac{{ϵ}_{l-1}^2{ϵ}_l^2({ϵ}_l^2-{ϵ}_{l-1}^2)}{(c+{ϵ}_{l-1}^2)(c+{ϵ}_l^2)}\left]f\right(u|\theta )\pi (\theta )d(\theta ,u).\end{array}$$

As $$\frac{1}{(c+{ϵ}_{l-1}^2)(c+{ϵ}_l^2)}\le C,\hspace{1em}\hspace{1em}{ϵ}_l^2-{ϵ}_{l-1}^2\le {ϵ}_l^2\le {ϵ}_{l-1}^2$$ we have $$|{ϵ}_l^2{Z}_{l-1}-{ϵ}_{l-1}^2{Z}_l|\le C{ϵ}_{l-1}^4{ϵ}_l^2.$$

Therefore one has $$\left|\frac{{ϵ}_l^2{Z}_{l-1}-{ϵ}_{l-1}^2{Z}_l}{{ϵ}_{l-1}^2{Z}_l}\right|\le C\frac{{ϵ}_{l-1}^2}{{ϵ}_l^{-2}{Z}_l}$$

Using almost the same calculation as for showing ${ϵ}_{l-1}^{-2}{Z}_l\ge C$, we have ${ϵ}_l^{-2}{Z}_l\ge C$ and so (10) $$|\frac{{ϵ}_l^2}{{ϵ}_{l-1}^2}\frac{Z_{l-1}}{Z_l}-1|\le C{ϵ}_{l-1}^2.$$(10)

Returning to Equation (5)(5) $$\frac{Z_{l-1}}{Z_l}{G}_{l-1}\left(x\right)-1=\frac{Z_{l-1}}{Z_l}\left(G_{l-1}\right(x)-\frac{{ϵ}_l^2}{{ϵ}_{l-1}^2})+\frac{{ϵ}_l^2}{{ϵ}_{l-1}^2}\frac{Z_{l-1}}{Z_l}-1.$$(5) and noting Equation (9)(9) $$\frac{{ϵ}_l^2}{{ϵ}_{l-1}^2}\frac{Z_{l-1}}{Z_l}-1=\frac{{ϵ}_l^2{Z}_{l-1}-{ϵ}_{l-1}^2{Z}_l}{{ϵ}_{l-1}^2{Z}_l}.$$(9) , one apply the triangular inequality and combine Equations (7)(7) $$\frac{Z_{l-1}}{Z_l}\le C.$$(7) and (10)(10) $$|\frac{{ϵ}_l^2}{{ϵ}_{l-1}^2}\frac{Z_{l-1}}{Z_l}-1|\le C{ϵ}_{l-1}^2.$$(10) to complete the proof. □

Appendix B: Proof of Proposition 3.2

Proof.

We will show that the expected cost of sampling a given full-conditional is $\mathcal{O}({ϵ}_l^{-1})$. Throughout C is a constant that does not depend on a level index l nor i but whose value may change upon appearance.

It is easily shown that $$h\left(w_{i+1}\right|w_i)\frac{1}{1+{\left(\frac{y_i-v_i}{{ϵ}_l}\right)}^2}\le C=C^{*}$$ and thus that the probability of accepting, in the rejection scheme is $${\left(C^{*}\right)}^{-1}{\int }_{\mathrm{V}\times \mathrm{W}}\frac{1}{1+{\left(\frac{y_i-v_i}{{ϵ}_l}\right)}^2}h\left(w_{i+1}\right|w_i\left)g\right(v_i\left|w_i\right)h\left(w_i\right|w_{i-1}\left)d\right(v_i,w_i).$$

The expected number of simulations is then the inverse. Clearly $$\frac{1}{1+{\left(\frac{y_i-v_i}{{ϵ}_l}\right)}^2}\ge C{ϵ}_l^2$$ and as $\mathrm{V}\times \mathrm{W}$ is compact and by assumption ${ϵ}_l>0$. Note as $h(w_{i+1}|w_i)g(v_i|w_i)h(w_i|w_{i-1})\ge C$ the expected number of simulations to sample the full conditional is at most $$C{ϵ}_l^{-2}$$ which completes the proof. □