Online-Batch Strongly Convex Multi Kernel Learning
Francesco Orabona∗
Università degli Studi di Milano
orabona@dsi.unimi.it

Luo Jie
Idiap Research Institute
EPF Lausanne

Barbara Caputo
Idiap Research Institutebcaputo@idiap.ch

jluo@idiap.ch

Abstract

considerable attention [8, 13, 24]. However most emphasis has been put so far on their accuracy, and recent findings seem to indicate that current MKL algorithms do not
improve much over the naive baseline of averaging all thekernels [9].

Several object categorization algorithms use kernel
methods over multiple cues, as they offer a principled approach to combine multiple cues, and to obtain state-of-theart performance. A general drawback of these strategies is
the high computational cost during training, that prevents
their application to large-scale problems. They also do notprovide theoretical guarantees on their convergence rate.
Here we present a Multiclass Multi Kernel Learning(MKL) algorithm that obtains state-of-the-art performancein a considerably lower training time. We generalize thestandard MKL formulation to introduce a parameter that allows us to decide the level of sparsity of the solution. Thanks
to this new setting, we can directly solve the problem in the
primal formulation. We prove theoretically and experimentally that 1) our algorithm has a faster convergence rate as
the number of kernels grow; 2) the training complexity islinear in the number of training examples; 3) very few iterations are enough to reach good solutions. Experiments on
three standard benchmark databases support our claims.

Almost every interesting categorization problems havemore than two classes, and most of the MKL algorithms [12, 18, 22] solves the multiclass problem by decomposing it into multiple independent binary classification
tasks (except [27]). However, recent evidence [9] seems
to suggest that a principled multiclass formulation (such as
those in [9, 23, 27]) achieves better performance, at least on
sparse problems using l1 regularization. Moreover, to ourknowledge, none of the MKL algorithms [12, 18, 22] provides theoretical guarantees on their convergence rate. In
practice, the learning process is usually stopped early, before reaching the optimal solution, based on the common
assumption that it is enough to have an approximate solution of the optimization function. Considering the fact thatcurrent MKL algorithms are solved based on their dual representation, this might mean being stopped far from the optimal solution [10]. Last but not least, scalability is also
very important for many real world applications.

1. Introduction

The contribution of this paper is a Multiclass MKL algorithm that has a guaranteed and fast convergence rate tothe optimal solution. We also generalize the MKL learning
problem, adding a parameter to tune the level of sparsity inthe kernel domain. We show experimentally that aiming atsparsity, as in the original MKL formulation, is not always
the optimal strategy. Our algorithm has a training time that
depends linearly on the number of training examples, with aconvergence rate sub-linear in the number of kernels used.
At the same time, it achieves state-of-the-art performanceon standard benchmark databases. The algorithm is basedon a stochastic sub-gradient descent algorithm in the primal objective formulation. Minimizing the primal objectivefunction directly results in a convergence rate that is fasterand provable, rather than optimizing the dual objective. We
show that by optimizing the primal objective function directly, we are able to solve the multiclass formulation effi-

Categorization is one of the most challenging problems
in computer vision today. Object categories present a widevisual variability within each class. This, coupled withrobustness issues (e.g. changes in illumination, occlusion,
clutter), makes it unclear how to build general models suitable for all categories. Because of this, a dominant approachis to learn instead what distinguishes them, by using highly
discriminative and robust features combined with machinelearning techniques [8, 9, 13, 16, 24, 25]. In particular thishas been recently translated into Support Vector Machine(SVM) based classifiers combined with kernels over multiple cues [2, 8, 9, 13, 24, 25]. Results obtained by thesemethods on various benchmark databases represent the current state-of-the-art in object categorization. Among them,Multi Kernel Learning (MKL) approaches have attracted∗ Work done while at Idiap Research Institute, Martigny, Switzerland

1

ciently, with a running time which is linear to the numberof classes. We can stop the algorithm after few iterations,while still retaining a performance close to the optimal one.
We call this algorithm OBSCURE, Online-Batch Strongly
Convex mUlti keRnel lEarning.

1.1. Multiple Cues and Kernels
Consider the task of image classification with M classes,
F different cues and N training instances {xi }N
i=1 drawn
from an unknown fixed probability distribution. We wantto learn a score function s(·, ·) that best predicts the class ŷ
for any future sample x drawn from the same distribution,
where the predicted class is the one with the highest scoreŷ(x) = argmax s(x, y) .

(1)

y∈Y

This score function should be learned using all the F different cues, to gain robustness and performance.
Some of the methods addressing this task are based on a
two-layers structure [9, 16]. A classifier is trained for eachcue and then their outputs are combined by another classifier. Even if this strategy has recently received attention in
the computer vision community, this kind of approach is theoldest and dates back to the seminal work of Wolpert [26].
They use Cross-Validation (CV) methods to create the training set for the second layer [9, 26]. Hence they have a runtime of about K+1 times the training of a single classifier,such as support vector machine (SVM), where K is the number of folds of the CV. This method is currently considered
the state-of-art method for image classification tasks [9].
Another interesting strategy uses a one-layer architecture, such as the MKL [14, 18, 22, 24, 27]. Using the theoryof kernels, one solves a joint optimization problem while
also learning the optimal weights for combining the kernels,
with each cue corresponding to a kernel. The optimization
problem is similar in all these approaches. This approachis theoretically founded, plus it consists of a unique optimization problem. However solving it is more complex thantraining, e.g., a single SVM classifier. Another issue is thatcurrent MKL approaches do not scale well to the numberof training examples and number of classes. For example,
the SILP algorithm [22, 27] depends polynomially on thenumber of training examples and number of classes with an
exponent of ∼ 2.4 and ∼ 1.7 respectively. For the otheralgorithms these dependencies are not clear.
From a theoretical point of view, if we consider a twolayers architecture with the first layer composed by kernel
classifiers, and a linear classifier in the second stage, the two
approaches are very similar. In both cases the final prediction function is written asŷ(x) = argmax
y∈Y

F
X
j=1

βyj sj (x, y),(2)where βyj are the weights learned by the one-layer or twolayers framework, and sj is the score function for each kernel. Therefore the two formulations are essentially equivalent, with differences given only by the specific training procedures used. In both methods a regularizer that favors theselection of only a subset of the kernels is used [1, 9, 22, 24].
The main contribution of this paper is showing that the
one-layer formulation, beside being more principled, canalso achieve a comparable performance and a considerably
lower training time than state-of-the-art two-layers architectures. We propose a p-norm version of the standard MKL
algorithm, and we minimize it with a two stages algorithm.
The first one is an online initialization procedure that determines quickly the region of the space where the optimal
solution lives. The second stage refines the solution foundby the first stage. Differently from the other methods, ouralgorithm solves the optimization problem directly in the
primal formulation, in both stages. Using recent approaches
in optimization theory, the algorithm takes advantage of theabundance of information to reduce the training time [21].
In fact, we show that the presence of a large number of kernels helps the optimization process instead of hindering it,
obtaining, theoretically and practically, a faster convergence
rate with more kernels.
The rest of the paper presents the theory and the experimental results supporting our claims. Section 2 revises thebasic definitions of MKL and generalizes it to p-norm formulation. Section 3 presents the theory and algorithm of
OBSCURE, while Section 4 reports experiments on categorization tasks.

2. p-norm Multi Kernel Learning
In this section we first introduce formally the MKL
framework and its notation, then its p-norm generalization.

2.1. Definitions
Notations. Let {xi , yi }N
i=1 , with N ∈ N, xi ∈ X andyi ∈ Y = {1, · · · , M }, M > 2, be the training set. We
indicate matrix and vectors with bold letters. A bar, e.g.
w̄, denotes the vector formed by the concatenation of the F
vectors wj , hence w̄ = [w1 , w2 , · · · , wF ].
Multi-class Classifier. A common approach to multiclassclassification is to use joint feature maps φ(x, y) on data X
and labels Y [23]. The function sj will be defined assj (x, y) = wj · φj (x, y),(3)where wj is a hyperplane1 . The functions φj (x, y) map
the samples into a high, possibly infinite, dimensional
space. With multiple cues, we will have F functions
1 For simplicity we will not use the bias, it can be easily added by modifying the kernel definition.

φj (·, ·), j = 1, · · · , F . This will also define F kernels
K j ((x, y), (x′ , y ′ )) as φj (x, y) · φj (x′ , y ′ ). This definition
includes the case of training M different hyperplanes, one
for each class. Indeed φj (x, y) can be defined as

We will now generalize this formulation to group-norms.
Using the notation defined above, we can rewrite (7) asminw̄

φj (x, y) = [0, · · · , 0, φ′j (x), 0, · · · , 0],| {z }(4)ywhere φ′j (·) is a transformation that depends only on
data. Similarly w will be composed by M blocks,[w1 , · · · , wM ]. Hence, by construction, w · φj (x, r) =wr · φ′j (x). According to the defined notation, φ̄(x, y) =[φ1 (x, y), · · · , φF (x, y)].
Loss Function.

We define a multi-class loss function [23]ℓ (w, x, y) = max|1 − w̄ · (φ̄(x, y) − φ̄(x, y ′ ))|+ , (5)′y 6=ywhere |t|+ is max(t, 0). This loss function is convex and it
upper bounds the multi-class misclassification loss.
Norms and dual norms. A generic norm of a vector w isindicated by kwk, its dual norm is indicated by kwk∗ . Forw ∈ Rd and p ≥ 1, we denote by kwkp the p-norm of w,
Pdi.e., kwkp = ( i=1 |wi |p )1/p . The dual norm of k · kp is
k · kq , where p and q satisfy 1/p + 1/q = 1. In the following
p and q will always satisfy this relation.
Group Norm. It is possible to define a (2, p) group normkw̄k2,p on w̄ as
kw̄k2,p := kw1 k2 , kw2 k2 , · · · , kwF k2 p , (6)that is the p-norm of the vector of F elements, formed by
2-norms of the vectors wj . The dual norm of k · k2,p isk · k2,q [11].

2.2. Multi Kernel Learning

The MKL optimization problem was first proposed in [1]and extended to multiclass in [27]. It can be written as

2
F
N
1 X
λ X
kwj k2  +
min
ξi
wj 2
N i=1
j=1

s.t. w̄ · (φ̄(xi , yi ) − φ̄(xi , y)) ≥ 1 − ξi , ∀i, y 6= yi . (7)This same formulation is used in [1, 22], while in [18]the proposed formulation is slightly different, although it
is proved to be equivalent. Note that we weight the regularization term by λ and divide the loss term by N , insteadof the more common formulation with only the loss term
weighted by a parameter C. Our choice greatly simplifies
the math of our algorithm. The two formulations are fully1.
equivalent when setting λ = CNN
1 X
λkw̄k22,1 +ℓ (w̄, xi , yi ) ,
2
N i=1

(8)

where w̄ = [w1 , w2 , · · · , wF ]. The (2, 1) group norm isused to induce sparsity in the domain of the kernels. Thismeans that the solution of the optimization problem will select a subset of the F kernels. However, even if sparsity canbe desirable for specific applications, it could bring to a decrease in performance. Moreover the problem in (8) is notstrongly convex [11], so its optimization algorithm is rather
complex and its rate of convergence is usually slow [1, 22].
We propose to generalize the optimization problem, using a generic group norm
N
λ
1 X
2
min
kw̄k2,p +ℓ (w̄, xi , yi ) ,
w̄
2
N i=1

(9)

where 1 < p ≤ 2. We define f (w̄) = λ2 kw̄k22,p +PN
1∗i=1 ℓ (w̄, xi , yi ) and w̄ equals to the optimal soluN∗tion of (9), w̄ = arg minw̄ f (w̄). The added parameter p
will allow us to decide the level of sparsity of the solution.
In fact it is known that the 1-norm favors sparsity, and here
the 1-norm favors a solution in which only few hyperplanes
have a norm different from zero. Moreover this new formulation has the advantage of being λ/q-strongly convex [11].
Strong convexity is a key property to design fast batch andonline algorithms: the more a problem is strongly convex
the easier it is to optimize it [11, 19]. Many optimization
problems are strongly convex, as the SVM objective function. When p tends to 1, the solution gets close to the sparse
solution obtained solving the problem in (7), but the strong
convexity decreases. When p equals to 2, it is equivalent tousing a single kernel equal to the sum of all the kernels. Recently a different p-norm MKL problem has been also proposed in [12], that allows non-sparse solutions. However,their algorithm did not take advantage of nice properties ofthe strong convexity for the optimization process. In thenext section, we will show how to use the strong convexity
to design a fast algorithm to solve (9).

3. The OBSCURE Algorithm
Our basic optimization tool is the framework developedin [19, 20]. It is a general framework to design and analyze
stochastic sub-gradient descent algorithms for any strongly
convex function. At each step the algorithm takes a random sample of the training set and calculates a sub-gradientof the objective function evaluated on the sample. Then it
performs a sub-gradient descent step with decreasing learning rate, followed by a projection of the solution inside
the space where the solution lives. The algorithm Pegasos,

Algorithm 1 OBSCURE stage 1 (online)
1: Input: q, η
2: Initialize: θ̄ 1 = 0, w̄ 1 = 0
3: for t = 1, 2, . . . , T do
4:
Sample at random (xt , yt )5:
ŷt = argmax w̄ t · φ̄(xt , y)
y6=yt

6:
7:
8:
9:

z̄ t = φ̄(xt , yt ) − φ̄(xt , ŷt )if ℓ(w̄ t , xt , yt ) > 0 then θ̄ t+1 = θ̄ t + η z̄ telse θ̄ t+1 = θ̄ t
«q−2
„ j
kθ
k2
w jt+1 = 1q kθ̄ t+1k
θ jt+1 , ∀j = 1, · · · , F
t+1 2,q

10: end for
11: return θ̄ T +1q, w̄ T +1
12: return R =2kw̄ T +1 k22,p + λN

PN

i=1 ℓ (w̄ T +1 , xi , yi )Algorithm 2 OBSCURE stage 2 (batch)
1: Input: q, θ̄ 1 , w̄ 1 , R, λ
2: Initialize: s0 = 0
3: for t = 1, 2, . . . , T do
4:
Sample at random (xt , yt )5:
ŷt = argmax w̄ t · φ̄(xt , y)
y6=yt

6:
7:
8:
9:
10:
11:
12:
13:

if ℓ(w̄ t , xt , yt ) > 0 then z̄ t = φ̄(xt , yt ) − φ̄(xt , ŷt )else z̄ t = 0
dt = λt + st−1 r!
st = st−1 + 0.5( λ kθ̄ t k2,q +kz̄ t k2,q )2

d2t + q q

R2

− dt

q
ηt = λt+st
θ̄ t+ 1 = (1 − ληq t )θ̄ t + ηt z̄ t2“”
θ̄ t+1 = min 1, qR/kθ̄ t+ 1 k2,q θ̄ t+ 1
2
2
„ j
«q−2
kθ t+1 k2
jj1
w t+1 = q kθ̄ k
θ t+1 , ∀j = 1, · · · , F
t+1 2,q

14: end forbased on this framework, is the current state-of-art solver
for linear SVM [20, 21].
Given that the (2, p) group norm is strongly convex, we
could use this framework to design an efficient MKL algorithm. It would inherit all the properties of Pegasos [20, 21].
In particular the convergence rate, and hence the training
time, would be proportional to λq . Although in general thisconvergence rate can be quite good, it becomes slow when
λ is small and/or q is big. Moreover it is common knowledge that in many real-world problems, particularly in visual learning tasks, the best setting for λ is very small, or
equivalently C is big (the order of 102 − 103 ). Notice that
this is a general problem. The same problem also exists inthe other SVM optimization algorithms such as SMO andsimilar approaches [10], as their training time also depends
on the value of the parameter C.
Do et al. [6] proposed a variation of the Pegasos algorithm called proximal projected sub-gradient descent. This

formulation has a better convergence rate for small valuesof λ, while retaining the fast convergence rate for big valuesof λ. A drawback is that the algorithm needs to know in advance an upper bound on the norm of the optimal solution.
In [6] the authors proposed an algorithm that estimates thisbound while training, but it gives a speed-up only when thenorm of the optimal solution w̄∗ is small. This is not thecase in most of the MKL problems for categorization tasks.
Our OBSCURE algorithm takes the best of the two solutions. We first extend the framework of [6] to the generic
non-Euclidean norms. Then we solve the problem of theupper bound of the norm of the optimal solution using an
new online algorithm. This takes advantage of the characteristic of the MKL task and quickly converges to a solution
close to the optimal one. Hence OBSCURE is composedby two steps: the first step is a fast online algorithm (Algorithm 1), used to quickly estimate the region of the space
where the optimal solution lives. The second step (Algorithm 2) starts from the approximate solution found by the
first stage, and exploiting the information on the estimatedregion, it uses a stochastic proximal projected sub-gradientdescent algorithm.
The following theorem2 gives a theoretical guarantee on
the convergence rate of OBSCURE to the solution of (9).
Theorem 1. Suppose that kφj (xt , yt )k2 ≤ 1, ∀j =1, · · · , F, t = 1, · · · , N . Let 1 < p ≤ 2, δ √∈ (0, 1), R thevalue returned by the first stage, and c = 2F 1/q + λR.
Then with probability at least 1 − δ over the choices of therandom samples we have that after T iterations of the 2ndstage of the OBSCURE algorithm, the difference between
f (w̄T ) and the optimal solution of (9), f (w̄∗ ), is less than
 √ √

√ √
c q 1 + log T 4R
c q 1 + log T
min
,√
.
δ
λT
T
Moreover if the problem is linearly separable by a hyperplane ū and the first stage is run until convergence, R is
2
less than 2(1 + ηF q )kūk2,p .
The theorem first shows that a good estimate of R can
speed-up the convergence of the algorithm. In particular if the first term is dominant, the convergence rate isTO( q log
second term is predominant, the converλT ). If the √T
R √gence rate is O( q log), so it becomes independent fromT
λ (i.e. independent from C). The algorithm will always optimally interpolate between these two different rates of convergence. As said before, the rate of convergence depends
on p, through q. When p tends to 1, the solution tends tothe sparse one of (7), with a worst rate. However in the experiment section we show that the best performance is notalways given by the sparsest solution. Moreover Theorem 1
2 For an extended version of this paper with proofs,
http://francesco.orabona.com/papers/obscure-proofs.pdf.

seealso shows that, when p is close to 1, the convergence rate
has a sublinear dependency on the number of kernels, F ,and if the problem is linearly separable it can have a fasterconvergence rate using more kernels. We will explain thisformally in Section 3.2.
The training time of OBSCURE is proportional to thenumber of steps given by Theorem 1 multiplied by the complexity of each step. This in turn is dominated by the prediction (line 5 in Algorithms 1 and 2), that has complexity
O(N F M ). Note that this complexity is common to any
other similar algorithm, and it can be reduced using methods like kernel caching [5].
In the following we introduce the necessary mathematical tools to be able to derive OBSCURE and its theorem.

3.1. Batch p-norm MKL
We first state a Lemma that is a generalization of Theorem 1 in [6] to general norms, using the framework in [19].
We need two additional definitions. Given a convex function f : S → R, its Fenchel conjugate f ∗ : S → R is
defined as f ∗ (u) = supv∈S (v · u − f (v)). A vector x is
a sub-gradient of a function f at v, indicated with ∂f (v), if∀u ∈ S, f (u) − f (v) ≥ (u − v) · x.
Lemma 1. Let h(·) = α2 k · k2 be a 1-strongly convex function w.r.t. a norm k · k over S. Assume that for all t, gt (·)
is a σ-strongly convex function w.r.t. h(·), and kz t k∗ ≤ Lt .
Then for any u : ku − wt k ≤ 2R, and for any sequence of
non-negative ξ1 , . . . , ξT , Algorithm 3 achieves the following bound for all T ≥ 1,
#
"
T
T
X
X
L2t
2
Pt
.
4ξt R +
(gt (wt ) − gt (u)) ≤ξiσt + i=1t=1
t=1αWith this Lemma we can now design stochastic subgradient algorithms. In particular, setting k · k2,p as norm,h(w̄) = 2q kw̄k22,p , and gt (w̄) = λq h(w̄) + ℓ (w̄, xt , yt ), we
obtain Algorithm 2 that solves the p-norm MKL problem in(9). In particular lines 6-7 correspond to the calculation of
the sub-gradient of the multiclass loss function (5). The updates are done on the dual variables θ̄ t , in lines 11-12, thatare transformed into w̄t in line 13.
Note also that Algorithm 2 can start from any vector,
while this is not possible in the Pegasos algorithm whereat the very first iteration the starting vector is multiplied by
0 [20]. The parameter R is basically an upper bound on
the norm of the optimal solution, i.e. R ≥ kw̄∗ k2,p . In thenext Section we show how to initialize this algorithm and to
calculate R in an efficient way.

3.2. Initialization through an online algorithm
In Theorem 1 we saw that if we have a good estimate ofR, the convergence rate of the algorithm can be much faster.

Algorithm 3 Proximal projected sub-gradient descent
1: Input: R, σ, w 1 ∈ S
2: Initialize: s0 = 0
3: for t = 1, 2, . . . , T do
4:
Receive gt
5:z t = ∂gt (w t )r(ασt+st−1 )2 +αLt−(ασt+st−1 )R2

st = st−1 +2ηt = (σt + st /α)−1
w t+1 = ∇h∗ (∇h(w t ) − ηt z t )9: end for

6:
7:
8:

Moreover starting from a good solution could speed-up thealgorithm even more.
We propose to initialize Algorithm 2 with an online algorithm. Algorithm 1 is the online version of problem (9)and it is derived using Corollary 7 in [11]. It is similar to
the 2p-norm matrix Perceptron in [3], but it overcomes the
disadvantage of being used with the same kernel on eachfeature. As in [3], for Algorithm 1 it is possible to provea relative mistake bound. We omit the details for lack ofspace, a future longer version of this work will include it.
We can run it just for few iterations and then evaluate its
norm and its loss. In Algorithm 1 R is then defined asq
PN
2
R := kw̄ T +1 k22,p + λN
i=1 ℓ (w̄ T +1 , xi , yi )
q
PN
∗
2
∗
≥ kw̄ ∗ k22,p + λN
i=1 ℓ (w̄ , xi , yi ) ≥ kw̄ k2,p .

(10)

So at any moment we can stop the algorithm and obtain an
upper bound on kw̄∗ k2,p .
If the dimension of the space induced by the F kernles isbig enough, it is very likely that the classification problem islinearly separable. When this is the case, we can prove that
Algorithm 1 will converge to a solution which has null loss
on each training sample, in a finite number of steps. Morespecifically we can state the following Theorem.
Theorem 2. Suppose that kφj (xt , yt )k2 ≤ 1, ∀j =1, · · · , F, t = 1, · · · , N , and 1 < p ≤ 2. If the problem(9) is linearly separable by a hyperplane ū, then the
Algorithm 1 will converge to a solution in a finite num2
ber of steps less than 2q(1/η + F q )kūk22,p . Moreover2

the returned value of R will be less than 2(1+ηF q )kūk2,p .
From the theorem it is clear the role of η: a bigger value
will speed up the convergence, but will decrease the qualityof the estimate of R. So η governs the trade-off between
speed and precision of the first stage. If p is close to 1,
the dependency on the number of kernels in this theorem
is strongly sublinear, moreover increasing the number ofkernels to F ′ > F , we have that kūk22,p will most likely
decrease or remain constant. This means that we expect Algorithm 1 to converge, in a number of steps that is almostFlowers (40 examples per class, 7 kernels)

10

80

10

70
60
OBSCURE
Pegasos

50

0

−1

10

−2

10

SimpleMKL

−3

10

LP−β
0

1

10

−4

10

The Oxford flowers dataset [17] contains 17 different
categories of flowers. Each class has 80 images withthree predefined splits (train, validation and test). The authors also provide seven precomputed distance matrices4 .
These distance matrices are transformed into kernel usingexp(−γ −1 · d), where γ is the mean of the pairwise distances and d is the distance between two examples. We
used a value of p equal to 1.05, found through CV.
We have implemented an extended version of the original Pegasos algorithm [20, 21] for problem (9). We firstcompare the running time performance between OBSCURE
and Pegasos. Their generalization performance on the testing data (Figure 1(Left)) as well as the value of the objective function (Figure 1(Right)) are shown in Figure 1. In
the same Figure, we also present the results obtained using
other combination methods: SILP [22], SimpleMKL [18]and LP-β [9]. The cost parameter is selected from the range
C ∈ {1, 10, 100, 1000} for MKL methods. We see that OBSCURE converges much faster compared to Pegasos. This
proves that, as stated in Theorem 1, OBSCURE has a better
convergence rate than Pegasos. All the feature combination methods achieve similar results on this dataset. LP-β
is order of magnitudes faster as it uses an efficient standard
SVM solver [5].

4.2. Caltech-101 datasets
The Caltech-101 [7] dataset is a standard benchmark
dataset for object categorization. Here we followed the experimental setup originally proposed and widely used in the
3 Code available at http://dogma.sourceforge.net/
4 www.robots.ox.ac.uk/

˜vgg/research/flowers/

4

10

traininig time (seconds)

4.1. Oxford flowers

OBSCURE
Pegasos

10

SLIP

10

In this section we test OBSCURE on the Oxford flowers [17], Caltech-101 [7] and MNIST [15] datasets. Although our MATLAB implementation of the algorithm3 is
not optimized for speed, it is already possible to observe
the advantage of the low runtime complexity. This is particularly evident when training on datasets containing large
numbers of categories and lots of training samples. In all
our experiments, the parameter η is fixed at 2, and p is chosen from the set {1.01, 1.05, 1.10, 1.25, 1.50, 1.75, 2}. The
1regularization parameter λ is set through CV, as CN, whereC ∈ {1, 10, 100, 1000}.

Flowers (40 examples per class, 7 kernels)

140

4. Experiments

290

objective function

classification rate

independent on F and in some cases even decreasing in F .
The same consideration holds for the value of R returnedby the algorithm, that can decrease when we increase thenumber of kernels. A smaller value of R will mean a fasterconvergence of the second stage. We will confirm this statement experimentally in Section 4.

5

10

number of iterations

Figure 1. Comparison of performance on Oxford flowers dataset.

literature. In our experiments, we used the pre-computedfeatures and kernels of [9], with the same training and test
split5 . This allows us to compare against them directly. Following that, we report results using all 102 classes of theCaltech-101 dataset using five splits. There are five different image descriptors, using different setup of parametersand computed at different scales. It results in a total of 39
kernels. Note that, as they are derived from 5 features only,
some of them might be redundant. For brevity, we omit thedetails of the features and kernels that can be found in [9].
Figure 2 shows the behavior of our algorithm using different values of the parameter p (Figure 2(Left)), different
number of kernels (Figure 2(middle)) and the running time
under different size of training examples (Figure 2(right)).
The dashed line in Figure 2(left & middle) corresponds to theresults obtained by the first online stage of the OBSCURE
algorithm. It can be observed from the figures that:a). [Figure 2(Left)] The online step of OBSCURE achieves
a performance close to the optimal solution in a training time order of magnitudes faster (101 to 103 ). Whenp is large (i.e. q is small) the online stage converges
even faster. This is consistent with Theorem 2.
b). [Figure 2(Left)] By changing p, it is possible to improve
performance. As stated before, when p tends to 1, thesolution gets close to the sparse solution. In particularhere 3 kwj k2 (out of 4) approach 0. When p equals 2,
we obtain a dense solution, that corresponds to use thesum of all the kernels. Although some of the kernels
may contain redundant information, all of them may be
informative for classification. Thus imposing sparsity
on them does not always help increasing performance.
Hence the optimal p here is 1.10 − 1.25.
c). [Figure 2(Middle)] OBSCURE has a better converges
rate when there are more kernels, as stated in Theorem 2. That is, the algorithm achieves a given accuracy
in less iterations when more kernels are given.
d). [Figure 2(Right)] We can see that the algorithm converges quite fast to the optimal solution. Using 15 examples per class, the run time is similar to the runtimeof LP-β (about 24 mins). When the number of training
5 www.vision.ee.ethz.ch/

˜pgehler/projects/iccv09/

Caltech−101 (4 kernels, 30 training examples)

Caltech−101 (p=1.01, 30 training examples)

58

78

56

76

70
60

50
48

classification rate

74

52

classification rateclassification rate

54

Caltech−101 (p=1.01, 39 kernels)
80

72
70
68

50
40
30

46
p=1.01p=1.10p=1.25p=1.50p=1.75p=2.00

44
42
40

1

2

10

3

10

10

66
64
62 4
10

5

10

6

10

training time (seconds)

10

number of iterations

OBSCURE: 5 examples
OBSCURE 15 examples
OBSCURE 30 example
LP−β: 15 examples
SILP: 15 examples
LP−β: 30 examples
SILP: 30 examples

20

5 kernels
10 kernels
20 kernels
30 kernels
39 kernels

0 −1
10

0

10

1

10

2

10

3

10

4

10

training time (seconds)

Figure 2. Behaviors of the OBSCURE algorithm on Caltech-101 dataset: (Left) the effect of different value of p, using four PHOG [2]kernels computed at different spatial pyramid level, as similar experiment performed in [9]; (Middle) the effect of different number ofkernels randomly sampled from the 39 kernels; (Right) running time for different number of training examples using all the 39 kernels.

Caltech−101 (p=1.01, 5−30 training examples )80
75classification rate

70
65
60
55
average kernel (39 kernels)
average kernel (5 kernels)
LP−β (39 kernels)
MKL (SILP, 39 kernels)
MKL (SILP, 5 kernels)
OBSCURE (39 kernels)
OBSCURE (5 Kernels)

50
45
40

5

10

15

20

25

30

# training examples

Figure 3. Performance comparison on Caltech-101 using different
combination methods.

examples increases to 30, our algorithm has an advantage over LP-β, that takes about 121 mins.
In Figure 3 we report the results obtained using different
combination methods. The best results for OBSCURE wereobtained when p is at the smallest value (1.01). This is probably because among these 39 kernels many were redundantor not discriminative enough. For example, the worst single kernel achieves only an accuracy of 13.5% ± 0.6 whentrained using 30 images per category, while the best single kernel achieves 69.4% ± 0.4. Thus, sparser solutions
are to be favored. We see also that our method achieves
performance comparable to the state-of-art (LP-β, [9]), andoutperforms the other MKL (SILP) methods. One possible reason may be the one-vs-all multiclass extension usedin the MKL algorithm. The sparse MKL algorithm maychoose different subset of kernels in different independent
binary classification tasks, which may introduce a bias onsome classes in the final decision process. However, notethat although our algorithm obtains a solution close to thesparse one, it will never reach a completely sparse solution.
This may be one of the reasons for the gap in performance
between OBSCURE and LP-β [9]. However, this may not
be critical, since usually in practice all used features/kernels
are informative. Non-informative/duplicate features are unlikely to be included in a real system. We did a simple testby selecting five kernels from the five different families offeatures [9] which achieve low leave-one-out (LOO) error
using 30 training examples per class. It can be done automatically using LS-SVM, which has a closed form solution for LOO error estimation [4]. The results as wellas the performance of the averaging of these five kernels
are also shown in Figure 3. We see that the algorithm improves slightly over the previous one. This suggests thatOBSCURE as well as SILP, when provided with discriminative features, could increase performance even further.
It also seems to indicate that there is a margin to improve
the regularization used in MKL methods, as currently morekernels do not necessarily transform into better accuracy.

4.3. MNISTIn the last experiment we use the MNIST [15] dataset of
handwritten digits. The dataset has a training set of 60,000
gray-scale 28x28 pixel digit images for training and 10,000
images for testing. We cut the original digit image into foursquare blocks (14 × 14) and obtained an input vector fromeach block. We used three kernels on each block: a linear
kernel, a polynomial kernel and a RBF kernel, resulting in
12 kernels. Figure 4 shows the generalization performanceon the test set achieved by OBSCURE over time, for various sizes of training set. We see that OBSCURE quickly
converges to the best performance. It also shows that thetime to reach the optimum is approximately linear in thenumber of training samples. The SVM performance using
averaging kernel and the best kernel is also plotted. Noticethat in the figure we only show the results of up to 20,000
training samples for the sake of comparison, otherwise weMNIST (p=1.10)
25

error rate

20

OBSCURE N=1000
OBSCURE N=5000
OBSCURE N=10000OBSCURE N=20000
SVM (1 vs. ALL, best feature) N=20000
SVM (1 vs. ALL, averaging kernel) N=20000

15

10

5

0

−1

10

0

10

1

10

2

10

3

10

training time (seconds)

Figure 4. The generalization performance of MNIST dataset overdifferent size of training samples.

could not cache all the 12 kernels in memory. However, bycomputing the kernel “on the fly” we are able to solve the
MKL problem using the full 60,000 examples efficiently.

5. Conclusions and Discussion
This paper presents OBSCURE, a novel and efficientalgorithm for solving p-norm MKL. It uses a hybrid
two-stages online-batch approach, optimizing the objectivefunction directly in the primal with a stochastic subgradient descent method. Experiments show that OBSCURE
achieves state-of-art performance on multiclass classification problems. Furthermore, the solution found by the online stage is close to the optimal one for various tasks, while
being computed several orders of magnitude faster. Our approach is general, hence it can be applied to any other algorithm with a strongly convex regularizer [11]. For example
the framework can be very easily extended to solve otherproblems such as structure output prediction [23], to havean MKL algorithm for structured output.
OBSCURE has a faster convergence rate as the numberof cues/kernels grows. Thus we expect to achieve better
performance with more discriminative features. A simple
feature selection technique such as cross-validation could
already be beneficial. On the other hand, our results showthat non-sparse models might get better performance (inthe sense of accuracy and speed). This is in agreementwith recent findings in [12]. As a last remark, we noticethat the disadvantageous results of MKL methods, reported
in [9], may be because those algorithms does not have aproper multiple class formulation for the object categorization problems. By using our method, MKL can still be an
efficient machine learning tool for cue combination tasks.
Acknowledgments
The kernel matrixes of Caltech-101 were kindly provided by Peter Gehler, who we also thank for his useful comments. This work
was sponsored by the EU project DIRAC IST-027787. FO also acknowledges partial support by the PASCAL2 NoE FP7-216886.

References[1] F. R. Bach, G. R. G. Lanckriet, and M. I. Jordan. Multiple kernel
learning, conic duality, and the SMO, algorithm. In Proc. ICML,
2004. 2, 3
[2] A. Bosch, A. Zisserman, and X. Munoz. Representing shape with aspatial pyramid kernel. In Proc. CIVR, 2007. 1, 7
[3] G. Cavallanti, N. Cesa-Bianchi, and C. Gentile. Linear algorithms
for online multitask classification. In Proc. COLT, 2008. 5[4] G. Cawley. Leave-one-out cross-validation based model selection
criteria for weighted LS-SVMs. In Proc. IJCNN, 2006. 7[5] C. C. Chang and C. J. Lin.
LIBSVM: A Library for
Support Vector Machines, 2001.
Software available atwww.csie.ntu.edu.tw/˜cjlin/libsvm. 5, 6
[6] C. B. Do, Q. V. Le, and C.-S. Foo. Proximal regularization for online
and batch learning. In Proc. ICML, 2009. 4, 5
[7] L. Fei-Fei, R. Fergus, and P. Perona. One-shot learning of object
categories. IEEE PAMI, 28(4):594–611, 2004. 6[8] P. Gehler and S. Nowozin. Let the kernel figure it out: Principledlearning of pre-processing for kernel classifiers. In Proc. CVPR,
2009. 1
[9] P. Gehler and S. Nowozin. On feature combination for multiclassobject classification. In Proc. ICCV, 2009. 1, 2, 6, 7, 8
[10] D. Hush, P. Kelly, C. Scovel, and I. Steinwart. QP algorithms
with guaranteed accuracy and run time for support vector machines.
JMLR, 7, 2006. 1, 4
[11] S. Kakade, S. Shalev-Shwartz, and A. Tewari. On the duality ofstrong convexity and strong smoothness: Learning applications andmatrix regularization. Technical report, TTI, 2009. 3, 5, 8
[12] M. Kloft, U. Brefeld, S. Sonnenburg, P. Laskov, K.-R. Müller, andA. Zien. Efficient and accurate lp-norm multiple kernel learning. In
Proc. NIPS. 2009. 1, 3, 8
[13] A. Kumar and C. Sminchisescu. Support kernel machines for object
recognition. In Proc. ICCV, 2007. 1[14] G. Lanckriet, N. Cristianini, P. Bartlett, and L. E. Ghaoui. Learning
the kernel matrix with semidefinite programming. JMLR, 5, 2004. 2[15] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-basedlearning applied to document recognition. Proceedings of the IEEE,
86:2278–2324, 1998. 6, 7
[16] M. E. Nilsback and B. Caputo. Cue integration through discriminative accumulation. In Proc. CVPR, 2004. 1, 2
[17] M.-E. Nilsback and A. Zisserman. A visual vocabulary for flower
classification. In Proc. CVPR, 2006. 6[18] A. Rakotomamonjy, F. R. Bach, S. Canu, and Y. Grandvalet. SimpleMKL,. JMLR, 9:2491–2521, November 2008. 1, 2, 3, 6
[19] S. Shalev-Shwartz and Y. Singer. Logarithmic regret algorithms forstrongly convex repeated games. Technical Report 2007-42, The Hebrew University, 2007. 3, 5[20] S. Shalev-Shwartz, Y. Singer, and N. Srebro. Pegasos: Primal estimated sub-gradient solver for SVM. In Proc. ICML, 2007. 3, 4, 5,
6[21] S. Shalev-Shwartz and N. Srebro. SVM optimization: inverse dependence on training set size. In Proc. ICML, 2008. 2, 4, 6
[22] S. Sonnenburg, G. Rätsch, C. Schäfer, and B. Schölkopf. Large scale
multiple kernel learning. JMLR, 7, 2006. 1, 2, 3, 6
[23] I. Tsochantaridis, T. Hofmann, T. Joachims, and Y. Altun. Support vector machine learning for interdependent and structured output spaces. In Proc. ICML, 2004. 1, 2, 3, 8
[24] M. Varma and D. Ray. Learning the discriminative power-invariance
trade-off. In Proc. ICCV, 2007. 1, 2
[25] A. Vedaldi, V. Gulshan, M. Varma, and A. Zisserman. Multiple kernels for object detection. In Proc. ICCV, 2009. 1[26] D. Wolpert. Stacked generalization. Neural Networks, 5(2), 1992. 2[27] A. Zien and C. S. Ong. Multiclass multiple kernel learning. In Proc.
ICML, 2007. 1, 2, 3