Improved Learning Rates of a Functional Lasso-type SVM with Sparse Multi-Kernel Representation
Authors: shaogao lv
Junhui Wang
Jiankun Liu
Yong Liu
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Learning theory
Lasso-type SVM
Excess risk
Multi-kernel learning

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 improves on previous results even for the additive or linear cases. In summary, this paper not only provides unified theoretical results for multi-kernel SVMs, but also enriches the literature on high-dimensional nonparametric classification.

Improved Learning Rates of a Functional Lasso-type SVM with Sparse Multi-Kernel Representation
Shaogao Lv Junhui Wang", Jiankun Liu", Yong 2i
*Najjing Audit University
Gaoling School of Artificial Intelligence, Renmin University of China, Beijing, China Beijing Key Laboratory of Big Data Management and Analysis Methods, Beijing, China *City University of Hong Kong
Institute of Information Engineering, Chinese Academy of Sciences 1vag7 @vag7160nau 6θnau. edu. liuyonggsai Cruc. edu. cn
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 previous results even for the additive linear cases. In summary, this paper not only provides unified theoretical results for multi- kernel SVMs, but also enriches the literature high-dimensional nonparametric classification.
Introduction
SVM was first introduced [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 theoretical perspective of SVM have also been among many others.
developed in recent years, such as 12
33 30
24
It is known that the performance of kernel machines largely depends on the data representation via 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. [66 optimize the scale parameter among various Gaussian kernels; and Ong al. 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 choice of kernel function [34] [6 [9
28
26 48
the so-called multiple kernel learning (MKL) method, learning SVM and linear combination of kernels simultaneously, which has received lot of attention in recent years 3 50 20 [9 16
23
17 27
255 29 [51]. To be precise, given a finite (possibly large) dictionary of symmetric
positive semidefinite kernels {Km
2, ..., M. one can try find an 'ideal' kernel K as convex combination of the kernels from a predefined family of potential candidates: K E K. :-
M 0m
>M Om 1, Pm 2 0) This combination of multiple kemnlss corresponds to
Cooresponding Author
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

multi-kernel hypothesis space for learning:
M Σ
Had
fm((): Im E HK,. x E
where Hk.. is a reproducing kernel Hilbert space (RKHS) induced by the kernel Km- as defined in Section 2 Given the learning rule, On 's also need to be estimated automatically from the training data.
Besides flexibility enhancement, other justifications of MKL have also been proposed: such each kernel function corresponds to different information source (e.g. text, image, gene), or classifiers from different spaces (corresponding to different kernels) are averaged 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 in some extreme cases. Interestingly, when one-dimensional linear (or additive) kernels are used and M is the dimensionality of covariates with M 2 n, MKL reduces to tigh-dimensional linear (or additive) models, which have been widely studied in the statisties and machine learning literature 15 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 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 [8
37 41). Particularly, in [37 [1], they established the optimal rates of convergence for the least square approaches in a related setting. In mulli--eennd 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- 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 random variable of the input space X, and Y E V = {-1,+11 +1} } be the response. Define the theoretical oracle predictor of the classical SVM within MM as
f" arg min E(f), with E(f) ((x)) fENM
(1)
Here (1-)==111)) is the hinge loss and the expectation is taken with respect to the joint distribution p defined on X' x V. In the sparse setting, one often assumes that f has an additive and sparse representation within 7 namely, f Emes f with an unknown subset S C 21,2.... M and f" E Hm with f K... < for all m E S. Of primary interest is the case with s == ||| < M. Note that f" here an optimal estimator within H opposed 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 [.]
The main contribution of this paper is to develop set of theoretical results on multi-kerne SVM and the rates of convergence for nonparametrie classification within the multi-kernel setting. including high- nigh-dimensional linear or additive classification as special cases. This paper provides refined error bounds for the excess risk, defined as Eff - -(((), of the proposed estimator f. as well as its estimation error |lʃ - 1" The proposed estimator in (5) is based on regularization of the hinge loss with two fold E, penalty terms, where one is used to control nonparametric sparsity and the other is to control functional smoothness. Particularly, Corollary I shows that with high probability, the

---

excess risk of the proposed estimator is upper bounded by
0 117 log M Px)
under some regularity conditions, where corresponds the spectral decay of each RKHS and is used to characterize functional complexity of kernels, A is called the Bernstein parameter that reflects the low-density level of decision boundary, and (S,, px) is used to characterize correlation structure among multiple RKHS's. The same rate also holds true for Iff 1 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 the same rate as the excess risk of the estimator plus some additional sparse approximation error. By using this specific form of RKHS's, 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 function f by Il Jx ((x))) with marginal distribution px. Given sample points {az) [l = = (2,)² and Il is viewed as the empirical Lz-norm. = b means that there are two positive constants C such that < b S Ca. Also, a (b) means that there is some positive constant C' such that S Cb in probability, and a (b) means that a/b - 0 in probability. To ease the notations, we write [M] == {l, M).
2 Preliminaries and Algorithms
Given a compact set X, we denote a positive semidefinite kernel on X x X,, i.c., a symmetric function K X' x X + IR satisfying Zi.j-1 (xi,K( 2 0 for any I1, In in X' and Cı,..., On. E R. As showed in 22 positive semidefinite kernel on X' is associated with a unique Hilbert space HK consisting of functions on X, and Hy is called RKHS associated with the kernel K. RKHS is known for its reproducing property, i.c., for any f e Hk and E X, f(z) (f Kg) K with K₂ = K(x, -). Another key property of RKHS the spectral theorem, which assures that admits
the following rigen-decomposition
K(I, x')
Σ (ele(())ee(z"), for any 2, x' E X, E21
where #1
M2 2 are its eigenvalues and (te E 1) are the corresponding eigenfunctions, leading to an orthogonal basis in (pxx. 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 5 E (0, 1]. we define
1/2
wn (6) =
(ue A 02)
where a A b means min(a, b). For some constant A > 0, we define a quantity associated with w., (6) as
A Alog M n
<(K) = inf E
(.) S c 22,
The quantity e(K) plays a key role in bounding the excess risk in RKHS 40 20 decay of jie, the upper bound of < ((K) can be derived explicitly in Section 3.1
Given appropriate
Given the training sample (X,, 2 i.i.d. from X' x V/ the standard SVM with single kemel 45
solves the following optimization task
min JEHR
(YYS((X)) + XIIE
(3)
n
3

---

where À is 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 39
In the context of MKI., the sparse multi-kernel SVM penalty,
6. equips the empirical hinge loss with the &
{ (YJ((X)) + n 1=1
M
min
Σ
f
Fmllkmm
(4)
M fm. f. EMEHRm Ke
m==
This type of sparse MKL method has been studied extensively in Essentially, it can be regarded as an infinite-dimensional version of the Lasso-type penalization [43]
34
3
20 16. and among others.
In this paper, present different approach from (4) to formulate the sparse multi-kerne SVM. For simplicity, we assume that supzex [m(2, x) S 1 for all m E [M]. We use a new Ly-te regularization term partially inspired by the additive mean models 32]. Denote the bounded ball of MM by BM == { Σラ= fm fm E HK.. ll. S <1> } the regularization term we adopt for the multiple-kernn SVM combines the empirical L2-norms and RKHS-norms. Specifically, the proposed sparse multi-kernel SVM is formulated as
M
M
f
fm = arg min fEBM
o(x.((x)))
+ E Am Am//lfflll Ilmmll + Yoo fmmllmmll m==1
(5)
192=1
where Ilmllln is used to enforce the sparsity in f. whereas ml ll... is used to enforce the smoothness of each fm. Here (Am, (Am:Tm)mn mmm are the regularization parameters, which will be specified in our theoretical results, By finite representation of reproducing kernel, each additive estimator fm(() = Ei= 1i=10 at" Km (m( )
for all m = I,..., M. A direct computation leads to
VIl 7a 11 = / (amyr K m
where Km, K² + K m- Here K,, is the kernel matrix induced by Km at points {2; bei)"_, Note that Km semi-definite matrix, which can be written Kn, A with some matrix A. Hence, our original learning scheme in Eq. 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 Si literature, such as Σm=1 [l.m kl 22 and Σm= (A 1lx + X2 fml. 20 37). Although the former penalty often generates sparse solutions, it is difficult to establish its theoretical results, due to the fact that the || - 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 Li-norm
Σ m=1 1 Am / [l.mmmll + 7m fm lik 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= (Ar fl + fm k.,,, which has been considered in 20 31 37
and
others.
Remark. In general, Il.flln does not imply f == However, in the case of any kernel-based minimization problem, [[flln = always implics f = O. Based on the reproducing property of Mercer kernel, fxx) (f, K2)x for any f E Hx, where HK is reproducing kemel Hilbert space. holds, that is, f(x)) have (f, K2,)K = for all i. Hence, f is orthogonal to the subspace S, := span Kz, J. On the other hand, using the reproducing property again, any solution f of kernel-based minimization problems has a finite representation within S,, So we conclude f
In fact. if ||.
for all 1...., n, by the reproducing property we
Remark. The 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 || Il used for sparsity is much milder than ||
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- non-sparse setting, Zhao and Liu [53] proposed 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(e")). 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, lot of work on general MKL with logarithmic dependence on M have emerged [T8 41 20), yet their analysis requires the loss function to be strongly convex, which rules out the commonly
hinge loss for SVM. We also note that [13 provided an upper bound Op(Vlog log M/ /n) of the Rademacher complexity with the L --omm constraint, which may lead 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
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 (ss log( M))n) as 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 di-ddnniiionalty.
3
Main Results
This section quantifies the asymptotic behavior of the proposed sparse multi-kernel SVM ( in estimating the oracle predictor f" in (I). Its asymptotic convergence rates are established in terms of both generalization error and estimation error.
Assumption A (Bernstein condition). There exist universal constants co >> O and 2 1, such that
E(f) - E(F") 2 - f for all f E BB
Assumption A is a lower bound for the hinge excess risk in term of the L2(xx) norm, as 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 x = 1, leading to the fast learning rate. Related to the Bernstein condition, more standard margin condition in [42] has been commonly assumed in fal
literature, where 8(f) - {{f)) 2 co l| f and fe the minimizer of the misclassification error over all possible measurable functions. As consequence, the Bernstein condition is more stringent than the standard margin condition, and detailed discussion referred to Proposition 8.3 of [[.
Since the complexity of RKHS is determined by the decay rate of the eigenvalues ut's 's 39 we now introduce the following spectral condition for the subsequent analysis.
Assumption B (Spectral condition). There exist a sequence of 0 < Tm < 1 and a universal constant e 0, such that
P S ///m A 1, m E [M].
(6)
(6 means the decay rate of the eigenvalues of kernel is polynomial. Note that Tm < 1 is very weak condition, due to the relation that E 11 = (m X)) < 1. For example, if px the Lebesgue measure on [0, 1). it is known that Hig (m) f-2nx for the Sobolev class Hk.. W with Indeed, spectral condition has 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 < Tm. < given in Assumption B, there exists some universal constant C2 > 0, such that
|| S calløl12 Tm l TH k".
Vg E HKm, m E [M].
As pointed out in 40), under some mild conditions on HK.," 's, Assumption equivalent to the spectral decay, stated in Assumption B.
5

---

For some constant > O, we define restricted subset of 7t" by
M
F3 =
f E B
Σ
Am
Vllsm - + + (2( sm 11k
m=1
b
Am Amvllum 1 + @(mm)llm - J'm llick
mES
The set F'S a cone in the space H where the components corresponding to E S dominate the remaining ones.
The following quantity is also crucial in our theoretical analysis, which is used describe how "dependent" these different RKHS's ' are. Particularly,
M (f fin)
px): = sup 7>0:7
Σ MES
fl5m - ft
$
(fi..., faa) E F's
m==
We can regard (S: px) as a generalized correlation between the components corresponding to S and S respectively.
Assumption D (Correlation condition). There exists some universal constant C3, such that
Px): > c3 O.
Loosely speaking, this represents correlation among RKHS's over the cone set where the compo- nents within the relevant indices S well "dominate" the remaining ones. Lemma 1 in [41] shows that Assumption related to two geometric quantities. 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 Go c3 EmEss Il - f (8(f) 1/r over
1/wz
F&. 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.
3.1 Oracle Rates
When the oracle predictor f defined over HM 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 active kernels s increases with the sample size n.
Theorem 1. Suppose that Assumptions A, and D hold, and all the following constraints are satisfied: 2Mc(Km) m)) I M, Xm 2 AC00)c(K,m) and ni 2 4c2 (Km) C2 for all m E [M]. Then with probability at least 4M-A, the estimated l1 -norm SVM function f satisfies
(4V2cn
2x
E(f)-E(f") < max
Σ mES
32
Am Tmn
[x)
mES
Additionally, there also holds
44/2000o (())
21c
coll. - max
Σ X2
32
Am Von
ME
mES
with the same probability as above. Here A, Co are positive constants specified in Lemma 7 and C specified in Proposition may depend on and e2.
The technical proof of Theorem i given in Appendix A. is easy to check that Theorems also holds if one replaces M in the by arbitrary M > M such that log M 2 2 log log In this case, the probability bounds in the theorems become 1 - 4M- It also has number of corollaries,

---

obtained by specifying particular choices of kernels. As Assumption B does not require 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 ((m)) given by
log M n
E <(Km)=
vn 2(1+5m))
In particular, this type of scaling covers Sobolev spaces, consisting of functions with 2mm derivatives. Up some constants, we now present direct corollary from Theorem i homogeneous setting.
Remark. (Co. 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 explicit form. So, we not give more explicit form on (Co, C1). Since "n2 = X in our theory, there is no additional hyperparameter to be optimized. To explain the role of two hyperparameters, rewrite the mixed penaltation with two different parameters as:
Am / fl + mmllfmll = / f.llfmlR + 0mllfflll
We see from the above equation that, 3n is used to control sparsity, while O2 is used to control functional smoothness, due to the fact that O, is smaller order of B.,, precisly, On S".
Corollary 1. Under the same conditions of Theorem Sameemaaan and Assumption holds that each kernel with eigenvalues decays at rate (m²) O((-1/7)
((e-1/T)for for some common T < 1. Then any solution f to 5 with Am = <(Km) and 7m = (m) for all m E [M] satisfies
( (n-
log M n
max -1 E())
{(M)) -
(2(S,px)
with probability at least -M- Specially for K 1, we have
s max {IIF f E(f) - [x(S
Op 14r
log M n
Corollary D 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 T is close to zero and thus the excess risk of our estimator attains the order Op(s log M/n) up to the term T(S, Px). 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 (Am, Tm) are adaptive to the sparsity and the margin, whereas the sparsity parameter and the Bersstein parameter x are not needed to learn the proposed estimator. Moreover, as stated in (20). Tm can be replaced by its empirical estimator based on K,n (Km 24. =x)))= this further implies that we can define two data-driven regularization parameters instead of 7m): 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 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.
3.2 Relative Classification Error
The goal of a binary classification procedure is predict the label Y E (-1,1} given the value of X. A binary classifier f: X - (-1,1) a function from to y which divides the input space X' into two classes. Let split p(X,Y)= px (X) x P(Y|X), where px is the marginal distribution on X' and P(-(a)) is the conditional probability measure given X. The efficiency of a binary classifier is measured by the so-called misclassification error
1 P(V + f())la)dpx(1))
R()) = P))())
7

---

It is known that fa) sgn sgn (2m(()) 1) is minimizer of R(f) over all measurable functions,
where 7(2) P(Y 1| z) the conditional probability of Y = 1 given z. Thus, to assess the classification performance of classifier f, its relative classification error, defined as R(() - (R(s.), 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 common strategy to find 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 SVM classifier, it natural 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(fo) S E(f) E(fo).
Note that our general results are on the smooth function f rather than on fcr and then it is often impossible to provide rates on the estimation of fa without stringent assumption on P(Y|X) and H, U|s|=,H, Hs with Hs == = Emss fm. fm E Hm. fl flfll.... K... < 1]_ Usually, fe 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(H,, fe) == inf SEH, {&(f) - E(fe) J. The quantity A(Hs. measures the approximation error of Hg in approximating fc. The sparsity balances
the approximation eπror A(Hs, fc) and the effective dimension of the function class Hy. Based
on this notation, for any f we can rewrite E(f E(fe) E(f) E(f*) + E(f") E(fc)
E(f) - E(f") A(H,, fo). This together with Theorem and 7 leads to the upper bounds of the relative classification error.
Theorem 2. Assume the same conditions of Theorem 7 are all met. We choose Am <((Km and 7m = e² Km) for all m E [M), then with probability at least 1 - 4M-A, we have
R(ss ((TTS..x))
In In"I
26-1
Σ (KKm) mES
+ Σ (Km)
+.((Ha:
mES
In the homogeneous cases as Corollary 7 we also have
s R(sgn(f)) - R(fe) = rx(s,
O
n2 -
r/r +
log M
I6-1
A(Ho,
As mentioned earlier, ordinary kernels including the Gaussian kernel and the Laplace kernel are universal in T.Lx in the sense that the approximation error A(Hs, fe) is negligible if fe E L. and in this case the excess risk of the estimator dominates the approximation error. Note that r is sparse minimizer of E-) defined on the multi-kernn class H From a model selection point of view, we are mainly interested in the selection of different RKHS's, s. whereas the classical SVM in focuses more on selection of parameters within a single RKHS; see 7 for details.
Similar to the common margin assumption in classification x implies the lower noise level of n(x) near 1/2. Particularly, our fast rate in Theorem 2 equals
the smaller Bernstein parameter
O
M when K 1. If there no assumption on the margin + oo), the rate
arbitrarily close to O - log M 1/2
when fixed, which matches the minimax lower
bounds without any low noise condition on the margin 47
3.3 Related Work
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 high- dimensional SVM as special cases. Hence, is natural to compare the learning rate established in Theorem
I and Corollary over the multi-kernel class with some existing results in literature.
I. Single kernel learning
In [T]. the regularization error and the projection operator are introduced derive convergence rates of the misclassification error. In particular, Theorem 10 there states that for separation exponent 0,
8

---

the minimizer ff of the standard regularized learning scheme
3 satisfies
- 1 2-7023
based on the relation between covering number and spectral decay, Our bound in Theorem 2 always better than (8) even in their best case with 0 + +00.
is
II. Multiple kernel learning
In [4]. they analyzed the general SVM scheme by varying scale parameter a of the Gaussian kernel, which can be regarded as a family of specific kernels. To be precise, the multi-kemnll SVM in [46) is formulated by adding minimization on a to the original learning scheme (3) In particular, Theorem 6 there states that when no approximation error is involved, the minimizer has the following error bound,
R(sgn(f)) -(()) (n (n=
Note that when 1 corresponding the lowest noise case, the error bound in ( is of the best order Op(n I which is the same as that in our Theorem
Besides, without specification of learning algorithms, Cortes et al. 13 provided refined generalization bounds for learning kernels based on a convex combination of M basis kernels with L--reularizztton. When the hinge loss is used, Corollary there can give the misclassification error with the order (log M/ /n)1//2 which is substantially slower than the error bound in our Theorem derived by advanced empirical process techniques.
III. High-dimensional learning
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 statistical perspective. Also, Peng et al. SVM in high dimension, and established refined error bound of its estimation error, with near-oracle rate O( s log M/n), where M is the number of candidate features and is the sparsity parameter. Note that the linear case corresponds to r - in the spectral assumption, and thus this rate in [36] is almost consistent with our derived result in Corollary [
B6 investigated the statistical performance of the -nom
(b) Additive SVM. Zhao and Liu (53] developed a sparse high dimensional nonparametric classifi- cation method with additive kernels, where each kernel K2 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 ( n ss
q log M n
(10)
where 7j is referred to as the approximation enror and q is the number of finite base approximation to the additive components. Even in the best case with 1, the convergence rate in (10) is not
comparable to our oracle rate established in Theorem [ not to mention that is often required to diverge at polynomial order of for functional flexibility.
The relation between our analysis and existing analyses are given the follow table.
Method
Penalty
Optimization
Convergence rate
[3]
Fm Km
Group Lasso
log(M) MM/
37
| ΣM
n + Yn EME flfm Im
SOCP
sn
log
53
ΣMe 11 1/2
Proximal GD
$V
Ing M 4,75
This Paper
M / fl 12 + mmllffall
Group Lasso
sn
riv
+ log
I

---

mmothir EOCEIS lize
(a) 0.01, 7 0.02
(b) 0.01, T 0.2
(c) T {0.2, 0.4, 0.6, 0.8}
0.011
0.12
0:22
0.00
6.10
1406
0.36-
0.4-
0.6
0.2-
6.00
1259 2500
1353
1000
3500 1250
100
280
300
400
500
630
830
(d) 8 0.05, J = 0.02
(c)
0.05, T 0.2
(f) E (0.2, 0.4, 0.6,06
Figure I: The empirical excess error of our method on the test set with different size of training data n, the sparse rate and the parameter т. In (a, b, d, e), the blue line is the empirical excess error the test set, the dotted orange line is the optimal rate of theoretical findings, the dotted green line is the fit curve of the empirical excess error.
4 Numerical Experiments
In this section, we report the results of our numerical experiments on simulated data aimed at validating our theoretical results. First consider constructing multiple kernels by random features of the spline kernel. A spline kernel of order q:
K2g (x, (x,x') 1 + Σ cos (2 (x (x-xx x\)) (129).
If the marginal distribution of X is uniform on (0, 1). then K2 (x)x')= = Sy +x(x, w))/(x where (x w) Kg (x, w) and ((w) is also uniform [0, 1]. We sample uniformly M times from [0, 1], so we get M kernels : &i (x, w1) & (x, wxr.. Then we construct the target function f. by randomly choose Ms kernels and corresponding weights, where 0 < < 1 is the sparse rate. For classification problem, we map the target value to (+1,- -1} labels.
w) ()((w)))a
We generate different size of samples, then split them into train set and test set. The number of kernels
M is set 1000, the regularization parameters are set to be n शाोे, , = n 1|v as from the theoretical analysis of Corollary [ 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 I From Figure [ (a, b) or e), we can see that the line of best fit for empirical excess risks match the learning rate
ri+ (from Corollary D.. which verifies our theoretical findings. Figure I' e) or (f) illustrates that at the same sparse rate the less the parameter т, the better the performance, One the other hand, Figure [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
I and Theorem 2
Conclusion
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 previous results even for the additive or linear cases.
10

---

Acknowledgment
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 Intelligent Social Govemance Platform, Major Innovation & Planning Interdisciplinary Platform for the "Double-Fire Class" initiative, Renmin University of China, China Unicom Innovation Ecological Cooperation Plan, Public Computing Cloud of Renmin University of China.
NO.BIJWZZVHH1220100000000
References
[1] Alquier, Cottet, and G. Lecué. Estimation bounds and sharp oracle inequalities of regularized procedures with Lipschitz loss functions. Annals of Statistics, 47(4):2117-2144 2019.
[2] N. Aronszajn. Theory of reproducing kernels. Transactions of the American Mathematical Society, 68(3):337-404, 1950.
[3] F. Bach. Consistency of the group lasso and multiple kernel learning. Journal of Machine Learning Research, 9:1179-1225, 2008.
[4] P. L. Bartlett and S. Mendelson. Empirical minimization. Probability theory and related fields, 135(3)311-334, 2006.
[5] A. Belloni and V. Chernozuukov. fi-penalized quantile regression in high-dimensional sparse models. The Annals of Statistics, 39(1):82-130, 2011.
[6] P. J. Bickel, Y. Ritov, and A. B. Tsybakov. Simultancous analysis of lasso and dantzig selector. The Annals of statistics, 37(4): 770--1322.77 2009.
[7] G. Blanchard, O. Bousquet, and P. Massart. Statistical performance of support vector machines. Annals of Statistics, (6(2):489-531 2008.
[8] G. Blanchard, G. Lugosi, and N. Vayatis. On the rate of convergence of regularized boosting classifiers. Journal of Machine Learning Research, 4:861-89) 2003.
[9] O. Bousquet. A bennett concentration inequality and its application suprema of empirical processes, Comptes Rendus Mathematique, 334(6):495-500, 2002.
[10] E. Candes and T. Tao. The dantzig selector: Statistical estimation when is much larger than Annals of statistics, 35(6):2313-2351, 2007.
[11] D.-R. Chen, Q. Wu, Y. Ying, and D.-X. Zhou. Support vector machine soft margin classifiers:
error analysis. The Journal of Machine Learning Research, 5:1 5:1143-1175 1155, 2004.
[12] A. Christmann and R. Hable. Consistency of support vector machines using additive kernels for additive models. Computational Statistics Data Analysis, 56(4):854 2012.
[13] C. Cortes, M. Mohri, and A. Rostamizadeh. Generalization bounds for learning kernels. Proceedings of the 27th International Conference on Machine Learning (ICMI), pages 247- 254, 2010.
[14] Cucker and D. X. Zhou. Learning theory: an approximation theory viewpoint. Cambridge University Press, 2007.
[15] J. Fan and Y. Fan. High dimensional classification using features annealed independence rules. Annals of statistics, 36(6):2605-2637 2008
[16] M. Gönen and E. Alpaydın. Multiple kernel learning algorithms. The Journal of Machine Learning Research, 12:2211-20 1-2268, 2011.
[17] A. Jambulapati, Y. T. Lee, J. Li, S. Padmanabhan, and K. Tian. Positive semidefinite pro- gramming: mixed, parallel, and aatth-independent. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 789-802, 2020.

---

[18] M. Kloft and G. Blanchard. On the convergence rate of norm multiple kernel learning. The Journal of Machine Learning Research, 13(1):2465-2500 2012.
[19] M. Kloft, U. Brefeld, S. Sonnenburg, and A. Zien. (P-norm multiple kemnel learning. The Journal of Machine Leurning Research, 12:953-997, 2011.
[20] V. Koltchinskii and M. Yuan. Sparsity in multiple kernel learning. The Annals of Statistics, (666):3660-3695 2010.
[21] J.-Y. Koo, Y. Lee, Y. Kim, and C. Park. A bahadur representation of the linear support vector machine. The Journal of Machine Learning Research, 9: 9:14431336,, 2008.
[22] G. R. Lanckriet, N. Cristianini, P. Bartlett, E. Ghaoui, and M. I. Jordan. Learning the kernel matrix with semidefinite programming. Journal of Machine learning research, 5:27-72, 2004.
[23] J. Li. Y. Liu, R. Yin, H. Zhang, L. Ding, and W. Wang. Multi-class learning: From theory to algorithm. In Advances in Neural Information Processing Systems (NeurlPS), pages 1586-1595, 2018.
[24] S. Li and Y. Liu. Sharper generalization bounds for clustering. In Proceedings of 38th International Conference on Machine Learning (ICML., pages 6392-6402, 2021.
[25] F. Liu, X. Huang, Y. Chen, and J. Suykens. Fast learning in reproducing kernel krein spaces via signed measures. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics (AISTATS) ). pages 388-396, 2021.
[26] Y. Liu, Jiang, and S. Liao. Efficient approximation of cross-validation for kernel methods using bouligand influence function. In Proceedings of the 31 International Conference Machine Learning (ICML). pages 324-332, 2014.
[27] Y. Liu and S. Liao. Eigenvalues ratio for kernel selection of kernel methods. In Proceedings of 29th AAAI Conference on Artificial Intelligence (AAAI), pages 2814-2820, 2015.
[28] Y. Liu, S. Liao, S. Jiang, L. Ding, H. Lin, and W. Wang. Fast cross-validation for kernel-based algorithms. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1083-160 2020.
[29] Y. Liu, S. Liao, H. Lin, Y. Yue, and W. Wang. Infinite kemee learning: generalization bounds and algorithms. In Proceedings of the 31th AAAI Conference on Artificial Intelligence (AAAI), pages 2280-22888 2017.
[30] Y. Liu, Liu, and S. Wang. Effective distributed learning with random features: Improved bounds and algorithms. In Proceedings of the 9th International Conference Learning Representations (ICLR), 2021.
[31] S. Lv, H. Lin, H. Lian, and J. Huang. Oracle inequalities for sparse additive quantile regression in reproducing kernel hilbert space. The Annals of Statistics, 46(2):781-813, 2018.
[32] L. Meier, S. V. de Geer, and P. Bühlmann. High-dimensional additive modeling. The Annals of Statistics, 37(6B) 2009.
[33] M. Meister and I. Steinwart. Optimal learning rates for localized svms. The Journal of Machine Learning Research, 17:6722-6765, 2016.
[34] C. A. Micchelli, M. Pontil, and P. Bartlett. Learning the kernel function via regularization. Journal of machine learning research, 6: 1:999-11255, 2005.
[35] C. Ong, Smola, and R. Williamson. Learning the kernel with hyperkernels. Journal of machine learning research, 6: 6:1003-1071, 2005.
[36] B. Peng, L. Wang, and Y. Wu. An error bound for I support vector machine coeffeients in uitra-high dimension. The Journal of Machine Learning Research, 17:8279-8300 2016.
12

---

[37] G. Raskutti, M. J. Wainwright, and B. Yu. Minimax -ottiaa---pmmaalaaaaa rates for sparse additive models over kernel classes via convex programming. Journal of Machine Learning Research, 13:389-421 427, 2012.
[38] B. Scholkopf and A. J. Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. Adaptive Computation and Machine Learning series, 2018.
[39] I. Steinwart and A. Christmann. Support Vector Machine. Springer, 2008.
[40] I. Steinwart, D. Hus, and C. Scovel. Optimal rates for regularized least squares regression. In Proceedings of the Conference on Learning Theory (COLT), 2009.
[41] T. Suzuki and M. Sugiyama. Fast learning rate of multiple kernel learning: Trade-off be- tween sparsity and smoothness. In Proceedings of 15th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1152-1 113.. PMLR, 2012.
[42] B. Tarigan and S. A. V.
D. Geer. Classifiers of support vector machine type with & complexity regularization. Bernuuli,, (K6):1045-1076, 2006.
[43] R. Tibshirani. Regression selection and shrinkage via the lasso. Journal of the Royal Statistical Society Series B, 58(1):267-285) 1996.
[44] A. B. Tsybakov. Optimal aggregation of classifiers in statistical learning. The Annals of Statistics, 32(1):135-166, 2004.
[45] V. Vapnik. The Nature of Statistical Learning Theory. Springer Verlag, 2000.
[46] Q. Wu, Y. Ying, and D.-X. Zhou. Multi-kernel regularized classifiers. Journal of Complexity, 23(1):108-134 2007.
[47] Y. Yang. Minimax nonparametric classification. i. rates of convergence. IEEE Transactions Information Theory, 45(7):2271-22844 1999.
[48] R. Yin, Y. Liu, W. Wang, and D. Meng. Distributed Nyström kernel learning with commu- nications. In Proceedings of 28th International Conference on Machine Learning (ICML), 2021.
[49] R. Yin, Y. Liu, W. Weiping, and D. Meng. Sketch kernel ridge regression using circulant matrix: Algorithm and theory. IEEE transactions on neural networks and learning systems, 3 31(9):3512-3224 2019.
[50] Y. Ying and C. Campbell. Generalization bounds for learning the kernel. In Proceedings of the Conference on Learning Theory (COLT), 2009.
[51] X. Zhang and S. Liao. Incremental randomized sketching for online kernel learning. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 7394- 7403, 2019.
[52] X. Zhang, Y. Wu, L. Wang, and R. Li. Variable selection for support vector machines in moderately high dimensions. Journal of the Royal Statistical Society. Series B, Staristical methodology, 78(1):53, 2016.
[53] T. Zhao and H. Liu. Sparse additive machine. In Proceedings of 15th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1435-1443, 2012.
[54] J. Zhu, S. Rosset, R. Tibshirani, and J. Hastie. 4 no-mr support vector machines. In Advances in Neural Information Processing Systems (NeurIPS). Citeseer, 2003.
[55] H. Zou. An improved 1-norm svm for simultaneous classification and variable selection. In Proceedings of 10th International Conference on Artificial Intelligence and Statistics (AISTATS). pages 675-681. PMLR, 2007.
13


Reviews:
[{"review_id": "t4MPGIv7Xg", "reviewer": "Reviewer_9Qmw", "summary": "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In this paper,  a refined excess risk bound depends on the complexity of multi-kernels, the sparsity, the Bernstein condition and the sample size is provided, which significantly improves the previous results even for the additive or linear cases.  The oracle rate of the relative misclassification error is established, which consists of the same rate as the excess risk of the estimator plus some additional sparse approximation error. Many existing results can be incorporated as special cases of MKL for SVMs, so several existing results can be improved by the derived results. Moreover, the paper not only provides unified theoretical results for multi-kernel SVMs, but also enriches the literature on high-dimensional nonparametric classification. At last, the experiments on simulated data for SVM with sparse multi-kernel validate the theoretical findings.\n\nIn my opinion,  these results seem very interesting and important: the paper not only provides unified theoretical results for multi-kernel SVMs but also enriches the literature on high-dimensional nonparametric classification. Overall, I think this is a good theoretical and well-written paper, which is clearly of interest for the machine learning community.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Here are some concerns:\n1. It would be better to briefly give the sketch of the proof in the main body, especially some important lemma. For example, in Theorem 1 (Line 204), the paper claims \"A, C0 are positive constants specified in Lemma 1\". However, Lemma 1 only appears in Appendix and is not provided in the main body.\n2.  It would be better to give a table to clearly depict the advantage compared with the related results: such as single kernel learning, multiple kernel learning and high-dimensional learning.\n3. Some notations should be explained after their first appearance.  For example, in the equation after Line 108, what does the operator $\\wedge$ means? In Eq.(6), what does $\\mu_{l}^{(m)}$ means?\n4. The font size in Figure 1 is too small to be readable.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 days."}, "extra_text": {}}, {"review_id": "X9rquqSQsXa", "reviewer": "Reviewer_k7x5", "summary": "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).", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Although I do not question the technical quality of the present submission, I feel that authors fail at conveying a clear message that would benefit the Neurips audience. Among the main criticisms:\n\n- the scope of the paper appears to be relatively restricted, as only the hinge loss is studied\n- I might have missed something, but I cannot see why penalizing $||f_m||_n$ makes $\\hat{f}$ sparse. As far as I understand, the proposed penalization is some kind of mixed norm (up to the regularization parameters $\\lambda_m$ and $\\gamma_m$), whose outer norm is $||\\cdot||_1$ and inner norm is $\\sqrt{||\\cdot||_n^2 + ||\\cdot||_K^2}$. By the $\\ell_1$ outer norm, the solution to (5) contains many components $f_m$ with null inner norm, which means $||f_m||_n^2 + ||f_m||_K^2 = 0$, or again $f_m = 0$ as $||f_m||_K^2 = 0$. But I cannot see where is the impact of $||\\cdot||_n$, as we can have $||f||_n = 0$ but $f \\ne 0$. Am I missing something here?\n- moreover, problem (5) is solved with penalization AND norm constraints (the optimization is carried out on $B_M$). Usually one of the two is chosen but not both at the same time. Is there a particular reason? Overall, I feel this penalization could have been better introduced and motivated, as it is far from natural from the current reading\n- another point which is not discussed at all by the authors is the optimization of criterion (5). I think this aspect is very relevant for the Neurips community, and should not be omitted. A better theoretical objective which is impossible to minimize in practice would attract less interest. On the contrary, if the optimization of (5) is simpler than previous algorithms, this is definitely something that should be mentioned\n- the bounds feature constants that are not explicited (e.g., $C_0, C_1$), making them harder to interpret. In addition, criterion (5) involves a lot of hyperparameters ($\\lambda_m, \\gamma_m$), to the extent that it is difficult to extract a clear and direct message from the Theorems, nor to determine how the new penalization was key. The comparison in Section 3.3 is however useful.\n- the experiments are very basic and do not present any benchmark\n\nMinor comments:\n- l. 12: has bec*o*me\n- l. 24/32: the acronyms DC and RKHS are never defined\n- throughout the paper, authors keep referring at future equations, sections, which makes the reading incomfortable\n- l. 43: not clear around citation [46]\n- l. 100-101: RKHSs *are* known\n- l. 156: we *knew*\n- l. 200: increase*s*\n- l. 254: *in this paper* twice\n- l. 323: improve on previous\n\nOverall, I think the present contribution is below the NeurIPS acceptance bar: better motivation/intuition/interpretation of the results seem needed, as well as a more in depth study of the algorithmic and empirical aspects.\n\n**Post-rebuttal edit**\n\nI thank the authors for their response, which addressed most of my concerns. Incorporating these comments into the submission (to the extent it is possible with the page limit) would be helpful I think. I won't oppose acceptance and have increased my score to 6 accordingly.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "ULKG90igl3", "reviewer": "Reviewer_MGcL", "summary": "The paper proposes a new sparse multi-kernel SVM which utilizes a mixed L-2 norm to enforce the sparsity and a RKHS-norm to enforce smoothness, and theoretically analyzes the estimation bound and excess risk. Finally, the numerical experiments are also performed in this paper.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Although the paper show that the proposed new formulation of the sparse MKL SVM enjoys better learning rate, it seems difficult to optimize due to the $\\sqrt{}$ operator in regularization. Thus, to achieve the same generalization performance, few examples are needed, but maybe more computation time will be spent on optimization. On the whole, the new formulation does not bring too many benefits.\n\nThe experiments are performed on synthetic data, it seems better to show more results on real world data.\n\n======================\n\nSince the response has addressed my main concerns, I raise my score to 7.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No efficient optimization method will hinder the usage in practice.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "48"}, "extra_text": {}}, {"review_id": "Bx2mnOdcAW", "reviewer": "Reviewer_xwyd", "summary": "The paper consists of a theoretical analysis for bounds on the excess risk and estimation of SVMs in a sparse MKL setting.\nAlthough 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.\nIt 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.\nAfter 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.\nThe experimental results seem to closely verify the theoretical findings.", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "First of all, I want to acknowledge that I am not an expert reviewer for this submission.\nDespite having contributed on MKL and in learning theory a long time ago, I have been mostly unaware of any development in the last decade or so.\nSpecifically, despite some efforts, I am not very confident about my ability to check the corectness of the proofs (although I could not spot any mistake).\nPerhaps more importantly, I find myself to be struggling to carefully interpret or comment on the assumptions that are made to derive the analysis, despite efforts from the authors to relate them to assumptions that are made in related work.\n\nI find the paper to be remarkably well-written (despite a few typos and mistakes I'll list later), and relatively easy to follow despite the technicality of the contributions.\nEspecially, the efforts made to write the proofs should be noted, especially as the proofs are \"only\" provided in the appendix.\nI only have a few remarks or questions:\n1) It is not clear to me how much the improvements over the existing results are specifically due to the choice of this peculiar penalty term. For instance, it would be nice to see whether the use of penalty terms that have been more classically used in the literature lead to slower convergence in the experimental setting used here.\n2) Although it is mentioned that the chosen penalty term can \"easily lead to a single adaptive group Lasso by the Cholesky decomposition\", there is not any other comment about the algorithm, or computational complexity of solving problem (5). Can the authors comment? Or does it compare to formulations more commonly used?\n3) Related to those last points, even if using that penalty term really improves the excess risk convergence in practive (beyond making this tighter analysis possible), can the authors comment on whether there is an interest for practioners to adopt (5)? More specifically, do you have any insight whether the (perhaps) faster empirical rate \"compensate\" for the higher computational cost induced by solving (5) rather than more computationally amenable formulations?\n\nHere are some typos / mistakes I noticed in the paper:\n- l.6: \"and\" was used twice\n- l.174 \"there existS\"\n- l.246 \"multi-kernel cLAss\", \"From *a* model selection POV\"\n- l.254 \"in this paper\" was used twice\n- l.259 \"the popularity of sparse MK classification *is* mainly due\"\n- l.308 \"from randomly choosING\"\n- l.323 \"significantly improvE\"\n\nLast, I think recalling the theorems / propositions before exposing their proofs in the appendix would improve even further the ease of the reader.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Despite some comparison to related work, the limitations of this work have not been very deeply addressed. Addressing some of the remarkes I wrote in my main review would maybe improve that a bit.\nThere was no mention of potential negative societal impact but I am not sure that contribution in statistical learning theory have so much.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers have praised the quality of the paper (both substance and form) and acknowledged their appreciation of the responses made by the authors to their comments. This is a clear accept, with an expectation from the authors to do their best to incorporate as much as the insightful comments they provided in the feedback into the main text.


Decision: Accept (Spotlight)