pipette
ENEnglish

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

Jan Harold Alcantara, Masahiro Inoue, Akiko Takeda

Preprint

En palabras de los autores

We study deterministic first-order bilevel optimization under weak lower-level convexity, allowing nonconvex lower-level objectives and without assuming strong convexity, the Polyak-{\L}ojasiewicz condition, or an error-bound property. We consider a -relaxed Moreau-gap constraint, with , 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 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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: jueves, 1 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 42 pages, 3 figures