From Cursed to Competitive: Closing the ZO–FO Gap via Input-to-State Stability¶

会议: NeurIPS 2026
arXiv: 2604.25372
OpenReview: https://openreview.net/forum?id=kEqC3TBex2
领域: 优化/理论
关键词: 零阶优化、动力系统、输入-状态稳定性 (ISS)、高斯平滑、收敛邻域

一句话总结¶

本文从离散时间动力系统与输入-状态稳定性（ISS）视角重新审视零阶优化，证明了在高斯平滑随机预言机下，零阶算法的平均轨迹等价于对应一阶算法叠加有界扰动，从而在期望下继承与一阶方法完全相同的无维数依赖迭代衰减率，维度因子仅作用于可控的极限收敛邻域半径。

研究背景与动机¶

在黑盒对抗攻击、强化学习无导数策略搜索、黑盒超参数调优以及大语言模型无反向传播微调（如 MeZO）等现代机器学习场景中，目标函数的真实解析梯度往往不可用或计算开销极其昂贵，研究者必须依赖仅通过函数值评估构建梯度估计的零阶（Zeroth-Order, ZO）优化算法。然而，长期以来学术界的经典认知一直认为零阶算法必然伴随着严苛的“维度诅咒”——自 Nesterov 与 Spokoiny 的开创性工作确立高斯平滑框架以来，理论界普遍认为在光滑凸优化问题上，ZO 梯度下降（ZO-GD）相较于标准一阶（First-Order, FO）梯度下降，必须付出与问题维度 \(n\) 呈正比（\(\mathcal{O}(n)\)）的额外迭代步数代价，即使引入稀疏性或有效维数假设也需严苛的谱衰减或梯度稀疏结构。

这一长期存在的认知鸿沟导致零阶方法在理论上被视作收敛速度天然弱于一阶方法的替代工具，其步长设定也常被强制约束在随维度倒数 \(\mathcal{O}(1/n)\) 缩放的保守区间内，与实际应用中可采用更进取步长且表现极佳的实证经验脱节。这引发了一个核心矛盾：零阶算法中维度的惩罚究竟是迭代收敛速度上的本质迟缓，还是由于估计误差导致其无法精准收敛到单点极小值而产生的稳态残差误差？

本文作者转换切入角度，不再沿用传统构造势函数强求单点精确收敛的证明范式，而是引入控制理论中的离散时间动力系统与输入-状态稳定性（Input-to-State Stability, ISS）框架。通过将零阶算法的期望演化轨迹严谨重写为标准一阶动力系统叠加上由平滑偏差和采样方差构成的有界扰动输入，作者揭示了零阶优化的瞬态收敛机制。核心 idea：将高斯平滑零阶算法建模为一阶动力系统受控输入扰动系统，利用输入-状态稳定性（ISS）证明其在期望下与一阶方法共享完全相同的无维数依赖瞬态指数衰减率，问题维度 \(n\) 仅决定最终收敛邻域的边界半径，且该半径可通过平滑参数 \(\mu\)、步长 \(h\) 及多方向采样数 \(t\) 任意压缩。

方法详解¶

整体框架¶

该方法的核心思想是将优化迭代视作离散动力系统状态演化过程。对于经典一阶算法（如梯度下降 GD、重球动量法 HB、Nesterov 加速梯度 NAG），其更新规则可统一抽象为状态更新映射 \(z_{k+1} = w(z_k)\)，在强凸或正则化条件下具备围绕不动点 \(z^e\) 的局部指数稳定性或渐近稳定性。当引入两点随机高斯平滑梯度预言机后，算法产生的随机轨迹经由历次扰动方向采样集合 \(U_k=\{u_1, \dots, u_k\}\) 的条件期望平滑，其平均迭代序列 \(\bar{z}_k = \mathbb{E}_{U_k}[\tilde{z}_k]\) 精确对应于受扰动的一阶离散动力系统 \(\bar{z}_{k+1} = w(\bar{z}_k) + q_k\)。

随后，作者证明当目标函数满足强凸性或引入 \(L_2\) 正则化时，误差系统不仅能够抑制内部方差传播，还能使扰动序列 \(\{q_k\}\) 达到全局一致上界 \(\sup_k \|q_k\| \leq \bar{q}\)。借助李雅普诺夫函数与 ISS 比较函数机制，受扰系统在瞬态过程保持与未受扰一阶系统完全相同的几何衰减率，最终收敛至以一阶不动点为中心、半径由扰动上界所决定的紧邻域内。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["连续可微黑盒目标函数 min f(x)<br/>仅能通过函数评估值查询"] --> B["高斯平滑两点随机预言机<br/>g_μ(x) = (f(x+μu) - f(x))u / μ, u ~ N(0, I)"]
    B --> C["动力系统平均轨迹等效建模<br/>z_k+1 = w(z_k) + q_k 扰动动力系统"]
    C --> D["强凸与正则化下的扰动误差一致有界性<br/>拆解为平滑偏差 O(μ n^(3/2)) 与累积方差 O(σ / √t)"]
    D --> E["输入-状态稳定性 (ISS) 传递定理<br/>继承 FO 瞬态指数衰减率，收敛至可控球域 B_r(z^e)"]

关键设计¶

1. 动力系统平均轨迹等效建模：将随机零阶轨迹投影至一阶动力系统受扰流形

针对传统零阶证明难以解耦随机扰动与确定性收敛动力学的痛点，该设计在状态空间中建立期望等效形式。以梯度下降为例，真实 FO 更新为 \(z_{k+1} = z_k - h\nabla f(z_k)\)，而 ZO 轨迹通过随机预言机 \(g_\mu(x) = \frac{1}{\mu}(f(x+\mu u) - f(x))u\) 进行更新：\(\tilde{z}_{k+1} = \tilde{z}_k - h g_\mu(\tilde{z}_k)\)。通过对过去历史高斯扰动向量 \(U_k\) 取全期望，定义均值轨迹 \(\bar{z}_k = \mathbb{E}_{U_k}[\tilde{z}_k]\)，其差分动力学精确重写为：

\[\bar{z}_{k+1} = \bar{z}_k - h \nabla f(\bar{z}_k) + q_k\]

其中扰动项 \(q_k\) 被严谨正交分解为平滑偏差项与状态随机漂移项之和：

\[q_k = h \bigl(\nabla f(\bar{z}_k) - \nabla f_\mu(\bar{z}_k)\bigr) + h \bigl(\nabla f_\mu(\bar{z}_k) - \mathbb{E}_{U_k}[\nabla f_\mu(\tilde{z}_k)]\bigr)\]

对于具有动量机制的重球法（HB）与 Nesterov 加速梯度（NAG），作者采用增广状态向量 \(z_k = [x_{k-1}^\top, x_k^\top]^\top \in \mathbb{R}^{2n}\) 统一建模：

\[z_{k+1} = A z_k + \begin{bmatrix} 0 \\ -h_1 \nabla f(P z_k) \end{bmatrix}\]

其中 \(P=T=[0, I_n]\) 对应 HB，\(P=TA\) 对应前瞻更新的 NAG。这一转化使得所有主流零阶加速算法均能统一纳入同一线性定常系统加非线性扰动反馈的标准控制系统形式中。

2. 强凸与正则化下的扰动误差一致有界性：建立非发散扰动控制界

要使控制理论的 ISS 定理生效，扰动序列必须一致有界。然而在（268）式中，随机漂移项包含状态方差 \(e_k = \tilde{z}_k - \bar{z}_k\) 的演化，若方差随迭代步数无限累积，扰动将发散。作者利用目标函数（及高斯平滑版本 \(f_\mu\)）的 \(\beta\)-强凸性结合 Jensen 不等式，证明内积项满足 \(\mathbb{E}[\langle e_k, \nabla f_\mu(\tilde{z}_k)\rangle] \geq \frac{\beta}{2} \mathbb{E}[\|e_k\|^2]\)，从而证明方差系统构成严格单步几何收缩。在单步步长 \(h \in (0, \frac{\beta}{2L_1^2})\) 条件下，扰动范数满足一致上界：

\[\sup_{k} \|q_k\| \leq h \frac{\mu}{2} L_1 (n+3)^{3/2} + h L_1 \sqrt{\frac{2h\sigma^2}{t(\beta - 2L_1^2 h)}}\]

在 NAG 情况下，前瞻点投影 \(TA\) 使得强凸收缩项直接作用于前瞻误差 \(y_k^e = TA e_k\)，完全消除了 HB 动量交叉项对稳定裕度的侵蚀。而针对非强凸目标函数，作者进一步设计 \(L_2\) 正则化引入收缩因子 \(c \in [0, 1)\)（对应 \(\lambda = \frac{1-c}{2h}\)），在正则化目标 \(f(x) + \lambda \|x\|^2\) 下重构严格收缩映射，获得可控的扰动上界。

3. 输入-状态稳定性（ISS）传递定理：零阶迭代复杂度与维数解耦

以往文献由于强行要求收敛至零误差极值点，导致每次迭代不得不消耗随 \(n\) 递增的计算量或降低步长，进而得出迭代复杂度依赖于 \(\mathcal{O}(n)\) 的结论。本文基于离散时间李雅普诺夫 ISS 定理（Theorem 1 与 Theorem 2），证明对于满足如下耗散条件的系统：

\[c_1 \|z - z^e\|^2 \leq V(z) \leq c_2 \|z - z^e\|^2, \quad V(\bar{w}(z, 0)) - V(z) \leq -c V(z)\]

受扰系统在有界输入下满足如下状态轨迹界：

\[\|z_k - z^e\| \leq \sqrt{\frac{c_2}{c_1}} \|z_0 - z^e\| (1-c)^{k/2} + \gamma\Bigl(\sup_{0 \leq j \leq k} \|q_j\|\Bigr)\]

该定理产生了一个根本性的理论洞见：指数衰减系数 \((1-c)^{k/2}\) 纯粹由一阶系统的收缩因子 \(c\) 决定，在迭代指数 \(k\) 的收敛率上不存在任何维度 \(n\) 的惩罚因子。维度 \(n\) 仅作为一个常数出现在扰动上界中，决定了极限收敛球 \(\mathcal{B}_r(z^e)\) 的稳态半径 \(r\)。更重要的是，通过选取更平滑的高斯半径 \(\mu\) 或通过 mini-batch 多方向采样（即增大 \(t\)），邻域半径 \(r\) 可以被任意缩小至机器精度级别的微小球域内，从而从机制上彻底闭合了 ZO 与 FO 在迭代收敛速度上的理论差距。

实验关键数据¶

主实验¶

论文在两个基准场景进行了严格的数值实验验证：一是高维（\(n=1000\)、条件数 \(\kappa=100\)）强凸二次函数极小化，二是基于真实 MNIST 手写数字识别（0 与 1 二分类）的双层全连接神经网络非凸二元交叉熵损失极小化（特征维数 \(d=784\)，隐层单元 \(H=128\)，模型总优化参数量达 \(n=100,609\)）。在神经网络实验中加入 \(\lambda=10^{-2}\) 的 \(L_2\) 正则化，设置 \(h=10^{-3}\)，动量参数 \(h_1=10^{-3}, h_2=5\times 10^{-4}\)，平滑参数 \(\mu=10^{-7}\)，采样方向数 \(t=7\)。

下表展示了全连接神经网络在 \(n=100,609\) 规模下，六种优化算法（GD、HB、NAG 及其对应 ZO 版本）的收敛性能与最终分类准确率对比：

优化算法类型	梯度阶次	最终训练损失	训练集准确率 (%)	测试集准确率 (%)	相对每轮运行耗时
标准梯度下降 (GD)	FO (一阶)	0.6529	99.55%	99.40%	1.0× (基准)
零阶梯度下降 (ZO-GD)	ZO (零阶)	0.6584	99.55%	99.40%	~4.0×
重球动量法 (HB)	FO (一阶)	0.6525	99.55%	99.40%	1.0×
零阶重球法 (ZO-HB)	ZO (零阶)	0.6580	99.55%	99.40%	~4.1×
Nesterov 加速梯度 (NAG)	FO (一阶)	0.6520	99.55%	99.40%	1.0×
零阶 NAG (ZO-NAG)	ZO (零阶)	0.6578	99.55%	99.40%	~4.1×

消融实验¶

为了直接验证理论给出的“零阶方法在收敛迭代步数上完全不随维度增加而衰减”的核心结论，作者固定超参数（\(h=5\times 10^{-4}, t=10, \mu=10^{-8}\)），通过系统调整神经网络隐藏层单元数 \(H \in \{16, 32, 64, 128, 256\}\)，使问题维度从 \(n=12,577\) 扩展至 \(n=201,217\)（跨越两个数量级），分别测量 GD 与 ZO-GD 达到 FO 最终收敛损失 20% 相对误差邻域所需的迭代步数与相对耗时比：

隐层单元数 \(H\)	优化参数量 \(n\)	FO 最终损失	ZO 最终损失	达到 20% 目标所需迭代比 (ZO/FO)	单步时间比 (ZO/FO)
16	12,577	0.6922	0.6920	0.99	5.5×
32	25,153	0.6720	0.6721	1.00	4.9×
64	50,305	0.6761	0.6798	1.03	5.4×
128	100,609	0.6529	0.6584	1.03	5.7×
256	201,217	0.6866	0.7017	1.05	4.5×

关键发现¶

迭代维度无关性获强力实证：在参数量从 \(1.2\times 10^4\) 猛增至 \(2.0\times 10^5\) 时，达到收敛目标所需的迭代步数比率（Iter ZO/FO）稳定保持在 \(0.99 \sim 1.05\) 之间，毫无传统理论预言的线性 \(\mathcal{O}(n)\) 迭代膨胀迹象，充分证实了 ISS 收敛率界与维度解耦的正确性。
超参数双通道解耦补偿机制：实验证实了扰动界中理论项的对应分工——\(\mu\) 严格控制由高斯平均引入的几何平滑偏差，当 \(\mu\) 缩小至方差占主导后继续缩小收益饱和；而采样方向数 \(t\) 与步长 \(h\) 协同抑制方差项。对于因步长过大导致 ZO 发散的情形，无需缩小步长，仅通过提升采样数 \(t\) 即可将扰动压制在收缩不变集内恢复收敛。

亮点与洞察¶

认知范式突破：打破了经典零阶优化中“迭代复杂度必须附加 \(\mathcal{O}(n)\) 惩罚”的思维定势。本文澄清了维数惩罚的本质是收敛球域的物理半径而非收敛动态的衰减时间常数，为大模型无导数微调的高效实证提供了坚实的理论解释底座。
跨学科理论嫁接：创造性地将非线性控制理论中的输入-状态稳定性（ISS）与离散时间李雅普诺夫反演定理引入优化理论，省去了为每一种新型零阶算法重复构建专用势函数的繁琐步骤，具备通用框架属性。
前瞻加速项的方差抑制特性：理论清晰揭示了 NAG 相比 HB 在零阶下的代数结构优势——NAG 的强凸收缩直接作用于前瞻采样点误差，避免了动量项历史误差交叉累积，为后续无导数加速器设计指明了架构准则。

局限与展望¶

函数查询开销随目标精度权衡：尽管迭代复杂度与维度解耦，但将邻域半径 \(r\) 压至极小所需的采样方向数 \(t\) 或预言机方差在最坏情形下依然可能隐式受维度影响，单次迭代的总函数查询（Function Evaluations）代价在极高精度需求下仍需权衡。
高概率保证缺失：现有理论结论均建立在全期望轨迹（In Expectation）下，尚未建立高概率（High-Probability）置信边界或鞅收敛停时保证，对重尾或极端采样扰动的鲁棒性有待完善。
通用非凸问题的理论外推：非凸情形目前依赖 \(L_2\) 正则化引入的人工强凸收缩，对于无正则项约束的通用非凸非光滑鞍点及平坦区域的 ISS 分析仍是开放挑战。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 巧妙利用控制理论 ISS 框架重新刻画优化收敛，颠覆了长久以来的维数界认知。
实验充分度: ⭐⭐⭐⭐ 涵盖病态二次函数与高维神经网络规模扩展实验，消融清晰，但缺乏真实大语言模型微调实验。
写作质量: ⭐⭐⭐⭐⭐ 数学推导严密自洽，从控制系统到底层收敛不等式的推演流畅清晰。
价值: ⭐⭐⭐⭐⭐ 具有极高的方法论价值，为连接控制理论与黑盒大模型优化开辟了极具前景的研究路径。