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 Lipschitz continuous conditions of stochastic oracles, 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
(multi-task SBO) by processing a constant number of lower problems at each
iteration, and establish its sample complexity no worse than $O(m/\epsilon^3)$,
which could be a better complexity than that of simply processing all $m$ lower
problems at each iteration. Lastly, we establish even faster convergence
results for gradient-dominant functions. To the best of our knowledge, this is
the first work considering multi-task SBO and developing state-of-the-art
sample complexity results.

本文提出了快速随机化算法来解决非凸随机双层优化问题，在 Lipschitz 连续条件下建立了单一下层问题和具有 $m>1$ 个下层问题（多任务 SBO）的非凸 SBO 的样本复杂度，以及在梯度主导函数下的更快收敛结果。