在线算法在表演性预测中的稳定性

View PDF HTML (experimental)

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.

Subjects:	Machine Learning (cs.LG); Computers and Society (cs.CY); Computer Science and Game Theory (cs.GT); Machine Learning (stat.ML)
Cite as:	arXiv:2602.24207 [cs.LG]
	(or arXiv:2602.24207v3 [cs.LG] for this version)
	https://doi.org/10.48550/arXiv.2602.24207 arXiv-issued DOI via DataCite

Submission history

From: Juan Carlos Perdomo [view email]
[v1] Fri, 27 Feb 2026 17:35:03 UTC (23 KB)
[v2] Wed, 3 Jun 2026 18:07:07 UTC (26 KB)
[v3] Thu, 5 Nov 2026 15:47:59 UTC (26 KB)