Research map / Optimization / Nonconvex and smooth optimization
Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems
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 penalty-based first-order methods for bilevel problems whose upper and lower levels are minimax, achieving O~(eps^-4) deterministic and O~(eps^-9) stochastic complexity for eps-KKT points, and improves constrained-lower-level bilevel complexity from O~(eps^-7) to O~(eps^-4) via Lagrangian duality.
Problem
Bilevel optimization where the lower-level problem is itself a (convex-concave) minimax problem, possibly with constraints, lacking strong convexity; existing penalty methods do not apply.
Approach
Value-function penalty reformulation of bilevel minimax problems into a single NCC minimax problem solved by an inexact proximal point method with an optimal SCSC inner solver; constrained lower levels are reformulated as minimax via Lagrangian duality with a box-bounded dual variable, removing the inner penalty parameter.
Key results
- Deterministic method finds an O(eps)-KKT point with O~(eps^-4) oracle complexity, improving the prior O~(eps^-7) for constrained lower levels.
- On Waterbirds (no l2 penalty), worst-group accuracy 86.9% vs 76.9% for DRO; on CelebA (lambda=0), 75.0% vs 41.1%.
- Stochastic variant finds a nearly eps-KKT point with O~(eps^-9) stochastic oracle complexity.
Surprising findings
- On CelebA with no l2 penalty, average accuracy of the proposed method (93.9%) is lower than DRO (94.7%), trading average for worst-group accuracy.
Limitations
- Requires compact feasible domains.
- epsilon-KKT point defined in a lifted space with auxiliary variables z1, z2.
- Stochastic O~(eps^-9) complexity is high; variance reduction left to future work.
Experimental setup
Datasets: CelebA Waterbirds synthetic constrained bilevel linear instances
Benchmarks: CelebA Waterbirds constrained bilevel linear optimization instances
Metrics: objective value log10 lower optimality gap log10 infeasibility worst-group accuracy average accuracy
Baselines: FOP SMO DRO
Builds on: penalty-based bilevel methods OptFOM optimal primal-dual method SAPD / SAPD+ Group DRO
Closest papers by meaning
- Penalty-based Methods for Simple Bilevel Optimization under Hölderian Error Bounds (NeurIPS 2024 · similarity 0.93)
- On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation (ICLR 2024 · similarity 0.93)
- On The Complexity of First-Order Methods in Stochastic Bilevel Optimization (ICML 2024 · similarity 0.93)
- An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization (NeurIPS 2024 · similarity 0.92)
- First-Order Methods for Linearly Constrained Bilevel Optimization (NeurIPS 2024 · similarity 0.91)
- 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.