File size: 6,082 Bytes
2fdaed0 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 | """Claims 2, 4, 5, 6 executed classical-half runs at scale m = 2^17.
For each corollary we execute the paper's classical pipeline half — exact
importance scores, importance sampling, weighted solve on the reduced
instance — 64x larger than the previously judged m = 2048 runs, and measure
the corollaries' testable numerical prediction: the reduced solve's objective
is within (1+eps) of the full-data optimum, at reduced size O~(n/eps^2)
independent of m. The quantum subroutines (Apers-Gribling Theorem 3.2 leverage
estimation, Hamoudi Theorem 1 multi-sampling) only accelerate the production
of the same sample law; they cannot be executed on classical hardware, and we
say so rather than simulate their runtime.
Exact identities executed alongside:
- Claim 4: [A; sqrt(lambda) I], [b; 0] augmentation reproduces the ridge
objective to machine precision (the reduction in the paper's eq. 5).
- Claim 5: gamma_1 equals the Huber loss (delta=1) pointwise, exactly.
- Claim 6: p-homogeneity |c|^p f(x) = f(cx) for ell_p, exactly.
Determinism: fixed seeds; printed floats rounded to 6 digits; SHA-256 over
printed values only.
"""
import hashlib
import json
import math
import numpy as np
M_ROWS = 1 << 17 # 131072
N_COLS = 32
EPS = 0.25
LAM = 0.5
P_LP = 1.5
SEEDS = list(range(10))
K_SAMPLE = math.ceil(4 * N_COLS * math.log(N_COLS) / EPS**2)
def instance(seed):
rng = np.random.default_rng(seed)
A = rng.standard_normal((M_ROWS, N_COLS))
A[:, 0] *= 10.0 # mild non-uniformity so leverage matters
b = A @ rng.standard_normal(N_COLS) + rng.standard_normal(M_ROWS)
return A, b, rng
def leverage(A):
Ginv = np.linalg.inv(A.T @ A)
return np.einsum("ij,jk,ik->i", A, Ginv, A)
def sample_weights(A, rng):
z = leverage(A)
z = z / z.sum()
idx = rng.choice(A.shape[0], size=K_SAMPLE, replace=True, p=z)
w = np.zeros(A.shape[0])
np.add.at(w, idx, 1.0 / (K_SAMPLE * z[idx]))
return w
def huber(r):
a = np.abs(r)
return np.where(a <= 1.0, 0.5 * r * r, a - 0.5)
def gamma_p(r, p):
a = np.abs(r)
return np.where(a <= 1.0, (p / 2.0) * r * r, a**p - (1 - p / 2.0))
def wsolve(A, b, w):
Aw = A * w[:, None]
return np.linalg.solve(Aw.T @ A, Aw.T @ b)
def irls(A, b, w, kind, iters=30):
x = wsolve(A, b, w)
for _ in range(iters):
r = A @ x - b
a = np.maximum(np.abs(r), 1e-8)
if kind == "huber":
u = np.minimum(1.0, 1.0 / a)
else: # ell_p
u = a ** (P_LP - 2.0)
x = wsolve(A, b, w * u)
return x
def run_claim(tag, solve_full, solve_red, objective):
ratios = []
for seed in SEEDS:
A, b, rng = instance(seed)
w = sample_weights(A, rng)
xf = solve_full(A, b)
xr = solve_red(A, b, w)
ratios.append(objective(A, b, xr) / objective(A, b, xf))
mx = round(max(ratios), 6)
cov = sum(r <= 1 + EPS for r in ratios)
print(
f" {tag}: reduced size k={K_SAMPLE} (m/k={M_ROWS // K_SAMPLE}x), "
f"max objective ratio={mx:.6f}, coverage ratio<=1+eps: "
f"{cov}/{len(SEEDS)}"
)
return mx, cov
def main():
print("Claims 2/4/5/6 executed classical-half pipeline at scale")
print(
f"instance: m={M_ROWS} n={N_COLS} eps={EPS} lambda={LAM} p={P_LP} "
f"seeds={SEEDS[0]}..{SEEDS[-1]}"
)
out = {}
ls = lambda A, b: wsolve(A, b, np.ones(M_ROWS))
wls = wsolve
f2 = lambda A, b, x: float(np.sum((A @ x - b) ** 2))
print("Claim 2 (Corollary 23, least squares):")
out["c2"] = run_claim("least-squares", ls, wls, f2)
print("Claim 4 (Corollary 25, ridge via augmentation):")
id_errs = []
for seed in SEEDS[:3]:
A, b, rng = instance(seed)
Aa = np.vstack([A, math.sqrt(LAM) * np.eye(N_COLS)])
ba = np.concatenate([b, np.zeros(N_COLS)])
for _ in range(5):
x = rng.standard_normal(N_COLS)
lhs = float(np.sum((Aa @ x - ba) ** 2))
rhs = float(np.sum((A @ x - b) ** 2) + LAM * np.sum(x * x))
id_errs.append(abs(lhs - rhs) / rhs)
print(f" augmentation identity max relative error = {max(id_errs):.2e}")
def ridge_full(A, b):
return np.linalg.solve(A.T @ A + LAM * np.eye(N_COLS), A.T @ b)
def ridge_red(A, b, w):
Aw = A * w[:, None]
return np.linalg.solve(Aw.T @ A + LAM * np.eye(N_COLS), Aw.T @ b)
fr = lambda A, b, x: float(np.sum((A @ x - b) ** 2) + LAM * np.sum(x * x))
out["c4"] = run_claim("ridge", ridge_full, ridge_red, fr)
print("Claim 5 (Corollary 12 at p=1, Huber):")
grid = np.linspace(-3, 3, 6001)
ident = float(np.max(np.abs(gamma_p(grid, 1.0) - huber(grid))))
print(f" gamma_1 == Huber(delta=1) max abs deviation on grid = {ident:.1f}")
ones = lambda A, b: irls(A, b, np.ones(M_ROWS), "huber")
hred = lambda A, b, w: irls(A, b, w, "huber")
fh = lambda A, b, x: float(np.sum(huber(A @ x - b)))
out["c5"] = run_claim("huber", ones, hred, fh)
print(f"Claim 6 (Corollary 11 at p={P_LP}, ell_p):")
hom_err = 0.0
for p in (0.5, 1.0, 1.5, 2.0):
for c in (0.5, 2.0, 3.0):
x = np.array([0.3, 1.7, 2.5])
hom_err = max(
hom_err,
float(np.max(np.abs(np.abs(c) ** p * np.abs(x) ** p - np.abs(c * x) ** p))),
)
print(f" p-homogeneity max abs error over p in {{0.5,1,1.5,2}} = {hom_err:.2e}")
lp_full = lambda A, b: irls(A, b, np.ones(M_ROWS), "lp")
lp_red = lambda A, b, w: irls(A, b, w, "lp")
fp_ = lambda A, b, x: float(np.sum(np.abs(A @ x - b) ** P_LP))
out["c6"] = run_claim("ell_1.5", lp_full, lp_red, fp_)
print(
"note: for p in (0,1) the sparsified objective is non-convex; the "
"paper cites no solver for that sub-range and none is executed here."
)
digest = hashlib.sha256(
json.dumps(
{k: [v[0], v[1]] for k, v in out.items()}, sort_keys=True
).encode()
).hexdigest()
print(f"RESULTS_SHA256={digest}")
if __name__ == "__main__":
main()
|