Heterogeneous-Neighborhood-based Multi-Task Local Learning Algorithms
All the existing multi-task local learning methods are defined on homogeneous neighborhood which consists of all data points from only one task. In this paper, different from existing methods, we propose local learning methods for multitask classification and regression problems based on heterogeneous neighborhood which is defined on data points from all tasks. Specifically, we extend the knearest-neighbor classifier by formulating the decision function for each data point as a weighted voting among the neighbors from all tasks where the weights are task-specific. By defining a regularizer to enforce the task-specific weight matrix to approach a symmetric one, a regularized objective function is proposed and an efficient coordinate descent method is developed to solve it. For regression problems, we extend the kernel regression to multi-task setting in a similar way to the classification case. Experiments on some toy data and real-world datasets demonstrate the effectiveness of our proposed methods.
The paper presents a set of novel Multi-Task 
      binary-classification and regression algorithms based on a weighted K-NN 
      prediction rule. The main idea is to make use of the labels of the nearest 
      neighbors from all the tasks, in order to predict the score for a target 
      sample (instead of using only the labels of the neighbors from the target 
      task). The prediction provided by each of the nearest neighbors is 
      weighted by a scalar which encodes the task-relationship between the task 
      of the target sample and the task of the neighbor considered. The 
      task-to-task weights are collected in a matrix and a global objective 
      function is devised to minimize the prediction error on the training set. 
      The objective function penalizes non-symmetric matrices and includes 
      constraints to force the magnitude of the task-to-task weights to be 
      smaller whenever the source and the target tasks differ. The penalties 
      used for the classification tasks include the hinge-loss and the 
      square-loss. For regression tasks the authors employ the square loss and 
      replace the K-NN classification rule with a kernel-regression rule. In 
      all the settings the optimization is performed using a (block) 
      coordinate-descent approach, where each sub-problem is solved using 
      efficient ad-hoc algorithms. For classification, the training time 
      complexity is reported to be linear in the number of tasks and log-linear 
      (linearithmic) in the number of training samples from each task, however 
      this complexity does not include the time for the K-NN search for each 
      sample. Moreover, the training complexity of the regression algorithm does 
      not seem to be provided. The algorithm is tested on two 
      classification tasks and one regression task and is compared with two 
      other classical multi-task learning approaches. The results show that the 
      proposed methods compare favorably w.r.t. the selected baselines, while 
      the proposed training procedures result in a significant speedup w.r.t. 
      the use of standard solvers (CVX). The main novelty of the 
      approach is the use of the nearest neighbors from all tasks, combined with 
      the learned task-to-task relatedness matrix. For classification tasks this 
      results in the possibility of learning positive, neutral and negative 
      correlations between tasks, which in turn result in positive, zero, or 
      negative weights assigned to each neighbor label. For regression task, the 
      weighting allows to learn a linear relationship between the different 
      tasks. A concern is about the convergence of the 
      coordinate-descent approach when used to minimize non-smooth functions 
      (e.g. hinge loss). The authors claim that the algorithm: "can converge to 
      a global optimum" since "all the subproblems are strictly convex", citing 
      the results in [1]. However, the hypothesis for local convergence in [1] 
      require the objective function to be smooth (C^2), while for global 
      convergence the solutions in the optimization procedure are required to 
      lie in a compact set. A more in-depth discussion and explanation seems 
      thus to be necessary. [1] Bezdek, James C., and Richard J. 
      Hathaway. "Convergence of alternating optimization." Neural, Parallel 
      & Scientific Computations 11.4 (2003): 351-368. The 
      experimental evaluation seems rather limited: - the classification 
      datasets considered (USPS, Letter) do not seem to match the datasets used 
      in the papers of the considered baselines - the baseline selected only 
      include multi-task methods which assumes that all the tasks are related, 
      while more recent multi-task approaches (e.g. [2] and [3]) are moving away 
      from this assumption; since the proposed method is also able to learn how 
      the tasks are related to each other, a comparison should be made with such 
      methods - while using nearest neighbors from all the tasks seem to 
      improve the performances (w.r.t using only the K-NNs of the target task), 
      it is also supposed to increase the K-NN search time; a comparison of 
      training-complexity or training-times w.r.t. the baseline methods would be 
      appreciated. The exposition is not always clear. Examples: 
      - in lines 40-42 the authors claim that "When the number of 
      labeled data is not very large, the performance of the local learning 
      methods is limited due to sparse local density". This is an important 
      point for the proposed methodology, as it is one of the motivations for 
      using the samples from all the tasks. It should thus definitely discussed 
      better, or a citation should be provided. - in lines 53-55 the authors 
      write about "low-confidence" and high-confidence estimations. However, the 
      notion of confidence of the estimations is never formalized for the 
      methods in question, so that the claims result to be quite vague - in 
      lines 61-64 the authors write: "Since multi-task learning usually 
      considers that the contribution of one task to another one equals that in 
      the reverse direction, we define a regularizer to enforce the 
      task-specific weight matrix to approach a symmetric matrix"; the 
      requirement of symmetry in the task-to-task relationships is also an 
      important point of the proposed approach and should thus be discussed more 
      thoroughly, or a citation should be provided - in lines 358-361 of the 
      experimental section two baseline algorithm (mtLMNN and MTFL) are 
      apparently introduced without any citation; while it is possible to infer 
      the related publications from the acronyms the citations should be 
      reported - the URL reported in line 377 for the Letter dataset 
      (http://multitask.cs.berkeley.edu/) does not seem to exist anymore 
      Minor comments While the classification function is local, the 
      task-to-task relationship matrix W is global and the learning of W is done 
      in a global-fashion, rather than in a local, as it figures in the title.