2025-11-21T05:43:14.438076

An Adaptive Algorithm for Bilevel Optimization on Riemannian Manifolds

Shi, Xiao, Jiang

Existing methods for solving Riemannian bilevel optimization (RBO) problems require prior knowledge of the problem's first- and second-order information and curvature parameter of the Riemannian manifold to determine step sizes, which poses practical limitations when these parameters are unknown or computationally infeasible to obtain. In this paper, we introduce the Adaptive Riemannian Hypergradient Descent (AdaRHD) algorithm for solving RBO problems. To our knowledge, AdaRHD is the first method to incorporate a fully adaptive step size strategy that eliminates the need for problem-specific parameters in RBO. We prove that AdaRHD achieves an $\mathcal{O}(1/Îµ)$ iteration complexity for finding an $Îµ$-stationary point, thus matching the complexity of existing non-adaptive methods. Furthermore, we demonstrate that substituting exponential mappings with retraction mappings maintains the same complexity bound. Experiments demonstrate that AdaRHD achieves comparable performance to existing non-adaptive approaches while exhibiting greater robustness.

academic

An Adaptive Algorithm for Bilevel Optimization on Riemannian Manifolds

基本信息

论文ID: 2504.06042
标题: An Adaptive Algorithm for Bilevel Optimization on Riemannian Manifolds
作者: Xu Shi, Rufeng Xiao, Rujun Jiang (复旦大学数据科学学院)
分类: math.OC (优化与控制)
发表会议: NeurIPS 2025 (第39届神经信息处理系统会议)
论文链接: https://arxiv.org/abs/2504.06042

摘要

现有求解黎曼双层优化(RBO)问题的方法需要预先知道问题的一阶、二阶信息以及黎曼流形的曲率参数来确定步长，这在参数未知或计算不可行时带来了实际限制。本文提出了自适应黎曼超梯度下降(AdaRHD)算法来求解RBO问题。据我们所知，AdaRHD是第一个在RBO中采用完全自适应步长策略的方法，消除了对问题特定参数的需求。我们证明AdaRHD达到了找到ε-稳定点的O(1/ε)迭代复杂度，与现有非自适应方法的复杂度相匹配。此外，我们证明用收缩映射替代指数映射仍能保持相同的复杂度界。实验表明AdaRHD在获得与现有非自适应方法相当性能的同时表现出更强的鲁棒性。

研究背景与动机

问题背景

双层优化问题在机器学习领域有广泛应用，包括强化学习、元学习、超参数优化、对抗学习等。黎曼双层优化(RBO)是双层优化在黎曼流形上的扩展，其一般形式为：

$\min_{x \in \mathcal{M}_x} F(x) := f(x, y^*(x))$ $\text{s.t. } y^*(x) = \arg\min_{y \in \mathcal{M}_y} g(x,y)$

其中 $\mathcal{M}_x, \mathcal{M}_y$ 是黎曼流形， $f,g$ 是光滑函数， $g(x,y)$ 关于 $y$ 是测地强凸的。

现有方法的局限性

参数依赖性：现有RBO方法(如RHGD、RieBO等)需要预先知道强凸参数、Lipschitz常数、曲率参数等来确定步长
实用性限制：这些参数在实际应用中往往难以估计或计算代价过高
鲁棒性不足：固定步长策略对初始化和问题条件敏感

研究动机

本文的核心动机是设计一个完全自适应的RBO算法，能够：

无需预先知道问题特定参数
自动调整步长以适应问题特性
保持与非自适应方法相当的理论复杂度
提供更强的实用鲁棒性

核心贡献

首个自适应RBO算法：提出AdaRHD，是第一个采用完全自适应步长策略的黎曼双层优化算法，消除了对强凸性、Lipschitz常数和曲率参数的依赖
理论复杂度匹配：证明AdaRHD达到O(1/ε)迭代复杂度找到ε-稳定点，与现有非自适应方法复杂度相匹配
收缩映射扩展：证明用计算效率更高的收缩映射替代指数映射仍能保持相同的复杂度保证
实验验证：在多个RBO问题上验证了算法的有效性和鲁棒性，包括黎曼超表示学习和鲁棒优化问题

方法详解

任务定义

考虑黎曼双层优化问题：

上层问题：在流形 $\mathcal{M}_x$ 上最小化 $F(x) = f(x, y^*(x))$
下层问题：对给定 $x$ ，在流形 $\mathcal{M}_y$ 上求解 $y^*(x) = \arg\min_y g(x,y)$
约束： $g(x,y)$ 关于 $y$ 测地强凸， $f$ 不要求凸性

核心技术：黎曼超梯度

黎曼超梯度定义为： $G_F(x) = G_x f(x, y^*(x)) - G^2_{xy}g(x, y^*(x))[H^{-1}_y g(x, y^*(x))[G_y f(x, y^*(x))]]$

由于精确计算困难，使用近似黎曼超梯度： $\hat{G}_F(x, \hat{y}, \hat{v}) = G_x f(x, \hat{y}) - G^2_{xy}g(x, \hat{y})[\hat{v}]$

其中 $\hat{y}$ 是下层问题的近似解， $\hat{v}$ 是线性系统的近似解。

AdaRHD算法架构

算法1：AdaRHD主要步骤

下层问题求解：使用自适应梯度下降
- 步长更新： $b^2_{k+1} = b^2_k + \|G_y g(x_t, y^k_t)\|^2$
- 迭代更新： $y^{k+1}_t = \text{Exp}_{y^k_t}(-\frac{1}{b_{k+1}} G_y g(x_t, y^k_t))$
线性系统求解：两种策略
- 梯度下降：类似下层问题的自适应步长
- 共轭梯度：使用切空间共轭梯度方法
上层更新：自适应超梯度下降
- 步长更新： $a^2_{t+1} = a^2_t + \|\hat{G}_F(x_t, y^{K_t}_t, v^{N_t}_t)\|^2$
- 迭代更新： $x_{t+1} = \text{Exp}_{x_t}(-\frac{1}{a_{t+1}} \hat{G}_F(x_t, y^{K_t}_t, v^{N_t}_t))$

技术创新点

累积梯度范数策略：采用"累积黎曼梯度范数的倒数"作为自适应步长，无需预知问题参数
三层自适应：对上层、下层和线性系统都采用自适应步长，形成完整的自适应框架
收缩映射优化：提供使用收缩映射替代指数映射的版本，降低计算复杂度
理论保证：严格的收敛分析，处理黎曼流形的几何结构带来的技术挑战

实验设置

数据集和问题

简单矩阵相似性问题：在Stiefel流形和SPD流形上的优化
- 数据规模：n=100和n=1000
- 参数设置：d=50, r=20, λ=0.01
深度超表示学习：AFEW情感识别数据集
- 3层SPD网络架构
- 7个情感类别，1747个训练样本
- 不平衡类别分布
鲁棒优化问题：
- 鲁棒Karcher均值问题
- 鲁棒最大似然估计问题