# Multi-Nyström Method Based on Multiple Kernel Learning for Large Scale Imbalanced Classification

Authors: Ling Wang; Hongqiao Wang; Guangyuan Fu
Journal: Computational Intelligence and Neuroscience
 (2021)

---

## Abstract

Extensions of kernel methods for the class imbalance problems have been extensively studied. Although they work well in coping with nonlinear problems, the high computation and memory costs severely limit their application to real-world imbalanced tasks. The Nyström method is an effective technique to scale kernel methods. However, the standard Nyström method needs to sample a sufficiently large number of landmark points to ensure an accurate approximation, which seriously affects its efficiency. In this study, we propose a multi-Nyström method based on mixtures of Nyström approximations to avoid the explosion of subkernel matrix, whereas the optimization to mixture weights is embedded into the model training process by multiple kernel learning (MKL) algorithms to yield more accurate low-rank approximation. Moreover, we select subsets of landmark points according to the imbalance distribution to reduce the model’s sensitivity to skewness. We also provide a kernel stability analysis of our method and show that the model solution error is bounded by weighted approximate errors, which can help us improve the learning process. Extensive experiments on several large scale datasets show that our method can achieve a higher classification accuracy and a dramatical speedup of MKL algorithms.


---

## Body

## 1. Introduction

Real-world problems in computer vision [1], natural language processing [2, 3], and data mining [4, 5] present imbalanced traits in their data, which may be developed by the inherent properties of the data or some external factors such as sampling bias or measurement error. Unfortunately, most traditional learning algorithms are designed based on balanced data and target the overall classification accuracy, leading the minority class to be overwhelmed by the majority class. However, the minority class in these real-world problems is usually more important and expensive than the majority class.In the past few decades, many algorithms have been proposed to solve the class imbalance problems [6–8]. The data-level methods artificially balance the skewed class distributions by data sampling [9, 10]. The algorithm-level methods lift the importance of minority instances via the modification of existing learners [11, 12]. However, there usually exist complex nonlinear structures in these real-world imbalanced data. In this case, the extensions of kernel methods for the class imbalance problems have been proven very effective [13–15]. In [16], Mathew et al. overcome the limitations of the synthetic minority oversampling technique (SMOTE) for nonlinear problems by oversampling in the feature space of the support vector machine. In [17], a kernel boundary alignment algorithm is proposed to adjust the class boundary by modifying the kernel matrix according to the imbalanced data distribution. The kernel-based adaptive synthetic data generation (KernelADASYN) for imbalanced learning is proposed in [18], which uses kernel density estimation (KDE) to estimate the adaptive oversampling density. However, with the development of data storage and data acquisition equipment, the scale of data continues to grow. The existing kernel-based class imbalanced learning (kernel CIL) methods suffer from serious challenges that the cost of calculating and storing a vast kernel matrix is very expensive.A general technique for making kernel methods scalable is kernel approximation, of which the Nyström method is the most popular one [19]. The Nyström method constructs a low-rank approximation of the original kernel matrix from a subset of l≪n landmark points, where n is the data size. Computationally, it only needs to decompose a smaller matrix (denoted as W∈ℝl×l). However, according to the approximation error bound On/l for the Nyström method in [20], there is a trade-off between accuracy and efficiency. The more landmark points sampled provide improved approximation accuracy but require more computing resources, which results in the rapid expansion of the subkernel matrix W as the data size increases and seriously affects the efficiency of the Nyström method.Some works study the efficacy of a variety of fixed and adaptive sampling schemes for the Nyström method. For example, Musco et al. presented a new Nyström algorithm based on recursive leverage score sampling, which runs in linear time in the number of training points [21]. An ensemble Nyström method has been proposed to yield more accurate low-rank approximations by running mixtures of the Nyström method based on several subsets of landmark points randomly sampled [22]. However, the mixture weights of the ensemble Nyström method are defined according to the approximation error of each Nyström approximation, which may lead to the performance not as expected when applied to practical classification or regression applications. Recently, there emerges a fast and accurate refined Nyström-based kernel classifier to improve the performance of the Nyström-based kernel classifier [23]. Although the Nyström method has been studied extensively, there still exists a potentially large gap between the performance of learner learned with the Nyström approximation and that learned with the original kernel.In this study, we propose a novel method, multi-Nyström, for large scale imbalanced classification. We incorporate the multi-Nyström method and multiple kernel learning to learn an improved low-rank approximation kernel superior to any one of each multi-Nyström approximation, where each approximation is defined by different kernel functions and subsets of landmark points. Moreover, unlike existing sampling schemes for the multi-Nyström method, our method selects subsets of landmark points according to the imbalance distribution to deal with the problem of skewed data. Without computing and storing the full kernel matrix, our method can scale to large scale scenarios. The main contributions of this study are summarized as follows:(1)
We propose a multi-Nyström method to overcome the computational constraints of the Nyström method. Due to our method parallelized easily, it can generate more accurate approximates in large scale scenarios.(2)
We optimize the mixture weights according to the data and the problem at the hand, so that the combined approximation kernel matrix can produce better performance. Moreover, the low-rank approximation can significantly speed up the existing MKL algorithms process.(3)
We provide a stability analysis of our method, showing us the impact of kernel approximation error on the model solution and help determine the acceptable approximation error in the approximation of the kernel matrix.The rest of this study is organized as follows. Section2 introduces some related concepts. Section 3 then describes the proposed multi-Nyström approximation algorithm in detail. Experimental results and analysis compared with other algorithms are presented in Section 4. Finally, Section 5 summarizes the full work.


## 2. Related Work

### 2.1. Kernel Methods

Kernel methods such as support vector machines (SVMs) have become one of the most popular technologies of machine learning [24]. It can extend linear learners to nonlinear cases by introducing kernel trick. Consider a binary-class dataset D=xi,yii=1n, where xi∈X⊆ℝs denotes an s-dimensional vector and yi∈+1,−1 denotes its label. Define a nonlinear descriptor as(1)Φ:X⟶ℋxi↦Φxi.The input data are mapped to a high-dimensional or even infinite-dimensional feature space, and the inner product in the feature space is calculated implicitly through the kernel function defined in the input space.(2)Kx,x′=Φx,Φx′ℋ=ΦxTΦx′,where K:ℝs×ℝs↦ℝ is the kernel function that satisfies Mercer’s theorem [25], and ℋ is the corresponding reproducing kernel Hilbert space (RKHS). K can simply be a classical kernel like the radial basis function (RBF) kernel. Unfortunately, the kernel matrix K∈ℝn×n expands quadratically with the increase of data scale. The poor scalability limits the applicability of kernel methods in large scale scenarios.


### 2.2. Multiple Kernel Learning

Due to different kernels corresponding to different similarity concepts or using features from different views, MKL can obtain more complete representations of the input data by combining multiple kernels. In MKL, each instancexi,yi is mapped into different feature spaces by a series of descriptors [26]:(3)Φℋxi=d1Φ1Txi1,…,dMΦMTxiMT,where xim represents feature from the mth view of instance xi, dm≥0, m=1,…,M is the corresponding weight, and M is the total number of predefined kernels. Then, substitute any dot product term with kernels:(4)Kx,xi=Φx,Φxiℋ=∑m=1MdmΦmxm,Φmximℋm=∑m=1MdmKmxm,xim,where each base kernel function Km⋅,⋅:ℝs×ℝs⟶ℝ is a positive definite kernel associated with an RKHS ℋm. The purpose of MKL is to learn a resulting discriminant function of the form fx=∑mfmxm+b with ℋm≔fm|fmx=∑i=1∞αiKmxm,xim.Based on the aforementioned definition, the seminal work in MKL proposes the following structural risk minimization framework as MKL primal problem with kernel weights on a simplex [27].(5)minfm,b,ξ,d:12∑m=1M1dmfmℋm2+C∑i=1Nξis.t.yi∑m=1Mfmxim+b≥1−ξiξi≥0,i=1,…,N∑m=1Mdm=1,dm≥0,m=1,…,M,where C is the regularization parameter of the error term. ξ is the slack variable. The L1-norm constraint on the weight vector d enforces the kernel combination to be sparse. We assume fmℋm2=0 whenever dm=0 in order to reach a finite objective. That implies if the weight of a certain kernel reaches dm=0, stop the optimization of fm since the solution is known fm=0 [28].Although MKL is an ideal candidate for combining multiview data, scalability is a key issue for MKL: (1) the computation and memory costs for maintaining several kernel matrices are heavy and (2) the computational efficiency of MKL solvers is not high.


### 2.3. Standard Nyström Method

LetL=c1,…,cl, where ci∈ℝs denotes a set of l landmark points randomly selected from D uniformly without replacement, C∈ℝn×l denotes the subkernel matrix between all instances and the landmark points, and W∈ℝl×l be a symmetric positive semidefinite (SPSD) subkernel matrix among the points in L. Then, the Nyström method uses W and C to generate a rank-k approximation K˜k of kernel matrix K for k≤l [20]:(6)K≈K˜k≔CWk+CT,where Wk∈ℝl×l is the best rank-k approximation to W with respect to the Frobenius norm, that is, Wk=argminrankV=kW−VF, and Wk+ denotes the pseudoinverse of Wk. Given the matrix Wk, the feature of each instance xi can be evaluated as(7)ϕxi=Wk+Kxi,c1,…,Kxi,clT.Calculate the singular value decomposition (SVD) ofW as W=UΛUT, where U is the orthonormal and Λ=diagσ1,…,σm is the diagonal with σ1≥⋯≥σm≥0. Then, the final approximate decomposition of K is denoted as the following form:(8)K≈U˜kΛ˜kU˜kT,withU˜k=lnCUkΛk−1,Λ˜k=nlΛk,where Λk∈ℝk×k is the diagonal formed by the top k singular values of Λ, and Uk∈ℝl×k is formed by the associated singular vectors.The total time complexity of the Nyström method isOl3+nlk including Ol3 for SVD on W and Onlk for matrix multiplication with C [29]. For l≪n, it is much lower than the On3 complexity taken by SVD on K.


## 2.1. Kernel Methods

Kernel methods such as support vector machines (SVMs) have become one of the most popular technologies of machine learning [24]. It can extend linear learners to nonlinear cases by introducing kernel trick. Consider a binary-class dataset D=xi,yii=1n, where xi∈X⊆ℝs denotes an s-dimensional vector and yi∈+1,−1 denotes its label. Define a nonlinear descriptor as(1)Φ:X⟶ℋxi↦Φxi.The input data are mapped to a high-dimensional or even infinite-dimensional feature space, and the inner product in the feature space is calculated implicitly through the kernel function defined in the input space.(2)Kx,x′=Φx,Φx′ℋ=ΦxTΦx′,where K:ℝs×ℝs↦ℝ is the kernel function that satisfies Mercer’s theorem [25], and ℋ is the corresponding reproducing kernel Hilbert space (RKHS). K can simply be a classical kernel like the radial basis function (RBF) kernel. Unfortunately, the kernel matrix K∈ℝn×n expands quadratically with the increase of data scale. The poor scalability limits the applicability of kernel methods in large scale scenarios.


## 2.2. Multiple Kernel Learning

Due to different kernels corresponding to different similarity concepts or using features from different views, MKL can obtain more complete representations of the input data by combining multiple kernels. In MKL, each instancexi,yi is mapped into different feature spaces by a series of descriptors [26]:(3)Φℋxi=d1Φ1Txi1,…,dMΦMTxiMT,where xim represents feature from the mth view of instance xi, dm≥0, m=1,…,M is the corresponding weight, and M is the total number of predefined kernels. Then, substitute any dot product term with kernels:(4)Kx,xi=Φx,Φxiℋ=∑m=1MdmΦmxm,Φmximℋm=∑m=1MdmKmxm,xim,where each base kernel function Km⋅,⋅:ℝs×ℝs⟶ℝ is a positive definite kernel associated with an RKHS ℋm. The purpose of MKL is to learn a resulting discriminant function of the form fx=∑mfmxm+b with ℋm≔fm|fmx=∑i=1∞αiKmxm,xim.Based on the aforementioned definition, the seminal work in MKL proposes the following structural risk minimization framework as MKL primal problem with kernel weights on a simplex [27].(5)minfm,b,ξ,d:12∑m=1M1dmfmℋm2+C∑i=1Nξis.t.yi∑m=1Mfmxim+b≥1−ξiξi≥0,i=1,…,N∑m=1Mdm=1,dm≥0,m=1,…,M,where C is the regularization parameter of the error term. ξ is the slack variable. The L1-norm constraint on the weight vector d enforces the kernel combination to be sparse. We assume fmℋm2=0 whenever dm=0 in order to reach a finite objective. That implies if the weight of a certain kernel reaches dm=0, stop the optimization of fm since the solution is known fm=0 [28].Although MKL is an ideal candidate for combining multiview data, scalability is a key issue for MKL: (1) the computation and memory costs for maintaining several kernel matrices are heavy and (2) the computational efficiency of MKL solvers is not high.


## 2.3. Standard Nyström Method

LetL=c1,…,cl, where ci∈ℝs denotes a set of l landmark points randomly selected from D uniformly without replacement, C∈ℝn×l denotes the subkernel matrix between all instances and the landmark points, and W∈ℝl×l be a symmetric positive semidefinite (SPSD) subkernel matrix among the points in L. Then, the Nyström method uses W and C to generate a rank-k approximation K˜k of kernel matrix K for k≤l [20]:(6)K≈K˜k≔CWk+CT,where Wk∈ℝl×l is the best rank-k approximation to W with respect to the Frobenius norm, that is, Wk=argminrankV=kW−VF, and Wk+ denotes the pseudoinverse of Wk. Given the matrix Wk, the feature of each instance xi can be evaluated as(7)ϕxi=Wk+Kxi,c1,…,Kxi,clT.Calculate the singular value decomposition (SVD) ofW as W=UΛUT, where U is the orthonormal and Λ=diagσ1,…,σm is the diagonal with σ1≥⋯≥σm≥0. Then, the final approximate decomposition of K is denoted as the following form:(8)K≈U˜kΛ˜kU˜kT,withU˜k=lnCUkΛk−1,Λ˜k=nlΛk,where Λk∈ℝk×k is the diagonal formed by the top k singular values of Λ, and Uk∈ℝl×k is formed by the associated singular vectors.The total time complexity of the Nyström method isOl3+nlk including Ol3 for SVD on W and Onlk for matrix multiplication with C [29]. For l≪n, it is much lower than the On3 complexity taken by SVD on K.


## 3. Proposed Algorithms

### 3.1. Multi-Nyström Method

We divide the imbalance datasetD=xi,yii=1n into the minority class set D+=xi,+1i=1n+ and the majority class set D−=xi,−1i=1n−. When there are irregularities in the imbalanced data (such as small disjuncts, overlapping, and noise [30]) and the data scale is large, applying a single kernel may make the model biased, skew, or misleading. Inspired by the MKL algorithm [31], we construct a low rank approximate multiple kernel framework as follows:(9)Kx,xi≈∑m=1MdmK˜m,kxm,xim,withdm≥0,where K˜m,k corresponds to the rank-k approximation of each base kernel matrix Km, and dm is the corresponding mixture weight. As for the Nyström method, a key aspect is the sampling scheme [32]. For reducing the sensitivity to skewness in data, we adopt the stratified undersampling of the majority class to select M subsets of landmark points written as L=Lmm=1M with each Lm=cm,1,…,cm,l. The subkernel matrix between all instances and the landmark points can be expressed as(10)C=C1,…,CM∈ℝn×Ml,where Cm∈ℝn×l. Then, we perform the standard Nyström method on each Cm independently to get a rank-k approximation K˜m,k=CmWm,k+CmT of each base kernel matrix Km. Finally, by linearly combining these approximations, we can get the general form of approximation multiple kernel K˜:(11)K˜=C1,…,CMd1W1,k+⋱dMWM,k+C1T⋮CMT.Given the mixture weightdm, the feature of each instance xi can be evaluated as(12)ϕ˜xi=d1W1,k+K1xi,c1,1,…,K1xi,c1,lT⋮dMWM,k+KMxi,cM,1,…,KMxi,cM,lT.Similarly, for the convenience of subsequent calculations, formula (11) can be rewritten as(13)K˜=U˜1,k,…,U˜M,kd1Λ˜1,k⋱dMΛ˜M,kU˜1,kT⋮U˜M,kT.where U˜m,k∈ℝn×k, and Λ˜m,k∈ℝk×k denotes the approximate decomposition of Km obtained by (8). Figure 1 shows the proposed multi-Nyström method and includes an optimization process of the mixture weights detailed futher in next subsection.Figure 1
Architecture of the proposed multi-Nyström method.M subsets from the majority class are sampled to construct balanced landmark points and then the Nyström method is used to obtain the approximate base kernel matrices and the multiple kernel learning (MKL) algorithm is applied to optimize the mixture weights and train classifier. Finally, the trained kernel classifier based on multi-Nystrom is obtained.When the mixture weightdm is fixed or known, the total time complexity of the multi-Nyström method is OMl3+Mnlk. Although our method requires M times more CPU resources than the standard Nyström method, M≪n is typically O(1) for large scale data, and our method can compute in parallel in the distributed computing environment. Moreover, the SVD on the subkernel matrix W is decomposed into that on M much smaller matrices would also accelerate the calculation process.


### 3.2. Optimization to Mixture Weights

The purpose of MKL is to learn an optimal convex combination of a series of kernels during training. Based on the aforementioned definition, we propose an approximate multiple kernel learning framework for large scale imbalanced classification by modifying the original MKL framework in [26](14)minJdsuch thatd12=1,dm≥0,m=1,…,M,where(15)Jd=minα12αTYK˜Yα−eTαs.t.yTα=00≤α≤C,where α is the Lagrange multipliers vector, and Y=diagy1,…,yn. To avoid numerical instability caused by ill-conditioning [19], we substitute K˜m,k⟵K˜m,k+σI, where σ is a small positive constant called jitter factor. Moreover, to calculate the inverse of the approximate matrix K˜−1 and avoid storing the complete n×n matrix K˜, we iteratively perform the following series of operations:(16)T0−1=1σI,T1−1=T0+d1K˜1,k−1=T0+d1U˜1,kΛ˜1,kU˜1,kT−1⋯TM−1=TM−1+dMK˜M,k−1=TM−1+dMU˜M,kΛ˜M,kU˜M,kT−1,where Tm−1 is calculated using the SMW formula according to the last result Tm−1−1. After performing the series of M+1 operations, we can obtain K˜−1=TM−1.Lemma 1 (see [33]).
LetA and C both be invertible; then, Sherman–Morrison–Woodbury (SMW) formula gives an explicit formula for the inverse of matrices A+UCV if C−1+VA−1U is invertible.(17)​​A+UCV−1=A−1−A−1UC−1+VA−1U−1VA−1.We can find that when the mixture weight is known, formula (15) is same as the dual problem of SVM. Hence, we have(18)J=12α∗TYK˜Yα∗−eTα∗,where α∗ is the optimal solution minimizing (15). With α∗ considered a constant in J, J can be regarded as a function of d, and we calculate the gradient of the objective J with respect to dm.(19)∂J∂dm=12α∗TYU˜m,kΛ˜m,kU˜m,kT+σIYα∗=12α∗TYU˜m,kΛ˜m,kU˜m,kTYα∗+σ2α∗Tα∗.We use the reduce gradient method in [27] to deal with problem (14). First, for satisfying the L1-norm constraint on the weight vector d in (14), we calculate the reduced gradient of d:(20)∇redJm=∂J∂dm−∂J∂dμ,∀m≠μ,μ=argmaxmdm,∇redJμ=∑m≠μ∂J∂dμ−∂J∂dm,μ=argmaxmdm,where ∇redJ denotes the reduced gradient of Jd. Let dμ be the largest element of the vector d, and μ be the corresponding index. Obviously, −∇redJ would be a descent direction. However, if ∃m that makes dm=0 with −∇redJm<0, then dm⟶0−, which does not meet the nonnegative restriction. Therefore, −∇redJm needs to be set to 0. Update descent direction is as follows:(21)Dm=0,dm=0,∇redJm>0,−∇redJm,dm>0,m≠μ,−∇redJμ,m=μ.In general, MKL uses a two-step training method. It requires frequent calls to support vector machine solvers, which is prohibitive for large scale problems. Therefore, after each update ond, we are not eager to substitute it into support vector machine solvers to update α∗, but continue to look for the maximum allowable step length in this descent direction until the objective function value stops declining. Finally, we get the optimal step length by the line search method. The complete algorithm of the multi-Nyström method with MKL is summarized in Algorithm 1.Algorithm 1: The proposed MKLMO algorithm.
Input. DatasetD; number of landmark points l; rank k; number of kernels M; predefined kernel function km⋅,⋅.Output. Classification result for instancex(1)
DrawM subsets of balanced landmark points L=Lmm=1M with each Lm=cm,1,…,cm,l(2)
Calculate subkernel matricesCm∈ℝn×l between the instances in D and Lm and Wm∈ℝl×l among the instances in Lm with kernel km⋅,⋅(3)
Calculate the singular value decomposition onWm=UmΛmUmT(4)
ApproximateK˜m,k=Um,kΛm,kUm,kT according to (8)(5)
Initialize mixture weightsdm=1/Mform=1,2,…,M(6)
While stopping criterion not met do(7)
CalculateJd by SVM solver with K˜=∑mdmK˜m,k according to (15)(8)
Calculate descent directionD according to (19)–(21)(9)
Setμ=argmaxmdm,J∗=0,d∗=d,D∗=D(10)
WhileJ∗<Jddo(11)
Setd=d∗, D=D∗(12)
Setν=argminm|Dm<0−dm/Dm, γmax=−dν/Dν(13)
Setd∗=d+γmaxD, Dμ∗=Dμ−Dν, Dν∗=0(14)
CalculateJ∗ with K˜=∑mdm∗K˜m,k(15)
end while(16)
Line search alongD for optimal γ∗∈0,γmax(17)
Assignd⟵d+γ∗D(18)
end while


### 3.3. Kernel Stability Analysis

In some previous related works, Nyström is usually considered as a preprocessing method and mostly only study the approximate error bounds without considering the impact of the approximate on the performance of the kernel machine. In the following, we analyze the kernel stability of our method, bounding the relative performance based on the weighted kernel approximation error. It provides performance guarantees for our multi-Nyström approximate method in the context of large scale imbalanced classification.Proposition 1.
Letα∗ be the optimal solution for kernel SVM with kernel K and α˜ be the solution of kernel SVM with kernel K˜ obtained by Nyström approximation. Then,(22)α˜−α∗2≤θ21+K˜2λminΔwithΔ=∑m=1MdmK˜m−Km2α∗2,where λmin is the smallest eigenvalue of K˜, and θ is the constant from Hoffman’s bound independent on α∗ and α˜.Proof.
Define∇+fx≡x−x−∇fxX+ be the projected gradient, where X is the bounded constraint and xX+≡argminy∈Xx−y is the convex projection operator. It can be used to define an error bound according to the following theorem:Theorem 1 (see [34]).
Letx˜ be the nearest optimal solution of the convex optimization problem:(23)minx∈Xfx=gEx+bTx,with gt being σg strongly convex, ∇fx being ρ Lipschitz continuous, and X=x|Ax≤d is a polyhedral set. The optimization problem admits a global error bound:(24)x−x˜≤θ21+ρσg∇+fx,∀x∈X,where θ is the constant from Hoffman’s bound.Considering now the problemminα∈Ωf˜α=g˜CTYα−eTα with g˜x=1/2xTWk+x and bounded constraint Ω=α|yTα=0,0≤α≤C, then(25)minα∈Ωf˜α=12αTYCWk+CTYα−eTα.Note that the above problem is equivalent to problem (15) with the equality K˜=CWk+CT (Wk+ is SPSD), and we have(26)λminWk+x−y2≤∇g˜x−∇g˜yTx−y=x−yTWk+x−y⟹σg¯=λminWk+,∇f˜x−∇f˜y=YCWk+CTYx−y≤CWk+CTx−y=K˜x−y⟹ρ=K˜2.Letf be the dual objective function of multiple kernel learning problem (5) with the original kernel K=∑mdmKm, and f˜ be the objective function of approximate multiple kernel learning problem (9) with kernel K˜=∑mdmK˜m obtained by our multi-Nyström method (13). Consider now α∗ and α˜ as the optimal solutions of fα and f˜α, respectively. We have(27)∇f˜α∗=YK˜Yα∗−YKYα∗+YKYα∗−e=YK˜−KYα∗+∇fα∗,where we use the fact that ∇fα∗=0and∇f˜α˜=0; therefore,(28)∇f˜α∗2=∑m=1MdmYK˜m−KmYα∗2≤∑m=1MdmK˜m−Kmα∗2≤∑m=1MdmK˜m−Km2α∗2,where K˜m−Km2 is the spectral norm error of the mth Nyström approximate based on the mth subset of landmark points.Furthermore, we use the inequality∇+f˜α∗2≤∇f˜α∗2 of the kernel SVM given by [35] (proof of Theorem 2) along with Theorem 1 to upper bound the norm difference between the optimal solutions of fα and f˜α:(29)α∗−α˜2≤θ21+ρσg˜∇+f˜α∗2≤θ21+ρσg˜∇f˜α∗2≤θ21+ρσg˜∑m=1MdmK˜m−Km2α∗2.The proposition shows us the norm differenceα∗−α˜2 is controlled by a weighted Nyström approximate error. And it guides us to focus on approximating the kernel matrices with greater weights for getting a better learning performance.


## 3.1. Multi-Nyström Method

We divide the imbalance datasetD=xi,yii=1n into the minority class set D+=xi,+1i=1n+ and the majority class set D−=xi,−1i=1n−. When there are irregularities in the imbalanced data (such as small disjuncts, overlapping, and noise [30]) and the data scale is large, applying a single kernel may make the model biased, skew, or misleading. Inspired by the MKL algorithm [31], we construct a low rank approximate multiple kernel framework as follows:(9)Kx,xi≈∑m=1MdmK˜m,kxm,xim,withdm≥0,where K˜m,k corresponds to the rank-k approximation of each base kernel matrix Km, and dm is the corresponding mixture weight. As for the Nyström method, a key aspect is the sampling scheme [32]. For reducing the sensitivity to skewness in data, we adopt the stratified undersampling of the majority class to select M subsets of landmark points written as L=Lmm=1M with each Lm=cm,1,…,cm,l. The subkernel matrix between all instances and the landmark points can be expressed as(10)C=C1,…,CM∈ℝn×Ml,where Cm∈ℝn×l. Then, we perform the standard Nyström method on each Cm independently to get a rank-k approximation K˜m,k=CmWm,k+CmT of each base kernel matrix Km. Finally, by linearly combining these approximations, we can get the general form of approximation multiple kernel K˜:(11)K˜=C1,…,CMd1W1,k+⋱dMWM,k+C1T⋮CMT.Given the mixture weightdm, the feature of each instance xi can be evaluated as(12)ϕ˜xi=d1W1,k+K1xi,c1,1,…,K1xi,c1,lT⋮dMWM,k+KMxi,cM,1,…,KMxi,cM,lT.Similarly, for the convenience of subsequent calculations, formula (11) can be rewritten as(13)K˜=U˜1,k,…,U˜M,kd1Λ˜1,k⋱dMΛ˜M,kU˜1,kT⋮U˜M,kT.where U˜m,k∈ℝn×k, and Λ˜m,k∈ℝk×k denotes the approximate decomposition of Km obtained by (8). Figure 1 shows the proposed multi-Nyström method and includes an optimization process of the mixture weights detailed futher in next subsection.Figure 1
Architecture of the proposed multi-Nyström method.M subsets from the majority class are sampled to construct balanced landmark points and then the Nyström method is used to obtain the approximate base kernel matrices and the multiple kernel learning (MKL) algorithm is applied to optimize the mixture weights and train classifier. Finally, the trained kernel classifier based on multi-Nystrom is obtained.When the mixture weightdm is fixed or known, the total time complexity of the multi-Nyström method is OMl3+Mnlk. Although our method requires M times more CPU resources than the standard Nyström method, M≪n is typically O(1) for large scale data, and our method can compute in parallel in the distributed computing environment. Moreover, the SVD on the subkernel matrix W is decomposed into that on M much smaller matrices would also accelerate the calculation process.


## 3.2. Optimization to Mixture Weights

The purpose of MKL is to learn an optimal convex combination of a series of kernels during training. Based on the aforementioned definition, we propose an approximate multiple kernel learning framework for large scale imbalanced classification by modifying the original MKL framework in [26](14)minJdsuch thatd12=1,dm≥0,m=1,…,M,where(15)Jd=minα12αTYK˜Yα−eTαs.t.yTα=00≤α≤C,where α is the Lagrange multipliers vector, and Y=diagy1,…,yn. To avoid numerical instability caused by ill-conditioning [19], we substitute K˜m,k⟵K˜m,k+σI, where σ is a small positive constant called jitter factor. Moreover, to calculate the inverse of the approximate matrix K˜−1 and avoid storing the complete n×n matrix K˜, we iteratively perform the following series of operations:(16)T0−1=1σI,T1−1=T0+d1K˜1,k−1=T0+d1U˜1,kΛ˜1,kU˜1,kT−1⋯TM−1=TM−1+dMK˜M,k−1=TM−1+dMU˜M,kΛ˜M,kU˜M,kT−1,where Tm−1 is calculated using the SMW formula according to the last result Tm−1−1. After performing the series of M+1 operations, we can obtain K˜−1=TM−1.Lemma 1 (see [33]).
LetA and C both be invertible; then, Sherman–Morrison–Woodbury (SMW) formula gives an explicit formula for the inverse of matrices A+UCV if C−1+VA−1U is invertible.(17)​​A+UCV−1=A−1−A−1UC−1+VA−1U−1VA−1.We can find that when the mixture weight is known, formula (15) is same as the dual problem of SVM. Hence, we have(18)J=12α∗TYK˜Yα∗−eTα∗,where α∗ is the optimal solution minimizing (15). With α∗ considered a constant in J, J can be regarded as a function of d, and we calculate the gradient of the objective J with respect to dm.(19)∂J∂dm=12α∗TYU˜m,kΛ˜m,kU˜m,kT+σIYα∗=12α∗TYU˜m,kΛ˜m,kU˜m,kTYα∗+σ2α∗Tα∗.We use the reduce gradient method in [27] to deal with problem (14). First, for satisfying the L1-norm constraint on the weight vector d in (14), we calculate the reduced gradient of d:(20)∇redJm=∂J∂dm−∂J∂dμ,∀m≠μ,μ=argmaxmdm,∇redJμ=∑m≠μ∂J∂dμ−∂J∂dm,μ=argmaxmdm,where ∇redJ denotes the reduced gradient of Jd. Let dμ be the largest element of the vector d, and μ be the corresponding index. Obviously, −∇redJ would be a descent direction. However, if ∃m that makes dm=0 with −∇redJm<0, then dm⟶0−, which does not meet the nonnegative restriction. Therefore, −∇redJm needs to be set to 0. Update descent direction is as follows:(21)Dm=0,dm=0,∇redJm>0,−∇redJm,dm>0,m≠μ,−∇redJμ,m=μ.In general, MKL uses a two-step training method. It requires frequent calls to support vector machine solvers, which is prohibitive for large scale problems. Therefore, after each update ond, we are not eager to substitute it into support vector machine solvers to update α∗, but continue to look for the maximum allowable step length in this descent direction until the objective function value stops declining. Finally, we get the optimal step length by the line search method. The complete algorithm of the multi-Nyström method with MKL is summarized in Algorithm 1.Algorithm 1: The proposed MKLMO algorithm.
Input. DatasetD; number of landmark points l; rank k; number of kernels M; predefined kernel function km⋅,⋅.Output. Classification result for instancex(1)
DrawM subsets of balanced landmark points L=Lmm=1M with each Lm=cm,1,…,cm,l(2)
Calculate subkernel matricesCm∈ℝn×l between the instances in D and Lm and Wm∈ℝl×l among the instances in Lm with kernel km⋅,⋅(3)
Calculate the singular value decomposition onWm=UmΛmUmT(4)
ApproximateK˜m,k=Um,kΛm,kUm,kT according to (8)(5)
Initialize mixture weightsdm=1/Mform=1,2,…,M(6)
While stopping criterion not met do(7)
CalculateJd by SVM solver with K˜=∑mdmK˜m,k according to (15)(8)
Calculate descent directionD according to (19)–(21)(9)
Setμ=argmaxmdm,J∗=0,d∗=d,D∗=D(10)
WhileJ∗<Jddo(11)
Setd=d∗, D=D∗(12)
Setν=argminm|Dm<0−dm/Dm, γmax=−dν/Dν(13)
Setd∗=d+γmaxD, Dμ∗=Dμ−Dν, Dν∗=0(14)
CalculateJ∗ with K˜=∑mdm∗K˜m,k(15)
end while(16)
Line search alongD for optimal γ∗∈0,γmax(17)
Assignd⟵d+γ∗D(18)
end while


## 3.3. Kernel Stability Analysis

In some previous related works, Nyström is usually considered as a preprocessing method and mostly only study the approximate error bounds without considering the impact of the approximate on the performance of the kernel machine. In the following, we analyze the kernel stability of our method, bounding the relative performance based on the weighted kernel approximation error. It provides performance guarantees for our multi-Nyström approximate method in the context of large scale imbalanced classification.Proposition 1.
Letα∗ be the optimal solution for kernel SVM with kernel K and α˜ be the solution of kernel SVM with kernel K˜ obtained by Nyström approximation. Then,(22)α˜−α∗2≤θ21+K˜2λminΔwithΔ=∑m=1MdmK˜m−Km2α∗2,where λmin is the smallest eigenvalue of K˜, and θ is the constant from Hoffman’s bound independent on α∗ and α˜.Proof.
Define∇+fx≡x−x−∇fxX+ be the projected gradient, where X is the bounded constraint and xX+≡argminy∈Xx−y is the convex projection operator. It can be used to define an error bound according to the following theorem:Theorem 1 (see [34]).
Letx˜ be the nearest optimal solution of the convex optimization problem:(23)minx∈Xfx=gEx+bTx,with gt being σg strongly convex, ∇fx being ρ Lipschitz continuous, and X=x|Ax≤d is a polyhedral set. The optimization problem admits a global error bound:(24)x−x˜≤θ21+ρσg∇+fx,∀x∈X,where θ is the constant from Hoffman’s bound.Considering now the problemminα∈Ωf˜α=g˜CTYα−eTα with g˜x=1/2xTWk+x and bounded constraint Ω=α|yTα=0,0≤α≤C, then(25)minα∈Ωf˜α=12αTYCWk+CTYα−eTα.Note that the above problem is equivalent to problem (15) with the equality K˜=CWk+CT (Wk+ is SPSD), and we have(26)λminWk+x−y2≤∇g˜x−∇g˜yTx−y=x−yTWk+x−y⟹σg¯=λminWk+,∇f˜x−∇f˜y=YCWk+CTYx−y≤CWk+CTx−y=K˜x−y⟹ρ=K˜2.Letf be the dual objective function of multiple kernel learning problem (5) with the original kernel K=∑mdmKm, and f˜ be the objective function of approximate multiple kernel learning problem (9) with kernel K˜=∑mdmK˜m obtained by our multi-Nyström method (13). Consider now α∗ and α˜ as the optimal solutions of fα and f˜α, respectively. We have(27)∇f˜α∗=YK˜Yα∗−YKYα∗+YKYα∗−e=YK˜−KYα∗+∇fα∗,where we use the fact that ∇fα∗=0and∇f˜α˜=0; therefore,(28)∇f˜α∗2=∑m=1MdmYK˜m−KmYα∗2≤∑m=1MdmK˜m−Kmα∗2≤∑m=1MdmK˜m−Km2α∗2,where K˜m−Km2 is the spectral norm error of the mth Nyström approximate based on the mth subset of landmark points.Furthermore, we use the inequality∇+f˜α∗2≤∇f˜α∗2 of the kernel SVM given by [35] (proof of Theorem 2) along with Theorem 1 to upper bound the norm difference between the optimal solutions of fα and f˜α:(29)α∗−α˜2≤θ21+ρσg˜∇+f˜α∗2≤θ21+ρσg˜∇f˜α∗2≤θ21+ρσg˜∑m=1MdmK˜m−Km2α∗2.The proposition shows us the norm differenceα∗−α˜2 is controlled by a weighted Nyström approximate error. And it guides us to focus on approximating the kernel matrices with greater weights for getting a better learning performance.


## 4. Experiments

In this section, in order to validate the efficiency of the proposed method in solving large scale imbalanced problems, we compare our method against kernel methods including SVM and MKSVM (multiple kernel SVM), as well as the Nyström approximation method. All experiments are implemented on a PC with Intel quad-core i7-8565U CPU@1.80 GHz and 8 GB memory.


### 4.1. Implementation

We implement our experiments on five real-world imbalanced datasets from the KEEL data repository (https://keel.es/) and the LIBSVM archive (https://www.csie.ntu.edu.tw/cjlin/libsvmtools/datasets/) (Table 1). For a fair comparison, we perform 10 times stratified 5-fold cross-validation and report the average result. We use LIBSVM (https://www.csie.ntu.edu.tw/cjlin/libsvm/index.html) and SimpleMKL (https://asi.insa-rouen.fr/enseignants/arakoto/code/mklindex.html) to run kernel SVM and MKSVM, respectively. As the kernel type, all experiments use the Gaussian kernel with bandwidth σ in the range of log10σ=−1,0,1,2. Because we are interested in relative performance, we empirically set the trade-off parameter C = 100. In this study, we adopt the following three evaluation measures of the classification performance on imbalanced datasets: F1 score, G-mean, and area under ROC curve (AUC).(30)PRE=TPTP+FP,REC=TPTP+FN,SPE=TNTN+FP,F1score=2×PRE×RECPRE+REC,G−mean=REC×SPE,where TP, TN, FP, and FN represent the number of true-positive, true-negative, false-positive, and false-negative instances, respectively. F1 score measures the classification performance on the minority class. G-mean reflects the overall classification performance. AUC works well for comparing performance between algorithms [36].Table 1
Datasets used in experiments
Dataset# feature# instanceIRPoker-8-9_vs_510207582Abalone1984174129.44Page-blocks01054728.79USPS (class 9 against all)256929812.13


### 4.2. Experimental Results

Table2 provides the average experimental results of the proposed method and the other three algorithms on the four imbalanced datasets using the above three measures. We first compare SVM and the standard Nyström method. The Nyström method uses uniform sampling without replacement to approximate the kernel matrix, which relieves the model’s sensitivity to class imbalance to a certain extent. For example, on the Poker-8-9_vs_5 dataset, in terms of G-mean, the Nyström method improves nearly 7 times more than SVM. However, we can also see that in terms of AUC and F1 score, there still exits a large gap in model accuracy as compared with SVM.Table 2
F1 score, G-mean, and AUC results of different algorithms on four datasets
DatasetsMeasuresSVMNyströmMulti-NyströmMKSVMPoker-8-9_vs_5F10.05710.03270.05850.1906G-mean0.03990.33570.51400.1589AUC0.81070.61060.79530.7942Abalone19F10.06110.02000.03340.0569G-mean0.06610.29140.35000.0661AUC0.74870.52030.60940.7263Page-blocks0F10.80610.79540.81710.8342G-mean0.70180.72920.71150.7381AUC0.98570.97530.95850.9904USPSF10.89910.66880.88530.9102G-mean0.87880.85930.84080.8807AUC0.99390.96080.98740.9963Next, we compare our multi-Nyström method with the standard Nyström method. The experimental results clearly demonstrate that our method outperforms the Nyström method, especially in the context of extreme imbalance. This mainly benefits from the use of undersampling of the majority class, which can effectively balance the class distribution. Moreover, it can be seen that multi-Nyström can improve the accuracy of the model. For example, with the same number of landmark points, theF1 score and AUC value of multi-Nyström on the USPS dataset are closer to that of SVM or even higher on Poker-8-9_vs_5 and Page-blocks0 datasets.Note that our method is also a type of approximation of MKL, and finally, we also examine the performance of MKL-based MKSVM. From the results, we can see the effect of using MKL to represent input data, which also implicitly explains how our method achieves better accuracy at the expense of more computations.


### 4.3. Discussion

In this part, we further discuss the impact of different parameters on performance. In the first experiment, in order to study the impact of the number of sampling landmark points on the classification performance, we fix the approximate rank parameter and successively increase the number of sampling landmark points, and then train and test the SVM model on four datasets, with results as shown in Figure2. We can see that as the number of sampling landmark points increases, although there are some fluctuations, the performance of our method and Nyström still presents a rising trend. Moreover, except for few cases, our method uses fewer landmark points and can still yield higher G-mean.Figure 2
Classification performance with different numbers of instances sampled on four datasets.
(a)(b)(c)(d)In the second experiment, we study the performance with the variance of the rank parameter. Figure3 shows the G-mean on four datasets by varying the approximate rank. They show us that with the same approximate kernel rank, our method can achieve better classification performance than others.Figure 3
Classification performance with different ranks of the kernel approximation on four datasets.
(a)(b)(c)(d)Finally, we further compare the running time of our method and MKSVM. We report the results on two datasets USPS and Page-blocks in Figure4. The results show that our method can significantly speedup the MKL process under guaranteed performance. For example, on the USPS dataset, our method can reduce the running time by more than one order of magnitude. The main reason is due to the low-rank attribute of the approximate kernel matrix that speeds up the MKL algorithm process.Figure 4
Timing performance with different numbers of kernels on two datasets.
(a)(b)For further analysis of the experimental results, we perform the Friedman test with respect to theF1 score. First, we calculate the average ranks of SVM, Nyström, multi-Nyström, and MKSVM as shown in Figure 5. It can be noticed that MKSVM gives the best performance. Meanwhile, the SVM and the proposed multi-Nyström rank similarly. In a comparison of k algorithms on N datasets, considering ri as the average ranking of the ith algorithm, the Friedman variable FF can be calculated as follows:(31)FF=N−1χF2Nk−1−χF2,with(32)χF2=12Nkk+1∑i=1kri2−kk+124,where FF is distributed to 4−1 and 4−14−1 degrees of freedom. For our experiments, FF=10.3333. The critical value of F3,9 is 3.8625 for α=0.05. Since FF>F3,9, we can reject the null hypothesis that all the algorithms have the same performance. Then, we perform the Nemenyi test to compare algorithms pairwise. The critical difference is calculated as follows:(33)CD=qakk+16N,considering α=0.05 and CD=2.3452. The difference between the average ranking of the SVM, Nyström, and multi-Nyström with MKSVM is 1.0, 2.75, and 1.25, respectively. Hence, we can state that the best MKSVM is significantly better than Nyström at α=0.05. However, the difference between the best MKSVM and the proposed multi-Nyström is not significant, which indicates the proposed method achieves better performance than the standard Nyström kernel classifier and more efficiency than the best MKSVM.Figure 5
Average rank of the four algorithms for four datasets.


## 4.1. Implementation

We implement our experiments on five real-world imbalanced datasets from the KEEL data repository (https://keel.es/) and the LIBSVM archive (https://www.csie.ntu.edu.tw/cjlin/libsvmtools/datasets/) (Table 1). For a fair comparison, we perform 10 times stratified 5-fold cross-validation and report the average result. We use LIBSVM (https://www.csie.ntu.edu.tw/cjlin/libsvm/index.html) and SimpleMKL (https://asi.insa-rouen.fr/enseignants/arakoto/code/mklindex.html) to run kernel SVM and MKSVM, respectively. As the kernel type, all experiments use the Gaussian kernel with bandwidth σ in the range of log10σ=−1,0,1,2. Because we are interested in relative performance, we empirically set the trade-off parameter C = 100. In this study, we adopt the following three evaluation measures of the classification performance on imbalanced datasets: F1 score, G-mean, and area under ROC curve (AUC).(30)PRE=TPTP+FP,REC=TPTP+FN,SPE=TNTN+FP,F1score=2×PRE×RECPRE+REC,G−mean=REC×SPE,where TP, TN, FP, and FN represent the number of true-positive, true-negative, false-positive, and false-negative instances, respectively. F1 score measures the classification performance on the minority class. G-mean reflects the overall classification performance. AUC works well for comparing performance between algorithms [36].Table 1
Datasets used in experiments
Dataset# feature# instanceIRPoker-8-9_vs_510207582Abalone1984174129.44Page-blocks01054728.79USPS (class 9 against all)256929812.13


## 4.2. Experimental Results

Table2 provides the average experimental results of the proposed method and the other three algorithms on the four imbalanced datasets using the above three measures. We first compare SVM and the standard Nyström method. The Nyström method uses uniform sampling without replacement to approximate the kernel matrix, which relieves the model’s sensitivity to class imbalance to a certain extent. For example, on the Poker-8-9_vs_5 dataset, in terms of G-mean, the Nyström method improves nearly 7 times more than SVM. However, we can also see that in terms of AUC and F1 score, there still exits a large gap in model accuracy as compared with SVM.Table 2
F1 score, G-mean, and AUC results of different algorithms on four datasets
DatasetsMeasuresSVMNyströmMulti-NyströmMKSVMPoker-8-9_vs_5F10.05710.03270.05850.1906G-mean0.03990.33570.51400.1589AUC0.81070.61060.79530.7942Abalone19F10.06110.02000.03340.0569G-mean0.06610.29140.35000.0661AUC0.74870.52030.60940.7263Page-blocks0F10.80610.79540.81710.8342G-mean0.70180.72920.71150.7381AUC0.98570.97530.95850.9904USPSF10.89910.66880.88530.9102G-mean0.87880.85930.84080.8807AUC0.99390.96080.98740.9963Next, we compare our multi-Nyström method with the standard Nyström method. The experimental results clearly demonstrate that our method outperforms the Nyström method, especially in the context of extreme imbalance. This mainly benefits from the use of undersampling of the majority class, which can effectively balance the class distribution. Moreover, it can be seen that multi-Nyström can improve the accuracy of the model. For example, with the same number of landmark points, theF1 score and AUC value of multi-Nyström on the USPS dataset are closer to that of SVM or even higher on Poker-8-9_vs_5 and Page-blocks0 datasets.Note that our method is also a type of approximation of MKL, and finally, we also examine the performance of MKL-based MKSVM. From the results, we can see the effect of using MKL to represent input data, which also implicitly explains how our method achieves better accuracy at the expense of more computations.


## 4.3. Discussion

In this part, we further discuss the impact of different parameters on performance. In the first experiment, in order to study the impact of the number of sampling landmark points on the classification performance, we fix the approximate rank parameter and successively increase the number of sampling landmark points, and then train and test the SVM model on four datasets, with results as shown in Figure2. We can see that as the number of sampling landmark points increases, although there are some fluctuations, the performance of our method and Nyström still presents a rising trend. Moreover, except for few cases, our method uses fewer landmark points and can still yield higher G-mean.Figure 2
Classification performance with different numbers of instances sampled on four datasets.
(a)(b)(c)(d)In the second experiment, we study the performance with the variance of the rank parameter. Figure3 shows the G-mean on four datasets by varying the approximate rank. They show us that with the same approximate kernel rank, our method can achieve better classification performance than others.Figure 3
Classification performance with different ranks of the kernel approximation on four datasets.
(a)(b)(c)(d)Finally, we further compare the running time of our method and MKSVM. We report the results on two datasets USPS and Page-blocks in Figure4. The results show that our method can significantly speedup the MKL process under guaranteed performance. For example, on the USPS dataset, our method can reduce the running time by more than one order of magnitude. The main reason is due to the low-rank attribute of the approximate kernel matrix that speeds up the MKL algorithm process.Figure 4
Timing performance with different numbers of kernels on two datasets.
(a)(b)For further analysis of the experimental results, we perform the Friedman test with respect to theF1 score. First, we calculate the average ranks of SVM, Nyström, multi-Nyström, and MKSVM as shown in Figure 5. It can be noticed that MKSVM gives the best performance. Meanwhile, the SVM and the proposed multi-Nyström rank similarly. In a comparison of k algorithms on N datasets, considering ri as the average ranking of the ith algorithm, the Friedman variable FF can be calculated as follows:(31)FF=N−1χF2Nk−1−χF2,with(32)χF2=12Nkk+1∑i=1kri2−kk+124,where FF is distributed to 4−1 and 4−14−1 degrees of freedom. For our experiments, FF=10.3333. The critical value of F3,9 is 3.8625 for α=0.05. Since FF>F3,9, we can reject the null hypothesis that all the algorithms have the same performance. Then, we perform the Nemenyi test to compare algorithms pairwise. The critical difference is calculated as follows:(33)CD=qakk+16N,considering α=0.05 and CD=2.3452. The difference between the average ranking of the SVM, Nyström, and multi-Nyström with MKSVM is 1.0, 2.75, and 1.25, respectively. Hence, we can state that the best MKSVM is significantly better than Nyström at α=0.05. However, the difference between the best MKSVM and the proposed multi-Nyström is not significant, which indicates the proposed method achieves better performance than the standard Nyström kernel classifier and more efficiency than the best MKSVM.Figure 5
Average rank of the four algorithms for four datasets.


## 5. Conclusions

In this study, we propose a novel method to overcome the time and memory limitations of the standard Nyström method and extend it to the case of large scale imbalanced classification. In general, kernel approximation and model training are carried out separately. To obtain more accurate results, our method mixes multiple Nyström approximations and embeds them in the model training process to learn the model parameters and mixture weights simultaneously. In particular, the approximate kernel matrix yielded by our method is low rank and balanced. We also provide an error bound of the model solution based on our approximate method to guide us in improving the learning process. Experimental results show that our method can achieve a higher classification accuracy. On the other hand, it can dramatically improve the efficiency of exiting MKL algorithms.Potential improvements: there are still some caveats in our current solution. For example, due to the curse of kernelization, the number of support vectors grows in an unbounded manner when suffered the nonzero loss. This significantly increases the computational cost and can be infeasible for large scale problems. Future work will chiefly focus on more efficient variants of multi-Nyström involving budget kernel learning to address the issue.



---

*Source: 9911871-2021-06-14.xml*