On the stability of sequential Monte Carlo methods in high dimensions

By Alexandros Beskos, D. Crisan, Ajay Jasra. 2011

186 citations recorded by the source corpus.

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–32 9 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 eN as d → ∞ with 1 < eN < N. The convergence is achieved with a computational cost proportional to Nd2. If eN � 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 eN,m as d → ∞ and limm→∞ eN,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.

Subfields: Management Science and Operations Research, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/a3130f3b3d1604b7547c1ef0cd5a7e157c0f1070

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Management Science and Operations Research

In Statistics and Probability

Citations in the corpus

Bayesian Probabilistic Numerical Methods (2017, methodology): “Development of SMC methods in the context of high-dimensional and infinitedimensional state spaces has also been considered in Beskos et al. (2014, 2015).”
A local particle filter for high-dimensional geophysical systems (2015, methodology): “Further, Beskos et al. (2012) discuss recursive methods for estimating the proposal densities, similar to the running-in-place algorithm (Yang et al., 2012a, b; Penny et al., 2013) that has been used with LETKF in meteorological and oceanographic data assimilation.”
Error Bounds and Normalising Constants for Sequential Monte Carlo Samplers in High Dimensions (2014, methodology): “The objective of this paper is to provide a more complete understanding of SMC samplers in high dimensions, complementing and building upon the results of [3].”
Nested Sequential Monte Carlo Methods (2015, unknown): “Furthermore, we have found (see Section 6) that NSMC can outperform ST-PF even when run on a single machine with matched computational costs.”
Data Assimilation: A Mathematical Introduction (2015, background): “Whilst there is ongoing work to overcome these problems with high-dimensional particle filtering, see [14, 25, 115] for example, this work has yet to impact practical data assimilation in, for example, operational weather forecasting.”