Improved KKT Complexity for First-Order Bilevel Optimization under Weak Lower-Level Convexity
Abstract
We study deterministic first-order bilevel optimization under weak lower-level convexity, allowing nonconvex lower-level objectives and without assuming strong convexity, the Polyak-Łojasiewicz condition, or an error-bound property. We consider a δ-relaxed Moreau-gap constraint, with δ>0, for the lower-level stationarity condition and propose an inexact variable-smoothing penalty method (IVSP) for computing its approximate Karush-Kuhn-Tucker (KKT) points. For any fixed relaxation level δ, under a standard extended no-nonzero-abnormal-multiplier constraint qualification (ENNAMCQ), we prove finite stabilization of the adaptive penalty parameter and an overall Õ(ε−3) first-order complexity for computing an ε-KKT point. Notably, we give verifiable sufficient conditions for ENNAMCQ covering convex lower-level objectives without nonconstant affine segments (including the strictly convex case), and a class of nonconvex sample-reweighting models. The positive relaxation avoids the intrinsic constraint-qualification degeneracy of the exact Moreau-gap constraint while achieving an 𝒪(√δ) lower-level near-stationarity guarantee. Numerical experiments on synthetic and real-world bilevel learning problems illustrate the practical performance of IVSP.
Related
- Newton-Based Methods for Bilevel Optimization Beyond Lower-Level Strong Convexity
- Decision-focused predictions via pessimistic bilevel optimization: complexity and algorithms
- Stochastic Nonconvex Bilevel Optimization: Improved Rates Without Rare-Visit Assumption
- An Ω(κy8ε−6) Lower Bound for Stochastic NC-SC Bilevel Optimization with First-order Oracles
- Accelerating Finite-Sum Bilevel Optimization with Fully First-Order Oracles
BibTeX
@misc{alcantara2026improved,
title = {{Improved KKT Complexity for First-Order Bilevel Optimization under Weak Lower-Level Convexity}},
author = {Jan Harold Alcantara and Masahiro Inoue and Akiko Takeda},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.39736},
eprint = {2609.39736},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.39736},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Improved KKT Complexity for First-Order Bilevel Optimization under Weak Lower-Level Convexity
AU - Jan Harold Alcantara
AU - Masahiro Inoue
AU - Akiko Takeda
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.39736
UR - https://arxiv.org/abs/2609.39736
AB - We study deterministic first-order bilevel optimization under weak lower-level convexity, allowing nonconvex lower-level objectives and without assuming strong convexity, the Polyak-Łojasiewicz condition, or an error-bound property. We consider a δ-relaxed Moreau-gap constraint, with δ>0, for the lower-level stationarity condition and propose an inexact variable-smoothing penalty method (IVSP) for computing its approximate Karush-Kuhn-Tucker (KKT) points. For any fixed relaxation level δ, under a standard extended no-nonzero-abnormal-multiplier constraint qualification (ENNAMCQ), we prove finite stabilization of the adaptive penalty parameter and an overall Õ(ε^−3) first-order complexity for computing an ε-KKT point. Notably, we give verifiable sufficient conditions for ENNAMCQ covering convex lower-level objectives without nonconstant affine segments (including the strictly convex case), and a class of nonconvex sample-reweighting models. The positive relaxation avoids the intrinsic constraint-qualification degeneracy of the exact Moreau-gap constraint while achieving an 𝒪(√δ) lower-level near-stationarity guarantee. Numerical experiments on synthetic and real-world bilevel learning problems illustrate the practical performance of IVSP.
ER -