cs.LGSep 24, 2026

To Solve Bilevel Optimization with Nonconvex Lower Levels, We Need Second-Order Stationarity

Authors: Zhiyao Zhang, Menglu Yu, Alvaro Velasquez, Nathaniel D. Bastian, Jia Liu

Organizations: The Ohio State University · Meta · University of Colorado Boulder · Johns Hopkins University

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Although bilevel optimization (BLO) has emerged as a powerful framework for addressing many complex and nested machine learning problems in recent years, most existing studies are confined to the lower-level strongly convex (LLSC) or lower-level generally convex (LLGC) settings (i.e., the lower-level objective function is assumed to be, at least, convex). While the LLSC/LLGC assumptions render more tractable algorithmic design and theoretical analysis, they are too rigid to encompass many machine learning problems in practice. The limitations of LLSC/LLGC assumptions in BLO motivate us to investigate solving the BLO problem in the general lower-level nonconvex (LLNC) settings, which remains in its infancy. In the literature on LLNC-BLO, most of the existing works either require additional structures in the lower-level objective function for tractable theoretical analysis, or adopt the first-order stationarity reformulation as a lower-level surrogate problem, which is inherited from the LLSC/LLGC settings but could lose their effectiveness in the LLNC setting. To bridge this gap, we propose to reformulate the nonconvex lower-level problem using a second-order stationarity-based surrogate, the solution of which guarantees a local optimal solution at the lower level. Based on this reformulation, we propose the PROBE (Perturbed gradient algorithm for bilevel problem) and show that it overcomes the limitations of prior works by probing and escaping lower-level saddle points. We prove that PROBE achieves a finite-time convergence rate of O(T−2/5)O(T^{-2/5}), where T denotes iterations. To our knowledge, this work is the first to establish the finite-time convergence for achieving lower-level second-order stationary solutions in general LLNC-BLO. Our experiments on both a large language model-based data curation task and a meta-learning task also show that PROBE outperforms SOTA methods.

Figures & tables

Figure 1: Example: x,y∈Rx,y\in\mathbb{R} , f(x,y)=(x−2)2+y2f(x,y)=(x-2)^{2}+y^{2} , g(x,y)=14y4−12xy2g(x,y)=\frac{1}{4}y^{4}-\frac{1}{2}xy^{2} . Fig. 1(a) shows the contour plot of f(x,y)f(x,y) along with converging trajectories with initial points (0,2)(0,2) and (3,0)(3,0) , and Fig. 1(b) plots ∣f(xt,yt)−f∗∣|f(x_{t},y_{t})-f^{*}| vs. iteration tt , illustrating how far the convergent sequences are from solving the LLNC-BLO problem. Our PROBE \mathsf{PROBE}~ (Alg. 1 ) is the only method that escapes the saddle point and finds true solutions , compared to existing baselines methods: PBGD ( Shen and Chen, 2023 ) , GALET ( Xiao et al., 2023 ) , MEHA ( Liu et al., 2024 ) , and SUN-DSBO-SE ( Ma et al., 2026 ) .
AlgorithmBLO Setting †Surrogate Problem ‡Escape Saddle Points
PBGDLLNCFirst-order stationarity✗
GALETLLNCFirst-order stationarity✗
MEHALLNCMoreau envelope✗
SUN-DSBO-SELLNCMoreau envelope✗
PROBE \mathsf{PROBE}~ (Ours)LLNCSecond-order stationarity✓
Table 1: Comparison of PROBE \mathsf{PROBE}~ (Alg. 1 ) with state-of-the-art LLNC-BLO methods. †\dagger : BLO Setting states the assumptions on the lower level of the LLNC-BLO. ‡\ddagger : Surrogate Problem refers to the relaxed surrogate of the lower level of the LLNC-BLO problem. Moreau envelope-based surrogates reduce to first-order stationarity under smoothness conditions ( Ma et al., 2026 ) .
Figure 2: Baseline comparison.
Figure 3: Hyperparameter investigation.
Figure 4: Ablation Study.
Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 5: Baseline comparison in meta-learning task.
Figure 6: Baseline (lower-level) comparison.
TrajectoryCandidatesStrictNon-strictUndetermined
18800
2201901
37700
4111001
5181701
Total646103
Appendix
Table 2: Numerical classification of the perturbation-triggered lower-level stationary-point candidates encountered along five PROBE \mathsf{PROBE}~ trajectories. Undetermined refers to candidates that could not be classified conclusively because of numerical instability.
More in this topic

Bilevel Optimization

Bilevel optimization studies problems where one set of decisions is optimized in response to the solution of another, nested problem.

See all 86 papers

Explore similar work

CardsList
May 9, 2026

A Tale of Two Problems: Multi-Task Bilevel Learning Meets Equality Constrained Multi-Objective Optimization

In recent years, bilevel optimization (BLO) has attracted significant attention for its broad applications in machine learning. However, most existing works on BLO remain confined to the single-task setting and rely on the lower-level strong convexity assumption, which significantly restricts their applicability to modern machine learning problems of growing complexity. In this paper, we make the first attempt to extend BLO to the multi-task setting under a relaxed lower-level general convexity (LLGC) assumption. To this end, we reformulate the multi-task bilevel learning (MTBL) problem with LLGC into an equality constrained multi-objective optimization (ECMO) problem. However, ECMO itself is a new problem that has not yet been studied in the literature. To address this gap, we first establish a new Karush-Kuhn-Tucker (KKT)-based Pareto stationarity as the convergence criterion for ECMO algorithm design. Based on this foundation, we propose a weighted Chebyshev (WC)-penalty algorithm that achieves a finite-time convergence rate of O(ST^{-\frac{1}{2}) to KKT-based Pareto stationarity in both deterministic and stochastic settings, where SS denotes the number of objectives, and TT is the total iterations. Moreover, by varying the preference vector over the SS-dimensional simplex, our WC-penalty method systematically explores the Pareto front. Finally, solutions to the ECMO problem translate directly into solutions for the original MTBL problem, thereby closing the loop between these two foundational optimization frameworks.

Zhiyao Zhang, Myeung Suk Oh, Zhen Qin +3

Department of Electrical and Computer Engineering, The Ohio State University, Columbus, OH, USA · Meta Platforms, Inc., Menlo Park, CA, USA.

Bilevel OptimizationMulti-Task OptimizationMulti-Objective Optimization
AskPDF
Aug 13, 2026

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) for the multi-objective bilevel learning problems with nonconvex lower level. Specifically, our method uses the Moreau envelope to relax 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 for 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

College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, China · College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, China; and also with MIIT Key Laboratory of Pattern Analysis and Machine Intelligence, Nanjing, China

Bilevel Optimization
AskPDF
Nov 27, 2025

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 O~(κˉy4ε−2)\tilde{\mathcal{O}}(\bar κ_y^4 ε^{-2}) upper bound that is near-optimal in εε, which can be reduced to O~(κˉy7/2ε−2)\tilde{\mathcal{O}}(\bar κ_y^{7/2} ε^{-2}) by a naive application of Nesterov acceleration in the inner loop, where κˉy\bar κ_y is the global condition number. However, the optimal dependency on the condition number is unknown. In this work, we establish a new Ω(κy5/2ε−2)Ω(κ_y^{5/2} ε^{-2}) lower bound, where κy<κˉyκ_y < \bar κ_y is the lower-level condition number that is of the same order as κˉy\bar κ_y when the smoothness constants are O(1)\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 Ω(κy31/14ε−12/7)Ω({κ_y^{31/14}} ε^{-12/7}) and Ω(κy21/10ε−8/5)Ω(κ_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/ε)Ω(κ_y /\sqrtε) to Ω(κy3/2/ε)Ω(κ_y^{3/2} / \sqrtε). (3) For smooth stochastic problems, we also show a lower bound of Ω(κy4ε−4)Ω(κ_y^4 ε^{-4}).

Lesi Chen, Jingzhao Zhang

IIIS, Tsinghua University

Oracle ComplexityNonconvex OptimizationBilevel Optimization
AskPDF