Research map / Learning theory and algorithms / Combinatorial and search optimization
Functionally Constrained Algorithm Solves Convex Simple Bilevel Problem
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 that absolute optimal solutions of convex simple bilevel problems are intractable for zero-respecting first-order methods, and proposes FC-BiO, a bisection-plus-subroutine method via functional-constraint reformulation that achieves near-optimal weak-solution rates in Lipschitz and smooth settings.
Problem
Convex simple bilevel optimization: minimize a convex upper-level f over the solution set of a convex lower-level problem g; find (eps_f, eps_g)-weak optimal solutions with first-order methods at near-optimal complexity.
Approach
Reformulate the simple bilevel problem as a functionally constrained problem with relaxed constraint g(x)-ĝ*≤0, then find its optimal value as the smallest root of a decreasing function ψ*(t) via bisection, solving each inner discrete minimax with subgradient or generalized accelerated gradient methods.
Key results
- Proves that any zero-respecting first-order method cannot find (eps_f,eps_g)-absolute optimal solutions: f(x_k)=f(x_0) for all k≤T while |f(x_0)-f*|≥1/48 (smooth) or ≥1/4 (Lipschitz).
- FC-BiO achieves O~(max{C_f^2/eps_f^2, C_g^2/eps_g^2}D^2) complexity for Lipschitz problems and O~(max{sqrt(L_f/eps_f), sqrt(L_g/eps_g)}D) for smooth problems, matching lower bounds up to log factors.
- In experiments FC-BiO^sm performs comparably to Bisec-BiO and outperforms a-IRG, Bi-SG, CG-BiO, AGM-BiO and PB-APG on the minimum norm problem; it converges faster on rcv1 logistic regression.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use FC-BiO with bisection and SGM for Lipschitz objectives | Simple bilevel optimization · Lipschitz simple bilevel problems | iteration complexity: \tilde \fO \left(\max\left\{\frac{C_f^2}{\epsilon_f^2},\frac{C_g^2}{\epsilon_g^2}\right\} D^2 \right), matching the lowe | Helped |
| Use FC-BiO with bisection and generalized AGM for smooth objectives | Simple bilevel optimization · Smooth simple bilevel problems | iteration complexity: \tilde \fO\left(\max\left\{\sqrt{\frac{L_f}{\epsilon_f}},\sqrt{\frac{L_g}{\epsilon_g}}\right\}D\right), matching the low | Helped |
| Use FC-BiO sm instead of existing methods | Smooth simple bilevel solvers · Minimum norm solution | convergence in upper- and lower-level objectives | Helped |
| Use FC-BiO sm instead of Bisec-BiO | Smooth simple bilevel solvers · Minimum norm solution | convergence | No clear effect |
| Use FC-BiO instead of other compared algorithms | Smooth simple bilevel solvers · Over-parameterized logistic regression on rcv1.binary | convergence in upper- and lower-level objectives | Helped |
| Seek an absolute optimal solution rather than a weak optimal solution | Zero-respecting first-order methods · Smooth simple bilevel problems | upper-level objective error: f(\vx_k)=f(\vx_0), while |f(\vx_0)-f^*|\geq \frac 1{48} | Hurt |
| Seek an absolute optimal solution rather than a weak optimal solution | Zero-respecting first-order methods · Lipschitz simple bilevel problems | upper-level objective error: f(\vx_k)=f(\vx_0), while |f(\vx_0)-f^*|\geq \frac 1{4} | Hurt |
Surprising findings
- Finding (eps_f,eps_g)-absolute optimal solutions is intractable for zero-respecting first-order methods, even though absolute optimality is achievable for constrained problems with explicit feasible sets.
- The output of FC-BiO on the minimum norm problem has f(x_hat) < f*, so it violates |f-f*|≤eps_f while still being a valid weak optimal solution.
Limitations
- An additional logarithmic factor remains compared to the lower bounds.
- The method cannot be directly applied to stochastic simple bilevel problems.
- Requires a compact convex feasible set with known diameter D.
Experimental setup
Datasets: Wikipedia Math Essential dataset rcv1.binary (LIBSVM)
Benchmarks: Wikipedia Math Essential minimum norm problem rcv1.binary over-parameterized logistic regression
Metrics: upper-level suboptimality |f(x)-f*| lower-level objective g(x) function value convergence vs. iterations
Baselines: a-IRG Bi-SG CG-BiO AGM-BiO PB-APG Bisec-BiO
Builds on: Nesterov lower bounds for zero-chain functions bisection reformulation of functionally constrained problems (Lin et al.) generalized accelerated gradient method CG-BiO
Closest papers by meaning
- An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization (NeurIPS 2024 · similarity 0.93)
- Penalty-based Methods for Simple Bilevel Optimization under Hölderian Error Bounds (NeurIPS 2024 · similarity 0.93)
- Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems (NeurIPS 2026 · similarity 0.91)
- A Single-Loop First-Order Algorithm for Linearly Constrained Bilevel Optimization (NeurIPS 2025 · similarity 0.90)
- On the Complexity of Finding Stationary Points in Nonconvex Simple Bilevel Optimization (NeurIPS 2025 · similarity 0.90)
- Conditional Gradient Methods with Standard LMO for Stochastic Simple Bilevel Optimization (NeurIPS 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.