Venue: NeurIPS 2022 Conference

Reviews:

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 manuscript proposes a GP covariance function to model multivariate piecewise constant functions so that computationally efficient inference and prediction becomes possible. The authors propose numerical primitives to compute matrix-vector multiplications, the inverse and log-determinant of the system matrix that scale linearly in the number of datapoints, the input dimension of the data and the inverse stepsize of the grid underlying the piecewise constant function both in terms of runtime and space. 
strengths_and_weaknesses: 1) Clarity
The paper is mostly well written and the technical content is rather well accessible. The Algorithms 1+2 and would become simpler if consistent vector algebra was used instead of loops over indices.

2) Originality
The proposed covariance function and the derived algorithmical approaches seem to not have been explored before.

3) Significance
The method is (currently) specific to GP regression and could extend the range of GP models to high-dimensional data whenever piecewise constant functions and rank-deficient covariances are appropriate.

4) Reproducibility
As the code to run the experiments is included in the submission and the datasets are public, it should be rather simple to reproduce the results.

5) Empirical analysis
The manuscript contains a large number of numerical results gathered in a big table regarding marginal likelihood, prediction error and runtime. Some more results on more subtle aspects of the covariance function itsel would have been much appreciated.
questions: * The piecewise constant nature of the modeled function should be emphasized more clearly.
* The space/time footprint of the algorithms depends linearly (derivative of hyperparameters quadratically) on the data dimension and the stepsize of the underlying grid. This information should be presented more prominently.
* Also, the fact that the covariance is degenerate (low-dimensional) could be made more accessible.
* Given that in line 29, the manuscript puts a lot of emphasis on the variance estimate of inducing point methods, I would have expected a detailed comparison of the predictive variance of the proposed (degenerate) covariance with an exact GP with non-degenerate covariance and an inducing point method approximation.
* Can the numerical algorithms be cast such that also non-Gaussian likelihoods can be treated via expectation propagation, variational Bayes or Laplace approximation?
* An analysis, why "better [..] likelihoods" were achieved could be instructive. In particular, how does the likelihood depend on q? How are hyperparameters optimised
* There is no comparison to the exact model in terms of modeling accuracy.
limitations: Yes
review_title: null

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 develops a novel binary tree kernel function for fast Gaussian process computation. The kernel is based on the similarity of permuted bit strings of the two input features, which induces a kernel matrix with a sparse rank one sum representation. The computational gain is achieved by efficient algorithms for matrix inversion and matrix-vector multiplication. 
strengths_and_weaknesses: Strength:
* Instead of approximating a kernel matrix (or its inverse), the paper presents a novel idea of constructing a kernel with a computationally favorable structure.
* The proposed sparse rank one sum representation and algorithms could be applicable to other settings.
* The method is nicely illustrated.

Weakness (see major comments below for details):
* Unclear performance in low-dimensional settings.
* Training time complexity appears to be $O(n\log{n})$ instead of $O(n)$.
* The paper could benefit from additional experiment results.
questions: Major comments:

1. As far as I understand, for any given bit permutation, $||x_1^{raw} - x_2^{raw}||_2 \rightarrow 0$ does not imply $k_w(x_1, x_2) \rightarrow ||w||_1$, where $x_1^{raw}, x_2^{raw} \in \mathbb{R}^d$ are the raw features, and $x_1, x_2 \in \mathbb{R}^q$ are their bit representation. However, in some low-dimensional problems such as spatial applications, it makes sense that data with two closer features (in terms of Euclidean distance) have stronger correlation, which cannot be captured by the proposed kernel. I am curious how the proposed method would perform in such scenarios. 

2. It appears to me that after the bit permutation is updated during model training, we need to re-sort the bit feature matrix $X$ to obtain a new $P$. Does this mean the actual training time complexity is $O(n\log{n})$ instead of $O(n)$?

3. The proposed kernel seems to be highly nonstationary in nature, which could be one of the reasons why it outperforms the standard stationary Mat\'ern model in real applications where the stationarity assumption does not make sense. It would be interesting to see how it compares with other nonstationary GP models such as Zhang \& Williamson (2019) and Trapp et al. (2020).

4. I think the high-dimensional kernel parameter $\theta$ could be somewhat hard to learn. How sensitive is the performance to the initial values of $\theta$? Also, the performance of BT is based on multiple initializations, which may not be fair to other competing methods.


Minor comments:

* Could you please elaborate more on why the matrix inversion algorithm is called "approximate" inversion?
* Figure 2: Are those piecewise constant functions the posterior means of binary tree kernel GPs? I think a realization from the proposed GP should be piecewise smooth rather than piecewise constant.


References:

Trapp, M., Peharz, R., Pernkopf, F., \& Rasmussen, C. E. (2020). Deep structured mixtures of gaussian processes. In International Conference on Artificial Intelligence and Statistics (pp. 2251-2261). PMLR.

Zhang, M. M., \& Williamson, S. A. (2019). Embarrassingly parallel inference for Gaussian processes. Journal of Machine Learning Research.
limitations: Please see the major comments 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: 
In this paper, the authors propose a binary tree-based kernel for Gaussian Process acceleration.  The proposed kernel enables a fast computation of the negative log-likelihood in $O(nq)$ time.
strengths_and_weaknesses: 
Pros.
1.  The proposed binary tree-based kernel enables a fast (approximate) compuation of  $(K_{X,X} + \lambda I)^{-1}$ and $|K_{X,X} + \lambda I |$, which is important for GP accelration.

2.  The fast computation algorithm (Algorithm 1) may be potential for acceleration in other tasks relying on the binary tree-based features.



Cons.
1.  The time complexity of Algorithm 2 may be up to $O(2^q)$.
 From Eq.(3),  the number of $s \in \mathbb{B}^r$ is $2^r$, and it can be up to $2^q$. As a result, the number of partitions can be as 
large as $2^q$. The time complexity of the  for loop in step 7 in Algorithm 2  is then up to $O(2^q)$. This can be much larger than $O(nq)$. 
Note that $q=dp$,  $O(2^q)$ is quite large.

2. The authors argue that inducing points-based GP acceleration is less competitive. However,  in the experiments,  a detailed comparison with strong inducing points-based methods is missing.   It is unconvinced to support the claim.

3. Some symbols are confusing. 
(1). the index $i$ in $(X_{[s]})_i$ confuse with the index in $w_i$ in  Eq.(3).
(2). The $\boldsymbol{i}$ in step 8 in Algorithm 2 is not defined or used in Algorithm 2. 
(3).  $m$ in Line 237-251 is confused with the number of partitions in Definition 2 in Line 120.

questions: 
1. Could the authors explain more about the time complexity regarding the above concern?

2. It is better to provide a detailed comparison with a strong inducing pionts-based GP (Kapoor et al. 2021) for better evaluation.


Kapoor et al. SKIing on Simplices: Kernel Interpolation on the Permutohedral Lattice for Scalable Gaussian Processes. ICML 2021.
limitations: NA
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 discusses a new type of kernel for Gaussian process regression based on binary-tree partitions of the input space. The structure of the kernel allows for a fast (linear time) inversion of the kernel matrix which is benefitable for large datasets. The Gaussian process with this kernel gives piecewise-constant predictions.
strengths_and_weaknesses: *Originality*. The work is original. It is somewhat similar in nature to works related to Random Forest kernels but I am not aware of other work based on bit representations of the input data.

*Clarity*. One area where the paper could use improvement is the clarity, especially notation-wise. It is quite hard to read the heavy-weight superscripts throughout the proof of the theorem 1 in particular. It seems like there is a typo on the line 178: missing \prime? There is also some notation inconsistencies like using the same letters $i$, $j$, $k$ with a different meaning in similar contexts. Also it seems like the proof of the Theorem 1 in the main paper is in between a high-level sketch and a precise mathematical formulation which makes it harder to read. Could be benefitial if the proof outlined a high-level sketch with the details hidden in the supplement.

*Quality*. The quality of research is high. The authors provided proofs of the mathematical statements they make. The authors have also made empirical performance comparison against popular GP kernels, such as Matern or SVGP method. The authors have provided a review of a related and competing methods of scaling up GP regression. An interesting thing would be to compare their method to other partition-based methods, such as a Random Forest Kernel.

The authors claim that their kernel widely outperforms other methods such as exact regression with a Matern kernel or a sparse GP regression. However, as presented in the Table 1, this is perhaps an overstatement. In particular, Matern kernel beats the BT(E) for moderately-sized datasets both in test RMSE and computational speed, and in terms of the test NLL, it is not a clear cut that a BT kernel is ultimately a better choice.

It would be also interesting to see some ablation studies regarding the choice of the bit precision and the noise variance $\lambda$. 

*Significance*. The work provides a new type of kernel that could be used in setttings where a piecewise-constant predictions are suitable. The authors provide an algorithm for a computationally-easy inversion of the (noised) covariance matrix. Since GP regression is notoriously heavy on the computational side, the new method to speed it up is a significant contribution.

questions: Since the authors claim the superioirity of their kernel over other methods of scaling up GP regression, it is interesting how the experiments were carried out.
In specific, it is known that a Matern kernel performance depends on the choice of the smoothness parameter. How did you choose this parameter in your experiments?

It is also interesting how did you choose the $\lambda$ parameter of your kernel (which is basically noise level)? Is it possible to train this parameter along with the order and weights?

Also an interesting thing is how does the choice of the precision $p$ affect the performance? In particular, since the train time scales quadratically with the precision. How did you come up with the precision in the experiments and is it possible to automatically train the precision? Does it makes sense to ensemble over not only different bit orders but also over different precisions?

It would be nice to see some comparision ageints other partition-based methods like Random Forest Kernel.

limitations: Authors have clearly stated the limitations of their work. The predictions provided with a GP with binary-tree kernel are piecewise-constant. That makes the kernel unusable in Bayesian Optimization. It would be nice to discuss limitations of the choise of the precision level $p$ and noise level $\lambda$.
review_title: null

Meta-review: metareview: Overall, reviews on this paper are positive. The paper presents a novel binary-tree based kernel which yields a structured kernel matrix that allows for near linear time GP inference. The approach is interesting theoretically and effective in practice. It is a valuable alternative to inducing point methods or other approaches that start with a standard kernel and then speed up inference via kernel matrix approximation.

The reviewers have made several suggestions to improve the presentation and empirical evaluation that I hope the authors will incorporate in the final version. Two important points that came up after author-reviewer discussion that I would like to point out are:

1. The matrix structure that arises from the binary tree kernel (which the authors call SROS) is exactly a classic hierarchical matrix structure, with rank-1 blocks. See e.g., https://www.mis.mpg.de/scicomp/Fulltext/WS_HMatrices.pdf. These matrices are extremely well studied in scientific computing, and it is well known that they admit fast linear system solvers, etc. it is surprising that the authors don't make a connection here -- presumably they are not aware of the prior literature. We feel that adding a discussion of the connection to hierarchical matrices is critical for the camera ready version. This would include a discussion of how the algorithms presented in the paper relate to existing algorithms for these matrices. 

2. The discussion of 'recall' in the introduction needs a significant overhaul or needs to be removed. In particular, this discussion is not backed up with any evidence or any citations. None of the empirical results of the paper address this claimed advantage over inducing point methods. Citations need to be a added to this area of discussion, and empirical results backing it up need to be added. Otherwise, it should be removed from the paper.


Thanks!
confidence: Less certain
Decision: Accept