Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random steps
This provides a more efficient method for sampling in machine learning and statistics, addressing a known bottleneck in computational tasks like Bayesian inference, though it is incremental as it builds on existing HMC techniques.
The paper tackles the problem of efficiently sampling from high-dimensional Gaussian distributions using Hamiltonian Monte Carlo (HMC), showing that it can achieve an ε-close sample with Õ(√κ d^{1/4} log(1/ε)) gradient queries by using long and random integration times, improving over lower bounds for fixed integration times.
Hamiltonian Monte Carlo (HMC) is a Markov chain algorithm for sampling from a high-dimensional distribution with density $e^{-f(x)}$, given access to the gradient of $f$. A particular case of interest is that of a $d$-dimensional Gaussian distribution with covariance matrix $Σ$, in which case $f(x) = x^\top Σ^{-1} x$. We show that HMC can sample from a distribution that is $\varepsilon$-close in total variation distance using $\widetilde{O}(\sqrtκ d^{1/4} \log(1/\varepsilon))$ gradient queries, where $κ$ is the condition number of $Σ$. Our algorithm uses long and random integration times for the Hamiltonian dynamics. This contrasts with (and was motivated by) recent results that give an $\widetildeΩ(κd^{1/2})$ query lower bound for HMC with fixed integration times, even for the Gaussian case.