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

Abstract

Let $μ(d x)\propto e^{-U(x)} d x$ on $\R^d$, where $U$ is $m$-strongly convex and $L$-smooth, and denote by $κ=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(κ^{1/2}d\,(d\logκ+\log\frac1\varepsilon))$ gradient queries for the bouncy particle sampler and $O(κd^{1/4}(d\logκ+\log\frac1\varepsilon))$ full-gradient equivalents for Zigzag, where $d$ coordinate-partial queries count as one equivalent.

Disclosure

“ate-partial queries count as one full-gradient equivalent. The letter C denotes a universal constant whose value may change from line to line. Use of AI tools. The general algorithm design and analysis approach are created by the authors. LLM-based assistants were used in the preparation of this manuscript for drafting, language editing, and consistency checks. The authors are responsible for independently checking every statement and proof and for the correctness and integrity”

PDF page 5

Classification

Drafting limited passages

Multiplier

5

Verified

2026-08-23T19:14:12.959253Z

Structural counts