{"id":"8e1b2642-2edf-4f7e-ac42-8bb8c999d2f6","arxiv_id":"2602.10714","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For strongly convex targets, a ULA sampler that learns a covariance or Fisher preconditioner can have lower total FLOPS cost than unpreconditioned ULA once a large number of samples is requested.","lead":"Markov chain samplers often run faster if the problem is first rescaled (preconditioned), but the rescaling itself has to be learned from the chain. This paper works out, in terms of computation time, when that learning step is worth it and applies the analysis to a standard gradient-based sampler.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Preconditioned sampling bound omits the Lipschitz constant of the inverse preconditioning map; Theorem 5's displayed FLOPS are not derived.","rationale":"The reader's CONDITIONAL verdict correctly identifies that Theorem 5's FLOPS do not follow from the proof as written, citing missing d and 1/m factors. My stress-test finds a more fundamental instance of the same class of gap: the proof applies the preconditioned contraction analysis to the transformed target π̃ with the same accuracy ε, but the final output is obtained by the linear map M^{-1/2}, whose Lipschitz constant amplifies the W2 error. Proposition 7, which the paper itself proves, requires rescaling ε by ‖M^{-1/2}‖; the proof never does so. This is an internal inconsistency, not a disagreement with consensus. The missing factor can be huge (e.g., λ_max(Σ_π) for the covariance preconditioner) even when κ_{Σ^{-1}_π} is small, so the theorem as stated could fail to predict the true amortization threshold. The framework is potentially salvageable by either tracking ε' explicitly or imposing an additional bound on ‖M^{-1/2}‖, but the current manuscript does not contain such an argument. Hence I agree with the CONDITIONAL verdict: the qualitative amortization idea is plausible, but the central quantitative claims require correction. I do not see a need to escalate to REJECT because the gap is identifiable and likely fixable, and there is independent value in the AIID framework and learning-phase bounds.","tokens_in":31122,"tokens_out":20716,"duration_ms":189767,"concrete_test":"Take π = N(0, diag(10^6, 1, ..., 1)), ε = 0.01. With the exact covariance preconditioner, the transformed target is N(0,I). Running ULA on N(0,I) to accuracy ε' = ε/‖Σ_π^{1/2}‖ = 10^{-5} requires γ^{-1} ∝ (ε')^{-2} = 10^{10}, while Theorem 5 Eq. (13)'s sampling term uses ε^{-2} = 10^4, a missing factor ~10^6. Compute the corrected FLOPS (per-iteration cost times iteration count) and compare to Eq. (13); if the corrected term is larger by ‖Σ_π^{1/2}‖², the displayed bound is not implied. Repeat for the Fisher preconditioner with λ_min(F̂) small.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Algorithm 2 collects {X̃_t} from the transformed target π̃ = M^{1/2}_♯π and outputs X_t = M^{-1/2}X̃_t. Proposition 7 implies that a √Nε-AIID sample from π̃ pushes forward to a √N‖M^{-1/2}‖ε-AIID sample from π. The proof of Theorem 5 Parts 2–3 (Sections B.5.2, B.6.2) verifies the ε-conditions for the transformed target using the same ε as in the theorem statement, and never rescales ε' = ε/‖M^{-1/2}‖ when applying the ULA step-size rule h = ε²/(100 d κ_M²). Consequently the FLOPS computed for the sampling stage are those needed to make the transformed chain output √Nε-AIID from π̃, not the stated √Nε-AIID from π. Correcting for this adds a factor ‖M^{-1/2}‖² = λ_max(Σ̂_π) in the covariance case and λ_min(F̂)^{-1} in the Fisher case, which is absent from Eq. (13)/(15). Since these quantities can be arbitrarily large even when κ_{Σ^{-1}_π} (or κ_F) is small, the theorem's conditions do not preclude the claimed bound from being far too optimistic. In addition, the step-size choice introduces a d factor and a 1/m_M factor from γ^{-1} that are also missing from the displayed sampling terms. Together, the central quantitative comparison is not established as stated.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a non-asymptotic framework for comparing the total computational cost of Markov chain Monte Carlo algorithms that learn and apply a linear preconditioner with those that do not. It introduces a √Nε-approximate IID (AIID) condition based on Wasserstein-2 distance to the N-fold product target and proves a generic iteration-complexity bound (Theorem 3) for thinned samplers whose kernel satisfies a (Γ,γ,b)-W2 contraction. It then provides high-probability learning complexities for covariance-based and Fisher-information-based preconditioners (Theorem 4), and applies the results to ULA to obtain total FLOPS bounds (Theorem 5), with an extension to underdamped Langevin in the supplement. The central affirmative claim is that, for targets that are linearly preconditionable and when many samples are required, the one-time cost of learning the preconditioner is amortized and preconditioned ULA can have lower total complexity than unpreconditioned ULA.","tokens_in":31495,"tokens_out":10962,"duration_ms":106801,"significance":"The framework and the AIID condition are genuinely useful: they connect mixing-time bounds with effective-sample-size intuition, and the modular structure (generic contraction bound, learning bound, sampler-specific application) is elegant. The paper contains detailed proofs of several intermediate propositions and makes the constants in the learning bounds fairly explicit. If Theorem 5 were established as stated, it would fill a notable gap in the non-asymptotic theory of adaptive MCMC. However, the central quantitative comparison is not currently derived from the proof: the sampling stage of Algorithm 2 ignores the Lipschitz constant of the inverse preconditioning map, and the displayed FLOPS omit factors that follow from the step-size choice. These issues directly affect the claimed comparison, so the affirmative answer to the motivating question is not yet supported.","major_comments":[{"comment":"The proof of Theorem 5, parts 2 and 3, does not convert the AIID guarantee from the transformed target back to π. Algorithm 2 outputs X_t = M^{-1/2} X̃_t, with X̃_t produced from π̃ = M^{1/2}_♯π. By Proposition 7, if {X̃_t} is √N ε'-AIID from π̃, then {M^{-1/2} X̃_t} is only √N ||M^{-1/2}|| ε'-AIID from π. The proofs in B.5.2 and B.6.2 verify the ε-conditions for π̃ using the same ε as in the theorem statement and choose the step size h = ε²/(100 d κ_M²) from that ε; they never apply Proposition 7 with ε' = ε/||M^{-1/2}||. Consequently the computed sampling-stage FLOPS are those needed to obtain a √Nε-AIID sample from π̃, not from π. Correcting this adds a factor ||M^{-1/2}||² — i.e. 1/λ_min(Σ̂π) for the covariance preconditioner and 1/λ_min(F̂) for the Fisher preconditioner — to the sampling term. This factor is not controlled by the theorem's assumptions: for π = N(0, σ² I_d), κ = 1 bu","section":"Sections B.5.2, B.6.2, Eq. (13), Eq. (15), Proposition 7"},{"comment":"The step-size choice made in the proof, h = 100^{-1} d^{-1} κ^{-2} ε², gives γ = mh and hence γ^{-1} = 100 d m^{-1} κ² ε^{-2}. Since the per-iteration cost is (d+G), the iteration bound from Theorem 3 yields an additional factor d in the total FLOPS bound. The displayed unpreconditioned bound in Eq. (11) is Õ(m^{-1}(d+G)κ² N ε^{-2}), with no d. Similarly, the sampling-stage terms in Eq. (13) and Eq. (15) omit the d from γ^{-1} and the m_M^{-1} (equivalently κ_M/L_M) factor in the contraction rate. These factors are polynomial in d and κ, not logarithmic constants, so they cannot be absorbed into Õ without saying so. As written, the displayed FLOPS expressions in Theorem 5 do not follow from the proof.","section":"Section 4.3.1, Section B.4, Eq. (11)"},{"comment":"Theorem 4, part 2, and hence the Fisher-preconditioned FLOPS in Theorem 5, part 3, rely on the bound that F^{-1/2}∇logπ(Z) is sub-Gaussian with proxy sup_x λ_1(F^{-1/2}∇²U(x)F^{-1/2}), imported from Negrea [2022, Theorem 2.2]. This is a self-citation to a thesis and is load-bearing: it is what produces K_Fisher in Eq. (88). The manuscript gives only a one-sentence summary of the result. Please include the precise statement and a proof (or a clearly labelled reference with the theorem reproduced) in the appendix, so this step can be verified independently.","section":"Section B.3.2, Eq. (87)–(88)"}],"minor_comments":[{"comment":"'one its un-preconditioned counterpart' should be 'one of its unpreconditioned counterparts'.","section":"Section 1"},{"comment":"'twice differential' should be 'twice differentiable'.","section":"Section 1"},{"comment":"'See 5 for further discussion' should be 'See Section 5'.","section":"Section 5"},{"comment":"In step 3, the notation K(M^{1/2}_♯π) is confusing because the pushforward is of the target, not of the kernel; a brief explanation of the transformation would help.","section":"Algorithm 2"},{"comment":"C is introduced as an absolute constant but its value changes from line to line; state 'C denotes a universal constant, possibly changing on each use'.","section":"Eq. (21) and elsewhere"}],"recommendation":"major_revision","confidential_remarks":"To the editor: The paper is substantial and the framework is appealing, but the central quantitative comparison currently appears to be off by factors that can be arbitrarily large. I would ask the authors to recompute Theorem 5 with the pushforward rescaling and the d/m_M factors included, and to test the resulting bounds on a simple Gaussian target (e.g., π = N(0, σ²I_d)) to see whether the claimed amortization survives. The self-cited sub-Gaussian bound should also be made checkable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nTwo things to know up front. The √Nε-AIID condition and the two-phase cost decomposition are genuinely useful tools, and the paper is careful in most of its proofs. But the central quantitative claim in Theorem 5 does not follow from the proof: the displayed FLOPS bounds are missing at least three factors — a d, a 1/m_M, and the Lipschitz constant of the inverse preconditioning map.\n\nThe paper's new idea is to measure MCMC output by how close a whole ensemble is to an IID sample in W2 (the AIID condition). That bridges the gap between mixing time and effective sample size, and it behaves well under Lipschitz maps (Prop 7). The two-phase analysis — one-time learning cost plus per-sample cost — is exactly the right way to think about amortizing a preconditioner. The claim that a moderately accurate estimate (Δ=0.5) suffices is a useful insight, and the learning-phase analysis is detailed and mostly sound.\n\nThe problem is Theorem 5. In the unpreconditioned case the step size is h = c d^{-1} κ^{-2} ε^2, so γ = m h and the iteration count carries d/(m ε^2). Eq (11) omits the d. The preconditioned cases inherit this and add 1/m_M from the transformed target; the sampling-stage terms in Eq (13) and (15) omit both. More seriously, when Algorithm 2 runs the chain on the transformed target π̃ and outputs X_t = M^{-1/2} X̃_t, the AIID tolerance must be rescaled by ||M^{-1/2}|| (Prop 7). The proof verifies the ε conditions for the transformed chain using the same ε as the theorem, not ε/||M^{-1/2}||. Correcting this adds λ_max(Σ̂_π) in the covariance case and λ_min(F̂)^{-1} in the Fisher case — factors that can be arbitrarily large under the theorem's stated conditions. So the quantitative FLOPS comparison, which is the paper's headline result, is not derived as stated. The qualitative amortization story may survive a correction, but the actual rates could differ by problem-dependent constants that affect the crossover regime.\n\nSmaller point: the abstract promises a proximal-sampler analysis that does not appear in the body. That is a quick fix.\n\nWho should read this? Anyone working on adaptive MCMC or non-asymptotic sampling theory. The framework is worth engaging with, but the paper needs a major revision before its main theorem can be trusted. I would send it to peer review — the ideas deserve referee time — but the referee should require a corrected Theorem 5 that tracks the transformation of ε and the step-size constants carefully.","headline":"Useful AIID framework, but Theorem 5's FLOPS bounds omit a d, a 1/m_M, and the pushforward rescaling factor — the quantitative comparison as stated is not derived.","tokens_in":31953,"tokens_out":6606,"would_cite":false,"duration_ms":55723,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65C05","60J22"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper shows that a Markov-chain sampler that learns its own linear preconditioner can have lower total computational cost than the same sampler without preconditioning, provided enough samples are drawn and the target is amenable to pr","keywords":["MCMC","preconditioning","adaptive MCMC","non-asymptotic analysis","Wasserstein contraction","unadjusted Langevin algorithm","covariance preconditioner","Fisher preconditioner"],"falsifier":"Run covariance-preconditioned ULA on a family of anisotropic Gaussian targets with known condition number κ, count the actual FLOPS to reach √Nε-AIID for a range of N, and compare with plain ULA; if the measured break-even N diverges from the amortization prediction of Theorem 5, or if preconditioning is never faster on any N for a target with κ_{Σ^{-1}_π}=κ, the central comparison is wrong for that class.","tokens_in":31015,"feed_emoji":"📉","tokens_out":7647,"duration_ms":74749,"temperature":0.7,"pith_summary":"The paper asks whether an MCMC algorithm that learns its own linear preconditioner from the chain can beat its unpreconditioned counterpart in total floating-point cost, including the cost of learning. The answer, for the unadjusted Langevin algorithm on smooth, strongly convex targets, is yes: a preconditioner based on the target covariance or the Fisher matrix reduces the condition number and, once enough samples are needed, the one-time learning cost is amortised. To make this comparison rigorous, the authors introduce a √Nε-approximately IID condition that measures how far a thinned chain's output is from an IID sample in Wasserstein-2 distance, letting them split the total cost into a learning phase and a sampling phase. A central finding is that the preconditioner needs only be estimated to moderate constant accuracy (relative error 1/2) to retain essentially all of its benefit.","feed_headline":"Learned preconditioners beat plain MCMC at large sample sizes","feed_subtitle":"Total-FLOPS analysis: the one-time learning cost is repaid once you need enough samples.","key_machinery":"The engine is the (Γ,γ,b)-W₂ contraction condition (Definition 2): a kernel K satisfies W₂(π, μK^k) ≤ Γe^{-γk}W₂(π,μ)+b, where b≥0 captures bias. This single condition lets the authors derive Theorem 3, which bounds the total number of iterations needed to output √Nε-AIID samples, and Theorem 4, which bounds the cost of estimating Σ_π or F from such an ensemble. Corollary 14 then shows that if the estimate satisfies ‖Σ^{-1/2}_π Σ̂_π Σ^{-1/2}_π - I‖ ≤ Δ, the resulting condition number is at most (1+Δ)/(1-Δ) times the ideal one, so Δ=1/2 suffices. These pieces assemble into the FLOPS totals in Theorem 5.","core_discovery":"The central claim, stated in Theorem 5, is an explicit total-FLOPS comparison for ULA: unpreconditioned ULA needs Õ(m^{-1}(d+G)κ²Nε^{-2}) FLOPS to produce N samples that are √Nε-approximately IID, while covariance-preconditioned ULA needs Õ(δ^{-2}d³(d+G)κ³max{δ^{-1},K³_cov} + (d²+G)κ²_{Σ^{-1}_π}Nε^{-2}) FLOPS with probability 1-δ (similarly for the Fisher preconditioner). The two terms are the cost to learn the preconditioner and the cost to generate the final ensemble; comparing them shows preconditioning wins when N is large enough to make the second term dominate and when the preconditioned condition number κ_{Σ^{-1}_π} is substantially smaller than κ. The authors also prove that learning","pith_inferences":["A practical consequence the authors leave implicit: because Δ=1/2 suffices, a short adaptation run that gives a rough covariance estimate should already deliver most of the sampling speedup; one need not wait for precise adaptation.","The FLOPS comparison suggests preconditioning is most valuable when gradient evaluations are expensive (large G, e.g., inverse problems); for very large d, the added d² per-iteration matrix-vector product may outweigh the condition-number reduction unless κ/κ_M is large. This is a testable boundary worth probing numerically.","The √Nε-AIID condition is a general-purpose objective: it could be applied to other adaptive MCMC parameters (step size, HMC integration time) or to periodic re-adaptation, as the paper itself notes as future work."],"forward_implications":["When the target is linearly preconditionable (κ_{Σ^{-1}_π} or κ_F much smaller than κ) and N is large, preconditioned ULA has lower total FLOPS than unpreconditioned ULA.","Learning the preconditioner costs Õ(d³(d+G)κ³δ^{-2}max{δ^{-1},K³_cov}) FLOPS, independent of N; this is a one-time expense that can be amortised over the output sample size.","A constant-accuracy estimate (Δ=1/2) of the covariance or Fisher matrix suffices; the condition number of the preconditioned chain grows by at most a factor of 3.","The √Nε-AIID framework gives non-asymptotic guarantees for both exact and biased (b>0) kernels, covering ULA and, in the supplement, the unadjusted underdamped Langevin algorithm.","The per-sample FLOPS after preconditioning is (d²+G)κ²_M Nε^{-2}, so the break-even point depends concretely on the dimension d and the gradient cost G."],"fun_headline_variants":["Preconditioners win when you need many MCMC samples","One-time learning cost: preconditioning pays off for large N","Non-asymptotic proof: learned preconditioners dominate at scale","MCMC preconditioning: worth it only beyond a sample-size threshold","Total-FLOPS comparison shows preconditioning wins for big jobs"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is that the target is smooth and strongly convex and that the learned preconditioner lands within a constant relative error (Δ=1/2) of the true covariance or Fisher matrix; if either fails, or if the target is not actually preconditionable (the preconditioned condition number is close to the original), the bounds do not guarantee any benefit over plain sampling.","fun_headline_variants_meta":{"raw":{"variants":["Preconditioners win when you need many MCMC samples","One-time learning cost: preconditioning pays off for large N","Non-asymptotic proof: learned preconditioners dominate at scale","MCMC preconditioning: worth it only beyond a sample-size threshold","Total-FLOPS comparison shows preconditioning wins for big jobs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000177,"raw_usage":{"total_tokens":1156,"prompt_tokens":799,"completion_tokens":357,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":543,"completion_tokens_details":{"reasoning_tokens":285}},"tokens_in":543,"tokens_out":357,"duration_ms":4139,"temperature":1.0,"reasoning_tokens":285,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T01:02:04.767630+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run covariance-preconditioned ULA on a family of anisotropic Gaussian targets with known condition number κ, count the actual FLOPS to reach √Nε-AIID for a range of N, and compare with plain ULA; if the measured break-even N diverges from the amortization prediction of Theorem 5, or if preconditioning is never faster on any N for a target with κ_{Σ^{-1}_π}=κ, the central comparison is wrong for that class.","supporting_citations":[],"review_version":1}