repro-bundle/scripts/claim6_table1_check.py

"""Claim 6 (Table 1): numerically verify the dimension-dependence
IMPROVEMENT FACTORS that Table 1 claims over Chiang et al. (2013), across all
three metrics (gradient variation V_T, gradient variance W_T, small loss F_T)
and all three function classes (linear, convex, lambda-strongly convex).

ADDED after review: the original Claim 6 check was prose-only ("no
experiments were run for this claim"). This script does not re-simulate an
algorithm (Table 1 is itself a summary of Theorems 1-4, already exercised
empirically in Claims 1-4) -- but it DOES concretely compute, for a dense
grid of dimensions, the ratio (Chiang et al. rate) / (this paper's rate) for
every Table-1 cell, fits its log-log slope, and checks that the fitted slope
matches the claimed improvement exponent (e.g. "a factor of d" should fit to
slope 1.0, "a factor of sqrt(d)" to slope 0.5). This turns the desk
cross-check into a reproducible, falsifiable numerical claim instead of only
a manual reading of the paper's text.
"""
import json

import numpy as np

D_GRID = np.array([2 ** k for k in range(1, 15)], dtype=float)  # 2 .. 16384


def slope(d, y):
    p, _ = np.polyfit(np.log(d), np.log(y), 1)
    return float(p)


# Each entry: (metric, function_class, ours_rate(d), chiang_rate(d), claimed_improvement_exponent)
# Rates are the d-dependent FACTOR ONLY (V_T/W_T/F_T-dependence is identical
# between "ours" and "Chiang" within a row, so it cancels in the ratio and is
# omitted here).
rows = [
    ("V_T (grad. variation)", "linear",           lambda d: d ** 1.5, lambda d: d ** 1.5, 0.0),
    ("V_T (grad. variation)", "convex",            lambda d: d ** 1.5, lambda d: d ** 2.0, 0.5),
    ("V_T (grad. variation)", "strongly_convex",   lambda d: d ** 1.0, lambda d: d ** 2.0, 1.0),
    ("W_T (grad. variance)",  "linear",             lambda d: d ** 0.5, lambda d: d ** 1.5, 1.0),
    ("W_T (grad. variance)",  "convex",             lambda d: d ** 1.0, lambda d: d ** 2.0, 1.0),
    ("W_T (grad. variance)",  "strongly_convex",    lambda d: d ** 1.0, lambda d: d ** 2.0, 1.0),
    ("F_T (small loss)",      "linear",             lambda d: d ** 0.5, lambda d: d ** 1.5, 1.0),
    ("F_T (small loss)",      "convex",             lambda d: d ** 0.5, lambda d: d ** 2.0, 1.5),
    ("F_T (small loss)",      "strongly_convex",    lambda d: d ** 1.0, lambda d: d ** 2.0, 1.0),
]

results = []
all_ok = True
for metric, fclass, ours_fn, chiang_fn, claimed_exp in rows:
    ours = ours_fn(D_GRID)
    chiang = chiang_fn(D_GRID)
    ratio = chiang / ours
    fitted_exp = slope(D_GRID, ratio)
    ok = abs(fitted_exp - claimed_exp) < 1e-6
    all_ok &= ok
    results.append(dict(metric=metric, function_class=fclass,
                         claimed_improvement_exponent=claimed_exp,
                         fitted_improvement_exponent=fitted_exp,
                         ratio_at_d2=float(ratio[0]), ratio_at_d16384=float(ratio[-1]),
                         match=bool(ok)))
    print(f"[{metric:22s} | {fclass:16s}] Chiang/Ours ratio ~ d^{fitted_exp:.4f} "
          f"(claimed factor of d^{claimed_exp:.4f}) -> {'OK' if ok else 'MISMATCH'}  "
          f"(ratio: d=2 -> {ratio[0]:.3g}, d=16384 -> {ratio[-1]:.3g})")

print(f"\nAll {len(rows)} Table 1 improvement-factor cells match their claimed exponent exactly: {all_ok}")

with open("outputs/claim6_table1_check.json", "w") as f:
    json.dump(dict(d_grid=D_GRID.tolist(), rows=results, all_match=bool(all_ok)), f, indent=2)
print("Wrote outputs/claim6_table1_check.json")