Efficient Multitask Feature and Relationship Learning

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

Abstract

We consider a multitask learning problem where multiple predictors are learned jointly. While learning task and feature relationships simultaneously can improve performance, existing methods often suffer from ill-posed optimization and high computational complexity. We introduce FETR (FEaTure and Relation learning), a framework that stabilizes the optimization problem through bounded constraints. We develop a block coordinate-wise minimization algorithm that leverages Sylvester equation solvers and a novel reduction of covariance optimization to bipartite graph matching. Our method is orders of magnitude faster than state-of-the-art baselines while achieving superior generalization on real-world datasets.

Introduction

Multitask Learning (MTL) aims to improve generalization by learning multiple related tasks simultaneously. A sophisticated approach involves learning task covariance (relationships between tasks) and feature covariance (relationships between input features). The state-of-the-art MTFRL framework uses a "flip-flop" algorithm for this purpose. However, in many practical scenarios, the Maximum Likelihood Estimation (MLE) for these covariance matrices is ill-posed, as they often become rank-deficient. This leads to undefined inverses and requires heuristic "fudge factors" that lack theoretical guarantees and can lead to divergence.

Methods: The FETR Framework

The proposed FETR framework stabilizes optimization by imposing bounded constraints on the covariance matrices, ensuring they remain positive definite. The optimization is solved via a block coordinate-wise minimization algorithm with two key innovations:

  1. Weight Optimization via Sylvester Equations: When features are shared across tasks, the weight update is transformed into a Sylvester equation ($AX + XB = C$). This allows the use of the Bartels-Stewart algorithm, which is significantly more efficient and numerically stable than standard gradient descent.
  2. Covariance Optimization via Bipartite Matching: A major theoretical contribution is proving that the matrix optimization problem for covariances reduces to a minimum-weight perfect matching problem on a bipartite graph. This yields a simple, closed-form solution involving Singular Value Decomposition (SVD) and a hard-thresholding step, bypassing the need for expensive iterative solvers.

FETR is also extended to deep learning (FETR-NN) by integrating it as a regularization layer after a neural network feature extractor.

Experimental Evaluation

The authors evaluated FETR against several baselines, including Single-Task Learning (STL), Multitask Feature Learning (MTFL), and the original MTFRL. Tests were conducted on synthetic data and two real-world benchmarks: the SARCOS robot arm dataset (7 tasks) and the School dataset (139 tasks).

Convergence and Computational Efficiency

The proposed coordinate minimization algorithm converges significantly faster than traditional "flip-flop" or projected gradient descent methods. By leveraging the Sylvester solver and the closed-form covariance update, FETR achieves a stable optimum in a fraction of the time required by iterative solvers. As shown in the convergence plot below, FETR reaches a lower function value much more rapidly than competing methods.

Convergence speed of FETR's coordinate minimization compared to baselines.

Predictive Performance

FETR consistently outperformed existing multitask methods across both real-world datasets. In the SARCOS dataset, the nonlinear FETR-NN variant achieved the lowest Mean Squared Error. The results in the table below demonstrate that FETR's mathematically sound constraints and efficient optimization lead to better generalization than heuristic-based methods.

Performance comparison (MSE) on SARCOS and School datasets. Lower values indicate better performance.

Conclusion

FETR provides a robust and efficient solution for multitask feature and relationship learning. By identifying the bipartite graph connection and utilizing Sylvester solvers, the authors transformed an ill-posed, slow optimization problem into one that is both mathematically sound and computationally superior. The framework successfully captures physical task relationships while maintaining high scalability and accuracy.

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, togeth...
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},
}

Loading related content...

Figure