scripts/claim6_thm312_proper.py

"""
CLAIM 6 -- Theorem 3.12:  proper learners require sample complexity
Omega((d_gamma/eps) ln(1/eps)), strictly worse than the O(d_gamma/eps) achieved
by median-of-three aggregation.

Concretely the theorem states: for any 0 < gamma < 1 and d_gamma >= 2 there is a
class H with gamma-graph dimension d_gamma such that for every proper learner A
and every 0 < eps < 1/(64e) there is a realizable D with
    E_{S~D^n}[L^gamma_D(A(S))] >= 4 eps / 3   whenever  n <= (d/(32 eps)) ln(1/(64 e eps)).

Independent method
------------------
(a) Build the split-space class of the proof overview and verify d_gamma = d
    exhaustively (Definition 3.2).
(b) Re-derive the hard instance: ku = Theta(d/eps), A subset [ku] with
    |A| = ku - d + 1 drawn uniformly, D_A uniform on {(ku,i) : i in A}, labels 0,
    realizable by h_{ku, A^c}.  Conditioned on the sample, the unobserved points
    are exchangeable, so EVERY proper learner is forced to pick its d-1
    "gamma-far" points blindly from the unobserved set.  We verify this
    exchangeability empirically by running five different proper-learner
    strategies and comparing their losses.
(c) Check the theorem's inequality at n = floor((d/(32 eps)) ln(1/(64 e eps))).
(d) The headline: measure n*(eps), the smallest n at which the BEST proper
    learner reaches loss eps against the worst ku, and regress n* eps / d on
    ln(1/eps).  A non-zero slope is the extra ln(1/eps) factor.
(e) Run median-of-three interpolators on the SAME instances and show it reaches
    eps with n = Theta(d/eps) (no log), i.e. aggregation strictly beats proper
    learning.

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 (
    dump_json,
    fit_loglog_slope,
    gamma_graph_dim,
    thm312_class,
)  # noqa: E402

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.12",
       "eps_upper_limit_1_over_64e": 1.0 / (64 * math.e)}

# ---------------------------------------------------------------------------
# (a) the class has gamma-graph dimension exactly d
# ---------------------------------------------------------------------------
print("== Theorem 3.12 class: exhaustive gamma-graph dimension ==")
dims = []
for d in (2, 3, 4):
    cls, specs, offs = thm312_class([2 * d, max(1, d - 1)], d, GAMMA)
    dg = gamma_graph_dim(cls, GAMMA, max_d=d + 2)
    dims.append(
        {
            "d": d,
            "blocks": [2 * d, max(1, d - 1)],
            "n_hyp": cls.n_hyp,
            "n_pts": cls.n_pts,
            "d_gamma": dg,
            "match": bool(dg == d),
        }
    )
    print(
        f"  d={d}: |H|={cls.n_hyp:4d} |X|={cls.n_pts:3d}  d_gamma={dg}  (expected {d})"
    )
res["dimensions"] = dims
res["all_dims_match"] = bool(all(x["match"] for x in dims))


# ---------------------------------------------------------------------------
# (b) the hard instance and the loss of ANY proper learner
# ---------------------------------------------------------------------------
def proper_loss_analytic(d, ku, n):
    """E[L] for the optimal proper learner.
    |A| = N = ku - d + 1.  After n i.i.d. draws from A, m = N - #distinct A-points
    are unobserved.  The unobserved universe is U = M  union  A^c, |U| = m + d - 1,
    and by exchangeability the learner's d-1 chosen gamma-far points are uniform
    in U, so E[|A' ∩ A|] = (d-1) m / (m + d - 1) and L = that / N."""
    N = ku - d + 1
    if N <= 0:
        return 0.0
    m = N * (1.0 - 1.0 / N) ** n
    return float((d - 1) * m / ((m + d - 1) * N))


def proper_loss_mc(d, ku, n, trials, seed, strategy="random"):
    """Real simulation with an explicit proper learner strategy."""
    rng = np.random.default_rng(seed)
    N = ku - d + 1
    out = np.empty(trials)
    for t in range(trials):
        perm = rng.permutation(ku)
        A = np.sort(perm[:N])  # the support of D_A
        Ac = np.sort(perm[N:])  # the d-1 points the target is gamma-far on
        draws = A[rng.integers(0, N, size=n)]
        obs = np.unique(draws)
        U = np.setdiff1d(np.arange(ku), obs, assume_unique=False)
        if strategy == "random":
            pick = rng.choice(U, size=d - 1, replace=False)
        elif strategy == "lowest":
            pick = U[: d - 1]
        elif strategy == "highest":
            pick = U[-(d - 1) :]
        elif strategy == "spread":
            pick = U[np.linspace(0, len(U) - 1, d - 1).astype(int)]
        elif strategy == "middle":
            mid = len(U) // 2
            pick = U[mid : mid + d - 1]
        out[t] = np.isin(pick, A).sum() / N
    return float(out.mean()), float(out.std(ddof=1) / math.sqrt(trials))


print("\n== proper learners are forced to guess: five strategies, same loss ==")
# the theorem requires 0 < eps < 1/(64 e) = 0.005746 for the sample bound to be
# positive; we use eps = 0.001
d_t, eps_t = 16, 0.001
ku_t = int(round(d_t / (2 * eps_t)))
n_t = max(
    1, int(np.floor((d_t / (32 * eps_t)) * math.log(1.0 / (64 * math.e * eps_t))))
)
strat = {}
for s in ("random", "lowest", "highest", "spread", "middle"):
    mean, se = proper_loss_mc(d_t, ku_t, n_t, 1500, SEED + 3, s)
    strat[s] = {"E_loss": mean, "stderr": se}
    print(f"  strategy={s:8s}  E[L] = {mean:.6f} +/- {2*se:.6f}")
ana = proper_loss_analytic(d_t, ku_t, n_t)
res["strategy_equivalence"] = {
    "d": d_t,
    "eps": eps_t,
    "ku": ku_t,
    "n": n_t,
    "analytic": ana,
    "strategies": strat,
}
vals = [v["E_loss"] for v in strat.values()]
res["strategy_spread_rel"] = float((max(vals) - min(vals)) / np.mean(vals))
res["analytic_vs_mc_rel_err"] = float(abs(np.mean(vals) - ana) / ana)
print(
    f"  analytic prediction = {ana:.6f}; strategy spread = "
    f"{res['strategy_spread_rel']*100:.2f}% ; analytic vs MC = {res['analytic_vs_mc_rel_err']*100:.2f}%"
)

# ---------------------------------------------------------------------------
# (c) the theorem's inequality
# ---------------------------------------------------------------------------
print("\n== Theorem 3.12 at n = floor((d/(32 eps)) ln(1/(64 e eps))) ==")
grid = []
for d in (4, 8, 16, 32, 64):
    for eps in (0.005, 0.002, 0.001, 0.0005, 0.0002):
        n = max(
            1, int(np.floor((d / (32 * eps)) * math.log(1.0 / (64 * math.e * eps))))
        )
        # the theorem lets the adversary choose D; ku = Theta(d/eps) -- optimise
        best = max(
            (
                (proper_loss_analytic(d, ku, n), ku)
                for ku in [
                    int(round(c * d / eps))
                    for c in (0.25, 0.4, 0.5, 0.75, 1.0, 1.5, 2.0, 3.0)
                ]
            )
        )
        grid.append(
            {
                "d_gamma": d,
                "eps": eps,
                "n_theorem": n,
                "best_ku": best[1],
                "ku_over_d_over_eps": best[1] / (d / eps),
                "E_loss": best[0],
                "target_4eps_over_3": 4 * eps / 3,
                "E_loss_over_eps": best[0] / eps,
                "holds": bool(best[0] >= 4 * eps / 3),
            }
        )
res["grid"] = grid
n_hold = sum(g["holds"] for g in grid)
res["grid_hold"] = f"{n_hold}/{len(grid)}"
res["min_ratio_to_4eps3"] = min(g["E_loss"] / (4 * g["eps"] / 3) for g in grid)
print(
    f"  {n_hold}/{len(grid)} cells satisfy E[L] >= 4eps/3;  min E[L]/(4eps/3) = {res['min_ratio_to_4eps3']:.4f}"
)
for g in grid:
    if g["d_gamma"] == 16:
        print(
            f"    d={g['d_gamma']:3d} eps={g['eps']:<7} n={g['n_theorem']:8d} ku={g['best_ku']:9d} "
            f"(={g['ku_over_d_over_eps']:.2f} d/eps)  E[L]={g['E_loss']:.6f}  vs 4eps/3={4*g['eps']/3:.6f}  {g['holds']}"
        )

# spot-check three grid cells with the real Monte-Carlo simulation
print("\n  Monte-Carlo spot checks of the analytic loss:")
spot = []
for d, eps in ((8, 0.005), (16, 0.002), (32, 0.005)):
    n = int(np.floor((d / (32 * eps)) * math.log(1.0 / (64 * math.e * eps))))
    ku = [g for g in grid if g["d_gamma"] == d and g["eps"] == eps][0]["best_ku"]
    a = proper_loss_analytic(d, ku, n)
    m, se = proper_loss_mc(d, ku, n, 800, SEED + 17)
    spot.append(
        {
            "d": d,
            "eps": eps,
            "n": n,
            "ku": ku,
            "analytic": a,
            "mc": m,
            "mc_stderr": se,
            "rel_err": abs(m - a) / a,
        }
    )
    print(
        f"    d={d:3d} eps={eps:<7} n={n:8d} ku={ku:8d}: analytic={a:.6f}  MC={m:.6f} +/- {2*se:.6f}"
    )
res["mc_spot_checks"] = spot

# ---------------------------------------------------------------------------
# (d) the ln(1/eps) factor, measured
# ---------------------------------------------------------------------------
print("\n== measured sample complexity of the best proper learner ==")


def worst_proper_loss(d, n):
    """max over ku of the optimal proper learner's loss at sample size n."""
    best = 0.0
    for c in np.geomspace(0.02, 40.0, 260):
        ku = int(round(c * n)) + d
        if ku <= d:
            continue
        best = max(best, proper_loss_analytic(d, ku, n))
    return best


def n_star_proper(d, eps):
    lo, hi = 1, 1 << 30
    while lo < hi:
        mid = (lo + hi) // 2
        if worst_proper_loss(d, mid) <= eps:
            hi = mid
        else:
            lo = mid + 1
    return lo


rows = []
for d in (8, 32, 128):
    for eps in (0.05, 0.02, 0.01, 0.005, 0.002, 0.001, 0.0005, 0.0002):
        ns = n_star_proper(d, eps)
        rows.append(
            {
                "d_gamma": d,
                "eps": eps,
                "n_star_proper": ns,
                "n_star_eps_over_d": ns * eps / d,
                "ln_1_over_eps": math.log(1 / eps),
            }
        )
        if d == 32:
            print(
                f"  d={d:4d} eps={eps:<7} n*={ns:10d}   n* eps/d = {ns*eps/d:8.4f}   ln(1/eps)={math.log(1/eps):.3f}"
            )
res["proper_sample_complexity"] = rows

# regress n* eps/d on ln(1/eps): the ln(1/eps) factor shows up as a positive slope
for d in (8, 32, 128):
    sub = [r for r in rows if r["d_gamma"] == d]
    x = np.array([r["ln_1_over_eps"] for r in sub])
    y = np.array([r["n_star_eps_over_d"] for r in sub])
    A_ = np.vstack([x, np.ones_like(x)]).T
    coef = np.linalg.lstsq(A_, y, rcond=None)[0]
    pred = A_ @ coef
    r2 = 1 - ((y - pred) ** 2).sum() / ((y - y.mean()) ** 2).sum()
    res[f"linear_fit_d{d}"] = {
        "slope_vs_ln_1_over_eps": float(coef[0]),
        "intercept": float(coef[1]),
        "r2": float(r2),
    }
    print(
        f"  d={d:4d}: n* eps/d = {coef[0]:.4f} * ln(1/eps) + {coef[1]:.4f}   R^2={r2:.5f}"
    )
    # null model: n* eps/d = const (i.e. no ln(1/eps) factor)
    r2_null = 1 - ((y - y.mean()) ** 2).sum() / ((y - y.mean()) ** 2).sum()
    res[f"const_model_range_d{d}"] = float(y.max() / y.min())
    print(
        f"        constant-model check: n* eps/d ranges over {y.min():.3f} .. {y.max():.3f} "
        f"(factor {y.max()/y.min():.2f}) -> NOT constant"
    )

# ---------------------------------------------------------------------------
# (e) median-of-three on the SAME instances
# ---------------------------------------------------------------------------
print("\n== median-of-three interpolators on the same class ==")


def median3_loss_mc(d, ku, n, trials, seed):
    """Three independent samples; each yields an interpolator h_{ku,A'_j} with
    A'_j a size-(d-1) subset of that sample's unobserved set.  The pointwise
    median errs at a point of A iff at least two of the three are gamma-far
    there.  (Note: the median-of-three predictor is NOT a member of H, so this
    is exactly the improper aggregation the theorem is compared against.)"""
    rng = np.random.default_rng(seed)
    N = ku - d + 1
    out = np.empty(trials)
    for t in range(trials):
        perm = rng.permutation(ku)
        A = np.sort(perm[:N])
        far_counts = np.zeros(ku, dtype=np.int8)
        for _ in range(3):
            obs = np.unique(A[rng.integers(0, N, size=n)])
            U = np.setdiff1d(np.arange(ku), obs)
            pick = rng.choice(U, size=d - 1, replace=False)
            far_counts[pick] += 1
        out[t] = (far_counts[A] >= 2).sum() / N
    return float(out.mean()), float(out.std(ddof=1) / math.sqrt(trials))


comp = []
for d in (8, 16, 32):
    for eps in (0.005, 0.002, 0.001):
        n = int(np.floor((d / (32 * eps)) * math.log(1.0 / (64 * math.e * eps))))
        ku = [g for g in grid if g["d_gamma"] == d and g["eps"] == eps]
        ku = ku[0]["best_ku"] if ku else int(round(0.5 * d / eps))
        pl = proper_loss_analytic(d, ku, n)
        m3, se3 = median3_loss_mc(d, ku, n, 400, SEED + 41)
        comp.append(
            {
                "d_gamma": d,
                "eps": eps,
                "n": n,
                "ku": ku,
                "proper_E_loss": pl,
                "median3_E_loss": m3,
                "median3_stderr": se3,
                "ratio_proper_over_median3": pl / max(m3, 1e-12),
            }
        )
        print(
            f"  d={d:3d} eps={eps:<7} n={n:8d} ku={ku:8d}:  proper={pl:.6f}   "
            f"median-of-3={m3:.6f} +/- {2*se3:.6f}   ratio={pl/max(m3,1e-12):8.1f}x"
        )
res["proper_vs_median3"] = comp
res["median3_beats_proper_everywhere"] = bool(
    all(c["median3_E_loss"] < c["proper_E_loss"] for c in comp)
)

slopes = [res[f"linear_fit_d{d}"]["slope_vs_ln_1_over_eps"] for d in (8, 32, 128)]
ok = (
    res["all_dims_match"]
    and n_hold == len(grid)
    and all(s > 0.01 for s in slopes)
    and all(res[f"linear_fit_d{d}"]["r2"] > 0.98 for d in (8, 32, 128))
    and res["median3_beats_proper_everywhere"]
)
res["verdict"] = "verified" if ok else "partial"
print(f"\nverdict = {res['verdict']}")
dump_json(os.path.join(OUT, "claim6_thm312.json"), res)