Research
Windowed thinning and query complexity for the bouncy particle and Zigzag samplers
arXiv:2607.28413v1 Announce Type: cross Abstract: 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
arXiv:2607.28413v1 Announce Type: cross Abstract: 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 arepsilon, the expected query counts are O(kappa^{1/2}d,(dlogkappa+logfrac1arepsilon)) gradient queries for the bouncy particle sampler and O(kappa d^{1/4}(dlogkappa+logfrac1arepsilon)) full-gradient equivalents for Zigzag, where d coordinate-partial queries count as one equivalent.
Related
Source: arXiv cs.LG | 2026-07-31