MGDA Converges under Generalized Smoothness, Provably
Authors: Qi Zhang
Peiyao Xiao
Shaofeng Zou
Kaiyi Ji
Venue: ICLR 2025 Poster (2025)
Keywords: Multi-Objective Optimization
Generalized Smoothness
Convergence Analysis
Sample Complexity
Primary area: optimization

Abstract: Multi-objective optimization (MOO) is receiving more attention in various fields such as multi-task learning. Recent works provide some effective algorithms with theoretical analysis but they are limited by the standard $L$-smooth or bounded-gradient assumptions, which typically do not hold for neural networks, such as Long short-term memory (LSTM) models and Transformers. In this paper, we study a more general and realistic class of generalized $\ell$-smooth loss functions, where $\ell$ is a general non-decreasing function of gradient norm. We revisit and analyze the fundamental multiple gradient descent algorithm (MGDA) and its stochastic version with double sampling for solving the generalized $\ell$-smooth MOO problems,  which approximate the conflict-avoidant (CA) direction that maximizes the minimum improvement among objectives. We provide a comprehensive convergence analysis of these algorithms and show that they converge to an $\epsilon$-accurate Pareto stationary point with a guaranteed $\epsilon$-level average CA distance (i.e., the gap between the updating direction and the CA direction) over all iterations,  where totally $\mathcal{O}(\epsilon^{-2})$ and $\mathcal{O}(\epsilon^{-4})$ samples are needed for deterministic and stochastic settings, respectively.  We prove that they can also guarantee a tighter $\epsilon$-level CA distance in each iteration using more samples. Moreover, we analyze an efficient variant of MGDA named MGDA-FA using only $\mathcal{O}(1)$ time and space, while achieving the same performance guarantee as MGDA.

Published as a conference paper at ICLR 2025
MGDA CONVERGES UNDER GENERALIZED SMOOTH- NESS, PROVABLY
Qi Zhang"', Peiyao Xiao"?, Shaofeng Zou' & Kaiyi Ji²
School Electrical, Computer and Energy Engineering. Arizona State University! Department of Computer Science and Engineering, University Buffalo² {qzhan26 61, zou easu.edu, (peiyaoxi, kaiyiji @buffallufoo..oo edu
ABSTRACT
Multi-objective optimization (MOO) is receiving more attention in various fields such as multi-task learning. Recent works provide some effective algorithms with theoretical analysis but they limited by the standard L-smooth bounded- gradient assumptions, which typically do not hold for neural networks, such as Long short-term memory (LSTM) models and Transformers. In this paper, we study a more general and realistic class of generalized ê-smooth loss functions, where l is a general non-decreasing function of gradient norm. We revisit and analyze the fundamental multiple gradient descent algorithm (MGDA) and its stochastic version with double sampling for solving the generalized f-smooth MOO problems, which approximate the conflict-avoidant (CA) direction that maximizes the mini- mum improvement among objectives. We provide a comprehensive convergence analysis of these algorithms and show that they converge stationary point with a guaranteed e-level average CA distance (i.c., the gap be- tween the updating direction and the CA direction) over all iterations, where totally O and (c) samples are needed for deterministic and stochastic settings, respectively. We prove that they also guarantee tighter c-level CA distance in each iteration using more samples. Moreover, we analyze an efficient variant of MGDA named MGDA-FA using only O(1) time and space, while achieving the same performance guarantee as MGDA.
e-accurate Pareto
INTRODUCTION
There have been a variety of emerging applications of multi-objective optimization (MOO), such as online advertising (Ma et al. 2018), autonomous driving (Huang et al. 2019), and reinforcement learning (Thomas al. 2021) Mathematically, the MOO problem takes the following formulation.
F+ min F(x) (Jr()) fa(x), fx(())
2ER
where K is the total number of objectives and f& (z) is the k-objective function given model parame- ters v. Under the stochastic setting, (x) = E,, [& (x; s)), where 8 denotes data sample. MOO setting, we are interested in optimizing all the objectives simultancously. However, this problem challenging due to the gradient conflict that some objectives with larger gradients dominate the update direction at the sacrifice of significant performance degeneration the less-fortun objectives with smaller gradients. Thus, a widely- target is to find the Pareto stationary point æ that the performance of all objectives cannot be further improved without compromising some objec- tives. A variety of MOO-based methods have been proposed to mitigate this conflict and find a more balanced solution among all objectives. In particular, the multiple gradient descent algorithm (MGDA) (Désidéri, 2012) aims to find conflict-avoidat (CA) update direction that maximizes the minimal improvement among all objectives and converges to Pareto stationary point which there is no common descent direction for all objective functions. This idea then inspired numerous follow-up methods including not limited CAGrad (L.iu et al. 202T), PCGrad (Yu et al. 2020).
GradDrop (Chen et al. 2020), FAMO (Liu et al.) 2024) and FairGrad (Ban & Ji 2024) with
"Equal contribution.

---

Published as a conference paper at ICLR 2025
convergence guarantee in the deterministic setting with full-gradient computations. The theoretical understanding of the convergence and complexity of stochastic MOO is not well-developed until very recently. Liu & Vicente (2021) proposed stochastic multi gualdegt (SMG) stochastic version of MGDA, and established its convergence guarantee. /Zhou et al. (2022) analyzed the non-convergence issues of MGDA, CAGrad and PCGrad in the stochastic setting, and further proposed convergent approach named CR-MOGM. More recently. Fernando et al. (2022) and Chen et al. (2024) proposed single-loop stochastic MOO methods named MoCo and MoDo, and proved their convergence to an c-accurate Pareto stationary point while guaranteeing an c-level average CA distance over all iterations. Xiao al.] (2024) proposed a double-loop algorithm named SDMGrad that enables to obtain an unbiased stochastic multi-gradient via a double-sampling strategy. They established the convergence SDMGrad with a guaranteed e-level CA distance in every iteration, which we call as iteration- CA distance.
However, all existing works are limited by the standard L-- smooth and nounded-gradien assumptions. Nevertheless, a recent study (Zhang et al. 2019) indicates that such assumptions may not necessarily be true for the training of neural networks and an alternative (Lo, Lm)ssmohh condition was observed and studied, which assumes the Lipschitz constant to be linear in the gradient norm and the gradient norm be potentially infinite. Furthermore, this phenomenon has been consistently observed in our experiments (c.g., see Figure Interestingly, it has been widely observed that MGDA algorithms always converge even under such generalized smoothness conditions (Sener & Koltun 2018 Liu et al. 2021; Xiao et al. (024)). This naturally raises a prouoki- question:
Tosk1
1.75
1.50
1.25
Busi og
0.75
0.50
0.00
Gradient norm
Figure 1: Local smoothness constant vs. gradient norm for training SegNet on CityScapes dataset of Task 1.
Q. Can the fundamental MGDA algorithm provably converge under the generalized smoothness condition, while achieving a sufficiently small CA distance?
This question remains open due to the following challenges.
The analysis of existing MOO methods cannot be generalized to this (To, I1) -s)-smoothssss directly due to the possible unbounded smoothness or gradient norm. In addition, all existing works (Reisizadeh et al. 2023 Zhang et al., 2019 Li et al. 2024b a Ji et al. 2021| Crawshaw et al. 2022 Chen et al. 2023 Zhang et al. 2024 in generalized smoothness are limited to the single task problems, which are fundamentally different from the MOO problems since even though each single task is generalized smooth, the linear combination of these tasks is not necessarily generalized smooth. In this paper, we provide an affirmative answer this question. Our main contributions are summarized below.
1.1 OUR CONTRIBUTIONS
We establish comprehensive convergence analysis for MGDA under the generalized smoothness condition, in both the deterministic and stochastic settings. Morcover, the analysis covers both the average CA distance and the iteration-wise CA distance.
Weakest assumptions in MOO. In this paper, we investigate the generalized f-smooth assumption, where é is general non-decreasing function of gradient norm, and includes both the standard L- smooth and (Lo, Li )smooth assumptions as special cases. This assumption finds many applications, such LSTM models (Zhang et al.] 2019), transformers (Crawshaw al., (022), distributionally robust optimization (Jin et al.) 2021) and higher-order polynomial functions (Chen et al., 2023). assumption, which is required in previous sis to ensure the bounded multi multi-grrddeet approximation. To the best of our knowledge, this is the first work to investigate generalized smoothness MOO problems. Table presents detailed comparison of assumptions with existing analyses.
In addition, we do not make any
Convergence analysis. We first show that the vanilla MGDA method can converge to an é-accurate Pareto stationary point, while guaranteeing a small e-eeeel average CA distance. A warm start process
CA distance means the distance between the updating direction and the CA direction. Its formal definition be found in Section 2.4
2

---

Published as a conference paper at ICLR 2025
is introduced before the main loop of MGDA to achieve more aggressive c-level iteration-wise CA distance. In the stochastic setting, we provide the convergence guarantee for MGDA with a double sampling, which was introduced by Xiao et al. (2024); Chen et al. (2024) to obtain unbiased multi-g multi-gradient approximations. Furthermore, we analyze a computation- and memory-efficient variant of MGDA, named MGDA with fast approximation (MGDA-FA), which updates the objective weights w using only forward passes of F(-) rather than gradient VF, effectively reducing ((K) time and space (1) without hurting the performance guarantee.
Sample complexity comparison. To achieve an c-accurate Pareto stationary point and an c-level average CA distance, we show that MGDA require Oee and O(e=4) samples in the deterministic and stochastic settings, respectively. Both of these complexities match with the existing best results. Furthermore, to achieve an e-level iteration-wise CA distance, MGDA with warm start requires an increased number of samples, at the order of O(e and O²) respectively, in both deterministic and stochastic scenarios, due to smaller step sizes and mini- data sampling, shown in Table [1] Typically, achieving an e-level -teration-wise CA distance results in much higher sample complexity, such as (c)-21) in Fernando et al. 2022), O Pin in Chen et al. (2024) and O in Xiao et al. (2024) for non-convex stochastic setting. Moreover, we show that -G achieves the same performance guarantee as vanilla MGDA.
1.2 RELATED WORKS
braddent-based multi-objective optimization. A variety of gradient manipulation techniques have emerged for simultaneous learning of multiple tasks. One prevalent category of methods adjusts the weights of various objectives according to factors such as uncertainty (Kendall et al., 2018), gradient norm (Chen et al.] 2018), and training complexity (Guo et al. [0118) Methods based on MOO have garnered increased attention due to their systematic designs, enhanced training stability, and model- agnostic nature. For instance, Sener & Koltun (2018) framed Multi-Task Learning (MTL) MOO problem and introduced an optimization method akin to MGDA (Désidéri) 2012). Afterward, many MGDA- methods have been proposed mitigate gradient conffict with promising empirical performance. Among them, PCGrad (Yu et al. (2020) avoids conflict by projecting the gradient of each task on the norm plane of other tasks. GradDrop (Chen et al., 2020 randomly drops out conflicted gradients. CAGrad (Liu et al. (022I) adds a constraint on the update direction to be close to the average gradient. NashMTL (Navon et al. 2022) and FairGrad (Ban & Ji 2024) formulated MTL as a bargaining game and a resource allocation problem, respectively. Theoretically, |ernando et al. (2022) proposed a provably convergent stochastic MOO method named MoCo based on an auxiliary tracking variable for gradient approximation, Chen et al. (2024) characterized the trade-off among optimization, generalization. and conflict avoidance in MOO. Xiao et al. (2024) proposed and analyzed stochastic MOO method named SDMGrad with a preference-oriente regularizer. However, all these works rely on the T-smoothness and bounded- -eaddienn assumptions. In contrast, this paper focuses on the MOO problems with generalized f-smooth objectives.
Generalized smoothness. The generalized (Lo, Li >smoothness was firstly proposed by Zhang et al. (001)). which was observed from extensive empirical experiments in training neural networks. A clipping algorithm was developed by Zhang et al. (2119) and the convergence rate was provided. Later, Jin al. (2021) analyzed the convergence of a normalized momentum method. The SPIDER algorithm was also applied to solve generalized smooth problems in Reisizadeh et al. (2023): Chen al. (203)), where et al. (2023) studied new notion of a-symmetric generalized smoothness, which includes (Lo, L, -mmoothnnsss as a special case. Very recently, a new generalized ê-smoothness condition was studied in Li et al. (2024a]b), b), which is the weakest smoothness condition and includes all the smoothness conditions discussed above. However, all the existing works generalized smoothness are limited to single-task optimizations and the understanding of MOO is insufficient. This paper provides the first study of MOO under the generalized E- e-moothhess condition.
2
PRELIMINARIES
2.1
GENERALIZED SMOOTHNESS
The standard L-moothhness condition is widely investigated in existing optimization studies (Ghadimi
& Lan 2013 Ghadimi al. 2016), which assumes function f X + R to be L-smooth if
'The order differs from Chen al. 2024 due to different definitions of the e-accurate Pareto stationarity and is taken when both e-accurate Pareto stationarity and e-level iteration-wise CA distance can be achieved.
3

---

Published as a conference paper at ICLR 2025
Method
Smoothness
Assumption
Setting
Complexity
CAGrad (Liu et al
2021
(LS)
(OD)
Deterministic
N/A
PCGrad Yu
2020
(I.S)
(C) (RC)
Deterministic
N/A
SMG (Liu Vicente
2021
(L.)
(C) or (BC)
Stochastic
N/A
ER-MOGM (Zhou
2022
(I.S)
(BF) and (BG)
Stochastic
O
MoCo Feennadd
2022
(LS)
(BF) and (BG)
Stochastic
O
MoDo (Chen et al. (024)
(LS)
(BG)
Stochastic
O(c
SDMGrad (Xiao al.
20224
(ISS)
(RG)
Stochastic
O(e-4)
MGDA (Them. and
(GS)
N/A
Deterministic
O
Stochastic MGDA (1 (Thmm. aandd
(GS)
N/A
Stochastic
O(c
Comparison to assumptions in existing analyses. MGDA Désidéri 2012) assumes the access of optimal update direction and step size for each iteration and gets an asymptotic result thus is omitted in the table. Explanation are standard L-smooth while (GS) the objectives are generalized f-smooth as defined in Definition I (OD) denotes the assumption of optimal direction in each iteration, (C) denotes the convex loss function assumption, (BC) denotes a lower bound on multi-task curvature, which is defined as H(f. 2, 2²) So f(x) & far + a(x V f (z)dda for function f. (BF) denotes the bounded function value assumption and (BG) denotes the bounded gradient assumption; 3 Sample complexity
Table 1:
the upper footmarks: 1 (LS) indicates that the objectives
achieving eaaccurate Pareto stationary point. N/A denotes no exploration non-convex settings.
there exists a bounded constant L such that for any 2, y E X. Nevertheless, recent studies show that in the training of neural networks such LSTM models (Zhang et al. 2019), transformers (Crawshaw et al. 2022), distributionally robust optimization (Jin et al.] 2021 and high-order polynomials functions (Chen et al. 2023), the standard L-smoothness assumption does not hold. Instead, a generalized (Zo, Ly J-mooohessss assumption was observed and studied in the training of LSTM models in [Zhang et al. (2019), which assumes that for any x E X, fx)]] < Lill unbounded and reduces the L-smoothness L1 Later, a more generalized assumption was proposed and studied in Li et al. (024a):
< L| yll-
This assumption implies the Lipschitz constant is potentially
Definition 1. (Generalized E-smoothness, Definition in et al. tiable function f : X + R is generalized f-smooth if [(x) S {x)](( almost everywhere in X, where L. [0, +oo) > (0, +20) is continuous non-decreasing function.
2024a ). A real-valued differen-
The (Lo, Li -smoothnesss is special case of generalized É-smoothness, where E(a) Lo + Lia. Another definition of generalized smooth is widely used and equivalent to the f-smoothness:
Definition 2. ((r, (rrr))smmotheesss Definition 2 in Li et al. (2024a)). real- vall-valued differentiable function f X + IR is (r. -moohh for any I E X. Blx, r( ff()))) E X, and for any T2 E B(x, r( (())) [[ - fzz)) < f(I (1)(] æ2ll. where for continuous functions r: [0, (00) + (0, -00), non-increasing, & non-decreasing and B(x, R) is the
Euclidean ball centered at x with radius R.
In B(x, r(] I()) f is also L-smooth where L - (x))). Definitions I and are equiv- alent (Li al. 2024a): An (r, E--smooth function 4-smooth; and é-smooth function satisfying Assumption is (r. m) mm-ooo with m(u) == E(u + a) and r(u) = a/m(u) for any a > 0.
2.2 PARETO CONCEPTS IN MULTI-ORJECTIVEE OPTIMIZATION (MOO)
MOO aims to find points at which there no common descent direction for all objectives. Considering points 3i, .22 E I we claim that dominates 322 if f((x1) > f((x2) for all [K] and F(x,) * (x2)). We say a point is Pareto optimal it is not dominated by any other point. other words, we cannot improve optimal point. non-conven settings, MOO aims to find a Pareto stationary point defined as follows.
objective without compromising another when reach a Pareto
Definition 3. x E R is a Pareto stationary point if min [/ 0, where W is the probability simplex over [K). J. an e-accurate Pareto stationary point min [/))() ?
4

---

Published as a conference paper at ICLR 2025
2.3 EXISTING MOO ALGORIHTM
Deterministic MOO. One of the big challenges of MOO is the gradient conffict, i.e., the gradients of different objectives may vary heavily in scale such that the largest gradient dominates the update direction. As a result, the performance of those objectives with smaller gradients (Yu et al.) (2200) may be significantly compromised. As the most fundamental MOO algorithm, MGDA tends find a balanced update direction for all objectives by considering the minimum improvement across all objectives and maximizes by solving the following problem
max min (f(x)) - fi(z (add)add)))) ~ max min (V dER KE[ a
(2)
dER" KE[K]
where a is the step size, d the update direction, and the first-order Taylor approximation is applied To efficiently solve the above problem in eq. (2), substitute the following relation
max min (V((()),) ||d||2 dER KE[K]
max min dER WEW
V(((z)),, d)
1
|d].
(3)
where the regularization term -1lld] is to regulate the magnitude of our update direction. The solution to the problem in eq. (3) be obtained by solving the following problem (Désidéri 2012):
d" v s.t. w² E arg min
/V
wEW
The above approach has been widely used in various variants of MGDA such as SDMGrad, CAGrad, and PCGrad (Xiao al. 2024 Yu et al. 2020
Liu et al. 2021).
Stochastic MOO. SMG (Liu & Vicente 2021 is the first stochastic MGDA. It directly replaces the gradients with stochastic gradients and the update rule becomes
d- VF(z;))u"; s.t. w E arg min FVF
wEW 2
where FF(x; s) the estimate of VF(z) based on the sample s. However, this leads to a biased gradient estimation of the update direction d',, and thus it requires an increasing batch size. To solve this issue, another work MoCo (Fernando et al. 2022) introduces a tracking variable Y stochastic estimation of the true gradient. Afterward, double-sampling strategy is proposed by Chen et al. (2024): Xiao et al. (2024) to generate a near-unbiased update direction.
Strong assumptions in analysis. All the works mentioned above require bounded gradients such as Chen et al. (2024); Fernando al. 2002)); Xiao et al. (2024) or T-smoothness such as Ban & Ji (2024); Liu et al. (2021): Navon et al. (2022) Yang et al. (2024). Their analyses do not apply to generalized E-smoothness objectives, since the Lipschitz constant is potentially infinity.
2.4 CONFLICT-AVOIDANT (CA) DIRECTION AND CA DISTANCE
We call the update direction d' in eq. (4) the conflict-avoidaan (CA) direction since it mitigates gradient conflict. Though it may not be feasible to calculate the exact CA direction, we aim to find an update direction be close the CA direction. Therefore, measuring the gap between the CA direction and the estimated update direction is important, which we define as the CA distance.
Definition 4. ||d d' is the CA distance between estimated update direction d and CA direction d'.
The larger the CA distance is, the further the estimated update direction will be away from the CA direction, and the more conflict there will be. In single-loop algorithms. MoCo (Fernando et al. 2022 ensures the average CA distance over iteration of the order of while MoDo (Chen et al. 2024) guarantees the e-order iteration-wise CA weight distance (as stated in their Theorem 3.4). Meanwhile, the double-loop algorithm SDMGrad (Xiao et al., 2024) guarantees an e-order CA distance in every iteration. In this work, we analyze the CA distance in both cases and provide convergence results.
3
MGDA ALGORITHMS UNDER GENERALIZED SMOOTHNESS
3.1 MGDA WITH AND WITHOUT WARM START
has been shown in eq. 44 that MGDA needs to approximate the optimal weight wt and the optimal updating direction d² However, since the optimal weight w² of the convex function is not unique,
5

---

Published as a conference paper at ICLR 2025
deal with this issue by adding lg regularization term and the problem becomes
1 IVF(z)) 1 (llull?
w arg min wEW 2
(5)
Besides the benefit of a unique solution, adding f2 regularization term also makes (x) Lipschitz continuous (Fernando et al., 2022). Note that w' (x) may not be Lipschitz continuous because (F(x) ( may not be positive definite. Nevertheless, the analysis of CA distance is difficult because w" may not be Lipschitz continuous. Thus, we will characterize the gap between w" and w plus the change of w. after adding this l regularization term. As result, the update rules become We first update wi by projected gradient descent process and compute the update direction de V to update model parameters.
Lines 5-6 in Algorithm
[
For our single-loop algorithm, CA distance is proportional the term ||w, - wil which decreases as the algorithm iterates with some error terms controlled by appropriately chosen small step sizes. If we initialize uig randomly, ||w0 e |l will be a constant order, and so will the first CA distance. Meanwhile, we can only get an c-order CA distance after a certain iteration number i' >> when ||w w takes an order. Thus, we introduce an extra warm start process using Algorithm to guarantee the new wi close enough to W and small level CA distance in every iteration. However, this warm start process is not needed if we only require small averaged CA distance.
Algorithm 1 Single loop MGDA with and without warm start
1: Initialize: model parameters weights and constant
2: Option I: wo wo. To. # for analyzing deration-wise CA distance for analyzing averaged CA distance
Option Wo wo
4: for = 0, ,...., T do
5: Wr+11 = Tw [00, (())()))
(VFF(.))FF(xx))u) FF(x)) + pive)
6: 31+1
aVF (x:))
7: end for
Algorithm 2 warm-start(wop vo. p)
I: for 1.... N do
2: Wo++1 = Hw (wa (w
3 /'(V ((/(())) ( (F(o)w + puo.))
3: end for
4: Output WN
3.2 STOCHASTIC MGDA WITH DOUBLE SAMPLING
In the stochastic setting, our algorithm keeps the same structure, having a warm start process aim control the CA distance in every iteration. In Algorithm we do the same projected gradient descent without using stochastic gradients. This is because we only need to compute Fxxx))
(VF Fz0)) once and reuse it in the whole loop, which does not bring computational burden. Then in the update loop, we update the weight and model parameters accordingly. We use double- sampling strategy here to make the weight gradient estimator unbiased (Xiao et al. (2024) such that de is a near-unbiased multi-gradient E2V))(x;; (Z₁
pw,] VF(z) FF(x;) (((z))) ww + pwr,
where (2,)), and VG3(#;) are independent and unbiased estimates of (2,). Similarly, we do not involve warm start process if we require the average CA distance to be small.
3.3 MGDA WITH FAST APPROXIMATION
can seen from Algorithm and Algorithm that MGDA requires O(K) space and time to compute and store all task gradients at each iteration for updating the weight wy This becomes drawback when the number of tasks or the model size large. Motivated Liu et al. (2024), one solution is use the Taylor Theorem approximate the gradient for updating the weight w; as
F(xx)) F( = FZ(x,) (z, - x(+1) R(x,) a aVF (z,) [F(I)) R(xz),
where R(x;) is the remainder term and it takes the order R(x,) = o( [[| - x 119), which can be made sufficiently small by adjusting the step size. By incorporating this fast approximation (FA)

---

Published as a conference paper at ICLR 2025
in Algorithm| we then present MGDA-FA in Algorithm (shown in Appendix where zt is updated along the update direction de = V (x;,)) wu to get 2141 following by the update rule of w/
F F(x)) F( +pu.)
W(+1 = 11w (wr
(6)
As result, in the model parameters update process, MGDA-FA only requires one backward process by calculating the gradient of F(x;)ux w.r.t. x; without storing it, and additional forward processes to compute F ( in the weight update process. This approach saves computational and memory costs in the practical implementation significantly. Most importantly, we provide a theoretical guarantee for this efficient method (in eq.
Algorithm Stochastic MGDA with Double Sampling
1: Initialize: model parameters Ho, weights wo and constant p
Option I: wy- zo. p) analyzing iteration-wise CA distance
3: Option II: Wpp f We
# for analyzing averaged CA distance
4: for t = 0, 0, 1..,, T do
5: Te+1
VV
6: WC411 = Tw (wx ((VG2(m) VGa(m)) + pwv)) # double sampling
7: end for
CONVERGENCE ANALYSIS UNDER AVERAGE CA DISTANCE
In this section, provide the theoretical results for Algorithms and without warm starts to obtain an e-accurate Pareto stationary point, with the average CA distance over iterations in O()).
4.1 DETERMINISTIC SETTING
Assumption 1. Each objective function ft Vi [K] is twice differentiable and lower bounded by
/ == =nR= f((x) > -00.
Assumption Each objective finctioo fi Vi E [K] generalized E-smooth defined in Definition
where c [0, +xx) + (0, +o0) is a continuous non-decreasing function such that sp(a) monotonically increasing for any 2 O.
22(2a) is
These assumptions are the most relaxed ones in existing MOO works since they directly assume
objective smoothness or gradient/function value boundness (Liu et al. 2021 Fernando et al. 2022
Navon et al., 2022] Xiao et al.) 2024] Chen et al.) 2024| Yang et al. [024 Ban Ji (024).
also includes the widely studied standard L-smoothness (Nemirovskij & Yudin, 1983 Ghadimi
Lan 2013; Ghadimi et al. 2016), (Lo, L1 )-moothnssss (Zhang et al. 2019) as special cases.
Moreover, for any 0 < < and x X, our assumption even holds for function such that [[v] < Lo + L=IVV(())] where are limited to [0, 1] in Chen et al. (2023).
Let > 0 and F > 0 be some constants such that A + S F, where A maxie[K] (f((z)) f:).
Define M = supf2 2 0/p(2)) < F). We then have the following convergence rate for Algorithm |
Theorem Let Assumptions ! and hold. Set
O ( ) = O + ).
max (e 3 ) p23
and = (E²). We then have that ETD | F2;))wll <
The full version with detailed constants and detailed proof can be found in Appendix D.1 Theorem provides the first convergence rate to obtain an e-accurate Pareto stationary point for MOO problems with generalized f-smooth objectives. Moreover, it achieves the optimal sample complexity in the order of (E -2 for GD with single standard T-smooth objective (Carmon et al. 2020). The MOO
problems with generalized f-smooth objectives are challenging due to two reasons: 1) F [x) is
potentially unbounded in our generalized '-smoothness setting, making all existing analysis in MOO
(Liu et al. 202T Fernando al. 2022 Navon et al. 2022 Xiao et al.) 2024] Chen et al. 2024 Yang et al.] 20224] Ban & Ji 2024h not applicable. 2) the update of x includes all gradient information from each task, making the existing adaptive methods for single generalized smooth functions invalid.
To solve the challenges in Theorem [
we find that a bounded function value implics a bounded gradient norm. Thus in proof, we use induction show that with parameters selected in

---

Published as a conference paper at ICLR 2025
Theorem for any w W and S T, we have that F(zy) is upper bounded by F. Consequently, for any é E [K]. we have that [[)( I M, which solves the unbounded gradient norm problem in our generalized smoothness setting. Then we can show that || (Z,()),, converges.
Corollary 1. Under the same setting in Theorem /
Ei
I| (F)) VF( O(?).
The proof is available in Appendix
D.2 Corollary shows that the average CA distance converges.
4.2 STOCHASTIC SETTING
In the stochastic setting, we assume that we have access to an unbiased stochastic gradient (2; 8) instead of the true gradient fa()), where is the collected samples. To prove convergence, we have the following assumption.
Assumption 3. There exists some 2 0 such that B[(l/)((;;)) {((=)) S a² for any i E [K]
Assumption 3 indicates bounded gradient variances, which is widely studied (Xiao al. 2024 Li
et al. [222a] Fermando et al. 2022). At time in the stochastic model, let $t,; = (St.i.1. s1,5 st,ik)
be the 2-th collection of samples and F Fxx; st,i) (fi (zx; st..1). (2 st,i2), (..2)......))) fo (1,,))
Note that E [3] because we have samples in Algorithm 3 Define St.i
We choose Gi(zt) = F(xe; 81.))
F (2:) (G,(
Let F. > 0 and 0 < 0 < be some constants such that F F> 4(A+)) and M = szp(2 2 010(2) S
F). Define the following random variables 71 (nin(1]3 [K], (1( - 5 F) A T, 72
min 3i [K],j E [3], ||s.j,all > La AT, T3 = min E [K], ||
vap JA
Vap
and r = min(71. T2, r3), where Lo. L1 > 0 are some constants and a A b denotes min b). We
have the following theorem for Algorithm 3
Theorem 2. Let Assumptions
1
2 hold. Set p 0
2e2 O(mint 374. x 1), a
Om,nn 7M++1)" M pT. STM
P.
1) and Omaxx 1 M² bae 8-27
1). We then have that with the proba-
bility at least 1 1- 8, + EE [VF())) o
The full version and detailed proof can be found in Appendix D.3 When we set ax 3. and T T O))=)), we can find an e-stationary point with the optimal sample complexity in the order of O for SGD with a single L-smooth objective (Arjevani et al. 2023). Note that in the proof of Theorem I show for each t < T and w W, we have that F (z,) )w is bounded by applying small constant step size a and B3. However, this condition does not necessarily hold for our stochastic setting due to the unbounded gradient noise. To solve this problem, we introduce stopping time т. The advantages are as follows: 1) for any & S w E W, we have that F F(x))U is bounded; 2) for any < T, the norm of gradient noise is bounded; 3) due the optional stopping theorem, for any ws] = O. Thus, we can further get the following lemma: Lemma 1. Using the parameters selected in Theorem 2
E W and i E (3), we have that
have that [[F((z)u)) [w] F I
6F
E
E [V
The proof of Lemma is available in D.4 Lemma J
indicates that EE EE (=(x))
is bounded by some constant and if T (dr)) ). Note that {r <T) = fr2 TTUfT < TJUfT < T, 72 = T, = 7}. The first two events are related to the gradient noise, where the probabilities can be bounded by Assumption and Chebyshev's 's inequality. The last event indicates that for some
with high probability, we have that
T LnD |V (2;,),, - - O
E [K] we have (xz) - ft
a.
F Based on Lemma I and Markov inequality, we can show that
P((n < T, T2 = T, T3 T))
and we further show that F(r T) 21- We then have
that T Ei | ((x, ) converges with high probability. Similar to Corollary Theorem also
1
implies the average of CA distances converges with time with high probability.
5 CONVERGENCE ANALYSIS UNDER ITERATION-WISH WISE CA DISTANCE
In Section 4 we show that the average CA distance is bounded under generalized smooth conditions. The average CA distance is also studied in MoCo (Fernando et al. 2022 and MoDo (Chen et al.
8

---

Published as a conference paper at ICLR 2025
2024)
with the bounded gradient assumption and these works only focus guarantees of the average CA distance over iterations. However, a c-level average CA distance only implies the smallest CA distance to be e-level. Since want to keep the update direction close enough to the CA direction, it better to have a tighter bound CA distances. In this section, we show the iterative CA distance is (c) with warm-start process and convergence results for Algorithms and
5.1 DETERMINISTIC SETTING
Deterministic setting without fast approximation. We first provide results about bounded iteration- wise CA distance for Algorithm I with a warm start.
Theorem 3. Let Assumptions 7 and 2 hold. Set 3' S MT.P O O(E)) O(e"),
N = 3) as constants, and T O(E All the parameters satisfy the requirements in the formal version of Theorem and we have [ ( O
The finite time error bound and the full proof can be found in Appendix H.1 Since our parameters satisfy the requirements in the formal version of Theorem T we can find an e-accurate Pareto stationary point with OEe-11) samples. In the analysis of CA distance, we show that the CA distance can be bounded by the term ||u; " plus the strongly-convex constant Meanwhile, there is decay relation between || - w and || wi,pl with some error terms controlled by step sizes. Nevertheless, the eттоr terms will accumulate since we do telescoping on this decay relation, which will be the dominating term. Thus, step sizes have to be much smaller than the choices in Theorem D to guarantee iteration wise small CA distance.
Deterministic setting with fast approximation. In this section, we show the convergence rate of Algorithm
f and bounded peration-wiss CA distance.
Theorem 4. Let Assumptions
| and 2 hold.
Set N ()==)) 8' S T P e bT as constants, T = (mmxx ae? Be
O( [in {e aT }).8 ( 0 Ommin( (B,
-- We have T
The full version and proof can be found in Appendix E. We can easily extend the analysis in Appendix [.I the convergence analysis of Algorithm 4 under the average CA distance, because the only extra effort is dealing with the remainder term, which can be bounded by the smallest step size. As result, the sample complexity remains the same O(c-11 to achieve Pareto stationary point.
Theorem 5. Let Assumptions | and hold. We choose 3 < N. O(E), = O(Et) a(=)) O(e"), N ( 2) constants, and T O(c-1), We have that [ V O(e).
5.2 STOCHASTIC SETTING
In this section, we show that Algorithm with warm start and mini-batcher achieves bounded iteration-wis wise CA distance with high probability. In this section, we choose Gz(z,) = E D F( St,i), where n, is the size of the mini-batch.
n,
Theorem 6. Let Assumptions 2 and hold. Set B I Mr. =
I
p= O
n. = 9((-0))))000 ),c--,,,,, N (2(-2), and T o(c-11), and all the parameters satisfy the requirements in VF(r))w; O with the probability at least 1 5.
Theorem We then have [[
The full version with detailed constants and proof can be found in Appendix E.4 Since our parameters satisfy all requirements in Theorem 2 we can find an e-accurate Pareto stationary point with high probability. Compared with Theorem 2 guarantee an iteration- wise CA distance, despite our warm start process, mini-batch method is required in our analysis. This is because given = T, the gradient not unbiased. In Theorem 2 the optional stopping theorem is applied which indicates that the expectation of the cumulative gradient is zero. However, for each iteration, this optional stopping theorem does not hold and the estimated error is controlled by the size the mini-batch. Then, the sample complexity to get Pareto stationary point becomes O -17) due to necessary mini-batch ng.
EXPERIMENTS
In this experiment, we evaluate the performance of the Cityscapes Cordts et al. 2016) and NYU- v2 (Silberman et al. 2012) datasets. The former involves pixel-wise tasks: 7-class semantic

---

Published as a conference paper at ICLR 2025
Sogmentation
Depth
Surface Normal
Metbod
Angle Distance
Within 1"1
MR 4
Am%
mloU
Pix Acc 1
Abs Ear J
Ret Eir
Mean
Median
11.25
22.5
30
63.76
0.6754
0.2780
25.01
19.21
57.20
69.15
LS
39.29
65.33
0,5493
0.2263
28.15
23.96
22.09
47.50
61.08
7.89
5.59
38.45
64:27
0.5354
0.2201
27.60
23.37
22.53
48.57
62.32
7.33
4.39
RLW al. 2021
57.17
63.77
0,5759
0,2410
28.27
24.18
22.26
47.05
60.62
9,89
7.78
DWA
[B 6 mi
2019
99.11
65.31
0.5510
0,2288
27.61
23.18
24.17
50.18
62.39
7.11
3.57
Repall
0.2260
22.61
49.05
7,11
2012
30.47
59.90
0.6070
0.2555
24.8%
19.45
29.18
56.88
69.36
5.56
1.38
MoCo
Fernaioo 0
2022
40.30
66.07
0.5575
0.2135
26.67
21.83
25.61
51.78
64.85
5.00
0.16
0.2405
20.33
7.55
Nash-MiTT
NNaven
Naveen o1
2022
40.13
65.93
0.5261
0.2171
25. 26
20.08
28.40
55.47
68.
3,33
-4.04
FAMO
(Liu
2022
38.88
64,90
0.5474
0.2194
25.06
19.57
29.21
56.61
68.98
3,22
-4.10
MGDA-warm start
40.57
67.17
0.5240
0.2281
25.21
19.74
28.74
55.79
68.21
2.78
-4.2
Table 2: Multi-task supervised learning on NYU-v2 dataset for different MOO methods comparison.
segmentation (Task 1) and depth estimation (Task 2) while the latter involves 3 pixel-wise tasks: 13-class semantic segmentation, depth estimation and surface normal estimation. Following the same experiment setup of (Xiao et al., 2024). we build a SegNet (Badrinarayanan et al. 2017) as the model. We compare the performance of MGDA with warm start, which is used to ensure a small
CA distance per iteration and mitigate gradient conflicts, against popular MGDA-type methods
including MGDA (Désidéri 2012), PCGrad (Yu al.. 2020). GradDrrop (Chen et al. 2020), CAGrad
(Liu et al. (021), MoCo (Fernando et al. 2022), MoDo (Chen et al.] (024). Nash-MTL (Navon al., (022), and FAMO (Liu al., (024). Since SDMGrad (Xiao al. (2024) incorporates
preference-based regularization within the MGDA framework, we exclude it from the tables to ensure a fair comparison. We utilize the metric Am% to reflect the overall performance, which considers the average per-task performance drop versus the single-task (STL) baseline to assess methods. It can be observed in Table Table 3 that MGDA-warm start has a much more balanced performance. Meanwhile, the proposed MGDA-FA is much faster shown in Table 5 in the Appendix.
We also illustrate the relationship between the gradient norm and the local smoothness for each task of the Cityscapes dataset. To do this, we compute them according to the method provided in Section H.3 in Zhang et al.] (2019). We scatter the local smoothness constant against gradient norms in Figure I for the semantic segmentation task and depth estimation task in Figure 2 (in the appendix), ,, respectively. Both results demonstrate a positive correlation between them, which further substantiates the necessity of our analysis. More experimental details can be found in Appendix B
Segmentation
Depth
Method
Am
mloU1 1
Pix Acc
Ahs Fir I
Rel Fir
STL.
74.01
93.16
0.0125
27.77
MGDA Desideri 2012
68.84
91.54
0.0309
33.50
44.14
PCGrad Yu 2020
75.13
93.48
0.0154
42.07
18.29
GradDrop erai
2020
75.27
93.55
0.0157
47.54
23.73
CAGrad (Liree 2044
75.16
93.48
0.0141
37.60
11.64
MoCo
Pemando el mi 2022
75.42
93.55
0.0149
34.19
9.90
MoDo Clien
74.55
93.32
0.0159
41.51
18.89
Nash-MIL Navonn ei al
2023
75.41
93.66
0.0129
35.02
6.82
FAMO (Liu al
74.54
93.29
0.0145
32.59
8.13
MGDA-warm start
75.41
93.46
0.0133
31.07
3.93+11.19
Table 3: Multi-task learning on Cityscapes dataset.
7 CONCLUSION
Building upon our observations of MGDA convergence under the (Lo, L1) smoothness condition, this paper provides a rigorous convergence analysis for both the fundamental MGDA and its stochastic variant under a more challenging, relaxed, and practical generalized (-smoothness assumption. Furthermore, we introduce a warm start progress to provide a more precise control over the iteration- wise CA distance. Our analysis also shows that an efficient variant named MGDA-FA, which uses only ((1) time and space, achieves the same performance guarantee MGDA. We anticipate that the convergence analysis developed in this work will provide valuable insights for analyzing other MOO algorithms such as CAGrad, PCGrad, FairGrad and FAMO under the generalized smoothness condition. The warm-start strategy may be of independent interest to other single-loop MOO algorithms to achieve sufficiently small heration-wiss CA distance.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
The work of Q. Zhang and S. Zou was partially supported by NSF under Grant CCF-2438429. P. Xiao and K. Ji were partially supported by NSF grants CCF-2311274 and ECCS-232652)
REFERENCES
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199(1): 165-214, 2023.
Vijay Badrinarayanan, Alex Kendall, and Roberto Cipolla. Segnet: A deep convolutional encoder- decoder architecture for image segmentation. IEEE transactions on pattern analysis and machine intelligence, (9(12):2481-2495, 2017.
Hao Ban and Kaiyi Ji. arXiv:2402. 15638, 2024.
Fair resource allocation in multi-task learning.
arXiv preprint
Amir Beck and Mare Teboulle. Gradient-based algorithms with applications signal recovery. Convex optimization in signal processing and communications, pp. 42-88, 2009.
Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, 184(1):71-120, 2020.
Lisha Chen, Heshan Fernando, Yiming Ying, and Tianyi Chen. Three-way trade-off in multi-objective learning: Optimization, generalization and conffict-avoidance. Advances in Neural Information Processing Systems, 36, 2024.
Zhao Chen, Vijay Badrinarayanan, Chen- Yu Lee, and Andrew Rabinovich. Gradnorm: Gradient normalization for adaptive loss balancing in deep multitask networks. In International conference machine learning, pp. 794 803. PMLR, 2018
Zhao Chen, Jiquan Ngiam, Yanping Huang, Thang Luong, Henrik Kretzschmar, Yuning Chai, and Dragomir Anguelov. Just pick a sign: Optimizing deep multitask models with gradient sign dropout. Advances in Neural Information Processing Systems, 33:2039- 22500, 2020.
Ziyi Chen, Yi Zhou, Yingbin Liang, and Zhaosong Lu. Generalized-smoode nonconvex optimization is as efficient as smooth nonconvex optimization. arXiv preprint arXiv:2303.02844 2023.
Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele. The cityscapes dataset for semantic urban scene understanding. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3213-3223, 2016.
Michael Crawshaw, Mingrui Liu, Francesco Orabona, Wei Zhang, and Zhenxun Zhuang. Robustness to unbounded smoothness of generalized signsgd. Advances in Neural Information Processing Systems, 35:9955-9966 2022.
Jean-Antoine Désidéri. Multiple-gradient descent algorithm (mgda) for multiobjective optimization. Comptes Rendus Mathematique, 350(5-6):313-3 2012.
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. In The Eleventh International Conference on Learning Representations, 2022.
Guillaume Garrigos and Robert M Gower. Handbook of convergence theorems for (stochastic) gradient methods. arXiv preprint arXiv:2301.1 2023.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal Optimization, 33(4):2341-2366 2013.
Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Mathematical Programming, 155(1-2):267-30)
2016.
11

---

Published as a conference paper at ICLR 2025
Michelle Guo, Albert Haque, De-An Huang, Serena Yeung, and Li Fei-Fei. Dynamic task priori- tization for multitask learning. In Proceedings of the European conference on computer vision (ECCV), pp. 270-287, 2018.
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 2719, 2019.
Jikai Jin, Bohang Zhang, Haiyang Wang, and Liwei Wang. Non-convex distributionally robust optimization: Non-asymptotic analysis. Advances in Neural Information Processing Systems, 34: 2771-2782, 2021.
Alex Kendall, Yarin Gal, and Roberto Cipolla. Multi-task learning using uncertainty to weigh losses for scene geometry and semantics. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 7482-7491, 2018.
Haochuan Li, Jian Qian, Yi Tian, Alexander Rakhlin, and Ali Jadbabaie. Convex and non-convex optimization under generalized smoothness. Advances in Neural Information Processing Systems, 36, 2024a.
Haochuan Li, Alexander Rakhlin, and Ali Jadbabaie. Convergence of adam under relaxed assumptions. Advances in Neural Information Processing Systems, 36, 2024b.
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.1003,, 2021.
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: 1878888--,,,,0 2021.
Bo Liu, Yihao Feng, Peter Stone, and Qiang Liu. Famo: Fast adaptive multitask optimization. Advances in Neural Information Processing Systems, 36, 2024.
Shikun Liu, Edward Johns, and Andrew Davison. End-to-end multi-task learning with attention. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 1871-1880, 2019.
Suyun Liu and Luis Nunes Vicente. The stochastic multi multi-gradient algorithm for multi-objectivv optimization and its application supervised machine learning, Annals of Operations Research, pp. 1-30, 2021.
Jiaqi Ma, Zhe Zhao, Xinyang Yi, Jilin Chen, Lichan Hong, and Ed H Chi. Modeling task relationships in multi-task learning with multi-gate mixture-of-experte Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 1930-1939, 2018.
Aviy Navon, Aviv Shamsian, Idan Achituve, Haggai Maron, Kenji Kawaguchi, Gal Chechik, and
Ethan Fetaya. Multi-task learning as bargaining game. arXiv preprint 2xXi:22222.0017 2022.
Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Amirhossein Reisizadeh, Haochuan Li, Subhro Das, and Ali Jadbabaie. Variance-reduced clipping for non-convex optimization. arXiv preprint arXiv:2303.0088; 2023.
Ozan Sener and Vladlen Koltun. Multi-task learning as multi-objective optimization. Advances in neural information processing systems, 31, 2018.
Nathan Silberman, Derek Hoiem, Pushmeet Kohli, and Rob Fergus. Indoor segmentation and support inference from rgbd images. In Computer Vision-ECCV 2012: 12th European Conference on Computer Vision, Florence, Italy, October 7-13, 2012, Proceedings, Part V 12, pp. 746-760. Springer, 2012.
Philip S Thomas, Joelle Pineau, Romain Laroche, al. Multi-objective spibb: Seldonian offline policy improvement with safety constraints in finite mdps. Advances in Neural Information Processing Systems, 24:2004-2017, 2021.
12

---

Published as a conference paper at ICLR 2025
Peiyao Xiao, Hao Ban, and Kaiyi Ji. Direction oriented multi-objective learning: Simple and provable stochastic algorithms. Advances in Neural Information Processing Systems, 36, 2024.
Ahrection-oriented
Haibo Yang, Zhuqing Liu, Jia Liu, Chaosheng Dong, and Michinari Momma. Federated multi- objective learning. Advances in Neural Information Processing Systems, 36, 2024.
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: 5824-5836, 2020.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. arXiv preprint /90. 2019.
Qi Zhang, Yi Zhou, and Shaofeng Zou, Convergence guarantees for rmsprop and adam in generalized- smooth non-convex optimization with affine noise variance. arXiv preprint arXiv:2404.01436 2024.
Shiji Zhou, Wenpeng Zhang, Jiyan Jiang, Wenliang Zhong, Jinjie Gu, and Wenwu Zhu, On the convergence of stochastic multi-objective gradient manipulation and beyond. Advances in Neural Information Processing Systems, 35:38103-383 15, 2022.
13

---

Published as a conference paper at ICLR 2025
A
NOTATION SUMMARY
We have summarized the notations used in this paper in the following table.
Table 4: Notations and their descriptions.
Notations
Descriptions
a E I
Model parameter, or decision variable
i-th collection of samples at time t in the stochastic model for training or testing
fa(z)
A scalar-valued population ohjective function
fe()))
Gradient of fa)),, with far) : R R rector-valued population objective function
F(r)
((x)
Gradient of Fxx), with F(z) R - R
((a)
continuous non-decreasing function: [0, (0,) - (0. +00)
((a)
monotonically increasing for any 2 0: (p(a) 20(20]
2
E eW
Weighting parameter in probability simplex over [K].
w ew
optimal solution equation 5 when p = 0, it is simplified w"
Step size to update model parameter æ Step size to update weight in the main loop Step size to update weight in the warm start Regularization parameter in equation
3'
P
B EXPERIMENTAL DETAILS
B. RELATION BETWEEN GRADIENT NORMS AND THE LOCAL SMOOTHNESS
We show the relation between local smoothness and gradient norms of each task in this part. Both results demonstrate a positive correlation between them, which further substantiates the necessity of our analysis.
Tascs
Tasc2
1.75
0.4
1.25
0.3
llrecton
1.00
0.15
0.-
2.50
0.5
Gradient
Gradient
Figure 2: Local smoothness constant vs. Gradient norm on training SegNet on CityScapes dataset of each task. Task on the left and Task 2 the right.
B.2 RESULTS AND RUNNING TIME COMPARISON BETWEEN MGDA-WARK START AND MGDA-FA
We compare the results and average running time of the proposed algorithms, MGDA-warm start and MGDA-FA the Cityscapes (Cordts et al., 2016). The time in Table is an average of the total running time over epochs (in minutes). The result solidifies the advantage of the fast approximation. For its performance, the fast approximation may introduce substantial errors in practice, potentially leading to inaccuracies in the weight update process. Meanwhile, the convergence analysis of the stochastic variant is not revealed. However, to enhance its effectiveness, we could apply logarithmic technique in FAMO(Liu al. 2024).
14

---

Published as a conference paper at ICLR 2025
Segmentation
Depth
Method
Am% +
Average running time
mloU t
Pix Ace
Abs Err +
Rel Err
STL
74.01
93.16
0.0125
27.77
MGDA-warm start
75.41
93.46
0.0133
31.07
3.93
2.93
MGDA-FA
74.38
93.24
0.0160
41.78
19.44
1.93
Table 5: Multi-task learning on Cityscapes dataset.
B.3 RESULTS OF OTHER MOO METHODS WITH WARM START
The warm start strategy can be applied to other multi-objective optimization algorithms. For MGDA- based methods, both MoCo (Fernando al. 2022) and MoDo (Chen et al., 2024) can incorporate the warm start as an add-on. However, the MoDo MoDo-warm warm start will exactly recover to our algorithm. Therefore, we evaluate the performance of the MoCo-warm start on the Cityscapes (Cordts al. 2016) and NYU-v2 (Silberman et al. 2012) datasets. As shown in the following tables, the warm start strategy improves performance.
Segmentation
Depth
Method
Am% |
mloU 1
Pix Acc t
Abs Er +.
Rel Hm
MoCo
75.42
93.55
0.0149 0.0148
34.19 31.43
9.90
MoCo-warm start
75.48
93.54
7.32
Table 6: Multi-task supervised learning with MoCo-warm start on Cityscapes dataset.
Segmentation
Depth
Surface Normal
Method
Am%
Angle Distance |
Within / 1
mloU
Pix Acc f
Abs Fir
Rel Err
Mean
Median
11.25
22.5
30
MoCo
40.30
66.07
0.5575
0.2135
26.67
21.83
25.61
51.78
64.85
0.16
MoCo-warm start
38.40
64,40
0,5377
0.2315
26.04
20.57
27.11
54.02
66.63
-0.88
Table 7: Multi-task supervised learning with MoCo-warm start on NYU-v2 dataset.
B.4 IMPLEMENTATION DETAILS
Multi-task learning on Cityscapes dataset. Following the experiment setup in Xiao et al. (2024), we train method for 200 epochs, using SGD optimizers for both model parameters and weights, and the batch size for Cityscapes 8. We compute the averaged test performance over the last 10 epochs the final performance measure. We fix the 3 0.5 and do a grid search on hyperparameters including N E [10, 20, 40, 50), a E [0.0001, 0.0002, 0.0005, 0.001], and P E [0.01, 0.05, 0.1, 0.2, 0.5, 0.6, 0.7, 0.8, 0.9, and choose the best result from them. It turns out our best performance is based on the choice that N = 40, a = 0.0005, 3 = 0.5, and p = 0.5. The choice of hyperparameters for MGDA-FA turns out be the same that for MGDA- start. All experiments are run on NVIDIA RTX A6000.
Multi-task learning on NYU-v2 dataset. Following the experiment setup in Xiao et al. (024). we train our method for 200 epochs, using SGD optimizers for both model parameters and weights, and the batch size for NYU-v2 is 2. We compute the averaged test performance over the last 10 epochs as the final performance measure. We fix the 3 = 0.5 and do grid search on hyperparameters including N E [10, 20, 40, 50], a E [0.0001, 0.0002, 0.0005, 0.001], and [0.01, 0.05, 0.2, 0.5, 0.6, 0.7, 0.8. 0.9. 1] and choose the best result from them. It turns out our best performance is based on the choice that N 40, a = 0.0001, 3 0.5, and = 0.5. All experiments
NVIDIA RTX A6000.
15

---

Published as a conference paper at ICLR 2025
Am% reflects the average per-task performance drop versus the single-task (STL) baseline b to assess method m. We calculate it by the following equation
K
Am%
1 (-1)" (M Mo,k)/Ma Mo,k x 100,
Σ A=1
K
where K is the number of metries, Ma. is the value of metric Ma obtained by baseline b, and M obtained by the compared method m. l if the evaluation metric Ms on task prefers higher value and 0 otherwise.
Generalized smoothness illustration. To illustrate the relation between gradient norms and local smoothness, follow the method in Section H.3 in Zhang al. (2019)and run SGD on each task sepa- rately without the warm start process. The code is available in clipping accelerates. Since there is weight update process, only need to choose 0.0005 for both tasks.
C ALGORITHM
Algorithm MGDA with Fast Approximation (MGDA-FA)
Initialize: model parameters zig weights wn constant P
2: my=aarm-start WW. To.
3: for = 0, .... do
4: Zt+1 2t V (zz)),
5: Update W/ according to eq.
6: end for
D DETAILED PROOFS FOR AVERAGE CA DISTANCE
D.1 FORMAL VERSION AND PROOF OF THEOREM
Let F > 0 be some constants such that
Define M sup(= 2 0/{(2) < FJ. We then have the following convergence rate for Algorithm without warm start:
Theorem 7. Suppose Assumptions and are satisfied, and we choose constant step sizes that
S 4KM a I min 3, 20[++1)' ME(M+1) }. 2 max { (194 10
} O ((E=)), and p s
min 20 108 2T v Tof = (c2)). We have that
2
(F(o,)ulll T
(8)
Proof. Compared with the standard L-smoothness, the generalized smoothness is more challenging to address due to the unbounded Lipschitz constant. Lemma demonstrates that bounded function value implics a bounded gradient norm, which further implies a bounded Lipschitz constant. In the following, solve the unbounded Lipschitz constant problem by showing that the function value is bounded with the parameters selected in Theorem [ that f(())) fr < F by induction.
We prove that for any i K and t < T we have
Base Case: since M non-negative, according to equation 7 we have that f.(xo) - f < < holds for any i [
Induction step: assume that for any i E [K] and t < < T, we have that f((x,) - ftt < F holds. We then prove that fx(x++1) f F holds for any E [K].
16

---

Published as a conference paper at ICLR 2025
For f((22) f? < F, based on the monotonicity shown in Lemma 2 have that [ M.
From assumption we have that fi(x) is (EII ((IVf(())) + 1)) -smooth by setting
a For any t - k. we have that
| xz |l a VFF S aM S ((M+ <(IVA(+=+++))
where the second inequality is due M[M++1 and the last inequality is due [[ M.
Based on Assumption Definition and Lemma 3.3 in (Li et al. 2024a), we have the following descent lemma:
f((x+11) S - VF(2)))) E(IV (((x)) + V(
s a( VF(x)) {(M + 1)
As result, for any E W, we have that
F(Z+41) & F(x))w (VVF(z)) VF(x))))) + (1M+1) Based on the update process of w, we have that
a² (F
(9)
Wh+1 = 1lw Wr - (VVF(()) VF(x)); + +wu))
then follows that
W++1 w|2
1Tw -B((F((z)) (VFFF())(((aa)
F (F: + pmv))
VF(x))) < W/ - 3 VF(xx) T + prcc) ) w0
|w, w|| - 23 (w: w, (VF(I)) VF(x,) + pf)w:)
B² ([)))())))) ((x) + pT)
where the inequality is due to the non-expansiveness of projection. By rearranging the above inequality, have that
(w) w. VF(x;) T (F()))))
23 (1
w||2
|| ==l + 2p (K =p²
(10)
Plug equation 10 into equation and we can show that
F(x++1)w- F(x:)w
a VF(l))ull E(M +1)
2 a a FFI
(1lrr w||2 || w1l
ap2 + 2ap. (11)
23
Taking sums of equation
from L to k. for any w E W we have that
F(x441)w F(ro)w
V wey + +
(M++1)
a² (BKM²) [IVF(1))ur1
2
1=0
1=0
a
Wp w| + Ta + 2Tpp
23
<
|wo
w||2
+ Ta,3p² 2 2Tap,
(12)
23
17

---

Published as a conference paper at ICLR 2025
where the first inequality is due to < T and the last inequality is due to that S 26(M+1) and 3KM < 1. Thus for any E [K] it can be shown that
f((x+11) f $ f((o)) f. + Taßp' 2Tap S F,
since we have that 3 S 1, Tr:32 and 2Tap S Now we finish the induction step and can show that f((xx+1) - ft 2 and equation 12 hold for all < T and [K].
Specifically, for 2E[M+1) 3 S 4KM². according to equation 12 for T we have that
T-
IVF (1 2(F(wo) F*
2 BT
+ 23p² + 4p = 0(?))
T Am D
aT
which completes our proof.
Lemma 2. (Lemma 3.5 in Li et al. (2024a)) If function J is E-smooth, we have that [=) ((()) f(x) -".
((IVI(())II
(13)
D.2 PROOF OF COROLLARY I
Proof. Recall that
VF (uf 1|2
( + V wi 2 (z; )w,, VF(x))w;)
V (ar))ell 2 V ue 2| V
FF(r )orl
V w11
VF(x))url
where the first inequality holds because of the optimality condition of w
arg wiw 2 [VF((x)) that for any w W,
(w, VF(z.) VFFx))) (wf, VF(2) (F(I:))7) = VF
Then we have
T-1
- Σ
[VF(s,)) (F())) < T IV 0(33),
1=0
where we follow the same setting Theorem
| The proof is complete.
D.3 FORMAL VERSION AND ITS PROOF OF THEOREM
Let 0, c3 0,
0, cs > 0, cs be some constants. Let and 8 be
some constants such that
8(A + + + 03 +
cc)
F>
where A max (f((z)) fd) Let Lu > 0, > 0 0, > 0, some constants,
for B = min
4LC(MM1Je+ HMMKKLatd MoLKMMMMKKK." {M++))3
min 6e2
622
13520
1,8222
(
384K
min
8,2
bap
1} = O d=3
192K +o
< min
2 M, 313, pB1 (30+0))
[(M+1)
Vog
5c2
[((+1)0=
I(M+
18

---

Published as a conference paper at ICLR 2025
min(cs: 24Ka² 8Ko ):
8L BLi
" p3T = ( i(M+ Tēz prr BTIZ))
pT
and T 2 max +8A+488,
1008 (30 M3
M²2 Omaxx hoce 82 }) such that
F
b1 + + by tc + ap(1+ 4a3KM S
(14)
2
Define the following random variables
71 min (1444))))1 J F}A AT,
Lo Vap
72 min [K],j E [3]. |E >
} AT,
L1 J AAT.
73 min [ E [lcc:
Vap
min (2,
We then have the following theorem:
Theorem 8. If Assumptiinss 7 and hold, with the parameters selected above, we have that
with the probability at least - 6.
Proof. Small probability of the event {7 < <T.
We first show that the probability of the event {r < T} is small: P(r < 7) < 6. Note that
{T TT (12 < U < U) < <T, T, =T}
For any E [K].jj E [3]. have that
Lo P( Vap'
1 ap
o²op
P(
13
where the last inequality is due Chebyshev's inequality. Based on the union bound, we have that
T- Σ
Lo
3Ko²apl
P(tre <TH) <
P(
>
<
(15)
Vap 1B
t=0
6L. Similarly, we have that
since p < 21KoaaT
L _
Li
o² o'ap
Plle
Vap
ap
L
follows that
T-1 K
K
I
K2 K20AapT
8
P((TS < <T)) $
(16)
aa
L
8"
We then bound the probability of the event {π < T, T2 = T, T3 = T). Since = Ti < T, we have that for some i [K], fe(x++1) f F.
19

---

Published as a conference paper at ICLR 2025
According to equation 21
shown in Lemma 1 for any i E [K] and t we have that
f((x++1) fi(),) - all
{(M 1 1)aa fl,, w; + a
+ +ap + a
3
+a2eeel2 + aMMM + ar 2
+4aBKM + 40,3M (|x,21
4a3 || + 40
SaM Lo
+ + + 1)a
Lg
+
a +
tap+ + +ap+
a.p
vap
B
VRLo
VKLo
VKL
+aM
+
+ aaM
Vap
Vap
Vap
+ 448KM 4a KLP
+ 44 KL
KL3
+ 4a
ap
op
op
- h + + by + + ap + 3p) + 4aBKM
F
$ 2'
where the first incquality is due to that 72 Ta T, and the second one is due to
by p SKMLL
and # min (3MVKL++MVKLL)) 1y
by
However, for some E [K], f(I++1) - fi > F. Thus for this task, we have that
F
[x(x)) - ( 2
According to Lemma
we have that
[lf((r)) fi1 1 8
F.
8
Based on Markov inequality, it follows that
[[fi(x+) - fi] 5
P (f((z)) - f7 2 I
S
(17)
F/2
4'
which indicates that P(Ti- < T2 = T3 T) / It follows that P(T T) < 2
Convergence of E
ETS (VF(())well' r] Based equation 24 in Lemma
have
that
E
V F (o)))eell (0x)
T
1
E
VVF
PPT T)
4F(1o) W
4F*
432 + +02)
+ 44008(M + +1) + 4p
aT
VT
448p² 163K 323KM222 163Kod
8 2 22
where the second inequality due to 8 parameters. As result, we have that
1/ and the last inequality is due to our selection of
E + VV
e T)
5
I
(F >0
<
(18)
T
2
T=
20

---

Published as a conference paper at ICLR 2025
where the first probability is due to Markov inequality. Thus we have that
P
Σ
VF(ar)oul S
T
1
( 2 T P(T=T)
2 - P(T< -
T t=
21- 8.
where the last inequality is due equation completes the proof.
15
equation
16
equation
17 and equation T8 This
D.4 PROOF OF LEMMA
Proof. For all i E [K]. 1 7, we have fi(x:) - f/ F which further implies that [[((()))] M. Moreover, we have that for any t S T and i E [K],
(2 + w s (M
Lo vap)
| =ell S Vl
M+
M
S 1(M +1)
Since fi(x)) [[(ト < ([]] -smooth, follows that
[((4+1) - fi(x)) (V)(()) (G) (Z.)wo)) e(IV 1) a² VG As result, for any w E W. we have that
F( - F(x:)w a (VF(2,)), (ZI(2,) + {(M + a² (z,),ull
2
$ F(m)) a aVF(( VF(x:)w)) + (
+ M + 1)aa 1 (x;) + {(M + 1)a2|ler,
(19)
Based on the update process of w, we have that
| - w
|1TTw (w. - (Va(art)) + pir)) w
S 11(we - (2, T VGz(zt))r + pw:)) w|l
I|w, - =wll 28(w; (VG2(x,)
VG3(zt) VV + p)w))
+ (z,) T VGa(z;)
+ p)w;l1
where the inequality follows from the non-expansiveness of projection. It follows that
23(w); w. (z,,,) T F
< (llw: 2 ||04 w|l²) + 2.p 23
+ 23 (w: - we &T ( VV(xz) E,,301 ,(
+ 28 ([)))) V
( ( (x() E,, + T 20,
< (Ilwz - w012 - ||:||| - =|] + 28p 232
+ 23 (w: - w. T V x. VV w1,3 s
+ + KM - 8 M 1 M2 || + 8.3 IeTToer,w..l?
(20)
Combine equation 19 and equation 20 and we can get that
F( F w - < E1,1
+ {(M + ( + {(M + 1) 1)a 1
+ a
28 (Iwr - w|l² | w + ap + a;3p²
+ a aw - w, VF + VF 51,3 - e
+ 448KM1 + 4a || 2 4a3.1 15 + 4a 40001=T725
(21)
21

---

Published as a conference paper at ICLR 2025
Taking expectation and sum up equation 21 from t to 1, we have that
[xF(x+)w] F(ro)
-
V VF(r))lll
ofE Σ V (xx)) en
W1 w. 2/ VF(c)) + (F( E1,3 st2c)se)))
+ aE
+ {(M + 1E
| we
wo - w||2 + apT + a.3pTT + 23
+ 44.3K + 1
||
+ +4,3MM2
||r,31|2
+ 40,3E
|| 2r
E
V VFF
t.E
V F (2)) El,ww)))
1=0
+aB
We 2. VF(x)) VF(x)) Ex,3 (.220,304))
110
m + apT T.3pTT
+ 4a8KM'T + To
40 4o
(22)
where the last inequality is due to that r S T and for any i E [K].j E [3]. E En |la
s
E ETo || < TKo By the optional stopping theorem, we have that
E
(F)()) O,
which further implies that
-= &+,1))
E[M]|=+1 I11 S M
E 1
M
E
1 12
MoVT++
V2MoVT.
(23)
Similarly, we have E Eid (
$ V2MovT, E
EED (1
v2MovT and (VF (T
S V2KMo²VT.
22

---

Published as a conference paper at ICLR 2025
Based equation 22 and equation 23
we have that
E ([(((x))ur F"w S F(ro)w - w E
VF (
(3
1=0
+ + 10M2 + a + apT + aBPTT
+ +43KM*T + T
+ 4433KM 0² 4o
8F E
(24)
which completes the proof.
E DETAILED PROOFS FOR ITERATION-WISE CA DISTANCE
We first provide some useful lemmas, which will be used in our main theorems.
Lemma (Continuity wip))- Suppose Assumptions 7 and 2 are satisfied. If for any
(V((al S M and || x++1ll S 8MM4IJ, we have,
(1w)(a)) (x2-1)l S L F Z+11l..
where L, = 2p KM + +).
Proof. We first define that wQ.e( W the Q-th iterate of a function J(w) = 2 (F(x)) [| using projected gradient descent (PGD) with constant step size The update rule ( = IIw ((L1- Bp)1
(p)1 - (VF(z;) VF(x:))uq.ptzy By the non-expansiveness of
projection, we have
(xzz) wQ+1, (
<11((1 3p) (VF(z))VF(z))) (F(
((1 Bp) - -VV (44
<1 - I -VF,, VFF (1) (F
+ -/1((VF VF(x,) (F(())) V ((44))
<(1 - 3p) -
-
+ (l((V VF((x) (
Since set (zx) = (x, and (x++ < 1, telescoping the above inequality over Q gives,
[w - wQ & S (VVF(()) (VF())) VF(x.)
VF VF (F
(25)
Then according the Seauchy-Shwward inequality, it follows that
2 (x)) - (x(+1l < lim (11x)( - (10300)))
+ [I - (Q,
lim
|| -xQ, (110)((0)) - 1,g_
+ VIF VF(2.) V (FF4)))
(6)
4
lim
2V p3Q
+ + [VF[ VF (F (F(4))F((H)))
Q+x
(26)
23

---

Published as a conference paper at ICLR 2025
where (i) follows from eq. (25 and (ii) follows from the convergence of PGD (Theorem 1.1,
Beck
Teboulle 2009)) on p-strongly convex objectives that
(xx) - (xx))
(1x) - we. (24 (x
(Jr))()))) - ((we,)()))) <
23Q
P3Q
Then eq. (26) can be bounded by
[1x (2++1ll
So (IVE(a)) (F((), VF(x)) ( (
22p 1 KMM(M +
1)[l, M Xe+1l|.
where the last inequality follows from [z)]] M and fa(x) (ाा Vt
1) -mooth by setting a = 1. The proof is complete.
Lemma 4. Given wi = arg min / ((,) and wi, = arg min [1F
2 [ we have
[VF(r:) VF(ct)) vp.
Proof. Recall that wt, arg min V + &|/l1 then we have
(x;)) 112 2 || | F (1F())) 2 [ -1 | 2
By rearranging the above inequality, we have
[[; [ S p(1 - 2)
S p-
Then recall that w, arg min V we have
[[))()) - (F())) 1| = [ | 3 2 (F(x))
(VF(ax)) (
Sp, where the first inequlity follows from the optimality that
-2(wi VF(x.) VF(x))w() I - V/
The proof is complete.
Lemma 5. Suppose Assumptions and 2 are satisfied. for any i E [x]] s M and
|1, x++1ll= S ((M+1)' we have
[R(x:)| < a² K²KM + 1)M2
2
Proof. According to the Talyor Theorem, we have the following result for any objective function f((x), E [K].
[((m))) = f((xx) + VSJ (#x)( - -x.) Ra(xx).
where Ra (2(x)) is the remainder term. Then according to the descent lemma of each objective function fe(z), we have
M(x+1) (1(())) + V. (1x) - x2)) ) + ạ ((IVV(())))
+
2
{(M +1
<)(x)) + (1 xx) ) + a
V (F
2
Then obtain
{(M+1 11)
(2(x,) S a²
(F(x))
2
Thus, according to the Cauchy-Schwartz inequality have
|[(x;)]] < a {(M - 11)
2
K + 1)M2
/F(rx)w
2
2
The proof is complete.
24

---

Published as a conference paper at ICLR 2025
E.1 PROOF OF THEOREM
Theorem
9.
Suppose
Assumptions
and
2 are
satisfied.
We choose 23p (of. AKMMa 2, a S
3'
M .N
(((3),
KM
P. S
min
min
B, MEM++ (1)
2 M'
Doe
pEa
T
max
10A ae
23
O(--1), and p S
min
20 27a
10
Tap
=
O
The CA distance in every iteration takes the order
of (+).
Proof. Since our parameters satisfy all requirements in Theorem | we have that [V M. According to the definition of CA distance, we have
(F(()) - [F(x)) VF(xx)w VF ) VF VF(x))
V (F(x))uii
VF(xx) - VF(x))) + |VF(
V
VKMBus wi vp.
(27)
where (i) follows from Cauchy-Son SSchhy---cwarzz inequality and (ii) follows from [f(x))) S M for any i
and Lemma 4 Then for the first term in the above incquality on the right-hand side (RHS), we have
|| W o1
||we+1
wipp' + 1|15+1, wi 2(w wip w wi+1p wi,p)
(28)
For the first term the RHS in the above inequality, have
(i)
| wi
VF + pw)] wipp11
Iw=- - - 23 (V ( (F(o)) + pire, We - wi,p)
+ VF(x;) ( pw,ll
(4)
(1 (B-)) w (p + VKMY)
(29)
where (i) follows from the non non-exxaasiveness projection and (it) follows from properties strong convexity and Shuuch-Schwartz inequality. Then for the second term on the RHS in eq. (28), we have
||wi+1,p wł,p! 12 < L2 = = ( < a² L2M M
(30)
Then for the last term on the RHS in eq. (28), we have
2(we-1 wi,p: Wi+1.p wipp)
<2||we+1 (itpplllu,++,, w
<2( will + l/uee wi D.ll wi
FF(x)), 22 (VF + pws, pw: VF + 3ppl2c. - w +
|| w
3p
MC + p) + Bpllw, - p 11 4a La2L?.M²
(31)
3p
where (i) follows from the update rule in Algorithm
i Lemma and Young's inequality. Then
substituting eq. 29 eq. (30p and eq. (31) into eq.
28
we have
|we41 w , 2 <(1 Bp) - + 32(p
3KM2 a L2,
4a L2
L M M(KKM2 + +
Bp
4a 4a2 M
<(1 Bp) - w2,p11 +,3 + a 2 M2 20 MC, +
3p
25

---

Published as a conference paper at ICLR 2025
where the last inequality follows from Lemma 5 and C1 VKM2 + p. Then do telescoping over = 0, 1....
| - w 11? S(1 - (3p= 1p)²"|un - w 3 cf
a² I2 M2
20
4a M
+
C1
Bp
P
3²p2
Then recalling that L = ( and substituting the above inequality into eq.
27
we have
VF(x))) -
$
+ a² 3p
S VMM (1pppp)1up
-
+
Cf
M+
2a M
4a²L,
C1 +
+ Vp
3²
- Bp) -0
1|w0 mo +
+ a
Vo)
Bp
Since we run projected gradient descent for the strongly convex function ((w) / V F
Zo We |2
|lw,,11 in the N-loop in Algorithm according to Theorem 10.5 (Garrigos & Gower 2023). we have by choosing 8' (0, 3/2
1
wo 2== ||NI "o 1 < 2
N
M
Thus, ||wg - w |l O()) as N = O(p-))) CA distance takes the order of e in every iteration by choosing O(E2), 8 O O and N = ()) The proof is complete.
E.2 FORMAL VERSION AND ITS PROOF OF THEOREM
Let 0,0 0, Cg. & 2 and F 0 be some constants such that
A a +
and C 2 VKM² + p+ IKMM+1)M
We then have the following convergence rate for Algorithm
4
Theorem 10. Suppose Assumptions
7 and 2 are satisfied, and choose constant step sizes that
C7 O S min (1,, V K((M+1MMT BOT K((M+1)M=> :P min (2 d
26
24/
2
2 3 and T >
<
max
1044
ac? 23
We have
v F W(
Proof. Following similar steps in Appendix have that f((2a) - f: S F by induction.
D.I. also prove that for any i E K and < T,
Base case: since all constants C1, cg,, cg. d4 nen-negative, have that fi(zo) ft holds for any i E [K].
Induction step: assume that for any i K and k< T. f. - f s F holds. We then prove fe(xk+1) - Sr < F holds for any E K]. Following similar steps in Appendix D.1 we have
F( S F(xr)w a ((VF(a))) ((())w.) a²E(M + 1)
V F (xx)
(32)
2
26

---

Published as a conference paper at ICLR 2025
Based on the update rule of w and non-expansiveness of projection, we have
||,+11 - w/12 - W 3 F(x)) - (( + +pw.) -w |
w1 8 (VF(x)"VV((x (F( + ppox + R(xr))
|10 w||² 23(wr w. (VF())) VF((x) + pl)we) + + [R(t)l (C2²
|10, w||2 - 23(wz - w; (VF(*)) T VF(x))++ + (p)(z)))+())))))
+ ta +)M+ (C'),
where (i) follows from Cauchy-Schwartz inequality and C₁ 2 vKM² + aKK(+I)M* (ii) follows from Lemma 5 Then have
and
2
(w, - w. VF(x,) VF(x)),, S 2 (1/0, - -wll - 11| w0l²))
+
23
+ aKE(M 1)M2
B(CR)
2
2
Then substituting the above inequality into eq.
(32 we obtain
F((41))-F(()) F(I++1)W - -F(x)) < all al)Ve( a² + 1)
FF w
w/ w||2) + apt a²KE(M - 1)M²
aB((y)²
(1/w; w||²
-||ww1111111 -
+
233
2
Then taking sums of the above inequality from / - 0 to k. for any w E W, we have
k
a + VF(x))
F(ZE+1) - F( 1
Σ
a
+
1=0
1=0
K + 1)M2T
a,((C)²T
+ a
Iwo w|12 + tapT +
23
2
2 + opT + a2 + 1)MP
(33)
2
2
where the last inequality follows from a S H(M+)). Thus, for any i E [K]. it can be shown that
((( S( ft + B tpp + a²KE(M + 11M
aB(C)) SF.
since we have that 3 S c1, c1 apT S cg <2KE(M+))M* S czl, aSC, c4. Now finish the
induction step and can show that f((xx) - St F and eq. 33 hold for k T and E [K].
Specifically, for S 7(M415' we have
IFF 2F(zo)w - 2F
2 3T
Σ t=o
+ 2p aK((M + 1)M² + B(C))²
T
aT
Then following the choice of step sizes, we can obtain
FF 0(22).
The proof is complete.
27

---

Published as a conference paper at ICLR 2025
E.3 FORMAL VERSION AND ITS PROOF OF THEOREM
Theorem 11. Suppose Assumplions M N
and 2 are satisfied.
We choose B' S
= 2(( Ci 2
+ p
aKB(M+1JM*
S
min
(1))2,
Epp
a
S
min (e18, BeTT [(3+1I)
26h
2L M ML
Bpe
Dea
T
max
10A ar
@(c
and
S min
2
= (ee)). The CA distance in every iteration takes the order of O(e).
20 27a
Proof. According the definition of CA distance, have VVF - (2(x,)
(V(az)u - (F(x))uf - (F(a)) V (x:))ull
FF(x))w - VF(xx)) [VF(( V V((:))
VKMluu -6 vp.
(34)
where (i) follows from Cauchy-Schwarr Schwartz inequality and (ii) follows from f((xz)) & M for any i and Lemma Then for the first term in the above inequality the right-hand side (RHS), have
|| 1,ll
||+++
wipp ? || wi,n"l? 2(w wi w wit w
(35)
For the first term on the RHS in the above inequality, we have
We 3 F(xx) F( + +wwx) whip 1
|ee+1
a
We 3 (VF(())) VF(x:) + pmu + R(xx)) ) wip1
a
1w2 -i 1|2 (VF VP(x)) + per, Wi - wi,p)
- (R(z)), we wppp) + 32
T (F(x:) + R(xx)
+ pwl
(88 S (1 2 - w +2 a
|R(x)]| + 8e (++VKM² ||
(36)
where (1) follows from the non-exxansiveness of projection and (it) follows from properties strong convexity and Cauchy-Schwartz inequality. Then for the second term the RHS in eq. (35), we have || - wi,p 1 s L 1|,, xe+1ll² I2 // F( (z.) S a² L2 M2.
(37)
Then for the last term on the RHS in eq. (3),, we have
2ww++1 wi Wi+ w[,p))
<21|wr+1 (e - ul
<2(1|u++1 - -wll + 1|we wi Mll wippll
(1)
L2aBLro F(x,) -F(#+41) + pwr
4
[VF(zz)) + 3pllwr - wi,
wwi+i.p
wi
a
3p
VKM² |[((x))] +p) + -
- wi 4a2
L2,
<2aBLro
(38)
Bp
Then substituting eq.
(36). eq. (37 and eq.
into eq. 35). we have
||w+11 - w
2 5(1 Bp] we wi,pI' 11 + R(Di)l + 32 + VKM² + |[((x))))>
+ +a²I + 30 (VRM²+ + [R(xE)] +D)+ 4a²L3,
3p
<(1 - Bp)][w: wi taKKeMM +
+ 1) (C))2
4a M2
+ - + 20
3p
28

---

Published as a conference paper at ICLR 2025
where the last inequality follows from Lemma 5 and 2 VKM² + + aKE(M+1)M Then we
do telescoping over / = 0, ,,.,, T- -
||wT - wr 5(1 - -3)pppppp 1p)"|ww - - 1)M2 + (C)² 2C))
a²
2ah
4a 4a
1 M +
Oi +
3p
P
B²p²
Then substituting the above inequality into eq.
(34 we have
| Fxx)w, (=(+)))
SVKM (1 Bp) wo
+ a
KeeM + +1M + 2
a² 1 M M
4a M
C4
V
3p
P
3pp²
=0 ( (1- 3p) wo wippll
B
vp).
V
3p
Since we run projected gradient descent for the strongly convex function J(w,) V
(wo) W. 1
f|[w,ll? in the N-loop in Algorithm according Theorem 10.5 (Garrigos Gower, 2023). we have
1w - ~ 12 =l|WN To s 2(1 M +
N
Thus, |1w0o - w || = (e)) as N =((pp)) CA distance takes the order of e in every iteration by choosing O(E*), 3 O a = O(e"), and N = 2)- The proof is complete.
E.4 FORMAL VERSION OF ITS PROOF OF THEOREM 6
Let a, p, satisfy all requirements for Theorem with 8 < 1. Moreover, for p= O(²),,
Q(E ,,3 <
M = O(E*), n, 2 max 36K M (6 (0+0)))))) S2( 6) and a S
5pe2
óp²e"
V 42 (3p-1] (Ee) and T O(E-1),, we have the following theorem:
Theorem 12. If Assumptiinss and hold, with the values of the parameters mentioned above, have that for each t < T,
[VF((z)) VF(x:)wū = O(e).
with the probability at least - 5.
Proof. When T = and < t, according to the definition of CA distance, we have
V ue (z
V - VF(x))wū, - (F(x)) - V (x;))
VF((x)) VF(x:)) IVF( [F(:))u
(1)
KM we - -i Vp.
(39)
where (i) follows from
Schwartz inequality and (ii) follows from [|V - M for any d E [K] and Lemma We then show that for any t < we have that Eillu, - "F,p 2 = 7 < 5 by induction.
Base case: Since we run projected gradient descent for the strongly convex function J (w.)) 1 V ((x))) w,,l + & 11,,,,11 in the N-loop in Algorithm according to Theorem 10.5 (Garrigos
Gower 2023). we have by choosing 3' (0, 3
P )² |mwl - w 11 2= ||w - wo 2 < 2(1
M
29

---

Published as a conference paper at ICLR 2025
Thus, ||200 - 12 O(Gc²) as N 1)p-11)
Induction: Assume we have that Elllw; - -1 S 2c, we will show that E1
wi+1,pl1 || == = T I ge²² holds for any t < T in the following proof. We first divide ||w++1 w 1 11
into three parts:
|| , || wippl + |1iit,,p wi,pll 2( wip wit1p wipp) (40)
For the first term on the RHS in the above inequality, we have that
| w
3 (VG2(1)) VGs(a)) + prr)) - wio
-1|wx wf,pl1 - 23 VG2(())) pur; we wppp)
+ +V11(V)(( VGa( + pioll
(1 23p) - wT,pll w
+ 2B we wi,ps E. V + E E,,2E,,30,)
+ f loww + VF(z,) VF - = - VF(xz) E1,3W, + = =,,,5,,0,l1,,
(41)
where (i) follows from the non-expansiveness of projection and (ii) follows from properties of strong convexity and Cauchy-Schward have that for any 01 > 0,
inequality. Taking the conditional expectation of equation 41 we
E Bill [[||w[11
w7, 12 T]
8 (33)e²
",ip:: (Fxx) 6,,3 s -T]
2
+ 1[3, + (FF
(F(x)) E,, + ,,,, = 71
< (B(Baa1lluu -wu--10 - + V
+
E - E 2T, //1//1//////////////1 T)))
8
+ 21 10--231 28p)
+ 5.8
5, k5
5, KM
|| 1 P|7=10 77
+ = | 1|
5,8
|| || T]. |2
(42)
where the last inequality is due to that for S T. and for any i [K], we have that [[((()) s
M. Then for the second term on the RHS in eq.
(40) we have
Bl]
w = T| <
E 2 |2, Ie+1 11 T
E. T. 2 F (Jiz, 8c,1 )ure) 11 =T]
E L (M + || = TT].
(43)
where the first inequality is due to Lemma 3 where L.- = (pp-)) Then for the last term on the
RHS in eq. 44).. for any 02 > 0, az > O, we have that
E 2(we41 wi wi+l,p wi,p) |T = 7]
B B[2 222111111 -/ |Ill| /// "i ||| =
B 2/2 - well + ||: w (ll
wT, = T]
1
SE
azl aellwe+1 - wi
| - - + asllwss -wi,pll 2
| 11, =T
03
8
1
a I (M + ||,,, r)
02 [V
VGG( paeel
pmrel 1| +
as3
2 +
+
2
02
a3
<02 8² +
5
77
+ +5
-, || 1 TT)
1
1
8
E
a² 122 (M + ||,, w: 1) 7 T
as
(44)
02
03
30

---

Published as a conference paper at ICLR 2025
where (1) follows from the non-expansiveness of projection and equation 43 and the last inequality
from equation 42
Then substituting eq. (42) eq. (43) and eq. (44) into eq. (40), we have
|lllw[+1 - wi+1,p م
- 7]
8
<(1 23p-23p + Bai + 23
+ (5p² + 5K 5KM* (1 + 02)
33
+ M
+ 5.82 + +5,3aa2
Bl|| = T
33
+ M
+ 532 + 5,32 a2
Bills,,311 7
30
+ 5,3²
+ 53302 02
B|| 12 |211, /// = 77
01
+
1+ +
2 L (M + || T)
S(1 23p + Ba1 + 03) _
+ (5p² + 15KM + 02)
33
[KKo²
2K204
+ 2
+ +582 + +58 02
n2
4Ko²
+
1
a 2
2M
(45)
02
03
nhe
where the last inequality is due to that for any E [3],
E||| 77 s /Elller/PPIT 77 S /Bllle /B/1ee,,111/PP(T = S
2K
11
and
21
27 s V 2211l,.22/1111.0.00
= 7)
Blller22
= 7)
/2K22
n
6pe
According to equation 45 with a1 0.5p, d2
1,a3 0.53p, 3 S
B0(1+KMaT n2 2
max{ (o²2 o M² (6 208p) and a
p32p"r²
we have that
6
B[]lw++1 : w1 T| T -²²²
We then complete our induction and prove that for any < т, we have that E[ w wi
T < $e2
As result, we have that
E |10+1 w T
P (IWEl1 21 =1+1,p11>=? TT) where the first probability due to Markov inequality. Thus we have that
8
2
P (1 We+1 wi+2,p11 =e
> 1 (P7 T) PP (1we41 wi+1 1/ (T ((T=T)
> 1 5,
(46)
31

---

Published as a conference paper at ICLR 2025
where the last inequality is because parameters satisfy all the requirements in Theorem thus
P(r < T)
< 8 Then based on equation 39, by setting p = O(e"), we have that || V (zy July
2'
VF(x))uf
|I
O(e) with probability at least 6 for each iteration t, which completes the
proof.
32


Reviews:
[{"review_id": "1v9BtqICYy", "reviewer": "Reviewer_Wanu", "summary": "The authors analyze the problem of multi objective optimization (MOO), \n$$\\begin{align*}\nF^\\star = \\min_{x\\in \\mathbb{R}^d} F(x) = (f_1(x), f_2(x), \\ldots f_K(x))\n\\end{align*}\n$$\nwhere each $f_i:\\mathbb{R}^m \\to \\mathbb{R}$ when each $f_i$ has generalized $\\ell$-smoothness. Generalized $\\ell$-smoothness implies that $\\|\\nabla^2 f_i(x)\\| \\leq \\ell(\\|\\nabla f_i(x)\\|), \\forall x$ for a continuous non-decreasing positive function $\\ell$. This subsumes $(L_0, L_1)$-smoothness, where $\\ell(a) = L_0 + L_1 a$, (Zhang et al 2019) and standard $L$-smoothness, where $\\ell(a) = L$. Further,  NNs do not satisfy stronger notions of $L$-smoothness but satisfy generalized smoothness. \n\nThe goal of MOO is to obtain $\\epsilon$-accurate Pareto stationary point, defined as $\\min_{w\\in \\mathcal{W}} \\|\\nabla F(x) w\\|^2 \\leq \\epsilon^2$. This is referred to as $\\epsilon$-CA distance (Conflict avoidant).\n\nFirst, the authors analyze the existing MGDA algorithm in Algorithm 1 (Desideri 2012) and its stochastic variant in Algorithm 3, to obtain $\\epsilon$-CA distance on average. The required sample complexity for these cases is $\\mathcal{O}((\\alpha\\epsilon^2)^{-1}, (\\beta\\epsilon^2)^{-1})$(Theorem 1)  and $\\mathcal{O}((\\alpha \\epsilon^2)^{-1} + \\epsilon^{-4})$ (Theorem 2) respectively, which matches the sample complexity for single objective optimization under $L$-smoothness. Here, $\\alpha$ and $\\beta$ are step sizes to update  $w$ and $x$ in their algorithms.\n\nSecond, the authors consider a stronger metric, the per-iteration $\\epsilon$-level CA distance, defined as $\\|\\nabla F(x_t)w_t - \\nabla F(x_t) w_t^\\star\\| \\leq O(\\epsilon)$, where $x_t, w_t$ are iterates of the algorithm, and $w_t^\\star \\in \\arg\\min_{w\\in \\mathcal{W}} \\|\\nabla F(x_t) w\\|^2$. To achieve this metric, the authors propose using a  warm-start for $w$ in deterministic setting (Algorithm 1), and warmstart with increasing batch size for stochastic setting (Algorithm 3), yielding sample complexities of $\\mathcal{O}(\\epsilon^{-11})$ (Theorem 3) and $\\mathcal{O}(\\epsilon^{-17})$ (Theorem 6) respectively.  Further, the authors propose a zeroth-order method modificiation to warm-start deterministic MGDA in Algorithm 4, which uses only $O(1)$ space and time and achieves per-iteration $\\epsilon$-level CA distance with same sample complexity $\\mathcal{O}(\\epsilon^{-11})$.\n\nA key advantage of their analysis is removing the bounded gradient assumption required by all existing works and they require sufficient effort to show such a bound exists implicitly for their algorithms.\n\n\nFinally, on two multi-task learning datasets (Cityscapes and NYU-v2), their warm start method obtains best average performance across all tasks.\n\n\n**References** --\n- (Zhang et al 2019) Why gradient clipping accelerates training: A theoretical justification for adaptivity. Arxiv.\n- (Desideri 2012) Multiple-gradient descent algorithm (mgda) for multiobjective optimization. CRM.", "questions": "- **References for Optimal rates for deterministic variants of per-iteration CA distance** : Can the authors provide any references for deterministic iteration-level CA distance to compare Theorems 3 and 4. Further, can the authors compare the performance of their warm-start procedure to existing baselines? Do warm-start procedures achieve optimal sample complexity for these cases? It might be helpful to include the sample complexity results in Table 1 for a quick comparison to baselines.\n\n- **Independent samples for each $f_i$ for stochastic variants**: For \nstochastic variants (Line 387) at each iteration $t$, $F(x_t;s_{t,i})$ requires a different sample $s_{t,i,j}$ to evaluate $f_j$ for $j\\in [K]$. Is this necessary for the analysis? Does using the same sample for all $f_j$ change the analysis, as in practice, one might take a single minibatch to evaluate all $f_j$ at each iteration. Further, in Eq 16 and 17, using the same sample can remove the terms of $K$ from the union bound while still obtaining similar results.\n\n- **Stochastic MGDA-FA** : If there is a bound the variance of $F(x;s)$ for instance $\\mathbb{E}[\\|F(x;s) - F(x)\\|^2]\\leq \\sigma_F^2, \\forall x$ or for each function $f_j(x;s)$, then would it be possible to analyze a stochastic variant of MGDA-FA by combining the analysis of the deterministic MGDA-FA and stochastic MGDA? Are there any reasons why the authors believe this shouldn't be possible or straightforward?\n\n- **Warm-start procedure for general bi-level optimization**: MOO is bi-level optimization problem, where the inner optimization problem solves for best $w$ and the outer optimization solves for $x$. The warm-start procedure here implies that for single loop solutions to bilevel optimization, the inner problem is already very accurate, $\\mathcal{O}(\\epsilon)$ to be precise. This makes solving the bi-level optimization easier, as the inner problem is already almost solved.\nCan this technique be applied to ohter bi-level optimization problems, where a single warm-start conveniently solves the inner problem accurately? Or is this an artifact of the MOO problem's simple structure?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- **Presentation**: The paper is easy to follow, even for readers without expertise in MOO. The MOO problem under generalized smoothness, the MGDA algorithm, and the warm-start procedure are well-motivated. Further, the proof sketch also provides a good overview of key ideas, atleast for average CA distance.\n\n\n- **Novel algorithms**: A warm-start procedure appears in (Xiao et al 2023), however, it requires running two-loops, one of warm start of $w$ and other for $x$. In contrast, the proposed warm-start algorithm is run only once at initialization for $w$, and then the simple MGDA algorithm takes over. Even with this \"weaker\" warm-start, the authors can achieve stronger per-iteration $\\epsilon$-CA distance. Algorithm 4, MGDA-FA, seems novel, and utilizes zeroth-order optimization intelligently, without worsening theoretical guarantees in the deterministic case.\n\n\n- **Weak assumptions**: All existing works require $L$-smoothness and bounded gradients, while this paper requires only generalized smoothness. For their proofs, they show that gradients are indeed bounded by initial suboptimality, $\\max_{i\\in [K]} (f_i(x_0) - f_i^\\star)$ for MGDA updates in the deterministic case. In the stochastic case, their proof is more complicated, wherein they take  a union bound over all iterations until a stopping time to show that gradient noise is also bounded.\n\n\n- **Best sample complexity**: Even under weaker conditions, the obtained sample complexities for average CA distance, $\\mathcal{O}(\\epsilon^{-2})$ and $\\mathcal{O}(\\epsilon^{-4})$ for deterministic and stochastic cases respectively, match the lower bounds for single-objective optimization under $L$-smoothness. For iteration level CA distance, it seems that the best sample complexity of existing methods with stronger assumptions is $\\mathcal{O}(\\epsilon^{-12})$ while their analysis obtains $\\mathcal{O}(\\epsilon^{-17})$.", "weaknesses": "- **Theory**:\n    - **Definition of $\\mathcal{W}$:** The authors have not defined the set $\\mathcal{W}$, however across the proof(Line 809, Eq 11), they use $\\max_{w\\in \\mathcal{W}}\\|w\\| \\leq 1$. It seems to be the unit sphere in $K$ dimensions. \n    - **Choice of step size does not work in Theorem 2:** The parameters $\\alpha,\\beta,\\rho = \\mathcal{O}(\\epsilon^2)$ do not work out for Theorem 2 as each of $\\alpha, \\beta$ and $\\rho$ depend on other two. Consider $\\rho \\leq \\frac{1}{\\sqrt{\\alpha T}}$ in Theorem 2, which for $T = \\epsilon^{-4}$ and $\\alpha  = \\epsilon^{2}$ implies, $\\rho \\leq \\epsilon$. For $\\epsilon << 1$, $\\rho=\\epsilon^2$ does not satisfy this condition. Ideally, the authors should provide the condition for parameters in a sequential manner, for instance, $\\rho$ depends on $\\beta$ and $\\alpha$, $\\beta$ depends on $\\alpha$ not $\\rho$ and $\\alpha$ doesn't depend on either $\\beta$ or $\\rho$. This would ensure that such inconsistent parameter values do not arise. Also, I am no longer sure that $T = \\mathcal{O}(\\epsilon^{-4})$ can be obtained for choice of $\\alpha,\\beta,\\rho$ satisfying all constraints in Theorem 2. \n    - **Value of $M$:**  For the deterministic case (Theorems 1, 3, 4 and 5), the value of step sizes depend on $M$ defined in Line 357, which is a function of $\\ell$ and initial function suboptimality. Therefore, while the bounds in these theorems scale well with  $\\epsilon$, they might not do so with $M$. If the scaling with $M$ in these theorems matches that of single-objective generalized $\\ell$-smooth optimization from (Li et al 2024), or if is small under certain conditions on $\\ell$, then it should not be an issue.\n    - **Dependence on high probability error $\\delta$ in stochastic variants (Theorem 2 and 6):** The authors do not provide the dependence on the high probability error $\\delta$ in Theorems 2 and 6. For high probability guarantees, we would want to know if we can make $\\delta$ extremely small, for instance $\\mathcal{O}(\\epsilon)$, or if it works only for a constant $\\delta$. From Theorem 8, it seems that a constant $\\delta \\in (0,\\frac{1}{2})$ might work, but the authors should provide more details on this. The union bound  over all iterations should force $\\delta$ to not be very small.\n    \n    \n \n- **Poor empirical Performance of MGDA-FA**: While MGDA-FA achieves the same performance as warm-start MGDA theoretically(Theorems 3 and 4), it performs much worse in experiments (Table 4). Its performance is better than only $2$ of the $8$ baselines in Table 3, while warm-start MGDA outperforms all $8$ baselines. The authors do not discuss possible causes for this. Even though MGDA-FA is fast in practice, as its error is very large, its usefulness is limited.\n\n\n\n\n- **Typos**: $f_i^\\star$ in the definition of $\\Delta$ in Line 357 and \"optional stopping theorem\" in Line 407-408.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SyjPwgxkJ6", "reviewer": "Reviewer_YM5v", "summary": "This paper studies the multi-objective optimization (MOO) problem under generalized $ell$-smoothness, where $\\ell$ is a general non-decreasing function of gradient norm. The authors provide the first convergence analysis of multiple gradient descent algorithm (MGDA) (and its variant with fast approximation) under this setting, in terms of $\\epsilon$-Pareto stationarity and $\\epsilon$-level conflict-avoidant (CA) distance. The resulting complexities with respect to $\\epsilon$-Pareto stationarity and $\\epsilon$-level average CA distance match the best known results.", "questions": "- What is the meaning of minimizing a vector as in Eq. (1)? I suggest that the authors may make it clearer, in the context of multi-objectives.\n- Could the authors elaborate how they computed the local smoothness for Figure 1?\n- What is $f_*$ in the definition of $\\Delta$ in Line 357?\n- Take Theorem 1 as an example. Could the authors provide a more detailed discussion on the constants $c$, $F$ and $M$, like how tight they can be in some special case? I found the current convergence result is hard to parse.\n- Would generalized smoothness bring any benefits in practice, like providing guidance on how to choose the step sizes?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The analysis of MGDA under generalized smoothness is new. Their analysis further relax the assumptions such as bounded function values or bounded gradients assumed in prior work. \n- The authors use a general notion of generalized smoothness, i.e., in terms of a non-decreasing function $\\ell$ instead of the original one with $ell(a) = L_0 + L_1 a$.\n- The authors further study a variant of MGDA, which approximates the gradient in each iteration to save memory and time.", "weaknesses": "- The notation of this paper is a bit unclear. In multiple places, the authors introduce something before they define the notation, so the write-up should be refined. For example, the authors should define $\\mathcal{W}$ in Definition 3.\n- The preliminaries on generalized smoothness from Section 2.1 is redundant, as those are not proposed by this work and not the main contribution here. \n- All the complexity results of this paper are only stated in terms of $\\epsilon$. A more clear statements with dependencies on other problem parameters would be better.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EW632rxiNk", "reviewer": "Reviewer_Ksvn", "summary": "This paper offers a rigorous convergence analysis for both deterministic and stochastic variants of the Multiple Gradient Descent Algorithm (MGDA) under a generalized $\\ell$-smoothness assumption. The authors demonstrate that these methods converge to an $\\epsilon$-accurate Pareto stationary point while maintaining an $\\epsilon$-level average conflict-avoidant (CA) distance over all iterations. The sample complexity is shown to be $\\mathcal{O}(\\epsilon^{-2})$ in the deterministic setting and $\\mathcal{O}(\\epsilon^{-4})$ in the stochastic setting. Additionally, the authors introduce a warm start strategy to enable more precise control over iteration-wise CA distance. They also analyze MGDA-FA, a variant that reduces the computational complexity to $\\mathcal{O}(1)$ in both time and space, making it notably efficient.", "questions": "1. In lines 389 and 393, why are $i \\in [3]$ and $j \\in [3]$ specified? What is the rationale behind selecting only the first three sample collections?\n2. In Section 5.2, the analysis involves mini-batch algorithms, yet the effect of batch size on the results is not discussed. How would adjusting the batch size impact the findings?", "limitations": "", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The theoretical analysis is comprehensive and robust.\n2. The paper is clearly written and well-organized, making the concepts easy to follow.", "weaknesses": "1. Assumption 2, which posits that $\\phi(a) = \\frac{a^2}{2\\ell(2a)}$ is monotonically increasing, restricts $\\ell(a) \\leq \\mathcal{O}(a^2)$. This places a strict limitation on the class of generalized $\\ell$-smooth functions considered.\n2. The paper's novelty is somewhat limited. From an algorithmic standpoint, MGDA was introduced several years ago, and the fast approximation presented here constitutes a relatively minor modification.\n3. The novelty of the analytical techniques is also limited, as the approach used closely resembles that of [1].\n4. The experimental results would benefit from the addition of confidence intervals to clarify statistical significance, particularly given the small differences in performance observed.\n5. In the main theorems, the authors use big-O notation without specifying constants. Providing explicit constants would enhance clarity and interpretability.\n\n**Reference**:\n\n[1] Li, Haochuan, et al. \"Convex and non-convex optimization under generalized smoothness.\" Advances in Neural Information Processing Systems 36 (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TPWszq90nz", "reviewer": "Reviewer_moXU", "summary": "This paper investigates a broader class of generalized $\\ell$-smooth loss functions, where $\\ell$ is a non-decreasing function of the gradient norm. We analyze the multiple gradient descent algorithm (MGDA) and its stochastic variant for addressing generalized ℓ\\ellℓ-smooth multi-objective optimization (MOO) problems. Its comprehensive convergence analysis demonstrates that these algorithms converge to an $\\epsilon$-accurate Pareto stationary point, ensuring guaranteed average conflict-avoidant distances.", "questions": "For specific questions, please refer to the \"Weakness\" section.\nI would be willing to raise my score if these  questions concerned are well addressed.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1.Writing: This work is presented with good writing style, where the summarized problems with detailed explanations make it easy for readers to understand the problem addressed in this article. \n\n2.Novelty: The paper investigates a more general and realistic class of generalized $\\ell$-smooth loss functions, which has been rarely considered in previous work. Additionally, a warm start strategy is proposed in the algorithm design to initialize the parameter $\\omega$ for enhanced performance.\n\n3.Experiments: Several scenarios and recent baselines are considered, implying improvements in accuracy and robustness under various distributional shifts.", "weaknesses": "1.Unreliable theoretical analysis: The theoretical work in this paper appears to lack reliability. A simple review of the proofs in the appendix reveals that the proof of Corollary 1 is entirely incorrect. \n\nThe inequality\n$$\n\\left\\|\\nabla F\\left(x_t\\right) w_t-\\nabla F\\left(x_t\\right) w_t^*\\right\\|^2 \\leq\\left\\|\\nabla F\\left(x_t\\right) w_t\\right\\|^2-\\left\\|\\nabla F\\left(x_t\\right) w_t^*\\right\\|^2,\n$$ \ndoes not hold.\n\n2.Originality of the algorithm. Could you clarify the differences between the algorithm presented in this paper and MGDA [1]?  Could you elaborate on how the algorithm mentioned in this paper improves the performance of MGDA?\n\n[1]Jean-Antoine Désidéri. Multiple-gradient descent algorithm (mgda) for multiobjective optimization.  Comptes Rendus Mathematique, 350(5-6):313–318, 2012.\n\n3.Warm start. Can the warm start strategy be applied to other multi-objective optimization algorithms? Would incorporating this strategy significantly improve algorithm performance?\n\n4.Computational complexity. \nThe paper may not provide a comprehensive assessment of the computational efficiency and practicality of the proposed method in real-world applications. Like the computational complexity analysis or empirical time/memory cost.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)