Entropy hypocoercivity and query complexity for the bouncy particle sampler

Source abstract

We study convergence in relative entropy of the bouncy particle sampler with Gaussian velocity refreshment, for a target $e^{-U}$ on $\mathbb R^d$ with $U$ $m$-strongly convex and $L$-smooth, and condition number $κ=L/m$. For initial laws with bounded density relative to equilibrium, we show that the relative entropy decays exponentially up to an arbitrary additive error $δ$, with a rate that depends only logarithmically on the density bound and on $δ$. From a Gaussian cold start and with a suitably chosen refreshment rate, the relative entropy falls below $δ$ after time $\widetilde O(\sqrt{d/m})$. Combined with exact simulation by windowed thinning, this gives an expected gradient-query complexity of $\widetilde O(d\sqrtκ)$, improving the $\widetilde O(d^2\sqrtκ)$ bound based on $L^2$ hypocoercivity.