On the Computational Complexity of Performative Prediction

ORID kkhVljGiMS · tags icml2026-repro paper-kkhVljGiMS

#StatusPageArtifactClaim excerpt
1VERIFIED 2/201-restated-computing-performatively-stable-pointartifactTheorem 1.2 (restated as Theorem 3.4) proves that computing an ε-performatively …
2VERIFIED 2/202-ppad-hardness-persists-simple-setting-lossartifactThis PPAD-hardness persists in the simple setting where the loss is quadratic, ℓ…
3VERIFIED 2/203-phase-transition-tractability-performatively-staartifactTheorem 3.5 shows a phase transition to tractability: when ρ ≤ 1 + O_ε(ε^4), an …
4VERIFIED 2/204-establishes-unconditional-information-theoreticartifactCorollary 3.7 establishes an unconditional information-theoretic lower bound: an…
5VERIFIED 2/205-extends-ppad-hardness-performative-stability-hypartifactTheorem 3.12 extends PPAD-hardness of performative stability from the hypercube …
6VERIFIED 2/206-special-case-strategic-classification-computingartifactFor the special case of strategic classification, Theorem 4.4 shows that computi…

Open logbook index · logbook.json