Research map / Optimization / Nonconvex and smooth optimization
First-Order Methods for Linearly Constrained Bilevel Optimization
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.
Gives first-order (Hessian-free) algorithms with finite-time hypergradient stationarity guarantees for bilevel problems with linear equality and linear inequality lower-level constraints, plus new nonsmooth nonconvex methods with inexact oracles.
Problem
Constrained bilevel optimization with linear lower-level constraints: prior finite-time guarantees for constrained bilevel programs need Hessian computations or unverifiable assumptions on the hyperobjective.
Approach
Use a finite-difference hypergradient proxy built from perturbed lower-level problems (equality case) and a penalty reformulation with inexact hypergradient oracle (inequality case), then run projected GD or new inexact nonsmooth nonconvex methods based on online-to-nonconvex conversion.
Key results
- Equality-constrained case: epsilon-stationarity in eO(epsilon^-2) oracle calls, nearly optimal.
- Inequality-constrained case: (delta,epsilon)-Goldstein stationarity in eO(d delta^-1 epsilon^-3) calls; dimension-free eO(delta^-1 epsilon^-4) under oracle access to optimal dual variable.
- Toy experiments show the fully first-order method matches cvxpylayer convergence and is cheaper per gradient step as lower-level dimension grows.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Assume oracle access to the optimal dual variable | Proposed first-order method for linear inequality-constrained bilevel optimization · Linear inequality-constrained bilevel optimization | gradient oracle calls: eO(dδ−1ϵ−3) -> eO(δ−1ϵ−4) | Mixed |
Limitations
- Inequality-case oracle requires exact access to optimal dual variable lambda*, which is not first-order computable.
- Results restricted to linear constraints; general convex constraints left open.
- Inequality rate eO(delta^-1 eps^-4) may not be inherent; best known nonsmooth rate is eps^-3.
Experimental setup
Datasets: randomly generated synthetic bilevel QP instances
Benchmarks: synthetic constrained bilevel toy problem (Problem 6.1)
Metrics: optimality gap gradient error computation time per gradient step
Baselines: cvxpylayer
Builds on: Liu et al. first-order bilevel method Kwon et al. stochastic first-order bilevel Cutkosky-Mehta-Orabona online-to-nonconvex Zhang et al. (delta,epsilon)-stationarity
Closest papers by meaning
- Set Smoothness Unlocks Clarke Hyper-stationarity in Bilevel Optimization (NeurIPS 2025 · similarity 0.92)
- On the Complexity of Finding Stationary Points in Nonconvex Simple Bilevel Optimization (NeurIPS 2025 · similarity 0.91)
- Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems (NeurIPS 2026 · similarity 0.91)
- On The Complexity of First-Order Methods in Stochastic Bilevel Optimization (ICML 2024 · similarity 0.91)
- An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization (NeurIPS 2024 · similarity 0.90)
- On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation (ICLR 2024 · similarity 0.90)
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.