Abstract

Generating samples from complex probability distributions is a fundamental challenge in statistical modelling and Bayesian statistics. In practice, this is generally impossible, and we must introduce a simpler reference distribution, such as a Gaussian, and manipulate its density and samples to approximate the target. In general, direct inference is reliable when the reference is close to the target and fragile when it is not. Annealing is a popular technique motivated by this principle and introduces a sequence of distributions that interpolates between the reference and target, ensuring the neighbouring distributions are close enough. An annealing algorithm specifies how to traverse this bridge of distributions to incrementally transform samples from the reference into samples approximating the target.

In this talk, we will construct two computationally dual annealing algorithms called Sequential Monte Carlo Samplers (SMC) and Parallel Tempering (PT), which propagate samples from the reference to the target using importance sampling and Metropolis-Hasting, respectively. By analysing the variance of the normalising constant estimator, we will see how the performance scales with increasing runtime, parallelism, memory, and the difficulty of the inference problem. Notable, we will identify a critical phenomenon and explain why these algorithms are efficient and can scale to tackle modern sampling problems. Finally, we will provide a black-box algorithm to tune these algorithms efficiently and practical guidelines for when to implement SMC versus PT.