The Stability of Online Algorithms in Performative Prediction | Gabriele Farina, Juan Carlos Perdomo | ResearchPod

Transcript: The Stability of Online Algorithms in Performative Prediction

Sam: Retrain a model on data your last model shaped, and you can chase your tail forever. A new theory result says the escape is simple. Randomize across the models your learner already produced.

Alex: Before the escape, place it for me. Whose work is this, and what kind of paper is it?

Sam: It's an arXiv preprint from Gabriele Farina at MIT and Juan Carlos Perdomo at MIT and NYU. It's a theory paper. There's a main theorem, some corollaries, and no experiments.

Alex: Most people I know retrain on fresh data and never think about feedback loops. Why should they care?

Sam: Because the data often depends on the model. A bank's credit model changes what people report. A school's dropout predictor triggers interventions that change who graduates. Retraining in those settings can fail to settle. This paper says a very wide class of standard algorithms does settle, with no assumptions on how people respond. So, what the problem is, the one idea, what the guarantees say, and where they stop.

Alex: Start with the vocabulary. What exactly is "settling" here?

Sam: The framework is called performative prediction. It means your predictions change the distribution of data you later see. The key solution concept is performative stability. A model is stable if, on the data it itself induced, no other model would have had lower loss. So if you retrain on its own data, you get the same model back. It's a fixed point of retraining.

Alex: And before this paper, when could you guarantee you'd reach that fixed point?

Sam: Under two strong conditions. The loss had to be strongly convex for every data point. And the distribution map, meaning how a deployed model shifts the data, had to be Lipschitz with a small constant. Roughly, small model changes cause small data changes, weak enough that retraining is a contraction.

Alex: Those sound like technical conditions people tolerate. Do they actually rule out anything important?

Sam: The authors argue they do. Take decisions made by thresholding a prediction. Their example is Wisconsin public schools, where students below a predicted graduation cutoff get an intervention. Prior work showed the chance of graduating jumps discontinuously at that cutoff. That's not Lipschitz at all. And common losses like squared loss and log loss, without a regularizer, aren't pointwise strongly convex either.

Alex: Couldn't someone just work harder on the analysis and find a stable model anyway?

Sam: Not always. There's a toy example from the original framework paper. Use squared loss, and suppose the data point is zero whenever your model is above one half, and one otherwise. Retraining produces zero, one, zero, one, forever. No stable model exists. And separately, work by Anagnostides and colleagues showed that even when stable models exist, finding one deterministically is PPAD-hard, a complexity class believed intractable. That holds even with nice, strongly convex, smooth losses once the feedback is strong enough.

The Stability of Online Algorithms in Performative Prediction

Gabriele Farina, Juan Carlos Perdomo

Feb 27, 2026·8:10·arxiv·Original Paper

Performative PredictionPerformatively Stable EquilibriumNo-Regret AlgorithmsMartingale ArgumentPerformative StabilityRegret Minimization

Listen

8 min

Summary

Understanding Performativity in Social Systems

Modern predictive systems rarely exist in isolation. In fields like credit scoring, healthcare, or school interventions, the models we deploy influence the behavior of the agents being modeled. This creates a feedback loop: a model determines an action, which alters the environment, which in turn generates new data used to retrain the model. This phenomenon is known as performative prediction. A primary goal in this framework is to reach a state of performative stability—a point where the model, by influencing the distribution, effectively justifies its own predictions and renders further retraining unnecessary.

Moving Beyond Restrictive Assumptions

Prior research established that achieving stable models often required stringent conditions, such as pointwise strong convexity of loss functions and a "smooth" response from the population. However, recent theoretical work demonstrated that finding deterministic stable models can be PPAD-hard, a computational complexity class suggesting that these solutions are generally difficult to find. Furthermore, many practical domains feature discontinuous data responses (e.g., thresholding based on model outcomes), which violate the smoothness assumptions previously required for convergence proofs.

The Power of No-Regret Dynamics

This paper introduces an unconditional reduction that bridges online learning and performative prediction. The authors prove that by simply maintaining a uniform mixture over the sequence of models produced by any no-regret algorithm, the learner is guaranteed to converge to a performatively stable equilibrium. This approach is powerful because it requires no assumptions on how the data distribution changes in response to the model. By utilizing martingale arguments rather than relying on deterministic contraction mappings, the researchers demonstrate that common algorithms—like gradient descent and repeated retraining—naturally lead to stability in environments where previous theory failed to provide guarantees. The authors further extend this result to multiplayer settings, showing that when multiple decision-makers independently run no-regret algorithms, the collective system also reaches a stable state.

Key Terms and Definitions

Performative Stability — A solution state where a model or mixture of models shapes the data distribution such that the model is risk-minimizing in hindsight.
No-Regret Algorithm — An optimization method that ensures the cumulative loss of its predictions is not significantly worse than the best fixed strategy in hindsight.
Distribution Map — A formal representation of how the choice of a model parameters influences the resulting data distribution.
Martingale Argument — A probabilistic tool used here to show that the discrepancy between empirical loss and expected loss vanishes, allowing for the convergence of randomized model mixtures to a stable equilibrium.
PPAD-Hard — A computational complexity classification indicating that a problem is likely difficult to solve efficiently, representing a significant barrier for finding deterministic stable models.

Abstract

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.

The Stability of Online Algorithms in Performative Prediction: Research Paper Podcast