Online Learning of Multiple Tasks with a Shared Loss
Ofer Dekel

oferd@cs.huji.ac.il
School of Computer Science and Engineering, The Hebrew University, Jerusalem , Israel

Philip M. Long

plong@google.com

Google, 1600 Amphitheater Parkway, Mountain View, CA 94043, USA

Yoram Singer

singer@cs.huji.ac.il
School of Computer Science and Engineering, The Hebrew University, Jerusalem , Israel

Editor:

Abstract
We study the problem of learning multiple tasks in parallel within the online learning
framework. On each online round, the algorithm receives an instance for each of theparallel tasks and responds by predicting the label of each instance. We consider the casewhere the predictions made on each round all contribute toward a common goal. The
relationship between the various tasks is defined by a global loss function, which evaluates
the overall quality of the multiple predictions made on each round. Specifically, eachindividual prediction is associated with its own loss value, and then these multiple loss
values are combined into a single number using the global loss function. We focus on thecase where the global loss function belongs to the family of absolute norms, and present
several families of online learning algorithms for the induced problem. We prove worstcase relative loss bounds for all of our algorithms, and demonstrate the effectiveness of ourapproach on a large-scale multiclass-multilabel text categorization problem.

1. Introduction
Multitask learning is the problem of learning several related problems in parallel. In thispaper, we discuss the multitask learning problem in the online learning context, and focus
on the possibility that the learning tasks contribute toward a common goal. Our hopeis that we can benefit from learning the tasks jointly, as opposed to learning each task
independently.
For concreteness, we focus on the task of binary classification, and note that our algorithms and analysis can be adapted to regression and multiclass problems using ideas in(Crammer et al., 2006). In the online multitask classification setting, we are faced with kseparate online binary classification problems, which are presented to us in parallel. The
online learning process takes place in a sequence of rounds. At the beginning of round t,
the algorithm observes a set of k instances, one for each of the binary classification problems. The algorithm predicts the binary label of each of the k instances, and then receives
the k correct labels. At this point, each of the algorithm’s predictions is associated with a
non-negative loss, and we use ℓt = (ℓt,1 , . . . , ℓt,k ) to denote the k-coordinate vector whose elements are the individual loss values associated with the respective tasks. Let L : Rk → R+
be a predetermined global loss function, which is used to combine the individual loss values
c 2007 Ofer Dekel and Philip M. Long and Yoram Singer.

into a single number, and define the global loss attained on round t to be L(ℓt ). At theend of this online round, the algorithm may use the k new labeled examples it has obtained
to improve its prediction mechanism for the rounds to come. The goal of the learningalgorithm
is to suffer the smallest possible cumulative loss over the course of T rounds,
PT
L(ℓ
).
t
t=1
The choice of the global loss function captures the overall consequences of the individual
prediction errors, and therefore how
P the algorithm should prioritize correcting errors. For
example, if L(ℓt ) is defined to be kj=1 ℓt,j then the online algorithm is penalized equallyfor errors on each of the tasks; this results in effectively treating the tasks independently.
On the other hand, if L(ℓt ) = maxj ℓt,j then the algorithm is only interested in the worst
mistake made on each round. We do not assume that the datasets of the various tasks
are similar or otherwise related. Moreover, the examples presented to the algorithm foreach of the tasks may come from completely different domains and may possess different
characteristics. The multiple tasks are tied together by the way we define the objective of
our algorithm.
In this paper, we focus on the case where the global loss function is an absolute norm.
A norm k · k is a function such that kvk > 0 for all v 6= 0, k0k = 0, kλvk = |λ|kvk for allv and all λ ∈ R, and which satisfies the triangle inequality. A norm is said to be absolute
if kvk = k|v|k for all v, where |v| is obtained by replacing each component of v with its
absolute value. The most well-known family of absolute norms is the family of p-norms(also called Lp norms), defined for all p ≥ 1 by
kvkp =nX
j=1

|vj |p 1/p .

A special member of this family is the L∞ norm, which is defined to be the limit of theabove when p tends to infinity, and can be shown to equal maxj |vj |. A less known family of
absolute norms is the family of r-max norms. For any integer r between 1 and k, the r-max
norm of v ∈ Rk is the sum of the absolute values of the r absolutely largest components ofv. Formally, the r-max norm is
kvkr-max =

r
X
j=1

|vπ(j) | where |vπ(1) | ≥ |vπ(2) | ≥ . . . ≥ |vπ(k) | .

(1)

Note that both the L1 norm and L∞ norm are special cases of the r-max norm, as well
as being p-norms. Actually, the r-max norm can be viewed as a smooth interpolation
between the L1 norm and the L∞ norm, using Peetre’s K-method of norm interpolation(see Appendix A for details).
Since the global loss functions we consider in this paper are norms, the global loss equals
zero only if ℓt is itself the zero vector. Furthermore, decreasing any individual loss can only
decrease the global loss function. Therefore, the simplest solution to our multitask problem
is to learn each task individually, and minimize the global loss function implicitly. The
natural question which is at the heart of this paper is whether we can do better than this.
Our answer to this question is based on the following fundamental view of online learning.
On every round, the online learning algorithm balances a trade-off between retaining the2

information it has acquired on previous rounds and modifying its hypothesis based on the
new examples obtained on that round. Instead of balancing this trade-off individually foreach of the learning tasks, we can balance it jointly, for all of the tasks. By doing so, weallow ourselves to make a big modification to one of the k hypotheses at the expense of theothers. This additional flexibility enables us to directly minimize the specific global loss
function we have chosen to use.
To motivate and demonstrate the practicality of our approach, we begin with a handfulof concrete examples.
Multiclass Classification using the L∞ Norm Assume that we are faced with amulticlass classification problem, where the size of the label set is k. One way of solving
this problem is by learning k binary classifiers, where each classifier is trained to distinguishbetween one of the classes and the rest of the classes. This approach is often called theone-vs-rest method. If all of the binary classifiers make correct predictions, then one ofthese predictions should be positive and the rest should be negative. If this is the case,
we can correctly predict the corresponding multiclass label. However, if one or more of thebinary classifiers makes an incorrect prediction, we can no longer guarantee the correctnessof our multiclass prediction. In this sense, a single binary mistake on round t is as bad as
many binary mistakes on round t. Therefore, we should only care about the worst binary
prediction on round t, and we can do so by choosing the global loss to be kℓt k∞ .
Another example where the L∞ norm comes in handy is the case where we are facedwith a multiclass problem where the number of labels is huge. Specifically, we would likethe running time and the space complexity of our algorithm to scale logarithmically with
the number of labels. Assume that the number of different labels is 2k , enumerate theselabels from 0 to 2k − 1, and consider the k-bit binary representation of each label. We cansolve the multiclass problem by training k binary classifiers, one for each bit in the binary
representation of the label index. If all k classifiers make correct predictions, then we haveobtained the binary representation of the correct multiclass label. As before, a single binary
mistake is devastating to the multiclass classifier, and the L∞ norm is the most appropriate
means of combining the k individual losses into a global loss.
Vector-Valued Regression using the L2 Norm Let us deviate momentarily from thebinary classification setting, and assume that we are faced with multiple regression problems.
Specifically, assume that our task is to predict the three-dimensional position of an object.
Each of the three coordinates is predicted using an individual regressor, and the regression
loss for each task is simply the absolute difference between the true and the predicted valueon the respective axis. In this case, the most appropriate choice of the global loss function is
the L2 norm, which reduces the vector of individual losses to the Euclidean distance between
the true and predicted 3-D targets. (Note that we take the actual Euclidean distance andnot the squared Euclidean distance often minimized in regression settings).
Error Correcting Output Codes and the r-max Norm Error Correcting Output
Codes (ECOC) is a technique for reducing a multiclass classification problem to multiple binary classification problems (Dietterich and Bakiri, 1995). The power of this technique liesin the fact that a correct multiclass prediction can be made even when a few of the binary
predictions are wrong. The reduction is represented by a code matrix M ∈ {−1, +1}s×k ,3

where s is the number of multiclass labels and k is the number of binary problems used to
encode the original multiclass problem. Each row in M represents one of the s multiclasslabels, and each column induces one of the k binary classification problems. Given a multiclass training set {(xi , yi )}m
i=1 , with labels yi ∈ {1, . . . , s}, the binary problem induced bycolumn j is to distinguish between the positive examples {(xi , yi : Myi ,j = +1} and negative
examples {(xi , yi : Myi ,j = −1}. When a new instance is observed, applying the k binaryclassifiers to it gives a vector of binary predictions, ŷ = (ŷ1 , . . . , ŷk ) ∈ {−1, +1}k . We thenpredict the multiclass label of this instance to be the index of the row in M which is closest
to ŷ in Hamming distance.
Define the code distance of M , denoted by d(M ), to be the minimal Hamming distance
between any two rows in M . It is straightforward to show that a correct multiclass prediction
can be guaranteed as long as the number of binary mistakes made on this instance is lessthan d(M )/2. In other words, making d(M )/2 binary mistakes is as bad as making morebinary mistakes. Let r = d(M )/2. If the binary classifiers are trained in the online multitask
setting, we should only be interested in whether the r’th largest loss is less than 1, which
would imply that a correct multiclass prediction can be guaranteed. Regretfully, taking ther’th largest element of a vector (in absolute value) does not constitute a norm and thus
does not fit in our setting. However, the r-max norm, defined in Eq. (1), can serve as agood proxy.
In this paper, we present three families of online multitask algorithms. Each family
includes algorithms for every absolute norm. All of the algorithms presented in this paper
follow the general skeleton outlined in Fig. 1. Specifically, all of our algorithms use linear
threshold functions as hypotheses and an additive update rule. The first two families are
multitask extensions of the Perceptron algorithm (Rosenblatt, 1958, Novikoff, 1962), while
the third family is closely related to the Passive-Aggressive classification algorithm (Crammer et al., 2006). Incidentally, all of the algorithms presented in this paper can be easilytransformed into kernel methods. For each algorithm, we prove a relative loss bound,
namely, we show that the cumulative global loss attained by the algorithm is comparable
to the cumulative loss attained by any fixed set of k linear hypotheses, even defined inhindsight.
Much previous work on theoretical and applied multitask learning has focused on how
to take advantage of similarities between the various tasks (Caruana, 1997, Heskes, 1998,
Evgeniou et al., 2005, Baxter, 2000, Ben-David and Schuller, 2003, Tsochantaridis et al.,2004); in contrast, we do not assume that the tasks are in any way related. Instead, we
consider how to take account of shared consequences of errors. Kivinen and Warmuth(2001) generalized the notion of matching loss (Helmbold et al., 1999) to multi-dimensional
outputs. Their construction enables analysis of algorithms that perform multi-dimensional
regression by composing linear functions with a variety of transfer functions. It is not
obvious how to directly use their work to address the problems that fall into our setting.
An analysis of the L∞ norm of prediction errors is implicit in some past work of Crammer
and Singer (2001, 2003). The algorithms presented in Crammer and Singer (2001, 2003)
were devised for multiclass categorization with multiple predictors (one per class) and asingle instance. The present paper extends the multiclass prediction setting to a broader
framework, and tightens the analysis. In contrast to the multiclass prediction setting, theprediction tasks in our setting are tied solely through a globally shared loss. When k, the4input: norm k · kinitialize: w1,1 = . . . = w1,k = (0, . . . , 0)
for t = 1, 2, . . .
• receive xt,1 , . . . , xt,k• predict sign(wt,j · xt,j )[1 ≤ j ≤ k]

• receive yt,1 , . . . , yt,k• calculate ℓt,j = 1 − yt,j wt,j · xt,j +[1 ≤ j ≤ k]

• update wt+1,j = wt,j + τt,j yt,j xt,j

[1 ≤ j ≤ k]

• suffer loss ℓt = k(ℓt,1 , . . . , ℓt,n )kFigure 1: A general skeleton for an online multitask classification algorithm. A concretealgorithm is obtained by specifying the values of τt,j .

number of multiple tasks, is set to 1, two of the algorithms presented in this paper as well as
the multiclass algorithms in Crammer and Singer (2001, 2003) reduce to the PA-I algorithm,
presented in (Crammer et al., 2006). Last, we would like to mention in passing that a few
learning algorithms for ranking problems decompose the ranking problem into a preference
learning task over pairs of instances (see for instance Herbrich et al. (2000), Chapelle andHarchaoui (2005)). The ranking losses employed by such algorithms are typically defined as
the sum over pair-based losses. Our setting generalizes such approaches for ranking learningby employing a shared loss which is defined through a norm over the individual pair-based
losses.
This paper is organized as follows. In Sec. 2 we present our problem more formally andprove a key lemma which facilitates the analysis of our algorithms. In Sec. 3 we present
our first family of algorithms, which works in the finite-horizon online setting. In Sec. 4 weextend the first family of algorithms to the infinite-horizon online setting. Then, in Sec. 5 we
present our third family of algorithms, and show that it shares the analyses of both previous
families. The third family of algorithms requires solving a small optimization problem oneach online round, and is therefore called the implicit update family of algorithms. In Sec. 6
and Sec. 7 we describe efficient algorithms for solving the implicit update in the case where
the global loss is defined by the L2 norm or the r-max norm. Experimental results areprovided in Sec. 8 and we conclude the paper in Sec. 9 with a short discussion.

2. Online Multitask Learning with Additive Updates
We begin by presenting the online multitask classification setting more formally. We arepresented with k online binary classification problems in parallel. The instances of eachtask are drawn from separate instance domains, and for concreteness we assume that the
instances of task j are all vectors in Rnj . As stated in the previous section, online learning5

is performed in a sequence of rounds. On round t, the algorithm observes k instances,(xt,1 , . . . , xt,k ) ∈ Rn1 × . . . × Rnk . The algorithm maintains k separate classifiers in its
internal memory, one for each of the multiple tasks, which are updated from round to
round. Each of these classifiers is a margin-based linear predictor, defined by a weightvector. We denote the weight vector used on round t to define the j’th predictor by wt,jand note that wt,j ∈ Rnj . The algorithm uses its classifiers to make k binary predictions,ŷt,1 , . . . , ŷt,k , where ŷt,j = sign(wt,j · xt,j ). After making these predictions, the correctlabels of the respective tasks, yt,1 , . . . , yt,k , are revealed and each one of the predictions isevaluated. In this paper we focus on the hinge-loss function as the means of penalizing
incorrect predictions. Formally, the loss associated with the j’th task is defined to beℓt,j = 1 − yt,j wt,j · xt,j + ,where [a]+ = max{0, a}. As previously stated, the global loss is then defined to be kℓt k,
where k · k is a predefined absolute norm. Finally, the algorithm applies an update to eachof the online hypotheses, and defines the vectors wt+1,1 , . . . , wt+1,k . All of the algorithms
presented in this paper use an additive update rule, and define wt+1,j to be wt,j +τt,j yt,j xt,j ,where τt,j is a scalar. The algorithms only differ from one another in the specific way inwhich τt,j is set. For convenience, we denote τt = (τt,1 , . . . , τt,k ). The general skeleton
followed by all of our online algorithms is given in Fig. 1.
A concept of key importance in this paper is the notion of dual norms (Horn andJohnson, 1985). Any norm k · k defined on Rn , has a dual norm, also defined on Rn ,denoted by k · k∗ and given bykuk∗ = maxn
v∈R

u·v
=
kvk

max

v∈Rn : kvk=1

u·v .

(2)

The dual of a p-norm is itself a p-norm, and specifically, the dual of k · kp is k · kq , where1
1
q + p = 1. The dual of k · k∞ is k · k1 and vice versa. In Appendix A we prove that thedual of kvkr-max is


kuk1
∗
kukr-max = max kuk∞ ,.
(3)rAn important property of dual norms, which is an immediate consequence of Eq. (2), isthat for any u, v ∈ Rn it holds thatu · v ≤ kuk∗ kvk .

(4)

If k · k is a p-norm then the above is known as Hölder’s inequality, and specifically, if p = 2
it is called the Cauchy-Schwartz inequality. Two additional properties which we rely on arethat the dual of the dual norm is the original norm (see for instance (Horn and Johnson,1985)), and that the dual of an absolute norm is also an absolute norm. As previously
mentioned, to obtain concrete online algorithms, all that remains is to define the updateweights τt,j for each task on each round. The different ways of setting τt,j discussed in thispaper all share the following properties:• boundedness:• non-negativity:∀1≤t≤Tkτt k∗ ≤ C for some predefined parameter C∀ 1 ≤ t ≤ T, 1 ≤ j ≤ k6

τt,j ≥ 0• conservativeness:∀ 1 ≤ t ≤ T, 1 ≤ j ≤ k(ℓt,j = 0) ⇒ (τt,j = 0)

Even before specifying the exact value of τt,j , we can state and prove a powerful lemma
which is the crux of our analysis. This lemma will motivate and justify our specific choicesof τt,j throughout this paper.
Lemma 1 Let {(xt,j , yt,j )}1≤j≤k
1≤t≤T be a sequence of T k-tuples of examples, where each xt,j ∈Rnj , and each yt,j ∈ {−1, +1}. Let w1⋆ , . . . , wk⋆ be arbitrary vectors where wj⋆ ∈ Rnj , and

define the hinge loss attained by wj⋆ on example (xt,j , yt,j ) to be ℓ⋆t,j = 1 − yt,j wj⋆ · xt,j + .
Let k · k be an arbitrary norm and let k · k∗ denote its dual. Assume we apply an algorithmof the form outlined in Fig. 1 to this sequence of examples, where the update weights satisfy
the boundedness, non-negativity and conservativeness requirements. Then, for any C > 0 it
holds that
T
k
T X
k 

X
X
X
2
kℓ⋆t k .
kwj⋆ k22 + 2C
2τt,j ℓt,j − τt,j
kxt,j k22 ≤t=1 j=1

j=1

t=1

Under the assumptions of this lemma, our algorithm competes with a set of fixed linear
classifiers, w1⋆ , . . . , wk⋆ , which may even be defined in hindsight, after observing all of the
inputs and their Plabels. The right-hand side of the bound is the sum of two terms, acomplexity term kj=1 kwj⋆ k22 and a term which is proportional to the cumulative loss ofP
our competitor, Tt=1 kℓ⋆t k. The left hand side of the bound is the term
T X
k 

X
2
2τt,j ℓt,j − τt,j
kxt,j k22 .

(5)

t=1 j=1

This term plays a key role in the derivation of all three families of algorithms presented
in the sequel. Each choice of the update weights τt,j enables us to prove a different lower
bound on Eq. (5). Comparing this lower bound with the upper bound in Lemma 1 gives usa loss bound for the respective algorithm. The proof of Lemma 1 is given below.
Proof Define ∆t,j = kwt,j − wj⋆ k22 − kwt+1,j − wj⋆ k22 . We prove the lemma by bounding
PT Pk
t=1
j=1 ∆t,j from above and from below. Beginning with the upper bound, we notePthat for each 1 ≤ j ≤ k, Tt=1 ∆t,j is a telescopic sum which collapses toTX
t=1∆t,j = kw1,j − w⋆ k22 − kwT +1,j − w⋆ k22 .

Using the facts that w1,j = (0, . . . , 0) and kwT +1,j −w⋆ k22 ≥ 0 for all 1 ≤ j ≤ k, we conclude
that
k
T X
k
X
X
kwj⋆ k22 .
(6)∆t,j ≤
t=1 j=1

j=1

7

Turning to the lower bound, we note that we can consider only non-zero summands which
actually contribute to the sum, namely ∆t,j 6= 0. Plugging the definition of wt+1,j into ∆t,j ,we get∆t,j = kwt,j − wj⋆ k22 − kwt,j + τt,j yt,j xt,j − wj⋆ k22= τt,j −2yt,j wt,j · xt,j − τt,j kxt,j k22 + 2yt,j wj⋆ · xt,j= τt,j 2(1 − yt,j wt,j · xt,j ) − τt,j kxt,j k22 − 2(1 − yt,j wj⋆ · xt,j ) .

(7)

Since our update is conservative, ∆t,j 6= 0 implies that ℓt,j = 1 − yt,j wt,j · xt,j . By definition,it also holds that ℓ⋆t,j ≥ 1 − yt,j wj⋆ · xt,j . Plugging these two facts into Eq. (7) and using thefact that τt,j is non-negative gives∆t,j ≥ τt,j 2ℓt,j − τt,j kxt,j k22 − 2ℓ⋆t,j .

Summing the above over 1 ≤ j ≤ k giveskX
j=1∆t,j ≥kX
j=1

2
2τt,j ℓt,j − τt,j
kxt,j k22



−2

k
X

τt,j ℓ⋆t,j .

(8)

j=1

P
Using Eq. (4) we know that kj=1 τt,j ℓ⋆t,j ≤ kτt k∗ kℓ⋆t k. From our assumption that kτt k∗ ≤ C,P
we have that kj=1 τt,j ℓ⋆t,j ≤ Ckℓ⋆t k. Plugging this inequality into Eq. (8) giveskX
j=1∆t,j ≥

k
X
j=1


2
2τt,j ℓt,j − τt,j
kxt,j k22 − 2Ckℓ⋆t k .

We conclude the proof by summing the above over 1 ≤ t ≤ T and comparing the result tothe upper bound in Eq. (6).

3. The Finite-Horizon Multitask Perceptron
In this section, we present our first family of online multitask classification algorithms, andprove a relative loss bound for the members of this family. This family includes algorithms
for any global loss function defined through an absolute norm. These algorithms are finitehorizon online algorithms, meaning that the number of online rounds, T , is known in advanceand is given as a parameter to the algorithm. An analogous family of infinite-horizon
algorithms is the topic of the next section.
As previously noted, the Finite-Horizon Multitask Perceptron follows the general skeleton outlined in Fig. 1. Given an absolute norm k · k and its dual k · k∗ , the multitask
Perceptron sets τt,j in Fig. 1 to
τt = argmax τ · ℓt ,(9)τ: kτk∗ ≤Cwhere C > 0 is a constant which is specified later in this section. There may exist multiple
solutions to the maximization problem above and at least one of these solutions induces a8conservative update. In other words, we may assume that the solution to Eq. (9) is suchthat τt,j = 0 at every coordinate j where ℓt,j = 0. To see that such a solution exists, takean arbitrary optimal solution τ and let τ̂ be defined byτj if ℓt,j 6= 0τ̂j =0 if ℓt,j = 0
Clearly, τ · ℓt = τ̂ · ℓt , whereas kτ̂k∗ ≤ kτk∗ ≤ C. If the optimization problem in Eq. (9) has
multiple solutions that induce conservative updates, assume that one is chosen arbitrarily.
An equivalent way of defining the solution to Eq. (9) is by satisfying the equality τt ·ℓt =Ckℓt k. To see this equivalence, note that the dual of k · k∗ is defined by Eq. (2) to bekℓk∗∗ =max

τ: kτk∗ ≤1

τ·ℓ .

However, since k · k∗∗ is equivalent to k · k (see for instance Thm 5.5.14 in Horn and Johnson(1985)), we getkℓk =max τ · ℓ .
τ: kτk∗ ≤1

Using the linearity of k · k∗ , we conclude that kτ/Ck∗ = kτk∗ /C for any C > 0, and therefore
the above becomes
Ckℓk =
max τ · ℓ .
τ: kτk∗ ≤C

We conclude that
τt · ℓt = Ckℓt k(10)

holds if and only if τt is a maximizer of Eq. (9).
When the global loss function is a p-norm, the following definition of τ t solves Eq. (9):τt,j =

p−1
Cℓt,jkℓt kp−1
p

.

(11)

When the global loss function is an r-max norm and π is a permutation such that ℓt,π(1) ≥. . . ≥ ℓt,π(k) , the following definition of τ t is a solution to Eq. (9):C
if ℓt,j > 0 and j ∈ {π(1), . . . , π(r)}τt,j =(12)0otherwise.
Note that when r = k, the r-max norm reduces to the L1 norm and the above becomes
the well-known update rule of the Perceptron algorithm (Rosenblatt, 1958, Novikoff, 1962).
The correctness of the definitions in Eq. (11) and Eq. (12) can be easily verified by observing
that kτt k∗ ≤ C and that τt · ℓt = Ckℓt k in both cases.
Before proving a loss bound for the multitask Perceptron, we must introduce anotherimportant quantity. This quantity is the remoteness of a norm k · k defined on Rk , and isdefined to be
kuk2=
max kuk2 .
(13)
ρ(k · k, k) = maxku∈Rk :kuk≤1u∈R kuk
Geometrically, the remoteness of k · k is simply the Euclidean length of the longest vector(again, in the Euclidean sense) which is contained in the unit ball of k · k. This definition is
9

√

1

1

√
6

L1 norm

L2 norm

L3 norm2

2

L∞ norm

Figure 2: The remoteness of a norm is the longest Euclidean length of any vector containedin the norm’s unit ball. The longest vector in each of the two-dimensional unit
balls above is depicted with an arrow.

visually depicted in Fig. 2. As we show below, the remoteness of the dual norm, ρ(k · k∗ , k),plays an important role in determining the difficulty of using k · k as the global loss function.
For concreteness, we now calculate the remoteness of the duals of p-norms and of r-max
norms.
Lemma 2 The remoteness of a p-norm k · kq equals(1
if 1 ≤ q ≤ 2
ρ(k · kq , k) =( 12 − q1 )kif 2 < q.

Before proving the lemma, we note that if k · kp is a p-norm and k · kq is its dual, then wepto obtain
can combine Lemma 2 with the equality q = p−1
ρ(k · kq , k) =(1k( 1p − 21 )if 2 ≤ p

if 1 ≤ p < 2.

This equivalent form is better suited to our needs. The proof of Lemma 2 is given below.
Proof If 2 ≤ p then 1 ≤ q ≤ 2, and the monotonicity of the p-norms implies thatkvkq ≥ kvk2 for all v ∈ Rk . Therefore kvk2 /kvkq ≤ 1 for all v ∈ Rk and thus ρ(k·kq , k) ≤ 1.
On the other hand, setting v = (1, 0, . . . , 0), we get kvkq = kvk2 and therefore ρ(k·kq , k) ≥ 1.
Overall, we have shown that ρ(k · kq , k) = 1.
Turning to the case where 1 ≤ p < 2, we note that q > 2. Let v be an arbitrary vectorin Rk , and define u = (v12 , . . . , vk2 ) and w = (1, . . . , 1). Noting that k · k q and k · k q are2
q−2
dual norms, we use Hölder’s inequality to obtainu · w ≤ kuk q kwk q
2

q−2

.
2

The left-hand side above equals kvk22 , while the right-hand side above equals kvk2q k1− q .

Therefore, kvk22 /kvk2q ≤ k
k

1
−1
2 q

1− 2q

and taking square-roots on both sides yields kvk2 /kvkq ≤1

1. Since this inequality holds for all v ∈ Rk , we have shown that ρ(k · kq , k) ≤ k 2 − q .
10

1

On the other hand, setting v = (1, . . . , 1), we get kvk2 = k 2
ρ(k · kq , k) ≥ k

1
− 1q
2

, and therefore ρ(k · kq , k) = k

1
− 1q
2

− 1q

.

kvkq . This proves that

Lemma 3 Let k · kr-max be a r-max norm and let k · k∗r-max be its dual. The remoteness of√k · k∗r-max equals r.
Proof Using Eq. (13), the remoteness of k · k∗r-max is defined to be the maximum value ofkuk2 subject to kuk∗r-max ≤ 1. Recalling the definition of k · k∗r-max from Eq. (3), we canreplace this constraint with two constraints kuk1 ≤ r and kuk∞ ≤ 1. Moreover, since boththe L1 norm and the L∞ norm are absolute norms, we can also assume that u resides in
the non-negative orthant. Therefore, we have that 0 ≤ uj ≤ 1 for all 1 ≤ j ≤ k. From this√we conclude that u2j ≤ uj for all 1 ≤ j ≤ k, and thus kuk22 ≤ kuk1 ≤ r. Hence, kuk2 ≤ r√and ρ(k · k∗r-max , k) ≤ r. On the other hand, the vector
r

u =

k−r

z }| { z }| { 
1, . . . , 1, 0, . . . , 0√
is contained in the unit ball of k · k∗r-max , and its Euclidean length is r. Therefore, we also√√
have that ρ(k · k∗r-max , k) ≥ r, and overall we get ρ(k · k∗r-max , k) = r.
We are now ready to prove a loss bound for the Finite-Horizon Multitask Perceptron.
Theorem 4 Let {(xt,j , yt,j )}1≤j≤k
1≤t≤T be a sequence of T k-tuples of examples, where eachnjxt,j ∈ R , kxt,j k2 ≤ R and each yt,j ∈ {−1, +1}. Let C be a positive constant and let
k · k be an absolute norm. Let w1⋆ , . . . , wk⋆ be arbitrary vectors where wj⋆ ∈ Rnj , and define
the hinge loss incurred by wj⋆ on example (xt,j , yt,j ) to be ℓ⋆t,j = 1 − yt,j wj⋆ · xt,j + . If we
present this sequence to the finite-horizon multitask Perceptron with the norm k · k and theaggressiveness parameter C, then,
T
X
t=1

T
k
X
T R2 C ρ2 (k · k∗ , k)
1 X
⋆ 2kℓ⋆t k +.
kwj k2 +kℓt k ≤
2C
2
t=1

j=1

Proof The starting point of our analysis is Lemma 1. The choice of τt,j in Eq. (9) is clearlybounded by kτt k∗ ≤ C and conservative. It is also non-negative, due to the fact that k · k∗
is an absolute norm and that ℓt,j ≥ 0. Therefore, the definition of τt,j in Eq. (9) meets therequirements of the lemma, and we have
T X
k 
X
t=1 j=1

2
2τt,j ℓt,j − τt,j
kxt,j k22



≤

k
X
j=1

kwj⋆ k22

+ 2C

T
X
t=1

kℓ⋆t k .

Using Eq. (10), we rewrite the left-hand side of the above as
2C

T
X
t=1

kℓt k −T X
kX
t=1 j=1

11

2
τt,jkxt,j k22 .

(14)

P
2 kx k2 ≤ (Rkτ k )2 . Using
Using our assumption that kxt,j k22 ≤ R2 , we know that kj=1 τt,j
t 2
t,j 2
the definition of remoteness, we can upper bound this term by (Rkτt k∗ ρ(k · k∗ , k))2 . Finally,using our upper bound on kτt k∗ we can further bound this term by R2 C 2 ρ2 (k·k∗ , k). Plugging
this bound back into Eq. (14) gives
2C

T
X
t=1

kℓt k − T R2 C 2 ρ2 (k · k∗ , k) .

Overall, we have shown that
2C

T
X
t=1

kℓt k − T R2 C 2 ρ2 (k · k∗ , k) ≤

k
X
j=1

kwj⋆ k22 + 2C

T
X
t=1

kℓ⋆t k .

Dividing both sides of the above by 2C and rearranging terms gives the desired bound.
In its current form, the bound in Thm. 4 may seem insignificant, since its right-most term
grows linearly with the length of the input√sequence, T . This term can be easily controlled
by setting C to a value on the order of 1/ T .
√Corollary 5 Under the assumptions of Thm. 4, if C = 1/( T R2 ), then

√ 
T
T
k
X
X
X
T  2
kℓ⋆t k +kℓt k ≤
kwj⋆ k22 + ρ2 (k · k∗ , k) .
R
2
t=1
t=1
j=1

This corollary bounds the global loss cumulated by our algorithm with the global loss
obtained by any fixed set of hypotheses, plus a term which grows sub-linearly in T . The
significance of this term depends on the magnitude of the constant


k
X
1 2
kwj⋆ k22 + ρ2 (k · k∗ , k) .
R
2
j=1

√
Our algorithm uses C in its update procedure, and the value of C depends on T . Therefore,
the algorithm is a finite horizon algorithm.
Dividing both sides of the inequality in Corollary 5 by T , we see that the average global
loss suffered by the multitask Perceptron is upper bounded by the average global loss of thebest fixed hypothesis ensemble plus a term that diminishes with T . Using game-theoretic
terminology, we can now say that the multitask Perceptron exhibits no-regret with respect toany global loss function defined by an absolute norm. The same cannot be said for the naive
alternative of learning each task independently using a separate single-task Perceptron. We
show this by presenting a simple counter-example. Specifically, we construct a concrete ktask problem with a specific global loss, an arbitrarily long input sequence {(xt,j , yt,j )}1≤j≤k
1≤t≤T ,
and fixed weight vectors u1 , . . . , uk to use for comparison. We then prove thatT
T
X
k+1X ⋆kℓ̂t k∞ ,kℓ t k∞ ≤
2
t=1

t=1

12

(15)

where ℓ̂t is the vector of individual losses of the k independent single-task Perceptrons,
and, as before, ℓ⋆t is the vector of individual losses of u1 , . . . , uk respectively. This example
demonstrates that a claim along the lines of Corollary 5 cannot be proven for the set ofindependent single-task Perceptrons.
First, we would like to emphasize that we are considering a version of the single-task
Perceptron that updates its hypothesis whenever it suffers a positive hinge-loss, and not
only when it makes a prediction mistake. Moreover, when an update is performed, thealgorithm defines wt+1 = wt + Cyt xt , where C is a predefined constant. This version of thePerceptron is sometimes called the aggressive Perceptron. If we were to use the simplest
version of the Perceptron, which updates its hypothesis only when a prediction mistakeoccurs, then finding a counter-example that achieves Eq. (15) would be trivial, withouteven using the distinction between single-task and multitask Perceptron learning.
Also, we can assume without loss of generality that 1/C = o(T ), since otherwise, even in
the case k = 1, simply repeating the same example over and over provides a counterexample.
Moving on to the counter-example itself, assume that our global loss is defined by the L∞
norm. Let k be at least 2, assume that the instances of all k problems are two dimensional
vectors, and set u1 = . . . = uk = (1, 1). Each of the single-task Perceptrons initializes its
hypothesis to (0, 0). Assume that all of the labels in the input sequence are positive labels.
For t = 0, we set x1,1 = . . . = x1,k = (1, 0). Each one of the independent Perceptrons suffers
a positive individual loss and updates its weight vector to (C, 0). We continue presenting thesame example for ⌈1/C⌉ − 1 additional rounds, which is precisely when all k weight√ vectorsof the Perceptrons become equal√to (α, 0), with α ≥ 1. For instance, if C = O(1/ T ) thenthe vector (1, 0) is presented O( T ) times. Meanwhile, the fixed weight vectors u1 , . . . , uk
suffer no loss at all.
Define t0 = ⌈1/C⌉, and note that the index of the next online round is t0 + 1. For
each t in t0 + 1, . . . , t0 + k, we set xt,t−t0 to (0, 1) and xt,j to (1, 0) for all j 6= t − t0 . On
round t, the (t − t0 )’th Perceptron, whose weight vector is (α, 0), suffers an individual lossof 1 and updates its weight vector to (α, C). The remaining k − 1 Perceptrons suffer no
individual loss and do not modify their weight vectors. Consequently, kℓ̂t k∞ = 1 on eachof these rounds. Once again, the fixed vectors u1 , . . . , uk suffer no loss at all. On roundt = t0 + k + 1, we set xt,1 = . . . = xt,k = (0, −1). As a result, each of the Perceptrons suffersa hinge loss of 1 + C and updates its weight vector back to (α, 0). Since C is positive, we
get kℓ̂t k∞ ≥ 1. Meanwhile, kℓ⋆t k∞ = 2. We now have thatt0X
+k+1
t=t0 +1kℓ̂t k∞ ≥ k + 1

and

t0X
+k+1
t=t0 +1kℓ⋆t k∞ = 2 .

Furthermore, the weight vectors of the k single-task Perceptrons have returned to theirvalues at the end of round t0 . Therefore, by repeating the input sequence from round t0 + 1
to round t0 + k + 1 over and over again, we obtain Eq. (15).
This concludes the presentation of the counter-example thus showing that a set of independent single-task Perceptrons does not attain no-regret with respect to the L∞ norm
global loss. Similar constructions can be given for other global loss functions. The exception is the L1 norm, which naturally reduces the multitask Perceptron to k independent
single-task Perceptrons.
13

4. An Extension to the Infinite Horizon Setting
In the previous section, we devised an algorithm which relied on prior knowledge of T , theinput sequence length. In this section, we adapt the update procedure from the previous
section to the infinite horizon setting, where T is not known in advance. Moreover, thebound we prove in this section holds simultaneously for every prefix of the input
P sequence.
This generalization comes at a price; we can only prove an upper bound on t min{ℓt , ℓ2t },a quantity similar to the cumulative global loss, but not the global loss per se.
To motivate our infinite-horizon algorithm, we take a closer look at the P
analysis of thefinite-horizon algorithm. In the proof of Thm. 4, we lower-bounded the term kj=1 2τt,j ℓt,j −2 kx k2 by 2Ckℓ k−R2 C 2 ρ2 (k·k∗ , k). The first term in this lower bound is proportional to
τt,j
t
t,j 2
the global loss suffered on round t, and the second term is a constant. When kℓt k is smaller
than this constant, our lower bound becomes negative. This suggests that the update stepsize applied by the finite-horizon Perceptron may have been too large, and that the update
step may have overshot its target. As a result, the new hypothesis may be inferior to theprevious one. Nevertheless, over the course of T rounds, our positive progress is guaranteed
to overshadow our negative progress, and thus we are able to prove Thm. 4. However, if weare interested in a bound which holds for every prefix of the input sequence, we must ensurethat every
makes positive progress. Concretely, we derive an update for
Pk individual update2
which j=1 2τt,j ℓt,j − τt,j kxt,j k22 is guaranteed to be non-negative. The vector τt remains inthe same direction as before, but by setting its length more carefully, we enforce an update
step-size which is never excessively large.
We use ρ to abbreviate ρ(k · k∗ , k) throughout this section. We replace the definition of
τt in Eq. (9) with the following definition,
τt =argmaxn

τ: kτk∗ ≤minkℓ k
C, 2t 2R ρo

τ · ℓt ,(16)

where C > 0 is a user defined parameter and R > 0 is an upper bound on kxt,j k2 for all
1 ≤ t ≤ T and all 1 ≤ j ≤ k. As in the previous section, we assume that τt,j = 0 wheneverℓt,j = 0. As in Eq. (10), the solution to Eq. (16) can be equivalently defined by the equation


kℓt k
(17)
τt · ℓt = min C, 2 2 kℓt k .
R ρ
When the global loss function is a p-norm, the following definition of τ t solves Eq. (16):

ℓ p−1

if kℓt kp ≤ R2 Cρ2
 R2 ρ2t,jkℓt kp−2pτt,j =
p−1

Cℓt,j

if kℓt kp > R2 Cρ2p−1
kℓt kpWhen the global loss function is an r-max norm and π is a permutation such that ℓt,π(1) ≥. . . ≥ ℓt,π(k) , then the following definition of τ t is a solution to Eq. (16):kℓt kr-max

if ℓt,j > 0 and kℓt kr-max ≤ R2 Cρ2 and j ∈ {π(1), . . . , π(r)}

rR2


τt,j =
C
if ℓt,j > 0 and kℓt kr-max > R2 Cρ2 and j ∈ {π(1), . . . , π(r)}




0
otherwise
14

The correctness of both definitions of τt,j given above can be verified by observing thatkτt k∗ ≤ min{C, Rkℓ2tρk2 } and that τt · ℓt = min{C, Rkℓ2tρk2 }kℓt k in both cases. We now turn toproving an infinite-horizon cumulative loss bound for our algorithm.
Theorem 6 Let {(xt,j , yt,j )}1≤j≤k
t=1,2,... be a sequence of k-tuples of examples, where each xt,j ∈Rnj , kxt,j k2 ≤ R and each yt,j ∈ {−1, +1}. Let C be a positive constant, let k · k be an
absolute norm, and let ρ be an abbreviation for ρ(k · k∗ , k). Let w1⋆ , . . . , wk⋆ be arbitrary
vectors where wj⋆ ∈ Rnj , and define the hinge loss attained by wj⋆ on example (xt,j , yt,j ) to
be ℓ⋆t,j = 1 − yt,j wj⋆ · xt,j + . If we present this sequence to the explicit multitask algorithmwith the norm k · k and the aggressiveness parameter C, then for every T
2 2

1/(R ρ )

X

2

kℓt k

t≤T :kℓt k≤R2 Cρ2+ CX

kℓt k ≤ 2Ct≤T :kℓt k>R2 Cρ2

T
X
t=1

kℓ⋆t k+kX
j=1

kwj⋆ k22 .

Proof The starting point of our analysis is again Lemma 1. The choice of τt,j in Eq. (16)is clearly bounded by kτt k∗ ≤ C and conservative. It is also non-negative, due to the factthat k · k∗ is absolute and that ℓt,j ≥ 0. Therefore, τt,j meets the requirements of Lemma 1,
and we have
T X
k 
X
t=1 j=1

2
2τt,j ℓt,j − τt,j
kxt,j k22



≤

k
X
j=1

kwj⋆ k22 + 2C

T
X
t=1

kℓ⋆t k .

(18)

We now prove our theorem by lower-bounding the left hand side of Eq. (18) above. We analyze two different cases. First, if kℓt k ≤ R2 Cρ2 then min{C, kℓt k/(R2 ρ2 )} = kℓt k/(R2 ρ2 ).
Together with Eq. (17), this gives
2

k
X
j=1

τt,j ℓt,j = 2kτt k∗ kℓt k = 2

kℓt k2
.
R2 ρ2

(19)

P
2 kx k2 can be bounded by kτ k2 R2 . Using the definition of
On the other hand, kj=1 τt,j
t,j 2
t 2
remoteness, we bound this term by (kτt k∗ )2 R2 ρ2 . Using the fact that, kτt k∗ ≤ kℓt k/(R2 ρ2 ),we bound this term by kℓt k2 /(R2 ρ2 ). Overall, we have shown that
k
X
j=1

2
τt,j
kxt,j k22 ≤kℓt k2.
R2 ρ2

Subtracting both sides of the above inequality from the respective sides of Eq. (19) giveskXkℓt k2
2
2
2τ
ℓ
−
τ
kx
k
≤
.
t,j
t,j
t,j
t,j
2
R 2 ρ2(20)

j=1

Moving on to the second case, if kℓt k > R2 Cρ2 then min{C, kℓt k/(R2 ρ2 )} = C. Using
Eq. (17), we have that
2

k
X
j=1

τt,j ℓt,j = 2kτt k∗ kℓt k = 2Ckℓt k .
15

(21)

input: aggressiveness parameter C > 0, norm k · kinitialize w1,1 = . . . = w1,k = (0, . . . , 0)
for t = 1, 2, . . .
• receive xt,1 , . . . , xt,k• predict sign(wt,j · xt,j )[1 ≤ j ≤ k]

• receive yt,1 , . . . , yt,k• suffer loss ℓt,j = 1 − yt,j wt,j · xt,j +[1 ≤ j ≤ k]

• update:{wt+1,1 , . . . , wt+1,k } = argmin

w1 ,...,wk

s.t. ∀j1 Pk
2
j=1 kwj − wt,j k2 + Ckξk2

wj ·xt,j ≥ 1 − ξj and ξj ≥ 0

Figure 3: The implicit update algorithmPk∗ 2 2 22
2
As before, we can upper boundj=1 τt,j kxt,j k2 by (kτt k ) R ρ . Using the fact that,∗222kτt k ≤ C we can bound this term by C R ρ . Finally, using our assumption that kℓt k >R2 Cρ2 , we conclude that
k
X
2
τt,j
kxt,j k22 < Ckℓt k .
j=1

Subtracting both sides of the above inequality from the respective sides of Eq. (21) gives
Ckℓt k ≤

k
X
j=1

2
2τt,j ℓt,j − τt,j
kxt,j k22



.

(22)

Comparing the upper bound in Eq. (18) with the lower bounds in Eq. (20) and Eq. (22)proves the theorem.

Corollary 7 Under the assumptions of Thm. 6, if C is set to be 1/(R2 ρ2 ) then for every
T ′ ≤ T it holds that,
′

′

T
X
t=1


min kℓt k2 , kℓt k

≤ 2

T
X
t=1

kℓ⋆t k + R2 ρ2

k
X
j=1

kwj⋆ k22 .

As noted at the beginning ofPthis section, we do not obtain a cumulative loss bound perse, but rather at a bound on t min{ℓt , ℓ2t }. However, this bound holds simultaneously forevery prefix of the input sequence, and the algorithm does not rely on knowledge of the
input sequence length.
16

5. The Implicit Online Multitask Update
We now discuss a third family of online multitask algorithms, which leads to the strongest
loss bounds of the three families of algorithms presented in this paper. In contrast to
the closed form updates of the previous algorithms, the algorithms in this family require
solving an optimization problem on every round, and are therefore called implicit update
algorithms. Although the implementation of specific members of this family may be more
involved than the implementation of the multitask Perceptron, we recommend using thisfamily of algorithms in practice. On every round, the set of hypotheses is updated according
to the update rule:k1X
kwj − wt,j k22 + Ckξk2

{wt+1,1 , . . . , wt+1,k } = argmin

w1 ,...,wk

(23)

j=1

s.t. ∀jwj ·xt,j ≥ 1 − ξjand

ξj ≥ 0This optimization problem
P captures the fundamental tradeoff inherent to online learning.
On one hand, the term kj=1 kwj − wt,j k22 in the objective function above keeps the new
set of hypotheses close to the current set of hypotheses, so as to retain the information
learned on previous rounds. On the other hand, the term kξk in the objective function,
together with the constraints on ξj , forces the algorithm to make progress using the new
examples obtained on this round. Different choices of the global loss function lead todifferent definitions of this progress. The pseudo-code of the implicit update algorithm ispresented in Fig. 3.
Our first task is to show that this update procedure follows the skeleton outlined inFig. 1, and satisfies the requirements of Lemma 1. We do so by finding the dual of the
optimization problem given in Eq. (23).
Lemma 8 Let k · k be a norm and let k · k∗ be its dual. Then the online update defined in
Eq. (23) is equivalent to setting wt+1,j = wt,j + τt,j yt,j xt,j for all 1 ≤ j ≤ k, wherekXτt = argmax
τ

j=1
∗

2τj ℓt,j − τj2 kxt,j k22

s.t. kτk ≤ C and ∀j τj ≥ 0 .
Moreover, this update is conservative.
Proof The update step in Eq. (23) sets the vectors wt+1,1 , . . . , wt+1,k to be the solution
to the following constrained minimization problem:kmin

w1 ,...,wk ,ξ≥01X
kwj − wt,j k22 + Ckξk
2

(24)

j=1

s.t. ∀j yt,j wj ·xt,j ≥ 1 − ξj .
We begin by using the notion of strong duality to restate this optimization problem in an
equivalent form. The objective function above is convex and the constraints are both linear
17and feasible, therefore Slater’s condition (Boyd and Vandenberghe, 2004) holds, and theabove problem is equivalent to
max

min

τ≥0 w1 ,...,wk ,ξ≥0L(τ, w1 , . . . , wk , ξ) ,where L(τ, w1 , . . . , wk , ξ) is defined as follows:
k

k

j=1

j=1

X
1X
τj (1 − yt,j wj ·xt,j − ξj ) .
kwj − wt,j k22 + Ckξk +2
We can rewrite L as the sum of two terms, the first a function of τ and w1 , . . . , wk (denoted
L1 ) and the second a function of τ and ξ1 , . . . , ξk (denoted L2 ),
k
k
k
X
X
1X
2
τj (1 − yt,j wj ·xt,j ) + Ckξk −kwj − wt,j k2 +
τ j ξj .
2
j=1
j=1
j=1
|
{z
}
{z
}
|
L1 (τ,w1 ,...,wk )L2 (τ,ξ)Using the notation defined above, our optimization problem becomes,max
min L1 (τ, w1 , . . . , wk ) + min L2 (τ, ξ).
τ≥0w1 ,...,wkξ≥0

For any choice of τ, L1 is a convex function and we can find w1 , . . . , wk which minimize itby setting all of its partial derivatives with respect to the elements of w1 , . . . , wk to zero.
Namely,∂L1= wj,l − wt,j,l − τj yt,j xt,j,l .
∀j, l 0 =∂wj,lfrom the above we conclude that wj = wt,j + τj yt,j xt,j for all 1 ≤ j ≤ k.
The next step is to show that the update is conservative. If ℓt,j = 0 then setting
wj = wt,j satisfies the constraint yt,j wj · xt,j ≥ 1 − ξj with any choice of ξj ≥ 0. Sincechoosing wj = wt,j minimizes kwt − wt,j k22 and does not restrict our choice of any othervariable, then it is optimal. The relation between wj and τj now implies that τj = 0
whenever ℓt,j = 0).
Plugging our expression for wj into L1 , we have thatmin L1 (τ, w1 , . . . , wk ) =w1 ,...,wk

k
X
j=1

k

1X 2
τj (1 − yt,j wt,j · xt,j ) −τj kxt,j k .
2
j=1

Since the update is conservative, it holds that τj (1 − yt,j wt,j · xt,j ) = τj ℓt,j . Overall, we
have reduced our optimization problem to


k 

X
1
τt = argmax τj ℓt,j − τj2 kxt,j k + min L2 (τ, ξ) .
ξ≥0
2
τ≥0
j=1

18

We finally turn our attention to L2 and abbreviate B(τ) = minξ≥0 L2 (τ, ξ). We now claimthat B is a barrier function for the constraint kτk∗ ≤ C, namely
0if kτk∗ ≤ C
B(τ) =.
−∞
if kτk∗ > C
To see why this is true, recall that kτk∗ is defined to bePk
j=1 τj ǫj∗kτk = max
.
kǫk
ǫ∈Rk
First, let us consider the case where kτk∗ > C. In this case there exists a vector ǭ for whichkXj=1

τj ǭj − Ckǭk > 0 .

Denote the left hand side of the above by δ. We can assume w.l.o.g. that all the componentsof ǭ are non-negative since τ ≥ 0. For any c ≥ 0, we now have that
B(τ) = min L2 (τ, ξ) ≤ L2 (τ, cǭ) = − cδ .
ξ≥0Therefore, by taking c to infinity we get that B(τ)
P= −∞.
Turning to the case kτk∗ ≤ C, we have that kj=1 τj ξj ≤ Ckξk for any choice of ξ, orin other words, minξ≥0 L2 (τ, ξ) ≥ 0. However, this lower bound is attainable by setting
ξ = 0. We conclude that if kτk∗ ≤ C then B(τ) = 0. The original optimization problem has
reduced to the form


k 

X
1
τt = argmax τj ℓt,j − τj2 kxt,j k + B(τ) .
2
τ≥0
j=1

Clearly, the above is maximized in the domain where B(τ) = 0. Therefore, we replace thefunction B with the constraint kτk∗ ≤ C, and getτt =argmaxτ≥0 : kτk∗ ≤C

k 

X
1
τj ℓt,j − τj2 kxt,j k .
2
j=1

Lemma 5 proves that the implicit update essentially finds the value of τ t that maximizes
the left-hand side of the bound in Lemma 1. This choice of τ t produces the tightest loss
bounds that can be derived from Lemma 1. In this sense, the implicit update algorithm
takes full advantage of our proof technique. An immediate consequence of this observationis that the loss bounds of the multitask Perceptron also hold for the implicit algorithm.
More precisely, the bound in Thm. 4 (and Corollary 5) holds not only for the multitask
Perceptron, but also for the implicit update algorithm. Equivalently, it can be shown thatthe bound in Thm. 6 (and Corollary 7) also holds for the implicit update algorithm. We
prove this formally below.
19

Theorem 9 The bound in Thm. 4 also holds for the implicit update algorithm.
′ denote the weights defined by the multitask Perceptron in Eq. (9) and let
Proof Let τt,j
τt,j denote the weights assigned by the implicit update algorithm. In the proof of Thm. 4,
we showed that,2

2 2

2Ckℓt k − R C ρ

≤

k
X
j=1

′
′2
2τt,j
ℓt,j − τt,j
kxt,j k22

.

According to Lemma 8, the weights τt,j maximize,
k
X
j=1

2
2τt,j ℓt,j − τt,j
kxt,j k22,′ also satisfy thesesubject to the constraints kτt k∗ ≤ C and τt,j ≥ 0. Since the weights τt,jconstraints, it holds that,
k
X
j=1

′
′2
2τt,j
ℓt,j − τt,j
kxt,j k22



≤

k
X

k
X

2
2τt,j ℓt,j − τt,j
kxt,j k22

j=1

2
2τt,j ℓt,j − τt,j
kxt,j k22

.

Therefore, we conclude that
2Ckℓt k − R2 C 2 ρ2 ≤

j=1



.

(25)

Since τt,j is bounded, non-negative, and conservative (due to Lemma 8), the right-hand sideof the above inequality is upper-bounded by Lemma 1. Comparing the bound in Eq. (25)with the bound in Lemma 1 proves the theorem.
In the remainder of this paper, we present efficient algorithms which solve the optimization
problem in Eq. (23) for different choices of the global loss function.

6. Solving the Implicit Update for the L2 Norm
Consider the implicit update with the L2 norm, namely we are trying to solve
τt =argmaxτ≥0 : kτk2 ≤C

k 

X
1
τj ℓt,j − τj2 kxt,j k .
2
j=1

The Lagrangian of this optimization problem is
L =

k
X
j=1



k
X

2
2
τt,j
− C 2 ,2τt,j ℓt,j − τt,j
kxt,j k22 − θ 
j=1

where θ is a non-negative Lagrange multiplier. The derivative of L with respect to each τt,j
is, 2ℓt,j − 2τt,j kxt,j k22 − 2θτt,j . Setting this derivative to zero, we getτt,j =ℓt,j.
kxt,j k22 + θ
20

(26)

ℓ

The optimum of the unconstrained problem is attained by choosing τt,j = kx t,jk2 for each j.
t,j 2P
2 ≤ C 2 does not hold, then θ must be greaterIf, for this choice of τt , the constraint kj=1 τt,jthan zero. The KKT
condition implies that in this case the constraint
P complementarity
2 = C 2 . In order to find θ, we must now solve the following
is binding, namely kj=1 τt,jequation:
2
k 
X
ℓt,j
= C2 .
(27)
2+θ
kx
k
t,j 2
j=1

The left hand side of the above is monotonically decreasing in θ. We also know that θ > 0.
Moreover, setting√
kkℓt k∞θ =Cin the left-hand
side
of
Eq.
(27)
yields
a
value
which
is at least C 2 , and therefore we conclude√

t k∞. These properties enable us to easily find θ using binary search.
that θ ≤ kkℓC
In the special case where the norms of all the instances are equal, namely kxt,1 k22 =. . . = kxt,k k22 = R2 , Eq. (27) gives θ = kℓCt k2 − R2 , and therefore τt,j = Cℓt,j /kℓt k2 . The
general expression for τt,j in this case becomes ℓt,j2
if kℓt k2 ≤ R2 C
R.
(28)
τt,j =
 Cℓt,jotherwisekℓt k2

Note that the above coincides with the definition of τt given by the Infinite Horizon Multitask Perceptron for the L2 norm, as defined in Sec. 4.

7. Solving the Implicit Update for r-max Norms
We now present an efficient procedure for calculating the update in Eq. (23), in the casewhere the norm being used is the r-max norm. Lemma 8, together with (3), tells us thatthe update can be calculated by solving the following constrained optimization problem:
τt = argmax
τ

s.t.

k
X
j=1

k
X
j=1

2τj ℓt,j − τj2 kxt,j k22



(29)

τj ≤ Cr , ∀j τj ≤ C , ∀j τj ≥ 0 .

After dividing the objective function by 2, the Lagrangian of this optimization problem is
k
k
k
k 
 X


X
X
X
1 2
2
βj τj ,λj (C − τj ) +τj +τj ℓt,j − τj kxt,j k2 + θ Cr −
2
j=1

j=1

j=1

j=1

where θ, the βj ’s and the λj ’s are non-negative Lagrange multipliers. The derivative of Lwith respect to each τj is, ℓt,j − τj kxt,j k22 − θ − λj + βj . All of these partial derivatives must
equal zero at the optimum, and therefore∀1≤j≤kτj =ℓt,j − θ − λj + βj.
kxt,j k22

21

(30)

The KKT complementarity condition states that the following equalities hold at the optimum:∀1≤j≤kλj (C − τj ) = 0andβj τj = 0 .
(31)
We consider three different cases:
1. Assume that ℓt,j − θ < 0. Since both τj and λj must be non-negative, then from thedefinition of τj in Eq. (30) we learn that βj must be at least θ − ℓt,j . In other words,
βj is positive. Referring to the right-hand side of Eq. (31), we conclude that τj = 0.
2. Assume that 0 ≤ ℓt,j − θ ≤ Ckxt,j k22 . Summing the two equalities in Eq. (31) andplugging in the definition of τj from Eq. (30) results in,ℓt,j − θℓt,j − θ(βj − λj )2
λj C −
+
β
+
= 0 .
j
kxt,j k22
kxt,j k22
kxt,j k22

(32)

Using our assumption that ℓt,j −θ ≥ 0, along with the requirement that βj ≥ 0, gives us
2that β(ℓt,j −θ)/kxt,j k22 ≥ 0. Equivalently, using our assumption that ℓt,j −θ ≤ Ckx
t,j k2along with the requirement that λj ≥ 0 results in λ C − (ℓt,j + θ)/kxt,j k22 ≥ 0.
Plugging the last two inequalities back into Eq. (32) gives, (βj − λj )2 /kxt,j k22 ≤ 0.
The only way that this inequality can hold is if (βj − λj ) = 0. Thus, the definition ofℓ −θ
τj in Eq. (30) reduces to τj = kxt,j k2 .
t,j 2

3. Finally, assume that ℓt,j − θ > Ckxt,j k22 . Since τj ≤ kτk∞ ≤ C and βj ≥ 0, thenfrom Eq. (30) we conclude that λj is at least ℓt,j − θ − Ckxt,j k22 . In other words, λj
is positive. Referring to the left-hand side of Eq. (31), we conclude that (C − τj ) = 0,and τj = C.
Overall, we have shown that there exists some θ ≥ 0 such that the optimal update weights
take the form
0
if ℓt,j − θ < 0
ℓt,j −θ
if 0 ≤ ℓt,j − θ ≤ Ckxt,j k22 .
τt,j =(33)kx k2
 t,j 2
2
C
if Ckxt,j k2 < ℓt,j − θThat is, if the individual loss of task j is smaller than θ then no update is applied to therespective classifier. If the loss is moderate then the size of the update step is proportional
to the loss attained, and inverse proportional to the squared norm of the respective instance.
In any case, the size of the update step cannot exceed the fixed upper limit C.
We are thus left with the problem of finding the value of θ in Eq. (33) which yields
the update weights that maximize
Eq. (29). We denote this value by θ ⋆ . First note thatPk
if we lift the constraint
j=1 τt,j ≤ rC then the maximum of Eq. (29) is obtained by
setting τt,j = min{ℓt,j /kxt,j k22 , C} for all j, which is equivalent to setting θ = 0 in Eq. (33).
Therefore, if


k
X
ℓt,j
, C
≤ rC ,min
kxt,j k22
j=1
22

the solution to Eq. (29) is τt,j = min{ℓt,j /kxt,j k22 , C} for all j. Thus, we can focus ourattention on the case where


k
X
ℓt,j
min
, C
> rC .
kxt,j k22
j=1
P
In this case, θ ⋆ must be non-zero in order for the constraint kj=1 τj ≤ rC to hold. OnceP
again using the KKT complementarity condition, it follows that kj=1 τt,j = rC. Now, forevery value of θ, define the following two sets of indices:Ψ(θ) = {1 ≤ j ≤ k : 0 < ℓt,j − θ} ,andΦ(θ) = {1 ≤ j ≤ k : Ckxt,j k22 < ℓt,j − θ} .

Let Ψ and Φ denote the sets Ψ(θ ⋆ ) and Φ(θ ⋆ ) respectively. The semantics of Ψ and Φ arereadily available from Eq. (33): the set Ψ includes all indices j for which τj > 0 in the
optimal solution, while Φ includes all indices j for which τj is clipped at C in the optimal
solution. If we know the value of θ ⋆ , we can easily obtain the sets Ψ and Φ from theirdefinitions above. However, the converse is also true: if we are able to find the sets Ψ andΦ directly then we can use themcalculate the exact value of θ ⋆ . Assuming we know Ψ
Ptokand Φ, and using the fact that j=1 τj = rC, we getX
X ℓt,j − θ ⋆+C = rC .
kxt,j k22
j∈Φ

j∈Ψ\Φ

Solving the above for θ ⋆ gives
θ

⋆

=

P
ℓt,j
j∈Φ C
j∈Ψ\Φ kxt,j k22 − rC +PP

1j∈Ψ\Φ kxt,j k22

.

(34)

We have thus reduced the optimization problem in Eq. (29) to the problem of finding the setsΨ and Φ. Once we find Ψ and Φ, we can easily calculate θ ⋆ using Eq. (34) and then obtain τtusing Eq. (33). Luckily, Ψ and Φ are subsets of {1, . . . , k} and can only be defined in a finite
number of ways. A straightforward and excessively inefficient solution is to enumerate overall possible subsets of {1, . . . , k} as candidates for Ψ and Φ, for each pair of candidate sets
to compute the corresponding values of θ and τ using Eq. (34) and Eq. (33) respectively
andP
then check if the obtained solution is consistent with our constraints (θ ≥ 0, j τj = rC
and 0 ≤ τj ≤ C). Of the candidates that turn out to be consistent, we choose the one which
maximizes the objective function in Eq. (29). This approach is clearly infeasible even forreasonably small values of k. We therefore describe a more efficient procedure for findingΨ and Φ, whose computational cost is only O(k log(k)).
Let us examine two losses ℓt,r and ℓt,s such that ℓt,r ≤ ℓt,s and there is no index j forwhich ℓt,r < ℓt,j < ℓt,s . Then, all the sets Ψ(θ) for θ ∈ [ℓt,r , ℓt,s ) are identical, and equal{j : ℓt,j ≥ ℓt,r }. Therefore, there are at most k different choices for Ψ(θ), which canbe easily computed by sorting the losses. An analogous argument holds for the set Φ with23

respect to the values ℓt,j −Ckxt,j k22 . Furthermore, to enumerate all admissible sets Ψ(θ) andΦ(θ) we need not examine their product space. Instead, let q denote the vector obtainedby sorting the union of the sets {ℓt,j }kj=1 , {ℓt,j − Ckxt,j k22 }kj=1 , and {0} in ascending order.
Extending the above rationale, the sets Ψ(θ) and Φ(θ) are fixed for every θ ∈ [qi , qi+1 ). We
can examine every possible pair of candidates Ψ(θ), Φ(θ) by traversing the sorted vector q
of critical values.
Concretely, define Ψ(q1 ) = {1, . . . , k} and Φ(q1 ) = {1, . . . , k}, and keep them sorted inmemory. Use these sets to define θ and τ as described above, and check if the solution
satisfies our constraints. If so, return this value of τ as the update step for the r-max
loss. Otherwise, move on to the next value in q and evaluate the next pair of candidates.
This procedure for choosing θ and τ implies that if more than one solution satisfies theconstraints, we will choose the one encountered first, namely the one for which θ is thesmallest. Indeed it can be verified that the smaller θ, the greater the value of the objectivefunction in Eq. (29). Given the sets Ψ(qi ) and Φ(qi ), we can obtain the sets Ψ(qi+1 ) andΦ(qi+1 ), and recalculate θ, by simply removing from Ψ(qi ) every j for which ℓt,j < qi+1 andremoving from Φ(qi ) every j for which ℓt,j − Ckxt,j k22 < qi+1 . This operation can be done
efficiently since the sets Ψ(qi ) and Φ(qi ) are sorted in memory.

8. Experiments with Text Classification
In this section, we demonstrate the effectiveness of the implicit multitask algorithm on largescale text categorization problems. Throughout this paper, we have argued that when facedwith multiple tasks in parallel, we can often do better than to learn each task individually.
The goal of the first two experiments is to demonstrate that this is indeed the case. The third
experiment demonstrates that the superiority of the implicit update algorithm, presented
in Sec. 5, over the multitask Perceptron, presented in Sections 3 and 4.
We used the Reuters Corpus Vol. 1, which is a collection of over 800K news articles
collected from the Reuters newswire over a period of 12 months, in 1996-1997. An averagearticle contains approximately 240 words, and the entire corpus contains over half a million
distinct tokens (not including numbers and dates). Each article is associated with one
or more of 104 possible low-level categories1 . On average, each article is associated with
1.5 low-level categories. The categorization problem induced by this corpus is referred toas a multiclass-multilabel (MCML) problem, since there are multiple possible classes (the104 categories) and each article may assigned multiple labels. Examples of categories thatappear in the corpus are: weather, money markets, and unemployment. The articles
in the corpus are given in their original chronological order, and our goal is to predict thelabel, or labels, associated with each newly presented article. Our first experiment addresses
this problem.
The Reuters corpus also defines 5 high-level meta-categories: corporate/industrial,
economics, government/social, markets, and other. About 20% of the articles in
the corpus are associated with more than one of the five meta-categories. After discarding
this 20%, we are left with over 600K documents, each with a single high-level label. This
1. The original corpus specifies 126 labels which are organized in a hierarchical tree-structure. Of theselabels, 104 are low-level categories, which correspond to leaves in the tree. The remaining labels aremeta-categories which correspond to inner nodes in the tree.

24

1
0.9
0.8

1−error rate∞−error rate

0.02∞−norm1−norm0.7
0.6∞−norm1−norm

0.015

0.01

0.5
0.4
0

2

4
online rounds

6

0.005

8
5
x 10

0

2

4
online rounds

6

8
5
x 10

Figure 4: The ∞-error (left) and 1-error (right) error-rates attained by the implicit multitask algorithm using the L∞ norm (solid) and the L1 norm (dashed) global loss
functions. Note that the two plots are on a very different scale: the two lines on
the left-hand plot differ by approximately 3%, whereas the lines on the right-handplot differ by approximately 0.05%.

induces a 5-class single-label classification problem. Our second experiment addresses thismulticlass single-label problem.
We began by applying some mild preprocessing to the articles in the corpus, which
included removal of punctuation, numbers, dates, and stop-words, and a global conversionof the entire corpus to lower-case. Then, each article was mapped to a real vector using
a logarithmic bag-of-words representation. Namely, the length of each vector equals thenumber of distinct tokens in the corpus, and each coordinate represents one of these tokens.
If a token appears s times in a given article, then the respective coordinate in the vector isset to log2 (1 + s).
8.1 Multiclass Multilabel Categorization
We trained a separate binary classifier for each of the 104 low-level classes, using the implicit
update algorithm presented in Sec. 5. Given an unseen article, each classifier predicts
whether its respective category applies to that article or not. We ran our algorithm using
both the L1 norm and the L∞ norm as the global loss function. In both cases, the userdefined parameter C was set to 10−3 .
The performance of the entire classifier ensemble on each article was evaluated in two
ways. First, we examined whether the 104-classifier ensemble predicted the entire set of
categories perfectly. An affirmative answer to this test implies that all 104 classifiers madecorrect predictions simultaneously. Formally, let et be the vector in {0, 1}104 such that
et,j = 1 if and only if yt,j wt,j · xt,j ≤ 0. In other words, et indicates which of the 104
binary classifiers made prediction mistakes on round t. Now define the ∞-error suffered onround t as ket k∞ . Second, we assessed the fraction of categories for which incorrect binary
predictions were made. Formally, define the 1-error suffered on round t as ket k1 /104. Both25

10K examples

100K examples

600K examples

multiclass error rate

0.13
0.078
0.125

0.052

0.076
0.12

0.074

0.115

0.072

0.051
0.05

0.07
0.11
0

5

r

10

15

0

5

r

10

15

0

5

r

10

15

Figure 5: The multiclass error rate of the online ECOC-based classifier, using a 15 column
code matrix, with various r-max norms, after observing 10K, 100K, and 600K
examples.

measures of error are reasonable, and one should be preferred over the other based on
the specific requirements of the underlying application. Since each coordinate of ℓt upperbounds the respective coordinate in et , it holds that ket k∞ ≤ kℓt k∞ and that ket k1 ≤ kℓt k1 .
Therefore, the L∞ norm update seems to be a more appropriate choice for minimizing the∞-error, while the L1 norm update is the more appropriate choice for minimizing the 1error. Our experiments confirm this intuitive argument.
The results of our experiments are summarized in Fig. 4. The left-hand plot in the figure
shows the ∞-error-rate of the L∞ norm and L1 norm multitask updates, as the number ofexamples grows from zero to 800K. The figure clearly shows that the L∞ norm algorithm
does a better job throughout the entire online learning process. The advantage of the L∞
norm algorithm diminishes as more examples are observed.
The right-hand plot in Fig. 4 compares the 1-error-rate of the two updates. In thiscase, the L∞ norm update initially takes the lead, but is quickly surpassed by the L1 norm
update. The fact that the L1 norm update ultimately gains the advantage coincides with
our initial intuition. The reason why the L∞ norm update outperforms the L1 norm update
at first can also be easily explained. The L1 norm update is quite aggressive, as it modifies
every binary classifier that suffers a positive individual loss on every round. Moreover, theL1 norm update enforces the constraint kτ t k∞ ≤ C. On the other hand, the L∞ norm
update is more cautious, since it enforces the stricter constraint kτ t k1 ≤ C. The aggressionof the L1 norm update causes its initial behavior to be somewhat erratic. At first, many of
the L1 norm updates actually move the classifier ensemble away from its target. Inevitably,
it takes the L1 norm classifier slightly longer to find its path.
8.2 Multiclass Meta-Categorization with ECOC and r-max Norms
Following one of the motivating examples given in the introduction, we used the ECOC
method (Dietterich and Bakiri, 1995) to reduce the 5 high-level meta-categories classification
task from the Reuters corpus to multiple binary classification tasks. We used the 5 × 15
26

Hadamard code matrix, defined as follows:+ + + + + + + + + + + + + +M =  + + + − − − − + − − + + − −− + − + − + −

+
−
+
+
+

+
−
+
+
−

+
−
+
−
+

+
−
+
−
−

+
−
−
+
+

+
−
−
+
−

+
−
−
−
+


+
− 

− 
 .
− 
−

This code matrix is derived by taking all 24 possible 5-coordinate columns with + in thefirst position, except for the all-plus column. This is the largest 5-row code matrix that
does not induce redundant or trivial binary classification problems. The distance between
any two rows of the matrix is 8, therefore this code is guaranteed to correct 4 binary
prediction mistakes. We can determine if more than 4 binary mistakes are made on roundt by comparing the fifth largest element of ℓt with 1. As mentioned in the introduction,
taking the fifth largest loss does not constitute a norm, and cannot be used as a global
loss within our setting. However, a norm with a similar flavor is the r-max norm, withr = 5. Our experiments show that it is actually advantageous to be slightly over-cautious,by setting r to 3 or 4.
The results of our experiments are summarized in Fig. 5. We trained 15 binary classifiers,
one per each column of M , using the implicit update algorithm presented in Sec. 5. We
used the r-max norm as the algorithm’s global loss function, with r set to every integer
value between 1 and 15. For each example, all 15 binary classifiers made predictions, and M
was used to decode a multiclass prediction, as described in (Dietterich and Bakiri, 1995). A
multiclass error occurs if the predicted label differs from the true label. In Fig. 5 we depict
the average number of errors that occurred after observing 10K, 100K, and 600K examples,for each value of r. We can see that using either the L1 norm (r = 15) or the L∞ norm(r = 1) is suboptimal, and the best performance is consistently reached by setting r to beslightly smaller than half the code distance. Although the theoretically motivated choice ofr = 5 is not the best, it still yields better results than the two extreme choices, r = 1 andr = 15.
When we replaced the Hadamard code matrix with the One-vs-Rest code matrix, definedby 2I − 1 (where I is the 5 × 5 identity matrix and 1 is the 5 × 5 all-ones matrix) thenthe multiclass error after observing 600K examples increases from 5% to around 8%. Thisjustifies using the ECOC method in the first place.
We conclude this experiment by noting that although setting r = 1 produces the largest
number of multiclass prediction mistakes, it still delivers the best performance if we evaluate
the 15 classifier ensemble using the ∞-error defined above.
8.3 The Implicit Update vs. the Multitask Perceptron
From a loss minimization standpoint, Thm. 9 proves that the implicit update, presented inSec. 5, is at least as good as the multitask Perceptron variants, presented in Secs. 3 and 4.
The following experiment demonstrates that the implicit update is also superior in practice.
We repeated the multitask multi-label experiment described in Sec. 8.1, using the multitask Perceptron in place of the implicit update algorithm. The infinite horizon extension
discussed in Sec. 4 does not have a significant effect on empirical performance, so we consider
only the finite horizon version of the multitask Perceptron, described in Sec. 3.
27

0.8

∞−norm perceptron∞−norm implicit
0.025
1−error rate

0.7∞−error rate∞−norm perceptron∞−norm implicit

0.6

0.5

0.02
0.015
0.01

0.4
0

2

4
online rounds

6

0.005

8
5
x 10

0

2

4
online rounds

6

8
5
x 10

Figure 6: The ∞-error (left) and 1-error (right) attained by the multitask Perceptron(dashed) and the implicit update algorithm (solid) when using the L∞ norm
as a global loss function.

When the global loss function is defined using the L1 norm, both the implicit update
and the multitask Perceptron update decouple to independent updates for each individualtask. In this case, both algorithms are very similar, their empirical performance is almost
identical, and the comparison between them is not very interesting. Therefore, we focus ona global loss defined by the L∞ norm.
A comparison between the performance of the implicit update and the multitask Perceptron update, both using the L∞ -norm loss, is given in Fig. 6. The plot on the left-hand sideof the figure compares the two algorithms’ ∞-error-rate, and the plot on the right-hand sideof the figure compares their 1-error-rate. The implicit algorithm holds a clear lead over themultitask Perceptron with respect to both error measures, throughout the learning process.
These results give empirical validation to the formal comparison of the two algorithms.

9. Discussion
When faced with several online tasks in parallel, it is not always best to distribute thelearning effort evenly. In many cases, it may be beneficial to allocate more effort to tasks
when they are seen to play “key” roles. In this paper, we presented an online algorithmic
framework that does precisely that. The priority given to each task is governed by its
relative performance and by the choice of a global loss function.
We presented three families of algorithms, each of which includes an algorithm forevery global loss defined by an absolute norm. The first two families are illustrative andtheoretically appealing. The third family of algorithms uses the most sophisticated updateof the three, and is the one recommended for practical use. We demonstrated the superior
performance of the third family of algorithms empirically.
We showed that, in the worst case, the finite horizon multitask Perceptron of Sec. 3
and the implicit update algorithm of Sec. 5 both perform asymptotically as well as the best28

fixed hypothesis ensemble. In other words, these algorithms are no-regret algorithms withrespect to any global loss function defined by an absolute norm. The same cannot be said
for the naive alternative, where we use multiple independent single-task learning algorithms
to solve the multitask problem. We also demonstrated the benefit of the multitask approachover the naive alternative on two large-scale text categorization problems.
Throughout the paper, we assumed that the multiple online tasks are perfectly synchronized, and that a complete k-tuple of examples is observed on every round. This is indeed
the case in each of the concrete examples described in the introduction and empiricallytested in our experiments. However, in other real-world situations, this may not be thecase. Namely, there could occur situations where not all of the tasks are active on every
single round. In other words, there may be a subset of “dormant tasks” on each round. For
example, say that we are operating an online store and that we have multiple registeredcustomers. Each product in our store is represented by a feature vector, and we train an individual binary classifier for each of our customers. When costumer j visits a product-pageon our website, the respective classifier is used to predict whether that customer intends topurchase the product or not. The prediction is then used to decide whether or not to lure
the customer away from that page. This setting induces a natural online multitask learning
problem. Moreover, only a fraction of the customers is online at any given moment. We
consider the tasks of those customers that are not online to be dormant or inactive tasks.
At a first glance, the inactive tasks setting may seem to be more complicated than the
fully synchronized setting discussed throughout the paper. However, our algorithms andanalysis accommodate this extension quite naturally. We simply need to define ℓt,j = 0 for
every inactive task and apply the multitask update verbatim. Due to the conservativenessassumption, the hypotheses of the inactive tasks will be left intact. Additionally, note that
all of the norms discussed in this paper have the property that kvk = kv′ k, where v′ isthe vector obtained by removing all of the zero entries from v. Therefore, we can imagine
that the length of the vector ℓt changes from round to round, and that the update on eachround is applied as if the tasks that are sleeping on that round never existed in the firstplace. We would also like to note that, although our presentation focuses on multiple binaryclassification tasks, our algorithms and techniques can be adapted to other online learning
problems as well. Specifically, a multitask implicit update can be derived for regression anduniclass problems using ideas from (Crammer et al., 2006).
The next-step would be to extend our framework from absolute norms to general norms.
For example, the family of Mahalanobis norms, defined by kzk2 = z⊤ P z (where P isa positive definite matrix) includes norms that are not absolute but which could haveinteresting applications in our setting. More generally, there exist meaningful global loss
functions which are not norms at all.
Another interesting research direction would be to return to the roots of statistical multitask learning, and to try to model generative similarities between the multiple tasks within
the online framework. In our work, we completely disregarded any relatedness between themultiple tasks, and only considered the shared consequences of errors. In the game-theoretic
spirit of online learning, modeling these similarities would have to be done without making
statistical assumptions on the data source.
29

References
J. Baxter. A model of inductive bias learning. Journal of Artificial Intelligence Research,
12:149–198, 2000.
S. Ben-David and R. Schuller. Exploiting task relatedness for multiple task learning. In
Proceedings of the Sixteenth Annual Conference on Computational Learning Theory, 2003.
C. Bennett and R. Sharpley. Interpolation of Operators. Academic Press, 1998.
S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
R. Caruana. Multitask learning. Machine Learning, 28(1):41–75, 1997.
O. Chapelle and Z. Harchaoui. A machine learning approach to conjoint analysis. In
Advances in Neural Information Processing Systems, volume 17, 2005.
K. Crammer and Y. Singer. On the algorithmic implementation of multiclass kernel-based
vector machines. Journal of Machine Learning Research, 2:265–292, 2001.
K. Crammer and Y. Singer. Ultraconservative online algorithms for multiclass problems.
Journal of Machine Learning Research, 3:951–991, 2003.
K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz, and Y. Singer. Online passive aggressive algorithms. Journal of Machine Learning Research, 7:551–585, Mar 2006.
T. G. Dietterich and G. Bakiri. Solving multiclass learning problems via error-correcting
output codes. Journal of Artificial Intelligence Research, 2:263–286, January 1995.
T. Evgeniou, C.Micchelli, and M. Pontil. Learning multiple tasks with kernel methods.
Journal of Machine Learning Research, 6:615–637, 2005.
D. P. Helmbold, J. Kivinen, and M. Warmuth. Relative loss bounds for single neurons.
IEEE Transactions on Neural Networks, 10(6):1291–1304, 1999.
R. Herbrich, T. Graepel, and K. Obermayer. Large marging rank boundaries for ordinal
regression. In A. Smola, B. Schölkopf, and D. Schuurmans, editors, Advances in Large
Margin Classifiers. MIT Press, 2000.
T. Heskes. Solving a huge number of silmilar tasks: A combination of multitask learning anda hierarchical bayesian approach. In Proceedings of the Fifteenth International Conference
on Machine Learning, pages 233–241, 1998.
R. A. Horn and C. R. Johnson. Matrix Analysis. Cambridge University Press, 1985.
J. Kivinen and M. Warmuth. Relative loss bounds for multidimensional regression problems.
Journal of Machine Learning, 45(3):301–329, July 2001.
A. B. J. Novikoff. On convergence proofs on perceptrons. In Proceedings of the Symposiumon the Mathematical Theory of Automata, volume XII, pages 615–622, 1962.
30

F. Rosenblatt. The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65:386–407, 1958. (Reprinted in Neurocomputing(MIT Press, 1988).).
I. Tsochantaridis, T. Hofmann, T. Joachims, and Y. Altun. Support vector machine learningfor interdependent and structured output spaces. In Proceedings of the Twenty-FirstInternational Conference on Machine Learning, 2004.

Appendix A. The K-Method of Norm Interpolation
In this section, we briefly survey Peetre’s K-method of norm interpolation. This method
takes a pair of norms and smoothly interpolates between them, producing a new family ofnorms which can be used in our setting. An example of such an interpolation is the familyof r-max norms, previously mentioned in this paper. The main practical purpose of thissection is to prove that the dual of the r-max norm takes the form given in Eq. (3). We
do not present the K-method in all its generality, but rather focus only on topics which
are relevant to the online multitask learning setting. The interested reader is referred to(Bennett and Sharpley, 1998) for a more detailed account of interpolation theory.
We begin by presenting Peetre’s K-functional and J-functional, and proving that they
induce dual norms. Let k · kp1 : Rk → R+ and k · kp2 : Rk → R+ be two p-norms, and let
k · kq1 and k · kq2 be their respective duals. The K-functional with respect to p1 and p2 , andwith respect to the constant α > 0, is defined as
kvkK(p1 ,p2 ,α) = min
kwkp1 + αkzkp2 .
w+z=v

The J-functional with respect to q1 , q2 , and with respect to the constant β > 0, is definedasonkukJ(q1 ,q2 ,β) = max kukq1 , β kukq2 .

The J-functional is obviously a norm: positivity and linearity follow immediately from thefact that k · kq1 and k · kq2 posses these properties. The triangle inequality follows fromon
kv + ukJ(q1 ,q2 ,β) = max kv + ukq1 , β kv + ukq2on≤ max kvkq1 + kukq1 , βkvkq2 + βkukq2oonn≤ max kvkq1 , βkvkq2 + max kukq1 , βkukq2= kvkJ(q1 ,q2,β) + kukJ(q1 ,q2,β) .

Since the J-functional is defined with respect to two absolute norms, it too is an absolute
norm.
Instead of explicitly proving that k · kK(p1 ,p2 ,α) is also a norm, we prove that it is thedual of k · kJ(q1 ,q2,β) when α = 1/β. Since the dual of an absolute norm is itself an absolutenorm, and since the dual of the dual norm is the original norm (Horn and Johnson, 1985),
our proof implies that k · kK(p1 ,p2 ,α) is indeed a norm, that it is absolute, and that its dual
is k · kJ(q1 ,q2 ,1/α) .
31

Theorem 10 Using the notation defined above,k · k∗J(q1 ,q2,β) ≡ k · kK(p1 ,p2 ,1/β) .
Proof We abbreviate kvkJ = kvkJ(q1 ,q2 ,β) and kvkK = kvkK(p1 ,p2 ,1/β) throughout theproof. First, we show that kvk∗J ≤ kvkK for all v ∈ Rk . Let v, w and z be vectors in Rk
such that v = w + z. Then for any u ∈ Rk , we can use Hölder’s inequality to obtain
u·v=

u·w + u·z≤

kukq1 kwkp1 + kukq2 kzkp2 .

By definition, it holds thatkukq1 ≤ kukJand so
u·v ≤



and

kukq2 ≤

1
kwkp1 + kzkp2
β

1
kukJ ,
βkukJ .

Since the only restriction on u, v, w and z is that v = w + z, we can fix v, choose u to be
the vector which maximizes the left-hand side above subject to kukJ ≤ 1, and choose w
and z which minimize the right-hand side above subject to v = w + z. This results in


1
.
max
u · v ≤ min kwkp1 + kzkp2
w+z=v
βu∈Rk :kukJ ≤1
The left-hand side above is the formal definition of kvk∗J , the right-hand side is the definitionof kvkK , and we have proven that kvk∗J ≤ kvkK .
To prove the opposite direction, fix v and let u be the vector with kukJ ≤ 1 which
maximizes u · v. We now consider two cases. If kukq1 ≥ βkukq2 then
kvk∗J =

max

u:kukq1 ≤1

u·v .

Using the duality of k · kq1 and k · kp1 , the right hand-side above equals kvkp1 . Since we canchoose w = v and z = 0, it certainly holds that
1
kvkp1 ≥ min
kwkp1 + kzkp2 = kvkK .
w+z=vβ
On the other hand, if kukq1 ≤ βkukq2 then
kvk∗J =

1
max u · v .
β u:kukp2 ≤1

Using the duality of k · kq2 and k · kp2 , the right hand-side above equals β1 kvkp2 . Since we
can choose w = 0 and z = v, it holds that
1
1
kvkp2 ≥ min
kwkp2 + kzkp2 = kvkK .
w+z=v
β
β
32

Overall, we have shown that kvk∗J ≥ kvkK .
The r-max norm discussed in the paper is an instance of the K-functional, and can be
defined as
kvkr-max = kvkK(1,∞,r) .
To see why this is true, let φ be the absolute value of the r’th absolutely largest coordinate
in v. Now define for each 1 ≤ j ≤ k
wj = sign(vj ) max{0, |vj | − φ}andzj = sign(vj ) min{|vj |, φ} .

Note that w + z = v, and thatkvkr-max = kwk1 + rkzk∞ .
This proves that kvkr-max ≥ kvkK(1,∞,r) .
Turning to the opposite inequality, let π(1), . . . , π(r) be the indices of the r absolutely
largest elements of v, and let w and z be vectors such that w + z = v. We now have thatkvkr-max =
=
≤
≤
≤

r
X
j=1

r
X

j=1
r
X

j=1
r
X
j=1

k
X
j=1

|vπ(j) ||wπ(j) + zπ(j) ||wπ(j) | +

r
X
j=1

|zπ(j) ||wπ(j) | + r max |zπ(j) |j=1,...,r|wj | + r max |zj | = kwk1 + rkzk∞ .
j=1,...,k

The above holds for any w and z which sum to v, and specifically to those which minimize kwk1 + rkzk∞ . We conclude that kvkr-max ≤ kvkK(1,∞,r) , and therefore kvkr-max =kvkK(1,∞,r) .
Finally, we calculate an upper bound on the remoteness of k · kJ(q1 ,q2 ,β) . This enables
us to obtain concrete loss bounds for interpolation norms from the theorems proven in thispaper. Recall thatkuk2
ρ(k · kJ(q1 ,q2 ,β) , k) = max.
ku∈R kukJ(q1 ,q2 ,β)Using the definition of the J-functional, the above becomes
kuk2 kuk2,.
max minkukq1 βkukq2u∈Rk33

Using the weak minimax theorem, we can upper-bound the above by


kuk2
kuk2
min max, max.
u∈Rk kukq1 u∈Rk βkukq2
Once again using the definition of remoteness, the above can be rewritten asρ(k · kq2 , k).
min ρ(k · kq1 , k),βUsing Lemma 2, we can obtain an explicit upper bound on the remoteness of any interpolation of p-norms.

34