  We present in this paper novel accelerated fully first-order methods in
\emph{Bilevel Optimization} (BLO). Firstly, for BLO under the assumption that
the lower-level functions admit the typical strong convexity assumption, the
\emph{(Perturbed) Restarted Accelerated Fully First-order methods for Bilevel
Approximation} (\texttt{PRAF${}^2$BA}) algorithm leveraging \emph{fully}
first-order oracles is proposed, whereas the algorithm for finding approximate
first-order and second-order stationary points with state-of-the-art oracle
query complexities in solving complex optimization tasks. Secondly, applying as
a special case of BLO the \emph{nonconvex-strongly-convex} (NCSC) minimax
optimization, \texttt{PRAF${}^2$BA} rediscovers \emph{perturbed restarted
accelerated gradient descent ascent} (\texttt{PRAGDA}) that achieves the
state-of-the-art complexity for finding approximate second-order stationary
points. Additionally, we investigate the challenge of finding stationary points
of the hyper-objective function in BLO when lower-level functions lack the
typical strong convexity assumption, where we identify several regularity
conditions of the lower-level problems that ensure tractability and present
hardness results indicating the intractability of BLO for general convex
lower-level functions. Under these regularity conditions we propose the
\emph{Inexact Gradient-Free Method} (\texttt{IGFM}), utilizing the
\emph{Switching Gradient Method} (\texttt{SGM}) as an efficient sub-routine to
find an approximate stationary point of the hyper-objective in polynomial time.
Empirical studies for real-world problems are provided to further validate the
outperformance of our proposed algorithms.
