Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oracles
This work addresses a fundamental gap in theoretical understanding for researchers in optimization and machine learning, providing new lower bounds that highlight the inherent complexity of bilevel optimization, even in simplified regimes.
The paper tackles the problem of establishing lower complexity bounds for bilevel optimization in the smooth nonconvex-strongly-convex setting, proving that any first-order algorithm requires at least Ω(κ^{3/2}ε^{-2}) deterministic oracle calls and Ω(κ^{5/2}ε^{-4}) stochastic oracle calls to find an ε-accurate stationary point, improving upon known bounds for related problems.
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.