Abstract: Heavy-tailed target distributions, arising frequently in statistics and machine learning, are very challenging in practice due to a typically poor performance of sampling algorithms. Based on practical L-drift conditions on the one-step transition kernels, we develop a new theory for comparing general Markov chains converging to a heavy-tailed distribution $\pi$. We apply our theory to the random walk Metropolis (RWM) sampler with light- and heavy-tailed proposals, Metropolis adjusted Langevin algorithm (MALA), unadjusted Langevin algorithm (ULA) and the recent stereographic projection sampler (SPS). The L-drift conditions yield a mathematically rigorous quantification of the "stickiness" (in the tails of $\pi$) and poor mixing of these sampling algorithms, characterising their rate of convergence and the validity of the central limit theorem for ergodic averages. Our results inform algorithm selection for heavy-tailed target $\pi$ by, for example, guiding the choice of the tail decay in the RWM proposal or rigorously identifying scenarios where SPS outperforms the RWM, MALA or ULA. Moreover, by quantifying their impact, our results identify the key components that govern algorithm performance, such as the use of Metropolis correction and the role of gradients in heavy-tailed settings. Our robust approach also implies that a heavy-tailed version of ULA (e.g., discretisation of a L\'evy-driven SDEs with arbitrary drift), if convergent, necessarily targets a distribution without the second moment, extending the well-known result for ULA with lighter than Gaussian targets.

This is joint work with Miha Bresar and Gareth Roberts.