Newton-Based Methods for Bilevel Optimization Beyond Lower-Level Strong Convexity
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.
Related
- Improved KKT Complexity for First-Order Bilevel Optimization under Weak Lower-Level Convexity
- Efficient Hessian-Free Methods for Multi-Objective Bilevel Optimization with Nonconvex Lower Level
- Proximal Limited-Memory Quasi-Newton Methods for Nonsmooth Nonconvex Optimization
- Weak Convexity and Proximal Bundle Methods for Nonsmooth Policy Optimization in Robust Control
- Beyond Polytopes: Damped Newton Frank--Wolfe Methods over Compact Convex Sets
BibTeX
@misc{dong2026newtonbased,
title = {{Newton-Based Methods for Bilevel Optimization Beyond Lower-Level Strong Convexity}},
author = {Youran Dong and Junfeng Yang and Wei Yao and Jin Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.26839},
eprint = {2610.26839},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.26839},
}
RIS
TY - UNPB
TI - Newton-Based Methods for Bilevel Optimization Beyond Lower-Level Strong Convexity
AU - Youran Dong
AU - Junfeng Yang
AU - Wei Yao
AU - Jin Zhang
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.26839
UR - https://arxiv.org/abs/2610.26839
AB - 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.
ER -