Superquantile-Gibbs Relaxation for Minima-selection in Bilevel Optimization

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 Fmax requires minima selection over the lower-level solution set; and (2) Fmax 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 PLcirc. Unlike the global PL condition often assumed in BLO, the PL inequality in PLcirc 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 Fmax 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(ε),ρ)-Goldstein stationarity condition for Fmax in expectation. In the small-accuracy regime, suppressing logarithmic and fixed-problem factors, it uses at most widetildemathcal O(m15+12kε-2(ερ)-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 Fmax 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.