On the Computational Complexity of Performative Prediction
This work addresses a foundational problem in machine learning by revealing inherent computational barriers in performative prediction, which is crucial for researchers and practitioners dealing with feedback loops in predictive systems.
The paper tackles the computational complexity of performative prediction, where model deployment shifts data distributions, and establishes that computing an ε-performatively stable point is PPAD-complete, even for weak performative effects, making it as hard as finding Nash equilibria.
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.