Research map / Optimization / Nonconvex and smooth optimization
On The Complexity of First-Order Methods in Stochastic Bilevel Optimization
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.
Studies first-order bilevel optimization with a y*-aware oracle that returns an O(eps)-accurate lower-level solution and locally unbiased gradients, proposing penalty-based first-order methods with O(eps^-6) and O(eps^-4) complexity plus matching lower bounds.
Problem
Finding epsilon-stationary points of stochastic bilevel problems with unconstrained strongly convex lower level using only first-order oracles, where the oracle also provides a lower-level solution estimate and gradients are reliable only near y*(x).
Approach
Introduces a y*-aware oracle model and a penalty-method first-order algorithm with lower-level coupling and projection onto a trust region around y*, achieving O(eps^-6) (or O(eps^-4) with stochastic smoothness) and matching probabilistic zero-chain lower bounds.
Key results
- Upper bound O(eps^-6) for first-order methods with y*-aware oracles, improving F2SA's O(eps^-7) by O(eps).
- Upper bound O(eps^-4) with stochastic smoothness in y, improving the best-known O(eps^-5).
- Matching lower bounds Omega(eps^-6) without and Omega(eps^-4) with stochastic smoothness for zero-respecting and randomized algorithms.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed penalty method instead of F^2SA | First-order bilevel optimization without stochastic smoothness · Bilevel optimization | first-order oracle complexity: O(\epsilon^{-7}) -> O(\epsilon^{-6}) | Helped |
| Use the proposed method with stochastic smoothness in y | First-order bilevel optimization · Bilevel optimization with stochastic smoothness | first-order oracle complexity: O(\epsilon^{-5}) -> O(\epsilon^{-4}) | Helped |
| Add stochastic smoothness | First-order bilevel optimization · Bilevel optimization | first-order oracle complexity: O(\epsilon^{-6}) -> O(\epsilon^{-4}) | Helped |
| Add stochastic smoothness | First-order bilevel optimization lower bound · Bilevel optimization | minimax oracle complexity lower bound: \Omega(\epsilon^{-6}) -> \Omega(\epsilon^{-4}) | Helped |
Surprising findings
- First-order methods can match the O(eps^-4) rate of second-order methods under stochastic smoothness assumptions.
Limitations
- Lower bounds hold only for oracle reliability radius r = Theta(eps); the globally unbiased case is left as a conjecture.
- Upper bounds rely on strong convexity of the lower-level problem and smoothness assumptions including Hessian Lipschitzness.
Experimental setup
Metrics: oracle complexity to epsilon-stationary point
Baselines: F2SA stocBiO MA-SOBA second-order bilevel methods
Builds on: F2SA penalty method for bilevel optimization probabilistic zero-chains
Closest papers by meaning
- Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems (NeurIPS 2026 · similarity 0.93)
- On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation (ICLR 2024 · similarity 0.91)
- On the Complexity of Finding Stationary Points in Nonconvex Simple Bilevel Optimization (NeurIPS 2025 · similarity 0.91)
- First-Order Methods for Linearly Constrained Bilevel Optimization (NeurIPS 2024 · similarity 0.91)
- Conditional Gradient Methods with Standard LMO for Stochastic Simple Bilevel Optimization (NeurIPS 2025 · similarity 0.91)
- Stochastic Dynamic Barrier Perturbed Gradient Methods for Nonconvex Simple Bilevel Optimization (NeurIPS 2026 · 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.