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

This paper addresses multi-objective bilevel optimization (MOBL) problems with nonconvex lower-level objectives. The problem is formulated as:

min F (x):= [fi (x, y ∗ (x))]m i=1, x∈Rdx s.t. y ∗ (x) ∈ arg min g(x, y), y∈Rdy

where m is the number of upper-level objectives, fi (x, y ∗ (x)) is the i-th upper level objective, and g(x, y) denotes the lower level objective. The authors note that this formulation is relevant in modern machine learning tasks such as federated learning with fairness and robustness trade-offs, policy alignment in reinforcement learning for LLMs, and multi-objective differentiable neural architecture search.

The paper identifies that almost all existing MOBL methods are limited by the assumption of lower-level convexity or strong convexity, which tends to fail in modern deep learning applications. Specifically:

• MOML (Ye et al. 2021) provides only asymptotic convergence guarantees

• MoCo (Fernando et al. 2022) operates with a nested structure and requires expensive Hessian-vector products

• FORUM (Ye et al. 2024) offers a Hessian-free alternative but maintains a double-loop design and assumes strong convexity on the lower level

• WC-MHGD (Zhang et al. 2026a) enables Pareto front exploration via preference vectors but still demands Hessian computations and assumes strong convexity

• WC-penalty (Zhang et al. 2026b) handles general convex lower levels but not nonconvex ones

The authors propose MOMEHA for the deterministic MOBL problem. The method:

1. Uses Moreau envelope reformulation to convert the original problem into a multi-objective single-level optimization with an envelope constraint:

min (x,y)∈Rdx×Rdy F (x, y) s.t. g(x, y) − υγ (x, y) ≤ 0

2. Incorporates smooth weighted Tchebycheff scalarization (STCH) to enable Pareto front exploration via preference vectors:

Fw(STCH) (x, y) = (1/µ) log(Σm i=1 exp(µwi (fi (x, y) − zi)))

3. Employs a single-loop, Hessian-free alternating gradient descent strategy with updates for θ (auxiliary variable), x (upper-level variable), and y (lower-level variable)

4. Introduces a relaxed constraint εc-εs-Pareto stationarity concept to handle the infeasibility-induced stationarity difficulty when porting the penalty-based framework to the multi-objective case

The authors propose MB-MOMEHA for the stochastic MOBL problem:

min F (x):= Eξ∼Di [fi (x, y ∗ (x); ξ)] m i=1, s.t. y ∗ (x) ∈ arg min Eϱ∼Dg [g(x, y; ϱ)]

This variant:

• Replaces all deterministic gradients with mini-batch stochastic estimates

• Uses Polyak-style momentum updates for θ, x, and y

• Provides the first convergence proof for the Moreau envelope Hessian-free framework in stochastic gradients with momentum

The paper introduces εc-εs-Pareto Stationarity (Definition 6): A point (x, y) in the εc-relaxed feasible region Fc:= (x, y) g(x, y) − υγ (x, y) ≤ εc reaches εc-εs-Pareto Stationarity if there exist λ ∈ ∆m−1 and n ∈ NFc (x, y) such that:

∥Σm i=1 λi ∇fi (x, y) + n∥ ≤ εs

Under MFCQ, this is equivalent to: there exist λ ∈ ∆m−1 and a multiplier p ≥ 0 such that:

∥Σm i=1 λi ∇fi (x, y) + p (∇g(x, y) − ∇υγ (x, y))∥ ≤ εs

Under Assumptions 1, 2, and 3 (properness, smoothness, and nondegenerate constraint gradient), with γ ∈ (0, 2ρ1y), ct = c0:

min 0≤t≤T Hct (xt+1, yt+1; C) = O(T −1/2)

i.e., O(1)-O(T −1/2)-stationarity in the best case.

Furthermore, if Pct (xt, yt) is upper-bounded and ct = c0(1 + t)1/4:

εT:= g(xT, yT) − υγ (xT, yT) = O(T −1/4)

min 0≤t≤T Hct (xt+1, yt+1; εT+1) = O(T −1/4)

i.e., O(T −1/4)-O(T −1/4)-stationarity in the best case.

The paper notes: "In the deterministic full-gradient setting, MOMEHA recovers the same convergence rate as its single objective counterpart–Single-loop Moreau Envelope based Hessianfree Algorithm (MEHA), indicating that the multi-objective extension incurs no loss in convergence speed."

Under Assumptions 1, 2, 3, and 4 (adding bounded variance), with γ ∈ (0, 2ρ1y), ct = c0, δ ∈ (0, 1/8), and appropriate step sizes:

min 0≤t≤T E [Hct (xt+1, yt+1; C′)] = O(T −(1/8−δ))

i.e., O(1)-O(T −(1/8−δ))-stationarity in the best case.

Furthermore, if E[Pct (xt, yt)] is upper-bounded and ct = c0(1 + t)1/16, αθ,t = αθ,0(1 + t)−3/8:

ε′T:= E [g(xT, yT) − υγ (xT, yT)] = O(T −1/16)

min 0≤t≤T E [Hct (xt+1, yt+1; ε′T+1)] = O(T −1/16 √ln T)

i.e., O(T −1/16)-O(T −1/16√ln T)-stationarity in the best case.

The paper explains: "The joint rate O(T −1/16)-O(T −1/16√ln T) reflects the fact that driving the lower-level stationarity toward zero comes at the expense of Pareto stationarity convergence. Concretely, if the lower-level stationarity is only required to reach a neighborhood, the Pareto stationarity measure alone can be driven to zero at the faster rate of O(T −(1/8−δ))."

1. Assumption 1 (UL Properness): Upper-level objectives fi(x, y) are proper; Fw(STCH)(x, y) is bounded below

2. Assumption 2 (Smoothness): fi(x, y) and g(x, y) have Lipschitz continuous gradients; g(x, y) is (ρx, ρy)-weakly convex

3. Assumption 3 (Nondegenerate Constraint Gradient): ∇g(x, y) − ∇υγ (x, y) ≠ 0 for points with 0 < g(x, y) − υγ (x, y) ≤ εU

4. Assumption 4 (Stochastic): Unbiased stochastic gradients with bounded variance σ2

• Conducted on FC-100 and Caltech-256 datasets with 4-domain 5-way 5-shot protocol

• MOMEHA achieves broader coverage of the performance space on Domains 1, 2, and 4

• On Domain 3, WC-penalty yields marginally better front, while both outperform remaining baselines

• Hypervolume comparison: Ours (1.127) > WC-penalty (1.092) > MOML (1.072) > FORUM (1.013)

• WC-MHGD was excluded due to failure to converge

• Conducted on CIFAR-10 with 4 objectives: validation loss, FLOPS loss, skip connection density, and pooling density

• MB-MOMEHA achieves superior performance in both quality and coverage of Pareto fronts

• Hypervolume comparison (2-task): Ours (1.522) > WC-MHGD (1.323) > WC-penalty (1.216) > MoCo (1.192)

The paper's main contributions are:

1. Proposing MOMEHA for MOBL with nonconvex lower levels using Moreau envelope and STCH scalarization

2. Proposing MB-MOMEHA for stochastic settings with momentum

3. Establishing εc-εs-Pareto stationarity convergence guarantees for both deterministic and stochastic variants

4. Demonstrating empirical superiority over existing baselines on few-shot meta-learning and neural architecture search

The authors state: Our methods consistently outperform existing baselines on few-shot meta-learning and neural architecture search, demonstrating the applicability of our methods to the MOBL problems with lower-level nonconvexity.

Based on this paper, I can make the following specific improvements to AI systems:

Improvement: Replace existing bilevel optimization components that assume convex lower-level objectives with the Moreau envelope-based Hessian-free approach (MOMEHA).

Capability: AI systems can now handle multi-objective problems where the inner optimization landscape is nonconvex—common in deep learning—without requiring expensive Hessian computations or convexity guarantees. This enables training on complex, realistic objectives where previous methods would fail or diverge.

Improvement: Integrate the smooth weighted Tchebycheff scalarization (STCH) into the optimization loop to enable systematic exploration of the Pareto front via user-specified preference vectors.

Capability: AI systems can now generate diverse trade-off solutions (e.g., balancing fairness vs. accuracy, or model complexity vs. performance) in a single training run, rather than requiring separate optimizations per trade-off point. This is particularly useful for federated learning with fairness constraints or LLM alignment with multiple safety/quality criteria.

Improvement: Adopt the MB-MOMEHA variant for stochastic settings, which uses momentum-based updates and avoids second-order derivatives.

Capability: AI systems can train on large-scale, noisy data (e.g., mini-batch gradient descent) for multi-objective bilevel problems—such as neural architecture search or meta-learning—while maintaining convergence guarantees. The momentum mechanism accelerates convergence without the computational overhead of Hessian-vector products, making it scalable to high-dimensional models.

Improvement: Implement the εc-εs-Pareto stationarity criterion to define practical stopping conditions that tolerate small constraint violations and stationarity errors.

Capability: AI systems can now determine when training has converged in multi-objective settings even when the lower-level problem is only approximately solved. This provides a principled early-stopping mechanism, reducing wasted computation while ensuring the final solution is near-optimal in the Pareto sense.

Improvement: Use the Moreau envelope reformulation with a relaxed constraint (εc) to handle intermediate iterates that may temporarily violate the lower-level optimality constraint.

Capability: AI systems can now train stably even when the inner problem is not perfectly solved at each step—a common issue in practice. This prevents oscillation or divergence during training and allows for more aggressive step sizes, improving overall convergence speed.

Improvement: Apply the proposed methods to multi-task neural architecture search with objectives like validation loss, FLOPS, and architectural complexity.

Capability: AI systems can automatically discover architectures that achieve better hypervolume (i.e., more comprehensive Pareto coverage) compared to existing methods, as demonstrated (1.522 vs. 1.323 for the best baseline). This leads to more efficient and better-performing models across multiple competing criteria simultaneously.

Improvement: Use the multi-objective formulation to explicitly optimize for both global accuracy and per-client fairness in federated settings.

Capability: AI systems can now train models that balance performance across heterogeneous clients (e.g., different devices or user groups) without requiring convexity of the local training objectives. This enables more equitable AI deployment in real-world distributed systems.

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.