Mitigating Gradient Bias in Multi-objective Learning: A Provably Convergent Approach
Authors: Heshan Devaka Fernando
Han Shen
Miao Liu
Subhajit Chaudhury
Keerthiram Murugesan
Tianyi Chen
Venue: ICLR 2023 notable top 5% (2023)
Keywords: Multi-objective Optimization
Machine Learning

Abstract: Many machine learning problems today have multiple objective functions. They appear either in learning with multiple criteria where learning has to make a trade-off between multiple performance metrics such as fairness, safety and accuracy; or, in multi-task learning where multiple tasks are optimized jointly, sharing inductive bias between them. This problems are often tackled by the multi-objective optimization framework. However, existing stochastic multi-objective gradient methods and its variants (e.g., MGDA, PCGrad, CAGrad, etc.) all adopt a biased noisy gradient direction, which leads to degraded empirical performance. 
To this end, we develop a stochastic multi-objective gradient correction (MoCo) method for multi-objective optimization. The unique feature of our method is that it can guarantee convergence without increasing the batch size even in the nonconvex setting. Simulations on multi-task supervised and reinforcement learning demonstrate the effectiveness of our method relative to the state-of-the-art methods. 

Published as a conference paper at ICLR 2023
MITIGATING GRADIENT BIAS IN MULTI-OBJECTIVE LEARNING: A PROVABLY CONVERGENT APPROACH
Heshan Fernando', HHn Shen', Miao Liu?, Subhajit Chaudhury", Keerthiram Murugesan', Tianyi Chen'
1 Rensselaer Polytechnic Institute
'IBM Thomas J. Watson Research Center
ABSTRACT
Machine learning problems with multiple objectives appear either i) in learning with multiple criteria where learning has make trade-off between multiple performance metrics such as fairness, safety and accuracy; or, ii) in multi-task learning where multiple tasks are optimized jointly, sharing inductive bias among them. These multiple-objective learning problems are often tackled by the multi- objective optimization framework. However, existing stochastic multi-objective gradient methods and their recent variants (c.g., MGDA, PCGrad, CAGrad, etc.) all adopt a biased gradient direction, which leads to degraded empirical performance. To this end, we develop stochastic multi-objective gradient correction (MoCo) method for multi-objective optimization. The unique feature of our method is that it can guarantee convergence without increasing the batch size even in the nonconvex setting. Simulations on supervised and reinforcement learning demonstrate the effectiveness of our method relative to state-of-the-are methods.
INTRODUCTION
Multi-objective optimization (MOO) involves optimizing multiple, potentially conflicting objectives simultaneously. Recently, MOO has gained attention in various application settings such as optimizing hydrocarbon production Youu et al., 2020), tissue engineering (Shi et al. 2019), safe reinforcement learning TThoma et al.) 2021), and training neural networks for multiple tasks (Sener & Koltun
2018 We consider the stochastic MOO problem as
min F F(x) == (Belfi (2,, E)], (2, (2, =EX
where X' C Rd the feasible set, and fm X' -> R with (x) == Ef E)] for m E [M]. Here we denote [M] = 21, .M and denote & as random variable. In this setting, we interested in optimizing all of the objective functions simultaneously without sacrificing any individual objective. Since we cannot always hope to find a common variable x that achieves optima for all functions simultancously, a natural solution instead is to find the so-termed Pareto stationary point that cannot be further improved for all objectives without sacrificing some objectives. In this context, multiple gradient descent algorithm (MGDA) has been developed for achieving this goal (Désidéri 2012). The idea of MGDA is to iteratively update the variable z via a common descent direction for all the objectives through a time-varying convex combination of gradients from individual objectives. Recently, various MGDA-based MOO algorithms have been proposed, especially for multi-task
learning (MTL) Sener& & Koltun 2018 Chen et al. 2018 Yu et al. 2020a Liu al. 202
While the deterministic MGDA algorithm and its variants are well understood in literature, only little theoretical study has been taken its stochastic counterpart. Recently, (Liu & Vicente 2021 has introduced the stochastic multi- multi-gradient (SMG) method as a stochastic counterpart of MGDA (see Section 2.3 for details). To establish convergence, however, (Liu & Vicente, (2021) requires strong assumption on the fast decaying first moment of the gradient, which was enforced by linearly growing the batch size. While this allows for analysis of multi-objective optimization in stochastic setting, this may not be true for many MTL tasks in practice. Furthermore, the analysis in (Liu & Vicente
The work was supported by the National Science Foundation CAREER project 2047177 and the RPI-IBM Artificial Intelligence Research Collaboration. Correspondence to: Tianyi Chen (chentianyi @mmail.ommmm

---

Published as a conference paper at ICLR 2023
Sai
75.4
(a) Mean objective
(b) Objective
(c) Objective
(d) MGDA
(c) SMG
(f) PCGrad
(g) CAGrad
(h) MoCo (ours)
Figure A toy example from (Liu et al. 2021a) with two objective (Figures lb and Ic show
the impact of gradient bias. We use the mean objective reference when plotting the trajectories corresponding to each initialization (3 initializations in total). The starting points of the trajectories denoted by black and the trajectories are shown fading from red (start) to yellow (end). The Pareto front given by the gray bar, and the black * denotes the point in the Pareto front corresponding equal weights to each objective. We implement recent MOO algorithms such as SMG (Liu & Vicente 2021). PCGrad (Yu et al. (020a), and CAGrad (Liu et al.) (021a), and MGDA (Désidéri 2012) alongside
method. Except for MGDA (Figure ld) all the other algorithms only have access to gradients of each objective with added zero mean Gaussian noise. It can be observed that SMG, CAGrad, and PCGrad fail to find the Pareto front in initializations.
2021 cannot cover the important setting with non-convex multiple objectives, which is prevalent in challenging MTL tasks. This leads us to a natural question:
Can design stochastic MOO algorithm that provably converges Pureto stationary point without growing batch size and also in the nonconvex setting?
Our contributions. this paper, we answer this question affirmatively by providing the first stochastic MOO algorithm that provably converges to Pareto stationary point without growing batch size. Specifically, we make the following major contributions:
C1) (Asymptotically unbiased multi-gradient). We introduce call the stochastic Multi-objective gradient with Correction (MoCo) method. MoCo is simple algorithm that addresses the convergence issues of stochastic MGDA and provably converges to Pareto stationary point under several stochastic MOO settings. We use toy example in Figure [ demonstrate the empirical benefit of our method. In this example, MoCo is able to reach the Pareto front from all initializations, while other MOO algorithms such as SMG, CAGrad, and PCGrad fail find the Pareto front due to using biased multi-gradient.
method for MOO that
C2) (Unified non-asymptotic analysis). We generalize our MoCo method to the case where the individual objective function has nested structure and thus obtaining unbiased stochastic gradients is costly. We provide a unified convergence analysis of the nested MoCo algorithm smooth non-convex and convex stochastic MOO settings. To our best knowledge, this is the first analysis of smooth non-convex stochastic gradient- MOO.
C3) (Experiments on MTL applications). We provide an empirical evaluation our method with existing state-of-the-aa MTL. algorithms in supervised learning and reinforcement learning (RL) settings, and show that our method can outperform prior methods such as stochastic MGDA, PCGrad, CAGrad, and GradDrop.
BACKGROUND
In this section, introduce the concepts of Pareto optimality and Pareto stationarity and then discuss MGDA and its existing stochastic counterpart. We then motivate our proposed method by elaborating the challenge stochastic MOO. The notations used in the paper are summarized in Appendix A
2

---

Published as a conference paper at ICLR 2023
2.1 PARETO OPTIMALITY AND PARETO STATIONARITY
In MOO, we are interested in finding the points which can not be improved simultaneously for all the objective functions, leading to the notion of Pureto optimality. Consider two feasible solutions to (T) I, X. We say that dominates z' if (a) I f (z()) for all m E [M]] and F(z) * F(z'). If point x² E X' is not dominated by any x E X, we say x" is Pareto optimal. The collection of all the Pareto optimal points are called the Pareto set. The collection of vector objective values F(x") ) for all the Pareto optimal x is called as the Pareto front.
Akin to the single objective case, necessary condition for Pareto optimality is Pareto stationarity. If x is a Pareto stationary point, then there no common descent direction for all fm (2) at x. Formally, is a called a Pareto stationary point if range F
0 where V VF(x) the Jacobian of Fzz), i.c. (z (z), (z))), .... (fr()))) and R- is the positive orthant cone. When all (I) are strongly convex, Pareto stationary point is also Pareto optimal.
Rdx
2.2 MULTIPLE GRADIENT DESCENT ALGORITIIM (MGDA)
The MGDA algorithm has been proposed in (Désidéri 2012) that can converge to a Pareto stationary point of F(z). MGDA achieves this by seeking a convex combination of individual gradients (m) (also known as the multi-gradient), given by d(x) = Σm=1 Am V (x) where the weights (x) = (M(2), Mr(()) are found by solving the following sub-problem:
(x)) arg min [[V[()))]) S. L. AE M E 11=== A A 0}.
(2)
With this multi culti-gradienteee d(x),, the kth iteration of MGDA is given by
Tk+1 xxx (I ogd((x)) with d(xx)) Σ V
where og is the learning rate, and xIx denotes the projection to set X. It can be shown that MGDA optimizes all objectives simultaneously following the direction -d(x) whenever x is not Pareto stationary point and will terminate once reaches Pareto stationary point (Fliege al. 2019).
However, in many real world applications we either do not have access to the true gradient of functions fm obtaining the true gradients is prohibitively expensive in terms of computation. This leads us to possible stochastic counterpart of MGDA, which is discussed next.
2.3 STOCHASTIC MULTI-OBJECTIV GRADIENT AND ITS BRITTLENESS
The stochastic counterpart of MGDA, referred to as SMG algorithm, has been studied in (Li & Vicente 2021). In SMG algorithm, the stochastic multi-gradied is obtained by replacing the true gradients V Vm (z) ) in (2) with their stochastic approximations V/m(z, (x,g), E), where V.m(())
Eg [V (ar, {)). Specifically, the stochastic multi-gradient is given by
M g(x,E) = Σ (1, with (xx = arg min YEAM
M Σ m==1
Am Xm (1,
(4)
m=1
While this change of the subproblem facilitates use of stochastic gradients in place deterministic gradients, it raise issues in the biasedness in the stochastic multi-gradient calculated in this method.
The bias of SMG. To better understand the cause of this bias, consider the case (4) for simplicity. We can rewrite the problem for solving for convex combination weights as arg min (z, + f2, () which admits the closed-form solution for
of
XE(O.1]
(= = (V (v Vf fa((,, {)
(5)
[[V)( - Vfz(,,)) 1F
where [x]+,]- max(min(r, 1), 0). It can be seen that the solution for À is non-linear in (zr
and (z, E). which suggests that (I) {) (z) and thus E[g(x, <)] + d(x))
To ensure convergence, a recent approach proposed to replace the stochastic gradient V (z, {) with
its mini-batch version with the batch size growing with the number of iterations (Liu & Vicente
3

---

Published as a conference paper at ICLR 2023
Algorithm 1 MoCo: Stochastic Multi-objective gradient with Correction
1: Input Initial model parameter Ip, tracking parameters (yo m=1 convex combination coefficient parameter λe and their respective learning rates {ax] k= and {5x]k=o {=
2: for k == 0........ K 1 do
3:
for objective m = I,... ,,..., MM do
4:
Obtain gradient estimator lmm.k Update 1/++1.m following 6 6: end for
either hmm
V.m (m Ex) or hmm in
13
14
5:
7: Update dc+1 and 2441 following
10
8: end for
9: Output JK
2021). However, this may not be desirable in practice and often leads to sample inefficiency. In multi- objective reinforcement learning settings, this means running increasingly many number of roll-outs for policy gradient calculation, which may be infeasible. On the other hand. Yang et al. (202T) also analyzes MGDA in the stochastic, smooth, and non-convex setting, and establishes convergence. However, to overcome the bias issue in stochastic MGDA, Yang et al. (2021) assumes having access (z), which allows access to an unbiased estimate of the true multi mull-ggadieet d(x). However, this assumption is not practical since computing X (zx requires access to true gradients V fm)(),, which may not be true in a stochastic setting. In contrast, in the following section we propose a method that reduces the bias in multi-gradiee asympioticllly and enjoys provable convergence.
3 STOCHASTIC MULTI-OBJECTIVE GRADIENT DESCENT WITH CORRECTION
In this section, we will first propose a new stochastic update that addresses the biased in MOO, extend it to the nested MOO setting, and then establish its convergence result. To achieve this, we use a momentum-like gradient estimate and a regularized version of MGDA subproblem.
3.1 A BASIC ALGORITHMIC FRAMEWORK
We start by discussing how to obtain Vm (x) without incurring the bias issue. The key idea is to approximate true gradients of each objective using a 'tracking variable', and use these approximations in finding optimal convex combination coefficients, similar to MGDA and SMG. At each iteration k. assuming we have access to hg.m which stochastic estimator of fm (e.g., hg.m = We obtain V (mx) by iteratively updating the 'tracking' variable yk.m E Rd by
V fm E..))
yk+1,m Im yk.m (= hr.m))
1,2, M,,
(6)
where 3& is the step size and II,.,, denotes the projection to set {y E Rd || < L. and Lm is the Lipschitz constant of fm on X.
Under some assumptions on the stochastic gradients ha,m that will be specified in Section 3.3 we can show that for a given Ig. the recursion in (6) admits a unique fixed-point yt, (Ix) that sauisfees
(7) In this subsection will first assume that hu.m is an unbiased estimator of (xx), and will generalize to the biased estimator in the next subsection. In this case, with only one sample needed at each iteration, the distance between Ym,,k and fm is expected diminish as k increases.
Vin (xxx B[hx,m] = (mx)).
Even with an accurate estimate of V (m)),, solving (1) is still not easy since these gradients could conflict with each other. As described in Section 2.2 given x X, the MGDA algorithm finds the optimal scalars, denoted as {>,, {x to scale each gradient V fm((x) such that d(x)) =
EM X (x) fm
fm)(). (r), and -d(x:) is common descent direction for every fm((). For obtaining the corresponding convex combinations when we do not have access to the true gradient, we propose
approximation of F In general, the solution for 2 is not necessarily unique. We overcome this issue by adding l regularization. Specifically, with p 0 denoting the regularization constant, the new subproblem given by
to use Y& = (JA.,,.... ... Mk. E d
(z) arg min /FF())11 I11111 s. AEAM- ( 1===1,20 (8)
4

---

Published as a conference paper at ICLR 2023
Remark 1 (On the Lipschitz continuity of (x))). Since (2) and (4) depend 2, the subproblems change at each iteration. To analyze the convergence of the algorithm, it is important to quantify the change of solutions X* (z) and (x, {) at different z. One natural way is assume the afore- mentioned solutions are Lipschitz continuous in V Fx)); see (Liu & Vicente 2021). However, this condition does not hold in general since V (x)) is not positive definite at least at Pareto stationary points, and thus the solutions to 22) and ( are not unique. We overcome this issue by adding the regularization p to ensure uniqueness of the solution and the Lipschitz continuity of X²(x) in
With this regularized reformulation, we find (x) by running stochastic projected gradient descent of (), given by
AR+1 = AA (Ax 7h (Yg Yn + pl) Xx),
where 7% is the step size, E MRM is the identity matrix, and operator A denotes the projection to the probability simplex A With dS as approximation of X² and Ys, as approximation of V F (xxx, we then update Tę with
24+1 (x as Yx
(10)
where X' is a closed convex set. We have summarized the basic MoCo algorithm in Algorithm |
3.2 GENERALIZATION TO NESTED MOO SETTING
In this section we extend MoCo to the bi-level MOO setting. Recall, in the previous section, we have introduced the gradient estimator hg.m- In the simple case where V m (I, {) is obtained, setting hk.m = V fm ( 5x) leads to the exact solution yrn (I+)) = V fm (2+). However, in some practical applications as shown Section 5.2 fm, <) difficult to obtain, and hence hū.m can be biased.
To put this on concrete ground, we first consider the following nested multi-objective problem:
min F(x) == (B& [/ (z. (a)) ()), (22 ()) BE [/ (2, =M ())) ZEA'
s.t. 2/ (I) = arg min 4m (z, 2) E,1 (z, z, s)), m = 1,2, ... M
(11)
=El
where 4m is strongly-conver
function, and yp is random variable. For convenience, we define
Im (1r, 2) == Egg [m (I, 2, <)] and (x) == (xr z (ar)). The problem [1] is generalization of the popular bilevel optimization framework Ghadimi & Wang 2018); Hong et al. 2020 Liu et al. (2020): Ji et al. (2021); Chen et al. (2021) 2022).
Under some conditions that will be specified later, it has been shown in Ghadiii & Wang 2018 that the gradient of fm (x) takes the following form:
fm)) Vzfm(1 2 (x)) - V Vizlm (I, 2 (z)) ha 2 2 (x)) (2,
(12)
where Vzf(z, 2t (x)) 0f(x.2) | 1 (x). V2 2 (x)) al(x.2)
Ozds === (w) and likewise for V= (xx zm (z:) and V Vsr, zm (x)). Computing the unbiased stochastic estimate of (12 requires
dx
zm (#), which is often costly in practice. Instead, we iteratively update 2k.m to approach zm (Ix) via
1k+ = 2k,m Bx 2. (T). Zk.m, PP))
(13)
Then we use zk.m to replace zm (xxx in the place of (12 to compute a biased gradient estimator as hg.m Vafm (Ih, 2k,m Ex) V2 (2k mm (k)) V=fm( 2k.ms {+)
(14)
where (pk, sh have the same distribution as that of yp, and H is a stochastic approximation of the Hessian inverse ( (Ix, m),m)]] Given JRg when Zk.m reaches the optimal solution = (xxe). it follows from 12) that TE. [(h.,mm = V. We summarize the algorithm for MoCo with inexact gradient in Algorithm (see Appendix DD. When 2k.m is non-optimal, we quantify the error below. Lemma 1. Define Fs as the o-algebra generated by Y1, Y2, ...y Yv. Consider the sequences generated by (6). (9) (1)). (13) and (14). Under certain standard assumptions that will be specified in the supplementary. we have for any m E [M] and for any that
K
E
B (he. [F)) Vmm((x))
0
K
E [
E [h [
- og (15)
K
where El|] is the total expectation, ax, BR are the learning rates, and on > 0 is constant.
5

---

Published as a conference paper at ICLR 2023
Lemma I shows that the average bias of the gradient estimator will diminish if ag and 3k are chosen properly. In addition, the variance of the estimator is also bounded by a constant. Allowing biased gradient in this manner facilitates MoCo to tackle more challenging MTL tasks as highlighted below.
Remark 2 (Connection between nested MOO with multi nulti-objective actor-critic). Choosing each fm T to be the infmite-horizon accumulated reward and each Im to be the critic objective function will lead to the popular actor-critic al algorithm in reinforcement learning (Konda & Borkar 1999.
Wen et al. (021). In this work, we have extended this to the multi-objectiive case, and conducted experiments multi-objective soft actor critic in Appendix K.3
3.3 A UNIFIED CONVERGENCE RESULT
In this section we provide the convergence analysis for our proposed method. First, we make following assumptions on the objective functions.
Assumption 1. For m E [M] [m(() Lipschitz continuous with modulus I'm and Jm (1) is Lipschitz continuous with modulus Im.1. for any x E &.
Due to the x update in (0). the optimal solution for yk.m and A sequences are changing at each iteration, and the change scales with || = In order guarantee the convergence of ykum and λR. the change in optimal solution needs to be controlled. The first half of Assumption [ ensures that f(x) is uniformly bounded, that is, | - x&ll is upper bounded and thus controlled. The second half of the assumption is standard in establishing the convergence of non-convex functions (Bottou al. 2018). Next, we make an alternative version of Assumption for analysis in the convex setting. Assumption 2. Function fm (z) is convex for any m [M] and the feasible set X is bounded.
Notice when X' is bounded, then there exists constant C2 such that || |x'l S C2 for any x, x' E X. This assumption controls |a - Ix when the objective functions are convex. Next, to unify the analysis of the nested MOO in Section 3.2 and the basic MOO in Section 3.11 we make the following assumption on the quality of the gradient estimator hg..
Assumption 3. For any m [M], there exist constants Cm Fm such that + Σ K / and Bathhh.mBBBhh... [FAl for any k.
[FR]
S fmxx)]]
Assumption 3 requires the stochastic gradient fuk. almost unbiased and has bounded variance. Compared to (Liu & Vicente 2021] Assumption 5.2), Assumption B]ss weaker, because i) it does not require the variance o' to decrease in the same speed as a and ii) it allows bias in the stochastic gradient of each objective function. In practice, the batch size is often fixed, and thus the variance is non-decreasing, which suggests one benefit of Assumption 3
over that in (Liu & Vicente 202T).
Lemma 2. Consider the sequences generated by Algorithm 7 Assume that K > M such that K = (M 1)). Then, under Assumptions [ and 3 or Assumptions 2 and 3 if we choose step sizes
ag = O(K 18 ). Bx O(K ), 7k = +O(K-
-t) 8). and p = O(K- $). it holds that
Σ E [d(pk)) Y&A O(K b).
(16)
With suitable choice of p. as A and Y2 converge to (zx) and Fx(x) respectively, the update direction Yελr for ig converges to d(xx)) = (*(xx)>*(xx)) which the desired MGDA direction. It can be seen that our method achieves vanishingly small expected error in stochastic multi gradient asymptotically for all trajectories, while SMG fails to reduce the error in multi gradie..
The following theorem then captures the convergence of I& under convex objective functions. Theorem 1. Consider the sequences generated by Algorithm | Under Assumptions 2 and if we choose ag = O(K 1)), Bx = O(K-5) -)), 3.,7k 7 O(K-3 $), and p O(K- &), it holds vx E X that
K
B(x((x)) (F(*)) F(x* ) = 0 K -
(17)
If we choose x² as the Pareto-optimal point and X (xxx) > O, Theorem captures the convergence to the Pareto-optimal objective values.

---

Published as a conference paper at ICLR 2023
-10
000
6
(a) MGDA
(b) SMG
(c) PCGrad
(d) CAGrad
(c) MoCo (ours)
Figure 2: Comparison of trajectories in the objective space. We use five initializations in the same toy example in Figure [ and plot the optimization trajectory in the objective space. MGDA converges to the Pareto front from all of the initializations. SMG, PCGrad, and CAGrad which only have access to single stochastic gradient per objective fail to converge to the Pareto front in some initializations. Our MoCo follows similar trajectory that of MGDA, and finds the Pareto front for each initialization.
In many practical problems the objective functions are non-convex, and the following theorem establishes the convergence of the proposed method for non non-convex functions.
Theorem 2. Consider the sequences generated by Algorithm / with X R Under Assumptions 1
and 3 if we choose 0g O(K +)) 3x ((K- }), 7hk O(K- +), and p O(K- +), it holds
K
Σ E [IV
o (KK+t) t
(18)
K
Theorem shows that the MGDA direction ( ) (xx) converges to O, which indicates that the proposed method is able to achieve Pareto-stationnaity. It is the first finite-time convergence guarantee for the stochastic MGDA method under non-convex objective functions.
Theorem 3. Consider the sequences generated by Algorithm 7 with X' = Furthermore assume
there exists a constant > such that for all [K], [[F((ar) || S F. Then, under Assumptions
and 3 if we choose 0g = OKK 8). Bx = OKK 8 7n O(K-K) and p = O, it holds that
K
E [[V K
1
(MMK-B)
(19)
Theorem 3 shows Algorithm will converge a Pareto stationary point with an improved convergence rate, if the sequence of functions F(z1), F(22),.... F. F(rx) are bounded.
Remark 3 (Comparison with SMG). Theorems 7 Jand provide the convergence rates of MoCo under Assumptions 7 and Assumptions 7 and respectively. Compared the convergence analysis of SMG in (Liu & Vicente| (027). the convergence rates in Theorems and are derived under small butch size, without the unjustified assumption on the Lipschitz continuity of X (xx) and additionally account for the non-convex MOO setting. This may not be true unless F is full rank which can not be true at Pareto stationary points. We overcome this problem by adding a properly chosen regularization to the problem. We also provide an improved sample/iteration complexity with Theorem 3 under some additional assumptions on F(xx). Furthermore, we provide an improvement over Theorem 3 with modified assumption the stochastic gradient bias in Appendix
4 RELATED WORK
To put our work in context, we review prior art that we group in the following two categories.
Multi-task learning. MTL algorithms find a common model that can solve multiple possibly related tasks. MTL has shown great success in many fields such as natural language processing, computer vision and robotics (Hashimoto et al. 2016), (Ruder] 2017). 7) (Zhang & Yang 2021), (Vandenhende) et al. 202 h. One line of research involves designing machine learning models that facilitate MTL, such as architectures with task specific modules (Misra et al. 2016). with attention based mechanisms (Rosenbaum et al.] 2017), YYagg et al. 2020), or with different path activation corresponding to different tasks. Our method is model agnostic, and thus can be applied to these methods in a complementary manner. Another line of work focuses decomposing problem into multiple local
7

---

Published as a conference paper at ICLR 2023
Segmentation (Higher Better)
Depth (Lower Better)
Method
mloU
Pix Acc
Abs Err
Rel Err
Am%
Independent
74.01
93.16
0.0125
27.77
Cross-Stitch Stitch Misra et al.
2016
73.08
92.79
0.0165
118.5
90.02
MTAN (Luu ct al.
2019)
75.18
93.49
0.0155
46.77
22.60
MGDA
Sener & Koltun 2018
68.84
91.54
0.0309
33.50
44.14
PCGrad
Yu et al.
2020a
75.13
93.48
0.0154
42.07
18.29
GradDrop
Chen
2020)
75.27
93.53
0.0157
47.54
23.73
CAGrad
Liu et al.
2021a)
75.16
93.48
0.0141
37.60
11.64
MoCo (ours)
75.42
93.55
0.0149
34.19
9.90
Table Multi-task supervised learning on CityScape dataset with the 7-class semantic segmentation and depth estimation results. Results averaged over 3 independent runs. CAGrad, PCGrad, GradDrop and our method are applied on the MTAN backbone.
tasks and learn these tasks using smaller models (Rusu et al. 2015)) (Parisotto et al. 2013). (Te et al. 2017), (Ghosh et al., 2017). These models then aggregated into single model using knowledge distillation (Hinton et al. 2015). Our method does not require multiple models in learning, and focus on learning different tasks simultaneously using a single model.
Gradient-based MOO. This line of work involves optimizing multiple objectives simultancously using gradient manipulations. A foundational algorithm in this regard MGDA(Desidén) (012)) which dynamically combine gradients to find a common descent direction for all objectives. A comprehensive convergence analysis for the deterministic MGDA algorithm has been provided in (Fliege et al., 2019). Recently, (Liu & Vicente, 202T) extends this analysis to the stochastic counterpart multi-gradient descent algorithm, for smooth convex and strongly convex functions. However, this work makes strong assumptions on the bias of the stochastic gradient and does not consider the nested MOO setting that is central to the multi-task reinforcement learning. In Yang et al.) (202T), the authors establish convergence of stochastic MGDA under the assumption of access true convex combination coefficients, which may not be true a practical stochastic optimization setting. Another related line of work considers the optimization challenges related to MTL, considering task losses as objectives. One common approach is to find gradients for balancing learning of different specific criteria such as uncertainty (Kendall et al. 2017), gradient norms (Chen et al. 2018) B) or task difficulty (Guo et al.) 2018). These methods are often heuristics and may be unstable. More recent work (Sener & Koltun 2018). (Yu et al. 2020a). (Liu et al. 202 (Gu et al., 202T) introduce gradient aggregation methods which mitigate conflict among tasks while preserving utility. In (Sener & Koltun 2018), MTI has been first tackled through the lens of MOO techniques using MGDA. In (Yu et al. 2020a). new method called PCGrad has been developed to amend gradient magnitude and direction confficts among per task gradients. In (Liu et al.) 202 algorithm similar to MGDA, named CAGrad, has been developed, which uniquely minimizes the average task loss. In (Liu et al. 2021b), an impartial objective gradient modification mechanism has been studied. Concurrent to work, a Nash bargaining solution has been proposed in (Navon et al.) 2022) for weighting per objective gradients. All the aforementioned works MTL use the deterministie objective gradient for analysis (if any), albeit the accompanying empirical evaluations are done in a stochastic setting. There are also gradient-based MOO algorithms that find set of Pareto optimal points for a given problem rather than one. To this end, works such as (Liu et al. 2021c| Liu & Vicente [021] Lin et al. 2019
tasks. The simplest way is to re-weight per task losses based
order to avoid
Mahapatra & Rajan 202T Navon al. 2020 Lin al. 2022] Kyriakis et al., 2021 Yang al. 2021; et al. 2021 Momma et al. (022). develop algorithms that find multiple points in the Pareto front in mutil-task supervised learning or reinforecement learning settings, ensuring some
quality of the obtained set of Pareto points. Our work is orthogonal to this line of research, and can potentially combined with those method to achieve better performance.
EXPERIMENTS
In this section, first we provide further illustration of our method in comparison with existing gradient- based MOO algorithms in the toy example introduced in Section [
Then we provide empirical
8

---

Published as a conference paper at ICLR 2023
Segmetation
Depth
Surface Normal
Method
(Higher Better)
(Lower Better)
Angle Distance
Within
Am% +
(Lower Better)
(Higher better)
mloU
Pix Ace
Abs Err
Rel Err
Mcan
Median
11.25 22.5 30
Independent
38.30
63.76
0,6754
0,2780
25.01
19.21
30.14
57.20
69.15
Cross-Stitch
37.42
63.51
0,5487
0.2188
28.85
24.52
22.75
46.58
59.56
6.96
MTAN
39.29
65.33
0.5493
0.2263
28.15
23.96
22.09
47.50
61.08
5.59
MGDA
30.47
59.90
0,6070
0.2555
24.88
19.45
29.18
56.88
69.36
1.38
PCGrad
38.06
64.64
0.5550
0.2325
27.41
22.80
23.86
49.83
63.14
3.97
GradDrop
39.39
65.12
0,5455
0.2279
27.48
22.96
23.38
49.44
62.87
3.58
CAGrad
39.79
65.49
0.5486
0.2250
26.31
21.58
25.61
52.36 65.58
0.20
MoCo (ours)
40,30
66.07
0,5575
0,2135
26.67
21.83
25.61
51.78 64.85
0.16
Table 2:
Multi-task supervised learning on NYU-v2 dataset with 13-class semantic segmentation, depth estimation, and surface normal prediction results on NYU-v2 dataset. Results are averaged over 3 independent runs. CAGrad, PCGrad, GradDrop and MoCo are applied on the MTAN backbone.
comparison of our proposed method with the state-of-the-art MTL algorithms,, using challenging and widely used real world MTL benchmarks in supervised and reinforcement learning settings. The details of hyperparameters are provided in Appendix K
Toy example. To further elaborate on how MoCo converges to a Pareto stationary point, we again optimize the two objectives given in Figure and demonstrate the performance in the objective space (Figure 2) MGDA with true gradients converges However, it can be seen that SMG, PCGrad,and CAGrad methods fail to converge to a Pareto stationary point, and end up in dominated points in the objective space for some initializations. This is because these algorithms use biased multi gulti-gradient that does not become zero. In contrast, MoCo converges to Pareto stationary points every initialization, and follows a similar trajectory to MGDA.
Pareto stationary point in all initializations.
5.1 SUPERVISED LEARNING
We compare MoCo with existing MTL algorithms using NYU-v2 (Silberman et al.) 2012) and CityScapes (Cordts et al. 2013) datasets. We follow the experiment setup of (Liu et al. 222 and combine our method with MTL method MTAN (Liu et al.. 2019), which applies an atten- tion mechanism. We evaluate our method in comparison to CAGrad, PCGrad, vanilla MTAN and Sross-Stitch (Misra et al., 2016). Following (Maninis et al., 2019 Liu et al.] 2021a] Navon et al.] (022)). we use the per-task performance drop of metric Sm for method A with respect to baseline as a measure of the overall performance of a given method, which is given by Am= 1 > (-1)6m (SA.m SB... 3/53,m. where M is the number of tasks, SR.m. and S.,.m M7
are the values of metric Sm obtained by the baseline and the compared method respectively. Here, lm =1 if higher values for S., are better and O otherwise.
The results of the experiments are shown in Table and 2 Our method, MoCo, outperforms all the existing MTL algorithms in terms of Am for both Cityscapes and NYU-v2 datasets. Since our method focuses on gradient correction, our method can also be applied on top of existing gradient-based MOO methods. Additional experiments regarding this are provided in Appendix K
5.2 REINFORCEMENT LEARNING
For the multi-task reinforcement learning setting, we use the multi-task reinforcement learning bench- mark MT10 available in the Met-world environment (Yu et al. 2020b). We follow the experimental setup used in (Liu et al. (2221a) and provide the empirical comparison between our MoCo method and the existing baselines. Specifically, we use MTRL codebase (Sodhani & Zhang 202I) and use soft actor-critic (SAC) (Haamooa et al., (018) as the underlying reinforcement learning algorithm. Due to space limitation, the experiment results in a multi-task reinforcement learning setting and details of hyperparameter selection are provided in Appendix K

---

Published as a conference paper at ICLR 2023
REFERENCES
Vijay Badrinarayanan, Alex Kendall, and Roberto Cipolla. Segnet: A deep convolutional encoder- decoder architecture for image segmentation. IEEE Trans. Pattern Anal. Machine Intell., 39(12): 2481-2495, 2017.
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization Methods for Large-Scale Machine Learning. SIAM Review, 60(2), 2018
Tianyi Chen, Yuejiao Sun, and Wotao Yin. Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problems. In Proc. Advances in Neural Info. Prucess. Syst., virtual, December 2021.
Tianyi Chen, Yuejiao Sun, Quan Xiao, and Wotao Yin. A single-timescale method for stochastic bilevel optimization. Proc. of International Conference on Artificial Intelligence and Statistics, virtual, 2022.
Zhao Chen, Vijay Badrinarayanan, Chen- Yu Lee, and Andrew Rabinovich. Gradnorm: Gradient normalization for adaptive loss balancing in deep multitask networks. In Proc. of International Conference on Machine Learning, virtual, July 2018.
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. In Proc. Advances in Neural Info. Process. Syst., virtual. December 2020.
Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Scharwächter, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele. The cityscapes dataset. In CVPR Workshop on the Future of Datasets in Vision, Boston, MA, June 2015.
Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and TAMT Meyarivan. A fast and elitist multiob- jective genetic algorithm: Nsga-ii. IEEE transactions on evolutionary computation, 6(2):182-197 197, 2002.
Asen I.. Dontchev and R. Tyrrell Rockafellar. Implicit Functions and Solution Mappings. Springer, 2009.
Jean-Antoine Désidéri. Multiple-gradien Descent Algorithm (MGDA) for Multi-objective Optimiza- tion. Comptes Rendus Mathematique, 350(5-6), 2012.
Chris Fifty, Ehsan Amid, Zhe Zhao, Tianhe Yu, Rohan Anil, and Chelsea Finn. Efficiently identifying task groupings for multi-task learning. Advances in Neural Information Processing Systems, 34, 2021.
Jörg Fliege, A Ismael F Vaz, and Luís Nunes Vicente. Complexity of Gradient Descent for Multi- objective Optimization. Optimization Methods and Software, 34(5):949-95) 2019.
Saeed Ghadimi and Mengdi Wang. Approximation Methods for Bi-level Programming. arXiv 1reprint:1802.022446 2018
Dibya Ghosh, Avi Singh, Aravind Rajeswaran. Vikash Kumar, and Sergey Levine. Divide-and- conquer reinforcement learning. arXiv preprint:1711.098777 2017.
Daniel Golovin and Qiuyi Zhang. Random hypervolume scalarizations for provable multi-objective black box optimization. arXiv preprint arXiv:2006.04665 2020.
Xiang Gu, Xi Yu, Jian Sun, Zongben Xu, et al. Adversarial reweighting for partial domain adaptation. In Proc. Advances in Neural Info. Process. Syst., virtual, December 2021.
Michelle Guo, Albert Haque, De-An Huang, Serena Yeung, and Li Fei-Fei. Dynamic task priori- tization for multitask learning. In Proceedings of the European conference on computer vision, Munich, Germany, July 2018.
Tuomas Haarooja, 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, pp. 1861-1870, PMIR, 2018.
10

---

Published as a conference paper at ICLR 2023
Kazuma Hashimoto, Caiming Xiong, Yoshimasa Tsuruoka, and Richard Socher. A Joint Many-task Model: Growing a Neural Network for Multiple NLP Tasks. arXiv preprin::1611.01588,, 2016.
Geoffrey Hinton, Oriol Vinyals, Jeff Dean, et al. Distilling the knowledge in neural network. arXiv preprint:1503.0233 02531, 2015.
Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A Two-Timescale Frame- work for Bilevel Optimization: Complexity Analysis and Application Actor-Critic. arXiv nreprint:207.055170 2020.
Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In Proc. of International Conference on Machine Learning, virtual, 2021.
A Kendall, Y Gal, and R Cipolla. Multi-task learning using uncertainty to weigh losses for scene geometry and semantics. arXiv prppiin::705.0711 2017.
Joshua Knowles. Parego: A hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems. IEEE Transactions on Evolutionary Computation, 10(1): 50-66, 2006.
Mina Konakovic Lukovic, Yunsheng Tian, and Wojeiech Matusik. Diversity-guiee multi-objective bayesian optimization with batch evaluations. Advances in Neural Information Processing Systems, 33:17708-17720, 2020.
Vijaymohan Konda and Vivek Borkar. Actor-critic-lype learning algorithms for markov decision processes. SIAM Journal on Control and Optimization, 38(1):94-122) 1999.
Jayash Koshal, Angelia Nedić, and Uday Shanbhag. Multiuser optimization: Distributed algorithms and error analysis. SIAM Journal on Optimization, 21(3):1046-0081, 2011.
Panagiotis Kyriakis, Jyotirmoy Deshmukh, and Paul Bogdan. Pareto policy adaptation. In Interna- fional Conference on Learning Representations, 2021.
Baijiong Lin and Yu Zhang. preprint:2203.143.. 2022.
LibMTL:: A Python Library for Multi-Task Learning. arXiv
Xi Lin, Hui-Ling Zhen, Zhenhua Li, Qing-Fu Zhang, and Sam Kwong, Pareto multi-task learning. In Proc. Advances in Neural Info. Process. Syst. Vancouver, Canada, December 2019.
Xi Lin, Zhiyuan Yang, and Qingfu Zhang. Pareto learning for neural multi-objective combinatorial optimization. arXiv preprint arXiv:2203.15886 2022.
Bo Liu, Xingchao Liu, Xiaojie Jin, Peter Stone, and Qiang Liu. Conffict-Averse Gradient Descent for Multi-task Learning. In Proc. Advances in Neural Info. Process. Syst., virtual, December 2021a.
Liyang Liu, Yi Li, Zhanghui Kuang, J Xue, Yimin Chen, Wenming Yang, Qingmin Liao, and Wayne Zhang. Towards impartial multi-task learning. In Proc. of International Conference on Learning Representations, virtual, May 2021b.
Risheng Liu, Pan Mu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A generic first-order algorithmic framework for bi-level programming beyond lower-level singleton. In Proc. of International Conference on Machine Learning, pp. 6305-6315, 2020.
Shikun Liu, Edward Johns, and Andrew Davison. End-to-end multi-task learning with attention. In Proc. of IEEE Conference on Computer Vision and Pattern Recognition, Long Beach, CA, June 2019.
Suyun Liu and Luis Nunes Vicente. The Stochastic Multi-gradient Algorithm for Multi-objective Ooptimization and its Application to Supervised Machine Learning. Annals of Operations Research, pp. 1-30, 2021.
Xingchao Liu, Xin Tong, and Qiang Liu. Profiling Pareto Front With Multi Mojtt--Ojeective Stein Variational Gradient Descent. In Proc. Advances in Neural Info. Process. Syst., virtual, December 2021c
11

---

Published as a conference paper at ICLR 2023
Debabrata Mahapatra and Vaibhav Rajan, Exact pareto optimal search for multi-tass learning: Touring the pareto front. arXiv http:/in:t100000559977 2021.
Kevis-Kokites Maninis, Lljaa Radosavovic, and Iasonas Kokkinos, Attentive single-tasking of multiple tasks. In Proc. of IEEE Conference Computer Vision and Pattern Recognition, Long Beach, CA, June 2019.
Elliot Meyerson and Risto Mikkulainen. The traveling observer model: Multi-task learning through spatial variable embeddings. arXiv preprint 2Xiv:20000002354 2020.
Ishan Misra, Abhinav Shrivastava, Abhinav Gupta, and Martial Hebert. Cross-stitch networks for multi-task learning. In Proc. of IEEE Conference on Computer Vision and Pattern Recognition, Las Vegas, NV, June 2016.
Michinari Momma, Chaosheng Dong, and Jia Liu. A multi-objective/mulittakkkk learning framework induced by pareto stationarity. International Conference on Machine Learning, pp. 15895-159077
PMLR, 2022.
Aviv Navon, Aviv Shamsian, Ethan Fetaya, and Gal Chechik. Learning the pareto front with hypemetworks. In Proc. of International Conference on Learning Representations, virtual, April 2020.
Aviv Navon, Aviv Shamsian, Idan Achituve, Haggai Maron, Kenji Kawaguchi, Gal Chechik, and Ethan Fetaya. Multi-Task Learning as a Bargaining Game. arXiv preprint:2202.00007 2022.
Emilio Parisotto, Jimmy Lei Ba, and Ruslan Salakhutdinov. Actor-mimic: Deep multitask and transfer reinforcement learning. arXiv preprint: 151 150.1113111....1 2015.
Clemens Rosenbaum, Tim Klinger, and Matthew Riemer. Routing networks: Adaptive selection of non-linear functions for multi-task learning. arXiv preprint:
2017.
Sebastian Ruder. An overview of multi-task learning in deep neural networks. arXiv
preprint: 1w0.:::::70000000000 2017.
Andrei A Rusu. Sergio Gomez Colmenarejo, Caglar Gulcehre, Guillaume Desjardins, James Kirk- patrick, Razvan Pascanu, Volodymyr Mnih, Koray Kavukeuoglu, and Raia Hadsell. Policy distillation. arXiv preprint: /5| 1.06295, 2015.
Kate Saenko, Brian Kulis, Mario Fritz, and Trevor Darrell. Adapting visual category models to new domains. In European conference on computer vision, Crete, Greece, September 2010.
Ozan Sener and Vladlen Koltun. Multi-task learning as multi-objective optimization. In Proc. Advances in Neural Info. Process. Syst., Montreal, Canada, December 2018.
Jia Shi, Jinchun Song. Bin Song, and Wen F Lu. Multi-objective Optimization Design through Machine Learning for Drop-on-demane Bioprinting. Engineering, 5(3):586-593, 2019.
Nathan Silberman, Derek Hoiem, Pushmeet Kohli, and Rob Fergus. Indoor segmentation and support inference from rgbd images. In European conference computer vision, Firenze, Italy, October 2012.
Shagun Sodhani and Amy Zhang. Mtrl multi task algorithms. Github, 2021. URL https
Yee Teh, Victor Bapst, Wojciech M Czarnecki, John Quan, James Kirkpatrick, Raia Hadsell, Nicolas Heess, and Razvan Pascanu. Distral: Robust multitask reinforcement learning. Proc. Advances in Neural Info. Process. Syst., December 2017.
Philip S Thomas, Joelle Pineau, Romain Laroche, al. Multi-objective spibb: Seldonian offline policy improvement with safety constraints in finite mdps. In Proc. Advances in Neural Info. Process. Syst., virtual, December 2021.
Simon Vandenhende, Stamatios Georgoulis, Wouter Van Gansbeke, Mare Proesmans, Dengxin Dai, and Lue Van Gool. Multi-task learning for dense prediction tasks: A survey. IEEE Trans. Pattern Anal. Machine Intell. 2021.
12

---

Published as a conference paper at ICLR 2023
Hemanth Venkateswara, Jose Eusebio, Shayok Chakraborty, and Sethuraman Panchanathan. Deep hashing network for unsupervised domain adaptation. In Proc. of IEEE Conference on Computer Vision and Pattern Recognition, Honolulu, Hawaii, July 2017.
Haoxiang Wang, Han Zhao, and Bo Li. Bridging multi-task learning and meta-learning: Towards efficient training and effective adaptation. In International Conference on Machine Learning, pp. 10991-11002. PMLR, 2021.
Junfeng Wen, Saurabh Kumar, Ramki Gummadi, and Dale Schuurmans. Characterizing the gap between actor-critic and policy gradient. In Proc. of Internaiional Conference Machine Learning, virtual, July 2021.
Ruihan Yang. Huazhe Xu, Yi Wu, and Xiaolong Wang. Multi-task reinforcement learning with soft modularization. In Proc. Advances in Neural Info. Process. Syst., virtual, December 2020.
Yijun Yang. Jing Jiang. Tianyi Zhou, Jie Ma, and Yuhui Shi. Pareto policy pool for model-based offline reinforcement learning. In International Conference on Learning Representations, 2021.
Feiyang Ye, Baijiong Lin, Zhixiong Yue, Pengxin Guo, Qiao Xiao, and Yu Zhang. Multi-objective meta learning. Proc. Advances in Neural Info. Process. Syst. virtual, December 2021.
Junyu You, William Ampomah, and Qian Sun. Development and Application of a Machine Learning Based Multi- Optimization Workflow for CO2-EOR Projects. Fuel, 264: 16758, 2020.
Tianhe Yu, Saurabh Kumar, Abhishek Gupta, Sergey Levine, Karol Hausman, and Chelsea Finn. Gradient surgery for multi-task learning. In Proc. Advances in Neural Info. Process. Syst., virtual, December 2020a.
Tianhe Yu, Deirdre Quillen, Zhampeng 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, Virtual, November 2020b.
Yu Zhang and Qiang Yang. A survey on multi-task learning. IEEE Trans. Knowledge Data Eng., 2021.
Yiyang Zhao, Linnan Wang, Kevin Yang, Tianjun Zhang. Tian Guo, and Yuandong Tian. Multi- objective optimization by learning space partitions. arXiv preprint arXiv:2110.03173, 2021.
Shiji Zhou, Wenpeng Zhang, Jiyan Jiang, Wenliang Zhong, GU Jinjie, and Wenwu Zhu. On the convergence stochastic multi-objective gradient manipulation and beyond. In Proc. Advances in Neural Info. Process. Syst., New Orleans, December 2022.
13

---

Published as a conference paper at ICLR 2023
A
NOTATIONS
In this section we summarize the notations used in the paper and a corresponding brief description.
Notation
Description
Decision variable model parameter
Some random variable independent Feasible set of æ
N
M
Number objectives in the MOO problem
fm (x)
An objective such that fm. X' + R, where m E 21,
F(x)
Vector of functions containing f (1)), (2(x), J...........M such that F: X' RR
(F))
Jacobian of F(x), wich has V (x)),, V/2(2)............. V..........
Vfr (2r (r) as columns
RM
Positive othant cone of dimension M
AM
M dimensional probability simplex
M dimensional vector of ones
A
An element of A M
(x)
A solution to the problem (original MGDA subproblem)
(xx)
A solution to the problem (SMG subproblem)
(x)
The unique solution to the problem (8) (&2 regularized sub-problem)
d(x)
MGDA mult-gradient given by (36)
Model parameter at iteration k. updated as 10
ham
Stochastic gradient estimator of V V (xx)
Ukmm
"Tracking" variable that approximates (z
Y
Matrix containing yk.11 2k. V... as columns, updated as 6
dR
Estimate for X (2x),, updated (9)
Ork Bk,
Learning rates of 3,. and A updates, respectively Eg regularization parameter used (8)
P
Extension to bi-level optimization setting
Lower level parameter where E Rd
Im
Lower level objective such that fm Some random variable independent of 2, Minimizer (m (x, 22 with respect to z for any x E
IR, where m 2 M}
zi (z)
2k.m
Approximation of 2m (zx), updated equation 13
22 4m z)
Hessian of (x, =) w.r.t. to z
Stochastic approximation of V 20 (JR, 2k,m)
k.m
Table 3: Some important notations used in the paper
B ADDITIONAL RELATED WORK
In this section provide brief discussion additional work related to MTL and MOO. We first discuss closely related concurrent work Zhoo et al. (2022), which was not available at the time of submission of this paper. In Zhou al. (2022), the authors introduce unified framework for stochastic gradient-basse based MOO algorithms. Similar to MoCo, the proposed algorithm in Zhou et al. techniques reduce the multi-gradient bias. The key algorithmic
(2022) also uses momentum- difference of the aforementioned method compared to MoCo is that MoCo uses momentum- saaeenttum-bseed moving
correction on the full gradient estimation while Zhou et al. (2022) uses the momentum- averaging for convex combination coefficients À computed using stochastic gradients. As a conse- quence of this difference, it not clear if the averaged weight À obtained in Zhou et al.) (2022) will ensure convergence of the stochastic MOO update direction to any deterministic MOO direction. the other hand, in our work, we can show the convergence to MGDA direction in Lemma 2 In terms of theoretical results in Zhou et al. (2022), the authors provide convergence guarantees of the proposed algorithm for both convex and non-convex cases with convergence rates similar to that of single objective stochastic gradient descent (SGD). However, in order to obtain these results, (Zouu iet al. (2022) requires additional assumptions on bound of the function values, which is not required in standard single objective SGD convergence analysis. On the other hand, in this work, the convergence
14

---

Published as a conference paper at ICLR 2023
guarantees presented in Theorems 1 and 2 based on fairly standard assumptions in optimization literature, and does not assume any bound on the function value. Furthermore, the results are based the stochastic gradient bias which facilitates bi-level MOO. In addition,
on weaker assumptions we provide improved convergence results for MoCo Theorems X and A with stronger assumptions on function value bounds similar those in Zhou et al. (2022). but still with weaker assumptions the bias of stochastic gradients.
In addition to gradient based MOO which is the main focus of this paper, there also exist non gradient based blackbox MOO algorithms such as (Deb et al.] 2002 Golovin & Zhhagg, 2020; Knowles, 2006 Konakovic Lukovic al., 2020), which are based on an evolutionary algorithm or Bayesian optimization. However, these methods often suffer from the curse of dimensionality, and may not be feasible large scale MOO problems.
On the other hand, recent works in MTL have analyzed MTL from different viewpoints. In (Wang al. 202T), the authors explore the connection between gradient based meta learning and MTL. In Yee et al., (02I), the meta learning problem with multiple objectives in the upper levels has been tackled via a gradient based MOO approach. The importance of task grouping in MTL is analysed in works such as (Fifty et al., 2021). In (Meyerson & Mükkullinen 2020), the authors show that seemingly unrelated tasks can be used for MTL.
C SUMMARY OF COMPARISON WITH CLOSELY RELATED PRIOR WORK
Lipschitz continuity of X (x+)
Bounded functions
Biased gradient
Sample complexity
Method
Batch size
Non-convex
SMG
O
(c-g)
X
x
x
o (c-*)
(Thoorem I)
MoCo
((1)
X
x
X
0
O (c- 10)
Theorem
MoCo
0(1)
x
X
(c-19)
(Thcorem
3r
MoCo
0(1)
X
O (c-255)
(Thcorem
MoCo
0(1)
X
O (3)
O (c
(Theorem
Table 4: Comparison of MoCo with prior work on gradient based stochastic MOO, stochastic multi- gradient method (SMG)(Liu Vicente 202T]. Here the "Batch size" column represents the number of samples used at each (outer level) iteration, "Non-convex" column denotes whether the analysis is valid for non-convex functions, "Lipschitz continuity of X (xx)" column denotes whether Lipschitz continuity of X (z) (see Remark with respect to denotes whether boundedness of function values was assumed, "Biased gradients" column denotes bias in the stochastic gradient of ofunctions allowed in analysis, and "Sample complexity" column provides the (outer level) sample complexity of the corresponding method.
assumed, "Bounded functions" column
D ALGORITHM FOR MoCo WITH INEXACT GRADIENT
In this section we provide the omitted pseudo-code for MoCo with inexact gradients described in Section 3.2. As remarked in Section 3.2 this algorithm can relate to the actor critic setting with multiple critics. In Appendix K. we provide empirical evaluations of multi-task reinforcement learning using soft actor critic.
E PROOF OF LEMMA
Throughout the section, we write [[[]FF]] as E&[-] for conciseness. Consider the following conditions
(a) For any X, Im (m (I,) strongly convex w.r.t. with modulus pln 0.
15

---

Published as a conference paper at ICLR 2023
Algorithm 2 MoCo with inexact gradient
Input Initial model parameter z0, tracking parameters (Vo.)) lower level parameter
( convex combination coefficient parameter A and their respective learning rates
{ax 1 and (-
2:
for k k= =0...... K do
3:
for objective m = 1, 1,..., M do
4:
Update 2m+1.m following (33)
5:
Obtain 1k.m following [4]
6: Update yk++1mm following
6
7:
end for
8: Update A6+1 and 2k+1 following 9
10
9:
end for
Output 27 TK
(b) There exist constants Luz les, such that Valm (z, 2) is Lay Lipschitz continuous w.r.t. x; V 7m (z, 2) is L continuous w.r.t 2. Vaslm (r, 2), V vestm (I, 2) are respectively la Lipschitz and 1,2 -ipsscitzz continuous w.I.. (z,
(c) There exist constants ( fa, I f= le such that Vafm 2) and V fmmm( z) are respectively l and f Lipschitz continuous w.r.t. 2; V= 2) is 12 Lipschitz continuous w.r.t. 2; fm (x, =) is I--Lisscchizz continuous w.r.t. 2.
(d) There exist constants CH and 0h such that H [V =kmm)l S
CHa /3 and | k. 1 S THt- There exist constants Ca, Cazy Cz Ci such that V (Ik: km 1I
I CR, zellV (xx, 2k,m: Aill S Cz.-
V (xD Zk.m )l? < C² and Es 5m 2, (P))l < CCP.
The above conditions standard in the literature (Ghadimi & Wang 2018). In particular, condition (d) on H can be guaranteed by Ghadiii & Wang 2018 Algorithm 3). With these conditions, we first give restatement of Lemmal
Lemma 3 (Restatement of Lemma D. Consider the sequences generated by (13 16) 19 and (10).
Under conditions
if we choose the step sizes as those of Lemma we have for any m that
E E
FR)
fmm(xa)) 0
K
(20)
K
There exists a constant do such that
Blllaam B.hk.mm Fill S o..
(21)
Proof. We first prove 21 with
Eg hamm E& [h 11
Bellhemm
ER (hk. 12= Eullfu.mm 1|2
< 2E, V (m 2k.m, Ex) + 2E, [I| V2 2 I'm (Fx, 2h m: [1
| 1 (Zgg 2k,m Ex) [2]
< 2C 202, C.O
(22)
where the last inequality follows from item (d) along with the independence of 2 1m (2t, 2k, ('r.) Ha and V 2m (Ik: 2k.m (x) given Fi.
Next we start to prove (20).
[+(hemm Valm (Kt,, 2kmm)
V2 2 I' (Ik, Zk.m Ex [H ( 2k.m).
(23)
16

---

Published as a conference paper at ICLR 2023
In the following proof, write 2k,m (2x) am. The above inequality along with (2) implies
ER ma - (xx))ll
fmfmma kk. VzJmm (Ik mm
V ( mn B k,m V =mmmm (I kk.m) V Ve (Ikk 2k 22 mm, (..m)lll V= (T 2 at.m))
I as Imaa 2k,m) IV 22 (I kk, )] - V ( kk. Vizlm 2k [V Ve mm (ot, kk V a fm (2 kkmm)
2m (1r) II + Ls [B k,ml V Vashm (Ziks 2k 11
Tunale 31= (zzlzl=2 ||zk, zm (ax))l
(24)
pm
where the last inequality follows from conditions
(a)
The inequality 24 implies
[[Ex(hu,m) - (m < 2L 2
zamm (Joks zk.m))
$12 )
Lustz
lyalebee
211z
11
zin (2rx)
pm
pm
ax
Losss
1/2
$ 22 1.CH
+
+211fx
Zyn
(3r2
8k
Um
pm
(25)
where the last inequality follows from condition (d) the quality of Hmm suffices to prove K Σk E ml
Thus to prove 20),
next.
The convergence of 2k.m. We start with
|| 1m 112 =| - mal? + 2(2++1,
=k 26.m - 2241m + 2
1. 11?
(26)
The first term is bounded
Eg = 2k 2
Exll 3% V 2 (IN, m, (pk) - ma
|| 2k 2Bx (2km kk V. Zm (2),, mk,)) + B 2/ (2k, mk. (Px)ll
S (1 2pmm 3k. )) =I m 112 O7 Bt
(27)
where the last inequality follows from condition and (d)
Under conditions (a) (c), it is shown that there exists a constant Iz,m such that 2% (x) is Iez.m lipschitz continuous (Ghadimi & Wang 2Lmmm 2.2 (b)). Let L maxm La,ms then the second term in 26 can be bounded as
(c).
m 2k.m 1mm) < L=11zk41.m zh.mlllax - Dbtill
< L, L..Cgaxllztt. - 2h.mll
Mm 3x
=m 1
122C2p pm 3x
a (28)
where Cy sup ||Yx|| supzex VF(2)]] < co (by Assumption I or and projection), and the last inequality uses the Young 's inequality.
The last term in 26 is bounded
1| *++1ml 25 L.
(29)
Substituting 27
into 266 yields
12C2 a + 1.
Ex 2 1,m
1. 12 < pm 3m 3r)) - =k +
C7
Be
(30)
17

---

Published as a conference paper at ICLR 2023
Taking total expectation both sides, and then telescoping implies that (set a₁ OKK BK, Vk)
1
K
( (0005))+0((n) +00 +0
E 2k.m - zk 1|2 = O K3K
(31)
K
K
The last inequality along with the step size choice Lemma implies that
El
2p.m 112 O
R
(32)
K
which along with
25
implies
20
This completes the proof.
F PROOF OF LEMMA
2
Before we present the main proof, we first introduce the Lemmas 4 and 5 which are direct conse-
quences of (Dontchev & Rockafellar 2009 Theorem 2F.7) and (Koshal 2011 respectively.
Lemma A.I),
Lemma 4. Under Assumption there exists a constant LA p= Em= Lm such that the
following inequality holds
(1)(()) - X1(20)11 (xIVVF(())) VV((')11
(33)
which further indicates
112)(x) - X)('')1 S Lx,Fll
(34)
Σ Lm ( Lm,11
where L, = =-p1L, with L
Lemma 5, For any 0 and X, we have
< IV
(1 ((
P
1
(35)
2 M
Now start prove Lemma 2
Proof. Throughout the following proof, we write B[|]Fx] as [x{[]] for conciseness. With d(zx)
(( (Ir),, have
[[d(x)) - Y
[VFF(z)) - VF(TN)A -F -FF (AN - -
3| V S <
31))),((M))) - YEARl1
it suffices to show (F( - -
- (a) - Yx]) - - Aael2
(36)
From (36). to prove Lemma 2
diminishes,
and establish the convergence of Y₁, and di-
Bounding (F( - V Fx)((()))) Denoting X (xx) as Ao and (3(x2)) as 2 we first
consider the following bound
[|V((**)) VF(*))
|VF |
VF(2)))
< -1 0
(37)
2'
where the first inequality is due to the optimality condition
(A, VF(Iz) (.F(x))TVF(ee) VF(=x)) 2 (Ai, VF(zz) (F(2))))) VF(a))VVF(.))))
|VF(2)>>;11
for any À E AM and the last inequality is due to Lemma 5 With the choice of ((K -b) as
required by Theorems and we have
|V (Fx
If o(K-b).
(38)
18

---

Published as a conference paper at ICLR 2023
Convergence of Yk. With E3 mm = El [ix,, we start by
Ex Eglly++1.m Im 111+
F 11 Vm (Fx)) + 20 Vfm(( Vm (xx) - Vm (xx++)))
E& V fm (TA) - V fm (xx+1))11
(39)
We bound the first term in 39 as
Ex 11
V fm (=x))
3x (yk.m mmmmm) - VV [[m((<))l
1lyke,
Vm (Ix) - 2/k (ykkm V Sm (Ix)) yk.m Ex m) + PR 1ly.,. hk.m 11
Ily
V (xx))2 2,k (yrum V fm (Ix): Mk.m Vm (=m()
2,3% (ykk,m (mm())) f. Ex [hx, 1) + 3B 1ykk. hm
< (1 2-33))) 1Byk) V ( (1 + 2.x I/ - Vm (xx) V fmxx)) En [u + S8 11u.,
hkmm 11?
$ (1 Blyk.mm - (x+))))) + && fm - Ex mll + S lukk m 1|2
(40)
where the last inequality follows from young's inequality. Now, consider the last term of (40). Selecting 3u such that 3,3% = /2, and Assumption 3 we have
Bl - ml
= -BRExllUKm V + V fm (I&) E& [4x,m]] + Ex mm m 11?
S 3,9g Il
V. (xxx
2 + 3 V Im (3xx) - Ex [Mv.. 111 =. [hr,m]] ha. ||
Bk I1
(xx()))) + 3 V fm (.x) - mm 11? + 1:
(41)
2
Then, plugging in in (40). we obtain
E 3k+1m
fm (xx)) 12 $ (1
3x 1lyk.. 2 Fm En mm
2
+ 355 V (mx) - E& Ex 111 + 3t.
(42)
The second term in 39 can be bounded as
( 1,m (mx),, V Jm (2xR V Sm
11 fm (xx) v (m
T.m 18++1m - V. (3x) ||| sxll
< Lm, Gyaullyn++,m v (xx))l
$ Be Ael1 - Vmm )12 2T.2.. C2 a
Br
ak Br.
5 Bxllys++.m (xx)))) +2L,0
(43)
where the second last inequality follows from young's inequality, and the last inequality follows from the definition L1 = maxm Lmm.1-
The last term in 39 can be bounded as
(zx) (mm(+++)) -7] zvil² < L.Caaj.
(44)
Collecting the upper bounds in
and substituting them into 39 gives
Eg l1. V. (= < (1 7 Bu)lu - fmm (8x + 3,5 fm (26) - Ex [h 11l
+0 3 o8 13C301 + 4I303 of
(45)
3x
19

---

Published as a conference paper at ICLR 2023
Suppose ag and By constants. Taking total expectation and then telescoping both sides of (45)
gives
K
1
1
1
Blyyk.m
Vfm(x))) O(
+
0
E
fm - [bk,,m111)
K
K3KK"
K
k=1
+((3) + 0
(46)
3%
Along with the choice of step sizes as required by Theorems 1 and 2 and due to Assumption last inequality gives
3 the
K
Elyyk,m (=m(m)))2===0)
(47)
which, based on the definitions
Y3 and VF(x)), implies that
BI VF(x))1== -0om))?20((MM) (MK
(48)
K
Convergence Ag. We write (1xx) in short as X in the following proof. We start by
|| X/ ||R+1 N2 + 2(Ax-1 Yak Nork AbN++)) + 11 1o.+11 112 (49)
The first term is bounded as
| - 22 ||[TaM (Ax - 7/k (Y Yn & + +pl) Aι)) -2
S || 7hk (Yr Yn + pl) d - X/.111
|| X7.0l12 27 (Ax Xxp (Y 1v. p1) 2x) (Y,
(Y,TY,Y Ys + pl) Anl1
< || 29 - n (Ax X2, (Yx T Yv + pl) Ax) + (0++
(50)
Consider the second term in the last inequality:
(Ax Xo,e0 (Yx Yn + pl) Au)
= (AA - N (YTY, Yvc VF((x) (FF))))F(())))))) (Ax - Aa,s -X;.;; (VF(T)) + pT) dx)
2 -20 111x VF(x=)] + (Ax - -op.k
VF((+)) + pl) (A+ xp,x0)
(Au Xp. (VF(*)) VF(Ix) + pl) X2,b)
2 2C,, A - -xp, 111y VF(x))] + pll No.
2 2C 11 VF(xx)]1 + 11 - X;,11
(51)
where the second last inequality follows from the optimality condition that
(Ax N (VF(*)) F((*)) pT) x 2 0,
and the last inequality in follows from the Young's 's inequality.
Plugging in (5T) back (50p gives
| - >; = - p - 1; + 4C, V VF(x))]1 + (C, + p)2 (52)
With Lemma 4 the second term (49) can be bounded as
(Ae+1 2o 25. - 2g S LA.ellAH11 - 11 - Ik+1ll
s LAr.Crarll 22
< mullde+ - 22al2² 13 C2 at
ppp
(53)
7k
20

---

Published as a conference paper at ICLR 2023
where the last inequality is due to Young's inequality. The last term in (49) is bounded
1 N/x++ll
(54)
Substituting
52
54
into
49
yields
| x 11?
I
P 7h |1 - x2xl1 402p 111 VF(x)) +Og
p)
+ 2L C2. -2 + C3
(55)
7k
Suppose okk Pk. and " constants given K. Taking total expectation, rearranging and taking telescoping sum on both sides of the last inequality gives
A1 A. -
-
+0 (xLT))
- (Kmm)
1 pk
E E
VF(xx)]1
+0
Tkk
P
of
+0
(56)
7xpp
where we have used Lx,F = -(+)) from Lemma 4 Then, plugging the choices oę O i))
3g = O(K )), 7h O(K- 3), p O(K- 3) and substituting from 48) (56) gives
-(K=)),
K
1
Σ
BIA x OMK do + K
(57)
K
Since typically the number of objectives is very small compared to the number of iterations, under assumption = 2), we get
Σ
BIA
(58)
K
Thus, from
36
38
48
and
58
we have
K
1
YxAp OKK-b).
(59)
K
This completes the proof.
G PROOF OF THEOREM
Proof. We first have
||x4+1 - x= 1|2 x (I - Oggya (x - x
< | Ork Yk> - =12
|| x= 1|2 -20x (24 x², Y.AA)) + +Y
< || x²1 2 2ora (Ztx x", F.,VF(()))) - 200 - =²,, YEAE VF(Ex) + a2c
< | x=1 2 20x (F(#x) F(x")) -2x (ax x", YadR VF(I + a2
(60)
where the last inequality uses the convexity of fm (V)).
Cauchy-Schwarz The third term in 660 can be bounded using the Cauchy- Schwarz inequality as + + 1
(Ix x² YEAE v F(xx)
CC VF(x+)I + CyllA
(61)
where Cz is the upper bound of || x' for x' E X, which follows from Assumption
21

---

Published as a conference paper at ICLR 2023
Substituting the above inequality into 660 and rearranging gives
(F((())) F(x")) S (11:rx- x 11 | -=11 + Cx(lIVa - VF(xx)] + Cyllde x2
20r
C
V (2( + okk.
(62)
Taking telescope sum the last inequality gives
(F((a))) - F(x)))
K
[ xx' 12
C2 K
C
(1
+Gl1 12 + +IVFF(=)))) - +
2Kax
K
2
k=1
(63)
which along with 38 48
and (58) indicates K Σ ElA - ((())))-((('))) if
choose Or O to ), 3x O (eKK-- )), 7 O 3), - and p O (K-
-
H PROOF OF THEOREM
Before we go into the main proof, we first show the following key lemma.
Lemma 6. For any x E X and
A M, with d(x) = (x))))((x), it holds that (d(z), VF |[((z)]13
(64)
Proof. We write (x) (=(x)) in the following proof. Since AM is convex set, for any X' E M we have a(X' - X²) + X M for any a E [0, 1]. Then by d(x) = arg minxeaM (x))1
we have
|d(=)]]² [|a(dx d(x))( [()) =(x)))
(65)
Expanding the right hand side of the inequality gives
(=]) - d(z))l + (d(x)) dx (x) d(x))) 2 0.
(66)
Since this needs to hold for arbitrarily close to 0, we have
(d(x), (x) d(x)) 2 0, VMEA
(67)
which indicates the result inequality by rearranging.
Now we can prove Theorem 2
Proof. By the Tmm1 -m.o-shmttsnsss of fm: we have for any m,
fm (xu+1) S fm (xx) + au (m)(())) YYnd)) + Lm.1 1 1x+11 =x2l
< fm)()) au V (zz), YAAd)) + Lm,1 C Caa..
(68)
The second term in the last inequality can be bounded as
[m)()))) -Yndu)
= -Vfm(II), VF(TN)AE YoAe) + (VWN))))
< Im (I|Yr - VF(IN)) + CyllA |VF VF(L + (x)) (V) -VF(
Lm (I|Y= VF(xw)) + CcllAA -22all IVF -VF - (69)
22

---

Published as a conference paper at ICLR 2023
where the last inequality follows from Lemma 6 by letting VF(xx)A= (z)( and the first inequality follows from
(V (m (2( YEAR)
Lm [F((=)) - Yeddll
Lm VF YEAE + + VF(Ix))
Lm (I V (z(x)) C2yl Av 1 IVVF(>>)) x
(70)
Plugging 669
into 68
taking expectation on both sides and rearranging yields
V Em (#x) fm (xx+ Li cus (B VF(xx)] Cy Nall
Lm,1 Cz
[F - VF +
(71)
2
Taking telescope sum on both sides of the last inequality gives
VF
0gK (fm(11) inf fmn()) + I' [ VF(xx)) C,
1%.all
A=1
[VF (F(TR)A Lm.1 C Cjax
(72)
which along with (38. (48 and indicates 1 Ex= B Aall (KK-1) if we choose
Og = OKK 3x @(K 7h = O(K -+), and p= (Kk-))
I PROOF OF THEOREM 3
Proof. Recall from 68 by the Lmooshmoothness of fm. we have for any
+ fm(()))) s (xx) + au (V (xx), -Y - + Lmn.1
Cgaz.
(73)
Multiplying both sides by X and summing over all E [M]] we obtain
L1 Cg
L
F(IE+1)A I F(xx)A+ + a (VF(I=)A.. - -Ydaa)
(74)
, ,M1 T and L, = maxm Lm, We can bound the where we have used Au = (2 x second term of (74)
(VF(w)))s
Yudn) = (VF(*)), VF(x)) V Ys)
S -VF + |VF(T + (VF(z)) YAIl
= /VF + IVF((=)) Y21l.
(75)
where the first inequality due to Cauchy-Schward and Young's inequalities. Substituting 75 in (74) and rearranging, have
LI
/VF(x))elll S F(xx)A - F( + Okk
Ok [[[(((x))) 12 + oi
a
(76)
2
2
Given K. let agg, 3% and be constants for any & E [K]. We then take total expectation on both sides and sum over iterations obtain
Olk
E
Σ E [[Fxa)A F(s OAk
VFF(x)
Yall
Li
(77)
23

---

Published as a conference paper at ICLR 2023
We bound the first term on the right-hand side of the inequality (77
K
{F - F(ox+1)da1=B =
F(oR+1)(A6+1 - Ao) F(z - F(IK+1)ds
E
P(==-illAAR++ +1 + [I((xx+))llAA
K-1 1 2F
F
(K - 1)7kk + 2F,
(78)
where the first inequality due to Cauchy-Schward the second inequality due to the bounds on F(xx), A and we have used the update for A for all l E [K] with p 0, and third inequality is due
to the bound on YE for all & E [K]. Substituting (78) in 77) and dividing both sides by a we have
K
V
< 2FF
(K
1)
7h
4F +
+
1
K
VF
E
- Yxll + Lia
K
K
ag
ayK
K
1=1
k=1
(79)
which, along with (46) and choosing Cg = (OK-KK))) 8, = 0 -33
and 7h = O(K-1), we obtain
8). The result then follows by observing that for any E [K], we have
(80)
K
[VF((=)) 2 min [/ = |VF(x=))211
(81)
X
J IMPROVED CONVERGENCE RATE WITH MODIFIED ASSUMPTIONS
In this section we state and prove Theorem which improves upon the results presented in Theorem 3 with modified assumptions. We will first state the modified assumptions.
Assumption 4. For any m, there exist constants Cyc Fm such that * Ek= Eh FFl < (mxx)))
6m3x and B -am--Ba El FR] S 2 for any k.
Similar to Assumption 3 Assumption requires the stochastic gradient hamm almost unbiased and has bounded variance, and this is also weaker than the standard unbiased stochastic gradient assumption. Furthermore, Assumption 4 can be satisfied by rumning multiple nested updates, which require additional lower-level samples. With this assumption, we present the following improved result.
Theorem 4. Consider the sequences generated by Algorithm 7 Furthermore assume there exists constant F > 0 such that for all E [K]. [xx)) < F. Then, under Assumptions 7 Lndd 4 if we choose slep sizes 0 = O(K }), Bs = O(K=)) )), 7h = O(K-(KK))) and O, it holds that
K
1
E [IVF( (IW)I =O
(82)
Proof. Convergence of Yg. We begin the proof by revisiting the convergence analysis on Y₁ in the proof of Theorem under the assumptions considered in Theorem For convenience, we restate
(39h here as
Eg 1 Vfm
E& 11 (mx)))) (2 - (f
- V/ (2
(83)
24

---

Published as a conference paper at ICLR 2023
We bound the first term in 83 similar to that in 42
= (1 } 3/) l1 (2x))) 3x1 fm)))
V (mx)ll
E& [h). 11
2
+ 3/2 V Vfm(ax) Ex(ha, m| 112 30
(84)
The second term in 83 can be bounded as
(yn+ 1,m
V Fm (1x) V (m(++1))
< 1
V
V fmm zæll
m,, yk+11m Vm
Lm, 100 11
V (
3 3e Bel1yx+1,m - (=x)) +2
|
K Bellut+1,m - (=x)) +203
O Bx
1?
(85)
where the third inequality is due the 2h update, the second last inequality follows from young's incquality, and the last inequality follows from the definition L1 = maxm Lmm.1
The last term in (83 can be bounded as
(m)))
S -+ - - S Li
(86)
Collecting the upper bounds in 84 86 and substituting them into (83) gives
ExIly++1,m fm (1 Bu)lum V.m(E (9x + 35 fm
Ex She
11
3o B + 4 o Bx ||
(87)
For all k. let or ag, Bx 3k. and 7k = 7k be constants given K. Then, taking total expectation and then telescoping both sides of (87
gives
E Elyyk.m - v 0 K3KK'
+0 1 K
Σ
E
(xx)
E& (mx.1)l11))))
K
+ O(xx) +
[
+
4
E
(88)
BK
8
K
k=1
Summing the last inequality over all objectives m E [M], and using Assumption
we obtain
K
0 M ) + +(M33))+ (MLãak + 4ML
Bliy
VF(xx)12
Y 12
K
K3x
8K
K
1=1
(89)
M
where we have used
1kkkm
Vfm(2x))12 2 I| VF(xx)11 Then with the decomposition
m=
(90)
we can arrive at
K
VF(x))1 0 M ) + +(M33))+ + 22M + -8M.
K
B|y2 -
ak
E
F
K
K3x
BK
K
k=1
K
2 2M + SM 1i1
B| vF(xa)11
911)
3xx
K
k=1
Now, note that with the choice of stepsize o'k S 4L/M 3K, << 3x 1, and ar and 3x are on
the same time scale, there exist some constant 0 < C1
< 1 and valid choice of 3x such that the
25

---

Published as a conference paper at ICLR 2023
following inequality holds
2M - -811, oK 2 C1.
(92)
3x
An example for constant that satisfy the last inequality for aforementioned choice of ox and Bx is C1 4' Then, from 91 and (92). we can arrive at
K K
M K3K
(2MT) C1
8MI, 0
K
VF 0(
+O(MBK)
a +
VF(
C1
Bx
K
R=1
(93)
Next, we analyse the sequence. For this purpose, we follow along similar lines as in the proof of Theorem Accordingly, from (68). we have for any m,
(I(+ s (mx) or (m)(()) - -EAs) + Lm..1
Cga
(94)
Multiplying both sides by X and summing over all m E [M]] we obtain
L
F(F++1) ) S Fx + a (VF(T))A (ada) Cga
(95)
and L1 = max, Lmn We can bound the where we have used A == (X b....... Ap ,..,,,,))) A second term of (95) as
(V (VF(x)) AE, YnAR) (VF(T)) - VF(CNMA + VF(TN)A - YEAR)
S -IIV (VF(LL)AR VF(E)) - Y&Ax)
I -IIVFFFT))AN 2 [V 2 1/2 [VF(x)) Yu
1 VF(E+) VF Yull.
(96)
2
where the second inequality is due to Cauchy-Schward and Young's inequalities, and the last inequality is due to bound on λp. Substituting 966) in (95) and rearranging, we have
L
ak VF(xx)A F(Tx)A F( 2
a& 2 VF(zk) Y= c2
(97)
For all k. let ag αg. 8x 8K. and nh = 7K be constants given K. We then take total expectation on both sides and sum over iterations to obtain
< Σ B(F(aa)d - F(#2+1)dd) + aK K B[ - Yu1l + L
OK
"5 Koy
2
(98)
We bound the first term on the right-hand side of the inequality
(98) as
K
KK-
B[F(#a)A - F(R =
F(ZR+)) - Ao) F(x1) - F(IK+1)A
E
F MIC-AA ||F(+))III + [[
K-1
l YRAR +2F
S FC Σ
Y +F,
(99)
where the first inequality is due to Cauchy-Schwatzz the second inequality is due to the bounds on F(xx), ) A and we have used the update for 2 for all [K] with p = and third inequality is due to the bound on Yg for all & E [K].
26

---

Published as a conference paper at ICLR 2023
Substituting (99 in 98)
and dividing both sides by ag have
K
K
$ 2FC y
1k Σ
E
YRARl
+ +FF
akK +
1
1
VF(())
Yall + LiaxCr
K
K
K
22F 02
OKK
2
KK
4K
ER 12 + 4F
OKK K
+
K
B B( - Yull + LIak
k=1
k=1
K
221 0
7K
3
Σ
((((()))) 1 +
E
E + ox + Lraxx C2
oKK
2K
2K
k=1
k=1
-0 1K
+ 00
M
)
+(M33)) + +
1 O(ax)
ak
K3K
KkK
L.
12M
o
K
+
2 +
E
(100)
C1
C1
BK]
K
k=
where the last equality is by substituting from
993 Now, with a similar argument that we made in
22)
given some C1, there exist some constant 0
< C2 < 1 such that
3ML. 2 12M a
2
C1
OK
C1 3x 2 C2-
(101)
Feasible choices of C1, C2 would be === = C2 = 4. Then, we can have
K
2
M
E EI = 0
K
+
0
+ 0(M3k) + OC OKK
+ O(ax).
(102)
KKK
2
KBK
By choosing ag = O(K (O(K+),, 3x = O(K 7), = O(K- we arrive at
F OO(K- 5). E
(103)
K
The result then follows by observing that for any & E [K]. we have
[V 2 min [F(x))11] [VF(zx))111
(104)
11
K DETAILS OF EXPERIMENTS
In this section, we describe the omitted details of experiments in the main paper.
K. TOY EXAMPLE
To show the advantages of our algorithm, example consists of optimizing two objectives fi (x) and f2(#) with x = (Ii, 22
toy example similar to (Liu al. 202 The
E 124 given by
fi(z) = Pı (x) + (z)))
fz(z) = p1)) (z)))
where we define
91 (x) = log (00.5 max (-x1 - 7) - lanbi(=22), + 6,
(2(2) log (00.5 max ( x1 -7) - tanh(-22)) + 0.00000)) + 6,
max
rx()) = ((-2) + 7) + 0.1 (-11 - -8)²) /10 20, r2(x) ((-21 - -7) 0.1 (-12 - -8)2) /10 20,
Pi (1))) max (tanh (0.522) 0) P2(x)) max (tanh (-0.5x2), 0).
27

---

Published as a conference paper at ICLR 2023
SMG Increasing batch size
102
MoCo (curs)
Muttigredleet error
k.
10-1
10-1
10 Iterations
10
10'
Iterations
Iterations
100
10a
Mutt-gradient eror
10a
10
10-1
10-1
10
10
10
10
10
10
100
10
10
10 Samples
10f
102
109
10
10
10
10
107
Samples
Samples
(a) Trajectory I
(b) Trajectory
(c) Trajectory
Figure 3: Comparison of multi multi-gradient enror
Generation of Figure
L For generating the trajectories in Figure we initializations
Ty {(-8.5, 7.5), ( (-8.5, 5), (1),--8);
and run each algorithm for 70000 iterations. For all the algorithms, we use the initial learning rate of 0.001, exponentially decaying at a rate of 0.05. In this example for MoCo, we use 3x 5..5 where & is the number of iterations.
Generation of Figure [] For the comparison of MOO algorithms in objective space depicted in Figure 2
we use initializations
To E ((-8.5, 7.5), (-8.5, 5), (10, -8,, (0, 0), (9,9)).
The optimization configurations for each algorithm is similar to that of the aforementioned trajectory example, except with initial learning rate of 0.0025.
Comparison with SMG with growing batch size. For the comparison of the multi-gradient bias among SMG, SMG with increasingly large batch size, and MoCo, we use the norm of the error of the stochastic multi-gradien
calculated using the three trajectories randomly initialized from To E ((-8.5, 7.5), (-8.5, 5), (10. -8). ). For calculating the bias of the multi-gradient, we compute multi-gradient using 10 sets gradient samples at each point of the trajectory, take the average and record the norm of the difference between the computed average and true multi-gradient. All three methods are run for 70000 iterations, and follow the same optimization configuration used for Figure 2 For SMG with increasing batch size, we increase the number of samples in the minibatch used for estimating the gradient by one every 10000 iterations. We report the bias of the multi-gradien with respect the number of iterations and also number of samples in Figure 3 In the figure, Trajectories 1, 2, and 3 correspond to initializations (-8.5, 7.5), (-8.5, 5), and (10, -8), respectively. It can be seen that our method performs comparable SMG with increasing batch size, but with fewer samples. Furthermore, SMG has non-decaying bias in some trajectories.
K.2 SUPERVISED LEARNING
In this section provide additional details and experiments Cityscapes and NYU-v2 datasets, and also provide experiment results on two additional datasets Office-31 and Office-home. Each experiment consists of solving multiple supervised learning problems related to each dataset. We
28

---

Published as a conference paper at ICLR 2023
Upin les.
0.07
0.7
0.6
0.5
0.0
04
0.03
0.3
0.02
081
100
(a) Semantic loss
(b) Depth loss
Figure 4: Training and test loss for the Cityscapes tasks
2.0
tran Inst
1.0
8
1.2
6.7
www. Muturah
Suffac namnal
0.25
1.00
0.75
0.5
0.20
0.35
0.3
100 Epochs
125
150
1/5
25
90
15
-00
125
150
175
200
0.30
25
100
1/b
150
1/5
2001
Epocis
(a) Semantic loss
(b) Depth loss
(c) Surface normal loss
Figure 5: Training and test loss for the NYU-v2 tasks
consider each such task objective, which then can be simultancously optimized by gradient based MOO algorithm. We describe details on formulating each task as an objective next.
Problem formulation. First we look into the problem formulation of NYU-v2 and Cityscapes experiments. For NYU-v2 dataset, 3 tasks are involved: pixel-wise 13-class classification, pixel-wise depth estimation, and pixel-wise surface normal estimation. In Cityscapes experiments, there 2 tasks involved: pixel-wise 7-class classification and pixel-wise depth estimation. The following problem formulation applies for both NYU-v2 and Cityscapes tasks, excpet for the surface normal estimation task which only relates to NYU-v2 dataset. Let the set of images be {U} pixel-wise class labels be (Ti J.N 1 pixel-wise depth values be [ and pixel-wise surface normal values be [ where is the number of training data samples. Let æ be the model that we train to perform all the tasks simultaneously. Let the image dimension be P x Q. We will use Tm for ground truth and 7,, for the corresponding prediction by the model x, where m [M] and M is the number of tasks. We can now formulate the corresponding objective for each task, as given in (Liu et al.) 2019). The objective for pixel-wise classification pixel-wise cross-entropy, which is given
fx NPQ
Σ TT. log (p. 3.p.q
where i E [M], p E [P], and q E [Q]. Similarly, we can have the objectives for pixel-wise depth estimation and surface normal estimation, respectively,
fz(x)) PPQ
1
Σ [T,(p, q) TT, g)l and fa(z) NPQ
ΣT.(p..)) - (p.
1,9.9
8,p.9
where is the elementwise dot product. With these objectives, we can formulate the problem ( for Cityscapes and NYU-v2 tasks, with Ja only used in the latter.
Similar to NYU-v2 and Cityscapes experiments, we can also formulate the supervised learning tasks on Office-31 1 and Office-home MTL as instance of problem
Cityscapes dataset. For implementing evaluation Cityscapes dataset, we follow the experiment set up used in (Liu et al.) 202 All the MTL algorithms considered are trained using SegNet (Badrinarayanan et al. 2017) model with attention mechanism MTAN @Lu et al. (019) applied on top of it for different tasks. Áll the MTL methods in comparison are trained for 200 epochs, using
batch size of We use Adam as the optimizer with learning rate of 0.0001 for the first 100 epochs,
and with learning rate of 0.00005 for the rest of the epochs. Following (Liu al. 2021a) for each
29

---

Published as a conference paper at ICLR 2023
Segmentation (Higher Better)
Depth
Method
(Lower Better)
Am% 4
mloU
Pix Acc
Abs Err
Rel Err
Independent
74.01
93.16
0.0125
27.77
PCGrad Yu et al.
2020a
75.13
93.48
0.0154
42.07
18.29
CAGrad
(Liu et al.
2021a)
75.16
93.48
0.0141
37.60
11.64
MoCo (ours)
75.42
93.55
0.0149
34.19
9.90
PCGrad + MoCo
75.49
93.62
0.0146
46.07
20.07
CAGrad + MoCo
75.07
93.39
0.0137
36.78
10.12
Table 5: MoCo with existing gradient manipulation MTL algorithms for Cityscapes dataset tasks.
Results are averaged over 3 independent runs.
Segmetation
Depth
Surface Normal
Method
(Higher Better)
(Lower Better)
Angle Distance
Within t (Higher better)
Am%
(Lower Better)
mloU
Pix Acc
Abs Err
Rel Err
Mean
Median
11.25
22.5
Independent
38.30
63.76
0.6754
0,2780
25.01
19.21
30.14
57.20 69.15
PCGrad et al.
2020a
38.06
64.64
0,5550
0,2325
27.41
22.80
23.86
49.83
63.14
3.97
CAGrad
Liu et al.
a02
39.79
65.49
0,5486
0.2250
26.31
21.58
25.61
52.36
65.58
0.20
MoCo (ours)
40,30
66.07
0,5575
0,2135
26.67
21.83
25.61
51.78
64.85
0.16
PCGrad MoCo
38.80
65.02
0,5492
0.2326
27.39
22.75
23.64
49.89
63.21
3.62
CAGrad MoCo
39.58
65.49
0,5535
0.2292
25.97
20.86
26.84
53.79
66.65
-0.97
Table 6: MoCo with existing gradient manipulation MTL algorithms for NYU-v2 dataset tasks. Results averaged over 3 independent runs.
method in comparison we report the average test performance of the model over last 10 epochs, averaged over 3 seeds. For implementing MoCo in Cityscapes dataset we use 8% = 0.05/k0.3 7kk 0.1/k105 where l is the iteration number. For the projection simplex in the A update, we use a softmax function. The training and test loss curves for semantic segmentation and depth estimation are shown in Figures 4a and an respecteivv
NYU-v2 dataset. For NYU-v2 dataset, we follow the same setup as Cityscapes dataset, except with a batch size of For implementing MoCo in NYU-v2 experiments, we use 8g = 0.99, 7 0.1 with gradient normalization followed by weighting each gradient with corresponding task loss. This normalization was applied to avoid biasing towards one task, as can be seen the case for MGDA. For the projection to simplex in the A update in MoCo, we apply softmax function to the update, to improve computational efficiency. The training and test loss curves for semantic segmentation, depth estimation, and surface normal estimation for NYU-v2 dataset and [cc respectively.. It can be seen that the model start to slightly overfit to the training data set with respect to the semantic loss after the 100th epoch. However this did not significantly harm the test performance in terms of accuracy compared to the other algorithms.
shown in Figures 55 5b
MoCo with existing MTL algorithms We apply the gradient correction introduced in MoCo on top of existing MTL algorithms to further improve the performance. Specifically, we apply the gradient correction of MoCo for PCGrad and CAGrad on Cityscapes and NYU-v2. For the gradient correction (update step (6) in PCGrad we use 8. 0.99 for both Cityscapes and NYU-v2 datasets, and for that in CAGrad we use B4 0.99 for Cityscapes dataset and Ar 0.99/ / for NYU-v2 dataset. The results are shown in Tables 5 and [6 for Cityscapes and NYU-v2 datasets, respectively. We restate the results for independent task performance and original MTL algorithm performance for reference. It can be seen that the gradient correction improves the performance of the algorithm which only use stochastic gradients. For PCGrad where no explicit convex combination coefficient computation for gradients is involved, there is an improvement of Am% for NYU-v2 by 0.35%. For Cityscapes, it can be seen a slight degradation in terms of Am% in exchange for improvement in 3 out of 4 performance metrics. This can be expected PCGrad does not explicitly control the
30

---

Published as a conference paper at ICLR 2023
Domain
Method
Am%
Amazon
DSLR
Webcam
Mean
84.22
94.81
97.04
MGDA
79.60
96.45
97.96
0.94
PCGrad
84,10
95.08
96.30
0.21
GradDrop
84.73
96.17
96.85
-0.61
CAGrad
84.22
94.26
97.41
0.07
MoCo (ours)
84.33
97.54
98.33
-1.45
Table 7: Results Office-31 dataset. We show the 31-class classification results over 3 domains Office-31 data set. The results are obtained from the epoch with the best validation performance.
Domain
Method
Am%
Art
Clipart
Product
Real-Worth
Mean
63.88
77.90
89.55
79.39
MGDA
63.63
73.78
90.18
79.82
1.11
PCGrad
63.06
77.46
89.09
78.70
0.81
GradDrop 63.82
78.22
89.19
78.88
0.18
CAGrad
63.06
77.03
89.62
79.53
0.54
MoCo (ours)
63.38
79.41
90.25
78.70
-0.27
Table 8: Multi-task learning results on Office-Home dataset. We show the 65-class classification results over 4 domains on Office-Home data set. For each method the results are obtained from the epoch with the best validation performance.
converging point be closer the average loss. For CAGrad which explicitly computes dynamic convex combination coefficients for gradients using stochastic gradients such that it converges closer to a point that perform well in terms of average task loss, there is an improvement of Am% for Cityscapes by 1.52% and that for NYU-v2 by 1.17%. This suggests that incorporating the gradient correction of MoCo in existing gradient based MTL algorithms also boosts their performance.
In addition to the experiments described above, we demonstrate the performance of MoCo in compar- ison with other MTI. algorithms using Office-31 (Saenko et al. 2010) and Office-home Venkateswara et al. 2017) datasets. Both of these datasets consist of images of several classes belonging to dif- ferent domains. We use the method "Mean" as the baseline for Am*%, instead of independent task performance. The Mean baseline is the method where the average of task losses on each domain used as the single objective optimization problem. For reporting per domain performance for all the methods compared in Office- 13 and Office-home experiments, the test performance at the epoch with highest average validation accuracy (across domains) is used for each independent run. This performance measure is then averaged over three independent runs.
Office-31 dataset. The dataset consists three classification tasks on 4,110 images collected from three domains: Amazon, DSLR, and Webcam, where each domain has 31 object categories. For implementing experiments using Office-home and Office-31 datasets, we use the experiment setup and implementation given by LibMTL framework (Lin & Zhang (022). The MTL algorithms are implemented using hard parameter sharing architecture, with ResNet 8 backbone. As per the implementation in (Lin & Zhang] 2022), 60% of the total dataset is used for training, 20% for validation, and the rest 20% for testing. All methods in comparison are run for 100 epochs. For MoCo implementation, we use 3g = /2..5 and ? = 0. 0.1/k... We report the test performance of best performing model based on validation accuracy after each epoch, averaged over 3 seeds. The results are given in Table 7 It can be seen that MoCo significantly outperforms other methods in most taks, and also in terms of Am%.
Office-home dataset. This dataset consists of four classification tasks over 15,500 labeled images on four domains; Art: paintings, sketches and/or artistic depictions, Clipart: clipart images, Product: images without background and Real- World: regular images captured with a camera. Each domain has 65 object categories. We follow the same experiment setup Office-31, and for MoCo imple-
31

---

Published as a conference paper at ICLR 2023
Train
button press
door open
drawer close
drawer open
peg insert side
pick place
push
reach
window open window close
Figure 6: Metaworld MT10 benchmark tasks Yuu et al. 2020b).
mentation, 8 0.5/k'. and 7 0.1/k The results are given in Table It can be seen that MoCo significantly outperforms other methods most taks, and also terms Am7
Method
success (mean + stderr)
Multi-task SAC
0.49 0.073
Multi-task SAC Task Encoder
0.54 0.047
Multi-hcaded SAC
0.61 + 0.036
PCGrad
0.72 + 0.022
CAGrad
0.83 + 0.045
MoCo (ours)
0.75 1 0.050
CAGrad MoCo (ours)
0.86 + 0.022
One SAC agent per task (upper bound)
0.90 1 0.032
Table 9: Multi-tase reinforcement learning results on MT10 Metworld benchmark.
K.3 REINFORCEMENT LEARNING
For the multi-task reinforcement learning setting, we use the multi-task reinforcement learning benchmark MT10 available in Met-world environment (Yu al., 2020b). Figure 6 illustrates the 10 tasks associated with MTI0 benchmark. We follow the experimental setup used in (Liu et al.) 2021a) and provide the empirical comparison between our MoCo method and the existing baselines. Specifically, we use MTRL codebase (Sodhani & Zhang 2021) and use soft actor-critic (SAC) (Haarnoja
2018) as the underlying reinforcement learning algorithm. All the methods are trained for 2 million steps with batch size of 1280. Each method is evaluated once every 10000 steps and the highest average test performance of a method over 5 random seeds over the entire training stage is reported in Table 9 In this experiment, the vanilla MoCo outperforms PCGrad, but its performance is not as good as CAGrad that optimizes the average performance of all tasks. We further run the gradient correction of MoCo top of CAGrad, and the resultant algorithm outperforms the vanilla CAGrad. This suggests that incorporating the gradient correction of MoCo in existing gradient based MTT. algorithms also boosts their performance.
Table 10 summarizes the hyper-parametee parameters choices used for MoCo each the experiments.
Cityscapes
NYU-v2
Office-31
Office-home
MT10
optimizer of 2
Adam
Adam
Adam
Adam
Adam
Ie stepsize (cx))
0.0001
0.0001
0.0001
0.0001
0.0003
Ya stepsize (3x)
0.05/k
0.99
0.5/k
0.5/k
0.99
Au stepsize (yx.)
0.1/
0.1
0.1/k0.
0.1/k0.5
10
batch size
2
64
64
1280
training epochs
200
200
100
100
2x 10 steps
Table 10: Summary of hyper-parameter choices for MoCo in each experiment
32


Reviews:
[{"review_id": "t5yj8WWnNA", "reviewer": "Reviewer_49fc", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "", "summary_of_the_paper": "This paper studies how to mitigate the gradient bias of multiobjective learning. They use the idea of momentum-based gradient bias correction to substitute the gradient when finding the common gradient.\n\nI have had some earlier attempts on this problem but didn't end up very successful and I am very excited that someone also works on this problem. However, I find some potential mistakes in a very core Lemma (Lemma 4) used in this paper and thus I doubt the correctness of the result in this paper.", "summary_of_the_review": "My main concern is the correct of a core Lemma. My current rating is mainly due to that issue if this can be addressed during the rebuttal period, I am happy to raise the score to 6 or 8. If it can't be addressed, this paper is not ready to publish.", "strength_and_weaknesses": "Strength:\nThis is an open and important problem in MOO.\n\nQuestions:\n\nI am *pretty* unsure about the correctness of Lemma 4 which indicates the Lipschitz continuity of the lambda. Dontchev & Rockafellar, 2009, Theorem 2F7 does not imply this Lemma.\n\nUsing the notation in Dontchev & Rockafellar, 2009, Theorem 2F7, that result holds locally (given $x$, we have a $\\mu$) but when we approach the Pareto stationary point ($x$ changes), that $\\mu$ might change and we cannot have a global bound of the $\\mu$. In other words, the Lipschitz constant of $\\lambda$ should actually increase (to infinite) when we are closer to the stationary.\n\nThe lambda can be viewed as a solution map of a dual problem of a quadratic programming problem and its Lipschitzness is a very classic problem. To my best knowledge, all of the existing estimations of the Lipschitz are local, not global. Some literatures [1,2,3]\n\n\n[1] On the continuity of the minimum in Parametric quadratic programs.\n[2] On the Lipschitz Behavior of Optimal Solutions in Parametric Problems of Quadratic Optimization and Linear Complementarity\n[3] Sufficient Conditions for the Lipschitz Continuity of QP-based Multi-Objective Control of Humanoid Robots", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "iRqjjOGxpB", "reviewer": "Reviewer_Hp6r", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "The author(s) studied the multi-objective optmization problem and proposed a new algorithm called MoCo that provably converges to a Pareto stationary point in the stochastic gradient setting. Experiments on both toy and real data are conducted to support the proposed method.", "summary_of_the_review": "Overall, this paper makes a decent contribution to the field; the author(s) give the first stochastic multi-gradient method can converges under mild conditions. I did not carefully check the proofs, the paper is above the bar of acceptence if other reviewers all agree that the proof is correct.", "strength_and_weaknesses": "Strengths:\n- The paper is well-motivated and well-written, the story line and analysis is easy to follow for experienced readers;\n- The MoCo algorithm proposed in this work is the fisrt stochastic multi-gradient method that can converge to Pareto stationary point under mild condition, which is a decent contribution to the field.\n\nWeakness:\n- I did not find any obvious weakness of the paper. The notation is a little bit heavy, maybe it is better to add a notation subsection.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "FyO6ruC5B3", "reviewer": "Reviewer_qnbb", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "", "summary_of_the_paper": "This paper studied the multi-objective optimization problem. Here, it reformulated it as a bilevel optimization problem and then leveraged the tools in bilevel optimization to establish the convergence rate. Since the main proof is adapted from bilevel optimization, the novelty is incremental. ", "summary_of_the_review": "This paper studied the multi-objective optimization problem. Here, it reformulated it as a bilevel optimization problem and then leveraged the tools in bilevel optimization to establish the convergence rate. Since the main proof is adapted from bilevel optimization, the novelty is good. ", "strength_and_weaknesses": "Strength:\n1. The problem studied is important.\n2. The writing is easy to follow. \n\nWeakness:\n1. It is not clear why multi-objective optimization problems should be formulated as bilevel optimization problems. This critical point should be discussed clearly. At present, it is a weird combination of those two problems. \n2. The theoretical analysis is mainly adapted from the bilevel optimization literature. This makes the contribution incremental. The authors should highlight the challenges and the different parts compared with existing bilevel optimization literature.\n3. This paper assumes that the loss function is Lipschitz continuous. With this strong assumption, existing bilevel optimization literature can achieve the convergence rate $O(K^{-1/2})$, which is much stronger than the convergence rate in this paper. \n4. In lemma 2, the number of objectives $M$ should depend on the number of iterations. This is definitely NOT feasible in real-world applications. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-5%