Cslib.MachineLearning.PACLearning.sampleComplexity
defimported Lean
The *sample complexity* of a concept class C under a learner model L, at accuracy ε ∈ (0, 1) and confidence δ ∈ (0, 1) over distribution family 𝒟, is the smallest sample size m with L m ε δ C 𝒟. Specialize with L := IsPACLearnerFor for the deterministic model and L := IsRPACLearnerFor for the randomized one. Caveat: because sInf on ℕ returns 0 for the empty set, this definition returns 0 when no learner exists (e.g., a concept class of infinite VC dimension). It is only meaningful when the defining set {m | L m ε δ C 𝒟} is nonempty. The IsPACLearnable.sampleComplexity_* variants below discharge this nonemptiness from a learnability hypothesis.
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.sampleComplexity (L : LearnerModel α β) (C : ConceptClass α β) (ε δ : Set.Ioo (0 : ℝ≥0) 1) (𝒟 : Set (Measure (α × β))) : ℕ
- Defined in
- CSLib, `Cslib.MachineLearning.PACLearning.sampleComplexity`
- 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.sampleComplexity← Cslib.MachineLearning.PACLearning.sampleComplexity (Cslib/MachineLearning/PACLearning/Defs.lean:342): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Built on 2
- 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.LearnerModelA *learner model* is a predicate on (sample size, accuracy, confidence, concept class, distribution family) that classifies which sample…
- Cslib.MachineLearning.PACLearning.ConceptClassA *concept class* over domain
- Used by 10
- Cslib.MachineLearning.PACLearning.sampleComplexity_antitone_δDeterministic sample complexity is antitone in the confidence parameter
δ: weaker confidence requires no more samples. - 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.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.IsPACLearnable.sampleComplexity_mono_C
sampleComplexity_mono_Cfor a learnable class (learnability at the *larger* classC'is the hypothesis). - Cslib.MachineLearning.PACLearning.rsampleComplexityThe *randomized sample complexity* of
C, i.e.sampleComplexityinstantiated at the randomized learner modelIsRPACLearnerFor. The… - Cslib.MachineLearning.PACLearning.sampleComplexity_antitone_εDeterministic sample complexity is antitone in the accuracy parameter
ε: weaker accuracy requires no more samples. - Cslib.MachineLearning.PACLearning.IsPACLearnable.sampleComplexity_antitone_δ
sampleComplexity_antitone_δfor a learnable class: the nonemptiness hypothesis comes for free fromIsPACLearnable. - Cslib.MachineLearning.PACLearning.IsPACLearnable.sampleComplexity_antitone_ε
sampleComplexity_antitone_εfor a learnable class. - Cslib.MachineLearning.PACLearning.sampleComplexity_le_of_forallGeneral pointwise monotonicity of
sampleComplexity: if every witness sample size for(L₁, ε₁, δ₁, C₁, 𝒟₁)is also a witness for…
- Cslib.MachineLearning.PACLearning.sampleComplexity_antitone_δDeterministic sample complexity is antitone in the confidence parameter
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 *sample complexity* of a concept class `C` under a learner model `L`, at accuracy `ε ∈ (0, 1)` and confidence `δ ∈ (0, 1)` over distribution family `𝒟`, is the smallest sample size `m` with `L m ε δ C 𝒟`. Specialize with `L := IsPACLearnerFor` for the deterministic model and `L := IsRPACLearnerFor` for the randomized one. **Caveat**: because `sInf` on `ℕ` returns `0` for the empty set, this definition returns `0` when no learner exists (e.g., a concept class of infinite VC dimension). It is only meaningful when the defining set `{m | L m ε δ C 𝒟}` is nonempty. The `IsPACLearnable.sampleComplexity_*` variants below discharge this nonemptiness from a learnability hypothesis. -/ noncomputable def Cslib.MachineLearning.PACLearning.sampleComplexity (L : LearnerModel α β) (C : ConceptClass α β) (ε δ : Set.Ioo (0 : ℝ≥0) 1) (𝒟 : Set (Measure (α × β))) : ℕ := sInf {m : ℕ | L m ε δ C 𝒟}