{"id":"cc98964b-c550-4bae-9676-5f206cd8cd54","arxiv_id":"2506.22701","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Any matrix-vector query algorithm that estimates tr(W^{-p}) for a d×d Wishart matrix within a constant factor needs Ω(d) queries when p>1/2.","lead":"The paper proves a query lower bound for estimating traces of inverse powers of Wishart matrices, showing that any algorithm needs about d matrix-vector products. It also reviews and extends polynomial approximation bounds that link Block Krylov iterations to trace estimation cost.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5's proof only establishes a contradiction for failure probabilities below δ0(C,p), while the theorem states δ depends only on C; fixed-confidence settings such as δ=1/3 are left unproved.","rationale":"The reader's weakest_assumption exactly identifies the unresolved δ quantifier in Theorem 5, and my reading agrees: the contradiction at the end of Section 4.2 requires δ < δ0, while the theorem's stated hypothesis allows larger failure probabilities such as 1/3. This is a genuine gap in the central lower-bound proof, but it is local and plausibly fixable by an amplification argument, so a conditional accept rather than a rejection is appropriate. I did not find a separate fatal flaw in the Wishart posterior argument or in the upper-bound polynomial construction; the main issue is that the theorem's proof, as written, does not cover the standard constant-confidence setting without additional reasoning.","tokens_in":10651,"tokens_out":16115,"duration_ms":200898,"concrete_test":"Re-derive Section 4.2 with δ fixed at 1/3 and a concrete choice such as C = 2, p = 1. Using Proposition 8, compute the constant ε and hence δ0. If δ0 < 1/3, the final contradiction does not fire, confirming the gap. Then check whether repeating the alleged algorithm O(log(1/δ0)) times and taking a median restores an n = Ω(d) lower bound with only a constant-factor loss in query count. If such an amplification argument can be written cleanly, the theorem is salvageable but the printed proof is incomplete; if not, the theorem as stated is unproved for this standard confidence regime.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is the final paragraph of Section 4.2. After deriving the inequality ε(1/2 − δ) ≤ δ, equivalently δ ≥ δ0 := ε/(2(1+ε)), the proof says that the theorem 'allows choosing any δ < δ0' and declares a contradiction. But the theorem's hypothesis is only that δ > 0 'is dependent only on C'; it does not assert a bound δ < δ0. Since ε depends on p through the Wishart lower-tail constant (ε ≍ (C^2 C'_p)^{-1/2p} in the proof), δ0 depends on p as well as on C. For a standard fixed failure probability such as δ = 1/3, if δ0 < 1/3 the final contradiction does not fire, so the proof as written does not prove n = Ω(d) for that setting. This is not purely presentational: the proof establishes a lower bound only for algorithms with unusually small allowed failure probability (δ < δ0), unless an additional amplification argument is supplied and analyzed. No such argument appears in Section 4.2. The rest of the proof structure (posterior Wishart form via Proposition 6, the λmin comparison via Proposition 7, and the constant-probability lower-tail event via Proposition 8) appears internally consistent, so the issue is specifically the quantifier and the missing amplification step.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies the query complexity of estimating tr(f(A)) by Hutchinson's method with Block Krylov subspace approximations. It formalizes the relation between Krylov iterations and polynomial degree, gives upper bounds for tr(A^{-1/2}) and tr(A^{-1}), and proves a query lower bound for estimating tr(W^{-p}) for a d-dimensional Wishart matrix W when p>1/2, claiming that n=Ω(d) matrix-vector product queries are necessary for a constant-factor approximation. The lower-bound proof uses a posterior Wishart characterization from BHSW20 and eigenvalue tail bounds from Edelman, Vershynin, and Szarek.","tokens_in":10982,"tokens_out":12157,"duration_ms":129530,"significance":"The paper's upper-bound formalization is useful pedagogy, and the lower-bound extension to p>1/2 is a natural and potentially valuable strengthening of the known p=1 result. The proof strategy of relating queries to a Wishart posterior is principled and builds on established results rather than fitted parameters or self-citations. The main claims are not, however, fully established by the proofs as written: the final paragraph of Theorem 5's proof only covers algorithms with failure probability below an explicit δ0(C,p), and the polynomial-degree calculation in Theorem 3 (and Proposition 2) oversimplifies in a way that invalidates the stated degree bound from the given argument. The results are likely repairable, but the manuscript requires substantive revision.","major_comments":[{"comment":"The proof of Theorem 5 establishes only the inequality δ ≥ δ0 := ε/(2(1+ε)), where ε depends on both C and p. This yields a contradiction only for algorithms whose failure probability δ is smaller than δ0. The theorem statement says 'δ >0 is dependent only on C' and does not impose δ < δ0; for a fixed confidence value such as δ=1/3 with δ0<1/3, the displayed inequality is consistent with n≤d/2 and the proof does not rule out o(d) queries. To prove the theorem as stated, the author must either add a median-amplification argument (which would transfer the small-δ lower bound to any fixed δ at a constant multiplicative query cost) or restate the theorem with an explicit quantifier of the form 'there exists δ0(C,p)>0 such that for all δ<δ0'. The missing amplification step is load-bearing because the theorem is claimed for arbitrary positive δ, not only for δ below a small threshold.","section":"§4.2, final paragraph"},{"comment":"The degree calculation is not valid. With T=Cκ log(2κ/δ_P) and δ_T=δ_P/(2T), the dominant degree is O(√T log(T/δ_T)) = O(√(κ log(κ/δ_P)) · log(κ^2 log^2(κ/δ_P)/δ_P)), which is O(√κ (log(κ/δ_P))^{3/2}) for fixed δ_P as κ→∞, not O(√κ log(κ/δ_P)). The displayed chain 'O(√T log T) = O(√κ log(κ/δ_P))' drops a √(log(κ/δ_P)) factor. Since Theorem 3's degree bound is exactly what is used to claim the O(√κ log(κ/δ)) cost for tr(A^{-1}), the proof as written does not establish the stated upper bound. The same simplification appears in the proof of Proposition 2 in §3.1, where the substitution T=O(κ log(κ/δ)) similarly yields an extra √(log(κ/δ)) factor.","section":"§3.2, proof of Theorem 3"}],"minor_comments":[{"comment":"Theorem 5 states the result for tr(W^{-p}) with p>1/2, but the proof uses q and says 'valid for all q>1/2'; the notation should be aligned.","section":"§4.2"},{"comment":"The sentence 'Let > 0 be the failure probability that we choose later' is missing the symbol for the positive constant; it should read 'Let ε > 0 be a positive constant that we choose later'.","section":"§4.2, opening sentence"},{"comment":"The phrase 'where δ >0 is dependent only on C' is ambiguous and should be replaced by an explicit quantifier, for example 'for every δ∈(0,δ0(C,p))' if that is the intended statement.","section":"Theorems 4 and 5"},{"comment":"The reduction 'Total Cost = O(N_v · g(x))' treats N_v as an independent parameter without discussing how N_v trades off against the target success probability or variance of Hutchinson's estimator; stating this assumption explicitly would improve clarity.","section":"§2.2.2"}],"recommendation":"major_revision","confidential_remarks":"The manuscript appears to be an early draft: it has a course-project acknowledgment, missing symbols, and ambiguous quantifier statements. The lower-bound result is plausible and the missing amplification step is standard, so major revision is appropriate. If the author cannot supply a correct polynomial-degree argument for Theorem 3, the upper-bound contribution should be downgraded or presented as conditional on a known approximation result, while the lower-bound theorem with a corrected quantifier could still stand."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the one genuinely new item is the extension of the CDLLN24 Wishart query lower bound from tr(W^{-1}) to tr(W^{-p}) for p>1/2, and the proof follows the right posterior-Wishart template. But the theorem as stated isn't what the proof shows, and the upper-bound section has a degree-computation gap. Both are fixable, so this is a revise-and-resubmit, not a reject.\n\nOn the plus side: the structural reduction from Block Krylov iteration count to polynomial degree is cleanly stated, and the lower-bound proof correctly assembles the pieces from BHSW20 and Edelman/Vershynin: the posterior Wishart form, the lambda_min comparison, and the constant-probability small-eigenvalue event. There's no circularity and no fitted parameters. The paper is honest about what is review (Section 3.1) and what is new.\n\nSoft spots: (1) Theorem 5 states delta depends only on C, but the proof derives delta >= delta0 with delta0 = epsilon/(2(1+epsilon)) where epsilon depends on both C and p. The final contradiction only fires if the algorithm's failure probability is below delta0. For a fixed confidence like 1/3, the proof gives nothing. The theorem needs to be restated, or an amplification argument supplied. This is not a tiny typo; it is the load-bearing step. (2) Theorem 3 claims degree O(sqrt(kappa) log(kappa/delta)) but the proof yields O(sqrt(kappa log(kappa/delta)) * log(kappa/delta)), which is about sqrt(kappa) log^{3/2}(kappa/delta) by the paper's own calculation. There is an unaccounted square root of the log factor. That may be fixable with a sharper polynomial approximation or a different parameter choice, but as written the bound doesn't follow. (3) Minor: lots of typos and missing symbols in the text, e.g., the proof of Theorem 5 opens with \"Let > 0 be the failure probability,\" and Proposition 1's statement is mangled. None of this obscures the main idea, but it is not polished.\n\nWho is this for? People working on query complexity of trace estimation or randomized linear algebra. The lower-bound extension is a natural incremental result and deserves a serious referee. My recommendation: send it out; a good referee can check whether the delta quantifier can be repaired, for instance by stating the result for delta below a constant depending on C and p, or by adding a standard amplification argument.","headline":"A plausible but not-yet-clean extension of the known Wishart query lower bound to inverse powers; the proof has a quantifier gap and the upper-bound section has a degree error, so it needs revision, not rejection.","tokens_in":11463,"tokens_out":3330,"would_cite":false,"duration_ms":35336,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60B20","65Y20","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"A constant-factor estimate of the trace of an inverse power of a Wishart matrix requires Ω(d) matrix-vector queries.","keywords":["trace estimation","lower bounds","Wishart matrices","Block Krylov","polynomial approximation","Hutchinson's method","query complexity","inverse trace"],"falsifier":"Compute $\\delta_0 = \\varepsilon/(2(1+\\varepsilon))$ for explicit constants, say $C=2$ and $p=1$, by extracting the hidden constant in Proposition 8's $\\asymp$. If $\\delta_0$ is smaller than a standard failure probability like $1/3$, then the proof does not establish the theorem for $\\delta=1/3$; moreover, an algorithm that estimates $\\mathrm{tr}(W^{-1})$ with $o(d)$ queries and success probability $2/3$ would directly refute the claimed lower bound.","tokens_in":10461,"feed_emoji":"📉","tokens_out":14800,"duration_ms":121916,"temperature":0.7,"pith_summary":"The paper sets out to prove that on a $d\\times d$ Wishart matrix $W$, any algorithm that estimates the trace of $W^{-p}$ for $p>1/2$ to within a constant factor with high probability must make $n=\\Omega(d)$ matrix-vector product queries. If true, constant-factor inverse-power trace estimation is as hard as reading the whole matrix on these random instances, matching the previously known $p=1$ lower bound. The paper also formalizes the connection between the number of Block Krylov iterations and the degree of a polynomial approximating the scalar function $f$, and uses it to derive upper bounds for estimating $\\mathrm{tr}(A^{-1/2})$ and $\\mathrm{tr}(A^{-1})$. The overall picture is that trace estimation cost is governed by polynomial approximation degree on the upper side and by query-information limits on the lower side.","feed_headline":"Inverse-power trace estimation provably needs Ω(d) queries","feed_subtitle":"Constant-factor estimates of inverse-power traces force probing nearly every dimension of a Wishart matrix.","key_machinery":"The machinery has three load-bearing components. First, a Block Krylov method with $m$ iterations only reaches the subspace $\\mathrm{span}\\{V, AV, \\ldots, A^{m-1}V\\}$, so its approximation to $f(A)V$ is exactly a matrix polynomial $Q_{m-1}(A)V$; this equates Krylov iteration count with polynomial degree and reduces upper-bound analysis to scalar polynomial approximation. Second, for a Wishart matrix $W$, any $n<d$ adaptive queries $Wv_1,\\ldots,Wv_n$ reveal only a Gaussian linear map: after an orthogonal change of variables, the conditional distribution of $W$ is a block matrix containing an independent $\\mathrm{Wishart}(d-n)$ corner, so the unobserved part retains full low-dimensional uncertainty. Third, spectral small-ball estimates for Wishart matrices (the smallest eigenvalue falls below a constant times $d^{-2}$ with probability about $\\sqrt{x}$) provide the constant-probability event that drives the lower bound. The chaining of these three pieces is what forces $n=\\Omega(d)$.","core_discovery":"The central claim is Theorem 5: for any $d\\ge 2$, any algorithm that performs $n$ matrix-vector product queries with a $d\\times d$ Wishart matrix $W \\sim \\mathrm{Wishart}(d)$ and outputs an estimator $\\hat{tr}$ satisfying $C^{-1}\\mathrm{tr}(W^{-p}) \\le \\hat{tr} \\le C\\,\\mathrm{tr}(W^{-p})$ with probability at least $1-\\delta$, where $p>1/2$, must have $n=\\Omega(d)$. The proof argues by contradiction, assuming $n\\le d/2$. After $n$ queries, the posterior distribution of $W$ has a block form whose lower-right corner is an independent $\\mathrm{Wishart}(d-n)$ matrix; with probability at least a constant $\\varepsilon$, the smallest eigenvalue of that corner is small, which would force the estimator to be too small on a set of positive probability. Since this failure probability is at least $\\varepsilon(1/2-\\delta)$, it contradicts the success guarantee when $\\delta$ is smaller than a threshold $\\delta_0$. The theorem extends an existing $p=1$ lower bound to every $p>1/2$.","pith_inferences":["An implicit consequence the paper does not draw: the same argument may extend to other spectral functions with singularities at zero, as long as the scalar polynomial approximation degree and the Wishart small-ball probability can be matched; the exact threshold $p>1/2$ is tied to convergence of $\\sum_j j^{-2p}$.","The quantifier issue around $\\delta$ suggests that a stronger argument, or an explicit handling of the dependency of $\\varepsilon$ on $C$ and $p$, is needed to guarantee fixed-failure-probability settings; a reader who only needs error probability $1/3$ should not treat the theorem as proven in its current form.","A direct testable extension would be to run the Hutchinson-Krylov method on Wishart instances with $n=o(d)$ and a constant-factor target, and measure the empirical failure probability; the theorem predicts it stays bounded away from 0."],"forward_implications":["If Theorem 5 holds, every constant-factor estimator of $\\mathrm{tr}(W^{-p})$ for $p>1/2$ on Wishart matrices requires essentially $d$ matrix-vector products, so the $p=1$ lower bound is not an artifact of the reciprocal function.","The upper-bound analysis shows the Hutchinson-Krylov method achieves cost $O(N_v \\sqrt{\\kappa}\\log(\\kappa/\\delta))$ for $\\mathrm{tr}(A^{-1})$ and $\\mathrm{tr}(A^{-1/2})$, tying the number of Krylov steps to the required polynomial degree.","For well-conditioned matrices, near-linear-in-$\\kappa$ algorithms are possible, while the Wishart lower bound shows that when the spectrum has heavy small eigenvalues, dimension-scale probing is unavoidable.","The result also clarifies that the information-theoretic hardness comes from the unbounded influence of small eigenvalues of $W$, not from the conditioning number alone."],"supporting_citations":[{"why":"Lemma 3.4 supplies the Wishart posterior block form under adaptive matrix-vector queries, the structural core of the lower-bound proof.","marker":"[BHSW20]"},{"why":"Theorem 4 is the p=1 inverse-trace lower bound that Theorem 5 extends to all p>1/2.","marker":"[CDLLN24]"},{"why":"Proposition 1, the polynomial approximation of monomials, supports the upper-bound results for tr(A^{-1/2}) and tr(A^{-1}).","marker":"[SV+14]"},{"why":"Theorem 1.2 gives the bound on reciprocals of Wishart eigenvalues used in Proposition 9 to control tr(W^{-1}).","marker":"[Sza91]"},{"why":"Provides the small-ball behavior of the smallest singular value of Gaussian matrices used in Proposition 8.","marker":"[Ede88]"},{"why":"Adds the tail bound on the largest singular value of Gaussian matrices used in Proposition 8.","marker":"[Ver18]"}],"fun_headline_variants":["Trace estimation lower bound: Ω(d) queries for inverse powers","Block Krylov trace estimation hits Ω(d) query wall","Wishart trace estimation requires probing all dimensions","Estimating inverse-power traces demands Ω(d) matrix-vector products","Lower bound: inverse-power trace estimation is dimension-bound"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof only forces a contradiction when the algorithm's failure probability $\\delta$ is smaller than a constant $\\delta_0$ that depends on both the approximation factor $C$ and the power $p$, while the theorem statement asserts $\\delta$ depends only on $C$; if the intended guarantee uses a fixed failure probability such as $1/3$, the final step does not go through.","fun_headline_variants_meta":{"raw":{"variants":["Trace estimation lower bound: Ω(d) queries for inverse powers","Block Krylov trace estimation hits Ω(d) query wall","Wishart trace estimation requires probing all dimensions","Estimating inverse-power traces demands Ω(d) matrix-vector products","Lower bound: inverse-power trace estimation is dimension-bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000554,"raw_usage":{"total_tokens":2653,"prompt_tokens":969,"completion_tokens":1684,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":585,"completion_tokens_details":{"reasoning_tokens":1603}},"tokens_in":585,"tokens_out":1684,"duration_ms":10946,"temperature":1.0,"reasoning_tokens":1603,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T22:01:40.565384+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute $\\delta_0 = \\varepsilon/(2(1+\\varepsilon))$ for explicit constants, say $C=2$ and $p=1$, by extracting the hidden constant in Proposition 8's $\\asymp$. If $\\delta_0$ is smaller than a standard failure probability like $1/3$, then the proof does not establish the theorem for $\\delta=1/3$; moreover, an algorithm that estimates $\\mathrm{tr}(W^{-1})$ with $o(d)$ queries and success probability $2/3$ would directly refute the claimed lower bound.","supporting_citations":[],"review_version":1}