{"id":"bff3cd42-55d9-44ac-bcdc-d2807e70f9c5","arxiv_id":"2501.06634","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":7,"one_line_summary":"Preconditioned conjugate gradient, especially with a randomized Nyström eigenvalue decomposition preconditioner, solves the Stein equation linear systems used for MCMC post-processing in far fewer iterations than plain conjugate gradient.","lead":"This paper tests preconditioning tricks and iterative solvers for the large linear systems that arise when using Stein equations to improve Monte Carlo estimates. On a logistic regression benchmark, a randomized Nyström eigenvalue decomposition preconditioner cut the number of solver iterations by 10 to 20 times.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Randomized Nyström EVD setup cost is understated by a factor N, so the paper's 'fast' claim rests on iteration counts that omit preconditioner construction time and the unreported power-iteration count q.","rationale":"The reader's verdict is CONDITIONAL, and I agree with that overall disposition; the paper is a clear, reproducible empirical study with correct theoretical re-derivations and credible iteration-count evidence. However, the most load-bearing weakness is sharper than the reader's stated concern about generalization across posteriors. Section 3.3.6 contains an internal complexity inconsistency: for a dense kernel matrix, the randomized Nyström EVD construction is dominated by O(N^2 n) matvecs, not O(N n). This directly affects the central practical claim that the recommended preconditioner yields 'fast approximate solutions': the paper explicitly omits timings and does not report q, so the reader cannot tell whether preconditioner construction cancels the 10–20× iteration reduction. The reader did flag the absence of timings and the unreported q, so there is partial agreement, but the concrete mechanism—an understated asymptotic setup cost—was not identified. The concern is addressable: report q, report wall-clock or setup timings, and correct the complexity statement. Since these are fixable limitations rather than invalidation of the empirical findings, the conditional verdict stands unchanged.","tokens_in":25975,"tokens_out":4930,"duration_ms":51853,"concrete_test":"Time the randomized Nyström EVD setup from Section 3.3.6 alone on the Section 4.3 configuration (N=20,000, n=200, reported ln ℓ=1), with q=0 and q=1, and compare against the wall-clock time of 100 iterations of the PCG loop using the same N and ActKp. Also report the q value used in Figures 1–4. If setup exceeds the PCG solve time for the gains reported, the headline claim must be revised to account for construction cost or restricted to settings with many right-hand sides.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3.3.6 claims the randomized Nyström EVD preconditioner costs O((q+1)Nn + n^3) flops. This appears internally inconsistent: forming Y = (Kp Kp^T)^q Kp Ω requires O(N^2 n) work per power iteration for a dense N×N Stein kernel matrix, since each matvec with Kp is O(N^2). Even q=0 requires O(N^2 n) to form KpΩ, plus another O(N^2 n) for B1 = KpQ. Thus the setup cost is O((q+1)N^2 n + n^3), not O((q+1)Nn + n^3). With the paper's own choice n = O(N^{1/2}) to keep PCG iterations at O(N^2), the setup cost is O(N^{2.5}) (or worse with q>0), exceeding one PCG iteration by a factor n. The reported gains are exclusively iteration-count reductions; no wall-clock or setup timings are provided, and the number q of power iterations is not reported in the experimental details (Section D.2.5 only specifies n=50). Consequently, the central recommendation that randomized Nyström EVD delivers 'fast approximate solutions' is not established: for the single large-N experiment in Section 4.3, preconditioner construction may dominate the entire CG solve time. This is a correctness risk in the complexity accounting, not merely a disagreement about empirical generality.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the numerical solution of the canonical Stein equation for post-processing MCMC output, focusing on the linear system Kp w = 1. It derives the closed-form estimator cN, proposes preconditioned conjugate gradient solvers with several preconditioning strategies (Jacobi, block Jacobi, Nyström, Nyström with diagonal sampling, FITC, randomized Nyström, and randomized Nyström EVD), and compares them on a logistic regression posterior in terms of CG iteration counts. The central empirical claim is that randomized Nyström EVD preconditioning performs best, with reported gains of 2–3 on the log scale corresponding to 10–20 times reduction in iteration counts in favourable settings, and that the method scales to N = 20,000.","tokens_in":26290,"tokens_out":8683,"duration_ms":73608,"significance":"If the claims are correct, the paper would provide a practical recipe for scaling Stein-equation-based estimators to realistic MCMC sample sizes, which is an active area of computational statistics. The paper's strengths include a self-contained proof of Proposition 1, an explicit worst-case error bound (16) that allows monitoring without knowing the integrand, a reproducible open-source implementation, and a systematic empirical comparison with ablations over kernel choice and dimension. However, the central 'fast' claim is currently undermined by a complexity-accounting error and the absence of wall-clock timings, so the transfer of the empirical iteration-count ranking to actual computational cost is not established.","major_comments":[{"comment":"The stated cost O((q+1)N n + n^3) for forming Y = (KpKp^T)^q Kp Ω is incorrect for a dense N×N Stein kernel matrix. Each application of Kp or Kp^T to an N×n matrix costs O(N^2 n) flops, so the range-finding stage costs O((2q+1)N^2 n) operations (or O(N^2 n) for q=0), not O(N n) per matvec. With the paper's own choice n = O(N^{1/2}) in Section 4.1, the setup cost is O(N^{2.5}) for q=0 and worse for q>0, which exceeds one PCG iteration by the factor n. Since the paper's performance metric in Section 4.1 counts only iterations and explicitly does not report timings, the advertised speedups for randomized Nyström EVD do not account for preconditioner construction; the claim of 'fast approximate solutions' is therefore not established.","section":"Section 3.3.6"},{"comment":"The displayed formula for M^{-1} is mathematically inconsistent. The matrix KpΩ(Ω^T KpΩ + ηI)^{-1}(KpΩ)^T is of rank at most n < N and is not invertible, yet its inverse is taken in the first line of (20); the second line is the correct Woodbury expression for the inverse of ηI + KpΩ(Ω^T KpΩ)^{-1}(KpΩ)^T. The text conflates the low-rank approximation with the preconditioner. This needs correction so that the preconditioner's definition is unambiguous and reproducible.","section":"Section 3.3.5, Eq. (20)"},{"comment":"The only large-N experiment (N = 20,000) is a single run with no replicates, no timings, and no uncertainty quantification. Given that this is the sole evidence for scalability to realistic MCMC output, and given the setup-cost issue raised above, the conclusion that randomized Nyström EVD is beneficial at scale is not supported. Reporting wall-clock time (or at least adding the preconditioner setup cost to the reported iteration counts) and multiple seeds would be necessary to substantiate the scalability claim.","section":"Section 4.3 and Figure 4"}],"minor_comments":[{"comment":"The sentence 'these do not not enjoy comparable software support' contains a duplicated 'not' and should read 'these do not enjoy comparable software support'.","section":"Section 1"},{"comment":"The sentence 'The time complexity of calculating M^{-1} is O(n^3 + n^2N)' should clarify that this is the cost of building the preconditioner, not of applying it in each CG iteration.","section":"Section 3.3.2"},{"comment":"The power-iteration count q is not reported in the experimental details; Appendix D.2.5 gives only n = 50. Please report q (or state that q = 0 was used) so that the setup cost is reproducible.","section":"Section 3.3.6 and Appendix D.2.5"},{"comment":"The performance metric uses min{10^4, mPCG} in the denominator, which makes the comparison sensitive to the 10^4 iteration cap. The paper states that negative gains are under-reported, but it would be helpful to also report how often this cap was reached for each preconditioner.","section":"Section 4.1"},{"comment":"The panel labels ('Matérn Kernel (ν=5/2, d=4)', 'Matérn Kernel (ν=5/2, d=10)', 'Gaussian Kernel (d=4)') are listed in the caption in a different order than they appear in the figure; please align the descriptions with the actual panel layout.","section":"Figure 2 caption"}],"recommendation":"major_revision","confidential_remarks":"The complexity-accounting error in Section 3.3.6 is the main obstacle to accepting the paper's central claim. The error appears fixable by correcting the flop count, clarifying the randomized Nyström preconditioner definition in Eq. (20), and adding wall-clock timings or setup-cost-adjusted comparisons. The theoretical parts (Proposition 1, the error bound in (16)) and the code release are solid, so rejection seems too harsh; major revision is appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take for your file. The paper does one genuinely useful thing: it runs a careful, replicated comparison of six preconditioners for the linear system Kpw = 1 that arises in kernel Stein post-processing of MCMC, on a logistic regression posterior with several kernels and dimensions. Fifty replicates with standard errors, ablation studies, and available code make this a solid empirical contribution within the subfield. That part is worth a look.\n\nThe theory is a re-derivation: Proposition 1 (closed form of cN) and the worst-case error bound in (16) are known control-functional results, proved here cleanly but not new. That is fine if labelled as background.\n\nThe soft spot is the complexity accounting for the randomized Nyström preconditioners, and it is a real one. Section 3.3.6 states the randomized Nyström EVD setup costs O((q+1)Nn + n^3) flops. That cannot be right for a dense N x N kernel matrix. Forming Y = (KpKp^T)^q KpΩ costs O((q+1)N^2 n) flops, because each multiplication of Kp with an N x n matrix is O(N^2 n); B1 = KpQ adds another O(N^2 n). With the paper's own choice n = O(N^{1/2}), the setup alone is O(N^{2.5}), roughly n times the cost of a single PCG iteration. The same error appears in Section 3.3.5 for the random projection variant. Since all reported gains are iteration counts—no wall-clock or setup timings—the claim that randomized Nyström EVD delivers 'fast approximate solutions' is not established. For the N=20,000 experiment in Section 4.3, the preconditioner construction may cost more than the CG solve it is supposed to accelerate. This is the paper's central recommendation, so the issue is significant.\n\nThe other limitations are real but addressable: the main experiments use a single logistic regression model, the one large-N run has no error bars, and the integrands in Appendix E.3 are outside the RKHS required by (16). The authors acknowledge these honestly.\n\nThe empirical design itself is careful: fixed dataset, 50 replicates, standard errors, kernel and dimension ablations. The derivations that are given are correct. This paper is for researchers working on scalable kernel Stein methods and control functionals. It deserves a serious referee, but with a clear request: correct the complexity claims and report setup timings alongside iteration counts. As written, the headline result should not be taken at face value.","headline":"Solid empirical benchmark of preconditioners for Stein systems, but the complexity claim for randomized Nyström EVD is off by a factor of N and the 'fast' recommendation needs correction.","tokens_in":26869,"tokens_out":6049,"would_cite":false,"duration_ms":51058,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Preconditioned conjugate gradients with a randomized Nyström eigenvalue decomposition solve the Stein-equation linear system up to 10–20 times faster than plain CG on ill-conditioned problems, making Stein-equation post-processing of MCMC…","keywords":["Stein equation","MCMC post-processing","preconditioned conjugate gradient","randomized Nyström","kernel quadrature","control variates","collocation","Bayesian computation"],"falsifier":"Run the same preconditioner comparison on a heavy-tailed or multimodal posterior in dimension $d \\geq 20$ using the paper's gain metric; if randomized Nyström EVD shows zero or negative gain on several such targets while plain CG reaches the same $\\sigma(w_m)$ tolerance, the paper's central recommendation fails to generalize. A second check is to rerun the $N=20{,}000$ experiment with multiple independent chains and measure wall-clock time, since a single unseeded run cannot distinguish a robust speedup from a favourable draw.","tokens_in":25773,"feed_emoji":"⚡","tokens_out":9981,"duration_ms":67165,"temperature":0.7,"pith_summary":"Bayesian inference via MCMC is reliable but slow when integrands are smooth, and post-processing the sample path by solving a Stein equation promises to exploit that smoothness. The price is a dense linear system $K_p w = \\mathbf{1}$ that becomes prohibitively expensive and ill-conditioned as the number $N$ of MCMC samples grows. This paper argues that iterative preconditioned conjugate gradient methods make the system tractable: they need only matrix-vector products, $O(N^2)$ time per iteration, and $O(N)$ storage, with an explicit computable stopping criterion. In the paper's empirical comparison of six preconditioning strategies on logistic regression posteriors, the randomized Nyström eigenvalue decomposition preconditioner performed best in every setting, cutting iteration counts by 10–20 times on ill-conditioned problems. If this ranking holds beyond the test bed, Stein-equation post-processing becomes practical for MCMC outputs of tens of thousands of samples.","feed_headline":"Preconditioning slices Stein-equation MCMC solve effort 10–20x","feed_subtitle":"Randomized Nyström EVD preconditioning cuts iterations 10–20x versus plain CG on ill-conditioned systems.","key_machinery":"The central object is the Stein reproducing kernel matrix $K_p$ defined in (11), built from a base kernel and the score $\\nabla\\log p$; it encodes the posterior and determines the collocation estimator $c_N = f^\\top K_p^{-1}\\mathbf{1}/\\mathbf{1}^\\top K_p^{-1}\\mathbf{1}$ as the solution of $K_p w = \\mathbf{1}$. The method for making that solve fast is preconditioned conjugate gradient: a symmetric preconditioner $M = EE^\\top$ with $M^{-1}$ available in $O(n^3 + n^2N)$ time is applied at each iteration. The winning variant, randomized Nyström EVD, builds $M$ from a two-stage randomized eigendecomposition of $K_p$ (range finding with power iterations followed by the Nyström trick), storing only the low-rank factors $U$ and $\\Lambda$. Convergence is monitored through the computable worst-case error $\\sigma(w_m) = (w_m^\\top K_p w_m)^{1/2}/\\mathbf{1}^\\top w_m$, which lets the solver stop within a user-specified tolerance of the exact solution without ever forming $K_p^{-1}$.","core_discovery":"The collocation solution of the canonical Stein equation produces the estimate $c_N = f^\\top K_p^{-1}\\mathbf{1}/\\mathbf{1}^\\top K_p^{-1}\\mathbf{1}$, so the entire computational burden is the linear system $K_p w = \\mathbf{1}$ for the Stein kernel matrix $K_p$. The paper's central claim is that this system should be solved iteratively with a preconditioner, and that among Jacobi, block Jacobi, Nyström with uniform or diagonal sampling, FITC, randomized Nyström, and randomized Nyström EVD, the randomized Nyström EVD is the winner: it 'performed best over all problem settings considered' and achieves gains of 2–3, corresponding to 10–20 times fewer iterations in favourable settings. The paper further reports that the ranking is not strongly affected by the dimension ($d=4$ vs $d=10$) or by the kernel (inverse multi-quadric, Matérn $\\nu=5/2,7/2$, Gaussian), and that preconditioned solvers reach low integration error for specific posterior predictives in far fewer iterations than plain CG or averaging MCMC output.","pith_inferences":["The empirical support is a single logistic regression test bed; a natural next experiment is a systematic comparison on heavy-tailed or multimodal posteriors in higher dimensions, where the paper's own discussion concedes cumulative evidence is needed.","The paper's large-$N$ demonstration ($N = 20{,}000$) is a single run without error bars or timings; replicating it with several MCMC chains and wall-clock measurements would clarify whether the advertised speedup is robust.","Combining randomized Nyström EVD preconditioning with warm-starting or subspace recycling across a family of related systems — which the paper suggests in its outlook — could further multiply the savings when tuning kernel length scales by cross-validation.","The integration-error experiments use integrands outside the RKHS $H(k_p)$ on which the bound (16) rests; a testable extension is to verify whether the preconditioned solver still preserves the worst-case error ranking for RKHS integrands, where the theory applies."],"forward_implications":["Randomized Nyström EVD becomes the recommended default preconditioner for the canonical Stein-equation system $K_p w = \\mathbf{1}$, particularly at large length scales where the system is most ill-conditioned.","Stein-equation post-processing moves from $O(N^3)$ direct solves to iterative solves with $O(N^2)$ per-iteration cost and $O(N)$ storage, making it feasible for MCMC outputs of $10^4$–$10^5$ samples.","The computable stopping criterion $\\sigma(w_m)$ enables users to trade iterations against a certified worst-case integration error, without needing a ground-truth solution.","The same preconditioning machinery transfers to other linear systems involving $K_p$, such as kernel-based cubature and Stein importance sampling."],"supporting_citations":[{"why":"Supplies the variational formulation and the Stein reproducing kernel that reduce solving the Stein equation to the linear system $K_p w = \\mathbf{1}$.","marker":"[42]"},{"why":"Establishes the Riemann–Stein kernel collocation framework and existence conditions on which the solution relies.","marker":"[3]"},{"why":"Introduces randomized Nyström preconditioning, the family to which the paper's best-performing preconditioner belongs.","marker":"[24]"},{"why":"Provides the two-stage randomized eigendecomposition (range finding plus Nyström trick) used to build the randomized Nyström EVD preconditioner.","marker":"[27]"},{"why":"Advocates Jacobi preconditioning for radial-basis collocation, the baseline that fails for large length scales in the paper's comparison.","marker":"[21]"},{"why":"Supplies the Nyström preconditioning analysis for kernel machines against which the Stein-equation results are contrasted.","marker":"[1]"},{"why":"Introduces diagonal sampling for Nyström approximation, one of the fixed-sampling variants compared here.","marker":"[18]"},{"why":"Introduces the FITC approximation that serves as one of the preconditioner baselines.","marker":"[45]"},{"why":"Exemplifies large-scale kernel preconditioning that motivates the memory-efficient iterative approach.","marker":"[46]"}],"fun_headline_variants":["Randomized Nyström EVD best for fast Stein-equation solves","Nyström preconditioning cuts Stein solver iterations up to 10–20x","Fast approximate Stein solutions via Nyström preconditioning","Stein-equation MCMC post-processing sped up by preconditioned CG","Random Nyström EVD: top preconditioner for Stein linear systems"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"That the ranking of preconditioners and the 10–20 times iteration savings observed on a logistic regression test bed transfer to other posteriors, higher dimensions, and other MCMC samplers.","fun_headline_variants_meta":{"raw":{"variants":["Randomized Nyström EVD best for fast Stein-equation solves","Nyström preconditioning cuts Stein solver iterations up to 10–20x","Fast approximate Stein solutions via Nyström preconditioning","Stein-equation MCMC post-processing sped up by preconditioned CG","Random Nyström EVD: top preconditioner for Stein linear systems"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000615,"raw_usage":{"total_tokens":2829,"prompt_tokens":889,"completion_tokens":1940,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":505,"completion_tokens_details":{"reasoning_tokens":1842}},"tokens_in":505,"tokens_out":1940,"duration_ms":81904,"temperature":1.0,"reasoning_tokens":1842,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T20:55:39.688983+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the same preconditioner comparison on a heavy-tailed or multimodal posterior in dimension $d \\geq 20$ using the paper's gain metric; if randomized Nyström EVD shows zero or negative gain on several such targets while plain CG reaches the same $\\sigma(w_m)$ tolerance, the paper's central recommendation fails to generalize. A second check is to rerun the $N=20{,}000$ experiment with multiple independent chains and measure wall-clock time, since a single unseeded run cannot distinguish a robust speedup from a favourable draw.","supporting_citations":[{"cited_title":"Journal of the Royal Statistical Society Series B: Statistical Methodology 79(3), 695–718 (2017)","cited_arxiv_id":null,"evidence_quote":"Supplies the variational formulation and the Stein reproducing kernel that reduce solving the Stein equation to the linear system $K_p w = \\mathbf{1}$."},{"cited_title":"Bernoulli 28(4), 2181–2208 (2022)","cited_arxiv_id":null,"evidence_quote":"Establishes the Riemann–Stein kernel collocation framework and existence conditions on which the solution relies."},{"cited_title":"and Udell, Madeleine: Randomized Nystr¨ om Preconditioning","cited_arxiv_id":null,"evidence_quote":"Introduces randomized Nyström preconditioning, the family to which the paper's best-performing preconditioner belongs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the two-stage randomized eigendecomposition (range finding plus Nyström trick) used to build the randomized Nyström EVD preconditioner."},{"cited_title":"Advances in Computational Mathematics 11(2), 139–159 (1999)","cited_arxiv_id":null,"evidence_quote":"Advocates Jacobi preconditioning for radial-basis collocation, the baseline that fails for large length scales in the paper's comparison."},{"cited_title":"In: International Conference on Artificial Intelligence and Statistics, pp","cited_arxiv_id":null,"evidence_quote":"Supplies the Nyström preconditioning analysis for kernel machines against which the Stein-equation results are contrasted."},{"cited_title":"Journal of Machine Learning Research 6, 2153–2175 (2005)","cited_arxiv_id":null,"evidence_quote":"Introduces diagonal sampling for Nyström approximation, one of the fixed-sampling variants compared here."},{"cited_title":"The Journal of Machine Learning Research 6, 1939– 1959 (2005)","cited_arxiv_id":null,"evidence_quote":"Introduces the FITC approximation that serves as one of the preconditioner baselines."},{"cited_title":"In: Advances in Neural Information Processing Systems (2017)","cited_arxiv_id":null,"evidence_quote":"Exemplifies large-scale kernel preconditioning that motivates the memory-efficient iterative approach."}],"review_version":1}