arXiv 新论文提出 PISO：零阶残差追踪应对部分梯度不可见优化
Partially Informed Stochastic Optimization via Zeroth-Order Residual Tracking
一篇优化理论新论文，处理一半梯度拿不到、得靠函数值猜的场景，复杂度界和实验都给全了，做双层优化或 performative 学习的可以看看。
arXiv 论文 2610.13871 提出 Partially Informed Stochastic Optimization（PISO），针对只能拿到部分梯度、其余需靠函数值估计的场景，如 performative prediction 和含黑盒下层的双层优化。方法把已知梯度分量与残差的运行估计结合，使随机探测带来的方差取决于追踪误差而非残差本身。在光滑非凸目标下，PISO 在 Lipschitz 梯度条件取得 O(d²ε⁻⁶) 的函数评估复杂度，加上 Lipschitz-Hessian 条件可达 O(d²ε⁻⁵)，每次更新只需 1 个探测方向、2 个函数采样和 1 个已知分量采样。在 5 个实验场景中，PISO 变体在 3 个上超过同阶 oracle 访问的基线，并在 performative 强化学习中成为无需响应模型导数的方法中表现最好的一个。
Partially Informed Stochastic Optimization via Zeroth-Order Residual Tracking
Many optimization problems provide direct access to only part of the gradient, while the remaining component must be inferred from function evaluations. This structure arises in performative prediction, performative reinforcement learning, and bilevel optimization with a black-box lower level. We introduce Partially Informed Stochastic Optimization (PISO), which combines the available gradient component with a running estimate of the residual. By centring each zeroth-order observation on this estimate, PISO makes the variance due to random probing depend on the tracking error rather than the residual's magnitude. This yields a randomized sketch iteration with an explicit contraction mechanism and a principled interpretation of momentum. For smooth nonconvex objectives, we establish convergence guarantees that depend on the residual's variation and initial magnitude, without requiring a uniform bound on the unavailable gradient component. With independently sampled function evaluations and Gaussian or spherical probes, PISO attains leading function-evaluation complexities of \(O(d^{2}\varepsilon^{-6})\) under Lipschitz gradients and \(O(d^{2}\varepsilon^{-5})\) under an additional Lipschitz-Hessian assumption. These rates require only one probe direction, two function samples, and one known-component sample per update. The analysis also quantifies how batching trades observations for fewer deployments. Across five settings, PISO variants improve on the tested baselines with comparable oracle access in three, reach a comparable solution faster in bilevel routing, and perform best among methods without response-model derivatives in performative reinforcement learning.