Multi-Task Learning as a Bargaining Game

Aviv Navon; Aviv Shamsian; Idan Achituve; Haggai Maron; Kenji Kawaguchi; Gal Chechik; Ethan Fetaya

Source-linked AI summary

Multi-Task Learning as a Bargaining Game

Aviv Navon, Aviv Shamsian, Idan Achituve, Haggai Maron, Kenji Kawaguchi, Gal Chechik, Ethan Fetaya

arXiv:2202.01017v2Feb 2, 2022cs.LGcs.GT

TL;DR

MTL can suffer when conflicting or differently scaled task gradients make joint training underperform single-task models. The paper formulates gradient aggregation as a cooperative bargaining game and introduces Nash-MTL, whose Nash bargaining update has theoretical convergence guarantees. Across multiple benchmarks and domains, the authors report state-of-the-art results.

Problem
MTL often suffers performance degradation because task gradients can conflict or differ greatly in magnitude, while principled axiomatic gradient aggregation remains missing.
Method
Nash-MTL views gradient combination as a cooperative bargaining game and combines gradients at each step using the Nash Bargaining Solution.
Results
Nash-MTL achieves state-of-the-art results across multiple benchmarks and domains, with convergence to Pareto optimal points in convex settings and Pareto stationary points in non-convex settings.
Takeaways & Limitations
Scale-invariant bargaining provides a principled update direction intended to balance tasks without domination by a single large gradient.
Takeaways & Limitations
The analysis uses a conservative weaker assumption for non-convex convergence because the stronger assumption needed for local Pareto optimality has strong implications.

Abstract

from arXiv · show

In Multi-task learning (MTL), a joint model is trained to simultaneously make predictions for several tasks. Joint training reduces computation costs and improves data efficiency; however, since the gradients of these different tasks may conflict, training a joint model for MTL often yields lower performance than its corresponding single-task counterparts. A common method for alleviating this issue is to combine per-task gradients into a joint update direction using a particular heuristic. In this paper, we propose viewing the gradients combination step as a bargaining game, where tasks negotiate to reach an agreement on a joint direction of parameter update. Under certain assumptions, the bargaining problem has a unique solution, known as the Nash Bargaining Solution, which we propose to use as a principled approach to multi-task learning. We describe a new MTL optimization procedure, Nash-MTL, and derive theoretical guarantees for its convergence. Empirically, we show that Nash-MTL achieves state-of-the-art results on multiple MTL benchmarks in various domains.

1. Introduction

MTL improves efficiency and data use by training tasks jointly, but conflicting or differently scaled gradients can degrade performance. Nash-MTL treats gradient aggregation as bargaining and reports convergence guarantees and state-of-the-art benchmark results.

Motivation: Jointly training multiple tasks can reduce computation costs and improve data efficiency, but MTL often underperforms corresponding single-task models.The paper attributes this degradation to conflicting gradient directions and unequal gradient magnitudes.
Existing approach: Most MTL methods compute per-task gradients, aggregate them into one update direction, and then apply a single-task optimization algorithm.The paper identifies the aggregation rule as the central design point.
Proposed method: Nash-MTL models gradient combination as a cooperative bargaining game in which tasks negotiate an agreed update direction.The Nash Bargaining Solution is proportionally fair and avoids domination by a single large gradient.
Illustrative behavior: Nash-MTL is invariant to loss-scale changes and produces balanced solutions across the Pareto front in the illustrative optimization example.LS, PCGrad, and CAGrad are described as being dominated by the larger gradient, while MGDA favors the smaller-gradient task.
Contributions: Nash-MTL characterizes and efficiently approximates the bargaining solution, with convergence guarantees established for convex and non-convex settings.The paper also reports empirical evaluation across four benchmarks spanning computer vision, quantum chemistry, and reinforcement learning.

2. Background

MTL optimization is a multiple-objective problem in which solutions are evaluated across several objectives without a natural total ordering. Cooperative bargaining supplies axioms and a unique solution, while affine invariance is adopted to prevent gradient-scale domination.

2.1. Pareto Optimality: MTL optimization is a form of multiple-objective optimization where solutions are represented by vectors of task-objective values.Because these vectors lack a natural linear ordering, there may be no single clearly optimal value.
2.1. Pareto Optimality: A solution is Pareto optimal when no alternative improves at least one objective without worsening another, and Pareto-optimal solutions form the Pareto front.Selecting among Pareto-optimal solutions requires additional assumptions or preferences.
2.2. Nash Bargaining Solution: A bargaining problem defines players, utilities, possible agreements, and a disagreement point, with payoff vectors collected in a feasible set U.The paper assumes U is convex and compact and contains a payoff strictly better than the disagreement point for every player.
2.2. Nash Bargaining Solution: The Nash Bargaining Solution is the unique solution satisfying Pareto optimality, symmetry, independence of irrelevant alternatives, and affine invariance.These axioms determine the bargaining outcome under the stated assumptions.
2.2. Nash Bargaining Solution: In MTL, affine invariance makes the solution insensitive to gradient norms, effectively treating gradients as normalized rather than allowing one direction to dominate.The paper presents this assumption as useful for varying loss scales and validates it with a scale-invariant baseline.

3. Method

Nash-MTL formulates gradient aggregation as a cooperative bargaining problem and uses the Nash bargaining solution to produce a principled, dynamically weighted update direction. An efficient approximation makes the per-update optimization practical, while experiments address computational cost and runtime.

Nash bargaining formulation: Nash-MTL frames each task as a bargaining-game player and searches for an agreed update vector within a ball around zero.The agreement set is Bϵ, and the disagreement point is Δθ = 0, representing no parameter change.
Interpretation: For orthogonal gradients, Nash-MTL reduces to the scale-invariant weighting α_i = 1/||g_i||.This provides the intuitive special case in which task gradients do not interact.
Interpretation: Negative interaction between task i and other gradients increases α_i, whereas positive interaction decreases it.The weights compensate for how other task gradients hamper or aid task i.
Efficient approximation: The approximation solves convex surrogate problems and iteratively linearizes a concave term using a concave-convex procedure.The iterates converge to a critical point of the original non-convex problem, while preserving the original constraints.
Practical speedup: Updating task weights less frequently reduces Nash-MTL runtime by up to ∼×10 on QM9 and ∼×5 on MT10 while maintaining high performance.The authors report runtime approaching linear scalarization or STL with competitive results against other baselines.

4. Related Work

Prior MTL methods use heuristic gradient weighting or multi-objective optimization, while Nash-MTL applies cooperative bargaining to seek Pareto-optimal and proportionally fair solutions. The paper distinguishes its approach from a closely related equal-cosine-similarity method.

Existing MTL optimization: MTL optimization combines task gradients using aggregation rules, with prior approaches based on uncertainty, gradient norms, random weights, similarity, or MGDA.These methods address conflicting gradients and related optimization difficulties, but many are described as heuristic and potentially unstable.
Multi-objective optimization: MGDA-based methods provide an appealing multi-objective formulation because, under mild conditions, they guarantee convergence to a Pareto stationary point.Sener and Koltun cast MTL as a multi-objective problem and use Frank-Wolfe-based task weighting.
Nash-MTL: Nash-MTL uses a bargaining game to seek solutions that are Pareto optimal and proportionally fair.This distinguishes its stated objective from prior gradient-aggregation approaches.
Closest related work: The closest related method seeks a fair direction with equal cosine similarities, but the paper states it can settle for a sub-optimal solution for fairness.The authors attribute this difference to the method satisfying Nash axioms except Pareto optimality.

5. Analysis

The convergence analysis targets Pareto stationary points under smoothness, boundedness, convexity-related, and gradient-independence assumptions. The analysis also explains why the independence assumption excludes degenerate task configurations and how stronger conclusions require stronger assumptions.

Non-convex convergence: In the non-convex case, Nash-MTL is analyzed for convergence to a Pareto stationary point, where some convex combination of gradients is zero.The analysis assumes gradients remain independent away from Pareto stationarity.
Assumptions: The gradient-independence assumption is stronger than Pareto stationarity and excludes degenerate cases such as two identical tasks.It applies along the generated sequence and at partial limits unless the point is Pareto stationary.
Stronger assumption: Replacing Pareto stationarity with local Pareto optimality can yield convergence to a local Pareto-optimal point, but this stronger assumption excludes local maxima and saddle points of individual tasks.The authors therefore state the weaker Pareto-stationarity result conservatively.
Assumptions: The stated assumptions require differentiable, bounded-below losses with bounded sub-level sets, an open convex input domain, and L-smooth losses.These conditions define the analytical setting for the convergence results.
Convergence result: A subsequence of iterates converges to a Pareto stationary point, and all loss functions converge to their values at that limit.The result is stated for the sequence generated by the update rule under the analysis assumptions.

6. Experiments

Experiments across molecular property prediction, scene understanding, and reinforcement learning show that Nash-MTL performs strongly across tasks while task-weight updates can be amortized for substantial speedups.

6.1. Multi-Task Regression for QM9: Nash-MTL achieves the best performance in both MR and ∆m on QM9.Most MTL methods underperform the scale-invariant baseline, whereas IMTL-G is approximately on par with it.
6.2. Scene Understanding: Nash-MTL achieves the best MR on both NYUv2 and CityScapes, plus the best ∆m on NYUv2 and fastest time to best ∆m on CityScapes.Its performance is well balanced across tasks, unlike MGDA, which favors surface-normal prediction.
6.3. Multi-Task Reinforcement Learning: Nash-MTL achieves the best performance by a large margin on MT10 and is the only MTL method matching the per-task SAC STL baseline.The MT10 results report average success over 10 random seeds.
6.4. Scaling-up Nash-MTL: A major computational drawback of state-of-the-art MTL methods is requiring all task gradients, which entails K backward passes per optimization step.Feature-level gradients can reduce Nash-MTL performance, motivating less frequent task-weight updates instead.
6.4. Scaling-up Nash-MTL: Updating task weights less frequently preserves fairly robust performance while reducing Nash-MTL training time.On QM9, updates every 5 or 50 steps yield ×3.7 or ×9.8 speedups relative to updating every step.
6.4. Scaling-up Nash-MTL: On MT10, updating weights every 100 steps gives an approximately ×10 speedup while outperforming all other MTL baselines.This setting is only approximately ×1.1 slower than the fastest baseline.

7. Conclusion

Nash-MTL frames MTL gradient combination as a bargaining game and uses the Nash bargaining solution to select update directions. The method has convergence guarantees and achieves state-of-the-art results across diverse benchmarks.

7. Conclusion: Nash-MTL uses the Nash bargaining solution to combine task gradients into an update direction.The approach emphasizes scale invariance for settings with varying loss scales and gradient magnitudes.
7. Conclusion: Nash-MTL converges to Pareto optimal points in convex settings and Pareto stationary points in non-convex settings.These are the paper’s theoretical convergence guarantees.
7. Conclusion: Experiments show that Nash-MTL achieves state-of-the-art results across multiple benchmarks and domains.The reported domains include computer vision, quantum chemistry, and reinforcement learning.

A. Proofs

The proofs establish that Nash-MTL updates converge to Pareto-stationary points, and under convexity, the iterates converge to a Pareto-optimal solution.

The smoothness lemma bounds the loss after an update using the gradient, displacement, and smoothness constant, supporting the monotonic-loss argument.
Under the stated update rule, Nash-MTL has a subsequence converging to a Pareto-stationary point, while all task losses converge to their values there.
If the algorithm reaches a Pareto-stationary solution at a finite step, it remains fixed there; otherwise, a convergent subsequence yields the same stationarity conclusion.
The proof uses decreasing losses, compact sublevel sets, bounded inverse bargaining coefficients, and vanishing smallest singular values of the gradient Gram matrix.
With convexity, the sequence of iterates converges to the Pareto-stationary limit, which is Pareto optimal for the convex combination of losses.

B. Experimental Details

The experimental details specify datasets, architectures, training schedules, gradient-application choices, and illustrative-example settings used to evaluate the methods.

All gradient-manipulation methods operate on shared-weight gradients except IMTL-G, which uses feature-level gradients as originally proposed.
QM9: The QM9 experiment trains a graph neural network on 110K molecules, with 10K validation and 10K test molecules, for 300 epochs.
Scene Understanding: Scene-understanding experiments use MTAN over SegNet, data augmentation for compared methods, 200 epochs, and a learning-rate reduction after 100 epochs.
MT10: MT10 experiments use multitask Soft Actor-Critic, train for 2 million steps with batch size 1280, and evaluate every 10K environment steps.
Illustrative Example: The illustrative example uses five initialization points, Adam, 35K iterations, and learning rate 1e-3 after setting ℓ1 = 0.1 · ˜ℓ1 and ℓ2 = ˜ℓ2.

C. Computing Task Gradient at the Features-Level

Using feature-level gradients can accelerate Nash-MTL, but the resulting gradient inner products may poorly represent task-level relationships and substantially reduce performance.

Feature-level gradients accelerate training by approximately 6× on QM9, but Nash-MTL’s test ∆m worsens from 62.0 to 179.2.
The feature-level approximation computes gradient inner products through the representation z and shared-parameter Jacobian ∇θz.
The approximation requires ∇θz^T∇θz ≈ I, described as a strong and restrictive requirement.

D.1. Full Results for Multi-task Regression

On QM9, Nash-MTL achieves the best test ∆m and MR performance among the evaluated methods across all 11 tasks.

Nash-MTL achieves the best ∆m and MR performance on the QM9 test set, averaged over three random seeds.

D.2. Effect of the Number of CCP steps

The study tests how many CCP steps are needed to approximate Nash-MTL’s optimal task-weight solution. More iterations improve approximation accuracy, but the reported improvement does not significantly affect MTL performance.

Experimental setup: The experiment compares CCP sequences of 1, 20, and 40 steps during Nash-MTL parameter optimization on NYUv2.The procedure is evaluated by varying the number of CCP iterations at each optimization step.
Approximation quality: 91.5% of optimization steps satisfy the approximation criterion with one CCP iteration, increasing to 93.5% with 20 iterations.Increasing the CCP sequence improves approximation to the optimal α.
MTL performance: The improved approximation from longer CCP sequences produces no significant improvement in MTL performance.Test ∆m is tracked throughout training to assess the performance effect.