On the Convergence of Stochastic Multi-Objective Gradient Manipulation and Beyond
Authors: Shiji Zhou
Wenpeng Zhang
Jiyan Jiang
Wenliang Zhong
Jinjie GU
Wenwu Zhu
Venue: NeurIPS 2022 Accept (2022)
Keywords: stochastic optimization
multi-objective learning

Abstract: The conflicting gradients problem is one of the major bottlenecks for the effective training of machine learning models that deal with multiple objectives. To resolve this problem, various gradient manipulation techniques, such as PCGrad, MGDA, and CAGrad, have been developed, which directly alter the conflicting gradients to refined ones with alleviated or even no conflicts. However, the existing design and analysis of these techniques are mainly conducted under the full-batch gradient setting, ignoring the fact that they are primarily applied with stochastic mini-batch gradients. In this paper, we illustrate that the stochastic gradient manipulation algorithms may fail to converge to Pareto optimal solutions. Firstly, we show that these different algorithms can be summarized into a unified algorithmic framework, where the descent direction is given by the composition of the gradients of the multiple objectives. Then we provide an explicit two-objective convex optimization instance to explicate the non-convergence issue under the unified framework, which suggests that the non-convergence results from the determination of the composite weights solely by the instantaneous stochastic gradients. To fix the non-convergence issue, we propose a novel composite weights determination scheme that exponentially averages the past calculated weights. Finally, we show the resulting new variant of stochastic gradient manipulation converges to Pareto optimal or critical solutions and yield comparable or improved empirical performance.

On the Convergence of Stochastic Multi-Objective Gradient Manipulation and Beyond
Shiji Zhou"t
Wenpeng Zhang Ant Group
Tsinghua University
choushij1000gmail.com
zhangkenpengg@@mail.comm com
Jiyan Jiang Tsinghua University
Wenliang Zhong Ant Group
Jinjie Gu
Ant Group
scjjy958outlook.com com
yice. www.:eaaatntttn.ooooo com
gujj@antgroup.com com
Wenwu Zhu Tsinghua University vnzhu@tsinghua. edu. cn
Abstract
The conflicting gradients problem is one of the major bottlenecks for the effective training of machine learning models that deal with multiple objectives, To resolve this problem, various gradient manipulation techniques, such as PCGrad, MGDA, and CAGrad, have been developed, which directly alter the conflicting gradients refined ones with alleviated or even no conflicts. However, the existing design and analysis of these techniques setting, ignoring the fact that they are primarily applied with stochastic mini-hatch gradients. In this paper, illustrate that the stochastic gradient manipulation algorithms may fail to converge to Pareto optimal solutions. Firstly, we show that these different algorithms can be summarized into unified algorithmic framework, where the descent direction is given by the composition of the gradients of the multiple objectives. Then we provide an explicit two-objective convex optimiza- tion instance to explicate the non-con non-convergence issue under the unified framework, which suggests that the non-convergence results from the determination of the composite weights solely by the instantaneous stochastic gradients. To fix the non- convergence issue, we propose novel composite weights determination scheme that ex exponeniially averages the past calculated weights. Finally, we show the re- sulting new variant of stochastic gradient manipulation converges Pareto optimal critical solutions and yields comparable or improved empirical performance.
mainly conducted under the full-batch gradient
Introduction
In many real-world application scenarios, the deployed machine learning models are designed to deal with multiple objectives. For example, in online advertising, the models need to maximize both the In autonomous driving, K
Click-Througe Rate and the Post-Click Conversion Rate [33
3d
the automatic pilots learn to simultaneously solve multiple tasks such as object identification and self-localization [14] 32) Despite being widely used, multi-objective machine learning models is known to be very challenging to train as different objectives may conflict with each other, creating the conflicting gradients problem
119 46 28
As is well acknowledged, the confficting gradients
Equall contributions
Coorespondiig authors
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

usually detrimental to the model training as they pull the model parameters into conflicting directions. Severe gradient conflicts will lead to significantly degraded model performance.
To resolve the confficting gradients problem, various multi-objective gradient manipulation (MOGM) techniques have been proposed, including MGDA K8 PCGrad 46 and CAGrad [28] etc. These techniques alleviate the conflicts between gradients by directly manipulating them. Typically, they alter the multiple gradients to seek a kind of common descent direction that can (approximately) simultancously descend all the losses w.r.t. the multiple objectives. While they have been widely applied and achieved significant empirical success, their current design and analysis are merely derived with exact (i.e., full-batch) gradients
B8 46 28 29 [6]. In contrast, in practice, these techniques are usually applied with stochastic (i.e., mini-batch) gradients, especially for training deep neural networks (DNNs) [22] (6],, as using stochastic gradients is much more practical and efficient.
In the single-objective setting, since the stochastic gradients are unbiased estimators of the true gradients, directly using the stochastic gradients still maintains the right expected direction to optimize the objective. However, this is not the case for the multi-objective setting when MOGM is used. In the multi-objective case, since altering the stochastic gradients could amplify the negative impact of the randomness of the gradients, the common descent direction for the stochastic objectives may not be the right direction to descend the true objectives in expectation. Such gap between full and stochastic gradients could cause non convergence issues for directly using MOGM algorithms.
In this paper, we rigorously show that the above non-convergence issues indeed exist. Surprisingly, we prove that altering the stochastic gradients yields direction that even inversely optimizes all the objectives in expectation for some cases. Such an inverse direction that moves the algorithms in the wrong direction will resist the solution from convergence. This implies that current MOGM algorithms are suboptimal under stochastic gradient settings, which potentially degrades the performance of MOGM algorithms applied for training DNNs. In particular, we make the following key contributions.
To uniformly analyze different MOGM algorithms, we summarize them into a general framework where the altered direction is weighted composition of the multiple gradients, and the composite weights are functions of the multiple gradients determined by the alteration rules of different MOGM algorithms. We provide strietly equivalent transformation to show that typical methods such as MGDA, PCGrad, and CAGrad are all included in the summarized form. This framework is general and incorporates wide range of algorithms, such as recently proposed GradVac 42), IMTL-G 29)
Under the above general framework, we elucidate how the MOGM algorithms can cause non- convergence by providing an example of simple stochastic convex optimization problem, where MGDA, PCGrad, and CAGrad provably do not converge to an optimal solution. The key reason is that the composite weights are calculated only from the instantaneous gradients in one step, and thus inherit the same randomness as the stochastic gradients. This strong correlation between the composite weights and stochastic gradients could lead to significant estimation bias of their composition. which forces the composite gradient in the wrong direction that even degrades all the objectives. Since MGDA, PCGrad, and CAGrad possess typical properties among MOGM algorithms, our analysis easily extends to other MOGM algorithms contained in our general framework as well. Furthermore, we point out that the previous analysis of the convergence for the MGDA algorithm [i is established on an unjustified assumption, where the composite weights are Lipschitz functions w.r.t. each gradient. We rigorously prove that this assumption is not true for MOGM algorithms.
The above analysis suggests that in order to achieve guaranteed convergence, the optimization algorithms must reduce the correlation between the composite weights and stochastic gradients. To resolve this issue while preserving the practical advantages of MOGM, we fix MOGM algorithms with a principled and practical momentum mechanism that exponentially averages the composite weights instead of just using the values computed from the instantancous gradients. Theoretically, momentum reduces the variance of the composite weight [ then decreasing the correlation as well. Thus, the inverse direction problem can be alleviated, and we prove that gradient manipulation algorithms can converge to optimal with the same rate as single objective stochastic optimization by adopting this mechanism. Our approach is simple to implement and agnostic to model and optimizer, and hence can be easily plugged into various gradient manipulation algorithms.
Finally, we empirically verify our proposal in simulation and deep multi-task learning tasks, where observe comparable better performance. Our advantage becomes more significant when the batch size is smaller, implying that the convergence issue is more severe with larger stochastic noise.
2

---

2
Preliminaries
In this section, we briefly review the basic background knowledge of multiplc-ojeective optimization, and introduce typical algorithms as well as their convergence analysis.
2.1 Basic Concepts of Multiple-Objective Optimization
Multiple-bjeective optimization (MOO) is concerned with solving the problems of optimizing multiple
objective functions simultaneously
48 38 termed as
min F(x) =
2 =
(I)
where m 2 denotes the number of objectives, and K. C. R2 denotes the feasible set in d dimension space, Each objective f* K + I,, i E , m is the i-th loss function. Different from single- objective optimization where solutions x, x can be order by f(x) S f(x') or f(z) > f (a'). In MOO, it could have two parameter vectors where one performs better for task i and the other performs better for task j + i. Therefore, Pareto optimality is defined to deal with such an incomparable case.
Definition 1 (Pareto optimality). For any two solutions I. x' E K. we say that dominates x', denoted as æ x x' or x' > I, if (z) S (z(2') for all i, and there exists one such that f'(x=) (x(x') otherwise, we say that x does not dominate x', denoted as x A x' x' & x. A solution x² E K. is called Pareto optimal if it is not dominated by any other solution in K.
Note that there is set of Pareto optimal solutions, termed Pareto set. The goal of MOO is find a Pareto optimal solution, which is necessary to be Pareto critical 3
Definition (Pareto criticality). A solution x² E KC is called Pareto critical if there is no common descent direction d E R such that (x= d < 0, i = m....m...p................... for all objectives.
This definition indicates that if æ is not Pareto critical, such direction d will be a local descent direction for F at point æ. Optimizing through d in the local neighborhood of æ is able to get a better solution that dominates x [8] Since Pareto criticality reflects the local property compared with Pareto optimality, it is often used the local minimal condition for MOO with non-convex objectives 1. We then present sufficient conditions for determining Pareto criticalityloptimality, which appear as metrics to study the convergence for MOO algorithm M AT. Denotes the probability simplex as E X = 1, E [o, 1]]. we have the following proposition.
Sm, = ((A'...,,A")) X"))
Proposition 1. For MOO problem D (a) If there exists X E Sm such that || E xx*'((") = 0, then xx E KC is Pareto critical. (b) For convex objectives f*()), I,..., m. If there exists X E Sm such that x² arg miD X" Fx)), then x² is Pareto optima
(a) is derived from the equivalent definition of Pareto critical points in 28 it reflects the stationary condition for MOO algorithms. (b) refers to Theorem 5.13 and Lemma 5.14 in (15), it implies that the minmmizer of any linearization is Pareto optimal for the multiple objectives.
2.2 Multi-Objective Gradient Manipulation
Similar to single-objective optimization, MOO can be solved by running iteratively with gradient- based algorithms. Suppose denotes the number of iterations. At each k = 1,..., round, the key challenge is the gradient conflicting problem. i.c., V f f (æx) < 0, j.i,j [m]] (1....,m) m). which leads to performance drop for an objective when optimizing another one 46). i.c optimizing f' along the negative gradient direction - fV will inversely optimize f`. multi- objective gradient manipulation (MOGM) algorithms aim to search for direction d, that is not conflicting with each negative gradient, i.e., - -V (xxx) dd > 0, E [m]] Using such con-conflitiin direction de to execute the gradient descent step to update the decision iee. I++1 = Ix + ndyy where is the step size, is shown to get better performance in practice G8 46 28 Mathematically, we can
measure the decrease of each objective
[m]]
f((x)) - fa + ndxx) R nnd (x))
Precisely, x" is weak Pareto optimal. If xx is the unique minimizer, x is Pareto optimal. For convenience of understanding, we do not distinguish them in the main text, and provide detailed comparison in Appendix A
3

---

by the first-order Taylor approximation assuming 7) is small 28 Therefore, if d V (xx) > 0 for each objective i, then this direction able descend all objectives simultaneously. There are various ways to compute such kind of direction, and we'll introduce typical MOGM methods as follows.
directly optimizes towards the Pareto critical- ity by leveraging Definition 2 Specifically, in each iteration k. MGDA aims to find a direction de to maximize the minimum decrease across the losses by solving the following subproblem
Multiple Gradient Descent Algorithm (MGDA) 48
max min (f(s) (2 + +dx)) -1 min max V (axx) dg.
de ke[m)
deRd ie m
By regularizing the norm of dı on the right side, it computes the direction by
dx = arg min mmax ((())) dEa" =E|ma
T d
2 [d]]])
This sub-problem can be rewritten equivalently as the following differentiable quadratic optimization
( |dll2 + 14), s.t. Vf((z)) d
dk μl arg min (dER>
If fa 0, then (=x)) the direction to descent all the objectives simultaneously B Р. To simplify the optimization, such primal problem has a dual objective min-norm oracle
T O, which means 3y is not Pareto critical from Definition 2 and dx is
A arg min
E
The direction is then calculated by d Σ m
(ax))
Projecting Conflicting Gradients (PCGrad) 46 alters the conflicting gradients by projecting each onto the normal plane of the other, preventing the interfering components of the gradient from being applied to the network. Specifically, initializes the projected gradients as of V (xxx). If projected gradient v; and raw gradient V (3xx) are conflicting, i.e., v! fxx) < O, then iteratively updates the projected gradients by
V J
PC
PC (m))
v (mxs)
for i, j = 1,... m until the projected gradients do not conflict with the received gradients. Since the conflicting components overall eliminated, it makes the direction dę Σ Di=1 of satisfies
d fz(z)) < for each objective i, thus optimizing all objectives simultaneously.
Conflict-Averse Gradient (CAGrad) 28 generalizes averaging lincarization and MGDA. Specifi- cally, it constrains search region for the common direction as a circle around the average gradient m 1 f with diagram e ||ooll-- Specifically, the direction d, is yielded by
v0 2i=1
dg
arg min max V faxx)) d, s.t. voll S cl dlvoll-
deRd
vE(m
can minimize the average loss function, while leveraging the worst local improvement of individual tasks to regularize the algorithm trajectory by using the common descent property of MGDA. Note that the gradient conflicting issue is not absolutely climinated due to the new constraint. Still, the above objective forces direction to approach the common descent direction close possible. To simplify the optimization, the dual objective is
m
m
A arg min XES...
Σ
8o voll
Σ
(xx)
Then the direction is calculated by d₃ = - (vo + +cllool (E N V (f)()))))
Convergence analysis. MGDA has been shown to converge to an arbitrary Pareto critical/optimal point with the same rate as single-objective optimization M.. A similar result has been proved with PCGrad 4o). CAGrad has been shown to converge to the minimizer or stationary point of the averaging loss To , fa(
when e [o, 1), or an arbitrary Pareto critical/optimal point when 0 we can infer that the minimizer or stationary point of the averaging loss also Pareto optimal or critical. Hence, we'll analyze them uniformly under the Pareto optimality in the following analysis, rather than distinguish them.
221 28 By Proposition

---

3 General Framework for Multi-Objective Gradient Manipulation
In this section, we summarize multi-objective gradient manipulation (MOGM) algorithms into general framework with the goal of uniformly analyzing the above algorithms.
3.1 The Framework with Full-batch Gradients
Without loss of generality, we summarize the direction search of MOGM in the following framework.
d2 V Faxg))
where the composite weights A = (1 gA....... >TTTT T is a function of the multiple gradients F = (xx)................ f (xx)) Specifically, MGDA and CAGrad obtain A by their dual form of take the two- the subproblem that depends the received gradients (zx)).) For PCGrad, (1/2, 12,1/4 1/2) as objective case as an example. If the gradients are not conflicting, we have A
d, - AV extending off and 2 as the following equivalent form.
PC (xx))) If they are conflicting, can rewrite dg (0) 02 by
d2 ((1 (as)) (
V ( + (1 V (xx) (2 (
(xx))
Then A = ( 2 (/ :
Since PCGrad with more than three objectives should be presented as protocol [А). we leave more details for the equivalent protocol with the general framework version in Appendix
V (m))))))))
21 2
B
Note that the composite weights A of PCGrad and CAGrad are not constrained in the probability simplex Sm. Hence, we here consider more general assumption on the boundness of A for including various MOGM methods than bounding it in Sm as MGDA.
Assumption 1. For the general framework 2 there exists a finite constant B E R, such that 0 S X < B, Em X 2 for all k 1,... T2,
I,..., m
Remark.
The general framework also contains more recent approaches that are based on the funda- mentals of the introduced methods, such as GradVae 142. IMTL-G (2)]. Note that we focus on the optimization side for multi-objective problems, thus we provide the derivation of existing fundamental optimizers. A vertical line of works that focus on neural architecture, such as RotoGrad [16], are not included in this work.
3.2 The Framework with Stochastic Gradients
MOO be solved with gradient manipulation algorithms with full gradients with theoretical guarantees g
28 However, training with mini-batch gradient much more practical for deep learning applications [36), while MOGM with stochastic gradients is largely underexplored.
Specifically, only obtain noisy gradient feedback G₁ (g (æx. E g (xx,," that is corrupted by stochastic noise E i = I,..., m.. Following
2 we have its stochastic version
d, G
Note that here A depends on stochastic gradients, not the exact ones. We then make the following standard assumption similar to single objective setting [8 12], which says that we have access to unbiased stochastic estimates of the gradients for all objectives.
Assumption 2. Let {xx }i-1 be the iterate sequence for any algorithm. For all k = 1, .,.... we have access to g² (æxs 41) ..., ........... 9 (xx. =x" which are unbiased estimates of fxx) (xx), i.e. Es, [g' (Ix, 4 = V V (xx) = 1...., m. Further, each gradient variance is bounded by Eg, [llg* (xx 4 (xx)) S s0
m.
To analyze MOGM in the stochastic setting, state the following definition to determine sequence generated by an iterative algorithm to asymptotic converge to Pareto critical and optimal.
Definition 3 (Convergence condition). (a) A sequence { 1.0 asymptotically converges to Pareto
critical points if limg-+ Elminx, es... || FVF(a (+x+)))))) - O.
(b) For convex multi-objective function F(-) A sequence { asymptotically converges to
Pareto optimal if lim E [[maxx;es EK minx (A) F(xx) X F(x[)) + 0.
5

---

USSA
Desarca
terabors
(a) Inverse Direction
(b) Loss
(c) Loss 2
(d) Distance Optimal
Figure I: (a) We plot the contours of two objectives. Gradient manipulation algorithms designed based on full-batch gradient could yield an expected composite gradient that conflicts with the true gradients and is inverse to Pareto set. (b) (c) This leads to the unexpected consequence of degrading all the objectives, making the objectives insufficiently optimized. (d) Hence, MGDA, PCGrad, and CAGrad can not converge to Pareto optimal solution, and suffer a large distance to Pareto optimal set.
The definition (a) directly follows Proposition I (a) and the definition of Pareto critical. The definition (b) is because 2x is the minimum of X F(z), thus is Pareto optimal (Proposition (b)).
Asymptotically converging Af. F(æt)) implies that æy approaches Pareto optimal. Note that the minimization operator of X is from the existence condition in Proposition | (b). This definition can
also be viewed as the stochastic version of metric function 40
and Pareto suboptimal gap 17
4 The Non-convergence of Stochastic Multi-Ohjective Gradient Manipulation
With the problem setup of stochastic MOGM in the previous section, we now discuss fundamental flaws among the current gradient manipulation methods that are all designed and analyzed based on full-batch gradients. We show that such batch algorithms fail to converge to Pareto optimal solution even in a simple two-objective
rooddimensional convex stochastic setting. The main issue lies in the strong dependence of X on the received stochastic gradients GG. Surprisingly, we find that combining such correlated A with the stochastic gradient yields biased composite gradient E[d,] - E Ae) that even conflicts with all full-batch gradients in expectation. This inverse direction even causes the algorithms to inversely optimize all the objectives simultancously.
An illustrative example. Next, we provide a simple problem instance in which MGDA, PCGrad, CAGrad can not converge to Pareto optimal. Consider the following two-dimensional stochastic optimization setting over the domain K. {(x. v) x E []1, 2 0}, where p represents the probability of occurrence
(x + 1)2 2) p 1/2
f (xx = (x-1)² 1)2+11++++--0 2)- p= 1/2
fl (z
(4)
5)² + 2) p= 1/1
(x- + 2)+ p= 1/2
The expected function is (x = (x 3x) y² + (x)
+ y² + Thus, by
ignoring the constant term, the optimization goal is to minimize the distance towards (-3, 0) and (3, 0) simultaneously. We can easily know that the Pareto set is the line segment {(a, 0) a E 1-)
In the first step. by calculating the expected gradient of the point (0, 0.4), we find that all the gradient manipulation algorithms generate a vertical-up direction in expectation, as shown in Figure Ta] which moves the algorithm in the wrong direction away from Pareto optimal setting. More seriously, the expected direction [[d,] = e), 0 is conflicting with both true gradients, suggesting that inversely optimizes both objectives.
Furthermore, we could prove that the inverse direction problem happens with Pareto optimal points, which resists the algorithms to approach Pareto optimal. Using the intuition above, we show that gradient manipulation algorithms can not converge to Pareto optimal for this setting.
Theorem 1. There is stochastic convex optimization problem for which MGDA, PCGrad, CAGrad do not converge to the Pareto optimal solution.
We relegate the proof to Appendix D In the proof, we provide stronger support that at least in the range [(x,, y) x E 1]. E [0, 0.05]. the expected directions for the three typical algorithms all move the solution away from Pareto set. This means there exists constant gap for gradient

---

manipulation algorithms to approach the Pareto optimal set. Note that this gap is a sufficient condition to verify the coneergerg,, and it can be much larger, as shown in Figure [d]
Intuitively, the convergence gap is caused by the strong correlation between the composite weights A and the stochastic gradients Gg, i.e., AS is solety determined by Gk, which could produce an inverse direction in the example above. When the composite weights is independent of the stochastic gradients, the expected composite gradient [[[d]] = [
I ( )^ will be a positive direction to approach the Pareto set. Hence, methods like linear scalarization are able to attain point in the Pareto optimal set [Л. but are deprived of the practical benefits of gradient manipulation.
We would also like to emphasize that while the example of non-convergence is carefully constructed to demonstrate the problems in the above three typical algorithms more easily, such an issue also happens with more general Gaussian noise, as shown in Appendix G.2 Hence, it is not unrealistic to suspect scenarios where such issue can impair practical performance. is also reasonable to assume that this problem is especially aggravated in high dimensional settings, where the variance of the gradients is more significant.
Comparison with existing convergence results. As introduced in Section 2.2 the optimal solution for the multi-task objective # - (x) must be Pareto optimal. Therefore, the above non- convergence analysis generates well with MOGM algorithms that optimize the averaging loss, such as CAGrad. This result shows that the previous convergence analyses in the full-batch setting are all invalid in the stochastic setting.
To the best of our knowledge, there is only MGDA that has convergence analysis in the stochastic setting. Liu et al. (31] establishes the convergence of MGDA with stochastic gradients, but based on two unjustified assumptions. The first is that the gradient variance asymptotically converges to O. The second is that the subproblem for AE. denoted as function (g g")., is Lipschitz continuous with right to each gradient. The first assumption needs to gradually increase the batch size to full batch; however, the reliance on giant batch sizes is impractical for deep learning training E. The second one can significantly simplify the convergence analysis, but is actually not true shown in the following proposition.
Proposition 2. Subproblem (-).) is not Lipschitz continuous with right to each gradient for MGDA, iee. there exist no finite 3 such that [| "..g"....9"" 9
9 Xa (g) ......"
g." . gg $
31|g*
g" [| = ,....,m and gradient g ,......"" g
Similar results can be proved for PCGrad and CAGrad, and we relegate the proof to the appendix D
5 Correlation-Reduuee Stochastic Multi-Objective Gradient Manipulation
In this section, we develop a new principled exponential moving average mechanism on the composite weights Xg. and provide its theoretical benefit for fixing the convergence issue for MOGM algorithms. Our aim is to devise a new strategy with guaranteed convergence, while preserving the practical benefits of MOGM without introducing additional computation and memory overhead.
Algorithmic insight. To understand the design of the mechanism, recall that the main issue of the non-convergence for MOGM lies in the strong correlation between the composite weights A and the stochastic gradients G5. which could cause the composite gradient E[dx] = -E G inversely optimizing all the objectives in expectation. It is natural to consider reducing such correlation, which can be bounded by the following lemma.
Lemma 1. Under Assumption
7 2 The correlation between AE and GR can be bounded as [[E[G - E| B[Ga < 2V,, (As), where Ve, (As) = EE, I|| ||| - Ex, [1.]
From Lemma 0 we know that the correlation can be reduced by reducing the variances of A From this intuition, we can modify MOGM algorithms to reduce such correlation by regularizing the variation of dge Correlation- reducedd MOGM (CR-MOGM) adopts momentum mechanism with coefficient ar on the update of composite weights as Line 5 in Algorithm | able to reduce variance as
which is shown to be
Lemma Under Assumption
7
A variance for Algorithm 1 is bounded Ve. [Au) S m²
This result shows that the correlation can be controlled by choosing on closed enough to With reduced correlation, the wrong direction generated by MOGM could be corrected to positive
7

---

Algorithm 1 CerrelationRReducee Stochastic Multi-objective Gradient Manipulation (CR-MOGM)
1: Input: Number of iterations K, regularization parameter Oi. learning rate T)k-
2: Initialize: zo. Ag Am.
3: for k = I.....I. K do
4: Compute A by gradient manipulation algorithms using the stochastic gradients.
5: Update the weights for the gradient composition A = oRdRR + (1 aa) A
6: Compute the composite gradient d..- = G (Tk; E)
7: Update xx++1 3k + n).
8:
end for
direction, and thus the algorithm would be able converge. Note that the momentum on A only requires an additional negligible computation cost.
On the other hand, the proposed exponential moving average mechanism also preserves the advantage of MOGM by carefully setting the momentum parameter ag to be O and asymptotically convergent to 1. Intuitively, CR-MOGM performs similarly to vanilla MOGM at the initial stage. and approximates like fixed linear scalarization in the late stage. Initially. the stochastic noise occupies a relatively small component of the stochastic gradient. Thus, methods like MGDA, PCGrad, CAGrad can search for good common descent directions. When the number of iterations increases and the solution approaches the Pareto optimal, the impact of the stochastic noise stands out, causing the inverse direction problem for MOGA as in the previous section. At this time, og becomes larger, maintaining relatively stable À eliminates the strong correlation and guarantees the convergence.
Convergence analysis. We next provide convergence analysis for CR-MOGM | concluding all algorithms based on the general framework Before that, we introduce basic assumptions.
Assumption& 3. fl (z))..... fth (ax) are all differentialable, H H-Lipschitz and L- L-smoothness, suggest- ing that for all æ. y K., i [m]) holds ([)] H and [ ( < L| yll-
Lipschitz and smoothness are commonly used in complexity analysis for stochastic gradient algo- rithms [1 12
[0
A. Based on Definition B we prove the following key results for CR-MOGM.
Theorem (Convex). Under Assumption
For the sequence To. 2I...., In generated by we assume objective functions [(x) fm (x) are all convex with bounded optimal "'..,,"'((", < F for x² in Pareto set, and the distance from sequence to Pareto set bounded, i.e., la0g x=1
Algorithm
7
values as F(x")
D. Set 0 S Am S S... sm S 1/mLBB, On (0, for 1,....?
in Algorithm it achieves
D2
m m2
(O²
+oH + H
max min (Ai F(xx)) - X F(Zz))
E
<
+
Ul
oi BIEK A.E.
n
1m
Rim 1
3/2
I an) + 6/m 22 Ho
2F n
m
as ax)m. +
Σ 1=1
1(1
041+1
|tt N/t1l
n
n
Theorem 3 (Non-convex). Under Assumption
Under Assumption
For the sequence
Tn, 21....,22 En generated by Algorithm we assume objective functions
k (xx <
all bounded for l- =1,.. 1,..., Set 0 achieves
Th I ... S mh 1/mLB and ag (0, in Algorithm
F
2
m
2mBF
E min [F 11 AGES
(1 aak
15
1-11+
2= TT
77/m
1=1
4m 5/2
//2 Ha
Im B3
+
ax)
+
nk-
2n
km
Remark. Note that our theoretical results imply that CR-MOGM is convergent in averaging by
choosing suitable and a. Such an averaging analysis scheme is adopted by CAGrad 28]. and
is often used in stochastic optimization 39 KK transformed into the traditional version, as shown in Appendix E.7
e.g. Adagrad (26). Adam 22 36 It can be
The above results falls an immediate corollary of the above Theorem.
8

---

2030
Kow
Trannin Lasace
Liess
Trankng
Tucking
Terators
Tenadons
Hendom
(a) Training Loss-L
(b) Training Loss-R
(c) Testing Loss-L
(d) Testing Loss-R
Performance comparison of gradient manipulation algorithms and their correlation-reducce counter part for MultiMNIST. We report the over 3 runs.
Figure 2:
Table 1:
Accuracy on MultiMNIST. We
report the means over runs.
Table 2: Losses of the final output of MGDA and CR-MGDA on MultiMNIST. We report the mean over runs.
Method
task-L Ace
task-R Acc
MGDA
96.46%
95.29%
MGDA
CR-MGDA
CR-MGDA
96.92%
95.44% f
Batch Size
loss-L
loss-R
loss-L
loss-R
PCGrad
96.63%
95.37%
8
0.44
0.54
0.24
0.35
CR-PCGrad
96.90%
95.75% 1
4
0.57
0.65
0.26
0.36
CAGrad
96.47%
95.20%
2
0.71
0.81
0.28
0.40
CR-CAGrad
96.85%
95.70% 1
Corollary 1.
1k/ (TE - in Algorithm converges with 12n Onn rates in the convex and non-convex case.
Set 1 2 7/4 O(1/V))) max m///,, 1-
Theorem
This result indicates that Algorithm has convergence rate that matches the one in the single- objective stochastic setting 21. demonstrates the efficacy of the proposed momentum mechanism.
Experiments
In this section, we present empirical results on both synthetic with convex objectives and real-world datasets for multi-task learning with deep neural networks, representing convex and nonconvex settings, respectively. We apply CR-MOGM to MGDA, PCGrad, CAGrad, and use CR- distinguish whether adopts our approach. We conduct experiments to answer the following questions:
Q1: Does our approach fix the non-convergence and improve the optimality for MOGM algorithms?
Q2: Does approach consistently improve the practical performance of MOGM in deep learning?
Q3: Does the non-convergence issue demonstrated with the special case still exists in practice?
Q4: Is our approach flexible to be implemented and agnostic to models as well as optimizers?
Synthetic experiments. To demonstrate whether CR-MOGM fixes the convergence issue for gradient manipulation algorithm, we first consider the same simple convex setting as the example in Section We initialize zg (0, 0.4) and use SGD the optimizer. To enable fair comparison, the adaptive stepsize is set with ид 0.006/ V for all the algorithms, and the momentum parameter for smoothing the composite weights set with the suggested parameter setting in Corollary |
Figure D fillustrates the multi-objective losses and distance to the Pareto set for this problem. We first note that both the two objective losses of MGDA, PCGrad, CAGrad are significantly larger than their counterparts applied with the proposed mechanism. Furthermore, the losses are even increasing at the initial stage as a result of the inverse direction issue demonstrated in Figure from the Pareto set, which unfortunately causes an increasing suboptimal gap. In contrast, applying CR-MOGM enhances the algorithms to converge to Pareto optimal. This positively answers Q1.
It moves 2 away
Multi-task classification. For multi-task classification scenarios, we follow the experiment setup from Sener al. (88, and consider the MultiMNIST dataset [37] with 60K examples. MultiMNIST contains two tasks: classifying the digit on the top-left (task-L) and classifying the digit on the bottom-

---

Segmentation (Higher Better)
Depth (Lower Better)
Method
(Training)
(Testing)
(Training)
(Testing)
mioU
Pix Acc
mloU
Pix Acc
Abs Err
Rel Err
Abs Err
Rel Err
MGDA
XN
76.05
94.08
66.32
88.85
0.0065
18.90
0.0248
33,50
CR-MGDA
79.58
95.12
73.21
93.01
0.0067
18.51
0.0151
33,59
PCGrad
in
80.19
95.31
75.25
93.50
0.0087
27.18
0.0148
45.37
CR-PCGrad
80.12
95,32
75.37
93.50
0.0085
26.44
0.0153
43.05
CAGrad 28
80.24
95.29
75.09
93.52
0,0081
25.06
0.0145
40,97
CR-CAGrad
80.33
95,33
75.58
93.53
0.0080
25.30
0.0142
38.51
Table 3: Multi-task learning results CityScapes Challenge. We report the mean over 3 runs.
right (task-R), We use the LeNet architecture 23 and use SGD as the optimizer. The stepsize and parameters are tuned from vanilla MGDA, PCGrad, CAGrad, and the correlation-reduced counterparts follow the same parameter setting to enable fair comparison. The momentum parameter set with suggested value in Corollary !
We report the train and test losses in Figure 2
We can see that algorithms with À momentum perform better than original ones with respect to both train and test losses. We also observed that À momentum consistently improves the accuracy for all the objectives in Table [ We hence positively answer Q2
In particular in Table we observe that the loss of vanilla MGDA becomes significantly larger when the batch size is smaller, while CR-MGDA appears not sensitive the batch size. The possible reason is that the convergence issue of MOGM becomes more severe with larger stochastic noise, which severely degrades the performance of MOGM. Since CR-MOGM is proven to converge the Pareto optimal/critical, it is much more robust to stochastic noises. Thus, in this regard, our method more practical for world applications. We hence positively answer Q3.
Semantic segmentation. For semantic segmentation scenarios, we follow the experiment setup from Yu et al. 46 and Liu et al. 22 and consider the CityScapes. CityScapes similarly contains two tasks: 7-class semantic segmentation and depth estimation. We combine algorithms with MTTA 300 based SegNet architecture [Τ. We use adam 22 as the optimizer. All parameters from vanilla MOGM algorithms, and the correlationrreduced counterparts follow the same parameter setting to enable a fair comparison. The momentum parameter
tuned
with the suggested value.
We report mean intersettion-Ove--nniooo (mloU), pixel accuracy (Pix Acc), and absolute/relative (abs/rel) errors in Table 3 We observe comparable or better performance when adopting our approach with the three gradient manipulation methods. In particular, the improvements for MGDA and CAGrad are more significant than PCGrad, possibly due to the special gradient manipulation rule that PCGrad does not alter the gradient when they are not conflicting, then the non-convergence issue of PCGrad could be less severe. Combining the above results, we demonstrate that methods work for different models and optimizers. We hence give a positive answer to Q4.
Conclusions
In this work, we study multi-objective gradient manipulation in the stochastic mini-batch setting and identify fundamental flaw in algorithms designed under the exact full-batch setting. Through an illustrative example, we rigorously prove the non-convergenee issue of typical methods, including MGDA, PCGrad, and CAGrad. In particular, we fix this problem by slightly changing these algorithms by an exponential smoothing mechanism without introducing additional computational or memory overhead. We prove the convergence of the resulting algorithms and show that they yield consistent empirical performance improvement. Our analysis is general and can be extended to analyze combining MOGM algorithms with other stochastic optimizers such Adam and Adagrad.
Limitations. This paper discusses the typical MOGM algorithms with striet convergence guarantees, i.e., MGDA, PCGrad, and CAGrad. Other empirical-driver methods without rigorous theoretical guarantees, such as RotoGrad 16), are too expensive be included our analysis. We believe that the convergence issue in that line of literature will be an excellent future work to explore in depth.
10

---

Acknowledgement
This work is supported by the National Key Research and Development Program of China No. 2020AAA0106300 and National Natural Science Foundation of China No. 62250008. This work was supported by Ant Group through Ant Research Intern Program. We would like thank Tianyu Liu, Xin Wang, and Ziwei Zhang for their advices on paper writing and Guannan Zhang for generous support on this project.
References
[1] Vijay Badrinarayanan, Alex Kendall, and Roberto Cipolla. Segnet: A deep convolutional incoder-decoder architecture for image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence. 39(12):2481-249) 2017.
[2] Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, (0(2):223-311 2018.
[3] Ana Luísa Custódio, JF Aguilar Madeira, A Ismael F Vaz, and Luís Nunes Vicente. Direct multisearch for multiobjective optimization. SIAM Journal on Optimization, 21(3:
2011.
[4] Ashok Cutkosky and Francesco Orabona. Momentum-based variance reduction non-convex sgd. Advances in Neural Information Processing Systems, 32, 2019.
[5] Yoel Drori and Ohad Shamir. The complexity of finding stationary points with stochastic gradient descent. In International Conference on Machine Learning, pages 2658-2667, 2020.
[6] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(7), 2011.
[7] Benjamin Fehrman, Benjamin Gess, and Arnulf Jentzen. Convergence rates for the stochastic gradient descent method for non-convex objective functions. Journal of Machine Learning Research, 21:136, 2020.
[8] Jörg Fliege and Benar Fux Svaiter. Steepest descent methods for multicriteria optimization. Mathematical Methods of Operations Research, 51(3):479 2000.
[9] Jörg Fliege, A Ismael F Vaz, and Luis Nunes Vicente. Complexity of gradient descent for multiobjective optimization. Optimization Methods and Software, 34(5):949-959, 2019.
[10) Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. Sgd: General analysis and improved rates. In International Conference on Machine Learning, pages 5200-5209, 2019.
[11] Walter J Gutjahr and Alois Pichler. Stochastic multi-objective optimization: survey non-scalarizing methods. Annals of Operations Research, 236(2):475 499, 2016.
[12] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pages 1225- 1234, 2016.
[13] Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Optimization, 2(3-4):157-325, 2016.
[14] 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 Pattern Analysis and Machine Intelligence, 42(10))2702-271 27119, 2019.
[15] Johannes Jahn. Vector Optimization: Theory, Applications, and Extensions. Springer Science & Business Media, 2010.
[16] Adrián Javaloy and Isabel Valera. Rotograd: Gradient homogenization in multitask learning. In International Conference Learning Representations, 2022.

---

[17] Jiyan Jiang, Wenpeng Zhang, Shiji Zhou, Lihong Gu, Xiaodong Zeng, and Wenwu Zhu. Multi- objective online learning. 2021.
[18] Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in Neural Information Processing Systems, 26, 2013.
[19] Alex Kendall, Yarin Gal, and Roberto Cipolla. Multi-task learning using uncertainty to weigh losses for scene geometry and semantics. In Conference Computer Vision and Pattern Recognition, pages 7482 00022-791,22 2018.
[20] Ahmed Khaled and Peter Richtárik. Better theory for sgd in the nonconvex world. arXiv preprint arXiv:2002.03322 00:.0099...,,9, 2020.
[21] Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A near-optimal algorithm for stochastic bilevel optimization via double-momentum. Advances in Neural Information Processing Systems, 34:30271-30285 2021.
[22] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Interna- tional Conference on Learning Representations, 2015.
[23] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 11:2277-7-222444 1998.
[24] Yunwen Lei, Ting Hu, Guiying Li, and Ke Tang, Stochastic gradient descent for nonconvex learning without bounded gradient assumptions. IEEE Transactions on Neural Networks and Learning Systems, 2020.
[25] Kfir Levy, Ali Kavis, and Volkan Cevher. Storm+: Fully adaptive sgd with recursive momentum for nonconvex optimization. Advances in Neural Information Processing Systems, 34:20571- 1- 20582, 2021.
[26] Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In International Conference Artificial Intelligence and Statistics, pages 983 992, 2019.
[27] Xi Lin, Hui-Ling Zhen, Zhenhua Li, Qing-Fu Zhang, and Sam Kwong. Pareto multi-task learning. Advances in Neural Information Processing Systems, 32, 2019.
[28] Bo Liu, Xingchao Liu, Xiaojie Jin, Peter Stone, and Qiang Liu. Conflict-averse gradient descent for multi-task learning. Advances in Neural Information Processing Systems, 34, 2021.
[29] Liyang Liu, Yi Li, Zhanghui Kuang, J Xue, Yimin Chen, Wenming Yang, Qingmin Liao, and Wayne Zhang. Towards impartial multi-task learning. In International Conference Learning Representations, 2021.
[30] Shikun Liu, Edward Johns, and Andrew J Davison. End-to-end multi-task learning with attention. In Conference on Computer Vision and Pattern Recognition, pages 1871-1880, 2019.
[31] Suyun Liu and Luis Nunes Vicente. The stochastic multi-gradient algorithm for multi-objective optimization and its application to supervised machine learning. Annals of Operations Research, pages 1-30, 2021.
[32] Weixin Lu, Yao Zhou, Guowei Wan, Shenhua Hou, and Shiyu Song. L.3-nt:: Towards learning based lidar localization for autonomous driving. In Conference on Computer Vision and Puttern Recognition, pages 6389-6398, 2019.
[33] Jiaqi Ma, Zhe Zhao, Xinyang Yi. Jilin Chen, Lichan Hong. and Ed H Chi. Modeling task rela- tionships in multi-task learning with multi-gate mixture-of-eepertt. In International Conference on Knowledge Discovery & Data Mining, pages 1930-1939 2018.
[34] Xiao Ma, Liqin Zhao, Guan Huang, Zhi Wang, Zelin Hu, Xiaoqiang Zhu, and Kun Gai. Entire space multi-task model: An effective approach for estimating post-click conversion rate. In Conference Research & Development in Information Retrieval, pages 1137-1140, 2018.
12

---

[35] Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In International Conference on Machine Learning, pages 1310-1318, 2013.
[36] Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018.
[37] Sara Sabour, Nicholas Frosst, and Geoffrey E Hinton. Dynamic routing between capsules. Advances in Neural Information Processing Systems, 30, 2017.
[38] Ozan Sener and Vladlen Koltun, Multi-task learning as multi-objective optimization. In Advances in Neural Information Processing Systems, pages 525-536, 2018.
[39] Ohad Shamir and Tong Zhang. Stochastic gradient descent for non non-smooth optimization: Convergence results and optimal averaging schemes. In International Conference on Machine Learning, pages 71-79, 2013.
[40] Hiroki Tanabe, Ellen Fukuda, and Nobuo Yamashita. Proximal gradient methods for multi- objective optimization and their applications. Computational Optimization and Applications, 72(2):339-3611 361, 2019.
[41] Hiroki Tanabe, Ellen H Fukuda, and Nobuo Yamashita. Convergence rates analysis of a multiobjective proximal gradient method. Optimization Letters, pages 1-18, 2022.
[42] Zirui Wang, Yulia Tsvetkov, Orhan Firat, and Yuan Cao. Gradient vaccine: Investigating and improving multi-task optimization in massively multilingual models. In International Conference on Learning Representations, 2020.
[43] Ruobing Xie, Yanlei Liu, Shaoliang Zhang, Rui Wang, Feng Xia, and Leyu Lin. Personalized approximate pareto-efficient recommendation. In Web Conference, pages 1839-3849) 2021.
[44] Yan Yan, Tianbao Yang. Zhe Li, Qihang Lin, and Yi Yang. A unified analysis of stochastic mo- mentum methods for deep learning. In International Joint Conference on Artificial Intelligence, pages 2955-2961, 2018.
[45] Junjie Yang, Kaiyi Ji, and Yingbin Liang. Provably faster algorithms for bilevel optimization. Advances in Neural Information Processing Systems, 34: 14:1:36 15:13317-16622 2021.
[46] 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, 33, 2020.
[47] Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. International Conference on Learning Representations, 2019.
[48] Eckart Zitzler and Lothar Thiele. Multiobjective evolutionary algorithms: comparative study and the strength pareto approach. IEEE Transactions on Evolutionary Computation, 3(4):257-2) 1999.
13


Reviews:
[{"review_id": "xGtjR1ZW8CZ", "reviewer": "Reviewer_XWtt", "summary": "This work studies the conflicting gradient problem in multi-objective optimization in the stochastic (minibatch) setting. The authors survey some recent gradient alterations algorithms, put them under one general framework (or update rule), and then construct a counter-example that shows that such algorithms can fail to converge to a Pareto optimal solution in the stochastic setting. They propose to deal with this using a momentum-based update for the gradient composite weights.", "questions": "How well does the counter-example translate to real-world data? It seems to be specifically constructed to make convergence fail. It is mentioned that a similar situation can happen with “more general Gaussian noise”, but wouldn’t the noise from SGD(+momentum) help mitigate getting into such rigid suboptimal situations?\n\nPerhaps proposing a reasonable assumption on the data distribution can avoid such a counter-example altogether?", "limitations": "This work has no apparent limitations and potential negative societal impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written and has a clear structure that makes it easy to read. It starts by stating the problem, then summarizes known approaches and pointing the common problem in them, and finally proposing a solution and validating it experimentally. The problem is well-posed and is clearly illustrated in the counter-example and in Figure 1. The improvements of the proposed fix in this specific example are significant.\n\nThe fix employs an exponential average of gradient composite weights. It is simple, practical, and easy to implement. Works just like momentum in SGD, so it can be added to any gradient alteration algorithm. The additional compute and memory footprint are not significant.\n\nThe results overall are better, but not significantly so. Perhaps this is because the situation in the counter-example is not as serious in real-world data as is thought to be. In any case, the adjustment can be made to any gradient alteration algorithm without affecting performance, so this is not a big problem. Still, it would be nice to see real-world situations where this adjustment can yield clear and significant improvements just to account for the additional complexity,\n\nMinor issues:\n* There is a typo in Assumption 2 (line 193): “… which are unbiased estimates of $f^1$ …”. There should be a $\\nabla$ before $f^1$, and so on.\n* Figure 1 is a bit too small, especially the font. I had to zoom in to see clearly.\n* Are the results in Figure 2 for MultiMNIST done for multiple seeds? If so, then it should be mentioned somewhere and the std bands should be plotted.\n* As for Table 1, reporting the std would be better. Also, some acronyms are not explained, such as mIoU and Pix Acc. And finally, the relative error under Depth->Testing->Rel Err for CR-PCGrad is larger than PCGrad but is in bold. Looking at the absolute errors, I assume there is a mistake in the calculation.\n* I think the bounds in Theorem 2 and Theorem 3 can be written a bit more clearly. The third term in the right hand side of Theorem 1 has an $\\eta_k$ in the denominator, but the summation of the index $k$ is in the numerator.\n* The conclusion is also a bit lacking. It would be nice for the readers to discuss future directions and room for improvements.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HCMWt22IGI0", "reviewer": "Reviewer_DjJR", "summary": "This paper proposed a new algorithm for stochastic multi-objective learning that solves some non-convergence issues in existing multi-objective learning algorithms. At each iteration, the update direction is computed as the weighted combination of gradient directions of every objective, and the weight is an exponential average of weights in past iterations. Such a weight scheme aims at reducing the correlation between the weight and stochastic gradient at each iteration. The convergence analysis is provided for the proposed algorithm and experiments show its advantages over existing algorithms.\n\nThis paper is clearly written. The proposed algorithm is simple and shows great improvement over existing algorithms. Therefore I recommend \"Accept\"", "questions": "All of them are minor:\n\n1. line 105, the author may want to clarify here what \"$F$ is convex\" means, it only gets clear when I read Theorem 2.\n2. line 315/316, probably add citations for the convergence rate in the single-objective setting?\n", "limitations": "The author claimed that there are discussions on limitations in the appendix but it is hard to find. Maybe it is better to put the discussions in a separate section.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper gives an excellent introduction to multi-objective learning, identifies convergence issues in existing approaches, and proposes a new algorithm as the solution. The paper is clearly written and easy to follow even for a non-expert in multi-objective optimization. Theoretical results on convergence are also provided together with experiments showing improvement over existing approaches. I can not assess the novelty of the paper as I'm less familiar with the literature on multi-objective learning.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "DCRKP5rk6jf", "reviewer": "Reviewer_eaLg", "summary": "Multi-objective optimization (MOO) has been an area of research interest lately, where the goal is to optimize multiple objectives simultaneously, using some optimality condition (e.g. Pareto optimality). One popular MOO algorithm is the multi-objective gradient alteration (MOGA) algorithm, where a common descent direction is chosen for all the objectives by manipulating objective gradients. In most MOGA literature, analysis is only provided using deterministic gradients, although in practice only stochastic gradients are used for calculating the common descent direction. This work addresses this issue. The authors propose an optimizer-agnostic framework to reduce the correlation between the aforementioned weights and the stochastic gradients, which can be applied to many MOGA algorithms. The authors specify the convergence criteria and provide theoretical guarantees for the convergence of the proposed algorithm for convex and non-convex cases. The authors also provide some empirical results to support their claims.\n", "questions": "* Could you justify the use of bounded objective assumption in the convergence analysis of the non-convex case, since it may not be true in general?\n\n* Could you provide justification/proof for the claim in line 542? Specifically, the concern is that a Pareto stationary point need not be a weakly Pareto optimal point in general even in a convex setting.\n\n* Could you provide any insight into how close $\\lambda_k$ in CR-MOGA is to the actual $\\lambda_k$ that is calculated by the corresponding MOGA? The work does not seem to provide adequate insight in this regard. If this closeness is not significant, could you explain the reason?\n\n* Could you provide an intuition for the expected value of $\\lambda_k$? By the variance reduction, $\\lambda_k$ becomes closer to the expected value, yet it is unclear what this value represents. This might be related to the previous question.", "limitations": "- Authors have identified the limitations of the examples they have used to introduce the problem, but provide additional experiments in a more practical setting that support their claims.\n\n- Authors may need to address the limitations of the work due to the strong assumptions such as the boundedness of the objectives.\n\n- There is no potential negative societal impact from this work.\n", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "***Strengths***\n- Investigate a key and important issue in the current MOO line of research;\n- Provide rigorous evidence of the non-convergence problem, and provide key insights into the source of the problem;\n- Propose a simple solution to the problem which has insignificant computational overhead compared to existing MOGA algorithms;\n- Provide theoretical and empirical justification for the performance improvement using the proposed algorithm.\n\n***Weaknesses***\n- The main theoretical results provided in the main text are inaccurate or different from those in the supplementary;\n- Some strong assumptions are not standard without providing a clear justifications. Specifically, the authors use a bounded objectives assumption for Theorems 2 and 3 (line 739,  798), which is not standard in optimization literature and prior work on MOGA algorithms.\n- It is not clear how the unified framework still guarantees the benefits of the original MOGA algorithms. Specifically, the assumptions on $\\lambda_k$ do not reflect the special properties of different MOGA algorithms, thus it is unclear how the modification will allow behavior similar to the original algorithm.\n- Seemingly incorrect/unclear proof steps possibly resulting in weaker dependence on the number of objectives $m$ in final results (e.g. lines 671, 687). Specifically, a factor of $m$ seems missing when upper bounding the squared norm. \n- Some claims on the relation between Pareto criticality and weak Pareto optimally in the convex setting need to be justified (line 542. Refer to the “Questions” for further elaboration of the concern).\n- Missing definition of notations (e.g. $[m]$ in text, possibly meaning $\\{1, 2, , …, m}$; p in toy example, probably meaning probability of occurrence) \n- Inconsistent notations used ( e.g. line 688, $\\leq$ used for comparing scalers and vectors without clarification)\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "BCQFRRe2fdI", "reviewer": "Reviewer_sBF7", "summary": "This work explores three gradient alteration methods: MGDA, PCGrad and CAGrad  used for multi-objective optimization and  shows that these methods are not guaranteed to converge to Pareto optimal/critical point in the stochastic cases, and illustrates that in a simple 2 stochastic quadratic functions case.\nIn fact, the included example showed that all three methods generate a direction that would degrade all objective functions. To remedy this issue, the authors proposed a momentum inspired algorithm that would reduce correlation of the stochastic gradients and the composite weights the stochastic gradients calculated to generate a descent direction.\nThe main claim is that this correlation issue does not become apparent until several iterations of the algorithms, therefore while MGDA, PCGrad and CAGrad will generate a good descent direction in early iterations, they will fail to do so as the algorithms proceeds. and therefore using momentum coefficient that starts close to 0 and convergences to 1 will solve this issue. The authors provide analysis for both convex and nonconvex cases with no assumptions of the lipschitzness of the composite weights .", "questions": "302: added sum in the theorem ? $\\sum_{i=1}^m$.\n760 (second line): why $||E_{\\zeta_k}[\\| \\sum_{i=1}^m (\\lambda_i^k \\nabla f^i(x_k) )+  d_k\\|] || \\leq \\sqrt{\\|||E_{\\zeta_k}[\\| \\sum_{i=1}^m (\\lambda_i^k \\nabla f^i(x_k) )+  d_k\\|] ||\\|}$?", "limitations": "The property of the momentum coefficient $\\alpha_k$ i.e. it starts close $0$ and converges to $1$ and decreasing step size $\\eta_k$ propose slower convergence speed than methods that does not use momentum and fixed step-size.\n No comparison with the convergence rate of vanilla MOGA alogorithms is provided.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strenghts:\nThis paper serves as a general framework that includes many methods used MOO. \nVery straight forward example of a stochastic case where MGDA, PCGrad and CAGrad do not generate a descent direction.\nThis paper avoids unrealistic assumptions such as gradient-wise lipschitzness of composite weights.\nAnalysis for two important classes of functions: convex and nonconvex.\nIllustrative experiments showing the effectiveness of the proposed approach.\nWeaknesses:\nNo analysis for strongly convex functions.\nAssumption of bounded gradients. \nHard to understand analysis. \nCritical typos:\n225: $E[d_k] = (0,-\\epsilon)$  should be $E[d_k] = (0,\\epsilon)$ i think.\n240: the direction is $- \\nabla F(x_k) \\lambda_k$.\n691: missing $\\Sigma$ and added $-$?\n716: the bound for the first term is not correct.\nAdditional typos:\n128: $\\mu$ should be in subscript.\n47: coefficients plural\n168: R is in calligraphic style \n197: asymptotically converge\n581: missing brackets\n672: $=$ instead of $\\leq$\n294: MODA ?\n495: Pareto optimal is always weakly Pareto optimal.\n702: Double sum $\\sum_{i=1}^m$\n725: missing sum (second line)\n727: $\\lambda_k^i \\in [0,B]$\n747: Before the final proof\n766; double $E_{\\zeta_k}[\\| d_k\\|]$\n806: missing $n_k^2$", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9Hps-6zzbS", "reviewer": "Reviewer_nhC2", "summary": "The main claim of the paper is that the stochastic gradient alteration algorithms do not always converge to Pareto optimal solutions. \nThe authors focus on multi-objective settings and present a unified algorithmic framework consisting of various gradients with respect to multiple objectives. The authors further propose a novel scheme that averages the previously calculated weights exponentially. \nThe authors also show that gradient alteration algorithms can converge to an optimal value with the same rate as single objective stochastic optimization by using a momentum-like exponentially averaging mechanism.", "questions": "- Could the authors include the error bars for Table 1 and 2 and also in the Figures?\n- Could the authors also maybe adjust the Figures to have time in x axis?", "limitations": "The limitations are not discussed. There is no potential negative societal impact.  ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## STRENGTHS\n- Multi objective optimization is an important topic, since there are many real life scenarios, applications and this is explained well in the paper. \n- The conjecture \"altering the stochastic gradients yields a direction that even degrades all the objectives in expectation\" is novel and presents a different way of looking at the problem \n- The paper is well-written.\n## WEAKNESSES\n- The presented results seem promising but I kindly request minor extensions for a slightly more convincing experimental results. \n- The error bar is missing for the experimental results, since the numerical values are very close it is important to do the analysis for different stochastic settings multiple times.  It is mentioned that the reported value is the mean of 3 runs but it would be still nice to see the error bar and maybe more number of iterations. \n- Similarly time analysis along with the accuracy and error values would be great. \n- Minor: In the checklist the limitations are said to discussed in Appendix but it is not discussed. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept