Conflict-Averse Gradient Descent for Multi-task learning
Authors: Bo Liu
Xingchao Liu
Xiaojie Jin
Peter Stone
qiang liu
Venue: NeurIPS 2021 Poster (2021)
Keywords: multi-task learning

Abstract: The goal of multi-task learning is to enable more efficient learning than single task learning by sharing model structures for a diverse set of tasks. A standard multi-task learning objective is to minimize the average loss across all tasks. While straightforward, using this objective often results in much worse final performance for each task than learning them independently. A major challenge in optimizing a multi-task model is the conflicting gradients, where gradients of different task objectives are not well aligned so that following the average gradient direction can be detrimental to specific tasks' performance. Previous work has proposed several heuristics to manipulate the task gradients for mitigating this problem. But most of them lack convergence guarantee and/or could converge to any Pareto-stationary point.
In this paper, we introduce Conflict-Averse Gradient descent (CAGrad) which minimizes the average loss function, while leveraging the worst local improvement of individual tasks to regularize the algorithm trajectory. CAGrad balances the objectives automatically and still provably converges to a minimum over the average loss. It includes the regular gradient descent (GD) and the multiple gradient descent algorithm (MGDA) in the multi-objective optimization (MOO) literature as special cases. On a series of challenging multi-task supervised learning and reinforcement learning tasks, CAGrad achieves improved performance over prior state-of-the-art multi-objective gradient manipulation methods.

Conflict-Averse Gradient Descent for Multi-task Learning
'oo Liu, Xingchao Liu, 'Xiaojie Jin, Peter Stone, 'Qiang Liu The University of Texas at Austin, "Sony AI, 'Bytedance Research
pstone, lqiinng@cs.. utexas. edu, xjjin0731@gmail.com com
Abstract
The goal of multi-task learning is to enable more efficient learning than single task learning by sharing model structures for diverse set of tasks. standard multi-task learning objective is to minimize the average loss across all tasks. While straightforward, using this objective often results in much worse final performance for each task than learning them independently. A major challenge in optimizing multi-task model the conflicting gradients, where gradients of different task objectives are not well aligned so that following the average gradient direction can be detrimental to specific tasks' performance. Previous work proposed several heuristics to manipulate the task gradients for mitigating this problem. But most of them lack convergence guarantee and/or could converge to any Pareto-stationary point. In this paper, we introduce Conflict-Averse Gradient descent (CAGrad) which minimizes the average loss function, while leveraging the worst local im- provement of individual tasks regularize the algorithm trajectory. CAGrad balances the objectives automatically and still provably converges to a minimum over the average loss. It includes the regular gradient descent (GD) and the multiple gradient descent algorithm (MGDA) in the multi-objective optimization (MOO) literature as special cases. On a series of challenging multi-task supervised learn- ing and reinforcement learning tasks, CAGrad achieves improved performance over prior state-of-the-art multi-objective gradient manipulation methods. Code is available at https:: / ///ggtttubbb com/ Cranial XIXXXXXXXXXXC.
Introduction
Multi-task learning (MTL) refers to learning a single model that can tackle multiple different
tasks [11 28
44
(8)
By sharing parameters across tasks, MTL methods learn more efficiently with
an overall smaller model size compared to learning with separate models [38 40 255. Moreover,
has been shown that MTL could in principle improve the quality of the learned representation and
therefore benefit individual tasks 35
43 34]. For example, an early MTL result by [2] demonstrated
that training neural network recognize doors could be improved by simultaneously training it to recognize doorknobs.
However, learning multiple tasks simultaneously can be challenging optimization problem because it involves multiple objectives (38]. The most popular MTL objective in practice the average loss over all tasks. Even when this average loss is exactly the true objective (as opposed to only caring about single task as the door/doorknob example), directly optimizing the average loss could lead to undesirable performance, e.g. the optimizer struggles to make progress the learning performance significantly deteriorates. A known cause of this phenomenon is the conflicting gradients [41]: gradicnts from different tasks 1) may have varying scales with the largest gradient dominating the update, and 2) may point in different directions so that directly optimizing the average loss can be quite detrimental to specific task's performance.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Pareto Set
Initial Point
Multi-Task Objective
Task Objective
Objective
PCGrad
CAGrad (ours)
The optimization challenges faced by gradient descent (GD) and existing gradient manipu- lation methods like the multiple gradient descent algorithm (MGDA) 6 and PCGrad [41]. MGDA, PCGrad and CAGrad are applied on top of the Adam optimizer [16]. For each methods, we repeat 3 runs of optimization from different initial points (labeled with .). Each optimization trajectory is colored from red to yellow. GD with Adam gets stuck on two of the initial points because the
Figure 1:
gradient of one task overshadows that of the other task, causing the algorithm to jump back and forth
between the walls of a steep valley without making progress along the floor of the valley. MGDA and PCGrad stop optimization as soon as they reach the Pareto set.
To address this problem, previous work either adaptively re-weights the objectives of each task based on heuristics B [5] or seeks a better update vector [0 by manipulating the task gradients. However, existing work often lacks convergence guarantees only provably converges any point on the Pareto set of the objectives. This means the final convergence point these methods may largely depend on the initial model parameters. As result, it is possible that these methods over-optimize one objective while overlooking the others (See Fig. D.
Motivated by the limitation of current methods, we introduce Conflict-Averse Gradient descent (CAGrad), which reduces the conflict among gradients and still provably converges to a minimum of the average loss. The idea of CAGrad is simple: it looks for update vector that maximizes the worst local improvement of any objective in a neighborhood CAGrad automatically balances different objectives and smoothly converges the average loss. Specifically, we show that vanilla gradient descent (GD) and the multiple gradient descent algorithm (MGDA) are special cases of CAGrad (See Sec. Sec.B.TI. We demonstrate that CAGrad can improve over prior state-of-the-an gradient manipulation methods on a series of challenging multi-task supervised, semi-supervised, and reinforcement learning problems.
the average gradient. In this way,
optimal point of
2
Background
In this section, we first introduce the problem setup of multi-task learning (MTL). Then we analyze the optimization challenge of MTL and discuss the limitation of prior gradient manipulation methods.
2.1 Multi-task Learning and its Challenge
In multi-task learning (MTL), we are given K 2 2 different tasks, each of which is associated with loss function (0) for shared set of parameters 0. The goal is to find optimal 0 T that achieves low losses across all tasks. In practice, a standard objective for MTL is minimizing the average loss over all tasks:
K Σ L.
0" arg min 8E
Lo 2 K
Unfortunately, directly optimizing ① using gradient descent may significantly compromise the optimization of individual losses in practice. A major source of this phenomenon is known as the conflicting gradients [41]
Optimization Challenge: Conflicting Gradients Denote by 9: = (O) the gradient of task i, and gu = (o) = 1 Σ 9: the averaged gradient. With learning rate a E R+ 8 < 8 agoo is the steepest descent update that appears to be the most natural update to follow when optimizing 1 However, go may conflict with individual gradients, i.e. 3 i, (gi: 9o) < O. When this conflict is large. following 9n will decrease the performance on task As observed by 41 and illustrated in Fig. [ when 0 is near steep "valley", where a specific task's gradient dominates the update, manipulating the direction and magnitude of go often leads better optimization.

---

2.2 Prior Attempts and Convergence Issues
Several methods have been proposed to manipulate the task gradients to form a new update vector and have shown improved performance on MTL. Sener et al. apply the multiple-gradient descent algorithm (MGDA) 6 for MTL,, which directly optimizes towards the Pareto set [30]. Chen et al.
dynamically re-weight each L; using pre-defined heuristic [3]. More recently, PCGrad identifies conflicting gradients as the motivation behind manipulating the gradients and projects each task gradient to the normal plane of others to reduce the conflict AT. While all these methods have shown success at improving the learning performance of MTL, they manipulate the gradient without respecting the original objective (T). Therefore, these methods could in principle converge to any point in the Pareto set (See Fig. and Sec. 3.2). We provide the detailed algorithms of MGDA and PCGrad in Appendix A. and A.2 and a visualization of the update vector by each method in Fig. 2
3 Method
We introduce our main algorithm, Conflict-Averse Gradient descent in Sec. 3.1 and then show theoretical analysis in Sec. 3.2
3.1 Conflict-Averse Gradient Descent
Assume we update 0 by O' < 0 ad, where is step size and d an update vector. We want to choose d to decrease not only the average loss Lo. but also every individual loss. To so, we consider the minimum decrease rate across the losses,
{ (L.(0- - ad) -000-aad)-1000 (L)0))
d) - max kE(K]
min (gi, d), RE[K]
(2)
where we use the first-order Taylor approximation assuming a is small. If R(0, d) < 0, it means that all losses are decreased with the update given sufficiently small a. Therefore, R(0, d) can be regarded as measurement of conflict among objectives.
With the above measurement, our algorithm finds an update vector that minimizes such conflict to mitigate the optimization challenge while still converging to an optimum of the main objective Lo To this end, we introduce Conflict-Averss Gradient descent (CAGrad), which on each optimization step determines the update d by solving the following optimization problem:
max min (gi, d) s.t. ||d - goll S c c|l9o]|,
(3)
dERm EE[R]
Here, E 1) is a pre-specified hyper-parameter that controls the convergence rate (See Sec. Sec. 3.2). The optimization problem (3) looks for the best update vector within a local ball centered at the averaged gradient go, which also minimizes the conflict in losses measured by (2) Since we focus on MTL and choose the average loss as the main objective, 9o is the average gradient. However, CAGrad also applies when go is the gradient of some other user-specified objective. We leave exploring this possibility as a future direction.
Dual Objective The optimization problem involves decision variable d that has the same dimension as the number of parameters in 6, which could be millions for a deep neural network. It is not practical to directly solve for d on every optimization step. However, the dual problem of Eq. (3). as we will derive in the following, only involves solving for a decision variable w e R which can be efficiently found using standard optimization libraries 77 Specifically, first note that min; (gi, d) = min (E: wigi; d' where w = (wi,.... wx) E R and W denotes the probability simplex, i.e. W {w: E,
1 and w; 0}. Denote Iw Σ; Wig: and
c² |gol ? The Lagrangian of the objective in Eq. 3
min de W2D
T.
All9. dl 00/22.
Since the objective for d is concave with linear constraints, by switching the min and max, we reach the dual form without changing the solution by Slater's condition:
min
max g d - A 1190 dlI² /2 + A2/2.
W deRm
3

---

Algorithm 1 Conflict-averse Gradient Descent (CAGrad) for Multi-task Learning
Input: Initial model parameter vector Bu differentiable loss functions {Li) constant c E [0, 1) and learning rate a E R* repeat
At the t-th optimization step, define go = K E (L,(0=-1) and Φ = 1.9001 Solve
K
min F(w) = In 90 + Volluul,, where Iw = K wEW
Σ
L. (0,-)).
1=1
0//2 lsull 9w)
Update 0 = 0 a go
until convergence
We end up with the following optimization problem w.r.t. w after several steps of calculus,
w" arg min 9o T v f1
wEW
where the optimal X = 119 || /01/2 and the optimal update d' 9o + 9w- /X'. The detailed derivation provided in Appendix AA.3 and the entire CAGrad algorithm is summarized in Alg. The dimension of w equals to the number of objectives K, which usually ranges from 2 to tens and is much smaller than the number of parameters in neural network. Therefore, in practice, we solve the dual objective perform the update of CAGrad.
Remark In Alg. when e = O, CAGrad recovers the typical gradient descent with d = 9o- On the other hand, when (X, then minimizing F(w) is equivalent to min I1 This coincides with the multiple gradient descent algorithm (MGDA) (6). which uses the minimum norm vector in the convex hull of the individual gradients as the update direction (see Fig. 2 second column). MGDA is a gradient-basee set, that is, it leaves all the points the Pareto specific point it will converge to). It is different from our method which targets to minimize Ly while using gradient conflict to regularize the optimization trajectory. As we will analyze in the following section, to guarantee that CAGrad converges to an optimum of Lo (0), we have to ensure 0 S c <<>
mujti-objective optimization designed to converge to an arbitrary point on the Pareto
fixed points (and hence
not control which
3.2 Convergence Analysis
In this section we first formally introduce the related Pareto concepts and then analyze CAGrad's convergence property. Particularly, in Alg. [ when e < 1, CAGrad is guaranteed to converge to a minimum point of the average loss Lo-
Pareto Concepts Unlike single task learning where any two parameter vectors 0 and 02 can be ordered in the sense that either L(O,)= < L(02) L(O,) > L(02) holds, MTL could have two parameter vectors where one performs better for task and the other performs better for task j * i. To this end, we need the notion of Pureto-optimality [13]
be a set of Definition 3.1 (Pareto optimal and stationary points). Let L(0) (L:(O): i [K]}
differentiable loss functions from R. R. For two points 0, 0' R say that 0 is Pareto
dominated by 0', denoted by L(O') < L()), if Lz(0') < [4) for all i E [K] and L(0") ) + L(0). A point 2.th is said to be Pareto-optimal if there exists no 0' E 1m such that L(0") < L()). The set of all Pareto-optimal points is called the Pareto set. A point 0 is called Pareto Pareto-stationary if we have minwew gl [0)l = 0, where (0) = - W. (., and W is the probability simplex on [K].
Similar to the case of single-objective differentiable optimization, a local Pareto optimal point must be Pareto stationary (see e.g.. (6)).
Theorem 3.2 (Convergence of CAGrad). Assume the individual loss functions Lo, Li,..., Lx are differentiable R.T and their gradients Lz,00) are all H-Lipschitz. i.e. || L, (x: V L, (y) S
H [ yll for à = 0, 0,1,..., "y..,KK K where O < H S co. Assume Li = inf Lo (0) > -00
With fixed step size satisfying 0 < S I/H, we have for the CAGrad in Alg. 7

---

92
92
92
92
91
91
91
91
GD
MGDA
PCGrad
CAGrad (ours)
max min 9,
d - (0 + 2211)/2
max min 9. d
d (9) 92)/2
4
9: g
||]]| 1
gEls 9:
|1
95
goll s |lool
The combined update vector d (in red) of two-task learning problem with gradient descent (GD), multiple gradient descent algorithm (MGDA), PCGrad and Conffict-Averse Gradient descent (CAGrad). The two task-specific gradients are labeled 91 and g2. MGDA's objective is given its primal form (See Appendix [A.1). For PCGrad, each gradient is first projected onto the normal plane of the other (the dashed arrows). Then the final update vector is the average of the two projected gradients. CAGrad finds the best update vector within a ball around the average gradient that maximizes the worse local improvement between task and task 2.
Figure 2:
1) For any 2 1, all the fixed points of CAGrad are Pareto-stationary points of (Lo, Li, LK). 2) In particular, if we take S then CAGrad satisfies
T
2(Lo((o) Lt)
[Lo
a(1 c2)
This means that the algorithm converges to stationary point of V Lo if we take 0 < < 1. The proof in Appendix A..] we discuss earlier, unlike our method, MGDA is designed to converge to an arbitrary point on the Pareto set, without explicit control of which point it will converges to. Another algorithm that mitigates the confficting gradients problem by removing the conflicting components of each gradient with respect to the other gradients before averaging them to form the final update; see Fig. 2 third column for the illustration. Similar to MGDA, shown in [I], PCGrad also converges to arbitrary Pareto point without explicit control of which point will arrive at.
algorithm with similar property is PCGrad 41), which is a gradient-basee
3.3 Practical Speedup
A typical drawback of methods that manipulate gradients is the computation overhead. For computing the optimal update vector, a method usually requires back-pru prokpapopagtinnns to find individual gradients 9s. in addition to the time required for optimization. This can be prohibitive for the scenario with many tasks. To this end, we propose only sample a subset of tasks S [K] compute their corresponding gradients {g. i S} and the averaged gradient go. Then optimize d in:
( Kg Eies Di
max min dERM
K [S] d),
min (g. d)
s.t. ||d - goll I cclgol
EES
Remark Note that the convergence guarantee in Thm. 3.2 still holds for Eq. 4 as the constraint does not change (See Appendix(A.3. [A.3). The time complexity O([SS) + T)), where denotes the time for one pass of back-propagation and T denotes the optimization time. For few-task learning (K 10), usually T & N. When [K], we recover the full CAGrad algorithm.
4 Related Work
Multi-task Learning Due to its benefit with regards to data and computational efficiency, multi-task
learning (MTL) has broad applications vision, language, and robotics [11] 22
44
38 A number
of MTL-friendly architectures have been proposed using task modules 25 [1] attention
based mechanisms 21 or activating different paths along the deep networks to tackle MTL
Apart from designing new architectures, another branch of methods focus on decomposing large problem into smaller local problems that could be quickly learned by smaller models [29
Then unified policy is learned from the smaller models using knowledge distillation 12
5

---

MTL Optimization In this work, we focus on the optimization challenge of MTL [8]. Gradient manipulation methods are designed specifically balance the learning of each task. The simplest form of gradient manipulation is to re- weight the task losses based on specific criteria, e.g., uncertainty [15.
gradient norm [3], or difficulty [9] These methods are mostly heuristics and their performance can
be unstable. Recently, two methods [30] 41] that manipulate the gradients to find better local update vector have become popular. Sener et al [30] view MTL as a multi-objective optimization problem, and use multiple gradient descent algorithm for optimization. PCGrad [4]] identifies major optimization challenge for MTL, the conflicting gradients, and proposes to project each task gradient to the normal plane of other task gradients before combining them together to form the final update vector. Though yielding good empirical performance, both methods can only guarantee convergence to Pareto- stacto--tatioaryyy point, but not knowing where it exactly converges to. More recently, GradDrop [4] randomly drops out task gradients based on how much they conflict. IMTI.- G (0 seeks update vector that has equal projections on each task gradient. RotoGrad [14] separately scales and rotates task gradients to mitigate optimization conflict.
Our method, CAGrad, also manipulates the gradient to find better optimization trajectory. Like other MTL optimization techniques, CAGrad model-agnostic. However, unlike prior methods, CAGrad converges to the optimal point in theory and achieves better empirical performance on both toy multi-objective optimization tasks and real-world applications.
Experiment
We conduct experiments to answer the following questions:
Question (1) Do CAGrad, MGDA and PCGrad behave consistently with their theoretical properties in practice? (yes)
Question (2) Does CAGrad recover GD and MGDA when varying the constant c? (yes)
Question (3) How does CAGrad perform in both performance and computational efficiency compared to prior ofte-of-theear methods, on challenging multi-task learning problems under the supervised, semi-supervised and reinforcement learning settings? (CAGrad improves over prior ofte--of-the-art methods under all settings)
5.1 Convergence and Ablation over
To answer questions (1) and (2), we create toy optimization example evaluate the convergence of CAGrad compared to MGDA and PCGrad. On the same toy example, we ablate over the constant e and show that CAGrad recovers GD and MGDA with proper e values. Next, to test CAGrad on more complicated neural models, we perform the same set of experiments on the Multi-FashiontMNNII benchmark [99 with a shrinked LeNet architecture [88 (in which each layer has a reduced number of neurons compared to the original LeNet). Please refer to Appendix B for more details.
For the toy optimization example, we modify the toy example used by Yu al. 0 = (01, 02) E 2² with the following individual loss functions:
41 and consider
L1 (0) ci (0) + (0) and (2 ci (0) (2)g22(0), where
f() log ( [max( (o.x((0.5(66))) - 7) tanh (-12)]. 0.000005)) 6,
f2(0) = log ( (maax(00.5( + 3) - tanh (-02) 2), 0.000005)) + 6,
91 (0) = ((-0) 77" +011 7 (-02 - -0))2)))//111 -))))/10 20,
0.1 (2( = + (-0, -8)²) 10 - 20,
c1 (0) max(tanh (0.5 02), 0) and c2( max(tanh (-0.5 * 0z), 0).
The average loss Lg and individual losses L, and L2 are shown in Fig. We then pick 5 initial parameter vectors 6mm E {(-8.5, 7.5). (-8.5, 5). (0. 0). (9. 9). (10, -8) and plot the corresponding optimization trajectories with different methods in Fig. 3 As shown in Fig. GD gets stuck in 2 out of the 5 runs while other methods all converge to the Pareto set. MGDA and PCGrad converge to different stationst points depending on Omi-- CAGrad with c recovers GD and CAGrad with 10 approximates MGDA well (in theory it requires co to exactly recover MGDA).

---

Pareto Set
Initial Point 1ig
GD
MCDW
PiGGrdd
CiGred
CAGred
CAGreed
1/
-3
-00
-3
-30
L1
0.5
c (0.10)
< 00.200350.8)
Figure 3: The left four plots are 5 runs of each algorithms from 5 different initial parameter vectors, where trajectories colored from red yellow. The right two plots are CAGrad's d's results with varying E {0, 0.2, 0.5, 0.8, 10).
Next, we apply the same set of experiments on the multi-task classification benchmark Multi- MasSion+MNIST [9]. This benchmark consists images that are generated by overlaying an image from FashionMNIST dataset [39] on top of another image from MNIST dataset [5]. The two images are positioned on the top-left and bottom-righ right separately. We consider shrinked LeNet as our model, and train it with Adam [16] optimizer with a 0.001 learning rate for 50 epochs using batch size of 256. Due to the highly non-convex nature of the neural network, we are not able visualize the entire Pareto set. But we provide the final training losses of different methods over three independent runs in Fig. 4 As shown, CAGrad achieves the lowest average loss with c = 0.2. In addition, PCGrad and MGDA focus optimizing task I and task 2 separately. Lastly, CAGrad with 0 and c 10 roughly recovers the final performance of GD and MGDA. By increasing c, the model performance shifts from more GD-like to more MGDA-like, though due to the non-convex nature of neural networks, CAGrad with S c < 1 does not necessarily converge to the exact same point.
Training Loss
0.65
0.60
Avg. Loss
-
Task 1 Loss
0.50
Task 2 Loss
GD
MGDA
PCGrad
CAGrad (e=00 0)
CAGrad (e= 0.2)
CAGrad (o= 0.5)
CAGrad (c= 0.8)
CAGrad (c = 10)
Figure 4: The average and individual training losses on the Fashion-and-MMNIST benchmark by running GD, MGDA, PCGrad and CAGrad with different e values. GD gets stuck at the steep valley (the area with a cloud of dots), which other methods can pass. MGDA and PCGrad converge randomly on the Pareto set.
5.2 Multi-task Supervised Learning
To answer question (3) in the supervised learning setting, follow the experiment setup from Yu et al. [41] and consider the NYU-v2 and CityScapes vision datasets. NYU-v2 contains tasks: 13-
class semantic segmentation, depth estimation, and surface normal prediction. CityScapes similarly
contains 2 tasks: 7-class semantic segmentation and depth estimation. Here, we follow [41] and
combine CAGrad with state-of-the-an MTT. method MTAN 21). which applies attention mechanism on top of the SegNet architecture [I]. We compare CAGrad with PCGrad, vanilla MTAN and Cross- Stitch (25). which another MTL method that modifies the network architecture. MTAN originally experiments with equal loss weighting and two other dynamic loss weighting heuristics 15 B. For a fair comparison, all methods are applied under the equal weighting scheme and we use the same training setup from [3]. We search e E {0.1, 0.2. 0.9} with the best average training loss for CAGrad on both datasets (0.4 4 for NYU-v2 and 0.2 for Cityscapes). We perform a two-tailed, Student's I-test under equal sample sizes, unequal variance setup and mark the results that are significant with an *. Following Maninis et 24), we also compute the average per-task performance drop of method m with respect to the
E (-1)" (-1)"((,,. - M,.;)/ / MM, where baseline Am = k
1
1, = 1 if higher value is better for criterion M, on task and 0 otherwise. The single-tasking baseline (independent) refers to training individual tasks with a vanilla SegNet. Results are shown in Tab. and Tab.
Given the single task performance, CAGrad performs better on the task that is overlooked by other methods (Surface Normal in NYU-v2 and Depth in CityScapes) and matches other methods'
7

---

Segmentation
Depth
Surface Normal
Angle Distance
Within (Higher Better)
#P.
Method
(Higher Better)
(Lower Better)
(Lower Better)
Am%
mloU
Pix Ace
Abs Err
Rel Em
Mcan
Median
11.25
22.5
30
3
Independent
38.30
63,76
0.6754
0.2780
25.01
19.21
30.14
57.20
69.15
7:3
C
37.42
63.51
0.5487
0.2188
*28.85
*24.52
*22.75
*46.58
559.56
6.96
1.77
MTAN
21
39.29
65.33
0.5493
0.2263
*28.15
*23.96
*22.09
*47.50
*61.08
5.59
1.77
MGDA
30
330.47
55990
*006070
*0,2555
24.88
19.45
29.18
56.88
69.36
1.38
1.77
PCGrad
38.06
64.64
0.5550
0.2325
*27.41
+22.80
*23.86
*49.83
"63.14
3.97
1.77
GradDrop
39.39
65.12
0.5455
0.2279
*27.48
+22.96
*23.38
+49.44
*62.87
3.58
1.77
CAGrad (ours)
39.79
65,49
0,5486
0.2250
26.31
21.58
25.61
52.36
65.58
0.20
Table Multi-task learning results on NYU-v2 dataset. #P denotes the relative model size compared to the vanilla SegNet. Each experiment is repeated over 3 random seeds and the mean is reported. The best average result among all multi-task methods is marked in bold. MGDA, PCGrad, GradDrop and CAGrad are applied on the MTAN backbone. CAGrad has statistically significant improvement over baselines methods with an *, tested with p-value of 0.I.
Segmentation
Depth
#P.
Method
(Higher Better)
(Lower Better)
Am% J
mloU
Pix Ace
Abs Err
Rel Err
2
Independent
74.01
93.16
0.0125
27.77
Rd3
Cross-Stitch
*73.08
*92.79
*0.0165
1118.5
90.02
1.77
MTAN 21
75.18
93.49
*0.0155
446.77
22.60
1.77
MGDA 30
168.84
191554
0.0309
33,50
44.14
1.77
PCGrad 41
75.13
93.48
0.0154
42.07
18.29
1.77
GradDrop 4
75.27
93.53
*0.0157
*47.54
23.73
1.77
CAGrad (ours)
75.16
93.48
0.0141
37.60
11.64
Table 2: Multi-task learning results on CityScapes Challenge. Each experiment is repeated over random seeds and the mean is reported. The best average result among all multi-task methods is marked in bold. PCGrad and CAGrad are applied on the MTAN backbone. CAGrad has statistically significant improvement over baselines methods with an *, tested with p-value of 0.1.
performance on the rest of the tasks. We also provide the final test losses and the per-epoch training time of each method in Fig. in Appendix B.2
5.3 Multi-task Reinforcement Learning
To answer question (3) in the reinforcement learning (RL) setting, we apply CAGrad on the MT10 and
MT50 benchmarks from the Meta-World environment [42) In particular, MT10 and MT50 contains 10 and 50 robot manipulation tasks. Following [33], we use Soft Actor-Critic (SAC) [IO] as the underlying RL training algorithm. We compare against Multi-task SAC (SAC with shared model), Muade- SAC (SAC with a shared backbone and task-specific head), Multi-task SAC Task Encoder (SAC with shared model and the input includes task embedding) We also compare with Soft Modularization [40] that routes different modules in a shared model to form different policies. Lastly, we also include recent method (CARE) that considers language metadata and uses a mixture of expert encoder for MTL. We follow the same experiment setup from (33] The results are shown in Tab. 3 CAGrad outperforms all baselines except for CARE which benefits from extra information from the metadata. We also apply the practical speedup in Sec. Sec.3.3 33. sub-sample and tasks for MT10 and MT50 (CAGrad-Fastt, CAGrad-fast achieves comparable performance against the statc-of-the-art method while achieving 2x (MT10) and 5x (MT50) speedup over PCGrad. We provide a visualization of tasks from MT10 and MT50, and the comparison of computational efficiency in Appendix B.3
42 and PCGrad [1].
5.4 Semi-supervised Learning with Auxiliary Tasks
Training with auxiliary tasks to improve the performance of a main task is another popular application of MTL. Here, we take semi-supervised learning an instance. We combine different optimization
8

---

Metaworld MT10
Metaworld MT50
Method
success
success
(mean + stderr)
(mean + stderr)
Multi-task SAC
42
0.49 +0.073
0.36 +0.013
Multi-task SAC Task Encoder 42
0.54 =0.047
0.40 10.024
Multi-hcaded SAC [42
0.61 +0.036
0,45 #0.064
PCGrad 41
0.72 +0.022
0.50 #0.017
Soft Modularization
0.73 00.04
0.50 10.035
CAGrad (ours)
0.83 +0.045
0.52 +0.023
CAGrad-Fast (ours)
0.82 +0.039
0.50 +0.016
CARE 33
0.84 +0.051
0.54 #0.031
One SAC agent per task (upper bound)
0.90 +0.032
0.74 #0.041
Table 3: Multi-task reinforcement learning results on the Metaworld benchmarks. Results averaged over 10 independent runs and the best result is marked in bold.
algorithms with Auxiliary Task Reweighting for Minimum-data Learning (ARML) 31 state-of- are-art semi-supervised learning algorithm. The loss function is composed of the main task and two auxiliary tasks:
Lo (0: Di) + wi I. (0: Dw.) + u22 T.2 yuu (0; Da):
(5)
where LeE is the main cross-entropy classification loss on the labeled dataset Dr, and aus: Laux are auxiliary unsupervised learning losses the unlabeled dataset D... We use the same and from ARML, and use the CIFARIO dataset [17]. which contains 50,000 training images and 10,000 test images. 10% of the training images is held out the validation set. We test PCGrad, MGDA and CAGrad with 500, 1000 and 2000 labeled images. The rest of the training set is used for auxiliary tasks. For all the methods, we use the same labeled dataset, the same learning rate and train them for 200 epochs with the Adam [6 optimizer. Please refer to Appendix f.4 for more experimental details. Results shown in Tab. 4 With all the different number of labels, CAGrad yields the best averaged test accuracy. We observed that MGDA performs much worse than the ARML baseline, because it significantly overlooks the main classification task. We also compare different gradient manipulation methods on the same task with GradNorm 33 which dynamically adjusts wi and W2 during training. The results and conclusions are similar those for ARMI.
Method
500 labels
1000 labels
2000 labels
ARML 31
67.05 10.16
73.22 10.26
81.35
10.36
ARML + PCGrad 41
67.49 10.64
73.23 10.62
81.91 10.19
ARML MGDA 30
49.27 10.68
60.11 12.35
60.78
10.17
ARMI. CAGrad (Ours)
68.25 +0.37
74.37 +0.42
82.81 +0.48
GradNorm 3
67.35 10.15
73.53
10.23
81.03
+0.71
GradNorm + PCGrad 41
67.83 +0.19
73.91
+0.09
82.72
+0.19
GradNorm + MGDA 30
36.99
+2.11
57.94
40.92
59.12 +0.63
GradNorm + CAGrad (Ours)
67.53
+0.26
74.72 +0.19
83.15 +0.56
Table 4: Semi-supervised Learning with auxiliary tasks on CIFAR10. We report the average test accuracy over 3 independent runs for each method and mark the best result in bold.
Conclusion
In this work, we introduce the Conflict-Averse Gradient descent (CAGrad) algorithm that explicitly optimizes the minimum decrease rate of any specific task's 's loss while still provably converging to the optimum of the average loss. CAGrad generalizes the gradient descent and multiple gradient descent algorithm, and demonstrates improved performance across several challenging multi-task learning problems compared to the state-of-the-an methods. While we focus mainly on optimizing the average loss, an interesting future direction look main objectives other than the average loss under the multi-task setting.

---

Acknowledgements
The research was conducted in the statistical learning and AI group (SLAI) and the Learning Agents Research Group (LARG) in computer science at UT Austin. SLAI research is supported in part by GAREER-1846211 SenSEE-037267, EAGER-204 204 2041127, 1327, and Office of Navy Research, and NSF AI Institute for Foundations of Machine Learning (IFML). LARG research is supported in part by NSF (CPS-1739964, IIS- 1724157, FAIN-2019844), ONR 1700014-18-2244 DARPA, Lockheed Martin, GM, Bosch, and UT Austin's Good Systems grand challenge. Peter Stone serves as the Executive Director of Sony AI America and receives financial compensation for this work. The terms of this arrangement have been reviewed and approved by the University of Texas at Austin in accordance with its policy on objectivity in research. Xingchao Liu is supported in part by funding from BP.
ARO (W91 INF-192-0333,
References
[1] Vijay Badrinarayanan, Alex Kendall, and Roberto Cipolla. Segnet: A deep convolutional encoder-decoder architecture for image segmentation. IEEE transactions on pattern analysis and machine intelligence, 39(12)244812249 2017.
[2] Rich Caruana. Multitask learning. Machine learning, 28(1):41-75, 1997.
[3] Zhao Chen, Vijay Badrinarayanan, Chen-Yu Lee, and Andrew Rabinovich. Gradnorm: Gra- dient normalization for adaptive loss balancing in deep multitask networks. In International Conference on Machine Learning, pages 794-803, PMLR, 2018.
[4] Zhao Chen, Jiquan Ngiam, Yanping Huang, Thang Luong. Henrik Kretzschmar, Yuning Chai, and Dragomir Anguelov. Just pick a sign: Optimizing deep multitask models with gradient sign dropout. arXiv preprini 20Xiv:2010006808. 2020.
[5] Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 1411144 2012.
[6] Jean-Antoine Désidéri. Multiple-gradient descent algorithm (mgda) for multiobjective opti- mization. Comptes Rendus 35 2012.
[7] Steven Diamond and Stephen Boyd. CVXPY: A Python-embeddded modeling language for convex optimization. Journal of Machine Learning Research, 17(83)11-5, 2016.
[8] Dibya Ghosh, Avi Singh, Aravind Rajeswaran, Vikash Kumar, and Sergey Levine. Divide-and- conquer reinforcement learning. arXiv preprint arXiv: 10.iv:/7711.99000 1.09874, 2017.
[9] Michelle Guo, Albert Haque, De-An Huang, Serena Yeung. and Li Fei-Fei. Dynamic task prioritization for multitask learning. In Proceedings of the European Conference on Computer Vision (ECCV), pages 270-287, 2018.
[10] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with a stochastic actor. In International Conference Machine Learning, pages 1861-1870. PMLR, 2018.
[11] Kazuma Hashimoto, Caiming Xiong, Yoshimasa Tsuruoka, and Richard Socher. A joint many- task model: Growing a neural network for multiple nip tasks. arXiv preprint 1..157761..01587 2016.
[12] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in a neural network. arXiv preprint 10X3::5003.02 2015.
[13] Harold M Hochman and James D Rodgers. Pareto optimal redistribution. The American economic review, 59(4))542-555 1969.
[14] Adrián Javaloy and Isabel Valera. Rotograd: Dynamic gradient homogenization for multi-task learning. arXiv preprint arXiv:2103.02631 2021.
[15] Alex Kendall, Yarin Gal, and Roberto Cipolla. Multi-task learning using uncertainty to weigh losses for scene geometry and semantics. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 7482-7491, 2018
[16] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.69800 2014.
10

---

[17] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[18] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 1):2278-2324, 1998.
[19] Xi Lin, Hui-Ling Zhen, Zhenhua Li, Qingfu Zhang, and Sam Kwong. Pareto multi-task learning. arXiv preprint arXiv: /9. /2544, 2019.
[20] Liyang Liu, Yi Li, Zhanghui Kuang, Jing-Hao Xue, Yimin Chen, Wenming Yang, Qingmin Liao, and Wayne Zhang. Towards impartial multi-task learning. In International Conference on Learning Representations, 2020.
[21] Shikun Liu, Edward Johns, and Andrew Davison. End-to-end multi-task learning with attention. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 1871-1880, 2019.
[22] Xingchao Liu, Xing Han, Na Zhang, and Qiang Liu. Certified monotonic neural networks. arXiv preprint arXiv:2011. 10221, 2020.
[23] Debabrata Mahapatra and Vaibhav Rajan. Multi-task learning with user preferences: Gradient descent with controlled ascent in pareto optimization. In International Conference on Machine Learning, pages 6597-6607. PMLR, 2020.
[24] Kevis-Kokitsi Maninis, Ilija Radosavovic, and lasonas Kokkinos. Attentive single-tasking of multiple tasks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1851-1860, 2019.
[25] Ishan Misra, Abhinav Shrivastava, Abhinav Gupta, and Martial Hebert. Cross-stitch networks for multi-task learning. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3994 4003, 2016.
[26] Emilio Parisotto, Jimmy Lei Ba, and Ruslan Salakhutdinov. Actor-mimic: Deep multitask and transfer reinforcement learning. arXiv preprint 1 2015.
[27] Clemens Rosenbaum, Tim Klinger, and Matthew Riemer. Routing networks: Adaptive selection of non-linear functions for multi-task learning. arXiv preprint arXiv:1711.0123: 2017.
[28] Sebastian Ruder. An overview of multi-task learning in deep neural networks. arXiv preprint arXiv:7706.05098, 2017.
[29] Andrei A Rusu, Sergio Gomez Colmenarejo, Caglar Gulcehre, Guillaume Desjardins, James Kirkpatrick, Razvan Pascanu, Volodymyr Mnih, Koray Kavukcuoglu, and Raia Hadsell. Policy distillation. arXiv preprint arXiv: 15110066,,, 2015.
[30] Ozan Sener and Vladlen Koltun. Multi-task learning multi- optimization. arXiv preprint arXiv:1810.0465 040500, 2018
[31] Baifeng Shi, Judy Hoffman, Kate Saenko, Trevor Darrell, and Huijuan Xu. Auxiliary task reweighting for minimum-data learning. Advances in Neural Information Processing Systems, 33, 2020.
[32] Shagun Sodhani and Amy Zhang. Mtrl - multi task rl algorithms. Github, 2021.
[33] Shagun Sodhani, Amy Zhang, and Joelle Pineau. Multi-task reinforcement learning with context-based representations. arXiv preprint arXiv:2102.06117, 02.1077.767 2021.
[34] Charles Stein. Inadmissibility of the usual estimator for the mean of multivariate normal distribution. In Contribution to the Theory of Statistics, pages 197-206. University of California Press, 2020.
[35] Kevin Swersky, Jasper Snoek, and Ryan Prescott Adams. Multi-task bayesian optimization. 2013.
[36] Antti Tarvainen and Harri Valpola. Mean teachers are better role models: Weight-averaan consistency targets improve semi-supervised deep learning results. In Proceedings of the 31t International Conference on Neurul Information Processing Systems, pages 1195-1204, 2017.
[37] Yee Whye Teh, Victor Bapst, Wojeiech Marian Czamecki, John Quan, James Kirkpatrick, Raia Hadsell, Nicolas Heess, and Razvan Pascanu. Distral: Robust multitask reinforcement learning. 2017.
arXiv preprint
11

---

[38] Simon Vandenhende, Stamatios Georgoulis, Wouter Van Gansbeke, Mare Proesmans, Dengxin Dai, and Lue Van Gool. Multi-task learning for dense prediction tasks: survey, IEEE Transactions on Puttern Analysis and Machine Intelligence, 2021.
[39] Han Xiao. Kashif Rasul, and Roland Vollgraf. Fashion-mnis
novel image dataset for henchmarking machine learning algorithms. arXiv preprint arXiv: 170.:007787777 2017.
[40] Ruihan Yang. Huazhe Xu, Yi Wu, and Xiaolong Wang. Multi-task reinforcement learning with soft modularization. arXiv preprint arXiv:2003. 13661, 2020.
[41] Tianhe Yu, Saurabh Kumar, Abhishek Gupta, Sergey Levine, Karol Hausman, and Chelsea Finn. Gradient surgery for multi-task learning. arXiv preprint arXiv:2001.000 067822, 2020.
[42] Tianhe Yu, Deirdre Quillen, Zhanpeng He, Ryan Julian, Karol Hausman, Chelsea Finn, and Sergey Levine. Meta-world: A benchmark and evaluation for multi-task and meta reinforcement learning. In Conference on Robot Learning, pages 1094-1100. PMLR, 2020.
[43] Amir Zamir, Alexander Sax, William Shen, Leonidas J Guibas, Jitendra Malik, and Silvio Savarese. Taskonomy: Disentangling task transfer learning. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3712-3722, 2018.
[44] Yu Zhang and Qiang Yang. A survey on multi-task learning. JEEE Transactions on Knowledge and Data Engineering, 2021.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Sec. 3.2 for the convergence analysis, Fig. for the challenges faced by previous methods, and Sec. 5 for empirical evaluation of these challenges and the advantage of CAGrad.
(b) Did you describe the limitations of your work? [Yes] See Sec. 6 Currently we mainly focus optimizing the average loss, which could be replaced by other main objectives.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our method does not have potential negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes] The assump- tions are stated in Thm. 3.2
(b) Did you include complete proofs of all theoretical results? [Yes] The complete proof is included in Appendix A.3.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] We mention most of the details to reproduce the result in Sec. 5 provide the rest of details of each experiment in Appendix.B. The code comes with the supplementary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix. and Sec. 5
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes] For each experiment except for the toy (since there is no stochasticity), we run over multiple (2 3) seeds.
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] We explicitly compare the computational efficiency in Fig. More details on the resources are provided in the corresponding sections in Appendix.B.
4. If you using existing assets (c.g., code, data, models) or curating/releasnng assets...
12

---

(a) If your work uses existing assets, did you cite the creators? [Yes] For most of the experiment, we follow the exact experiment setup and use the corresponding open- source code from previous works and have cited and compared against them.
(b) Did you mention the license of the assets? [Yes] All code and data publicly available under MIT license
(c) Did you include any new assets either in the supplemental material or as a URL? [No] No new assets introduced for our experiment. The only thing we modified is shrinked LeNet, where the details are provided in Appendix.B.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] The data we use are publicly available data that has been used by a lot of prior research. There should be no personally identifiable information offensive content.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A] No human subjects involved.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "uTZzj5U2Q-A", "reviewer": "Reviewer_Z94j", "summary": "Authors propose a multitask learning approach to reduce gradient conflict by minimizing harm to the worst-performing task given any gradient update. Proofs are provided for convergence and pareto optimality of the resultant weight configuration. Experiments are run on a variety of settings, including computer vision and multitask reinforcement learning, with good results throughout.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I enjoyed reading this paper and find the analysis to be exciting. The results themselves are rather marginal/middling, but given that these are complicated models and multitask learning is known to be quite a messy, high-variance problem setting, I'm happy to be a bit lenient on that. I am glad to see the mathematical analysis and general intuition behind the method, although I have some concerns regarding various elements (including motivation, robustness, and compute overhead). As a lot of this is more clarifications on the method and presumably addressable within the author response, I think the ideas within the paper could be worthwhile to publish at NeurIPS. \n\n(1) My biggest issue with the idea is that I suspect converging to an optimum of the average loss is not necessarily a desideratum. Indeed, given that there is so much literature around balancing loss function weights (MGDA, Uncertainty Weighting, GradNorm, etc.), I suspect that CAGrad is quite brittle when loss function magnitudes are off-balance. MGDA may not converge to the average loss minimum, but that's a feature not a bug, as MGDA is premised on the idea that relative loss magnitudes need to be retuned. For instance, one could arbitrarily increase weight to one loss function until the network is dominated by that task, and in that case it seems that finding a stationary point of the average loss will be a bad idea. So why should we actually want to fit to the average of arbitrarily weighted loss functions?\n\n(2) Have authors tried some of the loss balance methods (listed previously in (1)) in tandem with CAGrad? At the very least it would be nice to benchmark CAGrad against those balancing methods, which I noticed the authors did not do across their different benchmarks. \n\n(3) It would also be interesting to see a benchmark against Gradient Sign Dropout (https://arxiv.org/abs/2010.06808) which is a stochasticity-based method that appeared at NeurIPS last year and was shown to outperform PCGrad in some settings. This particular method at a very high level sparks some similarities as it also starts with the average gradient an then makes slight adjustments based on where the gradient vectors disagree.\n\n(4) Only a computational efficiency comparison is provided between CAGrad, PCGrad, and MTAN. Notably, both CAGrad and PCGrad require multiple full backpropagation passes, while other methods like MGDA, Gradnorm, etc. mitigate the computational overhead by only requiring the backpropagation back to a downstream activation layer. Could authors provide computational comparisons to those methods as well, as this efficiency is some cause for concern?\n\n(5) Authors sweep their main hyperparameter through 10 values - did they take this into account when calculating statistical significance between CAGrad and other baselines?\n\n(6) Is the primary reason for focusing on the worst-case gradient so that the dual problem formulation would work out? Or is there a more intuitive non-mathematical reason for why this is the right optimization problem to solve?\n\n(7) There is always an interesting disconnect in gradient-based MTL methods where the method itself is optimized on the training set while the experiments are all run on the test set. Could the authors comment on potential drawbacks of overfitting to the average loss in the context of generalizability?\n\n(8) Given that there are quite a large corpus of papers at this point that talk about gradient conflict for MTL, the title of the paper is rather ambiguous. Maybe modifying it to explicitly mention the minimax nature of the proposed method would be more appropriate. \n\n**Post-review**: Thanks to the authors for their thoughtful response. I think it is an interesting paper, and I think I am in agreement with authors that further work on loss scaling could further improve the work. As it is now I will maintain my rating at a 6.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "bHtdRyym5N", "reviewer": "Reviewer_KEnK", "summary": "This work proposes a method to reduce conflicting gradients during training of multi-task learning paradigms via gradient modification. Rather than simply take an average of the per-task gradients, the authors propose to learn a model-wide gradient direction $d$ to update the shared parameters by solving a dual objective to find per-task loss weights. Simply, the proposed method (CAGrad) finds a direction which maximizes the worst local improvement among all tasks, and then applies this gradient update to the shared parameters. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work naturally builds on prior efforts (notably MGDA and MOO) to propose a new algorithm inspired by past work on conflicting gradients (PCGrad) that simply tries to maximize the smallest per-objective change in loss after applying a gradient update (i.e. maximize the worst local improvement among all tasks). The paper is incredibly well-written and easy to read/understand. \n\nIt is my opinion that this method is not especially novel or surprising; however, strong empirical findings as well as comprehensive theoretical analysis could more than make up for the lack of novelty. The theoretical results are compelling, while the author's suggested speed-up by sampling a subset of tasks to reduce training-time overhead is also welcome. Nevertheless, there are several areas where the paper could be improved. \n\n\n-------------\nQuite a bit of recent related work is missing from this paper. For instance, recent methods improving upon PCGrad (namely [1] and [2]) are entirely absent. \n\n[1] Just Pick A Sign: Optimizing Deep Multitask Models with Gradient Sign Dropout (NeurIPS, 2020)\n\n[2] Gradient Vaccine: Investigating and Improving Multi-task Optimization in Massively Multilingual Models (ICLR, 2021)\n\nSimilarly, the concept of exploring the rate of loss decrease to modify optimization processes has been recently explored in [3] and equation (2) of this paper is remarkably similar to Line 2 of Equation (3) in [4]. \n\n[3] Measuring and Harnessing Transference in Multi-Task Learning\n\n[4] Adaptive Auxiliary Task Weighting for Reinforcement Learning\n\n-------------\n\nI would also ask the authors to address the following concerns:\n\n1. **Comparison with prior work.** From Section 5.2, it seems as if Uncertainty Weights are not added to PCGrad to create a \"fair comparison\"; although PCGrad uses this augmentation for all results reported in their paper.  Given CAGrad solving for $w^{*}$ at every step, thereby dynamically changing the loss weights, how is this fair? Am I missing something? \n\n2. **Loss values as a function of time.** Plotting the train loss as a function of steps to show overfitting/underfitting is not occurring on MultiMNIST for any of the methods presented in Figure 4. Providing the analogous plots for Figure 5 (test loss on NYUv2 and Cityscaps) would also strengthen this paper's empirical findings. \n\n3. **RL Training efficiency.** Similar to point 2, reformulating Table 3 in a similar manner to PCGrad's Figure 3 would be helpful for understanding the relative learning efficiency and convergence of CAGrad.\n\n4. **Hyperparameter tuning discrepancies.** Is the hyperparameter tuning of $c$ done for the experimental results analogous to hyperparameter tuning of the learning rate? Would it be appropriate to tune the learning rate for the other baseline methods in a similar manner (such that the total update magnitude is roughly equivalent, a small grid search over the learning rate)? \n\n5. **Runtime Comparison with PCGrad.** Is the training-time comparison to PCGrad in Figure 5 fair (i.e. using the efficient vectorized_map implementation by the official repo)? How are the quantities so different (600 -- what I assume to be minutes..? compared with just over 400) when both methods take the gradient w.r.t. each task? How does training time compare on MultiFashion/MNIST? What type of hardware is used (see Checklist item 3d)? \n\nFor these reasons, I think the experimental results, as presented, are insufficient. I am happy to revise my review during the rebuttal if they can be resolved to strengthen this facet of the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors did not discuss the societal impacts of their work. I think they could consider the possible ramifications as done in similar NeurIPS publications on this topic (see [1] and [5]). \n\n[5] Gradient Surgery for Multi-Task Learning (NeurIPS, 2020)\n", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "RwcYuwGVFwY", "reviewer": "Reviewer_Nd5K", "summary": "This work presents a first-order multi-task learning method which uses, in place of the average task gradient, a vector which maximises the minimum local single-task improvement in a neighborhood of the average task gradient.\n\nIn multi-task learning, the goal is to find the optimal point achieving low losses across all tasks. However, gradient descent methods commonly used for single tasks in computer vision and reinforcement learning achieve suboptimal performance when applied on the average task loss due to conflicting gradients (single tasks gradients pointing in opposite directions). Recently, several methods have proposed modification to the update direction that alleviate this problem. However, these methods are either heuristics or can converge to any point in the pareto optimal set of the task losses (e.g. MGDA [5]), which might not be a minimum of the average task loss. \n\nThe proposed method, called Conflict-Averse Gradient descent (CAGrad), introduces an additional hyperparameter $c \\geq 0$ which allows to interpolate between gradient descent ($c = 0$) and MGDA ($c \\to \\infty$). Furthermore, CAGrad provably converges to a stationary point of the average task loss with the same rate as gradient descent (when $c < 1$) or to a pareto stationary point (when $c \\geq 0$). At each step of the method, the update direction is obtained by solving  an optimization problem in $K$ dimensions, where $K$ is the number of tasks, but has an overhead comparable to state of the art multi-task learning methods of the same kind (see last plot of Figure 5). Experiments on several computer vision and reinforcement learning multi-task benchmarks, where the method is used to optimize deep network parameters, show that the method achieves state of the art performance in all the settings.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "#### **Originality**\n1. The method can be considered a fairly straightforward extension of MGDA [5] and it seems novel.  Related works are appropriately cited and it is very clear how the proposed approach compares to them. However, I am not very familiar with recent progress in multitask learning. Contributions are clearly stated in lines 43-51 but I have doubts on some of the claims (see quality section). \n\n#### **Quality**\n\n2. The authors claim that when $c -> \\infty$ the algorithm is equivalent to MGDA [5] (line 107). However, while intuitively minimizing $F(w)$ will correspond to the same minimization problem solved by MGDA, the final update direction will be scaled by $\\sqrt{\\phi} = c ||g_0||$.\n\n3. The authors write that one of the main advantages of the method is that it has convergence guarantees to the stationary point of the average task loss, which PCGrad and MGDA lack. While this is true for MGDA it is usually not true for PCGrad, which either converges to a stationary point of the average task loss or to a point where the directions of the task gradients cancel out [34], although the latter does not usually occur in practice when taking stochastic gradients. \n\n4. All methods in Tables 1 and 2 achieve largely better performance than what is reported in [34]. Why is that? I think this should be discussed in the paper.\n\n5. The proofs before the convergence analysis section seem correct. Theorem 3.3 in the main is different from the one in the supplementary. I will assume the latter to be the correct one. Theorem 3.3 1)  (convergence to stationary point of average task loss with $c < 1$) is proved correctly while the proof for 2) (all fixed points of the method are pareto stationary) is not clear to me: I could not understand how a fixed-point of the algorithm is a pareto stationary point when $g_0 (\\theta) = 0$ (lines 382 and 383). 2) is a fundamental result of the proposed method, without it even if you can show that when $c \\geq 1$ the method converges you cannot guarantee for it to converge to a pareto stationary point. Furthermore the convergence with $c \\geq 1$ is guaranteed (in the supplementary) with time-varying step sizes not used in the experiments or discussed. In the realistic experiments $c < 1$.\n\n6. The experiments are extensive and show a clear advantage of CAGrad in all settings considered. However, the authors should discuss more about the introduced hyperparameter $c$ and how much it is difficult to tune, as a potential limitation of the approach. Note that PCGrad and MGDA, which are the main contenders, have the same hyperparameters as gradient descent.  The experiments in Section 5.1 only study the final training loss varying $c$ for a single artificial setup and the toy example, while the other experiments select the best $c$ looking at the average training error and the optimal value varies largely among different scenarios. Including sensitivity analysis for $c$  in some of the realistic settings and discussing this limitation in the conclusion could address this issue.\n\n#### **Clarity**\n\n7. The main paper is well written and easy to follow. I really appreciated the toy example in Figures 1 and 3 and the illustration in Figure 2 which visually compare CAGrad with other methods. The supplementary was less clear and contained more typos.\n\n#### **Significance**\n8. Studying multi-task learning is important to widen the scope of applicability of machine learning models. This work develops a principled, efficient and effective method which can be applied in combination with deep learning models and optimizers and thus it is important for a large part of the machine learning community. \n\n#### **Final Score**\n\n9. I am giving a 5. The proposed method seems promising but the theoretical justification  is lacking and I have some doubts on the experiments. However, I am not very familiar with the topic and I am willing to increase the score if the authors properly address my concerns in the quality section.\n\n\n#### **Additional comments**\n\n10. In some parts of the paper, like the abstract and intro it is written that the method converges to a minimum or to optimal points. It would be better to say that it converges to stationary points instead since the single task and the average task losses are non-convex both in the theoretical results and in the experiments.\n\n11. eq. (2) and (3) could be misleading. Going forward in the paper shows that the objective that the authors actually minimize is the LHS of (3) but this could also be said close to line 94.\n \n12. Line 199. The authors could briefly describe what the two tasks are (one is to classify the MNIST image and the other to classify the Fashion mnist one).\n\n13. Figure 4. I think that using the same set of seeds for the algorithms could help to make the point more concrete.\n\n14. An interesting addition would be the comparison/discussion on MGDA-UB, which seems to greatly improve the time complexity of MGDA by using an upper bound on the objective used to obtain the update direction. Can a similar upper bound be derived for CAGrad?\n\n#### **Post Rebuttal**\nThe authors have addressed very well my concerns in the quality section of the review by conducting experiments which analyse the newly introduced hyperparameter c and clarifying parts of the paper I did not fully grasp before. Thus I am increasing the score from 5 to 7 and the confidence from 2 to 3.\n\n#### **References**\n\n[5] Jean-Antoine Désidéri. Multiple-gradient descent algorithm (mgda) for multiobjective optimization.Comptes Rendus Mathematique, 350(5-6):313–318, 2012.\n\n[25] Ozan Sener and Vladlen Koltun. Multi-task learning as multi-objective optimization. arXiv preprint arXiv:1810.04650, 2018.\n\n\n[34] Tianhe Yu, Saurabh Kumar, Abhishek Gupta, Sergey Levine, Karol Hausman, and Chelsea Finn. Gradient surgery for multi-task learning.arXiv preprint arXiv:2001.06782, 2020.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors address some but not all the limitations of the method. They do not discuss enough about the newly introduced $c$ hyperparameter which is absent in related methods (see point 6 of the main review). \n\nThe authors write in the checklist that their work does not have a negative societal impact. I agree\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "8X1ilJ9C80s", "reviewer": "Reviewer_w48w", "summary": "Multi-task learning (MTL) is an efficient way of learning multiple tasks efficiently by training all tasks together, amortizing their cost by sharing some parameters across tasks. In order to perform this, a weighted sum of the task losses is usually optimized, which can lead to poor final results due to sub-optimal optimization, an effect produced by the competition between tasks for the shared resources. Specifically, when computing the gradient updates for the shared resources, gradients of different tasks can conflict with each other, cancelling each other out (an effect known as *conflicting gradients*).\n\nThis work introduces CAGrad, an algorithm which minimizes the average loss function (the network's loss), while maximizing the worst local improvement across all tasks, provably converging to a local minimum of the average loss. This algorithm results in a generalization of the usual gradient descent, as well as the MGDA algorithm. Empirical results show the effectiveness of the method.", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Clarity and significance:** I enjoyed reading this paper. I think the paper is well-structured and well-presented, making it joyful to read. This is also partly because of its significance, as I can see CAGrad being impactful and used by the community, resulting in a strict improvement over MGDA. When it comes to the way CAGrad is described and introduced, while everything said is true, I find it a bit misleading. For me, it was way more interesting and clarifying to read the remark in line 339 of the appendix:\n> The major difference between MGDA and CAGrad is that the new update vector d is searched around the 0 vector for MGDA and $g_0$ for CAGrad.\n\nThis line and the results in that page made me better understand CAGrad and its connections with MGDA, and I truly believe this should be put into the main text.\n\n**Related work and experimental comparisons:** This is one of the weakest points of the paper. While the paper does a good job at presenting PCGrad and MGDA, it leaves out several works completely related with the topic of the paper:\n1.  [GradNorm](http://arxiv.org/abs/1711.02257) is mentioned but never compared with (GradNorm's goal is to normalize gradients, and it scales losses just because the gradient is a linear operation). \n2. [IMTL-G](https://openreview.net/forum?id=IMPnRXEWpvr) is another method for gradient scaling which is not even mentioned.\n3. [RotoGrad](https://arxiv.org/abs/2103.02631) is a method that focuses on reducing negative transfer by aligning task gradients.\n4. [GradDrop](https://proceedings.neurips.cc//paper_files/paper/2020/hash/16002f7a455a94aa4e91cc34ebdb9f2d-Abstract.html) is another gradient conflicting solution, contemporary to PCGrad, which solves the issue by randomly dropping gradient elements based on a sign-purity score.   \n\n**Working on the last-shared representation:** Most of these recent works address the inherent scalability issues of modifying the gradients of the shared parameters by simply modifying those of the last shared representation (the output of the backbone). Whilst I am not entirely sure how this would apply in the case of using MTAN rather than a usual hard parameter-sharing architecture, I am surprised that this was not thought as a way of scaling CAGrad. \n\nThis overlook is even more surprising since the authors claim to compare with the MGDA version of Sener et. al (e.g. in Table 4) rather than the one originally proposed by Jean-Antoine Désidéri. Both papers are mentioned in the manuscript, and my understanding is that the main contribution of the paper of Sener et. al. was proposing MGDA-**UB** (upper-bound), which showed that MGDA could scale for MTL settings by working on the output of the backbone. In reality, here CAGrad is compared with the original MGDA algorithm by Désidéri.\n\n**Experiments.** While the experiments are well described, I have some questions for the authors:\n- Why using a shrunk version of LeNet?\n- How did you choose the parameters for the FashionMNIST experiments? I have worked with very similar datasets and with 50 epochs convergence was not guaranteed. I would like to know why there are only 3 independent runs in such a simple experiment?\n- Do you apply some kind of loss normalization to ensure that losses have comparable values?\n- Regarding this last question, I find Figure 4 really confusing. You attempt to minimize the average of the losses, and so one could expect that the optimum of the average of the losses is achieved when both tasks losses are equal (at the end, \"you care the same\" about both losses), which is what MGDA achieves. I think this figure would be way more understandable (and therefore the discussion) if you showed the results normalizing each task by their initial loss during training.\n- Why did you choose c based on the *training* loss instead of the validation loss? This should not be the case.\n- Did you run MTAN on NYUv2 with data augmentation? This was included in the official repository of MTAN.\n\n**Minor comments:**\n- Caption on tables should be placed above the table.\n- Eq. (2) is a bit confusing, I would rather see the first part written as $min \\{\\frac{1}{\\alpha} (L_i(\\theta) - L_i(\\theta - \\alpha d))\\}$. \n- MTAN references are wrong in the experiments. \n- Figure 3 is hardly readable. I would remove the right-most and increase the size of the rest.\n\nI think this is a great paper with a lot of potential, and I will be happy to increase my score if the problems raised above are addressed.\n\n---\n\n**Update:** While I have few concerns when it comes its technical part, I still remain concerned regarding the way the paper presents existing work. It is missing important baselines (e.g. IMTL-G) and completely omits any reference to the set of methods that work on only the last shared representation of the architecture. \n\nI do not feel this is properly justified after rebuttal. First, if not comparing with it, this line of work should be mentioned as it is relevant. Second, in the response this was justified by the chosen experimental setup, but to me this is upside-down: the experimental setup should be chosen to compare with all relevant methods, and no the other way around.\n\nI am thus lowering my score to 5 as I expected a better justification by the authors and I am afraid that, given the nice quality of the paper, it is likely to get some attention and as a consequence harm relevant (and future) work by omitting any reference to prior approaches.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I find the discussion of the limitations of the work rather disappointing. In practice, MGDA is slow when it comes to time complexity (because of solving $min_\\omega ||g_w||$). This term also appears in CAGrad, does that mean that CAGrad also suffers the same overhead? Why? (lines 244 to 246 make me think so)", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7 hours"}, "extra_text": {}}, {"review_id": "1-z44mJZkON", "reviewer": "Reviewer_MG2N", "summary": "The paper proposes a new solution to multi-task learning  that should improve in cases with gradients conflict of a task loss and the average loss gradient. The solution optimizes for an update vector that maximizes the worst task loss relative improvement. Experiments show the superiority of the proposed solution over similar prior methods.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is very well written and easy to follow. \nThe proposed solution is sound and seem to overcome the existing optimization difficulties of multi-task learning.\nExtensive experiments are carried on, targeting different interesting questions. \nMethod performance is superior or comparable to existing methods. \nThe main down side is the optimization for an update vector after each update, however, the authors proposed a dual objective with the number of optimized parameters equal to the number of tasks being learned.  Further an approximation is proposed to reduce the computation cost where random tasks are selected for the optimization. This alternative is comparable in performance to existing methods. \n\nOn line 88, first order Taylor approximation is used but no discussion on this choice.\nLine 95, a hyperparameter is introduced with no discussion its role. However, in the experiments section it is effect is shown empirically. \nThe practical speedup  is not well motivated and justified.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The manuscript is proposing a multi-task learning method using multi-objective optimization. The proposed algorithm extends the MGDA line of work by simply changing the objective from finding a descent direction that is consistent with all objectives to finding a descent direction that is consistent with all objectives and closest to the average gradient. The proposed algorithm is later analyzed theoretically with Pareto stationarity and convergence guarantees. The authors provide an extensive empirical study with very promising results. Reviewers all enjoyed reading the paper and appreciated the algorithm. Most of the major issues about the paper are on the set-of-baselines side which the authors addressed successfully with additional experiments during the rebuttal perior. I believe the paper is interesting and warrant acceptance.
Decision: Accept (Poster)