Cslib.MachineLearning.PACLearning.sampleComplexity_le_of_forall
theoremverifiedformalizationimported Lean
General pointwise monotonicity of sampleComplexity: if every witness sample size for (L₁, ε₁, δ₁, C₁, 𝒟₁) is also a witness for (L₂, ε₂, δ₂, C₂, 𝒟₂), then the latter's sample complexity is at most the former's (provided the former is attained).
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 theorem Cslib.MachineLearning.PACLearning.sampleComplexity_le_of_forall {L₁ L₂ : LearnerModel α β} {ε₁ δ₁ ε₂ δ₂ : Set.Ioo (0 : ℝ≥0) 1} {C₁ C₂ : ConceptClass α β} {𝒟₁ 𝒟₂ : Set (Measure (α × β))} (hL : ∀ {m : ℕ}, L₁ m ε₁ δ₁ C₁ 𝒟₁ → L₂ m ε₂ δ₂ C₂ 𝒟₂) (h : ∃ m, L₁ m ε₁ δ₁ C₁ 𝒟₁) : sampleComplexity L₂ C₂ ε₂ δ₂ 𝒟₂ ≤ sampleComplexity L₁ C₁ ε₁ δ₁ 𝒟₁
- Formalizes
- CSLib, `Cslib.MachineLearning.PACLearning.sampleComplexity_le_of_forall`
- 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_le_of_forall← Cslib.MachineLearning.PACLearning.sampleComplexity_le_of_forall (Cslib/MachineLearning/PACLearning/Defs.lean:364): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- Cslib.MachineLearning.PACLearning.sampleComplexityThe *sample complexity* of a concept class
Cunder a learner modelL, at accuracyε ∈ (0, 1)and confidenceδ ∈ (0, 1)over… - 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.sampleComplexityThe *sample complexity* of a concept class
- Used by 12
- Cslib.MachineLearning.PACLearning.IsRPACLearnable.rsampleComplexity_mono_family
rsampleComplexity_mono_familyfor a randomized-learnable class. - 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.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.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.IsRPACLearnable.rsampleComplexity_antitone_δ
rsampleComplexity_antitone_δfor a randomized-learnable class. - 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.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.IsRPACLearnable.rsampleComplexity_mono_family
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 /-- General pointwise monotonicity of `sampleComplexity`: if every witness sample size for `(L₁, ε₁, δ₁, C₁, 𝒟₁)` is also a witness for `(L₂, ε₂, δ₂, C₂, 𝒟₂)`, then the latter's sample complexity is at most the former's (provided the former is attained). -/ theorem Cslib.MachineLearning.PACLearning.sampleComplexity_le_of_forall {L₁ L₂ : LearnerModel α β} {ε₁ δ₁ ε₂ δ₂ : Set.Ioo (0 : ℝ≥0) 1} {C₁ C₂ : ConceptClass α β} {𝒟₁ 𝒟₂ : Set (Measure (α × β))} (hL : ∀ {m : ℕ}, L₁ m ε₁ δ₁ C₁ 𝒟₁ → L₂ m ε₂ δ₂ C₂ 𝒟₂) (h : ∃ m, L₁ m ε₁ δ₁ C₁ 𝒟₁) : sampleComplexity L₂ C₂ ε₂ δ₂ 𝒟₂ ≤ sampleComplexity L₁ C₁ ε₁ δ₁ 𝒟₁ := Nat.sInf_le (hL (Nat.sInf_mem h))