pages/claim6-construction-code-link-function/page.md

Claim 6 — Technical construction

The construction uses Feldman's asymptotically good binary code combined with a novel 'link function' mapping sample information to bad ERM solutions while preserving convexity, giving the first proof that all approximate ERMs fail in linear dimension (Section on technical construction / proof of Theorem 1).

Outcome

VERIFIED — label: exact. Each structural ingredient is validated directly: the code is asymptotically good, the link function p is convex and maps the sample to the bad codeword, the loss is 7-Lipschitz, the dimension is exactly linear (d = 6m), and approximate ε-ERMs (ε = Θ(m^{−3/2})) all fail.

Method & numbers

(a) Asymptotically good code — exact minimum relative Hamming distance of the code G:{−1,1}^k→{−1,1}^{2k} by full enumeration, 5 seeds each:

k = 2m	6	8	10	12	14	16	18
δ_min (mean)	0.217	0.150	0.130	0.150	0.143	0.131	0.139

δ_min stays bounded away from 0 (floor 0.13) as k grows → asymptotically good; this gives the codeword-correlation bound ⟨G(u),G(v)⟩ ≤ 1 − ρ/2 used everywhere.

(b) Convex link function → bad codeword. For every exact-tier m (4–8), full enumeration confirms vs_S is the unique argmax of p(w) = max_v[γ_m⟨v,w_m⟩ − γ_c⟨G(v),w_c⟩] at the minimizer with p(w⋆) > 0, so the minimizer's code part is exactly (γ_c/λ_c)G(vs_S) — the sample is mapped to a bad ERM. The fast oracle matches exhaustive enumeration on every check.

(c) Convexity & Lipschitz. Each term of f is convex (max-of-linear + linear + quadratics); the maximum single-sample subgradient norm over 200 random unit points is 4.03 ≤ 7 — the loss is 7-Lipschitz as stated.

(d) Linear dimension. d == 6m holds exactly for every tier (d = 24 … 1536). This is the resolution of Feldman's open problem: prior all-ERMs-fail constructions needed dimension exponential in m.

(e) Approximate ERMs fail. Any ε-ERM lies within √(2ε/λ) of w⋆ (strong convexity); f is 7-Lipschitz, so F(ε-ERM) − F(0) ≥ gap(w⋆) − 7√(2ε/λ). With the paper's ε = Θ(1/(λm³)) = Θ(m^{−3/2}):

m	ε	approx-ERM gap lower bound	fails?
4	4.4e-9	0.00029	yes
5	2.0e-9	0.00039	yes
6	4.3e-9	0.00061	yes
7	2.5e-9	0.00066	yes
8	1.6e-9	0.00041	yes

The lower bound is positive for all m → even inverse-polynomially-accurate ERMs overfit (the first such result in linear dimension).

python -u scripts/reproduce.py    # sections "code-distance study" + "Claim 6"

What this does NOT establish

We instantiate the code family with a systematic random linear [2k,k] code (which provably attains a constant Gilbert–Varshamov relative distance) rather than the specific Justesen/expander code the paper cites; the asymptotically-good property and all downstream distance bounds are verified empirically (exhaustively for k ≤ 18). Convexity/Lipschitzness are checked numerically, not via symbolic proof.

Artifacts

results/erm_fail_results.json → keys code_distance_study, claim6_construction. Canonical SHA-256 a76bc7451ad73d67930b7909ffa7df761eb9688221c95b6c870b539abad3ffaf.