Kernel Functional Optimisation
Authors: Arun Kumar Anjanapura Venkatesh
Alistair Shilton
Santu Rana
Sunil Gupta
Svetha Venkatesh
Venue: NeurIPS 2021 Poster (2021)
Keywords: Non-parametric kernels
Kernel learning
Bayesian functional optimisation
Hyperkernels
Kernel machines
Gaussian Process
Hyperparameter tuning
Machine learning
Support Vector Machines
Reproducing Kernel Hilbert Spaces
Black-box optimisation
sample-efficient optimisation
Bayesian methods

Abstract: Traditional methods for kernel selection rely on parametric kernel functions or a combination thereof and although the kernel hyperparameters are tuned, these methods often provide sub-optimal results due to the limitations induced by the parametric forms. In this paper, we propose a novel formulation for kernel selection using efficient Bayesian optimisation to find the best fitting non-parametric kernel. The kernel is expressed using a linear combination of functions sampled from a prior Gaussian Process (GP) defined by a hyperkernel. We also provide a mechanism to ensure the positive definiteness of the Gram matrix constructed using the resultant kernels. Our experimental results on GP regression and Support Vector Machine (SVM) classification tasks involving both synthetic functions and several real-world datasets show the superiority of our approach over the state-of-the-art.

Kernel Functional Optimisation
Arun Kumar A V, Alistair Shilton, Santu Rana, Sunil Gupta, Svetha Venkatesh
Applied Artificial Intelligence Institute (A (A²12), Deakin University
Waurn Ponds, Geelong, Australia jaapjana,,,, alistair. shilton, santu. rantu.rana, gupta, svetha. Bankateshh@dealle edu.au
Abstract
Traditional methods for kernel selection rely on parametric kernel functions or a combination thereof and although the kernel hyperparameters are tuned, these methods often provide sub-optimal results due the limitations induced by the parametric forms. In this paper, we propose a novel formulation for kernel selection using efficient Bayesian optimisation find the best fitting non-parametric kernel. The kernel is expressed using linear combination of functions sampled from a prior Gaussian Process (GP) defined by a hyperkernel. We also provide a mechanism to ensure the positive definiteness of the Gram matrix constructed using the resultant kernels. Our experimental results on GP regression and Support Vector Machine (SVM) classification tasks involving both synthetic functions and several real-world datasets show the superiority of our approach over the state-of sate-of-theeart
Introduction
Kernel machines (Hofmann et al. 2008) generally work well with low-dimensional and small to medium-scaled data, most kernel machines, the kernel function is chosen from the standard bag of popular kernels (Genton 2001 Stein 2015) such as Squared Exponential kernel (SE), Matérn
kernel and Periodic kernel, or a weighted combination thereof (Aiolli and Donini 2015 Gönen and Alpaydın 2011 Rakotomamonjj
al., 2007). Recent developments (Jang et al. 2017 Wilson and
Adams 2013) in kernel learning parameterise the kernel function to boost the expressiveness of the kernel. However, the expressiveness of such kernels remains limited by the chosen parametric form and thus they often fall short in providing the best kernel function for complex data distributions.
There have been some early attempts to design an optimal non parametric kernel to remove the limitations associated with the parametric forms. Ong et al. (2003 2005) proposed a hyperkernel framework by defining Reproducing Kernel Hilbert Space (R (HSS on the space of kernels i.e., kernel on kernels to support kernel learning. They formulate a semidefinite programming (Vanden- berghe and Boyd 1996) based optimisation problem using the representer theorem (Steinwart and Christmann 2008 Vapnik, 1999) to find the best kernel. However, their method suffers from two key limitations: (i) their way of enforcing the positive definiteness property produces restrictive search space, resulting in a sub-optimal solution, and (ii) the computational complexity of their method scales with the dataset size, making it infeasible for larger datasets. [Benton et al. (2019) proposed Functional Kernel Learning (FKL), which extends the function space view of the Gaussian Process (GP) for kernel learning. FKL uses transformed GP over spectral density to define a distribution over kernels. However, the formulation of kernel functionals using the spectral densities induces strong assumptions the properties such periodicity, stationarity, etc. and thus are not generally applicable, Malkooee et al. (2016) proposed an automated kernel selection (BOMS) using Bayesian optimisation. The kernel space in BOMS is defined by the base kernels and the associated grammar to combine them. Although the search space is constructed by summing or multiplying the base kernels, the resultant kernel space is restricted in the compositional space of parametric forms.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In this paper, we propose a generic framework called Kernel Functional Optimisation (KFO) to address the aforesaid shortcomings. First, it provides flexible form of kernel learning whose computational complexity is decoupled from dataset size. Next, it allows us to use computationally efficient Bayesian optimisation method to find the best kernel. We incorporate hyperkernels into our Bayesian framework that allows us to search for the optimal kernel in Hilbert space of kernels spanned by the hyperkernel (Ong et al., 2005). We draw kernel functionals from a (hyper) GP distribution fitted using hyperkemel. As the kernel drawn from the hyper-GP may be indefinite, we provide ways to ensure positive definiteness by transforming indefinite, or Krein (Oglic and Gärtner 2019. Ong et al. 2004) kernel space into a positive definite kernel space. The optimisation of kemnl functionals necessitates solving larger covariance matrices and thus adds to the computational burden of the overall process. To speed up the computations, we perform a low-rank decomposition of the covariance matrix. Further, we provide a theoretical analysis of our method showing that it converges efficiently in its cumulative regret grows only sub-linearly and eventually vanishes.
We evaluate the performance of our method on both synthetic and real-world datasets using SVM classification (Dichl and Cauwenberghs 2003 Scholkopf and Smola | Burges 1998) and GP regression tasks. Comparison of predictive performance against the state-of-the-art baselines demonstrates the superiority of our method. Further, we compare with the state-of-the-art performance reported in the latest survey paper on classifier comparison (Zhang et al.) 2017) and find that our method provides the best performance on most of the datasets. Our main contributions in this paper are as follows: (i) we propose a novel approach for finding the best non con-maracttric kernel using hyperkernels and Bayesian functional optimisation (Section B (ii) we provide methods to ensure positive definiteness of the kernels optimised (Section(3) (3), (iii) we derive the convergence guarantees to demonstrate that the regret grows sub-linearly for proposed method (Section 4 (iv) provide
empirical results on both synthetic and real-world datasets to prove the usefulness (Section (
2 Background
Notations We use lower case bold fonts for vectors and e for each element in vt is the transpose. We use upper case bold fonts M (and bold greek symbols) for matrices and My for each element in M.
for the absolute value. N,, = {1, 2, ... .n.. E for Reals. X' is non-empty (index) set and x E X' X is a non-empty (compounded index) set and negative value to zero. [[] is the Iverson bracket (Iverson 1962) defined for any boolean value I as [T] = 1, if 7 True, 0 otherwise. Matrix M [MyyesJeN and | is the Frobenius Norm of M.
X, X2. (-+ clips a
2.1 Bayesian Optimisation
Bayesian Optimisation (BO) (Brochu et al.
2010 Shahriari et al. 2015 Frazier 2018) offers an
elegant framework for finding the global extrema of an unknown, expensive and noisy function fxx), represented as x" = argmax (x)) where X' is a compact search space. Bayesian optimisation comprised of two main components: (i) Gaussian Process (GP) (Williams and Rasmussen 2006) model of f. and (ii) an acquisition function (u) (Kushner, 1964, Močkus 1975 Wilson al. 2018) guide optimisation. Let D {xi:t> y1æ}] denote a set of observations of f. where y [x) + e' is the noisy observation corrupted with white Gaussian noise e' E NN( o2 R Then the predictive distribution at any point x, is given as (x.) NN ((((xx)),)))))))))))(())) (xx)), where p(x.). =
kT
K + o² Ppniss 10 yy,, (xx) = k(x,,, x.) kt K + o² maiso - k, k = [k(x.. x)) .... ((x,,x())) ),),
X x X + R and = [k((,,, x,) Jaa.e.. The negative log- likeelhddood for a GP distribution is
log P(y. (D.x.)
Mog(2to0(xxx
(v- (xx)))
(x.)
The acquisition function (u) guides the search by balancing between exploitation (searching known high-value regions) and exploration (searching high-variance regions). Gaussian Process Upper Confidence Bound (GP-UCB) acquisition function (Srinivas et al. 2012 Brochu al., 2010 the commonly used acquisition function to find the next best candidate for the evaluation, given as
44 (x) m(x) + V (x)
where Br grows as Ologt) with iteration Further, it can be shown that the average regret (R A $ E [fxx)) - f(x))) grows as O( (oooo l/t), and hence the average regret vanishes as
t + co. An algorithm for standard Bayesian optimisation is provided in the supplementary material.
2

---

The aforementioned standard Bayesian optimisation procedure often suffers from scaling issues originating from the curse of dimensionality. WWang al. (0016) proposed REMBO Random E.Mbedding Bayesian Optimisation to address these scaling issues. REMBO works by projecting the objective function onto a lower-dimensional subspace prior to optimisation. LINEBO (Kirschner et al.) 2019) builds on the same idea but instead of fixed subspace, it decomposes the given black-box optimisation problem into a sequence of one-dimensional subproblems. Further, our method builds upon the principles of Bayesian functional optimisation methodologies (Vien et al. [0118 Vellanki ct al.
2019 Shilton et al. 2020) in the literature to find a function to optimise the given process.
2.2 RKHS and Hyper-RKHS
The kernel functions used in the Gaussian process uniquely define associated Reproducing Kernel Hilbert Space (RKHS) (Aronszajn 1950). Formally:
Definition 1: Let Hy be Hilbert space of functions f X - R on non-empty set X. A function k : X x X + IR is a reproducing kernel of Hgs and Hy a Reproducing Kernel Hilbert Space (RKHS), if the following properties are satisfied.
k spans Hx i.e. H2 span(k(,, X}
EXEX, Vf E He. ((.)),(. x)) = f(x) (the reproducing property) vx, x' E X, k(x,x))= (M1: x), k(. x))
Next, we consider the Reproducing Kernel Hilbert Space (RKHS) of kernels by introducing compounded index set X² X' x X' and hyperkernel (Ong and Smola 2003 Ong et al. 2003). Analogous to the RKHS (Aronszajn (950) associated with the kernel function, a hyperkernel defines an associated Hyper-Reep Reproducing Kernel Hilbert Space Elyper-RKHS, (Ong et al. 2003).
Definition 2: Let X' be a non-empty set and X denote X x X. The Hilbert space Hy of functions Kernel Hilbert Space (Hyper-KKHS) if there exists a hyperkernel k & x X + R that satisfies the following properties:
k & R is called a
x spans Hh ie., Hhe span(n((, x) & x X)
vx E &, Ak E Hx: (k(+), x(,,)(())))))))))))))) 8)) = k(x) (the reproducing property)
vx, x E X, n( (m( x), kl: X'H
"(x',,",,"" , ) xxx", x x" x) vx',"", x""
The GP distribution defined by a hyperkernel k is a distribution on the space of kernels. This Hyper-RKHS is a Hilbert space comprised of positive definite, negative definite and indefinite kernels. A Kreīn kernel & (Oglic and Gärtner 2018 Ong et al. 2004) is an indefinite kernel with a positive decomposition i.e., there exist positive kernels h_ E H4 and k_ H.,, such that x(x', x", x" xx"") is kernel, where
k = k4 k_ From Definition 2, we see that x(X, x"). Generally, the samples drawn from GP k) do not lie in the corresponding RKHS He. but in a larger RKHS H (see discussion in Kanagawa et al. (2018), Remark 3.8 and Section
4). We also note that the posterior mean of GO( F) lies in the RKHS He. Similarly, with hyper- GP, the samples drawn from (0, x) lie in RKHS Har'e whereas its posterior mean (14) lies in Ha. Further, μ can be decomposed with positive and negative weights as μ = p4 μ ,4 > 0; and μ+ = >, ai, <(,, ) is kernel >, 04 aa___K({ xx.) -, 0g <(, X, where ai, Q4_
(Definition and Ong et al. 2004)). Thus, j p4 p is a Kreïn kernel (Oglic and Gärtner 2019).
3 Framework
In this paper, we address the global optimisation problem formulated as K* argmax, x KEH, (K), where f Hh. + R is an expensive objective functional and ς is a hyperkemnll. In particular, we are interested in finding the best kernel K* E H. to maximise the model performance represented by the objective functional (for example, f can be the leave-one-out classification performance of a SVM classifier). First, we describe the construction of valid kernel functionals using hyperkernel, followed by discussion the kernel functional optimisation using Bayesian optimisation. A flowchart
3

---

describing the overall optimisation process of kernel functionals is shown in Figure 1 A complete algorithm for the Kernel Functional Optimisation (KFO) is given by Algorithm
3.1 Construction of Kernel Functionals from Hausr-Gaussian Process
Ong and Smola (2003) and Ong et al. (2003) 2005) have discussed the general guidelines to design a hyperkernel. We follow the same strategy to formulate Matérn Harmonic Hyperkernel (k):
An.
<(x, x"
(3)
1 - (Ax ê 02 exp ( 23
+ +r))
where An and / correspond to the hyperparameters of the hyperkernel, 71 = ||x x'|, 72 T -x"","]|, (1+ and č2 (1+ x2r)). The derivation of Matérn Harmonic Hyperkernel is provided in the supplementary material. In our proposed method, we use the draws from a (hyper) Gaussian process GP (0, k) to construct mnite-dimensione subspaces of our kernel space which we perform optimisation. As discussed in Section 2.2 the kernel samples drawn from GP,((0, k) do not lie in Hx, hence we approximate the draws using the posterior mean of GP (0, R) lying in He.
||x- ||
In practice, when sampling from gPx x (0, R.), we assume grid G with Ng points {2, -.. |& X X' x X, Vi E Nv,) for placing a GP distribution on kernels using hyperkernel k mentioned in Eq. (3. The sample set k ~ gPx xPxx00 x) is essentially a set of noiseless observations of the kernel K on the grid-points x1 X2, lying in Haryex. The number of points in the grid is chosen such that the resulting grid is sufficiently fine represent the kernel K everywhere on X. Therefore, for any point & E X, the posterior variance of the kernel K given the observations {(x;, 1 E Nv, is negligible and thus the kernel K can be approximated using the posterior mean of GP, (0, k)
(x) Rs [x(2, x(x,, X2) (xx 83) ... k Σ as x(Xx where a = K -1 k (4)
A very fine resolution grid ensures that we can capture small-scale patterns in the kernel. However, a large grid size comes with large computational costs. Therefore, the choice of Ng trade-off between the overall computational cost and the accuracy of kernel optimisation expected. We discuss the computational complexity and the associated memory demands pertaining to N, in Section 4.4
3.2 Kernel Functional Optimisation
We adopt the ideas from Bayesian optimisation method LINEBO (Kirschner et al. 2019) for the optimisation of non non-poramn parametrie kernel functionals via sequence one-dimensional projections. First, we discuss the construction of low-dimensions subspaces. The key challenge here is to address the computational burden with the use of large grid. Next, we describe the Bayesian functional optimisation for each of the subspace and across many such subspaces. Since the best kernel obtained a Kreūn kernel, we apply transformations to ensure the positive definiteness of the Gram matrix.
Construction of Low-dimensional Spaces We start with the construction of low oww-dieeniooal search space spanned by randomly chosen basis vectors drawn from the hyper-GP GP (0. x). The hyper-GP surrogate modelling requires the computation of covariance matrix k E R XN, using for the predefined grid G. Further, the accuracy of the kernel functional to represent the kernel K is directly proportional to the assumed grid size Ng. To avoid the computational burden arising
Input parameters N₂, 8,
Fit (hyper) GP using x on pre defined grid
Construct dimensional subspaces
Find optimal kernel in using GP-UCB BO (inner-loop)
Subspoces limit (s)
No
O plimisation in subspaces (outer-loop)
Output best kemel
K
rechhed
Figure 1: A complete flowchart for the Kernel Functional Optimisation (KFO) framework.

---

from the larger grid size Ng. we perform Principal Component Analysis (PCA) (oold et al 1987 and choose N' principal components. Mathematically, we represent K: (EVA) A)T, tth column e, in E IR N corresponds to the 7th principal component and A E R R-'' x diagonal matrix containing top N' eigenvalues. The outer-loop in Algorithm I iterates through sequence of S dddimensional subspaces by drawing random basis vectors each subspace from GP,((O, k) i.e,, k(*,, k()),... k(() ~ GPx (0, k), where k( = E V ,3() and z ~ NO, Iv.).
where
the
Kernel Optimisation Observation Model
As discussed carlier, construct kernel functionals ((.-) from the hyper-GP distribution gP,, (0, k) as per Eq. (4) using
k = K
A (2 (2) ... + X k(
(5)
where XO) E [0, 1]. k are the random basis vectors drawn and K* corresponds to the best kernel found across all the previous subspaces. The optimal kernel in the given subspace is obtained by optimising À using a Bayesian optimisation procedure with another GP distribution GP(O, (o.)). The observation model for (O(O, İsE) considered as D' = {(K, y = f f())), where K' is the kernel functional constructed and is a measure signifying the ability of the latent kernel to represent the given data. For example, log-likelihood can be used as the measure y in our observation model.
Building GP for Kernel Optimisation We fit GP distribution (P( RSE) the observed kernel functionals using the Squared Exponential (SE) kernel (Fese) given by
KSB ( K2) क9 exp
Ki
K2 M,
(6)
2T
where o and T correspond to the signal variance and lengthscale parameters of KSE- Although there is no restriction the kernel choice here, consider the commonly used SE kemel. As mentioned earlier, we approximate K using the posterior mean (μ), therefore we compute the similarity between kernel functionals using the RKHS norm (II l|x,,) estimated
K2 - K2 K2ll = Il - 12 = -VaJka + a]Ka2 - 2a] kO22
where 141 and #2 are the posterior mean approximations of K₁ and K2, respectively. We refer the supplementary material for the details of similarity formulations using L
Kernel Optimisation We find the best kernel functional in the given low-dimensional subspace using GP-UCB acquisition function (Eq. (2) with 8r = 2 (t $ x² /35), where ñ corresponds to the total number of kernel functional observations and 8 a value in [0, 1]. The best kernel found (K*) across all the previous subspaces acts as subspace bias guiding the optimisation in the subsequent subspaces as per Eq. (5). The selection of S d-dimensional subspaces (outer-loop) and optimising the kernel (for T iterations) in each of the subspace (inner-loop) continues until the search budget is exhausted. The hyperparameters 0- = { Y) in ÆSE are tuned by maximising the log marginal likelihood. In addition to that, the hyperparameters of the hyperkernel (e- (An. (]) mentioned in Eq. (3) are tuned using another standard Bayesian optimisation procedure. The observation model for the hyperparameter tuning of hyperkernel is constructed as D {(O, y r(+))}. where I' maps the model performance 3/ with the corresponding hyperparameter set θ We refer to the supplementary
material for the detailed discussion on tuning the hyperparameters of both kernel and hyperkemnll.
From Kreūn kernels to Positive Definite Gram Matrix
As the kernel approximated by Eq. (4) is an indefinite, or Kreïn kernel (K), the Gram matrix (C) constructed for the datapoints using K is also indefinite. We use the following matrix post- processccssiig methods to ensure the positive definiteness of the Gram matrix constructed.
The Eigen Value Decomposition (EVD) based matrix post-processing involves the decomposition ZAZT, where Z is the square matrix containing eigenvectors
of the Gram matrix C as corresponding to the eigenvalues in the diagonal matrix A. The Eigen spectrum clip (A: = (A+)+) ensures positive definiteness of the given training and test covariance matrix, but in isolation, without considering the transformation of the underlying kernel function, thus resulting in inconsistency
5

---

Algorithm Kernel Functional Optimisation
Input: Ng Number of points in the grid, 5 Number of subspaces search, 7 Number of iterations
1. Initialise (K* (K#,;, 1/eaa) + (0, 0), Dn +
2. Compute R. for N₂ grid points ,, X2. ... using Eq.
3. Perform PCA of K. as
1,2, (EVA) (EVA)(EVA))
4. for Subspace
do (outer-loop)
5. Sample k()), k(2) ... k(d) ~ g0, (0, k)
6. Generate random initial observations in the current subspace $
D' {(K, 2)) Eg. K (2) + x - f(K), ALeN ~ (O,
7. for each iteration t = 1, _ do (inner-loop)
8.
Solve X, argmax un (u((((A)) + oBr XE(0
9.
Compute the new kernel Knew as Knew
Eq.
K#
+ k()) + +...+ X! k(d)
10.
Use the kernel Knew and Č to measure the fitting quality Vnew {KKeww
11.
D' + D' U [KKnow, ynew))
12.
end for
13.
D2 D UD' (K# (best) = argmax (K.y) ED,
14.
15.
end for
16. K* <- K#
17. return (K" Ybess)
(see discussion 2.2 in Chen et al. 2009)). Therefore, to consistently transform both the training and test points, the Eigen spectrum clip treated linear transformation on the training points first i.e. Cuaano = clip Cuain. where eelip is the spectrum transformation matrix and then, apply the same transformation on Crea [K (Xeest x1 K (Xest: X²) ..... as Cest Crest where delip ZZAlip ZT and Aeip = diag([I11 2 0], [2 2 O]. ...). The magnitude of change in the transformed matrix (C) from the given indefinite kernel matrix (C) is minimum with the spectrum clip transformations Le., Ctip argmin C ClIF. We note that, it is possible to the original optimised kernel for specialised SVMs (Ying al. 2009), but we consider this as part of the future work.
For GPs, there a strong requirement that the covariance matrix positive definite as it needs to generate positive definite covariances. AAhan and Chu (2012) have demonstrated the vulnerabilities of GP with indefinite kernels. The aforestated EVD based post-processing gets complicated for GP. The GP predictive distribution involves the calculation of mean (d-) and variance o² (-) for the test samples. The variance requires the computation of [K (Xies, Xies) Although the linear transformation & Selip on Cuain ensures positive definiteness of Cuea = (Xiess x1) K (Xess x2)... does not consistently transform [K (x Xes)]. Therefore, we need ways to enforce positive definiteness before we compute predictive variances. To ensure positive definiteness in GPs, we clip the values of a i.e., a = [a;:+] ] in the posterior mean approximation of kernels by visualising the kernel approximation (Eq. in terms of the representer theory mentioned in Ong et al. (2055)
4 Theoretical Analysis
4.1
Inner-loop
The cumulative regret for the optimisation in the inner-loop is given as RT = ET where K* is the best kernel found across all the subspaces. In the inner-loop, our goal is to derive the upper bound for the cumulative regret (Rr) in terms of the total number of iterations' T'.
In conventional BO algorithms, the variables being optimised are directly used in the model construc- tion. In contrast, the inner-loop in proposed method constructs the model using the projection of the variables (Ax) being optimised in the functional space i.e.. k K Σ, (1)

---

Proposition 1: Let S2 be the subspace constructed in each instance s the outer-loop. Then, at each
iteration I of the inner-loop, the maximum information gain (7t) of the kernel k : S. x S + IR is
same as that of the information gain of the standard kernel in Euclidean space k X X + R.
The proof of proposition is deferred to the supplementary material.
It is important to note that the model for f in the inner-loop is constructed with the observations obtained from the current and previous subspaces search and not just the observations from the current search. Therefore, the bounds on the overall regret for the inner-loop can be derived as follows.
Theorem 1: Let [(K) be the posterior of I in subspace before entering the inner-loop and f(K) UD' be the posterior iteration t of the inner-loop. Then, the updated posterior [(K))D,-1UD is equivalent to the posterior of the biased GP with prior covariance RrD.-, and the inner-loop regret grows sub- subllinearly as O (v /dtty.....) where "YD,-1,t is the maximum information gain the prior covariance kDD,., and O notation is a variation of O with log factors suppressed. The proof of Theorem is provided in the supplementary material.
4.2 Outer-loop
We provide theoretical analysis of the outer-loop based on the notion of effective dimension (Kirschner et al. 2019 Wang et al. 2016). As we deal with the functionals in our proposed method, the standard definition of effective dimension is slightly modified as follows:
Definition 3: function f H2x + IR is said have effective dimensionality d' E EN, if there exists (1)) ((2) k(d') E He such that [][(K + K1) [(K) = 0, AK E K, v E K-+, where K = span(k()) 1k)2).... ,.. ,k())((d))) and K = {K E H. (K, H.. = 0, AK E K}.
Following Kirschner et al. (2019), we derive the regret bounds for the outer-loop.
Theorem 2: Given a twice paachet-diffeenntaabe kernel H. x Hr + R. let 0 < 6 < 1.
f f~ GP k) with effective dimension d' and maxima K* argmax H.. f(K). Then, after subspaces search (s outer-loop iterations), with probability at least 1-ô, the regret f O(dd < d'I( l))( شं + ed,s). where K## is the best kernel found across all the previous subspace searches and ca,5 is the regret bound for the inner-loop and [|-] is the Iverson bracket.
The proof of Theorem is provided in the supplementary material.
4.3 Overall Convergence
In LINEBO, one-dimensional subspaces (or the lines) are optimised up to err (K+) < e for some fixed (Lemma of Kirschner et al. (2019) and K+ argmax (K,)). ). In our method, for a given subspace 8, we terminate after T iterations with accuracy err(K+) S cg,5. In our setup with d = 1, given a fixed budget (T' iterations) for the inner-loop, we get 61.6 E O(r=-1), where E (0, 0.5) (Assumption in Kirschner al. (2019)). On the other hand, if the number of vectors (d) spanning the random basis is same as the effective dimensionality (d"), then our convergence is analogous to REMBO (Wang et al. 2016), with the regret imposed only by ca' 8. Further, the order of regret bound in such cases remains unchanged even if we consider only one subspace search (S = 1).
Alternatively, simple regret measure implemented terminating condition in the inner-loop results in the regret bound 6d,6 e. If we consider one-dimensional spaces (d = 1) and use err atr(K') (K+)+ < as the terminating condition for the inner-loop, the convergence guarantee of algorithm exactly same as that of LINEBO with <d,8 = 6. Thus, the inner-loop of our algorithm is expected to complete
in T E O(e Trxa) iterations for some c 0.5) (see discussion around Assumption 2 in Kirschner et al. 2019)), resulting in ((Ser total number of function evaluations overall.
4.4 Computational Analysis
The computational complexity of our approach is in the order of O3S where S is the number of subspace searches, T is the number of iterations each subspace and N is the number of points in the grid, without including the complexity of the downstream class (as it would be different for
7

---

different kernel machines). The main bottleneck of our method is the computation of the covariance matrix R E I2 X,,, To avoid the computational burden resulting from the large covariance matrix K. for the given g.. we perform Principal Component Analysis (PCA) of K. Here, we do not perform a full PCA, rather we choose only top N' principal components (N' < Ng). The computational complexity of finding top N' principal components is O(N'N)) which much lower than ((vg). Moreover, we perform PCA only once, prior to entering the outer and inner optimisation loops. Thus, we incur a cost on startup but are rewarded with significant computational savings in the main optimisation loop where the computational burden is proportional to N rather than N2. The memory complexity for optimising the kernel functionals using our proposed method is in the order of (NV)).
Further, as we deal with kernel selection problem. we are only concerned with the complexity of the observed search (kernel) space. Theoretically, the optimality of our method is not limited to any dataset-specific characteristics such as the number of dimensions (n) or the number of target classes in the given problem. Such characteristics do not have a significant role in the kernel optimisation, but the complexity of the given search (kernel) space plays a vital role in the optimisation performance.
Experiments
We evaluate the performance of our proposed algorithm (KFO) on synthetic benchmark functions and also apply our method on real-world datasets for SVM classification and GP regression tasks. We have considered the following experimental settings for KFO. We have used Matérn Harmonic Hyperkernel (Eq. (3)) to define the space of kernel functionals. To express the kernel as kernel functional in RKHS, we consider N, Z 10 for a given dimensional problem. The outer-loop representing the number of low-dimensional subspace searches (S) to find the best kernel function is restricted to S 5 and the number of iterations (7") in each of the subspace (inner-loop) restricted to T = 20. We use GP-UCB acquisition function to guide the search for optimum in all our experiments and at all levels. The hyperparameters X and of the hyperkernel (Eq. (3) tuned in the interval (0, using a standard BO procedure mentioned in the supplementary material.
5.1 Synthetic Experiments
In this experiment, we test our algorithm (KFO) with the following synthetic functions: (i) Triangular wave, (ii) a mixture of three Gaussian distributions (Gmix). and (iii) SINC function. We compare with the following stationary and non-stationary kernels: (i) SE kernel, (ii) Matérn kernel with v 3/2 (Mat3/2), and (iii) Multi- Kertel Learning (MKL) as a linear combination of SE, Mat3/2 and Linear kernel. The hyperparameters Y, of and weights (in the case of MKL) of the baseline kernels are tuned by maximising the log-likelihoone synthetic functions. We report the mean and the standard deviation of the maximum log likelihood computed over 10 random runs. We show the posterior distribution and the maximum log- likelihhood estimates obtained for Triangular wave function in Figure 2 for the results on other synthetic functions. It is evident that the posterior distribution computed using the standard kernels has poor predictions in the held-out test region. By contrast, the kernel suggested by KFO has better predictive mean and variance in the held-out test region. Especially note that the KFO optimised kernel was able to find the correct periodicity even without explicit enforcement.
We compute the posterior distributions for the aforesaid
We refer the supplementary material
1.0.
Kernel
Matérn Kernel
1.0 Multiple Kerne Learning
Thue
True
True In
Tram
0.8
Mcon
0.8
Mean
MW
0.6
0.6
0.4
0.4
0.4
0.4
0.2
0.2
0.2
0.2
9800
0.25
0.50
0.75
1.00
08.00
0.25
0.50
0.75
1.00
98.00
0.25
0.50
0.75
1.00
0f00
0.25
0.50
0.75
1.00
x
likelihoodge 173 + 1.2
likelihoodyast = 81.8 + 1.9
likelihoodaaa. = 82.1 0.4
likelihnodgro 89.8
1.6
Figure 2: Posterior distribution and maximum log-likelihood computed for Triangular wave function using KFO and other baselines. The solid blue line shows the true function. The green shaded area covers two standard deviations above and below the posterior mean shown by the green dashed line.
8

---

5.2 Real-world Experiments
We compare the performance of our proposed algorithm in SVM classification and GP regression tasks against the state-of-the-as baselines. In our classification and regression experiments, we use the publicly available multi-dimennsonal real-world datasets from the UCI repository (Dua and Graff 2017). In SVM classification problems, we use C-SVM in conjunction with KFO to minimise the test classification error (Fer). We perform 10-fold cross-validation on the training data set containing 80% of the total instances and tune the cost parameter (C)) of the SVM in the exponent space of [-3,3].
We compare our results with Radial Basis Function (RBF) based traditional C-SVM classifier (SVM- RBF) and MKL based SVM classifier (SVM-MKL), We also compare with parameterised Linear SVM (v-SVM) adhering the definition of the hyperkernel optimisation problem using the results mentioned in in/ong and Smola (2003). The classification error (in %) obtained for the test set consisting of 20% of the total instances using different classifiers over 10 random runs are shown in Table [ To demonstrate the efficiency of our approach, we also present the best test classification error (last column of Table reported by state-of-the-ard classifiers in the literature (Zhang et al.) (017). To the best of our knowledge. [Zhang et al. (2017) is the most recent work that surveyed numerous classifiers and reported their performance on UCI datasets. Additionally, we also construct a SVM classifier (KFO-MKL) with its kernel formulated as a weighted combination of KFO tuned kernel and standard kernels (analogous to MKL), we refer to the supplementary material for the results with KFO-MKL.
Table 1: SVM classification results (mean test classification error and its standard deviation) for the real-world datasets using KFO and other baselines, with the test set consisting of 20% of the total instances. Bold indicates the best performance among all the columns. The last column shows the best performance reported among all the other classifiers mentioned in Zhang al. 2017
Dataset
KFO
SVM-RBF
SVM-MKL
V-SVM
Other Classifiers
lonosphere
3.06 + 1.6
1.1
9.31
6.7
5.56
Glass
0.19
7.2
20.86 0.7
8.9 2.6
9.52
Sonar
6.6 1.2
15.3
20.99 4.4
15.3 + 3.7
3.7
4.76
Heart
11.47 0.2
3.7
15
19.3 + 2.4
14.14
Wine
0
0.00
Credit
-..57
2.0
13.62 + 1.8
13.8
24.00
Biodeg
12.12 1.29
2.5
12.33 1.5
14.4 4.4
11.32
Hayes-Roth
1..18
6.2
18.69
16.1
21.43
WDBC
0.68 + 0.84
1.2
1.6
3.2
1.59
Contraceptive
30.1 + 2.71
2.3
3.7
44.59
Car
0
0.3
2.54
2.02
0
Phoneme
22.74 = 2.31
2.6
0.3
1..
10.17
Ecoli
0.96 + 0.7
+.7
1.3
3.99 + 0.7
12.12
Seeds
1.2 + 0.2
8.74
3.96 0.5
10.32 4.8
4.55
Summary
9/14
1/14
2/14
1/14
5/14
In GP regression tasks UCI datasets, we compute the negative log-likelihood (Eq. (1) on the test set as a measure of performance. We compare our results with the standard parametric kernels such as RBF and Automatic Relevance Determination (ARD) Matérn kernel and the non-parametric kernels such as Functional Kernel Learning based kernels (FKI-SShard and FKI--Spprrate) mentioned in Benton et al. (0119). FKL-Separate, the functional kernel learning is achieved by formulating a product of one- ine-dimensional kernels, each of which has its own GP and hyperparameters. In contrast, FKL-Shared uses GP with unique of hyperparameters to draw one-dimensional kernels. The results of our GP regression tasks are shown in Table [ with each cell containing the mean negative log- likeeiiolood and the standard deviation computed over 10 repeated runs with random 80/20 train/test splits. Evidently. our method outperformed the state-of offte-of-the-att the-art art baselines in both the SVM classification and GP regression experiments, demonstrating the significant improvement in generalisation performance. We refer to the supplementary material for the experimental details and the additional results. The code base used for the experiments mentioned above available at https: / /gi thub. com ma il toar htw.a//wwwwaaaae//eoo/oooeeoaaaa

---

Table 2: GP Regression results for the real-world datasets using KFO and other baselines. Each cell signifies the mean negative log-likelihooe and the standard deviation computed over 10 random runs. Lower the better. Bold indicates the best performance among all the columns.
Dataset
KFO
RBF
ARD Matérn
FKL-Shared
FKL-Seperate
Fertility
5.15 2.95
-3.90 + 1.76
-4.40 + 2.58
-2.7 = 1.25
-1.83 + 3.3
Yacht
-34.6 1.6
1.65
-19.49 14.0
-14.22 + 4.7
15.7 8.2
Slump
-3.01 1.7
3
26.33 7.48
4.38 +
59.4 12.87
Boston
-24.7 4.2
139.61
130.8 10.50
122.6
143.7
Auto
-8.78 1.2
96.18
94.01 5.03
101.7 19.3
98.94
Airfoil
-.04.1+4.5
358.93 8.93
305.88 + 7.46
270.0 + 28.4
284.8 + 48.7
To provide brief insights the computational time, we have reported the average CPU time (in %) spent optimising (or searching) the kernel and the average CPU time (in %) spent evaluating the kernel by our approach in Table 3 We observe that the percentage of time spent optimising the kernel no more than 10% of the whole model fitting time. Thus, the proposed method does not add much overhead to the model fitting process. We have also measured the total runtime (in seconds) required for an instance KFO tuned SVM to complete runtime also includes the runtime required for generating 4 random observations in each subspace. The aforesaid runtimes are measured on server with Intel Xeon processor having 16 GB of RAM.
x T iterations, where S = T = 5. The total
Furthermore, we ideally expect our proposed method to at least achieve the generalisation performance demonstrated by any standard parametric kernel for the reason that we find the optimum kernel the whole space of kernels composed of plethora of kernels including parametric kernels. Although our proposed approach able to find the global optimal kernel in most cases, we occasionally observe that our method does not provide the optimal kernel. A possible reason for this could be the insufficient computational budget allocated or the substandard approximations and optimisations. Our empirical results have demonstrated that with smaller grids (smaller Ng)) using Kernel Functional Optimisation (KFO) framework.
achieve good generalisation performance even
Table Runtimes measured for SVM classification using KFO tuned kernel on real-world datasets. The percentage of time spent optimising the kemnel and evaluating the kernel is depicted in the fourth and the fifth column, respectively. The total runtime (in seconds) is shown in the last column.
Dataset
Samples
Features
Optimisation Time(%)
Evaluation Time (%)
Total Runtime
Sonar
208
60
9.1 = 4.7 + 0.35 9.35 + 0.55
90.87 = 0.694
567.7 + 4.64 1070.1 + 24.1
Heart
303
13
95.24 = 0.567
Glass
214
9
90.64 = 0.441
554.7 8.19
Credit
1000
24
0.9 + 0.13
98.8 + 0.360
5191.3 34.2
6
Conclusion
We present a novel formulation for kernel selection via the optimisation of kernel functionals using Bayesian functional optimisation. The kernel functional learnt is non-parametric kernel capable of capturing the intricate stationary and non-stationary variations. Our algorithm iteratively searches through sequence of random kernel functional subspaces where the best kernel obtained from all the previous subspace searches biases the next search. The resultant kernel an indefinite. or Kreïn kernel, thus resulting Gram matrix. The theoretical analysis shows a fast convergence rate of our algorithm. The experimental results show that method outperforms the other state-of-the-art baselines.
matrix proc-progsssing techniques to ensure the positive definiteness of the
Acknowledgments
This research was partially funded by the Australian Government through Australian Research Council (ARC). Prof. Venkatesh is the recipient of an ARC Australian Laureate Fellowship (FL170100006).
10

---

References
Aiolli and M. Donini. F scalable multiple kernel learning algorithm. Neurocomputing. 169:215-224, 2015.
N. Aronszajn. Theory of reproducing kernels. Transuctions of the American Mathematical Society, 68(3)3337-44,, 1950.
M. S. Ayhan and C.-H. H. Chu. Towards indefinite Gaussian processes. Technical report, Technical report, University of Louisiana at Lafayette, 2012.
G. Benton, W. J. Maddox, J. Salkey, J. Albinati, and A. G. Wilson. Function-space distributions over kernels. In Advances Neural Information Processing Systems (NeurIPS 2019), pages 14965-14976, 2019.
E. Brochu, V. M. Cora, and N. De Freitas. A tutorial on Bayesian optimisation of expensive cost functions, with application active user modeling and hierarchical reinforcement learning. arXiv preprint arXiv11012.25999 2010.
C. J. Burges. A tutorial on support vector machines for pattern recognition. Data Mining and Knowledge Discovery, 2(2):121-167, 1998.
Y. Chen, E. K. Garcia, M. R. Gupta, A. Rahimi, and L. Cazzanti. Similarity-based classification: concepts and algorithms. Journal of Machine Learning Research, 10(3), 2009.
C. P. Diehl and G. Cauwenberghs. SVM incremental learning. adaptation and optimisation. In Proceedings of the International Joint Conference Neural Networks, (IJCNN 2003), volume pages 2685-2690. IEFE, 2003.
D. Dua and C. Graff. UCI machine learning repository, 2017. URL http::/aarchiiv...c... uci edu/ml
P. I. Frazier. A tutorial on Bayesian optimisation. arXiv preprint arXiv:1807.02811, 2018.
M. G. Genton. Classes of kernels for machine learning: statistics perspective. Journal of Machine Learning Research, 2(Dec):299-312 2001.
M. Gönen and E. Alpaydın. Multiple kernel learning algorithms. Journal of Machine Learning Research, 12:2211-2268, 2011.
T. Hofmann, B. Schölkopf, and A. J. Smola. Kernel methods in machine learning. The Annals of Statistics, pages 1171-1220, 2008.
K. E. Iverson. programming language. John Wiley & Sons, USA, 1962. ISBN 0471430145.
P. A. Jang, A. Loeb, M. Davidow, and A. G. Wilson. Scalable Lévy process priors for spectral kernel learning. In Advances in Neural Information Processing Systems (NeurIPS 20/7), pages 3940-3949, 2017.
M. Kanagawa, P. Hennig, D. Sejdinovic, and B. K. Sriperumbudur, Gaussian processes and kernel methods: a review on connections and equivalences. arXiv preprint 1 2018.
Kirschner, M. Mutný, N. Hiller, R. Ischebeck, and A. Krause. Adaptive and safe Bayesian optimisation in high dimensions via one-dimensional subspaces. arXiv preprint arXiv:1902.03229 2019.
H. J. Kushner. A new method of locating the maximum point of an arbitrary multipeak curve the presence of noise. Journal of Basic Engineering, 86:97-106, 1964.
G. Malkomes, C. Schaff, and R. Garnett. Bayesian optimization for automated model selec- tion. In Advances in Neural Information Processing Systems (NeurIPS 2016), volume 29, Cur- Associates, Inc., 2016. URL https: 3b1F
Paper pdf
Močkus. On Bayesian methods for seeking the extremum. In Optimisation Techniques IFIP Technical Conference, pages 400-404. Springer, 1975.

---

D. Oglic and T. Gärtner. Learning in reproducing kernel Krein spaces, In Proceedings of the 35th International Conference on Machine Learning (ICML 2018), 2018.
D. Oglic and T. Gärtner. Scalable learning in reproducing kernel Krein spaces. In Proceedings of the 36th International Conference on Machine Learning (ICML 2019), pages 4912 2019.
C. S. Ong and A. J. Smola. Machine learning with hyperkernels. In Proceedings of the 20th International Conference Machine Learning (ICML. 2003), pages 568-575, 2003.
C. S. Ong, R. C. Williamson, and A. J. Smola. Hyperkernels. In Advances in Neural Information Processing Systems (NeurIPS 2003), pages 495-502, 2003.
C. S. Ong, X. Mary, Canu, and A. J. Smola. Learning with non-positive kernels. Proceedings of the 21st International Conference Machine Learning (ICML 2004), page 81, 2004.
C. Ong, A. J. Smola, and R. C. Williamson. Learning the kernel with hyperkernels. Journal of Machine Learning Research, 60ul):1043-1071, 2005. 2005.
A. Rakotomamoniy, Bach, S. Canu, and Y. Grandvalet. More efficiency in multiple kernel learning. In Proceedings of the 24th International Conference on Machine Learning (ICML 2007), pages 775-782, 2007.
B. Scholkopf and A. J. Smola. Learning with kernels: support vector machines, regularisation, optimisation, and beyond. MIT Press, Cambridge, MA, USA, 2001. ISBN 0262194759.
B. Shahriari, K. Swersky, Z. Wang, R. P. Adams, and N. De Freitas. Taking the human out of the loop: a review of Bayesian optimisation. Proceedings of the IEEE, 104(1):148-175, 2015.
A. Shilton, S. Rana, S. Gupta, and S. Venkatesh. Sequential subspace search for functional Bayesian optimisation incorporating experimenter intuition. arXiv preprint arXiv:2009.0354: 2020.
N. Srinivas, A. Krause, S. M. Kakade, and M. W. Seeger. Information-theoreti regret bounds for Gaussian process optimisation in the bandit setting. IEEE Transactions Information Theory, 58 (5):3250-3263 2012.
M. Stein. Interpolation of spatial data: some theory for kriging. Springer, 02 2015. doi: 10.1007/ 978-1-4612-1494-6
I. Steinwart and A. Christmann. Support vector machines. Springer Science & Business Media, 2008.
L. Vandenberghe and S. Boyd. Semidefinite programming, SIAM Rev, 38(1):49-95, Mar. 1996.
ISSN 0036- 1445. doi: 10. 10.1137/103800) /tt. 11t../1111111888
V. N. Vapnik. An overview of statistical learning theory. IEEE Transactions on Neural Networks, 10 99:9988999, 1999.
Vellanki, S. Rana, Gupta, D. de Celis Leal, A. Sutti, M. Height, and S. Venkatesh. Bayesian functional optimisation with shape prior. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI 2019), volume 33, pages 1617-1624, 2019.
N. A. Vien, H. Zimmermann, and M. Toussaint. Bayesian functional optimisation. In Proceedings of the 32nd AAAI Conference Artificial Intelligence (AAAI 2018), pages 4171-4178, 2018.
Z. Wang, F. Hutter, M. Zoghi, D. Matheson, and N. de Feitas. Bayesian optimisation in a billion dimensions via random embeddings. Journal of Artificial Intelligence Research, 55:361-387, 2016.
C. K. Williams and C. E. Rasmussen. Gaussian processes for machine learning, volume 2. MIT press Cambridge, MA, 2006.
A. Wilson and R. Adams. Gaussian process kemels for pattern discovery and extrapolation. In Proceedings of the 30th International Conference on Machine Learning (ICMI. 2013), pages 1067-1075, 2013.
12

---

J. Wilson, F. Hutter, and M. Deisenroth. Maximising acquisition functions for Bayesian optimisation. In Advances Neural Information Processing Systems (NeurIPS 2018), pages 9884 1884-9895, 2018.
Wold, K. Esbensen, and P. Geladi. Principal component analysis. Chemometrics and Intelligent Laboratory Systems, 2(1-3):37-52, 1987.
Y. Ying, C. Campbell, and M. Girolami. Analysis of SVM with indefinite kernels. In Advances in Neural Information Processing Systems (NeurIPS 2003), volume 22. Curran Associates, Inc., 2009.
C. Zhang, C. Liu, X. Zhang, and G. Almpanidis. An up-to-date comparison of state-of-the-art classification algorithms. Expert Systems with Applications, 82: 12:122-150, 2017.
13


Reviews:
[{"review_id": "lpzP9SzcWs3", "reviewer": "Reviewer_ngk1", "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nPaper also also provides sound theoretical justification in terms of regret convergence of  of proposed algorithm as parameters of the effective dimension. \n\nProjection 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.\n\nEvaluation 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.\n\nTable 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? \n\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Paper addresses technical limitations well but does not address effect of model/data bias and explainability of learned models. ", "review_text": "", "extra_scores": {"ethical_concerns": "No specific ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "j52iL35p5jI", "reviewer": "Reviewer_gTjs", "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nSection 2 and 3 are clear enough.\nThe 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.\nThe 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.\nIt 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.\n\nThe experimental part seems more interesting. \nOverall, this work has a good potential but the theoretical part should be polished.\n\nTypos:\n- l.17 parameterise -> parameterize \n- l.79 symbol of average regret\n- l.241 space of f ? if f(K) is real no need for ||.||_{H_k}.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "Ueas9mffuJB", "reviewer": "Reviewer_Bqt6", "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality. Using the Bayesian optimization for kernel selection has been previously proposed in\n\nMalkomes et al. Bayesian optimization for automated model selection. NIPS 2016. \n\nThere 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.\n\nQuality. The paper is technically sound. The authors provide a convergence analysis of the proposed method. \n\nClarity. The paper is clearly written. \n\nOne 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. \n\nSignificance. 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. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Rvw8_MSK8g", "reviewer": "Reviewer_Fbiv", "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "However, there are still some issues should be addressed as follows:\n1. In Line 163, \\beta is a vector and should be in boldface. Moreover, the author should use upper case to represent the test set.\n2. This paper involves a lot of basic knowledge. The author should give more detailed introduction.\n3. What does GP-UCB mean in the Line 76? To increase the readability, the author should give some necessary descriptions in the main paper.\n4. 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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "15"}, "extra_text": {}}, {"review_id": "8VZJTOdQvTs", "reviewer": "Reviewer_1xJM", "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nMajor comments:\n-\tClipping: 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.\n-\tSynthetic 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.\nOverall, 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?\n\nMore 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.\n\nMinor comments:\n\n7 I would suggest citing the Ong et al. 2005 paper directly in the abstract since it serves as the main source for the procedure\n\n110 Hilbert with uppercase\n\n119  ``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.\n\n207 this should be a $\\succcurlyeq$\n\n209-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.\n\n225 Euclidean with uppercase\n\n240 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).\n\n241 Why underline the kernels? They have the same interpretation as the ones of Eq. (5).\n\n244 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?\n\n319 In Table 1, what is $\\dagger$ referring to?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "Three hours"}, "extra_text": {}}]

Author rebuttal:

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)