零阶非凸优化的全局联合下界：终结一个公开问题

为什么零阶优化需要一个"紧"的下界

零阶（zeroth-order）优化让算法只能通过函数值——而非梯度——来寻找最小值，这在黑盒调参、强化学习策略搜索、以及梯度不可得的仿真优化中非常常见。一个自然的做法是：用有限差分或高斯平滑把函数值变成梯度估计，再套用一阶方法的收敛保证。但这种"搬运"通常要付出一份与维度 d 线性相关的代价。

问题随之而来：这个 d 的代价是本质的，还是分析粗糙的结果？更尖锐地说，当目标是非凸、只求 Goldstein 稳定点、精度要求又很高时，复杂度对维度 d、稳定精度 δ、误差 ε 的依赖能否同时达到最优？此前已有工作分别证明了 d 的依赖和 (δ, ε) 的一阶依赖各自不可省，但把三者"联合"起来的下界一直空缺。

Goldstein 稳定点是非凸优化中的一种近似最优性概念。对于光滑函数 (f)，若点 (x) 满足 (|\nabla f(x)| \le \delta)，则称其为 (\delta)-稳定点（也称一阶稳定点）。但在非光滑情形下梯度可能不存在，Goldstein 稳定点通过梯度映射的范数来定义：(|\nabla f(x)| = |x - \text{prox}_{\eta f}(x)|/\eta) 的上确界不超过 (\delta)。它比简单的次梯度界更稳健，能在非光滑、非凸问题中给出可计算的停止准则。因此，当论文讨论"求 Goldstein 稳定点"时，实际上是在为一大类非光滑非凸问题提供统一的近似解概念，并以此作为复杂度的度量目标，这也是下界能同时涉及 (\delta) 和 (\varepsilon) 的原因。

前序工作留下的口子

据论文引用的 Kornowski (2024) 结果，非光滑非凸优化可以在 (\mathcal{O}(d\delta^{-1}\varepsilon^{-3})) 的零阶 oracle 复杂度内求解，作者当时提出疑问：这个复杂度对 (d, δ, ε) 的依赖是否联合最优。

拆开看，两部分已经清楚：维度依赖不可避免；对 (δ, ε) 的一阶依赖也不可避免。缺的是能同时匹配三者的零阶下界。要补上它，难点在于零阶算法的"自由度"太大——它可以在任意点查询、自适应选择采样、把同一个采样函数复用到多个位置，且对输出点没有空间限制。靠"限制查询区域"或"每次评估都是新鲜噪声"这类假设导出的下界，根本无法覆盖这种全自适应、可复用的标量 oracle。

零阶 oracle 复杂度衡量算法在只能查询函数值的情况下，达到给定精度所需的最少查询次数。一个零阶 oracle 接收点 (x) 和一个随机种子，返回带噪声的函数值 (f(x) + \xi)。算法的查询策略可以是自适应的：根据之前所有查询结果决定下一个查询点，甚至可以把同一个随机采样函数（如高斯向量）复用到多个点上，以构造有限差分梯度估计。这种完全自适应性使得传统下界技术（如限制查询区域或假设每次查询独立同分布）失效。因此，建立在该模型下的下界必须考虑信息在自适应复用中的保持，这正是论文证明中最棘手的部分。

这篇论文做了什么

论文在不受限的全空间设定下回答了这个公开问题，核心结论有两条。

光滑随机非凸：标量 oracle 下界

在目标函数光滑、种群目标全局下界，且样本 Lipschitz 常数有二阶矩界的前提下，论文给出标量 oracle 的下界：

[ \Omega!\left(\frac{dL_0^2\min{\Delta H,,L_0^2}}{\varepsilon^4}\right) ]

这个界对 \(d\) 线性，对精度是 \(\varepsilon^{-4}\)。

极小极大最优性（minimax optimality）是衡量算法性能的理论基准：对于某个问题类，如果算法的最坏情况复杂度与所有算法可能达到的下界（在常数因子内）匹配，则称该算法在极小极大意义下最优。论文证明 (d, δ, ε) 的联合极小极大最优性，意味着不存在任何零阶算法能在最坏情况下同时改进维度 (d)、稳定精度 (\delta) 和误差 (\varepsilon) 的依赖关系。换言之，(\Omega(dL_0^2\min{\Delta H, L_0^2}/\varepsilon^4)) 和相应的 Goldstein 稳定点下界是紧的，为这类问题划定了不可逾越的复杂度边界。

平滑归约到 Goldstein 稳定点

作者用一个光滑归约把上述结果转成 Goldstein 稳定点的下界，从而在显式的高维、小精度条件下，证明了 (d, δ, ε) 的联合极小极大最优性。这正是前序工作留下的那个口子。

值得强调的是下界适用的算法模型：算法可以在 \(\mathbb{R}^d\) 中查询任意点、自适应选择样本函数、把同一个采样函数复用到任意多个位置、输出点也不受空间约束。也就是说，它覆盖的是完全自适应、可复用样本的标量 oracle，比依赖有界查询区域或新鲜噪声的下界严格更强。论文还单独给出一个无噪声、精确取值的下界，对随机算法成立，因而对确定性方法同样成立。

证明路线：为什么"全自适应"反而更难下界

要证明这种下界，需要让信息难度在自适应复用下依然保持。论文的证明组合了几块工具：一个全局定义的序贯非凸构造、一个精确高斯标量信道、多阶段随机场估计，以及一个对偶有限样本实现——后者确保在自适应复用样本时，信息硬度不会衰减。

这也解释了这个结果为何有意义：许多下界靠限制查询区域或要求独立新鲜噪声来简化分析，而现实中的零阶方法恰恰不满足这些条件。这篇论文把假设放宽到几乎不设限，结论仍然成立，意味着 \(d) 线性的代价不是分析缺陷，而是问题本身的结构性代价。

对实践者意味着什么

如果你在设计零阶方法，这个结果的直接含义是：不要指望通过更聪明的查询策略或样本复用来消掉对维度 d 的线性依赖；在非凸、高维、小精度区间，目标是找到一个在 \(d\) 上线性、在精度上接近 \(\varepsilon^{-4}\) 的算法，而不是梦想亚线性维度。

次一级的含义在于 δ 与 ε 的耦合：既然联合下界表明三者的依赖无法分解式地优化，那么算法设计的权衡应放在如何让常数和实际样本复用效率更好，而不是试图在最坏情形保证上突破这三者的乘积结构。对于依赖零阶优化的黑盒调参、仿真优化等场景，这给出了一个清晰的性能天花板参照。