Research map / Optimization / Nonconvex and smooth optimization
A Nearly Optimal Single Loop 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 SLIP, a single-loop stochastic bilevel optimizer (warm-start SGD, then SGD for lower level and normalized momentum SGD for upper level) that finds epsilon-stationary points under unbounded smoothness with O~(eps^-4) oracle calls, in expectation and with high probability.
Problem
Stochastic bilevel optimization with a nonconvex upper level whose smoothness is potentially unbounded (relaxed smoothness, e.g. RNN losses) and a strongly convex lower level; prior algorithms for this setting are nested-loop and hard to tune.
Approach
A single-loop algorithm that warm-starts the lower-level variable with a few SGD steps, then simultaneously runs SGD on the lower-level variable and normalized SGD with momentum on the upper-level variable, using a refined control showing only the average lower-level error (not per-iteration accuracy) matters, plus an analysis linking the lower-level tracking to SGD under distributional drift.
Key results
- SLIP achieves O~(1/eps^4) oracle complexity for epsilon-stationary points in expectation and with high probability, matching the best nested-loop complexity (BO-REP) while using a single loop.
- In hyper-representation experiments on SNLI and ARD, SLIP consistently outperforms all baselines in training and test accuracy versus epochs.
- SLIP runs faster in wall-clock time than all baselines, with BO-REP second, e.g. in hyper-representation learning because gradients for y are reused in the same backpropagation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SLIP instead of bilevel optimization baselines | Hyper-representation learning · SNLI | training and test accuracy | Helped |
| Use SLIP instead of bilevel optimization baselines | Hyper-representation learning · Amazon Review Dataset | training and test accuracy | Helped |
| Use SLIP instead of bilevel optimization baselines | Data hyper-cleaning · Sentiment140, corruption rate p=0.2 | accuracy | Helped |
| Use SLIP instead of bilevel optimization baselines | Data hyper-cleaning · Sentiment140, corruption rate p=0.4 | accuracy | Helped |
| Use SLIP instead of bilevel optimization baselines | Hyper-representation learning and data hyper-cleaning · SNLI, Amazon Review Dataset, and Sentiment140 | running time | Helped |
Limitations
- Complexity is nearly optimal only without mean-squared smoothness of the stochastic gradient oracle; O(1/eps^3) left open.
- High-probability guarantee requires stronger almost-sure or light-tailed noise assumptions on the oracles.
- Experiments are limited to small-scale text classification and hyper-cleaning tasks.
Experimental setup
Datasets: SNLI Amazon Review Dataset Sentiment140
Benchmarks: SNLI Amazon Review Dataset Sentiment140
Metrics: training accuracy test accuracy running time
Baselines: MAML ANIL StocBio TTSA F2SA SABA MA-SOBA BO-REP
Builds on: BO-REP relaxed smoothness (Zhang et al.) StocBio SOBA / MA-SOBA SGD with distribution drift
Closest papers by meaning
- An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness (NeurIPS 2024 · similarity 0.96)
- Bilevel Optimization under Unbounded Smoothness: A New Algorithm and Convergence Analysis (ICLR 2024 · similarity 0.94)
- SPABA: A Single-Loop and Probabilistic Stochastic Bilevel Algorithm Achieving Optimal Sample Complexity (ICML 2024 · similarity 0.92)
- TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization (ICML 2025 · similarity 0.91)
- Generalized Smooth Bilevel Optimization with Nonconvex Lower-Level (ICML 2025 · similarity 0.90)
- A Single-Loop Gradient Algorithm for Pessimistic Bilevel Optimization via Smooth Approximation (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.