Sparse Multiple Kernel Learning: Alternating Best Response and Semidefinite Relaxations
Authors: Dimitris Bertsimas
Caio de Próspero Iglesias
Nicholas A. G. Johnson
Venue: Accepted by TMLR ()

Abstract: We study Sparse Multiple Kernel Learning (SMKL), which is the problem of selecting a sparse convex combination of prespecified kernels for support vector binary classification. Unlike prevailing $\ell_1$‐regularized approaches that approximate a sparsifying penalty, we formulate the problem by imposing an explicit cardinality constraint on the kernel weights and add an $\ell_2$ penalty for robustness. We solve the resulting non-convex minimax problem via an alternating best response algorithm with two subproblems: the $\alpha$‐subproblem is a standard kernel SVM dual solved via LIBSVM, while the $\beta$‐subproblem admits an efficient solution via the Greedy Selector and Simplex Projector algorithm. We reformulate SMKL as a mixed integer semidefinite optimization problem and derive a hierarchy of semidefinite convex relaxations which can be used to certify near-optimality of the solutions returned by our best response algorithm and also to warm start it. On ten UCI benchmarks, our method with random initialization outperforms state-of-the-art MKL approaches in out of sample prediction accuracy on average by $3.34$ percentage points (relative to the best performing benchmark) while selecting a small number of candidate kernels in comparable runtime. With warm starting, our method outperforms the best performing benchmark's out of sample prediction accuracy on average by $4.05$ percentage points. Our convex relaxations provide a certificate that in several cases, the solution returned by our best response algorithm is the globally optimal solution.

Published in Transactions on Machine Learning Research (11/2025)
Sparse Multiple Kernel Learning: Alternating Best Response and Semidefinite Relaxations
Dimitris Bertsimas
dbertsim@@mit.com edu
Massachusetts Institute of Technology Cambridge, MA 02139, USA
Caio de Próspero Iglesias
caiopigl@mit..c edu
Massachusells Institute of Technology
Cambridge, MA 02139, USA
Nicholas A. G. Johnson
nagj@mil edu
Massachusetts Institute of Technology Cambridge, MA 02139, USA
Reviewed on OpenReview: https: operrevie.. net/ net/forum forum? Y5dcuFukgh
Abstract
We study Sparse Multiple Kernel Learning (SMKL), which the problem of selecting a sporse convex combination of prespecified kernels for support vector binary classification. Unlike prevailing l--regularized approaches that approximate sparsifying penalty, for- mulate the problem by imposing explicit cardinality constraint on the kernel weights and add &a penalty for robustness. We solve the resulting non-convex minimax problem via an alternating best response algorithm with two subproblems: the a-subproblem is standard kernel SVM dual solved via LIBSVM, while the 3-subproblem admits an efficient solution via the Greedy Selector and Simplex Projector algorithm. We reformulate SMKL as a mixed integer semidefinite optimization problem and derive hierarchy semidefinite convex relaxations which can be used to certify near-optimality of the solutions returned by best response algorithm and also to warm start it. On ten UCI benchmarks, our method with random initialization outperforms state-of-the-art MKL approaches in out- of-sample prediction accuracy on average by 3.34 percentage points (relative to the best performing benchmark) while selecting a small number of candidate kernels in comparable runtime. With warm starting, our method outperforms the best performing benchmark's out-of-sample prediction accuracy on average by 4.05 percentage points. Our convex relax- ations provide a certificate that in several cases, the solution returned by our best response algorithm is the globally optimal solution.
1
Introduction
Given a dataset {(x,, Hi where x; E I are m-dimensional leat ures and yı E {-1,1} are binary labels, the Kernel Support Vector Machine problem (KSVM) seeks to select a possibly nufnite-dimensionall feature map T Rm - Rd and learn lincar classification rule ÿ = sgn(w" ((x) + b) that generalizes well to unseen data. For a fixed feature map 4, the learning problem can be written in primal form as:
min EERRRR.EE WEB MER" DER
Mi
s.t. miww ((x;) +b) 1- Vi,
1=1
where C R4 a hyperparameter that is to be cross-validated by minimizing a validation metric (sec, e.g., Owen & Perry, 2009) to obtain strong out-of-sample performance in theory and practice (Bousquet &

---

Published in Transactions on Machine Learning Research (11/2025)
Elissceff, 2002). The first term in the objective function of equation 1 encourages minimal norm solutions as regularity condition that reduces overfitting while the second term in the objective function penalizes misclassified examples in the training dataset.
The KSVM learning problem given by equation emits a dual formulation that is often the preferred formulation to consider as it avoids requiring explicit construction of the feature map & (which may be prohibitive for large dimensional feature maps or simply impossible in the case of infinite dimensional feature maps). Specifically, the dual form of KSVM is given by
max
a (a-g(voa)KKyoca s.t. Σ a,y -0 C a; 2 0 Ai,
(2)
DER
1=1
where K the kernel matrix corresponding the feature map & (meaning that Kij 2 (x))"((())))
In vanilla KSVM, the choice of kernel matrix is typically selected via crossvvalidtton.. This however is inefficient and significantly limits the number of kernels that are considered. Moreover, it can be natural to use different kernels for different features. This might occur, for instance, if each data point consists of both text-based and visual features. Multiple kernel learning (MKL) addresses this limitation by considering a prespecified collection of q candidate kernels {K.)== and searching over the space convex combinations of said kernels (note that some treatments of MKL consider general conic combinations of candidate kernels rather than only convex combinations). Explicitly, MKL is formulated as:
4 Σ
min max BER acRt
Σ ai 2 (y00)²
K; (yoa)
(3)
s.t.
0:li = 0, C2 0z 20 Vi, |1 = 11
Since any symmetric positive semidefinite matrix is valid kernel (meaning that it corresponds to some possibly infinite dimensional feature map), the matrix K(B) = Σi= 8,K, is a valid kernel matrix for any g E TR.. In words, equation 3 socks to find the kernel in the convex hull of the q kernels { {K,) that results in the lowest training objective value when used to fit KSVM. The inclusion of the constraint ||,31] = in equation 3 typically motivated as inducing sparsity in 8 as a convex surrogate the lo norm function. In this work, we take the approach of directly imposing cardinality constraint on and demonstrate that this yields tractable formulation that produces superior solutions to MKL. Explicitly, given target sparsity level ho E N, we consider:
min max BERY aeR
ai 2
(yoa)
Σ 3,K,
(y o a) + 1
1=1
(4)
Σ a.y 0, C2 82a20 Vi, | = 1, 1| $ ko-
s.t.
where addition to the cardinality constraint on 9 we have introduced an & regularization term in the objective function encourage robustness.
1.1 Contribution and Structure
In this paper, we present an alternating best response algorithm that efficiently produces solutions to equa- tion 4 which outperform state-of-the-ar benchmark methods. We exactly reformulate equation as a mixed integer semidefinite program which emits a natural hierarchy of semidefinite convex relaxations that pro- duce lower bounds on the optimal objective value of equation 4. We employ these lower bounds to produce certificates of near optimality of the feasible solutions returned by our alternating best response algorithm and additionally warm starts for our algorithmic approach. We present rigorous numerical results across
2

---

Published in Transactions on Machine Learning Research (11/2025)
UCI benchmark datasets. On average, approach outperforms the best performing benchmark method in out-of-sample prediction accuracy by 3.34 percentage points while selecting a small number of candidate kernels in comparable runtime when using random initialization. With warm starting, our approach out- performs the best performing benchmark's out-of-sample prodiction accuracy by 4.05 pereentage points on average. In many cases, the lower bounds produced by our semidefinite relaxations certify that the solution returned by our alternating best response heuristic the globally optimal solution to equation
The rest of the paper is laid out as follows. In Section 2, we review previous work that is closely related to SMKL. In Section 3, we study the two subproblems that emerge naturally from equation 4 and we present our alternating best response algorithm. We reformulate equation 4 as a mixed integer semidefinite optimization problem in Section 4 and present a family of convex relaxations. Finally, in Section 5 we investigate the performance of our algorithm against benchmark methods on real world UCI datasets.
Notation: We let nonbold face characters such as denote scalars, lowercase bold faced characters such as x denote vectors, uppercase bold faced characters such as X denote matrices, and calligraphic uppercase characters such as E denote sets. We let [n] denote the set of running indices {1, (1.-..,)) n.. We let O, denote n-dimensional vector of all O's, Oxxm denote an n X m-dimensional matrix of all O's, and I, denote the x identily matrix. We let 8 denote the cone of n symmetric matrices and S denote the cone of n X n positive semidefinite matrices.
2 Literature Review
In this section, we present a non-exhaustive literature review to highlight key ideas from the MKL literature that we build upon with a particular focus on open source methods that are used as benchmarks in this work. As an exhaustive review of the literature outside the scope of this paper, we refer the interested reader to Gönen & Alpaydm (2011). In Appendix A, we review commonly used kernel families that we leverage this work.
2.1 MKL Foundations
Multiple Kernel Learning emerged in the early 2000s as framework to learn an optimal combination of prespecified base kernels rather than relying on a single, preselected kernel. Lanckriet al. (2004) first formulated MKL as semidefinite optimization problem that learned nonnegative kernel weights alongside SVM classifier. The authors demonstrated that combining kernels from heterogeneous data sources can significantly improve accuracy over the best single kernel. As off the shelf interior point methods suffer from scalability challenges for semidefinite programming, several subsequent efforts sought to improve the scalability of MKL by leveraging alternate formulations and algorithmic methods. To this end, Bach et al. (2004) reformulated MKL as a quadratically constr quadratic program and designed a sequential minimization based solution method. In order solve MKL problems with large datasets, Sonnenburg et al. (2006) developed column generation algorithm to solve semi-infinite lincar programming reformulation of MKL and Rakotomamonjy et al. (2008) developed the widely used SimpleMKL solver which leverages an efficient gradient descent based algorithm.
Recognizing that the number of base kernels to consider may often be considerably large, several authors sought to develop techniques that produced a sparse kernel meaning that the selected kernel was formed using only a small subset of the input base kernels. As directly imposing a cardinality constraint on the kernel combination vector ( produces an NP hard problem, many approaches leverage the é norm function convex surrogate for the to norm function analogous to the approach taken by Lasso to solve sparse regression (Tibshirani, 1996). To this end, Bach (2008) proposed an MKL formulation that sought to enforce group-level sparsity through the inclusion of weighted f--nrrm regularizer in the SVM dual, which was shown to have desirable consistency properties. Several other convex approximations have been employed in the literature. For example, Koltchinskii & Yuan (2010) attempts to induce sparsity through a combination of an empirical l norm and the reproducing kernel Hilbert space norms induced by the base kernels. In an alternate direction, Kloft et al. (2011) explore lp norm constraints (for p 2 1) and theoretically explore their influence on sparsity.
3

---

Published in Transactions on Machine Learning Research (11/2025)
Beyond lp surrogates, some authors have explored non-convex penalties that more closely approximate the to norm. For example, Subrahmanya & Shin (2010) propose a log-penalised MKL formulation that attains competitive accuracy on cancer-detection and hyperspeecral-imaage benchmarks while selecting markedly fewer kernels than other multiple kernel mothods. Nevertheless, the sparsity in their approach is still inducod through a smooth relaxation rather than an explicit. cardinality constraint.
Despite their empirical success, smooth or convex surrogates of to do not guarantee truly sparse solutions. Lasso-type penalties, for instance, produce robust estimators but not sparse estimators and be out- performed by methods that exactly enforce sparsity (Bertsimas & Copenhaver, 2018). This insight has motivated recent line of work that revisits direct cardinality constraints in MKL. Xue & Song (2019) pro- pose a non-convex formulation of sparse MKL which they solve using techniques from difference--f-conves programming. However, their approach considers using various smooth approximations to the &y norm (ex- ponential, logarithmic, capped & and SCAD). In this work, we consider an explicit to norm constraint which we enforce directly without approximation.
2.2 Open Source MKL Benchmarks
this work, we benchmark our methods against three well studied and widely used MKL algorithuss that are implemented in the open-source MKLpy library (Lauriola Aiolli, 2020): Average EasyMKT. (Aiolli & Donini, 2015), and CKA (Cortes et al., 2012). We briefly outline each of these approaches below.
AverageMKL This baseline sets all kernel weights uniformly B; for all i. This produces the following combined kernel:
K(B) Σ K.
Although AverageMKL trivially determines kernel weights, this method is surprisingly competitive when most kernels are informative (Lewis et al., 2006). Its parameter-free design and limited training cost make it a useful sanily check and benchmark for evaluating the performance of more sophisticated MKL methods.
EasyMKL This method is a scalable MKL algorithm that learns a combined kernel without alternating between SVM training and kernel weight. updates. Explicitly, Fasy seeks a combined kernel K K(3) EL 3,K, where 2 0 and || =. This is achieved by introducing a distribution vector Y over the training examples (separately normalized on positive and negative classes), and letting Y diag(y). Here, I denotes the set of possible distributions. Define d(y) E R2 by letting d,(>) =y YKKY%, the (squared) margin of K; under weighting 7. EasyMKI. casts MKL as the saddle-point problem
min max - A)B () d(y) + A
(5)
geT 1812=1
where À E [0 trades off margin maximization against variance regularization. For fixed y, the inner maximization admits the closed-form solution 8r T
d(r) which reduces equation 5 to
min Yer (1 A) lld()))2 + A 111
(6)
The authors then replace [d(())]22 in equation 6 with [[d())],,, which produces tractable optimization problem and empirically is sparsity inducing.
CKA (Centered Kernel Alignment) This approach selects kernel weights by directly maximizing the alignment between a convex combination of base kernels and the target label kernel. Let Ko = yy" and denote by KF = C. C the centered version of kernel K₁ where = 111". Let a =
(KK), K Kc Kg)) and let Mi = (K;, KG). Then CKA solves the generalized Rayleigh quo- tient.
a))
max #20, =1 BT M 3
4

---

Published in Transactions on Machine Learning Research (11/2025)
whose solution admits the closed-form 8 MM MM While CKA typically produces dense weight vectors, its efficiency and strong empirical performance make it a valuable baseline for MKL.
In summary, AverageMKL serves as simple and effective baseline, EasyMKL provides a sparsity inducing and scalable convex method grounded in margin maximization, and CKA offers a fast alignment- solution. The strong empirical performance and reproducibility of these methods make them well-suited as benchmark methods for evaluating sparse MKL algorithms.
3 An Alternating Best Response Algorithm
In this section, we present an alternating best response algorithu that produces solutions for equation 4. The presence of the lo constraint on makes the problem non-convex and therefore not amenable to commonly used gradient descent ascent style algorithms for minimax optimization. Nevertheless, we show in Sections 3.1 and 3.2 that both the maximization over for a fixed value of B (which we refer to the a-subproblem) and the minimization over & for fixed value of a (which we refer to as the 3-subproblem) can be solved efficiently. In Section 3.4 we explore theoretical convergence and computational complexity properties of our algorithm.
3.1 The a-Subproblem
For a fixed value 3 E R4, define the combined kernel ((3) as ((B) = Σラ 8g Kj. Then, the a-subproblem is given by:
1 2 (yoa) K(B) (yoa)
max &E[O,
Σ
(7)
E 900:=0
This formulation is equivalent the standard Kernel SVM dual problem, with the only difference being that the kernel mairix is given by K(9). As a convex quadratic program, equation 7 can be solved global optimality using any one of several well-established solvers. In the implementation of our approach, leverage the LIBSVM solver (Chang & Lin, 2011) which employs the Sequential Minimal Optimization (SMO) algorithm. SMO decomposes the large-scale quadratic program inlo series of analytically solvable two-dimensional subproblems. This coordinate descent strategy is both efficient and robust in practice.
3.2 The B-Subproblem
For fixed value of RD that is feasible to equation the B-subproblem is given by
min BeR
(10
2
Σ 3 Ki (yoc) + 1lalle s.t. || 1, 1 S ko.
(8)
We define d, = (yoa) T K, (y for every i E [g]. Given this, we can express the objective function of equation 8 as:
((3)
Σ
Bid, 2or
For any given Bi, completing the square shows that we have
3,d, + A3 = x (B.
di
df
2
41
16A
Observe that if equation 8 were unconstrained, the optimal solution 8 would be given by 33. 3 Let
d and define the sets Σx, {B E R9: ||B]|u < ko) and A =(8 E. E By 1}. It follows w 4x that equation 8 has the same optimal solution as:
5

---

Published in Transactions on Machine Learning Research (11/2025)
min || wl..
(9)
In words, solving equation gives the Euclidean projection of the vector w onto the intersection of the sets Ego and A+. We obtain the solution equation by employing the Greedy Selector and Simplex Projector (GSSP) algorithm (Kyrillidis et al., 2013).
GSSP procoeds in three steps:
1. Top-k truncation PL.. Let S (1....,,q) o) index the & largest entries of w. Define
(PLx(w)); = ws i S This retains only the top & components of w.
0, i i S.
2. Simplex projection P+. Restrict to the active entries (wilies, sort them into descending order w(1) 2 ((2) w(k); and compute
wG)) 1), p= -max joaxj:ump
((m)) 1)}
Then form
(w)() max T, 0) for E S.
and set (P+(w)); for $ S. This enforces nonnegativity and the unit & norm constraint.
3. Reconstruction. The final projected vector is
(Pt (w));, i= 1,....,
which has support S and sums to 1.
By Theorem of Kyrillidis et al. (2013), these steps yield the exact minimizer of equation 9 in quasilinear time.
3.3 Alternating Best Response
We now describe complete alternating best response procedure used to obtain solutions to the sparse multiple kernel learning problem given by equation 4. Our approach itcratively alternates between optimizing the SVM dual variables a and the kernel weights B. We will see in Section 5 that this heuristic performs well in practice by providing both strong predictive accuracy and kernel interpretability.
Each iteration of Algorithm 1 consists of two steps. First, we fix (tt-1) and solve the standard SVM dual problem using the kernel matrix (()((t1)) = E - Ky. This subproblem is convex and can be solved to global optimality using either SMO-based solvers (c.g., LIBSVM), or quadratic programming solvers (e.g., Gurobi). This produces an updated vector of dual coeflicients (*). Next, we update the kernel weights by solving equation 9.
(!) and
Initialization Strategies. Before the first iteration, initialize the kernel weights ((0) using of the following strategies:
ho-Spurse Random Inilialization: A subset. S C {1.....h) 9) with |S] = ko is drawn uniformly at random. We set 5 = 1/kk for j E and 5 for j $ S.
Warm Stort: A feasible vector g(0) produced by solving a separate optimization problem (typically convex lower bound) is used.

---

Published in Transactions on Machine Learning Research (11/2025)
Objective Tracking. At each iteration, we compute the value of the dual objective associated with the current kernel weights and dual variables. Let j(t denote the value of the regularized SVM dual objective at iteration i, given by
a J
a / (yoal!0) K(0) (yoalo) 111
where K(O = E 8 K2 is the kernel matrix induced by the iteration t weights Bi0, and the final term corresponds to the le regularization penalty on the kernel weights. This quantity is used monitor convergence and trigger early termination when progress stalls.
Stopping Criteria. The algorithm terminates when either (i) a maximum number of iterations T is reached, or (ii) the absolute improvement in the dual objective falls below tolerance for M consecutive iterations.
Algorithm 1: Alternating Best. Response for Sparse MKL,
Data: (1r y)) (K,))=1> C, X, ko, e, M, T
Result: a, B
Init: choose 300); non decrease t- 0, obj_ obj_best t- 0o
for / ......,T do
// max iterations
(1) Σ, 3 Kj
(11) +- arg max SVM dual on K())
for j = I,....q do
d, - (y ( ky (1))
" + d2/(4A)
3(0) + GSSP(((;) ko)
Compute objective (()
if obj_ best (0] e then
non decrease non ceennoondeeeee decrease
else
non Lon_decrease-e t obj_best best -- (t)
Save ((())
if non_ decrease 2 M then L break
// early stopping
3.4 Algorithm Properties
In this subsection, we briefly explore convergence and complexity properties of Algorithm We defer the proofs of Proposition 1, Proposition 2 and Theorem to Appendix B.
Proposition 1 Let {a,, Be denote the sequence of iterates produced by Algorithm when we ignore the algorithm's 's stopping criteria. There exist accumalation points for this sequence.
Proposition 2 Let {ai, 31 denote the sequence of iterates produced by Algorithm when ignore the 9*)) algorithm's 's slopping crileria. Suppose the sequence converges. Lel ,x",,"') denole the limúl of the sequence. mutual best response pair.
Then (*) is
It can be seen immediately that Algorithm terminates given any input. It interesting to consider the asymptotic behavior of the iterates produced by Algorithm in the absence of stopping criteria. Taken
7

---

Published in Transactions on Machine Learning Research (11/2025)
together, Propositions 1 and establish that it is not possible for the iterates of Algorithm 1 to converge to point that is not mutual best response. If the iterates produced by Algorithm 1 converge, they must converge to a point (a*,8*) such that a solves equation 7 when B = B and 3 solves equation 8 when a =
Propositions and alone do not guarantee convergence for all input. Indeed, it is possible to construct instances where the iterates cycle. It is of interest to understand which conditions guarantee convergence of Algorithm 1. We present one such sufficient condition in Theorem 3. Specifically, Theorem 3 establishes linear convergence to the unique mutual best response pair if the support of the iterates Bt stabilizes and the problem hyperparameters satisfies an incquality.
Theorem Let [au,31)i= denote the sequence of iterates produced by Algorithm when we ignore the algorithm's 's stopping crileria. Suppose there erists an inder To and support set S C [g], [S| I ko such that for allt 2 To have supp(B.) S. Suppose further that all kernels are positive definite. Let (KK), Xn (Ki) denote the largest and smallest eigenvalues of K, respectively. Suppose the following condition holds:
C² C' |max A (Kx)] < 2Amin (k(K))
Then the sequence [,,,,1),22 converges linearly to the unique mutual best response (a*,8*) with rate C" (max, (K)
2Aminy (k))
We conclude this subsection by considering the computational complexity of Algorithm 1. At a given iteration, forming the kernel ((3) requires Okkn²) operations (recall that the individual kernels K; are precomputed). We employ an iterative method to solve the dual SVM problem in O(n!) operations where I denotes the number of iterations required and is empirically known to be higher than linear but less than quadratic in the number of training examples n (Chang & Lin, 2011). Forming the vector d requires Ogn²²) operations and the GSSP algorithm has complexity O(q log q) being dominated by the cost to sort a g-dimensional vector. Thus, the overall complexity of Algorithm 1 is O(T [gm² + glog + n/]).
4 An Exact Reformulation and Convex Relaxations
In this section, we reformulate equation 4 exactly as a mixed integer semidefinite optimization problem and derive several convex relaxations that will be used in Section 5 to both produce lower bounds for solutions returned by Algorithm and to warm start it.
4.1 A Mixed Integer Semidefinite Reformulation
We begin by exactly reformulating equation 4 as a mixed integer semidefinite optimization problem. Consider the alpha subproblem given by equation 7. Its dual is given by:
13
1
9
min FRR YERK
oi
22"
K 7
s.t.
- S (n + 7%)
Vi [m].
(10)
K. 7
I, B.K
For the interested reader, we present a derivation of equation 10 starting from equation 7 in Appendix C. Since equation 10 contains only affine constraints, Slater's condition trivially satisfied implying that strong duality holds between equation 7 and equation 10. Notice that equation 10 is convex quadratic optimization problem since for any B that feasible in equation 4, the matrix [Σ B,K,] will be positive semidefinite. We sock to leverage equation 10 to replace the inner maximization problem in equation 4 which would yield single minimization problem.
8

---

Published in Transactions on Machine Learning Research (11/2025)
Directly substituting the inner maximization of equation 4 with equation 10 is not desirable since would be optimization variable that appears within matrix pseudo inverse terms and is multiplied by 7, another optimization variable, in the objective function and in the last constraint. Consequently, we proceed by introducing semidefinite constraint that allows equation 10 to be reformulated as a semidefinite optimization problem without products between 7 and & or matrix pseudo inverse terms. Consider the optimization problem given by:
1 2
min n. yER
C Σ oi 0
i=1
s.t.
1 - S vi(n + 72) Vie [m].
(11)
(
7"
8:KK) =0.
It follows from the Generalized Schur Complement Lemma (see Boyd et al. (1994), Equation 2.41) that equation 10 and equation 11 achieve the same optimal objective value. We state this equivalence formally in Proposition 4 (proof deferred to Appendix D).
Proposition 4 Equation 11 is a valid reformulation of equation 10.
We can now obtain a more tractable reformulation of equation 4 by substituting its inner maximization problem with the equivalent minimization equation 11. Consider the optimization problem given by:
min RER
C
Σ
0, 2 1lll1k
YER" ,BER
s.t.
1 1- 0. S 8:(1 +()
Vi [n].
(12)
0
y
=
Y
E -i=1 B K,
3 = 1, ||1110 S ko-
equation 12 consists of a non-convex minimization problem where the nonconvexity is entirely captured by the cardinality constraint ||,8]oo < ko- We further reformulate equation 12 by introducing binary variables (0, 1 and imposing the nonlinear constraint 9 2 to model the sparsity pattern of B. Explicitly, we characterize the set of g-dimensional vectors with cardinality at most ko using the following equivalence:
( E TR? |181| < ko) = (A E RR: 32 E 10.1)% Σ
< ko. Bi 2.
As and B will both be optimization variables in our relaxation, the constraints B: = 2, are complicating as they are non-convex the decision variables. Accordingly, we invoke the perspective reformulation (Günlük & Linderoth, 2012) to model these constraints in convex manner. Specifically, we introduce a variable w R" where W; models & and we introduce constraints w;2; 2 33 which are second-order cone representable. This results in the following exact reformulation of equation 4 and equation 12:
9

---

Published in Transactions on Machine Learning Research (11/2025)
min RR yeR", Re
+
0 + A
Wis
2
1=1
s.t.
1
oj
S Vi + 74)
Vie [n],
(13)
0
7²
|
[.KK] 0.
7
4
Σ B,
= 1,
Σ 4 S Ko:
B s,w,
2,
AA E [g].
4.2 Positive Semidefinite Cone Relaxations
Equation 13 is an exact mixed integer semidefinite optimization reformulation of equation where the problem's non-convexity is entirely captured through the binary condition (0,1). We now obtain semidefinite relaxation by solving equation 13 with E conv({O, [0, 1j. This yields the following convex optimization problem, which we refer to as the Full SDP relaxation:
min PER yER" B,wER (0
Σ 1=1
oi + 00
0 +
Σ
Wi.
s.t.
1 oi
y1 74)
ViE [n],
(14)
0
7T
EE (.K,) 00,
7
q
Σ 8, 1,
ko,
B B zwws
Vi E [g]-
Theorem Equation 14 valid convez relazation of equation 4.
We defer the proof of Theorem 5 to Appendix D.
In Section 5, we use equation 14 to produce lower bounds for feasible solutions returned by Algorithm Note that Algorithm and equation 14 can be leveraged to design a custom branch and bound algorithm the sense of Little (1966); Land & Doig (2010) to solve equation to global optimality, Such an approach would involve constructing the enumeration tree would be defined by two disjoint collections of indices Io, I1 S [q] where I, denotes indices of constrained to take value i. At a given node, feasible solutions and lower bounds would be computed using slightly modified versions of Algorithm and equation 14 respectively.
enumeration tree that branches the entries of the vector Each node in
As a brief aside, we note that in the special case where all of the input kernels {Ka)== are simultaneously diagonalizable, equation 14 can be reducod a sccond order cone problem. Explicitly, consider the following optimization problem:
Σ
0 + A Σ
min o. B.eeR[=s[(0.1)
o
+
Wi. 1=1
1=1
s.t.
oi
S vn(n + 77)
Vi E [n].
9
(15)
B,DD)bb 2 ( u2
Vj [n].
g T3z Σ
0 > Σ
3, =
Σ
2 S ko,
zws
Vie [g],
1=1
10

---

Published in Transactions on Machine Learning Research (11/2025)
where = =DD for all E [q] are spectral decompositions of the candidate kernels which are assumed to be simultaneously diagonalizable. Note that uj E RR" denotes the jth column of U E RRax. We now have the following result (proof deferred to Appendix D):
Theorem the candidate kernels { (K:)== are simullaaneussy diogonalizable, meaning that we have K; U for all i [q] where D2 E R are diagonal matrices and U R=nx satisfies UUT U In. then equation 14 is equivalent to equation 15.
We stress that the assumption in Theorem 6 of simultancously diagonalizable kernels is strong assumption that in general will not hold in practice.
4.2.1 Sparse Positive Semidefinite Cone Approximations
We will see in Section 5 that equation 14 empirically produces strong lower bounds. However, solving equation becomes computationally difficult as the number of training examples n grows because even the most efficient interior point solvers for semidefinite optimization problems exhibit poor scaling with the size of the positive semidefinite constraint which in the case of equation 14 has dimension (n 1) (n + 1). In order to produce lower bounds efficiently for large problem instances, we are interested in developing approximations to equation 14 that can be computed more efficiently as the problem dimension scales.
To this end, we leverage a common approximation approach that involves relaxing the global positive semidef- inite constraint and instead, for a given value & N, constraining all ( l principal submatrices to be positive semidefinite. This technique often called the sparse SDP relaxation and known to have desirable ap- proximation properties in both theory and practice (Blekherman et al., 2022; Song & Parrilo, 2023). Recall that S denotes the set of all n x n real symmetric positive semidefinite matrices and let Sq denote the set of all n real symmetric matrices where all l x principal submatrices are positive semidefinite. It is clear that for any & E N, we have S S S/41 S Sy.
In general, for a matrix X E R(n+1)x(++1), substituting the constraint X s by X E Sp would involve replacing a (n + 1)) x (n + semidefinite constraint with (a+)) e semidefinite constraints. However, recall that the n sub block Σx= B,K, of the (n+1) (n 1) matrix involved in the semidefinite constraint of equation 14 is itself guaranteed to be positive semidefinite for any feasible B. Accordingly, any principal submatrix that is entirely contained within this sub block is guaranteed to be positive semidefinite which implies we need only concern ourselves with principal submatrices that involve the first row and column when
@ (
7"
1EL1,,K requires only ((=1) l x é semidefinite constraints rather than (*+ l x E many. This equates to using ((m) ( 1) fewer constraints.
defining our approximation. Thus, letting X
imposing the constraint X E Sp
As report results for f 2 and f = 3 in Section 5, we explicitly state the corresponding relaxations below. For f 2, the approximation to equation 14 is given by:
n
min "ER YER" A.ERR 1=] s.t.
oi +
0 + A
Σ wis
1 1- o, S vn + 71)
Vie [n].
(16)
0
Vj E [n], 3: [Kili 2 2
i=1
Σ 1=1
8, = 1,
S Ko
B7 8 2::;
Vi E [g].
Equation 16 a second order cone relaxation of equation 14. In Soction 5, we refer to this relaxation as Second Order Cone Relaration with basis vectors. Moreover, we can strengthen this second order cone relaxation by randomly sampling unit vectors E R and imposing the additional second order cone representable
11

---

Published in Transactions on Machine Learning Research (11/2025)
K, 2 (x for each sampled unit vector To see why these constraints are valid for equation 14, notice that by the schur complement lemma the semidefiitt constraint in equation 14 implies that the matrix Ein1 B, 2 must also be positive semidefinite. This condition can equivalently be expressed as A
constraints given by 8
Ei K,K, Σ my" Thus, for any vector a (whether a unit vector or not); we have 0. Ei=1 (x K 2 (a 7)2. Notice that if we generale these constraints letting æ be the standard basis vectors, we obtain the second order cone constraints in equation 16. Explicitly, let denote collection of randomly sampled unit vectors. Consider the optimization problem given by:
min n. YER" B 1 8.1.
Σ ==1
+ - 2
0 + Σ
wi
1=1
oi S yi
+ 7:) Vie
(17)
0
Ba
T K2 2 (a 7)² to E C U (e
4 Σ B4 = 1,
Σ S ko, S Vi E [g]-
Equation 17 a second order cone relaxation of equation 14. In Section 5, we refer to this relaxation as Second Order Cone Relazation with randomized vectors. Moreover it should be clear that equation 17 is stronger relaxation than equation 16 since the feasible set of equation 17 is subset of that of equation 16. Moreover, equation 17 becomes an increasingly strong approximation to equation 14 as the cardinality of C increases. We will explore this further in Section 5. The final relaxation we introduce is the sparse SDP relaxation with f = 3 for equation 14 which is given by:
min ER YER" BWERY [0 s.t.
oi
0
Wir
2
i=1
1 1- S v1 76)
Vi [n],
0
Σ Σタ 7A
(18)
7
Σ -
3 Ki
20 vIsckknjjt
21 3, Ki)ks
2i 3: Kiluk
Σ
8
=
Σ 2 S ko,
8 S 2,
1=1
i=1
In Section 5, we refer to this relaxation with = 3 as 3x-- relaxation.
5 Computational Results
In this section, we evaluate the performance of Algorithm and the relaxations introduced in Section 4. We benchmark against open source methods implemented in MKLpy library (Lauriola & Aiolli, 2020) that we introduced in Sention 2.2. All experiments were run using Julia 1.10.1 and Python 3.10.14. Semidefinite programs were solved with MOSEK 10. 1.31, while all other optimization relied on Julia's LIBSVM v0.8.0 and MIT's Supercloud Cluster (Reuther et al., 2018), which hosts Intel Xeon Platinum 8260 processors. To bridge the gap between theory and practice, we have made our code freely available at https: //github//tuub..... http:///ggtuuub.momgle/essste wtt..///eeeeaaaa//////e/////// Sateaaaii//paasM.......
MKLpy 0.6. We perform experiments
We seek to answer four questions:
Q1 Predictive accuracy and runtime. How does Algorithm 1 compare to other widely used open-source MKL solvers- EasyMKL, AverageMKL, and CKA- liAAA-imleemented in MKLpy (Lauriola & Aiolli, 2020), in terms of prediction accuracy and computational efficiency?
12

---

Published in Transactions on Machine Learning Research (11/2025)
Q2 Warm starts. Does initializing Algorithm with solutions from our convex relaxations enhance the quality of the returned solution?
Q3 Optimality. How close is the objective value achieved by the output of Algorithm to the lower bounds produced by the SDP relaxalions of Section 4?
Q4 Sealability. How does Algorithm as the number kernels g increases?
We address Q1-Q4 in the following sections.
5.1
Experimental design
Data sets. We evaluate all methods on ten benchmark binary classification tasks drawn from the UCI Machine Learning Repository (Dua & Graff, 2017). Seven of BREASTCACCE (Wisconsin Diagnostic), IONOSPHERE, SPAMBASE, BANKNOTE, HABERMAN, MAMMOGRAPHIC, and PARKINSONS- are provided in their original binary form. The remaining three IRIS, WINE, and HEART (Cleveland)- are originally multiclass and were converted into binary tasks.
Each data set was parsed into numeric features, with any categorical variables one-hot encoded while omitting one dimension to avoid collinearity. To ensure reproducibility, we fixed the random seed, shuffled the rows, and split 80% of the examples into a training set and the remaining 20% into a test set. Numeric features were standardized to zero mean and unit variance using statistics computed solely on the training set; the same centering and scaling parameters were then applied to the test set. Table summarizes, for each task, the original number of examples, the train set size Per; the test set size nte and the proportion of positive labels.
Table 1: Summary of binary classification tasks used in our experiments. The table reports, for each dataset, the number of examples n, the training size Pir. the test size Ries and the proportion of positive labels.
Dataset
Thr
Tite
% Positive (+1)
IRIS
150
120
30
33.3%
WINE
178
142
36
33.1%
BREASTCANCER
569
455
114
37.3%
1ONOSPHERF
351
280
71
64.1%
SPAMBASE
4601
3680
921
39.4%
BANKNOTE
1372
1097
275
44.5%
HEART
303
242
61
45.9%
HABERMAN
306
244
62
73.5%
MAMMOGRAPHIC
961
768
193
46.3%
PARKINSONS
195
156
39
75.4%
Set of Base Kernels. All methods are evaluated on the same predefined set of ten base kernels. Our goal in assembling this collection was to include a diverse yet representative sample of the similarity mea- sures introduced Appendix A, so as to provide each model with flexibility across different feature space geometries.
Concretely, our set comprises linear kernel (to capture simple inner-produte structure), three polynomial kernels of degree d E (2,3, 5) with offset (RBF) kernels with parameters 7 E {0.5, 0.3, 0.1). We further include two sigmoid kernels, each with offset Co = and slopes 7 E (0.5, 0.7) and a single Laplacian kernel with 7 = 0.3.
1 and 0.01, and three Gaussian radial-basis-ffnction
Each kernel matrix precomputed once and then symmetrized the transformation K {(K + KT)
guard against numerical asymmetry and guarantee positive semidefinitenes.. Finally, we add 10 I every kernel matrix to improve conditioning and ensure stable solver performance.
13

---

Published in Transactions on Machine Learning Research (11/2025)
Hyperparameter tuning. For Algorithm 1, perform 10-fold cross-validation over the training set to select the regularization and sparsity parameters from the grid
C (5, 10, 100), X (0.01, 0.1, 10, 100), ko (,,,5.
The same folds are reused to tune EasyMKL's margin-variance trade-off parameter λaay over 25 values in [10-4, 1]. AverageMKI and CKA require no parameter tuning. Once the best hyperparameters are identified, each model is retrained the full training set and evaluated the withheld test set.
Performance metrics. Classification quality is measured by lest accuracy (Table 2); solution quality by the MKL objective value (Table 6); optimality by the percentage gap with respect to the tightest available lower bound (Table 7); and computational burden by the training time (Table 4).
5.2 Predictive Accuracy and Runtime Compared to Open-Source MKL Solvers (Q1)
We begin our computational evaluation by assessing the predictive performance and runtime of Algorithm in comparison to existing open-source MKL solvers.
Table 2 reports the test set accuracy achieved by EasyMKT, AverageMKT, CKA, and Algorithm with random initialization. We find that Algorithm 1 matches or outperforms the best open-source baseline on all tasks: strictly improves over the strongest competitor in eight cases and ties the remaining two. The largest. absolute gains occur on IONOSPHERE (+7.1 percentage points), HRART (+6.5 points), and PARKINSONS (+7.6 points), with additional consistent improvements observed on WINE (+2.8 points), BREASTCANCER (+3.6 points), IIABERMAN (+1.6 points), and MAMMOGRAPIIC (+3.77 points). On the perfectly separable tasks IRIS and BANKNOTE, Algorithm attains 100% test accuracy, matching the best-performing solvers. Averaged across datasets, Algorithm 1 outperforms the strongest baseline by 3.34 percentage points.
Dataset
Train Size
EasyMKL
AverageMKL
CKA
Algorithm 1
iris
120
100.0
100.0
96.7
100.0
wine
142
97.2
97.2
91.7
100.0
breastcancer
455
93.0
92.1
94.7
98.3
ionosphere
280
73.2
74.6
85.9
93.0
spambase
3680
90.4
87.6
81.0
90.9
banknote
1097
100.0
100.0
85.1
100.0
heart
242
85.2
85.2
86.9
93.4
haberman
244
61.3
62.9
66.1
67.7
mammographic
768
80.8
79.3
75.1
84.5
parkinsons
156
82.1
82.1
74.4
89.7
Table 2: Test accuracy (%) of EasyMKL, AverageMKL, CKA, and Algorithm with random initialization.
Crucially, these gains achieved while selecting sparse kernel combinations as illustrated by Table 3. In contrast, AverageMKL, uniformly assigns nonzero weight to all kernels, EasyMKL encourages sparsity to some exlent via regularization but does not allow explicit control over the sparsity level; and CKA typically yields dense combinations of all kernels. We stress that the randomly initialized variant of Algorithm achieves these improvements without solving any semidefinite programming relaxations and only modest number of alternating best response steps. Consequently, the runtime of Algorithm competitive with standard MKT solvers illustrated in Table 4.
14

---

Published in Transactions on Machine Learning Research (11/2025)
Datasct
EasyMKL
AverageMKK
CKA
Algorithm
iris
10
10
9
1
wine
4
10
7
breastcancer
3
10
7
ionosphere
10
6
spambase
10
10
7
banknote
10
10
7
1
heart
3
10
7
haberman
8
10
8
mammographic 7
10
7
1
parkinsons
2
10
7
Table 3: Number of non-zero coofficients (13,)
10-3) for cach algorithm on every dataset.
Dataset
Train Size
EasyMKL
AverageMKL
CKA
Algorithm
iris
120
0.030
0.002
0.026
0.022
wine
142
0.045
0.002
0.029
0.005
breastcancer
455
0.244
0.004
0.061
0.110
ionosphere
280
0.072
0.003
0.036
0.070
spambase
3680
33.671
0.631
8.859
8.330
banknote
1097
0.337
0.006
0.301
0.519
heart
242
0.062
0.003
0.035
0.188
haberman
244
0.029
1.907
0.033
0.025
mammographic
768
0.228
13.027
0.125
0.436
parkinsons
156
0.038
0.002
0.028
0.245
Table 4: Training time (seconds) of FasyMKT. AverageMKT, CKA, and Algorithm with random initial- ization. The fastest runtime in each row bolded.
It should come no surprise that AverageMKL has the fastest runtime in eight of the ten benchmarks since this method just takes a naive average of the input kernels. Among the three weight-learning algorithms, performance is more nuanced. CKA posts the shortest times on a majority datasets, yet its advantage over Algorithm seldom exceeds a few hundredths on SPAMBASE (3,680 data points) Algorithmi the fastest learner, running 6% faster than CKA and over four times faster than EasyMKL. Amgorithm also takes the lead on IRIS, WINE, and HABERMAN. Easy offers savings relative Algorithm is the slowest option on the largest problem.
second and disappears entirely on the largest workload:
some mid-sized tasks (c.g., PARKINSONS, MAMMOGRAPHIC), but it
These results highlight Algorithm I's favorable trade-off between predictive accuracy, model sparsity, and computational officiency in the case of random initialization. This variant of Algorithm 1 suffices to achiove state-of-the-art performance across a broad range of benchmarks, offering strong predictive accuracy, inter- pretable sparsity, and practical training times.
5.3 Effect of Warm Starts (Q2)
We next evaluate the practical benefits initializing Algorithm with solutions of SDP relaxations. We consider thrre variants:
Random: Employ the sp-sparse random initialization technique described in Section 3.3;
15

---

Published in Transactions on Machine Learning Research (11/2025)
3 x 3-SDP: Solve our sparse semidefinite relaxation for l = given by equation 18. Select the ko largest entries of as the support of 8 and scale B (restricted to these entries) to have unit. E norm;
Full SDP: Solve the dense semidefinite relaxation given by equation 14. Select the ko largest entries of z as the support of B and scale 3 (restricted to these entrics) to have unit & norm.
Table 5 reports test set accuracy for these variants. Warm starts occasionally yield improvements, but their effect is heterogeneous across datasets. In some cases, warm initialization produces significant gains: on PARKINSONS, the full-warm start improves accuracy from 89.7% to 94.9%, and on IONOSPHERE, the 3 start increases accuracy from 93.0% 94.4%.
Datasct
Train Size
Best Bascline
Algorithm 1 Variants
(max of benchmarks)
(random)
(warm 3x3)
(warm full)
iris
120
100.0
100.0
100.0
100.0
wine
142
97.2
100.0
100.0
100.0
breastcancer
455
94.7
98.3
97.4
ionosphere
280
85.9
93.0
94.4
90.1
spambase
3680
90.4
90.9
93.9
banknote
1097
100.0
100.0
100.0
heart
242
86.9
93.4
93.4
93.4
haberman
244
66.1
67.7
66.1
66.1
mammographic
768
80.8
84.5
84.5
parkinsons
156
82.1
89.7
89.7
94.9
Table 5: Best baseline accuracy (highest of EasyMKL, AverageMKL, CKA) versus Algorithm 1 variants. a_" indicates that results were unavailable due memory limits. Foor SPAMBASE, the 3x3 warm start uses the randomized SOC relaxation due to memory limits.
In other cases, however, the benefits marginal nonexistent: HABERMAN, for instance, the random start alrcady achieves 67.7% accuracy, and both warm starts slightly reduce performance to 66.1%. Overall, while warm starts sometimes improve the quality of the solution, they do not consistently dominate the random start variant across all benchmarks. Averaged across datasets, the best warm-started variant of Algorithm improves upon the strongest bascline by 4.05 percentage points, where for cach dataset the improvement is defined as the difference between the maximum result of the full SDP and 3x3 minor warm- starts and the best baseline. This exceeds the 3.34-point gain of the random-start variant.
It is important to note that for SPAMBASE, the 3x3-SDP warm entry in Table does not correspond to the true 3x3 3x3-SDP, but instead uses randomized second-order cone (SOC) relaxation given by equation 17. This substitution was necessary because both the full SDP and the 3x3 SDP exceeded available memory on this large dataset. Interestingly, even though the SOC relaxation provides an extremely loose lower bound far from the heuristic objective value (0.2 vs. over 700 as shown in Table Section 5.4)- [0)]-wam-sttrtin from the SOC solution still improves the test accuracy substantially, from 90.9% 93.9%. This highlights that even relatively weak relaxations can offer valuable guidance for initialization when solving largo-scale SMKL problems with Algorithm 1.
While warm starts can help improve predictive performance, they impose substantial computational burdens. Both relaxations become impractical for large problems because of the poor memory scalability exhibited by interior point methods when used to solve semidefinite programs. In contrast, the randomly initialized variant of Algorithm 1 requires only a modest number of alternating best response steps, scaling efficiently even for datascts with thousands of examples. Despite its simplicity, the random start variant achieves competitive or superior predictive performance across all benchnarks without relying on solving costly semidefinite programs.
16

---

Published in Transactions on Machine Learning Research (11/2025)
5.4 Optimality certification via SDP relaxations (Q3)
Using the semidefinite relaxations introduced in Section 4, we certify how close the solutions returned by Algorithm are to global optimum. We consider three levels of relaxation:
Second Order Cone (SOC): Solve our sparse semidefinite relaxation with é with standard basis and randomized vectors, given by equation 17;
3 x 3-SDP: Solve our sparse semidefinite relaxation for é 3, given by equation 18;
Full SDP: Solve the dense semidefinite relaxation give by equation 14.
Each of these yields a lower bound ftB on the true optimal MKL objective. Given any SMKL feasible solution (B, we compute its objective value F(B, à) and report the relative optimality gop
Gap(B. F(3,a) -LB F(B,0)
x 100%,
which is upper bound how far (B can be from global minimizer.
Table 6 presents, for each dataset, the lower bounds from the SOC (slandard basis and randomized), the x 3-SDP and the full SDP relaxations, alongside the objective achieved by Algorithm 1 under three initialization strategies: random start, the 3 3-SDP warm start, and the full SDP warm start. As expected, the SOC bounds are weakest, the 3 3-SDP bounds are substantially tighter, and the full SDP bounds are the strongest wherever they could be computed. Moreover, warm-start initializations consistently reduce the Algorithm 1 objective: for example, on IONOSPHERE the random start gives 169.77, whereas the 3 x 3 and full SDP starts lower it to 125.36 and 121.83, respectively. In small problems like WINE, where Algorithm 1 with random initialization is already nearly optimal (7.71 vs. a 7.70 full-SDP lower bound), these gains are marginal. On the largest datasets (SPAMBASE, MAMMOGRAPHIC) memory constraints precluded the 3 x 3 and full SDP, so only the randomized SOC bounds are reported.
Table 6: Objective Values by Dataset. The line separate the relaxations (lower bounds) from the heuristic solutions (upper bounds).
SOC (basis)
SOC (rand.)
SDP (3x3)
SDP (full)
Alg (rand.)
Alg (3x3)
Alg 1 (full)
Dataset
Train Size
iris
120
0.50
1.04
7.68
14.69
16.78
16.78
16.78
wine
142
5.19
5.26
5.65
7.70
7.71
7.71
7.70
breastcancer
455
0.15
0.15
1.06
70.86
83.23
ionosphere
280
50.25
50.25
51.31
80.39
169.77
125.36
121.83
spambase
3680
0.20
0.20
759.10
banknote
1097
0.50
0.74
6.08
42.13
42.13
heart
242
0.19
0.33
1.75
69.95
98.75
98.75
98.75
haberman
244
0.51
1.56
63.15
431.97
476.80
431.97
431.97
mammographic
768
0.50
0.58
450.26
1092.47
1173.24
parkinsons
156
0.19
0.23
1.54
25.69
37.06
37.06
26.31
Table 7 reports the relative optimality gap for those datascts where the full SDP was tractable. On WINE and HABERMAN, the full SDP start drives the gap to zero (within solver tolerance), thereby certifying global optimality. On PARKINSONS, the gap shrinks from 44.3% (random start) to 2.4% (full SDP start), a dramatic improvement. Even for the most challenging instance (IONOSPHERE), the 3 x 3-SDP halves the gap (111.2% 55.9%), and the full SDP reduces it further to 51.6%. This demonstrates that our SDP hicrarchy provides meaningful certificates of hear-optimality for Algorithm 1 real benchmarks.
17

---

Published in Transactions on Machine Learning Research (11/2025)
Table 7: Worst-Case Optimality Gap (%) per Algorithm Variant and Best Estimate
3x3 SDP
Full SDP
Best
Datasct
Train Size
Random
warm start
warm start
gap estimate
iris
120
14.23
14.23
14.23
14.23
wine
142
0.13
0.13
0
ionosphere
280
111.18
55.94
51.55
51.55
heart
242
41.17
41.17
41.17
41.17
haberman
244
10.38
0
parkinsons
156
44.26
44.26
2.41
2.41
5.5 Increasing the number of candidate kernels (Q4)
The experiments in this section were conducted with the candidate kernel set enlarged to = 50 kernels by sampling kornel hyperparancters from denser grids and with cross-validation of C over the set {1,2, 2, 5, 10). We reran all methods with the same data splits and validation protocol as in Section 5.2. Three trends emerge.
(i) Test accuracy. Algorithm 1 remains the most accurate method across datasets, achicving the highest or high-highest test accuracy on every task. Averaged across lasks it attains 90.3% mean accuracy (90.2% on the nine tasks where all baselines ran), versus 80.6% for Easy 79.5% for AverageMKL, and 67.7% for CKA.
Relative the experiments in Section 5.2 (g=10, Table 2), our mean accuracy decreases only slightly (018%%+90.3%) while remaining best-in-class, whereas baselines often drop markedly as q grows (e.g.. MKL on WINE 97.2% 72.2%%. Out-of-sample accuracy for Algorithm remains stable when moving to g 50 (Table 8). The performance several datasets were unchanged (IRIS, WINE, BANKNOTE: 100%). We observed small performance gains on SPAMBASE (+0.5pp to 91.4%) and HABERMAN (+ 1.6pp to 69.4%). while performance declined modestly on a few datasets relative to the 10 kernel setting in Table 2. This pattern is consistent with enforcing a small, fixed cardinality kn, where many of the extra kernels are redundant or only weakly informative.
Dataset
Train Size
Easy MKL
AverageMKL
CKA
Algorithm 1
iris
120
100.0
100.0
76.7
100.0
wine
142
72.2
72.2
77.8
100.0
breastcancer
455
86.0
84.2
69.3
97.4
ionosphere
280
76.1
77.5
62.0
88.7
spambase
3680
85.3
91.4
banknote
1097
99.6
98.9
55.6
100.0
heart
242
70.5
65.6
57.4
90.2
haberman
244
64.5
59.7
66.1
69.4
mammographic
768
76.7
75.6
57.5
81.3
parkinsons
156
79.5
82.1
69.2
84.6
Table 8: Test accuracy (%) when increasing the number of candidate kernels to 50. Bold indicates the best in each row.
(ii) Sparsity. Despite the larger dictionary, Algorithm continues to select a small number of kernels (Table 9), with an average of 1.9 non-zcros out of and per-datasct supports between and 3. By construction AverageMKL uses all 50, while EasyMKL and CKA are denser on average (about 19.3 and 8.1 non-zeros, respectively). Relative to the experiments from Section 5.2 (Table 3), our average support size is
18

---

Published in Transactions on Machine Learning Research (11/2025)
essentially unchanged (~= 2.0 non-zeros at q=10 1.9 at 9=50), while the baselines methods become dense as grows (e.g,, MasyMKT. from ~6 to 19 non-zeros; AverageMKT, from 10 to 50).
Dataset
EasyMKL
AverageMKL
CKA
Algorithm
iris
15
50
10
1
wine
7
50
10
2
breastcancer
7
50
ionosphere
8
50
6
spambase
11
banknote
23
50
8
heart
7
50
7
haberman
50
50
7
mammographic
50
50
6
1
parkinsons
7
50
11
Table 9: Number of non-zero kernel weights (13,1 sparsest solution.
10 10-3) with q 50 candidates.
Bold indicates the
(iil) Training time. On the nine tasks where all methods terminated, Algorithm has comparable aver- age wall-clock time EKL (0.39s vs. 0.41s), and much faster than CKA (3.44s) and AverageMKL 138.13s), whose cost grows with kernel aggregation (Table 10); the largest task (SPAMBASE), only CKA completed the task within 822.97s, while Algorithm trained in 25.37s. Compared to Table 4, execu- tion time scales moderately with (common nine tasks ~0.18s=>0.39s; SPAMBASE 8.33s-225.37s) whereas the runtime of CKA and AverageMKL, increase far more (e.g,, BANKNOTE 0.30s-18.003; MAMMOGRAPHIC 13.03s++342.893)
Note that AverageMKL is typically fast; however, in some tasks (e.g., MAMMOGRAPHIC and HABERMAN) the simple average may yield kernels misaligned with the data, which in turn slows SVM convergence. The higher runtime likely reflects the solver's difficulty enforcing separability when the aggregated kernel lacks sulficient expressiveness.
Datasct
Train Size
EasyMKL
AverageMKL
CKA
Algorithm 1
iris
120
0.048
0.005
0.297
0.032
wine
142
0.167
0.005
0.377
0.022
breastcancer
455
0.662
0.017
2.552
0.285
ionosphere
280
0.238
0.007
0.836
0.103
spambase
3680
822.970
25.372
banknote
1097
1.056
0.024
18.029
1.887
heart
242
0.270
0.008
0.665
0.051
haberman
244
0.064
0.243
0.564
0.051
mammographic
768
0.979
342.890
7.284
1.065
parkinsons
156
0.186
0.005
0.394
0.023
Table 10: Training time (seconds) with dataset.
50 candidate kernels. Bold indicates the fastest method per
Overall, expanding the kernel dictionary improves flexibility without sacrificing interprctability or efficiency for Algorithm 1: test accuracy remains state-of-the-.e while exact cardinality keeps the learned combination sparse and training times practical.
19

---

Published in Transactions on Machine Learning Research (11/2025)
5.6 Summary of Findings
We are now in a position to answer the four questions introduced at the start of this section.
First, regarding predictive accuracy (Q1), Algorithm I achieves high out-of-sample accuracy while enfore- ing exact sparsity constraints. Across all ten UCI benchmarks, the randomly initialized variant Algorithm matches or outperforms the strongest open-source MKL baseline while selecting a small number of kernels from the candidate pool. On average, Algorithm 1 improves test set accuracy by 3.34 percentage points com- pared to the best competing method, with absolute gains reaching up 7.6 percentage points on challenging datasets such as IONOSPHERE, HEART, and PARKINSONS. These results highlight that exact cardinality con- straints, when appropriately enforced, not only preserve but can enhance predictive performance relative to dense kernel combinations.
Second, regarding the effect of warm starts (Q2), initializing Algorithm 1 with solutions from SDP relax- ations yields systematic benefits when computationally feasible. Warm starts based on the 3x3 principal- minor or full SDP relaxations consistently reduce the final optimality gap halving it in several cases and can yield accuracy improvements exceeding 5 percentage points. However, solving the full SDP or even the restricted 3x3 SDP relaxation becomes computationally infeasible for large datasets. In such cases, the ran- dom start version of Algorithm 1 remains highly competitive, achieving strong generalization performance without incurring the substantial overhead of solving costly semidefinite programs.
Third, regarding optimality (Q3), our semidefinite relaxations certify that Algorithm I attains solutions that are near-optimal. On two datasets, the objective value achieved by Algorithm 1 matches the full SDP lower bound within solver precision, certifying global optimality. Even in the most challenging instances, the worst-case optimality gap remains below 52%, offering strong empirical evidence that SMKL consistently identifies high-quality solutions within the feasible set.
Finally, regarding scalability (Q4), enlarging the kernel dictionary (from q=10 to 5050) preserves our accuracy advantage while keeping the learned combinations strictly sparse. The training time of our approach grows modestly with g, whereas baselines tend to become more dense or slow substantially as the candidate set expands.
Taken together, these results establish that Algorithm I's exact-sparsity alternating best response strategy produces classifiers that are simultaneously interpretable, computationally efficient, and in many cases near- optimal. The method scales favorably to large datasets and candidate kernels without sacrificing predictive accuracy, offering a practical and theoretically grounded solution to the sparse multiple kernel learning problem.
6 Conclusion
In this paper, we formulate the sparse mulliple kernel learning problem with an exact cardinality constraint on the kernel weights and present an alternating best response algorithm (Algorithm 1) that produces empirically strong solutions efficiently. Morcover, we reformulate the sparse multiple kernel learning problem as a mixed integer semidefinite program and derive a hierarchy of convex relaxations that deliver strong lower bounds and effective warm starts for Algorithm 1. Our numerical results on ten UCT benchmarks demonstrate that the randomly initialized variant of Algorithm 1 outperforms the open-source baselines AVERAGEMKL, EASYMKL, and CKA in out-of-sample prediction accuracy on average by 3.34 percentage points (relative to the best performing benchmark method) while selecting a small number of kernels in comparable runtime. Using the solution to our semidefinite relaxation as a warm start further shrinks the optimality gap of the solutions returned by Algorithm and yields additional out-of-sample accuracy gains of up to five percentage points.
These results illustrate that by imposing exact sparsity, our approach improves prediction accuracy while simultaneously providing interpretable kernel combinations and certificates of near-optinality. Future work includes developing a custom branch and bound algorithm that leverages the SDP relaxation given by equation 14 to obtain globally optimal solutions to the MISDP given by equation 12, and extending our framework to the regression setting.
20

---

Published in Transactions on Machine Learning Research (11/2025)
A
Common Kernel Families
Here, we briefly review commonly used families of kernel functions that consider in this work.
A.1
Linear
The linear kernel is given by ((x,, æ;y) = x x, for vectors 2; 2 E E This is the most primitive kernel which corresponds to the identity feature map. This kernel works well when the data is approximately linearly separable in its latent space. Linear kernels are especially popular in high-dimensional settings such as document classification, where sparse bag-of-words representations often admit an effective linear decision boundary and enable efficient training (Joachims, 1998).
A.2 Polynomial
The polynomial kernel of degree d N is given by (x,,, (a æy +c) for vectors 2;; 2y E R" where > 0 IR. This kernel allows learning nonlinear relationships by mapping inputs into the feature space of monomials up to degree d. Polynomial kernels were featured in early SVM work to demonstrate the kernel trick Boser et al. (1992); Cortes & Vapnik (1995). They can be useful for data where feat ura interactions of a known order are important, though choosing a very large degree d increases the risk of overfitting.
A.3 Radial Basis Function (RBF)
The RBF kernel, sometimes referred to the Gaussian kernel, is given by ((;;, m.)) exp(->/la;- -x, 2,,l²) for vectors Z;, Ri & Rn where 7 > 0. The RBF kernel corresponds to an infinite-dinensional feature map and is universal, meaning that its reproducing kernel Hilbert space can approximate any continuous function arbitrarily well on compact subsets of IK" (Steinwart, 2001). This kernel has become one of the most commonly used kernels in practice (Schölkopf Smola, 2002). The RBF kernel is governed by single bandwidth parameter 7, simplifying model selection relative to, for example, polynomial kernels. Thanks to its flexibility and strong empirical performance, it is the default choice in many SVM packages (e.g.. LIBSVM uses the RBF kernel by default (Chang & Lin, 2011)).
A.4 Sigmoid
The sigmoid kernel is given by K( my) tanh( xx] æy +r) for vectors æ; 2y E T where y 0, R. Also known the neural network kernel, this kernel arises from the activation function of a two-layer perceptron. It gained some popularity in early SVM experiments due to its connection to neural networks (Burges, 1998). In practice, the sigmoid kernel can behave like the RBF kernel for certain parameter settings (Schölkopf & Smola, 2002).
A.5 Laplacian
The Laplacian kernel is given by K(x,, exp(->llæ; 21 for vectors H,, æj R where 0. The Laplacian kernel is similar to the RBF kernel but uses the & distance as mcasure of similarity in place of using the f distance. Like the RBF kernel, the Laplacian kernel has a single width parameter y that controls the decay of the similarity measure.
B Deferred Proofs from Section 3
We present proof of Proposition 1.
Proof We establish Proposition by showing that the sequence (a,, B, lives in a compact set. then follows by the Bolzano- Weierstrass theorem that the sequence has at least one accumulation point.
Let (r) (a R" ||| < r²) denote the n-dimensional ball of radius centered at the origin. From
the feasibility of the iterates at, have ar E (a R En ozli 0,C 2 a4 2 0 vij C Ba(vnC)
21

---

Published in Transactions on Machine Learning Research (11/2025)
for every iteration t. Similarly, the feasibility of the iterates 3r implies that Bg E {B E R2 Ei= 1. 1,11,81o I ko) C (1) for every iteration L. Thus, the sequence (ax, Br ) is contained in the closed and bounded set Bx(vnC) x (1).. Since Ba(vCC) x (1) is Euclidean, it follows from the Heine-Borel theorem that being closed and bounded is equivalent to being compact. This completes the proof.
We present proof of Proposition 2.
fiJ and B (8 31 I Ko) denote the feasible sets of a and & respectively. Let f(a, 3) = Ei= a, - (y 1 1 3,K, (y a) + ||l@l| denote the objective function of equation 4. From the definition of Algorithm 1, we have Since
Proof Tet Let A= fa E R$
0.11 =
0t+1 E argmax ((a, for all L. Taking limits, we have a E limy-+e A is compact and f(ax, Bt) is continuous, we can interchange the limit and the argmax operation by Berge's Maximum Theorem to obtain that a* argmax f(x, 8*). An analogous argument allows to conclude that similarly have 3 E argminges f(a",8) Thus, (a",, ,8*) is mutual best response pair.
aex
Finally, we present a proof of Theorem 3.
Proof Let A, B. (3) be defined as they were the proof of Proposition 2. Let B = (3 E TRQ 3 = 0 Vi & S} C B. By assumption, for all t 2 To we have Bg E B. Observe that both .A and B are convex sets. Moreover, we have Vzl(a, g) 2XT therefore for any fixed ā E the function f(ā,)) :) is 2X-strongly convex. Similarly, we have (af(a, = -Diag(y) Ei=1 B.K,] Diag(y) therefore for any fixed A E B the function (9) is ma-strongly concave where m. min; An (K,) (note that ma 0 because all kernels are assumed to be positive definite). This is because ma is lower bound on the smallest eigenvalue of Diag(y) [ 3; K. Diag(y).
Let L denote an upper bound on the operator norm of the matrix of mixed second derivatives of f(ar 3). Specifically, we have L 2 Va
Define the functions g : B + A,h : A + B as g(3) argmax (ax (3 and h((a) argmin f(xx,, ()) respectively. Observe that since ((( is strongly concave, there unique maximizer over the convex set A so g is a well defined vector valued function. Similarly, h is well defined vector valued function since f(a, .) is strongly convex which implics the existence of unique minimizer over the convex set B. We claim that g(B) is Lipschitz with constant L To see this, consider two arbitrary vectors 3,8 E B. From strong concavity of f(, we have:
ma
[a -
2 m. mall9(3) -
g(B)]12-
Moreover, from the definition of L, we have
-v.ff)))))) B)1l S -113- -B112-
Observe that from the definition of g(B), we must have vaf(g(B), B) = 0 for all B e B. Therefore, from the two precoding inoqualitics, we have:
ma - -(()) S (IVaJ 11 S LII B1|2 = |10( - -(ا)ه12 S ma
-113- -112-
L
A similar argument allows to conclude that h(a;) is Lipschitz with constant L 2X
For all 2 To, the iterates produced by Algorithm 1 satisfy 0++1 = g(3)) and B.+1 = h((441)) From strong convexity of f(a..) and strong concavity of ((,,)), there exists a unique saddle point (a* , on the convex set A B satislying ax = =(8*) and 3 = h(a"). For any 2 To, we have:
I ||B. 1-1112
I.
I,2
||441 a ||2 (l9)(3)) |12")
[1(ax)) h(aa))))))))) )12 22ma
aa =
ma
ma
22

---

Published in Transactions on Machine Learning Research (11/2025)
Similarly, have [|s 1- I 2Am | 12 Thus, if L < 2A the and 3 updates are contraction and by the Banach Fixed--Pontt Theorem the sequence {ar, B1)12% converges linearly to 1.2
L2
(8", with rale 2Ama
To conclude the proof, it remain to show that we can take L = CVnku max, A1 (1 To see this, observe that for 3 E B, we have (a, B) = 1- - -Diag(y) Eies 3r (Diiag(y) For any i E S we have 8
a5, Va/ (a, B) = -Diag (y) K, (iDig((y) (for $ S, we trivially have ap, Val(a, 9) = 0). For i E S, we have the upper aB, (af 3)1l2 & ||]|||| K1 Cymmax, A1 (K)). Thus, have that Va B)
bound || 0
Cynko max, A (Kz). This concludes the proof.
C a-subproblem Dual Derivation
We present explicit derivation of equation 10 the dual of equation 7. We begin the derivation by trivially rewriting equation 7 as:
a
max a ME
0 2"
K(B)v
a SC ViE [n].
(19)
y:04
1/: y:a, Vi [n].
We introduce non negative dual variables R and uncontrained dual variables n E R, Y E R" for the contraints a S C, Σn yia; and v, yıa; respectively. We can now write the Lagrangian of equation 19 as:
((a,v,,,,,) = Σ a, 7" (((K) + Σ aC - as) - 17 y;a, + Σ
m(u - vaa)),
1=1
i=1
1=1
1 デ" K(B)u+
=C oi
Σ
a 0, 1881 - -391
The dual problem now given by milla maxa,v L(ax, v, ,, To see that this is equivalent to equa- tion 10, first notice that maximizing L(a, v, ",,,) over a produces a finite value if and only if have o, S (nn + 7)) for all i. In this setting the second term of the Lagrangian vanishes after maximizing Next, notice that the Lagrangian is concave quadratic function of For arbitrary vector decompose it as v = wll + where wlll is contained in the column space of (( (meaning that wll = K(B)A for some X E R") and - is contained in the null space of (B) (meaning that K KB3)=² = 0). Given this, we can rewrite the last two terms the Lagrangian as:
-" K(3)u + (U))-- TTlul+++
(20)
Therefore, maximizing the Lagrangian over v will only produce a finite value if TTT' D = 0. This occurs exactly when 7 lies in the column space of K(B), which can be expressed algebraic by the equation y = [E% [Eg B,K,)* 1y. Differentiating with respect to will and setting the gradient to be zero, the optimal wlll that maximizes the Lagrangian satisfics 7 = K(B)ull = wlll K())tt. Plugging this value of wil into the Lagrangian, the last two terms simplify (Kt)tty Thus, we have shown that mingany maxa.v L(a, U, ())) is given by:
23

---

Published in Transactions on Machine Learning Research (11/2025)
min VER,OER
04 + 2
Σ
B,
1=1
8.1.
1 - S vi(n + 7/1
ViE [m]]
3 K, 7 0.
In
B K
D Deferred Proofs from Section 4
We present proof of Proposition 4.
Proof We show that given feasible solution to equation 10, we can construct feasible solution to equation 11 that achieves the same objective value and that given a feasible solution to equation 11, we can construct a feasible solution to equation 10 that achieves an objective that is no greater than the objective value achieved by the feasible solution in equation 11.
First, consider an arbitrary solution (7) () that is feasible to equation 10. Let
0 Ú= 7"
K 4.
Clearly, (17, 0, 7) achieves the same objective value in equation 11 as 7, achieves in equation 10. To see that (77, 0, 7) is feasible to equation 11, we need only verify that semidefinite constraint in equation 11 is satisfied. Recall that for any / feasible in equation 4, the matrix Σ S,K, will be positive semidefinite. Furthermore, from the definition of Ø follows immediately that Ø 7" [E B,K, ' ž 0, and from the EL_1 K,K, )r = 0. Therefore, by
fcasibility of feasibility of y in equation 10 we have (In 1h-11 E K,
the Generalized Schur Complement Lemma, we have (0)
7
0.
7 | 3:K:
Now, consider an arbitrary solution 0, 7) that is feasible to equation 11. We claim that (7, o 7) is feasible in equation 10 and achicves an objective value no greater than the objective value achieved by (17, 0, 7) in equation 11. To see this, it suffices to note that from the Generalized Schur Complement Lemma, feasibility of (17 () in equation 11 implies that we have (I, 1 -EE 3.K, [E and that 0 2 [ 3.K, 7. This completes the proof.
Next, we present a proof of Theorem 5.
Proof By the duality between the alpha subproblem of equation 4 (given by equation 7) and equation coupled with Proposition 4, it suffices argue that equation 14 valid convex relaxation of equation 12 to establish Theorem 5. Clearly, equation 14 is a convex optimization problem. We will show that given any leasible solution to equation 12, we can construct feasible solution to equation 14 that achieves the same objective value.
Let (7, 1.0.07933)) 7) E R x RX X R" x R denote an arbitrary feasible solution to equation 12. Define J. 3." and & = 1 if B > O, otherwise & 0 for all [q]. Observe that (ñ. 0, o, 7, B, 22 is feasible equation 14. To see this, note that have 2,5; B, and Ei || < kn- Moreover, have Σl W _ B." || which shows that (7, 0, or 7, 8,8,B. و, achieves the same objective value in
equation 14 as (7. 6, o. 7, 3) achieves in equation 12. This completes the proof.
Finally, we present a proof of Thcorem 6.
Proof
24

---

Published in Transactions on Machine Learning Research (11/2025)
Define the sets A and B as:
(
[ B.K.) ( ).ki)==1 =0].
Y"
A = =x
9
B = e R 3T EERE R" 1 Σ Th T3 Σ B B 2 (F Vj
It suffices to show that we have A B. Recall that for any B E IR the combined kernel Eis B K, will be positive semidefinite so by the generalized schur complement. the matrix
7 (
|EL,
will be positive
semidefinite if and only we have 2 I" 3,K,J'y Since the candidate kernels are simultaneously
diagonalizable, we can express the pseudo inverse of the combined kernel as:
Σ B K;
U
B.D:
U
UAUT.
li=1
where A E Rax" is a diagonal matrix with diagonal entries defined as A,J = ET. B, D,ly
if if 3, B.
>
0, otherwise Aj 0. Thus, have
9 y
Ki
7= ~UU"
7= An)(
-" [h B. ''y equivalent the existence of a vector R such that 0 Z Σ}= Ty and T, 2 Anj(7 (7 u; for each j. Finally, recalling the definition of A, we can rewrite the inequality Tj 2 A as Σi= 3 Dily 2 u2,)). This completes the proof.
Therefore, the condition 0 2
References
Fabio Aiolli and Michele Donini. Easymkl: scalable multiple kernel learning algorithm. Newrocompuling; 169:215 224, 2015.
Francis R. Bach. Consistency of the group lasso and multiple kernel learning. Journal of Machine Learning Research, 9:1179-1225, 2008.
Francis R. Bach, Gert R. G. Lanckriet, and Michael Jordan. Multiple kernel learning, conic duality, and the smo algorithm. In Proc. 21st International Conference on Machine Learning (TCML., pp. 41-48, 2004.
Dimitris Bertsimas and Martin Copenhaver. Characterization of the equivalence of robustification and regularization in linear and matrix regression. European Journal of Operational Research, 270(3):931 942, 2018.
Grigoriy Blekherman, Santanu Dey, Marco Molinaro, and Shengding Sun. Sparse psd approximation of the psd cone. Mathematical Programméng, 191(2):981 1004, 2022.
Bernhard E. Boser, Isabelle M. Guyon, and Vladimir N. Vapnik. A training algorithm for optimal margin classifiers. In Proceedings of the 5th Annual ACM Workshop on Computational Learning Theory (COLT), pp. 144-158 152, 1992.
Olivier Bousquet and André Elissceff. Stability and generalization. Journal of machine learning research, 2 (Mar):499-52) 526, 2002.
25

---

Published in Transactions on Machine Learning Research (11/2025)
Stephen Boyd, Laurent El Ghaoui, Eric Feron, and Venkataramanan Balakrishnan, Linear matriz inequalities in system and control theory. STAM, 1994.
Christopher J. C. Burges. A tutorial support vector machines for pattern recognition. Data Mining and Knowledge Discovery, 2(2):121 167, 1998.
Chih-Chune Chang and Chih-Jen Lin. LIBSVM: library for support vector machines. ACM Transactions on Intelligent. Systems and Technology, 2(3):27:1 27:277, 2011.
Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine Learning. 20(3):273 297, 1995.
Corinna Cortes, Mehryar Mohri, and Afshin Rostamizadeh. Algorithms for learning kernels based on centered alignment. Journal of Machine Learning Research, 13:795- 828, 2012.
Dheeru Dua and Casey Graff. Uci machine learning repository. http://archive ics. uci sdu/ml, 2017.
Mehmee Gönen and Ethem Alpaydmn. Multiple kernel learning algorithms. Journal of Machine Learning Research, 12:2211- 122211-2268, 2011.
Oktay Günlük and Jeff Linderoth. Perspective reformulation and applications. In Jon Lee and Sven Leyffer (ods.), Mixed Integer Nonlinear Programming, pp. 61-89, New York, NY, 2012. Springer New York. ISBN 978-1-4611--197--.
Thorsten Joachims. Text categorization with support vector machines: Learning with many relevant fea- tures. In Claire Nédellec and Céline Rouveirol (eds.), Machine Learning: ECML-98, pp. 137 142, Berlin, Heidelberg, 1998. Springer Berlin Heidelberg. ISBN 978-3-5400-6981-77
Marius Kloft, Ulf Brefeld, Soeren Sonnenburg, and Alexander Zien. no-norm multiple kernel learning. Journal of Machine Learning Research, 12:953-999 99789997444 2011.
Vladimir Koltchinskii and Ming Yuan. 3660-300 3695, 2010.
Sparsity in multiple kernel learning. Annals of Statistics, 38(6):
Anastasios Kyrillidis, Stephen Becker, Volkan Cevher, and Christoph Koch. Sparse projections onto the simplex. In Sanjoy Dasgupta and David McAllester (eds.), Proceedings of the 30th International Conference on Machine Learning, volune 28 of Proceedings of Machine Learning Research, pp. 235 243, Atlanta, Georgia, USA, 17-19 Jun 2013. PMI.R
Gert R. G. Lanckriet, Nello Cristianini, Peter Bartlett, Laurent El Ghaoui, and Michael 1. Jordan. Learning the kernel matrix with semidefinite programming. Journal of Machine Learning Research, 5:27-72, 2004.
Ailsa H. Land and Alison G. Doig. An Automatic Method for Solving Discrete Programming Problems, pp. 105-132. Springer Berlin Heidelberg, Berlin, Heidelberg, 2010.
Ivano Lauriola and Fabio Aiolli. MKLpy: A python-based framework for multiple kernel learning. arXiv:2007.09982 2020.
Darrin P. Lewis, Tony Jebara, and William S. Noble. Support vector machine learning from heterogeneous data: An empirical analysis using protein sequence and structure. Bioinformatics, 22(22):2753 2760, 2006.
John DC Little. Branch and bound methods for combinatorial problems. PhD thesis, MIT, 1966.
Art B. Owen and Patrick O. Perry. valldais-vllidatiion of the SVD and the nonnegative matrix factorization.
The Annals of Applied Statistics, 3(2):564 594, 2009.
Alain Rakotomamonjy, Francis R. Bach, Stéphane Canu, and Yves Grandvalet. Simplemkl. Journal of Machine Learning Research, 9:2491-255 2521, 2008.
26

---

Published in Transactions on Machine Learning Research (11/2025)
Albert Reuther, Jeremy Kepner, Chansup Byun, Siddharth Samsi, William Arcand, David Bestor, Bill Berg- eron, Vijay Gadepally, Michael Houle, Matthew Hubbell, Michael Jones, Anna Klein, Lauren Milechin, Julia Mullen, Andrew Prout, Antonio Rosa, Charles Yee, and Peter Michaleas. Interactive supercomput- ing on 40,000 corcs for machine learning and data analysis. In 2018 IEEE High Performance extreme Computing Conference (HPEC), pp. 1-6. IEEE, 2018.
Bernhard Schölkopf and Alexander J. Smola. Learning with Kernels: Support Vector Machines, Regulariza- tion, Optimization, and Beyond. MIT Press, Cambridge, MA, 2002.
Dogyoon Song and Pablo A Parrilo. On approximations of the psd cone by polynomial number of smaller- sized psd cones. Mathematical Programming, (18(1):733-788) 2023.
Soeren Sonnenburg, Gunnar Raetsch, Christin Schafer, and Bernhard Schölkopf. general and efficient multiple kernel learning algorithm. In Advances in Neural Information Processing Systems 18 (NIPS), pp. 1273 1280, 2006.
Ingo Steinwart. On the influence of the kernel on the consistency of support vector machines. Journal of machine learning research, 2(Nov):66-99) 2001.
Niranjan Subrahmanya and Yung C. Shin. Sparse multiple kernel learning for signal processing applications. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(5))788-795) 798, 2010. doi: 10.1109/ TPAML.2009.98.
Robert Tibshirani. Regression shrinkage and selection via. the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267 288, 1996.
Hui Xue and Yu Song. Non-convex approximation based fo-morm multiple indefinite kernel feature selection. Applied Intelligence, 40(11):4012-4000 2019.
27


Reviews:
[{"review_id": "3rJdldcutX", "reviewer": "Reviewer_c5bU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "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": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents new approaches to learn a sparse kernel function from a linear combination of kernel functions. The paper imposes an explicit $\\ell_0$ constraint to the basis combination coefficients, and proposes to solve the optimization problem by alternative minimization strategies. The update of the weight vector can be done by standard LIBSVM solvers. The update of combination coefficients can be exactly computed in quasilinear time. The paper further proposes an exact reformation as a mixed integer semidefinite optimization problem and considers the convex relaxation. The paper also presents extensive experimental comparisons with three baseline methods to check the efficiency of the proposed algorithm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "**Strength**\n\n- The paper proposes to learn a sparse combination of kernel functions by imposing a $\\ell_0$ constraint. A nice property is that the update of the kernel coefficients can be exactly computed. This is impressive since the $\\ell_0$ constraint is highly challenging to handle in general.\n\n- The paper also gives interesting reformulations based on mixed integer semidefinite optimization problems, which is useful to design guidelines to certify optimality of the solution.\n\n- The authors open-resources the code to a website.\n\n- The authors also make an empirical comparison on test accuracy, execution time, sparsity and optimality gap and the initialization strategies. These experimental comparisons show consistent improvements over baseline methods.\n\n\n**Weakness**\n- The proposed methods consider $\\ell_0$, $\\ell_1$ and $\\ell_2$ regularizer/constraints. This introduces two hyperparameters to tune. Furthermore, the proposed method also needs to tune the hyperparameter $C$. This may cause high computation costs to tune these hyperparameters.\n\n- The paper considers three baseline methods EasyMKL, averageMKL and CKA. These seem to be not the most strong baseline methods in MKL. For example, another strong baseline method is $\\ell_p$-norm MKL MKL introduced in [1]. It would be interesting to make a comparison with this baseline.\n\n\n\n[1] Marius Kloft, Ulf Brefeld, Soeren Sonnenburg, and Alexander Zien. $\\ell_p$-norm multiple kernel learning. Journal of Machine Learning Research, 12:953–997, 2011.", "audience_yn": "Yes", "audience_explanation": "Learning good kernels are effective to improve the representation power of models since a kernel function corresponds to a feature. MKL provides a principled method to learn the kernel from datasets. This paper proposes a new MKL method which can improve the sparsity. The paper also gives several reformulations of the problem to improve the implementation efficiency. These techniques should be interesting to TMLR community.", "requested_changes": "- It would be interesting to consider strong baseline methods such as $\\ell_p$-norm MKL in the experimental comparison.\n\n- The structure can be improved. For example, the paper includes some proofs in Section 4. It would be better to collect these proofs in a single section, or put them to appendix.\n\n- In Section 4.1, the paper shows that the dual problem of the alpha subproblem in Problem 4 is Problem 10. It is not quite clear to me why this holds. It would be nice if the authors can give some explanations.\n\n- In table 4, the paper shows that AverageMKL requires 1.9 and 13 seconds for two datasets, which are much larger than other methods. This is a bit surprising since AverageMKL simply uses the average of base kernels as the kernel function. Then, it should achieve the smallest computational cost. It would be nice if the authors can give some explanations.\n\n- Theorem 3 requires that the kernels are simultaneously diagonalizable. This is a strong assumption. In practice, most kernel matrices cannot be simultaneously diagonalizable.\n\nMinor issues\n- The authors should be consistent in the use of notations. For example, $m$ and $n$ are used for dimensionality and sample size, respectively in Section 1. However, in Section 2, $n$ is used for dimensionality.\n- Section 2.1.2: \"a useful\" should be \"an useful\"\n- Section 4.1: \"It's dual\" should be \"Its dual\"\n- Section 4.2.1: \"$n+1 \\times n+1$\" should be \"$(n+1)\\times(n+1)$\"\n- Section 5.4: \"we can we can\" should be \"we can\"", "broader_impact_concerns": "No issues on ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "sHw4JjiXXv", "reviewer": "Reviewer_Pmss", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "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": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses sparse multiple kernel learning by introducing a novel formulation that imposes an explicit cardinality constraint on kernel weights, combined with an L2 penalty. To be specific, an additional <= constraint of non-zero elements is added to the L1-regularized kernel weights, offering extra control over sparsity.", "claims_and_evidence_yn": "Yes", "claims_explanation": "1. The alternating best response algorithm is well-designed, leveraging efficient subproblem solvers (LIBSVM for $\\alpha$, custom greedy/projection for $\\beta$).\n2. The derivation of semidefinite convex relaxations provides a theoretical foundation for certifying solution quality.\n3. Comprehensive empirical evaluation on multiple UCI datasets demonstrates consistent and substantial improvements over existing MKL methods, with clear ablation (random vs. warm start) and runtime comparisons.", "audience_yn": "Yes", "audience_explanation": "Solving MKL problem with explicit cardinality constraint is an important research topic.", "requested_changes": "1. Discuss the feasibility of imposing both >= and <= cardinality constraints.\n2. Include computational complexity analyses\n3. Considering moving Literature Review and Preliminaries to supplementary material to streamline the main text and focus on novel contributions.", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "lSD6rOkuuY", "reviewer": "Reviewer_PSAX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "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": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses Sparse Multiple Kernel Learning (SMKL) by directly imposing cardinality constraints on kernel weights rather than using $\\ell_1$ regularization as a sparsity surrogate. To solve the non-convex optimization problem, the authors propose an alternating best response algorithm that iterates between solving a standard SVM dual ($\\alpha$-subproblem) and a sparse kernel weight selection problem ($\\beta$-subproblem). In both cases, with one subproblem fixed, the remaining subproblem becomes convex and tractable. The $\\alpha$-subproblem can be solved efficiently using existing solvers like LIBSVM. The exact minimizer of the $\\beta$-subproblem can be attained in quasi-linear time.", "claims_and_evidence_yn": "No", "claims_explanation": "The paper presents comprehensive numerical results demonstrating the superior performance of the proposed method across multiple UCI benchmarks, but I have some concerns regarding the absence of theoretical guarantees that would support these empirical claims.\n\nThe authors prove that their mixed integer semidefinite reformulation is equivalent to the original problem. They also show that their SDP relaxation (from $z\\in \\{0, 1\\}^q$ to $z\\in [0, 1]^q$) provide a valid lower bound. \n\nHowever, besides these, **i)** there doesn't seem to be convergence analysis of the algorithm; **ii)** it's hard to argue how close the heuristic solutions are to the global minima since the lower bounds based on SDP relaxations may be quite loose; **iii)** there is no generalization error analysis justifying why we should expect that the exact cardinality constraints improve generalization performance over $\\ell_1$ surrogates; **iv)** it would be very useful to include an analysis of the algorithm's computational complexity.", "audience_yn": "Yes", "audience_explanation": "The paper presents interesting algorithmic ideas and insightful numerical results.", "requested_changes": "- Sentences like “We present … that produces high quality solutions to Problem 4…” appear multiple times throughout the paper as a description of the main contribution of the paper, but I wonder what exactly “high quality” means. Apart from empirical results, are there any theoretical guarantees on the improvements in predictive accuracy and runtime that the proposed algorithm can achieve? Please see above for the four types of guarantees i)--iv) which I think could largely strengthen the paper.\n\n- p.15: all numerical results consider 10 base kernels. Might 10 be too small to compare various sparsity-inducing methods, as the advantages of sparse selection become most apparent when choosing from larger candidate sets?\n\n- Table 7: I have a question about the certification of near global optimality here. If I understand correctly, the certification is only meaningful when the SDP relaxation happens to be tight. The tightness of this relaxation isn't proven and is only verified post-hoc by observing small gaps in some cases. Is this correct? For the results for breastcancer, spambase, mammographic etc in Table 7, the reported optimality gap seems to be very large, so large that we probably cannot claim optimality here at all. Am I missing something here?\n\n- Minor: For clarity, consider using \\\\\\eqref{} or Eq.~\\\\\\eqref{} to reference equations instead of “Problem xx”", "broader_impact_concerns": "N.A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)