Ultra-Fast Optimization Algorithm for Sparse Multi Kernel Learning

Francesco Orabonafrancesco@orabona.com
DSI, Università degli Studi di Milano, Via Comelico 39, 20135 - Milano, Italy
Luo Jie
Idiap Research Institute, Centre du Parc, 1920 - Martigny, SwitzerlandÉcole Polytechnique Fédérale de Lausanne (EPFL), 1015 - Lausanne, Switzerland

Abstract
Many state-of-the-art approaches for Multi
Kernel Learning (MKL) struggle at finding
a compromise between performance, sparsity of the solution and speed of the optimization process. In this paper we look at
the MKL problem at the same time froma learning and optimization point of view.
So, instead of designing a regularizer andthen struggling to find an efficient method tominimize it, we design the regularizer while
keeping the optimization algorithm in mind.
Hence, we introduce a novel MKL formulation, which mixes elements of p-norm andelastic-net kind of regularization. We also
propose a fast stochastic gradient descentmethod that solves the novel MKL formulation. We show theoretically and empiricallythat our method has 1) state-of-the-art performance on many classification tasks; 2) exact sparse solutions with a tunable level ofsparsity; 3) a convergence rate bound that
depends only logarithmically on the number of kernels used, and is independent of
the sparsity required; 4) independence on theparticular convex loss function used.

1. Introduction
In recent years there has been a lot of interest in designing principled classification algorithms over multiple cues, based on the intuitive notion that using
more features should lead to better performance. Focusing to the domain of the Support vector machines(SVM) (Cristianini & Shawe-Taylor, 2000), the use of
Appearing in Proceedings of the 28 th International Conference on Machine Learning, Bellevue, WA, USA, 2011.
Copyright 2011 by the author(s)/owner(s).

jluo@idiap.ch

multiple cues has been translated in the use of multiple
kernels, weighted by some positive coefficients.
A recent approach in this field is to use a two-stage
procedure, in which the first stage finds the optimal
weights to combine the kernels, using an improved definition of the kernel alignment (Cristianini et al., 2002)
as a proxy of the generalization error, and a standard
SVM as second stage (Cortes et al., 2010). Howeverin this approach, even if theoretically principled, theglobal optimality is not guaranteed, because the optimization process split in two phases.
A different approach with a joint optimization process is Multi Kernel Learning (MKL) (Lanckriet et al.,
2004; Rakotomamonjy et al., 2008; Sonnenburg et al.,2006; Nath et al., 2009; Zien & Ong, 2007).
In
MKL one solves a joint optimization problem while
also learning the optimal weights for combining thekernels. MKL methods are theoretically founded,
which are based on the minimization of an upperbound of the generalization error (Kakade et al., 2009;
Cortes et al., 2010), like in standard SVM. However
solving it is far more complex than training a single SVM classifier. The main difficulty lies in designing efficient optimization algorithms, especially whena sparse solution is wanted. Sparsity is often achieved
using an l1 norm as regularizer or as constraint. Unfortunately, the l1 norm is not smooth, so it slows down
the optimization process.
Most of proposed algorithms for MKL solve this difficult optimization problem with an alternating optimization approach, first optimizing over the kernel combination weights, with the current SVM
solution fixed, then finding the SVM solution,
given the current weights (Sonnenburg et al., 2006;
Rakotomamonjy et al., 2008; Xu et al., 2008). One
advantage of the alternating optimization approach isthat it is possible to use existing efficient SVM solvers
for the SVM optimization step. On the other hand, forUltra-Fast Optimization Algorithm for Sparse Multi Kernel Learningthese algorithms, even if they are known to converge,
it usually is not possible to prove a bound on the maximum number of iterations needed. For the same reason
it is not possible to compute how the relevant quantities affect the asymptotic computational complexity,
and often these dependencies are estimated numerically for the specific implementation at hand. For example, SILP multiclass MKL algorithm (Zien & Ong,
2007) seems to depend polynomially on the number oftraining examples and number of classes with an exponent of ∼ 2.4 and ∼ 1.7 respectively. For the other algorithms these dependencies are not clear. Moreover,the learning process is usually stopped early, based on
the common assumption that it is enough to have anapproximate solution. This approach can be dangerous when a dual algorithm is used, potentially stopping
far away from the optimal solution (Chapelle, 2007).
Notable exception to the use of l1 regularization for
MKL are (Kloft et al., 2009; Orabona et al., 2010;
Vishwanathan et al., 2010) in which a lp norm constraint is introduced, to have a simpler problem andto be able to tune the level of “sparsity” of the solution. However in this case the true sparsity is lost, andthe weights of the kernels, even if they can become extremely small, will never be exactly zero. Another limitation is that many of these algorithms relies on particular loss functions, and the entire algorithm has tobe changed if the loss function is changed (Kloft et al.,2009; Vishwanathan et al., 2010).
In this paper we look at the same time at the MKL
problem from a learning and optimization points ofview. Therefore, instead of designing a regularizer andthen try to find an efficient method to minimize it, we
design the regularizer while keeping the optimization
process in mind. In other words, a perfect regularizer
is useless if it is impractical to be used. The novel MKL
formulation that we propose gives 1) state-of-the-art
performance on many classification tasks; 2) exact
sparse solutions with a tunable level of sparsity; 3) aconvergence rate bound that depends only logarithmically on the number of kernels used, and is independentof the sparsity required; 4) independence on the particular convex loss function used. As in (Orabona et al.,2010; Jie et al., 2010; Martins et al., 2011), our algorithm solves the optimization problem directly inthe primal formulation. This allows us to use any
complex loss functions, as the multiclass loss in(Crammer & Singer, 2002) or more in general structured losses (Tsochantaridis et al., 2004), with minimal changes to the algorithm. We call this algorithm
Ultra Fast Online Multi Kernel Learning, UFO-MKL.
The rest of the paper presents the theory and the ex-perimental results supporting our claims. Section 2 revises the basic definitions and the mathematical tools
needed, Section 3 introduces the Multi Kernel Learning problem. Section 4 presents the theory and algorithm of UFO-MKL, while Section 5 reports experiments on binary and multiclass classification tasks.

2. Preliminaries
In this section we introduce formally the notation, andthe needed mathematical tools. We indicate matrices
and vectors with bold letters. We also indicate with abar, e.g. w̄, the vector formed by the concatenation of
the F vectors wj , hence w̄ = [w1 , w2 , · · · , wF ].
We also introduce some concepts of convex analysis
that are needed in the following. For a more thoroughintroduction see for example (Boyd & Vandenberghe,2004). Given a convex function g : S → R, its
Fenchel conjugate g ∗ : S → R is defined as g ∗ (u) =supv∈S (v T u − g(v)). A vector x is a subgradient of afunction g at v, if ∀u ∈ S, g(u) − g(v) ≥ (u − v) · x.
The differential set of g at v, indicated with ∂g(v), is
the set of all the subgradients of g at v. If g is convex
and differentiable at v then ∂g(v) consists of a single
vector which is the gradient of g at v and is denoted by∇g(v). A function g : S → R is said to be λ-strongly
convex w.r.t. a convex and differentiable function h iff
for any u, v ∈ S and any subgradient ∂g(u), g(v) ≥g(u)+∂g(u)·(v −u)+λ(h(v)−h(u)−(v −u)·∇h(v)),
where the terms in parenthesis form the Bregman divergence of h between v and u.
Let {xi , yi }N
i=1 , with N ∈ N, xi ∈ X and yi ∈ Y, be
the training set. Consider a function φ(x) : X → H
that maps the samples into a high, possibly infinite,
dimensional space. In the binary case Y = {−1, 1},
and we use the standard setting to learn with kernels1 , in which the prediction on a sample x is afunction of the scalar product between an hyperplane
w and the transformed sample φ(x). With multiple kernels, we will have F corresponding functions
φj (·), j = 1, · · · , F , and F corresponding kernels
K j (x, x′ ) defined as φj (x) · φj (x′ ).
For multiclass and structured classification Y ={1, . . . , M }, we follow the common approach touse joint feature maps φ(x, y) : X × Y →H (Tsochantaridis et al., 2004). Again, we will have
F functions φj (·, ·), j = 1, · · · , F , and F kernels
K j ((x, y), (x′ , y ′ )) = φj (x, y) · φj (x′ , y ′ ). This definition includes the case of training M different hyperplanes, one for each class. In fact φj (x, y) can be1
For simplicity we will not use the bias, it can be easily
added modifying the kernel definition.

Ultra-Fast Optimization Algorithm for Sparse Multi Kernel Learning

defined as
φj (x, y) = [0, · · · , 0, φ′j (x), 0, · · · , 0],| {z }ywhere φ′j (·) is a transformation that depends only on
data. Similarly w will be composed by M blocks,[w1 , · · · , wM ]. According to the defined notation,φ̄(x, y) = [φ1 (x, y), · · · , φF (x, y)]. With a slight abuseof notation, in the following we will denote by φ̄(x, ·)both the binary and multiclass feature transform.
A (2, p) group norm kw̄k22,p on w̄ is defined askw̄k2,p :=

kw1 k2 , kw2 k2 , · · · , kwF k2



p

,

that is the p-norm of the vector of F elements, formedby 2-norms of the vectors wj . The dual norm of k·k2,pis k · k2,q , where 1/p + 1/q = 1 (Kakade et al., 2009).

3. Multi Kernel Learning andRegularizers
The MKL optimization problem was first proposedin (Bach et al., 2004) and extended to multiclassin (Zien & Ong, 2007). It can be written as

2
F
N
λ X
1 X
min
kwj k2  +
ξi
w̄ 2
N i=1
j=1

(1)

s.t. w̄ · (φ̄(xi , yi ) − φ̄(xi , y)) ≥ 1 − ξi , ∀i, y 6= yi .

An equivalent formulation can be derived from thethis one through a variational argument. It has beenused in (Bach et al., 2004; Sonnenburg et al., 2006;
Rakotomamonjy et al., 2008). The variational formulation allows to use an alternating optimization strategy to efficiently solve the constrained minimization
problem. Recently in (Orabona et al., 2010; Jie et al.,2010; Martins et al., 2011) it has been shown that it
is possible to efficiently minimize directly the formulation in (1), or at least one variation of it.
We first rewrite (1) with group-norms. Using the notation defined above, we have
min
w̄

N

λ
1 X MCkw̄k22,1 +ℓw̄, φ̄(xi , ·), yi ,
2
N i=1

(2)

where
ℓM C
is
the
multiclasshinge
loss (Crammer & Singer, 2002). The (2, 1) groupnorm is used to induce sparsity in the domain of
the kernels. This means that the solution of the
optimization problem will select a subset of the F
kernels. However, even if sparsity can be desirable

for specific applications, it could bring to a decreasein performance (Kloft et al., 2009; Orabona et al.,2010). Moreover the problem in (2) is not strongly
convex (Kakade et al., 2009), so its optimization algorithm is rather complex and its rate of convergenceis usually slow (Bach et al., 2004; Sonnenburg et al.,2006). The (2, p) group norm has been proposed
instead of the (2, 1) (Kloft et al., 2009; Orabona et al.,2010; Vishwanathan et al., 2010), to be able to decide
the level of sparsity of the solution, but this formulation never induces coefficients that are mathematicallyzero for any p 6= 1. It is also interesting to note thatthe convergence rate of the lp MKL becomes slower
when p → 1 (Orabona et al., 2010). This can be explained formally with the fact that the lp formulationis 1/q strongly convex, where 1/p + 1/q = 1, andstrong convex functions are easier to be optimized.
In fact there are optimization algorithms that havea convergence rate proportional to the inverse of
the strong convexity constant (Hazan et al., 2007).
When p tends to 1, q goes to infinity and the strong
convexity is lost, resulting in a slower convergence. In
other words, it is more difficult and slower to find asparse solution to the MKL problem.
Tomioka & Suzuki (2010) have proposed to use anelastic net form of regularization for MKL, that canbe written as C( λ2 kw̄k22,2 + (1 − λ)kw̄k2,1 ). They havejustified this form of regularization as a mean to control the degree of sparsity of the solution. In this way
the solution has exact mathematical zeros, and thenumber of zeros can be tuned by changing λ.
In the next Section we will introduce the new regularization function, its theoretical properties and its
corresponding optimization algorithm.

4. UFO-MKL
Considering the regularizer in (Tomioka & Suzuki,2010), note that there is no particular reason to use
the (2, 2) group norm, apart from having an easier optimization problem and a way to tune the level of sparsity. Similar considerations hold for the (2, p) groupnorm. Hence, we propose to use a novel regularizer,
with the precise aim of having the optimal convergence rate and an exact mathematical sparsity, tunablethrough a parameter. Our regularization function isΩ(w̄) := λ/2 kw̄k22, 2 log F + αkw̄k2,1 ,(3)

2 log F −1

where F is the number of kernels. The first term ofΩ gives us an easy problem, while the second one
induces different levels of sparsity depending on α.
In fact, with the lp MKL formulation, it is possible to prove a convergence bound of the order ofUltra-Fast Optimization Algorithm for Sparse Multi Kernel Learning

qF 2/q (Orabona et al., 2010). If F ≥ 3 and p =2 log F
2/q
becomes equal to 2e log F , and the
2 log F −1 , qF
rate of convergence will depend logarithmically on thenumber of kernels (Jie et al., 2010). More in details,
with this choice of p the regularization becomes similar
to the entropic regularization. A similar method has
been used in the context of sparse linear optimizationin (Shalev-Shwartz & Tewari, 2009). This motivatesthe choice of the first term in Ω. On the other hand,using only this term would result in a fixed regularization function, losing the possibility to adapt it to the
problem. Hence we mix the (2, 2 log F/(2 log F − 1))squared group norm with a (2, 1) group norm, to beable to tune the level of sparsity.
We propose to use a stochastic gradient descent algorithm, so we can consider a generic loss function ℓ.
Hence the optimization problem becomesNmin Ω(w̄) +
w̄


1 X
ℓ w̄, φ̄(xi , ·), yi .
N i=1

(4)

Having designed the regularizer as being strongly convex for any value of α, to minimize (4) we can use
stochastic gradient descent and mirror descent. Figure 1 shows the minimization algorithm, which wecall Ultra Fast Online Multi Kernel Learning (UFOMKL) algorithm. As in the mirror descent algorithm, two sets of weights are maintained, a primal
one w̄t and a dual one θ̄ t . At each step it takes asample at random from the training set and update
the dual vector θ̄ t with a subgradient descent step,
where ∂ℓ w̄t , φ̄(xt , ·), yt is the subgradient w.r.t. w̄t .
Then the primal weight w̄t is calculated with lines 67. These two lines correspond to the gradient of the
Fenchel dual of Ω. Line 6 have the effect to put tozeros the kernels that have a norm smaller than αt. It
has the effect of inducing exact sparsity in the domainof the kernels. Note that in the algorithm we only needto access to scalar products, so that the kernels can beused without any problem. Even the l2 norms of θ jt+1
can be calculated in an efficient incremental way askθ jt+1 k22 = kθ jt k22 − 2θ jt · z jt + kz jt k22 .
where z̄ t = ∂ℓ w̄t , φ̄(xt , ·), yt .
4.1. Convergence rate guarantee
In this section we prove a theoretical guarantee forthe convergence rate of UFO-MKL to the optimal
solution of (4). We use the primal-dual framework
for the minimization of regularized loss functionsin (Shalev-Shwartz & Kakade, 2008). Note that a similar method has been rediscovered by Xiao (2010). We
use Theorem 2 in (Shalev-Shwartz & Kakade, 2008),

Algorithm 1 The UFO-MKL algorithm.
1: Input: α, λ, T
2: Initialize: w̄ 1 = 0, θ̄ 1 = 0, q = 2 log F
3: for t = 1, 2, . . . , T do
4:
Sample at random (xt , yt )5:
θ̄ t+1 = θ̄ t − ∂ℓ w̄t , φ̄(xt , ·), yt
6:vj = kθ jt+1 k2 − αt + , ∀j = 1, · · · , Fq−2vj θ jv, ∀j = 1, · · · , F7:
wjt+1 = tλkθjt+1k kvkj q
t+1 2

8: end forthat for completeness we restate here in a simpler form
and with our notation.
Theorem 1. (Shalev-Shwartz & Kakade, 2008) Let g
be a β-strongly convex function w.r.t. the norm k · kover a set S and let k · k∗ be its dual norm. Letℓ1 , . . . , ℓT be an arbitrary sequence of convex loss functions, and R such that maxi k∂ℓi (wi )k∗ ≤ R. Define
Pt−1
wt = ∇g ∗ (− ηt i=1 ∂ℓi (wi )) then, for any u ∈ S, andany η > 0 we have
T

1X
T t=1
≤η





T 
1 X g(u)g(wt )+ ℓt (wt ) −+ ℓt (u)η
T t=1ηR2 (1 + log T ).
2βTThis theorem introduces another way to minimize strongly convex regularized objective functions through stochastic gradient descent, different
from the well-known one used in the Pegasos algorithm (Shalev-Shwartz et al., 2007). Here there is norescaling of the hyperplane at each step, so each single
iteration will be faster. This lack of rescaling makes
each iteration of UFO-MKL faster than each iterationof OBSCURE (Orabona et al., 2010), so that the total
time needed to converge can be smaller. We will verify
this experimentally in Section 5.3.
Denote by z̄ = ∂ℓ w̄, φ̄(x, ·), y , we will now state theconvergence theorem for any loss function that satisfies
the following hypothesis
kz j k2 ≤ Lkφj (x, y ′ )k2 , ∀j = 1, . . . , F, y ′ ∈ Y . (5)Note that, for example,
the hinge loss,ℓHL w̄, φ̄(x), y := |1−yw̄
·φ̄(x)|+ , and the logisticloss, ℓLL w̄, φ̄(x), y := log(1 + exp(−y w̄ · φ̄(x))),satisfy this relation with L = 1. The multiclasshinge loss function (Crammer & Singer, 2002;
Tsochantaridis et al., 2004), ℓM C w̄, φ̄(x, ·), y :=′maxy′√
6=y |1 − w̄ · (φ̄(x, y) − φ̄(x, y ))|+ , satisfies with
L = 2 when φ(·, ·) induces the transformation inwhich there is one hyperplane for each class.

Ultra-Fast Optimization Algorithm for Sparse Multi Kernel Learning

Theorem 2. Denote by f (w̄) = Ω(w̄) +PN
1and by w̄∗ the solution
i=1 ℓ w̄, φ̄(xi , ·), yiNthat minimizes (4). Suppose that kφj (xt , ·)k2 ≤ 1,
and the loss function ℓ satisfies (5). Let δ ∈ (0, 1),
then with probability at least 1 − δ over the choices of
the random samples we have that after T iterations of
the UFO-MKL algorithmf (w̄T +1 ) − f (w̄∗ ) ≤eL2 (1 + log T ) log F,λδTwhere e is the Euler’s number.
Proof. (Sketch) Using (5) and kφj (xt , yt )k2 ≤ 1, wehave
k∂ℓ w̄t , φ̄(xt , ·), yt k2,q
≤ LF 1/q max kφj (xt , ·)k2 ≤ LF 1/q
j=1,...,FThe function Ω(w̄) in (3) is λ/q-strongly convex w.r.t.
the norm k · k2,q , for any α ≥ 0. Hence, using Theorem 1, with η = 1 and g = Ω, and using Markov inequality as in (Shalev-Shwartz et al., 2007) we prove
the stated result.
To derive the UFO-MKL algorithm the only thing thatis missing is to calculate ∇Ω∗ (θ̄).
Theorem 3. Lethiv = kθ 1 k2 − α + , · · · , kθ F k2 − α + ,then the component j of ∇Ω∗ (θ̄) is equal tovjq−1
θj
λkθ j k2 kvkqq−2
Proof. (Sketch) From standard Legendre-Fenchel duality, we have that ∇Ω∗ (θ̄) = argmax w̄ · θ̄ − Ω(w̄).
w̄

Setting to zero the derivative of this argmax we havethat wj must must be proportional to θ j , that is
wj = cj θ j /kθ j k, where cj are real numbers. So we
can focus on the coefficients cj , rewriting the argmax:
argmax c · a − αkck1 − λ/2 kck2p ,cwhere a = [kθ 1 k, · · · , kθ F k], c = [c1 , · · · , cF ]. This
problem is analyzed in Sec. 7.2 of (Xiao, 2010), andusing that theorems we have the stated result.

been implemented in MATLAB in the DOGMA library (Orabona, 2009), and we compare it against
the SHOGUN-0.9.2 toolbox2 , which contains the
SILP algorithm (Sonnenburg et al., 2006) and theMulticlass MKL (MC-MKL) algorithm (Zien & Ong,
2007). We also compare it with the OBSCURE
algorithm (Orabona et al., 2010), using the implementation in DOGMA. We consider the parameterα ∈ {0.0001, 0.001, 0.0025, 0.005, 0.0075, 0.01, 0.02},
and use p=1.01 for the OBSCURE algorithm whensparsity is desired in the solution. The λ parameterhas been chosen by cross validation as 1/(CN ), where
N is the number of training points, and C is fromthe set {1, 10, 102 , 103 }, and C=1000 yields the best
results for all the algorithms, except in the first andsecond experiment where we fix C = 100.
We consider both hinge loss ℓHL and logistical loss ℓLL
for the binary classification task, and multiclass loss
ℓMC for all the multiple classes tasks. For multiple
classes extension of the binary SILP algorithm, we use
the 1-vs-All scheme.
5.1. Binary classification
We first carry out a set of experiments on the UCI binary data sets, and compare the results with SILP. We
follow the procedure in (Rakotomamonjy et al., 2008),
to test the algorithms with artificially generated kernels. The candidate kernels are Gaussian kernels with
10 different bandwidths on all and each single dimension of the feature vectors, and similar for polynomial
kernels of degree 1 to 3. In UFO-MKL we use 10
epochs, that is 10 passes over all the training samples,for the Liver and Ionosphere dataset, and 20 epochs
for the Sonar dataset. Results for varying values of
α are presented in Table 1. We can see that UFOMKL is significantly faster compared to SILP whenused with the hinge loss, especially on Sonar where
it is more than 10 times faster. In most cases SILP
gets a sparser solution than UFO-MKL’s one, which isdue to the different regularizer used. It is known thatl1 norm kind of regularizer can result in bad performance when the problem is not sparse (Kloft et al.,2009; Orabona et al., 2010). However, with proper
tuning of α, UFO-MKL can possibly still remove someof the kernels, while still obtain superior performance(see for example α = 1.0e − 3 on the Sonar dataset).
5.2. Multiclass synthetic data

5. Experiments
In this section, we study the behavior of UFOMKL in terms of classification accuracy, computational efficiency and scalability. Our algorithm has

Multiclass problems are often decomposed into several
binary sub-problems using methods like 1-vs-All, how2

Available at http://www.shogun-toolbox.org.

Ultra-Fast Optimization Algorithm for Sparse Multi Kernel LearningαTime (seconds)
Accuracy
Liver, N=241, F=91
2.7 ± 0.3
71.8 ± 3.8
2.9 ± 0.3
66.1 ± 2.7
3.5 ± 0.4
68.7 ± 4.1
3.6 ± 0.4
64.5 ± 3.4
3.0 ± 0.6
64.7 ± 1.8
Ionosphere, N=245, F=442
6.1 ± 0.8
92.1 ± 2.1
6.1 ± 0.3
91.4 ± 1.7
8.2 ± 0.5
89.2 ± 2.4
21.9 ± 2.0
91.8 ± 2.6
18.2 ± 1.4
87.8 ± 2.0
19.2 ± 0.9
86.4 ± 3.6
41.9 ± 9.5
91.9 ± 2.1
Sonar, N=145, F=793
9.9 ± 0.5
80.3 ± 3.5
10.9 ± 0.9
79.6 ± 4.7
11.7 ± 0.5
75.7 ± 2.4
22.4 ± 2.1
77.0 ± 4.6
21.9 ± 1.5
75.5 ± 4.1
21.9 ± 1.8
74.4 ± 4.5
191.2 ± 38.7
78.7 ± 3.8

1.0e−32.5e−31.0e−3ℓLL
2.5e−3SILPℓHL

1.0e−32.5e−35.0e−31.0e−3ℓLL
2.5e−35.0e−3SILPℓHL

1.0e−32.5e−35.0e−31.0e−3ℓLL
2.5e−35.0e−3SILPℓHL

Kernel 1

Kernel 2
50

50

100

100

200

150
200

sample−id50100sample−id

50

150

150
200

250

300
0

300
0

100
200
sample−id

300

SILP (Class 1 vs. Class 2+3)

100
200
sample−id

300

SILP (Class 2 vs. Class 1+3)

0.2
0

0.6
0.4
0.2

Kernel 1 Kernel 2 Kernel 3 Kernel 40

Weights1
0.8

Weights1
0.8

Weights

1
0.8

0.4

0.6
0.4
0.2

Kernel 1 Kernel 2 Kernel 3 Kernel 4

0

55

3

10
training time (seconds)

4

10

Figure 2. (Top) Comparison of UFO-MKL to OBSCURE
on convergence rate with the same value of p, and α =0 for UFO-MKL. (Bottom) Performance comparison on
Caltech-101 using different MKL algorithms.

0.2
100
200
sample−id

300

0.6
0.4
0.2

Kernel 1 Kernel 2 Kernel 3 Kernel 4UFO−MKL: 15 examples
UFO−MKL: 30 examples
OBSCURE: 15 examples
OBSCURE: 30 examples
SILP: 15 examples
SILP: 30 examples
MC−MKL: 15 examples

60

UFO−MKL

1
0.8
0.6

65

45 2
10

0.4

250

300
0

70

50

0.6

250
300

75

0.8

300
0

100
200
sample−id

Caltech−101 (39 kernels)

150

250

3

10

80

1

200

2

10

training time (second)

Kernel 4
0

0

10

1

379.7 ± 131.1
192.6 ± 12.5
55.6 ± 9.1
793.0 ± 0.0
200.1 ± 64.8
28.8 ± 4.3
30.0 ± 2.2

0UFO−MKL (p=1.1581, α=0)OBSCURE (p=1.1581)

10

257.7 ± 87.0
93.2 ± 7.9
37.4 ± 5.6
442 ± 0.0
119.7 ± 6.3
1.6 ± 2.5
19.6 ± 3.0

100

SILP (Class 3 vs. Class 1+2)

Weights

89.7 ± 0.6
30.5 ± 3.5
91.0 ± 0.0
28.1 ± 15.4
9.9 ± 1.8

Kernel 30sample−idsample−id0# Kernels6= 0

classification rateLossobjective value

Caltech−101 (15 training examples per category)

Table 1. Training time, accuracy and number of selected
kernels on UCI datasets with N samples and F kernels.

0

Kernel 1 Kernel 2 Kernel 3 Kernel 4

Figure 1. (top) Kernel matrices of the 3-classes synthetic
experiments correspond to 4 different features. Sample
1–100, 101–200 and 201–300 are from class 1, 2 and 3
respectively. (bottom) Corresponding kernel combination
weights, normalized to have sum equal to 1, obtained by
SILP (binary) and by UFO-MKL (multiclass) (last figure).

ever solving the multiclass learning problem jointly using a multiclass loss can yield much sparser solutions.
Intuitively, when l1 -norm is used to impose sparsity inthe domain of kernels, different subsets of kernels canbe selected for different binary classification problems.
Therefore, the combined multiclass classifier might notobtain the desired sparse properties. Moreover, theconfidence outputs of the binary classifiers may notlie in the same range, so it is not clear if the winnertakes-all hypothesis is the correct approach for combing them.
To prove our point, we have generated a 3-classes classification problem consisting of 300 samples, with 100
sample from each class. There are in total 4 different
features, the kernel matrices corresponding to them
are shown in Figure 1 (top). These features are generated in a way that Kernels 1–3 are useful only for

distinguishing one class (class 3, class 1 and class 2,
respectively) from the other two, while Kernel 4 canseparate all the 3 classes. The corresponding kernel
combination weights obtained by the SILP algorithm
using the 1-vs-All extension and our multiclass UFOMKL are shown in Figure 1 (bottom). It can be observed that each of the binary SILP classifiers pick two
kernels. UFO-MKL selects only the 4th kernel, achieving a much sparser solution.
5.3. Multiple classes image categorization
Most of the state-of-art results obtained on several
object categorization datasets use algorithms which
combine multiple features (see (Gehler & Nowozin,
2009; Orabona et al., 2010) and references therein).
The Caltech-101 dataset is the most popular benchmark for object categorization.
In the experiments, we used the pre-computed features and kernels of (Gehler & Nowozin, 2009) which the authors
have made available3 . There are in total 39 kernels,
with 5 different training and test splits. The best
results on this data were obtained using regularization which favors sparsity (Gehler & Nowozin, 2009;
Orabona et al., 2010). For brevity, we refer the interested reader to (Gehler & Nowozin, 2009) for thedetails of the features and kernels.
3

www.vision.ee.ethz.ch/~pgehler/projects/iccv09/

Ultra-Fast Optimization Algorithm for Sparse Multi Kernel Learning

Following the experimental setup widely used in thecomputer vision literatures, we also report the results obtained using different MKL methods on various number of training data in Figure 2 (bottom).
The results support our claim of the previous sectionthat multiclass loss function is more suitable for thistype of problem, as all the methods that use the multiclass loss outperform SILP. MC-MKL is computational
infeasible for 30 samples per category, and its significant performance gap from OBSCURE and UFOMKL seems to indicate that it stops before converging
to the optimal solution. UFO-MKL also outperforms
OBSCURE, probably because OBSCURE does not geta real sparse solution although it tends to be sparse.
More importantly, the accuracy is comparable withthe best results obtained in the literature by the LPβ algorithm (Gehler & Nowozin, 2009) using the same
kernels: 70.4% for 15 training samples per category
and 77.8% for 30 samples.
5.4. Scalability w.r.t. the number of kernels
To test the scalability of UFO-MKL we tested it on
the Oxford Flower data set (Nilsback & Zisserman,
2006)4 , generating 1400 kernels. The task of thedataset is to classify 17 different flower categories.
Each class has 80 images with predefined train andtest splits. Precomputed distance matrices for 7 different features are available. For each precomputed
matrix, we generates 200 kernels using exp(−γ −1 · d)with 200 different γ values in the range between 0.01
and 100. Figure 3 (top) reports the results for varying
number of kernels. Our algorithm outperforms all theother baseline in term of both accuracy and efficiency.
4

www.robots.ox.ac.uk/~vgg/research/flowers/

Flower (3 splits, 680 training samples)
84

classification rate

8280

UFO−MKL: 1400 kernels
UFO−MKL: 500 kernels
UFO−MKL: 100 kernels
OBSCURE: 1400 kernels
OBSCURE: 500 kernels
OBSCURE: 100 kernels
SILP: 1400 kernels
SILP: 500 kernels
SILP: 100 kernels
MC−MKL: 1400 kernels
MC−MKL: 500 kernels
MC−MKL: 100 kernels

78
76
74
72
10

2

3

1500

10

83
UFO−MKL (α=1.0e−4)
UFO−MKL (α=5.0e−4)
UFO−MKL (α=1.0e−3)
UFO−MKL (α=2.5e−3)
UFO−MKL (α=5.0e−3)
UFO−MKL (α=7.5e−3)
UFO−MKL (α=1.0e−2)
UFO−MKL (α=2.0e−2)

1000

500

82
81
80
79
78

0

4

10
training time (seconds)

classification rate

number of non−zero kernel mixtures

We start by comparing the convergence rates of UFOMKL and OBSCURE, which is the state-of-art pnorm multiclass MKL solver. The training time of the
OBSCURE algorithm is proportional to q/λ, where
1/p + 1/q = 1. Therefore, when a sparse solution isneeded, the algorithm becomes slow because q becomesbig. For a fair comparison, we first set q = 2 log F in
OBSCURE, and α = 0 in UFO-MKL, so that theirregularizers become exactly the same. Figure 2 (top)shows the value of the objective function as a functionof the training time. OBSCURE is faster in the beginning because its first stage is an online algorithm,
which quickly determines the region of the space where
the optimal solution lives. UFO-MKL, after ≈ 1minof computation, converges faster than OBSCURE. We
think that this is due to the simpler algorithm that
does not require a scaling after each update, hence
each iteration in UFO-MKL is faster.

2

10

3

10
training time (seconds)

4

10

77 1
10

UFO−MKL (α=1.0e−4)
UFO−MKL (α=5.0e−4)
UFO−MKL (α=1.0e−3)
UFO−MKL (α=2.5e−3)
UFO−MKL (α=5.0e−3)
UFO−MKL (α=7.5e−3)
UFO−MKL (α=1.0e−2)
UFO−MKL (α=2.0e−2)
2

10

3

10

number of non−zero kernel mixtures

Figure 3. Running time performance of UFO-MKL andother baseline approaches w.r.t. different number of kernels and varying values of α.

UFO-MKL is 3-5 times faster compared to OBSCURE,
which is again due to the factor that OBSCURE does
not get a real sparse solution. It suggests that UFOMKL is more suitable for feature selection tasks whena lot of kernels are available. Figure 3 (bottom left)
shows the number of selected kernels and the accuracy
obtained by varying values of α, using the same number of epochs. We see that a larger value of α, whichcorresponds to a sparser solution, leads to a slower
running time. Figure 3 (bottom right) reports the accuracy and the number of non-zero kernel weights of
the last solution when the algorithm stops. It can beseen that when the model becomes over sparse (largerα) the performance starts dropping. However smallvalues of α, which result in a denser model, do notcorrespond to higher accuracy, in fact many less discriminative kernels are included in the solution.

6. Conclusions and Discussion
This paper presents a new MKL formulation and a fastalgorithm, UFO-MKL, to solve it. It optimizes the objective function directly in the primal with a stochastic subgradient descent method. Experiments showthat UFO-MKL achieves state-of-art performance on
binary and multiclass classification problems. Our
approach is general, hence it can be applied to any

Ultra-Fast Optimization Algorithm for Sparse Multi Kernel Learning

convex loss function such as structure output prediction (Tsochantaridis et al., 2004), to have an MKL algorithm for structured output.

Lanckriet, G., Cristianini, N., Bartlett, P., and Ghaoui,
L. E. Learning the kernel matrix with semidefinite programming. J. Mach. Learn. Res., 5, 2004.

UFO-MKL has a guaranteed convergence rate, witha logarithmic dependence on the number of kernels.
Moreover the level of sparsity is tunable, and the solution found will always have exact zeros.

Martins, A. F. T., Smith, N. A., Xing, E. P., Aguiar, P.,
and Figueiredo, M. Online learning of structured predictors with multiple kernels. In Proc. of the 14th Intl
Conf. on Artificial Intelligence and Statistics, 2011.

Acknowledgments. FO and LJ acknowledge support by the Pascal Pump Priming Project SS2-Rob
funded by PASCAL2 NoE under EC grant FP7216886.

References
Bach, F. R., Lanckriet, G. R. G., and Jordan, M. I. Multiple kernel learning, conic duality, and the SMO, algorithm. In Proc. of the 21th Intl Conf. on Machine
Learning, 2004.
Boyd, S. and Vandenberghe, L. Convex Optimization.
Cambridge University Press, 2004.
Chapelle, O. Training a support vector machine in the
primal. Neural Comput., 19:1155–1178, 2007.
Cortes, C., Mohri, M., and Rostamizadeh, A. Two-stage
learning kernel algorithms. In Proc. of the 27th Intl
Conf. on Machine Learning, 2010.
Crammer, K. and Singer, Y. On the algorithmic implementation of multiclass kernel-based vector machines.
J. Mach. Learn. Res., 2:265–292, 2002.
Cristianini, N. and Shawe-Taylor, J. An Introduction
to Support Vector Machines and Other Kernel-Based
Learning Methods. Cambridge University Press, 2000.
Cristianini, N., Kandola, J., Elisseeff, A., and ShaweTaylor, J. On kernel-target alignment. In Adv. Neural.
Inform. Process Syst. 14, 2002.

Nath, J. S., Dinesh, G., Raman, S., Bhattacharyya, C.,
Ben-Tal, A., and Ramakrishnan, K. R. On the algorithmics and applications of a mixed-norm based kernel
learning formulation. In Adv. Neural. Inform. Process
Syst. 22, 2009.
Nilsback, M.-E. and Zisserman, A. A visual vocabulary forflower classification. In Proc. of IEEE Conf. on Computer Vision and Pattern Recognition, 2006.
Orabona, F.
DOGMA: a MATLAB Toolbox forOnline Learning, 2009.
Software available at
http://dogma.sourceforge.net.
Orabona, F., Jie, L., and Caputo, B. Online-batch strongly
convex multi kernel learning. In Proc. of IEEE Conf. on
Computer Vision and Pattern Recognition, 2010.
Rakotomamonjy, A., Bach, F. R., Canu, S., and Grandvalet, Y. SimpleMKL,. J. Mach. Learn. Res., 9:2491–
2521, 2008.
Shalev-Shwartz, S. and Kakade, S. M. Mind the duality
gap: Logarithmic regret algorithms for online optimization. In Adv. Neural. Inform. Process Syst. 21, 2008.
Shalev-Shwartz, S. and Tewari, A. Stochastic methods forl1 regularized loss minimization. In Proc. of the 26th Intl
Conf. on Machine Learning, 2009.
Shalev-Shwartz, S., Singer, Y., and Srebro, N. Pegasos:Primal Estimated sub-GrAdient SOlver for SVM. In
Proc. of the 24th Intl Conf. on Machine Learning, 2007.
Sonnenburg, S., Rätsch, G., Schäfer, C., and Schölkopf, B.
Large scale multiple kernel learning. J. Mach. Learn.
Res., 7:1531–1565, 2006.

Gehler, P. and Nowozin, S. On feature combination for
multiclass object classification. In Proc. of IEEE Intl
Conf. on Computer Vision, 2009.

Tomioka, R. and Suzuki, T. Sparsity-accuracy trade-off in
MKL, 2010. URL http://arxiv.org/abs/1001.2615.

Hazan, E., Agarwal, A., and Kale, S. Logarithmic regret algorithms for online convex optimization. Machine
Learning, 69(2-3):169–192, 2007.

Tsochantaridis, I., Hofmann, T., Joachims, T., and Altun,
Y. Support vector machine learning for interdependentand structured output spaces. In Proc. of the 21th Intl
Conf. on Machine Learning, 2004.

Jie, L., Orabona, F., Fornoni, M., Caputo, B., and CesaBianchi, N. OM-2: An online multi-class multi-kernel
learning algorithm. In Proc. of the 4th IEEE Online Learning for Computer Vision Workshop (in CVPR
2010), 2010.
Kakade, S., Shalev-Shwartz, S., and Tewari, A. On the duality of strong convexity and strong smoothness: Learning applications and matrix regularization. Technicalreport, TTI, 2009.
Kloft, M., Brefeld, U., Sonnenburg, S., Laskov, P., Müller,
K.-R., and Zien, A. Efficient and accurate lp-norm multiple kernel learning. In Adv. Neural. Inform. Process
Syst. 22. 2009.

Vishwanathan, S. V. N., Sun, Z., Theera-Ampornpunt, N.,
and Varma, M. Multiple kernel learning and the SMO
algorithm. In Adv. Neural. Inform. Process Syst., 2010.
Xiao, L. Dual averaging methods for regularized stochastic
learning and online optimization. J. Mach. Learn. Res.,
11:2543–2596, October 2010.
Xu, Z., Jin, R., King, I., and Lyu, M. R. An extended
level method for efficient multiple kernel learning. In
Adv. Neural. Inform. Process Syst. 21, 2008.
Zien, A. and Ong, C. S. Multiclass multiple kernel learning.
In Proc. of the 24th Intl Conf. on Machine Learning,
2007.