×

On the stability of sequential Monte Carlo methods in high dimensions. (English) Zbl 1304.82070

Sequential Monte Carlo (SMC) methods form a collection of techniques that approximate a sequence of distributions, known up to the normalizing constant and of increasing dimension. They combine importance sampling and resampling to approximate a target distribution. The paper addresses the stability of a SMC for targets in \(\mathbb R^d\) for large \(d\). It is known that using a single importance sampling step, one produces an approximation to the target which deteriorates as \(d\) increases, unless the number of Monte Carlo samples \(N\) increases at an exponential rate in \(d\). The problem is bypassed by introducing a sequence of artificial targets beginning from any density and approaching the target of interest. The SMC method is used to sample from the obtained sequence. It is found that in high dimensions, SMC algorithms can efficiently control the variability of the importance sampling weights and estimate fixed-dimensional marginals at a cost which is less than exponential in \(d\). The resampling leads here to a reduction of the Monte Carlo error and an increase in the effective sample size (ESS). All of the analysis is carried out under an assumption that the target density is i.i.d.

MSC:

82C80 Numerical methods of time-dependent statistical mechanics (MSC2010)
60K35 Interacting random processes; statistical mechanics type models; percolation theory
60F99 Limit theorems in probability theory
62F15 Bayesian inference
65C05 Monte Carlo methods
91G60 Numerical methods (including Monte Carlo methods)
PDF BibTeX XML Cite
Full Text: DOI arXiv Euclid

References:

[1] Andrieu, C., Jasra, A., Doucet, A. and Del Moral, P. (2011). On non-linear Markov chain Monte Carlo. Bernoulli 17 987-1014. · Zbl 1241.60037
[2] Andrieu, C. and Moulines, É. (2006). On the ergodicity properties of some adaptive MCMC algorithms. Ann. Appl. Probab. 16 1462-1505. · Zbl 1114.65001
[3] Atchadé, Y. (2009). A strong law of large numbers for martingale arrays. Technical report, Univ. Michigan.
[4] Baehr, C. and Pannekoucke, O. (2010). Some issues and results on the EnKF and particle filters for meteorological models. In Chaotic Systems (C. H. Skiadas and I. Dimotikalis, eds.) 27-34. World Sci. Publ., River Edge, NJ.
[5] Bédard, M. (2007). Weak convergence of Metropolis algorithms for non-i.i.d. target distributions. Ann. Appl. Probab. 17 1222-1244. · Zbl 1144.60016
[6] Bengtsson, T., Bickel, P. and Li, B. (2008). Curse-of-dimensionality revisited: Collapse of the particle filter in very large scale systems. In Probability and Statistics : Essays in Honor of David A. Freedman (D. Nolan and T. Speed, eds.) 316-334. IMS, Beachwood, OH. · Zbl 1166.93376
[7] Berger, E. (1986). Asymptotic behaviour of a class of stochastic approximation procedures. Probab. Theory Related Fields 71 517-552. · Zbl 0571.62073
[8] Beskos, A., Crisan, D. and Jasra, A. (2011). On the stability of sequential Monte Carlo methods in high-dimensions. Technical report, Imperial College London. · Zbl 1304.82070
[9] Beskos, A., Crisan, D., Jasra, A. and Whiteley, N. (2014). Error bounds and normalizing constants for sequential Monte Carlo. Adv. in Appl. Probab. · Zbl 1291.65009
[10] Beskos, A., Pillai, N., Roberts, G., Sanz-Serna, J.-M. and Stuart, A. (2013). Optimal tuning of the hybrid Monte Carlo algorithm. Bernoulli 19 1501-1534. · Zbl 1287.60090
[11] Beskos, A., Roberts, G. and Stuart, A. (2009). Optimal scalings for local Metropolis-Hastings chains on nonproduct targets in high dimensions. Ann. Appl. Probab. 19 863-898. · Zbl 1172.60328
[12] Beskos, A. and Stuart, A. (2007). MCMC methods for sampling function space. In ICIAM 07 - 6 th International Congress on Industrial and Applied Mathematics . Zürich. · Zbl 1179.65003
[13] Bickel, P., Li, B. and Bengtsson, T. (2008). Sharp failure rates for the bootstrap particle filter in high dimensions. In Pushing the Limits of Contemporary Statistics (B. Clarke and S. Ghosal, eds.) 318-329. IMS, Beachwood, OH.
[14] Billingsley, P. (1999). Convergence of Probability Measures , 2nd ed. Wiley, New York. · Zbl 0944.60003
[15] Breyer, L. A., Piccioni, M. and Scarlatti, S. (2004). Optimal scaling of MaLa for nonlinear regression. Ann. Appl. Probab. 14 1479-1505. · Zbl 1048.62062
[16] Breyer, L. A. and Roberts, G. O. (2000). From Metropolis to diffusions: Gibbs states and optimal scaling. Stochastic Process. Appl. 90 181-206. · Zbl 1047.60065
[17] Cappé, O., Guillin, A., Marin, J. M. and Robert, C. P. (2004). Population Monte Carlo. J. Comput. Graph. Statist. 13 907-929.
[18] Chopin, N. (2002). A sequential particle filter method for static models. Biometrika 89 539-551. · Zbl 1036.62062
[19] Chopin, N. (2004). Central limit theorem for sequential Monte Carlo methods and its application to Bayesian inference. Ann. Statist. 32 2385-2411. · Zbl 1079.65006
[20] Crisan, D. and Rozovsky, B. (2011). The Oxford Handbook of Nonlinear Filtering . Oxford Univ. Press, Oxford. · Zbl 1210.60005
[21] Del Moral, P. (2004). Feynman-Kac Formulae : Genealogical and Interacting Particle Systems With Applications . Springer, New York. · Zbl 1130.60003
[22] Del Moral, P., Doucet, A. and Jasra, A. (2006). Sequential Monte Carlo samplers. J. R. Stat. Soc. Ser. B Stat. Methodol. 68 411-436. · Zbl 1105.62034
[23] Del Moral, P., Doucet, A. and Jasra, A. (2012). An adaptive sequential Monte Carlo method for approximate Bayesian computation. Stat. Comput. 22 1009-1020. · Zbl 1252.65025
[24] Del Moral, P., Doucet, A. and Jasra, A. (2012). On adaptive resampling procedures for sequential Monte Carlo methods. Bernoulli 18 252-278. · Zbl 1236.60072
[25] Del Moral, P., Patras, F. and Rubenthaler, S. (2009). Coalescent tree based functional representations for some Feynman-Kac particle models. Ann. Appl. Probab. 19 778-825. · Zbl 1189.60171
[26] Douc, R. and Moulines, E. (2008). Limit theorems for weighted samples with applications to sequential Monte Carlo methods. Ann. Statist. 36 2344-2376. · Zbl 1155.62056
[27] Douc, R., Moulines, E. and Rosenthal, J. S. (2004). Quantitative bounds on convergence of time-inhomogeneous Markov chains. Ann. Appl. Probab. 14 1643-1665. · Zbl 1072.60059
[28] Doucet, A., De Freitas, N. and Gordon, N., eds. (2001). Sequential Monte Carlo Methods in Practice . Springer, New York. · Zbl 0967.00022
[29] Hall, P. and Heyde, C. C. (1980). Martingale Limit Theory and Its Application . Academic Press, New York. · Zbl 0462.60045
[30] Heine, K. and Crisan, D. (2008). Uniform approximations of discrete-time filters. Adv. in Appl. Probab. 40 979-1001. · Zbl 1155.93039
[31] Jarzynski, C. (1997). Nonequilibrium equality for free energy differences. Phys. Rev. Lett. 78 2690-2693.
[32] Jasra, A., Stephens, D. A., Doucet, A. and Tsagaris, T. (2011). Inference for Lévy-driven stochastic volatility models via adaptive sequential Monte Carlo. Scand. J. Stat. 38 1-22. · Zbl 1246.91149
[33] Jasra, A., Stephens, D. A. and Holmes, C. C. (2007). On population-based simulation for static inference. Stat. Comput. 17 263-279.
[34] Kong, A., Liu, J. S. and Wong, W. H. (1994). Sequential imputations and Bayesian missing data problems. J. Amer. Statist. Assoc. 89 278-288. · Zbl 0800.62166
[35] Künsch, H. R. (2005). Recursive Monte Carlo filters: Algorithms and theoretical analysis. Ann. Statist. 33 1983-2021. · Zbl 1086.62106
[36] Lee, A., Yau, C., Giles, M., Doucet, A. and Holmes, C. C. (2010). On the utility of graphics cards to perform massively parallel implementation of advanced Monte Carlo methods. J. Comput. Graph. Statist. 19 769-789.
[37] Liu, J. S. (2001). Monte Carlo Strategies in Scientific Computing . Springer, New York. · Zbl 0991.65001
[38] Mattingly, J. C., Pillai, N. S. and Stuart, A. M. (2012). Diffusion limits of the random walk Metropolis algorithm in high dimensions. Ann. Appl. Probab. 22 881-930. · Zbl 1254.60081
[39] McLeish, D. L. (1974). Dependent central limit theorems and invariance principles. Ann. Probab. 2 620-628. · Zbl 0287.60025
[40] Meyn, S. and Tweedie, R. L. (2009). Markov chains and Stochastic Stability , 2nd ed. Cambridge Univ. Press, Cambridge. · Zbl 1165.60001
[41] Neal, R. M. (2001). Annealed importance sampling. Stat. Comput. 11 125-139.
[42] Pillai, N. S., Stuart, A. M. and Thiéry, A. H. (2012). Optimal scaling and diffusion limits for the Langevin algorithm in high dimensions. Ann. Appl. Probab. 22 2320-2356. · Zbl 1272.60053
[43] Roberts, G. O., Gelman, A. and Gilks, W. R. (1997). Weak convergence and optimal scaling of random walk Metropolis algorithms. Ann. Appl. Probab. 7 110-120. · Zbl 0876.60015
[44] Roberts, G. O. and Rosenthal, J. S. (1998). Optimal scaling of discrete approximations to Langevin diffusions. J. R. Stat. Soc. Ser. B Stat. Methodol. 60 255-268. · Zbl 0913.60060
[45] Rudin, W. (1976). Principles of Mathematical Analysis , 3rd ed. McGraw-Hill, New York. · Zbl 0346.26002
[46] Schäfer, C. and Chopin, N. (2013). Sequential Monte Carlo on large binary sampling spaces. Stat. Comput. 23 163-184. · Zbl 1322.62035
[47] Shiryaev, A. N. (1996). Probability , 2nd ed. Springer, New York. · Zbl 0909.01009
[48] Snyder, C., Bengtsson, T., Bickel, P. and Anderson, J. (2009). Obstacles to high-dimensional particle filtering. Mon. Weather Rev. 136 4629-4640.
[49] Whiteley, N. (2012). Sequential Monte Carlo samplers: Error bounds and insensitivity to initial conditions. Stoch. Anal. Appl. 30 774-798. · Zbl 1253.82077
[50] Whiteley, N. (2013). Stability properties of some particle filters. Ann. Appl. Probab. 23 2500-2537. · Zbl 1296.60098
[51] Whiteley, N., Kantas, N. and Jasra, A. (2012). Linear variance bounds for particle approximations of time-homogeneous Feynman-Kac formulae. Stochastic Process. Appl. 122 1840-1865. · Zbl 1262.60076
[52] Withers, C. S. (1981). Central limit theorems for dependent variables. I. Z. Wahrsch. Verw. Gebiete 57 509-534. · Zbl 0451.60027
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.