{"id":"ec8e9666-72dd-42e0-a8c6-761ae90bb1a6","arxiv_id":"1908.00633","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A randomized sketching algorithm estimates preconditioner stability in about a constant number of conjugate-gradient iterations and selects among candidate preconditioners with provable approximation guarantees.","lead":"Choosing a good preconditioner for solving linear systems is often a guessing game. This paper shows a randomized sketching trick can quickly estimate how effective each candidate preconditioner would be, and tests it on real solvers.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Load-bearing concern is the unproved stability-to-iteration proxy; a scalar-multiple example shows the two can disagree.","rationale":"The reader's CONDITIONAL verdict is appropriate and I agree with the identified weakest assumption. I read the main estimation argument as sound: Theorem 2.1's deterministic lower bound is a clean adversary argument, and Theorem 2.2's sample-complexity proof (modulo display typos in constants) gives a dimension-independent k with the claimed multiplicative error. The load-bearing weakness is the bridge from stability to conjugate-gradient iteration count. The manuscript itself flags this: Section 3.1.1 reports that for oilpan, increasing k from 10 to 50 moves the selected preconditioner away from the iteration-minimal choice, and Section 4 lists the proxy question as open. I add a sharper analytic counterexample: scalar multiples of A are all ideal CG preconditioners (unit condition number) but have different stabilities, so no theorem can assert that stability minimization equates to iteration minimization in general. This is a scope/caveat problem rather than a soundness failure of the randomized estimator. It strengthens the case for CONDITIONAL: the paper should release code/data, correct the displayed constants, and explicitly qualify that the selection guarantee is for the stability criterion, not for CG iterations.","tokens_in":20208,"tokens_out":21061,"duration_ms":215285,"concrete_test":"Run a controlled SPD test, e.g. A = diag(1,2,3,4) with candidates M_j ∈ {A, 2A, 100A} plus two block-diagonal pinchings: compute exact ||I - M_j^{-1}A||_F and run CG to convergence for each. The three scalar multiples all have κ(M_j^{-1}A)=1 and should converge in one exact-arithmetic iteration, yet their stabilities are 0, √d/2, and ≈√d. If stability and iteration rankings disagree, the proxy premise is falsified. Then, for the paper's own data, compute exact (or k=10^5-accurate) stabilities for the nine oilpan preconditioners of Table 1 and verify whether the exact stability-minimal candidate is the iteration-minimal D100; if it is not, the Section 3.1.1 inference is confirmed and the abstract's forecasting claim should be qualified.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The theorems establish only that Algorithm 2 returns a near-minimizer of ||I - M^{-1}A||_F (Theorem 2.3). The advertised practical conclusion, that this selects a good CG preconditioner, needs the extra premise that stability order predicts iteration count. No theorem proves this; Section 4 lists exactly this as an open problem, and Section 3.1.1's oilpan experiment shows the proxy is imperfect. The premise fails even in the simplest SPD setting: for any SPD A and any α>0, the preconditioner M=αA gives M^{-1}A = α^{-1}I with condition number 1, so exact-arithmetic CG converges in one iteration for every α, while ||I - M^{-1}A||_F = √d |1 - α^{-1}| varies with α. Thus stability ranking can distinguish equivalent preconditioners, and a stability-minimal choice need not be iteration-minimal. Because the abstract's 'forecast' claim and the kernel-regression 'never worse' claim depend on this empirical proxy, the practical selection value is not established by the theorems.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the preconditioner-selection problem: given candidate preconditioners M_j for Ax=b, choose the one that minimizes the number of conjugate-gradient iterations. The core algorithmic contribution is a randomized estimator Stab(A,M,k) of the preconditioner stability ||I-M^{-1}A||_F, obtained by applying the Gaussian trace estimator to the matrix (I-M^{-1}A)^*(I-M^{-1}A). The paper proves a deterministic lower bound (Theorem 2.1), a sample-complexity bound for the estimator (Theorem 2.2), a selection guarantee for choosing a near-minimal-stability candidate among n preconditioners (Theorem 2.3), a tightness result for the leading constant (Theorem 2.4), and an accelerated variant under an anti-concentration condition (Theorem 2.5). The numerical section evaluates stability-based selection on SuiteSparse matrices and on kernel-regression systems, and reports a kernel-regression preconditioning method that never uses more CG iterations than no preconditioner in the tested parameter range.","tokens_in":20436,"tokens_out":25183,"duration_ms":246977,"significance":"If the technical claims are repaired, the paper makes a useful point: a quantity previously considered impractical to compute can be estimated with O(epsilon^-2 log(1/delta)) matrix-vector products, independent of dimension. The deterministic lower bound in Theorem 2.1 is a clean and interesting argument, and the estimator is extremely simple and trivially parallelizable. The experiments are extensive and the kernel-regression results are genuinely promising. However, the practical interpretation of the method as a CG-preconditioner selector depends on the unproved premise that minimizing ||I-M^{-1}A||_F minimizes CG iterations; the paper itself identifies this as an open problem and reports an instance where the proxy is imperfect. The theorem statements also contain several errors that must be fixed before the results can be relied upon.","major_comments":[{"comment":"The selection guarantee in Theorem 2.3 is only a guarantee about the stability functional ||I-M^{-1}_j A||_F, not about the number of CG iterations. The abstract and the experimental discussion, however, present the method as selecting the preconditioner that minimizes iterations. This extra step is not proved: Section 4 explicitly lists the fundamental limits of the stability proxy as an open problem, and Section 3.1.1 reports that for the oilpan matrix, increasing k from 10 to 50 moves the selected preconditioner away from the iteration-minimal one. One can also see the mathematical mismatch in the simplest SPD case: for M=alpha A, M^{-1}A=alpha^{-1}I has condition number 1, so exact-arithmetic CG takes one iteration for every alpha, while ||I-M^{-1}A||_F = sqrt(d)|1-alpha^{-1}| varies with alpha. The practical claims should be reframed as empirical, or a supporting result connecting stability to iteration counts should be supplied.","section":"Sections 3.1.1 and 4; Theorem 2.3"},{"comment":"The statement and proof of Theorem 2.2 have two problems. First, the displayed sufficient condition is k >= 12/(epsilon^2(3-2epsilon)) log(2/delta); for epsilon <= 1/2 this gives at best k >= 6/epsilon^2 log(2/delta), not k >= 6/epsilon^2 log(1/delta) as claimed in the 'In particular' sentence. The stated simplification understates the proven sample size by a log 2 factor. Second, the theorem is stated for all 0<epsilon<1, but the lower-tail argument chooses t = epsilon/(2(1-epsilon)), which exceeds 1/2 when epsilon>1/2; the MGF bound (1-2t)^{-k/2} used in the proof is not valid in that range. Since all later applications use epsilon<=1/2, the main use of the theorem survives, but the theorem as stated is not proved.","section":"Theorem 2.2"},{"comment":"The explicit formula for k in Theorem 2.4 is not correctly derived from the proof. The proof sets k = floor(2/epsilon^2 W(1/(8 pi delta^2))). Using W(x) >= log x - log log x gives k >= floor(4 epsilon^{-2} log(1/(sqrt(8 pi) delta)) - 2 epsilon^{-2} log log(1/(sqrt(8 pi) delta)) - 2 epsilon^{-2} log 2). The theorem omits the final -2 epsilon^{-2} log 2 term. Since the failure probability decreases as k increases, choosing a k larger than the threshold established by the proof is in the wrong direction for a guaranteed lower bound on the failure probability. The statement and its proof need to be reconciled; as written, the claimed tightness result is not established.","section":"Theorem 2.4"}],"minor_comments":[{"comment":"The proof states that Stab(A,M,k) is equal in distribution to (1/k) sum_{i=1}^k q_i^* Lambda q_i; this is true of the squared estimator Stab(A,M,k)^2, not of Stab itself. The surrounding inequalities concern the squared quantity, so the wording should be corrected.","section":"Theorem 2.2 proof"},{"comment":"The letter m appears in the exponents in Equations (2.11)-(2.12) but is never defined; it should be k.","section":"Equations (2.11)-(2.12)"},{"comment":"The simplified bound k >= 11/epsilon^2 log(2n/delta) leading to a (1+epsilon)-factor is asserted without showing the intermediate scalar inequalities. Since the derivation involves choosing an effective accuracy different from epsilon, a sentence or displayed calculation is needed.","section":"Theorem 2.3"},{"comment":"There are several typographical and presentation issues: 'Tyrtyshkinov' is misspelled in Algorithm 2, 'standarad' appears in Section 3.2.1, and Figure 1 relies on color alone to convey positive versus negative values; a grayscale-accessible encoding would improve the paper.","section":"Various"}],"recommendation":"major_revision","confidential_remarks":"The paper has a solid core and the randomized estimator is standard but well deployed; the deterministic lower bound is a nice addition. The main reasons for major revision are the theorem-statement errors and the gap between the stability guarantee and the advertised CG-iteration conclusions. All of these are fixable within the scope of the manuscript, so I do not recommend rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. The paper does one genuinely new thing and does it well: it points out that preconditioner stability can be estimated with a Gaussian trace estimator in O(k) matrix-vector products, and proves a deterministic query lower bound that shows this kind of claim is close to optimal. The lower bound is simple but clean, and the sample-complexity analysis (Theorem 2.2) is a nice repurposing of known results with an improved constant. The experiments, especially the kernel regression ones, are suggestive and honest: they report cases where larger sketch size makes the selection worse, and they explicitly say the stability proxy is not perfect.\n\nThe soft spots are real but not fatal. First, the theorem statements have a few warts. The simplified k bound in Theorem 2.2 does not seem to follow from the displayed bound when epsilon = 1/2, and the formula in Theorem 2.4 has ambiguous logarithms and a floor that complicates the asymptotic story. These are the kinds of things a referee should ask to be cleaned up, not reasons to reject.\n\nSecond, and more importantly, the paper's advertised conclusion—that selecting minimal stability gives a good CG preconditioner—is not proven. The stress-test example is right: for M = alpha A, every alpha gives M^{-1}A proportional to I, so CG converges in one step, while ||I - M^{-1}A||_F varies. So stability can rank equivalent preconditioners. The paper itself acknowledges this in Section 4 and in the oilpan discussion, so it is not hiding the limitation. But the abstract's 'never worse' claim in kernel regression is an empirical observation from single runs with no released code or data, so I'd want to see that reproduced and ideally replaced by a distributional claim or a worst-case bound.\n\nOverall, the core contribution—an efficient, provably accurate estimator for a practically meaningful quantity—holds up. The gap between stability and iteration count is real but clearly documented, and the paper does not overclaim. I'd send this to a serious referee; the math is solid enough to engage with, and the application area is of interest to a broad numerical linear algebra audience. After some revision to fix the theorem statements and provide code/data, it could be accepted.","headline":"A well-executed paper that makes a known trace estimator practical for preconditioner selection; the theory is mostly solid, the proxy from stability to iteration count remains unproven but the paper is honest about it.","tokens_in":20945,"tokens_out":2599,"would_cite":true,"duration_ms":23942,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F08","68W20","68Q17","62G08"],"pacs":[],"model":"deepseek-v4-flash","headline":"Preconditioner stability, long deemed impractical to compute, can be estimated by randomized sketching in a dimension-free number of matrix-vector products.","keywords":["preconditioner selection","preconditioner stability","randomized sketching","trace estimation","conjugate gradients","kernel regression","Frobenius norm","matrix-vector product model"],"falsifier":"Take $A = I - e_1e_1^T$ and $M = I$, the worst case used in Theorem 2.4, and run Algorithm 1 with $k = \\lfloor 4\\epsilon^{-2}\\log(1/\\sqrt{8\\pi}\\delta) - 2\\epsilon^{-2}\\log\\log(1/\\sqrt{8\\pi}\\delta)\\rfloor$ for small $\\epsilon$; if the estimate falls outside $\\sqrt{1\\pm\\epsilon}\\,\\|I - M^{-1}A\\|_F$ with probability less than $\\delta$ over many trials, the claimed tightness bound is violated. Separately, finding a positive-definite matrix and a set of preconditioners whose stability ordering is opposite to their conjugate-gradient iteration ordering would refute the proxy on which the selection method rests.","tokens_in":19991,"feed_emoji":"🎲","tokens_out":10977,"duration_ms":104523,"temperature":0.7,"pith_summary":"This paper argues that preconditioner stability, the quantity $\\|I - M^{-1}A\\|_F$, is not the impractical diagnostic it was thought to be. The authors show that a randomized sketching estimator computes it, to multiplicative accuracy $\\sqrt{1\\pm\\epsilon}$ with failure probability at most $\\delta$, using $k = O(\\epsilon^{-2}\\log(1/\\delta))$ matrix-vector products; the sample count is independent of the matrix dimension $d$. They also prove that no deterministic algorithm can do this with fewer than $d$ queries, so randomness is a necessity rather than a convenience. Because the estimate costs about as much as a constant number of conjugate-gradient iterations, selecting the best of $n$ candidate preconditioners becomes an $n$-fold repetition with a union-bound guarantee, and the method can advise using no preconditioner at all. This matters because automated, reliable preconditioner choice is a bottleneck in iterative solvers, and the paper's kernel-regression experiments show the selection rarely loses to no preconditioning.","feed_headline":"A few random vectors pick the best preconditioner","feed_subtitle":"The stability estimate that seemed impractical now costs about as long as a few conjugate-gradient iterations.","key_machinery":"The load-bearing object is the identity $\\|I - M^{-1}A\\|_F^2 = \\mathbb{E}\\,\\|(I - M^{-1}A)q\\|_2^2$ for a standard Gaussian vector $q$, obtained by writing the squared Frobenius norm as a trace and using $\\mathbb{E}[qq^*] = I$. This turns stability estimation into Monte Carlo trace estimation: Algorithm 1 forms $Q$ with independent scaled Gaussian columns and returns $\\|(I - M^{-1}A)Q\\|_F$. The analysis follows a Markov/Jensen tail bound on the quadratic form $q^*\\Lambda q$, where $\\Lambda$ contains the eigenvalues of $(I - M^{-1}A)^*(I - M^{-1}A)$, yielding the dimension-free sample complexity; a matching lower bound uses a one-dimensional eigenvalue perturbation and the central limit theorem. This identity is what converts matrix-vector access to $M^{-1}$ and $A$ -- exactly the access iterative solvers already provide -- into a certificate of preconditioner quality.","core_discovery":"The paper's central discovery is that the Frobenius-norm stability $\\|I - M^{-1}A\\|_F$, long regarded as impractical to compute, is efficiently estimable and sufficient to drive preconditioner selection. Algorithm 1 draws $k$ independent Gaussian vectors $q_i$, forms the sketch $S = (I - M^{-1}A)Q$, and returns $\\|S\\|_F$; Theorem 2.2 guarantees that with $k \\ge \\frac{12}{\\epsilon^2(3-2\\epsilon)}\\log\\frac{2}{\\delta}$ this estimate lies within $\\sqrt{1\\pm\\epsilon}$ of the true stability with probability at least $1-\\delta$. The authors prove this bound is asymptotically tight, with leading constant $4$ as $\\epsilon\\to 0$, using a central-limit argument that also confirms a known conjecture about Gaussian trace estimators. Algorithm 2 then estimates stability for every candidate and returns the minimum; with $k = O(\\epsilon^{-2}\\log(n/\\delta))$ it returns a preconditioner within $\\sqrt{(1+\\epsilon)/(1-\\epsilon)}$ of the minimal stability, with probability $1-\\delta$. The paper further proves a deterministic lower bound that any exact multiplicative approximation requires at least $d$ matrix-vector queries, and an anti-concentration speedup that decouples the number of candidates from the accuracy cost when there is a clear winner.","pith_inferences":["If stability becomes cheap enough to evaluate repeatedly, one could re-select or re-weight preconditioners online during a single solve; the paper does not explore this adaptive use, but its per-query cost makes it plausible.","The same dimension-free estimator applies to any matrix $B$ given by matrix-vector access, not only $I - M^{-1}A$, which suggests cheap diagnostics for other matrix functions used in numerical linear algebra.","The anti-concentration speedup suggests a practical adaptive protocol: start with a small sketch, prune obviously bad candidates, and spend larger sketch sizes only on the finalists; the paper proves the bound under a distributional condition but does not separately validate this protocol as an algorithm.","Because the estimator parallelizes down to one matrix-vector product per processor, it could serve as a distributed preconditioner-selection primitive for very large systems; the paper notes the trivial parallelization but leaves communication-aware analyses open."],"forward_implications":["A solver can screen all candidates in advance because each stability estimate costs about as much as a constant number of preconditioned conjugate-gradient iterations.","No deterministic algorithm can certify stability with fewer than $d$ matrix-vector products, so the randomized failure probability is unavoidable.","For $n$ candidates, $k = O(\\epsilon^{-2}\\log(n/\\delta))$ matrix-vector products per candidate suffices to return a preconditioner within $\\sqrt{(1+\\epsilon)/(1-\\epsilon)}$ of minimal stability with probability $1-\\delta$.","The method can return the identity as the selected preconditioner, giving a principled recommendation to skip preconditioning when no candidate beats doing nothing; in the paper's kernel-regression tests this never produced more conjugate-gradient iterations than no preconditioner.","When candidate stabilities are well separated, the algorithm can prune bad candidates early and decouple the number of candidates from the accuracy cost, reducing the total work to a sum dominated by the near-ties."],"supporting_citations":[{"why":"Defines preconditioner stability as the empirical forecast used by the paper and documents the folklore that it is impractical to compute.","marker":"[8]"},{"why":"Provides the survey-level impracticality assessment for quantities like the inverse preconditioner norm that the randomized estimator overturns.","marker":"[7]"},{"why":"Supplies the improved trace-estimator sample bound that Theorem 2.2 sharpens and streamlines.","marker":"[25]"},{"why":"States the conjecture on Gaussian trace-estimator asymptotics that the paper confirms with a direct central-limit proof.","marker":"[5]"},{"why":"Gives the optimal query-complexity lower bound showing Algorithm 1 is asymptotically optimal among randomized matrix-vector estimators.","marker":"[33]"},{"why":"Relays the Schatten-2 norm estimator that Algorithm 1 specializes to the matrix-vector access model.","marker":"[34]"},{"why":"Defines the preconditioned conjugate-gradient iteration whose cost is the runtime benchmark for the paper's algorithms.","marker":"[16]"},{"why":"Provides the kernel-regression preconditioners and experimental baseline showing prior preconditioners sometimes lose to no preconditioning.","marker":"[11]"}],"fun_headline_variants":["Random sketching picks the best preconditioner fast","Preconditioner stability estimated by a few random vectors","Sketching turns impractical preconditioner metric into cheap one","Randomized method selects minimal-stability preconditioner in O(n log n)","A handful of random vectors forecast preconditioner quality"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that minimizing $\\|I - M^{-1}A\\|_F$ reliably identifies the preconditioner that minimizes conjugate-gradient iterations; the paper relies on empirical evidence for this proxy, tests it in its experiments, and does not prove it, and its own oilpan result shows that increasing the sketch size can move the selected preconditioner away from the minimal-iteration choice.","fun_headline_variants_meta":{"raw":{"variants":["Random sketching picks the best preconditioner fast","Preconditioner stability estimated by a few random vectors","Sketching turns impractical preconditioner metric into cheap one","Randomized method selects minimal-stability preconditioner in O(n log n)","A handful of random vectors forecast preconditioner quality"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000544,"raw_usage":{"total_tokens":2693,"prompt_tokens":1126,"completion_tokens":1567,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":742,"completion_tokens_details":{"reasoning_tokens":1489}},"tokens_in":742,"tokens_out":1567,"duration_ms":11713,"temperature":1.0,"reasoning_tokens":1489,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:43:46.521156+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take $A = I - e_1e_1^T$ and $M = I$, the worst case used in Theorem 2.4, and run Algorithm 1 with $k = \\lfloor 4\\epsilon^{-2}\\log(1/\\sqrt{8\\pi}\\delta) - 2\\epsilon^{-2}\\log\\log(1/\\sqrt{8\\pi}\\delta)\\rfloor$ for small $\\epsilon$; if the estimate falls outside $\\sqrt{1\\pm\\epsilon}\\,\\|I - M^{-1}A\\|_F$ with probability less than $\\delta$ over many trials, the claimed tightness bound is violated. Separately, finding a positive-definite matrix and a set of preconditioners whose stability ordering is opposite to their conjugate-gradient iteration ordering would refute the proxy on which the selection method rests.","supporting_citations":[{"cited_title":"Benzi, D","cited_arxiv_id":null,"evidence_quote":"Defines preconditioner stability as the empirical forecast used by the paper and documents the folklore that it is impractical to compute."},{"cited_title":"Benzi , Preconditioning techniques for large linear systems: a survey , Journal of computa- tional Physics, 182 (2002), pp","cited_arxiv_id":null,"evidence_quote":"Provides the survey-level impracticality assessment for quantities like the inverse preconditioner norm that the randomized estimator overturns."},{"cited_title":"A vron and S","cited_arxiv_id":null,"evidence_quote":"States the conjecture on Gaussian trace-estimator asymptotics that the paper confirms with a direct central-limit proof."},{"cited_title":"Wimmer, Y","cited_arxiv_id":null,"evidence_quote":"Gives the optimal query-complexity lower bound showing Algorithm 1 is asymptotically optimal among randomized matrix-vector estimators."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Relays the Schatten-2 norm estimator that Algorithm 1 specializes to the matrix-vector access model."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the preconditioned conjugate-gradient iteration whose cost is the runtime benchmark for the paper's algorithms."},{"cited_title":"Cutajar, M","cited_arxiv_id":null,"evidence_quote":"Provides the kernel-regression preconditioners and experimental baseline showing prior preconditioners sometimes lose to no preconditioning."}],"review_version":1}