Select-then-differentiate: Solving Bilevel Optimization with Manifold Lower-level Solution Sets

Saeed Masiha; Zebang Shen; Negar Kiyavash; Niao He

math.OCMay 9, 2026

Select-then-differentiate: Solving Bilevel Optimization with Manifold Lower-level Solution Sets

Authors: Saeed Masiha, Zebang Shen, Negar Kiyavash, Niao He

Organizations: EPFL School of Management of Technology, Station 5, 1015 Lausanne, Switzerland · ETH Department of Computer Science, Universitätstrasse 6, 8092 Zürich, Switzerland

Abstract

We study optimistic bilevel optimization when the lower-level problem has a non-isolated manifold of minimizers. In this setting, the hyper-objective may be non-differentiable because the upper-level criterion must choose among multiple lower-level solutions. Under a local Polyak--Łojasiewicz (PŁ) condition, we show that differentiability does not require the lower-level solution set to be a singleton: uniqueness of the optimistic selection is sufficient. This yields an explicit pseudoinverse-based hyper-gradient formula extending the classical singleton-minimizer result. We further characterize the regularity of the hyper-objective: non-degeneracy of the selected minimizer along the solution manifold yields local smoothness, while failure of uniqueness can create many non-differentiable points and failure of non-degeneracy can destroy all positive Hölder regularity of the hyper-gradient. Motivated by this theory, we propose HG-MS, a select-then-differentiate method combining explicit optimistic selection with efficient pseudoinverse-based hyper-gradient computation. Despite the nonconvex nature of optimistic selection over the lower-level solution manifold, we show that HG-MS converges to a stationary point of the optimistic objective with complexity governed by the intrinsic dimension of the solution manifold rather than its ambient dimension. Empirically, we test a practical variant of HG-MS for matched-budget LLM source reweighting. This variant preserves the select-then-differentiate principle and obtains the best GSM8K/MATH scores across the tested backbones, along with competitive or best MT-Bench instruction-following results.

Explore similar work

Aug 13, 2026math.OC

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

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.

Yicong Jiang, Feihu Huang

Bilevel Optimization Multi-Objective Optimization Nonconvex Condition Number

Ask PDF

Jul 11, 2026cs.LG

Sharper Analysis of Single-Loop Methods for Bilevel Optimization

Bilevel optimization underpins many machine learning applications, including hyperparameter optimization, meta-learning, neural architecture search, and reinforcement learning. While hypergradient-based methods have advanced significantly, a gap persists between theoretical guarantees and practical single-loop implementations required for efficiency. We bridge this gap by establishing sharper convergence results for single-loop approximate implicit differentiation (AID) and iterative differentiation (ITD) methods, leveraging our proposed analytical framework, decoupled norm analysis (DNA). For AID, we improve the convergence rate from

\mathcal{O}(κ^6/K)

\mathcal{O}(κ^5/K)

, where

κ

is the condition number of the inner-level problem. For ITD, we prove that the asymptotic error is

\mathcal{O}(κ^2)

, exactly matching the known lower bound and improving upon the previous

\mathcal{O}(κ^3)

guarantee. Numerical experiments on synthetic and real tasks corroborate our theoretical findings.

Yubo Zhou, Jun Shu, Luo Luo +4

Bilevel Optimization Convergence Analysis Gradient Descent Iterative Sharpness-Aware Minimization

Ask PDF

Nov 27, 2025math.OC

On the Condition Number Dependency in Bilevel Optimization

Bilevel optimization minimizes an objective function, defined by an upper-level problem whose feasible region is the solution of a lower-level problem. We study the oracle complexity of finding an

ε

-stationary point with first-order methods when the upper-level problem is nonconvex, and the lower-level problem is strongly convex. Recent works (Ji et al., ICML 2021; Arbel and Mairal, ICLR 2022; Chen et al., JMLR 2025) achieve a

\tilde{\mathcal{O}}(\bar κ_y^4 ε^{-2})

upper bound that is near-optimal in

ε

, which can be reduced to

\tilde{\mathcal{O}}(\bar κ_y^{7/2} ε^{-2})

by a naive application of Nesterov acceleration in the inner loop, where

\bar κ_y

is the global condition number. However, the optimal dependency on the condition number is unknown. In this work, we establish a new

Ω(κ_y^{5/2} ε^{-2})

lower bound, where

κ_y < \bar κ_y

is the lower-level condition number that is of the same order as

\bar κ_y

when the smoothness constants are

\mathcal{O}(1)

. Our lower bound establishes the first provable gap in terms of condition number dependency between bilevel problems and minimax problems in this setup. Our lower bounds can be extended to various settings, including high-order smooth functions, stochastic oracles, and convex hyper-objectives: (1) For second-order and arbitrarily smooth problems, we show lower bounds of

Ω({κ_y^{31/14}} ε^{-12/7})

and

Ω(κ_y^{21/10} ε^{-8/5})

, respectively. (2) For convex-strongly-convex problems, we improve the previously best lower bound (Ji and Liang, JMLR 2022) from

Ω(κ_y /\sqrtε)

Ω(κ_y^{3/2} / \sqrtε)

. (3) For smooth stochastic problems, we also show a lower bound of

Ω(κ_y^4 ε^{-4})

Lesi Chen, Jingzhao Zhang

Bilevel Optimization Convex Optimization Lower Bounds Condition Number Smoothing

Ask PDF