Research map / Optimization / Nonconvex and smooth optimization
LancBiO: Dynamic Lanczos-aided Bilevel Optimization via Krylov Subspace
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 LancBiO, a bilevel optimizer that approximates the Hessian-inverse-vector product via dynamically built Lanczos/Krylov subspaces with restarts and residual minimization, plus a simpler SubBiO variant, achieving O(epsilon^-1) convergence.
Problem
Computing the hyper-gradient in bilevel optimization requires a Hessian-inverse-vector product, which is expensive for large-scale problems; existing approximations (Neumann series, CG, warm starts) are costly or inaccurate.
Approach
Construct low-dimensional Krylov subspaces incrementally with a dynamic Lanczos process across outer iterations (with periodic restarts and residual-correction minimization), so that the Hessian inverse-vector product is approximated with about 1+1/m Hessian-vector products per outer iteration.
Key results
- On MNIST data hyper-cleaning with p=0.8, LancBiO reaches 89.45% test accuracy versus 89.14% for AmIGO-GD and 88.57% for AmIGO-CG, with residual 9.18e-5 vs 1.07e-2 for AmIGO-GD.
- LancBiO achieves the lowest residual norm of the linear system among compared methods in hyper-cleaning experiments.
- Theory: LancBiO is globally convergent with O(epsilon^-1) iteration complexity for the averaged hyper-gradient norm squared.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LancBiO instead of AmIGO-CG | bilevel optimization · MNIST data hyper-cleaning, p=0.5 | residual: \expnumber{5.89}{-4}\pm\expnumber{2.52}{-4} -> \expnumber{1.20}{-4}\pm\expnumber{2.52}{-5} | Helped |
| Use LancBiO instead of AmIGO-CG | bilevel optimization · MNIST data hyper-cleaning, p=0.8 | residual: \expnumber{6.32}{-4}\pm\expnumber{3.74}{-4} -> \expnumber{9.18}{-5}\pm\expnumber{2.77}{-5} | Helped |
| Use LancBiO instead of SubBiO | bilevel optimization · MNIST data hyper-cleaning, p=0.5 | test accuracy (%): 90.21\pm0.2159 -> 90.35\pm0.1716 | No clear effect |
| Use LancBiO instead of SubBiO | bilevel optimization · MNIST data hyper-cleaning, p=0.8 | test accuracy (%): 89.22\pm0.2587 -> 89.45\pm0.2470 | Helped |
| Increase LancBiO subspace dimension m (ablation) | LancBiO · synthetic bilevel problem | residual norm | Helped |
| Use LancBiO instead of AmIGO-CG | bilevel hyper-parameter selection · 20Newsgroups | upper-level objective | Helped |
| Use AmIGO-CG instead of LancBiO | bilevel hyper-parameter selection · 20Newsgroups | residual norm | Helped |
Surprising findings
- AmIGO-CG achieves a competitive residual norm on the hyper-parameter selection task, slightly better than LancBiO in residual reduction, though LancBiO completes more outer iterations in the same time.
Limitations
- Lanczos process is numerically unstable, requiring restarts and a moderate subspace dimension m
- Theory assumes strongly convex lower-level problem; nonconvex extension is only sketched in the appendix
- Experiments are deterministic and on small-scale tasks such as MNIST-based hyper-cleaning and a synthetic problem
Experimental setup
Datasets: MNIST Fashion-MNIST Kuzushiji-MNIST 20Newsgroups
Benchmarks: MNIST data hyper-cleaning Fashion-MNIST data hyper-cleaning Kuzushiji-MNIST data hyper-cleaning 20Newsgroups hyper-parameter selection synthetic bilevel problem
Metrics: test accuracy test loss residual norm of linear system hyper-gradient norm
Baselines: AmIGO-GD AmIGO-CG SOBA TTSA stocBiO F2SA HJFBiO SubBiO
Builds on: stocBiO AmIGO SOBA Lanczos process approximate implicit differentiation
Closest papers by meaning
- qNBO: quasi-Newton Meets Bilevel Optimization (ICLR 2025 · similarity 0.89)
- Optimal Hessian/Jacobian-Free Nonconvex-PL Bilevel Optimization (ICML 2024 · similarity 0.88)
- Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysis (ICLR 2025 · similarity 0.87)
- A Single-Loop First-Order Algorithm for Linearly Constrained Bilevel Optimization (NeurIPS 2025 · similarity 0.87)
- Problem-Parameter-Free Decentralized Bilevel Optimization (NeurIPS 2025 · similarity 0.87)
- A Single-Loop Gradient Algorithm for Pessimistic Bilevel Optimization via Smooth Approximation (NeurIPS 2025 · similarity 0.86)
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.