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

W1. In the introduction, the preference cones are not specified for the two examples, which causes confusion that the problem is not vector optimization.

Thanks for the suggestion. In the introduction, the cone is not specified, it can be any proper cone $C$ pre-defined by the user. Here, since we only intend to give application examples to motivate the problem, we do not intend to introduce the mathematical cone concept at this point.

However, to avoid confusion, we will add the cone $C$ in the revision by replacing Eq. (1.1), and (1.2) with the following equations.

$

&\mathrm{maximize}_ C~~ (f_ {\text{acc}}(\theta), f_ {\text{fair}}(\theta))^ {\top} ~~ \text{ s.t. } f_ {\text {fair }}(\theta) \geq \epsilon; \\ &\mathrm{maximize}_ C ~~ F(\theta):=(f_ 1(\theta), \ldots, f_ M(\theta))^ {\top} ~~ \text { s.t. } B F(\theta)=B v, B v=0 .

$

W2. Comparison with PAC guarantees

Thanks for raising this interesting point! The $(\epsilon, \delta)$-PACness results mentioned by the reviewer in [c,g] guarantee that with probability $1 - \delta$, the algorithm generates Pareto optimal (with some suboptimal) points within a precision $\epsilon$, and with a sample complexity depending on $\epsilon$ and $\delta$.

However, our results are not directly comparable to [c,g] since a key difference between our work and [c,g] is that [c,g] study the a-posteriori methods to generate a set of Pareto optimal solutions, after which the users specify their preferences and choose from the solutions. However, we study the a-priori method where the users first specify their preferences, then algorithms are used to find optimal solutions which satisfy the preferences.

Because of the difference between the studied problems, the PACness results in [c,g] only guarantee convergence to optimality for all the solutions generated by the algorithm, while our results guarantee convergence to both stationarity and preferences. When the objectives are convex / strongly convex, stationarity implies weakly Pareto optimality / Pareto optimality.

We will cite the related works including [c,g], and add the comparison in the revision.

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

[g] Peter, et al. "Pareto front identification from stochastic bandit feedback", AISTATS 2016.

W3. Preliminaries are not new but standard.

Thanks for the suggestion. We are aware of the standard results, and we have cited the preliminaries (Jahn, 2009) as [18] in Appendix C.1. Here we mean we consider the general cone to be a relative preference that is different from existing works [23,30,33] on preference-guided MOL. We will turn down the tone, remove the word "new", and cite more references here.

Q1. Clarification of Section 3.2.

The second point is to guide the decision maker to choose an appropriate cone when the cone is not pre-specified, or when the current extreme rays are not sufficient to encode the preferences, as discussed in General Response-2.

Here "add" means we will specify each extreme rays one by one, and add them to the current set of extreme rays to form a set that represents the cone, when the cone is not pre-specified. We use this method for the experiments in Figures 3 and 5 to specify a cone to allow controlled ascent. We will further revise and clarify this in the paper.

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

The green dots in Figure 2 are the initial objective values, which we omitted in the plots. We have regenerated the plots in Figure R1 in the attached PDF. We will change them in the revision.

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

Both are FERERO, implemented with Algorithm 1. The difference is the choice of the preference vectors represented by the dashed arrows. Here, using the two results with different preference vectors, we want to show that FERERO can model flexible preferences.

Q4. What is the difference between the algorithms in Fig. 3 (c) and (f)?

Both are FERERO, implemented with Algorithm 1. The difference lies in the experiment settings, as discussed in Section 5.1, lines 278-288. Specifically, the main difference is the initial values of the objectives. In Figures 3(a-c), all the initial objectives are in between the yellow and green preference vectors, and all three methods converge to the Pareto front, but their required iterations and convergence speeds are different. In Figures 3(d-f), the initial objective values are close to the blue or red preference vectors. In this setting, for PMTL, the green and yellow trajectories fail to converge to the Pareto front, but the other two methods can converge to the Pareto front and align with the corresponding preference vectors.

W1. The step sizes in Theorems 2 and 3 depend on iterations $T$, which can be unknown in real-world problems.

Choosing step size depending on the number of iterations $T$ is common in optimization convergence analysis. For example, in [4,10,42], for the convergence analysis of unconstrained MOO, the step sizes are chosen based on the pre-defined value $T$.

In all our experiments, including the real-world emotion recognition and multi-lingual speech recognition tasks, a proper number of iterations $T$ is set before optimization, and then we can choose $\alpha_t$ accordingly. Detailed iterations and step sizes are provided in Appendix F.

We also have general convergence results where the step size $\alpha_t$ is not explicitly chosen to be dependent on $T$. See the derivation in Appendix E.2, Eq. (E.18). They can be summarized as follows

$

\sum_{t=0}^{T-1} \alpha_t ||d_t||^2 + \alpha_t ||H(\theta_t)||^2 = O\Big(\sum_{t=0}^{T-1}\alpha_t^2 + 1 \Big).

$

In such cases, we choose the step sizes to satisfy $\sum_{t=0}^{\infty} \alpha_t^2 < \infty$, and $\sum_{t=0}^{\infty} \alpha_t = \infty$. For example, $\alpha_t = \frac{1}{(t+1)^{\frac{1}{2}+\epsilon}}$ with $0<\epsilon\leq \frac{1}{2}$ is also a proper choice to guarantee convergence. Similar choices exist in stochastic single-objective optimization literature, see [f].

[f] Optimization Methods for Large-Scale Machine Learning, Bottou et al.

W2. Computational cost per iteration is higher than the scalarization method.

Yes, we have discussed this limitation in the Broader Impacts and Limitations section. Though traditional scalarization methods have better per-iteration complexity, the benefit of the proposed method with flexible preference modeling cannot be achieved by scalarization methods. For example, see the experiments in Figure 2. The linear scalarization (LS) method cannot find certain points on the Pareto front.

Despite this, our computational cost per iteration is similar to or lower than existing non-scalarization-based methods [23,30]. See General Response-1.

In addition, since we proposed single-loop algorithms (Algorithms 2, 3), existing techniques for fast approximation of Gramian evaluation in FAMO [h, Section 3.2] can be applied to our method to largely reduce the gradient evaluation per iteration.

[h] Liu et al., "FAMO: Fast Adaptive Multitask Optimization," NeurIPS, 2023.

W3 & Q1. Motivation & examples of the studied problem.

• In the introduction (Section 1), we provide two examples when the constraints are linear functions of the objectives, with further explanation in Appendix B.1. Furthermore, in the experiments of multi-lingual speech recognition, we have another example when the constraints are linear functions of the objectives.
• In the experiments in Figures 3 and 5, we provide examples of using a general polyhedral cone $C_A$, where $A$ is not an identity matrix, to allow controlled ascent for the update of the objectives.
• We provide more examples in the General Response-3.

Also note that, our framework and algorithm with subprogram Eq. (2.1) can be directly applied to handle more general constraints that are not necessarily linear w.r.t. the objectives. However, it may require other constraint qualification (CQ) assumptions, or the CQs can be more challenging to prove. We leave this for future work.

W4. $C_A$ is not used in experiments.

This might be a misunderstanding. The use of $C_A$ is reflected in that we use a more general matrix $A$ that is not necessarily the identity matrix. Please see our discussions in Section 5.

• For synthetic data, in Figures 3(c) and 3(f), we use a more general $C_A$ as discussed in lines 278-288.
• For multi-patch image classification, to avoid the fact that some preference vectors are not attainable, we choose different preference vectors and different corresponding $C_A$ to obtain the results in Figure 5.

Specifically, in these cases, the extreme rays of $C_A$ are determined by the given preference vector, then $A$ is computed by solving (3.5).

Q2. How are the experimental choices of step sizes related to the theory?

In our experiments, a proper $T$ is set before optimization, and we can choose $\alpha_t$ accordingly.

• In the deterministic case, and for Algorithm 2, in theory, we choose $\alpha_t = \Theta(\frac{1}{T})$, i.e., $\frac{c_1}{T} \leq \alpha_t \leq \frac{c_2}{T}$ for positive constants $c_1,c_2$. This theoretical result is reflected in that under the same experiment settings, when we choose smaller $T$, we can choose larger step size $\alpha_t$; see e.g., in Table 10, Appendix F.2.
• In theory, we require $\alpha_t c_h \leq 1$. This is reflected in the experiments in Tables 7,8,10 in Appendix F.

Q1. Evidence and importance of "flexible".

Indeed, this is a critical point of our paper!

The "flexibility" is evidenced by that we model both absolute and relative preferences. Furthermore, absolute preference considers both inequality and equality constraints. The relative preference considers more general partial order compared to existing works. "Flexible" means we can flexibly choose the preferences such as absolute or relative preferences or both, without limiting to preference vectors or certain partial order cones.

This is in contrast to scalarization methods [22] or other preference-guided MOL methods such as [23,30], which have relatively restrictive formulations. For example, this is further evidenced by the multi-lingual speech recognition experiments in Section 5.2, where both inequality and equality constraints are considered, which cannot be directly solved by existing methods [22,23,30] that focus on either inequality constraints or preference vectors. Also, as evidenced by Figures 3 and 5, we use a more general partial order cone to allow controlled ascent of objectives, which cannot be achieved by e.g., [23], without such flexibility.

This flexibility is important because it makes our method applicable to many other real-world problems as listed in General Response-3. Existing methods [22,23,30,33] without such flexibility may not be able to solve these problems.

Q2. Meaning of "cross" in Table 1. Is it not mentioned in the literature or inherently impossible to do?

The "cross" means it is not mentioned or provided in the corresponding literature.

Q3. Advantages of general partial order? Is it related to escaping weak Pareto optimality?

It is not related to escaping weak Pareto optimality. One key advantage of using general partial order is that it allows flexible modeling of more general relative preferences. And therefore, it extends the ability of the FERERO method to solve broader problems. We further explain with two detailed advantages below.

• It allows us to use a primal algorithm with controlled ascent, as discussed in lines 98-99. Therefore, it is possible for us to find certain Pareto optimal solutions that would be otherwise impossible to find with a primal algorithm using $A=I$, e.g., see Figures 3 (d,f).
• It makes the method applicable to many other real-world problems that cannot be solved using $A=I$, as discussed in General Response-3.

The ability to escape weak Pareto optimality is because our formulation in Eq. (2.1) considers finding update direction $d$ such that the descent amount is normalized by function values. If certain objective function values already achieve zero, then the algorithm finds directions that further decrease other objectives rather than stopping at weak Pareto optimality. The ability to escape weak Pareto optimality is proved in Appendix D.3.

Q4. Scalarization methods can escape weak Pareto optimality.

We are not aware that scalarization methods can directly escape weak Pareto optimality in general. For example, for linear scalarization on general nonconvex objectives, the gradient descent algorithm converges at a stationary solution of the linearly scalarized objective, which may be weakly Pareto optimal but not Pareto optimal.

However, we are aware that under certain conditions, the global solutions of scalarization methods with positive weights are Pareto optimal [32, Theorem 3.1.2]. We will make revisions and clarifications on this point in Table 5. And we are very willing to cite proper references if the reviewer could kindly provide some.

Q5. More description of per-iteration complexity.

We have provided a detailed description of the per-iteration complexity. See General Response-1.

Q6-1. What if preferences are unavailable, e.g., $B_h,B_g$ not provided?

When the absolute preferences are not available, the MOO problem reduces to an unconstrained one, and the proposed algorithm reduces to an adaptive cone descent algorithm with the following subprogram replacing Eq. (2.1).

$

\psi(\theta):=\min _{(d, c) \in \mathbb{R}^q \times \mathbb{R}} c+\frac{1}{2}||d||^2 \quad \text { s.t. } A \nabla F(\theta)^{\top} d \leq c\left(\mathbf{1}^{\top} A F(\theta)\right)^{-1} A F(\theta) .

$

If $B_h,B_g$ are not directly specified, they can be computed given the information of the preference. For example, if a preference vector $v\in \mathbb{R}^M$ is given, we can convert it to an equality constraint with $B_h$ satisfying $B_h v = 0$, where $B_h$ is formed by linearly independent row vectors that belong to $\mathrm{ker}(v)$.

Q6-2. The settings of preferences in experiments are hard to find.

In synthetic, multi-patch image classification, and emotion recognition experiments, the preferences are specified by the preference vectors, following the experiment settings in [30]. The details of the preference vectors can be found in Appendix F. In these experiments, they are generated uniformly between certain angles, and plotted as dashed lines or arrows in Figures 2-5. As discussed in the answers to Q6-1, we can compute $B_h$ from the given preference vector $v$ by finding the orthonormal row vectors that belong to $\mathrm{ker}(v)$. When $M=2$, $v = [v_1;v_2]$, $B_h = [-v_2, v_1] \in \mathbb{R}^{1\times 2}$.

In the multi-lingual speech recognition experiment, the problem formulation is provided in Eq. (5.2). In this case, $B_g = [1,0,0], b_g = -\epsilon_1$, and $B_h = [0,1,-1], b_h = -\epsilon_2$.

We will further clarify the preference settings in the revision.

For more practical examples of the preferences that fit in the framework we study in this paper, please see General Response-3.

Q7. Clarification of subtitles in Figures 2,3.

The subtitle of Figure 2(e) is correct. It shows the result of our method with the same preference vectors as the previous methods. We will change the subtitle of Figure 3(c) from "Ours" to "FERERO" to be consistent.

W1-1 & Q1. Relative preferences are handled by both partial order and inequality constraints. It is confusing and redundant. Can inequality constraints be converted to the preference cone?

We respectfully disagree. As mentioned in the abstract, relative preference is handled by the partial order, and absolute preference is handled by the constraints. The two preferences are generally not redundant but complementary. Essentially, the cone captures relative improvement of the objectives, and the constraints capture the absolute feasible regions of the objectives. Some detailed differences are explained below.

• Equality constraints cannot be captured by the preference cone with nonempty interior.
• The constants $b_g$ in the inequality constraints cannot be captured by the preference cone, as the cone can only guarantee relative improvement at each iteration.
• Our method deals with the two preferences differently. For preference cone, our Algorithm 1 with proper step sizes guarantees the next iterate always improves over the previous one in terms of the partial order induced by the cone, i.e., $AF(\theta_{t+1}) \leq AF(\theta_t) \leq AF(\theta_0)$. In contrast, for preference constraints, our method does not guarantee feasibility at every iteration, i.e., $G(\theta_t)\leq 0, H(\theta_t)=0$, but only when the algorithm converges.

Nevertheless, there are special cases where the constants $b_g$ in the inequality constraints align with the initial objective values $F_0$, with $B_g (F(\theta) - F_0) = B_g F(\theta) + b_g$. In this case, it is possible to convert the inequality constraints to preferences defined by a cone to ensure feasibility.

W1-2. The experiment on multi-task learning seems to only tackle constraints.

This might be a misunderstanding. See Figures 3, 5. We use a more general cone $C_A$ to allow controlled ascent of objectives.

W2. Computing the ordering cone by solving another LP is complex.

We do not always have to compute $A$. See General Response-2.

When $A$ needs to be computed from the given extreme rays, the linear programming (LP) in Eq. (3.5) can be solved in polynomial time w.r.t. $M$. In practice and our experiments, $M\ll d$, therefore, solving this LP requires much less computation/time than solving the main program (PMOL) to obtain the optimal $\theta$.

W3. Comparison metrics using the number of function/gradient evaluations.

Following your suggestion, we adopt these metrics. Results are summarized in General Response-1.

Q2. Take $AF(\theta)$ instead of $F(\theta)$ as objectives, and use $\mathbb{R}_+^M$ as the preference cone.

Interesting point! This is possible only under the special cases with more restrictions on the constraints and preference cone.

• This is possible when there are no constraints. However, for constrained problems with constraints defined as functions of $F(\theta)$, if we use $AF(\theta)$ as objectives, we need to compute $B_h A^{-1}(AF(\theta))$, which may lead to higher computational complexity, and thus not practical. Moreover, $A$ may not always be invertible in general.
• This is only possible when the preference cone is polyhedral. For more general preference cones, they may not necessarily be written as in Definition 1. Therefore, one cannot use $AF(\theta)$ as objectives in such cases. However, in such cases, our FERERO method can be extended to cover the more general preference cones $C$ by replacing Eq. (2.1), $A\nabla F(\theta)^\top d \leq c (\mathbf{1}^\top AF(\theta))^{-1}AF(\theta)$ with $\nabla F(\theta)^\top d \leq_C c (\mathbf{1}^\top F(\theta))^{-1} F(\theta)$.

Q3. Inequality constraints in Theorem 2 are not present in Eq. (3.2).

Sorry for the confusion. Indeed, we focus on equality constraints ($M_g = 0$) for Theorem 2. We will further clarify this in the paper. The results can be extended to include inequality constraints in future work.

Q4. Clarification of multilingual constraint in Eq. (5.2). Would it be more reasonable to have the loss gap smaller than a threshold?

The multilingual constraint in Eq. (5.2) is a heuristic choice based on the experience. We found that in this experiment setting, if $\epsilon_2$ is close to zero, the performance in Chinese will be much better than the performance in English. However, we want the performance in both languages to be similar, hence we impose this equality constraint.

Q5. Clarification of emotion loss.

The emotion loss refers to the emotion classification loss. The task is to predict 6 types of emotions from 593 songs on the Emotions and Music dataset [38]. See Appendix F.2. We will add explanations of the emotion loss in the main text in the revision if space allows.

Q6. How are the scalarization weights in Figure 2(a) selected? Is the weight selection related to extreme rays?

The scalarization weights are selected uniformly from a simplex following the experiment settings in [30]. They are not related to extreme rays. We will clarify this in the revision.

Q7. Clarification of Figure 4.

• Missing square plots. Sorry for the confusion. This is because we limit the plot scales to a certain range to make the majority of the results clear. We add plots with larger scales in Figure R2 in the attached PDF. We will include the plots in the revision.
• Controlling constraint violation. Yes, constraint violation can be controlled by the hyperparameter $c_h$. Larger $c_h$ will make the constraint violation smaller.
• Figure (e) green plus is dominating. Indeed, in this experiment, under the green preference vector, XWC-MGDA gives the best solution compared to other methods. However, under other preference vectors, the solutions of XWC-MGDA are not dominating, and the overall hypervolume of XWC-MGDA calculated from all the solutions is worse than the proposed method.

Q8. Minor issues.

Thank you for your detailed comments! We will revise the paper accordingly.