On the Last-Iterate Convergence of Clipped Gradient Methods¶

会议: NeurIPS 2026
arXiv: 2610.21026
领域: 优化/理论
关键词: 随机凸优化, 梯度裁剪, 最后迭代收敛, 重尾噪声, 高概率界

一句话总结¶

针对随机（强）凸优化中存在重尾梯度噪声的现实设定，本文首次证明了 Clipped-SGD 的末次迭代（last-iterate）在具有高概率保证下的最优收敛速率，填补了现有理论中仅适用于轻尾假设或速率次优的长期空白。

研究背景与动机¶

在现代机器学习的大规模模型训练与随机优化理论中，建立一阶优化算法的最后迭代（last-iterate）收敛保证已成为理论界与工业界关注的核心课题。相比于传统的遍历平均迭代（average-iterate），实际深度学习训练管线（如 Transformer 与大语言模型）几乎均采用最终步的模型权重输出，因此最后迭代的收敛界与实际工程行为契合得最为紧密。现有针对经典随机梯度下降（SGD）的最后迭代收敛性证明通常严重依赖于对随机梯度噪声的强假设，例如期望收敛所要求的有限方差条件，或高概率收敛所要求的指数衰减尾部（如次高斯噪声）。

然而，越来越多的实证与理论研究表明，现代深度学习训练中的梯度噪声广泛呈现重尾分布（heavy-tailed noise），其二阶矩甚至可能不存在，而仅存在 $\mathtt{p} \in (1, 2]$ 阶矩。在面对重尾噪声时，标准 SGD 不仅在高概率界下表现出对失败概率 $\delta$ 的多项式依赖 $\mathrm{poly}(1/\delta)$，甚至在期望意义下都会发散。为了对抗重尾噪声，引入梯度裁剪机制的 Clipped-SGD 成为大模型训练的事实标准。然而，Clipped-SGD 的最后迭代收敛理论极为匮乏：在非光滑凸优化下仅知期望收敛界，而在光滑凸优化下的高概率最后迭代界速率显著次优（阶数为 $\mathcal{O}(T^{-\frac{2}{3}(1-\frac{1}{\mathtt{p}})})$），落后于平均迭代的已知最优界，且当 $\mathtt{p}=2$ 时甚至退化到比 SGD 更慢的 $\mathcal{O}(T^{-1/3})$。

由此产生的核心科学问题是：在重尾梯度噪声下，能否为 Clipped-SGD 的最后迭代建立在时间跨度 $T$ 与置信度 $\delta$ 上完全达到最优、且能与平均迭代高概率界完全匹配的严格理论保证？核心 idea：本文通过引入线性衰减步长与精细动态裁剪阈值设计，配合突破传统数学归纳法的全新极大值鞅差集中论证，首次证明了 Clipped-SGD 在一般凸与强星凸目标（覆盖光滑与非光滑）下的高概率最后迭代最优收敛速率，并消除了对置信度的次优对数多项式惩罚。

方法详解¶

整体框架¶

本文研究复合随机凸优化问题：$\min_{\boldsymbol{x} \in \mathcal{X}} F(\boldsymbol{x}) \triangleq f(\boldsymbol{x}) + r(\boldsymbol{x})$，其中 $\mathcal{X} \subseteq \mathbb{R}^d$ 为非空闭凸集，$f$ 为凸目标函数（可能满足 Lipschitz 连续或光滑性），$r$ 为可能非光滑的凸正则项。算法在每一步接收随机梯度 $\boldsymbol{g}_t = \boldsymbol{g}(\boldsymbol{x}_t; Z_t)$，采用阈值 $\tau_t$ 进行自适应模长截断，随后通过近端算子更新迭代点 $\boldsymbol{x}_{t+1}$。

整体优化管线由自适应噪声参数感知、动态阈值截断、前向-反向步进更新以及支撑整套收敛证明的势函数鞅差分析构成。根据凸性强弱的不同，算法采用单阶段或双阶段调度方案，从几何距离收缩逐步过渡到函数值最后迭代的最优极限定理。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入: 初始点 x_1, 时间步长 T, 噪声参数 (p, σ_s, σ_l)"] --> B["阶段划分与超参决定<br/>凸目标: 单阶段 / 强凸目标: 双阶段 (S=⌈T/2⌉)"]
    B --> C["梯度采样与动态模长裁剪<br/>g_t^c = clip_τ_t(g_t)"]
    C --> D["线性衰减步长近端投影更新<br/>优化子问题求解 argmin 产生 x_t+1"]
    D --> E["鞅差序列残差势函数收缩<br/>基于一致有界极大值技术控制轨迹偏离"]
    E --> F["输出: 最终最后迭代点 x_T+1 (最优高概率保证)"]

关键设计¶

1. 精细化重尾噪声建模与自适应参考阈值设计 针对重尾噪声传统模型中将所有方向噪声一并放大的缺陷，本文采用了区分一维投影与整体高维模长的精细重尾噪声假设：任意单位向量 $\boldsymbol{e} \in \mathbb{S}^{d-1}$ 满足 $\mathbb{E}[|\langle \boldsymbol{e}, \boldsymbol{g}(\boldsymbol{x}) - \nabla f(\boldsymbol{x}) \rangle|^\mathtt{p}] \leq \sigma_\mathtt{s}^\mathtt{p}$，而高维总模长满足 $\mathbb{E}[\|\boldsymbol{g}(\boldsymbol{x}) - \nabla f(\boldsymbol{x})\|^\mathtt{p}] \leq \sigma_\mathtt{l}^\mathtt{p}$。由此引入广义有效维度 $d_{\mathtt{eff}} \triangleq \sigma_\mathtt{l}^2 / \sigma_\mathtt{s}^2$ 及核心归一化阈值常数： $$\tau_\star \triangleq \left(\min\left\{\frac{\sigma_\mathtt{s}\sigma_\mathtt{l}^{\mathtt{p}-1}}{\ln(3/\delta)},\, \frac{\sigma_\mathtt{s}^2}{\sigma_\mathtt{l}^{2-\mathtt{p}}\mathbb{I}[\mathtt{p}<2]}\right\}\right)^{\frac{1}{\mathtt{p}}}$$ 该设计使得截断阈值能够在各向异性或极高维空间中准确平衡无偏截断误差与残余方差，成为后续在高概率界中彻底剥离不利维度爆炸与松弛因子的关键基石。

2. 匹配最后迭代收敛的线性衰减步长与两阶段阈值调度 传统最后迭代分析若沿用常数步长往往只能得到次优速率或必须引入复杂的切比雪夫加权平均。本文针对凸优化采用了形如 $\eta_t = \eta_\star (T - t + 1)$ 的线性递减步长，使得越靠后的迭代步长衰减越迅速，有效锁住靠近最优点附近的函数值。而在强星凸设定下，算法设计了分水岭为 $S = \lceil T/2 \rceil$ 的两阶段更新法则：前半程 $t \leq S$ 采用 $\eta_t = \frac{6}{\mu t}$ 快速收缩到最优解的欧氏距离邻域内；后半程 $t > S$ 切换为 $\eta_t = \frac{T - t + 1}{\mu T^2}$，并将裁剪阈值固定在 $\tau_\star \lfloor T/2 \rfloor^{1/\mathtt{p}}$ 水平，成功将距离收敛光滑桥接到最终点函数值差距的高阶衰减。

3. 突破传统数学归纳法的均匀有界性鞅集中分析 在光滑优化分析中，控制全轨迹梯度范数依赖于证明所有迭代点与最优解距离均匀有界 $\sup_{t \leq T+1} \|\boldsymbol{x}_t - \boldsymbol{x}_\star\|^2 = \mathcal{O}(D^2)$。以往文献采用标准数学归纳法结合 Freedman 不等式，因每步对失败概率做联合界分割，不可避免地引入次优的 $\mathrm{poly}(\ln(T/\delta))$ 膨胀因子。本文提出了一套逆向吸收论证：直接构造全时程极大值事件 $E \triangleq \{\max_{t \in [T]} |\sum_{s=1}^t X_s \zeta_s| \leq \mathcal{O}(\max_t h_{1,t} \ln(1/\delta) + \sqrt{\sum_t h_{2,t} \ln(1/\delta)})\}$，利用 Freedman 不等式对鞅最大值直接给出一笔 $\delta$ 的概率界，随后通过集合包含关系 $E \cap E_t \subseteq \{\zeta_{t+1}=1\}$ 严格递推证明 $E_{T+1} \supseteq E$，不仅将集中不等式的调用次数严格压制为一次，而且在理论界中完全抹去了对总步数 $T$ 的对数依赖，锁定了严格最优的 $\ln(1/\delta)$ 阶次。

理论分析与设计权衡¶

本套方法的理论分析核心在于利用辅助加权序列 $v_t^2 \triangleq \eta_T / \sum_{s=t}^T \eta_s$ 构造关于凸组合点 $\boldsymbol{z}_t$ 的非对称下降势函数。通过将裁剪随机梯度精准分解为无偏扰动 $\boldsymbol{d}_t^\mathrm{u}$ 与有偏截断残差 $\boldsymbol{d}_t^\mathrm{b}$，再利用矩阵算子范数界分别控制一阶鞅差和二次累积方差。在光滑目标下，通过引入点到初值距离的自适应动态截断项 $2L\|\boldsymbol{x}_t - \boldsymbol{x}_1\| + 2G_1$，巧妙规避了全局 Lipschitz 梯度的硬性假设，同时保持了截断操作对任意强重尾梯度的鲁棒包络。

实验关键数据¶

主实验：不同优化问题设定下的收敛速率对比¶

作为纯理论优化奠基性工作，论文在数学上严格证明并导出了各设定下的高概率最后迭代上界，并与已有文献的最优平均迭代（average-iterate）上界及信息论下界形成精确比对：

优化问题类别	目标函数性质	噪声设定	本文最后迭代上界 (Last-Iterate)	已知最佳平均迭代上界 (Average)	理论极小极大下界 (Lower Bound)
一般凸优化 ($\mu=0$)	$G$-Lipschitz 非光滑	经典重尾 ($\sigma_\mathtt{s}=\sigma_\mathtt{l}$)	$\mathcal{O}\left(\frac{\sigma D \ln^{1-1/\mathtt{p}}(1/\delta)}{T^{1-1/\mathtt{p}}}\right)$	$\mathcal{O}\left(\frac{\sigma D \ln^{1-1/\mathtt{p}}(1/\delta)}{T^{1-1/\mathtt{p}}}\right)$ [Liu, 2026]	$\Omega\left(\frac{\sigma D \ln^{1-1/\mathtt{p}}(1/\delta)}{T^{1-1/\mathtt{p}}}\right)$ [Liu, 2026]
一般凸优化 ($\mu=0$)	$L$-Smooth 光滑	经典重尾 ($\sigma_\mathtt{s}=\sigma_\mathtt{l}$)	$\mathcal{O}\left(\frac{\sigma D \ln^{1-1/\mathtt{p}}(1/\delta)}{T^{1-1/\mathtt{p}}}\right)$	$\mathcal{O}\left(\frac{\sigma D \ln^{1-1/\mathtt{p}}(1/\delta)}{T^{1-1/\mathtt{p}}}\right)$ [Nguyen et al., 2023]	理论完全匹配最优阶
强星凸优化 ($\mu>0$)	$G$-Lipschitz 非光滑	经典重尾 ($\sigma_\mathtt{s}=\sigma_\mathtt{l}$)	$\mathcal{O}\left(\frac{\sigma^2 \ln^{2-2/\mathtt{p}}(1/\delta)}{\mu T^{2-2/\mathtt{p}}}\right)$	$\mathcal{O}\left(\frac{\sigma^2 \ln^{2-2/\mathtt{p}}(1/\delta)}{\mu T^{2-2/\mathtt{p}}}\right)$ [Liu, 2026]	$\Omega\left(\frac{\sigma^2 \ln^{2-2/\mathtt{p}}(1/\delta)}{\mu T^{2-2/\mathtt{p}}}\right)$ [Liu, 2026]
强星凸优化 ($\mu>0$)	$L$-Smooth 光滑	经典重尾 ($\sigma_\mathtt{s}=\sigma_\mathtt{l}$)	$\mathcal{O}\left(\frac{\sigma^2 \ln^{2-2/\mathtt{p}}(1/\delta)}{\mu [T(T+\kappa)]^{1-1/\mathtt{p}}}\right)$	优于 $\widetilde{\mathcal{O}}\left(\frac{\sigma^2 \ln^{2-2/\mathtt{p}}(T/\delta)}{\mu T^{2-2/\mathtt{p}}}\right)$ [Sadiev et al., 2023]	移除了多余的 $\ln(T)$ 项

消融实验：技术假设与现有文献最后迭代结论对比分析¶

下表系统对比了本文提出的高概率收敛技术与前序代表性工作的收敛准则、噪声假设及速率阶数退化情况：

方法与理论来源	收敛判定度量	梯度噪声尾部假设	时间步长 $T$ 速率依赖	置信度 $\delta$ 依赖	是否匹配下界
Parletta et al. [2024]	期望收敛 $\mathbb{E}[F(\boldsymbol{x}_{T+1}) - F_\star]$	重尾噪声 $\mathtt{p} \in (1,2]$	$\mathcal{O}(T^{-(1-1/\mathtt{p})})$	无高概率保证	仅期望最优
Chezhegov et al. [2026]	高概率 $F(\boldsymbol{x}_{T+1}) - F_\star$	经典重尾光滑凸	$\mathcal{O}(T^{-\frac{2}{3}(1-1/\mathtt{p})})$ (次优)	$\ln^2(T/\delta)$ (次优)	否 ($\mathtt{p}=2$ 时退化为 $T^{-1/3}$)
Sadiev et al. [2023]	高概率 $\mu\\|\boldsymbol{x}_{T+1} - \boldsymbol{x}_\star\\|^2$	经典重尾强凸光滑	$\mathcal{O}(T^{-(2-2/\mathtt{p})})$	$\ln^{2-2/\mathtt{p}}(T/\delta)$ (含 $T$)	弱于函数值差距度量
本文 (Theorem 1 & 2)	高概率 $F(\boldsymbol{x}_{T+1}) - F_\star$	精细重尾各向异性	$\mathcal{O}(T^{-(1-1/\mathtt{p})})$ (完全最优)	$\ln^{1-1/\mathtt{p}}(1/\delta)$ (无 $T$)	是 (全参数最优)
本文 (Theorem 3 & 4)	高概率 $F(\boldsymbol{x}_{T+1}) - F_\star$	精细重尾各向异性	$\mathcal{O}(T^{-(2-2/\mathtt{p})})$ (完全最优)	$\ln^{2-2/\mathtt{p}}(1/\delta)$ (无 $T$)	是 (强于距离度量)

关键发现¶

首次揭示了 Clipped-SGD 并不需要依赖任何复杂的加权迭代平均（如多项式加权平均或局部滑动窗口平均），仅通过线性衰减步长即可直接驱动最后迭代点收敛到与平均迭代相同的理论极限。
彻底解决了过去在光滑凸优化高概率界分析中因多轮联合界归纳法导致的 $\mathrm{poly}(\ln(T/\delta))$ 次优膨胀问题，利用全局极大值吸收法恢复了纯净的 $\ln(1/\delta)$ 依赖。
理论度量全面升级：在强凸设定下，过去文献多局限于参数距离度量 $\mu\|\boldsymbol{x}_{T+1} - \boldsymbol{x}_\star\|^2$，而根据引理该度量严格弱于目标函数值残差 $F(\boldsymbol{x}_{T+1}) - F_\star$。本文直接证明了函数值残差的收敛，给出了更强的一阶理论保障。

亮点与洞察¶

步长与截断阈值的解耦协同：巧妙利用递减步长压低末期方差累积，同时令截断阈值保持宏观尺度，在阻断极端异常梯度的同时最小化截断引入的有偏漂移，实现了方差与偏差的渐近最优平衡。
极大值鞅差集中论证的新范式：提出的"全局极大有界事件逆向吸收"分析框架，可直接作为即插即用的数学工具迁移至强化学习、自适应算法等各类需要控制迭代轨迹有界性的高概率收敛性证明中。

局限与展望¶

算法参数（包括步长与裁剪阈值）的精确选定仍需要先验知晓重尾指数 $\mathtt{p}$，而在真实复杂数据场景中该尾部指数往往未知且极难在线准确估计，发展无需 $\mathtt{p}$ 的参数自适应方法是重要开放问题。
当前证明依赖于总时间步数 $T$ 提前已知的设定（fixed-horizon），暂无法直接无缝推广到任意时刻均成立的随时在线（anytime）收敛框架。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次证明了重尾噪声下 Clipped-SGD 的高概率最后迭代最优界，理论技术创新显著。
实验充分度: ⭐⭐⭐⭐☆ 纯数学与优化理论论文，数学推导极其严密完备，覆盖凸与强星凸、光滑与非光滑全部主流场景。
写作质量: ⭐⭐⭐⭐⭐ 结构清晰透彻，核心分析技巧阐述精辟，定理条件与推导脉络无懈可击。
价值: ⭐⭐⭐⭐⭐ 彻底解决了一阶随机优化与梯度截断领域一个长久未决的核心理论问题。

优化问题类别	目标函数性质	噪声设定	本文最后迭代上界 (Last-Iterate)	已知最佳平均迭代上界 (Average)	理论极小极大下界 (Lower Bound)
一般凸优化 (\(\mu=0\))	\(G\)-Lipschitz 非光滑	经典重尾 (\(\sigma_\mathtt{s}=\sigma_\mathtt{l}\))	\(\mathcal{O}\left(\frac{\sigma D \ln^{1-1/\mathtt{p}}(1/\delta)}{T^{1-1/\mathtt{p}}}\right)\)	\(\mathcal{O}\left(\frac{\sigma D \ln^{1-1/\mathtt{p}}(1/\delta)}{T^{1-1/\mathtt{p}}}\right)\) [Liu, 2026]	\(\Omega\left(\frac{\sigma D \ln^{1-1/\mathtt{p}}(1/\delta)}{T^{1-1/\mathtt{p}}}\right)\) [Liu, 2026]
一般凸优化 (\(\mu=0\))	\(L\)-Smooth 光滑	经典重尾 (\(\sigma_\mathtt{s}=\sigma_\mathtt{l}\))	\(\mathcal{O}\left(\frac{\sigma D \ln^{1-1/\mathtt{p}}(1/\delta)}{T^{1-1/\mathtt{p}}}\right)\)	\(\mathcal{O}\left(\frac{\sigma D \ln^{1-1/\mathtt{p}}(1/\delta)}{T^{1-1/\mathtt{p}}}\right)\) [Nguyen et al., 2023]	理论完全匹配最优阶
强星凸优化 (\(\mu>0\))	\(G\)-Lipschitz 非光滑	经典重尾 (\(\sigma_\mathtt{s}=\sigma_\mathtt{l}\))	\(\mathcal{O}\left(\frac{\sigma^2 \ln^{2-2/\mathtt{p}}(1/\delta)}{\mu T^{2-2/\mathtt{p}}}\right)\)	\(\mathcal{O}\left(\frac{\sigma^2 \ln^{2-2/\mathtt{p}}(1/\delta)}{\mu T^{2-2/\mathtt{p}}}\right)\) [Liu, 2026]	\(\Omega\left(\frac{\sigma^2 \ln^{2-2/\mathtt{p}}(1/\delta)}{\mu T^{2-2/\mathtt{p}}}\right)\) [Liu, 2026]
强星凸优化 (\(\mu>0\))	\(L\)-Smooth 光滑	经典重尾 (\(\sigma_\mathtt{s}=\sigma_\mathtt{l}\))	\(\mathcal{O}\left(\frac{\sigma^2 \ln^{2-2/\mathtt{p}}(1/\delta)}{\mu [T(T+\kappa)]^{1-1/\mathtt{p}}}\right)\)	优于 \(\widetilde{\mathcal{O}}\left(\frac{\sigma^2 \ln^{2-2/\mathtt{p}}(T/\delta)}{\mu T^{2-2/\mathtt{p}}}\right)\) [Sadiev et al., 2023]	移除了多余的 \(\ln(T)\) 项

方法与理论来源	收敛判定度量	梯度噪声尾部假设	时间步长 \(T\) 速率依赖	置信度 \(\delta\) 依赖	是否匹配下界
Parletta et al. [2024]	期望收敛 \(\mathbb{E}[F(\boldsymbol{x}_{T+1}) - F_\star]\)	重尾噪声 \(\mathtt{p} \in (1,2]\)	\(\mathcal{O}(T^{-(1-1/\mathtt{p})})\)	无高概率保证	仅期望最优
Chezhegov et al. [2026]	高概率 \(F(\boldsymbol{x}_{T+1}) - F_\star\)	经典重尾光滑凸	\(\mathcal{O}(T^{-\frac{2}{3}(1-1/\mathtt{p})})\) (次优)	\(\ln^2(T/\delta)\) (次优)	否 (\(\mathtt{p}=2\) 时退化为 \(T^{-1/3}\))
Sadiev et al. [2023]	高概率 \(\mu\\|\boldsymbol{x}_{T+1} - \boldsymbol{x}_\star\\|^2\)	经典重尾强凸光滑	\(\mathcal{O}(T^{-(2-2/\mathtt{p})})\)	\(\ln^{2-2/\mathtt{p}}(T/\delta)\) (含 \(T\))	弱于函数值差距度量
本文 (Theorem 1 & 2)	高概率 \(F(\boldsymbol{x}_{T+1}) - F_\star\)	精细重尾各向异性	\(\mathcal{O}(T^{-(1-1/\mathtt{p})})\) (完全最优)	\(\ln^{1-1/\mathtt{p}}(1/\delta)\) (无 \(T\))	是 (全参数最优)
本文 (Theorem 3 & 4)	高概率 \(F(\boldsymbol{x}_{T+1}) - F_\star\)	精细重尾各向异性	\(\mathcal{O}(T^{-(2-2/\mathtt{p})})\) (完全最优)	\(\ln^{2-2/\mathtt{p}}(1/\delta)\) (无 \(T\))	是 (强于距离度量)