The fundamental theorem of statistical learning. For a measurable concept class, finite VC dimension, eventually polynomial growth, and PAC learnability are mutually equivalent.
DeclvcDim_fundamental_theorem
∀ {X : Type u} [inst : MeasurableSpace X] [MeasurableSingletonClass X] (C : ConceptClass X Bool)
[MeasurableConceptClass X C],
(VCDim X C < ⊤ ↔ PACLearnable X C) ∧
(VCDim X C < ⊤ ↔ ∃ K d, ∀ᶠ (m : ℕ) in Filter.atTop, ↑(GrowthFunction X C m) ≤ K * ↑m ^ d)TopicPAC learnability
Arguments
| DOI | Author | Date |
|---|---|---|
| MTH.R-2026-6027 | Dhruv Gupta | 2026-09-24T00:00:00Z |
DOIMTH.C-2026-6027
Cite
Verification
- Library
- FLT_Proofs.Complexity.IndependentVC.FundamentalTheorem
- Statement digest
- 5744d678f6dc
- First verified
- 2026-09-24T00:00:00Z