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 manuscript proposes a methodology to speed up structured kernel interpolation Gaussian processes by using a grid with  a number of grid points that does not scale exponentially in the number of data dimension. The sparse grid approach is borrowed from computational mathematics and used to render Gaussian processes more scalable. A number of experiments on datasets with d>>4 illustrates the potential of the method.
strengths_and_weaknesses: 1) Clarity
The paper is well written. The notation language and figures are concise and well accessible.
Two typos: Line 85: scalibility, Line 287: Sentence needs to be revised.

2) Originality
The proposed (thinner) grid seems to not have been applied to scalable Gaussian process inference.

3) Significance
The method is a proper extension of SKI and is not specific to a particular covariance or likelihood function and can be used in a wide range of inference schemes. As demonstrated in the experiments, SKI is applicable to moderate dimensions up to 10 which was previously challenging.

4) Reproducibility
As the code for the experiments is available on https://anonymous.4open.science/r/skisg-485E/README.md, the results should be simple to reproduce. I'm assuming that the code will be shared at a more accessible location upon acceptance.

5) Empirical analysis
The experimental section reports a number of results on runtime and memory footprint and demonstrates the utility of the method.
questions: * The grid point density is not evenly distributed over the input space. Does this imply a preprocessing to the data to concentrate the relevant parts close to the coordinate axis where the density is higher?
* In Figure 1, you could align the color of the complexity panel and the grid visualisation panels.
* The term "nearly linear" should be properly defined or changed.
limitations: Yes.
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 manuscript proposes using sparse grids within the structured kernel interpolation framework to accelerate matrix vector products necessary when working with a kernelized Gaussian Process. Of particular note, sparse grids are preferable relative to dense grids as the dimension of the problem increases. A fast algorithm is provided for computing matrix vector products with the sparse grid based inducing point matrix and appropriate interpolation schemes are discussed. Finally, numerical results show the efficacy of the method for both synthetic and real world benchmark problems.
strengths_and_weaknesses: Overall, I think that this paper makes a good contribution to the SKI framework. While sparse grids are certainly a well-studied and developed area, to the best of my knowledge they have not found use in this setting. Moreover, the development of a fast algorithm for applying the resulting inducing point matrix is key for this application. Accordingly, the idea + algorithm development represents a clear strength of the manuscript. Moreover, the exposition is relatively easy to read and the key points are well explained.

The main weakness of the paper is in its experimental evaluation of the method. Some of this may be relatively easy to address by clarifying certain details (see some specific questions below). Nevertheless, there are a few larger issues outlined below: 

- The main focus of the paper seems to be on the efficiency of all parts of the SKI pipeline (i.e., both the inducing point matrix vector product and the interpolation). However, the most "comparative" experiment (table 1) simply looks at RMSE and comes off a bit as: "all these methods do reasonable in most cases and no one dominates the rest." While this is fine for showing the final result of the proposed method is comparable with other work, it does little to highlight the advantages (and/or potential disadvantages) of the proposed method relative to prior work. While there is a very small comparison in the appendix, given the focus of the paper it seems that balanced the numerical experiences more towards exploring the computational efficiency of the method would be preferable. For example, is the proposed method uniformly preferable? or when in say $d=2$ or $d=3$ does the practical efficacy of the FFT help dense grid methods win out? Where might one see the crossover to sparse grids being preferable? and more. Ideally the numerical experiments could help practitioners understand which method should be used in which settings (at least to a first approximation). 

- The manuscript would benefit from a more clear breakdown between the interpolation time and the inducing point matrix multiplication. For example, which one is the dominant cost? This would help direct future work and also make it easier to evaluate the limitations where the manuscript suggests improvements to the interpolation are important (suggesting that this ends up being the dominant cost).

In summary, there is a clear algorithmic contribution in the manuscript that suggests the possibility of a practically efficient method in slightly larger dimensions than SKI is typically used (though there are still limits). Moreover, it seems likely that these idealized gains translate to practical improvements over prior methods. However, the experimental evaluation makes assessing the latter point somewhat challenging and the manuscript would benefit significantly by making a clearer case here.

Assorted notes:

- The definition of $V_i$ could be made a bit more clear; maybe a figure or more precise mathematical statement in the appendix?

- The fact that certain base case operations in Algorithm 1 are Topelitz and, therefore, can be accelerated using the FFT should probably be mentioned in the main text discussion of Algorithm 1. It is clear in the appendix, but important enough to warrant inclusion above.

- The authors note that SKI is typically infeasible for $d \geq 4$ and then immediately proceed to run a variant of SKI in higher dimensions. I think it is better to stick to the more general "scaling" arguments rather than trying to draw somewhat arbitrary boundaries between methods based on the dimension.

- Proposition 2 is styled different than the other theoretical statements (e.g., Proposition 1 and Theorem 1). While either is fine, the styling should be consistent.

- The related work section focuses mainly on SKI type methods. While that being the focus is certainly appropriate given the contribution of this manuscript, given that the problem being solved is GPs and not "improve SKI" the manuscript may want to allude to the fact that there are other "styles" of algorithms that are also being developed to try and scale to larger dimensions (though they all certainly have their own limitations and pros/cons relative to SKI). For example, one common strategy is the use of rank-structured factorizations (as with SKI these are most effective for $d\leq 3$ but there has been work on "scaling up" to more moderate dimensions:

[Yang, Changjiang, Ramani Duraiswami, Nail A. Gumerov, and Larry Davis. "Improved fast gauss transform and efficient kernel density estimation." In Computer Vision, IEEE International Conference on, vol. 2, pp. 464-464. IEEE Computer Society, 2003.]

[Ambikasaran, Sivaram, Daniel Foreman-Mackey, Leslie Greengard, David W. Hogg, and Michael O’Neil. "Fast direct methods for Gaussian processes." IEEE transactions on pattern analysis and machine intelligence 38, no. 2 (2015): 252-265.]

[Ryan, John P., Sebastian E. Ament, Carla P. Gomes, and Anil Damle. "The fast kernel transform." In International Conference on Artificial Intelligence and Statistics, pp. 11669-11690. PMLR, 2022.]

- It seems ref 24 is a duplicate of 23? I believe this is just one paper from 2005 unless there is another reference I am unfamiliar with that is meant by the second appearance.
questions: - Is the plot in figure 1 (c) meant to show arithmetic operations or is this an actual timing experiment? "Complexity" is not a particularly descriptive y-axis. The statement "improves" suggests this is an actual experiment, but "complexity" suggests this is simply flop counting.

- Why are $\bar{\mathbf{a}}_i$ and $\bar{\mathbf{b}}_i$ lower case when they represent matrices? Also, maybe it would be clearer to make the recursive calls more closely match the algorithm input/output definition (technically, they can be fit into it by just calling the algorithm several times, but it does read a bit oddly given the input statement).

- Is there an explanation for the high variance in certain data points of Figure 2?

- Is Figure 2 showing the total MVM time or just the part with the kernel matrix (i.e., only Algorithm 1)? the text suggests this is an evaluation of Algorithm 1 and, therefore only $K$ is considered. However, by showing CG time the manuscript suggests it is the whole process including the interpolation matrices.

- In figure 3 what is the dense grid size? is it made to match the total number of points in the sparse grid or does each dimension match the maximum resolution. The results suggest the former (since the sparse grid interpolation is doing better), but this should be made clear.

- Is there a good explanation for why the sparse (simplicial) interpolation seems to be improving more slowly than simplicial interpolation using the dense grid?
limitations: - One limitation not discussed is the need to choose $\ell.$ While not dissimilar to parameters that appear in related methods (so I don't think this is a problem, per se), the manuscript does not provide much guidance on how select this parameter based on, e.g., the desired accuracy and that is a current limitation.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This study presents a way to improve the scalability of Structured kernel interpolation (SKI) for high dimensional dataset.  Specifically,  authors introduce the sparse grid inputs for constructing the inducing kernel Gram matrix $K_{G}$  in approximate kernel $W^{T}K_{G}W$. To use the sparse grid for SKI, they propose the MVM algorithm for the introduced sparse grid to have the near-linear computation for MVM, and the interpolation scheme for computing the $W$ (sparse weight). In this procedure, authors describe the properties of sparse grid and explain how the computational cost induced from sparse grid inputs could be much smaller compared to that of regular grid for SKI. 
Through experiments, authors validate that using the sparse grid with the proposed schemes is computationally efficient while obtaining the comparable prediction performance.
strengths_and_weaknesses: $\textbf{Strengths}$

The existing SKI framework has been the scalable issue for high dimensional dataset, because the computational cost of MVM for the regular grid is $O(N4^{d} + |U| \log{|U|})$, and this implies that high dimensional data set (large $d$) increases the computational cost exponentially, and thus incurs the computational issue for employing the SKI. This work alleviates this scalable issue by inducing the sparse grid, and then proposing the corresponding MVM for sparse grid inputs. Since the introducing the sparse grids in the naïve manner does not result in the improvement of the computational cost as shown in Figure 1.(c), I think that making the near-linear computation for MVM computation with sparse grid is a quite novel part of this work.

$\textbf{Weaknesses}$

Although this work proposes a novel inference scheme for overcoming the issue of SKI, I think that the validation procedures of the proposed method in the experiment section is not sophisticated, and seems to a little bit weak to validate the generalization of the proposed work on a variety of dataset, as comparing the experiments validating the existing variants of SKI.
For further details, see Section Limitations below.


questions: $\bullet $  Q1. For the scalable GP inference for high dimensional dataset, combining the random Fourier feature with fast food tricks enables the efficient inference in [1].  For the results in table 1, I am quite curious whether the proposed SKI framework could be comparable to other scalable GP inference scheme.

[1] A la Carte – Learning Fast Kernels, AISTATS 15

limitations: I think that if the validation procedure in experimental section is improved, this work could get a better evaluation.
Thus, I write some concerns about experiment section and some suggestions.

$\bullet $ For the experiment on synthetic dataset of $\cos({\vert{x}\vert}_{1})$, it seems that the more accurately the kernel is approximated in left figure ($d=6$), the more accurately it seems to predict in right figure ($d=6$). However, what if synthetic set are generated from different process, I am curious whether the effectiveness of sparse grid still remains (for generalization on a variety of datasets). If possible, what about applying the same experiment on some of the UCI datasets used in Table1?  If authors show the consistent results from the high dimensional UCI datasets, this method will be regarded as more powerful.

$\bullet $ For the UCI regression task, Table 1 does not report the standard deviation of the Test RMSE for 3 trials. Thus, I am not sure whether the proposed scheme results in stable training and prediction performance.  Also, for evaluating the GP regression task, it would be better to report the test negative log likelihood (nll), which is the widely used metric for GP regression task, as done [1].

$\bullet $ For regression task, comparing the training progress (xaxis: training time, yaxis: test rmse ) over varying number of sparse grid points $|\mathcal{G}|$  would be better to make sure that the sparse grid results in fast training for high dimensional dataset due to the reduced computational cost as shown in Figure 2 of [2].


[1] SKIing on Simplices: Kernel Interpolation on the Permutohedral Lattice for Scalable Gaussian Processes, ICML 21

[2] Product Kernel Interpolation for Scalable Gaussian Processes, AISTAST18
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper uses sparse grids in structured kernel interpolation (SKI), which speeds up Gaussian process inference by replacing the kernal matrix with a kernel matrix evaluated at a structured set of points. In sparse grids the number of points grows faster with the dimension than in full grids typically used in SKI.

The two main contributions of the paper are (1) linear time algorithm for multiplying sparse grid kernel matrices with vectors that can be used in solving linear systems arising in GP inference via the conjugate gradient algorithm and (2) a simplicial interpolation scheme for approximating the full kernel matrix.

strengths_and_weaknesses: Although the idea of replacing full grids with sparse grids is quite obvious and it is rather well known that, as opposed to orders of magnitudes more or something like that, one gains only a few extra dimensions with sparse grids (I appreciate that the paper does not attempt to hide this fact as is evident from line 80 and 272-273), I find this paper a very nice and useful contribution for the field. The paper is very well written and pleasant to read. 
questions: Which class of kernels does the method apply to? Scattered remarks in the main paper and supplement seem to indicate that the kernel should be a product of one-dimensional stationary kernels but this is not made clear anywhere. In either Section 2 or 3 the reader should be explicitly told which kernels are considered in the paper.
limitations: One of the main limitations of the work is that although sparse grids are an improvement over full grids in this regard, the dimension that one can work in still remains fairly low (at most ten in this paper, I think). The authors are sufficiently upfront about this issue.
review_title: null

Meta-review: metareview: All reviewers found this paper relevant for the conference, original, and well written. All four reviewers recommended accepting the paper. For the camera-ready, please go through the reviewer comments in detail and check that you have addressed the remaining concerns regarding clarity and improving presentation.

For the camera-ready version, you also need to fix the font issue in your paper. In the current version, the font/text size is not what it should be (most likely due to some package clash).
confidence: Certain
Decision: Accept