通过零阶残差跟踪实现部分信息随机优化

arXiv:2610.13871v1 公告类型：新论文 摘要：许多优化问题仅能直接获取部分梯度，而其余分量必须通过函数求值来推断。这种结构出现在施为预测、施为强化学习以及下层为黑箱的双层优化中。我们提出 Partially Informed Stochastic Optimization（PISO），将可获取的梯度分量与残差的动态估计相结合。通过以该估计为中心对每次零阶观测进行中心化，PISO 使随机探测引起的方差取决于跟踪误差，而非残差的大小。由此得到一种具有显式收缩机制的随机化草图迭代，并为动量提供了有理论依据的解释。对于光滑非凸目标，我们建立了依赖于残差变化量及其初始大小的收敛保证，而不要求不可获取的梯度分量具有一致界。在采用独立采样的函数求值以及高斯或球面探测方向时，PISO 在梯度满足 Lipschitz 条件下达到的函数求值复杂度主导项为 \(O(d^{2}\varepsilon^{-6})\)，在额外假设 Hessian 矩阵满足 Lipschitz 条件下则为 \(O(d^{2}\varepsilon^{-5})\)。实现这些速率，每次更新仅需一个探测方向、两个函数样本和一个已知分量样本。分析还量化了批处理如何通过增加观测次数来减少部署次数。在五种实验设置中，PISO 的变体在其中三种设置下，以相当的预言机访问条件优于所测试的基线方法；在双层路由问题中更快达到相当的解；在施为强化学习中，则在不使用响应模型导数的方法中表现最佳。