Improved Learning Rates of a Functional Lasso-type SVM with Sparse Multi-Kernel Representation
Year: 2022

Abstract:
In this paper, we provide theoretical results of estimation bounds and excess risk upper bounds for support vector machine (SVM) with sparse multi-kernel representation. These convergence rates for multi-kernel SVM are established by analyzing a Lasso-type regularized learning scheme within composite multi-kernel spaces. It is shown that the oracle rates of convergence of classifiers depend on the complexity of multi-kernels, the sparsity, a Bernstein condition and the sample size, which significantly improve on previous results even for the additive or linear cases. In summary, this paper not only provides unified theoretical results for multikernel SVMs, but also enriches the literature on high-dimensional nonparametric classification.

heading: 1 Introduction
text: SVM was first introduced in [45] and has became one of the most popular machine learning algorithms in the past two decades. The standard SVM classification consists of two main ingredients, namely the hinge loss and the kernel embedding. The hinge loss is used to model the learning target and can often generate sparse solutions [38], while the kernel embedding is used to model nonlinear relationship between input features and response [39]. In [38], they provide a detailed overview of SVMs and related learning theory. More work on theoretical perspective of SVM have also been developed in recent years, such as [12, 53, 36, 33, 30, 24], among many others.
It is known that the performance of kernel machines largely depends on the data representation via the choice of kernel function [34, 16, 19, 28, 26, 48, 49]. Towards this direction, many approaches have been proposed for kernel selection under different frameworks. For example, Micchelli et al.[34] attempt to find an optimal kernel from a prescribed convex set of basis kernels; Wu et al.[46] optimize the scale parameter among various Gaussian kernels; and Ong et al.[35] study hyperkernels on the space of kernels and alternative approaches, including kernels selection by DC programming and semi-infinite programming. In particular, the seminal work of [22] proposes the so-called multiple kernel learning (MKL) method, learning SVM and a linear combination of kernels simultaneously, which has received a lot of attention in recent years [3, 50, 20, 19, 16, 23, 17, 27, 25, 29, 51]. To be precise, given a finite (possibly large) dictionary of symmetric positive semidefinite kernels {Km : m = 1, 2, ...,M} , one can try to find an ‘ideal’ kernel K as a convex combination of the kernels from a predefined family of potential candidates: K ∈ K :={∑M
m=1 θmKm : ∑M m=1 θm = 1, θm ≥ 0 } . This combination of multiple kernels corresponds to a
∗Corresponding Author
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
multi-kernel hypothesis space for learning:
HM := { M∑ m=1 fm(x) : fm ∈ HKm , x ∈ X } ,
whereHKm is a reproducing kernel Hilbert space (RKHS) induced by the kernel Km, as defined in Section 2. Given the learning rule, θm’s also need to be estimated automatically from the training data.
Besides flexibility enhancement, other justifications of MKL have also been proposed; such as each kernel function corresponds to different information source (e.g. text, image, gene), or classifiers from different spaces (corresponding to different kernels) are averaged to achieve better classification accuracy [8]. Under many of these situations, the number of candidate kernels M is often very large, even larger than the sample size n in some extreme cases. Interestingly, when one-dimensional linear (or additive) kernels are used and M is the dimensionality of covariates with M ≥ n, MKL reduces to high-dimensional linear (or additive) models, which have been widely studied in the statistics and machine learning literature [15, 6, 32].
Given the large number of kernels, it is common that not all the kernels are significantly relevant to the response. To avoid impairing generalization performance [54] and enhance interpretability, many redundant kernels should be removed accordingly. In view of generalization ability, interpretability and computational feasibility, a more parsimonious and flexible algorithm for MKL is to generate a sparse linear combination of kernels based on the training data, namely sparse MKL. From a statistical point of view, sparse MKL can be interpreted as a model selection task, and can also be viewed as an extension of sparse linear models or sparse additive models. In other words, sparse MKL provides an appropriate route to tackle the kernel learning issues in machine learning and the high-dimensional issues in statistics.
In literature, many regularized learning algorithms based on different regularization terms have been investigated in multi-kernel regression [3, 20, 18, 37, 41]. Particularly, in [37, 41], they established the optimal rates of convergence for the least square approaches in a related setting. In multi-kernel classification, Christmann and Hable [12] gave consistency and robustness property of non-sparse additive SVM when M is fixed; In [36, 42], they provided upper bounds on the estimation error and the excess risk in high-dimensional linear case or with finite number of basis functions. In summary, all the aforementioned work either focus on the regression problem with the quadratic losses, or only consider the parametric case for high-dimensional SVM.
The main focus of this paper is on a more challenging case with sparse multi-kernel approximation for SVM. That is, while the total number of kernels may be larger than the sample size, only a small number of kernels are needed to represent/approximate the target function, so that such a learning problem in the sense of approximation is sparse. Let X be a random variable of the input space X , and Y ∈ Y = {−1,+1} be the response. Define the theoretical oracle predictor of the classical SVM withinHM as
f∗ = arg min f∈HM E(f), with E(f) := E[φ(Y f(X))]. (1)
Here φ(t) := (1−t)+ is the hinge loss and the expectation is taken with respect to the joint distribution ρ defined on X × Y . In the sparse setting, one often assumes that f∗ has an additive and sparse representation withinHM , namely, f∗ = ∑ m∈S f ∗ m with an unknown subset S ⊂ {1, 2, ...,M} and f∗m ∈ Hm with ‖f∗m‖Km ≤ 1 for all m ∈ S. Of primary interest is the case with s := |S| M . Note that f∗ here is an optimal estimator withinHM , as opposed to the classical Bayes decision rule defined over all the measurable functions. Actually, the minimizer of the expected risk corresponding to the hinge loss is not continuous against the conditional probability [5].
The main contribution of this paper is to develop a set of theoretical results on multi-kernel SVM and the rates of convergence for nonparametric classification within the multi-kernel setting, including high-dimensional linear or additive classification as special cases. This paper provides refined error bounds for the excess risk, defined as E(f̂) − E(f∗), of the proposed estimator f̂ , as well as its estimation error ‖f̂ − f∗‖2. The proposed estimator in (5) is based on a regularization of the hinge loss with two fold `1 penalty terms, where one is used to control nonparametric sparsity and the other is to control functional smoothness. Particularly, Corollary 1 shows that with high probability, the
excess risk of the proposed estimator is upper bounded by
s Γ2(S, ρX) O ( n− 1 1+τ + logM n ) κ 2κ−1
under some regularity conditions, where τ corresponds to the spectral decay of each RKHS and is used to characterize functional complexity of kernels, κ is called the Bernstein parameter that reflects the low-density level of decision boundary, and Γ(S, ρX) is used to characterize correlation structure among multiple RKHS’s. The same rate also holds true for ‖f̂ − f∗‖2κ2 following the Bernstein condition and the established results on the excess risk.
Furthermore, we establish the oracle rate of the relative misclassification error of f̂ in Theorem 2, which consists of the same rate as the excess risk of the estimator plus some additional sparse approximation error. By using this specific form of RKHS’s, we can incorporate many existing results as special cases of MKL for SVMs, and more importantly, several existing results can be improved by our derived ones. The detailed comparison between our general results with existing results is conducted in Section 3.3.
Notations. Define the L2 norm of a function f by ‖f‖22 = ∫ X |f(x)|2dρX(x) with marginal
distribution ρX . Given sample points {xi}ni=1, ‖fm‖2n := 1n ∑n i=1 fm(xi)
2 and ‖fm‖n is viewed as the empirical L2-norm. a ' bmeans that there are two positive constants c, C such that ca ≤ b ≤ Ca. Also, a = O(b) means that there is some positive constant C such that a ≤ Cb in probability, and a = o(b) means that a/b→ 0 in probability. To ease the notations, we write [M ] := {1, ...,M}.

heading: 2 Preliminaries and Algorithms
text: Given a compact set X , we denote a positive semidefinite kernel on X ×X , i.e., a symmetric function K : X × X → R satisfying ∑n i,j=1 cicjK(xi, xj) ≥ 0 for any x1, ..., xn in X and c1, ..., cn ∈ R. As showed in [2], a positive semidefinite kernel on X is associated with a unique Hilbert space HK consisting of functions on X , andHK is called a RKHS associated with the kernel K. RKHS is known for its reproducing property, i.e., for any f ∈ HK and x ∈ X , f(x) = 〈f,Kx〉K with Kx = K(x, ·). Another key property of RKHS is the spectral theorem, which assures that K admits the following eigen-decomposition:
K(x, x′) = ∑ `≥1 µ`ψ`(x)ψ`(x ′), for any x, x′ ∈ X , (2)
where µ1 ≥ µ2 ≥ ... ≥ 0 are its eigenvalues and {ψ` : ` ≥ 1} are the corresponding eigenfunctions, leading to an orthogonal basis in L2(ρX). These two fundamental properties of RKHS will be the foundation of our theoretical analysis.
To characterize functional complexities, we first introduce several basic facts of the empirical processes defined in RKHS. On basis of (2), for any δ ∈ (0, 1], we define
ωn(δ) :=
( 1
n n∑ `=1 ( µ` ∧ δ2
))1/2 ,
where a ∧ b means min{a, b}. For some constant A > 0, we define a quantity associated with ωn(δ) as
(K) := inf { ≥ √ A logM
n : ωn(δ) ≤ δ + 2,∀ δ ∈ (0, 1]
} .
The quantity (K) plays a key role in bounding the excess risk in RKHS [40, 20]. Given appropriate decay of µ`, the upper bound of (K) can be derived explicitly in Section 3.1.
Given the training sample {Xi, Yi}ni=1 i.i.d. from X ×Y , the standard SVM with a single kernel [45] solves the following optimization task
min f∈HK
{ 1
n n∑ i=1 φ(Yif(Xi)) + λ‖f‖2K
} , (3)
where λ is a regularization parameter that balances the tradeoff between the empirical risk and the function complexity. The theoretical properties of the standard SVM has been extensively studied in literature; see the earlier work of [11, 39, 7].
In the context of MKL, the sparse multi-kernel SVM [34] equips the empirical hinge loss with the `1 penalty,
min f= ∑M m=1 fm, fm∈HKm
{ 1
n n∑ i=1 φ(Yif(Xi)) + λ M∑ m=1 ‖fm‖Km
} . (4)
This type of sparse MKL method has been studied extensively in [34, 3, 20, 16], and among others. Essentially, it can be regarded as an infinite-dimensional version of the Lasso-type penalization [43].
In this paper, we present a different approach from (4) to formulate the sparse multi-kernel SVM. For simplicity, we assume that supx∈X |Km(x, x)| ≤ 1 for all m ∈ [M ]. We use a new L1-type regularization term partially inspired by the additive mean models [32]. Denote the bounded ball ofHM by BM := { f = ∑M j=1 fm : fm ∈ HKm , ‖fm‖Km ≤ 1 } , the regularization term we adopt for the multiple-kernel SVM combines the empirical L2-norms and RKHS-norms. Specifically, the proposed sparse multi-kernel SVM is formulated as
f̂ = M∑ m=1 f̂m := arg min f∈BM
{ 1
n n∑ i=1 φ(Yif(Xi)) + M∑ m=1 λm √ ‖fm‖2n + γm‖fm‖2Km } , (5)
where ‖fm‖n is used to enforce the sparsity in f̂ , whereas ‖fm‖Km is used to enforce the smoothness of each f̂m. Here (λm, γm)Mm=1 are the regularization parameters, which will be specified in our theoretical results. By finite representation of reproducing kernel, each additive estimator fm(·) = ∑n i=1 α
m i Km(xi, ·) for all m = 1, ...,M . A direct computation leads to√ ‖fm‖2n + γn‖fm‖2K = √ (αm)T K̃mαm
where K̃m = K2m n + γnKm. Here Km is the kernel matrix induced by Km at points {xi} n i=1. Note that K̃m is a semi-definite matrix, which can be written as K̃m = A2 with some matrix A. Hence, our original learning scheme in Eq.(5) can be transformed into a group Lasso optimization [32], and there exists several efferent numerical algorithms for solving it, such as proximal methods and coordinate descent ones.
This penalty term significantly differs from other sparsity penalties for nonparametric models in literature, such as ∑M m=1 ‖fm‖Km [22] and ∑M m=1(λ1‖fm‖n +λ2‖fm‖Km) [20, 37]. Although the former penalty often generates sparse solutions, it is difficult to establish its theoretical results, due to the fact that the ‖ · ‖K-norm cannot fully reflect the marginal distribution information. The latter penalty has been proved to enjoy some theoretical properties in [37], which is equivalent to the mixed L1-norm (∑M m=1 λm √ ‖fm‖2n + γm‖fm‖2Km ) in (5). Theoretically, based on empirical processes theory, our proposed approach can also achieve improved learning rates, like the penalized method with the penalty ∑M m=1(λ1‖fm‖n + λ2‖fm‖Km), which has been considered in [20, 31, 37] and others.
Remark. In general, ‖f̂‖n = 0 does not imply f = 0. However, in the case of any kernel-based minimization problem, ‖f̂‖n = 0 always implies f = 0. Based on the reproducing property of Mercer kernel, f(x) = 〈f,Kx〉K for any f ∈ HK , where HK is a reproducing kernel Hilbert space. In fact, if ‖f̂‖n = 0 holds, that is, f̂(xi) = 0 for all i = 1, . . . , n, by the reproducing property we have 〈f̂ ,Kxi〉K = 0 for all i. Hence, f̂ is orthogonal to the subspace Sn := span{Kx1 , ...,Kxn}. On the other hand, using the reproducing property again, any solution f̂ of kernel-based minimization problems has a finite representation within Sn. So we conclude f̂ = 0.
Remark. The use of the mixed norm regularization is mainly motivated by the following fact: i) the proposed estimation with the mixed norm can lead to very sharp learning rates; ii) the empirical norm ‖ · ‖n used for sparsity is much milder than ‖ · ‖K . There exists several related work on multi-kernel SVM. Under the setting of one-dimensional additive kernels, Christmann and Hable [12] constructed kernels for additive SVM and provided consistent and
statistically robust estimators under the fixed dimensional and non-sparse setting. Zhao and Liu [53] proposed a group Lasso penalty by means of finite-bases approximation to a RKHS, and particularly they developed an efficient accelerated proximal gradient descent algorithm and established oracle properties of the SVM under sparse ultra-high dimensional setting (e.g. M = o(en)). However, the additive SVM model may suffer from the lack of algorithmic flexibility and underfitting especially when the true model involves interaction effects. Similar concerns have been raised towards linear SVM as in [55, 21, 52].
Note that in the past decade, a lot of work on general MKL with logarithmic dependence on M have emerged [18, 41, 20], yet their analysis requires the loss function to be strongly convex, which rules out the commonly-used hinge loss for SVM. We also note that [13] provided an upper bound Op( √ logM/n) of the Rademacher complexity with the L1-norm constraint, which may lead to the same decay rate of the excess risk of SVM. However, this rate is not tight in general, since it is known that the fast rate of order 1/n can be attained for the linear case [11, 44].
This paper primarily focuses on the non-asymptotic analysis of the proposed sparse multi-kernel SVM method in (5) with an exponential number of kernels. Under the best ideal settings, the relative classification error of the proposed method is of near-oracle rate O(s log(M)/n), as if we knew the true sparsity in advance. Moreover, the method is adaptive to the sparsity of the learning problem and the margin parameter. In our proof, we have to face some technical challenges, such as dealing with non-smoothness of the hinge loss, functional complexities and NP-dimensionality.

heading: 3 Main Results
text: This section quantifies the asymptotic behavior of the proposed sparse multi-kernel SVM (5) in estimating the oracle predictor f∗ in (1). Its asymptotic convergence rates are established in terms of both generalization error and estimation error.
Assumption A (Bernstein condition). There exist universal constants c0 > 0 and κ ≥ 1, such that
E(f)− E(f∗) ≥ c0‖f − f∗‖2κ2 , for all f ∈ BM .
Assumption A is a lower bound for the hinge excess risk in term of the L2(ρX) norm, as a strong identification condition of the population quantity with the hinge loss. The Bernstein condition stems from [4] and it has been verified for the hinge loss in [1]. Particularly, for linear SVM, it has been verified in [36] that the Bernstein condition holds with κ = 1, leading to the fast learning rate. Related to the Bernstein condition, a more standard margin condition in [42] has been commonly assumed in literature, where E(f)−E(fc) ≥ c0‖f − fc‖2κ1 , and fc is the minimizer of the misclassification error over all possible measurable functions. As a consequence, the Bernstein condition is more stringent than the standard margin condition, and detailed discussion is referred to Proposition 8.3 of [1].
Since the complexity of a RKHS is determined by the decay rate of the eigenvalues µ`’s [39], we now introduce the following spectral condition for the subsequent analysis.
Assumption B (Spectral condition). There exist a sequence of 0 < τm < 1 and a universal constant c1 > 0, such that
µ (m) ` ≤ c1` −1/τm , ∀ ` ≥ 1, m ∈ [M ]. (6) Eq.(6) means the decay rate of the eigenvalues of kernel is polynomial. Note that τm < 1 is a very weak condition, due to the relation that ∑ `=1 µ (m) ` = E[Km(X,X)] ≤ 1. For example, if ρX is the Lebesgue measure on [0, 1], it is known that µ(m)` `−2α for the Sobolev classHKm =Wα2 with α > 12 . Indeed, spectral condition has a close quantitative relationship with the entropy number of the RKHS under mild conditions; see [40] for details.
Assumption C (Sup-norm condition). For the sequence of 0 < τm < 1 given in Assumption B, there exists some universal constant c2 > 0, such that
‖g‖∞ ≤ c2‖g‖1−τm2 ‖g‖ τm Km , ∀ g ∈ HKm , m ∈ [M ].
As pointed out in [40], under some mild conditions on HKm’s, Assumption C is equivalent to the spectral decay, as stated in Assumption B.
For some constant b > 0, we define a restricted subset ofHM by
FbS = { f ∈ BM : M∑ m=1 λm √ ‖fm − f∗m‖22 + 2(Km)‖fm − f∗m‖2Kj
≤ b ∑ m∈S λm √ ‖fm − f∗m‖22 + 2(Km)‖fm − f∗m‖2Kj } .
The set FbS is a cone in the spaceHM , where the components corresponding to j ∈ S dominate the remaining ones.
The following quantity is also crucial in our theoretical analysis, which is used to describe how ‘dependent’ these different RKHS’s are. Particularly,
Γ(S; ρX) := sup γ > 0 : γ (∑ m∈S ‖fm − f∗m‖22 ) ≤ ∥∥∥∥∥ M∑ m=1 (fm − f∗m) ∥∥∥∥∥ 2
2
, (f1, ..., fM ) ∈ FbS  . We can regard Γ(S; ρX) as a generalized correlation between the components corresponding to j ∈ S and j ∈ Sc, respectively. Assumption D (Correlation condition). There exists some universal constant c3, such that
Γ(S; ρX) > c3 > 0.
Loosely speaking, this represents the correlation among RKHS’s over the cone set where the components within the relevant indices S well “dominate" the remaining ones. Lemma 1 in [41] shows that Assumption D is related to two geometric quantities. In fact, Assumption D has been widely used for various sparse problems, such as [10] and [6] for linear models, and [20] and [41] for sparse MKL with the quadratic loss.
Remark. Assumptions A and D imply that c1/κ0 c3 ∑ m∈S ‖fm − f∗m‖22 ≤ ( E(f)− E(f∗) )1/κ over FbS , which is sufficient for deriving most of our results except for the estimation error. We also observe that, for the high-dimensional linear SVM, the restricted eigenvalue condition in [36] implies the above conclusion.

heading: 3.1 Oracle Rates
text: When the oracle predictor f∗ defined over HM is sparse, we now state the upper bounds on the excess risk and the estimation error of the proposed multi-kernel SVM in (5). We allow the number of kernels M and the number of active kernels s increases with the sample size n. Theorem 1. Suppose that Assumptions A, C and D hold, and all the following constraints are satisfied: 2M (Km) ≤ eM , λm ≥ 4C0C1 (Km) and γm ≥ 4 2(Km)/C20 for all m ∈ [M ]. Then with probability at least 1− 4M−A, the estimated `1-norm SVM function f̂ satisfies
E(f̂)− E(f∗) ≤ max  ( 4 √ 2c0C0 Γ(S, ρX) ) 2κ 2κ−1 (∑ m∈S λ2m ) κ 2κ−1 , 32 ∑ m∈S λm √ γm  . Additionally, there also holds
c0‖f̂ − f∗‖2κ2 ≤ max  ( 4 √ 2c0C0 Γ(S, ρX) ) 2κ 2κ−1 (∑ m∈S λ2m ) κ 2κ−1 , 32 ∑ m∈S λm √ γm  , with the same probability as above. Here A, C0 are positive constants specified in Lemma 1, and C1 specified in Proposition 1 may depend on A and c2.
The technical proof of Theorem 1 is given in Appendix A. It is easy to check that Theorems 1 also holds if one replaces M in the by an arbitrary M̃ ≥M such that log M̃ ≥ 2 log log n. In this case, the probability bounds in the theorems become 1 − 4M̃−A. It also has a number of corollaries,
obtained by specifying particular choices of kernels. As Assumption B does not require a lower bound of the spectral decay, so all the finite-dimensional RHKS’s, Sobolev classes and Gaussian kernels are covered in our settings. We here only present a corollary for the RKHS’s with infinite eigenvalues with decay rate as in Assumption B. In this case, the upper bound of (Km) is given by
(Km) '
{√ logM
n ∨ n− 1 2(1+τm)
} .
In particular, this type of scaling covers Sobolev spaces, consisting of functions with b 12τm c derivatives. Up to some constants, we now present a direct corollary from Theorem 1 in a homogeneous setting.
Remark. (C0, C1) are two constants independent of n,M or s. Their definitions rely on the result of Proposition 5 in [20], where their constant did not give an explicit form. So, we can not give a more explicit form on (C0, C1). Since γn = λ2n in our theory, there is no additional hyperparameter to be optimized. To explain the role of two hyperparameters, we rewrite the mixed penaltation with two different parameters as:
λn √ ‖fm‖2n + γn‖fm‖2K = √ βn‖fm‖2n + θn‖fm‖2K .
We see from the above equation that, βn is used to control sparsity, while θn is used to control functional smoothness, due to the fact that θn is a smaller order of βn, precisly, θn = β2n. Corollary 1. Under the same conditions of Theorem 1 and Assumption B holds in that each kernel with eigenvalues decays at rate µ(m)` = O(`
−1/τ ) for some common τ < 1. Then any solution f̂ to (5) with λm ' (Km) and γm ' 2(Km) for all m ∈ [M ] satisfies
max { ‖f̂ − f∗‖2κ2 , E(f̂)− E(f∗) } =
s
Γ2(S, ρX) O
( n− 1 1+τ + logM
n
) κ 2κ−1
,
with probability at least 1− 4M−A. Specially for κ = 1, we have
max { ‖f̂ − f∗‖22, E(f̂)− E(f∗) } =
s
Γ2(S, ρX) Op
( n− 1 1+τ + logM
n
) .
Corollary 1 considers the homogeneous setting that all the RKHS’s have the same complexities, denoted by the parameter τ in Assumption B. For the Gaussian kernel and the typical case with κ = 1, the parameter τ is close to zero and thus the excess risk of our estimator attains the order Op(s logM/n) up to the term Γ(S, ρX), which is the minimax rate of the least square parametric regression; see [37] for details.
It is worth noting that, the choices of the regularization parameters (λm, γm) are adaptive to the sparsity and the margin, whereas the sparsity parameter s and the Bernstein parameter κ are not needed to learn the proposed estimator. Moreover, as stated in [20], τm can be replaced by its empirical estimator based on Km = (Km(xl, xk))nl,k=1, this further implies that we can define two data-driven regularization parameters instead of (λm, γm). Here we omit the details to avoid repetition.
Remark. In view of the popularity of SVM in machine learning, this paper focuses on theoretical investigation on the hinge loss with a mixed functional norm under multi-kernel setting. In fact, the current technical analysis can be easily extended to any Lipschitz loss case, e.g., the Huber loss and the quantile loss used for robust methods. Yet we think this is also beyond the focus of this paper.

heading: 3.2 Relative Classification Error
text: The goal of a binary classification procedure is to predict the label Y ∈ {−1, 1} given the value of X . A binary classifier f : X → {−1, 1} is a function from X to Y which divides the input space X into two classes. Let us split ρ(X,Y ) = ρX(X)× P(Y |X), where ρX is the marginal distribution on X and P(·|x) is the conditional probability measure given X . The efficiency of a binary classifier f is measured by the so-called misclassification error
R(f) := P[f(X) 6= Y ] = ∫ X P[Y 6= f(x)|x]dρX(x).
It is known that fc(x) = sgn(2η(x) − 1) is a minimizer of R(f) over all measurable functions, where η(x) = P(Y = 1|X = x) is the conditional probability of Y = 1 given x. Thus, to assess the classification performance of a classifier f , its relative classification error, defined asR(f)−R(fc), is of some significance.
In empirical risk minimization, the optimization of misclassification error is difficult due to its non-convexity (i.e. 0/1 loss), and a common strategy is to find a surrogate convex loss to replace the non-convex 0/1 loss, such as the hinge loss, the logistic loss, or the quadratic loss. Therefore, to quantify the classification error of a SVM classifier, it is natural to ask for the connection between the hinge loss and the 0/1 loss. Recall from Theorem 9.21 in [14], for any measurable function f : X → R, the following inequality holds
R(sgn(f))−R(fc) ≤ E(f)− E(fc). (7)
Note that our general results are on the smooth function f∗ rather than on fc, and then it is often impossible to provide rates on the estimation of fc without stringent assumption on P(Y |X) andHs = ∪|S|=sHS withHS := { f = ∑ m∈S fm, fm ∈ Hm, ‖fm‖Km ≤ 1 } . Usually, fc is not necessarily sparse and smooth as f∗, we need to consider the approximation error between all the possible sparse multi-kernel spaces and fc, defined by A(Hs, fc) := inff∈Hs {E(f)− E(fc)} . The quantity A(Hs, fc) measures the approximation error of Hs in approximating fc. The sparsity s balances the approximation error A(Hs, fc) and the effective dimension of the function class Hs. Based on this notation, for any f we can rewrite E(f) − E(fc) = E(f) − E(f∗) + E(f∗) − E(fc) = E(f)− E(f∗) +A(Hs, fc). This together with Theorem 1 and (7) leads to the upper bounds of the relative classification error. Theorem 2. Assume the same conditions of Theorem 1 are all met. We choose λm ' (Km) and γm ' 2(Km) for all m ∈ [M ], then with probability at least 1− 4M−A, we have
R(sgn(f̂))−R(fc) = O ( 1 Γ(S, ρX) ) 2κ 2κ−1 (∑ m∈S 2(Km) ) κ 2κ−1 + ∑ m∈S 2(Km) +A(Hs, fc). In the homogeneous cases as Corollary 1, we also have
R(sgn(f̂))−R(fc) = s
Γ2(S, ρX) O
( n− 1 1+τ + logM
n
) κ 2κ−1
+A(Hs, fc).
As mentioned earlier, ordinary kernels including the Gaussian kernel and the Laplace kernel are universal in L1ρX in the sense that the approximation error A(Hs, fc) is negligible if fc ∈ L 1 ρX , and in this case the excess risk of the estimator dominates the approximation error. Note that f∗ is a sparse minimizer of E(·) defined on the multi-kernel class HM . From a model selection point of view, we are mainly interested in the selection of different RKHS’s, whereas the classical SVM in (3) focuses more on selection of parameters within a single RKHS; see [7] for details.
Similar to the common margin assumption in classification [11, 44, 1], the smaller Bernstein parameter κ implies the lower noise level of η(x) near 1/2. Particularly, our fast rate in Theorem 2 equals O ( n−
1 1+τ + logMn
) when κ = 1. If there is no assumption on the margin (κ → ∞), the rate
is arbitrarily close to O ( n−
1 1+τ + logMn
)1/2 when s is fixed, which matches the minimax lower
bounds without any low noise condition on the margin [47].

heading: 3.3 Related Work
text: As mentioned in the introduction, the popularity of sparse multi-kernel classification is mainly due to its flexibility and increased interpretability, including single kernel-based SVM and sparse highdimensional SVM as special cases. Hence, it is natural to compare the learning rate established in Theorem 1 and Corollary 1 over the multi-kernel class with some existing results in literature.

heading: I. Single kernel learning
text: In [11], the regularization error and the projection operator are introduced to derive convergence rates of the misclassification error. In particular, Theorem 10 there states that for a separation exponent θ,
the minimizer f̂ of the standard regularized learning scheme (3) satisfies
R(sgn(f̂))−R(f∗) = Op ( n− 1 1+2τ/θ+2τ ) , (8)
based on the relation between covering number and spectral decay. Our bound in Theorem 2 is always better than (8) even in their best case with θ → +∞.

heading: II. Multiple kernel learning
text: In [46], they analyzed the general SVM scheme by varying scale parameter σ of the Gaussian kernel, which can be regarded as a family of specific kernels. To be precise, the multi-kernel SVM in [46] is formulated by adding minimization on σ to the original learning scheme (3). In particular, Theorem 6 there states that when no approximation error is involved, the minimizer f̂ has the following error bound,
R(sgn(f̂))−R(f∗) = Op ( n− κ 2κ−1+τ ) , (9)
Note that when κ→ 1 corresponding to the lowest noise case, the error bound in (9) is of the best order Op(n− 1 1+τ ), which is the same as that in our Theorem 2.
Besides, without specification of learning algorithms, Cortes et al. [13] provided refined generalization bounds for learning kernels based on a convex combination ofM basis kernels with L1-regularization. When the hinge loss is used, Corollary 1 there can give the misclassification error with the order (logM/n) 1/2 , which is substantially slower than the error bound in our Theorem 2, derived by advanced empirical process techniques.

heading: III. High-dimensional learning
text: High dimensional data has attracted great interest in recent years, where the number of parameters (or dimensionality) can be much greater than the sample size. As mentioned earlier in Introduction, several work have considered high-dimensional linear or additive SVM classification.
(a) Linear SVM. Zhang et al. [52] proposed a sequence of non-convex penalized SVM’s in moderately high dimension, and gave variable selection consistency and oracle property for a statistical perspective. Also, Peng et al. [36] investigated the statistical performance of the L1-norm SVM in high dimension, and established refined error bound of its estimation error, with a near-oracle rate O( √ s logM/n), where M is the number of candidate features and s is the sparsity parameter. Note that the linear case corresponds to τ → 0 in the spectral assumption, and thus this rate in [36] is almost consistent with our derived result in Corollary 1.
(b) Additive SVM. Zhao and Liu [53] developed a sparse high dimensional nonparametric classification method with additive kernels, where each kernel Kj is one-dimensional function defined on each coordinate. Also, in their Theorem 5.1, they provided the oracle properties of the estimation error for the sparse additive SVM,
E(f̂)− E(f∗) = Op ( η̃ + s √ q logM
n
) , (10)
where η̃ is referred to as the approximation error and q is the number of finite base approximation to the additive components. Even in the best case with q = 1, the convergence rate in (10) is not comparable to our oracle rate established in Theorem 1, not to mention that q is often required to diverge at a polynomial order of n for functional flexibility.
The relation between our analysis and existing analyses are given in the follow table.
Method Penalty Optimization Convergence rate [13] ∑M m=1 ‖fm‖Km Group Lasso log(M)/ √ n
[37] ∑M m=1 ‖fm‖n + γn ∑M m=1 ‖fm‖Km SOCP sn − 11+τ + s logMn
[53] ∑M m=1 ‖fm‖2 Proximal GD s √ logM n4/5
This Paper ∑M m=1 √ ‖fm‖2n + γn‖fm‖2Km Group Lasso ( sn− 1 1+τ + s logMn ) κ 2κ−1

heading: 4 Numerical Experiments
text: In this section, we report the results of our numerical experiments on simulated data aimed at validating our theoretical results. First we consider constructing multiple kernels by random features of the spline kernel. A spline kernel of order q :
K2q (x,x ′) = 1 + ∞∑ k=1 cos (2πk (x− x′)) / ( k2q ) .
If the marginal distribution ofX is uniform on [0, 1], thenK2q (x,x′) = ∫ 1
0 ψ(x,ω)ψ(x,ω)%(ω)dω,
where ψ(x,ω) = Kq(x,ω) and %(ω) is also uniform on [0, 1]. We sample uniformly M times from [0, 1], so we get M kernels : ψ (x,ω1) , . . . , ψ (x,ωM ). Then we construct the target function f∗ by randomly choose Ms kernels and corresponding weights, where 0 < s < 1 is the sparse rate. For a classification problem, we map the target value to {+1,−1} labels. We generate different size of samples, then split them into train set and test set. The number of kernels M is set to 1000, the regularization parameters are set to be λ = n− 1 2(1+τ) , γ = n− 1 1+τ as from the theoretical analysis of Corollary 1. We repeat the training 20 times and estimate the averaged hinge loss on test data. The averaged hinge loss on the test data with different size of train data is given in Figure 1. From Figure 1(a, b) or (d, e), we can see that the line of best fit for empirical excess risks match the learning rate s · n− 1 1+τ (from Corollary 1), which verifies our theoretical findings. Figure 1(c) or (f) illustrates that at the same sparse rate s, the less the parameter τ , the better the performance. One the other hand, Figure 1(a, d) (b, e) or (c, f) shows that good performance can be obtained at a sparser setting. The above results is consistent with the theoretical analysis of Theorem 1 and Theorem 2.

heading: 5 Conclusion
text: We establish the first generalization error bounds for sparse multi-kernel SVMs, where the margin complexity term and the number of the potential kernels are considered carefully. The results we present significantly improve on previous results even for the additive or linear cases.

heading: Acknowledgment
text: This work is supported in part by the National Natural Science Foundation of China (No. 62076234, No.61703396, No.62106257), Beijing Outstanding Young Scientist Program NO.BJJWZYJH012019100020098, Intelligent Social Governance Platform, Major Innovation & Planning Interdisciplinary Platform for the "Double-First Class" initiative, Renmin University of China, China Unicom Innovation Ecological Cooperation Plan, Public Computing Cloud of Renmin University of China.

Review summaries:
This paper derives generalization bounds for the sparse multi-kernel Support Vector Machine (SVM) problem. Recall that previous literature has focused on sparse multi-kernel problems, but only for the Ridge regression (square loss instead of hinge loss), or on multi-kernel SVM but without the sparsity inducing penalization. To do so, the authors introduce a new penalization, see Equation (5). Under some assumptions already used in previous works, excess risk bounds and estimation error bounds are derived (Theorem 1), further explicited in terms of the eigendecay of the kernel (Corollary 1). Bounds on the classification error are also provided (Theorem 2).

This paper focus on the theoretical analysis of SVM with sparse multi-kernel approximation, where the total number of kernels may be larger than the sample size. More specifically, the refined bounds for the excess risk on multi-kernel SVM are provided, including high-dimensional linear or additive classification as special cases. The oracle rates of convergence of classifiers depend on the complexity of multi-kernels, the sparsity, the Bernstein condition and the sample size, which significantly improves the previous results even for the additive or linear cases.

The paper consists of a theoretical analysis for bounds on the excess risk and estimation of SVMs in a sparse MKL setting. Although the analysis is established for a larger class of combination of kernels with the Hinge loss, the derived bounds improve over existing ones, in terms of rates and dependency on the number of kernels, even in the more restrictive additive and linear cases and despite being adaptive to the unknown true sparsity. It is worth noting that the analysis relies on the miniminization of the SVM problem with a specific penalty term that is slightly different from the ones used in previous work. After deriving those theoretical results and comparing them to related work, the authors also provide some numerical experiments on simulated data whose generative process ensure that the true sparsity of the kernel combination is controlled. The experimental results seem to closely verify the theoretical findings.