精读笔记

Problem Setting

[Finding Stationary Points by Comparisons]（arXiv preprint / 2026）。这篇论文实际解决的是：在只能比较两个点函数值大小、完全不能读取函数值大小和导数信息的情况下，是否还能达到非凸二阶光滑优化中 epsilon^{-3/2} 的驻点复杂度。真正困难是 comparison oracle 抹掉了所有尺度信息：函数下降量不可见，梯度范数不可测，Hessian 范数也不可测；而二阶 trust-region 分析恰恰依赖这些尺度。以前 STP / direct-search 类方法能用比较做随机方向下降，但基本停留在一阶随机搜索逻辑，复杂度是 O(n/epsilon^2) 量级，无法把 Hessian Lipschitz 条件转化为 epsilon^{-3/2} 的下降尺度。关键矛盾是：comparison access 对单次查询极弱，但局部几何结构很强；论文要证明弱反馈在足够精细组织后仍能模拟二阶 oracle。

Motivation

已有 comparison-based 非凸方法的问题不是不能下降，而是只能以“哪个点更好”的方式做局部试探，缺少可组合的微分结构。作者的核心观察是：比较反馈虽然不给函数差，但足以估计梯度方向；多个邻近点的梯度方向之间的相对几何，又包含 Hessian-vector product 的方向信息。真正缺口是如何在没有尺度的情况下恢复二阶模型所需的相对尺度，尤其是 normalized Hessian 与 ||H||/||g||。因此本文不是简单改进 direct search，而是试图把 comparison oracle 系统性地编译成一个 scale-free second-order oracle。

Core Idea

核心思想可以概括为：用比较恢复方向，用方向恢复局部二阶几何，用二阶几何触发 trust-region 下降。比较 oracle 本身只给序，但局部排序边界决定梯度方向；在 x+r y 与 x-r y 处估计梯度方向后，三者之间的夹角关系相当于观察到了梯度方向的变化，而这个变化的一阶项就是 H y。这样，Hessian-vector product 的“方向”可以从纯几何关系中被恢复。

与 prior 的本质区别在于，STP/direct-search 是把 comparison 直接用于选择 step，而本文把 comparison 先转化为隐式二阶表示，再用二阶优化理论推进。它引入的 inductive bias 是局部 Taylor geometry：只要函数足够光滑，方向信息的变化比函数值本身更有结构。epsilon^{-3/2} 并不是新的优化现象，而是二阶 trust-region 下降尺度被 comparison 模型成功复现。

Method

方法的必要机制不是算法模块堆叠，而是三个尺度缺失问题的逐层修复。第一，Hessian-vector direction estimation 解决“comparison 只能给梯度方向，如何得到二阶方向”的问题；通过 x、x+ry、x-ry 的梯度方向三角关系，消去未知梯度范数，得到 H y 的 normalized direction。第二，normalized Hessian estimation 解决“只有 Hessian-vector 方向，如何拼出矩阵”的问题；逐列恢复方向，再用 H e_1、H e_i、H(e_1+e_i) 的三角关系恢复相对列范数，并用 perturbation 避免近共线导致的病态反演。第三，ratio estimation 解决“normalized Hessian 无法定义 trust-region 模型尺度”的问题；沿近似最大特征向量位移，利用梯度方向旋转量估计 ||H||/||g||。最后的 trust-region step、gradient step、line-search step 是覆盖不同几何退化情形的兜底组合，本质上保证只要当前点不是二阶驻点，总能找到 Omega(epsilon^{3/2}) 的下降。

Key Insight / Why It Works

最重要的 insight 是：comparison oracle 虽然丢掉函数值尺度，但没有丢掉局部 level-set orientation；而 level-set orientation 的一阶变化就是 Hessian 作用在方向上的信息。论文真正有效的原因不是 search 更聪明，而是把排序信息重新编码成 differential geometry。Hessian-vector direction recovery 是最核心贡献；normalized Hessian reconstruction 和 ratio estimation 是让它能进入 trust-region 框架的必要工程化理论组件。

epsilon 依赖改善主要来自二阶 smoothness + trust-region 的标准下降尺度，不是 comparison 模型特有的新优化机制。n^2 开销则来自显式恢复 Hessian 的列结构，属于方法范式的结构性成本，不太像可由简单 implementation 优化消掉。量子部分的 n 到 log n / n 级改进主要来自替换已有 quantum gradient direction estimation primitive，增益来源比较清楚，但也更依赖 oracle 模型。若从 practical ML/RLHF 角度看，这篇论文的“preference motivation”更像背景包装；核心理论完全建立在 noiseless scalar objective comparison 上，离真实人类偏好反馈仍很远。

Relation To Prior Work

最接近的路线有三类：direct search / pattern search / Nelder-Mead，STP 类随机三点方法，以及 comparison-based gradient direction estimation。本文与前两者的差异在于不把比较当作 step selector，而是当作局部几何测量工具；这是真正的范式差异。与 Tao et al. 的 gradient direction estimation 相比，本文的新增信息是把一阶方向 primitive 组合成 Hessian-vector、normalized Hessian 和 ratio oracle，从而进入二阶复杂度 regime。

看似新的 trust-region 部分本身不是创新，下降分析基本沿用二阶优化标准框架；真正新的是证明 comparison access 可以提供 trust-region 需要的近似对象。Hessian reconstruction 中的三角解比例、Davis-Kahan 控制特征向量扰动、退化情形 line-search 兜底都是已有数学工具的重组，但组合目标是新的：在完全 scale-free 的 oracle 下模拟二阶 oracle。它属于 derivative-free / comparison-based optimization 与 high-order nonconvex complexity 的交叉谱系。

Dataset / Evaluation

这篇论文没有传统 dataset / empirical evaluation，核心评价是理论查询复杂度与成功概率保证。它验证的是一个 oracle complexity claim：在无噪声 comparison oracle 下，能以 \widetilde{O}(n^2/epsilon^{1.5}) 访问量访问到驻点，并在 quantum oracle 下得到 \widetilde{O}(n/epsilon^{1.5})。从理论角度，这足以支持“comparison feedback 可利用二阶光滑性改善 epsilon 依赖”的 claim。

但 evaluation 并不支持实际可部署性。没有 stochastic comparison、没有真实 preference 数据、没有数值实验、没有常数规模评估，也没有展示算法在高维实际目标上的可运行性。文中关于 RLHF/preference learning 的动机不能被这些理论结果直接验证；它们共享 comparison 形式，但 oracle 假设、噪声结构和目标可表示性完全不同。

Limitation

最大限制是只保证 visited，而不是输出并认证一个 epsilon-stationary point；这不是小问题，而是 comparison 模型下尺度不可观测的根本后果。实际使用时返回最小函数值点只是 heuristic，不能保证 stationarity。第二，算法严重依赖无噪声、精确、可无限细分的 comparison oracle；一旦有 Bradley-Terry 噪声、非传递偏好或局部不一致，三角几何恢复可能迅速失效。第三，n^2 维度依赖很重，源于显式 normalized Hessian reconstruction；在大规模 ML 场景中几乎不可接受。

证明中存在大量退化情形处理：rank-one、definite Hessian、最大特征向量与梯度对齐、列方向近共线等。这说明主机制对几何条件很敏感，算法鲁棒性不是天然的，而是靠 case analysis 补起来的。量子结果依赖 quantum comparison oracle，可以作为 query complexity 结果看，但实际 oracle 构造成本文中未充分说明。总体上，实际增益来源不是 engineering / scaling，而是理论 oracle 编译；但 practical relevance 目前很弱。

Takeaway

• 最值得记住的第一点：comparison feedback 不只适合 accept/reject search，它可以在光滑假设下恢复局部微分几何，这是比 STP 更深的使用方式。
• 第二，epsilon^{-3/2} 速率来自把 comparison oracle 编译成 scale-free second-order oracle；这给 preference/ordinal optimization 提供了一个新理论方向，但不是即插即用算法。
• 第三，未来真正关键的是降低 n^2 Hessian reconstruction 成本，或者找到无需显式 Hessian 的 comparison-trust-region / lazy-update 版本。
• 第四，向 noisy/stochastic preference oracle 扩展比继续优化常数更重要，因为真实偏好反馈的主要困难不是缺函数值，而是比较本身不可靠。

一句话总结

这篇论文在 comparison-based 非凸优化中首次系统证明了“只凭排序也能模拟足够二阶几何并达到二阶 epsilon 复杂度”，本质贡献是一个 scale-free second-order oracle construction，而不是一个实用的 preference optimization 算法。