Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise¶

会议: NeurIPS 2026
arXiv: 2605.17394
OpenReview: https://openreview.net/forum?id=KNeGuHB7Md
领域: 优化/理论
关键词: 零阶优化, 重尾噪声, 标量截断, 非凸优化, 动量机制

一句话总结¶

针对机器学习中普遍存在的无限方差重尾梯度噪声，本文提出基于共享随机性与单方向标量截断的双点零阶优化算法 RSC-ZO 及其动量变体，在弱 $L_p$ 条件下首次建立了非凸零阶高概率收敛界，实现了匹配一阶下界的 $\widetilde{O}(d^{\frac{p}{2(p-1)}}\varepsilon^{-\frac{3p-2}{p-1}})$ 查询复杂度。

研究背景与动机¶

在缺乏显式梯度信息或反向传播开销难以承受的场景（如黑盒对抗攻防、强化学习策略搜索、大规模语言模型前向微调 MeZO 等）中，随机零阶（Zeroth-Order, ZO）优化通过有限差分构造目标函数梯度的替代估计，成为核心求解工具。经典非凸随机零阶理论主要建立在样本函数逐点光滑和样本梯度噪声方差有界的假设之上，已证明在期望意义下找到 $\varepsilon$-稳定点需要 $O(d\,\varepsilon^{-4})$ 次函数查询。

然而，现代机器学习实践（如 BERT 预训练、大规模图像分类与强化学习 PPO）的大量实证研究表明，随机梯度噪声往往表现出强烈的重尾特征，其经验方差甚至随样本量增加而无法收敛，对应尾指数 $p \in (1, 2]$ 的重尾甚至无限方差分布。虽然一阶随机优化已通过向量截断（Gradient Clipping）和动量技术，在有界 $p$ 阶矩噪声下取得了匹配下界的理论突破，但这一成果无法直接平凡推广至零阶设定：一阶方法直接观测带有重尾扰动的梯度向量，而零阶方法仅能查询受噪声污染的标量函数值。由于零阶估计需通过随机方向有限差分构建，若直接在聚合后施加向量截断，极端离群扰动会彻底带偏梯度估计方向；反之若不加截断，重尾噪声引发的剧烈数值振荡会导致整个更新轨迹崩溃。

面对如何将样本梯度的弱 $L_p$ 尾部分布控制有效传递到标量方向差分估计上的核心理论瓶颈，本文摒弃了在聚合后做粗糙向量截断的传统思路，提出直接在每个采样方向差分上执行标量截断。核心 idea：利用双点共享随机性与球面平滑消除函数值独立噪声发散，在求和聚合前对每个一维方向导数估计施加标量截断，建立首个非凸重尾弱 $L_p$ 噪声下的高概率零阶收敛界并给出小批量动量加速权衡。

方法详解¶

整体框架¶

算法面向光滑非凸随机优化问题 $\min_{x\in\mathbb{R}^d} f(x) := \mathbb{E}_{\xi\sim\mathbb{P}}[F(x;\xi)]$。算法的核心流程包含四个逻辑阶段：首先在单位球面 $\mathbb{S}^{d-1}$ 上均匀抽取扰动方向并采样随机批次，接着在正负扰动点上使用完全相同的随机数种子计算双点对称有限差分；随后对每个独立的标量方向差分应用软截断算子以抵御重尾噪声；最后沿抽样方向重构并放大 $d$ 倍作为拟梯度，输入给基准梯度下降或滑动平均动量递归更新。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["当前参数点 xt 与噪声种子 ξ 采样"] --> B["阶段1：双点共享随机性有限差分<br/>对称采样正负微扰函数值并计算方向差分"]
    B --> C["阶段2：一维标量方向导数截断<br/>对单标量施加阈值限制抑制重尾异常值"]
    C --> D["阶段3：高维方向加权聚合与拟梯度重构<br/>按扰动方向向量重构球面平滑代理梯度"]
    D -->|基准更新 (β=0)| E["输出：确定性步长参数更新 xt+1"]
    D -->|动量更新 (β>0)| F["输出：预热初始化与跨步滑动平均动量更新"]

关键设计¶

1. 双点共享随机性与方向投影：消除纯函数噪声并转化梯度扰动

若在计算有限差分时不共享随机数种子（即采用两批独立噪声 $\xi^+$ 与 $\xi^-$），函数值本身的重尾波动会被差分步长 $2\mu$ 放大至 $O(\sigma/\mu)$ 级别，导致估计方差在小扰动极限下直接发散。RSC-ZO 强制在正负微扰点 $x+\mu u_\ell$ 与 $x-\mu u_\ell$ 评估同一个样本 $\xi_\ell$ 的取值： $$Y_\ell(x) := \frac{F(x+\mu u_\ell; \xi_\ell) - F(x-\mu u_\ell; \xi_\ell)}{2\mu}$$ 根据中值定理与样本光滑性假设 $\|\nabla F(x;\xi) - \nabla F(y;\xi)\|_2 \le L\|x-y\|_2$，差分被严密限制在确定性无偏方向导数 $D_\mu f(x,u_\ell)$ 加上梯度噪声投影 $\langle \nabla F(x;\xi_\ell) - \nabla f(x), u_\ell \rangle$ 及二阶平滑误差 $L\mu$ 的量级。这一机制成功将不可控的函数值扰动转化为由高维随机方向投影压缩的梯度噪声 $\sigma / \sqrt{d}$。

2. 聚合前标量截断：保方向性与解耦截断偏差

传统的重尾优化习惯在得到全维度经验均值向量后计算 $L_2$ 范数并执行向量截断（即 $\text{clip}(g_{\text{raw}})$）。然而，一旦单个采样方向遇到极端重尾梯度异常值，该异常方向将主导未截断的均值向量，后续的向量截断仅能缩放向量长度，却无法修复已被彻底污染的方向对齐（余弦相似度趋近于零）。RSC-ZO 定义单标量截断函数 $\psi_\tau(z) := z \min\{1, \tau / |z|\}$，并在加权聚合前对每个标量方向估计施加截断： $$g(x) := \frac{d}{M} \sum_{\ell=1}^M \psi_\tau(Y_\ell(x)) u_\ell$$ 该设计将高维异常过滤转化为标量统计量控制。通过建立弱 $L_p$ 条件下的尾部截断引理，将估计误差精确正交分解为无偏截断偏差项 $B := \mathbb{E}[g(x)] - \nabla f_\mu(x)$ 与有界二阶矩经验涨落项 $A := g(x) - \mathbb{E}[g(x)]$，避免了方向向量畸变。

3. 动量平滑与小批量样本缩减：解耦单步批量与跨步稳定界

在基准 RSC-ZO 中，为了控制经验涨落以满足高概率收敛，单步运行批大小需要达到 $M \gtrsim \widetilde{O}(d^{\frac{p}{2(p-1)}} \varepsilon^{-\frac{p}{p-1}})$。针对实际深度微调中显存和计算资源无法支持大 Batch 的痛点，动量 RSC-ZO 引入了预热与指数滑动平均机制：在初始点 $x_0$ 采用大批次 $M_0$ 和阈值 $\tau_0$ 完成高精度热启动 $m_0 \leftarrow g_0$，随后在迭代过程中采用高动量参数 $\beta \in [1/2, 1)$： $$m_t \leftarrow \beta m_{t-1} + (1-\beta) g_t, \quad x_{t+1} \leftarrow x_t - \alpha m_t$$ 理论证明通过构建局部 Lyapunov 能量函数 $\Phi_t := f_\mu(x_t) + \frac{2\alpha}{1-\beta}\|m_t - \nabla f_\mu(x_t) - (1-\beta)a_t\|_2^2$，动量能够复用历史轨迹信息以降低单步方差，允许将运行批大小直接按比例缩减为 $M = (1-\beta) M_0$。当选取 $\beta = 1 - \widetilde{\Theta}((\varepsilon / \mathcal{R}_\mu)^{\frac{p}{p-1}})$ 时，算法甚至可在恒定批大小 $M=1$ 下稳定收敛。

损失函数 / 训练策略¶

算法使用带参数平滑的代理函数 $f_\mu(x) := \mathbb{E}_{v\sim \text{Unif}(\mathbb{B}^d)}[f(x+\mu v)]$。基准算法设置平滑微扰半径 $\mu \asymp \varepsilon / (Ld)$，更新步长取固定确定性界 $\alpha = \frac{1}{4L}$；动量算法中步长则与动量衰减严格耦合，设为 $\alpha = \frac{1-\beta}{16\sqrt{3}L}$。对于弱 $L_p$ 参数 $p \in (1, 2]$，最优标量截断阈值配置为： $$\tau := 8 S_\mu \left( \frac{M}{\log(T/\delta)} \right)^{1/p}, \quad S_\mu := \frac{\sqrt{L\bar{\Delta}_0} + \sigma}{\sqrt{d}} + L\mu$$ 其中 $\bar{\Delta}_0 := f(x_0) - f_* + \frac{L\mu^2}{2}$ 为考虑平滑偏移后的初始函数最优间隙。

实验关键数据¶

主实验¶

论文在 RoBERTa-large（350M 参数量）预训练模型上，在固定 $k=512$ 样本的小样本（Few-shot）分类微调任务（SNLI、MNLI、TREC）中，对比了一阶全量微调、零阶标杆 MeZO 以及不同扰动采样方向数 $M \in \{1, 2, 4\}$ 下的 RSC-ZO。为确保对比公平，所有零阶方法在相同前向评估计算预算下运行，当增大 $M$ 时等比例降低训练样本批大小。

任务 / 数据集	Zero-shot	MeZO (经典无截断ZO)	RSC-ZO ($M=1$)	RSC-ZO ($M=2$)	RSC-ZO ($M=4$)	本文增益 (vs MeZO)
SNLI (自然语言推理)	50.4	74.2 (±1.5)	83.0 (±1.0)	82.0 (±0.2)	79.7 (±0.7)	+8.8%
MNLI (多域语言推理)	49.2	67.9 (±2.8)	75.5 (±0.9)	76.2 (±1.5)	76.9 (±1.3)	+9.0%
TREC (问题主题分类)	32.0	83.2 (±4.3)	92.4 (±1.2)	92.9 (±1.2)	93.5 (±0.6)	+10.3%

消融实验¶

为了严格验证“聚合前标量截断”与“聚合后向量截断”的机制性差异，作者在受控合成二次目标函数 $f(x) = \frac{1}{2}\|x\|_2^2$ 上引入稀疏重尾噪声（Pareto 尾指数 $p=1.5$，维度 $d=100$，采样方向数 $M=256$），对比不同截断策略对优化轨迹收敛性与梯度余弦相似度（Cosine Similarity）的影响。

截断策略配置	梯度对齐余弦相似度	终点梯度范数 $\\|\nabla f(x_t)\\|_2$	轨迹稳定性说明
Raw ZO (未截断基线)	~0.02 (极低且剧烈跳变)	发散 / 剧烈震荡	无法收敛，重尾扰动导致轨迹发散
Vector Clipping (向量截断: clip(g_raw))	~0.03 (几乎无提升)	停滞于高平台 (>0.4)	仅能抑制更新步长爆炸，方向严重失真
Scalar Clipping (本文标量截断: RSC-ZO)	0.88 (高精度稳定对齐)	收敛至目标精密度 (<0.01)	成功滤除各方向单点离群值，梯度方向精准

关键发现¶

标量截断在单方向即可产生显著增益：在极其严苛的单方向设置（$M=1$）下，RSC-ZO 在 RoBERTa-large 的 SNLI、MNLI 和 TREC 上分别比 MeZO 高出 8.8%、7.6% 和 9.2%，表明 MeZO 实践中遇到的步长崩溃主要来源于随机前向差分的重尾异常扰动。
方向与梯度的余弦对齐验证了理论机制：在重尾控制实验中，向量截断后的余弦相似度曲线几乎与未截断版本重合，直接印证了“聚合后截断只缩放长度但无法纠正方向偏差”的核心论断，而聚合前标量截断实现了质的飞跃。
任务依赖的批方向最优解：在固定总查询预算下，MNLI 与 TREC 随着采样方向 $M$ 增加展现出性能进一步提升，而 SNLI 则在 $M=1$ 表现最好，说明不同任务对“更精准的方向估计”与“更多优化迭代步数”之间的权衡存在差异。

亮点与洞察¶

弱 $L_p$ 条件下的真推广：理论假设采用比经典有界 $p$ 阶矩更弱的弱 $L_p$ 尾部概率界 $\mathbb{P}(\|\nabla F(x;\xi) - \nabla f(x)\|_2 > t) \le (\sigma/t)^p$。论文严格构造反例证明，即使在 $p=2$ 时该条件依然允许无限方差分布，拓宽了极值噪声下的收敛理论边界。
首次匹配一阶高概率最优阶数：在光滑非凸目标函数下，RSC-ZO 达成了 $\widetilde{O}(d^{\frac{p}{2(p-1)}}\varepsilon^{-\frac{3p-2}{p-1}})$ 的函数查询复杂度，不仅在精度 $\varepsilon$ 依赖上完全吻合一阶重尾非凸优化的理论下界，且在 $p=2$ 时自然恢复经典的 $\widetilde{O}(d\,\varepsilon^{-4})$。
小批量动量技巧极具实用价值：证明了动量不仅能加速收敛，更关键的是可以将内层运行批大小降低 $1-\beta$ 倍，甚至降至 $M=1$，从而让重尾鲁棒算法能够无缝移植至显存极度受限的大模型无梯度前向微调场景。

局限与展望¶

假设局限于光滑目标与共享随机性：理论推导依赖于样本函数的李普希吉光滑性（$L$-smooth）以及双点扰动能够访问完全一致的随机种子 $\xi$。在无法控制随机种子的物理黑盒系统或不可微物理仿真中，该框架无法直接生效。
自适应截断参数理论缺失：理论证明的最优截断阈值 $\tau$ 依赖于 Lipschitz 常数 $L$、噪声尺度 $\sigma$ 和初始距离 $\Delta_0$ 等先验未知常数，实验中依赖网格搜索。未来亟需发展类似 AdaClip 的全自适应截断与自适应步长机制。
高维扩展性瓶颈：尽管维度依赖匹配了无结构零阶优化的理论最优 $O(d)$ 阶，但在超大参数模型（如数十亿级 LLM）中直接进行全参数零阶扰动依然极其缓慢，亟需将标量截断机制与低维子空间扰动（如 LoRA、随机子空间投射）深度结合。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次建立非凸弱 $L_p$ 重尾噪声下的零阶高概率收敛理论，标量截断先于聚合的设计直击零阶机制核心。
实验充分度: ⭐⭐⭐⭐ 既有对理论核心机制精准隔离的受控二次型仿真，又有 350M 参数 RoBERTa 的 NLP 真实下游任务落地。
写作质量: ⭐⭐⭐⭐⭐ 概念清晰，数学推导层层推进，从引理分解到动量 Lyapunov 函数构造均高度严密自洽。
价值: ⭐⭐⭐⭐⭐ 兼具高水平理论突破与强实用工程前景，为大模型无梯度微调算法提供了急需的鲁棒理论支撑与优化原语。