Research map / Optimization / Nonconvex and smooth optimization
Stochastic Dynamic Barrier Perturbed Gradient Methods for Nonconvex Simple 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.
Proposes SDBPG, a single-loop stochastic dynamic barrier gradient method with dual perturbation for nonconvex simple bilevel optimization, with a rare-visit assumption, plus penalty-regularized (PR-SDBPG) and variance-reduced (VR-PR-SDBPG) variants that remove that assumption.
Problem
Stochastic nonconvex-nonconvex simple bilevel optimization: minimize an upper-level objective over the solution set of a nonconvex lower-level problem, with only stochastic gradient access; the dual multiplier can blow up near lower-level stationary points.
Approach
Perturb the denominator of the DBGD dual multiplier (||grad g||^2 + gamma_k) so the stochastic multiplier stays bounded, controlling bias and variance; a penalty-regularized subproblem with fixed gamma>0 removes the need for the rare-visit assumption.
Key results
- SDBPG finds (eps,eps)-stationary point in O(eps^{-1/delta}) iterations with sample complexities O(eps^{-2/delta}) upper and O(eps^{-3/delta}) lower; O(eps^{-4}) and O(eps^{-6}) when delta=1/2.
- PR-SDBPG removes the rare-visit assumption with O(eps^{-8}) upper and O(eps^{-10}) lower sample complexities.
- VR-PR-SDBPG improves these to O(eps^{-6}) upper and O(eps^{-8}) lower.
- On LLM unlearning (TOFU, MUSE-News), stochastic methods show faster decay of stationarity metrics than deterministic DDBPG versus samples and wall-clock time.
Surprising findings
- Penalty-regularized PR-SDBPG uses fixed batch sizes, but its theoretical sample complexity is worse than the rare-visit SDBPG bound.
Limitations
- Rare-visit assumption required for the best SDBPG rate, with rate depending on unknown visit parameter delta.
- PR-SDBPG and VR-PR-SDBPG have much higher sample complexities than the rare-visit variant.
- Experiments are limited to LLM unlearning benchmarks; details deferred to appendix.
Experimental setup
Datasets: TOFU MUSE-News
Benchmarks: TOFU MUSE-News
Metrics: normalized squared gradient norm of lower-level objective normalized squared norm of descent direction
Baselines: DDBPG BLOOP SDBPG PR-SDBPG
Builds on: dynamic barrier gradient descent STORM ConEx SRPD
Closest papers by meaning
- On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation (ICLR 2024 · similarity 0.92)
- Conditional Gradient Methods with Standard LMO for Stochastic Simple Bilevel Optimization (NeurIPS 2025 · similarity 0.92)
- On the Complexity of Finding Stationary Points in Nonconvex Simple Bilevel Optimization (NeurIPS 2025 · similarity 0.91)
- TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization (ICML 2025 · similarity 0.90)
- An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization (NeurIPS 2024 · similarity 0.90)
- On The Complexity of First-Order Methods in Stochastic Bilevel Optimization (ICML 2024 · 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.