--- title: "Hypothesis Sketching for Online Kernel Selection in Continuous Kernel Space" authors: - "Xiao Zhang" - "Shizhong Liao" doi: "10.24963/ijcai.2020/346" url: "https://ijcai.org/proceedings/2020/346" pdf: "https://ijcai.org/proceedings/2020/0346.pdf" venue: "Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence" year: 2020 pages: "2498-2504" track: "Main track" keywords: - "Machine Learning: Kernel Methods" - "Machine Learning: Online Learning" - "Machine Learning: Learning Theory" --- # Hypothesis Sketching for Online Kernel Selection in Continuous Kernel Space Xiao Zhang, Shizhong Liao *Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence*, pages 2498-2504. DOI: [10.24963/ijcai.2020/346](https://doi.org/10.24963/ijcai.2020/346) ## Abstract Online kernel selection in continuous kernel space is more complex than that in discrete kernel set. But existing online kernel selection approaches for continuous kernel spaces have linear computational complexities at each round with respect to the current number of rounds and lack sublinear regret guarantees due to the continuously many candidate kernels. To address these issues, we propose a novel hypothesis sketching approach to online kernel selection in continuous kernel space, which has constant computational complexities at each round and enjoys a sublinear regret bound. The main idea of the proposed hypothesis sketching approach is to maintain the orthogonality of the basis functions and the prediction accuracy of the hypothesis sketches in a time-varying reproducing kernel Hilbert space. We first present an efficient dependency condition to maintain the basis functions of the hypothesis sketches under a computational budget. Then we update the weights and the optimal kernels by minimizing the instantaneous loss of the hypothesis sketches using the online gradient descent with a compensation strategy. We prove that the proposed hypothesis sketching approach enjoys a regret bound of order O(√T) for online kernel selection in continuous kernel space, which is optimal for convex loss functions, where T is the number of rounds, and reduces the computational complexities at each round from linear to constant with respect to the number of rounds. Experimental results demonstrate that the proposed hypothesis sketching approach significantly improves the efficiency of online kernel selection in continuous kernel space while retaining comparable predictive accuracies. ## Full text ## 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. Table 1: Comparisons between the proposed OKS-SIL and OKS, OKL-GD for convex functions (T: the number of rounds, N: the number of candidate kernels; t: the index of the round; B: the budget, a constant; Candidate kernels: the number of candidate kernels; "-": not available). | Approach | Computational complexities - Time (round t) | Computational complexities - Time (overall) | Computational complexities - Space | Regret guarantees - Candidate kernels | Regret guarantees - Regret bound | |------------|-----------------------------------------------|-----------------------------------------------|--------------------------------------|-----------------------------------------|------------------------------------| | OKS | O(N + t) | O(T 2 +NT) | O(T) | N | O (N √T ) | | OKL-GD | O(t) | O(T 2 ) | O(T) | Continuously many | - | | OKS-SIL | O(B) | O(BT ) | O(B) | Continuously many | O (√T ) | ## 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/](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. Table 2: The mistake rates (Mistake) and running time (Time) of OKL-GD, OKS, Proj-KA and our OKS-SIL after T rounds for online classification task. | Algorithm | german - Mistake (%) | german - Time (s) | svmguide3 - Mistake (%) | svmguide3 - Time (s) | spambase - Mistake (%) | spambase - Time (s) | mushrooms - Mistake (%) | mushrooms - Time (s) | |-------------|------------------------|---------------------|---------------------------|------------------------|--------------------------|-----------------------|---------------------------|------------------------| | OKS-SIL | 29.610 ± 0.363 | 0.250 | 21.480 ± 0.624 | 0.170 | 28.209 ± 0.104 | 1.526 | 0.351 ± 0.420 | 1.785 | | OKL-GD | 30.990 ± 0.899 | 0.217 | 23.821 ± 0.407 | 0.208 | 31.869 ± 0.145 | 5.567 | 3.957 ± 1.623 | 39.625 | | OKS | 42.590 ± 1.049 | 0.253 | 29.879 ± 0.852 | 0.287 | 34.432 ± 0.282 | 3.965 | 7.749 ± 0.532 | 7.690 | | Proj-KA | 38.280 ± 1.405 | 2.318 | 25.567 ± 0.829 | 3.307 | 30.596 ± 0.293 | 35.336 | 0.375 ± 0.415 | 175.815 | | Algorithm | a9a | a9a | w7a | w7a | ijcnn1 | ijcnn1 | cod-rna | cod-rna | | Algorithm | Mistake (%) | Time (s) | Mistake (%) | Time (s) | Mistake (%) | Time (s) | Mistake (%) | Time (s) | | OKS-SIL | 23.753 ± 0.502 | 32.026 | 2.975 ± 0.012 | 72.826 | 9.574 ± 0.327 | 23.392 | 12.989 ± 0.201 | 89.190 | | OKL-GD | 23.929 ± 0.436 | 319.956 | 2.973 ± 0.010 | 434.908 | 9.582 ± 0.322 | 110.356 | 13.558 ± 0.225 | 109.410 | | OKS | 24.302 ± 0.512 | 983.808 | 7.199 ± 0.860 | 837.220 | 9.873 ± 0.412 | 519.114 | 12.927 ± 0.707 | 1786.890 | | Proj-KA | 23.901 ± 0.471 | 321.434 | 5.430 ± 1.816 | 622.044 | 11.940 ± 1.540 | 212.476 | 15.151 ± 0.304 | 163.144 | ## 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. Figure 1: Average mistake rate and average runtime of OKS-SIL using different budget B, sampling size s and RLD parameter ν of RLD condition (1) on spambase. ![Image](https://ijcai.org/proceedings/2020/fulltext/346/image_000000_e787c5f1b8d15bb57d13173121042ba05e7500017436fa6514b55e0aeee0a03c.png) ## Acknowledgements This work was supported in part by the National Natural Science Foundation of China (No. 61673293). ## References 1. [Auer et al., 2002] Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic mul- tiarmed bandit problem. SIAM Journal on Computing, 32(1):48-77, 2002. 2. [Cesa-Bianchi and Lugosi, 2006] Nicolò Cesa-Bianchi and Gabor Lugosi. Prediction, learning, and games. Cam- bridge University Press, 2006. 3. [Chen et al., 2016] Badong Chen, Junli Liang, Nanning Zheng, and José C Príncipe. Kernel least mean square with adaptive kernel size. Neurocomputing, 191:95-106, 2016. 4. [Cortes et al., 2012] Corinna Cortes, Mehryar Mohri, and Afshin Rostamizadeh. Algorithms for learning kernels based on centered alignment. Journal of Machine Learn- ing Research, 13:795-828, 2012. 5. [Crammer et al., 2003] Koby Crammer, Jaz Kandola, and Yoram Singer. Online classification on a budget. In Advances in Neural Information Processing Systems 16, pages 225-232, 2003. 6. [Diethe and Girolami, 2013] Tom Diethe and Mark Giro- lami. Online learning with (multiple) kernels: A review. Neural Computation, 25(3):567-625, 2013. 7. [Ding et al., 2018] Lizhong Ding, Shizhong Liao, Yong Liu, Peng Yang, and Xin Gao. Randomized kernel selection with spectra of multilevel circulant matrices. In Proceed- ings of the 32nd AAAI Conference on Artificial Intelli- gence, pages 2910-2917, 2018. 8. [Foster et al., 2017] Dylan J Foster, Satyen Kale, Mehryar Mohri, and Karthik Sridharan. Parameter-free online learning via model selection. In Advances in Neural Infor- mation Processing Systems 30, pages 6022-6032, 2017. 9. [Freund and Schapire, 1999] Yoav Freund and Robert E Schapire. Large margin classification using the perceptron algorithm. Machine learning, 37(3):277-296, 1999. 10. [Hazan, 2016] Elad Hazan. Introduction to online convex optimization. Foundations and Trends R in Optimization, 2(3-4):157-325, 2016. 11. [Hu et al., 2015] Junjie Hu, Haiqin Yang, Irwin King, Michael R Lyu, and Anthony Man-Cho So. Kernelized online imbalanced learning with fixed budgets. In Pro- ceedings of the 29th AAAI Conference on Artificial Intelli- gence, pages 2666-2672, 2015. 12. [Kandola et al., 2002] J. Kandola, J. Shawe-Taylor, and N. Cristianini. On the extensions of kernel alignment. Technical Report Technical report 120, University of Lon- don, 2002. 13. [Kivinen et al., 2001] Jyrki Kivinen, Alex J Smola, and Robert C Williamson. Online learning with kernels. In Advances in Neural Information Processing Systems 14, pages 785-792, 2001. 14. [Liu et al., 2014] Yong Liu, Shali Jiang, and Shizhong Liao. Efficient approximation of cross-validation for kernel methods using bouligand influence function. In Proceed- ings of the 31st International Conference on Machine Learning, pages 324-332, 2014. 15. [Liu et al., 2018] Yong Liu, Hailun Lin, Lizhong Ding, Weiping Wang, and Shizhong Liao. Fast cross-validation. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pages 2497-2503, 2018. 16. [Minh, 2010] Ha Quang Minh. Some properties of Gaussian reproducing kernel Hilbert spaces and their implications for function approximation and learning theory. Construc- tive Approximation, 32(2):307-338, 2010. 17. [Nguyen et al., 2017] Tu Dinh Nguyen, Trung Le, Hung Bui, and Dinh Q. Phung. Large-scale online kernel learning with random feature reparameterization. In Proceedings of the 26th International Joint Conference on Artificial In- telligence, pages 2543-2549, 2017. 18. [Orabona et al., 2008] Francesco Orabona, Joseph Keshet, and Barbara Caputo. The projectron: A bounded kernel- based perceptron. In Proceedings of the 25th International Conference on Machine learning, pages 720-727, 2008. 19. [Shalev-Shwartz, 2011] Shai Shalev-Shwartz. Online learn- ing and online convex optimization. Foundations and Trends R in Machine Learning, 4(2):107-194, 2011. 20. Abhishek Singh and José C. Príncipe. Information theoretic learning with adaptive ker- nels. IEEE Transactions on Signal Processing, 91(2):203- 213, 2011. 21. [Yang et al., 2012] Tianbao Yang, Mehrdad Mahdavi, Rong Jin, Jinfeng Yi, and Steven C.H. Hoi. Online kernel se- lection: Algorithms and evaluations. In Proceedings of the 26th AAAI Conference on Artificial Intelligence, pages 22-26, 2012. 22. [Yukawa, 2015] Masahiro Yukawa. Adaptive learning in Cartesian product of reproducing kernel Hilbert spaces. IEEE Transactions on Signal Processing, 63(22):6037- 6048, 2015. 23. [Zhang and Liao, 2018] Xiao Zhang and Shizhong Liao. On- line kernel selection via incremental sketched kernel align- ment. In Proceedings of the 27th International Joint Con- ference on Artificial Intelligence, pages 3118-3124, 2018. 24. [Zhang and Liao, 2019] Xiao Zhang and Shizhong Liao. In- cremental randomized sketching for online kernel learn- ing. In Proceedings of the 36th International Conference on Machine Learning, pages 7394-7403, 2019. 25. [Zhang et al., 2019] Xiao Zhang, Yun Liao, and Shizhong Liao. A survey on online kernel selection for online kernel learning. WIREs Data Mining and Knowledge Discovery, 9(2):e1295, 2019. 26. [Zhao et al., 2012] Peilin Zhao, Jialei Wang, Pengcheng Wu, Rong Jin, and Steven C.H. Hoi. Fast bounded online gra- dient descent algorithms for scalable kernel-based online learning. In Proceedings of the 29th International Confer- ence on Machine Learning, pages 169-176, 2012. 27. [Zinkevich, 2003] Martin Zinkevich. Online convex pro- gramming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Ma- chine Learning, pages 928-936, 2003.