Intermediate Distributions and Complexity Bounds for SMC
- Prof. Anthony Lee, School of Mathematics, University of Bristol
KAUST
It is now fairly common to use Sequential Monte Carlo (SMC) algorithms for normalizing constant estimation of high-dimensional, complex distributions without any particular structure. In order for the algorithm to give reasonable accuracy, it is well known empirically that one must introduce appropriate intermediate distributions that allow the particle system to “gradually evolve” from a simple initial distribution to the complex target distribution, and one must also specify an appropriate number of particles to control the error. Since both the number of intermediate distributions and the number of particles affect the computational cost of the algorithm, it is crucial to study and attempt to minimize the computational cost of the algorithm subject to constraints on the error.
Overview
Abstract
It is now fairly common to use Sequential Monte Carlo (SMC) algorithms for normalizing constant estimation of high-dimensional, complex distributions without any particular structure. In order for the algorithm to give reasonable accuracy, it is well known empirically that one must introduce appropriate intermediate distributions that allow the particle system to “gradually evolve” from a simple initial distribution to the complex target distribution, and one must also specify an appropriate number of particles to control the error. Since both the number of intermediate distributions and the number of particles affect the computational cost of the algorithm, it is crucial to study and attempt to minimize the computational cost of the algorithm subject to constraints on the error. We present three strategies that have been used to specify intermediate distributions and provide bounds on the computational complexity of normalizing constant estimation with well-tuned sequences, which involves obtaining bounds on the length of sequences of intermediate distributions. Although the results for SMC algorithms involve some fairly strong assumptions on the Markov kernels involved, they are to the best of our knowledge the only general results available thus far. This primarily theoretical analysis also suggests where further research is required to tune the approach.
Brief Biography
Anthony Lee is a Computational Statistician in the School of Mathematics at the University of Bristol, and Director of the Data Science at Scale Programme at the Alan Turing Institute. He obtained BSc. and MSc. degrees in Computer Science at the University of British Columbia and a DPhil. in Statistics at the University of Oxford. Following a Research Fellowship at the University of Warwick, he took up a lectureship there before moving to the University of Bristol where he is currently Heilbronn Chair in Data Science.
His research is primarily in the area of stochastic algorithms for approximating intractable quantities that arise in data analysis. Examples of such algorithms are Markov chain and Sequential Monte Carlo. He works on both theory and methodology: research in this area is interdisciplinary, bringing together advances in applied probability, algorithms, and statistics. He is often interested in algorithms that scale well in parallel and distributed computing environments, and in computational and statistical trade-offs when conducting inference.