Hird, Max Harwood; (2025) Beyond Canonical MCMC: Preconditioning, Adaptivity, and Variational Approximations. Doctoral thesis (Ph.D), UCL (University College London).

Preview

Text Hird_10210080_Thesis.pdf Download (5MB) | Preview

Abstract

Since its conception in the middle of the twentieth century Markov chain Monte Carlo (MCMC) has grown into a suite of methods that serve as the de facto algorithmic solutions to a particular set of scientific problems. In this time a selection of variants of MCMC have effectively become canonical through their popularity and use within software packages. These include the Random Walk Metropolis (RWM), the Metropolis Adjusted Langevin Algorithm (MALA), and Hamiltonian Monte Carlo (HMC). It has become increasingly clear that there are certain properties of probability distributions, such as high dimensionality, multimodality, and ill- conditioning, in the face of which these canonical algorithms will perform poorly. In this thesis we explore three methods: preconditioning, adaptivity, and variational approximation, that can enhance the performance of the canonical kernels in order to overcome these obstacles. Chapter 1 serves as a theoretical and conceptual introduction to these canonical kernels. Chapter 2 introduces the three methods which can be used to enhance the kernels described in chapter 1. In chapter 3 we examine linear preconditioning. This is the practice of applying a linear transformation to the target distribution to make it easier to sample from. Its success is measured by a quantity known as the condition number, denoted κ. We assert verifiable conditions under which linear preconditioning will change κ and make a given MCMC sampler more efficient. We identify a case in which a commonly used linear preconditioner will cause sampler performance to worsen. In chapter 4 we propose a novel way to combine a variational approximation to the target distribution with an arbitrary underlying MCMC kernel in order to reduce the variance of the estimators we derive from the MCMC chain. We call our method ‘the occlusion process’. We state the analytic form of the variance of the estimators it produces. We prove that it inherits numerous beneficial properties from the underlying MCMC kernel, such as a Law of Large Numbers, Geometric Ergodicity, and a Central Limit Theorem. We demonstrate empirically the occlusion process’ decorrelation and variance reduction capabilities on two target distributions. The first is a bimodal Gaussian mixture model in 1d and 100d. The second is the Ising model on an arbitrary graph, for which we propose a novel variational distribution. In chapter 5 we propose a linear preconditioner that is learned and used in an adaptive MCMC algo- rithm. The preconditioner is conceived so that it can capture correlations between the directions of the target distribution. It is structured so that the resulting adaptive MCMC algorithm operates at a per-iteration computational complexity which is linear in the dimension of the state space. We show that our proposed adaptive algorithm dominates the competing methods in terms of its efficiency per unit time when operating on high-dimensional ill-conditioned target distributions.

Download activity - last month

Export as CSVXMLJSON

Download activity - last 12 months

Export as JSONXMLCSV

Downloads by country - last 12 months

Export as CSVXMLJSON

Archive Staff Only

View Item