提出新方法解决上下层均为极小极大问题的双层优化，无需强凸性假设。
Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems
- 用惩罚函数将极小极大下层问题转为可解形式，设计一阶迭代算法。
- 确定性下达到ε-KKT点需$ ilde{O}(ε^{-4})$次梯度调用，优于已有结果。
- 适用于无强凸性、含约束或随机梯度场景，适合优化理论研究者。
我们研究一类双层优化问题，其上下层均具有极小极大结构，涵盖众多新兴应用。尽管双层优化和极小极大优化已有大量研究，现有方法多集中于下层为最小化问题的情形，通常依赖强凸性假设，难以直接应用于本文所考虑的极小极大下层设置。为填补此空白，我们提出了无需强凸性假设的基于惩罚的一阶方法。在确定性设定下，该方法以$ ilde{O}(ε^{-4})$的预言机复杂度找到ε-KKT点。我们进一步证明，含凸约束的下层最小化问题可通过拉格朗日对偶性纳入本框架，从而获得优于现有$ ilde{O}(ε^{-7})$的$ ilde{O}(ε^{-4})$复杂度。最后，我们将方法拓展至仅可用随机梯度预言机的随机设定，证明该随机方法可在$ ilde{O}(ε^{-9})$复杂度下找到近似ε-KKT点。
原文摘要 · Abstract (English)
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 $\tilde{O}(ε^{-4})$ 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 $\tilde{O}(ε^{-4})$ complexity bound that improves upon the existing $\tilde{O}(ε^{-7})$ 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 $\tilde{O}(ε^{-9})$ oracle complexity.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。