Windowed thinning and query complexity for the bouncy particle and Zigzag samplers

Abstract

Let $\mu (dx)\propto e^{-U(x)}dx$ on ${\mathbb{R}}^d$, where $U$ is $m$-strongly convex and $L$-smooth, and denote by $\kappa =L/m$ the condition number. We consider windowed thinning, an exact simulation method for the bouncy particle sampler and the coordinate Zigzag process. The method divides a trajectory into deterministic windows and uses a gradient evaluation at the beginning of each window to construct a tractable local envelope for the event rate. Combining this construction with quantitative mixing estimates and finite-time bounds on the expected numbers of bounces and flips yields query complexity guarantees from a Gaussian cold start. For total-variation error $\epsilon$, the expected query counts are $O({\kappa }^{1/2}d(d\log \kappa +\log \frac{1}{\epsilon }))$ gradient queries for the bouncy particle sampler and $O(\kappa d^{1/4}(d\log \kappa +\log \frac{1}{\epsilon }))$ full-gradient equivalents for Zigzag, where $d$ coordinate-partial queries count as one equivalent.

Topics & keywords