On the Computational Complexity of Performative Prediction

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 ($\rho < 1$), the complexity in the regime $\rho > 1$ was hitherto open. In this paper, we establish a sharp phase transition: computing an $\epsilon$-performatively stable point is PPAD-complete---and thus polynomial-time equivalent to Nash equilibria in general-sum games---even when $\rho = 1 + O(\epsilon)$. 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.

This paper studies settings where the environment responds to the prediction model, thereby changing the underlying data distribution. Prior work showed when such feedback effects are weak, simple retraining procedures converge efficiently. This work establishes that once these effects pass the threshold for efficient convergence, the problem immediately becomes computationally intractable: finding a stable point in this framework can be as hard as finding a Nash equilibrium in a general-sum game. This hardness result holds even in seemingly elementary settings, such as quadratic loss functions and linear distribution shifts.