The use of algorithmic predictions in decision-making leads to a feedback loop where the models we deploy actively influence the data distributions we see, and later use to retrain on. This dynamic was formalized by Perdomo et al. 2020 in their work on performative prediction. Our main result is an unconditional reduction showing that any no-regret algorithm deployed in performative settings converges to a (mixed) performatively stable equilibrium: a solution in which models actively shape data distributions in ways that their own predictions look optimal in hindsight. Prior to our work, all positive results in this area imposed strong restrictions on how models influenced distributions. By using a martingale argument and allowing randomization, we avoid any assumption on how populations respond to predictions and sidestep recent hardness results showing that deterministic stable models are in general PPAD-hard to compute. Lastly, on a more conceptual note, our connection sheds light on why common algorithms, like gradient descent, are naturally stabilizing and prevent runaway feedback loops. We hope our work enables future technical transfer of ideas between online optimization and performativity.
Figures & tables
Figure 1: Visualizing the performative stability guarantee. A mixture μ over models θ is stable if it shapes the data in a way that its own predictions are risk minimizing. Our notion, Definition 3 , generalizes the prior notion where μ is a point mass on a single model.
Figure 2: Our main result shows that any no-regret algorithm yields a sequence of models whose uniform mixture is performatively stable. The idea is simple and surprisingly strong. It sidesteps recent hardness results and establishes the first proofs of stability that do not require any continuity assumptions on D(⋅) or curvature assumptions on ℓ .
Table 1: Comparison to prior work. We let ρ=εβ/γ to denote the “standard” setting where ℓ is γ -strongly convex and β -smooth in θ , and D(⋅) is ε -Lipschitz. Our reduction establishes the first known stability guarantees for arbitrary distribution maps D(⋅) , and weakly convex losses, while matching the rates in prior work up to log factors. † : [ 30 , 10 ] . ‡ : [ 4 ] .
When algorithmic predictions inform people's decisions, the models we deploy are performative and actively shape the data we see. This feedback loop between algorithms and their broader environments introduces a challenge in the mechanics of social prediction: If different predictive models induce different distributions, is it possible to efficiently learn a prediction rule that is optimal for the distribution that it induces? Formally, this solution concept is known as performative stability. A core challenge in learning a performatively stable predictor is that, unlike supervised learning where distributions are fixed, the learner must deploy different predictors and observe their induced distributions. The main contribution of our work is a new algorithmic procedure that, in the high-accuracy regime, finds a performatively stable model in nearly the minimum number of model deployments without making any assumptions regarding how predictions shape distributions. In particular, our procedure succeeds at finding a randomized performatively stable predictor using exponentially fewer model deployments than prior approaches. Our second main contribution is a structural result showing how this recent randomized notion of stability achieved by our algorithm can be derandomized into a single predictor satisfying the prior deterministic notion if one is willing to assume that the loss is well-conditioned and that performative effects are weak, as in early work in this area. On a technical level, our results come from building on an underexplored technical connection between performative stability and expected variational inequalities.
Performative prediction studies feedback loops that arise when predictive models are deployed in consequential domains. In these settings, deploying a model can change the population whose patterns the model aims to predict, inducing a distribution shift that is endogenous to the learning system. This perspective departs from classical treatments of distribution shift, where shifts are typically modeled as exogenous changes in the data-generating process. Yet, in practice, distribution shift is rarely one or the other. Predictive models may influence future data through the decisions they support, while the world itself continues to drift for reasons beyond the learner's control. We study partially performative prediction, a framework that captures both endogenous and exogenous sources of distribution shift. The framework generalizes performative prediction by allowing the data distribution to evolve both in response to the deployed model and according to an external, time-varying process. We extend the central notions of performative stability and performative optimality to this setting by defining their online analogues that track the evolving partially performative environment. We analyze practical learning heuristics, including repeated retraining, and characterize when they successfully adapt to partially performative environments.
Jaewook Lee, Tijana Zrnic
Department of Electrical Engineering, Stanford University · Departments of Statistics and Management Science & Engineering, Stanford University
Predictive models deployed at scale influence future data, a phenomenon called performativity. And there is always one way to cope: Train the model on new data, deploy it again, and repeat. This process, called retraining or repeated risk minimization, creates a feedback loop between model and data that real-world learning systems can't avoid. Results on performative prediction shed light on this dynamic: If the model's influence on the data is small, retraining reaches a fixed point. What remains open is why fixed points should naturally exist, and what governs retraining when the model's influence is strong. In this work we develop a new perspective on retraining -- the stable signal principle -- that addresses these questions. We start from the assumption that the prediction target has at least some small model-independent component, a stable signal, such as the intrinsic quality of an item. We prove that when a nonzero stable signal exists, repeated risk minimization, suitably regularized, converges geometrically to the direction of this stable signal. This is true even if the model's influence on the target is arbitrarily large relative to the stable signal. Regularization emerges naturally as a force to control performativity, rather than to promote generalization, revealing a new facet of an old concept. We extend the analysis to a broad family of affine retraining operators under arbitrary model-induced feature changes, heterogeneous time-varying effects, and nonlinear responses. The stable signal perspective also applies to data feedback loops in language modeling, providing new explanations for the stability of language model training from model-generated data.
Moritz Hardt
Max Planck Institute for Intelligent Systems, Tübingen, and Tübingen AI Center