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:
- Optimizing the model weights (W): For this, they offer three strategies:
- A closed-form solution derived from a matrix equation, which is computationally expensive (O(m³d³)).
- A gradient descent method with a guaranteed linear convergence rate.
- A solution based on the Sylvester equation, which is efficient (O(m³ + d³ + nd²)) and numerically stable when tasks share instances.
- 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