Double-Parallel Monte Carlo for Bayesian analysis of big data

Abstract

This paper proposes a simple, practical, and efficient MCMC algorithm for Bayesian analysis of big data. The proposed algorithm suggests to divide the big dataset into some smaller subsets and provides a simple method to aggregate the subset posteriors to approximate the full data posterior. To further speed up computation, the proposed algorithm employs the population stochastic approximation Monte Carlo algorithm, a parallel MCMC algorithm, to simulate from each subset posterior. Since this algorithm consists of two levels of parallel, data parallel and simulation parallel, it is coined as “Double-Parallel Monte Carlo.” The validity of the proposed algorithm is justified mathematically and numerically.

Appendix A Proof of Theorem 1

Under conditions A1 and A2, we can expand the mean of each subposterior at the corresponding MLE, $\hat{\varvec{\theta }}^{(j)}$, as follows:

$$\begin{aligned} \varvec{\mu }^{(j)}= & {} E_{\tilde{\pi }_j} (\varvec{\theta }) =\hat{\varvec{\theta }}^{(j)}+\frac{\hat{I}^{(j)-1}}{n} \\&\times \left[ \frac{\partial \log g({\varvec{\theta }})}{\partial {\varvec{\theta }}}|_{\hat{{\varvec{\theta }}}^{(j)}} -\frac{1}{2}\hat{H}^{(j)}\hat{I}^{(j)-1} \right] +O(n^{-2}), \end{aligned}$$

where $\tilde{\pi }_j=\tilde{\pi }({\varvec{\theta }}|{\varvec{X}}_{[j]})$, $\hat{I}^{(j)}=-\frac{1}{m} \frac{\partial ^{2} \log f({\varvec{X}}_{[j]}|\varvec{\theta })}{\partial \varvec{\theta }\partial \varvec{\theta }^{T}}|_{\varvec{\theta }=\hat{\varvec{\theta }}^{(j)}}$, $\hat{H}^{(j)}=-\frac{1}{m}\frac{\partial ^{3} logf({\varvec{X}}_{[j]}|\varvec{\theta })}{\partial \varvec{\theta } \partial \varvec{\theta }^{T}\partial \varvec{\theta }}|_{\varvec{\theta }=\hat{\varvec{\theta }}^{(j)}}$, and $\hat{H}^{(j)}\hat{I}^{(j)-1}$ is a vector whose rth element equals $\sum _{st}\hat{H}_{rst}^{(j)}\hat{I}_{st}^{(j)-1}$. To simplify the notation, we denote $\hat{I}^{(j)-1}[\partial \log g({\varvec{\theta }})/\partial {\varvec{\theta }}|_{\hat{{\varvec{\theta }}}^{(j)}} -\frac{1}{2}\hat{H}^{(j)}\hat{I}^{(j)-1}]$ by $\varvec{\nu }^{(j)}$. Here we would like to mention that although A1 and A2 are directly associated with the Laplace approximation of the full posterior, they can also lead to the conditions that guarantee the Laplace approximation of each subposterior, as long as m goes to $\infty$ with n.

Moreover, for each $\hat{\varvec{\theta }}^{(j)}$, we have

$$\begin{aligned} \hat{\varvec{\theta }}^{(j)}=\varvec{\theta }^{*}+\frac{\varvec{\xi }^{(j)}}{\sqrt{m}}+O_{p}(m^{-1}), \end{aligned}$$

where

$$\begin{aligned} \varvec{\xi }^{(j)}= & {} \frac{1}{\sqrt{m}}I^{-1}\sum _{i=1}^{m}\frac{\partial \log f(X_{ji}|\varvec{\theta }^{*})}{\partial \varvec{\theta }},\\ I= & {} -E_{{\varvec{X}}|\varvec{\theta }^{*}}\frac{\partial ^2 \log f({\varvec{X}}|\varvec{\theta }^{*}) }{\partial \varvec{\theta } \partial \varvec{\theta }^{T} }. \end{aligned}$$

Therefore, the mean of the mixture distribution $\tilde{\pi }(\varvec{\theta }|{\varvec{X}})$ is given by

$$\begin{aligned} E_{\tilde{\pi }} (\varvec{\theta })= & {} \frac{1}{k}\sum _{j=1}^{k}\varvec{\mu }^{(j)}\\= & {} \varvec{\theta }^{*}+\frac{1}{k}\sum _{j=1}^{k}\frac{\varvec{\nu }^{(j)}}{n}+\frac{1}{k}\sum _{j=1}^{k} \frac{\varvec{\xi }^{(j)}}{\sqrt{m}}\\&+\,O_{p}(m^{-1})+O(n^{-2}). \end{aligned}$$

We can also implement a similar procedure on the full data posterior $\pi (\varvec{\theta }|{\varvec{X}})$ and obtain

$$\begin{aligned} E_{\pi }(\varvec{\theta })= & {} \varvec{\theta }^{*}+\frac{\varvec{\nu }}{n} +\frac{\varvec{\xi }}{\sqrt{n}}+O_{p}(n^{-1})+O(n^{-2}), \end{aligned}$$

where $\varvec{\nu }=\hat{I}^{-1}[\partial \log g({\varvec{\theta }})/\partial {\varvec{\theta }}|_{\hat{{\varvec{\theta }}} } -\frac{1}{2}\hat{H}\hat{I}^{-1}]$, $\varvec{\xi }=\frac{1}{\sqrt{n}}I^{-1}\sum _{i=1}^{n}\frac{\partial \log f(X_{i}|\varvec{\theta }^{*})}{\partial \varvec{\theta }}$, $\hat{I}=-\frac{1}{n} \frac{\partial ^{2} \log f({\varvec{X}}|\varvec{\theta })}{\partial \varvec{\theta }\partial \varvec{\theta }^{T}}|_{\varvec{\theta }=\hat{\varvec{\theta }}}$, $\hat{H}=-\frac{1}{m}\frac{\partial ^{3} logf({\varvec{X}}|\varvec{\theta })}{\partial \varvec{\theta } \partial \varvec{\theta }^{T}\partial \varvec{\theta }}|_{\varvec{\theta }=\hat{\varvec{\theta }}}$, and $\hat{\varvec{\theta }}$ denotes the MLE of $\theta$ calculated with the full dataset. By noting that $\frac{\varvec{\xi }}{\sqrt{n}}=\frac{1}{k}\sum _{j=1}^{k}\frac{\varvec{\xi }^{(j)}}{\sqrt{m}}$, $\varvec{\nu }^{(j)}$ and $\varvec{\nu }$ are O(1), $m<n$, Eq. (4) in Theorem 1 is thereby verified:

$$\begin{aligned} E_{\tilde{\pi }} (\varvec{\theta })-E_{\pi } (\varvec{\theta })= & {} \frac{1}{k}\sum _{j=1}^{k}\frac{\varvec{\nu }^{(j)}}{n}+O_{p}(m^{-1})\\&-\frac{\varvec{\nu }}{n} +O_{p}(n^{-1})+O(n^{-2}) \\= & {} O(n^{-1})+O_{p}(m^{-1})+O(n^{-1})\\&+\,O_{p}(n^{-1})+O(n^{-2}) \\= & {} O_{p}(m^{-1}). \end{aligned}$$

The variance of each subposterior can be approximated as follows:

$$\begin{aligned} \mathrm{Var}_{\tilde{\pi }_{j}}(\varvec{\theta })=\frac{\hat{I}^{(j)-1}}{n}+O(n^{-2}). \end{aligned}$$

Therefore, the variance of the mixture distribution $\tilde{\pi }(\varvec{\theta }|{\varvec{X}})$ is given by

$$\begin{aligned} \mathrm{Var}_{\tilde{\pi }}(\varvec{\theta })=\frac{1}{k}\sum _{j=1}^{k}\mathrm{Var}_{\tilde{\pi }_{j}}(\varvec{\theta }) =\frac{1}{k}\sum _{j=1}^{k}\frac{\hat{I}^{(j)-1}}{n}+O(n^{-2}). \end{aligned}$$

In addition, we have

$$\begin{aligned} \mathrm{Var}_{\pi }(\varvec{\theta })=\frac{\hat{I}^{-1}}{n}+O(n^{-2}). \end{aligned}$$

Since $\hat{I}^{(j)}=I+o_{p}(1)$ and $\hat{I}=I+o_{p}(1)$, we further have $\hat{I}^{(j)-1}=I^{-1}+o_{p}(1)$ and $\hat{I}^{-1}=I^{-1}+o_{p}(1)$. Equation (5) in Theorem 1 is thereby verified:

$$\begin{aligned} \mathrm{Var}_{\tilde{\pi }}(\varvec{\theta })-\mathrm{Var}_{\pi }(\varvec{\theta })= & {} \frac{1}{k}\sum _{j=1}^{k}\frac{\hat{I}^{(j)-1}}{n}-\frac{\hat{I}^{-1}}{n}+O(n^{-2})\\= & {} \frac{I^{-1}}{n}+o_{p}(n^{-1})-\frac{I^{-1}}{n}\\&+\,o_{p}(n^{-1})+O(n^{-2})\\= & {} o_{p}(n^{-1}). \end{aligned}$$

Finally, for the square of the Wasserstein distance of order 2, we have

$$\begin{aligned}&\bigg |d^{2}(\tilde{\pi }(\varvec{\theta }|{\varvec{X}}),\delta _{{\varvec{\theta }}^{*}})-d^{2}(\pi (\varvec{\theta }|{\varvec{X}}),\delta _{{\varvec{\theta }}^{*}})\bigg |\\&\quad =\bigg |\int _{\Theta }\Vert \varvec{\theta }- \varvec{\theta }^{*}\Vert _{2}^{2}\tilde{\pi }(\varvec{\theta }|{\varvec{X}})\mathrm{d}\varvec{\theta }\\&\quad \quad -\int _{\Theta }\Vert \varvec{\theta }- \varvec{\theta }^{*}\Vert _{2}^{2}\pi (\varvec{\theta }|{\varvec{X}})\mathrm{d}\varvec{\theta }\bigg |\\&\quad =\left| \left\| E_{\tilde{\pi }}(\varvec{\theta })-\varvec{\theta }^{*}\right\| _2^2+tr\left( \mathrm{Var}_{\tilde{\pi }}(\varvec{\theta }) \right) \right. \\&\quad \quad \left. -\left\| E_{\pi }(\varvec{\theta })-\varvec{\theta }^{*}\right\| _2^2 -tr\left( \mathrm{Var}_{\pi }(\varvec{\theta }) \right) \right| \\&\quad \le \left| \left\| E_{\tilde{\pi }}(\varvec{\theta })-E_{\pi }(\varvec{\theta })+E_{\pi }(\varvec{\theta })-\varvec{\theta }^{*}\right\| _2^2\right. \\&\left. \quad \quad -\left\| E_{\pi }(\varvec{\theta })-\varvec{\theta }^{*}\right\| _2^2\right| +|tr\left( \mathrm{Var}_{\tilde{\pi }}(\varvec{\theta }) -\mathrm{Var}_{\pi }(\varvec{\theta }) \right) |\\&\quad \le \Vert E_{\tilde{\pi }}(\varvec{\theta })-E_{\pi }(\varvec{\theta })\Vert _2^2+2\Vert E_{\tilde{\pi }}(\varvec{\theta })\\&\quad \quad -\,E_{\pi }(\varvec{\theta })\Vert _{2}\Vert E_{\pi }(\varvec{\theta })-\varvec{\theta }^{*}\Vert _{2}+o_{p}(n^{-1})\\&\quad =O_{p}(m^{-2})+2O_{p}(m^{-1})O_{p}(n^{-1/2})+o_{p}(n^{-1})\\&\quad =o_{p}(n^{-1}), \end{aligned}$$

where the last equality follows from the fact $n=o(m^{2})$. This verifies Eq. (5) in Theorem 1.