Research map / Optimization / Nonconvex and smooth optimization
An Adaptive Algorithm 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.
Proposes AdaRHD, a fully adaptive (inverse cumulative gradient norm step size) double-loop algorithm for deterministic Riemannian bilevel optimization with a geodesically strongly convex lower level, achieving O(1/epsilon) iteration complexity without problem-specific constants.
Problem
Riemannian bilevel optimization requires knowing strong convexity, Lipschitz, and curvature constants to set step sizes, which are often unknown or costly to estimate.
Approach
Adapts the Euclidean D-TFBO inverse-cumulative-gradient-norm step size strategy to Riemannian manifolds for both the lower-level solver and the hypergradient linear system (GD or tangent-space CG), with a trigonometric distance bound handling curvature, and extends to retraction mappings.
Key results
- AdaRHD-CG reaches 85% validation accuracy fastest across step sizes (e.g., 1217 s at initial step 5 vs. RHGD-50/20 failing at large step sizes).
- RHGD-50 and RHGD-20 fail to converge for initial step sizes 5, 1, or 0.5 while AdaRHD remains stable.
- AdaRHD achieves O(1/T) convergence of averaged squared hypergradient norm, i.e., O(1/epsilon) iterations, matching non-adaptive methods; gradient complexity G_g is O(1/epsilon^2) for AdaRHD-GD, a 1/epsilon gap.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use fully adaptive step sizes instead of problem-specific fixed step sizes | AdaRHD versus RHGD · AFEW validation, initial step sizes 5, 1, or 0.5 | convergence to validation accuracy | Helped |
| use conjugate gradient instead of gradient descent to solve the linear system | AdaRHD · AFEW validation, 85% accuracy | time: 1488.26 (426.67) -> 1217.06 (635.57); 421.99 (88.31) -> 245.63 (72.42); 477.49 (120.17) -> 241.54 (33.09); 546.18 (66.68 | Helped |
| set initial step sizes to 1 or 2 rather than other tested initializations | AdaRHD variants · AFEW validation | training performance | Helped |
| replace exponential mappings with retraction mappings (ablation) | AdaRHD · Riemannian bilevel optimization | iteration complexity: \mathcal{O}\left(\frac{1}{T}\right) -> \mathcal{O}\left(\frac{1}{T}\right) | No clear effect |
Surprising findings
- Step size initializations greater than 1 (0.2 in reciprocal form) still converge although less stable, and the adaptive method outperforms RHGD even on the best RHGD step size for 85% accuracy in some settings.
Limitations
- Gradient and Hessian-vector complexity for AdaRHD-GD is worse than non-adaptive methods by a factor of 1/epsilon.
- Only deterministic, double-loop setting with geodesically strongly convex lower-level problem is treated.
- Assumes bounded iterates and curvature constants for retraction extension.
Experimental setup
Datasets: AFEW
Benchmarks: AFEW (5% subset, SPD hyper-representation) simple Stiefel/SPD matrix similarity problem
Metrics: upper-level objective hypergradient estimation error validation accuracy time to reach validation accuracy standard deviation over 5 seeds
Baselines: RHGD-50 RHGD-20 RieBO
Builds on: D-TFBO RHGD AdaGrad-Norm RieBO
Closest papers by meaning
- A Framework for Bilevel Optimization on Riemannian Manifolds (NeurIPS 2024 · similarity 0.94)
- Efficient Curvature-Aware Hypergradient Approximation for Bilevel Optimization (ICML 2025 · similarity 0.90)
- Select-then-differentiate: Solving Bilevel Optimization with Manifold Lower-level Solution Sets (NeurIPS 2026 · similarity 0.88)
- Adaptive Riemannian ADMM for Nonsmooth Optimization: Optimal Complexity without Smoothing (NeurIPS 2025 · similarity 0.88)
- Convergence and Trade-Offs in Riemannian Gradient Descent and Riemannian Proximal Point (ICML 2024 · similarity 0.88)
- Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Method (ICML 2025 · similarity 0.87)
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.