acceptodds
Under review as a conference paper at ICLR 2027

Supercharging trace estimation for concave matrix functions

Abstract

We propose the _accelerated funNystr\"om++_ method for computing spectral sums for positive increasing concave functions , like the log determinant. Our methods requires asymptotically fewer matrix–vector products (matvecs) with \(\mathbf A\) than all prior methods. In particular, despite Hutch++ and Lanczos-FA each having optimal matvec complexity for their respective tasks, their composition does not provide the optimal complexity matvec for computing spectral sums. Our method is especially efficient when has large condition number. We pair our algorithm with a high-quality implementation, provided as part of the open-source RandLAPACK library. We demonstrate the effectiveness of our algorithm and our implementation on a variety of real-world ML tasks, including evaluating Vendi scores and log-determinants. Compared to existing methods, we achieve an order of magnitude improvement in matvec complexity and wall-clock runtime.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
matrix method, numerical linear algebra, log determinant, trace estimation, krylov method, hutch++

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_SDvjOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3(+1)
Soundness
2
Read review
Paper summary

The paper estimates spectral sums tr(f(A))\mathrm{tr}(f(A)) for a psd matrix AA and a positive, increasing, concave function ff, such as the log-determinant or the von Neumann entropy used in Vendi scores, using only matrix–vector products (matvecs).

The proposed method, accelerated funNyström++, first builds a rank-kk Nyström approximation A^\hat{A} from a sparse sketch and computes tr(f(A^))\mathrm{tr}(f(\hat{A})) exactly. It then estimates the remainder tr(f(A)−f(A^))\mathrm{tr}(f(A) - f(\hat{A})) with ℓ\ell Hutchinson probes, applying f(A)f(A) by block Lanczos of depth tt.

The key observation is that a Nyström column costs one matvec while a probe costs tt, and the accuracy only requires kℓ≳1/ε2k\ell \gtrsim 1/\varepsilon^2. So taking k≫ℓk \gg \ell gives O(max⁡{t,t/ε})O(\max\{t, \sqrt{t}/\varepsilon\}) matvecs, compared with O(t/ε)O(t/\varepsilon) for composing Hutch++ with Lanczos-FA.

The supporting theory includes:

  • an extension of the funNyström bound beyond operator monotone functions (Thm. B.8);
  • a Nyström bound for sparse sketches (Thm. B.3);
  • degree bounds (Thm. 4.1);
  • a stopping rule (Thm. C.3).

The method is implemented in RandLAPACK and evaluated on Vendi scores, NTK log-determinants and synthetic spectra.

Critical strengths

S1. The idea is simple and gives a provable gain. Making the Nyström rank much larger than the number of probes improves the worst-case matvec complexity from O(t/ε)O(t/\varepsilon) to O(max⁡{t,t/ε})O(\max\{t, \sqrt{t}/\varepsilon\}), which shows that combining an optimal trace estimator with an optimal matrix-function method is not optimal for spectral sums. Theorem B.8 is also a useful extension: earlier funNyström guarantees needed operator monotone functions, and the new result covers −xlog⁡x-x\log x, which is what Vendi scores need. For me this is a clear and well-motivated improvement for a common task in ML.

S2. The experiments are extensive and carefully run. On Vendi scores (n=50,000n = 50{,}000) the error is about 4–16× lower at the same matvec budget, and on NTK log-determinants (n=25,000n = 25{,}000) the method matches the best competitor in matvecs while being about 10× faster. The authors rewrote the competitors' Lanczos code in blocked form for fairness and controlled the hardware setup, and the appendix contains many further comparisons and ablations (Figs. 3–6). The code is public. After reading the appendix, I have no real concerns about the experimental evidence.

Critical weaknesses

W1. In my opinion, the algorithmic novelty is too limited for ICLR. The method combines existing parts: the Nyström approximation, funNyström++ (Persson & Kressner 2023) and block Lanczos. The main new step is choosing k≫ℓk \gg \ell. Theorems B.3 and B.8 are real additions, but the core of the method is a re-balancing of a known estimator, and no lower bound shows that the new rate is optimal. I think this work would fit better in a numerical linear algebra or signal processing venue such as TMLR, IEEE TSP or SIMAX. This is the main reason for my rating.

W2. The theory and the implementation do not match, and the manuscript does not look finished.

App. D.4 (L1353–1355) says that RandBLAS does not implement the SparseStack sketch for which the theory is stated, so the code uses a SASO sketch instead. The experiments therefore do not directly test the sparse-sketch result (Thm. 3.3 / B.3).

The baselines are named only in the figure legends; their descriptions and references appear only in App. D.1 (L1215–1228). Krylov-aware trace estimation (Chen & Hallman 2023) is discussed but not compared.

Many cross-references are empty and some sentences are unfinished, for example "In , we show an ablation" (L326–327), "In , we shift our focus" (L471–472), "and computing ." (L161) and "See for discussion" (L269). The caption of Fig. 5 ends mid-sentence. The main text also runs two lines onto page 10 (L486–487), which the AC may want to check against the page limit.

I believe all of this can be fixed in a revision, but it should be addressed before publication.

Questions for authors

Q1. This first question is the most important one for my assessment. Your theory is stated for the SparseStack sketch, but the implementation uses SASO. How should the experiments be read as validating Theorem 3.3? Does the analysis extend to SASO, or can you show a comparison of the two sketches?

Q2. This question is about novelty. What do log-det-ective and Krylov-aware trace estimation achieve in worst-case matvec complexity? Is any lower bound known that shows O(max⁡{t,t/ε})O(\max\{t, \sqrt{t}/\varepsilon\}) is optimal?

Q3. What do the empty references at L326–327 and L471–472 point to? Could Section 5 introduce each competitor with its reference and year?

Q4. How do the results change if the cost of choosing the Lanczos depth is included, and how does the self-tuned variant (Alg. 7) compare in Figs. 1–2?

Minor:

  • The definition of operator monotone at L203–204 has the inequalities reversed, and L354 reads "0⪯f(A)⪯f(A)0 \preceq f(A) \preceq f(A)".
  • At L452 the shift should be nlog⁡σn\log\sigma, not "n+log⁡(1/σ)n + \log(1/\sigma)".
  • Cor. 4.2 uses success probability 9/10, while Thm. 3.2 uses 99/100.
  • Definition 3.1 uses tolerance ε/n\varepsilon/n, but Thm. 4.1 uses log⁡(1/ε)\log(1/\varepsilon).
  • Typos: "Our methods requires", "Lanzos", "enilsted", "these these".
2 comments
AuthorsOpenReview ↗

Response to Reviewer SDvj

We are glad to hear you say that our idea is simple, clear, and "gives a well-motivated improvement for a common task in ML"! We also appreciate you taking a close look at our experiments, and are happy that you found them to be well made!

We agree with the reviewer that our core algorithmic contribution is a simple tweak of a known algorithm. In our view, this simplicity is a strength of our article. After all, despite there being several publications on this topic, no prior work clearly proposes this algorithmic tweak. Further, while the idea is simple, the analysis in the article is nontrivial and justifies the use of accelerated funNystrom++ far beyond what the prior work admitted. We hope this clarifies our perspective on the theoretical novelty within the article.


In response to your questions:

  1. Within the numerical linear algebra community, it is well understood that the SparseStack and SASO sparse sketching matrices have essentially identical empirical performance [C25, CEMT26, EKN26]. So, while the theoretical guarantees are stronger for the SparseStack, developing a good HPC implementation of the SparseStack was out of scope for this work: doing so would require heavily refactoring the RandBLAS library. Instead, we used the HPC implementation that was available to us, which is known to perform just as well in practice.

  2. As far as we are aware, every method in the prior work has matvec complexity at least O(t/ε)O(t/\varepsilon), while our method has complexity O(max⁡t,t/ε)O(\max\\{t,\sqrt t/\varepsilon\\}). While there is not a matching lower bound of Ω(max⁡t,t/ε)\Omega(\max\\{t,\sqrt{t}/\varepsilon\\}), as we note on page 2, existing results do imply a lower bound of Ω(max⁡t,1/ε)\Omega(\max\\{t,1/\varepsilon\\}). It is not clear that existing theoretical techniques are capable of proving lower bound that exactly matches our upper bound.

  3. There was a latex issue with several references at submission; this has been fixed. L326-327 referenced Figure 5, and L471 referenced Section D.8 and L472 referenced Section D.4. In section 5, we have added a description of the algorithms we compare against alongside relevant citations. Further, we have added Krylov-aware trace estimation to Figure 7, which performs similarly to classic funNystrom++. We will be ready to add it to Figures 1 and 2 by the camera-ready deadline, though we were unable to get the proper large-scale experiments ready by the rebuttal deadline.

  4. Empirically, including the depth selection time makes almost no difference. For instance, for the matrix in figure 1, when we exclude the depth selection time, at a fixed level of accuracy, our method is about 1.68×1.68\times faster than the next-best method. If we include the time, our lead grows very mildly to 1.77×1.77\times. Nevertheless, due to reviewer interest, we have updated figures 1 and 2 to show all the times including depth selection. For an explanation of why we prefer to exclude the information, see our response to Reviewer qjnh.


[EKN26]: Randomized algorithms in numerical linear algebra for scientific computing (link)

[CEMT26]: Faster Linear Algebra Algorithms with Structured Random Matrices (link)

[C25]: GPU-Parallelizable Randomized Sketch-and-Precondition for Linear Regression using Sparse Sign Sketches (link)

Reviewer_SDvjOpenReview ↗

Thank you for the response; final assessment

Thank you for the response and the revised manuscript. Unfortunately, the response arrived only a few hours before the end of the discussion phase, so there is no time left for the further discussion I would have liked to have.

The revision fixes the empty references and most of the errors I pointed out, Section 5 now describes each competing method with its reference, and the updated Figures 1 and 2 include the cost of depth selection. I appreciate these changes. Some points remain open: the SparseStack theory and the SASO implementation are still not compared directly in the paper, and Krylov-aware trace estimation appears only in Figure 7. I also note that the main text of the original submission ran about two lines beyond the 9-page limit (lines 486–487), which I mentioned in my review; I leave it to the AC to decide whether this matters.

My main concern was the size of the contribution for ICLR. The response agrees that the core algorithmic idea is a simple modification of a known method, and argues that its simplicity and the analysis are its strength. I understand this view, but it does not change my assessment of the novelty. I therefore keep my score of weak rejection.

Reviewer_qjnhOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes accelerated funNyström++ for estimating traces of increasing concave matrix functions. By allocating more computation to a low-rank approximation and fewer stochastic residual probes, it improves the stated matvec complexity from O(t/ε)O(t/\varepsilon) to O(max⁡{t,t/ε})O(\max \{t,\sqrt{t}/\varepsilon \}). The authors also extend approximation guarantees beyond operator monotone functions and develop an optimized implementation. Experiments evaluate accuracy and runtime on entropy estimation, regularized log-determinants, and other synthetic benchmarks.

Critical strengths

The strongest positive aspect is the practical implementation and its empirical evaluation. The reported results show favorable accuracy-cost tradeoffs on entropy and log-determinant estimation tasks. The implementation addresses substantial computational bottlenecks through different approaches, while ablations help explain their effects. Although the precise magnitude of the runtime advantage remains subject to the benchmarking limitations discussed below.

Critical weaknesses
  1. The experiments do not establish the claimed end-to-end runtime advantage. The main comparisons exclude Lanczos depth-selection costs. Consequently, the reported timings do not adequately separate algorithmic gains from implementation differences or demonstrate the full cost of the advertised adaptive method.

  2. The theoretical guarantees are inconsistent as stated. In Theorem C.3, the stopping criterion implies a relative-error bound of ε/(1−ε)\varepsilon/(1-\varepsilon), rather than the claimed ε\varepsilon. Separately, Theorem 4.1 omits the dependence on nn introduced by Definition 3.1’s ε/n\varepsilon/n approximation tolerance. These issues appear potentially repairable, but require corrected statements and corresponding adjustments to downstream guarantees before the theoretical contribution can be assessed reliably.

Questions for authors

Does the reported runtime advantage persist when depth-selection costs are included? How much of the advantage over log-det-ective remains?

2 comments
AuthorsOpenReview ↗

Response to Reviewer qjnh

We are glad that the reviewer found our empirical evidence compelling, and that a strength of our article arises from the simplicity of our core algorithmic recommendation paired with provable gains.

For reasons we explain in the next paragraph, we excluded depth selection in the figures in an effort to avoid unfair comparisons. Though, based on reviewer interest, we have updated figures 1 and 2 to include depth selection. As we mentioned to reviewer SDvj, this does not significantly change the results. Additionally, we were able to speedup the implementation of several implementations competitor methods (imate and XNysTrace). Nonetheless, our method remains fastest.


Reasoning: Almost all methods studied in this article use either a block Krylov method (our method, XNysTrace) or a single vector Krylov method (classic funNystrom++, SLQ, imate). Krylov-aware trace estimation uses both. All of these methods need to be supplied a depth tblockt_{block} or tsinglet_{single}, depending on what kind of Krylov subspace they build. The automatic depth selection method in algorithm 6 is randomized, and we do not want algorithm 6 to potentially be why our method succeeds while other methods fail. So, for each matrix, we run algorithm 6 once to determine tblockt_{block} and once to determine tsinglet_{single}. Then, all methods use those same two parameters. In this sense, none of the methods are charged for depth selection.

The exception is log-det-ective, which provides its own depth selection criteria. Nonetheless, the updated figure 2 provides a head-to-head comparison between our method and log-det-ective that includes the time > it takes to compute the depth on all methods. Our method remains the fastest by a large margin.


Thank you for pointing out the errors in the log rates. Theorem 4.1 was should have log⁡(n/ε)\log(n/\varepsilon), and corollary 4.2 has been corrected to be O~\tilde O instead of OO. We have also corrected the typo in the early stopping theorem C.3, correcting the matrix on the RHS.

Thank you for your corrections. They have increased confidence in the time-efficiency advantage of the proposed method. However, I do not find the idea of redistributing computational costs to be particularly novel. While the generalization to a broader class of functions is mathematically significant, I believe its application within the context of machine learning has not been fully explored. So I prefer to keep my score.

Reviewer_r1EGOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents a new method for calculating "spectral sums" that is evaluting tr(f(A))=∑if(λi)tr(f(A)) = \sum_i f(\lambda_i) for large (symmetric) matrices. In particular this applies to when ff is increasing and concave. This is useful for Vendi Score, IIC, among other things.

The method uses an nystrom approximation followed a Block Lanczos-QF. The primary benefit of this method is that it is highly efficient in the number of required matrix vector multiplies. Experimentally the method does appear to work very efficiently on the tasks considered

Critical strengths

The method seems to work well, it is definitely something that is used regularly in AI/ML/ signal processing. A computation saving like this one is always nice. The mathematical analysis is also good, the method isn't ad-hoc

Critical weaknesses

I'm not sure that this is a great fit topically. Its a nice result but it seems a bit peripheral to current AI/ML reserach, especially for ICLR. This seems like a much better fit to a journal more closely aligned to numerical linear algebra or signal processing. where this sort of stuff is much more salient. Along these lines I think the work isn't really written in a way that is appropriate for the ICLR audience. It should be mentioned that A is understood to be symmetric, it should be clear that f(A)=Udiag[f(λ1),…,f(λm)]UTf(A) = U diag [f(\lambda_1),\ldots, f(\lambda _m)]U^T. Its really hard to see why, if UΛUT≈AU\Lambda U^T \approx A is available, then why doesn't f(\Lambda)$ itself give a good approximation. A lot of this paper is going to be pretty incomprehensible to ICLR people. What is Hutch++, what is Krylov?

The related work is extremely thin.

clear error on line 327

The "equation (5)"s on page 6 should say "equation (4)" im fairly certain

Questions for authors
  • Is this approximation something that could be easily derivated through? can it be used for optimization or is it just a fast evaluator
  • why is $tr f (\Lambda) $ itself not a good estimator
  • whats with the head mid and correction terms?
1 comment
AuthorsOpenReview ↗

Response to Reviewer r1EG

Thank you for taking a close read of our article, and we are glad that our method "work[s] well" and that the problem we solve "is definitely something that is used regularly in AI/ML/ signal processing."

We appreciate your concerns about the topical relevance of our article. Spectral sum computations are important and arise in many ML workflows. We feel there is a general understanding that ML venues adopt a somewhat broad view of what articles are considered relevant to ML. For instance, at the end of this message, we have included several examples of articles about matrix algorithms published at top ML venues, including several published at ICLR [DFL+25, MMM+22], and several about Krylov methods and trace estimation [ACG+24, PC21, WPH+22, CTU21]. We hope this clarifies why we feel that our article is well-aligned with the interests of the ICLR community.

We also appreciate the notes on the writing, and have full overhauled the related work section.

In response to your questions:

  1. While it is not clear that we can differentiate through the accelerated funNystrom++ method, we can use accelerated funNystrom++ when computing derivatives. For instance, the derivative of the log-likelihood of a Gaussian process with respect to observation noise requires computing the spectral sum tr(A−1)tr(A^{-1}).

  2. The estimate tr(f(Λ))tr(f(\Lambda)) approximates a sum over all nn eigenvalues by only looking at the kk largest eigenvalues. Unless AA is nearly rank-kk, the estimate tr(f(Λ))tr(f(\Lambda)) will not perform well. This is essentially the ``subspace projection'' method in Figure 1 of this paper link, which performs poorly.

  3. In section 3.5, we give a final formula for the accelerated funNystrom++ method, decomposed as

tr⁡^fN++=tr⁡(f(Λ))⏟head+1ℓtr⁡^BL(A,S,f,t(ε,f,A))⏟mid−1ℓtr⁡(S⊤Uf(Λ)U⊤S)⏟correction.\widehat{\operatorname{tr}}_{fN++} = \underbrace{\operatorname{tr}(f(\Lambda))}_{head} + \underbrace{\frac1\ell \widehat{\operatorname{tr}}_{BL}(A, S, f, t_{(\varepsilon,f,A)})}_{mid} - \underbrace{\frac1\ell \operatorname{tr}(S^\top U f (\Lambda)U^\top S)}_{correction}.

The first term is the "head", as it approximates the contribution of the k largest eigenvalues. The second term is the "mid", as it approximates the full tr(f(A))tr(f(A)). The sum of these two quantities would double-count the eigenvalues collected by the head. The third term is the "correction", which corrects for this double counting. We will have updated the text to have a clearer linking between section 3.5 and the names used in Algorithm 1.


[DFL+25]: Matrix Product Sketching via Coordinated Sampling, ICLR 2025

[ACG+24]: Nearly Optimal Approximation of Matrix Functions by the Lanczos Method, NeurIPS 2024

[MMM+22]: Fast regression for structured inputs, ICLR 2022

[CTU21]: Analysis of stochastic Lanczos quadrature for spectrum approximation, ICML 2021

[PC21]: Dynamic trace estimation, NeurIPS 2021

[CTU21]: Analysis of stochastic Lanczos quadrature for spectrum approximation, ICML2021

[BBG+23]: Block Subsampled Randomized Hadamard Transform for Nyström Approximation on Distributed Architectures, ICML 2023

[WPH+22]: Preconditioning for Scalable Gaussian Process Hyperparameter Optimization, ICML 2022

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.