Research map / Optimization / Nonconvex and smooth optimization
Optimal Hessian/Jacobian-Free Nonconvex-PL 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 HJFBiO, a Hessian/Jacobian-free single-loop bilevel method for nonconvex lower-level problems satisfying PL, using finite-difference Hessian/Jacobian-vector estimates and a new vector projection, claiming O(1/T) rate and O(eps^-1) gradient complexity.
Problem
Nonconvex-PL bilevel optimization where the upper-level may be nonconvex and the lower-level is nonconvex but satisfies the Polyak-Łojasiewicz condition; existing methods need costly Hessian/Jacobian matrices/inverses or have high complexity.
Approach
Replace Hessian/Jacobian matrices and projected Hessian inverses with finite-difference Hessian-vector and Jacobian-vector estimates and an auxiliary vector v updated by projected gradient steps on a strongly convex surrogate, with a new projection M_{r_h}(H,v)=S[H]P(v) that is applied to vectors; the three-sequence single-loop scheme achieves O(eps^-1) complexity.
Key results
- Theory: HJFBiO achieves O(1/T) convergence of averaged squared gradient mapping, i.e., O(eps^-1) gradient complexity (7T gradient calls per iteration) under global and local PL conditions.
- On the bilevel PL game and matrix-sensing hyper-representation tasks, HJFBiO outperforms the compared methods on gradient norm and distance vs. outer iterations.
- On the loss metric in hyper-representation learning, HJFBiO is only comparable to MGBiO.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use HJFBiO with finite-difference estimators and the new projection operator instead of Hessian/Jacobian-based computation | Nonconvex-PL bilevel optimization · Nonconvex-PL bilevel optimization (global and local PL) | gradient complexity: O(\epsilon^{-1}) | Helped |
| Use HJFBiO instead of the compared methods | Bilevel PL game · Bilevel PL game (d=100 and d=200) | gradient norm | Helped |
| Use HJFBiO instead of the compared methods | Hyper-representation learning · Matrix sensing distance (d=100 and d=200) | distance | Helped |
| Use HJFBiO instead of MGBiO | Hyper-representation learning · Matrix sensing loss (d=100 and d=200) | loss | No clear effect |
| Replace Hessian/Jacobian matrix computations with first-order gradients and finite-difference estimates | HJFBiO · Nonconvex-PL bilevel optimization | per-iteration computation complexity: O(p+d) | Helped |
| Use HJFBiO instead of MGBiO | Bilevel PL game and hyper-representation learning · Bilevel PL game and matrix sensing | per-iteration computation | Helped |
Surprising findings
- The GALET convergence results become meaningless when the Hessian's nonzero singular value lower bound goes to zero, per the paper's analysis.
Limitations
- Requires Lipschitz assumptions on Hessian/Jacobian-type terms and a bounded-upper-level-gradient assumption, and the complexity rests on a finite-difference parameter delta chosen as O(1/sqrt(T)).
- Experiments are limited to synthetic bilevel PL game and matrix sensing tasks with small dimensions (d=100, 200).
Experimental setup
Datasets: synthetic bilevel PL game data synthetic matrix sensing data
Benchmarks: bilevel PL game (d=100, d=200) hyper-representation learning on matrix sensing (d=100, d=200)
Metrics: norm of gradient distance ||UU^T-H*||_F^2/||H*||_F^2 loss
Baselines: BOME V-PBGD GALET SLM Prox-F2BA F2BA MGBiO AdaPAG BVFSM
Builds on: MGBiO F2BA BOME AdaPAG GALET
Closest papers by meaning
- Generalized Smooth Bilevel Optimization with Nonconvex Lower-Level (ICML 2025 · similarity 0.91)
- TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization (ICML 2025 · similarity 0.90)
- qNBO: quasi-Newton Meets Bilevel Optimization (ICLR 2025 · similarity 0.90)
- On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation (ICLR 2024 · similarity 0.88)
- Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysis (ICLR 2025 · similarity 0.88)
- Double Momentum Method for Lower-Level Constrained Bilevel Optimization (ICML 2024 · similarity 0.88)
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.