scripts/claim6_conjecture.py

"""CLAIM 6 -- Conjecture 5.3: for norm-oblivious comparators the minimax static regret of
uBLO is  R_T(u) = Theta( ||u|| sqrt( T (d v log||u||) ) ),  left as an OPEN PROBLEM.

This is a conjecture, not a theorem.  Nothing numerical can prove it, and this page does not
claim to.  What is done here:

 1  ACHIEVABILITY side (the O-direction, which the paper already supports via Eq. (5)):
    measure the regret of PABLO across ~7 orders of magnitude of ||u||, spanning the
    transition point log||u|| = d, on the strongest instance family we can build (max over
    a battery of adversarial and stochastic instances), and check whether
    R_T(u) / (||u|| sqrt(T (d v log||u||))) stays bounded and roughly flat across the
    transition -- i.e. whether the conjectured functional form is the right one.

 2  The OBSTRUCTION the paper describes, made executable: the scale/direction decomposition
    of Eq. (7), R_T(u) = R^V_T(||u||) + ||u|| R^Z_T(u/||u||), is computed along real
    trajectories on (a) the Theorem 5.2 direction-hard instance and (b) a scale-hard
    instance.  The paper argues the two partial lower bounds do not combine because on a
    direction-hard sequence the scale regret can be large and NEGATIVE.  That is measured.

 3  A cheap falsification probe: is there any instance in the battery on which the measured
    regret EXCEEDS C ||u|| sqrt(T(d v log||u||)) for a growing C?  (A reproducible instance
    family with a growing ratio would falsify the conjectured upper side.)
"""

from __future__ import annotations

import json
import os
import sys

import numpy as np

sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
from batch import BatchAlg6, fit_exponent, run_pablo_batch
from pablo import env_flip, env_hard, env_rademacher

OUT = os.path.join(
    os.path.dirname(os.path.dirname(os.path.abspath(__file__))), "outputs"
)
SEED = 20260725
G = 1.0
EPSILON = 1.0


def instance_battery(T, d, seed):
    """A battery of loss sequences; the adversary is approximated by taking, for each ||u||,
    the instance in the battery that maximises the measured regret."""
    out = {}
    rng = np.random.default_rng(seed)
    out["hypercube_hard"] = env_hard(T, d, G, rng)
    out["rademacher_coord"] = env_rademacher(T, d, G, rng)
    for amp in [0.05, 0.25, 1.0]:
        for nf in [1, 3, 7]:
            out["flip_amp%.2f_n%d" % (amp, nf)] = env_flip(
                T, d, G, rng, amp=amp, n_flips=nf
            )
    # a 1-dimensional (scale-hard) sequence embedded in R^d: the Streeter-McMahan geometry
    L = np.zeros((T, d))
    L[:, 0] = G * (rng.integers(2, size=T) * 2.0 - 1.0)
    out["one_dimensional_signs"] = L
    return out


def conjectured(u_norm, T, d):
    return u_norm * np.sqrt(T * max(d, np.log(max(u_norm, 1.0001))))


def run_instance(losses, T, d, S, seed, eps_pert=1e-3):
    olo = BatchAlg6(S, d, T, 2 * d * G, EPSILON / d)
    return run_pablo_batch(losses, olo, d, eps_pert, np.random.default_rng(seed), S)


def test1_achievability(T=4000, S=200):
    rows = []
    for d in [2, 4, 8]:
        norms = [10.0**k for k in range(0, 8)]
        battery = instance_battery(T, d, SEED + d)
        runs = {
            k: run_instance(v, T, d, S, SEED + 3 * d + len(k))
            for k, v in battery.items()
        }
        for un in norms:
            best, arg = -np.inf, None
            for name, r in runs.items():
                dirn = -r["sum_losses"] / max(np.linalg.norm(r["sum_losses"]), 1e-12)
                m = float(
                    np.mean(r["cum_play"] - float(np.dot(r["sum_losses"], un * dirn)))
                )
                if m > best:
                    best, arg = m, name
            c = conjectured(un, T, d)
            rows.append(
                dict(
                    d=d,
                    T=T,
                    u_norm=un,
                    worst_instance=arg,
                    max_mean_regret=best,
                    conjectured_rate=float(c),
                    ratio=best / float(c),
                    regime="d" if np.log(un) <= d else "log||u||",
                )
            )
    # is the ratio flat across the transition?
    summary = {}
    for d in [2, 4, 8]:
        rr = [x["ratio"] for x in rows if x["d"] == d]
        nn = [x["u_norm"] for x in rows if x["d"] == d]
        sl, _, se = fit_exponent(nn, np.maximum(rr, 1e-12))
        summary["d=%d" % d] = dict(
            min_ratio=float(np.min(rr)),
            max_ratio=float(np.max(rr)),
            spread=float(np.max(rr) / max(np.min(rr), 1e-12)),
            fitted_slope_of_ratio_vs_u_norm=sl,
            stderr=se,
            flat_would_be=0.0,
        )
    return dict(rows=rows, flatness_summary=summary, seeds=S)


def test2_decomposition(T=4000, S=200):
    """Eq. (7): R_T(u) = R^V_T(||u||) + ||u|| R^Z_T(u/||u||) with
    R^V_T(||u||) = sum_t (v_t - ||u||) <z_t, l_t>,  R^Z_T = sum_t <z_t - u/||u||, l_t>.
    """
    rows = []
    for d in [4, 16]:
        for name, losses in [
            (
                "theorem_5_2_direction_hard",
                env_hard(T, d, G, np.random.default_rng(SEED + d)),
            ),
            ("scale_hard_one_dimensional", None),
        ]:
            if losses is None:
                losses = np.zeros((T, d))
                rng = np.random.default_rng(SEED + 7 * d)
                losses[:, 0] = G * (rng.integers(2, size=T) * 2.0 - 1.0)
            r = run_instance(losses, T, d, S, SEED + 11 * d)
            sl = r["sum_losses"]
            dirn = -sl / max(np.linalg.norm(sl), 1e-12)
            A = r["sum_dir"]  # sum_t <z_t, l_t>
            RZ = float(np.mean(A - float(np.dot(sl, dirn))))
            for un in [1.0, 100.0, 1e4]:
                RV = float(np.mean(r["cum_play"] - un * A))
                R = float(np.mean(r["cum_play"] - float(np.dot(sl, un * dirn))))
                rows.append(
                    dict(
                        d=d,
                        instance=name,
                        u_norm=un,
                        direction_regret_R_Z=RZ,
                        scale_regret_R_V=RV,
                        full_regret=R,
                        identity_residual=abs(R - (RV + un * RZ)),
                        sqrt_dT=float(np.sqrt(d * T)),
                        R_Z_over_sqrt_dT=RZ / float(np.sqrt(d * T)),
                        scale_regret_is_negative=bool(RV < 0),
                    )
                )
    return rows


def test3_falsification_probe(T=4000, S=200):
    worst = []
    for d in [2, 4, 8, 16]:
        battery = instance_battery(T, d, SEED + 5 * d)
        for name, losses in battery.items():
            r = run_instance(losses, T, d, S, SEED + 13 * d + len(name))
            dirn = -r["sum_losses"] / max(np.linalg.norm(r["sum_losses"]), 1e-12)
            for un in [1.0, 1e2, 1e4, 1e6]:
                m = float(
                    np.mean(r["cum_play"] - float(np.dot(r["sum_losses"], un * dirn)))
                )
                worst.append(
                    dict(d=d, instance=name, u_norm=un, ratio=m / conjectured(un, T, d))
                )
    mx = max(worst, key=lambda x: x["ratio"])
    return dict(
        instances_probed=len(worst),
        worst_case=mx,
        max_ratio=mx["ratio"],
        any_ratio_above_one=bool(mx["ratio"] > 1.0),
    )


if __name__ == "__main__":
    res = dict(
        claim="claim-6 Conjecture 5.3 (OPEN PROBLEM)",
        seed=SEED,
        honesty_note="Conjecture 5.3 is an open problem. No simulation can prove the "
        "Omega side. The verdict recorded for this claim is 'toy': "
        "numerical evidence about the conjectured functional form on "
        "synthetic instances, nothing more.",
        T1_achievability_shape=test1_achievability(),
        T2_scale_direction_decomposition=test2_decomposition(),
        T3_falsification_probe=test3_falsification_probe(),
    )
    os.makedirs(OUT, exist_ok=True)
    with open(os.path.join(OUT, "claim6_conjecture.json"), "w") as f:
        json.dump(res, f, indent=1)
    print(json.dumps(res, indent=1))