Research map / Optimization / Nonconvex and smooth optimization
On the Complexity of Finding Stationary Points in 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 a discrete-time variant of dynamic barrier gradient descent (DBGD) for nonconvex simple bilevel problems, defining (eps_f, eps_g)-stationarity and proving an O(max(eps_f^{-(3+p)/(1+p)}, eps_g^{-(3+p)/2})) complexity bound.
Problem
Finding stationary points of nonconvex simple bilevel problems, where the upper-level objective f is minimized over the solution set of a smooth nonconvex lower-level objective g, without PL or convexity assumptions.
Approach
Applies the dynamic barrier gradient descent framework in discrete time with a gradient-norm-based barrier phi(x)=beta*||grad g||^2, using a new potential function that avoids needing a uniform bound on the dynamic multiplier lambda_k, and defines a stationarity metric tied to local behavior of f and g.
Key results
- Theorem gives complexity O(max(eps_f^{-(3+p)/(1+p)}, eps_g^{-(3+p)/2})); with p=1 this becomes O(max(eps_f^{-2}, eps_g^{-2})).
- On a toy example, DBGD outperforms fixed-penalty methods across ||grad g||, ||grad_perp f||, and cos theta for all tested lambda values in {1,10,100,1000}.
- On matrix factorization with sparsity penalties, DBGD consistently attains lower stationarity metrics and better g and f values than penalty methods across beta values.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the gradient-norm-based inequality-constrained DBGD update instead of a fixed-λ penalty update | Toy Example · Toy Example | ‖∇g‖ | Helped |
| Use the gradient-norm-based inequality-constrained DBGD update instead of a fixed-λ penalty update | Toy Example · Toy Example | ‖∇⊥f‖ | Helped |
| Use the gradient-norm-based inequality-constrained DBGD update instead of a fixed-λ penalty update | Toy Example · Toy Example | cos θ | Helped |
| Increase the fixed penalty parameter λ | Penalty method · Toy Example | ‖∇g‖ | Mixed |
| Use the gradient-norm-based inequality-constrained DBGD update instead of a fixed-λ penalty update | Matrix Factorization · Matrix Factorization | ‖∇g‖ | Helped |
| Use the gradient-norm-based inequality-constrained DBGD update instead of a fixed-λ penalty update | Matrix Factorization · Matrix Factorization | ‖∇⊥f‖ | Helped |
| Vary β for DBGD | DBGD · Matrix Factorization | reconstruction loss g(U) | No clear effect |
| Vary β for DBGD | DBGD · Matrix Factorization | sparsity penalty f(U) | No clear effect |
| Vary the fixed penalty parameter λ | Penalty method · Matrix Factorization | trade-off between reconstruction loss and sparsity penalty | Hurt |
Surprising findings
- The dynamic multiplier lambda_k may diverge as ||grad g|| approaches zero, so no uniform bound on lambda_k is available and the standard constant-step analysis fails.
Limitations
- Analysis is deterministic; stochastic setting not covered in the theory.
- Only small-scale numerical experiments; large-scale neural network experiments are not repeated.
- Requires bounded upper-level gradients (G_f) and Lipschitz gradients of f and g.
Experimental setup
Benchmarks: toy simple bilevel problem matrix factorization with sparsity penalty
Metrics: ||grad g||^2 ||grad_perp f||^2 cos theta f value g value
Baselines: Penalty method with fixed lambda BLOOP
Builds on: dynamic barrier gradient descent BLOOP lower-level linearization methods scaled KKT conditions
Closest papers by meaning
- An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization (NeurIPS 2024 · similarity 0.92)
- Set Smoothness Unlocks Clarke Hyper-stationarity in Bilevel Optimization (NeurIPS 2025 · similarity 0.92)
- First-Order Methods for Linearly Constrained Bilevel Optimization (NeurIPS 2024 · similarity 0.91)
- Stochastic Dynamic Barrier Perturbed Gradient Methods for Nonconvex Simple Bilevel Optimization (NeurIPS 2026 · similarity 0.91)
- On The Complexity of First-Order Methods in Stochastic Bilevel Optimization (ICML 2024 · similarity 0.91)
- Penalty-based Methods for Simple Bilevel Optimization under Hölderian Error Bounds (NeurIPS 2024 · similarity 0.91)
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.