Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This work is interested in kernel selection. In contrast with most of the literature they consider non-parametric class of kernels using hyper-kernels. Nevertheless, some previous works have already consider this setting but the authors argue that they had several limitations which motivates a new method. The authors first recall the background on Bayesian optimization and hyper-kernels then explain their method to mix the two while avoiding some computational complexity issues. They also show how to fix a naturally arising problem : the posterior mean of the hyper-GP may be positive. Finally, some theoretical and experimental results are provided.
main_review: The problem of kernel selection with non-parametric class of kernels is a subject of interest which has already been investigated. The limitations of the previous works indeed motivate new methods. It would have been great to have a more in-depth comparison with those works after the presentation of KFO to show that the latter does not suffer the same limitations.

Section 2 and 3 are clear enough.
The weak point of this work is the theoretical analyses of KFO. Indeed, the theorems may be stated in a more precise way : recall the space of each object, highlight the main claim with a centering when possible, recall the definition of each quantity or give a precise reference with equation numbers.
The proofs are not easy to check mainly because they are too wordy where a sequence of equations would be easier to follow. The use of previous results could also be more precise. The paragraph l.206 to l.216 is one example of those two problems.
It would be great to discuss more the results, comparing it to previous works on non-parametric kernel selection. Assumption 2 of Kirschner et al. 2019 should be recalled.

The experimental part seems more interesting. 
Overall, this work has a good potential but the theoretical part should be polished.

Typos:
- l.17 parameterise -> parameterize 
- l.79 symbol of average regret
- l.241 space of f ? if f(K) is real no need for ||.||_{H_k}.
limitations_and_societal_impact: -
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a zero-order optimization method where the optimized variable is a kernel function in Hyper-RKHS induced by a selected hyper-kernel. The method is an instance of the Bayesian Optimization method LINEBO [Kirschner 2019]. The contribution is in the adaptation of the LINEBO algorithm for efficient optimization w.r.t. positive definite kernel functions. The algorithm is applied to the optimization of kernel functions for C-SVM and GP regression. Experiments show significant improvement over existing methods. 
main_review: Originality. Using the Bayesian optimization for kernel selection has been previously proposed in

Malkomes et al. Bayesian optimization for automated model selection. NIPS 2016. 

There are similarities between the proposed method and the mentioned paper. For example, both use the GP to model the expensive objective function, the performance measure, and both optimize the objective via Bayesian optimization. There are also differences. Most notably, in the mentioned paper the kernel space is defined in terms of base kernels and a grammar to combine them, instead of using the Hyper-RKHS like in the paper under review. More detailed comparison of the two papers is work of the authors, who unfortunately do not reference it.

Quality. The paper is technically sound. The authors provide a convergence analysis of the proposed method. 

Clarity. The paper is clearly written. 

One unclear point that needs more discussion is the way used to select $N^2$ points for representing the hyper-kernel. The authors state that the points are constructed such that they represent the kernel sufficiently well (lines 142-143), however, it is not clear how. 

Significance. The empirical evaluation shows promising results. However, there are are points that need to be clarified. The paper does not provide a clear discussion of the computational/memory demands of the method and its efficacy w.r.t. size of the data (the number of examples and the feature space dimension) and the hyper-parameters like the number of approximation points $N^2$. There should be at least rough information about the computational time needed to perform the experiments on the data used. 

limitations_and_societal_impact: yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper introduces a novel approach which constructs the best fitting kernel function with adaptive tuned parameters. This kernel function is obtained by the linear combination of multiple kernels sampled from a prior Gaussian Process. The experimental results of two different kernel-based algorithms show the superiority of the proposed method.
main_review: This paper introduces a novel approach which constructs the best fitting kernel function with adaptive tuned parameters. This kernel function is obtained by the linear combination of multiple kernels sampled from a prior Gaussian Process. The experimental results of two different kernel-based algorithms show the superiority of the proposed method.
limitations_and_societal_impact: However, there are still some issues should be addressed as follows:
1. In Line 163, \beta is a vector and should be in boldface. Moreover, the author should use upper case to represent the test set.
2. This paper involves a lot of basic knowledge. The author should give more detailed introduction.
3. What does GP-UCB mean in the Line 76? To increase the readability, the author should give some necessary descriptions in the main paper.
4. A PCA algorithm is performed on a N^2 * N^2 matrix to avoid the computational burden as described in Line 157-159. However, the complexity of PCA is cubic of the dimension of a squared matrix. Please explain how PCA can reduce the complexity.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: Paper presents a novel framework for Bayesian learning of kernels using hyperkernels. It is able to address a broader set of kernels that are stationary and non-stationary, learn them efficiently and show state-of-the-art results on synthetic and real-world datasets.
main_review: A key contribution of the paper is of the ability to address a broader set of kernels that are non-stationary by using indefinite kernels later approximating positive-definite projection.  This allows the kernel regression approximation to deal with sharp changes in function value as shown in synthetic data.

Paper also also provides sound theoretical justification in terms of regret convergence of  of proposed algorithm as parameters of the effective dimension. 

Projection of data to to S subspaces provides a scalable approach to deal with larger datasets but parameter selection is not clear (n, T, S) seem to best selected for UCI datasets but selection strategy is not clear. How would parameter selection work for datasets like ImageNet and so on.

Evaluation is shown on UCI dataset which are real-word but small and not clear if it the proposed technique also works for large scale100s of category's classification.

Table 1 and Table 2 show that KFO does well for almost all but a few datasets. For classification Credit, Biodeg and Phoneme other classifier do well and for regression Fertility dataset ARD Matern does better. Is there a explanation for such a difference ? Are there any dataset specific peculiarities when KFO does not do well? 





limitations_and_societal_impact: Paper addresses technical limitations well but does not address effect of model/data bias and explainability of learned models.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This article proposes to use the hyperkernel formalism coupled with Gaussian Processes to derive the ‘best’ kernel for regression. The latter kernel depends mostly on the observations rather than on a pre-selected kernel family. The proposed procedure relies on several stages of Bayesian optimization as well as a clipping of the coefficients to avoid dealing with (indefinite) Krein kernels. The performance is presented on both synthetic and benchmark datasets, to assess visually the fit of the confidence intervals as well as the numerical performance.
main_review: I have found the article to be clearly written, with impressive numerical benchmarks, and a nice balance between exposition of the theory, of the algorithms, of the theoretical and numerical results. Though I did not go through the proofs in the appendix, the latter nicely complements the main body of the article.

Major comments:
-	Clipping: Since for indefinite kernels the strong topology is given by $k_++k_-$, have the authors tried flipping the coefficients ($\alpha_i\rightarrow |\alpha_i |$) instead of clipping them? In the synthetic/numerical experiments, can the authors show the number/magnitude of the coefficients that where clipped? I expect that, since kernels are understood in GPs as generating the covariance matrices, few negative coefficients should appear when fitting the synthetic curves. Could you remind the reader why negative definite covariance matrices cannot be considered in GPs as to explain why a clipping has to be introduced? It seems to me that in ``Learning the Kernel with Hyperkernels`` the discussion after Lemma 7 rules indefinite kernels out only because the authors have decided to focus on RKHSs rather than RKKSs. I thus imagine that the reasons for clipping differ between the kernel and GP communities.
-	Synthetic experiments: In Figure 2 and in the appendix, all the functions appear to have a non-zero mean. In kernel ridge regression (KRR), this would make the task much more difficult for the RBF/SE/Gaussian kernel and I am wondering if this may explain the failure of the SE kernel with this characteristic downward form sticking to zero in the area without observations. Can the authors repeat the synthetic experiments when normalizing the curves to have zero mean? While the choice of a linear kernel is classical, for these types of signals, it would be more adapted if there were some linear trends. Here it just seems to skew the confidence intervals. I believe that if the x-axis was centered to zero, then the weight assigned to the linear kernel would be close to null.
Overall, the Matern 3/2 kernel seems to produce confidence intervals very much alike the ones of the KFO. This begs the question of plotting the kernel of the KFO (for instance by showing $y\mapsto k(x,y)$ for several $x$). Does it recover some translation-invariant features of the data? All the experiments seem to focus exclusively on regression, would the KFO procedure be able to recover the covariance/kernel of a dataset that would be generated with zero mean and covariance some given kernel $k(x,y)$? Can an experiment be done in such a direction?

More generally, since $\lambda$ was managed to be chosen in $[0,1]$, would there be techniques to sample the kernels exclusively in the cone of positive definite kernels? As said above, I liked the article and am willing to upgrade my mark depending on the authors' answers.

Minor comments:

7 I would suggest citing the Ong et al. 2005 paper directly in the abstract since it serves as the main source for the procedure

110 Hilbert with uppercase

119  ``Learning the Kernel with Hyperkernels`` (Lemma 7) could be quoted with profit to justify for the finite decomposition. Or do the authors only intend to give examples of the type of indefinite kernels contained in $H_\kappa$? I very much appreciated the discussion of paragraph 109-120 which denotes a good knowledge of the existing literature.

207 this should be a $\succcurlyeq$

209-214 It is not clear to me why EVD was presented on 196-208 if not used (this contradicts 194 by the way). If the techniques of 196-208 are just quoted as other possibilities that are dismissed, then it should be stated more clearly.

225 Euclidean with uppercase

240 Formulation of Definition 3 is convoluted. I would suggest “if there exists” rather than “such that there exists” and to write $f:H_\kappa \rightarrow H_\kappa$ to make explicit input and output spaces (same for Theorem 2).

241 Why underline the kernels? They have the same interpretation as the ones of Eq. (5).

244 The kernel $k$ is a kernel over the hyper-RKHS, using $k$ here can be confusing. Maybe change it to $\Bbbk$ or any preferred notation?

319 In Table 1, what is $\dagger$ referring to?

limitations_and_societal_impact: Not applicable
review_title: null

Meta-review: The paper proposes a zero-order optimization method where the optimized variable is a kernel function in Hyper-RKHS induced by a selected hyper-kernel. The algorithm is applied to the optimization of kernel functions for C-SVM and GP regression. Experiments show significant improvement over existing methods. The reviewers consider the paper technically sound and clearly written with a potential relevant impact on the field. We encourage the authors to improve the clarity of the mathematical part following the discussion that emerged during the review and the rebuttal period.

Decision: Accept (Poster)