RBDA · Baseline Feasibility

RF²SA 与 AdaRHD 可实现性

两个候选基线的算法流程、所需算子对照 RBDA 仓库现状、以及在我们三个实验问题上的适用范围。青铜色标记 RF²SA（全一阶），群青色标记 AdaRHD（自适应二阶）。

先说结论：两个都能在 RBDA 仓库里实现，所需算子没有一件是缺的。RF²SA 只要一阶梯度和指数映射（约半天工作量），但要调的量不少，且理论步长依赖 $\mu_g$、$l_{f,1}$、$l_{g,1}$ 等未知常数；AdaRHD 的二阶机件（HVP、切空间 CG、交叉二阶）全可从现有基线复用（约一天），标称免调参，但内层停机容差和初始累积量仍要定。两篇的理论都以下层测地强凸（LLS）为前提——所以它们作为基线的主场只有 §5.1，在 §5.2 与超清洗上都出理论范围。

RF²SA（Dutta–Cheng–Sra, arXiv 2024）

全一阶 · 拉格朗日乘子递增 · 单环可行

只需 $f,g$ 的黎曼梯度 + 两个流形上的 Exp——仓库全有
维护两条下层序列（$y$ 追 $y_\lambda^*$、$z$ 追 $y^*$），每外层步下层代价约 2 倍
超参数 6 个：$\alpha_k,\gamma_k,\delta_k,\xi,T,\lambda_0$；理论取值全系于未知常数,实际要扫
确定性复杂度 $\tilde O(\epsilon^{-3/2})$,劣于隐式族与我们的阶
工作量:约半天(新方法键 + λ 调度 + config 组)

AdaRHD（Shi–Xiao–Jiang, NeurIPS 2025）

自适应步长 · 隐式超梯度 · GD/CG 两变体

= RHGD-CG 的免调参版:三层循环共用 AdaGrad-Norm 步长 $1/\sqrt{\sum\|\cdot\|^2}$
二阶机件与我们的 cg/hinv 基线同类,HVP/CG/交叉二阶全可复用
$y$ 与 $v$ 都热启动($v$ 要平行移动,SPD 有闭式)
确定性 $O(1/\epsilon)$,免先验常数;但初期步长过大易发散(论文自认难点)
工作量:约一天(累积器 + 双容差停机 + v 热启动)

两个更正与一个共同边界：方法名是 AdaRHD（Adaptive Riemannian Hypergradient Descent，变体 AdaRHD-GD / AdaRHD-CG），不是 AdaRHG；Dutta 一篇至今只有 arXiv v1，AdaRHD 已被 NeurIPS 2025 接收。两篇的收敛目标都是值函数 $\varphi$ 的 $\epsilon$-驻定点、假设都含下层 $\mu_g$-测地强凸——非 LLS 场景（§5.2、超清洗）对两者都是界外。

1RF²SA：拉格朗日化的全一阶方法

重构优化的是什么

把双层问题改写成单层约束问题 $\min_{x,y} f(x,y)$ s.t. $g(x,y)-g^*(x)\le 0$（$g^*(x)=\min_y g(x,y)$），对拉格朗日函数 $$\mathcal L_\lambda(x,y)=f(x,y)+\lambda\bigl(g(x,y)-g^*(x)\bigr)$$ 做黎曼梯度下降。$g^*(x)$ 的梯度靠一条辅助序列 $z\approx y^*(x)$ 来估计（$\mathrm{grad}\,g^*(x)=\mathrm{grad}_x g(x,y^*(x))$，Danskin）。乘子 $\lambda_k$ 随外层迭代递增：偏差是 $O(1/\lambda)$（其 Lemma 1：$|\mathrm{grad}F-\mathrm{grad}\mathcal L^*_\lambda|\le C_\lambda/\lambda$），但 $\lambda$ 太大又损害光滑性——增长率的选择正是这篇的主要理论贡献。

Algorithm 1 · RF²SA（照原文逐行转写）

输入：步长列 $\{\alpha_k,\gamma_k\}$、乘子增量列 $\{\delta_k\}$、内环步数 $T$、步长比 $\xi$；初值 $\lambda_0,x_0,y_0,z_0$。

对外层 $k=0,\dots,K-1$：
内环 $t=0,\dots,T-1$（$T=1$ 即完全单环）：
$z$ 步（追 $y^*(x_k)$，纯下层下降）：$\;z_{k,t+1}=\mathrm{Exp}_{z_{k,t}}\!\bigl(-\gamma_k\,\mathrm{grad}_y g(x_k,z_{k,t})\bigr)$
$y$ 步（追 $y^*_{\lambda_k}(x_k)$）：$\;y_{k,t+1}=\mathrm{Exp}_{y_{k,t}}\!\bigl(-\alpha_k\bigl[\mathrm{grad}_y f(x_k,y_{k,t})+\lambda_k\,\mathrm{grad}_y g(x_k,y_{k,t})\bigr]\bigr)$
收尾：$z_{k+1}=z_{k,T}$，$y_{k+1}=y_{k,T}$
$x$ 步：$\;x_{k+1}=\mathrm{Exp}_{x_k}\!\bigl(-\xi\alpha_k\bigl[\mathrm{grad}_x f(x_k,y_{k+1})+\lambda_k\bigl(\mathrm{grad}_x g(x_k,y_{k+1})-\mathrm{grad}_x g(x_k,z_{k+1})\bigr)\bigr]\bigr)$
乘子递增：$\lambda_{k+1}=\lambda_k+\delta_k$

每个外层步的 oracle 消耗：$T$ 次 $\mathrm{grad}_y g$（$z$ 侧）+ $T$ 次 $(\mathrm{grad}_y f+\mathrm{grad}_y g)$（$y$ 侧）+ 1 次 $\mathrm{grad}_x f$ + 2 次 $\mathrm{grad}_x g$。无 Hessian、无移动、无线性求解。

条件假设与步长（Thm 2 的实际含义）

假设集与 Han/Li–Ma 同族：$f,g$ 一阶 Lipschitz 光滑（沿平行移动定义）、$g$ 的 Hessian Lipschitz、$g(\bar x,\cdot)$ 对每个 $\bar x$ 都 $\mu_g$-测地强凸、梯度有界。定理 2 的步长条件把所有超参数拴在未知常数上：$\lambda_0\ge 2l_{f,1}/\mu_g$，$\beta_k:=\alpha_k\lambda_k\le\gamma_k\le\min\{\tfrac1{4l_{g,1}},\tfrac1{4T\mu_g}\}$，$\alpha_k\le\min\{\tfrac1{8l_{f,1}},\tfrac1{2\xi l_{F,1}}\}$，$\delta_k/\lambda_k\le T\mu_g\beta_k/16$。也就是说："全一阶"免掉的是二阶 oracle，不是常数先验——这正是 AdaRHD 那篇 Table 1 点名批评的地方。实现时这些一律变成扫描量。确定性情形 $\mathbb E\|\mathrm{grad}F\|^2$ 以 $\tilde O(K^{-2/3})$ 下降（$\tilde O(\epsilon^{-3/2})$），劣于隐式族的 $O(1/\epsilon)$。

映射对照 RBDA 仓库

RF²SA 需要	仓库现状	缺口
黎曼梯度 $\mathrm{grad}_y f,\mathrm{grad}_y g,\mathrm{grad}_x f,\mathrm{grad}_x g$	autograd + 度量转换，所有现有方法在用	无
两个流形上的 Exp	SPD 精确指数映射已实现（§5 下层即用它）；超清洗的欧氏头平凡	无
辅助序列 $z$	就是我们 group10 加的 `rgd`（μ=0 聚合内层）的一份拷贝	封装
$\lambda_k$ 调度 + 步长比 $\xi$	无对应物	新写（小）
config 组（$\lambda_0$、增长率、$\alpha,\gamma,\xi,T$ 扫描）	`config.py` 加方法键 `rf2sa` + 调参组	新写（小）

观察：RF²SA 的 $y$ 步就是权重趋零的聚合更新

把 $y$ 步的方向归一化：$\mathrm{grad}_y f+\lambda_k\,\mathrm{grad}_y g\propto\mu_k^{\mathrm{eff}}\,\mathrm{grad}_y f+(1-\mu_k^{\mathrm{eff}})\,\mathrm{grad}_y g$，其中 $\mu_k^{\mathrm{eff}}=\frac{1}{1+\lambda_k}\to 0$。也就是说 RF²SA 在 $y$ 侧跑的是一个调度递减的聚合内层（与 BDA 的 $\alpha_k\to0$ 同型），区别在它多了一条 $z$ 序列和 $x$ 步里的值函数修正项。这给 related work 一个干净的说法：拉格朗日路线在下层侧与递减调度聚合同构，我们的 constant 调度与之的差别（选择信号不衰减）原封不动地适用。写进论文前建议先跑一下验证行为。

边界在三个实验上

问题	能不能跑	说明
§5.1 LLS 合成	✓ 主场	假设全满足；与 RBDA 同属一阶 oracle 类，是最公平的一阶对照；复杂度阶劣于隐式族，时间对比预期偏慢
§5.2 忽略块	机械可跑,理论界外	$\mu_g=0$ 使 $\lambda_0\ge 2l_{f,1}/\mu_g$ 无定义；$z$ 序列在忽略块上冻结（同 `rgd`），$y$ 侧的选择信号随 $\mu_k^{\mathrm{eff}}\to0$ 衰减（BDA 型）；$x$ 步的修正项是"两个趋同量之差 × 发散的 $\lambda_k$"，数值上脆。若报告须标注 off-label
§5.4 超清洗	机械可跑,理论界外	下层退化同上；且递减调度对 constant 的对照已由 BDA 承担，再加 RF²SA 信息增量有限

2AdaRHD：免先验常数的自适应超梯度法

定位它是什么

本质是 RHGD-CG/GD（Han 框架的隐式超梯度路线）的免调参版：三层循环全部用同一种 AdaGrad-Norm 步长——累积平方梯度范数、取倒数平方根——从而不需要预先知道 $\mu_g$、Lipschitz 常数、曲率参数。代价换来的结论：确定性 $O(1/\epsilon)$ 迭代复杂度与非自适应方法同阶，且换成一般收缩映射不改阶（其 Algorithm 3）。

Algorithm 1 · AdaRHD（按你笔记里的整理转写；-GD / -CG 二选一）

输入：容差 $\epsilon_y,\epsilon_v$，初始累积量 $a_0,b_0,c_0$；初值 $x_0,y_0,v_0$。

对外层 $t=0,\dots,T-1$：
热启动：$y_t^0=y_{t-1}^{K_{t-1}}$；$v_t^0=\mathcal P(v_{t-1}^{N_{t-1}})$（平行移动到新基点）
内层 1（解下层）：直到 $\|\mathrm{grad}_y g(x_t,y_t^k)\|^2\le\epsilon_y$： $$b_{k+1}^2=b_k^2+\|\mathrm{grad}_y g\|^2,\qquad y_t^{k+1}=\mathrm{Exp}_{y_t^k}\!\Bigl(-\tfrac{1}{b_{k+1}}\mathrm{grad}_y g(x_t,y_t^k)\Bigr)$$
内层 2（解线性系统 $\mathcal H_y g[v]=\mathrm{grad}_y f$）：
-GD：对二次子问题 $R(v)=\tfrac12\langle v,\mathcal H_y g[v]\rangle-\langle v,\mathrm{grad}_y f\rangle$ 做同款自适应下降（累积量 $c_n$），直到 $\|\nabla_v R\|^2\le\epsilon_v$；
-CG：切空间共轭梯度直接解
超梯度：$\widehat{\mathcal G}F=\mathrm{grad}_x f(x_t,y_t^{K_t})-\mathcal G^2_{xy}g(x_t,y_t^{K_t})[v_t^{N_t}]$
外步：$a_{t+1}^2=a_t^2+\|\widehat{\mathcal G}F\|^2$，$\;x_{t+1}=\mathrm{Exp}_{x_t}\!\bigl(-\tfrac{1}{a_{t+1}}\widehat{\mathcal G}F\bigr)$

oracle 类别与我们的 cg 基线相同：下层梯度、HVP（内层 2 每步一次）、交叉二阶一次、上层梯度一次；额外的只有平行移动一次（$v$ 热启动）。

映射对照 RBDA 仓库

AdaRHD 需要	仓库现状	缺口
HVP $\mathcal H_y g[v]$	`main.py` 的 `hvp`（`cg`/`ns` 基线在用）	无
切空间 CG（-CG 变体）	`cg_solve` 现成	无
交叉二阶 $\mathcal G^2_{xy}g[v]$	`ift_hypergradient` 里已实现	无
SPD 平行移动（$v$ 热启动）	BB 步的割线已在做移动，闭式可复用	无
AdaGrad-Norm 累积器 ×3 + 双容差停机	无对应物	新写（小）
-GD 变体的自适应内层 2	无对应物（若只做 -CG 可跳过）	可选

风险两处要留意

其一，初期发散。论文自己把"自适应步长在初始迭代容易因步长过大而发散"列为三大难点之一（$b_0$ 小 → 第一步 $1/b_1$ 很大）。这与我们附录 C 观察到的"SPD 上 exp 更新在大步长下先塌掉"是同一处敏感点——初始累积量 $a_0,b_0,c_0$ 名义上不是问题常数，实际上就是新的调参量。其二，协议对齐。它的内层按容差停，我们的比较按固定内层预算 $K$ 计时；好在它的热启动 + 容差停机与我们主协议（热启动 + 规则 (b)）形态相近，对齐成本低，但"按容差还是按预算"要在跑之前定一次，否则时间对比没有共同尺子。

边界在三个实验上

问题	能不能跑	说明
§5.1 LLS 合成	✓ 主场	就是隐式族的自适应版；作为"免调参对照"很有信息量——我们的卖点之一是 BB 免去步长调参，AdaRHD 是同一诉求的另一条路线，同台时间对比正中要害
§5.2 忽略块	✗ 按设计失效	$\mathcal H_y g$ 沿忽略块奇异：内层 2 解的是奇异线性系统，CG 停滞或发散——与我们对 `hinv`/`cg` 的预言完全同型；如果要演示"自适应救不了隐式公式"，可以跑给读者看，但结论可预期
§5.4 超清洗	✗ 同上	无正则下层 Hessian 奇异；隐式族在此已实测掉点，AdaRHD 不改变这一机制

3横向对照（含现有基线）

方法	oracle 类别	自适应	确定性复杂度	LLS 假设	§5.1	§5.2	hc
HINV / CG / NS（已有）	二阶（Hessian 逆/线性解）	✗	$O(1/\epsilon)$	必需	✓	✗	✗
AD（已有）	一阶展开 + AD	✗	—	理论上必需	✓	✗	跑但掉点
RF²SA（候选）	纯一阶	✗（常数进步长）	$\tilde O(\epsilon^{-3/2})$	必需（$\lambda_0$ 依赖 $\mu_g$）	✓	off-label	off-label
AdaRHD（候选）	二阶（HVP + CG）	✓	$O(1/\epsilon)$	必需	✓	✗	✗
RBDA（我们）	纯一阶 + AD	BB（内层）	内层 $O(\kappa_\mu\log\tfrac1\epsilon)$/次超梯度	不需要	✓	✓	✓

复杂度均为各文自报的 $\epsilon$ 阶（略去条件数与曲率常数）；RF²SA/AdaRHD 的目标是 $\varphi$ 的 $\epsilon$-驻定点，与我们"每次超梯度的内层计数"不是同一种量，只作 oracle 类别与可行性对照，不能并表比数。

4建议

若要加基线，顺序与范围

先 RF²SA、只进 §5.1。理由：与 RBDA 同属一阶 oracle 类，是 tab:related 里唯一还没被实验触及的一行；实现半天；预期结论（复杂度阶劣、λ 调度敏感）对我们有利且可解释。照规矩先开调参组（λ₀、增长率、ξ 扫描）再进展示组。

AdaRHD 次之、也只进 §5.1。作为"免调参"的对照与我们的 BB 卖点正面相关，-CG 变体一天可成；§5.2/hc 不必跑——它失效的机制与 hinv/cg 完全相同，跑了只是重复已有结论（除非想要一句"自适应步长救不了隐式公式"的实测注脚）。

两件事先定再动手：①内层按预算还是按容差（协议尺子）；②这两个基线进正文还是只进附录——tab:related 的内容方向本来就在批注 #32 的待商榷清单里，可以一起定。

＊依据

S. Dutta, X. Cheng, S. Sra, "Riemannian bilevel optimization", arXiv:2405.15816 (v1, 2024)。算法与条件取自原文 Algorithm 1、Assumptions 1–5、Lemma 1–2、Theorem 2(pp. 5–9,PDF 见 Trilium 论文列表)。
X. Shi, R. Xiao, R. Jiang, "An adaptive algorithm for bilevel optimization on Riemannian manifolds", NeurIPS 2025(arXiv:2504.06042 v3)。流程取自 Trilium 笔记「An Adaptive Algorithm …：AdaRHD」整理的 Algorithm 1(含流程图子笔记)。
仓库现状:RBDA/main.py(cg_solve / ns_solve / lyap_solve / ift_hypergradient / hvp / spd_* / *_bb_step)。
Trilium 相关笔记:「Riemannian Bilevel Optimization(Dutta …):无需超梯度的全一阶方法 RF²SA」「An Adaptive Algorithm …(Shi …):AdaRHD」「Dutta_RBLO」(其他文章的证明)。