Cslib.MachineLearning.PACLearning.optimalError
defimported Lean
The *optimal error* of a concept class C under a joint distribution D, defined as the infimum of error D c over all concepts c ∈ C. When C is empty this is ⊤, making the PAC learning condition vacuously true.
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.optimalError (D : Measure (α × β)) (C : ConceptClass α β) : ℝ≥0∞
- Defined in
- CSLib, `Cslib.MachineLearning.PACLearning.optimalError`
- 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.optimalError← Cslib.MachineLearning.PACLearning.optimalError (Cslib/MachineLearning/PACLearning/Defs.lean:143): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Built on 2
- 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.ConceptClassA *concept class* over domain
αwith label typeβis a set of functionsα → β. For binary classification (β = Bool), this is…
- Cslib.MachineLearning.PACLearning.errorThe *prediction error* (0-1 loss) of a hypothesis
- Used by 9
- Cslib.MachineLearning.PACLearning.IsPACLearnerFor
IsPACLearnerFor m ε δ C 𝒟asserts that there exists a learner usingmsamples that is(ε, δ)-correct for the concept classCover… - Cslib.MachineLearning.PACLearning.IsRPACLearnerFor.antitone_familyThe randomized PAC learner predicate is antitone in the distribution family. The universe of the randomness space
Ωis pinned so the… - 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.IsRPACLearnerFor.mono_δA randomized PAC learner with confidence
δ₁is also a randomized PAC learner with any weaker confidenceδ₂ ≥ δ₁. Unlikemono_εor… - 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.IsRPACLearnerFor
IsRPACLearnerFor m ε δ C 𝒟asserts that there exists a *randomized* learner usingmsamples that is(ε, δ)-correct for the concept… - 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.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…
- Cslib.MachineLearning.PACLearning.IsPACLearnerFor
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 /-- The *optimal error* of a concept class `C` under a joint distribution `D`, defined as the infimum of `error D c` over all concepts `c ∈ C`. When `C` is empty this is `⊤`, making the PAC learning condition vacuously true. -/ noncomputable def Cslib.MachineLearning.PACLearning.optimalError (D : Measure (α × β)) (C : ConceptClass α β) : ℝ≥0∞ := ⨅ c ∈ C, error D c