知识卡片：部分知情随机优化与零阶残差追踪

一句话结论

PISO（Partially Informed Stochastic Optimization）把“已知的部分梯度”和“由函数评估推断的残差”结合起来，通过对残差做在线追踪并以此为基准中心化零阶观测，降低探测方差并给出非凸收敛保证。

事件概述或研究问题

许多优化问题只能直接获得梯度的一部分，剩余分量必须通过函数评估（零阶信息）推断。论文指出这类结构出现在 performative prediction、performative reinforcement learning，以及下层为黑盒的双层优化（bilevel optimization with a black-box lower level）中。研究问题是：如何在仅部分知情（partially informed）的设定下设计随机优化方法，并给出收敛与函数评估复杂度保证。

方法/产品要点

• 提出 PISO：将可获得的梯度分量与残差的运行时估计（running estimate）结合。
• 核心机制：以残差估计为中心化每一次零阶观测，使随机探测带来的方差取决于“追踪误差”而非“残差本身的幅度”。
• 由此得到一个带显式收缩（contraction）机制的随机草图（randomized sketch）迭代，并为动量（momentum）提供了一种有原理的解释。
• 每次更新仅需：一个探测方向（one probe direction）、两个函数样本（two function samples）、一个已知分量样本（one known-component sample）。
• 使用独立采样的函数评估，以及高斯或球面探测（Gaussian or spherical probes）。
• 分析还量化了批处理（batching）如何用更多观测换取更少的部署（deployments）。

主要结果或产业意义

• 对光滑非凸目标给出收敛保证，其依赖残差的变化（variation）与初始幅度，不要求对不可获得的梯度分量有统一上界。
• 函数评估复杂度：在 Lipschitz 梯度下为 (O(d^{2}\varepsilon^{-6}))；在额外 Lipschitz-Hessian 假设下为 (O(d^{2}\varepsilon^{-5}))。
• 实验覆盖五个设定：在三个设定中，在可比的 oracle 访问下 PISO 变体优于所测基线；在双层路由（bilevel routing）中更快达到可比解；在 performative reinforcement learning 中，在“不使用响应模型导数”的方法里表现最好。

为什么重要

• 针对“只有部分梯度可知”的优化结构给出了通用算法框架，覆盖 performative prediction、performative RL 与黑盒下层双层优化等场景。
• 通过残差追踪把零阶探测的方差与追踪误差挂钩，而非与残差规模挂钩，为方差控制提供了新的思路。
• 在不假设不可得梯度分量有统一上界的前提下给出收敛保证，降低了理论假设的强度。

与既有脉络的关系

• 与“曲率感知零阶优化用于内存高效的测试时适应（CAZO）”同属零阶优化方向：CAZO 侧重用对角 Hessian 构造各向异性扰动以降低方差，面向 TTA；PISO 侧重在“部分梯度可知”的设定下追踪残差并中心化零阶观测。两者的方差控制思路与适用场景不同，本卡片不重复 CAZO 的具体结论。
• 本卡片与其他已有卡片（OptiAgent、ProxyPose）在主题上无直接延续关系。

局限与不确定性

• 论文未给出真实部署实验的细节与开源实现信息（待核实）。
• 实验中的基线选择、数据集与算力规模等细节未在摘要中说明（待核实）。
• 复杂度结果依赖 Lipschitz 梯度或额外的 Lipschitz-Hessian 假设，实际满足程度需结合具体任务（待核实）。
• “leading function-evaluation complexities”的具体比较对象与最优性界定需查阅正文（待核实）。

可用于图书/PPT/简报的角度

• “部分知情优化”作为一类问题结构：只拿到部分梯度时怎么办。
• 残差追踪 + 中心化零阶观测：把方差从“残差幅度”转移到“追踪误差”的直觉解释。
• 零阶优化中的动量解释：从随机草图与收缩机制角度理解 momentum。
• 函数评估复杂度对比：(O(d^{2}\varepsilon^{-6})) 与 (O(d^{2}\varepsilon^{-5})) 及其假设差异。
• 黑盒下层双层优化、performative prediction、performative RL 的应用场景串联。

原始材料

• 标题：Partially Informed Stochastic Optimization via Zeroth-Order Residual Tracking
• arXiv ID：2610.13871v1
• 作者：El Mahdi Chayti, Alireza Mirrokni, Martin Jaggi
• 发布时间：2026-10-09T17:20:41Z
• 更新：2026-10-09T17:20:41Z
• 主分类：cs.LG
• 分类：cs.LG
• Abstract URL：https://arxiv.org/abs/2610.13871v1
• PDF URL：https://arxiv.org/pdf/2610.13871v1
• 关键词：Partially Informed Stochastic Optimization; PISO; Zeroth-Order Residual Tracking; performative prediction; performative reinforcement learning; bilevel optimization; black-box lower level