Lower Bounds and Accelerated Algorithms for Bilevel Optimization

Bilevel optimization has recently attracted growing interests due to its wide applications in modern machine learning problems. Although recent studies have characterized the convergence rate for several such popular algorithms, it is still unclear how much further these convergence rates can be improved. In this paper, we address this fundamental question from two perspectives. First, we provide the first-known lower complexity bounds of $\widetilde{\Omega}(\frac{1}{\sqrt{\mu_x}\mu_y})$ and $\widetilde \Omega\big(\frac{1}{\sqrt{\epsilon}}\min\{\frac{1}{\mu_y},\frac{1}{\sqrt{\epsilon^{3}}}\}\big)$ respectively for strongly-convex-strongly-convex and convex-strongly-convex bilevel optimizations. Second, we propose an accelerated bilevel optimizer named AccBiO, whose complexity improves the existing upper bounds orderwisely under strongly-convex-strongly-convex, convex-strongly-convex and nonconvex-strongly-convex geometries. We further show that AccBiO achieves the optimal results (i.e., the upper and lower bounds match) under certain conditions up to logarithmic factors. Interestingly, our lower bounds under both geometries are larger than the corresponding optimal complexities of minimax optimization, establishing that bilevel optimization is provably more challenging than minimax optimization. We finally discuss the extensions and applications of our results to other problems such as minimax optimization.