Research map / Optimization / Nonconvex and smooth optimization
A Framework for Bilevel Optimization on Riemannian Manifolds
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.
Introduces a Riemannian hypergradient descent framework for bilevel problems whose upper and lower variables live on manifolds, with four hypergradient estimators (Hessian inverse, conjugate gradient, truncated Neumann series, automatic differentiation), convergence and complexity analysis, stochastic and retraction extensions, and experiments on SPD/Stiefel tasks.
Problem
Bilevel optimization where both upper- and lower-level variables are constrained to Riemannian manifolds, with a geodesically strongly convex lower-level problem; existing bilevel methods are unconstrained or handle only Euclidean constraints.
Approach
Derives an intrinsic Riemannian hypergradient via the implicit function theorem on manifolds and runs hypergradient descent with exponential-map or retraction updates, comparing four hypergradient estimators and bounding their errors and the resulting convergence and complexity.
Key results
- On Caltech-Office domain adaptation, the proposed bilevel approach achieves higher accuracy than OT-EMD and OT-SKH on all 12 tasks (e.g., 78.70 vs 76.83 for best baseline on A→C, 98.73 on W→D).
- Theory: the hypergradient estimators (HINV, CG, NS, AD) each come with error bounds, and RHGD reaches epsilon-stationarity with complexity matching Euclidean counterparts in the gradient complexity for f except for CG (higher by O(kappa_l)).
- In the synthetic and hyper-representation experiments, HINV and CG converge fastest, followed by NS and AD; RHGD outperforms the extrinsic projected baseline PHGD in meta learning.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed bilevel method instead of OT-SKH | Caltech-Office unsupervised domain adaptation · Caltech-Office A→C | accuracy: 76.83 -> 78.70 | Helped |
| Use the proposed bilevel method instead of OT-SKH | Caltech-Office unsupervised domain adaptation · Caltech-Office A→D | accuracy: 75.80 -> 80.25 | Helped |
| Use the proposed bilevel method instead of OT-SKH | Caltech-Office unsupervised domain adaptation · Caltech-Office A→W | accuracy: 69.83 -> 69.83 | No clear effect |
| Use the proposed bilevel method instead of OT-SKH | Caltech-Office unsupervised domain adaptation · Caltech-Office C→A | accuracy: 84.35 -> 88.21 | Helped |
| Use the proposed bilevel method instead of OT-SKH | Caltech-Office unsupervised domain adaptation · Caltech-Office C→D | accuracy: 78.34 -> 80.25 | Helped |
| Use the proposed bilevel method instead of OT-SKH | Caltech-Office unsupervised domain adaptation · Caltech-Office C→W | accuracy: 68.14 -> 68.47 | Helped |
| Use the proposed bilevel method instead of OT-SKH | Caltech-Office unsupervised domain adaptation · Caltech-Office D→A | accuracy: 80.92 -> 82.74 | Helped |
| Use the proposed bilevel method instead of OT-SKH | Caltech-Office unsupervised domain adaptation · Caltech-Office D→C | accuracy: 71.57 -> 75.69 | Helped |
| Use the proposed bilevel method instead of OT-SKH | Caltech-Office unsupervised domain adaptation · Caltech-Office D→W | accuracy: 93.90 -> 97.97 | Helped |
| Use the proposed bilevel method instead of OT-SKH | Caltech-Office unsupervised domain adaptation · Caltech-Office W→A | accuracy: 74.17 -> 83.49 | Helped |
| Use the proposed bilevel method instead of OT-SKH | Caltech-Office unsupervised domain adaptation · Caltech-Office W→C | accuracy: 67.02 -> 73.62 | Helped |
| Use the proposed bilevel method instead of OT-EMD | Caltech-Office unsupervised domain adaptation · Caltech-Office W→D | accuracy: 96.82 -> 98.73 | Helped |
Surprising findings
- Automatic differentiation has the worst error bound due to the curvature constant, and NS needs careful tuning of gamma and T.
Limitations
- Requires geodesic strong convexity of the lower-level problem and bounded iterates within a compact neighborhood.
- Stochastic analysis only covers the Hessian-inverse estimator and requires large batch sizes (kappa_l^2 epsilon^-1).
- Complexity in the curvature-dependent constant zeta is worse than Euclidean counterparts.
Experimental setup
Datasets: ETH-80 MiniImageNet Caltech-Office
Benchmarks: Caltech-Office MiniImageNet ETH-80
Metrics: upper-level objective hypergradient estimation error test accuracy classification accuracy validation accuracy
Baselines: PHGD (projected hypergradient descent) OT-EMD OT-SKH stocBiO HGD-CG HGD-AD
Builds on: implicit function theorem Riemannian gradient descent stocBiO
Closest papers by meaning
- An Adaptive Algorithm for Bilevel Optimization on Riemannian Manifolds (NeurIPS 2025 · similarity 0.94)
- Efficient Curvature-Aware Hypergradient Approximation for Bilevel Optimization (ICML 2025 · similarity 0.91)
- Learning-Rate-Free Stochastic Optimization over Riemannian Manifolds (ICML 2024 · similarity 0.88)
- Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Method (ICML 2025 · similarity 0.88)
- Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling (NeurIPS 2024 · similarity 0.88)
- Select-then-differentiate: Solving Bilevel Optimization with Manifold Lower-level Solution Sets (NeurIPS 2026 · 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.