- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper investigates the multi-objective bilevel optimization (MOBL) problem, focusing on a slightly different setting, Preference-Aware Optimistic Selection (PAOS), in which the user preference is explicitly applied to guide solution selection at both levels.
It reformulates the lower-level problem by adding a term that combines the upper-level function with an adaptive preference coefficient. Then, to solve this new problem, the proposed method uses several techniques, such as the conjugate gradient method and weighted-Chebyshev scalarization.
The paper provides theoretical results and numerical experiments across various benchmarks.
Critical strengths
This paper is well-motivated, as preference control in MOBL is an interesting and open question. The experiments also seem good.
Critical weaknesses
My primary concerns lie in the theoretical analysis. (i) The paper does not establish a clear relationship between the reformulated problem and the original MOBL problem (also see Question 1). (ii) The assumptions are quite restrictive. The requirements of strong convexity and three-times continuous differentiability of the objective functions limit the scope of this paper.
Questions for authors
(1) The main theorem is not very clear to me. What is the formal definition of ? If I understand correctly, does not represent a combination of the exact hypergradients of the original MOBL problem. Thus, I wonder what Theorem 1 implies for the original problem.
(2) Equation 2 may not fully capture the original Pareto frontier when the functions are nonconvex. Essentially, it uses a weighted sum, or linear scalarization, of the objectives, which is known to potentially miss Pareto-optimal solutions in nonconvex settings.
(3) It seems that Equation 3 may introduce a systematic bias with respect to the user preference, and the subsequent techniques, although they adapt , do not seem to address this issue. Could the authors provide more evidence or insight?
Minor mistake: Line 210: is not Hessian.
Please address these questions as thoroughly as possible.
5 comments
Response to Reviewer C8J1
C-Q1 — The exact direction and its original-problem meaning
(Please refer to Sec. 3.4 and Appendix A.3–A.4 of the revised manuscript for the fully typeset formulas. OpenReview cannot reliably render the required notation; we apologize for using simplified notation below.)
1. What the exact direction denotes. Your interpretation of the selected direction is correct: it combines exact hypergradients of the selected response branch. At iteration t, let H*_t denote the hypergradient matrix evaluated at an exact local response of the selected lower objective, with ρ and the selector α_t held fixed during differentiation. Let λ*_t solve the weighted-Chebyshev subproblem in Eq. (5) using that response’s exact objective values and hypergradients. The reference direction is
d̄_t = H*_t (r ⊙ λ*_t).
“Exact” distinguishes this reference direction from the implemented direction, which includes finite-response, linear-solver, damping, and Pareto-subproblem approximation errors. Appendix A.1 defines the reference direction, and Appendix A.4, Eqs. (37) and (41), bounds the hypergradient and direction errors.
2. Theorem 1 directly addresses original-branch stationarity. Thank you for asking what the theorem implies for the original problem. We have revised its statement so that Theorem 1 now directly bounds the mean squared Pareto-stationarity residual on a branch of original lower-level solutions (Sec. 3.4, Eq. (11)).
Let H₀(x) collect the hypergradients of the original upper objectives evaluated along this branch. A zero residual means Pareto stationarity of the upper objectives restricted to the branch. The proof combines two results. Appendix A.5, Lemma 2, bounds the average squared exact selected direction.
For comparison with related methods, our response to Reviewer GXA8, “Theoretical guarantees and comparison with related methods,” includes a table separating lower-level assumptions, upper-level conditions, and theoretical guarantees, with separate entries for Proposition 1 and Theorem 1.
| Method / result | Lower-level assumptions | Upper-level and other conditions | Theoretical guarantee |
|---|---|---|---|
| MOML, Thm. 2 | Unique minimizer; uniformly bounded and uniformly convergent lower iterates | Compact convex upper domain; uniform Lipschitz continuity; approximate and exact reduced objectives are P-convex and strictly P-convex, respectively | Set convergence of efficient solutions and minimal objective values as the lower approximation improves |
| FORUM, Thm. 1 | Global strong convexity; Lipschitz gradient | Bounded objectives and gradients; Lipschitz gradients; bounded value-function constraint violation along iterates | Finite-iteration KKT-stationarity and feasibility bounds for the value-function reformulation |
| gMOBA, Thm. 3.9 | Global strong convexity; Lipschitz first and second derivatives | Closed convex upper domain; smooth parts bounded below with bounded Lipschitz gradients; convex continuous nonsmooth parts | Every accumulation point of the upper iterates is Pareto stationary for the reduced problem |
| WC-MHGD, Thm. 5.5 | Global strong convexity; Lipschitz gradient and relevant second derivatives | Lipschitz objectives and gradients; strictly positive preferences; prescribed solver accuracy and step sizes | Finite-iteration bound on the exact preference-weighted hypergradient direction, yielding approximate Pareto stationarity |
| MOMEHA, Thm. 1 | Smooth nonconvex objective; nondegenerate envelope-constraint gradient | Lower-bounded objectives with Lipschitz gradients; positive preferences; additional penalty boundedness and schedule for vanishing feasibility error | Finite-iteration stationarity for the relaxed envelope-constrained problem; feasibility decay under the additional penalty conditions |
| PAOS: Proposition 1 | Nonconvexity and nonunique minimizers allowed; continuity, existence, and compactness | Fixed upper variable and selector; continuous selected upper criterion; exact global surrogate minimization | Every accumulation point as ρ → 0 is an original lower minimizer that minimizes the selected upper criterion over the original lower solution set |
| PAOS: Theorem 1 | Smooth local continuation of original lower minimizers; positive lower Hessian; uniform perturbation constants | Fixed small ρ; unconstrained upper domain; positive preferences; local derivative regularity; lower-bounded merit with conditional descent and Lipschitz selector dependence | Finite-iteration mean squared original-branch Pareto-stationarity residual bound, accounting for selector drift, direction bias, noise, and an O(ρ²) perturbation term |
Response to Reviewer C8J1
C-Q2 — Linear selection is not a full-frontier parameterization
1. We clarify the role and scope of Eq. (2). We agree that linear scalarization is not a complete parameterization of a non-convex Pareto frontier. Eq. (2) has a more specific role: for a fixed upper variable , the original lower objective first defines , and the mixture then selects a response within that original solution set. Strictly positive weights select a Pareto-efficient response within , but varying the weights can miss unsupported efficient responses when this attainable set is non-convex (Sec. 3.2, Eq. (2); Appendix A.2).
2. Our contribution does not rely on full-frontier coverage by Eq. (2). PAOS uses this criterion for response selection, then computes a mixture from the current selected response’s objective and hypergradient geometry (Eq. (5)). That mixture updates the selector (Eq. (7)), which shapes the next lower-level response through Eq. (3), closing the loop in Eq. (8) and Fig. 2. Our claim is therefore about feedback-guided formation of preference-conditioned responses, not recovery of every unsupported point on a non-convex frontier.
C-Q3 — How the selector remains preference-conditioned
1. We distinguish the user preference from the adaptive selector. The user preference remains fixed throughout optimization; is a response-selection state, not a replacement for . We initialize . At each iteration, enters both the upper-level Pareto subproblem and update (Eqs. (5)–(6)), and the next selector is formed from the preference-conditioned target
{\mathbf 1^\top(\mathbf r\odot\boldsymbol\lambda_t)}, \qquad \boldsymbol\alpha_{t+1} =(1-\beta)\boldsymbol\alpha_t+\beta\mathbf q_t.$$ Thus, $\boldsymbol\alpha_t$ may differ from $\mathbf r$ because it incorporates conflicts revealed by the *current response*, but the feedback entering Eq. (3) remains conditioned on the user’s preference (Sec. 3.3, Eqs. (5)–(8); Fig. 2). **2. We make the preference effect explicit.** The local analysis distinguishes improvement of the selected criterion from improvement of the *fixed user criterion*. Applying Proposition 2 to the latter gives ψ_r(x, y(ρ, α)) − ψ_r(x, y⁰) = −ρ a(r)ᵀ G⁻¹ a(α) + O(ρ²). *(Please see Proposition 2 and Appendix A.3 of the revised manuscript for the fully typeset formula. OpenReview does not reliably render the required notation; we apologize for the simplified display here.)* Here a(r) and a(α) denote the lower-response gradients of the upper-objective mixtures associated with the fixed user preference and the adaptive selector, respectively, and G is the positive-definite original lower Hessian. **Positive cross-alignment yields a first-order improvement in the user’s fixed criterion** (Appendix A.3). **3. We report preference-wise evidence.** In the non-convex double-well study, the preferred branch changes with the specified user preference. PAOS reaches a valid preferred response in all 20 paired runs at **each** tested preference, whereas each open-loop control reaches 10/20 (Appendix B, Table 7): | User preference $w$ | WS-HG | TCH-HG | WC-MHGD | PAOS | |---|---:|---:|---:|---:| | 0.1 | 10/20 | 10/20 | 10/20 | **20/20** | | 0.3 | 10/20 | 10/20 | 10/20 | **20/20** | | 0.7 | 10/20 | 10/20 | 10/20 | **20/20** | | 0.9 | 10/20 | 10/20 | 10/20 | **20/20** | The learning-task evidence is consistent with this preference-conditioned behavior: on MNIST, Full PAOS improves target-aligned average accuracy from **84.66% to 84.73%** and reduces target validation CE from **0.6565 to 0.6522** relative to Static preference (Sec. 4, Table 3). Together, the mechanism, local alignment condition, and preference-wise outcomes explain why the selector adapts without simply discarding the user’s target. #### C-M1 — Correcting the derivative terminology Thank you for catching this terminology error. We have corrected the description around Eq. (4): $A_t=\nabla^2_{\mathbf y\mathbf y}\widetilde g_t+\delta I$ is the damped lower-level Hessian, whereas $B_t=\nabla^2_{\mathbf x\mathbf y}\widetilde g_t\in\mathbb R^{p\times q}$ is the **mixed derivative matrix**. We use the same terminology in the theoretical appendix.
Response to Reviewer C8J1
Thank you for recognizing preference control in MOBL as a well-motivated open problem and for the positive assessment of our experiments. We address the theoretical and methodological concerns below.
C-W1 — Connecting the selected problem to original MOBL
1. The original-solution-set connection. We now make explicit that the original lower objective g defines the admissible response set Y⋆(x) in Eq. (1), while Eq. (2) selects a preferred response within that set. The selected objective in Eq. (3), g+ρψα, implements this selection during response formation; it reduces to g at ρ=0. More importantly, Proposition 1 proves that, under its existence and compactness conditions, every accumulation point of its exact global minimizers as ρ↓0 belongs to the optimistic set in Eq. (2). This establishes the selection mechanism’s precise connection to the original lower-level solutions (Sec. 3.2–3.4; Appendix A.2).
2. The finite-ρ connection. We also quantify what changes when selection strength is positive. Near a nondegenerate original lower minimum, let G=∇yy2g≻0 and aα=∇yψα. Proposition 2 shows that, for sufficiently small ρ,
=-\rho\,\mathbf a_{\boldsymbol\alpha}^{\top}G^{-1}\mathbf a_{\boldsymbol\alpha}+O(\rho^2), \qquad \Delta g =\frac{\rho^2}{2}\mathbf a_{\boldsymbol\alpha}^{\top}G^{-1}\mathbf a_{\boldsymbol\alpha}+O(\rho^3).$$ Thus, when $\mathbf a_{\boldsymbol\alpha}\ne0$, the selected upper criterion improves at first order, while the original lower objective changes at second order (Sec. 3.4, Eqs. (9)–(10)). For a regular branch that is valid for the original lower problem, we further relate the selected direction $\bar{\mathbf d}$ to the original branch’s Pareto-stationarity residual: $$s(H_0)\leq\frac{\|\bar{\mathbf d}\|}{r_{\min}}+C_H\rho, \qquad s(H)=\min_{\mathbf w\in\Delta_S}\|H\mathbf w\|.$$ This pointwise relation is now Eq. (32) in Appendix A.3. The revised Theorem 1 (Sec. 3.4, Eq. (11)) combines it with the selected-direction bound to directly bound the mean squared Pareto-stationarity residual on the original solution branch. **3. We check original lower-level validity in the analytical study.** The double-well experiment counts a preferred response as valid only if it has the preferred sign, satisfies $|z_T|\geq0.9$, **and** meets $g(\mathbf x_T,z_T,v_T)\leq10^{-3}$ under the *original* lower objective. The feedback ablation reports: | Feedback (Appendix B, Table 8) | Preferred sign ↑ | Valid preferred branch ↑ | Median projected regret ↓ | |---|---:|---:|---:| | Static, $\beta=0$ | 67/80 | 0/80 | 0.243 | | PAOS, $\beta=0.25$ | 76/80 | 76/80 | 0.148 | | **PAOS, $\beta=1$** | **80/80** | **80/80** | **0.134** | In the separate balanced branch study, PAOS also obtains 80/80 valid preferred responses with a median terminal gap of **$2.32\times10^{-6}$ under the original $g$** (Appendix B, Table 7 and the following paragraph). These original-objective checks complement the solution-set limit and the local finite-$\rho$ bounds: **the selected response is evaluated against the original MOBL lower problem, not merely against PAOS’s surrogate.** #### C-W2 — What the regularity assumptions cover **1. Our selection result covers non-convex lower problems.** Proposition 1 requires continuity, existence of minimizers, and compactness of the relevant lower-level sublevel set (Assumption 1); it requires **neither strong convexity nor three-times continuous differentiability**. Its optimistic-selection limit therefore permits non-convex lower objectives and multiple lower-level minimizers (Sec. 3.4; Appendix A.1–A.2). **2. The stronger conditions support local quantitative guarantees.** Theorem 1 additionally requires that the unperturbed branch consists of original lower-level minimizers, that the perturbation constants are uniform along the iterates, and that the coordinator satisfies the conditional descent assumption in Appendix A.1. Under these conditions, it bounds the mean squared Pareto-stationarity residual on that original branch. Proposition 1 uses only the continuity, existence, and compactness conditions in Assumption 1. **3. We evaluate the method beyond those local guarantees.** The analytical double-well has a non-convex lower objective with two original optimal branches; PAOS obtains a valid preferred response in **80/80** paired runs (Appendix B, Eqs. (45)–(47), Table 7). We also evaluate the algorithm on four learning tasks with neural models (Sec. 4, Table 1). We present these as empirical evidence of the method’s behavior in broader settings, while keeping the formal guarantees tied to their stated assumptions.