Theorem G.1 — online-matching capacity and ERM hardness
OpenAggCG.Supplement.theorem_G_1algorithm-configurationcomputational-complexitymachine-learningoptimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1
For every , the explicit one-parameter dyadic online-matching policy has an instance domain with vertices and at most edges per instance, and
Width-one probe ERM is in , width-two exact ERM is NP-hard, and width-three zero-loss ERM is NP-complete. A finite-factor polynomial-time approximation for normalized regret would imply , although every rational-parameter loss evaluation is polynomial-time.
Differences from the source:
- encoding: the source states the three ERM problems and polynomial-time loss evaluation informally → Lean fixes self-delimiting rational input languages and the Cook–Levin polynomial-time model; reason: these are the explicit languages described in §G.3.2 and preserve all width and threshold conditions
Preamble
import Mathlib import Definitions.Def_CookLevin_Complexity import Definitions.Def_FoundationsML_Regression_PseudoDim import Definitions.Def_BartlettNN_Margin_FatShattering import Definitions.Def_AggCG_PEqNP import Definitions.Def_AggCG_Supplement_InP import Definitions.Def_AggCG_Supplement_ProbeERMLang
Formal statement
namespace AggCG.Supplement
/-- **Theorem G.1** (Joint statistical and ERM hardness; Sharma, *Computational Complexity of Data-Driven
Configuration for Integer Programming, Clustering, and Learning Algorithms*, STOC 2027 submission
(manuscript sha256 f7ea0248…), p.41, PDF p.42), for the one-parameter dyadic policy of §G.1.2 on
online-arrival-weighted matching and the instance domain `X_T` of §G.1.1–G.1.3:
(1) every instance has `3T + 1` vertices and at most `2T + 3` edges;
(2) `fat_{1/4}(F_T) = Pdim(F_T) = T` for every `T`;
(3) width-one probe ERM is in P;
(4) width-two exact ERM is NP-hard;
(5) width-three zero-loss ERM is NP-complete;
(6) a polynomial-time finite multiplicative approximation of ERM under normalized regret (width at most
three) gives `P = NP`;
(7) the loss of an instance at a rational parameter is computable in polynomial time.
**Formalization Note** The paper's "there is a policy family" is realized by the paper's own policy
(`matchLoss`). ERM languages take `T`, a list of probes and (decision versions) a rational threshold on the
average regret (§G.3.2). "Unless P = NP" is the published `AggCG.PEqNP`. -/
theorem theorem_G_1 :
(∀ (T : ℕ) (S : Finset (Offline T)), ValidProbe T S →
Fintype.card (Offline T) + (probeInst T S).k = 3 * T + 1 ∧
∑ i, ((probeInst T S).nbr i).card ≤ 2 * T + 3) ∧
(∀ T : ℕ, BartlettNN.Margin.fat (matchClass T) (1 / 4) = T ∧
FoundationsML.Regression.PseudoDim (matchClass T) T) ∧
InP (ProbeERMLang 1) ∧
CookLevin.NPHard (ProbeERMLang 2) ∧
CookLevin.NPComplete (ProbeZeroLang 3) ∧
(∀ A : List Bool → List Bool, CookLevin.IsPolyTimeComputable A → IsFactorApproxProbe A →
AggCG.PEqNP) ∧
(∃ g : List Bool → List Bool, CookLevin.IsPolyTimeComputable g ∧
∀ (T : ℕ) (l : List (Offline T)) (q : ℚ), ValidProbeList 3 T l → 0 ≤ q → q ≤ 1 →
∃ r : ℚ, g (encodeProbes T [l] ++ QAlgorithms.LocalHamiltonian.encRat q) =
QAlgorithms.LocalHamiltonian.encRat r ∧ (r : ℝ) = matchLoss T q l.toFinset) := by sorry
end AggCG.Supplement
Source
Sharma, STOC 2027 submission (manuscript sha256 f7ea0248…), Theorem G.1, p.41, PDF p.42; §G.3.2, p.43, PDF p.44