Bilevel optimization has been widely applied in many important machine
learning applications such as hyperparameter optimization and meta-learning.
Recently, several momentum-based algorithms have been proposed to solve bilevel
optimization problems faster. However, those momentum-based algorithms do not
achieve provably better computational complexity than $\mathcal{\widetilde
O}(\epsilon^{-2})$ of the SGD-based algorithm. In this paper, we propose two
new algorithms for bilevel optimization, where the first algorithm adopts
momentum-based recursive iterations, and the second algorithm adopts recursive
gradient estimations in nested loops to decrease the variance. We show that
both algorithms achieve the complexity of $\mathcal{\widetilde
O}(\epsilon^{-1.5})$, which outperforms all existing algorithms by the order of
magnitude. Our experiments validate our theoretical results and demonstrate the
superior empirical performance of our algorithms in hyperparameter
applications.

本论文提出了两种新的双层优化算法，第一种采用基于动量的递归迭代算法，第二种采用嵌套循环中的递归梯度估计以减少方差。我们表明，两种算法都实现了 Ω（ε^ -1.5）计算量的复杂度，超越了所有现有算法一个数量级。本文的实验证明了我们算法在超参数优化应用中的优越性能。