Hypothesis Sketching for Online Kernel Selection in Continuous Kernel Space

1 Introduction

Online kernel learning obtains hypotheses incrementally in a reproducing kernel Hilbert space in a single-pass over the data, which aims to make a sequence of accurate predictions [Freund and Schapire, 1999; Kivinen et al., 2001;

∗Corresponding author

Crammer et al., 2003; Zhang and Liao, 2019]. Since the performance of online kernel learning significantly depends on the chosen kernel, kernel selection is critical to online kernel learning. In the literature of online kernel learning, the kernel function is typically chosen beforehand, which is not theoretically sound and needs multiple passes over all the data. In batch learning settings, most of the offline kernel selection approaches, such as cross-validation [Liu et al., 2014; Liu et al., 2018] and randomized kernel selection [Ding et al., 2018], first learn the hypotheses on the training data for each candidate kernel, and then select the optimal kernel on the validation data. But in online learning settings, there is no such delineation among training, validation and testing [Diethe and Girolami, 2013; Zhang et al., 2019]. The selection of optimal kernels for online kernel learning is more challenging than offline kernel selection, which only has access to the arrived data for kernel selection at each round, must construct the hypothesis space incrementally in low computational complexities, and requires a sublinear regret without i.i.d. assumption. Given candidate kernels, we refer to the dynamic selection of the optimal kernel at each round for online kernel learning as online kernel selection, which intermixes kernel selection and training, and requires a sublinear regret and constant computational complexities at each round. We call an online kernel selection problem using a continuous kernel space containing continuously many candidate kernels the continuous online kernel selection problem, and that using a discrete kernel set containing a finite number of candidate kernels the discrete online kernel selection problem.

Recently, several online kernel selection approaches have been presented. Foster et al. [2017] presented a metaalgorithm framework using the multi-scale aggregation for online model selection, which can be used for discrete online kernel selection. This meta-algorithm framework enjoys a sublinear regret bound that is suitable for multi-scale losses. Yang et al. [2012] formulated a randomized online kernel selection approach, which measures the relative importance of the candidate kernels by maintaining a probability distribution via an exponential weighted average [Auer et al., 2002; Cesa-Bianchi and Lugosi, 2006]. This randomized online kernel selection approach to discrete online kernel selection has a quadratic overall time complexity and a linear space complexity with respect to the number of rounds. To address this issue, Zhang et al. [2018] proposed a randomized approach using a novel kernel alignment for discrete online kernel selection with a strongly convex loss function, which has constant computational complexities at each round. These two randomized approaches have sublinear regret bound for discrete online kernel selection, but cannot be applied to continuous online kernel selection with regret guarantees. Besides, they are not efficient for online kernel selection with a large number of candidate kernels. Adaptive kernel is another kind of online kernel selection approaches that use the gradient descent to minimize the losses for the updating of the hypotheses and the kernel parameters [Singh and Pr´ıncipe, 2011; Chen et al., 2016; Nguyen et al., 2017]. Although existing adaptive kernel approaches can be applied to continuous online kernel selection, they do not have sublinear regret guarantees that are essential for online kernel learning.

The aim of this paper is to propose a novel hypothesis sketching approach to continuous online kernel selection, which is theoretically solid and computationally efficient. We construct the hypothesis sketches by the basis function vector sketching and the weight vector sketching. Then we define the instantaneous loss of the hypothesis sketches, and use the gradient of this instantaneous loss to update the optimal kernel at each round. For regret analysis, we decompose the regret for continuous online kernel selection into three terms and derive a sublinear regret bound. When applied to continuous online kernel selection, our hypothesis sketching approach has only linear time and space complexities with respect to the budget at each round. Finally, we empirically demonstrate that our hypothesis sketching approach to online kernel selection achieves better performance than the existing approaches in efficiency with a comparable accuracy.

2 Notations and Background

Let R and R+ be the set of real numbers and the set of positive real numbers, respectively. Let [T] = {1, 2, . . . , T}, [·]+ be the function satisfying [a]+ = a when a > 0 and [a]+ = 0 when a ≤ 0, S = {(xi, yi)}Ti=1 ⊆ (X × Y)T be the sequence of T instances, where X ⊆ Rd and Y = {-1, 1}. We denote the Moore-Penrose pseudoinverse of A by A† , the loss function by ℓ : Y × Y → R+ ∪ {0}, the kernel function by κ : X × X → R and its corresponding kernel matrix by K = (κ(xi, xj)) ∈ RT×T . The reproducing kernel Hilbert space (RKHS) associated with κ is defined as Hκ = span{κ(·, x) : x ∈ X}. We denote a set containing N candidate kernels for online kernel selection by KN = {κi}Ni=1 .

Given a candidate kernel set KN = {κi}Ni=1 , online kernel selection is to update the hypothesis and select the optimal kernel from KN at each round in an online setting, which requires a sublinear regret guarantee and low computational complexities. Given convex loss functions, Yang et al. [2012] proposed a randomized kernel selection approach to discrete online kernel selection, which enjoys the regret bound of order O(N √T) against the optimal hypothesis in hindsight

But the regret bound of order O(N √T) for online kernel selection is invalid for continuous online kernel selection due to the unbounded regret when N → ∞. In this paper, we propose an efficient hypothesis sketching approach to online kernel selection, which enjoys a sublinear regret bound for continuous online kernel selection.

3 Novel Hypothesis Sketching Approach

In this section, we propose a novel hypothesis sketching approach, which has an efficient computation and can be applied to continuous online kernel selection with regret guarantees. We first define the hypothesis sketches as follows. Let

be the basis function vector, where Vt = {˜x1, . . . , ˜x|Vt|} is the buffer of examples at round t and |Vt| is the size of Vt, and

be the weight vector. Then we call

the hypothesis sketch for prediction at round t, which can be seen as an approximation of the original hypothesis over the first t - 1 instances 1 :

where {β∗ t,i }i∈[t-1] is the set of the optimal coefficients of the original hypothesis. Then we give the novel hypothesis sketching approach under a fixed budget. Specifically, we restrict the size of the hypothesis sketch ft(·) by |Vt| ≤ B at each round, where the budget B > 0. The novel hypothesis sketching approach includes the following two steps: the basis function vector sketching and the weight vector sketching.

Basis Function Vector Sketching: We first define a criterion to maintain the basis function vector of the hypothesis sketch, called randomized linear dependency condition. At round t, we use the inner product to measure the correlation between the newly arrived kernel function κ(·, xt) and the j-th kernel function in the basis function vector as follows:

which yields a probability vector

We regard pt as a multinomial distribution in the probability simplex on [|Vt|], and sample s (s ≪ |Vt|) kernel functions without replacement from the basis function vector according to pt, where the indices of the sampled kernel functions are k(t) j ∈ [|Vt|], j = 1, 2, . . . s. Then the Randomized Linear Dependency (RLD) condition at round t is given by

1 It follows from the representer theorem that it is sufficient to consider the original hypothesis of the linear combination form.

where ν > 0 is the RLD parameter and

RLD condition measures the linear dependency between the newly arrived kernel function and the random subset of the kernel functions in the basis function vector. Solving the minimization problem in (1) yields the optimum solution

where

and

Given a budget B, if |Vt| < B at round t, we directly insert the kernel function κ(·, xt) into the basis function vector. Next, we consider the case that the size of the basis function vector reaches the budget, i.e., |Vt| = B. When RLD condition holds, we delete the kernel function κ(·, ˜xrt ) with the smallest weight

and insert κ(·, xt) into the basis function vector, which is equivalent to Vt+1 = Vt \ {˜xrt } ∪ {xt}, otherwise set Vt+1 = Vt. Finally, we can obtain the updated basis function vector

and the hypothesis sketch after the basis function vector sketching as f b t (·) = 〈ω(t) ,ψ(t+1) κ (·)〉.

Weight Vector Sketching: After the basis function vector sketching, we maintain the weight vector of the hypothesis sketch. Given a convex loss function ℓ(·, ·), at round t, instead of the instantaneous loss of the original hypothesis, we define the Sketched Instantaneous Loss (SIL) of the hypothesis sketch f b t (·) by

Then, given a stepsize η > 0, we update the weight of the hypothesis sketch f b t (·) using the Kernelized Online Gradient Descent (KOGD) [Kivinen et al., 2001] for SIL as follows:

The key ingredient of the weight vector sketching is to compensate the weight vector when ignoring the newly arrived examples. When |Vt| < B, we obtain Vt+1 = Vt ∪ {xt} and insert the following weight into the weight vector

When the budget has been reached, we discuss the weight vector sketching in two cases: (a) for the case that RLD condition does not hold, we compensate the weight vector as

where i ∈ {k(t) 1 , . . . , k(t) s } and α∗ t (i) is the i-th component of α∗t in (2); (b) for the case that RLD condition holds, we replace κ(·, ˜xrt ) with κ(·, xt) in the basis function vector,

and obtain the weight corresponding to κ(·, xt) as

We finally obtain the hypothesis sketch after weight vector sketching as

4 Application to Online Kernel Selection

In this section, we apply the proposed hypothesis sketching approach to continuous online kernel selection. Specifically, we update the optimal kernel at each round to determine the reproducing kernel Hilbert space (RKHS) in which the prediction and the hypothesis sketching are performed at the next round. In this paper, we focus on the continuous kernel space containing differentiable candidate kernels, denoted by KΩ = {κσ| σ ∈ Ω}, where Ω is the kernel parameter space of KΩ and κσ is the kernel function with the kernel parameter σ ∈ Ω. For convenience, in the following sections, we denote ψ(t+1) κσ (·) byψ(t+1) σ (·). At round t, we select the optimal kernel σt+1 by minimizing SIL of the hypothesis sketch f w t (·) = 〈ω(t+1) ,ψ(t+1) σt (·)〉 as follows:

When the buffer Vt is changed, i.e., Vt+1 ̸= Vt, we update the optimal kernel by minimizing (3) using the online gradient descent [Zinkevich, 2003] as follows:

where ρ > 0 is the stepsize. After the hypothesis sketching and the optimal kernel updating at round t, we obtain the hypothesis sketch for prediction at round t + 1 as follows:

Next, we specify the loss function and the candidate kernels. For a hinge loss function ℓ (f(x), y) = [1 - yf(x)]+, ∇f(x)SIL(f(x)) is -y if yf(x) < 1 and 0 otherwise. For a candidate Gaussian kernel function 2

we set γ = 1/(2σ2 ) and denote this Gaussian kernel function by κγ(x1, x2) = exp (-γ‖x1 -x2‖2 ) . Then, (4) is equivalent to

We finally summarize the above stages into Algorithm 1, called OKS-SIL.

5 Theoretical Analysis

In this section, we prove the regret bound of our hypothesis sketching approach to continuous online kernel selection, analyze the computational complexities of our approach, and compare our approach with the existing online kernel selection approaches with respect to the theoretical results.

2 The optimal kernel updating in (4) can be directly applied to different types of candidate kernels, including the anisotropic RBF kernels and other differentiable kernels.

Algorithm 1 OKS-SIL Algorithm

Require: The stepsizes η and ρ, budget B, RLD parameter

ν, sampling size s, initial kernel parameter σ1 1: Initialize the weight vector ω(1) = 0 and the buffer V1 = ∅ 2: for t = 1, . . . , T do 3: Compute ψ(t) σt (xt) = [κσt (xt, ˜x1), . . . , κσt (xt, ˜x|Vt|)]ᵀ 4: Compute ft(xt) = 〈ω(t) ,ψ(t) σt (xt)〉 5: Predict ˆ yt = sgn(ft(xt)) 6: if ytft(xt) < 1 then 7: if |Vt| < B then 8: Vt+1 = Vt ∪ {xt} 9: else 10: if RLD condition holds then 11: Set rt = argmini∈[|Vt|] |ω(t) i | 12: Vt+1 = Vt \ {˜xrt } ∪ {xt} 13: else 14: Vt+1 = Vt 15: end if 16: end if 17: Update ω(t+1) using KOGDwith the compensation 18: if Vt+1 ̸= Vt then 19: Update the optimal kernel using γt+1 = γt - ρyt ∑|Vt+1| j=1 ω(t+1) j κγt (xt, ˜xj)‖xt - ˜xj‖2 20: end if 21: end if 22: end for

5.1 Regret Analysis

Consider a continuous kernel space KΩ containing candidate Gaussian kernels with the kernel parameter space Ω = {σ|σ ∈ [σmin, σmax]}, where σmin, σmax ∈ R+. For convenience, we denote the Gaussian RKHS associated with the kernel parameter σ by Hσ in the following theoretical analysis. In contrast to the regret analysis for online kernel learning in a given hypothesis space, the key challenge of the regret analysis for continuous online kernel selection is to bound the regret of a hypothesis sequence in an incrementally constructed hypothesis space. Our goal is to analyze the regret against the optimal hypothesis f ∗ with the optimal kernel κσ∗ as follows:

where f ∗ (·) = 〈ω∗ ,ψ∗σ∗(·)〉. Since Gaussian RKHS has a nested structure [Minh, 2010; Yukawa, 2015] as Hσmax ⊆ Hσ ⊆ Hσmin , σ ∈ Ω, it is reasonable to assume that

Let ¯ f ∗ σt (·) = 〈ω∗ , ψ∗σt (·)〉 and denote the optimal hypothesis in hindsight in Hσt by f ∗ σt . Finally, we demonstrate the regret bound of the proposed hypothesis sketching approach to continuous online kernel selection as in Theorem 1.

Theorem 1 (Regret Bound). Let ℓ(·, ·) be a hinge loss function, KΩ be a continuous kernel space containing Gaussian kernels with the kernel parameter space Ω = {σ|σ ∈ [σmin, σmax]}, and C(ν) be a decreasing function of ν which is of order O(lnT) of magnitude. For any sequence of T instances S = {(xi, yi)}Ti=1 ⊆ (X × Y)T , let Cmax = maxi,j∈[T] ‖xi - xj‖2 , assume that maxt∈[T] |∇σt f w t (xt)| ≤ L and σmax < min˜xi,˜xj∈V, ˜xi̸=˜xj ‖˜xi - ˜xj‖/√3, V = ∪Tt=1Vt. Then, let {ft}Tt=1 be the hypothesis sequence generated by Algorithm 1, we have

Proof Sketch. We first decompose the instantaneous regret at round t into the following three terms

where Regt(a, b) := ℓ(a(xt), yt) - ℓ(b(xt), yt). Then we prove the upper bounds of the three terms by bounding the gradient errors of the hypothesis sketches, and obtain the final regret bound.

Remark 1. For online classification, it is reasonable to assume that the values of the hypotheses are O(1/√T) as in [Zhao et al., 2012; Hu et al., 2015], because it does not have any influence on the prediction when multiplying the weight vector by a factor of order O(1/√T). Besides, it is a reasonable assumption that S is compact in online learning [Cesa-Bianchi and Lugosi, 2006], which indicates that Cmax is a positive constant. Then, for ∀t ∈ [T], we assume that S is compact and |f ∗ σt (xt)| , | ¯ f ∗ σt (xt)|, |f w t (xt)| are of the order of O(1/√T ), which yields Rb = O(√T ) and W = O(1/√T ). Setting η, ρ = O(1/√T ) and ν = O(1/T ), we obtain a O(√T) regret bound for continuous online kernel selection that is optimal for convex loss functions and an online gradient descent approach [Shalev-Shwartz, 2011; Hazan, 2016].

5.2 Complexity Analysis

At each round, for the basis function vector sketching, constructing the multinomial distribution has a linear time complexity with respect to the budget B, and computing the RLD condition is in O(s3 ) time complexity, where s is the sampling size and s ≪ B. The time complexities of the weight vector sketching and the optimal kernel updating are O(s) and O(B), respectively. Therefore, the time complexity of OKS-SIL at each round is O(B), where B is the budget of the hypothesis sketches which is a constant. Since OKS-SIL only stores the hypothesis sketch under the budget B, the total space complexity of OKS-SIL is O(B). Table 1 summarizes the theoretical results of our OKS-SIL, OKS [Yang et al., 2012] and OKL-GD [Chen et al., 2016]. From Table 1, we have the following observations: (a) our OKS-SIL reduces the time and space complexities at each round from linear to constant with respect to the number of rounds; (b) for continuous online kernel selection, in contrast to the existing approaches without regret guarantees, our OKS-SIL enjoys a sublinear regret bound.

6 Experiments

In this section, we present experimental results to demonstrate the effectiveness and efficiency of our OKS-SIL. We compared OKS-SIL algorithm with the following state-ofthe-art online kernel selection algorithms: (a) OKS [Yang et al., 2012] maintains a probability distribution for discrete online kernel selection, and updates the optimal kernel and the hypothesis at each round according to this distribution; (b) OKL-GD [Chen et al., 2016] uses KOGD to minimize the squared loss for the hypothesis updating and the kernel parameter updating 3 ; (c) Similar to the two-stage approach [Cortes et al., 2012], the two-pass algorithm Proj-KA uses the first m = min{T, 104 } instances to form a validation set, selects the kernel using the kernel alignment criterion [Kandola et al., 2002] on the validation set, and runs Projectron [Orabona et al., 2008] with the selected kernel. For each benchmark dataset 4 we merged the training and testing data into a single dataset. Experiments were conducted over 20 different random permutations of the datasets and all the algorithms were implemented in R 3.3.2 on a PC with 3.60 GHz Intel Core i7 CPU and 16GB memory. The mistake rate is used to evaluate the performance for classification, which is defined by ∑Tt=1 I(ytft(xt) < 0)/T × 100.

We chose a set of Gaussian kernels with kernel parameters σ ∈ {2-(i+1)/2 , i = [-12 : +1 : 12]} as the discrete candidate kernel set for OKS and Proj-KA, and restricted the kernel parameter space of OKS-SIL and OKLGD to the closed interval Ω = [2-6.5 , 25.5 ] for fair comparison. The index i of the initial kernel parameter was chosen in [-12 : +1 : -6] using uniform sampling, for avoiding the vanishing of the initial gradient. For our OKS-SIL, we set B = 150 for the small datasets (T < 104 ), B = 200 for the other datasets (T ≥ 104 ), and ν = 0.9, s = 3 according to the empirical analysis in the subsection "Parameter Influence". We used a time-varying stepsize ρt = 1/t at round t for optimal kernel updating, and tuned the stepsize of KOGD in a range 10[-5:+1:0] for all the algorithms. For OKS, we ran the algorithm in a single pass over the data with the smoothing parameter δ = 0.2 and the stepsize of weight updating η = √2(1- δ) lnN/NT as in [Yang et al., 2012]. For Projectron, we set the projection parameter U = 1/4√(B + 1)/ log(B + 1) as in [Orabona et al., 2008].

3 For the online classification task, we use the hinge loss instead of the squared loss, and limit the number of instances in memory to 2000 for OKL-GD to prevent the curse of kernelization.

4 http://www.csie.ntu.edu.tw/∼cjlin/libsvmtools/datasets/

6.1 Performance Evaluation

In this subsection, we evaluate the performances of OKS-SIL compared with OKL-GD, OKS, and Proj-KA for online classification on benchmark datasets. The results are listed in Table 2, including mistake rates (mean ± std) and running time after T rounds. From the results, we draw some observations as follows. First, the experimental results show that OKS-SIL is computationally more efficient than the other online kernel selection algorithms for online classification task when the number of rounds exceeds 1000. This is because the computation of the instantaneous loss on hypothesis sketches has a linear time complexity with respect to the budget per round, in comparison with the quadratic time complexity after T rounds of OKL-GD and OKS. Besides, the projection strategy of Projectron is in quadratic time complexity with respect to the budget B, while RLD condition in our hypothesis sketching approach is more efficient with a O(s3 ) time complexity, where s ≪ B. Second, OKS-SIL has lower mistake rates than other algorithms on most datasets for online classification, and preserves a comparable accuracy to the compared algorithms in terms of mistake rates on w7a and cod-rna, which demonstrates the effectiveness of OKS-SIL. The empirical performances of OKS-SIL conform to the regret analysis in Theorem 1. The main difference between OKL-GD and OKS-SIL is that, OKL-GD only updates the kernel parameter for the newly arrived kernel function, while OKS-SIL updates the kernel parameters for both the new kernel function and the previously chosen kernel functions, which yields better performances.

6.2 Parameter Influence

To analyze in more detail the behavior of OKS-SIL, we further conduct experiments with a range of values of B, s and ν on spambase. From the experimental results in Figure 1, we have the following observations for OKS-SIL.

For the budget B ∈ {50, 100, 200, 300, 400} in Figure 1 (a)-(b), we observe that the mistake rate of OKS-SIL decreases gradually with the increase of the budget while the runtime increases. But when the budget B > 50, the varying B has little influence on the accuracy of OKSSIL, which demonstrates the effectiveness of our hypothesis sketching approach in OKS-SIL. Figure 1 (c)-(d) show the performances of OKS-SIL using different sampling size s ∈ {1, 2, . . . , 6} in RLD condition. We can see that OKSSIL with larger sampling sizes has better empirical performances in terms of the mistake rate, and the mistake rate of OKS-SIL is no longer significantly reduced when the sampling size is relatively large. For a larger s, more values of kernel functions need to be computed for RLD condition, leading to a higher running time cost. The RLD parameter ν controls a trade-off between √ν and C(ν) in Ra in the regret bound of Theorem 1. From the results in terms of RLD parameter in Figure 1 (e)-(f), we can observe that OKS-SIL using RLD parameters closed to 1 yields better performances than that using other small RLD parameters, and OKS-SIL has a similar efficiency under different RLD parameters. The reason is that larger RLD parameters in (1) ensure that the kernel functions in the basis function vector are approximately orthogonal.

7 Conclusion

We have proposed a novel hypothesis sketching approach to online kernel selection in continuous kernel space, which is theoretically guaranteed and computationally efficient. Our sketching approach enjoys the optimal regret bound for online kernel selection, and has linear time and space complexities with respect to the budget at each round. The theoretical formulation and algorithmic implementation of the sketching mechanism are also promising for sketching approaches to online model selection and online learning.

Acknowledgements

This work was supported in part by the National Natural Science Foundation of China (No. 61673293).