Trust-Region Optimization for Performative Prediction without Response Modeling

Performative prediction studies learning problems in which deployed decisions change the distribution of future data. Optimizing under this feedback requires understanding not only how a decision affects the loss, but also how the population responds to that decision. Existing approaches often make this problem tractable by imposing structure on the population response, but lead to limiting applicability when responses are poorly captured by a fixed model class. Generic black-box optimization avoids response modeling, but discards structure that is readily available in this setting: the loss function itself is often known in performative prediction. We introduce Performative Trust-Region Optimization (PTRO), which bridges these two approaches by optimizing performative risk without specifying or fitting a response model while still exploiting the known loss. The key idea is sampling from the current population to evaluate the known loss at nearby decisions, and use additional deployments only to estimate the effect of population response. This gives a local approximation of performative risk without committing to a model of how the population responds. PTRO then uses a trust-region mechanism to determine and adapt how far this local information can be trusted. Under moment-bounded losses and suitable smoothness and estimator-accuracy conditions, we establish high-probability convergence to an $ϵ$-stationary point of the performative risk with in $O({ϵ}^{-2})$ iterations, with $O(d^{3+2/q}{ϵ}^{-4})$ samples per iteration, where $d$ is the decision dimension and $q\ge 2$ is the loss-moment order. Experiments illustrate methods built around a specified response model can be more sample-efficient when their structural assumptions are accurate, whereas PTRO remains effective as the population response is poorly captured by a fixed model class. Ablations further show that both exploiting the known loss and adaptive trust-region updates are important for controlling the accuracy and efficiency.