Journal of Machine Learning Research 13 (2012) 165-191

Submitted 3/11; Revised 9/11; Published 2/12

Multi Kernel Learning with Online-Batch Optimization∗
Francesco Orabona†

FRANCESCO @ ORABONA . COM

Toyota Technological Institute at Chicago
6045 South Kenwood Avenue
60637 Chicago, IL, USA

Luo Jie†

LUOJIE @ YAHOO - INC . COM

Yahoo! Labs
701 First Avenue
94089 Sunnyvale, CA, USA

Barbara Caputo

BCAPUTO @ IDIAP. CH

Idiap Research InstituteCentre du Parc, Rue Marconi 19
1920 Martigny, Switzerland

Editor: Francis Bach

Abstract
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. In the domain of kernel methods, a principled way to use multiple features is theMulti Kernel Learning (MKL) approach.
Here we present a MKL optimization algorithm based on stochastic gradient descent that has
a guaranteed convergence rate. We directly solve the MKL problem in the primal formulation. By
having a p-norm formulation of MKL, we introduce a parameter that controls the level of sparsityof the solution, while leading to an easier optimization problem. We prove theoretically and experimentally that 1) our algorithm has a faster convergence rate as the number of kernels grows; 2) the
training complexity is linear in the number of training examples; 3) very few iterations are sufficient
to reach good solutions. Experiments on standard benchmark databases support our claims.
Keywords: multiple kernel learning, learning kernels, online optimization, stochastic subgradientdescent, convergence bounds, large scale

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. Moreover, besides the purpose of decreasing the generalization error, practitioners
are often interested in more flexible algorithms which can perform feature selection while training.
This is for instance the case when a lot of features are available but among them noisy ones are
hidden. Selecting the features also improves the interpretability of the decision function.
This has been translated into various algorithms, that dates back to the ’90s (Wolpert, 1992),
based on a two-layers structure. There a classifier is trained for each cue and then their outputs∗. A preliminary version of this paper appeared in Orabona et al. (2010).
†. Work done mainly while at Idiap Research Institute.
c 2012 Francesco Orabona, Luo Jie and Barbara Caputo.

O RABONA , J IE AND C APUTO

are combined by another classifier. This approach has been re-invented many times, with different
flavors (Nilsback and Caputo, 2004; Sanderson and Paliwal, 2004; Jie et al., 2010a; Gehler andNowozin, 2009b; Jin et al., 2010). In general, the two layers approaches use Cross-Validation (CV)methods to create the training set for the second layer (Wolpert, 1992; Gehler and Nowozin, 2009b).
If the second layer is a linear classifier, these methods are equivalent to a linear combination of thesingle classifiers.
Focusing on the domain of the Support Vector Machines (SVM) (Cristianini and Shawe-Taylor,
2000), the use of multiple cues corresponds to the use of multiple kernels. Hence, instead of combining kernel classifiers, the focus of research has moved on how to build an optimal new kernel asa weighted combination of kernels.
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). This approach builds on the previous works on the maximization of thekernel alignment to combine kernels (Lanckriet et al., 2004). However in this approach, even if
theoretically principled, the global optimality is not guaranteed, because the optimization processsplit in two phases.
A different approach with a joint optimization process is Multi Kernel Learning (MKL) (Lanckriet et al., 2004; Bach et al., 2004; Sonnenburg et al., 2006; Zien and Ong, 2007; Rakotomamonjy
et al., 2008; Varma and Babu, 2009; Kloft et al., 2009). In MKL one solves a joint optimization
problem while also learning the optimal weights for combining the kernels. MKL methods aretheoretically founded, because they are based on the minimization of an upper bound of the generalization error (Kakade et al., 2009; Cortes et al., 2010), like in standard SVM. In most of theseapproaches the objective function is designed to impose sparsity on the weights of the combination using an l1 -norm constraint (Bach et al., 2004; Sonnenburg et al., 2006; Zien and Ong, 2007;
Rakotomamonjy et al., 2008; Varma and Babu, 2009). However solving it is far more complex
than training a single SVM classifier. In fact, the l1 norm is not smooth, so it slows down the optimization process. The original MKL problem by Lanckriet et al. (2004) was cast as a semidefinite
programming (SDP). SDP are known to have poor scalability, hence much of the subsequent research focused on devising more efficient optimization procedures. The first step towards practical
MKL algorithms was to restrict the weights coefficients to be non-negative. In this way, it waspossible to recast the problem as a much more efficient semi-infinite linear programming (SILP)(Sonnenburg et al., 2005; Rubinstein, 2005). This has allowed to solve the MKL problem with alternating optimization approaches (Sonnenburg et al., 2006; Rakotomamonjy et al., 2008; Xu et al.,2008; Nath et al., 2009), first optimizing over the kernel combination weights, with the current
SVM solution fixed, then finding the SVM solution, given the current weights. One advantage ofthe alternating optimization approach is that it is possible to use existing efficient SVM solvers,
such as Joachims (1999) and Chang and Lin (2001), for the SVM optimization step. On the other
hand, for these algorithms, it is usually not possible to prove a bound on the maximum number of
iterations needed, even if they are known to converge. In fact, to the best of our knowledge, none of
the existing MKL algorithms provides theoretical guarantees on the convergence rate. For the same
reason it is not possible to know the asymptotic computational complexity of these algorithms, andoften these dependencies are estimated numerically for the specific implementation at hand. For
example, multiclass MKL SILP algorithm (Sonnenburg et al., 2006; Zien and Ong, 2007) seems
to depend polynomially on the number of training examples and number of classes with an expo166

M ULTI K ERNEL L EARNING WITH O NLINE -BATCH O PTIMIZATION

nent of ∼ 2.4 and ∼ 1.7 respectively. For the other algorithms these dependencies are not clear.
Another disadvantage is that they need to solve the inner SVM problem till optimality. In fact, toguarantee convergence, the solution needs to be of a high enough precision so that the kernel weightgradient computation is accurate. On the other hand the learning process is usually stopped early,
before reaching the optimal solution, based on the common assumption that it is enough to havean approximate solution of the optimization function. Considering the fact that the current MKL
algorithms are solved based on their dual representation, this might mean being stopped far fromthe optimal solution (Hush et al., 2006), with unknown effects on the convergence.
An important point is that, very often, these approaches fail to improve much over the naive
baseline of just summing all the kernels (Kloft et al., 2009). Recently, researchers start to realizethat when the optimal Bayes classifier is not sparse, brutally imposing sparsity will hurt the generalization performance. Motivated by this, the l p -norm constraint has been proposed (Kloft et al.,2009; Orabona et al., 2010; Vishwanathan et al., 2010), instead of l1 -norm constrain, to be able totune the level of sparsity of the solution and to obtain an easier problem too. In particular Vishwanathan et al. (2010) derived the dual of a variation of the l p MKL problem for p > 1, suited to
be optimized with the popular Sequential Minimal Optimization algorithm (Platt, 1999). Howevereven for their algorithm it is not clear how the convergence rate depends on p and how to generalize
the algorithm to generic loss functions, such as the structured losses (Tsochantaridis et al., 2004).
This limitation on the use of particular loss functions is common to all the recent MKL optimization
algorithms. An alternative way to be able to tune the sparsity of the MKL solution, inspired by theelastic-net regularization, has been proposed by Tomioka and Suzuki (2010).
The main contribution of this paper is a new optimization algorithm to solve efficiently the l p MKL problem, with a guaranteed convergence rate to the optimal solution. We minimize it with a
two-stage algorithm. The first one is an online initialization procedure that determines quickly theregion of the space where the optimal solution lives. The second stage refines the solution foundby the first stage, using a stochastic gradient descent algorithm. Bounds on the convergence rate
are proved for the overall process. Notably different from the other methods, our algorithm solves
the optimization problem directly in the primal formulation, in both stages. This allows us to use
any convex loss function, as the multiclass loss proposed by Crammer and Singer (2002) or general
structured losses (Tsochantaridis et al., 2004), without any change to the core of the algorithm.
Using recent approaches in optimization theory, the algorithm takes advantage of the abundance of
information to reduce the training time (Shalev-Shwartz and Srebro, 2008). In fact, we show thatthe 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. Our algorithm
has a training time that depends linearly on the number of training examples, with a convergence
rate sub-linear in the number of features/kernels used, when a sparse solution is favored. At thesame time, it achieves state-of-the-art performance on standard benchmark databases. We call thisalgorithm OBSCURE, Online-Batch Strongly Convex mUlti keRnel lEarning.
The rest of the paper presents the theory and the experimental results supporting our claims.
Section 2 revises the basic definitions of Multi Kernel Learning and generalizes it to the l p -norm
formulation. Section 3 presents the OBSCURE algorithm and Section 4 shows our theoreticalguarantees, while Section 5 reports experiments on categorization tasks. We conclude the paperwith discussions and future works.
167

O RABONA , J IE AND C APUTO

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
In the following we define some notations and we also introduce some concepts of convex analysis.
For a more thorough introduction see, for example, Boyd and Vandenberghe (2004).
2.1.1 N OTATION
We indicate matrices and vectors with bold letters. We also introduce two notations that will help
us to synthesize the following formulas. We indicate by [w j ]F1 := w1 , w2 , · · · , wF , and with abar, for example, w̄, the vector formed by the concatenation of the F vectors w j , hence w̄ =[w1 , w2 , · · · , wF ] = [w j ]F1 .
We consider closed convex functions f : S → R, where in the following S will always denotea proper subset of X, an Euclidean vector space.1 We will indicate the inner product between two
vectors of X, w and w′ , as w · w′ . Given a convex function f : S → R, its Fenchel conjugate f ∗ : X →R is defined as f ∗ (u) = supv∈S (v · u − f (v)). A generic norm of a vector w ∈ X is indicated by kwk,
and its dual k · k∗ is the norm defined as kyk∗ = sup{x · y : kxk ≤ 1}. A vector x is a subgradient of afunction f at v, if ∀u ∈ S, f (u)− f (v) ≥ (u−v)·x. The differential set of f at v, indicated with ∂ f (v),is the set of all the subgradients of f at v. If f is convex and differentiable at v then ∂ f (v) consists ofa single vector which is the gradient of f at v and is denoted by ∇ f (v). A function f : S → R is said
to be λ-strongly convex with respect to a convex and differentiable function h iff for any u, v ∈ S
and any subgradient ∂ f (u), f (v) ≥ f (u) + ∂ f (u) · (v − u) + λ(h(v) − h(u) − (v − u) · ∇h(v)), where
the terms in parenthesis form the Bregman divergence between v and u of h.
2.1.2 B INARY AND M ULTI - CLASS C LASSIFIERS
Let {xi , yi }Ni=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 kernels,2 in which the prediction on a sample
x is a function of the scalar product between an hyperplane w and the transformed sample φ(x). With
multiple kernels, we will have F corresponding functions φ j (·), i = 1, · · · , F, and F corresponding
kernels K j (x, x′ ) defined as φ j (x) · φ j (x′ ).
For multiclass and structured classification Y = {1, . . . , M}, and we follow the common approach to use joint feature maps φ(x, y) : X × Y → H (Tsochantaridis et al., 2004). Again, we will
have F functions φ j (·, ·), i = 1, · · · , F, and F kernels K j ((x, y), (x′ , y′ )) as φ j (x, y) · φ j (x′ , y′ ). Thisdefinition includes the case of training M different hyperplanes, one for each class. Indeed φ j (x, y)
can be defined as
φ j (x, y) = [0, · · · , 0, φ′ j (x), 0, · · · , 0],| {z }
y

1. We allow the functions to assume infinite values, as a way to restrict their domains to proper subsets of X. Howeverin the following the convex functions of interest will always be evaluated on vectors that belong to their domains.
2. For simplicity we will not use the bias here, but it can be easily added modifying the kernel definition.

168

M ULTI K ERNEL L EARNING WITH O NLINE -BATCH O PTIMIZATION

where φ′ j (·) is a transformation that depends only on the data. Similarly w will be composed by
M blocks, [w1 , · · · , wM ]. Hence, by construction, w · φ j (x, r) = wr · φ′ j (x). According to the definednotation, φ̄(x, y) = [φ1 (x, y), · · · , φF (x, y)]. These definitions allow us to have a general notation forthe binary and multiclass setting.
2.1.3 L OSS F UNCTION
In the following we consider convex Lipschitz loss functions. The most commonly used loss inbinary classification is the hinge loss (Cristianini and Shawe-Taylor, 2000).
ℓHL (w, x, y) = |1 − yw̄ · φ̄(x)|+ ,where |t|+ is defined as max(t, 0). We also consider the following multi-class loss function (Crammer and Singer, 2002; Tsochantaridis et al., 2004), that will be used to specialize our results.
ℓMC (w, x, y) = max|1 − w̄ · (φ̄(x, y) − φ̄(x, y′ ))|+ .
′
y 6=y

(1)

This loss function is convex and it upper bounds the multi-class misclassification loss.
2.1.4 N ORMS AND D UAL N ORMS
For w ∈ Rd and p ≥ 1, we denote by kwk p the p-norm of w, that is, kwk p = (∑di=1 |wi | p )1/p .
The dual norm of k · k p is k · kq , where p and q satisfy 1/p + 1/q = 1. In the following p and q
will always satisfy this relation.
2.1.5 G ROUP N ORM
It is possible to define a (2, p) group norm kw̄k22,p on w̄ as
kw̄k2,p :=

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



p

,

that is the p-norm of the vector of F elements, formed by 2-norms of the vectors w j . The dual normof k·k2,p is k·k2,q (Kakade et al., 2009). These kind of norms have been used as block regularizationin the LASSO literature (Yuan and Lin, 2006).
2.2 Multi Kernel Learning
The MKL optimization problem was first proposed by Bach et al. (2004) and extended to multiclassby Zien and Ong (2007). It can be written as
λ
min
wj 2

F

∑ kw k2

j=1

j

!2

+

1 N
∑ ξi
N i=1

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

(2)

O RABONA , J IE AND C APUTO

An equivalent formulation can be derived from the first one through a variational argument (Bachet al., 2004)!2
λ F kw j k2
1 Nmin+ ∑ ξi∑w j ,α j ≥0 2
N i=1
j=1 α js.t. w̄ · (φ̄(xi , yi ) − φ̄(xi , y)) ≥ 1 − ξi , ∀i, y 6= yikαk21 ≤ 1 .

(3)This formulation has been used by Bach et al. (2004) and Sonnenburg et al. (2006), while
the formulation proposed by Rakotomamonjy et al. (2008) is slightly different, although it can beproved to be equivalent. The reason to introduce this variational formulation is to use an alternating
optimization strategy to efficiently solve the constrained minimization problem. However in thefollowing we will show that it is possible to efficiently minimize directly the formulation in (2), orat least one variation of it.
We first rewrite (2) with group norms. Using the notation defined above, we have
min
w̄

λ
1 N
kw̄k22,1 + ∑ ℓMC (w̄, xi , yi ) ,
2
N i=1

(4)

where w̄ = [w1 , w2 , · · · , wF ]. The (2, 1) group norm 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 lead to adecrease in performance. Moreover the problem in (4) is not strongly convex (Kakade et al., 2009),
so its optimization algorithm is rather complex and its rate of convergence is usually slow (Bachet al., 2004; Sonnenburg et al., 2006).
We generalize the optimization problem (4), using a generic group norm and a generic convex
loss function
λ1 N
min kw̄k22,p + ∑ ℓ (w̄, xi , yi ) ,
(5)
w̄
2
N i=1
where 1 < p ≤ 2. We also define f (w̄) := λ2 kw̄k22,p + N1 ∑Ni=1 ℓ (w̄, xi , yi ) and w̄∗ equals to the optimal
solution of (5), that is w̄∗ = arg minw̄ f (w̄). The additional parameter p allow us to decide the levelof sparsity of the solution. Moreover this formulation has the advantage of being λ/q-strongly
convex (Kakade et al., 2009), where λ is the regularization parameter in (5). Strong convexity is a
key property to design fast batch and online algorithms: the more a problem is strongly convex theeasier it is to optimize it (Shalev-Shwartz and Singer, 2007; Kakade et al., 2009). Many optimization
problems are strongly convex, as the SVM objective function. When p tends to 1, the solution getsclose to the sparse solution obtained by solving (2), but the strong convexity vanishes. Setting pequal to 2 corresponds to using the unweighted sum of the kernels. In the following we will show
how to take advantage of the strong convexity to design a fast algorithm to solve (5), and how to havea good convergence rate even when the strong convexity is close to zero. Note that this formulation
is similar to the one proposed by Kloft et al. (2009). Indeed, as for (2) and (3), using Lemma 26
in Micchelli and Pontil (2005) it is possible to prove that they are equivalent through a variational
argument.
We have chosen to 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. This choice170

M ULTI K ERNEL L EARNING WITH O NLINE -BATCH O PTIMIZATION

simplifies the math of our algorithm. However the two formulations are equivalent when setting1
λ = CN, hence a big value of C corresponds to a small value of λ.

3. The OBSCURE Algorithm
Our basic optimization tool is the framework developed in Shalev-Shwartz and Singer (2007);
Shalev-Shwartz et al. (2007). It is a general framework to design and analyze stochastic subgradient descent algorithms for any strongly convex function. At each step the algorithm takesa random sample of the training set and calculates a sub-gradient of the objective function evaluated on the sample. Then it performs a sub-gradient descent step with decreasing learning rate,
followed by a projection inside the space where the solution lives. The algorithm Pegasos, basedon this framework, is among the state-of-art solvers for linear SVM (Shalev-Shwartz et al., 2007;
Shalev-Shwartz and Srebro, 2008).
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 (Shalev-Shwartz et al.,2007; Shalev-Shwartz and Srebro, 2008). In particular a Pegasos-like algorithm used to minimize(5) would have a convergence rate, and hence a training time, proportional to λq . Although in
general this convergence rate can be quite good, it becomes slow when λ is small and/or p is close
to 1. Moreover it is common knowledge that in many real-world problems (e.g., visual learning
tasks) the best setting for λ is very small, or equivalently C is very big (the order of 102 − 103 ).
Notice that this is a general problem. The same problem also exists in the other SVM optimization
algorithms such as SMO and similar approaches, as their training time also depends on the value ofthe parameter C (Hush et al., 2006).
Do et al. (2009) proposed a variation of the Pegasos algorithm called proximal projected subgradient descent. This formulation has a better convergence rate for small values of λ, while retaining the fast convergence rate for big values of λ. A drawback is that the algorithm needs to know
in advance an upper bound on the norm of the optimal solution. Do et al. (2009) solve this problem
with an algorithm that estimates this bound while training, but it gives a speed-up only when thenorm of the optimal solution w̄∗ is small. This is not the case in most of the MKL problems for
categorization tasks.
Our OBSCURE algorithm takes the best of the two solutions. We first extend the frameworkof Do et al. (2009) to the generic non-Euclidean norms, to use it with the (2, p) group norm. Then
we solve the problem of the upper bound of the norm of the optimal solution using a new online
algorithm. This is designed to take advantage of the characteristics of the MKL task and to quickly
converge to a solution close to the optimal one. Hence OBSCURE is composed of two steps: thefirst 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 estimated region, it uses a stochastic
proximal projected sub-gradient descent algorithm. We also found that, even if we cannot guarantee
this theoretically, empirically in many cases the solution found by the first stage is extremely close
to the optimal one. We will show this in the experiments of Section 5.6.
3.1 Efficient Implementation
The training time of OBSCURE is proportional to the number of steps required to converge to the
optimal solution, that will be bounded in Theorem 3, multiplied by the complexity of each step. This171

O RABONA , J IE AND C APUTO

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 (xt , yt ) at random5:z̄t = ∂ℓ (w̄t , xt , yt )6:θ̄t+1 = θ̄t − ηz̄t
7:

j
wt+1 = 1qjkθt+1 k2kθ̄t+1 k2,q

8: end for
9: return θ̄T +1q, w̄T +1

q−2

j

θt+1 , ∀ j = 1, · · · , F2kw̄T +1 k22,p + λN
∑Ni=1 ℓ (w̄T +1 , xi , yi )10: return R =Algorithm 2 OBSCURE stage 2 (stochastic optimization)
1: Input: q, θ̄1 , w̄1 , R, λ
2: Initialize: s0 = 0
3: for t = 1, 2, . . . , T do
4:
Sample (xt , yt ) at random5:z̄t = ∂ℓ (w̄t , xt , yt )6:
dt = λt + st−1 r
7:

st = st−1 + 0.5

8:qηt = λt+s
t

9:
10:
11:

θ̄t+ 1 = (1 − ληq t )θ̄t − ηt z̄t2!
θ̄t+1 = min 1, kθ̄ qRk

t+ 21 2,qj

wt+1 = 1q

12: end forλ( kθ̄t k2,q +kz̄t k2,q )dt2 + q qR2

jkθt+1 k2kθ̄t+1 k2,q

q−2

2

− dt

!

θ̄t+ 12

jθt+1 , ∀ j = 1, · · · , F

in turn is dominated by the calculation of the gradient of the loss (line 5 in Algorithms 1 and 2).
This complexity, for example, for the multiclass hinge loss ℓMC is O (NFM), given that the numberof support vectors is proportional to N. Note that this complexity is common to any other similar
algorithm, and it can be reduced using methods like kernel caching (Chang and Lin, 2001).
Following (Shalev-Shwartz et al., 2007, Section 4), it is possible to use Mercer kernels without
introducing explicitly the dual formulation of the optimization problem. In both algorithms, θ̄t+1
can be written as a weighted linear summation of φ̄(xt , ·). For example, when using the multiclass loss function ℓMC , we have that θ̄t+1 = − ∑t ηt z̄t = ∑t ηt (φ̄(xt , yt ) − φ̄(xt , ŷt )). Therefore, thealgorithm can easily store ηt , yt , ŷt , and xt instead of storing θ̄t . Observing line 7 in Algorithm 1jjand line 11 in the Algorithm 2, we have that at each round, wt+1 is proportional to θt+1 , that isj
j jj
wt+1 = αt θt+1 . Hence w̄t+1 can also be represented using αt ηt , yt , ŷt and xt . In prediction thej
dot product between w̄t and φ̄(xt , ·) can be expressed as a sum of terms w̄t · φ j (xt , ·), that can becalculated using the definition of the kernel.
172

M ULTI K ERNEL L EARNING WITH O NLINE -BATCH O PTIMIZATION

Algorithm 3 Proximal projected sub-gradient descent
1: Input: R, σ, w1 ∈ S
2: Initialize: s0 = 0
3: for t = 1, 2, . . . , T do
4:
Receive gt
5:zt = ∂gt (wt )q6:
7:

st = st−1 +ηt = σt+1 st(ασt+st−1 )2 + αL2t −ασt−st−1R2αwt+1 = ∇h∗ (∇h(wt ) − ηt zt )9: end for

8:

Another important speed-up can be obtained considering the nature of the updates of the second
stage. If the optimal solution has a loss equal to zero or close to it, when the algorithm is close toconvergence most of the updates will consist just of a scaling. Hence it is possible to cumulate thescalings in a variable, to perform the scaling of the coefficients just before an additive update mustbe performed, and to take it into account for each prediction. Moreover, when using the multiclassloss (1), each update touches only two classes at a time, so to minimize the number of scalings we
can keep a vector of scaling coefficients, one for each class, instead of a single number. For moredetails on the implementation, we refer the reader to the MATLAB implementation of OBSCURE
in DOGMA (Orabona, 2009).

4. Analysis
We now show the theorems that give a theoretical guarantee on the convergence rate of OBSCURE
to the optimal solution of (5). The following lemma contains useful properties to prove the performance guarantees of Algorithm 1 and 2.
Lemma 1 Let B ∈ R+ , define S = {w̄ : kw̄k2,p ≤ B}. Let h(w̄) : S → R defined as q2 kw̄k22,p , definealso Proj(w̄, B) = min 1, kw̄kB2,p w̄, then
1. ∇h(w̄) = q

kw j k2
kw̄k2,p2. ∇h∗ (θ̄) = Proj

1
q

 p−2



wj

kθ j k2kθ̄k2,qF1, ∀w̄ ∈ S

q−2

θj

F
1

,B

!

3. kw̄k2,p = q1 k∇h(w̄)k2,q , ∀w̄ ∈ S
Proof All the proofs of these relations use the equality 1/p + 1/q = 1. The first one can be obtained differentiating h. The second relation is obtained using Lemma 2 in Shalev-Shwartz andSinger (2007), through lengthy but straightforward calculations. The last one is obtained from thefirst one.
We now introduce Algorithm 3, that forms the basis for Algorithm 2, and a lemma that bounds
its performance, that is a generalization of Theorem 1 in Do et al. (2009) to general norms, using173

O RABONA , J IE AND C APUTO

the framework in Shalev-Shwartz and Singer (2007). Hence it can be seen as a particular case of themirror descent algorithm (Beck and Teboulle, 2003), with an adaptive tuning of the learning rate.
Lemma 2 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 kzt k∗ ≤ Lt . Let R ∈ R+ suchthat kw − w′ k ≤ 2R for any w, w′ ∈ S. Then for any u ∈ S, and for any sequence of non-negative
ξ1 , . . . , ξT , Algorithm 3 achieves the following bound for all T ≥ 1,
"
#
T
T
2
L
t
.
∑ (gt (wt ) − gt (u)) ≤ ∑ 4ξt R2 +∑ti=1 ξiσt + αt=1
t=1
Proof Define gt′ (w) = gt (w) + s2t kw − wt k2 , where w, wt ∈ S, and the value of st will be specified
later. Using the assumptions of this Lemma, we have that gt′ is (σ + sαt )-strongly convex w.r.t. to h.
Moreover we have that ∂gt′ (wt ) = ∂gt (wt ), because the gradient of the proximal regularization term
is zero when evaluated at wt (Do et al., 2009). Hence we can apply Theorem 1 from Shalev-Shwartz
and Singer (2007) to have
T

T

t=1

t=1





st

1 T

T

T

t=1

t=1

Lt2

∑ gt (wt ) − ∑ gt (u) + 2 ku − wt k2 = ∑ gt′ (wt ) − ∑ gt′ (u) ≤ 2 ∑t=1 σt +∑ti=1 siα.

Using the hypothesis of this Lemma we obtain




αLt2
αLt2
1 T
1 T
2
2
∑ gt (wt ) − ∑ gt (u) ≤ 2 ∑ st ku − wt k + ασt + ∑t si ≤ 2 ∑ 4st R + ασt + ∑t si .
i=1
i=1
t=1
t=1
t=1
t=1
T

T

Using the definition of st in the algorithm and Lemma 3.1 in Bartlett et al. (2008), we have
T

T

t=1

t=1

min
∑ gt (wt ) − ∑ gt (u) ≤ ξ ,...,ξ
≥0
1

T


∑ 4ξt R2 +
T

t=1

αLt2
ασt + ∑ti=1 ξi.

Hence these settings of st give us a bound that is only 2 times worse than the optimal one.
With this Lemma we can now design stochastic sub-gradient algorithms. In particular, setting
k · k2,p as the norm, h(w̄) = 2q kw̄k22,p , and gt (w̄) = λq h(w̄) + ℓ (w̄, xt , yt ), we obtain Algorithm 2 thatsolves the p-norm MKL problem in (5). The updates are done on the dual variables θ̄t , in lines
9-10, and transformed into w̄t in line 11, through a simple scaling. We can now prove the following
bound on the convergence rate for Algorithm 2.
Theorem 3 Suppose that k∂ℓ (w̄, xt , yt ) k2,q ≤ L and kw̄∗ k2,p ≤ R, where w̄∗ is the optimal solutionof (5), that is w̄∗ = argmin f (w̄). Let 1 < p ≤ 2, and c = λR + L, then in expectation over the choicesw̄

of the random samples we have that, after T iterations of the 2nd stage of the OBSCURE algorithm,
the difference between f (w̄T ) and f (w̄∗ ), is less than √ √c q 1 + log T 4R√ p.
,√
c q 1 + log T min
λT
T
174

M ULTI K ERNEL L EARNING WITH O NLINE -BATCH O PTIMIZATION

Proof Let h(w̄) : S → R defined as 2q kw̄k22,p , where S = {w̄ : kw̄k2,p ≤ R}. Define also gt (w̄) =λλ2
2 kw̄k2,p + ℓ(w̄, xt , yt ) = q h(w̄) + ℓ(w̄, xt , yt ). Using Lemma 1 in Shalev-Shwartz and Singer (2007),

we can see that these two functions satisfy the hypothesis of Lemma 1, with α = q, σ = λq . It iseasy to verify that w̄t+1 is equal to ∇h∗ (∇h(w̄t ) − ηt zt ). In fact, taking into account Properties 1-3
in Lemma 1 with with B = R, lines 9-11 in Algorithm 2 are equivalent tow̄t+1 = ∇h∗ (θt − ηt zt )θ̄t+1 = ∇h(w̄t+1 ) .

We also have that
λk∂gt (w̄)k2,q ≤ k∇h(w̄t )k2,q + kz̄t k2,q = λkw̄t k2,p + kz̄t k2,q ≤ c,q
where the equality is due to Property 3 in Lemma 1. So we have

T
T 
qc2
∗
2
∑ (gt (w̄t ) − gt (w̄ )) ≤ ξ1min∑ 4ξt R + λt + ∑t ξi .
,··· ,ξT t=1
i=1
t=1
Reasoning as in Shalev-Shwartz et al. (2007), we divide by T , take the expectation on both sides.
So we obtain that


qc2
1 T
2
∗
E[ f (w̄T ) − f (w̄ )] ≤ min∑ 4ξt R + λt + ∑t ξi .
ξ1 ,··· ,ξT T t=1
i=1
Setting ξi = ξ, i = 1, . . . , T , the last term in the last equation can be upper bounded by
"
#
T
2
qc
1
AT = min 4ξR2 + ∑.
T t=1 t(λ + ξ)ξThis term is smaller than any specific setting of ξ, in particular if we set ξ to 0, we have that
2T)
AT ≤ qc (1+log. On the other hand setting optimally the expression over ξ and over-approximating
λT
we have that AT ≤bound.

√ √4cR q 1+log T√. Taking the minimum of these two quantities we obtain the statedT

The most important thing to note is that the converge rate is independent from the number ofsamples, as in Pegasos (Shalev-Shwartz et al., 2007), and the relevant quantities on which it depends
are λ and q. Given that for most of the losses, each iteration has a linear complexity in the numberof samples, as stated in Section 3.1, the training time will be linearly proportional to the number ofsamples.
The parameter R is basically an upper bound on the norm of the optimal solution. In the next
Section we show how to have a good estimate of R in an efficient way. The theorem first shows thata good estimate of R can speed-up the convergence of the algorithm. In particular if the first term isTdominant, the convergence rate is O ( q log
λT ). If the second term is predominant, the convergence rate√

q log T
is O ( R √), so it becomes independent from λ. The algorithm will always optimally interpolateTbetween these two different rates of convergence. Note that R can also be set to the trivial upper175

O RABONA , J IE AND C APUTO

bound of ∞. This would result in a standard Pegasos-like optimization. In fact, st would be equalT
to 0 in Algorithm 2, so the learning rate would be λt1 and the convergence rate would be O ( q log
λT ).
We will see in Section 5.3 that a tight estimate of R can improve dramatically the convergence rate.
Another important point is that Algorithm 2 can start from any vector, while this is not possible in
the Pegasos algorithm, where at the very first iteration the starting vector is multiplied by 0 (ShalevShwartz et al., 2007).
As said before, the rate of convergence√ depends on p, through q. A p close to 1 will result in aq log T
sparse solution, with a rate of at most O ( R √). However in the experiment section we show thatT
the best performance is not always given by the most sparse solution.
This theorem and the pseudocode in Algorithm 2 allows us to design fast and efficient MKL
algorithms for a wide range of convex losses. If we consider the multiclass loss ℓMC with normalized√ 1
kernels, that is, kφ j (xt , yt )k2 ≤ 1, ∀ j = 1, · · · , F, t = 1, · · · , N, we have that L ≤ 2F q . Instead, if we1
use the hinge loss ℓHL for binary classification, we have that L ≤ F q . Hence, in both cases, if p < 2,
the convergence rate has a sublinear dependency on the number of kernels, F, and if the problem
is linearly separable it can have a faster convergence rate using more kernels. We will explain thisformally in the next section.
4.1 Initialization Through an Online Algorithm
In Theorem 3 we saw that if we have a good estimate of R, the convergence rate of the algorithm canbe much faster. Moreover starting from a good solution could speed-up the algorithm even more.
We propose to initialize Algorithm 2 with Algorithm 1. It is the online version of problem (5)and it is derived using a recent result in Orabona and Crammer (2010). It is similar to the 2p-norm
matrix Perceptron of Cavallanti et al. (2008), but it overcomes the disadvantage of being used withthe same kernel on each feature.
We can run it just for few iterations and then evaluate its norm and its loss. In Algorithm 1 R isthen defined as
s
s
N
N
2
∗ k2 + 2
R := kw̄T +1 k22,p +
ℓ
(
w̄
,
x
,
y
)
≥
k
w̄
∑ T +1 i i∑ ℓ (w̄∗ , xi , yi ) ≥ kw̄∗ k2,p ,2,pλN i=1λN i=1
where we remind that w̄∗ is solution that minimizes (5), as defined in Section 2.2. So at any moment
we can stop the algorithm and obtain an upper bound on kw̄∗ k2,p . However if the problem is linearly
separable we can prove that Algorithm 1 will converge in a finite number of updates. In fact, as in
Cavallanti et al. (2008), for Algorithm 1 it is possible to prove a relative mistake bound. See also Jie
et al. (2010b) and Jin et al. (2010) for similar algorithms for online MKL, with a different update
rules and different mistake bounds.
Theorem 4 Let (x1 , y1 ), . . . , (xT , yT ) be a sequence of examples where xt ∈ X, y ∈ Y. Suppose thatthe loss function ℓ has the following properties• k∂ℓ (w̄, x, y) k2,q ≤ L, ∀ w̄ ∈ X, xt ∈ X, yt ∈ Y;
• ℓ(ū, x, y) ≥ 1 + ū · ∂ℓ(w̄, x, y), ∀ ū ∈ X, w̄ ∈ X : ℓ(w̄, x, y) > 0, x ∈ X, y ∈ Y;
• w̄ · ∂ℓ(w̄, x, y) ≥ −1, ∀ w̄ ∈ X, x ∈ X, y ∈ Y.
176

M ULTI K ERNEL L EARNING WITH O NLINE -BATCH O PTIMIZATION

Denote by U the set of rounds in which there is an update, and by U its cardinality. Then, for anyū, the number of updates U of Algorithm 1 satisfiesqr2
2
U ≤ q(2/η + L )kūk2,p + ∑ ℓ(ū, xt , yt ) + kūk2,p q(2/η + L2 ) ∑ ℓ(ū, xt , yt ) .
t∈U

t∈U

In particular, if the problem (5) is linearly separable by a hyperplane v̄, then the Algorithm 1 will
converge to a solution in a finite number of steps less than q(2/η + L2 )kv̄k22,p . In this case thereturned value of R will be less than (2 + ηL2 )kv̄k2,p .
Proof The bound on the number of updates can be easily derived using a recent result in Orabona
and Crammer (2010), that we report in Appendix for completeness. Let h(w̄) : X → R defined asq2
2 kw̄k2,p . Notice that, differently from the proof of Theorem 3, here the domain of the function h is
the entire Euclidean space X. Using Property 2 in Lemma 1 with B = ∞, we have that line 7 in thealgorithm’s pseudo-code implies that w̄t = ∇h∗ (θ̄t ). Using Lemma 5 in the Appendix, we have thats 2w̄t · z̄t√2
U ≤ ∑ ℓ(ū, xt , yt ) + qkūk2,p ∑ kz̄t k2,q −
η
t∈U
t∈U
s 

2
√
≤ ∑ ℓ(ū, xt , yt ) + qkūk2,p U L2 +.
ηt∈U
Solving for U and overapproximating we obtain the stated bound.
For the second part of the Theorem, using (Kakade et al., 2009, Corollary 19), we know thath∗ (w̄) is 1-smooth w.r.t. k · k2,q . Hence, we obtain
2w̄t · z̄t
2
2
2
2
2
2
kθ̄T +1 k2,q ≤ kθ̄T k2,q − 2qηw̄T · z̄T + qη kz̄T k2,q ≤ η q ∑ kz̄t k2,q −
η
t∈U


2
≤ η2 qU+ L2 .
ηSo we can writeqkθ̄T +1 k2,q ≤ η qU(2/η + L2 ),and using the bound of U and the hypothesis of linear separability, we haveqkθ̄T +1 k2,q ≤η q2 kūk22,p (2/η + L2 )2 = qkūk2,p 2 + ηL2 .

Using the relation kw̄t k2,p = q1 kθ̄t k2,q , that holds for Property 2 in Lemma 1 with B = ∞, we havethe stated bound on R.
From the theorem it is clear the role of η: a bigger value will speed up the convergence, but it will
decrease the quality of the estimate of R. So η governs the trade-off between speed and precision of
the first stage.
The multiclass loss ℓMC and the hinge loss ℓHL satisfy the conditions of the Theorem, and, as
noted for Theorem 1 when p is close to 1, the dependency on the number of kernels in this theorem
is strongly sublinear.
177

O RABONA , J IE AND C APUTO

Note also that the separability assumption is far from being unrealistic in our setting. In fact the
opposite is true: in the greater majority of the cases the problem will be linearly separable. This isdue to the fact that in MKL to have separability it is sufficient that only one of the kernel induces
a feature space where the problem is separable. So, for example, it is enough to have no repeatedsamples with different labels and at least one kernel that always produces kernel matrices with fullrank, for example, the Gaussian kernel.
Moreover, under the separability assumption, if we increase the number of kernels, we have that2kūk2,p cannot increase, and in most of the cases it will decrease. In this case we expect Algorithm 1
to converge to a solution which has null loss on each training sample, in a finite number of steps
that is almost independent on F and in some cases even decreasing while increasing F. The sameconsideration holds for the value of R returned by the algorithm, that can decrease when we increase
the number of kernels. A smaller value of R will mean a faster convergence of the second stage. We
will confirm this statement experimentally in Section 5.

5. Experiments
In this section, we study the behavior of OBSCURE in terms of classification accuracy, computational efficiency and scalability. We implemented our algorithm in MATLAB, in the DOGMA
library (Orabona, 2009). We focus on the multiclass loss ℓMC , being it much harder to be optimized
than the binary hinge loss ℓHL , especially in the MKL setting. Although our MATLAB implementation 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 data sets containing large numbers of categories and lots of training samples. Except in the synthetic experiment where we set p = 1.0001, in
all the other experiments the parameter p is chosen from the set {1.01, 1.05, 1.10, 1.25, 1.50, 1.75, 2}.
1
The regularization parameter λ is set through CV, as CN, where C ∈ {0.1, 1, 10, 100, 1000}.
We compare our algorithm with the binary SILP algorithm (Sonnenburg et al., 2006), themulti class MKL (MC-MKL) algorithm (Zien and Ong, 2007) and the p-norm MKL algorithm(Kloft et al., 2009), all of them implemented in the SHOGUN-0.9.2 toolbox.3 For p-norm MKL,
it is possible to convert from our p setting to the equivalent setting in Kloft et al. (2009) using
pp-norm = pOBSCURE /(2 − pOBSCURE ). In our experiments, we will compare between OBSCURE andp-norm MKL using the equivalent p parameter. We also compare with the SimpleMKL algorithm4 (Rakotomamonjy et al., 2008). To train with the unweighted sum of the kernels with an
SVM, we use LIBSVM (Chang and Lin, 2001). The cost parameter is selected from the range
C ∈ {0.1, 1, 10, 100, 1000} for all the baseline methods. For all the binary classification algorithms,
we use the 1-vs-All strategy for their multiple class extensions.
In the following we start by briefly introducing the data sets used in our experiments. Then we
present a toy problem on a synthetic data which shows that it is more appropriate to use a multiclassloss instead of dividing the multiclass classification problem into several binary subproblems. We
3. Available at http://www.shogun-toolbox.org, implemented in C++.
4. Available at http://asi.insa-rouen.fr/enseignants/˜arakotom/code/mklindex.html, implemented in
MATLAB. SimpleMKL is more efficient than SILP when uses the same SVM solver (Rakotomamonjy et al., 2008).
However, in practice, no efficient SimpleMKL implementation is available. SILP runs much faster compared to SimpleMKL, especially when the size of the problem grows. Moreover, the performance of SimpleMKL and SILP are
the same because both algorithm solve an equivalent optimization problem (Rakotomamonjy et al., 2008). Therefore,
we only use SILP algorithm as our l1 -norm MKL baseline in experiments whose size of training samples are large
than 1000.

178

M ULTI K ERNEL L EARNING WITH O NLINE -BATCH O PTIMIZATION

then study the convergence rate of OBSCURE and compare it with the original Pegasos algorithm(Shalev-Shwartz et al., 2007; Shalev-Shwartz and Srebro, 2008) as well as the p-norm MKL (Kloft
et al., 2009) (Section 5.3). Following that, we study the behaviors of OBSCURE w.r.t different
value of p and different number of input kernels (Sections 5.5 and 5.6). Finally we show thatOBSCURE achieves state-of-art performance on a challenging image classification task with 102
different classes, and we show its scalability.
5.1 Data Sets
We first briefly introduce the data sets used in this section, and we describe how their kernel matrices
are generated.
5.1.1 T HE OXFORD F LOWER DATA S ET (N ILSBACK AND Z ISSERMAN , 2006)
contains 17 different categories of flowers. Each class has 80 images with three predefined splits(train, validation and test). The authors also provide 7 precomputed distance matrices.5 These
distance matrices are transformed into kernel using exp(−γ−1 d), where γ is the average pairwise
distance and d is the distance between two examples. It results in 7 different kernels.
5.1.2 T HE P ENDIGITS DATA S ET (G ÖNEN AND A LPAYDIN , 2010)
is on pen-based digit recognition (multiclass classification with 10 classes) and contains four different feature representations.6 The data set is split into independent training and test sets with 7494
samples for training and 3498 samples for testing. We have generated 4 kernel matrices, one matrix
for each feature, using an RBF kernel, exp(−γ−1 kxi − x j k2 ). For each feature, γ is equal to theaverage of the squared pairwise distances between the examples.
5.1.3 T HE KTH-IDOL2 DATA S ET (P RONOBIS ET AL ., 2010)
contains 24 image sequences acquired using a perspective camera mounted on two mobile robot
platforms. These sequences were captured with the two robots moving in an indoor laboratoryenvironment consisting of five different rooms under various weather and illumination conditions(sunny, cloudy, and night) and across a time span of six months. For experiments, we used the same
setup described in Pronobis et al. (2010); Jie et al. (2010a). We considered the 12 sequences acquiredby robot Dumbo, and divided them into training and test sets, where each training sequence has acorresponding one in the test sets captured under roughly similar conditions. In total, we considered
twelve different permutations of training and test sets. The images were described using three visualdescriptors and a geometric feature from the Laser Scan sensor, as in Jie et al. (2010a), which forms
4 kernels in total.
5.1.4 T HE C ALTECH -101 DATA S ET (F EI -F EI ET AL ., 2004)
is a standard benchmark data set for object categorization. In our experiments, we used the precomputed features and kernels of Gehler and Nowozin (2009b) which the authors made available
on their website,7 with the same training and test split. This allows us to compare against them
5. Available at www.robots.ox.ac.uk/˜vgg/research/flowers/.
6. Available at http://mkl.ucsd.edu/dataset/pendigits.
7. Available at www.vision.ee.ethz.ch/˜pgehler/projects/iccv09/.

179

O RABONA , J IE AND C APUTO

directly. Following that, we report results using all 102 classes of the Caltech-101 data set using
five splits. There are five different image descriptors, namely, PHOG Shape Descriptors (PHOG)(Bosch et al., 2007), Appearance Descriptors (App) (Lowe, 2004), Region Covariance (RECOV)(Tuzel et al., 2007), Local Binary Patterns (LBP) (Ojala et al., 2002) and V1S+ (Pinto et al., 2008).
All of them but the V1S+ features were computed in a spatial pyramid as proposed by Lazebnik
et al. (2006), using several different setup of parameters. This generates several kernels (PHOG, 8
kernels; App, 16 kernels; RECOV, 3 kernels; LBP 3 kernels; V1S+, 1 kernels). We also compute a
subwindow kernel, as proposed by Gehler and Nowozin (2009a). In addition to the 32 kernels, theproducts of the pyramid levels for each feature results in other 7 kernels, for a total of 39 different
kernels For brevity, we omit the details of the features and kernels and refer to Gehler and Nowozin(2009a,b).
5.1.5 T HE MNIST DATA S ET (L E C UN ET AL ., 1998)
is a handwritten digits data set. It 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 four square blocks(14 × 14) and obtained an input vector from each block. We used three kernels on each block: alinear kernel, a polynomial kernel and a RBF kernel, resulting in 12 kernels.
5.2 Multiclass Synthetic Data
Multiclass problems are often decomposed into several binary sub-problems using methods like
1-vs-All, however solving the multiclass learning problem jointly using a multiclass loss can yieldmuch sparser solutions. Intuitively, when a l1 -norm is used to impose sparsity in the domain of kernels, different subsets of kernels can be selected for the different binary classification sub-problems.
Therefore, the combined multiclass classifier might not obtain the desired properties of sparsity.
Moreover, the confidence outputs of the binary classifiers may not lie in the same range, so it is notclear if the winner-takes-all hypothesis is the correct approach for combing them.
To prove our points, we have generated a 3-classes classification problem consisting of 300
samples, with 100 samples for 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) fromthe other two, while Kernel 4 can separate all the 3 classes. The corresponding kernel combination
weights obtained by the SILP algorithm using the 1-vs-All extension and our multiclass OBSCURE
are shown in Figure 1 (bottom). It can be observed that each of the binary SILP classifiers pick two
kernels. OBSCURE selects only the 4th kernel, achieving a much sparser solution.
5.3 Comparison with 1t Learning Rate
We have compared OBSCURE with a simple one-stage version that uses a 1t learning rate. This canbe obtained setting st = 0, ∀t, in Algorithm 2. It can be considered as a straightforward extensionof the original Pegasos algorithm (Shalev-Shwartz et al., 2007; Shalev-Shwartz and Srebro, 2008)
to the MKL problem of (5), so we denote it Pegasos-MKL.
We first compare the running time performance between OBSCURE and Pegasos-MKL on the
Oxford flowers data set. Their generalization performance on the testing data (Figure 2(Top, left)) as
well as the value of the objective function (Figure 2(Top, right)) are shown in Figure 2. In the same
Figure, we also present the results obtained using SILP, SimpleMKL, p-norm MKL and MC-MKL.
180

M ULTI K ERNEL L EARNING WITH O NLINE -BATCH O PTIMIZATION

Kernel 1

Kernel 2

Kernel 4

Kernel 3

0

0

0

0

50

50

50

50

100

100

100

100

1

0.9

150

sample−id150sample−idsample−idsample−id

0.8

150

0.7

0.6

150

0.5

0.4

200

200

200

200

250

250

250

250

0.3

0.2

0.1

300
0

50

100

150
sample−id

200

250

300
0

300

50

SLIP (Class 3 vs. Class 1+2)

100

150
sample−id

200

250

300
0

300

50

SLIP (Class 1 vs. Class 2+3)

0.7

100

150
sample−id

200

250

300

300
0

SLIP (Class 2 vs. Class 1+3)

0.7

50

100

150
sample−id

200

250

300

OBSCURE (Class 1 vs. Class 2 vs. Class 3)

0.7

1
0.9

0.6

0.6

0.6

0.5

0.5

0.5

0.4

0.4

0.4

0.3

0.7
0.6
Weights

0.3

Weights

Weights

Weights

0.8

0.3

0.2

0.2

0.2

0.1

0.1

0.1

0.5
0.4
0.3
0.2
0.1

0

Kernel 1

Kernel 2

Kernel 3

Kernel 40

Kernel 1

Kernel 2

Kernel 3

Kernel 40

Kernel 1

Kernel 2

Kernel 3

Kernel 40

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 OBSCURE (last figure).

We see that OBSCURE converges much faster compared to Pegasos-MKL. This proves that, as
stated in Theorem 3, OBSCURE has a better convergence rate than Pegasos-MKL, as well as fasterrunning time than SILP and SimpleMKL. Note that all the feature combination methods achieve
similar results on this data set.
Similar results are shown in Figure 2(Bottom, left) and (Bottom, right) on the Pendigits data sets.
5.4 Comparison with p-norm MKL and Other Baselines
We compare OBSCURE with p-norm MKL (Kloft et al., 2009). Figure 3 reports the results obtained by both algorithms for varying values of p on the Pendigits data set. We can see that all thealgorithms (OBSCURE, SILP and p-norm MKL) are order of magnitudes faster than MC-MKL.
OBSCURE and p-norm MKL achieve similar performance, but OBSCURE achieve optimal performance in a training time much faster (101 and 102 ). The performance of SILP and p-norm MKL
are quite close, and their classification rate seems to be more stable on this data set. The difference
between OBSCURE and p-norm MKL may be due to the different types of multi class extension
they use.
5.5 Experiments with Different Values of p
This experiment aims at showing the behavior of OBSCURE for varying value of p. We considerp ∈ (1, 2], and train OBSCURE on the KTH-IDOL2 and Caltech-101. The results for the two data
sets are shown in Figure 4 (top).
For the IDOL2 data set (Figure 4 (top, left)), the best performance is achieved when p is large,
which corresponds to give all the kernels similar weights in the decision. On the contrary, a sparse
181

O RABONA , J IE AND C APUTO

Flowers (40 examples per class, 7 kernels)

2

90

OBSCURE p=1.05
Pegasos−MKL p=1.05

110

objective function

80
classification rate

Flowers (40 examples per class, 7 kernels)

10

70
60
OBSCURE p=1.05
Pegasos−MKL p=1.05
SILP
SimpleMKL
p−norm p=1.11
MC−MKL

50
40
0

−1

10

−2

10

−3

10

−4

10

1

10

0

10

4

10

5

10

10

traininig time (seconds)

number of iterations

Pendigits (4 kernels)

Pendigits (4 kernels)

100

OBSCURE p=1.01
Pegasos−MKL p=1.01

210
objective function

classification rate

80

60

40
OBSCURE p=1.01
Pegasos−MKL p=1.01
SILP
p−norm p=1.02
MC−MKL

20

0 0
10

1

10

2

3

10
10
training time (seconds)

0

10

−2

10

4

4

10

10

6

10

8

10

number of iterations

Figure 2: Comparison of running time performance (Left) and objective function value (Right) on
the Oxford flowers data set (Top) and Pendigits data set (Bottom).

solution achieves lower accuracy. It indicates that all the kernels carry discriminative information,and excluding some of them can decrease the performance.
For the Caltech-101 data set (Figure 4 (top, right)), following Gehler and Nowozin (2009b), we
consider four PHOG (Bosch et al., 2007) kernels computed at different spatial pyramid level. It
can be observed that by adjusting p it is possible to improve the performance—sparser solutions(i.e., when p tends to 1) achieve higher accuracy compared to non-sparse solutions (when p tendsto 2). However, the optimal p here is 1.10. In other words the optimal performance is achieved fora setting of p different from 1 or 2, fully justifying the presence of this parameter.
Furthermore, Figure 4 (bottom) shows the running time of OBSCURE using the same four
kernels, with varying values of p. The dashed lines in the figure correspond to the results obtainedby the first online stage of the OBSCURE algorithm. It can be observed that the online stage of
OBSCURE converges faster when p is large, and this is consistent with Theorem 4. The online step182

M ULTI K ERNEL L EARNING WITH O NLINE -BATCH O PTIMIZATION

Pendigits (4 kernels)

classification rate

97

96.5
OBSCURE p=1.01
OBSCURE p=1.10
OBSCURE p=1.25
OBSCURE p=1.50
OBSCURE p=2.00
SILP
p−norm p=1.02
p−norm p=1.22
p−norm p=1.67
p−norm p=3.00
p−norm p=7.00
MC−MKL

96

95.5

95 0
10

1

10

2

10

3

10

4

10

training time (seconds)

Figure 3: (Best viewed in color.) Comparison of OBSCURE and p-norm MKL with varying valueof p on Pendigits.

of OBSCURE converges in a training time orders of magnitudes faster (101 to 103 ) compared to
the full training stage, and in certain cases (p ≤ 1.10) it can also achieve a performance close to the
optimal solution.
5.6 Experiments on Different Number of Kernels
Figure 5 (left) reports the behavior of OBSCURE for different numbers of input kernels. It showsthat the algorithm achieves a given accuracy in less iterations when more kernels are given. The
dashed line in the figure again corresponds to the results obtained by the first online stage of the
OBSCURE algorithm. Figure 5 (right) shows the number of iterations to converge of the online step,
proving that the convergence rate improves when there are more kernels, as stated in Theorem 4.
5.7 Multiclass Image Classification
In this experiment, we use the Caltech-101 data set with all the 39 kernels, and the results areshown in Figure 6. The best results for OBSCURE were obtained when p is at the smallest value(1.01). This is probably because among these 39 kernels many were redundant or 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. The results support our claim in Section 5.2 that multiclass loss
function is more suitable for this type of problem, as all the methods that use the multiclass loss183

O RABONA , J IE AND C APUTOIDOL2 (4 kernels, 12 training sequences)

Caltech−101 (4 kernels, 30 training examples)

97

58.5
58

96.5

96

classification rateclassification rate

57.5

95.5

95

57
56.5
56
55.5
55

94.5
54.5
94

1

1.1

1.2

1.3

1.4

1.5

1.6

1.7

1.8

1.9

2

54

1

1.1

1.2

1.3

p

1.4

1.5

1.6

1.7

1.8

1.9

2

p

Caltech−101 (4 kernels, 30 training examples)
58
56

classification rate

54
52
50
48
46
p=1.01p=1.10p=1.25p=1.50p=1.75p=2.00

44
42
40

1

2

10

10

3

10

training time (seconds)

Figure 4: Behaviors of the OBSCURE algorithm w.r.t. p: (top, left) the effect of different values ofp on the IDOL2 data set and (top, right) on the Caltech-101 data set using 4 PHOG (Boschet al., 2007) kernels; (bottom) running time for different values of p on Caltech-101 dataset.

outperform SILP and p-norm MKL (p=1.02) using 1-vs-All strategy. MC-MKL is computationallyinfeasible for 30 sample per category. Its significant gap from OBSCURE seems to indicate thatit stops before converging to the optimal solution. Figure 6 (left) reports the training time fordifferent algorithms. Again, OBSCURE reaches optimal solution much faster than the other threebaseline algorithms which are implemented in C++. Figure 6 (right) reports the results obtained184

M ULTI K ERNEL L EARNING WITH O NLINE -BATCH O PTIMIZATION

Caltech−101 (p=1.01, 30 training examples)
1.95# of iterations to converge of the online step

77
76

classification rate

75
74
73
72
71

5 kernels
10 kernels
20 kernels
30 kernels
39 kernels

70
69
68

5

x 10

1.94
1.93
1.92
1.91
1.9
1.89
1.88
1.87
1.86
5

6

10

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

6

78

10

10

15

20

25

30

35

40

number of kernels

number of iterations

Figure 5: Behaviors of the OBSCURE algorithm w.r.t. the number of kernels: (left) the effect ofdifferent number of kernels randomly sampled from the 39 kernels; (right) number of
iterations to converge of the online stage.

Caltech−101 (5−30 training examples, 39 kernels)
80

70

75

60

70

50
40
OBSCURE: 5 examples
OBSCURE 15 examples
OBSCURE 30 example
SILP: 5 examples
SILP: 15 examples
SILP: 30 examples
p−norm MKL: 5 examples
p−norm MKL: 15 examples
p−norm MKL: 30 examples
MC−MKL: 5 examples
MC−MKL: 15 examples

30
20
10
0

0

10

2

10

classification rateclassification rate

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

65

60

55

50

45

40

4

10

training time (seconds)

Average Kernel
SILP
p−norm MKL p=1.02
MC−MKLOBSCURE Online
OBSCURE Batch

5

10

15

20

25

30

# training examples

Figure 6: Performance comparison on Caltech-101 using different MKL methods.
using different combination methods for varying size of training samples. It is also interesting
to note the performance of the solution generated by the online step of OBSCURE, denoted by“OBSCURE Online”, that is very close to the performance of the full training stage, as alreadynoted above.
5.8 Scalability
In this section, we report the experiments on the MNIST data set using varying sizes of training
samples. Figure 7 shows the generalization performance on the test set achieved by OBSCURE
over time, for various training size. We see that OBSCURE quickly produces solutions with good185

O RABONA , J IE AND C APUTOMNIST (p=1.10, 12 kernels)
60
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

50

error rate

40
30
20
10
0

−1

10

0

10

1

2

10

10

3

10

4

10

training time (seconds)

Figure 7: The generalization performance of MNIST data set over different size of training samples.

performance. The performance of the SVM trained using the unweighted sum of the kernels andthe best kernel are also plotted. Notice that in the figure we only show the results of up to 20,000
training samples for the sake of comparison, otherwise we could not cache all the 12 kernels inmemory. However, by computing the kernel “on the fly” we are able to solve the MKL problem
using the full 60,000 examples: OBSCURE obtains 1.95% error rate after 10 epochs, which is
0.45% lower compared to the results obtained by OBSCURE with 20,000 training samples after
500 epochs.

6. Conclusions and Discussion
This paper presents OBSCURE, a novel and efficient algorithm for solving p-norm MKL. It uses
a hybrid two-stages online-batch approach, optimizing the objective function directly in the primal
with a stochastic sub-gradient descent method. Our minimization method allows us to prove convergence rate bounds, proving that the number of iterations required to converge is independent of thenumber of training samples, and, when a sparse solution is induced, is sub-linear in the number ofkernels. Moreover we show that OBSCURE has a faster convergence rate as the number of kernels
grows.
Our approach is general, so it can be used with any kind of convex losses, from binary losses tostructure output prediction (Tsochantaridis et al., 2004), and even to regression losses.
Experiments show that OBSCURE achieves state-of-art performance on the hard problem ofmulticlass MKL, with smaller running times than other MKL algorithms. Furthermore, the solution
found by the online stage is often very close to the optimal one, while being computed several ordersof magnitude faster.

Acknowledgments186

M ULTI K ERNEL L EARNING WITH O NLINE -BATCH O PTIMIZATIONThe 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.

Appendix A.
The following algorithm and Lemma can in found in Orabona and Crammer (2010), stated for thebinary case. Here we state them for generic convex losses and report them here for completeness.
Algorithm 4 Prediction algorithm
1: Input: A series of strongly convex functions h1 , . . . , hT .
2: Initialize: θ1 = 0
3: for t = 1, 2, . . . , T do
4:
Receive xt
5:
Set wt = ∇ht∗ (θt )6:zt = ∂ℓt (wt )7:
θt+1 = θt − ηt zt
8: end forLemma 5 Let ht ,t = 1, . . . , T be βt -strongly convex functions with respect to the norms k·kh1 , . . . , k·
khT over a set S and let k · kh∗i be the respective dual norms. Let h0 (0) = 0, and x1 , . . . , xT be an
arbitrary sequence of vectors in Rd . Assume that algorithm in Algorithm 4 is run on this sequencewith the functions hi . If hT (λu) ≤ λ2 hT (u), and ℓ satisfiesℓ(u, xt , yt ) ≥ 1 + u⊤ ∂ℓt (wt ), ∀u ∈ S, wt : ℓt (wt ) > 0,then for any u ∈ S, and any λ > 0 we haveT1∑ ηt ≤ L + λhT (u) + λ
t=1

T

D+ ∑

t=1



ηt2
kzt k2ht∗ − ηt wt⊤ zt
2βt

!

,

T
∗ (θ )). In particular, choosing the optimal(ht∗ (θt ) − ht−1
where L = ∑t∈M ∪U ηt ℓt (u), and D = ∑t=1
t
λ, we obtain
s

T
T  2
p
ηt
2
⊤
∑ ηt ≤ L + 2hT (u) 2D + ∑ βt kzt kht∗ − 2ηt wt zt .
t=1
t=1

References
F. R. Bach, G. R. G. Lanckriet, and M. I. Jordan. Multiple kernel learning, conic duality, and the
SMO, algorithm. In Proc. of the International Conference on Machine Learning, 2004.
P. Bartlett, E. Hazan, and A. Rakhlin. Adaptive online gradient descent. In Advances in Neural
Information Processing Systems 20, pages 65–72. MIT Press, Cambridge, MA, 2008.
A. Beck and M. Teboulle. Mirror descent and nonlinear projected subgradient methods for convex
optimization. Operations Research Letters, 31(3):167–175, 2003.
187

O RABONA , J IE AND C APUTO

A. Bosch, A. Zisserman, and X. Munoz. Representing shape with a spatial pyramid kernel. In Proc.
of the 6th ACM International Conference on Image and Video Retrieval, pages 401–408. ACM,
July 2007.
S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
G. Cavallanti, N. Cesa-Bianchi, and C. Gentile. Linear algorithms for online multitask classification.
In Proc. of the 21st Conference on Learning Theory, 2008.
C. C. Chang and C. J. Lin. LIBSVM: A Library for Support Vector Machines, 2001. Software
available at www.csie.ntu.edu.tw/˜cjlin/libsvm.
C. Cortes, M. Mohri, and A. Rostamizadeh. Two-stage learning kernel algorithms. In Proc. of the27th International Conference on Machine Learning, 2010.
K. Crammer and Y. Singer. On the algorithmic implementation of multiclass kernel-based vector
machines. The Journal of Machine Learning Research, 2:265–292, 2002.
N. Cristianini and J. Shawe-Taylor. An Introduction to Support Vector Machines and Other KernelBased Learning Methods. Cambridge University Press, 2000.
N. Cristianini, J. Kandola, A. Elisseeff, and J. Shawe-Taylor. On kernel-target alignment. In Advances in Neural Information Processing Systems 14, volume 14, pages 367–373, 2002.
C. B. Do, Q. V. Le, and Chuan-Sheng Foo. Proximal regularization for online and batch learning.
In Proc. of the International Conference on Machine Learning, 2009.
L. Fei-Fei, R. Fergus, and P. Perona. One-shot learning of object categories. IEEE Transactions on
Pattern Analysis and Machine Intelligence, 28(4):594–611, 2004.
P. Gehler and S. Nowozin. Let the kernel figure it out: Principled learning of pre-processing forkernel classifiers. In Proc. of the IEEE Conference on Computer Vision and Pattern Recognition,
2009a.
P. Gehler and S. Nowozin. On feature combination for multiclass object classification. In Proc. of
the International Conference on Computer Vision, 2009b.
M. Gönen and E. Alpaydin. Cost-conscious multiple kernel learning. Pattern Recognition Letters,
31:959–965, July 2010.
D. Hush, P. Kelly, C. Scovel, and I. Steinwart. QP algorithms with guaranteed accuracy and run
time for support vector machines. Journal of Machine Learning Research, 7:733–769, 2006.
L. Jie, F. Orabona, and B. Caputo. An online framework for learning novel concepts over multiple
cues. In H. Zha, R. Taniguchi, and S. J. Maybank, editors, Computer Vision - ACCV 2009, 9thAsian Conference on Computer Vision, Xi’an, China, September 23-27, 2009, Revised Selected
Papers, Part I, volume 5994 of Lecture Notes in Computer Science, Berlin / Heidelberg, 2010a.
Springer.
188

M ULTI K ERNEL L EARNING WITH O NLINE -BATCH O PTIMIZATION

L. Jie, F. Orabona, M. Fornoni, B. Caputo, and N. Cesa-Bianchi. OM-2: An online multi-classmulti-kernel learning algorithm. In 4th IEEE Online Learning for Computer Vision Workshop (inCVPR10). IEEE Computer Society, June 2010b.
R. Jin, S. C. H. Hoi, and T. Yang. Online multiple kernel learning: Algorithms and mistake bounds.
In Proc. of the 21st International Conference on Algorithmic Learning Theory, pages 390–404,
2010.
T. Joachims. Making large-scale SVM learning practical. In Advances in Kernel Methods – Support
Vector Learning, pages 169–185. MIT Press, 1999.
S. Kakade, S. Shalev-Shwartz, and A. Tewari. On the duality of strong convexity and strong smoothness: Learning applications and matrix regularization. Technical report, TTI, 2009.
M. Kloft, U. Brefeld, S. Sonnenburg, P. Laskov, K.-R. Müller, and A. Zien. Efficient and accurateℓ p -norm multiple kernel learning. In Advances in Neural Information Processing Systems 22,
pages 997–1005, 2009.
G. Lanckriet, N. Cristianini, P. Bartlett, and L. E. Ghaoui. Learning the kernel matrix with semidefinite programming. Journal of Machine Learning Research, 5:27–72, 2004.
S. Lazebnik, C. Schmid, and J. Ponce. Beyond bags of features: Spatial pyramid matching forrecognizing natural scene categories. In Proc. of the IEEE Conference on Computer Vision and
Pattern Recognition, 2006.
Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document
recognition. Proceedings of the IEEE, 86:2278–2324, 1998.
D. Lowe. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, 60(2):91–110, 2004.
C. A. Micchelli and M. Pontil. Learning the kernel function via regularization. Journal of Machine
Learning Research, 6:1099–1125, December 2005.
J. S. Nath, G. Dinesh, S. Ramanand, C. Bhattacharyya, A. Ben-Tal, and K. R. Ramakrishnan. On thealgorithmics and applications of a mixed-norm based kernel learning formulation. In Advancesin Neural Information Processing Systems 22, pages 844–852, 2009.
M. E. Nilsback and B. Caputo. Cue integration through discriminative accumulation. In Proc. of
the IEEE Conference on Computer Vision and Pattern Recognition, 2004.
M.-E. Nilsback and A. Zisserman. A visual vocabulary for flower classification. In Proc. of theIEEE Conference on Computer Vision and Pattern Recognition, 2006.
T. Ojala, M. Pietikaäinen, and T. Maäenpaäaä. Multiresolution gray-scale and rotation invariant
texture classification with local binary patterns. IEEE Transactions on Pattern Analysis andMachine Intelligence, 24(7):971–987, 2002.
F. Orabona. DOGMA: a MATLAB toolbox for Online Learning, 2009. Software available at http://dogma.sourceforge.net.
189

O RABONA , J IE AND C APUTO

F. Orabona and K. Crammer. New adaptive algorithms for online classification. In Advances in
Neural Information Processing Systems, December 2010.
F. Orabona, L. Jie, and B. Caputo. Online-batch strongly convex multi kernel learning. In Proc. ofthe 23rd IEEE Conference on Computer Vision and Pattern Recognition, June 2010.
N. Pinto, D. D. Cox, and J. J. Dicarlo. Why is real-world visual object recognition hard? PLoS
Computational Biology, 4(1), January 2008.
J. C. Platt. Fast training of support vector machines using sequential minimal optimization. In
Advances in Kernel Methods – Support Vector Learning, pages 185–208. MIT Press, 1999.
A. Pronobis, J. Luo, and B. Caputo. The more you learn, the less you store: Memory-controlled
incremental SVM for visual place recognition. Image and Vision Computing (IMAVIS), Special
Issue on Online Pattern Recognition and Machine Learning Techniques for Computer-Vision:
Theory and Applications, 28(7):1080–1097, July 2010.
A. Rakotomamonjy, F. R. Bach, S. Canu, and Y. Grandvalet. SimpleMKL. Journal of Machine
Learning Research, 9:2491–2521, November 2008.
E. Rubinstein. Support vector machines via advanced optimization techniques. Technical report,
Masters thesis, Faculty of Electrical Engineering, Technion, Nov 2005.
C. Sanderson and K. K. Paliwal. Identity verification using speech and face information. Digital
Signal Processing, 14(5):449–480, 2004.
S. Shalev-Shwartz and Y. Singer. Logarithmic regret algorithms for strongly convex repeated games.
Technical Report 2007-42, The Hebrew University, 2007.
S. Shalev-Shwartz and N. Srebro. SVM, optimization: inverse dependence on training set size. In
Proc. of the International Conference on Machine Learning, 2008.
S. Shalev-Shwartz, Y. Singer, and N. Srebro. Pegasos: Primal estimated sub-gradient solver forsvm. In Proc. of the International Conference on Machine Learning, 2007.
S. Sonnenburg, G. Rätsch, and C. Schäfer. Learning interpretable SVMs for biological sequenceclassification. In Research in Computational Molecular Biology, 9th Annual International Conference, RECOMB 2005, Cambridge, MA, USA, May 14-18, 2005, Proceedings, volume 3500 of
Lecture Notes in Computer Science, pages 389–407. Springer, 2005.
S. Sonnenburg, G. Rätsch, C. Schäfer, and B. Schölkopf. Large scale multiple kernel learning.
Journal of Machine Learning Research, 7:1531–1565, December 2006.
R. Tomioka and T. Suzuki. Sparsity-accuracy trade-off in MKL, 2010. URL http://arxiv.org/
abs/1001.2615.
I. Tsochantaridis, T. Hofmann, T. Joachims, and Y. Altun. Support vector machine learning forinterdependent and structured output spaces. In Proc. of the International Conference on Machine
Learning, 2004.
190

M ULTI K ERNEL L EARNING WITH O NLINE -BATCH O PTIMIZATIONO. Tuzel, F. Porikli, and P. Meer. Human detection via classification on Riemannian manifolds. In
Proc. of the IEEE Conference on Computer Vision and Pattern Recognition, 2007.
M. Varma and B. R. Babu. More generality in efficient multiple kernel learning. In Proc. of theInternational Conference on Machine Learning, 2009.
S. V. N. Vishwanathan, Z. Sun, N. Theera-Ampornpunt, and M. Varma. Multiple kernel learningand the SMO algorithm. In Advances in Neural Information Processing Systems, December 2010.
D. H. Wolpert. Stacked generalization. Neural Networks, 5(2):241–259, 1992.
Z. Xu, R. Jin, I. King, and M. R. Lyu. An extended level method for efficient multiple kernel
learning. In Advances in Neural Information Processing Systems 21, pages 1825–1832, 2008.
M. Yuan and Y. Lin. Model selection and estimation in regression with grouped variables. Journalof the Royal Statistical Society, 68:49–67, 2006.
A. Zien and C. S. Ong. Multiclass multiple kernel learning. In Proc. of the International Conference
on Machine Learning, 2007.

191