Research map / Optimization / Nonconvex and smooth optimization
An Accelerated Gradient Method for Convex Smooth Simple 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.
Proposes AGM-BiO, an accelerated projected-gradient method for convex smooth simple bilevel problems that replaces the lower-level solution set with a cutting-plane halfspace approximation, achieving improved suboptimality/infeasibility complexity bounds.
Problem
Simple bilevel optimization: minimize a convex smooth upper-level objective f over the (non-singleton) solution set of a convex smooth lower-level problem g, with convergence measured by suboptimality and infeasibility.
Approach
Approximate the lower-level solution set by a halfspace cutting plane (intersected with the constraint set) built from the gradient of g at an auxiliary point, using a sequence of lower-level values g_k that converge to g*, and run Nesterov-style accelerated projected gradient on f over this surrogate set; a Hölderian error bound on g yields faster rates and absolute suboptimality guarantees.
Key results
- Under compact feasible set, AGM-BiO achieves O(max{1/sqrt(eps_f), 1/eps_g}) iterations, improving over CG-BiO's O(max{1/eps_f, 1/eps_g}).
- With r=1 Hölderian error bound on g, AGM-BiO attains absolute-optimal complexity Õ(max{eps_f^-0.5, eps_g^-0.5}), matching R-APM's weak-sharpness rate and single-level optimal rate.
- For general r>1 Hölderian error bound, complexity Õ(max{eps_f^{-(2r-1)/(2r)}, eps_g^{-(2r-1)/(2r)}}), avoiding PB-APG's O(eps_f^{-0.5r}) term.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use AGM-BiO instead of CG-BiO | Simple bilevel optimization with a compact feasible set · Simple bilevel optimization, compact feasible set | iteration complexity: \mathcal{O}(\max\{1/\epsilon_f,1/\epsilon_g\}) -> \mathcal{O}(\max\{1/\sqrt{\epsilon_f},1/\epsilon_{g}\}) | Helped |
| Assume a first-order Hölderian error bound | AGM-BiO · Simple bilevel optimization with first-order Hölderian error bound | iteration complexity for infeasibility: \mathcal{O}(1/\epsilon_{g}) -> \tilde{\mathcal{O}}(1/\epsilon_{g}^{0.5}) | Helped |
| Assume an r-th order Hölderian error bound | AGM-BiO · Simple bilevel optimization with r-th order Hölderian error bound | iteration complexity: \mathcal{O}(\epsilon_f^{-0.5r})+\mathcal{O}(\epsilon_g^{-0.5}) -> \tilde{\mathcal{O}}(\max\{\epsilon_{f}^{-\frac{2r-1}{2 | Helped |
| Use AGM-BiO instead of R-APM and PB-APG | Over-parameterized regression · Wikipedia Math Essential over-parameterized regression | absolute suboptimality | Helped |
| Use AGM-BiO instead of other evaluated methods | Linear inverse problem · Linear inverse problem, n=100 | absolute suboptimality | Helped |
| Use AGM-BiO instead of other evaluated methods | Linear inverse problem · Linear inverse problem, n=3 | absolute suboptimality | Mixed |
| Use AGM-BiO instead of R-APM and PB-APG | Over-parameterized regression · Wikipedia Math Essential over-parameterized regression | infeasibility | No clear effect |
| Use a fixed regularization or penalty parameter instead of AGM-BiO's dynamic framework | R-APM and PB-APG · Linear inverse problem | infeasibility | Hurt |
Surprising findings
- Absolute suboptimality |f(x)-f*| cannot be bounded by any first-order method without additional assumptions, per a lower-bound result cited from prior work.
Limitations
- Analysis is for the smooth setting; composite/non-smooth extension is only sketched in the appendix under extra assumptions.
- Infeasibility bound is O(1/k) in the worst case without Hölderian error bound, requiring compact feasible set for that rate.
- Requires a sequence g_k computed from an auxiliary accelerated method on g or fixed horizon K for log-free bounds.
Experimental setup
Datasets: Wikipedia Math Essential dataset synthetic linear inverse problem
Benchmarks: Wikipedia Math Essential (over-parameterized regression) linear inverse problem
Metrics: suboptimality gap infeasibility gap absolute suboptimality runtime iteration count
Baselines: a-IRG Bi-SG SEA CG-BiO R-APM PB-APG Bisec-BiO
Builds on: FISTA / Nesterov accelerated gradient CG-BiO R-APM Bisec-BiO
Closest papers by meaning
- Penalty-based Methods for Simple Bilevel Optimization under Hölderian Error Bounds (NeurIPS 2024 · similarity 0.95)
- Functionally Constrained Algorithm Solves Convex Simple Bilevel Problem (NeurIPS 2024 · similarity 0.93)
- Conditional Gradient Methods with Standard LMO for Stochastic Simple Bilevel Optimization (NeurIPS 2025 · similarity 0.93)
- A Single-Loop First-Order Algorithm for Linearly Constrained Bilevel Optimization (NeurIPS 2025 · similarity 0.92)
- Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems (NeurIPS 2026 · similarity 0.92)
- On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation (ICLR 2024 · similarity 0.92)
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.