On the Condition Number Dependency in Bilevel Optimization

The paper presents new lower bounds on the oracle complexity for finding $\epsilon$-stationary points in bilevel optimization, particularly when the upper-level problem is nonconvex and the lower-level problem is strongly convex. It establishes a lower bound of $\Omega(\kappa_y^{5/2} \epsilon^{-2})$, which highlights a significant gap in condition number dependency between bilevel and minimax problems, and extends results to various settings including high-order smooth functions and stochastic oracles. This work is crucial for practitioners as it provides deeper insights into the complexity landscape of bilevel optimization, potentially guiding the design of more efficient algorithms in real-world applications.