scripts/claim4_thm310_failure.py

"""
CLAIM 4 -- Theorem 3.10:  for some hypothesis classes with constant gamma-OIG
dimension, NO finite interpolating aggregation rule can achieve non-trivial
cutoff loss regardless of sample size (E[L] >= 1 - eps for every n <= n'),
so learning them requires either infinite aggregation or non-interpolating rules.

Independent method
------------------
(a) Build the split-space class of the proof overview:
    X = union_{k = i^2} {(k,x) : x <= k},
    H = {h_{k,A} : |A| = sqrt(k)},  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.
    Compute the gamma-OIG dimension EXHAUSTIVELY (Definition 3.9, every point
    set, every orientation) and show d_gamma = sqrt(k) grows without bound.
(b) Simulate the hard distribution D_A (uniform on {(ku,i) : i in A}) against a
    best-effort finite aggregation algorithm with m hypotheses, with ku chosen
    as the proof requires (ku = omega(n'^2) and ku >> (m/eps)^2), and measure
    the realised cutoff loss.
(c) Compare against random guessing (1 - Theta(gamma)) to confirm the
    "worse than trivial" statement, and probe the two load-bearing assumptions
    (finiteness of the aggregation, interpolating-ness of the rule).

Seeds: numpy default_rng(20260725 + offset).  CPU only.
"""

import math
import os
import sys

import numpy as np

sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
from core import (  # noqa: E402
    dump_json,
    gamma_graph_dim,
    gamma_oig_dim,
    thm310_block_class,
    thm310_class,
)

OUT = os.path.join(
    os.path.dirname(os.path.dirname(os.path.abspath(__file__))), "outputs"
)
GAMMA = 0.1
SEED = 20260725
res = {"gamma": GAMMA, "seed": SEED, "theorem": "3.10"}

# ---------------------------------------------------------------------------
# (a) dimensions
# ---------------------------------------------------------------------------
print("== dimensions of the Theorem 3.10 split-space class ==")
rows = []
for k in (4, 9, 16):
    cls, _ = thm310_block_class(k, GAMMA)
    dg = gamma_graph_dim(cls, GAMMA, max_d=math.isqrt(k) + 1)
    rows.append(
        {
            "block_k": k,
            "sqrt_k": math.isqrt(k),
            "d_gamma": dg,
            "matches_sqrt_k": bool(dg == math.isqrt(k)),
            "n_hyp": cls.n_hyp,
        }
    )
    print(
        f"  block k={k:3d} (|H|={cls.n_hyp:5d}): d_gamma={dg}  (= sqrt(k) = {math.isqrt(k)})"
    )
res["d_gamma_growth"] = rows
res["d_gamma_unbounded"] = bool(all(r["matches_sqrt_k"] for r in rows))
print(
    f"  -> d_gamma = sqrt(k) is unbounded over the union of blocks: {res['d_gamma_unbounded']}"
)

print("\n  exhaustive gamma-OIG dimension (Definition 3.9):")
oig_rows = []
for blocks in ([1, 4], [4, 9], [1, 4, 9]):
    cls, specs, offs = thm310_class(blocks, GAMMA)
    max_k = 4 if cls.n_pts >= 4 else cls.n_pts
    oig, detail = gamma_oig_dim(cls, GAMMA, max_k=max_k)
    oig_rows.append(
        {
            "blocks": blocks,
            "n_hyp": cls.n_hyp,
            "n_pts": cls.n_pts,
            "oig_dim": oig,
            "le_3": bool(oig <= 3),
            "detail": detail,
        }
    )
    print(
        f"    blocks={blocks} |H|={cls.n_hyp:4d} |X|={cls.n_pts:3d}: gamma-OIG dim = {oig} "
        f"(min-max-outdeg per k: {[(k, v['min_max_outdegree']) for k, v in detail.items()]})"
    )
res["oig"] = oig_rows
res["oig_constant_le_3"] = bool(all(r["le_3"] for r in oig_rows))


# ---------------------------------------------------------------------------
# (b) the failure of finite interpolating aggregation
# ---------------------------------------------------------------------------
def simulate(n_prime, m, eps, trials, seed, ku_factor=4.0):
    """ku chosen as the proof requires: sqrt(ku) >= (ku_factor/eps)*max(n', m),
    which is both ku = omega(n'^2) and ku >> (m/eps)^2.

    |A| = sqrt(ku) = s.  The best-effort finite aggregation algorithm puts every
    observed point into the zero set of one of its m hypotheses and spends the
    remaining m*s - |obs| zero-slots uniformly over the unobserved part of the
    block.  Each still-unobserved point of A is then covered independently with
    probability 1 - (1 - 1/(ku-|obs|))^(m*s-|obs|); anything not covered is
    mispredicted by EVERY interpolating rule, because every selected hypothesis
    outputs a value > gamma there while the label is 0."""
    s = int(math.ceil(ku_factor * max(n_prime, m) / eps))  # s = sqrt(ku) = |A|
    ku = s * s
    rng = np.random.default_rng(seed)
    losses = np.empty(trials)
    for t in range(trials):
        obs = np.unique(rng.integers(0, s, size=n_prime))  # distinct A-points seen
        c_obs = int(len(obs))
        slots = max(0, m * s - c_obs)
        p_hit = 1.0 - (1.0 - 1.0 / max(ku - c_obs, 1)) ** slots
        c_guess = int(rng.binomial(s - c_obs, p_hit))
        losses[t] = 1.0 - (c_obs + c_guess) / s
    return float(losses.mean()), float(losses.std(ddof=1) / math.sqrt(trials)), ku, s


print("\n== Theorem 3.10: E[L] >= 1 - eps for finite interpolating aggregation ==")
grid = []
for eps in (0.1, 0.05, 0.02):
    for n_prime in (10, 100, 1000):
        for m in (1, 10, 100):
            mean, se, ku, s = simulate(n_prime, m, eps, 400, SEED + n_prime + m)
            grid.append(
                {
                    "eps": eps,
                    "n_prime": n_prime,
                    "m_hypotheses": m,
                    "ku": ku,
                    "sqrt_ku": s,
                    "E_loss": mean,
                    "stderr": se,
                    "target_1_minus_eps": 1 - eps,
                    "holds": bool(mean + 2 * se >= 1 - eps),
                }
            )
res["grid"] = grid
n_hold = sum(g["holds"] for g in grid)
res["grid_hold"] = f"{n_hold}/{len(grid)}"
res["min_E_loss"] = min(g["E_loss"] for g in grid)
print(
    f"  {n_hold}/{len(grid)} cells satisfy E[L] >= 1-eps;  min E[L] over grid = {res['min_E_loss']:.5f}"
)
for g in grid:
    if g["eps"] == 0.05:
        print(
            f"    eps={g['eps']} n'={g['n_prime']:5d} m={g['m_hypotheses']:4d} "
            f"ku={g['ku']:12d}  E[L]={g['E_loss']:.5f} (>= {1-g['eps']:.2f}? {g['holds']})"
        )

# sample size is irrelevant: sweep n' at fixed ku scaling
print("\n  loss vs n' (ku re-chosen for each n' as the theorem allows):")
ns = []
for n_prime in (1, 10, 100, 1000, 10000):
    mean, se, ku, s = simulate(n_prime, 10, 0.02, 200, SEED + 3)
    ns.append({"n_prime": n_prime, "ku": ku, "E_loss": mean})
    print(f"    n'={n_prime:6d}  ku={ku:14d}  E[L]={mean:.5f}")
res["loss_vs_n"] = ns

# ---------------------------------------------------------------------------
# (c) comparison with random guessing + assumption probes
# ---------------------------------------------------------------------------
print("\n== worse than random guessing, and the load-bearing assumptions ==")
rng = np.random.default_rng(SEED + 9)
# random guessing: uniform value in [0,1]; labels are 0
u = rng.random(2_000_000)
rand_uniform = float(np.mean(np.abs(u - 0.0) > GAMMA))
# random guessing over the gamma-net {2 i gamma}
net = 2 * GAMMA * np.arange(0, int(1 / (2 * GAMMA)) + 1)
pick = net[rng.integers(0, len(net), size=2_000_000)]
rand_net = float(np.mean(np.abs(pick - 0.0) > GAMMA))
res["random_guessing_uniform_loss"] = rand_uniform
res["random_guessing_gamma_net_loss"] = rand_net
res["theory_random_guessing"] = 1 - GAMMA
worst_fa = max(g["E_loss"] for g in grid if g["eps"] == 0.02)
res["finite_agg_loss_at_eps0.02"] = worst_fa
res["finite_agg_worse_than_random"] = bool(worst_fa > rand_uniform)
print(
    f"  random guessing (uniform in [0,1]):   L = {rand_uniform:.5f}   (theory 1 - gamma = {1-GAMMA})"
)
print(f"  random guessing (gamma-net):          L = {rand_net:.5f}")
print(
    f"  finite interpolating aggregation:     L = {worst_fa:.5f}   "
    f"-> {'WORSE than random guessing' if res['finite_agg_worse_than_random'] else 'not worse'} (eps = 0.02 < gamma = {GAMMA})"
)

probes = {}
# probe 1: let the aggregation grow.  With m = sqrt(ku) hypotheses (i.e. as many
# zero-slots as there are points in the block) the aggregation can cover the
# whole block and the bound evaporates -- this is the theorem's "aggregate
# infinitely many hypotheses" escape.
mean_m1, _, ku_p, s_p = simulate(100, 1, 0.02, 200, SEED + 21)
probes["finite_m1_E_loss"] = mean_m1
mgrid = []
for m in (1, 10, 100, 1000, s_p // 10, s_p, 10 * s_p):
    mm, _, _, _ = simulate(100, 1, 0.02, 200, SEED + 22)
    # recompute directly at the same ku with m hypotheses
    slots = m * s_p
    p_hit = 1.0 - (1.0 - 1.0 / ku_p) ** slots
    mgrid.append(
        {"m": int(m), "m_over_sqrt_ku": m / s_p, "expected_E_loss": 1.0 - p_hit}
    )
    print(f"    m={int(m):8d}  (= {m/s_p:8.3f} sqrt(ku))  E[L] -> {1.0-p_hit:.5f}")
probes["m_growth"] = mgrid
probes["infinite_aggregation_E_loss"] = mgrid[-1]["expected_E_loss"]
# probe 2: a NON-interpolating rule (constant 0) may predict outside the range
#          of its inputs; all labels are 0, so its cutoff loss is exactly 0
probes["non_interpolating_const0_E_loss"] = 0.0
res["assumption_probes"] = probes
print(f"  probe: m=1 finite aggregation           L = {probes['finite_m1_E_loss']:.5f}")
print(
    f"  probe: m = 10 sqrt(ku) (-> infinite)    L = {probes['infinite_aggregation_E_loss']:.5f}  (escapes)"
)
print(
    f"  probe: non-interpolating rule (const 0) L = {probes['non_interpolating_const0_E_loss']:.5f}  (escapes)"
)
print("  -> both escapes are exactly the two exits the theorem names.")

ok = (
    res["oig_constant_le_3"]
    and res["d_gamma_unbounded"]
    and n_hold == len(grid)
    and res["finite_agg_worse_than_random"]
)
res["verdict"] = "verified" if ok else "partial"
print(f"\nverdict = {res['verdict']}")
dump_json(os.path.join(OUT, "claim4_thm310.json"), res)