- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3(+1)
- Soundness
- 2
Read review
Paper summary
The paper estimates spectral sums for a psd matrix and a positive, increasing, concave function , 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- Nyström approximation from a sparse sketch and computes exactly. It then estimates the remainder with Hutchinson probes, applying by block Lanczos of depth .
The key observation is that a Nyström column costs one matvec while a probe costs , and the accuracy only requires . So taking gives matvecs, compared with 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 to , 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 , 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 () the error is about 4–16× lower at the same matvec budget, and on NTK log-determinants () 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 . 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 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 "".
- At L452 the shift should be , not "".
- Cor. 4.2 uses success probability 9/10, while Thm. 3.2 uses 99/100.
- Definition 3.1 uses tolerance , but Thm. 4.1 uses .
- Typos: "Our methods requires", "Lanzos", "enilsted", "these these".
2 comments
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.
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:
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.
As far as we are aware, every method in the prior work has matvec complexity at least O(t/ε), while our method has complexity O(maxt,t/ε). While there is not a matching lower bound of Ω(maxt,t/ε), as we note on page 2, existing results do imply a lower bound of Ω(maxt,1/ε). It is not clear that existing theoretical techniques are capable of proving lower bound that exactly matches our upper bound.
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.
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× faster than the next-best method. If we include the time, our lead grows very mildly to 1.77×. 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)