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

2026/07/30 by Jianfeng Lu, Yinchen Luo
Mathematics · Computer Science · #math.NA #cs.LG #cs.NA #math.PR #math.ST #stat.TH #msc:65C05 #msc:60J25 #msc:65C40 #msc:65Y20

paper · pdf

arxiv created 2026/07/30 · arxiv updated 2026/07/31

Abstract

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κ+log\frac1ε)) gradient queries for the bouncy particle sampler and O(κd^1/4(dlogκ+log\frac1ε)) full-gradient equivalents for Zigzag, where d coordinate-partial queries count as one equivalent.

Citations

• Space-Time Log-Sobolev Inequality and Hypocoercive Hypercontractivity for Underdamped Langevin Dynamics
• Shifted Composition IV: Toward Ballistic Acceleration for Log-Concave Sampling
• Automated Techniques for Efficient Sampling of Piecewise-Deterministic Markov Processes
• Non-reversible lifts of reversible diffusion processes and relaxation times
• Scaling of Piecewise Deterministic Monte Carlo for Anisotropic Targets
• Faster high-accuracy log-concave sampling via algorithmic warm starts
• Automatic Zig-Zag sampling in practice
• Concave-Convex PDMP-based sampling
• Concentration Inequalities and UQ Bounds for Hypocoercive MCMC Samplers
• Hypocoercivity of Piecewise Deterministic Markov Process-Monte Carlo
• High-dimensional scaling limits of piecewise deterministic sampling algorithms
• Geometric ergodicity of the bouncy particle sampler
• Exponential Ergodicity of the Bouncy Particle Sampler
• Forward Event-Chain Monte Carlo: Fast sampling by randomness control in irreversible Markov chains
• The Bouncy Particle Sampler: A Non-Reversible Rejection-Free Markov\n Chain Monte Carlo Method

Related

• A Discrete Bouncy Particle Sampler
• High-dimensional scaling limits of piecewise deterministic sampling algorithms
• Stochastic Bouncy Particle Sampler
• Spatiotemporal blocking of the bouncy particle sampler for efficient inference in state space models
• Transient regime of piecewise deterministic Monte Carlo algorithms