Cslib.MachineLearning.PACLearning.IsPACLearnerFor
defimported Lean
IsPACLearnerFor m ε δ C 𝒟 asserts that there exists a learner using m samples that is (ε, δ)-correct for the concept class C over the distribution family 𝒟: for every probability measure D ∈ 𝒟 on α × β, the probability (over i.i.d. samples from D) that the learner's hypothesis has error exceeding opt_C(D) + ε is at most δ. The parameters ε and δ are elements of Set.Ioo (0 : ℝ≥0) 1, bundling the value with the proof that it lies in (0, 1). This ensures the condition is non-vacuous: ε < 1 prevents the error threshold from exceeding the maximum possible error under a probability measure, and δ < 1 prevents the confidence bound from being trivially satisfied.
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.IsPACLearnerFor (m : ℕ) (ε δ : Set.Ioo (0 : ℝ≥0) 1) (C : ConceptClass α β) (𝒟 : Set (Measure (α × β))) : Prop
- Defined in
- CSLib, `Cslib.MachineLearning.PACLearning.IsPACLearnerFor`
- 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.IsPACLearnerFor← Cslib.MachineLearning.PACLearning.IsPACLearnerFor (Cslib/MachineLearning/PACLearning/Defs.lean:158): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Built on 5
- Cslib.MachineLearning.PACLearning.errorThe *prediction error* (0-1 loss) of a hypothesis
hunder a joint distributionDonα × β, defined as the probability that the… - Cslib.MachineLearning.PACLearning.LabeledSampleA *labeled sample* of size
mover domainαwith label typeβis a finite sequence of(point, label)pairs. - Cslib.MachineLearning.PACLearning.optimalErrorThe *optimal error* of a concept class
Cunder a joint distributionD, defined as the infimum oferror D cover all concepts… - 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.LearnerA *learner* using
msamples is a function that takes a labeled sample and produces a hypothesis (a function from the domain to the label…
- Cslib.MachineLearning.PACLearning.errorThe *prediction error* (0-1 loss) of a hypothesis
- Used by 17
- Cslib.MachineLearning.PACLearning.IsPACLearnable.antitone_CPAC learnability is antitone in the concept class: a subclass of a learnable class is learnable.
- Cslib.MachineLearning.PACLearning.sampleComplexity_antitone_δDeterministic sample complexity is antitone in the confidence parameter
δ: weaker confidence requires no more samples. - Cslib.MachineLearning.PACLearning.IsPACLearnerFor.antitone_familyThe deterministic PAC learner predicate is antitone in the distribution family: a learner for a larger family
𝒟'is also a learner for… - Cslib.MachineLearning.PACLearning.sampleComplexity_mono_familyDeterministic sample complexity is monotone in the distribution family under
⊆: a smaller family (fewer distributions to cover) requires… - Cslib.MachineLearning.PACLearning.IsPACLearnerFor.mono_δA PAC learner with confidence
δ₁is also a PAC learner with any weaker confidenceδ₂ ≥ δ₁: the failure-probability bound only gets… - Cslib.MachineLearning.PACLearning.sampleComplexity_mono_CDeterministic sample complexity is monotone in the concept class under
⊆: a smaller class (weaker agnostic benchmark) requires no more… - Cslib.MachineLearning.PACLearning.IsPACLearnable.sampleComplexity_mono_family
sampleComplexity_mono_familyfor a learnable class (learnability at the *larger* family𝒟'is the hypothesis). - Cslib.MachineLearning.PACLearning.IsPACLearnerFor.mono_εA PAC learner with accuracy
ε₁is also a PAC learner with any weaker accuracyε₂ ≥ ε₁: the bad event{error > opt + ε}only shrinks. - Cslib.MachineLearning.PACLearning.IsPACLearnerFor.toIsRPACLearnerForEvery deterministic PAC learner is in particular a randomized PAC learner (with the trivial one-point randomness space
PUnit). - Cslib.MachineLearning.PACLearning.IsPACLearnable.sampleComplexity_mono_C
sampleComplexity_mono_Cfor a learnable class (learnability at the *larger* classC'is the hypothesis). - Cslib.MachineLearning.PACLearning.sampleComplexity_antitone_εDeterministic sample complexity is antitone in the accuracy parameter
ε: weaker accuracy requires no more samples. - 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. - Cslib.MachineLearning.PACLearning.IsPACLearnableA concept class
Cis *PAC learnable* over the distribution family𝒟if for every accuracyε ∈ (0, 1)and confidenceδ ∈ (0, 1),… - Cslib.MachineLearning.PACLearning.IsPACLearnerFor.antitone_CThe deterministic PAC learner predicate is antitone in the concept class: a learner for a larger class
C'is also a learner for any…
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 /-- `IsPACLearnerFor m ε δ C 𝒟` asserts that there exists a learner using `m` samples that is `(ε, δ)`-correct for the concept class `C` over the distribution family `𝒟`: for every probability measure `D ∈ 𝒟` on `α × β`, the probability (over i.i.d. samples from `D`) that the learner's hypothesis has error exceeding `opt_C(D) + ε` is at most `δ`. The parameters `ε` and `δ` are elements of `Set.Ioo (0 : ℝ≥0) 1`, bundling the value with the proof that it lies in `(0, 1)`. This ensures the condition is non-vacuous: `ε < 1` prevents the error threshold from exceeding the maximum possible error under a probability measure, and `δ < 1` prevents the confidence bound from being trivially satisfied. -/ noncomputable def Cslib.MachineLearning.PACLearning.IsPACLearnerFor (m : ℕ) (ε δ : Set.Ioo (0 : ℝ≥0) 1) (C : ConceptClass α β) (𝒟 : Set (Measure (α × β))) : Prop := ∃ A : Learner α β m, ∀ (D : Measure (α × β)) [IsProbabilityMeasure D], D ∈ 𝒟 → (Measure.pi (fun _ : Fin m => D)) {S : LabeledSample α β m | error D (A S) > optimalError D C + ↑ε.val} ≤ ↑δ.val