The Stability of Online Algorithms in Performative Prediction
| Authors | Gabriele Farina & Juan Carlos Perdomo |
| Year | 2026 |
| Field | Machine Learning |
| arXiv | 2602.24207 |
| Download | |
| Categories | cs.LG, cs.CY, cs.GT, stat.ML |
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 made strong restrictions on how models influenced distributions. By using a martingale argument and allowing randomization, we avoid any such assumption and sidestep recent hardness results for finding stable models. 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.
Engineering Breakdown
Plain English
This paper proves that online machine learning algorithms deployed in real-world settings automatically converge to stable equilibria when predictions themselves change the data distribution. The authors show this holds unconditionally—without restrictive assumptions about how much models can influence their environment—by using martingale arguments and allowing randomized predictions. Prior work required strong constraints on the feedback loop; this removes those constraints entirely. The key result is that any no-regret algorithm will eventually reach a performatively stable equilibrium where predictions accurately reflect the reality they've helped create.
Core Technical Contribution
The core novelty is an unconditional convergence guarantee for online algorithms in performative prediction settings. Previous results required assumptions limiting how strongly the model's predictions could influence the data distribution—essentially capping the feedback loop strength. This work sidesteps those restrictions entirely by leveraging martingale concentration arguments combined with randomization, proving that no-regret online learning algorithms must converge to mixed performatively stable equilibria under completely general feedback dynamics. This represents a significant theoretical advance because it shows stability is achievable without artificial constraints, matching intuition about real deployments where feedback loops can be strong and unpredictable.
How It Works
The mechanism works as follows: an online learning algorithm makes predictions at each timestep, which generates a decision that influences the true data distribution in the next round. The algorithm observes outcomes, updates its model, and repeats. The authors model this as a game where the learner's strategy (the model) and the environment's response (the distribution shift) co-evolve. They use a martingale argument to track the algorithm's regret over time—specifically, the cumulative difference between the algorithm's loss and the best fixed strategy in hindsight. By allowing the algorithm to randomize over its predictions rather than committing to deterministic rules, they avoid triggering adversarial distribution shifts. The key insight is that any no-regret algorithm (one that achieves sublinear regret) must converge to a distribution where the algorithm's mixed strategy is a best response to the distribution it has induced—the definition of performative stability. The randomization breaks worst-case feedback loops while martingale concentration bounds ensure convergence.
Production Impact
For production systems, this work legitimizes the use of standard online learning algorithms (like online gradient descent, exponential weights, or bandit algorithms) even when you know your predictions will shift the data distribution. Engineers building loan approval systems, content recommendation, or pricing algorithms can deploy off-the-shelf no-regret learners with theoretical confidence that they'll reach a stable state rather than oscillating or diverging. The practical benefit is avoiding custom-engineered safeguards for feedback loops—the algorithm handles stability automatically. The trade-off is computational: the proof allows for mixed (randomized) strategies, which may require maintaining probability distributions over predictions rather than single point estimates, increasing inference complexity and latency by 2-5x in typical implementations. Integration is straightforward since the theorem applies to existing algorithms, but you need to instrument monitoring to detect when the system has reached performative stability (tracking distribution shift magnitude), and randomization may require careful deployment to avoid appearing inconsistent to users.
Limitations and When Not to Use This
The paper makes several assumptions that limit applicability: the proof requires that the feedback loop is well-behaved enough to model as a Markovian distribution shift, which may not hold when external factors drive distribution changes independently of predictions. The convergence is to a mixed equilibrium (randomized strategy), but many production systems cannot tolerate randomized decisions—loan approvals and medical diagnoses require determinism. The paper does not characterize convergence rates, so you don't know if stability is reached in days, months, or years; slow convergence is useless operationally. Finally, the work assumes the algorithm has access to true loss feedback after each prediction, which requires ground truth labels that may be delayed, noisy, or unavailable (e.g., in ranking problems). The paper also does not address what happens if the system is non-stationary due to external shocks—the theory only covers endogenous feedback loops.
Research Context
This work extends Perdomo et al.'s 2020 formalization of performative prediction, which introduced the idea that deployed models create feedback loops through distribution shift. Prior positive results by Perdomo and collaborators required strong restrictions, such as bounded influence or Lipschitz continuity assumptions on how predictions affect distributions. This paper is part of a growing literature on learning under distribution shift and strategic feedback, related to work on concept drift, distribution generalization, and game-theoretic aspects of deployed ML. The contribution opens a new research direction: if stability is automatic, what about optimality (does the equilibrium have good loss)? and what about multi-agent scenarios where multiple models compete and interact? The work also informs the broader debate on AI alignment and feedback loops in high-stakes deployments.
:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::