Superquantile-Gibbs Relaxation for Minima-selection in Bilevel Optimization

Bilevel optimization (BLO) becomes fundamentally more challenging when the lower-level objective admits multiple minimizers. Beyond the unique-minimizer setting, two difficulties arise: (1) evaluating the hyper-objective $F_{\max }$ requires minima selection, i.e., optimizing over a potentially topologically disconnected set; (2) $F_{\max }$ can be discontinuous without structural assumptions. We show both can be circumvented under a local Polyak–Lojasiewicz (PL) condition (PL${}^{\circ }$) on the lower-level objective. Under PL${}^{\circ }$, $F_{\max }$ is Lipschitz continuous and, for every upper-level variable, the set of lower-level minimizers is topologically connected and a closed embedded submanifold of common intrinsic dimension $k$. This intrinsic dimension $k$, rather than the ambient one, governs BLO complexity. We give a method that finds an $(\epsilon ,\rho )$-Goldstein stationary point of $F_{\max }$ with at most $\mathcal{O}(m^{8k+11}{\epsilon }^{-2}(\epsilon \rho {)}^{-8k-10})$ gradient-oracle queries, where $m$ is the upper-level dimension. The key is a Superquantile–Gibbs relaxation that turns minima selection into a sampling problem solvable via Langevin dynamics. To our knowledge, this is the first work to rigorously treat minima selection in BLO and quantify how its complexity scales with the intrinsic dimensionality of the lower-level problem.