Research map / Optimization / Nonconvex and smooth optimization
Bilevel Optimization under Unbounded Smoothness: A New Algorithm and Convergence Analysis
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 BO-REP, the first bilevel optimization algorithm for nonconvex upper-level functions with unbounded (relaxed) smoothness, using normalized momentum, lower-level initialization refinement, and periodic lower-level updates, achieving Õ(ε^-4) stochastic oracle complexity.
Problem
Stochastic bilevel optimization where the upper-level objective is nonconvex and has unbounded smoothness (e.g., RNNs/LSTMs), which breaks the standard bounded-smoothness analyses of hypergradient methods.
Approach
Update the upper variable with normalized momentum to tame unbounded gradients, initialize the lower-level variable via an epoch-SGD refinement, and update the lower-level variable only periodically, exploiting that normalized steps move the optimal lower-level solution slowly.
Key results
- BO-REP achieves Õ(ε^-4) stochastic oracle complexity for nonconvex, unbounded-smooth upper-level problems with strongly convex lower level, matching bounded-smoothness state of the art up to log factors.
- In hyper-representation learning on Amazon Review, BO-REP's green curve significantly outperforms MAML, ANIL, and bilevel baselines (per authors' figures).
- In data hyper-cleaning on Sentiment140 with corruption rate 0.3, BO-REP shows faster convergence and higher performance than baselines.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use BO-REP instead of the other bilevel optimization algorithms | Hyper-representation learning on Amazon Review Dataset · Amazon Review Dataset | training and test loss | Helped |
| Use BO-REP instead of the other bilevel optimization algorithms | Hyperparameter optimization for text classification · Amazon Review Dataset | validation loss | Helped |
| Use BO-REP instead of the other bilevel optimization algorithms | Data hyper-cleaning for text classification · Sentiment140, noise rate p=0.3 and p=0.1 | evaluation performance | Helped |
Limitations
- Analysis assumes strongly convex lower level and the algorithm is double-loop-like with periodic lower updates, not single-loop.
- Experiments are limited to text classification tasks with a small set of baselines.
- Oracle complexity is only logarithmically optimal relative to single-level lower bound; practical single-loop and Hessian-free variants left open.
Experimental setup
Datasets: Amazon Review Dataset Sentiment140
Benchmarks: Amazon Review Dataset Sentiment140
Metrics: training loss test loss validation loss
Baselines: MAML ANIL StocBio TTSA F2SA SOBA MA-SOBA
Builds on: relaxed smoothness (L0,L1) normalized momentum SGD StocBio SOBA MA-SOBA
Closest papers by meaning
- An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness (NeurIPS 2024 · similarity 0.95)
- A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness (ICML 2024 · similarity 0.94)
- Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysis (ICLR 2025 · similarity 0.90)
- Generalized Smooth Bilevel Optimization with Nonconvex Lower-Level (ICML 2025 · similarity 0.90)
- TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization (ICML 2025 · similarity 0.90)
- A Single-Loop Gradient Algorithm for Pessimistic Bilevel Optimization via Smooth Approximation (NeurIPS 2025 · 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.