On the stability of sequential Monte Carlo methods in high dimensions

DOI10.1214/13-AAP951MaRDI QIDQ2511554zbMATH OpenFDO

Authors Alexandros Beskos, Ajay Jasra, Dan Crisan

Publication date 6 August 2014

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1103.3965, https://projecteuclid.org/euclid.aoap/1400073653

convergence effective sample size functional central limit theorem high dimensions importance sampling resampling sequential Monte Carlo method stability target distribution

Mathematics Subject Classification ID

Limit theorems in probability theory (60F99) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Bayesian inference (62F15) Monte Carlo methods (65C05) Numerical methods (including Monte Carlo methods) (91G60)

Abstract: We investigate the stability of a Sequential Monte Carlo (SMC) method applied to the problem of sampling from a target distribution on

m a t h b b 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

v a r e p s i l o n_{N}

as

d i g h t a r r o w i n f t y

with

1 < v a r e p s i l o n_{N} < N

. The convergence is achieved with a computational cost proportional to

N d^{2}

. If

v a r e p s i l o n_{N} l l 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

v a r e p s i l o n_{N, m}

as

d i g h t a r r o w i n f t y

and

l i m_{m o i n f t y} v a r e p s i l o n_{N, m} = N

. Also, we show that the Monte Carlo error for estimating a fixed dimensional marginal expectation is of order

f r a c 1 s q r t 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.

Review text

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.

Recommendations

Cites work

Cited in

(66)

This page was built for publication: On the stability of sequential Monte Carlo methods in high dimensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2511554)