  Bilevel optimization recently has attracted increased interest in machine
learning due to its many applications such as hyper-parameter optimization and
meta learning. Although many bilevel methods recently have been proposed, these
methods do not consider using adaptive learning rates. It is well known that
adaptive learning rates can accelerate optimization algorithms. To fill this
gap, in the paper, we propose a novel fast adaptive bilevel framework to solve
stochastic bilevel optimization problems that the outer problem is possibly
nonconvex and the inner problem is strongly convex. Our framework uses unified
adaptive matrices including many types of adaptive learning rates, and can
flexibly use the momentum and variance reduced techniques. In particular, we
provide a useful convergence analysis framework for the bilevel optimization.
Specifically, we propose a fast single-loop adaptive bilevel optimization
(BiAdam) algorithm, which achieves a sample complexity of
$\tilde{O}(\epsilon^{-4})$ for finding an $\epsilon$-stationary solution.
Meanwhile, we propose an accelerated version of BiAdam algorithm (VR-BiAdam),
which reaches the best known sample complexity of $\tilde{O}(\epsilon^{-3})$.
To the best of our knowledge, we first study the adaptive bilevel optimization
methods with adaptive learning rates. Experimental results on data
hyper-cleaning and hyper-representation learning tasks demonstrate the
efficiency of our algorithms.
