On the stability of sequential Monte Carlo methods in high dimensions

We investigate the stability of a Sequential Monte Carlo (SMC) method applied to the problem of sampling from a target distribution on Rd for large d. It is well known [Bengtsson, Bickel and Li, In Probability and Statistics: Essays in Honor of David A. Freedman, D. Nolan and T. Speed, eds. (2008) 316.334 IMS; see also Pushing the Limits of Contemporary Statistics (2008) 318.329 IMS, Mon. Weather Rev. (2009) 136 (2009) 4629.4640] that using a single importance sampling step, one produces an approximation for the target that deteriorates as the dimension d increases, unless the number of Monte Carlo samples N increases at an exponential rate in d. We show that this degeneracy can be avoided by introducing a sequence of artificial targets, starting from a .simple. density and moving to the one of interest, using an SMC method to sample from the sequence; see, for example, Chopin [Biometrika 89 (2002) 539.551]; see also [J. R. Stat. Soc. Ser. B Stat. Methodol. 68 (2006) 411.436, Phys. Rev. Lett. 78 (1997) 2690.2693, Stat. Comput. 11 (2001) 125.139]. Using this class of SMC methods with a fixed number of samples, one can produce an approximation for which the effective sample size (ESS) converges to a random variable .N as d.. with 1<.N<N. The convergence is achieved with a computational cost proportional to Nd2. If .N.N, we can raise its value by introducing a number of resampling steps, say m (where m is independent of d). In this case, the ESS converges to a random variable .N,m as d.. and limm...N,m=N. Also, we show that the Monte Carlo error for estimating a fixed-dimensional marginal expectation is of order 1.N uniformly in d. The results imply 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 and indicate that resampling leads to a reduction in the Monte Carlo error and increase in the ESS. All of our analysis is made under the assumption that the target density is i.i.d.