Markov Chain Monte Carlo using Hamiltonian Dynamics: A Study in Stochastic Processes

Abstract

The goal of this thesis is to understand why Hamiltonian Monte Carlo has become such a successful method in machine learning applications for sampling from complex probability distributions. This understanding is developed by building a theoretical framework that starts with discrete-time Markov chains and progresses through modern Markov Chain Monte Carlo (MCMC) methods. First, the theory of discrete-time Markov chains is established, providing the essential foundation for constructing MCMC algorithms. Next, the Metropolis-Hastings algorithm is examined as the foundational framework upon which HMC is built, highlighting its critical limitations in high-dimensional settings, specifically, how random walk proposals suffer from quadratic scaling with dimension. Hamiltonian Monte Carlo addresses these limitations by leveraging geometric insights from classical mechanics, using principles of energy conservation and volume preservation to achieve linear displacement scaling, thus avoiding the inefficiencies of random walk behavior.