Partially Informed Stochastic Optimization via Zeroth-Order Residual Tracking

We study stochastic optimization when the gradient splits into a component that can be computed directly and a component that is opaque, accessible only through zeroth-order evaluations of the objective. Performative prediction, performative reinforcement learning, and bilevel optimization with a black-box lower level all have this shape, yet each is served by a separate literature with a separate algorithm. We show that the right object to estimate is not the gradient but the \emph{residual} $v(x)=\nabla F(x)-\gamma g_K(x)$, and that identifying it is a randomized-sketch fixed-point problem rather than a variance-reduction problem. Centring each zeroth-order observation on the running estimate makes the sketch multiply the tracking \emph{error} instead of the target. Three consequences follow: the complexity is governed by the smoothness $L_v$ of the residual rather than of the full gradient, with no dependence on the magnitude of the opaque component; the momentum parameter is the step size of the sketch, with optimum $1-1/c_d$ and a stability window outside which the residual iteration diverges; and one sample of each oracle per iteration suffices, with no minibatching. Across five settings spanning all three areas, the method is best on three, matches the strongest published bilevel baseline while reaching its solution earlier on a fourth, and on the fifth is best among methods that query the environment rather than differentiating a model of it.