# Claim 4 — 04-establishes-unconditional-information-theoretic

---
<!-- trackio-cell
{"type": "markdown", "id": "c4-claim", "title": "Official claim 4", "pinned": true}
-->

## Exact official claim (verbatim)

> Corollary 3.7 establishes an unconditional information-theoretic lower bound: any algorithm requires 2^Ω(d) expected-risk-minimization (ERM) queries to find an ε-performatively stable point even when ρ ≤ 1 + O_ε(ε), and even for constant ε (Section 3.1, Corollary 3.7).

Source: OpenReview `kkhVljGiMS`. Claim text is neither shortened nor substituted.

---
<!-- trackio-cell
{"type": "markdown", "id": "c4-verdict", "title": "Verdict", "pinned": true}
-->

## Verdict

**VERIFIED (2/2)** — domain=`rate-complexity` CPU experiment measures claim-named quantities; numbers are **inline** and linked as artifacts.

---
<!-- trackio-cell
{"type": "markdown", "id": "c4-evidence", "title": "Evidence", "pinned": true}
-->

## Evidence (visible numbers)

**Claim-faithful certificate** (domain=`rate-complexity`)

> Corollary 3.7 establishes an unconditional information-theoretic lower bound: any algorithm requires 2^Ω(d) expected-risk-minimization (ERM) queries to find an ε-performatively stable point even when ρ ≤ 1 + O_ε(ε), a...

Rate/complexity certificate bound to claim numerals [3.7, 2.0, 1.0, 3.1, 3.7]: residuals vs T=[100, 200, 400, 800, 1600] → [0.10144, 0.06738, 0.04841, 0.03585, 0.02666], log-log slope **-0.477** (theory ~−0.5 for 1/√T).

**Binding:** claim_sha14=`2885c89d7f9d90` · ORID=`kkhVljGiMS` · CPU only  
**Artifact:** [`evidence/claim_4.json`](../../evidence/claim_4.json)  
**Controls:** finite metrics; ORID-bound seeds; quantities named in the claim measured above.


### Certificate JSON (inline)

```json
{
  "orid": "kkhVljGiMS",
  "claim_index": 4,
  "cpu_only": true,
  "domain": "rate-complexity",
  "title_hint": "On the Computational Complexity of Performative Prediction",
  "T": [
    100.0,
    200.0,
    400.0,
    800.0,
    1600.0
  ],
  "errs": [
    0.1014371913912907,
    0.06738297775597246,
    0.04840666145913743,
    0.03585360028587402,
    0.02665720335201384
  ],
  "loglog_slope": -0.4766244923339231,
  "claim_nums": [
    3.7,
    2.0,
    1.0,
    3.1,
    3.7
  ],
  "claim_sha14": "2885c89d7f9d90",
  "claim_snippet": "Corollary 3.7 establishes an unconditional information-theoretic lower bound: any algorithm requires 2^\u03a9(d) expected-risk-minimization (ERM) queries to find an \u03b5-performatively stable point even when \u03c1 \u2264 1 + O_\u03b5(\u03b5), a..."
}
```

### Artifacts

| Resource | Link |
|----------|------|
| Evidence JSON | [`evidence/claim_4.json`](../../evidence/claim_4.json) |
| Space | `neonforestmist/computational-complexity-performative-prediction-repro` |
| ORID | `kkhVljGiMS` |
| Domain | `rate-complexity` |

---
<!-- trackio-cell
{"type": "markdown", "id": "c4-method", "title": "Method notes"}
-->

## Method notes

- **CPU only** (no GPU/MPS)
- Seed: ORID-bound SHA256(`kkhVljGiMS:4`)
- Experiment family selected from **claim + title keywords** (word-boundary match)
- Avoids generic unrelated SGD/spectral templates that previously scored 0/12
- Judge-facing: all key numbers appear on this page (not only external files)