Efficient Multi-task Feature and Relationship Learning

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

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.

Introduction

In Multi-Task Learning (MTL), the objective is to improve the generalization performance of multiple related tasks by learning them simultaneously. A powerful approach involves modeling the relationships between tasks and input features using a matrix-variate normal distribution. However, researchers from CMU, Amazon, and Microsoft have identified a fundamental flaw in existing frameworks like MTFRL. The standard "flip-flop" optimization algorithm used in these contexts is often mathematically ill-posed because the model parameters typically represent only a single sample. This leads to numerical instability, where the objective function can diverge toward negative infinity or produce non-positive definite matrices.

The FETR Framework

To address these stability issues, the authors introduce FETR (FEaTure and Relationship learning). This framework incorporates bounded constraints on the task and feature precision matrices, ensuring the optimization problem remains well-defined.

Efficient Optimization

The core of FETR is a highly efficient block coordinate-wise minimization algorithm. The optimization is split into two primary subproblems:

  1. Weight Optimization ($W$): For scenarios with shared data, the authors utilize the Sylvester equation (via the Bartels-Stewart algorithm). This approach provides a numerically stable solution in cubic time, proving significantly faster than standard Gradient Descent.
  2. Covariance Optimization ($\Sigma_1, \Sigma_2$): The authors demonstrate a novel connection to graph theory, proving that finding optimal task/feature relationships is equivalent to solving a minimum-weight perfect matching problem on a bipartite graph. This allows for a closed-form solution involving Singular Value Decomposition (SVD) and hard-thresholding, bypassing iterative solvers.

Finally, the framework is extended to FETR-NN, which integrates these regularization benefits into deep neural network architectures to capture complex, nonlinear relationships.

Experimental Results

Convergence Speed

In synthetic and real-world benchmarks, the proposed coordinate minimization algorithm demonstrated superior efficiency. As shown in the convergence analysis, FETR reaches the optimal function value orders of magnitude faster than traditional "flip-flop" or projected gradient descent methods.

Convergence comparison showing the log function value over time for different optimization methods.

Predictive Accuracy

FETR was evaluated on the SARCOS robot dynamics dataset and the School examination dataset. The results indicate that FETR consistently outperforms baseline multitask methods such as MTFL and MTRL. Notably, the nonlinear extension, FETR-NN, achieved the lowest Mean Squared Error (MSE) across all SARCOS tasks, significantly outperforming standard single-task and multi-task neural networks.

Predictive performance (MSE) comparison across various datasets and methods.

Conclusion

FETR provides a robust and efficient solution to the stability issues inherent in joint task and feature relationship learning. By leveraging Sylvester equations and bipartite matching theory, the algorithm achieves unprecedented speed. Future work may explore further scaling the weight subproblem for high-dimensional data and deeper integration of relationship learning within neural network layers.

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 Renato Negrinho and Alexander J. Smola and Geoffrey J. Gordon},
  title = {{Efficient Multi-task Feature and Relationship Learning}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=7TOXWDAngl3},
}

Loading related content...

Figure