While stochastic bilevel optimization methods have been extensively studied
for addressing large-scale nested optimization problems in machine learning, it
remains an open question whether the optimal complexity bounds for solving
bilevel optimization are the same as those in single-level optimization. Our
main result resolves this question: SPABA, an adaptation of the PAGE method for
nonconvex optimization in (Li et al., 2021) to the bilevel setting, can achieve
optimal sample complexity in both the finite-sum and expectation settings. We
show the optimality of SPABA by proving that there is no gap in complexity
analysis between stochastic bilevel and single-level optimization when
implementing PAGE. Notably, as indicated by the results of (Dagr\'eou et al.,
2022), there might exist a gap in complexity analysis when implementing other
stochastic gradient estimators, like SGD and SAGA. In addition to SPABA, we
propose several other single-loop stochastic bilevel algorithms, that either
match or improve the state-of-the-art sample complexity results, leveraging our
convergence rate and complexity analysis. Numerical experiments demonstrate the
superior practical performance of the proposed methods.

我们的主要结果解决了一个开放问题：在机器学习中解决双层优化问题时，通过对非凸优化的一个适应性方法进行改进，SPABA 在有限和期望设置下都能达到最优样本复杂度，并证明了随机双层优化和单层优化在复杂度分析上不存在差距。此外，我们还提出了几种其他的单环随机双层算法，它们要么与最新的样本复杂度结果相匹配，要么超过其性能，利用了我们的收敛速率和复杂度分析。数值实验证明了所提方法的卓越实际性能。