×

On parallel implementation of sequential Monte Carlo methods: the island particle model. (English) Zbl 1331.65023

Summary: The approximation of the Feynman-Kac semigroups by systems of interacting particles is a very active research field, with applications in many different areas. In this paper, we study the parallelization of such approximations. The total population of particles is divided into sub-populations, referred to as islands. The particles within each island follow the usual selection/mutation dynamics. We show that the evolution of each island is also driven by a Feynman-Kac semigroup, whose transition and potential can be explicitly related to ones of the original problem. Therefore, the same genetic type approximation of the Feynman-Kac semi-group may be used at the island level; each island might undergo selection/mutation algorithm. We investigate the impact of the population size within each island and the number of islands, and study different type of interactions. We find conditions under which introducing interactions between islands is beneficial. The theoretical results are supported by some Monte Carlo experiments.

MSC:

65C40 Numerical analysis or methods applied to Markov chains
65C05 Monte Carlo methods
65Y05 Parallel numerical computation
60J60 Diffusion processes
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Arnaud, E., Le Gland, F.: SMC with Adaptive Resampling: Large Sample Asymptotics, pp. 481-484 (2009)
[2] Cappé, O.; Moulines, E., On the use of particle filtering for maximum likelihood parameter estimation, Antalya, Turkey
[3] Casarin, R., Grassi, S., Ravazzolo, F., Van Dijk, H.K.: Parallel sequential Monte Carlo for efficient density combination: the deco Matlab toolboox. Tinbergen Institute Discussion Paper, 055/III (2013) · Zbl 1155.62056
[4] Chopin, N.: A sequential particle filter method for static models. Biometrika 89, 539-552 (2002) · Zbl 1036.62062
[5] Chopin, N., Jacob, P., Papaspiliopoulos, O.: SMC2: a sequential Monte Carlo algorithm with particle Markov chain Monte Carlo updates. J. R. Stat. Soc. B. 75(3), 397-426 (2013). doi:10.1111/j.1467-9868.2012.01046.x · Zbl 1411.62242
[6] Del Moral, P.: Feynman-Kac Formulae. Genealogical and Interacting Particle Systems with Applications. Springer, Berlin (2004) · Zbl 1130.60003
[7] Del Moral, P., Doucet, A., Jasra, A.: On adaptive resampling strategies for sequential Monte Carlo methods. Bernoulli 18(1), 252-278 (2012a) · Zbl 1236.60072
[8] Del Moral, P., Hu, P., Wu, L.: On the concentration properties of interacting particle processes. Found. Trends Mach. Learn. 3(3-4), 225-289 (2012b)
[9] Douc, R., Moulines, E.: Limit theorems for weighted samples with applications to sequential Monte Carlo methods. Ann. Stat. 36(5), 2344-2376 (2008) · Zbl 1155.62056
[10] Doucet, A., Freitas, N.D. (eds.): Sequential Monte Carlo Methods in Practice. Springer, New York (2001) · Zbl 0967.00022
[11] Durham, G., Geweke, J.: Massively parallel sequential Monte Carlo for Bayesian inference. Manuscript, URL http://www.censoc.uts.edu.au/pdfs/geweke_papers/gp_working_9.pdf (2011) · Zbl 1453.62615
[12] Jasra, A., Doucet, A., Stephens, D.A., Holmes, C.C.: Interacting sequential Monte Carlo samplers for trans-dimensional simulation. Comput. Stat. Data Anal. 52, 1765-1791 (2008) · Zbl 1452.62077
[13] Liu, J.S.: Monte Carlo Strategies in Scientific Computing. Springer, New York (2001) · Zbl 0991.65001
[14] Liu, J., Chen, R.: Blind deconvolution via sequential imputations. J. Am. Stat. Assoc. 90(420), 567-576 (1995) · Zbl 0826.62062
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.