Home | Articles | Past volumes | About | Login | Notify | Contact | Search
 Stochastic Systems > Vol. 6 (2016) open journal systems 


Convergence properties of weighted particle islands with application to the double bootstrap algorithm

Pierre Del Moral, University of New South Wales
Eric Moulines, Télécom ParisTech
Jimmy Olsson, KTH Royal Institute of Technology
Christelle Vergé, ONERA, The French Aerospace Lab/Centre National d’Études Spatiales


Abstract
Particle island models [32] provide a means of parallelization of sequential Monte Carlo methods, and in this paper we present novel convergence results for algorithms of this sort. In particular we establish a central limit theorem—as the number of islands and the common size of the islands tend jointly to infinity—of the double bootstrap algorithm with possibly adaptive selection on the island level. For this purpose we introduce a notion of archipelagos of weighted islands and find conditions under which a set of convergence properties are preserved by different operations on such archipelagos. This theory allows arbitrary compositions of these operations to be straightforwardly analyzed, providing a very flexible framework covering the double bootstrap algorithm as a special case. Finally, we establish the long-term numerical stability of the double bootstrap algorithm by bounding its asymptotic variance under weak and easily checked assumptions satisfied typically for models with non-compact state space.

Keywords: Central limit theorem, exponential deviation, parallelization, particle island models, particle filter, sequential Monte Carlo methods.

Creative Common LOGO

Full Text: PDF
Moral, Pierre Del, Moulines, Eric, Olsson, Jimmy, Vergé, Christelle, Convergence properties of weighted particle islands with application to the double bootstrap algorithm, Stochastic Systems, 6, (2016), 367-419 (electronic). DOI: 10.1214/15-SSY190.

References

[1]    B. Balasingam, M. Bolić, P. M. Djurić, and J. Míguez. Efficient distributed resampling for particle filters. In 2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3772–3775, May 2011.

[2]    M. Bolic, P. M. Djuric, and Sangjin Hong. Resampling algorithms and architectures for distributed particle filters. IEEE Transactions on Signal Processing, 53(7):2442–2450, July 2005.

[3]    O. Cappé and E. Moulines. On the use of particle filtering for maximum likelihood parameter estimation. In European Signal Processing Conference (EUSIPCO), Antalya, Turkey, September 2005.

[4]    O. Cappé, E. Moulines, and T. Rydén. Inference in Hidden Markov Models. Springer, 2005. MR2159833

[5]    F. Cérou, P. Del Moral, T. Furon, and A. Guyader. Sequential Monte Carlo for rare event estimation. Stat. Comput., 22(3):795–808, 2012.

[6]    N. Chopin. A sequential particle filter method for static models. Biometrika, 89:539–552, 2002.

[7]    N. Chopin. Central limit theorem for sequential Monte Carlo methods and its application to Bayesian inference. Ann. Statist., 32(6):2385–2411, 2004. MR2153989

[8]    N. Chopin, P. Jacob, and O. Papaspiliopoulos. SMC2: A sequential Monte Carlo algorithm with particle Markov chain Monte Carlo updates. J. Roy. Statist. Soc. B, 75(3):397–426, 2013.

[9]    D. Crisan and B. L. Rozovskii, editors. The Oxford handbook of nonlinear filtering. Oxford N.Y. Oxford University Press, 2011.

[10]    P. Del Moral. Feynman-Kac Formulae. Genealogical and Interacting Particle Systems with Applications. Springer, 2004. MR2044973

[11]    P. Del Moral and J. Garnier. Genealogical particle analysis of rare events. Ann. Appl. Probab., 15(4):2496–2534, 2005. MR2187302

[12]    P. Del Moral and A. Guionnet. Central limit theorem for nonlinear filtering and interacting particle systems. Ann. Appl. Probab., 9(2):275–297, 1999.

[13]    P. Del Moral and A. Guionnet. On the stability of interacting processes with applications to filtering and genetic algorithms. Annales de l’Institut Henri Poincaré, 37:155–194, 2001.

[14]    R. Douc, A. Garivier, E. Moulines, and J. Olsson. Sequential Monte Carlo smoothing for general state space hidden Markov models. Ann. Appl. Probab., 21(6):2109–2145, 2011. MR2895411

[15]    R. Douc and E. Moulines. Limit theorems for weighted samples with applications to sequential Monte Carlo methods. Ann. Statist., 36(5):2344–2376, 2008.

[16]    R. Douc, É. Moulines, and J. Olsson. Optimality of the auxiliary particle filter. Probab. Math. Statist., 29(1):1–28, 2009.

[17]    R. Douc, E. Moulines, and J. Olsson. Long-term stability of sequential Monte Carlo methods under verifiable conditions. Ann. Appl. Probab., 24(5):1767–1802, 2014. MR3226163

[18]    R. Douc, E. Moulines, and D. Stoffer. Nonlinear Time Series: Theory, Methods and Applications with R Examples. Chapman & Hall/CRC Texts in Statistical Science, 2014.

[19]    A. Doucet, N. De Freitas, and N. Gordon, editors. Sequential Monte Carlo Methods in Practice. Springer, New York, 2001.

[20]    K. Heine and N. Whiteley. Fluctuations, stability and instability of a distributed particle filter with local exchange. ArXiv e-prints, May 2015.

[21]    A. Kong, J. S. Liu, and W. Wong. Sequential imputation and Bayesian missing data problems. J. Am. Statist. Assoc., 89(278-288):590–599, 1994.

[22]    H. R. Künsch. Recursive Monte-Carlo filters: algorithms and theoretical analysis. Ann. Statist., 33(5):1983–2021, 2005. MR2211077

[23]    J. S. Liu. Metropolized independent sampling with comparisons to rejection sampling and importance sampling. Stat. Comput., 6:113–119, 1996.

[24]    J.S. Liu. Monte Carlo Strategies in Scientific Computing. Springer, New York, 2001.

[25]    J. Olsson, O. Cappé, R. Douc, and E. Moulines. Sequential Monte Carlo smoothing with application to parameter estimation in non-linear state space models. Bernoulli, 14(1):155–179, 2008. arXiv:math.ST/0609514.

[26]    M. K. Pitt and N. Shephard. Filtering via simulation: Auxiliary particle filters. J. Am. Statist. Assoc., 94(446):590–599, 1999.

[27]    B. Ristic, M. Arulampalam, and A. Gordon. Beyond Kalman Filters: Particle Filters for Target Tracking. Artech House, 2004.

[28]    O. Rosen and A. Medvedev. Efficient parallel implementation of state estimation algorithms on multicore platforms. IEEE Transactions on Control Systems Technology, 21(1):107–120, Jan 2013.

[29]    A. C. Sankaranarayanan, A. Srivastava, and R. Chellappa. Algorithmic and architectural optimizations for computationally efficient particle filtering. IEEE Transactions on Image Processing, 17(5):737–748, May 2008. MR2516598

[30]     S. Sutharsan, T. Kirubarajan, T. Lang, and M. Mcdonald. An optimization-based parallel particle filter for multitarget tracking. IEEE Transactions on Aerospace and Electronic Systems, 48(2):1601–1618, April 2012.

[31]    C. Vergé, C. Dubarry, P. Del Moral, and E. Moulines. On parallel implementation of sequential Monte Carlo methods: the island particle model. Statistics and Computing, 23, 2013.
Home | Articles | Past volumes | About | Login | Notify | Contact | Search

Stochastic Systems. ISSN: 1946-5238