# The Stability of Online Algorithms in Performative Prediction

arXiv: https://arxiv.org/abs/2602.24207 · HTML: https://mlsanity.com/paper/2602.24207/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 49 references that are in the map.
- First posted on arXiv 27 Feb 2026.

## Builds on (most cited first, 30 of 34)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Performative Prediction](https://mlsanity.com/paper/2002.06673/) (2020)
- [Strategic Classification](https://mlsanity.com/paper/1506.06980/) (2015)
- [Game-theoretic statistics and safe anytime-valid inference](https://mlsanity.com/paper/2210.01948/) (2022)
- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [Outside the Echo Chamber: Optimizing the Performative Risk](https://mlsanity.com/paper/2102.08570/) (2021)
- [Stochastic Optimization for Performative Prediction](https://mlsanity.com/paper/2006.06887/) (2020)
- [Performative Prediction in a Stateful World](https://mlsanity.com/paper/2011.03885/) (2020)
- [How to Learn when Data Reacts to Your Model: Performative Gradient Descent](https://mlsanity.com/paper/2102.07698/) (2021)
- [Stochastic optimization with decision-dependent distributions](https://mlsanity.com/paper/2011.11173/) (2020)
- [Data Feedback Loops: Model-driven Amplification of Dataset Biases](https://mlsanity.com/paper/2209.03942/) (2022)
- [Performative Prediction: Past and Future](https://mlsanity.com/paper/2310.16608/) (2023)
- [Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion](https://mlsanity.com/paper/2302.03775/) (2023)
- [Multiplayer Performative Prediction: Learning in Decision-Dependent Games](https://mlsanity.com/paper/2201.03398/) (2022)
- [Regret Minimization with Performative Feedback](https://mlsanity.com/paper/2202.00628/) (2022)
- [State Dependent Performative Prediction with Stochastic Approximation](https://mlsanity.com/paper/2110.00800/) (2021)
- [Difficult Lessons on Social Prediction from Wisconsin Public Schools](https://mlsanity.com/paper/2304.06205/) (2023)
- [Performative Prediction with Neural Networks](https://mlsanity.com/paper/2304.06879/) (2023)
- [Multi-agent Performative Prediction: From Global Stability and Optimality to Chaos](https://mlsanity.com/paper/2201.10483/) (2022)
- [Making Decisions under Outcome Performativity](https://mlsanity.com/paper/2210.01745/) (2022)
- [Decision-Dependent Risk Minimization in Geometrically Decaying Dynamic Environments](https://mlsanity.com/paper/2204.08281/) (2022)
- [Fast swap regret minimization and applications to approximate correlated equilibria](https://mlsanity.com/paper/2310.19647/) (2023)
- [On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities](https://mlsanity.com/paper/1510.03925/) (2015)
- [Multi-agent Performative Prediction with Greedy Deployment and Consensus Seeking Agents](https://mlsanity.com/paper/2209.03811/) (2022)
- [Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium](https://mlsanity.com/paper/2104.01520/) (2021)
- [Plug-in Performative Optimization](https://mlsanity.com/paper/2305.18728/) (2023)
- [Online Projected Gradient Descent for Stochastic Optimization with Decision-Dependent Distributions](https://mlsanity.com/paper/2107.09721/) (2021)
- [Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates](https://mlsanity.com/paper/1506.04838/) (2015)
- [Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games](https://mlsanity.com/paper/2412.20291/) (2024)
- [From External to Swap Regret 2.0: An Efficient Reduction and Oblivious Adversary for Large Action Spaces](https://mlsanity.com/paper/2310.19786/) (2023)

## Built on by (most cited first, 4 of 4)

- [Partially Performative Prediction](https://mlsanity.com/paper/2606.07890/) (2026)
- [Retraining Seeks Stable Signals](https://mlsanity.com/paper/2607.15623/) (2026)
- [Local and Global Stability in Performative Reinforcement Learning](https://mlsanity.com/paper/2609.06467/) (2026)
- [Stabilizing Performative Feedback Loops with Minimal Model Deployments](https://mlsanity.com/paper/2609.14065/) (2026)

## Abstract (arXiv)

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.