Efficient Multitask Feature and Relationship Learning

Han Zhao, Otilia Stretcu, Alexander J. Smola, Geoffrey J. Gordon

TL;DR

This paper introduces FETR, a novel formulation for multitask learning that efficiently learns relationships between tasks and features. It addresses an ill-posed optimization issue in prior methods and proposes an efficient algorithm that is orders of magnitude faster, achieving better generalization, especially in nonlinear settings.

What Problem Does This Paper Address?

In machine learning, we often want to train models for multiple related tasks simultaneously to improve prediction accuracy, especially when labeled data is scarce. Multitask learning (MTL) aims to achieve this by learning these tasks jointly. A key aspect of MTL is understanding and leveraging the relationships between tasks and their underlying features. Existing methods, like MTFRL, attempt to capture these relationships using covariance matrices. However, the authors identify a critical flaw in these existing formulations: they lead to an ill-posed optimization problem, making it difficult to guarantee convergence and positive definiteness of the learned covariance matrices. This often requires ad-hoc fixes that might not be theoretically sound. The paper aims to fix this by proposing a well-defined variant and an efficient optimization algorithm.

Methods

The core contribution is a new formulation called FETR (FEaTure and Relation learning). This formulation addresses the ill-posedness by introducing bounded constraints on the covariance matrices, making the optimization problem well-defined and multiconvex.

To optimize FETR, the authors propose an efficient block coordinate-wise minimization algorithm. This algorithm iteratively optimizes different blocks of variables:

  1. Optimizing the model weights (W): For this, they offer three strategies:
  2. A closed-form solution derived from a matrix equation, which is computationally expensive (O(m³d³)).
  3. A gradient descent method with a guaranteed linear convergence rate.
  4. A solution based on the Sylvester equation, which is efficient (O(m³ + d³ + nd²)) and numerically stable when tasks share instances.
  5. Optimizing the covariance matrices (Σ₁ and Σ₂): This is the most novel part. They reduce the problem of optimizing these matrices to a minimum-weight perfect matching problem on a weighted bipartite graph. This allows for an analytic, closed-form solution using combinatorial techniques, avoiding expensive iterative procedures common in prior work.

The paper also extends FETR to nonlinear settings by combining its regularization with neural networks, allowing for more expressive models.

Datasets

The paper evaluates FETR on the following datasets:

  • SARCOS: A robot inverse dynamics dataset with 7 tasks and shared inputs.
  • School Data: A dataset of student examination scores from secondary schools, with 139 tasks and non-shared inputs.

Key Insights and Ideas

  • Ill-posedness of existing MTL formulations: The paper clearly demonstrates that a common approach to learning task and feature relationships in MTL leads to an optimization problem that is not well-defined, particularly when dealing with the covariance matrices.
  • The power of graph theory for covariance learning: Reducing the problem of learning covariance matrices to a minimum-weight perfect matching problem is a clever and efficient approach, leading to analytic solutions where iterative methods were previously needed.
  • Analytic solutions for subproblems: The ability to derive closed-form or efficient analytic solutions for optimizing different parts of the model (weights and covariances) is a significant advantage, leading to substantial speedups.
  • Nonlinear extension for improved performance: Combining FETR's regularization with neural networks shows promise for achieving state-of-the-art results on complex real-world problems.

Key Results

  • Computational Efficiency: The proposed FETR optimization algorithm is orders of magnitude faster than competitors like projected gradient descent and the flip-flop algorithm. For instance, Figure 3b shows FETR converging much faster on the SARCOS dataset.
  • Improved Generalization: FETR consistently achieves lower test set NMSEs on both linear and nonlinear settings compared to existing methods.
  • Nonlinear FETR Performance: The nonlinear extension (FETR-NN) significantly outperforms linear baselines and other multitask neural network approaches on both SARCOS and School datasets.
  • Covariance Matrix Estimation: Figure 4 shows that FETR can effectively estimate feature and task covariance matrices, revealing meaningful correlations (e.g., block diagonal structure indicating negative correlations between groups of tasks).

Limitations and Future Work

  • Computational Cost of Closed-Form W Solution: While a closed-form solution for W exists, it is computationally expensive (O(m³d³)) and not practical for large dimensions. The paper suggests gradient descent or Sylvester equation solvers as more scalable alternatives.
  • Nonlinear Extension Complexity: While effective, the nonlinear extension involves training neural networks, which can be computationally intensive and require careful hyperparameter tuning.
  • Future Work: The paper suggests exploring the nonlinear extension further and applying the framework to other domains. The authors also mention that their approach has close connections to proximal methods for matrix completion and Euclidean projection under trace norm constraints, hinting at potential theoretical connections to explore.

Summary updated

Abstract

We consider a multitask learning problem, in which several predictors are learned jointly. Prior research has shown that learning the relations between tasks, and between the input features, together with the predictor, can lead to better generalization and interpretability, which proved to be useful for applications in many domains. In this paper, we consider a formulation of multitask learning that learns the relationships both between tasks and between features, represented through a task covariance and a feature covariance matrix, respectively. First, we demonstrate that existing methods proposed for this problem present an issue that may lead to ill-posed optimization. We then propose an alternative formulation, as well as an efficient algorithm to optimize it. Using ideas from optimization and graph theory, we propose an efficient coordinate-wise minimization algorithm that has a closed form solution for each block subproblem. Our experiments show that the proposed optimization method is orders of magnitude faster than its competitors. We also provide a nonlinear extension that is able to achieve better generalization than existing methods.
BibTeX
@inproceedings{zhao2019efficient,
  author = {Han Zhao and Otilia Stretcu and Alexander J. Smola and Geoffrey J. Gordon},
  title = {{Efficient Multitask Feature and Relationship Learning}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=7TOXWDAngl3},
}
Figure