large_matrix

第11章：流形预条件技术

流形优化中的预条件技术是将欧氏空间中成熟的二阶方法推广到曲线空间的关键桥梁。本章深入探讨如何在保持几何结构的同时，利用曲率信息加速收敛。我们将看到，恰当的预条件不仅能显著提升算法效率，还能揭示问题的内在几何结构。

11.1 流形上的Natural Gradient

11.1.1 从信息几何到优化

在机器学习中，参数空间往往具有自然的Riemannian结构。最典型的例子是概率分布的参数空间，其上的Fisher信息矩阵定义了一个自然的Riemannian度量：

\[g_{ij}(\theta) = \mathbb{E}_{p(x|\theta)}\left[\frac{\partial \log p(x|\theta)}{\partial \theta_i} \frac{\partial \log p(x|\theta)}{\partial \theta_j}\right]\]

Natural Gradient方法的核心思想是在这个几何结构下进行最陡下降：

\[\theta_{k+1} = \theta_k - \alpha_k G^{-1}(\theta_k) \nabla f(\theta_k)\]

其中$G(\theta)$是度量张量的矩阵表示。

11.1.2 流形Natural Gradient的一般形式

对于一般的Riemannian流形$\mathcal{M}$，Natural Gradient更新可以写成：

\[x_{k+1} = \mathcal{R}_{x_k}(-\alpha_k \xi_k)\]

其中：

• $\xi_k = G_{x_k}^{-1}(\text{grad} f(x_k))$是预条件后的搜索方向
• $G_{x_k}$是点$x_k$处的Riemannian度量
• $\mathcal{R}_{x_k}$是回缩映射

关键观察：Natural Gradient在流形上的表现形式自然地结合了几何结构和函数的局部信息。

11.1.3 度量选择的艺术

不同的度量选择导致不同的算法行为：

1. 标准度量：对于$\text{St}(p,n)$（Stiefel流形），标准度量是 \(g_X(\xi, \eta) = \text{tr}(\xi^T(I - \frac{1}{2}XX^T)\eta)\)

2. 欧氏度量：简单地继承环境空间的度量 \(g_X(\xi, \eta) = \text{tr}(\xi^T\eta)\)

3. 问题相关度量：基于目标函数的Hessian信息构造 \(g_X(\xi, \eta) = \langle \xi, \mathcal{H}_X[\eta] \rangle\)

11.1.4 高效实现策略

计算$G^{-1}\text{grad} f$的主要挑战在于：

• 度量张量可能是稠密的
• 直接求逆计算代价高昂
• 数值稳定性要求

实践中常用的技巧包括：

1. 对角近似：当度量接近对角时，使用对角预条件
2. 低秩修正：利用Woodbury公式处理低秩扰动
3. 迭代求解：使用共轭梯度法求解线性系统$G\xi = \text{grad} f$

11.1.5 收敛性分析要点

Natural Gradient在流形上的收敛性依赖于：

• 度量的Lipschitz连续性
• 目标函数的测地凸性
• 步长选择策略

关键定理：在适当条件下，Natural Gradient达到局部二次收敛率。

11.1.6 与经典方法的联系

有趣的是，许多经典算法可以视为特定流形上的Natural Gradient：

• 矩阵Scaling：正定矩阵流形上的Natural Gradient
• Riemannian共轭梯度：使用特定度量的预条件共轭梯度
• 测地Newton法：二阶Natural Gradient

具体例子：

1. Sinkhorn算法：可视为Wasserstein流形上的Natural Gradient
2. 幂方法：单位球面上使用特定度量的Natural Gradient
3. 交替最小化：某些乘积流形上的块坐标Natural Gradient

11.1.7 计算优化技巧

在实际实现Natural Gradient时，以下技巧至关重要：

1. 度量矩阵的高效表示：
   • 利用Kronecker结构：$G = A \otimes B$
   • 稀疏模式识别：只存储非零元素
   • 低秩分解：$G = UU^T + \sigma I$
2. 预条件系统的迭代求解：

   PCG算法框架：
   输入：线性系统 Gx = b，预条件子M
   初始化：r₀ = b - Gx₀, z₀ = M⁻¹r₀, p₀ = z₀
   迭代直到收敛：
     αₖ = (rₖᵀzₖ)/(pₖᵀGpₖ)
     xₖ₊₁ = xₖ + αₖpₖ
     rₖ₊₁ = rₖ - αₖGpₖ
     zₖ₊₁ = M⁻¹rₖ₊₁
     βₖ = (rₖ₊₁ᵀzₖ₊₁)/(rₖᵀzₖ)
     pₖ₊₁ = zₖ₊₁ + βₖpₖ
   

3. 自适应精度控制：
   • 远离最优点时使用低精度
   • 接近收敛时提高求解精度
   • 基于梯度范数动态调整

11.1.8 在深度学习中的应用

Natural Gradient在现代深度学习中有重要应用：

1. K-FAC (Kronecker-Factored Approximate Curvature)：
   • 将Fisher矩阵近似为Kronecker积
   • 显著减少存储和计算需求
   • 在大规模网络中实用
2. TONGA (Toroidal Natural Gradient Ascent)：
   • 专门用于环形拓扑的参数空间
   • 在循环神经网络中特别有效
3. Shampoo算法：
   • 使用块对角加Kronecker结构
   • 在Transformer训练中表现优异

11.1.9 理论深入：信息几何视角

从信息几何角度理解Natural Gradient提供了深刻洞察：

1. KL散度与Fisher信息： \(D_{KL}(p_{\theta}||p_{\theta+\delta}) \approx \frac{1}{2}\delta^T G(\theta) \delta\)

   这表明Fisher信息矩阵测量了参数空间中的”信息距离”。

2. α-联络与几何结构：
   • 不同的α值定义不同的几何结构
   • α=0对应混合联络（自然梯度）
   • α=±1对应指数和混合联络
3. 对偶结构：
   • 参数空间与期望参数空间的对偶
   • 通过Legendre变换联系
   • 提供了算法设计的新视角

11.1.10 数值稳定性深入分析

Natural Gradient的数值稳定性挑战及解决方案：

1. 病态Fisher矩阵：
   • 添加Tikhonov正则化：$\tilde{G} = G + \lambda I$
   • 使用谱截断：保留前k个特征值
   • 自适应调整正则化参数
2. 梯度爆炸/消失：

   • 梯度裁剪：$\xi = \min(1, \frac{c}{

     \xi

     }) \xi$

   • 层归一化技术
   • 自适应步长调整
3. 计算精度损失：
   • 使用双精度计算关键步骤
   • Kahan求和算法减少舍入误差
   • 定期重新计算基准值

11.1.11 前沿研究方向

Natural Gradient方法的活跃研究领域：

1. 量子Natural Gradient：
   • 在量子参数优化中的应用
   • Fubini-Study度量的使用
   • 与经典方法的性能比较
2. 分布式Natural Gradient：
   • Fisher矩阵的分布式计算
   • 通信高效的近似方案
   • 异步更新策略
3. 元学习中的Natural Gradient：
   • 任务空间的自然几何
   • 快速适应的理论基础
   • 与MAML等方法的联系
4. 隐式Natural Gradient：
   • 避免显式计算Fisher矩阵
   • 通过动量方法隐式实现
   • 理论分析与实践验证

11.2 Riemannian BFGS方法

11.2.1 动机与基本思想

BFGS方法在欧氏空间中的成功激发了其在流形上的推广。核心挑战在于如何在曲线空间中维护和更新Hessian近似。Riemannian BFGS (RBFGS)通过巧妙利用向量传输解决了这一问题。

基本更新公式遵循拟Newton条件： \(\mathcal{H}_{k+1} s_k = y_k\)

其中：

• $s_k = \mathcal{T}{x_k}^{x{k+1}} \xi_k$是步长的向量传输
• $y_k = \text{grad} f(x_{k+1}) - \mathcal{T}{x_k}^{x{k+1}} \text{grad} f(x_k)$

11.2.2 向量传输的选择

向量传输$\mathcal{T}$的选择对算法性能至关重要：

1. 平行传输：保持向量”方向”不变，理论性质最好
   • 优点：保度量、保正交性
   • 缺点：计算代价可能很高
2. 投影传输：简单地投影到切空间 \(\mathcal{T}_{x}^{y} \xi = \mathcal{P}_{T_y\mathcal{M}} \xi\)
   • 优点：计算简单
   • 缺点：可能不保度量
3. 向量场传输：利用流形的向量场结构
   • 适用于具有Lie群作用的流形

11.2.3 RBFGS更新公式

给定当前Hessian近似$\mathcal{H}_k$，更新公式为：

\[\mathcal{H}_{k+1} = \mathcal{H}_k - \frac{\mathcal{H}_k s_k s_k^T \mathcal{H}_k}{s_k^T \mathcal{H}_k s_k} + \frac{y_k y_k^T}{y_k^T s_k}\]

注意：所有运算都在切空间$T_{x_{k+1}}\mathcal{M}$中进行。

11.2.4 有限内存变体 (L-RBFGS)

对于大规模问题，有限内存版本更实用：

1. 存储最近$m$对$(s_i, y_i)$
2. 使用两循环递归计算搜索方向
3. 初始Hessian近似的巧妙选择： \(\mathcal{H}_0 = \frac{y_{k-1}^T s_{k-1}}{y_{k-1}^T y_{k-1}} I\)

11.2.5 数值稳定性考虑

RBFGS实现中的关键数值问题：

1. 曲率条件：确保$y_k^T s_k > 0$
   • 可能需要修正$y_k$或使用阻尼策略
2. 正定性维护：
   • 使用修正BFGS公式
   • Powell-Wolfe线搜索条件
3. 向量传输的数值误差：
   • 累积误差可能破坏收敛性
   • 定期重置或重正交化

11.2.6 收敛性理论

关键结果：

• 局部超线性收敛：在适当条件下，RBFGS达到超线性收敛率
• 全局收敛：配合适当的线搜索，保证全局收敛到驻点

收敛速度依赖于：

• 向量传输的等距性
• Hessian的Lipschitz连续性
• 初始点选择

11.2.7 实际应用案例

1. 低秩矩阵优化：在Grassmann流形上的RBFGS
2. 张量分解：在乘积流形上的应用
3. 深度学习：正交约束下的网络训练

让我们深入这些应用：

案例1：Netflix奖问题的几何视角

• 使用Grassmann流形建模低秩矩阵分解
• RBFGS相比梯度下降加速3-5倍
• 关键：利用了问题的内在低维结构

案例2：脑成像数据的张量分解

• fMRI数据的多路分解
• 在$\mathcal{St}(r_1,n_1) \times \mathcal{St}(r_2,n_2) \times \mathcal{St}(r_3,n_3)$上优化
• RBFGS处理高维数据的优势明显

案例3：正交递归神经网络

• 解决梯度消失/爆炸问题
• 在Stiefel流形上保持权重正交性
• 长序列建模性能提升显著

11.2.8 实现细节与代码结构

虽然我们不展示具体代码，但理解RBFGS的实现结构很重要：

1. 核心数据结构：
   • 存储结构：循环缓冲区存储$(s_k, y_k)$对
   • 向量传输缓存：避免重复计算
   • 度量信息：根据流形类型特化
2. 算法流程： ``` RBFGS主循环：
   1. 计算Riemannian梯度
   2. 使用两循环递归计算搜索方向
   3. 执行线搜索（测地线搜索）
   4. 更新位置（通过回缩）
   5. 计算向量传输
   6. 更新BFGS存储
   7. 检查收敛条件 ```
3. 性能优化要点：
   • 向量化所有可能的运算
   • 利用流形的对称性减少计算
   • 智能内存管理避免频繁分配

11.2.9 与其他二阶方法的比较

RBFGS在流形优化方法谱系中的位置：

1. vs Riemannian Newton：
   • Newton：需要计算/存储完整Hessian
   • RBFGS：只需存储$2m$个向量
   • Newton：局部二次收敛
   • RBFGS：超线性收敛但更稳定
2. vs Riemannian共轭梯度：
   • RCG：内存需求最小
   • RBFGS：利用历史信息更充分
   • RCG：对非凸问题可能需要频繁重启
   • RBFGS：对曲率变化适应性更好
3. vs Riemannian Trust Region：
   • RTR：全局收敛性保证更强
   • RBFGS：实现相对简单
   • RTR：每步需要求解子问题
   • RBFGS：只需线搜索

11.2.10 高级变体与改进

RBFGS的现代变体解决特定挑战：

1. Riemannian L-BFGS-B（带界约束）：
   • 处理流形上的盒约束
   • 投影梯度与RBFGS的结合
   • 在参数有物理意义限制时有用
2. 随机RBFGS：
   • 使用采样梯度估计
   • 方差缩减技术的融入
   • 大规模机器学习应用
3. 分布式RBFGS：
   • 向量对的分布式存储
   • 异步更新策略
   • 通信与计算的权衡
4. 自适应RBFGS：
   • 动态调整存储大小$m$
   • 基于曲率信息选择性更新
   • 在线学习场景的应用

11.2.11 理论前沿：收敛速度的精细分析

最新理论结果提供了更深入的理解：

1. Dennis-Moré条件的流形推广： \(\lim_{k \to \infty} \frac{\|(\mathcal{H}_k - \text{Hess} f(x_*))s_k\|}{\|s_k\|} = 0\)

   这保证了超线性收敛。

2. 有限终止性质： 对于二次目标函数在流形上的限制，RBFGS在至多$n$步内收敛（$n$是流形维数）。

3. 全局收敛速度： 在强凸情况下，可以证明： \(f(x_k) - f(x_*) \leq C \cdot r^k\) 其中$r < 1$依赖于条件数和步长策略。

4. 局部收敛率的精确刻画： 设$x_*$是非退化极小点，且RBFGS更新满足标准假设，则： \(\lim_{k \to \infty} \frac{d(x_{k+1}, x_*)}{d(x_k, x_*)^{1+\tau}} = 0\) 其中$\tau \in (0,1)$，$d(\cdot,\cdot)$是流形上的测地距离。

5. 步长为1的接受性： 类似欧氏空间情形，当充分接近最优点时，单位步长最终会被接受，这对实际计算效率至关重要。

6. 有限内存版本的收敛性： 即使只保存$m$对向量（$m \ll n$），在适当的紧致性假设下，L-RBFGS仍保持：

   • R-线性收敛（全局）
   • R-超线性收敛（局部，当$m$足够大）

11.2.12 调试与诊断技巧

实践中调试RBFGS的关键点：

1. 数值检查：
   • 验证向量传输的等距性
   • 检查拟Newton条件$\mathcal{H}_{k+1}s_k = y_k$
   • 监控条件数变化
2. 收敛诊断：
   • 绘制梯度范数对数图
   • 检查步长接受率
   • 分析搜索方向与负梯度的夹角
3. 常见问题排查：
   • 收敛停滞：检查数值精度和向量传输误差
   • 振荡行为：可能需要更保守的步长
   • 发散：验证强Wolfe条件是否满足

11.3 几何感知的Trust Region

11.3.1 流形Trust Region的基本框架

Trust Region方法在流形优化中特别有效，因为它自然地处理了曲率带来的非线性。基本思想是在每次迭代中求解子问题：

\[\min_{\xi \in T_x\mathcal{M}} m_k(\xi) \quad \text{s.t.} \quad \|\xi\|_x \leq \Delta_k\]

其中$m_k(\xi)$是目标函数的局部近似模型。

11.3.2 模型构造的艺术

不同的模型选择导致不同的算法特性：

1. 一阶模型： \(m_k(\xi) = f(x_k) + \langle \text{grad} f(x_k), \xi \rangle_x\)

2. 二阶模型： \(m_k(\xi) = f(x_k) + \langle \text{grad} f(x_k), \xi \rangle_x + \frac{1}{2}\langle \xi, \text{Hess} f(x_k)[\xi] \rangle_x\)

3. 拟Newton模型：使用RBFGS近似替代真实Hessian

11.3.3 子问题求解策略

Trust Region子问题在流形上的求解面临独特挑战：

1. Cauchy点计算：
   • 沿负梯度方向的最优步长
   • 提供下界保证
2. 截断共轭梯度法 (tCG)：
   • 在切空间中迭代求解
   • 遇到负曲率时提前终止
3. Steihaug-Toint算法的流形推广：
   • 结合CG迭代与Trust Region约束
   • 自适应处理负曲率

11.3.4 回缩映射的选择与影响

回缩映射$\mathcal{R}_x$将切向量映射回流形，其选择影响：

1. 计算效率：指数映射vs投影回缩
2. 近似质量：二阶vs一阶回缩
3. 数值稳定性：大步长时的行为

关键性质： \(\mathcal{R}_x(t\xi) = \gamma(t)\) 其中$\gamma$是从$x$出发、初始速度为$\xi$的测地线。

11.3.5 自适应半径调整

Trust Region半径$\Delta_k$的调整策略：

1. 预测比率： \(\rho_k = \frac{f(x_k) - f(\mathcal{R}_{x_k}(\xi_k))}{m_k(0) - m_k(\xi_k)}\)

2. 更新规则：
   • 若$\rho_k < 0.25$：$\Delta_{k+1} = 0.25\Delta_k$
   • 若$\rho_k > 0.75$且$|\xi_k| = \Delta_k$：$\Delta_{k+1} = 2\Delta_k$
   • 否则：$\Delta_{k+1} = \Delta_k$
3. 几何考虑：
   • 考虑流形的内蕴曲率
   • 在高曲率区域使用更保守的半径

11.3.6 收敛性分析

Trust Region方法在流形上的收敛性质：

1. 全局收敛：从任意初始点收敛到一阶驻点
2. 局部收敛速度：
   • 使用精确Hessian：二次收敛
   • 使用RBFGS近似：超线性收敛

关键假设：

• 目标函数在回缩邻域内Lipschitz连续
• 模型充分近似真实函数

11.3.7 与线搜索方法的比较

Trust Region vs 线搜索在流形优化中的权衡：

1. Trust Region优势：
   • 自然处理负曲率
   • 对病态问题更稳健
   • 理论保证更强
2. 线搜索优势：
   • 实现相对简单
   • 每步计算代价较低
   • 对某些流形结构更自然
3. 混合策略：
   • 在Trust Region框架中使用线搜索
   • 自适应切换策略

11.3.8 高级子问题求解技术

Trust Region子问题的求解是算法效率的关键：

1. Lanczos方法用于大规模问题：
   • 将Hessian投影到Krylov子空间
   • 在低维空间求解子问题
   • 特别适合Hessian-向量积便宜的情况
2. 随机化方法：
   • 使用随机投影降维
   • Johnson-Lindenstrauss引理保证近似质量
   • 在超高维流形上的应用
3. 流形特定的加速技巧：
   • Grassmann流形：利用商空间结构
   • 对称正定矩阵流形：Cholesky分解技巧
   • 固定秩矩阵流形：SVD更新公式

11.3.9 Trust Region的现代变体

近年来发展的创新方法：

1. 立方正则化方法 (ARC)： \(\min_{\xi} m_k(\xi) + \frac{\sigma_k}{3}\|\xi\|^3\)
   • 更好的理论复杂度：$O(\epsilon^{-3/2})$ vs $O(\epsilon^{-2})$
   • 自适应调整三次项系数$\sigma_k$
   • 在流形上的推广需要谨慎处理范数
2. 概率Trust Region：
   • 使用随机模型近似
   • 适合噪声优化和大规模学习
   • 收敛性分析基于鞅理论
3. 多级Trust Region：
   • 不同精度的模型层次
   • 粗网格到细网格的递归策略
   • 在PDE约束优化中特别有效

11.3.10 Trust Region与流形结构的深度结合

如何充分利用流形的几何特性：

1. 测地凸性的利用：
   • 当目标函数测地凸时，子问题全局最优
   • 设计保证测地凸性的模型
   • 凸性半径内的快速收敛
2. 曲率自适应策略： ``` 曲率感知的半径调整：
   • 计算截面曲率κ(x,ξ)
   • 调整有效半径：Δ_eff = min(Δ, π/(2√κ_max))
   • 避免超出凸性半径 ```
3. 对称性利用：
   • 等变优化：利用Lie群作用
   • 降低有效维数
   • 在物理系统优化中常见

11.3.11 数值实验深入分析

典型问题上的详细性能分析：

1. 主成分分析的几何优化：
   • Stiefel流形$St(k,n)$上最大化迹
   • Trust Region vs 标准特征值算法
   • 结果：中等规模问题上快2-3倍
2. 最近正定矩阵问题：
   • 在$S_+^n$（正定矩阵流形）上投影
   • 几何Trust Region保持正定性
   • 避免了传统方法的特征值分解
3. 同步问题（相位恢复）：
   • 在$(S^1)^n$（环面）上优化
   • Trust Region处理非凸性
   • 相比SDP松弛方法效率提升10倍

11.3.12 理论深度：最优性条件与对偶理论

Trust Region在流形上的KKT条件：

1. 一阶必要条件： 存在$\lambda \geq 0$使得：
   • $(H + \lambda I)\xi^* = -g$
   • $\lambda(|\xi^*| - \Delta) = 0$
   • $H + \lambda I \succeq 0$（在流形度量下）
2. 二阶充分条件：
   • 检查缩减Hessian的正定性
   • 在切空间的子空间中验证
   • 与约束优化理论的联系
3. 对偶问题： \(\max_{\lambda \geq 0} \min_{\|\xi\| \leq \Delta} L(\xi, \lambda)\)
   • 强对偶性在适当条件下成立
   • 对偶间隙提供最优性度量

11.3.13 软件工程视角

Trust Region方法的模块化实现：

1. 接口设计： ``` TrustRegionSolver接口：
   • solve_subproblem(model, radius)
   • compute_rho(actual_decrease, predicted_decrease)
   • update_radius(rho, step_norm, radius) ```
2. 流形抽象： ``` Manifold接口需要提供：
   • retraction(x, v)
   • inverse_retraction(x, y)
   • vector_transport(x, y, v)
   • norm(x, v) ```
3. 可扩展性考虑：
   • 插件式子问题求解器
   • 自定义停止准则
   • 性能监控钩子
4. 内存管理策略： ``` 内存池设计：
   • 预分配切向量缓冲区
   • 重用临时矩阵存储
   • 懒惰计算与缓存失效 ```
5. 数值精度控制：
   • 使用Kahan求和减少舍入误差
   • 关键运算的高精度实现
   • 条件数监控与警告系统
6. 调试与诊断工具： ``` 诊断输出：
   • 每步的模型精度ρ
   • Trust Region半径历史
   • 子问题求解迭代数
   • 梯度范数演化 ```

11.3.14 前沿应用：机器学习中的Trust Region

1. 神经网络训练：
   • 二阶信息的高效近似
   • 与K-FAC等方法结合
   • 在关键层使用Trust Region
2. 强化学习中的应用 (TRPO)：
   • 策略空间的自然参数化
   • KL散度作为Trust Region约束
   • 单调改进保证
3. 元学习与少样本学习：
   • 参数空间的快速适应
   • Trust Region控制适应步幅
   • 避免灾难性遗忘

11.3.15 开放研究问题

值得深入探索的方向：

1. 非光滑流形优化的Trust Region：
   • 处理不可微点
   • 束方法的推广
   • 应用于稀疏优化
2. 量子优化中的Trust Region：
   • 量子态空间的几何结构
   • 量子近似优化算法(QAOA)改进
   • 与变分量子算法结合
3. 分布式Trust Region：
   • 子问题的分布式求解
   • 异步半径更新
   • 拜占庭容错设计
4. 自适应流形Trust Region：
   • 动态调整工作流形
   • 基于曲率的半径自适应
   • 多尺度Trust Region策略

11.4 与欧氏空间方法的性能对比

11.4.1 理论复杂度分析

比较流形方法与投影方法的计算复杂度：

1. 每次迭代成本：
   • 欧氏投影方法：$\mathcal{O}(n^2) + $ 投影成本
   • Riemannian方法：$\mathcal{O}(n^2) + $ 回缩成本

   关键观察：对许多流形，回缩和投影的成本相当。

2. 收敛速度：
   • 欧氏方法：线性到超线性（取决于曲率）
   • Riemannian方法：保持原始收敛率
3. 内存需求：
   • L-BFGS vs L-RBFGS：相同的$\mathcal{O}(mn)$
   • Trust Region：额外的子问题求解器内存

11.4.2 数值实验基准

典型测试问题的性能对比：

1. 低秩矩阵补全（Grassmann流形）：
   • 问题规模：$1000 \times 1000$，秩$r=10$
   • Riemannian方法通常快2-5倍
   • 在高噪声情况下优势更明显
2. 特征值优化（Stiefel流形）：
   • 寻找主特征空间
   • 几何方法避免了重复正交化
   • 数值稳定性显著提升
3. 张量分解（乘积流形）：
   • Tucker分解、CP分解
   • 利用流形结构减少约束违反

11.4.3 算法选择指南

何时使用流形预条件方法：

1. 强烈推荐场景：
   • 约束曲率大
   • 问题具有自然的几何结构
   • 需要高精度解
   • 欧氏方法收敛缓慢
2. 谨慎使用场景：
   • 流形运算（如回缩）代价过高
   • 问题规模极大，内存受限
   • 只需要低精度解
   • 缺乏高效的流形运算实现

11.4.4 实现优化技巧

提升流形方法性能的关键技巧：

1. 缓存几何量：
   • 度量张量的Cholesky分解
   • 常用的投影算子
   • Christoffel符号（如需要）
2. 自适应精度：
   • 初期使用低精度回缩
   • 接近收敛时提高精度
   • 动态调整子问题求解精度
3. 并行化机会：
   • 向量传输的批处理
   • 多个搜索方向的并行评估
   • Trust Region子问题的并行求解

11.4.5 鲁棒性比较

数值稳定性和鲁棒性分析：

1. 条件数敏感性：
   • 欧氏方法：受环境空间条件数影响
   • 流形方法：仅受内蕴条件数影响
2. 初始化敏感性：
   • 流形方法通常有更大的收敛域
   • 几何结构提供了自然的正则化
3. 参数调优：
   • 流形方法的超参数通常更少
   • 默认参数的鲁棒性更好

11.4.6 前沿研究方向

1. 自适应流形选择：
   • 动态调整工作流形
   • 多流形融合策略
2. 硬件加速：
   • GPU上的流形运算
   • 专用硬件设计
3. 与深度学习的结合：
   • 神经网络中的流形层
   • 几何深度学习的优化
4. 随机流形方法：
   • 流形上的SGD变体
   • 方差缩减技术的推广

11.5 本章小结

本章深入探讨了流形优化中的预条件技术，涵盖了三个核心方法：

1. Natural Gradient方法：
   • 利用信息几何结构加速收敛
   • Fisher信息矩阵作为自然度量
   • 在深度学习中的K-FAC、Shampoo等实用变体
2. Riemannian BFGS方法：
   • 将经典拟Newton方法推广到流形
   • 通过向量传输维护Hessian近似
   • 有限内存版本适合大规模问题
3. 几何感知Trust Region：
   • 在曲线空间中自然处理非线性
   • 子问题求解与回缩映射的结合
   • 强大的全局收敛保证

关键洞察：

• 预条件技术的核心是利用问题的几何结构
• 恰当的度量选择可以显著改善条件数
• 流形方法通常比投影方法更高效、更稳定

11.6 练习题

基础题

练习11.1 证明Natural Gradient方向是切空间中的最陡下降方向。

提示：考虑在Riemannian度量下的优化问题 $\min_{|\xi|_g=1} \langle \text{grad} f(x), \xi \rangle$。

答案

设$g$是Riemannian度量，目标是求解： $$\min_{\xi} \langle \text{grad} f(x), \xi \rangle \quad \text{s.t. } g(\xi,\xi) = 1$$ 使用Lagrange乘数法，设$L(\xi,\lambda) = \langle \text{grad} f(x), \xi \rangle + \lambda(g(\xi,\xi) - 1)$。 一阶条件给出： $$\text{grad} f(x) + 2\lambda G\xi = 0$$ 因此 $\xi = -\frac{1}{2\lambda}G^{-1}\text{grad} f(x)$，这正是Natural Gradient方向（忽略归一化常数）。

练习11.2 推导Stiefel流形上的RBFGS更新公式，特别注意向量传输的作用。

提示：从拟Newton条件 $\mathcal{H}_{k+1}s_k = y_k$ 出发。

答案

Stiefel流形$\text{St}(p,n)$上的RBFGS更新需要： 1. 计算 $s_k = \mathcal{T}_{X_k}^{X_{k+1}} \eta_k$，其中$\eta_k$是搜索方向 2. 计算 $y_k = \text{grad} f(X_{k+1}) - \mathcal{T}_{X_k}^{X_{k+1}} \text{grad} f(X_k)$ 3. 确保所有运算在切空间$T_{X_{k+1}}\text{St}(p,n)$中进行 4. 更新公式保持标准BFGS形式，但所有内积使用流形度量 关键是向量传输保证了$s_k$和$y_k$在同一切空间中。

练习11.3 说明为什么Trust Region方法在处理负曲率时比线搜索方法更有优势。

提示：考虑Hessian有负特征值时两种方法的行为。

答案

Trust Region方法的优势： 1. 子问题求解自然发现负曲率方向 2. 当遇到负曲率时，沿该方向移动到Trust Region边界 3. 不需要额外的负曲率检测机制 线搜索方法的局限： 1. 标准线搜索沿固定方向，可能错过负曲率 2. 需要额外修改（如负曲率方向搜索） 3. 在鞍点附近可能停滞 Trust Region通过约束步长自然地平衡了下降和曲率利用。

练习11.4 计算球面$S^{n-1}$上的Natural Gradient，其中度量是标准球面度量。

提示：球面的切空间是 $T_xS^{n-1} = {v \in \mathbb{R}^n : x^Tv = 0}$。

答案

对于$x \in S^{n-1}$，球面度量在切空间上就是欧氏内积限制。因此： 1. 欧氏梯度：$\nabla f(x)$ 2. Riemannian梯度：$\text{grad} f(x) = \nabla f(x) - (x^T\nabla f(x))x$ 3. 由于度量是恒等的，Natural Gradient就是Riemannian梯度 4. 更新：$x_{k+1} = \frac{x_k - \alpha \text{grad} f(x_k)}{\|x_k - \alpha \text{grad} f(x_k)\|}$（归一化回球面）

挑战题

练习11.5 设计一个自适应选择度量的Natural Gradient算法，使其能够在优化过程中动态调整度量以改善条件数。

提示：考虑使用历史梯度信息或局部曲率信息。

答案

自适应度量Natural Gradient算法框架： 1. **度量更新策略**： - 收集最近$m$步的梯度：$\{\text{grad} f(x_{k-i})\}_{i=0}^{m-1}$ - 估计局部协方差：$C_k = \frac{1}{m}\sum_{i=0}^{m-1} g_i g_i^T$ - 更新度量：$G_{k+1} = \beta G_k + (1-\beta)(C_k + \epsilon I)$ 2. **条件数监控**： - 计算$\kappa(G_k) = \lambda_{\max}(G_k)/\lambda_{\min}(G_k)$ - 若$\kappa > \kappa_{\max}$，增加正则化$\epsilon$ 3. **理论保证**： - 度量保持正定性 - 收敛性通过Lipschitz连续性论证 - 自适应性通过regret分析量化 4. **实现考虑**： - 使用滑动窗口减少内存 - 增量更新特征值分解 - 在线估计主要曲率方向

练习11.6 分析在Grassmann流形上，RBFGS与Riemannian共轭梯度的性能差异，特别关注迭代次数与每次迭代成本的权衡。

提示：考虑不同问题规模和条件数下的表现。

答案

性能分析要点： 1. **迭代次数比较**： - RBFGS：通常需要更少迭代（利用二阶信息） - RCG：线性收敛，迭代数依赖于条件数 - 经验规律：RBFGS迭代数约为RCG的1/3到1/2 2. **每次迭代成本**： - RBFGS：$O(np + m^2)$，其中$m$是存储的向量对数 - RCG：$O(np)$，主要是矩阵向量乘法 - Grassmann上的特殊结构可以进一步优化 3. **内存需求**： - L-RBFGS：$O(mn)$ - RCG：$O(n)$ - 当内存受限时RCG有优势 4. **实际建议**： - 中等规模高精度：选择RBFGS - 超大规模低精度：选择RCG - 病态问题：RBFGS配合预条件

练习11.7 推导流形Trust Region方法的最坏情况迭代复杂度，并与欧氏空间的结果比较。

提示：使用立方正则化模型的分析技术。

答案

最坏情况复杂度分析： 1. **一阶驻点**： - 流形TR：$O(\epsilon^{-2})$次迭代达到$\|\text{grad} f(x)\| \leq \epsilon$ - 与欧氏空间相同的复杂度 2. **二阶驻点**： - 需要$O(\epsilon^{-3})$次迭代达到近似二阶驻点 - 立方正则化可改进到$O(\epsilon^{-3/2})$ 3. **关键假设**： - Lipschitz连续梯度（常数$L_g$） - Lipschitz连续Hessian（常数$L_H$） - 这些常数在流形上可能与欧氏空间不同 4. **流形特有因素**： - 曲率影响有效Lipschitz常数 - 需要考虑回缩映射的近似误差 - 在高曲率区域可能需要更多迭代 总结：理论复杂度相同，但常数因子可能不同。

11.7 常见陷阱与错误

11.7.1 Natural Gradient实现陷阱

1. Fisher矩阵的错误估计：
   • 错误：使用单个样本估计Fisher矩阵
   • 正确：使用批量样本或移动平均
   • 影响：单样本估计方差过大，导致不稳定
2. 数值稳定性问题：
   • 错误：直接求逆$G^{-1}$
   • 正确：添加正则化$G + \lambda I$或使用Cholesky分解
   • 影响：矩阵接近奇异时数值错误
3. 度量更新频率：
   • 错误：每步都重新计算完整Fisher矩阵
   • 正确：周期性更新或使用增量更新
   • 影响：计算开销过大

11.7.2 RBFGS常见错误

1. 向量传输的忽视：
   • 错误：直接使用欧氏空间的BFGS公式
   • 正确：所有向量必须传输到同一切空间
   • 影响：破坏算法收敛性
2. 曲率条件违反：
   • 错误：不检查$y_k^Ts_k > 0$
   • 正确：使用damping或跳过不满足条件的更新
   • 影响：Hessian近似失去正定性
3. 内存管理错误：
   • 错误：存储过多历史向量对
   • 正确：限制存储数量，使用循环缓冲
   • 影响：内存溢出或cache miss增加

11.7.3 Trust Region实现陷阱

1. 子问题求解精度：
   • 错误：过度求解子问题
   • 正确：使用相对精度准则，远离最优时可以粗糙
   • 影响：浪费计算资源
2. 半径更新策略：
   • 错误：半径调整过于激进
   • 正确：使用保守的更新因子（如0.25和2.0）
   • 影响：算法震荡或进展缓慢
3. 回缩映射选择：
   • 错误：总是使用指数映射
   • 正确：根据流形特性选择高效回缩
   • 影响：不必要的计算开销

11.7.4 流形特定陷阱

1. Stiefel流形上的正交性丢失：
   • 错误：数值误差累积导致正交性损失
   • 正确：周期性重正交化或使用稳定的参数化
   • 影响：约束违反，结果无效
2. Grassmann流形的商空间处理：
   • 错误：忽略等价类结构
   • 正确：选择标准代表元，保持一致性
   • 影响：算法行为不确定
3. 正定矩阵流形的数值问题：
   • 错误：直接参数化可能产生非正定矩阵
   • 正确：使用Cholesky因子或其他保证正定性的参数化
   • 影响：优化过程中违反流形约束

11.7.5 性能调优陷阱

1. 过早优化：
   • 错误：一开始就追求最优实现
   • 正确：先保证正确性，再优化性能
   • 影响：引入难以调试的错误
2. 忽视缓存局部性：
   • 错误：随机内存访问模式
   • 正确：设计cache-friendly的数据布局
   • 影响：性能下降10倍以上
3. 并行化错误：
   • 错误：细粒度并行化导致同步开销
   • 正确：识别合适的并行粒度
   • 影响：并行效率低下

11.8 最佳实践检查清单

11.8.1 算法选择检查清单

□ 问题规模评估

• 流形维数是否适中（<10000）？
• 是否需要高精度解？
• 内存限制是否严格？

□ 几何结构分析

• 流形曲率是否已知？
• 是否有高效的回缩映射？
• 切空间运算成本如何？

□ 收敛需求确认

• 是否需要全局收敛保证？
• 局部收敛速度要求？
• 对初始点敏感性？

11.8.2 实现质量检查清单

□ 数值稳定性保证

• 所有矩阵运算是否有条件数检查？
• 是否处理了接近零的除法？
• 迭代更新是否保持流形约束？

□ 性能优化验证

• 是否profile确认了性能瓶颈？
• 内存访问模式是否优化？
• 并行化是否带来实际加速？

□ 调试工具完备

• 是否有收敛诊断输出？
• 能否可视化优化轨迹？
• 是否保存了中间结果用于分析？

11.8.3 参数调优检查清单

□ Natural Gradient参数

• Fisher矩阵正则化参数$\lambda$选择合理？
• 批量大小是否足够估计Fisher矩阵？
• 度量更新频率是否合适？

□ RBFGS参数

• 存储的向量对数量$m$是否合适？
• 线搜索参数（Wolfe条件）是否调整？
• 初始Hessian近似是否合理？

□ Trust Region参数

• 初始半径$\Delta_0$是否与问题规模匹配？
• 半径更新阈值是否需要调整？
• 子问题求解精度是否自适应？

11.8.4 验证与测试检查清单

□ 算法正确性验证

• 是否在已知解的问题上测试？
• 梯度/Hessian是否通过有限差分验证？
• 是否测试了边界情况？

□ 性能基准测试

• 是否与标准方法比较？
• 是否测试了不同问题规模？
• 是否评估了鲁棒性？

□ 可重现性保证

• 随机种子是否固定？
• 浮点运算顺序是否确定？
• 结果是否跨平台一致？

练习11.8 设计一个结合Natural Gradient和Trust Region思想的混合算法，并分析其理论性质。

提示：考虑在Trust Region框架中使用Natural Gradient度量。

答案

Natural Gradient Trust Region (NGTR)算法： 1. **算法框架**： ``` 子问题：min_{||ξ||_G ≤ Δ} <grad f(x), ξ> + (1/2)<ξ, H[ξ]> 其中||ξ||_G^2 = <ξ, Gξ>，G是Fisher信息矩阵 ``` 2. **关键特性**： - 结合了NG的几何适应性和TR的稳健性 - Trust Region在自然度量下定义 - 子问题在信息几何意义下求解 3. **理论性质**： - 全局收敛到一阶驻点 - 局部二次收敛（使用精确Hessian时） - 对病态Fisher矩阵的鲁棒性 4. **实现要点**： - 子问题可通过变量替换$\tilde{\xi} = G^{1/2}\xi$简化 - 使用Lanczos方法处理大规模情形 - 自适应调整Fisher矩阵正则化 5. **应用前景**： - 深度学习中的二阶优化 - 变分推断中的自然参数更新 - 强化学习的策略优化