# SPABA: A Single-Loop and Probabilistic Stochastic Bilevel Algorithm Achieving Optimal Sample Complexity

arXiv: https://arxiv.org/abs/2405.18777 · HTML: https://mlsanity.com/paper/2405.18777/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 May 2024.

## Built on by (most cited first, 6 of 6)

- [Efficient Curvature-Aware Hypergradient Approximation for Bilevel Optimization](https://mlsanity.com/paper/2505.02101/) (2025)
- [On the Condition Number Dependency in Bilevel Optimization](https://mlsanity.com/paper/2511.22331/) (2025)
- [A Fully First-Order Layer for Differentiable Optimization](https://mlsanity.com/paper/2512.02494/) (2025)
- [A Provably Convergent Plug-and-Play Framework for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2505.01258/) (2025)
- [BROS: Bias-Corrected Randomized Subspaces for Memory-Efficient Single-Loop Bilevel Optimization](https://mlsanity.com/paper/2605.10288/) (2026)
- [Federated stochastic bilevel optimization with fully first-order gradients](https://mlsanity.com/paper/2609.16350/) (2026)

## Abstract (arXiv)

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.