Finite-sample complexity of sequential Monte Carlo estimators
From MaRDI portal
Publication:6177328
DOI10.1214/23-AOS2295arXiv1803.09365OpenAlexW2795211099MaRDI QIDQ6177328FDOQ6177328
Authors: Joe Marion, Joseph Mathews, Scott C. Schmidler 
Publication date: 31 August 2023
Published in: The Annals of Statistics (Search for Journal in Brave)
Abstract: We present bounds for the finite sample error of sequential Monte Carlo samplers on static spaces. Our approach explicitly relates the performance of the algorithm to properties of the chosen sequence of distributions and mixing properties of the associated Markov kernels. This allows us to give the first finite sample comparison to other Monte Carlo schemes. We obtain bounds for the complexity of sequential Monte Carlo approximations for a variety of target distributions including finite spaces, product measures, and log-concave distributions including Bayesian logistic regression. The bounds obtained are within a logarithmic factor of similar bounds obtainable for Markov chain Monte Carlo.
Full work available at URL: https://arxiv.org/abs/1803.09365
Recommendations
- Computational complexity of Markov chain Monte Carlo methods for finite Markov random fields
- On the computational complexity of MCMC-based estimators in large samples
- Sequential Monte Carlo Samplers: Error Bounds and Insensitivity to Initial Conditions
- Complexity results for MCMC derived from quantitative bounds
- Sequential Monte Carlo on large binary sampling spaces
- Complexity bounds for Markov chain Monte Carlo algorithms via diffusion limits
- Sequential Monte Carlo Samplers
- An Invitation to Sequential Monte Carlo Samplers
- Efficient Sequential Monte-Carlo Samplers for Bayesian Inference
Cites Work
- Sequential Monte Carlo Samplers
- Stability and uniform approximation of nonlinear filters using the Hilbert metric and application to particle filters
- 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
- Title not available (Why is that?)
- On parallel implementation of sequential Monte Carlo methods: the island particle model
- A sequential particle filter method for static models
- Limit theorems for weighted samples with applications to sequential Monte Carlo methods
- Conditions for rapid mixing of parallel and simulated tempering on multimodal distributions
- General state space Markov chains and MCMC algorithms
- A nonasymptotic theorem for unnormalized Feynman-Kac particle models
- Random generation of combinatorial structures from a uniform distribution
- Random walks and anO*(n5) volume algorithm for convex bodies
- Title not available (Why is that?)
- Recursive Monte Carlo filters: algorithms and theoretical analysis
- Sequential Monte Carlo for rare event estimation
- Title not available (Why is that?)
- Adaptive sequential posterior simulators for massively parallel computing environments
- On the convergence of adaptive sequential Monte Carlo methods
- Hit-and-run from a corner
- Sufficient conditions for torpid mixing of parallel and simulated tempering
- Central limit theorem for nonlinear filtering and interacting particle systems
- Title not available (Why is that?)
- Title not available (Why is that?)
- The geometry of logconcave functions and sampling algorithms
- Sequential Monte Carlo Samplers: Error Bounds and Insensitivity to Initial Conditions
- Quantitative approximations of evolving probability measures and sequential Markov chain Monte Carlo methods
- Theoretical Guarantees for Approximate Sampling from Smooth and Log-Concave Densities
- Stability of sequential Markov Chain Monte Carlo methods
- Log-concave sampling: Metropolis-Hastings algorithms are fast
- Non-asymptotic error bounds for sequential MCMC methods
- Error bounds for sequential Monte Carlo samplers for multimodal distributions
- Forest resampling for distributed sequential Monte Carlo
Cited In (5)
- Stability of sequential Monte Carlo samplers via the Foster-Lyapunov condition
- On the Power of Restricted Monte Carlo Algorithms
- Finite space Kantorovich problem with an MCMC of table moves
- Sequential Monte Carlo Samplers: Error Bounds and Insensitivity to Initial Conditions
- Finite sample complexity of sequential Monte Carlo estimators on multimodal target distributions
This page was built for publication: Finite-sample complexity of sequential Monte Carlo estimators
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6177328)
