An Adaptive Algorithm for Bilevel Optimization on Riemannian Manifolds¶

会议: NeurIPS 2025
arXiv: 2504.06042
代码: https://github.com/RufengXiao/AdaRHD
领域: 黎曼优化 / 双层优化
关键词: 黎曼流形, 双层优化, 自适应步长, 超梯度, 共轭梯度

一句话总结¶

AdaRHD 是首个无需预知问题参数（强凸常数、Lipschitz 界、流形曲率）的黎曼双层优化自适应算法——通过逆累计梯度范数策略自适应选择步长，在三阶段框架中逐步求解下层问题/线性系统/上层更新，收敛速率 \(O(1/\epsilon)\) 匹配非自适应方法，对初始步长选择鲁棒性远超 RHGD。

研究背景与动机¶

领域现状：黎曼双层优化（RBO）在机器学习中应用广泛——SPD 流形上的超参数优化、Stiefel 流形上的鲁棒主成分分析等。现有方法 RHGD 需要预知强凸常数、Lipschitz 连续界、流形曲率参数来确定步长。
现有痛点：这些参数在实践中难以估计——尤其在非欧几何上。错误的步长选择导致 RHGD 完全失败（实验中步长 5/1/0.5 时直接发散），而 AdaRHD 在 0.2-20 的步长范围内都能收敛。
核心矛盾：双层优化在欧几里得空间已有自适应方法（如 AdaGrad），但黎曼流形的几何特性（测地线、平行传输、指数映射）使得自适应步长设计更加困难。
本文要解决什么？ 设计无需超参数调节的黎曼双层优化算法，保持与已知参数方法相同的收敛速率。
切入角度：将 AdaGrad-Norm 策略扩展到黎曼流形上的三层嵌套优化。
核心 idea 一句话：逆累计梯度范数自适应步长 + 三阶段（下层 RGD → 线性系统 CG → 上层超梯度下降）= 无参数黎曼双层优化。

方法详解¶

整体框架¶

三阶段：Stage 1 用自适应 RGD 求解下层问题（测地强凸）→ Stage 2 用 CG/GD 求解 Hessian 逆向量积（线性系统）→ Stage 3 用近似超梯度做上层自适应下降。每阶段步长均用逆累计范数：\(\eta_t = \eta_0 / \sqrt{\sum_{s=1}^t \|\nabla f_s\|^2}\)

两种变体：AdaRHD-GD（梯度下降求解线性系统，\(O(1/\epsilon)\)）和 AdaRHD-CG（共轭梯度，\(O(\log(1/\epsilon))\)——Hessian-向量积复杂度更优）。

关键设计¶

自适应步长策略（逆累计梯度范数）:
做什么：根据历史梯度自动调整步长
核心思路：\(\eta_t = \eta_0 / \sqrt{\sum_{s=1}^t \|g_s\|^2}\)——梯度大时步长小（避免震荡），梯度小时步长大（加速收敛）。Stage 1 对数缩放，Stage 2 指数缩放
设计动机：消除对强凸常数 \(\mu\)、Lipschitz 常数 \(L\)、流形曲率 \(\kappa\) 的依赖
两种变体（AdaRHD-GD 和 AdaRHD-CG）:
做什么：用不同方法求解线性系统 \(H^{-1}v\)
核心思路：GD 变体用梯度下降求解线性系统，\(O(1/\epsilon)\) 复杂度；CG 变体用共轭梯度，\(O(\log(1/\epsilon))\) 复杂度（与 AdaGrad-Norm 理论匹配）。CG 变体的 Hessian-向量积复杂度为 \(O(1/\epsilon)\)，比竞争者的 \(O(1/\epsilon^2)\) 更优
设计动机：CG 变体在理论和实验上都更优——收敛更快且超梯度估计误差更低
Retraction 映射支持:
做什么：用 retraction 替代指数映射降低计算成本
核心思路：Algorithm 3 支持一般的 retraction 映射（不要求是指数映射），保持相同 \(O(1/\epsilon)\) 收敛率
设计动机：指数映射在某些流形（如 Stiefel 流形）上计算昂贵，retraction 是实用的替代

损失函数 / 训练策略¶

收敛率：\(O(1/\epsilon)\) 找 \(\epsilon\)-稳定点（匹配非自适应方法）
假设：下层目标测地强凸

实验关键数据¶

主实验¶

实验	AdaRHD-CG	RHGD-50	RHGD-20
矩阵对齐（Stiefel-SPD）	最快收敛，最低误差	慢	更慢
AFEW 鲁棒性（SPD 网络）	85% 验证准确率，最短时间	步长 5/1/0.5 完全失败	步长 0.1 才工作

消融/鲁棒性分析¶

初始步长	AdaRHD	RHGD
0.2	✓ 收敛	—
1.0	✓ 收敛	✗ 失败
2.0	✓ 收敛	—
10.0	✓ 收敛	—
20.0	✓ 收敛	—
RHGD 0.05	—	✓ 唯一工作

关键发现¶

AdaRHD 对初始步长极其鲁棒——0.2 到 20.0 范围内都收敛，RHGD 只在 0.05 工作
CG 变体比 GD 变体超梯度估计误差更低——收敛更快
标准差更低——说明自适应步长使训练更稳定

亮点与洞察¶

首个无参数黎曼双层优化算法：消除了对问题特定参数的依赖是重要的实用进步
鲁棒性差距巨大：AdaRHD 在 100× 的步长范围内工作，RHGD 需要精确调参
CG 变体的二阶复杂度更优：\(O(1/\epsilon)\) vs \(O(1/\epsilon^2)\) Hessian-向量积

局限性 / 可改进方向¶

仅处理确定性 RBO + 测地强凸下层——非强凸和 PL 条件目标未覆盖
与非自适应方法相比梯度/Hessian 复杂度有 \(1/\epsilon\) 的额外因子——自适应性的代价
未处理随机/mini-batch 设置——实际大规模问题通常使用随机梯度
仅在中小规模问题上验证——SPD 和 Stiefel 流形实验维度 ≤50
单循环算法（更高效）的设计留作未来工作
超梯度估计的误差界在某些流形上可能更松——需要流形特定的分析
未与欧几里得空间的自适应双层方法做运行时间直接对比
Retraction 映射的选择对收敛速度的影响未量化

评分¶

新颖性: ⭐⭐⭐⭐ 首个自适应黎曼双层优化算法，理论贡献稳实
实验充分度: ⭐⭐⭐ 两个实验（矩阵对齐+AFEW），规模较小但鲁棒性验证充分
写作质量: ⭐⭐⭐⭐⭐ 理论推导严谨，复杂度分析完整
价值: ⭐⭐⭐⭐ 使黎曼双层优化在实践中更可用——消除了参数调节的主要障碍