Multi-Task Learning as a Bargaining Game

A General MTL Optimization Scheme

Compute the gradients for all tasks $g_{1},..., g_{k}$.
Combine those gradients into a joint direction, $\Delta=\mathcal{A}\left(g_{1}, \ldots, g_{K}\right)$ using an aggregation algorithm $\mathcal{A}$.
Finally, the model parameters are updated using a single-task optimization algorithm, replacing the gradients with $\Delta$.

Relevant Background On MTL

Pareto Optimality

Given objective functions $\ell_{1}, \ldots, \ell_{K}$, the performace of a solution $x$ is measured by a vector of objective values $\left(\ell_{1}(x), \ldots, \ell_{K}(x)\right)$.

Nash Bargaining Solution

In a bargaining problem, we have $K$ players, each with their own utility function $u_{i}: A \cup\{D\} \rightarrow \mathbb{R}$, which they wish to maximize.
$A$ is the set of possible agreements and $D$ is the disagreement point which the players default to if they fail to reach an agreement.
The set of possible payoffs is defined as $U=\left\{\left(u_{1}(x), \ldots, u_{K}(x)\right): x \in A\right\} \subset \mathbb{R}^{K}$ and $d=\left(u_{1}(D), \ldots, u_{K}(D)\right)$.
It is assumed that $U$ is convex, compact and that there exists a point in $U$ that strictly dominates $d$, namely there exists a $u \in U$ such that $\forall i: u_{i}>d_{i}$.

Pareto Optimality: The agreed solution must not be dominated by another option, i.e. there cannot be any other agreement that is better for at least one player and not worse for any of the players. As it is a cooperative game, it makes little sense that the players will curtail another player without any personal gains. It's natural to assume the agreed solution will not be dominated by another.
Symmetry: The solution should be invariant to permuting the order of the players.
Independence of Irrelevant Alternatives: If we enlarge the of possible payoffs to $\tilde{U} \supsetneq U$, and the solution is in the original set $U$, $u^{*} \in U$, then the agreed point when the set of possible payoffs is $U$ will stay $u^{*}$.
Invariant to Affine Transformations: If we transform each utility function $u_{i}(x)$ to $\tilde{u}_{i}(x)=c_{i}\cdot u_{i}(x)+b_{i}$ with $c_{i}>0$ then if the original agreement had utilities $\left(y_{1}, \ldots, y_{k}\right)$ the agreement after the transformation has utilities $\left(c_{1} y_{1}+b_{1}, \ldots, c_{k} y_{k}+b_{k}\right)$.

Nash-MTL: The Algorithm

Let $G$ be the $d \times K$ matrix whose columns are the gradients $g_{i}$. The solution to $\arg \max _{\Delta \theta \in B_{\epsilon}} \sum_{i} \log \left(\Delta \theta^{\top} g_{i}\right)$ is $\sum_{i} \alpha_{i} g_{i}$ where $\alpha \in \mathbb{R}_{+}^{K}$ is the solution to $G^{\top} G \alpha=1 / \alpha$ where $1 / \alpha$ is the element-wise reciprocal.

Practical Speedup

Using a subset of tasks as proposed by Conflict-Averse Gradient Descent for Multi-task Learning
Replacing the task gradients with the feature level gradients as proposed by End-to-End Multi-Task Learning with Attention.

Scene Understanding Experiment

Conclusion

In this article, we discuss Nash-MTL, a novel and principled approach for multitask learning presented in the paper Multi-Task Learning as a Bargaining Game.
The authors frame the gradient combination step in MTL as a bargaining game and use the Nash bargaining solution to find the optimal update direction.
The authors highlight the importance of the scale invariance approach for multitask learning, specifically for setups with varying loss scales and gradient magnitudes.
The authors also provide a theoretical convergence analysis for Nash-MTL, showing that it converges to Pareto optimal and Pareto stationary points in the convex and non-convex settings, respectively.
Finally, the experiments conducted by the authors show that Nash-MTL achieves state-of-the-art results on various benchmarks across multiple domains.