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, for which we provide the first-known complexity bounds without
the gradient boundedness assumption (which was made in existing analyses) under
the two aforementioned geometries. We also provide significantly tighter upper
bounds than the existing complexity when the bounded gradient assumption does
hold. We show that AccBiO achieves the optimal results (i.e., the upper and
lower bounds match up to logarithmic factors) when the inner-level problem
takes a quadratic form with a constant-level condition number. 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.

该论文从两个方面揭示双层优化的收敛率：提出首个双层加速优化器 AccBiO 并给出无梯度边界假设的复杂度上限，同时得出更紧的下限。此外，论文还证明在某些情况下，双层优化比极大极小问题更具有挑战性。关键词包括双层优化、收敛率、下限复杂度、AccBiO 和二次型条件数。