零阶残差跟踪如何优化部分已知梯度？

梯度被拆成已知与不透明两部分

许多优化问题只能直接获得梯度的一部分。论文把梯度写成两项之和：g_K 可以通过直接采样估计，g_U 则只能借助对目标函数 F 的带噪评估间接获得。论文举出的典型场景有三类：在表演性预测中，部署的模型会改变数据分布；在表演性强化学习中，环境会对策略作出反应；在双层问题中，下层是一个黑箱，例如道路管理机构设定通行费、司机据此重新选路。在收费场景里，只要观察到跟随者的响应，领导者一侧的偏导数就是精确的，真正缺失的是响应雅可比矩阵。

如果把 F 当作黑箱、对整个梯度做零阶优化，就等于丢掉了 g_K。论文保留了应当使用 g_K 这一前提，但改变了被估计的对象：不再在每一步从零开始估计完整梯度或不透明部分，而是维护一个残差的持续估计，并要求每次新观测报告当前估计错在哪里。

让每次探测以当前估计为中心

被跟踪的对象是残差 v(x) = ∇F(x) − γ g_K(x)，它在 γ = 1 时等于 g_U，在 γ = 0 时等于完整梯度。方法维护一个状态 m_k，用来跟踪 v(x_k)，于是 γ g_K(x_k) + m_k 就构成对完整梯度的估计。每次迭代抽取一个探测方向 u_k 及其得分 s_k，用两次函数查询构造对称的两点方向导数，再减去当前估计与探测方向的内积。

由此得到的观测 R_k = m_k + (D_k − ⟨γ ĝ_K(x_k) + m_k, u_k⟩) s_k 与未中心化的估计瞄准同一个目标，因为 m_k 在期望意义下两次出现相互抵消。改变的是误差尺度：它现在由 v(x_k) 与 m_k 之间的距离决定，而不是由 v(x_k) 的大小决定。论文把这一做法归入控制变量与误差反馈的思路——估计的是对一个已知量的修正，而不是这个量本身。另有一个平均状态 h_k 单独跟踪已知分量，因为直接使用新鲜的 ĝ_K 会把它的全部方差注入搜索方向。

动量对应一次收缩的定点迭代

在预言机精确、迭代点固定的理想情形下，跟踪误差满足 E_{k+1} = (I_d − βP_k)E_k，其中 P_k 是秩一草图 s_k u_kᵀ，β = 1 − ρ 等于 1 减去动量参数。这相当于在 ½‖m − v‖² 上做步长为 β 的随机梯度下降，只是梯度被替换成了它的无偏草图。取二阶矩后得到收缩因子 θ(b) = 1 − 2b + c_d b²，其中 c_d 对高斯探测为 d + 2，对球面探测为 d。

该因子小于 1 当且仅当 0 < β < 2/c_d，在 β = 1/c_d 处取最小值，在 β = 2/c_d 处等于 1。论文由此得出一个反直觉的推论：ρ = 0 并不是“没有动量”，而是 β = 1，对应 θ(1) = c_d − 1 的扩张映射。因此最优动量是 ρ* = 1 − 1/c_d，而残差迭代在 ρ = 1 − 2/c_d 处处于中性。这也是论文称其对动量的解释有原理依据、而非启发式的原因。

收敛保证取决于残差漂移而非其大小

对于光滑的非凸目标，主定理给出 T 次迭代上平均梯度平方范数的上界。该上界包含一个与 ‖v(x_0)‖² 成正比的初始化项、一个已知预言机方差项，以及若干噪声项和偏差项。关键在于，它不要求 ‖g_U‖ 的一致上界，也不要求有界区域、凸性或 Polyak-Łojasiewicz 条件。不透明分量只通过它在起点处的取值，以及通过一个刻画残差每步移动幅度的常数 L_v 进入结论，L_v 定义为满足该逐步界的最小常数。

由于 v 是 (L + γL_K)-Lipschitz 的，L_v 总是有限，且不超过 L + γL_K。当 L_v 较小时，这些速率优于黑箱方法的速率，论文指出这取决于具体问题。步长依据 L + γL_K 这类先验上界设定；沿轨迹得到的 L_v 只能在事后收紧界。已知预言机方差总是乘以 βc_d、β̃²c_d 或 β_K，这正是每次迭代只需一个已知分量采样的原因；当 ρ_K = 0 时该系数变为常数阶，方差就变成无法消除的下限。

共享随机性决定两种复杂度情形

论文区分了两种预言机情形。当两次函数查询可以共享随机性时，噪声主要由一个与探测半径无关的梯度项主导，取量级为 min{σ_g/ℓ, ε/L} 的有限半径即可，方法在 O(Δ_v d (γ²σ_K² + σ_g²) ε⁻⁴) 次迭代内达到 ε-稳定，其中 Δ_v = L_v Δ_F + ‖v(x_0)‖²。

在表演性问题中，两次查询分别部署 x_k ± μ_k u_k，并从两个不同分布采样，因此无法共享随机性。此时探测半径必须在正比于 σ_F²/(2μ_k² n_F) 的方差项与有限差分偏差之间取得平衡，而且这种平衡是不对称的：方差被 β 压低，均值偏差却没有。这决定了 ε 的指数。在 Lipschitz 梯度条件下，方法达到 O(d²ε⁻⁶) 的函数评估复杂度；在额外假设 Hessian 为 Lipschitz 时，达到 O(d²ε⁻⁵)。这两个速率都只需每次更新一个探测方向、两个函数采样和一个已知分量采样。分析还量化了批处理如何用更多观测换取更少的部署次数。

残差跟踪在什么条件下划算

论文把与黑箱方法的比较写得明确。令 γ = 0 时残差等于完整梯度，方法退化为黑箱方法，其主导项为 L Δ_F d σ_g² ε⁻⁴。PISO 对应的项是 L_v Δ_F d (γ²σ_K² + σ_g²) ε⁻⁴，因为残差观测减去了 ⟨γĝ_K, u_k⟩，也继承了它的噪声。因此 PISO 恰好当 L_v/L < σ_g²/(σ_g² + γ²σ_K²) 时优于黑箱基线。

换句话说，残差必须比 F 更光滑，光滑的程度至少要抵消已知预言机对观测噪声的放大倍数。论文指出，不等式两边都可以估计，而且只要已知分量相对于函数预言机足够准确，该条件就有充足余量；论文称其所有实验场景都满足这一点。收益在不透明分量沿轨迹变化缓慢时才会实现；在表演性预测中，L_v 随表演性敏感度变化。

五个场景中三处明确胜出

论文报告了五个场景的实验。PISO 的各个变体在其中三个场景里以相当的预言机访问量优于所测试的基线，在双层路由问题中更快达到可比解，在表演性强化学习中在不使用响应模型导数的方法里表现最好。摘要没有给出各场景的具体差距，因此这里概述的证据并未确定每项改进的幅度。

论文还把自己的探测预算与先前工作做了对比：此前的保证要求每次更新 N = Ω(d) 个探测，按其常数会迫使 N ≥ 81d，而在 d = 30 时由此得到的查询次数超过了该工作自身 5000 个样本的预算。PISO 每次更新只需一个探测，这正是其分析所支撑的结构性差异。

光滑性假设与尚未解决的扩展

收敛分析假设目标光滑，论文也承认均衡响应映射未必满足这一条件。论文把残差跟踪推广到 Goldstein 稳定点，作为处理非光滑双层问题的一条路径。实验中表现较强的正交循环变体使用了相关探测，超出了论文的假设范围，对其进行分析仍是开放问题。批处理分析还揭示了一种资源权衡：在 n_K = 1 时，不做平均时已知分量采样的总数为 Θ(ε⁻⁸)，做平均后为 Θ(ε⁻⁶)，也就是说已知分量动量在这一资源上换来了 ε⁻² 的因子。

因此论文确立的实践优先级是有条件的，而非普适的。当不透明分量相对于完整目标漂移缓慢，且已知预言机相对于函数预言机足够准确时，残差跟踪才是正确选择；论文给出的显式阈值 L_v/L < σ_g²/(σ_g² + γ²σ_K²)，就是判断用 L_v 替代 L 究竟是收益还是代价的自有检验标准。

本文引用的文献