AI RESEARCH
SPABA: A Single-Loop and Probabilistic Stochastic Bilevel Algorithm Achieving Optimal Sample Complexity
arXiv CS.LG
•
ArXi:2405.18777v2 Announce Type: replace-cross 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, 2021) to the bilevel setting, can achieve optimal sample complexity in both the finite-sum and expectation settings.