Accelerated High-Accuracy Sampling from a Warm Start via the Proximal Bouncy Particle Sampler

Abstract

We study the problem of sampling from $\mu (\mathrm{d}x)\propto e^{-V(x)}\mathrm{d}x$ on ${\mathbb{R}}^d$, where $V$ is $\alpha$-strongly convex and $\beta$-smooth, and write $\kappa :=\beta /\alpha$. We design and analyze the Proximal Bouncy Particle Sampler (Proximal BPS), a new sampler that combines ideas from the proximal sampler and the bouncy particle sampler. From a warm start initialization with $O(1)$ Rényi divergence w.r.t. $\mu$, Proximal BPS returns a sample whose law is $\epsilon$-close to $\mu$ in total variation distance using $\tilde{O}(\sqrt{\kappa }{d}^{1/4}\mathrm{polylog}(1/\epsilon ))$ gradient queries in expectation.