Research map / Optimization / Nonconvex and smooth optimization
qNBO: quasi-Newton Meets 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 qNBO, a bilevel framework where quasi-Newton (BFGS/SR1) recursions solve the lower-level problem and approximate the inverse-Hessian-vector product for hypergradients, with a non-asymptotic convergence analysis for BFGS.
Problem
Hypergradient estimation in bilevel optimization requires both an accurate lower-level solution and inverse-Hessian-vector products, which existing methods handle separately at extra cost.
Approach
Coordinate lower-level solving and inverse-Hessian approximation by reusing quasi-Newton (BFGS/SR1) recursion pairs from the lower-level solve, plus a separate quasi-Newton subroutine for the upper-level direction (Q_k>1) to avoid incorrect inversion as in SHINE; the outer update uses the resulting hypergradient approximation.
Key results
- On MNIST hyper-cleaning, qNBO (BFGS) reaches 91.5% test accuracy in 0.42 s versus 6.31 s for BOME, the second fastest method.
- On Omniglot 5-shot meta-learning, qNBO (BFGS) reaches 99.14% accuracy in 772 s versus PZOBO's 99.31% in 11124 s (5-way), and is faster at 20-way and 30-way.
- Theory: non-asymptotic rate O(kappa^3/K + kappa^3 ln K / K) for the averaged squared gradient norm of qNBO (BFGS) in the general case, with gradient complexity tilde-O(kappa^6 eps^-2) and JV complexity tilde-O(kappa^3 eps^-1).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use qNBO (BFGS) instead of BOME | Data hyper-cleaning · MNIST test | time (s): 6.31 -> 0.42 | Helped |
| Use qNBO (BFGS) instead of BOME | Data hyper-cleaning · MNIST test | accuracy (%): 91.50 -> 91.54 | Helped |
| Use qNBO (BFGS) instead of SHINE-OPA | Data hyper-cleaning · MNIST test | F1 score: 95.44 -> 95.34 | Hurt |
| Use qNBO (BFGS) instead of BOME | Data hyper-cleaning · FashionMNIST test | time (s): 3.59 -> 0.83 | Helped |
| Use qNBO (BFGS) instead of SHINE-OPA | Data hyper-cleaning · FashionMNIST test | accuracy (%): 83.07 -> 83.04 | Hurt |
| Use qNBO (BFGS) instead of PZOBO | Few-shot meta-learning · Omniglot 5-way 5-shot | accuracy (%): 99.31 -> 99.14 | Hurt |
| Use qNBO (BFGS) instead of PZOBO | Few-shot meta-learning · Omniglot 5-way 5-shot | time (s): 11124 -> 772 | Helped |
| Use qNBO (BFGS) instead of PZOBO | Few-shot meta-learning · Omniglot 20-way 5-shot | accuracy (%): 97.94 -> 99.14 | Helped |
| Use qNBO (BFGS) instead of PZOBO | Few-shot meta-learning · Omniglot 30-way 5-shot | accuracy (%): 97.15 -> 99.05 | Helped |
| Increase Q_k to k+1 (ablation) | qNBO (BFGS) · Toy example | hypergradient error | Helped |
| Use a warm start for u_k (ablation) | qNBO (BFGS) · Toy example | hypergradient error | Helped |
| Reduce T (ablation) | qNBO (BFGS) · MNIST and FashionMNIST data hyper-cleaning | accuracy | Helped |
Surprising findings
- qNBO (SR1) oscillated and was omitted from the 20News experiment due to numerical instability without a correction strategy.
- The SR1 variant lacks convergence guarantees for the general (nonquadratic) case without numerical-stability corrections.
Limitations
- General-case convergence analysis requires strong assumptions (Lipschitz Hessians, strong convexity) and the SR1 variant lacks guarantees without corrections.
- Gradient complexity tilde-O(kappa^6 eps^-2) is higher than AID-BIO's gradient complexity.
- Stochastic adaptation is left as future work and not analyzed.
Experimental setup
Datasets: 20News Real-sim MNIST FashionMNIST miniImageNet FC100 Omniglot
Benchmarks: toy quadratic bilevel problem 20News hyperparameter optimization Real-sim hyperparameter optimization MNIST data hyper-cleaning FashionMNIST data hyper-cleaning miniImageNet few-shot meta-learning FC100 few-shot meta-learning Omniglot few-shot meta-learning
Metrics: hypergradient error test loss test accuracy F1 score wall-clock time to target accuracy gradient norm convergence rate
Baselines: SHINE-OPA PZOBO BOME F2SA SABA BSG1 AID-BIO AID-TN AMIGO
Builds on: SHINE AID-BIO PZOBO BOME F2SA
Closest papers by meaning
- Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysis (ICLR 2025 · similarity 0.90)
- Optimal Hessian/Jacobian-Free Nonconvex-PL Bilevel Optimization (ICML 2024 · similarity 0.90)
- Generalized Smooth Bilevel Optimization with Nonconvex Lower-Level (ICML 2025 · similarity 0.89)
- LancBiO: Dynamic Lanczos-aided Bilevel Optimization via Krylov Subspace (ICLR 2025 · similarity 0.89)
- Bilevel Optimization under Unbounded Smoothness: A New Algorithm and Convergence Analysis (ICLR 2024 · similarity 0.89)
- Double Momentum Method for Lower-Level Constrained Bilevel Optimization (ICML 2024 · 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.