Finite-sample complexity of sequential Monte Carlo estimators

DOI10.1214/23-AOS2295MaRDI QIDQ6177328zbMATH OpenOpenAlexFDO

Authors Joe Marion, Joseph Mathews, Scott C. Schmidler

Publication date 31 August 2023

Published in The Annals of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.09365, https://projecteuclid.org/journals/annals-of-statistics/volume-51/issue-3/Finite-sample-complexity-of-sequential-Monte-Carlo-estimators/10.1214/23-AOS2295.full

zbMATH Keywords

Bayesian computationsequential Monte Carlocomputational complexity

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Bayesian inference (62F15)

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.

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

• scientific article; zbMATH DE number 1666085 (Why is no real title available?)
• scientific article; zbMATH DE number 1500585 (Why is no real title available?)
• scientific article; zbMATH DE number 2106098 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 5019925 (Why is no real title available?)
• A nonasymptotic theorem for unnormalized Feynman-Kac particle models
• A sequential particle filter method for static models
• Adaptive sequential posterior simulators for massively parallel computing environments
• Central limit theorem for nonlinear filtering and interacting particle systems
• Central limit theorem for sequential Monte Carlo methods and its application to Bayesian inference
• Conditions for rapid mixing of parallel and simulated tempering on multimodal distributions
• Error bounds for sequential Monte Carlo samplers for multimodal distributions
• Forest resampling for distributed sequential Monte Carlo
• General state space Markov chains and MCMC algorithms
• Hit-and-run from a corner
• Limit theorems for weighted samples with applications to sequential Monte Carlo methods
• Log-concave sampling: Metropolis-Hastings algorithms are fast
• Non-asymptotic error bounds for sequential MCMC methods
• On parallel implementation of sequential Monte Carlo methods: the island particle model
• On the convergence of adaptive sequential Monte Carlo methods
• On the stability of sequential Monte Carlo methods in high dimensions
• Quantitative approximations of evolving probability measures and sequential Markov chain Monte Carlo methods
• Random generation of combinatorial structures from a uniform distribution
• Random walks and anO*(n5) volume algorithm for convex bodies
• Recursive Monte Carlo filters: algorithms and theoretical analysis
• Sequential Monte Carlo Samplers
• Sequential Monte Carlo Samplers: Error Bounds and Insensitivity to Initial Conditions
• Sequential Monte Carlo for rare event estimation
• Stability and uniform approximation of nonlinear filters using the Hilbert metric and application to particle filters
• Stability of sequential Markov Chain Monte Carlo methods
• Sufficient conditions for torpid mixing of parallel and simulated tempering
• The geometry of logconcave functions and sampling algorithms
• Theoretical Guarantees for Approximate Sampling from Smooth and Log-Concave Densities

Cited in

(5)

• Finite sample complexity of sequential Monte Carlo estimators on multimodal target distributions
• 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

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)