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: This paper considers the problem of selecting the kernel of a Gaussian process (i.e., the model selection problem), which is one of the hyperparameter optimization problems for Bayesian optimization. 
The authors considered that a kernel function is consisted of a set of "basis" kernels in the space of kernel functions and a number of operations, following the previous (kernel grammer) work of Duvenaud et al.
A kernel grammar can be mapped to a tree that represents it.
For the discrete probability distribution that is a summary of this representation tree, we can define the Wasserstein distance with the indicator function as the cost function. In this case, the Wasserstein distance coincides with the total variation distance. This distance can be used to define a meta kernel function (kernel-kernel) that measures the similarity of two kernel functions on the space of kernel functions. The proposed method uses a Gaussian process with this kernel-kernel as the covariance function, and Bayesian optimization is used to select the kernel model. 
In the experiment, the authors compared and evaluated the model selection performance of the proposed method with existing methods on four types of benchmark data including time series.
strengths_and_weaknesses: strength

- Traditionally, model selection for the kernel function itself has been done manually depending on the problem or by multiple kernel modeling for several candidate kernels. On the other hand, this study performs Bayesian optimization of combinations of kernel components based on the similarity defined between the kernel functions. In this approach, only the base kernel and operation rules need to be prepared, and there is no need to prepare multiple candidate kernel functions as in multiple kernel learning. Bayesian optimization for model selection allows for the "construction" of good kernel functions without human intervention.

- The mapping of kernels to representation trees allows the problem of finding the optimal kernel to be viewed as a problem of finding the optimal tree structure.　

- The proposed method has higher scalability than existing methods (Malkomes et al.) that use Bayesian optimization based on Hellinger distance for the same problem. This is because the Hellinger distance-based method requires an integral calculation on the kernel parameters for kernel-kernel evaluation.

weakness

- In this paper, an indicator function is used for the base distance to describe the Wasserstein distance as a closed-form solution (total variation distance). However, this seems to be a discrete and extreme similarity evaluation that only looks at whether or not the elements that make up the two representation trees match.

- The distance for kernel-kernel (3) itself contains the hyperparameters alpha_1, 2, and 3, so it seems that the hyperparameter tuning for kernel-kernel are going to be harder than for ordinary BO when performing BO on the kernel space.
questions: - The proposed method seems to cover only model selection for the kernel function itself, but if we want to further perform hyperparameter selection for the kernel, can we combine it with conventional methods (e.g., marginal likelihood maximization)?

- Is it possible to approximate the Wasserstein distance and use the proposed method when a general distance that is not an indicator function is used as the base distance?

- Are the hyperparameters alpha_1, 2, and 3 in distance (3) optimized at the same time as the other kernel-kernel hyperparameters? How does this affect performance of the proposed method?
limitations: The authors adequately addressed the limitations and potential negative societal impact of their work.
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: To find the best kernel for a GP, rather than conducting BO with a value function given by a GP comparison in function space, this paper develops a novel way to compare two kernels, based on optimal transport between feature representations of the tree representation of the kernel.
strengths_and_weaknesses: The paper comes up with a good idea for kernel search, inspired I believe from references [10,4] which conduct NAS by BO using OT over the computational graph. Thus the central idea is at hand (structure search by BO using OT over structure distance), though not immediate.
The paper is clearly written. Many details are left to the appendix, but this still seems adequate.
The experimental validation is adequate.
The formalization of the OT metric in sec 3 is justified thoroughly.
Fig 1 is not legible when printed on A4 format.
questions: Given that your method eschews functional distance like in [2], are we sure that it would do well in cases where the true kernel is known? I suppose this can be evaluated on synthetic data. Or is there some weakness here, hidden in the simplicity (both theoretical and computational) of the pairwise evaluation?
How can the OT distance be interpreted? Is there something of interest happening with the multiplicative factors in the total distance eq3 once they get learnt?
limitations: Yes, though section 5 could be made more explicit.
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 proposes a method for kernel selection (search) wherein kernels are built from base kernels using fundamental operations (eg addition, multiplication etc).  Kernels so constructed are represented as trees, allowing their similarity to be evaluated based on their grammar (tree structure and assumptions regarding basic operations, eg their commutativity or otherwise) rather than e.g. distance between GPs.
strengths_and_weaknesses: The construction of the kernel-kernel is thorough and I am persuaded that, while heuristic, this is a good alternative to measuring the difference between GPs or kernels using e.g. L2-norm.  Further, the overall approach of building kernels from base kernels reflects the human (parametric) approach to the problem well.

My main problems with this paper are:

1. Comparison with non-parametric approaches to kernel selection (such as hyperkernels) is missing.
2. It could be argued that this approach is incremental, simply substituting one kernel-kernel [2] with another that has the advantage of being more readily evaluated.
3. Experimental results are limited.

I would be more comfortable in overlooking the second point if there was more experimental results (ie. more than 4 datasets evaluated), but it is difficult to draw strong conclusions from limited results, even though the improvements shown appear strong.  However I think it is important to include comparisons with non-parametric approaches for completeness.
questions: 1. When constructing base kernels, do you "fix" hyperparameters like length-scales (for the SE kernels) for each base, or do you tune such parameters using e.g. max-likelihood?  Further:
1a. if the former, do you attempt to give some flexibility by e.g. having multiple SE kernels with different lengthscales as distinct base kernels?
1b. if the latter, how do you measure the similarity between two examples of the "same" base kernels with different lengthscales?

2. Similarly, when doing operations like ADD, do you considered allowing for weighted sums (a1.K1(x,y) + a2.K2(x,y), where a1,a2 are scaling factors) rather than simple sums (K1(x,y)+K2(x,y))?  This would allow more flexibility, but I'm not sure how well it would fit in your kernel similarity calculations.

3. As a rough order-of-magnitude, how complicated do SOT kernels become?  I would imagine this would depend on how long you let the BO run and what heuristic limits you place on the your evolutionary algorithm, but I'm curious how complex the tree becomes.

4. Does using an evolutionary algorithm rather than global optimisation when maximising your BO acquisition function adversely affect convergence guarantees that usually apply to BO?
limitations: As noted previously, more experimental comparisons (more datasets) and at least one non-parametric result (e.g. hyperkernels) would improve this paper.
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: This paper proposes a new way to select a kernel (covariance function) for Gaussian processes (GP). The authors borrow ideas from NN architecture search to propose a so called symbolical-optimal-transport (SOT) kernel over the architecture of the kernel. In contrast to prior work, they do not compare to different kernels in function space. Instead they compare the symbolic architecture of the kernel directly. They do this by capturing the structure of the kernel in a tree and then compare these trees by comparing them by some kind of optimal-transport metric. 
This SOT kernel is then used for Bayesian optimization for model selection. This is fairly standard. A comparison to a hellinger kernel-kernel is given. The SOT kernel is computational advantageous because no integrals have to be computed.
The authors then demonstrate in a series of four experiments that the SOT kernel outperforms Greedy, Hellinger, Tree-GEP and SOT. This is true for both the training and the test set.
strengths_and_weaknesses: Strengths: While this idea has been executed for Neural Networks before, the presented idea is novel for Gaussian process model selection. The experiments are very encouraging and the idea seems natural. The computational advantages of this approach (over the known function space view) are well-explained. While the idea is simple, I do not consider this a weakness. The topic is very significant because model selection is extremely important for GPs. The quality of writing is good, it is quite easy to understand.

Weakness: There is almost no theory in the paper, except for the trivial Proposition 1. I think the focus on "Optimal Transport" is misleading because the special case of the OT distance that is used is quite trivial, and looks more like an l1 norm of the weights. Nowhere else is optimal transport used. 
questions: --- How does this work together with hyper parameter tuning of GP? Can I first run your method and then tune the hyper parameters as usual?
--- Can this be used to pick the kernel for RKHS regression or SVMs?
--- On page 4: Are Rule 3 and Rule 2 ('exchanging a base kernel with another kernel') really necessary? It seems to that they assuming the other rules would be enough...

Minor points:
--- The plural of GP is GPs, not GP's.
--- Please define g before it's used on page 3. 
limitations: The limitations are transparent and well-addressed.
review_title: null

Meta-review: metareview: This is a strong submission that benefitted greatly from productive and clarifying discussion between the authors and reviewers, after which the reviewers reached a unanimous stance in favor of acceptance. I recommend the authors to revise the manuscript accordingly in light of these discussions. 
confidence: Certain
Decision: Accept