Online Kernel Selection via Incremental Sketched Kernel Alignment

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.

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.

{-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.

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).