FERERO: A Flexible Framework for Preference-Guided Multi-Objective Learning
Authors: Lisha Chen
A F M Saif
Yanning Shen
Tianyi Chen
Venue: NeurIPS 2024 poster (2024)
Keywords: Multi-objective Learning; Preference-Guided Learning; Constrained Vector Optimization
Primary area: optimization
TL;DR: We cast preference-guided multi-objective learning as a constrained vector optimization problem to capture flexible preferences, under which provably convergent algorithms are developed.

Abstract: Finding specific preference-guided Pareto solutions that represent different trade-offs among multiple objectives is critical yet challenging in multi-objective problems. 
Existing methods are restrictive in preference definitions and/or their theoretical guarantees.
In this work, we introduce a Flexible framEwork for pREfeRence-guided multi-Objective learning (**FERERO**) by casting it as a constrained vector optimization problem.
Specifically, two types of preferences are incorporated into this formulation -- the *relative preference* defined by the partial ordering induced by a polyhedral cone, and the *absolute preference* defined by constraints that are linear functions of the objectives. 
To solve this problem, convergent algorithms are developed with both single-loop and stochastic variants. 
Notably, this is the *first single-loop primal algorithm* for constrained optimization to our knowledge. 
The proposed algorithms adaptively adjust to both constraint and objective values, eliminating the need to solve different subproblems at different stages of constraint satisfaction. 
Experiments on multiple benchmarks demonstrate the proposed method is very competitive in finding preference-guided optimal solutions.
Code is available at https://github.com/lisha-chen/FERERO/.

FERERO: A Flexible Framework for Preierence-Guided Multi-Objective Learning
Lisha Chen', AFM Saif',
Yanning Shen', Tianyi Chen
Rensselaer Polytechnic Institute, University of California, Irvine
Abstract
Finding specific preference-guidee Pareto solutions that represent different trade- offs among multiple objectives is critical yet challenging in multi-objective prob- lems. Existing methods are restrictive in preference definitions and/or their theoret- ical guarantees. In this work, we introduce a Flexible framEwork for pREfeRence- guided multi- culti-OObeectvee learning (FERERO) by casting optimization problem. Specifically, two types of preferences are incorporated into this formulation the relative preference defined by the partial ordering induced by polyhedral cone, and the absolute preference defined by constraints that are linear functions of the objectives. To solve this problem, convergent algorithms are developed with both single-loop and stochastic variants. Notably, this is the first single-loop primal algorithm for constrained optimization to our knowledge. The proposed algorithms adaptively adjust to both constraint and objective values, eliminating the need to solve different subproblems at different stages of con- straint satisfaction. Experiments on multiple benchmarks demonstrate the proposed method is very competitive in finding sefterenne-guiderr optimal solutions. Code is available https: / github..... com/lismhiiie 1ishhaishhaaeeeeee chen/FERERO/.
constrained vector
Introduction
Many machine learning tasks inherently involve multiple objectives, which can be different perfor- mance metrics such as accuracy, fairnsss, and privacy; or, the same metrics defined different data [52, 42). To tackle such multi-objective problems, it is common to learn a shared model that simultaneously performs well on all the objectives. Compared to learning one model for each objec- tive, learning a shared model has the benefit of reducing both the model size and the inference time. This can be achieved through multi-objective optimization [52, 59, 35], which minimizes the vector-valued objective. In practical applications, it is of interest to learn solutions with controlled trade-offs or preferences. To further illustrate, we give two examples below.
learn model that
In fairness- aware machine learning, a trade-off exists between the faimess flair (f) and accuracy (f) [42, 37], see also Figure la. With 0 denoting the model parameter, and C denoting the partial order cone, to find the optimal models that consider different trade-offs, one can solve the following problem with different thresholds [9]
maximize: (0nrc(0), Stair (0)) S.I. Stair (fair(0) 2
(1.1)
Another example is in drug molecule design, where the goal is to design drugs molecules with multiple desired properties (0), fz())... fai (6). Aiming to align the values of the properties F(0) with predefined preference vector in Figure 1b, one can solve the following problem [40, 1, 61]
maximizeg F(0) (0) (N)) s.t. BF(0) Bv, Bu
(1.2)
where B E IR (M-1)) is full row rank.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table 1: Comparison to existing methods. "Flexibilityy represents preference modeling, such as by using weights, preference vectors (rays), or constraints. "Exactness" represents the ability to align with preference vector exactly. "Deter." "Stoch." " represent deterministic and stochastic, respectively. "x" means not provided in the corresponding work, and "-" means not relevant.
Preference
Controlled
Single loop
Convergence
Method
Flexibility
Exactness
Deter.
Stoch.
Linear Scalarization
weight weight
T non-asy non-asymplotic asymptotic
(Smooth) Tehehycheff [32]
PMTL [33]
incqualities (absolute)
EPO
ray (ratio, absolute)
asymptotic
(X)WC-MGDA MGDA [44]
shifted ray (absolute)
FERERO (ours)
relative absolute
7
Then natural question arises:
face
f2
preference vector
Can we develop
Pureto
principled framework to capture flexible preferences and admit provably convergent deterministic and stochastic algorithms?
foir
f
(b) Figure 1: Illustration of preferences in different ex- amples. The solid red curves represent the Pareto front, dashed lines represent preference constraints.
Our answer to this question is affirmative. Rec- ognizing that all the aforementioned applica- tions can be addressed within unified frame- work, we formulate preference-guidee multi-objective learning (PMOL) as constrained vector optimization problem. Specifically, given a model IRS, and the objectives fm IR9 R, m 1.
M, we define the constrained vector optimization problem
min F(0) BERY
s.t. G(0) S 0, (0)))
(PMOL)
where G(O) and (0) are the vector-valued preference constraints such as the examples in (1.1) and (1.2). Here "<" and "=" are element wise relations on the vectors, with each row representing one constraint. In these examples, the preferences directly defined in the objective space, as intersections half-spaces defined by the hyperplanes; see Figure 1. Thus, G(-) and (-) in (PMOL) can be expressed linear functions of F()). given by
G(0) = (0) + by. H()) F(0 bn.
(1.3)
where Bg E M,MM BA E MMM and by E RM,, by E RM,, Different Bg Bn by by corre- spond to different preferences, and thus different trade-offs among the objectives.
comparison of our methods to existing methods summarized in Table Specifically, our contributions are listed as follows:
C1) We cast the PMOL problem as a constrained vector optimization problem, and develop the FERERO framework to capture flexible preferences.
C2) Under the FERERO framework, we develop a meta primal algorithm with a unified subpro- gram adaptive both objectives and constraints to meet flexible preferences, eliminating the need for multiple subprograms under different active constraints.
C3) Under the FERERO framework, we develop a practical single-loop algorithm with non- asymptotic convergence guarantees. To our best knowledge, this is the first single-loop primal algorithm in constrained vector optimization with convergence guarantees.
C4) We apply the proposed algorithms various synthetic and real-world image and speech datasets to demonstrate its ability to find flexible preference-guides optimal models.
In our theoretical analysis, address the following technical challenges.
T1) The commonly used constraint qualification assumptions do not generally hold for the PMOL problem. We overcome this challenge by leveraging the specific structure that the constraints are linear functions of F to prove the calmness condition holds for PMOL. See more details in Lemma 2.
T2) The convergence of the single-loop algorithm is slower with the commonly-used merit functions. We provide sharper analysis by introducing a different merit/l yapunov function and exploiting the algorithm properties under additional assumptions. See Theorem 3.

---

T3) The convergence analysis often relies on assumptions on bounded functions or bounded constraints. We remove such assumptions by applying similar techniques in [7] with proper choice of Lyapunov functions, and exploiting algorithm properties. See Theorems 2 and 3.
2 Problem Setup and A Meta Algorithm
To characterize the optimality conditions of PMOL, we introduce the generalized notion of dominance and the related concept of optimality. We then present meta-algorithm to solve PMOL.
2.1 Problem setup and preliminaries
f2
We first introduce optimality definitions for PMOL that go beyond the standard definitions of Pareto optimality [15. 11, 36). Given two vectors and w, we use v < w and v S w to denote U/ < wy for all i, and i/ S wt for all i, respectively. We use v $ to denote v S w and v # w. and define >, Z analogously.
Pureto front
h
(a)
(b)
Figure Illustration of Ca-dominance. The solid red curves are the Pareto fronts, green dots are the reference points, gray shaded regions are the set of objectives dominating the reference points, under different C^ in (a) and (b).
Definition 1 (Ca-dominance [12, 27]). Given V. W E RR MMM A E RMXM, and CA == {y E RM Ay 2 0} # 0, we say strictly domi- nates w based on CA if and only if A(E w) < 0.
The generalized dominance defines a partial order on RM. i..., the relation between two vectors. Illustrations of different partial orders are given in Figure 2. Figure 2a shows the dominance relation under the widely used non-negative orthant cone with CA R corresponding to Pareto optimality. However, as illustrated by the figure, given the initial green reference point, a descent method such as MGDA [15] cannot find points on the Pareto front but outside the gray shaded region. This poses a critical challenge for applications where specific sefference-guided solutions on the Pareto front are needed. Nevertheless, this issue can addressed by substituting R. with a more general definition of CA displayed in Figure 2b. Under this partial order, a general descent method is able to reach any points on the Pareto front starting from the green reference point.
Based on the partial order, one can then find the minimum or optimal elements in the vector-valued objective space, whose formal definition is provided below.
Definition (CA-optimal), A point 0 RS is CA-optimal if there is no 0' + 0 such that, AF(0') $ (F A point 0 is weakly CA- opttiia if there is no 6' o 0 such that, AF(0') ) < (F))
Note that, CA is a polyhedral cone, or the intersection of half-spaces defined by the rows of the inequality Ay 2 O. When A = IM. an M x M identity matrix, Ca R := {g E R.M ym 2 O Vm [M] then Definition reduces the commonly used notion of dominance associated with Pareto optimality. The cone CA can be interpreted as a relative preference that defines the objectives' improvement directions, which generalizes the relative preference defined by R. In contrast, the preference defined by constraints in (1.3) can be interpreted as an absolute preference that defines the feasible or preferred set of objective function values. In practice, CA be chosen based on the requirements of specific applications. For example, when the controlled ascent of objectives is needed [41], we can choose CA such that the controlled ascent direction belongs to -CA- We defer the detailed implementation to Section 3.2. The CA-optimal set, denoted as PA, contains all the Cottmml models. When A IM. PA the Pareto optimal set P. The Pareto front the set of function values evaluated at Pareto optimal models, i.c., F (F(() 1 E P).
We make the following standard assumptions throughout the paper [15, 25,
Assumption 1. I. (Non-negative objectives) AF(0) 2 O. and 1 AF(()) 2 CAF > 0 for all A E R2, (Differentiable objectives) F is twice continuously differentiable.
3. (Ordering cone with non-emply interior) CA has a non-empty interior.
2.2 Find the preference-guided direction
In this section, we proceed to discuss an adaptive method to solve (PMOL). At iteration 4, the algorithm finds an update direction d, and performs the iterative update 0 0e + and, with a step size ay. Idcally, the update direction d, is chosen improve the objective F(0) and to satisfy
3

---

the preference constraints. It is desirable that when the constraints are not satisfied, d, decreases the violation of constraints and improves the objectives in the general partial ordering sense; when the constraints are satisfied, de improves the objectives and ensures the constraints are satisfied. To achieve this, we find a direction d' d0) that solves following subprogram
1 Illalp s.t. AVF(O) AAF(O) (0) == min c+ (d,c) xR 2
AF
(2.1)
VG VG(()Td+c,Gil) S O, VH( (,,
where || |. denotes the f2-norm, Cg and O are pre-defined positive constants. Larger Cg and C put more emphasis constraint satisfaction than objective improvement. We call this subprogram adaptive since it deals with constraints in an adaptive way, which does not require the initial model to be feasible, nor Oe be feasible at each iteration. But rather, it finds update direction that decreases the constraint violation. Because of this, it neither requires solving different subprograms at different stages nor requires different treatment of the active set of inequalities as in existing works [33, 41, 44].
We then show in Lemma I that the desired properties can be satisfied.
Algorithm 1 A meta FERERO algorithm
1: Initialize ( = 0, Oo. step size {ar}: define A. while (=.) o 0 do
Lemma 1. For the subprogram (2.1), the
2:
following holds:
3:
Compute gradient (F();):
If B is a local optimal solution with
4:
Compute de by (approximately) solving (2.3);
AF(0)= > O, then (0) = O, (0)) O. Otherwise, if is not a local optimal solu- tion, then d' (0) # 0, vb()) < O, and when 0 is feasible,
5:
Compute the update direction
6:
de -
7: Update 0g by 0s+1 = 0: + aade;
Set +1
(2.2) Let 9 be a weak C opttiiall solution, with
2x)(0) S -Idd (0) < O.
9: end while
(AF(0)) m 0. 0.ror some m [M.). If there exists feasible and non-strictly improving directions 0 with (V) d 0, then d' (0) * 0, (0) < O. Otherwise, d' d0) 0. (00) = O.
By Lemma 1, (0) = is a stationary condition for PMOL. Recall the feasibility condition requires [G())] = 0 and (0)lab 0, where [:]_ and la are entry-wise ReLU and absolute functions, respectively. And the complementary slackness condition requires X; [+]]+ =
Thus (0)] +
+ ||./1 (0)ll achieves zero if and only if the model 0 satisfies the first-order KKT condition. Besides the properties in Lemma 1, it has an additional scale-invariant property that is deferred to Lemma 6 due to space limit.
[[] [-G(0]+
By the Lagrangian of (2.1), 1), the optimal update direction can be expressed in a simple form as a weighted combination of the gradients, i.e. d" dt) = - F (g X*, with Aag = [A; Bg: B,), and
1 T 2
X E arg min c(\; 0) = |VF(O) - Cg G()) c, H (e
(2.3) (
where A= = (Ay; Ag: An). (0) is the domain of the Lagrangian multipliers, given by
(0) = (0) x R x IR MR, with sx (0) = (> E M X AF = AF(()) (2.4)
Our goal is to design an algorithm that converges to a KKT solution based on 1). However, the KKT condition is not necessary unless certain constraint qualifications (CQs) hold. Prior works [20, 33] assume certain CQs hold, e.g.. the Linear Independence Constraint Qualification (LICQ). However, the LICQ assumption (c.f., [20, Section 3. (A2))) does not generally hold at local optimal solution for problem (PMOL), c.f., Example in Appendix D.3.2. Though some commonly used CQs do not hold generally, in our case, leveraging the specific structure that the constraints are linear functions of F, we can justify the calmness CQ in Definition 10 tailored for our problem in Lemma 2, thus the KKT condition is necessary optimality condition. The proof is deferred to Appendix D.3.2.
Note that, our formulation and analysis cover the constrained MOO problem with simplified subprogram. where Ul A which is detailed in Remark 4 in Appendix D.I.

---

Lemma 2. Let 0 E R2 be global solution to (PMOL). Define Σ(p.g) == E Bgy + by S p. B,y + by q}. If Ep. 9) line, the PMOL calmness condition in Definition 10 satisfied for (PMOL) at 0 if A E RM is full rank, H (0), G(O) defined by (1.3) satisfy [ B + and Bn, By are full row rank. Consequently, the KKT condition is necessary optimality condition.
Lemma 2 provides sufficient condition for the KKT condition to be necessary optimality condition without relying on unjustified assumptions. The requirement that the constraint set is line in the objective space is common for applications such as alignment to preference vector.
We then discuss generic preference-guie guided multi-objective algorithm based on the subprogram.
2.3 A meta algorithm for preference-guided multi-objective learning
Given the model 0r at iteration t. one can then solve (2.3) to obtain A The direction de = -VF(O))AA used update the model Og by 0r+1 = 0, + ard, iteratively until convergence. The full procedure of this meta algorithm is summarized in Algorithm 1, where Step 4 is a generic step and can be customized in Section
To establish the non-asymptotic convergence rate, we use the following standard smoothness assump- tion that has been commonly used in prior works for multi-objective learning [7, 36]. Assumption (Smooth objectives). For all m [M], fm (0) is f Liiischhh continuous.
We then state the convergence result for Algorithm
Theorem 1.
Theorem 1 (Convergence of the generic FERERO algorithm). Suppose Assumptions 1, 2 hold. Let {0r} be the sequences produced by Algorithm 1, with d, being e-optimal solution to the subprogram (2.1). (f11""00)) S cx. 04 S min[ extra Isx. . ,.hh and a₁ O(1), then
( + (3) |- C(O.)) + [|[(O)))+| + [H = O(T +c). (2.5)
stathonaiity
complementury flocknezs
feauiiitity
Theorem guarantees the non-asymptotic convergence for the generic FERERO algorithm. In Algorithm 1, A can be solved through projected gradient descent or Frank Wolfe algorithm iteratively within an inner loop. practice, we usually do not need solve the subprogram exactly. Next, we discuss the efficient single-loop approximate algorithm based on Algorithm 1.
Efficient Single-loop Algorithms
Algorithm 2 FERERO-SA
In this section, we first discuss algorithm devel- opment with the approximate single-loop update and practical choice of preferences. We focus on (PMOL) with equality constraints only, i.e., M, = 0. Building upon this, we then discuss the stochastic variants of the algorithms that can be applied to large-scale learning problems.
1: Initialize O, Go. λo step sizes {ar: :e): define A. number of iterations T.
2: for = 0 O,...,
do Compute gradient VF(O:);
3:
4:
Compute direction d, (F(())
5:
Update O, by 0.+1 O, + ardy;
6: Update X, by (3.1);
7:
end for
3.1 Single-loop approximate algorithm
In practice, if one only requires the converging solutions generated by the algorithm to be feasible, but not all the iterates, then further approximations can be made to the subprogram (2.3). iteration f, to obtain an approximate direction d,, we adopt the following update
Ae+1 Ua, (A+ 7h V (Ax 0.))-
(3.1)
The single-loop algorithm with the approximate solution is summarized in Algorithm 2. We name FERERO with Single-loop Approximate update (FERERO-SA, algorithm.
We make the following additional assumption of Lipschitz objectives to prove the convergence of Algorithm 2, which is standard in optimization literature.
Assumption 3 (Lipschitz objectives). For all m [M), fma (0) is e Lipschhtt continuous.
5

---

To prove the convergence of Algorithm 2, we can use the same merit function with & norm of H (0,), which leads to slow convergence rate of (T- &). See Theorem 2 below and its proof in Appendix F.2, where the proof follows similar ideas of the proof's of Theorem 3 and Theorem [7].
Theorem 2 (Convergence of the FERERO-SA algorithm). Suppose Assumptions 2, hold, and Mg 0. Let {6r} ), {de) be the sequences produced by Algorithm with = I and 92,, (0) = = A (c.f. Remark 4). Assume Xe, (0t)), and (0a) = arg min ((>; 0z) + & || are bounded.
With property chosen step sizes a 6 8). ( )). and hyperparaameters, it holds that
T
[F((0) Arl2 + (H( 1= 8)
(3.2)
T t=
To obtain a sharper convergence rate, we consider a different merit function with E--norm of the constraint (6:), and under additional assumptions listed below.
Definition (Proximal PL inequality). Define D ();r();)))) == - minyea, {(V (Vxp(>;))) X - A)
2 IX }/ We say (0\;; 0) satisfies the prx-prxiimal PL inequality on the point (X, if there exists some constant Mip 0 such that (x,,(>;)) 2 Mhp (p({;;
(0\ (0); 0)).
Assumption 4. For 0 {0t), X E {Dr} on the trajectory of Algorithm 2, the following hold:
1. ((; 0) is pep-prxiiaal PL. in Definition 3;
2. For all m E [M]. fm (0) is f,2--Lipchhin continuous.
Assumption 4-1 essentially requires some regularity conditions of (p=; 0) on the trajectory of Algo- rithm 2. Leveraging the fact that cp(: f) is convex, has been discussed in e.g., [28, Appendix B] that if the smallest non-zerv singular value of the Hessian is bounded away from zero, then Assumption 4-1 holds. This could be satisfied when the gradients F(O))) have lower- wourddo non-zer non-zero singular values on the trajectory. A more detailed analysis of the sufficient conditions for Assumption 4-1 to hold is left for furture work.
We then provide a sharper convergence analysis in Theorem 3. The detailed proof and choices of step sizes and hyperparameters are deferred Appendix F.3.
Theorem 3 (Sharper convergence of the FERERO-SA algorithm). Suppose Assumptions 1, 2, 3, 4 hold, and My = O. Let {0t), {de} be the sequences produced by Algorithm 2 with A I and l2, A M (c.f. Remark 4). With properly chosen step sizes ag @(1), 7t @()), and hyperpurameters, it holds that
T Σ IVF(O)) +1H(00011 o(-)).
(3.3)
Theorem 3 states that (0c) produced by Algorithm converges to a KKT solution of the PMOL problem in the general nonconvex case. Moreover, both ||d,]| and || (0.))l converge to zero at both the objective values and the preference constraints. Note that, the convergence in terms of || (0.) 2 at rate of O(T-1) is weaker compared to the one with [ (0.)ll at the same rate for Algorithm This is reasonable since Algorithm 2 only uses a one-step approximate update of X instead of exactly solving the subprogram.
rate (TT-1), implying the convergence
The stochastic variant. We employ stochastic variant of Algorithm based on the double sampling techniques developed in the recent work [7]. The update is given by
0.t1 =0, + V F Alg
(3.4a)
Aet1 -I,, (A. 7t V Ap((;;;
(3.4b)
Axp(Ar; AAg
V V (0.) V (0.) - [0 cc, He, [I.
(3.4c)
where & the unbiased stochastic estimate of the gradient, and ε,, and E.2 are two independent stochastic samples obtained at iteration t.

---

The full description of the stochastic algorithm and its convergence guarantee are deferred to Ap- pendix G. We provide a converegnce rate guarantee that matches the rate of SGD under additional assumptions on the bounded variance of the stochastic gradients.
3.2 Choice of relative preferences
As briefly discussed in Section 2.1, the ordering cone and the corresponding matrix can be specified according to practical needs. We first discuss how to obtain matrix A for the relative preference given the set of improvement directions. Then we discuss how to choose the relative preference to allow controlled ascent update, which is useful for touring the Pareto front [41].
Ordering cone generation. In practice, obtain the polyhedral cone that defines the partial order, one can usually first define the extreme rays of the polyhedral cone. We then show how to convert the extreme ray description of the cone to the half-space description given by matrix A, i.e., Ay 2 0}. by showing how to compute A from the extreme rays.
CA = ( E R
Let = y/ ........ -M E R MRMx be matrix that contains all the extreme rays of Ca as its column vectors, then CA [Y>] X 2 0}. Let a RIXM denote the row vectors of A for all E [M]. Then all Om can be found by a that solves the following linear feasibility program
find 4,20
s.t. Y c, c'a=0, 0, a
(3.5)
Choice of CA for controlled ascent. If CA is not pre-specified, and the decision maker wants to choose CA to allow controlled ascent, it can be achieved with the following procedure. Let Fo F F(o)) be the objective of the initial iterate of the algorithm, and Fig be the target function value along the controlled ascent direction. To ensure Pig Fo E -CA for controlled ascent, we include (Fo- /tg)/
Figll in the set of extreme rays, then take the extreme rays of the convex hull of the new set to form the columns of Y. Finally, we obtain CA by solving (3.5).
Related Works
To put our work in context, we review the most relevant literature in (preference guideed) multi- objective optimization, constrained optimization, with focus gradient-batt based approaches.
Multi-objective optimization (MOO). A straightforward approach of MOO is to use scalarization to transform MOO into a single-objective optimization problem [43]. Another popular approach focuses on finding update directions which avoid conflicts with the gradients of the objectives [52, 59, 35]. A foundational algorithm in this domain is the Multiple Gradient Descent Algorithm (MGDA) [15, 17, 11, 36), which dynamically weights gradients to find a steepest common descent direction for all objectives. Later on, variants of MGDA are developed, which are discussed in detail in Appendix B.1 and [7]. However, solutions based on MGDA usually cannot capture pre-defined user preferences that represent various trade-offs the Pareto front. This motivates the development of preference-guie guided multi mujti-objecttvv optimization methods.
Preferences can be modeled through weights or thresholds assigned to different objectives [43]. For example, scalarization- based methods use the t--norm of the weighted vector-valued objective to convert the vector-valued objective into ccalar-valued objective, e.g., Linear scalarization (LS), Tehebycheff scalarization; see e.g.. [32]. Then the problem can be solved by single-objective optimization on the scalar objective. The e-constraint methods enforce threshold constraints on different objectives, then solve the problem by constrained optimization; see e.g., [9]. More recently, preferences have been modeled by preference vectors defined in the objective space. Then the problem can be formulated as finding Pareto optimal solutions satisfying the constraints defined by the preference vectors [33], or optimizing the distance to the preference vectors [41, 44]. The key difference between FERERO and these works is that FERERO can capture more flexible preferences based on general partial order, and general incquality/equality constraints. Moreover, we provide convergence rate guarantees for the proposed algorithms. A detailed comparison is summarized in Table 1 in Section and Table 5 in Appendix B.2.
Constrained optimization. Constrained optimization methods include primal methods, penalty and barrier methods, and primal-dual methods [4, 39]. Our proposed method is related to the primal method that finds an update direction to ensure the models are feasible and improving along the optimization trajectory. To address the limitation that it usually requires a stage-one procedure to
7

---

2.6
(a) LS
(b) MGDA
(c) PMTL
(d) EPO
(e) FERERO
(1) FERERO
Figure 3: Converging solutions (blue dots) and optimization trajectories (blue lines) on the objective
space of different methods on synthetic objectives given in (5.1). Dashed arrows represent pre- specified preference vectors. The green dots represent initial objective values.
(a) PMTL
(b) EPO
(c) FERERO
(d) PMTL
(e) EPO
(I) FERERO
Figure 4: Outputs (colored markers) and optimization trajectories (colored lines) of different methods when initial objectives are near the Pareto front. Different colors represent different preferences.
ensure the initialization is feasible, we use an adaptive approach to ensure the constraint violation is decreasing and converging zero. This idea also be found in sequential quadratic programming (SQP). SQP has been widely applied to solve constrained single-objective optimization [21, 6J. Later on, it has also been applied constrained MOO [16]. Compared SQP, we use an identity matrix to approximate the Hessian of each objective, and we propose an adaptive variant that automatically adjust the descent amount of objectives. Furthermore, existing SQP algorithms typically require an inner loop to solve the optimal Lagrangian multiplier, resulting in double-loop algorithms. In contrast, we develop single-loop algorithm which can be more efficient.
Vector optimization. Vector optimization [12, 27] generalizes multi-objective optimization by general partial order, such
substituting the commonly used component-wise partial order with as a general convex-cone induced partial order used in this paper. In the unconstrained setting, the MGDA method is extended steepest
descent method in the vector optimization setting in [25]. In the constrained setting, the first-order optimality conditions are studied in [23, 57J. Algorithms based on projected gradient [24, 18, 19] or conditional gradient [8] developed to solve vector optimization with parameters in a constraint set, to name a few. Besides gradient-based vector optimization, another line of works focus on black-box vector optimization with discrete design space; see e.g. [3, 2]. To our best knowledge, we are the first to design gradient-based single-loop (stochastic) primal algorithms for constrained vector optimization with convergence rate guarantees.
Experiments
In this section, we conduct experiments to verify our theory and show the applicability of the algorithms preference- greference-guided multi-task learning, and multi-objective finetuning of large multi- lingual speech recognition models. We use Linear scalarization (LS), MGDA [52], PMTL [33], EPO [41], XWC-MGDA [44] as baselines for comparison.
Metries. Objective loss and accuracy. We report the objective losses and accuracies in classification. Relative loss profile. We use the dlement-wise product of the preference vector and the objective values as a measure the relative loss profile. Hypervolume. Let F" RM denote a reference point, and S denote set of objective function values of the obtained models. Hypervolume measures the size of the dominated space of S relative to F", which can be computed by HS)) = A(lg e RM 3F S F < q < F')), where A(-) denotes the Lebesgue measure. For fair comparison, the Nadir point, i.e., the worst performance on single-task baselines, as the reference point F'.
Additional details. The implementation and additional experiments can be found in Appendix H.
5.1 Synthetic data
Following [33, 41, 44], the first objective we consider
F(0) = (1 - ||0 t 1ll
1-e -16+ J 113).
(5.1)
The objective has a nonconvex Pareto front (PF). See the results of different methods in Figure 3. With uniformly generated weights from a simplex, LS only finds extreme points on the PF with one objective minimized. MGDA can only find points close to the center of the PF. PMTL can find points
8

---

0.00
0.50
0.92
0.03
0.70
0.73
0.50
0.83
0.73
0.50
0.85
0,20
0.45
0.48
AX
X
0.02
EPP
X
0.90
0.70
XWC MODA
PMTT.
0.75
Oue
0.76
(a) accuracy
(b) Multi-Fashion accuracy
(c) Multi-F++ accuracy
0.7
1.0
0.7
0.9
0.7
FX
0.4
0.1
0.5
0.4
(d) Multi-MNIST loss
(c) Multi-Fashion loss
(f) Multi-F+M loss
Figure 5: Training losses and accuracies of various methods with different preferences across three image datascts. The horizontal and vertical axes represent results for objective 1 and objective 2, respectively. Different colored dashed arrows indicate various preference vectors. Different markers denote the solutions obtained by different methods, with marker colors matching the preferences.
the subregions but not aligned well with the exact preference vectors. Similar to EPO, in Figure 3e, method finds points that align well with the exact preferences; and in Figure 3f, method can handle different definitions of preferences.
We conduct another experiment in a more difficult setting where the initial objectives are close to the PF. In Figures 4a-4c, we consider a relatively casier case where the initial model is not too close to the Pareto optimal. For our method, by solving (3.5), a1 = 1 Lg .2 Vs V/l. The corresponding matrix A is given by A = [a1,a2]] az] In this setting, all methods converge to the PF, and our method takes the least number of iterations (PMTL takes 100, EPO Search takes 60, and our method takes only 10 iterations). PMTL does not align exactly with the preference vectors, while EPO and our method do. In Figures 4d-4f, PMTL and our method take 200 iterations, EPO Search takes 80 iterations. Results show that for the green and yellow preferences, PMTL moves further away from the PF in the first stage, and does not perform any update the second stage. It converges to the PF only in 2 out of cases. In contrast, with controlled ascent updates, EPO and our method can converge to PF and trace the PF until the objectives align exactly with the preferences.
5.2 Real data
Multi-patch image classification. Following [33, 41, 44], consider three datasets for image classification, including Multi- -NIST, Multi-Fashion, and Sallii-FashonnMMNIT.. The two tasks or objectives in all three datasets to classify the top-left and the bottom-right images, respectively. For a fair comparison, we use LeNet as the backbone neural network. The training losses and accuracies of different methods given different preference vectors are plotted in Figure 5. Experiments for method are repeated 5 times. Hypervolumes with means and standard deviations are reported in Table 2. The results for other methods Table are referenced from [44].
Table 2: Hypervolumes of different methods (x (x10-
Datasets
LSS
PMTL [33]
EPO [41]
XWC-MGDA [44]
FERERO
Multi-MNIST loss
1.68
1.41
1.35
1.42
1.97=021
Hulti-Fashion loss
6.75
5,90
6.02
6.77
7.76
Multi-F+M loss
3.63
3.03
3.76
3,89
3.82
Multi-MNIST accuracy
0.19
0.15
0.15
0.16
0.24
accuracy
0.99
0.87
0.87
0.99
1.17
Multi-F-4 accuracy
0.48
0.40
0.50
0.52
0.53:404

---

0.00
0.53
0.36
0.50
0.30
0.40
6.55
0.40
0.33
6.20
0.25
0.30
0.31
0.00
0:63
0.40
0.45
0.00
0.23
0.00
0.46
6.30
0.3
0.0
0.5
(a) Multi-MNIST loss
(b) Multi-Fashion loss
(c) Multi-F+M loss
Figure 6: Losses and preferences of FERERO when the initial objective is close to the Pareto front.
One limitation of EPO is that the preference is defined ray from the origin in the objective space, whose corresponding objectives can be unattainable, e.g., the yellow preferences in Figure 5. As a result, the losses of all methods are far away from the preference vectors. In this case, more flexible choice of preferences is helpful to ensure preference satisfaction. To demonstrate this, we conduct experiments with more flexible preferences; align better with the preference lines compared to those in Figure 5. Moreover, it can perform controlled ascent updates during optimization, which cannot be achieved by PMTL or XWC-MGDA.
the results in Figure 6, where the obtained solutions
Multi-lingual speech recognition. We further apply the proposed method to the multi-objective finetuning of pre-trained multi-lingual speech models. We use the Librispeech (100 hours) [47], and
Table 3: WERs (%) on Librispeech and AISHELL v1.
Method
English
Chinese
Average
Komatsu et al. [29]
7.11
w/o CPC [51] Init. (M2ASR) [51]
11.8
10.2
11.0
AISHELL v1 [5] datasets for multi--ingual speech recognition. A conformer with 8 blocks is used as the model architecture. The total number of parameters is around 64.5M with 58.4M encoder layer parameters and the rest being the classification layer parameters. We consider the objectives associated with the speech recognition Connectionist Temporal Classifi- cation (CTC) losses Chinese and English, denoted as frh and respectively. We also use the self-supervised Contrastive Predictive Coding (CPC) loss fp for representation learning; that is
7.3
6,2
6.7
LS-FT
6.8
5.9
6.4
FERERO-FT
5.4
4.9
5.1
min F(0) (f) (0), (0)) s.t. fz(0) S 61, (()(() (0)
(5.2)
where the first constraint ensures to learn good representation with e 1.2, and the second con- straint avoids one language loss dominates the other with 62 = 0.5; see more details in Appendix H.I.
Results on the word eтror rate (WER) are reported in Table 3. The baselines include the state-of -of-the-artt result from Komatsu al. [29] without an additional large language model, our own implementation of training using only the sum of supervised CTC losses (w/o CPC), the initial pre- pre-trained M2ASR model [51] (init.), linear scalarization of all three objectives for finetuning pre-trained model with the CPC loss (LS-FT)). Results show that considering CPC loss besides the supervised CTC loss improves the average WER by 4.2%, and this can further improved by 0.3% by finetuning with linear scalarization. However, the LS-FT model has much better performance in Chinese compared to English. With our proposed approach, the performance gap between different languages is reduced, and the average WER is further improved by 1.3%.
Conclusions
In this work, we frame preference-guided multi-objective learning as constrained vector opti- mization problem. Specifically, we introduce constraints and partial order to capture the absolute and relative preferences. Under this framework, we develop algorithms to solve the constrained vector optimization problem. Our proposed algorithms use unified formulation without solving different subprograms at different stages. And they enjoy the benefit of allowing controlled ascent and escaping weak optimal solutions. Theoretical guarantees on the non-asymptotic convergence of the deterministic algorithms and their stochastic variants are provided. Experiments on benchmark datasets demonstrate the broad applicability of the proposed algorithms.
10

---

Broader Impacts and Limitations
This paper casts the preference-guided multi-objective learning as constrained vector optimization problem and proposes an algorithm with single-loop and stochastic variants to solve the problem, which have non-asymptotic convergence guarantees. The proposed method is applied to image classification and speech recognition. The positive impact is that it is principled method with efficient implementations that has broad applications across various domains. There no negative social impact.
The proposed algorithm is able to model flexible preferences but cost of higher per-iteration complexity compared to scalarization methods. The theoretical guarantees make standard assump- tions that the objectives are lower bounded, Lipschitz continuous and smooth. These are common assumptions in the optimization literature, and can be satisfied for neural networks with smooth activation functions.
Acknowledgements
The work of L.. Chen, AFM Saif, and T. Chen was supported by the National Science Foundation (NSF) projects 2401297, 2412486, the RPI-IBM Artificial Intelligence Research Collaboration (AIRC), the Cisco Research Award, and the IEEE Signal Processing Society scholarship. The work of Shen was supported by NSF ECCS-2412484, We also thank Quan Xiao, Prof. Luis Nunes Vicente, Prof. Rongjie Lai for inspiring and helpful discussions, and the anonymous reviewers for their constructive feedback to improve our paper.
References
[I] Jaqueline S Angelo, Isabella A Guedes, Helio JC Barbosa, and Laurent E Dardenne. Multi-and many-objective optimization: present and future in de novo drug design. Frontiers in Chemistry, 11, 2023.
[2] Cagin Ararat and Cem Tekin. Vector optimization with stochastic bandit feedback. In Proc. International Conference on Artificial Intelligence and Statistics, pages 2165-2190, Valencia, Spain, 2023.
[3] Peter Auer, Chao-Kai Chiang, Ronald Ortner, and Madalina Drugan. Pareto front identification from stochastic bandit feedback. Proc. International Conference on Artificial Intelligence and Statistics, pages 939-9477, Cadiz, Spain, 2016
[4] Dimitri Bertsekas. Constrained Optimization and Lagrange Multiplier Methods (Optimization and Neural Computation Series). Athena Scientific, 1996.
[5] Hui Bu, Jiayu Du, Xingyu Na, Bengu Wu, and Hao Zheng. Aishell-1: An open-source mandarin speech corpus and a speech recognition baseline. In Conference of the oriental chapter of the international coordinating committee on speech databases and speech I/O systems and assessment, pages 1-5, 2017.
[6] Richard H Byrd, Frank E Curtis, and Jorge Nocedal. An inexact sqp method for equality constrained optimization. SIAM Journal on Optimization, 19(1):351-369, 2008
Lisha Chen, Heshan Fernando, Yiming Ying, and Tianyi Chen. Three-way trade-off in multi- objective learning: Optimization, generalization and conffict-avoidance. Journal of Machine Learning Research, 2024.
[8] Wang Chen, Xinmin Yang, and Yong Zhao. Conditional gradient method for vector optimization. Computational Optimization and Applications, 85(3):857-88) July 2023.
[9] Frank E Curtis, Suyun Liu, and Daniel Robinson. Fair machine learning through constrained stochastic optimization and an epsilon-constraint method. Optimization Letters, pages 1-17, 2023.
[10] Dmitriy Drusvyatskiy and Adrian Lewis. Error bounds, quadratic growth, and linear conver- gence of proximal methods. Mathematics of Operations Research, 43(3):919 2018.
11

---

[11] Jean-Antoine Désidéri. Multiple-gradient Descent Algorithm (MGDA) for Multi-objective Optimization. Comptes Rendus Mathematique, 350(5-6), 2012.
[12] Matthias Ehrgott. Multicriteria optimization. Springer, Berlin; New York, 2nd ed edition, 2005.
[13] Heshan Fernando, Lisha Chen, Songtao Lu, Pin- Yu Chen, Miao Liu, Subhajit Chaudhury, Keerthiram Murugesan, Gaowen Liu, Meng Wang, and Tianyi Chen. Variance reduction can improve trade-off in multi-objective learning. In Proc. IEEE International Conference on Acoustics, Speech, and Signal Processing, pages 6975-6979, 2024.
[14] 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, May 2023.
[15] Jörg Fliege and Benar Fux Svaiter. Steepest descent methods for multicriteria optimization. Mathematical methods of operations research, 51:4794494, 2000.
[16] Jörg Fliege and A. Ismael F. Vaz. A method for constrained multiobjective optimization based on sqp techniques. SIAM Journal on Optimization, 26(4):2091-2113 2016.
[17] Jörg Fliege, A Ismael F Vaz, and Luís Nunes Vicente. Complexity of Gradient Descent for Multi-objective Optimization. Optimization Methods and Software, 34(5):949 99999999,9 2019.
[18] Ellen H. Fukuda and L. M. Graña Drummond. On the convergence of the projected gradient method for vector optimization. Optimization, 60(8 10:19900111222 2011.
[19] Ellen H. Fukuda and L. M. Graña Drummond. Inexact projected gradient method for vector optimization. Computational Optimization and Applications, 54:473-493, 2013.
[20] Bennet Gebken, Sebastian Peitz, and Michael Dellnitz. A descent method for equality and inequality constrained multiobjective optimization problems. In Numerical and Evolutionary Optimization, pages 29-61. Springer, 2019.
[21] Philip E Gill, Walter Murray, and Michael A Saunders. Snopt: An sqp algorithm for large-scale constrained optimization. SIAM review, 47(1):99-131, 2005.
[22] Chengyue Gong, Xingchao Liu, and Qiang Liu. Automatic and harmless regularization with constrained and lexicographic optimization: A dynamic barrier approach. In Proc. Advances in Neural Information Processing Systems, volume 34, pages 29630-296444 virtual, 2021.
[23] L. M. Graña Drummond, A. N. lusem, and B. F. Svaiter. On first order optimality conditions for vector optimization. Acta Mathematicae Applicatae Sinica, English Series, 19(3), September 2003.
[24] L. M. Graña Drummond and A.N. lusem. A projected gradient method for vector optimization problems. Computational Optimization and Applications, 28:5-29, April 2004.
[25] L. M. Graña Drummond and B.F. Svaiter. A steepest descent method for vector optimization. Journal of Computational and Applied Mathematics, 175(2):395-414, March 2005.
[26] Anmol Gulati, James Qin, Bhung-Cheng Chiu, Niki Parmar, Yu Zhang, Jiahui Yu, Wei Han, Shibo Wang, Zhengdong Zhang, Yonghui Wu, et al. Conformer: Convolution-augment transformer for speech recognition. arXiv preprint wxXi:2005.08800 2020.
[27] Johannes Jahn. Vector Optimization: Theory, Applications, and Extensions. Springer Berlin Heidelberg, Berlin, Heidelberg, 2011.
[28] Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak-lojasiewiez condition. arXiv preprint arXiv: 1608, 04636, 2016.
[29] Tatsuya Komatsu, Yusuke Fujita, Jaesong Lee, Lukas Lee, Shinji Watanabe, and Yusuke Kida. Better intermediates improve CTC inference. arXiv preprint arXiv:2204.00177, 2022.
12

---

[30] Panagiotis Kyriakis, Jyotimmoy Deshmukh, and Paul Bogdan. Pareto policy adaptation. In Proc. International Conference on Learning Representations, virtual, 2021.
[31] Xi Lin, Zhiyuan Yang, Xiaoyuan Zhang, and Qingfu Zhang. Pareto set learning for expensive multi-objective optimization. In Proc. Advances in Neural Information Processing Systems, volume 35, New Orleans, LA, December 2022.
[32] Xi Lin, Xiaoyuan Zhang, Zhiyuan Yang, Fei Liu, Zhenkun Wang, and Qingfu Zhang. Smooth tchebycheff scalarization for multi-objective optimization. arXiv preprint 140. 2024.
[33] 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.
[34] Bo Liu, Yihao Feng, Peter Stone, and Qiang Liu. Famo: Fast adaptive multitask optimization. In Proc. Advances Neural Information Processing Systems, volume 36, New Orleans, LA, 2023.
[35] Bo Liu, Xingchao Liu, Xiaojie Jin, Peter Stone, and Qiang Liu. Conrsict-Averse Gradient Descent for Multi-task Learning. In Proc. Advances in Neural Information Processing Systems, virtual, December 2021.
[36] 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.
[37] Suyun Liu and Luis Nunes Vicente. Accuracy and faireess trade-offs in machine learning: stochastic multi-objective approach. Computational Management Science, 19(3)=513-537, 2022.
[38] 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.
[39] David G. Luenberger and Yinyu Ye. Linear and Nonlinear Programming, volume 116 of International Series in Operations Research & Management Science. Springer US, New York, NY, 2008.
[40] Sohvi Luukkonen, Helle W. van den Maagdenberg, Michael T.M. Emmerich, and Gerard J.P. van Westen, Artificial intelligence in multi-objective drug design. Current Opinion in Structural Biology, 79:102537, 2023.
[41] Debabrata Mahapatra and Vaibhav Rajan. Multi-task learning with user preferences: Gradient descent with controlled ascent in pareto optimization. In Proc. International Conference on Machine Learning, virtual, 2020.
[42] Natalia Martinez, Martin Bertran, and Guillermo Sapiro. Minimax pareto fairesss: A multi objective perspective. In Proc. International Conference on Machine Learning, pages 6755- 6764, virtual, 2020.
[43] Kaisa Miettinen. Nonlinear Multiobjective Optimization, volume 12. Springer US, Boston, MA, 1998.
[44] Michinari Momma, Chaosheng Dong, and Jia Liu. A mutti-abjcctivv/muttttaaaa learning framework induced by pareto stationarity. In Proc. International Conference on Machine Learning, Baltimore, MD, 2022.
[45] Aviv Navon, Aviv Shamsian, Ethan Fetaya, and Gal Chechik. Learning the pareto front with hypernetworks. In Proc. International Conference on Learning Representations, virtual, April 2020.
[46] Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding, arXiv preprint arXiv:1807.03744 2018
13

---

[47] Vassil Panayotov, Guoguo Chen, Daniel Povey, and Sanjeev Khudanpur. Librispeech: an ASR corpus based on public domain audio books. In Proc. International Conference on Acoustics, Speech and Signal Processing, pages 2200-5210, 2015.
[48]
Javier Peña, Juan C. Vera, and Luis F. Zuluaga. New characterizations of hoffman constants for systems of linear constraints. Mathematical Programming. (57(1):7--109 2021.
[49] Hoang Phan, Ngoc Tran, Trung Le, Toan Tran, Nhat Ho, and Dinh Phung. Stochastic multiple target sampling gradient descent. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, December 2022.
[50] Sashank Reddi, Suvrit Sra, Barnabás Póczós, and Alex Smola. Proximal stochastic methods for nonsmooth nonconvex finite-sum optimization. In Proc. Advances in Neural Information Processing Systems, volume 29, 2016.
[51] A F M Saif, Lisha Chen, Xiaodong Cui, Songtao Lu, Brian Kingshury, and Tianyi Chen. M2ASR: Multilingual multi-task automatic speech recognition via multi-objective optimization. In Interspeech 2024, pages 1440-124, 2024.
[52] Ozan Sener and Vladlen Koltun. Multi-task learning multi-objective optimization. In Proc. Advances in Neural Information Processing Systems, Montreal, Canada, December 2018.
[53] Han Shen, Quan Xiao, and Tianyi Chen. On penalty-based bilevel gradient descent method. arXiv preprini urXiv:2302.05//8 2023.
[54] 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.
[55] Peiyao Xiao, Hao Ban, and Kaiyi Ji. Direction-oriented multi-objective learning: Simple and provable stochastic algorithms. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, 2023.
[56] 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.
[57] Jane J Ye and Qiji J Zhu. Multiobjective optimization problem with variational incquality constraints. Mathematical Programming, 96(1):139-160, 2003.
[58] Yiming Ying and Ding- -uan Zhou. Unregularized online learning algorithms with general loss functions. Applied and Computational Harmonic Analysis, 42(():224-22) 2444, 2017.
[59] 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.
[60] 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-38115, New Orleans, LA, December 2022.
[61] Yiheng Zhu, Jialu Wu, Chaowen Hu, Jiahuan Yan, Tingjun Hou, Jian Wu, et al. Sample-efficient objeivv molecular optimization with gflownets. Proc. Advances in Neural Information Processing Systems, volume 36, New Orleans, LA, 2023.
14

---

Appendix for " "EERER: A Flexible Framework for Preference-Guided Multi-Objective Learning"
Table of Contents
A Notations
15
B Related Works and Comparison
15
B.I Extended related works
16
B.2 A detailed comparison with existing works
17
Preliminaries
General cone-induced partial ordering.
C.2 Necessary and sufficient conditions for C-optimality
Seagghaiily.....................
D Proof of Auxiliary Lemmas
19
D.1 Lagrangian of the subprogram
19
D.2 First-order necessary optimality conditions
19
D.3 Properties of PMOL
20
E Proof of Theorem 1: convergence of Algorithm
25
E.1 Auxiliary lemmas
25
E.2 Proof of Theorem
27
F Proof Theorems 2 and 3: convergence Algorithm
F.1
Auxiliary lemmas
F2 Analysis with the merit function: proof of Theorem 2
31
D3 Sharper analysis with different merit function: proof of T Theorem
34
G Stochastic Algorithms
40
G.1 Algorithm summary
40
G.2 Proof of Theorem 4: convergence of Algorithm
40
Implementation Details and Additional Experiment Results
44
H.l Implementation details
44
Additional experiment results
45
A Notations
summary of notations used in this work is listed in Table 4 for ease of reference.
Recall that given vectors v, w, we use e < w and v S w to denote 0; < w, for all i, and v; S w; for all i, respectively. We use w to denote S w and In the proof, we use || || to denote the mo-nomm, and || ||a to denote the -ormr. We use lab to denote the operator that takes element-wise absolute value of matrix. We use and 0 to denote the all-one and zelo vectors, respectively. Their dimensions are specified only when they are not clear in the context. We use [v. w) represent column concatenation of matrices or vectors, and use (u: w) to represent row concatenation of matrices or vectors.
and define >, 2. 2 analogously.
B Related Works and Comparison
In this section, we provide a detailed review and comparison of additional related works in multi- task/objective learning, vector optimization, and Pareto front approximation.
15

---

Table 4: Notations and their descriptions.
Notations
Descriptions
0 E R {
Model parameter, or decision variable
Stochastic samples during training
A scalar-valued objective function evaluated on data point &, with fe.m : R2 + R, or on dataset D, fr. with fm == [D] E RED fe.m Gradient of fm (0). with V fm R - R2
fe.m
(0)
A vector- valued objective function evaluated on data point &, with F& R + IRM,, or dataset D. with F (D] EeEn Fe(O)
(e(O), F(0)
VF(()
Gradient of F0). with VF R E
Step size to update model parameter Step size to update multiplier À
B.1
Extended related works
In this section, we provide an extended discussion of the works that are closely related to ours.
Variants and analysis of MGDA. MGDA [15, 11] finds non-conflicting or the steepest common descent direction at each iteration, which we term as conflict-avoidant (CA) direction. Our work is related to MGDA in the unconstrained setting since when CA RR Mg Mn. i.e., there are no constraints, and Ωx, (0) = A for the subprogram, our Algorithm reduces to MGDA. Non- asymptotic convergence analysis for the deterministic MGDA was first provided in [17]. Convergence of the proximal algorithm was discussed
[54]. Later on, stochastic variants of MGDA were developed with convergence analysis [36, 60, 14, 7, 55, 13]. A critical challenge in developing convergent stochastic MGDA is that the CA directions can biased even if they are calculated from unbiased stochastic gradients of the objectives. This issue can be mitigated using variance reduction techniques on the stochastic gradients. For example, one can use increased batch size [36], or momentun-based methods [60, 14, 13]. Alternatively, one can also use double (independent) sampling [7, 55]. Among these MGDA variants, [60, 14, 13, 7] also use single-loop updates, where, instead of exactly solving the weight to combine the objective gradients, the weight is approximately updated only once at each iteration. One benefit of such gradient- based single-loop update is that the approximation approach proposed in [34, Section 3.2] can be applied to largely improve the per-iteration complexity by eliminating the need to compute multiple gradients.
Convergence rate to Pareto stationarity of the above MGDA variants is discussed in existing literature. Specifically, the analysis in [36] focuses on the convex case, while the rest [60, 14, 7, 55, 13] focus on the nonconvex case. However, with merely convergence to the Pareto stationarity, the theoretical benefit of MGDA variants over linear scalarization is unclear. To address this, convergence of the stochastic approximate CA direction to the deterministic optimal CA direction besides convergence to the Pareto stationarity is first analyzed in [14], and later improved in [7] with relaxed assumptions and/or faster convergence rate. Some of the improved analysis techniques in [7] has been applied algorithm, and in [55] with a double-loop algorithm. Moreover, it discussed in [7] that the analysis technique is widely applicable to other algorithms, such as the SMG algorithm [36] in the nonconvex case for both convergence to Pareto stationarity and to the CA direction. In our proof of Theorem 2, the convergence of the
in [13] to further improve the convergence rate with a momentum-bass
single-loop algorithm, we use similar techniques as in [7], which are detailed in Appendix F.2.
Pareto front approximation. Pareto front approximation aims to find multiple different solutions whose objective values approximate the Pareto front. Scalarization-batt approximate the Pareto front by enumerating different weights of the objectives. However, they cannot find solutions on the nonconvex part of the Pareto front [43]. Decomposition-base -based methods partition the objective space into different subsets with constraints that represent different trade-off preferences, and solve the resulting constrained multi-objective optimization problems with gradient- based or evolutionary algorithms [33, 22]. Probabilistic inference methods update a set of models following distribution that converges to Pareto stationary [38, 49]. The expected update direction of the models typically follows the steepest common descent direction for all objectives. Pareto set learning methods use neural network to lear mapping from user preferences to corresponding
methods can be used to
16

---

models. The learned neural network is able to generate different models with different input user preferences [45, 56, 30, 31]. Although we do not focus on Pareto front approximation in this work, our algorithm can be applied to generate different models based on different diverse preferences to approximate the Pareto front, as [33]-
B.2 A detailed comparison with existing works
Preferences as linear constraints of objectives. Different constraints S partition the objectives into sub-regions, as shown in Figure Many preferences can be modeled by linear equality or inequality constraints [33, 41, 44]. For example, below we list different choices of C' for different methods in Figure 1.
(a) Bg = 12 E RRMXM b -0,, 62. <M]"; .M]]
(b) B₁ E (M b
In Figure la the preferences are based on the function values of fi controlled by different thresholds, corresponding to the inequality constraints defined by (a). In Figure 1b, the constraints are that the objectives F() should lie on one of the preference vectors therefore should satisfy the equality constraint B₁ (0) 0.
Detailed comparison with the most relevant works. Below we provide fine-grained comparison with some existing works in Table as an extension of Table
In terms of preference modeling, the scalarization-basse methods such as Linear Scalarization and Smooth Tchebycheff scalarization use weight of different objectives to model preferences. They are not flexible enough to capture preferences illustrated in Figure 1. PMTL uses constrained multi-objective optimization formulation, with preferences modeled by inequalities. EPO models the preference by an r- ray, same as the example given in Figure 1b. (X)WC-MGDA uses a shifted ray not necessarily from the origin to model the preferences. In all of these works, they only model the absolute preferences that define the preferred objective values. In contrast, we also consider the relative preference that define the relative improvement directions of objectives.
In addition to the comparison in Table 1, our framework enjoys additional benefits including the ability escape weak optimal solutions and to maintain vcale-invariance These abilities are attributed to the subprogram that is adaptive to the objective values, as detailed in Lemma 6.
Table 5: Comparison to existing PMOL methods, extension of Table 1.
Handle aoncomex
Gesena
subprogram
Provable CQ
partial
wio computing active index
invariance
optinal
(Smooth) Tchebycheff [32)
PMTL [39]
assume LICQ
BPO
[14]
PERERO (ours)
prove calmiees
Below, we further summarize the reasons behind the benefits of our proposed method. We use "
indicate the reasons the left and the corresponding benefits the right.
relative preference (by general partial order)
+ allow controlled ascent
Flexible preference
handle nonconvex Parcto Front
absolute preference (by constraints)
equality constraints - align exactly to preference vector constraints are linear functions of objectives -> provable CQ
scale invariance
adaptive objectives
Adaptive subprogram
ability escape weak optimality
single subprogram w/o computing active indices non-asymptotic convergence
adaptive to constraints
17

---

C
Preliminaries
In this section we introduce preliminaries on the general cone-induced partial ordering and the corresponding optimality conditions for completeness since we use these concepts in our proofs. Then we discuss the relation between the Pareto optimality and the optimality induced by general polyhedral cone.
C.1 General cone-induced partial ordering
In this section, we introduce basic definitions, lemmas, propositions, and theorems in vector opti- mization, including the cone-induced partial ordering, the minimum and weakly minimum associated with the partial ordering in real linear space, and necessary conditions for minimum. These concepts are defined in [27]. We restate them following our notations for completeness. We denote Z as a real linear space, C, S as subsets in Z, and w, z, y, 2 as points or elements in Z, Oz as the zero vector in the space Z.
Definition 4 (Cone). Let C' be nonempty subset of a real linear space Z. The set C is called a cone, if y C, C,X 0 xy E C.
Lemma 3 (Convex cone). A cone C in real linear space is convex if and only if C + CCC. Definition (Partially ordered linear space). A real linear space equipped with partial ordering is a partially ordered linear space.
Proposition (a) If < is partial ordering on Z, then the set := 1z S 23 a convex cone. If. in addition, I is antisynmetric, then C is pointed.
(b) If C is convex cone in Z, then the binary relation Sc:= {(I.y) E Z Z y I C) is
partial ordering on Z. !f. in addition, C is pointed, then Sc is antisymmetric.
Definition (Ordering cone). convex cone churacterizing a partial ondering in a real linear space is an ordering cone.
Definition 7 (Cone-induced partial ordering). Let C' be closed pointed convex cone of RM, with nonempty interior. The partial order in R. induced by C, Sc defined by
u Sc v. if u--uEC
(C.1)
The relation induced by int(C) R.M, <o is defined by
a<ov, v, if v E int(C).
(C.2)
Definition 8 (C-minimum and C-weakly minimum). Let S be a nonempty subset of partially ordered linear space with an ordering cone C, then
(a) element E S is called C-minimum of the set S, if ((2) C) (2) C. in other words, there exists no other z' E S with z' Sc z and z' + 2;
(b) element
S is called C-weakly minimum of the set S. if ({2) in)(CC) n 0. where int(C)) + 0 is the algebraic interior of C, in other words, there exists no other z' E S with x' <o and z' #2.
Definition 9 (C-stationary). point 0 E R99 is C-stationary there is first-order common descent direction d E R2 that V F(()) d (C), i.e., (F())(VF(()T)))))) (-innt(()) = 0.
C.2 Necessary and sufficient conditions for C-optimality
Note that, when C = RM = f= R- 2m > 0 for all m [M]], C-minimum and C-weakly minimum in Definition are Pareto minimum and weakly Pareto minimum, respectively. Recall that F : R + AM is a continuously differentiable function. The problem we consider is to find the unconstrained C-minimizers of F, denoted as ming F(0) with 6 E R?. We then proceed to introduce the relation between C-stationarity and Pareto stationarity in this section.
Proposition 2.
Let C be a closed convex pointed cone.
1) Suppose C A. O is Pareto stationary, is C-stationary. other words, C-stationarity is necessary condition for Pareto stationarity
2) Suppose R C C. if is C-stationary, 0 Pareto stationary. other words, C-stationarity is sufficient condition for Pareto stationarity.
18

---

Proof of Proposition 2. 1) By definition, if is Pareto stationary, then range (ang)(VF(()T) n (-int(R*)) 0. Since - R then Cin () C -in and we have
(ange(VF(())
(-int(C)) S range ( = 0.
(C.3)
Therefore, is C-stationary.
Following similar arguments, 2) can also be proved.
D Proof of Auxiliary Lemmas
In this section, we provide proof the main theoretical results in this paper.
D.1 Lagrangian of the subprogram
Proof of subprogram reformulation.
Define the Lagrangian function
Ll,, Xy, An) = |dl (T c(1 AF(O)) (AT
1 Bg ( d cg(() + XT (B, (F())( d (0)) (D.I)
where x E N. Ag E RR,, An E R Ma. By the first-order optimality condition w.r.t. and e, we can obtain that
d" + VF(O)A X; + B + B, AN 0;
(D.2)
1 AF - X; AF = O.
(D.3)
Combining the last equation with Ny R, obtain X; E 22 (0). Plugging the above results into the Lagrangian function gives
A
argmin min AN
VF(O)(A + N, B xn)
G(0)) H())
(D.4)
which leads to the dual form in (2.3). Since (2.1) is constrained convex optimization problem where the Slater's s condition holds, therefore, the duality gap is zero.
Remark Note that we can also have a simplified subprogram with A I, and without adaptation to the objective values, as defined below
1 min c+ - Ildpp s.t. VF(O) < cl (d.c)ER*XR
(0)
(D.5)
d cg) S O, VH(A) + c()( =
This formulation corresponds the SQP method applied the constrained MOO problem [16].
Then the corresponding Lagrangian function becomes
L(c, d, A5, An) =c | |dll XT(
+ +
++ c + (B.VF(()) d H()))
(D.6)
By the first-order optimality condition w.r.t. c, (D.3) can be replaced by
1- X; 0.
(D.7)
And the rest results remain the same, i.e., (D.2) and (D.4) still hold, while 22y, A
D.2 First-order necessary optimality conditions
We then discuss the first-order necessary optimality conditions for problem (PMOL.). We begin the discussion with the geometric notions of improving and feasible directions.
19

---

Improving directions. The improvement directions are defined as generalized common descent directions so that the iterates strictly improve or dominate the previous iterates based on CA. i.e.. F(O.) F(+++1) E int((C)) Denote de E IR as update direction at iteration I, and 0g > 0 as the step size the 1-th iteration. The general update equation given update direction d, is 0++1 0, + a,dz Based on first-order Taylor expansion, the amount of improvement at iteration t can be approximately expressed as F(O,) - P(0++1) R -a, (0+) de E int(CA). We term such directions the general Ca-improving directions. The cone of Ca-improving directions at is
DC {d I2 VF(() d -in)(
(D.8)
When A = IM, they are common descent directions.
Feasible directions. Similar the concept in constrained single objective optimization, the feasible directions are those that ensure F(O, + orde) E S. We rewrite problem (PMOL) with explicit
C'-induced partial ordering as
min CA F(O) s.t. G(O) S 0, H()) =
PMOL
where G R2 RMa, H R2 MM are linear functions of F, and are differentiable. Let / = ii ((( 0} be the index set of the active inequality constraints in G(O), and Gr(0) = [... (.)....... for E A subset of the feasible directions described by the gradients of the
equality and active inequality constraints at 0 is given by
D₂ {d E R (G) d 0}, DH {d R (H(0)dd=))
(D.9)
A necessary optimality condition is that there exists no feasible and improving directions at 8, i.e.. DCa n D2 Dr = U. An algebraic description of the necessary optimality conditions for (PMOL) is summarized below.
Proposition 3 (First-order necessary optimality conditions for (PMOL)). Let CA = fy E R Ay 2 0) that satisfies iCt(Ca) * 0. If solves (PMOL) locally, then there exists xy RM
Xg E R4,,, Agy; + O, and X E RM that
VF(O)ATA + VG(O)\, + +H(())> = and N1 X][-G(()) =0
(D.10)
Proof of Proposition 3. The geometric description Dca n D2 Dr equivalent to that the linear system below w.r.t. d is inconsistent
AVF(O)
d <<0 O and VH( 0 (0)
(D.11)
By the Motzkin's transposition theorem, system (D.11) being inconsistent is equivalent to that the following linear system w.r.t. p, An has a solution with p 2 0
VF VG, p + VH(() 0.
(D.12)
Letting = PAy; Ag.1), where Ag. = [... ; Ag. ] E 7, and >g. = 0, for all & / completes the proof.
Remark 5. Notice that, Proposition 3 provides Fritz John (FJ)-type first-order necessary optimality condition, which has been discussed in prior works such as [57, Theorem 1.2] with additional variational inequality constraints, and [23, Section 3, (2)-(5)] with inequality constraints only. We provide the derivation for our problem here for completeness. condition, the multiplier Xj associated with the objective F(0) can be zero if [I] > 1, which is undesirable. We need additional constraint qualifications to ensure the condition in (D.10) with Xj * O, i.e., the KKT condition, is also a necessary optimality condition. This is equivalent to po 1, and without considering the variational inequality constraints in [57, Theorem 1.2). The constraint qualification is discussed in detail in Appendix D.3.2.
the FJ-type necessary optimality
D.3 Properties of PMOL
In this section, we discuss the properties of PMOL and their proofs. These include the properties of the subprogram in Lemma 1, and the calmness CQ of PMOL in Lemma 2.
20

---

D.3.1 Proof of Lemma 1: properties of the subprogram
Lemma 6 (Additional properties of the subprogram). For the subprogram (2.3), the following properties hold:
1. The solution (0) is unique.
If is a local weak optimal solution with AF > 0, then d' (0) (0)= 0, (0) - O. Otherwise, if is not a local weak optimal solution, then d² (0) & 0, xb(0) < 0, and when 0 is feasible,
2x(0) S -Idd (0)1l O.
(D.13)
3. (Ability escape weak optimal solutions). Let 0 be weak optimal solution, with (AF(0)) m
0 for some m E [M]. If there exists feasible and non-strictly improving divections at with AV F(O) d $ O, then d' (0) # O, (00) O. Otherwise, if there exists no feasible and non-strictly improving directions at 0 with (V) T $ O, then (0) = 0, (0) = O.
4. (Scale invariance) Suppose there are only equality constraints, ie., Mg = O, and MA. = M 1. Bp is full row rank and selected such that (F(1)) - F(02)) = with F(01), F(02) being two different reference points in the objective space. For all 0 E RR9 that are feasible, i.e., H(0) = 0, when = 1, the normalized solution d' (0)/ (0)ll does not change when the objective F F()) is scaled by an arbitrary positive diagonal matrix.
Proof of Lemma 6. For Property-1, the uniqueness of d (0) follows from the strict convexity of the objective function w.r.t. the direction d.
For Property-2, in the first case if is a local optimal solution, by definition, there exists no feasible and improving directions d such that AVE(O) d < 0. Let (0) be the set of d E R2 that satisfy the constraints in (2.1), i.e.,
(o) {d RO (F (oVF(()dd+.p d 0, (.
0}.
(D.14)
Then, since AF > 0, for all d E (2(().
max (AVF(O) d)) 20 0
(D.15)
mE[M)]
and max mE(M]
2 0.
(D.16)
since AF(()= > 0, it holds that
(0) = min c+ マ lld|2
(O)
min max (AV d) (1 AA())) + + |ldd11 2 defla(0) ME[M
(D.17)
with (0) = 0 attainable by taking d = 0 E (a) The first case of Property-2 2 is proved.
In the second case, if f is not a local weak optimal solution, then there exists d E 12x(0) such that AV (()) < 0. Taking a = (AV d) (TTAF())(((A(())))))))))))) [|d]] and
dg ad, then
(0)) = min c 2 (0)
ldl
min max (O) T d)m (1 AF()))(AF(0)) + - 1d12
dERt(() ME(M]
max (AVF(O) (0)( (1 ()) AF(O)/(AP(()).. (dd
mE[M]
< max (AVF(B)) do mm AF(O))
1|d=|12
mE[Md]
max (AVF(O) d) (T AF(O)/ 1 1111111 mE(M]
1 -
< <0. (D.18)
2
Thus d' (0) # O. Recall that
d' d' = (
(D.19)
21

---

where by the feasibility and optimality conditions,
X (BAT+ =0,
(D.20a)
( (GGG) =0,
(D.20b)
T (AVF(O)) (0) - ((L =0. Combining the above with (D.19), have
'
(D.20c)
||d (0)11 = d' (0) VP(O) (A AA +
d' (0) VF(0)A X3 + +, H()) + Cg G(0)
AF(()) = -c' where the last inequality uses the fact that θ is feasible, and G(0) - 0, (()) = 0.
S (0)(1 AF( (F())
(D.21)
Then it holds that
(x) (0) + I|d (0)11 S 1dd O.
(D.22)
Therefore, Property-2 holds.
For Property-3, let S [M] be the set such that (AF(0))m 0 for all m E I, then (2.1) is equivalent
(0) min c+ ] |d]]
1
SPIw
XR
s.t. (O d)m c(1 A SO, for all m E [M] \
(AVF d)m 5. for all m E
F d+ d cy((0) < B₁
In the first case, if there exists feasible and non-strictly improving directions at 0 with AVF(0)
O, then such * O. E Qg. Following similar arguments as (D.18) by taking o maxmmmmM)y -MaX (AV ((O) m) (4())) and d, od, then
(0) = min C (x)
1
min dEfa(()) mE[M]V
((V) (1 AF(O))((AF(()),) +551ld Illl
1
< max (AVF(O) dg) m (1 AF(O)) + 1|d, mE[M]
=0 max (AVF(O) dl (1 AF()))(AFF()) + [| mE[M]
0 <0.
1
(D.23)
And the corresponding d' (0) # 0.
In the second case, if there exists no feasible and non-strictly improving directions at 0, then for all d E (a)()).
max m (AVF(O)T d)m dm) 2 0
(D.24)
and
(AVF(O) ddmm d)F((AF())),,, 2 0. mE[M]]
(D.25)
And since (AF(0)) > 0 for all m E [M] \ 7, holds that
(1) =
min ++ ||ll
(d.e)eBa(())))
max (AVF(O) T d) (1 AF(O)/(AF(()),, + 11 MEMM]
min
(D.26)
dE
22

---

with (b) = 0 if and only if d = 0 E Ra(0).
Combining the above arguments, Property-3 is proved.
For Property-4, let d" (0) the solution the original problem (2.1) without inequality constraints.
Using the fact that H/ (0) O, and letting À A >y B3 An Ay B3 d then the original dual problem can be written as
d' (0) = -FF(
s.t. X arg min (p; 0) - [ (0)
(D.27)
where (0) (0) + B% (R.)). and S2,, (0) & E E X F(0)=11T(())
Suppose the objective scaled by positive diagonal matrix A R MMMM then the scaled subprogram has a dual given by
(0) = VF(O)AX
s.t. X E arg (); - (0()((0A))
(D.28)
where A); = (Ωx, (0: + By (R.M),, and (x;((:A) = (As E IN AT (A((F)))
=
1 IFF(O)) Letting X' = Ad, then
(0) = -VF((O)>"
8.1. X E mrg ():00) 1 |F(O))11
(D.29)
where (0:A) = A(2x, (0: (0:A)))))A((1,,))
+ +AB (IR The set A A12,, (0; (0: can be written as
A A(22,, (0: A)) =(AA, | EER, X AF(0) = AF(0)=1TAF((0
=(2G E R ((O) = AAF(()))
(D.30)
Notice that,
F( =1 1 AF(O) F(()cc
(D.31)
where c 11AF(0)((TF(OO) Therefore, A(2x, A)) c. (02, (0)).
Also note that, B₁ E (MMMM is full row rank, and is selected based on F(0), which satisfies
(F(e() F(02))
(D.32)
where F(O)), F(02) are two reference points which fully defines the kernel of B₁. Similarly, when F(0) is scaled by A, the corresponding By, satisfies
B)A(((())) - -((2)) O.
(D.33)
This further implies
A AB T (RR = Fange(AB) T) ker (B/A) A)+ = (er(BB))== BA MA) = c. Ba (D.34)
Combining with A (0: = c. (2,, (8)) it holds that
2z. (0: A) = (0)
(D.35)
Therefore, the solution of î and X' is only subject to scaling factor, which does not change the direction of d' (f). This proves Property-4, the scale invariance.
L
Remark 7. Note that, Property 3, the ability to escape weak optimal solutions, and Property the scale invariance, come from the subprogram design that is aduptive to the objectives. For the simplified subprogram that not adaptive the objectives, these two properties no longer hold, but Properties and still hold.
23

---

D.3.2 Proof of Lemma 2: calmness of PMOL
Example 1. Let F R + RR? Consider the problem below as special case of (PMOL), given by
ming? F(f) s.t. f2(0) = min f2(0).
(D.36)
For = arg minøeRe f2(0), we have f2() = 0, and 9 satisfies (D.10) with X = [0, 1| * 0 and
A However, V (H())= V f0( violates the LJCQ, the Slater's CQ. and the MFCQ.
Below we restate the definition of the Calmness condition for PMOL [57], which generalizes the calmness condition in single-objective optimization.
Definition 10 (Calmness condition for PMOL [57, Restatement of Definition 4.5)). Let 0 be local solution to (PMOL). We say the PMOL problem satisfies the calmness condition at provided that there exists > 0 and Lipschitz function RM, + RM satisfying c(0, 0) 0 such that there exists no (0,p, p. q) E 0,0,0,0) 0) + <B] (0, O, 0)} satisfying
G(0) PS
(D.37a)
(1)) + --00,
(D.37b)
F(0) - F(0) + o(p iint(CA).
(D.37c)
Our proof relies on the following relative form of Hoffman error bound, which bounds the distance of point to nonempty solution set defined by constraints by measure of the constraint violation of the point.
Lemma 8 (Relative form of Hoffman error bound [48, Proposition 5]). Given BA RK by RR By E x by E Ro define E(p, ②) == {y E RM B&y + by I p, B&y + b, = q] and dom == {(p. q) E(p, q) + 0}. Let Qa S RM be a reference polyhedron (e.g., one defined by the intersection of half-spaces). Then for all u E QR. and (p, q) E dom E, there exists a relative Hoffmmun constant Chat depending only on By, Br, Sn such that
(B
by p) BR bb -q
dist(u, E(p, (gd) S Chof (By Br 2R)
(D.38)
where (Byu + bg p)+ = max (0. Byu + by - p} which replaces each negative component of Byu + bg p by zero, and dist(u, 52) inf e I|u (tuu-ul] w''l.
Proof of Lemma 2.
We first construct Φ(p, 9) = Chof [p_ 9 - where Chaf is the Hoffman
constant upper bound in Lemma 8. Then (00, 0) = O. and @(p. 7) is Lipschitz because
Pp]
| g) "(p',9') Schot M 111-111 ||
9
Schor
||
p
(D.39)
9
Next we prove the PMOL calmness condition holds by contradiction. Suppose for every c 0, there
exists (0, p. q) E [(0, 0) + <BB/((0, 0, })} satisfying (D.37).
Define 12p = (F(0)= E E(O, | TRO} + 0, there exists Ø RR9 such that F(0) E 2p, and [[ < 0C. We then consider the following two cases:
Case 1: F(O) E (0, 0). In this case, (0, p.p g) (0, (0,0,0) # (0, 0, 0), thus # 0. Take ē = 0 + 0.
Case 2: F()) & E0, 0). Take Ō such that F(0)= E QF, then F(Ō) / F()).
In both cases, let 22 be the convex hull of {F)(), F())), i.e., UR conv(((()). F())). Then OR is a line segment (or reduces to a point in case 1), thus a polyhedron. Since E0, 0) is line, F(O) E (0 0) R2 thus E( 0) n 22 = Un = { (F(0)} } in case 1, and Σ(0, n S2 = (F()) in case 2. Therefore, in both cases,
[[F(Ō) F(O)) = dist (is)(((()) E(0, ((00) nda)
(D.40)
where dist(F, = inf |F-FF'I
24

---

We also have
(a)
[B, + b2)+
dist(F(0), (() ann)
Chof (2x)
B₁ F(F) + bn.
(-p)+ q
[p)
Chaf
S Chof
(D.41)
where (a) follows from Lemma 8; (6) follows from (D.37) that 0 < (B)F(0) + by)+ S (-p)++ BR (0) + by -,, and that Chof (52)) S Chof for different bounded f2g. Multiplying || M on both sides of the above inequality yields
(F(0) ((0,0) (Z) S Ad(p.g).
(D.42)
can then be derived that
AF AF(O) S AF AF(0)] S (AIIF(()-F(())
Σ Alldist(F(O)) 0( 0) LR S Ap(p.1).
(D.43)
By rearranging the above inequality and applying (D.37c), we have that AF - AF) + Ao(p. g) AF(O)
(D.44)
which contradicts to that a global solution to (PMOL).
Therefore, the PMOL calmness condition in Definition 10 is satisfied.
E Proof of Theorem 1: convergence of Algorithm 1
Recall that, we let À (Ay; Ag; An] M Aag [A: By; Br] use the following concise notation
RMM++M and
d' (0) (V)( (0)
1 [VF(()) - crAT
s.t. (0) E min (();0) = xEl2x10)
(E.1)
M, where (0) 22, (0) x R x M. and 22,, (0) (A, E R 1 AF(O) AF)(
In the following discussion in this section, we first present the supporting lemmas and their proofs, then provide the proof of Theorem I.
E.1 Auxiliary lemmas
Lemma 9 is result from the smoothness of F(0), and thus the smoothness of G(0) and H()), whose smoothness constants depend on By and Bn, respectively.
Lemma 9, Suppose Assumptions 1, hold. Then all 0, 0' E R2, and all Ay E RRM, we have
- Sa.T)A))O d, laallA x/
a ||db]1
(E.2)
lτ.1
G(O++1) G(()) (G.V de
a
af
J
|l 11
(E.3)
2
f
H(O++1) ((.)) <a. (H)) de
a
B
bo. 11
(E.4)
2
Proof. By Assumption 2, it holds that AF(IB is |A |AT Xy 1222,, By the definition of smoothness, we have
XJ AF(0(1)) S AF(()) + AVF()) + A
aj P.
(E.5)
2
25

---

Let B g.m and Ba.m be the m-th row of Bg and BR, respectively, then by the smoosoossssssss of
F(0), B gg is f g.m I1- l1-shooth for all m E [Mg] Also because || || ll - [ loo.
where |BB 2o ma g. (0) is Br.llBy blo,, sm.oohh for all m [Mg]. By the definition of smoothness, it holds that
G(0++1) - G(O.) So. Sa.VG(O.) Td, d. + f o ox. 1..1
(E.6)
2
Following similar arguments as the above for G(Ø), (E.4) can be proved.
Lemma 10. For the subprogram (2.3) or equivalently (E.1). it holds that for any E (0).
VFT [0" cc,G(0) ( T( (²) 2 [VF
og X (0)1
(E.7)
Proof of Lemma 10. Since yo(A; 0) is a convex function w.r.t. X, by the first order optimality condition, it holds that for all À E S2x(0)
(V (A)(A(0) 20
(E.8)
which can be further written as
X Aag (F(O) (F( ( c. H() 1(A (1 2 [ (00)1 (E.9)
This completes the proof.
L
We next prove Lemma 11, which can be viewed as a descent lemma for [G(0)]+ and (0)lab based on the smoothness of G(0) and (0), well proper hyperparameter choices. This is crucial for proving the convergence result in Theorem 1. One key technical challenge in proving the lemma is that even though G()) and (0) are smooth, [G[0]]+ and ( are not. We address this challenge by exploiting the fact that (G(O,) d' (0.) S (B)) and (H.) d" (0,) Cg H (O,), as well as choosing a, properly depending on Cg and Cy-
Lemma 11. Let 2 0 be constant. Define [y]+ max 0} which replaces each negative component of y by zero, and lb replaces each component of y by its absolute value. Let {0, be the sequence produced by Algorithm I with the update Oct11 O. and where de satisfies the constraints of the subprogram (2.1) up to an error of e, i.e.
[VG(0.) de + cgGG(0))) S e1, (H())) de + (,) S e1.
(E.
(E.11)
If a min(cy' ch , then it holds that
f/ a B 1 ||d,11 c1
[G((e+1)]+ -GG(0)]] < (G())G(())]+ +
(E.12)
2
(H(0+ (0))laa < arca -
|0.0 ||d +el.
(E.13)
2
Proof. By the smoothness of G(0) in Lemma 9 and VG(O) d+ Co G(0) [= el, it holds that
رر 03 B |o,, | + e1
G(O++1) G(O.) Sa, VG(O.) d, +
2
f of BB ll |
S - a.c G(O,) --C,))(( +
dl
(E.14)
2
For all m E [Mgl, since G(O,) < [G((+)]++ it holds that
Im (0++1) (0r))+ Sgm (0.) - (gm (0,)) - arlggm (0:) + fイ1 a3 B + (E.15) 2
f a B oo.. 1| +c.
s (- a.cggm(( (0.)
(E.16)
26

---

It can be further derived that
= - ai ag (0)). 9m (0,) 2 0
- 1m-9m - CxCygm
CrCg)gm (0e), 9m (m((e)) < <0
S arCy Im (0+)l+
(E.17)
where the last incquality holds since 1 - 04Cy 2 0. Plugging this inequality back into (E.16), yields that when 9m (0c+1) O,
Iam (on0++1)]+ (0))++ -040g (m0)ggm(000)++ + l 0 11, i|del1 +e.
(E.18)
When Im (0c-1) have
Im (0++1))+ (mm(0))+ S -1mm S -ancglym(0))
S aacglem + f1 a, BB 1ldel1 +e.
(E.19)
2
Combining (E.18) and (E.19) proves (E.12).
By the smoothness of (0) and (O) d (0) E1, we have
[H(0++))las (0.) 0. (O:)) + { 0i [B |o,, || +e
2
f a B loc, 12 +1
- a(1- (B)))lb +
(E.20)
2
where the last equality holds because 1 arch 2 0, which proves (E.13).
E.2 Proof of Theorem 1
In this section, we prove Theorem Similar the proof techniques used [7], we use (F.))) with a fixed ' E S2, (0) as a part of the Lyapunov function, instead of using the dynamically changing Aj.t- This eliminates the need to assume the objective values are bounded above in our theorem.
Proof of Theorem 1. To consider both objective function minimization and constraint satisfaction, define a Lyapunov function below with a constant vector À = (Ay, Ag An) E (2( where A5 = 1,
Xg R Mr
An. RRM,, and Ag Xg (0.), An (0.) for all & [T].
V, J AF(O.) + X [G(O,)+ + +A (0.))
(E.21)
V
Vhat
Note that V, 2 for all since AF(0) 0, 0, 2
For notation simplicity, we let d; = d' (0,). From Assumption 2, the smoothness of the objectives, and Lemma 9, based the update 0.+1 0, + and,, it holds that
(a) V A141 V S aLTTAVF())) d, +
f at A 1bc.
2
A AVF(O.) di + 42 a A |l ||d 1d +1
(c) - - az |2 an ( cg (0)) T G(..)
l 222 1|/14/11 +e1 (E.22)
+ en (0.) H())))
2
where (a) follows Lemma 9; (b) follows from that d, is an e-optimal solution to the subprogram: (c) follows from Lemma 10 with x [y; 0; 0] (0) therein.
From Lemma 11, for a min c 13. it holds that
f at a 1|d,112112 ed
g.++1 V S -acc,,A,IG((..) +
(E.23)
2
27

---

L b-aa1113 l1 20,
Vh,411 Vn, - a,ch (M +
Idell
Xo 1 + 1.
(E.24)
2
Combining the above inequalities for f,,, q.,. Vh,ts we have
V++1 - V S - 04 12;1d + az (cg (1) G(O,) (.
lr a afll A11 - - aoo ((())labb + A
+
2
a4 |dīl| alcg (Ag -2(00)))) [(())) G(0)) - a1gg)((00)) -a0())))-aaa,00000 G-G(0)]++
o, (Ax (A(00))T(((()))) 411 af A ||111|1111 +eA
(B.25)
where the last inequality holds because (0) G(O,) =
Taking telescoping sum of the above inequality from t = ......T - and rearranging, we have
T-1
Σ (1 5 A 2 ldd;1++ (A, - 27)),) ( [G(0,)] + a (20,
1=
+ arp (2(0,)) (H V. V + T<A S Vo + Tc]AilI
(E.26)
Recall that S [1/(f,_]144gg Al11). Plugging this into the above inequality yields
T-1
Σ aanlldti + anco =
+ +,,,
+ ancan(An - - Vo Te|lAl,
(E.27)
Taking a ((), then
- (0:)1) (000
+c - ( (H = - -c)
(F.28)
The proof is complete.
Next we show that the subprogram converges with projected gradient descent (PGD) algorithm on with K iterations.
Lemma 12 (Convergence of the subprogram with projected gradient descent). At the t-th iteration, given G, let {de,eh be the sequence generated by the projected gradient descent algorithm to solve the subprogram minxeax(o)) sp(A; 0.), then
S | (0))11
((),,x;0)) min (A) (0)
(E.29)
2-
Proof. The result follows from the convergence result of projected gradient descent for convex objective functions. Note that at each iteration t, given 6,, (6x)))) is fixed.
Suppose Assumption 3 holds. Due to the l smoothstsssssss and the convexity of the subprogram, it holds for all X E (0) that
Lemma 13.
|V>x(A>;) (xP(A*(0);))) <
(E.30)
Proof. Since the objectives fma are Lipschitz continuous for all m E [M]. the subprogram objective p(\; 0) is f -moooh w.r.t. A. By Proposition (b) in [58], it holds that
[A (AP(AT(0):))11 + (O) x²))) s ((A: - ())
20 11.1
(E.31)
28

---

By the convexity of () w.r.t X, for all X E (x))), (Vxp(A)00;:)) À (²)) 0.
(E.32)
Combining the above two inequalities proves the result.
Corollary 14 (Convergence of Algorithm I with K-iteration PGD for the subprogram). Suppose Assumptions 1, 2 hold. Let {0r} be the sequence produced by Algorithm with the update f--1 0, + ord, where de is the e-optimal solution to the subprogram (2.1) obtained by K K-iteration PGD for the subprogram on X. Define X = (Ax, >g. Xn) E (2x(0) with Xg 2 Xg(0) + +1, An 2 ())
for all 0 R2, the step size at I 1/(CgaalAA 1 and a; (1), then
T-1 E cy(2, - xg(0)) (;(0) c,)((0,)) +,NN00))--(0)))
(An - 22 (0))) (H())aa = 0(1)
(E.33)
Proof. = .,..., T 1, we take K = 2 applying Lemma 12, we have
((Ac,x(0.)) - min (A(;0,) || - (0.))? xe0x(0.)
(E.34)
277"2
From Lemma 13, the above inequality implies
[Vp((A)))) V=((A((0): s 2l. -(((s))))))((((()))))))))))))))) = S fex.1l/e-11 (0.)
7/22
(E.35)
Plugging in the gradient Vep(Ar;Oe), we have
[AVF(O)) (d. - dz)ll + ( Td, (d,-d,) (d,11
11111 (0.)11
16
(E.36)
7I2
7222
Let c = 46, 103 72
from Theorem 1, it holds that
V4+1 V. 5 -arlddi11 ar (1, A1n) [G(0:)]+ x,000 [=00 (-(00))
+ + (2)(0)) >n)) (H + + + "arlllV 01)2
1
f a I Alla 1|
2
(E.37)
Taking telescoping sum of the above inequality from 0..... T 1, rearranging, and letting ar I x1/[IA|] f,, A A I),, we have
T-1 Σ
Eaalldd1 1ll + arcg(Ag
+ +
cnon(An (T(0.)) V + Teb.
(E.38)
Letting 0g = 0(1, = 0(1) yields
(01),-=600
|, 11 xx(01) +,x(0))))))+
(An - (z.) (H()))a = 0(1)
(E.39)
The proof is complete.
29

---

Proof of Theorems 2 and 3: convergence of Algorithm 2
In this section, we prove the convergence of Algorithm 2 with single-loop updates. We focus the problem with equality constraints only, i.e., Mg = 0. Furthermore, we consider the simplified subprogram without adaptivity to the objectives, thus 22,, (0) = -AM.
We provide two theoretical results in Theorems and 3, respectively. Specifically, Theorem 2 uses the same merit function as Theorem I, but provides a slower convergence rate. Theorem uses different merit function, and provides faster convergence rate than Theorem 1 under additional assumptions.
F.1 Auxiliary lemmas
Lemma 15 (Smoothness of w.r.t A). Suppose Assumptions I and 3 hold. (xx;; 0) s w.E. X, with 1xx.11 = AnglAng
Proof. The Hessian of sf(;; 0) w.r.t À can computed by ())=0)) = Ang VF(0) VF(0)A By Assumption the Lipschitz continuity of F, holds that (A; & || VF(() T (F S IVF(()A S AllAagl 1l.
The result is proved.
Lemma 16 V ( 0e)l is bounded by [dd]]). Suppose Assumptions I and 3 hold. For {0,}
produced by Algorithm 2, we have
[Vx, s || |lAT 1y
(F.1)
Proof. The gradient of (p({;; 0c) w.r.t. Xy can be computed by
Vx, (A,;((e;6))) 0.) AVF( (F) AVF((H)) de
(F:2)
By Assumption 3, it holds that
IV ((x; ||A 1
(F.3
The proof is complete.
Lemma 17. Let 7; Drr d. Consider the sequence Then for all X E Q2 (0,) with X = (Ay, An). it holds thut
{ generuted by the update (3.1).
(7c(Ag. 'y. V ((,s 0,)) ||A Ayl1² || A1ll² V (Ax 0,)1;
2% Ano VA, (Ae; 0:)) ||A,. -ha.--Aa11 1|A..11111111111---- - - V (Ax 1.1. (F.4)
Proof. By the update of As and the non-expansiveness projection, for all Xy M, have
|| - 11 s a - Vx, 11 =I|Ar,- - 1, - 2 (Ay 'y. (A,;(),;))) + ((A (,
0.111.
(FS)
Rearranging the above inequality proves the first inequality.
By the update Aa,t, for all constant A E MR, we have
| A = [|(An, 7i XA, (A,;0,)) - 1t11
-An, 11 222 Vx, (Aee 11 (7/(hn. Ano Aa (p(a 0.).
(F.6
Rearranging the above inequality proves the second inequality.
Corollary 18. Let A (A An,el. Consider the sequence 12' generated by the update (3.1).
Then for all X E Si with X = (xf,)u). it holds that
()(((((;;; (.)),)) < 1| 212 ||++1
All 7 (A;
(F.7)
Proof of Corollary 18. The result follows from combining the two inequalities Lemma 17, and applying the convexity property of ip w.r.t. X.
30

---

F.2 Analysis with the same merit function: proof of Theorem
In this section, we provide analysis with the same merit function as Theorem 1. The proof follows similar ideas of the proof' of Theorem 3 (for convergence of the subprogram with the approximate single-loop update) and Theorem 5 (for convergence of the main program) [7]. We follow the
proofs in [7], as they provide, to the best of our knowledge, the fastest convergence rate guarantees for single-loop MOO algorithms under minimal assumptions.
Similar to [7]. we first define the following auxiliary functions to assist our analysis. Note that the functions are only used for analysis but not for the algorithm update.
P IIIIP. x2)0) (p(A: ((): 0) 2
arg min (p) XeΩ,
(F.8)
We then present the following Lemmas that are useful for the proof convergence of Algorithm 2.
Lemma 19. Suppose Assumption holds, and X" (0) and (7) are bounded for E {00))-0 produced by Algorithm 2, i.e. [[)* I cx [ S cx- Then on the trajectory of Algorithm 2, with 0 (0.) we have
(XZ(00): - (x) P 2x
(F.9)
Proof of Lemma 19. The proof follows the proof of [7, Lemma 13].
Corollary 20. Suppose Assumption 3 holds, and X" (0) and x2 are bounded for 0 E {0:) produced by Algorithm 2, i.e., [|^* S ox [ S cx- Then on the trajectory of Algorithm with 0 E {0.)7=> we huve
T-
Vx,, s 26 26.x. -((]((AA))))(((()))))))))))))))) LPx
(F.10)
Proof of Corollary 20. By applying Lemma 13, and that VA, (AA(((0) 0) = O. we have
V ((,; 0) = V A. (Ax:))
[Vxp(A;)) [0)()=(0):)11
Lemma
26xx.1 (v){:
min 6)): 10Rx(0)
(F.11)
Applying Lemma 19, we can further derive
(p(;;) min (0)
(();0) =x(>; (x)x + +(2;00): ,(>;(0):0)
Lemma
(xx; 0) ()))(0):0) + 2 x
(F.12)
Combining (F.11) and (F.12) yields the result.
Lemma 21 (Continuity of (²)..). For (0) defined in (F.8), and (0) = 22 the following holds
[| -,70)(x)7(00)))) (0)) <P 11 VV (X)(()()))
22p 2
8'|1.
(F.13)
Proof of Lemma 21. The proof follows the proof of [7, Lemma 12].
Lemma 22. Suppose Assumptions 2, hold. Let (0t), {2}} be the sequences produced by Algorithm 2 with step sizes an = > 0, 7/ = 7 > 0. Assume ||* (6.)). 12;(0)) Mell s Cz. Then
for any p > holds that
T
20
T
Σ t=0
(.));))) -(A;()))))) < (1 + 2p - aT 13 11,
)
7
(xp((A::0)11
T
7T
og
2T
(F.14)
31

---

Proof of Lemma 22. The proof follows the proof techniques of [7, Lemma 15].
First, applying Corollary 18 and "/t yields
(7(((>,; 02) (A))(0)); 0,)) < al (0))1 M X2(00)1
(F.15)
Taking telescoping sum of the above inequality and rearranging. we have
T-1
T-1
Σ
(();; 8x) -(2)()))) -
X2(0))l2 - 11 - x2(0))12
T 1=
2yT
J1
+
IV [AP(Ac;0))]1
(F.16)
27
where J1 can be further bounded by
J1 31120 x2(06)11
11T 1,(0--1)11 +
Σ
22 22(0+-1) x((0))1112((0--)) -2
(2)))
T-2
<40 4ex
(A7(0+1) x7 S 4 86x
Σ t=0
p aely,1 o |ddel]
where the last incquality follows from Lemma 21 and the update of 0,.
Finally, taking a = a, plugging the above bound for J1 back into (F.16), and bounding ||dell by Assumption and that || Cx prove the result.
Proof of Theorem 2. We consider the following Lyapunov function with a constant vector À (}y; Aa] 22x where Ay AM. An
E RMM
V, = AF( +
a0
D$ Arl1
ao
| Aall2 XT H(0)) + ov [H)0h
(F.17)
270
270
VA
Vniz.e
Vxya
Van.c
Vh.c
Vx.6
DAya: An,a), and the algorithm takes the update 0.11 = 0g + and, with d; = (F. From Assumption 2, the smoothness of the objectives, and Lemma 9, the function XJ AF()) is smooth, thus
Recall that d
1,.1-VVA V, S(VF(O))) 0.11 - 01) + Le1 | Xy11111 - 0a1l2
=a((VF(()) (TAR))AT,,,,,, d,) L1. az Ay1h
(F.18)
By Lemma 17, taking Y > and rearranging, we have
1
(VF(O.) X dr) < (IAr. 21 -1
2%
2 (x,[VV, (A Vx, (()c:
(F.19)
Combining (F.18) and (F.19), and choosing = for all t E [T], we have
70
V V + VAy VAyu
f a Ayllu|dl1 + + (anilVA,,A(AA - (A,)(A,;0)).. 2
(F:20)
By the smoothness of A, (0),, and VA, P(r;0)))) = VH(O)) -
cy. ((,,) it holds that
V VA.1 (H) d. + f,.11 a3 B, X, |1,112
2
32

---

a. H(0,)) 41 ai B > ||1
2
(A,, VAn ((2; 0t)).
(F.21)
Bounding the last term in the above inequality by Lemma 17, and taking V/ > 0, we have
f11 az B >n |dell 220h 2 An 0
V1,10+1 V1,1, an H(O,)
aa Va (Ac 0o)) + ai (IIA.. Aall 1| -10-- 1n.13). (F.22)
27
Adding up (F.20) and (F.22) yields
V F + VA Vx 11111+1 14,1,
1 S S- ar xxx (+); + 2 n Vx 0.)1 - - H())) + f1 o
0i 1 1111//111
2
L1
S - --ailld/12 arc (An. - AN) (0))) + 2 n Vxp(A; +
2 a
A
All ||
2
(F.23)
where the last inequality the fact that (Ae, Vxp(Ac; 0.))
Using the fact that VA, ((A;; 0z) (0.) T de cn (1 (0.). and with similar arguments as (E.20)
in Lemma 11, we can further derive that
+ Cx af 11 bc.1 |d/l=11
H (O++1))aa (0H( o,,,H((0) a, Vn
L11 41 = bx0 110.1 ac VA, ((n, 0z)lab (F.24)
5(1 - (0)))) +
2
Therefore,
f/1 ev, M,a 1lo0, 114.11 arer, VR, ((A;) 0c)1
W1,2,111 V1 S -0cchor,1HH())))
2
(F.25)
Combining (F.23) and (F.25), and by choosing step sizes at, Ths parameter cv, such that
f ev, Mn [B 11,0,1 f a A A/12 s 2'
1
(F:26)
2
we have
1
V4+1 V. -
2 aullddll2 - area(ev - DA (0))ll $ maalt + aven ll VA, ((A:; 0.)1
(F277)
Taking telescoping sum of the above inequality over t = ,,...,T - 1, and applying that (X,;)1)) S VA, ();;) we have
1
Σ V41 V,
0 |d]1|22 (eca 1| (n.elli)) + 2 noal
t=
+ auev, / MA ((ii))))
(F228
where 7T-1
A can be further bounded by applying Lemma 22 and Corollary 20 along with Jensen's inequality follows
VA (():)))))) S T Aa 0())))))1
T
Corollary 20
T-1
24px.11 (v))e; +(2)(0.):0:)) + Ppx
7
33

---

Lemma 22
1 46 pl 2 ITT
T-1
-
(1+ 2p
Vxv((A;; 0:)1 + plex,10s
27
(F:29)
where [V 02] 0,)]1
|V (Ax;;(A;;;))))))) + V 0:)12 x VV 02)1 ||de|| Plug-
ging the above inequality back into (F.28), choosing p = ( and rearranging yield
|dlll (0 (+T at (TT) + ( +7)+
(F.30)
t=
Choosing a = 0(T 8) = b(T proves the result.
F.3 Sharper analysis with a different merit function: proof of Theorem 3
In this section, we provide an analysis of convergence of Algorithm 2 with a different merit function and faster convergence rate. We first present the auxiliary lemmas and then prove Theorem
Lemma 23. Suppose Assumptions I and hold. For {02), {he) produced by Algorithm 2 with Mg = 0 and f2y (6:) = A M, and for all = 0, 0...., T, |dell can be bounded by
||d. < e/.1ll 11 + |),,olla,
(F.31)
and || Vxip(Ae 0,) can be bounded by
0x)ll s Aag 2 Med (
(F.32)
Proof. Since de ((;)) de, we have
|d VV Arl Arl S Eeall S E/aal4 + (Aaell
(F.33)
which proves (F31).
Furthermore, invoking that Vxi(AAr;)) 01) = Ang TF())) de ca (0:), we have VAp(AG 0,)112 = |gg (F.))) e. (0,))1
22 Aag (F.) d, + 2| ((,)) < 2| Aag 11 /eMe 20
(F34)
which proves (F32).
Lemma 24. Suppose Assumptions 1, 2, and 3 hold, and Mg = For {0c}, {1+ produced by
Algorithm 2, further assume {AE,t are bounded the trajectory. i.e.. || 1l S Cds- For all and azll ((0,)) S Ca.h for any O <
Co.b t O,...,T, choose such that I E,,al AiIlo(
Co.b < cc, then holds that
1 H (6 ( S TH(())))THH))) de a
with 41221,1 = Bx 2(a + CH) Me Ball, and LH ||BalI Mey (F33)
b Proof. By choosing S Ły,1 1. All)) and invoking (F.11) in Lemma 23, we have
arl/dell < Ca.h-
(F.36)
By the mean-value theorem, for all t O,..., there exists 0, such that
-= |H((0))) T.H(H))))THH(O)) d, a =
(F.37)
The term (())) (()))) can be upper bounded by
(H))) ((θ.)) <2 =H(
34

---

S2M 2
(F.38)
Since H (0.) is Li--iscchiz continuous with en [BallvMef and 02 lies on the line segment of 0, and 8141 with [0(+1 - 8ell = az [del]. therefore,
(())) - (0))l + axeHIldel & [H{ + CaC Plugging the above inequality into (F.37) yields
(F.39)
- - o,2H (V.)) (2 ((.))III
(T.) de - 2 2M (M 1 1 + 2(a +HH) 2 MM 1B |ddl1
(F.40)
The proof is complete.
Lemma 25 (Smoothness of i w.r.t. 9). Under Assumptions 2, 3, 4-2, ()); is f w.r.f.
0 for all X, 0 on the trajectory of Algorithm 2. with Epp.1 ( + (x2 All + Ba CN || |B fl
Proof of Lemma 25. By the definition of yp, its gradient w.r.t can be computed by
Vop(A; = (VF(O)AT A) (FF(O)(AT)))
^, (0).
(F:41)
For brevity, let = Aug A. Then for any 0, 0' E } on the trajectory of Algorithm 2, V/V)))(A;)) Va l'll can be further bounded by
|| (o 0) Vop(A; II S - =F000/11100
+ +IVEF(0")|I| - V= +a/ - VH()'I (Me, + , +
0'1l
(F.42)
where the last inequality follows from Assumptions 2 and 3. Using the fact that X, E AMM, and |A.all S Cx. on the trajectory of Algorithm 2, for all À E {Ae] on the trajectory of Algorithm
||||| AAg All can be further bounded by
| = | + [B, Aw I |||| + ||
(F.43)
Plugging the above inequality back into (F.42) completes the proof.
Lemma 26 ([53, Lemma 4)). Let Q2 C R.M be a closed convex set, and let ll denote Euclidean projection Q. Given any À E Z2 d E R.M and y O, it holds that
1 11
I1(A - -d) arg min (d, X²) +
(F.44)
Xen
2
Lemma 27 (Proximal PI. inequality implies proximal error bound and quadratic growth). Suppose Assumptions 3, and 4-1 hold. Then for X, on the trajectory of Algorithm 2, (x(x; 0) + (\)) with g(A) being an indicator function defined the set Px, satisfies the E. -roxiimaaal error bound (EB) and the 1 v. quadratic growth (QG) w.r.. for some Pups 1/g2 > 0 depending on pup. as defined below
- 1 1l (1 [V(({:0))
(A,
(proximal EB)
(F.45)
Php
7
1
dist (A, s (():0) (()) (QG)
(F.46)
1/
where (0) = A ((>; ()))
Proof of Lemma 27. By Lemma 15, ()x; is smooth w.r.t. Furthermore, by [28, Appendix G]. and combined with Assumption 4-1, the proximal PL. inequality, it implies that (p(A0) g())
satisfies the proximal error bound. From [10, Corollary 3.6), the proximal error bound further implies the quadratic growth, which proves the result.
35

---

Lemma 28 (Lipschitz continuity of X (0), [53, Lemma 5]). Suppose Assumption 3 holds. If given E Szy and 0' R (p(;; 6") satisfies the _ proximmal evvor bound w.r.t X. Then given R', P. for any X (0) E arg minseR, ((); 0), there exists X" (* E arg minxest, (x(2; such that
(x) - (= = 2x- ||0 -01l
with εx- = -exx. and lep.11 defined in Lemma 15.
Lemma 29 (Danskin-type Lemma for proximal PL functions [53, Proposition 6)). Suppose Assump- tions 2, 3, 4 hold, then ((X*((); 0) is differentiable with the gradient computed by
Vi((> 0) Vo AA E arg min (p(:; 0).
(F.47)
XEOx
Moreover, cxx* (0);0) is f-m.ohh with lir,11 = l, lx.)
Below, Lemma 30 establishes the approximate descent or contraction of the subprogram after taking one-step update on Ac. This is crucial for sharper analysis of convergence of Algorithm 2. Lemma 30 (Error of subprogram). Suppose Assumptions 1, 2, 4 hold, Mg 0. and 22, AM
Let {0c), } be the sequences produced by Algorithm 2 with step size 7/s S (2.11 Then for any
Cp.d > 0, the following hold
((A++100)) - (((* (0:); S (1
(()=)());
(F.48a)
((A441:0411) (p(A (0+11: S (1+ ac (4)
(v(()41: -(x
20pd + lxnnt ler ot)
at
12) |d..1.
(F.48b)
2
Proof of Lemma 30. We first prove (F.48a). Recall the definition of (A; in Definition 3. By the -smoothhsssss of & w.r.t and the update X and that 7 {-) 1x,1 we have
(1) S ((ri + (Vxi(Ar 0z), Art1 Ao) + ||A4+1 - Xell
27
Tt Pan (ee; 0c) by Lemma 26 and Definition 3
Spp(Ne:()) 2
Sp(Ae; 06) 70/4 (v(::: 0.) p (0c); 0))) by Assumption 4-1 and Definition (F.49)
where the last inequality follows from the proximal PL inequality. Subtracting both sides of the above inequality by (A* (0:); 0:) proves (F.48a).
Next we prove (F.48b). We decompose the error on the left hand side of (F.48b) by
((AA4110041) - (A)
=p(Ac41i041) 0141)):044)+00 (8+1)))))) - (p()ec1:::)))))) -(x (o( -
())(()));)))
(F.50)
where we use the (kyp,1 + bar ( smmoohhsessssssssseoooo.ee. of -));;)))((((()))))
w.r.t. further bound J1 by
J1 < (Vop(A(41:8) - 8,41 01) + lpo.1 + l
1
0ell
2
de) + (xpo.1
+ l
< -a 0.) -
ai
a??(de|1?
2
0.) V=((> l
l
S
a
(F.51)
2
Then we can further derive that
Jn S
(0) arC.pd
V Vop() vp((A+(0):0..)11 20
at
||d,
112
+
36

---

2 14 ((o(A++1;0) - ((A((()): +
2dpp ||d,12 1 +
at
lpo.1 + lo-.1
a aflldil1
2
(F.52)
inequality, and (b) holds because where (a) is from Cauchy-Swartz inequuuaalt
Vopp 02) - (o:()"0::) 0,)1
I ("
by Lemma 29 and f continuity of Vo
Sbg (f((e+1: 02) - pp (6,);
(F.53)
where the last inequality follows from Lemma 27, the 1 -uaddraticc growth of (p::
Finally, plugging (F.52) back into (F.50) completes the proof of (F.48b).
Corollary 31. Suppose Assumptions 2, 3, 4 hold, and Mg = 0. Let {0c): {de} be the sequences produced by Algorithm 2 with step size 7tt S 6,2 Then for any Ca.d > O, it holds that
(p(Ace1; s0A" (0++1):0e+1)) - (s(()e; (()> (1 (1-(m)))
7p16)) -1 (p(() ((x' (0))
at 20ipp
loa.1 fot oz ||d.11..
(F:54)
Proof of Corollary 31. The proof directly follows by plugging (F.48a) into (F.48b).
Lemma 32. by choosing ot min { Sachh [H(. Ca with O < Ca,h: Co oc, and from the algorithm update and properties we can derive on [0 O(1) is bounded, then (0))l is bounded.
Proof of Lemma 32. We prove by contradiction. Suppose [|H()))] = (1) is not bounded, then
02 = min {
(H( Ca =
Ca.b
Ca.h
(F.55)
Furthermore,
a. (o.) -.,A (|,,)(()) = 0(1)
(F.56)
which implies [0.)l (1)) and contradicts with [0.) w(1). Therefore, we have proved [(())) is bounded.
Remark 33. Lemma 32 uses the algorithm properties to prove that (0:)]] is bounded, instead of directly assuming (0.) is bounded. This will be used in the proof of Theorem 3 to show that [H)))) is bounded on the trajectory of Algorithm 2.
Next we proceed to prove Theorem 3, the sharper convergence of Algorithm
Proof of Theorem 3. We consider the following Lyapunov function with a constant vector Ay A
V. = AJ AF(O.)
ao Dd
Arll² + (T.
[[.0) + 0.) p(A'(00)::0)
270
Vya
Vays
Vn.0.
Vasa
V
Vn,e
(F.57)
Following the same arguments from (F.18)-(F.20), and by choosing we have
1 for all E [T].
cy..
Mf F + VAy,e x,
f111 a A Ayllil|d /t/p//alllttggollll///aaaala -a/A vAyp(Ar;0)).
(F.58)
37

---

Similarly, we can derive that
f1 aj aB An.elli/d.11 ar(den Van (A(e;;))))))
V1,0,+1 Vh,o,t I - - ((.))
+ (An,0+1 \n.1) ((,)).(()).
(F.59)
Combining (F.58) and (F.59) yields
S - 5 + Vay.t+1 Vay. + V4,0.+1 - Vn.0. S -ai Idel2
La A Aylli + +1B,, An.lll)dddel 26 Va H(.)).
+ =2 Va
2
(F.60)
Next we proceed to bound V1,3,++ VA,3, By Lemma 24, it holds that
W13, - V1.3 S (O,) T (O.) d. + +
(F.61)
where (HE_1 2M 2(a, Ca.h (arca)MMfr Because VA, - ea (0,), the term H())) T (0.) (0,) de can be further written as
H(0,) V (6;) de H(,)) T AV (p)(; + ccH((())) (0.) H(O)) (xai()ri
(F.62)
Plugging (F.62) into (F.61) yields
1
1 a N2 1,
(H:) VV ((A) + (( (0x)) -aych ( =
2
(F.63)
Letting - - ( (IIA + [B c,,)), and adding up (F.60) and (F:63), we have
V 5, V, V Vxy. Vn.t+1 Vn, -as || -a.//dell
o. 1 (0,))l 1
-(ar 76) V., 0,) (100) " ((ee; 0,)1 + 2 + 1aa,11 (F:64)
where // 01) & V (A: 011 is further bounded by Lemma 23, (F.32) as
V 0,) 11 s 2 Aap 1 MM,, +2
(F.65)
Plugging (F.65) back into (F.64) yields
V f441 V + V W
Vxyit + VA,t11 Vn S =auldeel| - 04 (0.))
(a: + 71 VA, H(00)) (26rHH1 + 1H2,e,))ddel?
7r0el Ang 1 1dell + H
(F.66)
J2
where by choosing the step sizes at S 2pm.tteme,, Nt S min ( 2cp f. holds that
J1 < az 1/d,1, J/ lll Ja 1
(F.67)
Plugging (F.67) into (F:66), and rearranging, have
W fa+1
5 + V VAysh+1 Vay.t + V - Vn,t
1
1
S 3 az
3 a,ch (+,))) (a, + +%) V (px;; 0.) H(O))
2
< an [/de (H (1+ Cya)² arl V (0>,;; 02)
(F.68)
2
Ch
where the last inequality follows from Sauchy-Schware incquality and that 7/- Cy
38

---

20..a Mi
By applying Corollary 31 with n S f2x.1 as S (oo.stheraaaa and Gya 2 further have that
we
1 V p.41 - V - - -(()))))))))))))))))))) + at
|dell..
(F.69)
Gp
Then note that from (F.11) we have VA, 26 ( (XX((()): Adding up (F.69) and (F.68) with properly chosen hyperparameters +1+ (1,c )2 Craa 4lead and
Pp
Go.d 4 yields
4+ V, ar C4 ((
Taking telescoping sum of the above inequality over / - 0, T - yields
[ call ( 4(Vo - Vr)
S4V n. (( XT,r + 2 4V 9,00 S 26g + 8Cx, eH
(F.70)
where the second last incquality follows from V, 2 0, choosing Xy = A1,0- and p 2 0, the last inequality follows from choosing Oo, Ag such that 2J AF(o). H (0o), (ooo 0o) - (0))(0));0))))
are bounded, thus 2 f.o + || (0o) 1|2 + p.
p.0 & co co, An. are bounded on the trajectory. and (0))), (Or) S cH. thus 4 ( H o (0)) H (0T)) S 8cA, CH.
We then summarize the best possible choices for (4 Te. Recall that we require 21 Rearranging this inequality with L B, E2 + 2(a An)ca,AMMe, Br and choosing Ca.
yield
AVME, [B,1|
(2(FH + 117,1,) 20 + Ma 1 + 11 anlx) $1.
(F.11)
Then we can choose the following ensure the above inequality holds
04 4(erHA + BI (3)) l.
(F.72)
To summarize, we can choose the following hyperparameters and step sizes
Sn 2 max { 88
4hxx.11 j: ca (1 + ), Ca.b
1
(F.73a)
Me
Php
4V Bull
7t Cy,ats, and au min
Co.A
max H(0))) C, Enalla (1 + cxa Hr 4lbpo.1 + bo)
1
1
Graloxa 1cy,a (Ag [2M,] 20
A(lFn, M. 1217)
ln (F.73b)
where (FH,1 = - || |icx))) and Eu = BBB Then it holds that
T-1
Σ or [Idell + cn (11001))111) 0(1)
(F.74)
Therefore, arch [ ( are bounded for all t = 0, O.....T T. Combining with Lemma 32, we have (ex)) are bounded for all 0, O.....7 T, thus we can choose a, 2()1, i.e., a, lower bounded by a constant.
Collecting the results above, have proved that can choose or @(1), 7 O(1) such that
T
[1dbl1 + (1((0))))== -
(F.75)
T
E=
The proof is complete.
39

---

G Stochastic Algorithms
In this section, we discuss the single-loop stochastic algorithm and its convergence guarantees. Note that, the extension of the analysis of the double-loop algorithm, i.e., Algorithm and the extension of the single-loop algorithm analysis in Theorem 2 to their stochastic variants with double sampling as used in [7], are rather straightforward, thus we ommit the discussion this paper, and only focus on the single-loop stochastic algorithm with equality constraints only, i.e., Mg 0, and with sharper analysis as an extension Theorem 3.
Let and ç' be i.i.d. random variables. The stochastic constrained vector optimization problem is defined as
min F(0) = [[))( s.t. H()) = [0) = 0, with (0) (0) + bn- (G.1) DERv
G.1 Algorithm summary
The stochastic algorithm is summarized in Algorithm 3. Note that, instead of computing Fe.. (0+), V (O)) which requires 2M gradient computation at each iteration, we compute Fe., (0+), (8.), (F ( (g))) which requires M + gradient computation per iteration. This saves nearly half of the per-iteration complexity compared to the most relevant existing stochastic algorithm for multi-objective optimization [7]. Furthermore, with the gradient-based single-loop update for d the approximation approach proposed in [34, Section 3.2] can be further applied to largely reduce the per-iteration complexity, which we leave for future work.
Algorithm 3 Stochastic FERERO-SA
1: Initialize 0, On, λn step sizes Or, 7ti
2: for -= -,..., T do
3: Compute the stochastic gradients F (0t), V (0t) Aggir dei
4:
Compute the stochastic estimate of the constraint Hg., (0.):
5:
Compute an update direction de = F (0t) ATg
6:
Choose the step size or by predefined schedule;
7:
Update Og by 0.+1 0, + arde;
8:
Update de by (3.4);
9: end for
G.2 Proof of Theorem 4: convergence of Algorithm 3
We first introduce the supporting lemmas, and then present the main proofs. Denote F, as the o-algebra generated by F.. (0o), VFa (01),..., Ve,,, where & = 1 (r,2). For brevity,
let [.[ = E[. Fe-1). Also recall that V the unbiased stochastic estimate of the gradient.
We make the following additional assumptions for proof of convergence.
Assumption 5. For {0e, Aet on the trajectory of Algorithm 3, it holds that
1. The variance of V F.,,, (8t) is bounded by o².
2. The variance of V xxpp(Mx dạ; 0,) is bounded by no.
The function (0x)] || is bounded by cH-
Note that the bounded variance assumption common optimization literature. However, for sharp analysis here, we additionally require xxp(AA; 0.) has reduced variance in the order of O(x:). which can be achieved using large batch size. Note that, even without assuming reduced variance, ie., Assumption 5-2, the stochastic algorithm still converges, which can be proved by extending Theorem 2 to the stochastic case using the same techniques in [7] for MoDo, double-sampling-beee based single-loop stochastic variant of MGDA. However, the convergence rate will be slower than -7 Here we use this additional assumption to achieve a faster convergence rate.
The following Lemma 34 extends Lemma 17 to the stochastic case.
40

---

Lemma 34. Let X₁ Dg,ti dn..]. Consider the stochastic sequence produced by Algorithm 3. Then for all À Ddy: Aal E f2y it holds that
2% (.,,, y, VA, ((es OOM [. Ayl1² || - 72 0,)
Ey An V 8: B. Anll 1111-11A,,447 || -all2 + v/ V (Ax:
G.2
Proof. By the update of X, it holds that
| Ap11² < AA vx, -
2y12²
= 2yl - 2% (Ag. Ay. (x,;(>r;;))) - P(A; 0.)11
(G.3)
Taking expectation the stochastic samples and rearranging the above inequality, we have
Bx >, Vx, 0.) 0x))( 2n.B. Xs, (ayi((e; 0.))]
<BalIAA 2,| 11 >,l1² + 221 (A,
(G.4)
Following similar arguments, it holds that
27 - An ((e;
<B, Al Aa |1 Axal + ((,
(G.5)
The proof is complete.
Lemma 35 (Restatement of [50, Lemma 21). Let ((x) ((x) + h(x), where 4p R2 + IR is L-- smooth, and It + IR is nonsmooth but convex and relatively simple. Define y = prox,h (x 7dd" for some d' E R9. Then for y, the following inequality holds for all E Rº;
( S (y 2, Vi(x)) -d')
L 1 _ Ily - x=12
L 1 }1|2 27
1 _11 2112.
+
x112
(G.6)
27
27
The following Lemma 36 extends Lemma 30 to the stochastic case.
Lemma 36 (Error of subprogram in the stochastic setting). Suppose Assumptions 1, 2, 3, 4, 5 hold, and Mg O. Let {0.), {he} be the sequences produced by Algorithm 3 with step size 7 S px.1
Then for any Ci.dd > 0, the following hold
Elp(A++1;0)) 0.) (xx** (0.): 0.)1 S (1 71 0z) -0\> (0:; + t2202
(G.7a)
E(p(()41:: 0141) sp(* (0++1) 0142) 1(10)=$+000)) (1+aicpaa ( Bi) -((A 0))
On
Exp.11 + Eir 0i E E[IVF((A))
l + tpp a.?0
+ 2Cppd
2
2
(G.7b)
Proof of Lemma 36. The proof follows most of that of Lemma 30. We highlight the difference.
First we define X = Ho (Ne (xp((((;e))) as an auxiliary variable. By the -mmotthsss of (): we have
E(p(M (lp((A,; 0.) + Resd = del1
(G.8)
7t
Applying Lemma 35 with y A N411 de, and that de, Ne,1,1,,1 N441 E Sr yields
(pppa 0.)1 & E 2//ppAlea: 0c) + (Ae41 Neni vxp(Ar;;)) - {xp((Ar;))))
ber
1 1lleee+1 dell + bexu 1 1 >ell
1 || Xar1?
2
27,
2 2%
2%
(G.9)
41

---

Furthermore, following similar arguments as (F.49), by Assumption 4-1, and taking total expectation,
we have
(l (1),: ((A,; 0,) - THo -((()))))(((()))))))))
(G.10)
Adding up 1 (G.8), 1x (G.9), and 1 (G.10) yiclds
Elyp(A+11 8.)] SE p(Ac; 06) 56pm111 1
)11 - -oll2 Epx.d
1
-11 - dell
6%
2%
MOTI (p: 0e) (0(((0));:)))
1 -X+111?
27/e
+ (Ae+1 No+1 VA 0,) (Ai 0.)33
(G.11)
Choosing > 2 Tuga 2 Sea.11
and applying Cauchy-Schwarz and Young's inequality, we have
E Elp(A++1: 0.)1
< (((A))))) 0.)
M (p((c;:)) -(x)(0)))
3
+ 7 (x,(A( 2
(G.12)
The first inequality is proved. We then prove the second inequality. Note that (F.50) still holds here. Following similar arguments (F51), [[J]] in (F.50) can further bounded by
ar (Vooo((Ae 0.) V=((A laa.1 + + all11
B[J]] < E
2
+ lpo.1 + l ai ai de
E
or (Vop(Aett; (O))
2
6po.1
+ tpp
E
az
a #1lde11
(G.13)
Then following similar arguments in (F.52) and (F:53), we have
B EEEEE ar d 1 (al.a//((((ee))) (0())+110)) p(Ar(0)):
at
ag
E + Eop
at ||d]]l]]
(G.14)
20ppd
2
Plugging (G.14) back into (F:50) with total expectation completes the proof of the second inequality.
Next we proceed to state and prove Theorem 4, which generalizes Theorem to its stochastic variants, with matching convergence rate the unconstrained stochastic MOO algorithms and stochastic gradient descent. This allows us to apply the algorithm to large-scale machine learning problems, which detail in Section 5. Its proof also extends that of Theorem 3. We ommit the similar derivations and only highlight the difference.
Theorem (Convergence of the single-loop stochastic FERERO algorithm). Suppose Assump-
tions 1, 2, 3, 4, 5 hold, and Mg = 0. Let {0.). ). (he) be the sequences produced by Algorithum with A = I and Sxy, (0) A (c.f. Remark 4). With properly chosen step sizes at O $
7 = - 3) holds that
(F(00) [[(())) (T
E
(G.15)
T
Proof of Theorem Reuse the Lyapunov functions defined in (F57). Let A = [Ayas A,,)]- The algorithm takes the update 0.+1 0, + orde with d, = (0.,,.0 ATT Av. From Lemma 9, the function AF(()) is A TTallATliaaa -mo-shoohh. Then following similar arguments from (F.18)-(F:20),
42

---

choosing
1 for all t E [T], and taking total expectation, we have the stochastic version Esya
70
of (F.58) below
S.441 - VA + Ay,0+1 - Vxyaal
G [ 1
-.. Vx, (G.16)
The stochastic version of (F.59) is
B - Vn,0,l S BiChEIAT,HHON + f,1 a I0,, 11c,, 4[1
2
a -, A0 0z) H(O))) (G.17)
By Lemma 24, and that ((ni() = V1)(0,) - - (0r), the stochastic version of (F.63) is
V - s TVH(H)
VH(O.) T VF.., (0)) ag ag Ad + 1 ,
S )
T VA. (,1;
(G.18)
where
11PT111 = 1 = B, + 2(CH (HCO,,) M6 BBll by Assumption 5-3, and tH [BallVMe, Let CFH,1 f,, (I 1| + |B] 1l,.) Adding up (G.16), (G.17), and (G.18)
yields that
11411111 f, + Vxy,1+1 Vxy + VA,++1 Vn
4 (26 + 11 - - Vxy(A 0x)1] - 0.Ch E[A H(C,) H(0.)
-arckE]] (ax + + ((,, 0.)] 2 1I ( 0.)
(G.19)
Further rearranging the above inequality, applying (F:65), invoking that 7/2 0t, and choosing
ae S min
p MMC 201.7.a S have
B 114111 - V Vay,t+1 - Vx,,t Vh,th1 Va.d
2 30 -
1
(1 cra)
(
PA. 0:)1
ch
+ + 2 22 + (2p + 10
(G.20)
By applying Lemma 36, and choosing 0; S min Ppr. +ho slood
Mig
and Cy,a 2
20 a.. the stochastic version of (F.69) is
E Vo.el <
2 u ( ((A)())):)))
ax
E VF
M + (1 + 2
(G.21)
Go.d
Adding up (G.20) and (G.21) with properly chosen hyperparameters C₁ 2 (1 cy.a), C.aa" 2 Hy
16ax
and Cp.d 4, we have
V.J < 1
1 1 B(
E[V411
+ (1 + 20 2 + ( + و ,) azO²
(G.22)
With the same hyperparameters and step sizes summarized in (F.73), one can choose a O(T- +) to obtain
= o(T
=
(G.23)
The proof is complete.
43

---

H
Implementation Details and Additional Experiment Results
In this section, we report the additional implementation details omitted from the main text in Appendix H.1 and the additional experimental results in Appendix H.2.
H.1 Implementation details
Computation. All experiments were conducted on server with an Intel 19-7920X CPU, two NVIDIA A5000 GPUs and two NVIDIA A4500 GPUs.
For all the experiments reported in the main text except for the multi-lingual speech recognition experiment, we exactly follow the settings from [41]. The implementations of the baselines including LS, PMTL, and EPO are from the official code of the EPO paper in https: //gi thub. com/ /bmppt// EPOSearch with their default hyperparameters. The results of XWC-MGDA directly referenced from the paper due to lack of official implementation.
Synthetic data. For the results in both Figure 3 and Figure 4, the model parameter 0 has dimension q =220, the number of objectives is M = The angles between the preference vectors and the horizontal axis are generated between 20 RT, 20 with equal angular distance. This experiment does not involve stochastic optimization. For our method, we solve the subprogram using PGD with a step size 0.1 up parameter Cy = for the subprogram not otherwise specified.
error of 10 or with maximum of 250 iterations. In the experiments, set the
In Figure 3, for all preferences and all methods, the initial model parameter 6g is randomly generated from a Gaussian distribution (0, 1) for each dimension. In Table we provide summary of the hyperparameters for the baselines and our methods for the experiments in Figure 3.
Table 6: Summary of Hyperparameters
for the synthetic data experiments in Figure 3.
LS
MGDA
PMTL
EPO
Ours Figure 3e
Ours Figure 3f
step size Ca max iterations
0.1
0.2
0.2
0.1
0.05
0.05
150
150
150
100
100
100
In Figures 4a-4c, the initial model parameters are randomly generated from uniform distribution between -0.3, 0.3] for each dimension. In Figures 4d-4f, the initial model parameters are randomly generated from a uniform distribution between [-0.5, -0.15] or [0.15, 0.5) for each dimension. Table 7 summarizes the hyperparameters for the experiments in Figure 4.
Table 7: Summary of hyper- parametrrssserrs for the synthetic data experiments in Figure 4.
Hyperparameters
Figures 4a-4c
Figures 4d-4f
PMTL
EPO
Ours
PMTL
EPO
Ours
step size Ote
0.25
0.10
0.60
0.50
0.20
0.60
max iterations
100
60
10
200
120
200
Ch
0.01
Multi-patch image classification. For fair comparison, we follow the same data splitting and processing procedures as [41] using their official code. In each of the three datasets, there are 10kk samples for training and 20k samples for testing. There are two tasks on each dataset: classifying the top-left image, and 2) classifying the bottom-right image.
For all methods, we the SGD optimizer with batch size 256. Note that, for stochastic method, we use batch size 128 for each batch in the double sampling. Thus the total number samples taken each iteration is also 256. The hyperparameters are summarized in Table 8. The results of XWC-MGDA are directly referenced from the paper.
We use the Pymoo 0.6.1 library to compute the hypervolume. The Nadir points, i.e., the worst performance on single task baselines, used for the hypervolume computation are given in Table 9. For fair comparison, the Nadir points we use are the same with [44] inferred from Figure 4 in the paper.
44

---

Table 8: Summary of hyper-parametee choices for multi multi-patch image classification experiments.
Hyperparameters
Multi-MNIST
Multi-atshion
Multi-FahhonnMNIST PMIL
LS
LS
PMIL
EPO
EPO
Ours
step size di step size 7V opochs
1E.3
1E.3
1B.3
1B.3
1E.3
1E.3
1E.3
1B.3
16.3
1E.3
1E:3
1E.3
1E.4
1E.4
1E.4
100
100
100
100
100
100
100
100
100
100
100
100
CA
0.5
Table 9: Nadir points for the hypervolume computation
Dataset metries
Nadir points, metrics on objective [I,...,
Multi-MNIST loss
[0.500, 0.450]
Multi-Fashion loss
[0.840, 0.800]
Multi-F+NN loss
[0.625, 0,575]
accuracy
[0.830, 0,848]
Huuti-Fashionn accuracy
[0.840, 0.800]
Multi-F+M accuracy
[0.790, 0.785]
Multi-lingual speech recognition. We datasets, Librispeech and AISHELL v1. Librispeech an English speech dataset that consists of 960 hours of labeled audio data. For our experiments, we the "train-clean- 100" subset of the Librispeech dataset for supervised training, which contains 100 hours of clean training data. Additionally, we use the full 960 hours of data for self-supervised training. AISHELL v1 is a 178-hour Mandarin speech corpus designed for various speech and speaker processing tasks. We use the full AISHELL vI dataset for both self-supervised and supervised training. We combine these two datasets for our multi-lingus lingull speech recognition experiments.
We use the conformer [26] model with 8 conformer blocks as the encoder. Each block contains 512 hidden units and 8 attention heads. Each attention head has dimension 64. The convolutional kernel size is 31. Two classification heads are used. They contain two linear layers, one with 1000 output size for English, and another with 5000 output size for Chinese.
The loss functions we use include the Contrastive Predictive Coding (CPC) loss, and the Connection- ist Temporal Classification (CTC) loss. The CPC loss [46] is self- sulf-vuper loss to learn robust representations from unlabeled speech data. The CPC loss is designed to maximize the probability of a future sample given a contextual representation generated from the current speech sequence. The CTC loss is defined as the negative log-likelihood of the model parameter given the input sequence and the label sequence.
Lo
6
A
(a) Without scale
(b) With scale
Figure 7: Scale invariance verification.
For all methods including the baselines, we use the step sizes 0t,1 = 5 x 10-4 for training backbone conformer parameters and 0,,2 = 5 10-5 for training classification head parameters. The step size 7 0.1 and the parameter с₁ 0.5.
H.2 Additional experiment results
Synthetic data. We conduct several additional experiments the synthetic objectives to further verify our theory. First, we conduct all the experiments on the synthetic objectives reported in the main text, using the single-loop approximate algorithm described in Algorithm 2. The results are plotted in Figure 8. The hyperparameters are the same unless otherwise specified.
From Figure 8a, we can see that Algorithm 2 with a one-step approximate update of X also leads to convergence and preference aligmment. However, different from the results obtained by exactly solving for A (0,) at each iteration, the models on the optimization trajectories do not align exactly with the preference. Similar observations can be found in Figure 8b. In Figure 8c, which a difficult case due to the initialization, A = Tas does not work since it does not incorporate more general relative preference to allow controlled ascent update. This is addressed in Figure 8d, where general A (the same as in prior experiments) is used. Compared with exactly solving for X (0:) at each
45

---

30
38
04
12
13
20
54
10
10
Standard
(b) Easy init.
(c) Hard init. A Inr (d) Hard init. general
Figure 8: Synthetic experiment results with Algorithm 2.
iteration, the approximate algorithm takes more iterations to converge, but has smaller per-iteration complexity, and smaller total time complexity.
Table 10: Summary of hyper-parameters for the synthetic data experiments in Figure 8.
Hyperparameters Figure 8a
Figure 8b
Figure 8c
Figure 8d
step size at max iterations
0.10
0.06
0.15
0.15
100
100
250
250
Ch
6
0.1
0.1
We conduct another experiment to verify that the scale invariance can be preserved. We use the same objective as above, but scale the second one by We use fixed initialization for this experiment. The other hyperparameters are the same the default. We use both F(o)) and F(0) as the reference points and choose B, such that BF - F(0)) = O. Results in Figure 7 show that for different scales, the trajectory and the converging solution the same.
0.3 [1 1
Table Summary average run time in seconds (s) or minutes (m) and number of iterations or epochs of different methods on different datasets. We use Algorithm for the synthetic experiments, and Algorithm 3 for the other two experiments.
Datasets
Metries
LS
PMTL
EPO
FERERO
Synthetic, Figures ((a-c)
Iterations
100
100
60
10
Per-iteration run time
3.50E-4s
7.67E-4s
4.93E-3s
7.50E-4s
Total run time
0.035s
0.0767s
0.296s
0.0075s
Synthetic, Figures 3(d-f)
Iterations
100
200
80
200
Per-iteration time
3.10E-4s
7.65E-4s
4.93E-3s
7.30E-4s
Total run time
0.031s
0.153s
0.394s
0.146s
Mull--MNiSSTFaationfF-MM
Epachs
100
100
100
100
Per-epoch run time
3.54s
11.88s
9.66s
7.02s
Total time
5.9m
19.8m
16.1m
11.7m
46

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: See Section introduction.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See the Broader impacts and limitations section.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: See Assumptions 1, 2, 3, 4 for the assumptions, and the Appendix D, and G for the proof.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: See Section 5 and Appendix H.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Code is available
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: See Section 5 and Appendix H.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: See Section We use the standard deviations as the error bars for all experi- ments except the speech recognition experiments since the speech recognition experiments take much longer time to run.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: See Section 5 and Appendix H.
47

---

9. Code Of Ethics
Question:
Does the research conducted in the paper conform, in every respect, with the
NeurlPS Code of Ethics https: http://aww....ccoaaaaaa/a/tttear
Answer: [Yes]
Justification: We preserve anonymity.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
See the end the main paper in the Broader impacts and limitations section.
Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: the paper poses no such risks.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: See Section 5 and Appendix H.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: the paper does not release new assets.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: the paper does not involve crowdsourcing research with human subjects. 15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects
48


Reviews:
[{"review_id": "0Wgq9o7YGp", "reviewer": "Reviewer_dD8J", "summary": "This paper tackled constrained multi-objective optimization problems with Pareto optimality generalized to partial order cone. The authors proposed an algorithm framework to iteratively solving a subproblem to get a update direction and aim at search for Pareto optimal solution in a certain Pareto front region associated pre-defined preferences.\n\nThe paper presented rich convergence analysis for deterministic algorithm with exact subproblem solutions, deterministic algorithm with inexact subproblem solutions, as well as stochastic version where gradient is estimated through double samplings. \n\nThe stochastic algorithm variant is tested on image classification and speech recognition tasks and compared against state-of-art benchmark algorithms.", "questions": "* As both the relative preference and constraints are defined in objective space and both equality and inequality constraints are defined as linear functions of objectives, would it possible to convert at least inequality constraints to preference defined by a cone? \n* Can we reduce Pareto dominance defined in a polyhedral cone to Pareto dominance defined in Real space $R^m_+$ by taking $AF(\\theta)$ as objective vector? \n* From Theorem 1 to Theorem 2, the second part on the left of Equation (2.5) $G(\\theta_t)$ no longer present in equation (3.2). How is the inequality violation converging to zero in the single loop approximate algorithm variant? \n* Equation (5.2): what is the rationale to have the representation learning loss for Chinese and English differing by an exact number. Would it be more reasonable to have the loss gap smaller than a threshold?\n* It is not clear in Table 2 what is Emotion loss without referring to Appendix.\n* Figure 2(a): “LS only finds extreme points on the PF with one objective minimized.\" How are the secularization weights selected? Is the weight selection related to extreme rays?\n* Figure 4 clarification\n    * 4(c) LS accuracy is missing. 4(a) also missing red square.\n    * As mentioned in the paper, orange preference vector is not attainable. In (d)-(f), the proposed algorithm tends to search for Pareto front region closer to the ideal Pareto minimizer. Is this constraint violation controllable?\n    * Figure (e) green cross given by XWC-MGDA seems dominating most of other solutions. \n\n* Minor issues:\n    * Notation consistency: Theorem 2 equation (3.2) $d_t$ → $d_t(\\theta_t)$. \n    * Line 279: figure 3d-3f should be 3a-3c. \n    * Figure 3: caption (c) and (f) should be consistent.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* This paper is well-structured, well-written and easy to follow. \n* The proposed algorithm framework can handle relative preferences where decision makers don’t need to specify explicit weights or threshold numbers. Also, the proposed algorithm has more flexible control on the search region on the Pareto front which is specified by extreme rays and/or constraints. This makes the algorithm more practical. \n* This paper provides comprehensive theoretical convergence analysis on the proposed three algorithm variants in general non-convex cases. The ideal of normalizing search direction by function values is novel to me. \n* The experiment on image and speech recognition tasks demonstrates its applicability to large scale neural network learning objectives. The improvement over recognition error rate is significant.", "weaknesses": "* The relative preference seems being handled by both partial order cone associated with the objective function and inequality constraints. It is kind of confusing and redundant to have both preference cone and constraints defined in the objective space in the optimization problem. See the questions part for more details. The experiment on multi-task learning seems only tackling constraints. \n* In real decision making application, computing the ordering cone by solving another LP makes the decision making process more complex and less doable.\n* The authors selected number of algorithm iterations to compare computational cost, which leads to apple to orange comparison. Better to adopt number of function evaluations, number of gradient evaluations, etc. as the metrics.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">W1-1 & Q1. Relative preferences are handled by both partial order and inequality constraints. It is confusing and redundant. Can inequality constraints be converted to the preference cone?\n\nWe respectfully disagree. As mentioned in the abstract, relative preference is handled by the partial order, and absolute preference is handled by the constraints. The two preferences are generally **not redundant but complementary**. Essentially, the cone captures *relative improvement* of the objectives, and the constraints capture the *absolute feasible regions* of the objectives. Some detailed differences are explained below.\n- **Equality constraints cannot be captured** by the preference cone with nonempty interior. \n- **The constants $b_g$ in the inequality constraints cannot be captured** by the preference cone, as the cone can only guarantee relative improvement at each iteration.\n- **Our method deals with the two preferences differently.** For preference cone, our Algorithm 1 with proper step sizes guarantees the next iterate always improves over the previous one in terms of the partial order induced by the cone, i.e., $AF(\\theta_{t+1}) \\leq AF(\\theta_t) \\leq AF(\\theta_0)$. In contrast, for preference constraints, our method does not guarantee feasibility at every iteration, i.e., $G(\\theta_t)\\leq 0, H(\\theta_t)=0$, but only when the algorithm converges. \n\nNevertheless, there are special cases where the constants $b_g$ in the inequality constraints align with the initial objective values $F_0$, with $B_g (F(\\theta) - F_0) = B_g F(\\theta) + b_g$. In this case, it is possible to convert the inequality constraints to preferences defined by a cone to ensure feasibility.\n\n>W1-2. The experiment on multi-task learning seems to only tackle constraints.\n\nThis might be a misunderstanding. See Figures 3, 5. We use a more general cone $C_A$ to allow controlled ascent of objectives.\n\n>W2. Computing the ordering cone by solving another LP is complex.\n\nWe do not always have to compute $A$. See **General Response-2**.\n\nWhen $A$ needs to be computed from the given extreme rays, the linear programming (LP) in Eq. (3.5) can be solved in polynomial time w.r.t. $M$. In practice and our experiments, $M\\ll d$, therefore, solving this LP requires much less computation/time than solving the main program (PMOL) to obtain the optimal $\\theta$.\n\n>W3. Comparison metrics using the number of function/gradient evaluations.\n\nFollowing your suggestion, we adopt these metrics. Results are summarized in **General Response-1**.\n\n>Q2. Take $AF(\\theta)$ instead of $F(\\theta)$ as objectives, and use $\\mathbb{R}_+^M$ as the preference cone.\n\nInteresting point! This is possible **only under the special cases** with more restrictions on the constraints and preference cone. \n\n- This is possible when there are no constraints. However, for constrained problems with constraints defined as functions of $F(\\theta)$, if we use $AF(\\theta)$ as objectives, we need to compute $B_h A^{-1}(AF(\\theta))$, which may lead to higher computational complexity, and thus not practical. Moreover, $A$ may not always be invertible in general.\n- This is only possible when the preference cone is polyhedral. For more general preference cones, they may not necessarily be written as in Definition 1. Therefore, one cannot use $AF(\\theta)$ as objectives in such cases. However, in such cases, our FERERO method can be extended to cover the more general preference cones $C$ by replacing Eq. (2.1), $A\\nabla F(\\theta)^\\top d \\leq c (\\mathbf{1}^\\top AF(\\theta))^{-1}AF(\\theta)$ with $\\nabla F(\\theta)^\\top d \\leq_C c (\\mathbf{1}^\\top F(\\theta))^{-1} F(\\theta)$.\n\n>Q3. Inequality constraints in Theorem 2 are not present in Eq. (3.2).\n\nSorry for the confusion. Indeed, we focus on equality constraints ($M_g = 0$) for Theorem 2. We will further clarify this in the paper. The results can be extended to include inequality constraints in future work.\n\n>Q4. Clarification of multilingual constraint in Eq. (5.2). Would it be more reasonable to have the loss gap smaller than a threshold?\n\nThe multilingual constraint in Eq. (5.2) is a heuristic choice based on the experience. We found that in this experiment setting, if $\\epsilon_2$ is close to zero, the performance in Chinese will be much better than the performance in English. However, we want the performance in both languages to be similar, hence we impose this equality constraint.\n\n>Q5. Clarification of emotion loss.\n\nThe emotion loss refers to the emotion classification loss. The task is to predict 6 types of emotions from 593 songs on the Emotions and Music dataset [38]. See Appendix F.2. We will add explanations of the emotion loss in the main text in the revision if space allows.\n\n>Q6. How are the scalarization weights in Figure 2(a) selected? Is the weight selection related to extreme rays?\n\nThe scalarization weights are selected uniformly from a simplex following the experiment settings in [30]. They are not related to extreme rays. We will clarify this in the revision.\n\n>Q7. Clarification of Figure 4.\n\n- *Missing square plots.* Sorry for the confusion. This is because we limit the plot scales to a certain range to make the majority of the results clear. We add plots with larger scales in Figure R2 in the attached PDF. We will include the plots in the revision.\n- *Controlling constraint violation.* Yes, constraint violation can be controlled by the hyperparameter $c_h$. Larger $c_h$ will make the constraint violation smaller.\n- *Figure (e) green plus is dominating.* Indeed, in this experiment, under the green preference vector, XWC-MGDA gives the best solution compared to other methods. However, under other preference vectors, the solutions of XWC-MGDA are not dominating, and the overall hypervolume of XWC-MGDA calculated from all the solutions is worse than the proposed method.\n\n>Q8. Minor issues.\n\nThank you for your detailed comments! We will revise the paper accordingly.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "T9HIqmSvPi", "reviewer": "Reviewer_aduv", "summary": "This paper introduces FERERO, a novel framework for preference-guided multi-objective learning by depicting the task as a constrained single-objective optimization problem. It incorporates relative preferences, defined by a polyhedral cone, and absolute preferences, defined by linear constraints, into the above optimization problem. Both deterministic and stochastic algorithms with finite-time convergence guarantees are proposed. FERERO is validated through experiments on multiple benchmarks, demonstrating its effectiveness in finding competitive preference-guided Pareto optimal solutions.", "questions": "Refer to the above comments.", "limitations": "The discussion is comprehensive in my view.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1.  This paper is very well-written and its results are solid.\n2.  A novel concept called relative preference is proposed, which interests me.\n3.  A stochastic version is also proposed for fast gradient estimation.\n4.  Only one optimization problem needs to be solved for each preference, while some methods require solving multiple subproblems.\n5.  The experimental results are competitive and promising.", "weaknesses": "I do not notice any obvious weakness. Some comments are given below:\n\n1. What is the evidence of ``flexible``? Is flexibility important?\n2. What is the meaning of ``cross`` in Table 1? Is it not mentioned in the literature or is it inherently impossible to do this?\n3. What are the advantages of a method based on general partial order? Is it related to escaping weak Pareto optimality?\n4. As far as I am concerned, Linear Scalarization and (Smooth) Tchebycheff can escape weak Pareto optimality.\n5. The per-iteration may need more descriptions.\n6. What if some absolute preferences are not available? e.g., $B_h$ or $B_g$ are not provided by the decision maker. Besides, the settings of preferences in the experiments are hard to find.\n7. Are there some typos in the subtitles of Figure 2(e) and Figure 3(c)?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">Q1. Evidence and importance of \"flexible\". \n\nIndeed, this is a critical point of our paper! \n\nThe \"flexibility\" is evidenced by that we model **both absolute and relative preferences**. Furthermore, absolute preference considers both inequality and equality constraints. The relative preference considers more general partial order compared to existing works. \"Flexible\" means we can flexibly choose the preferences such as absolute or relative preferences or both, without limiting to preference vectors or certain partial order cones.\n\nThis is in contrast to scalarization methods [22] or other preference-guided MOL methods such as [23,30], which have relatively restrictive formulations. For example, this is further evidenced by the multi-lingual speech recognition experiments in Section 5.2, where both inequality and equality constraints are considered, which cannot be directly solved by existing methods [22,23,30] that focus on either inequality constraints or preference vectors. Also, as evidenced by Figures 3 and 5, we use a more general partial order cone to allow controlled ascent of objectives, which cannot be achieved by e.g., [23],  without such flexibility.\n\nThis flexibility is important because it makes our method ```applicable to many other real-world problems``` as listed in **General Response-3**. Existing methods [22,23,30,33] without such flexibility may not be able to solve these problems.\n\n\n>Q2. Meaning of \"cross\" in Table 1. Is it not mentioned in the literature or inherently impossible to do?\n\nThe \"cross\" means it is not mentioned or provided in the corresponding literature.\n\n>Q3. Advantages of general partial order? Is it related to escaping weak Pareto optimality?\n\nIt is not related to escaping weak Pareto optimality. One key advantage of using general partial order is that it allows flexible modeling of more general relative preferences. And therefore, it extends the ability of the FERERO method to solve broader problems. We further explain with two detailed advantages below.\n\n- It allows us to use a primal algorithm with controlled ascent, as discussed in lines 98-99. Therefore, it is possible for us to find certain Pareto optimal solutions that would be otherwise impossible to find with a primal algorithm using $A=I$, e.g., see Figures 3 (d,f). \n- It makes the method applicable to many other real-world problems that cannot be solved using $A=I$, as discussed in **General Response-3**.\n\nThe ability to escape weak Pareto optimality is because our formulation in Eq. (2.1) considers finding update direction $d$ such that the descent amount is normalized by function values. If certain objective function values already achieve zero, then the algorithm finds directions that further decrease other objectives rather than stopping at weak Pareto optimality. The ability to escape weak Pareto optimality is proved in Appendix D.3.\n\n>Q4. Scalarization methods can escape weak Pareto optimality.\n\nWe are not aware that scalarization methods can directly escape weak Pareto optimality in general. For example, for linear scalarization on general nonconvex objectives, the gradient descent algorithm converges at a stationary solution of the linearly scalarized objective, which may be weakly Pareto optimal but not Pareto optimal. \n\nHowever, we are aware that under certain conditions, the global solutions of scalarization methods with positive weights are Pareto optimal [32, Theorem 3.1.2]. We will make revisions and clarifications on this point in Table 5. And we are very willing to cite proper references if the reviewer could kindly provide some.\n\n>Q5. More description of per-iteration complexity. \n\nWe have provided a detailed description of the per-iteration complexity. See **General Response-1**.\n\n>Q6-1. What if preferences are unavailable, e.g., $B_h,B_g$ not provided? \n \nWhen the absolute preferences are not available, the MOO problem reduces to an unconstrained one, and the proposed algorithm reduces to an adaptive cone descent algorithm with the following subprogram replacing Eq. (2.1).\n\\begin{align}\n\\psi(\\theta):=\\min _{(d, c) \\in \\mathbb{R}^q \\times \\mathbb{R}} c+\\frac{1}{2}||d||^2 \\quad \\text { s.t. } A \\nabla F(\\theta)^{\\top} d \\leq c\\left(\\mathbf{1}^{\\top} A F(\\theta)\\right)^{-1} A F(\\theta) .\n\\end{align}\n\nIf $B_h,B_g$ are not directly specified, they can be computed given the information of the preference. For example, if a preference vector $v\\in \\mathbb{R}^M$ is given, we can convert it to an equality constraint with $B_h$ satisfying $B_h v = 0$, where $B_h$ is formed by linearly independent row vectors that belong to $\\mathrm{ker}(v)$.\n\n>Q6-2. The settings of preferences in experiments are hard to find.\n\nIn synthetic, multi-patch image classification, and emotion recognition experiments, the preferences are specified by the preference vectors, following the experiment settings in [30]. The details of the preference vectors can be found in Appendix F. In these experiments, they are generated uniformly between certain angles, and plotted as dashed lines or arrows in Figures 2-5. As discussed in the answers to Q6-1, we can compute $B_h$ from the given preference vector $v$ by finding the orthonormal row vectors that belong to $\\mathrm{ker}(v)$. When $M=2$, $v = [v_1;v_2]$, $B_h = [-v_2, v_1] \\in \\mathbb{R}^{1\\times 2}$. \n\nIn the multi-lingual speech recognition experiment, the problem formulation is provided in Eq. (5.2). In this case, $B_g = [1,0,0], b_g = -\\epsilon_1$, and $B_h = [0,1,-1], b_h = -\\epsilon_2$.\n\nWe will further clarify the preference settings in the revision.\n\nFor more practical examples of the preferences that fit in the framework we study in this paper, please see **General Response-3**.\n\n>Q7. Clarification of subtitles in Figures 2,3. \n\nThe subtitle of Figure 2(e) is correct. It shows the result of our method with the same preference vectors as the previous methods. We will change the subtitle of Figure 3(c) from \"Ours\" to \"FERERO\" to be consistent.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "k4gDz94vmu", "reviewer": "Reviewer_rRCm", "summary": "This paper introduces a new algorithm called FERERO, which can handle both relative and absolute preferences in preference-guided multi-objective learning. The problem is formulated as a constrained vector optimization problem. The goal is to find the (approximated) $C_A$-optimal set that satisfies the absolute preference constraints. The cone $C_A$ can be interpreted as a relative preference that defines the objectives’ improvement directions. \n\nIn each iteration, the FERERO finds a direction $d^{\\star}(\\theta)=-\\nabla F(\\theta)A_{ag}^T\\lambda^{\\star}$, derived by solving a subprogram. The $\\lambda^{\\star}$ in $d^{\\star}(\\theta)$ is derived from the Lagrangian of subprogram. Moreover, the approximated update rules and a stochastic version of FERERO are proposed for large-scale learning problems. \n\nThe paper includes theoretical analysis of FERERO and its stochastic, approximated variants. The experimental comparisons with existing multi-gradient descent methods are also conducted to demonstrate the effectiveness of this approach.", "questions": "1.\tThe preference constraints are expressed as linear functions of $F(\\theta)$. Is this kind of linear structure assumption for preference constraints common in real world problems?\n\n2.\tCould you explain your choice of step sizes in the experiment and how can it be related to your theoretical results.", "limitations": "Yes", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.\tFERERO deals with both preference constraints and objective values in an adaptive way, eliminating the need to solve different subprograms at different stages. \n\n2.\tThe finite-time convergence rates of FERERO and its variants are established and the proof is solid. \n\n3.\tThe approximated rules, practical choice of preferences, and stochastic variants of FERERO-SA can be efficient for real-world problems.", "weaknesses": "1.\tThe step sizes in some of the convergence analyses, e.g., Theorem 2 and Theorem 3, depend on the $T$, which can be unknown in real-world problems.\n\n2.\tThe computational cost per-iteration can be higher than the traditional scalarization methods.\n\n3.\tThe studied problem is not well motivated. Compared to the traditional multi-objective optimization, the authors consider a more complicated case, where each objective function is a linear combination of the original multiple objectives. More real-world applications should be given to validate the significance of the problem.\n\n4.\tC_A is not used in the experiments. That is, traditional multi-objective optimization is considered. This seems to be insufficient.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">W1. The step sizes in Theorems 2 and 3 depend on iterations $T$, which can be unknown in real-world problems. \n\nChoosing step size depending on the number of iterations $T$ is common in optimization convergence analysis. For example, in [4,10,42], for the convergence analysis of unconstrained MOO, the step sizes are chosen based on the pre-defined value $T$.\n\nIn all our experiments, including the real-world emotion recognition and multi-lingual speech recognition tasks, a proper number of iterations $T$ is set before optimization, and then we can choose $\\alpha_t$ accordingly. Detailed iterations and step sizes are provided in Appendix F.\n\nWe also have general convergence results where the step size $\\alpha_t$ is not explicitly chosen to be dependent on $T$. See the derivation in Appendix E.2, Eq. (E.18). They can be summarized as follows\n\n\\begin{align}\n\\sum_{t=0}^{T-1} \\alpha_t ||d_t||^2 + \\alpha_t ||H(\\theta_t)||^2 = O\\Big(\\sum_{t=0}^{T-1}\\alpha_t^2 + 1 \\Big).\n\\end{align}\n\nIn such cases, we choose the step sizes to satisfy $\\sum_{t=0}^{\\infty} \\alpha_t^2 < \\infty$, and $\\sum_{t=0}^{\\infty} \\alpha_t = \\infty$. For example, $\\alpha_t = \\frac{1}{(t+1)^{\\frac{1}{2}+\\epsilon}}$ with $0<\\epsilon\\leq \\frac{1}{2}$ is also a proper choice to guarantee convergence. Similar choices exist in stochastic single-objective optimization literature, see [f].\n\n[f] Optimization Methods for Large-Scale Machine Learning, Bottou et al.\n\n\n>W2. Computational cost per iteration is higher than the scalarization method.\n\nYes, we have discussed this limitation in the Broader Impacts and Limitations section. Though traditional scalarization methods have better per-iteration complexity, the benefit of the proposed method with flexible preference modeling cannot be achieved by scalarization methods. For example, see the experiments in Figure 2. The linear scalarization (LS) method cannot find certain points on the Pareto front.\n\nDespite this, our computational cost per iteration is **similar to or lower than** existing non-scalarization-based methods [23,30]. See **General Response-1**.\n\nIn addition, since we proposed single-loop algorithms (Algorithms 2, 3), existing techniques for fast approximation of Gramian evaluation in FAMO [h, Section 3.2] can be applied to our method to largely reduce the gradient evaluation per iteration.\n\n[h] Liu et al., \"FAMO: Fast Adaptive Multitask Optimization,\" NeurIPS, 2023.\n\n>W3 & Q1. Motivation & examples of the studied problem.\n\n- In the introduction (Section 1), we provide two examples when the constraints are linear functions of the objectives, with further explanation in Appendix B.1. Furthermore, in the experiments of multi-lingual speech recognition, we have another example when the constraints are linear functions of the objectives.\n- In the experiments in Figures 3 and 5, we provide examples of using a general polyhedral cone $C_A$, where $A$ is not an identity matrix, to allow controlled ascent for the update of the objectives.\n- We provide more examples in the **General Response-3**.\n\n\nAlso note that, our framework and algorithm with subprogram Eq. (2.1) can be directly applied to handle more general constraints that are not necessarily linear w.r.t. the objectives. However, it may require other constraint qualification (CQ) assumptions, or the CQs can be more challenging to prove. We leave this for future work.\n\n\n>W4. $C_A$ is not used in experiments.\n\nThis might be a **misunderstanding**. The use of $C_A$ is reflected in that we use a **more general matrix $A$ that is not necessarily the identity matrix**. Please see our discussions in Section 5. \n- For synthetic data, in Figures 3(c) and 3(f), we use a more general $C_A$ as discussed in lines 278-288. \n- For multi-patch image classification, to avoid the fact that some preference vectors are not attainable, we choose different preference vectors and different corresponding $C_A$ to obtain the results in Figure 5. \n\nSpecifically, in these cases, the extreme rays of $C_A$ are determined by the given preference vector, then $A$ is computed by solving (3.5).\n\n\n>Q2. How are the experimental choices of step sizes related to the theory?\n\n\nIn our experiments, a proper $T$ is set before optimization, and we can choose $\\alpha_t$ accordingly.\n\n- In the deterministic case, and for Algorithm 2, in theory, we choose $\\alpha_t = \\Theta(\\frac{1}{T})$, i.e., $\\frac{c_1}{T} \\leq \\alpha_t \\leq \\frac{c_2}{T}$ for positive constants $c_1,c_2$. This theoretical result is reflected in that under the same experiment settings, when we choose smaller $T$, we can choose larger step size $\\alpha_t$; see e.g., in Table 10, Appendix F.2.\n- In theory, we require $\\alpha_t c_h \\leq 1$. This is reflected in the experiments in Tables 7,8,10 in Appendix F.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "P1XAMCkWpR", "reviewer": "Reviewer_PTWJ", "summary": "This paper considers preference-guided multi-objective learning from the lens of constrained vector optimization. Cone captures relative preferences. Constraints capture absolute preferences. Under boundedness and smoothness assumptions on the objective function, the paper provides gradient-based methods for the identification of Pareto optimal points. The paper provides convergence guarantees for deterministic and stochastic versions of various gradient-based algorithms and illustrates their applicability in a wide range of vector optimization problems.", "questions": "1) Section 3.2 is confusing. As far as I understand, the goal of the paper is to optimize the objective function using gradient-based methods for a given ordering cone. First, a method that generates polyhedral cone matrix A from extreme rays of the cone is presented. This is okay, as it is just another way to express the cone. However, the second point, i.e., choosing $C_A$ for controlled ascent, is ambiguous. If the cone encodes the preferences of the decision maker, why do the authors need to change it by adding a new extreme ray? \n\n2) Where are the green dots in Fig. 2 (a)-(e)?\n\n3) What is the difference between the algorithms in Fig. 2 (e) and (f)?\n\n4) What is the difference between the algorithms in Fig. 3 (c) and (f)?", "limitations": "Limitations are adequately discussed.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1)\tThe proposed adaptive iterative update scheme has some nice properties, such as not requiring the initial model and $\\theta_t$ to be always feasible, and not requiring different subprograms or different treatment of active inequalities. \n2)\tModels both relative preferences and absolute preferences.\n3)\tProposed iterative methods come with convergence guarantees.", "weaknesses": "1) This paper formalizes preference-guided multi-objective learning as a constrained vector optimization problem; however, the vector optimization aspect of the paper is not mentioned in the introduction section. It is not clear what “maximize” means, and it is not clear with respect to what cone the authors maximize. The introduction section gives the impression that the authors consider a multi-objective optimization problem, not a vector optimization problem. \n\n2) Since there can be many solutions in the Pareto set, the set of solutions $\\theta$ of PMOL may be very large. An important thing that is not mentioned explicitly in this work is how much of the true Pareto front ${\\cal F}$ or the true Pareto set $\\\\{\\theta : F(\\theta) \\in {\\cal F} \\\\}$ the proposed algorithms capture when they converge. The theoretical results point to the convergence but do not point to what set of solutions the algorithms converge towards. Indeed, many algorithms whose task is to identify a Pareto set of solutions (either for multi-objective or vector optimization) come with guarantees on the returned Pareto set in the form of $(\\epsilon,\\delta)$-PACness results. Some success conditions that quantify the quality of the returned Pareto set or Pareto front are given in the following works. \n\nAuer, Peter, et al. \"Pareto front identification from stochastic bandit feedback.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2016.\n\nArarat, Cagin, and Cem Tekin. \"Vector optimization with stochastic bandit feedback.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2023.\n\nThe contribution of this work will be much clearer if the authors can demonstrate guarantees for the solutions returned by their algorithms, and compare them with the existing $(\\epsilon,\\delta)$-PAC guarantees in the related works. \n\n3) Problem setup and preliminaries: “We first introduce new optimality definitions for PMOL that go beyond standard definitions of Pareto optimality”. These are some standard textbook results, not new. See and cite some of the following works. \n\nBoyd, Stephen P., and Lieven Vandenberghe. Convex optimization. Cambridge University Press, 2004.\n\nJahn, Johannes, ed. Vector optimization. Berlin: Springer, 2009.\n\nLöhne, Andreas. Vector optimization with infimum and supremum. Springer Science & Business Media, 2011.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">W1. In the introduction, the preference cones are not specified for the two examples, which causes confusion that the problem is not vector optimization.\n\nThanks for the suggestion. In the introduction, the cone is not specified, it can be any proper cone $C$ pre-defined by the user. Here, since we only intend to give application examples to motivate the problem, we do not intend to introduce the mathematical cone concept at this point.\n\nHowever, to avoid confusion, we will add the cone $C$ in the revision by replacing Eq. (1.1), and (1.2) with the following equations.\n \n\\begin{align}\n&\\mathrm{maximize}_ C~~ (f_ {\\text{acc}}(\\theta), f_ {\\text{fair}}(\\theta))^ {\\top} ~~ \\text{  s.t. } f_ {\\text {fair }}(\\theta) \\geq \\epsilon; \\\\\\\\\n&\\mathrm{maximize}_ C ~~ F(\\theta):=(f_ 1(\\theta), \\ldots, f_ M(\\theta))^ {\\top} ~~ \\text { s.t. } B F(\\theta)=B v, B v=0 .\n\\end{align}\n\n>W2. Comparison with PAC guarantees\n\nThanks for raising this interesting point! The $(\\epsilon, \\delta)$-PACness results mentioned by the reviewer in [c,g] guarantee that with probability $1 - \\delta$, the algorithm generates Pareto optimal (with some suboptimal) points within a precision $\\epsilon$, and with a sample complexity depending on $\\epsilon$ and $\\delta$.\n\nHowever, **our results are not directly comparable to [c,g]** since a key difference between our work and [c,g] is that [c,g] study the **a-posteriori** methods to generate a set of Pareto optimal solutions, after which the users specify their preferences and choose from the solutions. However, we study the **a-priori** method where the users first specify their preferences, then algorithms are used to find optimal solutions which satisfy the preferences.\n\nBecause of the difference between the studied problems, the PACness results in [c,g] only guarantee convergence to optimality for all the solutions generated by the algorithm, while our results guarantee convergence to **both stationarity and preferences**. When the objectives are convex / strongly convex, stationarity implies weakly Pareto optimality / Pareto optimality. \n\n\n\nWe will cite the related works including [c,g], and add the comparison in the revision.\n\n[c] Cagin and Tekin, \"Vector optimization with stochastic bandit feedback\", AISTATS 2023.\n\n[g] Peter, et al. \"Pareto front identification from stochastic bandit feedback\", AISTATS 2016.\n\n\n>W3. Preliminaries are not new but standard.\n\nThanks for the suggestion. We are aware of the standard results, and we have cited the preliminaries (Jahn, 2009) as [18] in Appendix C.1. Here we mean we consider the general cone to be a relative preference that is different from existing works [23,30,33] on preference-guided MOL. We will turn down the tone,  remove the word \"new\", and cite more references here.\n\n\n>Q1. Clarification of Section 3.2.\n\nThe second point is to guide the decision maker to choose an appropriate cone when the cone is **not pre-specified**, or when the current extreme rays are not sufficient to encode the preferences, as discussed in **General Response-2**. \n\nHere \"add\" means we will specify each extreme rays one by one, and add them to the current set of extreme rays to form a set that represents the cone, when the cone is not pre-specified. We use this method for the experiments in Figures 3 and 5 to specify a cone to allow controlled ascent. We will further revise and clarify this in the paper.\n\n\n>Q2. Where are the green dots in Fig. 2 (a)-(e)? \n\nThe green dots in Figure 2 are the initial objective values, which we omitted in the plots. We have regenerated the plots in Figure R1 in the attached PDF. We will change them in the revision.\n\n>Q3. What is the difference between the algorithms in Fig. 2 (e) and (f)? \n\nBoth are FERERO, implemented with Algorithm 1. The difference is the choice of the **preference vectors** represented by the dashed arrows. Here, using the two results with different preference vectors, we want to show that FERERO can model flexible preferences.\n\n>Q4. What is the difference between the algorithms in Fig. 3 (c) and (f)? \n\nBoth are FERERO, implemented with Algorithm 1. The difference lies in the **experiment settings**, as discussed in Section 5.1, lines 278-288. Specifically, the main difference is the initial values of the objectives. In Figures 3(a-c), all the initial objectives are in between the yellow and green preference vectors, and all three methods converge to the Pareto front, but their required iterations and convergence speeds are different. In Figures 3(d-f), the initial objective values are close to the blue or red preference vectors. In this setting, for PMTL, the green and yellow trajectories fail to converge to the Pareto front, but the other two methods can converge to the Pareto front and align with the corresponding preference vectors.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
## General Response

We thank all reviewers for their support and constructive comments. Below we address 3 common questions from the initial reviews.

>1. Comparison of computational cost with baselines.

Following the suggestion, we summarize the per-iteration complexity of different algorithms in terms of **gradient/function evaluation** in the table below.

|Algorithm|Per-iteration gradient evaluation|Per-iteration function evaluation| 
|---|---|---|
|Linear scalarization|$1$|-|
|PMTL [23]|$M$|$M_g$|
|EPO [30]|$M$|$M$|
|(X)WC-MGDA [33]|$M$|$M$|
|**FERERO (Ours)**|$M$|$M$|

To summarize, our method has **similar per-iteration complexity with PMTL and EPO**, but it is **higher than linear scalarization** methods.

Among them, PMTL only considers inequality constraints, i.e., $M_h=0$. At each iteration, it computes $M$ gradients, and evaluates $M_g$ inequality constraints to determine whether the inequalities are active or not. EPO and (X)WC-MGDA also compute $M$ gradients per iteration. They both evaluate $M$ objective values to obtain the index set $J^*$ for EPO, and to obtain the subprogram constraints for (X)WC-MGDA. FERERO computes $M$ gradients, and evaluates the $M$ function values per iteration.

We also summarize the **iterations and run time** for all experiments in Table R1 in the attached PDF. In practice, our Algorithm 1 has similar per-iteration run time with PMTL, but higher than EPO. Our Algorithm 3 has lower per-iteration run time than both PMTL and EPO.

>2. How to choose/compute the preference cone?

We do not always have to compute the preference cone or $A$.

Usually, the preference cone is pre-defined by the user, represented by matrix $A$ or the extreme rays. Only when $A$ is not pre-defined, but the extreme rays of the cones are defined, we need to compute $A$ following Eq. (3.5) in order to use the FERERO method. Otherwise, we can simply use a pre-defined $A$.

>3. More motivating examples of the studied problem.

Thanks for raising this question! We provide examples from the following two cases. 

- **Examples of general $C_A$.**
    - **Portfolio selection in security markets** requires finding weakly minimal points w.r.t. feasible portfolio cones, which are nonlattice, i.e., cones with more extreme rays than the ambiance space dimension. See [a].
    - **Multi-asset markets with transaction costs** use "solvency cones", where $A\neq I$ is defined in terms of the bid-ask prices of the assets. See [b].
    - **Optimal arm identification under noisy feedback** uses multiple objectives based on the rewards. The practitioners want to narrow down the set of solutions by using their domain knowledge about the relative importance of each objective. If the user wants to give at least 100$\alpha$% relative importance to each objective for $\alpha \in (0, 0.5)$, then this can be achieved by defining a new cone-induced partial order in [c, Eq. (2)]. 
    - **Small molecule drug discovery** considers the optimization of properties such as solubility, metabolic stability, and toxicity. By using a smaller cone $C_A \subset \mathbb{R}_+^M$ for in silico experiments, the practitioner can ensure that more designs are passed to the wet lab stage. See [c, Remark 2.3].

- **Examples of linear constraints of objectives.**
Linear structure in the constraints can be very common. Below we provide several examples with more details.
    - In **drug discovery**, constrained property optimization is often considered, where molecules are generated such that molecular properties are optimized, while satisfying certain constraints [d, 48]. See more discussion in Appendix B.1.            
    - In **fairness-aware learning**, one needs to consider the tradeoff between fairness and utility. For example, one may want to maximize the classification accuracy of multiple tasks/population groups (objective function), while ensuring fairness. The fairness constraint can be introduced such that the accuracy discrepancy between two groups (e.g., female, male) is bounded by a certain threshold, or the utility of a certain group should reach the prescribed threshold. See [e].    
    - In **self-supervised learning**, typically, the self-supervised loss without labeled data is combined with supervised losses for downstream tasks. This problem naturally fits in preference-guided MOL. The preference can be specified that the self-supervised loss is bounded by a certain threshold.    
    - In our paper, a **multi-lingual speech recognition** example is given in Section 5.2, Eq. (5.2). We consider a combination of self-supervised learning and fairness-aware learning. We use the self-supervised loss $f_p(\theta)$ besides the supervised language prediction losses as objectives, and the difference of language performances as constraints. 

[a] Aliprantis et al., "Equilibrium analysis in financial markets with countably many securities", J. Math. Econom. 40: 683–699, 2004.

[b] Kabanov, "Hedging and liquidation under transaction costs in currency markets", Finance and Stochastics, 3: 237–248, 1999.

[c] Cagin and Tekin, "Vector optimization with stochastic bandit feedback", AISTATS 2023.

[d] You et al., "Graph Convolutional Policy Network for Goal-Directed Molecular Graph Generation", NeurIPS 2018.

[e] Liu and Vicente, "Accuracy and fairness trade-offs in machine learning: A stochastic multi-objective approach", arXiv:2008.01132, 2020.

Meta-review: All reviewers agree that this submission makes significant progress in the area of multi-objective learning. The authors propose a new framework based on constrained vector optimization and present new iterative (gradient descent type) algorithms. They obtain both theoretical guarantees and provide also convincing experimental results. There has been a discussion between the authors and the reviewers in which all concerns and questions of the reviewers could be resolved.
Decision: Accept (poster)