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

Let μ(d x)propto e-U(x) d x on Rd, 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(kappa1/2d,(dlogkappa+logfrac1varepsilon)) gradient queries for the bouncy particle sampler and O(kappa d1/4(dlogkappa+logfrac1varepsilon)) full-gradient equivalents for Zigzag, where d coordinate-partial queries count as one equivalent.