Newton-Based Methods for Bilevel Optimization Beyond Lower-Level Strong Convexity

Youran Dong; Junfeng Yang; Wei Yao; Jin Zhang

math.OCOct 19, 2026

Newton-Based Methods for Bilevel Optimization Beyond Lower-Level Strong Convexity

Authors: Youran Dong, Junfeng Yang, Wei Yao, Jin Zhang

Organizations: School of Mathematics, Nanjing University, Nanjing, P. R. China. · School of Artificial Intelligence, Southern University of Science and Technology, Shenzhen, P. R. China. · Department of Mathematics and National Center for Applied Mathematics Shenzhen, Southern University of Science and Technology, Shenzhen, P. R. China.

Abstract

Bilevel optimization provides a framework for machine learning tasks such as hyperparameter optimization, data reweighting, and meta-learning. Existing Newton-based bilevel methods typically rely on the classical hypergradient formula, which is generally unavailable when lower-level solutions are nonunique and the lower-level Hessian is singular. We develop two Newton-based methods beyond lower-level strong convexity by exploiting curvature shared by the lower-level and multiplier updates. Newton-based GALET handles potentially singular lower-level curvature under a positive spectral-gap condition, exploiting its range structure to avoid the squared-Hessian multiplier system used in GALET. Newton-based BAMM uses a strongly convex aggregation model when the lower-level objective is convex and the upper-level objective is strongly convex in the lower-level variable. We establish convergence guarantees and improved complexity bounds relative to GALET and sl-BAMM under the corresponding assumptions. We further introduce GNBO, a generalized Newton-based framework that captures the shared-curvature structure of the proposed methods and several existing Newton and quasi-Newton bilevel methods. Experiments on synthetic problems, data hyper-cleaning, and GPT-2 data reweighting evaluate the proposed methods across different bilevel learning tasks.

Figures & tables

Setting	Condition	Method	Gradient/JVP computations	Hessian-vector products
PL with positive spectral gap	—	GALET ( Xiao et al., 2023 )	$O(\kappa^{6}\epsilon^{-1})$	$O(\kappa^{8}\epsilon^{-1}\log(\kappa/\epsilon))$
PL with positive spectral gap	—	Newton-based GALET	$O(\kappa^{4}\epsilon^{-1})$	$O(\kappa^{5}\epsilon^{-1}\log(\kappa/\epsilon))$
$g(x,\cdot)$ convex, $f(x,\cdot)$ strongly convex	$x^{k},y^{k},u^{k}$ bounded	sl-BAMM ( Liu et al., 2023 )	$O(\epsilon^{-11/(2-6\tau)})$	$O(\epsilon^{-11/(2-6\tau)})$
	$x^{k},y^{k},u^{k}$ bounded	Newton-based BAMM	$O(\epsilon^{-4/(1-3\tau)})$	$O(\epsilon^{-(9-3\tau)/(2-6\tau)})$
	$\nabla_{2}f_{\sigma_{k}}^{*},u^{k}$ bounded	sl-BAMM ( Liu et al., 2023 )	$O(\epsilon^{-7/(2-6\tau)})$	$O(\epsilon^{-7/(2-6\tau)})$
	$\nabla_{2}f_{\sigma_{k}}^{*},u^{k}$ bounded	Newton-based BAMM	$O(\epsilon^{-3/(1-3\tau)})$	$O(\epsilon^{-(7-3\tau)/(2-6\tau)})$

Table 1: Complexity comparison with the corresponding baselines beyond LL strong convexity. For BAMM,

O(\cdot)

suppresses dependence on

\mu_{f},L_{f,1},L_{f,2},L_{g,1},L_{g,2}

Figure 1: GALET, GALET-Q, and Newton-based GALET on ( 12 ) with

\zeta=1

. Left:

\mathcal{R}_{x}

. Right:

\mathcal{R}_{y}

Figure 2: Results on ( 12 ) with

\zeta=1

. Left:

\mathcal{R}_{u}

for GALET, GALET-Q, and Newton-based GALET. Right:

\mathcal{R}_{u}

for Newton-based GALET with

T_{2}=6,11,21

Figure 3: GALET and Newton-based GALET on ( 12 ) with

\zeta=0.5,0.1

. Left:

\mathcal{R}_{x}

. Right:

\mathcal{R}_{y}

Figure 4: Newton-based BAMM and sl-BAMM on ( 13 ), with stepsizes chosen according to Case 1 of Theorem 3.2 .

Figure 5: Data hyper-cleaning with linear models. Comparison of sl-BAMM and Newton-based BAMM on MNIST (upper) and FashionMNIST (lower).

Figure 6: Data hyper-cleaning with two-layer MLPs. Comparison of GALET and Newton-based GALET on MNIST (upper) and FashionMNIST (lower).

Figure 7: Clean and corrupted data weights for ScaleBiO and Newton-based GALET, averaged over five random seeds.

Method	Clean weight	Corrupted weight	Validation loss	Test loss	Peak memory
ScaleBiO	0.928	0.072	2.603	2.555	9.984 GiB
Newton-based GALET	0.929	0.071	2.439	2.398	18.509 GiB

Table 2: GPT-2 data denoising after three training epochs, averaged over five random seeds.

Method	LL model	LL corrections	Solver / curvature	$(\delta_{y},\delta_{u})$
SHINE ( Ramzi et al., 2022 )	$g$	Multiple	Quasi-Newton, reused	$(0,0)$
qNBO ( Fang et al., 2025 )	$g$	Multiple	Separate quasi-Newton	$(0,0)$
NBO-GD ( Dong et al., 2025 )	$g$	One	$T$ GD steps, common Hessian	$(1,1)$
Newton-based GALET	$g$	One	$T_{1}/T_{2}$ GD steps, common Hessian	$(1,0)$
Newton-based BAMM	$\psi_{\sigma_{k}}$	One	$T_{k}$ GD steps, common Hessian	$(1,1)$

Table 3: Representative instances of GNBO.

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

Efficient Hessian-Free Methods for Multi-Objective Bilevel Optimization with Nonconvex Lower Level
Aug 13, 2026Yicong Jiang, Feihu HuangBilevel Optimization
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
To Solve Bilevel Optimization with Nonconvex Lower Levels, We Need Second-Order Stationarity
Sep 24, 2026Zhiyao Zhang, Menglu Yu, Alvaro Velasquez +2Bilevel Optimization Second-Order Optimization
The Ohio State University · Meta · University of Colorado Boulder +1
Select-then-differentiate: Solving Bilevel Optimization with Manifold Lower-level Solution Sets
May 9, 2026Saeed Masiha, Zebang Shen, Negar Kiyavash +1Nonconvex Optimization Bilevel Optimization
EPFL School of Management of Technology, Station 5, 1015 Lausanne, Switzerland · ETH Department of Computer Science, Universitätstrasse 6, 8092 Zürich, Switzerland

Aug 13, 2026J/K move · Enter open · S save

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

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

Open paper AskPDF arXiv

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.

Abstract

Bilevel Optimization

Explore similar work

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

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

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