Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Extended teaching dimension, fractional splitting fγf\gammafγ and fractional extended teaching dimension

Definition
ExactLearningSeparation678_Randomized_Supplement_Teaching

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

machine-learningp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationquery-complexity

Let C⊆{0,1}NC\subseteq\{0,1\}^NC⊆{0,1}N be a concept class and, for a distribution μ\muμ on CCC, write μ(Ci,b)\mu(C_{i,b})μ(Ci,b​) for the mass of the concepts ccc with ci=bc_i=bci​=b.

  1. Extended teaching dimension. For any h∈{0,1}Nh\in\{0,1\}^Nh∈{0,1}N (in CCC or not), a set S⊆[N]S\subseteq[N]S⊆[N] is specifying if at most one concept of CCC agrees with hhh on all of SSS, and
ETD(C,h)=min⁡{∣S∣:S specifying for h},ETD(C)=max⁡h∈{0,1}NETD(C,h).\mathrm{ETD}(C,h)=\min\{|S|: S\text{ specifying for }h\},\qquad \mathrm{ETD}(C)=\max_{h\in\{0,1\}^N}\mathrm{ETD}(C,h).ETD(C,h)=min{∣S∣:S specifying for h},ETD(C)=h∈{0,1}Nmax​ETD(C,h).
  1. Fractional splitting parameter (Definition 4.5).
fγ(C)=min⁡μ distribution on Cmax⁡cμ(c)≤1/2 max⁡i∈[N]min⁡{μ(Ci,0),μ(Ci,1)}.f\gamma(C)=\min_{\substack{\mu\text{ distribution on }C\\ \max_c\mu(c)\le1/2}}\ \max_{i\in[N]}\min\{\mu(C_{i,0}),\mu(C_{i,1})\}.fγ(C)=μ distribution on Cmaxc​μ(c)≤1/2​min​ i∈[N]max​min{μ(Ci,0​),μ(Ci,1​)}.
  1. Fractional extended teaching dimension (Definition 4.7).
fETD(C,h)=min⁡c∗∈Cw1,…,wN≥0{∑i=1Nwi: ∑i:ci≠hiwi≥1 for every c∈C∖{c∗}},fETD(C)=max⁡h∈{0,1}NfETD(C,h).\mathrm{fETD}(C,h)=\min_{\substack{c^*\in C\\ w_1,\dots,w_N\ge0}}\Big\{\sum_{i=1}^N w_i:\ \sum_{i:c_i\ne h_i}w_i\ge1\text{ for every }c\in C\setminus\{c^*\}\Big\},\qquad \mathrm{fETD}(C)=\max_{h\in\{0,1\}^N}\mathrm{fETD}(C,h).fETD(C,h)=c∗∈Cw1​,…,wN​≥0​min​{i=1∑N​wi​: i:ci​=hi​∑​wi​≥1 for every c∈C∖{c∗}},fETD(C)=h∈{0,1}Nmax​fETD(C,h).

The splitting parameter γ(C)\gamma(C)γ(C) is the mission's published one. These are the fractional relaxations of γ\gammaγ and ETD\mathrm{ETD}ETD compared in Theorem 4.10 and used in the query bounds of Theorems 4.11, 4.12 and 1.6.

Formalization Note Distributions are real mass functions on the members of CCC. The minima are written as real infima over the feasible sets. For fγf\gammafγ on ∣C∣≥2|C|\ge2∣C∣≥2, the feasible capped simplex is nonempty and compact and the objective continuous. For fETD\mathrm{fETD}fETD on nonempty CCC, feasible weights can be clipped to [0,1][0,1][0,1] without increasing cost or violating a constraint; a minimum exists on a finite union of compact cubes. Thus these infima are attained source minima. Where the source assigns no value (∣C∣≤1|C|\le1∣C∣≤1 for fγf\gammafγ, C=∅C=\emptysetC=∅ for fETD\mathrm{fETD}fETD, because no feasible point exists) the value is 000. The maxima over hhh range over all of {0,1}N\{0,1\}^N{0,1}N.

Definition code
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Learning

open Classical
set_option autoImplicit false

namespace ExactLearningSeparation678.Randomized.Supplement

/-- p.31: `ETD(C, h)`, the least size of a coordinate set `S` on which at most one concept of
`C` agrees with `h` (a specifying set; zero agreeing concepts also qualify). The set is nonempty
(`S` = all coordinates). -/
noncomputable def etdAt {ι : Type*} [Fintype ι] (C : Finset (ι → Bool)) (h : ι → Bool) : ℕ :=
  sInf {k : ℕ | ∃ S : Finset ι, S.card = k ∧ (C.filter fun c => ∀ i ∈ S, c i = h i).card ≤ 1}

/-- p.31: `ETD(C) = max_{h ∈ {0,1}^N} ETD(C, h)`, over every ambient `h`, in `C` or not. -/
noncomputable def etd {ι : Type*} [Fintype ι] (C : Finset (ι → Bool)) : ℕ :=
  (Finset.univ : Finset (ι → Bool)).sup fun h => etdAt C h

/-- Definition 4.5, p.31: the probability distributions `µ` on `C` (real masses on the members
of `C`, nonnegative, summing to `1`) with every atom `µ(c) ≤ 1/2`. -/
def IsCappedDist {ι : Type*} (C : Finset (ι → Bool)) (μ : {c // c ∈ C} → ℝ) : Prop :=
  QAlgorithms.Learning.IsDistribution μ ∧ ∀ c, μ c ≤ 1 / 2

/-- p.31: `µ(C_{i,b})`, the mass of the concepts `c ∈ C` with `c_i = b`. -/
noncomputable def massAt {ι : Type*} {C : Finset (ι → Bool)} (μ : {c // c ∈ C} → ℝ) (i : ι)
    (b : Bool) : ℝ :=
  ∑ c ∈ Finset.univ.filter (fun c : {c // c ∈ C} => c.1 i = b), μ c

/-- Definition 4.5, p.31: the objective `max_{i ∈ [N]} min{µ(C_{i,0}), µ(C_{i,1})}`. -/
noncomputable def splitObjective {ι : Type*} [Fintype ι] {C : Finset (ι → Bool)}
    (μ : {c // c ∈ C} → ℝ) : ℝ :=
  ⨆ i : ι, min (massAt μ i false) (massAt μ i true)

/-- Definition 4.5, p.31: the fractional splitting parameter
`fγ(C) = min_µ max_i min{µ(C_{i,0}), µ(C_{i,1})}` over all distributions `µ` on `C` with
`max_c µ(c) ≤ 1/2`. For `|C| ≥ 2` the feasible set is nonempty and the objective is bounded below
by `0`, so this infimum is the source's value (attainment is a fact about the compact feasible
set). Reading for `|C| ≤ 1`, where no distribution is feasible and the source assigns no value:
the empty infimum is `0`. -/
noncomputable def fGamma {ι : Type*} [Fintype ι] (C : Finset (ι → Bool)) : ℝ :=
  ⨅ μ : {μ : {c // c ∈ C} → ℝ // IsCappedDist C μ}, splitObjective μ.1

/-- Definition 4.7, p.31: the feasible pairs `(c*, w)` for `fETD(C, h)`: `c* ∈ C`, real weights
`w_i ≥ 0`, and `∑_{i : c_i ≠ h_i} w_i ≥ 1` for every `c ∈ C ∖ {c*}`. -/
def IsFetdFeasible {ι : Type*} [Fintype ι] (C : Finset (ι → Bool)) (h : ι → Bool)
    (p : (ι → Bool) × (ι → ℝ)) : Prop :=
  p.1 ∈ C ∧ (∀ i, 0 ≤ p.2 i) ∧
    ∀ c ∈ C, c ≠ p.1 → 1 ≤ ∑ i ∈ Finset.univ.filter (fun i => c i ≠ h i), p.2 i

/-- Definition 4.7, p.31: `fETD(C, h) = min_{c* ∈ C, w ≥ 0} ∑_i w_i` subject to the constraints
of `IsFetdFeasible`, minimizing jointly over the exempt concept and the weights. For nonempty
`C` the feasible set is nonempty and the objective is bounded below by `0`, so this infimum is
the source's minimum (an attained linear-program optimum). Reading for `C = ∅`, where no `c*`
exists: the empty infimum is `0`. -/
noncomputable def fetdAt {ι : Type*} [Fintype ι] (C : Finset (ι → Bool)) (h : ι → Bool) : ℝ :=
  ⨅ p : {p : (ι → Bool) × (ι → ℝ) // IsFetdFeasible C h p}, ∑ i, p.1.2 i

/-- Definition 4.7, p.31: `fETD(C) = max_{h ∈ {0,1}^N} fETD(C, h)`, a maximum over the finite set
of all ambient `h`. -/
noncomputable def fetd {ι : Type*} [Fintype ι] (C : Finset (ι → Bool)) : ℝ :=
  ⨆ h : ι → Bool, fetdAt C h

/-! ### Sanity checks -/

example {ι : Type*} [Fintype ι] (h : ι → Bool) : etdAt (∅ : Finset (ι → Bool)) h = 0 :=
  Nat.sInf_eq_zero.2 (Or.inl ⟨∅, rfl, by simp⟩)

example {ι : Type*} [Fintype ι] : fGamma (∅ : Finset (ι → Bool)) = 0 := by
  have : IsEmpty {μ : {c // c ∈ (∅ : Finset (ι → Bool))} → ℝ // IsCappedDist ∅ μ} :=
    ⟨fun μ => by simpa [QAlgorithms.Learning.IsDistribution] using μ.2.1.2⟩
  simp [fGamma]

end ExactLearningSeparation678.Randomized.Supplement
Source
Srinivasan Arunachalam, Amin Shiraz Gilani, Nikhil S. Mande, STOC 2027 submission #678 (October 2026), §4.2.1, p.31 (ETD, Eq. (22)); Definition 4.5, p.31; Definition 4.7, p.31; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/678.pdf

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me