Direction-oriented Multi-objective Learning: Simple and Provable Stochastic Algorithms
Authors: Peiyao Xiao
Hao Ban
Kaiyi Ji
Venue: NeurIPS 2023 poster (2023)
Keywords: Multi-objective optimization
multi-task leaning
stochastic algorithms
convergence and complexity
Pareto stationarity

Abstract: Multi-objective optimization (MOO) has become an influential framework in many machine learning problems with multiple objectives such as learning with multiple criteria and multi-task learning (MTL). In this paper, we propose a new direction-oriented multi-objective formulation by regularizing the common descent direction within a neighborhood of a direction that optimizes a linear combination of objectives such as the average loss in MTL or a weighted loss that places higher emphasis on some tasks than the others. This formulation includes GD and MGDA as special cases, enjoys the direction-oriented benefit as in CAGrad, and facilitates the design of stochastic algorithms. To solve this problem, we propose Stochastic Direction-oriented Multi-objective Gradient descent (SDMGrad) with simple SGD type of updates, and its variant SDMGrad-OS with an efficient objective sampling. We develop a comprehensive convergence analysis for the proposed methods with different loop sizes and regularization coefficients. We show that both SDMGrad and SDMGrad-OS achieve improved sample complexities to find an $\epsilon$-accurate Pareto stationary point while achieving a small $\epsilon$-level distance toward a conflict-avoidant (CA) direction. For a constant-level CA distance, their sample complexities match the best known $\mathcal{O}(\epsilon^{-2})$ without bounded function value assumption. Extensive experiments show that our methods achieve competitive or improved performance compared to existing gradient manipulation approaches in a series of tasks on multi-task supervised learning and reinforcement learning. Code is available at https://github.com/ml-opt-lab/sdmgrad.

Direction-oriented Multi-objective Learning: Simple and Provable Stochastic Algorithms
Peiyao Xiao Hao Ban', Kaiyi Ji
Depaarment of CSE, University at Buffalo
2 Zuoyi Technology
katyoxiiaaiiiii]a11ai, (atp bhsimon0810@gmai com
Abstract
Multi-objective optimization (MOO) has become an influential framework in many machine learning problems with multiple objectives such as learning with multiple criteria and multi-task learning (MTL). In this paper, propose new direction-oriented multi-objective formulation by regularizing the common descent direction within neighborhood of direction that optimizes lin- car combination of objectives such as the average loss in MTL or a weighted loss that places higher emphasis some tasks than the others. This formu- lation includes GD) and MGDA as special cases, enjoys the direction-oriented benefit in CAGrad, and facilitates the design of stochastic algorithms. To solve this problem, we propose Stochastic Direction-oriented Multi-objective Gradient descent (SDMGrad) with simple SGD type of updates, and its vari- ant SDMGrad-OS with an efficient objective sampling. We develop a compre- hensive convergence analysis for the proposed methods with different loop sizes and regularization coefficients. We show that both SDMGrad and SDMGrad- OS achieve improved sample complexities find an e-accurate Pareto stationary point while achieving small e-level distance toward a conffict-vvidaant (CA) di- rection. For a constant-level CA distance, their sample complexities match the best known (c)-²) without bounded function value assumption. Extensive ex- periments show that our methods achieve competitive or improved performance compared to existing gradient manipulation approaches in series of tasks on multi-task supervised learning and reinforcement learning. Code is available https:://iiiieii com/mll moloptttpptpp ab/sdmgrad.
Introduction
In recent years, multi-objective optimization (MOO) has drawn intensive attention wide range of applications such online advertising (I., hydrocarbon production [2], autonomous driving (3) safe reinforcement learning [4]. etc. In this paper, we focus on the stochastic MOO problem, which
takes the formulation of
min L( = (R Bg(22(()) Ee(T=x mE
(1)
where is the parameter dimension, K > 2 the number of objectives and [,(0) = (0:
One important example of MOO in eq. (T) is the multi-task learning (MTL) 5 6., whose objective
First authors contributed equally.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Batch size
Bounded function value
Sample complexity
Algorithms
Nonconvex
CA distance
SMG 11
O(e-²)
X
X
O(e
N/A
CR-MOGM
((1)
/
O(e
N/A
MoCo R
((1)
/
/
O(e
N/A
MoDo 14
(())
/
X
O(e7))
O(1)
SDMGrad (Theorem
((1)
X
O(e
((1)
SDMGrad-OS (Theorem 4
((1)
X
O(e
o(1)
MoCo [3
((1)
X
((e-10)
((e)
MoDo 14
0(1)
V X
O(e*))
O(e)
SDMGrad (Corollary
((1)
X
(
O(c)
SDMGrad-OS (Theorem 2
((1)
X
O(e-)
(
Table I: Comparison of different algorithms for stochastic MOO problem achieve an 6-accurate
Pareto stationary point. MoDo 14
concurrent work. Definition of CA distance can be found in
Definition 2 (-)) omits logarithm factors.
function is often regarded as the average loss over K objectives.
(1()) & Σ (.))
8 arg min BER
where (0) is the loss function for task i. However, solving the MOO problem is challenging because can rarely find a common parameter that minimizes all individual objective functions simultaneously. As result, widely-adopted target is find the Pareto stationary point which there is no common descent direction for all objective functions. In this context, a variety of gra- dient manipulation methods have been proposed, including the multiple gradient descent algorithm (MGDA) 77. PCGrad [ CAGrad [9] and Nash-MTL [10]. Among them, MGDA updates the model parameter 0 using time-varying multi-gradient, which is a convex combination of gradients for all objectives. CAGrad further improves MGDA by imposing new constraint on the difference between the common descent direction and the average gradient ensure convergence the min- imum of the average loss of MTL. However, these approaches mainly focus on the deterministic case, and their stochastic versions still remain under-explored.
Stochastic MOO has not been well understood except for several attempts recently. Inspired by MGDA, 111 proposed stochastic multi-gradient (SMG), and established its convergence with con- vex objectives. However, their analysis requires the batch size to increase linearly. In the more practical nonconvex setting, [12] proposed correlation-redueed stochastic multi-objective gradient manipulation (CR-MOGM) to address the non-convergence issue of MGDA, CAGrad and PCGrad in the stochastic setting. However, their analysis requires a restrictive assumption the bounded function value. Toward this end, [33 recently proposed method named MoCo a stochastic counterpart of MGDA by introducing a tracking variable approximate the stochastic gradient. However, their analysis requires that the number T of iterations is big at an order of K 10 where K is the number of objectives, and hence may be unsuitable for the scenario with many objectives. Thus, it is highly demanding but still challenging to develop efficient stochastic MOO methods with guaranteed convergence the nonconvex setting under mild assumptions.
1.1 Our Contributions
Motivated by the limitations of existing methods, we propose Stochastic Direction-oriented Multi- objective Gradient descent (SDMGrad), which is easy implement, flexible with direction- oriented objective formulation, and achieves a better convergence performance under milder as- sumptions. Our specific contributions are summarized follows.
New direction-oriented formulation. We propose a new MOO objective (see eq. 66) by regu- larizing the common descent direction d within neighhorhood of direction dg that optimizes

---

linear combination (o( of objectives such as the average loss in MTL or weighted loss that places higher emphasis on some tasks than the others. This formulation is general include gra- dient descent (GD) and MGDA as special cases and takes similar dtrection-orienter spirit as in CAGrad 19] However, different from the objective in CAGrad [9] that enforces the gap between d and do to be small via constraint, our regularized objective is easier to design near-unbiased multi- gradient, which is crucial in developing provably convergent stochastic MOO algorithms.
New stochastic MOO algorithms. The proposed SDMGrad is simple with efficient stochastic gradient descent (SGI) type of updates the weights of individual objectives in the multi-gradient and on the model parameters with )unbiased (multi-)gradient approximations at each iteration. SDMGrad does not require either the linearly-growing batch sizes in SMG the extra tracking variable for gradient estimation as in MoCo. Moreover, we also propose SDMGrad-OS (which refers to SDMGrad with objective sampling) as an efficient and scalable counterpart of SDMGrad in the setting with large number of objectives. SDMGrad- -SS samples a subset of data points and objectives simultaneously in all updates and is particularly suitable large-scale MTL scenarios.
Convergence analysis and improved complexity. We provide comprehensive convergence anal- ysis of SDMGrad for stochastic MOO with smooth nonconvex objective functions. For a constant- level regularization parameter A (which covers the MGDA case), when an c-level conflict-avoidant (CA) distance (see Definition 2 is required, the sample complexities (i.e., the number of samples to achieve an e-accurate Pareto stationary point) of the proposed SDMGrad and SDMGrad-OS im- prove those of MoCo [3] and MoDo [4] by order of c1 and -2 (see Table I. respectively. In addition, when there is no requirement on CA distance, the sample complexities of SDMGrad and SDMGrad-OS are improved to O)e=)), matching the existing best result in the concurrent work [4]. For an increasing X, we also show this convergent point reduces to a stationary point of the linear combination Lo (0) of objectives.
Promising empirical performance. We conduct extensive experiments in multi-task supervised learning and reinforcement learning on multiple datasets and show that SDMGrad can achieve com- petitive or improved performance compared to existing state-of-the-art gradient manipulation meth- ods such MGDA, PCGrad, GradDrop. CAGrad, IMTL-G, MoCo, MoDo, Nash- Mash-MTL and FAMO, and can strike a better performance balance on different tasks. SDMGrad-ON also exhibits a much better efficiency than SDMGrad in the setting with a large number of tasks due to the efficient ob- jective sampling.
2 Related Works
Multi-task learning. One important application of MOO is MTL, whose target is learn multiple tasks with possible correlation simultancously. Due to this capability, MTL has received significant attention in various applications in computer vision, natural language process, robotics, and rein- 17. A group of studies have focused on how to design better MTL forcement learning [5] 15 16,
model architectures. For example, I& 19 20 enhance the MTL models by introducing task speciffc modules, an attention mechanism, and different activation functions for different tasks, respectively. Another line of research aims to learn a bunch of smaller models of local tasks split from the original problem, which are then aggregated into single model via knowledge distillation (2I). Recent sev- eral works [2 23 have explored the connection between MTI. and gradient- based meta-learning. (24] and [25] highlight the importance of task grouping and unrelated tasks in MTL, respectively. This paper focuses on a single model by learning multiple tasks simultancously with novel model- agnostic SDMGrad and SDMGrad-OS methods.
Gradient-based MOO. Various gradient manipulation methods have been developed to learn mul- tiple tasks simultancously. One popular class of approaches re-weight different objectives based on uncertainty 266. gradient norm [27]. and training difficulty (28). MOO-based approaches have re- ceived more attention due to their principled designs and training stability. For example, [6] viewed MTL as a MOO problem and proposed an MGDA-type method for optimization. A class of ap- proaches has been proposed to address the gradient conflict problem. Among them, [8] proposed PCGrad by projecting the gradient direction of each task on the norm plane of other tasks. Grad- Drop randomly dropped out highly conflicted gradients 22), and RotoGrad rotated task gradients to alleviate the conflict [30.- [ proposed CAGrad by constraining the common direction direction within a local region around the average gradient. These approaches mainly focus on the determin-
3

---

istic setting. In the stochastic case, 13 proposed MoCo as stochastic counterpart of MGDA, and provided comprehensive convergence and complexity analysis. More recently, concurrent work [44 analyzed three-way trade-off among optimization, generalization, and conflict avoidance, pro- viding an impact on designing the MOO algorithm. In addition, [3T] found that scalarization SGI) could be incapable of fully exploring the Pareto front compared with MGDA-variant methods. In this paper, we propose a new stochastic MOO method named SDMGrad, which benefits from a direction-oriented regularization and an improved convergence and complexity performance.
Concurrent work. A concurrent work [4] proposed a multi-objective approach named MoDo, which uses a similar double sampling strategy (see Section 4.2). However, there are still several differences between this work and [14]. First, our method benefits from a -rriente mech- anism and is general to include MGDA and CAGrad as special cases, whereas MoDo [14] does not have such features. Second, MoDo takes a single-loop structure, whereas our SDMGrad features a double-loop scheme with an improved sample complexity. Third, [14] focuses more on the trade-off among optimization, generalization and conflict-vvoidnce,, whereas our work focues more on the optimization efficiency and performance balance in theory and in experiments.
3 Preliminaries
3.1 Pareto Stationarity in MOO
Differently from single-objective optimization, MOO aims find points which all objectives cannot be further optimized. Consider two points 0 and 6'. It is claimed that A dominates 6' if (,)0) < (,()") for all i [K] and L(0) * L(0"). In the general nonconvex setting, MOO aims to find a Pareto stationary point 0, at which there is no common descent direction for all objectives. In other words, we say is a Pareto stationary point if range(VV.(0)) (-RK = where TR the positive orthant cone.
3.2 MGDA and Its Stochastic Variants
Deterministic MGDA. The deterministic MGDA algorithm was first studied by 77]. which updates
the model parameter 0 along multi-gradient d Σ w 90) G(O)w", where G(0) (g) (0), (0)) .... 9K (0)) are the gradients of different objectives, and w² == (wi, uz .... w
are the weights of different objectives obtained via solving the following problem.
" arg min [|] s.t. w E W = (w E R 1 = L, 2
(3)
20
where W the probability simplex. The deterministic MGDA and its variants such as PCGrad and CAGrad have been well studied, but their stochastic counterparts have not been understood well.
Stochastic MOO algorithms. SMG [1] is the first stochastic variant of MGDA by replacing the full gradient (()) in eq. (3) by its stochastic gradient G(0:E) == (g) (0: (). IK E)), and updates the model parameters along the direction given by
de = G(O:E)wg s.t. w E arg min || [[)(3:))=1..
However, this direct replacement can introduce biased multi cullti-gradent estimation, and hence SMG required increase the batch sizes linearly with the iteration number. To address this limitation, [13] proposed MoCo by introducing an additional tracking variable yt as the stochastic estimate of the gradient (O),,, which is iteratively updated via
1e+1,5 Hy. (ye, (e hr,:)), 1,2,... K;
where Br is the step size, Hl denotes the projection on bounded set 3/; = {y R [1yl| < Cg. for some constant Cy.i. and he, denotes stochastic estimator of (L) at t-th iteration. Then, MoCo was shown to achieve an asymptotically unbiased multi-gradient, but with a relatively strong assumption that the number 7 of iterations is much larger than the number K of objectives. Thus, important but still challenging to develop provable and easy-to-implement stochastic MOO algorithms with mild assumptions.

---

4
Our Method
We first provide new direction-oriented MOO problem, and then introduce a new stochastic MOO algorithm named SDMGrad and its variant SDMGrad-OS with objective sampling.
4.1
Direction-oriented Multi-objective Optimization
MOO generally targets at finding direction d to maximize the minimum decrease across all objec- tives via solving the following problem.
max min TER [E[K]
{
L,(0 - -L(0 x0 max min (g., d), dER" sE[K]
1,(0 -ad))
(5)
where the first-order Taylor approximation of L, is applied 0 with small stepsize
In some scenarios, the target is to not only find the above common descent direction but also optimize specific objective that is often a linear combination Lo(0) Σ; w; (0) for some ã E W of objectives. For instance, MTL often takes the averaged loss over tasks as the objective function, and every element in Φ will be set as -. In addition. it is quite possible that there is preference for tasks. In this case, motivated by the framework in 62]. we can regard w as preference vector and tend to approach preferred stationary point along this direction. To address this problem, propose the following multi- oulti--bjjective problem formulation by adding an inner-produce regularization X(gn. d) in eq. (5) such that the common descent direction d stays not far away from target direction go Σ; Wigs-
max min (gi: d) dER [E[K]
||dl] + Xggo d).
In the above eq. 6 the term | is used regularize the magnitude of the direction d and the constant X controls the distance between the update vector d and the target direction gu-
Compared to CAGrad. We note that CAGrad also takes direction-oriented objective but uses different constraint-enforred formulation as follows.
max min (gi, d) s.t. ||d - holl S c||/ool
deltm ie [K]
where ho is the average gradient and E [0, 1) is constant. To optimize eq. 7 CAGrad involves the evaluations of the product [ I.!l and the relation [holl with Iur E. wigs both of which To
complicate the designs of unbiased stochastic gradien//multi-rradeee comparison, our formulation in eq. (6) as shown later, admits very simple and provable stochastic algorithmic designs, while still enjoying the direction-oriented benefit in CAGrad.
the and 0 updates. As
To efficiently solve the problem in eq. 66) we then substitute the relation that min (g,, d) mingew EEK= gew;; d) min d) into eq. (6), and obtain an equivalent problem as
max min (gwr + Ago, d) dd d weW
By switching min and max in the above problem, which does not change the solution due to the concavity in d and the convexity w, we finally aim to solve min max (Sw + Ago d)
= ||]]] where the solution to the min problem on is
w E arg min WEW! 2 llo + Agoll?
(8)
and the solution to the max problem is d Iw3 + Ago-
Connection with MGDA and GD. It can be seen from eq. 8 that the updating direction d' reduces to that of MGDA whenwe set = 0, and is consistent with that of GD for large enough. This consistency is also validated empirically in Appendix A.2 by varying X.
5

---

4.2 Proposed SDMGrad Algorithm
The natural idea to solve the problem in eq. (8) is use simple SGD-type method. The detailed steps are provided in algorithm [ start initialization and with soouble-ammlligg-biee based stochastic gradient estimator, which is unbiased by noting that
At each iteration E, we run S steps of projected SGD with warm-
Eg.e (G(ri) (G(0)))
+ Ago(Or; G()) + (go()
where e, are sampled data and (o())) = G(0:) denotes the orientated direction. After obtaining the estimate we,s. SDMGrad updates the model parameters 9, based the stochastic counterpart G(0i; (),,, s + Ago (C): of the direction d' = 9w + Àgo with a stepsize of aạ- can be seen that SDMGrad is simple to implement with efficient SGD type of updates on both and 0 without introducing other auxiliary variables.
Algorithm Stochastic Direction-oriented Multi-ohjective Gradient descent (SDMGrad)
Initialize: model parameters 0g and weights w/o
2: for / 0, 1..,, T do
3: for 5 = 0, 1,.,, S 1 do
4: Set Wr.0 W1-1.5 (warm start) and sample data e,
5: Wt,a++1 Ill (Wi,a Br.a ()) ("(Oo;'')waa Auo(Or;E')))
6: end for
7: Sample data and 0.+1 02 aa(G((0;))), + (O)(
8: end for
4.3 SDMGrad with Objective Sampling (SDMGrad-OS)
Another advantage of SDMGrad is its simple extension via objective sampling to the more practical setting with large of objectives, c.g., in large-scale MTL. In this setting, we propose SDMGrad- OS by replacing the gradient matrix G(O,; E) in Algorithm by a matrix (0;;;) with randomly sampled columns, which takes the form of
H HO0,: E, = (O,,E)) (0)( (0:t)))
where (0;; ((: E) with a probability of n/ K or 0 otherwise, S corresponds to the ran- domness by objective sampling, and is the expected number of sampled objectives. Then, the stochastic gradient the update is adapted to
K2 n
(Gradient on w)
H( (H' S'))u,, Aho(OriE',
where ho(.) = H.)).. Similarly, the updating direction d= ".. H( 5) Wr,s + K Ahg In the practical implementation, lowing a Bernoulli distribution with length K and probability n/K, and then compute the gradient g0; E) of G(0:g) E) only if the 7th entry of s equals to This sampling strategy greatly speeds up the training with large number of objectives, shown by the reinforcement learning experiments in Section 6.3
n first use np. random. binomial to sample 0-1 sequence s fol-
Main results
5.1 Definitions and Assumptions
We first make some standard definitions and assumptions, also adopted by existing MOO stud- ies in [I] 12 13). Since we focus on the practical setting where the objectives are nonconvex,
algorithms are often expected to find an e-accurate Pareto stationary point, as defined below.
Definition 1. say TR. is an e-accurate Pareto stationary point Rf min Il (0)) S where W is the probability simplex.
MGDA-varian methods find direction d(0) (e.g., d= = Iwo + Ago with w given by eq. (8) that tends to optimize all objective functions simultaneously, which is called conflict-avoidat (CA)

---

direction [4]. Thus, it is important to measure the distance between stochastic direction estimate d(0) and the CA direction, which we call CA distance, defined below.
Definition 2. [| [d(+]] - d(()]l denotes the CA distance.
The following assumption imposes the Lipschitz continuity on the objectives and their gradients.
Assumption 1. For every task E [K], L2(0) is i, LL-psschiit continuous and (I) is , -ipschhitz continuous for any 0 E 1
We next make an assumption on the bias and variance of the stochastic gradient ();
Assumption 2. For every task i [K], the gradient 9: () is the unbiased estimate of (:))). Moreover, the gradient variance is bounded by (elllg:(f:E) - (0) S o².
Assumption 3. Assume there exists a constant Cg such that ||G(O)] S Cg.
The bounded gradient condition in Assumption necessary ensure the boundedness of the multi-gradien estimation error, as also adopted by 12 13
5.2 Convergence Analysis with Nonconvex Objectives
We first upper-bound the CA distance for our proposed method.
Proposition 1. Suppose Assumptions are satisfied. If we choose Br, = c/v3// and S > then
Re,,,,, (G(Or;))me (go { G(0,))o,, Ago(O:))l V/22 +(22))))
2
2+log(S) log(S)
vS
where C1 = O(K 2)) and is constant.
Proposition 1 shows that CA distance decreasing with the number S of iterations on updates. Then, by selecting a properly large S, we obtain the following general convergence result. are satisfied. Set at = @((1 +
Theorem (SDMGrad). Suppose Assumption
- 3.,e =c/ /s, where e is constant, and S @(11 A) 27)). Then the outputs of the proposed SDMGrad algorithm satisfy
Σ
((l))(t Ago(0.))) 5(( x
(10)
T
where ① omits the order log T.
Theorem D esttablises a general convergence guarantee for SDMGrad along the multi-gradient di- rection d' 9wt Ago- Building on Theorem we next show that with different choices of the regularization parameter two types of convergence results can be obtained in the following two corollaries.
Corollary (Constant A). Under the same setting in Theorem choosing constant-level X > 0. we have & ET- ([]]((0))w T where wi arg min (l( To achieve an c-accurate Pareto stationary point, each objective requires OKK3c-6) samples in & (E') and (2))2) samples in Ç, respectively. Meanwhile, the CA distance takes the order of ((e).
Corollary covers the MGDA case when À = 0. In this setting, the sample complexity (cc-6) improves those of MoCo [13] and MoDo [4] by an order of - and -2, respectively, while achieving an e-level CA distance.
Corollary (Increasing A). Under the same setting as in Theorem i and choosing X @(T we have Er- [[]lga((.))l O(K O(KåT - ). To achieve an e-accurate stationary point, each objective requires OKK2, samples in (E') and O (KK))) samples in Ç. respectively. Meanwhile, the CA distance takes the order of ((V K).
7

---

Corollary 2 analyzes the case with an increasing À = )(T'). We show that SDMGrad converges to stationary point the objective (0) Σ, W; (0) with an improved sample complexity, but with a worse constant-level CA distance. This justifies the flexibility of our framework that the À can balance the worst local improvement of individual objectives and the target objective (0)).
Convergence under objective sampling, We provide a convergence analysis for SDMGrad-OS.
Theorem 2 (SDMGrad-OS), Suppose Assumption | are satisfied. Define y n' at @([++ - Br.. c/ where c is a constant, and S = @ 2 2??).
Then, by choosing constant X, the iterates of the proposed SDMGrad OS algorithm satisfy
Σ
=
T
Theorem Theorem@estaaieee establishes the convergence guarantee for our SDMGrad-OS algorithm, which achieves per-objective sample complexity of (c) comparable to that of SDMGrad, but with much better efficiency due the objective sampling, as also validated by the empirical comparison in Table
5.3 Lower sample complexity but constant-level CA distance
Without the requirement on the e-level CA distance, we further improve the sample complexity of our method O(e 2), as shown in the following theorem.
Theorem 3. Suppose Assumptions are satisfied. Set S = 1, a2 = = θ(K- Be =
3 O(K-'T-T and X as constant. The iterates of the proposed SDMGrad satisfy
=
Theorem shows that to achieve e-accurate Pareto stationary point, method requires T OK? In this case, each objective requires a number ( of samples in E(g') and Ç.
Convergence under objective sampling. We next analyze the convergence of SDMGrad-OS.
Theorem 4. Suppose Assumptions
are satisfied. Set S
= K at = a
n,
- 1)) 8 3 O(K 'T à) and X constant. The iterates of the proposed SDMGrad OS algorithm satisfy
Theorem 4 shows that to achieve an e-accurate Pareto stationary point, our algorithm requires T ( 2 K2 2), and each objective requires number O(22 of samples E(E') and Ç.
Experiments
In this section, first describe the implementation details of our proposed methods. Then, demonstrate the effectiveness of the methods under a couple multi-task supervised learning and reinforcement settings. The experimental details and more empirical results such as the two- objective toy example, consistency with GD and MGDA, and ablation studies over À can found in the Appendix A
6.1 Practical Implementation
Double sampling. In supervised learning, double sampling (i.e., drawing two samples simultane- ously for gradient estimation) is employed, whereas in reinforcement learning, single sampling is used because double sampling requires to visit the entire episode twice a time, which is much more time-consuning.
Gradient normalization and rescale. During the training process, the gradient norms of tasks may change over time. Thus, directly solving the objective in eq. (8) may trigger numerical problems.

---

Inspired by CAGrad 19. we normalize the gradient of each task and rescale the final update d by multiplying a factor of I+X to stabilize the training.
Projected gradient descent. The computation of the projection to the probability simplex use is the Euclidean projection proposed by [33, which involves solving a convex problem via quadratic programming. The implementation used in experiments follows the repository in 34 which is
very efficient in practice.
Segmentation
Depth
Method
MR 1
Am% 4
mloU
Pix Acc
Abs Err
Rel Err
STL
74.01
93.16
0.0125
27.77
LS
75.18
93.49
0.0155
46.77
8,50
22.60
ST
70,95
91.73
0.0161
33.83
11.50
14.11
RLW
35
74.57
93.41
0,0158
47.79
11.25
24.38
DWA
36
75.24
93.52
0.0160
44.37
8.50
21.45
UW
26
72.02
92.85
0.0140
30.13
7.75
5.89
MGDA
F
68.84
91.54
0.0309
33.50
12,00
44.14
PCGrad 8
75.13
93.48
0.0154
42.07
8.75
18.29
Grop
75.27
93.53
0,0157
47.54
7.75
23.73
CAGrad
75.16
93.48
0.0141
37.60
7.25
11.64
IMTL-G 37
75.33
93.49
0.0135
38.41
5.25
11.10
MoCo
75.42
93.55
0.0149
34.19
4,00
9,90
MoDo
74.55
93.32
0.0159
41.51
10.75
18.89
Nash-MII
10
75.41
93.66
0.0129
35.02
2.75
6.82
FAMO
38
74.54
93.29
0.0145
32.59
7.75
8.13
SDMGrad
74.53
93.52
0.0137
34.01
6.25
7.79
Table 2: Multi-task supervised learning Cityscapes dataset.
6.2 Supervised Learning
For the supervised learning setting, we evaluate the performance the Cityscapes 39 and NYU- v2 [40] datasets. The former dataset involves 2 pixel-wise tasks: 7-class semantic segmentation and depth estimation, and the latter one involves 3 pixel-wise tasks: 13-class semantic segmenta- tion, depth estimation and surface normal estimation. Following the experimental setup of [9] we embed MTL method MTAN (36) into our SDMGrad method, which builds on SegNet [4]] and is empowered by a task-specific attention mechanism. We compare SDMGrad with Linear Scalar- ization (LS) which minimizes the average loss, Scale-invariant (SI) which minimizes the average logarithmic loss, RLW (35. DWA (36,, UW (26). MGDA 77). PCGrad (8. GradDrop [29] CA-
Grad 19, IMTL-G [37]. MoCo 13, MoDo [4). Nash-MTL [10]. and FAMO [38. Following 13 TO 38) we compute two metrics reflecting the overall performance:
42
9
(1) Am%, the
average per-task performance drop versus the single-task (STL) baseline b to assess method m: Am% = *
/ x 100, where K is the number of metrics, My. is the value of metric M& obtained by baseline b, and Mm,k obtained by the compared method 4 = 1 if the evaluation metric Mj on task i prefers a higher value and 0 otherwise. (2) Mean Rank (MR): the average rank of each method across all tasks.
E (-1)² (Mm.k
We search the hyperparameter E (0.1, 1.0} for our SDMGrad method and report the results in Table 2 and Table 3 Each experiment is repeated 3 times with different random seeds and the average is reported. comparable results than the baselines, and in addition, can strike a better performance balance on multiple tasks than other baselines. For example, although MGDA achieves better results on Surface Normal, it performs the worst on both Segmentation and Depth. As comparison, our SDMGrad method can achieve more balanced results on all tasks.
can be seen that our proposed method able to obtain better or
6.3 Reinforcement Learning
For the reinforcement learning setting, we evaluate the performance on the MT10 benchmarks, which include 10 robot manipulation tasks under the Meta-World environment 43). Following the
experiment setup in 9 [3 [00, we adopt Soft Actor-Critic (SAC)
44 as the underlying training
algorithm. We compare SDMGrad with Multi-task SAC [3), Multi-headed SAC 43 Multi-task
SAC+ Task Encoder 43. PCGrad ( CAGrad [9), MoCo 13) Nash-MTI. 10 and FAMO (8)
We search X E (0.1, 0.2, ... 1.0) and provide the success rate and average training time (in sec-

---

Segmentation
Depth
Surface Normal
Method
Angle Distance
Within 1
MR
Am%
mloU 1
Pix Acc f
Abs Err
Rel Err
Mean
Median
11.25
22.5
STL
38.30
63.76
0.6754
0.2780
25.01
19.21
30.14
57.20
69.15
LS
39.29
65.33
0,5493
0.2263
28.15
23.96
22.09
47.50
61.08
11.33
5.59
SI
38.45
64.27
0.5354
0.2201
27.60
23.37
22.53
48.57
62.32
10.33
4.39
RLW
37.17
63.77
0.5759
0.2410
28.27
24.18
22.26
47.05
60.62
13.89
7.78
DWA 56
39.11
65.31
0,5510
0.2285
27.61
23.18
24.17
50.18
62.39
10.11
3.57
MGDA
30.47
59.90
0.6070
0.2555
24.88
19.45
29.18
56.88
69.36
7.33
1.38
PCGrad
38.06
64.64
0,5550
0.2325
27.41
22.80
23.86
49.83
63.14
10.44
3.97
GradDrop
39.39
0.5455
0.2279
27.48
23.38
49.44
62.87
3.58
CAGrad 9
39.79
65.49
0,5486
0.2250
26.31
21.58
25.61
52.36
65.58
6.44
0.20
IMTL-G
37
39.35
65.60
0.5426
0.2256
26.02
21.19
26.20
53.13
66.24
5.67
-0.76
McCo 13
40.30
66.07
0,5575
0.2135
26.67
21.83
25.61
51.78
64.85
6.33
0.16
MoDo
[4
35.28
62.62
0,5821
0.2405
25.65
20.33
28.04
54,86
67.37
8.89
0.49
Nash-Mil
65.93
0.5261
0.2171
25.26
68.15
3.33
FAMO
38
38.88
64.90
0.5474
0.2194
25.06
19.57
29.21
56.61
68.98
4.22
-4.00
SDMGrad
40.47
65.90
0.5225
0.2084
25.07
19.99
28.54
55.74
68.53
2.33
-4.84
Table 3: Multi-task supervised learning on NYU-v2 dataset.
onds) per episode in Table compared baselines.
As shown, SDMGrad achieves second best success rate among the
We also validate the efficiency of the proposed objective sampling strategy against other acceleration strategies including CAGrad-Fast [9], Nash-MTL with updating once per (50, 100] iterations (38). Following [9] we choose the task sampling size n 4. As shown in Table 4 our SDMGrad-OS with objective sampling achieves approximately 1.4x speedup on MT10, while achieving success rate comparable to that of SDMGrad. We also observe that although our SDMGrad-OS requires more time than CAGrad-Fast 9 and Nash-MTL. success rate.
38 (every 100), it reaches higher or comparable
Metaworld MT11
Method
time
(mean stderr)
SAC STL (upper bound)
0.90
Multi-task SAC
43
0.49 0.07
Multi-task SAC Task Encoder
0.54 0.05
Multi-headed SAC
0.61 + 0.04
Nash-MTL 10
0,91 + 0.03
PCGrad g
0.72
11.6
CAGrad
0.83 0.05
13.5
MoCo
15
0.75 0.05
11.5
Nash-MTL
38
0,80 - 0.13
87.4
FAMO 38
0.83 + 0.05
4,2
SDMGrad
0.84 0.100
13.6
CAGrad-Fast 9
0.82 + 0.04
8.6
Nash-MTL
38
(every 50)
0.76 + 0.10
9.7
Nash-MTL
(every 100)
0.82 0.12
9.3
SDMGrad-OS
9.7
SDMGrad OS (S=1)
0.80 0.12
6.8
Table 4: Multi-task reinforcement learning on Metaworld MT10 benchmarks. Nash-MTL- [00
denotes the results reported in the original paper. Nash-MTL 38 denotes the reproduced result.
7 Conclusion
In this paper, we propose a new and flexible direction-oriented multi-objective problem formula- tion, as well as two simple and efficient MOO algorithms named SDMGrad and SDMGrad-O We establish the convergence guarantee for both algorithms in various settings. Extensive experi- ments validate the promise of our methods. We anticipate that our new problem formulation and the proposed algorithms can be applied in other learning applications with multiple measures, and the analysis can be of independent interest in analyzing other stochastic MOO algorithms.
10

---

References
[1] Jiaqi Ma, Zhe Zhao, Xinyang Yi, Jilin Chen, Lichan Hong, and Ed Chi. Modeling task relationships in multi-task learning with multi-gate mixture-of-experts. In Proceedings the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 1930-1939, 2018.
[2] Junyu You, William Ampomah, and Qian Sun. Development and application a machine learning based multi-objective optimization workflow for co2-eor projects, Fuel, 264:116755 2020.
[3] Xinyu Huang, Peng Wang, Xinjing Cheng, Dingfu Zhou, Qichuan Geng, and Ruigang Yang- The apolloscape open dataset for autonomous driving and its application. IEEE transactions on pattern analysis and machine intelligence, 42(10):2702-277 21112222222299,,,-11111119999990 2019.
[4] Philip S Thomas, Joelle Pineau, Romain Laroche, al. Multi-objective spibb: Seldonian offline policy improvement with safety constraints in finite mdps. Advances in Neural Infor- mation Processing Systems, 34:2004-2017, 2021.
[5] Simon Vandenhende, Stamatios Georgoulis, Wouter Van Gansbeke, Mare Proesmans, Dengxin Dai, and Luc Van Gool. Multi-task learning for dense prediction tasks: A survey. IEEE transactions on pattern analysis and machine intelligence, 44(7):311--3633, 2021.
[6] Ozan Sener and Vladlen Koltun. Multi-task learning as multi-objective optimization. Advances neural information processing systems, 31, 2018
[7] Jean-Antoine Désidéri. Multiple-gradient descent algorithm (mgda) for multiobjective opti- mization. Comptes Rendus Mathematique, 350(5-6):313-315 2012.
[8] Tianhe Yu, Saurabh Kumar, Abhishek Gupta, Sergey Levine, Karol Hausman, and Chelsea Finn. Gradient surgery for multi-task learning. Advances in Neural Information Processing Systems, 145582458836 2020.
[9] Bo Liu, Xingchao Liu, Xiaojie Jin, Peter Stone, and Qiang Liu. Conflict-averse gradient de- scent for multi-task learning. Advances in Neural Information Processing Systems, 34:18878- 18890, 2021.
[10] Aviv Navon, Aviv Shamsian, Idan Achituve, Haggai Maron, Kenji Kawaguchi, Gal Chechik, and Ethan Fetaya. Multi-task learning as a bargaining game. arXiv preprint arXiv:2202.01017, 2022.
[11] Suyun Liu and Luis Nunes Vicente. The stochastic multi-gradiem algorithm for multi-objective optimization and its application supervised machine learning. Annals of Operations Re- search, pages 1-30, 2021.
[12] Shiji Zhou, Wenpeng Zhang, Jiyan Jiang, Wenliang Zhong, Jinjie Gu, and Wenwu Zhu. On the convergence stochastic multi-objective gradient manipulation and beyond. Advances in Neural Information Processing Systems, 35:38103-388
2022.
[13] Heshan Devaka Fernando, Han Shen, Miao Liu, Subhajit Chaudhury, Keerthiram Murugesan, and Tianyi Chen. Mitigating gradient bias in multi-objective learning: A provably convergent approach. The Eleventh International Conference on Learning Representations, 2023.
[14] Lisha Chen, Heshan Fernando, Yiming Ying, and Tianyi Chen. Three-way trade-off in multi-objective learning: Optimization, generalization and conflict-avoidance. arXiv preprint arXiv:2305.20057, 2023.
[15] Kazuma Hashimoto, Caiming Xiong, Yoshimasa Tsuruoka, and Richard Socher. A joint many-task model: Growing a neural network for multiple nip tasks. arXiv preprint 1rXiv:1611.01881 2016.
[16] Sebastian Ruder. overview of multi-task learning in deep neural networks, arXiv preprint 17X1v:1706.05098, 2017.

---

[17] Yu Zhang and Qiang Yang. A survey on multi-tast learning. IEEE Transactions on Knowledge and Data Engineering. 34(12):5586-560 5609, 2021.
[18] Ishan Misra, Abhinav Shrivastava, Abhinav Gupta, and Martial Hebert. Cross-stitch networks for multi-task learning. In Proceedings of the IEEE conference on computer vision and pattern recogmition,, pages 3994-4003, 2016.
[19] Clemens Rosenbaum, Tim Klinger, and Matthew Riemer. Routing networks: Adaptive selec- tion of non-linear functions for multi- malti learning. arXiv preprint arXiv:1711.01239, 2017.
[20] Ruihan Yang, Huazhe Xu, Yi Wu, and Xiaolong Wang. Multi-task reinforcement learning with soft modularization. Advances in Neural Information Processing Systems, 33:4767-4777, 2020.
[21] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. arXiv preprini 30K3::/5033025// 2015.
[22] Haoxiang Wang, Han Zhao, and Bo Li. Bridging multi-task learning and meta-learning: To- wards efficient training and effective adaptation. In International Conference on Machine Learning (ICML), pages 10991-11002. PMLR, 2021.
[23] Feiyang Ye, Baijiong Lin, Zhixiong Yue, Pengxin Guo, Qiao Xiao, and Yu Zhang. Multi- objective meta learning. Advances in Neural Information Processing Systems (NeurIPS), 34:21338 21351, 2021.
[24] 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 (NeurIPS), 34:27503-27516, 2021.
[25] Elliot Meyerson and Risto Miikkulainen. The traveling observer model: Multi-task learning through spatial variable embeddings. arXiv preprint arXiv:2010.02354 2020.
[26] Alex Kendall, Yarin Gal, and Roberto Cipolla. Multi-task learning using uncertainty to weigh losses for scene geometry and semanties. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages (4822-7497 2018.
[27] Zhao Chen, Vijay Badrinarayanan, Chen- Yu Lee, and Andrew Rabinovich. Gradnorm: Gra- dient normalization for adaptive loss balancing in deep multitask networks. In International conference on machine learning, pages 794-803. PMLR, 2018
[28] Michelle Guo, Albert Haque, De-An Huang, Serena Yeung, and Li Fei-Fei. Dynamic task prioritization for multitask learning. In Proceedings of the European conference computer vision (ECCV), pages 270-287, 2018.
[29] Zhao Chen, Jiquan Ngiam, Yanping Huang, Thang Luong, Henrik Kretzschmar, Yuning Chai, and Dragomir Anguelov. Just pick sign: Optimizing deep multitask models with gradient sign dropout. Advances in Neural Information Processing Systems, 33:2039-2050, 2020.
[30] Adrián Javaloy and Isabel Valera. Rotograd: Gradient homogenization in multitask learning.
arXiv preprint
2021.
[31] Yuzheng Hu, Ruicheng Xian, Qilong Wu, Qiuling Fan, Lang Yin, and Han Zhao. Re- visiting scalarization in multi-task learning: A theoretical perspective. arXiv preprint a308v:2308. 13985, 2023.
[32] Michinari Momma, Chaosheng Dong, and Jia Liu. multi--hhjective/mltiiass learning framework induced by pareto stationarity. In International Conference on Machine Learning, pages 15895-15907. PMLR, 2022.
[33] Weiran Wang and Miguel Á. Carreira- Perpiñán. Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application, 2013.
[34] Adrien Gaidon. Compute euclidean projections on the simplex l1-ball. GitHub, 2011.
12

---

[35] Baijiong Lin, Feiyang Ye, Yu Zhang, and Ivor W Tsang. Reasonable effectiveness of random weighting: A litmus test for multi-task learning. arXiv preprint arXiv:2111.10603 2021.
[36] Shikun Liu, Edward Johns, and Andrew J Davison. End-to-end multi-task learning with atten- tion. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pages 1871-1880, 2019.
[37] Liyang Liu, Yi Li, Zhanghui Kuang, J Xue, Yimin Chen, Wenming Yang, Qingmin Liao, and Wayne Zhang. Towards impartial multi-task learning. iclr, 2021.
[38] Bo Liu, Yihao Feng, Peter Stone, and Qiang Liu. Famo: Fast adaptive multitask optimization, 2023.
[39] Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld. Markus Enzweiler, Ro- drigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele. The cityscapes dataset for semantic urban scene understanding. In Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
[40] Pushmeet Kohli Nathan Silberman, Derek Hoiem and Rob Fergus. Indoor segmentation and support inference from rgbd images. In ECCV, 2012.
[41] Vijay Badrinarayanan, Alex Kendall, and Roberto Cipolla. Segnet: A deep convolutional encoder-decoder architecture for image segmentation. IEEE transactions on paltern analysis and machine intelligence, 39(12):2481-2445 2017.
[42] Kevis-Kokitsi Maninis, Ilija Radosavovic, and lasonas Kokkinos. Attentive single-tasking of multiple tasks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1851-1860, 2019.
[43] Tianhe Yu, Deirdre Quillen, Zhanpeng He, Ryan Julian, Karol Hausman, Chelsea Finn, and Sergey Levine. Meta-world: A benchmark and evaluation for multi-task and meta reinforce- ment learning. Conference on robot learning, pages 1094-1100. PMLR, 2020.
[44] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with stochastic actor. In International conference on machine learning, pages 1861-1870. PMLR, 2018.
[45] Xi Lin, Hui-Ling Zhen, Zhenhua Li, Qing-Fu Zhang, and Sam Kwong, Pareto multi-task learn- ing. In H. Wallach, H. Larochelle, Beygelzimer, d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[46] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Cradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 (6(11))2278-22) 2324, 1998.
[47] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnin marking machine learning algorithms. arXiv preprint wwXiv:1708.07747 2017.
novel image dataset for bench-
[48] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-2324, 1998.
[49] Shagun Sodhani and Amy Zhang. Mtrl multi task rl algorithms. Github, 2021.
[50] Jonathan Borwein. very complicated proof of the minimax theorem. Minimax Theory and its Applications, 1
[51] Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Con- vergence results and optimal averaging schemes. In International conference on machine learning, pages 7 71-79. PMLR, 2013.
13

---

Supplementary Materials
Experiments
A.1 Toy Example
To demonstrate our proposed method can achieve better or comparable performance under stochastic settings, we provide an empirical study on the two-objective toy example used in CAGrad П The two objectives (z) and (2(x) shown in Figure are defined on z x2) R??
(x)x) (z))) + (z)))( T2(x;) fi (x) + (2))))2())
where the functions are given by
(x) max (lanh(0.5.22)) 0)
f2(x) max (tanh(--O (00.lm0-0 0)
gi ((()) log max (10.5(-2) 7) tanh((=2)), (.000000))))
92(x) log [ax (10.5(-31 + tanh(-w2) 2). 0.000005) +
h1(2) ((-#1 +) 0.1 8)3)/10- 20
- h2(x) = -1) + 8)3) -02
(a) Mcan objective
(b) Objective
(c) Ohjective
(d) MGDA
20
-9
41
(e) GD
(I) PCGrad
CAGrad
(h) SDMGrad(Ours)
Figure 1: A two-objective toy example.
We choose 3 initializations
3o E (1-8,5,, (-8.5, (9,9))
for different methods and visualize the optimization trajectories in Figure The starting point of every trajectory in Figure [d Figure 1h is given by the symbol, and the color of every trajectory changes gradually from red yellow. The gray line illustrates the Pareto front, and the symbol denotes the global optimum. To simulate the stochastic setting, we add zero-mean Gaussian noise to the gradient of each objective for all the methods except MGDA. We adopt Adam optimizer with learning rate of 0.002 and 70000 iterations for each run. As shown, GD can get stuck due to the dominant gradient of a specific objective, which stops progressing towards the Pareto front. PCGrad and CAGrad can also fail to converge to the Pareto front in certain cireumstances.
14

---

A.2 Consistency Verification
We conduct the experiment on the multi-task classification dataset Multi-Fashion Fashion+MNNIST 445 Each image contained in this dataset is constructed by overlaying two images randomly sampled from MNIST [46] and FNSST [47 respectively. We adopt shrinked Lener [48] as the shared base-encoder and a task-specific linear classification head for each task. We report the training losses obtained from different methods over independent runs in Figure 2 As illustrated, the performance of SDMGrad with large À is similar to GD, and the performance when À is small resembles MGDA. With properly tuned X, lower average training loss can be obtained. Generally, the results confirm the consistency of our formulation with the direction-orienter principle.
0.60
Task Loss
Task 2 Loss
Avg. Loss
0.55
0.50
0.45
Training
0.40
0.35
0.30
0.25
GD
MGDA
SDMGrad (1=
SDMGrad
SDMGrad 1)
SDMGrad
SDMGrad
(A = 0.5)
(A=5) = 10)
Figure 2: Consistency verification on Multi-Fashion-MNISTT dataset.
The Molti-Fashionn-NNITTT.. includes images constructed from FashionMNIST and (46) First, select one image from each dataset randomly, then transform the images into a single image with one put in the top-left corner and the other in bottom-right corner. The dataset contains 120000 training images and 20000 test images. We use SGD optimizer with learn- ing rate 0.001 and train for 100 epochs with batch size 256. We use multi-step scheduler with scale factor 0.1 decay learning rate every 15 epochs. The projected gradient descent performed with learning rate of 10 and momentum of 0.5 and 20 gradient descent steps are applied.
A.3 Supervised Learning
We implement the methods based on the library released by [10]. Following 9 [3]]0,, we train method for 200 epochs, using Adam optimizer with learning rate 0.0001 for the first 100 epochs and 0.00005 for the rest. The batch size for Cityscapes and NYU-v2 are 8 and 2 respectively. We compute the averaged test performance over the last 10 epochs final performance measure. The inner projected gradient descent performed with learning rate of 10 and momentum of 0.5 and 20 gradient descent steps applied. The experiments Cityscapes and NYU-v2 are RTX 3090 and Tesla V100 GPU, respectively. We also report additional experiment results over different and S 1 in Table and Table 6
A.4 Reinforcement Learning
We train our method for million steps with batch size of 1280. The inner projected gradient descent is performed with learning rate of 10 for MT10 benchmark and 20 gradient descent steps are applied. The method evaluated once every 10000 steps and the best average test performance over random seeds over the entire training process is reported. We search X E {0.1, 0.2, 1.0} for MT10 benchmark and the highest success rate achieved when 0.6. For our objective sampling strategy, the number of sampled objectives is random variable obeying binomial distribution whose expectation is n.
Following 99
13
10
we conduct the experiments based MTRL codebase 49
15

---

Method
Segmentation
Depth
Am%%
mloU 1
Pix Acc
Abs Err
Rel Err
STL
74.01
93.16
0.0125
27.77
SDMGrad (A 0.1)
72.56
92.68
0.0156
40.89
18.65
SDMGrad 0.2)
74.79
93.30
0.0149
32.46
8.62
SDMGrad 0.3)
74.53
93.52
0.0137
34.01
7.79
SDMGrad -0.4)
75.10
93.48
0.0137
35.66
9.11
SDMGrad =0.5)
SDMGrad =0.6]
74.42
93.22
0.0138
38.79
12.30
SDMGrud (2 == =0.7)
75.06
93.42
0.01588
39.98
17.24
SDMGrad =0.8)
74.99
SDMGrad -0.9)
75.60
93.50
0.0134
43.52
15.39
SDMGrad (A 1.0)
74.50
93.47
0.0142
42,80
16.41
SDMGrad
74.17
0.0154
SDMGrad =
75.41
0.0139
Table 5: Addtional supervised learning experiments Cityscapes dataset.
Segmentation
Depth
Surface Normal
Method
Angle Distance
Within t"
Am%
mioU
Pix Acc
Abs Err
Rel Err
Mcan
Median
11.25
22.5
30
STL
38.30
63.76
0.6754
0.2780
25.01
19.21
30.14
$7.20
69.15
SDMGrad (A 0.1)
40.23
66.01
0.5360
0.2268
19.99
28.45
55.80
68.65
-3.86
SDMGrad (A 0.2)
39.23
65.67
0.5315
0,2189
25.13
20.02
28.12
55.71
68.46
-3.66
SDMGrad (A 0.31
40.47
65.90
0.5225
0.2084
25.07
19.99
28.54
55.74
68.53
-.84
SDMGrad (A 0.4)
40.68
66.53
0.5248
0,2199
25.21
20.01
27.69
55.72
68.58
-4.14
SDMGrad (A 00.51
41.08
66.82
0.5184
0.21166
25.65
20.68
26.70
54.27
67.46
-3.33
SDMGrad 0.6)
41,20
66.86
0.5258
0.2175
25.85
21.03
26.47
53.51
66.82
-2.39
SDMGrad (A =0.7)
41.00
66.31
0.5224
0,2202
25.60
20.64
27.64
$4.30
67.15
-3.16
SDMGrad
0.5406
0.2266
SDMGrad (A 0..9)
41.03
67.16
0,5314
0,2271
25.89
20.97
27.22
53.58
66.48
-2.17
SDMGrad 1.0)
0,5224
0,2155
26.51
21,95
25.15
51.54
64.94
SDMGrad (A= 10)
39.81
66.11
0.5352
0.2232
27.05
22.57
24.53
50.24
63.59
1.82
SDMGrad (A =03.S= 1)
39.63
65.43
0.5296
0.2140
25.66
20.83
27.18
53.93
67.05
-2.34
Table 6: Addtional supervised learning experiments on NYU-v2 dataset.
To compare with CAGrad-Fastl 9 choose n for MT10 benchmark. We cite the reported success rates of all baseline methods in Table 4 but independently run each experiment 5 times to calculate the average running time. All experiments on MT10 are run on RTX 2080Ti GPU. We also report addtional experiments results over S = 1 on MT10 in Table
Metaworld MT10
Method
success
time
(mean stderr)
SDMGrad
0.84 + 0.10
13.6
SDMGrad (S=1)
0.83 + 0.05
11.2
SDMGrad-OS
0.82 + 0.08
9.7
SDMGrad-OS (S=1)
0.80 + 0.12
6.8
Table Additonal reinforcement learning experiments on Metaworld MT10 benchmarks.
B Notations for Technical Proofs
In this part, we first summarize all the notations that we used in this paper in order to help readers understand. First, in multi-objective optimization, of them has the loss function (,).) Let 9i denote the gradient of objective i and go denotes the target gradient. w (w..... wK) )" E gg and W denotes the probability simplex. Other useful notations are listed as below:
have K > different objectives and each
0* = arg min
Lo(
Σ 1.... go - (0) G(0) i=1
DERm
16

---

9v Σ wigs s.t. = {w: Σ wa and wi 2 0]
wx - arg min
wEW 2
1l + Agoll w² = arg min
wEW 2 gml wi - arg min =
1
[[)(w)))l
weW 2
wi,x = arg min F(w) arg min G( + (0)(
weW
wEW? 2
V [(w) = G(O,) (G(O,)) + (O)). V F(w) - G(O,;)) (G(O:, (): (11)
We use E[.AA B to denote taking expectation over A conditioning on B and Ö omits the order of log.
C Detailed proofs for convergence analysis with nonconvex Objectives
We now provide some auxiliary lemmas for proving Proposition 1 and Theorem | Lemma 1, Let d' be the solution of
max min (ee d) - =/l + N(g. d), dE {E[K]
then we have In addition, w is the solution of
d' 9w + Ago.
1
min wEW
b11ow Iw Agoll?
Proof. First, be seen that
max min (gr, d) - [1]] + Mggo d)
deRm iE(K]
max min dER WEW
Σ
wigi d) - 2 =Ild]] + A(go. d)
1 |dl M(go, d).
max min Iw d
(12)
dek" WEW
Noting that the problem is concave w.r.t. d and convex w.r.t and using the Von Neumann-Fau Fan minimax theorem [50], we can exchange the min and max problems without changing the solution. Then, we can solve the following equivalent problem.
min max Fne T WEW AERm
2 ||d|l + A(go d)
(13)
Then by fixing w, we have d' 9nr + Ago- Substituting this solution the eq. [33 and rearranging the equation, we turn to solve the following problem.
wEW _ g.w Agoll
min
Let w. be the solution of the above problem, and hence the final updating direction d' =Iws + Agu- Then, the proof is complete.
Lemma 2.
Suppose Assumption 3 are satisfied. According to the definition of go in eq.
we have the following inequalities,
[0))(0)]| < Cg,, [1) - -000))) Koj
Proof. Based the definitions, have
[0) [|G(0)ā|| Cg, where the inequality follows from the fact that || < and Assumption 3 Then, have (el {) go (0)1 < Egll G(0; G( < Koj
where of max; of and the proof is complete.
17

---

Lemma 3. Suppose Assumptions 2 are satisfied and recall that F(w) 2 (l + (go
is convex function. Let w = arg win Ellgw + Agol? and set step size Br, = c/ where e > 0 is a constant. Then for any S > holds that,
E (w)ll 501,
B[llG()))ws + Ago(0)))12 - + A0o (0.) S +2200() 2 2+ log(S)
)
VS
where C = + (X c2)² O(K + XK), vwF (C(O:))) )go(
Proof. This lemma mostly follows from Theorem in 51 However, we did not take that E[I[V,, ((w))l II] is bounded by constant as an assumption. Therefore, we first provide bound
for it in our method. Based on the definition in Equation q11. (wF(w)= = (((O)))))(
(0; {¹)). According to the fact that [[ S / have
F. (I)
V
(()) /EIIG(0:: (ou(Ori
2E
+ 90(0:)))))))))))))))) (o(())')))"""
(14)
where (i) follows from the Young's inequality. Next, we provide bounds for [B[A] and E[B). sepa- rately:
E[A] 3C
-EII(G(B:E)* (Mlcc(/(S---cG0(/((00-))00000--- G(O,)) G(
< 4ET(I((0:E5T - -C(A)))))0GG0 - [[00777111100000--000000+1111111 (0000))0000))))))))))))))))))+) ([G(0EE) G(O,) |10,)
+ +IG(G)) G(A,)) +IG(())
(18) < + + 4C 4 (Kop + Cz)
(15)
where (i) follows from Cauchy-Schwarz inequality and w E W where W is the simplex, (tt)
follows from Young's inequality and (tii) follows from Assumption 2 and Assumption Then for term B, we have,
[BB] [[[((((0))) - - -(()))))) - go.))))
-(00))))))) ((C0:))))) -C(h)))))) (0.)ll
+ ( ||G(0 )o (0:)
(48)
$ 4K o0 &Ko + 4C; 4 4(Ko] + c?,2
(16)
where (1) follows from Young's inequality, (it) follows from Assumption 3 and Lemma
Then
substituting eq. 15) and eq. 16 into eq. (14), we can obtain,
El F
(w]] /(KK] + Cg) + 8X2 + C2)2 Ci.
Meanwhile, since E| E[[ (w))ll S CI. sup o || - w'll s and by choosing step size B, c/ / where c is a constant, we can obtain the following incquality from Theorem in [5I]:
1 + cCi)
2 + log(S)
F(F(ws) F(w)) s (
VS
Then after multiplying by 2 both sides, the proof is complete.
18

---

C.1 Proof of Proposition 1
CA distance. Now we show the upper bound for the distance to CA direction. Recall that we define
the CA distance as [Bc,,,g10 [G(O;; w) + (0u - G( )w (gu
Proof. Based on the Jensen's inequality, we have
Bc, [G(O;; ()wr, (0o ()) -(0))))) (go()))
<Bm,, (s. | [E) Aeu ()1 G( - \go(0)))
2 - - G(0,)wuxx11)
-B]lIG(0.)ur.,5 + Ago((,)) - G( (0)())))
=E]IIG(0))uv.5+ + Ago +[G(())) + Ago (0:)
-2E(G(0,)wt.5 (0)), G(O,) + +goo(O)))]
[|I 1[G(0))) + Ago (0:)]l²
-1 Ag0)))) (Ago
(()))) Ago(0)))]
(1)
$ +1lc(ea)juussttxo0000]]++++++++3 + Aau (6:))1
-B[(0(000 - 2E (Agu (()) G( + Ago(O.))
= [|IlC/00)0u.sttxx20000000)001111
+ (
=F. (0] W4,5 + (0) - + Ago (0:))1
2 15g
2
(18)
VS
where (i) omits the subscript of taking expectation over whss conditioning on t,, (fi) follows from optimality condition that
(w, G(O.) (G(())) + Ago().))) 2 (wT G(O.) + (0)().)))-
(19)
(iit) follows from Lemma whenwe choose Bt.s c/ where is constant. Then take the square root on both sides, the proof is complete.
C.2 Proof of Theorem
Theorem 5 (Restatement of Theorem 1.. Suppose Assumptions 3 are satisfied. Sel 0z
@((1 + 1)- - Br,e v/vs where is a constant, and S O((1 + 2)-212). The outputs of the proposed SDMGrad algorithm satisfy
BlI))(,)) (go( 5((1 (²)
T
2 0
Proof. Recall that G((:; + (f:; (). According to Assumption 1 have for any
a L,(0411) + ( - (..) + (L) + au (6.) + (g,) dd) + 2
||]]
(20)
where 11, 441 + Amx, 4,1 @(1 + A). Then bound the second and third terms separately on the right-hand side (RHS). First, for the second term, conditioning on 0 and taking expectation, have
((x (0)) ()wr, - (0:: <)) [0:] (0.) + (g)( -G(0))wr. - (0.)
(0,) + (0)) G(0:) G(B,)wr,s) (0. + )go(())), G(O,)w -go((.))
19

---

SB(( + +C, G( - Bl| ((f))a + (go(
(4 + +CO) B1I|((0)) wi, G((6))() [..] [[]|G(())w] (00
(46) I (4 + +0, ( 2cCc) 2+1oog log(S)
+
vS - El (0)((1))
(21)
where (i) follows from Cauchy- Schwarz inequality and optimality condition in eq. 19 (ii) follows from the fact that [[X] s / [ and (tit) follows from eq. (18
Then for the third term,
[|]](( (wr,s Ago ()
=BI|G(0;: -(())) G(O,) wr.s + Ago(Ori - >go((0)) + {go(
4B|I|G((;; - +
4X3Billou 4E||
go (0.)
4K + 40g + Ko + 4x
(22)
where (i) follows from Young's inequality, and (ii) follows from Assumption 3 and Lemma that C2 = O(K + Kx²). Then taking expectation on eq. (20). substituting eq. 21 and eq. 22 it, and unconditioning on Oz, we have
Note
into
E E[L,(0141) ALo(Ot-1)
< (0.) + (Lo( + a, + (go) -d>] + 14 az
E B||d
( +20C1) 2 (o)
(0.) + ALo( + a1 + +
vS
4, C2
a,B[[G(0))) + Ago (0.)l1
(23)
2
Then, choosing a₂ = a, and rearranging the above inequality, we have
aBll(G(0.)wz, (0) (0.) + ALo(O.) Li(00+1) (Lo(O++1)]
+ al4 + >C2) ? 2 2003)
+200s) 2+ (og(s)
+ a2
2 Cz.
VS
Telescoping over / [T] in the above inequality yields
T-1
Σ E]IGG(O))w + Ago t=0
T
V Cz
(lo) - inf ((() A(L - inf Lo)
aT
+ (14 + AC2)) (2+cch)) 2ccr) 2 + logg(S)
VS
If we choose 0 + K -ork-=1--- サ) and 5= @(1 + A) -272), we have
Σ
G(0, (oo( 5(( xx3)
where Ô means the order of logT is omitted. The proof is complete.
20

---

C.3 Proof of Corollary 1
Proof. Since À > 0 and gu(Ot) G( we have
Bl][G(,))w? + (00(0,) = - 1) (1 A)
where w' 1
1+1 (wi, + Aw w 22 Xwe "K,,A \ūx) "r such that w' E W. According to parameter selection in Theorem | and by choosing constant X, we have
Σ =
(24)
To achieve an e-accurate Pareto stationary point, requires T Ö(K and each objective re- quires O(K 9) samples in & (5') and O(Ke samples in Ç. respectively. Meanwhile, according the choice of $ and T, have the following result for CA distance,
K sl, (G(e,, () s (0o ()) - G( - Ago = T
(c))
(25)
Remark. Our algorithm with constant À helps mitigate gradient conflict and it guarantees an e-accurate Pareto stationary point and the CA distance takes the order of Ö(e) simultaneously. O
C.4 Proof of Corollary 2
Proof. According to the incquality ||a + 6 b- b1|2 = 2||a + b112 + 2|16/ we have
X \211)=(0,)11 <2) + ( + [
(2|(((b,)ur,, + (g)( 2C²
where the last inequality follows from Assumption Then we take the expectation on the above inequality and sum up it over E [T] such that
T-1
T-1
C
B Bll)((()))) + Ago(000)
T
X²T
X
1=0
=5((2 + 1)K + +
where the last inequality follows from Theorem
we choose O(T then we have
Σ E (0.)) =
To achieve an c-accurate stationary point, requires T Ö(Kr and each objective requires Ō(K²,-1) samples in & (g') and (()= samples in (, respectively. Meanwhile, according to the choice of X, S and T, we have the following result for CA distance,
| (O,,,, Ow,s + (Or: ()) G( (go( =6(V A(1+ ) =
T =
Remark. With an increasing X, our algorithm approaches GD and it has a faster convergence rate to the stationary point. However, the CA distance takes the order of Ö(VK).
C.5 Proof of Theorem 2
Now we provide the convergence analysis with nonconvex objectives with objective sampling.
Theorem 6 (Restatement of Theorem D.. Suppose Assumptions 7 are satisfied. Set K at = a = @([1 + - K- Br, c/ vss and S @((1 2)- 22T2). Then by choosing constant X, the iterates of the proposed SDMGrad-OO algorithm satisfy
Σ
=
21

---

Proof. Recall that updating direction for 0g is K H Sywr, + 4 S. Similarly, we have
(g)( -d') a |
(0(+1)) + (Lo(Oe+1) - L.)))) + (Lo(O)) + ar (g)(())))
(26)
2
Then for the inner product term on the RHS of eq. (26). conditioning on Og and taking expectation, we have
(1:) d'' (0) + (B:) -((,) Agu(Oe))10A)
5(4+ + AC,)( <(,+AC,)(1
( 2cC,)
2 (og(())) ElIG((,))u,,, + Ago
(27)
VS
where the last inequality follows from eq. bound the last term on the RHS of eq. (26 as
21
Then following the same step as in eq. 22 we can
E Billd'11 - 2 X2) (nog + Cg)
(28)
Then taking expectation eq. (26). substituting eq. 27 and eq. 28 into it and unconditioning d, we have
20(3, 2 (+lg((S) ( +
(0++() ALo(0++1) SE(L,(0)) (Lo(O.) + +al4 (C
vS
4 12 C₁
a,BB)G((,)uu. + (0:)11
2
Then choosing a₂ a, telescoping the above inequality over t e [T]. and rearranging the terms, we have
1 ElIGG(0))u;, + Ago
aT B(L, -0) - inf L.(0) + X(Lo(Oo) - inf Lo(O))] + 41110 C2
T
t=
2 20Cr) + S+Lo((S),
+ (4 + xCg)(
vS
we choose a = @(11 + 2 and @(11 + 2 2T we can get + I [[]] + (0))l = Õ(( + - 4). Furthermore, by choosing À as
constant and following the same step as Appendix C.3 we have
Σ =
To achieve an e-accurate Pareto stationary point, it requires T = Ö(K7e 2). In this case, each objective requires a similar number of samples ÖKK 6) in & (g') and Ö(Kye ?) samples in S, respectively. As far as we know, this is the first provable objective sampling strategy for stochastic multi-objective optimization.
D Lower sample complexity but higher CA distance
When we do not have requirements on CA distance, we can have much lower sample complexity. In Algorithm|] [ the update process for w to reduce CA distance, which increases sample complexity. Thus, we will set 5 = 1 to make Algorithm I more sample-efficient In addition, we will use w1+1 = w1.1 and 3, instead of Br, in Algorithm for simplicity. The following proof mostly motivated by Theorem 3 in [1]
22

---

D.1 Proof of Theorem 3
Theorem (Restatement of Theorem 3) Suppose Assumptions 33 are satisfied and S Set
a, a -(K- +T++), 8, = 3 OKK-T TT #) and X as constant. The iterates of the proposed SDMGrad algorithm algorithhn satisfy,
B =
Proof. Now we define a new function, with fixed weight E W. 1'(0,) = L(0,) + (0.).
(29)
For this new function, we have
(((0++1) (1) (G(((()) (go( -dy 1 a ||d]?
2
=1'(0,) + 0r (G(O + Ago(Oe), - G( ( W04+1 - (00 ()) + ya
||d]
2
where 1 max; 4,11 + Ah.11 Then taking expectations over on both sides and rearranging the inequality, we have
([(((++))] - -E(((0)) (G, (0.) -G(0)) - Ago + 1 B|||
= (GE - (O.). G(O,) G(())wn)]
o, - (0.) G(O,) io + Ago(O:))) + 10 [[[ld]
2
= a.E((G(()))r - (O.). G( W++1 G(())ww))
o,B((G(()))r G(O w., G(O:) ww (go(O.)))
-a.B[]G(0,)w) + (0))l 1 oa B[[d]]
Sa, B[I(G(())) + Ago (0:) G(O,)) w
+ au B[((G(),) G(O,)w, G(O,)wr + (go(
Ma E[|d]]),
G((,) + (0) +
(30)
2
where (i) follows from Schwarz inequlaity. Then we provide bound for term and term D, respectively. For term C,
[[I](G(O))) + ((o)lll w
[G) + (aee://:haaaaaaaeecaeccaa/l/...a
+ (0:
(3, + +go (10eeee))") E')u,l XlIG((;; (1)) <, + X) Koo c,)²= 3,Cs,
(31)
where C3 O((1 + =)= Then for term D, we first follow the non-expansive property of projection onto the convex set,
|1041 - wwl <||w,, - (CC(::)))(((((:)))))))
Ago w|l2 =||w; - w 23, (w, w. (G(8; + (0;; (0:; [
+ ( (G
Then taking expectation on the above inequality, obtain,
Eillwe+1 w| <Eillw; w|| 23, w. G(O.; (G(O):)))(((())))))))) + Ago(Or: E'M
23

---

+ 1 (G(,; + Ago (9;
<B||w, =||²| 1 (w, w, G(O,)² (G(()) + (0.))) +.C.
where the last inequality follows from Lemma obtain,
3 Then by rearranging the above inequality, we can
1
3r P2 200 (32)
- w. G(( (G(O)))r + (go(O.))))
|| w/13] R [[[ wwl
23
2
Then substituting eq.
(31 and eq.
(2 into eq.
30 we can obtain,
Bl(((0 - (0.)) Sa,3,C3
ai
B
E
wy
w|1
||
w0|2 ar C?
23
Gáa2
a,Blll((f))uu {0o(
Bi|ld|s]
2
Sa,BCss+ + at
Billw: wm - w|12 -1|we+1 - -wll 2/
C?
2
Kj C2
ar a(B] + (0)(
(33)
2
Then we take ar = a and B. = B as constants, telescope and rearrange the above inequality,
Σ
B[l)(())) + (00 aT
(l)) - ((()r)
B wo w|l - 1ewr - =wl??
T
23T
1=0
C ) Ga C2
+ B +
( 0o at + +ak + 3T + 3K3)
(34)
where (i) follows from that we choose À constant. If we choose OKK- and -7- 1), can get + -
E [[()[( w, + Ago((0)) ((KT-)). Furthermore,
following the same steps as in Appendix
C.3 we have
=1
1=0
To achieve an e-accurate Pareto stationary point, it requires T OK) In this case, each objective requires a similar number of samples O(K2 in E(E') and Ç. respectively.
Convergence under objective sampling. We next analyze the convergence of SDMGrad-OS.
Theorem 8 (Restatement of Theorem 4.. Suppose Assumptions 73 are satisfied and S Ser
K at a - ²), B, 3 O(K-1)) 7n- 'T b) and as a constant. The iterates of the proposed SDMGrad OS algorithm satisfy.
Σ
T
Proof. In SDMGrad-OS, the vector for updating 0g d' K H(Br; S. 5p + AK Ahh(0f; 5)- Using the same function defined in eq. (29). we have
Ga² ||12112.
(((0++)) <1'(0)) + a (G(O)) Ago(O.), dd')
Then by taking expectation over and š. we have
I'a
(1((( - -'(()) (G,))(G(())) Ago(O.), -G(,)),, (go( 2
B|||d'|
24

---

=a C() - -
+ o, G( G( + A
El] Ago (0.)) 11
2 B[[|d'P9)
(G )gu ( (i)
w++1ll
+ +G, -
w. G(O.) + Ago(
- [l)]G( + Ago (0.) + 1 B
(35)
2
Then following the same steps eq. 31 and eq. 32) we can obtain,
(1(((0+1)-1((0)) - Sa,B.C's
E
w|l2 - || w]]1]+
2
2
-(l() (0:) + o0 C2.
(36)
where (x= ( (nap + + Cg), and Cy = (3+
Cg)?. Then we take a; = a and Bt = 3 as constants and telescope the above inequality,
1
Σ t=
(l)))( + +000
- oT
1
(0o) -((0r)]
Sl w|l - | - w1
T
23T
+ BC, + 97
1,a
C2
2
0 aT
+ KayK + BT + ,T²
(37)
where (i) follows from that we choose À constant. Similarly, if we choose 0 -
and B O ((K-1g-1T-$) we can get + EE [[I)G(0,)wr, + Ago((.))) = O(K7T- -)- Fur-
thermore, following the same step in Appendix C.3 we have
Σ
T
To achieve an e-accurate Pareto stationary point, requires T 0(?2K2 In this case, each objective requires a similar number of samples ((22 22 in ((')) and Ç. respectively. Li
25


Reviews:
[{"review_id": "I3BhVfhoac", "reviewer": "Reviewer_QQfF", "summary": "This paper proposes stochastic variants of the MGDA for multi-objective optimization (MOO) problem, named \"Stochastic Direction-Oriented Multi-objective Gradient descent\" (SDMGrad) and SDMGrad-OS with efficient sampling. Optimization convergence analysis to the Pareto stationary point is provided, with improved complexities compared to prior works on stochastic MOO. \nThe proof of optimization convergence mainly follows that of [12].\nExperiments on multi-task supervised learning and reinforcement learning justified the superior performance of the proposed method.", "questions": "1. In Section 4.2, line 170-172, why is the case \"the objective in eq. (8) is merely convex w.r.t. $w$, it can only guarantee the convergence of at least one iterate (not necessarily the last one) to the solution $w_\\lambda^*$\"?  \nIn fact, there are works that prove the last iterate convergence of convex objectives, see [c].  \nSince this serves as a motivation for the algorithm design, it is important to clarify it.  \nAnd although it claims that \"to ensure the more practical last-iterate convergence\" in line 172, no guarantee of convergence of objective in eq. (9) for last iterate is provided in the paper.\n\n>[c] Ohad Shamir et al. \"Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes\".\n\n2. The use of smoothing constant $\\rho$ seems to be redundant since you already have another regularization term $\\lambda g_0$, which makes the update direction close to $g_0$. Using the regularization term $\\rho ||w||^2$ has a similar effect of making the update direction close to a uniform combination of gradients of all objectives.  \nSince the motivation \"to ensure the more practical last-iterate convergence\" is questionable, see __Question__-1,\nmore justification is needed for this design.\n\n3. The expectation operations used throughout the paper and proof are very unclear. \nThe same notation $\\mathbb{E}[\\cdot]$ is used for almost all expectations, whether conditioning on $\\theta_t$ or not, except for Eq. (11) in the main paper where $\\mathbb{E}[\\cdot\\mid \\theta_t]$ is used. This makes the arguments or proof steps ambiguous. \n   - In Proposition 1, Equation (11), the LHS has two expectations, one conditioned on $\\theta_t$, and the other not. What are the specific distributions for these two expectations? There is some ambiguity since there are multiple random variables, e.g. $\\zeta, w_{t,S}, \\theta_t$.  \nAlso in the proof of Proposition 1, Appendix C.1, line 522, how is the condition on $\\theta_t$ removed in the first equation of (21)?  \nThis does not seem correct if the inner expectation is not conditioned on $\\theta_t$.\n    - In most part of the proof, $\\mathbb{E}[\\cdot]$ is used for both conditioning on $\\theta_t$ and without conditioning on $\\theta_t$.  \n    E.g. line 533 in the Appendix, Eq (24) is \"conditioning on $\\theta_t$\", and later on in line 538 Eq(26) is \"unconditioning on $\\theta_t$\".\n\n1. In Appendix C.2, line 533-534, I did not see how the inequality (iii) is derived from eq. (21)?", "limitations": "I did not see specific discussions on the limitations and broader societal impacts. \n\nThis does not decrease my score, and it would be better if the authors provide some.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper proposes a stochastic variant of MGDA to address the MOO problem.\n\n2. Optimization convergence analysis is provided with improved complexity over [12] without bounded function values assumption, and with improved complexity over [11] with bounded function values assumption.\n\n3. Experiments on MTL benchmarks demonstrated the superior performance of the proposed methods.", "weaknesses": "## Soundness\n### Lack of justification of some claims\n\nSee __Questions__-1,2.\n\n\n### Some steps of the proof is ambiguous or unclear\n\nSee __Questions__-3,4.\n\n### Theoretical and practical benefits of the proposed algorithm over the simple unitary scalarization (GD or SGD) baseline are unclear\n\n1. The algorithm is not very efficient. In Theorems 1, 2, with a constant $\\lambda$, it requires the inner loop iterations $S = \\mathcal{O}(T^3)$, and each step of the inner loop needs to compute a projection to the simplex, which adds more time complexity to the MGDA based algorithms as they already require computing $K$ gradients at each outer iteration comparing to $1$ gradient for GD or SGD.  \nHow does your algorithm compare to the simple SGD baseline in terms of convergence to Pareto stationary point in clock time? It would be better if some evaluations and discussions regarding this can be provided.\nE.g., in Table 6 or other experiments, compare with the time and performance of the simple SGD baseline.\n\n5. What is the theoretical benefit of this proposed algorithm compared to SGD of unitary scalarization, as the latter can also converge to Pareto stationary (PS) point and is more efficient?   \nFor example, in [12], in addition to the convergence to PS point, Lemma 2 is provided to justify the convergence of MoCo to the desired MGDA direction, does similar results apply for the proposed algorithm also?\n\n2. In the experiments, one baseline method with unitary scalarization is needed, as it has been shown in prior works [a,b] that unitary scalarization outperforms MGDA-based algorithms in some practical applications.  \nI understand that experiments with varying $\\lambda$ are provided, which becomes close to GD with larger $\\lambda$, but they are still not the same. Instead I would expect an ablation study with varied $\\beta_t$, and especially $\\beta_t = 0$.\n\n>[a] Vitaly Kurin et al. \"In Defense of the Unitary Scalarization for Deep Multi-Task Learning\"\n\n>[b] Derrick Xin et al. \"Do Current Multi-Task Optimization Methods in Deep Learning Even Help?\"\n\n### Technical novelty is limited\n\nNovelty in terms of proof techniques is limited, the proof mainly follows that of [12].\n\n## Minor\n\n1. Appendix C.2, line 530, \"satisfies\" -> \"satisfy\"\n2. Move Table 4 to Section 6.2\n3. In Appendix D.1, LHS of Equation below line 591, \"$E$\" -> \"$\\mathbb{E}$\"\n\n\n\n================UPDATE==========================\n\nTo avoid unnecessary misunderstandings, and unevidenced accusations, I change the word *honest* to *accurate* in my previous comment and also update my final comments and suggestions below.\n\nI appreciate the reviewers carefully checking the code and I also appreciate the authors clarifying what they implemented in the rebuttal. \n\nMy current score is based on the theoretical contributions and also conditioned on the authors can correctly implement and report the results with double sampling. Otherwise it could be confusing.\n\n=================================================", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1. How does your algorithm compare to the simple SGD baseline in terms of convergence to Pareto stationary point in clock time?**\n\n**A:** For the SGD baseline, we use the implementation by [1].  The experiments on Cityscapes, NYU-v2, and MT10 are provided in  Table 1-3 in the global response PDF. It can be seen that SGD outperforms others on a specific task but achieves a worse overall performance than our SDMGrad method. The clock time comparison is provided in Table 3, where it can be seen that the SGD baseline is faster than SDMGrad but slower than SDMGrad-OS.\n\n[1] Liu, Bo, et al. \"Conflict-averse gradient descent for multi-task learning.\" Advances in Neural Information Processing Systems 34 (2021): 18878-18890.\n\n**Q2. What is the theoretical benefit of this proposed algorithm compared to SGD of unitary scalarization, as the latter can also converge to Pareto stationary (PS) point and is more efficient?**\n\n**A:** Great question! Although SGD of unitary scalarization can achieve a faster convergence rate, our method is more flexible and general to enjoy the theoretical advantages of both SGD and MGDA. On the one hand, our method reduces to this SGD type of method for a large $\\lambda$ (which achieves a much higher efficiency as shown in Corollary 2). On the other hand, for a smaller $\\lambda$, our method with iteratively optimized weights can enjoy the benefits of MGDA type methods in mitigating the gradient conflict during the optimization process. Indeed, it has been shown in [2] that the weight changing methods like MGDA strike a better tradeoff among optimization, generalization, and gradient conflict than static weighting methods like SGD.  \n\n[2] Chen, Lisha, et al. \"Three-Way Trade-Off in Multi-Objective Learning: Optimization, Generalization and Conflict-Avoidance.\" arXiv preprint arXiv:2305.20057 (2023). \n\n**Q3. In the experiments, one baseline method with unitary scalarization is needed, as it has been shown in prior works [a,b] that unitary scalarization outperforms MGDA-based algorithms in some practical applications. And compare the case with $\\beta_t=0$.**\n\n**A**: The comparison results of unitary scalarization [a] are shown in Tables 1 and 2 in the global response. In general, it can be seen that our SDMGrad outperforms unitary scalarization under different metrics. From Table 3 in the global response, it can be seen our SDMGrad-OS is faster than unitary scalarization due to the efficient task sampling. \nThe ablation study of $\\beta_t=0$ is also shown in Tables 1 and 2. It can be seen that our method with $\\beta_t=0$ performs poorly in these experiments. This confirms the importance of the $w$ updates. \n\n[a] Kurin, Vitaly, et al. \"In defense of the unitary scalarization for deep multi-task learning.\" Advances in Neural Information Processing Systems 35 (2022): 12169-12183.\n\n**Q4. In Section 4.2, line 170-172, why is the case \"the objective in eq. (8) is merely convex w.r.t. w, it can only guarantee the convergence of at least one iterate (not necessarily the last one) to the solution \"?**\n\n**A:** Sorry about the confusion and thanks for pointing this reference out for us! After careful checking, we find that the analysis in [c] (Theorem 2 therein) on convex functions relies on additional assumptions like bounded estimators and domains, which may be restrictive in our MOO setting. To make our claim more rigorous, we will revise our sentence to “To ensure the last-iterate convergence, one possible approach is to add a quadratic regularization term for smoothing.” \nThe results for the guarantee of last-iterate convergence of objective in eq. (9) can be found in Lemma 3 of the appendix. We will clarify this in the main body. \n\n**Q5.The use of smoothing constant $\\rho$ seems to be redundant since you already have another regularization term $\\lambda g_0$, which makes the update direction close to $g_0$. Using the regularization term $\\rho\\\\|w\\\\|^2$ has a similar effect of making the update direction close to a uniform combination of gradients of all objectives.**\n\n**A:** We want to clarify that these two regularization terms serve different purposes. The regularizer $\\lambda\\langle g_0,d\\rangle$ makes the update direction close to $g_0$, whereas the quadratic term is to make the eq.(9) strongly convex to establish the convergence rate guarantee. In other words, the smoothing term $\\rho\\\\|w\\\\|^2$ is necessary here because the regularization $\\lambda\\langle g_0,d\\rangle$ cannot make the problem in eq. (9) strongly convex.\n\n**Q6. In Proposition 1, Equation (11), the LHS has two expectations, what are the specific distributions for these two expectations? In the proof of Proposition 1, Appendix C.1, line 522, how is the condition on $\\theta_t$ removed in the first equation of (21)?  In most parts of the proof,  $\\mathbb{E}[\\cdot]$is used for both conditioning on $\\theta_t$ and without conditioning on $\\theta_t$. E.g. line 533 in the Appendix, Eq (24) is \"conditioning on $\\theta_t$\", and later on in line 538 Eq(26) is \"unconditioning on $\\theta_t$\".**\n\n**A:** Sorry for the confusion. In eq. (11), the inner expectation is conditioning on $\\theta_t$ but the outer expectation takes the randomness over $\\zeta, w_{t,S}, \\theta_t$. \nIn line 522, the inner expectation is indeed conditioned on $\\theta_t$, and we remove the condition on $\\theta_t$ based on the fact that $\\mathbb{E}[\\mathbb{E}[A|B]]=\\mathbb{E}[A]$. We will make this clear in the proof. \nTo make it clearer, we will use $\\mathbb{E}[\\cdot]$ to denote the expectation unconditioning on $\\theta_t$, and use $\\mathbb{E}[\\cdot |\\theta_t]$ to denote the expectation conditioning on $\\theta_t$.\n\n**Q7. In Appendix C.2, Line 533-534, I did not see how the inequality (iii) is derived from eq. (21)?**\n\n**A:** Sorry for the confusion. The detailed steps can be found in the global response.\n\n\n"}, {"review_id": "ogyqrAOBQA", "reviewer": "Reviewer_ft1r", "summary": "This paper introduces the stochastic direction-oriented multi-objective gradient descent (SDMGrad) and SDMGrad-OS (OS stands for objective sampling). The idea of SDMGrad is to make the objective “direction-oriented”, which is done by regularizing the descent direction towards a specific direction. This direction is chosen to be the average of all gradients, which would allow the regularizer to interpolate the algorithm between multiple-gradient descent and regular gradient descent. This formulation is similar to CAGrad, but results in a simpler stochastic analysis and a simpler algorithm. The experiments show that, for a well-tuned regularization parameter, SDMGrad’s performance is competitive with the state-of-the-art. The objective sampling procedure in SDMGrad-OS makes it run significantly faster than SDMGrad when the number of objectives is large. Analysis for both methods is provided with good sample complexities.", "questions": "- Which method do you use to project the weights onto the simplex? Is the projection costly?\n- Have you considered relaxing the simplex constraint? Would it make sense to use the closed-form minimum $w$ for unconstrained $w$?\n- Have you considered a different regularizer for $w$? How do you set $\\rho$ in practice?", "limitations": "None.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The idea is clear, the formulation is sound, and the algorithm is simple to implement.\n- The formulation allows for a better stochastic analysis and simpler algorithm. The sample complexity achieved by the algorithm is good.\n- SDMGrad generalizes MGDA and GD, and is a better formulation of CAGrad.\n- The code is available, so experiments can be reproduced.\n- Performance is good overall, and can be better for fine-tuned lambda.\n- Objective sampling helps when the number of objective is large. The analysis also justifies this procedure, which is a good contribution.", "weaknesses": "- Need to tune lambda to get better results. It does not seem to be easy to pick a good starting point as the algorithm is not very robust to the choice of lambda. Also, it is not clear how to choose $\\rho$.\n- The algorithm interpolates between MGDA and GD (with $w$ regularization), so the algorithmic novelty is limited.\n- In equation 4, $h_{t,i}$ is not explained.\n- The improvements are not significant, and that is for the best choices of $\\lambda$. For other choices of $\\lambda$, it might be worse. It seems to be on par with CAGrad and MoCO, which is competitive.\n- In the appendix, the authors mention Young's inequality for some steps, but I think it's Cauchy-Schwartz, though I might be mistaken.\n- Note that the Lipschitzness (bounded gradient) assumption of $L_i$ would not work with strongly convex losses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1.  Need to tune lambda to get better results. It does not seem to be easy to pick a good starting point as the algorithm is not very robust to the choice of lambda. Also, it is not clear how to choose $\\rho$.**\n\n**A:** Good question! From the formulation of our proposed SDMGrad, we know that it becomes close to SGD when $\\lambda$ is large, and close to MGDA with a small $\\lambda$. We first try to identify the large and small values of $\\lambda$ where the performance shows consistency with our formulation. In experiments, we find that $\\lambda=0.1$ and $\\lambda=10$ work well. Next, we narrow the range by trying different values in [0.1, 10]. Specifically, we search with $\\lambda \\in [0.1, 1, 2, 5]$ and evaluate which choice is better. Overall, this grid search takes small efforts and the performance improvement is robust to certain ranges (e.g., [0.1,1] used in our search) within $[0.1,10]$. \n\nThe parameter $\\rho$ is used for theoretical analysis and guarantees that the proposed method works well in the worst case. In the experiments (which are not necessarily the worst case), we find the performance when $\\rho=0$ is good enough. Thus, we make this choice for simple implementation. \n\n**Q2. The algorithm interpolates between MGDA and GD (with w regularization), so the algorithmic novelty is limited.**\n\n**A:** Let us explain the algorithmic novelty of our method as follows. \nFirst, our method has substantial differences from existing stochastic MGDA-type methods. For example, MoCo constructs an additional auxiliary sequence $Y_k$ to approximate the gradients in MOO with decreasing estimation error, whereas our approach leverages a double-sampling mechanism that admits a near-unbiased multi-gradient estimation at each iteration. This type of approach is new in the literature.  \nSecond, our regularization is new and contains careful designs. Compared to the most relevant CAGrad method that uses a constraint to regularize the update direction close to $g_0$, our regularization not only enjoys such direction-oriented benefit, but also admits a provable algorithmic design in the challenging stochastic setting. \nThird, our double-sampling-based approach is flexible to incorporate the objective sampling for better efficiency. To the best of our knowledge, this is the first result for a stochastic MOO algorithm with objective sampling.  \n\n**Q3. What is $h_{t,i}$ in equation 4?**\n\n**A:**  $h_{t,i}$ is defined in eq. (6) of MoCo paper in the ICLR version, where $h_{t,i}$ denotes a stochastic estimator of $\\nabla L_i(\\theta)$ at t-th iteration. We will clarify this in the revision. \n\n**Q4. In proof, Young’s inequality or Cauchy-Schwarz.**\n\n**A:** Thanks! We will double check the proofs and make the revisions accordingly.\n\n**Q5. Note that the Lipschitzness (bounded gradient) assumption of $L_i$ would not work with strongly convex losses.**\n\n**A:** Note that in our setting,  the function $L_i(\\theta)$ is generally nonconvex rather than strongly convex. The problem in eq. (9) is strongly convex w.r.t. $w$ rather than $\\theta$.  \n\n**Q6. Which method do you use to project the weights onto the simplex? Is the projection costly?**\n\nA: The computation of the projection to the probability simplex we use is the Euclidean projection proposed by [1], which involves solving a convex problem via quadratic programming. The implementation used in our experiments follows the repository in [2], which is very efficient in practice.  \n[1] Weiran Wang, and Miguel Á. Carreira-Perpiñán. Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application. arXiv preprint arXiv: 1309.1541\n\n[2] Adrien Gaidon. Compute Euclidean projections on the simplex or L1-ball.\n\n**Q7. Have you considered relaxing the simplex constraint? Would it make sense to use the closed-form minimum w for unconstrained w?**\n\n**A:** Good question! It is possible to use the closed-form minimum $w$ if the full gradients are used. For example, for the two-objective example provided by the MoCo paper (see eq. (5) therein), a closed-form solution is provided. This solution is accurate when full gradients are taken. However, when only stochastic gradients are available, they show that a large bias can be induced. Thus, it may be challenging to apply this idea in the stochastic setting, which is the focus of this paper. However, we would like to leave such exploration for future study.\n\n**Q8. Have you considered a different regularizer for w? How do you set it up $\\rho$ in practice?**\n\n**A:** Great question! Since the main purpose of the regularizer for $w$ is to make the problem in eq. (9) strongly convex such that the theoretical convergence guarantee can be established. For this reason, we use the simplest quadratic regularizer. However, it is possible to use other strongly-convex regularizers for a stronger theoretical guarantee. We would like to leave it for future study. \n\nIn experiments, we tune $\\rho$ and find the best range to be $[0,0.1]$. For a simple implementation, we simply set $\\rho=0$ in all experiments.  \n\n"}, {"review_id": "jbuOpJgMBN", "reviewer": "Reviewer_tz6S", "summary": "This paper proposes a direction-oriented multi-objective gradient descent algorithm under stochastic gradient settings. The authors show that the algorithm can benefit from the direction-oriented mechanism and ensure optimal convergence. In addition, an objective sampling strategy is applied to the proposed algorithm for the case of many objectives.", "questions": "No", "limitations": "Novelty is limited.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "This paper studies an important problem in multi-objective optimization. It has solid analysis and experiments.\n\n", "weaknesses": "1. The key benefit of MoCo compared with CR-MOGM is that the direction can gradually be unbiased to the one calculated by full-batch gradients (Lemma 2). However, there is no respective analysis of the direction bias in the analysis.\n\n2. I check that CR-MOGM has the same sample complexity as SDMGrad in the non-convex setting. Note that $O(T^{-1/4})$ in CR-MOGM is for the first-order convergence of $\\|\\|G_t w_t\\|\\|$, and for the second-order convergence $\\|\\|G_t w_t\\|\\|_2^2$ is $O(T^{-1/2})$. Usually, the first-order one is more often used.\n\n3. The idea is very similar to [1], which studies multi-objective online learning that can be easily reduced to stochastic settings. [1] also uses a regularization to restrict the direction to be closed to a prior preference.\n\n4. CR-MOGM has not been compared in the experiments.\n\n5. I am not convinced with the motivation to face many objectives problems as stated in Line 46. It is known that the many objective problem is hard to be solved by Pareto optimization, since when the number of objectives becomes too large, the Pareto set will cover nearly the majority of the space, then optimizing towards Pareto optimality is meaningless.\n\n\n[1] Jiang et al. Multi-Objective Online Learning. ICLR 23.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1. There is no respective analysis of the direction bias in the analysis.**\n\n**A:** Our analysis of the direction bias can be found in Proposition 1. It can be seen that the bias is upper-bounded by an exponentially decaying term $4C_g^2(1-2\\beta_t\\rho)^S$ plus two small terms $\\frac{\\beta_tC_g^2C_1}{\\rho}$ and $\\rho$. This error bound is controllable by selecting stepsize $\\beta_t$ and smoothing constant $\\rho$ properly small.  \n\n**Q2. CR-MOGM has the same sample complexity as SDMGrad in the non-convex setting.**\n\n**A:** Thanks for pointing this out for us! We have double checked the sample complexity of CR-MOGM and the second order convergence is indeed $\\mathcal{O}(T^{-\\frac{1}{2}})$. We will revise it accordingly. \n\n**Q3. The idea is similar to [1].\n[1] Jiang et al. Multi-Objective Online Learning. ICLR 23.**\n\n**A:** Thanks for pointing this paper out for us! However, we believe our work has substantial differences from this work:\n\n1. First, we focus on different objective functions. [1] studied the multi-objective online convex optimization problem with convex objective functions, whereas we focus on the stochastic multi-objective optimization with nonconvex objective functions.\n\n2. Second, our regularizer is different from theirs. In specific, the $l_1$-regularizer in [1] is to use time-varying historical information for stabilizing the algorithm performance, whereas our regularizer $\\lambda\\langle g_0, d\\rangle$ is to regularize the update direction $d$ close to a fixed direction $g_0$.\n\n3. Third, algorithms are different. The method in [1] is motivated by mirror descent, whereas ours is an SGD-type approach with a double-sampling scheme. \n\nWe will cite this relevant paper in the revision and provide a detailed discussion for comparison. \n\n**Q4. CR-MOGM has not been compared in the experiments.**\n\n**A:** The official codes of CR-MOGM have not been released, so we implement them by ourselves. We provide the preliminary results of CR-SDMGrad on Cityscapes and NYU-v2 in Table 1-2 in global response. It can be seen that our method performs comparably to CR-SDMGrad on Cityscapes, but on NYU-v2, our method is significantly better. \n\n**Q5. I am not convinced with the motivation to face many objectives problems as stated in Line 46. It is known that the many objective problem is hard to be solved by Pareto optimization, since when the number of objectives becomes too large, the Pareto set will cover nearly the majority of the space, then optimizing towards Pareto optimality is meaningless.**\n\n**A:** Sorry for the confusion and let us clarify the motivation here. In lines 44-46, we mentioned that MoCo needs an assumption that the number $T$ of iterations is large at an order of $K^{10}$, where $K$ is the number of objectives. This is a strong assumption even for a small number $K=10$ (in this case, $T$ is as large as $10^{10}$). Then, our motivation is to remove this requirement rather than the need to face many objectives. We will clarify this in the revision.\n\n\n"}, {"review_id": "SarSNcmzFY", "reviewer": "Reviewer_ZeY5", "summary": "Authors presented a new stochastic gradient method for multi-objective optimization (MOO) problem, called SDMGrad.\nCompared with previous SMG, they claimed SDMGrad dose not need to increase the batch size linearly with the iteration numbers.\nCompared with previous MoCo, they claimed SDMGrad could be applied into situations with large number of objectives.", "questions": "1. Could you detail the advantages and novelty of SDMGrad over MoCo?\nFirst, Line 5 in Algorithm 1 seems similar with Equation 4 of MoCo.\nSecond, authors commented MoCo \"a relatively strong assumption that the number T of iterations is much larger than the number K of objectives.\" Well, in the real industrial systems, the number T of iterations could be millions, and the number K of objectives (maybe 3 or 10?) is obviously much smaller than T. So this is a natural assumption to me and hence weaken the necessity to improve MoCo from this perspective.\n\n2. Why the equation in the Line 5 of Algorithm 1 is an unbiased estimation? (Line 175)\n\n3. The equation after line 175 is the derivative of Equation 9, right? Why we need two different data samples: \\xi and \\xi\\prime?\nand how do we implement this in the mini-batch training? sample two mini-batches in each s?\n\n4.  Line 5 in Algorithm 1, why we need \\prod_{W}? what is the meaning of this? In Equation 3, W is a set with infinite possibilities of w. How does this multiply work? And this is element-wise multiple?\n\n\n", "limitations": "No social impact.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors presented a new stochastic gradient method for multi-objective optimization (MOO) problem, called SDMGrad.\nDetailed background is provided to help understand the history of MOO.\nAnd various experiments show that the new method can outperform the previous methods.\nBut I need to ask some questions to fully understand the novelty of this method.", "weaknesses": "I need to ask some questions to fully understand the novelty of this method.\nAlso, some technically details are presented very clear, I will also post some questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1. Could you detail the advantages and novelty of SDMGrad over MoCo? First, Line 5 in Algorithm 1 seems similar with Equation 4 of MoCo. Second, authors commented MoCo \"a relatively strong assumption that the number T of iterations is much larger than the number K of objectives.\" Well, in the real industrial systems, the number T of iterations could be millions, and the number K of objectives (maybe 3 or 10?) is obviously much smaller than T. So this is a natural assumption to me and hence weaken the necessity to improve MoCo from this perspective.**\n\n**A:** Good question! After reading MoCo paper carefully, we guess that you refer to eq. (10) of the ArXiv version of MoCo paper. \nFor the first question, line 5 of our method and eq. (10) of MoCo have some key differences. In eq. (10) of MoCo, an auxiliary tracking variable $Y_k$ is used as a stochastic estimator for the full gradient $G(\\theta_k)$, and the direction bias $\\\\|d(x_k)-Y_kw_k\\\\|$ can be shown to decrease iteratively. As a comparison, our approach directly uses the stochastic gradients $G(\\theta_t; \\xi), G(\\theta_t; \\xi^\\prime)$ in $w$ updates, and show that the direction bias is sufficiently small at each iteration. \nFor the second question, we wanted to claim that the assumption that $T$ is large at an order of $K^{10}$ is relatively strong. For example, $T$ can be as large as $10^{10}$ even though we choose a relatively small $K=10$. We will make this clear in the revision. \n\n**Q2.  Why the equation in the Line 5 of Algorithm 1 is an unbiased estimation? Why we need two different data samples: \\xi and \\xi\\prime? and how do we implement this in the mini-batch training? sample two mini-batches in each s?**\n\n**A:** Great questions! Since we use two independent sample data $\\xi$ and $\\xi^\\prime$, $G(\\theta_t;\\xi)$ and $G(\\theta_t; \\xi^\\prime)w_{t,s}+\\lambda G_0(\\theta_t;\\xi^\\prime)$ are independent w.r.t.~$\\xi,\\xi^\\prime$. Based on the fact that $\\mathbb{E}[AB]=\\mathbb{E}[A]\\mathbb{E}[B]$ if A and B are independent, we can get\n\n$\\mathbb{E}[G(\\theta_t;\\xi)^T(G(\\theta_t; \\xi^\\prime)w_{t,s}+\\lambda G_0(\\theta_t; \\xi^\\prime))+\\rho w_{t,s}] = \\mathbb{E}[G(\\theta_t;\\xi)^T]\\mathbb{E}[G(\\theta_t; \\xi^\\prime)w_{t,s}+\\lambda G_0(\\theta_t; \\xi^\\prime)]+\\rho w_{t,s}$\n\n$=G(\\theta_t)^T(G(\\theta_t)w_{t,s}+\\lambda G_0(\\theta_t))+\\rho w_{t,s}$. Therefore, it is an unbiased estimation w.r.t. data sampling. Then, if there is one sample data $\\xi$, then $G(\\theta_t; \\xi)$ and $G(\\theta_t; \\xi)w_{t,s}+\\lambda G_0(\\theta_t; \\xi)$ have correlation with each other, and hence it could lead a biased estimation. This is the reason why we use double sampling in the gradients.\nIn experiments, we found that using two different mini-batches performs similarly to using the same mini-batch. Thus, for simple implementation, we use the same mini-batch for gradient constructions. We also provide additional experiments with two different mini-batches Table 1 shown in above to support this observation.\n\n**Q3. Line 5 in Algorithm 1, why we need \\prod_{W}? what is the meaning of this?**\n\n**A:** This notation $\\prod_{\\mathcal{W}}$ denotes the projection on the probability simplex. We will clarify this in the revision. \n"}, {"review_id": "mFZDfplPey", "reviewer": "Reviewer_5qpL", "summary": "The contributions are as follows:\n- First, this work gives a new framework of direction-oriented multi-objective optimization.\n- Second, they propose an algorithm, SDMGrad (and an objective sampling version when the number of objectives is large)\n- Third, they give a convergence analysis for their algorithm and show that it has improved complexity compared to previous work\n- Finally, they show good empirical performance on both supervised learning (semantic segmentation + depth estimation) and reinforcement learning (robot manipulation task) paradigms ", "questions": "- Could you outline, in intuitive terms, a sketch of the proof of Theorem 1? Is the proof inspired by any previous work (such as MoCo or CR-MOGM)?\n- Is there any chance to remove or relax the bounded gradient assumption?\n- Why can the convergence rate (of both your algorithm and MoCo) improve so much with a bounded function assumption?\n- Do you have any sense how things would change if you remove the smoothness assumption?", "limitations": "No limitation section is included. ", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Overall, the paper is clearly written, the new algorithm is straightforwardly effective, and the convergence rates beat existing bounds with fewer convergence assumptions. More specifically:\n- The proposed formulation is a generalization of existing algorithms, CAGrad and SGD\n- Algorithm 1 is intuitive to understand and memory-efficient to implement \n- The convergence rate beats the previous MoCo by epsilon^2, and even is able to handle the case where the number of objectives is large (via the objective sampling version)\n- Experiments are conducted well and show the effectiveness of the method in practice", "weaknesses": "- I am unsure about the applicability of the newly proposed formulation in the context of multi-objective optimization. Could the authors share some examples where this direction based regularization would be useful? \n- Also, I am not sure how the -1/2||d||^2 term will affect the regularization, as it seems added for the convenience of the algorithm and convergence proof.\n- Combining the above two points, properly choosing $$\\lambda$$ also seems like it is important but would add an extra hyperparameter (making things more costly, empirically). For the examples you could give above, can you also share how this parameter would be chosen? \n- I believe the work would benefit from a short discussion of the theorems and proof challenges in the main text. Currently, there are four theorems listed with little discussion of any proof details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1. Could the authors share some examples where this direction based regularization would be useful?**\n\n**A:** This direction based regularization would be useful if one target is to minimize a specific objective function, e.g., the average loss in MTL. A more specific example is provided in A.1 of the appendix, where the goal is also to find the minimizer (the black point in the Pareto front) of the average loss of two tasks. From Fig. 2, it can be seen that MGDA without such regularization converges to different points in the Pareto front when starting from different points. As a comparison, our method can converge to this target black point from different initializations. This supports the importance of our regularization. \n\n**Q2.  Also, I am not sure how the -1/2$\\\\|d\\\\|^2$ term will affect the regularization, as it seems added for the convenience of the algorithm and convergence proof.**\n\n**A:** The regularization $-1/2||d||^2$ is necessary here to ensure the boundedness of the magnitude of the direction $d$. Without this regularizer, it can be seen that eq. (6) that the maximizer $d^*$ can go to infinity, and hence makes the problem meaningless. This regularizer is not new, and has also been used in works such as MGDA, CR-MOGM [1], etc.\n [1] Zhou, Shiji, et al. \"On the convergence of stochastic multi-objective gradient manipulation and beyond.\" Advances in Neural Information Processing Systems 35 (2022): 38103-38115.\n\n**Q3. Choosing $\\lambda$ also seems like it is important but would add an extra hyperparameter (making things more costly, empirically). For the examples you could give above, can you also share how this parameter would be chosen?**\n\n**A:** From the formulation of our proposed SDMGrad, we know that it becomes close to SGD when $\\lambda$ is large, and close to MGDA with a small $\\lambda$. We first try to identify the large and small values of $\\lambda$ where the performance shows consistency with our formulation. In experiments, we find that $\\lambda=0.1$ and $\\lambda=10$ work well. Next, we narrow the range by trying different values in [0.1, 10]. Specifically, we search with $\\lambda \\in [0.1, 1, 2, 5]$ and evaluate which choice is better. Overall, this grid search takes small efforts and the performance improvement is robust to certain ranges (e.g., [0.1,1] used in our search) within $[0.1,10]$. \n\n**4. Currently, there are four theorems listed with little discussion of any proof details. Could you outline, in intuitive terms, a sketch of the proof of Theorem 1? Is the proof inspired by any previous work (such as MoCo or CR-MOGM)?**\n\n**A:** Great suggestion! We summarize our proofs as following three main steps:\n1. Characterization of the last-iterate convergence of SGD in solving eq. (9).\n2. Use Proposition 1 to upper-bound the bias of the update vector $d$. The main step here is to use an intermediate quantity $G(\\theta_t)w_{t, \\rho, \\lambda}$ to split the bound into the error in solving eq. (9) and the bias induced by smoothing.\n3. Combine the previous two steps with a decent lemma of each objective to derive the final convergence. \n\nWe will provide a proof sketch in the revision.\n\n**Q5. Is there any chance to remove or relax the bounded gradient assumption?**\n\n**A:** Interesting question! It is hard to remove this assumption given the current framework. This is because when approximating the true update direction  $d^*=G(\\theta)w^*_\\lambda+\\lambda G_0(\\theta)$, we cannot get the exact $w^*_\\lambda$ but an estimate $\\hat w$, and hence if the gradient $G$ is unbounded, one approximation error $\\\\|G(\\theta)(w^*_\\lambda-\\hat w)\\\\|$ can be uncontrollable. This is why the assumption is necessary here. \n\n**Q6. Why can the convergence rate (of both your algorithm and MoCo) improve so much with a bounded function assumption?**\n\n**A:** Good question! Without bounded function assumption, we need to add a quadratic term $\\rho\\\\|w\\\\|^2$ to smooth the problem w.r.t. $w$, which makes the complexity to be proportional to $\\frac{1}{\\rho}$ (see proof of Theorem 1). Since the smoothing factor $\\rho$ is sufficiently small, the complexity becomes large. When having this assumption, we do not require such a smoothing trick, and hence improve the complexity quite a lot.  \n\n**Q7.Do you have any sense how things would change if you remove the smoothness assumption?**\n\n**A:** Interesting question! First we note that solving the eq. (9) w.r.t. $w$ keeps unchanged. The main change lies in optimization w.r.t. the variable $\\theta$, i.e., line 7 of our Algorithm 1. Some new challenges will arise here. For example, it is not clear if $d=G(\\theta_t;\\zeta)w_{t,S}+\\lambda G_0(\\theta_t;\\zeta)$ still achieves a small bias for approximating true direction $d^*$. Decent lemma for each objective in our proof may not work here. We guess some techniques in [1] or some proximal methods may be helpful here, and we would like to leave it for future study.\n\n[1] Ohad Shamir et al. \"Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes\".\n\n"}, {"review_id": "5CADPUsjfq", "reviewer": "Reviewer_81UB", "summary": "This paper proposes a gradient manipulation method named SDMGrad for multi-task learning (MTL). SDMGrad improves the previous MGDA method by using two constraints. The first one is to constrain the common descent direction nearby the one computed with a specific preference (such as the average direction), which is similar to the previous CAGrad method. The second one is to add a regularization term for the computed weights, which is the same as the previous MoCo method. To reduce the computational cost, partial tasks are randomly selected to compute their gradients in SDMGrad, which is called SDMGrad-OS and is similar to the previous RLW method.\n\nTheoretically, a stochastic non-convex convergence analysis for the proposed methods is provided. Empirically, experiments on multi-task supervised learning and reinforcement learning are conducted but some important baselines are missing.", "questions": "1. The novelty of the proposed methods is limited. The proposed SDMGrad method improves the previous MGDA method by using two constraints.\n- constraining the common descent direction nearby the one computed with a specific preference, as shown in Eq. (6). This is very similar to CAGrad in Eq. (7). The only difference is the norm constraint used in CAGrad while the angle constraint used in SDMGrad. Thus, what is the motivation and advantage to use Eq. (6)?\n- adding a regularization term for the computed weights in Eq. (9), which is the same as MoCo. \n- SDMGrad-OS reduces the computational cost in SDMGrad by randomly sampling tasks, which is similar to RLW [1]. In RLW, loss/gradient weights are randomly sampled from a distribution (such as Normal and Bernoulli) at each iteration. If the sample distribution is Bernoulli-family, it is equivalent to randomly sampling task losses/gradients to optimize at each iteration.\n\n&ensp;&ensp; In a word, it is hard to find something new or interesting in Section 4.\n\n2. What is the meaning of \"propose a new direction-oriented multi-objective problem\" in Lines 3-4, Line 139, and Line 313? Maybe \"formulation\" is more appropriate than \"problem\".\n3. $L_i$ in the last of Line 23 is quite confusing. It is better to use more clear notation.\n4. Lines 24-25: \"MTL aims to solve an average loss for all $K$ tasks\" is wrong. \n5. Line 27: why MOO **cannot** find a common parameter $\\theta$ that achieves optima for all objectives? MOO can, but rarely. The description of \"parameter $\\theta$ that minimizes all objective functions\" is wrong. \n6. Eq. (4): what is the meaning of $h_{t, i}$?\n7. Line 133: $\\mathbb{R}^K\\rightarrow\\mathbb{R}^m$\n8. Lines 145-147: in what scenarios? It is better to provide some examples here.\n9. Line 176 in the text and Step 5 in Algorithm 1: why two different sampled data is used for the update of $\\omega$? From the code in the supplementary material, the same sampled data is used in the implementation.\n10. Proposition 1: it seems the bound is meaningless when $\\rho\\rightarrow0$.\n11. Lines 447-448 in Appendix: the experimental setting of adding zero-mean Gaussian noise is following MoCo but without citation. Besides, MoCo does not been compared in this toy example section.\n12. Section B in Appendix: \"$g_0$ denotes the average gradient\" in Line 483 but $g_0=G_0(\\theta)=G(\\theta)\\tilde{\\omega}$ in Eq. (13). What does $\\tilde{\\omega}$ denote? Is $G_0$ a vector here? It is confusing because capital $G$ denotes a matrix and lowercase $g$ denotes a vector in Eq. (13). The last line in Eq. (13): $G(\\theta_t)\\rightarrow G(\\theta_t)\\omega$.\n13. Eq. (17) in Appendix: Is it possible to provide a detailed derivation of step (i)? \n14. Hyperparameter selection.\n- how to set $\\rho$? From the code in the supplementary material, it seems $\\rho=0$ in the implementation. So why? If so, the regularization term in Eq. (9) and the bound in Proposition 1 are meaningless.\n- $\\lambda$ in the proposed SDMGrad is searched for the best. How about the hyperparameters of baselines? From Table 8 in Appendix, CAGrad performs significantly better than the results in Table 4 in the main text.\n- how to set $n$ for SMDGrad-OS?\n15. Line 289: the definition of $\\Delta m$ is wrong since some task has more than one metric (for example those tasks in Cityscapes and NYU-v2).\n16. Lack of some important baselines.\n- Nash-MTL [2] outperforms the proposed SMDGrad in all benchmark datasets, i.e., Cityscapes, NYU-v2, MT10, and MT50. Besides, the running time of Nash-MTL is shorter than SMDGrad-OS in MT10.\n- It is better to compare with more baselines such as RLW [1], GradNorm [3], IMTL [4], and so on.\n17. SegNet is out-of-dated and performs unsatisfactory. It is better to conduct experiments using a more powerful backbone, such as resnet50 and transformer.\n18. The results of SMDGrad-OS in Cityscapes and NYU-v2 datasets should be reported.\n19. The claim of SMDGrad-OS can deal with the case where the number of objectives is large (Lines 10-11) while MoCo does not (Lines 44-47). However, there is no experiment to support this. \n20. Lines 94-96: there is no experiment to support that the proposed SMDGrad is model-agnostic. \n \n\n\n\n\n----\n[1] Reasonable Effectiveness of Random Weighting: A Litmus Test for Multi-Task Learning. TMLR 2022.\n\n[2] Multi-Task Learning as a Bargaining Game. ICML 2022.\n\n[3] GradNorm: Gradient Normalization for Adaptive Loss Balancing in Deep Multitask Networks. ICML 2018.\n\n[4] Towards Impartial Multi-task Learning. ICLR 2021.", "limitations": "N/A", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. This paper proposes a method for MTL.\n2. This paper provides a stochastic non-convex convergence analysis for the proposed methods.\n3. The code is provided.", "weaknesses": "1. The novelty of the proposed methods is limited. This paper aims to improve the previous MGDA method by adding several components. However, those components are similar to some existing work.\n2. Lack of some important baselines, especially Nash-MTL (ICML 2022), which outperforms the proposed SMDGrad in all benchmark datasets.\n3. The regularization term with a coefficient $\\frac{\\rho}{2}$ in Eq. (9) is one of the proposed improvements. However, the paper does not mention how to set $\\rho$. Besides, from the code in the supplementary material, it seems $\\rho=0$ in the implementation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Answer to Q1** We would like to clarify the novelty of our algorithmic designs and the difference from previous works.\n1. As we discussed in lines 152-158, optimizing the constraint-based regularization (see eq. (7)) in CAGrad involves the evaluations of product $\\\\|h_0\\\\|\\\\|g_w\\\\|$ and the ratio $\\\\|h_0\\\\|/\\\\|g_w\\\\|$, which can heavily complicate the design of unbiased stochastic gradient/multi-gradient in $w$ and $\\theta$ updates. As a result, CAGrad does not have performance guarantees in stochastic setting. As a comparison, our angle-based regularization admits very simple optimization steps in the stochastic setting (see line 5 and 7 of our Algorithm 1), while guaranteeing the convergence for general regularization constant $\\lambda$. Thus, developing a simple and provable stochastic MOO method under such direction-oriented mechanism is the motivation and advantage of our design in eq. (6).\n2. Our regularization term in Eq. (9) and the one in MoCo serves different purposes, and also lead to different analyses. In specific, our regularizer is to ensure the last-iterate convergence for solving Eq. (9), whereas the regularizer in MoCo is to ensure the Lipschitz continuity of the solution $w^*_{\\rho,0}(\\theta)$ (under our notations) w.r.t. $\\theta$. \n3. We agree that the task sampling is not new, but it is new to show that such sampling guarantees the near-unbiasedness of the gradient/multi-gradient in lines 5 and 7 of our Algorithm, and achieves an improved convergence guarantee. Previous works do not have such results. \n\n**Answer to Q2, 3, 7.** Many thanks. We will follow your suggestions to improve the presentation. \n\n**Answer to Q4.** We will revise this sentence to “The objective function of MTL is taking as the average loss over K objectives”. \n\n**Answer to Q5.** Sorry for the improper wording. We will revise it to “MOO rarely finds a common parameter $\\theta$ that achieves optima for all individual objective functions simultaneously”. \n\n**Answer to Q6.** Please refer to our answers to Q3 from the reviewer ft1r.\n\n**Answer to Q8.** The most relevant example is multi-task learning, whose objective function is an average loss for all tasks. Another possible case is that we have prior knowledge about the importance of different tasks, and the target is to optimize a weighted sum of loss functions for all tasks. \n\n**Answer to Q9.** In theory, please refer to our answers to Q2 from the reviewer ZeY5. In experiments, we found that using two different mini-batches performs similarly to using the same mini-batch. The result can be found in Table 1 in the global response.\n\n**Answer to Q10.** Note that in theory, the upper bounds are often derived in a uniform sense, i.e., hold for a class of objectives satisfying the assumptions. Thus, the $\\rho>0$ is necessary here to ensure the worst case in this class to achieve a performance guarantee. However, in practice, the problem may not be the worst case, and hence $\\rho\\rightarrow 0$ may still work well. \nIt is also worth mentioning that for another class of objectives under a bounded function value assumption, we do not need this $\\rho$ (Theorem 3 and 4).\n\n**Answer to Q11.** We will add the citation of MoCo. The results of reproduced MoCo can be found in Figure 1 in the global response PDF. \n\n**Answer to Q12.** Since we use $g_0$ to denote average gradient, $\\widetilde{w}$ denotes a vector whose elements are all $\\frac{1}{K}$, where $K$ is the number of objectives. Yes, $G_0$ is a vector. To remove the confusion, we will revise $G_0(\\theta)$ to $g_0(\\theta)$ in the revision. \n\n**Answer to Q13.** Note that eq. (9) is strongly convex w.r.t. w. Using the property of a smooth $\\mu$-strongly-convex function $f$ that $\\forall x, y, (\\nabla f(x)-\\nabla f(y))^T(x-y)\\geq\\mu\\\\|x-y\\\\|^2$, we can derive $(i)$. We will clarify it in our revision. \n\n**Answer to Q14.** Our selection takes following steps:\nThe parameter $\\rho$ is used only for theoretical analysis and for guaranteeing our method to work well in the worst case. In the experiments (which are not necessarily the worst case), we find the performance when $\\rho=0$ is good enough. Thus, we make this selection for simplicity. \nFrom the formulation of our proposed SDMGrad, we know that it becomes close to SGD when $\\lambda$ is large, and close to MGDA with a small $\\lambda$. We first try to identify the large and small values of $\\lambda$ where the performance shows consistency with our formulation. In experiments, we find $\\lambda=0.1$ and $\\lambda=10$ work well. Next, we narrow the range by trying different values in [0.1, 10]. Specifically, we search with $\\lambda \\in [0.1, 1, 2, 5]$ and evaluate which choice is better. For $n$, we make the same selection as the baseline CAGrad.\n\n**Answer to Q15.** Thanks! We revise the definition as:\n$\\Delta_m=\\frac{1}{K}\\sum_{k=1}^K(-1)^\\delta_k (M_{m,k}-M_{b,k})/M_{b,k}$, where $K$ is the number of metrics, $M_{b,k}$ is the value of metric $M_k$ obtained by the baseline and $M_{m,k}$ obtained by the compared method. $\\delta_k=1$ if a higher value is better for metric $M_k$ and 0 otherwise.\n\n**Answer to Q16.** For supervised learning, we add baselines including RLW, IMTL-G, and Nash-MTL in supervised learning and reinforcement learning. It can be seen from Table 3 in the global response PDF that our SDMGrad and SDMGrad-OS achieve higher success rate than NashMTL, while using much less time.\n\n**Answer to Q17.** We follow former works using SegNet as backbone and it is fair to compare.\n\n**Answer to Q18.** The numbers of tasks in Cityscapes and NYU-v2 are 2 and 3 respectively, which are already very small, and hence we do not apply task sampling in these two datasets. \n\n**Answer to Q19.** Please refer to added experiment in the global response.\n\n**Answer to Q20.** Following the CAGrad paper, all gradient manipulation methods such as CAGrad, MoCo, PCGrad, and MGDA are called as model agnostic because they manipulate gradients rather than models to avoid conflict. "}]

Author rebuttal:
**To all reviewers:**

We thank all reviewers for their time and valuable comments! Based on the reviewers’ suggestions, we have added the following additional experiments:
1. Comparison to additional baselines including SGD, unitary scalarization, RLW, IMTL, and NashMTL.
2. Running time comparison to unitary scalarization and MoCo.
3. Comparison to CR-MOGM.
4. Comparison between one data sample and two different data samples in the inner loop of SDMGrad.

Please refer to the attached PDF file for these experiment results.

**We also add details of how the inequality $(iii)$ is derived in Appendix C.2, Line 533-534.**

The detailed steps are shown as follows. 

$\\|G(\\theta_t)w_{t,\\lambda}^*+\\lambda G_0(\\theta_t)- G(\\theta_t)w_{t,\\rho,\\lambda}^*-\\lambda G_0(\\theta_t)\\|^2$
 $=\\|G(\\theta_t)w_{t,\\lambda}^*+\\lambda G_0(\\theta_t) \\|^2+\\| G(\\theta_t)w_{t,\\rho,\\lambda}^*+\\lambda G_0(\\theta_t)\\|^2-2\\langle G(\\theta_t)w_{t,\\lambda}^*+\\lambda G_0(\\theta_t) , G(\\theta_t)w_{t,\\rho,\\lambda}^*+\\lambda G_0(\\theta_t)\\rangle$
 $\\overset{(i)}{\\leq}\\|G(\\theta)w_{t,\\rho,\\lambda}^*+\\lambda G_0(\\theta_t)\\|^2-\\|G(\\theta)w_{t,\\lambda}^*+\\lambda G_0(\\theta_t)\\|^2$

 $\\overset{(ii)}{\\leq}\\frac{1}{2}\\rho,$

where $(i)$ follows from optimality condition.
 $\\langle G(\\theta_t)w_{t,\\lambda}^*+\\lambda G_0(\\theta_t) , G(\\theta_t)w_{t,\\rho,\\lambda}^*+\\lambda G_0(\\theta_t)\\rangle$
$\\geq\\langle G(\\theta_t)w_{t,\\rho, \\lambda}^*+\\lambda G_0(\\theta_t) , G(\\theta_t)w_{t,\\rho,\\lambda}^*+\\lambda G_0(\\theta_t)\\rangle=\\| G(\\theta_t)w_{t,\\rho,\\lambda}^*+\\lambda G_0(\\theta_t)\\|^2$.

Step $(ii)$ follows from $(iv)$ in eq.(21). It uses the optimality that $\\|G(\theta)w_{t,\rho,\lambda}^*+\lambda G_0(\theta_t)\\|^2-\\|G(\theta)w_{t,\lambda}^*+\lambda G_0(\theta_t)\\|^2\leq\frac{1}{2}\rho$.

Then the inequality (iii) can be derived.


Meta-review: The paper is proposing a stochastic MOO algorithm with a theoretical analysis as well as experiments on classification and RL settings. It was reviewed by 6 reviewers and among them consensus was accepting paper. Although authors provided a rebuttal, the disagreement was still there. I carefully read the paper, reviews and the rebuttal. The major issues against acceptance was about empirical study. Specifically,

- There were minor mismatch between algorithmic description and empirical study
- Evaluation lacked some datasets/settings.

Overall, the mismatch is not a major issue as it is common to make some simplifications or engineering choices while implementing the methods. Authors clearly provided a source code and there is no re-production issue. I fail to see the importance the mismatch as both theoretical study and implementation is shared publicly. I also think we can not judge empirical study of a theoretical contribution same as empirical paper. The provided empirical study is enough to justify theoretical study (the convergence). Theory does not say anything about comparison to other methods.

It is a good theoretical contribution and should be shared with the community. I strongly recommend authors to incorporate reviewer feedback in their camera-ready.
Decision: Accept (poster)