Three-Way Trade-Off in Multi-Objective Learning: Optimization, Generalization and Conflict-Avoidance
Authors: Lisha Chen
Heshan Devaka Fernando
Yiming Ying
Tianyi Chen
Venue: NeurIPS 2023 poster (2023)
Keywords: Generalization
algorithm stability
multi-objective optimization
gradient conflict

Abstract: Multi-objective learning (MOL) often arises in emerging machine learning problems when multiple learning criteria or tasks need to be addressed.  Recent works have developed various _dynamic weighting_ algorithms for MOL, including MGDA and its variants, whose central idea is to find an update direction that _avoids conflicts_ among objectives. Albeit its appealing intuition, empirical studies show that dynamic weighting methods may not always outperform static alternatives. To bridge this gap between theory and practice, we focus on a new variant of stochastic MGDA - the Multi-objective gradient with Double sampling (MoDo) algorithm and study its generalization performance and the interplay with optimization through the lens of algorithm stability. We find that the rationale behind MGDA -- updating along conflict-avoidant direction - may \emph{impede} dynamic weighting algorithms from achieving the optimal ${\cal O}(1/\sqrt{n})$ population risk, where $n$ is the number of training samples. We further highlight the variability of dynamic weights and their impact on the three-way trade-off among optimization, generalization, and conflict avoidance that is unique in MOL. Code is available at https://github.com/heshandevaka/Trade-Off-MOL.

Three-Way Trade-Off in Multi-Objectivee Learning: Optimization, Generalization and Conflict-Avoidance
Lisha Chen'
Heshan Fernando
Rensselaer Polytechnic Institute Troy, NY. United States manml21@rpi... edu
Rensselaer Polytechnic Institute Troy, NY, United States fernahrrpi edu
Yiming Ying
Tianyi Chen
University of Sydney
Rensselaer Polytechnic Institute
Camperdown, Australia yiming. bingg..innnsse yingdsydney...ommmmo edu.. edu. au
Troy, NY, United States chentiany1190gma1. com
Abstract
Multi-objective learning (MOL) often arises emerging machine learning prob- lems when multiple learning criteria or tasks need to be addressed. Recent works have developed various dynamic weighting algorithms for MOI., including MGDA and its variants, whose central idea is to find an update direction that avoids con- flicts among objectives. Albeit its appealing intuition, empirical studies show that dynamic weighting methods may not always outperform static alternatives. To bridge this gap between theory and practice, we focus on new variant stochastic MGDA the Multi-objective gradient with Double sampling (MoDo) algorithm and study its generalization performance and the interplay with opti- mization through the lens of algorithm stability. We find that the rationale behind MGDA - updating along conffict-avoidant direction may impede dynamic weight- ing algorithms from achieving the optimal O /n) population risk, where is the number of training samples. We further highlight the variability of dy- namic weights and their impact the three-way trade-off among optimization, generalization, and conflict avoidance that is unique in MOL. Code is available https:///itthut www.meesanneeaaaaaa..oommmaaaaaa Traaeeaaaaaaeeeeaaaeeeeeeeeeeeee Soadde-Off--e -
Introduction
Multi-objective learning (MOL) emerges frequently in recent machine learning problems such as learning under fairness and safety constraints [49]; learning across multiple tasks, including multi-task learning [39] and meta-learning [47]; and, learning across multiple agents that may not share a global utility including federated learning [40] and multi-agent reinforcement learning [33].
This work considers solving the empirical version of MOL defined on the training dataset S = (21...., }. The performance of model z E Rd on datum 2 for the m-th objective is denoted Sa.m Rd + IR, and its performance
the entire training dataset S is measured by the m-th empirical objective fs.m (I) for m E [M]. MOL optimizes the vector-valuce objective, given by
min zERd
(s(x) = JsM, (x))
(1.1)
Equual contribution.
The work of L.. Chen, H. Fernando, and T. Chen supported by the National Science Foundation (NSF) McDL-SCALE project 2134168 and RPI-IBM Artificial Intelligence Research Collaboration (AIRC). The work of Ying was partially supported by NSF (DMS 21 10836, IIS-2103450, and IIS (1S-2110546).
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

X3
(a) Objective
(b) Objective 2
(c) MGDA
(d) Static
(c) MoDo (dynamic)
Figure 1: An example from [29] with two objectives (Ia and 1b) to show the three-way trade-off in MOL. Figures lc-le show the optimization trajectories, where the black marks initializations of the trajectories, colored from red (start) to yellow (end). The background solid/dotted contours display the landscape of the average empirical/pooplation objectives. The gray/green bar marks empirical/populatinn Pareto front, and the black w/green * marks solution to the average objectives.
One natural method for solving (1.1) is to optimize the (weighted) average of the multiple objectives. also known as static or unitary weighting [18, 45]. However, this method may face challenges due to potential conflicts among multiple objectives during the optimization process; e.g., conflicting gradient directions (V fs.m(z) fs, (z)) < O. A popular alternative is thus to dynamically weight gradients from different objectives to avoid conflicts and obtain a direction d(xx) that optimizes all objective functions jointly that we call a conflict-avoidan (CA) direction. Algorithms in this category include the multi- gulti--rradeet descent algorithm (MGDA) [9], its stochastic variants [30, 10, 52]. While the idea of finding CA direction in dynamic weighting-base based approaches is very appealing, recent empirical studies reveal that dynamic weighting methods may not outperform static weighting in some MOL benchmarks [18, 45], especially when it involves stochastic updates and deep models. Specifically, observed by [18], the vanilla stochastic MGDA can be under-optimized, leading to larger training errors than static weighting. The reason behind this training performance degradation has been studied in [52, 10], which suggest the vanilla stochastic MGDA has biased updates, and propose momentum-boe manneed methods to address this issue. Nevertheless, in [45], it is demonstrated that the training errors of MGDA and static weighting are similar, while their main difference lies in the generalization performance. Unfortunately, the reason behind this testing performance degradation is not fully understood and remains an open question.
To gain deeper understanding of the dynamic weighting-based algorithms, a natural question is Q1: What are the major sources of errors in dynamic weighting based MOL methods?
To answer this question theoretically, we first introduce proper measure of testing performance in MOL the Pareto stationary measure in terms the population objectives, which will immediately imply stronger measures such as Pareto optimality under strongly convex objectives. We then decompose this measure into generalization eтror and optimization error and further introduce a new metric on the distance to CA directions that is unique to MOL; see Sections 2.1 and 2.2.
To characterize the performance of MOL methods in unified manner, introduce generic dynamic weighting- MOL method that we term stochastic Multi-Objective gradient with DOuble sampling algorithm (MoDo), which uses step size ? control the change of dynamic weights. Roughly speaking, by controlling 7, MoDo approximates MGDA (large ?) and static weighting algorithm (7 0) as two special cases; see Section 2.3. We first analyze the generalization error of the model learned by MoDo through the lens of algorithmic stability [3, 14, 24] in the framework of statistical learning theory. To our best knowledge, this is the fist-ever--noww stability analysis for MOL algorithms. Here the key contributions lie in defining a new notion of stability MOL uniform stability and then establishing a tight upper bound (matching lower bound) on the MÖL uniform stability for MoDo algorithm that involves two coupled sequences; see Section 3.1. We then analyze the optimization error of MoDo and its distance CA directions, where the key contributions lie in relaxing the bounded function value/gradies assumptions and significantly improving the convergence rate of state-of-the-a dynamic weighting- -ased MOL methods [10]; see Section 3.2.
Different from the stability analysis for single-objective learning [14], the techniques used in our generalization and optimization analysis allow remove conflicting assumptions and use larger step sizes to ensure both small generalization and optimization errors, which are of independent interest.
Given the holistic analysis of dynamic weighting methods provided in Q1, follow-up question is Q2: What may cause the empirical performance degradation of dynamic weighting methods?

---

Optimization
Step sizes a &
lterations
Region
Opt.
Gen.
Conflict
& data size n
I
t
+
+
= w(a)
T d(n)
IV
III
II
+
t
+
w(a)
T = w(n)
II
C.A direction error
III
+
y = o(T
T = w(n)
IV
>
T O(m))
Generniization error
An illustration of three-way trade-off among optimization, generalization, and conflict avoidance in the strongly convex case; a is the step size for z, y is the step size for weights where o(-) denotes strictly slower growth rate, wo(-) denotes strictly faster growth rate, and ( denotes the same growth rate. Arrows and respectively represent diminishing in an optimal rate and growing in a fast rate w.r.t. n, while > represents diminishing w.r.t. n, but not in an optimal rate.
Figure 2:
Visualizing MOL solution concepts. To reason the root cause for this, we first compare different MOL algorithms a toy example shown in Figure 1. We find MGDA can navigate along CA directions and converge the empirical Pareto front under all initializations, while static weighting gets stuck in some initializations; at the same time, the empirical Pareto solution obtained by MGDA may incur larger population risk than the suboptimal empirical solution obtained by the static weighting method; finally, if the step size y of dynamic weights is carefully tuned, MoDo can converge along CA directions the empirical Pareto optimal solution that also generalizes well.
Aligned with this toy example, our theoretical results suggest a novel three-way trade-off in the performance of dynamic weighting-bee based MOL algorithm: see Section 3.3. Specifically, it suggests that the step size for dynamic weighting Y plays a central role in the trade-off among convergence to CA direction, convergence empirical Pareto stationarity, and generalization error; Figure 2. In this sense, MGDA has an edge in convergence to the CA direction but could sacrifice generalization; the static weighting method cannot converge to the CA direction but guarantees convergence to the empirical Pareto solutions and their generalization. Our analysis also suggests that MoDo achieves a small population risk under proper combination of step sizes and the number of iterations.
Problem Formulation and Target of Analysis
In this section, we first introduce the problem formulation of MOL, the target of analysis, the metric to measure its generalization, and then present the MGDA algorithm and its stochastic variant.
2.1 Preliminaries of MOL
Denote the vector-valued objective function on datum z as Fx)x [f). fa. The training and testing performance of can then be measured by the empirical objective Es(r) and the population objective F(z) which are, respectively, defined as Fs( = n E. Fz, (x) and
F(x) = E.nDDFFFFFFF. [.)]. Their corresponding gradients are denoted as Fs( and V (x)) E RdxM
Analogous to the stationary solution and optimal solution in single-objective learning, we define the Pareto stationary point and Pareto optimal solution for MOL problem min F(x) as follows.
rER"
Definition 1 (Pareto stationary and Pareto optimal). If there exists convex combination of the gradient vectors that equals to zero, i.e., there exists X E A such that F = O, then x E IRd Pareto stationary, If there no x E Rd and x + x" such that, for all m E [M] fm((x) S fm((a)) (2"), with fo (x) < fmr(2" for at least one m' E [M], then x" Pareto optimal. there is no x R such that for all m [M), fm(x)= < fm(x"), then x² is weakly Pareto optimal.
By definition, at Pareto stationary solution, there no common descent direction for all objectives. A necessary and sufficient condition for being Pareto stationary for smooth objectives is that minxAAM /V ) Al| = 0. Therefore, minxeAM [VF(() can be used as a measure of Pareto stationarity (PS) [9. 11, 42, 30, 10J. We will refer to the aforementioned quantity as the PS population risk henceforth and its empirical version as PS empirical risk or PS optimization error. We next introduce the target of our analysis based on the above definitions.
2.2 Target of analysis and error decomposition
In existing generalization analysis for MOI,, measures based on function values have been used to derive generalization guarantees in terms of Pareto optimality [7, 41]. However, for general
3

---

nonconvex smooth MOL problems, it can only be guaranteed for an algorithm to converge to Pareto stationarity of the empirical objective, i..., small A or [VF((z) not reasonable to measure population risk in terms of Pareto optimality in this case. Furthermore, when all the objectives are convex or strongly convex, Pareto stationarity is a sufficient condition for weak Pareto optimality or Pareto optimality, respectively, as stated in Proposition 1.
X|ll [9, 11, 30, 10). Thus, is
Proposition ([42, Lemma 2.2]). If fm (2) are convex or strongly-cowee for all m E [M], and I E Rd is a Pareto stationary point of F(x), then x is weakly Pareto optimal or Pareto optimal.
Next, we proceed to decompose the PS population risk.
Error Decomposition. Given a model z, the PS population risk can be decomposed into
min A
min
VP(x)AI - min [VF((T)aI+ M
+
min [VF((
(2.1)
AEAM
PS population risk Rpop (2))
PS generalization crror (2)
PS optimization eitor (ape(a)
where the optimization error quantifies the training performance, i.e., how well does model perform on the training data; and the generalization error (gap) quantifies the difference between the testing performance on new data sampled from DD and the training performance, i.e., how well the model performs on unseen testing data compared to the training data.
Let A z Rd denote randomized MOL algorithm. Given training data S, we are interested in the expected performance of the output model x = A(S), which is measured by EA,s[Bpop (APPp)((((()))))))))))))))))))) (A(S))). From (2.1) and linearity of expectation, it holds that
EA.s RAps (A(S)) = EA.s Rgen (A(S)) + EA,s Ropt (A(S)))
(2.2)
Distance to CA direction. As demonstrated in Figure 1, the key merit of dynamic weighting over static weighting algorithms lies in its ability navigate through conflicting gradients. Consider an update direction d = v (r) A where À is the dynamic weights from a simplex À E A A = {} e RM A = 1, 2 0). To obtain such a steepest CA direction in unconstrained learning that maximizes the minimum descent of all objectives, we can solve the following problem [11]
CA direction d(x) = arg min max dE3d mE[M] (V.sm(()).) d) + 2 l|ll2
(2.3a)
equivalent to d(x)) = (Fss s.t. X((x)) arg min ||VFs())\|] NEA
(2.3b)
Defining (x(x) = - (Fs( & E Rd and A E A we measure the distance to d(z) via [10]
CA direction error
Exa( = ||dx d(x))l².
(2.4)
With the above definitions of measures that quantify the performance of algorithms in different aspects, we then introduce a stochastic gradient algorithm for MOL that is analyzed in this work.
2.3 A stochastic algorithm for MOL
MGDA finds X (x)x in (2.3b) using the full-batch gradient V Fs(x), and then constructs d(x) = - (x) (x:). a CA direction for all empirical objectives fs (x). However, in practical statisti- cal learning settings, the full-batch gra-
Algorithm 1 Stochastic MGDA MoDo algorithm
1: input Training data S, initial model za. weighting co- efficient Ay and their learning rates {T frlt 2: for t = O,..., T
1 do
3: for objective m = 1,..., M do Independent gradients [mm,,, (mx), [3]
dient (I)(x) may be costly to obtain,
4:
and thus one may resort a stochas-
5:
end for
tic estimate of v Fs(x)) instead. The di- rect stochastic counterpart of MGDA, re- ferred to as the stochastic multi- gradient algorithm [30], replaces the full-batch gradients V Vss (x) in (2.3b) with their
6: Compute dynamic weight A++1 following (2.5a)
7: Update model parameter 2441 following (2.5b)
8: end for
9: output
stochastic approximations V.z.(2)) for z E S. which, however, introduces a biased stochastic estimate of \o+1, thus biased CA direction; see [10, Section 2.3].

---

Table Comparison of optimization error, generalization error, and population risk under different assumptions for static and dynamic weighting, Use "NC", "SC" to represent nonconvex and strongly convex, and "Lip-C", "S" represent Lipschitz continuous and smooth, respectively.
Assumption
Method
Optimization
Generalization
Risk
CA Distance
NC. Lip-C. S
Static
(aT) : +
T T 7
n 8
x
Dynamic
(aT) 2 + +
7 t
(7T) -1 + a +7
Static
(a1))++a) +
7
n $
x
SC,
n 2 7 O(T
Dynamic
(aT) 3 + +
n
(7T) + a +7
T 2, O.W.
n
To provide a tight analysis, we introduce simple yet theoretically grounded stochastic variant of MGDA stochastic Multi-Objective gradient with DOuble sampling algorithm (MoDo). MoDo obtains an unbiased stochastic estimate of the gradient of problem (2.3b) through double (in-
dependent) sampling and iteratively updates X, because 1 |V (x+) V (2)) =
Fx4) (F)()))) At each iteration t, denote 24,s an independent sample from S with [3].
and V Fz,,, (xr) as a stochastic estimate of FFs())). MoDo updates x, and de as
Aet1 IT ar (Ae 72 V (1+) V (1t)A))
(2.5a)
2++1 Z₁ ag F. (z)))
(2.5b)
where 04, 't are step sizes, and IT (.) denotes Euclidean projection to the simplex A We have summarized the MoDo algorithm Algorithm and will focus on MoDo in the subsequent analysis.
3 Optimization, Generalization and Three-Way Trade-Off
This section presents the theoretical analysis of the PS population risk associated with the MoDo algorithm, where the analysis of generalization error is in Section 3. and that of optimization error is in Section 3.2. A summary of our main results is given in Table
3.1 Multi-objective generalization and uniform stability
We first bound the expected PS generalization error by the generalization in gradients in Proposition 2, then introduce the MOL uniform stability and establish its connection to the generalization in gradients. Finally, bound the MOL uniform stability.
Proposition 2. With || || denoting the Frobenious norm, Rgen(A(S)) (A(S)) in (2.2) can be bounded by
EAS Rgen (A(S)) < EA,s E [IFFF((()))))))))))))))()))))))) (Fs(A()))
(3.1)
With Proposition 2, next introduce the concept of MOL uniform stability tailored for MOL problems and show that PS generalization error MOL can be bounded by the MOL uniform stability. Then we analyze their bound in general nonconvex case and strongly convex case, respectively.
Definition 2 (MOL uniform stability). A randomized algorithm A 2 + Rd, is MOL-uniformly stable with ep for all neighboring datasets S, S' that differ at most one sample, we have
sup EA (FF S c.
(3.2)
Next show the relation between the upper bound of PS generalization error in (3.1) and MOL uniform stability in Proposition 3.
Proposition 3 (MOL uniform stability and generalization). Assume for any 2, the function F3 (x) is differentiable. If randomized algorithu A -" + Rd is MOL-uniformlyy stable with cp, then
EA - VFs(A(()) ||] < 4EF VE
(3.3)
where the variance is defined as V.. E.-D -.-D| (...
5

---

Proposition 3 establishes connection between the upper bound of the PS generalization error and the MOL uniform stability, where the former can be bounded above by the latter plus the variance of the stochastic gradient over the population data distribution. It is worth noting that the standard arguments of bounding the generalization error measured in function values by the uniform stability measured in function values [14, Theorem 2.2] is not applicable here as the summation and norm operators are not exchangeable. More explanations are given in the proof in Appendix B.I.
Theorem 1 (PS generalization enror of MoDo in nonconvex case). If sus EA G² for any then the MOL. uniform stability, i.e,, & in Definition 2 is bounded by of 4G²T) / n. And the PS generalization error (ann (A(S)) - O(Tin $).
<
Compared to the function value uniform stability upper bound in [14, Theorem 3.12] for nonconvex
single-objective learning, Theorem does not require a step size decay a₁ = (1/t), thus can enjoy at least a polynomial convergence rate of optimization errors w.r.t. T. Combining Theorem I with Proposition 3, to ensure the generalization error is diminishing with n. one needs to choose = = o(n), which lies in the "early stopping" regime and results in potentially large optimization error. We then provide a tighter bound in the strongly convex case that allows larger choice of T. Below we list the standard assumptions used to derive the introduced MOL stability.
Assumption 1 (Lipschitz continuity of Fz))), For all
[M], V.z.m(()) is f, contimuous for all z. And V F (z) is -lipsscch continuous in Frobenius norm for all z.
Assumption 2. For all m E [M]. 2, fz.m (x) is j-sttrongyy convex w.r.t. F, with μa > O.
Note that in the strongly convex case, the gradient norm (FF can be unbounded in IR.. Therefore, one cannot assume Lipschitz continuity of f2,0 (xx w.r.. E Rd. We address this challenge by showing that { generated by the MoDo algorithm is bounded as stated in Lemma 1. Notably, combining with Assumption I, we can derive that the gradient norm || IVF= (x:))ll is also bounded, which serves as a stepping stone to derive the MOL stability bound.
Lemma (Boundedness of z; for strongly convex and smooth objectives). Suppose Assumptions I, 2 hold. For {at}, E (T) generated by MoDo algorithm or other dynamic weighting algorithm with weight X E A M ssep size a4 = a, and S a S fT there exists a finite positive constant e₂ such that | Cz- And there exists finite positive constants & Cy VM such that for all X A.M.
we have V (ll) S &t,, and FVF( Ey.-
With Lemma 1, the stability bound and PS generalization is provided below.
Theorem (PS generalization error of MoDo strongly convex case). Suppose Assumptions I.
2 hold. Let A be the MoDo algorithm (Algorithm 1). For the MOL uniform stability cr of
algorithm in Definition 2, if the step sizes satisfy 0 < a: S a S 1/(2lça). and 0 < Ttt S 7 S
minf 120076 8(387+22 +2,,,) //TT then it holds that
2²
GG (a um
48
12 + 4MC,
10MEY P
and [A Rgen = O 5). (3.4)
um
And there exist functions Fx) that satisfy Assumptions 1. 2, neighboring datasets S. S' that differ in at most one sample, and MoDo algorithm with step sizes 0 < a; S a S 1/(2l,,),, and
0 < 7t S
min{ 12007 21,))-20,11 3/T such that
n²
1
Mp²
EA [IVEL(((()) - VFL(A(S)) >
(3.5)
256n
Theorem 2 provides both upper and lower bounds for the MOL uniform stability. In this case, we choose a = ( +), = o(T-1), and T (n²2) to minimize the PS population risk upper bound, as detailed in Section 3.3. With this choice, the MOL. uniform stability upper bound matches the lower bound in an order of n2 suggesting that our bound tight. The generalization error bound in (3.4) is direct implication from the MOL uniform stability bound in (3.4), Propositions 2, and 3.

---

It states that the PS generalization error of MoDo is O(n=a), é), which matches the generalization error of static weighting up constant coefficient [22]. Our result also indicates that when all the objectives are strongly convex, choosing small step sizes a and can benefit the generalization error.
3.2 Multi-objective optimization error
In this section, we bound the multi multi-objective PS optimization error M [ 19, 30, 10). As discussed in Section 2.2, this measure being zero implies the model x achieves a Pareto stationarity for the empirical problem.
Below we list an additional standard assumption used to derive the optimization error.
Assumption 3 (Lipschitz continuity (z))). For all m E [M]] fz)m(z) are & L--iiscchitz continuous for all z. Then (x) are Ly-Lisschitz continuous in Frobenius norm for all with E = MMy.
Lemma 2 (Distance to CA direction). Suppose either: 1) Assumptions 1, 3 hold; or 2) Assumptions 1. 2 hold, with E and E defined in Lemma 1. For {21}, {Ne} generated by MoDo, holds that
T
4 (All)d,,(x)) d(x,))) < 7T T
+ +6 Me M + +
(3.6)
Lemma 2 analyzes convergence to the CA direction using the measure introduced in Section 2.2. By, e.g., choosing (T- and 7 O(T- the RHS of (3.6) converges in a rate of O $)
Theorem 3 (PS optimization error of MoDo). Suppose either: 1) Assumptions 1, 3 hold; or, 2) Assumptions 1, hold, with & defined in Lemma 1. Define oF such that (A(Fs(a)))M) min EA (F) I cp. Considering {zı} generated by MoDo (Algorithm 1), with a: = S (1) ?t- 7, then under either condition or 2), holds that
BA
min M
[VFs(M))\|]
s
CF + aT
22
3
M + V Valnnll.
(3.7)
The choice of step sizes (T and y= = ( to ensure convergence to CA direction is suboptimal for the convergence to Pareto stationarity (see Theorem 3), exhibiting trade-off between convergence to the CA direction and convergence to Pareto stationarity; see discussion in Section 3.3.
3.3 Optimization, generalization and conflict avoidance trade-off
Combining the results Sections 3.1 and 3.2, we are ready to analyze and summarize the three-way trade-off of MoDo in MOL. With A,( = 2z denoting the output of algorithm A at the t-th iteration, we can decompose the PS population risk (A, as (cf. (2.1) and (3.1))
( [IFF(A(()) (Fs()(
EA.S Rpop (Ar())) S EA,
min [VFF(A + TEAS AEAM
The general nonconvex Theorem 1, and the optimization error bound in Theorem 3, the PS population risk of the output of MoDo can be bounded by
Suppose Assumptions 1, hold. By the generalization error in
Σ EAS RRoo (Ar(S))) = -a-
1 a + + Tán
(3.8)
T
Discussion of trade-off. Choosing step sizes 1)) -( and number of steps = @(n²), then the expected PS population risk is O(n b which matches the PS population risk upper bound of general nonconvex single objective in [22]. A clear trade-off in this case is between the optimization error and generalization error, controlled by T. Indeed, increasing leads to smaller optimization errors but larger generalization errors, and vice versa. To satisfy convergence to CA
7

---

direction, it requires = wo(a) based on Lemma 2, and the optimization error in turn becomes worse, so does the PS population risk. Specifically, choosing leads to the expected PS population risk in Onn +b and the distance to CA direction in On tb). This shows another trade-off between conflict avoidance and optimization error.
1) (TT and T = (n
The strongly convex case. Suppose Assumptions I, 2 hold. By the generalization error and the optimization error given in Theorems 2 and 3, MoDo's PS population risk can be bounded by
T-1 Σ T 1=0
EA.s (aao[pooppAASS)) = o (a tT + at + 73 + +n
(3.9)
o(T-1), -)((-)) and number of steps = O(2)) we have the expected PS population risk in gradients is O(n However, choosing 7 =o(T-1) leads to large distance to the CA direction according to Lemma 2 because the term 77 in (3.6) increases with T. To ensure convergence to the CA direction, it requires 7 = (T under which the tighter bound in Theorem 2 does not hold but the bound in Theorem 1 still holds. In this case, the PS population risk under proper choices of a, 7, I' is O(n- as discussed in the previous paragraph. Therefore, to avoid conflict of gradients, one needs to sacrifice the sample complexity of PS population risk, demonstrating a trade-off between conflict avoidance and PS population risk.
Discussion of trade-off. Choosing step sizes a = O(T-
4 Related Works and Our Technical Contributions
Multi-task learning (MTL). MTL. as one application of MOL., leverages shared information among different tasks to train a model that can perform multiple tasks. MTL has been widely applied to natural language processing, computer vision, and robotics [15, 38, 50, 43]. From the optimization perspective, a simple method for MTL is to take the weighted average of the per-task losses as the objective. However, studied in [16], the static weighting method is not able to find all the Pareto optimal models in general. Alternatively, the weights can be updated dynamically during optimization, and the weights for different tasks can be chosen based on different criteria such as uncertainty [17], gradient norms [6], or task difficulty [13]. These methods are often heuristic and designed for specific applications. Another line of work tackles MTL through MOL [39, 48, 29, 12]. A foundational algorithm in this regard is MGDA [9], which takes dynamic weighting of gradients to obtain a CA direction for all objectives. Stochastic versions of MGDA have been proposed in [30, 52, 10]. Besides finding one single model, algorithms for finding a set of Pareto optimal models rather than one have been proposed in [28, 35, 31, 20, 46, 51, 32, 27, 34].
Theory of MOL. Optimization convergence analysis for the deterministic MGDA algorithm has been provided in [1]] Later on, stochastic variants of MGDA were introduced [30, 52, 10]. However,
the vanilla stochastic MGDA introduces biased estimates of the dynamic weight, resulting in biased
estimates of the CA directions during optimization. To address this, Liu et al. [30] proposed to
increase the batch size during optimization, Zhou et al. [52] and Fernando et al. [10] proposed to use momentum- based bias reduction techniques. Compared to these works on the optimization analysis, we have improved the assumptions and/or the final convergence rate of the PS optimization error. A detailed comparison is summarized in Table 2. While the community has rich history of investigating the optimization of MOL algorithms, their generalization guarantee remains unexplored until recently. In [7]. min-max formulation to solve the MOL problem is analyzed, where the weights are chosen based on the maximum function values, rather than the CA direction. More recently, [41] provides generalization guarantees for MOL. for more general class of weighting. These two works analyze generalization based on the Rademacher complexity of the hypothesis class, with generalization bound independent of the training process. Different from these works, we use algorithm stability to derive the first aggoritmm-dependee the effect of the training dynamics. In contrast previous MOL theoretical works that focus solely on either optimization [10, 52] or generalization [7,41] we propose a holistic framework to analyze three types of errors, namely, optimization, generalization, and CA distance in MOL with an instantiation of the MoDo algorithm. This allows us to study the impact of the hyperparameters on the theoretical testing performance, and their optimal values to achieve the best trade-off among the errors. Our theory and algorithm design can also be applied to algorithms such as PCGrad [48], CAGrad [29], and GradNorm [6]. Specifically, for example, the implementation of CAGrad takes iterative updates of the dynamic weight using single stochastic estimate, resulting in biased estimate of the update
generalization error bounds, highlighting
8

---

Table 2: Comparison with prior stochastic MOL algorithms in terms of assumptions and the guarantees of the three errors, where logarithmic dependence is omitted, and Opt., CA dist., and Gen. are short for optimization error, CA distance, and generalization error, respectively.
Batch size
Lipschitz X (x)
Bounded function
CA dist.
Algorithm
NC
Opt.
Gen.
SMG [30, Thm 5.3]
(1)
x
X
T
CR-MOGM [52, Thm 3]
(1)
/
X
V
T
MoCo [10, Thm 2]
(1))
/
X
X
T
20
T
MoCo [10, Thm 4]
(1))
/
X
v
T
O(1)
MoDo (Ours, Thms 1,2,3)
((1)
/
X
X
T
O(1)
T
MoDo (Ours, Thms 1,2,3)
O(1)
/ X
X T
T
direction, thus no guarantee of convergence for the stochastic algorithm. This issue can addressed by the double sampling technique introduced in this paper. In addition, our analysis techniques have been applied to improve the analysis of convergence rates for other algorithms [44, 5].
Algorithm stability and generalization. Stability analysis dates back to the work [8] in 1970s. Uniform stability and its relationship with generalization were studied in [3] for the exact minimizer of the ERM problem with strongly convex objectives. The work [14] pioneered the stability analysis for stochastic gradient descent (SGD) algorithms with convex and smooth objectives. The results were extended and refined in [19] with data-dependent bounds, in [4, 37, 23] for non-convex objectives, and in [1. 24] for SGD with non-smooth and convex losses. However, all these studies mainly focus on single-objective learning problems. To our best knowledge, there is no existing work on the stability and generalization analysis for multi-objective learning problems and our results on its stability and generalization are the prrst-vver-noww ones.
Challenges and contributions. Our contributions are highly non-trivial as summarized below. The definition of PS testing risk in gradient (2.1) is unique in MOL, and overcomes the unnecessarily small step sizes usually brought by the classical function value-based risk analysis. Specifically, prior stability analysis in function values for single objective learning [14] requires 1/t step size decay in the nonconvex case, otherwise, the generalization error bound will depend exponentially on the number of iterations. However such step sizes lead to very slow convergence of the optimization error. This addressed by the definitions of gradient-based measures and sampling-deterinee MOL algorithms, which yield stability bounds in OTT/n) without any step size decay. See Theorem 1. The stability of the dynamic weighting algorithm in the strongly convex (SC) case is non- con-trivial compared to single objective learning [14] because it involves two coupled sequences during the update. As a result, the classical contraction property for the update function of the model parameters that are often used to derive stability does not hold. This is addressed by controlling the change of X by the step size y, and using mathematical induction to derive a tighter bound. See Appendix B.4.
In the SC case with unbounded domain, the function is not Lipschitz or the gradients unbounded, which violates the commonly used bounded gradient assumption for proving the stability and optimization error. We relax this assumption by proving that the iterates generated by dynamic weighting algorithms in the SC case are bounded on the optimization trajectory Lemma 1.
5 Experiments
In this section, we conduct experiments further demonstrate the three-way trade-off among the optimization, generalization, and conflict avoidance of the MoDo algorithm. An average of 10 random seeds with 0.5 standard deviation is reported if not otherwise specified.
5.1 Synthetic experiments
Our theory in the SC case first verified through a synthetic experiment; see the details in Ap- pendix D.1. Figure 3a shows the PS optimization error and PS population risk, as well as the distance to CA direction, decreases as T increases, which corroborates Lemma 2, and Theorem 3. addition, the generalization error, in this case, does not vary much with T, verifying Theorems 2. In Figure 3b, the optimization error first decreases and then increases as a increases, which consistent with Theorem 3. Notably, we observe a threshold for below which the distance to the CA direction converges even when the optimization error does not converge, while beyond which the distance to the CA direction becomes larger, verifying Lemma 2. Additionally, Figure 3c demonstrates that

---

Esross
Ecrure
Erons
[log scale)
(log scale) (b) Different step size a.
(2og scale)
(a) Number of iterations T.
(c) Different step size
Figure 3: Optimization, generalization, and CA direction errors of MoDo the strongly convex case
under different T, T,a,7 y. The default parameters are T = 100, 0.01, = 0.001.
235
Ram
Etrors
107
10
16
16
15"
(log acale)
scale)
[Jog scale)
(a) Number iterations
(b) Different step size a
(c) Different step size Y
Figure 4: Optimization, generalization, and CA direction errors of MoDo for MNIST image classifi- cation under different T, a, and The default parameters are 7' 1000, = 0.1, and 7 0.01.
increasing enlarges the PS optimization error, PS generalization error, and thus the PS population risk, but decreases the distance to CA direction, which supports Lemma 2.
5.2 Image classification experiments
We further verify theory in the NC case MNIST image classification [21] using multi-layer perceptron and three objectives: cross-entropy, mean squared error (MSE), and Huber loss. Following Section 2.2, we evaluate the performance in terms of Rpop (z), Ropt(x), (2),
(z). and (x, A). The exact PS population risk Rpop(2) (2) is not accessible without the true data distribution. To estimate the PS population risk, we evaluate min I/V (z) on the testing data set Ste that is independent of training data set S. The PS optimization error (op(()) is obtained by minxEA V (1) and the PS generalization error Rgen(1) (x) is estimated by minxEAM |/ Fs, (z:) (x))
We examine the impact of differ- ent T, a, Y the errors in Fig- ure 4. Figure 4a shows that in-
Table 3: Classification results on Office 31 dataset.
Amazon
DSLR
Webcam
Method
A,% 4
creasing 7' reduces optimization error and CA direction distance but increases generalization ror, aligning with Theorems 1, 2, and 3. Figure 4b shows that in- creasing a leads to an initial de- crease and subsequent inerease in PS optimization error and population risk. which aligns with Theorem 3 and (3.8). On the other hand, there is an overall increase in CA direction distance with a, which aligns with Theorem Figure 4c shows that increasing y increases both the PS population and optimization errors but decreases CA direction distance. This matches our bounds for PS optimization error in Theorem PS population risk in (3.8), and CA direction distance in Theorem 2.
Test Acc 1
Test Acc
Test Acc t
Static
84.62 +: 0.71 94.43 1 0.96 97.44 1. 1.20 2.56 1: 0.37 79.45 0.11 96.56 + 1.20 97.89 + 0.74 3.65 0.64
MGDA
MoDo 85.13 0.58 95.41 0.98 96.78 + 0.65 2.26 0.31
6 Conclusions
This work studies the three-way trade-off in MOL among optimization, generalization, and conflict avoidance. Our results show that, in the general nonconvex setting, the traditional trade-off between optimization and generalization depending on the number of iterations also exists in MOL. Moreover, dynamic weighting algorithms like MoDo introduce a new dimension of trade-off terms of conflict avoidance compared to static weighting. We demonstrate that this three-way trade-off can be controlled by the step size for updating the dynamic weighting parameter and the number iterations. Proper choice of these parameters can lead to decent performance all three metrics.
10

---

Broader impacts and limitations
This work has potential impact on designing dynamic weighting algorithms and choosing hyper- parameters such as step sizes and number of iterations based on the trade-off for MTL applications such as multi-language translation, and multi-agent reinforcement learning. No ethical concerns arise from this work. A limitation of this study is that the theory focuses on a specific algorithm, MoDo, for smooth objectives in unconstrained learning. Future research could explore the theory of other algorithms for non-smooth objectives constrained learning, which would be interesting directions to pursue.
References
[1] Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. In Proc. Advances in Neural Information Processing Systems, volume 33, virtual, 2020.
[2] Amir Beck and Mare Teboulle. Gradient-based algorithms with applications signal-recovery problems. In Comvex Optimization in Signal Processing and Communications, 2010.
[3] Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of Machine Learning Research, 2:499-526, March 2002.
[4] Zachary Charles and Dimitris Papailiopoulos. Stability and generalization of learning algorithms that converge to global optima. In Proc. International Conference on Machine Learning, pages 744-753, Stockholm, Sweden, 2018
[5] Lisha Chen, Heshan Fernando, Yiming Ying, and Tianyi Chen. Three-way trade-off in multi-objective learning: Optimization, generalization and conffict-avoidance. arXiv preprint arXiv:2305.20007 2023.
[6] Zhao Chen, Vijay Badrinarayanan, Chen-Y Yu Lee, and Andrew Rabinovich. Gradnorm: Gradient normalization for adaptive loss balancing in deep multitask networks. In Proc. International Conference on Machine Learning. virtual, July 2018.
[7] Corinna Cortes, Mehryar Mohri, Javier Gonzalvo, and Dmitry Storcheus. Agnostic learning with multiple objectives. In Proc. Advances in Neural Information Processing Systems, volume 33, pages 20485-20495, virtual, 2020.
[8] Luc Devroye and Terry Wagner. Distribution-free performance bounds for potential function rules. IEEE Transactions Information Thheory, 25(5):601-604 1979.
[9] Jean-Antoine Désidéri. Multiple-gradient Descent Algorithm (MGDA) for Multi-objective Optimization. Comptes Rendus Mathematique, 350(5-6), 2012.
[10] Heshan Fernando, Han Shen, Miao Liu, Subhajit Chaudhury, Keerthiram Murugesan, and Tianyi Chen. Mitigating gradient bias in multi-objective learning: A provably convergent stochastic approach. In Proc. International Conference on Learning Representations, Kigali, Rwanda, 2023.
[11] Jörg Fliege, A Ismael F Vaz, and Luís Nunes Vicente. Complexity of Gradient Descent for Multi-objective Optimization. Optimization Methods and Software, (4(5))94999955 2019.
[12] Xiang Gu, Xi Yu, Jian Sun, Zongben Xu, et al. Adversarial reweighting for partial domain adaptation. In Proc. Advances in Neural Information Processing Systems, virtual, December 2021.
[13) Michelle Guo, Albert Haque, De-An Huang, Serena Yeung, and Li Fei-Fei. Dynamic task prioritization for multitask learning. Proceedings of the European conference on computer vision, Munich, Germany, July 2018.
[14] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In Proc. International Conference on Machine Learning, pages 2234-123, New York City, NY, 2016.

---

[15] Kazuma Hashimoto, Caiming Xiong, Yoshimasa Tsuruoka, and Richard Socher. A Joint Many- task Model: Growing a Neural Network for Multiple NLP Tasks. arXiv preprint: 1611.01587. 2016.
[16] Yuzheng Hu, Ruicheng Xian, Qilong Wu, Qiuling Fan, Lang Yin, and Han Zhao. Revisiting scalarization in multi-task learning: A theoretical perspective. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, 2023.
[17] A Kendall, Y Gal, and R Cipolla. Multi-task learning using uncertainty to weigh losses for scene geometry and semanties. arXiv preprimt: 07111,, 2017.
[18] Vitaly Kurin, Alessandro De Palma, llya Kostrikov, Shimon Whiteson, and Pawan K Mudigonda. In defense of the unitary scalarization for deep multi-task learning. In Proc. Advances in Neural Information Processing Systems, volume 35. pages 12169-12183, New Orleans, LA, 2022.
[19] Ulja Kuzborskij and Christoph Lampert. Data-dependent stability of stochastic gradient descent. In Proc. International Conference on Machine Learning, pages 281 1-22444, Stockholm, Sweden, 2018.
[20] Panagiotis Kyriakis, Jyotirmoy Deshmukh, and Paul Bogdan. Pareto policy adaptation. In Proc. International Conference on Learning Representations, virtual, 2021.
[21] Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mnistl, 1998.
[22] Yunwen Lei. Stability and generalization of stochastic optimization with nonconvex and nonsmooth problems. In Proc. Annual Conference on Learning Theory, Bangalore, India, July 2023.
[23] Yunwen Lei, Rong Jin, and Yiming Ying. Stability and generalization analysis of gradient methods for shallow neural networks. In Pruc. Advances in Neural Information Processing Systems, New Orleans, LA, 2022.
[24] Yunwen Lei and Yiming Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In Proc. International Conference on Machine Learning, pages 5809-5819, virtual, 2020.
[25] Baijiong Lin, Ye Feiyang, Yu Zhang, and Ivor Tsang. Reasonable effectiveness of random weighting: A litmus test for multi-task learning. Transactions on Machine Learning Research, 2022.
[26] Baijiong Lin and Yu Zhang. LibMTL: A python library for multi-task learning. arXiv preprint arXiv:2203.14338 2022.
[27] Xi Lin, Zhiyuan Yang, and Qingfu Zhang. Pareto set learning for neural multi-objective combinatorial optimization. arXiv preprint arXiv:2203. 15386, 2022.
[28] Xi Lin, Hui-Ling Zhen, Zhenhua Li, Qing-Fu Zhang, and Sam Kwong. Pareto multi-task learning. In Proc. Advances in Neural Information Processing Systems, Vancouver, Canada, December 2019.
[29] Bo Liu, Xingchao Liu, Xiaojie Jin, Peter Stone, and Qiang Liu. Conflict-Averse Gradient Descent for Multi-task Learning. In Proc. Advances in Neural Information Processing Systems, virtual, December 2021.
[30] Suyun Liu and Luis Nunes Vicente. The Stochastic Multi-gradient Algorithm for Multi-objective Optimization and its Application to Supervised Machine Learning. Annals of Operations Research, pages 1-30, 2021.
[31] Xingchao Liu, Xin Tong, and Qiang Liu. Profiling Pareto Front With Multi-Objective Stein Variational Gradient Descent. In Proc. Advances in Neural Information Processing Systems, virtual, December 2021.
[32] Debabrata Mahapatra and Vaibhav Rajan, Exact pareto optimal search for multi-task learning: Touring the pareto front. arXiv preprin::108.005597 2021.
12

---

[33] Kristof Van Moffaert and Ann Nowé. Multi Multi--bjecctive reinforcement learning using sets of pareto dominating policies. Journal of Machine Learning Research, 15(107)3363--369, 2014.
[34] Michinari Momma, Chaosheng Dong, and Jia Liu. A mulli-obijecivv/mutt-tasss learning framework induced by pareto stationarity. In Proc. International Conference on Machine Learning, pages 15895-15907, Baltimore, MD, 2022.
[35] Aviv Navon, Aviv Shamsian, Ethan Fetaya, and Gal Chechik. Learning the pareto front with hypernetworks. In Proc. International Conference on Leurning Representations, virtual, April 2020.
[36] Yurii Nesterov. Introductory Lectures on Convex Optimization: Basic Course. Springer Publishing Company, Incorporated, 1 edition, 2014.
[37] Dominic Richards and Ilja Kuzborskij. Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel. In Proc. Advances in Neural Information Processing Systems, volume 34, virtual, 2021.
[38] Sebastian Ruder. An overview of multi-task learning in deep neural networks. preprint: 1706.05096, 2017.
arXiv
[39] Ozan Sener and Vladlen Koltun. Multi-task learning multi-objective optimization. In Proc. Advances in Neural Information Processing Systems, Montreal, Canada, December 2018.
[40] Virginia Smith, Chao-Kat Kai Chiang, Maziar Sanjabi, and Ameet S Talwalkar Federated multi-task learning. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Proc. Advances in Neural Information Processing Systems, volume 30, Long Beach, CA, 2017.
[41] Peter Súkeník and Christoph H Lampert. Generalization in multi-objective machine learning. arXiv preprint arXiv:2208. / 33499, 2022.
[42] Hiroki Tanabe, Ellen H. Fukuda, and Nobuo Yamashita. Proximal gradient methods for multi- objective optimization and their applications. Computational Optimization and Applications, 72(2):339-361, 2019.
[43] Simon Vandenhende, Stamatios Georgoulis, Wouter Van Gansbeke, Marc Proesmans, Dengxin Dai, and Lue Van Gool. Multi-task learning for dense prediction tasks: A survey. IEEE Trans Pattern Anal. Machine Intell., 2021.
[44] Peiyao Xiao, Hao Ban, and Kaiyi Ji. Direction-oriented multi-objectivv learning: Simple and provable stochastic algorithms. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, 2023.
[45] Derrick Xin, Behrooz Ghorbani, Justin Gilmer, Ankush Garg, and Orhan Firat. Do current multi-task optimization methods in deep learning even help? In Proc. Advances in Neural Information Processing Systems, volume 35, pages 13597-13609, New Orleans, LA, 2022.
[46] Yijun Yang, Jing Jiang, Tianyi Zhou, Jie Ma, and Yuhui Shi. Pareto policy pool for model-based offline reinforcement learning. In Proc. International Conference on Learning Representations, virtual, 2021.
[47] Feiyang Ye, Baijiong Lin, Zhixiong Yue, Pengxin Guo, Qiao Xiao, and Yu Zhang. Multi- objective meta learning. In Proc. Advances in Neural Information Processing Systems, vol- ume 34, pages 21338-2133 virtual, 2021.
[48] Tianhe Yu, Saurabh Kumar, Abhishek Gupta, Sergey Levine, Karol Hausman, and Chelsea Finn. Gradient surgery for multi-task learning. In Proc. Advances in Neural Information Processing Systems, virtual, December 2020.
[49] Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna P Gummadi. Fairness constraints: Mechanisms for fair classification. In Proc. International Conference on Artificial Intelligence and Statistics, pages 962-970, Fort Lauderdale, FL, 2017.
13

---

[50] Yu Zhang and Qiang Yang. A survey on multi-task learning. IEEE Trans. Knowledge Data Eng.. 2021.
[51] Yiyang Zhao, Linnan Wang, Kevin Yang, Tianjun Zhang, Tian Guo, and Yuandong Tian. Multi-objective optimization by learning space partitions. arXiv preprint arXiv:2110.03173, 2021.
[52] Shiji Zhou, Wenpeng Zhang, Jiyan Jiang, Wenliang Zhong, Jinjie Gu, and Wenwu Zhu. On the convergence of stochastic multi-objective gradient manipulation and beyond. In Proc. Advances in Neural Information Processing Systems, volume 35, pages 38103-381 15, New Orleans, LA, December 2022.
14

---

Appendix for "Three-Way Trade-Off in Multi-Objective Learning: Optimization, Generalization and Conflict-Avoidance "
Table of Contents
A Notations
15
B Bounding the generalization error
16
B.I Proof Propositions 2-3
16
B.2 Proof of Theorem
generalization error nonconvex case
18
B.3 Proof of Lemma Boundedness of z; in strongly convex case
19
B.4 Proof of Theorem 2 PS generalization error in strongly convex case
23
C Bounding the optimization error
36
C.I Auxiliary lemmas
36
C.2 Proof of Lemma Distance CA direction
38
C.3 Proof of Theorem PS optimization error
40
D Additional experiments and implementation details
43
D.1 Synthetic experiments
43
D.2 Multi-task supervised learning experiments
45
A
Notations
summary of notations used in this work is listed in Table for ease of reference.
Table 4: Notations and their descriptions.
Notations
Descriptions
Rd Z
Model parameter, or decision variable
Data point for training testing Dataset that S {z1..... 2..
S n
scalar-valued objective function evaluated on data point z,
fa,m(x). fs.m
with fa.m R + R.
dataset S, fs.m. with fs.m 18 ExesSem(t)
fm(())
A vealur-valued population objective function, (x) = (e)m Gradient (z). with V. IRd Rd
(.)(())
vector-valued objective function evaluated on data point z.
F.(z), Fs(x)
with F. B >> A
dataset S, with F3 = J E.ES Fs(x)
F(x)
A vector-valued population objective, F(w) = (x))
VF(x)
Gradient F(x), with VF(#) Rd /- R
XEAM
Weighting parameter an (M 1)-simplex
Aa(x) E A
CA weight, optimal solution to (2.3), when p = 0, simplified as X (T(x)
1 R
All-one vector with dimension M
Step update model parameter æ
Step size update weight
In the proof, we use denote the spectral norm, and - ||p to denote the Frobenius norm.
15

---

B Bounding the generalization error
B.1 Proof of Propositions 2-3
In this subsection, we prove Propositions 2-3, which establishes the relation between PS generalization error and MOL uniform stability.
Proof of Proposition 2.
For a given model x holds that
Rgen (2)
min XEA M
[ min A
[
max - -|VF((>)\]
max - [VVFs()))] AEA
AEA
IA3 WV
max (IIVF (VFs
max (I((F((2) - (=s(<))A[])
AEAM
ΛEAM
max (l)) (=s(+)|+[|AI & VV
V FFs(()))
(B.1)
ΛEAM
where (a) follows from the subadditivity of max operator, (b) follows from triangle inequality, (c)
follows from Cauchy-Schwards inequality.
Setting A(S), and taking expectation over S, on both sides of the above inequality, we have
A.s Reen (A(S)) S EA.slIVF(((SS) - (Fs(A()))
(B.2)
Proof of Proposition 3. The proof extends that of [22] for single objective learning to our MOL setting. Recall that S -(2,,.., Zn), which are drawn i.i.d. from the data distribution D. Define the perturbed dataset 5(() = {=1,..... ,..,.., =n sampled i.i.d. from D with 2 independent of æj. for all i,j E [n). Let E be an independent sample of 2j, 2j. for all j E [n]) and from the same distribution D. We first decompose the difference of population gradient and empirical gradient on the algorithm output (V (((S)) Fs (F)))) as follows using the gradient on (SS))). Since holds that n(VF(A(S)) VFF((AS)) nÊ, -
E: (AF)() = (F)(
-
=n VF VF, + a
+E (A(S -E -
E.S. (P:(A(()) VP:(A(S
Σ [E -F
(((S)
Eg
VF F., )) -VF,,
(B.3)
1=1 where the last equality follows from rearranging and that 2,, 2/. 2 are mutually independent. Applying triangle inequality to (B.3), it then follows that
n| n||VF(A(S)) - VFs(A &
E. I
- VE
Ci(S)
E. VF. (A(S))l
(B.4)
Note S and ( differ by single sample. By Definition 2, the MOL uniform stability Ep, and Jensen's inequality, we further get
nE - S 2nEF + E Σ {(()))
(B.5)
16

---

We then proceed to bound E Ei=1 (a(
which satisfies
2
E Σ 5
E Σ (S)
Σ E [I)
E
E((((()),
J2
(B.6)
For J1 according to the definition of (S) in (B.3) and Jensen inequality, it holds that
J1 = =
E
3 E. - V (A
3 E
-V
( E [
(B.7) where (a) follows from Jensen's 's inequality. (b) follows from the symmetry between 2; and 2/. To bound J2, with * j. further introduce 5" =
E (V
* which are drawn i.id. from the data
distribution D. Then for each i, [n]] with * j, introduce Sj neighboring dataset of S by replacing its 2j with zy. and 5 as a neighboring dataset of ( by replacing its 2j with zj. i.e.,
S {.1,..., 22-11 24,
2n).
(B.8a)
5/ {.1...., 2-11 24, 2441 1............................... 2z- 23 2g+1 mn
(B.8b)
Then the idea is to bound J2,s, using the newly introduced neighboring datasets Sj and 5 so as to connect to the definition of the stability 6p. We first show that TE E,
E ((E((S) (5) (S.))) because for i *
[ 0, (((((S)).,,()) o, (((,(())),,(S)) @ 0. (B.9)
E (S),
For + j. (c) follows from E (S,), {,)),,, = E.,, ((((S)) = (())))) R., [s((S))) 0,
(B.
where the second identity holds since {:(5)) is independent of zj and the last identity follows from E2g [E, (S)] 0 due to the symmetry between ă and 24, and their independence with s derived as
E,, [s() = E2, B (VF
V F2, (A(S())) = 0, Vi [n).
(B.11)
In similar way, for i + j. (d) and (e) follow from
E (() = EE,, (((()) = - (5, 0, ((E) EE,, ((,, E (s),, (((,)) O.
(B.12)
(B.13)
Based (B.9), for # have
J2 = (S), E, (5)) = E (,S))), -
<E (1(E(S) - ((S))) (15((1))-((((66 [+())
- - 1E [IL((S) &(S)))
+ + [ -
(B.14)
where we have used ab 5 / (u² + 1? According to the definition of E((S) and & (S,) we know the following identity for i +
E [|((()) {S)))
=E E (VE (Fs((( [)]
+ E. VP,, -VF,(()))))) 21
(B.15)
17

---

It then follows from the inequality (a (a+ 2 (a² + b²) and the Jensen's inequality that
(A(S))) (V
(B.16)
Since St0), - and st), s(zi) are two pairs of neighboring datasets, it follows from the definition of stability that
E - (.S,
< 4e and E [I,)(S) - (S.)) 4e Vi +
(B.17)
We can plug the above inequalities back into (B.14) and bound J2, by
J2, E (E) (S)) S 4ef-
Vi Vi
(B.18)
Combining the bound for J1,; in (B.7) and J2 in (B.18) and substituting them back into (B.6), then follows that
Σ ((S) 1=1
= E
+
Σ
(((()()),
S nE (V=( + 4m(n - 404mmmmm66
(B.19)
Plugging the above inequality back into (B.5), using subadditivity of the square root function, we get
nB BF(())(((S)) - VFs( < 4ncp V
(B.20)
The proof is complete.
B.2 Proof of Theorem 1- PS generalization error nonconvex case
In this subsection, we prove Theorem 1, which establishes the PS generalization error of MoDo in the nonconvex case.
Organization of proof. To prove the PS generalization error of MoDo, first define the concept of cumpling-determineee algorithms Definition 3. This concept has been defined [22] for the analysis in single-objective learning. Then show that MoDo is samplin--determing in Proposition 4. Finally, combining Propositions 2-4, we can prove Theorem 1, the MOL uniform stability and PS generalization error of MoDo.
Definition 3 -Sampling-determmneed algorithm [22]). Let A be randomized algorithm that randomly chooses an index sequence I(A) = { to compute stochastic gradients. We say a symmetric algorithm A is sampling determindd if the output model is fully determined by {2 : E I(A)}.
Proposition 4 (MoDo is sampling determined). MoDo (Algorithm 1) is sampling determined. In other words, Let T(A) = {it) be the sequence of index chosen by these algorithms from training
set S = {2 2n), and 2, ii.d. P for all e [n] build stochastic gradients, the output A(S) is determined by {zz j E [(A)). To be precise, A(S) is independent of 2, if & I(A).
Proof of Proposition 4. Let [(A) (41.... ..... 4, {dr, 13 and i E [n] for all 1 < And SHA) = }. By the description in Algorithm 1, A(S) = Ge,, o .... Gzt, (ID). where G-(+) is the stochastic update function of the model parameter given random sample 2. Therefore, for all possible sample realization 2, have
P(A(S) 2 2, $ I ((A)) =P(G o... G (zo) 2j =2, $ ((A)) Gz,, (zo) 1 T(A))
-P(G= =P(A(S)
$ 1 (AA)
(B.21)
where the last equality holds because 2, & ST(A). and 2, is independent of all elements in ST(A) by Li.d. sampling. Therefore, A(S) is independent of zj if & I(A). The proof is complete. D
18

---

Note that, besides MoDo, other popular stochastic randomized MTL algorithms such as SMG [30] and MoCo [10] are also cumpling-determingg Therefore, the result also applicable to these algorithms.
Lemma 3 ([22, Theorem 5 (b)]). Let A be a and S,S' be neighboring datasets with n data points that differ only in the i-th data point. If sup, EA [[[ ([ (A(S)) i [[A)] I G2 for any S. then
random algorithm (Definition 3)
sup
VFL(A(S)))I) S 4G P(i))(A))
(B.22)
Proof of Theorem 1. From Proposition 4, algorithm A, MoDo is on Lemma 3, its MOL uniform stability in Definition can be bounded by
Then based
& S 4G P(i E ((A)}.
(B.23)
Let de be the index the sample selected by A at the t-th step, and i* be the index of the data point that is different in S and S". Then
T-1
T
P(i" E(A))) < Σ
(B.24)
0=
Combining (B.23) and (B.24) gives
c S 4G2
(B.25)
Then based on Propositions 2-3, we have
EAS Rgen (A(5))]=BA.s ltt.s..sllVVV..... [[([((((())))))))))) VFs(A(())
by Proposition 2 by Proposition by (B.25)
<4ep + vn EEs (V>=D(VV((((())
=0(T
The proof is complete.
B.3
Proof of Lemma Boundedness of xe in strongly convex case
Technical challenges. In this work, focus on analyzing stochastic MGDA-based MOL algo- rithms in the unconstrained setting. This is because the constrained setting, MGDA with projected gradient descent on æ has no guarantee to find the CA direction, and a new algorithm needs to be developed to achieve this [42]. However, a fundamental challenge in the unconstrained strongly convex setting is that strongly convex function is Lipschitz continuous on Rdd. We overcome this challenge by showing that {xx Yz=1 generated by the MoDo algorithm is bounded on the trajectory. so the gradient of PS optimization and generalization errors without the Lipschitz continuity assumption for strongly convex objectives.
(xx) for all m [M], and z Z. Thereby, we can derive the upper bound
Organization of proof. Without loss of generality, we assume inf fm.:(z) < oo for all m E [M] and 2 E Z in the strongly convex case. In Lemma 4, we show that the optimal solution of F. (z) given any stochastic sample 2 E Z. and weighting parameter À E M is bounded. In Lemma 5, we show that if the argument parameter is bounded, then the updated parameter by MoDo at each iteration is also bounded by exploiting the co-coereiveness strongly convex and smooth objectives. Finally, based on Lemma 4 and Lemma 5, we first prove in Corollary 4 that with bounded initialization zg, the model parameter {-,) generated by MoDo algorithm is bounded on the trajectory. Then based on Lemma 6, by the Lipschitz smoothness assumption of fam (2), we immediately have that [/ is bounded for E { generated by MoDo algorithm, which completes the proof of Lemma Lemma paves the way for deriving the MOL uniform stability and PS generalization error of MoDo in the strongly convex and unconstrained setting.
19

---

Lemma 4. Suppose Assumptions 1, 2 hold. WLOG, assume enR fm,a(a) < oc for all m [M] and & E Z. For any given X E A", and stochastic sample 2 E 2, define Tx arg min F=(x)), then geR Fz(z) 3o and ||2,, oc, i.e. there exist finite positive constants cp- and ca- such that
inf F=(2)A S cp- and | S cz- =ER4
(B.26)
Proof. Under Assumption 2, for all m [M]] f (x) is strongly convex w.r.t. æ, thus has a unique minimizer. Define the minimizer Tm.= arg mRn (2)= Since a strongly convex function is coercive, infz (x) < co, i.e., (m. < oc, implies that ||= co.
By Assumption 1, the -Lipschit smoothness of fm,e(1), for x such that |>||| < 00
fx,2(x)= Smm,a + ( (2,,)), -..0--mm Fm + E || ml
2
112 | x 11 < 20.
Sfma +
(B.27)
Since Fz(2)) is convex w.r.t v, for all X E AM, with X [A....., Aas T, we have
M F.
M
M
M
Σ -
x
Σ
1
Σ
Σ
f
D)m < 80.
(B.28)
M m==1
M
M
m=1
m m'=1
Therefore, for all X E M we have
M
inf P.(OAAS F2
Σ m=1
L d < co.
(B.29)
ZERd
M
Since Fe(r) is strongly convex, thus is coercive, we have || < oc, which proves the result. D
Lemma 5. Suppose Assumptions hold, and define n. 36 3.2/1 2 3. For any given X A A and a stochastic sample Z, define x²,; arg min, Fz(z)). Then by Lemma 4, there exists positive finite constant Cx,1 2 C.- such that || 11 S Cx. S Cr Recall the multi-objective gradient update is
Gx = I &VV22x))
(B.30)
with step size 0 a f.). Defining C, = (1 + v2k) Co,1, d. we have that
if |||||| Cr22, then [[)x, Cx22-
(B.31)
Proof. We divide the proof into two cases: 1) when ||ق||| < Cr,1i and, 2) when Cr,1 S |||||| S ca,2-
1) For the first case, ||ا|||| < Cx,1 S C2,2, then we have
[x)xl < G x. (z) - x x=1 + ||
(0) GGx (x) (x,=(=*)) I| ||01|| S | x111 ||**||
<||>|| + 2||2" < 3c,,1 I (1 (1+ vo)c,,1 $ (1 v2k) S C222
(B.32)
where (a) follows from VF, (x*) A = 0, and (b) follows from the non-expansiveness of the gradient update for strongly convex and smooth function.
2) For the second case, 1 < ||||||| < Cs.2, we first consider a - Let μ² = n/3. Note that since (z(r) is y-strongly convex, it is also μl pl-strongly convex. By strong convexity and smoothness of Fx(x)) X, the gradients are co-coercive [36, Theorem 2.1. i.e., for any x we have
|VF
# x x 11
(VE,())))T<>> - -x²)
(B.33)
1
+ K
20

---

Rearranging and applying Cauchy-Schwartz inequality, we have
(VF,( 2 (z))()))) x² + V + 1/1 - 12
1
1t
- [V + (
1/ -0=1-0111
(B.34)
1
1
By the definition of (3))
[VF - 2 (VFL())A) I. (B.35)
[G),
VFL(
-|0||12+ + f
Substituting (B.34) into (B.35) yields
1 (F>
1'1 -'1 x01
[G),
|0:1|
Cr, (+)
2
E911
1 16
f.1
+ f
Cr.1
(F))
1- Ι
[F)
1
1 x x²1²²)
21
1 R
1 K-
2
pl 1'1x=="" x
< <|>/1 +
sup
Cx.1
)7
(B.36)
28
1 1+
1+K
tER
Since 2 3, thus 1-x- > O. then 7n is quadratic function w.r.t. and is strictly concave, thus I+A-T
can be bounded above by
1
1 1- k
1
sup Ca,
)
(B.37)
FER
2.
1
Substituting this back into (B.36) gives that
2
1+*"
( $||0||
||00 x=" 112)
f
2
1 1 1-
+ R-
=||0||
+ xx
2
1+
1
- 2
K
||0 x x²112
x-1
k-
+ x-
<||0:|1
2
(1|x]| - ||x0 11)
2,,
x-1
+ k
| + 26 k - (||=|| 1x
(B.38)
where the last inequality follows from 2 3, thus
= I-X-T 2, -2 ItK 1, and |x=1| <
Cz,1 I ||>|| by assumption.
For Cr.1 S ||ar||| S Cz.2, Iz a strictly convex quadratic function || which achieves its maximum at ||<:|| = C,,1 or ||=||| Cz,2. Therefore,
|[Gx, (x) < m3x 2 + 2c2, -x (c.22))-)
-c,,1)
(c) max 11 (222 < 2
(d)
(B.39)
where (c) follows from the definition that C22 (1 C2,1 (d) follows from 2 3, and thus 302 (1+ 22x)222 22
We have proved the case for a = f71 The result for < a < f11 follows by observing that,
||Gx,
=||x a (z)A
=1|(1 at -1
- + [ Co.2-
(B.40)
The proof is complete.
21

---

Lemma 6. Suppose Assumptions 1, 2 hold. For all X E AM and 2 E S, define xx,s arg aig (x)x),, then there exist finite positive constants cp- and ez- such that F F= ) cF- and || I Ce., And for E R& such that ||||| is bounded, i.e., there exists a finite positive constant Oz such that ||>||| S Ca. then
and F((D) Ln (cx + Cz- cp..
[VF2(+)\] S lea + cxr)
(B.41)
Proof. Under Assumptions 1, 2, by Lemma 4, there exist finite positive constants and such that F, (xx,,) I CF- and ||=x,= S Cz-
By Assumption the f.1 Lipschitz continuity of the gradient (Fs(x)), have
[FF( = VIF (1
5111111 - sg. + ||=x,=1)) s Enu(cz cxr)
(B.42)
where the first equality the fact that (
For the function value, by Assumption 1, the ff.i-Lipschizz smoothness of F=(x)A, we have
( ) xx,x) f1 || xx,el 12
Fe(x)A SF. (1 )
L1111
sF.(
| - x1,2
2
f1 (cz + Cz.)²
Sep. +
(B.43)
2
from which the proof is complete.
Corollary 4 (x, bounded on the MoDo trajectory). Suppose Assumptions 1, hold. Define k 34 u and xx, arg ming F& (z)) with X E A Then there exists finite positive constant Cæ- such that |, Cz-. Choose the initial iterate to be bounded, i.e.. there exists a finite positive constant Czg such that ||æro|| S Cao- then for (xt) generated by MoDo algorithm with a₁ and 0 F.1 we have
[selll S Cas with Cx max((1 V2x)cc*,, Cxp
(B.44)
Proof of Corollary 4. Under Assumptions 1, 2, by Lemma 4, || < 00, i.e. there exists a finite positive constant cz. such that || $ cx. Let c2 max + (2x)-'cea Cx and
Ca.2 = (1 + 22k)c,,1 = max (1 + v /2kx } in Lemma 5. We then consider the following two cases:
1) If (1 + Cx S Cag- then ||xx_|1 Cx
Cr. < (1 + 22)))1caa Then satisfies the condition in < Cz.2. Applying Lemma yields | S Cr.--
Lemma 5 that | 11 S Ca,1 and ||
2) If (1 C2 Crp then |
< Cro < (1 22kcc=.. Then it satisfies the condition in
Lemma 5 that |
S Ca.1 and
[ol S Cz,2- Applying Lemma yields ||=||] S Ca.2-
Therefore, (B.44) holds for = 1. We then prove by induction that (B.44) also holds for t E [T]. Assume (B.44) holds
< A < T - i...
| S C2 = Cx.2
(B.45)
Then by Lemma 5, at 1,
| || |G (Ix)) S Cr.2.
(B.46)
Since ||l S Cx,2, for /. 0, .., 1, we have
|| || = || (2t) S Cr,2-
(B.47)
Therefore, by mathematical induction, ||,;|| S Cx,2 Ca, for all [T]. The proof is complete.
D
22

---

Proof of Lemma 1. By Corollary 4, for {zz} generated by MoDo algorithm with a2 and 0 S a S f.1' we have
|sell| S Cri with Or = max + 22k)22', Czo
(B.48)
According to Lemma 6, define Ey (e, + cz.), and &o = VMdy, then it holds for all À E A |VF(()))]] S Ey and |[VF(>))] S [VF s lr.
(B.49)
B.4 Proof of Theorem PS generalization error in strongly convex case
Technical challenges. One challenge that the strongly convex objectives are not Lipschitz con- tinuous for IR is addressed by Lemma Another challenge compared to static weighting or single-objective learning is that the MoDo algorithm involves the update of two coupled sequences { and {A+}. Consequently, the traditional standard argument that the SGD update for strongly convex objectives has the contraction property [14] does not necessarily hold in our case since the weighting parameter À is changing, as detailed Section B.4.1. Nevertheless, we manage derive tight stability bound when y = O(T '), as detailed in Section B.4.3.
Organization of proof. In Section B.4.1, we prove the properties of the MoDo update, including ex- pansiveness or non-expansiveness and boundedness. Building upon these properties, in Section B.4.3, we prove the upper bound of argument stability Theorem 5, and the upper bound of MOL uniform stability. To show the tightness of the upper bound, in Section B.4.4, Theorem 6, we derive matching lower bound of MOL uniform stability. Combining the upper bound Section B.4.3 and the lower bound in Section B.4.4 leads the results in Theorem 2, whose proof is in Section B.4.5.
B.4.1 Expansiveness and boundedness of MoDo update
In this section, we prove the properties of the update function of MoDo at each iteration, including boundedness and approximate expansiveness, which is then used to derive the algorithm stability. For 2, 22 E S, A A recall that the update functions MoDo is
Ga (A) 11 (A VVF. (x) (F)A
(x,=
a (VF()))
Lemma 7 (Boundedness of update function of MoDo). Let &g be a positive constant. If [ S & for all À E AM, 2 and x E (xt)T= Yea generated by the MoDo algorithm with step size On a, then Gx (x) is ( --bounded on the trajectory of MoDo, i.e.,
sup (E
[[xx,(()) - xl| S all-
(B.50)
Proof. For all x E (1o)T A AM and = E S, since [ S l,. we have
[[)x, x S SIaVF S aly
(B.51)
which proves the boundedness.
Lemma 8 (Properties of update function of MoDo in convex case). Suppose Assumptions 1,
hold. Let & be a positive constant. for all X, E AM 2 S, and {I:)T x' {x
generated by the MoDo algorithm on datasets and St, respectively, we have (x)(a))]] S Ef.
| F2 (x'')X1) S lf. and [[ < lr. [[VF.(x)) < fr. and step sizes of MoDo satisfy aa S V S 7, it holds that
[[Gx,<(=) - (x <(1 - 2ap 2a f,,)l1= 2'11
+ 22 1| x' /|| | X'I1 + 2a2 -
(B.52)
|G [Ga,,n.aa Gat (2) S ( + 1z2) 2 + (1+ +(1+1111
(1+7))00m1) 2
+ (11 l + (6,77) ||= x1112.
(B.53)
23

---

Proof. The squared norm of the difference of (x))( and (2') can be bounded by
|Gx,, (1) (x)2
1/2 z11? 20(x -
1/2 z²12 - -2(x L' -
(a)
(1) -V
+ 20 - x', (F2((') - -)) +2022///
(6)
2 (1 2ah + 2a e, f,1)1l= x²112 - 2a - /. (2' )(X a)) + 20 - 2112
(9)
< (1 2ah + 2a e (-,))l== x'12 20lf/1= x' |11 \ll + 20 2/11' - 2112 (B.54)
where (a) follows from rearranging and that || + 612 < 2||a|2 2116/2 (b) follows from the
j-strong convexity of P5 (x)),, L/.-Lipschitz continuity of V (z)),, and that (xx'll) S Ep for
x' E (2;))=1: and, (c) follows from Cauchy-Schwartz inequality.
And (122, an (l) can be bounded by
|G (A) Gr
| M (A- 7 (VF,, (x) VF,, (x)( (I
(4)
S | X' - (VP
(F (
5 A XII + - (z)) 107T::000---0111111111000010000-
S W
AA - + (1
VF, (VF
8 AA XII + -1 VF. (z))) (x)XII
+ (V=,
(1+ +
XIII + (c (, x'1l
(B.55)
where (d) follows from non-expansiveness of projection; (e) follows from triangle inequality. (f) follows from [=)] E for æ E {x1)]] (g) follows from triangle inequality; and (h) follows from f,, -Lisshhttt continuity of V (= &
- continuity of VF.(x), [V)x()) S &
for x E {=1]T=, and | [+)X| S f for x E (
Let fg,1 Eflr,1 + fr Taking square on both sides of (B.55) yields
||G |G (A) Gz
< ((11 + (7)l - XII + f1,171100110// ='1)²
=(1 + (11+6))110 1 - X1I2 + + + -II - -'11
x'11
-
<(1 1 XII2 (1 + X1112 ||2 - x2112) 12 12,172110 2212
= =(11 + +,) (1+ (7) 11A 2112 + (11 (11 ( ||0 1'1 (B.56)
The proof is complete.
B.4.2 Growth recursion
Lemma (Growth recursion with approximate expansiveness). Fix an arbitrary sequence of updates
G GI...., GT and another sequence G',..., G/y. Let zo = 1/ be a starting point in Ω and define
8, 1// - xx where Fe, d are defined recursively through
Z441 2+41= = G((xt), 2 (2, (t > 0).
24

---

Let Tt > 0.14 2 O, and 2 0. Then, for any > 0, and t E [T], we have the recurrence relation
(with 8n 0)
1):07 + Ut: + p) m + ve, 82) (1 4
G. G2 is (m, approxxiiilll expansive in square;
0++1 S
G. and G2 are se-bounded,
Ge is (mt, V4) apprrxxixiyy expansive in square.
Proof. When Ge and G2 are s--bounded, we can bound 81+1 by
8 = |,141 1 =[[G[(x)) - (z(2)]
-I)) It G2(()) + a/f + x ='/ll
<1(G)(1))= - xell [['((")) a''l || 2''ll
22a + dc.
(B.57)
Altematively, when G, and G² are & bounded, G₁ is (m, v1 approximaaly expansive, we have
o.+1 = | 4141 = -[Gr((z)) G((x))
= =[GG((++) G,(x() +
(x))( GG((()I|++ +1G())
Smd + + +[GG((/))) -
Smo + 4 |[G((z)) -x41l +111++ +[[ =
Sm. + 4 + 25c-
(B.58)
When G2 G₁ is (1) approxiatall expansive in square, given 5, 87 can be bounded by
8/41 ||+ u + 2| (G((z)) G((z))| S m||l; - x''1² + ut = no + ve.
(B.59)
When G2 and G², are ç q--bounded, applying (B.57), we can bound 8,4 by
6 S (8. + 25. < (1 p)d + 11 1/p)4<3
(B.60)
where > O and the last inequality follows from (a 6)2 v (1+ p)a² + (1 1/p)b².
Alternatively; when Ge and G², s--bounded, Gę (n, -pprroxxxii expansive in square, the following holds
6.t = | 2'41 (x;) - G1(21)11
=][G((=)) - G.(x)) + G.()
<(1+p)noo++u) [00/0//0===++++++/0////0++)))))1 -
G,(z)) +2/1
<(1 - +11 ([) 2/1
<(1 p) +4) +0)+ +1)
(B.61)
The proof is complete.
B.4.3 Upper bound of MOL uniform stability
In Theorem 5 we bound the argument stability, which is then used to derive the MOL uniform stability and PS generalization error in Theorem 2.
Theorem (Argument stability bound strongly convex case). Suppose Assumptions 1, hold. Let A be the MoDo algorithm in Algorithm I. Choose the step sizes Oi S S 2 //T. Then holds that
(/ and 7t S ming 120
d²
48 EA | A(()) - A(S')I
e3 um
(a
12 4MG 10Me
(B.62)
25

---

Proof of Theorem 5. Under Assumptions 1, 2. Lemma 1 implies that for {xz} generated by the MoDo algorithm, and for all X A AM, and for all m [M],
[ & f,,(cz + cxx))= l-. and (x.)((.)) & (F)]( & VME, = lp. (B.63)
For notation simplicity, denote ó, = ||,, -ill- 4. 1A - MII, -T = (S) and 24 = (S"). Denote the index of the different sample S and S' as i", and the set of indices selected at the t-th iteration as 4, i..., 4 = {ir,a)=11- When i* & L. for any c1 > 0, based on Lemma 8, we have
82 <11 - 20rp + +20, 20 + 20,lr015441 + 222
<(1 204f 2a )01 + a (900 + + (4 2a
<( 0411)66 ( + 7 (
+ 20
(B.64)
where the second last inequality is due to Young's inequality; the last inequality is due to choosing Ot S (2(7)))
When i E I, from Lemma 7, the (atly (oaef))-bbbee -boundeddesss of the update t-th iteration, and Lemma the growth recursion, for a given constant
O, we have
6 S (1 + p) + (1 + 1/p))a
(B.65)
Taking expectation of 6/41 over Lt we have
E,, 17,10111 SP(i" $ 4.) 11)(11 - am4)68 (1)1)) + axlresd (arlret + 2a7 (4+ 1 4il)
+P(i" E T.) (1) (1+ p) (1 1/p)Aa
arlu - PP( 11) pPili E 1.) o8
+ at (LECT + 20 R. S2 8" & IP(( & Tt) + (1+ ) eDAA
(B.66)
At each iteration of MoDo, we randomly select three independent samples (instead of one) from the training set S. Then the probability of selecting the different sample from S and S' at the t-th iteration, IP(i" E I,) in the above equation, can be computed as follows
3
Pi 4)) =
(B.67)
Consequently, the probability of selecting the same sample from S and 5' at the 1-th iteration is P(i* & 4e) = -P((" 4).
Let f..1 +ppkr, Recalling when i & Lt, G++1 S (1+ + 21e6g from Lemma it follows that
G S
<((1 (1 + (2)))) + (1 2.. ) + (z+ 22,7)))
<(1 (3 20 7x) 22 + 36 37,
(B.68)
where the last inequality follows from fg.17 I 1, and ls S And since &e and & are independent of T,, it follows that Eg,1 1" $ 4J < (1 + 36
(B.69)
Combining (B.66) and (B.69), we have E,, [521] <(1 or(u (Frr) $ [t) + pP(r E 1.) + (1+ 1 F(r e T.)40
+ +anc (1+ + 30 3l P(i & 1,)
(B.70)
26

---

-(m pF( E (1)) of + 0102(1 + cot & I + (1+ )) e E1)40e4
where we define 77c = 1 - arlu - fFc - 302kg,1 M))P(t $ It).
While when 1" E T, for given constant p2 > 0, we have
S++1 = م x (Ae When (h. (zx)) - (X - (24) ( (x)2((
~ X - (e() (z) (x)) - (122(14)MM1
<|> XaIl + 2nefls Se + Me:
C S(1 5(1+ p2) + +1+ Me
(B.71)
Taking expectation of 22+1 over 1e gives
Ey, 11 1E2, 1" E LI)((i" e 4)) + E1, | i" & LIP(ii 1.)
S + + 11+1/p2)1 1/ M P(i" E +i) + + P(i $ It)
<11+03 c37t + - p2) 23 + (1+ 1 ? n + 30 1
3
(B.72)
p2
Based on linearity of expectation and applying (B.72) recursively yields
E
Σ
(1+
1
3 )
+ 34 ,1168)))
II k=/1+1
(1 (1+
3 =,0
D2
n
f==0
1
+ 3l,, 11, (1 (1 + c37 + 3 t-t
(1 +
)472
M
PD2
P2
P=
(1+
8T
)47
MP
3
+ 30 116681)))))) (1+
1 1-1'
n
2T
Σ (1+
8T
1
3
+ 33 +66 c
n
n
(2)
22 Σ
(11 + n
8T J4, M n
+ 36 1(0g)
(B.73)
1'=0
where (a) follows from choosing ?o ' S 1/ T). P2 = n (b) follows from -' ST. and (1 + 1)T² I e", and the inequality (c) follows from ea < 2.
Note that & = 0, C = 0. Applying (B.66) at t = 0 gives
3 - + 1 4a22l
< n
p
which together with (B.72) gives
)4 M 3
E < 36
+ (1 36
P2
Therefore, for 0 < S 1, it satisfies that
B(5,] <
3 - (1
+ p
1 e + 24M
87 + +
(Σ
2 cpp
1
3p
P=0
9,
3 - (1 +
1
|4a² E3 + 20Mef02 (
87T 7)
am
Be-
(B.74)
p
n
27

---

Next, we will prove by induction that (B.74) also holds for t > 1.
Assuming that (B.74) holds for all S & S T 1, apply (B.70) to the case where = k to obtain
3p
+ +cn0 BiCHIP(C & It) + (1 1 p + 04.02
)) 40
-
13
+ n
B
(a)
I1k + 3p
El62]
127Me (1+
8T
+ 3 ) P(U & I1) + 3 3(1
+ 205027
Σ
1 p/
40
n
n
n
h
+ 3p)
8x + 1 + 6are2lg11
Σ
Be P(i" & 1i)
p=11
x
1
23 + 24ME302
SY +
a
(B.75)
where (a) follows from (B.73), and (b) follows from (B.74) for 0 S and that 7h ST S The coefficient J1 in (B.75) can be further bounded by
3p) )){
J1 = mh +
3. + +1 60402 9
P(' & I))
3p)
n m) }s 6arc2ly 1 BriPP(i I.)
(4)
3p) 1 anlu - (Fc]- - ( & 4.) +
8x +1
n
(2) (1
1
3p
oup +
B2 1
(B.76)
2
n
where (c) follows from 3, < Be+1, 7t S for all 1 = = 0...., T; (d) follows from the definition of mes (e) is because S (12/ gg 7), a S 1/(22),1) 1/((2)) and choosing Ca 11/44p leads to
(k + +17 Epcl + 3 g. 7 + 2 Stre: + +((Fc + 20 lg,
u 6(4 + 22) k+1
1
4²
1 <
T
120
2 H..
Combining (B.75) and (B.76) implies
0
S
(1-2
2 cxp + 3p)
1
) Be +1
(
3 [1 ! + 24M6722 (
33
8YF
+ 7) _
p
Ck++
3 (1 + 24n 24M0 2
8yT
+7)²
a
(B.77)
n
where the equality follows by the definition of B. given in (B.74). The above statements from
(B.75)-(B.77) show that if (B.74) holds for all t such that 0 < t < k < T - 1, it also holds for k=
Therefore, we can conclude that for T 2 0, it follows
3 (1
8YT - 20
E 1
SBT
+
-
n
p
n
n
(33 3 (1+ ) + 22
8-T
+7)
a
T-1
Σ
ap
+
3p T-k-1
n
p
n
n
n
k=
28

---

(1+
3 n
12 apn
STT ) + 24M2/02 + + n )
-1
[ (1-(1-
1 T
4 app
n
(B.78)
where the last equality follows from taking p / and compute the sum of geometric series. By plugging in c1
/1((4))) 02
Pxc + 20 C3 3fG + 26g,1, we have that
3
12
24 + 24M1 n2 24M0 a7) 1 Hom)-
E
- (1
aym
48
12
2M + 2M 2M4err))
/
a
+
1m
pm
"
48
/
(a
a
12 + 4M
+ 10Metr)
(B.79)
um
Jm
1
where the last inequality follows from C2 (4p + 2a) S 5M6H and c2 5l (Pfp"1/(BB3) /(3()) s 2p
B.4.4 Lower bound of MOL uniform stability
In this section, we construct Example I with lower bound of stability for the MoDo algorithm. Before proceeding to the example, we first define 1 as the all-one vector in R A {A R.
1 1}. and Pi = I - M _11, Then given any vector R.M II 3 (u) Piu + M 1.
Example 1. Recall that S {21, ..., 2j.... ... 2n S' {21. 22, ........ 24. 2...... 2n where S and S' differ only in the j-th data point. Define the m-th objective function as
1 x Ax bm
fa. (x)
(B.80)
2
where A is symmetric positive definite matrix, 16n > O is the smallest eigenvalue of A, and is the corresponding eigenvector of A. For the datasets S, and S' let z; = CcU, with Ezes [z] peu, [1,1 + v2] such
Eses' [z] p'v; u' 2j 2/} U, i.e., p μt h.- For simplicity, let M
that P.b = bp = 1- 22 /2 T, where bp is the eigenvector of P1 with eigenvalue 1.
Technical challenges. One challenge of deriving the lower bound lies in the projection operator when updating A. Unlike deriving the upper bound, where the projection operator can be handled by its non-expansive property, due to the nature of inequality constrained quadratic programming, neither a simple closed-form solution can be obtained, nor a non-trivial tight lower bound can be derived in general. We overcome this challenge by showing that when 7 = O(T-1), the Fuclidean projection onto the simplex is equivalent to a linear operator in Lemma 10. Another challenge compared to deriving the lower bound for single-objective learning is that the update of MoDo involves two coupled sequences, } and { The update of x, and z' involves different weighting parameters x and X. where {.r}. {>e} and {a/}, (X) are generated by the MoDo algorithm on neighboring training data S and S", respectively. We overcome this challenge by deriving a recursive relation of the vector [2, 2/; d X]] in Lemma 11.
Organization of proof. Lemma 10 proves that under proper choice of initialization of À and step size y, the projection of the updated À onto simplex A M is equal to the projection of that onto the set A : {> E R M 1 X 1). And thus the projection is equivalent to a linear transformation. Thanks to Lemma 10, we are able to derive a recursive relation the vector [z, - z/; X - X]] in Lemma 11. Finally, relying on the recursive relation, we derive a lower bound for the recursion of [TA ||= 2'll: E. - XiIl], depending on a 2 x 2 transition matrix. And based on its eigen decomposition, we could compute the --th power of such a transition matrix, which is used to derive the final lower bound of
- A(S')l I| in Theorem 6.
Lemma 10. Suppose Assumptions 1, 2 hold. For MoDo algorithm, choose Ao = _े 1, Y S 2MTEFEj and define
x = = - FVFF (xx) T (F)
(B.81)
29

---

then the update of for MoDo algorithm is A+t1 I (2,).
Define the set A M = {A E TRM 1 = 13, Pi = - 1 M 11,, Ar. = T
P1 + M.
Then for O,.... ...
holds that
Aet1 = P1 (A- VV- (21) VF ( (1))2e)) + 1 - P1 + 1.
(B.82)
M
M
Proof. By the update of )e we have
|| - Axll = |[| Ax - -V- (It) TV 22 - Xell
- ~ - 7V (II) F (21) - dell
S VF (1t) V 2 S &prll
(B.83)
where the last inequality follows from Lemma 6, with E & (cx + cz.).
Then for all f [T' - 1], holds that
A Aoll =
A6+1
A - Aull stbppy S
(B.84)
2MT
k=
K=
where the last inequality follows from 7 2MIleej
Then for t E [T' 1]. holds that
|| - >all < = - >ell + || - -aal
1
(z.) VV ( ptppls st( 1)ffl, S &Tpppl S
2M
(B.85)
By the update of X and the definition of projection,
Ae11 AT (At) = arg min /|x - 111 xC
(B.86)
Also we have
Ap. = -gg (At) = arg min [|] - 111122
(B.87)
>
Let Apạ. = DA.A,
AP.,M]] T. Then it holds that
| doll (b)
1
DAp..m Ap,ml
Dpp Aoll gM (At)) - doll
I
2M
where (a) follows from eonessxanssee of projection and that λu A M; (b) follows from (B.85). Therefore, each element of Xp satisfies
1 1
3
0
< Au
Dd Aamm S Apa. I do + pMp.. Au,m 5
< 1
M
2M
2.M
(B.88)
which shows that Ap, = 11 (A,) E A. Therefore holds that,
|AP - x 12
min
|| X
11 (2)
min ||> 1111 (e) XEAM
-AP
(B.89)
NEAM
where (c) is because dp E A, (d) is because A M c A M by the definition of the simplex; (e) is
because Apςt 11 (At) Then the equality holds that
A - 2 = min
|| 1
(B.90)
AEAM
and
1 pix -
1= dp. argmin 2 IIAEAM
(xt) =1IEAAM
det1-
(B.91)
M
The proof is complete.
30

---

With the help of Lemma 10, which simplifies the Euclidean projection operator as linear operator, we then prove Lemma 11, the recursive relation of 2, - x/2 and X; X₁. Lemma 11. Suppose Assumptions 1, hold. Under Example 1, choose Ao the MoDo algorithm. Denote { {dc} and {2/}, {X1 as the sequences generated by the MoDo algorithm with dataset S and S", respectively. Then it holds that
M L. 2 for
Ft x = P2210 and X X1 PA,bb
(B.92)
and Pa,, Px,t satisfy the following recursion
Pz,1+ = (1 ap on9,,,4,11 + 001,,( - (9,111 + 1(1,3 = j)a X²-1)
+ 1 = -))00,,31100 24 c,,b X2) - 1(4, d) N2
(B.93)
PA,1+1 = (1 -c,,1 + 72,1/44.11
1 =1,,, j) 241) a,2(b² X)) 1(in 1) X))
(B.94)
where (() is the indicator function.
Proof. Denote st,s, and z/ $ E [3]. as the samples selected in the t-th iteration from S and S' respectively. According to the MoDo algorithm update of Fe, and the definition of the problem in (B. 80), we have
T++1 =t - aV FR. = =
=x--a(Are a[Axr - b121.3.... ................................ Ar, - 2M A4+1 =t aAr; + a2,,(( Aet1).
(B.95)
The difference xt+1 + be computed by
Ft+1 2'41 = (T aA)) (Ir x'() a Act1 2/,33² ((+1)
=(T AAA) (I+ - x')) + az (de+1 - X/+1) + a(21,3 - 24,3) N
=(I aA)( x1)) az1z3' (de+1 X421) 114,33 j)cobb" Xe+1 (B.96)
where 11 (-) denotes the indicator function, and the last equation follows from that 21,3 - 2/,33 = 0 if i,, # j, and 2t,3 24,3 = - 2/j = v if ir.3 = j. By Lemma 10, in Example 1, Ax+1 Pi (A. -VFF (x)) further derived as
T T V (F)2A))) + M 1. which can be
A411 =Pi(A, - -VV (xx) T V Fx (ee + T/'
1
-P1 \1 - >11x, A bzjT,) (Arr - 2b 21)
+ M
N - 7 A - Pibz, (Ax, 2 Txo)
N 7bb (Az, - 2, Xx)
(B.97)
where (a) follows from rearranging the equation and that Pide+ 1/ II (A)) as d. AM; (b) follows from that P1b = 6p and P11 = O.
The difference det1 N4+1 be derived as
Aet1 X41 =0, -x) + >br [2,11Ar Ar, 24, Ax') 7br (2. d, 21.2 X)
(c) (N1 - X) + + A(2: - x1) + 7bp(2111 - TT An, - - 20 (Ar - X)
>br((2,11 > 2 X - 7br2(T](212 =12) X/
( (A -) + 7 A x3)) - >bp2 - 2 (A, Xx) vT 2, x1) (ir,2 j)>bp2/ Tub" X/
+ = (((:1=j))pp(pm
(B.98)
where (c) follows from rearranging the equation; (d) follows from that 2t.s 21,0 = 0 if it, # j. and 2t,8 24. 2g - 2/ = v if i, j. and that Au pv.
31

---

Combining (B.96) and (B.98) gives
xt-1 2/+1
Cr.a.t
Cr...
It z/
cob [ob
000,30 jbb1 X
+ (V2,3 j)ax
- (ir,2 iiy
Ar-1 X++1
Cx,,,
Ae - X/]
0
bpc,, 1 bT X
(aceaaluu 24 c222 Xi)
+ 11111,1=10 50y
(B.99)
bp(wr zy - c, X/)
where the matrices are defined as
C2 =l aA + 2, bp T 1 1 aA + a7,
(B.100a)
C2 3 T (1 rbp2i, 20,2
act T (1 a
70,22
(B.100b)
OA -y "C,11/bbpp
(B.100c)
OA.A1 -1I - 77b22,, 21,2 (I (I=00,1442bbbb))
(B.100d)
Next we show by induction that
Tt x ux and d X pxxbb.
(B.101)
First, when /. = 0, vo- - 2 = 0 = 0x or and λo X/ = fxoobp with 9r.0 = 0 and PP,00 = 0.
Therefore (B.101) holds = 0. Supposing that (B. holds for t = k next we show that also holds at f = k + 1.
At f k 1, applying (B.99) for rx+1 2 and substituting (B.100a), (B.100b) yields
I z/
Tk+1 - 2 = 1Crp CR,A,e]
+ 1 (1k.3 = j)embl x
A1= N/.
+ + j)rack, T I'a cx,2 Xb) 1(ix,2 joaac,,dh, 1 X/.
-(I aA 0 1) &U (cc y0,, Ck, + 1 1 = j)abb T No+1
+ 1(i..1 = j) 1) 1/4 - cx.b x)) 1( = j) ub X
=(1 ay + a,,,,,0t,111)4
ack,3(1 70,111,2)) + 1( j)a(bT (et1)u
+ 1 = j) j)
I/ cx.b X) 1 j) vb X
=0,,++1
(B.102)
where Pr,k+1 is computed by
Pn,t+1 =(1 au + anc + (11 - -0,,10 + Ilik,s f)a(b" M
(1k, j)yack,s (nN) 2/6 cb Xx) 1 (ix,2 = sc b_ Xx-
(B.103)
Therefore, for all t E [T]. it holds that - 11 = P2
At f k apply (B.99) for AR+1 No41 and substitute (B.100c), (B. yields
Iz xx Av - Xx
AR+1 Xet1 = =COx. CxA..l
+ + = ()bbur a'k cx Xx) 1(ix,2 = jlrck, bpb X
=ycm,1ubpp" P0 + (1 - 1c. >bpPA.
+1(1n,11 = ()bpu Tok cxpbbbb X²) 1 = 1bbb X/
=70,.14Ps. + (1 - -T00,10.229x..bp
+1(in,1 = j) (m(u (M(uTAt) Tab))= cb,2(b Xb) 1lin.2 j)yck, (bT 1r3bp
=
(B.104)
where PX,++1 is computed by
PPAA+1 -/,,,11992, (1 70.
+ + = j):(m( xx4) - (b Xx)) 1(x,2 10b2=jhie i0cck Xx).
(B.
Therefore, for all t [T]. it holds that ); - 2/. bp.
32

---

Lemma 11 provides the recursive relation of zt - 24, and X X, And Lemma 12 below provides another property used derive the lower bound of E||ØTT z/y II] in Theorem 6.
Lemma 12. Suppose Assumptions 1, hold. Under Example I, choose so = = TV, a AnT for the MoDo algorithm. Denote {x+}. {de} and {24 {M) as the sequences generated by the MoDo algorithm with dataset and S", respectively. Then holds that
V E'AAAT' zr22 20 and b
(B.106)
Proof. From the update of zyy we have
2 =1 aAx' + (b (xxx))
=x/- aAd' + adl 1141)
(B.107)
Suppose z/ = 12 then 2/41 = 1,,+1 with
2,,41 = (1 (1- <1 + ad
N+41)
and BA = (1 - -aa))aaaa + aul (b N+41)
Applying the above inequality recursively gives
e EAAL =v
T (1- aup) (1-a1pp))) xo + ap Σ (1 ax² E6 (bT=)))+) P=0
20 To (1-ap))' zo ap' - (1 axp)
6 A 1 for all À E AM
opp
=(1 ax4)² (v xo p'u-11) 1 11
Since zo = Tv, pl 11 < 1, holds that
v E [ =(1 axt (7 μ 1) + p'p=11 2 261 auu) + +1'p1
Then it follows that
u T. AAAA 2b \/] =uBAAo T x -bb
bT [1] 2 16011 axd + + (1 + v2))
zμ 6(1 aptt) - (1 + v2))
/ p -1 2
zμ 6(1 1) (1 + v2) 20 0
TnT
By the update of X, from (B.97),
TT "EAAA
x1=b² T T 1 (Ax4 - =1,22' [x)1
-yEAlp'' (An', <4,2b² xx)1
EA 1 æf,1 independent of X; and a!
=yp'e T [Ax', - yl'uT X1
EA[ = plv, 24,2 independent of X n1 S p. b x 1 for all À E A EA[2,2] pv, 2t.2 independent of X
Zyu'v T EA [Ax' -uob" X]
=up'v EA - 2r, XM 2 0.
The proof is complete.
Theorem 6. Suppose Assumptions 1 and 2 hold. Under Example with M = 2, choose An + To = = = 7v, a 4uT 0 < <<T 2MT and T & An for the MoDo algorithm. Denote (x+), ). {)e) and (a(), {X. the sequences generated by the MoDo algorithm with dataset S and S¹. respectively. Then holds that
TT
E E|
2
(B.108)
2n
16n
33

---

Proof. Denote 6, = |z, -2/1l Se = || - XII. From Lemma 11, it holds that
[| El| El 2 B Px,0+1]
(B.109)
18 [[ = 111/,,.++111. = Px.++1l 2 [px,,+1]]
(B.110)
where Pa,,, PA,r satisfy
Pp,1+1 = (1 - ap ao 001,3 70,1-1)),))) + - X-11
=
+ + = j) 22 c2 X) - 1 j)yac,ad,, X
(B.11I)
PA,++ = (1 - 1r,22)) + 77,11442.
+ + (u(v af() a,2(b' x)) 1iin j)rch, X).
(B.112)
The expectation of P2,t+1 can be further bounded as
E[p2,0411 =B[(1 ap a792306110)00 + a01,3(1 (011012) + 1 a (411)
1
+ - >acc,3(u0 c X) -a04,34,1 6" Xi]
1 2 (1 ap(l "2²))))20000 ( au(11 7/2 (2))))BB ]B(Px, + ab E[ ~rapp't B[X]] n 2(1 -11oa0 a(1-ap(1 ap(1- (x² (1(p))))))) + aup - 742 )12))((px.)] + ab [[]][[1 -xx²) (B.113)
(4)
n
where (a) follows from TE [ct.)] ] = 14, BA [c = = S E[X++1] 2 [EV]] by Lemma 12, and the fact that Ct2, is independent of (Px,t-
Similarly, the expectation of (PA,-11 can be further bounded as
1 76,, X)I Elpx =B((1 - -0,,1 + yo.1 + (u(u( xa/) c2, (x))
n
1 -yp'b b [[X]
21 (1-1 ) + 7/1 El (p
(B.114)
where (b) follows from E. [cr.l = μr EA Bclcc = n² S μr and Lemma 12.
The above arguments prove that
E E
E pr,
api(1 - 2 (1 - axp(1 - -11))
E Pr,t E
Ta(1 - 71²2 +
B(G++1)
E (
7p1
-1-701 21
n
(B.115)
where the inequality for vectors denotes the inequality of each corresponding element in the vectors, and matrix has UB, = [1, 1] as an eigenvector associated with the eigenvalue because
app(1 7)2))
apl(1 (4(1))43)
[
!
BUB.1
(1 - (1-
(B.116)
212 2
Similarly, since
B [a(1 (1 - y
(1 ajp(1 7121)
aju(1 - 7121
[a(1 7122)
|
7/10
7/2
(1 - 7p12)
7784
(1 aqj(1 7422 ))({)aa(11 - 7122) yaau(1 - 7/²1
71 (1 - 9/12) 7m(1 - 7412)
(1 a1))(1 - -112)aa11 - 9112
= (1 a1)) - 7122 [a(1--110 - 7122)
[
(1 a44 (1-9)))))
-7/4
(B.117)
then UB,2 Ja(1 -)12), yy] is another eigenvector of B with positive eigenvalue (1-a4)(1- n4²²) < 1. Let Qn [Un,1, Un 2]. which can be expressed as
a< 1 7422
Q Q = [UB,1, U =
1
(B.118)
7/
34

---

Then B has eigenvalue decomposition B - QBABQB where Ag = diag([1, (1- -11)))> and thus B² = Q for i E [T].
Let [a(1 - -, - = QB(CB,1 where [CB,1, CB22
=QB [0(1aa(11 1a(1a111//4 -1²), -p/n1" can
be computed by
CD.1 cB,2
a(1 7122 =QB
-7p -a(1 yp2)
[ -w'n
a(1 - 222) + 7M
1
Ta 1²) 7122) a + n¹7
> ?
(B.119)
a(1 - + 7/
where the last inequality follows from nl = 1 and a(1 71²²) 2 j 1/(8uT) 2 7 for
CB,1 2 2.7 and ap² (4T))
4n 4n 3 2
μ - μ², so that μ'y 702 - μ
11) 2 a+ 7(p axr2) a11 - yp²) 7/ for CB2 2
Since all elements in B are positive, multiplying B on both sides preserves inequality. Applying (B.115) recursively yields
B B B
T-1
B
aa(1 72²2
-1l7
=
T-1
Σ
BT- 1-t
1 [a(1- -n1²)
-1'7
T-1 Σ
B
1-t 1
QB
CR,1
cn22
1=0
t=0
1=0
1 CB,IUB,1 +
Σ
(11 au) (1- -11²)) T-1
CB,2UB,2
1=0
1=0
T
TT
1 Snee
-
CBB +
CB, 2
UB
+
B.2
(B.120)
STac
2n²
where the last inequality follows from CB.1 2
1
and CB2 2 1. Plugging in UB,1 = [] and
2n
UB,2 [a(1 7x²), -nu]", and since - 71
1.4 it follows that B[ōr) 2
16n
B.4.5 Proof of Theorem
Proof of Theorem 2. Combining the argument stability in Theorem 5, and Assumption 1, the MOL uniform stability can be bounded by
sup EA VE, (A(S)) - (FA(((
<EAL 12 (1As) - -A(S))11
by Assumption
48 l. Lr. (a+
12 + 4M07 10M0
(B.121)
pn
un
Then based Propositions 2-3, have
EAS BA.s,Roon (A(S))] A.S ( - (Fs(((
by Proposition by Proposition 3 by (B.121)
<dep + Vn (V>
=0(n
The proof of the upper bound is complete. We then prove the MOL uniform stability lower bound based the argument uniform stability lower bound in Theorem 6. By the strong convexity of the function fm, (x), for all m E [M]
sup EA / - VEL
2MM - I1 by Assumption
2
by Theorem 6 and Jensen's 's inequality
256n
The proof of the lower bound is complete.
35

---

C Bounding the optimization error
C.1 Auxiliary lemmas
Lemma 13 (Uniqueness of CA direction). Given Q E RdxM then do = QX with X E arg x ||QII| exists, and dq is unique.
Proof. This standard result due to convexity of the subproblem. Proof is given in [9, Section 2].
Lemma 14. For any x E R,, define X (x) such that
(x) E arg min XEAM
[[VF(T))]?
(C.1)
Then, for any E Rdd and X E AM, it holds that (v)( VF(x)A) 2 (VF( and |V(z)A- VF()) [VF (VF
(C.2)
(C.3)
Proof. By the first order optimality condition for (C.1), for any E Rd and X E AM we have
VFF))) - (²x))) 20.
(C.4)
By rearranging the above inequality, we obtain
(vF()))"(r), VF(=)A) 2 |VF(
(C.5)
which is precisely the first inequality in the claim. Furthermore, we can also have
[[F(())> (=) = -
(z) I VF (1 (=) (|) = =|VF(=)>| (VF
(C.6)
which is the desired second inequality claim. Hence, the proof complete.
Lemma 15 (Continuity of x²(x)). Given any p > and Rd. define Xz(x)
arg mig (x) + |P?, then the following inequality holds
(x)(*) - x²x001 P ([V[II))][TFL
(C.7)
Suppose either 1) Assumptions 1, hold, or 2) Assumptions 1, 2 hold, with E defined in Lemma 1. Then for x {xr)T=1 x' E {x/ generated by MoDo algorithm on training dataset and St, respectively, it implies that
- ((,))~)(('')) < 2p 2p-2ppppppp 1eiefll - 2'11
(C.8)
Proof. We provide proof leveraging the convergence properties of the projected gradient descent algorithm on strongly convex objectives below. Consider the problem minxEΛ" g x, {=))a(=)\|1 + =1 which is p-strongly convex. Let (Ap,(=)) for k = 0, 0, K de- note the sequence obtained from applying projected gradient descent (PGD) on the objective p(); = (Fs(2)A11 + / i.c.,
(x)+ =11-
=II MM ((1-10) (VP (p.
(C.9)
where y) is the step size that < ( of K. By the convergence result of PGD strongly convex objective, we know that (7(x) is the limit point of (2) By the non-expansiveness of projection, have
+ p). Note that both 7 are independent
D (x) Ap.4+1(x')
36

---

<|I((1 - mp)r (FF((() ((1-))())))--------------------- ( VFs(z')) (pxx
[1(1-1)) 1171 )
<(1 - - +1 VPs(x) -FFs())
(C.10)
Since A2,0(2) =x,0(x')= = Ap,0. apply the above inequality recursively from h: 0, O. K
we have
K-1
(1)) (xx(x0)) <n(((F (Fs(2) VFGG)--V
Σ (1 np)*
k=
(1p)
TP
51 (10) - VPs(z')
(C.11)
Then it follows that
(x) X5(2')1
- lim (115(0)) (ax(x)] (122(()) - (axx(2)) -
K+*
$ lim (112(()) (xxxx=)|++143) (x)x(=))1)
K+x
+ lim p -11- (m1p) x ((V))(()) T VFS(E) VFs(t') (Fs('')) (FF(a'"
K=000
4
1 (VVFs(() VFs(2) VFs(x)) T VFs(2')1 lim 2V pnk K-00
Sp (VEss() VPs(x) VFs(T) VFs(z')I
(C.12)
where (a) follows from lim 1 - (np)* 1, and from the convergence of PGD [2, Theorem 1.1] on p-strongly convex objectives that
211),0(x)- (xxx))
1xx2111
(x)
-
-
Σ
2n
pm
This proves (C.7).
In addition, under Assumptions 1, 3, the above result directly implies that [) - x7(x')1 (VVF(()) VFs(2) VFs(=')
+ VFF())))e - VFs(=')1
x'1l-
(C.13)
While under Assumptions 1 and 2, and for Ep defined in Lemma 1, and for x (2y 17 I' {21]T= generated by MoDo algorithm on training dataset S and S", respectively, [[(]s()]] s lr. [VFs(z))) < LF, which along with (C.12) implies that
(a) - X,(x0) <p- ([VFs(() + VF VFs(2')l s 2p--1 tF, x'
The proof is complete.
Lemma 16. For any p > 0 and x E R2,, define (xxx) arg min |VF((r)A11 and X2(x) = arg M [=) + p||A||?. then have
(VS( (1- 1
0 < [Fg(2)))())) -
(C.14)
M
Proof. Since (x)x) arg minxes* [>) therefore
[V [VFs(=)>*<>)) - M
[[ min [VFs(=)\|] 2 (C.15)
37

---

Since )7(x) = arg minxes
therefore
p(1x 20 0.
(C.16)
Rearranging the above inequality gives
50(0)) = M M
sol Pl1A5(0)1
(C.17)
Lemma 17. Consider { (Fe) generated by the MoDo algorithm. For all X E AM, it holds that
Ba X, (v+) (F)())))
<TAAAAr 2|1 - E A++1 A|12 FV V (
(C.18)
and W: (x (V
AA - All BAllA++1 - A|l? + (VV., (
(C.19)
Proof. By the update of X, for all À E AM, we have
Det1 211
VF2,, (z)))A) A/R2 < < FF, (xre) V Fz
=I (de - 7/ (x))
AlI2
= 1 X|12 11p--2114 (Ar X, (V Fx., (xx) ( ((V,,
V F s2, (3r))
Taking expectation 2t,1, 2, both sides and rearranging proves (C.18).
By the convexity of the problem, minxEAM 2 ) we have
( -1=rs [VF
32> (A: - X, (V/ (VFss((())VV
VFs((:))A))
(C.18) S EAllA A122 EaIlA++1 X|I + 1 ((V (2x) (x.,(aa)))
(C.20)
Rearranging the above inequality proves (C.19).
C.2 Proof of Lemma Distance CA direction
Organization of proof. In Lemma 18, prove the upper bound of the distance to CA direction,
- EA {srr))A (Fs X (ar))lF², in terms of two average of sequences, SI, and S2, Then under either Assumptions 1, 3, or Assumptions 1, 2, we prove the upper bound of ST,T, and S2,T. and thus the average-iterate distance CA direction in Lemma 2.
Lemma 18. Suppose Assumption I holds. Let {xt}, {Ar} be the sequences produced by the MoDo algorithm. With positive constant > 0, define
1
SI. EAI( (z.) VF. VF:..
(C.21a)
T-1
S2. = T
Σ
ExllVF)(0H4) + V
(C.21b)
Then it holds that
T
2/(1 (1 11-pp'arrpa (arr. + +
T
1=0
(C.22)
38

---

Proof. Define (2)) arg AM FV + e with p > 0. Note that p is strictly positive and is used only for analysis but for algorithm update.
Substituting À = (x+) in Lemma 17, (C.19), we have
7h. PB ( (1=
EA |1 - (,(x,)] A++1 + (( (F). (C.23)
Setting 7 = > 0, taking expectation and telescoping the above inequality gives
Ball -
BA X|(00)1--- 11 - - -x
(VF,, V
T
T
1=
T
E - x0(0011 11++1 -
BBll(VFF,, (mx)
(
7T
T
1=
(C.24)
where 1ı can be further derived as
T-1
1 Σ BAllA, - - - -2,12:111
=Bal 22(20))12 - EAIIAT 23(0T)112 Σ EA Elll X2(00+11112 1e41 - x7(x))
<AAlAAo 12(20)112 - EAIlAT 15(xT)11
T-2
EAI1 17(0++1) X2
(3(x))1 -1)(0)))
T-2
<4 4 (xll)((0111) - (1))
Σ
(C.25)
1=
where (13(11411) 17(zz))1 111 by Lemma 15, can be bounded by
[15(0++1) - 1b(x))11 ~ 3 "VF + -
-p FF. V/S
al (
(C.26)
Hence, it follows that
1 <4+ 1 F Σ +
=4+ 4p 7
(C.27)
plugging which into (C.24) gives
E - (VF 4 (1 + aap, + 7,,T5. (C.28)
T
7T
Define X* (xx) E mi
\F Then
T-1
39

---

EA - (175))))))))
T
(C
(1 + p
alp, + +
BA -
TT
< 7/ + a (S2,T) +
(C.29)
where the last inequality follows from Lemma 16. The proof is complete.
Proof of Lemma 2. Building on the result in Lemma 18, and by the convexity of the subproblem,
min 211l (xx+))) and Lemma 14, have
T
1-
Spt (1 + p alp + +1,1 (C.30)
I
By Assumptions 1, 3 or Assumptions 1, and Lemma 1, we have
S1,7 T
EA F (2r)) VV (x:))A (eglr) S &ME
(C.31)
S2. T
228flp.
(C.32)
Substituting S1,T, S2,r (C.30) with the above bound yields
BAll (Fs(a))A(x)111 + 7I (1 + (1t2p/aaarl/1/ + yMe.
T
t=0
(C.33)
Because bEilF S M, choosing p 13//)),113/7)) yields
(a)
4
(Fs(2.)A<<<))1 (Fs
sp+
(1 + +p2pptaa 2------TMM aTM + YME
T
7T
4
xT 6 Meg + +rM
(C.34)
where (a) follows from Lemma 14. This proves the result.
C.3 Proof of Theorem 3 PS optimization error
Technical contributions. The optimization error bound in Theorem 3 is improved with either relaxed assumption or improved convergence rate compared to prior stochastic MOL algorithms [52, 10, 30] (see Table 2). This is achieved by 1) instead of bounding the approximation error to X* >*(x)). we bound that to the CA direction d(xx)) = - F (FF(()))) (xx))* (x; as a whole, and 2) instead of using the descent lemma of Fs (sxx)) )** (xx) with dynamic weight, use that of Fs (xxx)) ) with fixed weight (see Lemma 19, (C.36)), thereby improving the tightness of the bound.
Organization of proof. In Lemma 19, we prove the upper bound of the PS optimization error, terms three average of sequences, SI.T, Sa, and S4,7. Then we prove the upper bound of S1,T, Sa.T, and S4,7, and thus the PS optimization error either in the nonconvex case under Assumptions 1, or in the strongly convex case under Assumptions 1, Combining the results leads to Theorem 3.
+ Σ (z)))
40

---

Lemma 19. Suppose Assumption I holds. Consider the sequence {2t), {Mr generated by MoDo in unbounded domain for æ. Define
T
S1,
V (2)) (z))b
(C.35a)
T
t=
S3,
1
Σ
BAIl (E)))
(C.35b)
T
t=
T
ST.
T
(C.35c)
Then holds that
B 2nT [A(Fs(r1) Fs(#T+1)]A + 575, 78,T + Jalz,1S...
Proof.
By the f -wi.--ippphhiizsmmsea smoothness of Fs(x)) for all X E AM we have
- Fs(x;) F xx) +
| 12l?
2
l a
= - a..VFF((L))) VF, +
VF.
(C.36)
Taking expectation over 22,3 on both sides of the above inequality gives
f a Ez. VV
E., [Fs(x(41]A Fs(x1)A (FVVSss-
(xx) (C.37)
) 11
By Lemma 17, (C.18), we have
E (Ae X, (VFs(r)) VFs((:))) VFF(())))
< 2| EAllA++1 ^ll ( (Ix) VF (r)))all
(C.38)
Rearranging the above inequality and letting 7t = gives
EA V.s((.) < EATA, (VFs(T)) T (FS 1 EA(1A - 2112 11 A113)
1
24
EF.. T (x:)).
- EA 27
EA(IA AII
D - -113)
7E (zt) T V' (x:)))
(C.39)
Plugging the above inequality into (C.37), and setting a = a 0. we have
(F Fs(x1)A) - VFs(E)) + l (VF.
2
< -- ( + - EA(lAA: -112 -112-11441 - -
27
1 LI (1.))
+OEA(VF VFS(E)) >442))
2
E. (Z.) VF (1)))1)))
(C.40)
41

---

Taking telescope sum and rearranging yields, for all X E AM,
EA (F
t=
1
BAll A/12
af Σ
2
+ 27
Σ
2 (VP (MEAIVVP2,, (1:)
+ f BAl (F.
t=
+ 2 (VEg(a)) A (A
- -1+1)))
1
BA 2|I2 - || A1121 ot Ba(Fs((r) Fs( 27,1, 73, + - jall,1 (C.41)
2
Setting À = Å in the above inequality yields
1 EA(Fs(m)) Fs( + 2 2 + S + f
1
1
E F
- aT
T
2
Finally, the results follow from the definition of X (ar)) such that T El
- EA (F
T-1 (2s))\1
Et=
Proof of Theorem 3. Lemma 19 states that, under Assumption we have
T T
1 aT < - BA(Ps(())) ExI - Fs( + S1 + 78a, - 2 F.1...
1
1
t=0
Then we proceed to bound SI,T, S3,T, S4,r. Under either Assumptions 1, or Assumptions 1, with l,, Ep defined in Lemma 1, we have that for all 2 E S and ( S Ey. and [V & lp. Then S1,r,Sa, S3,T, S4,7 can be bounded below
ST. T
BAI((VF s., ( (1)))1 & M
(C.42a)
1 T-1
Sa.T T
Σ
SeG ME (C.42b)
1=0
T-1
S4.7
T
Σ
(1)
S
(C.42c)
which proves that
1
E (
a9 + 7TME + al
(C.43)
2
We arrive at the results by B - from the Jensen's 's inequality and the convexity of the square function, as well as the subadditivity of square root function.
(
42

---

Empirici Parcto Inihal teerato
hagiee
23
23
25
-10
-30
10
15
10
15
1
fs,
Fs, 1
Populnijón
4
lamay hante
10
-10
-10
-15
-15
-15
20
20
-20
20
15
(a) MGDA
(b) Static
(c) MoDo
Figure 5: Convergence of MGDA, static weighting and MoDo to the empirical (gray, upper) and population (green, lower) Pareto fronts. Horizontal and vertical axes in figures the first second row are the values of the two empirical / population objectives. Three colormaps are used for the trajectories from three initializations, respectively, where the same colormaps represent the trajectories of the same initializations, and darker colors in colormap indicate carlier iterations and lighter colors indicate later iterations.
D Additional experiments and implementation details
Compute. Experiments done on a machine with GPU NVIDIA RTX A5000. We MATLAB R2021a for the synthetic experiments in strongly convex case, and Python 3.8, CUDA 11.7, Pytorch 1.8.0 for other experiments. Unless otherwise stated, all experiments are repeated with random seeds. And their average performance and standard deviations are reported.
D.1 Synthetic experiments
D.1.1 Experiments strongly convex objectives
Implementation details. Below provide the details of experiments that generate Figure 3. We use the following synthetic example for the experiments in the strongly convex case. The m-th objective function with stochastic data sample is specified
fa)m(() b bl. am Ar
b2,m= x
(D.I)
where 61.m > 0 for all m E [M], and 62.m is another scalar. We set M = 3, bj = [b1,1; b1.2 b1.3] = [1; 2; 1], and b2 [b2, 22 b2.3] 11 2]. The default parameters are T 100,
0.01,
0.001. In other words, in Figure 3a, we fix 0.01, 0.001, and vary T: in Figure 3b, we fix T 100, 0.001, and vary o; and in Figure 3c, we fix T 100, 0.01, and vary 7.
D.1.2 Experiments on nonconvex objectives
Implementation details. The toy example is modified from [29] to consider stochastic data. Denote the model parameter standard multi-variate Gaussian distribution. And the individual empirical objectives are defined as:
[x1, 222] RR² stochastic data [21, 22] IR2 sampled from the
f2, (x) ei (x) (z) + ( and fa.2(=) ei (2) c2(1))e,(x)) where
hi (x) (og(max( [0.((=11 - (anl(-222), + 6,
ho (ma(max(( 0.5((21 (og(max((0.5(222 + tanh(-22) + 2), 0.000005) + 6,
43

---

2
13
10
X3
(a) 7
(b) 10
(c) 10 4
(d) 10-2
Figure 6: Trajectories of MoDo under different 7 on the contour of the average of objectives. The black marks initializations of the trajectories, colored from red (start) to yellow (end). The background solid/dotted contours display the landscape of the average empprical//populaiinn objectives. The gray/green bar marks empirical/ppopulaion Pareto front, and the black +/green * marks solution to the average objectives.
(2,1(x) ((-x) + 3.5) + (-22-1)9)110 2101 5.5 2232, g0,2(2) (1-21-
- 3.5) (-22 100
5.5 2242,
(xr = max(tanh(0.5 * x2),, 0) and c2(x) = max((anhh(-055 x2),, 0).
(D.2)
Since z is zero-mean, the individual population objectives are correspondingly:
f(x)) e1 (2) + and (z())a(()))) (o( where 91 (x) ((-2) 3.5) 0.1 (-I2 1)3)/10-00 20, (2(2) ((-21 - 0.1 (-I2 1)3)/10 20.
(D.3)
The training dataset size is |S| 20. For all methods, i.c. MGDA, static weighting, and MoDo, the number of iterations is T = 50000. The initialization of À is λ [0.5, 0.5] The hyperparameters for this experiment are summarized Table
Figure 5, in addition Figure 1, shows the trajectories of different methods from different initializa- tions to empirical and population Pareto fronts (PF). With the visualized empirical and population PFs, it is clear in Figure 5a, the first row, that the three trajectories of MGDA all converge to the empirical PF, but, it stops updating the model parameter as soon as it reaches the empirical PF However, due to the difference between the empirical and population PFs caused by finite stochastic training data, as shown in Figure 5a, the second row, not all three solutions from MGDA has small population risk, implied from the distance of the solution (yellow point) the population PF colored in green. For static weighting method with uniform weights in Figure 5b, one trajectory able to converge the center of the empirical PF, which is the optimal solution of the uniform average of the two objectives. However, the other two get stuck and oscillate around suboptimal parameters for long time, corresponding the clusters of scattered points in the figure. Nevertheless, in the second row Figure 5b, one empirically suboptimal solution (on the trajectory with red to yellow colormap) is able to achieve small population risk. This example demonstrates that even though static weighting method does not have small distance to CA direction, it might still be able to achieve small testing error. Finally, for MoDo in Figure 5c, the first row shows that MoDo is slower than MGDA in convergence to the empirical PF, since it only approximately solves the CA direction using
Table 5: Summary of hyper-parameter choices for nonconvex synthetic data.
Static
MGDA
MoDo
optimizer of
Adam
Adam
Adam
ze step size (at)
x 10-3
10-3
10-3
A step size (ty)
10-4
batch size
16
full
16
44

---

Prppica Freet
Jeugl
-10
-20
35
6.1
f5.1
f5.1
6.1
Pepukaja
Iani famas
-10
-10
-10
-10
-15
31
-10
20 -13 -10
-0 -1" -10
76
-15
-10
(a) 7
(b) 10
(c) 7 10
(d) 10
Figure 7: Convergence of MoDo to the empirical (gray, upper) and population (green, lower) Pareto fronts under different y. Horizontal and vertical axes in figures in the first second row the values of the two empirical population objectives. Three colormaps are used for the trajectories from three initializations, respectively, where the same colormaps represent the trajectories of the same initializations, and darker colors in one colormap indicate earlier iterations and lighter colors indicate later iterations.
stochastic gradient. The second row shows that all three solutions of MoDo can achieve relatively small population risk, demonstrating good generalization ability.
To demonstrate how the choice of y has an impact on the performance of MoDo, we further conduct experiments with different 7 and show that MoDo recover static weighting (y 0) and approximate MGDA (7 = 1)) Results are visualized in Figure 6, which plots the trajectories over the contours of the average objectives, and Figure 7, which plots the empirical and population PFs. Figure 6a and Figure 7a together verify that MoDo with = behaves the same as static weighting, ef. Figure Id and Figure 5b. Like static weighting, for two of the initializations. they either cannot go through the valley or stuck in the valley for long time. And if the trajectory converges, will converge the optimal solution of the average empirical objectives. In addition, Figure 6d and Figure 7d together indicate that MoDo with = 10-2 behaves similarly as MGDA, cf. Figure Ic and Figure 5a. Like MGIAA, it can go through the valley without getting stuck in it for a long time, and then converge to the empirical PF for all three initializations. But also like MGDA, it will stop updating or oscillating around the parameters as soon worse population risk for one of the solutions with a trajectory colored from purple to pink to yellow. We also conduct experiments on < < 10-2 With y 10-12, as shown Figures 6b, and 7b, MoDo is able to go through the valley and converge to the empirical PF for all initializations, but very slowly. And all initializations converge to the optimal solution of the average objectives. While with = 10 to the empirical PF for all initializations quickly. And it stops updating the parameters as soon as it reaches the empirical PF. The solutions of the three initializations are different from the optimal solution of the average objectives. But compared to the case when y = 10-2, the three solutions are closer to the optimal solution of the average objectives. This is because the weighting parameter À does not change too much during the optimization procedure with a small y.
reaches the empirical PF, resulting in
shown in Figures 6c, and 7c, MoDo is able to go through the valley and converge
D.2 Multi-task supervised learning experiments
In this section we present experiment details and additional results for comparison of static weight- ing, MGDA, and MoDo algorithms, under synthetic and real world multi-task supervised learning problems. We use MNIST, Office-31, Office-home, and NYU-v2 datasets.
D.2.1 MNIST dataset experiments
Implementation details. Below we provide the details and additional experimental results on MNIST image classification. We simulate synthetic multi-objective optimization problem using
45

---

different loss functions applied for training an image classifier for MNIST handwritten digit dataset. We consider three loss functions; cross entropy, mean squared eтror (MSE), and Huber loss. The model architecture is two-layer multi-layer perceptron (MLP). Each hidden layer has 512 neurons, and no hidden layer activation. The input size is 784, and the output size 10, the number of digit classes. The training, validation, and testing data sizes are 50k, 10k, and 10k, respectively. Hyper- parameters such as step sizes are chosen based on each algorithm's 's validation accuracy performance, as given in Table 6.
We then discuss the results of the experiments Table 7, which shows the performance of the last iterate for each method. Experiments are repeated 10 times with average performance and standard deviations reported. Observed from Table 7, for cross- entropy loss, MGDA performs the worst while static weighting performs the best. On the other hand. for Huber loss, MGDA performs the best while static weighting performs the worst. This not surprising as cross-entropy loss has the largest scale and Huber loss has the smallest scale among the three losses. Since equal weights are assigned for all three objectives in the static weighting method, it tends focus more on optimizing the loss with the largest scale. While for MGDA, it is the other way around. Compared to MGDA, MoDo performs much better on cross-entropy loss, and in the meantime, it achieves comparable performance Huber loss. Comparing their PS population risks Rpop and the decomposed PS optimization errors Ropt and PS generalization errors Rgen. MGDA has the smallest PS population risk and PS optimization error. One potential reason is that MGDA performs best on Huber loss, with smaller gradients. Another reason is that the generalization errors for all the algorithms are similar and not dominating compared to optimization errors in this setting. making the PS population risk close to the PS optimization error. Overall, MoDo demonstrates a balance among objectives with different scales and performs reasonably well on all three objectives since it combines the properties of static weighting and MGDA.
Table 6: Summary of hyper-parameter choices for MNIST image classification
Static
MGDA
MoDo
optimizer of xt. step size (ox) 0.1
SGD
SGD
SGD
5.0
1.0
A step size (7x)
1.0
batch size
64
64
Table 7: MNIST classification with cross-entropy, MSE, and Huber loss as objectives.
Cross-entropy
MSE loss
Huber loss
Method
Ryop (10-3)
Ropi (10-9)
[Rges (10 (10-3)4
Loss (10-3) 3)
Loss (10 9)4
Loss (10- 3
Static
306.9113,9
13.2.10.14
2.2.10.03
2.1510.56
1.9.0..5
0.2.10.19
MGDA
363.6:24.1
13.5=:0133
1.9:0.011
1.3:10.24
1.1::0.2
0.2:+0.13
MoDo
317.9+3.4
13.1::0113
2.1::0.55
2.1
1.910.4
0.1:10.09
D.2.2 Office-31 and Office-home dataset experiments
Implementation details. We give the details for the experiments conducted using Office-31 1 and Office-home datasets, which consist of multi-domain image classification tasks. Both of these are multi-input single-task learning problems. Office-31 and Office-home consist of 31 and 65 image classes, respectively. The image domains for Office-31 1 are; "Amazon", which includes object images from Amazon, "DSLR", which includes high-resolution images of objects, and "Webcam".. which includes low-resolution images from objects. The image domains for Office-31 are "Art", "Clipart", "Product", and wooldd"""d" which include images of objects taken from the respective image domains. We use the MTL benchmark framework LibMTL [26] to run experiments on both of the aforementioned datasets. For both datasets, we tune the step size of x and weight decay parameters for Static and MGDA algorithms and tune the step sizes of x and À for the MoDo algorithm. We use batch size 64 to update static weighting and MGDA, and use 2 independent samples of batch size 32 to update MoDo, for both Office-31 and Office-home. A summary of cappe--paramteer used for
46

---

Table 8: Summary of syper--prameee choices for Office-31 331 task
Static
MGDA
MoDo
optimizer of ar
Adam
Adam
Adam
2t step size (ax)
10
10
10
A step size (%c
10-3
weight decay
10-3
10-7
10-5
batch size
64
64
64
Office-31 31 and Office-home for each algorithm given in Table 8 and Table 9, respectively. All other experiment setup is shared for all algorithms, and the default LibMTL configuration is used.
The results of Office-31 and Office-home experiments given in Tables 3 and 10, respectively (average over 5 seeds, the error indicates standard deviation). Here, we use the average per-task performance drop of metries SA.m for method A with respect to corresponding baseline measures SB,m as a measure of the overall performance of given method. Specifically, this measure is
M Σ (-1) (SA. SSB.))SB,.. x 100, M m==
AA%
(D.4)
where M is the number of tasks. Here, fm -1 if higher values for SAm are better and 0 otherwise. We use the best results for each task obtained by dedicated independent task learners of each task as SB.m- The independent task learners are tuned for the learning rate and weight decay parameter. For Office-31, SB.n values are 87.50% for "Amazon", 98.88 98.88% for "DSLR". and 97.32% for "Webcam". For Office-home, S8.m values are 66.98% for "Art", 82.02% for "Clipart", 91.53% for "Product", and 80.97% for "Real-world". It can be seen from Tables and 10 that static weighting outperforms MGDA method in some tasks and also in terms of 4.%. However, by proper choices of hyper- parameters, MoDo performs on par or better compared both static weighting and MGDA, and hence achieves the best overall performance in terms of A.%.
Table 9: Summary of syper-parameter choices for Office-home task
Static
MGDA
MoDo
optimizer of aı
Adam
Adam
Adam
x; step size (ax)
10
10-4
10-4
A step size (7c)
10
weight decay
10
10-6
10
batch size
64
64
64
Table 10: Classification results on Office-home dataset.
Art
Clipart
Product
Real-world
Method
A,% 4
Test Ace f
Test Acc f
Test Ace
Test Acc 1
Static
64.14 1.40
79.57 1.09
90.00 0.50
78.94 + 0.87
2.85 + 1.08
MGDA
61.71 1.33
73.95
0.43
90.17 + 0.27
79.35 + 1.15
5.29 + 0.47
MoDo
65.50 + 0.55
79.44 0.29
89.72 + 0.94
79.65 1 0.67
2.24 1: 0.48
D.2.3 NYU-v2 dataset experiments
Implementation details. We give the details for the experiments conducted using NYU-v2 dataset, which consists of image segmentation, depth estimation, and surface normal estimation tasks. Un- like Office-31 and Office-homa datasets, this is single-input multi-task learning problem. The
47

---

dataset consists of images from indoor video sequences. We use the MTL benchmark framework LibMTL [26] to run experiments with this dataset. We tune step size of and weight decay parame- ters for static weighting and MGDA algorithms, and tune step sizes of x and À for MoDo algorithm. We use batch size 4 to update static weighting and MGDA, and use independent batches of size to update MoDo. Experiments were run for 50 epochs for all methods. Since there was no validation set for NYU-v2, we averaged and reported the test performance of the last 10 epochs. summary of hyper-parameters used for each algorithm is given in Table 11. All other experiment setup is shared for all algorithms, and the default LibMTL configuration is used.
Table 11: Summary of hlyer--paameett choices for NYU-v2 task
Static
MGDA
MoDo
optimizer of xt
Adam
Adam
Adam
xt step size (ax)
10-4
10-4
10-1
Ae step size (7c)
10-3
weight decay
10
10-6
10-6
batch size
4
4
4
Table 12: Segmentation, depth, and surface normal estimation results on NYU-v2 dataset.
Sogmetation
Depth
Surface Nomual
Method
(ligher Bester)
(Lower Better)
Widhin 1 (Higher better)
A.4%
(Lower Better)
Ace
Mean
Medias
30
Stutic 52,02 + 0.09 74.21 + 0.57 0.9944 + 0.0032
0.1645 + 0.0010
23,79
0.10
17.44 = 0.15
34.07
+ 0.17 60.17 4 0.31 71.48 + 0.29
5.88 +: 0.70
MGDA 16.39 1 0.17 70.27 1: 0.24
0.4299 a 0.0024
0,1737 1: 0.0009
22.34
0.03
15,70
0.08
37.71
+ 0.1
63.96 1 0.11 74.50 1 0.06
6.25
1:00 0.38
MoDo 52.64 + 0.19 74,67 + 0.08 0L394
0.0020
O. 1649 + 0.0188
23.45
0.06
17.09
0:05
34.79
0.11
60:30
0.13
02112
321 121:000 0.34
The results of NYU-v2 experiments are given in Tables 12 (average over 3 seeds, the error indicates standard deviation). Again, use the average per-task performance drop of metrics S m for method A with respect to corresponding baseline measures SB.m as a measure of the overall performance of given method. We the best results for each task obtained by dedicated independent task learners of each task as SB,m- The independent task learners are tuned for the learning rate and weight decay parameter. For segmentation task, SB,m. values are 53.94% for "mloU", and 75.67% for "Pix Acc". For depth estimation task, SB.m values are 0.3949 for "Abs Err", and 0.1634 for "Rel Err". For surface normal estimation task, S8.m values are 22.12 for "Angle Distance Mean", 15.49 for "Angle Distance- Median", 38.3 38.35% for "Within 11.25 64.30% for "Within 22.5 and 74.70% for "Within 30p". can be seen from Table 12 that MoDo outperforms both MGDA and static weighting in some tasks and also in terms of A.%. The worse performance of MGDA in terms of A.% can be due to the large bias towards the Surface normal estimation task, which seems to affect other tasks adversely.
D.2.4 Additional experiments for comparison with other MOL baselines
In this section, we provide comparison between MoDo and other popular MOL baselines. For this purpose, we use the same benchmark datasets as the previous section and use the experiment setup provided in [25] to run experiments with MoDo. Hence, we use experiment results provided by [25] for other baselines for comparison. Additionally, we implement MoCo [10], which is not included [25]. For results this section we report two holistic measures: AAst, which measures performance degradation w.r.t. static scalarization (similar to [25], but lower the better), and Asa. which measures performance degradation w.r.t. independent task learners (as defined in our paper)
The results on Office-31, Office-home, and NYU-v2 are given in Tables 13, 14, and 15, respectively. where MoDo outperforms all the baselines for most tasks, and has a better overall performance in A Ag % and A.ia %. The hyper-parameters of MoDo for the above experiments are in Table 16.
48

---

Table 13: Comparison with other methods on Office-31 dataset.
Method
Amazon
DSLR
Webcam
A.44%
A.A.% 4
Static (EW)
81.02
96.72
96.11
0.00
2.96
MGDA-UB [39]
81.02
95.90
97.77
0.40
3.32
GradNorm [6]
83.93
97.54
94.44
-0.19
2.80
PCGrad [48]
82.22
96.72
95.55
0.40
3.35
CAGrad [29]
82.22
96.72
96.67
0.01
2.96
RGW [25]
84.27
96.72
96.67
-0.81
2.18
MoCo [10]
85.30
97.54
97.22
-1.70
1.32
MoDo (ours)
85.47
98.36
96.67
-1.86
1.17
Table 14: Comparison with other methods on Office-home dataset.
Method
Art
Clipart
Product
Real-world
A.4 4
A.a%% 4
Static (EW)
62.99
76.48
88.45
77.72
0.00
5.02
MGDA-UB [25]
64.32
75.29
89.72
79.35
-1.02
4.04
GradNorm [6]
65.46
75.29
88.66
78.91
-1.03
4.04
PCGrad [48]
63.94
76.05
88.87
78.27
-0.53
4.51
CAGrad [29]
63.75
75.94
89.08
78.27
-0.48
4.56
RGW [25]
65.08
78.65
88.66
79.89
-2.30
2.85
MoCo [10]
64.14
79.85
89.62
79.57
-2.48
2.68
MoDo (ours)
66.22
78.22
89.83
80.32
-3.08
2.11
Table 15: Comparison with other methods on NYU-v2 dataset.
Seamentttion
Dopth
Surface Normal
4.4% 4.
A.4 %
Method
(Higher Better)
(1 Better)
Angle
(Lowwer Betler)
(iigher better)
mloU
Pix Acc
Abs Err
Rel Ei
Mean
Median
11.25
22.5
30
53.77
0.3845
0.1605
23.57
17.04
35.00
60:95
72.077
MGDA-UB
73,46
0.3834
0.1555
33.78
73.61
-0.38
1,26
GradNorm
53.58
75.06
0.3931
0.1663
23.54
16.98
35.11
61.11
72.24
0.99
2.62
POGrad
53.70
7544
0.3903
0.1607
23.43
16.97
35.16
61.19
72.28
0.16
1.79
RGW
53.85
75.87
0.3772
0.1562
23.67
17.24
34.62
60.49
71.75
0.62
1,03
MoCo
$4.05
75.58
0138112
0.1530
23.39
16.69
35.65
61.68
72,60
-1.47
0.18
MaDo
53.37
75.25
0.3739
0.1531
23.22
16.65
35.62
61.84
72.76
+1.59
Table 16: Summary of hyper- paree--rrrmeeter choices for MoDo
Office-31
Officc-home
NYU-v2
optimizer of æ
Adam
Adam
Adam
æe step size (ax)
x 10
x 10 4
2.5 -4
A step size (Tc)
10-6
10-3
10
weight decay
10-5
10-5
10
batch size
128
128
49


Reviews:
[{"review_id": "705m4hjA0h", "reviewer": "Reviewer_CY8e", "summary": "This paper studies the multi-objective optimization, and in particular, focus on the generalization and stability analysis. By decomposing the Pareto stationarity error into the generalization and optimization error, the authors then analyze and upper-bound these two errors respectively. The distance to the conflict-avoidant direction, which optimizes al objectives jointly, is also analyzed. A stochastic variant of MGDA named MoDo has been developed and analyzed. Based on the theoretical derivations, the authors find a three-way tradeoff among the optimization error, generalization error and the CA error. Some implications on the parameter selection and illustrations are provided.  ", "questions": "See Weakness part.", "limitations": "See Weakness part.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The studied topic on multi-objective optimization has received increasing attention thanks to the important applications like multi-task learning. Studying the generalization, stability and the tradeoff is important and under-explored.\n\n2. Although generalization has been studied for multi-objective optimization, stability has not been explored. This work seems to be the first one to fill this gap.\n\n3. The tradeoff among optimization and generalization is not surprising, but their tradeoffs with the CA direction error seem to be new given the multi-objective structure. ", "weaknesses": "1. How is (4a) equivalent to (4b)? Can the authors provide some more details?\n\n2. Before (4a), it says that CA direction maximize the minimum descent of all objectives. But (4a) seems to say that the direction minimizes something. \n\n3. The upper bounds in the nonconvex case may not be very tight given the large exponential dependence, and hence may not be able to exactly capture the generalization and tradeoff behaviors. Is it possible to provide a lower bound in this case? Or what challenges in getting a tight bound? \n\n4. The analysis uses Frobenius norm, which may be large in practice. Instead, spectrum norm may be more proper. Can the authors comment on why use Frobenius norm rather than spectrum norm?\n\nOverall, I appreciate the studied problem and the analysis in this work, but I am also open to other reviewers’ comments. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for appreciating our problem setup and analysis! We will respond to the weaknesses and questions point by point as follows.\n\n> **W1. & W2.** Derivations of (4a) and (4b).\n\nThis is a **standard derivation for the MGDA algorithm**. Similar derivations are provided in [25, Section 3.1], [47, Section 2.2].\n\nHere we also include a derivation as follows. For (4a), the original problem in MOO is to maximize the minimum descent (among all objectives) along the update direction $d$, where the minimum descent given $d$ can be computed by\n$$\\frac{1}{\\alpha}\\min_{m\\in [M]} \\{f_{S,m}(x) - f_{S,m}(x+\\alpha d)\\} \\approx \\min_{m\\in [M]} -\\langle \\nabla f_{S,m}(x), d\\rangle\n.$$\n\nThen with regularization on $d$ to control its norm, the problem is formulated as\n$$\\max_{d \\in \\mathbb{R}^d} \\min_{m\\in [M]} -\\langle \\nabla f_{S,m}(x), d\\rangle - \\frac{1}{2}||d||^2 $$\nwhich is equivalent to (4a) as\n$$\\min_{d \\in \\mathbb{R}^d} \\max_{m\\in [M]} \\langle \\nabla f_{S,m}(x), d\\rangle + \\frac{1}{2}||d||^2 .$$\n\nThen (4a) can be reformulated as\n\\begin{align}\n\\min_ {d \\in \\mathbb{R}^d} \\max_ {m\\in [M]} \\langle \\nabla f_ {S,m}(x), d\\rangle + \\frac{1}{2}||d||^2\n& =\\min_ {d \\in \\mathbb{R}^d} \\max_ {\\lambda \\in \\Delta^M} \\langle \\nabla F_ {S}(x)\\lambda, d\\rangle + \\frac{1}{2}||d||^2 \\\\\\\\\n&= \\max_ {\\lambda \\in \\Delta^M} \\min_ {d \\in \\mathbb{R}^d} \\langle \\nabla F_ {S}(x)\\lambda, d\\rangle + \\frac{1}{2}||d||^2\n\\end{align}\n\nwhere we use the min-max theorem to change the order of min and max operators in the last equation.\n\nIn this way, given $\\lambda$, the optimal $d^*(x,\\lambda)$ is obtained as $d^*(x,\\lambda) = -\\nabla F_S(x)\\lambda$, and the optimal $\\lambda^* \\in \\arg\\min_{\\lambda\\in \\Delta^M} ||\\nabla F_S(x)\\lambda||^2$. Combining these leads to the formulation (4b).\n\n>**W3.** The upper bounds in the nonconvex case may not be very tight given the large exponential dependence, and hence may not be able to exactly capture the generalization and tradeoff behaviors. Is it possible to provide a lower bound in this case? Or what challenges in getting a tight bound?\n\nThis might be a **misunderstanding** of our theorem. Note that **we do NOT have exponential dependence** on the hyperparameters $T$ or $n$, but rather, our general bound is in the order of $\\mathcal{O}(T/n)$ in the NC case (see Theorem 1). Therefore, our bound is already tighter compared to the one for single objective learning in [12], which could lead to exponential dependence on $T$ without $1/t$ step size decay even for static weighting.\n\nWe overcome the exponential dependence by bounding the probability of selecting the perturbed data in all $T$ iterations and the resulting error, instead of bounding the accumulated expected error in the output parameters  through recursion over each iteration as did in [12].\nThe latter could result in exponential dependence on $T$ in the NC case, since the expected error at each iteration increases over the previous one in a rate larger than 1, due to the expansiveness of the update function.\n\n>**W4.** The analysis uses Frobenius norm, which may be large in practice. Instead, spectrum norm may be more proper. Can the authors comment on why use Frobenius norm rather than spectrum norm?\n\nThank you for the suggestion. There are two main reasons for using Frobenius norm.\n\n**1. Frobenius norm of the gradient matrix, $||\\nabla F_ S(x)||_ F$ can be directly derived from the $\\ell$-2 norm of each gradient $||\\nabla f_ {S,m}(x)||$.**\nTherefore, the $\\ell_ F$-Lipschitz continuity of $F_ z(x)$ in Frobenius norm (Assumptions 1) can be direcly derived from the $\\ell_ f$-Lipschitz continuity of $f_ {z,m}(x)$ for all $m \\in [M]$ with $\\ell_ {F} = \\sqrt{M}\\ell_ {f}$, as discussed in Lemma 1. The latter assumption of $\\ell_ f$-Lipschitz continuity of $f_ {z,m}(x)$ for all $m \\in [M]$  were standard in prior works such as CR-MOGM [47], MoCo [8] for optimzation analysis.\n\n**2. The spectral norm and Frobenius norm can be used interchangeably up to a factor since for $A\\in\\mathbb{R}^{d\\times M}$, $||A||\\leq ||A ||_ F \\leq \\sqrt{r}||A ||$ where $r\\leq M<<d$ is the rank of $A$.**\nIn our analysis, $A$ is the gradient matrix $\\nabla F_ S(x)$, and $M$, the number of objectives, is a fixed constant and relatively small compared to other factors.\n\nNevertheless, it would interesting to derive our theory under the spectral norm or other matrix norms given appropriate assumptions.\n\n---\nWe hope that our responses to your comments are satisfactory. Thank you again!\n"}, {"review_id": "BKxHdMmGGT", "reviewer": "Reviewer_LuAm", "summary": "This paper studies three-way trade-off in multi-objective learning: 1) optimization error caused by sampling and stochastic training; 2) generalization error that measures the difference between source and target sets; 3) conflict-avoidance direction error that is the bias between the calculated direction and the right one. The authors propose the MoDo algorithm to optimize this trade-off in one algorithm. Plenty of theoretical analysis supports the claims.", "questions": "1. Why use double sampling? Can MoCo completely solve the problem? Or is it possible to reduce the sample complexity?\n\n2. Does the proposed theory can help improve PCGrad and CAGrad?", "limitations": "Sample efficiency of the proposed algorithm.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. This paper considers the multi-objective algorithmic design in a bigger picture by compositing three-way trade-off together, and provides solid analysis to solve it.\n\n2. This paper is well written. In particular, Table 1 and Figure 2 help to understand the contribution better.", "weaknesses": "1. The proposed algorithm needs to compute three batches of gradients to run an iteration, which is much less computationally efficient. \n\n2. Benchmarks are too limited that only contain static and MGDA (2018 proposed), experiments have not compared with other typical methods like PCGrad and CAGrad, which have better empirical performance. \n\n3. Several claims are out-of-date. In 34-35 \"Unfortunately, the reason behind this empirical performance\ndegradation is not fully understood and remains an open question\" is not accurate, since [1] has proved that the vanilla MGDA algorithm and also PCGrad and CAGrad will not converge to Pareto optimal. In 268 \"This can be overcome by increasing the batch size during optimization [25]\" is wrong, because the assumption on Lipschitzness for $\\lambda$ with respect to gradients has been proved to be wrong (Proposition 2 in [1]). Also, it can be proved that even a stochastic error of the gradient can cause a significant bias in the direction, so only increasing the batch size does not work.\n\n[1] S Zhou, W Zhang, J Jiang, W Zhong, J Gu, W Zhu - Advances in Neural Information Processing Systems, 2022", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for acknowledging the strengths of our work. Our point-to-point response to your comments follows next.\n\n> **W1 & Q1-3 & Limitation.** MoDo has limitation on sample efficiency. Is it possible to reduce improve?\n\n- Theoretically, MoDo is not necessarily worse on total sample complexity; see our **General Response-Q1**.\n\n- Practically, MoDo does not require more samples, because the batch size can be controlled to keep the sample size per iteration $n'$ the same.\nE.g., for the experiments in **Appendix D and General Response-Q2**, MoDo generally performs better than the baselines under the same $T\\times n'$.\n\nIn short, **MoDo could have better total sample complexity theoretically and practically**. While there may be room for improvement, it is beyond the scope of this paper.\n\n>**W2.** Limited benchmarks.\n\nSee more results in **General Response-Q2**.\n\n>**W3.** Outdated claims. ([1] is replaced with [47] as indexed in our submission)\n\n>**W3-1.** \"the reason ... is not fully understood ...\" is not accurate. [47] proved...\n\nWe agree **[47] partially addresses this from the optimization perspective**.\nHowever, \"empirical performance degradation\" in this context refers to the observed phenomenon of **test performance** being often worse than static weighting [15,40]. The reasons for this degradation are not fully understood theoretically, as prior works, such as [47], have focused solely on analyzing the theoretical training (optimization) error, NOT the generalization (test) error.\nIn fact, it has been demonstrated in [40, Figure 2] that the training (optimization) errors are all relatively small, while the generalization performances differ. Therefore, **only analyzing the optimization error is not enough to fully understand the test performance**. Nevertheless, we will follow your great suggestion to desribe related works more precisely and acknowledge the pioneering contribution of [47] in optimization. \n\n>**W3-2.** \"...can be overcome by increasing the batch size[25]...\" is wrong, because the assumption...in [25] is wrong...\n\nThis is a **misunderstanding**. We intend to convey that \"the bias in the CA direction can be mitigated by increasing the batch size\". We agree the assumption on Lipschitz $\\lambda^*(x)$ in [25] is wrong. But **this is a limitation of their proofs, NOT this claim**. In fact, for $Q\\in \\mathbb{R}^{d\\times M}$, although $\\lambda^*(Q)\\in \\arg\\min_{\\lambda\\in \\Delta^M}||Q\\lambda||^2$ is not Lipschitz continuous w.r.t. $Q$, it can be proved that the update direction is $\\frac{1}{2}$-Holder continuous w.r.t. $Q$ as stated below. \n$$||Q\\lambda^*(Q)-Q'\\lambda^*(Q')||^ 2\n\\leq 4\\max (||Q||,||Q'||)||Q - Q'||.$$\nPlugging in $Q = \\nabla F_S(x)$, $Q' = \\nabla F_Z(x)$ with $Z$ being a stochastic batch of $S$, we have\n$$\n||\\nabla F_S(x)\\lambda^*_S(x)- \\mathbb{E}_Z[\\nabla F_Z(x)\\lambda^*_Z(x)]||^2\n\\leq\\mathbb{E}_Z||\\nabla F_S(x)\\lambda^*_S(x) - \\nabla F_Z(x)\\lambda^*_Z(x)||^2 \n\\leq 4 \\ell_F \\mathbb{E}_Z||\\nabla F_S(x) - \\nabla F_Z(x)||=O(1/\\sqrt{|Z|}), \n$$\nwhich decreases as the batch size $|Z|$ increases. Therefore, the bias in the CA direction can be reduced by increasing the batch size. \n\nWe will follow your great suggestion to revise it as \"One challenge ... is the bias in the CA direction, which can be mitigated by increasing the batch size ...\", and **acknowledge [47] is the first work to prove the assumption is wrong in prior work [25], and propose a bias reduction scheme to address this issue**.\n\n>**Q1-1.** Why double sampling? \n\nIt is one way to mitigate the gradient bias without the momentum-based methods. See **General Response-Q3**.\n\n> **Q1-2.** Can MoCo solve the problem?\n\nIf the \"problem\" is to reduce bias in optimization, MoCo can solve it. But the \"problem\" we study in this paper, the theoretical test risk, is **different**. MoCo **CANNOT completely solve** the test problem since it only provides guarantee for optimization error but not for generalization error. Even for optimization, MoDo has improved sample complexity; see **General Response-Q1**.\n\n>**Q2.** Does the proposed theory help improve PCGrad and CAGrad?\n\nGreat suggestion! We summarize 2 ways to improve PCGrad and CAGrad based on our theory.\n\n**1. Controlling the change of $\\lambda_t$ can improve generalization and achieve the best trade-off.**\nOur theory suggests, while dynamic weighting enables conflict avoidance, large drift of weights during update may degrade generalization. Thus, controlling this drift in PCGrad and CAGrad could improve their performance.\n\n**2. The theoretical framework for MOL is general, and can be used for other dynamic weighting methods including PCGrad and CAGrad.**\nE.g., for generalization, Propositions 2, 3 still hold. Since the stochastic implementations of PCGrad and CAGrad are sampling determined (Definition 3), the bound in the NC case (Theorem 1) holds. Combining the optimization and generalization error bounds, we can find better hyperparameters in PCGrad and CAGrad to minimize the test risks.\n\n---\nWe hope this can address your questions and raise the score. Thank you again!"}, {"review_id": "6I62bQZv37", "reviewer": "Reviewer_L3j5", "summary": "This work considers the multi-objective learning problem. The classic idea of dynamic weighting in MOL is to take gradients from each objective and to weight them using a fixed procedure to avoid conflicts between different objectives. Empirically, however, there often seems to be performance degradation when using these methods. They discover that this is due to a tradeoff between optimization, generalization, and conflict avoidance. They propose a new algorithm, MoDo, that interpolates between static weighting and dynamic weighting and find parameters that can control this tradeoff effectively.", "questions": "- Can you compare the theoretical tradeoffs in Table 1 with the empirical findings in Figure 4? How well do they match with each other?\n- How can knowledge of this three-way tradeoff be used to design better algorithms in multi-task learning in the future?\n- How can we tune the parameters in practice? How sensitive is the algorithm to the parameters?", "limitations": "Great!", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Overall, this is a strong work that provides a lot of insight into dynamic weighting in multi-objective optimization. The highlights are as follows:\n- The paper is very intuitively written and easy to follow. Specifically, the three-way tradeoff is clear both intuitively and quantitatively. In addition, Figures 1 and 2 are very well done and extremely insightful.\n- The proposed MoDo algorithm is very simple and intuitive while brilliantly highlighting the three-way tradeoff inherent in dynamic weighting algorithms. I found the remark about being in the early stopping regime for generalization error to diminish (T = o(n)) interesting, and it is also empirically highlighted later in the work.\n- The tradeoffs for both strongly convex and nonconvex cases are analyzed\n- The findings in this work translate to a practical explanation of the behavior of dynamic weighting algorithms", "weaknesses": "- While MoDo is a great theoretically inspired algorithm that controls the aforementioned tradeoffs, I am not sure how well it performs empirically. While there is an empirical result, the tasks seem rather simple. In addition, as Table 2 shows, MoDo does not consistently outperform MGDA. In practice, I feel handling the conflict avoidance tradeoff shouldn't matter much as long as the accuracy for the task is good. Therefore, I am not sure how applicable the algorithm would be in practical situations. \n- As the authors mention in their limitations section, the analysis is only about one specific algorithm in one specific setting, which makes it unclear how general the principles in this work would apply when the assumptions are relaxed. I feel this given this work is meant to analyze a practical phenomenon, this is a substantial weakness, as it is unlikely that Assumptions 1-3 are all true in real-world settings (such as the image classification setting the authors test on)\n- There is no intuition of the proof in the main text, and while this is common in optimization papers, it would be useful to learn about the key insights towards the proof.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for recognizing our work as a strong one! We will respond to the weaknesses and questions point by point as follows.\n\n> **W1.** Empirical benefit of MoDo. \n\nWe have more results in the submitted **Appendix D.2** to demonstrate its better performance on other datasets. Also see **General Response-Q2** for more results.\n\n> **W2.** Strong assumptions compared to practical phenomenon.\n\nIt is a **misunderstanding** that our theory requires ''Assumptions 1-3 are all true''. In fact, we only generally require smoothness of the functions (Assumption 1), and provide separate discussions for nonconvex case (under Assumptions 1 and 3), and the discussion for strongly convex case (under Assumptions 1 and 2) for both optimization and generalization.\n**These assumptions are standard in prior optimization analysis [8,25,47].**\nThe general smooth non-convex case covers a lot of practical problems such as using neural networks with ELU activation functions. And the strongly convex smooth case covers, e.g., the linear fine-tuning problem with l2-norm regularizer.\n\n> **W3.** No intuition of the proof in the main text.\n\nDue to space limitation, we defer the intuition of the proof to the Appendix in each section.\nThe key insights of the proof are summarized as follows.\n\n1. For **generalization**, the key is to use the error of the algorithm output resulting from perturbation of training data (stability) to bound the expected difference of performance on the testing and training data (generalization). Then using the property of stochastic sampling and the update function, the expected error of the current iteration caused by the dataset perturbation can be bounded recursively by a linear function of that of the previous iteration.\nSee also **Summary of Theoretical Contributions-T2**.\n2. For **optimization**, the key is to use the descent Lemma derived from smoothness of the functions, which shows the function value approximately decreases after each update, with an approximation error caused by the dynamically changing weight. Then we are able to bound this approximation error using the property of the update of the dynamic weight based on the convexity of the subproblem.\nSee also **Summary of Theoretical Contributions-T3**.\n\n> **Q1.** Comparison of Table 1 and Figure 4.\n\nYes, we have discussions and comparisons in Section 5.2; see line 313-329 in the main text. Since Figure 4 corresponds to the general nonconvex case, it matches the result described in Table 1, line 1 for the nonconvex (NC) case. \n\n> **Q2.** How can knowledge of this three-way tradeoff be used to design better algorithms in multi-task learning in the future?\n\nAs discussed in Section 3.3, Appendix D.1.2 in our paper, our theory (Theorems 1,2) suggests that, when chosing dynamic weighting at each iteration, it is better that **the drift of the dynamic weights is not large across iterations**, to ensure better test performance. \n\nIf the dynamic weights are iteratively updated, this can ensured by \n- having appropriately small learning rate for the dynamic weights;\n- do not update dynamic weight at each iteration, but rather update the dynamic weight only when there are conflicts in gradients.\n\n> **Q3.** How can we tune the parameters in practice? How sensitive is the algorithm to the parameters?\n\nWe have included hyperparameter choice and sensitivity analysis in **Appendix D**. In practice, $T$ should not be too large to ensure good generalization performance. $\\alpha, \\gamma$ depend on the choice of $T$. For example, $\\alpha = \\mathcal{O} (T^{-\\frac{1}{2}})$ works well, and a relatively small $\\gamma$ works well in practice. Furthermore, overall performance of the algorithm is mostly sensitive to iterate step size $\\alpha$, while individual task-trade offs are mostly sensitive to dynamic weighting step size $\\gamma$.\n\n---\nWe hope that our responses to your comments are satisfactory. Thank you again!"}, {"review_id": "16w26CfubN", "reviewer": "Reviewer_UWFs", "summary": "This paper has two contributions:\n(1) MoDo algorithm which is a variant of MGDA with a double sampling to obtain an unbiased stochastic estimate of the gradient problem.\n(2) A solid theoretically analysis on the error of multi-objective optimization.\n", "questions": "Could you summarize and simply explain the advantages of MoDo over MGDA here, smaller error or more efficient?\n\nWhy MoDo has an unbiased gradient estimation? line 142", "limitations": "Authors only discuss the situation of using Pareto optimal to get the aggregated gradient.\nHowever, there are other methods other than Pareto to balance multi-objective optimization like balancing gradient magnitudes like AdaTask, GradNorm.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper has a very detailed analysis on the optimization error and generalization error of multi-objective optimization.", "weaknesses": "In the experiments, authors only compare MoDo with MGDA, but there are many other algorithms, like CAGrad, GradNorm, Uncertainty Weight. This baseline is not enough to demonstrate the effectiveness of the proposed method.\n\nOverall, MoDo is better than MGDA. However, in two objectives out of three (table 2), MGDA is better than MoDo, also not convincing enough on the effectiveness of the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for acknowledging the strengths of our work. Our point-to-point response to your comments and suggestions follows next.\n\n>**W1.** In the experiments, authors only compare MoDo with MGDA, but there are many other algorithms, like CAGrad, GradNorm, Uncertainty Weight. This baseline is not enough to demonstrate the effectiveness of the proposed method.\n\nSee response to **General Response-Q2**.\n\n>**W2.** Overall, MoDo is better than MGDA. However, in two objectives out of three (table 2), MGDA is better than MoDo, but also not convincing enough on the effectiveness of the proposed method.\n\n1. This may be a **misinterpretation** of the results for the following two reasons.\nThis phenomenon is mainly due to trade-offs among different tasks. In the simulation, the loss values of DSLR and Webcam are smaller than that of Amazon. Therefore, MGDA tends to favor these tasks compared to Amazon, leading to significantly worse performance of MGDA on Amazon. This calls for a more holistic measure -- the average performance degradation of the method compared to single-task learners (last column of Table 2). It can be seen that MoDo clearly outperforms MGDA with regard to this measure. Thus, we believe that the bias of MGDA towards some tasks compared to MoDo in Table 2 does not indicate a lack of effectiveness of MoDo, but rather a limitation of MGDA.\n2. More results in **Appendix D.2 and General Response-Q2** demonstrate the effectiveness of MoDo over MGDA.\n\n>**Q1.** Could you summarize and simply explain the advantages of MoDo over MGDA here, smaller error or more efficient?\n\n**MoDo has advantages than MGDA in both smaller optimization error and better efficiency** because:\n1) **MoDo is better than the full-batch MGDA in efficiency**, as it does not require computing the full-batch gradients at each iteration but only stochastic estimates of the gradients.\n2) **MoDo smaller optimization error theoretically than the vanilla stochastic version of MGDA**, as the latter is not guaranteed to converge to Pareto stationarity as proved in [47, Theorem 1] while MoDo does.\n\n>**Q2.** Why MoDo has an unbiased gradient estimation? line 142\n\nThis is because if we take expectation w.r.t. stochastic samples of the update over $\\lambda_ t$ in (6a), which is $\\mathbb{E}_ {z_ {t,1}, z_ {t,2}}[\\nabla F_ {z_ {t,1}}(x_ t)^ \\top \\nabla F_ {z_ {t,2}}(x_ t)\\lambda_ t] = \\nabla F_ S(x_ t)^ \\top \\nabla F_ S(x_ t)\\lambda_ t$, equal to the full batch gradient of problem (4b). See also **General Response-Q3**.\n\n\n>Limitations. Authors only discuss the situation of using Pareto optimal to get the aggregated gradient. However, there are other methods other than Pareto to balance multi-objective optimization like balancing gradient magnitudes like AdaTask, GradNorm.\n\nWe will include more discussion of AdaTask, GradNorm [4] in the related works section. See also the new empirical comparison in **General Response-Q2**.\n\nWe hope that our responses have addressed your questions. Thank you again!"}]

Author rebuttal:
## General Response

We appreciate the reviewers' constructive comments. All reviewers agree the paper has made solid theoretical contributions, and it has "a bigger picture" concerning three types of errors -- optimization, generalization, and CA distance unique in MOL in a holistic framework. It also provides the first algorithm stability-based generalization bound for MOL.

Despite this, we want to re-emphasize that **our standpoint is not a new algorithm that improves over SOTA MOL algorithms**. Instead, we propose a framework for theoretical comparisons of stochastic MGDA and static weighting, complementing to the recent empirical studies [15,40] in NeurIPS 2022; see our **"Summary of Theoretical Contributions"** in the separate thread below.

The reason we use **MoDo as a stochastic variant of MGDA** is that it
- is the simplest possible unbiased stochastic variant of MGDA (as vanilla mini-batch MGDA does not converge) which has theoretical guarantees (with better rates or relaxed assumptions than [8,26,47]);
- interpolates between static and dynamic weighting, thus flexibly controlling the trade-off, which cannot be achieved by existing methods [24,25,36,44].
 


 Below we address three major questions from the initial reviews.

>**Q1. The benefit of MoDo in sample efficiency or error. (Reviewers LuAm, UWFs)**

Regarding the benefit, **MoDo does have benefit in terms of theoretical guarantee of sample efficiency  and  test risk**, which we explain below.

1. **In terms of sample efficiency, the overall sample complexity of MoDo could be better than other MOO variants.** Although MoDo requires computing 3 independent stochastic gradients at each iteration, it does not necessarily harm the total sample efficiency as questioned by Reviewer LuAm. This is because the **convergence rate of MoDo is faster under the same assumptions**; see the Table below. When the bounded function values assumption is removed, MoDo achieves $\mathcal{O} (\epsilon^{-2})$, significantly improving MoCo with $\mathcal{O}(\epsilon^{-10})$. 
The overall sample complexity is:  

``` 
(number of iterations T) X (number of samples per iteration n') = Tn'.
```

Since MoDo improves the number of iterations $T$ to achieve small optimization error, it could improve the overall sample complexity $T\times n'$ when $T$ dominates.

|Algorithm|Assume bounded function values|Sample complexity
|---|---|---|
|CR-MOGM [47, Theorem 3]|Yes|${\cal O} (\epsilon^{-2})$
|MoCo [8, Theorem 2]|No|${\cal O} (\epsilon^{-10})$
|MoCo [8, Theorem 4]|Yes|${\cal O} (\epsilon^{-2})$
|MoDo (Ours, Theorem 3)|No|${\cal O} (\epsilon^{-2})$

2. **In terms of test risk, MoDo has theoretical guarantee of the generalization error, thus the total test risk**, but the generalization error guarantees of MGDA, MoCo and CR-MOGM are unknown or at least not established. 

>**Q2. Limited empirical evaluation or recent benchmarks. (Reviewers LuAm, UWFs, L3j5)**

1. **Misunderstanding of our key contributions.** It is worth mentioning again that **we do not claim that MoDo works better than the SOTA algorithms on multi-task learning**. Therefore, it is not our main target to demonstrate MoDo performs better than SOTA algorithms for MTL.

2. **Reasons for current baselines.** We choose static weighting as an important baseline because it has been demonstrated in recent works [15, 40] that on many tasks, static weighting outperforms the recent MOL-based algorithms such as PCGrad and CAGrad.

3. **Other benchmarks as per reviewers' requests.** We compare to PCGrad, CAGrad, and MoCo, etc. following the experimental settings in [arxiv:2111.10603]. Results are summarized in the **attached PDF, Tables 1-3** and will be included in the revision. The results show that MoDo performance is comparable or better to these baselines.

>**Q3. Why use double sampling, how it mitigates gradient bias (Reviewers LuAm, UWFs)**

The **CA distance or gradient bias** can be mitigated since MoDo uses **double/independent sampling** for update. Specifically, taking expectation w.r.t. stochastic samples of the update over $\lambda_t$ in (6a) leads to
$$\mathbb{E}_ {z_ {t,1}, z_ {t,2}}[\nabla F_ {z_ {t,1}}(x_ t)^\top \nabla F_ {z_ {t,2}}(x_ t)\lambda_ t] = 
\mathbb{E}_ {z_ {t,1}}[\nabla F_ {z_{t,1}}(x_ t)]^\top \mathbb{E}_ {z_ {t,2}}[\nabla F_ {z_{t,2}}(x_ t)]\lambda_ t = \nabla F_S(x_t)^\top \nabla F_S(x_t)\lambda_t,$$
which is equal to the full batch gradient of problem (4b). This allows us to derive the convergence of distance to CA direction in Lemma 2 using the stochastic optimization framework.

However, if we use the same sample for $z_ {t,1}$ and $z_ {t,2}$, this equality does not hold, i.e., 
$$\mathbb{E}_ z[\nabla F_ z(x_ t)^\top \nabla F_ z(x_ t)\lambda_ t] \neq \nabla F_S(x_ t)^\top \nabla F_ S(x_ t)\lambda_ t.$$
As a consequence, the distance to CA direction cannot be reduced due to this bias.

We would like to make the most use of the interactive discussion function provided by Openreview to clarify any concern the reviewers may have. We look forward to the rolling dicussion and further engagement with the reviewers and area chair!

Sincerely,

Authors

Meta-review: The manuscript investigates multi-objective optimization with a particular emphasis on stability analysis. The work ultimately unveils a three-way tradeoff between optimization error, generalization error, and the conflict-avoidance. Empirical studies complement the theoretical results. The paper was reviewed thoroughly with a committee and the consensus recommended acceptance. The reviewer recommending rejection raised some valid concerns. After reading the paper as well as the reviews/rebuttal carefully, I agree with the consensus. However, I also recommend authors to improve their manuscript with the following aspects:
- Even if the empirical study covering other methods like PCGrad, CAGrad, GradNorm,... is not necessary, at least discussion on the implication of the theoretical results for these methods would be beneficial.
- There were unclear parts about the theory which authors successfully clarified during rebuttal. These clarifications need to be reflected in the camera-ready version.
Decision: Accept (poster)