Cslib.MachineLearning.PACLearning.Learner
abbrevimported Lean
A *learner* using m samples is a function that takes a labeled sample and produces a hypothesis (a function from the domain to the label type).
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open MeasureTheory Set in open scoped ENNReal NNReal in abbrev Cslib.MachineLearning.PACLearning.Learner (α β : Type*) (m : ℕ)
- Defined in
- CSLib, `Cslib.MachineLearning.PACLearning.Learner`
- 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.Learner← Cslib.MachineLearning.PACLearning.Learner (Cslib/MachineLearning/PACLearning/Defs.lean:129): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Built on 1
- Cslib.MachineLearning.PACLearning.LabeledSampleA *labeled sample* of size
mover domainαwith label typeβis a finite sequence of(point, label)pairs.
- Cslib.MachineLearning.PACLearning.LabeledSampleA *labeled sample* of size
- Used by 14
- 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.IsConsistentA learner is *consistent* with the concept class
Cif, on every labeled sample it receives, its output hypothesis lies in the version… - 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.IsConsistent.empiricalError_eq_zeroA consistent learner has zero empirical error on every sample.
- 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.IsConsistent.output_mem_conceptClassA consistent learner's output is always in the concept class.
- 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.IsConsistent.output_agreesA consistent learner's output agrees with the sample on every observed point.
- Cslib.MachineLearning.PACLearning.IsConsistent.empiricalMiscount_eq_zeroA consistent learner has zero empirical miscount on every sample.
- 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 /-- A *learner* using `m` samples is a function that takes a labeled sample and produces a hypothesis (a function from the domain to the label type). -/ abbrev Cslib.MachineLearning.PACLearning.Learner (α β : Type*) (m : ℕ) := LabeledSample α β m → (α → β)