Search papers, labs, and topics across Lattice.
This paper introduces windowed thinning as an exact simulation method for the bouncy particle sampler and the coordinate Zigzag process, leveraging deterministic trajectory windows and gradient evaluations to create a local envelope for event rates. The authors derive query complexity guarantees that significantly improve efficiency, showing that the expected number of gradient queries required for the bouncy particle sampler scales as \(O(\kappa^{1/2}d\,(d\log\kappa+\log\frac1\varepsilon))\) and for the Zigzag process as \(O(\kappa d^{1/4}(d\log\kappa+\log\frac1\varepsilon))\). These results highlight the potential for enhanced sampling efficiency in high-dimensional spaces, which is crucial for applications in Bayesian inference and machine learning.
Query complexity for bouncy particle and Zigzag samplers can be drastically reduced using windowed thinning, achieving efficiency gains that scale with the condition number.
Let $\mu(d x)\propto e^{-U(x)} d x$ on $\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 $\varepsilon$, the expected query counts are $O(\kappa^{1/2}d\,(d\log\kappa+\log\frac1\varepsilon))$ gradient queries for the bouncy particle sampler and $O(\kappa d^{1/4}(d\log\kappa+\log\frac1\varepsilon))$ full-gradient equivalents for Zigzag, where $d$ coordinate-partial queries count as one equivalent.
