超越有界方差：Blum-Gladyshev噪声下非凸优化的方差缩减归一化方法

# 超越有界方差：Blum–Gladyshev 噪声下非凸优化的方差缩减归一化方法 来源: https://arxiv.org/html/2605.15314 Antesh Upadhyay, Arda Fazla, Abolfazl Hashemi 作者单位：普渡大学电气与计算机工程学院，美国印第安纳州西拉斐特 47907。 ###### 摘要 我们研究 Blum–Gladyshev (BG\mathsf{BG}-0) 噪声模型下的非凸随机优化问题，其中随机梯度方差随与初始点的距离呈二次增长。我们在标准光滑性和对称广义光滑性框架[7 (https://arxiv.org/html/2605.15314#bib.bib142)]下考虑该问题，后者刻画了局部曲率可随梯度范数缩放的目标函数。我们证明，在 BG\mathsf{BG}-0 噪声下，每步仅使用一个随机梯度的带动量归一化随机梯度下降方法，其预言复杂度为 O(ε−6)\mathcal{O}(\varepsilon^{-6})。该速率在标准光滑性和 α\alpha-对称广义光滑性下均成立，表明在此设定下广义光滑性对归一化动量是速率中性的。随后，我们研究了一种方差缩减的归一化 STORM 方法。在均方光滑性和锐利初始化的条件下，该方法达到极小极大最优复杂度 O(ε−4)\mathcal{O}(\varepsilon^{-4})，匹配下界[13 (https://arxiv.org/html/2605.15314#bib.bib139)]。在期望的 α\alpha-对称广义光滑性下，STORM 递归耦合了依赖梯度的光滑性与依赖距离的噪声，导致复杂度为：当 α∈(0,1)\alpha\in(0,1) 时为 O(ε−(4+α))\mathcal{O}(\varepsilon^{-(4+\alpha)})，当 α=1\alpha=1 时为 O(ε−5)\mathcal{O}(\varepsilon^{-5})。当噪声模型中的距离增长参数消失时，我们的保证恢复标准有界方差速率：动量方法为 O(ε−4)\mathcal{O}(\varepsilon^{-4})，方差缩减方法为 O(ε−3)\mathcal{O}(\varepsilon^{-3})，确定性情形为 O(ε−2)\mathcal{O}(\varepsilon^{-2})。据我们所知，这是在 BG\mathsf{BG}-0 噪声下，无需有界域、无需增大批大小、无需显式锚定，且覆盖标准光滑性和广义光滑性两种情形的、关于归一化方法在非凸随机优化中收敛性的首批保证。 ## 1 引言 大规模非凸学习通常被表述为随机优化问题 minx∈Rd f(x), f(x):=Eξ[f(x;ξ)],\min_{x\in\mathbb{R}^d}f(x),\qquad f(x):=\mathbb{E}_{\xi}[f(x;\xi)], (1) 其中 f:Rd→Rf:\mathbb{R}^d\to\mathbb{R} 通常是非凸的。目标是找到一个 ε\varepsilon-稳定点，即满足 E‖∇f(x)‖≤ε\mathbb{E}\|\nabla f(x)\|\leq\varepsilon 的点 xx。在标准光滑性和一致有界随机噪声假设下，该问题的复杂度理论已相当完善。在确定性设定中，梯度下降在光滑非凸优化中达到最优 O(ε−2)\mathcal{O}(\varepsilon^{-2}) 迭代复杂度[34 (https://arxiv.org/html/2605.15314#bib.bib56),35 (https://arxiv.org/html/2605.15314#bib.bib112)]。在随机设定中，SGD 在有界方差 Eξ‖∇f(x;ξ)−∇f(x)‖2≤σ2\mathbb{E}_{\xi}\bigl\|\nabla f(x;\xi)-\nabla f(x)\bigr\|^{2}\leq\sigma^{2} 下达到经典 O(ε−4)\mathcal{O}(\varepsilon^{-4}) 样本复杂度，该速率对于一般光滑非凸随机优化不可改进[14 (https://arxiv.org/html/2605.15314#bib.bib50),2 (https://arxiv.org/html/2605.15314#bib.bib29)]。在更强的均方光滑性或平均光滑性条件下，方差缩减方法（如 SVRG、SAGA、SARAH、SPIDER、SpiderBoost、SNVRG、PAGE、STORM）将复杂度提升至最优 O(ε−3)\mathcal{O}(\varepsilon^{-3})[23 (https://arxiv.org/html/2605.15314#bib.bib137),11 (https://arxiv.org/html/2605.15314#bib.bib138),36 (https://arxiv.org/html/2605.15314#bib.bib12),12 (https://arxiv.org/html/2605.15314#bib.bib45),42 (https://arxiv.org/html/2605.15314#bib.bib68),46 (https://arxiv.org/html/2605.15314#bib.bib135),31 (https://arxiv.org/html/2605.15314#bib.bib16),10 (https://arxiv.org/html/2605.15314#bib.bib41)]。

这些经典随机保证通常依赖于一致有界噪声模型。虽然数学上方便，但该假设即使在基本的无约束随机优化问题（如最小二乘）以及现代深度学习中也可能失败——随机梯度方差并非一致常数，而是随着迭代点远离参考点而增长。这激发了 BG\mathsf{BG}-0 噪声模型[4 (https://arxiv.org/html/2605.15314#bib.bib79),15 (https://arxiv.org/html/2605.15314#bib.bib93)]，该模型最近被识别为理论分析中最弱的可行方差假设之一[1 (https://arxiv.org/html/2605.15314#bib.bib129)]。在 BG\mathsf{BG}-0 下，方差允许随与初始点的距离呈二次增长： Eξ‖∇f(x;ξ)−∇f(x)‖2≤B2‖x−x0‖2+G2.\mathbb{E}_{\xi}\bigl\|\nabla f(x;\xi)-\nabla f(x)\bigr\|^{2}\leq B^{2}\|x-x^{0}\|^{2}+G^{2}. 经典有界方差设定由 B=0B=0 恢复，确定性情形对应 B=G=0B=G=0。尽管 BG\mathsf{BG}-0 比有界方差更宽松，但它引入了内在的反馈机制：若迭代点远离 x0x^{0}，则预言变得更嘈杂；更大的随机噪声进而扰动未来方向，将轨迹推离 x0x^{0} 更远。因此，在无界域上，方差尺度 B2‖xk−x0‖2+G2B^{2}\|x^{k}-x^{0}\|^{2}+G^{2} 不能被视为无害的常数。最近 Fazla 等人[13 (https://arxiv.org/html/2605.15314#bib.bib139)] 表明这种困难是内在的：在 BG\mathsf{BG}-0 噪声下，光滑非凸优化的下界从经典的 Ω(ε−4)\Omega(\varepsilon^{-4}) 恶化至 Ω(ε−6)\Omega(\varepsilon^{-6})，即使在均方光滑性下，最佳可能速率也是 Ω(ε−4)\Omega(\varepsilon^{-4}) 而非有界方差下的 Ω(ε−3)\Omega(\varepsilon^{-3}) 速率[2 (https://arxiv.org/html/2605.15314#bib.bib29)]。他们还提出了 PASTA，通过结合 Halpern 型锚定[18 (https://arxiv.org/html/2605.15314#bib.bib100)]、Tikhonov 正则化和动态批大小，匹配这些界限，将 BG\mathsf{BG}-0 随机逼近与经典不动点格式（如 Halpern 和 Krasnoselskii–Mann 迭代[32 (https://arxiv.org/html/2605.15314#bib.bib21),28 (https://arxiv.org/html/2605.15314#bib.bib20),18 (https://arxiv.org/html/2605.15314#bib.bib100),13 (https://arxiv.org/html/2605.15314#bib.bib139)]）联系起来。

在本文中，我们采取互补的视角。我们不添加显式的稳定锚或增加每步批大小，而是探究是否无需有界域，带动量或递归方差缩减的归一化随机方法就能处理 BG\mathsf{BG}-0 噪声。

**为什么归一化？** 关键在于归一化将更新的步长与随机梯度估计量的范数解耦。给定估计量 vkv^{k}，定义 dk=vk‖vk‖, xk+1=xk−γdk.d^{k}=\frac{v^{k}}{\|v^{k}\|},\qquad x^{k+1}=x^{k}-\gamma d^{k}. 那么，‖xk+1−xk‖=γ‖dk‖≤γ,\|x^{k+1}-x^{k}\|=\gamma\|d^{k}\|\leq\gamma, 无论 ‖vk‖\|v^{k}\| 的大小如何。因此，‖xk−x0‖≤∑t=0k−1‖xt+1−xt‖≤kγ.\|x^{k}-x^{0}\|\leq\sum_{t=0}^{k-1}\|x^{t+1}-x^{t}\|\leq k\gamma. 因此，沿归一化轨迹，BG\mathsf{BG}-0 方差尺度满足 (B2‖xk−x0‖2+G2)1/2≤G+Bkγ.\left(B^{2}\|x^{k}-x^{0}\|^{2}+G^{2}\right)^{1/2}\leq G+Bk\gamma. 因此，归一化将随机梯度大范数的潜在失控效应转化为受控的轨迹增长。相比之下，PASTA[13 (https://arxiv.org/html/2605.15314#bib.bib139)] 通过动态批大小控制 BG\mathsf{BG}-0 方差。在那里，批大小必须与局部方差上界成比例，即 Nk ∝ B2‖xk−x0‖2+G2σ2N_{k}\ \propto\ \tfrac{B^{2}\|x^{k}-x^{0}\|^{2}+G^{2}}{\sigma^{2}}，并依赖于问题相关的精度和步长因子。这样的规则需要知道或至少可靠估计方差增长常数 BB 和 GG，这在实践中可能难以获得。

**广义光滑性。** 第二个挑战是许多学习目标并非全局光滑，即其局部光滑性可能随梯度范数增长[22 (https://arxiv.org/html/2605.15314#bib.bib140),44 (https://arxiv.org/html/2605.15314#bib.bib141)]。这是归一化更新的自然设定[7 (https://arxiv.org/html/2605.15314#bib.bib142)]。因此，我们研究 Chen 等人[7 (https://arxiv.org/html/2605.15314#bib.bib142)] 定义的确定性类 Lsym∗(α)\mathcal{L}_{\rm sym}^{*}(\alpha) 及其随机类比 ELsym∗(α)\mathbb{E}\mathcal{L}_{\rm sym}^{*}(\alpha) 下的 BG\mathsf{BG}-0 噪声，其中 α∈(0,1]\alpha\in(0,1]。类 Lsym∗(α)\mathcal{L}^{*}_{\rm sym}(\alpha) 包含标准光滑函数 (L)(\mathcal{L})、非对称广义光滑函数 (Lasym∗)(\mathcal{L}_{\rm asym}^{*}) 和基于 Hessian 的广义光滑函数 (LH∗)(\mathcal{L}_{\rm H}^{*})，还包括高阶多项式和指数型目标[7 (https://arxiv.org/html/2605.15314#bib.bib142),44 (https://arxiv.org/html/2605.15314#bib.bib141),29 (https://arxiv.org/html/2605.15314#bib.bib143)]。附录 A (https://arxiv.org/html/2605.15314#A1) 总结了这些定义。先前工作表明，在适当的有界或相对方差假设下，广义光滑非凸优化可以像光滑非凸优化一样高效：归一化梯度方法恢复确定性 O(ε−2)\mathcal{O}(\varepsilon^{-2}) 速率，而 SPIDER 型方差缩减在期望广义光滑性下恢复随机 O(ε−3)\mathcal{O}(\varepsilon^{-3}) 速率[7 (https://arxiv.org/html/2605.15314#bib.bib142),12 (https://arxiv.org/html/2605.15314#bib.bib45)]。然而，这些结果并未涉及 BG\mathsf{BG}-0 噪声。在此设定下，噪声水平依赖于距离，而在广义光滑性下，局部曲率依赖于梯度。这创造了有界方差设定中不存在的轨迹增长与梯度增长之间的新相互作用。因此，事先并不清楚广义光滑优化“如同光滑优化一样高效”的原则在 BG\mathsf{BG}-0 噪声下是否仍然成立。本文正是研究这种相互作用。

### 1.1 贡献

为此，我们发展了一套归一化随机方法在标准光滑性和广义光滑性下关于 BG\mathsf{BG}-0 噪声的收敛理论。结果回答了四个问题。

- **Q1. 单样本归一化动量能否在 BG\mathsf{BG}-0 下收敛？** 能。我们证明带动量的归一化随机梯度下降 (NSGDM\mathsf{NSGDM}) 在 BG\mathsf{BG}-0 下使用每步一个新鲜随机梯度样本即可收敛。该方法无需有界域、有界随机梯度、有界方差、动态批大小或显式锚定。在 BG\mathsf{BG}-0 噪声下，NSGDM\mathsf{NSGDM} 的预言复杂度为 O(ε−6)\mathcal{O}(\varepsilon^{-6})。因此，归一化和动量提供了隐式稳定机制：归一化控制轨迹增长，动量稳定带噪声的更新方向。

- **Q2. 在 BG\mathsf{BG}-0 下，用广义光滑性取代标准光滑性是否会恶化 NSGDM\mathsf{NSGDM} 的预言复杂度？** 不会。对于 NSGDM\mathsf{NSGDM}，广义光滑性在 ε\varepsilon-复杂度指数级别上是速率中性的：在 Lsym∗(α)\mathcal{L}_{\rm sym}^{*}(\alpha) 型光滑性下，随机一阶预言 (SFO) 复杂度保持为 O(ε−6)\mathcal{O}(\varepsilon^{-6})，仅常数依赖于广义光滑性参数。

- **Q3. 额外的随机正则性能否恢复最优的 BG\mathsf{BG}-0 速率？** 能。均方光滑性 (MSS\mathsf{MSS}) 通过控制随机梯度的差 Eξ‖∇f(y;ξ)−∇f(x;ξ)‖2≤L2‖y−x‖2\mathbb{E}_{\xi}\bigl\|\nabla f(y;\xi)-\nabla f(x;\xi)\bigr\|^{2}\leq L^{2}\|y-x\|^{2} 提供了额外的随机正则性。在此更强条件下，归一化 STORM (NSTORM\mathsf{NSTORM}) 改进了 O(ε−6)\mathcal{O}(\varepsilon^{-6}) 的单样本动量速率。通过一次性的锐初始化批处理，它达到最优预言复杂度 O(ε−4)\mathcal{O}(\varepsilon^{-4})。

- **Q4. 最优的 NSTORM\mathsf{NSTORM} 速率在期望广义光滑性下是否仍然成立？** 不完全。在均方光滑性下，NSTORM\mathsf{NSTORM} 恢复 BG\mathsf{BG}-0 最优速率 O(ε−4)\mathcal{O}(\varepsilon^{-4})。但在 ELsym∗(α)\mathbb{E}\mathcal{L}_{\rm sym}^{*}(\alpha) 广义光滑性下，估计量差值的递归依赖于依赖梯度的光滑项，这些项与依赖距离的 BG\mathsf{BG}-0 方差相互作用。结果，NSTORM\mathsf{NSTORM} 达到：当 α∈(0,1)\alpha\in(0,1) 时为 O(ε−(4+α))\mathcal{O}(\varepsilon^{-(4+\alpha)})，当 α=1\alpha=1 时为 O(ε−5)\mathcal{O}(\varepsilon^{-5})。因此，广义光滑性对 NSGDM\mathsf{NSGDM} 在 ε\varepsilon-指数级别上是免费的，但在 BG\mathsf{BG}-0 下对方差缩减的 NSTORM\mathsf{NSTORM} 引入了可量化的依赖于 α\alpha 的代价。

我们还提供了在 Chen 等人[7 (https://arxiv.org/html/2605.15314#bib.bib142)] 的广义光滑目标上，使用 BG\mathsf{BG}-0 预言机的合成实验，比较了归一化动量和归一化方差缩减方法与动态批大小基线。最后，表 1 (https://arxiv.org/html/2605.15314#S1.T1) 总结了与先前工作的比较，强调了本文研究的 BG\mathsf{BG}-0 噪声、归一化方法和光滑性制度的组合。

**表 1：** 与不同光滑性概念（L, LH∗, Lasym∗, Lsym∗(α), MSS, ELsym∗(α)\mathcal{L},\mathcal{L}_{\rm H}^{*},\mathcal{L}_{\rm asym}^{*},\mathcal{L}_{\rm sym}^{*}(\alpha),\mathsf{MSS},\mathbb{E}\mathcal{L}_{\rm sym}^{*}(\alpha)）下的代表性工作的比较。复杂度以找到 ε\varepsilon-稳定点所需的预言调用次数衡量。

| 工作 | 光滑性类 | BG\mathsf{BG}-0？ | 方法 | 预言复杂度 |
|------|----------|-------------------|------|------------|
| Cutkosky and Mehta[9 (https://arxiv.org/html/2605.15314#bib.bib144)] | L\mathcal{L} | ✗ | NSGDM\mathsf{NSGDM} | O(ε−4)\mathcal{O}(\varepsilon^{-4}) |
| Zhang et al.[44 (https://arxiv.org/html/2605.15314#bib.bib141)] | LH∗\mathcal{L}_{\rm H}^{*} | ✗ | clipped SGD | O(ε−4)\mathcal{O}(\varepsilon^{-4}) |
| Reisizadeh et al.[38 (https://arxiv.org/html/2605.15314#bib.bib145)] | Lasym∗\mathcal{L}_{\rm asym}^{*} | ✗ | SPIDER + clipping | O(ε−3)\mathcal{O}(\varepsilon^{-3}) |
| Chen et al.[7 (https://arxiv.org/html/2605.15314#bib.bib142)] | Lsym∗(α)\mathcal{L}_{\rm sym}^{*}(\alpha), ELsym∗(α)\mathbb{E}\mathcal{L}_{\rm sym}^{*}(\alpha) | ✗ | 归一化方法 + SPIDER | O(ε−2)+O(ε−3)\mathcal{O}(\varepsilon^{-2})+\mathcal{O}(\varepsilon^{-3}) |
| Chen et al.[7 (https://arxiv.org/html/2605.15314#bib.bib142)] | Lsym∗(α)\mathcal{L}_{\rm sym}^{*}(\alpha), ELsym∗(α)\mathbb{E}\mathcal{L}_{\rm sym}^{*}(\alpha) | ✗ | 归一化方法 + PAGE | O(ε−2)+O(ε−3)\mathcal{O}(\varepsilon^{-2})+\mathcal{O}(\varepsilon^{-3}) |
| Fazla et al.[13 (https://arxiv.org/html/2605.15314#bib.bib139)] | L\mathcal{L} | ✓ | PASTA | O(ε−4)\mathcal{O}(\varepsilon^{-4}) (MSS\mathsf{MSS}) |
| Fazla et al.[13 (https://arxiv.org/html/2605.15314#bib.bib139)] | L\mathcal{L} | ✓ | PASTA | O(ε−6)\mathcal{O}(\varepsilon^{-6}) (L\mathcal{L}) |
| 本文 (定理 1) | L\mathcal{L}, Lsym∗(α)\mathcal{L}_{\rm sym}^{*}(\alpha) | ✓ | NSGDM\mathsf{NSGDM} | O(ε−6)\mathcal{O}(\varepsilon^{-6}) |
| 本文 (定理 3) | MSS\mathsf{MSS} | ✓ | NSTORM\mathsf{NSTORM} | O(ε−4)\mathcal{O}(\varepsilon^{-4}) |
| 本文 (定理 5) | ELsym∗(α)\mathbb{E}\mathcal{L}_{\rm sym}^{*}(\alpha) | ✓ | NSTORM\mathsf{NSTORM} | O(ε−(4+α))\mathcal{O}(\varepsilon^{-(4+\alpha)}) (α∈(0,1)\alpha\in(0,1)) |
| 本文 (定理 5) | ELsym∗(α)\mathbb{E}\mathcal{L}_{\rm sym}^{*}(\alpha) | ✓ | NSTORM\mathsf{NSTORM} | O(ε−5)\mathcal{O}(\varepsilon^{-5}) (α=1\alpha=1) |