Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems

We study a class of bilevel optimization problems in which both the upper- and lower-level problems are minimax problems. Existing studies on bilevel optimization primarily focus on settings where the lower-level problem is an unconstrained or constrained minimization problem, and are therefore not directly applicable to the setting of a minimax lower-level problem considered in this work. To address this gap, we develop penalty-based first-order methods for bilevel minimax optimization. In the deterministic setting, we prove that the proposed method finds an $\epsilon$-KKT point with $\tilde{O}(\epsilon^{-4})$ oracle complexity. We further show that bilevel optimization problems with constrained lower-level minimization can be reformulated, via Lagrangian duality under Slater's condition, as special cases of our framework and hence can also be solved by our method. This yields an $\tilde{O}(\epsilon^{-4})$ complexity bound for finding an $\epsilon$-KKT point, improving upon the existing $\tilde{O}(\epsilon^{-7})$ result. Finally, we extend our approach to the stochastic setting and establish that the proposed stochastic method finds a nearly $\epsilon$-KKT point with $\tilde{O}(\epsilon^{-9})$ oracle complexity. To the best of our knowledge, these are the first deterministic and stochastic first-order complexity results for bilevel minimax optimization.