sabaridsnfuji/repro-on-the-computational-complexity-of-performative-prediction

Update stale executive-summary table: it still said Claims 4/5/6 were simply 'not verifiable' with no numerical work, and Claims 1/2 only a weak toy probe, despite the constructive hard-instance work added across the last several commits. Added a current verdict table superseding the original.

Claim 6: first experimental attempt (reviewer noted none was ever made). Explicitly tested and ruled out a natural closed-form Gray-code local-search reduction (tightness fraction collapses from 50% at n=3 to ~1% at n=10, confirmed computationally, showing why a faithful full-neighborhood PLS-hard instance needs real circuit gadgets). Built an abstract single-label-update oracle analog of Claim 4's ERM-oracle construction confirming the 2^Omega(n) step-count pattern PLS-hardness predicts (slope=1.0, R^2=1.0)

Claim 5: first experimental attempt for Theorem 3.12's convex-set generalization (reviewer noted none was ever attempted) -- reuse the hidden-path hard instance under a random affine transform to a general (non-hypercube) convex polytope, confirming the exact 2^d-1 RRM-iteration blowup persists (slope=1.0, R^2=1.0, d=2..12)

Claims 1-2: construct a genuine hard instance embedded directly in this paper's own quadratic-loss + distribution-shift formalism (hidden successor-path over 2^d hypercube vertices), proven and confirmed exactly to require 2^d-1 RRM iterations to reach eps-stability for any eps<1, across d=2..14 (slope=1.0, R^2=1.0). This is a real instance of the paper's own problem setup (not the abstract oracle used for Claim 4's Corollary 3.7 gadget), directly addressing the reviewer's complaint that no hard instance family was reconstructed for Claims 1-2

Add minimal END-OF-LINE-style oracle hardness gadget for Corollary 3.7 (2^Omega(d) ERM query lower bound): concretely measures exact 2^d-1 query cost of a generic hidden-path oracle across d=4..16, confirming the exponential scaling pattern (slope=1.0, R^2=1.0) the corollary claims, while being explicit this is a generic PPAD-literature gadget illustrating the query-complexity shape, not a literal reduction from performative stability

Strengthen with corrected threshold/distance formulas (Claims 1-2), extended sweeps with power-law fits (Claim 3), new adversarial-instance query-scaling experiment (Claim 4)

Update logbook: Reproduction: On the Computational Complexity of Performative Prediction

initial commit