FERERO: A Flexible Framework for Preference-Guided Multi-Objective Learning

Authors: lisha  chen
afm  saif
yanning  shen
tianyi  chen
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 05:33:17

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

Main paper: 
 introduction: 
 Many machine learning tasks inherently involve multiple objectives, which can be different performance metrics such as accuracy, fairness, and privacy; or, the same metrics defined on different data [40, 31] . To tackle such multi-objective problems, it is common to learn a shared model that simultaneously performs well on all the objectives. Compared to learning one model for each objective, learning a shared model has the benefit of reducing both the model size and the inference time. This can be achieved through multi-objective optimization [40, 45, 25, 6] , which is to learn a model that minimizes the vector-valued objective. In practical applications, it is of interest to learn solutions with controlled trade-offs or preferences. To further illustrate, we give two examples below.In fairness-aware machine learning, a trade-off exists between the fairness f fair (θ) and accuracy f acc (θ), see also Figure 1a . With θ denoting the model parameter, and C denoting the partial order Table 1 : Comparison to existing methods. "Flexibility" represents preference modeling, such as by using weights, preference vectors (rays), or constraints. "Exactness" represents the ability to align with a preference vector exactly. "Deter.", "Stoch." represent deterministic and stochastic, respectively. "✗" means not provided in the corresponding work, and "-" means not relevant. (Smooth) Tchebycheff [23] weight -✗ ✓ non-asymptotic ✗ PMTL [24] inequalities (absolute) ✗ ✗ ✗ asymptotic ✗ EPO [30] r -1 ray (ratio, absolute) ✓ ✓ ✗ asymptotic ✗ (X)WC-MGDA [33] shifted ray (absolute)✓ ✗ ✗ ✗ ✗ FERERO (ours) relative & absolute ✓ ✓ ✓ T -1 T -1 2cone, to find the optimal models that consider different trade-offs, one can solve the following problem with different thresholds ϵ [8] maximize C (f acc (θ), f fair (θ)) ⊤ s.t. f fair (θ) ≥ ϵ.(1.1)Another example is in drug or molecule design, where the goal is to design drugs or molecules with multiple desired properties f 1 (θ), f 2 (θ), . . . , f M (θ). Aiming to align the values of the properties F (θ) with a predefined preference vector v as in Figure 1b , one can solve the following problem [29, 1, 46] maximize C F (θ) := f 1 (θ), . . . , f M (θ) ⊤ s.t. BF (θ) = Bv, Bv = 0(1.2)where B ∈ R (M -1)×M is full row rank. Then a natural question arises:Can we develop a principled framework to capture flexible preferences and admit provably convergent deterministic and stochastic algorithms?Our answer to this question is affirmative. Recognizing that all the aforementioned applications can be addressed within a unified framework, we formulate preference-guided multi-objective learning (PMOL) as a constrained vector optimization problem. Specifically, given a model θ ∈ R q , and the objectives f m : R q → R, m = 1, . . . , M , we define the constrained vector optimization problem asmin θ∈R q F (θ) := f 1 (θ), . . . , f M (θ) ⊤ , s.t. G(θ) ≤ 0, H(θ) = 0 (PMOL)where G(θ) and H(θ) are the vector-valued preference constraints such as the examples in (1.1) and (1.2). Here "≤" and "=" are element-wise relations on the vectors, with each row representing one constraint. In these examples, the preferences are directly defined in the objective space, as intersections of half-spaces defined by the hyperplanes; see Figure 1 . Thus, G(•) and H(•) in (PMOL) can be expressed as linear functions of F (θ), given byG(θ) = B g F (θ) + b g , H(θ) = B h F (θ) + b h (1.3)where A comparison of our methods to existing methods is summarized in Table 1 . Specifically, our contributions are listed as follows: C1) We cast the PMOL problem as a constrained vector optimization problem, and develop the FERERO framework to capture flexible preferences.B g ∈ R Mg×M , B h ∈ R M h ×M ,We develop a method with an adaptive subprogram that efficiently finds update directions to meet flexible preferences, eliminating the need for multiple subprograms under different active constraints. This approach ensures iterative improvement in a general partial ordering while allowing controlled ascent of objectives to satisfy preferences.We propose a practical single-loop algorithm and establish non-asymptotic convergence guarantees for deterministic and stochastic variants of the proposed algorithm. To our best knowledge, this is the first single-loop primal algorithm in constrained vector optimization with convergence guarantees. C4) We apply the proposed algorithms to various synthetic and real-world image and speech datasets to demonstrate its ability to find flexible preference-guided optimal models.In our theoretical analysis, we address the following technical challenges.T1) The commonly used constraint qualification assumptions do not generally hold for the PMOL problem. We overcome this challenge by leveraging the specific structure that the constraints are linear functions of F to prove the calmness condition holds for PMOL. See more details in Lemma 2. T2) The commonly used merit or Lyapunov functions for constrained optimization are usually non-smooth, making it difficult to derive a descent lemma on the functions, and thus difficult to derive the non-asymptotic convergence guarantees. We overcome this challenge by exploiting the optimality conditions and proper step size choices. See Lemma 8. T3) The convergence of our single-loop algorithm is slower with the commonly-used merit functions. We provide a sharper analysis by introducing a different merit function and exploiting the algorithm properties; see Theorem 3. 
problem setup and a meta algorithm: 
 To characterize the optimality conditions of PMOL, we introduce the generalized notion of dominance and the related concept of optimality. We then present a meta-algorithm to solve PMOL. We first introduce optimality definitions for PMOL that go beyond the standard definitions of Pareto optimality [12, 10, 26] . Given two vectors v and w, we use v < w and v ≤ w to denote v i < w i for all i, and v i ≤ w i for all i, respectively. We use v ⪇ w to denote v ≤ w and v ̸ = w, and define >, ≥, ⪈ analogously. Definition 1 (C A -dominance [11, 19] ). Given v, w ∈ R M , A ∈ R M ×M , and C A := {y ∈ R M | Ay ≥ 0} ̸ = ∅, we say v strictly dominates w based on C A if and only if A(v -w) < 0. The generalized dominance defines a partial order on R M , i.e., the relation between two vectors. Illustrations of different partial orders are given in Figure 2 . Figure 2a shows the dominance relation under the widely used non-negative orthant cone with C A = R M + , corresponding to Pareto optimality. However, as illustrated by the figure, given the initial green reference point, a descent method such as MGDA [12] cannot find points on the Pareto front but outside of the gray shaded region. This poses a critical challenge for applications where specific preference-guided solutions on the Pareto front are needed. Nevertheless, this issue can be addressed by substituting R M + with a more general definition of C A as displayed in Figure 2b . Under this partial order, a general descent method is able to reach any points on the Pareto front starting from the green reference point.Based on the partial order, one can then find the minimum or optimal elements in the vector-valued objective space, whose formal definition is provided below. Definition 2 (C A -optimal). A point θ ∈ R q is C A -optimal if there is no θ ′ ̸ = θ such that, AF (θ ′ ) ⪇ AF (θ). A point θ is weakly C A -optimal if there is no θ ′ ̸ = θ such that, AF (θ ′ ) < AF (θ).A is a polyhedral cone, or the intersection of half-spaces defined by the rows of the inequality Ay ≥ 0. When A = I M , an M × M identity matrix, C A = R M + := {y ∈ R M | y m ≥ 0 ∀m ∈ [M ]}, then Definition 1 reduces to the commonly used notion of dominance associated with Pareto optimality. The cone C A can be interpreted as a relative preference that defines the objectives' improvement directions, which generalizes the relative preference defined by R M + . In contrast, the preference defined by constraints in (1.3) can be interpreted as an absolute preference that defines the feasible or preferred set of objective function values. In practice, C A can be chosen based on the requirements of specific applications. For example, when the controlled ascent of objectives is needed [30] , we can choose C A such that the controlled ascent direction belongs to -C A . We defer the detailed implementation to Section 3.2. The C A -optimal set, denoted as P A , contains all the C A -optimal models. When A = I M , P A is the Pareto optimal set P. The Pareto front is the set of function values evaluated at Pareto optimal models, i.e., F = {F (θ) | θ ∈ P}. We make the following standard assumptions throughout the paper [12, 17, 6] . Assumption 1. 1. (Non-negative objectives) AF (θ) ≥ 0, and 1 ⊤ AF (θ) ≥ c AF > 0 for all θ ∈ R q . 2. (Differentiable objectives) F is twice continuously differentiable.In this section, we proceed to discuss an adaptive method to solve (PMOL). At iteration t, the algorithm finds an update direction d t and performs the iterative update θ t+1 = θ t + α t d t with a step size α t . Ideally, the update direction d t is chosen to improve the objective F (θ) and to satisfy the preference constraints. It is desirable that when the constraints are not satisfied, d t decreases the violation of constraints and improves the objectives in the general partial ordering sense; when the constraints are satisfied, d t improves the objectives and ensures the constraints are satisfied. To achieve this, we find a direction d * (θ) that solves following subprogramψ(θ) := min (d,c)∈R q ×R c + 1 2 ∥d∥ 2 s.t. A∇F (θ) ⊤ d ≤ c 1 ⊤ AF (θ) AF (θ) (2.1) ∇G(θ) ⊤ d + c g G(θ) ≤ 0, ∇H(θ) ⊤ d + c h H(θ) = 0where ∥ • ∥ denotes the ℓ 2 -norm, c g and c h are pre-defined positive constants. Larger c g and c h put more emphasis on constraint satisfaction than objective improvement. We call this subprogram adaptive since it deals with constraints in an adaptive way, which does not require the initial model to be feasible, nor θ t to be feasible at each iteration. But rather, it finds an update direction that decreases the constraint violation. Because of this, it neither requires solving different subprograms at different stages nor requires different treatment of the active set of inequalities as in existing works [24, 30, 33] .Algorithm 1 A meta FERERO algorithm 1: Initialize t = 0, θ 0 , step size {α t }; define A. Set t = t + 1; 9: end while We then show in Lemma 1 that the desired properties can be satisfied. Lemma 1. For the subprogram (2.1), the following holds: If θ is a local optimal solution with AF (θ) > 0, then d * (θ) = 0, ψ(θ) = 0. Otherwise, if θ is not a local optimal solution, then d * (θ) ̸ = 0, ψ(θ) < 0, and whenθ is feasible, 2ψ(θ) ≤ -∥d * (θ)∥ 2 < 0. (2.2) Let θ be a weak C A -optimal solution, with (AF (θ)) m = 0 for some m ∈ [M ]. If there exists feasible and non-strictly improving directions at θ with A∇F (θ ) ⊤ d ⪇ 0, then d * (θ) ̸ = 0, ψ(θ) < 0. Otherwise, d * (θ) = 0, ψ(θ) = 0.Thus ∥d * (θ)∥ 2 + λ * g ⊤ [-G(θ)] + + ∥[G(θ)] + ∥ 1 + ∥H(θ)∥ 1 achieveszero if and only if the model θ satisfies the first-order KKT condition. Besides the properties in Lemma 1, it has an additional scale-invariant property that is deferred to Lemma 4 due to space limit.By the Lagrangian of (2.1), the optimal update direction can be expressed in a simple form as a weighted combination of the gradients, i.e. d * (θ) = -∇F (θ)A ⊤ ag λ * , with A ag := [A; B g ; B h ], andEQUATIONwhere λ = [λ f ; λ g ; λ h ], Ω λ (θ) is the domain of the Lagrangian multipliers, given by1 Ω λ (θ) := Ω λ f (θ) × R Mg + × R M h , with Ω λ f (θ) := {λ ∈ R M + | λ ⊤ AF (θ) = 1 ⊤ M AF (θ)}. (2.4)Our goal is to design an algorithm that converges to a KKT solution based on (2.1). However, the KKT condition is not necessary unless certain constraint qualifications (CQs) hold. Prior works [14, 24] assume certain CQs hold, e.g., the Linear Independence Constraint Qualification (LICQ). However, the LICQ assumption (c.f., [14, Section 3.1, (A2)]) does not generally hold at a local optimal solution for problem (PMOL), c.f., Example 1 in Appendix D.3.2. Though some commonly used CQs do not hold generally, in our case, leveraging the specific structure that the constraints are linear functions of F , we can justify the calmness CQ in Definition 9 tailored for our problem in Lemma 2, thus the KKT condition is a necessary optimality condition. The proof is deferred to Appendix D.3.2.Lemma 2. Let θ ∈ R q be a global solution to (PMOL). Define Σ(p, q):= {y ∈ R M | B g y + b g ≤ p, B h y + b h = q}. If Σ(p, q) is a line, the PMOL calmness condition in Definition 9 is satisfied for (PMOL) at θ if A ∈ R M ×M is full rank, H(θ), G(θ) defined by (1.3) satisfy [B ⊤ h , B ⊤ g ] ̸ = 0, and B h , B g are full row rank. Consequently, the KKT condition is a necessary optimality condition.Lemma 2 provides a sufficient condition for the KKT condition to be a necessary optimality condition without relying on unjustified assumptions. The requirement that the constraint set is a line in the objective space is common for applications such as alignment to a preference vector.We then discuss a generic preference-guided multi-objective algorithm based on the subprogram.Given the model θ t at iteration t, one can then solve (2.3) to obtain λ t . The direction d t = -∇F (θ)A ⊤ ag λ t is used to update the model θ t by θ t+1 = θ t + α t d t iteratively until convergence. The full procedure of this meta algorithm is summarized in Algorithm 1, where Step 4 is a generic step and can be customized in Section 3. To establish the non-asymptotic convergence rate, we use the following standard smoothness assumption that has been commonly used in prior works for multi-objective learning [6, 26] . Assumption 2 (Smooth objectives). For all m ∈ [M ], ∇f m (θ) is ℓ f,1 -Lipschitz continuous.We then state the convergence result for Algorithm 1 in Theorem 1.Theorem 1 (Convergence of the generic FERERO algorithm). Suppose Assumptions 1, 2 hold. Let {θ t } be the sequences produced by Algorithm 1, with d t being an ϵ-optimal solution to the subprogram (2.1).If ∥λ * (θ t )∥ 1 ≤ c, α t ≤ min{ 1 cℓ f,1 ∥A ⊤ ag ∥∞,1 , c -1 g , c -1 h }, and α t = Θ(1), then 1 T T -1 t=0 ∥∇F (θt)A ⊤ ag λ * (θt)∥ 2 stationarity + λ * g (θt) ⊤ [-G(θt)]+ complementary slackness + ∥[G(θt)]+∥1 + ∥H(θt)∥1 feasibility = O T -1 + ϵ . (2.5)Theorem 1 guarantees the non-asymptotic convergence for the generic FERERO algorithm. In Algorithm 1, λ t can be solved through projected gradient descent or Frank Wolfe algorithm iteratively within an inner loop. In practice, we usually do not need to solve the subprogram exactly. Next, we discuss the efficient single-loop approximate algorithm based on Algorithm 1. In this section, we first discuss efficient algorithm development with the approximate update rules and practical choice of preferences. We focus on (PMOL) with equality constraints only, i.e., M g = 0. Building upon this, we then discuss the stochastic variants of the algorithms that can be applied to large-scale learning problems. 
(ordering cone with non-empty interior) c: 
 A has a non-empty interior.In practice, if one only requires the converging solutions generated by the algorithm to be feasible, but not all the iterates, then further approximations can be made to the subprogram (2.3). At iteration t, to obtain an approximate direction d t , we adopt the following updateλ t+1 =Π Ω λ (θt) λ t -γ t ∇ λ φ(λ t ; θ t ) . (3.1)The single-loop algorithm with the approximate solution is summarized in Algorithm 2. We name it FERERO with Single-loop Approximate update (FERERO-SA) algorithm.We make the following additional assumption of Lipschitz objectives to prove the convergence of Algorithm 2, which is standard in optimization literature.Assumption 3 (Lipschitz objectives). For all m ∈ [M ], f m (θ) is ℓ f -Lipschitz continuous.To prove the convergence of Algorithm ), it holds thatEQUATIONTo obtain a sharper convergence rate, we consider a different merit function ∥∇F (θ t )A ⊤ ag λ t ∥ 2 + ∥H(θ t )∥ 2 , which achieves zero if θ t satisfies the KKT condition. We use this merit function because it provides better properties for sharper analysis. The detailed proof is deferred to Appendix F.3.Theorem 3 (Sharper convergence of the FERERO-SA algorithm). Suppose Assumptions 1, 2, 3 hold, and M g = 0. Let {θ t }, {λ t } be the sequences produced by Algorithm 2. With properly chosen step sizes α t = Θ(1), γ t = Θ(T -1 ), it holds that The stochastic variant. We employ a stochastic variant of Algorithm 2 based on the double sampling techniques developed in the recent work [6] . The update is given byEQUATIONθt+1 =θt + ∇F ξ t,1 (θt)A ⊤ ag λt (3.4a) λt+1 =Π Ω λ (θ t ) λt -γt ∇λ φ(λt; θt) (3.4b) ∇λ φ(λt; θt) =Aag∇F ξ t,1 (θt) ⊤ ∇F ξ t,2 (θt)A ⊤ ag λt -[0 ⊤ , c h H ξ t,1 (θt) ⊤ ] ⊤ (3.4c)where ∇ is the unbiased stochastic estimate of the gradient, and ξ t,1 and ξ t,2 are two independent stochastic samples obtained at iteration t.The full description of the stochastic algorithms and their convergence guarantees are deferred to Appendix G. Note that, compared to [6] , we adopt a more efficient implementation that reduces the per-iteration computational complexity.Theorem 4 (Convergence of the stochastic FERERO algorithm). Suppose Assumptions 1, 2, 3 hold, and M g = 0. Let {θ t }, {λ t } be the sequences produced by Algorithm 3. Suppose the variance of ∇F ξ (θ t ), ∇λ φ(λ t ; θ t ) are bounded. With properly chosen step sizesα t = α = Θ(T -1 2 ), γ t = γ = Θ(T -32 ), it holds that1 T T -1 t=0 E ∥∇F (θt)A ⊤ ag λt∥ 2 + ∥H(θt)∥ 2 = O T -1 2 . (3.5)Theorem 4 generalizes Theorem 3 to its stochastic variants, with a matching convergence rate to the unconstrained stochastic MOO algorithms and stochastic gradient descent. This allows us to apply the algorithm to large-scale machine learning problems, which we detail in Section 5.As briefly discussed in Section 2.1, the ordering cone and the corresponding matrix A can be specified according to practical needs. We first discuss how to obtain matrix A for the relative preference given the set of improvement directions. Then we discuss how to choose the relative preference to allow controlled ascent update, which is useful for touring the Pareto front [30] .Ordering cone generation. In practice, to obtain the polyhedral cone that defines the partial order, one can usually first define the extreme rays of the polyhedral cone. We then show how to convert the extreme ray description of the cone to the half-space description given by matrix A, i.e., C A = {y ∈ R M | Ay ≥ 0}, by showing how to compute A from the extreme rays.Let Y = [y 1 • • • y M ] ∈ R M ×Mbe a matrix that contains all the extreme rays of C A as its column vectors, thenC A = {Y λ | λ ≥ 0}. Let a ⊤ m ∈ R 1×M denote the row vectors of A for all m ∈ [M ]. Then all a m can be found by a that solves the following linear feasibility programEQUATIONChoice of C A for controlled ascent. If C A is not pre-specified, and the decision maker wants to choose C A to allow controlled ascent, it can be achieved with the following procedure. Let F 0 = F (θ 0 ) be the objective of the initial iterate of the algorithm, and F go be the target function value along the controlled ascent direction. To ensure F go -F 0 ∈ -C A for controlled ascent, we include (F 0 -F go )/∥F 0 -F go ∥ in the set of extreme rays, then take the extreme rays of the convex hull of the new set to form the columns of Y . Finally, we obtain C A by solving (3.6). 
related works: 
 To put our work in context, we review the most relevant literature in (preference-guided) multiobjective optimization, constrained optimization, with a focus on gradient-based approaches.A straightforward approach of MOO is to use scalarization to transform MOO into a single-objective optimization problem [32] . Another popular approach focuses on finding update directions which avoid conflicts with the gradients of the objectives [40, 45, 25] .A foundational algorithm in this domain is the Multiple Gradient Descent Algorithm (MGDA) [10, 26, 6] , which dynamically weights gradients to find a steepest common descent direction for all objectives. However, a single solution usually cannot capture different trade-offs on the Pareto front. This motivates the development of preference-guided multi-objective optimization methods.Preferences can be modeled through weights or thresholds assigned to different objectives [32] . For example, scalarization-based methods use the ℓ p -norm of the weighted vector-valued objective to convert the vector-valued objective into a scalar-valued objective, e.g., Linear scalarization (LS), Tchebycheff scalarization. Then the problem can be solved by single-objective optimization on the scalar objective. The ϵ-constraint methods enforce threshold constraints on different objectives, then solve the problem by constrained optimization. More recently, preferences have been modeled by preference vectors defined in the objective space. Then the problem can be formulated as finding Pareto optimal solutions satisfying the constraints defined by the preference vectors [24] , or optimizing the distance to the preference vectors [30, 33] . The key difference between FERERO and these works is that FERERO can capture more flexible preferences based on a general partial order. Moreover, we provide non-asymptotic convergence guarantees for the proposed algorithms. Constrained optimization. Constrained optimization methods include primal methods, penalty and barrier methods, and primal-dual methods [4, 28] . Our proposed method is related to the primal method that finds a feasible update direction to ensure the models are feasible and improving along the optimization trajectory. To address the limitation that it usually requires a stage-one procedure to ensure the initialization is feasible, we use an adaptive approach to ensure the constraint violation is decreasing and converging to zero. This idea can also be found in sequential quadratic programming (SQP) [13] . However, compared to SQP, we use an identity matrix to approximate the Hessian of each objective, and we use an adaptive approach that automatically adjust the descent amount of objectives. Furthermore, existing SQP algorithms typically require an inner loop to solve the optimal Lagrangian multiplier, resulting in double-loop algorithms. In contrast, we develop a single-loop algorithm which is more efficient to implement.Vector optimization. Vector optimization [11, 19] generalizes multi-objective optimization by substituting the commonly used component-wise partial order with a more general partial order, such as a general convex-cone induced partial order used in this paper. In the unconstrained setting, the MGDA method is extended to a steepest cone descent method in the vector optimization setting in [17] . Besides gradient-based vector optimization, another line of works focus on black-box vector optimization with discrete design space [3, 2] . In the constrained setting, the first-order optimality conditions are studied in [16, 43] . Algorithms based on projected gradient [9] or conditional gradient [7] are developed to solve vector optimization with parameters constrained in a set, to name a few. To our best knowledge, we are the first to design single-loop (stochastic) primal algorithms for constrained vector optimization with convergence rate guarantees. 
experiments: 
 In this section, we conduct experiments to verify our theory and show the applicability of the algorithms to preference-guided multi-task learning, and multi-objective finetuning of large multilingual speech recognition models. We use Linear scalarization (LS), MGDA [40] , PMTL [24] , EPO [30] , XWC-MGDA [33] as baselines for comparison.Metrics. Objective loss and accuracy. We report the objective losses and accuracies in classification.Relative loss profile. We use the element-wise product of the preference vector and the objective values as a measure of the relative loss profile. Hypervolume. Let F ′ ∈ R M denote a reference point, and S denote a set of objective function values of the obtained models. Hypervolume measures the size of the dominated space of S relative to F ′ , which can be computed byH(S) = Λ({q ∈ R M | ∃F ∈ S : F ≤ q ≤ F ′ }), where Λ(•) denotes the Lebesgue measure. For a fair comparison, we use the Nadir point, i.e., the worst performance on single-task baselines, as the reference point F ′ .Additional details. The implementation and additional experiments can be found in Appendix H.Following [24, 30, 33] , the first objective we consider is The objective has a nonconvex Pareto front (PF). See the results of different methods in Figure 3 .EQUATIONWith uniformly generated weights from a simplex, LS only finds extreme points on the PF with one objective minimized. MGDA can only find points close to the center of the PF. PMTL can find points in the subregions but not aligned well with the exact preference vectors. Similar to EPO, in Figure 3e , our method finds points that align well with the exact preferences; and in Figure 3f , our method can handle different definitions of preferences.We conduct another experiment in a more difficult setting where the initial objectives are close to the PF. In Figures 4a-4c , we consider a relatively easier case where the initial model is not too close to the Pareto optimal. For our method, by solving (3.6),a 1 = [ 1 √ 5 ; 2 √ 5 ], a 2 = [ 2 √ 5 ; 1 √ 5 ].The corresponding matrix A is given by A = [a 1 , a 2 ] ⊤ . In this setting, all methods converge to the PF, and our method takes the least number of iterations (PMTL takes 100, EPO Search takes 60, and our method takes only 10 iterations). PMTL does not align exactly with the preference vectors, while EPO and our method do. In Figures 4d-4f , PMTL and our method take 200 iterations, EPO Search takes 80 iterations. Results show that for the green and yellow preferences, PMTL moves further away from the PF in the first stage, and does not perform any update in the second stage. It converges to the PF only in 2 out of 4 cases. In contrast, with controlled ascent updates, EPO and our method can converge to the PF and trace the PF until the objectives align exactly with the preferences.Multi-patch image classification. Following [24, 30, 33] , we consider three datasets for image classification, including Multi-MNIST, Multi-Fashion, and Multi-Fashion+MNIST. The two tasks or objectives in all three datasets are to classify the top-left and the bottom-right images, respectively. For a fair comparison, we use LeNet as the backbone neural network. The training losses and accuracies of different methods given different preference vectors are plotted in Figure 5 . Experiments for our method are repeated 5 times. Hypervolumes with means and standard deviations are reported in Table 2 . The results for other methods in Table 2 are referenced from [33] .One limitation of EPO is that the preference is defined as a ray from the origin in the objective space, whose corresponding objectives can be unattainable, e.g., the yellow preferences in Figure 5 . As a result, the losses of all methods are far away from the preference vectors. In this case, a more flexible choice of preferences is helpful to ensure preference satisfaction. To demonstrate this, we conduct experiments with more flexible preferences; see the results in Figure 6 , where the obtained solutions align better with the preference lines compared to those in Figure 5 . Moreover, it can perform controlled ascent updates during optimization, which cannot be achieved by PMTL or XWC-MGDA. Emotion recognition. We apply our method to predict 6 types of emotions from 593 songs on the Emotions and Music dataset [41] . We follow the experiment settings in [30] , with more details summarized in Appendix H.2. The hypervolumes are reported in Table 2 . Multi-lingual speech recognition. We further apply the proposed method to the multiobjective finetuning of pre-trained multilingual speech models. We use the Librispeech (100 hours) [36] , and AISHELL v1 [5] datasets for multi-lingual speech recognition. A conformer with 8 blocks is used as the model architecture. The total number of parameters is around 64.5M with 58.4M encoder layer parameters and the rest being the classification layer parameters. We consider the objectives associated with the speech recognition Connectionist Temporal Classification (CTC) losses in Chinese and English, denoted as f ch t and f en t , respectively. We also use the self-supervised Contrastive Predictive Coding (CPC) loss f p for representation learning; that ismin θ F (θ) := fp(θ), f ch t (θ), f en t (θ) ⊤ s.t. fp(θ) ≤ ϵ1, f ch t (θ) -f en t (θ) = ϵ2 (5.2)where the first constraint ensures to learn a good representation with ϵ 1 = 1.2, and the second constraint avoids one language loss dominates the other with ϵ 2 = 0.5; see more details in Appendix H.1.Results on the word error rate (WER) are reported in Table 3 . The baselines include the state-of-the-art result from Komatsu et al. [20] without an additional large language model, our own implementation of training using only the sum of supervised CTC losses (w/o CPC), the initial pre-trained M2ASR model [39] (init.), linear scalarization of all three objectives for finetuning a pre-trained model with the CPC loss (LS-FT). Results show that considering CPC loss besides the supervised CTC loss improves the average WER by 4.2%, and this can be further improved by 0.3% by finetuning with linear scalarization. However, the LS-FT model has a much better performance in Chinese compared to English. With our proposed approach, the performance gap between different languages is reduced, and the average WER is further improved by 1.3%. 
conclusions: 
 In this work, we frame preference-guided multi-objective learning as a constrained vector optimization problem. Specifically, we introduce constraints and partial order to capture the absolute and relative preferences. Under this framework, we develop algorithms to solve the constrained vector optimization problem. Our proposed algorithms use a unified formulation without solving different subprograms at different stages. And they enjoy the benefit of allowing controlled ascent and escaping weak optimal solutions. Theoretical guarantees on the non-asymptotic convergence of the deterministic algorithms and their stochastic variants are provided. Experiments on benchmark datasets demonstrate the broad applicability of the proposed algorithms. 
 
 Appendix: This paper casts the preference-guided multi-objective learning as a constrained vector optimization problem and proposes an algorithm with stochastic variants and non-asymptotic convergence guarantees to solve the problem. The proposed method is applied to image classification, speech recognition, and emotion classification. The positive impact is that it is a principled method that has broad applications across various domains. There is no negative social impact.The proposed algorithm is able to model flexible preferences but at a cost of higher per-iteration complexity compared to scalarization methods. The theoretical guarantees make standard assumptions that the objectives are lower bounded, Lipschitz continuous and smooth. These are common assumptions in the optimization literature, and can be satisfied for neural networks with smooth activation functions.Appendix for " FERERO: A Flexible Framework for Preference-Guided Multi-Objective Learning " A summary of notations used in this work is listed in Table 4 for ease of reference.Recall that given vectors v, w, we use v < w and v ≤ w to denote v i < w i for all i, and v i ≤ w i for all i, respectively. We use v ⪇ w to denote v ≤ w and v ̸ = w, and define >, ≥, ⪈ analogously.In the proof, we use ∥ • ∥ to denote the ℓ 2 -norm, and ∥ • ∥ 1 to denote the ℓ 1 -norm. We use | • | ab to denote the operator that takes element-wise absolute value of a matrix. We use 1 and 0 to denote the all-one and all-zero vectors, respectively. Their dimensions are specified only when they are not clear in the context. We use [v, w] to represent column concatenation of matrices or vectors, and use [v; w] to represent row concatenation of matrices or vectors.In this section, we provide a detailed review and comparison of additional related works in multitask/objective learning, vector optimization, and Pareto front approximation. f ξ,m (θ), fm(θ)A scalar-valued objective function evaluated on data point ξ, with f ξ,m : R q → R, or on dataset D, fm, with fm := 1|D| ξ∈D f ξ,m (θ) ∇fm(θ)Gradient of fm(θ), with ∇fm : R q → R q F ξ (θ), F (θ) A vector-valued objective function evaluated on data point ξ, with F ξ : R q → R M , or on dataset D, withF := 1 |D| ξ∈D F ξ (θ) ∇F (θ)Gradient of F (θ), with ∇F : R q → R q×M αStep size to update model parameter θ γStep size to update multiplier λIn this section, we provide an extended discussion of the works that are closely related to ours.Pareto front approximation. Pareto front approximation aims to find multiple different solutions whose objective values approximate the Pareto front. Scalarization-based methods can be used to approximate the Pareto front by enumerating different weights of the objectives. However, they cannot find solutions on the nonconvex part of the Pareto front [32] . Decomposition-based methods partition the objective space into different subsets with constraints that represent different trade-off preferences, and solve the constrained multi-objective optimization subproblems with gradientbased or evolutionary algorithms [24, 15] . Probabilistic inference methods update a set of models following a distribution that converges to Pareto stationary [27, 38] . The expected update direction of the models typically follows the steepest common descent direction for all objectives. Pareto set learning methods use a neural network to learn a mapping from user preferences to corresponding models. The learned neural network is able to generate different models with different input user preferences [34, 42, 21, 22] .Preferences as linear constraints of objectives. Different constraints S partition the objectives into sub-regions, as shown in Figure 1 . Many preferences can be modeled by linear equality or inequality constraints [24, 30, 33] . For example, below we list different choices of C for different methods in Figure 1 .(a) B g = [0, I 2:M ] ⊤ ∈ R M ×M , b = -[0, ϵ 2 , . . . , ϵ M ] ⊤ ; (b) B h ∈ R (M -1)×M , b = 0;In Figure 1a , the preferences are based on the function values of f 1 controlled by different thresholds, corresponding to the inequality constraints defined by (a). In Figure 1b , the constraints are that the objectives F (θ) should lie on one of the preference vectors v, therefore should satisfy the equality constraint B h F (θ) = 0.Detailed comparison with the most relevant works. Below we provide a fine-grained comparison with some existing works in Table 5 , as an extension of Table 1 .In terms of preference modeling, the scalarization-based methods such as Linear Scalarization and Smooth Tchebycheff scalarization use weight of different objectives to model preferences. They are not flexible enough to capture preferences illustrated in Figure 1 . PMTL uses a constrained multi-objective optimization formulation, with preferences modeled by inequalities. EPO models the preference by an r -1 ray, same as the example given in Figure 1b . (X)WC-MGDA uses a shifted ray not necessarily from the origin to model the preferences. In all of these works, they only model the absolute preferences that define the preferred objective values. In contrast, we also consider the relative preference that define the relative improvement directions of objectives.In addition to the comparison in Table 1 , our framework enjoys additional benefits including the ability to escape weak optimal solutions and to maintain scale-invariance. These abilities are attributed to the subprogram that is adaptive to the objective values, as detailed in Lemma 4. ✗ ✓ ✗ ✗ - (Smooth) Tchebycheff [23] ✓ ✗ ✓ ✗ ✗ - PMTL [24] ✓ ✗ ✗ ✗ ✗ assume LICQ EPO [30] ✓ ✗ ✗ ✗ ✓ ✗ (X)WC-MGDA [33] ✓ ✗ ✗ ✗ ✓ ✗ FERERO (ours) ✓ ✓ ✓ ✓ ✓ prove calmnessBelow, we further summarize the reasons behind the benefits of our proposed method. We use "→" to indicate the reasons on the left and the corresponding benefits on the right.Flexible preference               In this section we introduce preliminaries on the general cone-induced partial ordering and the corresponding optimality conditions for completeness since we use these concepts in our proofs.Then we discuss the relation between the Pareto optimality and the optimality induced by a general polyhedral cone.In this section, we introduce basic definitions, lemmas, propositions, and theorems in vector optimization, including the cone-induced partial ordering, the minimum and weakly minimum associated with the partial ordering in real linear space, and necessary conditions for minimum. These concepts are defined in [19] . We restate them following our notations for completeness. We denote Z as a real linear space, C, S as subsets in Z, and w, x, y, z as points or elements in Z, 0 Z as the zero vector in the space Z.Definition 3 (Cone). Let C be a nonempty subset of a real linear space Z.The set C is called a cone, if y ∈ C, λ ≥ 0 =⇒ λy ∈ C. Lemma 3 (Convex cone). A cone C in a real linear space is convex if and only if C + C ⊂ C.Definition 4 (Partially ordered linear space). A real linear space equipped with a partial ordering is a partially ordered linear space.Theorem 5. (a) If ≤ is a partial ordering on Z, then the setC := {z ∈ Z | 0 Z ≤ z} is a convex cone. If, in addition, ≤ is antisymmetric, then C is pointed. (b) If C is a convex cone in Z, then the binary relation ≤ C := {(x, y) ∈ Z × Z | y -x ∈ C} is a partial ordering on Z. If, in addition, C is pointed, then ≤ C is antisymmetric.Definition 5 (Ordering cone). A convex cone characterizing a partial ordering in a real linear space is an ordering cone.Definition 6 (Cone-induced partial ordering). Let C be a closed pointed convex cone of R M , with nonempty interior. The partial order in R M induced by C, ≤ C is defined byu ≤ C v, if v -u ∈ C. (C.1)The relation induced by int(C) in R M , < C is defined by u < C v, if v -u ∈ int(C). (C.Definition 8 (C-stationary). A point θ ∈ R q is C-stationary if there is no first-order common descent direction d ∈ R q that ∇F (θ) ⊤ d ∈ -int(C), i.e., range(∇F (θ) ⊤ ) ∩ (-int(C)) = ∅.Note that, whenC = R M + := {z ∈ R M | z m ≥ 0 for all m ∈ [M ]}, C-minimum and C-weakly minimum in Definition 7 are Pareto minimum and weakly Pareto minimum, respectively. Recall that F : R q → R M is a continuously differentiable function. The problem we consider is to find the unconstrained C-minimizers of F , denoted as min C F (θ) with θ ∈ R q . We then proceed to introduce the relation between C-stationarity and Pareto stationarity in this section. Following similar arguments, 2) can also be proved.In this section, we provide proof of the main theoretical results in this paper.Proof of subprogram reformulation. Define the Lagrangian functionL(c, d, λ f , λ g , λ h ) :=c + 1 2 ∥d∥ 2 + λ ⊤ f A∇F (θ) ⊤ d -c(1 ⊤ AF (θ)) -1 AF (θ) + λ ⊤ g B g ∇F (θ) ⊤ d + c g G(θ) + λ ⊤ h B h ∇F (θ) ⊤ d + c h H(θ) (D.1)whereλ f ∈ R M + , λ g ∈ R Mg + , λ h ∈ R M h. By the first-order optimality condition w.r.t. d and c, we can obtain thatd * + ∇F (θ)(A ⊤ λ * f + B ⊤ g λ * g + B ⊤ h λ * h ) = 0; (D.2) 1 ⊤ AF (θ) -λ * f ⊤ AF (θ) = 0. (D.3)Combining the last equation with λ f ∈ R M + , we obtain λ * f ∈ Ω λ f . Plugging the above results into the Lagrangian function gives[λ * f ; λ * g ; λ * h ] ∈ arg min [λ f ;λg;λ h ]∈Ω λ 1 2 ∥∇F (θ)(A ⊤ λ f + B ⊤ g λ g + B ⊤ h λ h )∥ 2 -c g λ ⊤ g G(θ) -c h λ ⊤ h H(θ) (D.4)which leads to the dual form in (2.3). Since (2.1) is a constrained convex optimization problem where Slater's condition holds, therefore, the duality gap is zero.We then discuss the first-order necessary optimality conditions for problem (PMOL). We begin the discussion with the geometric notions of improving and feasible directions.Improving directions. The improvement directions are defined as generalized common descent directions so that the iterates strictly improve or dominate the previous iterates based on C A , i.e., F (θ t ) -F (θ t+1 ) ∈ int(C A ). Denote d t ∈ R q as an update direction at iteration t, and α t > 0 as the step size at the t-th iteration. The general update equation given update direction d t isθ t+1 = θ t + α t d t .Based on first-order Taylor expansion, the amount of improvement at iteration t can be approximately expressed asF (θ t ) -F (θ t+1 ) ≈ -α t ∇F (θ t ) ⊤ d t ∈ int(C A ). We term such directions the general C A -improving directions. The cone of C A -improving directions at x isD C A = {d ∈ R q | ∇F (θ) ⊤ d ∈ -int(C A )}. (D.5)When A = I M , they are common descent directions.Feasible directions. Similar to the concept in constrained single objective optimization, the feasible directions are those that ensure F (θ t + α t d t ) ∈ S. We rewrite problem (PMOL) with explicit C A -induced partial ordering asmin C A F (θ) s.t. G(θ) ≤ 0, H(θ) = 0. PMOLwhere G : R q → R Mg , H : R q → R M h are linear functions of F , and are differentiable. Let I = {i | G i (θ) = 0} be the index set of the active inequality constraints in G(θ), andG I (θ) = [• • • , G i (θ), • • • ] ⊤ for i ∈ I.A subset of the feasible directions described by the gradients of the equality and active inequality constraints at θ is given byD g = {d ∈ R q | ∇G I (θ) ⊤ d < 0}, D H = {d ∈ R q | ∇H(θ) ⊤ d = 0}. (D.6)A necessary optimality condition is that there exists no feasible and improving directions at θ, i.e., D C A ∩ D g ∩ D h = ∅. An algebraic description of the necessary optimality conditions for (PMOL) is summarized below. Proposition 2 (First-order necessary optimality conditions for (PMOL)).Let C A := {y ∈ R M | Ay ≥ 0} that satisfies int(C A ) ̸ = ∅. If θ solves (PMOL) locally, then there exists λ f ∈ R M + , λ g ∈ R Mg + , [λ f ; λ g ] ̸ = 0, and λ h ∈ R M h that ∇F ( θ)A ⊤ λ f + ∇G( θ)λ g + ∇H( θ)λ h = 0, and λ ⊤ g [-G( θ)] + = 0 (D.7)Proof of Proposition 2. The geometric description D C A ∩ D g ∩ D h = ∅ is equivalent to that the linear system below w.r.t. d is inconsistentA∇F ( θ) ⊤ ∇G I ( θ) ⊤ d < 0 and ∇H( θ) ⊤ d = 0. (D.8)By the Motzkin's transposition theorem, system (D.8) being inconsistent is equivalent to that the following linear system w.r.t. p, λ h has a solution with p ⪈ 0∇F ( θ)A ⊤ ∇G I ( θ) p + ∇H( θ)λ h = 0. (D.9) Letting p = [λ f ; λ g,I ], where λ g,I = [• • • ; λ g,i ; • • • ], i ∈ I, and λ g,i ′ = 0, for all i ′ / ∈ I completes the proof. Remark 6. Notice that, Proposition 2 provides a Fritz John (FJ)-type first-order necessary optimality condition, which has been discussed in prior works such as [43, Theorem 1.2] with additional variational inequality constraints, and [16, Section 3, (2)-( 5)] with inequalities constraints only. In the FJ-type necessary optimality condition, the multiplier λ f associated with the objective F (θ) can be zero if |I| ≥ 1, which is undesirable. We need additional constraint qualifications to ensure the condition in (D.7) with λ f ̸ = 0 is also a necessary optimality condition, i.e., the KKT condition, which is equivalent to µ 0 = 1, and without considering the variational inequality constraints in [43, Theorem 1.2] . The constraint qualification is discussed in detail in Appendix D.3.2.In this section, we discuss the properties of PMOL and their proofs. These include the properties of the subprogram in Lemma 1, and the calmness CQ of PMOL in Lemma 2.Lemma 4 (Additional properties of the subprogram). For the subprogram (2.3), the following properties hold: 1. The solution d * (θ) is unique. 2. If θ is a local weak optimal solution with AF (θ) > 0, then d * (θ) = 0, ψ(θ) = 0. Otherwise, if θ is not a local weak optimal solution, then d * (θ) ̸ = 0, ψ(θ) < 0, and when θ is feasible,2ψ(θ) ≤ -∥d * (θ)∥ 2 < 0.(D.10) 3. (Ability to escape weak optimal solutions). Let θ be a weak optimal solution, with (AF (θ)) m = 0 for some m ∈ [M ]. If there exists feasible and non-strictly improving directions at θ with A∇F (θ) ⊤ d ⪇ 0, then d * (θ) ̸ = 0, ψ(θ) < 0. Otherwise, if there exists no feasible and non-strictly improving directions at θ with A∇F (θ) ⊤ d ⪇ 0, then d * (θ) = 0, ψ(θ) = 0. 4. (Scale invariance) Suppose there are only equality constraints, i.e., M g = 0, and M h = M -1, B h is full row rank and is selected such that B h (F (θ 1 ) -F (θ 2 )) = 0 with F (θ 1 ), F (θ 2 ) being two different reference points in the objective space. For all θ ∈ R q that are feasible, i.e., H(θ) = 0, when A = I, the normalized solution d * (θ)/∥d * (θ)∥ does not change when the objective F (θ) is scaled by an arbitrary positive diagonal matrix.Proof of Lemma 4. For Property-1, the uniqueness of d * (θ) follows from the strict convexity of the objective function w.r.t. the direction d.For Property-2, in the first case if θ is a local optimal solution, by definition, there exists no feasible and improving directions d such that A∇F (θ) ⊤ d < 0. Let Ω d (θ) be the set of d ∈ R q that satisfy the constraints in (2.1), i.e.,Ω d (θ) := {d ∈ R q | B g ∇F (θ) ⊤ d + c g G(θ) ≤ 0, B h ∇F (θ) ⊤ d + c h H(θ) = 0}. (D.11) Then, since AF (θ) > 0, for all d ∈ Ω d (θ), max m∈[M ] (A∇F (θ) ⊤ d) m ≥ 0 (D.12)and maxm∈[M ] (A∇F (θ) ⊤ d) m /(AF (θ)) m ≥ 0. (D.13)And since AF (θ) > 0, it holds that ψ(θ) := min(d,c)∈Ω d (θ)×R c + 1 2 ∥d∥ 2 = min d∈Ω d (θ) max m∈[M ] (A∇F (θ) ⊤ d) m (1 ⊤ AF (θ))/(AF (θ)) m + 1 2 ∥d∥ 2 ≥ 0 (D.14)with ψ(θ) = 0 attainable by taking d = 0 ∈ Ω d (θ). The first case of Property-2 is proved.In the second case, if θ is not a local weak optimal solution, then there existsd ∈ Ω d (θ) such that A∇F (θ) ⊤ d < 0. Taking σ = -max m∈[M ] (A∇F (θ) ⊤ d) m (1 ⊤ AF (θ))/ (AF (θ)) m ∥d∥ 2 , and d σ = σd, then ψ(θ) := min (d,c)∈Ω d (θ)×R c + 1 2 ∥d∥ 2 = min d∈Ω d (θ) max m∈[M ] (A∇F (θ) ⊤ d) m (1 ⊤ AF (θ))/(AF (θ)) m + 1 2 ∥d∥ 2 = max m∈[M ] (A∇F (θ) ⊤ d * (θ)) m (1 ⊤ AF (θ))/(AF (θ)) m + 1 2 ∥d * (θ)∥ 2 < max m∈[M ] (A∇F (θ) ⊤ d σ ) m (1 ⊤ AF (θ))/(AF (θ)) m + 1 2 ∥d σ ∥ 2 =σ max m∈[M ] (A∇F (θ) ⊤ d) m (1 ⊤ AF (θ))/(AF (θ)) m + 1 2 σ 2 ∥d∥ 2 = - 1 2 σ 2 ∥d∥ 2 < 0. (D.15) Thus d * (θ) ̸ = 0. Recall that d * (θ) = -∇F (θ) A ⊤ λ * f + B ⊤ g λ * g + B ⊤ h λ * h (D.16)where by the feasibility and optimality conditions,λ * h ⊤ B h ∇F (θ) ⊤ d * (θ) + c h H(θ) =0, (D.17a) λ * g ⊤ B g ∇F (θ) ⊤ d * (θ) + c g G(θ) =0, (D.17b) λ * f ⊤ A∇F (θ) ⊤ d * (θ) -c * (1 ⊤ M AF (θ)) -1 AF (θ) =0. (D.17c)Combining the above with (D.16), we have∥d * (θ)∥ 2 = -d * (θ) ⊤ ∇F (θ) A ⊤ λ * f + B ⊤ g λ * g + B ⊤ h λ * h = -d * (θ) ⊤ ∇F (θ)A ⊤ λ * f + c h λ * h ⊤ H(θ) + c g λ * g ⊤ G(θ) ≤ -c * (θ)(1 ⊤ AF (θ)) -1 λ * f ⊤ AF (θ) = -c * (θ) (D.18)where the last inequality uses the fact that θ is feasible, and G(θ) ≤ 0, H(θ) = 0.Then it holds that2ψ(θ) = 2c * (θ) + ∥d * (θ)∥ 2 ≤ -∥d * (θ)∥ 2 < 0. (D.19)Therefore, Property-2 holds.For Property-3, let I ⊆ [M ] be the set such that (AF (θ)) m = 0 for all m ∈ I, then (2.1) is equivalent toψ(θ) = min (d,c)∈R q ×R c + 1 2 ∥d∥ 2 SP1w s.t. (A∇F (θ) ⊤ d) m -c(1 ⊤ AF (θ)) -1 (AF (θ)) m ≤ 0, for all m ∈ [M ] \ I (A∇F (θ) ⊤ d) m ≤ 0, for all m ∈ I B g ∇F (θ) ⊤ d + c g G(θ) ≤ 0 B h ∇F (θ) ⊤ d + c h H(θ) = 0In the first case, if there exists feasible and non-strictly improving directions at θ with A∇F (θ = min) ⊤ d ⪇ 0, then such d ̸ = 0, d ∈ Ω d .d∈Ω d (θ) max m∈[M ]\I (A∇F (θ) ⊤ d) m (1 ⊤ AF (θ))/(AF (θ)) m + 1 2 ∥d∥ 2 < max m∈[M ]\I (A∇F (θ) ⊤ d σ ) m (1 ⊤ AF (θ))/(AF (θ)) m + 1 2 ∥d σ ∥ 2 =σ max m∈[M ]\I (A∇F (θ) ⊤ d) m (1 ⊤ AF (θ))/(AF (θ)) m + 1 2 σ 2 ∥d∥ 2 = - 1 2 σ 2 ∥d∥ 2 < 0. (D.20)And the corresponding d * (θ) ̸ = 0.In the second case, if there exists no feasible and non-strictly improving directions at θ, then for all d ∈ Ω d (θ), = mind∈Ω d (θ) max m∈[M ]\I (A∇F (θ) ⊤ d) m (1 ⊤ AF (θ))/(AF (θ)) m + 1 2 ∥d∥ 2 ≥ 0 (D.23) with ψ(θ) = 0 if and only if d = 0 ∈ Ω d (θ).Combining the above arguments, Property-3 is proved.For Property-4, let d * (θ) be the solution to the original problem (2.1) without inequality constraints.Using the fact that H(θ) = 0, and lettingλ = A ⊤ λ f + B ⊤ h λ h = λ f + B ⊤ h λ h ,then the original dual problem can be written asd * (θ) = -∇F (θ)λ * s.t. λ * ∈ arg min λ∈Ωλ(θ) φ(λ; θ) := 1 2 ∥∇F (θ)λ∥ 2 (D.24)where whereΩ λ(θ) = Ω λ f (θ) + B ⊤ h R M h , and Ω λ f (θ) = {λ f ∈ R M + | λ f ⊤ F (θ) = 1 ⊤ F (θ)}.Ω λ(θ; Λ) = Ω λ f (θ; Λ) + B ′ h ⊤ R M h , and Ω λ f (θ; Λ) = {λ f ∈ R M + | λ f ⊤ ΛF (θ) = 1 ⊤ ΛF (θ)}. Letting λ ′ = Λλ, then d * (θ) = -∇F (θ)λ ′ * s.t. λ ′ * ∈ arg min λ ′ ∈Ωλ′ (θ;Λ) φ(λ; θ) := 1 2 ∥∇F (θ)λ ′ ∥ 2 (D.26)whereΩ λ′ (θ; Λ) = Λ Ω λ f (θ; Λ) + ΛB ′⊤ h R M h . The set Λ Ω λ f (θ; Λ) can be written as Λ Ω λ f (θ; Λ) ={Λλ f | λ f ∈ R M + , λ f ⊤ ΛF (θ) = 1 ⊤ ΛF (θ)} ={λ ′ f ∈ R M + | F (θ) ⊤ λ f ′ = 1 ⊤ ΛF (θ)}. (D.27)Notice that,F (θ) ⊤ λ f ′ = 1 ⊤ ΛF (θ) = 1 ⊤ F (θ)c s (D.28)wherec s = 1 ⊤ ΛF (θ)/(1 ⊤ F (θ)). Therefore, Λ Ω λ f (θ; Λ) = c s Ω λ f (θ) .Also note that, B h ∈ R (M -1)×M is full row rank, and is selected based on F (θ), which satisfiesB h (F (θ 1 ) -F (θ 2 )) = 0 (D.29)where F (θ 1 ), F (θ 2 ) are two reference points which fully defines the kernel of B h . Similarly, whenF (θ) is scaled by Λ, the corresponding B ′ h satisfies B ′ h Λ(F (θ 1 ) -F (θ 2 )) = 0. (D.30)This further impliesΛB ′ h ⊤ (R M h ) = range(ΛB ′ h ⊤ ) = ker(B ′ h Λ) ⊥ = ker(B h ) ⊥ = B h (R M h ) = c s B h (R M h ). (D.31) Combining with Λ Ω λ f (θ; Λ) = c s Ω λ f (θ) , it holds that Ω λ′ (θ; Λ) = c s Ω λ(θ). (D.32)Therefore, the solution of λ and λ ′ is only subject to a scaling factor, which does not change the direction of d * (θ). This proves Property-4, the scale invariance.D.3.2 Proof of Lemma 2: calmness of PMOL Example 1. Let F : R q → R 2 .Consider the problem below as a special case of (PMOL), given bymin R 2 + F (θ) s.t. f 2 (θ) = min f 2 (θ). (D.33)For θ = arg min θ∈R q f 2 (θ), we have ∇f 2 ( θ) = 0, and θ satisfies (D.7) with λ = [0, 1] ⊤ ̸ = 0 and λ h = 1. However, ∇H( θ) = ∇f 2 ( θ) = 0 violates the LICQ, the Slater's CQ, and the MFCQ.Below we restate the definition of the Calmness condition for PMOL [43] , which generalizes the calmness condition in single-objective optimization. Definition 9 (Calmness condition for PMOL [43, Restatement of Definition 4.5]). Let θ be a local solution to (PMOL). We say the PMOL problem satisfies the calmness condition at θ provided that there exists ϵ > 0 and a Lipschitz function ϕ : R Mg+M h → R M satisfying ϕ(0, 0) = 0 such that there exists no (θ, p, q) ∈ [( θ, 0, 0) + ϵB]/{( θ, 0, 0)} satisfyingG(θ) + p ≤ 0, (D.34a) H(θ) + q = 0, (D.34b) F (θ) -F ( θ) + ϕ(p, q) ∈ -int(C A ). (D.34c)Our proof relies on the following general version of Hoffman error bound, which bounds the distance of a point to a nonempty solution set defined by constraints by a measure of the constraint violation of the point. Lemma 5 (Relative form of Hoffman error bound [37, Proposition 5] ).Given B h ∈ R k H ×M , b h ∈ R k H , B g ∈ R k G ×M , b g ∈ R k G , define Σ(p, q) := {y ∈ R M | B g y + b g ≤ p, B h y + b h = q}, and dom Σ := {(p, q) | Σ(p, q) ̸ = ∅}.Let Ω R ⊆ R M be a reference polyhedron (e.g., one defined by the intersection of half-spaces). Then for all u ∈ Ω R , and (p, q) ∈ dom Σ, there exists a relative Hoffman constant c hof depending only onB g , B h , Ω R such that dist(u, Σ(p, q) ∩ Ω R ) ≤ c hof (B g , B h | Ω R ) (B g u + b g -p) + B h u + b h -q (D.35)where (B g u + b g -p) + := max{0, B g u + b g -p} which replaces each negative component of B g u + b g -p by zero, and dist(u, Ω) := inf u ′ ∈Ω ∥u -u ′ ∥. Proof of Lemma 2. We first construct ϕ(p, q) = c hof ∥[p ⊤ , q ⊤ ] ⊤ ∥A -1 1 M, where c hof is the Hoffman constant upper bound in Lemma 5. Then ϕ(0, 0) = 0, and ϕ(p, q) is Lipschitz because∥ϕ(p, q) -ϕ(p ′ , q ′ )∥ ≤c hof M ∥A -1 ∥ p q - p ′ q ′ ≤c hof M ∥A -1 ∥ p -p ′ q -q ′ . (D.36)Next we prove the PMOL calmness condition holds by contradiction. Suppose for every ϵ > 0, there exists ( θ, p, q) ∈ [( θ, 0, 0) + ϵB]/{( θ, 0, 0)} satisfying (D.34).Define Ω F1 := {F (θ) ∈ Σ(0, 0) | θ ∈ R q } ̸ = ∅, there exists θ ∈ R q such that F ( θ) ∈ Ω F1 and ∥F ( θ)∥ < ∞. We then consider the following two cases: Case 1: F ( θ) ∈ Σ(0, 0). In this case, ( θ, p, q) = ( θ, 0, 0) ̸ = ( θ, 0, 0), thus θ ̸ = θ. Take θ = θ ̸ = θ. Case 2: F ( θ) / ∈ Σ(0, 0). Take θ such that F ( θ) ∈ Ω F1 , then F ( θ) ̸ = F ( θ).In both cases, let Ω R be the convex hull of {F ( θ), F ( θ)}, i.e., Ω R = conv({F ( θ), F ( θ)}). Then Ω R is a line segment (or reduces to a point in case 1), thus a polyhedron. Since Σ(0, 0) is a line,F ( θ) ∈ Σ(0, 0) ∩ Ω R , thus Σ(0, 0) ∩ Ω R = Ω R = {F ( θ)} in case 1, and Σ(0, 0) ∩ Ω R = {F ( θ)} in case 2.Therefore, in both cases,∥F ( θ) -F ( θ)∥ = dist(F ( θ), Σ(0, 0) ∩ Ω R ) (D.37)where dist(F, Ω) := inf F ′ ∈Ω ∥F -F ′ ∥.We also havedist(F ( θ), Σ(0, 0) ∩ Ω R ) (a) ≤ c hof (Ω R ) (B g F ( θ) + b g ) + B h F ( θ) + b h (b) ≤c hof (-p) + -q ≤ c hof p q (D.38)where (a) follows from Lemma 5; (b) follows from (D.34) that 0 ≤ (B g F ( θ) + b g ) + ≤ (-p) + , B h F ( θ) + b h = -q, and that c hof (Ω R ) ≤ c hof for different bounded Ω R .Multiplying ∥A∥1 M on both sides of the above inequality yields∥A∥dist(F ( θ), Σ(0, 0) ∩ Ω R )1 M ≤ Aϕ(p, q). (D.39)It can then be derived thatAF ( θ) -AF ( θ) ≤∥AF ( θ) -AF ( θ)∥1 M ≤ ∥A∥∥F ( θ) -F ( θ)∥1 M ≤∥A∥dist(F ( θ), Σ(0, 0) ∩ Ω R )1 M ≤ Aϕ(p, q). (D.40)By rearranging the above inequality and applying (D.34c), we have thatAF ( θ) ≤ AF ( θ) + Aϕ(p, q) < AF ( θ) (D.41)which contradicts to that θ is a global solution to (PMOL).Therefore, the PMOL calmness condition in Definition 9 is satisfied.Recall that, we let λ = [λ f ;λ g ; λ h ] ∈ R M +Mg+M h , A ag = [A; B g ; B h ] ∈ R (M +Mg+M h )×M, and use the following concise notationd * (θ) = -∇F (θ)A ⊤ ag λ * (θ) s.t. λ * (θ) ∈ arg min λ∈Ω λ (θ) φ(λ; θ) := 1 2 ∥∇F (θ)A ⊤ ag λ∥ 2 -c g λ ⊤ g G(θ) -c h λ ⊤ h H(θ) (E.1)whereΩ λ (θ) = Ω λ f (θ) × R Mg + × R M h , and Ω λ f (θ) = {λ f ∈ R M + | λ f ⊤ AF (θ) = 1 ⊤ AF (θ)}.In the following discussion in this section, we first present the supporting lemmas and their proofs, then provide the proof of Theorem 1.Lemma 6 is a result from the smoothness of F (θ), and thus the smoothness of G(θ) and H(θ), whose smoothness constants depend on B g and B h , respectively. Lemma 6. Suppose Assumptions 1, 2 hold. Then for all θ, θ ′ ∈ R q , and all λ f ∈ R M , we haveλ ⊤ f AF (θ t+1 ) -λ ⊤ f AF (θ t ) ≤α t λ ⊤ f A∇F (θ t ) ⊤ d t + ℓ f,1 ∥A ⊤ λ f ∥ 1 2 α 2 t ∥d t ∥ 2 (E.2) G(θ t+1 ) -G(θ t ) ≤α t ∇G(θ t ) ⊤ d t + ℓ f,1 2 α 2 t ∥B ⊤ g ∥ ∞,1 ∥d t ∥ 2 1 (E.3) H(θ t+1 ) -H(θ t ) ≤α t ∇H(θ t ) ⊤ d t + ℓ f,1 2 α 2 t ∥B ⊤ h ∥ ∞,1 ∥d t ∥ 2 1. (E.4) Proof. By Assumption 2, it holds that λ ⊤ f AF (θ) is ∥A ⊤ λ f ∥ 1 ℓ f,1 -smooth.By the definition of smoothness, we haveλ ⊤ f AF (θ t+1 ) ≤ λ ⊤ f AF (θ t ) + α t λ ⊤ f A∇F (θ t ) ⊤ d t + ℓ f,1 ∥A ⊤ λ f ∥ 1 2 α 2 t ∥d t ∥ 2 . (E.5)Let B g,m and B h,m be the m-th row of B g and B h , respectively, then by the ℓ f,1 -smoothness ofF (θ), B g,m F (θ) is ℓ f,1 ∥B g,m ∥ 1 -smooth for all m ∈ [M g ]. Also because ∥B g,m ∥ 1 ≤ ∥B ⊤ g ∥ ∞,1 where ∥B ⊤ g ∥ ∞,1 = max m∈Mg ∥∥B g,m ∥ 1 ∥, g m (θ) is ℓ f,1 ∥B ⊤ g ∥ ∞,1 -smooth for all m ∈ [M g ]. By the definition of smoothness, it holds thatG(θ t+1 ) -G(θ t ) ≤α t ∇G(θ t ) ⊤ d t + ℓ f,1 2 α 2 t ∥B ⊤ g ∥ ∞,1 ∥d t ∥ 2 1. (E.6)Following similar arguments as the above for G(θ), (E.4) can be proved.Lemma 7. For the subprogram (2.3) or equivalently (E.1), it holds that for any λ ∈ Ω λ (θ),⟨∇F (θ)A ⊤ ag λ, ∇F (θ)A ⊤ ag λ * (θ)⟩ -[0 ⊤ , c g G(θ) ⊤ , c h H(θ) ⊤ ](λ -λ * (θ)) ≥ ∥∇F (θ)A ⊤ ag λ * (θ)∥ 2 . (E.7)Proof of Lemma 7. Since φ(λ; θ) is a convex function w.r.t. λ, by the first order optimality condition, it holds that for all λ ∈ Ω λ (θ)⟨∇ λ φ(λ * (θ); θ), λ -λ * (θ)⟩ ≥ 0 (E.8)which can be further written asλ ⊤ A ag ∇F (θ) ⊤ ∇F (θ)A ⊤ ag λ * (θ) -[0 ⊤ , c g G(θ) ⊤ , c h H(θ) ⊤ ](λ -λ * (θ)) ≥ ∥∇F (θ)A ⊤ ag λ * (θ)∥ 2 . (E.9)This completes the proof.We next prove Lemma 8, which can be viewed as a descent lemma for [G(θ)] + and |H(θ)| ab based on the smoothness of G(θ) and H(θ), as well as proper hyperparameter choices. This is crucial for proving the convergence result in Theorem ) ⊤ d t + c g G(θ t )] + ≤ ϵ1, (E.10) |∇H(θ t ) ⊤ d t + c h H(θ t )| ab ≤ ϵ1. (E.11) If α t ≤ min{c -1 g , c -1 h }, then it holds that [G(θ t+1 )] + -[G(θ t )] + ≤ -α t c g [G(θ t )] + + ℓ f,1 2 α 2 t ∥B ⊤ g ∥ ∞,1 ∥d t ∥ 2 1 + ϵ1 (E.12) |H(θ t+1 )| ab -|H(θ t )| ab ≤ -α t c h |H(θ t )| ab + ℓ f,1 2 α 2 t ∥B ⊤ h ∥ ∞,1 ∥d t ∥ 2 1 + ϵ1. (E.13)Proof. By the smoothness of G(θ) in Lemma 6 and ∇G(θ) ⊤ d+c g G(θ) ≤ [∇G(θ) ⊤ d+c g G(θ)] + ≤ ϵ1, it holds that G(θ t+1 ) -G(θ t ) ≤α t ∇G(θ t ) ⊤ d t + ℓ f,1 2 α 2 t ∥B ⊤ g ∥ ∞,1 ∥d t ∥ 2 1 + ϵ1 ≤ -α t c g G(θ t ) + ℓ f,1 2 α 2 t ∥B ⊤ g ∥ ∞,1 ∥d t ∥ 2 1 + ϵ1. (E.14) For all m ∈ [M g ], since G(θ t ) ≤ [G(θ t )] + , it holds that g m (θ t+1 ) -[g m (θ t )] + ≤g m (θ t ) -[g m (θ t )] + -α t c g g m (θ t ) + ℓ f,1 2 α 2 t ∥B ⊤ g ∥ ∞,1 ∥d t ∥ 2 + ϵ (E.15) ≤ -[-g m (θ t )] + -α t c g g m (θ t ) + ℓ f,1 2 α 2 t ∥B ⊤ g ∥ ∞,1 ∥d t ∥ 2 + ϵ. (E.16)It can be further derived that-[-g m (θ t )] + -α t c g g m (θ t ) = -α t c g g m (θ t ), g m (θ t ) ≥ 0 (1 -α t c g )g m (θ t ), g m (θ t ) < 0 ≤ -α t c g [g m (θ t )] + (E.17)where the last inequality holds since 1 -α t c g ≥ 0. Plugging this inequality back into (E. 16 ), yields that when g m (θ t+1 ) ≥ 0,[g m (θ t+1 )] + -[g m (θ t )] + ≤ -α t c g [g m (θ t )] + + ℓ f,1 2 α 2 t ∥B ⊤ g ∥ ∞,1 ∥d t ∥ 2 + ϵ. (E.18)When g m (θ t+1 ) < 0, we have[g m (θ t+1 )] + -[g m (θ t )] + ≤ -[g m (θ t )] + ≤ -α t c g [g m (θ t )] + ≤ -α t c g [g m (θ t )] + + ℓ f,1 2 α 2 t ∥B ⊤ g ∥ ∞,1 ∥d t ∥ 2 + ϵ. (E.19)Combining (E.18) and (E. 19 ) proves (E.12).By the smoothness of H(θ) and |∇H(θ) ⊤ d + c h H(θ)| ab ≤ ϵ1, we have |H(θ t+1 )| ab ≤|H(θ t ) -α t c h H(θ t )| ab + ℓ f,1 2 α 2 t ∥B ⊤ h ∥ ∞,1 ∥d t ∥ 2 1 + ϵ1 =(1 -α t c h )|H(θ t )| ab + ℓ f,1 2 α 2 t ∥B ⊤ h ∥ ∞,1 ∥d t ∥ 2 1 + ϵ1 (E.20)where the last equality holds because 1 -α t c h ≥ 0, which proves (E.13).Proof of Theorem 1. To consider both objective function minimization and constraint satisfaction, we define a Lyapunov function below with a constant vector λ = (λ f , λ g , λ h ) ∈ Ω λ (θ), whereλ f = 1, λ g ∈ R Mg + , λ h ∈ R M h , and λ g > λ * g (θ t ), λ h > λ * h (θ t ) for all t ∈ [T ]. V t := λ ⊤ f AF (θ t ) V f,t + λ ⊤ g [G(θ t )] + Vg,t + λ ⊤ h |H(θ t )| ab V h,t . (E.21) Note that V t ≥ 0 for all t since AF (θ) ≥ 0, λ f ≥ 0.For notation simplicity, we let d * t = d * (θ t ). From Assumption 2, the smoothness of the objectives, and Lemma 6, based on the update θ t+1 = θ t + α t d t , it holds thatV f,t+1 -V f,t (a) ≤ α t λ ⊤ f A∇F (θ t ) ⊤ d t + ℓ f,1 2 α 2 t ∥A ⊤ ∥ ∞,1 ∥d t ∥ 2 λ ⊤ f 1 (b) ≤α t λ ⊤ f A∇F (θ t ) ⊤ d * t + ℓ f,1 2 α 2 t ∥A ⊤ ∥ ∞,1 ∥d * t ∥ 2 λ ⊤ f 1 + ϵ1 (c) ≤ -α t ∥d * t ∥ 2 + α t c g λ * g (θ t ) ⊤ G(θ t ) + c h λ * h (θ t ) ⊤ H(θ t ) + ℓ f,1 2 α 2 t ∥A ⊤ 1∥ 1 ∥d * t ∥ 2 + ϵ1 (E.22)where (a) follows Lemma 6; (b) follows from that d t is an ϵ-optimal solution to the subprogram; (c) follows from Lemma 7 by settingλ = [1 ⊤ , 0 ⊤ , 0 ⊤ ] ⊤ ∈ Ω λ (θ).From Lemma 8, forα t ≤ min{c -1 g , c -1 h }, it holds that V g,t+1 -V g,t ≤ -α t c g λ ⊤ g [G(θ t )] + + ℓ f,1 2 α 2 t ∥B ⊤ g ∥ ∞,1 ∥d t ∥ 2 λ ⊤ g 1 + ϵλ ⊤ g 1 (E.23) V h,t+1 -V h,t ≤ -α t c h λ ⊤ h |H(θ t )| ab + ℓ f,1 2 α 2 t ∥B ⊤ h ∥ ∞,1 ∥d t ∥ 2 λ ⊤ h 1 + ϵλ ⊤ h 1. (E.24)Combining the above inequalities for V f,t , V g,t , V h,t , we haveV t+1 -V t ≤ -α t ∥d * t ∥ 2 + α t c g λ * g (θ t ) ⊤ G(θ t ) + c h λ * h (θ t ) ⊤ H(θ t ) + ℓ f,1 2 α 2 t ∥A ⊤ ag λ∥ 1 ∥d * t ∥ 2 -α t c g λ ⊤ g [G(θ t )] + -α t c h λ ⊤ h |H(θ t )| ab + ϵλ ⊤ 1 ≤ -α t ∥d * t ∥ 2 -α t c g (λ g -λ * g (θ t )) ⊤ [G(θ t )] + -α t c g λ * g (θ t ) ⊤ [-G(θ t )] + -α t c h (λ h -λ * h (θ t )) ⊤ |H(θ t )| ab + ℓ f,1 2 α 2 t ∥A ⊤ ag λ∥ 1 ∥d * t ∥ 2 + ϵλ ⊤ 1 (E.25)where the last inequality holds becauseλ * g (θ t ) ⊤ G(θ t ) = λ * g (θ t ) ⊤ [G(θ t )] + -λ * g (θ t ) ⊤ [-G(θ t )] + .Taking telescoping sum of the above inequality from t = 0, . . . , T -1 and rearranging, we haveT -1 t=0 α t 1 - 1 2 ∥A ⊤ ag λ∥ 1 ℓ f,1 α t ∥d * t ∥ 2 + α t c g (λ g -λ * g (θ t )) ⊤ [G(θ t )] + + α t c g λ * g (θ t ) ⊤ [-G(θ t )] + + α t c h (λ h -λ * h (θ t )) ⊤ |H(θ t )| ab ≤ V 0 -V T + T ϵλ ⊤ 1 ≤ V 0 + T ϵ∥λ∥ 1 . (E.26)Recall that α t ≤ 1/(ℓ f,1 ∥A ⊤ ag λ∥ 1 ). Plugging this into the above inequality yieldsT -1 t=0 1 2 α t ∥d * t ∥ 2 + α t c g (λ g -λ * g (θ t )) ⊤ [G(θ t )] + + α t c g λ * g (θ t ) ⊤ [-G(θ t )] + + α t c h (λ h -λ * h (θ t )) ⊤ |H(θ t )| ab ≤ V 0 + T ϵ∥λ∥ 1 . (E.27)Taking α t = Θ(1), then1 T T -1 t=0 1 2 ∥d * (θ t )∥ 2 + c g (λ g -λ * g (θ t )) ⊤ [G(θ t )] + + c g λ * g (θ t ) ⊤ [-G(θ t )] + + c h (λ h -λ * h (θ t )) ⊤ |H(θ t )| ab = O 1 T + ϵ . (E.28)The proof is complete.Next we show that the subprogram converges with a projected gradient descent (PGD) algorithm on λ with K iterations. Lemma 9 (Convergence of the subprogram with projected gradient descent). At the t-th iteration, given θ t , let {λ t,k } k be the sequence generated by the projected gradient descent algorithm to solve the subprogram min λ∈Ω λ (θt) φ(λ; θ t ), thenφ(λ t,K ; θ t ) -min λ∈Ω λ (θt) φ(λ; θ t ) ≤ ∥λ t,0 -λ * (θ t )∥ 2 2γK . (E.29)Proof. The result follows from the convergence result of projected gradient descent for convex objective functions. Note that at each iteration t, given θ t , Ω λ (θ t ) is fixed.Lemma 10. Suppose Assumption 3 holds. Due to the ℓ φ λ ,1 -smoothness and the convexity of the subprogram, it holds for all λ ∈ Ω λ (θ) that∥∇ λ φ(λ; θ) -∇ λ φ(λ * (θ); θ)∥ 2 ≤ 2ℓ φ λ ,1 φ(λ; θ) -φ(λ * (θ); θ) . (E.30)Proof. Since the objectives f m (θ) are Lipschitz continuous for all m ∈ [M ], the subprogram objective φ(λ; θ) is ℓ φ,λ,1 -smooth w.r.t. λ. By Proposition 1 (b) in [44] , it holds that1 2ℓ φ λ ,1 ∥∇ λ φ(λ; θ) -∇ λ φ(λ * (θ); θ)∥ 2 + ⟨∇ λ φ(λ * (θ); θ), λ -λ * (θ)⟩ ≤ φ(λ; θ) -φ(λ * (θ); θ). (E.31)By the convexity of φ(λ; θ) w.r.t. λ, for all λ ∈ Ω λ (θ),⟨∇ λ φ(λ * (θ); θ), λ -λ * (θ)⟩ ≥ 0. (E.32)Combining the above two inequalities proves the result.Corollary 7 (Convergence of Algorithm 1 with K-iteration PGD for the subprogram). Suppose Assumptions 1, 2 hold. Let {θ t } be the sequence produced by Algorithm 1 with the update θ t+1 = θ t + α t d t , where d t is the ϵ-optimal solution to the subprogram (2.1) obtained by K-iteration PGD for the subprogram on λ.Define λ := (λ f , λ g , λ h ) ∈ Ω λ (θ) with λ g ≥ λ * g (θ), λ h ≥ λ * h (θ) for all θ ∈ R q . If the step size α t ≤ 1/(ℓ f,1 ∥A ⊤ ag λ∥ 1 ) and α t = Θ(1), then T -1 t=T 1 2 ∥d * t ∥ 2 + c g (λ g -λ * g (θ t )) ⊤ [G(θ t )] + + c h (λ h -λ * h (θ t )) ⊤ |H(θ t )| ab = O 1 . (E.33)Proof. For t = 0, . . . , T -1, we take K = T 2 , applying Lemma 9, we haveφ(λ t,K ; θ t ) -min λ∈Ω λ (θt) φ(λ; θ t ) ≤ ∥λ t,0 -λ * (θ t )∥ 2 2γT 2 . (E.34)From Lemma 10, the above inequality implies∥∇φ(λ t ; θ t ) -∇φ(λ * (θ t ); θ t )∥ 2 ≤ 2ℓ φ λ ,1 φ(λ t ; θ t ) -φ(λ * (θ t ); θ t ) ≤ ℓ φ λ ,1 ∥λ t-1 -λ * (θ t )∥ 2 γT 2 . (E.35)Plugging in the gradient ∇φ(λ t ; θ t ), we haveEQUATIONλγT 2 , from Theorem 1, it holds thatV t+1 -V t ≤ -α t ∥d * t ∥ 2 + α t c g λ * g (θ t ) -λ g ⊤ [G(θ t )] + + α t c h λ * h (θ t ) -λ h ⊤ |H(θ t )| ab + ϵ 1 2 + 1 2 γα t ∥∇ λ φ(λ t ; θ t )∥ 2 + ℓ f,1 2 α 2 t ∥A ⊤ ag λ∥ 1 ∥d * t ∥ 2 . (E.37)Taking telescoping sum of the above inequality from t = 0, . . . , T -1, rearranging, and lettingEQUATION(E.38)Letting α t = Θ(1), γ = Θ(1) yields T -1 t=T 1 2 ∥d * t ∥ 2 + c g (λ g -λ * g (θ t )) ⊤ [G(θ t )] + + c h (λ h -λ * h (θ t )) ⊤ |H(θ t )| ab = O 1 . (E.39)The proof is complete.F Proof of Theorems 2 and 3: convergence of Algorithm 2F.1 Auxiliary lemmas Lemma 11 (Smoothness of φ). Suppose Assumptions 1 and 3 hold.φ(λ; θ) is ℓ φ λ ,1 -smooth w.r.t. λ, with ℓ φ λ ,1 = M ∥A ag ∥ 2 ℓ 2 f .Proof. The Hessian of φ(λ; θ) w.r.t. λ can be computed by∇ 2 λ φ(λ; θ) = A ag ∇F (θ) ⊤ ∇F (θ)A ⊤ ag . By Assumption 3, the Lipschitz continuity of F , it holds that ∥∇ 2 λ φ(λ; θ)∥ ≤ ∥A ag ∇F (θ) ⊤ ∇F (θ)A ⊤ ag ∥ ≤ ∥∇F (θ)A ⊤ ag ∥ 2 ≤ M ∥A ag ∥ 2 ℓ 2f . The result is proved.Lemma 12 (∥∇ λ f φ(λ t ; θ t )∥ bounded by ∥d t ∥). Suppose Assumptions 1 and 3 hold. For {θ t } produced by Algorithm 2, we have∥∇ λ f φ(λ t ; θ t )∥ ≤ ∥A ⊤ ∥ ∞,1 ℓ f ∥d t ∥. (F.1)Proof. The gradient of φ(λ t ; θ t ) w.r.t. λ f can be computed by∇ λ f φ(λ t ; θ t ) = A∇F (θ t ) ⊤ ∇F (θ t )A ⊤ ag λ t = -A∇F (θ t ) ⊤ d t . (F.2)By Assumption , it holds that∥∇ λ f φ(λ t ; θ t )∥ ≤ ∥A ⊤ ∥ ∞,1 ℓ f ∥d t ∥. (F.3) Lemma 13. Let λ t = [λ f,t ; λ h,t ].Consider the sequence {λ t } T t=1 generated by the update (3.1). Then for all λ ∈ Ω λ (θ t ) with λ = (λ f , λ h ), it holds that2γ t ⟨λ f,t -λ f , ∇ λ f φ(λ t ; θ t )⟩ ≤ ∥λ f,t -λ f ∥ 2 -∥λ f,t+1 -λ f ∥ 2 + γ 2 t ∥∇ λ f φ(λ t ; θ t )∥ 2 ; 2γ t ⟨λ h,t -λ h , ∇ λ h φ(λ t ; θ t )⟩ = ∥λ h,t -λ h ∥ 2 -∥λ h,t+1 -λ h ∥ 2 + γ 2 t ∥∇ λ h φ(λ t ; θ t )∥ 2 . (F.4)Proof. By the update of λ f,t , and the non-expansiveness of projection, let λ f = 1 ∈ Ω λ f (θ) for all θ ∈ R q , we have∥λ f,t+1 -λ f ∥ 2 ≤ ∥λ f,t -γ t ∇ λ f φ(λ t ; θ t ) -λ f ∥ 2 =∥λ f,t -λ f ∥ 2 -2γ t ⟨λ f,t -λ f , ∇ λ f φ(λ t ; θ t )⟩ + γ 2 t ∥∇ λ f φ(λ t ; θ t )∥ 2 . (F.5)Rearranging the above inequality gives2γ t ⟨λ f,t -λ f , ∇ λ f φ(λ t ; θ t )⟩ ≤∥λ f,t -λ f ∥ 2 -∥λ f,t+1 -λ f ∥ 2 + γ 2 t ∥∇ λ f φ(λ t ; θ t )∥ 2 (F.6)which proves the first inequality.By the update of λ h,t , for all constant λ h ∈ R M h , we have∥λ h,t+1 -λ h ∥ 2 = ∥(λ h,t -γ t ∇ λ h φ(λ t ; θ t )) -λ h ∥ 2 =∥λ h,t -λ h ∥ 2 + γ 2 t ∥∇ λ h φ(λ t ; θ t )∥ 2 -2γ t ⟨λ h,t -λ h , ∇ λ h φ(λ t ; θ t )⟩. (F.7)Rearranging the above inequality gives In this section, we provide analysis with the same merit function as Theorem 1. The proof follows similar ideas of the proofs of Theorem 3 and Theorem 5 in [6] .2γ t ⟨λ h,t , ∇ λ h φ(λ t ; θ t )⟩ -2γ t ⟨λ h , ∇ λ h φ(λ t ; θ t )⟩ =∥λ h,t -λ h ∥ 2 -∥λ h,t+1 -λ h ∥ 2 +We first define the following auxiliary functions to assist our analysis. Note that the functions are only used for analysis but not for the algorithm update. ∥∇ λ h φ(λ; θ)∥ 2 ≤ 2ℓ φ λ ,1 φ(λ; θ) -φ(λ * ρ (θ); θ) + ℓ φ λ ,1 ρc λ . (F.12)Proof of Corollary 9. By applying Lemma 10, and that ∇ λ h φ(λ * (θ); θ) = 0, we have Lemma 15 (Continuity of λ * ρ (θ)). For λ * ρ (θ) defined in (F.10), and Ω λ (θ) = Ω λ , the following holds∥∇ λ h φ(λ; θ)∥ 2 =∥∇ λ h φ(λ; θ) -∇ λ h φ(λ * (θ); θ)∥ 2 ≤ ∥∇ λ φ(λ; θ) -∇ λ φ(λ * (θ); θ)∥ 2∥λ * ρ (θ) -λ * ρ (θ ′ )∥ ≤ρ -1 ∥∇ 2 λ φ(λ * ρ (θ); θ) -∇ 2 λ φ(λ * ρ (θ ′ ); θ ′ )∥ ≤2ρ -1 ℓ f,1 ℓ f ∥A ⊤ ag ∥ 2 ∞,1 ∥θ -θ ′ ∥. (F.15)Proof of Lemma 15. The proof follows the proof of [6, Lemma 12] .Lemma 16. Suppose Assumptions 1, 2, 3 hold. Let {θ t }, {λ t } be the sequences produced by Algorithm 2 with step sizes α t = α > 0, γ t = γ > 0. Assume ∥λ * (θ t )∥, ∥λ * ρ (θ t )∥, ∥λ t ∥ ≤ c λ . Then for any ρ > 0, it holds that Taking telescoping sum of the above inequality and rearranging, we have1 T T -1 t=0 φ(λ t ; θ t ) -φ(λ * ρ (θ t ); θ t ) ≤ 2c 2 λ γT (1 + 2ρ -1 αT ℓ f,1 ℓ 2 f ∥A ⊤ ag ∥ 3 ∞,1 ) + γ 2T T -1 t=0 ∥∇ λ φ(λ t ; θ t )∥1 T T -1 t=0 φ(λ t ; θ t ) -φ(λ * ρ (θ t ); θ t ) ≤ 1 2γT T -1 t=0 ∥λ t -λ * ρ (θ t )∥ 2 -∥λ t+1 -λ * ρ (θ t )∥ 2 I1 + γ 2T T -1 t=0 ∥∇ λ φ(λ t ; θ t )∥ 2 (F.18)where I 1 can be further bounded byI1 ≤∥λ0 -λ * ρ (θ0)∥ 2 -∥λT -λ * ρ (θT -1)∥ 2 + T -2 t=0 ∥2λt+1 -λ * ρ (θt+1) -λ * ρ (θt)∥∥λ * ρ (θt+1) -λ * ρ (θt)∥ ≤4c 2 λ + 4c λ T -2 t=0 ∥λ * ρ (θt+1) -λ * ρ (θt)∥ ≤ 4c 2 λ + 8c λ T -2 t=0 ρ -1 αtℓ f,1 ℓ f ∥A ⊤ ag ∥ 2 ∞,1 ∥dt∥where the last inequality follows from Lemma 15 and the update of θ t .Finally, taking α t = α, plugging the above bound for I 1 back into (F.18), and bounding ∥d t ∥ by Assumption 3 and that ∥λ t ∥ ≤ c λ prove the result.Proof of Theorem 2. We consider the following Lyapunov function with a constant vector λ =[λ f ; λ h ] ∈ Ω λ (θ), where λ f = 1, λ h ∈ R M h . V t := λ ⊤ f AF (θ t ) V f,t + λ ⊤ h H(θ t ) V h,1,t + c V h ∥H(θ t )∥ 1 V h,3,t V h,t . (F.19)Recall that λ t = [λ f,t ; λ h,t ], and the algorithm takes the update θ t+1 = θ t + α t d t with d t = ∇F (θ t )A ⊤ ag λ t . From Assumption 2, the smoothness of the objectives, and Lemma 6, the functionλ ⊤ f AF (θ) is smooth, thus V f,t+1 -V f,t ≤⟨∇F (θ t )A ⊤ λ f , θ t+1 -θ t ⟩ + ℓ f,1 2 ∥A ⊤ λ f ∥ 1 ∥θ t+1 -θ t ∥ 2 =α t ⟨∇F (θ t )A ⊤ λ f , d t ⟩ + ℓ f,1 2 α 2 t ∥A ⊤ λ f ∥ 1 ∥d t ∥ 2 . (F.20)By Lemma 13, taking γ t > 0 and rearranging, we have⟨∇F (θ t )A ⊤ λ f , d t ⟩ ≤ 1 2γ t ∥λ f,t -λ f ∥ 2 -∥λ f,t+1 -λ f ∥ 2 + 1 2 γ t ∥∇ λ f φ(λ t ; θ t )∥ 2 -⟨λ f,t , ∇ λ f φ(λ t ; θ t )⟩. (F.21)Combining (F.20) and (F.21), we haveV f,t+1 -V f,t ≤ α t 2γ t ∥λ f,t -λ f ∥ 2 -∥λ f,t+1 -λ f ∥ 2 + ℓ f,1 2 α 2 t ∥A ⊤ λ f ∥ 1 ∥d t ∥ 2 + 1 2 α t γ t ∥∇ λ f φ(λ t ; θ t )∥ 2 -α t ⟨λ f,t , ∇ λ f φ(λ t ; θ t )⟩. (F.22)By the smoothness of λ ⊤ h H(θ), and∇ λ h φ(λ t ; θ t ) = -∇H(θ t ) ⊤ d t -c h H(θ t ), it holds that V h,1,t+1 -V h,1,t ≤α t λ ⊤ h ∇H(θ t ) ⊤ d t + ℓ f,1 2 α 2 t ∥B ⊤ h λ h ∥ 1 ∥d t ∥ 2 = -α t c h λ ⊤ h H(θ t ) + ℓ f,1 2 α 2 t ∥B ⊤ h λ h ∥ 1 ∥d t ∥ 2 -α t ⟨λ h , ∇ λ h φ(λ t ; θ t )⟩. (F.23)Bounding the last term in the above inequality by Lemma 13, and taking γ t > 0, we haveV h,1,t+1 -V h,1,t ≤ -α t c h λ ⊤ h H(θ t ) + ℓ f,1 2 α 2 t ∥B ⊤ h λ h ∥ 1 ∥d t ∥ 2 + 1 2 α t γ t ∥∇ λ h φ(λ t ; θ t )∥ 2 -α t ⟨λ h,t , ∇ λ h φ(λ t ; θ t )⟩ + α t 2γ t ∥λ h,t -λ h ∥ 2 -∥λ h,t+1 -λ h ∥ 2 . (F.24)Adding up (F.22) and (F.24) yieldsV f,t+1 -V f,t + V h,1,t+1 -V h,1,t ≤ -α t ⟨λ t , ∇ λ φ(λ t ; θ t )⟩ + 1 2 γ t α t ∥∇ λ φ(λ t ; θ t )∥ 2 -α t c h λ ⊤ h H(θ t ) + α t 2γ t ∥λ t -λ∥ 2 -∥λ t+1 -λ∥ 2 + ℓ f,1 2 α 2 t ∥A ⊤ ag λ∥ 1 ∥d t ∥ 2 ≤ -α t ∥d t ∥ 2 + α t c h (λ h,t -λ h ) ⊤ H(θ t ) + α t 2γ t ∥λ t -λ∥ 2 -∥λ t+1 -λ∥ 2 + 1 2 γ t α t ∥∇ λ φ(λ t ; θ t )∥ 2 + ℓ f,1 2 α 2 t ∥A ⊤ ag λ∥ 1 ∥d t ∥ 2 (F.25)where the last inequality uses the fact that ⟨λ t , ∇ λ φ(λ t ; θ t )⟩ = ∥d t ∥ 2 -c h λ ⊤ h,t H(θ t ). Using the fact that ∇ λ h φ(λ t ; θ t ) = -∇H(θ t ) ⊤ d t -c h H(θ t ), and with similar arguments as (E.20) in Lemma 8, we can further derive that|H(θ t+1 )| ab ≤|H(θ t ) -α t c h H(θ t ) -α t ∇ λ h φ(λ t ; θ t )| ab + ℓ f,1 2 α 2 t ∥B ⊤ h ∥ ∞,1 ∥d t ∥ 2 1 ≤(1 -α t c h )|H(θ t )| ab + ℓ f,1 2 α 2 t ∥B ⊤ h ∥ ∞,1 ∥d t ∥ 2 1 + α t |∇ λ h φ(λ t ; θ t )| ab . (F.26) Therefore, V h,2,t+1 -V h,3,t ≤ -α t c h c V h ∥H(θ t )∥ 1 + ℓ f,1 2 c V h M h α 2 t ∥B ⊤ h ∥ ∞,1 ∥d t ∥ 2 + α t c V h ∥∇ λ h φ(λ t ; θ t )∥ 1 . (F.27)Combining (F.25) and (F.27), and by choosing step sizes α t , γ t , parameter c V h such thatℓ f,1 2 c V h M h α 2 t ∥B ⊤ h ∥ ∞,1 + ℓ f,1 2 α 2 t ∥A ⊤ ag λ∥ 1 ≤ 1 2 , (F.28)we haveVt+1 -Vt ≤ - 1 2 αt∥dt∥ 2 -αtc h (cV h -∥λ h -λ h,t ∥1)∥H(θt)∥1 + αt 2γt ∥λt -λ∥ 2 -∥λt+1 -λ∥ 2 + 1 2 γtαtℓ 2 φ + αtcV h ∥∇ λ h φ(λt; θt)∥1. (F.29)Taking telescoping sum of the above inequality over t = 0, . . . , T -1, and applying that∥∇ λ h φ(λ t ; θ t )∥ 1 ≤ √ M h ∥∇ λ h φ(λ t ; θ t )∥, we have T -1 t=0 V t+1 -V t ≤ T -1 t=0 - 1 2 α t ∥d t ∥ 2 -α t c h (c V h -∥λ h -λ h,t ∥ 1 )∥H(θ t )∥ 1 + 1 2 γ t α t ℓ 2 φ + α t 2γ t ∥λ t -λ∥ 2 -∥λ t+1 -λ∥ 2 + α t c V h M h ∥∇ λ h φ(λ t ; θ t )∥ (F.30)where T -1 t=0 ∥∇ λ h φ(λ t ; θ t )∥ can be further bounded by applying Lemma 16 and Corollary 9 along with Jensen's inequality as follows1 T T -1 t=0 ∥∇ λ h φ(λ t ; θ t )∥ 2 ≤ 1 T T -1 t=0 ∥∇ λ h φ(λ t ; θ t )∥ 2 Corollary 9 ≤ 1 T T -1 t=0 2ℓ φ λ ,1 φ(λ t ; θ t ) -φ(λ * ρ (θ t ); θ t ) + ℓ φ λ ,1 ρc λ Lemma 16 ≤ 4ℓ φ λ ,1 c 2 λ 1 γT (1 + 2ρ -1 αT ℓ f,1 ℓ 2 f ∥A ⊤ ag ∥ 3 ∞,1 ) + γ 2T T -1 t=0 ∥∇ λ φ(λ t ; θ t )∥ 2 + ρℓ φ λ ,1 c λ (F.31)where∥∇ λ φ(λ t ; θ t )∥ 2 = ∥∇ λ h φ(λ t ; θ t )∥ 2 + ∥∇ λ f φ(λ t ; θ t )∥ 2 ≲ ∥∇ λ h φ(λ t ; θ t )∥ 2 + ∥d t ∥ 2 . Plug-ging the above inequality back into (F.30), choosing ρ = Θ ( α γ ), and rearranging yield 6 ) proves the result.EQUATIONF. ∥H(θ t+1 )∥ 2 -∥H(θ t )∥ 2 ≤ α t 2H(θ t ) ⊤ ∇H(θ t ) ⊤ d t + 1 2 α 2 t ℓ H 2 ,1 ∥d t ∥ 2 with ℓ H 2 ,1 = 2M ℓ 2 f + 2(α -1 t + ℓ H )c d,h √ M ℓ f,1 .Proof. By the mean-value theorem, for all t ∈ [T ], there exists θ such that∥H(θ t+1 )∥ 2 -∥H(θ t )∥ 2 ≤ α t 2H(θ t ) ⊤ ∇H(θ t ) ⊤ d t + 1 2 α 2 t ∥∇ 2 H( θ) ⊤ H( θ)∥∥d t ∥ 2 . (F.33)The Hessian of ∥H( θ)∥ 2 can be upper bounded by∥∇ 2 H( θ) ⊤ H( θ)∥ ≤ 2∥∇H( θ)∇H( θ) ⊤ ∥ + 2∥∇ 2 H( θ)∥∥H( θ)∥ ≤ 2M ℓ 2 f + 2∥H( θ)∥ √ M ℓ f,1 . (F.34)Since H( θ) is ℓ H -Lipschitz continuous with ℓ H = ∥B h ∥ℓ F , and θ lies on the line segment of θ t and θ t+1 with ∥θ t+1 -θ t ∥ = α t ∥d t ∥, therefore,∥H( θ)∥ ≤ ∥H(θ t )∥ + α t ℓ H ∥d t ∥ ≤ ∥H(θ t )∥ + ℓ H c d . (F.35)Plugging the above inequality into (F.33) yields∥H(θ t+1 )∥ 2 -∥H(θ t )∥ 2 ≤ α t 2H(θ t ) ⊤ ∇H(θ t ) ⊤ d t + 1 2 α 2 t ∥∇ 2 H( θ) ⊤ H( θ)∥∥d t ∥ 2 ≤α t 2H(θ t ) ⊤ ∇H(θ t ) ⊤ d t + 1 2 α 2 t 2M ℓ 2 f + 2(α -1 t c α,h + ℓ H c d ) √ M ℓ f,1 ∥d t ∥ 2 .The proof is complete. Proof. By choosing γ t = Θ( αt T ), and ∥λ 0 ∥ to be bounded, then for all τ ∈ [T ], we have∥λ τ ∥ ≤∥λ 0 ∥ + τ -1 t=0 ∥∇ λ φ(λ t ; θ t )∥ = ∥λ 0 ∥ + τ -1 t=0 γ t ∥∇ λ φ(λ t ; θ t )∥ ≲∥λ 0 ∥ + 1 T τ -1 t=0 α t (∥∇F (θ t )A ⊤ ag ∥∥d t ∥ + c h ∥H(θ t )∥) ≤∥λ 0 ∥ + ℓ F ∥A ag ∥c d + c h c α,h = Θ(1). (F.36)This proves that ∥λ t ∥ is bounded for all t ∈ [T ].Since d t = ∇F (θ t )A a gλ t , consequently we have∥d t ∥ = ∥∇F (θ t )A a gλ t ∥ = Θ(1). (F.37) Furthermore, if ∥H(θ t )∥ ≤ c ht for all t ∈ [T ], invoking that ∇ λ h φ(λ t ; θ t ) = -∇H(θ t ) ⊤ d t - c h H(θ t ), we have ∥∇ λ h φ(λ t ; θ t )∥ =∥∇H(θ t ) ⊤ d t + c h H(θ t )∥ ≤ ∥∇H(θ t )∥∥d t ∥ + c h ∥H(θ t )∥ ≤ℓ H ∥d t ∥ + c h ∥H(θ t )∥ = Θ(1). (F.38)The proof is complete. S T = 2 T T -1 t=0 α t c h λ ⊤ h,t H(θ t ) -∇ λ h φ(λ t ; θ t ) ⊤ H(θ t ) + α 0 T γ 0 (∥λ h,T ∥ 2 -∥λ h,0 ∥ 2 ). (F.39)Then we have that ∥S T ∥ = Θ(1) is bounded.Proof. By the definition of S T , Cauchy-Schwartz inequality, we have∥S T ∥ ≤ 2 T T -1 t=0 α t c h ∥λ h,t ∥∥H(θ t )∥ + α t ∥∇ λ h φ(λ t ; θ t )∥∥H(θ t )∥ + α 0 T γ 0 ∥λ h,T ∥ 2 . (F.40)By Lemma 18 and that ∥H(θ t )∥ is bounded, ∥λ t ∥ and ∥∇ λ h φ(λ t ; θ t )∥ are both bounded for all t ∈ [T ], therefore, ∥S T ∥ = Θ(1) is also bounded.Proof of Theorem 3. We consider the following Lyapunov function with a constant vector λ =[λ f ; λ h ] ∈ Ω λ (θ), where λ f = 1, λ h ∈ R M h . V t := λ ⊤ f AF (θ t ) V f,t + λ ⊤ h H(θ t ) V h,1,t + 1 2 ∥H(θ t )∥ 2 V h,3,t V h,t . (F.41)Following the same arguments from (F.20)-(F.25), we haveV f,t+1 -V f,t + V h,1,t+1 -V h,1,t ≤ -αt∥dt∥ 2 + αtc h (λ h,t -λ h ) ⊤ H(θt) + αt 2γt ∥λt -λ∥ 2 -∥λt+1 -λ∥ 2 + 1 2 γtαt∥∇ λ φ(λt; θt)∥ 2 + ℓ f,1 2 α 2 t ∥A ⊤ ag λ∥1∥dt∥ 2 . (F.42)Next we proceed to bound V h,3,t+1 -V h,3,t . By Lemma 17, it holds thatV h,3,t+1 -V h,3,t ≤ α t H(θ t ) ⊤ ∇H(θ t ) ⊤ d t + 1 4 α 2 t ℓ H 2 ,1 ∥d t ∥ 2 (F.43) where ℓ H 2 ,1 = 2M ℓ 2 f + 2(α -1 t c α,h + ℓ H c d ) √ M ℓ f,1 . Because ∇ λ h φ(λ t ; θ t ) = -∇H(θ t ) ⊤ d t - c h H(θ t ), the term H(θ t ) ⊤ ∇H(θ t ) ⊤ d t can be further written as H(θ t ) ⊤ ∇H(θ t ) ⊤ d t = -H(θ t ) ⊤ ∇ λ h φ(λ t ; θ t ) + c h H(θ t ) = -c h ∥H(θ t )∥ 2 -H(θ t ) ⊤ ∇ λ h φ(λ t ; θ t ). (F.44) Plugging (F.44) into (F.43) yields 1 2 ∥H(θ t+1 )∥ 2 - 1 2 ∥H(θ t )∥ 2 ≤ -α t c h ∥H(θ t )∥ 2 -α t H(θ t ) ⊤ ∇ λ h φ(λ t ; θ t ) + 1 4 α 2 t ℓ H 2 ,1 ∥d t ∥ 2 . (F.45)Letting ℓ Fag,1 = ℓ f,1 ∥A ⊤ ag λ∥ 1 , and adding up (F.42) and (F.45), we haveV t+1 -V t ≤ -α t ∥d t ∥ 2 -α t c h ∥H(θ t )∥ 2 + α t c h (λ h,t -λ h ) -∇ λ h φ(λ t ; θ t ) ⊤ H(θ t ) + α t 2γ t ∥λ t -λ∥ 2 -∥λ t+1 -λ∥ 2 + 1 2 γ t α t ∥∇ λ φ(λ t ; θ t )∥ 2 + 1 4 α 2 t (2ℓ Fag,1 + ℓ H 2 ,1 )∥d t ∥ 2 (F.46)where ∥∇ λ φ(λ t ; θ t )∥ 2 can be further bounded via triangle inequality and Cauchy-Schwarz inequality, given by∥∇ λ φ(λ t ; θ t )∥ 2 =∥A ag ∇F (θ t ) ⊤ d t -c h H(θ t )∥ 2 ≤2∥A ag ∇F (θ t ) ⊤ d t ∥ 2 + 2∥c h H(θ t )∥ 2 ≤2∥A ag ∥ 2 M ℓ 2 f ∥d t ∥ 2 + 2c 2 h ∥H(θ t )∥ 2 . (F.47) Plugging (F.47) back into (F.46) yields V t+1 -V t ≤ -α t ∥d t ∥ 2 -α t c h ∥H(θ t )∥ 2 + α t c h (λ h,t -λ h ) -∇ λ h φ(λ t ; θ t ) ⊤ H(θ t ) + α t 2γ t ∥λ t -λ∥ 2 -∥λ t+1 -λ∥ 2 + 1 4 α 2 t (2ℓ Fag,1 + ℓ H 2 ,1 )∥d t ∥ 2 J1 + γ t α t ∥A ag ∥ 2 M ℓ 2 f ∥d t ∥ 2 J2 + γ t α t c 2 h ∥H(θ t )∥ 2 J3 (F.48)where by choosing the step sizes α t ≤1 2ℓ Fag ,1 +ℓ H 2 ,1 , γ t ≤ min 1 4∥Aag∥ 2 M ℓ 2 f , 1 2c h , it holds that J 1 ≤ 1 4 α t ∥d t ∥ 2 , J 2 ≤ 1 4 α t ∥d t ∥ 2 , J 3 ≤ 1 2 α t c h ∥H(θ t )∥ 2 . (F.49)Plugging (F.49) into (F.48), choosing αt γt = α0 γ0 for all t ∈ [T ], and rearranging, we haveV t+1 -V t ≤ - 1 2 α t ∥d t ∥ 2 - 1 2 α t c h ∥H(θ t )∥ 2 + α t c h (λ h,t -λ h ) -∇ λ h φ(λ t ; θ t ) ⊤ H(θ t ) + α 0 2γ 0 ∥λ t -λ∥ 2 -∥λ t+1 -λ∥ 2 . (F.50)Taking telescoping sum of the above inequality over t = 0, . . . , T -1 yieldsT -1 t=0 α t ∥d t ∥ 2 + c h ∥H(θ t )∥ 2 - T -1 t=0 2α t c h (λ h,t -λ h ) -∇ λ h φ(λ t ; θ t ) ⊤ H(θ t ) ≤2(V 0 -V T ) + α 0 γ 0 (∥λ 0 -λ∥ 2 -∥λ T -λ∥ 2 ) ≤2V f,0 + 2λ ⊤ h H(θ 0 ) -H(θ T ) + ∥H(θ 0 )∥ 2 + α 0 γ 0 (∥λ 0 -λ∥ 2 -∥λ T -λ∥ 2 ) (F.51)where the last inequality uses the definition of V t and that V f,t ≥ 0.Choosing λ f,0 = λ f , and rearranging the above inequality, we haveT -1 t=0 α t ∥d t ∥ 2 + c h ∥H(θ t )∥ 2 ≤ 2V f,0 + ∥H(θ 0 )∥ 2 + α 0 γ 0 (∥λ h,0 -λ h ∥ 2 -∥λ h,T -λ h ∥ 2 ) + T -1 t=0 2α t c h λ h,t -∇ λ h φ(λ t ; θ t ) ⊤ H(θ t ) + 2λ ⊤ h H(θ 0 ) -H(θ T ) -c h T -1 t=0 α t H(θ t ) .(F.52)Note that (F.52) holds for all λ h ∈ R M h . And λ h here serves as an auxiliary multiplier to prove the convergence in Theorem 3. We then discuss how to choose a bounded λ h such that the desired convergence result holds. A simple choice is that the additional terms related to λ h and λ h,t on the right hand side of (F.52) amount to a value greater than zero, i.e., F (0) as the reference points and choose B h such that B h (F (θ 0 ) -F (0)) = 0. Results in Figure 7 show that for different scales, the trajectory and the converging solution are the same. Emotion recognition. The task is to predict 6 types of emotions from 593 songs based on the Tellegen Watson-Clark model of affect. The 6 emotions include: amazed-surprised (E1), happy-pleased (E2), relaxing-calm (E3), quiet-still (E4), sad-lonely (E5), and angry-fearful (E6). Following [30] , we use the fully connected neural network with 4 layers as the model architecture. The Sigmoid cross entropy loss is used as the objective for each task. And 10 preference vectors are generated uniformly. The hyperparameters used in this experiment are summarized in Table 11 .2λ ⊤ h -c h T -1 t=0 α t H(θ t ) - α 0 γ 0 (∥λ h,0 -λ h ∥ 2 -∥λ h,T -λ h ∥ 2 ) =2λ ⊤ h -c h T -1 t=0 α t H(θ t ) - α 0 γ 0 (∥λ h,0 ∥ 2 -∥λ h,T ∥ 2 -2⟨λ h , λ h,0 -λ h,T ⟩) ≥ -2 T -⊤ f AF (θ) is ℓ AF,1 -smooth with ℓ AF,1 = ℓ f,1 ∥A ⊤ λ f ∥ 1 , thus E t [V f,t+1 -V f,t ] ≤E t [⟨∇F (θ t )A ⊤ λ f , θ t+1 -θ t ⟩ + ℓ AF,The results on the relative loss profile (RLP) are reported in Figure 9 . Results show that all methods, including LS, work similarly well. EPO achieves the highest hypervolumes, and our proposed approach obtains the second-best hypervolumes. One reason could be that the Pareto front in this problem is convex.Note that, A∇F (θ) ⊤ d ≤ c 1 ⊤ AF (θ) AF (θ) in (2.1) can be replaced by A∇F (θ) ⊤ d ≤ c • 1, which leads to a simplified subprogram with Ω λ f (θ) = Ω λ f = ∆ M ,and can be covered by our analysis. 


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

Reviews: review: paper_summary: paper_summary: This paper tackled constrained multi-objective optimization problems with Pareto optimality generalized to partial order cone. The authors proposed an algorithm framework to iteratively solving a subproblem to get a update direction and aim at search for Pareto optimal solution in a certain Pareto front region associated pre-defined preferences.

The paper presented rich convergence analysis for deterministic algorithm with exact subproblem solutions, deterministic algorithm with inexact subproblem solutions, as well as stochastic version where gradient is estimated through double samplings. 

The stochastic algorithm variant is tested on image classification and speech recognition tasks and compared against state-of-art benchmark algorithms.
strength_weakness: strength_weakness: * The relative preference seems being handled by both partial order cone associated with the objective function and inequality constraints. It is kind of confusing and redundant to have both preference cone and constraints defined in the objective space in the optimization problem. See the questions part for more details. The experiment on multi-task learning seems only tackling constraints. 
* In real decision making application, computing the ordering cone by solving another LP makes the decision making process more complex and less doable.
* The authors selected number of algorithm iterations to compare computational cost, which leads to apple to orange comparison. Better to adopt number of function evaluations, number of gradient evaluations, etc. as the metrics.
questions: questions: * As both the relative preference and constraints are defined in objective space and both equality and inequality constraints are defined as linear functions of objectives, would it possible to convert at least inequality constraints to preference defined by a cone? 
* Can we reduce Pareto dominance defined in a polyhedral cone to Pareto dominance defined in Real space $R^m_+$ by taking $AF(\theta)$ as objective vector? 
* From Theorem 1 to Theorem 2, the second part on the left of Equation (2.5) $G(\theta_t)$ no longer present in equation (3.2). How is the inequality violation converging to zero in the single loop approximate algorithm variant? 
* Equation (5.2): what is the rationale to have the representation learning loss for Chinese and English differing by an exact number. Would it be more reasonable to have the loss gap smaller than a threshold?
* It is not clear in Table 2 what is Emotion loss without referring to Appendix.
* Figure 2(a): “LS only finds extreme points on the PF with one objective minimized." How are the secularization weights selected? Is the weight selection related to extreme rays?
* Figure 4 clarification
    * 4(c) LS accuracy is missing. 4(a) also missing red square.
    * As mentioned in the paper, orange preference vector is not attainable. In (d)-(f), the proposed algorithm tends to search for Pareto front region closer to the ideal Pareto minimizer. Is this constraint violation controllable?
    * Figure (e) green cross given by XWC-MGDA seems dominating most of other solutions. 

* Minor issues:
    * Notation consistency: Theorem 2 equation (3.2) $d_t$ → $d_t(\theta_t)$. 
    * Line 279: figure 3d-3f should be 3a-3c. 
    * Figure 3: caption (c) and (f) should be consistent.
limitations: limitations: N/A
paper_summary: paper_summary: This paper introduces FERERO, a novel framework for preference-guided multi-objective learning by depicting the task as a constrained single-objective optimization problem. It incorporates relative preferences, defined by a polyhedral cone, and absolute preferences, defined by linear constraints, into the above optimization problem. Both deterministic and stochastic algorithms with finite-time convergence guarantees are proposed. FERERO is validated through experiments on multiple benchmarks, demonstrating its effectiveness in finding competitive preference-guided Pareto optimal solutions.
strength_weakness: strength_weakness: I do not notice any obvious weakness. Some comments are given below:

1. What is the evidence of ``flexible``? Is flexibility important?
2. What is the meaning of ``cross`` in Table 1? Is it not mentioned in the literature or is it inherently impossible to do this?
3. What are the advantages of a method based on general partial order? Is it related to escaping weak Pareto optimality?
4. As far as I am concerned, Linear Scalarization and (Smooth) Tchebycheff can escape weak Pareto optimality.
5. The per-iteration may need more descriptions.
6. What if some absolute preferences are not available? e.g., $B_h$ or $B_g$ are not provided by the decision maker. Besides, the settings of preferences in the experiments are hard to find.
7. Are there some typos in the subtitles of Figure 2(e) and Figure 3(c)?
questions: questions: Refer to the above comments.
limitations: limitations: The discussion is comprehensive in my view.
paper_summary: paper_summary: This paper introduces a new algorithm called FERERO, which can handle both relative and absolute preferences in preference-guided multi-objective learning. The problem is formulated as a constrained vector optimization problem. The goal is to find the (approximated) $C_A$-optimal set that satisfies the absolute preference constraints. The cone $C_A$ can be interpreted as a relative preference that defines the objectives’ improvement directions. 

In each iteration, the FERERO finds a direction $d^{\star}(\theta)=-\nabla F(\theta)A_{ag}^T\lambda^{\star}$, derived by solving a subprogram. The $\lambda^{\star}$ in $d^{\star}(\theta)$ is derived from the Lagrangian of subprogram. Moreover, the approximated update rules and a stochastic version of FERERO are proposed for large-scale learning problems. 

The paper includes theoretical analysis of FERERO and its stochastic, approximated variants. The experimental comparisons with existing multi-gradient descent methods are also conducted to demonstrate the effectiveness of this approach.
strength_weakness: strength_weakness: 1.	The step sizes in some of the convergence analyses, e.g., Theorem 2 and Theorem 3, depend on the $T$, which can be unknown in real-world problems.

2.	The computational cost per-iteration can be higher than the traditional scalarization methods.

3.	The studied problem is not well motivated. Compared to the traditional multi-objective optimization, the authors consider a more complicated case, where each objective function is a linear combination of the original multiple objectives. More real-world applications should be given to validate the significance of the problem.

4.	C_A is not used in the experiments. That is, traditional multi-objective optimization is considered. This seems to be insufficient.
questions: questions: 1.	The preference constraints are expressed as linear functions of $F(\theta)$. Is this kind of linear structure assumption for preference constraints common in real world problems?

2.	Could you explain your choice of step sizes in the experiment and how can it be related to your theoretical results.
limitations: limitations: Yes
paper_summary: paper_summary: This paper considers preference-guided multi-objective learning from the lens of constrained vector optimization. Cone captures relative preferences. Constraints capture absolute preferences. Under boundedness and smoothness assumptions on the objective function, the paper provides gradient-based methods for the identification of Pareto optimal points. The paper provides convergence guarantees for deterministic and stochastic versions of various gradient-based algorithms and illustrates their applicability in a wide range of vector optimization problems.
strength_weakness: strength_weakness: 1) This paper formalizes preference-guided multi-objective learning as a constrained vector optimization problem; however, the vector optimization aspect of the paper is not mentioned in the introduction section. It is not clear what “maximize” means, and it is not clear with respect to what cone the authors maximize. The introduction section gives the impression that the authors consider a multi-objective optimization problem, not a vector optimization problem. 

2) Since there can be many solutions in the Pareto set, the set of solutions $\theta$ of PMOL may be very large. An important thing that is not mentioned explicitly in this work is how much of the true Pareto front ${\cal F}$ or the true Pareto set $\\{\theta : F(\theta) \in {\cal F} \\}$ the proposed algorithms capture when they converge. The theoretical results point to the convergence but do not point to what set of solutions the algorithms converge towards. Indeed, many algorithms whose task is to identify a Pareto set of solutions (either for multi-objective or vector optimization) come with guarantees on the returned Pareto set in the form of $(\epsilon,\delta)$-PACness results. Some success conditions that quantify the quality of the returned Pareto set or Pareto front are given in the following works. 

Auer, Peter, et al. "Pareto front identification from stochastic bandit feedback." International Conference on Artificial Intelligence and Statistics. PMLR, 2016.

Ararat, Cagin, and Cem Tekin. "Vector optimization with stochastic bandit feedback." International Conference on Artificial Intelligence and Statistics. PMLR, 2023.

The contribution of this work will be much clearer if the authors can demonstrate guarantees for the solutions returned by their algorithms, and compare them with the existing $(\epsilon,\delta)$-PAC guarantees in the related works. 

3) Problem setup and preliminaries: “We first introduce new optimality definitions for PMOL that go beyond standard definitions of Pareto optimality”. These are some standard textbook results, not new. See and cite some of the following works. 

Boyd, Stephen P., and Lieven Vandenberghe. Convex optimization. Cambridge University Press, 2004.

Jahn, Johannes, ed. Vector optimization. Berlin: Springer, 2009.

Löhne, Andreas. Vector optimization with infimum and supremum. Springer Science & Business Media, 2011.
questions: questions: 1) Section 3.2 is confusing. As far as I understand, the goal of the paper is to optimize the objective function using gradient-based methods for a given ordering cone. First, a method that generates polyhedral cone matrix A from extreme rays of the cone is presented. This is okay, as it is just another way to express the cone. However, the second point, i.e., choosing $C_A$ for controlled ascent, is ambiguous. If the cone encodes the preferences of the decision maker, why do the authors need to change it by adding a new extreme ray? 

2) Where are the green dots in Fig. 2 (a)-(e)?

3) What is the difference between the algorithms in Fig. 2 (e) and (f)?

4) What is the difference between the algorithms in Fig. 3 (c) and (f)?
limitations: limitations: Limitations are adequately discussed.

Comments: title: Detailed comparison between our work and [c,g]
comment: Dear Reviewer PTWJ,

Thank you for your helpful comments and suggestions! We are glad that the difference between our work and [c,g] is clarified.

We will add this comparison and limitation in the paper, and make other promised revisions and clarifications to further improve our paper.
Dear Reviewer rRCm,

Thank you for your helpful comments and acknowledgement! 

We will make the promised revisions and clarifications to further improve our paper.
Dear Reviewer aduv,

Thank you very much for your helpful suggestions! We are glad that we have addressed your concerns.

We will make the promised revisions and clarifications to further improve our paper.
Dear Reviewer dD8J,

Thanks for spotting this typo in Table R1. You are correct, we will make the changes.

Thank you again for your detailed comments and helpful suggestions! We will make the promised revisions to further improve our paper.
Thanks for the reply. The differences are clear now. Please include this comparison in the revised version and also mention the limitations of the current approach.
Thanks for adding the computational time comparison. For Synthetic, Figures 3(d-f), Per-iteration run time of PMTL should be 7.65E-4s and  Per-iteration run time of FERERO should be 7.30E-4s. Otherwise, it looks good to me. 

A minor comment: regarding the multilingual constraint in Eq. (5.2), the author claimed that it is a heuristic choice based on experience. This will require domain knowledge for decision-makers to specify the exact gap number. As the proposed framework is capable of handling inequality constraints, a more practical choice is to use inequality constraints. 

The authors' response has addressed my concerns. I will keep my rating. Thanks!
Thanks for the response. Most of my concerns have been addressed. I raise my score by 1.
Thank you very much for your prompt reply and the follow-up questions. After carefully reading the related works [c,g], we summarize the differences between our work and [c,g]. Then we answer the question about our theoretical guarantees.

### Problem difference

**1. Continuous vs. discrete design space.**
The design space, i.e., the domain of the optimization variables is different. [c,g] consider a discrete finite set $[K]$, see [c, Section 2, paragraph 2], while we consider a continuous space $\theta \in \mathbb{R}^q$ that might have infinitely many Pareto optimal solutions. 

**2. Gradient-based vs. blackbox optimization.**
[c,g] focus on the best arm identification problem using blackbox optimization with unknown objectives. In contrast, we are using gradient-based optimization, where the objectives are known.

**3. Preference specification.**
The prior works [c,g] focus on ```relative preference only```, defined by a partial order cone, while our work considers ```both relative and absolute preferences```. The absolute preference is modeled by constraints $G(\theta), H(\theta)$ in our work. 

### Method difference

**A posteriori vs. a priori method [32].** Both methods need to specify the relative preference in the beginning, i.e., the partial order cone $C$ for the optimization problem to be well-defined.

***A-posteriori method [c,g]***: first returns a set of $C$-optimal solutions, then the user selects from the returned solutions based on their absolute preferences. 

***A-priori method (ours)***: the user first specifies the absolute preferences before running the method, e.g., based on weights or constraints, then the method returns one solution that satisfies the absolute preferences and is $C$-optimal.

Our method can find one Pareto optimal solution that satisfies the constraint, see Figures 2-5, the solutions align with the preference vectors in dashed lines. To the best of our knowledge, this cannot be achieved by [c,g].

### Guarantees to find all Pareto optimal solutions.

>Can this algorithm be used to find all Pareto optimal solutions or a desired subset of them? Do you have any guarantees on coverage of all Pareto optimal solutions or the diversity of returned solutions, etc?


```No, our a-priori method returns one solution given the absolute preference, not all Pareto optimal solutions.``` 

As there may be infinitely many Pareto optimal solutions, our method guarantees finding one solution that satisfies the absolute constraint and is Pareto optimal. We do not provide guarantees on finding all the Pareto optimal solutions. By running our algorithm multiple times, each time with a different absolute preference, we can obtain multiple different solutions, one solution at a time. We will clarify this in the paper.
Thanks for your kind response. I am pleased to see that you have provided many examples to illustrate their considered preferences. 

Your method is general/flexible for various tasks, as it accommodates multiple types of preferences and still works when some preferences are unavailable. My concerns regarding weak Pareto optimality have been addressed, and the relationship between general partial order and weak Pareto optimality has been clarified. My other concerns have been addressed as well.
Thanks for the response. The a-posteriori and a-priori comparison made in the response is unclear to me. Can you further clarify the difference of the approach from the one in [c,g]?  In these works, first, the user specifies preferences (a general polyhedral $C$ in [c] and $C=\mathbb{R}^d_{+}$ in [g]. The objective function is unknown. Then, sequential evaluation of designs is performed, taking into account $C$. Only the objective values at queried designs are observed (with noise). When the algorithms stop, they output an estimated Pareto set $P$ of designs that is ($\epsilon,\delta$)-PAC correct. It seems to me that the main difference from the prior work is the knowledge and use of gradient information. 

Can this algorithm be used to find all Pareto optimal solutions or a desired subset of them? Do you have any guarantees on coverage of all Pareto optimal solutions or the diversity of returned solutions, etc?