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(d2ε−6) under Lipschitz gradients and O(d2ε−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.
Figures & tables
Method
Setting
Complexity
Probes
Additional structure
Two-point ZO ( Ghadimi and Lan, 2013 )
black box
O(dε−4)
1
shared randomness
Guided ZO ( Hikima et al., 2025 )
perf. pred.
O(d4ε−6)
1
known component
Multi-direction ZO ( Hikima and Takeda, 2025a )
perf. pred.
O(d2ε−6) , O(d2ε−5)
Ω(d)
Q -Lipschitz ( ε−5 )
PZOS ( Fischer and Paccagnan, 2026 )
MPEC
O(d3/2ε−5) , Goldstein
1
bounded ∇f , exact ∇xf
PePG ( Basu et al., 2025 )
perf. RL
Ω(∣S∣∣A∣2ε−2(1−γ)−3)
n/a
response model
Piso (this work)
all three
O(d2ε−6) , O(d2ε−5)
1
split ( 1 ), gK 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 d4→d2 ; against the frontier we match d2 with L→Lv 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 100 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 10 – 90 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
cd
ς2
χ1
χ2
Gaussian, u=s∼N(0,Id)
d+2
d
d
d
Sphere, u=s=dw , ∥w∥=1
d
d
d
d
Coordinate, u=s=dei
d
d
d/2
d3/2/3
Appendix
Table 2: Constants for three standard families. Gaussian and sphere satisfy the smoothing identity (D4), with ν Gaussian and κ=1 for the first and ν uniform on the unit ball and κ=d for the second, and therefore share χ1=d . 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 d in χ1 . This is the structural cause of the known gap between coordinate and random directions.
Figure 3: Strategic classification on the credit dataset, d=12 , five strategic-response strengths τ . Training loss against samples consumed; means over 100 simulations with one-standard-error bands. All four Piso variants reach a loss of about 0.63 at every τ , while the strongest baseline plateaus near 0.80 ; the two methods that ignore the computable component degrade sharply as τ increases.
τ=0.5
τ=1
τ=2
τ=4
τ=8
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
Appendix
Table 3: Strategic classification: test loss and test accuracy (%) at the end of the sample budget, averaged over 100 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 0.2 in test loss and 4 – 10 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 8×8 gridworld, 20 seeds. Left: performative return Vππ against the number of trajectories consumed, with ±1.96 standard-error bands. Right: normalized L1 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 dx∈[100,300] 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 t=50 .
Figure 6: Routing, per-instance comparison of GaussianPISO against each baseline at t=10,25,50 , 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 t and at small dimension.
Figure 7: Components. gK alone (black) uses only the computable part and diverges once the opaque part matters; γgK+Rk (blue) adds the uncentred residual observation of Appendix B.1 with ρ=0 , 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 ρ⋆=1−1/cd , that is 0.917 for the Gaussian panels and 0.900 for the cycling panels, and predicts that the residual iteration is neutral at ρ=1−2/cd and expands below it, that is at 0.833 and 0.800 respectively (Appendix I ). Both are visible. The best curve is ρ=0.92 in all four panels, the nearest grid point to the prediction; ρ∈{0,0.5,0.8} all descend initially and then rise , the signature of a tracking error that grows once the sketch step size leaves its stability window; and ρ=0.99 is over-smoothed, descending furthest before turning up as the state lags the moving residual.
Figure 9: Known-component momentum ρK . Here ρK=0 , that is βK=1 and a fresh estimate, is among the best choices, and performance degrades monotonically for ρK≥0.7 . This is what the analysis predicts in this regime: with the growing batch the known-component variance σK2/nK is already small, so βK=1 satisfies the floor condition of ( 40 ) and a smaller βK only tightens the step-size cap η≤βK/(9γLK) of ( 10 ) and adds lag. The known-component average earns its place when nK is small, where it is what makes nK=1 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: γ=0 tracks ∇F and is worst, and large γ degrades as the noise term γ2σK2 and the drift constant Lv(γ) both grow. The interior optimum is γ∈{1,2} depending on the variant, consistent with Proposition 4 placing γ⋆=1+B/C 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 {0,0.25,0.5,0.75,1} , with λ=1 , which discards the state and uses the fresh observation alone, far worse than λ=0 . This is consistent with ( 51 ): at ρ=0.92 and cd∈{10,12} the high-signal-to-noise optimum λ⋆=(1/cd−β)/ρ is 0.004 and 0.022 , both below the smallest nonzero grid point, so the grid cannot separate λ⋆ from 0 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 L for the orthogonalized probe, at d=10 . Longer cycles are mildly better and L=d=10 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 L , 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.
Stochastic trajectory optimization methods like STOMP enable planning with non-differentiable costs, offering substantial flexibility over gradient-based approaches. We show that STOMP implicitly minimizes the KL divergence from a Boltzmann trajectory distribution, revealing an elegant Variational Inference (VI) structure underlying its updates. Building on this insight, we propose the \textit{Proximal Inference for Stochastic Trajectory Optimization} (PISTO) algorithm that stabilizes the updates by augmenting the objective with a KL regularization between successive Gaussian proposals. This proximal formulation admits a trust-region interpretation and yields closed-form mean updates computable as expectations under a surrogate distribution. We estimate these expectations via importance-weighted Monte Carlo sampling, producing a simple, derivative-free algorithm that inherits STOMP's ability to handle non-differentiable and discontinuous costs without modification. On robot arm motion planning benchmarks, PISTO achieves an 89% success rate -- outperforming CHOMP (63%) and STOMP (68%) -- while producing shorter, smoother paths at twice the speed of competing stochastic methods. We further validate PISTO on contact-rich MuJoCo locomotion and manipulation tasks, where it consistently outperforms both CEM and MPPI baselines in reward.
Hongzhe Yu, Zinuo Chang, Yongxin Chen
School of Aerospace Engineering, Georgia Institute of Technology, Atlanta, GA · School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, GA
This paper considers the nonconvex nonsmooth problem in which the objective function is Lipschitz continuous. We focus on the stochastic setting where the algorithm can access stochastic function value evaluations with heavy-tailed noise, which is prevalent in many popular machine learning applications. We propose a stochastic zeroth-order algorithm that refines the framework of online-to-nonconvex conversion by clipping the two-point gradient estimator. The theoretical analysis shows that our algorithm can find a (δ,ε)-Goldstein stationary point with zeroth-order oracle complexity of O(d2(p−1)pδ−1ε−p−12p−1), where d is the problem dimension and p∈(1,2] is the order of bounded moments. Note that our dependence on dimension d matches the best-known results of stochastic zeroth-order optimization for finding the sub-optimal solution of a stochastic convex nonsmooth problem. In addition, our dependence on accuracy parameters δ and ε is consistent with that of the best-known stochastic first-order algorithms for stochastic nonconvex nonsmooth problems. Finally, we conduct numerical experiments to demonstrate the effectiveness of the proposed method.
We study zeroth-order optimization of non-convex functions with the aid of directional hints, which are cheap but potentially inaccurate approximations of the true gradient direction, given by linear subspaces at each iteration. To leverage these hints adaptively while maintaining robustness to their quality, we introduce Control-Variate Zeroth-Order Descent (CV-ZOD), a new framework that refines the classical zeroth-order gradient estimator with a control variate that can be set based on the directional hints. We first show that the oracle algorithm that optimally sets the reference vector and step size at each iteration achieves a convergence rate that interpolates between the first-order O(1/T) rate and the zeroth-order O(d/T) rate, depending on the quality of the hints along the trajectory. We then develop a practical variant of CV-ZOD that achieves the same oracle guarantee up to logarithmic factors, without any prior knowledge of the hint quality. We validate the method empirically on simulation-based scientific optimization tasks, demonstrating sustained progress on non-convex landscapes where zeroth-order descent is slower and existing guided methods stall as guidance deteriorates.
Alexander Ryabchenko, Jian Qian, Wenlong Mou
University of Toronto and Vector Institute · University of Hong Kong