Research map / Optimization / Nonconvex and smooth optimization
An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness
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 AccBO, a bilevel method with normalized recursive-momentum upper-level updates and stochastic Nesterov accelerated lower-level updates, achieving Õ(ε^-3) oracle complexity under unbounded smoothness when lower-level gradient noise is O(ε).
Problem
Stochastic bilevel optimization where the upper-level objective is nonconvex with unbounded (gradient-norm-dependent) smoothness and the lower level is strongly convex; prior best oracle complexity was Õ(ε^-4).
Approach
Combine normalized SGD with recursive momentum for the upper level and stochastic Nesterov accelerated gradient with averaging for the lower level, plus a high-probability analysis of SNAG under distribution drift, to get Õ(ε^-3) complexity under almost-sure Lipschitz stochastic oracles.</234>
Key results
- AccBO achieves Õ(ε^-3) oracle complexity for finding an ε-stationary point when lower-level stochastic gradient variance is O(ε), improving the Õ(ε^-4) of prior unbounded-smoothness bilevel methods.
- On imbalanced Sentiment140 deep AUC maximization with an RNN, AccBO reports the highest AUC among the bilevel baselines over epochs and running time.
- On SNLI data hyper-cleaning with noise rates 0.1 and 0.2, AccBO shows the highest train and test accuracy among the bilevel baselines with high runtime efficiency.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use AccBO instead of prior unbounded-smoothness bilevel algorithms | Bilevel optimization with a nonconvex unbounded-smooth upper level and strongly convex lower level · ε-stationary point | oracle complexity: \widetilde{O}(\epsilon^{-4}) -> \widetilde{O}(\epsilon^{-3}) | Helped |
| Use AccBO rather than the compared bilevel optimization baselines | Deep AUC maximization with an RNN on imbalanced Sentiment140 · Sentiment140 | AUC | Helped |
| Use AccBO rather than the compared bilevel optimization baselines | Data hypercleaning with an RNN on SNLI · SNLI, noise rates p=0.1 and p=0.2 | classification accuracy | Helped |
Limitations
- Option I single-loop analysis only holds for quadratic lower-level functions.
- Requires lower-level stochastic gradient variance O(ε), which may be restrictive.
- No single-loop algorithm with guarantees for general strongly convex lower levels.
Experimental setup
Datasets: Sentiment140 SNLI
Benchmarks: Sentiment140 SNLI
Metrics: AUC classification accuracy running time
Baselines: StocBio TTSA SABA MA-SOBA SUSTAIN VRBO BO-REP
Builds on: momentum-based variance reduction (STORM) relaxed smoothness (Zhang et al.) Stochastic Nesterov accelerated gradient MA-SOBA Hao et al. unbounded smoothness bilevel
Closest papers by meaning
- A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness (ICML 2024 · similarity 0.96)
- Bilevel Optimization under Unbounded Smoothness: A New Algorithm and Convergence Analysis (ICLR 2024 · similarity 0.95)
- TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization (ICML 2025 · similarity 0.91)
- SPABA: A Single-Loop and Probabilistic Stochastic Bilevel Algorithm Achieving Optimal Sample Complexity (ICML 2024 · similarity 0.90)
- Generalized Smooth Bilevel Optimization with Nonconvex Lower-Level (ICML 2025 · similarity 0.90)
- Conditional Gradient Methods with Standard LMO for Stochastic Simple Bilevel Optimization (NeurIPS 2025 · similarity 0.90)
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.