PPAD-Complete: Performative Prediction erreicht kritischen Schwellenwert

In einer bahnbrechenden Veröffentlichung auf arXiv wird die bislang ungelöste Frage der Rechenkomplexität bei performativem Vorhersagen geklärt. Performative Prediction beschreibt das Phänomen, dass das Ausrollen eines prädiktiven Modells die zugrunde liegende Datenverteilung verändert. Für schwache performative Effekte (ρ < 1) sind die bekannten Retraining‑Dynamiken bereits linear konvergent, doch die Komplexität im regime ρ > 1 blieb lange Zeit ungeklärt.

Die Autoren zeigen einen scharfen Phasenübergang: Das Finden eines ε‑performativ stabilen Punktes ist PPAD‑vollständig. Das bedeutet, dass die Aufgabe im Wesentlichen gleichwertig zu Nash‑Equilibrien in allgemeinen Mehrparteien‑Spielen ist – ein klassisches Beispiel für ein NP‑schwieriges Problem, das in polynomieller Zeit nicht lösbar ist, sofern PPAD≠P. Interessanterweise gilt diese Inkompatibilität bereits bei ρ = 1 + O(ε).

Bemerkenswert ist, dass die Intransparenz auch in einem scheinbar einfachen Rahmen besteht: Quadratischer Verlust und lineare Verteilungsverschiebungen. Darüber hinaus erweitern die Autoren die PPAD‑Hardness‑Ergebnisse auf beliebige konvexe Domänen, was weitreichende Konsequenzen für die Komplexität von Variationsungleichungen hat.

Im speziellen Fall der strategischen Klassifikation wird zusätzlich gezeigt, dass die Berechnung eines strategischen lokalen Optimums PLS‑schwer ist – ein weiteres Indiz für die inhärente Rechenintensität dieser Problemklasse.