ICML 2026 | 仅用比较完成梯度测试与估计

优化是机器学习的核心问题。神经网络训练、强化学习中的策略搜索、黑盒对抗攻击等任务^[1][2]，本质上都可以看作对某个目标函数的最小化。机器学习与优化问题往往维数很高，而梯度下降类方法的复杂度通常不显式依赖维数，因此在高维问题中被广泛采用。理想情况下，算法可以直接访问梯度；但在很多现实场景中，梯度要么不可获得，要么计算代价过高。例如，在黑盒对抗攻击中，算法通常只能通过模型输入输出推断目标函数变化；在强化学习的策略搜索中，目标值往往来自随机环境交互；在调用专有模型或闭源系统时，用户也可能只能获得有限反馈。

因此，零阶优化长期以来都是机器学习和优化理论的重要方向。零阶算法通常假设可以查询函数值，而本文考虑的信息比函数值还要弱：算法不能知道  的具体数值，只能比较两个点  的函数值大小，即知道  还是  。

这种比较查询看似简单，却在许多实际算法中自然出现。例如，直接搜索、模式搜索、Nelder-Mead 方法^[3]，以及近年来的排序型或偏好型优化方法，本质上都大量使用候选点之间的比较。问题在于：如果只允许比较，我们究竟能否恢复梯度信息，需要多少次比较，以及经典算法和量子算法之间是否存在复杂度差距。

本文围绕这些问题展开，研究比较查询模型下的梯度测试与梯度估计，并给出了近乎完整的复杂度刻画。

设  是一个光滑函数。算法不能直接访问 或 ，只能访问比较预言机：当  时，预言机可以返回任意一个结果。本文关注归一化梯度方向 之所以研究归一化方向，是因为比较查询对函数的正比例缩放不敏感：如果把目标函数乘以一个正常数，所有比较结果都不会改变，梯度方向也不会改变。论文中假设  ，这是为了避免驻点附近方向不稳定，而不是额外增加查询复杂度。

本文研究两个核心问题：

• 梯度测试：给定一个单位向量  ，判断真实梯度方向  是否与  足够接近，即  ，或者二者是否相距较远，即  。

• 梯度估计：仅通过比较查询，输出一个单位向量  ，使其满足  。

一旦得到这样的梯度方向估计  ，它可以直接用于归一化梯度下降更新： 因此，本文的局部方向估计过程可以作为比较型优化算法中的基础模块。

论文的算法将比较访问归约为一个鲁棒的一次查询测试，用于判断方向导数的符号；这与比较型优化中的方向偏好（directional preference）有关。

方向偏好（DP）。比较  与 。直觉。沿方向  做一次很小的探测，就能揭示  与   大致同向还是反向。

图1: 方向偏好（DP）示意图：比较 𝑥 与 𝑥 + 𝜂𝑣 的函数值，就能获得梯度在 𝑣 方向上的符号信息。

旋转坐标系使  后，写作  。测试归约为区分  

思路。

图2: 通过随机方向 𝑦 构造测试向量 𝛼_𝑦，再用 DP 判断其与梯度的相对关系。

目标是仅使用比较查询来恢复归一化梯度方向  关键思想是估计所有坐标相对于一个主导坐标的比例。

算法思路。

1. 使用 DP 查询找到一个与  有常数重叠的参考方向。

2. 将该参考方向旋转到  ，于是以常数概率有  

图3: 用随机正交基构造参考方向 𝑢，并把它作为后续比例估计的参照轴。

3. 对每个坐标  ，通过 DP 估计比例  。

对于比例估计，查询    的符号会说明  位于  的上方还是下方，从而可以进行二分搜索。

图4: 通过查询 𝑤_𝑖(𝛽) = 𝛽𝑒_1 − 𝑒_𝑖，判断比例𝑔_𝑖/𝑔_1 所在区间。

自适应范围搜索避免在小坐标上浪费查询。由于 总查询复杂度为 这与经典下界匹配。

量子算法将基于比较的比例估计与 Jordan 的基于 QFT 的梯度估计结合起来^[4]。 

• 选择一个随机参考方向  ，并将其旋转到  。

• 在叠加态中，使用相干二分搜索找到  ，使得  与  近似正交。

• 这会把  的一个近似编码到相位中。

• 逆 QFT 使用  次量子比较恢复方向。

量子为何有帮助。量子过程不是显式学习  个坐标比例，而是在叠加态中提取全局相位模式。

论文还通过数值实验验证了算法的实际表现。实验包括三类测试函数：一般强凸二次函数、稀疏二次函数，以及扩展 Rosenbrock 函数。

在梯度测试任务中，论文构造了接近边界的 YES 实例和 NO 实例，并在  、  的设置下进行测试。实验显示，随机梯度测试算法与确定性梯度测试算法在所有配置中都达到  的成功率，明显高于理论分析中保证的常数成功概率。

在梯度估计任务中，实验显示算法输出的单位向量误差几乎总是低于目标精度  ，平均误差远小于理论上限。进一步地，论文在扩展 Rosenbrock 函数上测试了查询复杂度随  和  的变化，拟合结果与理论复杂度  高度一致。

更重要的是，论文将本文的梯度方向估计器接入自适应归一化梯度下降算法中^[5]。实验表明，在相近的每轮查询预算下，使用本文估计器的 ADANGD+OURS 几乎追踪了能够直接访问真实归一化梯度的 IDEAL ADANGD 曲线，而其他比较型或零阶基线方法则明显停滞在更高的目标函数值附近。这说明，本文提出的局部梯度估计模块不仅有清晰的理论复杂度，也能在优化过程中提供足够准确的下降方向。

图5: 论文 Figure 1 的实验曲线：查询复杂度拟合于 Rosenbrock 函数上的优化表现。

为了说明算法的最优性，论文进一步建立了经典和量子下界。

对于经典梯度估计，论文使用球面上的  -net 构造大量彼此分离的可能梯度方向。由于每次比较查询只能返回有限种结果，算法若要区分这些方向，就必须获得足够多的信息。因此，任何经典算法都需要至少  次比较查询。这与本文的经典算法完全匹配。

对于量子梯度估计，论文构造了具有二值偏导结构的困难实例，并利用混合论证分析不同预言机之间的可区分性，得到  的量子下界。本文的量子算法复杂度为  ，因此仅剩一个   的差距。

本文的研究也提出了若干值得进一步探索的问题。

首先，量子梯度估计算法与量子下界之间仍存在一个  因子。是否存在查询复杂度达到  的量子算法，是一个自然的开放问题。

其次，本文主要研究确定性比较预言机。实际应用中，比较结果可能带有噪声，例如人类偏好反馈、近似函数评估或随机仿真环境。因此，带噪声的随机比较预言机下是否仍能实现类似复杂度，是后续研究的重要方向。

最后，本文的梯度测试与估计过程可以作为比较型优化算法的局部模块。如何将这些模块系统地嵌入更大规模的优化求解器，并在非凸、随机或高维机器学习任务中获得更好的性能，也值得进一步研究。

[1] Xiwen Tao, Chenyi Zhang, Helin Wang, Yexin Zhang, Tongyang Li. Gradient Testing and Estimation by Comparisons. Proceedings of the 43rd International Conference on Machine Learning, 2026.

[2] Nesterov and Spokoiny. Random Gradient-Free Minimization of Convex Functions. Foundations of Computational Mathematics, 2017.

[3] Karabag et al. Gradient estimation and optimization using comparison queries, 2021.

[4] Cai et al. Recovering gradient information from noisy comparison feedback, 2022.

[5] Tang et al. Ranking-based comparison models for optimization, 2024.

[6] Jordan. Fast quantum algorithm for numerical gradient estimation. Physical Review Letters, 2005.

图文 | 陶希文

PKU QUARK Lab