Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper proposes a novel algorithm to approximate kernel matrix-vector multiplication (KMVM), for large kernels and data of dimension less than or equal to 7. Experiments and theoretical analysis suggest the algorithm has linear time and memory complexity. Since KMVM is a key component of other algorithms like conjugate gradients, the authors show their algorithm can be combined with existing large-scale kernel methods and demonstrate significant speed ups.
strengths_and_weaknesses: Strengths
- The limitations of the method are clearly discussed.
- The paper makes a strong contribution with a nice algorithmic advance and a technically challenging implementation on GPU.
- All the main claims of the paper are thoroughly supported by experiments, including an ablation study. Overall a high quality paper.

Weaknesses
- The algorithm is limited to low-dimensional data, which might hamper the paper's significance in the NeurIPS community. However, this limitation is clearly acknowledged and discussed.
- I found some sections of the paper hard to follow, particularly Section 4.2, but this may be because I'm not familiar with some of the prior work the paper builds on.

questions: - Maybe mention that $D$ is the dimension of the data in the first paragraph where it is introduced.
- Are there any assumptions on the type of kernel F$^3$M is useful for? It seems like most experiments were performed on RBF kernels.
- Line 143 should $u_1$ and $u_2$ be $v_1$ and $v_2$?
- Can the authors include more detail in Section 4.1 on the low-level GPU optimizations performed in the main text?
limitations: No concerns about negative societal impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper considers speeding up the matrix-vector multiplication operation in kernel methods for a specific structure (tall and skin) of the kernel matrix. The approximation method builds on the FFM algorithm, which separates data points into far-field and near-field interactions and Lagrange interpolation. The proposed schemes are further implemented on GPUs to exploit their parallel processing power; various speed-ups can be observed compared to the FFM method.
strengths_and_weaknesses: The methods contain several levels of approximation and heuristics, with many hyperparameters to be tuned. It is not clear how sensitive these methods are to these parameters. How to best select them for a given dataset?

The paper is densely packed with approximations and notations, which make it quite difficult to follow at some points. 
In Section 4.1, the authors repeatedly mentioned **we used non-trivial method...** without any guidance. Please consider updating it. Some parameters are used for a different meaning, e.g., the vector **v** in Line 143 and Line 144.
questions: The last two items in Table 1 are quite strange as runtime depends on the hardware. What does that mean by running under a minute or an hour?

It seems that the F3 method is specific to the Gaussian kernel in Section 4.3? It is not clear how the methods depend on hyperparameters when the data set is changed. For example, the suggested parameters in Line 250 are based solely on Figure 7, which may not generalize to new data sets.

Theorem 2 is hard to understand, it needs more discussion. It is not clear how large the different terms (with negative signs) are, relative to the first term in the complexity bound. 
limitations: see above
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper presents a fast matrix vector multiplication for skinny matrices.

strengths_and_weaknesses: Strong Points
----
1. This paper targets to solve a well-motivated and important problem.
2. Related work is clearly discussed.
3. The empirical results substantially outperform baselines.

Weak Points
---
1. The V100 used in the experiments supports tensor cores. I suggest the authors include a discussion of whether tensor cores may be utilized in F^3M.
2. The GPU utilization of the proposed algorithm is relatively low to the full capacity of V100. I wonder whether the authors could add a discussion of the reason and how to improve the utilization.

Presentation
----
The upper part of Figure 5 is incomplete. And the text is too small for readers.

questions: 1. Is it possible to use tensor cores in the proposed algorithm?
2. How to improve the FLOP efficiency?
limitations: As the authors claim, the major limitation of the proposed algorithm is the restriction of the dimension (D <= 7).
Although it may limit the usage, many relational tabular data fit the constraint.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper tries to accelerate the fundamental problem of kernel matrix-vector multiplication (KMVM) operation. The authors propose F^{2.5}M and which is built on classical FFM and specially designed for GPU parallelization. Then they introduce the main algorithm F^{3}M to further accelerate the computation speed. The experiments show that compared with CPU and GPU baselines the new proposed algorithm uses less memory and has a faster speed while controlling the error in an acceptable range.
strengths_and_weaknesses: This paper tries to solve the fundamental problem of high memory usage and low speed in large-scale KMVM operations. The writing is clear and the motivation is well-driven. The algorithm is straightforward but seems effective according to the experiment results. The figures in the attachment materials show clearly how the algorithm utilizes the GPU parallelization attribute.
Minor:
Pictures need to be replaced with vector graphics to improve clarity.
questions: I would like to to see some ablation studies and experiments on F^{2.5}M.
limitations: N/A
review_title: null

Meta-review: metareview: The authors propose an new approximation procedure for Kernel matrix-vector multiplication target to tall and skinny kernel matrices. The proposed method achieves significant speedups over the state-of-the-art GPU-based linear solver FALKON while sacrificing only small drops in accuracy due to approximation.

The paper discusses a specific use case (low dimensional data) but it is very clear about the scope. The reviewers agree that the problem still has high significance, is well motivated and the reported performance gains are convincing. The experiments also provide interesting insights into the inner working of the method and the trade-offs between accuracy and efficiency.

For a potential camera ready version the authors should carefully work in the reviewers' comments on the presentation to improve the accessibility of their work for a general NeurIPS audience. Also additional details about the low-level GPU optimizations would be good to add in section 4.1 and some comments on how to extend the method to other kernel functions would strengthen the paper.
confidence: Less certain
Decision: Accept