Adaptive Smoothed Online Multi-Task Learning
This paper addresses the challenge of jointly learning both the per-task model parameters and the inter-task relationships in a multi-task online learning setting. The proposed algorithm features probabilistic interpretation, efficient updating rules and flexible modulation on whether learners focus on their specific task or on jointly address all tasks. The paper also proves a sub-linear regret bound as compared to the best linear predictor in hindsight. Experiments over three multitask learning benchmark datasets show advantageous performance of the proposed approach over several state-of-the-art online multi-task learning baselines.
Authors proposed a method to do Online Multi-Task Learning. In their work, they: - Choose dataset from one domain (ex: spam detection, and 2 others), and split the data into multiple tasks (ex: each "user" is a task), and learn a per-user spam detector while leveraging the global data. - Formulate a loss objective (equations 1 and 2), that makes each parameter vector "w_k" do well on its own task loss "L_k" but at the same time, do well on other task losses "L_j" even for "j != k". - They model matrix \eta with entry \eta_{kj} being the "similarity" between tasks k and j. In particular, the total loss for selecting w_k is \sum_j \eta_{kj} L_j(w_k) -- in other words, w_k should incur low loss for other tasks where \eta_{kj} is high. They propose to define \eta as: \eta  = \alpha * I_K + (1 - \alpha) P; where \alpha is a scalar in [0, 1]; I_K is KxK identity matrix; and P is a row-stochastic matrix. - They discuss alternatives where \alpha and P are fixed (for example SHAMO [1]) but they also explain their algorithm, which trains P and varies (increments) \alpha over time, where the choice of \alpha is justified in section 2.5 (Regret Bound). - They propose an "Online Formulation" where the parameters evolve smoothly over time: They evolve to minimize the loss, but also to minimize the changes of parameters from previous iteration/example. Their "smoothness" is achieved by:    * minimizing the L2 norm of delta "w", this is similar [20], though they *dont* cite this similarity (maybe it is obvious??)    * minimizing the change in P, this is novel in online learning as far as my little knowledge goes: where they suggest to minimize the KL divergence: KL(P_k^(t+1) || P_k^(t)) - They show that their model performs better than others on 3 multi-task, binary datasets. 
The paper is technically sound, with some minor flaws that are explained below. Overall, I am on the "edge" of deciding if this should be accepted or rejected as a Poster. The largest factor contributing to my "reject" thought is the incompleteness of the experiments, as explained below. Nonetheless, I will provide lots of things that confused me and can be improved:   Problem Setup: 1- L19, and in other places: you claim "online learning", yet you assume that all K tasks emit examples at the same time step, which inherently invalidates your motivation: now data from all tasks is equal in quantity. You mention on L153 that the assumption can be relaxed with "added complexity". I *think* you should mention how one can train without that assumption.  Language / math correctness: 2- You mention on L23, L156, and elsewhere, that your model only updates when it makes a mistake. This does not agree with the math you have. In particular, your hinge-loss emits updates *even* if your prediction is on the correct side of the hyper-plane but if it was within "1" (margin) away from the hyperplane.  3- You mention probability simplex and use \Delta^{K-1}. What does probability simplex mean? I tried googling it and failed to find a justifying answer. I know about the tetrahedron geometric simplex but I bit it is not it. Did you just mean a "distribution" [i.e. positive entries summing to 1]? And why set the dimensions to K-1? Is it because the diagonal entry in P is set to zero since there is an Identity matrix in equation 3 which fills the diagonal?  4- Line 139, equation (4), the notation got confusing! What is \eta_{kj}(p_k) ? I am assuming that it is the (k, j)-th entry with the given p_k. Regardless if my assumption is correct, please explain notation right after you present it the first time.  5- In equation 6, my immediate response was a shock that there is no \alpha in the update rule. I should calculate the derivative myself perhaps.  Unfair comparison:  6- For your argument on multi-task learning, You should experiment with OSMTL-ONE and OSMTL-ITL, to show that your data-sharing loss is effective. You only compare the -ONE and -ITL using the PA algorithm, which is not equivalent to OSMLT, and therefore it is not clear if your wins come from the "smooth" online updates (PA is 'aggressive') or if they come from the data sharing. You don't want to over-sell the multi-task (MT) aspect if the wins comes from the "smooth" (S). If somehow PA-ONE is equivalent to OSMLT-ONE, please make it clear in the paper.   Incompleteness: 7- The online experimental setting is not clear. In particular, do you go over the training data just once? What is the size of the test data? was it held-out during training? Please complete this information. If the datasets have Train : Test splits and you have used them, please mention so.