Pith. sign in

REVIEW 5 minor 1 cited by

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

T0 review · 0 major / 5 minor · reviewed 2026-07-31 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Windowed thinning exactly simulates BPS and Zigzag from a Gaussian cold start and gives explicit gradient-query bounds of order κ^{1/2}d(d log κ + log 1/ε) and κ d^{1/4}(d log κ + log 1/ε).

desk verdict Solid cold-start query accounting for exact BPS/Zigzag via windowed thinning; the new technique is real, the proofs check out, and the dimension cost is honestly worse than MALA/FORS. read the letter →

arxiv 2607.28413 v1 pith:P7BMEENO submitted 2026-07-30 math.NA cs.LGcs.NAmath.PRmath.STstat.TH

Jianfeng Lu , Yinchen Luo This is my paper
classification math.NAcs.LGcs.NAmath.PRmath.STstat.TH MSC 65C0560J2565C4065Y20
keywords piecewisedeterministicMarkovprocessbouncyparticlesamplerZigzagPoissonthinningquerycomplexityhypocoercivitylog-concavesamplingwindowed
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Sampling from a strongly log-concave density can be done by continuous-time piecewise-deterministic processes such as the bouncy particle sampler and Zigzag: a particle flies in a straight line and only changes velocity at random bounce or flip times. Those event times depend on the gradient along the path, so exact simulation needs a tractable upper envelope and Poisson thinning. This paper introduces windowed thinning: the trajectory is cut into fixed windows, one gradient is evaluated at each window start, and Lipschitz smoothness supplies a local envelope that stays tight when windows are short. Combined with known χ² mixing rates and new finite-horizon bounds on expected bounces and flips from an explicit Gaussian cold start, the method yields end-to-end expected query complexities that are polylogarithmic in the accuracy. A reader who cares about high-accuracy sampling gets concrete oracle counts for two exact PDMP algorithms that previously lacked matching cold-start guarantees.

What carries the argument

Windowed thinning: partition the horizon into deterministic windows, evaluate the gradient at the start of each window, and build a local affine envelope for the bounce or flip rate from the cumulative distance travelled; the envelope is tight enough that the expected number of rejected proposals is controlled by the window length times velocity moments.

What would settle it

Implement windowed thinning for a standard Gaussian or strongly convex quadratic in moderate dimension, measure the actual expected gradient queries to reach a fixed TV tolerance from the stated cold start, and check whether the observed counts track the predicted κ^{1/2}d² and κ d^{5/4} scaling (up to the logarithmic factors) as κ and d vary.

Watch

Extended reading notes

Core claim

From the Gaussian cold start centered at the mode, windowed thinning exactly simulates the bouncy particle sampler and the coordinate Zigzag process; for total-variation error ε the expected number of gradient queries is O(κ^{1/2} d (d log κ + log 1/ε)) for BPS and O(κ d^{1/4} (d log κ + log 1/ε)) full-gradient equivalents for Zigzag, by balancing anchor evaluations against rejected proposals inside each window.

Load-bearing premise

The end-to-end bounds rest on external continuous-time χ² contraction rates for BPS and Zigzag at specific refreshment speeds; if those mixing times are substantially slower, the query counts inflate even though the simulation method remains exact.

Editorial extensions

If this is right

  • BPS becomes an exact high-accuracy sampler whose cold-start gradient cost scales like square-root condition number times d² (up to logs), competitive in κ with leading first-order methods though worse in dimension.
  • Zigzag admits an exact cold-start guarantee of order κ d^{5/4} full-gradient equivalents, improving the earlier warm-start global-envelope analysis in condition-number dependence.
  • The same window-and-local-envelope idea can be paired with any quantitative mixing bound for these PDMPs to convert continuous-time rates into oracle complexity.
  • Finite-time expected bounce and flip counts are controlled from the cold start via Dynkin identities on simple observables, without assuming stationarity.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If coordinate-wise Lipschitz constants are much smaller than the global L, the Zigzag envelope and the d^{1/4} factor could improve further; the paper flags this but does not pursue it.
  • The same local-envelope accounting might transfer to other event-driven PDMPs (boomerang, coordinate sampler) once matching hypocoercive rates exist.
  • Because the guarantees are only in expectation, a high-probability version would need concentration of the proposal count around its mean—an extension the authors note was found independently for BPS.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper introduces windowed thinning, an exact Poisson-thinning scheme for the bouncy particle sampler (BPS) and the coordinate Zigzag process on m-strongly convex, L-smooth targets. Trajectories are partitioned into deterministic windows; a single gradient evaluation at each window start supplies a local Lipschitz envelope for the event rate. Combined with Lu–Wang χ²-contraction rates (Theorems 1–2) and new finite-horizon bounds on expected bounce/flip counts from an explicit Gaussian cold start (Lemmas 8, 10), the construction yields end-to-end expected query complexities: O(κ^{1/2} d (d log κ + log 1/ε)) full-gradient queries for BPS and O(κ d^{1/4} (d log κ + log 1/ε)) full-gradient equivalents for Zigzag (Theorems 3–4). Algorithms 1–2 are proved exact (Propositions 9, 11), and window lengths are chosen by balancing anchor cost against rejection cost.

Significance. The work supplies the first cold-start, expected-query guarantees for exact BPS and Zigzag simulation under standard strong-convexity/smoothness assumptions. The technical contribution is the combination of local envelopes with Dynkin-based control of integrated squared event rates from a nonstationary Gaussian start, avoiding stationarity or warm-start hypotheses. Relative to prior Zigzag analysis (Lu–Wang), the local envelope and direct expectation bounds improve the condition-number and dimension dependence in the expected-complexity metric, while the BPS bound is new. The comparison with MALA/FORS (Table 1) is appropriately cautious about dimension. The proofs are self-contained once the external mixing rates are granted, and the algorithmic constructions are fully explicit.

minor comments (5)
  1. [Remark 5 / Introduction] Remark 5 and the abstract state only expected complexity; a brief forward pointer in the introduction that high-probability analogues are left open (and that Lu–Wang obtained high-probability warm-start bounds under extra assumptions) would set expectations more clearly for readers coming from the high-probability literature.
  2. [§3.2 / Algorithm 2] In Algorithm 2 the anchor step queries the full gradient G_k = ∇U(X_{t_k}), which is correctly charged as d coordinate-partial queries in Proposition 11, but a one-line remark in §3.2 that the algorithm may alternatively query only the coordinates needed for the envelope weights would avoid any ambiguity about oracle model.
  3. [Table 1] Table 1 caption and the Õ notation suppress logs in d, κ, ε^{-1}; the main theorems retain the explicit (d log κ + log 1/ε) factor. Aligning the table entries with the theorem statements (or adding a footnote that Õ hides those factors) would prevent a casual misreading of the dimension dependence.
  4. [Theorems 3–4] The universal constants K_BPS, K_ZZ appear in the mixing horizons (12), (14) but are never numerically bounded. A short remark that the final O(·) absorbs them (and that they depend only on the hypocoercivity framework) would be helpful.
  5. [§4.2 / §1] Typographical: in the display after (25), the term d√L is written “d p L” in one place in the source; ensure the compiled PDF consistently uses √L. Also “i.e.,from” missing space in §1.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: end-to-end query bounds combine independent continuous-time mixing inputs with a new, self-contained thinning and event-count analysis.

full rationale

The paper’s claimed complexities (Theorems 3–4) are assembled from three pieces: (i) Lu–Wang χ² contraction rates (Theorems 1–2) used only as black-box continuous-time mixing horizons, (ii) new local envelopes (10)–(11) justified by L-smoothness, and (iii) new Dynkin-based expected bounce/flip bounds (Lemmas 8, 10) plus rejection accounting that determine window lengths by balancing anchor vs. proposal cost. The Lu–Wang citations are prior published hypocoercivity results whose assumptions do not include windowed-query counts; they supply T, not the query-per-unit-time analysis. Window lengths τ=(Ld)^{-1/2} and τ=L^{-1/2}d^{-1/4} are chosen inside the proofs from moment bounds, not fitted to data. Cold-start χ² and moment estimates (9), (20) follow from the Hessian bounds and Gaussian initialization by direct calculation. Nothing in the derivation defines the target complexity in terms of itself, renames a fitted quantity as a prediction, or imports a uniqueness theorem that forces the claim. Mild author overlap with the mixing citations is ordinary reuse of prior work and is not circular under the stated criteria.

Assumptions & free parameters 0 free parameters · 6 assumptions · 1 invented entities

The end-to-end claim rests on standard strong-convexity/smoothness oracle assumptions, an explicit Gaussian cold start, Poisson thinning exactness, and quantitative χ² mixing theorems imported from Lu–Wang with prescribed refreshment rates. No parameters are fit to data. The only ‘new entity’ is the algorithmic construction (windowed local envelopes), which is fully specified and falsifiable by re-implementation.

assumptions (6)
  • domain assumption U is C², m-strongly convex and L-smooth: m I ⪯ ∇²U(x) ⪯ L I on R^d (display (1)).
    Stated at the outset; used for envelopes, r(x) bounds, Hessian control in Dynkin arguments, and cold-start density comparison.
  • domain assumption Oracle access to ∇U or coordinate partials ∂_i U, and knowledge of m, L, and minimizer x⋆.
    Query model in the introduction; complexity counts these oracle calls.
  • standard math Lu–Wang BPS χ² contraction (Theorem 1) at γ_BPS=√(d m) with universal K_BPS≥1.
    Imported continuous-time mixing input that sets bT_BPS_ε in Theorem 3.
  • standard math Lu–Wang Zigzag χ² contraction (Theorem 2) at γ_ZZ=√L with universal K_ZZ≥1.
    Imported mixing input that sets bT_ZZ_ε in Theorem 4.
  • domain assumption Initialization ρ₀=N(x⋆,L^{-1}I_d)⊗N(0,I_d) satisfies χ²(ρ₀∥ρ∞)≤κ^{d/2}−1 (eqs. 8–9).
    Explicit cold start; log of this χ² produces the d log κ term in both complexities.
  • standard math Classical Poisson thinning: proposals from a dominating envelope, accepted with rate/envelope, yield the exact inhomogeneous process.
    Used for exactness of Algorithms 1–2 (Props. 9 and 11).
invented entities (1)
  • Windowed thinning (local gradient-anchored envelopes on deterministic windows) independent evidence
    purpose: Provide a tractable dominating event-rate envelope that balances anchor queries against rejected proposals for exact BPS/Zigzag simulation.
    Core algorithmic contribution; fully constructive from L-smoothness and cumulative path length D_s. Not a physical entity; independent_evidence is algorithmic reimplementation.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Windowed thinning and query complexity for the bouncy particle and Zigzag samplers." pith.science (2026). https://pith.science/paper/P7BMEENO

@misc{pith2026260728413,
  author       = {Pith},
  title        = {Pith review of: Windowed thinning and query complexity for the bouncy particle and Zigzag samplers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/P7BMEENO}},
  note         = {Machine review of arXiv:2607.28413}
}
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 $\varepsilon$, the expected query counts are $O(\kappa^{1/2}d\,(d\log\kappa+\log\frac1\varepsilon))$ gradient queries for the bouncy particle sampler and $O(\kappa d^{1/4}(d\log\kappa+\log\frac1\varepsilon))$ full-gradient equivalents for Zigzag, where $d$ coordinate-partial queries count as one equivalent.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. A Profile-Separation Framework for Quantitative Convergence of No-U-Turn Samplers

    math.ST 2026-08 conditional novelty 7.0 of 10

    Under a new profile-separation condition, multinomial and biased-progressive NUTS mix in O~(1 + a*^2 kappa^2(1+gamma)^{4/3}) and O~(1 + a*^4 kappa^3(1+gamma)^2) transitions.

Reference graph

Works this paper leans on

35 extracted references · 5 linked inside Pith · cited by 1 Pith paper

  1. [1]

    Sanket Agrawal, Joris Bierkens, Kengo Kamatani, and Gareth O. Roberts. Transient regime of piecewise deterministic Monte Carlo algorithms, 2025. arXiv:2509.16062

    arXiv 2025

  2. [2]

    Altschuler and Sinho Chewi

    Jason M. Altschuler and Sinho Chewi. Faster high-accuracy log-concave sampling via algorithmic warm starts. Journal of the ACM , 71(3):24:1--24:55, 2024

    2024

  3. [3]

    Altschuler, Sinho Chewi, and Matthew S

    Jason M. Altschuler, Sinho Chewi, and Matthew S. Zhang. Shifted composition IV : Toward ballistic acceleration for log-concave sampling. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing , pages 1739--1750. ACM, 2026

    2026

  4. [4]

    Hypocoercivity of piecewise deterministic Markov process-- Monte Carlo

    Christophe Andrieu, Alain Durmus, Nikolas N \"u sken, and Julien Roussel. Hypocoercivity of piecewise deterministic Markov process-- Monte Carlo . The Annals of Applied Probability , 31(5):2478--2517, 2021

    2021

  5. [5]

    Automated techniques for efficient sampling of piecewise-deterministic Markov processes, 2024

    Charly Andral and Kengo Kamatani. Automated techniques for efficient sampling of piecewise-deterministic Markov processes, 2024. arXiv:2408.03682

    arXiv 2024

  6. [6]

    Vollmer, and Arnaud Doucet

    Alexandre Bouchard-C \^o t \'e , Sebastian J. Vollmer, and Arnaud Doucet. The bouncy particle sampler: A nonreversible rejection-free Markov chain Monte Carlo method. Journal of the American Statistical Association , 113(522):855--867, 2018

    2018

  7. [7]

    The Zig-Zag process and super-efficient sampling for Bayesian analysis of big data

    Joris Bierkens, Paul Fearnhead, and Gareth Roberts. The Zig-Zag process and super-efficient sampling for Bayesian analysis of big data. The Annals of Statistics , 47(3):1288--1320, 2019

    2019

  8. [8]

    The boomerang sampler

    Joris Bierkens, Sebastiano Grazzi, Kengo Kamatani, and Gareth Roberts. The boomerang sampler. In Proceedings of the 37th International Conference on Machine Learning , volume 119 of Proceedings of Machine Learning Research , pages 908--918, 2020

    2020

Show all 35 references
  1. [9]

    Joris Bierkens, Kengo Kamatani, and Gareth O. Roberts. High-dimensional scaling limits of piecewise deterministic sampling algorithms. The Annals of Applied Probability , 32(5):3361--3407, 2022

    2022

  2. [10]

    Joris Bierkens, Kengo Kamatani, and Gareth O. Roberts. Scaling of piecewise deterministic Monte Carlo for anisotropic targets. Bernoulli , 31(3):2323--2350, 2025

    2025

  3. [11]

    Joris Bierkens and Gareth O. Roberts. A piecewise deterministic scaling limit of lifted Metropolis--Hastings in the Curie--Weiss model. The Annals of Applied Probability , 27(2):846--882, 2017

    2017

  4. [12]

    Concentration inequalities and UQ bounds for hypocoercive MCMC samplers

    Jeremiah Birrell and Luc Rey-Bellet. Concentration inequalities and UQ bounds for hypocoercive MCMC samplers. Quarterly of Applied Mathematics , 2025. Electronically published November 14, 2025

    2025

  5. [13]

    Roberts, and Pierre-Andr \'e Zitt

    Joris Bierkens, Gareth O. Roberts, and Pierre-Andr \'e Zitt. Ergodicity of the zigzag process. The Annals of Applied Probability , 29(4):2266--2301, 2019

    2019

  6. [14]

    High-accuracy sampling for diffusion models and log-concave distributions, 2026

    Fan Chen, Sinho Chewi, Constantinos Daskalakis, and Alexander Rakhlin. High-accuracy sampling for diffusion models and log-concave distributions, 2026. arXiv:2602.01338

    2026 arXiv

  7. [15]

    Fan Chen, Sinho Chewi, Alexander Rakhlin, and Matthew S. Zhang. Private communication. 2026

    2026

  8. [16]

    Log-concave sampling

    Sinho Chewi. Log-concave sampling. https://chewisinho.github.io/main.pdf, 2026. Book draft, accessed on Jul 30, 2026

    2026

  9. [17]

    On explicit L^2 -convergence rate estimate for underdamped Langevin dynamics

    Yu Cao, Jianfeng Lu, and Lihan Wang. On explicit L^2 -convergence rate estimate for underdamped Langevin dynamics. Archive for Rational Mechanics and Analysis , 247(5):90, 2023

    2023

  10. [18]

    Alice Corbella, Simon E. F. Spencer, and Gareth O. Roberts. Automatic Zig-Zag sampling in practice. Statistics and Computing , 32:107, 2022

    2022

  11. [19]

    Exponential ergodicity of the bouncy particle sampler

    George Deligiannidis, Alexandre Bouchard-C \^o t \'e , and Arnaud Doucet. Exponential ergodicity of the bouncy particle sampler. The Annals of Statistics , 47(3):1268--1287, 2019

    2019

  12. [20]

    Wainwright, and Bin Yu

    Raaz Dwivedi, Yuansi Chen, Martin J. Wainwright, and Bin Yu. Log-concave sampling: Metropolis--Hastings algorithms are fast. Journal of Machine Learning Research , 20(183):1--42, 2019

    2019

  13. [21]

    Geometric ergodicity of the bouncy particle sampler

    Alain Durmus, Arnaud Guillin, and Pierre Monmarch \'e . Geometric ergodicity of the bouncy particle sampler. The Annals of Applied Probability , 30(5):2069--2098, 2020

  14. [22]

    Non-reversible lifts of reversible diffusion processes and relaxation times

    Andreas Eberle and Francis L \"o rler. Non-reversible lifts of reversible diffusion processes and relaxation times. Probability Theory and Related Fields , 194(1--2):173--203, 2026

    2026

  15. [23]

    Paul Fearnhead, Joris Bierkens, Murray Pollock, and Gareth O. Roberts. Piecewise deterministic Markov processes for continuous-time Monte Carlo . Statistical Science , 33(3):386--412, 2018

    2018

  16. [24]

    Space-time log- Sobolev inequality and hypocoercive hypercontractivity for underdamped Langevin dynamics, 2026

    Bowen Li and Jianfeng Lu. Space-time log- Sobolev inequality and hypocoercive hypercontractivity for underdamped Langevin dynamics, 2026. arXiv:2605.25083

    2026 arXiv

  17. [25]

    P. A. W. Lewis and G. S. Shedler. Simulation of nonhomogeneous Poisson processes by thinning. Naval Research Logistics Quarterly , 26(3):403--413, 1979

    1979

  18. [26]

    A sharp hypocoercive entropy decay estimate for underdamped Langevin dynamics, 2026

    Jianfeng Lu. A sharp hypocoercive entropy decay estimate for underdamped Langevin dynamics, 2026. arXiv:2605.01933

    2026 arXiv

  19. [27]

    Complexity of Zigzag sampling algorithm for strongly log-concave distributions

    Jianfeng Lu and Lihan Wang. Complexity of Zigzag sampling algorithm for strongly log-concave distributions. Statistics and Computing , 32:48, 2022

    2022

  20. [28]

    On explicit L^2 -convergence rate estimate for piecewise deterministic Markov processes in MCMC algorithms

    Jianfeng Lu and Lihan Wang. On explicit L^2 -convergence rate estimate for piecewise deterministic Markov processes in MCMC algorithms. The Annals of Applied Probability , 32(2):1333--1361, 2022

    2022

  21. [29]

    Forward event-chain Monte Carlo : Fast sampling by randomness control in irreversible Markov chains

    Manon Michel, Alain Durmus, and St \'e phane S \'e n \'e cal. Forward event-chain Monte Carlo : Fast sampling by randomness control in irreversible Markov chains. Journal of Computational and Graphical Statistics , 29(4):689--702, 2020

    2020

  22. [30]

    On the entropic convergence for piecewise deterministic samplers: Speedup and obstruction, 2026

    Pierre Monmarch \'e and Lihan Wang. On the entropic convergence for piecewise deterministic samplers: Speedup and obstruction, 2026. arXiv:2606.26086

    2026 arXiv

  23. [31]

    On Lewis' simulation method for point processes

    Yosihiko Ogata. On Lewis' simulation method for point processes. IEEE Transactions on Information Theory , 27(1):23--31, 1981

    1981

  24. [32]

    E. A. J. F. Peters and G. de With. Rejection-free Monte Carlo sampling for general potentials. Physical Review E , 85(2):026703, 2012

    2012

  25. [33]

    Concave-convex PDMP -based sampling

    Matthew Sutton and Paul Fearnhead. Concave-convex PDMP -based sampling. Journal of Computational and Graphical Statistics , 32(4):1425--1435, 2023

    2023

  26. [34]

    Changye Wu and Christian P. Robert. Coordinate sampler: A non-reversible Gibbs -like MCMC sampler. Statistics and Computing , 30(3):721--730, 2020

    2020

  27. [35]

    Minimax mixing time of the Metropolis-Adjusted Langevin Algorithm for log-concave sampling

    Keru Wu, Scott Schmidler, and Yuansi Chen. Minimax mixing time of the Metropolis-Adjusted Langevin Algorithm for log-concave sampling. Journal of Machine Learning Research , 23(270):1--63, 2022

    2022

Pith tools

Reviewed July 31, 2026 · model on record in the stance chip above.