Finite Sample Complexity of Sequential Monte Carlo Estimators

2018/03/25 by Joe Marion, Marion, Joe, Joseph Mathews +3 · 4 citations
Mathematics · Computer Science · #Markov Chains and Monte Carlo Methods #Statistical Methods and Inference #Bayesian Methods and Mixture Models

paper · pdf · doi:10.48550/arxiv.1803.09365

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.

Cited by

• Convergence of a Sequential Monte Carlo algorithm towards multimodal distributions on Rd
• Improved Bounds for Context-Dependent Evolutionary Models Using Sequential Monte Carlo
• Partial Envelope for Optimization Problem with Nonconvex Constraints
• On the complexity of standard and waste-free SMC samplers
• Polynomial complexity sampling from multimodal distributions using Sequential Monte Carlo

Related

• Finite Sample Complexity of Sequential Monte Carlo Estimators on Multimodal Target Distributions
• Sequential Monte Carlo samplers: error bounds and insensitivity to initial conditions
• Finite Sample Bounds for Sequential Monte Carlo and Adaptive Path Selection Using the L₂ Norm
• Error Bounds for Sequential Monte Carlo Samplers for Multimodal\n Distributions
• Error Bounds and Normalizing Constants for Sequential Monte Carlo in High Dimensions