带动量的原始SGD在重尾噪声下的收敛性分析：无需梯度裁剪或归一化

# 带动量的普通 SGD 在重尾噪声下的生存：无需梯度裁剪或归一化的收敛性分析 来源：https://arxiv.org/html/2607.08104 ###### 摘要 随机梯度下降 \(SGD\) 是现代优化的基石。虽然其在重尾噪声下的性能通常通过梯度裁剪或归一化等专门修改来解决，但我们研究了一个更基本的问题：普通的 SGD，特别是带动量的版本，在重尾噪声存在时表现如何？本文中，我们改进了现有关于普通 SGD 的收敛结果，更重要的是，首次对带动量的普通 SGD 在强凸、凸和非凸目标函数下的收敛性进行了全面分析，且未使用任何梯度控制机制。我们的结果表明，所获得的收敛速率劣于裁剪或归一化变体 SGD 达到的最优速率，从而揭示了普通方法在重尾噪声下的固有限制。理论发现得到了合成函数实验的支持。

## 1 引言

本文考虑以下优化问题：
\[\min_{\bm{x}\in\mathbb{R}^d} f(\bm{x}):=\frac{1}{n}\sum_{i=1}^n f_i(\bm{x}),\]
其中每个 \(f_i\) (\(i\in[n]\)) 是可微的。我们处理 \(f\) 为强凸、凸或非凸的三种基本情况。

经验风险最小化是机器学习核心的首要目标。作为该问题的主要求解器，随机梯度下降 \(SGD\) [Her1951Ast] 及其基于动量的变体 [Polyak1964Som, Rumelhart1986Lea] 仍是当代优化的黄金标准。此类随机算法收敛性分析中的一个标准假设是随机噪声的有界方差，具体来说，是随机梯度与全梯度之间误差的二阶矩有界。虽然许多开创性结果 [Nemirovski2009Rob, Rakhlin2012Mak, Liu2020AnI] 依赖此假设，但最近的实验证据表明，现代深度学习 [Simsekli2019ATa, Battash2024Rev, Ahn2024Lin] 和强化学习 [Garg2021OnP] 中的随机噪声通常表现出重尾特性。因此，研究焦点已转向当有界方差假设不成立时算法的收敛行为，特别是当随机噪声仅具有有界 \(\mathfrak{p}\) 阶矩（\(\mathfrak{p}\in(1,2]\)）时。

在此有界 \(\mathfrak{p}\) 阶矩假设下，已知普通 SGD 的收敛性会失效 [Zhang2020Why]。为缓解此问题，裁剪 SGD（将梯度幅度缩放至预定义阈值内）已成为一种稳健的替代方案。裁剪 SGD 及其变体已被证明在期望 [Zhang2020Why] 和高概率 [Cutkosky2021Hig, Liu2023Bre, Sadiev2023Hig, Nguyen2023Imp, Nguyen2023Hig, Liu2024Hig] 下均收敛。值得注意的是，这些研究通常包含梯度归一化（见表1），并且普遍认为，当噪声方差无界时，裁剪或归一化梯度对于确保收敛是必要的。

最近，一些研究开始通过探索无裁剪 SGD（带动量）在有界 \(\mathfrak{p}\) 阶矩假设下的收敛性来挑战这一观点。Hubler2025Fro 证明了归一化 SGD 即使没有裁剪也能以高概率收敛。Liu2025Non 首次建立了带动量的归一化 SGD 在期望下的收敛性，当尾指数 \(\mathfrak{p}\) 已知时达到 \(\mathcal{O}\left(T^{-\frac{\mathfrak{p}-1}{3\mathfrak{p}-2}}\right)\) 的速率，当未知时达到 \(\mathcal{O}\left(T^{-\frac{\mathfrak{p}-1}{2\mathfrak{p}}}\right)\) 的速率。最近，Fatkhullin2025Can 和 He2025Acc 证明了没有任何归一化或裁剪的普通 SGD 确实可以在期望下收敛。受这些最新进展的启发，我们决定研究普通带动量 SGD 在重尾噪声下的收敛速率。

表 1：在重尾噪声下，相关工作与本文在假设、算法特性和收敛速率方面的比较。缩写 "w.o. Clip."、"w.o. Norm." 和 "w. Mom." 分别表示 "无梯度裁剪"、"无梯度归一化" 和 "带动量"。

| 参考文献 | 函数 | 光滑性 | w.o. Clip. | w.o. Norm. | w. Mom. | 速率 |
| :--- | :--- | :--- | :--- | :--- | :--- | :--- |
| Zhang2020Why | S.C. | L-光滑 | × | × | × | \(\mathcal{O}(T^{-\frac{2(\mathfrak{p}-1)}{\mathfrak{p}}})\) |
| Sadiev2023Hig | S.C. | L-光滑 | × | ✓ | × | \(\mathcal{O}(T^{-\frac{2(\mathfrak{p}-1)}{\mathfrak{p}}})\) |
| Fatkhullin2025Can | S.C. | Hölder-光滑 | ✓ | ✓ | × | \(\mathcal{O}(T^{-(\mathfrak{p}-1)})\) |
| Ours (定理3.1) | S.C. | Hölder-光滑 | ✓ | ✓ | × | \(\mathcal{O}\left(T^{-(\mathfrak{p}-1)}\right)\) |
| Ours (定理3.2) | S.C. | Hölder-光滑 | ✓ | ✓ | ✓ | \(\mathcal{O}\Big((1-\eta)^T+\eta^{\mathfrak{p}}\Big)\) |
| Sadiev2023Hig | C. | L-光滑 | × | ✓ | × | \(\mathcal{O}(T^{-\frac{\mathfrak{p}-1}{\mathfrak{p}}})\) |
| Fatkhullin2025Can | C. | Hölder-光滑 | ✓ | ✓ | × | \(\mathcal{O}(T^{-\frac{\mathfrak{p}-1}{\mathfrak{p}}})\) |
| Ours (定理3.3) | C. | Hölder-光滑 | ✓ | ✓ | × | \(\mathcal{O}\Big(\frac{\log T}{T^{(\mathfrak{p}-1)/\mathfrak{p}}}\Big)\) |
| Ours (定理3.4) | C. | Hölder-光滑 | ✓ | ✓ | ✓ | \(\mathcal{O}\left(\frac{1}{\eta T}+\eta^{\mathfrak{p-1}}\right)\) |
| Zhang2020Why | N.C. | L-光滑 | × | × | × | \(\mathcal{O}(T^{-\frac{\mathfrak{p}-1}{3\mathfrak{p}-2}})\) |
| Cutkosky2021Hig | N.C. | L-光滑 | × | × | ✓ | \(\mathcal{O}(T^{\frac{\mathfrak{p}-1}{3\mathfrak{p}-2}})\) |
| Liu2023Bre | N.C. | L-光滑 | × | × | ✓ | \(\mathcal{O}(T^{-\frac{\mathfrak{p}-1}{3\mathfrak{p}-2}})\) |
| Sadiev2023Hig | N.C. | L-光滑 | × | ✓ | × | \(\mathcal{O}(T^{-\frac{\mathfrak{p}-1}{\mathfrak{p}}})\) |
| Nguyen2023Hig | N.C. | L-光滑 | × | × | × | \(\mathcal{O}(T^{-\frac{\mathfrak{p}-1}{3\mathfrak{p}-2}})\) |
| Hubler2025Fro | N.C. | L-光滑 | ✓ | × | × | \(\mathcal{O}(T^{-\frac{\mathfrak{p}-1}{3\mathfrak{p}-2}})\) |
| Liu2025Non | N.C. | \((L_0,L_1)\)-光滑 | ✓ | × | ✓ | \(\mathcal{O}(T^{-\frac{\mathfrak{p}-1}{3\mathfrak{p}-2}})\) |
| Fatkhullin2025Can | N.C. | Hölder-光滑 | ✓ | ✓ | × | \(\mathcal{O}(T^{-\frac{\mathfrak{p}-1}{\mathfrak{p}}})\) |
| Ours (定理3.5) | N.C. | Hölder-光滑 | ✓ | ✓ | × | \(\mathcal{O}\Big(\frac{\log T}{T^{(\mathfrak{p}-1)/\mathfrak{p}}}\Big)\) |
| Ours (定理3.6) | N.C. | Hölder-光滑 | ✓ | ✓ | ✓ | \(\mathcal{O}\Big(T^{-\frac{\mathfrak{p}-1}{2\mathfrak{p}}}\Big)\) |

我们的贡献可总结如下：

1.  我们首次提供了带动量普通 SGD 在重尾噪声下对强凸、凸和非凸函数收敛的理论保证。具体而言，对于非凸目标，当尾指数 \(\mathfrak{p}\in(1,2]\) 已知时，我们建立了 \(\mathcal{O}\left(T^{-\frac{\mathfrak{p}-1}{2\mathfrak{p}}}\right)\) 的收敛速率；当未知时，速率为 \(\mathcal{O}\left(T^{-\frac{\mathfrak{p}-1}{4}}\right)\)（见定理 3.6）。虽然这些速率略逊于带动量的归一化 SGD [Liu2025Non]，但我们的发现揭示了普通带动量 SGD 在重尾噪声下的表现，为未来的算法改进提供了基本基线。

2.  我们证明了普通 SGD 在重尾噪声下对所有三类目标函数在期望中收敛。与现有工作 [Fatkhullin2025Can] 相比，我们的结果不需要有界梯度假设，并且在显著更弱的条件下成立，提供了更通用和稳健的理论框架。

3.  通过在合成函数上的实验，我们证明了条件 \(\nu+1 \leq \mathfrak{p}\) 对于普通带动量 SGD 的稳定收敛至关重要。这里，\(\nu \in (0,1]\) 是 Hölder 连续性参数（假设 2.1），\(\mathfrak{p} \in (1,2]\) 是尾指数（假设 2.2）。该条件突显了我们的理论与实证观察之间的重要契合（第 4 节）。值得注意的是，由于当噪声是严格重尾时（\(\mathfrak{p}<2\)），标准的 \(L\)-光滑性（\(\nu=1\)）不满足此条件，我们的结果表明 Hölder 光滑性在此类设置下是更合适且更通用的分析框架。

## 2 预备知识

#### 符号表示

设 \(\mathbb{N}\) 为非负整数集。对于 \(m \in \mathbb{N} \setminus \{0\}\)，定义 \([m]:=\{1,2,\ldots,m\}\)。设 \(\mathbb{R}^d\) 为 \(d\) 维欧几里得空间，内积为 \(\langle\cdot,\cdot\rangle\)，由此导出范数 \(\|\cdot\|\)。设 \((x_t)_{t\ge 1} \subset \mathbb{R}^d\) 表示算法 1 中递推生成的迭代序列。设 \(\xi\) 为随机变量，\(\mathbb{E}_\xi[X]\) 表示随机变量 \(X\) 关于 \(\xi\) 的期望。\(\xi_{t,i}\) 是在时间 \(t\) 第 \(i\) 次采样生成的随机变量，且 \(\bm{\xi}_t := (\xi_{t,1},\xi_{t,2},\ldots,\xi_{t,b})^\top\) 与 \((x_k)_{k=0}^t\) 独立，其中 \(b \in [n]\) 是批大小。\(\bm{\xi}_1, \bm{\xi}_2, \ldots\) 的独立性使得我们可以定义总期望 \(\mathbb{E}\) 为 \(\mathbb{E} = \mathbb{E}_{\bm{\xi}_1} \mathbb{E}_{\bm{\xi}_2} \cdots \mathbb{E}_{\bm{\xi}_t}\)。设 \(\mathsf{G}_\xi(\bm{x})\) 为 \(f(\cdot)\) 在 \(\bm{x} \in \mathbb{R}^d\) 处的随机梯度。小批量 \(\mathcal{S}_t\) 在时间 \(t\) 由 \(b\) 个样本组成，对于 \(\mathcal{S}_t\)，\(f(\bm{x})\) 的小批量随机梯度定义为
\[\nabla f_{\mathcal{S}_t}(\bm{x}) := \frac{1}{b} \sum_{i\in[b]} \mathsf{G}_{\xi_{t,i}}(\bm{x}) = \frac{1}{b} \sum_{i\in \mathcal{S}_t} \nabla f_i(\bm{x}).\]
在强凸和凸情况下，我们记 \(\bm{x}^\star \in \operatorname*{argmin}_{\bm{x}\in\mathbb{R}^d} f(\bm{x})\) 和 \(f^\star := f(\bm{x}^\star)\)。我们将既不使用归一化也不使用裁剪的带动量 SGD 称为普通带动量 SGD。此外，我们将通过设置算法 1 中 \(\beta=0\) 得到的无动量普通 SGD 简称为普通 SGD。

**算法 1** 普通带动量 SGD
0: \(x_1 \in \mathbb{R}^d\), \(\eta_t > 0\), \(b \in [n]\), \(\beta \in [0,1)\), \(m_0 := 0\), \(T \in \mathbb{N}\)
for \(t = 1\) to \(T\) do
    \(m_t := \beta m_{t-1} + (1-\beta) \nabla f_{\mathcal{S}_t}(x_t)\)
    \(x_{t+1} := x_t - \eta_t m_t\)
end for
return \(x_{T+1}\)

我们做出以下假设。

###### 假设 2.1。
\(\nabla f: \mathbb{R}^d \to \mathbb{R}^d\) 是 Hölder 连续的；即存在 \(\nu \in (0,1]\) 和 \(L>0\)，使得对所有 \(\bm{x}, \bm{y} \in \mathbb{R}^d\)，
\[\|\nabla f(\bm{x}) - \nabla f(\bm{y})\| \le L \|\bm{x} - \bm{y}\|^\nu.\]

###### 假设 2.2。
(i) 对于所有不依赖于 \(\xi\) 的 \(\bm{x} \in \mathbb{R}^d\)，
\[\mathbb{E}_\xi[\mathsf{G}_\xi(\bm{x})] = \nabla f(\bm{x}).\]
(ii) 存在 \(\sigma \ge 0\) 和 \(\mathfrak{p} \in (1,2]\)，使得对所有不依赖于 \(\xi\) 的 \(\bm{x} \in \mathbb{R}^d\)，
\[\mathbb{E}_\xi[\|\mathsf{G}_\xi(\bm{x}) - \nabla f(\bm{x})\|^{\mathfrak{p}}] \le \sigma^{\mathfrak{p}}.\]

假设 2.1 是我们分析的核心。由于当 \(\nu=1\) 时它退化为标准 \(L\)-光滑性，因此该假设是 \(L\)-光滑性的扩展。假设 2.2 (ii) 是分析重尾噪声下优化器的标准条件，广泛应用于之前的研究中 [Zhang2020Why, Cutkosky2021Hig, Sadiev2023Hig, Nguyen2023Imp, Chezhegov2025Cli]。当 \(\mathfrak{p}=2\) 时，它退化为标准的有界方差假设 [Nemirovski2009Rob, Ghadimi2012Opt, Ghadimi2013Sto]；当 \(\mathfrak{p}<2\) 时，随机梯度可能具有无界方差。

### 2.1 重尾分析工具

以下引理对于重尾噪声下的分析很有用。为完整起见，我们将其证明包含在附录 A 中。

###### 引理 2.1。
假设假设 2.1 成立。那么对所有 \(\bm{x}, \bm{y} \in \mathbb{R}^d\)，以下不等式成立：
\[f(\bm{y}) \le f(\bm{x}) + \langle \nabla f(\bm{x}), \bm{y}-\bm{x} \rangle + \frac{L}{\nu+1} \|\bm{y}-\bm{x}\|^{\nu+1}.\]

###### 引理 2.2。
设 \(q \in (1,2]\)。对于任意 \(\bm{y} \in \mathbb{R}^d\) 和任意 \(\bm{x} \in \mathbb{R}^d \setminus \{\bm{0}\}\)，以下不等式成立：
\[\|\bm{x} \pm \bm{y}\|^q \le \|\bm{x}\|^q \pm q \|\bm{x}\|^{q-2} \langle \bm{x}, \bm{y} \rangle + 2^{2-q} \|\bm{y}\|^q.\]

###### 引理 2.3。
假设假设 2.2 成立。那么对所有 \(t \in \mathbb{N}\) 和所有不依赖于 \(\bm{\xi}_t\) 的 \(\bm{x} \in \mathbb{R}^d\)，以下不等式成立：
\[\mathbb{E}_{\bm{\xi}_t} \left[ \| \nabla f_{\mathcal{S}_t}(\bm{x}) - \nabla f(\bm{x}) \|^{\mathfrak{p}} \right] \le \frac{C_{\mathfrak{p}} \sigma^{\mathfrak{p}}}{b^{\mathfrak{p}-1}},\]
其中 \(C_{\mathfrak{p}} \in [1,2)\) 是引理 A.1 中给出的常数。

###### 引理 2.4。
设 \(\mathfrak{p} \in (1,2]\) 且 \(\nu \in