Lemma 3.1 (Sauer): if VCD(C) ≤ d then Π_C(m) ≤ Φ_d(m) for every m
ProvedComputationalLearning.sauer_lemmacombinatoricssauer-lemmavc-dimension
Lemma 3.1. If , then for any , .
Formally: for every concept class with and every , , where is the maximum number of dichotomies realized on a set of points and is defined by the recurrence of Definition 11.
Preamble
import Definitions.Def_ComputationalLearning_VC open MeasureTheory
Formal statement
namespace ComputationalLearning
/-- **Lemma 3.1** (p. 55, Sauer's lemma). If `VCD(C) = d`, then for any `m`, `Π_C(m) ≤ Φ_d(m)`.
Stated for every class of VC dimension at most `d`. -/
theorem sauer_lemma {X : Type*} [MeasurableSpace X] (C : Set (X → Bool)) (d : ℕ)
(hd : vcDim C ≤ d) (m : ℕ) :
growth C m ≤ Phi d m := by sorry
end ComputationalLearning
Source
Kearns and Vazirani, An Introduction to Computational Learning Theory, MIT Press 1994, doi:10.7551/mitpress/3897.001.0001, §3.4 pp. 55-56, Lemma 3.1 with its proof (induction on d and m through the class C')
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.