Width-bounded online-matching probe ERM
DefinitionAggCG_Supplement_ProbeERMLangalgorithm-configurationcomputational-complexitymachine-learningoptimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1
A width- probe contains at most offline vertices and at most one vertex from each pair . The ERM language asks whether some makes the average normalized matching regret at most a rational threshold; its zero-loss variant asks whether every listed probe has zero loss.
Definition code
import Mathlib
import Definitions.Def_CookLevin_Satisfiability
import Definitions.Def_QAlgorithms_ClassicalRationalEncoding
import Definitions.Def_AggCG_Supplement_matchLoss
namespace AggCG.Supplement
/-- A probe of width at most `w` over `T` prefix pairs, given as a list of offline vertices: nonempty, no
repetition, at most `w` vertices, at most one from each pair (Sharma, *Computational Complexity of
Data-Driven Configuration for Integer Programming, Clustering, and Learning Algorithms*, STOC 2027
submission (manuscript sha256 f7ea0248…), §G.1.3, p.41, PDF p.42; §G.3.2, p.43, PDF p.44: "a list of
width-at-most-three probe graphs"). -/
def ValidProbeList (w T : ℕ) (l : List (Offline T)) : Prop :=
l ≠ [] ∧ l.Nodup ∧ l.length ≤ w ∧ ∀ j : Fin T, ¬ ((j, true) ∈ l ∧ (j, false) ∈ l)
/-- The code of an offline vertex: `A_j ↦ 2j + 1`, `B_j ↦ 2j`. -/
def offlineCode {T : ℕ} (v : Offline T) : ℕ := 2 * v.1.val + if v.2 then 1 else 0
/-- The code of a training set: `T` in unary, then the list of probes as lists of vertex codes. -/
def encodeProbes (T : ℕ) (P : List (List (Offline T))) : List Bool :=
CookLevin.encodeNat T ++ CookLevin.encodeFormulaN (P.map fun l => l.map offlineCode)
/-- The empirical (average) normalized regret of `θ` on a training set of probes. -/
noncomputable def avgMatchLoss (T : ℕ) (θ : ℝ) (P : List (List (Offline T))) : ℝ :=
(1 / (P.length : ℝ)) * (P.map fun l => matchLoss T θ l.toFinset).sum
/-- Width-`w` probe ERM, decision version: `T`, a list of width-`≤ w` probes and a rational threshold `K`;
is there `θ ∈ [0, 1]` with empirical regret at most `K`? Strings that encode no valid input are rejected. -/
def ProbeERMLang (w : ℕ) : CookLevin.Language := fun x =>
∃ (T : ℕ) (P : List (List (Offline T))) (K : ℚ),
x = encodeProbes T P ++ QAlgorithms.LocalHamiltonian.encRat K ∧ (∀ l ∈ P, ValidProbeList w T l) ∧
∃ θ ∈ Set.Icc (0 : ℝ) 1, avgMatchLoss T θ P ≤ K
/-- Width-`w` zero-loss probe ERM (§G.3.2, p.43: "Matching-Probe-ERM-Zero takes T and a list of
width-at-most-three probe graphs and asks whether there is θ ∈ [0, 1] with zero empirical regret"). -/
def ProbeZeroLang (w : ℕ) : CookLevin.Language := fun x =>
∃ (T : ℕ) (P : List (List (Offline T))),
x = encodeProbes T P ∧ (∀ l ∈ P, ValidProbeList w T l) ∧
∃ θ ∈ Set.Icc (0 : ℝ) 1, ∀ l ∈ P, matchLoss T θ l.toFinset = 0
/-- A finite multiplicative approximation algorithm for width-`≤ 3` probe ERM: on every valid training
set it returns the code of a rational `q ∈ [0, 1]` whose empirical regret is at most `α` times that of
every `θ ∈ [0, 1]`, for a factor `α` that may depend on the input.
**Formalization Note** Same shape as the published `AggCG.IsFactorApprox`. -/
def IsFactorApproxProbe (A : List Bool → List Bool) : Prop :=
∃ α : (T : ℕ) → List (List (Offline T)) → ℝ, ∀ (T : ℕ) (P : List (List (Offline T))),
(∀ l ∈ P, ValidProbeList 3 T l) → ∃ q : ℚ,
A (encodeProbes T P) = QAlgorithms.LocalHamiltonian.encRat q ∧ 0 ≤ q ∧ q ≤ 1 ∧
∀ θ ∈ Set.Icc (0 : ℝ) 1, avgMatchLoss T q P ≤ α T P * avgMatchLoss T θ P
end AggCG.Supplement
Source
Sharma, STOC 2027 submission (manuscript sha256 f7ea0248…), §G.1.3 and §G.3.2, pp.41,43, PDF pp.42,44