RBDA 证明路线报告

1. 问题与两种情形

双层问题。上层变量 $x\in\mathcal M$,下层变量 $y\in\mathcal N$,均为完备黎曼流形,$F,f:\mathcal M\times\mathcal N\to\mathbb R$ 为 $C^2$:

固定 $x$ 后记 $\psi(y):=f(x,y)$,$\Psi(y):=F(x,y)$。

两种情形的分界(假设 A1):

• LLS 情形:$\psi$ 强 g-凸 $\Rightarrow$ $\mathcal S(x)=\{y^*(x)\}$ 单点,$\varphi(x)=F(x,y^*(x))$ 是通常的值函数,隐式超梯度公式(隐函数定理那条封闭表达式)可用。
• 非 LLS 情形:$\mathcal S(x)$ 可以是正维数的测地全凸子流形(连续对称性、只依赖低维量等)。此时 $\varphi$ 取乐观值 $\varphi(x)=\min_{y\in\mathcal S}\Psi(y)$,记 $\mathcal S^{\mathrm{opt}}(x)=\arg\min_{y\in\mathcal S}\Psi(y)$。聚合更新的意义:在 $\mathcal S(x)$ 内部做出上层偏好的选择,这是纯下层求解做不到的。

被分析的对象。固定 $x$,内层迭代(指数映射形式):

两种系数安排:

• 递减比($\alpha_k\to0$,$\beta_k\ge\underline\beta\gt 0$):选择信号渐弱但精确,收敛到 $\mathcal S^{\mathrm{opt}}$(定理 1、2)——这是分析里的精确极限;
• 常数比($\alpha_k=\beta_k=p_k$):算法 1 实际运行的方式,等价于在固定混合目标 $\psi_\mu=(1-\mu)\psi+\mu\Psi$ 上做单层梯度下降,快、但带 $O(\mu)$ 偏差(命题 3)。

范围声明(论文的「范围注记」):所有结论只针对固定 $x$ 的内层动态;外层序列 $\{x^r\}$、有限步估计量 $\widetilde{\mathcal G}\varphi_K$ 都不在保证之内,因此没有端到端复杂度,LLS 复杂度(第 6 节)是「固定 $x$ 下单次超梯度的成本」。

2. 基础几何工具

全部收敛分析建立在四件几何事实上:

1. Hadamard 流形:$\mathcal N$ 完备、单连通、截面曲率 $\in[\kappa^-,0]$。于是 $\operatorname{Exp}$/$\operatorname{Exp}^{-1}$ 全局定义,$d(\cdot,\cdot)$ 由测地线实现,$\|\operatorname{Exp}^{-1}_y(y')\|=d(y,y')$。
2. g-凸与 g-光滑的一阶不等式: $$f(y')\ge f(y)+\langle\mathcal G f(y),\operatorname{Exp}^{-1}_y(y')\rangle\ \Big(+\tfrac{C_f}{2}d^2\ \text{强凸时}\Big),\qquad f(y')\le f(y)+\langle\mathcal G f(y),\operatorname{Exp}^{-1}_y(y')\rangle+\tfrac{L_f}{2}d^2.$$
3. 比较不等式(zhang2016first-order):在直径 $D$ 的紧 g-凸集 $\mathcal K$ 上存在 $\zeta=\zeta(\kappa^-,D)\ge1$($\kappa^-\to0$ 时 $\zeta\to1$),使 $$d^2(\operatorname{Exp}_y(v),y')\ \le\ d^2(y,y')-2\langle v,\operatorname{Exp}^{-1}_y(y')\rangle+\zeta\|v\|^2. \tag{2}$$ 关键观察:曲率放大因子 $\zeta$ 只乘在 $\|v\|^2$(步长平方项)上,不乘首项距离,因此用步长条件一次性压住即可,不随迭代累积。这是整套证明能在负曲率下照常进行的原因。
4. 度量投影:Hadamard 流形上,到闭 g-凸集的投影 $P_{\mathcal C}$ 单值且非扩张。用于:$P_{\mathcal S}$(定义 $u_k^-$ 的控制、偏差量化)、$P_{\mathcal K}$(强制迭代点留在 $\mathcal K$ 内)。

3. 假设体系与各自的用途

关于 $\mathcal K$-包含性不是隐藏假设(论文的「包含性注记」,三种落实方式):

• (i) 自举球:固定 $\bar y\in\mathcal S^{\mathrm{opt}}$、半径 $\rho$,把全部常数在闭测地球 $\bar B(\bar y,\rho)$ 上读出;拟 Fejér 不等式(后文式 (5) 的形式 $d^2(y_{k+1},\bar y)\le d^2(y_k,\bar y)+C_3\alpha_k^2$)加上显式小性条件 $d^2(y_0,\bar y)+C_3\sum\alpha_k^2\le\rho^2$ 归纳可得迭代点永不出球。投影点的包含由 $P_{\mathcal S}$ 非扩张 + $P_{\mathcal S}(\bar y)=\bar y$ 免费得到。
• (ii) 投影:更新后复合 $P_{\mathcal K}$,非扩张性使所有证明原样通过。也是 BB 阶段后 $y_{K_1}\in\mathcal K$ 的唯一保证手段。
• (iii) 强制性:常数比时更新是 $\psi_\mu$ 上的单调下降,迭代点不出初始下水平集;$\psi_\mu$ 强制(coercive)时该集紧。

4. 证明链依赖图

式(2) 比较不等式 + g-凸一阶不等式 + 梯度界 ‖Gψ(y_k)‖² ≤ 2L_f·g_k
        │
        ▼
引理 6 一步聚合估计 式(3) —— 一切的公共起点
        │
        ├─[递减比: α_k→0, Σα_k=∞, Σα_k²<∞, β_k≥β̲>0; s≤1/(4ζ(1-μ)L_f); 需 G1]
        │       ▼
        │  定理 1  LLOCP + ULOCP + 全列收敛 y_k → ȳ ∈ S^opt   [经式(4)、式(5)]
        │       │
        │       ▼ [再加 G2; 取 α_k=(k+1)^{-θ}, θ∈(1/2,1)]
        │  定理 2  滑动窗口内好点 j_k 的四条速率
        │       ▼
        │  内层复杂度  k = O(ε^{-p/(1-θ)})  (到 S^opt 的距离 ≤ ε)
        │
        └─[常数比: α_k=β_k=p_k; Σp_k=∞, Σp_k²<∞ 或 p_k≡1, s<1/(ζL_μ)]
                ▼
          命题 3  = ψ_μ 上的单层下降 式(6): O(1/k) 值速率 + 单点收敛
                │              + O(μ) 偏差(三条量化不等式)
                │  偏差注记: 偏差在常数比下本质不可去除(反例精确到 μ);
                │  上层可分 ⇒ 平坦方向选择精确; 跨外层退火 μ_k↓0 ⇒ 沿 Tikhonov 路径回到精确
                │
                ├─[+A1 强 g-凸] 推论 4  线性率至 O(α_k²) 扰动(Ψ 的凸性不需要)
                │                 常数比时留下 μ² 量级的底,引出 ↓
                └─[+混合强 g-凸 m_μ] 推论 5  无底的收缩 式(7): 因子 1 − 1/(4ζκ_μ)
                          ▼
                    步数 式(8): S_RBDA(ε) = ⌈8ζκ_μ log(d₀/ε)⌉,  偏差 ≤ 2Mμ/((1-μ)C_f)
                          ▼
                    比值 式(9): S_RBDA/S₀ → κ_μ/κ_f (ε↓0);  退火 μ(ε) ⇒ 精度 2ε 且 S_RBDA ~ S₀
                          ▼
                    成本表: 与 HINV/CG/NS/AD 的单次超梯度成本对照

5. 主线结果与证明骨架

5.1 引理 6(一步聚合估计)

骨架。比较不等式 (2) 用在 $v_k=-(1-\mu)s\beta_k\mathcal G\psi-\mu s\alpha_k\mathcal G\Psi$;两个内积分别用 $\psi,\Psi$ 的 g-凸一阶不等式;平方项用 $(a+b)^2\le2a^2+2b^2$ 拆开并以 $\|\mathcal G\Psi\|\le G_F$ 封顶;梯度界来自沿试探测地线 $t\mapsto\operatorname{Exp}_{y_k}(-t\,\mathcal G\psi/L_f)$ 的 $L_f$-光滑下降不等式(试探点不要求在 $\mathcal K$ 内,光滑性是全流形陈述——这是 A3 写在全流形上的原因之一)。

5.2 定理 1(递减比:选出乐观解)

骨架(四步,固定 $y'\in\mathcal S^{\mathrm{opt}}$,记 $\Phi_k=d^2(y_k,y')$、$u_k=\Psi(y_k)-\varphi$)。

1. 把梯度界代入式 (3):$\Phi_{k+1}\le\Phi_k-2s(1-\mu)\beta_k\big[1-2\zeta s(1-\mu)\beta_kL_f\big]g_k-2s\mu\alpha_ku_k+C_2\alpha_k^2$;步长条件使方括号 $\ge\tfrac12$,得 $$\Phi_{k+1}\le\Phi_k-c_1g_k-2s\mu\alpha_ku_k+C_2\alpha_k^2,\qquad c_1=s(1-\mu)\underline\beta. \tag{4}$$
2. 偏移控制(G1 唯一入口):$u_k$ 可能为负(迭代点在 $\mathcal S$ 外时 $\Psi$ 可低于 $\varphi$),但 $u_k^-\le G_F\,d(y_k,\mathcal S)\le G_F\sqrt{c\,g_k}$(投影 + Lipschitz + G1)。
3. LLOCP:Young 不等式把交叉项 $2s\mu\alpha_k u_k^-$ 吸收成 $\tfrac{c_1}{2}g_k+O(\alpha_k^2)$,得 $$\Phi_{k+1}\le\Phi_k-\tfrac{c_1}{2}\,g_k+C_3\alpha_k^2; \tag{5}$$ 求和 $\Rightarrow\sum g_k\lt\infty\Rightarrow g_k\to0$。同法得加权可和 $\sum\alpha_ku_k^+\lt\infty$。
4. 拟 Fejér 升级为单点收敛:式 (5) 说明 $\{d^2(y_k,y')\}$ 对每个 $y'\in\mathcal S^{\mathrm{opt}}$ 都是拟 Fejér 单调、故收敛;由 $\sum\alpha_k=\infty$ 与加权可和取子列 $u_{k_i}^+\to0$,紧性抽极限 $\bar y$;$g_{k_i}\to0$ 给 $\bar y\in\mathcal S$,再由 $u_{k_i}\to0$ 给 $\Psi(\bar y)=\varphi$,即 $\bar y\in\mathcal S^{\mathrm{opt}}$;最后在 $y'=\bar y$ 上用拟 Fejér 性质:极限存在且沿子列为 0,故全列 $y_k\to\bar y$。ULOCP 由连续性。

5.3 定理 2(显式速率)

骨架。定理 1 已给两笔总预算 $\sum g_j\le 2B/c_1$、$\sum\alpha_ju_j^+\le B'$;在窗口 $W_k=\{\lceil k/2\rceil,\dots,k\}$ 内 $\alpha_j\ge(k+1)^{-\theta}$,窗口长 $\ge k/2$,取平均(抽屉原理)得好点 $j_k$:$g_{j_k}\le2B_0/k$、$u_{j_k}^+\le4B_0/k^{1-\theta}$。G1 把第一条换算成第二条;设 $\hat y=P_{\mathcal S}(y_{j_k})$,$\Psi(\hat y)-\varphi\le u_{j_k}^++G_Fd(y_{j_k},\mathcal S)\le C_4k^{-(1-\theta)}$($k^{-1/2}$ 项被吸收,因 $1-\theta\lt\tfrac12$);G2 换算成 $d(\hat y,\mathcal S^{\mathrm{opt}})$,三角不等式收尾。

读法。选择指数 $1-\theta$ 明确:$\theta$ 越小指数越好,但常数 $C\propto\sum(k+1)^{-2\theta}$ 在 $\theta\downarrow\tfrac12$ 发散——指数与常数互换。第三条是单边的:$\mathcal S$ 外 $\Psi$ 可低于 $\varphi$,至多低 $G_F\,d(y_{j_k},\mathcal S)=O(k^{-1/2})$。

内层复杂度(一般情形)。由最后一条,$d\le\epsilon$ 需 $k=O(\epsilon^{-p/(1-\theta)})$ 次内层迭代;每次一个 $\mathcal G\psi$、一个 $\mathcal G\Psi$、一次 retraction,无 Hessian、无线性方程组求解。

5.4 命题 3(常数比:算法 1 实际运行的模式)

结论与骨架。共同乘子使更新因式化为固定 g-凸目标 $\psi_\mu$ 上的调度梯度步——这是「调度决定收敛到哪」的精确含义。

• (i) 单层速度:关键不等式 $$d^2(y_{k+1},\bar y_\mu)\le d^2(y_k,\bar y_\mu)-2sp_k(1-\zeta sp_kL_\mu)\big[\psi_\mu(y_k)-\min\psi_\mu\big]. \tag{6}$$ 常数 $p_k$ 时求和给 $O(1/k)$ 值速率(在 $s=1/(2\zeta L_\mu)$ 为 $O(\zeta L_\mu d_0^2/k)$);距离对每个最小点不增 $\Rightarrow$ Fejér 单调 $\Rightarrow$ 全列收敛到单个最小点 $\bar y_\mu$。
• (ii) 偏差量化(需 G1 + $\|\mathcal G\Psi\|\le M$):混合一阶最优条件 $(1-\mu)\mathcal G\psi(\bar y_\mu)=-\mu\mathcal G\Psi(\bar y_\mu)$ 给 $\|\mathcal G\psi(\bar y_\mu)\|\le\mu M/(1-\mu)$;与 g-凸性、G1 串联得 $$d(\bar y_\mu,\mathcal S)\le\frac{c\,M\mu}{1-\mu},\qquad \Psi(\bar y_\mu)\le\varphi(x),\qquad \Psi\big(P_{\mathcal S}(\bar y_\mu)\big)-\varphi(x)\le\frac{\ell_F\,c\,M\mu}{1-\mu}.$$

注意不声称的东西:不直接界 $d(\bar y_\mu,\mathcal S^{\mathrm{opt}})$。论文的「偏差注记」用 $\mathbb R^2$ 反例($\psi=y_1^2/2$、$\Psi$ 平移二次)证明横向偏差恰等于 $\mu$——常数比下不可去除;上层跨因子可分时平坦方向选择精确,带耦合项 $\lambda y_1y_2$ 时平坦方向同样染上 $\Theta(\mu)$ 偏差;跨外层退火 $\mu_k\downarrow0$(每个内层循环用常数 $\mu_k$)沿 Tikhonov 路径 $\bar y_{\mu_k}\to\mathcal S^{\mathrm{opt}}$ 找回精确性,而不牺牲内层速度。

6. LLS 条件下的 $\epsilon$ 计算复杂度(重点)

6.1 推论 4(LLS 基线)

A1 成立时:$\mathcal S=\mathcal S^{\mathrm{opt}}=\{y^*(x)\}$,G1 自动成立($c=2/C_f$),LLOCP 与 ULOCP 合而为一。直接论证(绕开 $\Psi$ 的 g-凸性,只用 $\|\mathcal G\Psi\|\le G_F$):上层内积改用 Cauchy–Schwarz,强凸给 $g_k\ge\tfrac{C_f}{2}\Phi_k$,Young 后得收缩

即线性率直到消失的 $O(\alpha_k^2)$ 聚合扰动。但在常数比 $p_k\equiv1$ 下扰动不消失,留下 $\mu^2$ 量级的底——这正是推论 5 要给出的干净形式:换参照点后无底收缩。

6.2 推论 5(条件数中的 LLS 复杂度)

推导链(七步)。

1. 收缩:强凸不等式 $\psi_\mu(y)-\min\psi_\mu\ge\tfrac{m_\mu}{2}d^2(y,\bar y_\mu)$ 代入式 (6)($p_k\equiv1$):$d^2_{k+1}\le\big[1-s(1-\zeta sL_\mu)m_\mu\big]\,d^2_k$;在 $s=1/(2\zeta L_\mu)$ 处方括号取最小,得 $$d^2(y_{k+1},\bar y_\mu)\le\Big(1-\frac{1}{4\zeta\kappa_\mu}\Big)d^2(y_k,\bar y_\mu). \tag{7}$$ 顺带:距离单调不增,迭代点自动留在初始球内,$\mathcal K$-包含性在此自我供给。
2. 步数:迭代 + $\log(1-t)\le-t$ 给 $d(y_k,\bar y_\mu)\le e^{-k/(8\zeta\kappa_\mu)}d_0$,于是 $$d(y_k,\bar y_\mu)\le\epsilon\quad\text{当}\quad k\ge S_{\mathrm{RBDA}}(\epsilon)=\Big\lceil8\zeta\kappa_\mu\log\frac{d(y_0,\bar y_\mu)}{\epsilon}\Big\rceil. \tag{8}$$
3. 偏差:命题 3(ii) 代入 $c=2/C_f$:$d(\bar y_\mu,y^*(x))\le\dfrac{2M\mu}{(1-\mu)C_f}$。收敛目标离真解有这么远,不能更近。
4. 基准:$\mu=0$ 即朴素下层求解(每个隐式/展开估计量都要先跑的那一步),同样的推导给 $S_0(\epsilon)=\lceil8\zeta\kappa_f\log(d(y_0,y^*)/\epsilon)\rceil$。
5. 比值:$\epsilon\downarrow0$ 时对数占主导, $$S_{\mathrm{RBDA}}(\epsilon)\sim\frac{\kappa_\mu}{\kappa_f}\,S_0(\epsilon),\qquad \frac{\kappa_\mu}{\kappa_f}\le1+\frac{\mu}{1-\mu}\cdot\frac{L_F}{L_f}\ \longrightarrow\ 1\quad(\mu\downarrow0). \tag{9}$$
6. 退火消偏差:取 $\mu(\epsilon)$ 使 $\mu/(1-\mu)\le C_f\epsilon/(2M)$,则偏差 $\le\epsilon$,三角不等式给 $d(y_k,y^*(x))\le2\epsilon$ 对 $k\ge S_{\mathrm{RBDA}}(\epsilon)$,且 $S_{\mathrm{RBDA}}(\epsilon)\sim S_0(\epsilon)$:到真解 $2\epsilon$ 精度,步数与朴素求解渐近相同。
7. $\Psi$ 也强凸时:$m_\mu=(1-\mu)C_f+\mu C_F$, $$\kappa_\mu=\frac{(1-\mu)L_f+\mu L_F}{(1-\mu)C_f+\mu C_F}$$ 是 $\kappa_f$ 与 $\kappa_F=L_F/C_F$ 的加权中间数——落在两者之间,且 $\kappa_\mu\lt\kappa_f\iff\kappa_F\lt\kappa_f$:上层条件更好时,混合问题反而比纯下层好解。

6.3 单次超梯度成本对照(论文表「成本表」)

三条带条件的读法(与论文口径一致,不许写强了):

• 对 AD 是等价而非增益:步数只差 $\kappa_\mu/\kappa_f=1+O(\mu)$,退火时完全一样;只有当 $\Psi$ 自身强 g-凸且 $\kappa_F\lt\kappa_f$ 时混合才严格更好。
• 对隐式估计量是交换:省掉一次线性求解(精确解 / CG / Neumann),代价是 $(\kappa_\mu/\kappa_f-1)S_0$ 步额外一阶迭代 + $O(\mu)$ 偏差;划不划算取决于那次求解的价格(§5.1 实测)。
• 常数取决于几何:计数里的条件数是「该方法所在几何」的条件数。SPD 下层在仿射不变度量中 $\operatorname{cond}(\mathcal H)\sim\operatorname{cond}(A)^{1/2}$,欧氏度量中 $\sim\operatorname{cond}(A)^{1.2}$(附录 C 实测)——同一计数,欧氏几何(E-BDA)的常数按此幂次更大,这就是 §5.3 优势的机制。

两个边界:$p_k=1/(1+\rho k)$、$\rho\gt 0$ 时,预算 $K$ 内计数至多放大 $(1+\rho K)$ 倍,渐近陈述式 (9) 是 $\rho=0$ 的;BB 阶段在计数之外(经验加速,不进理论)。

7. 若从零构建,建议的推进顺序

1. 几何底座:Hadamard、比较不等式 (2)、投影非扩张——全部可直接引用(zhang2016first-order;Bauschke–Combettes 的 Fejér 工具箱),不需自证。
2. 引理 6(一步估计):所有支线的公共起点,先把它连同梯度界一次写严。
3. 常数比支线(命题 3):最短路径,只用 g-凸 + 光滑;先 (i) 后 (ii);顺带把注记的反例算清($\mathbb R^2$ 手算)。
4. LLS 支线(推论 4 → 推论 5):在强凸下把命题 3 升级为收缩,并完整走一遍 6.2 节的七步——这是复杂度结论所在。
5. 递减比支线(定理 1 → 定理 2):最重的部分(拟 Fejér、窗口论证),依赖 G1。
6. 收尾:统一核对常数($c_1,C_2,C_3,C_3',B,B',B_0,C_4$)与第 3 节的「假设消费表」,确认没有结果用了未声明的条件。

8. 已知边界与缺口清单

1. retraction 差距未量化:分析用指数映射形式;换一般 retraction 需控制其在法邻域内的局部误差,论文未做。实验的下层($\mathcal S_{++}^d$ 仿射不变度量)用的是精确指数映射,差距为零。
2. 只有固定 $x$ 的内层结论:外层序列 $\{x^r\}$、有限步估计量 $\widetilde{\mathcal G}\varphi_K$(不声称 $\to\mathcal G\varphi$)都无保证;端到端复杂度不存在也不能写。欧氏侧 liu2022general 用 $\varphi_K\to\varphi$ 闭合了这半环,黎曼版(需要定理 1 对 $x$ 一致)是公开问题。
3. best-iterate 而非 last-iterate:定理 2 的速率在滑动窗口内取好点;最后一个迭代点的速率未知。
4. 定理 1 依赖 G1:仅 g-凸(无误差界)时,欧氏侧靠 liu2022general Thm 5 的双域论证,其黎曼推广未做。
5. BB 阶段在保证之外:唯一衔接点是阶段结束点 $y_{K_1}\in\mathcal K$(可用 $P_{\mathcal K}$ 投影强制,包含性注记 (ii);否则作为附带条件);不声称可证加速。
6. 常数的退化方向:定理 2 的 $C$ 在 $\theta\downarrow\tfrac12$ 时经 $\sum(k+1)^{-2\theta}$ 发散;$\zeta\to\infty$(强负曲率或大直径)时所有常数变坏。
7. 命题 3 不界 $d(\bar y_\mu,\mathcal S^{\mathrm{opt}})$:一般情形该界必在 $\mu$ 阶失效(反例),只有上层跨因子可分时平坦方向精确——写结论时须保持这个精确度。

附:与 article.tex 源标签的对照表