RBDA:黎曼双层下降聚合

论文《Riemannian Bilevel Optimization with Gradient Aggregation》算法 1 的流程,右侧标注每个环节承担的卖点。

输入:x⁰ ∈ 𝓜,y₀ ∈ 𝓝,聚合权重 μ ∈ (0,1) 预算 K、BB 阶段 K₁ ≤ K(上限 θ)、步长 s、衰减 ρ、外层步 η r ← 0 外层循环(while 未收敛) 内层 k = 0 … K−1(从 y₀ 出发,整条轨迹被记录) 取两个梯度:下层 𝒢y f(xʳ, yₖ) 与上层 𝒢y F(xʳ, yₖ) 混合方向 gₖ = (1−μ)·𝒢y f + μ·(αₖ/βₖ)·𝒢y F μ 把上层的选择信号注入下层更新(式 A:agg 的方向) 1 ≤ k ≤ K₁ ? (BB 阶段) 是 sₖ = BB 步 混合割线、截断于 θ 式 (A:ss1) 否 sₖ = s · pₖ pₖ = 1/(1+ρk) 常数比,式 (A:ss2) 更新 yₖ₊₁ = Ryₖ(−sₖ · gₖ)(聚合更新,式 A:agg) 迭代点存入轨迹 {y₀, …, yₖ₊₁},供反向传播使用 更新长度 ≤ 停机阈值? 规则 (b):stop_rtol × 本轮首步长度 否 · k ← k+1 是,或 k = K(预算用尽) → 内层终点 y_K 轨迹 {yₖ} 超梯度 𝒢̃φK(xʳ) ← 反向传播 F(xʳ, y_K) 沿记录的整条内层轨迹逐步回溯(式 A:HG2) 外层更新 xʳ⁺¹ = Rxʳ(−η · 𝒢̃φK(xʳ)) r ← r+1 收敛? 否:下一轮 协议:热启动 y₀ ← 上一轮 y_K 是 输出 (xʳ, y_K) 聚合 = 选择 非 LLS 时基线沿被忽略的块 没有梯度信号;μ>0 的混合方向 在下层解集内选中 optimistic 解(§5.2) BB 阶段 = 速度 理论覆盖常数步,BB 只为提速; 实测把内层步数压到基线以下(§5.1) 常数比 = 单层速度 内层是固定混合目标 (1−μ)f+μF 的梯度法:LLS 下线性收缩, S(ε)=⌈8ζκμ log(d₀/ε)⌉(推论 5); 代价:极限点偏离下层解集 O(μ) 无 Hessian、无线性求解 超梯度只是一次反向传播; 隐式族在此处要解 CG/NS/ Hessian 逆的线性系统(表 tab:cost)
RBDA(算法 1):外层在 𝓜(实验中 Stiefel 流形)上沿超梯度更新,内层在 𝓝(实验中 SPD 流形)上跑聚合更新——前 K₁ 步用混合割线的 BB 步长,其余用常数比调度 pₖ,规则 (b) 允许提前停机;超梯度由整条内层轨迹的反向传播给出, 不出现 Hessian 或线性求解。虚线为数据流,实线为控制流。

记号

x ∈ 𝓜,y ∈ 𝓝
上、下层变量;实验中 𝓜 = Stiefel(W),𝓝 = SPD(M),𝓝 要求 Hadamard(分析)
f,F
下层与上层目标;φ(x) = F(x, y*(x)) 为值函数
μ
聚合权重(实验:synthetic 0.1,nonlls 0.3,超清洗 0.5);μ=0 退化为普通下层更新
pₖ = 1/(1+ρk)
常数比调度,上下两项共用同一乘子(ρ=0.01);diminishing 调度只是分析里的精确极限
K,K₁,θ
内层预算、BB 阶段长度(实验取 K/2)、BB 步上限(黎曼路线 10,欧氏路线 1/L_E)
s,η
内层基础步长与外层步长
R,𝒢
retraction(分析用指数映射)与黎曼梯度
规则 (b)
热启动协议的停机:阈值 = stop_rtol × 本次内层首步更新长度,每外层步重算