scripts/fill_logbook.py

"""Write the Trackio logbook pages for the reproduction.

page.md files carry JSON inside HTML comments, so they are emitted from Python
(never via an editor tool) to avoid a formatter mangling the cell metadata.
"""

import json
import os
import re

ROOT = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
PAGES = os.path.join(ROOT, ".trackio", "logbook", "pages")
BUCKET = "https://huggingface.co/buckets/SabaPivot/interp-agg-repro-artifacts"
SPACE = (
    "SabaPivot/repro-the-interplay-between-interpolation-and-aggregation-in-"
    "regression-optimal-sample-complexit"
)

SLUGS = {
    "exec": "executive-summary",
    "c1": "claim-1-claim-1-gamma-graph-dimension-definition",
    "c2": "claim-2-claim-2-omega-d-eps-for-proper-aggregation",
    "c3": "claim-3-claim-3-d-gamma-vs-oig-3-separation",
    "c4": "claim-4-claim-4-finite-interpolating-aggregation-fails",
    "c5": "claim-5-claim-5-median-of-three-o-d-n",
    "c6": "claim-6-claim-6-proper-learners-need-extra-ln-1-eps",
    "concl": "conclusion",
}

CELL_RE = re.compile(r"<!-- trackio-cell\n(\{.*?\})\n-->", re.S)


def existing_meta(slug):
    """Reuse the cell ids/timestamps the scaffold created."""
    path = os.path.join(PAGES, slug, "page.md")
    if not os.path.isfile(path):
        return []
    return [json.loads(m.group(1)) for m in CELL_RE.finditer(open(path).read())]


def write_page(slug, heading, cells):
    parts = [f"# {heading}\n"]
    for meta, body in cells:
        parts.append(
            "\n---\n<!-- trackio-cell\n"
            + json.dumps(meta)
            + "\n-->\n"
            + body.rstrip()
            + "\n"
        )
    path = os.path.join(PAGES, slug, "page.md")
    os.makedirs(os.path.dirname(path), exist_ok=True)
    with open(path, "w") as f:
        f.write("".join(parts))
    return path


# ---------------------------------------------------------------------------
# Executive summary
# ---------------------------------------------------------------------------
exec_meta = existing_meta(SLUGS["exec"])
summary_meta = exec_meta[0]
poster_meta = exec_meta[1]

SUMMARY = """**All six claims reproduce; verdict `verified` on every one.** Every construction in the
paper was rebuilt from its statement as an explicit finite hypothesis class, the gamma-graph
dimension (Definitions 3.1/3.2) and the gamma-OIG dimension (Definition 3.9) were computed
**exhaustively** rather than quoted, and each aggregation rule was checked against Definition 3.4 /
3.7 before being used. The Omega(d_gamma/eps) barrier of Theorem 3.5 holds in 30/30 grid cells
(min margin 1.77x) and Theorem 3.8's in 64/64 cells (min margin 1.96x) with the empirical threshold
collapsing onto `n* = 0.339 d_gamma/eps` at a 1.2% coefficient of variation; Theorem 3.10's failure
mode holds in 27/27 cells with `E[L] >= 0.951` and beats random guessing in the wrong direction;
median-of-three fits `L = 0.347 d_gamma/n` with exponents `-0.999` in n and `+1.000` in d_gamma
(both R^2 = 1.000); and the extra factor Theorem 3.12 predicts for proper learners is measured
directly as `n*(eps) eps / d_gamma = 0.77 ln(1/eps) - 1.17`, R^2 = 0.9988. No contradiction was
found anywhere in the tested envelope, and every stated assumption was probed from both sides
(dropping properness, dropping the interpolating property, allowing infinite aggregation, and
d_gamma = 1 each make the corresponding bound evaporate exactly as the proofs require).

## Scope & cost

| Item | Value |
| --- | --- |
| Scope | 6/6 claims reproduced independently: exhaustive dimension computation + seeded Monte-Carlo of every aggregation rule on the paper's own hard distributions |
| GPU / compute | none - CPU only (numpy/scipy/matplotlib), single process |
| Hardware | 1 CPU core of a shared x86-64 box; no GPU, no API key |
| Wall time | ~12 min total for all six claim scripts + figures + poster |
| Cost | $0 |
| Feasibility | high - the paper is pure learning theory; every construction is finitely presentable and every bound is a closed form that can be evaluated exactly |
| Official code | none released; searched the paper text, arXiv page and OpenReview - no GitHub or project page is referenced |
"""

poster_body = open(os.path.join(ROOT, "poster", "poster_embed.html")).read()
POSTER_CELL = "````html\n" + poster_body.rstrip() + "\n````"

write_page(
    SLUGS["exec"],
    "Executive summary",
    [(summary_meta, SUMMARY), (poster_meta, POSTER_CELL)],
)

# ---------------------------------------------------------------------------
# Claim pages
# ---------------------------------------------------------------------------
CLAIMS = {}

CLAIMS["c1"] = (
    "Claim 1: gamma-graph dimension (Definitions 3.1 / 3.2)",
    """## Claim (verbatim)

> The paper defines the gamma-graph dimension d_γ (Definition 3.2) via a gamma-shattering condition
> (Definition 3.1) and uses it to characterize the sample complexity of aggregation-based regression
> procedures.

## Verdict: **verified**

## Independent method

Definitions 3.1 and 3.2 were transcribed into executable code and evaluated **exhaustively** - every
witness `h in H`, every subset of the finite domain, every one of the `2^d` sign patterns. Sequences
with repeated points cannot help for `d >= 2`, so subsets suffice. gamma-graph shattering is downward
closed in the point set (drop a coordinate from every `b`), so the search runs level-wise and is
exact, not sampled. Nothing here is read off the paper: the answer for each class is *computed*.

Script: `scripts/claim1_graph_dimension.py` (core primitives in `scripts/core.py`:
`_relation_matrix`, `is_gamma_graph_shattered`, `gamma_graph_dim`). Seed `numpy.default_rng(20260725)`,
`gamma = 0.1`.

## Scale and results

**25 / 25 exhaustive checks match the analytic value.**

| class | \\|H\\| | computed d_gamma | expected |
| --- | --- | --- | --- |
| full boolean cube on 2/3/4/5 points | 4 / 8 / 16 / 32 | 2 / 3 / 4 / 5 | 2 / 3 / 4 / 5 |
| singleton class `{h}` | 1 | 0 | 0 |
| thresholds on 8 points | 9 | 1 | 1 |
| Thm 3.5 hard class, target d = 2..5 | 4..32 | 2 / 3 / 4 / 5 | 2 / 3 / 4 / 5 |
| Thm 3.8 class, `ku=10, d=5` | 252 | 5 | 5 |
| Thm 3.12 full class, `d=4` | 57 | 4 | 4 |
| Thm 3.10 block `k=16` | 1820 | 4 | `sqrt(k) = 4` |

**gamma-dependence.** On `{0, 0.3}^4`: `d_0.2 = 4` but `d_0.5 = 0` - the measure genuinely tracks
gamma, it is not a relabelled VC/graph dimension.

**Not a stand-in for cardinality.** `d_gamma = 2` occurs at `|H| = 15` and at `|H| = 28`;
`|H| = 35` occurs with `d_gamma = 3`. `d_gamma` is decoupled from `|H|` and `log|H|`.

**Unboundedness.** The Theorem 3.10 blocks give `d_gamma = sqrt(k)` for `k = 4, 9, 16`, so the union
over blocks has infinite gamma-graph dimension while its gamma-OIG dimension stays constant. That is
exactly the regime Claim 4 needs.

**Characterisation.** Running median-of-three interpolator aggregation with a worst-case interpolator
and binary-searching the sample size needed for expected cutoff loss 0.05 gives

| d_gamma | 2 | 4 | 8 | 16 | 32 | 64 |
| --- | --- | --- | --- | --- | --- | --- |
| n(eps=0.05) | 3 | 9 | 23 | 49 | 101 | 205 |
| n / d_gamma | 1.50 | 2.25 | 2.88 | 3.06 | 3.16 | 3.20 |

`log n(eps)` regressed on `log d_gamma` (d >= 8) gives slope **1.0511** - linear in d_gamma, as the
measure claims.

## Boundary / assumption audit

* **Finite-universe truncation.** The paper's classes live over `N`; we truncate to `[ku]`. The
  all-far pattern needs a size-`d` set disjoint from `A`, so truncation caps the dimension at
  `min(d, ku - d)`. We verify that formula explicitly (e.g. `ku=7, d=4` gives 3, `ku=9, d=5` gives 4)
  rather than hiding the truncated cases.
* **Single-block Thm 3.12 class.** Dropping the extra blocks costs exactly one dimension
  (`d - 1` instead of `d`), confirming that the split input space is load bearing in that proof.

## Limitation

Exhaustive enumeration is only possible on finite truncations (`|H| <= 1820`, `|X| <= 16` here); the
`d_gamma -> infinity` statement is verified as a growth law in `k`, not for the infinite class itself.

## Artifacts

* `scripts/claim1_graph_dimension.py`, `scripts/core.py`
* `outputs/claim1_graph_dimension.json`
""",
)

CLAIMS["c2"] = (
    "Claim 2: Omega(d_gamma/eps) for interpolator-based aggregation (Theorem 3.5)",
    """## Claim (verbatim)

> Any interpolator-based aggregation using proper aggregation rules requires sample complexity
> Ω(d_γ/ε) to reach expected cutoff loss ε (Theorem 3.5).

## Verdict: **verified**

## Independent method

The hard instance was rebuilt from the proof sketch, not copied: a gamma-graph-shattered set of size
`d_gamma` with an all-zero witness (shattering asserted by the Definition-3.1 checker), Ehrenfeucht
masses `1 - 2eps` on the heavy point and `2eps/(d_gamma - 1)` on each light point, all labelled by the
witness. The worst-case interpolator returns the member of `H` that agrees with the witness on every
observed point and is gamma-far from it on every unobserved point - possible exactly because the set
is shattered.

Every sub-sequence `S_j` of `S` inherits the misses of `S`, so each `h_j = A(S_j)` is gamma-far on
every point missing from `S`; a proper rule (Definition 3.4) must output one of those values.
The Monte-Carlo therefore sweeps **five sub-sequence constructions** (single interpolator, bagging
with m = 3 / 5 / 101, disjoint 3-split, leave-one-point-out) crossed with **seven rules** (min, max,
median, two order statistics, an x-dependent adversarially-best proper rule, and two controls).

Script: `scripts/claim2_thm35_lower_bound.py`. Seeds `default_rng(20260725 + k)`, 4000 Monte-Carlo
trials per cell, `gamma = 0.1`.

## Scale and results

**30 / 30 grid cells** over `d_gamma in {2,4,8,16,32,64}` and `eps in {0.01, 0.02, 0.05, 0.1, 0.2}`
satisfy `E[L] > eps` at `n = floor(d_gamma/(32 eps))`. **Minimum margin: `E[L]/eps = 1.772`.**

Monte-Carlo at `d_gamma = 8`, `eps = 0.05`, `n = 5`, 4000 trials (closed-form reference 0.09307):

| sub-sequences | rule | E[L] | E[L]/eps |
| --- | --- | --- | --- |
| m = 1 (single interpolator) | median | 0.09315 | 1.86 |
| bagging m = 101 | median | 0.09316 | 1.86 |
| bagging m = 101 | **adversarially best proper rule** | 0.09315 | 1.86 |
| disjoint 3-split | min / order-stat 0.25 | 0.09315 | 1.86 |
| leave-one-point-out | median | 0.93632 | 18.73 |
| any | *control:* const-0 (not proper) | 0.00000 | 0.00 |

The strongest possible proper rule - at every `x`, pick whichever input value is closest to the true
label - does no better than the plain median, which is the structural point of the theorem.

## Boundary / assumption audit

* **Properness is load bearing.** The const-0 rule is neither proper nor interpolating and drives the
  loss to exactly 0. Our Definition-3.4 checker also reproduces the paper's own caveat: `median` is
  proper only for **odd** arity (over random arities including even m it fails; restricted to odd m
  it passes), while `mean` is never proper.
* **The bound stops biting where it should.** Sweeping `n` upward at `d_gamma = 8, eps = 0.05`:
  `E[L] = 0.0931 / 0.0866 / 0.0750 / 0.0562 / 0.0316 / 0.0100` at 1x / 2x / 4x / 8x / 16x / 32x the
  threshold. The bound first fails at 16x - it is a threshold statement, not an asymptote.
* **`d_gamma >= 2` is necessary.** At `d_gamma = 1` the construction degenerates (no light points) and
  the loss is 0.
* **Sensitivity to the free mass constant `a`.** With light mass `a * eps`: `a = 0.5` gives
  `E[L]/eps = 0.49` and `a = 1` gives 0.97 (bound fails), `a = 2` gives 1.86 and `a = 16` gives 10.03.
  The theorem's "there exists a distribution" is doing real work; we report the whole curve, not just
  the favourable point.

## Limitation

The lower bound quantifies over *all* interpolator-based aggregation algorithms; a simulation can only
sample a family of them. We mitigate this by including the pointwise-optimal proper rule, which
dominates every other proper rule by construction, and by cross-checking against the closed form
`sum_i p_i (1 - p_i)^n` (agreement to three digits).

## Artifacts

* `scripts/claim2_thm35_lower_bound.py`, `scripts/core.py`
* `outputs/claim2_thm35.json`, `figs/fig3_lower_bounds.png` (left panel)
""",
)

CLAIMS["c3"] = (
    "Claim 3: d_gamma vs gamma-OIG-3 separation (Theorem 3.8)",
    """## Claim (verbatim)

> There exist hypothesis classes with γ-graph dimension d_γ and γ-OIG dimension at most 3 for which
> finite interpolating-aggregation algorithms still require sample complexity Ω(d_γ/ε), separating
> them from general learners that achieve Õ(1/ε) (Theorem 3.8).

## Verdict: **verified**

## Independent method

The Cantor-style class of the proof overview was built explicitly:
`H = {h_A : A subset of N, |A| = d}` with `h_A = 0` on `A` and a unique `gamma_A in (gamma, 1]`
elsewhere. Both dimensions are then **computed**, not quoted:

* `d_gamma` exhaustively from Definitions 3.1/3.2;
* the gamma-OIG dimension exhaustively from Definition 3.9 - for every point set of size `k` we build
  the induced one-inclusion hypergraph, then take the **minimum over all orientations** of the maximum
  out-degree by brute force (plus every vertex-induced subgraph on small instances), and count `k`
  only when that minimum exceeds `k/3`.

For the lower bound we simulate the paper's hard family (`A_1 = 1`, the rest drawn without
replacement from `{2..ku}`, mass `1 - 2eps` on `A_1` and `2eps/(d-1)` on the others, all labelled 0)
against a **best-effort** finite aggregation algorithm: it puts every observed point into the zero
set of one of its `m` hypotheses and spends the remaining `m*d - |obs|` zero-slots guessing. Anything
outside the union of zero sets is mispredicted by every interpolating rule - each of mean / median /
midrange / min / max was first verified *interpolating* against Definition 3.7, and each was checked
to still err when all its inputs lie in `(gamma, 1]`.

Script: `scripts/claim3_thm38_separation.py`. 3000 trials/cell, `ku = 1000 * d * m`.

## Scale and results

**Dimensions (exhaustive).**

| ku | d | \\|H\\| | d_gamma (expected) | gamma-OIG dim | <= 3? |
| --- | --- | --- | --- | --- | --- |
| 5 | 2 | 10 | 2 (2) | 2 | yes |
| 6 | 3 | 20 | 3 (3) | 2 | yes |
| 8 | 4 | 70 | 4 (4) | 2 | yes |

**Lower bound: 64 / 64 grid cells** over `d_gamma in {32,64,128,256}`, `eps in {0.01,0.02,0.05,0.1}`,
`m in {1,3,10,100}` satisfy `E[L] > eps` at `n = floor(d_gamma/(128 eps))`, at 2 sigma.
**Minimum margin: `E[L]/eps = 1.965`.** Representative row (`eps = 0.01`, `m = 100`):
`d = 32 -> 0.01965`, `64 -> 0.01966`, `128 -> 0.01967`, `256 -> 0.01968` - flat at `1.97 eps`,
independent of `m` once `ku >> d*m`.

**Empirical threshold.** Binary-searching the smallest `n` at which the loss falls to `eps`:

| d_gamma \\ eps | 0.05 | 0.02 | 0.01 |
| --- | --- | --- | --- |
| 32 | 214 | 529 | 1073 |
| 64 | 435 | 1086 | 2185 |
| 128 | 879 | 2192 | 4383 |

`n* / (d_gamma/eps)` has mean **0.3388** and coefficient of variation **1.2%** across all nine cells,
i.e. `n* = Theta(d_gamma/eps)` with a genuinely constant constant.

**The separation.** An explicit *general* improper learner on the same class - if any non-zero label
appears it reveals the unique `gamma_A` and identifies the target exactly, otherwise predict the
constant-0 function - has worst-case loss `<= 1/(e n)`, independent of `d_gamma`. At
`n = d_gamma/(128 eps)`, `eps = 0.01`:

| d_gamma | 32 | 64 | 128 | 256 |
| --- | --- | --- | --- | --- |
| finite aggregation E[L] | 0.01965 | 0.01966 | 0.01967 | 0.01968 |
| general learner E[L] | 0.01434 | 0.00705 | 0.00303 | 0.00179 |
| **gap** | 1.4x | 2.8x | 6.5x | **11.0x** |

The gap grows linearly in `d_gamma`, i.e. it is arbitrarily large - which is exactly the claim. Note
the constant-0 predictor is not a member of `H` and is not reachable by any interpolating aggregation
of members of `H`, so this learner is genuinely outside the class the lower bound covers.

## Boundary / assumption audit

* **`ku >> d*m` is the real hypothesis, not `m` alone.** Holding `ku = 20000` fixed at `d = 128`,
  `eps = 0.01` and raising `m`: `E[L]/eps = 1.96 / 1.85 / 1.04 / 0.29 / 0.003` for
  `m = 1 / 10 / 100 / 300 / 1000`. The bound breaks precisely when `d*m/ku` exceeds 1, as the proof
  requires.
* Every rule used was verified interpolating first, so a failure could not be blamed on a rule that
  quietly violated Definition 3.7.

## Limitation

We compute `d_gamma = min(d, ku - d)` on the truncated universe, so `ku >= 2d` is required to realise
the paper's value; this is a truncation artefact, verified explicitly (Claim 1). Our exhaustive OIG
scan reaches `k <= 5` and returns 2 on these truncations - consistent with the paper's "at most 3",
but we did not exhibit a size-3 witness, so we confirm the upper bound and the constancy, not the
exact value 3.

## Artifacts

* `scripts/claim3_thm38_separation.py`, `scripts/core.py`
* `outputs/claim3_thm38.json`, `figs/fig4_separation.png`, `figs/fig3_lower_bounds.png` (middle panel)
""",
)

CLAIMS["c4"] = (
    "Claim 4: finite interpolating aggregation cannot learn (Theorem 3.10)",
    """## Claim (verbatim)

> For some hypothesis classes with constant γ-OIG dimension, no finite interpolating aggregation rule
> can achieve non-trivial cutoff loss regardless of sample size, requiring either infinite aggregation
> or non-interpolating rules (Theorem 3.10).

## Verdict: **verified**

## Independent method

The split-space class of the proof overview was built explicitly:
`X = union over k = i^2 of {(k,x) : x <= k}`, `H = {h_{k,A} : A subset [k], |A| = sqrt(k)}` with
`h_{k,A} = 0` on `{(k,x) : x in A}` and a unique `gamma_{k,A} in (gamma, 1]` on every other point of
`X` (including every other block).

* The **gamma-OIG dimension** is computed exhaustively from Definition 3.9 on multi-block truncations
  (minimum over all orientations of the maximum out-degree, plus vertex-induced subgraphs).
* The **gamma-graph dimension** is computed exhaustively per block and grows as `sqrt(k)`.
* The **failure** is simulated: `A` uniform of size `sqrt(ku)`, `D_A` uniform on
  `{(ku,i) : i in A}` with all labels 0, and a best-effort finite aggregation algorithm that zeroes
  every observed point and spends its remaining `m*sqrt(ku)` zero-slots guessing. `ku` is chosen as
  the proof requires: `sqrt(ku) >= (4/eps) max(n', m)`, which is both `ku = omega(n'^2)` and
  `ku >> (m/eps)^2`.

Script: `scripts/claim4_thm310_failure.py`. 400 trials/cell, seeds `default_rng(20260725 + k)`.

## Scale and results

**Dimensions.** `d_gamma = sqrt(k)` for `k = 4, 9, 16` (computed 2, 3, 4 on classes of 6, 84 and 1820
hypotheses) so the union over blocks has **infinite** gamma-graph dimension, while the exhaustive
gamma-OIG dimension is **2** on every truncation tested (blocks `[1,4]`, `[4,9]`, `[1,4,9]`) - constant
and `<= 3`.

**27 / 27 grid cells** over `eps in {0.02, 0.05, 0.1}`, `n' in {10, 100, 1000}`, `m in {1, 10, 100}`
satisfy `E[L] >= 1 - eps`. **Minimum observed loss over the whole grid: 0.95100.**

**Sample size is irrelevant** (ku re-chosen per `n'`, as the theorem allows):

| n' | 1 | 10 | 100 | 1000 | 10000 |
| --- | --- | --- | --- | --- | --- |
| ku | 4e6 | 4e6 | 4e8 | 4e10 | 4e12 |
| E[L] | 0.99446 | 0.99004 | 0.99452 | 0.99496 | 0.99501 |

**Worse than trivial.** With `gamma = 0.1`:

| predictor | E[L^gamma_D] | theory |
| --- | --- | --- |
| finite interpolating aggregation, `n' = 10^4` | **0.99501** | `>= 1 - eps` |
| random guess, uniform on [0,1] | 0.90024 | `1 - gamma = 0.9` |
| random guess on the gamma-net | 0.83311 | `1 - Theta(gamma)` |

At `eps = 0.02 < gamma = 0.1`, finite interpolating aggregation is strictly worse than random
guessing - exactly the "strictly worse than random guessing for eps = o(gamma)" statement.

## Boundary / assumption audit

The theorem names two escapes; both are reproduced quantitatively.

* **Infinite aggregation.** Holding `ku` fixed and growing `m`, the loss walks down monotonically:
  `0.99995` (m = 1), `0.99501` (m = 100), `0.95123` (m = 1000), `0.90484` (m = 0.1 sqrt(ku)),
  `0.36788` (m = sqrt(ku)), `0.00005` (m = 10 sqrt(ku)). The barrier is `m << sqrt(ku)`, not `m`
  being finite per se.
* **Non-interpolating rules.** The constant-0 predictor may leave the range of its inputs and scores
  exactly `0.00000`.

## Limitation

`ku` reaches `4e12`, so the support is handled combinatorially (distinct-coupon count plus a binomial
for the guess coverage) rather than by materialising the domain; the class itself is materialised and
exhaustively analysed only on the small blocks `k <= 16`. As in Claim 3 the exhaustive OIG scan
returns 2 rather than the paper's stated 3 - within "constant" and within "at most 3", but we did not
exhibit a size-3 witness.

## Artifacts

* `scripts/claim4_thm310_failure.py`, `scripts/core.py`
* `outputs/claim4_thm310.json`, `figs/fig3_lower_bounds.png` (right panel)
""",
)

CLAIMS["c5"] = (
    "Claim 5: median-of-three achieves O(d_gamma/n) (Theorem 3.11)",
    """## Claim (verbatim)

> Taking the median of three independently trained interpolators achieves expected cutoff loss
> O(d_γ/n), yielding optimal sample complexity O(d_γ/ε) that matches the lower bound (Theorem 3.11).

## Verdict: **verified**

## Independent method

Four independent strands, none of which quotes the proof:

1. **The structural lemma, re-derived executably.** The proof's union bound rests on "the median of
   three is gamma-far from `y` only if at least two of them are". We test that over 4,000,000 random
   triples plus an exhaustive `41^4` grid of `(z_1, z_2, z_3, y)`: **0 violations**.
2. **Worst case over distributions.** On the Theorem 3.5 hard family with a worst-case interpolator,
   the error probability of `A(S)` at a point of mass `p` is exactly `(1-p)^n`, so
   `E[L] = sum_i p_i (3 q_i^2 - 2 q_i^3)` with `q_i = (1-p_i)^n`. We **maximise** this over mass
   profiles - i.e. we compute the worst case the theorem must dominate, not a favourable one.
3. **Fitted scaling exponents** in `n` and in `d_gamma`, and the sample complexity `n(eps)`.
4. **Full Monte-Carlo** with real independent samples, real interpolators (materialised from `H` and
   looked up by bit pattern for `d <= 12`) and a real pointwise median.

Script: `scripts/claim5_thm311_median3.py`. Seeds `default_rng(20260725 + n)`, 4000 trials per MC cell.

## Scale and results

**The constant is bounded.** Over `d_gamma in {2,...,128}` and `n/d_gamma` from 1 to 1000
(56 cells), `n * E[L] / d_gamma` stays in **[0.2970, 0.3468]**. A bounded constant is precisely
`L = O(d_gamma/n)` with **no hidden log n**.

| d_gamma = 64 | n = 64 | 320 | 3200 | 64000 |
| --- | --- | --- | --- | --- |
| worst-case E[L] | 3.450e-1 | 6.928e-2 | 6.935e-3 | 3.468e-4 |
| n E[L] / d_gamma | 0.3450 | 0.3464 | 0.3467 | 0.3468 |

**Fitted exponents.**

| fit | slope | predicted | R^2 |
| --- | --- | --- | --- |
| `d log L / d log n` at d = 8 / 32 / 128 | -0.9954 / -0.9988 / **-0.9997** | -1 | 1.00000 |
| `d log L / d log d_gamma` at fixed n = 5e3 / 2e4 / 1e5 | **+1.0000** (all three) | +1 | 1.00000 |

**Sample complexity.** `n(eps) = C d_gamma/eps` with `C` measured at **0.3473**, coefficient of
variation **0.31%** across `d_gamma in {8,32,128}` x `eps in {0.005..0.1}`. This matches the
`Omega(d_gamma/eps)` lower bounds of Claims 2 and 3 up to a constant, which is the optimality
statement.

**Monte-Carlo cross-check** (real sampling, real median):

| d_gamma | n | analytic | Monte-Carlo (+/- 2 se) | rel. err |
| --- | --- | --- | --- | --- |
| 8 | 40 | 0.068775 | 0.068760 +/- 0.000712 | 0.02% |
| 12 | 120 | 0.034580 | 0.034519 +/- 0.000304 | 0.18% |
| 32 | 160 | 0.069209 | 0.069498 +/- 0.000363 | 0.42% |
| 128 | 640 | 0.069318 | 0.069216 +/- 0.000182 | 0.15% |

Maximum relative error 0.42%.

## Boundary / assumption audit

* **`d_gamma` finite is required.** Running median-of-three on the Theorem 3.10 class (infinite
  gamma-graph dimension, `ku = 4e6`, `n = 500`) gives `E[L] = 0.87365` - the `O(d_gamma/n)` bound is
  vacuous there, exactly as it must be. This is the sharpest available check that the bound really
  depends on `d_gamma` and not on some other property of the construction.
* **Comparison with a single interpolator.** On its own worst-case profile a single interpolator gets
  `3.676e-3` where median-of-three gets `3.466e-3` at `n = 100 d_gamma`: on *this* family the two rates
  differ only by a constant (1.06x). The paper's strict separation is against **proper learners**
  (Claim 6), and that is where we measure it.

## Limitation

The worst-case-over-distributions optimisation is restricted to the uniform-on-`d`-points profile
family (plus a free heavy point), searched over 4000 log-spaced masses. That family contains the proof's
own hard instance and yields the tight constant, but it is not a search over all realizable
distributions.

## Artifacts

* `scripts/claim5_thm311_median3.py`, `scripts/core.py`
* `outputs/claim5_thm311.json`, `figs/fig1_median3_rate.png`
""",
)

CLAIMS["c6"] = (
    "Claim 6: proper learners need an extra ln(1/eps) (Theorem 3.12)",
    """## Claim (verbatim)

> Proper learners require sample complexity Ω((d_γ/ε)ln(1/ε)), strictly worse than the O(d_γ/ε)
> achieved by median-of-three aggregation, demonstrating aggregation's superiority over proper
> learning (Theorem 3.12).

## Verdict: **verified**

## Independent method

The split-space class of the proof overview was built and its gamma-graph dimension **computed**
exhaustively (`d = 2, 3, 4` on classes of 5 / 16 / 57 hypotheses over 5 / 8 / 11 points - all exactly
`d`). The hard instance follows the proof: `ku = Theta(d/eps)`, `A subset [ku]` with
`|A| = ku - d + 1` drawn uniformly, `D_A` uniform on `{(ku,i) : i in A}` with all labels 0,
realizable by `h_{ku, A^c}`.

The key step is re-derived rather than assumed: conditioned on the sample, the unobserved points are
**exchangeable**, so a proper learner must place its `d - 1` gamma-far points blindly in the
unobserved set `U`, giving `E[|A' ∩ A|] = (d-1) m / (m + d - 1)` where `m` is the number of unobserved
`A`-points. We verify the exchangeability empirically by running five different proper-learner
strategies and comparing.

Script: `scripts/claim6_thm312_proper.py`. Seeds `default_rng(20260725 + k)`, 800-1500 trials per
Monte-Carlo cell.

## Scale and results

**Any proper learner is forced.** At `d = 16`, `eps = 0.001`, `ku = 8000`, `n = 874`:

| strategy | random | lowest | highest | spread | middle | closed form |
| --- | --- | --- | --- | --- | --- | --- |
| E[L] | 0.001874 | 0.001874 | 0.001875 | 0.001875 | 0.001875 | 0.001875 |

Spread across strategies **0.05%**; analytic vs Monte-Carlo **0.01%**. The forcing is a property of
the instance, not an artefact of picking one adversarial learner.

**The theorem's inequality: 25 / 25 cells** over `d_gamma in {4,8,16,32,64}` and
`eps in {0.0002, 0.0005, 0.001, 0.002, 0.005}` (all below the theorem's `1/(64e) = 0.005746`) satisfy
`E[L] >= 4 eps / 3` at `n = floor((d/(32 eps)) ln(1/(64 e eps)))`. **Minimum margin
`E[L]/(4eps/3) = 2.248`.** Monte-Carlo spot checks agree with the closed form to `<= 0.1%`.

**The ln(1/eps) factor, measured.** Binary-searching the smallest `n` at which the *best* proper
learner reaches loss `eps` against the worst `ku` (searched over 260 values of `ku/n`):

| eps (d = 32) | 0.05 | 0.01 | 0.002 | 0.0005 | 0.0002 |
| --- | --- | --- | --- | --- | --- |
| n* | 784 | 7486 | 57191 | 300588 | 872739 |
| n* eps / d_gamma | 1.225 | 2.339 | 3.574 | 4.697 | **5.455** |

Regressing `n* eps / d_gamma` on `ln(1/eps)`:

| d_gamma | slope | intercept | R^2 |
| --- | --- | --- | --- |
| 8 | 0.6954 | -1.0548 | 0.99876 |
| 32 | **0.7697** | -1.1661 | 0.99878 |
| 128 | 0.7883 | -1.1938 | 0.99877 |

A constant model - which is what `O(d_gamma/eps)` would predict - is refused: the ratio moves by a
factor of **4.45** over the tested range, while median-of-three's identically-measured ratio is flat
at `0.347` with a 0.31% coefficient of variation (Claim 5).

**Aggregation beats proper learning on the *same* instance**, at identical `(d_gamma, eps, ku, n)`:

| d_gamma | eps | n | proper E[L] | median-of-3 E[L] | ratio |
| --- | --- | --- | --- | --- | --- |
| 8 | 0.005 | 6 | 0.017495 | 0.000878 | 19.9x |
| 16 | 0.002 | 263 | 0.007492 | 0.000147 | 50.8x |
| 32 | 0.001 | 1748 | 0.003871 | 0.000043 | **90.7x** |

The advantage grows as `eps` shrinks, which is the signature of the extra `ln(1/eps)`. Note the
median-of-three predictor is not a member of `H`, so it is improper - it is exactly the "aggregation"
side of the comparison.

## Boundary / assumption audit

* **`eps < 1/(64e)` is necessary for the statement to be non-vacuous.** At `eps = 0.01` the theorem's
  own sample bound `(d/(32 eps)) ln(1/(64 e eps))` is *negative*; we restrict the grid to
  `eps < 0.005746` and say so rather than silently clamping.
* **The adversary's `ku` matters.** `ku = Theta(d/eps)` with the best constant found at `0.25 d/eps`
  across the grid; using a much larger `ku` weakens the bound, consistent with the proof's careful
  choice.

## Limitation

The "for any proper learning algorithm" quantifier is discharged by the exchangeability argument plus
five concrete strategies, not by enumerating all learners. A learner that outputs a hypothesis from a
*different* block is strictly worse (loss 1), so the argument covers the only non-dominated family.

## Artifacts

* `scripts/claim6_thm312_proper.py`, `scripts/core.py`
* `outputs/claim6_thm312.json`, `figs/fig2_proper_log_factor.png`
""",
)

for key in ("c1", "c2", "c3", "c4", "c5", "c6"):
    slug = SLUGS[key]
    heading, body = CLAIMS[key]
    metas = existing_meta(slug)
    meta = metas[0] if metas else {"type": "markdown"}
    meta["title"] = heading
    write_page(slug, heading, [(meta, body)])

# ---------------------------------------------------------------------------
# Conclusion
# ---------------------------------------------------------------------------
CONCL_ARTIFACT_META = {
    "type": "artifact",
    "title": "Reproduction bundle",
    "artifact_type": "dataset",
}
CONCL_MD_META = {"type": "markdown", "title": "Download & rerun"}
CONCL_FINDINGS_META = {"type": "markdown", "title": "Findings"}

FINDINGS = """## Outcome

| # | Claim (theorem) | Verdict | Key number |
| --- | --- | --- | --- |
| 1 | Def 3.1 / 3.2 - d_gamma characterises aggregation | **verified** | 25/25 exhaustive checks; `log n(eps)` vs `log d_gamma` slope **1.051** |
| 2 | Thm 3.5 - proper aggregation needs `Omega(d_gamma/eps)` | **verified** | 30/30 cells, min `E[L]/eps = 1.772` |
| 3 | Thm 3.8 - OIG `<= 3` yet still `Omega(d_gamma/eps)` | **verified** | 64/64 cells; `n* = 0.339 d_gamma/eps`, CV **1.2%**; gap to a general learner grows 1.4x -> **11.0x** |
| 4 | Thm 3.10 - finite interpolating aggregation fails | **verified** | 27/27 cells, min `E[L] = 0.951` vs 0.900 for random guessing |
| 5 | Thm 3.11 - median-of-three is `O(d_gamma/n)` | **verified** | `n E[L]/d_gamma <= 0.3468`; exponents **-0.999** in n, **+1.000** in d_gamma |
| 6 | Thm 3.12 - proper learners pay `ln(1/eps)` | **verified** | `n* eps/d_gamma = 0.77 ln(1/eps) - 1.17`, R^2 = **0.9988** |

**Six verified, none falsified, none toy, none inconclusive.**

## What would have falsified each claim

Every claim was implemented so that a contradiction would surface as a number, not as a judgement
call: a computed `d_gamma` different from the analytic value; a `(d_gamma, eps, m, rule)` cell with
`E[L] <= eps` at the theorem's sample size; a finite interpolating aggregation beating `1 - eps`; a
fitted `n`-exponent away from `-1` or a growing `n E[L]/d_gamma`; a flat `n* eps/d_gamma` for proper
learners. None occurred.

## Honest deviations and limitations

* **Finite truncation.** The paper's classes live over `N`. Truncating the universe to `[ku]` caps the
  gamma-graph dimension at `min(d, ku - d)`; we verify that formula explicitly and use `ku >= 2d`
  wherever the paper's value is intended.
* **gamma-OIG dimension.** Our exhaustive Definition-3.9 computation (minimum over orientations of the
  maximum out-degree, plus vertex-induced subgraphs, `k <= 5`) returns **2**, not 3, on the finite
  truncations of the Theorem 3.8 and 3.10 classes. This is consistent with Theorem 3.8's "at most 3"
  and with Theorem 3.10's constancy requirement, but we did not exhibit a size-3 witness, so the exact
  value 3 stated in Theorem 3.10 is confirmed only as an upper bound here.
* **Quantifiers.** Lower bounds quantify over *all* algorithms of a class; simulation samples a family.
  We mitigate by always including the pointwise-optimal member (the adversarially-best proper rule in
  Claim 2, the cover-then-guess aggregator in Claims 3-4, the exchangeability argument in Claim 6).
* **No official code exists.** The paper text, arXiv page and OpenReview entry reference no GitHub
  repository or project page; everything here is written from the statements of the definitions and
  the proof overviews.

## Sources

* Paper: [arXiv 2605.29819](https://arxiv.org/abs/2605.29819) - Hogsgaard, Larsen, Zou (Aarhus / Oxford)
* [OpenReview qXlovWytwg](https://openreview.net/forum?id=qXlovWytwg)
* Background: Attias, Hanneke, Kalavasis, Karbasi, Velegkas (2023), realizable regression &
  gamma-OIG dimension; Aden-Ali et al. (2024), majority-of-three for binary classification.
"""

RERUN = f"""## Reproduction bundle & rerun

Bundle: **[`SabaPivot/interp-agg-repro-artifacts`]({BUCKET})** (Hugging Face Bucket). It contains
`scripts/` (the six claim scripts plus `core.py`, `make_figures.py`, `fill_logbook.py`), `outputs/`
(one JSON per claim plus captured stdout), `figs/` (four figures) and `poster/`
(`poster.html`, `poster_preview.pdf`, `poster_preview.png`, `poster_embed.html`, `GATE_REPORT.json`).

```bash
pip install numpy scipy matplotlib
python scripts/claim1_graph_dimension.py     # exhaustive d_gamma (Def 3.1/3.2)      ~6 s
python scripts/claim2_thm35_lower_bound.py   # Thm 3.5 lower bound                   ~13 s
python scripts/claim3_thm38_separation.py    # Thm 3.8 separation + OIG dimension    ~4 min
python scripts/claim4_thm310_failure.py      # Thm 3.10 total failure                ~40 s
python scripts/claim5_thm311_median3.py      # Thm 3.11 median-of-three rate         ~3 min
python scripts/claim6_thm312_proper.py       # Thm 3.12 proper-learner ln(1/eps)     ~3 min
python scripts/make_figures.py               # the four figures
```

Everything is CPU-only and deterministic given the seeds printed in each script
(`numpy.random.default_rng(20260725 + offset)`); total wall clock is about 12 minutes on one core.
Poster gates: `python posterly/tools/run_gates.py poster/poster.html` (PASS) then
`python posterly/tools/render_preview.py poster/poster.html`.

Space: [`{SPACE}`](https://huggingface.co/spaces/{SPACE}) ·
Paper: [arXiv 2605.29819](https://arxiv.org/abs/2605.29819) ·
[OpenReview qXlovWytwg](https://openreview.net/forum?id=qXlovWytwg). Theory paper - no official code
released.
"""

write_page(
    SLUGS["concl"],
    "Conclusion",
    [
        (CONCL_FINDINGS_META, FINDINGS),
        (CONCL_ARTIFACT_META, f"{BUCKET}"),
        (CONCL_MD_META, RERUN),
    ],
)

print("pages written:", sorted(os.listdir(PAGES)))