Bilevel optimization, with broad applications in machine learning, has an
intricate hierarchical structure. Gradient-based methods have emerged as a
common approach to large-scale bilevel problems. However, the computation of
the hyper-gradient, which involves a Hessian inverse vector product, confines
the efficiency and is regarded as a bottleneck. To circumvent the inverse, we
construct a sequence of low-dimensional approximate Krylov subspaces with the
aid of the Lanczos process. As a result, the constructed subspace is able to
dynamically and incrementally approximate the Hessian inverse vector product
with less effort and thus leads to a favorable estimate of the hyper-gradient.
Moreover, we propose a~provable subspace-based framework for bilevel problems
where one central step is to solve a small-size tridiagonal linear system. To
the best of our knowledge, this is the first time that subspace techniques are
incorporated into bilevel optimization. This successful trial not only enjoys
$\mathcal{O}(\epsilon^{-1})$ convergence rate but also demonstrates efficiency
in a synthetic problem and two deep learning tasks.

通过 Lanczos 方法构建低维近似 Krylov 子空间，解决偏导数求逆问题，提高双层优化问题的效率，并在合成问题和深度学习任务中展示了收敛速度和效率。