On the Condition Number Dependency in Bilevel Optimization

Bilevel optimization minimizes an objective function, defined by an upper-level problem whose feasible region is the solution of a lower-level problem. We study the oracle complexity of finding an ε-stationary point with first-order methods when the upper-level problem is nonconvex, and the lower-level problem is strongly convex. Recent works achieve a tildeO(bar kappay7/2 ε-2) upper bound that is near-optimal in ε. In this work, we establish a new Omega(kappay5/2 ε-2) lower bound, where kappay ≤ bar kappay is the lower-level condition number. Our lower bound establishes the first provable gap in terms of condition number dependency between bilevel problems and minimax problems in this setup, and textitis tight up to logarithmic factors when the lower-level function is quadratic. Our lower bounds can be extended to various settings. (1) For second-order and arbitrarily smooth problems, we show lower bounds of Omega(kappay9/4 ε-7/4) and Omega(kappay13/6 ε-5/3), respectively. (2) For convex--strongly-convex problems, we improve the previously best lower bound (Ji and Liang, JMLR 2022) from Omega(kappay /√ε) to Omega(kappay3/2 / √ε). (3) For stochastic nonconvex--strongly-convex problems, we also show the lower bounds of Omega(kappay4 ε-4) and Omega(kappay9/2 ε-4) for stochastic Hessian-vector-product and stochastic first-order methods, respectively.