Preference Optimization on Pareto Sets: On a Theory of Multi-Objective Optimization
Authors: Abhishek Roy
Geelon So
Yian Ma
Venue: NeurIPS 2025 poster ()
Keywords: multi-objective optimization
Pareto set
non-asymptotic convergence
preference function
Primary area: optimization
TL;DR: An algorithm with theoretically guaranteed convergence rate to optimize a preference function over the Pareto set of a given set of objectives.

Abstract: In multi-objective optimization, a single decision vector must balance the trade-offs across many objectives. Pareto-optimal solutions are those achieving optimal trade-offs, where improving any objective comes at a cost to another. As many different decisions can be Pareto optimal, this raises the question of which solution to pick and how. We formulate this problem as one of optimizing a preference function over the set of Pareto-optimal solutions, or Pareto-constrained optimization for short. It poses significant challenges: not only is the constraint set defined implicitly, but it is also generally non-convex and non-smooth, even when the objectives are strongly convex. We propose an equivalent formulation of the problem where the constraint set is the simplex, leading to clearer notions of optimality and stationarity that improve upon existing definitions in literature. We give an algorithm with a last-iterate convergence rate of $O(K^{-1/2})$ to stationarity when the preference function is Lipschitz smooth and when the objective functions are strongly convex and Lipschitz smooth. Motivated by applications like Reinforcement Learning with Human Feedback (RLHF), we also extend this algorithm to the case where access to the preference function is only available through dueling feedback.

Preference Optimization on Pareto Sets: On a Theory of Multi-Objective Optimization
Abhishek Roy" Texas A&M University abhi shekro@@taa. edu
Geelon So UC San Diego geelon@ucsd. edu
Yi-An Ma UC San Diego
yianma@ucsd, edu
Abstract
In multi-objective optimization, single decision vector must balance the trade-offs across many objectives. Pareto-optimal solutions are those achieving optimal trade- offs, where improving any objective comes at cost to another. As many different decisions can be Pareto optimal, this raises the question of which solution to pick and how. We formulate this problem one of optimizing a preference function over the set of Pareto-optimal solutions, or Parett-constraiine optimization for short. It poses significant challenges: not only is the constraint set defined implicitly, but it also generally non-convex and non-smooth, even when the objectives are strongly convex. We propose equivalent formulation of the problem where the constraint set the simplex, leading to clearer notions of optimality and stationarity that improve upon existing definitions in literature. We give algorithm with a last-iterate convergence rate of O function is Lipschitz smooth and when the objective functions are strongly convex and Lipschitz smooth. Motivated by applications like Reinforcement Learning with Human Feedback (RLHF), also extend this algorithm the case where access to the preference function is only available through dueling feedback.
to stationarity when the preference
Introduction
Modern, large-scale machine learning often draws data from diverse sources, simultaneously deployed across many settings to perform many tasks, or need to perform well across many different metrics. These learning settings naturally be formulated as multi-objective optimization (MOO) problems, including multi-task, multi-distribution, meta-learning; multi-calibration, multi-group learning; learning from crowds, from heterogencouu/mmuti-neeeee
sources; personalization, prefer- ence learning; hyperparameter optimization, model fine-tunin tie-ttnnng and model fusion (Jin, 2007; Sener and Koltun, 2018: Huang al., 2015; Haghtalab et al., 2022; Ye al., 2021; Reed et al., 2022; Martinez et al., 2020; La Cava, 2023; Kamani et al., 2021; Globus-Harris et al., 2022: Lee et al., 2022; Tosh and Hsu, 2022: Raykar et al., 2010; Chen al., 2025a). As a result, MOO has increasingly attracted the interest of the learning community. But, in contrast to the single-objective case, far less has been established theoretically and algorithmically for the multi-objective setting- even very basic questions may not have rigorous definitions or solutions. We formalize and tackle such a problem.
To give intuitive problem description, consider the concrete example of large language model (LLM) alignment (Houlsby et al., 2019; Liu et al., 2022; Ding et al., 2023). In this problem, we aim to finetune LLM outputs achieve number of desiderata: positivity of the tone, succinetness of the answer, consistency with lexical conventions, and so on. While no model is generally optimal under all criteria, is Pareto optimal if it makes an optimal trade-off between the objectives. We would like our decision to at least be Pareto optimal, as this means no other decision was strictly better by all metrics. Many different trade-offss can usually be made; we call the of all such decisions the
Equal contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Pareto set. Eventually, as we must single out one from this set to deploy, we ask how to select the most preferred Pareto-optimal solution. That is, out of the many different possible trade-offs that can be made, which one do we choose and how do we discover it?
There are main frameworks to making this selection (Hwang and Masud, 2012). The first is through scalarization, where multiple objectives are aggregated into one. Thus, it reduces the problem back to the familiar single-objective setting (Mahapatra and Rajan, 2020; Lin et al., 2024). The second, indirect approach is to find a representative subsample of the Pareto set; this helps a decision maker by paring down the number of solutions that need be inspected (Lin al., 2019; Liu et al., 2021: Kobayashi et al., 2019; Guerreiro et al., 2021).
Neither approach quite fully answers how to select the final trade-off. It might not be clear how to meaningfully scalarize a multi-objective problem, especially when the objectives are incomparable. And while subsampling can reduce the complexity of the problem, the actual decision is left open. For classical settings, these gaps may not be crucial. But modern, large-scale decision-making settings can be high-dimensional, incorporate many objectives, or have high-throughutt and need to be automatic. It may be impossible to scalarize the problem by hand, and even representative subsample of the Pareto set can become untenably large, scaling exponentially with the number of objectives (Papadimitriou and Yannakakis, 2000). There is a need for a more principled selection, which motivates the question we ask:
Given a set of objectives (f1..... and a preference fu. how do we define a suitable notion of the most preferred Pareto solution, and how do we efficiently approximate it?
The preference- based formulation of multi-objective optimization, with the inclusion of a preference function fo. refines more common versions of MOO given in standard references (e.g., Ehrgott (2005)). and the preference fo are mathemattcally the same type of objects,
While the objectives fi,..., , Sn the latter can conceptually represent the more ineffable desiderata that human prcisiin-mmkeen or users may have, as in the earlier example about LLM alignment. For this reason, we also consider learning from dueling preference feedback in this paper. In that setting, instead of direct access to fo- we can only ask users to rank different options x according to their preferences fa()..
Besides LLM finetuning, several standard problems in machine learning also fit this preference- based framework of MOO. In fairness-aware learning, the objectives can represent subgroup utilities, while the preference fo is a social welfare function. In neural architecture search, objectives can be accuracy, latency, and energy consumption while fo can be user-specific preferences reflecting their priorities. In portfolio optimization, objectives could be return, risk, and liquidity, while So might capture the risk aversion tendency of an investor. We now formalize the problem mathematically.
1.1 Pareto-Constrained Optimization
Let = (fi...., Idd + R. be a set of objectives that are jointly minimized over a shared decision space Ied and let Pareto(F) FF) be the set Pareto-optimal solutions, consisting of decision vectors Id that make an optimal trade-off between objectives. As it is often not clear a priori which trade-off to make, we consider the Pereto-constraineed optimization problem, where the aim is to optimize preference function fo Rd - R constrained the Pareto set of F:
minzzPaarto(F)) Jo(æ))
and we call solution x of this optimization problem preference optimal. This problem is also called semivectorial bilevel optimization or optimization on efficient sets, and can be considered as an instantiation of bi-level optimization (Bolintinéanu, 1993b; Yamamoto, 2002; Bonnel and Morgan, 2006; Dempe, 2018; Ye and Liu, 2022). It has applications for economics, portfolio management, manufacturing planning, and machine learning (Thach et al., 1996; Yamamoto, 2002; Ye and Liu, 2022). While heuristics have been proposed, little more is known. In fact, even notions such as stationarity have not been formalized, which is generally needed to study convergence.
Main Challenges There are major challenges to this problem.
1. Theoretical Chullenges. The Pareto set is generally non-smooth and non-convex. It can have "needle-like extensions" and "knees" (Kulkarni et al., 2022), or "singularities" (Sheftel et al., 2013). These are possible even when the objectives are quadratics (see Figure 1). Moreover,

---

in the setting where both objectives and preferences are linear, the problem is known to be NP-hard (Fülöp, 1993). Thus, there a need for appropriate relaxations of the problem that are algorithmically attainable. But even defining a reasonable notion of stationarity is not straightforward, given the complicated nature of the constraint set (Zhang et al., 2020; Kornowski and Shamir, 2021; Li et al., 2020; Jordan et al., 2023; Kornowski et al., 2024).
2. Algorithmic Challenges. The Pareto set is non-smooth, non-convex, and an implicitly defined object. It not clear how to analytically parameterize Parcto F)) or to specify Parcto F) as feasible set of system of inequalities. Pareto cnneto-constrained optimization (1) becomes even more challenging when we do not have access to the preference function for but only preference comparisons between two decision vectors, as is the case of RLHF for LLM alignment.
1.2 Main Results
We consider Pareto-constrained optimization with strongly convex and smooth objectives f1,..., . fn- and smooth, but potentially nonconvex preference function fo- We list our main contributions below.
1. We introduce the Pareto manifold of F (Definition 3), 'lifting' of the Pareto set, that recovers the Pareto set when projected down to R4, We show that the Pareto manifold is a smooth manifold diffeomorphic to the (n - si-sipee This leads to clear notion of stationarity.
2. We use the connection with the simplex to introduce an (approximate) stationarity condition (Definitions 3 and 5) for the pareto-constrainet optimization. We show that any non-trivial, local stationarity condition requires more than local first-order information about F.
3. We propose the Pareto to an (5o. aapproxxmmte preference stationary point of Pareto-constraing optimization with iteration complexity ((5²)), ignoring logarithmic factors, under first-order feedback fo (Theorem 10), and noisy dueling preference feedback (Theorem 11).
Bogrrization-Mnnmizzaan
algorithm (Algorithm 1), which converges
1.3 Related Work
Selecting the most-preferred decision vector out of the Pareto set is a classical problem in MOO (see Bolintinéanu (1993b) and related works therein for classical motivation), and it has also gained renewed interest from the machine learning community. However, is well-established to be challenging (e.g. Fülöp (1993)), and most prior work studying the Pareto-constrained optimization problem have largely focused on (i) linear preferences (Philip. 1972; Benson, 1984; Liu and Ehrgott, 2018), (ii) linear objectives (Dauer, 1991; Bolintinéanu, 1993a; Tao et al., 1996; Yamamoto, 2002), or (iii) specific choices of preference functions (Steuer, 1989; Mahapatra and Rajan, 2020).
To our knowledge, there are only two prior works that have studied the problem more generally in the nonlinear setting. The first work is Bolintinéanu (1993b), which considers a regularized version of the problem: they balance the preference fo with penalty term capturing the Pareto set of F. While regularized solutions are suboptimal for the original problem, they show that these solutions asymptotically become optimal as the weight the penalty term goes to infinity. They also describe a necessary condition for the regularized solution, which can be approximated via nonlinear programming. The second work is Ye and Liu (2022), which provides heuristic for the same problem based on a similar but distinct penalty function. They also propose a stationary condition stationarity with respect to their optimization dynamics. But, this turns out to not be necessary condition, meaning that their dynamics can actively avoid optimal points (see Appendix D).
These two conditions in both papers entangle independent aspects of an ideal solution: (a) being close to preference optimal and (b) being close to the Pareto set. As a result, these conditions can seem somewhat opaque. In this work, we first clarify the manifold structure of the Pareto set under strong convexity of the objectives. This enables us to keep these two aspects disentangled, and to derive standard, necessary relaxations of preference optimality. While existing work have studied the smoothness structure of the Pareto set (Hillermeier, 2001a,b; Hamada et al., 2020), the prior focus has been on extrinsic smoothness within the decision space. We instead leverage the intrinsic geometry of the Pareto manifold, which is diffeomorphic to the simplex, to simplify optimization.
The algorithm we propose along with its analysis draw majorization cnnpriaaationnnnnizzaiioo and trust-region ideas to handle the implicit nature of the problem (Lange et al., 2000; Marumo et al., 2023). This algorithm can make use of both first-order preference information dueling feedback. For ducling
3

---

feedback, we work under a standard preference learning model (see Section 6.2) from psychology, statistics, and also more recent learning literature (Bradley and Terry, 1952; Agresti, 2012; Wang et al., 2023). For this setting, we also make use of ideas from derivative-free or zeroth-order optimization (Jamieson et al., 2012; Saha al., 2025; Cai et al., 2022). In terms of guarantees, we provide the first finite-time convergence result to approximate preference stationarity. Additionally, we provide non-asymptotic guarantees on the suboptimality of approximately preference-optimal solutions, which parallel the asymptotic guarantee of Bolintinéanu (1993b).
Following an earlier version of this article shared on arXiv, Chen al. (2025b) developed results for the Pareto-constrained optimization problem that goes beyond strictly-convex objectives.
Organization In Section 2 we discuss some preliminaries on Pareto set. In Section 3, we introduce the Pareto manifold. In Section 4, we define preference stationarity. In Section 5, define approximate preference stationarity and formalize our assumptions. In Section 6, we present Algorithm 1, which solves
optimization under two feedback models: (a) access first-order feedback, and (b) access to preference comparisons. In Section 7, we provide rates of convergence. For detailed glossary, see Appendix A. Full proof' provided in the appendix.
The Pareto Set
From multi-objectivg optimization, recall that decision is Pareto optimal if there is no way to improve any one fi without also worsening some other fz. Formally:
Definition (Parcto optimality). Given objectives fi...., , Sn. we say that a decision vector x E RRd is Pareto optimal if for all x' E I
fi(x') < f((x)
Ej s.t. [ > fz(2).
The set of Pareto optimal decision vectors of fi,..., fn forms the Pareto set, denoted Pareto(F),
For smooth objectives, related, first-order condition called Pareto stationarity is necessary for Pareto optimality Maruşciac (1982). In the following, let n-11 denote the (n - -immmple, and for all B E A" ==11, let fs denote the linear scalarization:
fa(z) == (1fi(z) + Pnfn(x).
(2)
Definition 2 (Pareto stationarity). Given objectives fi,..., Jun we say that a decision xr E Rdd is Pareto stationary if fa(x) 0 for some
A
When the objectives fi..... fn are twice-differentiable and strictly convex, Pareto stationarity is also necessary for Pareto optimality Fliege et al. (2009). We shall assume throughout that the objectives smooth and strongly convex (Assumption A), so these two notions coincide. Given these definitions, defined in (1) is highly non-trivial: the Pareto set remains
optimization constrained to the Pareto implicit, and it is generally non-smooth and non-convex. The following gives the example Figure 1.
Example (A singular Pareto set arising from strongly convex objectives). Define three positive- definite quadratic objectives fi IR² + IR of the form f((r) = 1 {xx - xx,) At(x - Z.).
0 00
A = 0.25 0
1 0.5
0.5
A = σι
=
22
As =
0.25
x3 =
1
Even in this highly-structured setting where all objectives are strongly convex quadratics, the Pareto set is non-convex and has a singularity. This example is visualized in Figure
3 Lifting to the Pareto Manifold
We overcome the issue of non-smoothness of the Pareto set by lifting the problem into higher- dimensional space Rd x A n-1 which contains what we call the Pareto manifold. This is the set of all tuples (xr, B) such that & Pareto stationary point of the linearly scalarized objective fa.
Definition 3 (Pareto manifold). The Pareto manifold P(F) C R x A-- is the zero set:
P(F) {xx fz(zz) 0}.
Farlier title: Optimization Pareto Sets: On Theory of Multi- Abjti--bjeettve Optimization (Roy et al., 2023).

---

183.00
A
Pareto F)
Figure 1: The Pareto set of the three positive-defintt quadratic objectives given by Example (Left) The 2-simplex parametrizes all scalarizations fa. (Right) The Pareto set in I2 For each 3 E A?, the minimizer x (B) of fa is Pareto optimal; the colors preserve this correspondence.
In the case of strictly convex objectives, the projection of the Pareto manifold P(F) to its first component in the decision space Rd precisely yiclds the Pareto set, as shown by Lemma 1. As this projection
also collapse any smoothness structure that P(F) has, it becomes clear how non-smoothness arises on the Pareto set. On the other hand, Proposition 2 shows that it is a smooth submanifold of Rd A n diffeomorphie the (n 1--simllex.
Lemma 1. Let F (fi....,fw. fn) be a collection of smooth and strictly convex objectives, Then: (x, B) P(F) for some 3 An1
Parcto(F)
Proposition (Characterization of the Pareto manifold). Let F (f Sn) be collection of smooth and strictly convex objectives. Define x" An~ Pareto(()) by:
x² (3) Dg == arg min f((x)).
(3)
Let VF(x) Raxd be the Jacobian. Then, the map x² has derivative:
Vx (B) - -((
(4)
n- so that the map B (xz, B) a diffeomorphism of n with the Pareto manifold P(F).
The main tool used is the implicit function theorem; we defer the full proof' to Appendix B.
4 Solution Concept: Preference Stationarity
The tight connection between the Pareto set and the Pareto manifold given by Lemma allows us to smoothly lift the preference optimization problem (1) onto the Pareto manifold, as follows:
(in(a.)))P(() fo(x).
And as Proposition 2 shows, the Pareto manifold is diffeomorphic to the simplex, so (5) further reduces the following smooth optimization over the convex n-1
mingeA (Jo o x" (3)).
This is an equivalent formulation: if 3 solves (6), then x (B) solves (1) and (5). Furthermore, as the constraint set the simplex, we can appeal to convex optimization for the following notion of preference stationarity, which is necessary for preference optimality (Nesterov, 2003).
Definition 3 (Preference stationarity). We say that point x Pareto(F) is weakly preference stationary if there exists some 3 E n- where (ar, B) E P(F) such that:
v(fo x (3) 50
VB' A--1,
(7)
with Vx as in (4). (7) holds for all B where (z, 3) P(F), then x is preference stationary.
As (F(xs) B fsa(#)) 0, (7) reduces
- o (B) 8' S for all & n-1

---

Proposition 4 (Necessary condition (Lemma 3.1.19 of Nesterov (2003))). Preference optimality implies (weak) preference stationarity.
It turns out that developing reasonable relaxations of preference optimality without lifting the problem to Pareto manifold is surprisingly subtle. For example, prior notion of stationarity (e.g., Ye and Liu (2022)) is not necessary for preference optimality (Appendix D.I). Any optimization dynamics that achieve stationarity conditions that are not necessary can actively avoid optimal decisions. We show that any local first-order condition suffers from this limitation (Appendix D).
5 Algorithmic Solution Concept: Approximate Preference Stationarity
In first-order optimization, notions of approximate stationarity allow us to provide meaningful, finite- time guarantees about the solutions that are reached by optimization algorithms in practice; likewise, we introduce the following e-approximate version of preference stationarity. Again, we appeal to a standard notion of approximate solutions Nesterov (2013); Marumo et al. (2023).
Definition $ (Approximate preference stationarity). Let So, E 2 A point (x, E E x A n-1 is
(co, -preferencc stationary if:
-ololz)) Vn ( 3) S Eol B11,,
4g nーー
(8a)
[[Vf((>)]22 S
(8b)
Intuitively, if (a, B) is approximately preference stationary, then (a) there a ball around 9 within which fo x* decreases at most at an O(so)-rate when moving away from B, and (b) the point & is O(s)-close to g.. We will formalize this geometric interpretation in Proposition To do so, we need to formalize the assumptions, which are standard and used in the rest of the paper.
Assumption A. Let the objectives Ji,...: Jn Rd - TR be twice differentiable, pu-strongly convex, and have L-Lipschitz continuous gradient. That is, μI V f((z) 3 LI for all i ,,...,n. n. We also define K. := L/u μ and r := maX].jE[m] || arg min f.(x) - arg min f, (z)]l2
Assumption B. Let the objectives f1,-.., Sn : IRd + IR have I --pisschhtt continuous Hessian. That is, for all x. y Bd and i ,,..., we have 2 fx(x) V f(w))l2 S LH || 1x---p v1l2-
Assumption C. Let the preference function fo IRd + R have Lipschit continuous gradient. That for all v, E Rd, we have [f[() (o)) < Lu || yl12
Assumption allows us to bound the diameter of the Pareto set (Lemma E.1); Assumption B bounds the curvature of the Pareto manifold (Lemma E.2); and all three lead to bounds on approximation errors (Lemma E.5 and Lemma E.6) needed the constraint set is implicit. They also lead to the following geometric intuition for approximate preference stationarity (see Appendix E for proof).
Proposition 6 (Geometric meaning of approximate stationarity). Let (ă, 39 be (co, -preffrccce stationary. With Assumptions A,B,C, and R == diam (Pareto(F)) and s == 24 (LooLLLLL (LoL2R²) R²), then:
(a) fl B11 < then fo(Øz) fo(zz) 2 - 3| 11|,, and
(b) || - r2ll2 2 e/μ.
5.1 Overcoming Implicitness: Approximating Local Information
The final issue is that these notions of (approximate) preference stationarity are implicit. They depend on Vx (3) and x², which come from solving the optimization problem:
xx (5) 23 arg min fa(z). sERd
(3)
Vx (
(4)
Since 2a does not generally have a closed form, we cannot exactly compute Vx" (B), which is needed to directly check whether the pair (&, B3) is (approximately) preference stationary. Since cannot compute Vx (8) exactly, an obvious estimator is the following, which uses local information 22 fz() and V Fxx) at x as a proxy for the corresponding local information Zgzt
Vx" (z, = VV
(10)

---

Algorithm Pareto majorizationn-miinnizzaioo (PMM)
Input: objectives F (f1,- -...,,.:: fn); preference function Jo: black-box optimizer arg min; family of majorizing surrogates {g(: 22, B) (x, 3) E R2 x A An-1 exact (13) approximate (16)
Initialize: (zo, Pb) E R x An-1
1: for k k= ...... K do
2: Select the (approximate) majorizing surrogate gi(()) + g(- 1k Bx))
3: Compute approximate minimizers
Bk+1 f arg min (3) and Tb+1 < arg min S (x). BEAn-1
(9)
aggd
4: end for
5: return (IK+1, 3k+11
With the above assumptions, approximate information enough to verify approximate stationarity. Again, defer proofs to Appendix E.
Lemma 7 (Verifiability of approximate stationarity). Under Assumptions A,B,C, the point (8, is (Eore) preffrenee stationary if V ( S and for some x E IRd and a E (0,
(a) a -o-ppproxiimaee stationary condition holds for all 3' E An-1: -V Vx* (x, ()(3 - BB S a colls -B11,
(11)
(b) an error bound holds: so S aa) -o. where:
erT fo (x,
Mi
[fo(z)]l2 LoMo) [V
2M
and Mo = KR, M = 2x² R(1 l + LB R/Ru.
Algorithm Design: Pareto Majorizationn-Miiniaatee
In this section, we present our algorithm to solve (6). While this is conceptually the optimization of smooth function f o x² over the convex set A n-1 the main challenge is that the objective implicit. Methods like gradient descent require both x² and Vx to compute the gradient via chain rule:
ViJo oz (B) = V fo (B)) Vx'(3)
But, if we can estimate (3) to arbitrary precision by solving the optimization (3), then Vx*(3) also be approximated arbitrarily well: both of its terms, F((x)) and V f²fa(xx=11 continuous in x and 33 by assumption. Thus, the estimator Vx* (x. approaches z3. We will quantify the validity of the estimator by using it to construct majorizing surrogate function, a function that upper bounds fo x", where better estimators yield tighter bounds.
defined in (10) approaches Vx Vx* (3) as x
Definition 4 (Majorizing surrogate). A function g n H. majorizes fo x= if:
Jo(*x) S (3"),
(12)
for all B' E n-1 We say that g is a (majorizing) surrogate of f.
The following uses the estimator Vx (s. (3) to construct a family of quadratic surrogates for fo xx. An error term errv (x,,3) ()) appears constant in (13), which Lemma E.6 shows goes to zero as (x., (3) goes to (x3,,1), Thus, the estimator becomes more 'valid' with better estimates of (()). Proposition 8 (A family of majorizing surrogates). Let F and fo satisfy Assumptions A,B.C. Ler
errv (x. 3) be as defined in Lemma E. Define the family indexed by (z, 3) IRd x A--1
g(3'; x. 8) = fo(æz) + ff(x)) (x, (x, (5' - 3) + 1 313 e where Hg := nLoM Then g(8'; xr 3) majorizes fo o xx, satisfying (12).
(13)
This result is proved in Appendix F. Technically, we still cannot explicitly compute (B'; 3 because contains the term Fo(2,)) However, minimize using any gradient-based method, we only need ( xz 3), which does not require the knowledge of fo(2z) nor errv fo (x, 3).
7

---

6.1 Minimizing the Majorizing Surrogate with First-Order Preference Information
The first algorithm we describe assumes access first-order feedback to fo. which allows to compute the majorizing surrogate 9 x, 5) from Proposition 8. We then directly minimize the surrogate. The idealized Pareto majorization ionittttioooiiiniiatiiio (PMM) algorithm proceeds in rounds:
1. majorization: query Vz (IR: 3x) to construct majorizing surrogate gx) 9(3; ZR. 3k),
2. minimization: make updates Bx+1 < arg min gk (5) and 2k+1 f arg min f02t1 (z).
=ER.
The majorizing property of the surrogate ensures that fo(#3,) improves every iteration. In fact, there is no need to fully optimize I and Sa, 1 (x) in the second step. By relaxing this step, we obtain Algorithm when it uses the exact surrogates (13) and any black-box optimizer. In Section we provide a last-iterate convergence rate for Algorithm I to an (Eo. ->reffereeeee stationary point.
6.2 A Model of Dueling Feedback
In the next section, we will extend Algorithm to the dueling feedback setting. Especially in cases of human preferences, exact forms of fo or V are unknown, but we can ask users to rank different options by preference. Such a setting arises, for example, in supervised fine-tuning or RLHF (e.g. Zhu et al. (2023); Ziegler et al. (2019)). We assume a comparison oracle that provides noisy, binary responses to the queries of the form: do you prefer 21 over xz?
Definition 5 (Preference feedback model). Given two options I1 and V2, the comparison oracle returns binary random variable ((1,, x2) (0, 13 where:
E (a1 .22] = a (Jo (((x))))) - fo(x1)),
(15)
and (-) is a link function. response Y (x), x2) = indicates that users prefer #1 over T2-
This is a standard model from preference learning, psychology, and RLHF (e.g. Bradley and Terry (1952); Wang et al. (2023); Chen et al. (2025a)). and it aims to capture the phenomenon where preference judgments tend to be noisier when it is difficult to discriminate a clear winner (Nunnally and Bernstein, 1994). The link function a formalizes the relationship between the 'random component" in the observed responses to the 'systematic component" of the underlying preference values fo fa( (Nelder and Wedderburn, 1972; Agresti, 2012). For analysis, we make standard assumptions, which are satisfied by all commonly-used link functions including the logistic, softplus, and tanh functions.
Assumption D (Link funetion). Let B satisfy B sup Ifo 2¹1. Let o()) [-B, (0, 1) be a known link function that is a smooth, L1- Ln-Lipschitz and monotonically increasing function. We assume that a (0) 2. and the inverse a -(p) is locally Lg (1 + (p(1 (((1-p)) p)) -el--p)))--pppoeeiee L-ipschhtt continuous.
6.3 Optimizing Preferences with Dueling Feedback
In Section 6.1, we described a version of PMM using first-order preference information, where the gradient V fo(z) gives rise to the majorizing surrogate function ( xx, 3x,32, from Proposition 8. Under dueling feedback, the gradient not directly available, but we construct an estimator V fo(). as described in Algorithm
2. The basic idea is to estimate fo(x) by querying preferences between
the pair æ1 = x + UU and 12 = x UU, where is a uniform--t--andoon unit vector and 7 is precision parameter. A single comparison can be seen as an estimate of pu = a fo(z) T.) Since we assume knowledge of a, we can invert this to measure fo(r)) This leads to the following family of approximate majorizing surrogate, indexed by (x, B) E 12d
1-
g(3'; x, 9) := fo(2g) + fo(z)) T Va (x, (3' - 3) + 11, 3 s (16)
This family of approximate surrogates can also be used in Algorithm 1. Of course, it performance depends on the quality of the estimator fo().. also requires separate analysis, which will use the following bounds on the bias and the variance of fo(r), proved in Appendix H.1.
Lemma (Bias and variance of dueling gradient estimator). Under Assumptions A to D) let fo( be defined as in (14) with a 1/8, m d log(d/eo)/ed) b bx d/să. and so/d. Then:
V fo(z)] fo(x))l S Eo. and EE fo())) V fo) X =/.
In the next section, we provide the results on the iteration complexity of Algorithm with first-order feedback (Theorem 10) and ducling feedback (Theorem 1)).
8

---

Algorithm 2 Approximation of preference gradient with dueling feedback
Input: decision vector x, weights 3, clipping threshold o, precision 7, number of batches b, batch size m, and a comparison oracle (z1, 22) satisfying (15)
1: Sample unit vector in IRd uniformly at random, U, Unif(5d-1) for each E [b]
2: Query comparison oracle for Yu Y (x + yU;, yU;) for each (ž, [b] [m]
3: Compute clipped Bernoulli parameter estimators for each E [b] and the gradient estimator:
1 Σ
d
A < CLIP (a.1aa
Yo
and
fo(z)
(f.)
U.
(14)
27
JE(m
iE
where CLIP (p) is the projection of p into the interval (a, 1 - al. 4: return fo(x)
7 Convergence Analysis
We establish the convergence rate of Algorithm in terms of the convergence guarantees of its two black-box optimizers: one for the surrogate g( : x. (3) and another for the scalarized objective fa(-)- For our convergence results, assume that the optimizers achieve the guarantees:
Assumption (Black-box optimizers), Let 3 and &g be the approximate solutions that are returned by the black-box optimizers for g( ;x, B) and f((() in (9) of Algorithm 1:
B + arg min ( ix, B)
and
& f- arg min fz(2).
SrEA--1
meRd
We assume that there constants C1 Cg such that:
1. the approximate minimizer 3 is 0( aaproximaaely stationary:
43' En-1
vg(3,, 3) 5 Se ar -oll.3" - -31l2
2. the approximate minimizer it is an -aprrxiitt solution:
|V [ S .2.
Theorem 10 (Convergence of PMM with first-order feedback). Suppose that and fo satisfy Assumptions A to C, and that the black-box optimizers satisfy Assumption Fix e1/2 < ED Let (Ik, Bx)b be the iterates of Algorithm I using the family of surrogates (13). There exist eı (f F) and cf, F') bounded away from zero and a stopping time K such that (foor*) (3x) monotonically decreasing for k E [K] and (IX,3a) is an (Eo. E) >>eeeeernncce stationary point. Furthermore:
24g (5 (J) KS
.
where f == max fo(z) and f. = min fo(x) are optimized over the compact set Parcto F).
Proof sketch. We use a standard approach and show that every iteration, either we have converged to an preffereee stationary point and can stop, we can find way to improve the preference by (( To do so, we require the optimizer for the surrogate g to also achieve O(Eg) aaprroxiio stationarity, which is enough to achieve an
- -pproxxiiil optimal point (Lemmas G.4 and G.5);
(3; xr B) g(3"; x. B) + (
where 9 minimizes the surrogate. The surrogate contains an approximation error crrv (8, x). this error term ((=2), then it is possible for the surrogate to fail to either (i) decide that the current iterate 3 is Eo eo-prefernnce stationary (ii) make progress by finding some 3 that certifiably improves on fo. We preclude this by requiring the optimizer for fa to achieve -(piiaoptimallty.
The full proof of Theorem 10 is in Appendix G.

---

PNG
PMM
0.4
0.0
322
32
0.2
0.1
0.3 0.4
0.0 1.5
-1.3 -0.5
1.0
Figure 2: Visualization of learning dynamics for two Pureto-constrained optimization problems; Algorithm (PMM) is in orange, and the existing method (PNG) introduced by Ye and Liu (2022) in blue. In both cases, the dynamics begin at the black dot. The ground truth preference-optimal solution, found by exhaustive search, marked by black square. The boundary of the Pareto set of F is colored white. The preference function fo visualized by the heatmap and contour lines. All objectives and preferences are strongly-convex quadratics. See Appendix for details.
Remark 1. Algorithm I makes calls to sub-routines at each iteration to solve two sub-problems. As the problems are strongly-convex and Lipschitz-smooth, they can be solved using (projected) gradient descent with iteration complexity O(log(L/Eo)) And so, taking the computational cost of the sub-problems into account only increases the rate obtained in Theorem 10 by logarithmic factors.
Theorem 11 (Convergence of PMM with dueling feedback). In addition to the assumptions of Theorem 10, suppose that the link function satisfies Assumption D. Let the family of approximate surrogates (16) be constructed by Algorithm with input parameters (a, Y, b, m) that are specified by Lemma 9. Let (Ik, Bx)s be the iterates Algorithm I using this family of surrogates. There is stopping time K such that [E[(Jo o x² (Bx)) is monotonically decreasing for l E
and (IK, ( an (Eo, e) --prefeerncce stationary point in expectation, i.e., VVV./ fag (x ll2 S E, and conditions (a)
and (b) of Lemma 7 hold in expectation for (x 3x). Moreover, K =0 (cp) (00))
The complete theorem statement and its proof are given in Appendix H.2.
ensuring its applicability to large-scale problems. However, under dueling feedback, achieve the rate in Theorem 11, m and b needs to be conension-dependee al., 2021). One might expect dependent on 4. d under more informative dueling feedback, e.g. preferences between 3 vectors rather than x. Exploring such strategies is left for future work.
Remark 2. The rate obtained in Theorem 10 ciimension-iddeenee
which unavoidable (Wang et al., 2023; Chen et al., 2025a; Saha
8 Conclusion
In this work, we provide a principled and efficient way to select a decision vector from the Pareto set of set of objectives f1, fi...., fu given additional preference function fu- The primary motivation to seek the most preferred solution from a large model like LLM that is pretrained to satisfy a number of desiderata. notion of (approximate) preference stationarity. This is non-trivial due to the non-smoothness and non-convexity of the Pareto set. We achieve this by reformulating the constraint set the Pareto manifold instead of the Pareto set. We also provide a simple algorithm that achieves ao-approximate stationarity with iteration complexity of ((E 2), under both first-order and dueling feedback.
main contribution of this work is to provide
wanetricalll-meannnne
There are several promising directions for future research. For example, extending this work to nonconvex significantly more challenging. Another impactful direction is incorporating deter- ministic dueling feedback to enhance practical applicability. A high-dimensional setup, where not only the decision vector nigh-dimensional, but the number of objectives f1, '2, Sn are allowed to increase with the problem scale, will also be quite interesting explore.
10

---

Acknowledgments and Disclosure of Funding
The research is partially supported by the NSF award CCF-2112665 (TILOS). is also supported in part by the U.S. Department of Energy, the Office of Science, DARPA AIE FoundSci, as well as CDC-RFA-FT-23-066 from the CDC's Center for Forecasting and Outbreak Analyties.
References
A. Agarwal, O. Dekel, and L.. Xiao. Optimal algorithms for online convex optimization with multi-point bandit feedback. In Coll. pages 28-40. Citeseer, 2010.
A. Agresti. Categorical data analysis, volume 792. John Wiley & Sons, 2012.
F. Bach and V. Perchet. Highly-smooth zero-th order online optimization. In Conference on Learning Theory, pages 257-283. PMLR, 2016.
H. P. Benson. Optimization over efficient set. Journal of Mathematical Analysis and Applications. 98(2): 562-580, 1984.
Bolintinéanu. Minimization of quasi-concave function over efficient set. Mathematical Programmingg 61:89 110, 1993a.
S. Bolintinéanu. Necessary conditions for nonlinear suboptimization over the weakly-efficient set. Journal of optimizatiin Theory and Applications, 78(3):579-55) 1993b.
H. Bonnel and J. Morgan. Semivectorial bilevel optimization problem: penalty approach. Journal of Optimization Theory and Applications, 131:365-388 2006.
A. Bradley and Terry. Rank analysis of incomplete block designs: The method of paired comparisons. Biometrika, 3933/44), 1952.
H. Cai, D. McKenzie, W. Yin, and Z. Zhang. A one-bit, comparison-basee gradient estimator. Applied and Computational Harmonic Analysis, 60:242-266, 2022.
D. Chen, Y. Chen, A. Rege, Z. Wang, and R. K. Vinayak. Pal: Sample-efficient personalized reward modeling for pluralistic alignment. The 13th International Conference on Learning Representations, 2025a.
Chen, Q. Xiao, F. H. Fukuda, Chen, Yuan, and T. Chen. Efficient first-order optimization on Pareto set for multi-objective learning under preference guidance. In International Conference on Machine Leaming. PMLR, 2025b.
P. Dauer. Optimization over efficient set using an active constraint approach. Zeitschrift, für Operations Rexearch, 35: 18:185,, 1991.
S. Dempe. Bilevel optimization: theory, algorithus and applications, volume TU Bergakademie Freiberg, Fakultät Mathematik und Informatik. 2018.
N. Ding. Y. Qin, G. Yang, F. Wei, Z. Yang. Y. Su, S. Hu, Y. Chen, C.-M. Chan, W. Chen, J. Yi, W. Zhao, X. Wang. Z. Liu, H.-T. Zheng, J. Chen, Y. Liu, J. Tang, J. Li, and M. Sun. Parameter-effeiiet fine-tuning of large-scale pre-trained language models. Nature Machine Intelligence, 5(3):220 235, 2023.
A. L. Dontchev and R. T. Rockafellar, Implicit functions and solution mappings, volume 543. Springer, 2009,
M. Ehrgott. Multicriteria optimization,, volume 491. Springer Science Business Media, 2005.
J. Fliege, L. G. Drummond, and B. F. Svaiter. Newton's 's method for multiohjective optimization. SIAM Journal on Optimizaaioon, 20(2):602-666, 2009.
J. Fülöp. On the equivalence between a lincar bilevel programming problem and lincar optimization over the efficient set. Techn. Rep. WP, pages 93-1, 1993.
I. Glohus-Harris, M. Kearns, and A. Roth. An algorithmic framework for bias bounties. In Proceedings of the 2022 ACM Conference on Fairness, Accountability and Transparency, pages 110--124, 2022.
A. P. Guerreiro, C. M. Fonseca, and L. Paquete. The hypervolume indicator: Computational problems and algorithms. ACM Comput. Surv., 54(6), 2021.
N. Haghtalab, M. Jordan, and E. Zhao. On-demand sampling: Learning optimally from multiple distributions. Advances in Neural Information Processing Systems, 35:406 419, 2022.
N. Hamada, K. Hayano, S. Ichiki, Y. Kabata, and Teramoto. Topology Pareto sets strongly convex problems. SIAM Journal on Optimization, 30(3):2659-28)) 2020.
C. Hillermeier. Generalized homotopy approach multiobjective optimization. Journal of Optimization Theory and Applications, 110())557 583575887,-40 2001a.
C. Hillermeier. The Manifold of Stationary Points, pages 65- 86. Birkhäuser Basel, Basel, 2001b. ISBN 978-3-0348 8280-4, doi: 10. 1007/00077730000 3-34888---38-----80 3-0338-8280-4.5

---

N. Houlsby, A. Giurgiu. S. Jastrzebski. B. Morrone, Q. De Laroussilbe. A. Gesmundo. M. Attariyan, and S. Gelly. Parameter-efficiett transfer learning for NLP. In International Conference Machine Learning, pages 2790-2799. PMLR, 2019.
Z. Huang, J. Li. S. M. Siniscalchi, L.F. Chen, J. Wu, and C.-H. Lee, Rapid adaptation for deep neural networks through multi-task learning. In Sixteenth Annual Conference of the International Speech Communication Association, 2015.
C.-L. Hwang and A. S. M. Masud. Multiple objective decision wuking-methood and applications: a state-of- the-art survey, volume 164. Springer Science & Business Media, 2012.
K. G. Jamieson, Nowak, and Recht. Query complexity of derivative- free optimization. Advances in Neural Information Processing Systems, 25, 2012.
Y. Jin. Multi-ohjective machine learning, volume 16. Springer Science & Business Media, 2007.
M. Jordan, G. Kornowski, T. Lin, Shamir, and M. Zampetakis. Deterministic nonsmooth nonconvex optimization. In The Thirty Sixth Annual Conference on Learning Theory, pages 4570-4597. PMLR, 2023.
M. M. Kamani, R. Forsati, J. Z. Wang. and M. Mahdavi. Pareto efficient faimess in supervised learning: From extraction to tracing. arXiv preprint 104Kv:2204.011333 634, 2021.
K. Kobayashi, N. Hamada, A. Sannai, A. Tanaka, K. Bannai, and M. Sugiyama. Bézier simplex fitting: Describing Pareto fronts of simplicial problems with small samples in multi-objective optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 2304-2313, 2019.
G. Kornowkk and O. Shamir. Oracle complexity in nonsmooth nonconvex optimization. Advances in Neural Information Processing Systems, 34:324-334, 2021.
G. Komowski, S. Padmanabhan, and O. Shamir. On the hardness of mcaningful local guarantees in nonsmooth nonconvex optimization. arXiv preprint urXiv:2409. 10323, 2024.
A. Kulkarni, M. Kohns, M. Bortz, K.-H. Küfer, and H. Hasse. Regularities of pareto sets in low-dimensional practical multi-eriteria optimisation problems: analysis, explanation, and exploitation. Optimization and Engineering, pages 1 22, 2022.
W. G. La Cava. Optimizing fairess tradeoffs in machine learning with multiobjective meta-models. arXiv preprint XXXv:2304.12190 2023.
K. Lange, R. Hunter, and I. Yang. Optimization transfer using surrogate objective functions. Journal of computational and graphical statistics, 9(I)1120, 2000.
D. Lee, G. Noarov, M. Pai, and A. Roth. Online minimax multiobjective optimization: Multicalibeating and other applications. Advances in Neural Information Processing Systems, 15:29051--2066 2022.
J. Li, A. M.-C. So, and W.-K. Ma. Understanding notions of stationarity in nonsmooth optimization: A guided tour of various constructions of subdifferential for nonsmooth functions. IEEE Signal P Processing Magazine, 37(5):18 31, 2020.
X. Lin, H.-L. Zhen Z. Li, Q.- Zhang, and S. Kwong. Pareto multi-task learning. In Advances in Neural Information Processing Systems, volume 32, 2019.
X. Lin, X. Zhang, Z. Yang. F. Liu, Z. Wang, and Q Zhang, Smooth tchebycheff' scalarization for multi-objective optimization. arXiv preprint arXiv:2402. 19078, 2024.
H. Liu, D. Tam, M. Muqeeth, J. Mohta. T. Huang, M. Bansal, and C. A. Raffel. Few-shot srrameter-efficienn
fine-tuning is better and cheaper than in-context learning. Advances in Neural Information Processing Systems, 35:1950- 1950-1965, 2022.
X. Liu, X. Tong, and Q. Liu. Profiling Pareto front with multi-objective Stein variational gradient descent. In Advances in Neurul Information Processing Systems, volume 34, pages 14721-14733, 2021.
Liu and M. Ehrgott. Primal and dual algorithms for optimization over the efficient set. Optimization, 67(10): 1661- 1666, 2018.
D. Mahapatra and V. Rajan, Multi-task learning with user preferences: Gradient descent with controlled ascent in Pareto optimization. In International Conference on Machine Learning, pages 6597-6607. PMLR, 2020.
N. Martinez, M. Bertran, and G. Sapiro. Minimax Pareto fairness: A multi objective perspective. In International Conference on Machine Learning, pages 6755-6764. PMLR, 2020.
N. Marumo, T. Okuno, and A. Takeda. Majorization-minine minimization baaaaiiatttt----edddddee Levenberg Marquardt method for constrained nonlinear least squares. Computational Optimization and Applications, pages 1-42, 2023.
I. Marusciac. On Fritz John type optimality criterion in multi-objective optimization. Mathematica Revue d' a'analyse numérique de théorie de l'appreximation. L'analyse numérique la théorie de l'approximation. pages 109-114 14, 1982.
J. A. Nelder and R. W. Wedderburn. Generalized linear models. Journal of the Royal Statistical Society Series A: Statistics in Society, 135(3):370-335 384, 1972.
12

---

Y. Nesterov. Introductory lectures convex optimization: A busic course. volume 87. Springer Science & Business Media, 2003.
Y. Nesterov. Gradient methods for minimizing composite functions. Mathematical programming, 140(1):
125-161, 161,161,112 161,,115 2013.
Nunnally and I. Bernstein. Psychometric Theory (Third Edition). McGraw Hill, Inc., New York, 1994.
C. H. Papadimitriou and M. Yannakakis. On the approximability of trade-off's and optimal access of web sources. In Proceedings st annual symposium foundations of computer science, pages 86-92 92. IEEE, 2000.
J. Philip. Algorithms for the vector maximization problem. Mathematical programming. 2:207- 1972.
V. C. Raykar, S. Yu, L. H. Zhao, G. H. Valadez, C. Florin, L. Bogoni, and L. Moy. Learning from crowds. Journal of machine learning research, 11(4), 2010.
S. Reed, K. Zolna, E. Parisotto, S. G. Colmenarejo, A. Novikov, G. Barth-Maron, M. Gimenez, Y. Sulsky, J. Kay, J. T. Springenberg, et al. A generalist agent. arXiv preprint arXiv:2205.061 266720675, 2022.
A. Roy, G. So, and Y.AA. Ma. Optimization on Pareto sets: On theory of multi-objective optimization. arXiv preprint arXiv:2308.0000 0tl::2308.0211555/ 021vv1, 2023.
A. Saha, Koren, and Y. Mansour. Ducling convex optimization. In International Conference on Machine Learning, pages 9245-9254, PMLR, 2021.
A. Saha, T. Koren, and Y. Mansour. Ducling convex optimization for general preferences: An unified framework for optimal convergence
International Conference on Machine Learning, 2025.
O. Sener and V. Koltun, Multi-task learning as multi-objective optimization. Advances in newral information processing systems, 31, 2018.
H. Sheftel, O. Shoval, A. Mayo, U. Alon. The geometry of Pareto front biological phenotype space. Ecology and evolution, 3(6):1471-14B; 2013.
Smale. Global analysis and economics I: Pareto optimum and generalization of Morse theory. In Dynamical systems, pages 531-544. Elsevier, 1973.
M. Spivak. Calculus manifolds: modern approuch to classical theorems of advanced calculus. CRC press. 2018.
R. E. Steuer. The Tchebycheff procedure of interactive multiple objective programming. In Multiple criteria decision making and risk andyysis using microcomputers, pages 235-249. Springer, 1989.
D. Tao et Numerical solution for optimization over the efficient set by de optimization algorithms. Operations Research Letters, 19(3):117-1)))
1996.
P. Thach, H. Konno, and D. Yokota. Dual approach minimization the set of Pareto-optimal solutions. Journal of optimization theory and applications, 88:689-707, 1996.
C. Tosh and D. Hsu. Simple and ocar-optimal algorithms for hidden stratification and multi-grow learning, In International Conference on Machine Learning, pages 21633-21657, PMLR, 2022.
Wang, Q. Liu, and C. Jin. RLHF more difficult than standard RL.2 theoretical perspective. Advances in Neural Information Processing Systems, (6676666-7602,, 2023.
Yamamoto. Optimization over the efficient set: overview. Journal of Global Optimization, 22:285-317, 2002.
F. Ye, B. Lin, Z. Yue, P. Guo, Q. Xiao, and Y. Zhang. Multi-objective meta learning. Advances in Neural Information Processing Systems, 14:21333--21351 2021.
M. Ye and Q Liu, Pareto navigation gradient descent: a first-order algorithm for optimization in Pareto set. In Uncertainty in Artificial Intelligence, pages 2246-2255. PMLR, 2022.
J. Zhang, H. Lin, S. Jegelka, S. Sra, and Jadbabaie. Complexity of finding stationary points of nonconvex nonsmooth functions. International Conference on Machine Learning, pages 11173-11182, PMLR, 2020.
B. Zhu, M. Jordan, and J. Jiao. Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. In International Conference Machine Learning, pages
PMLR, 2023.
D. M. Ziegler, N. Stiennon, J. Wu, T. B. Brown, A. Radford, D. Amodei, P. Christiano, and G. Irving. Fine-tuning language models from human preferences. arXiv preprint 1909 1909 1909.08999 2019.
13

---

A
Notation
Symbol
Usage
the (n simmipx equipped with the mmmmtri
A --11 {3 I2" Eie(n] B; = 1 and E [n]] 8, 2 0] the set of B3 satisfying VSz = 0, (17)
A (a)
Vx, Vz
derivative of the map x" and its approximation, (4), (10)
eTTV (),
bound on the approximation error of V o x*), Lemma E.6
F, (f........n) fo fa(ø) 3 k L, LH. Lo Mo. Mi.
the set of objective functions the preference function the scalarized objective (.f((2)).
majorizing surrogate for f(x3)) (12) condition number K == L/p for V Assumption A
Lipschitz parameters for Vfi fi and V Assumptions A, B, C
Lipschitz parameters for x² and Vx*, Lemma E.2
μ
strong convexity parameter for fi, see Assumption strong convexity parameter M1 for the surrogate (12)
Pg
FF)
the set of Pareto optimal solutions of F, Definition distance between the minimizers of [1, 11..... Sn. Assumption the Pareto manifold, Definition 3
PFF)
diam (Pareto (F)) := sup {|| 2212 x, x' E Pareto(F)). Lemma E.
x² (B), Zg
stationary point for fa. (3)
link function for comparison oracle, (15)
14

---

B Proofs for Section 3
Lemma 1. Let F (a) be a collection of smooth and strictly convex objectives. Then: (z, B) P(F) for some 3 A
Pareto(F)
Proof. The condition on the left states that x is Pareto optimal. The one on the right states that æ is Pareto stationary. When the objectives smooth and strongly convex, Pareto optimality and Pareto stationarity are equivalent (Theorem 3.1, Fliege et al. (2009)).
Proposition (Characterization of the Pareto manifold). Let F = (J1,...; be a collection of smooth and strictly convex objectives. Define x' - Pareto(F) by:
= 2 == arg min fa(x))
(3)
Let FF()) Ianxd be the Jacobian. Then, the map x² has derivative:
V (())==v\/((c))>AA//PG
so that the map B (I (3 a diffeomorphism of n~ with the Pareto manifold P(F).
Proof. The map x² is well-defined because fa is strongly convex- is the convex combination of strongly convex objectives, so it has a unique minimizer. And as the objectives are smooth, the stationarity condition fz) = 0 uniquely holds at (3))
Vfa(z;) =
Define the map ()r (0), and which be parametrized by simplex - via the map + (I,,
ffs(). Then, the Pareto manifold is precisely the zero set P(F)
In fact, a smooth parametrization. To see this, we apply the implicit function theorem (Theo- rem B.1), which states that the map x² is smooth at B when VzC( is invertible. Indeed, have that is continuously differentiable, with:
V2((x,
Σ 3E(m]
3. vzfa(z),
V)((x, V
Σ (V VF(T).
iEIn]
As fa is strictly convex, it has positive definite Hessian, that det ( 3) + O. Furthermore, Theorem B.1 also implies that the derivative Vx* is given by Equation (4), It follows that the map 3 (Iz, 3) is smooth. It also has smooth inverse. Namely, the projection onto the second component (Ig, 3) + B. Thus, P(F) is diffeomorphic with An-1
Theorem B.1 (Implicit function theorem, Spivak (2018)). Let f Rd R" + +Rd be continuously differentiable on an open set containing (a,, b) and let f(a, b) = Let V.J(u, v) be the x matrix:
(u,( 1) -uy.liuu
If det V. (a, + O. there are open sets U C. Rd and V C. RR" containing and b respectively with the following property: for each u E there is a unique g(v) such that f(g(v), v) Furthermore, the map g is differentiable with derivative given by:
Vg(e) -VV[= V..
15

---

Figure 3: An embedding the Pareto manifold from (1) into three dimensions from two camera angles. The singularity seen in (1) is artifact of the projection of the manifold into the decision space, rather than an intrinsic irregularity in the manifold.
16

---

C A comparison of solution concepts
In this section, we elaborate on the relationship between different solution concepts (optimality, stationarity, approximate stationarity) for the Pareto-constrained optimization problem:
minimize (fo x: (3). 9Ea
(6)
The solution concepts are related by:
preference
preference stationariy
weak preference stationarity
approximate preference stationariy
optimality
It is fairly clear that the first and last inequalities are strict. We discuss the inner inequality.
It turns out that point can be weakly preference stationary without being preference station- ary. However, this can only happen if x is also a point of singularity in Pareto F). Geometri- cally, we consider Pareto(F) as the projection of P(F) onto its first component in R the this means that multiple points are collapsed onto Algebraically, this means that the set of gradients V V (z),
fn (z) fails to have full (Pareto) rank (Smale, 1973; Hamada et al., 2020).
To elaborate, define the set:
A (-) = { A-11 (fa(2) 0).
(17)
Then, is Pareto stationary if there is some 3 in A 10 (x). that:
Σ AVf(() 0, iE(n]
and the rank of this set of gradients is at most n - 1. Since An does not contain any collinear
vectors, A (x) contains more than a single point, then the rank of the gradients must be strictly less than n 1. This leads us to the definition:
Definition C.1 (Pareto genericity). Let (UI,..., Un C CR.. This set is Pareto generic if:
fii1 +...+ Bn Un O, for some B A=
and the non-degeneracy condition holds: rank(u Un) =
If F(x) is Pareto generic, then (x) contains unique 8, so we immediately have: Proposition C.1 (Weak and strong preference stationarity). When the set of gradients Fz(x) is Pareto generic and is weakly preference stationary. then z is preference stationary.
However, when the gradients Fx))) are not Pareto generic, then weak preference stationarity can be strictly weaker. Let (x, B) where A n- (z)) be weakly preference stationary, so that:
[f(=)) T
V [[() - B)) S S0,
VB' E-
(a)
We can simplify this by using the fact that Vfs(r) = FF = 0. Then, one way for the stationary condition to be fulfilled is for the underlined term to normal to (f()))
(=)())) 3' E span (ofa))))()))
v3' V --1
This statement has the following geometric interpretation. These vectors contained in the Clarke tangent cone of Parcto(F) F) at æ. If these are the only vectors in the tangent cone, then this condition states that fo(x) contained in the normal cone of Pareto(F)) at a.
But, in general, the tangent cone contains the union of subspaces:
U
(-V' 3' : 8'EA-11)
BEA" (())
And so, when (x) does contain a unique vector, the tangent cone can contain more vectors. By selecting different J's, we recover different slices of the tangent cone. This also means that even if the above normality condition holds for one 3, it may fail to hold for another 3 E A An-1(x), Then, (z, B) is weakly preference stationary while (z, () may not be.
17

---

D Insufficiency of first-order information
The notion of preference stationarity uses second-order information F, for the term V Vafa(2)-1 A natural question is whether there are reasonable notions of stationarity that only use first-order information. turns out there are none, if we require the stationarity condition be (i) non-trivial, (ii) necessary for preference optimality and (iii) decidable from local information at a single point
The reason is that from (zz) alone, Pareto manifold. is not enough to determine locally how the manifold curves. For example, (4) shows different Pareto sets that share the same gradients with respect to fo depends on its neighboring Pareto points. It turns out that to attain a non-trivial and necessary condition, we would either need look at higher-order information, or first-order information at more than a one point.
only determine whether the point is contained in the
point The local optimality of
To formalize this, we define stationarity conditions as decision functions. These are functions that return Boolean outcomes true or false (we interpret these functions as ways of classifying points as stationary not). In particular, given only the gradients V fo and f.,...,, fn, at a single point:
consider first-order stationary conditions, which makes decisions
Definition D.1 (Stationarity function), first-order stationary condition is decision funcction whose input is tuple of n + vectors in Rd:
1+ rimes
Stationary: Rdd X
R2 {true, false).
Let fo be smooth preference function and f1...., fn be smooth, strongly convex objectives. We say that a first-order condition necessary if the following holds:
x is preference optimal
Stationar(VVfo(r).... Vnn(z)) true.
There specific cases in which it is possible determine that decision is not preference optimal from first-order information. First, if x is not even Pareto optimal, then it cannot be preference optimal. This occurs whenever fa + 0 for all B E A--1, The second case occurs if is Pareto optimal, but fo( is in the convex cone spanned by the columns of VF(x),
ff(())
Σ Ai(),, where A 0. iE(n)
In particular, let zg. Then, let [0,1] + n be the curve parametrized by >(t)
tA + t)3. Then whenever (f((z)) + 0:
(o(=)(((01)
= Vo(l -A-
t=
= VVVVlta)VVV/((tt>>>VV>>>>>
<.
Intuitively, these solutions are not preference optimal because we can find more preferable Pareto solutions by weighting those objectives that align with fo more. To exclude these specific cases, we introduce the notion of preference genericity. Then, Proposition D.1 shows that any necessary, first-order stationary condition must accept all preference generic sets.
Definition D.2 (Preference genericity). Let {no. 01,..., Un C Rd where 1 < n. S d. This set is
preference generic if there exists some 3 A n-1 such that 9iv1 ........ ".. 0, and:
vp & span(c)...., Uw)
Proposition D.1 (Necessary first-order conditions are trivial), IfStationary is a nicsssary,fisttooree stationary condition, then it is trivial in the following sense:
Stationary(Vo Un) = true,
for any preference generic set of vo..... Un dR...
Proof. It suffices to show that there exist fo. F, and xt such that x' is preference optimal and for i 0.....7. n nE
2 vx(x")
(18)
18

---

Figure Two instances of Pareto fi, f2) are shown (thick gray lines), where fi and f2 are positive-definite quadratic objectives in R² (visualized by contour lines). At z (the black dot). the instances share the same local information - (f) and V (2x) (orange arrows); they cross the contour lines at right angles. When n = 2, the Pareto set contains all z such that fi and r does not minimize fo over TR? then cannot be stationary for both instances.
(2)) for À 2 Notice that if fo is strictly convex
And since x* is preference optimal, any necessary stationary condition must accept:
Stationary(Uo,..... Un) = true.
Without loss of generality, let x² 0 by affine transformation. To construct fo and F, we can simply consider family of positive-defintt quadraties:
Let the preference function fo be:
fo(x) = =2 | + voll?
Notice that fa(= up.
Let the objectives fi...., fo share the same Hessian:
f((x) マ
A|( 11
2;)11?
where A Iddd is full rank and 2, Rdd Let H A for short.
We show that we can set A and the 2;'s es's so that x² is preference optimal while (18) holds.
By Lemma D.I, the Pareto set is the convex hull C conv 2n). Notice that the choice of H and rs's determines the z s, since we require (z(xx") = Ui which expands to:
H
Us.
Vi E [n]]
From convex optimization, x² = is preference optimal if (i) x² e C and (ii) is normal to V.fo. Indeed, these conditions can be fulfilled:
(i) Because 01,..., Un is assumed to be Pareto generic, zero is a convex combination of the v, 's. As the 2, are related the v, by a linear transformation, this also implies that zero is a convex combination of the 2 's (with the same set of convex weights).
iii) We need to show that the subspace span span(U2...... Un) can be mapped into span(u))* by the map - -H v where H is positive definite. Lemma D.2 shows that such map H exists long as vu & span(V1. U1,.................. vn). which is assumed from preference genericity.
Thus, there exists fo and F that is preference optimal xx with matching first-order information. necessary stationary condition must therefore be accepted.
Remark D.1. Suppose that Stationary is not necessary, but that can design some optimization method that provably converges a stationary point in {a: Stationary(x)) true). Then, there are settings in which the method provably avoids preference optimal points.
19

---

In the remainder of this section, we prove Lemma D.1 and Lemma D.2 used above.
Lemma D.I. Let f1...., fn R2d IR be positive-defiiite quadratics with a shared Hessian:
f((x) 2 Al -1)(=,
2
where A Rddd is full rank and 2 E Rd. Then, the Pareto set is the convex hull:
Pareto(S1,..... fn) conv(21,........)
Proof. As the objectives f1,...; fn are strongly convex, optimality is equivalent to stationarity. Thus, E Parcto(f1. fn) if and only if there exists some B E A such that:
3, f((z), REin]
which, when expanded, states that:
(A A)æ = (ATA) Σ
3:2
iE(n]
But as invertible, this is equivalent to:
8
kE(n)
which is to say that x E conv(21,..... zn)-
Lemma D.2. Let U and V be linear subspuces TR. such that U n V =0). Then, there exists some positive definite map H Rd + RR such that HU) C.V.
Proof. S C Rd is a subspace, let IIs Rd + RRd be the projection onto Define the map:
H := Ily + Il 1g.1
Then Il satisfies the following:
H is positive definite. To this, let 0 * Rdd have decomposition x1 22,, where
21 E U and E U-_ Then:
x Hr x. Ilvar 2x 1lv22 + x2llyw + o. yy 02 + x. 1ly
x
Flve
x TTIly 1ly
1
+ क 02 +
| 2 2
[[ + x2l1
where the last inequality is strict because x + 0 and U n V- {0}.
H(U) c V. If e U, then by definition Ily so that Hr IIvr E V.
D.1 An example of a first-order stationarity condition avoiding optimality
In this section, we discuss the first-order stationarity condition of Ye and Liu (2022), defined to as stationarity with respect their optimization dynamics, Pareto navigating grudient descent (PNG). We show that it fails to be necessary condition for preference optimality.
Despite that, their condition and dynamics have appealing properties since (i) they do not require second-order information, which is computationally more expensive, and (ii) their dynamics largely satisfies what they call the Pareto improvement property, which ensures that each objective enjoys monotonic improvement during optimization:
Ji f((x)) So. O, for all i E [m]]
As Pareto improvement can at odds with preference optimality, this leads to an open question: when and how should we balance Pareto improvement with preference optimality?
20

---

Definition D.3 (PNG stationarity, Ye and Liu (2022)), Lete > 0. The PNG vector (2(2) is defined:
(x(2)) = arg min
fo()) - ul?
VER* 2
Vf(()) c, for all i [n]. s.t.
Let E > O. vector x E Rd is (c,E)-PNG stationary if vo( = (V for some X S 0 and: min BEA
[V]a(()]| =e.
In the following, we consider an example R² with n objectives. Let the standard basis be denoted e1, E IR? and let the objective functions /2 IR2 + R be defined:
fi (x)) = - || + e1)l
and
(2(x) - | - e )l1
(19)
where A E 2R is full-rank. Lemma D.1 shows that the Pareto set of the objectives Pareto( f2) the line segment from -e to e2. Thus, the Pareto set invariant under change in A, while PNG stationarity is not, as the constraint set changes with A:
{u: (a ea) He cf n (o: e1) Hu 2 2c),
and = A Due to this discrepancy, PNG stationary points can be preference suboptimal. Example D.1. Let the preference function be: fo(æ) H|(= e2 and let the objectives fi, fa be defined as the above (19) with:
AT
(20)
Then, the unique preference optimal point is the origin O. However, the (c, EN- stationary point is bounded away from 0. It even converges e₁ the error tolerance goes
Proof. Consider the PNG vector (z(x) when x is in the region:
C = { E R² fo(x) Vfi(a) < 0, for i = 1, n [
Here, both constraints ff()) 2 c are active in the constrained optimization problem that defines the PNG vector; and so, (z(x) is the vertex point of the constraint set, satisfying:
(T2(a))T.(a)) =c
Expanding out the gradients, obtain:
(x e1) (v)())== and
(x (1- Huc(x)) =c
This implies that e, Hvy(x) = O. Now suppose that TPNG E is PNG stationary. Then, by definition, must satisfy V fo(TPNG) E
has the form:
FPNG =2 + Au, where e, Hu 0. 0.
Whenever the standard basis vectors are not eigenvectors of H. the line e2 + Au intersects Pareto(Si, /2) away from 0. For example, let A satisfy (20).
Then, the line e2 + Au runs through e₁ and eg. We can verify that C contains all points on this line between its two endpoints. When e2 X(e ez) and X E (0, 1), we have:
fo(()) (Vf()) (r 02) H( (x+ +1)
and similarly, we have: A(e1 - 02) T H ((1 + A)01 + (1-A)oz) - -)),
Vo(x))Tff() = (s 02) H(r - 01)
= x o2) T H (() 1) - -2)) = A)..
This implies that for all 0 and converging to e₁ as e goes to zero.
0, the (c. ) stationary point is bounded away from 0,
This example is visualized in Figure 2.
21

---

E Proofs for Section 5
In this section, we derive the following implications from the assumptions from Section 5:
Assumption allows us to bound the size of the Pareto set (Lemma E.
Assumption additionally bounds the curvature of the Pareto manifold: we show that Vz is well-behaved (Lemma E.2) and well-approximated by Vx (Lemma E.5).
Assumption C further leads to error bounds when approximating gradient of foox* (Lemmaa E.6). It also allows us to define a notion of approximate preference stationarity that is geometrically meaningful (Proposition 6) and can be verified using approximate information (Lemma 7).
Let's recall from Assumption A that the condition number of the objectives V fa for E [r]] is upper bounded by k L/μ. We also defined the scale parameter r as the maximum distance between any of the minimizers of the objectives:
max 5.jmmml
arg min f((x) arg min fz(2))12
Lemma E.1 (Size of Pareto set). Let F satisfy Assumption A. Then R S vKr, where:
diam (Pareto(F)) = sup {1|= x' ll2 x, Pareto(F))
Proof. Because each Si is p-strongly convex and L-Lipschitz smooth, so is the convex combination Js. This implies the upper and lower bounds:
Σ KE(N)
s
S L Σ
B1112
-x,12
2 aE(n]
It follows that the minimizer of ʃe is bounded:
fa(zø) S L.².
On the other hand, if point || - x,|| >> 2s for some i [n]., then by reverse triangle inequality, || - 2; > for all j E [m]. This implies that:
1
| ri|l > 2s
fa(x) 7 jus.
follows that if |z 24|| > 2/ L/p for some then a Pareto optimal point.
Lemma E.2 (Smoothness of x²). Let F satisfy Assumptions A.B. Then, x² : A n-1 Rd is Mo-Lipschitz continuous and has M1 -ipiiischttz continuous gradients, where:
Mo = kR
and
M1 = 2x. R LHR
Proof of Lemma E.2 That x² is Lipschitz continuous with Lipschitz continuous gradients follows from the following two lemmas:
Lemma E.3. Let F = (fi....,hy fn) be set of twice-differentiable objectives and let fo be smooth preference. Suppose the objectives are L-Lipschitz smooth and y-sttrongyy convex:
V2 LI.
Let R diam (Pareto(F)). Then, the map x² (A"-1,E)) (TRd,62) is p-/pshiish
Proof. Recall from (4) that Vz) = -V 1 (zz Then:
(2))())
(2 - VF(a,) 11.2
(0)
LRR.
where (i) is property of the || noom,, (ii uses μ 3 f2 and Lemma G.I.
22

---

Lemma E.4. Let 3' E A= Then,
2L2R 112
1 (1+-1) LuR) 113 - 1811.
V (B) Vx Vx'(8')112 S
Proof. By definition, have:
(3* Vx Vz' 11, = (3 (VF(xa)) (VF())) 1
We can add and subtract (fflzz))-VVP- (x inside the right- hand side (RHS):
v2 (a(a)) [V((=)) ()F()))-V((79)) [
( V (2(()))))
(F(Tg))
(RHS)
We can bound the two terms in the norm separately. For the first:
( L
(6) -
L S 4
- f3(xz)) -VF()))VV((()))
I 1
|| 81
where (i) follows the same argument as Lemma E.5, and (ii) applies Lemma E.3. For the second term, can add and subtract V fer - )J
(z
to obtain:
VF(2z)) 11,,2 f((x)))) -- (z
= =1[
+ v fo(
for --foocc))----oo(ooo VF(xg)
L B'111
Lu LR || - 8111 LR.
112 1
where V - (z) is bounded by Lemma G.3; is bounded by Lemma G.I.
is bounded
by Lemma G.2 and Lemma E.3; ) |1,2
The result follows by substituting in the definitions of My and M,. Lemma E.5 (Approximabilliy of Vxx). If satisfies Assumptions A,B. Then:
Vz (B) Vx (z. S p 2Mo
My [Vo(=))
Proof. Recall that T3 == x (B). Then, by definition, we have:
(-1 ( "1,,,-
We can add and subtract V - )zz33) T inside the right-hand side (RHS) to get:
(RHS) = (z(xx)) [F(xx) - "> (V'
vF(xs)
L || - zaol + LH
|| | LR
422
(0)
(1 1+ 1
L
LHR L [x))
where (i) the first blue term uses μuI f and the T--Lipschizz smoothness the objectives, while the bracket orange term follows from Lemma G.2 and the final purple term follows from Lemma G.I. and (ii) uses the f--ttoogg convexity of fg.
Lemma F.6 (Approximability of V(Jo oz)). F, So satisfy Assumptions A,B,C C. Then:
[V (z)) Vfo(z) (z. 31 I (r,
where (x,
[[(( Lo [V
2
23

---

Proof. Add and subtract ff(()) ( Vr within the norm on the right-hane hand side:
(RHS) = (V V/((r)) Vx (3)
+ Vx*(3)+
Voola) (V=* Vx (x, (w.
1 M1 [
$ LoMooloag - + μ. 2MM
where we use the fact that fo Lo- Lo-Liipehitz smooth by Assumption C, that -i-Lipschiz continuous by Lemma E.2, and that || V (B) V (3)1222 2 is bounded by Lemma E.5. The result follows from upper bounding |2 z|| by p-strong convexity of fø:
| - xl - [Vfa()]]|-
Proposition (Geometric meaning of approximate stationarity). Les (i,, 9) be (co, -oreee-eeeeeen stationary. With Assumptions A,B,C, and R = diam (Pareto(F)) and s == 2 (Ly then:
(a) 1 B111 S then fo(zg) fo(zz) 2 -2co11B Bl11, and
(b) || - rzll2 S e/μ-
Proof. (a) Recall that Ty is the minimizer of Sa. by definition. Because Sa is μ-strongly convex, bound the distance between x and 25 by:
|| xpهl - [Vfa(t)] E
jr'
where the second inequality follows from condition (8a).
(b) Let 3, (1 - s)B s3' parametrize the line connecting 3 and 8'. Let [0, 1] - Pareto(F) be the path (s) = x (8.), so that:
dr(s) - Vx -x=))) (3.)(0) B) ds.
We can now upper bound the difference:
fo(xs) - fo(xx)
v volkE.) ds(ss
/ (Vo((x), V(o((R) + [io(za)] d7(s)
< f Lollxo, 2oll(d>(ss) + / (- (oo(z))) dd(()).
Let's bound the integrals separately. Since 2z, = S dr(ss 3), have by Lemma E.3:
LR
1|:9 x <
|13 11'11
1
We also have [dy(s)] < p 1 - - by Lemma E.3. The first integral is bounded by:
[ Lollze. x [d>(s)) < /'
L RR
L. R2
1 1
B sds =
||B - 117
2 41
For the second integral, first note that condition (8b) implies:
(o((xa)ddr(s) = - (o(o))) V=" V (xs) -3) < 30 - 88 el11
yielding the other bound:
1 (- (io(oa)
sol1 8'11 111161 ds soll3 -313-111111. (
3'112-
24

---

Putting these two together. we obtain:
1
fo(xs) Fo(x _
|1B - 3-11 + =ollB 8'11
2
11²
It follows that if we restrict ||3 - 1'111 S
24 LgL one of the factors of ||, 3'1l1 in the first
term can be absorbed into the constant, proving the result:
fo(#z) S fo(x + 20al - 3'111
Lemma' 7 (Verifiability of approximate stationarity). Under Assumptions A,B,C, the point (é, 3) is ( preefernce stationary if [ (+) S e, and for some x E TR. and a E (0, 1),
(a) Eo-approximate stationary condition holds for all B² An-1:
-Vfo(z) Vxx (a, B)(3' B) a Bl|
(11)
(b) an error bound holds: s (B, S (1-a) - So. where:
M1
[/((a)] ToMo) [VVs(())].
erry So = 1 2M
and Mo kR, M1 = 2x T. R/R).
Proof. For -preferncee stationarity, we require [V]](l)] S and:
V 3) + 5 || ||1 2 0.
Then by Lemma E.6, the left-hand side is lower bounded:
fo(x)) ((lx))aa (z, (3'
B) - errv,,
(8, x) 18 111 + Eoll3' B11
[ (8' - B) + su 61ll8' - -Bll2
(1 a)) 3 B||1 err fo (3,z) 118" B111.
for a E (0, 1). The two terms are lower bounded by zero by conditions (1) and (2).
25

---

Proofs for Section 6
Proposition (A family of majorizing surrogates). Let F and fo satisfy Assumptions A,B,C. Let fo (a, be as defined in Lemina E.6. Define the family indexed by (x, 3) E IR x An-1:
g(B'; a. 3) = fo(2g) + Vfo(z) T (x, (3 - -3 + + 313 f (13)
where Hy == nLoM1. Then g(8"; z, 3) majorizes fo a xx, satisfying (12).
Proof. As fo and x² respectively Lg- and M1 Mi-Liccchitz smooth (Assumption C and Lemma E.5), their composition is Lo smooth, and so it admits the standard quadratic upper bound (e.g., Lemma 1.2.3, Nesterov (2003)):
fo(#)') - fo( + Vio o x²) n -
where have used | BIR nl| 313 This could be an easy choice for majoriz- ing surrogate g but the gradient V(fo o oz) is implicit. Substituting in the approximation
v fo(x) Vx (x, 3) yields the result, where the error term comes from Lemma E.6.
L
26

---

G
Convergence for Pareto majoriration-iiniiizattoo
Theorem 10 (Convergence of PMM with first-order feedback). Suppose that F and fo satisfy Assumptions A to C, and that the black-box optimizers satisfy Assumption E. Fix 0 el/2 S Eu 1. Let (Ik, Bk l be the iterates of Algorithm using the family of surrogates (13). There exist 01 (1 F)
and coloo F) bounded away from and a stopping time K such that (fnox*) (3x) is monotonically decreasing for k E [K] and (IK,8r is an (Eo, è) >-preference stationary point. Furthermore:
K 2pg f.)
where f max fo(æ)) and f. min fo( optimized the compact Pareto F)-
Proof. Fix k > For short, we let:
(x, B) = 3k-1) and
(G, (Irk, Bk)-
Claim. At each iteration, either (i) the preference improves by at least constant:
1 C1 Fg
fo(0z) fo(z)) S
or (ii) the point (é, 3) (ea, e) -rrrfeeeee stationary.
Assuming the claim holds, the theorem immediately follows: if the algorithm in K steps has not found an (Eo, E) prefereece stationary point, then the value fo(*,,) must decrease every iteration by a constant. But because fo o x² is lower bounded over A n-1 by f", this can happen at most:
2pg (s- f.) of -
times.
Proof of the claim. Let 8* arg gin x,, 3). Lemma G.4 shows that approximate stationary point / of strongly convex function is close to the exact point (
|| 3
C1
(21)
Hg
where we let denote this constant for short.
We can analyze & through 3*, There are two cases, leading to either (1) ( -rrfferrreeeeeceeeee stationarity or (2) ((=e)-constant descent. The two cases depend on the suboptimality of 3.
Case 1: || B||2 26. Here, B is fairly close the optimum 8 of the surrogate. We show
that the approximate stationarity of 3 with respect the surrogate implies approximate preference stationarity. We do so via Lemma 7, which states that (#, 8) is (5o, -ppeeerree stationary provided:
[Vfa(t)l22 5e
(22)
1
-Vf(()) (3' 3)
2
-0 311.
VB' A-11
(23)
1
crTV to (z, 3)
2 Eu
(24)
While (22) is immediate from our choice of cz. defined in the last section the proof, the others do not follow automatically from approximate stationarity with respect to the surrogate: the surrogate is
derived from local information at (ar, B), while we would like guarantees at (xx B3. But because 3 is close to both 8 and B, control all of these. By triangle inequality:
|| 3112 ||
3-112 + 1| -||2 35,
(25)
27

---

( combining (21) and the assumption that ||5" -B122 < 26.
We now show (23). We have for all 3' EA"11
-VJo(z) (x, (3' 3)
( 2 - V Vz (z, 3) - B) + [Vf(()) (Vx' (x, (1)ll)))l -113* - B112
I.
CEE 11,3 -B B11 +
||3 B||2 11,8' - -B112
/2
(00)
2 C180 LIVVo(=)]2
36
-1188 311
(26)
1
((v) 1 5 20 113' B111,
where (i) adds and subtracts Vf((z) Vx (x, (3)
3) and applies Hölder's inequality, (ii) sub- stitutes in Condition 1 for the first term and bounds the second via Lemma G.3, and (ii) bounds || - B|12 using (25), and (iv) applies the definition of set in the last section of the proof.
To show (24), we have:
(2. B) 1 cITV fo (x,
M1
[f((())l2 LoMo)) (IV.f((=)12--IV4 [+f(()))
1
2Mo
(i)
Mi
fIT fo (1, +
[| + Mo ||VF(>) 1l2 11 B|12
2M,
(68)
1
M
|
fo((() + LoMM) (02s + (|V[+())
36
(27)
2
2M
((v)
W E0
where (i) expands out c (ii) uses the fact that 3 with respect to the éo-nomm, (iii) applies the definition of err fo and the incquality (25), and (iv) follows by definition of C1 and 02, set in the last section of the proof.
[VF(2) B112 is
in
As (22, 23, 24) hold, Lemma 7 shows that (á, B) is (co, prreferrne stationary.
Case 2: ||8- 107--ppp -B12 2 28. Here is suboptimal and 8 achieves large descent:
fo(#x=) - fo(z)) S g(3";2, 9) - fo(2z)
1
f (x, (3)
Σ 5 -3112
(H))
Mi
S 2M,
[fo(2)]l2 + Lo c2c 22
(28)
(iv)
2 n'002
(29)
where (i) uses the majorizing property of g, (ii) follows from Lemma G.5, (iii) applies the definition of errv fo (x, 3) and the assumption that S E/ and (iv) uses the definition of c2.
The large descent also carries over to 9 because is approximately stationary:
fo(zz) - fo(xs) S g(6;z, B) fo(rz)
g(3 B) - fo(xx) + (g(3; x, B) g0
(w)) 3
2 ugg + c100 8 = 1 c1 20
1lg
28

---

where (i) uses the majorizing property of (ii) adds and subtracts ,(,"; B) and (iii) applies (29) and Lemma G.4.
Thus, the preference improves by at least a constant. To finish proving the claim, we need to verify that it is indeed possible er and appropriately.
Setting ej and e2: we tabled few inequalities above. Recall: For (22), we need:
C2 S 1.
For (26), we need:
2 C150 + 3L [o(())12
C160
S Eo.
4
Mg
For (27), we need:
M
[u(xx)] +LoM) {OSE {o25+3IIVP(z)) +3IVP(())
CiC0
112
S ED.
MM
Mgg
For (28), we need:
M1 [o(z))ll + Lolb) oz S 2/4 M4
C1ED
2.
unenlightening but straightforward to verify that it suffices to set:
C1 max
2
Vo(x)ll
12
(
Mi
[Vfo(x)]22 Lo
1IVF(x)
2M,
2
M1 [V Lo
(2v My of
} S1,
C2 max
1,
2M
where Vb::= max(a, b).
concerned reader may wonder whether e₁ and c2 may be bounded away from zero, as claimed in the theorem statement: we need to ensure that ff((z)]l and F[)) l|e do not blow up. Indeed, this holds because the iterates dy remain within a constant distance the Pareto set. particular, since < 1, by Condition 2, we have that the kth iterate satisfies:
2 - -
which follows from p-strong convexity of fa.- Thus, all iterates of the algorithm are within ε/μ of the Pareto set and also satisfy for all k, k E N:
|| oy || = R + 25/p.
Then, by Lo-Lipschitz smoothness, we can bound:
[o)(()) < fo((( + [V(x( Vf((z)) fo(z)) + Lu + 20/H).
(30)
Similarly, by L-Lipschitz smoothness, we also have:
FVF(2) 1 S [VF IVV((s)) VF(a1) ll2
< VV + nL. (R + 22/1))
(31)
G.1 A bound on the gradient
Lemma G.I. Let = diam diam(Pareto(F))) Then for any F3 = x (8),
VF(xs)) 11 11 < T.R.
29

---

Proof. By definition, we have:
VF(x))
Σ v f((zz)
sup ||=|| -1
sup
|z [[sig((z))
(f((z))ll
|| =1 iE|m]
V (V l
:E(n]
(682) IA
max
L|| - -;,l2;
[E(2]
where (i) follows from Jensen's 's inequality, (ii) holds because the max is no smaller than the average, (iii) applies L-Lipschitz smoothness. In particular, let 2; arg min fix),, that Vf,(),) = 0. Then:
[( (2( S L| z2ll2- The result holds because u and all x, is are contained in Pareto(F)) F).
G.1.1 Lemmas: matrix inverses
Lemma G.2. Let M Rd + Raxd be L-Lipschitz satisfying M(x) & put where Rd has the by-norm and paaxd the operator norm. Then, the map x ++ Mxx) is T./ p.
Proof. For short, let us denote (z) by Mg. Note that I (M² + M2 M,) that:
M M M M (M + M M2)
M M M (M, M M - (M, M..)
which series of unenlightening algebraic manipulations. But now, we may apply I--Lipschitz continuity to obtain MM M S L| a - æ'|| and the y-lower bound to obtain ||M M|, s p_1 Together, we obtain L/ 21,2-Lipschhtz continuity:
L f1l I'll
[|M MMx'
Lemma G.3. Let M be positive-defintte matrices in Rdxd equipped with the operator norm, and let A n be equipped with the & norm. Suppose the following holds:
μ M M T.I.
The map 3 + Mq' where M3 = Exe(n) 3rM, has bounded derivative || V 11,2 S L/12.
Proof. We can compute the derivative of the above map:
Vg M3 (V)
where yaMad3 = Mag. The upper bound on the M,'s implies that | S L. On the other hand, the lower bound implies that || 1 ||2 S μ
G.1.2 Lemmas: constrained optimization of strongly convex functions
Lemma G.4. Let R R be smooth and convex and let C R be convex constraint set. Suppose that 8* B C are stationary and e-approximately stationary, respectively:
VT (8 (²)) s and
VS(OT 3) s elIB - .1,. 49 E C.
Then, (18))((83)) < =11, 1) Furthermore, if is p-strongly convex, then ||@ - 33 S e/U
30

---

Proof. For the first part, we apply the mean value theorem, which states that there exists some 5 that is a convex combination of B and 13* such that:
1(3)- VB
3r) < VB())((B 8*)
(80
(0) =|1 B-
where (i) applies the mean value theorem, (ii) uses the monotonicity of gradients of convex functions:
(V/(3) VS(3) (B 3) 2
and that 3 2(3 3*)) for some [0, 1], and (iii) applies the E-stationarity condition.
For the second part, by strong convexity, we have on the one hand:
(vf(i) v)())) (3 3r) 2 w11 18
And the other, by stationarity and E-stationarity, have that:
(v)(3) - vf(()) (8 8*) 2 1*
Dividing through by ||3 - || yields the result.
Lemma G.S. Let C C IR be conver constraint set with 3 E C, and let Q C - R be a quadratic:
Q(3) c
3) - -
C1B' - -113, 2
(32)
where e IR U. E R", and 0. Let 3 E C minimize Q. 1111 - B11 2 e> 0, then:
Q(8") Q(3) Cea.
Proof. Define the quadratic function RR IR by:
((A) c Ao ToT(6S (8* - 3) + Cx B11
2
c 2 311= -1
2X*)
(33)
(8" -11 minimizes Restricting Q to the line between 3 and 3*, we get:
where
+ Q(3+1(8 - 3)) = ={A);
for À E [0, 1]. This follows by expanding the definition Q.
Notice that monotonically decreases on the interval < X S X*, and also that g monotonically
increases for À > X Because Q(3)) q(1) minimizes Q on the convex set C, q must be descending
on À E [0, 1]. Thus, S X² It follows that 1 - 2X* < -1 Plugging in into (33), we have:
Q(3") = (1) < CII 3112.
2
Applying Q(3)) = cnd ||8 - -b 2 = yields the result.
31

---

H Proofs for Dueling Feedback
H.1 Proof of Lemma
Lemma (Bias and variance of dueling gradient estimator). Under Assumptions A to D. let V Vo(()) be defined as in (14) with a 1/8, m dt log(d/eo)/Ei) bx d/ and so/d. Then:
[B[}]o(>>] - (o(x))l2 X EO:
and
E [[IV[[(())
[ - c
Before proving Lemma 9, we first need the following lemma. Lemma H.1. Let Assumption D true. Then, we have,
E 10 (0) - v 4 2m + 8² + (exp (-2m(1 - 1/11²) exp (-2m(1/uu -/))) L2 a1a u 13).
Proof. We will omit the subscripts and write pi, pi = th -)E(m)) Yijs Patyuna as D, D, p when there is no confusion. Consider the following three events.
1. For some constants u, I > 1, define event Es = [a<p<l-all/<<<< such that a > 1/u, and a < 1/l.
2. Fi = ( 2 1 - a 1 1 1/11)
3. Eg = (p < 1/u < p 1/1).
By Hoeffding's inequality, we have,
P(E)) 2 exp 1-2m(1 - a - 1/1)²) exp (-2m(1/u - aa)3) P(E2) exp 2m
1/()²), P(Es) S exp (-2m(1/u--)))
(34)
Let = p - p. Let the event Ei be true. Then we have p = p. and
-o- (p) o (p) s Lo Cvll
where C. =(1 all-a) + (11) For sufficiently small max(p a, 0--pppppp p) > B> 0, consider
the event, E1 [1/ > B E1}.
P(Ea) < exp( exp(-2m182)
P(F()
Then, since |u| < 2,
E [ Fi] < exp( 22m1
+ 132
(35)
P(Ez)
Under Eg,
0 ( 0 d1)] < - pl S To Cala - -1
(36)
Under Esg
(0) - -v)) < LoColp pl S Lo
(37)
Combining (34), (35), (36), and (37), we obtain,
2(1o-100-00
<P (P(E)) P(Es)) L2C (1-1-al² +|a 11)
(4xp((2mm83) + 3²
+ (exp (-2m(1 - a - 1/1)²) + exp (-2m(1/u- - x1})) 13,03 (11 - -al2 la - u -11).
32

---

Proof of Lemma 9. Since Algorithm ensures that 24 are contained in a compact set, Assumption C
implies that || foll2 I G for some constant G observed (30).*
Then, fo(x + Tu4) fo(x ru)) _ Gy implying Patruna--uu I u, where,
u ( By Lipschitz continuity of (-), using o(0) 1/2, and y S 1/(4L))), we have, (1.u) (4/3, 4). First we look at the bias of (or))
= a (-
and
(38)
V fo())]
d
(Potru.o-ru) u4 u4- - -- (PetTu.
27b
1=1
d
+
E
(Pettu..--nu) Vfo(z)
276
i=1
d
(2 12exp((mol
+ 2L Ca expmmm666)) + 3Lydy
27
d(3 + CB)
+ 3Lody
2y
SczEo:
where C3 > is a constant. The first inequality follows by triangle inequality, the second inequality follows by Lemma H.1. Section 3 of Agarwal et al. (2010), and choosing a = ğ. and the third inequality follows by choosing m max (1/3², 64) log(1/ (), the fourth inequality follows by choosing 3 = 7², and the fifth inequality follows by choosing 7 = e d. Note that with these choice of a, u, one has Ca is bounded by constant 27.
Now consider the variance term.
E
V fo(x)
ff(())
d E
<2E
fo(
1- (Pot-m.-
27
d
+ 2E
27
d
<2E
V
fo))
E
+ 6Lzd2g2
2
2d b
E
(pott.m -0 -- -0
2b
d²
b
+
Var (a -1 (prttmaa-mm))) + 6II.dPg2
212
1=1
201²
72 22 (4exp( 1 2mm + B2 + C2 exp (-m/32))
1zd2222 2 + 2T
Gdd+
b
20 (5 + I.,02,
72 b
Gdd Lzddq² + 6L2ddR2
72
"To be precise, in the dueling feedback case, since we do know fo(2)) we need to make mild assumption that there at least one point 3i E where is some compact set containing Pareto (FF) such that V (x.))) < B where B% > 0 is constant. Then the algorithm can always be initiated at x = 24 and the V (x( remain uniformly bounded as per (30). This is mild assumption because if the gradient is large everywhere. then the problem itself becomes meaningless to study. For all practical purposes, can assume ||V foll, G.
33

---

where the first inequality follows by Young's inequality, the second inequality follows by Section of Agarwal al. (2010), the third inequality follows by Young's 's and Cauchy Schwarz inequality, the fourth inequality follows by Lemma H.I, Lemma 2 of Bach and Perchet (2016), and choosing 8 the fifth inequality follows by choosing m max (1/B², //2 64) log(1/3), B), and the seventh inequality follows by choosing b d/eg. 3 72, and 7 Ea/ d.
H.2 Proof of Theorem 11
We expand Theorem here.
Theorem H.1 (Convergence of PMM with Dueling Feedback). Let F. fo. and satisfy Assump- tions A, B, and D. Fix < e I ED S 1. Let ã and be the approximate solutions that are returned by the black-bo box optimizer for 9 (1';30 (3) and fe(-). defined in (13) and (2), respectively:
- arg min 3(8 3x, 8'EA--1
and
Rg - arg min f/((x).
sERd
Given constants C1, > 0, suppose the black-box optimizer achieves the following guarantees:
1. the approximate minimizer 3 is (0E00((()pppooi) approximately stationary:
-V(0; (5' B) S c1 -uul B112.
AB' An-1
2. the approximate minimizer its is an -apprxippoox solution:
[Vg((s)]] C2
Let (Ik, B&)k be the iterates of Algorithm / with dueling feedback. Then, choosing 1/8. m = dt log(d/eo)/et,
x d/ and x /e/dd in (14), there exist eı (fo, and c2(fo, F) bounded away from zero and some K such that Bi(fo x= (Bx)) is monotonically decreasing for k [K] and (x 3x) is an (Eo, -ppreference stationary point in expectation, i.e., |/V sax (xx) S e, and conditions (a) and (b) of Lemma 7 hold in expectation for (Ix, .K)) In particular, have the following.
E| V(oV T ( 3k)] s
2 Folls - 3kil1
VB' E E
(X-1,,)) < Eu
Also.
K < 2pg (f* f.)
Proof of Theorem 11 Fix l: >> For short, let:
(a, 3) (0t- 1x-11) and
Claim. At each iteration, either (i) the preference improves by at least constant on expectation:
C1
[)fo(x)) - fo(2x)) <
2 jg
or (ii) the point (0, () is (Eu, e) prerfeerneeee stationary expectation.
Assuming the claim holds, the theorem immediately follows: if the algorithm in K steps has not found an (Co, -reeferree stationary point, then [[, must decrease every iteration by constant. But fo x= is lower bounded over - by f*, on expectation, this can happen at most:
2p (f* f.))
times.
2 E
34

---

Proof of the claim. Let 3" == arg s'a- , 5), and 3 := arg ming'ea-- 0(3'; B).
Lemma G.4 shows that an approximate stationary point of strongly convex function close to the exact point 3":
|13 - 3 S
C150 =: 6,
(39)
Mg
where we let 5 denote this constant for short. Since g(8; x. (3) a strongly convex function and simplex is compact convex set, by tilt stability of solution mapping of strongly convex functions (see Proposition 2G.4 of Dontchev and Rockafellar (2009)), we have,
8- 8r S (Vf6(z) (f(())) (1) -
Mo [
(40)
Hg
The last inequality follows by Lemma E.2.
There are two cases, leading to either (1) (so)) -preference stationarity or (2) O(e)) -constant descent. The two cases depend on the suboptimality of B.
Case 1: 3 < 28. Here, 8 fairly close to the optimum 3 of the true surrogate. We show that
approximate stationarity of 3 with respect to the noisy surrogate implies approximate expected preference stationarity. Similar to Theorem 10, (.,3) is expected (5o, -)-pffernnnce stationary provided:
[V/b(0)]lz S c E (z", 3)]
(41)
50ll13 -111
AB' E-11
(42)
E Elerrv (2; B] < 2
(43)
Observe that,
Mn
||3 - 118-1112 - ||3 3*112 + 113" - -B-112 + +1 - -B112 < 38 +
[)(()) Vl((a) (44)
Mg
combining (39), (40), and the condition that 118-111 < 25.
Note that (41) follows trivially by Condition of Theorem H.l. One can efficiently find such with log(1/Eo) iteration complexity as just requires optimizing a strongly-convex objective over compact convex set.
Now we show (42). We have the following bound.
T (3, -B) V0(8; x, 2) -3) 9)) + My B, - B)
Scie0 1|8' -8]1 + Ug (133 8011, 11, +1135 - -/0111- + 113 - -112) 10000-800 8|1,
< C1ED (c180+30
Mo (5((z) - v[o(o) (1)) 118- -811-
+160++0 +35
(45)
Hg
The equality follows by the definition of g. The first inequality follows by Condition 1 of Theorem 11, triangle inequality, and Holder's inequality. The second inequality follows by (39), (40), and by the condition ||3" B112 28 in Case 1.
35

---

Now, for all 8 E A we have,
V[(cz) Vx (r (z, - 3)
(9)
I Vx 3)(8' (1 - (x, 11/3 - -111
(4)
V/6(+) Vx () - +)+ + Mo Vo(()) - Vfo(2) 1 2 - $11
+1VV6(()) (V= (z, B) V2 (a. 8> 1118' B1l1
(00
Mo ff(()) 7 118 B|11 + Mo [fo(z) -1 811
9150 + 3
M9
L
+ +|[VSo(z)]l2
3| B1|2 118' - 3111
112
(10)
C150 + (1+
2 ( ) 38 + Mo
1
L (V p2p0
- 113' -111
+ 1+
Mg
(46)
where (i) adds and subtracts V fo(x) (x, - and applies Hölder's inequality, (ii) follows
by adding and subtracting [z) Vz (z, (3' B). Lemma E.2, Holder's inequality, and the fact that || S ||,r||>] (iii) follows by (45), Lemma E.2, and Lemma G.3, and (iv) bounds ||,3 - -1112
using (25), and (iv) follows by (44). Taking conditional expectation both sides, using Lemma and Cauchy- Schwarz inequality, we get,
E
Vf(lz)
( Vx (z, B)(88 - B3) 12,8
L c9.0 + (1+ [1 902 0gMB
(2+1+
L
2 $ (B|1 (117)) [V
1ig 1221g
| $11
Taking expectation on both sides and by the definition of c1, and observing
s 2, we have,
E Va (z. B)( })] s E B111)
To show (43), we have:
errv fo (x,
1
Mi
[f(())]22 + LoMo) (1V52(=))la -
crrV (I,
/
2M
(10)
1
M1
S e (z, B) +
[[oo))) - LoMMo
|VF(()) lle 11.3 - B112
/
2.
(aa)
1 2 Mi
[u((x)] + Lo.Mo) (ooE+
Mo
[ - V(6(o)) [IFF())
38 +
2 P 2M
Hg
(47)
where (i) expands out errv (ii) uses the fact that 3 [VF()) 3112 is [IVF()) [ -ipppsschtz in with respect to the fz-norm, and (iii) applies the definition of errv and (44). Taking conditional expectation on both sides, and by Lemma 9,
E errv 1o (2. Jc, 3
1 2 Mi + [225 + 35
(0ss+
caMoo
|VFF())]l2
2 μ
2M
Mo
Taking expectation on both sides, and by definitions of ci and c2, we have,
errv (z. 3)] S 2 E0.
1
E
36

---

Case 2: 118 8112 2 26. Here 3 is suboptimal and 8 achieves a large descent. Akin to (29), we have,
- fo((z)) - - 22g02
(48)
Now we have,
Jo(xz)) - So(x;)
,(B:2z, 2, (] ff(0z)
= g(8";,,, x2, 3) fo(zz) + (g(3;x, 8) g xr, + - 2z,
(0) 3
20 + Vo(3;x, (3 Br) He 3 3012
(())
3)+ nn vg(3;2, (B - (vfo(z) - Violat) (x, Br)
3
2
+ Hg
8 8*
2
2
(6v)
3
Px (100)) |1 3 -811
3r 8-11 + v/600))
2 ug00 0100
+ 4g
8r 8r
2
(0) 3 u88 c1E08 +
Mpō [fo(z) vf(())
Mb (odla)-Vo(s)))
+ 2/1
Ug
where (i) uses the majorizing property of g. (ii) applies (48), and strong convexity of g(; 22, 99. (iii) follows from the definition of (( B), (iv) follows from Hölder's inequality, and choice of Ct, (V) follows by (39), (40), and Lemma F.2.
Taking conditional expectation on both sides, using Lemma 9
[[)( - fo((z) 1 z2 + +c1500 + caMrdEo
Mg
2/1
Taking expectation on both sides,
Modo
23 M&
[[)((r)) fo(#z)] < - nu + c100 +
Mg
2/1g
Observe that, choosing parameters properly Lemma 9, we can always ensure
C3 S (uin)//et/(5M)),c//1122
Then, have,
B[fo(rg) - fo( < -
Thus, expectation, the preference improves by at least a constant. The choices of ei and e2 follows similarly as in Theorem 10.
37

---

I Details to Visualization of Toy Examples
Figure visualizes learning dynamics for two different Pareto-constrained optimization problems. The code can be found at https: / thw.thb..tt.ee/te///////gg com/ ttwp./o/ppeeeeeeeeeeeeeeeeee pareto.
Preference optimization on non-smooth Pareto set The left sub-figure an example of optimization on the Pareto set described in Example 1. In particular, the preference function is:
0.35
0.2 0.75
Fu( - 2 (x vo) 0.35
(x vo)
and
Hyperparameters used using the PNG algorithm by Ye and Liu (2022) include the Pareto-set approxi- mation threshold 0.001, learning rate = 0.01, and regularization parameter aı = 0.01. These were not particularly tuned. The two different phases in the algorithm can be clearly observed the dynamics. In particular, when the iterates are close the Pareto set, the PNG dynamies minimizes fo- Otherwise, it aims to move toward the Pareto set in a direction that also optimizes the preference. This leads the jagged appearance of the PNG dynamics. We 40k iterations.
The PMM algorithm visualize in this example alternates between updating 2 and 3x. Each update step for 3% is implemented by approximate gradient descent, making of Vx followed by projection back onto the simplex. The learning rate for 3 chosen here was 0.1. Then, the update step for Σą. consists of single step of gradient descent få, with learning rate of 0.1. A total of 1500 iterations was run. These hyperparameters were not specifically tuned.
Preference optimization where first-order information is insufficient The right sub-figure visualizes the counterexample given in Example D.1.
The PNG algorithm in this example used parameters = 0.001, 5 0.1, and 0.01. We ran the algorithm for 26k iterations. The PMM algorithm in this example is the same as the previous example. The learning rate chosen here was 0.1. The inner loop used I step of gradient descent with learning rate of 0.1. We ran 1500 iterations and did not attempt to tune hyperparameters.
38

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Abstract and introduction clearly states our main result with explicit rate. As this is a theoretical paper, this summarizes our main contribution.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We mention after Theorem 10 that dimension dpeendence in the dueling feedbak setting unavoidable. Also our work is for strongly convex objectives.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
39

---

Answer:
[Yes]
Justification:
All the assumptions are in the main body. Proof' are mostly in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: The code is contained in the supplementary materials and httpps//g/h thub. com/ www.eeloooppeeeeeeeeeeeee
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
40

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
Seeii//guides//oeeeuuue www.isiiiiooooliiiooooooooooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results, See the NeurIPS code and data submission guidelines (https:
wttpp.cccpubbll...pp ccc/publcc/ga /tcc///gi///////// seeess/ooeSubbbii sorbmissiii wwwsssolisogooooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: No experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: NO experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
41

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: No esperiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: / http://eeeiiscceee http///rrrrp..c.pooo/ttttctteeee
Answer: [Yes]
Justification: We abide by all the rules.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Even though this is theoretical work, we mention the introduction about the possible applications nad their implications of our framework.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
42

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
No data or model used.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Yes.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com/ com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
43

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: NA.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: NA.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [No]
Justification:
No such participant.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
44

---

Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [No]
Justification: No.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer our LLM policy (https: (nttts::/nnerrppppstst / for what should or should not be described.
45


Reviews:
[{"review_id": "50vrUHH3qh", "reviewer": "Reviewer_H4W1", "summary": "This paper studies the problem of selecting the pareto optimal solutions among potential many candidates for multi-objective optimization. The authors formulate the problem as Pareto-constrained optimization to optimize a preference function constrained to a set of Pareto optimal solutions.  Subsequently, the authors propose a reformulation of the problem where the constraint set is redefined in terms of an appropriately defined manifold, which allows the authors to introduce an algorithm with a last-iterate convergence rate of $O\\left(K^{-1 / 2}\\right)$ to stationarity under strong assumptions.", "questions": "1. Given the strong assumptions (A, B, C), Can the authors provide concrete examples that meet these assumptions so that people who read the paper can better understand these assumptions? Without these, it is difficult to understand how practical of these problems? For example, Assumption A itself excludes lots of practical settings, such as the Portfolio optimization problem mentioned in the motivating examples, which has a linear objective: Let $f_1(x)$ be the expected return, where $f(x)=\\sum_{i=1}^n r_i x_i$\nLet $f_2(x)$ be the expected risk, where $f_xx)=\\sum_{i=1}^n \\sum_{j=1}^n \\sigma_{i j} x_i x_j$\n\n2. Can the authors provide a concrete example of $f_0(x)$? As a potential user of the proposed Pareto majorization-minimization algorithm, one needs to have a sense of when and how to cast the problem into the preference setting of this paper. For example, the authors mention that in fairness-aware learning,  $f_0$ is the social welfare function; In neural architecture search, $f_0$ can be a user-specific preference reflecting trade-offs (e.g., prioritizing low latency). Can the authors mathematically formulate them? \n\n3. The authors mention that the primary motivation is to seek the most preferred solution from a large model like LLM that is retrained to satisfy a number of objectives. However, I doubt that these objectives, if any, behind the pre-training of any LLMs satisfy the assumptions (e.g., strongly convex, smooth, etc) in the paper. I'd like to see to what extent these settings and theoretical results resonate with the motivations.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\nThe paper studies a practical problem of selecting the pareto optimal solutions among potential many candidates.  The authors proposed Pareto Majorization-Minimization Algorithm with theoritical guarantees under restricted assumptions that converges to an ( $\\varepsilon_0, \\varepsilon$ )-approximate preference stationary point of Pareto-constrained optimizationwith iteration complexity $O\\left(\\varepsilon_0^{-2}\\right)$.\n\nWeaknesses\n\nMy major comments on the weaknesses of the paper are about the practicality of the settings (e.g., assumptions). Specially, \n\n1. Given the strong assumptions (A, B, C), Can the authors provide concrete examples that meet these assumptions so that people who read the paper can better understand these assumptions? Without these, it is difficult to understand how practical of these problems? For example, Assumption A itself excludes lots of practical settings, such as the Portfolio optimization problem mentioned in the motivating examples, which has a linear objective.\n\n2. Can the authors provide a concrete example of $f_0(x)$? As a potential user of the proposed Pareto majorization-minimization algorithm, one needs to have a sense of when and how to cast the problem into the preference setting of this paper. For example, the authors mention that in fairness-aware learning,  $f_0$ is the social welfare function; In neural architecture search, $f_0$ can be a user-specific preference reflecting trade-offs (e.g., prioritizing low latency). Can the authors mathematically formulate them? \n\n3. The authors mention that the primary motivation is to seek the most preferred solution from a large model like LLM that is retrained to satisfy a number of objectives. However, I doubt that these objectives, if any, behind the pre-training of any LLMs satisfy the assumptions (e.g., strongly convex, smooth, etc) in the paper. I'd like to see to what extent these settings and theoretical results resonate with the motivations.", "was_revised": true, "final_justification": "I will raise my score to 4. Thanks for the answers to my questions, especially those examples in 1 & 2. While I appreciate the ongoing work for extending the theories from convex to non-convex, I can not raise my score to 5 as the primary motivation is to seek the most preferred solution from a large model like LLM that is pretrained to satisfy many desiderata and the theory is not about that thus far.", "rebuttal": "Thank you to Reviewer H4W1 for taking the time to review and for the detailed feedback. It seems that the reviewer found the problem we study well-motivated, but is mainly concerned about the practicality of the setting we study theoretically. We address this first, and more specific concerns below.\n\n**Main contributions: theoretical vs. practical**\n\nWe agree that this work’s main contributions are theoretical, although practical problems such as LLM fine-tuning serves as a key motivation for our framework. But, in developing a principled approach, we found the problem to be highly non-trivial due to the non-convexity, non-smoothness, and the implicit nature of the constraint set (even when the objectives are simply quadratics). We greatly simplify the problem conceptually.\n\nPrior to our work, there were only heuristics for this problem. The literature lacked a proper definition of stationarity and algorithms with provable behavior. Actually, intuitive heuristics easily go wrong. We proved that there is a large class of very natural stationary conditions—including one in existing literature, and another we had initially considered—that will *reject* the true preference-optimal solution. Practically, this means that the prior algorithm in literature *provably avoids* the correct solution, even in the strongly convex setting!\n\nIn contrast, our work is the first to establish a well-justified solution concept that is efficiently and provably achieved by a simple algorithm, under two forms of feedback. The issue of practicality, especially in the context of LLM fine-tuning, is certainly a valid one. But, we believe that our work already makes a significant and meaningful contribution to the literature, and that it provides a solid theoretical foundation upon which to develop algorithms that work under less restrictive conditions, and that are more sample and computationally efficient.\n\n\n**Question 1: concrete examples of objectives**\n\n*Portfolio optimization*\n\nLet $x=[x_1, x_2, \\cdots, x_n]^\\top$ and let $\\Sigma\\in\\mathbb{R}^{n\\times n}\\succ \\mu I$ ($\\mu>0$), i.e.,  $\\Sigma$ is positive definite.\n\nConsider the objectives: uncertainty regularized expected return $f_a(x)=-\\sum_{i}r_ix_i+ x^\\top \\Sigma x$  (In your notation $-f_1+f_2$, the minus sign is needed as we are minimizing)[1], and the quadratic transaction cost $f_b(x)=\\|x-x_p\\|_2^2$ [2,3]. $\\nabla^2 f_a(x)=\\Sigma\\succ \\mu I$, and $\\nabla^2 f_b(x)=I\\succ I $.\n \nThen, the norm of Σ is bounded as $\\sigma_{ij}$ are constants. Since, $\\nabla^2 f_a(x),\\nabla^2 f_b(x)$ are constants it satisfies Assumption B. Since Assumption C is on $f_0$, we address it in our answer to your Q2.\n\n*Classification with sub-populations*\n\nConsider classification using regularized logistic regression where the population has $k$ subpopulations, i.e., $(x_j^i,y_j^i) \\sim D_i$ for $j = 1,\\ldots, n$ where $D_i$ is the data distribution of the $i$-th subpopulation. This is a $k$ objective MOO where $f_i(\\theta)=\\frac1n\\sum_{j=1}^n\\log (1+\\exp(-y_j^i{x_j^i}^\\top\\theta))]+\\|\\theta\\|_2^2$, $i=1,\\cdots,k$. Then, $(2+m_2^i)I\\succ \\nabla^2f_i(\\theta)\\succ 2I $ which implies Assumption A, and $\\nabla^2 f_i(\\theta)$ is $0.1m_3^i$-Lipschitz continuous implying Assumption B where $m_2^i,m_3^i$ are 2nd and 3rd sample moments of the $i$-th population.\n\n[1]DeMiguel et. al., \"Optimal versus naive diversification: How inefficient is the 1/N portfolio strategy?.\" The review of Financial studies 22, no. 5 (2009): 1915-1953.\n\n[2]Chen et. al., \"A note on portfolio optimization with quadratic transaction costs.\" arXiv preprint arXiv:2001.01612 (2020).\n\n[3]DeMiguel et. al., \"Multiperiod portfolio optimization with general transaction costs.\" Available at SSRN (2013).\n\n[4]Han et. al., \"Merton’s portfolio problem under Volterra Heston model.\" Finance Research Letters 39 (2021): 101580.\n\n[5]Tong et. al., \"A smoothing method for solving portfolio optimization with CVaR and applications in allocation of generation asset.\" Applied Mathematics and Computation 216, no. 6 (2010): 1723-1740.\n\n[6]Zafar et. al., Fairness Beyond Disparate Treatment \\& Disparate Impact (2017).\n\n\n**Question 2: Concrete examples of preferences**\n\n*Portfolio optimization*\n\n Several popular preference function $f_0$ choices satisfy Assumption C:\n\n1. Constant Relative Risk Aversion in Merton’s portfolio problem, $f_0(x)=\\frac{1}{\\gamma}\\exp(-x^\\top r)$, $\\gamma>0$ [4].\n\n2. Smoothed version of Conditional Value-at-Risk (CVaR) $f_0(x) = \\min_{\\zeta \\in \\mathbb{R}} \\{ \\zeta + \\frac{1}{\\alpha} \\mathrm{E} [ \\phi(-x^\\top r - \\zeta) ] \\}\n$ where $\\phi(u) = \\frac{1}{\\beta} \\log(1 + e^{\\beta u})$[5].\n\n\n*Classification with sub-populations*\n\nThere are several social utility functions that satisfy Assumption C:\n\n1. User-defined social utility for public policy making $f_0 = \\sum_{i=1}^n w_i^* f_i(\\theta)$ where $w_i^*$ for $i = 1,\\ldots, k$ are a given set of weights.\n\n2. Demographic parity fairness $f_0(\\theta)=\\mathrm{E}[(z-E(z))(\\sigma(\\theta^\\top x)-E(\\sigma(\\theta^\\top x)))]$ where $\\sigma(\\cdot)$ is the logit function [6].\n\n\n**Question 3: practicality of assumptions**\n\nWe agree that it is of practical importance to extend our work to less restrictive settings, especially to non-convex objectives. However, this criticism can in a sense be leveled against the whole field of (single-objective) convex optimization. But, as it is with convex optimization, here we have found that even the strongly convex setting is already theoretically very rich, and that it has helped us to significantly deepen our understanding of the nature and challenges of multi-objective optimization. \n\nWe are already working on extending these results to the non-convex setting, and we’ve found it to be quite interesting and challenging (see also our response to Reviewer 9L4B for specifics). We believe that the completion of those results would be substantial enough to be published in a separate paper; this paper is already packed with many results. \n\nOf course, we welcome differences of opinions from the reviewer, but if so, we would really appreciate it if the reviewer would also articulate more specifically what results would be needed to make this work ready for publication."}, {"review_id": "XQMP3fRe0v", "reviewer": "Reviewer_9L4B", "summary": "This paper introduced the Pareto manifold which is a ‘lifting’ of the Pareto set. Pareto manifold is a smooth manifold. By connecting with the simplex to introduce an (approximate) stationarity condition for the Pareto-constrained optimization, the papers shows that any non-trivial, local stationary condition requires more than first-order information on the manifold. Further, the paper proposes Pareto Majorization-Minimization Algorithm which converges to an approximate preference stationary point of Pareto-constrained optimization with proved complexity. \n\nThe paper is well written, and the method is novel. The solved problem is also interesting and challenging.", "questions": "a. The Related Work section clarifies that existing stationary conditions are overly restrictive or non-necessary. Is it possible to provide more detailed comparison in both theoretical and empirical perspectives?\nb. Will the correlation between objectives impact the PMM's performance? For instance, what if two objectives are conflicting?", "limitations": "The paper is purely theoretical. While there is some justification that the main goal is theory, the absence of any synthetic or motivating example to illustrate how the PMM algorithm performs in practical problems and visualize convergence or solution quality. For example, running the proposed algorithm on toy quadratic objectives.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: The paper describes the motivation, problem setting, and major techniques clearly.\n\nWeaknesses: Beyond what's stated in the conclusion, are there intuitions derived from the developed results about how the framework might break down or need to be adapted in nonconvex objective settings?\n\nThough the paper is a theory paper, it would be good to include a practical example to visualize how the algorithm works and how the algorithm compares to other multi-objective optimization approaches.", "was_revised": true, "final_justification": "I appreciate the authors' feedback, and would like to maintain my rating.", "rebuttal": "Thank you for your careful and positive review.\n\n**Generalization to non-convex objectives**\n\nExtending to the non-convex setting is definitely an important future direction, and one we’ve found to be quite interesting and challenging. Some challenges:\n\n1. Without strict convexity, linear scalarization can miss out on Pareto optimal solutions: not every Pareto solution $x^*$ is a (local) minimizer of $f_\\beta$ for some convex combination $\\beta \\in \\Delta^{n-1}$ of the objectives. \n\n2. In fact, the Pareto optimal points can unintuitively even correspond to local maximizers of $f_\\beta$! This can happen even if the objectives are quasiconvex (thus, not non-convex in an arbitrary way; an example below). \n\n3. And if the objectives are arbitrarily non-convex, we also lose the diffeomorphism between the Pareto manifold and the simplex (though local diffeomorphisms may remain). \n\nWe have some ideas and are pursuing this direction, but it would probably be better to present results there in a separate paper.\n\n*Example of Pareto optimal point that is a local maximizer*. \n\nLet $q_1, q_2 : \\mathbb{R} \\to \\mathbb{R}$ be the quadratics $q_1(x) = (x - 1)^2$ and $q_2 = (x + 1)^2$. And let us aim to minimize the objectives $f_1, f_2 : \\mathbb{R} \\to \\mathbb{R}$, where $f_i = \\sigma \\circ q_i$, and $\\sigma$ is any strictly monotonic increasing function. Then, the Pareto set of $(f_1, f_2)$ coincides with the Pareto set of $(q_1, q_2)$, which is the interval $[-1, 1]$. \n\nConsider $\\sigma(z) = - \\exp(- z/T)$, where $T > 0$ is some temperature parameter (the objectives $f_i$ look like upside-down Gaussians). For sufficiently small $T$, the Pareto optimal solution $x = 0$ will be the local *maximizer* of the weighted objective $\\frac{1}{2} f_1 + \\frac{1}{2} f_2$ (which looks like an upside-down mixture of Gaussians).  \n\n\n**Visualization of algorithm/comparison with prior definitions of stationarity**\n\nWe agree that visualizing the algorithm would be helpful, especially in helping demonstrate the issues with earlier definitions of stationarity. We will update the paper with experiments and visualizations.\n\n\n**Impact of (anti)-correlation across objectives**\n\nOur convergence guarantees are independent of the correlation across objectives. While we’re not ruling out the possibility that (anti)-correlation can have some effect on convergence speed, from our analysis, it seems that the more fundamental quantities are the condition number of Hessians $\\nabla^2 f_i$ for each of the objectives. \n\nIn fact, in the extreme zero-sum setting, where two objectives are perfectly anti-correlated $f_1 = - f_2$, every point is Pareto optimal. In that case, the preference optimization over the Pareto set is “easy” since it becomes an unconstrained optimization problem (of course, this example is excluded from our setting since we require all objectives to be strongly convex).\n\nIn any case, we think this is a good type of question to pursue and refine in further research, since the goal of multi-objective optimization is to provide guidance on how to navigate conflicting objectives."}, {"review_id": "VZ33epW8QL", "reviewer": "Reviewer_i8uk", "summary": "The paper considers Pareto-constrained optimization, or constrained optimization of a user-defined preference function over Pareto-optimal solutions. It addresses the challenges of the non-smooth, non-convex Pareto set by lifting the problem to a \"Pareto manifold\" diffeomorphic to the $n-1$ simplex. The authors define a \"preference stationarity\" condition and relax it to a $(\\epsilon_0, \\epsilon)$-approximate version for practical optimization algorithms. The main algorithmic contribution is the Pareto Majorization-Minimization (PMM) algorithm, a two-step method that alternates between fitting a quadratic surrogate that upper-bounds $f_0$ and minimizing it over the simplex. PMM can accommodate gradient-based and dueling-based feedback and converges to an $\\epsilon_0$-approximate preference stationary solution in $O(\\epsilon_0^{-2})$ iterations.", "questions": "- Assumption A requires each objective $f_i$ to be strongly convex, which may not apply in many practical MOO settings. How can the Pareto-manifold lift be extended to just smooth (or even non smooth) objectives? What would be the technical challenges? So far as the paper is claiming relevance to RLHF, can the authors empirically demonstrate robustness to violating these assumptions?\n- Can the authors suggest some practical heuristics for determining when an inner solve is \"good enough?\"\n- The sample complexity for the dueling-based feedback scales poorly with dimension and $\\epsilon_0$. Can the authors include some experiments or suggest (e.g., variance reduction) methods to lower the sensitivity to dimension or $\\epsilon_0$?", "limitations": "The limitations are mentioned throughout the text (e.g., Remark 3), but it would be helpful to include a separate limitations section.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "### Strengths\n- While dense, the paper is well written and the narrative clear through the definition of the lifted Pareto manifold. The \"weight\" parameterization is intuitive and illustrated effectively in Fig 1\n- The preference stationarity condition is shown to be provably necessary for preference optimality and improves on earlier notions of stationarity that could miss optimal decisions\n- The PMM algorithm has an $O(\\epsilon_0^{-2})$ last-iterate convergence rate for both gradient-based and dueling-based feedback\n- Approximate proxy using only the local Hessian/gradient information is enough to verify approximate stationarity, by Lemma 7\n\n### Weaknesses\n- The framework assumes that all objectives are $\\mu$-strongly convex with Lipschitz Hessians (Assumption A), which may rule out more complex real-world MOO tasks.\n- The dueling-based feedback scales poorly with dimension and $\\epsilon_0$, as $O(d^4/\\epsilon_0^4 \\log (d/\\epsilon_0))$\n- Solving the inner problem every iteration may be resource-expensive for large models.\n- The paper is purely theoretical. Experiments on real RLHF or MOO benchmark problems would help validate constants or verify robustness to assumption violations, particularly Assumption A\n- The related work section seems to omit existing work on multi-objective stein variational gradient descent (e.g., [1]) and multi-objective Bayesian optimization, which similarly uses a Bayesian surrogate (e.g., [3-6]). In particular, [4] considers preference provided in the form of preference weights and [6] uses copulas and a game-theoretic argument for the preferred solution.\n\n[1] Liu, Xingchao, Xin Tong, and Qiang Liu. \"Profiling pareto front with multi-objective stein variational gradient descent.\" 2021.\n\n[2] Belakaria, Syrine, et al. \"Uncertainty-aware search framework for multi-objective Bayesian optimization.\" 2020.\n\n[3] Knowles, Joshua. \"ParEGO: A hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems.\" (2006).\n\n[4] Paria, Biswajit, Kirthevasan Kandasamy, and Barnabás Póczos. \"A flexible framework for multi-objective bayesian optimization using random scalarizations.\" 2020.\n\n[5] Emmerich, M., and Klinkenberg. The computation of the expected improvement in dominated hypervolume of pareto front approximations. 2008.\n\n[6] Binois, Mickaël, et al. \"The Kalai-Smorodinsky solution for many-objective Bayesian optimization.\" 2020.", "was_revised": true, "final_justification": "My concerns regarding related work and reframing (as a theory paper not directly validated on LLMs, as previously suggested throughout the text) have been addressed.", "rebuttal": "Thank you to Reviewer i8uk for taking the time to review and for the detailed feedback. It seems that the reviewer found the theoretical contributions strong, but raises concerns about the applicability to practical multi-objective settings such as for LLM fine-tuning, specifically because of (a) strong convexity assumptions, (b) how sample complexity scales with different parameters of the problem, and (c) the computational costs of solving the inner optimization problem.\n\n\n**Main contributions: theoretical vs. practical**\n\nWe agree that this work’s main contributions are theoretical, although practical problems such as LLM fine-tuning serves as a key motivation for our framework. But, in developing a principled approach, we found the problem to be highly non-trivial due to the non-convexity, non-smoothness, and the implicit nature of the constraint set (even when the objectives are simply quadratics). We greatly simplify the problem conceptually.\n\nPrior to our work, there were only heuristics for this problem. The literature lacked a proper definition of stationarity and algorithms with provable behavior. Actually, intuitive heuristics easily go wrong. We proved that there is a large class of very natural stationary conditions—including one in existing literature, and another we had initially considered—that will *reject* the true preference-optimal solution. Practically, this means that the prior algorithm in literature *provably avoids* the correct solution, even in the strongly convex setting!\n\nIn contrast, our work is the first to establish a well-justified solution concept that is efficiently and provably achieved by a simple algorithm, under two forms of feedback. The issue of practicality, especially in the context of LLM fine-tuning, is certainly a valid one, but also in a sense beyond the scope of this work: each of the goals of going beyond non-convexity, significantly improving sample complexity, reducing computational complexity are quite non-trivial and can be papers in themselves (indeed, we are currently pursuing these directions, and know of other groups doing so). We believe that our work already makes a significant and meaningful contribution to the literature, and that it provides a solid theoretical foundation upon which to develop algorithms achieving the above goals. As the reviewer puts it, this work already presents quite a \"dense\" set of results.\n\nOf course, we welcome differences of opinions from the reviewer, but if so, we would really appreciate it if the reviewer would also articulate more specifically what remaining results would make this work ready for publication.\n\nIn the following, we respond to more specific points.\n\n\n**Generalization to non-convex objectives**\n\nExtending to the non-convex setting is definitely an important future direction, and one we’ve found to be quite interesting and challenging. Some challenges:\n\n1. Without strict convexity, linear scalarization can miss out on Pareto optimal solutions: not every Pareto solution $x^*$ is a (local) minimizer of $f_\\beta$ for some convex combination $\\beta \\in \\Delta^{n-1}$ of the objectives. \n\n2. In fact, the Pareto optimal points can unintuitively even correspond to local maximizers of $f_\\beta$! This can happen even if the objectives are quasiconvex (thus, not non-convex in an arbitrary way; an example below). \n\n3. And if the objectives are arbitrarily non-convex, we also lose the diffeomorphism between the Pareto manifold and the simplex (though local diffeomorphisms may remain). \n\nWe have some ideas and are pursuing this direction, but it would probably be better to present results there in a separate paper.\n\n*Example of Pareto optimal point that is a local maximizer*. Let $q_1, q_2 : \\mathbb{R} \\to \\mathbb{R}$ be the quadratics $q_1(x) = (x - 1)^2$ and $q_2 = (x + 1)^2$. And let us aim to minimize the objectives $f_1, f_2 : \\mathbb{R} \\to \\mathbb{R}$, where $f_i = \\sigma \\circ q_i$, and $\\sigma$ is any strictly monotonic increasing function. Then, the Pareto set of $(f_1, f_2)$ coincides with the Pareto set of $(q_1, q_2)$, which is the interval $[-1, 1]$. \n\nConsider $\\sigma(z) = \\exp(z/T)$, where $T > 0$ is some temperature parameter. For sufficiently small $T$, the Pareto optimal solution $x = 0$ will be the local *maximizer* of the weighted objective $\\frac{1}{2} f_1 + \\frac{1}{2} f_2$. \n\n\n**Computational cost of inner solve and practical heuristics**\n\nAt least under our setting of strong convexity and Lipschitz smoothness, the cost of the inner solve is dimension-independent, with linear convergence rate. Moreover, our convergence analysis for the PMM algorithm quantifies how accurately the inner solve needs to be to achieve a target approximation error. In particular, to obtain $\\epsilon$-approximate preference stationarity, Theorem 9 shows that it is sufficient to optimize the inner objective $f_\\beta$ to approximate stationarity $\\| \\nabla f_\\beta(\\hat{x})\\| < O(\\epsilon)$. This takes around $O(\\log \\frac{1}{\\epsilon})$ steps of gradient descent.\n\n\n**Improving sample efficiency in dueling feedback setting**\n\nWe agree that a very practically-motivated problem is how to increase sample complexity of preference optimization under dueling feedback. Currently, we do not know how suboptimal the dependence on dimension is, nor on other parameters such as $\\epsilon_0$. It would be of great interest to explore how to reduce these dependencies or to show that in fact they are necessary. Still, this work is the first to obtain meaningful convergence guarantees under either forms of feedback.\n\n\n**Relationship to prior works**\n\nThank you for sharing these references to other works; we can contextualize our work among them. Classically speaking, methods in multi-objective optimization can be categorized as *a priori*, *a posteriori*, and *interactive*.\n\nIn *a priori* methods, the decision maker knows beforehand what their preference is, and the role of the MOO algorithm is to find the most-preferred Pareto-optimal solution. The bulk of our work falls under this category, with the exception of the section on dueling feedback, which is more interactive. The reference [6] is of this type, but their focus is on introducing one specific preference function motivated from game theory.\n\nIn *a posteriori* methods, the decision maker needs to first learn the Pareto set before deciding on their preference/making the final decision. In this case, the role of the MOO algorithm is to approximate the whole Pareto set. That is, to provide a shortlist of Pareto optimal options that would satisfy a wide variety of preferences of a downstream decision maker. The references [1,2,3,5] listed above fall under this category. (We do not operate under this setting).\n\nAnd *interactive* methods are in between, where the decision maker repeatedly interacts with the MOO algorithm, where both can refine their search and preferences over time. Our section on dueling feedback is of this form, and so is the reference [4] provided. However, the goals are somewhat different. We aim to recover the most preferred solution, while [4] aims to sample a diverse set of solutions from the Pareto set related to a user-specified distribution/prior over solutions."}, {"review_id": "rIG0jM23vs", "reviewer": "Reviewer_YrFB", "summary": "This paper proposes a method to tackle the optimization on the Pareto set problem, with application to preference optimization. Specifically, the upper-level objective is smooth and possibly nonconvex, while the lower-level objectives are smooth and strongly convex. An algorithm based on majorization-minimization is proposed to solve this problem.  Theoretical analysis on the convergence of the proposed algorithm, and the Bias and Variance bounds of Dueling Gradient Estimator for preference optimization are provided.", "questions": "1. Section 6.3.\n\n- Many notations are not introduced in this section.\nFor example, what are $u_i, d, b, \\gamma$?\n\n- Equation (16) needs more explanation. \n  - What is the intuition for this estimate? \n  - What are the required assumptions for the preference model and the preference samples? e.g., the underlying distributions that generated these samples? \n  - How to choose different link functions in practice?\n\n2. Assumption D.\nWhy is the Lipschitz constant of $\\sigma^{-1}$ depending on $x$?\nIf it depends on $x$, it cannot be called \"Lipschitz\".\n\n3. How is the operator $\\widehat{\\arg\\min}$ defined? It is used in the algorithm and Theorem 9 but not explicitly defined. What is the black-box optimizer?", "limitations": "1. The theory and the proposed method only apply to strongly convex lower-level objectives. \n2. The proposed method may require second-order information, can be computationally very expensive.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "1. Missing references.\n\nThere are many prior works that have already tackled the optimization on the Pareto set, or semivector bilevel optimization problem. See a few examples listed below. These works should be discussed and compared at least in the related works. Among these works, [1] is very close to the method proposed in this paper.\n\n[1] A. Roy, G. So, Y. Ma. Optimization on Pareto sets: On a theory of multi-objective optimization, arXiv:2308.02145\n\n[2] T. Giovannelli, G. D. Kent, and L. N. Vicente. Bilevel optimization with a multi-objective lowerlevel problem: Risk-neutral and risk-averse formulations. Optimization Methods and Software, 2024.\n\n[3] L. Chen, Q. Xiao, E. H. Fukuda, X. Chen, K. Yuan, T. Chen. Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance, arXiv:2504.02854\n\n\n2. Computational complexity is not discussed sufficiently.\n\nThe paper should provide more discussion on the iteration complexity and convergence rate of the proposed algorithm, and compare them with those of the existing algorithms.\n\n3. No experiments are provided to test the effectiveness/efficiency of the proposed method/algorithm and to compare with the existing methods.\n\n\n4. Some parts lack clarity.\n\n- Section 6.3. See **Questions-1**.\n\n- Assumption D. See **Questions-2**.\n\n- Algorithm. See **Questions-3**.", "was_revised": true, "final_justification": "The authors actively engaged in the discussion and promised to make some important revisions. I will raise my score to 4 if those revisions are included.", "rebuttal": "Thank you for your careful review and detailed feedback. We will especially take into account where it seems that the writing was unclear and improve our exposition. Besides that, there were two consistent concerns: (1) relationship/comparison to prior work, (2) practicality. We first address those now, before answering specific questions below.\n\n## Response to main concerns\n\n### Relationship to prior work/comparison with other methods\n\nThank you for sharing the related works. We are indeed familiar with [1], but it turns out that a comparison with [1] is not very meaningful. While [2] does consider a similar setting to us, there are no convergence guarantees provided for the proposed algorithms. [3] follows up on [1] and is also quite interesting; it was concurrent with our NeurIPS submission, but we will update our related works going forward. Besides these, the most related work to our setting is the PNG algorithm (Ye and Liu 2022), against which we theoretically compare in Appendix D.1.\n\nOut of all of these references prior to our work, there were only heuristics for this problem. The literature lacked a proper definition of stationarity and algorithms with provable behavior. Actually, intuitive heuristics easily go wrong. We proved that there is a large class of very natural stationary conditions—including the one found by the PNG algorithm—that will *reject* the true preference-optimal solution. This means that the prior algorithm in literature *provably avoids* the correct solution, even in the strongly convex setting! \n\nIn contrast, our work is the first to establish a well-justified solution concept that is efficiently and provably achieved by a simple algorithm, under two forms of feedback. Theoretically, there is nothing to compare against. And since we proved that the closest prior algorithm in literature converges to the wrong solution, it is also not meaningful to compare against them experimentally.\n\n### Practicality: strongly convex objectives and second-order information\n\nWe agree that many practical problems have objectives that are not strongly convex. Indeed, such problems, such as LLM fine-tuning, serves as a key motivation for our framework. But, in developing a principled approach, we found the problem to be highly non-trivial due to the non-convexity, non-smoothness, and the implicit nature of the constraint set (even when the objectives are simply quadratics). Here, we have found that even the strongly convex setting is already theoretically very rich, and that it has helped us to significantly deepen our understanding of the nature and challenges of multi-objective optimization.\n\nAnd so while our main contributions are theoretical, we believe they are still of significance to the multi-objective optimization community, as we have greatly simplified the problem conceptually. We believe this may help researchers avoid the same pitfall as the PNG algorithm (which we also initially fell into). Additionally, we have already shared this work with part of the community (non-archival), and know of other groups that are developing further results on top of this.\n\nSpecifically regarding strong convexity, we are already working on extending these results to the non-convex setting, and we’ve found it to be quite interesting and challenging (see also our response to Reviewer 9L4B). And on second-order information, we have shown that second-order information is necessary. However, we are hopeful that there are computationally-efficient estimators (e.g. using ideas from [I,J]), and we are currently working on this as well. \n\nThe completion of either of these results would arguably be substantial enough to be published in separate papers; this paper is already packed with many results. We believe that our work already makes a significant and meaningful contribution to the literature, and that it provides a solid theoretical foundation upon which to develop algorithms that work under less restrictive conditions, and that are more sample and computationally efficient.\n\nOf course, we welcome differences of opinions from the reviewer, but if so, we would really appreciate it if the reviewer would also articulate more specifically what results would be needed to make this work ready for publication.\n\n## Specific questions\n\n### Computation complexity\n\nThe iteration complexity and the convergence rate of our algorithm, $K \\leq \\frac{2 \\mu_g\\cdot \\big(f^* - f_*\\big)}{ c_1^2 \\cdot \\epsilon_0^2}$, are provided for the first-order feedback in Theorem 9 (page 8) and for the dueling feedback in Theorem 10 (page 9). The proofs of the theorems are provided in Appendix G and Appendix H.2 respectively.\n\n### Clarification for Section 6.3\n\n**What are $u_i,d,b,\\gamma$?**\n\nIn (16), {$u_i$}$_{i=1}^b$ are $b$ unit vectors chosen uniformly at random from the unit sphere $S^{d-1}$ where $d$ is the ambient dimension of the space - same as introduced in Section 2. $\\gamma>0$ is a scalar. We will update this notations in the final version. \n\n**Equation (16).**\n\nUnder zeroth-order feedback, i.e., when only $f_0(x)$ can be computed, one has the following gradient estimator:\n\n$$\\tilde{\\nabla} f_0(x)=\\frac{d(f_0(x+\\gamma u)-f_0(x-\\gamma u))}{2\\gamma}u,$$\n\nwhere $u\\in S^{d-1}$ is chosen uniformly at random. Then, $\\|\\mathbb{E}[\\tilde{\\nabla} f_0(x)]-\\nabla f_0(x)\\|_2=O(d\\gamma)$, which is small for small enough $\\gamma$. \n\nSo estimating $ \\nabla f_0(x) $ only requires estimating function value differences which is implicitly encoded in the preference model. If $\\mathbb{E}[Y(x+\\gamma u, x-\\gamma u)]$ were known, one has\n\n$$f_0(x+\\gamma u)-f_0(x-\\gamma u)=\\sigma^{-1}(\\mathbb{E}[Y(x+\\gamma u,x-\\gamma u)]).$$\n\nEstimating $\\nabla f_0(x)$ reduces to estimating $\\mathbb{E}[Y(x+\\gamma u, x-\\gamma u)]$, the mean of a Bernoulli random variable. A natural estimator is the empirical average\n\n$$\\tilde{p} = \\frac{1}{m} \\sum_{j=1}^m q_j(x,u), \\quad \\text{where } q_j(x,u) = Y_j(x+\\gamma u, x-\\gamma u),$$\n\ninterpretable as averaging the feedback from querying $m$ independent individuals for preferences between two points. The caveat is that for common preference models, $\\sigma^{-1}(x)$ becomes unbounded as we approach $x = 0,1$ (e.g., Bradley–Terry with $ \\sigma^{-1}(x) = \\log(x/(1-x))$). So we apply clipping:\n\n$$\\hat{p} = \\max(\\alpha, \\min(\\tilde{p}_{x+\\gamma u, x-\\gamma u}, 1 - \\alpha)).$$\n\nHere, $\\alpha$ is chosen so that clipping error is balanced with the approximation error in $\\mathbb{E}[\\tilde{\\nabla} f_0(x)]$ and the stochastic error $\\text{err}_{\\nabla f_0}$. This leads to the following estimator:\n\n$$\\tilde{\\nabla} f_0(x) = \\frac{d}{2\\gamma} \\sigma^{-1}\\left( \\hat{p}_{x+\\gamma u, x-\\gamma u} \\right) u.$$\n\nNow, to approximate $\\mathbb{E}[\\tilde{\\nabla} f_0(x)] \\approx \\nabla f_0(x)$ (with error $O(d\\gamma)$ ), we average over $b$ i.i.d. directions {$u_i$}$_{i=1}^b$, and arrive at (16):\n\n$$\\hat{\\nabla} f_0(x) = \\frac{d}{2\\gamma b} \\sum_{i=1}^b \\sigma^{-1}\\left( \\hat{p}_{x+\\gamma u_i, x-\\gamma u_i} \\right) u_i.$$\n\nWe plan to improve the intuition in the final version.\n\n**Assumption D.**\n\nOur preference model (Definition 5) assumes that the binary variable $Y(x_1, x_2)$ satisfies $\\mathbb{E}[Y(x_1, x_2)] = \\sigma(f_0(x_2) - f_0(x_1))$. The query points $x_1, x_2$ are non-random, so no distributional assumption is imposed on them. Characterizing the preference model reduces to specifying assumptions on $\\sigma$, as in Assumption D.\n\n**Choice of link function**\n\nThe choice of preference function is problem-specific. Our goal, however, is not to model preferences but to provide an algorithm for Pareto-constrained optimization which can be used as black-box by an user with any preference model (Definition 5) they may choose. As long as Assumption D holds—which is true for common models like logistic, softplus, and tanh—our algorithm converges at the rate stated in Theorem 10, ensuring broad applicability. However, some common preference models include Logistic (Bradley-Terry)/Softmax [A,B,C,D,E] and Tanh [F,G,H].\n\n\n**Lipschitz constant**\n\nBy $L_\\sigma (1 + (x(1 - x))^{-1})$-Lipschitz continuity, we mean that $\\sigma^{-1}$ is locally Lipschitz, but we agree that this can be made less confusing. More precisely, we assume $\\left| \\frac{d}{dx} \\sigma^{-1}(x) \\right| \\leq C(1 + (x(1 - x))^{-1})$ for some constant $C > 0$, which implies via the mean value theorem:\n\n$$|\\sigma^{-1}(x) - \\sigma^{-1}(y)| \\leq L_\\sigma \\left(1 + \\frac{1}{x(1 - x)} + \\frac{1}{y(1 - y)}\\right) |x - y|$$\n\nfor some $L_\\sigma > 0$. This is the bound used in Lemma 1 (Appendix H), and we will revise the terminology in the final version.\n\n**Definition of $\\widehat{\\mathrm{argmin}}$**\n\nThe operator $\\widehat{\\arg\\min}$ denotes the approximate minimizer from the black-box optimizer referenced in Theorem 9. As discussed in Section 6.1 and Remark 2, this can be any suitable off-the-shelf optimizer suitable, including (projected) gradient descent. We will clarify this in the paper.\n\n[A]Maystre et.al, \"Choicerank: identifying preferences from node traffic in networks.\" ICML 2017.\n[B]Chu et.al, \"Preference learning with Gaussian processes.\" ICML 2005.\n[C]Hunter, \"MM algorithms for generalized Bradley-Terry models.\" AOS 2004.\n[D]Chen et.al, \"Pairwise ranking aggregation in a crowdsourced setting.\" ICWDM 2013.\n[E]Ouyang et.al, \"Training language models to follow instructions with human feedback.\" NeurIPS 2022.\n[F]Orlando, \"A discrete mathematical model for chaotic dynamics in economics: Kaldor’s model on business cycle.\" MCS 2016.\n[G]Tuev et.al, \"Using modified hyperbolic tangent function to approximate the current–voltage characteristics of field–effect transistors.\" Tomsk Polytechnic University, 2009.\n[H]Giulio. \"Power Exhaust Data Analysis and Modeling of Advanced Divertor Configurations.\" 2018.\n[I]Huang et.al, \"Efficiently escaping saddle points in bilevel optimization.\" JMLR 2025.\n[J]Kwon et.al, \"A fully first-order method for stochastic bilevel optimization.\" ICML 2023."}]

Author rebuttal:

Meta-review: This paper introduces a new algorithm with a provable convergence rate for preference function optimization over the Pareto set, supported by a meaningful notion of approximate preference stationarity. The theoretical contributions are solid, including the insight that first-order information is insufficient, motivating the use of second-order terms. While reviewers noted missing references, lack of toy experiments, and limited discussion of practical motivation, the rebuttal satisfactorily addresses these issues: the authors commit to adding comparisons, provide concrete examples of practical relevance, and will include illustrative experiments. Overall, the paper makes a clear and rigorous theoretical advance, and I support acceptance.
Decision: Accept (poster)