Research map / Optimization / Nonconvex and smooth optimization

Select-then-differentiate: Solving Bilevel Optimization with Manifold Lower-level Solution Sets

NeurIPS 2026 · Optimization › Nonconvex and smooth optimization · approach: Penalty and implicit-gradient bilevel methods · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows the optimistic bilevel hyper-objective is C^1 with a pseudoinverse hyper-gradient when the optimistic selection over a manifold of lower-level minimizers is unique (smooth if non-degenerate), and proposes HG-MS, a Best-of-N select-then-differentiate method with convergence guarantees and LLM source-reweighting experiments.

Problem

Optimistic bilevel optimization where the lower-level problem has a non-isolated manifold of minimizers, so the hyper-objective may be nondifferentiable due to the upper-level minima selection among multiple lower-level solutions.

Approach

Under a local PL-circle condition, uniqueness of the optimistic selection (rather than singleton lower-level solution sets) suffices for C^1 differentiability of the hyper-objective with a pseudoinverse hyper-gradient; HG-MS selects the candidate with best upper-level value from Gibbs/ULA samples near the solution manifold and then differentiates at that point.

Key results

• HG-MS obtains 74.85 GSM8K / 30.86 MATH on Llama-3-8B, 82.03 / 38.98 on Qwen-2-7B, and 80.86 / 38.48 on Gemma-2-9B, the best in every column of the ten-source math table.
• On Qwen2.5-32B, HG-MS reaches 92.58% GSM8K and 53.32% MATH, improving over ScaleBiO by 4.18 and 2.03 points.
• HG-MS achieves the best MT-Bench score on Qwen-2-7B (6.92) and Gemma-2-9B (8.30), while ScaleBiO is best on Llama-3-8B (7.36 vs 7.33).

Surprising findings

• On the multilingual controlled task, HG-MS gives the best validation and test losses even though its learned mixture is not closest to the nominal source ratio (ScaleBiO is).
• Uniqueness of the optimistic minimizer alone does not yield Hölder continuity of the hyper-gradient; non-degeneracy must be intrinsic to the restricted objective on the solution manifold.

Limitations

• Oracle-complexity exponent is very conservative and the analyzed ULA/Gibbs variant is not a practical runtime model.
• Practical LLM experiments use finite-budget optimizer branches instead of true Gibbs sampling, so theory does not directly cover the experiments.
• Theory requires uniqueness and intrinsic non-degeneracy of the optimistic minimizer; failure of these yields non-differentiability or lack of Hölder continuity.

Experimental setup

Datasets: GSM8K training portfolio MATH training portfolio ScaleBiO eighteen-source instruction portfolio Alpaca Alpaca-GPT4-ZH Alpaca-GPT4-EN MNIST

Benchmarks: GSM8K MATH MT-Bench MNIST hyper-cleaning Alpaca two-source GPT-2 reweighting

Metrics: accuracy MT-Bench score validation loss test loss source-weight recovery error

Baselines: HG-baseline ScaleBiO LESS RHO-LOSS Uniform Weighting

Builds on: ScaleBiO LESS RHO-LOSS implicit differentiation PL-circle condition

Closest papers by meaning

• An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization (NeurIPS 2024 · similarity 0.91)
• On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation (ICLR 2024 · similarity 0.90)
• Set Smoothness Unlocks Clarke Hyper-stationarity in Bilevel Optimization (NeurIPS 2025 · similarity 0.90)
• Conditional Gradient Methods with Standard LMO for Stochastic Simple Bilevel Optimization (NeurIPS 2025 · similarity 0.90)
• Penalty-based Methods for Simple Bilevel Optimization under Hölderian Error Bounds (NeurIPS 2024 · similarity 0.90)
• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling (NeurIPS 2024 · similarity 0.90)