Cslib.MachineLearning.PACLearning.IsRPACLearnerFor
IsRPACLearnerFor m ε δ C 𝒟 asserts that there exists a *randomized* learner using m samples that is (ε, δ)-correct for the concept class C over the distribution family 𝒟. A randomized learner draws internal randomness ω from a probability space (Ω, Q) and acts as the deterministic learner A(ω). For every probability measure D ∈ 𝒟, the failure probability function ω ↦ D^m{S | error(A(ω)(S)) > opt_C(D) + ε} must be Q-a.e. measurable, and its expectation over ω must be at most δ. The randomness space Ω : Type* is universe-polymorphic; the universe is an implicit parameter of IsRPACLearnerFor, and downstream statements reference it via the pattern IsRPACLearnerFor.{_, _, u}. Fix u := 0 for the usual case of a standard randomness space. A deterministic learner (IsPACLearnerFor) is the special case Ω = PUnit; see IsPACLearnerFor.toIsRPACLearnerFor.
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.IsRPACLearnerFor (m : ℕ) (ε δ : Set.Ioo (0 : ℝ≥0) 1) (C : ConceptClass α β) (𝒟 : Set (Measure (α × β))) : Prop
- Defined in
- CSLib, `Cslib.MachineLearning.PACLearning.IsRPACLearnerFor`
- 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.IsRPACLearnerFor← Cslib.MachineLearning.PACLearning.IsRPACLearnerFor (Cslib/MachineLearning/PACLearning/Defs.lean:181): 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 11
- 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.IsRPACLearnable.rsampleComplexity_mono_family
rsampleComplexity_mono_familyfor a randomized-learnable class. - Cslib.MachineLearning.PACLearning.IsRPACLearnableA concept class
Cis *randomized PAC learnable* over the distribution family𝒟if for every accuracyε ∈ (0, 1)and confidence… - Cslib.MachineLearning.PACLearning.rsampleComplexity_mono_familyRandomized sample complexity is monotone in the distribution family under
⊆. - Cslib.MachineLearning.PACLearning.rsampleComplexity_antitone_δRandomized sample complexity is antitone in the confidence parameter
δ. - 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.toIsRPACLearnerForEvery deterministic PAC learner is in particular a randomized PAC learner (with the trivial one-point randomness space
PUnit). - Cslib.MachineLearning.PACLearning.IsRPACLearnable.antitone_familyRandomized PAC learnability is antitone in the distribution family.
- Cslib.MachineLearning.PACLearning.IsRPACLearnable.rsampleComplexity_antitone_δ
rsampleComplexity_antitone_δfor a randomized-learnable class. - Cslib.MachineLearning.PACLearning.rsampleComplexityThe *randomized sample complexity* of
C, i.e.sampleComplexityinstantiated at the randomized learner modelIsRPACLearnerFor. The… - Cslib.MachineLearning.PACLearning.IsPACLearnable.toIsRPACLearnableDeterministic PAC learnability implies randomized PAC learnability.
- Cslib.MachineLearning.PACLearning.IsRPACLearnerFor.antitone_familyThe randomized PAC learner predicate is antitone in the distribution family. The universe of the randomness space
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 /-- `IsRPACLearnerFor m ε δ C 𝒟` asserts that there exists a *randomized* learner using `m` samples that is `(ε, δ)`-correct for the concept class `C` over the distribution family `𝒟`. A randomized learner draws internal randomness `ω` from a probability space `(Ω, Q)` and acts as the deterministic learner `A(ω)`. For every probability measure `D ∈ 𝒟`, the failure probability function `ω ↦ D^m{S | error(A(ω)(S)) > opt_C(D) + ε}` must be `Q`-a.e. measurable, and its expectation over `ω` must be at most `δ`. The randomness space `Ω : Type*` is universe-polymorphic; the universe is an implicit parameter of `IsRPACLearnerFor`, and downstream statements reference it via the pattern `IsRPACLearnerFor.{_, _, u}`. Fix `u := 0` for the usual case of a standard randomness space. A deterministic learner (`IsPACLearnerFor`) is the special case `Ω = PUnit`; see `IsPACLearnerFor.toIsRPACLearnerFor`. -/ noncomputable def Cslib.MachineLearning.PACLearning.IsRPACLearnerFor (m : ℕ) (ε δ : Set.Ioo (0 : ℝ≥0) 1) (C : ConceptClass α β) (𝒟 : Set (Measure (α × β))) : Prop := ∃ (Ω : Type*) (_ : MeasurableSpace Ω) (Q : Measure Ω) (_ : IsProbabilityMeasure Q) (A : Ω → Learner α β m), ∀ (D : Measure (α × β)) [IsProbabilityMeasure D], D ∈ 𝒟 → AEMeasurable (fun ω => (Measure.pi (fun _ : Fin m => D)) {S : LabeledSample α β m | error D ((A ω) S) > optimalError D C + ↑ε.val}) Q ∧ ∫⁻ ω, (Measure.pi (fun _ : Fin m => D)) {S : LabeledSample α β m | error D ((A ω) S) > optimalError D C + ↑ε.val} ∂Q ≤ ↑δ.val