Superquantile-Gibbs Relaxation for Minima-selection in Bilevel Optimization

Abstract

Bilevel optimization (BLO) becomes more challenging when the lower-level objective admits multiple minimizers. Compared with the commonly studied unique-minimizer setting, this introduces two difficulties: (1) evaluating the hyper-objective $F_{\max }$ requires minima selection over the lower-level solution set; and (2) $F_{\max }$ may be discontinuous without additional structure. We address both issues under a parameter-uniform local Polyak-Lojasiewicz (PL) condition on the lower-level objective, denoted by ${\mathrm{PL}}^{\circ }$. Unlike the global PL condition often assumed in BLO, the PL inequality in ${\mathrm{PL}}^{\circ }$ is imposed only near the local minima. This formulation accommodates bounded, non-singleton minimizer sets and is motivated by hyperparameter tuning in over-parameterized learning. We show that $F_{\max }$ is Lipschitz continuous and that the lower-level minimizer sets are connected, compact, embedded submanifolds with a common intrinsic dimension $k$. This intrinsic dimension determines the explicit accuracy exponents in our complexity bound. We propose a randomized method whose output satisfies an $(\mathcal{O}(\epsilon ),\rho )$-Goldstein stationarity condition for $F_{\max }$ in expectation. In the small-accuracy regime, suppressing logarithmic and fixed-problem factors, it uses at most $\tilde{\mathcal{O}}(m^{15+12k}{\epsilon }^{-2}(\epsilon \rho {)}^{-12k-14})$ queries to the gradient oracle of the lower-level objective, where $m$ is the upper-level dimension. Its key ingredient is a Superquantile-Gibbs relaxation that provides an approximate function-evaluation oracle for $F_{\max }$ and turns minima selection into a sampling problem addressed by standard Langevin dynamics. To our knowledge, this is the first rigorous treatment of minima selection in BLO that explicitly relates overall complexity to the lower-level intrinsic dimension.