Preprint
Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems
ArXiv.org
Cornell University
05/08/2026
DOI: 10.48550/arxiv.2605.08006
Abstract
We study a class of bilevel optimization problems in which both the upper- and lower-level problems have minimax structures. This setting captures a broad range of emerging applications. Despite the extensive literature on bilevel optimization and minimax optimization separately, existing methods mainly focus on bilevel optimization with lower-level minimization problems, often under strong convexity assumptions, and are not directly applicable to the minimax lower-level setting considered here. To address this gap, we develop penalty-based first-order methods for bilevel minimax optimization without requiring strong convexity of the lower-level problem. In the deterministic setting, we establish that the proposed method finds anε -KKT point withÕ(ε⁻⁴)oracle complexity. We further show that bilevel problems with convex constrained lower-level minimization can be reformulated as special cases of our framework via Lagrangian duality, leading to anÕ(ε⁻⁴)complexity bound that improves upon the existingÕ(ε⁻⁷)result. Finally, we extend our approach to the stochastic setting, where only stochastic gradient oracles are available, and prove that the proposed stochastic method finds a nearlyε -KKT point withÕ(ε⁻⁹)oracle complexity.
Details
- Title: Subtitle
- Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems
- Creators
- Yiyang ShenYutian HeWeiran WangQihang Lin
- Resource Type
- Preprint
- Publication Details
- ArXiv.org
- DOI
- 10.48550/arxiv.2605.08006
- ISSN
- 2331-8422
- Publisher
- Cornell University; Ithaca, New York
- Language
- English
- Date posted
- 05/08/2026
- Academic Unit
- Computer Science; Business Analytics
- Record Identifier
- 9985163710602771
Metrics
1 Record Views