Research map / Optimization / Optimizers
Efficient Curvature-Aware Hypergradient Approximation for 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 NBO, a Newton-based bilevel framework that couples lower-level inexact Newton steps with Hessian-inverse-vector products via a shared Hessian, with deterministic (NBO-GD/NBO-CG) and stochastic (NSBO-SGD) variants and improved complexity bounds.
Problem
Hypergradient estimation for bilevel optimization requires solving the lower-level problem and computing Hessian inverse-vector products, which are usually treated separately, leading to high computational cost and lacking convergence-rate guarantees for SHINE-style quasi-Newton approaches.
Approach
Exploit the shared lower-level Hessian: solve the lower-level subproblem and the Hessian-inverse-vector product jointly via inexact Newton directions (inner GD/CG/SGD steps using only Hessian-vector products), and use the resulting curvature-aware approximation in an inexact hypergradient descent with warm-started u.
Key results
- NBO-GD with T=1 performs comparably to AmIGO with Q=10 on synthetic hyperparameter optimization and is fastest in running time.
- Theoretical complexity of NBO-GD: O(kappa^3/eps) gradient computations and O(kappa^4/eps) Hessian-vector products, improving over AID-BiO and AmIGO in the deterministic setting.
- NSBO-SGD achieves O(kappa^9 eps^-2) sample complexity, improving on AmIGO by a log kappa factor, and shows fastest convergence on IJCNN1 and MNIST hyper-cleaning among compared methods.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use curvature-aware inexact Newton directions in place of the compared gradient-based deterministic methods | NBO-GD · Deterministic bilevel optimization | gradient computations: AmIGO-GD: $ O((\kappa^4 \log \kappa)\epsilon^{-1}) $ -> NBO-GD: $ O(\kappa^3 \epsilon^{-1}) $ | Helped |
| Use conjugate gradient instead of gradient descent for solving the subproblems (ablation) | NBO · Deterministic bilevel optimization | Hessian-vector products: $ O(\kappa^4 /\epsilon) $ -> $ O(\kappa^{3.5} \log \kappa/\epsilon) $ | Helped |
| Use curvature-aware Newton-direction approximation with T = 1 rather than the single gradient-descent step in AmIGO | NBO-GD · Synthetic problem, r'=1 | running time to convergence | Helped |
| Reduce Newton-direction approximation to T = 1 (ablation) | NBO-GD · Synthetic problem, r'=1 | optimization performance | No clear effect |
| Use curvature-aware Newton-direction approximation with T = 1 instead of AmIGO's Q = 10 gradient steps | NSBO-SGD · IJCNN1 hyperparameter optimization | suboptimality gap over time | Helped |
| Use curvature-aware Newton-direction approximation with T = 1 instead of AmIGO's Q = 10 gradient steps | NSBO-SGD · Covtype hyperparameter optimization | test error over time | Helped |
| Use NSBO-SGD instead of the compared algorithms | NSBO-SGD · MNIST data hyper-cleaning | test error over time | Mixed |
| Use NSBO-SGD instead of the compared algorithms | NSBO-SGD · FashionMNIST data hyper-cleaning | test error over time | Mixed |
| Add the NBO framework to SAGA-based variance reduction | NSBO-SAGA · IJCNN1 hyperparameter optimization | optimization performance | Helped |
| Add the NBO framework to SAGA with moving-average momentum | MA-NSBO-SAGA · MNIST data hyper-cleaning | optimization performance | Helped |
| Add the NBO framework to BAMM hypergradient computation | BAMM+NBO · Toy problem with a non-strongly convex lower-level objective | optimization performance | Helped |
| Add moving-average momentum to NSBO-SAGA (ablation) | MA-NSBO-SAGA · FashionMNIST data hyper-cleaning | optimization performance | No clear effect |
Surprising findings
- A single inner gradient step (T=1) for the Newton direction suffices to match AmIGO with 10 inner steps, while AmIGO degrades badly with one step.
Limitations
- Theoretical results require strong convexity of the lower-level problem and bounded-gradient assumptions; non-strongly convex case handled only heuristically via BAMM aggregation.
- Stochastic complexity bounds are high in kappa (kappa^9 eps^-2), and the gain over AmIGO is only a log factor in the stochastic case.
- Experiments are on small-scale problems (logistic regression, MNIST/FashionMNIST, IJCNN1, Covtype) with no deep-network bilevel tasks.
Experimental setup
Datasets: IJCNN1 Covtype MNIST FashionMNIST synthetic logistic regression data
Benchmarks: IJCNN1 hyperparameter optimization Covtype hyperparameter optimization MNIST data hyper-cleaning FashionMNIST data hyper-cleaning synthetic hyperparameter optimization toy non-strongly convex bilevel example
Metrics: suboptimality gap test error running time iterations to tolerance
Baselines: SOBA SABA StoBiO AmIGO SHINE F2SA MA-SABA AID-BiO No-loop AID ALSET FSLA
Builds on: AID-BiO AmIGO SHINE SOBA stocBiO
Closest papers by meaning
- A Framework for Bilevel Optimization on Riemannian Manifolds (NeurIPS 2024 · similarity 0.91)
- An Adaptive Algorithm for Bilevel Optimization on Riemannian Manifolds (NeurIPS 2025 · similarity 0.90)
- An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization (NeurIPS 2024 · similarity 0.89)
- Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling (NeurIPS 2024 · similarity 0.89)
- TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization (ICML 2025 · 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.