Cslib.MachineLearning.PACLearning.IsPACLearnable
defimported Lean
A concept class C is *PAC learnable* over the distribution family 𝒟 if for every accuracy ε ∈ (0, 1) and confidence δ ∈ (0, 1), there exists a sample size m admitting a deterministic (ε, δ)-PAC learner for C. Here ε and δ are elements of the subtype Set.Ioo (0 : ℝ≥0) 1.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open MeasureTheory Set in open scoped ENNReal NNReal in variable {α : Type*} {β : Type*} [MeasurableSpace α] [MeasurableSpace β] in noncomputable def Cslib.MachineLearning.PACLearning.IsPACLearnable (C : ConceptClass α β) (𝒟 : Set (Measure (α × β))) : Prop
- Defined in
- CSLib, `Cslib.MachineLearning.PACLearning.IsPACLearnable`
- Lean proof
- By Samuel Schlesinger, from github.com/leanprover/cslib at
3951377e5a3f(Copyright (c) 2026 Samuel Schlesinger. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.33.0.Cslib.MachineLearning.PACLearning.IsPACLearnable← Cslib.MachineLearning.PACLearning.IsPACLearnable (Cslib/MachineLearning/PACLearning/Defs.lean:285): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Built on 2
- Cslib.MachineLearning.PACLearning.IsPACLearnerFor
IsPACLearnerFor m ε δ C 𝒟asserts that there exists a learner usingmsamples that is(ε, δ)-correct for the concept classCover… - Cslib.MachineLearning.PACLearning.ConceptClassA *concept class* over domain
αwith label typeβis a set of functionsα → β. For binary classification (β = Bool), this is…
- Cslib.MachineLearning.PACLearning.IsPACLearnerFor
- Used by 7
- Cslib.MachineLearning.PACLearning.IsPACLearnable.antitone_CPAC learnability is antitone in the concept class: a subclass of a learnable class is learnable.
- Cslib.MachineLearning.PACLearning.IsPACLearnable.sampleComplexity_mono_family
sampleComplexity_mono_familyfor a learnable class (learnability at the *larger* family𝒟'is the hypothesis). - Cslib.MachineLearning.PACLearning.IsPACLearnable.sampleComplexity_mono_C
sampleComplexity_mono_Cfor a learnable class (learnability at the *larger* classC'is the hypothesis). - Cslib.MachineLearning.PACLearning.IsPACLearnable.antitone_familyPAC learnability is antitone in the distribution family: a subfamily of a learnable family is learnable.
- Cslib.MachineLearning.PACLearning.IsPACLearnable.sampleComplexity_antitone_δ
sampleComplexity_antitone_δfor a learnable class: the nonemptiness hypothesis comes for free fromIsPACLearnable. - Cslib.MachineLearning.PACLearning.IsPACLearnable.toIsRPACLearnableDeterministic PAC learnability implies randomized PAC learnability.
- Cslib.MachineLearning.PACLearning.IsPACLearnable.sampleComplexity_antitone_ε
sampleComplexity_antitone_εfor a learnable class.
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in open MeasureTheory Set in open scoped ENNReal NNReal in variable {α : Type*} {β : Type*} [MeasurableSpace α] [MeasurableSpace β] in /-- A concept class `C` is *PAC learnable* over the distribution family `𝒟` if for every accuracy `ε ∈ (0, 1)` and confidence `δ ∈ (0, 1)`, there exists a sample size `m` admitting a deterministic `(ε, δ)`-PAC learner for `C`. Here `ε` and `δ` are elements of the subtype `Set.Ioo (0 : ℝ≥0) 1`. -/ noncomputable def Cslib.MachineLearning.PACLearning.IsPACLearnable (C : ConceptClass α β) (𝒟 : Set (Measure (α × β))) : Prop := ∀ (ε δ : Set.Ioo (0 : ℝ≥0) 1), ∃ m, IsPACLearnerFor m ε δ C 𝒟