# Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel Optimization. (arXiv:2105.02266v1 [math.OC])

In this paper, we consider non-convex stochastic bilevel optimization (SBO)
problems that have many applications in machine learning. Although numerous
studies have proposed stochastic algorithms for solving these problems, they
are limited in two perspectives: (i) their sample complexities are high, which
do not match the state-of-the-art result for non-convex stochastic
optimization; (ii) their algorithms are tailored to problems with only one
lower-level problem. When there are many lower-level problems, it could be
prohibitive to process all these lower-level problems at each iteration. To
address these limitations, this paper proposes fast randomized stochastic
algorithms for non-convex SBO problems. First, we present a stochastic method
for non-convex SBO with only one lower problem and establish its sample
complexity of $O(1/epsilon^3)$ for finding an $epsilon$-stationary point
under appropriate conditions, matching the lower bound for stochastic smooth
non-convex optimization. Second, we present a randomized stochastic method for
non-convex SBO with $m>1$ lower level problems by processing only one lower
problem at each iteration, and establish its sample complexity no worse than
$O(m/epsilon^3)$, which could have a better complexity than simply processing
all $m$ lower problems at each iteration. To the best of our knowledge, this is
the first work considering SBO with many lower level problems and establishing
state-of-the-art sample complexity.