揭示预测模型部署后数据分布变化的计算复杂性边界
On the Computational Complexity of Performative Prediction
- 证明当影响强度ρ>1时，求解稳定预测点是计算上难解的
- 即使在简单线性分布变化下，计算复杂度仍达PPAD完全
- 适用于关注模型部署后反馈效应的研究者
绩效预测描述了部署预测模型会改变底层数据分布的现象。当绩效效应较弱（ρ<1）时，简单的重训练动态已知可线性收敛，但ρ>1情形的复杂性此前未知。本文建立了一个精确的相变：计算一个ε-绩效稳定点是PPAD完全的——即与一般和博弈中的纳什均衡在多项式时间内等价——即使ρ=1+O(ε)。这种计算困难性在二次损失函数和线性分布偏移的看似简单设定中依然存在。我们关键技术贡献之一是将该PPAD难解性结果推广至一般的凸域，这对变分不等式的复杂性研究具有更广泛意义。最后，我们研究了战略分类的特殊情况，证明计算战略局部最优是PLS难的。
原文摘要 · Abstract (English)
Performative prediction captures the phenomenon where deploying a predictive model shifts the underlying data distribution. While simple retraining dynamics are known to converge linearly when the performative effects are weak ($ρ< 1$), the complexity in the regime $ρ> 1$ was hitherto open. In this paper, we establish a sharp phase transition: computing an $ε$-performatively stable point is PPAD-complete -- and thus polynomial-time equivalent to Nash equilibria in general-sum games -- even when $ρ= 1 + O(ε)$. This intractability persists even in the ostensibly simple setting with a quadratic loss function and linear distribution shifts. One of our key technical contributions is to extend this PPAD-hardness result to general convex domains, which is of broader interest in the complexity of variational inequalities. Finally, we address the special case of strategic classification, showing that computing a strategic local optimum is PLS-hard.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。