On the Convergence Theory for Hessian-Free Bilevel Algorithms
  Bilevel optimization has arisen as a powerful tool in modern machine
learning. However, due to the nested structure of bilevel optimization, even
gradient-based methods require second-order derivative approximations via
Jacobian- or/and Hessian-vector computations, which can be costly and
unscalable in practice. Recently, Hessian-free bilevel schemes have been
proposed to resolve this issue, where the general idea is to use zeroth- or
first-order methods to approximate the full hypergradient of the bilevel
problem. However, we empirically observe that such approximation can lead to
large variance and unstable training, but estimating only the response Jacobian
matrix as a partial component of the hypergradient turns out to be extremely
effective. To this end, we propose a new Hessian-free method, which adopts the
zeroth-order-like method to approximate the response Jacobian matrix via taking
difference between two optimization paths. Theoretically, we provide the
convergence rate analysis for the proposed algorithms, where our key challenge
is to characterize the approximation and smoothness properties of the
trajectory-dependent estimator, which can be of independent interest. This is
the first known convergence rate result for this type of Hessian-free bilevel
algorithms. Experimentally, we demonstrate that the proposed algorithms
outperform baseline bilevel optimizers on various bilevel problems.
Particularly, in our experiment on few-shot meta-learning with ResNet-12
network over the miniImageNet dataset, we show that our algorithm outperforms
baseline meta-learning algorithms, while other baseline bilevel optimizers do
not solve such meta-learning problems within a comparable time frame.
