{"id":"c799eded-4847-4f45-9ecf-44077191d933","arxiv_id":"2411.14983","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For large datasets, the Zig-Zag sampler with control variates draws effectively independent posterior samples at O(1) cost per sample in stationarity, while vanilla sub-sampling and canonical Zig-Zag cost O(n).","lead":"Bayesian sampling algorithms that subsample data can get stuck mixing slowly. This paper proves that the Zig-Zag sampler with control variates avoids the slowdown, sampling independently at fixed cost per draw once a good reference point is found.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 4.12 is vacuous as stated: it starts ZZ-CV at the target posterior, so the KR bound holds trivially and cannot support the O(n^{-1/2}) mixing-time claim.","rationale":"The reader's CONDITIONAL verdict is reasonable, but the weakest assumption is not primarily the reference-point distance. The more immediate defect is that Corollary 4.12, the stated basis for the headline scaling, is vacuous as written: with U^n_0 drawn from the exact posterior Π^(n)_♯ξ, the chain is stationary and the KR distance is identically zero, so T=0 works. No non-trivial mixing time or independence can be inferred. The proof cites Roberts-Rosenthal Theorem 1 with a 'slight modification' but does not verify any of its conditions for the PDMP limit, nor does it reconcile the initial-distribution notation. This does not invalidate the transient fluid limits or the weak convergence theorems, but it severs the logical link from those theorems to Table 1's O(1) total effort for ZZ-CV. I therefore keep the CONDITIONAL verdict: the gap is concrete and fixable, but the central claim is currently unproven. Secondary issues (reference-point rate conditions and computational-bound tightness) remain, but the corollary's vacuity is the load-bearing one.","tokens_in":46395,"tokens_out":17982,"duration_ms":181104,"concrete_test":"Re-derive Corollary 4.12 using a non-stationary initial condition such as ξ=0 (the natural entry to the stationary phase, cf. Theorem 4.1), and check the two conditions needed for Theorem 1 of [44]: (i) the limiting Zig-Zag with rates (4.6) is exponentially ergodic with an explicit rate; (ii) the weak convergence in Theorem 4.6 is uniform enough to transfer that rate. If the only literal reading of the corollary is the vacuous one (start at the target), the O(n^{-1/2}) mixing-time claim should be withdrawn or properly restated and proved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Corollary 4.12, cited in Section 4.3 as the basis for the O(n^{-1/2}) time-to-independent-sample claim, is stated with initial condition U^n_0 ∼ Π^(n)_♯ξ. Because the Zig-Zag process is Π^(n)-invariant, starting at the target gives L(ξ^n_{n^{-1/2}t}) = Π^(n)_♯ξ for all t, so the KR-distance bound is trivially true with T=0. A vacuous statement cannot yield the non-trivial mixing-time conclusion used in Table 1 and the abstract. The proof ('same as Corollary 4.5 ... with a slight modification of Theorem 1 of [44]') does not specify a non-stationary starting distribution, and does not verify that the limiting Zig-Zag process with rates (4.6) meets the hypotheses of Roberts-Rosenthal Theorem 1 (e.g., exponential ergodicity in the required metric), nor that the weak convergence of Theorem 4.6 transfers to the needed uniform-in-n bound. Thus the paper's central complexity conclusion is unsupported as written, independently of reference-point quality or thinning-bound tightness.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the large-sample (n → ∞) behavior of the Zig-Zag sampler and its sub-sampling variants, ZZ-SS and ZZ-CV, in parametric Bayesian inference with fixed dimension. In the transient phase, the authors prove a fluid limit: Zig-Zag trajectories converge to the solution of the ODE x'(t) = b(x) with drift (3.3) given by the negative expected score normalized by the local switching rate. In the stationary phase, they derive three different limits under the n^{1/2} rescaling: ZZ-SS converges to an Ornstein-Uhlenbeck diffusion (4.4), while slowed-down ZZ-CV and canonical Zig-Zag converge to Zig-Zag processes with rates (4.6) and the canonical rate, respectively. From these limits, the paper claims complexity bounds per essentially independent sample: O(n) for canonical Zig-Zag and ZZ-SS, and O(1) for ZZ-CV (Table 1). The proofs are detailed and self-contained in the appendix, and the limiting objects are internally consistent: for example, the OU drift in Theorem 4.2 preserves the asymptotic posterior N(0, I(x0)^{-1}), and the limiting Zig-Zag rate in Remark 4.7 has the correct skew-symmetric structure for that Gaussian target.","tokens_in":46549,"tokens_out":5342,"duration_ms":54323,"significance":"If the complexity conclusions are valid, the paper is a substantial contribution: it is the first scaling-limit analysis of PDMP samplers as a function of dataset size, it covers misspecified models, and it provides explicit and checkable limiting equations (3.3), (4.4), and (4.6) that explain both the transient optimization-like behavior and the stationary mixing differences between sub-sampling schemes. The strength of the paper is its careful martingale and averaging arguments, which appear to support the qualitative distinction between ZZ-SS (diffusive, O(n) effort) and ZZ-CV (Zig-Zag limit, potentially O(1) effort). However, the headline complexity claim, and specifically the O(n^{-1/2}) time-to-independent-sample for ZZ-CV, is currently supported by Corollary 4.12, and that corollary is vacuous as stated. Because this is the central claim advertised in the abstract and Table 1, the paper requires substantial revision before the complexity contribution can be accepted.","major_comments":[{"comment":"Corollary 4.12 is vacuous as stated and cannot support the O(n^{-1/2}) mixing-time claim. The corollary takes U^n_0 ∼ Π^(n)_♯ξ, i.e. the initial law is exactly the target in the rescaled coordinate. Since each Zig-Zag process is Π^(n)-invariant, L(ξ^n_{n^{-1/2}t}) = Π^(n)_♯ξ for all t ≥ 0, so the KR-distance bound holds trivially with T = 0. A trivial bound with T = 0 cannot imply that the algorithm needs O(n^{-1/2}) time to obtain an essentially independent sample from a non-stationary initial distribution. The same objection applies to Corollary 4.5, which also starts at Π^(n)_♯ξ. The complexity rows in Table 1 and the claims in Section 4.3 therefore rest on a statement that proves nothing about mixing from a general starting point. The authors need either to prove the mixing-time claim from a non-stationary initial distribution or to explicitly restate and limit the contribution as a stationary-phase cost-per-sample result rather than a time-to-independent-sample result.","section":"§4.3, Corollary 4.12 (and Corollary 4.5)"},{"comment":"Even if the initial distribution were non-stationary, the proof sketch ('same as Corollary 4.5 ... with a slight modification of Theorem 1 of [44]') does not supply the missing hypotheses. Theorem 1 of Roberts and Rosenthal (2016) gives complexity bounds for diffusion limits under conditions that include exponential ergodicity of the limiting process in the relevant metric and a transfer of that ergodicity to the prelimit processes uniformly in n. The paper does not verify exponential ergodicity of the limiting Zig-Zag process with rates (4.6) in the KR metric, nor does it establish the uniform-in-n bound linking Theorem 4.6 to a finite-time KR error. Weak convergence alone does not provide a rate of convergence, and the uniform-in-n statement in the corollary is precisely what is needed for the complexity calculation. This is a load-bearing gap, not a cosmetic one.","section":"§4.2, Proof of Corollary 4.12"},{"comment":"The O(1) complexity conclusion is conditional on an assumption about the reference point that is not guaranteed by the algorithm. Theorem 4.6 requires ξ^*_n → ξ^* in probability, which in the notation of Section 4.2 means ∥X^*_n − x̂_n∥ = O_p(n^{-1/2}) with a nontrivial limit. If the reference point is only O_p(1) away, Remark 4.10 shows that the ZZ-CV switching rates are O(n) and the process reverts to the diffusive ZZ-SS regime with O(n) total cost. The paper does acknowledge a one-off O(n) initialization cost to find a good reference point, but the theorem itself does not provide a constructive or guaranteed mechanism for selecting T_n satisfying the required rate. The authors should state this condition explicitly as a hypothesis of the complexity theorem and discuss whether it is verifiable in practice, rather than treating it as an automatic consequence of the ZZ-CV construction.","section":"§4.2, Remark 4.10 and Theorem 4.6"}],"minor_comments":[{"comment":"Equation (3.3) is defined on R^d \\ H(ω), but the final clause says 'x ∈ H(ω)'; this should read 'x ∉ H(ω)'.","section":"§3, equation (3.3)"},{"comment":"The proof of Corollary 4.5 says 'combining this and Theorem 4.6', but the relevant result is Theorem 4.2; Corollary 4.12 similarly refers to 'Theorem 4.2 or 4.11' where it should refer to Theorem 4.6 or 4.11.","section":"§4.1, Corollary 4.5 proof"},{"comment":"The notation for the subsample collection is inconsistent: S(n,m) and S(m,n) are both used, and at one point S(m,n) is written where S(n,m) appears intended; please standardize.","section":"§2.5 and §4.1"},{"comment":"Minor spelling issue: 'Kullback-Liebler' should be 'Kullback-Leibler'.","section":"Abstract and Section 1"}],"recommendation":"major_revision","confidential_remarks":"The vacuous statement of Corollary 4.12 is the main obstacle: it is the sole cited support for the O(1) complexity claim in Table 1 and the abstract. The rest of the scaling-limit analysis is substantial and well executed, so I would not reject the paper outright, but the authors need to either prove a genuine mixing-time result from a non-stationary starting distribution or explicitly reframe the contribution as a stationarity-regime cost analysis. I would also ask the editor to ensure the reference-point condition for ZZ-CV is treated as a formal hypothesis in all complexity statements, since Remark 4.10 shows that the O(1) claim collapses when the reference point is farther than n^{-1/2} from the estimator."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is the first scaling analysis of PDMPs in the data-size regime, and the transient fluid limits plus the stationary weak convergence results are real contributions. But the paper's headline complexity claims are currently supported by corollaries that start the process at its target distribution, which makes the KR bounds trivially true. That is a load-bearing gap, not a stylistic complaint.\n\nWhat's genuinely new: Theorem 3.3 (fluid limit to an ODE drifting along KL), Theorem 4.2 (OU limit for ZZ-SS), Theorem 4.6 (Zig-Zag limit for ZZ-CV), and the explicit rate formulas. The proof machinery is careful, and the asymptotics are internally consistent. The reference-point caveat is honestly flagged in Remark 4.10 and Section 4.3: ZZ-CV's O(1) cost requires ||X*_n - x̂_n|| = O_p(n^{-1/2}) with an O(n) one-time initialization. That is a fair qualification.\n\nThe soft spot is exactly the jump from weak convergence to mixing-time bounds. Corollaries 4.5 and 4.12 state bounds on the KR distance between the process law and the posterior, but they take the initial law to be the posterior. Since the Zig-Zag process is invariant, the distance is zero for all t. The proofs are deferred to 'a slight modification of Theorem 1 of [44]' without specifying a non-stationary start or verifying the limiting process's ergodicity in the required metric. So the O(n^{-1/2}) time-to-independent-sample entries in Table 1 and the abstract's O(1) speed-up are not actually derived. This is the central quantitative conclusion of the paper, so it matters.\n\nThe good news is the gap is plausibly patchable: start from a non-stationary initial distribution (e.g., a deterministic point in the ξ-rescaled domain), use the exponential ergodicity of the OU / limiting Zig-Zag processes, and transfer that bound to finite n via the weak convergence plus some uniformity. That is real work, but not a change of the paper's architecture.\n\nWho this is for: researchers working on PDMP theory or subsampling MCMC will want to read the transient and stationary limit theorems even if the complexity claims need another pass. I would not desk-reject this; a serious referee should see it. But I would not yet take the O(1) claim as established.","headline":"First data-size scaling analysis for PDMPs with solid limit theorems, but the headline O(1) complexity claim rests on vacuous corollaries that start at the target distribution.","tokens_in":47201,"tokens_out":3292,"would_cite":false,"duration_ms":31674,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60F17","60J25","62F15","62E20","65C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"With control variates, a sub-sampled Zig-Zag sampler can draw independent posterior samples at O(1) cost as the data size grows.","keywords":["piecewise deterministic Markov processes","Zig-Zag sampler","sub-sampling","control variates","fluid limits","large-sample asymptotics","Bayesian computation","computational complexity"],"falsifier":"Run ZZ-CV in the stationary phase with a reference point whose error is $O_p(n^{-\\alpha})$ for $\\alpha < 1/2$ (for instance, an estimator based on $n^{1/3}$ observations) and measure the total CPU time per effectively independent sample; if the time grows with $n$ rather than remaining bounded, the $O(1)$ claim fails. A more direct check is to count proposed switches per independent sample and confirm that they grow like $n^{1-2\\alpha}$ instead of staying $O(1)$ in this regime.","tokens_in":46119,"feed_emoji":"🎲","tokens_out":8642,"duration_ms":69407,"temperature":0.7,"pith_summary":"The paper asks what happens to the Zig-Zag sampler, a Markov chain Monte Carlo method that moves at constant speed and randomly flips direction, when the number of data points $n$ grows. In the stationary phase it proves that the control-variate sub-sampling version (ZZ-CV) needs only $O(n^{-1/2})$ time and $O(1)$ proposed velocity switches per essentially independent sample, with each switch costing $O(1)$, so the total work per sample is $O(1)$. That is an $O(n)$ speed-up over canonical Zig-Zag and over traditional MCMC, both of which cost $O(n)$. In the transient phase the paper shows all Zig-Zag variants are approximated by a deterministic flow that drifts toward decreasing KL divergence, with sub-sampling damping the drift. These are the first scaling limits for a piecewise deterministic sampler as a function of data size rather than dimension.","feed_headline":"Zig-Zag with control variates samples at O(1) cost as data grows","feed_subtitle":"Large-sample analysis gives O(n) speed-up, if the control reference point stays near the posterior mode.","key_machinery":"The key mechanism is the imbalance between switching rates in opposite velocity directions, which produces drift, together with the magnitude of the total switching rate. In the transient phase the drift $b_i(x) = -E[S_i(x;Y)]/(\\lambda_i(x,-\\mathbf{1})+\\lambda_i(x,\\mathbf{1}))$ defines a fluid-limit ODE, with the denominator acting as the damping factor from sub-sampling. In the stationary phase the rescaled coordinate $\\xi = n^{1/2}(x - \\hat{x}_n)$ separates the regimes: ZZ-SS has switching rates of order $n$, leading to a diffusion limit, while ZZ-CV and canonical Zig-Zag have effective rates of order $n^{1/2}$ after time rescaling, leading to Zig-Zag limits. The complexity table then multiplies time-to-mixing, switching rate, and per-switch cost to obtain the $O(1)$ versus $O(n)$ totals.","core_discovery":"In the stationary phase, after rescaling coordinates by the posterior contraction rate, the paper proves weak convergence of the Zig-Zag process in three regimes. Vanilla sub-sampling (ZZ-SS) converges to an Ornstein-Uhlenbeck diffusion with a damping matrix determined by the subsample estimator, and it needs $O(1)$ time but $O(n)$ switching events, so its total cost is $O(n)$. Canonical Zig-Zag and ZZ-CV, slowed down by a factor $n^{1/2}$, converge to Zig-Zag processes invariant for the limiting Gaussian posterior. Since ZZ-CV estimates the gradient from random batches of fixed size, each proposed switch costs $O(1)$, and the process reaches an essentially independent sample in $O(n^{-1/2})$ time with $O(1)$ proposed switches, giving $O(1)$ total effort. This $O(1)$ claim holds only if the reference point used by the control variates satisfies $\\|X^*_n - \\hat{x}_n\\| = O_p(n^{-1/2})$; otherwise the switching rates grow to $O(n)$ and ZZ-CV degrades to the slow diffusive regime.","pith_inferences":["The same scaling logic suggests that updating the reference point adaptively as the sampler runs could preserve the $O(1)$ complexity, provided the update error stays $O_p(n^{-1/2})$; the paper advocates this but does not analyze it.","The fluid-limit result is not special to Bayesian settings: the paper notes that the ODE approximation holds whenever switching rates grow as $n^{\\beta}$ with position speed $n^{\\alpha}$, so the transient analysis should transfer to other piecewise deterministic samplers such as the bouncy particle sampler.","For heavy-tailed models, Corollary 5.1 implies a mixed scheme that provably beats both pure schemes in the transient phase; testing this on real heavy-tailed posteriors is a natural next step.","Because the analysis fixes dimension $d$, an open question is how the $O(1)$ complexity interacts with dimension; if the per-switch cost or the reference-point error degrades with $d$, the practical speed-up may be smaller than the headline $O(n)$ factor."],"forward_implications":["ZZ-CV with a good reference point obtains an essentially independent sample in $O(1)$ total work as $n \\to \\infty$, matching the 'superefficiency' claim of the original Zig-Zag paper.","Canonical Zig-Zag and ZZ-SS both have $O(n)$ total cost per independent sample; the gain from control variates is realized only when the reference point is already within $O_p(n^{-1/2})$ of the posterior mode.","In the transient phase, canonical Zig-Zag converges to the minimizer at optimal speed $\\pm 1$, while ZZ-SS slows down near the mode and ZZ-CV can be arbitrarily slow in heavy-tailed models.","A mixed scheme that uses ZZ-SS in the tails and ZZ-CV near the mode converges faster than either pure scheme in heavy-tailed examples.","Under the Bernstein-von Mises theorem, the stationary limits are invariant for the asymptotic Gaussian posterior, so the scaling analysis transfers directly to the standard large-sample Bayesian setting."],"supporting_citations":[{"why":"introduces the Zig-Zag sampler with sub-sampling and control variates and supplies the algorithm whose complexity this paper analyzes.","marker":"[14]"},{"why":"provides limit theorems for the one-dimensional Zig-Zag with excess switches, the diffusive behaviour underlying the ZZ-SS limit.","marker":"[12]"},{"why":"gives the Bernstein-von Mises theorem under misspecification, which justifies the asymptotic Gaussian posterior used in the stationary phase.","marker":"[32]"},{"why":"supplies the law of large numbers for U-processes used to derive the limiting switching rates uniformly on compact sets.","marker":"[4]"},{"why":"provides the diffusion-limit complexity bound and the KR-distance argument used in Corollaries 4.5 and 4.12.","marker":"[44]"},{"why":"is the text whose generator-convergence and tightness criteria are used in the weak convergence proofs.","marker":"[30]"},{"why":"supplies the averaging-over-fast-variables coupling technique used to prove the fluid-limit ODE in the transient phase.","marker":"[37]"},{"why":"defines piecewise deterministic Markov processes and their generator, forming the process class under study.","marker":"[27]"},{"why":"gives the computational bounds for Bayesian logistic regression used in the Section 4.3 cost discussion.","marker":"[13]"}],"fun_headline_variants":["Zig-Zag control variates sample at O(1) cost","O(1) cost Bayesian sampling via Zig-Zag control variates","Zig-Zag with control variates: O(n) speed-up at O(1) cost","Control variates make Zig-Zag O(1) for large-sample inference","Zig-Zag CV: O(1) sampling for large data"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The $O(1)$ cost of ZZ-CV rests on the assumption that the reference point used for control variates is within $O_p(n^{-1/2})$ of the posterior mode; if the reference point is farther away, the switching rates grow to $O(n)$ and the advantage disappears.","fun_headline_variants_meta":{"raw":{"variants":["Zig-Zag control variates sample at O(1) cost","O(1) cost Bayesian sampling via Zig-Zag control variates","Zig-Zag with control variates: O(n) speed-up at O(1) cost","Control variates make Zig-Zag O(1) for large-sample inference","Zig-Zag CV: O(1) sampling for large data"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001485,"raw_usage":{"total_tokens":6021,"prompt_tokens":1056,"completion_tokens":4965,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":672,"completion_tokens_details":{"reasoning_tokens":4862}},"tokens_in":672,"tokens_out":4965,"duration_ms":32120,"temperature":1.0,"reasoning_tokens":4862,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:40:10.405571+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run ZZ-CV in the stationary phase with a reference point whose error is $O_p(n^{-\\alpha})$ for $\\alpha < 1/2$ (for instance, an estimator based on $n^{1/3}$ observations) and measure the total CPU time per effectively independent sample; if the time grows with $n$ rather than remaining bounded, the $O(1)$ claim fails. A more direct check is to count proposed switches per independent sample and confirm that they grow like $n^{1-2\\alpha}$ instead of staying $O(1)$ in this regime.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"introduces the Zig-Zag sampler with sub-sampling and control variates and supplies the algorithm whose complexity this paper analyzes."},{"cited_title":"and Duncan, A","cited_arxiv_id":null,"evidence_quote":"provides limit theorems for the one-dimensional Zig-Zag with excess switches, the diffusive behaviour underlying the ZZ-SS limit."},{"cited_title":"and van der Vaart, A","cited_arxiv_id":null,"evidence_quote":"gives the Bernstein-von Mises theorem under misspecification, which justifies the asymptotic Gaussian posterior used in the stationary phase."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the law of large numbers for U-processes used to derive the limiting switching rates uniformly on compact sets."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the diffusion-limit complexity bound and the KR-distance argument used in Corollaries 4.5 and 4.12."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"is the text whose generator-convergence and tightness criteria are used in the weak convergence proofs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the averaging-over-fast-variables coupling technique used to prove the fluid-limit ODE in the transient phase."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"defines piecewise deterministic Markov processes and their generator, forming the process class under study."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gives the computational bounds for Bayesian logistic regression used in the Section 4.3 cost discussion."}],"review_version":1}