On the stability of sequential Monte Carlo methods in high dimensions

DOI10.1214/13-AAP951zbMATH Open1304.82070arXiv1103.3965MaRDI QIDQ2511554FDOQ2511554

Authors: Alexandros Beskos, Ajay Jasra, Dan Crisan 

Publication date: 6 August 2014

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

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 $varepsilo{n}_N$ as $dightarrowinfty$ with $1<varepsilo{n}_N<N$. The convergence is achieved with a computational cost proportional to $N{d}^2$. If $varepsilo{n}_{N}llN$, 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 $varepsilo{n}_{N,m}$ as $dightarrowinfty$ and $li{m}_{moinfty}varepsilo{n}_{N,m}=N$. Also, we show that the Monte Carlo error for estimating a fixed dimensional marginal expectation is of order $frac1sqrtN$ 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.

Full work available at URL: https://arxiv.org/abs/1103.3965

Recommendations

• Error bounds and normalising constants for sequential Monte Carlo samplers in high dimensions
• Conditional sequential Monte Carlo in high dimensions
• On adaptive resampling strategies for sequential Monte Carlo methods
• Sequential Monte Carlo Samplers: Error Bounds and Insensitivity to Initial Conditions
• scientific article; zbMATH DE number 5007617

zbMATH Keywords

convergencehigh dimensionsimportance samplingresamplingstabilityfunctional central limit theoremeffective sample sizetarget distributionsequential Monte Carlo method

Mathematics Subject Classification ID

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

Cites Work

• Sequential Monte Carlo Methods in Practice
• Sequential Monte Carlo Samplers
• Title not available (Why is that?)
• Weak convergence and optimal scaling of random walk Metropolis algorithms
• Markov Chains and Stochastic Stability
• Title not available (Why is that?)
• Central limit theorem for sequential Monte Carlo methods and its application to Bayesian inference
• On the stability of sequential Monte Carlo methods in high dimensions
• Curse-of-dimensionality revisited: Collapse of the particle filter in very large scale systems
• Stability properties of some particle filters
• Title not available (Why is that?)
• Sequential Imputations and Bayesian Missing Data Problems
• Title not available (Why is that?)
• Error bounds and normalising constants for sequential Monte Carlo samplers in high dimensions
• Monte Carlo strategies in scientific computing
• A sequential particle filter method for static models
• Limit theorems for weighted samples with applications to sequential Monte Carlo methods
• Dependent central limit theorems and invariance principles
• Optimal Scaling of Discrete Approximations to Langevin Diffusions
• On the ergodicity properties of some adaptive MCMC algorithms
• Title not available (Why is that?)
• An adaptive sequential Monte Carlo method for approximate Bayesian computation
• Title not available (Why is that?)
• Recursive Monte Carlo filters: algorithms and theoretical analysis
• Optimal scalings for local Metropolis-Hastings chains on nonproduct targets in high dimensions
• Inference for Lévy-driven stochastic volatility models via adaptive sequential Monte Carlo
• On adaptive resampling strategies for sequential Monte Carlo methods
• Sequential Monte Carlo on large binary sampling spaces
• Central Limit Theorems for dependent variables. I
• Tree based functional expansions for Feynman--Kac particle models
• Optimal tuning of the hybrid Monte Carlo algorithm
• MCMC methods for sampling function space
• On nonlinear Markov chain Monte Carlo
• Uniform approximations of discrete-time filters
• Linear variance bounds for particle approximations of time-homogeneous Feynman-Kac formulae
• Sequential Monte Carlo Samplers: Error Bounds and Insensitivity to Initial Conditions
• Asymptotic behaviour of a class of stochastic approximation procedures
• Quantitative bounds on convergence of time-inhomogeneous Markov chains
• From Metropolis to diffusions: Gibbs states and optimal scaling.
• Optimal scaling of MaLa for nonlinear regression.
• Weak convergence of Metropolis algorithms for non-I.I.D. target distributions
• Diffusion limits of the random walk Metropolis algorithm in high dimensions
• Optimal scaling and diffusion limits for the Langevin algorithm in high dimensions

Cited In (58)

• Asymptotic behavior of the forecast-assimilation process with unstable dynamics
• Ensemble MCMC: accelerating pseudo-marginal MCMC for state space models using the ensemble Kalman filter
• A unified framework for the analysis of accuracy and stability of a class of approximate Gaussian filters for the Navier-Stokes equations
• Statistical inference with quantum measurements: methodologies for nitrogen vacancy centers in diamond
• On spatially correlated observations in importance sampling methods for subsidence estimation
• Finite-sample complexity of sequential Monte Carlo estimators
• Convergence acceleration of ensemble Kalman inversion in nonlinear settings
• Randomized maximum likelihood based posterior sampling
• Sequential estimation of temporally evolving latent space network models
• Error bounds and normalising constants for sequential Monte Carlo samplers in high dimensions
• Approximate large-scale Bayesian spatial modeling with application to quantitative magnetic resonance imaging
• Monotone Emulation of Computer Experiments
• A lagged particle filter for stable filtering of certain high-dimensional state-space models
• Sequential Monte Carlo for Bayesian sequentially designed experiments for discrete data
• An adaptive sequential Monte Carlo method for approximate Bayesian computation
• An Invitation to Sequential Monte Carlo Samplers
• A simulated annealing approach to approximate Bayes computations
• Polynomial Propagation of Moments in Stochastic Differential Equations
• Sequential Bayesian inference for implicit hidden Markov models and current limitations
• Stability of sequential Monte Carlo samplers via the Foster-Lyapunov condition
• Importance sampling: intrinsic dimension and computational cost
• Sequential Monte Carlo with transformations
• Particle Filters for nonlinear data assimilation in high-dimensional systems
• On the stability of sequential Monte Carlo methods in high dimensions
• On the convergence of adaptive sequential Monte Carlo methods
• Sequentially constrained Monte Carlo
• A particle filter for stochastic advection by Lie transport: a case study for the damped and forced incompressible two-dimensional Euler equation
• Iterative Bayesian inversion with Gaussian mixtures: finite sample implementation and large sample asymptotics
• Multilevel ensemble Kalman filtering for spatio-temporal processes
• Pricing discretely-monitored double barrier options with small probabilities of execution
• Improving SAMC using smoothing methods: Theory and applications to Bayesian model selection problems
• Robust measurement of (heavy-tailed) risks: theory and implementation
• Multilevel sequential Monte Carlo with dimension-independent likelihood-informed proposals
• Sparse index tracking using sequential Monte Carlo
• A 4D-Var method with flow-dependent background covariances for the shallow-water equations
• A unified performance analysis of likelihood-informed subspace methods
• Sequential Monte Carlo methods for Bayesian elliptic inverse problems
• Population Monte Carlo algorithm in high dimensions
• Bayesian Conditional Density Filtering
• Inference on high-dimensional implicit dynamic models using a guided intermediate resampling filter
• A stable particle filter for a class of high-dimensional state-space models
• A population Monte Carlo scheme with transformed weights and its application to stochastic kinetic models
• Data assimilation for a quasi-geostrophic model with circulation-preserving stochastic transport noise
• Likelihood-free parallel tempering
• Clustered exact Daum-Huang particle flow filter
• On the optimality and stability of exponential twisting in Monte Carlo estimation
• Quantitative approximations of evolving probability measures and sequential Markov chain Monte Carlo methods
• Advanced Multilevel Monte Carlo Methods
• Long-time asymptotics of the filtering distribution for partially observed chaotic dynamical systems
• Practical adaptive quantum tomography
• Affine-invariant ensemble transform methods for logistic regression
• Sequential Monte Carlo EM for multivariate probit models
• Inference for a class of partially observed point process models
• Some contributions to sequential Monte Carlo methods for option pricing
• Nested particle filters for online parameter estimation in discrete-time state-space Markov models
• Linear variance bounds for particle approximations of time-homogeneous Feynman-Kac formulae
• Error bounds for sequential Monte Carlo samplers for multimodal distributions
• Multilevel sequential Monte Carlo samplers

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)