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:
- 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.
- 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.
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.
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