Exponential speed up in Monte Carlo sampling through radial updates

Abstract Recently, it has been shown that the hybrid Monte Carlo (HMC) algorithm is guaranteed to converge exponentially to a given target probability distribution <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>∝</mml:mo> <mml:mrow> <mml:msup> <mml:mrow> <mml:mi mathvariant="normal">e</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>−</mml:mo> <mml:mi>V</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:msup> </mml:mrow> </mml:mrow> </mml:math> 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:mo stretchy="false">|</mml:mo> <mml:mrow> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mi>x</mml:mi> <mml:mrow> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mrow> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:mi>f</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>z</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:math> so that the effective potential <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:mi>V</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>f</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>z</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:math> grows exponentially with <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:mi>z</mml:mi> <mml:mo stretchy="false">→</mml:mo> <mml:mo>±</mml:mo> <mml:mi mathvariant="normal">∞</mml:mi> </mml:mrow> </mml:math> . Any additive update of z then leads to the desired convergence. We show that choosing this update from a normal distribution with standard deviation <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:mi>σ</mml:mi> <mml:mo>≈</mml:mo> <mml:mn>1</mml:mn> <mml:mrow> <mml:mo>/</mml:mo> </mml:mrow> <mml:msqrt> <mml:mi>d</mml:mi> </mml:msqrt> </mml:mrow> </mml:math> 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.