Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance

Thanks for acknowledging that we propose a novel formulation and an easy-to-understand novel method for preference-guided multi-objective optimization, our proof is sound and interesting, and the experiments are sufficient with sound analysis.

Below we address your concerns point by point. The link to additional results is https://anonymous.4open.science/r/FOOPS-F746/ICML3045_rebuttal.pdf

Claims And Evidence: "The preference-guided multi-objective optimization problem can be solved through a semivectorial bilevel optimization problem" is unclear... How are $G(x)$ and $H(x)$ related to $f_0(x)$? Whether they are solving the same problem?

Yes, $F(x)$ remains the same. The relation of $G,H$ to $f_0$ is that $f_0$ can be chosen as $f_0(x) = ||H(x)||^2 + ||[G(x)]_+||^2$. $f_0$ is minimized when $H(x)=0$ and $G(x)\leq 0$. In our experiments, we show the example for equality-constrained problems without $G$ and with $f_0(x) = ||H(x)||^2$. See Section 6, and Eq. (16) for the speech experiment.

The two formulations are not equivalent mathematically. But both can be applied to preference-guided multi-objective learning with different emphasis on either satisfying preference or achieving weak Pareto optimality. As discussed in Section 3.3 and Section 6 in our paper, the constrained formulation in e.g., PMTL and FERERO with preference modeled by constraints $G$ and $H$ puts more emphasis on satisfying the preference, while the FOOPS formulation with preference modeled by $f_0$ puts more emphasis on achieving weak Pareto optimality.

Methods And Evaluation Criteria: While the proposed method is easy to understand and the evaluation is sufficient, I am a bit curious on whether the proposed method can be combined with other bi-level optimization methods, as is also mentioned in Appendix A.1. Specifically, after converting the lower-level constraint to a single-objective constraint, I suppose the converted problem can be also solved by some bi-level optimization methods other than the penalty-based formulation? Some empirical comparisons can be useful here.

• Other bilevel methods. Thanks for the suggestion. Indeed, the penalty method used in this paper is not the only way to solve a bilevel problem. However, the existing methods listed in Appendix A.1, Table 5 require different assumptions which cannot be satisfied by our converted problem. Therefore, the methods in Table 5 cannot be directly applied to our converted problem. However, we provide a discussion on how some other methods could be applied under certain additional assumptions. For example, the recent concurrent AGILS (Bai et al., 2024) method can be applied when the merit function $v_{l,\tau}$ has HEB with $\eta \geq 1$.

• Empirical comparisons. Since other existing bilevel methods require different assumptions, they cannot be directly applied to our converted problem. Further investigation is needed to check whether the methods still work under weaker assumptions. The concurrent AGILS (Bai et al., 2024) method may be applied to specific problems satisfying the assumptions therein, which we leave for future work. We provide a comparison to other OPS methods such as PNG in Figure A and Table B in the link.

Other Comments Or Suggestions: The authors seem to have modified margins in some places, e.g., lines 110-116 and lines 432-439. This should be strictly forbidden and some reasonable explanation is necessary here.

Thanks for spotting this. We would like to clarify that we did not intentionally or explicitly alter the margins. Instead, we used the {\small } environment in LaTeX to reduce the size of Equations (5) and (16) so they would better fit the space. This inadvertently caused the line spacing for lines 110-116 and 432-439, immediately before the equations, to appear smaller, despite our attempt to limit the {\small } environment to the equations themselves. In response to the reviewer’s feedback, we will modify the paper to remove this unintended spacing issue.

---

We hope our rebuttal resolves the reviewer's concerns and the reviewer can reconsider the rating of our paper. Thanks!

Thanks for acknowledging that the problem is important and the bilevel perspective is new. We would like to emphasize that the bilevel problem in this paper with non-convex vector-valued lower-level objective is much more challenging and nontrivial, as pointed out by Reviewer XkmK.

Below we address your concerns. The link to additional results is https://anonymous.4open.science/r/FOOPS-F746/ICML3045_rebuttal.pdf

W1.Writing&assumptions not clear... Explicitly point out all assumptions before the theorems.

It might be a misunderstanding that the HEB and KL conditions are assumed. Instead of directly assuming them, we prove them based on the properties of $F$. In our theorems, we list all the required assumptions in the beginning and then discuss other conditions that can be proved. We will clarify this.

W2.Motivation of smoothing the merit function ...Validate this in the experiments?

Smoothing is commonly used for nonsmooth optimization problems, whose motivation is well-studied in prior works, e.g. [R1] and references therein. [R1] shows that smoothing is necessary for finite-time convergence of nonconvex nonsmooth problems using any algorithm. Therefore, we use LSE to smooth the max-min nonsmooth $\bar{u}$ to ensure finite-time convergence, which is widely used in prior works, e.g. [R2]. In our experiments, we find that without smoothing, it could return NaN (not a number) errors and the algorithm could diverge.

[R1] Deterministic Nonsmooth Nonconvex Optimization. M.I. Jordan, et. al. COLT 2023.

[R2] An alternative softmax operator for reinforcement learning. Kavosh Asadi, et. al. ICML 2017.

W3.Smoothing introduces hyperparams. \tau and l. How to select them? Provide ablation studies.

We choose $\tau,l$ to be small and to ensure differentiability. We use grid search to tune them. See more details in Appendix F. We provide an ablation study in Table C in the link.

W4.The assumptions could be strong...The subanalyticity&KL assumptions make the analysis less applicable...Justification of problems in the experiments satisfying these assumptions (ok if partially)?

Note that compared to existing works for OPS (Table 2) and bilevel optimization (Table 5), which usually require convexity or PL assumptions, our assumptions are actually much weaker. The subanalylticity and KL conditions are weaker than PL, see more discussions in Appendix C with examples justifying the assumptions.

W5.In lemma 3.4, meaning of global subanalyticity?...A definition should be provided.

We have mentioned in the main paper, lines 204-216 that, the definition of (global) subanalyticity, including both subanalytic functions and sets is provided in Appendix C, Definitions C.1 and C.2.

W6.In theorem 3.5, what is the definition of $(\epsilon,\delta)$-global solution for (CP)?

The $(\epsilon,\delta)$-global solution for (CP) is that, $f_0(x) - \min_{x\in {\cal X}_{\delta}} f_0(x) \leq \epsilon, x\in {\cal X}_{\delta} = \{x \in {\cal X} \mid v_{l,\tau}(x) + \tau\ln M \leq \delta \}.$ This is a widely used definition for constrained optimization.

W7.The algorithm is complex, containing multiple hyperparameters like $\tau, l, \gamma_t, K_t, \alpha_t,\beta_t$, as well as two projections in steps 5 and 8. Compared to previous methods like EPO, FERERO, this is less appealing.

This might be a misunderstanding. The algorithm is general such that it can be applied to both the cases when $\cal X$ is compact and when ${\cal X} = R^q$. When ${\cal X} = R^q$, the two projections are not needed, which is the case in our experiments. $K_t$ can be chosen to be small like 1 or 2. As a comparison, FERERO also requires choosing hyperparameters such as $\alpha_t,\gamma_t,K,c_g,c_h$. So the number of hyperparameters is similar. They do not make FOOPS more complex or inefficient.

We do provide a run time in Appendix F, Table 10 in the paper, and Table A in the link to show FOOPS is comparable or more efficient than FERERO.

W8&Methods&Evaluation&Experiment: Experiments are not convincing. In Table 4, it is very close to FERERO-FT ...confidence interval... A running time comparison could be provided to further justify the efficiency compared to FERERO.

We respectively disagree. We show in Table 3 that FOOPS achieves much better hypervolume compared to FERERO and other baselines. In Table 4, it achieves comparable average performance as FOOPS. So we believe our result demonstrates FOOPS is effective, as acknowledged by all other reviewers. This experiment takes much longer time. We will run additional experiments add the confidence in the revision.

Running time comparison is given in Appendix F, Table 10 in the paper, and Table A in the linked PDF. Results show FOOPS can be faster than FERERO.

References: More works on differentiable MOO could be discussed.

Thanks, we will include a discussion in the revision.

---

We hope we have addressed your concerns and you can reconsider the rating of our paper. Thanks!

Thanks for acknowledging that we consider BLO with non-convex vector-valued lower-level objective with stronger guarantees, which is different from prior works, and the experiment results are promising.

We would like to emphasize that the non-convex vector-valued lower-level objective is much more challenging and nontrivial, as also pointed out by Reviewer XkmK.

Below we address all your concerns. The link to additional results is https://anonymous.4open.science/r/FOOPS-F746/ICML3045_rebuttal.pdf

Claims: How to incorporate Preference Guidance...

This might be a misunderstanding. In our paper, the preference guidance was not replaced with another objective from $F$, but was enforced via a new upper-level preference objective $f_0$.

Our experiments include the preference vector guided problems with $f_0(x) = ||H(x)||^2$, and $H(x)=0$ describing the preference vector; see Section 6. See also the response to Reviewer SqKr-Claims. We will clarify this.

Broader Literature: ...scale up to applications in larger models.

We have experiments for larger models for speech recognition. See Section 6, Table 4. The model size is around 64.5M, with more details provided in Appendix F.

Methods&Evaluation: Relationship between (1) and CP.

In our paper, below Eq. (CP), we have discussed that as $l,\tau \downarrow 0$, (1) and (CP) are equivalent. For $\tau \downarrow 0, l>0$, (1) and (CP) are equivalent under conditions in Proposition 3.2-2-b). Moreover, by Proposition 3.2, the approximate solutions to (CP) with $v_{l,\tau}(x) + \tau \ln M \leq \epsilon$ are $\epsilon'$-weak Pareto optimal. Therefore, an $\epsilon$-global/local solution $x$ to (CP) satisfies that it is global/local $\epsilon'$-weakly Pareto optimal, and that $f_0(x)\leq f_0(x^*)$, with $x^*$ being the global/local solution to (1). We will add this discussion in the modified paper.

Theoretical Claims: In Proposition 3.2, $\epsilon=\tau\ln M$,... choose $\tau$ as a function of $M$...?

Yes. In our experiments, $M$ is fixed for a problem, and $\tau$ is chosen according to $M$, so we can ensure $\epsilon$ to be sufficiently small.

Experimental Designs/Analyses: ...Compare with methods listed in Table 2.

It is hard to compare with the methods since they do not provide open-source code. Furthermore, these methods require different assumptions that cannot be satisfied in our case. For example, for the lower-level objective, PMM and TAWT require strong convexity or invertible Hessian, which does not hold in our problems. So these methods cannot be applied.

As per the reviewer's request, we implement PB-PDO and PNG. Figure A and Table B in the linked PDF summarize the results, which show they sometimes cannot converge to the Pareto front, and they achieve worse hypervolumes compared to FOOPS.

W1.How should $\tau$ and $l$ be chosen theoretically and in practice?

As discussed in Section 3.1, theoretically, smaller $\tau$ approximates $\bar{u}$ better, but also increases the smoothness constant. We need to choose $l \geq \ell_{f,1}$ to ensure $\nabla v_{l,\tau}$ exists and can be computed. In practice, we choose relatively smaller $\tau$ and $l$ but not smaller such that $v_{l,\tau}$ is not differentiable. Detailed choices are provided in Appendix F.

W2.Thm 3.6, 3.7, and 3.9 appear to be direct adaptations from (Shen, 2023)...

We respectively disagree. The theorems compared to (Shen, 2023) are not minor. In (Shen, 2023), the focus is on a scalar lower-level objective satisfying the QG condition (a special case of HEB with $\eta=2$). Directly applying the results from (Shen, 2023) is impossible as we can only make assumptions on objective $F$, but not on $v_{l,\tau}$, and $v_{l,\tau}$ does not satisfy this condition even if $F$ satisfies. In comparison, our theories require much weaker assumptions, as discussed in Appendix A.1, lines 749-756. In addition, (Shen, 2023) assumes the QG holds on the entire domain. However, the exponential function in our case is not globally subanalytic on the whole domain (Remark C.9). Instead, we can prove that $v_{l,\tau}$ is globally subanalytic on any bounded subanalytic set given that the objective $F$ is subanalytic. Thus, the HEB holds on the bounded subanalytic set, which is the base of the proof for Thm 3.6, 3.7, and 3.9.

W3.Convergence analysis is relatively trivial...

We respectively disagree. Our main contribution is to convert the challenging semivectorial bilevel optimization problem to a simpler penalty problem with guarantees on their relations, and easy-to-evaluate gradients for the penalty problem. Building upon this, the convergence of the penalty problem can be analyzed using existing tools.

By converting challenging problems to simpler ones, we have a simple convergence analysis. This actually shows the strength rather than weakness of our method.

---

We hope the concerns are addressed and the reviewer can reconsider the rating of our paper. Thanks!

Thanks for supporting our work, acknowledging that we propose a new efficient method to solve a very challenging semivectorial bilevel optimization problem, with a strong theoretical guarantee, and with intuitive experimental result demonstrating the authors' claims.

We address your other comments below. The link to the additional results is https://anonymous.4open.science/r/FOOPS-F746/ICML3045_rebuttal.pdf

1.Lacking analysis on computational cost. Provide the order of computational cost and memory cost per iteration, and the real running time for each method.

Thanks for the suggestion. In Appendix F, Table 10, we have provided the real running time for each method. We add the memory cost per-iteration in Table A in the link.

2.In Appendix A, the authors discuss several works on bi-level optimization (BLO). I suggest they also provide a discussion on multi-objective bi-level optimization (MOBLO) problems, as explored in [1-5]...

Thanks for the suggestion. We will incorporate these works in our paper.

3.Typo: consistency of the punctuation at the end of the formulas.

Thanks for the suggestion. We will check to ensure the consistency of the punctuation.

4.The experiment on the multi-patch image classification problem (using Multi-Fashion+MNIST) is relatively simple and may not fully demonstrate the capabilities of the proposed method. Could the authors conduct experiments on more challenging and widely used datasets, such as Office-31 or Office-Home?

We have included the experiment for larger models in our paper for speech recognition; see e.g., Table 4 in Section 6. The model size is around 64.5M, much larger than the image classification problem. More details are provided in Appendix F. The benchmarks Office-31 and Office-Home suggested by the reviewer are designed for multi-task learning, but not for preference-guided multi-objective learning studied in this paper, thus not very suitable for our problem. To do such experiments, we need to first define a preference objective $f_0$, then conduct the experiments using our method. We will include the results in the revision.

5.It seems the number of objectives in the LL subproblem is small in the experiments. Could the authors conduct experiments on more challenging settings, $M>20$?

Theoretically, our method can be used for a larger $M$ without significantly increasing complexity. We test this on a toy problem with $M=25$ and report the running time till convergence in Table A in the linked PDF, the last row, which shows the run time can be much shorter compared to FERERO. The problem is defined as $f_m(x) = (x - m)^2, m\in [M]$, $H(x) = f_1(x) - f_2(x)$, and $f_0(x) = ||H(x)||^2$. $x$ is initialized to be $100$. We will find some other real-world problems with more objectives and include the experiments in the revised paper.

---

We hope the concerns are addressed and the reviewer can continue to support our paper. Thanks!