  In the paper, we propose a class of efficient adaptive bilevel methods based
on mirror descent for nonconvex bilevel optimization, where its upper-level
problem is nonconvex possibly with nonsmooth regularization, and its
lower-level problem is also nonconvex while satisfies Polyak-{\L}ojasiewicz
(PL) condition. To solve these deterministic bilevel problems, we present an
efficient adaptive projection-aid gradient (i.e., AdaPAG) method based on
mirror descent, and prove that it obtains the best known gradient complexity of
$O(\epsilon^{-1})$ for finding an $\epsilon$-stationary solution of nonconvex
bilevel problems. To solve these stochastic bilevel problems, we propose an
efficient adaptive stochastic projection-aid gradient (i.e., AdaVSPAG) methods
based on mirror descent and variance-reduced techniques, and prove that it
obtains the best known gradient complexity of $O(\epsilon^{-3/2})$ for finding
an $\epsilon$-stationary solution. Since the PL condition relaxes the strongly
convex, our algorithms can be used to nonconvex strongly-convex bilevel
optimization. Theoretically, we provide a useful convergence analysis framework
for our methods under some mild conditions, and prove that our methods have a
fast convergence rate of $O(\frac{1}{T})$, where $T$ denotes the number of
iterations.
