Bilevel optimization has arisen as a powerful tool for many machine learning
problems such as meta-learning, hyperparameter optimization, and reinforcement
learning. In this paper, we investigate the nonconvex-strongly-convex bilevel
optimization problem. For deterministic bilevel optimization, we provide a
comprehensive convergence rate analysis for two popular algorithms respectively
based on approximate implicit differentiation (AID) and iterative
differentiation (ITD). For the AID-based method, we orderwisely improve the
previous convergence rate analysis due to a more practical parameter selection
as well as a warm start strategy, and for the ITD-based method we establish the
first theoretical convergence rate. Our analysis also provides a quantitative
comparison between ITD and AID based approaches. For stochastic bilevel
optimization, we propose a novel algorithm named stocBiO, which features a
sample-efficient hypergradient estimator using efficient Jacobian- and
Hessian-vector product computations. We provide the convergence rate guarantee
for stocBiO, and show that stocBiO outperforms the best known computational
complexities orderwisely with respect to the condition number $\kappa$ and the
target accuracy $\epsilon$. We further validate our theoretical results and
demonstrate the efficiency of bilevel optimization algorithms by the
experiments on meta-learning and hyperparameter optimization.

本文研究非凸强凸双层优化问题，提供了两种基于近似隐式导数和迭代导数的算法以及一种名为 stocBiO 的新型算法，并对它们进行了收敛性分析和比较，实验表明这些优化算法在元学习、超参数优化等方面表现出良好效果。