Research map / Optimization / Nonconvex and smooth optimization
On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation
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.
Studies penalty-method landscape for nonconvex, constrained bilevel optimization under a proximal error-bound condition, showing O(sigma)-closeness of penalty and hyper-objective, and proposes double-loop and single-loop first-order stochastic algorithms with O(eps^-3)/O(eps^-7)/O(eps^-5) oracle complexities.
Problem
Finding stationary points of bilevel optimization problems with smooth, possibly nonconvex and constrained lower-level problems, where implicit gradient methods do not apply.
Approach
Connects the penalty function and hyper-objective via a proximal error-bound condition, deriving an explicit gradient formula for the hyper-objective with multiple lower-level solutions, and optimizes the penalty formulation as a saddle-point problem with decreasing penalty parameter and Moreau-envelope smoothing, including a momentum-assisted fully single-loop variant.
Key results
- Penalty function and hyper-objective values are O(sigma)-close and gradients O(sigma/mu^3)-close under proximal error-bound assumptions.
- Deterministic oracle complexity O(eps^-3); fully stochastic O(eps^-7) for double-loop and O(eps^-5) for single-loop with momentum.
- Explicit gradient formula for the hyper-objective when the lower-level problem has multiple solutions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use gradually decreasing penalty parameters instead of setting the penalty to O(\epsilon) from the first iteration | Double-loop penalty algorithm · Bilevel optimization, stochastic oracles | oracle complexity: O(\epsilon^{-8}) -> O(\epsilon^{-7}) | Helped |
| Add momentum-assisted gradient estimators and use a fully single-loop implementation | Bilevel penalty algorithm · Bilevel optimization, fully stochastic oracles | sample complexity: O(\epsilon^{-7}) -> O(\epsilon^{-5}) | Helped |
| Add momentum-assisted gradient estimators and use a fully single-loop implementation | Bilevel penalty algorithm · Bilevel optimization, only upper-level stochastic oracles | sample complexity: O(\epsilon^{-5}) -> O(\epsilon^{-4}) | Helped |
| Add momentum-assisted gradient estimators and use a fully single-loop implementation | Bilevel penalty algorithm · Bilevel optimization, deterministic oracles | sample complexity: O(\epsilon^{-3}) -> O(\epsilon^{-3}) | No clear effect |
| Use a fully single-loop method instead of the double-loop method | Bilevel penalty algorithm · Bilevel optimization, fully stochastic oracles | sample complexity: O(\epsilon^{-7}) -> O(\epsilon^{-5}) | Helped |
Limitations
- Requires proximal error-bound and Lipschitz solution-set assumptions that may not hold in general
- Lower-level constraints independent of x; x-dependent constraints not handled
- Complexity not shown to be tight with stochastic oracles and constraints
Experimental setup
Metrics: oracle complexity stationarity measure
Builds on: Moreau envelope implicit gradient descent penalty methods for bilevel optimization
Closest papers by meaning
- Penalty-based Methods for Simple Bilevel Optimization under Hölderian Error Bounds (NeurIPS 2024 · similarity 0.94)
- Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems (NeurIPS 2026 · similarity 0.93)
- Stochastic Dynamic Barrier Perturbed Gradient Methods for Nonconvex Simple Bilevel Optimization (NeurIPS 2026 · similarity 0.92)
- An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization (NeurIPS 2024 · similarity 0.92)
- 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.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.