仅凭带噪两两比较，如何优化非光滑函数？

比较只给出方向，不给出差值大小

在基于比较的优化中，算法看不到目标函数值 f。它提交两个点 x 和 y，只收到一个比特：该比特以概率 σ((f(y)−f(x))/τ) 等于 1，其中 σ 是已知的、严格递增且对称的链接函数，τ 是温度。这一模型刻画了对偶赌博机、人在回路调参，以及 RLHF 类流程中的偏好信号等场景。

难点在于，这个比特只取决于差值 f(y)−f(x) 的符号，不反映其大小。已有的非光滑非凸方法依赖带噪的函数值反馈，需要知道函数值差的幅度：随机平滑加两点差分需要 O(d^{3/2}δ^{−1}ε^{−4}) 次求值，方差缩减把它改进到 O(d^{3/2}δ^{−1}ε^{−3})，在线到非凸的转化则达到维度最优的 O(dδ^{−1}ε^{−3})。当只返回一个比特时，这些方法都不能直接照搬。

论文的目标是 (δ,ε)-Goldstein 稳定点，这是梯度可能不存在时的标准解概念。核心量是 κ，即被查询的最大差值除以 τ。由于查询的是对称点对 x±ρu（u 为单位向量），最大差值等于 2Lρ，因此 κ 由平滑半径 ρ 控制，而 ρ 必须满足 ρ≤δ/2。

用连续相同结果的长度构造无偏差值估计

关键构造是把逆链接函数 g=σ^{−1} 展开成多项式 b_m(p)=p^m−(1−p)^m 的级数。对每个 b_m，用同一串比较得到的自然估计在结果第一次翻转后就会归零，因此整条无穷级数可以由有限多个比特算出来。估计器的做法是反复比较这对点，直到结果翻转，然后返回 ±τ 乘以展开系数的部分和。

对 logistic 链接，这个部分和就是连续相同结果长度的调和数。该估计器精确无偏，期望比较次数不超过 1+1/(1−α)，其中 α 是被查询的最大成功概率；其二阶矩的量级为差值平方加 τ²。对 logistic 链接，论文给出界 E[Δ̂²]≤13τ²(1+κ)²。

该展开存在的条件是 g 在复平面的透镜区域 {|z|≤r}∩{|z−1|≤r} 上解析，logistic、probit 和 cauchit 链接都满足。仅在实区间附近解析并不够：论文给出了一个链接，它在被操作区间附近解析，但在透镜内部有极点，因此不存在这样的展开。这确实限制了该方法能服务哪些比较模型。

从差值估计到 Goldstein 稳定点

把无偏差值估计 Δ̂ 与查询方向 u 结合，得到梯度估计 G=(d/2ρ)Δ̂u，它是平滑目标函数梯度的无偏估计。随机平滑处理了梯度不存在的问题，在线到非凸的转化则把由此得到的在线学习序列转成 Goldstein 稳定性的保证。

两者结合后，论文在 Δ_f≥Lδ 时得到 O(d(1+dC_link/κ²)L²Δ_f/(δε³)) 次比较，其中 Δ_f 界定 f(x₀)−inf f，C_link 只依赖链接函数和 κ。平滑加 SGD 的变体需要 E[N]d(1+dC_link/κ²)L³Δ_f/(δε⁴) 次比较，E[N] 是每次差值估计的期望比较次数。

与函数值预言机基准的对比才是关键信息。相对于带噪函数值预言机的最优速率 O(dL²Δ_f/(δε³))，比较反馈要多付一个 d/κ² 的因子。这个因子不是记账上的宽松：它来自基于比较的梯度估计二阶矩随维度增长，实验也证实了这一点。

噪声主导区间内上下界一致

论文证明，在一个光滑凸子类上，只要 d 至少达到 (εδ/τ)² 的量级，任何基于比较的方法都需要 Ω(d²τ²/(ε²δ²)) 次比较。这个下界是针对比较模型量身定制的，而不是从函数值预言机的下界继承来的。

在比较噪声主导的区间，上界与下界在 d 和 τ 上一致。把下界写成 Ω(d²L²/(κ²ε²)) 就能看出两者共享 d² 和 κ 的依赖关系。两个界之间还差一个 Δ_f/(δε) 因子，论文说明了为什么把困难实例串联起来也无法在更大的 Δ_f 下补上这个差距。

该下界只在 τ 至少达到 Lδ 量级时才有信息量。超出这个区间，它并不约束基于比较的方法，因此“上下界一致”应理解为关于带噪比较区间的结论，而不是关于所有温度的结论。

实验揭示的代价与方差

在合成函数上，连续长度估计器与一个提前停止的嵌套变体在每个测试过的 κ 下都无偏。连续长度估计器的二阶矩更小，提前停止的嵌套估计器的代价以及代价与二阶矩的乘积更小；两者都在 κ⋆≈1.5 附近取到最小值。实测的梯度估计二阶矩在函数值反馈下随 d 增长，在比较反馈下随 d² 增长。

在糖尿病数据上用 ReLU 模型做 ℓ₁ 回归（442 个样本、10 个特征、d=49），Comparison-O2NC 用 1.8×10⁵ 次比较把损失从 1.05 降到 0.73±0.03，Comparison-SGD 降到 0.70±0.05；函数值预言机用 1.2×10⁵ 次求值达到 0.484±0.001。在固定迭代次数下，对 d∈{49,97,193}，基于比较的方法都高于函数值预言机。原因由一项单独测量定位：温度固定时，基于比较的 E‖G‖² 从 d=25 到 769 增长了 951 倍，接近 d² 增长预期的 946 倍。

在 Chebyshev–Rosenbrock 函数上，Comparison-O2NC 用少十倍的调用次数把梯度范数降到 0.87±0.06，而函数值预言机为 0.08±0.03。在 d=16 的摆杆起摆策略搜索中，Comparison-O2NC 用 4×10⁵ 次比较在三个随机种子中的两个上从所有初始状态成功起摆；函数值预言机用 10⁵ 次求值在三个种子中的一个上成功，Comparison-SGD 则停留在 6.2 到 6.8 之间。

温度与链接设定偏差会改变结论

平滑半径规则 ρ=min{δ/2, κ⋆τ/(2L)} 把 κ 限制在常数以内，实验说明了这个上限为何重要。在 2×10⁵ 次比较的预算下，只要比较仍有信息量，ρ=δ/2 就能工作；但一旦比较接近确定性，它就会失效：在 τ₀/64 时，一次估计约需 3×10⁴ 次比较，预算只够七次迭代，损失停留在初始的 1.05，而带上限的规则对每个 τ≤τ₀ 都给出 0.63 到 0.66。当 τ>τ₀ 时两种规则重合，损失在 4τ₀ 时退化到 0.80。

把链接形状或温度错设两倍，损失相对其正确设定下的 0.68 最多移动 0.1。理论要求链接函数已知且在透镜上解析，但实验表明估计器在中等程度的错设下会平缓退化。

在 τ=τ₀/32 时与八个调过参的基线相比，使用幅度信息的方法（论文的估计器、一个有偏的代入估计和 sign-SGD）在 Chebyshev–Rosenbrock 上达到 f≈0.35、平滑梯度范数落在 [0.23,0.39]；直接搜索停在 0.43，梯度范数高于 1.1；方向恢复类方法不收敛。在 ℓ₁ 回归上所有方法都落在 0.49 到 0.55，sign-SGD 最好，为 0.493 对 0.503，但它用的半径 ρ=2δ 超出了 Goldstein 论证允许的范围。

幅度信息何时值得付出代价

论文自己跨任务的比较给出了实用分界。符号的代价在大差值与小差值下相同，而无偏差值估计的代价随 e^{2Lρ/τ} 增长。这就是为什么在测试的预算下，基于符号的更新在 ℓ₁ 回归上具有竞争力甚至更好，也是论文指出基于符号的更新不带有此类保证的原因。

幅度信息在仅靠符号不足以推进时才划算：在 Chebyshev–Rosenbrock 上，使用幅度的方法达到 f≈0.35，而直接搜索停在 0.43。有偏的代入估计在两个任务上都与无偏估计相差不超过 0.01，因此在这些预算下实验没有显示无偏性带来实际优势，尽管分析所要求的正是无偏性。

最具决策意义的阈值是 κ，即被查询的最大差值除以 τ。当被查询的差值远小于温度时，单次比较的符号本身已经是差值（相差一个标量）的无偏估计，符号方法领先。当差值相对 τ 很大时，比较接近确定性，连续长度估计器变得昂贵，而带上限的平滑规则正是让方法保持可用的关键。

保证的适用边界

该保证要求链接函数已知且在透镜上解析，因此 logistic、probit 和 cauchit 链接符合条件，而仅在实区间附近解析的链接不符合。下界只在 τ 至少达到 Lδ 量级时才有信息量，估计器二阶矩界中的常数也偏松。摆杆实验用局部尺度的有限差分估计（d=16 时 L≈9）替代全局 Lipschitz 常数，而定理假设的是全局常数。

尚未补上的差距是上下界之间的 Δ_f/(δε) 因子。论文在比较噪声主导的区间闭合了 d 和 τ 的依赖，但没有闭合对 Δ_f 的联合依赖，因此该速率应视为在维度和温度上匹配，而不是对基于比较的复杂度的完整刻画。

论文确立的判断重点

论文的独特贡献不是单独一个更快的算法，而是证明可以从有限多个带噪比特中提取出精确无偏的差值估计，并且这足以支撑非光滑非凸优化中的 Goldstein 稳定性。代价是明确的：相对函数值预言机速率多出 d/κ² 因子，其来源是基于比较的梯度估计二阶矩按 d² 增长。

对判断比较反馈是否可行的读者来说，关键问题是所查询的差值相对 τ 处在什么位置。若差值相对 τ 很小，基于符号的更新是更便宜的选择，无偏估计器的优势只是理论上的。若差值相对 τ 很大，带上限的平滑规则与连续长度估计器才是让 Goldstein 保证可达的关键，代价是比较次数随差值与温度之比增长。

本文引用的文献