Research map / Optimization / Nonconvex and smooth optimization
SPABA: A Single-Loop and Probabilistic Stochastic Bilevel Algorithm Achieving Optimal Sample Complexity
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes SPABA, a single-loop bilevel algorithm adapting PAGE (plus MA-SABA and SRMBA variants) that matches single-level optimal sample complexity under finite-sum and expectation settings.
Problem
Stochastic nonconvex-strongly-convex bilevel optimization: whether optimal single-level sample complexities (O(eps^-1.5) expectation, O(sqrt(n) eps^-1) finite-sum) can be attained by fully single-loop methods under standard smoothness.
Approach
Adapt the PAGE probabilistic gradient estimator to all three directions of the decoupled hypergradient framework (DecBO), with a single loop and a momentum-equipped UL update analysis that avoids high-order smoothness; also introduce MA-SABA (SAGA + x-momentum) and SRMBA (STORM-based).
Key results
- SPABA attains O((n+m)^{1/2} eps^-1) sample complexity in the finite-sum setting, closing the gap with single-level PAGE/SARAH/SPIDER under standard smoothness.
- SPABA attains O(eps^-1.5) sample complexity in the expectation setting under bounded variance and mean-squared smoothness, matching the single-level lower bound.
- MA-SABA improves SABA's sample complexity from O((n+m) eps^-1) to O((n+m)^{2/3} eps^-1) without high-order smoothness; experiments show SPABA best on MNIST hyper-cleaning and MA-SABA best on covtype suboptimality.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PAGE-based SPABA in place of the SAGA-based SABA baseline | Stochastic bilevel optimization · Finite-sum | sample complexity: $\mathcal{O}((n+m)\epsilon^{-1})^*$ -> $\mathcal{O}((n+m)^{\frac{1}{2}}\epsilon^{-1})$ | Helped |
| Add upper-level momentum to SABA | SABA (MA-SABA) · Finite-sum | sample complexity: $\mathcal{O}((n+m)\epsilon^{-1})^*$ -> $\mathcal{O}((n+m)^{\frac{2}{3}}\epsilon^{-1})$ | Helped |
| Use PAGE-based SPABA for bilevel optimization | Stochastic bilevel optimization · Expectation (mean-squared smoothness) | sample complexity: $\tilde{\mathcal{O}}(\epsilon^{-1.5})$ -> $\mathcal{O}(\epsilon^{-1.5})$ | Helped |
| Increase q from 0 in MA-SOBA-q (ablation) | MA-SOBA-q · MNIST data hyper-cleaning | convergence speed | Helped |
Surprising findings
- The SOBA-style analysis under standard smoothness gives O(eps^-2.5), so a gap with single-level SGD exists for that estimator, which momentum on x closes.
Limitations
- Still relies on Hessian and Jacobian-vector products (second-order oracle access).
- Optimality in the finite-sum setting holds only under conditions like m=O(n) and eps=O(n^-1/2) per the lower bound comparison.
- Experiments are on small-scale hyperparameter and hyper-cleaning tasks with logistic regression models.
Experimental setup
Datasets: MNIST covtype IJCNN1
Benchmarks: MNIST data hyper-cleaning covtype hyperparameter selection IJCNN1 hyperparameter selection
Metrics: test error suboptimality gap running time iterations
Baselines: AmIGO SUSTAIN SABA SOBA SRBA MRBO VRBO MA-SOBA
Builds on: PAGE DecBO SABA MA-SOBA STORM
Closest papers by meaning
- A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness (ICML 2024 · similarity 0.92)
- A Single-Loop Gradient Algorithm for Pessimistic Bilevel Optimization via Smooth Approximation (NeurIPS 2025 · similarity 0.90)
- An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness (NeurIPS 2024 · similarity 0.90)
- TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization (ICML 2025 · similarity 0.89)
- On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation (ICLR 2024 · similarity 0.89)
- Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems (NeurIPS 2026 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.