Exponential speed up in Monte Carlo sampling through radial updates

Source abstract

Abstract Recently, it has been shown that the hybrid Monte Carlo (HMC) algorithm is guaranteed to converge exponentially to a given target probability distribution p ( x ) ∝ e − V ( x ) on non-compact spaces if augmented by an appropriate radial update. In this work we present a simple way to derive efficient radial updates meeting the necessary requirements for any potential V . We reduce the problem to finding a substitution for the radial direction | | x | | = f ( z ) so that the effective potential V ( f ( z ) ) grows exponentially with z → ± ∞ . Any additive update of z then leads to the desired convergence. We show that choosing this update from a normal distribution with standard deviation σ ≈ 1 / d in d dimensions yields very good results. We further generalise the previous results on radial updates to a wide class of Markov chain Monte Carlo (MCMC) algorithms beyond the HMC and we quantify the convergence behaviour of MCMC algorithms with badly chosen radial update. Finally, we apply the radial update to the sampling of heavy-tailed distributions and achieve a speed up of many orders of magnitude.