技术摘要：Blum–Gladyshev 噪声下非凸优化的方差缩减归一化方法

问题表述

本文研究形式为 $\min_{x \in \mathbb{R}^d} f(x) = \mathbb{E}_\xi[f(x; \xi)]$ 的非凸随机优化问题，其中目标函数 $f$ 通常是非凸的。本文解决的主要挑战是Blum–Gladyshev (BG-0) 噪声模型，这是对标准有界方差假设的一种放宽。在 BG-0 模型下，随机梯度的方差并非一致有界，而是随着与初始化点 $x_0$ 的距离呈二次方增长：
$$\mathbb{E}_\xi \|\nabla f(x; \xi) - \nabla f(x)\|^2 \leq B^2 \|x - x_0\|^2 + G^2$$
其中 $B, G \geq 0$。该模型捕捉了深度学习和无约束优化中的场景，即随着迭代点偏离起始点，梯度噪声随之增加。作者指出，在此噪声模型下，固有的反馈机制（即更大的迭代点引发更大的噪声，进而将迭代点推得更远）造成了内在困难，将光滑非凸优化的理论下界从 $\Omega(\epsilon^{-4})$ 恶化至 $\Omega(\epsilon^{-6})$ [13]。

本研究考虑两种光滑性情形：

1. 标准光滑性 ($L_0$)： 梯度是全局 Lipschitz 连续的。
2. 广义光滑性 ($L^*_{sym}(\alpha)$ 和 $EL^*_{sym}(\alpha)$)： 局部光滑性常数随梯度范数缩放，具体为 $\|\nabla f(y) - \nabla f(x)\| \leq (L_0 + L_1 \max_{\theta} \|\nabla f(x_\theta)\|^\alpha) \|y-x\|$。该框架捕捉了曲率具有高阶多项式或指数增长的目标函数。

方法论

本文提出并分析了归一化随机方法，这些方法不依赖有界域、动态批处理或显式锚定（如先前工作 PASTA [13] 中使用的 Halpern 风格正则化）。其核心机制是归一化，它将更新步长与随机梯度估计量的幅度解耦：
$$x_{k+1} = x_k - \gamma \frac{v_k}{\|v_k\|}$$
这确保了轨迹增长受控（$\|x_k - x_0\| \leq k\gamma$），从而限制了依赖于距离的方差项 $B^2\|x_k - x_0\|^2$。

本文分析了两种具体算法：

1. NSGDM（带动量的归一化随机梯度下降）： 每次迭代使用一个新鲜的随机梯度，并配合动量更新以稳定方向。
2. NSTORM（归一化 STORM）： 一种方差缩减方法，使用基于当前和下一个迭代点处两个随机梯度之差的递归估计量。它采用“锐利初始化”（在 $x_0$ 处使用单个批次）来控制初始误差。

主要贡献与结果

1. 归一化动量 (NSGDM) 的收敛性

作者证明了 NSGDM 在 BG-0 噪声下收敛，每次迭代仅需一个随机梯度，且无需有界域或动态批处理。

• 复杂度： 该方法实现了 $O(\epsilon^{-6})$ 的 oracle 复杂度。
• 广义光滑性： 该速率适用于标准光滑性、$\alpha$-对称广义光滑性 ($\alpha \in (0, 1)$) 以及端点 $\alpha=1$。作者证明，在此设定下，广义光滑性对 NSGDM 是速率中性的；$\epsilon$ 的指数保持为 $-6$，广义光滑性参数仅影响主导常数。
• 意义： 这提供了在 BG-0 噪声下无需显式稳定机制的归一化动量收敛保证，与该设定下的已知下界 [13] 相匹配。

2. 归一化方差缩减 (NSTORM) 的收敛性

本文研究了方差缩减是否能在 BG-0 噪声下恢复最优速率。

• 均方光滑性 (MSS)： 在 MSS 和锐利初始化下，NSTORM 达到了 $O(\epsilon^{-4})$ 的极小极大最优复杂度。这与 MSS 下 BG-0 噪声的下界 [13] 相匹配，并在 $B=0$（有界方差）时恢复了标准的 $O(\epsilon^{-3})$ 速率。
• 期望广义光滑性 ($EL^*_{sym}(\alpha)$)： 在期望 $\alpha$-对称广义光滑性下，依赖于梯度的光滑性与依赖于距离的噪声之间的相互作用引入了一个依赖于 $\alpha$ 的代价：
  • 对于 $\alpha \in (0, 1)$，复杂度为 $O(\epsilon^{-(4+\alpha)})$。
  • 对于 $\alpha = 1$，复杂度为 $O(\epsilon^{-5})$。
• 意义： 作者指出，虽然广义光滑性对基于动量的方法（NSGDM）是“免费”的，但在 BG-0 噪声下，由于梯度矩与依赖于轨迹的方差之间的耦合，它会对方差缩减方法（NSTORM）产生可量化的惩罚。

3. 标准速率的恢复

分析表明，当距离增长参数 $B$ 消失（恢复有界方差）或当 $B$ 和 $G$ 均消失（确定性情况）时，所提出的方法恢复了标准最优速率：

• 有界方差： 动量法为 $O(\epsilon^{-4})$，方差缩减法为 $O(\epsilon^{-3})$。
• 确定性： 归一化梯度下降为 $O(\epsilon^{-2})$。

实验验证

本文在带有 BG-0 预言机的广义光滑目标函数（相位检索和三次多项式）上进行了合成实验。

• 发现： 归一化方法（NSGDM 和 NSTORM）成功控制了轨迹增长，并实现了比单样本 SGD 更低的梯度范数。
• 比较： 与动态批处理基线（如 PASTA [13]）不同，后者需要批处理大小增长至 $\sim 10^3$ 以补偿噪声，归一化方法在整个优化过程中保持批处理大小为 1，证明了归一化无需知晓方差增长常数 $B$ 和 $G$ 即可有效控制方差尺度。

意义与主张

本文声称提供了在 BG-0 噪声下非凸随机优化中归一化方法的首个收敛保证，这些方法运行时无需：

1. 有界域。
2. 增加批处理大小（动态批处理）。
3. 显式锚定或正则化。

这项工作将“广义光滑优化与标准光滑优化同样高效”的原则（已在有界方差情况下确立 [7]）扩展到了更具挑战性的 BG-0 设定。然而，它也阐明了该原则的局限性：虽然广义光滑性不会降低动量方法的速率，但在依赖于距离的噪声下，它确实会给方差缩减方法带来依赖于 $\alpha$ 的退化。作者推测，这种退化是依赖于梯度的曲率与依赖于距离的方差之间耦合的内在属性；在该机制下，是否存在匹配的 lower bound 或替代方法能在期望广义光滑性下实现最优的 $O(\epsilon^{-4})$ 速率，仍是一个未决问题。