在线算法在反馈预测中自动趋于稳定，无需强假设。
The Stability of Online Algorithms in Performative Prediction
- 用鞅论证和随机化，不依赖数据响应假设。
- 任何无悔算法最终收敛到可表演稳定均衡。
- 解释梯度下降为何能抑制反馈循环，适合优化研究者。
算法预测用于决策时会形成反馈环：部署的模型影响观测数据分布，而这些分布又用于后续训练。这一动态由Perdomo等人（2020）提出为可表演预测。本文核心结果是首次给出无条件归约，证明任何无悔算法在可表演设置下均收敛至（混合）可表演稳定均衡——即模型主动塑造数据分布，使其自身预测在事后看来最优。此前所有正向结果均需对模型如何影响分布施加强限制。本文通过鞅论证与随机化，避免了对种群响应机制的假设，绕开了近期关于确定性稳定模型计算为PPAD-hard的硬性结论。此外，我们的联系揭示了为何梯度下降等常见算法天然具备稳定性，可防止反馈失控。期望本工作推动在线优化与可表演性之间的技术迁移。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。