技术摘要：RanSOM

1. 问题陈述

本文解决了深度学习随机优化中的一个根本性局限：标准动量方法（如 Polyak 的动量球）在非凸景观中应用时存在的曲率诱导偏差。

在随机设置下，动量向量 $m_t$ 聚合了先前迭代的梯度。当优化器从 $x_{t-1}$ 移动到 $x_t$ 时，损失景观的曲率导致梯度方向发生变化。因此，$m_{t-1}$ 成为当前梯度 $\nabla f(x_t)$ 的“过时”估计量。这种偏差与沿更新路径的 Hessian 矩阵积分成正比，阻碍了标准动量方法达到非凸优化所需的最佳 $O(\epsilon^{-3})$ 样本复杂度，通常将其限制在次优的 $O(\epsilon^{-4})$ 速率。

现有的校正策略面临“偏差 - 方差瓶颈”：

• 基于差异的估计量（如 STORM）： 需要单个样本的平滑性（通常被 ReLU 激活函数违反）或遭受高方差的影响。
• 确定性二阶动量（SOM）： 需要对 Hessian 矩阵施加强全局 Lipschitz 假设（有界三阶导数）。
• 随机 SOM（SOM-Unif）： 放宽了平滑性假设，但通过要求辅助“前瞻”查询（每次迭代 3 次前向/后向传递）而产生了过高的计算开销。

2. 方法论：RanSOM 框架

作者提出了RanSOM（随机化二阶动量），这是一个统一的框架，无需额外假设或计算开销即可消除曲率偏差。核心创新在于用从特定分布中抽取的随机化步长替代确定性步长。

2.1 随机化分部积分

代替固定步长 $\eta_t$，步长 $s_t$ 被视为具有均值 $\mathbb{E}[s_t] = \eta_t$ 的随机变量。通过利用Stein 型恒等式（分部积分公式），该方法将梯度的有限差分（即偏差）与在随机端点评估的单个 Hessian-向量积（HVP）联系起来。

该框架利用了两个特定的恒等式：

1. 指数恒等式（无约束）： 如果 $s \sim \text{Exp}(\lambda)$，则：
   $$\mathbb{E}[g(s) - g(0)] = \frac{1}{\lambda} \mathbb{E}[g'(s)]$$
   这允许通过将 $x_{t+1}$ 处的 HVP 缩放 $\eta_t$ 来估计偏差 $\nabla f(x_{t+1}) - \nabla f(x_t)$。
2. Beta 恒等式（有约束）： 如果 $s \sim \text{Beta}(1, K)$，则：
   $$\mathbb{E}[g(s) - g(0)] = \mathbb{E}\left[ \frac{1-s}{K} g'(s) \right]$$
   这考虑了 Beta 分布的紧支撑性，确保在有约束优化中的可行性。

2.2 算法实例化

该框架在两种算法中得以实例化：

• RanSOM-E（无约束）： 使用指数分布步长。它与线性最小化 oracle（LMO）集成以统一各种几何更新，恢复了归一化 SGD（$L_2$ 球）、SignSGD（$L_\infty$ 球）和 Muon 风格的谱更新。
• RanSOM-B（有约束）： 在 $[0, 1]$ 上使用 Beta 分布步长。这确保更新 $x_{t+1} = (1-s_t)x_t + s_t v_t$（其中 $v_t$ 是 LMO 方向）严格保持在凸可行集 $C$ 内，从而避免投影操作。

2.3 计算效率

RanSOM 的一个关键优势是其计算成本。校正项需要在 $x_{t+1}$ 处计算 HVP。在现代自动微分框架（如 PyTorch、JAX）中，该 HVP 可以通过 Pearlmutter 技巧在单次组合后向传递中与标准梯度计算一起完成。

• 成本： $2(F_c + B_c)$（相当于两次前向/后向传递）。
• 比较： 这与 STORM 等标准方差减少方法的成本相当，且显著低于 SOM-Unif，后者需要专用的辅助查询（$3(F_c + B_c)$）。

3. 主要贡献

1. 统一框架： 一种利用随机化步长和 Stein 恒等式消除曲率诱导偏差的方法，适用于无约束和有约束优化。
2. 最优收敛速率： 理论分析证明，在标准有界噪声假设下，RanSOM 实现了最优的 $O(\epsilon^{-3})$ 样本复杂度。
3. 对重尾的鲁棒性： 该方法扩展到具有重尾梯度噪声（$p \in (1, 2]$）和广义 $(L_0, L_1)$-平滑性（其中 Hessian 范数随梯度范数增长）的挑战性设置，无需 Hessian 满足 Lipschitz 连续性。
4. 无辅助开销： 与先前的二阶校正不同，RanSOM 不需要辅助“前瞻”点，保持了 $2(F_c + B_c)$ 的标准查询复杂度。
5. 无需截断： 该方法在不进行显式梯度截断的情况下实现最优速率，而是依赖于 LMO 更新提供的内在归一化以及随机步长的统计特性。

4. 理论结果

本文在以下条件下建立了非凸优化的收敛性：

• 假设： 目标函数下有界，并满足逐点 $(L_0, L_1)$-平滑性。随机梯度和 HVP 是无偏的，且具有仿射重尾噪声（矩 $p, q \in (1, 2]$）。
• 无约束（RanSOM-E）： 以速率收敛到平稳点：
  $$\frac{1}{T} \sum_{t=0}^{T-1} \mathbb{E}[\|\nabla f(x_t)\|_*] \leq O\left( T^{-\frac{q(p-1)}{2q(p-1)+p}} \right)$$
  对于标准情况（$p=q=2$），这恢复了最优的 $O(T^{-1/3})$ 速率。
• 有约束（RanSOM-B）： 以相同的最佳速率 $O(T^{-1/3})$（当 $p=q=2$ 时）在 Frank-Wolfe 间隙 $G(x)$ 方面收敛。

分析强调了动量参数 $\beta$ 的非对称缩放：较小的 $\beta$ 有助于平均高方差梯度，而较大的 $\beta$ 使曲率校正更具影响力。最优的 $\beta$ 平衡了这些效应。

5. 实验结果

作者在三个非凸任务上评估了 RanSOM：

1. 二分类（SPLICE）： RanSOM-E（Muon 变体）实现了最高的测试准确率（84.90%），与 STORM（73.35% ± 10.77%）相比方差显著更低。
2. 序列分类（MNIST1D）： RanSOM-E（Muon）达到了 91.90% 的准确率，优于 STORM（88.83%）和经典 SOM，同时保持了高稳定性（标准差 ±0.36，而 STORM 为 ±1.38）。
3. 有约束矩阵补全（MovieLens）： RanSOM-B 收敛到的最终 RMSE 低于随机 Frank-Wolfe 基线（SFW-Polyak、SFW-SOM），证明了其在导航复杂约束几何方面的有效性。

6. 意义与主张

本文声称，RanSOM 解决了二阶动量校正的“困境”：它在不需要 Lipschitz Hessian 或单个样本平滑性的限制性假设，且不需要辅助采样的计算开销的情况下，实现了 $O(\epsilon^{-3})$ 的最优收敛速率。

通过将步长视为随机变量，RanSOM 实现了鲁棒的二阶偏差校正，其特点如下：

• 假设轻量： 处理非平滑单个损失（如 ReLU 网络）和重尾噪声。
• 计算高效： 成本与带动量的标准 SGD 相当。
• 几何灵活： 通过 LMO 自然地推广到归一化优化器和有约束设置。

作者将 RanSOM 定位为现代非凸优化的统一解决方案，特别是在标准平滑性假设失效且计算效率至关重要的深度学习架构中。