Research map / Optimization / Nonconvex and smooth optimization
Penalty-based Methods for Simple Bilevel Optimization under Hölderian Error Bounds
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 a penalty reformulation of simple bilevel optimization (minimize convex F over argmin of convex G) under a Hölderian error bound, and penalty-based accelerated proximal gradient methods with non-asymptotic complexity guarantees.
Problem
Simple bilevel optimization: minimizing a convex upper-level objective over the solution set of a convex lower-level problem. Existing methods are asymptotic, slow sublinear, or need strong assumptions.
Approach
Penalize the lower-level residual G(x)-G* with weight gamma and relate approximate solutions of the penalized problem to (eps_F, eps_G)-optimal solutions of the original problem under an alpha-Hölderian error bound; then solve the penalized problem with (adaptive) accelerated proximal gradient, obtaining complexity matching unconstrained composite optimization when alpha=1.
Key results
- PB-APG and PB-APG-sc converge faster than MNG, BiG-SAM, DBGD, a-IRG, CG-BiO, Bi-SG and R-APM on LRP and LSRP for both lower- and upper-level objectives.
- Theoretical complexity of O(sqrt(1/eps^max{alpha,beta})) iterations for an (eps, eps^beta)-optimal solution when both objectives are composite convex; linear rate when F is strongly convex and alpha=1, beta<=1.
- Adaptive aPB-APG and aPB-APG-sc achieve faster convergence than their primal counterparts in the experiments.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PB-APG, aPB-APG, PB-APG-sc, or aPB-APG-sc instead of the compared methods | LRP · LRP | convergence speed | Helped |
| Use PB-APG or PB-APG-sc instead of R-APM | LRP · LRP | lower-level objective residual | Helped |
| Add adaptive penalty updates and warm-start (ablation) | PB-APG and PB-APG-sc · LRP | convergence speed | Helped |
| Use PB-APG, aPB-APG, PB-APG-sc, or aPB-APG-sc instead of the compared methods | LSRP · LSRP | convergence speed | Helped |
| Add adaptive penalty updates and warm-start (ablation) | PB-APG and PB-APG-sc · LSRP | convergence stability | Helped |
Surprising findings
- The proposed methods reach higher upper-level objective values than some baselines, because they achieve much higher lower-level accuracy and thus larger feasible sets.
Limitations
- Results for nonconvex upper-level objective only cover global solutions and approximate local solutions with weaker guarantees.
- Requires Hölderian error bound and prox-friendly assumptions on the penalized nonsmooth part.
- Non-smooth case complexity (subgradient method) is weaker and experiments only cover smooth-composite instances.
Experimental setup
Benchmarks: logistic regression problem (LRP) least squares regression problem (LSRP)
Metrics: lower-level residual G(x)-G* upper-level objective F(x) running time
Baselines: MNG BiG-SAM DBGD a-IRG CG-BiO Bi-SG R-APM
Builds on: Shen and Chen 2023 penalty framework Tseng accelerated proximal gradient Lin and Xiao 2014 APG strongly convex Samadi et al. 2023 R-APM Beck 2017 subgradient method
Closest papers by meaning
- An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization (NeurIPS 2024 · similarity 0.95)
- On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation (ICLR 2024 · similarity 0.94)
- Functionally Constrained Algorithm Solves Convex Simple Bilevel Problem (NeurIPS 2024 · similarity 0.93)
- Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems (NeurIPS 2026 · similarity 0.93)
- Conditional Gradient Methods with Standard LMO for Stochastic Simple Bilevel Optimization (NeurIPS 2025 · similarity 0.92)
- A Single-Loop First-Order Algorithm for Linearly Constrained Bilevel Optimization (NeurIPS 2025 · similarity 0.91)
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.