cs.LGOct 9, 2026
SavePartially Informed Stochastic Optimization via Zeroth-Order Residual Tracking
Organizations: Machine Learning and Optimization Laboratory (MLO), EPFL
Abstract
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 under Lipschitz gradients and 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.
Figures & tables
| Method | Setting | Complexity | Probes | Additional structure |
| Two-point ZO ( Ghadimi and Lan, 2013 ) | black box | shared randomness | ||
| Guided ZO ( Hikima et al., 2025 ) | perf. pred. | known component | ||
| Multi-direction ZO ( Hikima and Takeda, 2025a ) | perf. pred. | , | -Lipschitz ( ) | |
| PZOS ( Fischer and Paccagnan, 2026 ) | MPEC | , Goldstein | bounded , exact | |
| PePG ( Basu et al., 2025 ) | perf. RL | n/a | response model | |
| Piso (this work) | all three | , | split ( 1 ), oracle |
Table 1: Complexities as reported by each source; criteria and oracle models differ, so only the last two columns compare directly. Against the guided line we improve ; against the frontier we match with and one probe per update; PZOS has a Goldstein guarantee we lack but assumes bounded gradients and a deterministic follower; PePG requires a differentiable response model.
Figure 1: Multiproduct pricing, six weekly instances. Objective (lower is better) against samples consumed; means over simulations with one-standard-error bands. All four Piso variants separate from the guided baselines early in the run and the cycling variants attain the lowest objective on every instance. ZO-TG and ZO-OGVR, which do not use the computable component, remain far behind.
Figure 2: Bilevel games with an opaque lower level; per-instance normalized objective against iteration, median with interquartile and – percentile bands. (a) Routing is a maximization problem: Piso attains the same endpoint as PZOS but reaches it well before the guided baselines. (b) Security is a minimization problem: Piso separates from PZOS from the first iterations and ends below it.
Appendix figures & tables12 assets
Supplementary material from the paper’s appendix.
Appendix
| family | ||||
|---|---|---|---|---|
| Gaussian, | ||||
| Sphere, , | ||||
| Coordinate, |
Table 2: Constants for three standard families. Gaussian and sphere satisfy the smoothing identity (D4), with Gaussian and for the first and uniform on the unit ball and for the second, and therefore share . The coordinate family fails (D4): its mean estimator is the coordinate-wise finite-difference gradient, which is not the gradient of any smoothing, and it loses a factor in . This is the structural cause of the known gap between coordinate and random directions.
Figure 3: Strategic classification on the credit dataset, , five strategic-response strengths . Training loss against samples consumed; means over simulations with one-standard-error bands. All four Piso variants reach a loss of about at every , while the strongest baseline plateaus near ; the two methods that ignore the computable component degrade sharply as increases.
| Method | loss | acc. | loss | acc. | loss | acc. | loss | acc. | loss | acc. |
|---|---|---|---|---|---|---|---|---|---|---|
| GZO-NS | 0.891 | 59.1 | 0.912 | 60.8 | 0.899 | 63.2 | 0.879 | 65.0 | 0.878 | 65.7 |
| GZO-HS | 0.846 | 57.2 | 0.862 | 59.8 | 0.865 | 62.0 | 0.835 | 63.7 | 0.821 | 65.0 |
| ZO-TG | 1.428 | 45.4 | 1.487 | 46.0 | 1.505 | 45.8 | 1.558 | 44.6 | 1.580 | 44.1 |
| ZO-OGVR | 1.181 | 51.4 | 1.243 | 52.8 | 1.383 | 54.3 | 1.539 | 54.9 | 1.534 | 56.4 |
| GaussianPISO | 0.624 | 66.6 | 0.620 | 67.6 | 0.632 | 67.7 | 0.622 | 69.3 | 0.631 | 69.0 |
Table 3: Strategic classification: test loss and test accuracy (%) at the end of the sample budget, averaged over simulations, for each strategic-response strength . Best per column in bold. All four Piso variants dominate every baseline on both metrics at every , by roughly in test loss and – accuracy points. The two methods that ignore the computable component, ZO-TG and ZO-OGVR, degrade as grows, that is as the opaque component becomes more influential, whereas the Piso variants are essentially flat in ; the guided baselines improve with but never close the gap. Training metrics are in the accompanying archive.
Figure 4: Performative reinforcement learning on an gridworld, seeds. Left: performative return against the number of trajectories consumed, with standard-error bands. Right: normalized change of the state occupancy between consecutive updates, on a log scale. Piso and Piso 2 make the fastest early progress among the methods that operate under ( 1 ), while GZO-NS closes part of the gap late in the run. PePG is a reference with privileged information: it is supplied with exact reward and transition response Jacobians and exact tabular advantages, so it differentiates the environment’s response rather than querying it. Its curve is not a bound on what other methods can attain, but it indicates what a differentiable response model is worth.
Figure 5: Security game, normalized objective against problem dimension at three iteration counts. The separation between Piso and PZOS is stable across the range, and both separate from the guided baselines, whose objective does not decrease appreciably after .
Figure 6: Routing, per-instance comparison of GaussianPISO against each baseline at , coloured by problem dimension. Points above the diagonal favour Piso , which is a maximization problem here. The PZOS row lies on the diagonal at every horizon, so the two methods return the same solution per instance; the ZOS, GZO-NS and GZO-HS rows lie above it, with the margin largest at small and at small dimension.
Figure 7: Components. alone (black) uses only the computable part and diverges once the opaque part matters; (blue) adds the uncentred residual observation of Appendix B.1 with , and is unstable; Piso and Piso 2 add the centring and the momentum. The two unstable arms are the two ways of omitting a piece of ( 6 ), and confirm that neither the known component nor an uncentred zeroth-order correction suffices on its own.
Figure 8: Momentum , the sharpest test of the analysis. Theory predicts an optimum at , that is for the Gaussian panels and for the cycling panels, and predicts that the residual iteration is neutral at and expands below it, that is at and respectively (Appendix I ). Both are visible. The best curve is in all four panels, the nearest grid point to the prediction; all descend initially and then rise , the signature of a tracking error that grows once the sketch step size leaves its stability window; and is over-smoothed, descending furthest before turning up as the state lags the moving residual.
Figure 9: Known-component momentum . Here , that is and a fresh estimate, is among the best choices, and performance degrades monotonically for . This is what the analysis predicts in this regime: with the growing batch the known-component variance is already small, so satisfies the floor condition of ( 40 ) and a smaller only tightens the step-size cap of ( 10 ) and adds lag. The known-component average earns its place when is small, where it is what makes admissible (Remark 30 ); it is not needed when one can afford a large batch.
Figure 10: Known-component weight . The endpoints behave as § G.4 describes: tracks and is worst, and large degrades as the noise term and the drift constant both grow. The interior optimum is depending on the variant, consistent with Proposition 4 placing away from both endpoints, though the grid is too coarse to resolve precisely and we do not attempt to estimate it directly.
Figure 11: Mixing weight . Performance is monotonically decreasing in over the grid , with , which discards the state and uses the fresh observation alone, far worse than . This is consistent with ( 51 ): at and the high-signal-to-noise optimum is and , both below the smallest nonzero grid point, so the grid cannot separate from and only the degradation for large is resolved. A finer sweep near zero would be needed to test the prescription itself.
Figure 12: Cycle length for the orthogonalized probe, at . Longer cycles are mildly better and is best, but the differences are small and within a fraction of the spread of the ablation. Since the per-step marginal is the same for every , and only the dependence between consecutive probes changes, the analysis of § 3 does not distinguish these curves; the ordering is consistent with orthogonality reducing the effective sketch variance, but we do not claim it as a prediction.