--- title: "Online Kernel Selection via Incremental Sketched Kernel Alignment" authors: - "Xiao Zhang" - "Shizhong Liao" doi: "10.24963/ijcai.2018/433" url: "https://ijcai.org/proceedings/2018/433" pdf: "https://ijcai.org/proceedings/2018/0433.pdf" venue: "Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence" year: 2018 pages: "3118-3124" track: "Main track" keywords: - "Machine Learning: Learning Theory" - "Machine Learning: Kernel Methods" - "Machine Learning: Classification" - "Machine Learning: Online Learning" --- # Online Kernel Selection via Incremental Sketched Kernel Alignment Xiao Zhang, Shizhong Liao *Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence*, pages 3118-3124. DOI: [10.24963/ijcai.2018/433](https://doi.org/10.24963/ijcai.2018/433) ## Abstract In contrast to offline kernel selection, online kernel selection must rise to the new challenges of passing the training set once, selecting optimal kernels and updating hypotheses at each round, enjoying a sublinear regret bound for online kernel learning, and requiring a constant maintenance time complexity at each round and an efficient overall time complexity integrated with online kernel learning. However, most of existing online kernel selection approaches can not meet the new challenges. To address this issue, we propose a novel online kernel selection approach via the incremental sketched kernel alignment criterion, which meets all the new challenges. We first define the incremental sketched kernel alignment (ISKA) criterion, which estimates the kernel alignment and can be computed incrementally  and efficiently. When applying the proposed ISKA criterion to online kernel selection, we adopt the subclass coherence to maintain the hypothesis space, select the optimal kernel at each round using the median of the ISKA criterion estimates, and update the hypothesis following the online gradient decent method. We prove that the ISKA criterion is an unbiased estimate of the maximum mean discrepancy, enjoys the optimal logarithmic regret bound for online kernel learning, and has a constant maintenance time complexity at each round and a logarithmic overall time complexity integrated with online kernel learning. Empirical studies demonstrate that the proposed online kernel selection approach is computationally efficient while maintaining comparable accuracy for online kernel learning. ## Full text ## 1 Introduction Kernel selection is to select the kernel function corresponding to a reproducing kernel Hilbert space (RKHS) by a proper kernel selection criterion. Offline kernel selection criteria are usually defined via the estimate of the generalization error, such as k-fold cross validation [Anguita et al., 2009], Rademacher complexity [Bartlett and Mendelson, 2002] and eigenvalues ratio [Liu and Liao, 2015]. ∗Corresponding author In online setting, the kernels used significantly affect the performance of online kernel learning, which are usually preset empirically without theoretical guarantees. We refer to the kernel selection for online kernel learning as online kernel selection. In contrast to offline kernel selection performing separately training and testing on all instances with generalization guarantee, online kernel selection is a completely different problem that intermixes kernel selection and hypothesis updating on arrived instances at each round, which requires a sublinear regret bound, a constant maintenance time complexity at each round and at most a linear overall time complexity integrated with online kernel learning. Traditional offline kernel selection approaches do not apply to the online kernel learning scenario. First, offline kernel selection approaches need multiple passes over the data and have at least quadratic time complexity with respect to the data size, suffering from a low efficiency. Second, most of offline kernel selection approaches consist of the training phase and the testing phase, while online kernel learning can not split the training set and does not separate the two phases. Much attention has been directed at online model selection. Reisinger et al. (2008) presented an online model selection approach for Gaussian process temporal difference using sequential Monte-Carlo methods. Foster et al. (2015) established elegant model selection inequalities for online learning problems via the sequential complexity measures, and presented a generic meta-algorithm framework for online model selection [Foster et al., 2017], but efficient online model selection algorithms for online kernel learning need to be further explored. Recently, some online kernel selection approaches have been proposed. Yang et al. (2012) presented an online kernel selection approach that learns a probability distribution for each candidate kernel classifier, and selects the optimal kernel according to the distribution, which enjoys a regret bound of order O(√T), where T is the number of rounds. Kernel learning using the adaptive kernel was also introduced for online kernel selection, which updates the kernel widths using the gradient descent method for instantaneous loss directly [Chen et al., 2016; Nguyen et al., 2017]. A major limitation of most online kernel selection approaches is that they do not limit the model size at each round, leading to a linear space complexity and a quadratic time complexity with respect to the number of rounds. Besides, the existing adaptive kernel approaches for online kernel selection do not enjoy a sublinear regret bound that is critical to online kernel learning, and are not robust to initial kernels that may lead to poor performance. In this paper, we propose an online kernel selection approach that is theoretically guaranteed and computationally efficient. We define a novel online kernel selection criterion, which is an unbiased estimate of the maximum mean discrepancy and can be computed incrementally. When applying the proposed criterion to online kernel selection, there needs only logarithmic number of updates, where each update is in a linear time complexity with respect to the budget. In contrast to the existing regret analysis using a fixed kernel, the key challenge of the regret analysis for online kernel selection is to bound the average gradient error with varying kernels, and we derive the optimal logarithmic regret bound for online kernel selection using a novel definition of the weight degradation. Experimental results demonstrate the effectiveness and efficiency of our proposed online kernel selection approach that does not depend on the initially selected kernel. ## 2 Notations and Preliminary Let [T] = {1, 2, . . . , T}, [a : b] = {a, a + 1, . . . , b} and S = {(xi, yi)}Ti=1 ⊆ (X × Y)T be the sequence of T instances, where X ⊆ Rd and Y = {-1,+1}. We define the numbers of the positive and negative examples as T+, T-, respectively. Let y = [y1, y2, . . . , yT ]ᵀ be the label vector, and Y = yyᵀ be the label matrix. We denote the loss function by ℓ(·, ·), 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}. For kernel selection, we denote by K = {κi : i ∈ [N]} the candidate kernel set. The alignment metric of kernels is a widely used class of kernel selection criteria,which measures the similarity between the kernel matrix and the label matrix. Kernel Alignment (KA) problem is to maximize the following criterion [Sinha and Duchi, 2016] For i ∈ [T ], define the modified labels ˆ yi = 1/T+ if yi = +1 and ˆ yi = -1/T- if yi = -1 as in [Kandola et al., 2002]. The corresponding label vector and matrix are denoted by ˆ y and ̂ Y . Then the kernel alignment is translated into which is a biased empirical estimate of the Maximum Mean Discrepancy (MMD) [Gretton et al., 2012] where D1 (D2) is the distribution from which the positive (negative) examples are drawn. The hypothesis using the optimal kernel of MMD enjoys a generalization bound of order O(1/√T ) [Sinha and Duchi, 2016] for the soft-margin SVM. It is obvious that the time complexity of KA is in O(NT 2 )1 , where N is the size of the candidate kernel set. ## 3 Incremental Sketched Kernel Alignment In this section, we propose the incremental sketched kernel alignment to reduce the computational complexities, which can be applied to online kernel selection. We consider the kernel matrix sketch Sᵀ t KtSt of the kernel matrix Kt ∈ Rt×t at round t, where St ∈ Rt×Bt is the sketch matrix and limt→+∞Bt/t = 0. We first define the Incremental Sketched Kernel Alignment (ISKA) as follows We choose the sub-sampling sketch matrix as the matrix St, and introduce two buffers to store the sampled examples of positive class and negative class, denoted by V + t and V - t respectively. Let Vt = V + t ∪ V - t , B+ t = |V + t |, Bt = |V - t |, |Vt| = Bt, and denote the examples in the buffers by ˜x ∈ Vt with label ˜ y. Then ISKA is equivalent to which is computed in the updated buffers. For the incremental computation of ISKA, we transform (2) into where and γt+1 = ∑˜xi∈V + t+1 , ˜xj ∈V - t+1 κ(˜xi, ˜xj), in which we replace the original βξ t+1 with ˆ βξ t+1 to obtain an unbiased estimate of MMD as shown in Theorem 1. Then we update βξ t+1 and γt+1 in the ISKA criterion incrementally at each round. When yt = +1, let ξ denote +, ¯ ξ denote - and vice versa. For the insert operation, i.e., V ξ t+1 = V ξ t ∪ {xt}, we perform 1 For the complexity analysis, we focus on the number of rounds and omit the feature dimension d in this paper. ## 4 NewOnline Kernel Selection Approach In this section, we present the new online kernel selection approach using ISKA and apply it to online kernel learning. ## 4.1 Integration with ISKA We first formulate the hypothesis space sketch at round t using the basis functions corresponding to examples in the buffer as follows where ψ(t) κ (·) is the basis function vector and ω(t) is the weight vector For a new instance (xt, yt), we first give the predicted label ˆ yt = sgn(ft(xt)), receive the true label yt, and maintain the hypothesis space sketch using the buffer updating strategy under a fixed budget B. Specifically, let B+ t ≤ B/2 and Bt ≤ B/2, inspired by the reservoir sampling policy [Vitter, 1985; Zhao et al., 2011; Hu et al., 2015], when the size of the buffer is smaller than the budget we insert the new example into the buffer, i.e., V ξ t+1 = V ξ t ∪{xt}, otherwise invoke the BUFFERUPDATING process according to a Bernoulli distribution where Xt = 1 indicates that we perform the BUFFERUPDATING process at round t, including the following two steps. ## · INSERT Different from the existing notion of coherence [Tropp, 2004], we consider the correlation in positive and negative classes separately, which can reduce the computational cost with theoretical guarantee. At round t, we define the Subclass Coherence (SC) for κ(·, xt) as where ξ denotes + for yt = +1 or - for yt = -1. Given the threshold µξ , if the SC condition holds, i.e., we insert xt into the buffer after the delete operation. ## · DELETE If the SC condition holds at the t-th round, we choose the example ˜xrt in the buffer V ξ t to delete via and update the buffer as V ξ t+1 = V ξ t \ {˜xrt } ∪ {xt}, while V ¯ ξ t+1 = V ¯ ξ t . Finally, when the buffers are changed at round t, we first compute the ISKA criterion incrementally using (3) and (4), called INCREMENTALCOMPUTATION process. Then we evaluate the performance of each kernel in the candidate kernel set K = {κi : i ∈ [N]} using the median of ISKA criterion estimates over the past q (q ≥ 1) rounds and select the optimal kernel at round t by ## 4.2 Application to Online Kernel Learning For online kernel learning, we update the hypothesis using Online Gradient Descent (OGD) method [Kivinen et al., 2001; Shalev-Shwartz, 2011] to minimize the following instantaneous loss at round t where ˜κ = κ∗t+1 and λ denotes the regularization parameter. Denote the hypothesis of round t after selecting the optimal kernel by and the hypothesis updating using OGD can be expressed as where ηt denotes the stepsize at round t and Then we consider two cases depending on whether the budget has been reached or not. In the first case, Bξ t < B/2. If xt is inserted into the buffer, we set ˜xBt+1 = xt and update the weight vector as follows If the buffers are not changed, choose the surrogate example and update the weight vector as follows Next we consider the second case when Bξ t = B/2. If the buffers change we replace ˜xrt with xt and perform otherwise we update the weight vector as in (9). For hinge loss ℓ(·, ·), the value of ℓ′ ( ˜ ft(xt), yt) is 0 if yt ˜ ft(xt) ≥ 1 and -yt otherwise. If the loss is zero, i.e., yt ˜ ft(xt) ≥ 1, we just update the weight vector using weight decay as ω(t+1) = (1 - ηtλ)ω(t) . Finally, we summarize the above stages into Algorithm 1, called OKS-ISKA. ## 5 Theoretical Analysis In this section, we analyze the statistical properties of ISKA, derive the regret bound of online kernel learning using ISKA, and analyze the computational complexities of ISKA. ## Algorithm 1: OKS-ISKA Algorithm ``` Require: The budget B, regularization parameter λ, candidate kernel set K, subclass coherence parameters µ+, µ-, parameter q for median estimate 1: Initialize ω(1) = 0, C(0) sk = 0 and two buffers V + 1 = ∅, V - 1 = ∅ 2: for t = 1, . . . , T do 3: Compute ψ(t) κ∗t (xt) = [κ∗t (xt, ˜x1), . . . , κ∗t (xt, ˜xBt )]ᵀ 4: Compute ft(xt) = 〈ω(t) ,ψ(t) κ∗t (xt)〉 5: Predict ˆ yt = sgn(ft(xt)) 6: if ytft(xt) < 1 then 7: Set ξ as + for yt = +1 or - for yt = -1 8: if Bξ t < B/2 then 9: V ξ t+1 = V ξ t ∪ {xt} 10: else 11: Sample X with Pr(X = 1) = B/(2t) 12: if X = 1 then 13: (V ξ t+1 , ˜xrt ) = BUFFERUPDATING(V ξ t , xt) 14: end if 15: end if 16: if the buffers change then 17: C(t) sk (κ) = INCREMENTALCOMPUTATION(C(t-1) sk , xt, ˜xrt ) 18: Select the optimal kernel κ∗t+1 = argmaxκ∈K C(t) sk (κ, q) 19: end if 20: Update ω(t+1) via OGD 21: else 22: ω(t+1) = (1 - ηtλ)ω(t) 23: end if 24: end for ``` ## 5.1 Unbiasedness and Regret Analysis We demonstrate the expectation and probabilistic error bound of ISKA as shown in Theorem 1. Theorem 1. For Gaussian kernel, the median estimate of ISKA is an unbiased estimate of MMD 2 , i.e., And with probability at least 1 - 2 exp (-(1 - 2δ)2 q/2) Remark 1. Theorem 1 indicates that (11) holds with probability at least 1 - ¯ δ provided q = Θ(ln(1/¯ δ)). Due to the incremental computation of ISKA, we may obtain different optimal kernel at each round, and perform OGD in varying RKHS. For regret analysis, we construct a surrogate hypothesis space Hˆκ that contains all the candidate kernel functions and derive the norm bound in Theorem 2. Theorem 2. For Gaussian kernel κ(x1, x2) = exp(-‖x1 - x2‖2 /(2σ2 )), given candidate kernel set K = {κi : i ∈ [N]} with kernel widths σ1, σ2, . . . , σN, define Then the RKHS Hˆκ induced by ˆκ with ˆσ = σmin contains all the candidate kernel functions, and ‖κi(·, x)‖2Hˆκ ≤ θ, 2 We omit the constant terms that do not affect the kernel selection results. In contrast to the regret analysis for online kernel learning using a fixed kernel [Cesa-Bianchi et al., 2010], we derive the regret bound for online kernel selection with varying kernels in Hˆκ using a novel definition of weight degradation. We define the weight degradation caused by online kernel selection and hypothesis updating at round t as follows where ft(·) = 〈ω(t) ,ψ(t) κ∗t (·)〉 uses the optimal kernel κ∗t of round t - 1. Then we give the upper bound of the average gradient error where Et = Λt/ηt, and demonstrate the regret bound of online kernel learning as follows. Theorem 3. Let ν = max{P/λ, 1/√λ}, ηt = 1/(tλ), µmin = min{µ+, µ-}, θ be the norm bound in (12). Assume 〈κ∗t (·, xt), κ∗t (·, ˜xst )〉Hˆκ ≥ Z for any surrogate example ˜xst while not invoking the BUFFERUPDATING process, and ‖Et‖Hˆκ + 1 ≤ P. For problem (7) with the hinge loss and the Gaussian kernel, let f ∗ = argminf∈Hˆκ ∑Tt=1 Lt(f ) using the optimal kernel selected by MMD, ζ be the maximum size that the buffer may reach without budget, and ft, t ∈ [T ] be the sequence of hypotheses generated by (8), (9) and (10). Then there is a constant C ≥ 0 such that E[E] ≤ ˆE/T, and where Proof Sketch. For the hinge loss, the weight degradation in (13) can be expressed as follows We decompose the weight degradation Λt into two terms Λt = Γt +∆t, where is that of buffer updating and hypothesis updating. Then we derive the upper bound of the average gradient error and complete the proof by Theorem 1 and Theorem 2. Remark 2. By Proposition 3 in [Richard et al., 2009], our SC condition is a sufficient condition of the Approximate Linear Dependency (ALD) condition. Since the eigenvalues of Gaussian kernel matrix decay exponentially to 0 [Caponnetto and De Vito, 2007], the maximum size of the buffer without budget via ALD is of order O(lnT) [Sun et al., 2012], which yields ζ = O(lnT). Then let Z = θ - (lnT/T)2 , we can obtain ˆE = O(lnT), and the regret bound of order O(lnT) in Theorem 3 that is the optimal regret bound for strongly convex objective function and OGD [Hazan, 2016]. ## 5.2 Computational Complexities of ISKA When applying the proposed ISKA to online kernel selection with N candidate kernels, the maintenance of ISKA criterion includes two operations at each updating step: (a) the buffer updating is in O(B) time complexity, which is a linear time complexity with respect to the budget; (b) the incremental computation is in O(NB) time complexity 3 . Since the updating steps are according to the probability distribution in (5), the expectation of the number of the updates is O(B lnT) for ISKA. Thus, the overall time complexity of ISKA is O (NB2 ln T ). Table 1 summarizes the time complexities of KA and our ISKA after T rounds. Since only β+ t , βt and γt need to be stored for each candidate kernel, the space complexity of ISKA is O(B +N), where B, N ≪ T and both are constant. Table 1: Time complexities of kernel alignment criteria (BU: buffer updating per round; IC: incremental computation per round; N: size of the candidate kernel set; T: number of rounds; B: budget). | KA | ISKA - # Updates | ISKA - BU | ISKA - IC | ISKA - Total | |----------|--------------------|-------------|-------------|----------------| | O(NT 2 ) | O(B lnT) | O(B) | O(NB) | O (NB2 lnT ) | ## 6 Experiments This section empirically evaluates the proposed OKS-ISKA for online kernel learning. ## 6.1 Experimental Setups Algorithms were implemented in R 3.3.2 on a machine with 4-core Intel Core i7 3.60 GHz CPU and 16GB memory. All the experiments were performed over 20 different random permutations of the datasets. We merged the training and testing data into a single dataset for each benchmark dataset 4 , and compared the proposed OKS-ISKA with the following state-of-the-art online kernel selection algorithms. - Online Kernel Selection (OKS) [Yang et al., 2012]: OKS is a randomized kernel selection algorithm. It learns a probability distribution for each candidate kernel by which the optimal kernel is selected. - Online Kernel Learning with Adaptive Kernel [Chen et al., 2016]: It updates the hypothesis and the kernel width by OGD method to minimize the squared loss. We replace the squared loss with the hinge loss for fair comparison, which we refer to as OKL-GD 5 . 3 Since we set q < N in the experiments, we omit q in the complexity analysis for ISKA. 4 http://www.csie.ntu.edu.tw/∼cjlin/libsvmtools/datasets/ http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html 5 To prevent the curse of kernelization, we keep at most 1000 examples in memory when learning using OKL-GD. - Projectron++ [Orabona et al., 2008]: Projectron++ is a budgeted online kernel learning algorithm using a projection strategy that is equivalent to ALD condition. For baseline, similar to the two-stage method [Cortes et al., 2012], we first select a kernel via KA criterion in (1) and then run Projectron++ with the selected kernel, which we refer to as Proj-KA. 6 A set of Gaussian kernels with kernel widths σ ∈ {2-(i+1)/2 , i = [-12 : +2 : 12]} was adopted as the candidate kernel set and the kernel widths of OKL-GD were restricted to the same range. The initial parameter i of the kernel width was selected in {-12,-10,-8} uniformly, since small kernel width may lead to the vanishing of the initial gradient of OKL-GD. We tuned the stepsize of OGD in a range 10[-5:+1:0] and the regularization parameter λ in a range 10[-4:+1:1] . For our OKS-ISKA, we set q = 5 for the median estimate, µξ = 0.3, B = 150 for small datasets (T < 10, 000) and B = 200 for other datasets according to the experimental analysis in "Parameter Influence." Besides, we set ηt = 1/(tλ) as in Theorem 3. For fair comparison, we ran OKS with single pass over the data and set the smoothing parameter ¯ δ = 0.2, stepsize of weight updating η = √2(1 - ¯ δ) lnN/(NT) as in [Yang et al., 2012]. For Projectron++, we use hinge loss for fair comparison, and set the projection parameter U = 1/4√(B + 1)/ log(B + 1) as in [Orabona et al., 2008]. The mistake rate is used to evaluate the accuracy of online kernel selection approaches for online kernel learning, which is computed by ∑Tt=1 I(ytft(xt) < 0)/T × 100, and the mean of mistake rates over the 20 runs is referred to as average mistake rate. ## 6.2 Performance Evaluation Table 2 lists the experimental results in terms of the mistake rate and running time for online kernel learning. We can summarize the results as follows: (a) For small datasets, OKSISKA performs better than the other kernel selection algorithms in terms of the mistake rates, while having a slightly lower efficiency due to the frequent updates of the buffers for OKS-ISKA at the initial period; (b) For large datasets, OKS-ISKA is significantly more efficient than the other algorithms while preserving accuracy; (c) The offline computation of kernel alignment for Proj-KA consumes much more time than the incremental computation for our ISKA. Figure 1 depicts the convergence behaviors in terms of the mistake rates and running time on splice. Since Proj-KA adopted the offline kernel selection, we do not include its running time curve. The results show that the OKS-ISKA is significantly more efficient after the initial period. ## 6.3 Parameter Influence We further conducted experiments using different initial kernel widths, budgets and SC conditions. Figure 2 shows the mistake rate and runtime on spambase in terms of initial kernel widths in a range i ∈ 6 Due to the high computational complexities, we randomly sample 10000 examples for Proj-KA to select the optimal kernel in the experiments on large datasets. Table 2: Performances of online kernel selection approaches for online kernel learning on benchmark datasets. | Dataset | OKS-ISKA - Mistake rate (%) | OKS-ISKA - Time (s) | OKL-GD - Mistake rate (%) | OKL-GD - Time (s) | OKS - Mistake rate (%) | OKS - Time (s) | Proj-KA - Mistake rate (%) | Proj-KA - Time (s) | |-----------|-------------------------------|-----------------------|-----------------------------|---------------------|--------------------------|------------------|------------------------------|----------------------| | german | 30.012 ± 0.767 | 0.373 | 35.202 ± 1.813 | 0.223 | 42.207 ± 1.377 | 0.303 | 39.280 ± 1.119 | 0.889 | | svmguide3 | 22.684 ± 0.625 | 0.368 | 23.263 ± 0.338 | 0.341 | 29.572 ± 0.963 | 0.304 | 26.641 ± 1.282 | 1.787 | | spambase | 28.876 ± 0.942 | 1.236 | 33.136 ± 2.323 | 3.403 | 34.055 ± 0.263 | 3.641 | 29.723 ± 0.791 | 19.120 | | splice | 23.616 ± 1.855 | 1.112 | 28.057 ± 5.097 | 2.182 | 37.814 ± 2.154 | 1.986 | 35.389 ± 6.478 | 11.262 | | mushrooms | 0.360 ± 0.059 | 2.293 | 9.652 ± 1.725 | 21.430 | 8.003 ± 0.328 | 8.938 | 0.377 ± 0.014 | 92.592 | | a9a | 17.293 ± 0.420 | 26.023 | 23.930 ± 0.001 | 172.202 | 23.132 ± 0.101 | 1033.891 | 20.893 ± 0.097 | 183.605 | | w7a | 2.582 ± 0.083 | 83.061 | 2.973 ± 0.125 | 537.550 | 6.926 ± 0.073 | 1134.709 | 2.632 ± 0.078 | 364.350 | | w8a | 2.570 ± 0.074 | 98.530 | 2.912 ± 0.111 | 633.350 | 6.911 ± 0.072 | 1453.720 | 2.486 ± 0.075 | 415.682 | | corrected | 3.737 ± 0.341 | 268.341 | 4.452 ± 0.315 | 1256.462 | 5.505 ± 0.045 | 13930.106 | 4.323 ± 0.377 | 397.781 | | cod-rna | 11.615 ± 0.002 | 41.230 | 12.603 ± 0.450 | 68.030 | 12.727 ± 0.124 | 1852.235 | 15.142 ± 0.255 | 115.877 | Figure 1: Convergence behaviors w.r.t. the mistake rate and runtime on benchmark datasets. ![Image](https://ijcai.org/proceedings/2018/fulltext/433/image_000000_b6698dfe9862f85342728e304951c2a8bdd46509bc9812e6817f52b8ead6e830.png) {-12, -8, -4, 0, 4, 8}. We can observe that the initial kernel width has almost no effect on the performance of OKS-ISKA. Thus, OKS-ISKA is robust to the initial kernel. From Figure 3, we observe that, for our OKS-ISKA, the buffers with budget B = 200 perform as well as those with larger budget with respect to the mistake rate, while having less runtime. Thus, OKS-ISKA is suitable for large-scale online kernel learning. Besides, a smaller threshold µξ of SC condition incurs a better performance in terms of both accuracy and efficiency, which demonstrates that our buffer updating strategy is effective for online kernel selection. ## 7 Conclusion Kernel selection is critical to kernel methods, and online kernel selection is faced with some new challenges. In this paper, we have proposed the novel online kernel selection approach that is theoretically sound and computationally efficient. The proposed approach gives an unbiased estimate of the maximum mean discrepancy, enjoys the optimal regret bound for online kernel learning, and dynamically maintains the hypothesis space and selects the optimal kernel at each round, while the maintenance time complexity is constant and the overall time complexity is logarithmic. We conclude that the proposed online kernel selection approach meets the new challenges of online kernel selection and is promising for both online and offline large-scale model selection. Figure 2: The effect of initial kernel width on the mistake rate and runtime of OKS-ISKA. ![Image](https://ijcai.org/proceedings/2018/fulltext/433/image_000001_d4a4eee44f94050ee24c7cd7093d5118d5303dea10b69fc27e3ae30501d5faa6.png) Figure 3: Kernel selection results, average mistake rate, average runtime w.r.t. budget B and µξ in the SC condition (6). ![Image](https://ijcai.org/proceedings/2018/fulltext/433/image_000002_f765eae655f72a5c49a0069bd8fef18551a0ab74d18f9dbe47f8167da77a48ff.png) ## Acknowledgments This work was supported in part by the National Natural Science Foundation of China (No. 61673293 and No. 61703396), and the State Key Development Program of China (No. 2017YFE0111900). ## References 1. [Anguita et al., 2009] Davide Anguita, Alessandro Ghio, Sandro Ridella, and Dario Sterpi. k-fold cross validation for error rate estimate in support vector machines. In Pro- ceedings of the 2009 International Conference on Data Mining, pages 291-297, 2009. 2. [Bartlett and Mendelson, 2002] Peter L Bartlett and Shahar Mendelson. Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learn- ing Research, 3:463-482, 2002. 3. [Caponnetto and De Vito, 2007] A. Caponnetto and E. De Vito. Optimal rates for the regularized least- squares algorithm. Foundations of Computational Mathematics, 7(3):331-368, 2007. 4. [Cesa-Bianchi et al., 2010] Nicolò Cesa-Bianchi, Shai Shalev-Shwartz, and Ohad Shamir. Online learning of noisy data with kernels. In Proceedings of the 23rd Conference on Learning Theory, pages 218-230, 2010. 5. [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. 6. [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. 7. [Foster et al., 2015] Dylan J Foster, Alexander Rakhlin, and Karthik Sridharan. Adaptive online learning. In Ad- vances in Neural Information Processing Systems 28, pages 3375-3383, 2015. 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. [Gretton et al., 2012] Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. Journal of Machine Learning Research, 13:723-773, 2012. 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 and Liao, 2015] Yong Liu and Shizhong Liao. Eigen- values ratio for kernel selection of kernel methods. In Pro- ceedings of the 29th AAAI Conference on Artificial Intelli- gence, pages 2814-2820, 2015. 15. [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. 16. [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. 17. [Reisinger et al., 2008] Joseph Reisinger, Peter Stone, and Risto Miikkulainen. Online kernel selection for Bayesian reinforcement learning. In Proceedings of the 25th In- ternational Conference on Machine Learning, pages 816- 823, 2008. 18. [Richard et al., 2009] Cédric Richard, José Carlos M Bermudez, and Paul Honeine. Online prediction of time series data with kernels. IEEE Transactions on Signal Processing, 57(3):1058-1067, 2009. 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. [Sinha and Duchi, 2016] Aman Sinha and John C Duchi. Learning kernels with random features. In Advances in Neural Information Processing Systems 29, pages 1298- 1306, 2016. 21. [Sun et al., 2012] Yi Sun, Faustino Gomez, and Jürgen Schmidhuber. On the size of the online kernel sparsifi- cation dictionary. In Proceedings of the 29th International Conference on Machine Learning, pages 329-336, 2012. 22. [Tropp, 2004] Joel A Tropp. Greed is good: Algorithmic results for sparse approximation. IEEE Transactions on Information Theory, 50(10):2231-2242, 2004. 23. [Vitter, 1985] Jeffrey S Vitter. Random sampling with a reservoir. ACM Transactions on Mathematical Software, 11(1):37-57, 1985. 24. [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. 25. [Zhao et al., 2011] Peilin Zhao, Rong Jin, Tianbao Yang, and Steven C.H. Hoi. Online AUC maximization. In Pro- ceedings of the 28th International Conference on Machine Learning, pages 233-240, 2011.