Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oracles

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 $\Omega(\kappa^{3/2}\epsilon^{-2})$ oracle calls to find an $\epsilon$-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 $\Omega(\kappa^{5/2}\epsilon^{-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.

Modern AI systems often rely on “optimization,” a mathematical process for improving models and making better decisions. Some important applications, such as hyperparameter tuning, reinforcement learning, and meta-learning, involve a particularly challenging form called bilevel optimization, where one optimization problem is nested inside another. While researchers have designed many algorithms for these problems, it remains unclear how difficult they are fundamentally and whether existing methods are close to optimal. In this work, we study the theoretical limits of solving bilevel optimization problems. Instead of proposing a faster algorithm, we identify situations where any algorithm based only on first-order information, such as gradients, must take a large number of computational steps before reaching a good solution. We establish these limits both when the information is exact and when it is noisy or randomized. Our results show that bilevel optimization is inherently harder than several related optimization settings that have been studied before. These findings reveal a significant gap between what current algorithms can guarantee and the fundamental limits we prove. This suggests that there is still substantial room for improving optimization methods and for better understanding the true complexity of these widely used machine learning problems.