Efficient Hessian-Free Methods for Multi-Objective Bilevel Optimization with Nonconvex Lower Level

Feihu Huang; Yicong Jiang

Efficient Hessian-Free Methods for Multi-Objective Bilevel Optimization with Nonconvex Lower Level

T0 review · 2 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims that multi-objective bilevel optimization with a nonconvex lower level is solvable by a single-loop, Hessian-free algorithm family that converges to Pareto-stationary points, deterministically at rate $O(T^{-1/2})$ and…

desk verdict A substantial algorithmic extension whose central equivalence claim fails under weak convexity, so both convergence theorems currently solve a surrogate problem rather than the stated one. read the letter →

arxiv 2608.12704 v2 pith:G3LOWZQP submitted 2026-08-13 math.OC cs.LG

Yicong Jiang , Feihu Huang This is my paper · ORCID

classification math.OCcs.LG MSC 90C2990C2690C3090C15

keywords multi-objectivebileveloptimizationnonconvexlowerlevelMoreauenvelopeHessian-freealgorithmsmoothTchebycheffscalarizationParetostationaritystochasticmomentumsingle-loop

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper takes on multi-objective bilevel optimization, where an upper-level decision must balance several conflicting objectives, each evaluated at the solution of a nested lower-level problem, in the regime where that lower level is nonconvex. Previous multi-objective bilevel methods required convex or strongly convex lower levels, which excludes many modern machine-learning applications. The paper claims that a Moreau-envelope reformulation together with smooth Tchebycheff scalarization turns the problem into a single-level constrained problem that can be attacked by alternating gradient steps, with no Hessian computation and no inner loop. For the deterministic method MOMEHA and the stochastic momentum variant MB-MOMEHA, it proves convergence to a relaxed Pareto-stationarity concept at rates $O(T^{-1/2})$ and $O(T^{-(1/8-\delta)})$, respectively, and reports better Pareto fronts than existing methods on few-shot meta-learning and neural architecture search.

What carries the argument

The load-bearing mechanism is the Moreau envelope $\upsilon_\gamma(x,y)=\min_\theta\{g(x,\theta)+\frac{1}{2\gamma}\|\theta-y\|^2\}$, which converts the lower-level problem into an explicit scalar constraint $g(x,y)-\upsilon_\gamma(x,y)\le 0$, together with the smooth weighted Tchebycheff scalarization $F_w^{\mathrm{STCH}}(x,y)=\frac{1}{\mu}\log\sum_{i=1}^m\exp(\mu w_i(f_i(x,y)-z_i))$, which encodes user preferences and enables Pareto-front exploration. The algorithms maintain an auxiliary variable $\theta$ that tracks the envelope minimizer with a single gradient step per iteration, so the overall scheme is single-loop and Hessian-free. The stationarity measure is a relaxed concept, $\varepsilon_c$-$\varepsilon_s$-Pareto stationarity, defined through the normal cone of the $\varepsilon_c$-relaxed feasible region, because penalty iterates can remain slightly infeasible with respect to the envelope constraint.

What would settle it

Run MOMEHA on the scalar bilevel problem $\min_{x,y} (x-1)^2+y^2$ subject to $y\in\arg\min_y(-y^2+y^4)$. The lower-level minimizers are $y=\pm 1/\sqrt{2}$, not the stationary point $y=0$; if the reported $\varepsilon_c$-$\varepsilon_s$-Pareto stationary point is at $y=0$, the reformulation has certified a point that is not a true bilevel solution.

Watch

Extended reading notes

Core claim

The paper's central claim is that the Moreau-envelope reformulation of bilevel programs, which replaces the lower-level argmin by the explicit constraint $g(x,y)-\upsilon_\gamma(x,y)\le 0$ and, under weak convexity, by the stationarity condition $\nabla_y g(x,y)=0$, can be combined with smooth weighted Tchebycheff scalarization to produce preference-guided, Hessian-free, single-loop algorithms for multi-objective bilevel problems with nonconvex lower levels. For the deterministic algorithm MOMEHA it establishes convergence to an $\varepsilon_c$-$\varepsilon_s$-Pareto stationary point of the relaxed constrained problem at rate $O(T^{-1/2})$. For the stochastic momentum variant MB-MOMEHA it establishes the same stationarity concept at rate $O(T^{-(1/8-\delta)})$, with the envelope constraint violation driven to $O(T^{-1/16}\sqrt{\ln T})$ under an increasing penalty. The paper further claims that the stochastic result is the first momentum-based convergence proof for the Moreau-envelope Hessian-free framework, and reports that the methods outperform existing baselines on Pareto-front quality in few-shot meta-learning and neural architecture search.

Load-bearing premise

The load-bearing premise is that, for the weakly convex lower-level functions considered, the stationarity condition $\nabla_y g(x,y)=0$ pins down the lower level's true best response; a stationary point of a weakly convex function need not be a minimizer, and if that gap is wide the reformulated problem and the original bilevel problem are different problems.

Editorial extensions

If this is right

Multi-objective bilevel problems with nonconvex lower levels become tractable with single-loop, Hessian-free updates, removing the two main computational bottlenecks of prior methods.
User-specified preference vectors translate into concrete points on the Pareto front, so practitioners can trade off objectives without re-solving the entire problem.
The deterministic convergence rate $O(T^{-1/2})$ matches the single-objective Moreau-envelope Hessian-free baseline, so the multi-objective extension adds no extra convergence cost in the full-gradient setting.
In the stochastic setting, momentum-based mini-batch updates converge to the same stationarity concept, making the method applicable to data-driven tasks with noisy gradients.
The $\varepsilon_c$-$\varepsilon_s$-Pareto stationarity measure provides a well-defined stopping criterion even when iterates remain slightly infeasible with respect to the envelope constraint.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The paper leaves implicit, but important, that the equivalence between $\nabla_y g(x,y)=0$ and the true lower-level argmin is not guaranteed for weakly convex lower levels; without strong convexity, the certified stationary point may not be a lower-level global minimizer, so empirical results should be read as solving the reformulated problem rather than the original bilevel problem as stated.
The smooth Tchebycheff scalarization with finite $\mu$ only approximates the true Tchebycheff scalarization, so reported Pareto fronts may depend noticeably on the choice of $\mu$; a natural editorial extension would be to report front sensitivity to $\mu$ alongside the proposed stationarity measure.
A testable extension beyond the paper is to benchmark MOMEHA and MB-MOMEHA on synthetic nonconvex bilevel problems with known Pareto fronts, where the exact trade-off surface is available, to separate reformulation error from optimization error.
The stochastic rate $O(T^{-(1/8-\delta)})$ suggests that variance-reduced or adaptive momentum variants could push the stochastic guarantee closer to the deterministic $O(T^{-1/2})$ rate, but the paper does not claim this.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things worth knowing. The paper really does propose a new single-loop, Hessian-free algorithm for multi-objective bilevel problems with nonconvex lower-level objectives, and the deterministic convergence analysis is deep and mostly coherent. But the central claim that MOMEHA solves the original bilevel problem (1) is not supported: the Moreau-envelope reformulation replaces the lower-level argmin by the stationarity condition ∇_y g=0, which is not equivalent to global minimality under weak convexity. Theorems 1 and 2 establish convergence to a relaxed Pareto stationarity of this surrogate problem, not of (1). The stochastic variant has a second issue: the smoothed Tchebycheff gradient estimator is not unbiased, so the momentum analysis applies to an idealized estimator the algorithm does not actually use.

What is genuinely useful: this is the first method in the cited set with nonconvex lower level, single-loop structure, and no Hessian; the smooth Tchebycheff scalarization gives preference-guided Pareto exploration; and the potential-function argument with the auxiliary variable θ is intricate, with deterministic rates O(T^{-1/2}) matching single-objective MEHA. The ε_c-ε_s Pareto stationarity concept is a sensible way to handle infeasible penalty iterates, and the paper is transparent about using it.

The soft spots are not cosmetic. Section 4.1 asserts an equivalence with Theorem A.2 of Liu et al., but under ρ_y-weak convexity, ∇_y g=0 can hold at local maxima, so the feasible set of (6) strictly contains the argmin-feasible set. The stress-test note is right on this. Without an additional condition (PL inequality, convexity, or a global-minimizer characterization), the abstract overclaims. I’d ask the authors to recast the contribution as convergence for the Moreau-envelope surrogate, or supply a hypothesis that closes the equivalence gap.

The stochastic analysis has a matching hole: Assumption 4 assumes unbiased estimates of ∇F_w^(STCH), but Algorithm 2’s mini-batch ratios are biased because numerator and denominator share samples. The error recursions in Lemma 8 don’t cover the actual estimator. That is fixable with independent batches or a correction term, but as written it is a real gap.

Experiments are illustrative only: one seed, no released code, and WC-MHGD is excluded for non-convergence. Minor relative to the theory issues.

Bottom line: this deserves serious refereeing, and I’d engage with a revised version. I would not cite the current arXiv version for solving nonconvex MOBL; I might cite it for the surrogate stationarity framework once the claims are scoped properly.

Referee Report

2 major / 5 minor

Summary. The paper proposes MOMEHA and its stochastic variant MB-MOMEHA for multi-objective bilevel optimization with a nonconvex (weakly convex) lower-level problem. The methods combine a Moreau-envelope reformulation of the lower-level problem with a smooth Tchebycheff scalarization, yielding single-loop, Hessian-free, preference-guided algorithms. The main theoretical claims (Theorems 1 and 2) are non-asymptotic convergence to ε_c-ε_s-Pareto stationary points of the reformulated problem, with rates O(T^{-1/2}) in the deterministic setting and O(T^{-(1/8-δ)}) in the stochastic setting. Experiments on few-shot meta-learning and neural architecture search are reported and compared with several prior methods.

Significance. If the reformulation were equivalent to the stated bilevel problem, the results would be a substantial advance: they would remove the lower-level convexity assumption for multi-objective bilevel learning, provide the first momentum-based stochastic convergence guarantee for the Moreau-envelope Hessian-free framework, and demonstrate preference-guided Pareto front exploration. The analysis is detailed and largely self-contained, with a Lyapunov argument in the stochastic case, and the experimental comparison covers relevant benchmarks. However, the equivalence between the reformulation and the original problem (1) is not established for weakly convex lower levels, so the significance is currently limited to a stationarity-constrained surrogate problem rather than the global-minimizer bilevel problem stated in the title and abstract.

major comments (2)

[Section 4.1, Eqs. (5)-(6)] The claimed equivalence between the Moreau-envelope constrained problem (5) and the stationarity-constrained problem (6) is false for weakly convex lower-level objectives. Stationarity ∇_y g(x,y)=0 is necessary but not sufficient for y ∈ argmin_y g(x,y). A concrete counterexample is g(y) = -y^2/2 + y^4/4, which is 1-weakly convex; y=0 is a stationary point (indeed a local maximum) but the global minima are at y=±1. Since the constraint g(x,y)-v_γ(x,y)≤0 is equivalent to ∇_y g(x,y)=0 under the stated assumptions, the feasible set of (6) is strictly larger than the feasible set of (1). Consequently, the ε_c-ε_s-Pareto stationarity guarantees in Theorems 1 and 2 and Definition 6 are guarantees for the relaxed surrogate problem (16), not for the original MOBL problem (1). The abstract and Section 1 claim of solving (1) is therefore unsupported unless an additional hypothesis is imposed, such as lower-level convexity, a Polyak-Łojasiewicz condition, or another condition guaranteeing that stationarity implies global minimality.
[Section 5.1, Definition 6] The equivalence between the normal-cone formulation (14) and the multiplier formulation (15) omits the complementarity condition p·(g(x,y)-v_γ(x,y)-ε_c)=0. Without this condition, (15) can be satisfied at points strictly inside the relaxed feasible set with p>0, which is not equivalent to the normal-cone condition in (14). The convergence proofs appear to construct points on the boundary of the relaxed feasible set (where ε_c equals the actual constraint violation), so the omission is repairable, but Definition 6 as stated is not precise and should be amended.

minor comments (5)

[Throughout] There are several typographical errors, including 'satiesfies' in Definition 6, 'staionarity' in Section 4.1, 'supplemeTntary' in Section 6, and 'has been begun' in the abstract.
[Theorem 1 and Theorem 2] The step-size intervals are written as [α_x, α_x] and [α_y, α_y]; the overbars appear to be missing from the upper endpoints, making the notation ambiguous.
[Lemma 2] In the definition of L_υ and in the chain of inequalities in Eq. (23), the second term inconsistently uses L_θ in one place and L_g in another; the constants should be defined consistently.
[Definition 6] The equivalence between (14) and (15) should explicitly state that the multiplier p is nonnegative and that complementarity holds, or restrict the equivalence to boundary points of the relaxed feasible set.
[Algorithm 2] The definition of \hat{d}_{θ,t} in the algorithm box has an unbalanced parenthesis; the reader must infer the intended grouping of terms.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the convergence analysis is a self-contained descent proof, and the cited reformulation is external prior work rather than a self-referential input.

full rationale

The paper's core derivation is self-contained: Algorithms 1 and 2 are analyzed through merit-function descent lemmas (Lemmas 5 and 10) that yield bounds on the norm of the penalty gradient (Lemmas 6 and 11), and Theorems 1 and 2 then express this as the paper's epsilon_c-epsilon_s-Pareto stationarity measure from Definition 6. That measure is the standard KKT residual of the relaxed Moreau-envelope constrained problem (16); the proof chooses the Lagrange multiplier n to be the penalty term, so the stationarity bound is proportional to the penalty gradient norm, which is the natural first-order condition for the problem the algorithm actually optimizes. This is a definition of the convergence target, not a fitted parameter or a prediction derived from the same data. The load-bearing citations for the Moreau-envelope reformulation (Gao et al. 2023; Liu et al. 2024) and the smooth Tchebycheff scalarization (Lin et al. 2024) are all to external authors, so there is no self-citation chain. Whether the Moreau-envelope reformulation is truly equivalent to the original nonconvex bilevel problem is a correctness and assumption concern about an external theorem, not a circularity in this paper's own derivation chain. No step reduces by construction to its own inputs.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

The central claim rests on the Moreau-envelope reformulation equivalence, the nondegeneracy condition, and the unbiasedness of stochastic gradient estimates. The first is a domain assumption that changes the problem being solved. The last is not satisfied by the proposed plug-in estimator, creating a gap in the stochastic analysis. The algorithmic hyperparameters (mu, gamma, penalty exponent, step schedules) are chosen by hand and are not derived from first principles.

free parameters (4)

smoothing parameter mu = 4.0 in experiments
Smoothing parameter in the STCH scalarization; larger mu approximates Tchebycheff weighting. Tuned in sensitivity analysis (Section C.1).
Moreau envelope regularity gamma = 8.0 in experiments
Envelope parameter that must satisfy gamma < 1/(2 rho_y). Chosen by hand and tuned in experiments.
penalty exponent p = 1/4 (deterministic), 1/16 (stochastic)
Exponent in c_t = c0(1+t)^p, chosen to balance constraint violation and stationarity convergence rates.
step-size schedule exponents = alpha_theta,t = (1+t)^{-(3/8+delta)} etc.
Step-size decays in Theorem 2, chosen to obtain the stated stochastic convergence rates.

assumptions (4)

domain assumption Moreau-envelope reformulation equivalence (Theorem A.2 of Liu et al. [2024])
Invoked in Section 4.1 to replace the original bilevel problem with a stationarity-constrained problem. Equivalence to the original argmin problem is not established for weakly convex lower levels.
domain assumption Assumption 3: nondegenerate constraint gradient
Ensures MFCQ and a normal cone characterization; used in Definition 6 and Theorem 1.
ad hoc to paper Assumption 4: unbiased stochastic gradients of the scalarized objective
The plug-in estimator in Algorithm 2 is not unbiased for the STCH scalarization of expectations because softmax weights are stochastic. This assumption is not justified by the described algorithm.
domain assumption Smoothness and weak convexity assumptions (Assumptions 1 and 2)
Standard Lipschitz smoothness of f_i and g, and weak convexity of g in y, are assumed throughout the analysis.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Efficient Hessian-Free Methods for Multi-Objective Bilevel Optimization with Nonconvex Lower Level." pith.science (2026). https://pith.science/paper/G3LOWZQP

@misc{pith2026260812704,
  author       = {Pith},
  title        = {Pith review of: Efficient Hessian-Free Methods for Multi-Objective Bilevel Optimization with Nonconvex Lower Level},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/G3LOWZQP}},
  note         = {Machine review of arXiv:2608.12704}
}

read the original abstract

Multi-objective bilevel optimization has wide applications in the AI area such as automated learning and multi-task meta-learning. Although recently some works have been begun to study the multi-objective bilevel optimization, the proposed methods rely on the (strongly) convex lower level problems. In fact, these multi-objective bilevel learning problems are generally nonconvex, and particularly their lower level problems are nonconvex. To fill this gap, we propose a class of Multi-Objective Moreau Envelope based Hessian-free Algorithms (MOMEHA) to solve the multi-objective bilevel learning problems with nonconvex lower level. Specifically, our method uses the Moreau envelope to convert the original problem into a multi-objective single-level optimization with an envelope constraint. In particular, our method retains computational advantages of being single-loop and Hessian-free in the multi-objective setting by incorporating a smooth weighted Tchebycheff scalarization. Furthermore, we propose a momentum-based variant of MOMEHA (i.e., MB-MOMEHA) method to solve the stochastic multi-objective bilevel learning problems. In theory, we provide the convergence properties of our algorithms under both deterministic and stochastic setting. Some experiments on few-shot meta-learning and neural architecture search demonstrate that our methods outperform the existing approaches in Pareto front, validating its effectiveness and robustness.