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 ] .