scripts/claim4b_blocks.py

"""
CLAIM 4, part B -- learning-to-warm-start on the s-normalised block-decomposable MILP family.

On the flat family the trace of Cov(pi*(P)) saturates in s (the instance size is held fixed
while s grows), so the s-exponent of the warm-start excess risk is confounded.  Here the
instance grows with s, so the O(s/N) claim of Theorem 6.1 can be tested cleanly on genuine
MILP instances.
"""

import sys, os, time

sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
import numpy as np
from blockfam import gen_block_instance, BlockPool, maximize_weighted_block
from common import loglog_fit, dump_json

OUT = os.path.join(
    os.path.dirname(os.path.dirname(os.path.abspath(__file__))), "outputs"
)
SEED = 61618
PIMAX = 1.0
M = 800
t0 = time.time()
res = {"seed": SEED, "pimax": PIMAX, "M": M}
rows = []
S_LIST = [2, 4, 8, 16, 32]
N_LIST = [8, 16, 32, 64, 128, 256, 512]
TIE = 1e-6

for s in S_LIST:
    r = np.random.default_rng(SEED + 5 * s)
    insts = []
    while len(insts) < M:
        it = gen_block_instance(r, s)
        if it is not None:
            insts.append(it)
    pool = BlockPool(insts, PIMAX)
    # exact pi*(P_i) with a vanishing linear tie-break (consistent min-sum rule)
    tp = time.time()
    PS = np.empty((M, s))
    for i in range(M):
        sub = BlockPool.__new__(BlockPool)
        sub.M, sub.s, sub.pimax, sub.K = 1, s, PIMAX, pool.K
        sub.AA = pool.AA[i : i + 1]
        sub.W1 = pool.W1[i : i + 1]
        sub.W2 = pool.W2[i : i + 1]
        sub.bb = pool.bb[i : i + 1] - TIE
        sub.prev, sub.nxt, sub.B = pool.prev, pool.nxt, pool.B
        PS[i] = maximize_weighted_block(sub, np.array([0]), np.array([1.0]))[0]
    phi_star = PS.mean(axis=0)
    trace_cov = float(((PS - phi_star) ** 2).sum(axis=1).mean())
    print(
        "s=%2d  %d exact pi*(P) in %.1fs   tr(Cov)=%.5f   per-coord %.5f"
        % (s, M, time.time() - tp, trace_cov, trace_cov / s)
    )
    for N in N_LIST:
        exact = trace_cov / N
        mc = [
            float(np.sum((PS[r.integers(0, M, N)].mean(axis=0) - phi_star) ** 2))
            for _ in range(400)
        ]
        rows.append(
            {
                "s": s,
                "N": N,
                "trace_cov": trace_cov,
                "exact_excess_risk": exact,
                "monte_carlo": float(np.mean(mc)),
                "popoviciu_bound_s_pimax2_over_4N": float(s * PIMAX**2 / (4 * N)),
                "within_popoviciu": bool(exact <= s * PIMAX**2 / (4 * N)),
            }
        )
res["rows"] = rows
res["N_exponents"] = {
    str(s): loglog_fit(
        [x["N"] for x in rows if x["s"] == s],
        [x["exact_excess_risk"] for x in rows if x["s"] == s],
    )
    for s in S_LIST
}
res["s_exponents"] = {
    str(N): loglog_fit(
        [x["s"] for x in rows if x["N"] == N],
        [x["exact_excess_risk"] for x in rows if x["N"] == N],
    )
    for N in N_LIST
}
res["popoviciu_never_violated"] = bool(all(x["within_popoviciu"] for x in rows))
res["max_ratio_to_popoviciu"] = float(
    max(x["exact_excess_risk"] / x["popoviciu_bound_s_pimax2_over_4N"] for x in rows)
)
print(
    "N-exponents (predicted -1):",
    {k: round(v[0], 3) for k, v in res["N_exponents"].items()},
)
print(
    "s-exponents (predicted +1):",
    {k: round(v[0], 3) for k, v in res["s_exponents"].items()},
)
print(
    "Popoviciu never violated:",
    res["popoviciu_never_violated"],
    " max ratio:",
    round(res["max_ratio_to_popoviciu"], 4),
)
res["wall_time_s"] = time.time() - t0
dump_json(os.path.join(OUT, "claim4b_blocks.json"), res)
print("done in", round(time.time() - t0, 1), "s")