揭示非凸-强凸双层优化的理论下界，指出现有算法仍有改进空间。
Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oracles
- 构造难例推导出确定性与随机情形下的新下界。
- 确定性下界为 Ω(κ^{3/2}ε^{-2})，随机下界为 Ω(κ^{5/2}ε^{-4})。
- 揭示当前上界与下界间巨大差距，启发后续研究。
尽管双层优化的上界已有广泛研究，但受限于其结构复杂性，下界进展有限。本文聚焦光滑非凸-强凸情形，构建新的难例，在确定性和随机一阶黑盒模型下给出非平凡的下界。在确定性情况下，证明任意一阶零尊重算法至少需要 Ω(κ^{3/2}ε^{-2}) 次查询才能找到 ε-精度驻点，优于单层非凸优化及非凸-强凸极小极大问题的已知最优下界。在随机情况下，证明至少需要 Ω(κ^{5/2}ε^{-4}) 次随机查询，同样强化了相关设置下的最佳已知下界。结果揭示当前上界与下界之间存在显著差距，表明即使在二次低层目标等简化情形下，也需进一步研究以厘清标准一阶黑盒下的最优复杂度。
原文摘要 · Abstract (English)
Although upper bound guarantees for bilevel optimization have been widely studied, progress on lower bounds has been limited due to the complexity of the bilevel structure. In this work, we focus on the smooth nonconvex-strongly-convex setting and develop new hard instances that yield nontrivial lower bounds under deterministic and stochastic first-order oracle models. In the deterministic case, we prove that any first-order zero-respecting algorithm requires at least $Ω(κ^{3/2}ε^{-2})$ oracle calls to find an $ε$-accurate stationary point, improving the optimal lower bounds known for single-level nonconvex optimization and for nonconvex-strongly-convex min-max problems. In the stochastic case, we show that at least $Ω(κ^{5/2}ε^{-4})$ stochastic oracle calls are necessary, again strengthening the best known bounds in related settings. Our results expose substantial gaps between current upper and lower bounds for bilevel optimization and suggest that even simplified regimes, such as those with quadratic lower-level objectives, warrant further investigation toward understanding the optimal complexity of bilevel optimization under standard first-order oracles.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。