On the Stability of Sequential Monte Carlo Methods in High Dimensions

Abstract

We investigate the stability of a Sequential Monte Carlo (SMC) method applied to the problem of sampling from a target distribution on ${\mathbb{R}}^d$ for large $d$. It is well known 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. 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 ${\epsilon }_N$ as $d\to \infty$ with $1<{\epsilon }_N<N$. The convergence is achieved with a computational cost proportional to $N{d}^2$. If ${\epsilon }_N\ll N$, we can raise its value by introducing a number of resampling steps, say $m$ (where $m$ is independent of $d$). In this case, ESS converges to a random variable ${\epsilon }_{N,m}$ as $d\to \infty$ and ${\lim }_{m\to \infty }{\epsilon }_{N,m}=N$. Also, we show that the Monte Carlo error for estimating a fixed dimensional marginal expectation is of order $\frac{1}{\sqrt{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, in high dimensions, resampling leads to a reduction in the Monte Carlo error and increase in the ESS.

References in corpus (9)

• Curse-of-dimensionality revisited: Collapse of the particle filter in very large scale systems
• On adaptive resampling strategies for sequential Monte Carlo methods
• Sharp failure rates for the bootstrap particle filter in high dimensions
• Quantitative bounds on convergence of time-inhomogeneous Markov chains
• Optimal scalings for local Metropolis--Hastings chains on nonproduct targets in high dimensions
• Diffusion limits of the random walk Metropolis algorithm in high dimensions
• Linear Variance Bounds for Particle Approximations of Time-Homogeneous Feynman-Kac Formulae
• Tree based functional expansions for Feynman--Kac particle models
• A strong law of large numbers for martingale arrays

Cited by in corpus (8)

• Bridging the ensemble Kalman and particle filter
• Accuracy and Stability of The Continuous-Time 3DVAR Filter for The Navier-Stokes Equation
• A Simulated Annealing Approach to Approximate Bayes Computations
• Error Bounds and Normalizing Constants for Sequential Monte Carlo in High Dimensions
• Sequential Monte Carlo EM for multivariate probit models
• Monotone Function Estimation for Computer Experiments
• Inference for a Class of Partially Observed Point Process Models
• Computational Methods for a Class of Network Models