[Paper] 显式且非渐近的基于秩的零阶算法在光滑函数上的查询复杂度

Source: arXiv - 2512.16200v1

概述

本文首次给出了 明确、非渐近 的上界，说明 基于排序 的零阶（ZO）优化器需要多少函数查询才能达到目标精度。通过聚焦于支撑 CMA‑ES、NES 以及基于排序的遗传算法等流行工具的简单 “top‑k” 选择规则，作者表明这些启发式方法不仅在经验上表现稳健，而且在光滑（凸或非凸）目标函数上也具备可证明的效率。

关键贡献

• 显式查询复杂度公式 用于基于秩的 ZO 算法，消除了先前工作中“仅渐近”限制。
• 强凸情况： (\widetilde{\mathcal O}!\big(\frac{dL}{\mu}\log\frac{dL}{\mu\delta}\log\frac{1}{\varepsilon}\big)) 次查询即可获得 (\varepsilon)‑次优解。
• 非凸光滑情况： (\mathcal O!\big(\frac{dL}{\varepsilon}\log\frac{1}{\varepsilon}\big)) 次查询即可达到 (\varepsilon)‑驻点。
• 高概率保证（概率 ≥ (1-\delta)），而非期望，这对安全关键或生产环境更有用。
• 新颖的分析技术，规避了传统的漂移分析和信息几何论证，提供了对基于秩的启发式方法为何有效的全新视角。

方法论

1. Algorithmic skeleton – 该研究方法从一组随机搜索方向中抽样，在扰动点上评估目标函数，对结果进行排序，并保留前 (k) 个方向来更新当前估计。这对应于 CMA‑ES 和 NES 中的“selection”步骤。

2. Smoothness assumptions – 假设函数是 (L)-平滑的（梯度变化不过快）。在凸情形下，还要求函数具有参数 (\mu) 的强凸性。

3. Probabilistic analysis – 通过界定排序正确识别下降方向的概率，作者推导出估计梯度代理的浓度不等式。

4. Recursive error reduction – 分析表明，每一次迭代都会按一个取决于 (d)、(L)、(\mu) 和所选 (k) 的因子缩小最优性间隙。

5. Stopping criterion – 将使间隙降至 (\varepsilon) 以下所需的迭代次数相加，得到上文给出的显式查询复杂度公式。

关键洞见是，仅需函数值的相对顺序即可构造可靠的梯度估计，而方向抽样中的随机性提供了足够的信息，以高概率保证算法的进展。

结果与发现

这些界限表明，基于排序的 ZO 方法在理论上 与基于梯度的 ZO 算法竞争，同时对噪声和单调变换具有额外的鲁棒性。

实际意义

• 稳健的超参数调优 & 黑箱优化 – 工程师可以依赖 CMA‑ES 风格的优化器，并对所需评估次数有明确预期，即使目标函数存在噪声或仅提供序数反馈（例如 A/B 测试的点击率）。
• 资源预算 – 明确的公式使从业者能够在启动大规模搜索之前估算计算预算（GPU 小时、云额度），从而改进项目规划。
• 安全关键领域 – 高概率保证对航空航天、金融或医疗 AI 等领域非常有价值，因为在这些领域最坏情况的表现比平均情况更为重要。
• 算法设计 – 分析表明，增大 top‑(k) 选择规模可以在每轮成本与收敛速度之间进行权衡，为开发者提供可调节的参数。
• 与现有库的集成 – 由于算法核心与已在 cmaes、nevergrad 或 pycma 等库中实现的相同，理论结果可以作为文档添加，或作为可选的“理论指导”停止准则。

限制与未来工作

• 平滑性假设 – 现实中的黑箱函数可能不平滑或存在不连续；将分析扩展到此类情形仍是未解之题。
• 强凸性要求 以实现快速的 (\log(1/\varepsilon)) 收敛率；许多实际问题仅局部凸或仅满足 Polyak‑Łojasiewicz 条件。
• 固定的 top‑(k) 策略 – 本文研究的是静态的 (k)；自适应方案（例如在搜索过程中逐步增大 (k)）可能提升实际性能，但本文未涉及。
• 实证验证 – 虽然理论界限已相当紧致，论文并未包含大规模实验；未来工作可将预测的查询次数与真实优化运行进行基准对比。

总体而言，该工作弥合了基于排序的零阶方法的经验成功与理论基础之间的关键鸿沟，为开发者在生产环境中信任并进一步改进这些算法提供了坚实的基础。

作者

• Haishan Ye

论文信息

• arXiv ID: 2512.16200v1
• 分类: cs.LG, cs.NE
• 出版日期: 2025年12月18日
• PDF: 下载 PDF