{"id":"f5d91909-f83c-4083-bff6-716c4dab1e78","arxiv_id":"2607.28413","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Windowed thinning yields exact BPS and Zigzag simulation with cold-start query complexities O(κ^{1/2}d(d log κ + log 1/ε)) and O(κ d^{1/4}(d log κ + log 1/ε)) full-gradient equivalents.","lead":"The paper gives an exact simulation method called windowed thinning for two continuous-time MCMC samplers, with end-to-end gradient-query bounds from a Gaussian cold start. It matters because it turns piecewise-deterministic samplers into algorithms with explicit high-accuracy complexity guarantees under standard log-concave assumptions.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The paper’s central claim is an end-to-end expected-query bound obtained by coupling an exact local thinning scheme with existing hypocoercive mixing rates and new cold-start event-count estimates. The reader correctly isolates the external Lu–Wang rates as the principal external dependency; those rates are cited theorems with explicit refreshment choices, not circular self-citations. Inside the manuscript the novel pieces—windowed envelopes, Dynkin control of ∫E[λ²] from a Gaussian cold start, and the resulting τ-balancing—are elementary and appear correctly executed. Dimension dependence is worse than MALA/FORS and is stated honestly. No hidden boundedness assumption, no unjustified interchange, and no gap between the stated algorithms and the complexity theorems was found. Consequently the ACCEPT verdict stands; the concrete check above is only a routine verification of the most delicate internal identity.","tokens_in":20429,"tokens_out":519,"duration_ms":11381,"concrete_test":"Independently re-derive the BPS identity (25) from generator (3) and the reflection jump of ψ, then insert only the cold-start bounds E|V_t|²=d and (20); confirm that the resulting integrated-λ² bound is still ≤LdT+γ_BPSd/4+√(L)d/2 and that Cauchy–Schwarz plus T≥max{L^{-1/2},γ_BPS/(4L)} recovers B_BPS(T)≤2√(Ld)T. If this holds, the query claim is intact.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's weakest-assumption call (dependence on Lu–Wang χ² rates with fixed refreshments) is real but external and standard; it does not undermine the paper's own contribution. Within the manuscript the load-bearing steps check out: local envelopes (10)–(11) dominate by L-smoothness; Dynkin identities for ψ=⟨x−x⋆,v⟩ (BPS) and q=v·∇U (Zigzag) produce the integrated squared rates after the elementary lower bound r(x)∈[1/L,1/m] and the Hessian bound; cold-start moments (Lemma 6) close the estimates without stationarity; window lengths balance anchors against rejections to give the stated expected query counts. No internal gap appears that would falsify Theorems 3–4 under the cited continuous-time inputs.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","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.","tokens_in":20568,"tokens_out":922,"duration_ms":28039,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"Remark 5 / Introduction"},{"comment":"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.","section":"§3.2 / Algorithm 2"},{"comment":"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.","section":"Table 1"},{"comment":"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.","section":"Theorems 3–4"},{"comment":"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.","section":"§4.2 / §1"}],"recommendation":"accept","confidential_remarks":"The manuscript is technically solid and appropriate for a strong computational-mathematics or applied-probability venue. The dependence on Lu–Wang rates is the only external load-bearing input and is standard. The AI-use paragraph (including the note that ChatGPT Pro independently recovered the BPS bound) is unusually candid; I leave to the editor whether any additional disclosure is required by journal policy. I see no novelty or citation concerns."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The one thing worth knowing: Lu and Luo give the first clean expected-query bounds for exact BPS and Zigzag from an explicit Gaussian cold start, by replacing global envelopes with deterministic windowed local envelopes anchored at a single gradient evaluation. That is the actual novelty; the mixing rates are imported from their earlier Lu–Wang χ² work.\n\nWhat they do well is the finite-horizon bookkeeping. Lemmas 8 and 10 turn bounce/flip counts into time integrals of squared rates via Dynkin on ψ = ⟨x−x⋆, v⟩ and q = v·∇U, then close the estimates with cold-start moments and the elementary bound r(x) ∈ [1/L, 1/m]. Window lengths are chosen by balancing anchors against rejections, not by fitting. Algorithms 1–2 are standard thinning once the envelopes (10)–(11) are written down; exactness and non-explosion are careful but routine. Table 1 is honest: BPS is Õ(κ^{1/2} d²) and Zigzag Õ(κ d^{5/4}) in full-gradient equivalents, worse in d than MALA/FORS.\n\nSoft spots are minor and external. The simulation horizon is set directly from the Lu–Wang rates with fixed refreshments γ_BPS = √(dm), γ_ZZ = √L and the crude χ²(ρ₀∥ρ∞) ≤ κ^{d/2}−1; if those constants are loose the query numbers inflate, but that is not a flaw in the windowed analysis itself. Guarantees are expectation-only, not high-probability, and Zigzag still pays an arithmetic O(d) per proposal that is not folded into the oracle count. None of this breaks Theorems 3–4 under the stated inputs.\n\nThis is for people who care about PDMP complexity and exact continuous-time simulation. It will not change practice for anyone already using MALA or proximal samplers, but it closes a real accounting gap in the PDMP literature. Math and citations look solid; no circularity. I would send it to referees without hesitation.","headline":"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.","tokens_in":21266,"tokens_out":531,"would_cite":true,"duration_ms":8900,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65C05","60J25","65C40","65Y20"],"pacs":[],"model":"grok-4.5","headline":"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/ε).","keywords":["piecewise deterministic Markov process","bouncy particle sampler","Zigzag process","Poisson thinning","query complexity","hypocoercivity","log-concave sampling","windowed thinning"],"falsifier":"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.","tokens_in":21247,"feed_emoji":"🎲","tokens_out":1043,"duration_ms":23980,"temperature":0.7,"pith_summary":"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.","feed_headline":"Exact PDMP sampling with cold-start query bounds","feed_subtitle":"Windowed thinning turns BPS and Zigzag into gradient oracles with explicit κ and d costs from a Gaussian start.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Windowed thinning: exact BPS/Zigzag query bounds from Gaussian start","Cold-start query complexity for windowed BPS and Zigzag samplers","Exact PDMP simulation via windowed thinning with κ,d costs","BPS and Zigzag as gradient oracles: windowed thinning bounds","From Gaussian cold start: explicit query rates for BPS and Zigzag"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Windowed thinning: exact BPS/Zigzag query bounds from Gaussian start","Cold-start query complexity for windowed BPS and Zigzag samplers","Exact PDMP simulation via windowed thinning with κ,d costs","BPS and Zigzag as gradient oracles: windowed thinning bounds","From Gaussian cold start: explicit query rates for BPS and Zigzag"]},"model":"grok-4.5","effort":"low","cost_usd":0.004016,"raw_usage":{"total_tokens":1225,"prompt_tokens":779,"num_sources_used":0,"completion_tokens":95,"cost_in_usd_ticks":40164000,"prompt_tokens_details":{"text_tokens":779,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":351,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":779,"tokens_out":95,"duration_ms":8172,"temperature":1.0,"reasoning_tokens":351,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-31T08:07:49.486119+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"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.","supporting_citations":[],"review_version":1}