OM-2: An Online Multi-class Multi-kernel Learning Algorithm
Luo Jie∗† , Francesco Orabona‡ , Marco Fornoni∗† , Barbara Caputo∗ , Nicolò Cesa-Bianchi‡∗
Idiap Research Institute, 1920 Martigny, Switzerland†
Swiss Federal Institute of Technology in Lausanne (EPFL), 1015 Lausanne, Switzerland‡
DSI, Università degli Studi di Milano, 20135 Milan, Italy
jluo@idiap.ch, francesco@orabona.com, mfornoni@idiap.ch
bcaputo@idiap.ch, cesa-bianchi@dsi.unimi.it

Abstract

often means re-training from scratch.
A framework for learning algorithms designed with aclear focus on incremental learning and scalability is online
learning [4]. The algorithms developed in the online learning framework are designed so that their current model canbe efficiently updated after each sample is received. The
time needed for each update is small, typically at most linear in the number of observed examples. In online learning there is no distinction between a training and a testing
phase: learning proceeds sequentially and the knowledge
is continuously exploited and updated. More specifically,at each time step the system is presented with a new input
vector and uses the current model to predict the associatedlabel. The correct label is then revealed, and the system canupdate the model based on the received feedback. The goal
is to minimize the number of prediction mistakes, regardlessof the mechanism generating the samples. For this reason
the online learning framework is suitable to model situations in which that i.i.d. assumption on the samples is notrealistic. Yet, in case the data are really i.i.d., it is still possible to have algorithms with the same (or better) statisticalguarantees as the batch algorithms. In this sense, the online
learning scenario is both harder and more general than thebatch one.
Online learning algorithms have been successfully applied to many computer vision tasks where the amount ofdata is so big [5, 13] that standard batch algorithms would
have unacceptably long training times. On the other hand,the practical performance of online learning algorithms is
usually lower compared to batch methods. Ideally, we
would like to get best of both worlds, i.e., high performanceand fast computation w.r.t. sample size.
The current state-of-the-art methods for object categorization are based on the combination of multiple discriminative and robust features via machine learning techniques [11, 18, 26, 27]. Among these approaches, Multi
Kernel Learning (MKL) [18, 26, 27] has attracted considerable attention. However, even if many attempts have been

Efficient learning from massive amounts of information
is a hot topic in computer vision. Available training setscontain many examples with several visual descriptors, asetting in which current batch approaches are typically slow
and does not scale well. In this work we introduce a theoretically motivated and efficient online learning algorithm
for the Multi Kernel Learning (MKL) problem. For thisalgorithm we prove a theoretical bound on the number ofmulticlass mistakes made on any arbitrary data sequence.
Moreover, we empirically show that its performance is onpar, or better, than standard batch MKL (e.g. SILP, SimpleMKL) algorithms.

1. Introduction
A common trend in computer vision research is the exploitation of massive amounts of information to achieve a
performance increase. In particular, learning from huge collections of labeled images collected from the Web, and using multiple discriminative features, has led to a significant
boost of performance on problems considered very hard formany years (for example, see [8, 11, 27] and references
therein). Yet, current classification batch algorithms, suchas Support Vector Machines (SVM), do not scale well withthe training set size. For this reason, researchers are constantly looking for new ways of learning efficiently fromlarge-scale datasets.
A further issue hampering the application of batch learning to vision is that many computer vision problems are intrinsically sequential; e.g., applications with “human in theloop” in robotic vision [10, 16] and computer vision [14]. In
these problems the system is primed on a small dataset, andthen keeps updating its current model as more data are acquired (often through an interaction with the user). This is
in contrast with batch algorithms, where updating the model1

made to speed up the training process [21, and references
therein], this approach is still slow and does not scale to big
datasets. Some recent work has tried to address this problem using online learning method. Cavallanti et. al. [3] proposed a p-norm multiview Perceptron. However, they assume that all the cues live in the same space, meaning thatsame kernel must be used on all the cues. Jie et. al. [15]present a wrapper algorithm using a two-layer structure,
which can use most of the known online learning methods
as base algorithms. The specific version proposed in [15]has a bounded memory complexity, but there is neither mistake bound nor convergence guarantee.
In this paper, we first introduce a generalization of themulti-class MKL learning problem that allows to tune thelevel of sparsity of the solution in the domain of the kernels.
This enable us to design a theoretically motivated online
learning algorithm, which we call OM-2 for Online Multiclass Multi-kernel, with a guaranteed mistake bound on any
individual data sequence. OM-2 achieves state-of-the-art
performance for online algorithms on standard benchmark
databases. We also show that in the traditional train/test
setup, OM-2 achieves a performance close to MKL batchalgorithms while requiring an update time linear in the number of past examples.
In the next section we describe the online learning framework and the building blocks that we use in our online MKL
architecture (Section 2 and 3). Section 4 describes our experimental findings. Section 5 contains the conclusions.

2. Preliminaries
In this section we first formally define the multiclass online learning problem and the p-norm MKL framework. We
start by introducing some basic notions of classification andconvex analysis.
In the following bold letters are used to denote theelements of a linear space (e.g., vectors x in Rd ).
Let (x1 , y1 ), . . . , (xT , yT ) be a sequence of examples(instances-label pairs), with (xt , yt ) ∈ X × Y, where yt ∈Y = {1, . . . , M } and M ≥ 2.
Multi-class classification.
fiers of the form

We consider multiclass classi-ỹ(x) = argmax s(x, y)function φ maps the examples into a reproducing kernel
Hilbert space (of arbitrarily high dimensionality) whose
inner product is implemented by the associated kernel,
K (x, y), (x0 , y 0 ) = φ(x, y) · φ(x0 , y 0 ). With multiple cues, we have F feature maps φ1 , . . . , φF and F kernels K 1 , . . . , K F , where K i (x, y), (x0 , y 0 ) = φi (x, y) ·φi (x0 , y 0 ) for each i = 1, . . . , F . In our multiclass setup,
for each y = 1, . . . , M we define(2)φj (x, y) = 0, . . . , 0, ψ j (x), 0, . . . , 0| {z }ywhere ψ j (·) is a label-independent feature map. Similarly,
w consists of M blocks, w1 , . . . , wM . Hence, by construction, w · φj (x, y) = wy · ψ j (x).
Loss Function. We introduce the following“bar” nota
tion φ̄(x, y) = φ1 (x, y), . . . , φF (x, y) and, similarly,w̄ = w1 , w2 , . . . , wF , where each wj is a M -block vec
tor wj1 , . . . , wjM . Consider the following multiclass loss
function [10]` (w̄, x, y) = max
1 − w̄ · (φ̄(x, y) − φ̄(x, y 0 )) +
0
y 6=y

(3)

where |t|+ = max{t, 0}. This loss function is convex andupper bounds the multiclass misclassification loss.
p-norms. A generic norm of a vector w is indicated by
kwk, its dual norm is indicated by kwk∗ . For w ∈ Rd andp ≥ 1, we denote by kwkp the p-norm of w, where kwkp =
P
1/p
d
p
. The dual norm of k · kp is k · kq , wherei=1 |wi |p and q are dual coefficients; i.e., they satisfy 1/p + 1/q =1. In the following, p and q always denote a pair of dual
coefficients.
Group Norm. We can define the (2, p)-group normkw̄k2,p of w̄ as
kw̄k2,p :=kw1 k2 , kw2 k2 , . . . , kwF k2



.
p

(4)

This is the p-norm of the vector whose elements are the 2norms of the vectors w1 , . . . , wF . Note that the dual normof k · k2,p is k · k2,q [17].

(1)

y∈Y

where s(x, y) is the value of the score function when instance x is assigned to class y. Hence, the predicted classỹ(x) in (1) is the class achieving the highest score.
We use linear1 score functions s(x, y) = w · φ(x, y),where w are the linear parameters and φ is a kernel feature map jointly defined on X × Y —see, e.g., [10]. The
1 For simplicity we will not use the bias, it can be easily added by modifying slightly the feature map.

Sub-gradients and Fenchel conjugate. Given a convex
function h : X → R, its sub-gradient ∂h(v) at v statisfies: ∀u ∈ X, h(u) − h(v) ≥ (u − v) · ∂h(v). The
Fenchel conjugate of h, h∗ : S → R, is defined ash∗ (u) = supv∈S v · u − h(v) .

2.1. Multi Kernel Learning (MKL)The MKL optimization problem was first proposed in [1]and then extended to multiclass classification in [28]. Usingthe group norm notation introduced above, we can define
the MKL [1] problem asTXλ2kw̄k2,1 +min` (w̄, xt , yt )
(5)
w̄
2
t=1

where, as usual, w̄ = w1 , w2 , . . . , wF . The same formulation is used in [25] —see also [21] for equivalent formulations. The (2, 1) group norm induces sparsity in thedomain of the kernels. This means that the solution of (5)tends to depend on a small subset of the F kernels.
Even if enforcing sparsity is desirable in many applications, in some cases it could lead to a decrease in performance. For this reason, problem (5) has been recently generalized to p-norms in [19]. This allows to finely tune thelevel of sparsity needed for the task at hand. In fact, theauthors show that in computational biology problems MKL
achieves higher accuracies using (2, p) group norms withp > 1 [19]. In this paper we propose to consider the p-norm
problem in the following formulation

min
w̄

T
X
λ
kw̄k22,p +` (w̄, xt , yt )
2
t=1

(6)

where 1 < p ≤ 2. This directly generalizes (5) and is different from the one proposed in [19]. The advantage of (6) isthat the objective function is λ/q-strongly convex [17]. Intuitively, strong convexity measures the minimum curvatureof a function. If a problem has a strongly convex objectivefunction, then it is easier to optimize it. Therefore strong
convexity is a key property for the design of fast online andbatch algorithms [23, 17]. The added parameter p allow us
to decide the level of sparsity of the solution. 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. When p tends to 1, the solution of (6) getsclose to the sparse solution obtained by solving (5), but thestrong convexity vanishes. Setting p equals to 2 corresponds
to using the unweighted sum of the kernels.

2.2. Online Learning
An online algorithm learns by observing the training
examples (x1 , y1 ), (x2 , y2 ), . . . , (xT , yT ) in a sequential
manner. At each round t = 1, 2, . . . , T , the algorithm receives the next instance xt and makes a prediction ỹt . Oncethe algorithm has made its prediction, it observes the correct label yt . Based on the label information the algorithm
may update its current model, thus improving the chances ofmaking accurate predictions in the subsequent rounds. The
quality of the predictions is measured by a given loss function, and the algorithm’s goal is to minimize the cumulativeloss suffered along the sequence of observations.
Note that, contrary to the standard batch learning framework, in online learning there are no stochastic assumption on the data-generating process. In other words, thealgorithm’s performance is measured on each individual sequence of observations, rather than only on those sequencesthat are typical with respect to some underlying probability
distribution. For this reason the performance of online algorithms is usually compared to that of the fixed classifier
performing best on the entire observed data sequence.
An approach to solve the online learning problem is to
use the “Follow the Regularized Leader” framework [22,17]. This corresponds to using at each step the solution of
the optimization problemw̄t+1 = argmin h(w̄) + w̄ · ηw̄

tX∂`(w̄i , xi , yi )

(7)

i=1

where h(w̄) is the regularizer and η > 0 is a parameter.
Intuitively, this amounts to solving at each step a problem
similar to (6), the difference being that the loss function
has been replaced by its subgradient. The linearization of
the loss function through the subgradient provides an efficient closed formula update and allows to prove regretbounds [22, 17]. The solution of the above minimization
problem gives an update of the form!
tX∗w̄t+1 = ∇h −η∂`(w̄i , xi , yi )(8)i=1where h∗ is the Fenchel conjugate of h.
Next, we propose a variant of “Follow the Regularized
Leader” in which the parameter η = ηt is changed at eachtime step. We prove that the cumulative number of mistakes
made on any sequence of T observations is roughly equal
to the optimum value of the MKL problem (6).

3. Algorithm
In this Section we describe the OM-2 algorithm (pseudocode in Algorithm 1) and analyze its performance on
any arbitrary sequence of observations. It is important topoint out that even if we solve the problem in the primal,
we do use nonlinear kernels without computing the nonlinear mapping φ̄(x, y) explicitly. In other words, OM-2 canbe used with any kernel function satisfying Mercers conditions. We briefly outline the approach for implementing it
in Section 3.1.
The design and analysis of this algorithm is based on theframework and machinery developed in [17]. It is similar
to the p-norm matrix Perceptron of [3], but it overcomes
the disadvantage of using the same kernel on each feature.
The regularizer of our online MKL problem is defined byh(w̄) = 2q kw̄k22,p . It can be verified thath∗ (θ̄) =1
kθ̄k22,q2q1∇h (θ ) =q∗jkθ j k2kθ̄k2,q!q−2
θj ,∀j = 1, . . . , F.

Similarly to [3], we prove a mistake bound for Algorithm 1.
We say that the algorithm makes a “mistake” each time theprediction ỹ is different from the true class yt . Algorithm
OM-2 updates the weight w̄t not only at each mistake, butalso when the prediction is correct and the multiclass loss`(w̄t , xt , yt ), is greater than 0. In the following, we showthat this aggressive update strategy improves the theoretical
performance of the algorithm.
We denote by I the set of rounds in which there is no
mistake but there is an update; that is,
I = t : 0 < w̄t · z̄ t < 1 .
Theorem 1. Let (x1 , y1 ), . . . , (xT , yT ) be a sequenceof examples where xt ∈ X, y ∈ Y and such thatφj (xt , yt ) 2 ≤ 1 for j = 1, . . . , F and t = 1, . . . , T .
Then, for any ū, the number of mistakes M of Algorithm
OM-2 satisfies
M ≤C +L+

√

LC −

X

ηt

t∈I

where C = 2qF

2/qkūk22,p and L =PT

t=1 `(ū, xt , yt ).

Proof. Proofs are deferred to Appendix A.
P
Apart from the negative term − t∈I ηt , the bound has
the standard form of mistake bounds for online learning
multiclass algorithms that only update on mistakes [10].
The presence of this negative term theoretically motivates
the use of updates in margin error rounds. Note also thatwhen the problem is linearly separable, the algorithm converges to a solution that has training error equal to zero.
Moreover, when p goes to 1, the term C in the bound has astrongly sublinear dependence on the number of kernels, but
unfortunately q goes to infinity. Similarly to [12], we tradeoff these two terms to obtain a logarithmic dependence on
the number kernels. In particular, we obtain the following
corollary.
Corollary 1. Under the hypotheses of Theorem 1, if p =2 ln(F )2 ln(F )−1 then for any ū, the number of mistakes M of Algorithm OM-2 is less than
√
C +L+

CL −

X

ηt

t∈I

where C = 4e ln(F )kūk22,1 and L =PT

t=1 `(ū, xt , yt ).

Suppose that only one kernel is useful for the classification task at hand while the others F − 1 are irrelevant. With
the optimal tuning of p the price we pay in the bound for notknowing which kernel is the right one is just logarithmic in
their number F .

Algorithm 1 OM-2
1: Input: q
2: Initialize: θ̄ 1 = 0, w̄ 1 = 0
3: for t = 1, 2, . . . , T do
4:
Receive new instance xt
5:
Predict ỹt = argmax w̄t · φ̄(xt , y)y=1,...,M

6:
7:

Receive label yt
Compute ŷt = argmax w̄t · φ̄(xt , y)8:z̄ t = φ̄(xt , yt ) − φ̄(xt , ŷt )

9:


ff
2w̄t ·z̄ tif `(w̄t , xt , yt ) > 0 then ηt = min 1 − kz̄
,
1
k2

y6=yt

10:
11:
12:

t 2,q

else ηt = 0θ̄ t+1 = θ̄ t + ηt z̄ t
„ j
«q−2
kθ
k2
θ jt+1 ,wjt+1 = 1q kθ̄ t+1k
t+1 2,q∀j = 1, · · · , F

13: end for3.1. Implementation
Following [24, Section 4], it is possible to use Mercer
kernels without introducing explicitly the dual formulationof the optimization problem. As θ̄ 1 is initialized
P to thezero
vector,θ̄
canbewritten
as
θ̄
=
t+1
t+1
t ηt z̄ t =
P
η
(
φ̄(x
,
y
)
−
φ̄(x
,
ŷ
)).
Therefore,
thealgorithm
can
t t
t t
t t
easily store ηt , yt , ŷt , and xt instead of storing θ̄ t . Observing line 12 in the algorithm, we have that at each round,
wjt+1 is proportional to θ jt+1 , that is wjt+1 = αtj θ jt+1 .
Hence w̄t+1 can also be represented using αtj ηt , yt , ŷt
and xt . During prediction, the dot product between w̄t+1
and φ̄(xt+1 , yt+1 ) can be expressed as a sum of termsw̄jt+1 · φj (xt+1 , yt+1 ), that can be calculated as
wjt+1 · φj (xt+1 , yt+1 )j= αt+1X

ηt ( φj (xt , yt ) · φj (xt+1 , yt+1 )t− φj (xt , ŷt ) · φj (xt+1 , yt+1 ) )X j= αt+1
ηt K j (xt , yt ), (xt+1 , yt+1 )tj− K (xt , ŷt ), (xt+1 , yt+1 ).

Note that the time spent by the OM-2 algorithm in each stepis dominated by the prediction (line 5). The time required
to execute line 5 is O(St F M ), where St is the number of
updates made before the t-th iteration.

4. Experiments
In this section we present an experimental evaluation of
our approach in two different scenarios, corresponding to
two publicly available databases. The first scenario is about
learning new object categories, and the experiments wereconducted on the Caltech-101 dataset [9]. The second sce-nario is about place recognition for a mobile robot, using
the IDOL2 dataset [16].
We compared the performance of our algorithm to the
OMCL algorithm [15], to the Passive-Aggressive algorithm(PA-I) [7] using the average kernel and the single best feature, and to a batch MKL algorithm [25]2 . We determined
all of our online learning parameters via cross-validation.
The features and kernel parameters were obtained directlyfrom the authors who made this information publicly available [15, 11].
In both experiments we reported the average online training error. This is the number of prediction mistakes the algorithm makes on a given input sequence normalized by
the length of the sequence, which is a standard performancemeasure for online learning algorithms. We also tested thegeneralization performance of our algorithms on a separate
test set, which is similar to the classic batch learning setup.
However, it is known that the generalization performanceof an online algorithm trained with only one pass (epoch)is typically inferior to batch algorithms, especially when
the number of training instances is small. Hence we cycled through the training samples several times (epochs),
and we reported the performance on a separate test set as
a function of the number of epochs. This is similar to astochastic gradient descent optimization [2]. Experiments
show that OM-2 achieves better performance than the other
online learning methods, and comparable performance as
the batch MKL method at much lower computational cost.
The MATLAB implementation of our algorithm is available
within the DOGMA library [20], which we also used for
implementation of the baseline online algorithms.

ples. Figure 1 (Right) reports the classification performanceobtained using different online learning algorithms and thebatch MKL algorithm. It can be observed from the plots that
the OM-2 algorithm achieves better performance on bothtraining and test phase compared to the other online learning algorithms. The best results were obtained when p issmall (1.01 in our setup). This is probably because among
these 48 kernels (computed from eight different image descriptors) many of them were redundant. Thus a sparse solution is favored. After about 80 epochs, the OM-2 achieve
comparable results as the batch MKL algorithm at a relative
low computational time. Although our MATLAB implementation is not optimized for speed, training on Caltech101 dataset using 30 examples per class and 48 kernels takes
about 45 mins4 (150 epochs, 3060 × 150 iterations). Whilefor MKL the training time using the SILP implementation
is more than 2 hours. The performance advantage of OM-2
over SILP is due the fact that OM-2 is based on a native
multiclass formulation (see Section 2), while SILP solves
the multiclass problem by decomposing it into multiple independent binary classification tasks. Thanks to the online
learning framework, we could solve the new MKL formulation using the multi-class loss function efficiently. This is
in line with similar observations in [11].

4.2. Place Recognition: IDOL-2

The Caltech-101 [9] dataset is a standard benchmark
dataset for object categorization. In our experiments weused the pre-computed features as well as the train/test splitsof [11], which the authors made available on their website3 .
There are eight different image descriptors. Using different
setup of parameters and different pyramid scales we end up
with a total of 48 kernel matrices. For brevity, we omit
the details of the features and kernels. These can be foundin [11] and its project website.
We report results using all 102 classes and 30 training
images per category over five different splits. For each split,
the experiments were performed over 10 different permutations of the training images. Figure 1 (Left) shows the average online training error rate using different online learningalgorithms as a function of the number of training exam-

We also performed a series of experiments on the IDOL2
database [16], which 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 laboratory environment consisting of five different rooms under various weather and illumination conditions (sunny, cloudy, and night) and across atime span of six months. This dataset is ideal for testing online learning algorithm: the algorithm has to incrementally
update the model, so to adapt to the variations captured in
the dataset. For experiments, we used the same setup described in [16, 15]. We considered the 12 sequences acquired by robot Dumbo, and divided them into training andtest sets, where each training sequence has a corresponding
one in the test sets captured under roughly similar conditions. In total, we considered twelve different permutationsof training and test sets. The images were described using
three visual descriptors and a geometric feature from theLaser Scan sensor, as in [15].
Figure 2 reports the average online training and recognition error rate on the test set. In contrast to the previous experiments, here the best performance is obtained at p = 2,

2 To the best of our knowledge, SILP [25] is the most efficient MKL implementation publicly available. Although SimpleMKL [21] is found to be
more efficient, a good implementation for large problems is not available.
3 www.vision.ee.ethz.ch/ pgehler/projects/
˜
iccv09/4 Notice that this time is measured using precomputed kernel matrix as
inputs. In practice, if not all the data points are available from the beginning, the kernel value could be computed “on the fly” and the total computation time of several epochs could be reduced using methods like kernelcaching.

4.1. Object Categorization: Caltech-101

Caltech−101 (5 splits, 30 training examples per category)

Caltech−101 (5 splits, 30 training examples per category)

80

100

75

classification rate on test data

Online average training error rate

95

90

85

80

75

70

OM−2, p=1.01
OMCL
PA−I (average kernel)
PA−I (best kernel)
500

1000

70

65

60
OM−2, p=1.01
OMCL
PA−I (average kernel)
PA−I (best kernel)
SILP

55

1500

2000

2500

3000

50

3500

10

20

30

40

50

60

70

80

90 100 110 120 130 140 150

number of epochs

number of training samples

Figure 1. Performance of different online learning algorithms on Caltech-101 dataset as a function of the number of training examples:(left) average online training error rate; (right) classification rate on the test set.
IDOL2 (12 training sequences)

IDOL2 (12 training sequences)

50

96.5

45

35
30
OM−2, p=2
OMCL
PA−I (average kernel)
PA−I (best kernel)

25
20
15

classification rate on test data

Online average training error rate

96

40
95.5

95

94.5
OM−2, p=2
OMCL
PA−I (average kernel)
PA−I (best kernel)
SILP

94

10
93.5

5
0

500 1000 1500 2000 2500 3000 3500 4000 4500 5000 5500 6000

93

2

4

number of training samples

6

8

10

12

14

16

18

20

number of epochs

Figure 2. Performance of different online learning algorithms on IDOL2 dataset as a function of the number of training examples: (left)
average online training error rate; (right) classification rate on the test set.

which means that there are no redundant features and allof them are discriminative for the given task. OM-2 andPA-I using average kernel achieve better performance compared to the other online learning algorithms. Surprisingly,
the performance of batch MKL is worse than all the other
online feature combination method, including the performance of the single best feature. Hence, in agreement withrecent findings [6], promoting sparsity hurts performance
when the problem is not sparse at all.

of the MKL problem that allows us to tune the level of sparsity in order to obtain always nearly optimal performance.
The time to update the model of OM-2 is linear in the number of features, classes and training examples. Therefore,
our algorithm scales well to large problems. Experiments
show that our algorithm achieves better performance compared to common baselines. Using enough epochs of training, our approach achieves the same generalization performance, or even better, than batch MKL, with a considerably
lower training time.

5. Conclusion

Acknowledgments

This paper presents a theoretically motivated online
learning algorithm for solving the multiclass MKL problem. The algorithm is based on a new p-norm formulation

The Caltech-101 kernel matrices were kindly provided by Peter
Gehler. LJ, MF and BC were supported by the EU project DIRAC
IST-027787. FO and NCB gratefully acknowledge partial support by the PASCAL2 Network of Excellence under EC grant no.

216886. This publication only reflects the authors’ views. Partof this work was done while FO was still at Idiap Research Institute.

[15] L. Jie, F. Orabona, and B. Caputo. An online framework for learning novel concepts over multiple cues.
In Proc. ACCV, 2009. 2, 5References[16] L. Jie, A. Pronobis, B. Caputo, and P. Jensfelt. Incremental learning for place recognition in dynamic
environments. In Proc. IROS, 2007. 1, 5

[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] L. Bottou and Y. L. Cun. On-line learning for verylarge dataset. Applied Stochastic Models in Businessand Industry, 21(2):136–151, 2005. 5[3] G. Cavallanti, N. Cesa-Bianchi, and C. Gentile. Linear
algorithms for online multitask classification. In Proc.
COLT, 2008. 2, 3, 4[17] 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. 2, 3, 8
[18] A. Kembhavi, B. Siddiquie, R. Miezianko, S. McCloskey, and L. S. Davis. Incremental multiple kernel
learning for object recognition. In Proc. ICCV, 2009.
1[4] N. Cesa-Bianchi and G. Lugosi. Prediction, learning,and games. Cambridge University Press, 2006. 1[19] M. Kloft, U. Brefeld, S. Sonnenburg, P. Laskov, K.-R.
Müller, and A. Zien. Efficient and accurate lp-norm
multiple kernel learning. In Proc. NIPS. 2009. 3[5] G. Chechik, V. Sharma, U. Shalit, , and S. Bengio.
An online algorithm for large scale image similarity
learning. In Proc. NIPS. 2009. 1[20] F. Orabona. DOGMA: a MATLAB toolbox for Online Learning, 2009. Software available at http://dogma.sourceforge.net. 5[6] C. Cortes, A. Gretton, G. Lanckriet, M. Mohri, and
A. Rostamizadeh. Proceedings of the NIPS Workshop
on Kernel Learning: Automatic Selection of Optimal
Kernels, 2009. 6[21] A. Rakotomamonjy, F. R. Bach, S. Canu, andY. Grandvalet. SimpleMKL,. JMLR, 9:2491–2521,
November 2008. 2, 3, 5

[7] K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz,
and Y. Singer. Online passive-aggressive algorithms.
JMLR, 7:551–585, 2006. 5[8] M. Everingham, L. Van Gool, C. K. I.
Williams, J. Winn, and A. Zisserman.
The
PASCAL Visual Object Classes Challenge
2009 (VOC2009) Results.
http://www.pascalnetwork.org/challenges/VOC/voc2009/workshop/.
1[9] L. Fei-Fei, R. Fergus, and P. Perona. One-shot learning of object categories. IEEE PAMI, 28(4):594–611,
2004. 4, 5
[10] M. Fink, S. Shalev-Shwartz, Y. Singer, and S. Ullman. Online multiclass learning by interclass hypothesis sharing. In Proc. ICML, pages 313–320, 2006. 1,2, 4[11] P. Gehler and S. Nowozin. On feature combination for
multiclass object classification. In Proc. ICCV, 2009.
1, 5[12] C. Gentile. The robustness of the p-norm algorithms.
Machine Learning, 53(3):265–299, 2003. 4[13] D. Grangier and S. Bengio. A discriminative kernelbased approach to rank images from text queries.
IEEE PAMI, 30(8), 2008. 1[14] P. Jain and A. Kapoor. Active learning for large multiclass problems. In Proc. CVPR, 2009. 1[22] S. Shalev-Shwartz. Online learning: Theory, algorithms, and applications, 2007. PhD thesis. 3[23] S. Shalev-Shwartz and Y. Singer. Logarithmic regret
algorithms for strongly convex repeated games. Technical Report 2007-42, The Hebrew University, 2007.
3[24] S. Shalev-Shwartz, Y. Singer, and N. Srebro. Pegasos:primal estimated sub-gradient solver for svm. In
Proc. ICML, 2007. 4[25] S. Sonnenburg, G. Rätsch, C. Schäfer, and
B. Schölkopf. Large scale multiple kernel learning. JMLR, 2006. 3, 5[26] M. Varma and D. Ray. Learning the discriminative
power-invariance trade-off. In Proc. ICCV, 2007. 1[27] A. Vedaldi, V. Gulshan, M. Varma, and A. Zisserman.
Multiple kernels for object detection. In Proc. ICCV,2009. 1[28] A. Zien and C. S. Ong. Multiclass multiple kernel
learning. In Proc. ICML, 2007. 2

A. Appendix

where

Proof of Theorem 1. The proof is based on an adaptation ofa result from [17] for the “Follow the Regularized Leader”
algorithm. We start by introducing a few basic notions ofconvex analysis. A differentiable function f : S → R is
said to be λ-smooth with respect to a norm k · k iff for any
2u, v ∈ S, f (u+v) ≤ f (u)+∇f (u)·v+ λ2 kvk . Note thatf is λ-smooth w.r.t. a norm iff f is (1/λ)-strongly convex
w.r.t. the corresponding dual norm [17].
We now proceed by bounding the quantity θ̄ T +1 · ū frombelow and from above. From [17, Corollary 19], we knowthat h(w̄) is 1-smooth w.r.t. k · k2,q . Moreover, line 12 in
the algorithm’s pseudo-code
implies that w̄t = ∇h∗ (θ̄ t ) =

Pt−1
∗
∇h
i=1 ηi z̄ i . Hence, we obtainkθ̄ T +1 k22,q ≤ kθ̄ T k22,q + 2qηT w̄T · z̄ T + qηT2 kz̄ T k22,q
≤q

T
X


2ηt w̄t · z̄ t + ηt2 kz̄ t k22,q .

t=1

Let Rt = 2ηt w̄t · z̄ t + ηt2 kz̄ t k22,q . Using the convex inequality for norms we then get
v
u T
u X
Rt .
θ̄ T +1 · ū ≤ kθ̄ T +1 k2,q kūk2,p ≤ kūk2,p tq
i=1

We can further bound the last term by considering separately the steps t when w̄t · z̄ t ≤ 0 (a mistake occurs), andthe steps when 0 ≤ w̄t · z̄ t ≤ 1 (a margin error occurs).
Using that kz̄ t k22,q ≤ 2F 2/q given φj (xt , yt ) 2 ≤ 1, we
have that ηt = 1 at mistakes, and we can further upperbound θ̄ T +1 · ū as followssXθ̄ T +1 · ū ≤ kūk2,p 2qF 2/q M + q
Rt .
(9)
t∈I

For the lower bound we have thatθ̄ T +1 · ū =TXηt ū · z̄ t

t=1

=

T
X


ηt ū · φ̄(xt , yt ) − φ̄(xt , ŷt )

t=1

≥

T
X

ηt 1 − `(ū, xt , yt )



t=1

≥M+

X

ηt − L .

t∈I

Combining this last inequality with (9), solving the inequality for M , and using the definition of C, we obtain
r
X
C
4
C
+L−
ηt +
1 + (A + L)
M≤
2
2
C
t∈I

A=

X Rt − 2ηt F 2/qt∈I

2F 2/q.

Now, observing that ηt has been chosen so that A ≤ 0 andoverapproximating we obtain the stated bound.