On the role of interaction in sequential Monte Carlo algorithms
arXiv:1309.2918 · doi:10.3150/14-BEJ666
Abstract
We introduce a general form of sequential Monte Carlo algorithm defined in terms of a parameterized resampling mechanism. We find that a suitably generalized notion of the Effective Sample Size (ESS), widely used to monitor algorithm degeneracy, appears naturally in a study of its convergence properties. We are then able to phrase sufficient conditions for time-uniform convergence in terms of algorithmic control of the ESS, in turn achievable by adaptively modulating the interaction between particles. This leads us to suggest novel algorithms which are, in senses to be made precise, provably stable and yet designed to avoid the degree of interaction which hinders parallelization of standard algorithms. As a byproduct, we prove time-uniform convergence of the popular adaptive resampling particle filter.
Published at http://dx.doi.org/10.3150/14-BEJ666 in the Bernoulli (http://isi.cbs.nl/bernoulli/) by the International Statistical Institute/Bernoulli Society (http://isi.cbs.nl/BS/bshome.htm)
References in corpus (2)
Cited by in corpus (26)
- Effective Sample Size for Importance Sampling based on discrepancy measures
- A Survey of Monte Carlo Methods for Parameter Estimation
- Kernel Risk-Sensitive Loss: Definition, Properties and Application to Robust Adaptive Filtering
- Adapting the Number of Particles in Sequential Monte Carlo Methods through an Online Scheme for Convergence Assessment
- Rethinking the Effective Sample Size
- Group Importance Sampling for Particle Filtering and MCMC
- A Compilation Target for Probabilistic Programming Languages
- Divide-and-Conquer with Sequential Monte Carlo
- candl: Cosmic Microwave Background Analysis with a Differentiable Likelihood
- A proof of uniform convergence over time for a distributed particle filter
- Asynchronous Anytime Sequential Monte Carlo
- Sequential Monte Carlo as Approximate Sampling: bounds, adaptive resampling via -ESS, and an application to Particle Gibbs
- Importance Sampling: Intrinsic Dimension and Computational Cost
- Interacting Particle Markov Chain Monte Carlo
- A scalable optimal-transport based local particle filter
- A simple scheme for the parallelization of particle filters and its application to the tracking of complex stochastic systems
- Theory of Parallel Particle Filters for Hidden Markov Models
- Unifying Sequential Monte Carlo with Resampling Matrices
- Anytime Monte Carlo
- When is Particle Filtering Efficient for Planning in Partially Observed Linear Dynamical Systems?
- An Adaptive Resample-Move Algorithm for Estimating Normalizing Constants
- Sequential Ensemble Transform for Bayesian Inverse Problems
- Generalized Posterior Calibration via Sequential Monte Carlo Sampler
- PF: A C++ Library for Fast Particle Filtering
- Fluctuations, stability and instability of a distributed particle filter with local exchange
- Parallelising Particle Filters with Butterfly Interactions