Title: LIFELONG LEARNING WITH OUTPUT KERNELS

Abstract: Lifelong multitask learning poses considerable challenges in terms of effectiveness (minimizing prediction errors for all tasks) and overall computational tractability for real-time performance. This paper addresses continuous lifelong multitask learning by jointly re-estimating the inter-task relations (output kernel) and the per-task model parameters at each round, assuming data arrives in a streaming fashion. A new algorithm called Online Output Kernel Learning Algorithm (OOKLA) for lifelong learning setting is proposed. To avoid the memory explosion, a robust budget-limited versions of the proposed algorithm is introduced, which efficiently utilizes the relationships between the tasks to bound the total number of representative examples in the support set. In addition, a two-stage budgeted scheme for efficiently tackling the task-specific budget constraints in lifelong learning is proposed. Empirical results over three datasets indicate superior AUC performance for OOKLA and its budget-limited cousins over strong baselines.

1. INTRODUCTION:

Instead of learning individual models, learning from multiple tasks leverages the relationships among tasks to jointly build better models for each task and thereby improve the transfer of relevant knowledge between the tasks, especially from information-rich tasks to information-poor ones. Unlike traditional multitask learning, where the tasks are presented simultaneously and an entire training set is available to the learner (Caruana (1998) ), in lifelong learning the tasks arrives sequentially (Thrun (1996) ). This paper considers a continuous lifelong learning setting in which both the tasks and the examples of the tasks arrive in an online fashion, without any predetermined order.

Following the online setting, particularly from Saha et al. (2011) ; Cavallanti et al. (2010) , at each round t, the learner receives an example from a task, along with the task identifier and predicts the output label for the example. Subsequently, the learner receives the true label and updates the model(s) as necessary. This process is repeated as we receive additional data from the same or different tasks. Our approach follows an error-driven update rule in which the model for a given task is updated only when the prediction for that task is in error.

Lifelong learning poses considerable challenges in terms of effectiveness (minimizing prediction errors for all tasks) and overall computational tractability for real-time performance. A lifelong learning agent must provide an efficient way to learn new tasks faster by utilizing the knowledge learned from the previous tasks and also not forgetting or significantly degrading performance on the old tasks. The goal of a lifelong learner is to minimize errors as compared to the full ideal hindsight learner, which has access to all the training data and no bounds on memory or computation. This paper addresses lifelong multitask learning by jointly re-estimating the inter-task relations from the data and the per-task model parameters at each round, assuming data arrives in a streaming fashion. We define the task relationship matrix as output kernels in Reproducing Kernel Hilbert Space (RKHS) on multitask examples. We propose a novel algorithm called Online Output Kernel Learning Algorithm (OOKLA) for lifelong learning setting. For a successful lifelong learning with kernels, we need to address two key challenges: (1) learn the relationships between the tasks (output kernel) efficiently from the data stream and (2) bound the size of the knowledge to avoid memory explosion.

The key challenge in learning with a large number of tasks is to adaptively learn the model parameters and the task relationships, which potentially change over time. Without manageability-efficient updates at each round, learning the task relationship matrix automatically may impose a severe computational burden. In other words, we need to make predictions and update the models in an efficient real time manner.

We propose simple and quite intuitive update rules for learning the task relationship matrix. When we receive a new example, the algorithm updates the output kernel when the learner made a mistake by computing the similarity between the new example and the set of representative examples (stored in the memory) that belongs to a specific task. If the two examples have similar (different) labels and high similarity, then the relationship between the tasks is increased (decreased) to reflect the positive (negative) correlation and vice versa.

To avoid the memory explosion associated with the lifelong learning setting, we propose a robust budget-limited version of the proposed algorithm that efficiently utilizes the relationship between the tasks to bound the total number of representative examples in the support set. In addition, we propose a two-stage budgeted scheme for efficiently tackling the task-specific budget constraints in lifelong learning.

It is worth noting that the problem of lifelong multitask learning is closely related to online multitask learning. Although the objectives of both online multitask learning and lifelong learning are similar, one key difference is that the online multitask learning, unlike in the lifelong learning, may require that the number of tasks be specified beforehand. In recent years, online multitask learning has attracted extensive research attention Abernethy et al. (2007) ; Dekel et al. (2007) ; Lugosi et al. (2009) ; Cavallanti et al. (2010) ; Saha et al. (2011); Murugesan et al. (2016) . We evaluate our proposed methods with several state-of-the-art online learning algorithms for multiple tasks. Throughout this paper, we refer to our proposed method as online multitask learning or lifelong learning.

There are many useful application areas for lifelong learning, including optimizing financial trading as market conditions evolve, email prioritization with new tasks or preferences emerging, personalized news, and spam filtering, with evolving nature of spam. Consider the latter, where some spam is universal to all users (e.g. financial scams), some messages might be useful to certain affinity groups, but spam to most others (e.g. announcements of meditation classes or other special interest activities), and some may depend on evolving user interests. In spam filtering each user is a "task," and shared interests and dis-interests formulate the inter-task relationship matrix. If we can learn the matrix as well as improving models from specific spam/not-spam decisions, we can perform mass customization of spam filtering, borrowing from spam/not-spam feedback from users with similar preferences. The primary contribution of this paper is precisely the joint learning of inter-task relationships and its use in estimating per-task model parameters in a lifelong learning setting.

1.1. RELATED WORK:

Most existing work in online learning of multiple task focuses on how to take advantage of task relationships. To achieve this, Lugosi et al. (2009) imposed a hard constraint on the K simultaneous actions taken by the learner in the expert setting, Agarwal et al. (2008) used matrix regularization, and Dekel et al. (2007) proposed a global loss function, as an absolute norm, to tie together the loss values of the individual tasks. Different from existing online multitask learning models, our paper proposes an intuitive and efficient way to learn the task relationship matrix automatically from the data, and to explicitly take into account the learned relationships during model updates. Cavallanti et al. (2010) assumes that task relationships are available a priori. However often such taskrelation prior knowledge is either unavailable or infeasible to obtain for many applications especially when the number of tasks K is large (Weinberger et al. (2009) ) and/or when the manual annotation of task relationships is expensive (Kshirsagar et al. (2013) ). Saha et al. (2011) formulated the learning of task relationship matrix as a Bregman-divergence minimization problem w.r.t. positive definite matrices. The model suffers from high computational complexity as semi-definite programming is required when updating the task relationship matrix at each online round. We show that with a different formulation, we can obtain a similar but much cheaper updating rule for learning the inter-task weights. Murugesan et al. (2016) proposed an efficient method for learning the task relationship matrix using the cross-task performance measure, but their approach learns only the positive correlation between the tasks. Our proposed approach learns positive and negative correlations between the tasks for robust transfer of knowledge from the previously learned tasks.

Recent work in output kernel learning estimate the task covariance matrix in RKHS space, inferred it directly from the data (Dinuzzo et al. (2011) ; Sindhwani et al. (2013) ; Jawanpuria et al. (2015) ). The task covariance matrix is called the output kernel defined on the tasks, similar to the scalar kernel on the inputs. Most recently, Jawanpuria et al. (2015) showed that for a class of regularization functions, we can efficiently learn this output kernel. Unfortunately most of the proposed methods for learning output kernels require access to the entire data for the learning algorithm, a luxury unavailable in online learning and especially in the lifelong learning setting.

Unlike in online multitask learning, most lifelong learning approaches use a single model for all the tasks or reuse the models from the previous tasks to build a model for the new task (Alquier et al. (2016) 2013)). These approaches either increase the computation time on iterations where we encounter a novel task or reduce the prediction power of the model learned from the previous tasks due to catastrophic forgetting. To the best of our knowledge, relationships among the tasks has not been successfully exploited in the lifelong learning setting due to the difficulty in learning a positive semi-definite task relationship matrix in large-scale applications. This paper provides an efficient way to learn the task relationship matrix in the lifelong learning setting.

2. LIFELONG LEARNING OF MULTIPLE TASKS:

Let ((x t , i t ), y t ) be the example received by the learner from the task i t (at the time step t) where we assume that the x t ∈ X and y t is its corresponding true label. The task i t can be a new task or one seen by the learner in the previous iterations. We denote by [N ] the consecutive integers ranging from 1 to N . In this paper, we do not assume that the number of tasks is known to the learner ahead of time, an important constraint in lifelong learning problems. Let K be the number of tasks seen so far until the current iteration t.

For brevity, we consider a binary classification problem for each task y t ∈ {-1, +1}, but the methods generalize to multi-class cases and are also applicable to regression tasks. We assume that the learner made a mistake if y t = ŷt where ŷt is the predicted label. Our approach follows a mistake-driven update rule in which the model for a given task is updated only on rounds where the learner predictions differ from the true label.

Let K : X × X → R (kernel on input space) and Ω : N × N → R (output kernel) be symmetric, positive semi-definite (p.s.d) multitask kernel functions and denote H as their corresponding RKHS of functions with the norm • H on multitask examples (Smola & Schölkopf (1998) ; Dinuzzo et al. (2011); Jawanpuria et al. (2015) ). Using the above notation, we can define a kernel representation of an example based on a set of representative examples collected on the previous iterations (prototypes). Formally, given an example x ∈ X , its kernel representation can be written using this set:

x -→ {K(x, x s ) : s ∈ S} S is the set of stored examples for which the learner made a mistake in the past. The set S is called the support set. The online classification function is then defined as the weighted sum of the kernel combination of the examples in the support set. To account for the examples from the different tasks, we consider both the kernel on the input space K and the output kernel Ω in our classification function.

EQUATION

We set α s = y s . The predicted label for a new example is computed from the linear combination of the labels of the examples from the support set S weighted by their input similarity K and the task similarity Ω to the new example. Using the kernel trick, one can write:

f((x t , i t )) = φ(x t ) (xs,is)∈S α s Ω isit φ(x s ) = (xs,is)∈S α s Ω isit K(x s , x t )

Note that, in the above representation, we need to learn both the support set S and the output kernel Ω from the data. As explained in the previous section, for a successful lifelong learning with kernels, we need to address two key challenges: (1) learn the relationships between the tasks (output kernel) efficiently from the data arriving in an online fashion and (2) bound the size of the support set S to avoid memory explosion. We address these two challenges in the following sections.

Algorithm 1: Online Output Kernel Learning Algorithm Initialize:

EQUATION

(or)

Ω itk ← Ω itk exp 1 λ (xs,is)∈S is=k y t K(x t , x s )y s (3) end end

2.1. ONLINE OUTPUT KERNEL LEARNING:

Our objective function for the lifelong learning problem is given as follows:

EQUATION

where (•) is some loss function such as hinge loss or logistic loss, R(•) is the regularization on the task relationship matrix Ω and λ is the regularization parameter. Note that f in the above equation depends on Ω. In order to reduce the time taken for each time-step, we require an efficient update to the task relationship matrix Ω. Following the work of Jawanpuria et al. (2015) in the batch setting, we consider a subset of regularization functions R for which we can efficiently learn the task covariance matrix. Consider the dual function of the above equation, at time-step t (see Barzilai & Crammer (2015) ; Jawanpuria et al. (2015) ):

EQUATION

When we consider the entry-wise l p norm between Ω and Ω (t-1) from the previous iteration as our regularization i.e., R(Ω,

Ω (t-1) ) = k |Ω itk -(Ω (t-1) ) itk | p for p ≥ 1 1

, we get the update function in Equation 2. Similarly, if we consider the generalized KL-divergence between Ω and Ω (t-1) i.e., R(Ω, Ω (t-1) ) = k Ω itk log

Ω i t k

(Ω (t-1) ) i t k -Ω itk + (Ω (t-1) ) itk , we get the update function in Equation 3. Unlike in the previous work, we update only the row (and the corresponding column) of the task relationship matrix Ω specific to the task i t , which significantly reduces the time taken per example.

We can see that the update equations are simple and quite intuitive. For a given new example (x t , i t ) at round t, the algorithm updates Ω itk (for some k ∈ [K]) by computing the similarity between the new example and the examples in the support set S that belongs to the task k. If the two examples have similar (different) labels and high similarity K(x t , x s ), then the Ω itk is increased to reflect the positive (negative) correlation and vice versa. A value close to 0 implies no significant relationship between the tasks. The update to the Ω itk is normalized by the regularization parameter λ for scaling.

It is worth noting that our update equations do not violate the p.s.d constraints on Ω in Equation 5.

If Ω from the previous iteration is a p.s.d matrix and the update is a p.s.d matrix (as it is computed using the Gram matrix of the example from the previous iteration), the sum and Hadamard product of two p.s.d matrices satisfy the p.s.d constraint (using the Schur Product Theorem).

Algorithm 1 outlines the key steps in our proposed method. We write f ((x t , i t )) as f it (x t ) for notational convenience. At each time-step t, the learner receives an example x t ∈ X and predicts the output label y t using ŷt = sign(f it (x t )). We update both the support set S and the output kernel Ω it• when the learner makes a mistake.

Algorithm 2: Budgeted OOKLA Initialize: S = ∅, Ω For t = 1, 2, • • • Receive new example (x t , i t ) Let f it = (xs,is)∈S y s Ω isit φ(x s ) Predict ŷt = sign(f it (x t )) Receive label y t If y t = ŷt If |S| < B S ← S ∪ (x t , i t ) Else

Find an example to remove arg max

(xr ,ir )∈S k∈[K] Ω ir k yr f k -yrΩ ir k φ(xr) φ(xr) (6) S ← S ∪ (x t , i t )\(x r , i r ) end Update Ω itk ∀k ∈ [K]

as in Algorithm 1. end end Algorithm 3: Two-Stage Budgeted Learning Initialize:

S = ∅, T k = ∅, k ∈ [K], Ω For t = 1, 2, • • • Receive new example (x t , i t ) Let f it = (xs,is)∈Ti t y s Ω isit φ(x s ) Predict ŷt = sign(f it (x t )) Receive label y t If y t = ŷt S ← S ∪ {t}\{r} / * r=∅ if |S| < B, else choose r using Equation 6 * / For k ∈ [K] T k ← T k ∪ {l}\{r} / * remove r from T k ; choose l from S -T k * / end Update Ω itk ∀k ∈ [K] as in Algorithm 1. end end

2.2. BUDGETED LEARNING:

In Algorithm 1, we can see that both the classification function f and the update equations for Ω use the support set S. When the target function changes over time, the support set S grows unboundedly. This leads to serious computational and runtime issues especially in the lifelong learning setting. The most common solution to this problem is to impose a bound on the number of examples in the support set S. There are several budget maintenance strategies proposed recently (Cavallanti et al. (2007) ; Dekel et al. (2008) ; Orabona et al. (2008) ). Unfortunately these schemes cannot be directly used in our setting due to the output kernels in our learning formulation. Cavallanti & Cesa-Bianchi (2012) proposed multitask variants of these schemes but they are impractical for the lifelong learning setting. We follow a simple support set removal schemes based on Crammer et al. (2004) . In single-task setting, when the number of examples in the support set S exceeds the limit (say B), a simple removal scheme chooses an example x r with the highest confidence from S. The confidence of an example x r is measured using y r f(x r ) after removing x r from the support set S.

EQUATION

We extend the above approach to the multitask and lifelong learning settings. Since the support set S is shared by all the tasks, we choose an example x r with high confidence to remove from each task function f k , weighted by the relationship among the tasks. The objective function to choose the example is shown in Equation 6. We show in the experiment section that this simple approach is efficient and performs significantly better than the state-of-the-art budget maintenance strategies.

Algorithm 2 shows pseudocode of the proposed budgeted learning algorithm.

2.2.1. TWO-STAGE BUDGETED LEARNING:

In lifelong learning setting, the number of tasks is typically large. The support set S may have hundreds or thousands of examples from all the tasks. Each task does not use all the examples from the support set S. For example, in movie recommendations task, recommendation for each user (task) can be characterized by just a few movies (subset of examples) in the support set S. Motivated by this observation, we propose a two-stage budgeted learning algorithm for the lifelong learning setting.

Algorithm 3 shows pseudocode of the proposed two-stage budgeted learning algorithm. In addition to the support set S, we maintain task-specific support set T k . We choose the budget for each task (say L) where L <<< B. Similar to the removal strategies for S, we remove an example from T k when |T k | > L and replace with an example from the set S -T k . The proposed two-stage approach provides better runtime complexity compared to the budgeted algorithm in Algorithm 2. Since only a subset of tasks may hold an example from S, the removal step in Equation 6requires only a subset of tasks for choosing an example. This improves the runtime per iteration significantly when the number of tasks is large. One may consider a different budget size for each task L k based on the complexity of the task.

In addition, the proposed two-stage budgeted learning algorithm provides an alternative approach to using state-of-the-art budget maintenance strategies. For example, it is easier to use the Projectron algorithm (Orabona et al. (2008) ) on T k , rather than on S. We will further explore this line of research in our future work.

3. EXPERIMENTS:

In this section, we evaluate the performance of our algorithms. All reported results are averaged over 10 random runs on permutations of the training data. Unless otherwise specified, all model parameters are chosen via 5-fold cross validation.

3.1. BENCHMARK DATASETS:

We use three benchmark datasets, commonly used for evaluating online multitask learning. Details are given below:

Newsgroups Dataset2 consists of 20 tasks generated from two subject groups: comp and talk.politics. We paired two newsgroups, one from each subject (e.g.,comp.graphics vs talk.politics.guns), for each task. In order to account for positive/negative correlation between the tasks, we randomly choose one of the newsgroups as positive (+) or negative (-) class. Each post in a newsgroup is represented by a vocabulary of approximately 60K unique features.

Spam Dataset3 We use the dataset obtained from ECML PAKDD 2006 Discovery challenge for the spam detection task. We used the task B challenge dataset, which consists of labeled training data from the inboxes of 15 users. We consider each user as a single task and the goal is to build a personalized spam filter for each user. Each task is a binary classification problem: spam (+) or non-spam (-) and each example consists of approximately 150K features representing term frequency of the word occurrences. Some spam is universal to all users (e.g. financial scams), but some messages might be useful to certain affinity groups and spam to most others. Such adaptive behavior of each user's interests and dis-interests can be modeled efficiently by utilizing the data from other users to learn per-user model parameters.

Sentiment Dataset4 We also evaluated our algorithm on product reviews from amazon. The dataset contains product reviews from 25 domains. We consider each domain as a binary classification task. Reviews with rating > 3 were labeled positive (+), those with rating < 3 were labeled negative (-), reviews with rating = 3 are discarded as the sentiments were ambiguous and hard to predict. Similar to the previous datasets, each example consists of approximately 350K features representing term frequency of the word occurrences. 

3.2. RESULTS:

To evaluate the performance of our proposed algorithm (OOKLA), we use the three datasets (Newsgroups, Spam and Sentiment) for evaluation and compare our proposed methods to 5 baselines. We implemented Perceptron and Passive-Aggressive algorithm (PA) Crammer et al. (2006) for online multitask learning. Both Perceptron and PA learn independent model for each task. These two baselines do not exploit the task-relationship or the data from other tasks during model update. Next, we implemented two online multitask learning related to our approach: FOML -initializes Ω with fixed weights Cavallanti et al. (2010) , Online Multitask Relationship Learning (OMTRL) Saha et al. (2011) -learns a task covariance matrix along with task parameters. Since OMTRL requires expensive calls to SVD routines, we update the task-relationship matrix every 10 iterations. In addition, we compare our proposed methods against the performance of Online Smooth Multitask Learning (OSMTL) which learns a probabilistic distribution over all tasks, and adaptively refines the distribution over time Murugesan et al. (2016) . We implement two versions of our proposed algorithm with different update rules for the task-relationship matrix: OOKLA-sum (Equation 2OOKLA with sum update) OOKLA-exp (Equation 3OOKLA with exponential update) as shown in Algorithm 1.

Table 1 summarizes the performance of all the above algorithms on the three datasets. In addition to the AU C scores, we report the average total number of support vectors (nSV) and the CPU time taken for learning from one instance (Time).

From the table, it is evident that both OOKLA-sum and OOKLA-exp outperform all the baselines in terms of both AU C and nSV. This is expected for the two default baselines (Perceptron and PA). The update rule for FOML is similar to ours but using fixed weights. The results justify our claim that learning the task-relationship matrix adaptively leads to improved performance. As expected, both OOKLA and OSMTL consume less or comparable CPU time than the subset of baselines which take into account learning inter-task relationships. Unlike in the OMTRL algorithm that recomputes the task covariance matrix every (10) iteration using expensive SVD routines, the task-relationship matrix in our proposed methods (and OSMTL) are updated independently for each task. We implement the OSMTL with exponential update for our experiments as it has shown to perform better than the other baselines. One of the major drawbacks of OSMTL is that it learn only the positive correlations between the tasks. The performance of OSMTL worsens when the tasks are negatively correlated. As Average rate of mistakes we can see from the table, our proposed methods outperform OSMTL significantly in the Newsgroup dataset.

Table 2 compares the proposed methods with different budget schemes and budget sizes in terms of test set AU C scores and the runtime. We use OOKLA-sum for this experiment. We set the value of B to {50, 100, 150} for all the datasets. We compare our proposed budgeted learning algorithm (Algorithm 2) with the following state-of-the-art algorithms for online budgeted learning: Table 2 shows both the test set AUC scores (first line) and time taken for learning from one instance (including the removal step). It is evident from the table, our proposed budgeted learning algorithm for online multitask learning significantly outperforms the other state-of-the-art budget schemes on most settings. Our proposed algorithm uses the relationship between the tasks efficiently to choose the next example for removal.

Finally, we evaluate the performance of the proposed two-stage budgeted scheme compared to the Algorithm 2. To study the effect of different budget sizes L, we compute the cumulative mistake rate t I{yt = ŷt} t measured at each time-step t. Figures 1 show average rate of mistakes against the number of training examples seen so far on newsgroup, spam and sentiment datasets for different values of L. We fix the value of B = 100. As we can see from the figures, even for small values of L, the average mistake rate of the two-stage budgeted learning algorithm is comparable to the model which uses all the examples from the support set S. We observe similar trend in the test set AUC scores. On average, we achieved over 16% improvement in running time compared to the budget maintenance scheme in Algorithm 2. We believe that the time consumption and the performance improvement will be even better for applications with larger numbers of tasks.

4. CONCLUSIONS:

We proposed a novel lifelong learning algorithm using output kernels. The proposed method efficiently learns both the model and the inter-task relationships at each iteration. Our update rules for learning the task relationship matrix, at each iteration, were motivated by the recent work in output kernel learning.

In order to handle the memory explosion from an unbounded support set in the lifelong learning setting, we proposed a new budget maintenance scheme that utilizes the task relationship matrix to remove the least-useful (high confidence) example from the support set. In addition, we proposed a two-stage budget learning scheme based on the intuition that each task only requires a subset of the representative examples in the support set for efficient learning. It provides a competitive and efficient approach to handle large number of tasks in many real-life applications.

The effectiveness of our algorithm is empirically verified over several benchmark datasets, outperforming several competitive baselines both in the unconstrained case and the budget-limited case, where selective forgetting was required.

Future research includes other forms of budget limits (e.g. time or reprocessing capacity), more complex inter-task relationships (e.g. hierarchical), and additional factors such as task reliability (e.g. prefer transferring from a well-trained related task, vs from a relatively data-sparse one, whose model is less reliable).

:

We set p =

in this paper.

http://qwone.com/~jason/20Newsgroups/

http://ecmlpkdd2006.org/challenge.html

http://www.cs.jhu.edu/~mdredze/datasets/sentiment

Figures and Tables:

; Pentina & Urner (2016); Pentina & Ben-David (2015); Balcan et al. (2015); Rusu et al. (2016); Hinton et al. (2015); Rebuffi et al. (2016); Ruvolo & Eaton (

Figure 1: Number of training examples vs Average rate of mistakes calculated for different values of L.

(1) Random Budgeted Perceptron (RBP) Cavallanti et al. (2007)-randomly chooses an example to remove (2) (Self-tuned) Forgetron Dekel et al. (2008)-forgets the oldest example (3) Projectron++ Orabona et al. (2008)-projects the new example on the others (4) Budgeted Online Kernel learning (Budget-OKL)removes an example using equation 7 (5) Budgeted Online Output Kernel Learning (Budget-OOKLA)removes an example using equation 6. FollowingCavallanti & Cesa-Bianchi (2012), we implement the online multitask version of RBP, Forgetron and Projectron for our experiments.

Average performance on three datasets: means and standard (test set) scores over 10 random shuffles.We choose 2000 examples (100 posts per task) for 20 Newsgroups, 1500 emails for spam (100 emails per user inbox) and 2500 reviews for sentiment (100 reviews per domain) as training set for our experiments. Note that we intentionally kept the size of the training data small to simulate the lifelong learning setting and drive the need for learning from previous tasks, which diminishes as the training sets per task become large. Since these datasets have a class-imbalance issue (with few (+) examples as compared to (-) examples), we use average Area Under the ROC Curve (AU C) as the performance measure on the test set.

Table content: <table><tr><td>Models</td><td/><td colspan="2">Newsgroups</td><td/><td>Spam</td><td/><td/><td>Sentiment</td><td/></tr><tr><td/><td>AUC</td><td>nSV</td><td>Time (s)</td><td>AUC</td><td>nSV</td><td>Time (s)</td><td>AUC</td><td>nSV</td><td>Time (s)</td></tr><tr><td>Perceptron</td><td>0.7974 (0.01)</td><td>1421.6</td><td>8.36</td><td>0.8621 (0.01)</td><td>1110.0</td><td>9.23</td><td>0.6363 (0.01)</td><td>1018.8</td><td>255.3</td></tr><tr><td>PA</td><td>0.7633 (0.02)</td><td>1926.6</td><td>9.89</td><td>0.8394 (0.01)</td><td>1482.1</td><td>11.5</td><td>0.5321 (0.01)</td><td>2500.0</td><td>357.7</td></tr><tr><td>FOML</td><td>0.7830 (0.01)</td><td>1592.0</td><td>18.46</td><td>0.8803 (0.01)</td><td>1228.2</td><td>16.0</td><td>0.6484 (0.01)</td><td>1030.0</td><td>266.0</td></tr><tr><td>OMTRL</td><td>0.7694 (0.01)</td><td>1560.4</td><td>72.36</td><td>0.8583 (0.01)</td><td>1266.3</td><td>45.4</td><td>0.5651 (0.01)</td><td>1057.6</td><td>328.2</td></tr><tr><td>OSMTL</td><td>0.7969 (0.02)</td><td>1426.2</td><td>18.18</td><td>0.8611 (0.01)</td><td>1115.1</td><td>17.3</td><td>0.6425 (0.01)</td><td>1021.8</td><td>264.3</td></tr><tr><td>OOKLA-sum</td><td>0.8512 (0.02)</td><td>884.9</td><td>15.58</td><td>0.8825 (0.01)</td><td>833.4</td><td>17.3</td><td>0.6261 (0.01)</td><td>925.0</td><td>306.6</td></tr><tr><td>OOKLA-exp</td><td>0.8382 (0.02)</td><td>886.9</td><td>15.50</td><td>0.8819 (0.01)</td><td>1062.5</td><td>19.2</td><td>0.6731 (0.01)</td><td>882.2</td><td>302.8</td></tr></table>

Evaluation of proposed methods with different budgets: means and standard AUC (test set) scores over 10 random shuffles.

Table content: <table><tr><td colspan="3">Models</td><td/><td/><td/><td/><td colspan="4">Newsgroups</td><td>Spam</td><td>Sentiment</td></tr><tr><td colspan="3">Budget (B)</td><td/><td/><td>50</td><td/><td/><td colspan="2">100</td><td/><td>150</td><td>50</td><td>100</td><td>150</td><td>50</td><td>100</td><td>150</td></tr><tr><td/><td/><td/><td/><td colspan="3">0.6272</td><td/><td colspan="3">0.6954</td><td>0.7373</td><td>0.6426</td><td>0.7197</td><td>0.7536</td><td>0.5679</td><td>0.5790</td><td>0.5889</td></tr><tr><td>RBP</td><td/><td/><td/><td colspan="3">(0.07)</td><td/><td colspan="3">(0.03)</td><td>(0.01)</td><td>(0.06)</td><td>(0.03)</td><td>(0.04)</td><td>(0.02)</td><td>(0.02)</td><td>(0.02)</td></tr><tr><td/><td/><td/><td/><td/><td colspan="2">6.5s</td><td/><td colspan="2">6.4s</td><td/><td>7.4s</td><td>14.5s</td><td>18.5s</td><td>16.3s</td><td>1772.4s</td><td>1666.9s</td><td>1860.2s</td></tr><tr><td/><td/><td/><td/><td colspan="3">0.6353</td><td/><td colspan="3">0.6860</td><td>0.7240</td><td>0.6546</td><td>0.7403</td><td>0.7339</td><td>0.5579</td><td>0.5847</td><td>0.6195</td></tr><tr><td colspan="3">Forgetron</td><td/><td colspan="3">(0.07)</td><td/><td colspan="3">(0.05)</td><td>(0.01)</td><td>(0.06)</td><td>(0.04)</td><td>(0.04)</td><td>(0.02)</td><td>(0.02)</td><td>(0.02)</td></tr><tr><td/><td/><td/><td/><td/><td colspan="2">9.1s</td><td/><td colspan="2">8.6s</td><td/><td>9.9s</td><td>20.5s</td><td>21.4s</td><td>21.9s</td><td>2219.1s</td><td>2097.0s</td><td>2272.6s</td></tr><tr><td/><td/><td/><td/><td colspan="3">0.6399</td><td/><td colspan="3">0.6984</td><td>0.6986</td><td>0.6352</td><td>0.6041</td><td>0.6402</td><td>0.5215</td><td>0.5187</td><td>0.5221</td></tr><tr><td colspan="3">Projectron</td><td/><td colspan="3">(0.03)</td><td/><td colspan="3">(0.02)</td><td>(0.02)</td><td>(0.03)</td><td>(0.05)</td><td>(0.05)</td><td>(0.01)</td><td>(0.01)</td><td>(0.02)</td></tr><tr><td/><td/><td/><td/><td colspan="3">16.7s</td><td/><td colspan="2">16.6s</td><td/><td>17.6s</td><td>24.7s</td><td>26.1s</td><td>27.9s</td><td>2712.0s</td><td>2622.5s</td><td>2804.5s</td></tr><tr><td colspan="2">Budget -OKL</td><td/><td/><td colspan="3">0.6810 (0.02) 6.3s</td><td/><td colspan="3">0.7106 (0.03) 10.2s</td><td>0.7499 (0.03) 13.4s</td><td>0.6472 (0.03) 18.8s</td><td>0.6471 (0.03) 22.6s</td><td>0.6552 (0.04) 24.7s</td><td>0.5683 (0.02) 1708.8s</td><td>0.5732 (0.01) 1674.4s</td><td>0.6153 (0.01) 1935.2s</td></tr><tr><td colspan="3">Budget -OOKLA</td><td/><td colspan="3">0.7576 (0.04) 9.9s</td><td/><td colspan="3">0.7562 (0.04) 11.7s</td><td>0.7749 (0.03) 14.1s</td><td>0.7485 (0.08) 20.1s</td><td>0.7969 (0.04) 24.3s</td><td>0.8472 (0.02) 26.9s</td><td>0.6117 (0.06) 2250.5s</td><td>0.6901 (0.01) 2073.0s</td><td>0.7000 (0.04) 2334.3.3s</td></tr><tr><td>0</td><td>200</td><td>400</td><td>600</td><td>800</td><td>1000</td><td>1200</td><td>1400</td><td>1600</td><td>1800</td><td>2000</td></tr><tr><td/><td/><td/><td colspan="5">Number of training examples</td><td/><td/><td/></tr></table>

Peer review (iclr2018):
 The paper proposes a budgeted online kernel algorithm for multi-task learning. The main contribution of the paper is an online update of the output kernel, which measures similarity between pairs of tasks. The paper also proposes a removal strategy that bounds the number of support vectors in the kernel machine. The proposed algorithm is tested on 3 data sets and compared with several baselines. Positives: - the output kernel update is well justified - experimental results are encouraging Negatives: - the methodological contribution of the paper is minimal - the proposed approach to maintain the budget is simplistic - no theoretical analysis of the proposed algorithm is provided - there are issues with the experiments: the choice of data sets is questionable (all data sets are very small so there is not need for online learning or budgeting; newsgroups is a multi-class problem, so we would want to see comparisons with some good multi-class algorithms; spam data set might be too small), it is not clear what were hyperparameters in different algorithms and how they were selected, the budgeted baselines used in the experiments are not state of the art (forgetron and random removal are known to perform poorly in practice, projectron usually works much better), it is not clear how a practitioner would decide whether to use update (2) or(3)