Bilevel Gradient Methods and the Morse Parametric Qualification Condition

We introduce the Morse parametric qualification condition for bilevel programming. Generic semialgebraic functions are Morse parametric in a piecewise sense. Thus, bilevel programs with a Morse parametric lower level constitute a relevant intermediate class between strongly convex and fully generic lower levels. In this framework, we study bilevel gradient algorithms with two strategies: the single-step multistep strategy, which involves a sequence of steps on the lower-level problems followed by one step on the upper-level problem, and a differentiable programming strategy that optimizes a smooth approximation of the bilevel problem. Although the first is shown to be a biased gradient method on the problem with rich properties, the second, which is inspired by metalearning applications, is less stable but offers simplicity and ease of implementation.

Funding: This research was supported by the Agence Nationale de la Recherche [Grants ANR-19-PI3A-0004 and ANR-23-CE23-0012-01]. J. Bolte, Q.-T. Le, and E. Pauwels thank the AI Interdisciplinary Institute [ANITI funding], the Agence Nationale de la Recherche [France 2030 Program Grant ANR-23-IACL-0002], the Chair TRIAL, and the Air Force Office of Scientific Research [Grant FA8655-22-1-7012]. J. Bolte, E. Pauwels, and S. Vaiter acknowledge support from the ANR MAD. J. Bolte and E. Pauwels acknowledge support from the Agence Nationale de la Recherche [Grant ANR-17-EURE-0010]. Q.-T. Le is supported by the Agence Nationale de la Recherche [Grant ANR-23-IACL-0006]. E. Pauwels acknowledges support from the IUF. S. Vaiter thanks the Agence Nationale de la Recherche [Grant ANR-23-PEIA-0004] and the Chair 3IA BOGL [Grant ANR-23-IACL-0001].