{"id":"47679ffa-e25e-4beb-96de-131f84517c4a","arxiv_id":"2506.17556","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Block-Nyström averages many smaller Nyström approximations to match the guarantee of one large approximation at lower cost when the effective dimension is large.","lead":"This paper introduces Block-Nyström, a low-rank matrix approximation that averages several small Nyström blocks and is designed to be faster than the standard Nyström method when a matrix has a heavy-tailed eigenvalue decay. It proves speed-ups for preconditioning quadratic optimization and for kernel ridge regression in hard learning settings.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Unproved, self-cited Lemma 6 is the linchpin: it supplies the only lower bound on the expected Nyström projection that powers the tail-approximation and inversion analyses.","rationale":"The reader's weakest_assumption identifies exactly the point I would stress: Lemma 6, imported from an overlapping preprint, is the load-bearing bias estimate for the entire Block-Nyström analysis. I found no independent error in the matrix-Chernoff argument that follows once Lemma 6 is granted, and the recursive-inversion proof, while sketchy and with a malformed constant condition in Theorem 4, is secondary: even if the solver theorem were fully repaired, the spectral-approximation guarantee would still fail without Lemma 6. The paper's core conceptual claim—that averaging several smaller Nyström approximations improves tail estimates—depends on the expected-projection lower bound, so the correctness of Lemma 6 is the condition that must hold for the central claim to be true. This is not an objection to the approach's plausibility; the lemma is plausible and may well be provable, but the paper as written does not provide the proof, and the constant and sample-size requirements are precisely what set q and the final approximation factor. My recommendation is unchanged: acceptance should be conditional on a self-contained proof of Lemma 6 (and, secondarily, on cleaning up the statement of Theorem 4).","tokens_in":33914,"tokens_out":26169,"duration_ms":236548,"concrete_test":"Obtain a complete proof of Lemma 6 from the authors or from Rathore et al., and independently check its quantitative content: for a non-diagonal heavy-tailed matrix such as A = Q diag(1, 1/2, ..., 1/n) Q^T with a random orthogonal Q, set λ' = 1 and sample m = 100 d_{λ'}(A) log^3 n landmarks i.i.d. from O(1)-approximate ridge leverage scores, averaging the projection P over at least 1000 trials; the smallest eigenvalue of the empirical E[P] − (1/2) A(A+λ'I)^{-1} must be nonnegative. If the proof requires a larger sample size or the inequality fails numerically, then Theorem 3's q = O(α) block count and Theorem 1's guarantees collapse.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 6 (Appendix B) applies Lemma 6 to obtain E[Â_i] ⪰ (1/2) A(A+λ'I)^{-1}A, which is the sole source of the μ_min ≥ (1/8)√(λ/λ') lower bound used in the matrix-Chernoff argument. That lower bound directly determines the block count q = O(α) and the final approximation factor in Theorem 3, and the same Lemma 6 drives Theorem 7, i.e. the concentration step behind the recursive solver's preconditioner quality. Lemma 6 is stated without proof and cited to Rathore et al. 2025, an unpublished preprint with overlapping authorship. The claim is not a trivial identity: for i.i.d. leverage-score sampling, E[P] is a sum of rank-one projections, and controlling its off-diagonal structure to get E[P] ⪰ (1/2)A(A+λ'I)^{-1} with m = O(d_{λ'}(A) log^3 n) samples is exactly the nontrivial part. The constant 1/2 and the hidden constant in the sample size are what make q = O(α) sufficient; if either is off, the averaging number and the O(α) approximation both change. Separately, Theorem 4's statement contains a self-referential condition on c (c ≥ log^{2/ϕ}(20c^2(1+θ)^4)) and relies on imported Lemma 12, but the more load-bearing issue is the unproved bias bound. The central claim of Theorem 1 therefore rests on an unverified external lemma.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Block-Nyström, an algorithm that averages q independent Nyström approximations built from smaller blocks of ridge-leverage-score landmarks, and claims a λ-regularized O(α)-approximation of an n×n psd matrix with rank m = O~(α d_{α²λ}(A)), construction time O~((nm²+m³)/α²+nm), and (after a recursive preconditioning scheme) inverse-application time O~(nm α^{o(1)}). The analysis is based on a bias-variance trade-off in which the expectation of the Nyström projection provides tail information and averaging controls variance, leading to a Chernoff-type concentration bound. Applications to quadratic minimization and to kernel ridge regression in the unattainable setting are given, including a new risk bound for approximate KRR with non-projection approximations.","tokens_in":34258,"tokens_out":12859,"duration_ms":122162,"significance":"The proposed technique is a genuine departure from the classical Nyström method: the improvement is obtained by sampling at regularizer α²λ instead of αλ, and the comparison with classical Nyström is not tautological. If the results hold, they reduce the cost of low-rank approximation in heavy-tailed spectral regimes by a factor α^{2γ} for polynomial decay, and the general KRR risk analysis of Theorem 5 is a useful independent contribution. The proof structure is transparent and the Chernoff argument for averaging is clean. However, the main spectral approximation theorem is conditional on an unproved external lemma (Lemma 6), and the recursive solver is stated with a self-referential constant; these are load-bearing gaps that must be addressed before the claims can be accepted.","major_comments":[{"comment":"The proof of Theorem 6 relies on Lemma 6, which is stated without proof and cited to Rathore et al. [2025], an unpublished preprint with overlapping authorship. The lower bound E[P] ⪰ (1/2)A(A+λ'I)^{-1} is the sole source of the bound μ_min ≥ (1/8)√(λ/λ'), which in turn determines q = O(α) and the final approximation factor in Theorem 3, and the same lemma drives Theorem 7 and hence the recursive solver. This is the central load-bearing step of the paper; please include a complete proof of Lemma 6 or replace it with an independently verifiable published result.","section":"§3.1, Appendix B, Lemma 6"},{"comment":"The stated condition on c is self-referential and therefore not a well-formed theorem hypothesis. Theorem 4 requires c ≥ max{ log^{2/ϕ}(20c²(1+θ)^4), 2 }, and Theorem 8 requires c ≥ max{ (4(1+θ)²)^{2/ϕ}, log^{2/ϕ}(20c²(1+θ)^4) }; in both cases c appears on both sides of the inequality. The proof sketch and Lemma 13 show that a sufficiently large c exists, but the theorem statements should be reformulated with an explicit choice, for example c = Θ(log n) satisfying the required inequalities, rather than a condition defined in terms of c itself.","section":"Theorem 4 (main text) and Theorem 8 (Appendix B)"}],"minor_comments":[{"comment":"The displayed inequality uses (64α)^{-1} on the left-hand side, but the text calls this a 16α-approximation; the constant in the statement and the constant in the text should be made consistent.","section":"Theorem 3"},{"comment":"The total landmark count is m = O~(α d_{α²λ}(A)), not O~(α d_{αλ}(A)) as written; the current formula is inconsistent with Theorem 1 and with the proof of Theorem 1.","section":"Remark 2"},{"comment":"The text 'O~(n^{0.065}+k^ω)' appears to be a typo for 'O~(n^{2.065}+k^ω)' based on the comparison in Corollary 2; please correct it.","section":"Section 4 Discussion"},{"comment":"The phrase 'using techniques from Lemma 8' should refer to Theorem 8, since Lemma 8 is the Cordes inequality and is not the solver result used for the linear-system cost.","section":"Appendix C, Lemma 17"},{"comment":"The statement does not explicitly restrict 0<θ<1 and 0<ϕ<1, although the proof uses these restrictions; please state them in the theorem.","section":"Theorem 8"},{"comment":"The claim that the minimum of the displayed rational function is attained at x = √(λλ') is asserted without showing the calculation; adding the one-line derivation would improve verifiability.","section":"Proof of Theorem 6"}],"recommendation":"major_revision","confidential_remarks":"The main exposure is the reliance on Lemma 6 from an unpublished, overlapping-authored preprint; I recommend that acceptance be conditional on the authors either providing a full proof of this lemma or citing a published version. There is also a self-referential condition in Theorems 4 and 8 that should be cleaned up before the paper is sent to production."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The one thing you should know: this paper proposes a smart variant of Nyström — average several independent small Nyström approximations instead of one large one — and shows that this can give a λ-regularized α-approximation with roughly α times fewer landmarks. If the analysis holds, it genuinely broadens where Nyström-type methods are affordable for heavy-tailed spectra.\n\nWhat's actually new: the block-averaging construction and the bias-variance trade-off analysis are, as far as I can tell, new. Theorem 6 (spectral approximation) is a clean application of matrix Chernoff once you accept Lemma 6. Theorem 5's risk bound for non-projection approximations is a useful extension of the KRR analysis and likely of independent interest. The concrete runtime improvements for quadratic minimization (n^2.065 → n^2.044) and for KRR are real if the main theorem stands.\n\nWhere it wobbles: the load-bearing Lemma 6 — E[P] ⪰ ½ A(A+λ'I)^{-1} for ridge leverage score sampling — is stated without proof and cited to a preprint by overlapping authors. This lemma is exactly what turns the averaged Nyström copies into an O(√(λ'/λ)) tail approximation. The ½ constant and the sample-size requirement determine the block count and the final approximation factor. I could not find a proof in the paper, and it is not a trivial identity. That is a serious gap for a main theorem. Separately, Theorem 8 (the recursive solver) has a statement with a self-referential condition on c (c appears on both sides of the inequality), and the proof sketch is hard to parse. That needs to be fixed before a referee can judge it.\n\nOverall: the central idea is plausible and the paper is honestly written — the authors flag the reliance on Lemma 6 in the body, which is good practice. But the current draft is not self-contained for its main result. I would send it to peer review with a request for a full proof or independent verification of Lemma 6, and a cleaned-up statement of Theorem 8. If the lemma turns out to be true, this is a solid incremental contribution worth citing; if not, the approximation guarantee collapses.\n\nWho this is for: people working on randomized low-rank approximation, preconditioning, and kernel ridge regression. I'd bring it to a reading group to see whether anyone can verify Lemma 6 from Rathore et al.","headline":"Smart averaging idea with real potential, but the central spectral bound currently rests on an unproved self-cited lemma and the recursion theorem is not in checkable form.","tokens_in":34784,"tokens_out":2262,"would_cite":false,"duration_ms":22718,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that a $\\lambda$-regularized $O(\\alpha)$-approximation of any positive semidefinite matrix can be built and inverted faster than classical Nyström when the spectrum is heavy-tailed, by averaging $q = \\tilde{O}(\\alpha)$…","keywords":["Block-Nyström method","low-rank matrix approximation","ridge leverage scores","effective dimension","kernel ridge regression","recursive preconditioning","heavy-tailed spectra","randomized numerical linear algebra"],"falsifier":"Run the construction on a diagonal matrix $A$ with eigenvalues $i^{-1/\\gamma}$ (for instance $n=10^4$, $\\gamma=0.8$), choose $\\lambda$ so that $d_{\\alpha^2\\lambda}(A)\\approx 200$, draw $q=64\\alpha\\log(n/\\delta)$ blocks, and compute $\\rho_{\\min} = \\lambda_{\\min}\\big((A+\\lambda I)^{-1/2}(\\hat A[q]+\\lambda I)(A+\\lambda I)^{-1/2}\\big)$. If $\\rho_{\\min} < 1/(64\\alpha)$ with non-negligible probability, the main spectral guarantee fails; alternatively, Monte Carlo estimate the Loewner gap $\\mathbb{E}[P] - \\tfrac12 A(A+\\lambda'I)^{-1}$ on one block to test Lemma 6 directly.","tokens_in":33735,"feed_emoji":"🧮","tokens_out":10360,"duration_ms":94116,"temperature":0.7,"pith_summary":"The paper proposes Block-Nyström, a randomized low-rank approximation for positive semidefinite matrices aimed at the regime where classical Nyström becomes too expensive: heavy-tailed spectra with large effective dimension. Its central claim is that averaging $q = \\tilde{O}(\\alpha)$ independent small Nyström approximations, each built from $\\tilde{O}(d_{\\alpha^2 \\lambda}(A))$ landmarks, produces a $\\lambda$-regularized $O(\\alpha)$-approximation of $A$ in Loewner order, while reducing the construction cost to $\\tilde{O}((n m^2 + m^3)/\\alpha^2 + n m)$ and allowing $(\\hat A + \\lambda I)^{-1}$ to be applied in $\\tilde{O}(n m \\alpha^{o(1)})$ time. The key insight is a bias-variance trade-off: one large Nyström approximation has a poor spectral tail, whereas several smaller ones average out tail variance while retaining top-spectrum bias. The paper applies this construction to preconditioned convex optimization and to kernel ridge regression in the unattainable regime, proving new risk bounds for approximate solvers that are no longer exact projections.","feed_headline":"Averaged Nyström blocks tame heavy-tailed matrices faster","feed_subtitle":"Block-Nyström keeps an O(α) approximation while cutting sampling and inversion cost when effective dimension is huge.","key_machinery":"The load-bearing object is the Block-Nyström matrix, defined as an average of $q$ i.i.d. Nyström projections $\\hat A_i = C_i W_i^{-1} C_i^\\top$ on disjoint landmark blocks $S_i$; the block-diagonal $W$ encodes that averaging. The argument runs on two small parts. First, the expected projection bound $\\mathbb{E}[P] \\succeq \\tfrac12 A(A+\\lambda' I)^{-1}$ for $\\lambda'$-ridge leverage score sampling (Lemma 6) shows that the expectation of a single Nyström matrix estimates the spectral tail, even though any single low-rank realization does not; a matrix Chernoff bound then converts this expectation into a bias-variance error of order $\\sqrt{\\lambda'/\\lambda} + \\lambda'/(q\\lambda)$, whose optimum forces $\\lambda' = \\alpha^2 \\lambda$ and $q=\\tilde{O}(\\alpha)$. Second, the inverse is computed by recursive preconditioning: at level $k$ the system $M_k = \\hat A[q_k] + c^{2k}\\lambda I$ is preconditioned by the smaller $M_{k+1}$, until the recursion reaches a single Nyström block inverted via Woodbury; a solver composition lemma keeps the total per-vector cost nearly linear. A novel risk analysis for kernel ridge regression replaces the projection assumption of prior work with the regularized-approximation condition (1), which is what lets the non-projection Block-Nyström solver inherit near-optimal learning rates.","core_discovery":"For any positive semidefinite $A$, regularizer $\\lambda>0$, and approximation factor $\\alpha\\ge 1$, the paper claims a data structure $\\hat A$ of rank $m=\\tilde{O}(\\alpha d_{\\alpha^2\\lambda}(A))$ such that $(64\\alpha)^{-1}(A+\\lambda I) \\preceq \\hat A+\\lambda I \\preceq A+\\lambda I$ with high probability. Here $d_{\\lambda}(A)=\\operatorname{tr}(A(A+\\lambda I)^{-1})$ is the $\\lambda$-effective dimension. The structure is the Block-Nyström matrix $\\hat A = C W^{-1} C^\\top$ with $C=A_{:,S}$ and $W = q\\operatorname{diag}(A_{S_1,S_1},\\ldots,A_{S_q,S_q})$, equivalently the average of $q$ independent Nyström approximations sampled from $O(1)$-approximate $\\alpha^2\\lambda$-ridge leverage scores. Setting $\\alpha=1$ recovers the classical Nyström guarantee, while increasing $\\alpha$ replaces the costly dimension $d_\\lambda(A)$ by the smaller $d_{\\alpha^2\\lambda}(A)$. The paper also claims that $(\\hat A+\\lambda I)^{-1}$ can be applied to a vector in $\\tilde{O}(n m \\alpha^{o(1)})$ time using a recursive preconditioning scheme, and that these guarantees translate into faster preconditioning and near-optimal kernel ridge regression in heavy-tailed settings.","pith_inferences":["Beyond the paper: the averaging principle is not tied to ridge leverage scores; any estimator whose expectation captures the spectral tail but whose single draws are noisy could be averaged the same way, so random-feature and sketching variants are a natural testbed.","Beyond the paper: the bias-variance split suggests the optimal block count should track the ratio $d_{\\alpha\\lambda}(A)/d_{\\alpha^2\\lambda}(A)$, so one could tune $q$ adaptively from eigenvalue estimates, which the paper does not do.","Beyond the paper: if the imported expected-projection lemma is improved or weakened, the $16\\alpha$ and $64\\alpha$ constants and the phase-transition thresholds in the cost analysis should shift; the same calculations would identify cross-over regimes not listed in the paper."],"forward_implications":["For spectra with polynomial decay $\\lambda_i=\\Theta(i^{-1/\\gamma})$, the construction is faster than classical Nyström by a factor $\\tilde{\\Omega}(\\alpha^{2\\gamma})$ at the same approximation quality; heavier tails give larger gains.","As a preconditioner for a strongly convex quadratic in the spiked-covariance model with at most $O(n^{0.82})$ large eigenvalues, the paper's Corollary 2 reduces the runtime from $\\tilde{O}(n^{2.065})$ to $\\tilde{O}(n^{2.044})$.","In kernel ridge regression over Hilbert spaces with smoothness $\\zeta<1/2$, Block-Nyström recovers the near-optimal learning rate with an extra factor $\\alpha$, and for small $\\theta$ (with $\\alpha=n^\\theta$) it cuts the Nyström cost by $n^{2\\theta\\gamma}$.","The recursive inversion scheme itself is a reusable primitive: it applies $(\\hat A+\\lambda I)^{-1}$ in near-linear time without paying the $O(m^3)$ Woodbury cost on the full block system."],"supporting_citations":[{"why":"Supplies the recursive ridge-leverage-score sampling algorithm and the classical Nyström spectral guarantee used as the base of Block-Nyström.","marker":"Musco and Musco [2017]"},{"why":"Imported Lemma 6, the expected-projection lower bound $\\mathbb{E}[P] \\succeq \\tfrac12 A(A+\\lambda'I)^{-1}$ that carries the tail-approximation argument.","marker":"Rathore et al. [2025]"},{"why":"Source of the recursive preconditioning scheme adapted to obtain near-linear inversion of the Block-Nyström matrix.","marker":"Dereziński and Sidford [2025]"},{"why":"Provides the preconditioned solver composition lemma used at every recursion level.","marker":"Jambulapati and Sidford [2024]"},{"why":"Provides the Nyström preconditioner baseline and the base solver for a single Nyström block used to terminate recursion.","marker":"Dereziński et al. [2025]"},{"why":"Fast approximate ridge leverage score sampling for kernel matrices with bounded diagonal, used in the KRR cost analysis.","marker":"Rudi et al. [2018]"},{"why":"Bias/variance lemmas and the optimal learning-rate framework for spectral algorithms in Hilbert spaces that the new KRR risk analysis extends to non-projection approximations.","marker":"Lin et al. [2020]"},{"why":"Accelerated approximate Newton convergence result combined with Block-Nyström to precondition convex objectives.","marker":"Ye et al. [2020]"}],"fun_headline_variants":["Block-Nyström accelerates low-rank and kernel ridge regression","Averaged Nyström blocks master heavy-tailed spectra quickly","Recursive Block-Nyström cuts cost for hard kernels","Smaller Nyström blocks, stronger tails, same guarantee"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is Lemma 6, an imported result that for $\\tilde{O}(d_{\\lambda'}(A))$ landmarks from $\\lambda'$-ridge leverage scores the expected Nyström projection satisfies $\\mathbb{E}[P] \\succeq \\tfrac12 A(A+\\lambda'I)^{-1}$; if that lemma is false or weaker than stated, the block count and the $O(\\alpha)$ approximation factor collapse.","fun_headline_variants_meta":{"raw":{"variants":["Block-Nyström accelerates low-rank and kernel ridge regression","Averaged Nyström blocks master heavy-tailed spectra quickly","Recursive Block-Nyström cuts cost for hard kernels","Smaller Nyström blocks, stronger tails, same guarantee"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000223,"raw_usage":{"total_tokens":1517,"prompt_tokens":1067,"completion_tokens":450,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":683,"completion_tokens_details":{"reasoning_tokens":377}},"tokens_in":683,"tokens_out":450,"duration_ms":4460,"temperature":1.0,"reasoning_tokens":377,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T19:08:20.347832+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the construction on a diagonal matrix $A$ with eigenvalues $i^{-1/\\gamma}$ (for instance $n=10^4$, $\\gamma=0.8$), choose $\\lambda$ so that $d_{\\alpha^2\\lambda}(A)\\approx 200$, draw $q=64\\alpha\\log(n/\\delta)$ blocks, and compute $\\rho_{\\min} = \\lambda_{\\min}\\big((A+\\lambda I)^{-1/2}(\\hat A[q]+\\lambda I)(A+\\lambda I)^{-1/2}\\big)$. If $\\rho_{\\min} < 1/(64\\alpha)$ with non-negligible probability, the main spectral guarantee fails; alternatively, Monte Carlo estimate the Loewner gap $\\mathbb{E}[P] - \\tfrac12 A(A+\\lambda'I)^{-1}$ on one block to test Lemma 6 directly.","supporting_citations":[],"review_version":2}