A gradient split into known and opaque parts
Many optimization problems expose only part of the gradient. The paper writes the gradient as a sum of two terms: g_K, which can be estimated by direct sampling, and g_U, which can only be reached through noisy evaluations of the objective F. The motivating settings are performative prediction, where a deployed model shifts the data distribution; performative reinforcement learning, where the environment reacts to the policy; and bilevel problems whose lower level is a black box, such as a road authority setting tolls while drivers reroute. In the toll case the leader's partial derivatives are exact once the followers' response is observed, and what is missing is the response Jacobian.
Treating F as a black box and applying zeroth-order optimization to the whole gradient discards g_K. The paper keeps the premise that g_K should be used but changes what is estimated: instead of estimating the full gradient or the opaque part from scratch at each step, it maintains a running estimate of the residual and asks each new observation to report how wrong that estimate currently is.
Centring each probe on the running estimate
The tracked object is the residual v(x) = ∇F(x) − γ g_K(x), which equals g_U at γ = 1 and the full gradient at γ = 0. The method keeps a state m_k intended to track v(x_k), so that γ g_K(x_k) + m_k estimates the full gradient. Each iteration draws one probe direction u_k with a score s_k, forms a symmetric two-point directional derivative from two function queries, and subtracts the inner product of the current estimate with the probe.
The resulting observation R_k = m_k + (D_k − ⟨γ ĝ_K(x_k) + m_k, u_k⟩) s_k has the same target as an uncentred estimate, because the two occurrences of m_k cancel in expectation. What changes is the error scale: it is now set by the distance between v(x_k) and m_k rather than by the magnitude of v(x_k). The paper describes this as the device behind control variates and error feedback — estimate the correction to a known quantity, not the quantity itself. A separate averaged state h_k tracks the known component, because using ĝ_K fresh would inject its full variance into the search direction.
Momentum as a contracting fixed-point step
With exact oracles and a stationary iterate, the tracking error follows E_{k+1} = (I_d − βP_k)E_k, where P_k is the rank-one sketch s_k u_kᵀ and β = 1 − ρ is one minus the momentum parameter. This is a step of stochastic gradient descent on ½‖m − v‖² with step size β, with the gradient replaced by its unbiased sketch. Taking second moments gives a contraction factor θ(b) = 1 − 2b + c_d b², where c_d is d + 2 for Gaussian probes and d for spherical probes.
The factor is below one exactly when 0 < β < 2/c_d, is minimized at β = 1/c_d, and equals one at β = 2/c_d. The paper draws a counterintuitive consequence: ρ = 0 is not "no momentum" but β = 1, an expanding map with θ(1) = c_d − 1. The optimal momentum is therefore ρ* = 1 − 1/c_d, and the residual iteration is neutral at ρ = 1 − 2/c_d. This is why the paper calls its momentum interpretation principled rather than heuristic.
Guarantees that depend on residual drift, not its size
For smooth nonconvex objectives, the main theorem bounds the average squared gradient norm over T iterations. The bound contains an initialization term proportional to ‖v(x_0)‖², a known-oracle variance term, and noise and bias terms. Crucially, it requires no uniform bound on ‖g_U‖, no bounded domain, no convexity and no Polyak-Łojasiewicz condition. The opaque component enters only through its value at the starting point and through its drift, captured by a constant L_v defined as the smallest constant satisfying a per-step bound on how much the residual moves.
Because v is (L + γL_K)-Lipschitz, L_v is always finite and never exceeds L + γL_K. The rates improve on black-box ones when L_v is small, which the paper says depends on the problem. The step size is set with an a-priori upper bound such as L + γL_K; the trajectory-specific L_v sharpens the bound only retrospectively. The known-oracle variance appears multiplied by βc_d, β̃²c_d or β_K, which is what allows a single known-component sample per iteration; at ρ_K = 0 the coefficient becomes order one and the variance turns into a floor.
Two complexity regimes set by shared randomness
The paper separates two oracle regimes. When the two function queries can share randomness, the noise is dominated by a gradient term that does not depend on the probe radius, a finite radius of order min{σ_g/ℓ, ε/L} suffices, and the method reaches ε-stationarity in O(Δ_v d (γ²σ_K² + σ_g²) ε⁻⁴) iterations, with Δ_v = L_v Δ_F + ‖v(x_0)‖².
In a performative problem the two queries deploy x_k ± μ_k u_k and sample from two different distributions, so they cannot share randomness. The probe radius must then balance a variance term proportional to σ_F²/(2μ_k² n_F) against finite-difference bias, and the balance is asymmetric because variance is damped by β while the mean bias is not. This fixes the exponent of ε. Under Lipschitz gradients the method attains O(d²ε⁻⁶) function-evaluation complexity; under an additional Lipschitz-Hessian assumption it attains O(d²ε⁻⁵). Both rates need only one probe direction, two function samples and one known-component sample per update. The analysis also quantifies how batching trades more observations for fewer deployments.
The condition under which tracking pays off
The paper makes the comparison with a black-box method explicit. Setting γ = 0 makes the residual equal the full gradient and recovers a black-box method whose leading term is L Δ_F d σ_g² ε⁻⁴. The corresponding PISO term is L_v Δ_F d (γ²σ_K² + σ_g²) ε⁻⁴, because the residual observation subtracts ⟨γĝ_K, u_k⟩ and inherits its noise. PISO therefore improves on the black-box baseline exactly when L_v/L < σ_g²/(σ_g² + γ²σ_K²).
In words, the residual must be smoother than F by at least the factor by which the known oracle inflates the observation noise. The paper notes that both sides are estimable and that the condition holds with room to spare whenever the known component is accurate relative to the function oracle, which it says is the case in all of its settings. The gain is realized when the opaque component varies slowly along the trajectory; in performative prediction L_v scales with the performative sensitivity.
Five settings, three clear wins
The paper reports experiments across five settings. PISO variants improve on the tested baselines with comparable oracle access in three of them, reach a comparable solution faster in bilevel routing, and perform best among methods without response-model derivatives in performative reinforcement learning. The abstract does not report per-setting margins, so the size of each improvement is not established by the evidence summarized here.
The paper also contrasts its probe budget with prior work: the earlier guarantee required N = Ω(d) probes per update, which with its constants forces N ≥ 81d, and at d = 30 the resulting query count exceeds that work's own 5000-sample budget. PISO's one-probe-per-update requirement is the structural difference the analysis is built to support.
Smoothness assumptions and open extensions
The convergence analysis assumes a smooth objective, and the paper acknowledges that equilibrium response maps need not produce one. Extending residual tracking to Goldstein stationarity is named as a route to nonsmooth bilevel problems. The empirically strong orthogonal cycling variants use dependent probes that fall outside the paper's assumptions, and analysing them remains open. The batching analysis also shows a resource trade: the total number of known-component samples is Θ(ε⁻⁸) without averaging and Θ(ε⁻⁶) with it at n_K = 1, so known-component momentum buys a factor of ε⁻² in that resource.
The practical priority the paper establishes is therefore conditional rather than universal. Residual tracking is the right choice when the opaque component drifts slowly relative to the full objective and the known oracle is accurate relative to the function oracle; the explicit threshold L_v/L < σ_g²/(σ_g² + γ²σ_K²) is the paper's own test for whether the substitution of L_v for L is a gain rather than a cost.
Sources used in this answer
Partially Informed Stochastic Optimization via Zeroth-Order Residual Tracking
PISO centres zeroth-order probes on a running residual estimate, making probing variance depend on tracking error rather than residual magnitude, and attains O(d²ε⁻⁶) function-evaluation complexity under Lipschitz gradients with one probe direction per update.