Theorem H.7 — B&B capacity and probe-size dependence
OpenAggCG.Supplement.theorem_H_7algorithm-configurationcomputational-complexitymachine-learningoptimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1
If every odd final parity-trap size is part of the instance domain, the unnormalized clause-probe tree-size class has pseudo-dimension exactly . For a fixed and every arity , with ,
Differences from the source:
- encoding: the source's encoded MILP domain → the subtype of pairs consisting of the odd probe size and the clause, which uniquely determine the displayed MILP; reason: this removes irrelevant serialization choices without changing any instance or loss
Preamble
import Mathlib import Definitions.Def_FoundationsML_Regression_PseudoDim import Definitions.Def_BartlettNN_Margin_FatShattering import Definitions.Def_AggCG_Supplement_clauseProbeMILP
Formal statement
namespace AggCG.Supplement
/-- **Theorem H.7** (Capacity and probe-size dependence; Sharma, *Computational Complexity of Data-Driven
Configuration for Integer Programming, Clustering, and Learning Algorithms*, STOC 2027 submission
(manuscript sha256 f7ea0248…), p.48, PDF p.49), for the B&B policy family of §H.2 with parameter
`θ ∈ [0, 1]`:
(1) fix `T` and allow every odd probe size `k∗` as part of the encoded instance; the unnormalized
tree-size class `{Q ↦ TreeSize_θ(Q)}` has `Pdim = T` on the clause-probe domain (clauses of at most three
literals);
(2) for a fixed `H = h(k∗) ≥ 4(2T + 3 + 38T)` and each `r ∈ {1, 2, 3}`, on the class `X_{T,r}` of encoded
MILPs whose clauses have arity at most `r`, with `M = H + 2T + 3 + 38T` and `f_θ(Q) = TreeSize_θ(Q)/M`,
`fat_{1/4}({f_θ}|X_{T,r}) = Pdim({f_θ}|X_{T,r}) = T` (eq. (18)).
**Formalization Note** An encoded MILP is identified by its probe size `k∗` and clause (which determine the
block sizes (15)); the fixed `H` is given through an odd `k∗` with `h(k∗) = H`. -/
theorem theorem_H_7 :
(∀ T : ℕ, FoundationsML.Regression.PseudoDim
{g : {x : ℕ × CookLevin.Clause // Odd x.1 ∧ ProbeClause 3 T x.2} → ℝ |
∃ θ ∈ Set.Icc (0 : ℝ) 1, ∀ x, g x = probeTreeSize T (clauseSizes T x.1.2 x.1.1) θ} T) ∧
(∀ (T kstar : ℕ), Odd kstar → 4 * (2 * T + 3 + 38 * T) ≤ trapCount kstar → ∀ r : ℕ, 1 ≤ r → r ≤ 3 →
BartlettNN.Margin.fat
{g : {C : CookLevin.Clause // ProbeClause r T C} → ℝ | ∃ θ ∈ Set.Icc (0 : ℝ) 1, ∀ C,
g C = (probeTreeSize T (clauseSizes T C.1 kstar) θ : ℝ) /
((trapCount kstar + 2 * T + 3 + 38 * T : ℕ) : ℝ)} (1 / 4) = T ∧
FoundationsML.Regression.PseudoDim
{g : {C : CookLevin.Clause // ProbeClause r T C} → ℝ | ∃ θ ∈ Set.Icc (0 : ℝ) 1, ∀ C,
g C = (probeTreeSize T (clauseSizes T C.1 kstar) θ : ℝ) /
((trapCount kstar + 2 * T + 3 + 38 * T : ℕ) : ℝ)} T) := by sorry
end AggCG.Supplement
Source
Sharma, STOC 2027 submission (manuscript sha256 f7ea0248…), Theorem H.7 and eq. (18), p.48, PDF p.49