Theorem 3.5: PAC learning a class of VC dimension d needs Ω(d/ε) examples; explicit forms m ≤ d/2 and m ≤ (d−1)/(64ε)
ProvedComputationalLearning.vc_lower_boundTheorem 3.5. Any algorithm for PAC learning a concept class of Vapnik–Chervonenkis dimension must use examples in the worst case.
Formally, for a class shattering a set of points on an instance space with measurable singletons, and every learning function on samples of size : (i) if , there are a target and a distribution (uniform on the shattered set) such that the error of 's hypothesis is at least with probability at least over the sample (the book's first argument: the labels of unseen points are fair coins); (ii) if and , there are and (one point of weight , the others of weight ) such that the error exceeds with probability at least . The constants in (ii) instantiate the book's : with fewer than examples the algorithm fails with probability at least for some target and distribution.
import Definitions.Def_ComputationalLearning_VC open MeasureTheory
namespace ComputationalLearning
/-- **Theorem 3.5** (p. 62). Any algorithm for PAC learning a concept class of VC dimension `d`
must use `Ω(d/ε)` examples in the worst case. Stated with the two explicit forms of the proof
(pp. 62–64), for a class shattering some set of `d ≥ 1` points, on an instance space with
measurable singletons, and for every learning function `L` on samples of size `m`:
(i) if `m ≤ d/2`, some target concept in the class and some distribution make the error of
`L`'s hypothesis at least `1/8` with probability at least `1/2`;
(ii) if `ε ≤ 1/16` and `m ≤ (d − 1)/(64ε)`, some target concept and some distribution make the
error greater than `ε` with probability at least `1/4` (so a PAC algorithm with `δ < 1/4` needs
more than `(d − 1)/(64ε)` examples). -/
theorem vc_lower_bound {X : Type*} [MeasurableSpace X] [MeasurableSingletonClass X]
(C : Set (X → Bool)) (d : ℕ) (hd1 : 1 ≤ d) (hd : (d : ℕ∞) ≤ vcDim C) (m : ℕ)
(L : (Fin m → X × Bool) → X → Bool) :
((m : ℝ) ≤ d / 2 → ∃ c ∈ C, ∃ D : Measure X, IsProbabilityMeasure D ∧
ENNReal.ofReal (1 / 2) ≤ sampleLaw D c m {S | 1 / 8 ≤ errorOf D c (L S)}) ∧
(∀ ε : ℝ, 0 < ε → ε ≤ 1 / 16 → (m : ℝ) ≤ (d - 1) / (64 * ε) →
∃ c ∈ C, ∃ D : Measure X, IsProbabilityMeasure D ∧
ENNReal.ofReal (1 / 4) ≤ sampleLaw D c m {S | ε < errorOf D c (L S)}) := by sorry
end ComputationalLearning
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.