Improved KKT Complexity for First-Order Bilevel Optimization under Weak Lower-Level Convexity

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 $\delta$-relaxed Moreau-gap constraint, with $\delta >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 $\delta$, under a standard extended no-nonzero-abnormal-multiplier constraint qualification (ENNAMCQ), we prove finite stabilization of the adaptive penalty parameter and an overall $\tilde{O}({\epsilon }^{-3})$ first-order complexity for computing an $\epsilon$-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 $\mathcal{O}(\sqrt{\delta })$ lower-level near-stationarity guarantee. Numerical experiments on synthetic and real-world bilevel learning problems illustrate the practical performance of IVSP.