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

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)

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.

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

Cites work

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

Cited in

(58)

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

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)