Windowed thinning and query complexity for the bouncy particle and Zigzag samplers
Abstract
Let μ(d x)∝ e−U(x) d x on Rd, 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 ε, the expected query counts are O(κ1/2d (dlogκ+log1/ε)) gradient queries for the bouncy particle sampler and O(κd1/4(dlogκ+log1/ε)) full-gradient equivalents for Zigzag, where d coordinate-partial queries count as one equivalent.
Related
- Hypocoercivity of Tempered Bouncy Particle Samplers for Heavy-Tailed Targets
- Entropy hypocoercivity and query complexity for the bouncy particle sampler
- Accelerated High-Accuracy Sampling from a Warm Start via the Proximal Bouncy Particle Sampler
- A priori regularity of the reverse heat flow and dimension-dependent complexity of higher-order diffusion samplers
- When Windowed Anderson Acceleration Converges Faster
BibTeX
@misc{lu2026windowed,
title = {{Windowed thinning and query complexity for the bouncy particle and Zigzag samplers}},
author = {Jianfeng Lu and Yinchen Luo},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.28413},
eprint = {2607.28413},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.28413},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Windowed thinning and query complexity for the bouncy particle and Zigzag samplers
AU - Jianfeng Lu
AU - Yinchen Luo
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2607.28413
UR - https://arxiv.org/abs/2607.28413
AB - Let μ(d x)∝ 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 ε, the expected query counts are O(κ^1/2d (dlogκ+log1/ε)) gradient queries for the bouncy particle sampler and O(κd^1/4(dlogκ+log1/ε)) full-gradient equivalents for Zigzag, where d coordinate-partial queries count as one equivalent.
ER -