- Rating
- 1
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
In this paper, the authors observe that kernel matrix is too large to be stored or computed. Therefore, they propose to adopt a matrix-free method to avoid storing the whole matrix. However, since the authors do not provide clear experimental evaluation and methodology discussion, I cannot understand how this method can advance the state of the art.
Critical strengths
S1: Storing kernel matrix is definitely the bottleneck in many tasks of kernel methods. This has also been studied extensively in the literature.
S2: It sounds interesting to avoid storing the kernel matrix in the machine learning tasks because this approach can potentially avoid the time and space.
Critical weaknesses
W1: The authors do not provide the clear problem definition for what they want to solve. Do they want to optimize the time or space (or both)? Which task do they intend to handle? Without clear definition, I cannot understand this paper.
W2: To my understanding, I can only see that the authors only demonstrate the performance of their methods. No competitor has been provided for comparison.
W3: There is a lack of experimental comparison in this work. Many kernel matrix compression techniques and feature approximation techniques have been proposed in the literature. Howeer, the authors do not have any comparison in the experimental evaluation. Therefore, I cannot judge whether it can really advance the state of the art.
W4: I do not know how this method can be applied to some machine learning task. I think the authors should provide some case studies for illustration.
Questions for authors
Q1: What is the optimization objective of this work? (Reducing the time/space or both.)
Q2: Is there any formal problem definition?
Q3: Can kernel matrix compression/feature approximation methods be used as competitors?
Q4: Can the authors provide the case study to illustrate whether the proposed method can be adopted in some machine learning tasks?
2 comments
Reply to the comment
I have read the rebuttal. However, I still think the authors do not address (or partially address) my comments. As an example, they still do not provide any new experimental results related to W3. As another example, the reply is too brief related to my comment regarding the case studies (W4). Therefore, I do not change the scores.
We thank the reviewer for their time and for the clear, direct questions. We agree with the central criticism: the original submission did not state its problem, its competitors or its applications clearly enough.
W1: The authors do not provide the clear problem definition for what they want to solve.
We agree that the original submission did not state the problem clearly. The revised introduction (§1) now does so explicitly. We quote the relevant passages here.:
In summary. in kernel methods we need to solve the bandwidth β>0 (solved by beta-flow) and large N datasets (this is O(N^2) in space (which we solve matrix-free tech.) and O(N^2) in time (solved by using GPUs). caution is its easy to cheat small \beta\to0 implies easy to solve (not our objective).
W2: To my understanding, I can only see that the authors only demonstrate the performance of their methods. No competitor has been provided for comparison.
We (in appendix) compared our matrix-free primitive XGEMM to KeOPs, both methods were on par. Now we also have, a brute-force full-N scan in §2.1 as a reference to the ladder is evaluated against in Table 1.
$\color{red}{\text{W3: There is a lack of experimental comparison in this work. Many kernel matrix compression techniques and feature approximation techniques have been proposed in the literature. Howeer, the authors do not have any comparison in the experimental evaluation. Therefore, I cannot judge whether it can really advance the state of the art.}}$
We agree that the paper should make this comparison explicit. These methods target a different regime from ours, and the revision explains why (§1, App.A).
Low-rank methods (Nyström, RFF) are accurate at small β, but resolving many harmonics requires large β, where the kernel is high-rank and compression discards the higher modes (§1). Our ladder uses Nyström only to warm-start each rung; the final solve is exact.
kNN/ANN methods do not provide a true comparison for reasons listed in (App.A).
Existing scalable kernel solvers (KeOps, EigenPro) leave β to the user; GP frameworks (GPyTorch, gp2Scale) do learn it, but by marginal likelihood, which requires labels. We know of no scalable method that selects β without supervision, so our comparisons are against the same exact operator: KeOps for evaluation (App.B; comparable timings, agreement to ∼10−6 in fp32), and a brute-force scan of 240 bandwidths at full N for the ladder (\S2.1, Table~1). We will add a quantitative comparison against Nyström and random features in the final version.
W4: I do not know how this method can be applied to some machine learning task. I think the authors should provide some case studies for illustration.
Our primary experiment in the past and current work was Alanine-Dipeptide for use in Molecular Dynamics (MD) simulations. Dynamical systems more generally, finding exact harmonics on empirical data.
Q1: What is the optimization objective of this work? (Reducing the time/space or both.)
Eq. 1 and 2 of the revised work.
Q2: Is there any formal problem definition?
Our objective is to find the "best" harmonics of a kernel matrix. We define "best" as given: X⊂RD and α, find β⋆, the largest-β local maximum of E(β) before the graph fissions. The leading k eigenpairs of Pα,β⋆ satisfying ∥Pψj−λjψj∥2≤ε, using O(ND+Nk) memory and no approximation of the kernel.
Q3: Can kernel matrix compression/feature approximation methods be used as competitors?
Yes. Low-rank methods are accurate at small β, and our ladder in fact uses the Nystr"om extension to warm-start each rung; but at the β⋆ needed to resolve many harmonics the kernel is high-rank, so we keep the exact operator for the final solve (\S1, App.~A).
Q4: Can the authors provide the case study to illustrate whether the proposed method can be adopted in some machine learning tasks?
See W4.