Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
Authors: Lisha Chen
Quan Xiao
Ellen Hidemi Fukuda
Xinyi Chen
Kun Yuan
Tianyi Chen
Venue: ICML 2025 spotlightposter (2025)
Keywords: multi-objective optimization
optimization on the Pareto set
semivectorial bilevel optimization
Primary area: optimization
TL;DR: We cast the preference-guided multi-objective learning problem as optimization on the Pareto set, and propose a first-order penalty approach to solve it.

Abstract: Multi-objective learning under user-specified preference is common in real-world problems such as multi-lingual speech recognition under fairness. In this work, we frame such a problem as a semivectorial bilevel optimization problem, whose goal is to optimize a pre-defined preference function, subject to the constraint that the model parameters are weakly Pareto optimal. To solve this problem, we convert the multi-objective constraints to a single-objective constraint through a merit function with an easy-to-evaluate gradient, and then, we use a penalty-based reformulation of the bilevel optimization problem. We theoretically establish the properties of the merit function, and the relations of solutions for the penalty reformulation and the constrained formulation. Then we propose algorithms to solve the reformulated single-level problem, and establish its convergence guarantees. We test the method on various synthetic and real-world problems. The results demonstrate the effectiveness of the proposed method in finding preference-guided optimal solutions to the multi-objective problem.

Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
Lisha Chen
Quan Xiao
Ellen Hidemi Fukuda
Xinyi Chen
Kun Yuan
Tianyi Chen
Abstract
Pareto front
loss langunge
Multi-objective learning under user-specified pref- erence is common in real-world problems such as multi-lingual speech recognition under fair- ness. In this work, we frame such a problem as a semivectorial bilevel optimization problem. whose goal to optimize a pre-defined preference function, subject the constraint that the model parameters are weakly Pareto optimal. To solve this problem, convert the multi-objective con- straints to single-objective constraint through a merit function with an easy-to-evaluate gradi- ent, and then, we use a penalty-bast -bsed reformu- lation of the bilevel optimization problem. We theoretically establish the properties of the merit function, and the relations of solutions for the penalty reformulation and the constrained formu- lation. Then we propose algorithms to solve the reformulated single-level problem, and establish its convergence guarantees. We test the method on various synthetic and real-world problems. The results demonstrate the effectiveness of the pro- posed method in finding preference-guided opti- mal solutions to the multi-objective problem.
preference
solution
pprofere da
preference
Solver
solution
Meerabiity
preference
solution 3
loss of language
Figure I. Example on multi- multi-linguul speech or language processing problem under user-specified preference guidance. The red curve represents the Pareto front, which is, informally, the set of objective values that achieve the best trade-off's among multiple objectives.
significant benefits most notably, it reduces model size and inference time, making it more efficient and scalable. Multi- objective optimization facilitates this by enabling the learn- ing of models that minimize vector-valued objectives (Mi) ettinen. 1998 Ehrgotti 2005). In practical scenarios, often desirable obtain solutions that provide controlled trade-off's reflect specific preferences among competing objectives, rather than treating all objectives equally.
To further illustrate, we use one example on multi-lingual speech or language processing problem in Figure [ The goal of this problem is to minimize multiple losses from different languages, while satisfying the user-specified pref- erences. Preferences can control trade-offs among mul- tiple losses and enhance steerability, enabling the solver to return diverse solutions on the Pareto front. Analyti- cally, the preferences can be defined as constraints or ob- jectives, see, e.g., (Lin et al., 2019 Curtis et al. 2023 Chen et al.] 2024a) To prioritize finding the optimal so- lutions of the multi-lingual losses over satisfying the pref- erences, we model the preference as a secondary scalar- valued objective. We first optimize the vector-valued ob- jective formed by concatenating the multi-lingual losses, and then optimize the vcalar-valued preference objective. More formally, let fi...., fM : X' + R be the objec- tive functions, and fo X + be the preference func- tion, e.g., the discrepancy between different objectives, with X' C R4 being nonempty, closed and convex. De- pending on the problem, X can be compact or E3, Let F F= (fi,..., fM) X - RM be vector-valued function. Then the optimization problem is
1. Introduction
Many machine learning tasks naturally involve multiple objectives, which may include diverse performance met- rics such as accuracy, fairness, and privacy, or even the same metries evaluated across different datasets (Sener & Koltun 2018). A common approach to tackling such multi- objective problems is to learn shared model that performs well across all objectives simultaneously. Compared to train- ing separate models for each objective, this approach offers
'Rensselaer Polytechnic Institute, Troy, United States "Kyoto University, Kyoto, Japan 'Peking University. Beijing, China. Correspondence to: Lisha Chen <lishachenn5577e (037777mmmll.o.m goail.com>> Tianyi Chen <chentianyil 1ell9@@@mmailoooo gom...com>.
Proceedings of the nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
minzex fo(x) s.t. x E arg min F(x)
(OPS)

---

Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
where for minimizing the vector-valued objective Far)), we consider the widely used Pareto optimality, whose formal
the penalty problem and that to the simple bilevel problem.
definition is deferred to Section 2 Then problem (OPS) is also known as Optimization on the Pareto Set (OPS), or a semivectorial simple bilevel optimization problem (Bolin-
2. Problem Setup and Preliminaries
lineanu 1993a/b b).
For the optimization problem mingex F(x) in OPS we use the standard definitions for Pareto optimality (Mittinenn 1998). Given two vectors v and w, we use e < w and v S w to denote U2 < Wy and 2/ S wy for all i, respectively. We use S w to denote S w and v + w, and define >.2, 2-' analogously. We use 1 1M to denote an all-one vector with dimension M, where M is sometimes ommitted if it is clear from the context. Then Pareto dominance and weak Pareto optimality are formally defined below.
The OPS or semivectorial bilevel optimization problem is
generally very difficult to solve (Bolintineanu 1993b). Ex- isting studies usually make strong assumptions such as the convexity of the objectives F (Roy et al. 2023), or the al- gorithms require evaluating the second-order derivatives of the objectives, and is thus inefficient for large-scale prob- lems (Chen et al., 2022 Roy et al. 2023). To address these challenges, we introduce reformulations of the OPŞ problem, establish relations of the reformulations and the original problem, and propose algorithms to solve the refor- mulated problem with convergence guarantees.
Definition 2.1 (Pareto dominance and optimality). Given e, w E M we say v strictly dominates w if and only if wーE < O. Correspondingly, a point x E X is weakly Pareto optimal if there is no x' E X such that, F(x') < F(x). In addition, point X is e-weakly Pareto optimal if there exists no x' E X and x' o x such that, F(x') < F F(a)) cl.
Our contributions can be summarized as follows: First, we propose a smoothed merit function to convert the vector-valued objective F to a scalar-valued objective, with easy-to-evaluate gradient. We prove that the smoothed merit function preserves the equivalence with approximate weak Pareto optimality. Then we use the smoothed merit func- tion as penalty function, prove its error bound properties, and establish the relation of the global/local/staionnay so- lutions of the penalty-based reformulation and the original problem. Based on the reformulation, we propose an effi- cient first-order algorithm with convergence rate guarantees. Experiments are conducted on various synthetic and real datasets with possibly nonconvex objectives demonstrate its effectiveness.
Throughout the paper, we assume fm()), m = ,,...,M are proper and bounded below. And we assume they are twice continuously and directionally differentiable. Denote the directional derivative of fm at point æ along direction d as f (z; d), defined as
fm (I; = lim Sm (x + cd) Sm( a.0
(1)
a
Then the Pareto stationarity is defined as follows. Definition 2.2 (Parcto stationarity e.g. (Ehrgott 2005 A
point E X' is Pareto stationary if max [M] Fm (x;
Technically, we address the following challenges:
x) 2 0 for all z E X, where [M] = ( M).
TI The original OPS problem in general has a non-convex non-smooth structure, posing challenges to evaluating the subdifferential and developing convergent algo- rithms. We propose to use a smoothed merit function as penalty so that it has easy-to-evaluate gradient, and the convergence of the developed algorithm can be analyzed.
Denote WP(F) S X' as the weak Pareto set of F. which contains all the weakly Pareto optimal solutions for min F(x). Then problem (OPS) is equivalent to min fo(z). We say that the solutions to (PP)) are preferred Pareto optimal. We then discuss in the next section the problem formulation to find these solutions.
T2 Instead of directly assuming the lower-level merit (penalty) function satisfies the error bound as in ex- isting (simple) bilevel optimization literature, we prove the proposed merit (penalty) function satisfies the de- sired error bound when the objectives satisfy certain conditions such as subanalyticity.
3. Problem Reformulation
In this section, first convert the original problem (OPS) with multiple lower-level objectives to an equivalent prob- lem with a single lower-level objective using a merit func- tion. Then we discuss its penalty-based reformulation.
T3
We define a stationary condition for the simple bilevel problem with provable calmness condition under the Hurdyka-Lojasiewice incquality, weaker than the as- sumptions in existing results, and thus applicable to a wider range of problems including ours. Based on this, we establish the relation of the stationary solution
3.1. A smoothed merit function and its properties
A merit function associated with the multi-objective op- timization problem min F(x) is non-negative, and returns zero only at the weakly Pareto optimal solu- tions (Auslender 1976 Hearn 1982). Under this require-
2

---

Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
ment, assuming lower semicontinuity of F, then
been established for the merit functions and ny (c.f. Ap- pendix B.T.. We will show that the smoothed version Vi,r can still preserve these properties approximately depend- ing on the hyperparameters and т. For our analysis, we make the following assumptions that are common in multi- objective optimization (Fliege et al. 2019 Liu & Vicente 2021). Note that we do not require all the following as- sumptions to hold for all our results, which will be specified correspondingly.
ū a = sup min yE mE[M]
(m((z) - (m))
is merit function in the sense of weak Pareto optimal- ity (Tanabe et al. 2024| Theorem 3.1). In other words, [(x) = 0 if and only x is weakly Pareto optimal. Given this equivalence, it is desirable to convert the original lower- level multi-ohjeccive optimization problem to minimizing the scalar-valued function ū(x). However, ū(x) in gen- eral can be non-differentiaale due to its max-min structure, posing challenges to directly applying
Assumption 1. For all m E {O..... M3. fm (x) is locally Lipschitz on any bounded set in X'.
madient-based ap- proaches to minimize ū(x). To address this challenge, we propose the following smoothed and regularized merit func- tion Ut (x) given 1 2 0,5 0.
Definition 3.1 (Weak convexity). A locally Lipschitz func-
tion f X + R is y-weakly convex if fxx 5 | is convex for x E X.
Assumption 2. For all m E [M], fm. is locally Lipschitz and p--eakly convex on X.
M
ha, v) = In Σe
fm(()) fmi()) + 2/100- w/1²
(3a)
Before proceeding to the theoretical results, we introduce the following definition, which relaxes the commonly used convexity assumption of the objective functions.
(x) = -mnn hr. (2. v).
(3b)
v
Note that, U1, can be seen as a smoothed and regularized function of u. Specifically, when I = 0, Up.r smoothes the maximization operation over m E [MM] in ū with the log- sum-exponential (LSE) function [Nesterov] 2005). And it uniformly converges to ū as 7 converges to zero. Besides, adding the regularization with 1 >> 0 can further lift weakly convex objective to a strongly convex one, that not only the minimization minyex (x, in (3b) enjoys a unique solution, but also v1,-(1 is smooth and has casy-to-evaluate gradient. To further illustrate, we provide a visualization of ū. Ui.r on simple example in Figure 2 It shows that ut,r with smaller 7 or approximates ū better, while larger 1 makes Vir smoother. Too large I could possibly change the shape of ut, significantly compared to i.
Definition 3.2 (Point strong quasar-convex functions Hardt
et al. 2018 Definition 2)1)). A function f /: X' + R is
(Cg. H0) -ponnt strong quasar-conver with cy E (0. 1 2 0
at x E X for all x E Ex
f())
1 v(() (x) + Co
1 2
11
xll" (4)
The point (strong) quasar-convexity in Definition 3.2 is a re- laxation of the (strong) convexity. When Cg = 1, the quasar- convexity implies point star-convexity (Lee & Valiant 2016). And if the point star-convexity holds at all x E X, then it implies convexity. There are many examples of noncon- vex but point quasar-convex functions, see the discussions in, e.g., (Hinder al. 2020). In machine learning, typi- cal examples that satisfy the quasar convexity include the linear dynamical systems identification (Hardt et al. 2018) and generalized linear models with leaky ReLU or logistic activation functions (Wang & Wibisono 2023).
or
Piaci
= 0.01
= 0,10
r= 0.03
0.30
F
1.00
0.00
Based on the above assumptions and definition, we intro- duce the properties of the smoothed merit function Uh in
-016
-0.5
10x
1ox
Proposition 3.3
(a) 00.y and 7
(b) 21,0 01 and i7
Proposition 3.3 (Properties of u1,z). Suppose Assump-
Figure 2. Illustration of vrr and a with different values of and
tion 2 holds. The merit function vi, (x) defined in (3b) satisfies the following properties:
with F(x)=
( (x + 2)2 + 8/(x= 1)2 2))+
1. ((x) T In M S vo, (z) S ū(x). Furthermore,
mingex (x)) -7 In M.
Then we discuss the properties of the smoothed merit func- tion and outline the procedure for computing its gradient. Properties of the smoothed merit function. We estab- lish how the value of the smoothed merit function changes when x reaches the weak Pareto optimality condition. In the prior work (Tanabe et al. 2024), such properties have
2. If is weakly Pareto optimal, then ve,((x) < 0. Con-
versely, if a) = 0, (x) S O. then x is e-weakly Pareto
optimal with e = 7 In M; b) > O, (x)(()) < - In M. and for all m E [M], fm are (1, O)-pint quwsar-comear at x. then x is weakly Pareto optimal.
3

---

Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
The proof of Proposition 3.5 is deferred to Appendix B.3
widely-used objective functions (Dries & Miller 1996
In Appendix [.44] we provide some examples of nonconvex F that satisfies condition 2-b) in Proposition 3.3
Bolte et al., 2007). For example, the E--norm with p 2 1, and the LSE and polynomial functions defined on bounded set, all satisfy the subanalyticity. More discussions and examples are provided in Appendix [222 and Table [ In- tuitively speaking, global subanalytic functions can be de- scribed by finite combinations of locally analytic functions. They exhibit a "tame" geometry, thus stability under basic operations, and desirable properties for optimization. One of them is the Hölderian error bound defined below.
Next we discuss how to compute the gradient of the smoothed merit function 01,r, so that we can use gradient- based methods to directly minimize v1,."
Gradient of the smoothed merit function. Under As- sumption 2 all the objectives fm are p-weakly convex, i.e., fm 2 ||=]| is convex X. The LSE func- tion preserves weak convexity (c.f. Lemma B.3) thus (1, y) is strongly convex w.I.t. y if μ > 0. Then (z) == arg mingex h4,5 (I. y) is a singleton, and is con- tinuous w.r.t. z, so the Danskin-type type theorem can be applied here to compute the gradient of vi given by
Definition 3.4 ((e, HHödderra error bound), For func- tion U X R. let X2 arg minzex v(z). Then satisfies the (e, () Hôllderraa error bound (HEB) if
e(v(x)
min e(x)) > (tist(2,x)))) =eX
(6)
M
[e(,(()=
Tm (=) 1xx vi. (z)),
(5a)
where (i, 5) is the Euclidian distance from a point æ to a set S, and 0. > 0.
et et (()) (m)))
with (x)
(5b)
Σm= (fmili (2)) (m))
M
The HEB in Definition Quadratic Growth (QG) condition with 1) = 2 in optimiza- tion (Karimi et al. 2016 Drusvyatskiy & Lewis 2018), and the weak sharp minima condition with v)
3.4 generalizes the widely used
Reformulation of problem OPS] J. We then consider the following optimization problem by approximating the Pareto set constraint x E WPF() through merit function
(Burke & Ferris 1993). This condition ensures the point is close to the solution set if the function value gap at the point is small. In our problem, it is desirable that the function Vi, also satisfies such a condition, so that it satisfies HEB near its solution set. This can be proved based on the properties of subanalytic functions, as described in Lemma 3.5 below.
constraint using Vt,r.
min fo(z), s.t. x E ==< E X (x) + - In M S 0). xex
(CP)
We name the above program constrained program (CP)
reformulation. By Proposition 3.3 S(F) C ((F). and
these two sets become equal as [, 4 0. To solve (CP).
Lemma 3.5 (Subanalyticity of X and vt, (z)). Under Assumption 3 and that X is subanalytic, given a com- pact subanalytic set Xc, suppose I' (m()) is continuous and bounded on X for all m E [MM). Then both X nxc and (x)) on Xe n X are globully subanalytic. Conse- quently. Ut. (z), p(z) satisfy the (e. 1) and (Cp- (pp- H in Definition 3.4 on Xe X, respectively, with some e, > O. hpp = On, and Qp g².
we further consider a penalty-based program (P..) with
penalty parameter 7, > below
min (x(x) fo(z) + 7p(x) =EX
(PP.)
with p(z)= = (vt, (z) + M))
For (PP.) when y - oc, any limit point of the sequence of solutions to the approximation problem (PP.) d is a solution to the problem (CP).
Definition 3.4 and Lemma 3.5 crucial for establishing the relations of the global/local/staionnn solutions of the penalty reformulation (PP.,) and the constrained formula- tion (CP). Below we first define the global and local solu- tions to CCP, then we discuss their relation with global and local solutions to (P..).
3.2. Relation of different formulations
To establish the relations of the solutions to (P p. (CP). and (OPS), without loss of generality, we assume there exists least one x= E arg min 01 (x) that x² is bounded, and that the function value fm and gradient fm Definition 3.6 (Global and local solutions). We say x is an (c, (c,5)-global solution to CCP on Xs S X if it satisfies
at x= for m = o,..., .M are also bounded. We also intro- duce the following global subanalyticity assumptions on the objectives below.
fo(x) - min fo(x) Se, x Z Nos
(7a)
Assumption 3 (Subanalyticity of fm)).) For all m [M]. fm (x) is subanalytic on X.
Z X,
with x== = (rEX
p (x) < 6).
(7b)
Due to space limit, the definitions on (global) subanalytic functions and the related properties are provided in Ap- pendix C Subanalyticity can be generally satisfied by many
Let B(x, r) denote the neighborhood of x with radius r. We say x is an (c. Loccll solution to (CP) on X' if is an (c, -gllbbll solution on X'- = B(x, r) n.
4

---

Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
In Theorem 3.7 we establish the relation of solutions (CP with a smoothed merit function and those the original problem (OPS). We also establish the relations of the glob al/local solutions of the penalty reformulation (PP-) and the constrained formulation (CP).
x E B(x*) with KL inequality at x², then v1,r satisfies the condition in Theorem 1...rrem.77.... The above condition holds if a) for all E [MM] fm satisfies the (1, 1..0intt quasar- convexity at z, and (1, popinnt strong quasar-convexity at vī = arg minyex h1, y); or b) 01 (x) + In M v in Lemma C.9
Theorem 3.7 (Relation of e-global/local solutions
The condition in Theorem 3.7 2 requires local solution to mingex V1,- is also c-globally optimal to this problem. Such a condition holds if F satisfies point convexity sub- analyticity near the stationary points of (t,((1), as shown in Proposition 3.9 The proof is deferred to Appendix [D.2 Next, we define the KKT condition, its necessity, and estab- lish the relation of stationary solutions.
to (OPS), (CP and ) ). Suppose Assumptions 7 and
hold. Then with proper choices of 8,, depending on 5 for all 8 > 0, we have
1. (Relation of (OPS) and (C)) The (e, (ol))--glllcccd
solutions to CPp with 6 2 t In M are (c.6)-globallion globballoloaal
solutions to OPS Conversely, the (e, (e,5)-g)) -gglbbll//oll so-
lutions to (PSS) are (e', ((,)'))g ("'''')globaallii "lloball/local solutions to (CP).
2. (Relation of CPP and (PPr)) The c-global/local solu-
Definition 3.10 ((c, 8) -stationayyy condition, e.g. (Liu et al. 2022 Xiao et al. 2023b)). Let X = R9. For the func- tion p such that Vp(z) and p(z() exist, and Vp(r) = 0 implies p(x) = 0, a gradient- based reformulation of the
tion to (PP denoted as Zn, is an (c, 0..2 )--+22""-glouull g-glbbll/tocal solution to CPP, where Ex = 0 for the global case, and E" iinffee(e, p(x) for the local case. Conversely, an (cC.c)-gooballocc solution to (CP) is a 8- 5-global/loca solution to PP*
problem is
min fo(x), s.t. Vp(x)= = 0,
(9)
The proof of Theorem 3.7 is deferred Appendix [D2] It extends the result from (Shen et al. 2025) using the HEB proved in Lemma 3.5 on a compact subanalytic set instead of directly assuming the QG condition on the whole domain X. Furthermore, it does not rely on convexity assumptions of (x). The less restrictive assumptions make it appli- cable to a much wider set of problems. A more detailed comparison is given in Appendix A.I
The (e, (KKT condition of the problem 9 is
[[( + p()())l S e, [Vp(2)) s 6
(10)
where w E R2 is bounded.
Theorem 3.11 (Relation of e-stationary solutions). Let X' = R2 and 6 = 1. Let In be bounded c-stationary solution to (PP.) Then there exists compuct subanalytic set XC c I with Xen # 0 and x. E Xxc Suppose Assumption D Tholds, and that on Nc, Vvi,( exists and is lv smmoohh,, and vi (a) is (Ce; 0cr) with oa 2 2. Then with proper choice of parameter 7, depending on ö, By is an (c + 5, -)KK point to the problem (
Theorem 3.7 2 states that if Ut,r satisfies HEB, and there exists p(*) S e" in the neighborhood of the local solution, then the local solution of (PP.,) is a local solution of (CP). In e.g., (Shen et al. 2025; Chen et al.) 2024b), these con- ditions can be satisfied under certain assumptions on the lower-level objective, such as the PL. inequality or convex- ity. However, in our problems (PP.)) and (CP), we cannot directly assume such conditions hold for Vt, Therefore, next we will show that the conditions hold under additional conditions specified in Proposition 3.9 We first introduce the Burdyka-L.jjsievii inequality below.
The sy.p-smoothness of V0t,r can be justified under addi- tional assumptions of the Hessian of fm for m E [M]] See detailed discussion in Lemma [ Theorem 3.1 shows that for simple bilevel problem where the lower-level ob- jective 01.- (1)) satisfies the KI. inequality with exponent O₂ 2 2, a stationary solution to the penalty reformulation approximates the KKT solution to the constrained formu- lation ( This indicates that though the KKT solution to a bilevel problem often requires the second-ordes infor- mation of the lower-level objective as shown in (10) and discussed in e.g., (Roy et al., 2023 Liu et al.) 2022 Xiao et al. 20236), one can still use first-order methods to ap- proximate such solutions. The proof of Theorem 3.11 is provided in Appendix D.3] We first prove that the calmness condition holds in the above settings, ensuring the KKT conditions are necessary for global optimality.
Definition 3.8 Surddyka-.ojasiewicz http:/iiiiiieuulliyy.... inequality). A proper and lower semicontinuous function f R3 + (-oc, +oo] satisfies the (c.aa)-Kurda) - Kurdyka-toojssiewiic. (KL) inequality at
r if there exist & E (0, +x)]. 0, > 1, a neighborhood (()). ), such that for all x E B(T) and f(z)= f(x)= <
f(z) + v, the following inequality holds
((dist(0.0f(z)) 2 11f(()) f())ll.
(8)
Moreover, if f satisfies the (c, aLLKLLL incquality for ev- ery pair of points (x,z) 2) on a set Xe with f(z) = mingexe fz), then we say f is (c, KLL on Xc.
3.3. Comparison with existing methods
Proposition 3.9. Let x E X be a bounded e-stationary point of mingex (x). If there exists x² E X and
To address the cefference-guideer MOL problem, one com- monly used formulation is linear scalarization (I.)) where
5

---

Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
Table 1. A recipe to choose hyperparameters 8, Y to obtain solutions to (PP and thus the solutions to (PP Denote Tpp Op as the HEB,
KL exponents of p(r). and v,, de the HEB, KL exponents of en (x) on subanalytic and compact set, respectively.
IPp
X
Vt,r (2) property
p(æ) property
c-global/local (Theorem 3.7 2)
(c, gllobal/oocaa
compact or RR9
7 0
2e 0
"
7pp 2 Op
e Ex
(c. c) -oglobal/oocal
e-stat. (Theorem 3.11)
R
Oy 2
(c, KKT to
Table 2. Comparison with existing methods for OPS semivec- torial bilevel optimization. "NC", "C" and "SC" represent "non- convex", "convex" and "strongly convex", respectively. "Nes." represents whether the method converges to necessary condition to the OPS problem.
1Sindged
PRIFRO eatpal
Oww.
30 (7
19.
(a) LS
(b) FERERO
(c) FOOPS
Method
(m( m E [M] fo(#)
First order
Nes.
PB-PDO Kamani et al 2021
NC
NC
V
X
Figure 3. Results of LS, FERERO, and FOOPS Example 3.12
TAWT
Chen et
NC
NC
x
The black dashed lines is the preference defined by (xx)= = O. Green dots represent initial values. blue markers represent con- verged values for different methods.
PNG
NC
NC
PMM
Roy et al 2025
SC
SC
X
BSG Giovannell
Stricly
NC
X
Ohis
NC
NC
the preference modeled by different weights of the objec- tives. Another commonly used formulation is constrained vector optimization (Lin et al., 2019 Chen et al. 2024a),
certain initialization, LS cannot converge to a point that sat- isfies (2b) with different weights, see Proposition 3.13 The intuition is that, in Example 3.12 a solution to both (OPS) and [1 that satisfies F À 0 with À E A is local maximum point of the objective A F(x).. It is also worth noting that, there are some other examples where LS cannot find all points on the Pareto front even after enumerating all possible weights (Osyezka 1984, Athan 1994 Hu et al. 2023). See detailed discussion in Appendix A.2
given by
mingex F(z), s.t. G(x) O, (x)) (11)
where H H vector-valued functions defined by user- specified perferences. Though the above formulation has successful applications in, e.g., multi-task learning, it is only guaranteed to converge to a KKT point of (I]). which may be far away from the optimal solutions to minzex F(x). See Example 2.12 and the corresponding results in Fig- ure 3 An intuitive explanation for this suboptimality is that 1II puts constraints at the lower level, emphasizing more on satisfying the constraints rather than minimizing the objectives.
Proposition 3.13. Under certain initializations, there exists À A such that gradient descent algoritiun LS objective with weight X converges to the solution of (12)
Moreover, algorithms developed under the preference- constrained formulation (T), such as PMTL (Lin et al., 2019 and FERERO (Chen al. 2024a) (with the partial order cone being nonnegative orthant cone R&)), converge to a KKT point to [T]. which is not necessarily Pareto op- timal or Pareto stationary. For more detailed discussion on this example, see Appendix A.2 Proposition 3.14 is provided to further support the claim that the KKT solution to (TT) can be suboptimal for minzex F(x), with its proof in Appendix A.2 A.2
Example 3.12. Let M =2, = 1, and M, = 0, Mn 1. Let X R. The objective F and constraint H for the preference-constained formulation [1 is defined as
F(x) - - e -lle---- 1111,, --c e -11-+1111))
(12a)
(zx) (x) -f(())
(12b)
Proposition 3.14. The KKT solution to is not neces- sarily Pareto stationary to mingex F(z).
The corresponding preference function fo in formula- tion (PS) to minimize the constraint violation of H is defined as fo(x)= = [=)]| In Figure it is easy to see that there exists a solution x= in the Pareto set whose objec- tive F(z") is at the intersection of the dashed line defined by H (x) 0 and the solid curve representing the Pareto front. Therefore, x² is an optimal solution to both (OPS) and
Besides modeling preference by weights or constraints, there are also some works which model the preference by objectives, and formulate the problem as optimization on the Pareto set (OPS), as in (OPS). Among these meth- ods, Preference- Basedd Pareto Descent Optimization (PB- PDO) (Kamani et al. (021 1 and Pareto Navigation Gradient descent (PNG) (Ye & Liu 2022) use a descent-type algo- rithm to ensure the output of the algorithm satisfies the preference and decreases the objectives F at each iteration. However, it has been shown in (Roy et al. 2023) that the
In this example, linear scalarization (LS) fails to converge to the preferred region that H (x) = 0, even after enumer-
ating different weights. Indeed, we could prove that with
6

---

Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
2022 is not necessary optimality condition for OPS Furthermore, as discussed in (Roy et al.) 2023 Proposition 3), non-
stationary condition derived in (Ye & Liu
We then discuss the choices of update oracles and the non- asymptotic convergence rate of Algorithm | with different oracles below. Let w represent the updated parameter, which can be either x and y, Aw denote the gradient vector, a the stepsize, and & is the iteration number.
trivial stationarity condition for (PSS) typically requires
second-order derivatives of the objectives fm, m E [M]- Different from these methods, Target-Aware Weighted Train-
We give examples of oracles using projected gradient desent (PGD), and momentum updates (Momentum) in (14). The Nesterov's acceleration and Adam update are also applica- ble, which is detailed in Appendix H one can also see in e.g., (Wang et al. 2024).
ing (TAWT) (Chen et al., 2022) and Pareto Majorization- Minimization (PMM) (Roy et al. 2023) convert the lower- level vector-valued objective to a scalar-valued objective through linear scalarization (LS), and optimize both the scalarization weight and the model parameter. However, as discussed in Example(.1D [3.12 and Appendix [A.2 optimality for LS is not necessary for (PS) unless fm are convex for all m E [M].
PGD: U(w, Aur ar, 1) = Projx (w (14a) Momentum: U(w, Aw; tt Projx (wae))
We summarize in Table 2 the key differences of our work compared to existing methods for OPS. See also detailed review in Section 5 and Appendix A
with āv + Aw
(14b)
4. Algorithms and Analysis
Discussion about the convergence. Since (z, y) is Mhg -strongyy convex w.r.t. y as detailed in the proof of Lemma E.4, when we choose Uy as projected gradient de- scent, the momentum updates and Nesterov's acceleration, it gives linear convergence rate for the inner-loop of y. For the outer-loop w.r.t. x, 0 2 1, then the objective (p,(2) (1) dif- ferentiable and thus projected gradient descent, momentum, Nesterov's 's acceleration, Adam updates give O1/TT) con- vergence rate in the deterministic setting and O(1/VT) con- vergence rate in the stochastic setting according to (Wang) et al. 2024). Therefore, combining outer-loop and inner- [ converges. We provide a proof for the convergence of Algorithm Ap- pendix Theorem E.6 when choosing both Uy and U, as the PGD oracle and choosing 0 Z 1, and assuming the objectives (z) for m 0, M are smooth. For l < 1. p(x) can be nonsmooth. The convergence for Algorithm 1 can be built upon nonsmooth optimization (Kiwiel 2004 Davis et al. 2018). but possibly under additional assump- tions. Some discussions about algorithms for nonsmooth lower-level objective are provided in (Chen et al.) 2024b). When fo(x) and p(x) are Lipschitz, the algorithm can be applied to problem. We leave more detailed study of algorithm development in nonsmooth cases for future research.
In this section, we introduce practical first-order gradient- based algorithms to solve (PP-). We first update y to obtain an estimate for (1)), and thus an estimate for (z,- (1, vi (x)). Then we update based on the estimated penalty function ipy-
At the 1-th outer iteration and the k-th inner iteration, we iteratively update z, and ft, as follows.
,t,,+1 = U, AU, v4); Br k); Zt+1= = (2,, (Te(E a4.));attt)
(13a)
(13b)
loop update oracles together, Algorithm
where U is some gradient based oracle, and the gradient vectors with respect to y and x are defined as
(BL,a V Vulu. (Ir, k1
Anc V fo(zs) 7 (eg "o Vahee (are, 8241)
with y++1 = Kt,KK and i/- = r In M - hr, (Fe, 16+1)-
meta algorithm with the above updates is summarized in Algorithm[] [ We name it First-Order Order Optimization on the Pareto Set (FOOPS) algorithm.
Algorithm 1 The meta FOOPS algorithm with oracles
1: Initialize t 0, zo, you set step sizes (ax, 3. penalty parameter { ), inner-loop iterations ( {
Single-loop and stochastic variants. When we take the exact penalty method with 7p = 1, 7 and K, can be upper bounded by a constant. In fact, under Assumption 2 when ff.1, a single-loop variant of Algorithm | that takes K, = 1 also has non-asymptotic convergence guarantees, see e.g. (Chen et al. (021). Besides, stochastic variants of Algorithm | can also be derived which replace the deter- ministic gradients with their unbiased stochastic estimates. We leave the development and convergence analysis of such variants for future work.
2: while || / (2x) > do
3: Set k = 0;
4: for k = ..... K₁- 11 do
5: Update V by 13a):
6: end for
7: Set Mi+1 = K,;
8: Update x, by (3b);
9: Set t- ++l. 1;
10: end while
7

---

Efficient First-Order
Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
5. Related Works
ter converting the vector-valued LL objective scalar- valued one through the merit function fl,r, the LLL objective is generally nonconvex and non-PL even if the objectives fm. m E [M] are all convex or PL. Therefore, it is difficult to directly apply the existing analysis or algorithms to our problem.
We discuss recent works that are most related to ours. An extended discussion is provided in Appendix(A.. iiierrenee-eettr-guiddee multi-objecttvv learning. Pref- erences in multi-objeccivv optimization can be represented using weights, thresholds, or preference vectors. Scalar- ization methods, such as linear and Tchebycheff scalar- ization, convert vector objectives into scalar objectives by applying weighted norms (Miettinen 1998). Alternativel.. e-constraint methods impose thresholds on objectives to convert the problem to constrained optimization prob- lem (Curtis al. 2023). There are also other approaches which represent preferences with vectors in the objective space, focusing on finding optimal solutions satisfying con- straints defined by these vectors (Lin et al. 2019)] Chen et al. 2024a) or minimizing distances to the vectors (Mahapatra
6. Experiments
In this section, we conduct experiments to verify our theory and show the applicability of the algorithms to preference- guided multi-task learning. We use LS, PMTL (Lin et al. 2019), EPO (Mahapatra & Rajan 2020). XWC-MGDA
(XM) (Momma et al. (0022). FERERO (Chen et al.) 2024a)
as baselines for comparison. For preference vector-guided MOL problem, we define fo()) = (xr) where I/ (x) is
the equality constraint function derived from the preference
& Rajan 2020, Momma et al. 2022). See also a compre-
vector (Chen et al.. 2024a)
hensive review (Chen et al., 2025).
Optimization on the Pareto Set. In machine learning, there are specific instantiations of the OPS problem. For example, EPO (Mahapatra & Rajan (020) and Preference-Bane Pareto Descent Optimization (PB-PDO) (Kamani et al. 2021) find a Pareto model such that the objective values satisfy a ratio constraint by minimizing the non-uniformity score. Specifically, EPO finds update directions to improve the objective values, or to reduce the constraint violations, or both. PB-PDO finds common descent directions for the lower-level multi-objectives and the upper-level objective. They are not guaranteed to converge to a necessary condi- tion of the OPS problem. Target-Aware Weighted Training (TAWT) (Chen et al., 2022) learns a multi-task model that minimizes the discrepancy of task representations to ensure they are similar. TAWT converts the lower-level objectives to linearly scalarized objective, and optimizes the scalar- ization weights in the upper level. This approach has the limitation of introducing undesired local solutions.
Metries. Objective loss and accuracy. We report the objec- tive losses and accuracies in classification.
Hypervolume. Let F² E RM denote the Nadir point, i.c. the worst performance on single-task baselines, and S de- note set of objective function values of the obtained models. Hypervolume measures the size of the domi- nated space of S relative to F', which can be computed by H(S) = A(fg E RM| 3F S F S S F'H), where A(-) denotes the Lebesgue measure. Additional details. The implementation and additional
experiments can be found in Appendix F
(a) PMTL
(b) FERERO
(c) FOOPS
(Simple) bilevel optimization. Problem (CP) is a con- strained reformulation of the simple bilevel program with a generally nonconvex lower-level (L..) objective. For non- convex LL objectives, algorithms are proposed in e.g., (Liu jet al. 2021b; |Huang, 2023; Xiao et al.) 2023b). However, they usually require second-order derivatives in the algo- rithms, which can be expensive to implement. More re- fently,firstorriee Hessian-free approaches were proposed to address this by the value function reformulation of BLO. For example, sequential quadratic programming (Liu et al. 2022), and smoothed Lagrangian method (Lu 2023) were
Figure 4. Outputs (colored markers) and optimization trajectories (colored curves) of different methods when initial objectives are near the Pareto front. Dashed arrows with different colors represent different preferences.
Following (Lin et al. 2019 Mahapatra & Rajan 2020), the first objective we consider is 12a in Ex- ample 3.12 but with q = 20. The results for the experiments with hard initialization are displayed in Figure They show that under certain initializations and preferences, algorithms developed under [T]) such as PMTL and FERERO (with A / therein) could fail reach the Pareto front. It further justifies our Proposition] 3.14 the KKT solution to (II) with preferences modelled by the constraints at the lower level, can be suboptimal for min F(r). In contrast, FOOPS successfully converges to preferred Pareto optimal solutions under different preferences. It demonstrates the benefit of the OPS formulation over (T). by prioritizing the
Example 3.12
used to solve the constrained problem. Later on, penalty- based algorithm was proposed (Shen et al. 2025). Variants such as Moreau Envelope based algorithms (Kwon et al.
2024| Liu et al. 2024) and adaptive algorithms (Chen et al. 2024b) were proposed. However, none of these works tackle BLO with vector-valued LL objective. Moreover, even af-
8

---

Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
0.7
1.0
0.7
LS
0.9
0.6
EPO PM I'L XM
0.5
0.3
0.4
PERtERO
FOOPS
0.3
0.3
0.4
0.3
0..4
0.5
0.0 0.7 0.4
0.5
0.6
0.7
0.5
0.9
1.0
0.2
0.3
0.4
0.5
0.6
0.7
(a) Multi-MNIST loss
(b) Multi-Fashion loss
(c) Multi-F+M loss
Figure 5. Losses of various methods with different preferences across three image datasets. The horizontal and vertical axes represent results for objective 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.
Table 3. Hypervolumes of different methods f (x 10 1)
Table 4. WERs J (%) for speech recognition.
Datasets
LS
PMTL
EPO
XM
FERERO
FOOPS
Method
English
Chinese
Average
Mt-M loss
1.68
1.41
1.35
1.42
1,95
2.62
Komatsu al.
7.11
Mt-F loss
6.75
5,90
6.02
6.77
7.76
8.32
w/o CPC
11.8
10.2
11.0
Mt-F+M loss
3.63
3.03
3.76
3.89
3.8220m1
4.80
Init. (M2ASR)
7.3
6.2
6.7
Mt-M accuracy
0.19
0.15
0.15
0.16
0.25
0.33
LS-FT
6.8
5.9
6.4
Mt-F accuracy
0.99
0.87
0.87
0.99
1.131007
1.22
FERERO-FT
5.4
4.9
5.1
Mt-F+M accuracy
0.48
0.40
0.50
0.52
0.53+004
0.72++0.06
FOOPS-FT
5.7
4.7
5.1
attainment of weak Pareto optimality instead of the optimal- ity of the preference function.
good representation, and the upper-level objective ensures the difference of the performances on both languages is small; see more details in Appendix F The results are re- ported in Table 4 which show that FOOPS demonstrate competitive average performance on different languages, but is less good at optimizing the fairness preference func- tion fo. This observation consistent with that in Figure
Multi-patch image classification. Following (Momma jtt al. 2022), we use Multi-MNIST (Mt-M), Multi-Pashion (Mt-F), and Mulli-Fashion-MNIIT (Mt-F+M) for image classification. The two tasks or objectives in all three datasets are classify the top-left and the bottom-right images, respectively. We use LeNet as the backbone neural network. The losses of different methods given different preference vectors are plotted in Figure 5 Experiments for our method are repeated times. Hypervolumes with means and standard deviations are reported Table The results for other methods Table are are referenced from (Momma al. 2022; Chen et al.] 2024a). The results show that FOOPS is better at obtaining large hypervolumes, see Ta- ble 3 but worse at aligning with preferences compared to other methods, see Figure
7. Conclusions
In this work, we cast preference-guided multi-objective learning as an optimization on the Pareto set (OPS) problem, which is essentially a semivectorial simple bilevel optimiza- tion problem, with a lower-level vector-valued objective, and an upper-level scalar-valued preference objective. We propose first-order penalty method solve the problem, where the penalty function is the polynomial of smoothed merit function. For the theoretical analysis, first we es- tablish the properties of the merit function, including its relation to weak Pareto optimality, and the Hölderian error bound. Then we discuss the relation of solutions to the penalty reformulation and the original OPS problem. Part of our theoretical analysis is of independent interest to sim- ple bilevel optimization problem. Interestingly and perhaps surprisingly, analysis shows that although the stationary condition of the OPS problem usually requires second-ord -oderr derivative information, it can be approximated using first- order methods. Based on the results, we develop first-order algorithms to solve the penalty problem and provide their convergence guarantees. For the empirical experiments, we apply the proposed method to synthetic and real-world prob- lems, which demonstrate the effectiveness of the proposed method in finding preference-guided optimal solutions.
Multi-lingual speech recognition. We use the proposed method to fine-tune a pre-trained multi-lingual speech recognition model. The datasets include Librispeech (100 hours) (Panayotov al. 2015), and AISHELL v1 (Bu al. 2017). The model architecture is conformer with 8 blocks. The speech recognition Connectionist Temporal Classifica- tion (CTC) losses in Chinese and English are denoted as fch and fen respectively. We also use the self-supervised Con- trastive Prodictive Coding (CPC) loss fp for representation learning, i.e.,
- min fo(x) = II (x) (x)]l
(15a)
s.t. x E arg min F(x) = (Fz(z), Sthh (z), (("))"))))
(15b)
where the lower-level objective fp ensures the model learns

---

Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
Acknowledgement
Bonnel, H. and Morgan, J. Semivectorial bilevel optimiza- tion problem: Penalty approach. J. Optim. Theory Appl., 131(3):35-382,, 12 2006.
The work of Lisha Chen, Quan Xiao, and Tianyi Chen was supported by Cisco Research Gifts and the IBM through the IBM-Renssllaer Future of Computing Research Collabora- tion. The work of Ellen Hidemi Fukuda was supported by the Japan Society for the Promotion of Science, Grant-in- Aid for Scientific Research (C) (JP25K15002). The work of Xinyi Chen was done while she was remote intern at Rensselaer Polytechnic Institute.
Bu, H., Du, J., Na, X., Wu, B., and Zheng, H. Aishell-1: An open-source mandarin speech corpus and speech recognition baseline. In Conference of the oriental chap- ter of the international coortinating committee on speech databases and speech I/O systems and assessment, pp. 1-5, 2017.
Impact Statement
Burke, J. V. and Ferris, M. C. Weak sharp minima in math- ematical programming. SIAM J. Control Optim., 31); 1340-1359, 1993.
This paper presents work whose goal is advance the field of Machine Learning, especially algorithms and the- ory for optimization on the Pareto set with applications to preference-guides multi-objective learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Chen, L., Fernando, H., Ying, Y., and Chen, T. Three- way trade-off multi culti-objeective learning: Optimization, generalization and conflict-vvoidance In Proc. Advances Neural Inf. Process, Syst., New Orleans, LA, 2023.
Chen, L., Saif, F. M., Shen, Y., and Chen, T. FERERO: flexible framework for preference-guided multi-objective learning. In Proc. Advances Neural Inf. Process. Syst., Vancouver, Canada, 2024a.
References
Athan, T. W. quasi-Monte Carlo method for multicriteria opfimization. PhD thesis, University of Michigan, 1994.
Auslender, A. Optimisation: Méthodes Numériques, vol. Masson, Paris, France, 1976.
Chen, P., Shi, X., Jiang, R., and Wang. J. Penalty-based methods for simple bilevel optimization under Hölderian error bounds. In Proc. Advances Neural Inf. Process. Syst., Vancouver, Canada, 2024b.
Bai, X., Zeng, S., Zhang, J., and Zhang, L. Alternating gradient-tyl type algorithm for bilevel optimization with in- exact lower-level solutions via moreau envelope-based reformulation. arXiv:2412.1888 2024.
Chen, S., Crammer, K., He, H., Roth, D., and Su, W. J. Weighted training for cross-task learning. In Proc. Int. Conf. Learn. Representations, number 3861, virtual, 2022.
Benko, M. and Mchlitz, On implicit variables in opti- mization theory. J. Nonsmooth Anal. Optim., 2:7215, 8 2021.
Chen, T., Sun, Y., and Yin, W. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. In Proc. Advances Neural Inf. Process. Syst., volume 34, pp. 25227775377 virtual, 2021.
Bierstone, E. and Milman, P. D. Semianalytic and subana- lytic sets. Publ. Math. Inst. Hautes Études Sci., 67:5-42 1 1988.
Bolintineanu, S. Necessary conditions for nonlinear subop- timization over the weakly-efficient set. J. Optim. Theory Appl., 78(3):579-50) -99,, 1993a.
Chen, W., Zhang, X., Lin, B., Lin, X., Zhao, H., Zhang, Q., and Kwok, J. T. Gradient-based multi-objective deep learning: Algorithms, theories, applications, and beyond. arXiv preprint arXiv:2501.10945 2025.
Bolintineamu, S. Optimality conditions for minimization over the (weakly or properly) efficient set. J. Math. Anal. Appl., 173(2):523-5A4 541, 1993b.
Clarke, F. H. Optimization and Nonsmooth Analysis. SIAM, Philadelphia, PA, USA, 1990.
Bolte, J., Danilidis, A., and Lewis, A. The Lojasiewicz inequality for nonsmooth subanalytic functions with ap- plications to subgradient dynamical systems. SIAM J. Optim., 17(4) 1203-123,,311111 2007.
Curtis, F. E., Liu, S., and Robinson, D. P. Fair machine learning through constrained stochastic optimization and an epsilon-constraint method. Optimization Letters, pp. 1-17, 2023.
Bolte, J.. Nguyen, T. P., Peypouquet, J., and Suter, B. W. From error bounds to the complexity of first-order descent methods for convex functions. Math. Program., 165(2): 471-507, 11 2016.
Davis, D., Drusvyatskiy, D., MacPhee, K. J., and Paque- tte, C. Subgradient methods for sharp weakly convex functions. J. Optim. Theory Appl., 179:962-99999 982, 2018.
10

---

Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
Dempe, S. and Mehlitz, Semivectorial bilevel program- ming versus scalar bilevel programming. Optim., 69(4): 657-679, 6 2019.
Hardt, M., Ma, T., and Recht, B. Gradient descent learns linear dynamical systems. J. Machine Learn. Res., 19 (29):1-44, 8 2018.
Dontchev, A. L. and Rockafellar, R. T. Implicit Functions and Solution Mappings. Springer, Berlin, Germany, 2009.
Hearn, D. The gap function of convex program. Oper. Res. Lett. 1(2):67-71, -71, 4 1982.
Hinder, O., Sidford, A., and Sohoni, N. Near-optimal meth- ods for minimizing star-convex functions and beyond. In Proc. Conf. Learn. Theory, pp. 1894-1938, virtual, Jul. 2020.
Doron, L. and Shtern, S. Methodology and first-order algo- rithms for solving nonsmooth and non-strongly convex bilevel optimization problems. Math. Program., 201: 521-558, 12 2023.
Hong. M., Wai, H.-T., Wang. Z., and Yang, Z. two- timescale stochastic algorithm framework for bilevel op- timization: Complexity analysis and application actor-
Dries, L. and Miller, C. Geometric categories and o-minimal structures. Duke Math. J., 84(2):997-540, 1996.
Drusvyatskiy, D. and Lewis, A. S. Error bounds. quadratic growth, and linear convergence of proximal methods. Math. Operations Res., 43(3):919-949) 3 2018.
critic. SIAM J. Optim,, 33(1):147-180) 1 2023.
Hu, Y., Xian, R., Wu, Q. Fan, Q. Yin, I.., and Zhao, H. Re- visiting scalarization in multi-task learning: A theoretical perspective. In Proc. Advances Neural Inf. Prucess. Syst., volume 36, New Orleans, LA, 2023.
Ehrgott, M. Multicriteria optimization. Springer, Berlin; New York, 2nd ed edition, 2005.
Huang, F. On momentum-bant based gradient methods for bilevel optimization with nonconvex lower-level. arXiv:2303.003944 2023.
Fernando, H., Shen, H., Liu, M., Chaudhury, S., Muruge- san, K., and Chen, T. Mitigating gradient bias in multi- objective learning: A provably convergent stochastic ap- proach, In Proc. lut. Conf. Learn. Representations, Kigali, Rwanda, May 2023.
Ji, K., Yang. J., and I Liang, Y. Bilevel optimization: Conver- gence analysis and enhanced design. Proc. Int. Conf. Machine Learn., pp. 4892, virtual, 2021.
Fliege, J. and Svaiter, B. F. Steepest descent methods for multicriteria optimization. Mathematical methods of op- erations research, 51:479-494 2000.
Jiang, R., Abolfazli, N., Mokhtari, A., and Hamedani, E. A conditional gradient-based method for simple bilevel optimization with convex lower-level problem. In Proc. Int. Conf. Artif. Intell. Statistics, pp. 10305-10323, 2023,
Fliege, J., Vaz, A. I. F., and Vicente, L. N. Complexity of gradient descent for multi-objective optimization. Opti- mization Methods and Software, 34(5):949 -599, 2019.
Kamani, M. M., Forsati, R., Wang. J. Z., and Mahdavi. M. Pareto efficient fairness in supervised learning: From extraction to tracing. arXiv:2104.01633 2021.
Ghadimi, S. and Wang, M. Approximation methods for bilevel programming. arXiv:1802.02246 2018
Karimi, H., Nutini, J., and Schmidt, M. Linear conver- gence of gradient and proximal-gradient methods under condition. In Proc. Eur. Conf. Much. Learn. Knowl. Discov. Data., pp. 795-811, 2016.
Giang-Tran, K.-.., Ho-Nguyen, N., and Lee, D. A projection-free method for solving convex bilevel op- timization problems. Mathematical Programming, pp. 1-34, 2024.
the
Kiwiel, K. C. Convergence approximate and incremental subgradient methods for convex optimization. SIAM J. Optim., 14(3):807-840, 2004.
Giovannelli, T., Kent, G. D., and Vicente, L. N. Bilevel optimization with a multi-objective lower-level problem: Risk-neutral and risk-averse formulations. Optim. Meth- ods Softw., 39(4):756 778,77777777 7 2024.
Kosiba, M.
The generalized Łojasiewicz inequality for definable and subanalytic multifunctions. J. Math. Anal. Appl., 543(2, Part 1): 3 2025.
Gu, A., Lu, S., Ram, P., and Weng, L. Min-max bilevel multi-objective optimization with applications machine learning. Proc. Int. Conf. Learn, Representations, Ki- gali, Rwanda, 2023.
Kurdyka, K. On gradients of functions definable in minimal structures. Ann. Inst. Fourier, 48(3):769-783, 1998.
Gulati, A., Qin, J., Chiu, C.-.,, Parmar, N., Zhang, Y., Yu, J., Han, W., Wang, S., Zhang, Z., WU, Y., et al. Con- former: Convolution -yvolutioon-aummeeeee augmented transformer for speech recognition. arXiv preprint arXiv:2005.0 100000000000.0..0.. 2020.
Kwon, J., Kwon, D., Wright, S., and Nowak, R. On penalty methods for nonconvex bilevel optimization and first- order stochastic approximation. In Proc. Int. Conf. Learn Representations, number 1380, May 2024.

---

Efficient First-Order Optimization on the Pareto Set for Multi-O/jective Learning under Preference Guidance
Lee, J. C. and Valiant, P. Optimizing star-convex functions. In Proc. IEEE Annu. Symp. Found. Comput. Sci., pp. 603- 612, 2016.
Mejia-De-Dios, J.-A., Rodríguez-Molina, A., and Mezura- Montes, E. Multiobjective bilevel optimization: A survey of the state-of-the-art. IEEE Trans. Syst., Man, Cybemn. Syst. 53(9))5478-53)) 5490, 9 2023.
Liao, F.-.., Ding, L., and Zheng, Y. Error bounds, PL con- dition, and quadratic growth for weakly convex functions, and linear convergences of proximal point methods. In Proc. Learn. Dyn. Control, volume 242, pp. 993-1005, Jul. 2024.
Merchav, R. and Sabach, S. Convex bi-level optimization problems with nonsmooth outer objective function. SIAM J. Optim., 33(4):311443142 2023.
Miettinen, K. Nonlinear Multiobjective Optimization, vol- ume 12. Springer US, Boston, MA, 1998.
Lin, X., Zhen, H.-L., Li, Z., Zhang, Q.-F., and Kwong, S. Pareto multi-task learning. In Proc. Advances Neural Inf. Process. Syst., Vancouver, Canada, December 2019.
Momma, M., Dong, C., and Liu, J. A multi-objective/mulii task learning framework induced by Pareto stationarity. In Proc. Int. Conf. Machine Learn., Baltimore, MD, 2022.
Liu, B., Liu, X., Jin, X., Stone, P., and Liu, Q. Conflict- Averse Gradient Descent for Multi-task Learning. In Proc. Advances Neural Inf. Process. Syst., virtual, December 2021a.
Nesterov, Y. Smooth minimization of non-smooth functions. Math. Program., (03(1):127-155)) 2005.
Oord, A. v. d., Li, Y., and Vinyals, O. Representation learn- ing with contrastive predictive coding. arXiv preprint (KKYv:8807.03777 2018
Liu, B., Ye, M., Wright, S., Stone, P., and Liu, Q. BOME! Bilevel optimization made easy: A simple first-order approach. In Proc. Advances Neural Inf. Process. Syst., volume 35, pp. 30612-30625, New Orleans, LA, 2022.
Osyczka, A. Multicriteriin optimization in engineering with
FORTRAN programs. Ellis Horwood, 1984.
Liu, R., Liu, Y., Zeng. S., and Zhang, J. Towards gradient- based bilevel optimization with non-convex followers and beyond. In Proc. Advances Neural Inf. Process. Syst., volume 34, pp.
Panayotov, V., Chen, G., Povey, D., and Khudanpur, S. Lib- rispeech: an ASR corpus based on public domain audio books. In Proc. International Conference on Acoustics, Speech and Signal Processing, pp. 5206-5210, 2015.
virtual, 2021b.
Liu, R., Liu, Z., Yao, W., Zeng, S., and Zhang, J. Moreau envelope for nonconvex bi-level optimization: A single- loop and Hessian-free solution strategy. In Proc. Int. Conf. Machine Learn., 2024.
Roy, A., So, G., and Ma, Y-A. Optimization on Pareto sets: On theory of multi-objective optimization. arXiv:2308.02144 2023.
Liu, S. and Vicente, N.N. The stochastic multi- cellii-graiintt algo- rithm for multi-objective optimization and its application to supervised machine learning. Annals of Operations Research, pp. 1-30, 2021.
Samadi, S., Burbano, D., and Yousefian, Achieving opti- mal complexity guarantees for class of bilevel convex optimization problems. In Proc. Amer. Control Conf., pp. 2206 22112 2024.
Lu, S. SLM: A smoothed first-order lagrangian method for structured constrained nonconvex optimization. In Proc. Advances Neural Inf. Process. Syst., pp. 80414-80454, New Orleans, LA, 2023.
Sener, O. and Koltun,
V. Multi-task learning as multi- objective optimization. In Proc. Advances Neural Inf. Process. Syst., Montreal, Canada, December 2018.
Shen, H., Xiao, Q., and Chen, T. On penalty-based bilevel gradient descent method. Math. Program., pp. 1-51, 2 2025.
Luo, Z.-Q., Pang, J.-S., and Ralph, D. Mathematical Pro- grams with Equilibrium Constraints. Cambridge Univer- sity Press, Cambridge, United Kingdom, 1996a.
Stackelberg, H. F. V. Market Structure and Equilibriumm Princeton University Press, Princeton, NJ, USA, 1952.
Luo, Z.-Q.. Pang, J.S.., Ralph, D., and Wu, S.-Q. Exact penalization and stationarity conditions of mathematical programs with equilibrium constraints. Math. Program., 75:19-76, 10 1996b.
Tanabe, H., Fukuda, E. H., and Yamashita, N. New merit functions for multiobjective optimization and their prop- erties. Optimization, 73(13):3821-3888 2024.
Mahapatra, D. and Rajan, V. Multi-task learning with user preferences: Gradient descent with controlled ascent in Pareto optimization. In Proc. Int. Conf. Machine Learn., virtual, 2020.
Vicente, L. N. and Calamai, P. H. Bilevel and multilevel programming: bibliography review. J. Glob. Optim., (3):291-306, 10 1994.
12

---

Efficient First-Order Optimization on the Pareto Set for Multi-Ojjective Learning under Preference Guidance
Wang, B., Zhang, H., Meng, Q. Sun, R., Ma, Z.-M., and Chen, W. On the convergence of adam under uniform smoothness: Separability from sgdm and beyond. arXiv:2403.15146, 2024.
Wang, J.-K. and Wibisono, A. Continuized acceleration for quasar convex functions in non-convex optimization. In Proc. Int. Conf. Learn. Representations, number 2055, Kigali, Rwanda, 2023.
Xiao, Ban, H., and Ji, K. Direction-oriented multi- objective learning: Simple and provable stochastic al- gorithms. In Proc. Advances Neural Inf. Process. Syst., New Orleans, LA, 2023a.
Xiao, Q. Lu. S., and Chen, T. An alternating opti- mization method for bilevel problems under the Polyak- Lojasiewiez condition. In Proc. Advances Neural Inf. Pro- cess. Syst., pp. 63847-63873, New Orleans, LA, 2023b.
Yang, X., Yao, W. Yin, H., Zeng. S., and Zhang, Gradient- based algorithms for multi-objective bi-level optimization. Science China Mathematics, (7(6)) -1144-13998.4.- 2024.
Ye, F., Lin, B., Yue, Z., Guo, P. Xiao, Q., and Zhang, Y. Multi-objective meta learning. Proc. Advances Neural Inf. Process. Syst., volume 34, pp. 11338-21351 virtual, 2021.
Ye. F., Lin, B., Cao, X., Zhang, Y., and Tsang, I. W. A first-order multi-gradien algorithm for mujti-objective bi-level optimization. In Proc. European Conference on Artificial Intelligence, pp. 2621-2628, 2024.
Ye, J. Constraint qualifications and necessary optimality conditions for optimization problems with variational inequality constraints. SIAM J. Optim., 10(4):943-96,, 2000.
Ye, J.. Zhu, D. L., and Zhu, Q. Exact penalization and necessary optimality conditions for generalized bilevel programming problems. SIAM Optim.,, 7(2):481-507, 1997.
Ye, M. and Liu, Q. Pareto navigation gradient descent: a first-order algorithm for optimization Pareto set. Proc. Conf. Uncertainty Artif. Intell., pp. 2246-2255, 8 2022.
13

---

Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
Appendix
Throughout the paper, we assume fm (z). m = =0, .,...,,,......... M are twice continuously differentiable and bounded below, and the minimizer of X F()) exists for all E AM,
For notation simplicity, we use LSE, RRM R denote the Log-sum-exp function with parameter т. We say function ju-(waklly convex, with j IR. If 0, the function is strongly convex, if μ 0, the function is convex, and μu O, the function is weakly convex.
Organization of the appendix. We organize the proof in the appendix as follows.
In Appendix A
we discuss additional related work on (semivectorial) bilevel optimization and limitation of linear scalariza-
tion and preference as constraint formulations.
Appendix A.1
additional related work on bilevel and multi-ohjective optimization
Appendix
limitations of linear scalarization and preference as constraint
In Appendix we prove the basic properties of the merit function.
Appendix B.2
continuity of the merit function
Appendix
relations of o1r and weak Pareto optimality
In Appendix we discuss (global) subanalyticity and prove related properties such as the subanalyticity, Hölderian error bound (HEB), and KI. inequality of the merit function.
Appendix
C.1
proof of global subanalyticity of vt,r
Appendix
examples of globally subanalytic functions and their HEB
Appendix
relations of proximal error bound (EB), proximal KL, and HEB
In Appendix
D
prove the relations of different formulations.
Appendix
D.1
e-global/tocal solutions relation of the smoothed problem
Appendix
D.2
c-global/local solutions relation between the constrained problem and the penalty problem
Appendix
D.3
c-stationary solutions relation between the constrained problem and the penalty problem
In Appendix
we prove the convergence of the proposed algorithm.
In Appendix
we provide implementation details and additional experiment results.
A. Extended discussion of related works
In this section, we provide an extended review of recent works that are closely related to ours.
A.1. Bilevel optimization
Bilevel optimization (BLO) is classical problem that dates back to (Stackelberg 1952 Vicente & Calamai 1994 Luo
al. 1996a). Gradient-based approaches with non-asymptotic convergence analysis and applications to machine learning were studied in e.g., (Ghadimi & Wang 2018 Chen et al. [021 Ji et al. 2021 Hong et al. 2023). These works focus on problems with (strongly) convex lower-level (LL.) objectives. Similarly, in simple bilevel optimization with shared optimization variable the upper- and fower-lever objectives, line of works focus on convex LL objectives, including
e.g., (Jiang et al. 2023. Merchav & Sabach 2023 Giang-Tree al. 2024 Samadi al. 2024
Doron & Shtern 2023
14

---

Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
For nonconvex LL objectives, pessimistic algorithm with asymptotic convergence guarantee was proposed in (Liu et al. 2021b), the stationary metric was studied for BLO with lower-level PL. objective, and alternating descent algorithm with non-asymptotic analysis was proposed in (Xiao al., 2023b). In T we provide a summary of the bilevel optimization works with possibly nonconvex lower-level objectives which may satisfy the Hölderian error bound (HEB).
Semivectorial BLO. OPS can be seen as a semivectorial simple BLO problem, where the bilevel program has vector- valued lower-level (LL) objective and scalar-valued upper-level (UL) objective. To solve such problems, one straightforward approach is to convert the LL vector-valued objective to a scalar-valuee objective through scalarization, and to optimize the scalarization parameter in the upper level, see, e.g., (Roy et al. (023). However, it has been shown that this reformulation could induce additional local minimizers or stationary solutions Dempe & Mehlitz 2019 Benko & Mehlitz, 202T Furthermore, this reformulation might require stronger constraint qualifications than the original problem (Benko & Mchlitz 2021]. Alternatively, penalty- reformulations have been considered (Bonnel & Morgan 2006). where the penalty function is defined as the maximum improvement amount of the vector-valued objective. However, no practical implementation, or relation of solutions to the original problem in nonconvex settings, non-asymptotic convergence analysis are provided for the reformulation. Recently. in (Giovannelli ct al. 2024), deterministic and stochastic risk-neutral and risk-averse algorithms are proposed, under the assumption that the LL objective is strictly convex w.r.t. the LL variable, and requiring the second-order derivative of the objective.
Another line of research study the problem with vector-valued upper-level (UL.) objective, and scalar-valued LL objective (Ye ct al. problem. For a more detailed review of multi-objectivee BLO algorithms,,
2021 Gu al. 2023 Ye al. 2024 Yang et al., 2024). It is sometimes also referred as the multi-objective BLO a survey Dejiia-eeDDios et al.
2023) and the
references therein. Besides, single-level multi-ohjective learning algorithms have been extensively studied, these include the
variants of the multi-gradient descent algorithm (Fliege & Svaiter 2000 Sener & Koltun 2018 Liu et al. 202 la
Liu &
Vicente 2021
Fernando et al., 2023 Chen et al. 2023 Xiao et al. 2023a) that are designed to avoid gradient conflicts
during the optimization procedure. For a more detailed review of multi-objecttve learning algorithms, see a survey (Chen
ct al. 2025 and the references therein.
Comparison of the theory in Section 3.2 to existing works. The works most related to ours regarding the theory in Section include (Ye et al. 1997 Luo et al. 1996b) and recent works (Shen et al. 2025 Chen et al. 2024b). However, a major difference that they directly assume the lower-level objective satisfies HEB, while in our work, we prove the property holds on bounded set for (x)) and p(x)) when the objective F is subanalytic. The two works (Ye et al. 1997
Luo et al.) 1996b) focus the cases with exact penalty. Other differences include that the results in (Shen et al. 2025
only consider LL objective satisfies HEB with 17 2, while we consider more general 17. Also, we do not require the global convexity or Lipschitz assumption as in (Chen et al. (024b), which is generally not satisfied by our merit function. Furthermore, we provide the relation between the stationary solution of the penalty formulation and the KKT solution of the constrained formulation under the general KL inequality, which is not discussed in either of the two works.
A.2. Limitation of linear scalarization and preference as constraint
Besides using empirical results on Example we also provide theoretical justifications to show the limitations of LS and KKT solutions for preference-guided MOL.
Limitation of linear scalarization. We first discuss the limitation of linear scalarization (LS) for preference-guided MOL. is known that LS is not good at handling nonconvex Pareto front. Prior works have shown that the optimality condition of LS is not a necessary condition for Pareto optimality, see e.g., (Athan 1994, Proposition 3.3). As a result, the solution set of LS, even by enumerating all possible weights of objectives, does not include all Pareto optimal solutions, and thus it does not include Pareto optimal solutions under certain preferences.
Below we provide the proof of Proposition 3.13 which shows that under certain initializations, gradient descent on the LS objective does not converge to a preferred Pareto optimal solution in Example 3.12
Proof of Proposition 3.13 and
In Example 3.12 there exists a solution xx E (-1, which is an optimal solution to both OPS
And there exists À= = [AI'>2]" e A with A2 = X (1=z")e-("--n" -()"
]e (15 that FF(x*), ) = 0. To show this, let c denote
15

---

Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
Table Comparison with existing methods for (simple) bilevel optimization with lower-level scalar objective, "SC" and "C" represent "strongly convex" and "convex", respectively; "comp" represents "compact set"; "Lip" represents "Lipschitz continuous", For non-simple bilevel optimization problem, lower-level and upper-level properties are w.r.t. the lower-level variable for a meaningful comparison. The lower-level objective in our problem is (2) T In M.
Method
lower-level HEB
other lower-level properties
upper-level
first-order
non-simple bilevel optimization
TAPTT-GM (Lii et al.
2021b)
smooth, comp
smooth, comp
X
BOME
[iu et al
2022)
11 = 2
PL. Lip. smooth
Lip. smooth
Pl., smooth
Lip, smooth
PBGD Shen et al. 2025
1 2
/
C, smooth
Lip, smooth
GALET Xiao ct al 2023b)
= 2
PL. smooth
Lip, smooth
x
AGILS
Bai et al.
2024)
11 2
KL, weakly (composite)
smooth
smooth
smooth
MEIIА Liu et al. 2024)
weakly C (composite)
smooth
SLM Lu 2023
17 2
PL. smooth
smooth, comp
simple bilevel optimization
C, smooth
C, smooth
CG-BiO Jiang et al.
2023
") 2
C, smooth
non-C, smooth
R-APM Samadi et
2024)
17 =
C, composite
C, smooth
C, composite
C, composite
PB-APG Chen et al.
2024b)
1 2 1
C, composite
SC, composite
nonsmooth, Lip
nonsmooth, Lip
subanalytic (provable)
locally Lip
FOOPS (ours)
(modified by 0
de 2 2)
KL (provable)
locally Lip
7
a positive constant, note that
VF(x) =21i (x-1)² (z 1) 21e (0+1) (x (x+1)
=e 2e (a-1)² 1)² (x 1) + x² ) (x*
+ 2e -a++))))) (x + 1)(1 - x²) -=" (x'-)))))
-2c(1 1)(x* 1)e (x+1)
dn --1
x- 4x')
(16)
x+1
x²
Let r(t) z-1e Then r(x) > r(z") = VF(z) 0 and vice versa for r(x) < r(x*). The above equation implies
x+1
that when r(x') r(x"), VF(x')> 0. Therefore, VF(=*)>= 0. Also observing that there exists different points -1 < æι < x² < 1 that
r(x1) = r r(x").
(17)
This means that æi, 22 22 are all stationary points of X FTF()) Furthermore,
1. for x' (#1, U (z2, 1), r(z') r(=*), thus V=(=')> > 0, then gradient descent (GD) on A FF((2) starting from o' E (#1, x²) with sufficiently small step size converges to I1, and it converges to 22 if starting from x' E (x2, 1);
2. for x' E (-1, (x*" (2), r(x') < r(z*), thus (Fx'))> < 0, then GD on A F(x) starting from x' E (-1,21) with sufficiently small step size converges to æ1, and converges to 22 if starting from x' E (x",
This proves that they will not converge x..
Limitation of preference as constraint. We then discuss in more detail of the limitation of modeling preference by constraints. We verify Proposition 3.14 by constructing an example with a KKT but non-Pareto stationary solution. Using Example 3.12, and noticing that one solution that PMTL converges to, denoted as x². has objective value that is approximately F F(x*) (0.80; 0.99], which satisfies the feasibility condition that H (x*) 0. Furthermore, its gradient at x" can be computed approximately as
(x²) =0.062
(18a)
V f2(x") =0.0002.
(18b)
16

---

Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
Clearly, x² not Pareto stationary. By the KKT stationarity condition, further have
VF(#)A5+ + VH(T)An - VF(1) - -4
+ 2n)
-41% )) = 0, for some Xy E A
5
= =V (y
(19)
It can be verified that 0.5062 + 5 0.0002(1 -A,,1 4 0 has solutions, c.g., Ay [0:1], -7.9 x019x100 Therefore, x' is KKT point.
10-5.
We use another example with strongly convex objectives to prove Proposition 14 that a KKT point to 11 is not necessarily Pareto stationary.
Example A.1. Let M = 2, = 2, and M, = M, = 1. Let X = IR?, and x = [21; The objective F and constraint H is defined as
F(x) = ((11 - -1²² z 0.5z + 23) -9 (f)
(20a)
(20b)
Proof of Proposition 3.14 In Example A.l the gradient of F can be computed by
VF(x)= = [2 - 1)
(21)
20²
2m2
[4 3 0 0
For x = 03. VF(=)
Let AM denote the (M 1)-simplex. Apparently, there exists no A such that
FF(x)> 0. Therefore, not Pareto stationary.
Then check whether satisfies the KKT condition. First, it satisfies the feasiblity condition since (x) 0. Second, by invoking the KKT stationarity condition, for some X, A 2 An R. we have
4
3
1) =
VF(x)Ay VH())A, VF(x) A
An
(22)
8
0 0
-87x
It can then be verified that the above holds true when 'y = [0, 1] E 2 and A -0.25.
Therefore, x is a KKT point but not a Pareto stationary point. The proof is complete.
B. Proof of the properties of the merit functions For convenience, define the merit function (zx and restate the smoothed merit function o1,r (x) below.
(x) max yEX
min mE[M]
(fm(x) fm)
"110 111--11² -y1²}
(23)
M
1 || - y/²}
U1, (x) = min
In
+ 2
(24)
yEX
m==1
Correspondingly, define (z y) below for analysis. Note that U1,r (z) mingex x hi, ().
M fm(s) Smlla
1
h1, v) =n
+ 2 =1100 - -yl12.
(25)
m=
B.I. Auxiliary lemmas
Lemma B.1 (Restatement of (Tnnabe et al. 2024 Theorems 3.1 and 3.3)), For | 2 0, consider the merit function ux(x)
defined in (23). Then (z) 2 0 for 1 2 O. (x) = 0 if and only if x is weakly Pareto optimal. For 1 > 0, x is weakly
Pareto optimal implies u(x) = 0: furthermore, if fm(x) is convex for all m E [M], then u(x) = implies x is weakly
Pareto optimal.
17

---

Efficient First-Order Optimization on the Pareto Set for Multi-Ojjective Learning under Preference Guidance
Proposition B.2 (Smoothness implies weak convexity). If locally Lipschitz, function f is f then it is also
-f,1 -eei-laklly convex.
Lemma B.3 (Log-sum-exp function preserves weak convexity). Let (m( m E [M] be weakly convex with modulus Mm- Then In / is weakly convex with modulus μt.
pm E IR Let j = millm[M]
Proof of Lemma B.3 By definition, and since p minme[A[] Pms we have fm (x) ||1=r|² is convex for all m E [M].
Also because the Log-sum-exp function preserves convexity, we have that In (Em=) (m =|m)") is convex. Further rearranging this function, we have
M Σ
M Σ fm(())
In Σ fm()) -l
- In (e $|1-11
f em(())))
In
P ||/1|
(26)
which convex. By definition, this implies that In complete.
EEM= cfu(l)) is weakly convex with modulus j.. The proof is
Corollary B.4. If (m()), E [M] is weakly convex with modulus pmm. R. and I + minme(M] Pm > O, then hy, (2r, v) defined in 25 is strictly convex w.r.f. and the solution to minyex (1, y) is a singleton.
Proof of Corollary B.4 By the pm wwek convexity, 1 f (V) is f-weakly convex w.r.t. Therefore, combining with
Lemma B.3 the function r In Em= fm(m))-f(tt is ji-weakly convex w.r.t y. where minme(M) Mmm Since
++ me(a] Pm = I J > 0, h1 (x, y) is strictly convex w.r.t. y, and the solution to mingex h y) is unique. The proof is complete.
Lemma B.5. If fm),, m E [M] is continuous and weakly convex with modulus pms and 2 -minme Pmo then there exists x E such that (1,-(x) - - In M.
Proof of Lemma B.5 From Corollary B.4 since I -minme[M] Mms h4 y) is convex w.r.t y. Let be the indicator y (2, v) aP(u) if and only if y = arg minyex (x,
function defined on X. Then, 0 V
By the definition of 1u.- (I, the gradient V y (2, y) can be derived as
(mis) Smie)
V yglu,(0,11
Vm (v) + [(y .t).
(27)
m=1
When y = x, it can be further derived that
1 M M
Σ Vm. m=1
(28)
Recall that X F(x) is lower bounded for all À E A And A F(x) is continuous since fm are continuous for all E [M].
We assume either X' is compact, or X' = RD and fm is coercive for all m E [M]. Then the solution to min X F(x)
exists. Let x² arg min ΣM (x), which implies
M
0E
(mm(x") ( +PP()")
(29)
Combining 29 with 28 we have that 0 E V Vyli, + OP()) ((),))(or,r>)) Therefore, x² E arg mingex hn,("", (a",v) .v),
and thus
M
Im /m(e))=(((11)) = 1 M.
min h (a".v) = h1,-(",, T
(30)
*EX
m=1
By definition, Vi, (x*) can be computed by
min berr (x= -- yEA
(31)
which completes the proof.
18

---

Efficient First-Order Optimization on the Pareto Set for Multi-Ojjective Learning under Preference Guidance
B.2. Continuity of the merit function
Lemma B.6 (Continuity of ht,r, 01,r, and p). 1) (x) is continuous for all m [M], then the merit function v1,r (x)
lower semi-continuous.
2) Given bounded set Nc. suppose fm is Lipischhit continuous on Xc for m ......MM. Let lz supzeXa ||=||- Then - y) is (Ez + 21lz)) continuous w.r.f both Xc and y E Xc, v1,((x) is Eur -Lipschitz continuous on Nc with k = Eg + 21lz, and 0 2 1, p(x) is E--Lipschitz continuous on Xc with Ep = 0((22)
c
Proof of Lemma B.6 Proof of 1). Recall that (x) = millgxx 11. y), and he (z, 1) - LSE, (fm (y) Jm (x)) +
| (ax-yll yll.. Since (x) is continuous for all m E [M], and the LSE function is continuous, we have h (I, y) is continuous w.r.t. x and y.
X, given any e > O, let y E X satisfy 1 D) S minyex h4 (z. e. As hr is continuous (z, 7). there exists T such that
For any sequence (at) S satisfying lime- Jt
min h4 (Ft,)) S ( 1) s (x, 5) S yEX
min (#, y) + 2c, vt T, yEX
(32)
and thus
lim sup min (i, v) S min N1. (7. y) + 2e. t-000
(33)
yEX
yeX
As the above inequality holds for any e 0, we obtain.
lim sup min hy - S min ht,- (ā. y)
(34)
t-
veX
yEX
which proves that (x) is lower semi-continuous. Proof of 2). We prove the Lipschitz continuity of h (2z, v) below. We define
(mm(()))mm(t)
Tm (m 3)
(35)
EM - (m
Note that
|| (x, S
Σ
T. (z, + ||(x - s + ll/l s ly 21l
(36)
M
[V,,,,,-4,, 8)11 <
Tm (1, (1
||((x - -)ll s e + [[|||||| + lbll S ly + 21e
(37)
m
Therefore, (x, y) is (ly + 21e - continuous w.r.t. both x E Xe and y E Xc.
Next we prove the Lipschitz continuity of the merit function Ur, under additional assumptions. From Assumption I the functions fm (z), m 0, ...... M are Ly-Lisschitz on bounded X where ||^||| s lz. From ( we can compute (z). We then derive the bound of [x)] below.
M
[er, =
Σ
T (m) 1(x vī.- (x))
<ly + || + || (x) & E,
211,
(38)
which proves that (x) is (&, + 2le,) - continuous on X.
Recall that p(x) (v,, (x) + In M)² For 0 1, the gradient of p(x) is given by
Vp(x) 0 ur. (x) + T In 11) 8-
(x)
(39)
19

---

Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
Note that v1,r (ar) + In M is bounded compact set since vi, (a:) is Lipschitz on this set, i.e.,
Ur, (z) + 7 IM fu,,- 11= =x'll s 26,, lo with lerr = + 211
(40)
Then Vp(z)]] can be bounded by
[V((2)] < EBlurr (v1,- T In MM) 0-1
s fl +m.
(41)
<blur- (21 Lx) 0-1 = (2(x))
0 e0
(42)
o1r
which proves that p(x) is (0(2 )0 e -Lipschitz continuous on X.
6-1
Corollary B.7 (Lipschitz continuity of sp.). Under the same settings as Lemma E.1 let la supzexe || Given >> (x) (7lp + Lipschitz continuous on Xc-
0,
Proof of Corollary B.
Recall that ς- (z) = fu(x) + yp(x). The proof directly follows by applying the ep-Lipschitz
continuity of p from Lemma B.6 and the LypLsshhiizz continuity So from Assumption !
Lemma B.8 (Lipschitz continuity of vf,r (x)). Under the same settings as Lemma E.
recall that
(x) == arg min (2, = arg min { yEA
Σ
Im fm (z)
1 + 2 1| 1--)1?]
(43)
yEN'
m=1
2M0, 11 + E311 + 4M8E)
For 1 Er,1 2 phg > 0, there exists vi.
> 0 that for all x, x' E Xc, the following holds
(1)),(()) -),((11)) (a')) S -11 x'|l-
(44)
Proof. By Corollary B. for 1 + min [M] Mm 2 Mhg > 0, the function (u, y) is Phy -sronnlyy convex w.r.t.
Therefore, from (Dontchev & Rockafellar 2009 Theorem 2F.7), or using similar arguments for the proof in (Chen et al.)
2023 Lemma 15), we can derive that
hu (x) - vi,r (z') S MTT, ha. (2,z) v h (z', y)
(45)
can be further computed by Let Lg E Rax4 denote the identity matrix, then V 2 14, 3)
Am(Wi//m(a)
V (2, V. Σ
V + 1(y x²)
as 2mml
Smilal Smlll-Amia Smila)
am(2)))
=V, (F(y)=(Z,))
M +l(y - xx)) with x<x [TT ().,,)).... (x.
8(x.9)
M
1 S(I, ())(,)) +
Ty (z (m)
Σ m=11
Tmm (x, (x, fm + 11.
(46)
We first bound [|S(,, Sz, T) S(z', .))((')) v) by
(((z,))S(x.))) 5(x' S() v) TIl s (1S((x + 1|5(2', will [|[(z, v) 5(a'v0)l
(47)
Then from Assumptions and can bound /1 (x, v2 hu (z', w)1l by
2
/1, (xr, 3) 2 br (2', .v)l
sy
M
Σ
Jm (x, 1/) (m 1)Il (11S(z, +15(2' ([((((.))]] ((5(,)))) S(+',v))
m=1
20

---

Efficient First-Order Optimization on the Pareto Set for Multi-Ojjective Learning under Preference Guidance
M
IT (2, v) Tm (2', y V
m=
26 (15(s..)) s(d', Tm (x, Tmm (o's w)ll 1 taa)
(48)
where [T, v) Tm ( (x), can be further bounded
|| Im (a,, y) Tem (2', 22'1 S 28 || 2'11.
(49)
Similarly, [IS(z, v) - S(r', v()l can be further bounded by
2M
[|S(z, 3) 5(x1.0))
(Tm (2, v) 7m (m fm)
11
x
(50)
m=1
The proof is complete with byt,
2M
AMP
B.3. Proof Proposition 3.3: relations Ut, and weak Pareto optimality
Proof of Proposition We prove each property as follows.
Property For the first argument, by the property of the Log-sum-exp function (Nesterov 2005). and since taking mingex preserves inequality, have that
((x) r In M v1,r (I) S (x).
(51)
This implies that, & 0, (x) uniformly converges to (z). Also recall from Lemma B.1 that is weakly Pareto optimal if and only if 0. Therefore, x is weakly Pareto optimal if and only if lim, (2,((z) 0. The first argument is proved.
For the second argument, from Nesterov 2005). we have that
M Σ
T
In
e
Im Im(e)=/m(()
+ 2
v112 S + max (fm(y) - fmn( + + 22110 - y11
(52)
mE[M]
Since taking m preserves inequality, it implies that
M fmil)) (mii)))
min yE
T
z11zz u1?? S r Il
M
min vex
max (fm(y) - fm + + -101 mE(M)
m12}
(53)
m==1
which proves that
(1,((1) 2 min max (fm - fm) + 111 y112 IM yEA
mE[M]
=u((x) In M - M
(54)
where the last inequality holds because (x) > 0. Furthermore, there exists X' such that (x.(2x) -7 In M by Lemma B.5 Then min Ut, (z) = - M.
Property 2. For the first argument, by Lemma B. if x is weakly Pareto optimal, then u(x)) = 0. Furthermore, by Property-1, (xxx) 2 (x),, which proves (x) <<
Conversely, for the second argument, for condition a), vo. (x) < 0 implies that
ū(x) S vorr (x) In M M.
(55)
21

---

Efficient First-Order Optimization on the Pareto Set for Multi-O/jective Learning under Preference Guidance
By the definition of ú, for all E X, it holds that
min fmm - ū(x) S M. mE| m
(56)
In other words, there exists no 2 E X' and # such that, F(z) F(x) 7 M.
For condition b), O, (.)((a)) - In M implies that
S u((x) S (1) + M S 0.
(57)
By the definition of (1:), it implies
1
min {fm (x) - fmm( mc(N/]
2 y11² 0
(58)
By the convexity of X, take X, and E (0, then (1 1)x 12 X. Let y (1 -t) + tz, and plug it into the above inequality, we have
1
x + [z)] - 2 - y11² 2 0 min (Sm (x) (m
(59)
mE[M]
2
By the (1, point-aaaa convexity of fm at for all m E [M], fm ((1 +)x + tz) S {z)((2) + (1 - fx). Therefore,
min mc[Md]
(t)
||t(z - x)11 so.
(60)
Dividing both sides by l and letting 4 we have that for all z E X,
{fm(z) - (2)} s 0. mEIM]
min
(61)
This proves x is weakly Pareto optimal.
The proof of the properties of the smoothed merit function is complete.
B.4. Examples of point quasar convex functions
By definition, p-(strongly) convex functions are (1, (4) (stronnyy) point quasar convex everywhere. This quasar convexity property is also closely related to convexity, restricted secant condition, variational coherence, PL condition, invexity, etc. For more detailed discussion and more examples, refer to e.g., (Hinder et al. 2020 Appendix A, D.2, D.3).
B.4.1. EXAMPLES CONDITION 2-B) IN PROPOSITION 3.3
Example B.9. For all m e [M], fm are strongly convex on X'
Example B.9 is the simplest case covered by our method. But existing works which focus on such cases usually require second-order information in the algorithm, as summarized in Table 2
Example B.10. For r [2] E RR2 let X RRa. Define (x) = 27 fz(z) = atag.
In Example 10 S1, /2 are nonconvex but star-convex HHinder et al. 2020) at x. = |0; 0j. Furthermore, xx satisfies that (x") = - In M. And both f1, fz satisfies the (1, -o-in quasar couvar-c at I within X.
B.5. Proof of gradient of the smoothed merit function
Lemma B.11 (Gradient and directional derivative of vz,r), The gradient of U1,r can be computed by
e (x)) ΣM
V Σ Te (=) 1(x (x)), with Tm xm(
(62)
1 (fm (x)) (x))
22

---

Efficient First-Order Optimization on the Pareto Set for Multi-Ojjcctive Learning under Preference Guidance
For all X, the directional derivative of v1,r, denoted as v/ (2; x)), can be computed by
M
(2; 2)
7m (i
z) -1(x -ví,(()) (z
(2=x))===1)) (z-x)..
(63)
Proof of Lemma B.17 Recall that we have defined
M
1 y) = T In
h1. (x,
Σ m=1
+ 2
|| -yl1
(64)
- -1,- (z, Vi,, (x)), with vi (x) E argminged ht.7(z; v). If I + minme[M] Pm 2 <> 0, by Corollary B.4 Vi, (a)) is unique. Furthermore, yi, (r) is continuous w.r.t. x.
By definition, (2) minggxx b1,r(1)) v)
By the extended Danskin-type theorem in e.g., (Shen et al. be computed by
2025 Proposition 5), oz (œ) differentiable. Its gradient can
Valy, (2,, (x))
M
Im (v (m)))
(m)(x) - 1(x - (x)).
(65)
Em=1
M
6
Imatyg,- 10)--mml)
Then given all 2, X, the directional derivative of u2,y (x) can be computed by
M n (z, (x)) (2; x)) 1(x yi, (x)) [2 x)
(1; - x)
for all 2 E X
(66)
m==1
Imif) Smiiel
where nm (x,
The proof is complete.
Im-lil-mmt -m
M
C. Subanalyticity and related properties
In this section, we first discuss some preliminaries subanalyticity, and then prove the global subanalyticity of the merit function (z))
Definition C.1 (Subanalyticity (Bierstone & Milman 1988) ). 1) A subset S C 12 is called semianalytic if each point of R29
admits neighborhood V for which S V assumes the following form
(rEV: fu(x) 0, 0, 0}, (=
UN
(67)
where 9ig. V are real analytic functions for 1 < i 2) A subset S C RR9 is called subanalytic if each point of R29 admits neighborhood V such that
snv = far E R9 (x,y) E B}
(68)
where B a bounded semianalytic subset of R R
3) A function F R u {+oo} is called subanalytic if its graph is subanalytic subset of R x R.
Definition C.2 (Global subanalyticity DDiies & Miller 1996 p. 506)), Let [.I,..., xig) R9, Define the function
.11
Tig
(x(x)
(69)
1 + x
x2
1) A subset S of Rd is called globally subanalytic if its image under b is a subanalytic subset of R?
2) A function f R9 R U (+00) called globally subanalytic if its graph is globally subanalytic subset of R9 x R.
23

---

Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
Proposition C.3 (Bolte al. 2007)) ) Globally subanalytic sets are subanalytic, and conversely, any bounded subanalytic
set is globally subanalytic.
Lemma C.4 (Dries & Miller (99)).
The image the preimage of a globally subanalytic set by globally subanalytic
function (respectively, globally subanalytic multivalued operator) is globally subanalytic.
Lemma C.5 (Projection theorem (Dries & Miller 1996). Let , [n+1) (21,..., .n. be the canonical projection
from Rn+1 onto R S is globully subanalytic subset of [R*+1, Ihen so is (I) in R
Lemma C.6 (Lojasiewicz factorization lemma (Bierstone & Milman 1988 Theorem 6.4)). If X arg m UL (2)
globally subanalytic, and vi,r (z) is continuous and globally subanalytic, then the (e. n)) HHölderian error bound holds for 21,r (x) for some e. 7 > O.
C.I. Proof of global subanalyticity of Ut P, and us
Lemma C.7. Let X and y be two bounded subanalytic subsets in R9. Let f X x y - TR be bounded subanalytic function. Then 1) the function & below is bounded and subanalytic, thus globally subanalytic.
3: max max ((I,
(70)
may 2) Given v, the solution set (xx) = arg max yEy (xx v) is bounded and subanalytic, thus globally subanalytic.
Lemma 4. 4.1)). The key difference that instead of using local boundedness of the functions, we start from global boundedness of on X' and derive the global boundedness of ø, which, combined with subanalyticity, leads to the global subanalyticity of ø on X.
Proof. The proof mainly adopts the proof idea of Kosiba 2025
Let Gr(-) denote the graph of function. Since f is bounded, let of denote its upper and lower bound, respectively. And define W = {w I of S w S cy.. Then W c. R is bounded. Consider the following set
v. A (,, E X x x X W/| (,, E Gr(J(z, S w).
(71)
Note that 2, y are bounded, and so is z because of the boundedness of f. Furthermore, w is bounded by definition. Thus A is bounded. Also note that A is subanalytic because / is subanalytic, its graph is subanalytic, and the Cartesian product of two subanalytic sets is subanalytic. Therefore, A is globally subanalytic.
Define the following projection IIA and the set B by canonical projection of A.
A : X x T5. W (xr, 2, (I, w) X X x W. B = II (A) [ x x W [(x, S sw).
(72)
(73)
Then B is globally subanalytic based on Lemma C.5
We also define the following auxiliary sets
BR = (Z, EX W}: BR = ( E X y W| f(z,y) w).
(74)
(75)
Then we define the projection IIg and define the following set C' by canonical projection of B.
I X x y x W e (2, + (x)w)) E X x W, C = (B)
(76)
= ((x,w) X W sup f(z, < w].
(77)
vEy
Since C' is bounded and subanalytic, it is globally subanalytic.
We further define the following subanalytic set and projection
D = (1x wi, W2) E X' x W W
(z, w1) E C, (2, w2) E C, > w2).
(78)
Up X x W W (x, wT, w2) (z, wi) E X W.
(79)
24

---

Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
Finally, observe that
((IDD(D) s (x, w) F there exists no w' such that (z, w'), (2, w) E C' and w > w/
(80)
there exists no w' such that sup f(x,8) y) S w' and sup f(r, y) - w and w > w' vey
(81)
yey
which means that Gr(((x)) (D). Since Gr()(z)) is bounded and subanalytie, thus is globally subanalytic. By definition, Φ is also globally subanalytic.
Next proceed to prove the global subanalyticity of y* given Define the following set E and projection IIg
E = ((r,y, E x' x W (æ, w) E Gr(d(s)), f(x,0) = w) Hg
(82)
W (z. y, w) (x. x.
(83)
Then (xx(E)= ((1,1) E x x y/ v E (x)) is globally subanalytic. Furthermore, given Cx E X for any Ca. E X, we have
(g) n ((z.)) E X x x == e ( cx
(84)
which is globally subanalytic. Taking projection II: : X x y e (z. v) + y y yields that y (x) given x = Cr. for any Co E X' is also globally subanalytic.
Proof of Lemma 3.5 Part 1: By Assumption + Jm is globally subanalytic for all 0,..., M. By Definition C.1 and
Lemma C.4
subanalyticity is preserved under the subanalytic LSE function.
Recall the definition of (x, in (25). By Assumption and Lemma B.6 (z, y) is Lipschitz continuous w.r.t. both 3, E Xc. thus hr, y) is bounded for y) E N' x Xc. Combining the above arguments, 11, y) is bounded and subanalytic on Xc, thus globally subanalytic on Xg by Proposition C.3
Part 2: Next, we prove that Vt,r (x) min h (zz, y) and p(x) (v),(x) In are both globally subanalytic on Nc. This directly follows by applying Lemma C.7 1).
Part 3: Finally, we prove that X ei.r = arg minzex U1, (x) is also globally subanalytic on X This directly follows by applying Lemma 2.7
Consequently, the merit function vir (x) satisfies the (e, 1)) Hölderian error bound for some 2, 17 > 0 on a bounded set X by Lemma C.6 The penalty function p(x) also satisfies the (Op, 1p Hööldrrin error bound with @p e and Upp On. U
Following similar arguments as the above proof, we can obtain that the original merit function uz(x) is globally subanalytic on a bounded subanalytic set, and thus satisfies the HEB on the set. This result formally stated below.
Corollary C.8. Under Assumption 3 and that X is subanalytic, given compact subanalytic set Xc, suppose f fmx(x) is continuous and bounded on NX for m E [M]. Then both X n&C and 01, on N are globally subanalytic. Consequently, the merit function (a:)) in 23 with some Qus > 0.
without smoothing satisfies the (Qu,Tu) HHBB in Definition 3.4 on XC O X,
Lemma C.9 (KL inequality (Kurdyka 1998
Theorem 1)). Let f. fΩ + R be subanalytic function which is differentiable in (0), where Q is open bounded subset of R2. Then there exist 0, 0 and > 1 such that: ell V f=(x))) Z (f())), for each x E Q such that (f()) (0, If in addition limz- f(x) ) = 0 for some a E Ωt then the above inequality holds for each x E (0) close to a.
C.2. Examples of globally subanalytic functions
We summarize some commonly used globally subanalytic functions and their corresponding Hölderian error bound (HEB) in 6 The first few examples of convex functions in Table are directly referenced from (Doron & Shtern] 2023 Table 2) and (Chnn et al. 2024b. Table 2).
Below, we prove the HEB of the last four bounded functions in Table
25

---

Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
Table 6. Summary of some functions satisfying Hölderian error bound with corresponding exponents.
Functions
Remarks
Names
"
Convex functions
maXig[m] (a., 1)- b,)
04 E R b E R"
Polytope
1
maxie (m]] [lla
|1 zo zolle= V [x xo) Qix ma)
39
0, R
Q Q-norm (Ellipsoid)
1
(Amia (Q))a((Q)=
- xollp
20 R2 . p2p1
n--no
(Amin (Q)) Qis is
D log(1 exp(-a,
a. E R2 b E R. A E Ruxx
Logistic loss
2
a function of ac
(ax) ||
I convex. a 0 Bounded and possibly nonconvex functions
strongly-convex
2
(1)(2) x
x 00, 3
Sine
2
(5)
x E [0, 1|, >
Polynomial
p
2 E [0, 1]
Exponential
ln(x+ + 1)
x E [0, 1]
Logarithmic
2 1
Io(2)
Proof of HEB of bounded functions in Table 6 We prove the (e. n) Hööderria error bound (HEB) of the last four functions in Table one by one as follows.
1) Sine function. For E [0. [0, == is the unique minimizer of sin(z), thus for 17 2 1, (dist(z, x²2n)) |x|| S
(g) sin(x) for all E [0, 1²) Therefore, sin(x) satisfies (e, H)) for E [0, 2T] with 2 and @ (z))
2) Polynomial function. For E [0, 11. x=' 0 is the unique minimizer of æP. Thus (dist(ar, Xii)) |x|/² S x for all e [0, 1]. Therefore, x² satisfies (e, 17) HEBB for z E [0, 1] with r p and 1.
3) Exponential function. For x E [0, 1]. x² = 0 is the unique minimizer of e". Thus (dist(z, (atn =)""))" |a|" S e² c² for all x E [0, 1], and 2 1. Therefore, ex satisfies (g, HEB for x E [0,1] with 17 2 1 and g o= 1.
4) L function. For x E [0, 1], x= = 0 is the unique minimizer of In(x + 1). Thus (dist(r, ))n))) |z|0 S (n( In( + 1) for all x E [0, 1]. and r7 2 Therefore, et satisfies (e, 7HEB for x E [0, 1] with rj 2 and 0 In(2)*
The proof is complete.
Remark C.10. Note that, even though we have shown in the above that the exponential function satisfies HEB in a compact and subanalytic set x E [0, 1). it known that the exponential function not globally subanalytic on R. In the following proofs which require the HEB property, it suffices to show the global subanalyticity holds on compact and subanalytic set constructed from the corresponding problem, which leads to the HEB property the compact and subanalytic set. And HEB of p(z) on compact and subanalytic set within X is sufficient to show the relations of global/locallstttionary solutions of the penalty problem to the bilevel problem as long as there exists bounded solutions to min p(x), even if X is not bounded.
C.3. Relations of Hölderian error bound, quadratic growth, proximal PL, and proximal error bound
We further discuss the relations of Hölderian error bound (HEB), also known as Hölderian growth, with other commonly used conditions such as quadratic growth (QG), proximal error bound (EB), proximal PL inequality, and strong convexity (SC). Below, we consider a general function for the discussion.
d(x) = f(x) + g(x)
(85)
with f smooth and g convex. In our specific problem, is an indicator function on X. Let X' denote the set of minimizers for cb. We first review the formal definitions of the above conditions, and then discuss their relations.
Definition C.11 (Proximal error bound). The function & in (5) satisfies proximal error bound if for / >> 0, there exists
co > that
dist(x; S cot-1/la 1|x prox, to (x fx)(
(86)
Definition C.12 (Proximal PL). The function Φ in (85) satisfies proximal PL inequality if for t > 0, there exists c >> 0haa
(xx) x(x") S cDg(1, t) with x" E X2, and
26

---

Efficient First-Order Optimization on the Pareto Set for Multi-Ojjective Learning under Preference Guidance
(2,t)) 24 min [V](()), x) 2 |yy + g(v)= -g(x).
(87)
By definition, QG is special case of HEB with the exponent 1) 2. And similarly, proximal KL generalizes the concept of proximal PL. The relations of SC, proximal EB, proximal PL. QG have been studied in existing literature. We summarize these relations using the equation below.
is SC
proximal EB
proximal PL
QG
proximal EB
proximal KL
НEB
(88)
where (a) has been proved in e.g.. (Karimi et al. 2016 Appendix F-2); (6) has been proved in e.g., (Karimi et al. 2016
Appendix G); (c) has been proved in e.g., (Liao et al. 2024 Theorem 3.1) with additional conditions that ø is closed and
weakly convex, or in (Krimi et al. 2016 Theorem 2) with additional conditions that is a constant.
Furthermore, when the function f is convex, we have that
proximal EB/PL
QG
$
proximal EB/KL.
HEB
(89)
Corollary 3.6); (f) has been proved in e.g., (Bolte et al. 2016 Theorem 5). In this paper, we provide proof of the relations between KL, HEB, and EB in (88) for nonconvex of and constant y in Lemma C.13 and Lemma(C.14 below.
where (d) has been proved in e.g., (Drusvyatskiy & Lewis 2018
Lemma C.13 (KL implies HEB). Consider the function & in 85 with g(x) = 0, and min Φ(x) = 0. If 6 satisfies the (cp, ) -L inequality on Ω with exponent ag > 1, then it also satisfies the (0o. no)-HEB on Q with exponent ne a. II
as
and es
9--
Proof of Lemma C.13 We first define an auxiliary function
[(x) = (d((;)) -
(90)
Since & satisfies the KL inequality, then for any & X3, and thus (bx) * O. have
[+(2)|| = -1-
_ (1- arp (d(x)) -o
Vo(x)
(1- as (0(x))
1 2 V
(1
(91)
Cp
Also satisfies the KI. inequality implies that ø is an invex function and thus T, is a non-negative invex function with a closed optimal solution set and zero optimal value. or any point zy & Xú, consider solving the following differential equation for æ(l) & X2:
dx((1) = -I((x(())
(92)
dt
x(t = 0) =
(93)
Following similar arguments for proving PL implies QG, see e.g., Karimi al. 2016, Theorem 2, Appendix A), there exists T such that x(T) E Xj (and this point the differential equation ceases be defined). Then
1 (VL(x),
/ (VL(x(t)), dx(t), dt dt
L(xo) L(xx)=
(VL(x),dr)
(94)
(' pptt =MIT.
[V(I(t)) >
(95)
27

---

Efficient First-Order Optimization on the Pareto Set for Multi-Ojjective Learning under Preference Guidance
As ((re) 0, this shows need to have T ((ro)/LL so there must be 7 with s(T) X The length of the orbit
at() starting wo, which we'll denote by ((x)), is given by
D(xn)= = [( [|do(1)/d((dd J [VL( 2 1:00 -xpl
[["
(96)
where dp is the projection zo onto 22 and the inequality follows because the orbit a path from ag to a point in 2Y (and thus must be least as long as the projection distance).
Then further bound
VL(x(t)) 2 VPL [ [VL(x(t)]ld
(xzo) = L(xo) - ((TT)
2 Vuz xpll
(97)
The proof is complete.
Lemma C.14 (KI. and HEB imply EB). For ((x) in 85 with g(x) = 0 that satisfies the KI. inequality with exponent Og and the HEB with exponent no. i.e.,
KL: ca Vo(z)) 2 ((x),
HEB: <(x) 2 2s -1 (dist( (x))) n
(98)
Then it holds that
th with Th = 7 and @h = (2oco) do. V 2 2h (z))
(99)
as
Proof of Lemma C.14 The proof directly follows from combining the two inequalities from KL and HEB that
co. Vo(z))] 2 d(x) 2 200 (dist((x, n1
(100)
Rearranging the above inequalities proves the result.
D. Proof of relations of different formulations
In this section, we prove the relations of the solutions of the bilevel problem and the penalty reformulation. Recall that we denote the penalty function with exponent as
p(x) +
(101)
Recall that let x = arg m (x). Similarly, we define X arg min (x).). For 0, define the e-approximate solution set (level set) below
X. (a E X p(x) Se.
(102)
Then X X, S Xe. We use X' denote a compact subanalytic set, X's C X to denote a closed subanalytic subset of X. and define ze (x) E arg min || z||.
D.I. Proof of Theorem 3.7 1: the e-global/local solutions relation of the smoothed problem
Proof of Theorem 3.7 1. We use u, as an auxiliary merit function, defined below
(r(x) == sup min vex mE(M]
(Sm - (v) 11y - x 112].
(103)
Under the conditions Proposition 3.3 2, solving (PSS) is equivalent to solving
min folx), s.t. E X = {x E X' ux(x) - 0}. xex
(104)
28

---

Efficient First-Order Optimization on the Pareto Set for Multi-O/jective Learning under Preference Guidance
Part I: proof of global solations relation. Let mg be an (e, d)globall solution to (CP). then 2g E X,, i.e., ut (drs) + In M 2. have that un (3ss) S n1, (2ra) + In M S 6.
6. From Proposition
Let x² be global solution to (OPS). and let 2p = Proix; (æt)) By the (.) 1h) H-EB of the function 2n in Corollary C.8
sec Appendix C.1 we have |. - xpll = (2s Xi,)) I (ew6) Ri..
For 2 In M, Xr, S Xg, thus fa(x*) fo(as) 2 By the floocll Lipsehitz continuity of fo. holds that
fo(x") - fo(xs) & fo(xp) - fo( - 11 - =xpll - {5(ea))
(105)
This proves that 26 is an (<', 8) -global solution to OPS with e' = (
Conversely, is an (e, (3.6))gll -global optimal solution to OPS)) then by definition,
fo(z') min fo( S e, and x' E Nu =
(106)
In other words, (1() 8. which implies ur, (1,) (T')+TlI In M 88+Thi In M, i.e., o' Ny with 8' 88+7 M. Furthermore, since & S Ng, mi, fa(x)= I mingex.,. fz) therefore
fo(2') - min fo(x) =fox²') zER
min fo(æ) + min fo(x) =EXuy.8
min fo(z)
=EXug,
Se min #EXu,,
fo(æ)
min fo(#) xENa
(107)
where letting zzg E arg min ,ix, fo(x), and p0000 o = Projx (z), then min fu(z) mmn fu(Ø) can be further bounded by
min fo(z) - min fo(x)= min fo(x) fo( =EZuy.o
=ENiy. ffo(= fo(I3r,)) I Ef|lz'/. F ,lll S ( o Xt, S (end"))
aEXy
(108)
Therefore, x' is an 8'),8" solution to (CP with é' + (e th and 8' 8
Part 2: proof of local solutions relation. Let vs be an (c, -ocal solution to CCP) then 28 E Xs. and vs is an (c, 6)gllbbl solution to (CP) on the set X' n B((s, r). Applying the results in Part we get that is an (e', 8)-global solution to (OPS)
on the set X' I (8(2,, r), thus an (é', -oocll solution to (OPS) on the set Y. Similar arguments can be used to prove the converse statement.
Combining Part and Part completes the proof.
D.2. Proof of Theorem 3.7 2: the e-global/local solutions relation
We first present some auxiliary lemmas below, then prove the main results.
Lemma D.1. Let X' S IR be compact subanalytic set with Xe O No + 0, and thus Xc n + 0 for some 2 0. Suppose fo(x) is --iipshhitz continuous on NG ( X' with some l >> O. If Vt, is globally subanalytic on Xe NX then it satisfies the (g, 17) -)-HEB on Xg O X with some 0, r) > O, and p(z) satisfies the (0p: -HEB on Xe n X with 0p = e" and "pp = On. Given x XG X, holds for any e that
11 Thp
up
(11 1),
Tp > 1, > 0:
fo(x) + xp(x)) - fo(=c())) -cy =
7/
(109)
Tp 1, 2 e
Proof of Lemma D.I Since (x) and p(z) are globally subanalytic on X' X, there exists 2. 0 that vt, (1) satisfies the (e, HEBB thus p(z) satisfies the (en, Tp) m HEB with 2p e and Πp On on Xo n X, which yields that for all 2 0.
(xp(x) 2 []= - x Th > [1= x 2:
(110)
29

---

Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
Since &e is bounded, have that for all x, x' E Xc. there exists & 0 such that fo(x) So(x') 2 -tyllx x'1 Combined with the above inequality, it holds that
fo(x) + + (o(x(x)) 2 - [(((()) x/ (x) - xll 2 inf 2 - Eg5 ÇER+ lp
(111)
Up
Analyzing -cy separately under 7pp and ?p = 1 proves the result. When 7p 1, the result is obtained by solving the optimal ( through the first-order optimality condition. When ?pp 1, the optimal value is achieved at ( Ç=.. 0.
Lemma D.2. Given 2, E Xs S X with p(z,) = Cy, and that 24 an e-global solution to PP- on Ng, then
So(w))
inf =EX'nn.,
fo(x) S
(112)
Proof of Lemma D.2 Since my an e-global solution of (P on Xs, by definition we have that for all 2g n N.,,>
fo(zy) + mp(x,) fo(x) + <p(x)) + c.
(113)
Recall p(xry) = En, and p(x) S e, since E Xs n x Plugging these into the above inequality yields (122
Lemma D.3. Let N' S Rd be compact subanalytic with Xc n n # 0, and thus Xc n X. 0 for some e 2 0. Let [x,, r) denote the neighborhood of x with radius > 0.for some x: E Xc N. If there exists I E BB r) n n Xc such that p(á) S then there exists (I( E arg gig,, I| æl| such that ze (x(x)= E 1B(x, r) n X Nic.
Proof of Lemma D.3 As X. n Xo for e 2 O is closed and nonempty, there exists ze(x)= E arg min || x|I. Also since ă E B(x, r) n X, and p()) I c, thus ã E B( r) n X, n Nc. then
(x) æ11 = min =EXtnie
||
æ1 S || - - Sr
(114)
which implies that (xx E Bax, r), combined with (x) E X. O Xo proves the result.
Lemma D.4. Let Xg X' or Xs X' (B, Given Fee, Xs S X, which is also an (cb, c)-global solution
CP on
Xg. Suppose Xs O X. + 0 with 2 e' 2 O, and there exist bounded points in Xs O Xe, then for e,y specified in 109 in
Lemma D.I we have
fo( + pp(.))))))))))))))))))))))))(p S inf fo(Ø) + +x(x)) + by + cb + yE.
(115)
=EXs
Proof of Lemma
By the definition of (eb, global solution (CP) on Xs. we have
p(xe)) Se, and fo( S inf fo(x) + e6. =EX,NX
(116)
Therefore,
fo( + (p(()))) S inf fo(x) + cb 7 xEXinx
(117)
Recall that X's n &x * 0. Let X'e be a compact subanalytic set such that X n X'ss n Xe * 0, and X' n n * 0. The set X' exists because there exist bounded points in X's O Xe and X' respectively. For x E Xe n X, recall we define =a( E arg mine ||= æz|.. When X's X, =x(x)) E Xs; when X'- = X n BB(,, r), =x(x) E X's by Lemma D.3
Let at E arg min (x). Then infrex.nxs fo(x) can be further bounded by
fo(x) < inf *ER,nxs
inf nxxin ((0)) since z (x() E Xe n Xe n X's
fo(x)
since Xe n Xe n Xs C X. n's
<foldE) + >p(x()) tey
from Lemma D.I
inf fo(x) 7p(x) Ey.
since X O X' #
(118)
zEXss
30

---

Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
Plugging (18) into 117 yields
fo( + pp(xn)) - inf fo(x) + + Ey eb 7E.
(119)
zERy
The proof is complete.
Proof of Theorem 3.7 1) Given y > O, let By be a bounded e-global solution of PP-. on Xs, with Xs = X' or Xs- = B(y,, r) nxX then for a E Xs.
fu(z-) + pp(x,) - fo(x) + Tp(xx) + c.
(120)
Let xx E As nx2- denote bounded (0, e²) -llobal solution of (CP) on X'.. Then there exists a compact and subanalytic
set Xo such that 24, x" Xe and 2e n Xx- * 0. Let ze- (a) arg mingex,- || =x||. When 1) Xg X.
ze (xn) Xg Xe: when 2) Xs = B(x,, ze- (xz) E X' n X. according to Lemma D.3 Then by Lemma D.I.
given
r > 0, in both cases we have that
fo(2,) - \')(,)) -(())>>'((())))
- solze (xx)) 2 -Ey'
(121)
Because So(ze- fo(=e-(zn)) 2 fo(x"), 121 indicates that fo(zi)) + 1' p(p(a))) 2 fo(x²) - Gyt, Plugging = x= in 120 and combining with the above inequality, we obtain that
f0())) + xp())) <f0(=") + 76" +
since p(x") c
{fo(z)) + +/((xz)) + ex' + 7E" +e from [21
(122)
which further implies
(7 (1)(x) S Sey + YE +e. Define == p(xx)) then Ty E Xe, = fo E X p(xe,)) S Seg. The above inequality implies Ey 5 5.tt6-
(123)
Further,
9-7"
from Lemma D.2 we have
fo(x)) - inf zERyNX,
fo(x) Se.
(124)
Combining 123 and 124 proves that By is an (e, daprroappio global solution to CP) on X's with ey S Sy +e
7-2
mp-1 "
1 (1
Sp-1 my
mp up
When 1pp > 1, choosing 7' = 3.7 2e
Lr 7p
my
and S lod
n
Pr 2pp
mp (1
we further
7p
have that
S Ey + 76"
26
Op
2E
+
2c
S 8 + 2c
(125)
11p
1pp
Tp-1
which proves that the e-global solution of (PP
on X's with 7 2 2e
02
(1
1
and e S E
8v
(1
2mp
"p is an (c, + 2c*) 2c") -loobal solution to CCP on Xs..
7yp
When 7p = 1, from Lemma D.1 for 7 2 c. 0. Choosing 7 2 lply
have 6, Sc. Therefore, the e-global solution of (PP.) Xss is an (e, 2e" >-global solution to (CP) on Xs. The set Xss can be X' or ((I,, r) O X, which
corresponds to the global solution on X,, or the local solution in the neighborhood of Iy,, respectively.
2) Next we prove the converse. Define Fe,, to be a bounded (cs, c)-global solution to CCp on X's, and recall X, = fx E X
p(x) S e). Then by Lemma D.4| we have
fo(x.,)) + vp(()s)))
S inf fo(x)) + 7p(x)) + G. + cb + 7E
xEX's
< inf fo(x) + 7p(xx) +
(126)
xEXas
when Thp > 1, 7 = Opty when ?7p = 1. The set Xs can be X or (I,,, r) N. which corresponds to the global solution on X, or the local solution in the neighborhood of Fe,, respectively. The converse proved.
where the last inequality holds by choosing e < 8
37 <
3. and 7
eee:
(22 mp
31

---

Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
Lemma D.5. Ey E X an e-stationary solution PP and [V)((r))]| S E then it is also an ey-stationary solution to minaex p(z) with Exy sttr, Furthermore, for 0 2 1, let Co(x)) = 0(11,- (2,) + + In M) Then either one of the following two conditions holds.
Ce(()))) = and Bny an optimal solution, thus also a stationary solution to min V1,7 (x));
2) (x())) > 0, and any is an <x-stationary solution minnex (1,((x) with e/ "o,(
Proof of Lemma D.5 Since Bn E X is an e-stationary solution (PP, for a >> O, we have
1 |xy ( avp, sc.
(127)
By the definition that (y(x)) fo( + mp(z), further have that
2 Projx (21 ar (p(x,))))) ))Il
< F7 Projx (Vig aV (,,
-V - Proix(1, - -o>Vp(z
< 1 Projx (3g (x,))) (z,) - arvVp(z)))
= 1,, Projx((z, (x,)() + Vo,
(128)
Dividing both sides by a of the above inequality yields
|,, (roir - a c+ 7
(129)
an
which proves that 2, is an ---sttiionary solution to min p(z) with G = ett, (Z,) + T In M) for 2 1, we further have
By the definition that p(x,)
7
1
C+
|r Proix(e,- an Tn Vu,, (x,,)) ory
(130)
ca()))
where (x())) 2 This implies that either v1,- (x,)) T 7n M 0r, > 0, and
E+l (co(xy)
aryco (xn) | Prooi((e, orr,,,
(131)
The proof is complete.
Lemma D.6. Suppose Assumption 4 holds. Recall that vi,, (x) = arg min hir (z, y). For 1 E,2 O. have
362 3l + 6a -2
-
f.1 | - (z)11 < vi, (z) + M
|| - v1,
(132)
2
2(1 - (,,1)
Proof of Lemma D.6 By definition, U1,- = hu, (z, Vi,r (I)). and h4r (x, In M. Therefore,
1 ff11 ||-- (x)) (x) + T = h (z, yi, (x)) + hn x)
(133)
2
where the last inequality follows from the (1 - -sttong convexity of 11,- :), thus the quadratic growth. The first inequality 132) is proved.
For the second inequality in (12), we have
(0)
0t (x) + I (x, + h (x, 5
a y 2(1 - (5, | P ()))
(8)
1
2(1 -- 1-2 1 Projx(e aV, x))
vi (x) + Projx
(r,
32

---

Efficient First-Order Optimization on the Pareto Set for Multi-Ojjective Learning under Preference Guidance
(c) r.. + 60 | - vi,r(x) (2)11
(134)
3(1-44 2(1)
where (a) follows from the (1 - -sttong convexity of (z, thus the proximal-PL inequality, (b) follows from the optimality condition mingex hir, (Ir, y) at Vi, (ar), and (c) follows from the li,, . -smoothnsssss of hi (2; :), and the non-expansiveness of projection.
Corollary D.7. Lemma D.6 implies that, for I εG > 0, v1,(() achieves minimum value if and only if Vū, (x) = a.
Proof of Proposition 3.9 Since 2, is a local solution to PP.
stationary solution to (PP,) thus an e-stationary
solution to minzex v1,r by Lemma D.5
We then show the e-stationary solution of minzex V1rr is also an c'-optimal solution of min V1, under additional assumptions of F. By Lemma B.11 the directional derivative of Wir denoted as (x; - x)), can be computed by
M
11,r(1 - r) =
( -0) -
Σ
Tm (I,
vi)( (2 x))x)== 2 -e|lz - æll for all 2 E X. (135)
m=1
Plugging == Vi,r (2) into the above inequality yields
M
(1),, - x||? -ellE[, (o)) x/|.
(136)
Furthermore, let P(r) be the indicator function on X, by the optimality condition of h4. (z. :) at Vi.- (2t), we have
M
0
Tm (I, (i) -, +PP(,,,-
(137)
[A1; : Aui E A is a hyperparameter. Then R(y) is (1, 0)-poitt quasar convex at = Vi,r (x:) By the definition the subgradient of R(y), and the (1, -pointt quasar convexity, for all E X, we have
For analysis, we construct an auxiliary function R(y) = X F()) + P(y). where
M
M $
Am V fm + (z)) - vī.
Σ m=1
Am (fm(2) (x))
(138)
TTa
Letting Am = Tmm (xx, Vi,r (x)) given that x E X' is a stationary point of minzex (1), and plugging = vi,, (z)), [xx (x)) E DM Tm (2, Vi,- (z)) (x) aP (P(v,,(xx)) into the above inequality yield
Ux ((x-yi, vi. (x)) Ti (x, vi,- (x)) (m(()) (vi.t
(139)
Substituting = x into the above inequality, then /||x - vi, (x)112 < EM Te (x, vi, (x)) (mo))-fm((e (mi, (1))) which combined with (36) yields
M
mm (a, vi.r (x)) fm (x), fm(4)) -ellyt,r (x) x||
nea (I, vi (2) ()
M
Σ
Tm (x, vi.r (x)) (Vi (1:) - Sm(()) - ullvi, - xel2
(140)
1=11
where the last incquality holds since (x) are (1, 11) -trong point quasar convex for all m [M] at æ. The above inequality implies (x) x|| S
33

---

Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
Applying Lemma D.6 and letting a =()), have
m1, .1 + -2
3 h,, + 6a - || 1r-yit (t))
(x) + +r 1
è -0=(())
(141)
2(1 f,11)
2(1 1111
Then there exists 7 E (Kx,,)) that p(ā) = 2
D.3. Proof of Theorem 3.11: the e-stationary solutions relation
We first discuss the stationary condition of CPP when X' = RR, and the calmness condition that ensures the KKT condition
a necessary condition. Then we prove Theorem 3.11 general constrained problem below
the relation of e-stationary solutions to (P and CCP.
Consider a
min So(z) =Eav
s.t. H(x)
(142)
where fo 129 + R. and R2 + Rd with d, 1.
Definition D.8 (KKT condition of (42)
The KKT condition of (142) is
((x) O.
v fo(()) VH())== with w E Rd
(143)
leasibility
staionarity
Correspondingly, the (e', e)-KKT condition of (142
Vz))) Sé, [I(2)]| s. with E Rd.
(144)
Definition D.9 (Calmness (Clarke 1990 Definition 6.4.1)). Let x² be the global minimizer of (142). If there exist c, c. such that for any Rd with | S and any that I x=1 II S e which satisfies H(x) 0, one has
fo(x) fo(x*) + c|lu|| 2 0.
(145)
Then the problem 142 is said to calm with c.
Lemma D.10
Ye 2000 Theorem 3.6)). If the problem
142 is calm at global solution x², then satisfies the KKT
condition in Definition D.8
Below lemma show that if the objective is Lipschitz and the constraint satisfies error bound with exponent greater than one, then the calmness condition holds. Similar results have been discussed in Ye 2000 Proposition 4.2) with exponent equal one. This result connects error bound with the calmness condition, and thus the necessity of KKT condition.
Lemma D.11. Let x² be global minimizer of problem 142 For < 1, consider any E Rdd and ||||| < and any that || - x S e and H (z) + +u- = 0. Define I2 = Proix; xp (I), where Xi = {x E R (xx) 0}. If H(z) satisfies
an error bound that || [x) 2 2x11= || xpp th and fo is E Lipschhhit for all B(x", (c) with 1, then the calmness condition in Definition D.9 for problem (12) holds.
Proof of Lemma
D.11 By definition, for E B(x", ,)) with S 1,
c < ||||| = [H(x)] 2 eallx - -xpp-pp11' 1/
(146)
Since x² is global minimizer, and ||w|| S 1, for 7h S 1,
(a) fo(z) fo(x*) 2 fz) fo(op) 2 - -1,11z lz zpll 2
e/ 1
Es
th
||
(147)
@h
2h
where (a) holds because of the Lipschitt continuity of fo on bounded that includes x and Fg. Therefore, the calmness condition in Definition D.9 holds with c 4r.
Proposition D.12. Recall that p(x: (v), + M) with 0 > Vt. satisfies the (Coy (v))-K. inequality on
with ar > 1, then p satisfies the (Cp, ap) KL inequality on with ap 0-14 > 1, and cp = Cy
T0-1Jou41
34

---

Efficient First-Order Optimization on the Pareto Set for Multi-Ojjcctive Learning under Preference Guidance
Proof of Proposition D.12 For Ω and that v2,r (x) + M O, we have
[Vp(>)]] -0 (2) + M1 (2)]l
# 8-11 mm
20(c.) के (z), 7 In In 11 -(())) (p(x))
(148)
Rearranging the above inequality proves the result.
Theorem 3.11 requires the assumption of the f...-smos of Vut, a bounded set. Below provide sufficient condition, which shows that under additional assumptions of fm, E [M]. the sm..-mmos of Vvi, on bounded set Nc can be justified.
Lemma D.13 (Smoothness of Vtrr). Suppose Assumption 2 holds, and L + p. > O. Vf is 1122-mooth for all m E [M] on a bounded set Xc, and there exists x' E Nc that V2 fm for all m E [M] is bounded, then V0i, is 2..2-smooth on Nc, with f,, = 2 + (vt,,) +
+ lis 2 + bet.
Proof of Lemma D.13 With similar arguments as Lemma E.1 since Vm is fm.2-hoo for all m [M] on bounded
set Xc, and there exists x' E Xc that V (2')) for all m E M is bounded, therefore, there exists f, >> 0 such that for I E Nc, and for all m E [M. || fm (x))l || < E,,1-
Under Assumption and with + μ > O, first recall from 5 that Ver, (x) can be computed by
M
- Vzh(z, 1y=ut, (x)=
n (z. y) [m - 1(x - y) Im)
(149)
m=
Because of the twice continuous differentiability of Jm for m E [M]. ( exists and can be computed by
(x),,(()) = v2 h(x,)) - (z) h(x, y) (x)
(150)
For simplicity, simplify vī,- (1)) y" (xr), and (,, v) h( y) in the following derivations. Then / (1r) R [I')l can be bounded by |
( 22, h(,, h(x, - Mad (2
(v) Vy Mxx (z)))l
Vy V har (x')))
(151)
where Jj can be further bounded by
Jn < l (1 2'1 (z) (2(x')1) I l l 221 +
(,i )|[ - 2'1l
(152)
with l denoting the Lipschitz continuity of V2 122, 3) w.r.t. [x) v). Similarly, with Eney. denoting the Lipschitz continuity of 2 Vaz y) w.r.t [z; v]. Ja can be bounded by
J3 S Cyg, 2 (1 + lyg,, )l( x'1l-
(153)
And J2 can be bounded by
J2 1 x'
(154)
Therefore,
()), - V'r,, & (1nmn.2(1 + Evz..) ) + 2 + loi, 2 + + lge.)) || x'1l-
(155)
The derivation of byr, is discussed in Lemma B.8 We next discuss the derivation for Enay 1, Cn 2; Chap and lyz
35

---

Efficient First-Order Optimization on the Pareto Set for Multi-O/jective Learning under Preference Guidance
To compute vr.,..1 from implicit differentiation, Vii (1r) can be computed by
Vzi, - ", (x)))
(156)
Then Vv), Vi, (2')l can be bounded by
(x) Vyi.- (xx) S 2 (x)) Vigh ha' / (x))] [=])]]11
+ V by h(2', y² (z
h(x (z))
(z 1 y (x)) hy
h(2', 2 (x'))
21 + p)) + E (1 (1+10 14) 2 (1 + Ez | 2-1-
(157)
We then proceed to bound Enay.1"
M
V M y) Σ V nT (m +11
V2
1 v (v) (Z).))))) diag(T(z,)))) VF(x) -1g--
(158)
We have that
2 s ey + Ch.....
(159)
Furthermore, to bound En have
2 (,,,) Mar S (FFFF)---F -(inn(((rx,))))FFF[[))))
+ -
+ ) ( V/)
1 f + +l5flz) Me, (11x0 - x'll 11 v'll).
(160)
Enzy.2
To compute f,, recall that
V (2, = (FF
(161)
V (x, (lly
(162)
from which we have
max
< VMM, = lx.
(163)
Next we bound liex. 2, and En 2- The Hessian of h(2, y) can be computed by
M
- vF(v) (T(( ((I,,))((( VT diag(T(z,)))) VF(y) +
= va --
nm mm V2 + 11g.
(164)
m=1
Vinh(z,y)= 1 T (( ding(r(z.)))
Tm (z, 8) V2 22 fm(x) + +1l.
(165)
Then we have
2 byyh(z,)))
(2x v) Vi s/)ll 11'1l= (1
()) - diag(T(Z, (F))))
36

---

Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
- |V
+ +177:///f...00n0o.1111-o22222111 -FF)) vF(()I)
+ +
=(2',3
- (26 + +leflx) ME, + 2 V Mef,1x7
( I'1l
(1|x-
y v/1)) (166)
En yy.
With similar derivations the above, we have le.. .2
Ebgu. 2-
Collecting the results in 155
157
160
163
(166) completes the proof.
Proof of Theorem
3.17
Since x, is an e-stationary solution to PP. thus
[V.o(z,,) + > S.
(167)
By Lemma
D.5 it is also an -ystttiionary solution to minzeR= p(r)), and thus
[Vp(,z)]] S Et
(168)
7
By Lemma C.14 the KL condition implics that on (d X nddc)) Th S V[p(zy))] And since X n Xe is closed, the above implies that there exists x² E Ag n do such that
||,,, x dist (.y, X n Xc) S en Th Vp(2,, Th (0r c.) th = 0(e,t) ).
(169)
Taking Taylor expansion of Vp(r)) at and by the 6p.2 sm.ossmos of Vp(x) on Xc, we have [Vp(z,)
V2p(z") (o("i,)))"Pp(<"(00))
xx =\Vp(zz) Vp(x') v²p(="))(s (20, - x=)]
2
<lp.2 - x²1 I ( (G) 0(e,7 7h
(170)
Plugging the above inequality into 167 we have
(fo(z=)+>V>pp +>0++ x²)] Se E 72.2 en) 0(e + -²=
(171)
Letting w = >>(x x²), then || 0 1 ) < 0(1) is bounded since T/ I 1. We can further bound // [x(x,) + V (il(1,)wll by
[V/5o(z)) \u Vlf(( V>p==>>'(=//ll)) \
v²p(=")lllux) -V V>pz=")>''uu 1p.27 x2
+ + 276. (.) _ेत = + - th
(172)
Recall that 7)6 < 1, thus choosing 7 1) and < Ly, we have ey S 6, and ()( + (pl(x,)wll S e + 8, which
proves the result. In this case, since we require
Up 1
1 12 1hh
(173)
Op
Op
which implics a₂ 2 2, and thus 8-1+ 2 2 from Proposition D.12 implying < 2.
Remark D.14. Note that, the HEB and KL exponents may not be unique (c.f. Appendix C.2) In such cases, there may exist < 1/p + - And the above theorem still requires ym- = Ih S 1, thus Op 2 1/p we further have that p(x) is ag
smooth around x², then the smoothness implies πlp 2 2 2 app. combining which with a, 2 7pp, implies that we require a, = ?/p = 2. This condition can be relaxed, or the exponent can take a wider range if the local Lipschitz continuity fo is replaced by the Hölder continuity with larger exponent as in (Ye et al. 1997 Definition 2.8). We leave a detailed discussion to future work.
37

---

Efficient First-Order Optimization on the Pareto Set for Multi-Ojjective Learning under Preference Guidance
E. Proof of convergence of algorithms
In this section, we prove the convergence of the proposed algorithms with a specific instantiation of 0 1, thus p(æ) (1,((z) in M. For convenience, we define (9 (z. y) == fo(z)) -2,,,=(2,))
The details of other oracles including Nesterov's acceleration and Adam updates are given below.
Nesterov's acceleration. Define U(w, Aw; ar, () = (roix((e+1 + 5(v++1 uz)), where u++1 = or aw and à is the lookahead coefficient.
Adam updates. Define U(w, Aw; a,t) t) = Projx( a th Vo++e where m, = 31m--1 + (1 Aw) denotes the moving average of gradients, V2 -2 + (1 (21-32)(Aan) (Aw2)) denotes moving average of squared gradients, mz 1- bias-corrected first moment, é 1- is bias-corrected second moment, with $1, E (0, 1), is the small error.
m²
In our convergence analysis, we the PGD algorithm as oracle.
E.1. Auxiliary lemmas
We first present the auxiliary lemmas to prove the convergence of the algorithms.
Assumption (Smoothness of functions). For all m E (O...., M). fm is ff.1-smooth on X.
Assumption 5. The sequence } generated by Algorithm is bounded on the trajectory.
The above assumption combined with Lemma B.1 implies that (Sm (x+)): m O,..., M are e-Liischiizz on the trajectory. 4 holds. Given bounded Xc C X such that ||œ||| ey for all Xc, if there exists x' E Xe that || V fm((')) (a')ll εt. and ff((')) < Eg for all m 0, . M. Then fm (x) is bounded and E Lippschitz continuous for all x E Ne with y = E ,
Lemma F.1. Suppose Assumption
Proof of Lemma E.1
We first prove that fm is l Lipischhitz continuous on Nc. For all x E Xc, it holds that
(m)]l <
V (z) fmm + +lallz x'll s 28
(174)
Then we can further bound [xm( by
(x)l < (x') + (f (x')) Eg
1zllz 1-l1a=>> - 2'1 S 2 + 20
(175)
The above holds for all 0, ..... M, the proof is complete.
Lemma E.2 (Smoothness of hi,r and v1,)), Under the same settings as Lemma E.1 then hi, (2, 8) is Ene 1-moohh on Xe
eyex et And (x) is Ce,,..1-mmool Xo with l l + lui.))
W.E.t. both and y with f = 1 + f.1 + 2e
Proof of Lemma
E.2 The gradient of hı. v) w.r.t. x can be computed by
V V=h1,-(2,0
Σ
Tmm (m (a. 1(x v).
(176)
Given x, x E X, we can bound Vah4,r (x, y) (x', by
1ihht (x. y) (al,, (1))
M
</Il z'll +
Tea (x, (
vf
12m v) (m v)]l fmm('))
M Σ
</Il
2'll + f 1| x' +
(2, v) Fm (a'.))l
(177)
38

---

Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
where we bound |T (1; 1) Tm (a' w)|l by
[m(v) (m(e
I' finta2
Tm (x, v) - mm (2'
Σ m=1
imiui- fmm
Σ m==
I'm Imilot)
Im(r) Jmii)
I' (x) !m(x'
(m) fm(tl)
fm (s) Jm (m
m=
M
Im (
2m=1 (m
2m==
m==1
M
(m( I' (mm)
Imlv)-/m(tt fmاtt)
L || - 22'l
Smily) [m()e
2m=1
M
Am(u) (m(a)
|| x''l
(178)
Σ ===
[miss]
im(vi smiel
Em
(mfr)) Smiled
where é is on the line segment of x and x'. Taking Em=1 of the above inequality yields
Tm (2i, y)
Fm (m (x',
m=]
fm (m()))
-1 2'11 +
m==
M
fm(
Fm) Imly) Smil
Ej 1| x'll
Σ m= e.
/m(l)-/m(o)
===1=
M
fg Ef 2e 11100 z'1l
(179)
where the last inequality uses the fact that Ilf - - fm(())l S Eglz. Combining the above arguments yields
| 1V, V w)ll Slm,., || - x'
(180)
with - pz.1 + 2e 4t e
Similarly, given x. U. 1/ E X, we can bound (1, Vhy,- (x, !ll by
V (I, 3) V 1zh4, (I, 3/ )l S ne. 3/1 V (x, - V , (I, 3/)) <bn,, 11y - s/ ||-
(181)
(182)
The gradient of (r) can be computed by
M
Vn,r (x)
Σ
Tm (z, vī, (z)) 1(x (x))
(183)
Given n, x' E X. we can bound V11,, (x) (x))(='))1 by
[v) - Vui,- S lnc... (Ilo - x'll + l1 (x) - ( S Cn.... (1 + Cor, )|( - x'11. (184)
The proof is complete.
Lemma E.3 (Smoothness of the penalized function). Suppose Assumptions 4 5 hold. Then fh is p 1- smooth w.E. f. + y
and y on the trajectory, with E
Proof of Lemma E.3 Given x, U. y X, can bound the difference V (2 V V sn (2',v)l by
(V.9 V2 vl1l < Vo((')) + V// (2. (2. (4',
< + 2'1.
(185)
Similarly, we bound the difference
| Vy (.,
(x, by
I [V (09/a, V (z) -/u v'll S 7lm,...lly v'1l.
(186)
The proof is complete.
39

---

Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
Lemma E.4 (Contraction of (t.k). Suppose Assumptions 4
hold, and & 2
Why O. Recall that fi,((1) =
arg min, M,, y). The sequence ( k=1 produced by Algorithm Satiisies
I| yi, (1:)11 - (1 Ph. -,,, Bex))lek -i, (x+)]1
(187)
Proof of Lemma E.4 Recall that the update of 1/t, in 13a takes the projected gradient descent (PGD) on (1, v). By Corollary B.4. for I m|M Mmn 2 Mhv 0, the function (2, y) is yh, -strongly convex w.r.t y-
Leveraging the convergence result of PGD on strongly convex functions, we have
Ilve Vi. (2))1 - (1 ph, Bex))lu, (x:))1
(188)
The proof is complete.
Corollary E.5. Suppose Assumptions 4 hold, and f,, 2 ph.
Recall that yi,r (z) arg ht, (x,y), y). The
sequence (yr, h==1 produced by Algoritim satisfies
K-1
11 Vi. (xx))1
<
II (1 un,
B.x))lll vi, (sr)))?
(189)
Proof of Corollary E.S
The result directly follows from the update of ye, in 13a. and by applying Lemma E.4 iteratively
from
E.2. Convergence of the meta algorithm
Theorem E.6 (Convergence of Algorithm with projected gradient descent). Suppose Assumptions 4 and 5 hold. The sequence (vt, Yizo produced by Algorithm with aa a = θ()), Br = 3 = 01)) 7t = O + (). Ke 0 + satisfies
T T
Projx P a Ver (t))l =
(190)
af
Proof of Theorem F.6 We first prove (190), the convergence of the penalty reformulation PP outer-loop iteration, Algorithm dooes the following update
Recall that at each
Ø1+1 = Projx (xx arl (V(((()))) 7 V Ve, Mt+1)))
(191)
where V1+11 Vt,K approximates (2:) with sufficiently large K based on Corollary E.5 for all & = 0, O....,KK K - 1, it then follows that ...,,
Choosing 3r,1 = Br S 1/Kh,
|| (x.)(= llv.K vī,- (x:))1 < (1 Hb, B.)
xk
Ilv,, (2:))
(192)
Let 1, denote the smoothness constant for fo(x) reh1, y). Define the Lyapumov function V, to be
V, = fo(x;) - he, - (Fe: Me+1).
(193)
Applying the convergence of PGD for general nonconvex smooth objective yields
V < (o)()))) - 7 Vhy,- V+41), - xz) + l |1141 - xell?
(194)
By the property of projection, and the update of we further have
(o(o)))) 7o Vhe (Xe, Dt- 11, Be41 Iz) 5 1 6--12241 - Fzel
(195)
40

---

Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
Since ot & fh,,, plugging the above inequality back into (994 and rearranging yield
V+1 V1 S
1 - 21
(196)
2ay
Recall from 191 and (192) that 24+1 is an approximation to Projx (3t ar V (ri) Projx (V
Tt V wh,, (oe, Vi, (z+)))), since yc+1 is an approximation yf, (2x). Therefore, the term 1 Projxx (zI- Vir (21)) 1 can be further decomposed as
52 Projx 04 Ver (x))) 1|0- Projx (x oz V (1)))))
< 21 Projx (z: (o((((( - V Vahi, (xe. b++))))
V - V2h Vi, (x)))
<2 ct 1 112 + +2722 he.r, |1 vi, (1:))1
<2 r x1+1 2- + 2 1
1, y.
(197)
where 222 = (1 phy 3.) ||ve,0 Vi, (2:))12
Plugging 197) into 196 and rearranging, we have
|| |r Projx (xt or Ver (x)))l 22| - 2++1 27/ 22 hi.,1 1.y yut
2
<4a,(V, V + 27² R2
1 1..1 413
(198)
hr..
Taking telescoping sum of the above inequality, and choosing a = a = ((), 3 = B = 7 = 0(1 + t).
K, O(1 + t) prove the result.
F. Implementation details and additional experiments
In this section, we report the additional implementation details and additional experimental results and discussion omitted from the main text.
Computation. All experiments were conducted on a server with an Intel 19-7920X CPU, and one NVIDIA A5000 GPU. Some experiments require CPU only.
For all the experiments reported in the main except for the multi-lingual speech recognition experiment, exactly follow the settings from (Mahapatra & Rajan 2020p. For the multi-lingual speech recognition experiment, follow the settings from (Chen et al. 2024a).. The implementations of the baselines including LS, PMTL, and EPO are from the official code of the EPO Mahapatra & Rajan 2020) and that of FERERO (Chen et al., 2024a) is from its official code with their default hyperparameters. The results of XWC-MGDA are directly referenced from the paper.
Synthetic data. For the results in both Figure 4 and Figure the model parameter æ has dimension q = 20, the number of objectives is M = 2. The angles between the preference vectors and the horizontal axis are generated between [ ग, 20 m] with equal angular distance. The optimization methods are all deterministic in this experiment. We use the default parameters for all baseline methods. For the FOOPS method,
9
hyperparameters 0 1,7 1, 0.01. The penalty parameter O'e min(0.03 0.01t, 1.5). The inner-loop parameters are K 100, 3 0.1.
Table 7. Summary of hyper-parameters for the synthetic data experiments in Figure 6
Hyperparameters
LS
MGDA
PMTL
EPO
FERERO
FOOPS (ours)
step size a₁ max iterations
0.1
0.2
0.2
0.1
0.05
0.2
150
150
150
100
100
100
In Figure 6 we include additional results from LS and MGDA for comparison. For all preferences and all methods, the initial model parameter Ze is randomly generated from a Gaussian distribution (0, 1) for each dimension. In Table 7 we provide a summary of the hyperparameters for the baselines and our methods for the experiments in Figure

---

Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
02
62
(a) LS
(b) MGDA
(C) PMTL
(d) EPO
(e) FERERO
(1) FOOPS
Figure 6. Converging solutions (bluc dots) and optimization trajectories (blue lines) the objective space of different methods synthetic objectives given in 12a Dashed black arrows represent pre-specified preference vectors. The green dots represent initial objective values.
0.0
0.6
0.4
6.4
Initial valuss
P3ZEL
FEREROO
045
(a) PMTL
(b) EPO
FERERO (4 I)
(d) FOOPS
-4
0.5
0.5
66
0..
Eiitii valuos
*
RPO
FERERO outpot
0.2
cutgra
00
16.1
(c) PMTL
(f) EPO
FERERO (A
(h) FOOPS
Figure 7. Extension of Figure Outputs (colored markers) and optimization trajectories (colored lines) of different methods when initial objectives are near the Pareto front. Different colors represent different preferences. For FERERO, represents choosing the partial order cone CA R.M therein for vector optimization, which corresponds Pareto dominance.
Figure is an extension of Figure under the same experiment objectives but with additional results from EPO and by different initializations. In Figures 7a 7 the initial model parameters are randomly generated from a uniform distribution between [-0.3, 0.3] for each dimension. While Figures 4a
4c and Figures 7 7h the initial model parameters are randomly generated from a uniform distribution between [-0.5, 0.15 or 10.15, 0.5) for each dimension. Table 8 summarizes the method is more robust to initializations
hyperparameters for the experiments in Figure Compared other baselines,
and requires the least number of iterations for the hard initialization in Figures 7c 7h
Table Summary hyper parameters for synthetic data experiments Figure
Hyperparameters
Figures 7a 7d
Figures 7c 7h
PMTL
EPO
FERERO
FOOPS
PMTL
EPO
FERERO
FOOPS
step size a, max iterations
0.25
0.10
0.60
0.20
0.50
0.20
0.60
0.20
100
60
10
100
200
120
200
100
Multi-patch image classification. For a fair comparison, we follow the same data splitting and processing procedures (Mahapatra & Rajan 2020). In each of the three datasets, there 120k samples for training and 20k samples for testing. There are two tasks each dataset: 1) classifying the top-left image, and 2) classifying the bottom-right image. For all methods, we use the SGD optimizer with batch size 256. The step sizes for updating the model parameters of all methods are 30 The number epochs for methods are 100. The parameters for other methods are chosen as default. For the FOOPS method, we use hyperparameters = 1, = 0.6, = 0.01. The penalty parameter 7/ is set initially to 0.1 and increased by 0.1 after every 10 epochs until reaches The inner-loop parameters are K 5, 10-3.
42

---

Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance
We the Pymoo 0.6.1 library compute the hypervolume. The Nadir points for the hypervolume computation are given in Table For a fair comparison, the Nadir points we use the same with (Momma et al. 2022 Chen al. 2024a
Table 9. Nadir points for the hypervolume computation
Datasel and metrics
Nadir points, metrics on objective [1,.... M]
Multi-MNIST loss
[0.500, 0,450]
Multi-Fashion loss
[0.840, 0.800]
Multi-F+M loss
[0.625, 0.575]
MoIti-MNIST accuracy
[0.830, 0.848]
Malti-Fashhon accuracy
[0.680, 0.710]
Multi-F+M accuracy
[0.790, 0.785]
Table 10. Hypervolumes t (x10-3) in multi multi-patch image classification of different methods including PNG and PB-PDO
Datasets
LS
PMTL
EPO
XM
PB-PDO
PNG
FERERO
FOOPS
Mt-M loss
1.68
1.41
1.35
1.42
1.89
1.93
1.95 + 0.21
2.62 = 0.21
Mt-F loss
6.75
5.90
6.02
6.77
7.82
7.79
7.76
Mt-F+M loss
3.63
3.03
3.76
3.89
3.77
3.85
3.22
4.80 0.45
Mt-M accuracy
0.19
0.15
0.15
0.16
0.23
0.25
0.05
0.33 + 0.02
Mt-F accuracy
0.99
0.87
0.87
0.99
1.16
1.15
1.17
1.22 0.07
Mt-F+M accuracy
0.48
0.40
0.50
0.52
0.51
0.56
0.53
0.72 + 0.06
Ablation studies. In the multi-patch image classification problem, we further conduct ablation studies to test the sensitivity of hypervolumes (HV) for the proposed FOOPS algorithm under different hyperparameters 7 and I. Results are plotted in Figure Seuure&belood below. They show that choosing T or to be too large or too small could degrade the performance. Nevertheless, the performances of FOOPS under suboptimal choice of the hyperparameters are still better than the baselines.
Loss vs (r= 0.01)
Accumay vs (T= 0.01)
Loss vs (1 0.6)
Accurncy vs t (f = 0.6)
MI-M Laner
1.2
Mr-I Loss
Mt P0 Locs
1.0
Accuracy
0.0
Mt M Loss
Mr
ML-M Accunay
3-
Mb- Acturacy
2
0.2
MM- hccuracy
0.4
0.2
0.A
0.8
02
3.4
0.5
1.0
10
10
10
(a) Loss HV vs.
(b) Accuracy HV
(c) Loss HV vs. T
(d) Accuracy HV vs. T
Figure& 8. Ablation studies for multi patch image classification on / and
Multi-lingual speech recognition. We follow the same experiment settings in (Chen et al. 2024a). We use two datasets, Librispeech and AISHELL v1. Librispeech is an English speech dataset that consists of 960 hours of labeled audio data. For our experiments, we use 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 v1 dataset for both self-supervised and supervised training. We combine these two datasets for our multi-lingual speech recognition experiments.
We use the conformer (Gulati et al. 2020 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 total number of parameters is around 64.5M with 58, 58.4M encoder layer parameters and the rest being the classification layer parameters.
43

---

Efficient First-Order Optimization on the Pareto Set for Multi-Ojecctive Learning under Preference Guidance
The loss functions use include the Contrastive Predictive Coding (CPC) loss, and the Connectionist Temporal Classifica- tion (CTC) loss. The CPC loss (Oord et al. 2018) is self-supervised loss to learn robust representations from unlabeled speech data. The CPC loss is designed to maximize the probability of future sample given contextual representation generated from the current speech sequence. The CTC loss is defined as the negative lig-liiei of the model parameter given the input sequence and the label sequence.
For all methods including the baselines, we use the step sizes 0r,1 5 x 10 for training the backbone conformer parameters and 2,2 x 10-5 for training the classification head parameters.
Comparison run time and memory cost. In Table 11 we summarize the average run time and number of iterations or epochs of different methods different datasets. The results show that FOOPS generally requires shorter time than FERERO, but longer time than LS. Furthermore, summarize the memory cost in Table 12 It shows slightly higher memory cost than LS or FERERO on smaller-scale experiments. This is because although FOOPS does not compute M gradients per-iteration while FERERO does, which saves some memory, FOOPS requires storing the model parameters for both x and y while FERERO does not, which introduces extra memory cost. We leave it for future work to further reduce the memory cost and improve the efficiency of the algorithms.
Table Summary of average run time seconds (s), minutes (m), hours (h) number of iterations epochs different methods on difforent datasets.
Datasets
Metrics
LS
PMTL
EPO
FERERO
FOOPS
Synthetic, Figures 3(--c)
Iterations
100
100
Per-iteration run time
3.50E-4s
7.67E-4s
4.93E-3s
7.50E-4s
7.61E-4s
Total run time
0.035s
0.0767s
0.296s
0.0075s
0.0761s
Synthetic, Figures 3(d-1)
Iterations
100
200
80
200
100
Per-iteration run time
3.10E-4s
7.65E-4s
4.93E-3s
7.30E-4s
7.43E-4s
Total run time
0.031s
0.153s
0.394s
0.146s
0.074s
Multi MuliiMMNiST/FFashiooofftt
Epochs
100
100
100
100
100
Per-epoch time
3.54s
11.88s
9.66s
7.02s
6.89s
Total run time
5.9m
19.8m
11.7m
11.5m
Multi-lingual ASR
Finetuning time
4.2 h
13.5 h
12.7 h
Table 12, Summary of memory consumption and running time of different methods on different datasets. "M" short for "Megabytes", "O" is short for "Gigabytes".
Datasets
Metrics
LS
PMTL
EPO
FERERO
FOOPS
GPU memory (LeNet)
1356 M
1378 M
1358 M
1380 M
1395 M
Multi-M/F/F+M
GPU memory (ResNet18)
1738 M
2386 M
2060 M
2196 M
2224 M
Multi-lingual ASR
GPU memory
38 G
40 G
40 G
44


Reviews:
[{"review_id": "ekWmgrNfiD", "reviewer": "Reviewer_XkmK", "summary": "This paper proposes a new method for solving the semivector bilevel optimization problem. The authors first reformulate the multi-objective subproblem as a single objective constraint and then use a penalty-based method to solve the reformulated optimization problem. The results demonstrate the effectiveness of the proposed method in finding preference-guided optimal solutions to the multi-objective problem.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for supporting our work, acknowledging that **we propose a new efficient method to solve a very challenging semivectorial bilevel optimization problem,  with a strong theoretical guarantee, and with intuitive experimental result demonstrating the authors' claims**.\n\nWe address your other comments below. The link to the additional results is \nhttps://anonymous.4open.science/r/FOOPS-F746/ICML3045_rebuttal.pdf\n\n>1.Lacking analysis on computational cost. Provide the order of computational cost and memory cost per iteration, and the real running time for each method.\n\nThanks for the suggestion. In Appendix F, Table 10, we have provided the real running time for each method. We add the memory cost per-iteration in Table A in the link.\n\n>2.In Appendix A, the authors discuss several works on bi-level optimization (BLO). I suggest they also provide a discussion on multi-objective bi-level optimization (MOBLO) problems, as explored in [1-5]...\n\nThanks for the suggestion. We will incorporate these works in our paper.\n\n>3.Typo: consistency of the punctuation at the end of the formulas.\n\nThanks for the suggestion. We will check to ensure the consistency of the punctuation.\n\n>4.The experiment on the multi-patch image classification problem (using Multi-Fashion+MNIST) is relatively simple and may not fully demonstrate the capabilities of the proposed method. Could the authors conduct experiments on more challenging and widely used datasets, such as Office-31 or Office-Home?\n\nWe have included the experiment for larger models in our paper for speech recognition; see e.g., Table 4 in Section 6. The model size is around 64.5M, much larger than the image classification problem. More details are provided in Appendix F. The benchmarks Office-31 and Office-Home suggested by the reviewer are designed for multi-task learning, but not for preference-guided multi-objective learning studied in this paper, thus not very suitable for our problem. To do such experiments, we need to first define a preference objective $f_0$, then conduct the experiments using our method. We will include the results in the revision.\n\n>5.It seems the number of objectives in the LL subproblem is small in the experiments. Could the authors conduct experiments on more challenging settings, $M>20$?\n\nTheoretically, our method can be used for a larger $M$ without significantly increasing complexity. We test this on a toy problem with $M=25$ and report the running time till convergence in Table A in the linked PDF, the last row, which shows the run time can be much shorter compared to FERERO. The problem is defined as\n$f_m(x) = (x - m)^2, m\\in [M]$, $H(x) = f_1(x) - f_2(x)$, and $f_0(x) = ||H(x)||^2$. $x$ is initialized to be $100$. We will find some other real-world problems with more objectives and include the experiments in the revised paper.\n\n---\nWe hope the concerns are addressed and the reviewer can continue to support our paper. Thanks!", "claims_and_evidence": "I think all the claims have been well supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "I think the proposed methods are well-evaluated.", "theoretical_claims": "I have checked the proof.", "experimental_designs_or_analyses": "I have checked the experimental designs.", "relation_to_broader_scientific_literature": "The key contribution of this paper is proposing a new method for solving the challenging semivector bilevel optimization problem.", "essential_references_not_discussed": "I think the author should discuss some related work. (See Comments 2)", "other_strengths_and_weaknesses": "Strengths:\n1. I think this paper is clearly written and easy to understand.\n2. The solved semivector bilevel optimization is very challenging. This paper proposes an efficient method to solve it with a strong theoretical guarantee.\n3. The experimental result is intuitive and demonstrates the authors' claims.", "other_comments_or_suggestions": "1. Lacking analysis on computational cost. The authors should provide the order of computational cost and memory cost per iteration, and provide the table of real running time for each method.\n2. In Appendix A, the authors discuss several works on bi-level optimization (BLO). However, I suggest they also provide a discussion on multi-objective bi-level optimization (MOBLO) problems, as explored in [1-5]. The key difference between semivector bi-level optimization and multi-objective bi-level optimization is that the former involves solving multiple objectives at the lower level, making it significantly more challenging. \n3. Typo: The author should pay attention to the consistency of the punctuation at the end of the formulas; some formulas end with a period, while others do not.\n4. The experiment on the multi-patch image classification problem (using Multi-Fashion+MNIST) is relatively simple and may not fully demonstrate the capabilities of the proposed method. Could the authors conduct experiments on more challenging and widely used datasets, such as Office-31 or Office-Home?\n5. It seems the number of objectives in the LL subproblem is small in the experiments. Could the authors conduct experiments on more challenging settings, $M>20$ ?\n\n\n\n\n[1] Gu et al. Min-max multi-objective bilevel optimization with applications in robust machine learning. ICLR, 2023.\n\n[2] Ye et al. AFirst-Order Multi-Gradient Algorithm for Multi-Objective Bi-Level Optimization, ECAI 2024.\n\n[3] Ye et al. Multi-Objective Meta-Learning, AIJ 2024.\n\n[4] Yang et al. Gradient-based algorithms for multi-objective bi-level optimization, Science China Mathematics, 2024\n\n[5] Fernando et al. Mitigating gradient bias in multi-objective learning: A provably convergent approach. ICLR, 2023.", "questions_for_authors": "No other questions.", "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": "jEOJ6BqrHl", "reviewer": "Reviewer_3nrf", "summary": "In this work, the authors frame preference-guided multi-objective learning as an optimization problem on the Pareto set and propose a first-order penalty method to address it, where the penalty function is a polynomial of a smoothed merit function. They begin by establishing key properties of the merit function, including its connection to weak Pareto optimality and the Hölderian error bound. Next, they examine the relationship between solutions of the penalty reformulation and those of the original problem. Finally, they present algorithms for solving the penalty problem and analyze their convergence guarantees.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for acknowledging that we consider BLO with *non-convex vector-valued lower-level objective* with stronger guarantees, which is different from prior works, and the experiment results are promising.\n\nWe would like to emphasize that the *non-convex vector-valued lower-level objective* is much more challenging and nontrivial, as also pointed out by Reviewer XkmK. \n\nBelow we address all your concerns. The link to additional results is \nhttps://anonymous.4open.science/r/FOOPS-F746/ICML3045_rebuttal.pdf\n\n>**Claims:** How to incorporate Preference Guidance...\n\nThis might be a misunderstanding. In our paper, the preference guidance was not replaced with another objective from $F$, but was enforced via a new upper-level preference objective $f_0$.\n\nOur experiments include the preference vector guided problems with $f_0(x) = ||H(x)||^2$, and $H(x)=0$ describing the preference vector; see Section 6. See also the response to **Reviewer SqKr-Claims**. We will clarify this.\n\n>**Broader Literature:** ...scale up to applications in larger models.\n\nWe have experiments for larger models for speech recognition. See Section 6, Table 4. The model size is around 64.5M, with more details provided in Appendix F.\n\n>**Methods&Evaluation:** Relationship between (1) and CP.\n\nIn our paper, below Eq. (CP), we have discussed that as $l,\\tau \\downarrow 0$, (1) and (CP) are equivalent. For $\\tau \\downarrow 0, l>0$, (1) and (CP) are equivalent under conditions in Proposition 3.2-2-b). Moreover, by Proposition 3.2, the approximate solutions to (CP) with $v_{l,\\tau}(x) + \\tau \\ln M \\leq \\epsilon$ are $\\epsilon'$-weak Pareto optimal. Therefore, an $\\epsilon$-global/local solution $x$ to (CP) satisfies that it is global/local $\\epsilon'$-weakly Pareto optimal, and that $f_0(x)\\leq f_0(x^*)$, with $x^*$ being the global/local solution to (1). We will add this discussion in the modified paper.\n\n>**Theoretical Claims:** In Proposition 3.2, $\\epsilon=\\tau\\ln M$,... choose $\\tau$ as a function of $M$...?\n\nYes. In our experiments, $M$ is fixed for a problem, and $\\tau$ is chosen according to $M$, so we can ensure $\\epsilon$ to be sufficiently small.\n\n>**Experimental Designs/Analyses:** ...Compare with methods listed in Table 2.\n\nIt is hard to compare with the methods since they do not provide open-source code. Furthermore, these methods require different assumptions that cannot be satisfied in our case. For example, for the lower-level objective, PMM and TAWT require strong convexity or invertible Hessian, which does not hold in our problems. So these methods cannot be applied.\n\nAs per the reviewer's request, we implement PB-PDO and PNG. Figure A and Table B in the linked PDF summarize the results, which show they sometimes cannot converge to the Pareto front, and they achieve worse hypervolumes compared to FOOPS.\n\n>W1.How should $\\tau$ and $l$ be chosen theoretically and in practice?\n\nAs discussed in Section 3.1, theoretically, smaller $\\tau$ approximates $\\bar{u}$ better, but also increases the smoothness constant. We need to choose $l \\geq \\ell_{f,1}$ to ensure $\\nabla v_{l,\\tau}$ exists and can be computed. In practice, we choose relatively smaller $\\tau$ and $l$ but not smaller such that $v_{l,\\tau}$ is not differentiable. Detailed choices are provided in Appendix F.\n\n>W2.Thm 3.6, 3.7, and 3.9 appear to be direct adaptations from (Shen, 2023)...\n\nWe respectively disagree. The theorems compared to (Shen, 2023) are not minor. In (Shen, 2023), the focus is on a scalar lower-level objective satisfying the QG condition (a special case of HEB with $\\eta=2$). Directly applying the results from (Shen, 2023) is impossible as we can only make assumptions on objective $F$, but not on $v_{l,\\tau}$, and $v_{l,\\tau}$ does not satisfy this condition even if $F$ satisfies. In comparison, our theories require much weaker assumptions, as discussed in Appendix A.1, lines 749-756. In addition, (Shen, 2023) assumes the QG holds on the entire domain. However, the exponential function in our case is not globally subanalytic on the whole domain (Remark C.9). Instead, we can prove that $v_{l,\\tau}$ is globally subanalytic on any bounded subanalytic set given that the objective $F$ is subanalytic. Thus, the HEB holds on the bounded subanalytic set, which is the base of the proof for Thm 3.6, 3.7, and 3.9.\n\n>W3.Convergence analysis is relatively trivial...\n\nWe respectively disagree. Our main contribution is to **convert the challenging semivectorial bilevel optimization problem to a simpler penalty problem** with guarantees on their relations, and easy-to-evaluate gradients for the penalty problem. Building upon this,  the convergence of the penalty problem can be analyzed using existing tools.\n\nBy converting challenging problems to simpler ones, we have a simple convergence analysis. This actually shows the *strength rather than weakness* of our method.\n\n---\nWe hope the concerns are addressed and the reviewer can reconsider the rating of our paper. Thanks!", "claims_and_evidence": "I find it unclear how the authors incorporate Preference Guidance in this paper. If Preference Guidance were replaced with another objective function, the overall formulation would remain largely unchanged, raising questions about its specific role and impact.", "methods_and_evaluation_criteria": "I believe there is still a missing component in the problem reformulation. The authors only establish the connection between CP and PP, but it would be helpful if they could also provide insights into the relationship between (1) and CP.", "theoretical_claims": "In Proposition 3.2, where $\\epsilon = \\tau \\ln M$, $\\epsilon$ can become quite large as $M$ increases. Would it be better to choose $\\tau$ as a function of $M$ rather than a constant, ensuring that $\\epsilon$ remains sufficiently small?", "experimental_designs_or_analyses": "The baselines used in the experimental section are incomplete. I suggest that the authors compare their algorithms with those listed in Table 2 for a more comprehensive evaluation.", "relation_to_broader_scientific_literature": "The experimental results appear promising. After incorporating comparisons with additional baselines, it would be beneficial to scale up the approach and explore its potential applications in larger models.", "essential_references_not_discussed": "I did not find any essential references that are missing.", "other_strengths_and_weaknesses": "Strengths:\n\n1. This paper improves the theoretical results of optimization on the Pareto set by removing the strong convexity assumption in (Roy, 2023) and provides stronger convergence guarantees compared to (Ye, 2022).\n2. The applications of this type of optimization problem are broad. The paper presents an algorithm to solve such problems, which has the potential to be scaled up to some large-scale applications.\n\nWeaknesses:\n\n1. How should $\\tau$ and $l$ be chosen both theoretically and in practice for the merit function?\n2. Theorem 3.6, 3.7, and 3.9 appear to be direct adaptations from (Shen, 2023) with only minor modifications.\n3. The convergence analysis is relatively trivial, as it primarily leverages results from well-known optimization algorithms.\n\nReferences:\n\n[1] Roy, A., So, G., and Ma, Y.-A. Optimization on Pareto sets: On a theory of multi-objective optimization. arXiv preprint arXiv:2308.02145, 2023.\n\n[2] Ye, M. and Liu, Q. Pareto navigation gradient descent: a first-order algorithm for optimization in Pareto set. In Uncertainty in Artificial Intelligence, pp. 2246–2255, 2022.\n\n[3] Shen, H., Xiao, Q., and Chen, T. On penalty-based bilevel gradient descent method. arXiv preprint arXiv:2302.05185, 2023.", "other_comments_or_suggestions": "No", "questions_for_authors": "See Theoretical Claims, Experimental Designs Or Analyses, and Other Strengths And Weaknesses.", "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": "NQ74KH0bxF", "reviewer": "Reviewer_7wXS", "summary": "This paper studies multi-objective optimization with user-specified preferences. The authors formulate the problem as a bilevel optimization problem, where the upper-level is a preference function, and the lower-level problem is the minimization of a smoothed version of merit function. Merit function usually serves as an objective whose solutions are a set of weak Pareto optimal points. The authors provide a comprehensive analysis for the proposed problem. In particular, they first provide some properties of the smoothed merit functions under the assumption that f_m is quasar-convex function. Then, they consider a penalized reformulation of the original bilevel problem. And then they characterize the equivalence between the two problems in terms of global or local solutions, based on the assumption on the global subanalyticity, Holderian error bound and KL inequality. Experiments validate the effectiveness of the proposed method.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for acknowledging that the problem is important and the bilevel perspective is new. We would like to emphasize that the bilevel problem in this paper with *non-convex vector-valued lower-level objective* is much more challenging and nontrivial, as pointed out by Reviewer XkmK.\n\nBelow we address your concerns. The link to additional results is https://anonymous.4open.science/r/FOOPS-F746/ICML3045_rebuttal.pdf\n\n>W1.Writing&assumptions not clear... Explicitly point out all assumptions before the theorems.\n\nIt might be a misunderstanding that the HEB and KL conditions are assumed. Instead of directly assuming them, **we prove them** based on the properties of $F$.\nIn our theorems, we list all the required assumptions in the beginning and then discuss other conditions that can be proved. We will clarify this.\n\n>W2.Motivation of smoothing the merit function ...Validate this in the experiments?\n\nSmoothing is commonly used for nonsmooth optimization problems, whose motivation is well-studied in prior works, e.g. [R1] and references therein. [R1] shows that smoothing is necessary for finite-time convergence of nonconvex nonsmooth problems using any algorithm. Therefore, we use LSE to smooth the max-min nonsmooth $\\bar{u}$ to ensure finite-time convergence, which is widely used in prior works, e.g. [R2]. In our experiments, we find that without smoothing, it could return NaN (not a number) errors and the algorithm could diverge.\n\n[R1] Deterministic Nonsmooth Nonconvex Optimization. M.I. Jordan, et. al. COLT 2023.\n\n[R2] An alternative softmax operator for reinforcement learning. Kavosh Asadi, et. al. ICML 2017.\n\n>W3.Smoothing introduces hyperparams. \\tau and l. How to select them? Provide ablation studies.\n\nWe choose $\\tau,l$ to be small and to ensure differentiability. We use grid search to tune them. See more details in Appendix F. We provide an ablation study in Table C in the link.\n\n>W4.The assumptions could be strong...The subanalyticity&KL assumptions make the analysis less applicable...Justification of problems in the experiments satisfying these assumptions (ok if partially)?\n\nNote that compared to existing works for OPS (Table 2) and bilevel optimization (Table 5), which usually require convexity or PL assumptions, our assumptions are actually much weaker. The subanalylticity and KL conditions are weaker than PL, see more discussions in Appendix C with examples justifying the assumptions.\n\n>W5.In lemma 3.4, meaning of global subanalyticity?...A definition should be provided.\n\nWe have mentioned in the main paper, lines 204-216 that, the definition of (global) subanalyticity, including both subanalytic functions and sets is provided in Appendix C, Definitions C.1 and C.2.\n\n>W6.In theorem 3.5, what is the definition of $(\\epsilon,\\delta)$-global solution for (CP)?\n\nThe $(\\epsilon,\\delta)$-global solution for (CP) is that, $f_0(x) - \\min_{x\\in {\\cal X}_{\\delta}} f_0(x) \\leq \\epsilon, x\\in {\\cal X}_{\\delta} = \\{x \\in {\\cal X} \\mid v_{l,\\tau}(x) + \\tau\\ln M \\leq \\delta \\}.$ This is a widely used definition for constrained optimization.\n\n>W7.The algorithm is complex, containing multiple hyperparameters like $\\tau, l, \\gamma_t, K_t, \\alpha_t,\\beta_t$, as well as two projections in steps 5 and 8. Compared to previous methods like EPO, FERERO, this is less appealing.\n\nThis might be a misunderstanding. The algorithm is general such that it can be applied to both the cases when $\\cal X$ is compact and when ${\\cal X} = R^q$.\nWhen ${\\cal X} = R^q$, the two projections are not needed, which is the case in our experiments. $K_t$ can be chosen to be small like 1 or 2. As a comparison, FERERO also requires choosing hyperparameters such as $\\alpha_t,\\gamma_t,K,c_g,c_h$. So the number of hyperparameters is similar. They do not make FOOPS more complex or inefficient.\n\nWe do provide a run time in Appendix F, Table 10 in the paper, and Table A in the link to show FOOPS is comparable or more efficient than FERERO.\n\n>W8&**Methods&Evaluation&Experiment**: Experiments are not convincing. In Table 4, it is very close to FERERO-FT ...confidence interval... A running time comparison could be provided to further justify the efficiency compared to FERERO.\n\nWe respectively disagree. We show in Table 3 that FOOPS achieves much better hypervolume compared to FERERO and other baselines. In Table 4, it achieves comparable average performance as FOOPS. So we believe our result demonstrates FOOPS is effective, as *acknowledged by all other reviewers*. This experiment takes much longer time. We will run additional experiments add the confidence in the revision.\n\nRunning time comparison is given in Appendix F, Table 10 in the paper, and Table A in the linked PDF. Results show FOOPS can be faster than FERERO.\n\n>**References:** More works on differentiable MOO could be discussed.\n\nThanks, we will include a discussion in the revision.\n\n---\nWe hope we have addressed your concerns and you can reconsider the rating of our paper. Thanks!", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "A running time comparison and confidence intervals could be provided.", "theoretical_claims": "Check some proofs and did not find main problems.", "experimental_designs_or_analyses": "A running time comparison and confidence intervals could be provided. More details", "relation_to_broader_scientific_literature": "The idea of using bilevel optimization for preference-based multi-objective optimization is new to the literature.", "essential_references_not_discussed": "Yes. it includes the most important works on preference-based MOO. However, more related works on differentiable MOO in ML could be provided. For example, PCGrad, CAGrad, NashMTL, MoCo, SDMGrad, where CAGrad and SDMGrad also introduce preference-based regularization or constraints. They should be discussed.", "other_strengths_and_weaknesses": "Strengths:\n\n1.\tThe studied problem is very important in multi-objective optimization, because we often tend to find a preferred point on the Pareto front. The bilevel optimization perspective seems to be new.\n\n2.\tThe authors analyze the smoothed merit function and the equivalence between the bilevel problem and the panelized problem under some assumptions. Experiments seem to support that the proposed method can get higher accuracy.\n\nWeakness: \n\n1.\tThe paper is not well written. The analysis part makes multiple assumptions. Some theorem requires the convexity-like assumptions, some needs HEB assumption, and later a KL inequality is needed to guarantee the penalty function is less than \\epsilon. I suggest explicitly point out all assumptions in before the theorems. \n\n2.\tThe motivation of smoothing the merit function is not very clear to me. I understand that the original merit function could be non-differentiable. It may not be a problem in real-world problems. Can the authors validate this in the experiments to see if smoothing is necessary? \n3.\tAnother issue for this smoothing is that it introduces two more hyperparameters \\tau and l. Can the authors explain how they select these hyperparameters in practice? Ablation studies should be provided. \n\n4.\tThe assumptions could be quite strong. The point strong quasar-convexity assumption is hard to be satisfied in practical problems. Although the authors mention some examples such as linear models with leaky ReLU, for general setups, it may be hard to validate this assumption. In addition, the subanalyticity and the KL inequality assumptions further make the analysis less applicable to the practical cases. It would be great if the authors could provide some justification that the problems in the experiments could satisfy these assumptions (it is ok if just partially)? \n\n5.\tIn lemma 3.4, what does it mean by X_v^* \\cap X_C is globally subanalytic. The assumption 2 is made on the function rather than the set. Perhaps a definition on subanalyticity should be provided. \n\n6.\tIn theorem 3.5, what is the definition of $(\\epsilon,\\delta)$-global solution for (CP)?\n\n7.\tThe algorithm is complex, containing multiple hyperparameters like $\\tau, l, \\gamma_t, K_t, \\alpha_t,\\beta_t$, as well as two projections in steps 5 and 8. Compared to previous methods like EPO, FERERO, this is less appealing. \n\n8.\tExperiments results are not convincing. In table 4, it is very close to FERERO-FT. Then, multiple seeds with confidence interval should be provided. A running time comparison could be provided to further justify the efficiency compared to FERERO.", "other_comments_or_suggestions": "see the strengths and weaknesses.", "questions_for_authors": "see the strengths and weaknesses.", "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": "Qzr8uumfrn", "reviewer": "Reviewer_SqKr", "summary": "This paper considers the problem of preference-guided multi-objective optimization. The authors first formulate it as a semivectorial bilevel optimization problem, which optimizes the upper-level preference objective, subject to the constraint that the model parameters are weakly Pareto optimal or Pareto stationary for the lower-level multi-objective optimization problem. The authors further propose an algorithm to solve this semivectorial bilevel optimization problem, which first converts the lower-level constraint to a single-objective constraint through a merit function, then solves the transformed problem by a penalty-based reformulation. Theoretically, the authors analyze the relations of solutions for different formulations and the convergence of the proposed method. Empirical results on various synthetic and real-world problems demonstrate the effectiveness of the proposed method.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for acknowledging that **we propose a novel formulation and an easy-to-understand novel method for preference-guided multi-objective optimization, our proof is sound and interesting, and the experiments are sufficient with sound analysis**.\n\nBelow we address your concerns point by point. The link to additional results is https://anonymous.4open.science/r/FOOPS-F746/ICML3045_rebuttal.pdf\n\n>**Claims And Evidence:** \"The preference-guided multi-objective optimization problem can be solved through a semivectorial bilevel optimization problem\" is unclear... How are $G(x)$ and $H(x)$ related to $f_0(x)$? Whether they are solving the same problem?\n\nYes, $F(x)$ remains the same. The relation of $G,H$ to $f_0$ is that $f_0$ can be chosen as $f_0(x) = ||H(x)||^2 + ||[G(x)]_+||^2$. $f_0$ is minimized when $H(x)=0$ and $G(x)\\leq 0$. In our experiments, we show the example for equality-constrained problems without $G$ and with $f_0(x) = ||H(x)||^2$. See Section 6, and Eq. (16) for the speech experiment.\n\nThe two formulations are not equivalent mathematically. But both can be applied to preference-guided multi-objective learning with different emphasis on either satisfying preference or achieving weak Pareto optimality. As discussed in Section 3.3 and Section 6 in our paper, the constrained formulation in e.g., PMTL and FERERO with preference modeled by constraints $G$ and $H$ puts more emphasis on satisfying the preference, while the FOOPS formulation with preference modeled by $f_0$ puts more emphasis on achieving weak Pareto optimality.\n\n>**Methods And Evaluation Criteria:** While the proposed method is easy to understand and the evaluation is sufficient, I am a bit curious on whether the proposed method can be combined with other bi-level optimization methods, as is also mentioned in Appendix A.1. Specifically, after converting the lower-level constraint to a single-objective constraint, I suppose the converted problem can be also solved by some bi-level optimization methods other than the penalty-based formulation? Some empirical comparisons can be useful here.\n\n- *Other bilevel methods.*\nThanks for the suggestion. Indeed, the penalty method used in this paper is not the only way to solve a bilevel problem. However, the existing methods listed in Appendix A.1, Table 5 require **different assumptions** which cannot be satisfied by our converted problem. Therefore, the methods in Table 5 cannot be directly applied to our converted problem.\nHowever, we provide a discussion on how some other methods could be applied under certain additional assumptions.\nFor example, the recent concurrent AGILS (Bai et al., 2024) method can be applied when the merit function $v_{l,\\tau}$ has HEB with $\\eta \\geq 1$.\n\n- *Empirical comparisons.*\nSince other existing bilevel methods require different assumptions, they cannot be directly applied to our converted problem. Further investigation is needed to check whether the methods still work under weaker assumptions. The concurrent AGILS (Bai et al., 2024) method may be applied to specific problems satisfying the assumptions therein, which we leave for future work. We provide a comparison to other OPS methods such as PNG in Figure A and Table B in the link.\n\n>**Other Comments Or Suggestions:** The authors seem to have modified margins in some places, e.g., lines 110-116 and lines 432-439. This should be strictly forbidden and some reasonable explanation is necessary here.\n\nThanks for spotting this. We would like to clarify that **we did not intentionally or explicitly alter the margins**. Instead, we used the {\\small } environment in LaTeX to reduce the size of Equations (5) and (16) so they would better fit the space. This inadvertently caused the line spacing for lines 110-116 and 432-439, immediately before the equations, to appear smaller, despite our attempt to limit the {\\small } environment to the equations themselves.\nIn response to the reviewer’s feedback, we will modify the paper to remove this unintended spacing issue.\n\n---\nWe hope our rebuttal resolves the reviewer's concerns and the reviewer can reconsider the rating of our paper. Thanks!", "claims_and_evidence": "There are two key claims in this work:\n- The preference-guided multi-objective optimization problem can be solved through a semivectorial bilevel optimization problem\n- The proposed method FOOPS can effectively solved the obtained semivectorial bilevel optimization problem\n\nWhile the second claim is supported by sound theoretical analysis and empirical results, the first claim seems not sufficiently supported from my perspective. I am a bit confused on how the original formulation for preference-guided multi-objective optimization:\n\n$\\min_x F(x), s.t., G(x) \\le 0, H(x)=0$\n\ncan be re-formulated as\n\n$\\min_x f_0(x), s.t., x \\in \\arg\\min F(x)$\n\nI suppose $F(x)$ remains the same, while how are $G(x)$ and $H(x)$ related to $f_0(x)$? Some more explanations are necessary here. Without such explanations, it is even unclear how existing preference-guided multi-objective optimization methods are implemented and if they are solving the same problem.", "methods_and_evaluation_criteria": "While the proposed method is easy to understand and the evaluation is sufficient, I am a bit curious on whether the proposed method can be combined with other bi-level optimization methods, as is also mentioned in Appendix A.1. Specifically, after converting the lower-level constraint to a single-objective constraint, I suppose the converted problem can be also solved by some bi-level optimization methods other than the penalty-based formulation? Some empirical comparisons can be useful here.", "theoretical_claims": "Theoretical analysis in this work is sound and interesting. I have checked the proofs in Appendix B-E and found they are clearly organized and easy to understand without significant errors.", "experimental_designs_or_analyses": "Generally the experiments are sufficient with sound analysis.", "relation_to_broader_scientific_literature": "This paper proposes a novel formulation of preference-guided multi-objective optimization as well as a novel method (based on smoothed merit functions and existing gradient-based bi-level optimization methods) to solve the optimization problem under this formulation.", "essential_references_not_discussed": "The references are generally complete, and I do not have any works that are strongly recommended to be included.", "other_strengths_and_weaknesses": "All mentioned in previous parts", "other_comments_or_suggestions": "The authors seem to have modified margins in some places, e.g., line 110-116 and line 432-439. This should be strictly forbidden and some reasonable explanation is necessary here.", "questions_for_authors": "Please see the mentioned points of weakness in the **Claims And Evidence** and **Methods And Evaluation Criteria** part, as well as the possible violation of paper format template.", "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:

Meta-review: This paper explores the problem of multi-objective learning under preference guidance. It formulates the problem as a semivectorial bilevel optimization task and proposes a first-order penalty approach to solve it. The paper further establishes the theoretical foundations of the proposed method and demonstrates its practical effectiveness on several machine learning tasks.

The reviewers agree that this paper addresses a challenging and important problem in multi-objective optimization, that the proposed method is novel, and that the theoretical foundation is solid. Given its important contributions to the field, I recommend accepting this paper to ICML.
Decision: Accept (spotlight poster)