Superquantile-Gibbs Relaxation for Minima-selection in Bilevel Optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908884420001792 |
|---|---|
| author | Masiha, Saeed Shen, Zebang Kiyavash, Negar He, Niao |
| author_facet | Masiha, Saeed Shen, Zebang Kiyavash, Negar He, Niao |
| contents | 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 $(ε,ρ)$-Goldstein stationary point of $F_{\max}$ with at most $\mathcal{O}(m^{8k+11}ε^{-2}(ερ)^{-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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_05991 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Superquantile-Gibbs Relaxation for Minima-selection in Bilevel Optimization Masiha, Saeed Shen, Zebang Kiyavash, Negar He, Niao Optimization and Control 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 $(ε,ρ)$-Goldstein stationary point of $F_{\max}$ with at most $\mathcal{O}(m^{8k+11}ε^{-2}(ερ)^{-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. |
| title | Superquantile-Gibbs Relaxation for Minima-selection in Bilevel Optimization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2505.05991 |